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