New optimal solution to disjoint set K-coverage for lifetime extension in wireless sensor networks
New optimal solution to disjoint set K-coverage for lifetime extension in wireless sensor networks
复制标题
用于延长无线传感器网络寿命的不相交集 K 覆盖的新最优解决方案
作者：
M. Ashouri;Zeinab Zali;S. R. Mousavi;M. Hashemi
由于每个传感器的能量有限，延长寿命是无线传感器网络的一个基本问题。在许多应用中，传感器的随机和密集部署在无线传感器网络中造成了一定的覆盖冗余，这促使人们采取措施避免这种冗余，以延长网络的整体生命周期。为此，一种有效的方法是将传感器划分为最大数量的不相交的组，称为盖子，每个组可以覆盖所有目标，因此任何时候都只有一个盖子处于活动状态。求最大覆盖数问题已被证明是NP难问题。本文提出了一种求解该问题的优化方法。该方法将问题转化为著名的布尔可满足性(SAT)问题。仿真结果表明，该方法优于现有的遗传算法(GAMDSC)和启发式算法(MCMCC)。此外，作为一种最优算法，它保证得到最优解，而现有的(元)启发式算法不能保证得到最优解。此外，我们将所提出的方法扩展到K-覆盖问题，其中每个目标被至少K个节点覆盖。
Lifetime extension is a fundamental concern in wireless sensor networks (WSNs) owing to the limited energy of each sensor. Random and dense deployment of sensors in many applications impose some coverage redundancy in WSNs, which motivates methods to avoid such redundancy for extending the overall lifetime of the networks. An effective method for this purpose is to divide the sensors into a maximum number of disjoint groups called covers, each of which can cover all targets, so that only one cover is active at any time. The problem of obtaining the maximum number of covers has been proved to be NP-hard. In this study, an optimal method is proposed for the problem. The proposed method is based on the transformation of the problem into the well-known Boolean satisfiability (SAT) problem. Simulation results indicate that the proposed method is superior to existing genetic (GAMDSC) and heuristic (MCMCC) methods. Moreover, as an optimal algorithm, it guarantees obtaining an optimum solution, whereas the existing (meta)heuristic algorithms do not. In addition, we extend the proposed method to the K-coverage problem, where each target is supposed to be covered by at least K number of nodes.