Q-Coverage Maximum Connected Set Cover (QC-MCSC) Heuristic for Connected Target Problem in Wireless Sensor Network

Q-Coverage Maximum Connected Set Cover (QC-MCSC) Heuristic for Connected Target Problem in Wireless Sensor Network

1. Sunita Gupta

   Ph.D. Scholar

   Department of Computer Science Engineering, Suresh Gyan Vihar University, Jaipur

   Dr. K. C. Roy

   Professoe & HOD Department of Electrical Engineering

   Kautilya Institute of Technology & Engineering, Jaipur

   Abstract-Wireless Sensor Network is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions. Wireless sensors networks (WSNs) can operate in harsh environments in which actual monitoring by human being are risky, inefficient and sometimes infeasible. This is the main advantages of WSN. In most of the cases, replenishment of batteries might be impossible. Thats why lifetime of WSN shows a very strong dependency on battery lifetime. So an important issue in sensor networks is power scarcity, which depends on battery size and weight limitations of WSN node.

   Energy-aware algorithms are designed for extending the lifetime of Wireless Sensor Network. Different mechanisms can be used to optimize the energy of sensors and they have a great impact on prolonging the network lifetime. Energy minimization techniques can be used at routing, clustering and sensor scheduling etc. For appropriate data acquisition in WSN, coverage of all targets and connectivity with the base station, both are required. Also for the reliability purpose higher order of coverage and connectivity is required.

   In this paper an energy minimization heuristic called Q- coverage maximum connected set cover (QC-MCSC) is proposed. This heuristic schedules the sensor nodes activities that are having Q-coverage and connectivity requirements and thus increase the lifetime of Wireless Sensor Network.

   Keywords:-Wireless Sensor Network, Connected target Coverage, Network Lifetime, Network architecture, Cover set, Coverage, Connectivity, Q-Coverage, Connectivity.

   1. INTRODUCTION

Wireless Sensor Network is consists of many self-organized sensing nodes that cooperate with each other to gather the information. WSN are application specific and all design and requirement considerations are different for each application especially when it is used for military application. Each node is equipped with devices which are used to monitor and collect the data, process the collected data and then transmit the data to the adjacent nodes. Finally the data is send to the base station, from which it is send to the user through the satellites or internet. Wireless Sensor Networks are now used in wide range of applications related to national security, surveillance, home and office application[1],habitat monitoring [2,3], health application [4,5], environment forecasting and military etc.Given the vast area to be covered, the short lifespan of the battery-operated sensors and the possibility of having damaged

nodes during deployment, large population of sensors are expected in most WSNs applications. It requires scalable architectural and management strategies. Sensor node lifetime shows a very strong dependency on battery lifetime [6]. In addition, sensors in such environments are energy constrained and their batteries cannot be recharged. The nodes lose their energy quickly and become dead. The frequent topology changes due to the die of sensors make the network quite unstable.

II. Q-COVERAGE AND P-CONNECTIVITY IN WSN

Coverage is a fundamental issue in a WSN, which determines how well a phenomenon of interest (Area or target) is monitored or tracked by sensors [7, 8]. Means up to how much distance a node may sense the information. Each sensor node is able to sense the phenomenon in a finite sensing area. The sensing area of a sensor is normally assumed to be a disk with the sensor located at the center. The radius of the disk is called the sensing radius (Rs) of the sensor, up to which a sensor may cover the area.

Connectivity means the sensor network should remains connected so that the information sensed by sensor nodes can be send back to the base station. Rc (Connectivity radius) is the radius up to which a sensor may communicate its data with other sensor nodes in WSN. Connectivity is as critical as sensing coverage. Multi-hop communications are necessary when a sensor is not connected to the sink node directly. Two sensors are called neighbors if they are within each other's communication range. Along with coverage, connectivity is also important. Moderate loss in coverage may be tolerated by applications but loss in connectivity can be fatal as it can render an entire portion of the network useless as their sensing data cannot reach to the base station. Therefore, it is desirable to have higher degrees of connectivity in Wireless Sensor Networks.

Network lifetime is one of the most important and challenging issues in WSNs which defines how long the deployed WSN can function well. The time till the sensor network remain active and provide the information of the coverage area is called lifetime of WSN. Sensors are unattended nodes with limited battery energy. In the absence of proper planning, the network may quickly cease to work due to the network departure or the absence of observation

sensors deployed close to the interested phenomenon. Since a sensor network is usually expected to last several months without recharging [9, 10], prolonging network lifetime is one of the most important issues in Wireless Sensor Networks.

Coverage and Connectivity are most fundamental requirement of a Wireless Sensor Network. Every target in the network should be covered by more than one node so that it may remain connected even if one sensor fails. Higher order of connectivity is also required for appropriate communications up to the base station. So there is requirement of Q-Coverage and P-connectivity.

Q-coverage: Every point in the plane is covered by at least q- different sensors [11].

P-connectivity: There are at least p disjoint paths between any two sensors [11].

III .PROBLEM STATEMENT AND FORMULATION

Given m targets, with known location in energy constrained Wireless Sensor Network and with n sensors, randomly deployed in the targets vicinity, a problem is formulated to plan the sensor nodes activity in such a way that all the targets are regularly monitored with Q-coverage and connectivity requirement and network lifetime is maximized Given a set S of sensors S1, S2, . . . , Sn, a base station S0, and a set T of targets T1, T2, . . . , Tm, a family of set-covers C1, C2, …, Ck ,is to be find out with time weights l1,…, lk in [0, 1]such that the following constraints are satisfied.

1. Q-coverage and connectivity requirements are satisfied

2. l1 … lk are to be maximized or k is to be maximized.

3. Sensors in each set Ck (k = 1 . . . k) are BS-connected.

4. Each sensor set or cover set monitors all targets.

5. Each sensor appearing in the sets C1, C2… Ck consumes at most E energy, where E is the lifetime of each sensor.

The requirement to maximize k is equivalent with maximizing the network lifetime.

A sensor can participate in multiple sets and thus the sensor sets do not need to be disjointed.

1. CONSTRAINS AND PARAMETERS IN PROPOSED HEURISTIC

   In the proposed heuristic the following parameters are used.

   Sensor Set :-

   S= { S1, S2 , S3,. Sn} denotes the set of n sensors.

   Target Set:-

   T = { T1, T2 , T3,. Tm} denotes the st of m targets.

   Sensor Battery Life time set:-

   B = {B1, B2 , B3 , . … .. Bn} be the set of available battery lifetime of each sensor.

   Sensor target coverage matrix A:-A sensor target coverage matrix A is defined as

   Aij = {1 If sensor Si covers target Tj } Aij = {0 Otherwise }

   Using this metrics A, a Q-Cover C can be find out. A Q-

   Cover C is a set of rows of A (Means set of sensor) such that for every column j, there are at least qj rows, i1 , i2 , i3 ,.. iqj in S where Aij = 1.

   Q-Coverage vector Q:-Q is an integer vector where each element of Q called qi denotes the number of sensors that should covers the target i. (Here each qi of Q is same).

   Connectivity: – Connectivity means there should be at least a

   path between any two sensors. To send the information to the base station, Connectivity is necessary. Proposed algorithm is to maximize the network lifetime satisfying both Q-Coverage and Connectivity requirements.

   Q-Covers C:-Each Q-Cover denotes the set of sensor nodes that together covers all the targets, satisfying their Q- Coverage and P-Connectivity requirement. k is the number of set covers formed. Thus C={C1,C2,C3,.Ck}.

   Lifetime constant vector L:- For each Q-Cover Ck, a small constant lifetime (lk) is given such that lk >= 0.This small constant of lifetime tells for how much time that set cover is active. Thus L= {l1,l2,l3,lk}.

   A small sensor lifetime granularity constant l [0,1]:-A small

   sensor lifetime granularity constant is decided for each set cover and it is l.

   Sensor-Cover Matrix M:-A matrix M defined as:- Mij = {1 if sensor Si is in Q-Cover Cj}

   = {O otherwise}

   e1:-e1 is the energy consumed for sensing per unit of time e2:- e2 is the energy consumed for communication per unit of time.

   There for during a round, consumed energy by an active sensor for sensing is equal to El =lkel, and for communication is E2 = lke2.

2. PROPOSED HEURISTIC WITH Q-COVERAGE MAXIMUM CONNECTED SET COVER (QC-MCSC)

   Input to the propose heuristic is A, Q, l, E, e1 and e2.Where A is the sensor target Coverage matrix. If a sensor Si covers the target Tj, then the value of Aij is set to 1.Else it is 0.Q is the Coverage vector that has been already defined. Each value of Q-Coverage vector is same here. Means the order of Coverage for all the targets are same. l is the lifetime granularity constant which is already defined. E is the initial battery of each sensor. Each active sensor consumes el energy for sensing and e2 energy for communication per unit of time. Initially the lifetime of each sensor is set equal to E. Set covers are made only if the condition of Q-Coverage is satisfied. Means the given condition i Aij Bi qj should be satisfied. So all the three phases will be executed till the condition of Q-Coverage is satisfied. Initially k is set equal to 0, which means the numbers of set covers are 0.

   The proposed heuristic is consisting of four phases.

   1. Coverage Phase:Coverage phase is used to check the order of Coverage while covering all the targets. If the condition of Q-Coverage is satisfied then k is incremented by one. Means a new set cover can be formulated.

      Initially for all targets the numbers of sensors uncovering them are equal to the value qi of Q-Coverage vector. At each step, a critical target to be covered is selected. This can be for example the target most sparsely covered, both in terms of number of sensors as well as with regards to the residual energy of those sensors.

      Once the critical target has been selected, the heuristic selects the sensor with the greatest contribution or we can say the sensor with the maximum utility and that covers the critical target. There are various sensor contribution functions that can be defined. For example a sensor has greater contribution if it covers a larger number of uncovered targets and if it has more residual energy available. After the sensor has been selected, it is added to the current set cover. Uncover_level of all additionally covered targets are also reduced by one. A target is either covered by the sensors already selected in the set cover, or it becomes a critical target, at which point the sensor with the greatest contribution, that covers the critical target, is selected again.

      Output of this phase is set Ck, which will be used in Connectivity and Redundancy Reduction Phase.

   2. Connectivity and Redundancy Reduction Phase: – Input to the Connectivity phase is Ck and G. Ck is the set cover returned in Coverage phase. G is the network Connectivity graph. The goal in this phase is to compute the new and updated connected set Ck. For this apply the BFS algorithm. BFS algorithm is used, to find out the shortest path for each sensor node Si in Ck to the BS in G. All the sensors in this path are added to the set Ck, forming the new and updated connected set Ck.

      If the set Ck is already a connected set, then the new and updated connected set Ck is equal to the old set Ck formed in step 1. Otherwise, relay sensors are added to the set Ck to form a new and updated connected set Ck.

      Next goal is to remove the redundant sensors from the set Ck

      so that a minimal connected set cover can be formulated. A sensor Si Ck with least priority in C is likely to be removed. Remove the sensor Si Ck with least priority and then check if it is still a connected set cover. If it is, then the set Ck is updated by Ck = Ck – S.

   3. Energy and Priority Updation Phase:-

      Input to this phase is Ck. A small constant of lifetime to the set cover Ck is assigned, which has been generated in Redundancy Reduction Phase. This is a non disjoint algorithm which means a sensor may participate in more than one set cover. So one sensor may participate in more than one cover set as a sensor doesnt consume all of its energy in a single cover set. The lifetime of a set cover is decided as minimum between small lifetime granularity constant (l) and

      E2, then that sensor is removed from the set S. This is because of the sensor cannot participates as a sensing or relay node in another set-cover in future.

      At last, the priorities of sensors are updated according to their remaining energy.

3. QC-PC-MCSC HEURISTIC

   INPUT (A, Q, l, E, e1, e2)

   Set lifetime of each sensor to E. k=0

   Repeat while for each target i Aij Bi qj

   1. Coverage Phase

      k = k + 1 Ck =

      For all targets

      Uncover_level(T) = qi

      Do while uncover_level (T)! = 0 for all targets Select a critical target T with uncover_level (T)

      > 0 and a sensor S having greatest contribution function.

      Ck = Ck U{S}

      For all targets covered by S

      Uncover_level (T) = Uncover_level (T) -1 End do

   2. Connectivity and Redundancy Reduction Phase

      Run the BFS algorithm and find out the shortest path from each sensor S Ck to BS in G. Add extra nodes in this path to Ck, forming a new and updated connected set Ck for all S

      Ck

      Select a sensor S Ck with least priority. If Ck – S is still a connected set cover, then

      Ck = Ck – S

      End for

   3. Energy and Priority Updation Phase

   lk = Lifetime (Ck) = Min (l,Max_lifetime ( Ck ) ) For all Si Ck

   If Si Ck is performing as only relay node Then Bi = Bi – E2

   Else if Si is performing as sensing node then Bi = Bi – (E1+E2)

   Else if Bi < E2 then

   S = S – Si

   End for

   Update priorities according to their remaining energy.

   maximum lifetime available from sensors in a set cover Ck, which is obtained by Min(l, Max_lifetime(Ck)). Bi is the

   residual energy of each sensor Si .Each connected set cover corresponds to a round that will be active for lk time. It is assumed that each active sensor consumes el energy for sensing and e2 energy for communication per unit of time. There for during a round, consumed energy by an active sensor for sensing is equal to El = lk el,and for communication is E2 = lk e2.

   Thus an active sensing sensor consumes El + E2 energy, while a relay sensor consumes only E2 energy per round (Since a sensing node sense data and communicates with neighbors in

   the same time, but a relay node is only responsible for communication). In this heuristic, If, after the update, the residual energy Bi of a sensor Si is less than E2, means Bi <

4. SIMULATION AND COMPARISON OF QC-MCSC

   WITH TPICSC

   A small sensing area of 1000x1000m is considered in the simulation of QC-MCSC. All sensors have the same energy equal to 1 unit and sensing range equals 70m. For the simulation, the number of sensors are varied in interval [20, 150] and the number of targets in [20, 90] with an increment of 10.

   Simulations are done for various values of l and vector Q. For each set of parameters, 20 random problem instances are solved and the average of the solution and the upper bounds

   are taken to examine the closeness of the solution to the upper bound.

   The proposed QC-MCSC heuristic is implemented and results are analyzed. Results are then compared with TPICSC

   [12] in figure 1, the graph has been drawn between the number of targets and lifetime for fixed number of sensors. In Figure, the graphs depicts the quality of solution against the upper bound for fixed qm = 1 and for different values of targets. The graph is drawn for different values of l. Smaller the values of l, greater is the lifetime achieved.

   Figure 1: The Average Lifetime Obtained by QC-MCSC for qm =1, and for

   Different Values Of Targets.

   In figure 2, the graph has been drawn between the number of sensors and lifetime for fixed number of targets. In Figure, the graphs depicts the quality of solution against the upper bound for fixed qm = 1and for different values of sensors. The graph is drawn for different values of l.

   Figure 2: The Average Lifetime Obtained by QC-MCSC for qm=1, and for Different Values of Sensors.

   In figure 3, comparison of proposed heuristic QC-MCSC is done with the existing heuristic called TPICSC. Figure shows the lifetime of WSN obtained for QC-MCSC and TPICSC with varying target count. The graph has been drawn between the number of targets and lifetime for fixed number of sensors. In figure, the graphs depicts the quality of solution against the upper bound for l=1.00 and for fixed qm = 1 and for different values of targets. The graph shows that the proposed heuristic QC-MCSC achieves the lifetime higher than TPICSC.

   Figure 3: The Average Lifetime Obtained by QC-MCSC and TPICSC for qm

   =1 and for Different Values of Targets.

   In figure 4, comparison of proposed heuristic QC-MCSC is done with the existing heuristic called TPICSC. Figure shows the lifetime of WSN obtained for QC-MCSC and TPICSC for fixed number of targets. The graph has been drawn between the number of sensors and lifetime for fixed number of targets. In figure, the graphs depicts the quality of solution against the upper bound for l=1.00 and for fixed qm = 1 and for different values of sensors. The graph shows that the proposed heuristic QC-MCSC achieves the lifetime higher than TPICSC.

   Figure 4: The Average Lifetime Obtained by QC-MCSC and TPICSC for qm

   =1 and for Different Values of Sensors.

5. CONCLUSION

   In this paper, a centralized heuristic for Q-coverage and connectivity problem with QoS Requirement is proposed. Simulations are done using MATLAB and results are analyzed. The simulations result reveals that the proposed method yields solution very close to the actual optimal solution. QC-MCSC is based on greedy approach. Finally QC-MCSC is compared with TPICSC and showed that it is better than QC-MCSC. The algorithm selects the critical target and the sensor with highest residual energy. One can have many variations of the problem with additional constraints of coverage and connectivity or directional sensing etc.

6. REFERENCES

1. Mani B. Srivastava, Richard R. Muntz, and Miodrag Potkonjak. Smart kindergarten: sensorbased wireless networks for smart developmental problem-solving environments. In Mobile Computing and Networking, pages 132.138, 2001.

2. A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat monitoring:Application driver for wireless communications technology. In Proceedings of the 2001ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, April 2001, 2001.

3. Alan Mainwaring, Joseph Polastre, Robert Szewczyk, 1`David Culler, and John Anderson. Wireless Sensor Networks for habitat monitoring. In ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02), Atlanta, GA, September 2002.

4. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E.Cayirci, A Survey on Sensor Networks, IEEE Communications Magazine, (Aug. 2002), pp 102-11.

5. Loren Schwiebert, Sandeep K. S. Gupta, and Jennifer Weinmann. Research challenges in wireless networks of biomedical sensors. In Mobile Computing and Networking, pages151. 165, 2001.

6. V. Kawadia, P.R. Kumar, Power control and clustering in Ad Hoc networks, in: Proceedings of IEEE INFOCOM, San Francisco, CA, March 2003.

7. Mohammad Ilyas and Imad Mahgoub eds., Coverage Problems in Wireless Ad Hoc Sensor Networks ,(), Handbook of Sensor Networks, chapter 19, CRC Press, 2004.

8. C.F. Huang and Y.C. Tseng, A survey of solutions to the coverage problems in Wireless Sensor Networks," Journal of Internet Technology, vol. 6, no. 1, pp.1-8, 2005.

9. K. S., L. T. H. and B. J., On k-coverage in a mostly sleeping sensor network, in Proc. of ACM International Conference on Mobile Computing and Networking (MOBICOM), 2004, pp. 144-158.

10. W. K., G. Y., L. F. and X. Y.,Lightweight deployment-aware scheduling for Wireless Sensor Networks," ACM/Kluwer Mobile Networks and Applications (MONET) Special Issue on Energy Constraints and Lifetime Performance in Wireless Sensor Networks, vol. 10, no. 6, pp. 837-852, 2005.

11. X. Bai, S. Kumar, D. Xuan, Z. Yun and T. H. Lai. Deploying Wireless Sensors to Achieve Both Coverage and Connectivity. In Proc. of ACM MobiHoc, 2006.

12. Jamali, M.a., Bakhshivand, N. , Easmaeilpour, M. , Salami, D., An energy-efficient algorithm for connected target Coverage problem in Wireless Sensor Networks,Computer Science and Information Technology (ICCSIT), 2010 3rd IEEE International Conference

,Volume: 9,Page(s): 249 – 254 , Publication Year: 2010 ,IEEE Conference Publications