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

移動式隨意網路由許多自主移動的節點所組成，節點之間以無線媒介通訊。此網路架構不需仰賴已存的基礎建設，而網路拓樸會隨著節點的移動而持續變化。另一項重要的特性即為節點的電力資源有限，能量耗損會影響網路壽命長短，因此成為一項重要的效能衡量指標。 群播為移動式隨意網路中許多應用的基本運作機制，這些應用大部份都強調資訊傳輸的延遲限制，因此需要一個低延遲的群播演算法來滿足其限制，然而在設計的過程中同時考慮上述議題包括低能耗和節點移動性，會使問題變得十分複雜。 本論文主要研究在移動式隨意網路中多群組進行群播時，如何進行路由以及節點傳輸時間的排程問題。我們將此問題設計成一個數學模型，目標為最小化群播的延遲時間，同時我們也將群播產生之能耗限制在某個合理的範圍並且避免傳輸時會產生的資料碰撞，此碰撞情形會造成能量消耗。最後我們提出以拉格蘭日鬆弛法為基礎的演算法來解決此問題。我們設計一系列的實驗以測試演算法的表現，實驗結果顯示此演算法在多種網路情境下均能提供低延遲以及節能的傳輸排程。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. n 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.n 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.謝詞 I文摘要 IIIHESIS ABSTRACT VABLE OF CONTENT VIIIST OF TABLES IXIST OF FIGURES XIHAPTER 1 INTRODUCTION 1.1 BACKGROUND 1.2 MOTIVATION 4.3 LITERATURE SURVEY 6.3.1 Multicasting in Ad Hoc Networks 6.3.2 Scheduling of Broadcasting 11.3.3 Mobility Model 14.4 PROPOSED APPROACH 19.5 THESIS ORGANIZATION 19HAPTER 2 PROBLEM FORMULATION 21.1 PROBLEM DESCRIPTION 21.2 PROBLEM NOTATION 31HAPTER 3 SOLUTION APPROACH 43.1 INTRODUCTION TO LAGRANGEAN RELAXATION METHOD 43.2 LAGRANGEAN RELAXATION 46.2.1 Subproblem 1 49.2.2 Subproblem 2 49.2.3 Subproblem 3 51.2.4 Subproblem 4 52.2.5 Subproblem 5 53.2.6 Subproblem 6 54.2.7 Subproblem 7 54.2.8 Subproblem 8 57.3 THE DUAL PROBLEM AND THE SUBGRADIENT METHOD 58HAPTER 4 GETTING PRIMAL FEASIBLE SOLUTION 59.1 HEURISTIC FOR ROUTING POLICY 60.2 HEURISTIC FOR CALCULATING MAXIMAL TRANSMISSION TIME 61.3 HEURISTIC FOR SCHEDULING POLICY 64.4 HEURISTIC FOR SAVING ENERGY CONSUMPTION 66.5 LAGRANGEAN RELAXATION BASED ALGORITHM 67HAPTER 5 COMPUTATIONAL EXPERIMENTS 69.1 EXPERIMENT ENVIRONMENT 69.2 SIMPLE ALGORITHM FOR COMPARISON AND PERFORMANCE METRICS 70.3 EXPERIMENT SCENARIO 71.3.1 Static Network with Different Number of Nodes 71.3.2 Static Network with Different Number of Source Nodes 74.3.3 Dynamic Network with Different Density of Destination Nodes 75.3.4 Static Network with Different Transmission Radius 78.3.5 Dynamic Network with Different Transmission Radius 81.3.6 Summary 83.4 IMPLEMENTATION IN LONG-TERM OPERATION 84.4.1 A Scenario of Constant Speed during a Phase 87.4.2 A Scenario of Variable Speed during a Phase 98HAPTER 6 CONCLUSION 113.1 SUMMARY 113.2 FUTURE WORK 114EFERENCES 11