林永松臺灣大學：資訊管理學研究所王弘翕Wang, Hung-ShiHung-ShiWang2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/54398無線感測網路是由許多具有感應、計算以及無線通訊能力之感測器所組成的。由於無線感測網路通常是用隨機的方式來撒佈，故為能源即將耗盡的感測器充電是不可行的。因此，如何延長整個網路的系統壽命成為了無線感測網路相關研究中一項非常重要的議題。 本篇論文研究在感測器具有資料集縮能力之無線感測網路中，如該何路由並且排程所有感測器其活動之問題。我們針對了這個問題提出了一個數學模型。並且，更進一步地提出了一個能建立資料集縮樹以及排程無線感測網路中所有感測器其活動之演算法。藉由拉格蘭日鬆弛法，我們可以找到一個近似的最佳解並且驗證我們提出的演算法是否能達到低能耗、資料集縮能力以及保証所產生的延遲會在一個合理的範圍內。Wireless sensor networks (WSNs) consist of a number of small nodes with sensing, computation, and wireless communication abilities. Because of the deployment of sensors would be typically in random fashion. It would not be feasible to recharge the batteries of a moribund sensor. Hence, how to prolong the lifetime becomes a principal issue in wireless sensor networks. In this thesis, we emphasize on a problem of routing and scheduling the activities of all sensors in a data-centric wireless sensor network. We propose a mathematical formulation to model this problem as an integer programming problem, where the objective function is to minimize the total energy consumption, including transmitting, receiving, idling and sleeping. By Lagrangean Relaxation method, we can find a near optimal solution out and verify whether the algorithm we proposed achieves energy efficiency, fulfils data aggregation, and ensures the latency within a reasonable range.謝詞 I 論文摘要 III THESIS ABSTRACT V Table of Contents VII Lists of Tables IX Lists of Figures X Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 3 1.3 Literature Survey 4 1.3.1 Power Consumption 4 1.3.2 Delay 5 1.3.3 Data Aggregation and Data-centric Routing 7 Chapter 2 Problem Formulation 9 2.1 Problem Description 9 2.2 Problem Notation 13 2.3 Problem Formulation 15 Chapter 3 Solution Approach 23 3.1 Introduction to the Lagrangean Relaxation Method 23 3.2 Lagrangean Relaxation 25 3.2.1 Subproblem 1 (related to decision variable ) 28 3.2.2 Subproblem 2 (related to decision variable ) 28 3.2.3 Subproblem 3 (related to decision variable ) 29 3.2.4 Subproblem 4 (related to decision variable ) 31 3.2.5 Subproblem 5 (related to decision variable ) 32 3.2.6 Subproblem 6 (related to decision variable ) 33 3.2.7 Subproblem 7 (related to decision variable ) 34 3.2.8 Subproblem 8 (related to decision variable ) 34 3.2.9 Subproblem 9 (related to decision variable ) 35 3.2.10 Subproblem 10 (related to decision variable ) 36 3.2.11 Subproblem 11 (related to decision variable ) 36 3.3 The Dual Problem and the Subgradient Method 38 Chapter 4 Getting Primal Feasilbe Solution 41 4.1 Getting Primal Heuristic 41 4.1.1 Heuristic for Routing Policy 42 4.1.2 Heuristic for Scheduling Policy 44 4.2 Rerouting Heuristic 46 4.3 Lagrangean Relaxation Based Algorithm 47 Chapter 5 Computational Experiments 49 5.1 Experiment Environment 49 5.2 Simple Algorithms and Metrics 50 5.3 Experiment Scenarios 50 5.4 Random Network with Different Number of Sensor Nodes 52 5.4.1 Random Network with Different Number of Sensor Nodes (Random Source) 52 5.4.2 Random Network with Different Number of Sensor Nodes (congregated source) 53 5.5 Random Network with Different Number of Sensor Nodes 55 5.6 Random Network with different density of source nodes 56 5.7 Experiment Discussion 58 5.7.1 Topology and Sensor Placement Manner 58 5.7.2 Density of Sources 58 5.7.3The Sequence of Path Selection 59 Chapter 6 Conclusion and Future Work 61 6.1 Summary 61 6.2 Future Work 61 References 63475178 bytesapplication/pdfen-US排程資料集縮,高效率節能低延遲資料中心路由最佳化拉格蘭日鬆弛法整數線性規劃無線感測網路SchedulingData aggregationEnergy-EfficientDelay-EfficientData-centric RoutingOptimizationLagrangean Relaxation MethodInteger Linear ProgrammingWireless Sensor Network.otherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54398/1/ntu-95-R93725038-1.pdf