##
**A novel minimum delay maximum flow multicast algorithm to construct a multicast tree in wireless mesh networks.**
*(English)*
Zbl 1238.68028

Summary: The construction of multicast tree within given constraints, such as delay and capacity, is becoming a major problem in many wireless networks, especially wireless mesh networks (WMN). Due to the limited capacity of the wireless node, a multicast call may be dropped if there is no multicast tree formed within the given constraints. In this paper, we propose a new multicast tree construction algorithm which has maximum traffic flow and minimum delay under capacity constraints. The problem of multicast is formulated as a linear programming (LP) problem with associated constraints. A cost function (CF) is defined to choose the less loaded route among the available ones. A minimum delay maximum flow multicast (MDMF) algorithm is proposed to solve this problem using CF and associated constraints. The performance of the proposed algorithm and CF is evaluated and compared with well-known algorithms with respect to packet delivery fraction, latency, and network throughput. The results obtained show that the proposed algorithm has a lesser number of transmissions for a given CF. Moreover, the proposed algorithm has high throughput, packet delivery fraction and less latency compared to other well-known algorithms in this category.

### MSC:

68M10 | Network design and communication in computer systems |

PDFBibTeX
XMLCite

\textit{N. Kumar} et al., Comput. Math. Appl. 63, No. 2, 481--491 (2012; Zbl 1238.68028)

Full Text:
DOI

### References:

[1] | Akylidiz, F.; Wang, X.; Wang, W., Wireless mesh networks: a survey, Journal of Computer Networks, 47, 4, 445-448 (2005) · Zbl 1152.68319 |

[2] | K. Jain, J. Padhye, V. Padmanabhan, L. Qiu, Impact of interference on multi-hop wireless network performance, in: Proc. of the ACM International Conference on Mobile Computing and Networking, MobiCom, 2003.; K. Jain, J. Padhye, V. Padmanabhan, L. Qiu, Impact of interference on multi-hop wireless network performance, in: Proc. of the ACM International Conference on Mobile Computing and Networking, MobiCom, 2003. |

[3] | R. Cruz, A. Santhanam, Optimal routing, link scheduling and power control in multi-hop wireless networks, in: Proc. of the IEEE Annual Joint Conference of the IEEE Computer and Communications, INFOCOM, 2003.; R. Cruz, A. Santhanam, Optimal routing, link scheduling and power control in multi-hop wireless networks, in: Proc. of the IEEE Annual Joint Conference of the IEEE Computer and Communications, INFOCOM, 2003. |

[4] | J. Zhang, H. Wu, Q. Zhang, B. Li, Joint routing and scheduling in multi-radio multi-channel multi-hop wireless networks, in: Proc. of International Conference on Broadband Networks, BroadNets, 2005.; J. Zhang, H. Wu, Q. Zhang, B. Li, Joint routing and scheduling in multi-radio multi-channel multi-hop wireless networks, in: Proc. of International Conference on Broadband Networks, BroadNets, 2005. |

[5] | M.S. Kodialam, T. Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, in: Proc. of the ACM International Conference on Mobile Computing and Networking, MobiCom, 2005.; M.S. Kodialam, T. Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, in: Proc. of the ACM International Conference on Mobile Computing and Networking, MobiCom, 2005. |

[6] | A. Raniwala, T. Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, in: Proc. of the IEEE Annual Joint Conference of the IEEE Computer and Communications, INFOCOM, 2005.; A. Raniwala, T. Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, in: Proc. of the IEEE Annual Joint Conference of the IEEE Computer and Communications, INFOCOM, 2005. |

[7] | Gupta, P.; Kumar, P. R., The capacity of wireless networks, IEEE Transactions on Information Theory, 46, 2, 388-404 (2000) · Zbl 0991.90511 |

[8] | J. Bicket, D. Aguayo, S. Biswas, R. Morris, Architecture and evaluation of an unplanned 802.11b mesh network, in: Proc. of the ACM International Conference on Mobile Computing and Networking, MobiCom, 2003.; J. Bicket, D. Aguayo, S. Biswas, R. Morris, Architecture and evaluation of an unplanned 802.11b mesh network, in: Proc. of the ACM International Conference on Mobile Computing and Networking, MobiCom, 2003. |

[9] | S. Biswas, R. Morris, ExOR: opportunistic multi-hop routing for wireless networks, in: Proc. of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM, 2005.; S. Biswas, R. Morris, ExOR: opportunistic multi-hop routing for wireless networks, in: Proc. of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM, 2005. |

[10] | S. Chachulski, M. Jennings, S. Katti, D. Katabi, Trading structure for randomness in wireless opportunistic routing, in: Proc. of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM, 2007.; S. Chachulski, M. Jennings, S. Katti, D. Katabi, Trading structure for randomness in wireless opportunistic routing, in: Proc. of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM, 2007. |

[11] | Jahanshahi, M.; Dehghan, M.; Meybodi, M. R., A mathematical formulation for joint channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks, Journal of Network and Computer Applications (2011) |

[12] | Karimi, O. B.; Liu, J.; Li, Z., (Multicast in Multi-channel Wireless Mesh Networking. Multicast in Multi-channel Wireless Mesh Networking, Lecture Notes in Computer Science, LNCS, vol. 6091 (2010)), 148-159 |

[13] | Z. Ke, L. Li, Q. Sun, N. Chen, A QoS multicast routing algorithm for wireless mesh networks, in: Proc. of the ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD, 2007, pp. 835-840.; Z. Ke, L. Li, Q. Sun, N. Chen, A QoS multicast routing algorithm for wireless mesh networks, in: Proc. of the ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD, 2007, pp. 835-840. |

[14] | S.-H. Lim, C. Kim, Y.-B. Ko, N.H. Vaidya, Efficient multicasting for multi-channel multi-interface wireless mesh networks, in: Proc. of the IEEE Military Communications Conference, MILCOM, 2009.; S.-H. Lim, C. Kim, Y.-B. Ko, N.H. Vaidya, Efficient multicasting for multi-channel multi-interface wireless mesh networks, in: Proc. of the IEEE Military Communications Conference, MILCOM, 2009. |

[15] | Nguyen, U. T., On multicast routing in wireless mesh networks, Computer Communications, 31, 7, 1385-1399 (2008) |

[16] | Zeng, G.; Wang, B.; Ding, Y.; Xiao, L.; Mutka, M. W., Efficient multicast algorithms for multichannel wireless mesh networks, IEEE Transactions on Parallel and Distributed Systems, 21, 1, 86-99 (2010) |

[17] | Li, F.; Fang, Y.; Hu, F.; Liu, X., Load-aware multicast routing metrics in multi-radio multi-channel wireless mesh networks, Computer Networks, 55, 9, 2150-2167 (2011) |

[18] | Pourfakhar, E.; Rahmani, A. M., A hybrid QoS multicast framework-based protocol for wireless mesh networks, Computer Communications, 33, 17, 2079-2092 (2010) |

[19] | Acharya, Prashanth A. K.; Belding, Elizabeth M., MARS: link-layer rate selection for multicast transmissions in wireless mesh networks, Ad Hoc Networks, 9, 1, 48-60 (2011) |

[20] | K. Han, Q. Guo, Reducing multicast redundancy and latency in wireless mesh networks, in: Proc. of the International Workshop on Education Technology and Computer Science, ETCS, 2009, pp. 1075-1079.; K. Han, Q. Guo, Reducing multicast redundancy and latency in wireless mesh networks, in: Proc. of the International Workshop on Education Technology and Computer Science, ETCS, 2009, pp. 1075-1079. |

[21] | Rong, B.; Qian, Y.; Lu, K.; Hu, R. Q., Enhanced QoS multicast routing in wireless mesh networks, IEEE Transactions on Wireless Communications, 7, 6, 2119-2130 (2008) |

[22] | X. Zhao, C.T. Chou, J. Guo, S. Jha, A scheme for probabilistically reliable multicast routing in wireless mesh networks, in: Proc. of the IEEE Conference on Local Computer Networks, LCN, 2007, pp. 213-214.; X. Zhao, C.T. Chou, J. Guo, S. Jha, A scheme for probabilistically reliable multicast routing in wireless mesh networks, in: Proc. of the IEEE Conference on Local Computer Networks, LCN, 2007, pp. 213-214. |

[23] | L. Zhao, A.Y. Al-Dubai, G. Min, A QoS aware multicast algorithm for wireless mesh networks, in: Proc. of the IEEE International Symposium on Parallel & Distributed Processing, IPDPS, May 2009.; L. Zhao, A.Y. Al-Dubai, G. Min, A QoS aware multicast algorithm for wireless mesh networks, in: Proc. of the IEEE International Symposium on Parallel & Distributed Processing, IPDPS, May 2009. |

[24] | Torkestani, J. A.; Meybodi, M. R., A link stability-based multicast routing protocol for wireless mobile ad hoc networks, Journal of Network and Computer Applications, 34, 4, 1429-1440 (2011) |

[25] | Menchaca-Mendez, Rolando; Garcia-Luna-Aceves, J. J., Hydra: efficient multicast routing in MANETs using sender-initiated multicast meshes, Pervasive and Mobile Computing, 6, 1, 144-157 (2010) |

[26] | Kharraz, M.-A.; Sarbazi-Azad, H.; Zomaya, Albert Y., On-demand multicast routing protocol with efficient route discovery, Journal of Network and Computer Applications (2011) |

[27] | Manoj, B. S.; Rao, R. R., Load balancing in wireless mesh networks, (Zhang, Y. S., Wireless Mesh Networks: Architectures, Protocols, and Standards (2006), CRC Press) |

[28] | X. Tao, T. Kunz, D. Falconer, Traffic balancing in wireless MESH networks, in: Proc. of the International Conference on Wireless Networks, Communications and Mobile Computing, June 2005, pp. 169-174.; X. Tao, T. Kunz, D. Falconer, Traffic balancing in wireless MESH networks, in: Proc. of the International Conference on Wireless Networks, Communications and Mobile Computing, June 2005, pp. 169-174. |

[29] | Zhao, L.; Al-Dubai, Ahmed Y.; Min, G., GLBM: a new QoS aware multicast scheme for wireless mesh networks, Journal of Systems and Software, 83, 8, 1318-1326 (2010) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.