Connected Sensor Cover Self-Organization of Sensor Networks for Efficient Query Execution(7)

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

Figure2:Subelements and Valid Subelements. that gathers temperature samples in a geographical region monitored by a sensor network.Now,due to the spatial na-ture of temperature,temperature values at any two points that are less than d distance apart may be highly correlated. In such a case,we can again de?ne sensing regions of circular radius d around each sensor.

As discussed above,typically,we can determine the sens-ing region for each sensor either as a static approximation of the sensor’s location and capabilities,or as a function of query’s resolution,or application’s con?dence requirements. The concept of sensing region similar to ours has been used in recent research,for example,by Slijepcevic and Potkon-jak in[25],which addresses a closely related problem,and more recently,by Shakkottai et al.in[24].

If the sensing region is not known a priori,we can solve the connected sensor coverage problem iteratively for increasing sensing regions and pick the minimum solution whose gath-ered data is su?ciently accurate in comparison with the collective data of all the sensors.Otherwise,without the assumption of sensing regions,the connected sensor cover-age problem could be formulated as a problem of selecting a minimum connected set of sensors such that every point in the query region gets a minimum amount of“exposure”from the selected set of sensors.Such a concept of exposure has been de?ned in[22]albeit in a di?erent context.

In our treatment,the sensing regions can take any convex shape.The convexity assumption is needed to make Obser-vation1(de?ned later).The convexity assumption will be true in practice,unless there are impregnable obstacles in the sensor network region.For ease of presentation,we have shown circular sensing regions in the?gures throughout this article.

3.CENTRALIZED APPROXIMATION AL-

GORITHM

In this section,we present the approximation algorithm for the connected sensor coverage problem.The algorithm runs in polynomial time and guarantees a solution whose size is within O(r log n)of the optimal,where r is the link radius of the sensor network and is de?ned later.One of the important features of our algorithm is that it can be easily transformed into a distributed version that has low communication overhead.

De?nition3.(Subelement;Valid Subelements)Con-sider a geographic region with a number of sensing regions.

A subelement is a set of points.Two points belong to same subelement i?they are covered by the same set of sensing regions.In other words,a subelement is a minimal region that is formed by an intersection of a number of sensing re-gions.Given a query region R Q,a subelement is valid if its region intersects with R Q.

In Figure2,where R Q is the given query region,there are fourteen subelements numbered1to14,of which only1to 11are valid subelements.2 Algorithm Description:We designed a greedy algorithm to select a connected sensor cover of near-optimal size.In short,the greedy algorithm works by selecting,at each stage, a path(communication path)of sensors that connects an already selected sensor to a partially covered sensor.The selected path is then added to the already selected sensors at that stage.The algorithm terminates when the selected set of sensors completely cover the given query region.

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科Connected Sensor Cover Self-Organization of Sensor Networks for Efficient Query Execution(7)全文阅读和word下载服务。