第36卷　增刊Ⅰ2008年　10月　华　中　科　技　大　学　学　报(自然科学版)J.Huazhong Univ.of Sci.&Tech.(Natural Science Edition )Vol.36Sup.Ⅰ　Oct.　2008收稿日期:2008207215.作者简介:郝志凯(19832),男,博士研究生,E 2mail :zk -hao @.基金项目:国家高技术研究发展计划资助项目(2006AA11Z225);国家自然科学基金资助项目(60635010,60605026).无线传感器网络定位方法综述郝志凯　王　硕(中国科学院自动化研究所复杂系统与智能科学实验室,北京100190)摘要:介绍了国内外研究机构在无线传感器网络定位方法方面开展的研究工作,并对这些研究工作进行了归纳和总结.定位的基本方法分为距离式定位和非距离式定位.距离式定位是通过测量距离或角度进行位置估计,测量数据的精度对定位精度有很大影响.非距离式定位是通过节点间的hop 数或估计距离计算节点的坐标,这种方法不需要测量距离或角度,利用估计距离代替真实距离,算法简单但精度不高.无线传感器网络中定位方法的应用需要针对不同的应用场合,综合考虑节点的规模、成本及系统对定位精度等要求来进行设计和选择.关　键　词:无线传感器网络;定位方法;距离式定位;非距离式定位;相对定位中图分类号:TN919.2;TP732 文献标识码:A 文章编号:167124512(2008)S120224204Survey on localization algorithms for wireless sensor net w orksH ao Zhi k ai W ang S huo(Laboratory of Complex Systems and Intelligence Science ,Institute of Automation ,Chinese Academy of Sciences ,Beijing 100190)Abstract :Current researches in wireless sensor networks (WSNs ′)localization algorit hms are int ro 2duced ,and t hese researches are analyzed and concluded.The p recision of t he nodes ′locations are im 2portant for t he data ′s effectiveness in WSNs ′.The localization algorit hms are divided into range 2based and range 2free.Range 2based algorit hms use t he measured distance and angle to calculate t he nodes ′coordinates.However ,t he range 2f ree researches use hop s or evaluated distance to localization ,which are simple but low 2precision.In different occasions ,t he algorit hm should be taken account in t he net 2work ′s size ,co st ,p recision and so on.K ey w ords :wireless sensor networks (WSNs ′);localization ;range 2based ;range 2f ree ;relative po sitio 2ning 目前广泛使用的全球卫星导航定位系统GPS 可用来确定携带者的绝对位置,但不适合在无线传感器网络中大量使用.主要有以下原因[1]:a .成本高.无线传感器网络中的节点数量多、分布密集,如果各节点都配备GPS 接收器成本很高;b .能源限制.网络中的节点通常是通过内部电池进行供电,由于其工作环境有时在森林、山地等人迹罕至的地方,对其进行电源更换困难;c .工作环境限制.节点有时会分布在室内等电磁波较难到达的环境中,这种工作环境下GPS 无法完成定位任务;d .尺寸较大.由于上述种种原因使得GPS 不能广泛用在无线传感器网络系统的节点上,这就需要发展适合于无线传感器网络应用的节点定位方法.鉴于无线传感器网络节点在能耗、计算能力、通信能力等方面的限制,其节点的定位方法应该具有分布式、低复杂性、精度较高、通用性较好等特点,国内外的研究机构已开展了大量工作[2～9].本文对无线传感器网络节点间定位的基本原理和国内外开展的相关研究工作进行了介绍和归纳,以便于为无线传感器网络的深入研究与应用提供借鉴.1　节点定位基本原理传感器节点定位过程中,未知节点在获得对于邻近参考节点的距离或估计距离,或获得邻近的参考节点与位置节点的相对角度后,通常使用以下原理计算自己的位置[10].a .三边测量原理.三边测量原理是根据3个已知坐标的节点到未知节点的距离来确定节点坐标.已知A ,B 和C 3个节点的坐标分别为(x a ,y a ),(xb ,y b )和(xc ,y c ),它们到未知节点D 的距离分别为d a ,d b 和d c ,假设节点D 的坐标为(x ,y ),则通过计算可以得到　xy =2(x a -x c )2(y a -y c)2(x b -x c )2(y b -y c )-1・x 2a -x 2c +y 2a -y 2c +d 2c -d 2a x 2b -x 2c +y 2b -y 2c +d 2c -d 2b.b .三角测量原理.三角测量原理是根据3个已知坐标的节点到未知节点的相对角度来确定节点坐标的.已知A ,B 和C 3个节点的坐标分别为(x a ,y a ),(x b ,y b )和(xc ,y c ),假设节点D 的坐标为(x ,y ).对于节点A ,C 和D ,如果弧段A C 在△A B C 内,那么能够唯一确定一个圆,并存在下列公式(x O 1-x a )2+(y O 1-y a )2=r 1;(x O 1-x c )2+(y O 1-y c )2=r 1;(xa -x c )2+(y a -y c )2=2r 21-2r 21cosα,式中:r 1为圆半径;O 1(x O 1,y O 1)为圆心;α为圆心角∠A O 1C.由上式能够确定圆心O 1点的坐标和半径r 1.同理可对A ,B ,D 和B ,C ,D 分别确定相应的圆心和半径.最后利用三边测量法,由点O 1,O 2,O 3与D 的距离确定D 的坐标(x ,y ).c .极大似然估计原理.极大似然估计原理是根据n 个已知坐标的节点到未知节点的距离来确定节点坐标的.已知n 个节点的坐标分别为(x 1,y 1),(x 2,y 2),…,(x n ,y n ),它们到未知节点D 的距离分别为d 1,d 2,…,d n ,假设节点D 的坐标为(x ,y ).通过计算可以得A X =b .使用标准最小均方差估计方法可以得到节点D 的坐标为X ^=(A T A )-1A T b .(3) 极大似然估计原理利用了n 个点的数据来对未知节点进行定位,与三边测量原理相比,它可以减小距离误差对定位精度的影响.2　定位方法研究进展根据使用的不同测量量,无线传感器网络中的定位方法分为距离式定位和非距离式定位.距离式定位利用节点间的距离来计算节点的相对位置.距离式定位方法的精度在很大程度上取决于测量节点间距离的精度.目前常用的距离测量方法有TOA ,TDOA 和RSSI.利用角度定位的方法也属于距离式定位.非距离式定位无需测量节点间的绝对距离或方位,利用节点间的估计距离或求区域质心来计算节点的位置.2.1　中心算法N.Bulusu 和J.Heidemann 在文献[2]中提出了一种非距离式的中心算法.传感器网络中包含参考节点和普通节点.参考节点的位置或坐标都已知为(X i ,Y i ),普通节点利用接收到的参考节点的位置或坐标来估算自己的位置或坐标:　(X est ,Y est )=[(X 1+X 2+…+X k )/k ,(Y 1+Y 2+…+Y k )/k ]. 这种定位方法简单易行,通过计算k 个参考节点的中心来估计普通节点的位置或坐标,但误差较高,要得到较高的定位精度需要很多参考节点且均匀分布在网络的外围.2.2　A PIT 算法T.He 和C.Huang 在文献[3]提出的A PIT (app roximation point 2in 2t riangulation test )是一种非距离式的定位方法.对普通节点在能通信到的所有参考节点中选择3个,然后测试是否在由这3个参考节点所组成的三角形区域中,即PIT 检测;改变参考节点组合再进行测试直到所有的组合被测试或达到所需的精度,这些三角形会形成一个重叠区域,计算该区域的中心即为节点的位置.算法的关键在于PIT 检测和区域的融合.PIT 检测判断一点是否在由另外三点组成的三角形区域内,若点M 在区域内,则M 沿任一个方向移动都会靠近或偏离至少一个顶点;若M 在区域外,则至少存在一个方向,当M 沿着这个方向移动时会同时靠近或偏离所有的顶点.在实际定位时,不可能让节点M 移动,这就需要PIT 的逼近方法A PIT.A PIT 是利用M 临近的节点代替M 的移动进行计算.当节点分布不均匀时,A PIT 会・522・增刊Ⅰ 郝志凯等:无线传感器网络定位方法综述 产生判断错误.文献[3]说明当相邻节点为6个或6个以上时,误判不超过14%.A PIT适用于节点随机分布且不要求各节点通信能力完全一样,定位精度在很大程度上取决于融合区域的大小,如果节点能通信到的参考节点数量很少,就会出现较大误差.2.3　A PS算法D.Niculescu和B.Nat h在文献[1]中提出了A PS(Ad2hoc po sitioning system)算法,分为DV2hop和DV2distance算法.DV2hop算法提出了估计节点之间最短距离的方法.在该算法中,每个节点只和它直接相邻的节点通信.参考节点发送位置信息,收到位置信息的普通节点将跳数加1并转发参考节点的位置信息,这样所有的节点都可以连通.每个参考节点计算到其他参考节点的距离和跳数,利用下面的公式计算该节点每一跳的平均距离,d i=∑(X i-X j)2+(Y i-Y j)2∑h j(i≠j),式中:h j是节点i到节点j的跳数;(X j,Y j)是参考节点j的坐标.参考节点把该距离信息传送到周围的节点.普通节点接收距离最近参考节点的距离信息并以此进行定位.DV2distance是用两个相邻节点之间的距离代替平均距离.这种方法不要求节点有长距离通信能力,可以节省能量.在DV2hop中,一跳的距离实际上是一种平均距离,当相邻节点间的距离差异比较大时,会出现较大的误差.DV2distance则用相邻节点的距离代替平均距离,定位精度更高,但也同时提高了对硬件的要求,成本增加.这两种方法在节点密度大和网络连通性强的情况下定位精度较高.2.4　MDS算法Y.Shang和W.Ruml等在文献[4]和[5]中利用多维排列(MDS,multidimensional scaling)的数据分析方法来解决传感器网络中节点的定位问题,根据节点间的信息不同(例如与其他节点的距离)对节点进行定位.然后对距离矩阵进行奇异值分解得到节点初始坐标,再进行优化使这些坐标满足其间的距离关系.距离矩阵B= -0.5J D(2)J,其中:J=I n×n-n-111×n・1′n×1;D(2)是节点间距离的平方组成的矩阵;n表示节点数.由B=XX′,求出B的最大的2(二维)或3(三维)个奇异值和对应的奇异向量,便得出X=U r V1/2r,其中:r=2或3;V r表示r个最大的奇异值组成的向量;U r表示r个最大奇异值对应的奇异向量.然后对整个网络节点坐标进行线形变换得到绝对位置坐标.当网络中节点数量较多时,相距较远的节点的距离误差较大,利用该算法得出的位置误差大且距离矩阵维数大,使计算复杂.为此,文献[5]进一步提出了基于MDS的局部定位算法,设定跳数范围,网络中的每个节点在该跳数范围内进行局部定位,然后融合局部定位图得到全局定位图.局部定位算法不需要估计相距较远节点的距离,从而提高了定位精度,而且适合于有大量节点的传感器网络.此外,在不同的节点上同时进行局部定位实现分布式计算.利用距离定位的精度要比利用跳数定位的精度高.2.5　SHARP算法文献[6]提出一种SHA RP(simple hybrid absolute2relative positioning)定位方法.这种方法先在传感器网络节点中选择N r个节点,将这些节点作为参考节点但不要求知道其坐标.这N r 个节点利用相对定位方法M1确定一个相对坐标系以及它们在这个坐标系中的坐标.最后网络中的其他节点利用定位方法M2确定自身在上述坐标系中的坐标.在SHARP中,参考节点的选择有2种方法:随机法和外围节点法.M1选择MDS 定位算法,M2选择DV2distance定位算法. SHARP结合了MDS和DV2distance算法的优点:用MDS确定参考节点相对坐标精度较高,并且避免了计算所有节点组成的距离矩阵;DV2dis2 tance算法易于实现.经实验验证,在节点密度高连通性好的传感器网络中,SHA RP算法的定位精度要高于DV2distance和MDS的.2.6　PRI信息算法X.Li和H.Shi在文献[7]中提出了一种代替距离与跳数信息的PRI(partial range informa2 tio n)进行定位的方法.PRI是随着距离增减而增减的单调变化的信息,但与距离没有确定的函数关系.例如接收到的信号强度就是一种PRI信息.在以前的非距离定位方法中,不考虑相邻节点间的距离差异,把它们的跳数都设为1,这样在定位时就引入了误差.利用PRI信息可以解决这个问题,通过接收到的相邻节点间的PRI信息的差异对1跳内的节点进行分级,分级越多估计越准确.文献[7]提出了三种不同的分级模型:线性模型、最值线性模型和区域模型.仿真试验结果表明,区域模型要优于前两种,它利用泊松分布来确定相邻节点处于哪个级.通过与MDS和A PS算法的比较,当距离测量误差在15%～35%之间时,PRI算法的定位精度更高.・622・ 华　中　科　技　大　学　学　报(自然科学版)　第35卷2.7　基于移动参考节点的定位算法下面介绍两种基于移动参考节点的定位方法[11,12].文献[11]用移动机器人投放节点,每次投放一个节点并对该节点进行定位.在投放节点前,需要设定一个坐标系,将三个静止的参考节点分别标定为(0,0),(0,l)和(l,0),投放的第一个节点通过测量与这三个参考节点的距离来确定自己的坐标,然后变为参考节点,作为后续节点定位的参照.这种算法只适用于某些特定的场合,要求投放节点后,节点的位置不能改变,只能进行一次定位.文献[12]提出了MBAL(mobile beacon2as2 sisted loc2alization scheme)定位方法,利用一个移动的节点对整个网络中的节点进行定位.移动节点随时知道自己的坐标或位置,在移动过程中,发送位置信息,周围的节点测量与移动节点不同位置的距离.当周围节点测量到与移动节点的三个或三个以上的位置信息时,利用三边定位原理确定自己的位置,当节点确定自己位置时,变为参考节点.考虑到移动节点的能量损耗比较大,文中主要对移动节点的路径作了规划.这两种方法虽然在定位方法上没有提出新的思想,但提供了一种新的定位机制,就是利用移动节点的自身可定位性和可移动性在网络的局部或整体对相关的节点进行定位,可以避免网络多跳和远距离测量的误差.移动节点的路径规划算法和采取的定位机制需要深入考虑.本文对无线传感器网络中的基本定位原理、国内外研究现状进行了归纳和介绍.目前研究的各类定位算法都是在综合权衡能耗、成本和精度等因素的基础上提出来的,其计算量、精度等方面也存在较大差别,适合的应用范围也各不相同.因此,无线传感器网络中定位方法的应用需要针对不同的场合,综合考虑节点的规模、成本及系统对定位精度等要求来设计和选择.同时,对于具有分布式、低复杂性、高精度、通用性等特点的无线传感器网络定位方法还有待进一步深入研究.参考文献[1]Dragos Niculescu,Badri Nash.Ad Hoc positioningsystem(A PS)[J].G lobecom Telecomunications, 2001,5:292622931.[2]Nirupama Bulusu,John Heidemann,Deborah Estrin.GPS2less low2cost outdoor localization for very small devices[J].IEEE Personal Communications,2000,7(5):28234.[3]He T,Huang C,Blum B M,et al.Range2f ree locali2zation schemes for large scale sensor networks[C]∥Mobi Com2003,San Diego:[s.n.].2003:81295.[4]Shang Y,Ruml W,Zhang Y,et al.Localizationf rom connectivity in sensor networks[J].Parallel andDistributed Systems,IEEE Transactions on,2004, 15(11):9612974.[5]Shang Y,Ruml W.Improved MDS2based localization[J].IEEE Info2Com,2004,15(1):9612974.[6]Ahmed A A,Shi Hongchi,Shang Y i.SHARP:anew approach to relative localization in wireless sen2 sor networks[C]∥Distributed Computing Systems Workshops,2005.25th IEEE International Confer2 ence.[s.n.],2005:8922898.[7]Li Xiaoli,Shi Hongchi,Shang Y i.A partial2rang2a2ware Localization algorithm for ad2hoc wireless sen2 sor networks[C]∥In Distributed Compution Ssytems Workshops2004,Proceedings.24th International Conference.[s.n.],2004:77283.[8]Niculescu D,Nath B.Ad hoc positioning system(A PS)using AOA[J].IEEE Iinfocom,2003,13:173421743.[9]Nasipuri A,Li K.A directionality based location dis2covery scheme for wireless sensor networks[C]∥First ACM International Workshop on Wireless sen2 sor Networks and Applications.[s.n.],2002:1052 111.[10]孙黎民,李建中,陈　渝,等.无线传感器网络[M].北京:清华大学出版社,2005.[11]Zhang Y ing,Huang Qingfeng,Liu J uan.Sequentiallocalization algorithm for active sensor network de2 ployment[C]∥Proceedings of the20th InternationalConference on Advanced Information Networkingand Applications(A INA′06).[s.n.],2006,2:1712178.[12]K im Kyunghwi,Lee Wonjun.MBAL:a mobile bea2con2assisted localization schem for wireless sensornetworks[C]∥ICCCN2007.Proceedings of16thInternational Conference.[s.n.],2007:57262.・722・增刊Ⅰ 郝志凯等:无线传感器网络定位方法综述 。