A Survey on Coverage and Connectivity Algorithms for Deploying Wireless Sensor Network

A Survey on Coverage and Connectivity Algorithms for Deploying Wireless Sensor Network

Ancy Emmanuel

Post-Graduate Student,

Department of Computer Science and Engineering, Karunya University,

India

PriyaDharsini C

Assistant professor,

Department of Computer Science and Engineering, Karunya University,

India

Abstract

Coverage and connectivity are the most two important problems in wireless sensor network. By eliminating the redundant nodes , reduce computation and get high degree of coverage with connectivity by using minimum number of active nodes is extremely challenging. Coverage and connectivity of the network provide high quality of service to the network it shows that how the area is covered and how accurate the information is gathered by the nodes. Maximizing the network coverage and maintaining the connectivity among the nodes in the network is a main problem . This survey include several algorithms and techniques that addresss coverage connectivity issue.

Keywords:- wireless sensor network , Coverage , Connectivity , Sleep scheduling, Redundant node, active node, Region of interest

1. Introduction

   The WSN consist of autonomous sensors that are spatially connected. The main task of wireless sensor network (WSN) are to identify, collect and report the factors of the physical world. Each node in the network is capable of processing , gathering, communicating sensory information with other nodes in the network. WSN have wide variety of application in the field of military area, battle field

   , medical diagnosis ,environmental monitoring. The success of the WSN depends on the position of the sensor node . The sensor nodes are battery powered when one node is out of battery that will affect the entire network. Performance of the network is one of the key factor of WSN in order to achieve high performance of the network the sleep scheduling approach is used. In sleep scheduling approach some of the nodes are sleep intermittently if they have no work to do that will increases the battery life time . along with that the removal of redundant nodes from the network will decreases the collision between the datas that also reduce the usage of power so that the life time of the battery is improved.

   For the successive operation of the WSN network coverage and connectivity is required . coverage means how much area it can covered and the connectivity shows that how effectively it send data from the source node to the sink. Coverage problem is caused by three main reasons: not enough sensors to cover the whole Region of Interest (ROI), limited sensing range and random deployment. Depended on the coverage objectives and applications, they can be mainly classified into three categories area coverage, point coverage and path coverage. Node which contain redundant information is called redundant nodes and the other nodes are called active nodes. By eliminating the redundant nodes and use minimum number of active nodes to achieve the coverage , connectivity and higher performance is the major aim of this work.

2. Key Concepts

   The important concepts are described below

   briefly.

   1. Coverage

      Overall system performance is affected by the coverage so we need to use a measure of coverage Historically, coverage of three type have been defined

      Blanket Coverage to achieve a static arrangement of nodes that maximizes the detection rate of targets appearing in the sensing field

      Barrier Coverage to achieve a static arrangement of nodes that minimizes the probability of undetected intrusion through the barrier

      Sweep Coverage to move a number of nodes across a sensing field, such that it addresses a specified balance between maximizing the detection

      rate of events and minimizing the number of missed detections per unit area.

      1. Connectivity

         It shows how the data is to be transmitted from the data source to the data sink.

      2. Redundant node

         A node is said to be redundant if all the data present inside that node is present in some other nodes also. The removal of redundant node from the network is very important and it reduces the energy consumption by avoiding collisions inside the network.

      3. Network life time

         It shows how long a network can work in normal stage. Longer network lifetime is needed for good performance.

      4. Computational Complexity

      The summation of time complexity and the space complexity of a network shows the computational complexity of that network.

3. Overview

   In this section we giving brief outline of different algorithms to achieve coverage and connectivity of the WSNs. Table 3.1shows the comparison between them.

   1. Artificial Bee Colony Algorithm For Dynamic Deployment Of Wireless Sensor Networks

      Celaozturk et al.,[1] proposed Artificial Bee Colony Algorithm For Dynamic Deployment Of Wireless Sensor Networks. The major issue of wireless sensor network is dynamic deployment and it directly affect the performance of the system. The artificial bee colony (ABC) algorithm achieves high performance by increasing the coverage area of the network and are developed by taking forging behavior of honeybee swarms as model. The position of the food source and the amount of nectar in that food corresponds to the solution to the optimization problem and the quality of the associated solution respectively. The food source refers to the deployment of sensors in the sensed area. Total coverage area is showed by the fitness value of the

      solution. ABC algorithm is a an appropriate way to achieve Good coverage.

   2. Energy Efficient Ant Colony Algorithms for Data Aggregation in Wireless Sensor Networks

      Chi Lin et al.,[2] proposed Energy Efficient Ant Colony Algorithms for Data Aggregation in Wireless Sensor Networks. One of the most effective swarm intelligence that are applied in wireless sensor network is ant colony optimization(ACO), Each ant in aco considered to have individually limited cognitive ability. The cooperation of ants which find optimal solutions in graphis the process of ACO. DAACA for data aggregation is a family of ant colony optimization it include three phases initialization, packet transmission and operations on pheromones. The remaining energy and the amount of pheromones of neighbor node to select the next hop is estimated in the transmission phase. DAACA shows energy efficiency, increases the network lifetime, success ratio of one hop transmission and computation complexity . The computational problems can be solved by using this probabistic mechanism and the good paths can be founded by using ACO.

   3. Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks

      Sudip Misra etal.,[3] proposed connectivity coverage algorithm for area monitoring using wireless sensor networks . Connectivity and coverage are the major factors that affecting the operation of the wireless sensor network. good coverage is achieved by using minimum number of sensor nodes. Main feature of the covering algorithm is that it will keep a subset of nodes as active to maintain the coverage. For an efficient algorithm it will keep minimum number of nodes as active to achieve the coverage and also it minimizes the energy consumption of the network. By using the Euclidean distance based coverage scheme area of monitoring is covered effectively and it can be extendable to large scale sensor networks.

   4. The Maximum overage Set Calculated Algorithm for WSN Area Coverage

      Xin He et al.,[4] proposed the maximum coverage set calculated algorithm for wsn area of coverage. Coverage problem is one of the most important problem in wsn and it reflects the quality of service of a particular sensor network.. K-Cover

      algorithm can prolong network lifetime. All the nodes are divided into K coverage node set and each coverage node set can cover the entire area. In this case the maximum coverage set number is difficult to calculate . So the new technique has been emerged with the concept of node minimum layer overlapping subfields (MLOF).Minimum coverage layer number of network area is calculated by MLOF. Maximum number of coverage node set is obtained from this. From the maximum number of node set, it divides the node set. Finaly , the distributed maximum coverage set number calculated.

      1. Grid Based Wireless Mobile Sensor network Deployment with Obstacle Adaptability

         Mr. Mayur C et al.,[5] proposed Grid Based Wireless Mobile Sensor network Deployment with Obstacle Adaptability. Coverage and full connectivity are very important problems in wireless sensor network. Suppose an obstacle came over the target field it should be managed carefully during deployment. To achieve k- connectivity a self deployment scheme implemented. In this approach the target area of the sensor is divided into square grid of n*n. The algorithm deploys the square grid to achieve maximum coverage and k connectivity. The algorithm proposed has the capability to solve obstacle adaptability also it reduces the communication overhead , movement of sensor nodes which helps to improve network life time.

      2. A Hybrid Multiobjective Evolutionary Approach for Improving the Performance of Wireless Sensor Network

      Flávio V. C. Martins et al.,[6] proposed a multiobjective hybrid optimization algorithm. The major aim of this approach was to solve the Dynamic coverage and connectivity problem(DCCP) in flat WSNs . It combines multiobjective global on-demand algorithm that helps to improve the DCCP solution using genetic algorithm . This approach provide one of the best method for enhancing the network lifetime

      , coverage and connectivity.

      3.7. A virtual square grid-based coverage algorithm of redundant node for wireless sensor network

      Yanheng Liu et al .,[7] proposed VSGCA for wireless sensor network .Each sensor node has a sensing range in virtual square grid-based coverage algorithm(VSGCA) this sensing range of each sensor node divides into square grids .The node is redundant if all the grids are covered by neighbors. The method cover and judge helps to achieve full coverage and connectivity by using minimum number of active nodes it also eliminate the redundant nodes from the network . VSGCA can also guarantee better performance , lower computational complexity.

      Table 3.1 Comparison

      Algorithm	Coverage achieved	Connectivity	Redundant nodes removed	High Network lifetime
      Artificial Bee Colony Algorithm For Dynamic Deployment Of Wireless Sensor Networks(2012)
      Energy Efficient Ant Colony Algorithms for Data Aggregation in Wireless Sensor Networks(2011)
      Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks(2011)

      The Maximum Coverage Set Calculated Algorithm for WSN Area Coverage(2010)
      Grid Based Wireless Mobile Sensor network Deployment with Obstacle Adaptability(2012)
      A Hybrid Multiobjective Evolutionary Approach for Improving the Performance of Wireless Sensor Network(2011)
      A virtual square grid-based coverage algorithm of redundant node for wireless sensor network(2012)

      – Satisfies the specific condition provided

4. Conclusion

   Coverage and connectivity are the most important feature of a WSN. Compared to other algorithms that we have discussed VSGCA can guarantee coverage, connectivity, longer network lifetime and high performance by using minimum number of active nodes. It out performs compared with other algorithms also it eliminate the redundant nodes from the network.

5. References

1. Celaozturk, Karaboga, Beyza Gorkeml, Artificial bee colony algorithm for dynamic deployment of wireless sensor networks , Turk J Elec Eng & Comp Sci, Vol.20,

   No.2, 2012, c_ T¨UBITAK,doi:10.3906/elk-1101-1030

2. Chi Lin, Guowei Wu, Feng Xia, Mingchu Li, Lin Yao, Zhongyi Pei, Energy efficient ant colony algorithms for data aggregation in wireless sensor networks, Journal of Computer and System Sciences 78 (2012) 16861702, 2011 ELSEVIER.

3. Sudip Misra, Manikonda Pavan Kumar, Mohammad S. Obaidat, Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor

   networks, Computer Communications 34 (2011) 1484

   1496, 2011 ELSEVIER.

4. Xin He,Hua Yang,Xiaolin Gui, The Maximum Coverage Set Calculated Algorithm for WSN Area Coverage, JOURNAL OF NETWORKS, VOL. 5, NO. 6, JUNE 2010.

5. Mr. Mayur C. Akewar and Dr. Nileshsingh V. Thakur, Grid Based Wireless Mobile Sensor Network Deployment With Obstacle Adaptability, International Journal of Wireless & Mobile Networks (IJWMN) Vol. 4, No. 5, October 2012.

6. Flávio V. C. Martins, Eduardo G. Carrano, Elizabeth F. Wanner, Ricardo H. C. Takahashi, Member, IEEE, and Geraldo R. Mateus, A Hybrid Multiobjective Evolutionary Approach for Improving the Performance of Wireless Sensor Networks, IEEE SENSORS JOURNAL, VOL. 11, NO. 3, MARCH 2011.

7. Yanheng Liu , LongxiangSuo, DayangSun , AiminWang, A virtual square grid-based coverage algorithm of redundant node for wireless sensor network, Journal of Network and Computer Applications 36 (2013) 811817,2012 ELSEVIER.