基于无人机动态路径的无线传感器网络定位

李松生

摘要：无线传感器网络若收集的数据带有位置信息，则作用更加显著，普遍应用的GPS对能耗要求较高，但无线传感器为了延长寿命和工作时间，为能源节俭型，而且GPS成本高于传感器，所以单个传感器配备GPS是不可行的。可移动灯塔能够重复使用，且可以配置GPS、可充电电源，无人机是典型的可移动灯塔的应用实例，由算法实时决定的无人机动态路径是无线传感器网络定位的更优选择。实验与仿真结果表明，与传统静态路径算法相比，该算法更加灵活，效率更高，用类似的时长和距离，可实现平均90%的定位率。

关键词：無线传感器网络；传感器；可移动灯塔；静态路径；动态路径；无人机

DOIDOI：10.11907/rjdk.173245

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2018）008-0065-06

英文摘要Abstract：Data collected by WSN is more valuable if it provides location information.GPS is the common source of location information，but it requires sustainable energy which is not available from wireless sensor，in addition，the cost of GPS is too expensive for WSN compared to the cost of sensor.Mobile beacon is a special sensor which is equipped with GPS and and it is rechargeable power supply and flexible to move.It can be alternative of many static beacons which are fixed.Static path of mobile beacon can be planted in advance so it is intentional and suitable for regular territory.By contrast，dynamic path need not know the condition and it is flexible and economical with time.UAV is popular and affordable currently，and it meets the need of mobile beacon.Simulation in the paper proves that dynamic path for localization of WSN based on UAV is effective and efficient with similar steps of static path and it can achieve 90% localized rate in average.

英文关键词Key Words：WSN；sensor；mobile beacon；static path；dynamic path；UAV

0 引言

WSN由一组互联的小尺寸、低成本传感器组成，通常用于监视特定区域参数[1]，其收集到的数据如果带有位置信息将更具有价值。GPS常用于提供位置信息[2]，但其能耗较高，不适用于要求低能耗的WSN。灯塔作为WSN中的一个特殊节点，可配备GPS且具有高电量。可移动的灯塔（MBC）能够代替多个静态灯塔，穿越监测区域发现传感器位置，从而帮助传感器提供带有位置信息的传感数据。无人机（UAV）是理想的可移动灯塔，其移动灵活，可反复充电以保证电源充足[3]。最新的智能飞行模式[4]包括航向锁定、航点飞行与兴趣点环绕等，使UAV的控制更加灵活。更重要的是，由于无人机制造公司对API开放，使固件层次的直接编程控制无人机成为可能。

可移动灯塔路径将决定传感器定位所需时间、成功百分比及定位准确性。静态路径，也即预先规划好的路径适用于传感器均匀分布的规则区域，而动态路径由灯塔在运动过程中接收到的传感器信息变化实时决定，更适用于传感器不均匀分布的不规则区域。由于传感器通常随机分布在目标区域，所以动态路径方法更加合理与可行[5]。

几何学由于具有直观特性，因而在路径设计方面应用广泛。Xiao B[6]等提出两种基于MB的传感器定位方法。一种利用MB到达与离开传感器时可能的重叠区域（ADO），缩小传感器的可能位置范围；另一种根据MB越接近则信号越强的基本原理，利用接收到的信号强度（RSS）推测MB最接近的时刻。以上两种方法都要求MB严格跟从预设路径，但有些位置的传感器仍无法定位。根据圆上任意两点形成线段的垂直平分线必然通过圆心的几何原理，如果传感器接收到3个来自MB的信号，则可确定自身位置，即3点形成两线段所在圆的圆心[7]。由于圆心位置最后由RSS推算而来，所以误差相对较大，随机理论与RSS配合更好。M L Sichitiu、V Ramadurai[8]提出利用贝叶斯推理处理MB收集到的传感器数据，从而推断传感器位置。其通过大量测试获得距离与RSS之间的概率密度函数（PDF），并且需要不断校正；文献[9]同样基于贝叶斯滤波器的粒子滤波器，即在多组有加权值的随机样本中应用蒙特卡洛滤波器，然后利用方差决定传感器最终位置，样本越多，方差越小，位置越准确，计算量越大，所以该算法对MB的运算能力要求很高；Kim K 、Lee W[10]应用粒子滤波器，利用一台专用电脑进行运算，选择RSS与距离的相关性作为加权值，用标准差判断位置的收敛。概率论所需计算量较大，无法适用于要求低运算、低能耗的无线传感器。

上述文献提出的静态路径规划主要应用于水平和垂直线，R Huang、G V Zaruba提出扫描、双扫描、Hilbert曲线几种路径[11]；文献[12]又增加了圆和S圆两种方式，并应用克拉美罗界作为评估工具比较以上路径。共线性是直线路径中的主要问题[13]，提高扫描分辨率可以减少共线性的影响，但导致路径变长。同心圆越多，覆盖率越高，但路径越长，共线性问题越突出。连通性是WSN的内在特性，其意味着图论原理也可应用于传感器发现过程[14]。D Koutsonikolas等[15]提出两种不同算法，宽度优先（BRF）和回溯贪婪（BTG），WSN被看成是一个无向连接图，路径规划转变为生成树的遍历问题；N Patwari等[16]提出深度优先算法，将路径问题转化成旅行推销员问题，并建议采用淘汰、连通支配集和最小生成树改善算法性能。与概率论相同，图论也存在计算复杂性问题[17-18]。

在本文提出的算法中，可移动灯塔UAV负责所有的分析与计算工作，每次行动有6个可供选择的基于几何学的新位置，传感器只需进行几次通信。图论只应用于局部网络以避开复杂计算。邻居数量决定灯塔走向，位置未知且拥有最多邻居的传感器将成为灯塔的下一个目标。RSS用来估计距离，位置已确定的传感器将化身为静态灯塔。正面与负面信息都可帮助灯塔定位传感器，灯塔只需两个位置信息结合自身运动方向即可确定传感器位置，并且所有前序信息都被重新浏览，以帮助确定位置未知传感器的位置。综上所述，所有计算都是轻量级的比较和判断，并且集中在MBC上。

1 算法描述

1.1 基本概念

（1）位置未知傳感器Unode，位置已知传感器Snode。

（2）参考传感器Rnode，Snode可以转化成Rnode。

（3）邻居传感器Nnode，相互可以通信的传感器互为邻居。

（4）所有传感器都有唯一、独立的编号ID，Unode.ID表示位置未知传感器编号。

（5）可移动灯塔MBC为算法主角，其也一样具有唯一、独立的ID。

（6）覆盖半径R，MBC与Unode的覆盖半径不需要一致，但为了表达与计算方便，在不失通用性的前提下本文默认一致。

（7）可移动灯塔的位置PMBC，每个位置都有地址ADDR和唯一、独立的序列号SN，SN与ID不重叠。当前位置为CPMBC，CPMBC.SN表示当前位置的序列号。

（8）下一个位置NPMBC，其具有6种可能性，如图1所示。

M是MBC的当前位置CPMBC，其坐标为（X0，Y0），将P1～P6均分以M为原点、R为半径的圆，其位置（Xn，Yn）可表示为公式（1）。

Xn=X0+Rcosπ6+n-1π3Yn=Y0+Rsinπ6+n-1π3（1）

其中，n为1～6。

目标传感器Tnode可帮助MBC决定NPMBC，成为Tnode的条件是传感器能接收到MBC从CPMBC发出的信息。传感器间通信只有hello和located两种信息， hello信息用来确定邻居关系，内容是信息发送者的ID，表示为hello.ID，located信息用来通知已定位的传感器，其内容为被定位传感器的ID，表示为located.ID以及地址信息located.ADDR。

无线传感器网络的定位问题可描述为：一批位置未知传感器{Unode}随机分布在指定区域，可移动灯塔MBC在该区域按指定规则行走，路过位置形成路径{PMBC}。将尽量多的Unode转变成Snode，Snode再转化成Rnode，以帮助MBC定位尽可能多的传感器，实现从{Unode}到{Snode}的转变。

1.2 普通传感器

本方法的主要执行者是MBC，普通的位置未知传感器只是配合MBC完成定位任务。普通传感器的任务相对简单，分为初始化与定位两个阶段：

（1）Unode初始化阶段。包括：①广播信息hello一次；②一直接收信息，将接收到的hello.ID加入到{Nnode}；③广播自己的ID，同时收集所有邻居的ID。如图2所示，Unode C的{Nnode}为{A，B，D}，F的为{E}。

（2）Unode定位阶段。未定位传感器定位前一直处于接收状态，第一次收到来自MBC的hello信息，上报{Nnode}，否则只回答“hello”；收到定位信息，如果是自己，则located.ID=self.ID， 完成定位，成为已定位传感器Snode，可以充当参考传感器Rnode；如果located.ID∈{Nnode}，被定位的传感器则为邻居传感器，转发定位信息，通知该邻居。

因此，传感器端基本没有计算，只有简单的查询和有限的交互通信，从而节省定位所需能耗，将有限的能耗留到实际的数据检测与传输过程中。相反，MBC移动能力强，具有足够电量，且计算能力强大，其可能是无人机UAV或机器人。为了实现传感器定位算法，其需要维持至少3个数据表：①位置表{PMBC}以SN为索引，内容为地址ADDR；②{Nnode}表记录所有收到并响应hello信息的邻居传感器ID；③传感器信息表{INFO}以传感器的ID作为索引。

每个传感器项包括以下内容：①ADDR：地址，被定位前为空；②{Nnode}：该传感器的邻居传感器信息，主要是Nnode.ID；③{MSG}：该传感器收到的位置信息，主要是PMBC.SN或Nnode.ID。{INFO}结构如图3所示。

1.3 MBC工作描述

MBC在目标区域中移动，其第一个步骤为“首三角”，在每个PMBC位置，它都循环执行“新参考点”、“参考点广播”、“两点测试”几个步骤，最后是“新目标”和“新位置”，以确定下一位置，直到再也找不到新目标，算法结束，MBC才停止移动。MBC工作流程如图4所示。

首三角是指定位过程开始时的3个PMBC位置，它们必须形成正三角形，以保证三角形内的所有位置未知传感器都被定位，转化成为参考传感器。

1.4 新PMBC

算法描述如下：

（1）新PMBC记录→{PMBC}

（2）广播hello

（3）While “hello”

hello.ID→ID

If {Nnode}

新的{INFO}项，记录ID，ADDR为空，{Nnode}、{MSG}为空

SN→ID.{MSG}

对于每个新的PMBC，首先一条新的PMBC记录被加入{PMBC}中，其SN=SN+1，即在之前的SN上加1，可保证其唯一性；广播“hello”消息，并等候Unode回应；每收到一条Unode上报的包含{Nnode}的消息，说明该Unode第一次收到来自MBC的信息。此时MBC在传感器信息表{INFO}中增加一项，保存Unode.ID与{Nnode}，同时生成空的{MSG}，将当前位置的SN，即CPMBC.SN放到{MSG}中；如果Unode的响应信息中没有{Nnode}，说明其不是第一次收到MBC信息，MBC只需将CPMBC.SN加入到{MSG}中；通信结束，MBC执行下一步“新参考点”。

1.5 新参考点

以ID为索引遍历{INFO}表，如果ID.ADDR为空，传感器位置未知，其ID.{MSG}里的SN和ID总数为3，即基数|ID.{MSG}|=3，说明该传感器有足够的定位信息，使用三角测量（triangulation）[19]可以直接估算位置，并将结果存储到ID.ADDR。

1.6 参考点广播

其算法描述如下：

ID为索引，遍历{INFO}

If ID.ADDR

If ID.{MSG}

清空ID.{MSG}

遍历ID.{Nnode}里的nID

If nID∈{INFO} & nID.ADDR为空

ID→nID.{MSG}

再以ID为索引遍历{INFO}表，如果ID.ADDR不为空，传感器位置已知；如果ID.{MSG}不为空，说明这是刚被定位的传感器Snode，可以转化成Rnode，此时清空ID.{MSG}，遍历此ID里的{Nnode}；如果Nnode.ID在{INFO}，即Nnode.ID∈{INFO}；如果Nnode.ID.ADDR为空，该Nnode尚未定位，将自己的self.ID加入Nnode.ID.{MSG}中。

如果ID.{MSG}的内容全为ID，没有SN，说明该ID的定位信息全部来自邻居Nnode，其位置信息准确性较差，将不被选为Rnode。

新参考点和参考点广播两个步骤循环执行，直到没有新参考点为止。

1.7 两点测试

当位置未知传感器Unode只有两个位置信息，其接收到两个来自PMBC或参考传感器Rnode的信息，根据三边测量（trilateration）[20]，它有两个可能位置P1和P2。两点测试即分别计算P1、P2与非邻MBC的位置{PMBC}-Unode.ID.{MSG}，以及非邻node：{Rnode}- Unode.ID.{Nnode}。如果P1或P2与任一个{PMBC}或{Rnode}的距离小于MBC的覆盖范围R，该位置将被否决，其它位置才是正确位置。因为该Unode既没有收到非邻PMBC的信息，也不可能与那些非邻node有邻居关系，而有邻居关系的node已被排除在外。

如果通过两点测试产生新的合格Rnode，根据图4流程所示，MBC继续重复“新参考点”、“参考点广播”以及“两点测试”过程，直到没有新的合格参考点Rnode为止。至此，MBC一个新位置PMBC的全部流程结束，开始选择NPMBC。

1.8 NPMBC选择

NPMBC选择流程如下：①根据SN.{Nnode}决定候选目标Tnode；②根据Tnode.ID.{Nnode}的基数|ID.{Nnode}|计算候选目标Tnode的权重W；③根据位置关系Cmn计算候选NPMBC的权重，argmax∑ni=1CmiWi最大者成为NPMBC，C如公式（2）所示。

其中m为候选位置个数|{NPMBC}|，n为候选目标个数|{Tnode}|，只有第m个NPMBC与第n个Tnode之间距离小于R时，Cmn=1，否则为0。

如果候选NPMBC权重相同，计算候选NPMBC的净权重w，argmax（wm）成为NPMBC。如果只有一个候选目标，MBC直接来到离目标最近的NPMBC即可。所有CPMBC.{Nnode}里的传感器，如果已收到两个以上信息，即|{MSG}|内容基数大于等于2，其将为下一PMBC的候选目标。因为如果位置未知传感器只收到1条信息，MBC无法估计其位置，则无法向其靠近。候选目标的选择依据是邻居基数W=|ID.{Nnode}|，邻居越多，权重越大。只收到两个地址信息，还未确定位置的Unode权重再加1，因为其自身即是未定位的传感器。

NPMBC选择的第一原则是不能重复。MBC先检查P1-P6是否已记录在{PMBC}中，否则自动成为NPMBC的候选者。遍历NPMBC候选者，如果其与候选目标Tnode的距离小于覆盖范围R，说明MBC如果选择该位置，候选目标将会接收到MBC的“hello”信息，该候选目标的权重W则被累计到相应NPMBC的权重中。最后如果存在唯一权值总和最大的NPMBC，其则为最终的NPMBC。如果没有唯一的总权值占优的NPMBC，進一步扩展算法则是NPMBC的净权重w，因为NPMBC候选目标Tnode的ID为ID1～IDn，其{Nnode}互有交集，所以净权值w为|ID1.{Nnode}∪ID2.{Nnode}∪…∪IDn.{Nnode}|，w≤W。净权值间的比较更加合理，但运算较为复杂。净权值w最大的候选NPMBC将会成为NPMBC。图5是NPMBC选择的直观表示，M是CPMBC，P1-P6是6个候选NPMBC，A、B、C以及D、E各为一组候选目标，所以P3、P6将是两个候选NPMBC，最终选择将由各自总权值决定。

综上所述，算法从“首三角”开始，保证有“新参考点”，其捆绑执行“广播参考点”与“两点测试”，在每个PMBC，3个函数循环交替执行直到没有新参考点，然后决定新目标和新位置，并移动到新的PMBC，重复以上步骤，最后定位过程在没有新目标的情况下完成并退出。

2 仿真与分析

从100次仿真数据中随机抽取数据得到仿真图6。場景设置为：在一个60 *60 m的区域里，随机分布60个传感器，每个传感器用“o”指示，其右边有一对数据用“/”分开，左边是该传感器ID，右边是其邻居个数|{Nnode}|。当传感器被定位时，在“o”中间加上“*”号，没有“*”则表示传感器未被定位。缺省设计MBC从研究区域的左下角开始，图中实线是MBC的行走轨迹，虚线是MBC在每个PMBC的信号覆盖范围R。在该仿真中，R=10 m，在此范围内的传感器能接收到来自PMBC的“hello”信息并回应。

由图6可见，一共有17个MPBC、4个传感器未被定位，从上至下ID分别为50、41、58和9。其中41和50互为邻居，其位置偏远，没有接收到PMBC的信息；50的另一个邻居为11，其已被定位，没有直接接收到PMBC的信息，所以不会转化成Rnode，没有广播定位信息；ID为58的传感器状况与ID50类似；ID为9的传感器有3个已被定位的邻居，因而有机会被定位，但只有一个邻居ID36直接接收来自MPBC的信息，并转变为Rnode，其它两个邻居26和7都没有直接接收到MPBC的信息，尽管被定位，却无法转为Rnode，所以ID9只接收来自ID36的定位信息，而无法定位。

图7呈现的是同一前提条件下的100次仿真结果，其显示基本规律是MBC的行走距离越长，被定位的传感器越多。出现两次3步的状况是由于本仿真缺省从左下角开始，如果随机分布在此处的传感器与其它传感器没有直接联系，或者联系较弱，MBC则无法决定NPMBC，因而停止。该状况出现了两次，说明算法尚存在改善空间。

图8是用一元线性回归分析方法拟合的MBC行走距离与被定位传感器之间的线性关系，其中“*”表示MBC行走距离对应的被定位传感器的数目平均值。当PMBC个数大于18后，其结果不再符合线性，被定位的传感器平均数量保持在55左右，超过总数的90%。总共有60个未知传感器，55个被定位已基本达到极限，因为总有几个传感器分布在研究区域边缘。

3 结语

本文提出一种利用可移动灯塔的动态路径实现无线传感器网络中位置未知传感器定位的算法，无论从计算量还是能量消耗角度，都是一种轻量级算法，仿真结果也证明该算法是高效可行的。

由仿真数据可知，在某些场景中，移动灯塔只移动几次即停止，被发现的传感器数目也相对较少。出现该状况的主要原因是算法以邻居数目|{Nnode}|为驱动，如果出现如图6所示ID为41的传感器状况，其没有邻居，移动灯塔则会出现停止的情况。改进方法为让移动灯塔多移动一步，则可能发现新目标，或者换一个起点。缺省状况是从左下角起步，如果出现突然停止而定位率低的情况，可以移动到右下角或从其它角落开始。

从提高效率的角度考虑，还可以尝试的方法包括改善目标权重，目前是所有邻居都计算在内，可以考虑剔除重复与已定位的邻居，专注于寻找尚未定位的传感器。还可缩小下一灯塔位置的选择范围，目前的原则是不重复，将来可以适当降低到达位置附近的位置权重，因为它们可能已有足够的定位信息。如果不考虑距离，优先考虑定位率，灯塔按照静态路径行走将可能提高定位率。

随着无人机技术的不断成熟与广泛应用[21-22]，该算法的现实意义是无人机可以充当移动灯塔，只要把该算法植入无人机的飞行控制系统，即可实现自动寻找待定位的无线传感器，发现与记录传感器位置，并在未来的应用数据中附加上位置信息，以确保数据的完整性和准确性。

参考文献：

[1] 崔莉，鞠海玲，苗勇，等.无线传感器网络研究进展[J].计算机研究与发展， 2005，42（1）：163-174.

[2] 彭宇，王丹.无线传感器网络定位技术综述[J].电子测量与仪器学报，2011，25（5）：389-399.

[3] 毕凯，李英成，丁晓波，等.轻小型无人机航摄技术现状及发展趋势[J].测绘通报，2015（3）：27-31，48.

[4] 大疆.智能飞行新时代已经到来[EB/OL].Http：//www.dji.com/cn/intelligent-flight-mode/v1-doc.

[5] 王成群.基于学习算法的无线传感器网络定位问题研究[D].杭州：浙江大学，2009.

[6] XIAO B，CHEN H K，ZHOU S G.A walking beacon-assisted localization in wireless sensor networks[C].In International Conference on Communications，Glasgow，Scotland，2007：3070-3075.

[7] SSU K，OU C ，JIAU H.Localization with mobile anchor points in wireless sensor networks[J].IEEE Transactions on Vehicular Technology，2005，54 （3）：1187-1197.

[8] M L SICHITIU，V RAMADURAI.Localization of wireless sensor networks with a mobile beacon[C].In Proceedings of the 1st IEEE International Conference on Mobile Ad Hoc and Sensor Systems （MASS 2004），2004：174-183.

[9] HUANG R，ZRUBA G V.Monte carlo localization of wireless sensor networks with a single mobile beacon[J].Wirel.Netw，2008.

[10] KIM K，LEE W.MBAL：a mobile beacon-assisted localization scheme for wireless sensor networks[C].In Proc.ICCCN，2007：57-62.

[11] R HUANG，G V ZARUBA.Static path planning for mobile beacons to localize sensor networks[C].Pervasive Computing and Communications Workshops，PerCom Workshops 07.Fifth Annual IEEE International Conference on，2007：323-330.

[12] CABALLERO F，L MERINO，et al.A probabilistic framework for entire WSN localization using a mobile robot[J].Robot.Auton.Syst，2008，56（10）：798-806.

[13] 王成群.基于學习算法的无线传感器网络定位问题研究[D].杭州：浙江大学，2009.

[14] 戴欢.无线传感器网络定位算法及其应用研究[D].无锡：江南大学，2012.

[15] D KOUTSONIKOLAS，S M DAS，Y C HU.Path planning of mobile landmarks for localization in wireless sensor networks[C].In Proc.of IEEE Distributed Computing Systems Workshops，2006：86.

[16] N PATWARI，A HERO，J ASH，et al.Locating the nodes：cooperative geolocation of wireless sensors[J].IEEE Signal Processing Magazine，2005，22：54-69.

[17] HONGJUN LI，JIANWEN WANG，XUN LI，et al.Real-time path planning of mobile anchor node in localization for wireless sensor networks[C].Proceedings of Information and Automation，2008.

[18] X LI，N MITTON，I RYL，et al.A novel sensor localization scheme by mobile actors[C].In Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing （MobiHoc），2009：339-340.

[19] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005，16（5）：857-868.

[20] 杜存功，丁恩杰，苗曙光，等.无线传感器网络改进型节点定位算法的研究[J].传感器与微系统，2010，29（1）：52-54.

[21] 冯家莉，刘凯，朱远辉，等.无人机遥感在红树林资源调查中的应用[J].热带地理，2015，35（1）：35-42.

[22] 张波，罗锡文，兰玉彬，等.基于无线传感器网络的无人机农田信息监测系统[J].农业工程学报，2015，31（17）：176-182.

（责任编辑：黄 健）