基于路由信息的传感网络定位算法

    1.引言

    无线传感器网络是近年来一个热点研究领域，其中传感器网络定位技术也越来越受到人们的关注，这是因为传感器网络的大量应用都依赖于节点的位置信息，例如在战场侦察、生态环境监测、地震洪水火灾等现场的监控等应用中，都需要知道传感器节点的位置信息，从而获知信息来源的准确位置。

    现有无线传感器网络定位系统种类繁多，实现方法各异[1][2]。具有代表性的有采用超声波测距的TDOA(TimeDifference of Arrival)系统[3]，基于RSSI (Receive Signal Strength Indicator)的技术[4]，基于网络连通性的质心定位算法[5]，基于多跳传感器网络节点间跳数的DV-Hop算法[6]等。现有算法大多存在额外的硬件开销，或需要较多已知位置的参考节点，而且都有较大的通信开销，带来了传感器节点额外的功耗，这样就降低了全网的生存周期。因此，需要针对无线传感器网络的具体场景，设计低成本，低开销，易实现的定位算法。

    2.基于路由信息的定位算法

    2.1研究场景定义

    无线传感器网络的应用场景各异，对定位的需求也各不相同。因此，在进行定位算法的设计前，必须选定应用场景进行有针对性的设计。本文选用传感器网络中广泛应用的大范围数据采集场景，例如土壤温湿度监测、森林火险预警、智能大厦人员数据采集等，作为研究前提。

    在这种场景下，数量众多的传感器节点分布在较大范围的区域内，节点需要通过多跳路由将数据返回到一个或多个网关节点。所有传感器节点不装配GPS、超声收发器、有向天线等额外的定位和测距设备，节点射频模块只具备射频信号强度检测能力(RSSI)，甚至RSSI能力也不具备（即只有通信功能）。为了方便下面的研究，进一步对场景作如下简化定义：

    1.传感器节点数目表示为n,网关节点数目表示为m；

    2.n个传感器节点在区域内随机均匀分布，自身位置为(xi,yi)均未知，其中i= 1...n；

    3.m个网关节点在区域内以某种规律分布，自身位置(xi,yi)均已知，其中i= n+1...n+m；

    4.传感器节点均以一定且相同的周期采集数据，节点间相对静止；

    5.节点采用无线全向天线进行互通信，RSS测距的先验概率分布满足高斯分布；

    2.2设计思路

    而且因为数据采集任务对网络的存活时间要求一般较高，所以降低传感器节点的功耗，即降低传感器节点的通信开销就成为设计定位算法中重要的因素。而现有定位算法存在的主要问题就是通信开销大，其中有一个重要原因是现有的研究将定位过程与网络路由和数据采集看作独立的过程，而事实上这两个过程存在大量通信的重复，这样就带来了额外的通信开销。本文的研究就是将路由协议与定位算法结合来减少这部分开销，基本思路是通过在数据包上附加网络路由信息来获得部分节点间的连接和距离关系，然后根据这些关系来进行传感器节点定位，该算法命名为RBSL(RoutinginformationBased Sensor Localization)。

    本文选用了传感器网络中常用的定向扩散路由协议[7](DirectedDiffusion)作为研究的基础。定向扩散路由协议是一种以数据为中心的路由协议，网关节点向所有传感器节点发送对任务描述的“兴趣”(Interest)，“兴趣”会逐渐在全网中扩散，最终达到所有匹配“兴趣”的传感器节点，与此同时也建立起了从网关节点到传感器节点的“梯度”，传感器节点会沿着梯度最大的方向将数据传回网关节点。定向扩散的原理示意图如下图1所示：

    对于全网数据采集的场景，网关节点发送的“兴趣”是采集所有节点数据。在建立梯度之后，每个一个传感器节点都有一个自己对网关节点的最大“梯度”方向，即下一跳传输的目的节点编号(ID)。若每个传感器节点在发送数据包末尾都附加自己的下一跳节点ID，则在每一个网关节点就都可以获得网络中n条链路的连接情况，即获得了到一个网关节点的树状路由表。将m个网关节点的数据进行综合就可以获得更多条链路的连接情况。将获得的n个传感器节点和m个网关节点之间的连接关系表示为对称连接矩阵L(n+m,n+m)，其中Lij= 1 表示i, j节点存在路由链路，反之Lij = 0表示不存在路由链路，其中1≤i, j≤ n+m，若1≤i≤n表示i为传感器节点，若n

    进一步的，如果传感器节点具有RSSI，可以根据射频信号传输的经验模型估计链路距离dij，同样将估计距离发往网关节点。与连接矩阵L类似可以生成对称距离矩阵，表示为D(n+m,n+m)，其中Dij=Dji 表示i, j节点间路由链路的估计距离。

    下一步就是根据连接矩阵L或距离矩阵D来进行节点定位。这里就需要用到MDS算法，MDS算法的全称是多维标度分析（Multi-DimensionalScaling），是一种最早应用在计量心理学和生物信息统计中的算法。作为MDS算法的一种简单的应用，若已知二维空间上n个点的两两距离，即完全的距离矩阵LALL(n,n)，则可以反解出这n个点的二维相对拓扑。YiShang等人[8]最早将MDS算法应用到无线网络定位中，本文也采用了类似的思路。由于通过路由过程获得的连接矩阵L或距离矩阵D都只是部分链路，所以还需要通过最短路径算法生成在原矩阵中不连通的节点之间的近似距离，得到近似的DALL来作为MDS算法的输入。

    在获得距离矩阵DALL之后，就可以根据MDS算法计算得到节点的相对二维拓扑分布，但该分布与真实分布存在缩放，旋转和平移的关系。因为m个网关节点都已知自身位置，当m≥3时，可以根据网关节点的位置，对相对拓扑进行坐标变换得到最终估计的二维拓扑。

    3.算法实现过程

    3.1定向扩散

    目的是尽可能多的携带节点间的连接或测距信息，在建立梯度阶段中，每个节点可以得到其下一跳节点ID。在传输数据阶段，则将下一跳节点ID也打入数据包，按照最大梯度方向发往网关节点。当节点具有RSSI时，还要将下一跳节点对应的测距结果发往网关节点。

    3.2计算节点距离矩阵DALL

    目的是提取网关数据中关于节点连接或测距的信息，并通过最短路径算法得到所有节点间的近似距离，即完全的距离矩阵。当节点具有RSSI时，则可以根据数据包中的每个节点的测距信息生成部分距离矩阵D，然后采用Floyd最短路径算法，生成DALL。若节点不具备RSSI，则将连通表示为单位距离1，同样用Floyd最短路径算法，由连接矩阵L生成DALL。

    3.3多维标度分析MDS

    将节点距离矩阵DALL作为MDS算法的输入矩阵，可以获得节点的相对位置估计X’,Y’。

    3.4平移和旋转变换

    通过比对已知位置的网关节点，将MDS结果进行坐标变换使得网关位置均方误差最小。即设X’,Y’为MDS输出的网关节点位置，求变换矩阵A,B使得[X’’,Y’’] = A * [X’, Y’] + B与网关节点已知位置[X, Y]的均方误差最小。

    4.仿真结果和分析

    算法仿真采用Matlab6.5，仿真场景为100个传感器节点随机均匀分布在半径50m的圆型区域内，网络中有大于等于三个已知位置的网关节点。

    在图2的仿真中，10个网关节点均匀分布在半径为10米的圆周上，射频通信距离取20m，射频信号测距误差为20%，图中线段长度代表定位误差大小。仿真结果直观的给出了RBSL算法在节点具有RSSI和没有RSSI情况下定位的效果。从图2的仿真中，还可以发现RBSL算法的一个应用场景，即在大范围的数据采集中，如果只有一个网关节点，可以通过数据采集员手持一个网关节点在一个小范围内移动，在不同位置采集数据就可以对节点进行定位。

    图3-a给出了节点RSSI测距误差对结果的影响，可以发现，当测距误差在20%以内时，定位结果较好，而若测距误差进一步增大，则结果恶化较为明显。图3-b给出了节点通信距离对结果的影响，可以发现在通信距离=25m时定位误差最低，这是因为通信距离过短会使得部分边缘节点只有很少的邻居，从而导致这些节点定位精度很低，而当通信距离过长时，网络中的路由链路变少，导致能获得链路信息变少，同样降低了定位精度。

    5.结论和研究展望

    针对无线传感器网络的大范围数据采集应用场景，本文作者提出了基于路由信息的传感器网络定位算法RBSL。RBSL算法的主要优点是通信开销小，只需要每个节点在自身数据包上附加几字节的信息，且容易实现，在大范围的数据采集场景，只需要多个网关节点或一个可移动的网关节点就可以获得节点的定位结果。RBSL算法存在的问题是计算量较大，MDS和Floyd最短路径算法复杂度均为O(n3)。但因在数据采集场景下，执行计算任务的是网关PC节点，因此计算量的问题相对是可以接受的。此外，在前面的分析中假设网络均匀同构，事实上传感器节点性能可能并不相同，且由于地形等因素影响也会造成网络的不均匀，反映在RBSL算法中就是节点间测距结果精度的不同，如何在MDS算法中对精度不同的测距结果进行加权是下一步的研究任务之一。

    作者所在的清华大学电子工程系复杂系统工程实验室(CESL,ComplexEngineering System Lab)已经自主开发了“灵活的低成本无线传感器网络平台”，即FLOWS (Flexible Low-cOst Wireless Sensor network platform)。我们正在进行FLOWS系统在智能大厦定位系统的研究与开发，相信会有很好的应用前景和经济效益。