支援定位服務之感測器配置演算法

Sensor Deployment Algorithms for Target Positioning Services

邱佩玲(Pei-Ling Chiu)

指導教授 ： 林永松

國立臺灣大學/管理學院/資訊管理學研究所/博士(2007年)

https://doi.org/10.6342/NTU.2007.02298

摘要

近年來，無論在實務或是學術領域，無線感測器網路(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:

並列關鍵字

sensor deployment ； target positioning ； quality of positioning service ； Energy-Efficiency ； Lagrangean Relaxation ； Simulated Annealing ； Mathematical Modeling ； Network Optimization

參考文獻

[Wan06] B. Wang, “A Survey on Coverage Problems in Wireless Sensor Networks”, Tech. Rep., National University of Singapore, 2006.

[AGP04] Z. Abrams, A. Goel, and S. Plotkin, “Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks,” in Proc. 3rd International Symposium on Information Processing in Sensor Networks (IPSN’04), April 2004, pp. 424-432.

[AS03] S. Adlakha and M. Srivastava, “Critical Density Thresholds for Coverage in Wireless Sensor Networks,” IEEE Wireless Communication and Networking, vol. 3, March 2003, pp. 1615-1620.

[BG77] M. L. Bazarra and J. J. Goode, “The Traveling Salesman Problem: A Duality Approach,” Math. Programming, vol. 13, 1977, pp. 221-237.

[BHE00] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less Low-Cost Outdoor Localization for Very Small Devices,” IEEE Personal Communications, October 2000.