於多重速率無線群播網路下同時考慮路由與容量分配以達成群內暨群間延遲公平之演算法

Joint Routing and Capacity Assignment Algorithms to Achieve Inter- and Intra-group Delay Fairness in Multi-rate Multicast Wireless Networks

林世昌(Shih-Chang Lin)

指導教授 ： 林永松

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

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

摘要

在無線網路中，存在著單一資料來源端傳送資料給多個接收端的多媒體應用，如視訊會議、遠距教學等，而群播樹的結構可適用於這樣的網路拓樸。當網路上的使用人數激增時，在群播時分配有限的無線網路資源，以及提供網路服務品質，例如端點至端點延遲的公平性，就變的相當重要。更進一步的思考，在無線群播網路下，同時考慮路由與容量分配以達成群內暨群間延遲公平性的議題需要被更廣泛討論。
　　在本論文中，我們提出一套演算法用來建構一個群播網路，目的在於令每一個使用者的端點至端點延遲具有公平性。因此，我們將問題關注在無線群播網路上，同時考量對每一條路徑的鏈結容量分配，以及提供具有群內端點至端點延遲公平性、群間延遲公平性的路由。我們將此路由與容量分配問題使用數學規劃法正確描述，在於達到上述研究目標。採用拉格蘭日鬆弛法和次梯度法為基礎，藉由調整與利用拉格蘭日乘數，設計出啟發式演算法，進而逐步改善可行解之品質。最後藉由電腦實驗結果顯示本論文所提出之解決方案具有較佳的可行解。

關鍵字

無線網路 ； 群播 ； 端點對端點公平性 ； 服務品質 ； 拉格蘭日鬆弛法 ； 最佳化

並列摘要

In network applications, such as video-conferencing and e-learning, a sender might transmit data to multiple receivers. Multicasting is suitable for the kind of network applications, especially in resource-constrained wireless networks. However, as the popularity of wireless users grows up, the consequence of allocating limited resources to ensure Quality of Service, for instance, end-to-end latency constraints of transmission, becomes crucial in a multicast wireless network. So, the issue of joint routing and capacity assignment algorithms to achieve intra- and inter-group end-to-end delay fairness should also be discussed further.
In this thesis, an approach is proposed to construct a wireless multicast network to accommodate delay fairness for each user. This approach focuses on the problem of jointly considering link capacity assignment for each multicast group, and the multicast routing in intra-group end-to-end delay fairness and inter-group delay fairness. The problem is formulated to a mathematical programming problem, in which the objective is to minimize the inter-group delay among all multicast groups, thus achieving perfectly fairness. Based on Lagrangean Relaxation method and subgradient optimization technique, the Lagrangean multipliers can be adjusted and used to develop a heuristic algorithm to improve the quality of the solution. According to computational experiments, our proposed algorithm is more efficient than a compared simple algorithm.

並列關鍵字

Wireless Networks ； Multicast ； End-to-End Fairness ； Quality of Service ； Lagrangean Relaxation Method ； Optimization

參考文獻

[1] C. A. S. Oliveira and P. M. Pardalos, “A Survey of Combinatorial Optimization Problems in Multicast Routing”, Computers and Operations Research, Vol. 32, Issue 8, pp. 1953-1982, August 2005.

[3] S. Chen and K. Nahrstedt, “An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions”, IEEE Network, Vol. 12, No. 6, pp. 64-79, November/December 1998.

[5] X. Yuan, “Heuristic Algorithms for Multi-constrained Quality-of-Service Routing”, IEEE/ACM Transactions on Networking, Vol. 10, Issue 2, April 2002.

[8] X. Masip-Bruin et al., “Research Challenges in QoS Routing”, Computer Communication, Vol. 29, Issue 5, pp. 562-581, March 2006.

[10] P. Khadivi, S. Samavi, T.D. Todd and H. Saidi, “Multi-constraint QoS Routing Using a New Single Mixed Metrics”, IEEE ICC’04, Vol. 4, pp. 2042-2046, June 2004.