刘香爱，冯烟利

（1.山东师范大学 信息科学与工程学院，山东 济南250014；2.山东工商学院 计算机科学与技术学院，山东 烟台264005）

0 引 言

覆盖 问题是无线 传 感 器 网 络（wireless sensor networks，WSN）的基本问题。它反映了WSN对被监测区域或目标提供的感知服务能力。无线传感器网络在部署传感器时通常采用随机部署方式，所以覆盖空洞的出现是避免不了的。这会使网络的生存时间提前结束，网络中会遗留大量未被利用的能量资源。所以，在保持网络原有覆盖水平的基础上，有效地节能对传感器网络来说是非常重要的［1－6］。

在无线传感器网络中，覆盖问题的最终目的是在不降低原有覆盖水平的基础上，有效分配各节点的状态，最小化网络每轮的能量消耗，同时使每个节点平均分担网络能耗［7］。所以在移动传感器修复覆盖空洞时，确定了移动传感器的最后位置之后我们需要决定怎样把传感器移动到目标位置才能达到更好的网络覆盖效果。文献 ［9］中基本竞标协议采用直接移动（direct movement，DM）的方式，但它一般达不到网络的应用需求，浪费更多的时间，过度消耗单个传感器的能量。在文献 ［11］中提出用级联移动（cascaded movement，CM）来优化这个问题。文中详细讲述了选择中间级联节点的方法，但在选择级联移动路径时，只考虑了路径的总能耗，不能更好的均衡每个移动传感器的能耗。怎么确定最优的级联移动路径是一个值得考虑的问题。最优的级联移动路径既要平衡各传感器的能量消耗，又要减少路径的总能耗。……