加权最小二乘法在无线传感器网络中的应用

第9期王建刚等:加权最小二乘估计在无线传感器网络定位中的应用・ 41 ・

加权最小二乘估计在无线传感器网络定位中的应用

王建刚, 王福豹, 段渭军

(西北工业大学宽带网络技术研究所, 陕西西安710072)

*

摘 要:节点自身定位是目前无线传感器网络领域研究的重点之一, 定位误差累积问题是节点定位中必须解决的一个关键问题, 利用加权最小二乘估计的方法可以有效抑制累积误差的影响。介绍了如何将加权最小二乘估计应用于节点定位以及如何合理地选择加权系数以降低定位误差。仿真实验表明, 运用加权最小二乘估计可以有效地抑制误差累积的影响, 提高定位精度。

关键词:节点定位; 无线传感器网络; 加权最小二乘估计

中图法分类号:TP301 文献标识码:A 文章编号:1001-3695(2006) 09-0041-03

Applicat ion of Weigh ted L east Squar e Est im a tes on

Wir eless Sen sor N etw ork N ode Localiza tion

WANG J ian-ga ng, WAN G Fu-bao, DU AN Wei-jun

(Institute of Br oadband Network, Nor thwes ter n Polytechnical Univers ity, Xi ’an Shanxi 710072, China)

Abst ract :N ode localiza tion is a hot spot in int ernat ional res ea rch of Wireles s Sensor Netw ork (WS N) . Locat ion error cum u-lat e is a key problem to deal w it h in node loca lizat ion. Error cum ulat e could be rest rained effectively by us ing Weig ht ed Least

S quare Est im a tes (WLS E) . How t o apply WL SE to node localizat ion a lg orithm and choose proper weig ht coefficient t o reduce locat ion error are introduced. S im ulat ions s tudies show that WLS E perform well by restra in the error cum ula te a nd im prove lo-cat ion precision.

Key words:N ode Localiz at ion; Wireles s Sens or Netw ork(WSN ) ; Weighted Leas t Square Es tim at es(WLS E) 无线传感器网络(Wireles s S ensor N etw ork, WS N) 是指由大量成本低廉的, 具有感知能力、计算能力、无线通信能力的传感器节点组成的网络。WS N 一般被密集地部署在特定的监控区域, 节点间以无线、多跳的通信方式自组织网络拓扑结构, 节点间通过协同工作完成单个节点不能完成的全局任务。WS N 在军事、环境、医疗和商用领域均有很高的应用价值。

由于无线传感器网络通常部署于人员不能到达或敌对的区域, 因此决定了传感器节点在部署时的不可控制性, 同时传感器节点受到成本、能量和体积的限制, 不可能为每个节点装配GPS 接收器。这样, 网络中大多数节点的位置不能事先确定, 而WS N 的大量应用均需要节点的地理位置信息从而获知信息来源的准确位置, 或者利用节点位置信息设计路由算法以提高路由效率等。所以节点定位问题已成为无线传感器网络的一个首要解决的问题。近年来, 国外的大学和研究机构提出了许多专用于传感器网络的定位系统[1], 基于测距的定位方法是常用的定位方法。

b =

二乘估计的算法。当未知节点获得与三个或三个以上锚节点的距离时, 可以执行三边测量定位(Trilat erat ion) 或多边测量定位(Mult ilat era tion) 。设未知节点坐标为A(x, y) , 锚节点坐标为L 1(x 1, y 1) , …, L k (x k , y k ) , 未知节点到锚节点的距离分别为r 1, r 2, …, r k , 则可根据测量值与已知量建立线性方程组。

A x =b

(x 1-x k )

(y 1-y k ) (y 2-y k ) …

(y k -1-y k )

, x =

x , y

(x 2-x k ) …

(x k -1-x k )

(1)

其中, A =-2×

22222

r 21-r k -x 1+x k -y 1+y k 22222r 22-r k -x 2+x k -y 2+y k

…r 2k -1

2

-r 2k -x k -1

22

+x 2k -y k -1+y k

由于存在测距误差, 合理的线性模型应该是

A x +N =b

(2)

其中, N 为k -1维随机误差向量。利用最小二乘原理, x 的值应当使模型误差N =b -Ax 达到最小, 即用最小化Q(x) =‖N ‖2=‖b -Ax ‖2求x 的估计, 对Q(x) 关于x 求导并令其等于0, 可以求解未知节点的最小二乘位置估计:

x ^LS =(A T A )

-1

1 三边测量定位

本文将WSN 中需要定位的节点称为未知节点; 而已知位置并协助未知节点定位的节点称为锚节点(Anchor) 。

目前提出的基于测距的定位算法中, 最常用的是基于最小收稿日期:2005-08-09; 修返日期:2005-09-25

基金项目:国家自然科学基金资助项目(60472074) ; 西北工业大学研究生创业种子基金资助项目(Z200568)

A T b

(3)

2 加权最小二乘定位方法

为了降低成本, WSN 中锚节点所占的比例应尽可能地小, 但锚节点的比例越小必然会降低定位节点的覆盖率。在很多定位算法中, 为了提高定位节点的覆盖率, 将已经定位的节点

升级为锚节点, 利用升级的锚节点迭代定位将定位节点的范围逐步扩展到整个网络。但是这种迭代的方法引入了误差累积的问题:升级的锚节点本身可能存在较大的位置误差, 从而在下一轮的定位估计中引入了更大的误差, 当网络规模较大时, 误差累积的影响造成的位置误差将会无法接受。

为了解决误差累积问题, 引入了加权最小二乘估计的方法, 即根据每个锚节点的位置精度, 在最小二乘估计中采用不同的加权系数进行定位计算, 以提高定位精度。加权最小二乘估计可按下式求解:

x ^W LS =(A T WA )

-1

A T Wb

(4)

式中, W 是加权矩阵, 为保证x ^WLS 是无偏估计或最小方差无偏估计, 加权矩阵W 有特殊的要求, 在实际应用中一般要求W 为对称正定矩阵。利用许瓦兹不等式可以证明, 在测距误差与距离之比为独立分布的高斯随机变量的条件下, 当W =R -1时, ^x W LS 的估计均方误差最小[2, 3], R 为测距误差的方差矩阵, R =E{NN T }。

在节点定位中, 未知节点到锚节点距离值的误差是由测距误差和锚节点的位置误差两部分叠加组成的, 这样就使得距离值的误差难以估计, 因此实际求解时, 加权矩阵W 是无法利用先验信息生成的。在WS N 定位的实际应用中, 加权系数一般需要预先设定, 例如在Sa va rese 等人

[5]

提出的Robus t Positio-

ning 定位算法中, 使用了在迭代求精过程中逐步提高节点权值的方法, 权值取0～1之间, 锚节点权值设为1, 已定位节点的初始权值从0. 1开始, 在每一次的迭代求精过程中, 以0. 1为步长逐步提高其权值。

3 Hop-Euclidean 算法

[8]

与误差累积问题

美国路特葛斯大学(Rut gers U niversit y) 的Niculescu 等人提出了一种命名为Euclidea n 的定位算法

[6, 7]

, 该算法利用几何

原理提出了一种计算与锚节点相隔两跳的未知节点位置的方法。Hop-E uclidea n 算法[8]是在E uclidea n 算法的基础上融入距离矢量路由和迭代循环的思想而设计出的一种新的定位算法。

Hop-E uclidean 算法定义了三种节点, 即Anchor, Orphan 和g et Fina l, 分别用于标志该节点为锚节点、无法定位的节点和未升级为锚节点的已定位节点。算法由三个阶段组成:

(1) 初始化阶段。所有节点广播一个Hello 消息用于相邻节点相互发现及节点间RS SI 测距, 所有未知节点根据接收到的信息生成邻居节点和锚节点链表。锚节点将其Anchor 标记设置为真; 假如某个未知节点的邻居节点少于三个, 这些节点就将其Orphan 标记设置为真, 并在算法的下一阶段告知邻居节点将不能从它这里得到任何位置信息。

(2) 定位阶段。锚节点广播TTL 域为2, 包括节点ID 、自身位置信息的信标消息, 经过一段时间, 未知节点就可获得与它相隔两跳内的所有锚节点和中间节点的相关信息。当未知节点获得满足计算两跳距离条件的信息后, 即可使用毕达哥拉斯定理计算与锚节点的两跳距离; 当未知节点获得与三个及三个以上锚节点距离后即可利用最小二乘定位算法进行定位计算, 并对计算结果进行合理性验证。如果通过验证则升级为锚节点, 置Anchor 标记; 如果三次循环不能通过验证, 则置g et Fi-

na l 标记, 接受其位置估计, 但并不升级为锚节点。

(3) 迭代循环阶段。在定位阶段已定位的节点可以升级为锚节点, 这些节点也开始发送信标消息, 即再次开始第(2) 阶段, 将定位的节点的范围不断扩大。当所有节点的Anchor 或Orpha n 或getF inal 标记均为真时, 则完成定位过程, 退出定位算法。

更详细的算法描述可参阅文献[6～8], 我们更关注的是大规模网络中的误差累积问题。在Hop-Euclidean 算法中, 为了抑制累积误差的影响, 在定位阶段使用了验证的过程。在未知节点执行定位计算后, 使用自身的估算位置与已知的锚节点信息做验证计算。例如, 未知节点A 与锚节点L 相隔两跳, 那么A 到L 的距离d AL 就应该满足r

本文在Hop-E uclidea n 算法的基础上引入加权定位算法, 进一步抑制了定位误差累积的影响。在定位阶段, 对于升级为锚节点的节点赋予一个合理的权值, 该权值用于形成加权矩阵, 在下一轮定位计算过程中, 使用加权最小二乘算法进行节点位置计算。

4 定位算法仿真

为了检验和比较加权最小二乘算法对定位估计的影响, 使用了NS -2网络仿真平台对算法进行仿真。N S 是美国DARPA 支持的项目VIN T(Virtual Int erN et work Test bed) 开发的通用多协议网络仿真平台, 经过不断改进, U C Berkeley 发布了N S-2, 目前已被网络研究者广泛采用

[9]

。

仿真中, 将节点射频通信距离设置为10m , 测距精度使用相对误差表示, 如10%的测距误差表示误差为射频通信距离的10%, 测距误差服从高斯分布。分别在60m ×60m , 50m ×50m 和45m ×45m 的正方形二维区域随机部署100个节点(网络平均连通度分别为7. 5, 10. 5和12. 5) , 在1%, 5%, 10%, 20%, 30%, 40%, 50%的测距误差条件下各仿真50次。

仿真过程分两个阶段, 第一阶段用来分析不同条件下如何选择合理的加权系数。由于实际定位计算过程中无法获得定位误差的先验信息来确定权值, 为了比较不同权值对于定位精度的影响, 对于符合加权最小二乘定位算法的节点, 使用了0. 01, 0. 02, 0. 03, 0. 04, 0. 05, 0. 06, 0. 07, 0. 08, 0. 09, 0. 1, 0. 2, 0. 3, 0. 4, 0. 5, 0. 6, 0. 7, 0. 8, 0. 9几种权值分别计算, 以验证权值取多大才能达到最小的定位误差。通过对仿真结果的分析发现, 当测距误差增大时, 能够达到最小定位误差的权值有减小的趋势, 但这种趋势并不明显, 如第3节所述, 这正是由于测距误差与锚节点的位置误差叠加的影响造成的。图1给出了不同测距误差下取0. 08、0. 1、0. 2三种权值时达到最小定位误差的节点占参与加权运算节点的比例。

经过对第一阶段的仿真分析确定了取加权系数的方法。当测距误差小于10%时, 加权系数取0. 2; 当测距误差为10%～20%时, 加权系数取0. 1; 当测距误差为30%～50%时, 加权系数取0. 08。每经过一次迭代循环, 由于再次升级的锚节点的

位置精度会下降, 所以其权值比上一轮循环减小0. 02。

[1**********]

10

2030

Range Error(%R)

40

50

加权最小二乘估计的方法, 应用于Hop-E uclidea n 定位算法中, 以抑制定位迭代循环过程中误差累积的影响。利用仿真实验确定了一个较优的加权方法, 最后的仿真结果表明该方法能够获得更高的定位精度。参考文献:

[1]

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

陈希孺, 王松桂. 线性模型中的最小二乘法[M]. 上海:上海科学技术出版社, 2003. 1-26. [3]

沈凤麟, 叶中付, 钱玉美. 信号统计分析与处理[M]. 合肥:中国科学技术大学出版社, 2001. 365-373. [4]

范平志, 邓平, 刘林. 蜂窝网无线定位[M]. 北京:电子工业出版社, 2002. 61-86. [5]

C Savar ese, J Ra bay, K Langendoen. Robust Positioning Algorithms for Distr ibuted Ad hoc Wireless S ensor Networ ks[A]. Car la S chlatter E llis. Proceedings of the US ENIX Technical Annual Conference[C]. M onter ey:USE NIX Pr ess, 2002. 317-327. [6]

Dra gos Nicolescu, Badr i Nath. Ad hoc Positioning Systems (APS) [C]. Pr oceedings of IEEE Global Telecommunications C onfer ence, S an Antonio:IEEE Communications S ociety, 2001. 2926-2931. [7]

D Niculescu, B Nath. DV Based Positioning in Ad hoc Netw orks[J ]. J ournal of Telecommunication Systems, 2003, 22(4) :267-280. [8]

史龙. 无线传感器网络自身定位算法研究[D]. 西安:西北工业大学, 2005. 38-42. [9]

徐雷鸣, 庞博, 赵耀. NS 与网络模拟[M]. 北京:人民邮电出版社, 2003. 2-8.

图1测距误差对权值的影响

图2和图3给出了当锚节点比例为10%、网络平均连通度分别为12. 5和7. 5时定位估计的误差随测距误差变化的情况, 其中实线表示由式(3) 计算的未加权的Hop-E uclidea n 定位算法, 虚线表示由式(4) 计算的加权最小二乘定位算法得到的统计结果。可见, 利用加权最小二乘估计的定位算法可以达到较小的定位误差, 当测距误差增大时, 加权最小二乘定位算法的定位精度提高的趋势更为明显。

[**************]00

[**************]00

10203040Range Error(%R)

图2定位误差对测距误差

( 连通度12.5)

50

10203040Range Error(%R)

图3

( 连通度7.5)

50

作者简介:

王建刚(1974-) , 男, 陕西人, 硕士研究生, 主要研究方向为无线传感器网络与嵌入式计算技术; 王福豹(1963-) , 男, 山西人, 教授, 博士, 主要研究方向为计算机网络、流媒体、传感器网络等; 段渭军(1962-) , 男,

定位误差对测距误差

5 结论

为提高基于测距的无线传感器网络节点定位精度引入了(上接第40页)

陕西人, 高工, 博士, 主要研究方向为流媒体、无线通信等。

了非结构型P2P 和结构型P2P, 归纳了DHT 的性质与特点, 并对几种现有的DHT 进行了介绍, 最后指出DHT 现存的主要问题并提出了可能的解决方案。参考文献:

[1][2]

nutella Homepage[EB/OL]. http://www. gnutella. com.

Ion S toica, Robert Mor ris, David Liber nNowell, et al . Chord:A S ca-lable Peer-to-Peer Lookup Protocol for Inter net Applications [J]. IEEE/ACM Tr ans. on Networ king, 2003, 11(1) :17-32. [3]

Ben Y Zhao, J ohn Kubiatowicz, Anthony D J oseph. Ta pestry:An In-fr astructure for Fault-toler ant Wide-ar ea Location and Routing[R]. Tech. Report No. UCB /CS D-01-1141, 2001. [4]

Indranil Gupta, Ken Birman, Pra kash Ling a, et al . Kelips:Building an Efficient and S table P2P DHT through Increased Memory and B ackgr ound Over head[C]. Berlin:The 2nd Inter national Workshop on Peer-to-Peer Sy stems, 2003. 160-169. [5]

Ratnasa my S, Fr ancis P, et al . A S calable Content-a ddr essable Net-w ork[J]. Proc. of AC M SIGC OM M, 2001, 31(4) :161-172.

3. 5 实现方式问题

考虑到在实际的P2P 中, DHT 为上层应用提供服务, 其具体实现方式同样也是一个有待研究的问题。传统上, DHT 被作为库来实现, 作为库来实现的好处是提供了很大的灵活性; 而它的一个弊端是不具有通用性, 对于每个不同的上层应用都需要开发不同的DHT 。

DHT 同样也可以作为服务来实现, 这需要为上层应用定义并提供一组严格的接口。OpenDHT 在这一方面进行了尝试, 它为外界提供了公共的DHT 服务。对于客户端来说, 它们不再需要运行DHT 节点, 而仅仅需要向DHT 节点发出PU T 和GET 操作命令, 这些DHT 节点就会执行相应的操作。这种DHT 的服务模型使客户端不需要关心DHT 的部署和维护, 简化了上层应用的开发和部署。

4 总结

DHT 是P2P 中一类重要的查找、定位和路由的基础设施, 为广域文件存储、文件和服务分布索引以及大规模分布计算平台等大规模分布式的P 2P 应用提供了重要的服务。本文介绍

作者简介:

袁霖(1980-) , 男, 硕士研究生, 研究方向为对等网络、分布式计算; 覃征(1956-) , 男, 教授, 博导, 博士, 研究方向为分布式计算、移动计算、软件体系结构、计算机系统集成与电子商务。