Connected Sensor Cover Self-Organization of Sensor Networks(10)

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of

102030405060702

3

4

5678

9

N o . o f m e s s a g e s (D ) i n t h o u s a n d s

Transmission radius (t)

n=1600n=2000n=3000n=4000

(a)Communication cost (D )05

101520253035404550552

3

4

56

7

89

T h r e s h o l d v a l u e o f q

Transmission radius (t)

n=1600n=2000n=3000n=4000

(b)Threshold value q θ

Figure 5:The communication cost (D )for the distributed algorithm and the threshold value of q (q θ)shown for various transmission radii and number of sensors.monitored/query area.As only one set of sensors need to be active at any time,their technique results in energy savings while preserving coverage.They only present a centralized algorithm which does not extend easily to a distributed algo-rithm.Moreover,they do not consider the communication cost incurred in the execution of their heuristic or the query.Hence,they do not require the selected sets to be connected.We should note that a repeated execution of our algorithm gives a good heuristic for the problem addressed in their work.In other closely related work,Shakkottai et al.in [24]consider an unreliable sensor grid-network and derive neces-sary and sufficient conditions for the coverage of the region and connectivity of the network in terms of the transmission radius,sensing radius,and failure rate of the sensors.

In [21],the authors formulate coverage problems to ad-dress the quality of service (surveillance)provided by a sen-sor network.In particular,they address the problem of find-ing maximal paths of lowest and highest observabilities in a sensor network,which is very different than our connected sensor coverage problem.The work in [19]addresses the problem of selecting a set of k base stations from a given set of n stations to maximize radio coverage.The issue of connectivity,query execution,or energy-efficiency does not arise in the radio coverage setting.

There has been a significant amount of work on developing efficient mechanisms to broadcast a message in a mobile ad hoc network.The idea here is to suppress redundant broad-casts by using only a small number of nodes to broadcast but ensuring that all the nodes in the network receive the broadcast message.The above described problem of select-ing a minimum number of nodes such that each node in the network is either selected or a neighbor of a selected node is known as the minimum dominating connected set (MDCS)problem [14].The work in wireless network research com-munity [9,18,26,1,7]has primarily focussed on developing energy-efficient distributed algorithms to construct a near-optimal dominating connected set.However,the notion of dominating set is significantly different than that of sensor cover.

Other related problems based on various other notions of coverage are as follows.The Art Gallery Problem [20,10]considers placement of observers in a room such that each point in the room is “seen”by at least one observer.The Art Gallery Problem was solved optimally in 2D and shown to be NP-hard in 3D case.The essential difference of the Art Gallery and the related problems with our connected sensor coverage problem is that the Art Gallery and related prob-lems require an optimal placement of observers,while our problem deals with an optimal selection of already placed sensors.From that perspective,the geometric variations [16,17,5]of the classic set cover problem are more related to our problem.However,none of the geometric set cover variations addressed in the literature deal with the notion of connectivity.For the disk-cover problem [5],there is a poly-nomial algorithm that delivers a constant-factor approxima-tion,however,the approximation algorithm does not gener-alize to other geometric regions (not even rectangles)and due to involved computation required,the straightforward distributed implementation would incur a very large number of messages.

There has been some other work done on optimizing en-ergy consumption in sensor networks.For example,in [6],heuristic techniques have been designed to put sensor net-work nodes in inactive states based on the observed con-nectivity in the network and loss of messages.In [15],a randomized clustering algorithm has been devised to select cluster heads in a sensor network so that the energy budget for relaying information to a gateway is distributed evenly among sensor nodes.None of the above work deals with the notions of spatial coverage or connectivity.

7.CONCLUSIONS

We have designed efficient algorithms for self-organization in sensor networks.The self-organization algorithms exploit the redundancy in the sensor network to select a small subset of sensors (called connected sensor cover )that is sufficient to process a given query.The motivation is to conserve the overall battery power of the network.We show that the