林永松臺灣大學：資訊管理學研究所邱佩玲Chiu, Pei-LingPei-LingChiu2007-11-262018-06-292007-11-262018-06-292007http://ntur.lib.ntu.edu.tw//handle/246246/54239近年來，無論在實務或是學術領域，無線感測器網路(Wireless Sensor Networks, WSNs)的應用與技術發展都是極受關注的議題。目前已有許多重要的WSNs應用被熱切探討，如：環境監測、標的物定位、物體追蹤及健康照護等。預期未來在軍事與民用上，WSNs都會有更廣泛的應用出現。 感測器網路的設計有兩個典型的議題：一是如何建構一個能滿足應用所需之服務品質的感測器網路。另一則是如何延長感測網路生命期。從應用層的觀點來看，改善服務品質需求，必須考慮感測器網路對於應用的支援，如環境監測、標的物定位或追蹤等的能力。再者，感測器電力有限，通常很難再充電。因此，如何延長WSNs的生命期也是配置感測器網路所關注的議題。 此論文朝向提供具環境監測與標的物定位服務的應用方向，來探討感測器配置(sensor deployment)議題，由不同觀點進行一系列的深入研究。茲將每一研究主題之內涵與成果簡述如下：From either practical or theoretical viewpoint, wireless sensor network (WSN) techniques are new and important research issues. Numbers of interesting applications for WSNs have been investigated, e.g., surveillance, target positioning, tracing, and health care. Sensor networks have been forecasted to apply variously, both the civilian and military domains. There are two important issues usually are concerned on WSNs design. One is to construct a qualified WSN for applications to guarantee desired quality of service (QoS). The other challenge is to prolong the network lifetime. From application perspective, in order to improve the QoS supporting by WSNs, the ability of environment surveillance, target positioning, or target tracking have to be controlled carefully. Moreover, it is difficult to replace or recharge the battery for numerous sensors in the most scenarios. Hence, how to prolong the lifetime of WSNs also becomes a key challenge. In this dissertation, we focus on the sensor deployment problem to support environment surveillance and target positioning services from various perspectives. Subsequently, we present each topic briefly as follows:CHAPTER 1 INTRODUCTION 1 1.1 OVERVIEW 1 1.2 RESEARCH SCOPE 5 CHAPTER 2 RESEARCH BACKGROUND 11 2.1 RELATED WORK 11 2.1.1 Coverage 11 2.1.2 QoS in WSNs 22 2.1.3 Energy Efficiency 23 2.1.4 Target Location 24 2.1.5 Sensor Deployment 35 2.2 LAGRANGEAN RELAXATION METHOD 46 2.3 SIMULATED ANNEALING METHOD 51 CHAPTER 3 SENSOR PLACEMENT ALGORITHMS FOR ACHIEVING COMPLETE COVERAGE AND DISCRIMINATION 54 3.1 OVERVIEW 54 3.2 PROBLEM DESCRIPTION 55 3.3 SENSOR PLACEMENT PROBLEM FOR ACHIEVING COMPLETE COVERAGE AND DISCRIMINATION 57 3.3.1 Mathematical Model 57 3.3.2 Algorithm 58 3.3.3 Computational Results 60 3.3.4 Concluding Remarks 65 3.4 CONSIDER ADJUSTABLE DETECTION RADIUS ON RANDOM SENSOR PLACEMENT PROBLEM 66 3.4.1 Simulated Annealing Based Algorithm 66 3.4.2 Computational Results 67 3.5 CONCLUDING REMARKS 74 CHAPTER 4 SENSOR PLACEMENT PROBLEM FOR DIFFERENTIATED QUALITY OF POSITIONING AND SURVEILLANCE SERVICES 75 4.1 OVERVIEW 75 4.2 PROBLEM DESCRIPTION 78 4.2.1 The Framework 78 4.2.2 An Example 80 4.3 MATHEMATICAL MODEL 82 4.4 LAGRANGEAN RELAXATION APPROACH 86 4.4.1 Equivalent Model 86 4.4.2 Transformation 88 4.4.3 Relaxation 90 4.4.4 Getting Primal Feasible Solutions 98 4.4.5 Computational Results 100 4.5 SIMULATED ANNEALING APPROACH 111 4.5.1 Algorithm SA_1 111 4.5.2 Algorithm SA_2 113 4.5.3 Computational Results 113 4.6 PERFORMANCE COMPARISONS 118 4.6.1 Performance Evaluations 118 4.6.2 Convergence Properties Analysis 119 4.6.3 Compare with Other Approaches 124 4.6.4 Results Analysis 127 4.7 CONCLUDING REMARKS 128 CHAPTER 5 ENERGY-EFFICIENT SENSOR NETWORKS DESIGN 130 5.1 OVERVIEW 130 5.2 PROBLEM DESCRIPTION 132 5.3 MATHEMATICAL MODEL 139 5.4 LAGRANGEAN RELAXATION APPROACH 141 5.4.1 Relaxation 141 5.4.2 Getting Primal Feasible Solutions 144 5.4.3 Computational Results 145 5.5 SIMULATED ANNEALING APPROACH 152 5.5.1 Algorithm 152 5.5.2 Computational Results 154 5.6 CONCLUDING REMARKS 164 CHAPTER 6 CONCLUSION AND FUTURE WORK 165 6.1 SUMMARY 165 6.2 FUTURE WORK 168 REFERENCES 169 PUBLICATIONS 176 APPENDIX A: SET-COVER AND SET K-COVER PROBLEMS 177 APPENDIX B: THEOREM A.1 179 APPENDIX C: 189 APPENDIX D: LIST OF NOTATIONS 1921363563 bytesapplication/pdfen-US感測器配置標的物定位完全覆蓋完全辨識服務品質電能效率拉格蘭日鬆弛法模擬退火法數學規劃網路最佳化sensor deploymenttarget positioningquality of positioning serviceEnergy-EfficiencyLagrangean RelaxationSimulated AnnealingMathematical ModelingNetwork Optimizationotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54239/1/ntu-96-D87725001-1.pdf