E-VEDGE: A Coverage Hole Minimization Technique for Wireless Sensor Network

E-VEDGE: A Coverage Hole Minimization Technique for Wireless Sensor Network

Mira Rani Debbarma (Tripura University, Suryamaninagar, India), Sangita Rani Bhowmik (Tripura University, Suryamaninagar, India) and Abhishek Majumder (Tripura University, Suryamaninagar, India)
DOI: 10.4018/978-1-7998-2454-1.ch072


Hole minimization in wireless sensor networks is a critical issue. In the presence of obstacles, the issue becomes much more challenging. In this article, a hole minimization technique named enhanced VEDGE (E-VEDGE) has been proposed. The scheme uses both the Voronoi polygon and Delaunay triangulation so that it can work efficiently in presence of obstacle. The proposed scheme, along with two other existing schemes namely: VEDGE and the Delaunay Triangulation-Score (DT-Score) has been simulated. Simulation results show that while the proposed E-VEDGE provides a maximum coverage of 95% to 96.8%, VEDGE and DT-Score provide maximum coverage of 89% to 92.5% and 86% to 87%, respectively.
Chapter Preview


In recent years, the usage of wireless sensor networks (WSNs) (Akyildiz et al., 2002; Potdar et al., 2009) has increased in a very rapid rate in almost every field. This increase in usage of WSN is going to continue for few more decades. This great potential of WSN has drawn the attention of the researchers to enhance its capabilities. The advantages of using WSN are: no necessity of infrastructure, applicability in hazardous condition, cost effectiveness, flexibility and scalability. But one of the fundamental issues in WSN is the coverage problem (Huang et al., 2005) during deployment. The effectiveness of WSN deployed in a region depends on the topology it builds. The coverage area of a WSN is decided by how well the sensor nodes are deployed, how well the sensors can communicate with each other and so on. A WSN should be connected at all times so that nodes are able to communicate with each other. Many schemes have been proposed for enhancing the coverage and connectivity (Zhu et al., 2012) of WSN considering different objectives. Based on the applications and objectives the coverage problems can be classified in three categories (Cardei et al., 2006; Fan et al., 2010): area coverage, point coverage and barrier coverage. The objective of area coverage is to cover a region and monitor each of the points in the region. In case of point coverage, targets can be represented as a set of discrete points. The objective is to cover all these points with minimum number of sensor nodes. The objective of barrier coverage is to detect penetration of an intruder through a region. The challenge of improving the coverage becomes more critical in presence of obstacles. Primary focus of this paper is to provide better area coverage in presence of obstacles. For area coverage, sensors need to cover the entire sensing area. A group of sensors are placed in appropriate locations in order to examine the environment. If any number of sensors does not ensure full coverage, coverage holes (Ahmed et al., 2005) will appear. Therefore, it is necessary to detect holes in WSN in order to improve the area coverage and connectivity of the network.

In the literature, many techniques have been proposed to detect holes in WSN. Some of such techniques are: Voronoi Diagram (Mahboubi, Vaezi, & Labeau, 2014) and Delaunay Triangulation (Aziz et al., 2009; Ghosh et al., 2014). Another scheme named VEDGE strategy (Mahboubi, Moezzi, Aghdam, Sayrafian-Pour, & Marbukh, 2014) which is a combined strategy of two algorithms, namely the Maxmin-edge algorithm (as an edge-based technique) and the Minimax algorithm (as a vertex-based technique), tends to provide better coverage area. The Maxmin-edge algorithm maximizes the minimum distance of every sensor from the edges of its Voronoi polygon. The Minimax algorithm, on the other hand, minimizes the maximum distance of every sensor from the vertices of its Voronoi polygon.

Problem arises when obstacles are present in the sensing region. The sensor node may not be able to sense other sensor nodes, receive or broadcast its local information, move to any desired location or create accurate Voronoi polygon. DT-Score algorithm (Wu et al., 2007) has been designed to work with obstacles. In this scheme, at first, contour points are generated near the obstacles in order to minimize holes. Secondly, refined deployment of the nodes is done where the Delaunay Triangulation is used to find the position of the node and to select the position of the node with more coverage area. A sensor node is then deployed in that area. The problem with DT-Score algorithm is that it is very difficult to use in large areas since Delaunay Triangulation (Aziz et al., 2009) is not suitable for larger regions. Moreover, this approach is applicable in locations with many obstacles.

Complete Chapter List

Search this Book: