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

Abstract

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

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.