林永松臺灣大學：資訊管理學研究所傅琳智Fu, Lin-ChihLin-ChihFu2007-11-262018-06-292007-11-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/54358　　移動性的Ad Hoc網路使用無線傳播，是一個不需事先決定網路拓樸設計的網路。這種網路架構的特性使得它可以被快速的部署，並且不需依賴已存的基礎建設。值得注意的是在這顯著的特徵下，它適合使用在設計階段無法預測的網路架構的應用。 　　然而，在設計移動性的Ad Hoc網路存在很多關鍵的挑戰需要被解決。其中三個主要的挑戰是: 1) 缺乏集中式管理, 2) 節點的自主移動, 3) 所有通訊透過無線媒介傳播。 　　本篇論文我們著重在探討當每個節點受限於有限的電力資源，且整個路由的路徑是由每個自主移動的節點所組成的情況下，要如何以低能耗的路由決策，成功傳送資料給群播成員，在會因為節點移動而導致傳輸中斷，而需要重新作路由決策的網路拓樸。 　　不同於傳統設計的單層結構，我們同時考慮在有效的傳送半徑範圍內（網路連接性，屬實體層）以及群播樹的建立（路由功能，屬網路層），來做出低能耗的路由決策。我們將此問題設計成最佳化的數學模型，並且採用拉格蘭日鬆弛法（Lagrangian relaxation）為基礎的方法來處理此複雜的問題。The Mobile Ad Hoc Network (MANET) is an emerging network topology based on a radio propagation model. The network topology, which is neither fixed nor predetermined, can be rapidly deployed and does not need to rely on a pre-existing infrastructure. It is noteworthy that this salient feature makes it suitable for the network operations that, by their nature, are unpredictable during the design stage. However, a lot of critical challenges in the design and operation of MANET need to be solved. The three main challenges come from: 1) the lack of a centralized entity, 2) the possibility of platform movements, 3) the fact that all the communication is carried over the wireless medium. The issues we address here are 1) a node operates on limited battery resources, and 2) multi-hop routing paths are used over constantly changing network environments due to node mobility. Hence, efficient utilization of routing packets and immediate recovery of route breaks are critical in routing and multicasting protocols in MANET. Our approach to energy-efficient communication departs from the traditional layered structure in that we jointly address the issues of transmitted power levels (a network connectivity function, related to the Physical layer) and multicast tree formulation (a routing function, associated with the Network layer). We model the problem as a linear integer mathematical programming problem. In addition, we propose a set of heuristic solution procedures based on Lagrangian relaxation methods to solve the complicated problem.謝詞 III 論文摘要 IV THESIS ABSTRACT V TABLE OF CONTENTS VII LIST OF TABLES IX LIST OF FIGURES X CHAPTER 1 INTRODUCTION 1 1.1 BACKGROUND 1 1.2 MOTIVATION 3 1.3 LITERATURE SURVEY 5 1.3.1 Minimal power consumption in wireless networks 5 1.3.2 Gauss-Markov mobility model 6 1.3.3 Adapting the refresh interval via mobility prediction 8 1.3.4 Lagrangian relaxation 10 1.4 PROPOSED APPROACH 12 CHAPTER 2 PROBLEM FORMULATION 13 2.1 PROBLEM DESCRIPTION 13 2.2 NOTATION 17 2.3 PROBLEM FORMULATION 19 CHAPTER 3 SOLUTION APPROACH 24 3.1 LAGRANGIAN RELAXATION 24 3.1.1 Subproblem1 (related to decision variable ) 26 3.1.2 Subproblem2 (related to decision variable ) 27 3.1.3 Subproblem3 (related to decision variable ) 29 3.1.4 Subproblem4 (related to decision variable ) 35 3.2 THE DUAL PROBLEM AND THE SUBGRADIENT METHOD 36 CHAPTER 4 GETTING PRIMAL FEASIBLE SOLUTION 37 4.1 HEURISTIC FOR ROUTING POLICY ADJUSTMENT 37 CHAPTER 5 COMPUTATIONAL EXPERIMENT 41 5.1 LARGRANGIAN RELAXATION BASE ALGORITHM (LR) 41 5.2 EXPERIMENT ENVIRONMENTS 43 5.2.1 Assumptions 43 THE ASSUMPTIONS WE MAKE IN THIS STUDY ARE AS FOLLOWS: 43 5.2.2 Parameters 43 5.3 SCENARIOS AND EXPERIMENT RESULTS 44 5.3.1 Scenario 1 (controlling factor: number of destination nodes) 44 5.3.2 Scenario 2 (controlling factor: mobility pattern) 46 5.3.3 Scenario 3 (controlling factor: maximum power radius) 47 CHAPTER 6 CONCLUSION 48 6.1 SUMMARY 48 6.2 FUTURE WORK 49 REFERENCES 50 簡歷 53511258 bytesapplication/pdfen-US移動性的Ad Hoc 網路能源最佳化移動性數學最佳化拉格蘭日鬆弛法MANETEnergy-EfficientMobilityMathematical OptimizationLagrangian Relaxation Methodotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54358/1/ntu-94-R92725019-1.pdf