Lifetime and Coverage Guarantees Through Distributed Coordinate-Free Sensor Activation
Lifetime and Coverage Guarantees Through Distributed Coordinate-Free Sensor Activation
复制标题
DOI：
10.1109/tnet.2010.2077648
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
G. Kasbekar;Yigal Bejerano;S. Sarkar
中科院分区：
文献类型：
--
作者：
G. Kasbekar;Yigal Bejerano;S. Sarkar
在无线传感器网络（WSN）中，大量传感器对目标场进行分布式传感。传感器覆盖是覆盖目标区域的所有传感器集合的子集。网络的生命周期是指从网络开始运行到剩余能量非零的所有传感器集合不再构成传感器覆盖的时间。传感器网络的一个重要目标是设计一个时间表，即在每个时隙激活一系列传感器覆盖物，以便最大限度地延长网络的寿命。在本文中，我们设计了一种多项式时间分布式算法来最大化网络的寿命，并证明其寿命至多比最大可能寿命低一个因子 O(logn * lognB)，其中 n 是传感器的数量，B 是每个传感器初始能量的上限。我们的算法不需要知道节点的位置或方向信息，这在传感器网络中很难获得。每个传感器只需要知道其传输范围内相邻节点之间的距离及其感知半径。在每个时隙中，该算法首先为每个节点分配一个权重，该权重与其迄今为止已用完的初始能量的分数成指数关系。然后，它以分布式方式找到一个 O(logn) 近似最小重量传感器盖，并在插槽中激活它。
In wireless sensor networks (WSNs), a large number of sensors perform distributed sensing of a target field. A sensor cover is a subset of the set of all sensors that covers the target field. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with nonzero remaining energy does not constitute a sensor cover any more. 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(logn * lognB) 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 an O(logn) approximate minimum weight sensor cover, which it activates in the slot.