Abstract: To further reduce the energy consumption of Wireless Sensor Network (WSN) strong k-barrier coverage for crossing behavior detection, the minimum energy consumption of strong k-barrier coverage was proved to be NP-hard firstly, and then a heuristic algorithm named HARPN which could adjust the sensing power of nodes was proposed. In HARPN, four rules of computing node's sensing radius were put forward according to the distance between wireless nodes in barriers and the state of the preorder nodes, and then sensing power of nodes was determined based on the size of node's sensing radius. On the premise that sensing barriers must be connected, the energy consumption of overall barriers should be reduced as much as possible. The theoretical analysis and simulations show that the adaptability and stability of HARPN are stronger than the others, and its average energy consumption is about 62% of Heuristic-2's under the same network conditions of barrier fluctuation, which means the network lifetime is prolonged.

Key words: Wireless Sensor Network (WSN), strong k-barrier coverage, NP-hard, heuristic algorithm, energy-efficiency

摘要： 为了进一步降低监测穿越行为的无线传感器网络强k-栅栏覆盖的能耗，首先证明了强k-栅栏覆盖最小能耗问题是NP难的，进而提出了一个节点感知功率可调的启发式节能算法HARPN。该算法根据栅栏中相邻节点的间距和前向节点的状态制定了4种节点感知半径的计算规则，再根据节点感知半径的大小确定节点的感知功率等级，在保证传感栅栏贯通的前提下，尽可能降低栅栏整体的能耗。理论分析和仿真实验表明，在相同的栅栏波动条件下，HARPN算法的适应性和稳定性更强，网络平均能耗约为Heuristic-2算法的62%，网络的生存期进一步延长。

关键词: 无线传感器网络, 强k-栅栏覆盖, NP难, 启发式算法, 节能