Connected sensor cover: Self-organization of sensor networks for efficient query execution
Connected sensor cover: Self-organization of sensor networks for efficient query execution
复制标题
DOI：
10.1109/tnet.2005.863478
复制
发表时间：
2006-02-01
影响因子：
3.7
通讯作者：
Gu, QY
中科院分区：
文献类型：
--
作者：
Gupta, H;Zhou, ZH;Gu, QY
空间查询执行是传感器网络的基本功能，其中查询收集特定地理区域内的传感器数据。可以利用传感器网络中的冗余来减少在执行此类查询时产生的通信成本。任何通信成本的降低都将导致电池能量的有效利用，而电池能量在传感器中是非常有限的。减少查询的通信成本的一种方法是将响应查询的网络自组织到一个拓扑中，该拓扑只涉及足以处理查询的一小部分传感器子集。然后只使用构造拓扑中的传感器执行查询。自组织技术对于运行时间足够长的查询是有益的，这样可以平摊自组织中产生的通信成本。在本文中，我们设计并分析了这种传感器网络自组织的算法，以降低能耗。特别是，我们开发了连接传感器覆盖的概念，并设计了一个集中的近似算法，该算法构建了一个涉及近最优连接传感器覆盖的拓扑。我们证明了构造的拓扑的大小在最优大小的O （log n）因子内，其中n为网络大小。我们开发了一个分布式自组织版本的近似算法，并提出了几个优化来减少算法的通信开销。我们还设计了另一种基于节点优先级的分布式算法，该算法具有更低的通信开销，但不能保证所连接的传感器盖的大小。最后，我们使用模拟来评估分布式算法，并表明我们的方法显著降低了通信成本。
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 such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology. The self-organization technique is beneficial for queries that run sufficiently long to amortize the communication cost incurred in self-organization.In this paper, we design and analyze algorithms for suchself-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an O (log n) factor of the optimal size, where n is the network size. We develop a distributed self-organization version of the approximation algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. We also design another distributed algorithm based on node priorities that has a further lower communication overhead, but does not provide any guarantee on the size of the connected sensor cover constructed. Finally, we evaluate the distributed algorithms using simulations and show that our approaches results in significant communication cost reductions.