Abstract: Aiming at the critical areas coverage NP-complete problem in Wireless Sensor Networks(WSN), this paper proposes a Critical Areas Coverage Heuristic Optimization(CACHO) algorithm. Based on unit disk graph communication model, this algorithm describes the problem of critical areas coverage, and assigns different weight for critical grid points and common grid points to create graph of sensing filed and terminal set and form critical areas coverage grids set with minimal number. Comparison results with an existed coverage algorithm named NPCC prove that CACHO algorithm deploys fewer sensors and can fully cover critical areas.

Key words: Wireless Sensor Networks(WSN), critical area, coverage, heuristic algorithm

摘要： 针对无线传感器网络关键区域覆盖NP完全问题，提出一种关键区域覆盖启发式优化(CACHO)算法。该算法基于单位圆通信模型对关键区域覆盖问题进行描述，为关键区域格点与一般区域格点分配不同权值，以创建感知区域图和终端集合，形成具有最少数量的关键区域覆盖格点集合。与现有覆盖算法NPCC的比较结果表明，CACHO算法放置的传感器数量较少，能完全覆盖关键区域。

关键词: 无线传感器网络, 关键区域, 覆盖, 启发式算法

CLC Number: 

• TP302