考慮端點對端點流量公平性之無線網狀網路最佳化建置

Abstract

無線網狀網路(WMNs)為一項可提供寬頻存取網際網路的「最後一里(last mile) 」技術，能夠提供可靠且更加廣泛的服務給無線使用者。研究顯示，由於與出口閘道較遠的用戶能夠使用的頻寬較少，因此在建置無線網狀網路的同時如何兼顧網路效能與服務品質(QoS)是重要的議題。 本論文提出一個最大最小公平性(max-min fairness)的數學模型，在網路規劃階段考慮營運階段的端點對端點流量公平性問題(end-to-end throughput fairness)，並且聯合考慮網路節點佈署、出口閘道佈署、傳輸能量控制、信道佈署、路由規劃以及流量控制最佳化。本論文所提出的解決方案是基於拉格蘭日鬆弛法(Lagrangean Relaxation)為基礎所開發之啟發式演算法。 本論文提出前置處理方法(preprocessing)處理原先棘手的問題，並提出了適合多信道多網卡無線網狀網路(multi-channel multi-radio wireless mesh networks)的最大最小流量控制演算法(max-min flow control algorithm)。實驗結果顯示，以拉格蘭日對偶解(Lagrangean dual solution)為提示開發的啟發式演算法能夠有效地找到好的解。此外結果也顯示出，在本論文所設計的環境下，平均地將信道分配給使用者通訊(user communications)與骨幹通訊(backbone communications)能夠更有效地利用網路資源。

Wireless Mesh Networks (WMNs) are considered as a technology for last-mile broadband Internet access to provide reliable and more extensive connectivity to wireless users. Previous studies stated that users with longer paths must endure lower bandwidth allocation; as a result, performance and Quality of Service (QoS) are important factors in network planning stage. In this paper, a max-min fairness mathematical model is proposed, which jointly consider end-to-end throughput fairness problem with network deployment, transmission power control, channel assignment, routing and flow control optimization. The solution approach introduced in this paper is a heuristic algorithm derived from Lagrangean Relaxation based problem formulation. This thesis proposes a preprocessing stage for handling the originally intractable problem. A max-min flow control algorithm is established for multi-channel multi-radio wireless mesh networks. The experiment results show the heuristic algorithm, which takes dual solutions of Lagrangean Relaxation method as hints, can efficiently get a good solution. And the results also show that network designers can better use the resource through evenly allocate available channels to user communications and backbone communications.