Coverage and Connectivity using Virtual Spanning Tree in Wireless Sensor Networks

Coverage and Connectivity using Virtual Spanning Tree in Wireless Sensor Networks

Anusha S P1Abhilash C N2

4thSem M.Tecp, Associate Professor 2

Department of ISE, SJB Institute of Technology, Bangalore

Abstract:- Energy consumption is one of the most critical challengesin the area of sensor networks. Sleep-wakeup techniquescan reduce the energy consumed in the sensor networks. Coveragetends to cover the area with the minimum possible number ofsensors in networks. There are many area coverage approaches such as area coverage, point coverage and boundary coverage which alsoconsider the connectivity problem. However, in the area of pointcoverage, they cover specified points within the area of the network.Here, we present a point coverage mechanism andtwo connectivity mechanisms. These mechanisms are comparedto one of the best methods that consider both point coverageand connectivity. In the point coverage mechanism, we presenta method for computing the waiting time, which reduces thenumber of the required sensors. For preserving the connectivity,virtual spanning tree (VST) and Microsoft research (MSR) are proposed. These mechanisms arebased on making a virtual spanning tree and converting this treeto a physical tree. In order to spread out sensed data to the base stationfrom different paths and decrease the loss of dead nodes, insteadof using a minimum spanning tree (MST) to connect nodes tothe base station, a combination of distance of nodes and numberof hops are used to select edges and construct the tree. The simulationresults show that the proposed coverage method reduces energyconsumption and maximizes network lifetime compared to the existing method. TheVST and MSR use more energy than the existing method,but the average packet loss decreases by up to 40%. Moreover,VST and MSR have less depth and data latency.

Keywords: Energy efficiency, VST, MSR, MST, Sleep-wakeup technique, Coverage, point coverage.

1. INTRODUCTIONA

   wireless sensor network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions such as temperature, sound, pressure etc and to cooperatively pass their data through the network to a main location.Wireless sensor networks constitute the platform of a broad range of applications related to national security, surveillance, military, healthcare, and environmental monitoring. The sensor coverage problem has received increased attention recently, being considerably driven by recent advances in affordable and efficient integrated electronic devices. Wireless sensor networks (WSNs) have attracted a great deal of research attention due to their wide-range of potential applications. WSNs provide a new class of computer systems and expand the ability of individuals to remotely interact with the physical world. In a broad sense, WSNs will transform the way we manage our homes, factories, and environment. Applications of WSNs include battlefield surveillance,

   biological detection, home appliance, smart spaces, and inventory tracking.The coverage concept is subject to a wide range of interpretations due to a variety of sensors and their applications. Different coverage formulations have been proposed, based on the subject to be covered (area versus discrete points) andsensor deployment mechanism (random versus deterministic) as well as on other wireless sensor network properties (e.g. networkconnectivity and minimum energy consumption)Sensor node: A sensor node, also known as a mote , is a node in a wireless sensor network that is capable of performing some processing, gathering sensory information and communicating with other connected nodes in the network. A mote is a node but a node is not always a mote. A minimumspanning tree (MST) or minimum weight spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.Virtual spanning tree and Microsoft research spanning trees are used to preserve connectivity and to protect against node failure.Coverage is one of the most important challenges in the areaof sensor networks. Since the energy of sensors are limited, it is vital to cover the area with fewer sensors. Generally,coverage in sensor networks is divided into area coverage,point coverage, and boundary coverage subareas. Coveragedoes not ensure connectivity of nodes. However, many approacheshave addressed both area coverage and connectivity, but limited numbers of approaches have covered both.Cardei proposed one of the best approaches in the field of connected point coverage. It contains two steps. Using thefirst step, the sensing nodes are selected. In the second step,some relay nodes are selected to make a MST between sensingnodes and the sink, based on Prims algorithm, to ensure sinkconnectivity.However, MST has a problem. Usually,MSTis relatively deep. In addition, the sink does not have many branches. Therefore, in the case of failure, they lose a significantamount of data.

   In this method, MST is modified and a balancedtree is introduced, which solves the problem of using MST to ensureconnectivity. In Prims algorithm, the cost of edges is thedistance of nodes. In contrast, the proposed method uses acombination of distance and hop count as the cost of edges. In the first step, distributed algorithm is used to computethe priority of nodes. This priority is computed based onthe residual energy of nodes and the number of targets intheir sensing area. Nodes with more residual energy and moretargets in their sensing area have more priority than other nodes. In the second phase,

   authors use another algorithm to selectsome relay nodes to construct a balanced tree between sensingnodes and the sink. To construct the tree, they first constructa virtual tree with targets and the sink, which is used as askeleton to built an actual tree. After making a virtual tree, they convert it to a physical tree between nodes that are selectedin the covering phase as a sensing node and the sink.In comparison to the Cardei method, the proposed method uses less sensors to cover all targets. In addition, proposedmethod is more balanced than the Cardei method; therefore, in the case of node failure, they will lose less data, as all branches are more balanced. However, proposed trees uses morerelay nodes to deliver sensed data to the sink, so the probability of a node failure in the tree is more of that the Cardei method.

   The contributions of this method are as follows:

   • One of the existing point coverage methods is changed to reduce energy consumption of sensor nodes which uses VST and MSR mechanisms.

   • To maintain connectivity, a method is proposed to construct a balanced tree which is more robust against failure.

   • We modify MSR to reduce no of dead nodes as well as packet loss.

2. RELATED WORKS

   A survey on coverage problems in wireless sensor networks is presented. The coverage problem is divided into three subcategories: area coverage, point coverage and boundarycoverage.Most of the research in the field of sensor networks consistsof area coverage. The goal of area coverage is to cover as mucharea as possible with the minimum number of sensors. Mostof these researches use probabilistic or geometric approaches. It is shown that the problem of selecting a subsetof sensors that cover the whole area is NP-Complete, andan efficient approximation algorithm is proposed toaddress area coverage. If the radio range isat least twice the sensing range, complete coverage of a areaimplies connectivity among the working set of nodes. In ACOS[5], each node computes the area which can be only coveredby it. Ifthis area is smaller than a threshold, then this nodegoes to active mode.

   The goal of point coverage is to cover some specific points of the network. An efficient method is proposed to extendthe sensor network lifetime by organizing the sensors into amaximal number of disjoint sets that are activated successively. Selecting disjoint sets do not necessarilyresult in a larger lifetime of the network than non-disjointsets. In this approach, the nodes are organized into maximalnumbers of set covers instead of disjoint-sets. The target coverage issue in wireless sensor networkshave sensors with adjustable sensing range. To solve thisissue, linear programming, a localized greedy algorithm, anda distributed greedy algorithm, are proposed.In the boundary coverage problem, the goal is to cover thenetwork so as to minimize the probability that a mobile objectwhich cross the barrier of network remains undetected. The best path for an intruder from asource to a

   destination is in the Voronoi diagram. The view field of sensor nodes is limited and sensors a havea directional camera. An optimal polynomial time algorithmwas presented for computing the worst-case breach coverage.

   Breach is the maximal distance that any hostile target cannotbe detected by the sensors while traveling through a region. The coverage method uses a distributed algorithm to select sensing nodes. Duringthe second phase, it selects relay nodes. For this purpose, itmakes a virtual tree between targets and the sink and thenconverts it to a physical tree of sensing nodes and the sink. In the proposed method thecoverage method is changed to reduce the number of active sensors thatare needed to cover all of the targets. Instead of using MST tomaintain sink-connectivity, a balanced tree is used to decrease the amount of data loss in sensor networks.

   M. Cardei and J. Wu [2] Wireless sensor networks constitute the platform of a broad range of applications related to national security, surveillance, military, health care, and environmental monitoring. The sensor coverage problem has received increased attention recently, being considerably driven byrecent advances in affordable and efficient integrated electronic devices. This problem is centeredaround a fundamental question: How welldo the sensors observe the physical space? The coverage concept is subject to a wide range of interpretations due to a variety of sensors andtheir applications. Different coverage formulations have been proposed, based on the subject to be covered (area versus discrete points) and sensor deployment mechanism (random versus deterministic) as well as on other wireless sensor network properties (e.g. networkconnectivity and minimum energy consumption). Here authors survey recent contributions addressing energy-efficient coverageproblems in the context of static wireless sensor networks. Authors present various coverage formulations, their assumptions, as well as anoverview of the solutions proposed.

3. APPROACHES

   A distributed method is proposed forconnected point coverage, which is based on the Cardei method. In order to cover some targets in a homogeneous sensor network, an efficient number of sensors are used while stillpreserving sink-connectivity. Nodes and targets are stationary and authors suppose that each node knows the location of all targetsand the sink.The algorithm runs in rounds. Each round begins with aninitialization phase in which every sensor decides whether tobe active or inactive for the rest of the round. This phaseis divided into two steps: In the first step, sensing nodesselection, the sensor nodes are selected such that the unionof them covers all the targets. In the second step, relay nodesselection, additional relay nodes are chosen so as to guaranteesink-connectivity. These steps are explained in the followingsections.

   1. Sensor Nodes Selection

      In this phase a set of efficient sensing nodes is selected tocover all the targets in the field. Since this problem is NP-complete a distributed greedy heuristic

      approach is used to address it. we start from selecting sensors with more targets in theirsensing area and more residual energy as sensing nodes and they keep doing it until covering all the targets. To make thisheuristic distributed, each sensor node computes a waiting timebased on its residual energy and the number of uncovered targets it can cover. We use these waiting times to selectsensing nodes in increasing order of their priority. The sensorthat covers more uncovered targets and has more residualenergy will get less waiting time, and thus more priority thanother sensors. The waiting time of a sensor su is computedby the equation (1):

      Tu=(1-*Eu/E*|TargetSu|/M)*W1-Tu(1)

      Where:

      • Eu: the residual energy of sensor su

      • E: the initial energy of sensors

      • M: the number of targets in the network

      • W1: the maximum waiting time

      • ,: weights which are assigned to the residual energy and the number of uncovered targets

      • TargetSu: Targets which are in sensing range of node su and have not been covered by any sensor node yet

      • Tu: the waiting time which sensor su has passed

      When the waiting time of a sensor su is finished, it isselected as a sensing node and it acts as the supervisor ofall the targets in the set TargetSu. The supervisor of a targetis the first sensor that passed its waiting time and covers it.Next, this sensor broadcasts a notification message to informits neighbors about the targets covered by it.When a sensor passing its waiting time receives a notification message from its neighbours, it updates its waiting time and the set TargetSu if it has at least one target within itssensing range in common with the targets mentioned in themessage. Assuming that RS is the sensors sensing rangeand RC is the sensorscommunication range, the maximumdistance between two sensors with a common target in theirsensing range is 2RS, if RS<2RC. Therefore, it is adequateto broadcast the notification message in two hops.

      The basic difference between the proposed method forsensing nodes selection and the Cardei method is that in theformer the elapsed waiting time of a sensor is not consideredin re-computation of the waiting time when it receives anotification message. As a result, sensors with a high numberof targets in common with other sensors must update theirwaiting time many times, so their priority decreases and theirwaiting time increases each time, regardless of the time thatpassed up until now.

   2. VST and MSR mechanism based on relay nodes

      After selecting sensing nodes and covering all the targets,relay nodes must be selected to provide sink- connectivity. We suppose here that each sensor knows the location of the sinkand all the targets.Achieving sink- connectivity, each selected sensing node sumakes a virtual tree based on the set of targets and the sink.Unlike the Cardei method, which uses Prims algorithm toconstruct a

      virtual minimum spanning tree, a modifiedversion of robust spanning tree is used in order to make authors approach robust against failure of nodes. In this spanning tree, which they call a virtual spanning tree (VST), the rootis the sink and other vertices are targets. This tree serves as avirtual skeleton for the considered network. In order to convertthis virtual tree to a physical tree of sensors, each sensing nodebroadcasts a message to find the supervisor of the target whichis the parent of its covered target.

      The VST algorithm is similar to Prims algorithm, butrather than using the edges length (edges cost) for choosingan edge, it uses a combination of the edges length and thevertexs depth (hop count). Here, we assume that the edgeslength is Euclidean distance between connecting points. In thisalgorithm, cost is computed as follows:

      Cost=*hop count+(1-)*weight of pathi(2)

      whereis a function of the depth of a vertex:

      i= 1- hi/i (3)

      weight of pathi = weight of athj + zi,j (4)

      Descriptions of notations are as follows:

      • hop count: number of hops to the sink.

      • Weight of pathi: sum of the edges cost which connect vertex i to the sink

      • 1:depth of the MST (maximum hop count)

      • hi : depth of vertex i

      • zi,j: length of edge (i,j)

        In relay node selections, authors first construct a MST basedon the set of targets and the sink, using the Prims algorithm, and they set 1 to the depth of this tree. Subsequently, cost iscomputed for each vertex and for the edges which connect itto a vertex of the tree according to equation (2). The vertexconnected to the edge with the minimum cost is selected andadded along with this edge to the tree.

        The closer a vertex is to the sink, the greater it will have.Therefore, the edges length has a greater effect on computingthe edges cost. As a result, vertices nearer to the sink willdirectly connect to it yielding a fat tree around the sink. Onthe other hand, vertices farther from the sink will have morechoices to connect. As a result, the depth of the tree willdecreases. Farther vertices have smaller , so the path weight as more of an effect on their edges cost. Thus, these verticeswill connect to the tree along edges which connect them to the path with the minimum cost.

        Fig.3.2.1: Examples of virtual trees in (a) MST and (b) VST

        Figures 3.2.1(a) and 3.2.1(b) show a MST built with Primsalgorithm and a VST, respectively. Obviously, the depth of the VST is far less than the MST.

        As said before the supervisor of a target is the first sensorthat passed its waiting time and covers it. After constructingthe virtual tree, supervisors of targets must connect togethervia physical paths. Therefore, we have to select some relaynodes to connect the supervisorsof targets. For each target ti,the sensing node su starts the selection of relay nodes along the virtual link (ti, (ti)), where (ti) is the parent of targetti in the virtual tree.

        Every sensing node su broadcasts a control messageRELAY_REQ for each target under its supervision. Thismessage contains the location of sensing node su, destinationtarget (ti), and the maximum distance from sensing nodesu to the supervisor of target (ti). The maximum distanceof two supervisors can be calculated using equation (5). Eachsensor that receives this message computes its distance fromthe source sensor. If this distance is less than the maximumdistance mentioned in the message RELAY_REQ, then itforwards the message.

        Maxdistance = distance(ti,(ti)) + 2RS (5)

        When the supervisor of target (ti) receives the messageRELAY_REQ, it will reply to this message. It will sendthis reply message to the sensing node su, through one of thepathes in which it received the message RELAY_REQ. Thesupervisor of target (ti) can select one of the relay sensorswho delivered the message RELAY_REQ, based on one ofthe following criteria:

        • Relay sensor closest to the node su

        • The first relay node which delivered the message

        • Relay node with the most residual energy

        This procedure will continue until the reply message is delivered to the source sensing node. Consequently, a physical path is built between sensing

        nodes and the sink. All nodes participating in delivering the reply message are chosen as relay nodes.In Figure 3.2.2, virtual trees made by the Cardei method, the VST method, and physical trees built based on them areshown. It can be seen in this figure that the physical tree made based on the VST method, has less depth and more paths tothe sink compared to the physical tree made based on MST. Therefore, in this proposed method, we will have less data losswhen a sensor node fails.

        Fig. 3.2.2.Examples of virtual and physical trees in (a) Cardei and (b) VST

        In equation (4), the cost of connecting vertex (target) i to vertex j as a member of the tree is equal to the sum ofthe length of edge (i, j) and the paths weight from vertexjto the sink. Hence, in addition to the direct effect of depthon equation (2) as hop count, it indirectly affects the pathweight from vertex j to the sink; thus, it has a double effecton this equation. In other words, not only is the vertexsdepth important to vertices near the sink, but also importantto the vertices far from it. Its immediate result is that thevertexs depth has a more important role than the edges lengthin selecting edges. For this reason, in the second proposed method (MSR), for relay nodes selection, they ignore theweight of path from vertex j to the sink and they consider theweight of edge (i, j) as the weight of the path from vertex i to the sink:

        weight of pathi = z(i,j)(6)

        Fig.3.2.3. Examples of virtual and physical trees in (a) MSR and (b) VST

        As shown in Figure 3.2.3, virtual and physical trees made by the MSR method have less depth than trees made by the VST method.

   3. Removal Of Cycle Formation

      Since some of the sensing nodes cover more than one targetand are supervisors of some or all of them, it is possible that while they are converting a virtual tree to a physical tree, cyclesare formed. This happens when a sensing node is a supervisorof more than one target and these targets have different parents.These cycles could have a length greater than or equal to two.

      In Figure 3.3(a), a cycle with a length of two is shown. Sensor2 covers two targets whose parents are different. If this sensorchooses sensor 3 as its parent during the conversion fromvirtual to physical tree, a cycle will be formed between sensors2 and 3.

      Fig.3.3. Forming cycles during converting virtual trees to physical trees

      In order to avoid cycles with length of two, when a sensingnode su, which is supervisor of more than one target, wantsto select sensing node sj as its parent, it must check if it hasreceived any RELAY_REQ message from node sj that itsdestination is node su. Receiving this message means that itis possible that sensing node sj selects sensing node su as itsparent, and in this case, a cycle with a length of two will beformed. For cases with a length more than two, we could usetwo approaches:

      • Using cycle detection algorithms: Sensors covering morethan one target run a cycle detection algorithm. If theydetect a cycle, they choose another sensor as their parent.

      • Packet examination: Sensors send their packets in oneof the existing paths. A returned packet to its sourceindicates that there is a cycle in the network, and thissensor should change its parent.

        Packet examination approach is used in the proposedmethods, since it is more efficient than cycle detection approach.The reason is that the computational cost of cycledetection algorithms is high, which is O(n3), and the probabilityof formation of cycles with length more than two islow.

4. PERFORMANCE

   A set of simulation experiments are used to compare the performance of proposed method withthat of the Cardei method. For this purpose, a simulator in the environment of MATLAB is implemented. Consider a stationary network in which sensor nodes and targets arescattered randomly in a square field 500m × 500m. Othersimulation parameters are as follows:

   • 500 sensors.

   • 50 targets.

   • Sensing energy consumption in a range of 50m is 20mW/s.

   • Communication energy consumption in a range of 80m is 60mW/s.

   For sensing and communication ranges greater than the specified ranges, energy consumption is computed as a squarepower. All sensors are homogeneous, so they have equalsensing and communication range. For each scenario, simulations are executed 200 times and the averageoutputs are shown in charts.

   In the first experiment, the proposed coveragemethod is compared with the Cardei coverage method. In both methods they used the same relay nodes selection scheme, proposed by Cardei. Energy consumption of all the nodes, as show in Figure 4.1, is the sum of energy consumption of sensing nodesand relay nodes. In this figure, the communication range is120m. It can be seen that energy consumption of the proposedcoverage method is less than that of the Cardei coveragemethod.

   Fig.4.1. Effect of sensing range on energy consumption: RC = 120m

   Fig. 4.2.Effect of sensing range on energy consumption: RC = 120m

   The difference between these methods increases byincreasing the sensing range. The reason is that by increasingthe sensing range, the number of common targets covered bydistinct sensors increases.

   In Figure 4.2, the VST and MSR methods are compared against the Cardei method. In this figure the proposedcoverage method is compared with the VST and MSR methods. Since the VST method gives more priority to the depth of thevirtual tree and tries to decrease it, the number of relay nodesand consequently energy consumption of this method is morethan that of others. Finally, as the MSR method gives more importance toenergy consumption during the construction of the virtual tree,where as the VST method, its energy consumption is less.Notice in Figure 4.2 that the energy consumptions of the VST and MSR methods are decreased more than the Cardeimethod by increasing the sensing range. As mentioned before,the reason is that by increasing the sensing range, the effect of proposed coverage method increases.

   Fig. 4.3. Effect of sensing range on the maximum data loss: RC = 120m

   Fig. 4.4.Effect of sensing range on the average data loss: RC = 120m

   In Figures 4.3 and 4.4, the maximum and average data loss of proposed methods are compared with that of the Cardeimethod in a scenario of a single node failure. As expected,the maximum and average amount of data loss in the Cardeimethod is significantly more than the VST and MSR methods, since the Cardei method does not consider the depth of the tree and the number of transmission paths to the sink. Itcan be observed in Figure 4.2 that there are some critical nodesin the Cardei method, which their failure will result in a lossof more than 95% of sensed data.

   Fig. 4.5.Effect of communication range on the maximum data loss: RS

   =70m

   Fig. 4.6.Effect of communication range on the average data loss: Rs = 70m

   Figures 4.5 and 4.6 illustrate the effect of communicationrange on the maximum and average data loss. In these figuresthe slope of all charts is almost zero. This is because that communication range only affects the number of relay nodesand it has no effect on the construction of virtual trees andnumber of transmission paths to the sink. It is clear fromthese figures that the amount of data loss only depends onthe structure of the virtual trees.

   In the next experiment, data loss is divided into 10% slots and the probability of failure is computed which could result in a given percent of data loss. The probability of failure in proposed methods is more than that of the Cardei method, since the number of relay nodes in VST and MSR are greater than that method. Therefore, in the VST and MSR methods, the probability of a failure which causes a low percentage of data loss is more than that of the Cardei method, as shown in Figure 4.7. However, in these methods, the probability of a failure which causes more than 40% data loss is less than that of the Cardei method. In other words, these methods reduce the probability of a high percentage of data loss, but they increase the probability of a low percentage ofdata loss.

   Fig. 4.7.Probability of data loss: RS = 70m and RC = 100m

   The most important parameter in transmission delay is the depth of sensing nodes, which can be used to estimate the transmission delay. Consequently, the average sensing nodes depth of the proposed methods are compared with

   that of theCardei method in Figure 4.8, instead of comparing transmissiondelay. Contrary to the Cardei method, the depth of the nodes is considered in the VST and MSR methods, and as expected, proposed methods have less depth and lesstransmission delay than those of the Cardei method. Sincethe nodes depth has a greater role in the selection of the nodes in the VST method, MSR has more depth than VST. The number of relay nodes decreasesby increasing thecommunication range, and the depth of the tree in all methodsdecreases.In both the proposed coverage method and Cardei coveragemethod, each node uses a linear equation to compute the waitingtime .

   Fig. 4.8.Average depth: RS = 70m

   Therefore, complexities of both coverage methodsare O(c). On the other hand, in Cardei connectivity method,each node runs Prims algorithm to construct a MST. Thus,the complexity of Cardei connectivity method is the same asPrims algorithm, which is O(n3). In the VST and MSR methods, they use Prims algorithm to compute the maximum depth of MST, and then, they run an algorithm similar to Primsalgorithm to construct a spanning tree. The only differencebetween Prims algorithm and the algorithm used here is the way they assign weights to the edges. Therefore, the complexity of the VST and MSR methods are O(n3)+O(n3), whichis equal to O(n3).

5. FUTURE ENHANCEMENT

   Here in this method is VST directly communicates with target nodes and hence it would consume more energy to overcome this we would enhance MSR by first communicating with other nodes and then to communicate with target nodes thereby reducing energy as well decreases no of dead nodes.

6. CONCLUSION

Coverage is one of the most important challenges in the area of wireless sensor networks. Here a point coverage mechanism is proposed inaddition to two connectivity mechanisms. In comparison with existing approaches, the point coverage mechanism needs lesssensing nodes to cover all the targets, and as a result, lessenergy consumption. VST and MSR methods are used to preserve

connectivity. In these mechanisms, inorder to spread out sensed data to the sink from different paths and decreasing the loss of dead nodes, a combination ofdistance of nodes and number of hops are used to select edges and construct the tree. Simulations show that the proposedcoverage method reduces the energy consumption by up to7% compared to the Cardei method. The VST and MSR use more energy than the previous method, but the average packet loss decreases by up to 40%. Moreover, this approachhas less data latency and hence maximizes network lifetime.

REFERENCES

1. I. Cardei and M. Cardei, Energy-efficient connected-coverage in wirelesssensor networks, International Journal of Sensor Networks, Vol.3, No. 3, pp. 201-210, May 2008.

2. M. Cardei and J. Wu, Energy-Efficient Coverage Problems in WirelessAd Hoc Sensor Networks,Computer Communications, Vol. 29, No. 4,pp. 413-420, February, 2006.

3. M. Hefeeda and M. Bagheri, Randomized k-coverage algorithms fordense sensor networks, in Proc. of IEEE INFOCOM: 26th

   IEEEInternational Conference on Computer Communications, Anchorage,AK, United States, pp. 2376-2380, 2007.

4. H. Zhang and J. C. Hou, Maintaining Sensing Coverage and Connectivityin Large Sensor Networks, Ad Hoc and Sensor Wireless Networks,Vol. 1, No. 1-2, pp. 89-124, March 2005.

5. Y. Cai, M. Li, and M. Y. Wu, An area-based collaborative sleepingprotocol for wireless sensor networks, in Proc. of 8th Asia-Pacific WebConference, Harbin, China, pp. 449-460, 2006.

6. M. Cardei and D. Du, Improving wireless sensor network lifetimethrough power aware organization, Wireless Networks, Vol. 11, No.3, pp. 333-340, May 2005.

7. M. Cardei, M. T. Thai, Y. Li, and W. Wu, Energy-efficient targetcoverage in wireless sensor networks, in IEEE INFOCOM 2005,Miami, FL, United states, pp. 1976-1984, 2005.

8. M. Cardei, J. Wu and M. Lu Maximum network lifetime in wirelesssensor networks with adjustable sensing ranges, in Proc. of IEEE International Conference on Wireless and Mobile Computing, Networkingand Communications, (WiMob), pp. 438- 445, 2005.

9. M. Lu, J. W, M. Cardei, and M. Li, Energy-efficient connectedcoverage of discrete targets in wireless sensor networks, International Journal of Ad Hoc and Ubiquitous Computing, Vol. 4, No. 3-4, pp.137-147, 2009.

10. S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M.B. Srivastava,Coverage problems in wireless ad-hoc sensor networks, in Proc.ofIEEE INFOCOM, 2001