# Introduction

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.


# 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 (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.


# W


# Year ( )

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].


# 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 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.


# 3) Sensors in each set
C k (k = 1 . . . k) are BS- connected.
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.


# IV.


# Constrains and Parameters in Proposed Heuristic

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.


# Sensor target coverage matrix A:-A sensor target coverage matrix A is defined as -
A ij = {1 If sensor S i covers target T j } A ij = {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 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 .


# Global Journal of C omp uter S cience and T echnology

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.


# 2) 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.


# 3) Energy and Priority Updation Phase:-

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.


# VI.


# Qc-pc-Mcsc Heuristic

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 Journal

# Conclusion

In 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.
![of C omp uter S cience and T echnology Volume XV Issue VI Version I Year ( ) C k = ? For all targets Uncover_level(T) = q i 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. C k = C k U{S} For all targets covered by S Uncover_level (T) = Uncover_level (T) -1 End do b) Connectivity and Redundancy Reduction Phase Run the BFS algorithm and find out the shortest path from each sensor S ? C k to BS in G. Add extra nodes in this path to C k , forming a new and updated connected set C k for all S ? C k Select a sensor S ?C k with least priority. If C k -S is still a connected set cover, then C k = C k -S End for c) Energy and Priority Updation Phasel k = Lifetime (C k ) = Min (l,Max_lifetime ( C k ) ) For all S i ?C k If S i ?C k is performing as only relay node Then B i = B i -E 2 Else if S i is performing as sensing node then B i = B i -(E 1 +E 2 ) Else if B i < E 2 then S =S -S i End forUpdate priorities according to their remaining energy.VII. Simulation and Comparison of Qcmcsc with TpicscA 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 figure1, the graph has been drawn between the number of targets and lifetime for fixed number of sensors. In Figure, the graphs](image-2.png "")
1![Figure 1 : The Average Lifetime Obtained by QC-MCSC for q m =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.](image-3.png "Figure 1 :")
2![Figure 2 : The Average Lifetime Obtained by QC-MCSC for q m =1, and for Different Values of SensorsIn figure3, 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 q m = 1 and for different values of targets. The graph shows that the proposed heuristic QC-MCSC achieves the lifetime higher than TPICSC.](image-4.png "Figure 2 :")
3![Figure 3 : The Average Lifetime Obtained by QC-MCSC and TPICSC for q m =1 and for Different Values of Targets.In figure4, 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 q m = 1 and for different values of sensors. The graph shows that the proposed heuristic QC-MCSC achieves the lifetime higher than TPICSC.](image-5.png "Figure 3 :")
4![Figure 4 : The Average Lifetime Obtained by QC-MCSC and TPICSC for q m =1 and for Different Values of Sensors.](image-6.png "Figure 4 :")
			© 2015 Global Journals Inc. (US)
			© 2015 Global Journals Inc. (US) 1
		
		
			

				


* 
	
		Smart kindergarten: sensorbased wireless networks for smart developmental problemsolving environments
		
			BMani
		
		
			RichardRSrivastava
		
		
			MiodragMuntz
		
		
			Potkonjak
		
	
	
		Mobile Computing and Networking
				
			2001
			138
			132
		
	




* 
	
		Habitat monitoring:Application driver for wireless communications technology
		
			ACerpa
		
		
			JElson
		
		
			DEstrin
		
		
			LGirod
		
		
			MHamilton
		
		
			JZhao
		
	
	
		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
		
			AlanMainwaring
		
		
			JosephPolastre
		
		
			RobertSzewczyk
		
		
			DavidCuller
		
		
			JohnAnderson
		
	
	
		ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02)
				Atlanta, GA
		
			September 2002
		
	




* 
	
		
		
			IFAkyildiz
		
		
			WSu
		
		
			YSankarasubramaniam
		
		
			ECayirci
		
	
	
		A Survey on Sensor Networks?
		
			
			Aug. 2002
		
	
	IEEE Communications Magazine




* 
	
		Research challenges in wireless networks of biomedical sensors
		
			LorenSchwiebert
		
		
			KSSandeep
		
		
			JenniferGupta
		
		
			Weinmann
		
	
	
		Mobile Computing and Networking, pages151. 165
				
			2001
		
	




* 
	
		Power control and clustering in Ad Hoc networks
		
			VKawadia
		
		
			PRKumar
		
	
	
		Proceedings of IEEE INFOCOM
				IEEE INFOCOMSan Francisco, CA
		
			March 2003
		
	




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




* 
	
		A survey of solutions to the coverage problems in Wireless Sensor Networks
		
			CFHuang
		
		
			YCTseng
		
	
	
		Journal of Internet Technology
		
			6
			1
			
			2005
		
	




* 
	
		On k-coverage in a mostly sleeping sensor network
		
			KS
		
		
			LT H
		
		
			BJ
		
	
	
		Proc. of ACM International Conference on Mobile Computing and Networking (MOBICOM)
				of ACM International Conference on Mobile Computing and Networking (MOBICOM)
		
			2004
			
		
	




* 
	
		ACM/Kluwer Mobile Networks and Applications (MONET) Special Issue on Energy Constraints and Lifetime Performance in Wireless Sensor Networks
		
			WK
		
		
			GY
		
		
			LF
		
		
			XY
		
		
			2005
			10
			
		
	
	Lightweight deployment-aware scheduling for Wireless Sensor Networks




* 
	
		Deploying Wireless Sensors to Achieve Both Coverage and Connectivity
		
			XBai
		
		
			SKumar
		
		
			DXuan
		
		
			ZYun
		
		
			THLai
		
	
	
		Proc. of ACM MobiHoc
				of ACM MobiHoc
		
			2006
		
	




* 
	
		An energy-efficient algorithm for connected target Coverage problem in Wireless Sensor Networks
		
			MAJamali
		
		
			NBakhshivand
		
		
			MEasmaeilpour
		
		
			DSalami
		
	
	
		Computer Science and Information Technology (ICCSIT), 2010 3rd IEEE International Conference
				Page(s
		
			IEEE Conference Publications
			
		
	
	Publication Year: 2010