多信道無線網狀網路下近似最佳化之分散式具服務品質路由演算法

A Near-Optimail Distributed QoS Constrained Routing Algorithm for Multichannel Wireless Mesh Networks

謝友仁(Yu-Jen Hsieh)

指導教授 ： 林永松

共同指導教授 ： 顏宏旭

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2009年)

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

摘要

無線網狀網路可視為一個用來提供寬頻存取網際網路之「最後一哩」技術的解決之道。於無線網狀網路中採用多個信道來傳輸，已經被證實是一種用來克服容量因干擾而降低之問題的有效方法。對於每個使用者而言，希望選擇低干擾且傳輸延遲最低的路徑去存取網際網路；然而，這對整個系統而言並不是最佳化的結果。
　　在這篇論文中，我們提供了一個簡單的信道分配演算法，不但容易實施而且使得每個節點能有局部的最大化平行傳輸。我們也提供一個分散式具有服務品質限制的路由演算法，將系統觀點與使用者觀點都納入考量；為了達到這個目標，我們定義一個路由衡量標準，這個路由衡量標準是由鏈結平均傳輸延遲與佇列長度之導數兩者所組成，並且由拉格蘭日鬆弛法為基礎的問題公式所推導出來。
　　我們使用鏈路狀態路由協定來作動態路由，並且提供多條最短路徑與多條最快路徑給每一個起終點配對，使這個演算法能藉由流量控制啟發式演算法而適用於更多情況之下。最後，我們透過模擬來評估近似最佳化之分散式具服務品質限制路由演算法。模擬結果顯示我們的演算法在較大的網路下於平均端對端傳輸延遲、延遲時間變化與符合服務品質限制之系統吞吐量上優於其他演算法。

關鍵字

無線網狀網路 ； 分散式路由演算法 ； 鏈結狀態路由協定 ； 服務品質限制路由演算法 ； 拉格蘭日鬆弛法

並列摘要

Wireless mesh networks (WMNs) are considered as a solution to providing last-mile broadband Internet access. Employing multiple channels into WMN is shown to be an efficient way to conquer the degradation of capacity due to the interferences. For each user, it is desirable to choose the route with low interference and minimum delay to access the Internet; however, this is suboptimal for the whole system.
　　In this thesis, we propose a simple channel assignment heuristic algorithm which is easy for implementation and makes each node have locally maximal parallel transmission. We also propose a distributed QoS (Quality-of-Service) constrained routing algorithm which takes “system perspective” and “user perspective” into consideration; to achieve the goal, we define a routing metric which is composed of link mean delay and the derivative of queue length, and is derived from a Lagrangean Relaxation based problem formulation.
　　We use link-state routing protocol for distributed routing and provide both K shortest paths and K fastest paths for each Origin-Destination pair, so that, this algorithm can be suitable for much more scenarios by the admission control heuristic algorithm we proposed. Finally, we evaluate the performance of Near-Optimal Distributed QoS Constrained (NODQC) routing algorithm via simulations. The simulation results show that our routing algorithm outperforms others in terms of average end-to-end delay, delay jitter and system throughput with QoS satisfaction in large-scale networks.

並列關鍵字

Wireless Mesh Networks ； Distributed Routing Algorithm ； Link-State Routing Protocol ； QoS Constrained Routing Algorithm ； Lagrangean Relaxation

參考文獻

[1] T. Liu and W. Liao, “On Routing in Multichannel Wireless Mesh Networks: Challenges and Solutions,” IEEE Network, Vol. 22, NO. 1, pp. 13-18, January/February 2008.

[2] L. Badia, A. Erta, L. Lenzini, and M. Zorzi, “A General Interference-Aware Framework for Joint Routing and Link Scheduling in Wireless Mesh Networks,” IEEE Network, Vol. 22, NO. 1, pp. 32-38, January/February 2008.

[3] A. Raniwala, K. Gopalan, and T.-C. Chiueh, "Centralized Channel Assignment and Routing Algorithms for Multi-channel Wireless Mesh Networks," ACM Mobile Computing and Communications Review (MC2R), Vol. 8, NO. 2, pp. 50–65, April 2004.

[4] P. Kyasanur and N. H. Vaidya, “Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks,” Proc. IEEE WCNC, Vol. 4, pp. 2051- 2056, 2005.

[5] A.P. Subramanian, H. Gupta, S.R. Das, “Minimum Interference Channel Assignment in Multi-Radio Wireless Mesh Networks,” Proc. IEEE SECON, pp. 481-490, 2007.