WSNs巡航覆盖中基于合力势场的移动策略比较*

张红艳, 张振亚, 谢陈磊

(安徽建筑大学 智能建筑与建筑节能安徽省重点实验室，安徽 合肥 230601)

0 引 言

无线传感器网络(WSNs)[1～3]应用于建筑能效状态监测时，监测区域信息采集过程有两个显著特点[4]:兴趣点位置和其邻近节点在空间上不连续;兴趣点不需要实时地收集信息。当无线传感器网络需要监测建筑能效状态时，所有兴趣点位置都需要被无线传感器节点覆盖用于获取所有有用的信息参数，且无线传感器网络覆盖技术[5～8]可以用于每个兴趣点位置的全覆盖。事实上，在能效监测过程中并不是所有的兴趣点的信息都需要被实时采集，同时不是所有监测区域在任何位置的信息都需要采集。由于以上提到的这两个新特点，使用地毯覆盖[9]或者栅栏覆盖[10]采集建筑能效监测所需的信息，必然面临着因构建无线传感器网络的部署浪费而造成的尴尬局面。

利用无线传感器网络构建能效状态监测过程时，移动节点[11,12]可以用于在适时的时间内采集所需信息。由于使用了移动节点，传感器节点的数目可以明显降低，传感器网络的复杂性也相应降低。同时，移动节点的使用大大提高了无线传感器网络的灵活性，可用于应对一些突发事件。由于移动节点硬件和维护成本高，因此在移动节点的数量和移动性能已知的前提下，有必要为每个移动节点规划一个合理的移动路径。本文使用势场[13，14]实现了移动节点移动路径的规划，利用移动节点与兴趣点之间的相互作用力与磁相互作用的“同极相斥、异极相吸”的原理，从两种角度构建合力势场。

1 无线传感器网络巡航覆盖

设Ω⊆R2为监测区域，Pi∈Ω为兴趣点，即移动传感器节点(简称移动节点)需部署在其周围，感知其目标信息的位置点，其中i=1,2,…，n。若传感器sj部署在兴趣点Pi处，则Pi被sj覆盖。如果每个兴趣点Pi附近目标信息需要周期性的采集，且一次信息采集过程的执行应在每个T时刻前完成，T被称为Pi的最大访问期限。由于P={P1,P2,…,Pn}中Pi的信息不需要连续采集，一个移动节点可以在其最大访问期限之前移动到Pi处完成对其的信息采集即可。

设P={Pi∈Ω⊆R2,i=1,2,…，n}为兴趣点集，T为相对应于兴趣点集P的最大访问期限，Pj1,Pj2，…，Pjs为第j个移动节点在T前访问兴趣点的访问序列，且Pjk≠Pj(k+1)，其中k=1,2，…，s-1，则〈Pj1,Pj2，…，Pjs〉是第j个移动节点在时刻T前的移动路径。每个兴趣点被移动节点覆盖的过程即为所有兴趣点的信息采集过程。特别地，如果对任意移动节点sj，Pj1=Pjs，那么可认为所有兴趣点在最大访问期限前完成被移动节点覆盖的一次有效巡航覆盖。

鉴于移动节点的移动性能限制与兴趣点离散特性，为了有效完成无线传感器网络的巡航覆盖，在无线传感器网络中的移动节点的数目通常大于1，且所有兴趣点都可以被巡航覆盖中移动节点定期访问。为了保证巡航覆盖的有效性，移动节点的移动、信息收集和其他辅助动作等行为应保证在一定成本范围内。因此需要对移动节点的移动路径进行规划。

2 基于合力势场的移动传感器节点移动策略

在无线传感器网络巡航覆盖中，目标位置不确定，因此，机器人和多智能体领域中用于路径规划的势场并不能直接的应用于无线传感器网络巡航覆盖中。

2.1 势场定义

在无线传感器网络巡航覆盖中，移动节点与兴趣点之间存在吸引力，使得移动节点可以往兴趣点的位置移动。相应地，移动节点与移动节点之间存在排斥力。由于移动节点之间斥力的存在使得移动节点在移动的过程中就会避免发生碰撞。这种吸引力和排斥力可以参照磁相互作用，吸引力与兴趣点的访问期限和当前时间的之间差值有关，差值定义为兴趣点的紧急等级。紧急等级值越小，引力越大。因此将巡航覆盖中兴趣点的紧急等级与磁化强度对应。排斥力与与移动节点之间的距离密切相关，当距离较小时，排斥力就迅速增大，以达到避免碰撞的目的。

设P为所有兴趣点集，S={s1,s2,…,sm}为所有移动节点集,Mmax为所有兴趣点的最大磁化强度，Ti为兴趣点Pi的访问期限，Δt为移动节点运行时间，兴趣点Pi的磁化强度为MPi=Mmax·exp((Δt-Ti)/Ti)，表面积为APi。若对于∀i∈Z+，1≤i≤n，有APi=AP。移动节点sj的磁化强度为Msj，表面积为Asj，对于∀j∈Z+，1≤j≤m，有Msj=Ms，Asj=As，则第k个移动节点sk处的第j个移动节点sj所受斥力为

(1)

第j个移动节点sj受到来自第i个兴趣点Pi的引力为

(2)

假定Mmax已知，APi和ASj为确定值，且移动节点的移动速度一定，由式(1)和式(2)可知，移动节点之间斥力主要取决于Msj和移动节点之间的距离，而移动节点和兴趣点的引力主要取决于兴趣点的紧急等级和兴趣点与移动节点之间的距离。由于无线传感器网络巡航覆盖应用的特殊性，本文根据从移动节点选择目标和兴趣点选择目标两个角度，分别提出两种策略。

2.2 移动节点角度寻找目标兴趣点的移动策略

当移动节点作为主体，选择下一步移动目标时，把在当前时刻，当前位置对移动节点产生引力最大的某个兴趣点作为目标，也就是作为下一个目标兴趣点进行访问。由于每个移动节点都是一个主体，在选择下一个移动目标并进行移动时可能会产生碰撞，因此，在确定移动目标之后对移动方向的确定也是很有必要的。对每个移动节点来说，首先根据式(1)计算当前移动节点与所有未访问兴趣点之间的引力大小，选择对其引力最大的兴趣点作为下一移动目标，然后根据式(2)计算当前移动节点与在距离影响范围内的其他移动节点之间的斥力，并且计算合力方向，根据合力方向进行访问，直至所有的兴趣点访问完毕。

策略1

输入：所有兴趣点集P={Pi∈Ω⊆R2，i=1,2,…,n},所有未访问兴趣点集P′={Pi∈P}，兴趣点之间距离矩阵D=(dij)n×n，移动节点的个数m，移动传感器移动速度v，移动节点运行时间t(s)，兴趣点的访问期限集T={Ti∈Z,i=1,2,…,n},兴趣点最大磁化强度Mmax，移动节点磁化强度MS，兴趣点表面积AP，移动节点表面积AS，空气中的磁导率μ0。

输出：所有移动节点的移动路径list。

1)t(0)=0;P′=P

2) while(P′)

3) for(i=0;i

4) 计算t(s)

5)以未访问兴趣点集P′为被访问节点，依据式(1)构建移动节点si的引力势场，计算对移动节点si产生引力最大的兴趣点p

6)根据式(2)构建移动节点si的斥力势场，计算对移动节点si产生的合力方向

7)list_add(p);并根据合力方向进行移动

8)P′_delete(p)

9) end for

10)end while

11)输出list

2.3 兴趣点角度寻找合适移动节点的移动策略

从兴趣点角度选择移动节点根据兴趣点紧急等级的角度进行，以每个兴趣点为计算对象，根据式(1)计算兴趣点与所有移动节点之间的引力大小，选出引力最大的移动节点和兴趣点并根据式(2)计算选出的移动节点与在距离影响范围内的其他移动节点之间的斥力，然后计算合力方向，把当前移动兴趣点作为选中移动节点的下一移动目标，并在移动时根据合力方向进行，直至所有兴趣点访问完毕。

策略2

输入：所有兴趣点集P={Pi∈Ω⊆R2,i=1,2,…,n}，所有未访问兴趣点集P′={Pi∈P}，兴趣点之间距离矩阵D=(dij)n×n，移动节点的个数m，移动传感器移动速度v，移动节点运行时间t(s)，兴趣点的访问期限集T={Ti∈Z,i=1,2,…,n},兴趣点最大磁化强度Mmax，移动节点磁化强度MS，兴趣点表面积AP，移动节点表面积AS，空气中的磁导率μ0。

很多学者都在研究高管薪酬激励与技术创新之间的关系，其理论各不相同，但核心基本相似：为获超额利润与竞争优势，企业倾向于高管做技术创新，而高管进行技术创新的程度与企业的薪酬激励相关，因此，提高高管薪酬是企业技术创新的基本手段。技术创新是企业发展的根本，技术创新需要资金等条件的保障。高管是企业发展的关键因素，让高管利益与企业利益进行挂钩，是企业进行技术创新突破的关键。通过薪酬激励，促使高管引领企业技术创新，是保障企业科学发展的重要手段[4]。

输出：所有移动节点的移动路径list。

1)t(0)=0;P′=P

2)while(P′)

3) for(i=0;i

4) 计算t(s)

5)以未访问兴趣点集P′为被访问节点，依据式(1)构建所有未访问兴趣点对每个移动节点的引力势场，计算兴趣点对所有移动节点的引力，得出引力最大所对应的兴趣点p及移动节点si

6)根据式(2)计算当移动节点si把兴趣点p作为下一步移动目标时，si当前所受合力方向d

7)判断是否存在极小值，若存在，则根据图1进行解决，否则,结束

8)list_add(s,p);并沿着方向d进行移动;∥将p加入到s列表中

9)P′_delete(p)

10) end for

11)end while

12)输出list

图1 极小点问题的解决

3 实验结果

为了验证文中提到的基于合力势场的移动策略的有效性及两种角度移动策略的优越性，本文对人工数据进行了仿真实验。在人工数据中，所有兴趣点都是在一个10 m×10 m正方形区域内随机分布的，移动速度均为5 m/min,并设所有移动节点磁化强度相同，同时所有兴趣点的最大访问期限相同。对策略1和策略2分别进行了4次实验，并对实验结果进行分组比较，第一组和第二组实验结果针对移动节点个数为3，兴趣点个数从30～1 000个不等时，分别使用2种策略得到移动路径平均值和完成一次巡航覆盖平均时间的比较，结果如图2所示；第三组和第四组实验结果针对兴趣点个数为1 000，移动节点个数从3～50个不等时，分别使用2种策略得到移动路径平均值和完成一次巡航覆盖平均时间的比较，结果如图3所示。

图2 实验结果(移动节点个数相同、兴趣点个数不同)

图3 实验结果(移动节点个数不同、兴趣点个数不同)

可以看出，针对4组实验，当移动节点的个数相同、兴趣点个数不同时和兴趣点个数相同、移动节点数不同时，使用两种策略的结果比较表明策略2的移动路径平均值比策略1的要短，并且完成一次巡航覆盖所需要的平均时间比策略1用时要少。

4 结束语

本文中提出了基于合力势场的两种移动策略。在基于无线传感器网络巡航覆盖中合力势场的研究基础上，对两种不同角度的移动路径规划进行了比较，即分别从兴趣点选择移动节点的角度和移动节点选择兴趣点的角度规划的路径进行了实验对比，结果表明从兴趣点选择移动节点角度出发的策略在时间和路程上均具有优越性。在后续的研究中考虑使移动节点能够自主学习，在学习上一次巡航访问历史后能够重新规划出更合适的路径是下一步研究的工作。