ireless Sensor Network is consists of many selforganized 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.
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 (R s ) 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. R c (Connectivity radius) is the radius up to which a sensor may communicate its data with other sensor nodes in WSN. Connectivit y 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 Pconnectivity. 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].
Given m targets, with known location in energy constrained Wireless Sensor Network and with n sensors, randomly deployed in the target's 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 S 1 , S 2 , . . . , S n , a base station S 0 , and a set T of targets T 1 , T 2 , . . . , T m , a family of set-covers C 1 , C 2 , ..., C k ,is to be find out with time weights l 1 ,..., l k in [0, 1]such that the following constraints are satisfied. 1) Q-coverage and connectivity requirements are satisfied 2) l 1 ?... l k are to be maximized or k is to be maximized.
4) Each sensor set or cover set monitors all targets. 5) Each sensor appearing in the sets C 1 , C 2 ... C k 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.
In the proposed heuristic the following parameters are used.
Sensor Set :-S= { S 1 , S 2 , S 3, ??. S n } denotes the set of n sensors. Target Set:-T = { T 1 , T 2 , T 3, ??. T m } denotes the set of m targets.
Sensor Battery Life time set:-B = {B 1 , B 2 , B 3 , ?. ... .. B n } be the set of available battery lifetime of each sensor.
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 q j rows, i 1 , i 2 , i 3 ,?.. i qj in S where A ij = 1. Q-Coverage vector Q:-Q is an integer vector where each element of Q called q i denotes the number of sensors that should covers the target i. (Here each q i 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={C 1 ,C 2 ,C 3 ,??.C k }. Lifetime constant vector L:-For each Q-Cover C k , a small constant lifetime (l k ) is given such that l k >= 0.This small constant of lifetime tells for how much time that set cover is active. Thus L= {l 1 ,l 2 ,l 3 ,??l k }.
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:-
M ij = {1 if sensor S i is in Q-Cover C j }= {O otherwise} e 1 :-e 1 is the energy consumed for sensing per unit of time e 2 :-e 2 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 E l =l k e l , and for communication is E 2 = l k e 2 .
Volume XV Issue VI Version I Year ( )
V. proposed heuristic with q-coverage maximum connected set cover (qcmcsc)
Input to the propose heuristic is A, Q, l, E, e 1 and e 2 .Where A is the sensor target Coverage matrix. If a sensor S i covers the target T j , then the value of A ij 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 e l energy for sensing and e 2 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 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 q i 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 C k , which will be used in Connectivity and Redundancy Reduction Phase.
Input to the Connectivity phase is C k and G. C k 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 C k. For this apply the BFS algorithm. BFS algorithm is used, to find out the shortest path for each sensor node S i in C k to the BS in G. All the sensors in this path are added to the set C k , forming the new and updated connected set C k .
If the set C k is already a connected set, then the new and updated connected set C k is equal to the old set C k formed in step 1. Otherwise, relay sensors are added to the set C k to form a new and updated connected set C k .
Next goal is to remove the redundant sensors from the set C k so that a minimal connected set cover can be formulated. A sensor S with least priority in C is likely to be removed. Remove the sensor S with least priority and then check if it is still a connected set cover. If it is, then the set C k is updated by C k = C k -S.
Input to this phase is C k . A small constant of lifetime to the set cover C k 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 doesn't consume all of its energy in a single cover set. The lifetime of a set cover is decided as minimum between small life time granularity constant (l) and maximum lifetime available from sensors in a set cover C k , which is obtained by Min(l, Max_lifetime(C k )). B i is the residual energy of each sensor S i .Each connected set cover corresponds to a round that will be active for l k time. It is assumed that each active sensor consumes e l energy for sensing and e 2 energy for communication per unit of time. There for during a round, consumed energy by an active sensor for sensing is equal to E l = l k e l , and for communication is E 2 = l k e 2 .
Thus an active sensing sensor consumes E l + E 2 energy, while a relay sensor consumes only E 2 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 B i of a sensor S i is less than E 2, means B i < E 2 , 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.
INPUT (A, Q, l, E, e 1 , e 2 ) Set lifetime of each sensor to E. k=0 Repeat while for each target
? i A ij B i ? q j a) Coverage Phase k = k + 1 ? i A ij B i ? q j i ?C k i ?C k Global JournalIn this paper, a centralized heuristic for Qcoverage 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.
Habitat monitoring:Application driver for wireless communications technology. Proceedings of the 2001ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, (the 2001ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean) April 2001, 2001.
Wireless Sensor Networks for habitat monitoring. ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02), (Atlanta, GA
Smart kindergarten: sensorbased wireless networks for smart developmental problemsolving environments. Mobile Computing and Networking, 2001. 138 p. 132.
A survey of solutions to the coverage problems in Wireless Sensor Networks. Journal of Internet Technology 2005. 6 (1) p. .
On k-coverage in a mostly sleeping sensor network. Proc. of ACM International Conference on Mobile Computing and Networking (MOBICOM), (of ACM International Conference on Mobile Computing and Networking (MOBICOM)) 2004. p. .
Research challenges in wireless networks of biomedical sensors. Mobile Computing and Networking, pages151. 165, 2001.
An energy-efficient algorithm for connected target Coverage problem in Wireless Sensor Networks. Computer Science and Information Technology (ICCSIT), 2010 3rd IEEE International Conference, (Page(s
Power control and clustering in Ad Hoc networks. Proceedings of IEEE INFOCOM, (IEEE INFOCOMSan Francisco, CA
Deploying Wireless Sensors to Achieve Both Coverage and Connectivity. Proc. of ACM MobiHoc, (of ACM MobiHoc) 2006.