Approximate algorithm for joint routing and scheduling in wireless relay networks

doi:10.7523/j.issn.2095-6134.2010.4.015

Abstract

Abstract:

The problem of joint routing and scheduling in 802.16j based wireless relay networks is studied to minimize the traffic time. The routing problem is solved by linear programming method, and the traffic is allocated to links. A novel link scheduling algorithm based on shifting and switching is proposed. Theoretical analysis indicates that the performance of the proposed algorithm is within a factor of 1.5 of that of any optimal algorithm in the worst case. Simulation results show that with the proposed algorithm near-optimal performance can be effectively achieved.

Key words: wireless relay networks, routing, scheduling, approximate algorithm

CLC Number:

TN929.5

SUN Shao-Feng, WEI Guo. Approximate algorithm for joint routing and scheduling in wireless relay networks[J]. , 2010, 27(4): 530-537.

References

[1] Bononi L, Di Felice M, Molinaro A, et al. Joint channel assignment and multi-path routing for multi-radio wireless mesh networks //IEEE International Conference on Distributed Computing Systems Workshops, ICDCS, 2009: 476-481.

[2] Xie G, Swarmy M N S, Ahmad M O. Joint optimal multipath routing and rate control for multidescription coded video streaming in Ad Hoc networks
[J]. IEEE Transactions on Multimedia, 2008, 10(8): 1687-1697.

[3] Ren J, Qiu Z D, Wang S H. Congestion control for multihop flows in wireless mesh networks
[J]. Journal on Communications, 2008,29(4):99-107(in Chinese). 任娟, 裘正定, 王升辉. 无线mesh网络中多跳数据流的拥塞控制
[J]. 通信学报, 2008, 29(4):99-107.

[4] Zou J, Zhao D M. Connection-based scheduling for supporting real-time traffic in wireless mesh networks
[J]. IEEE Transactions on Wireless Communications, 2009, 8(3): 1182-1187.

[5] Luo H Y, Ci S, Wu D L. A cross-layer optimized distributed scheduling algorithm for peer-to-peer video streaming over multi-hop wireless mesh networks //Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON, 2009: 1-9.

[6] Zou J, Zhao D M. G-BFS: A scheme for scheduling real-time CBR traffic in IEEE 802.11-based mesh networks //Wireless Communications and Networking Conference, WCNC, 2007: 4268-4273.

[7] Chen Q, Niu Z S. Graph theory and opportunistic link scheduling in wireless ad hoc networks
[J]. Journal of Tsinghua University: Science and Technology, 2008, 48(10): 1574-1577(in Chinese). 陈庆, 牛志升. 基于图论的无线多跳网络合作机会调度
[J]. 清华大学学报:自然科学版, 2008,48(10):1574-1577.

[8] Arikan E. Some complexity results about packet radio networks
[J]. IEEE Transactions on Information Theory, 1984, 30(4): 910-918.

[9] Wang B, Mutka M, Torng E. Optimization based rate allocation and scheduling in TDMA based wireless mesh networks //IEEE International Conference on Network Protocols, ICNP, 2008:147-156.

[10] Wei H Y, Ganguly S, Izmailov R, et al. Interference-aware IEEE 802.16 WiMax mesh networks //IEEE Vehicular Technology Conference, VTC, 2005: 3102-3106.

[11] Molle C, Peix F, Rivano H. An optimization framework for the joint routing and scheduling in wireless mesh networks //IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC, 2008: 1-5.

[12] Hong C Y, Pang A C. 3-approximation algorithm for joint routing and link scheduling in wireless relay networks
[J]. IEEE Transactions on Wireless Communications, 2009, 8(2): 856-861.

[13] Fan Y, Thompson J. MIMO configurations for relay channels: theory and practice
[J]. IEEE Transactions on Wireless Communications, 2007, 6(5): 1774-1786.

[1]	ZHOU Ya, XIE Zhuochen, LIU Peilong, LIU Huijie. Inter-satellite load balancing routing algorithm for LEO satellite constellation based on regional-traffic-detour [J]. Journal of University of Chinese Academy of Sciences, 2021, 38(5): 687-695.
[2]	WANG Jing, CHEN Lan, ZHANG He, WANG Haiyong. Multi-resource scheduling algorithm based on EDA simulation software [J]. Journal of University of Chinese Academy of Sciences, 2021, 38(5): 696-701.
[3]	JIN Yeqi, ZHENG Min, TAN Chong, LIU Hong. RB dynamic pre-allocation scheduling scheme for cellular Internet of Things [J]. , 2019, 36(6): 825-831.
[4]	TIAN Leixia, YANG Wenguo, GAO Suixiang, JIANG Zhipeng. Robust optimization models for study of wireless resource scheduling problem with uncertain transmission rate [J]. , 2018, 35(1): 18-25.
[5]	FANG Qiusheng, HONG Peilin. Batch routing in SDN networks with resource preference consideration [J]. , 2016, 33(4): 554-561.
[6]	YU Sheng, SHANG Dezhong, ZHOU Meng, ZHANG Baoxian. An adjustable local-flooding-based routing protocol for wireless sensor networks with mobile sink [J]. , 2015, 32(2): 273-280.
[7]	GUO Guanhua, JIAO Zhenzhen, ZHOU Meng, ZHANG Baoxian. A location-based multi-level-neighbor-assisted coding-aware routing protocol for wireless multi-hop networks [J]. , 2015, 32(1): 140-144.
[8]	DUAN Guojian, HAO Jie, YAO Zheng, ZHANG Baoxian. An adaptive-energy-threshold-based energy-efficient on-demand multicast routing protocol [J]. , 2014, 31(2): 276-283.
[9]	SUN Hao, CHEN Yong-Rui, XU Xu-Zhu, XU Ding-Xin, YI Wei-Dong. Underground parking information system based on wireless sensor network [J]. , 2013, 30(5): 664-670.
[10]	ZHANG Yong-Jiang, HAO Jie, LIU Yue, ZHANG Bao-Xian. A new routing method for duty-cycled wireless sensor networks [J]. , 2013, 30(2): 251-256.
[11]	ZHANG Jin-Zhu, HONG Pei-Lin, XUE Kai-Ping. Load adaptive CoMP scheduling strategies [J]. , 2012, 29(5): 644-651.
[12]	TIAN Jian-Jun, QIU Ling. UE power saving scheduling method using DRX for video streaming in LTE [J]. , 2012, 29(4): 518-523.
[13]	WANG Chao, CHEN Xiang-Lan, ZHOU Xue-Hai, WANG Ai-Li. Performance evaluation based on task division and scheduling in heterogeneous multi-core systems [J]. , 2012, (2): 257-263.
[14]	HE Wei-Qing, YANG Shou-Bao, TENG Da, HU Yun. Cooperation diversity-aware routing metric and cooperative routing protocol for 802.11s-based wireless Mesh networks [J]. , 2011, 28(4): 522-530.
[15]	SONG Hu, YANG Shou-Bao, LIU Xiao-Qian, GUO Liang-Min. A quality-driven algorithm for task scheduling in grid market [J]. , 2011, 28(1): 86-93.