School of Computer Science and Engineering, Changsha University, Changsha 410022, China.
Department of Computer Science and Software Engineering, Swinburne University of Technology, Hawthorn 3122, Australia.
Sensors (Basel). 2023 May 24;23(11):5026. doi: 10.3390/s23115026.
Path coverage attracts many interests in some scenarios, such as object tracing in sensor networks. However, the problem of how to conserve the constrained energy of sensors is rarely considered in existing research. This paper studies two problems in the energy conservation of sensor networks that have not been addressed before. The first problem is called the least movement of nodes on path coverage. It first proves the problem as NP-hard, and then uses curve disjunction to separate each path into some discrete points, and ultimately moves nodes to new positions under some heuristic regulations. The utilized curve disjunction technique makes the proposed mechanism unrestricted by the linear path. The second problem is called the largest lifetime on path coverage. It first separates all nodes into independent partitions by utilizing the method of largest weighted bipartite matching, and then schedules these partitions to cover all paths in the network by turns. We eventually analyze the energy cost of the two proposed mechanisms, and evaluate the effects of some parameters on performance through extensive experiments, respectively.
路径覆盖在某些场景中吸引了很多关注，例如传感器网络中的目标跟踪。然而，在现有研究中很少考虑如何节约传感器的受限能量。本文研究了在传感器网络的节能方面以前没有解决的两个问题。第一个问题称为路径覆盖中的节点最小移动问题。它首先证明了这个问题是 NP 难的，然后使用曲线分离将每条路径分成一些离散的点，并最终根据一些启发式规则将节点移动到新的位置。所使用的曲线分离技术使得所提出的机制不受线性路径的限制。第二个问题称为路径覆盖中的最大寿命问题。它首先通过利用最大加权二分匹配的方法将所有节点分成独立的分区，然后通过轮流的方式为这些分区安排覆盖网络中的所有路径。最后，我们分析了这两个所提出的机制的能量消耗，并通过广泛的实验分别评估了一些参数对性能的影响。
