無線網狀網路基於服務品質之最小成本路由演算法

A QoS-Based Minimum Cost Routing Algorithm for Wireless Mesh Networks

林書帆(Shu-Fan Lin)

指導教授 ： 蔡志宏

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201702638

摘要

為了滿足工業級使用者需要的特殊應用，無線網狀網路在運用時須考慮服務品質、無線通道擾動的適應，以及單一節點之可用無線通道數量上限等。在此環境中，常見之服務品質要求為統計式延遲目標，而非絕對延遲時間上限。本研究假設在此無線網狀網路中，導入802.11ac，搭配多天線收發，在5GHz頻段以20MHz通道頻寬進行無線傳輸。研究目的在於為此類網狀網路找到能滿足特定統計式服務品質延遲目標的最小成本路由和無線通道配置，可為許多8k和一般無線監控設備，提供良好的傳輸環境。
為了建置合乎統計式服務品質目標之無線網狀網路，並獲得最低成本路由，本論文設計一種可滿足特定服務品質之最小成本路由演算法(QMCRA)，也設計出一種U型效用函數以計算路由成本；而該效用函數由無線通道效用函數和延遲效用函數組成。對所有交通流可以用無線通道效用函數測試其不同無線通道配置，並計算其鏈路效用值。路由演算法則測試各種路徑組合、計算每個鏈路效用值，以及整體網路效用值，來獲得整體網路最低效用值及各鏈路最佳無線通道配置。最後步驟則經由檢查服務品質目標是否符合，以決定是否保留該路徑設計。
本研究利用佇列模擬軟體JMT (Java Modelling Tools)，在多種交通情境下，驗證了此演算法之效能，其所試算出的路徑，並與最短路徑之設計做比較。本研究結論是此設計方法不僅可滿足特定服務品質之延遲目標，也兼具負載平衡的優點。在可連接之無線通道數量內，能合理分配單一節點連接的無線通道總數。此外，本論文所提演算法還能適應交通流源頭的突爆和無線通道的擾動所造成之無線通道短暫阻塞，使交通流之延遲分佈滿足其統計式服務品質延遲目標。

關鍵字

無線網狀網路 ； 服務品質 ； 延遲目標 ； 突爆 ； 通道擾動

並列摘要

In order to satisfy specific requirement for industrial users in the wireless mesh networks (WMNs), one needs to consider QoS (Quality of Service), the channel fluctuation and limitation of available wireless channels on each node. Additionally, in the industrial environment, users frequently set up QoS in the form of stochastic delay objective, instead of deterministic delay. The purpose of this research is to obtain minimum cost routing and channel allocation under specific stochastic delay objectives satisfying the targeted QoS in WMNs. Our simulation WiFi environment assumed that 802.11ac supports MU-MIMO (Multi-user Multiple-Input and Multiple-Output) and employs 20MHz channel bandwidth on the 5GHz frequency band.

In order to construct stochastic QoS objective in WMNs and to calculate a minimum cost routing for traffic flows, we design an algorithm called QoS-Based Minimum Cost Routing Algorithm (QMCRA) for WMNs, and propose a U-shaped utility function for traffic routing. For all traffic flows, the U-shaped utility function can be used to test various wireless channel allocations while calculating links’ utility. Secondly, the routing algorithm can test various route arrangements by obtaining every links’ utility and the utility sum for the overall network. The routing solution and the best wireless channel allocation is then determined by the one leading to the minimum utility sum of the network. Finally, we check the QoS objectives to determine whether to employ the obtained routing design.

The proposed algorithm was evaluated under various scenarios of several traffic flows. We employed a queue simulator, JMT (Java Modelling Tools), to verify the performance of our design when it is compared with the shortest path approach. By simulation results, we observed that the main advantage of the proposed algorithm is that it satisfied the QoS requirement with less path cost than shortest path. The other advantages are predictability of traffic burstiness and channel fluctuation, load balancing and proper channel allocation on each link. In summary, our algorithm has achieved desirable outcomes: finding a minimum cost routing solution satisfying the desired delay QoS objective.

並列關鍵字

wireless mesh network ； QoS ； delay objective ； burstiness ； fluctuation

參考文獻

[1] Centralized Self-healing Routing Protocol (CSRP), http://www.chinaaet.com/article/3000011112

[2] I. F. Akyildiz and X. Wang, “A survey on wireless mesh networks,” IEEE Communications magazine 43.9 (2005): S23-S30.

[3] D. Benyamina, A. Hafid, and M. Gendreau, “Wireless mesh networks design—A survey,” IEEE Communications surveys & tutorials 14.2 (2012): 299-310.

[4] Y. Yang, J. Wang, and R. Kravets, “Designing routing metrics for mesh networks,” IEEE Workshop on Wireless Mesh Networks (WiMesh). 2005.

[5] W. Shen and Q. A. Zeng, “Cost-function-based network selection strategy in integrated wireless and mobile networks,” IEEE Transactions on Vehicular Technology 57.6 (2008): 3778-3788.