The Divide-and-Conquer Deployment Algorithm Based on Triangles for Wireless Sensor Networks

被引:20
作者
Shiu, Liang Cheng [1 ]
Lee, Chao Yang [2 ]
Yang, Chu Sing [2 ]
机构
[1] Nationl Pingtung Inst Commerce, Dept Comp Sci & Informat Engn, Pingtung 900, Taiwan
[2] Natl Cheng Kung Univ, Dept Elect Engn, Inst Comp & Commun Engn, Tainan 701, Taiwan
关键词
Coordinate transformation; coverage hole; sensor deployment; wireless sensor networks (WSNs); SELF-DEPLOYMENT; COVERAGE; MOBILITY; LIFETIME;
D O I
10.1109/JSEN.2010.2059006
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In order to monitor environmental conditions, a large quality of static sensors normally are deployed randomly in large monitored area. Obviously, there are coverage holes distributed over the monitored area, and the coverage hole can be polygonal. Each coverage hole is evaluated collaboratively by static sensors surrounding the hole, while all coverage holes are evaluated in parallel. Because a polygon can be divided triangularly, exactly how to deploy sensors on a triangle is a priority. Three static sensors are located individually on the three nodes of triangles following random deployment. This work presents a novel divide-and-conquer deployment algorithm based on the triangular form that is executed on the three static sensors. The triangle can be cut into smaller ones that contain at least one interior angle equal to 60 degrees. The small triangles with a 60 degrees angle can be ensured full coverage, while the remaining area is still a triangle. The cutting is repeated until the triangle is sufficiently small so that the sensors on the three nodes can fully cover the area. Ultimately, the coverage hole of a triangle can be full coverage. Moreover, the x-y coordinates of each deployed sensor can be deduced. The proposed algorithm can conquer the coverage hole of each triangle of the polygon. The number of sensors and x-y coordinates of all sensors deployed in the coverage hole of the polygon can be evaluated as well.
引用
收藏
页码:781 / 790
页数:10
相关论文
共 27 条
  • [1] Wireless sensor networks: a survey
    Akyildiz, IF
    Su, W
    Sankarasubramaniam, Y
    Cayirci, E
    [J]. COMPUTER NETWORKS, 2002, 38 (04) : 393 - 422
  • [2] Promoting heterogeneity, mobility, and energy-aware Voronoi diagram in wireless sensor networks
    Ammari, Habib M.
    Das, Sajal K.
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, 19 (07) : 995 - 1008
  • [3] AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880
  • [4] Robust Deployment of Dynamic Sensor Networks for Cooperative Track Detection
    Baumgartner, Kelli A. C.
    Ferrari, Silvia
    Wettergren, Thomas A.
    [J]. IEEE SENSORS JOURNAL, 2009, 9 (09) : 1029 - 1048
  • [5] Berg M., 2008, COMPUTATIONAL GEOMET, V3rd, DOI DOI 10.1007/978-3-540-77974-2
  • [6] General network lifetime and cost models for evaluating sensor network deployment strategies
    Cheng, Zhao
    Perillo, Mark
    Heinzelman, Wendi B.
    [J]. IEEE TRANSACTIONS ON MOBILE COMPUTING, 2008, 7 (04) : 484 - 497
  • [7] Chlamtac Imrich., 2003, Ad Hoc Networks, V1, P13, DOI DOI 10.1016/S1570-8705(03)00013-1
  • [8] Clouqueur T., 2002, P 1 ACM INT WORKSHOP, P42, DOI DOI 10.1145/570738.570745
  • [9] GIBILISCO S, 2003, GEOMETRY DEMYSTIFIED
  • [10] Meguerdichian S, 2001, IEEE INFOCOM SER, P1380, DOI 10.1109/INFCOM.2001.916633