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

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.仿真结果和分析

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

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

图2：RBSL算法仿真结果1 

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

    图3：RBSL算法仿真结果2

5.结论和研究展望

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

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

    本文作者创新点：将传感器网络路由和定位信息的获取过程结合，易于在现有系统上实现，降低了定位过程的通信开销，并采用MDS算法获得了较好的定位精度。