移動式隨意網路下多群組群播之 低延遲與能耗排程演算法

A Low-latency and Energy-efficient Scheduling Algorithm for Multi-group Multicasting in Mobile Ad Hoc Networks

李培維(Pei-Wei Li)

指導教授 ： 林永松

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

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

摘要

移動式隨意網路由許多自主移動的節點所組成，節點之間以無線媒介通訊。此網路架構不需仰賴已存的基礎建設，而網路拓樸會隨著節點的移動而持續變化。另一項重要的特性即為節點的電力資源有限，能量耗損會影響網路壽命長短，因此成為一項重要的效能衡量指標。

　　群播為移動式隨意網路中許多應用的基本運作機制，這些應用大部份都強調資訊傳輸的延遲限制，因此需要一個低延遲的群播演算法來滿足其限制，然而在設計的過程中同時考慮上述議題包括低能耗和節點移動性，會使問題變得十分複雜。

　　本論文主要研究在移動式隨意網路中多群組進行群播時，如何進行路由以及節點傳輸時間的排程問題。我們將此問題設計成一個數學模型，目標為最小化群播的延遲時間，同時我們也將群播產生之能耗限制在某個合理的範圍並且避免傳輸時會產生的資料碰撞，此碰撞情形會造成能量消耗。最後我們提出以拉格蘭日鬆弛法為基礎的演算法來解決此問題。我們設計一系列的實驗以測試演算法的表現，實驗結果顯示此演算法在多種網路情境下均能提供低延遲以及節能的傳輸排程。

關鍵字

移動式隨意網路 ； 排程 ； 群播 ； 高效率節能 ； 低延遲 ； 移動性 ； 拉格蘭日鬆弛法

並列摘要

A Mobile Ad Hoc Network (MANET) consists of a set of mobile nodes which communicate over the wireless medium. The network topology, which does not relay on any pre-existing infrastructure, changes rapidly due to the mobility of nodes. Another property of such networks is that the battery capability of nodes is limited. As a result, energy-efficiency becomes an important performance measure since it directly affects the network lifetime.
In MANET, multicasting is a fundamental operation to a wide range of applications which impose end-to-end latency constraints of transmissions. Designing a low-latency multicast protocol which satisfies these constraints is crucial important. However, it becomes a challenging task while addressing the critical issues of energy-efficiency and mobility at the same time.
In this thesis, we focus on the problem of routing and scheduling the transmission time of nodes for multi-group multicasting in MANET. We formulate the problem as a linear integer programming problem, in which the objective is to minimize the latency of multicasting. In addition, the formulation ensures the energy consumption within a reasonable range and avoids possible collisions of transmission which consume a large amount of valuable energy resources. A set of heuristic algorithms based on Lagrangean relaxation method is proposed to solve this problem. We conduct a series of experiment designed from the perspective of design and operation both. Experimental studies indicate that our algorithm has good performance and high practicability under various network conditions.

並列關鍵字

MANET ； Multicast ； Scheduling ； Energy-Efficient ； low-latency ； Mobility ； Lagrangean Relaxation Method

參考文獻

[1] L. Chan and W. Heinzelman, “A Survey of Routing Protocols that Support QoS in Mobile Ad Hoc Networks,” IEEE Network, Vol. 21, No. 6, pp. 30-38, November-December 2007.

[2] C. T. Chou, J. Qadir, and J. G. Lim, “Advances and Challenges with Data broadcasting in Wireless Mesh Networks,” IEEE Communication Magazine, Vol. 45, No. 11, pp. 78-85, November 2007.

[5] J. E. Wieselthier, G.-D. Nguyen, and A. Ephremides, “Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Mobile Network and Applications, Vol. 7, No. 6, pp. 481-492, December 2002.

[6] N. Rahnavard, B. N. Vellambi, F. Fekri, “Distributed Protocols for Finding Low-Cost Broadcast and Multicast Trees in Wireless Networks,” Proc. IEEE SECON’08, pp. 551-559, June 2008.

[7] H. Liu, X. Jia, P.-J. Wan, X. Liu, and F. F. Yao, “A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 18, No. 5, pp. 658-671, May 2007.