移动参考节点动态路径最优规划

张玉强，何泾沙，徐　晶，赵　斌，4，蔡方博

移动参考节点动态路径最优规划

张玉强1，3，何泾沙2，3，徐晶1，3，赵斌2，3，4，蔡方博2，3

（1.北京工业大学计算机学院，北京100124；2.北京工业大学软件学院，北京100124；3.北京市物联网软件与系统工程技术研究中心，北京100124；4.济宁学院计算机科学系，山东济宁273155）

在利用移动参考节点对无线传感器网络进行时间同步或定位的过程中，参考节点的移动路径规划，直接影响节点同步精度、定位精度和能量损耗.将移动节点的移动路径规划转化为对广播点的选取及广播点间路径规划，对应数学模型为经典的选址问题和旅行商问题.通过建立两者的最优联合数学模型，提出利用贪婪算法寻找最优的广播点并获得最优移动路径的方法.仿真结果表明:该路径能够覆盖整个网络，同时缩短参考节点的移动距离.

时间同步；定位；移动参考节点；路径规划；贪婪算法

在移动参考节点的路径规划中，主要涉及2方面因素:节点的同步或定位精度和能量消耗.在现实试验环境中，当传感器节点靠近移动参考节点的规划路径时，节点获得信号较强、干扰少、时间或空间定位精度较高.距离较远时，信号弱、干扰强、时间或空间定位精度较低，甚至无法获得信号.当网络中节点的分布密集靠近参考节点移动的路径时，网络的整体精度较高.否则，精度急剧下降［1］.

根据能量消耗模型［2］，两节点间的通信距离与节点的能耗成平方关系.在通信过程中，为了保障通信质量，移动参考节点和普通节点间需要进行数据交换.节点在响应参考节点信息时，随节点离移动参考节点间的距离的增大，能量损耗成平方比例增大.因此，在网络的同步或节点的定位过程中，节点的通信能耗与移动参考节点间的距离关系密切，距离越短，整个网络的能量消耗越小.否则，网络能耗越大.

目前，对移动参考节点路径的规划分为静态路径规划和动态路径规划2种方式.静态路径规划是预先设定移动曲线，移动参考节点沿此曲线移动.不考虑网络中节点的分布以及节点是否有效，移动参考节点都按照预先规划的路径进行移动，且不会发生改变.其中文献［3］提出Scan型、Double Scan型和H ILBERT型等3种移动路径.文献［4］提出移动参考节点的圆形和S形移动路径方法.文献［5］提出参考节点的等距螺旋形轨迹移动路径方法.文献［6］中LTS-MB算法提出参考节点采用正弦曲线进行移动的方法.

动态路径规划是根据节点的分布以及节点是否有效等情况，动态调整移动路径的方法.为移动参考节点进行动态路径规划的研究现在较少.在AHLoS算法［7］中提出了一种动态路径规划，首先提出在区域中选取移动参考经过“最优节点”，类似本文中的广播点，继而利用旅行商问题建立最短距离的最优数学模型.但是此算法没有对广播点进行最优规划，因而最终的路径不一定最优.

本文提出一种移动参考节点的动态路径规划方法（dynamic path planning method for mobile reference nodes，DP-MRN）.本文要求移动参考节点首先采用MRN-CS算法［8］，进行静态路径规划.参考节点移动一个周期后，搜集到整个网络区域中的节点分布，继而移动参考节点进行动态路径规划.DP-MRN算法将路径规划问题转化为联合选址问题和旅行商问题的最优数学规划模型，最后利用贪婪算法进行路径规划.

1　广播点的最优选取模型

对移动参考节点的路径规划，本文首先建立广播点的最优选取模型.

假设目标区域的传感器节点集合为 T=｛1，2，…，M｝，传感器节点i和j之间的距离为di，j，所有传感器节点（包括参考节点）的通信半径为r，建立如下广播点的最优选取模型（optimal acquisition point，OAP）.

式中决策变量xi和yi，j均为0～1变量.当xi取值为1，表示将选取传感器节点i位置作为广播点位置；否则，将不选取传感器节点i位置作为广播点位置.当yi，j取值为1，表示将在位置i处与传感器节点j进行通信；否则，将不在位置i处与传感器节点j进行通信.

该模型的目标在于使广播点总个数最小化.第1个约束要求只能在选取的广播点处与附件的传感器通信.第2个约束要求在一个移动周期内与任意传感器只需要进行一次通信即可.第3个约束要求进行通信时，必须满足通信距离限制，即只有在通信半径的节点才能通信.

广播点最优选取模型是一个包含不超过M2+ M个变量以及M2+M个约束的0～1线性规划问题，该问题可以采用CPLEX或Matlab等优化软件进行有效求解.

该模型的计算量较大，不适合能量有限的传感器节点进行运算；可以利用具有较强的处理能力的后台服务器，有效地计算出最优广播点坐标，然后传送给移动参考节点.

2　联合广播点选取-最短路径规划模型

广播点最优选取模型（1）中，以最小化广播点总个数为目标函数，并未考虑参考节点的移动路径最优化问题.为此，进一步提出了考虑参考节点的最短移动路径的联合广播点选取-最短路径规划模型.

2.1联合路径规划模型

为建立联合广播点选取-最短路径规划模型，首先考虑不同广播点对最短路径规划的影响.

如果将传感器节点i位置和传感器节点j位置选取为广播点，那么其距离di，j将会出现在最优路径规划问题中，为此需要考虑所选取广播点相互之间距离对最终最优路径的影响.

定义新的决策变量zi，j=xixj，用来表示是否同时将传感器节点i位置和传感器节点j位置都选取为广播点.从而建立如下数学模型.

模型（2）中包含二次乘积项，其求解非常困难.为此首先对二次乘积项的取值进行分析.

表1　二次乘积项zi，j的分析Table 1　Analysis of the secondary product items

由此可知，通过引入如下约束进行等价转化

该约束保证当xi和xj同时为1时，即传感器节点i位置选为广播点，同时传感器节点j位置也选为广播点；zi，j不小于1；否则zi，j不小于0.考虑目标函数为最小化加权的zi，j的和，从而通过引入该约束可以将模型（3）等价转化为如下考虑路径规划的最优广播点选取模型（routing based optimal acquisition point，ROAP）.

2.2路径规划最优广播点选取模型

模型（4）为0～1线性规划问题，该问题可以采用CPLEX或Matlab等优化软件进行有效求解.

考虑到在最终的最优路径规划中往往只包含那些较短的距离，可以引入加权变换的距离来重新建立模型（4）.具体而言，引入如下加权函数w:R+→R+，其满足如下性质:

1）单调性:当d1≥d2时，

2）边际递减:即随着自变量的增大，w的导数逐渐变小，即w为凹函数.

w满足以上性质可以保证当距离较大时，其映射后的惩罚仍较大，同时随着距离的增大，其惩罚效应逐渐减小（因为较大的距离往往不会出现在最终的最短路径中，所以其影响应该不会增大）.w可以选为开根号函数，例如w=等.

2.3加权模型

基于加权距离的方法，可以得到如下模型:

同时，也可以综合考虑最小广播点和最优路径，建立加权模型

式中θ为0～1的正实数.

3　仿真实验

为了验证联合广播点选取-最短路径规划模型（简称联合算法）的优越性，与 LTS-MB算法和MRN-CS算法进行路径对比实验，仿真条件设置如表2所示.

表2　实验参数设置Table 2　Experimental parameters

联合算法采用贪婪算法，部分关键程序如下: while（Leftnum＞0）%寻找当前最多覆盖的节点

for i=1:datanum

Covernum（i）=0；

for j=1:datanum

Covernum（i）=Covernum（i）+Index（i，j）；

end

end

［maxcovernum，index］=max（Covernum）；%计算得到最多覆盖节点的覆盖数量和下标

Referencenumber=Referencenumber+1；%更新采样点数目

Referencepoint（Referencenumber）=index；%存储采样点下标

Leftnum=Leftnum-maxcovernum；%更新剩余节点数目

for j=1:datanum

if（Index（index，j）==1）%如果第j个节点可以被index节点覆盖

for k=1:datanum

Index（k，j）=0；%那么其他任意节点对该节点的覆盖都没有意义，从而可以设为0.

end

end

Index（index，j）=0；%从数据中删去已选取的采样点的覆盖信息，从而下次循环不会再重新选择其为采样点

end

end

MRN-CS算法中参考节点的移动路径如图2所示.

可见，移动参考节点的路径形成了一个闭合曲线.移动参考节点在两同步点间移动的距离为R.移动过程中经过所有的同步点，同时有且经过1次.

LTS-MB算法的移动路径如图3所示.

联合算法的参考节点的移动路径如图4所示.

从图4中可以看出，区域中有2个广播点之间的路径最长，这2个广播点是路径规划的起点和终点.联合算法的数学模型实质上是选址问题和起止点相同的旅行商问题的综合模型.首先利用贪婪算法最优的选取广播点，继而选取最短的2个广播点中的一个为起点，继而通过贪婪算法寻找最短的广播点，这造成了终点可能是距离起点最远的广播点.

假若不要求移动路径是起止点相同的闭合曲线，那么图4的最长线段可以去掉，此时的路径将是动态规划的最短路径，否则将为最优路径.继续上述假设，移动路径起止点不相同时，处于路径中心广播点附近的普通节点的同步周期等于移动周期，处在起止广播点附近的普通节点同步周期最长等于2倍的移动周期，最短为零.这将使得网络中节点时钟偏移可能增大1倍，这将背离研究目的.

通过3种算法的实验得到各自的路径规划长度，结果如图5所示.

从图5中可以看出，联合算法路径长度最小. LTS-MB算法要求参考节点对网络中的节点进行3次覆盖，所以路径最长.MRN-CS算法因为采用覆盖圆的内正六边形，使用1次覆盖，路径长度居中.在小规模网络，以及网络中“空洞”较少时，该联合算法优势不明显，以致路径规划所产生的同步精度与所付出的代价不相符.

4　结论

1）针对静态路径规划的不足，提出移动参考节点的动态移动路径最优规划方案.

2）通过结合经典的选址问题和旅行商问题，建立广播点的最优选取模型、联合广播点选取-最短路径规划模型以及改进后的加权模型，利用贪婪算法寻找最优的广播点，最终得到移动参考节点的最优移动路径.

3）通过仿真实验显示，最优移动路径不仅有效覆盖整个网络，同时缩短了参考节点的移动距离.

［1］郑国强，李建东，周志立.多跳无线传感器网络的高能效数据收集协议［J］.软件学报，2010，21（9）:2320-2337.

ZHENG G Q，LI J D，ZHOU Z L.Energy-efficient data gathering protocol for multihop wireless sensor networks［J］.Journal of Software，2010，21（9）:2320-2337.（in Chinese）

［2］徐朝农，徐勇军，李晓维.无线传感器网络时间同步新技术［J］.计算机研究与发展，2015，45（1）:138-145.

XU C N，XU Y J，LI X W.New time synchronization techniques for wireless sensor networks［J］.Journal of Computer Research and Development，2015，45（1）:138-145.（in Chinese）

［3］ELSON J，GIROD L，ESTRIN D.Fine-grained network time synchronization using reference broadcasts［J］.ACM SIGOPS Operating Systems Review，2002，36（SI）:147-163.

［4］GANERIWAL S，KUMARR，SRIVASTAVAMB. Timing-syncprotocolforsensornetworks［C］∥Proceedingsofthe1stinternationalconferenceon Embedded networked sensor systems.Los Angeles:ACM，2003:138-149.

［5］PING S.Delay measurement time synchronization for wireless sensor networks［R］.［s.l.］:Intel Research Berkeley Lab，2003.

［6］SICHITIU M L，VEERARITTIPHAN C.Simple，accurate time synchronization for wireless sensor networks［C］∥Wireless Communications and Networking.New Orleans: IEEE，2003，2:1266-1273.

［7］MAR譫TI M，KUSY B，SIMON G，et al.The flooding time synchronization protocol［C］∥Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.New York:ACM，2004:39-49.

［8］张玉强，何泾沙，徐晶，等.基于移动参考节点的无线传感器时钟同步方法［J］.通信学报，2015，36（11）: 171-180.

ZHANG Y Q，HE J S，XU J，et al.Time synchronization method for wireless sensor networks based on mobile reference nodes［J］.Journal of Communications，2015，36（11）:171-180.（in Chinese）

（责任编辑杨开英）

Dynamic Optimal Planning of Path of Mobile Nodes

ZHANG Yuqiang1，3，HE Jingsha2，3，XU Jing1，3，ZHAO Bin2，3，4，CAI Fangbo2，3
（1.College of Computer Science，Beijing University of Technology，Beijing 100124，China；2.School of Software Engineering，Beijing University of Technology，Beijing 100124，China；3.Beijing Engineering Research Center for IOT Software and Systems，Beijing 1000124，China；4.Department of Computer Science，Jining University，Jining 273155，Shandong，China）

In the process of time synchronization and location of wireless sensor networks based on mobile reference nodes，the path planning of the reference node directly affects the accuracy and energy loss of the nodes.This paper transforms the path planning of mobile nodes into the selection of broadcast points with the path planning，and sets up a mathematical model based on the problem of location and traveling salesman problem.By establishing the optimal joint mathematical model，a method that uses a greedy algorithm was proposed to find the optimal broadcast point and obtain the optimal path.The simulation experiments were done to validate the performance of the method.Experimental data shows that the mobile path witch through this method can cover the whole network，and significantly shorten the moving distance of the reference node.

time synchronization；localization；mobile reference node；path planning；greedy algorithm

TP 393

A

0254-0037（2016）06-0851-05

10.11936/bjutxb2015070087

2015-07-16

国家“863”计划资助项目（2015AA017204）；北京市自然科学基金资助项目（4142008）

张玉强（1982—），男，博士研究生，主要从事无线传感器网络、信息安全方面的研究，E-mail:yuqzhang@emails. bjut.edu.cn

何泾沙（1961—），男，教授，博士生导师，主要从事无线传感网技术、信息安全方面的研究，E-mail:jhe@bjut. edu.cn