|
|
An effective scheduling scheme for multi-hop
multicast in wireless mesh networks |
Zheng LIU,Heng DAI,Farouk ALKADHI,Jufeng DAI, |
School of Electronic
Information Engineering, Tianjin University, Tianjin 300072, China; |
|
|
Abstract With the utilization of concurrent transmission strategy, a throughput-enhanced scheduling scheme is devised for multicast service in wireless multi-hop mesh networks. Since the performance of a multicast mechanism is constrained in a wireless setting due to the interference among local wireless transmissions, the interference relationships are first characterized by introducing a graph transformation method. Based on the graph transformation, the multicast scheduling problem is converted to the graph coloring problem, and then a capacity greedy algorithm is designed to provide concurrent transmission scheduling so that the demanded multicast transmission rate can be achieved. Moreover, the necessary and sufficient conditions of multicast schedulable feasibility are derived. Through corresponding simulations, it is shown that the proposed strategy can enhance the throughput of wireless multi-hop multicast systems significantly.
|
Keywords
multicast
wireless mesh networks
scheduling
interference
capacity
|
Issue Date: 05 March 2010
|
|
|
Yang Y, Papagiannaki K, Ci S, et al. Wireless mesh networks: applications, architecturesand protocols. IEEE Network Magazine, January/Febuary 2008, 22(1): 4–5
doi: 10.1109/MNET.2008.4435896
|
|
Akyildiz I, Wang X, Wang W. Wireless mesh networks : a Survey. Computer Networks Journal (Elsevier), January 2005, 47: 445–487
doi: 10.1016/j.comnet.2004.12.001
|
|
Paul S. Multicaston the Internet and its applications. Kluwer, 1998
|
|
Jia W. Implementationof a reliable multicast protocol. Journalof Software: Practice and Experience, 1997, 27(7): 813–850
doi: 10.1002/(SICI)1097-024X(199707)27:7<813::AID-SPE107>3.0.CO;2-E
|
|
Jia W, Zhao W, Xuan D, et al. An efficient fault-tolerant multicast routingprotocol with core-based tree techniques. IEEE Transactions on Parallel and Distributed Systems, 1999, 10(10): 984–1000
doi: 10.1109/71.808133
|
|
Viswanathan H, Mukherjee S. Throughput-range tradeoffof wireless mesh backhaul networks. IEEEJournal on Selected Areas in Communications, March 2006, 24(3): 593–602
doi: 10.1109/JSAC.2005.862408
|
|
Liu Z, Yang M, Dai J. Throughput range based on concurrent transmission inwireless mesh networks. In: Proceedingsof IEEE International Conference on Wireless Communications, Networkingand Mobile Computing (WiCOM2007), September 2007, 1449–1452
|
|
Nguyen U, Xu J. Multicast routing in wirelessmesh networks: minimum cost trees or shortest path trees?. IEEE Communication Magazine, November 2007, 45(11): 72–77
doi: 10.1109/MCOM.2007.4378324
|
|
Ruiz P M, Gomez-Skarmeta AF. Approximatingoptimal multicast trees in wireless multihop networks. In: Proceedings of the 10th IEEE Symposium on Computer and Communication, June 2005, 686–691
|
|
Roy S, Koutsonikolas D, Das S, et al. High throughput multicast routing metrics inwireless mesh networks. In: Proceedingsof International Conference on Interactive Digital Storytelling, 2006
|
|
Yin Z, Li Z, Chen M. A novel channel assignment algorithm for multicast inmulti-radio wireless mesh networks. In:Proceedings of IEEE Symposium on Computers and Communications (ISCC2007), July 2007, 283–288
|
|
Yuan J, Li Z, Yu W, et al. A cross-layer optimization framework for multihopmulticast in wireless mesh network. IEEEJournal on Selected Areas in Communications, 2006, 24(11): 2092–2102
doi: 10.1109/JSAC.2006.881617
|
|
Koutsonikolas D, Das S, Hu Y, An interference-aware fair scheduling for multicast inwireless mesh networks. Journal of Paralleland Distributed Computing, 2008, 68: 372–386
doi: 10.1016/j.jpdc.2007.05.007
|
|
Meng X R, Tan K, Zhang Q. Joint routing and channel assignment in multi-radio wirelessmesh networks. In: Proceedings of IEEEInternational Conference on Communications (ICC 2006), 2006, 3596–3601
|
|
West D B, Introduction to graph theory, PrenticeHall, 2001
|
|
Raman B and Chebrolu K. Design and evaluation ofa new MAC protocol for long-distance 802.11 mesh networks. In: Proceedings of the 11th Annual InternationalConference on Mobile Computing and Networking ( ACM Mobicom 2005), 2005, 156–169
|
|
Brelaz D. Newmethods to color the vertices of a graph. Communications of the ACM, 1979, 22 (4): 251–256
doi: 10.1145/359094.359101
|
|
IEEE Standard 802.16―2004. IEEE Standard for local and metropolitan area networks-Part16: Air Interface for Fixed Broadband Wireless Access Systems, October 2004
|
|
Kodialam M, Nandagopal T. The effect of interferenceon the capacity of multi-hop wireless networks. Bell Labs Technical Report, Lucent Technologies, July 2003
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|