由於科技的進步及無線網路的便利性，使得無線網路在近年來蓬勃發展，現在更是能夠將無線的技術與感測器相結合，形成一種獨特的無線偵測網路，能即時偵測資料並以無線方式回傳至主控端，與以往以人力進行偵測任務相較，不僅節省人力資源，也能以相對以較少時間完成偵測。但無線偵測網路最大的問題在於它的電力控制，由於資料封包是以轉傳的方式傳回主控端，因此在主控端附近的節點電力消耗十分嚴重，如何能平均分配整個網路的電力消耗是主要的研究重點。
本文研究目的，是要提供適用於無線偵測網路的中繼點機制，利用Voronoi diagram的特性，針對網路節點分佈情況設立中繼點，藉由中繼點提供中控端路由資訊及降低網路節點的電力損耗。經過模擬驗證，我們發現採用我們的中繼點機制的確能有效降底回傳的延遲時間及能量消耗，提高封包傳送的效率及網路的生存時間，藉此增進無線偵測網路的效能。

Wireless networks grow vigorously in recent years. Furthermore, it can combine wireless technology with detecting devices to form a kind of unique wireless detecting sensor networks. Sensor can detect data and transmit to the controller. Compared with executing detecting task with manpower in the past, sensor networks not only save human resources, but also cost less time.
This paper proposed a scheme for relay deployment in wireless sensor networks based on Voronoi diagram. Voronoi diagram can be seen as an assignment of a planar convex region to each site according to the nearest neighbor rule. The scheme could deploy sensor relays efficiently. The amount of the deployed relays is close to the Predetermine Location scheme and far less than the Minimum Set Cover scheme. The energy consumption of the sensors in our scheme is the most efficient. The goal is to reduce the power consumption in each sensor and the delay time and to provide longer lifetime.

[1] David Culler, Deborah Estrin, and Mani Srivastava, "Overview of sensor networks, " IEEE Computer, Special Issue in Sensor Networks, vol. 37, Issue 8, pp. 41-49, Aug. 2004.
[2] Ian F, Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, "A survey on sensor networks," IEEE Communications Magazine, vol. 40, pp. 102-114, 2002.
[3] Ian F, Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci, "Wireless sensor networks: a survey," Computer Networks, vol. 38, pp. 393-422, 2002.
[4] C. Y. Chong and S. P. Kumar, "Sensor networks: evolution, opportunities, and challenges," Proceedings of the IEEE, vol. 91, no. 8, pp. 1247-1256, Aug. 2003.
[5] John A. Stankovic, Tarek Abdelzaher, Chenyang Lu, Lui Sha, and Jennifer Hou, "Real-time communication and coordination in embedded sensor networks," Proceedings of the IEEE, vol. 91, no. 7, July 2003.
[6] Nilesh Khude, Anurag Kumar, and Aditya Karnik, "Time and energy complexity of distributed computation in wireless sensor networks," IEEE INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, Florida, USA, vol. 4, pp. 2625-2637, 2005.
[7] Santosh Pandey, Shaoqiang Dong, Prathima Agrawal, and Krishna Sivalingam, "A hybrid approach to optimize node placements in hierarchical heterogeneous networks," IEEE Wireless Communications and Networking Conference, pp. 3918-3923, Mar. 2007.
[8] Yunxia Chen, Chen-Nee Chuah, and Qing Zhao, "Sensor placement for maximizing lifetime per unit cost in wireless sensor networks," Military Communications Conference, MILCOM 2005, vol. 2, pp. 1097-1102, Oct. 2005.
[9] Zack Butler and Daniela Rus, "Controlling mobile sensors for monitoring events with coverage constraints," Proceedings of 2004 IEEE International Conference on Robotics and Automation, vol. 2, pp. 1568- 1573, Apr. 2004.
[10] Cortes J, Martinez S, Karatas T, and Bullo F, "Coverage control for mobile sensing networks," IEEE Trans. Robotics and Automation, pp. 243-255, 2004.
[11] Bogdan Carbunar, Ananth Grama, Jan Vitek, and Octavian Carbunar, "Coverage preserving redundancy elimination in sensor networks," Proceedings of the 1st IEEE Conf. on Sensor and Ad Hoc Communications and Networks, pp. 377-386, 2004.
[12] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor setworks," IEEE Trans. Wireless Communications, vol. 1, no. 4, pp. 660-670, Oct. 2002.
[13] Hsi-Feng Lu, Yao-Chung Chang, Hsing-Hsien Hu, and Jiann-Liang Chen, "Power-efficient scheduling method in sensor networks," Proceedings of IEEE System, Man and Cybernetics, pp. 4705-4710, 2004.
[14] Kung, H. T., and Vlah, D. "Efficient location tracking using sensor networks," IEEE Wireless Communications and Networking Conference (WCNC), vol. 3, pp. 1954-1961, Mar. 2003.
[15] Robert Kaucic, A. G. Amitha Perera, Glen Brooksby, John Kaufhold, and Anthony hoogs, "A Unified Framework for Tracking through Occlusions and across Sensor Gaps", Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), vol. 1, pp. 990–997, 2005.
[16] Wei-Peng Chen, Jennifer C. Hou, and Lui Sha, "Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks", IEEE Transactions on Mobile Computing, vol. 3, no. 3, pp. 258–271, Jul. 2004.
[17] Yingqi Xu, Julian Winter, and Wang-Chien Lee, "Dual Prediction-Based Reporting for Object Tracking Sensor Networks", First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04), pp. 154-163, 2004.
[18] Jukka Suomela, "Approximating relay placement in sensor networks," Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, pp. 145-148, Oct. 2006.
[19] Maulin Patel, R. Chandrasekaran, and S. Venkatesan, "Energy efficient sensor, relay and base station placements for coverage, connectivity and routing," Performance, Computing, and Communications Conference, IPCCC 2005, 24th IEEE International, pp. 581-586, Apr. 2005.
[20] A. Kashyap, S. Khuller, and M. Shayman, "Relay placement for higher order connectivity in wireless sensor networks," IEEE INFOCOM, Barcelona, Spain, pp. 1-12, Apr. 2006.
[21] Abhishek Kashyap, Fangting Sun, Mark Shayman, "Relay placement for minimizing congestion in wireless backbone networks," WCNC 2006, Las Vegas, pp. 159-164, 2006.
[22] K. Xu, Q. Wang, H. Hassanein, and G. Takahara, "Optimal wireless sensor setworks (WSNs) deployment: Minimum cost with lifetime constraint," IEEE WiMob 2005, Montreal, QC, Canada, pp. 454-461, Aug. 2005.
[23] Quanhong Wang, Kenan Xu, Glen Takahara, and Hossam Hassanein, "On lifetime-oriented device provisioning in heterogeneous wireless sensor networks: approaches and challenges," Network, IEEE, pp. 26-33, May-June 2006.
[24] S. Coleri Ergen, and P. Varaiya, "Optimal placement of relay nodes for energy efficiency in sensor networks," Communications, 2006 IEEE International Conference, vol. 8, pp. 3473-3479, June 2006.
[25] F. Aurenhammer, and R. Klein. "Voronoi diagrams," In J. Sack and G. Urrutia, editors, Handbook of Computational Geometry, ch. 5, Elsevier Science Publishing, pp. 201-290, 2000.
[26] Qiang Wang, Yaoyao Zhu, and Liang Cheng, "Reprogramming wireless sensor networks: challenges and approaches," IEEE Network, vol. 20, no. 3, pp. 48-55, May/June 2006.
[27] Stine J.A. "Exploiting smart antennas in wireless mesh networks using contention access," IEEE Wireless Communications, vol. 13, no. 2, pp. 38 - 49, Apr. 2006.