林永松臺灣大學：資訊管理學研究所蕭至偉Hsiao, Chih-WeiChih-WeiHsiao2007-11-262018-06-292007-11-262018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/54347無線感測網路的存活時間受限於電池壽命、能源使用效率等因素，此外由於感測網路往往不具同步化的機制，封包重傳所消耗的電力不可忽視。本篇論文中，我們強調路由選徑演算法對於網路存活時間的影響力，同時考慮封包重傳因子，用數學模型闡述封包重傳次數的期望值，以一個應變於各節點累積流量的凸性函數表示之。我們應用最佳化技術規劃這個無線感測網路上的節能最佳化路由問題，雖然該問題具有最小最大化目標式、非線性等特性造成數學解題上的難度所在，應用拉格朗日鬆弛法可以求出該凸性規劃問題的最佳解，基於拉格朗日鬆弛法，本文中提出兩種演算法：分別最佳化解決拉格朗日鬆弛後的對應問題，以及直接處理原始規劃問題的最佳化演算法。兩種方法各有其效率上的優缺點，將於內文中分析之。透過上述兩種方法的合併使用，我們得出一組最佳的路由選徑值，使得感測網路的存活時間最大化。經過實驗，其他以最短路徑為基礎的演算法相對於我們的最佳化演算法，存活時間只有最佳解的百分之四十八，證明我們的方法於解題品質上的優越性。The network lifetime for wireless sensor network plays an important role to survivability. It is constraint to battery capacity and energy-efficiency. Besides, being lack of synchronization mechanism in sensor network, the retransmission for each packet is non-neglected. In this thesis, we indicate the importance of routing protocol to network lifetime, and model the expected retransmission time as a convex function with respect to aggregate flow on each sensor node. Thus we formulate the optimal energy-efficient routing as a non-linear min-max programming problem with convex product form, which can be optimally solved by optimal routing framework. Based on the optimal routing framework, we propose Lagrangean-based algorithm and primal optimal algorithm. By the combination of these two algorithms, we can optimally and efficiently get the routing assignment to maximize the network life in the sensor network. From experiments, we observe that when the optimal network lifetime increases as the number of sensor nodes increase. While the shortest path-based heuristic algorithm can only achieve about 48% network lifetime compared with our solution approach.Contents i List of Figures iii Chapter 1 Introduction 1 1.1 Related Work 2 1.2 Research Scope 4 1.3 Retransmission Model 6 Chapter 2 Energy Efficient Routing 8 2.1 Problem Description 8 2.2 Program Formulation 12 2.3 Convex Programming Problem 15 Chapter 3 Solution Approach 17 3.1 Lagrangean Relaxation Methods 17 3.1.1 Lagrangean Subproblems 17 3.1.2 The Dual Problem and the Subgradient Method 21 3.2 Optimal Routing Framework 22 3.2.1 Features of Optimal Routing Framework 22 3.2.2 Computing First Derivative Length 24 3.2.3 Finding MFDL Path 24 3.2.4 Path Flow Adjustment 25 3.3 Primal Optimal Algorithm 26 3.3.1 Finding Minimum Capacity Cut Path 28 3.3.2 Polya’s Method on Path Flow Adjustment 31 Chapter 4 Experiment 33 4.1 Experiment Environments 33 4.1.1 Assumptions 33 4.1.2 Parameters 34 4.2 Scenarios 35 4.3 Discussion 38 4.4 Computational Complexity 40 Chapter 5 Conclusion 43 5.1 Summary 43 5.2 Future Work 44 References 46263002 bytesapplication/pdfen-US能源效率最佳繞路框架拉格朗日鬆弛法最佳化感測網路網路存活時間sensor networksenergy-efficientoptimizationnetwork lifetimeoptimal routing frameworklagrangean relaxationotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54347/1/ntu-93-R91725044-1.pdf