利用多重傳輸速率增進無線網狀網路之效能

Exploiting Multiple Rates to Maximize the Throughput of Wireless Mesh Networks

林靖茹(Ching-Ju Lin)

指導教授 ： 周承復

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/博士(2009年)

https://doi.org/10.6342/NTU.2009.02966

摘要

多重網卡多重頻帶無線網狀網路(Multi-Radio Multi-Channel Wireless Mesh Networks)的架構設計提供普及的寬頻無線存取務。近年來，如何有效的分配網狀網路之頻寬資源，利用多重網卡及多重頻帶來增進網路效能，已受到諸多的關注。在多重頻帶網狀網路中，路由和頻帶分配交互影響並決定網狀網路之頻寬容量(network capacity)。目前已有文獻指出同時解決路由和頻帶分配問題(joint routing and channel assignment, i.e., JRC)，可以使網狀網路達到較高的頻寬效能。雖然已經有非常多學術論文致力於解決網狀網路中之路由與頻帶分配問題(JRC problem)，但其中大多數都忽略了網路中多重傳輸速率之特性，亦或假設無線鏈結僅使用基礎速(basic rate)傳送資料。然而，在多重傳輸速率網路中，當使用高傳輸速率之鏈結與使用低傳輸速率之鏈結共享相同頻帶時，由於多重速率分享問題(multi-rate sharing problem)，使用高傳輸速率之鏈結可能無法獲得相當的平均吞吐量。

為了解決多重速率分享問題，我們首先提出一套量化的公式以估計無線鏈結之動態頻寬容量(dynamic link capacity)。此外，此估計公式可以有效的指出多重速率分享問題的嚴重性，幫助網狀網路配置適當的頻帶分配方式，以減輕多重速率網路中之多重速率分享問題。

本論文的第二部分旨在提出一套最佳化資源分配模型(multi-rate JRC model)，藉由估計每個無線鏈結之動態頻寬容量，網狀網路能夠找到最佳的路由及頻帶配置以最大化總體網路吞吐量。我們更將此最佳化問題轉換成Lagrangian對偶問題(Lagrangian dual problem)，並基於梯度演算法(subgradient-based algorithm)來解決此對偶問題。由於每個對偶問題中的子問題(Lagrangian sub-problem)仍是非線性之問題(non-linear problem)，我們更推導出一套演算法使其能在有效時間內(polynomial-time)解決對偶子問題，以逼近資源分配之最佳解。我們藉由實驗來驗證所提估計公式之準確性，並使用電腦模擬來驗證最佳化資源分配模型之效能。結果顯示估計出的動態頻寬容量能真實的反應出網路中的多重速率共享問題。此外，模擬結果也顯示多重速率資源分配模型(multi-rate JRC model)能有效解決單一速率分配模型(base-rate JRC model)所產生的缺點，並提升整體網路之效能。

關鍵字

無線網狀網路 ； 路由與頻帶分配 ； 多重傳輸速率 ； 多重網卡多重頻帶網路

並列摘要

Multi-radio Multi-channel wireless mesh networks (WMNs) aim to perform ubiquitous wireless broadband network access. In WMNs, much attention has been paid to the problem of resource allocation, i.e. how to efficiently utilize
multiple orthogonal channels and multiple communication radios to enhance the aggregate throughput. In multi-channel wireless mesh networks (WMNs), the routing and channel assignment can interdependently determine network capacity. Some literatures show that a multi-channel, multi-radio WMN can achieve higher aggregate throughput if it can solve the routing and channel assignment problems jointly. However, current works on the joint routing and channel assignment (JRC) problem in wireless mesh networks (WMNs) assume that all links operate at the base rate. In other words, they do not consider the presence of multiple bit-rates. However, in multi-rate WMNs, the achievable throughput of a link operating at higher rates could be much less than its bit-rate when it has to contend with low-rate links. This is also known as the multi-rate sharing problem. To address the problem, we first present a numerical formulation for estimating the dynamic link capacity, which can indicate the degree of the multi-rate sharing problem. Next, we propose an optimization model called Multi-Rate JRC, which solves the JRC problem by considering the dynamic link capacity in order to maximize the throughput in multi-rate, multi-radio, multi-channel WMNs. We then reformulate the primal problem as a Lagrangian dual problem, and apply the subgradient method to approach the dual. Finally, since each subproblem in the dual problem is also a non-linear problem, we design a polynomial-time algorithm to solve it. Our experiment results demonstrate that the proposed capacity formulation can approximate the actual link throughput. We compare the multi-rate JRC model with the base-rate JRC model via simulations. The results show that the multi-rate JRC model achieves throughput gains of 3-4 times and recover from network failure efficiently.

並列關鍵字

Wireless Mesh Networks ； Routing and Channel Assignment ； Multiple Bit-Rates ； Multi-Radio Multi-Channel

參考文獻

[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, February 1993.

[3] I. Akyildiz and X. Wang. A Survey on Wireless Mesh Networks. Communications Magazine, IEEE, 43(9):S23–S30, Sept. 2005.

[4] I. F. Akyildiz, X.Wang, andW.Wang. Wireless Mesh Networks: A Survey. Computer Networks, 47(4):445–487, 2005.

[5] M. Alicherry, R. Bhatia, and L. E. Li. Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks. In MobiCom’05: Proceedings of the 11th annual international conference on Mobile computing and networking, 2005.

[7] J. Bicket. Bit-Rate Selection in Wireless Networks. PhD thesis, Massachusetts Institute of Technology, 2005.