基於配置頻寬、流量控制與路由決策達成無線網狀網路端點至端點延遲及吞吐量之公平性

無線網狀網路被視為提供客戶寬頻接入至網際網路之“最後一哩”的方式之一。隨著閘道器與無線路由器的功能日漸增強，所服務的區域也隨之擴增。公平性一直是網路研究者所重視的研究議題之一。然而，以現有的頻寬分配法則及流量控管機制，並無法達成公平性目標。因此，本研究之目標為藉由流量控制機制及頻寬分配來達成兼顧各用戶延遲及吞吐量之公平性，更進一步結合路由決策使系統吞吐量最大化。本論文採用數學模型來完整描述問題，再試圖以最佳化為基礎的演算法解決該混合整數非線性數學規劃問題。由於必須同時處理若干決策變數，同時效能均符合一定服務品質，在解題過程中，首先採用兩階段經驗法則，計算出具有公平性之頻寬分配基準，其目的為保證端點至端點吞吐量及端點至端點延遲公平性。再引用拉格蘭日鬆弛法及次梯度法為基礎逐步調整決策變數以逼近最佳值。最後藉由電腦實驗結果證明所提出的解決方案之優異性。

關鍵字

無線網狀網路；流量控制；頻寬分配；路由決策；服務品質；端點至端點公平性；最佳化；拉格蘭日鬆弛法

並列摘要

Wireless mesh networks provide connectivity to communities and act as a solution for last-mile broadband Internet access. By improvements of routers and gateways, service region expands much broader than before. Fairness, which is an important issue since Internet has been researched, is our objective subject to the capacity of equipments. The hop count from client to gateway influences the performance. A more hop count may experience lower quality of service (QoS) and even starvation. In this thesis, we focus on capacity allocation, flow control and routing to achieve end-to-end fairness. This end-to-end fairness problem is formulated as a mathematical programming model and then deal with by an optimization-based algorithm. In this thesis, two important performance metrics, end-to-end delay and throughput are discussed. Several decision variables need to be determined where a certain level of QoS requirements is satisfied. We purpose a two-phased heuristic to ensure end-to-end delay and throughput fairness. To solve this problem, the Lagrangean Relaxation method is introduced to decompose the primal problem into several subproblems and we also adopt the subgradient method to obtain a reasonable lower bound. Further, we show the efficiency and effectiveness of the purposed algorithm by computational experiments.

並列關鍵字

Flow control ； Capacity Allocation ； Routing ； End-to-end Fairness ； Mathematical Programming ； Optimization ； Lagrangean Relaxation

參考文獻

[1]. F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks: A Survey,” Computer Networks, Vol. 47, No.4, pp. 445-487, March 2005.

[2]. V. Gambiroza, B. Sadeghi, and E. Knightly, “End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks,” Proc. MobiCom ’04, pp. 287–301, October, 2004.

[3]. N. Ben Salem and J.P. Hubaux, “A Fair Scheduling for Wireless Mesh Networks,” Proc. IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005.

[5]. T. Bonald, L. Massoulie, A. Proutiere and J. Virtamo, “A Queueing Analysis of Max-Min Fairness, Proportional Fairness and Balanced Fairness,” Queueing Systems: Theory and Applications, pp. 65–84, 2006.

[6]. T. Bonald and A. Prouti`ere, “On performance bounds for balanced fairness,” Performance Evaluation 55, pp. 25–50, 2004.

國際替代計量

基於配置頻寬、流量控制與路由決策達成無線網狀網路端點至端點延遲及吞吐量之公平性

全文下載

主題瀏覽