Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks
Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks
复制标题
无线传感器网络中最大寿命目标覆盖的参数化复杂度
DOI：
10.1016/j.tcs.2013.06.008
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Jianer Chen
中科院分区：
文献类型：
--
作者：
Weizhong Luo;Jianxin Wang;Jiong Guo;Jianer Chen
最大寿命目标覆盖可以被视为一系列问题，其中的任务是将传感器分组并分配其时隙，以便在满足某些覆盖要求的同时最大化覆盖寿命。不幸的是，这些问题是 NP 困难的。为了深入了解复杂性的来源，我们对两种类型的最大生命周期目标覆盖率启动了系统参数化复杂性研究：最大-最小目标覆盖率和最大个体目标覆盖率。我们首先证明，即使在每个目标最多被两个传感器覆盖或每个传感器最多可以覆盖两个目标的特殊情况下，这两个问题仍然是 NP 困难的。相比之下，限制目标数量可以降低所考虑问题的复杂性。换句话说，就“目标数量”参数而言，它们都是固定参数易处理（FPT）的。此外，我们将研究扩展到结构参数“覆盖至少两个目标的传感器数量”。积极的一面是，这两个问题都在 FPT 中关于 tok 的问题。最后，我们表明 FPT 中的最大-最小目标覆盖率相对于组合参数“组数”和“每组覆盖的目标数”。
Max-lifetime Target Coverage can be viewed as a family of problems where the task is to partition the sensors into groups and assign their time-slots such that the coverage lifetime is maximized while satisfying some coverage requirement. Unfortunately, these problems are NP-hard. To gain insight into the source of the complexity, we initiate a systematic parameterized complexity study of two types of Max-lifetime Target Coverage: Max–min Target Coverage and Max-individual Target Coverage. We first prove that both problems remain NP-hard even in the special cases where each target is covered by at most two sensors or each sensor can cover at most two targets. By contrast, restricting the number of targets reduces the complexity of the considered problems. In other words, they are both fixed parameter tractable (FPT) with respect to the parameter “number of targets”. Moreover, we extend our studies to the structural parameter “numberkof sensors covering at least two targets”. Positively, both problems are in FPT with respect tok. Finally, we show that Max–min Target Coverage is in FPT with respect to the combined parameters “number of groups” and “number of targets covered by each group”.
登录
查看更多内容
DOI：
--
发表时间：
1994-03
期刊：
Nord. J. Comput.
影响因子：
--
作者：
J. A. Telle
通讯作者：
J. A. Telle
DOI：
--
发表时间：
2007-01
期刊：
--
影响因子：
--
作者：
Jianer Chen;Songjian Lu;S. Sze;Fenghui Zhang
通讯作者：
Jianer Chen;Songjian Lu;S. Sze;Fenghui Zhang
DOI：
10.1016/j.cosrev.2007.09.001
发表时间：
2007-12
期刊：
Comput. Sci. Rev.
影响因子：
--
作者：
D. Thilikos
通讯作者：
D. Thilikos
影响因子：
3
作者：
Cardei, M;Du, DZ
通讯作者：
Du, DZ
影响因子：
1.8
作者：
M. Cheng;Xuan Gong
通讯作者：
M. Cheng;Xuan Gong