Lifetime and coverage guarantees through distributed coordinate-free sensor activation
Lifetime and coverage guarantees through distributed coordinate-free sensor activation
复制标题
DOI：
10.1145/1614320.1614339
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
G. Kasbekar;Yigal Bejerano;S. Sarkar
中科院分区：
文献类型：
--
作者：
G. Kasbekar;Yigal Bejerano;S. Sarkar
无线传感器网络是一种新兴的传感技术，具有广泛的军事和民用应用。在这些网络中，大量的传感器执行目标场的分布式感测。每个传感器都是一个小型的电池供电设备，可以在其感测范围内感测感兴趣的事件，并可以与相邻的传感器进行通信。传感器覆盖是所有传感器的集合的子集，使得目标场中的每个点在该子集中的至少$k $个不同传感器的感测范围的内部，其中k是给定的正整数。网络的生命周期是从网络开始运行到剩余能量为非零的所有传感器的集合不构成传感器覆盖的时间。传感器网络的一个重要目标是设计一个时间表，即在每个时隙中激活的传感器覆盖序列，以最大化网络的生命周期。在本文中，我们设计了一个多项式时间，分布式算法最大化的网络的生命周期，并证明其寿命是最多一个因素O（log n * log nB）低于最大可能的寿命，其中n是传感器的数量和B是一个上限的初始能量的每个传感器。我们的算法不需要知道的节点的位置或方向信息，这是很难获得的传感器网络。每个传感器只需要知道其传输范围内相邻节点之间的距离和它们的感知半径。在每个时隙中，该算法首先为每个节点分配一个权重，该权重与其到目前为止已经用完的初始能量的分数呈指数关系。然后，以分布式的方式，它找到一个O（log n）近似的最小重量传感器覆盖，它在插槽中激活。我们的模拟表明，我们的算法大大优于现有的几个生命周期最大化算法。
Wireless Sensor Networks are emerging as a key sensing technology, with diverse military and civilian applications. In these networks, a large number of sensors perform distributed sensing of a target field. Each sensor is a small battery-operated device that can sense events of interest in its sensing range and can communicate with neighboring sensors. A sensor cover is a subset of the set of all sensors such that every point in the target field is in the interior of the sensing ranges of at least $k$ different sensors in the subset, where k is a given positive integer. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with non-zero remaining energy does not constitute a sensor cover. An important goal in sensor networks is to design a schedule, that is, a sequence of sensor covers to activate in every time slot, so as to maximize the lifetime of the network. In this paper, we design a polynomial-time, distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factor O(log n * log nB) lower than the maximum possible lifetime, where n is the number of sensors and B is an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each sensor only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. Then, in a distributed manner, it finds a O(log n) approximate minimum weight sensor cover which it activates in the slot. Our simulations reveal that our algorithm substantially outperforms several existing lifetime maximization algorithms.