Efficient gathering of correlated data in sensor networks
Efficient gathering of correlated data in sensor networks
复制标题
DOI：
10.1145/1062689.1062739
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
Himanshu Gupta;Vishnu Navda;Samir R Das;Vishal Chowdhary
中科院分区：
文献类型：
--
作者：
Himanshu Gupta;Vishnu Navda;Samir R Das;Vishal Chowdhary
在本文中，我们设计了一种技术，利用传感器数据中的数据相关性来最小化传感器网络中数据收集过程中产生的通信成本(因此，能量成本)。我们提出的方法是选择一小部分传感器节点，这些节点可能足以重建整个传感器网络的数据。然后，在数据收集过程中，只需要将选定的传感器参与通信。还必须连接所选的一组传感器，因为它们需要将数据转发到数据收集节点。我们将传感器集合的选择问题定义为连通相关支配集问题，并根据适当定义的关联结构来描述传感器网络中的一般数据相关性，提出了一套能量高效的分布式算法和竞争集中式启发式算法来选择规模较小的连通相关支配集。所设计的分布式算法可以在异步通信模型中实现，并且能够容忍消息丢失。我们还设计了一个指数(但非穷举)集中逼近算法，它能在O(Logn)内返回最优解。在近似算法的基础上，我们设计了一类高效的集中式启发式算法，并通过实验证明这些启发式算法能够返回近似最优解。在随机生成的传感器网络上使用人工和自然生成的数据集进行的仿真结果证明了所设计的算法的有效性和我们的技术的可行性--即使在动态条件下也是如此。
In this paper, we design techniques that exploit data correlations in sensor data to minimize communication costs (and hence, energy costs) incurred during data gathering in a sensor network. Our proposed approach is to select a small subset of sensor nodes that may be sufficient to reconstruct data for the entire sensor network. Then, during data gathering only the selected sensors need to be involved in communication. The selected set of sensors must also be connected, since they need to relay data to the data-gathering node. We define the problem of selecting such a set of sensors as the connected correlation-dominating set problem, and formulate it in terms of an appropriately defined correlation structure that captures general data correlations in a sensor network.We develop a set of energy-efficient distributed algorithms and competitive centralized heuristics to select a connected correlation-dominating set of small size. The designed distributed algorithms can be implemented in an asynchronous communication model, and can tolerate message losses. We also design an exponential (but non-exhaustive) centralized approximation algorithm that returns a solution within O(log n) of the optimal size. Based on the approximation algorithm, we design a class of efficient centralized heuristics that are empirically shown to return near-optimal solutions. Simulation results over randomly generated sensor networks with both artificially and naturally generated data sets demonstrate the efficiency of the designed algorithms and the viability of our technique -- even in dynamic conditions.