Please wait a minute...
浙江大学学报(工学版)
J4  2009, Vol. 43 Issue (8): 1406-1411    DOI: 10.3785/j.issn.1008-973X.2009.
电子、通信与自动控制技术     
无线Mesh网络中功率控制、信道分配和调度的联合优化
陈勋,张朝阳,罗海燕
(浙江大学 信息与通信工程研究所, 浙江 杭州 310027)
Joint optimization of power control, channel assignment and scheduling in wireless mesh network
 CHEN Xun, ZHANG Chao-Yang, LUO Hai-Yan
Institute of Information and Communication Engineering, Zhejiang University, Hangzhou 310027, China
 全文: PDF(900 KB)  
摘要：

研究规则的多接口多信道无线Mesh网络吞吐量最优化问题,目的是在给定网络拓扑结构和流量需求的情况下,联合考虑功率控制、信道分配和调度,求出公平性约束下的最大吞吐量.采用图论的方法,目标优化问题可以被分解为有限个子问题,而每个子问题可以表示成一个线性规划问题,分别求解这些子问题从而得到目标问题的解,并从理论上证明了该解的全局最优性.该算法需要遍历所有可行的场景,具有O(2n)的计算复杂度.同时提出了一种次优算法,以很小的性能下降为代价获得了O(n)的计算复杂度.仿真实验结果显示,在9个节点的网络中,次优算法得到的网络吞吐量与最优算法相比下降不超过8％,而计算速度有显著提高.
关键词： 无线Mesh网络;  功率控制;  信道分配;  调度;  联合优化    
Abstract:

The optimization problem of maximizing the throughput of a regular multi-radio, multi-channel wireless mesh network was addressed. Given certain network topology and traffic demands, by jointly considering the power control, channel assignment and scheduling, this work studied how to maximize the network throughput under fairness constraint. Based on graph theory, the problem was divided into several sub-problems, which could be formulated as linear programming. It was proved that the solutions of these sub-problems will lead to the global optimal solution. However, the computational complexity of the above algorithm was O(2n) as it needed to traverse all possible scenarios. A suboptimal algorithm was proposed to achieve a complexity of O(n) at the cost of moderate performance degradation. Simulation showed that the suboptimal algorithm solved the problem much faster, while the performance degradation was less than 8%, in comparison with the optimal one.
Key words: wireless mesh network    power control    channel assignment    scheduling    joint optimization
出版日期: 2009-09-01
:  TN 929.5  
基金资助:

国家自然科学基金资助项目（60572115）；国家“863”高技术研究发展计划资助项目（2007AA01Z257）；浙江省自然科学基金重点资助项目（Z104252）
通讯作者: 张朝阳，男，教授，博导.     E-mail: ning_ming@zju.edu.cn
作者简介: 陈勋（1984-），男，福建福州人，硕士生，从事无线Mesh网络与WiMAX通信系统研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
陈勋
张朝阳
罗海燕

引用本文:

陈勋, 张朝阳, 罗海燕. 无线Mesh网络中功率控制、信道分配和调度的联合优化[J]. J4, 2009, 43(8): 1406-1411.

CHEN Xun, ZHANG Chao-Yang, LUO Hai-Yan. Joint optimization of power control, channel assignment and scheduling in wireless mesh network. J4, 2009, 43(8): 1406-1411.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2009.    或    http://www.zjujournals.com/xueshu/eng/CN/Y2009/V43/I8/1406

[1] FACCIN S M, WIJTING C, KENCKT J, et al. Mesh WLAN networks: concept and system design [J]. IEEE Journal of Wireless Communications, 2006, 13(2): 10-17.
[2] GUPTA P, KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory, 2000, 46(2): 388-404.
[3] TOUMPIS S, GOLDSMITH A J. Capacity regions for wireless Ad hoc networks [J]. IEEE Transactions on Wireless Communications, 2003, 2(4): 736-748.
[4] JANGEUN J, SICHITIU M L. The nominal capacity of wireless mesh networks [J]. IEEE Journal of Wireless Communications, 2003, 10(5): 814.
[5] AOUN B, BOUTABA R. Max-Min fair capacity of wireless mesh networks [C]∥ IEEE International Conference of the Mobile Ad-hoc and Sensor Systems (MASS). Vancouver: IEEE, 2006: 21-30.
[6] BURKHART M, WATTENHOFER R, ZOLLINGER A. Does topology control reduce interference [C]∥ Proceedings of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing. Tokyo: ACM, 2004: 9-19.
[7] BEHZAD A, RUBIN I. Impact of power control on the performance of Ad hoc wireless networks [C]∥ 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami: IEEE, 2005: 102-113.
[8] IVAN W H, SOUNG C L. Impact of power control on performance of IEEE 802.11 wireless networks [J]. IEEE Transactions on Mobile Computing, 2007, 6(11): 1245-1258.
[9] KULKARNI G, RAGHUNATHAN V, SRIVASTAVA M. Joint end-to-end scheduling, power control and rate control in multi-hop wireless networks [C]∥ IEEE Conference of Global Telecommunications. Dallas: IEEE, 2004, 5: 3357-3362.
[10] CHEN L, ZHANG Q, LI M, et al. Joint topology control and routing in IEEE 802.11-based multi-interface multi-channel mesh networks [J]. IEEE Transactions on Vehicular Technology, 2007, 56(5): 3123-3136.
[11] WU H, YANG F, TAN K, et al. Distributed channel assignment and routing in multi-interface multi-channel multi-hop wireless networks [J]. IEEE Journal of Selected Areas in Communications, 2006, 24(11): 19721-983.
[12] RANIWAL A, GOPALAN K, CHIUEH T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks [J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2004, 8(2): 50-65.
[13] WANG W, LIU X. A framework for maximum capacity in multi-channel multi-interface wireless networks [C]∥ IEEE 3rd Conference of Consumer Communications and Networking. Las Vegas: IEEE, 2006: 720-724.
[14] SUNDARESAN K, SIVAKUMAR R. A unified MAC layer framework for Ad-hoc networks with smart antennas [J]. IEEE/ACM Transactions on Networking, 2007, 15(3): 546-559.
[15] YEE J, HOSSAIN P E. Understanding wireless LAN performance trade-offs [J]. Journal of Communication Systems Design, 2000: 32-35. http:∥ www.commsdesign.com/showArticle.jhtml？articleID=16505827.
[16] KARMARKAR N. New polynomial-time algorithm for linear programming [J]. Journal of Combinatorica, 1984, 4(4): 373-395.
[1] 周健, 石德晓. 基于中断应急的集成弹性供应链网络[J]. 浙江大学学报(工学版), 2018, 52(2): 240-246.
[2] 陆源源, 王慧, 宋春跃. 考虑列车混行的运行调度一体化优化方法[J]. 浙江大学学报(工学版), 2018, 52(1): 106-116.
[3] 李建丽, 丁丁, 李涛. 基于二次聚类的多目标混合云任务调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1233-1241.
[4] 袁友伟, 余佳, 郑宏升, 王娇娇. 基于新颖性排名和多服务质量的云工作流调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1190-1196.
[5] 任逸飞, 陆志强, 刘欣仪, 张猛. 考虑技能水平的多技能资源约束项目调度[J]. 浙江大学学报(工学版), 2017, 51(5): 1000-1006.
[6] 张心怡, 杨家强, 张晓军. 基于机会约束的含多风电场动态经济调度[J]. 浙江大学学报(工学版), 2017, 51(5): 976-983.
[7] 王越, 苏宏业, 邵寒山, 卢山,谢磊. 需求与公用工程不确定的生产计划与调度集成[J]. 浙江大学学报(工学版), 2017, 51(1): 57-67.
[8] 周炳海, 赵猛. 柔性Job Shops集成调度启发式算法[J]. 浙江大学学报(工学版), 2016, 50(6): 1073-1079.
[9] 梅天华, 甘德强. 基于调度“三公”的浙江电力调峰交易市场模型[J]. 浙江大学学报(工学版), 2016, 50(2): 369-376.
[10] 郭映彤,王贺,冯翰信,潘尔顺. 成组条件下的研制批产混合调度方法[J]. 浙江大学学报(工学版), 2016, 50(11): 2224-2230.
[11] 王青, 温李庆, 李江雄, 柯映林, 李涛, 张世炯. 基于Petri网的飞机总装配生产线建模及优化方法[J]. 浙江大学学报(工学版), 2015, 49(7): 1224-1231.
[12] 苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[13] 张新艳,周健,林婷. B2C电商环境下集中式退货中心的车辆调度[J]. 浙江大学学报(工学版), 2015, 49(3): 598-604.
[14] 王成龙,李诚,冯毅萍,荣冈. 作业车间调度规则的挖掘方法研究[J]. 浙江大学学报(工学版), 2015, 49(3): 421-429.
[15] 马腾, 赵兴忠, 高博青, 吴慧. 自由曲面形状和拓扑联合优化研究[J]. 浙江大学学报(工学版), 2015, 49(10): 1946-1951.