隨著無線感測網路的發展日漸蓬勃，各種相關議題也被廣泛的討論，其中覆蓋率（Coverage）更是直接影響了感測網路的效能，也因此受到更多的關切。然而以往所提出之方法總是假設感測器在各個方向的感測能力都是一致無異的，但在測量上已證明感測器各個方向的感測距離不是完全相等的，所以其感測範圍並不構成一個正圓形，實際狀況下將依然存在許多未覆蓋區域（Hole），使得整體感測之覆蓋率不如預期的高。
本論文建基於不規則感測範圍之假設下，提出了一個節點部署（Deploy）演算法，並且使用一個不規則感測模型（Irregular Sensing Model）來呈現因為不規則（Irregularity）的感測距離而產生非預期的未覆蓋區域。透過將已部署的工作節點以三角化（Triangulation）分組，並利用三角形外心（Circum center）與三頂點等距的特性，將新的節點部署在外心的位置能夠增進較多的覆蓋面積，進而根據外心周圍網格（Grid）被覆蓋的狀況、外心與頂點的距離以及外心與外心的距離做調整和取捨，並在所有選出節點提供的覆蓋率和節點部署的成本效益比都太低時終止演算法。本論文亦加入了一個補強邊界（Boundary）的機制，來彌補靠近邊界處不易選到工作節點的情況，提升整體覆蓋率。實驗結果顯示本論文提出之演算法能夠有效利用感測節點，快速提昇整體覆蓋率至約95％，但相對的剩餘之未覆蓋區域較為零碎且分散，需要較多新節點加入來增加覆蓋率，效益較低。

As the growing of Wireless Sensor Network, various kinds of relative topics have been broadly discussed. Among these topics, since “coverage” directly influent the performance of the network, it catches a lot of concentration. The proposed methods assume that the sensor has a fixed sensing ability in all directions, but experiments show that sensors may have various sensing ability in various directions. In other words, the coverage area of a sensor node will not be a circular disk. Under this situation, there will be a lot of holes so that the coverage rate cannot achieve as high as expected.

This proposed paper holds the assumption of irregular sensing range and propose a sensor deployment algorithm. An irregular sensing model is used to present the unexpected holes caused by irregular sensing range. Deployed sensor nodes will be grouped through the Triangulation procedure. Because of the property of having same distance between the three vertices, the circum center of a triangle is a ideal position to put a node on. Moreover, the proposed algorithm does adjustments according to the status of grids around the circum center, the distance between the circum center and the vertices, and the distance between the circum centers. The algorithm terminates when there is not any new node to provide enough efficient coverage. A boundary enhancement scheme is included in this algorithm to solve the problem that the result of new node location seldom appears near the boundary and elevate the whole coverage rate. The experiment results show that the proposed algorithm can use sensor nodes efficiently and elevate the coverage rate up to 95% fast. In the opposite, the remaining holes will be bitty and dissipative so that lots of new nodes are needed to cover these holes with low benefits.

[1] C.-F. Huang and Y.-C. Tseng, “The coverage problem in a wireless sensor network,” in Proc. ACM Int. Conf. Wireless Sensor Networks and Applications (WSNA), pp. 115–121, 2003.
[2] C.-H. Wu and Y.-C. Chung, “Heterogeneous wireless sensor network deployment and topology control based on irregular sensor model.” Department of Computer Science, National Tsing Hua University.
[3] C.-H. Wu, K.-C. Lee and Y.-C. Chung, “A delaunay triangulation based method for wireless sensor network deployment.” in Proc. of the 12th Int. Conf. on Parallel and Distributed Systems.
[4] E. Onur, C. Ersoy and H. Deli¸c, “Quality of deployment in surveillance wireless sensor networks”, International Journal of Wireless Information Networks, Vol. 12, No. 1, pp. 61-67, January 2005.
[5] F. Aurenhammer, “Voronoi diagrams—A survey of a fundamental geometric data structure,” in ACM Comput. Survey, vol. 23, pp.345–405, 1991.
[6] Gang Zhou, Tian He, Sudha Krishnamurthy, and John A. Stankovic. “Impact of
radio irregularity on wireless sensor networks”, In MobiSYS 2004, June 2004.
[7] G. Wang, G. Cao, and T. La Porta, “Movement-Assisted Sensor Deployment,” Proc. IEEE Infocom, March 2004.
[8] GuilingWang, Guohong Cao, and Tom La Porta. “A bidding protocol for deploying mobile sensors”, In 11th IEEE International Conference on Network Protocol ICNP ’03, pages 315–324,Nov 2003.
[9] Guiling Wang, Guohong Cao and Tom La Porta. Proxy-Based Sensor Deployment for Mobile Sensor Networks. IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), October 2004.
[10] H. Chen, et al., “Grid-based Approach for Working Node Selection in Wireless Sensor Networks,” in Proc. of SAC 2002, Madrid, Spain, pp. 1134-1139, Mar. 2002.
[11] Honghai Zhang and Jennifer C. Hou. “Maintaining sensing coverage and connectivity in large sensor networks”, Technical Report UIUDCS-R-2003-2351, Department of Computer Science,University of Illinois at Urbana Champaign,
2003.
[12] N. Ahmed, S. Kanhere, and S. Jha, “The holes problem in wireless sensor
networks: A survey,” ACM Mobile Computing and Communication Review, vol. 9(2), pp. 4–18, April 2005.
[13] 0. Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu.ACM Sympos. Comput. Geom., pages 106-l 15,1998.
[14] R.-C. Luo, L.-C. Tu and O. Chen, “Auto-deployment of mobile nodes in wireless in wireless sensor networks using grid method.” ICIT 2005, pp. 359-364, 14-17 Dec. 2005 .
[15] S. Meguerdichian, F. Koushanfar, G. Qu, M. Potkonjak, “Exposure in wireless ad-hoc sensor networks”, Proceedings of ACM MobiCom'01, Rome, Italy, pp. 139–150, 2001.
[16] S. S. Dhillon and K. Chakrabarty, “Sensor placement for effective coverage
and surveillance in distributed sensor networks,” in Proc. IEEE Wireless Commun. Netw. Conf., pp. 1609–1614, 2003.
[17] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. F. Abdelzaher, “Range-Free Localization Schemes in Large Scale Sensor Networks,” MobiCom 2003, September 2003.
[18] Xiang-Yang Li, Peng-Jun Wan, Yu Wang, and Ophir Frieder, “Coverage in wireless ad-hoc sensor networks,” in ICC, 2002, New York City, April 28-May 2nd 2002.