Restricted strip covering and the sensor cover problem
Restricted strip covering and the sensor cover problem
复制标题
DOI：
--
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
A. Buchsbaum;A. Efrat;Shaili Jain;Suresh Venkatasubramanian;Ke Yi
中科院分区：
文献类型：
--
作者：
A. Buchsbaum;A. Efrat;Shaili Jain;Suresh Venkatasubramanian;Ke Yi
假设我们得到一组覆盖某个区域的对象以及与每个对象关联的持续时间。将对象视为作业，我们是否可以安排它们的开始时间以最大化原始区域保持覆盖的时间长度？我们将此问题称为传感器盖问题。它是在用传感器覆盖某个区域的背景下出现的。例如，假设您希望通过放置在各个固定位置的传感器来监视沿栅栏（间隔）的活动。每个传感器都有一个范围（也是一个间隔）和有限的电池寿命。接下来的问题是安排何时打开传感器，以便尽可能长时间地全面监控围栏。这个一维问题涉及实线上的区间。将持续时间与每个矩形相关联会产生一组空间和时间的矩形，每个矩形由一对固定的水平端点和一个高度指定。目标是为每个矩形分配一个底部位置（通过向上或向下移动它们），以便最大化完全覆盖跨越间隔的高度。我们将这个一维问题称为“受限条带覆盖”。如果我们用打包约束替换覆盖约束（矩形可能不重叠，目标是最小化覆盖的最高点），那么问题就变得与动态存储分配相同，这是一个经过充分研究的调度问题，而这又是众所周知的问题 STRIP PACKING 的受限情况。我们提出了一系列限制条带覆盖的算法。我们证明该问题是 NP 难问题，并提出了一种 O(log log log n) 近似算法。我们还针对某些特殊情况提供了更好的近似或精确算法，包括当所有间隔具有相等宽度时。对于一般的传感器覆盖问题，我们区分元素具有统一或可变持续时间的情况。结果取决于要覆盖的区域的结构：我们针对受限条带覆盖的均匀持续时间情况给出了多项式时间的精确算法，但证明了高维区域的均匀持续时间情况是 NP 困难的。我们给出了二维区域的一些更具体的结果。最后，我们考虑任意集合的区域，并针对最一般的情况提出 O(log n) 近似算法。
Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time that the original region remains covered? We call this problem the SENSOR COVER PROBLEM. It arises in the context of covering a region with sensors. For example, suppose you wish to monitor activity along a fence (interval) by sensors placed at various fixed locations. Each sensor has a range (also an interval) and limited battery life. The problem is then to schedule when to turn on the sensors so that the fence is fully monitored for as long as possible. This one-dimensional problem involves intervals on the real line. Associating a duration to each yields a set of rectangles in space and time, each specified by a pair of fixed horizontal endpoints and a height. The objective is to assign a bottom position to each rectangle (by moving them up or down) so as to maximize the height at which the spanning interval is fully covered. We call this one-dimensional problem RESTRICTED STRIP COVERING. If we replace the covering constraint by a packing constraint (rectangles may not overlap, and the goal is to minimize the highest point covered), then the problem becomes identical to DYNAMIC STORAGE ALLOCATION, a well-studied scheduling problem, which is in turn a restricted case of the well known problem STRIP PACKING. We present a collection of algorithms for RESTRICTED STRIP COVERING. We show that the problem is NP-hard and present an O(log log log n)-approximation algorithm. We also present better approximation or exact algorithms for some special cases, including when all intervals have equal width. For the general SENSOR COVER PROBLEM, we distinguish between cases in which elements have uniform or variable durations. The results depend on the structure of the region to be covered: We give a polynomial-time, exact algorithm for the uniform-duration case of RESTRICTED STRIP COVERING but prove that the uniform-duration case for higher-dimensional regions is NP-hard. We give some more specific results for two-dimensional regions. Finally, we consider regions that are arbitrary sets, and we present an O(log n)-approximation algorithm for the most general case.