收稿日期: 2009-12-02
修回日期: 2010-02-20
网络出版日期: 2010-07-15
基金资助
国家重点基础研究973计划(2007CB310602)资助
Approximate algorithm for joint routing and scheduling in wireless relay networks
Received date: 2009-12-02
Revised date: 2010-02-20
Online published: 2010-07-15
孙绍峰 , 卫国 . 无线中继网络的联合路由与调度的近似最优算法[J]. 中国科学院大学学报, 2010 , 27(4) : 530 -537 . DOI: 10.7523/j.issn.2095-6134.2010.4.015
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
[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.
/
| 〈 |
|
〉 |
