Improving Target Coverage and Network Connectivity of Mobile Sensor Networks

Improving Target Coverage and Network Connectivity of Mobile Sensor Networks

Renuka Narayan Kattimani Prof. Prathima S. D

PG Student Asst. Professor

Department of ECE, M. Tech (DCN) Department of ECE, M. Tech (DE&CS) BTLITM, Bangalore, India BTLITM, Bangalore, India

Abstract – Target coverage and Network connectivity are two main challenging issues of mobile sensor networks. Target coverage covers a set of specified points of interest in the randomly deployed MSNs. Target coverage is usually interpreted as how well a sensor network will cover an area of interest. Coverage of interest points and network connectivity are two main challenges of Wireless Sensor Networks (WSNs). MSD problem has again two problems i.e., Target coverage (TCOV ) and Network connectivity (NCON). For general cases of TCOV, two heuristic algorithms, i.e., the Basic algorithm based on clique partition and the TV-Greedy algorithm based on Voronoi partition of the deployment region, are proposed to reduce the total movement distance of sensors. For NCON, an efficient solution based on the Steiner minimum tree with constrained edge length is proposed .The combination of the solutions to TCOV and NCON, as demonstrated by extensive simulation experiments.

Key words- Wireless sensor networks, target coverage, connectivity, mobile sensors, energy consumption

1. INTRODUCTION

   Wireless sensor networks are used in many application

   .In this paper WSN has been used for environmental monitoring and object tracking. Target coverage and connectivity are two main challenging and practically important issues of WSNs. Target coverage aims to cover a set of specified points of interest in the deployment region of a WSN. A wireless sensor network is a set of physically distributed sensor nodes. For network connectivity sensors are used to performs the task of collecting important data, processing the data, monitoring the environment, etc.

   1. For the case of TCOV, Basic algorithm and TV greedy algorithms are used. In case of Basic algorithm, it is used to reduce the total movement distance by minimizing number of sensor. In case of TV Greedy algorithm, it will minimizes the distance by grouping and dispatching the sensors.

   2. For NCON problem first an edge length constrained Steiner tree is constructed. It will determine the Steiner points and these points are used to connect coverage sensors in the selected area and then the extended Hungarian method is used to find the optimal sensors to move to these points.

   3. Extensive simulation experiments are conducted to evaluate the performance of the proposed algorithms. The simulation result gives the combination of the solutions to TCOV and NCON.

   4. Related Work

   Movement of sensors consumes more energy than sensing. So the movement of sensors need to be reduced to conserve energy. Target coverage is divided into two cases: special and general case. Special is done by using Hungarian method and general case is done by using both Basic and TV Greedy algorithm. Up to this we first formulate mobile sensor deployment (MSD).This MSD problem leads to Combine the solution of TCOV and NCON.

2. METHODOLOGY

   Node Deployment:

   The Node Deployment is the algorithm which is used to place the nodes in the network in the given area of x*y Group Formation Time Based: This is used to group the set of nodes under a target based on REPLY time of the node to the Target

   Group Formation Random Based: This is used to group the set of nodes under a target based on random selection of the node to the Target

   Group Formation Distance Based: This is used to group the set of nodes under a target based on distance of the node to the Target and also used to adjust the position of the targets

   Route Discovery Based on Time:

   Source node, destination node & Transmission Range acts as an input parameters. The set of nodes are found which have the distance within transmission range known as neighbors nodes. If the set of neighbors has the destination node then stop the process otherwise pick a node which sends REPLY in less time as the next forward node Repeat steps until destination is reached

   Route Discovery Based on Random:

   Source node, destination node & Transmission Range acts as an input parameters. The set of nodes are found which

   have the distance within transmission range known as neighbors nodes. If the set of neighbors has the destination node then stop the process otherwise pick a node randomly as the next forward node Repeat steps until destination is reached

   Route Discovery Based on Probabilistic Fashion:

   Source node, destination node & Transmission Range acts as an input parameters. The set of nodes are found which have the distance within transmission range known as neighbors nodes. If the set of neighbors has the destination node then stop the process otherwise pick a node based on maximum coverage. Decrement the Time to Live period.

   Energy Consumption:

   The energy wasted for delivering the packets from the source node to destination node. The total energy consumption is given as follows

   l

   l

   TEc Ei

   i1

   Where,

   l number of links

   i

   i

   E Energy consumed by the ith link

   The energy consumed by the ith link given by

   The process is repeated until destination is reached or TTL expires, Once TTL expires Min Hop Routing is used.

   Ec 2 Etx

   • Eamp d

   Comparison:

   End to End Delay:

   End to End Delay is the time taken for the RREQ to go

   Etx energy required for data transmission Eamp energy required for data generation d dis tan ce between two int ermediate nodes

   from the source node to destination node and then send

   back the RRPLY from destination node to source node.

   environment

   factor

   E2Edelay tstop tstart

   0.1 1

   Where,

   The S tan dard environment

   factor

   tstop

   This is the Time at which RRPLY

   is recieved

   Number of Alive Nodes:

   This is defined as the count of set of nodes whose battery

   tstart This is the Time at which RREQ is send

   Number of Hops:

   The Number of intermediate links from the source node to destination node is called Number of Hops.

   level is greater than or equal to B/4 Where B is initial Battery Power.

   Number of Dead Nodes:

   This is defined as the count of set of nodes whose battery level is less than B/4.Where B is initial Battery Power.

   Node Deployment

   Node Deployment

   Time Based Grouping

   Random Based Grouping

   Distance based Grouping

   Time Based Grouping

   Random Based Grouping

   Distance based Grouping

   Route Discovery Probabilistic Tree Based

   Route Discovery Random Based

   Route Discovery Time Based

   Route Discovery Probabilistic Tree Based

   Route Discovery Random Based

   Route Discovery Time Based

   Comparison Time Based Discovery, Random Based Discovery and Probalistic Tree Based

   1. End to End Delay

   2. Number of Hops

   3. Energy Consumption

   4. Number of Alive Nodes

   5. Number of Dead Nodes

   6. Routing Overhead

3. SOLUTIONS TO THE TCOV PROBLEM

   Fig 1: Methodology

   1. Exact Solutions to a Special Case of TCOV

      In this special case, as targets disperse from each other by more than double of the coverage radius, each sensor can cover at mostone target. Thus, different targets need to be covered by different mobile sensors.

   2. Heuristic Solutions to the General Case of TCOV

      1. The Basic Algorithm

   The algorithm first finds out the set of targets to be covered and the set of mobile sensors to be moved. It then finds a minimum clique partition on the graph of targets in Tneedcov. For every clique and every sensor in Srest, the potential destination and corresponding movement distance for the sensor to

   cover targets in that clique is computed. Fig. 2 demonstrates the execution of the Basic algorithm.

   Fig 2: Illustration of the Basic algorithm: (a) Initial positions of targets and sensors; (b) The results of the Basic algorithm, in which two sensors need to move; (c) Suboptimality of the Basic algorithm: moving least sensors may induce longer total movement distance.

   1. The Target-Based Voronoi Greedy Algorithm

      TV Greedy algorithm, it will minimizes the distance by grouping and dispatching the sensors. The basic idea of TV-Greedy is to deploy the nearest sensor to cover the targets that are uncovered. Since sensors located in a targets Voronoi polygon are closer to this target than to others, we use Voronoi diagrams of targets to group sensors. Fig 3 shows illustration of TV greedy algorithm.

      Fig.3: Illustration of the TV-Greedy algorithm.

   2. TV-Greedy Algorithm:

   Input: T ¼ t1; t2; . . . ; tm;//The position of all targets S ¼ s1; s2; . . . ; sn;//The position of sensors

   rs;//The coverage radius Output: tmc;//The total moving cost

   1. Generate the Voronoi diagram (VD) of targets;

   2. Determine neighbors for each target according to their Voronoi polygon;

   3. Determine the OSG for each target according to S and VD;

   4. for each OSGido

   5. Determine the chief server;

   6. Identify the aid server for tis neighbor; 7 for each ti do

   8 if ti has already been covered then 9 Return cost(tiÞ ¼ 0;

   1. else

   2. Produce CSGi of ti; 12 if CSGi 6¼ ; then

   13 Move the nearest server to cover ti; 14 return cost(tiÞ ¼ moving distance; 15 else

   1. if there exit neighbors chief servers that could be shared then

   2. move the nearest chief server to cover ti; 18 Return cost(ti)= moving distance;

   1. else

   2. Regenerate the CSG of ti by searching aid servers of the tis 2nd or higher order neighbors;

   3. Move the nearest aid server to cover ti; 22 Return cost(tiÞ ¼ moving distance ;

   23 tmc ¼ tmc þ cost(ti) 24 return tmc

4. SOLUTIONS TO THE NCON PROBLEM

   There are steps to solve NCON problem. The first step is seeking an edge length constrained Steiner tree T spanning coverage sensors and the sink. Since the Steiner tree problem is NP-hard, we propose an approximate algorithm as follows: (1) constructing an euclidean minimum spanning tree (ECST), and (2) separating each edge of the spanning tree into the sections with length.

5. COMPARISON OF ALGORITHMS.

   Figure.3 shows the comparison between three algorithms: Basic, TV-Greedy and EX-Hungarian method. The movement distance increases when targets increase. Ex- Hungarian and basic algorithm performs very close to each other. Basic algorithm uses the minimum number of coverage sensors. The number of coverage sensors used by TV-Greedy is between the other two algorithms.

   Fig.4: Comparison of Basic, TV-Greedy and Ex- Hungarian method

   TV-Greedy achieves less movement than other two algorithms. This is because of TV-Greedy uses smart strategy to choose coverage sensors. This algorithm groups sensors according to their proximity to the targets, and uses the nearest sensor to cover a target. This effectively minimizes the total movement distance to cover all the all the targets

6. SIMULATION EXPERIMENTS.

   1. Simulation Settings and Performance Metrics.

      We evaluate the performance of algorithms and conduct a set of simulation experiments using matlab.TV-Greedy algorithm performs the best among the three algorithms, we also investigate the performance gap between TV- Greedy and the optimal solution in a small network to get an impression of how close TV-Greedy approaches the optimal solution. Fig 5 shows a network

      topology generated by different combinations of algorithms.

      Fig.5:. Network topologies generated by different combinations of algorithm.

   2. Performance of Different Algorithms to TCOV We will compare three algorithms

      1. In case of number of mobile sensors

         Fig.6: Impact of the number of mobile sensors

      2. In case of number of targets

         Fig.7: Impact of the number of targets

   3. Further investigation of TV Greedy

7. FUTURE WORK

   In the future, we plan to extend our work to address the problem of target coverage and network connectivity in MSNs in a distributed way. A distributed solution to the MSD problem is very attractive because it takes advantage of robustness when facing network changes and sensor failures. The main challenge is that, in the distributed manner, mobile sensors can communicate only with sensors in proximity. Similarly, the moving decisions need to be made Locally

8. CONCLUSION

In this work, we have studied the Mobile Sensor Deployment (MSD) problem in Mobile Sensor Networks (MSNs), This problem is divided into two sub-problems, Target COVerage (TCOV) problem and Network CONnectivity (NCON) problem. For the TCOV problem, we prove it is NP-hard. For a special case of TCOV, an extended Hungarian method is provided to achieve an optimal solution; for general cases, two heuristic algorithms are proposed based on clique partition and Voronoi diagram, respectively. For the NCON problem, we first propose an edge constrained Steiner tree algorithm to find the destinations of mobile sensors, then use the extended Hungarian to dispatch rest sensors to connect the network.

6.3.1 Impact of different network parameters

Fig 8: shows the impact if different network parameters on TV Greedy algorithm

Fig.8: Impact if network parameters on TV Greedy algorithm

5.3.2. Impact of sensors initial position on TV Greedy algorithm

Fig.8 Impact of sensors initial position on TV Greedy algorithm

REFERENCE

1. Target Coverage and Network connectivity in Mobile sensor networks, IEEE sponsored second International Conference on Electronics and Communication Systems (ICECS 2015).

2. Zhuofan Liao, Jianxin Wang, Shigeng Zhang, Jiannong Cao and Geyong Min, Minimizing Movement for Target Coverage and Network Connectivity in Mobile Sensor networks, IEEE Transactions on Parallel and Distributed Systems, vol. Xxx, no. Xxx, April, 2014.

3. Zhuofan Liao, Shigeng Zhang, Jiannong Cao, Weiping Wang, Jianxin Wang, Minimizing Movement for Target Coverage in Mobile Sensor Networks, 32nd International Conference on Distributed Computing Systems Workshops, 2012.

4. R. Huang, W.-Z. Song, M. Xu, N. Peterson, B. Shirazi, and R. LaHusen, Real-world sensor network for long-term volcano monitoring: Design and findings, IEEE Trans. Parallel Distrib. Syst., vol. 23, no. 2, pp. 321329, Feb. 2012.

5. G. Blumrosen, B. Hod, T. Anker, D. Dolev, and B. Rubinsky, Enhancing rssi-based tracking accuracy in wireless sensor networks, ACM Trans. Sens. Netw., vol. 9, no. 3, pp. 129, 2013.

6. M. Lu, J. Wu, M. Cardei, and M. Li, Energy-efficient connected coverage of discrete targets in wireless sensor networks, in Proc.n of 3rd Int. Conf. Netw. and Mobile Comput., pp. 4352, 2005.

7. B. Liu, O. Dousse, P. Nain, and D. Towsley, Dynamic coverage of mobile sensor networks, IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 2, pp. 301311, Feb. 2013.

8. G. Wang, M. Z. A. Bhuiyan, J. Cao, and . Wu, Detecting movements of a target using face tracking in wireless sensor networks, IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 4, pp. 939949, 2014.

9. R. Tan, G. Xing, J. Wang, and H. C. So, Exploiting reactive mobility for collaborative target detection in wireless sensor networks, IEEE Trans. Mobile Comput., vol. 9, no. 3, pp. 317 332, Mar. 2010.