權值感測區域的無線感測器網路佈建方法

Deployment Method for Wireless Sensor Networks on Weighted Fields

趙英欽(Ying-Chin Chao)

指導教授 ： 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

在一個給定的區域如何去佈署感測器是一個重要的研究領域，因為它影響無線感測器網路的效能甚巨。傳統的演算法，把感測器網路區域均視為相等的重要性，很多的感測器佈署演算法都著重在如何用有限的感測器或是有限的預算去覆蓋到最大的感測區域面積。然而，在很多的應用裡，例如消防系統、軍防監視、輻射偵測、生化攻擊偵測等等，所監視的地方應隨著每個不同區域的重要性給予不同的優先權：愈重要的區域應該擁有愈高的權值與愈高的優先性。在這篇論文裡，我們提出權值區域感測器覆蓋問題的概念，感測器佈署不再是以覆蓋到最大的區域面積為考量，而是以覆蓋到最大的權值總和為目標。我們在論文裡證明了這個問題屬於NP-Complete，並提出一個接近最佳解的演算法。

關鍵字

無線感測器網路 ； 感測器佈置演算法 ； 權值感測區域的感測器覆蓋問題 ； NP-Complete problem ； Rectilinear Steiner Tree Problem

並列摘要

The deployment of sensors on a given field is an important issue that affects wireless sensor networks. Traditionally, all areas of a sensor field are equivalent, and multiple deployment algorithms are used to maximize the area covered by a given number of sensors or a certain budget. However, in many applications, such as fire control system, battlefield surveillance, detection of nuclear, biological, or chemical (NBC) attack, and other things, the areas must be weighted based on priority of deployment: the more critical the area, the higher the weight and the higher the priority. In this thesis, we introduce the problem of the weighted sensor field, and determine the maximum weight of the coverage area by deploying a given number of sensors on a given weighted field. We prove that this problem is an NP-Complete problem. And propose an algorithm to find a near-optimal solution for the weighted field sensor covering problem.

並列關鍵字

Wireless sensor networks ； deployment algorithm ； weighted field sensor covering problem ； NP-Complete problem ； Rectilinear Steiner Tree Problem

參考文獻

[18] C. F. Huang and Y. C. Tseng, “A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks,” Journal of Internet Technology, vol. 6, no. 1, pp. 1–8, 2005.

[1] M. Cardei and J. Wu, “Coverage in Wireless Sensor Networks,” Handbook of Sensor Networks, M. Ilyas and I. Magboub, CRC Press, 2004.

[2] M. Cardei and D. Z. Du, “Improving Wireless Sensor Network Lifetime through Power Aware Organization,” ACM Wireless Networks, vol. 11, no. 3, pp. 333–340, 2005.

[3] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Transactions on Computers, vol. 51, no.12, pp.1448–1453, 2002.

[4] N. Heo and P. K. Varshney, “An Intelligent Deployment and Clustering Algorithm for a Distributed Mobile Sensor Network,” Proc. of the 2003 IEEE International Conference on Systems, Man and Cybernetics, 2003.