无线传感器网络中一种基于“Z”曲线的路径规划方案

谢绍国

（安庆师范大学，安徽安庆 246133）

无线传感器网络中一种基于“Z”曲线的路径规划方案

谢绍国

（安庆师范大学，安徽安庆 246133）

路径规划方案在无线传感器网络的节点部署中有着非常重要的作用。为了克服锚节点共线问题和减少定位时间，在研究已有的移动锚节点路径规划方案的基础上，提出了一种“Z”曲线路径规划方案。仿真实验表明，所提出的“Z”曲线路径规划方案与已有的4种路径规划方案相比，克服了锚节点共线问题，减少了定位时间，提高了节点定位精度。

无线传感器网络；定位误差；接收信号强度指示；路径规划方案

0 引言

无线传感器网络节点定位是当前无线传感器网络研究热点之一[1]。传统的无线传感器网络节点定位是采用静态锚节点进行定位，这会大大增加成本，降低节点部署效率。如果采用移动锚节点的方式进行定位，则可以减少锚节点的数量，从而减少成本，并且提高节点部署效率，减少定位时间。针对移动锚节点的路径规划方案，国内外研究者已提出了一些解决方案。文献[2]调查了无线传感器网络中移动锚节点的路径规划问题。文献[3]提出了一种基于几何公式和批处理移动的无碰撞路径规划机制，解决移动传感器节点部署问题。文献[4]中研究了一种移动锚节点路径规划方案，该方案能够减少定位误差，并保证所有的节点能够确定它们的位置。为了避免直线问题和减少节点能量消耗，文献[5]和[6]提出了一种“Z”曲线的路径规划机制。文献[7]中研究了一种基于无线传感器网络的避障路径规划方法。文献[8]给出了一种基于无线传感器网络的动态路径规划方法。文献[9]分析了基于测距和非测距两种技术方案在无线传感器网络的移动锚节点定位中的性能。文献[10]研究了一种三维基于虚拟力的移动锚节点的动态路径规划方法。为解决移动锚节点的路径规划问题，文献[11]提出了一种宽度优先和回溯式贪婪算法，该算法把路径规划问题转化为图的生成树及遍历问题。大部分的路径规划方案存在着锚节点共线问题，从而使得节点定位精度不高。针对锚节点共线问题和减少定位时间，本文提出了一种改进的“Z”曲线的路径规划方案。

1 路径规划方案

1.1“Z”曲线路径规划方案

针对移动锚节点的路径规划，我们提出了“Z”曲线路径规划方案，所有节点都部署在一个二维空间内。设计“Z”曲线路径规划方案的关键目的是“Z”曲线路径规划方案能够克服锚节点共线的问题；同时为了减少定位时间，移动锚节点发送三个连续的非共线锚节点坐标信息并创建一条最优路径。如果移动锚节点的移动路径按照“Z”曲线移动，则未知传感器节点的定位将更准确，而移动锚节点的移动路径主要是通过部署区域的边界和整个网络区域来保持。我们采用“Z”曲线等级的概念来介绍“Z”曲线移动锚节点路径规划方案。基本的路径曲线定义为等级1，如图1所示，一个二维区域被分成4块，移动锚节点按照“Z”曲线移动经过4块小区域的交界中心及每块小区域的中心，4块小区域的中心分别记为 C1、C2、C3、C4。“Z”曲线等级 2 和等级 3分别如图2和图3所示。“Z”曲线移动锚节点路径规划方案包含四个阶段，具体如下所示。

图1 “Z”曲线（等级1）

第一阶段：分析未知传感器节点在通信范围内之间的关系及可定位性。根据下面的公式及移动锚节点按照“Z”曲线移动，未知传感器节点都能够被定位。公式如下：

图2 “Z”曲线（等级2）

图3 “Z”曲线（等级3）

si表示未知传感器节点；bj表示移动锚节点从三个不同位置发送的位置信息；dist（bj，si）表示未知传感器节点到移动锚节点的距离；Rc表示传感器节点的通信范围。

第二阶段：移动锚节点按照“Z”曲线移动，调整移动锚节点的通信范围，保证所有的传感器节点都能够定位。

第三阶段：通过“Z”曲线路径规划方案，移动锚节点选择最短路径发送三个不同移动锚节点位置信息给未知传感器节点。

第四阶段：通过“Z”曲线确定的路径提供了三个连续非直线的最短距离的锚节点。

1.2 节点定位

针对未知传感器节点的位置进行定位，本文采用非测距的定位算法进行定位。由于无线传感器网络能量受限，采用基于非测距的定位算法将减少节点的能量消耗，延长网络的生命周期。

在前期的研究中，我们已对基于非测距的定位算法有较深入的研究并提出了改进的IWCL-RSSI定位算法[12]。

RSS很容易获得并且不需要额外的电路，因此，减少了成本和能量消耗。由于基于RSS的非测距定位算法是利用接收信号强度直接计算盲节点的位置而无需测距，因此，减少了节点的计算量，提高了效率，从而减少节点能耗。由于无线传感器网络节点发射接收芯片都装有一个接收信号强度指示（RSSI，received signal strength indicator），这样 RSS测量无需额外的花费。

移动锚节点在移动的过程中，需要发送自己的坐标信息。因此，我们设计移动锚节点配置一个GPS定位模块，采用GPS技术定位，以便移动锚节点在移动的过程中及时发送自己的坐标信息。

由于对RSS进行了修正，采用新的基于RSS的非测距定位算法能够减少定位误差。改进的IWCLRSSI定位算法的定位过程具体如下：

第一步：当移动锚节点进入普通传感器节点部署区域，按照“Z”曲线移动路径规划方案，相隔一定的距离（折线拐点处）向周围的未知传感器节点发送自己的位置坐标。

第二步：未知传感器节点接收移动锚节点发送的不同位置坐标，并记录锚节点不同位置坐标和信号强度。

第三步：未知传感器节点根据记录的锚节点不同位置坐标和信号强度，利用改进的IWCL-RSSI定位算法计算普通节点的位置。

2 性能分析

在本部分中，将对本文提出的“Z”曲线路径规划方案与已有的路径规划方案进行性能比较，已有的路径规划方案包括 HILBERT[13]、SCAN[13]、CIRCLES[4]和LMAT[14]。实验是在无障碍环境中进行。我们将通过仿真实验来分析所设计的路径规划方案的性能，仿真工具采用MATLAB软件。

2.1 无线信道模型

d表示锚节点到未知节点的测量距离；PL0表示在参考距离为d0（d0=1m）的接收信号强度；β路径损耗因子；Nα是标准偏差为α、均值为0的高斯噪声。

2.2 仿真参数

实验区域大小100米×100米；200个未知传感器节点随机分布在试验区域；1个移动锚节点按照规划的路径进行移动；移动锚节点速度分别为0.5，1，1.5，2，2.5，3，3.5，4，4.5，5（单位：米 /秒（m/s））；其中Rc/d 分别为：0.5，0.75，1，1.25，1.5，1.75，2，2.25，2.5，2.75，3；路径损耗为 3.0；标准偏差为 3；PL0 为 50；d0为 1米；发射功率为-20dBm。

2.3 仿真实验

（1）定位误差率

采用改进的IWCL-RSSI定位算法时，五种路径规划方案的定位误差率对比如图4所示。通过观察图4可知，本文提出的“Z”曲线路径规划方案的定位误差最小。“Z”曲线路径规划方案的优点是移动锚节点在移动的时候更接近每一个未知传感器节点。当Rc/d等于2的时候，“Z”曲线路径规划方案具有最小的定位误差率。

图4 定位误差率

（2）定位时间

移动锚节点速度为0-5m/s时，未知节点的平均定位时间如图5所示，其中Rc/d为2。从图5可以看出，随着移动锚节点速度的增加，未知节点的平均定位时间也在减少；同时，可以看出“Z”曲线路径规划方案的未知节点的平均定位时间最少，优于其他4种路径规划方案。当移动锚节点速度为1-5m/s时，5种路径规划方案的未知节点平均定位时间都在1分钟以内。这是因为改进后的IWCL-RSSI定位算法无需测距，减少了节点的计算量，从而减少了定位时间。

图5 节点在不同速度下的平均定位时间

3 结语

路径规划方案在无线传感器网络的节点部署中非常重要。为了克服锚节点共线问题和减少定位时间，本文提出了一种“Z”曲线路径规划方案。从仿真结果可以看出，本文提出的“Z”曲线路径规划方案与已有的四种曲线路径规划方案相比，克服了锚节点共线问题，减少了定位时间和定位误差。同时，本文采用改进的IWCL-RSSI定位算法大大减少了节点定位的能耗和定位时间。因为改进的IWCL-RSSI定位算法采用无需测距技术，从而减少了节点能耗和定位时间。

［1］丁蕙.超宽带无线传感器网络节点定位优化模型研究［J］.廊坊师范学院学报（自然科学版），2009，9（4）：20-23.

［2］ Liang Yue，Guoru Ding，Ze Zheng.Path planning in sensor localization with mobile anchors：Survey and challenges［C］.2015 International Conference on Wireless Communications&Signal Processing（WCSP），2015：1-6.

［3］ Ting-Yu Lin，Hendro Agus Santoso，Chung-An Lin，Gui-Liu Wang.CFPP：Collision-free path planning for wireless mobile sensors deployment ［C］.2015 IEEE International Conference on Communications（ICC），2015：6412-6417.

［4］ Chia-HoOu，Wei-Lun He.Path Planning Algorithm for Mobile Anchor-Based Localization in Wireless Sensor Networks［J］.IEEE Sensors Journal，2013，13（2）：466-475.

［5］ Javad Rezazadeh，Marjan Moradi，Abdul Samad Ismail，Eryk Dutkiewicz.Superior Path Planning Mechanism for Mobile Beacon-Assisted Localization in Wireless Sensor Networks［J］.IEEE Sensors Journal，2014，14（9）：3052-3064.

［6］ M.S.Aruna，R.Ganesan，A.Pravin Renold.Optimized path planning mechanism for localization in wireless sensor networks［C］.2015 International Conference on Smart Technologies and Management for Computing，Communication，Controls，Energy and Materials（ICSTM），2015：171-177.

［7］ Yinglong Wang，Huanqing Cui，Qiang Guo，Minglei Shu.Obstacleavoidance path planning of a mobile beacon for localisation［J］.IET Wireless Sensor Systems，2013，3（2）：126-137.

［8］ Yi-lun Yang，Ling-Hua Zhang.Dynamic path planning of mobile beacon for localization in wireless sensor network ［C］.2013 International Conferenceon Wireless Communications&Signal Processing（WCSP），2013：1-5.

［9］ Sachin Gopal V，G.S.Binu.Mobile anchor path planning in wireless sensor networks ［C］.2015International Symposium on Advanced Computing and Communication（ISACC），2015：315-319.

［10］ Jialiang Lv，Yinglong Wang，Nuo Wei，Huanqing Cui.Dynamic path planning method for anchor node in three-dimensional wireless sensor networks［C］.2013 2nd International Symposium on Instrumentation and Measurement，Sensor Network and Automation（IMSNA），2013：900-904.

［11］李洪峻，卜彦龙，薛晗，等.面向无线传感器网络节点定位的移动锚节点路径规划 ［J］.计算机研究与发展，2009，46（1）：129-136.

［12］谢绍国，艾列富，施赵媛.无线传感器网络中IWCL_RSSI算法的改进［J］.安庆师范学院学报，2016，22（1）：31-33.

［13］ D.Koutsonikolas，S.M.Das，and Y.C.Hu.Path planning of mobile landmarks for localization in wireless sensor networks［C］.Comput.Commun.2007，30（13）：2577-2592.

［14］ Guangjie Han，Xuan Yang，Li Liu.A Disaster Management-Oriented Path Planning for Mobile Anchor Node-Based Localization in Wireless Sensor Networks ［J］.IEEE Transactions on Emerging Topics in Computing，2017，（99）.

A Path Planning Scheme Based on“Z”Curve in Wireless Sensor Networks

XIE Shao-guo
（Anqing Normal University,Anqing 246133,China）

Path planning scheme is essential in the node deployment of wireless sensor networks （WSNs）.In order to overcome the collinear beacons problem and reduce positioning time，based on the existing mobile beacon path planning schemes，this paper proposes a path planning scheme based on“Z”curve.Simulation results show that compared with four existing path planning schemes，the proposed path planning scheme based on “Z”overcomes the collinear beacons problem，reduces positioning time，and improves the localization accuracy.

wireless sensor network；localization error；RSSI；path planning scheme

TN911.21

A

1674-3229（2017）04-0017-04

2017-09-02

2015年安徽省自然科学基金（AQKJ2015B005）

谢绍国（1980-），男，博士，安庆师范大学计算机与信息学院讲师，研究方向：无线通信。