传感网络中坐标评估机制的研究∗

张 洁

（福建农业职业技术学院 福州 350007）

1 引言

传感网络通过网中节点的位置坐标信息可以感知到节点附近发生QoS异常事件的位置坐标。于是节点坐标评估相关技术就成为了研究的热点。现阶段，传感网络中关于节点位置坐标评估的常见技术有基于测距/非测距定位方案。测距［1］方案要先计算待测节点和已知节点的间距才能确定待测位置的坐标信息，而非测距方案仅仅只需知道已知节点的位置坐标信息即可通过算法评估待测节点的位置坐标。无论从分布式系统的计算复杂度、能耗、成本可控等方面，后者都不失作为定位的首选方案。

目前，关于非测距定位方案的相关算法众多。从定位精度角度而言，研究最多的是基于距离矢量跳数加权计算算法。该算法通过增设加权系数来体现全局拓扑网络中不同的已知节点对待测节点的间隔计算的影响力，再计算出加权平均跳距，进而获取待测节点位置坐标信息。然而通过引入加权系数的方式提高节点位置坐标评估精度是建立在节点均衡分布于全局拓扑网络的前提下来展开研究的。反之，当节点无规则地分布在全局拓扑网络中，加权算法仍然通过计算已知节点加权平均跳距的方式获取未知节点位置坐标，将与未知节点在网络中的实际位置坐标有较大的差距。

基于此，本文提出一种旨在提高随机［2］拓扑全局中，节点坐标计算值与实际值吻合度的评估机制。该评估机制通过对未知节点的平均跳距重新展开评估来改善待测节点位置坐标的数值精确度。

2 加权算法原理

加权算法思想是节点仅仅与邻接节点互换各自网络参数信息，并通过互换协议［3］使全局节点获得距离已知节点的跳数信息。已知节点获取全局范围内的其他已知节点的位置信息和间隔跳数信息，算出平均跳距。待测节点与已知节点之间的间距，通过全局平均每一次跳距与两个节点间最短路由跳数相乘来计算获得。当待测节点搜集到三个以上已知节点的距离信息时，通过极大似然估计来获取未知节点的位置坐标信息。加权算法思想下的算法流程如图1所示。

图1 加权算法流程

由图中流程可知算法虽然通过加权方式提高了计算未知节点位置坐标的准确性，但这是建立在全网节点密度［4］分布均衡的前提下。然而在实际网络环境中由于诸多因素导致节点在全网中的密度呈现不均。此时再将加权平均跳距视同为节点间的实际物理距离势必导致后续定位环节出现偏差；其次，未知节点从众多已知节点中选出距离其最近的已知节点，计算出两节点间的平均跳距，并将该平均跳距值等同为全网中其他已知节点的平均跳距；再者，算法忽略了在节点的通信范围内已知/邻居节点间跳数与实际距离的客观关系；同时，通信范围内各类节点的规模对计算未知节点坐标位置［5］的影响程度在算法中未得到体现。上述因素累加必然导致加权算法下的节点位置坐标与实际位置坐标吻合度较低。因此，从缩小未知节点位置坐标计算值与实际值的误差角度而言，有必要对全局节点间平均跳距重新展开评估。

3 重新评估机制

当全网中有较多节点时，网中待定位的未知节点与已知节点在跳跃过程中可能存在跳跃路径部分重叠的情形。比如，网中距离待测节点a最近的信标节点是已知节点A，则已知节点A到已知节点B的最短跳跃路由与未知待测节点a到锚节点B的最短跳跃路由中有一部分可能是一样的。对于这样的情形，在计算已知节点与未知待定位节点间距的环节中要求已知节点A仍然以先前获得的跳距作为其平均跳距。除此情形之外，所有节点的平均跳距均要求重新评估。重新评估步骤为：1）计算平均跳距。平均跳距=（已知节点A到网中其他已知节点的距离）/已知节点的最短跳跃数；2）计算算术平均值。对先前获得的平均跳距和上述步骤获得的平均跳距进行算数平均，并将算数平均值取代先前获得的平均跳距；3）评估节点距离。从已知节点的位置坐标信息获取补偿数据，并结合算数平均值来评估［6］节点的距离。

算法在启动网络后首先通过网中节点相互转发数据包，使全网节点获取各自已知节点的坐标位置和跳数数据，再评估已知节点之间的平均每跳距离和实际距离。以已知节点i和已知节点j转发的数据包为例，分别转发数据包［IDi-Xi-Yi-HopNumberi］和［IDj-Xj-Yj-HopNum⁃berj］。IDi/IDj为锚节点的标志位，（Xi，Yi）/（Xj，Yj）为已知节点的位置坐标，HopNumberi/HopNumberj为跳数信息。假设SDij为两个已知节点的实际间距，将平均跳距与两个已知节点间的最短跳数的乘积作为评估距离PDij，求得两个已知节点的增长指数 Zij=（PDij-SDij）/SDij。再由这对已知节点将次增长指数以广播方式转发给全网中其他未知节点。为了描述未知节点w对这对已知节点的偏离程度，引入误差因数Ywij。则Ywij=PDwi+PD⁃wj-PDij。为使被评估的跳距更加客观地体现出节点之间真实距离降低评估值与实际值的差距，引入加权平均法来评估跳数最短的三个锚节点的补偿系数。因此在假设距离未知节点w最近的上述一对已知节点i、j的同时新增一个已知节点m。

为评估未知节点w对网中n个已知节点的偏离度［7］，引入Ywin。Ywin=PDwi+PDwn-PDin。

定义未知节点w到达已知节点i再到网中三个偏离程度最低的已知节点e、已知节点f、已知节点g的误差因数为Ywie、Ywif、Ywig，再求得未知节点w的补偿因子Bwi。

据此可得未知节点w到达已知节点j/m的补偿因子Bwj/Bwm分别如下：

结合上述未知节点w距离最近已知节点i、已知节点j、已知节点m的三个补偿因子［8］，对未知节点w到已知节点i、已知节点j、已知节点m的间距进行重新评估。重新评估后的距离分别为CPwi=PD⁃wi/（1+Bwi）；CPwj=PDwj/（1+Bwj）；CPwm=PDwm/（1+Bwm）。

4 实验分析

4.1 实验模型

为方便通过Matlab仿真平台对重新评估机制的效能进行考察，实验开始前先对仿真模型［9］和相关指标做如下设置：1）构建100m×100m的待测传感网络，并在全网范围内随机投放30个位置坐标信息明确的已知节点和70个位置坐标信息不明确的未知待测节点。2）仿真通过6次变换节点的通信半径来考察通信范围对算法的影响力。3）每运行一次都重新将这100个传感节点随机投放在所构建的网中。为了避免相同类型节点在投放过程中不够随机导致实验数据不准确，故将仿真［10］模型运行400次，再对比未知待测节点经过跳距重新评估后的位置坐标与实际位置坐标的偏离度，即定位误差。

加权算法在计算节点坐标方面的误差较大，根本原因在于该算法默认未知节点的跳数均为一跳，就算是多跳也默认为仅一跳。再通过平均跳距和跳数的乘积来评估已知节点和待测节点的间距。显然这严重降低了算法对位置坐标计算的精度，尤其是节点在全网随机布局情形下，这样的误差显得愈加明显。而在重评机制中为了衡量定位待测节点的准确性，引入坐标误差因子E。该因子描述的是未知待测节点经过算法计算分析后给出的评估坐标信息（Xp，Yp）与该未知待测节点在监测网络区域范围内的实际坐标信息（Xs，Ys）之间的差异。当监测［11］的传感网络范围内有N个未知待测节点参与时，待测节点所对应的坐标误差因子被记为

为了考察重评机制的实效性，本次实验方案主要从以下几个方面来实施：1）通信半径范围内已知节点规模占比的变化；2）已知节点占比相同的情况下，通信半径范围的变化；3）通信半径范围内全部节点规模的变化。通过实施上述三种方案来比较算法［12］优化前后在评估跳距方面的差异程度。

4.2 实验分析

通过Matlab将100个已经/未知节点无规则地投放在如图2所示的传感网络范围内，网中节点通信半径置为20m。其中星号表示已知节点，三角形表示未知节点。

图2 节点随机布局图

图中显而易见，已经节点和未知节点在网络中的密度是不均匀的，甚至出现未知节点周围基本不存在已知节点以及已知节点周围的未知节点稀疏现象。就是这样的布局，使得加权算法在计算跳距［13］时出现了误判，进而导致后续坐标计算环节进一步偏差。

如图3所示，是加权算法为未知节点计算出来的评估值与实际值之间在距离上的偏差。从仿真图中不难看出偏差范围主要集中在10m～20m之间，个别节点的偏差甚至更大。造成这么大坐标偏差的主因便是上述所说的加权算法为周边已知节点密度稀少甚至没有已知节点参与的未知节点，计算跳距时出现了误差，尤其多跳情形下这样的误差进一步加剧。而改进的算法通过补偿等方式对平均跳距重新开展评估，显著提高了实际跳距的客观性。故在图4所示的仿真图中，未知节点的位置坐标评估值与实际值在距离上的差距显著缩小。观察该仿真图可知，偏差范围降至5m～10m范围内。这与优化前坐标定位效果形成鲜明对比。

图3 未知节点在加权算法下的评估值与实际值在距离上的差异

图4 未知节点在重评机制下的评估值与实际值在距离上的差异

为了验证节点通信半径对坐标误差的影响力，通过仿真得到如图5所示的实现曲线图。仿真场景中的节点通信半径依次是20m、30m、40m、50m、60m、70m、80m。每个通信范围均投放15个已知节点。从曲线走势观察到，两种算法的坐标误差都随着通信半径的扩大总体呈现降低趋势。相对而言，重评机制的坐标误差改善幅度比传统的加权算法明显的多。随着通信半径［14］进一步扩大，在两种算法坐标误差总体趋于平稳的情况下，优化的重评机制仍然略微呈现继续降低趋势。

图5 两种算法下节点通信半径与坐标误差关联度

由重评机制的评估原理可知，待测区域内未知节点坐标计算的准确程度与已知节点的位置坐标息息相关。当已知节点的数量越多，位置坐标信息越明确越丰富，越有利于缩小待测节点位置坐标评估值与位置坐标实际值的误差程度。据此原理，在待测的随机拓扑网络范围内投放不同规模的已知节点：5个、10个、15个、20个、25个、30个，并将节点通信半径范围统一置为30M，以此考察已知节点的规模对未知节点坐标计算带来的影响力。为了提高仿真［15］数据的客观性，本次实验针对不同规模的已知节点开展高达400次的仿真，运行出如图6所示的待测节点坐标误差曲线图。

图6 两种算法下已知节点的规模对计算待测节点坐标的影响力

图中所示的两条坐标误差走势图可知，在总节点规模不变的前提下，两种算法表现出来的坐标误差均和已知节点的规模呈反比关系。在该待测随机拓扑网络中，已知节点占比相同的情况下，采用重评机制对待测节点开展坐标计算出现的误差有明显的降幅。当已知节点占比超过25%以后，加权算法的坐标误差开始趋于稳定。相比之下，此时优化的重评机制却能够依然呈现略微下降的态势。

虽然拓扑网络中投放的节点越多，越有益于对待测节点的坐标进行精准地分析和计算。但节点规模无节制的增加反而降低网络资源使用情况。为此，在待测拓扑网络范围内随机布署节点，节点通信半径置为20m，已知节点占比5%，节点总数从100增至350。通过仿真得到如图7所示的曲线图。

从图中曲线走势看出，无论算法优化前后的坐标误差均随总节点数增加而总体呈现逐渐降低趋势。当节点总规模低于250个时，两种算法的坐标误差下降得都较为显著。随着节点总数进一步增加，两种算法的显著趋势开始逐渐趋缓，甚至趋于平稳。这是由于在特定区域的拓扑网络内，节点间通信开销随着总节点规模过渡扩大而线性地增加，最终耗尽网络资源导致全网阻塞。因此，改善待测节点坐标计算精度时要事先参照设定好的网络区域大小来合理地规划全网节点通信半径、全网节点投放总数。否则超出了网络承载节点的门限，定位坐标的效能性便不再持续。此外，通过该图曲线末端的走势仍然可见，即便在总节点过渡投放的情况下，重评机制仍自始至终表现出坐标评估误差较低的相对优势。

图7 节点总规模对两种算法坐标计算误差的影响力

5 结语

本文通过分析加权算法运用在节点均匀投放的全局网络中所表现出来的坐标定位误差和算法适用的局限性，提出了一种节点随机分布于拓扑全网且在节点通信半径范围内实现多跳情形下的平均跳距重新评估机制。该机制先为节点计算出平均跳距的算术平均值并将该值取代原有的跳距值，再对跳距系数进行相应补偿。最后，在Matlab仿真平台上搭建实验模型并构建一套实验方案来考察本文提出的评估机制与传统的加权算法在计算节点位置坐标方面的精度对比。经过四项实验，最终验证了重新评估机制应用在全局感知网络中为待测节点计算位置坐标具有更高的可靠性和准确性。重新评估机制带来的高精度定位可为物流跟踪、军事侦查、智能交通、航海定位等生产实践领域提供一定的参考意义。