一种基于QR分解的分布式移动节点定位算法

《一种基于QR分解的分布式移动节点定位算法》由会员分享，可在线阅读，更多相关《一种基于QR分解的分布式移动节点定位算法（6页珍藏版）》请在装配图网上搜索。

1、一种基于QR分解的分布式移动节点定位算法刘少帅1，2，罗海勇2，邹仕洪1 ，张波2（1.北京邮电大学 网络技术研究院，北京 100876；2.中国科学院 计算技术研究所，北京 100190）摘要: 针对目前大多数无线传感器网络定位算法只适用于静态节点的不足，利用QR分解的思想对分布式最小二乘算法进行改进，提出了一种分布式移动节点定位算法。该算法先是对每一个信标节点的观测矩阵进行QR分解，然后移动未知节点在距离自己最近邻居信标的QR分解基础上进行更新来估计自己的位置，降低了移动节点定位阶段的计算复杂度。同时进行了参数无偏估计的Cramr-Rao下限分析来估计节点位置可能达到的误差下界。实验结果表

2、明该定位算法在一定程度上降低了节点的计算复杂度，并且具有比较好的定位精度。关键词: 无线传感器网络；QR 分解；定位；Givens 矩阵中图分类号: TP393 Distributed Mobile Node Localization with QR FactorizationLiu Shaoshuai1, Luo Haiyong2, Zou Shihong1, Zhang Bo2(1.Institue of Networking Technology, Beijing University of Posts and Telecommunications, Beijing 100876;2.

3、Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)Abstract: Most localization algorithms in the literature focused on static wireless sensor networks without taking mobility of sensor nodes into account. Aiming at the drawbacks, an efficient approach for localization in

4、mobile sensor networks using QR factorization was proposed. This algorithm first used QR factorization to solve the linear equations for every beacon, and then mobile blind sensors updated the results received from the nearest beacon without computing QR factorization again to estimate the locations

5、, which reduced the mobile blind sensors cost of computation in a large extent. Also the estimation lower bound ( the Cramr-Rao lower bound ) was analyzed for the location error characters in wireless sensor networks. The experimental results show this algorithm can efficiently reduce the cost of co

6、mputation and perform well in locating the mobile blind sensors.Keywords: wireless sensor networks; QR factorization; localization; Givens matrix1 引言收稿日期：2010-04-15 ；修回日期：2010-07-05基金项目：国家自然基金资助项目(60873244, 60973310, 60772070)；北京自然基金资助项目（4102059）Foundation Items: the National Natural Science Foundat

7、ion of China (60873244, 60973310, 60772070); the Natural Science Foundation of Beijing City of China (4102059)定位技术是无线传感器网络的关键支撑技术。目前，大部分无线传感器网络定位算法都只是适用于静态场景，因此在移动传感器网络中，部署区域内节点的随机移动给定位技术带来了新的挑战。国内外针对移动节点定位方面已进行了一些研究。Tilak等1探讨了移动传感器网路中运行节点定位算法的周期问题，认为定位算法需要在定位精度和能量消耗之间综合平衡。Bergamo等2使用两个射频覆盖整个网络的静态信标

8、，基于测距方法实现移动节点定位。Savarese C等3提出了一种分布式的基于测距的鲁棒节点定位算法。Datta等4提出了既可应用于移动节点，也可应用于静止节点的定位算法，不过当节点无线发射范围不是规则圆形时，算法定位精度明显下降。Haiyong Luo等5提出了一种基于均值漂移和联合粒子滤波的移动节点定位方法。黄梅根等6在传统蒙特卡罗的基础上进行改进，通过构建节点运动模型进行运动预测。在基于测距的定位技术中，未知节点通过测量和信标节点之间的距离，利用最小二乘进行定位是无线传感器网络中定位技术中一种易于实现、开销小的定位算法，也是很多WSN定位算法的基础7。本文在分布式最小二乘的基础上进行改进

9、，利用QR分解的思想实现一种适用于移动节点的定位算法。2 基于QR分解的分布式移动节点定位算法在节点定位过程中，主要是通过距离或角度测量未知节点与三个或三个以上信标节点的位置关系，计算得到未知节点的坐标。假设个信标节点的坐标分别为，未知节点的坐标是，该节点到个信标节点的距离分别是。根据二维空间距离计算公式，可以获得一个非线性方程组： (1)求解此方程组就可以得到未知节点的坐标。2.1 分布式最小二乘算法针对非线性定位方程组（1）式，从第一个方程开始分别减去最后一个方程，消去二次项，得线性方程表示为： (2)其中： 利用最小二乘原理可以求解未知节点的最小二乘位置。在上述求解过程中，矩阵求逆的复杂

10、度为，这需要传感器节点大量的能量消耗。为了延长传感器网络的整个生存周期，将上述最小二乘算法改进为分布式计算方法，由服务器节点（服务器节点可以是笔记本或是计算功能强大的节点）来计算复杂度较高的，然后将计算结果发送给每个未知节点，未知节点仅需要根据自己到信标的距离计算，从而大大降低了未知节点的计算开销。在移动节点的定位过程中，未知节点只能接收到自身通信半径范围内的信标节点，这就使得每个未知节点的结果是不同的，从而导致上述算法不再适用。针对分布式最小二乘算法的这种不足，本文利用QR分解的思想对其进行了改进，提出了一种基于QR分解的分布式移动节点定位算法。2.2 基于QR分解的分布式移动节点定位算法由

11、于在求解过程中需要使用QR分解，本节先给出一些QR分解的性质。定理 1 设方阵，则存在正交矩阵和上三角矩阵，使得 (3)推论 1 设矩阵且，则存在阶正交矩阵和阶上三角矩阵，使得 (4)根据推论1，可以得到：(5)因此求解可以转化求解为： (6)由于R是一个上三角矩阵（R的对角线下面的元素都是0），利用向后代入法即可以求解向量。在移动节点的定位过程中，每个未知节点的观测矩阵不同，QR分解的结果也就不同。如果服务器节点为每个未知节点都分别进行一次QR分解，这样的计算代价太大。考虑到未知节点的邻居信标和距离未知节点最近信标的邻居信标在很大程度上是相似的，因此可以利用服务器节点对每个信标节点的观测矩阵

12、进行一次QR分解，然后信标通信范围内的移动节点根据QR更新算法来更新信标QR分解的结果，从而使得每个信标节点通信半径内的未知节点都在相同的QR分解基础进行更新，不必重新计算，降低了系统计算开销。具体的QR更新算法见2.3节。基于QR分解的分布式定位算法如下：Step 1：选择邻居阶段所有的信标节点发送广播消息来确定自己的邻居信标节点Step 2: 初始化阶段信标节点将其位置信息和邻居信息发送给服务器节点Step 3: 预处理阶段服务器节点为每个信标节点计算和 Step 4: 通信阶段服务器节点将预处理结果发送给每个信标节点，信标节点将其预处理结果发送给其通信范围内的未知节点Step 5: 定位

13、阶段未知节点计算自己到信标节点的距离，同时更新最近信标的预处理结果，估计自己的位置2.3 QR更新算法在进行QR更新的时候，引入了矩阵。下面给出矩阵的性质。矩阵的定义如下： (7)其中，矩阵中没有写出的元素都是0。对于，我们设定，于是有，其中(8)由公式（8）可以看出，通过左乘，向量的第行转变为0。因此，变换具有将矩阵中的某一行转化为0的性质。未知节点和其最近信标的观测矩阵很大程度上是相似的，因此在最近信标的QR分解基础上进行更新就存在两种形式：一是在原有观测矩阵基础上增加几行，一是在原有观测矩阵基础上删除几行。在此给出利用变换增加一行的算法，删除一行的算法与前者类似。增加一行：当观测矩阵增加

14、一行时，假设：增加的一行为，位于的第行，于是更新后的矩阵为 (9)在的左边乘上一个置换矩阵，可以将置换到最后一行 (10)由得到 (11)此时，因为是一个上三角矩阵，只需要将最后一行消掉就能够把转换为新的上三角矩阵。此处引入了个矩阵。 (12)于是： (13)3 算法性能分析3.1 算法复杂度分析在基于QR分解的分布式移动节点定位过程中，移动未知节点仅仅需要在距离自己最近信标的QR分解结果基础上利用变换进行QR更新来计算自己的位置，这种算法的复杂度为。而重新计算QR分解的复杂度为，利用2.1节中矩阵求逆方法定位的复杂度为。在主频为1.8GHz，内存为1G的PC机进行仿真测试，各种定位算法计算复

15、杂度如表(1)所示，可以看出当网络节点规模扩大时，利用更新QR的定位算法未知节点的计算功耗比其他两种算法的功耗减少很多。表1 各种算法计算复杂度比较（单位：秒）节点数目QR更新QR重计算矩阵求逆502.52.97.61004.28.315.41506.312.626.520010.718.432.130023.148.670.33.2 参数无偏估计的Cramer-Rao 下限（CRB）本文将未知节点位置的估计看作一个参数估计问题，由估计理论的克拉美-罗界（Cramr-Rao bound，CRB）得到目标位置的无偏估计的方差下限8。假设所有的节点都分布在二维平面内，每个节点通过信号强度来测量该节

16、点与邻居节点的距离。当节点处于节点的射频信号的通信范围内时，称节点为节点的邻居节点，记为。节点的实际坐标为，当时，节点和节点之间的测量距离为 (14)其中为测量误差，通常认为测量误差服从高斯正态分布，并假设。对于未知节点位置的无偏估计为：(15)是Fisher信息矩阵，求期望， 是射频信号强度在位置处的测量值的统计测量模型。Fisher信息矩阵为： (16)对于有M个未知节点的网络，有个元素，其元素计算如下： (17) (18) (19)当且时，有： (20)(21) (22)当时，Fisher信息矩阵的元素为0。4 实验4.1 测距模型公式（23）是经典RSSI测距模型，它根据节点接收信号功

17、率来获取节点间的距离估计。其中为节点发射、节点接收的信号功率，为自由空间条件下参考接收点接收的信号强度，为信标节点到参考接收点的距离，为无线传输衰减系数，与无线传输环境有关，接收功率服从分布，为接收功率均值，为方差，为节点无线发射半径。(23)4.2 基于RSSI测距模型的仿真实验 本节利用matlab对基于QR分解的分布式移动节点定位算法进行仿真验证。实验中设置64个传感器节点随机分布在一个的方格内，测距误差为10%，通信半径为0.55，连通度约为5。仿真实验100次对相对定位误差RMSE进行平均，RMSE为13.19%。定位结果如图(1)所示：图1 基于QR分解的定位算法仿真结果为评估无线

18、通信半径对定位精度的影响，本文在测距误差为10%，不同无线通信半径下进行仿真测试，该算法的定位性能如图(2)所示。从图(2)可以看出，当无线通信半径较小时，节点的邻居数量较少，定位精度较低。随着通信半径的增大，节点邻居数目增多，定位误差逐渐减小，当通信半径为0.55时，定位精度达到最高，定位误差约为13.1%，很接近参数无偏估计的CRB下限。图2 不同无线通信半径下算法定位性能4.3 基于实际测量数据的定位性能本节采用Neal Patwari提供的实测数据集9，对该算法性能进行评测。实验共有44个节点，部署在12米14米的长方形区域，使用RSSI测距方法。节点间使用宽带直接序列扩频通信方式，其

19、中心频率为2.4GHz。每个RSSI值共进行10次测量，其中每个节点各收发5次，使用极大似然估计获得节点间测距估计值。该实测数据集包含较多数量粗差，且随机分布。使用该测距数据集，利用基于QR分解的分布式移动节点定位算法进行定位。定位结果如图(3)所示。图3基于QR分解的实际定位结果（定位误差2.8米）5 结束语本文将QR分解的思想引入分布式最小二乘定位算法，提出了一种基于QR分解的分布式移动节点定位。当未知节点移动至某一区域时，它仅需要更新距离自己最近信标的QR分解结果就能估计出自己的位置，不必要求服务器节点重新为自己进行QR分解。当网络节点规模比较大时，该定位算法具有明显的优势，大大降低了未

20、知节点的计算开销。同时本文通过Cramer-Rao 下限估计理论对节点位置坐标的无偏估计进行分析，可以体现节点坐标估计可能达到的误差下界。实验结果验证了该分布式移动定位算法有效地降低了未知节点的计算开销，并且具有很好的定位精度。参 考 文 献1 TILAK S, KOLAR V, ABU GHAZALEH NB, et al. Dynamic Localization Control for Mobile Sensor NetworksA. In: Proceedings of the 24th IEEE International Performance, Computing and Com

21、munications Conference (IPCCC) C. Phoenix, Arizona. 2005:587-5922 BERGAMO P, MAZZINI G. Localization in Sensor Networks with Fading and MobilityA. In: Proceedings of the 13th IEEE International Symposium on Personal, Indoor and Mobile Radio CommunicationsC. Pavilhao atlantico, Lisbon, Portugal.2002,

22、 2:750-7543 SAVARESE C, RABAY J, LANGENDOEN K. Robust positioning algorithms for distributed Ad-hoc wireless sensor networks A. In: Proceedings of the USENIX Technical Annual ConferenceC. Monterey. 2002. 317-3274DATTA S, KLINOWSKI C , RUDAFSHANI M, et al. Distributed Localization in Static and Mobil

23、e Sensor NetworksA. In IEEE International Conference on Wireless Mobile Computing, Networking and Communications (WiMob)C. Montreal Canada .2006:69-76 5 LUO HAIYONG, LI JINTAO, ZHU ZHENMIN, et al. Mobile Node Localization Based on Mean Shift in Wireless Sensor NetworksA. The Third International Conf

24、erence on Pervasive Computing and Applications. (ICPCA2008)C. 06-08 October 2008, Alexandria, Egypt. Vol.1 pp.248-2536 黄梅根,常新峰. 一种基于蒙特卡罗的无线传感器网络移动节点定位算法研究J. 传感技术学报, 2010, 23(4):562-5667 王建刚,王福豹,段渭军. 加权最小二乘在无线传感器网络定位中的应用J. 计算机研究与发展,2006,23(9):41-438 LARSSON EG. Cramer-Rao Bound Analysis of Distribute

25、d Positioning in Sensor Networks. IEEE Signal Processing LettersJ, 2004,11(3):334-3379 PATWARI N, ASH J.N., KYPEROUTAS, et al. Locating the Nodes: Cooperative Localization in Wireless Sensor Networks, IEEE Signal Proc. Mag. J, 2005, 22(4):54-69 作者简介：刘少帅（1985-），男，山东潍坊人，北京邮电大学硕士研究生，主要研究方向为普适计算和无线传感器网络定位。罗海勇（1967-），男，湖北麻城人，博士，中国科学院计算技术研究所高级工程师，主要研究方向为嵌入式系统、智能定位与跟踪、视频处理。邹仕洪（1978-），男，江西抚州人，博士，北京邮电大学副教授，主要研究方向为服务质量、服务管理、移动自组网、无线传感器网络。张波（1984-），男，山西阳泉人，中国科学院计算技术研究所博士研究生，主要研究方向为无线多媒体传感器网络、嵌入式系统、计算机视觉。