无线传感器网络中的自身定位系统和算法

Vol.16, No.5 ©2005 Journal of Software 软 件 学 报 1000-9825/2005/16(05)0857 无线传感器网络中的自身定位系统和算法∗ 王福豹 1+, 史 龙 1, 任丰原 2 1(西北工业大学 宽带网络研究所,陕西 西安 710072) 2(清华大学 计算机科学与技术系,北京 100084) Self-Localization Systems and Algorithms for Wireless Sensor Networks WANG Fu-Bao1+, SHI Long1, REN Feng-Yuan2 1(Institute of Broadband Network, Northwest Polytechnical University, Xi’an 710072, China) 2(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China) + Corresponding author: Phn: +86-29-88494908, E-mail: wangfubao@nwpu.edu.cn, http://www.nwpu.edu.cn Received 2004-01-27; Accepted 2004-05-14 Wang FB, Shi L, Ren FY. Self-Localization systems and algorithms for wireless sensor networks. Journal of Software, 2005,16(5):857−868. DOI: 10.1360/jos160857 Abstract: Wireless Sensor Networks, a novel technology about acquiring and processing information, have been proposed for a multitude of diverse applications. The problem of self-localization, that is, determining where a given node is physically or relatively located in the networks, is a challenging one, and yet extremely crucial for many applications. In this paper, the evaluation criterion of the performance and the taxonomy for wireless sensor networks self-localization systems and algorithms are described, the principles and characteristics of recent representative localization approaches are discussed and presented, and the directions of research in this area are introduced. Key words: wireless sensor network; self-localization; positioning 摘 要: 作为一种全新的信息获取和处理技术,无线传感器网络可以在广泛的应用领域内实现复杂的大规模 监测和追踪任务,而网络自身定位是大多数应用的基础.介绍了无线传感器网络自身定位系统和算法的性能评 价标准和分类 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ,着重综述了近年来该领域具有代表性的算法及系统的原理和特点,并指出未来的研究方向. 关键词: 无线传感器网络;自身定位;定位 中图法分类号: TP393 文献标识码: A 微机电系统(micro-electro-mechanism system,简称 MEMS)、无线通信和数字电子技术的进步孕育了无线传 感器网络(wireless sensor network,简称 WSN)[1].通过部署大量传感器节点至目标区域,WSN将改变我们与客观 世界的交互方式.从军事应用、目标追踪、环境检测到空间探索,WSN的未来应用将超出我们的想象力[1−4]. ∗ Supported by the National Natural Science Foundation of China under Grant Nos.60273009, 60472074 (国家自然科学基金) 作者简介: 王福豹(1963－),男,山西运城人,博士,教授,主要研究领域为计算机网络,流媒体,传感器网络;史龙(1975－),男,硕士 生,主要研究领域为传感器网络,分布式计算技术;任丰原(1970－),男,博士,副教授,主要研究领域为网络流量管理与控制,传感器网络, 系统性能评价. 858 Journal of Software 软件学报 2005,16(5) 对于大多数应用,不知道传感器位置而感知的数据是没有意义的[5].传感器节点必须明确自身位置才能详 细说明“在什么位置或区域发生了特定事件”,实现对外部目标的定位和追踪[6].另一方面,了解传感器节点位置 信息还可以提高路由效率[7,8],为网络提供命名空间[9−11],向部署者报告网络的覆盖质量[12,13],实现网络的负载均 衡[14,15]以及网络拓扑的自配置[16].而人工部署和为所有网络节点安装 GPS 接收器都会受到成本、功耗、扩展 性等问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的限制,甚至在某些场合可能根本无法实现,因此必须采用一定的机制与算法实现 WSN的自身定位. 从 1992年 AT&T Laboratories Cambridge开发出室内定位系统 Active Badge[17,18]至今,研究者们一直致力 于这一领域的研究.事实上,已有许多系统和算法能够解决 WSN 自身定位问题.但是,每种系统和算法都用来解 决不同的问题或支持不同的应用,它们在用于定位的物理现象、网络组成、能量需求、基础设施和时空的复杂 性等许多方面有所不同.本文综述了 WSN自身定位技术的性能评价标准、分类,总结了近年来典型的定位系统 和算法. 本文中,将WSN中需要定位的节点称为未知节点(unknown node);而已知位置,并协助未知节点定位的称为 锚节点(anchor node).邻居节点是指在一个节点通信半径内,可以直接通信的节点. 1 无线传感器网络自身定位系统和算法的性能评价 WSN 自身定位系统和算法的性能直接影响其可用性,如何评价它们是一个需要深入研究的问题.下面定性 地讨论几个常用的评价标准. (1) 定位精度.定位技术首要的评价指标就是定位精度,一般用误差值与节点无线射程的比例表示,例如,定 位精度为 20%表示定位误差相当于节点无线射程的 20%.也有部分定位系统将二维网络部署区域划分为网格, 其定位结果的精度也就是网格的大小,如微软的 RADAR[2],Wireless Corporation的 RadioCamera[19]等. (2) 规模.不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个房间内实现定位. 另外 ,给定一定数量的基础设施或在一段时间内 ,一种技术可以定位多少目标也是一个重要的评价指标 .例 如,RADAR[2]系统仅可在建筑物的一层内实现目标定位,剑桥的 Active Office 定位系统[20]每 200ms 定位一个 节点. (3) 锚节点密度.锚节点定位通常依赖人工部署或 GPS 实现.人工部署锚节点的方式不仅受网络部署环境 的限制,还严重制约了网络和应用的可扩展性.而使用 GPS 定位,锚节点的费用会比普通节点高两个数量级[21], 这意味着即使仅有 10%的节点是锚节点,整个网络的价格也将增加 10倍.因此,锚节点密度也是评价定位系统和 算法性能的重要指标之一. (4) 节点密度.在WSN中,节点密度增大不仅意味着网络部署费用的增加,而且会因为节点间的通信冲突问 题带来有限带宽的阻塞.节点密度通常以网络的平均连通度来表示.许多定位算法的精度受节点密度的影响,如 DV-Hop[22,23]算法仅可在节点密集部署的情况下合理地估算节点位置. (5) 容错性和自适应性.通常,定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设备.但 在真实应用场合中常会有诸如以下的问题:外界环境中存在严重的多径传播、衰减、非视距(non-line-of-sight, 简称 NLOS)、通信盲点等问题;网络节点由于周围环境或自身原因(如电池耗尽、物理损伤)而出现失效的问题; 外界影响和节点硬件精度限制造成节点间点到点的距离或角度测量误差增大的问题.由于环境、能耗和其他原 因,物理地维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难或不可行的.因此,定位系统和 算法的软、硬件必须具有很强的容错性和自适应性,能够通过自动调整或重构纠正错误、适应环境、减小各种 误差的影响,以提高定位精度. (6) 功耗.功耗是对WSN的设计和实现影响最大的因素之一.由于传感器节点电池能量有限,因此在保证定 位精度的前提下,与功耗密切相关的定位所需的计算量、通信开销、存储开销、时间复杂性是一组关键性指标. (7) 代价.定位系统或算法的代价可从几个不同方面来评价.时间代价包括一个系统的安装时间、配置时 间、定位所需时间.空间代价包括一个定位系统或算法所需的基础设施和网络节点的数量、硬件尺寸等.资金 代价则包括实现一种定位系统或算法的基础设施、节点设备的总费用. 上述 7个性能指标不仅是评价WSN自身定位系统和算法的标准,也是其设计和实现的优化目标.为了实现 王福豹 等:无线传感器网络中的自身定位系统和算法 859 这些目标的优化,有大量的研究工作需要完成.同时,这些性能指标是相互关联的,必须根据应用的具体需求做 出权衡[24],以选择和设计合适的定位技术. 2 无线传感器网络自身定位系统和算法的分类 2.1 物理定位与符号定位(physical position and symbolic location)[11] 定位系统可提供两种类型的定位结果:物理位置和符号位置.例如,某个节点位于 47°39′17″N,122°18′23″W 就是物理位置;而某个节点在建筑物的 123 号房间就是符号位置.一定条件下,物理定位和符号定位可以相互转 换.与物理定位相比,符号定位更适于某些特定的应用场合,例如,在安装有无线烟火传感器网络的智能建筑物 中,管理者更关心某个房间或区域是否有火警信号,而不是火警发生地的经纬度.大多数定位系统和算法都提供 物理定位服务,符号定位的典型系统和算法有 Active Badge[17,18]、微软的 Easy Living[25]等,MIT的 Cricket定位 系统[26]则可根据配置实现两种不同形式的定位. 2.2 绝对定位与相对定位(absolute versus relative)[11] 绝对定位与物理定位类似,定位结果是一个标准的坐标位置,如经纬度.而相对定位通常是以网络中部分节 点为参考,建立整个网络的相对坐标系统.绝对定位可为网络提供唯一的命名空间,受节点移动性影响较小,有 更广泛的应用领域.但研究发现[27],在相对定位的基础上也能够实现部分路由 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ,尤其是基于地理位置的路由 (geo-routing),而且相对定位不需要锚节点.大多数定位系统和算法都可以实现绝对定位服务,典型的相对定位 算法和系统有 SPA(self-positioning algorithm)[7],LPS(local positioning system)[28],SpotON[29],而 MDS-MAP定位 算法[30]可以根据网络配置的不同分别实现两种定位. 2.3 紧密耦合与松散耦合(tightly coupled versus loosely coupled)[31] 所谓紧密耦合定位系统是指锚节点不仅被仔细地部署在固定的位置,并且通过有线介质连接到中心控制 器;而松散型定位系统的节点采用无中心控制器的分布式无线协调方式. 典型的紧密耦合定位系统包括AT&T的Active Bat系统[10]和Active Badge[17,18],HiBall Tracker[32]等.它们的 特点是适用于室内环境,具有较高的精确性和实时性,时间同步和锚节点间的协调问题容易解决.但这种部署策 略限制了系统的可扩展性,代价较大,无法应用于布线工作不可行的室外环境. 近年来提出的许多定位系统和算法,如 Cricket[26],AHLos[33]等都属于松散耦合型解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 .它们以牺牲紧 密耦合系统的精确性为代价而获得了部署的灵活性,依赖节点间的协调和信息交换实现定位.在松散耦合系统 中,因为网络以 ad hoc 方式部署,节点间没有直接的协调,所以节点会竞争信道并相互干扰.针对这个问题,剑桥 的Mike Hazas等人在文献[34,35]中提出使用宽带扩频技术(如DSSS,DS/CDMA)以解决多路访问和带内噪声干 扰问题. 这种分类方法与基于基础设施和无须基础设施(infrastructure-based versus infrastructure-free)[7]的分类方法 相似,所不同的是,后者是以整个系统除了传感器节点以外是否还需要其他设施为标准. 2.4 集中式计算与分布式计算(centralized computation versus distributed computation)[17] 集中式计算是指把所需信息传送到某个中心节点(例如,一台服务器),并在那里进行节点定位计算的方式; 分布式计算是指依赖节点间的信息交换和协调,由节点自行计算的定位方式. 集中式计算的优点在于从全局角度统筹规划,计算量和存储量几乎没有限制,可以获得相对精确的位置估 算.它的缺点包括与中心节点位置较近的节点会因为通信开销大而过早地消耗完电能,导致整个网络与中心节 点信息交流的中断 ,无法实时定位等 [33].集中式定位算法包括凸规划(convex optimization)[8,36],MDS-MAP[30] 等.N-hop multilateration primitive[37]定位算法可以根据应用需求采用两种不同的计算模式. 2.5 基于测距技术的定位和无须测距技术的定位(range-based versus range-free)[38] Range-Based 定位通过测量节点间点到点的距离或角度信息 ,使用三边测量 (trilateration)、三角测量 860 Journal of Software 软件学报 2005,16(5) (triangulation)或最大似然估计(multilateration)定位法计算节点位置;Range-Free 定位则无须距离和角度信息,仅 根据网络连通性等信息即可实现. Range-Based 定位常用的测距技术有 RSSI[39],TOA[10],TDOA[9]和 AOA[40,41].RSSI(received signal strength indicator)虽然符合低功率、低成本的要求,但有可能产生±50%的测距误差[42];TOA(time of arrival)需要节点间精 确的时间同步,无法用于松散耦合型定位;TDOA(time difference on arrival)技术受限于超声波传播距离有限 (WSN 所使用的超声波信号通常传播距离仅为 20~30 英尺,因而网络需要密集部署)和 NLOS 问题对超声波信 号传播的影响;AOA(angle of arrival)也受外界环境影响,而且需要额外硬件,在硬件尺寸和功耗上可能无法用于 传感器节点.除上述测距技术的局限性以外,range-based 定位机制使用各种算法来减小测距误差对定位的影响, 包括多次测量[43],循环定位求精[44],这些都要产生大量计算和通信开销.所以,range-based 定位机制虽然在定位 精度上有可取之处,但并不适用于低功耗、低成本的应用领域. 因功耗和成本因素以及粗精度定位对大多数应用已足够(当定位误差小于传感器节点无线通信半径的 40%时 ,定位误差对路由性能和目标追踪精确度的影响不会很大 [38]),range-free 定位方案倍受关 注.DV-Hop[22,23]、凸规划[8,36]和 MDS-MAP[30]等就是典型的 range-free 定位算法,其中 MDS-MAP 还可以在 range-based条件下实现更精确的定位. 2.6 粗粒度与细粒度(fine-grained localization versus coarse-grained localization)[4] 依据定位所需信息的粒度可将定位算法和系统分为两类:根据信号强度或时间等来度量与锚节点距离的 称为细粒度定位技术;根据与锚节点的接近度(proximity)来度量的称为粗粒度定位技术.其中细粒度又可细分 为基于距离和基于方向性测量两类.另外,应用在 RadioCamera 定位系统[19]中的信号模式匹配专利技术(signal pattern matching)也属于细粒度定位.粗粒度定位的原理是利用某种物理现象来感应是否有目标接近一个已知 的位置,如 Active Badge[17,18]、凸规划[8,36]、Xeror的 ParcTAB系统[45]、佐治亚理工学院的 Smart Floor[46]等. 2.7 三角测量、场景 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 和接近度定位(triangulation, scene analysis, and proximity)[47] 定位技术也可分为三角测量、场景分析和接近度 3类,其中三角测量和接近度定位与粗、细粒度定位相似. 而场景分析定位是根据场景特点来推断目标位置.通常被观测的场景都有易于获得、表示和对比的特点,如信 号强度和图像.场景分析的优点在于无须定位目标参与,有利于节能并具有一定的保密性;它的缺点在于需要事 先预制所需的场景数据集,而且当场景发生变化时,必须重建该数据集.RADAR[2]系统(基于信号强度分析)和 MIT的 Smart Rooms[48](基于视频图像)就是典型的场景分析定位系统. 3 典型的自身定位系统与算法 到目前为止,WSN自身定位系统和算法的研究大致经过了两个阶段. 第 1 阶段主要偏重于紧密耦合型和基于基础设施的定位系统,代表性的研究成果包括 RADAR[2],Active Bat[10],Active Badge[17,18],RadioCamera[19],Active Office[20],Easy Living[26],SpotON[29],HiBall Tracker[32],Parc TAB[45],Smart Floor[46],Smart Rooms[48],3D-iD[49],WhereNet[50]等.文献[4,11]中对这些系统作了比较详细的描述. 对于松散耦合型和无须基础设施的定位技术的关注和研究可以认为是自身定位系统和算法研究的第 2阶 段,目前已经成为 WSN领域一个不小的热点.下面对典型系统和算法加以归纳总结. 3.1 Cricket定位系统[26] 为了弥补紧密耦合定位系统的不足,MIT 开发了最早的松散耦合定位系统 Cricket.它由散布在建筑物内位 置固定的锚节点和需要定位的人或物体携带的未知节点(称为 Listener)组成.锚节点随机地同时发射 RF和超声 波信号,RF 信号中包含该锚节点的位置和 ID.未知节点使用 TDOA 技术测量其与锚节点的距离,当它能够获得 3个以上锚节点距离时即使用三边测量法提供物理定位,精度为 4×4英尺 2,否则就以房间为单位提供符号定位. 3.2 SPA(self-positioning algorithm)相对定位算法[7] 瑞士洛桑联邦工业大学(EPFL)的 Srdjan Capkun 等人针对无基础设施的移动无线网络,提出了一种称为 王福豹 等:无线传感器网络中的自身定位系统和算法 861 SPA的相对定位算法.它选择网络中密度最大处的一组节点作为建立网络全局坐标系统的参考点(称为 location reference group),并在其中选择连通度最大的一个节点作为坐标系统的原点.首先根据节点间的测距结果在各 个节点建立局部坐标系统,通过节点间的信息交换与协调,以参考点为基准通过坐标变换(旋转与平移)建立全 局坐标系统.因为所有节点都需要参与坐标的建立和变换计算,所以 SPA的通信开销与节点数量几乎呈指数比. 针对 SPA的缺点,美国仁斯利尔理工学院(Rensselaer Polytechnic Institute)的 Rajagopal Iyengar等人[51]提出 了一种基于聚类(clustering-based)的定位算法:网络部署后,每个节点都开始运行一个随机定时器.假如与邻居 节点相比,节点 i的定时器最早到期,则 i成为一个主节点(master),并向邻居节点广播一个消息,所有接收到该消 息的邻居节点终止自己的定时器并成为一个从节点(slave),这些节点形成一个域.然后分别以这些主节点为原 点使用与 SPA类似的方法建立各个域的局部坐标系统.然后以主节点 ID较小的局部坐标系统为参考,相邻域进 行坐标转换,逐步建立全局坐标系统.因为通信量是随着域的数量而增长的,所以该算法的通信开销与网络中节 点数量呈线性比,更适合于大规模网络的部署. 很显然,相对定位算法最大的问题是当参考点移动或失效时,整个网络就必须重新定位. 3.3 凸规划定位算法[8,36] 加州大学伯克利分校的 Doherty等人将节点间点到点的通信连接视为节点位置的几何约束,把整个网络模 型化为一个凸集,从而将节点定位问题转化为凸约束优化问题,然后使用半定规划和线性规划方法得到一个全 局优化的解决方案,确定节点位置.同时也给出了一种计算未知节点有可能存在的矩形区域的方法.如图 1所示, 根据未知节点与锚节点之间的通信连接和节点无线射程,计算出未知节点可能存在的区域(图中阴影部分),并 得到相应矩形区域,然后以矩形的质心作为未知节点的位置. (The shaped region and the tight rectangular bound represents the feasible set for the unknown node) Fig.1 Example of convex position estimation 图 1 凸规划算法示意 凸规划是一种集中式定位算法,在锚节点比例为 10%的条件下,定位精度大约为 100%.为了高效工作,锚节 点必须部署在网络边缘,否则节点的位置估算会向网络中心偏移. 作为对凸规划算法的改进,文献[52]中提出了将节点间没有通信连接但同样视为节点位置约束的思想来提 高定位精度. 3.4 APS(ad hoc positioning system)[22,23,41] 美国路特葛斯大学(Rutgers University)的 Dragos Niculescu等人利用距离矢量路由(distance vector routing) 和 GPS 定位的原理提出了一系列分布式定位算法,合称为 APS.它包括 6 种定位算法:DV-Hop,DV-distance, Euclidean,DV-coordinate,DV-Bearing和 DV-Radial. 3.4.1 DV-Hop定位算法[22,23] DV-Hop算法由 3个阶段组成.首先使用典型的距离矢量交换协议,使网络中所有节点获得距锚节点的跳数 (distance in hops).第 2阶段,在获得其他锚节点位置和相隔跳距之后,锚节点计算网络平均每跳距离,然后将其作 为一个校正值(correction)广播至网络中.校正值采用可控洪泛法在网络中传播,这意味着一个节点仅接受获得 Anchor node Unknown node 862 Journal of Software 软件学报 2005,16(5) 的第 1 个校正值,而丢弃所有后来者,这个策略确保了绝大多数节点可从最近的锚节点接收校正值.在大型网络 中,可通过为数据包设置一个 TTL域来减少通信量.当接收到校正值之后,节点根据跳数计算与锚节点之间的距 离.当未知节点获得与 3个或更多锚节点的距离时,则在第 3阶段执行三边测量定位. 如图 2 所示,已知锚节点 L1 与 L2,L3 之间的距离和跳数.L2 计算得到校正值(即平均每跳距离)(40+75)/ (2+5)=16.42.在上例中,假设 A从 L2获得校正值,则它与 3个锚节点之间的距离分别为 L1−3×16.42,L2−2×16.42, L3−3×16.42,然后使用三边测量法确定节点 A的位置. DV-Hop 算法在网络平均连通度为 10,锚节点比例为 10%的各向同性网络中定位精度约为 33%[22,23].其缺 点是仅在各向同性的密集网络中,校正值才能合理地估算平均每跳距离. 3.4.2 DV-distance定位算法[22,23] DV-distance算法与 DV-Hop类似,所不同的是相邻节点使用 RSSI测量节点间点到点距离,然后利用类似于 距离矢量路由的方法传播与锚节点的累计距离.当未知节点获得与 3 个或更多锚节点的距离后使用三边测量 定位.DV-distance 算法也仅适用于各向同性的密集网络.实验显示[22,23],该算法的定位精度为 20%(网络平均连 通度为 9,锚节点比例为 10%,测距误差小于 10%);但随着测距误差的增大,定位误差也急剧增大. 3.4.3 Euclidean定位算法[22,23] Euclidean 定位算法给出了计算与锚节点相隔两跳的未知节点位置的方法.假设节点拥有 RSSI 测距能力, 如图 3所示,已知未知节点 B,C在锚节点 L的无线射程内,BC距离已知或通过 RSSI测量获得;节点 A与 B,C相 邻.对于四边形 ABCL,所有边长和一条对角线 BC已知,根据三角形的性质可以计算出 AL的长度(节点 A与 L的 距离).使用这种方法,当未知节点获得与 3个或更多锚节点之间的距离后定位自身. Fig.2 Example of DV-Hop Fig.3 Example of Euclidean 图 2 DV-hop定位算法示意 图 3 Euclidean算法示意 3.4.4 DV-coordinate定位算法[23] 在DV-coordinate算法中,每个节点首先利用Euclidean算法计算两跳以内的邻近节点的距离,建立局部坐标 系统(以自身位置作为原点).随后,相邻节点交换信息,假如一个节点从邻居那里接收到锚节点的信息并将其转 化为自身坐标系统中的坐标后,可使用以下两种方法定位自身:(1) 在自身坐标系统中计算出距离,并使用这些 距离进行三边测量定位;(2) 将自身坐标系统转换为全局坐标系统.这两种方法具有相同的性能[23]. Euclidean和 DV-coordinate 定位算法虽然不受网络各向异性的影响,但受测距精度、节点密度和锚节点密 度的影响.实验显示[22,23],Euclidean 和 DV-coordinate 算法定位误差分别约为 20%和 80%(网络平均连通度为 9, 锚节点比例为 20%,测距误差小于 10%). 3.4.5 DV-Bearing和 DV-Radial定位算法[41] E911系统和智能机器人导航领域都有使用AOA技术确定目标方向和位置的方案,但它们大都使用了高能 耗的天线阵列测量信号方向,并不适用于低能耗的 WSN 领域.针对这个问题,MIT 提出了一种融合 TDOA 和信 号到达相位差的硬件解决方案——Cricket Compass[40],其原型系统可在±40°角内以±5°的误差确定接收信号 方向. DV-Bearing和 DV-Radial算法提出了以逐跳方式(hop by hop)跨越两跳甚至 3跳来计算与锚节点的相对角 度 ,最后使用三角测量定位的方法 .两者的区别在于 ,DV-Radial 算法中每个锚节点或节点都安装有指南针 C L A B L3 A L1 L2 王福豹 等:无线传感器网络中的自身定位系统和算法 863 (compass),从而可以获得绝对角度信息(例如与正北方向的夹角),并达到减少通信量和提高定位精度的目的.实 验显示[41],DV-Bearing 和 DV-Radial 算法在网络平均连通度为 10.5,锚节点比例为 20%,AOA 测量误差小于 5° 的条件下,90%以上的节点可以实现定位,定位精度分别为 40%和 25%. 3.5 Cooperative ranging[3,6]和Two-Phase positioning[44]定位算法 为了减小测距误差对定位的影响,加州大学伯克利分校的 Chris Savarese等人提出了两种循环求精定位算 法——Cooperative ranging和 Two-Phase positioning. 它们都分为启始和循环求精两个阶段.启始阶段着重于获得节点位置的粗略估算.而在循环求精阶段,每一 次循环开始时每个节点向其邻居节点广播它的位置估算,并根据从邻居节点接收的位置信息和节点间测距结 果,重新执行三边测量,计算自身位置,直至位置更新的变化可接受时循环停止. Cooperative ranging 算法的启始阶段又称为 TERRAIN(triangulation via extended range and redundant association of intermediate nodes).首先在所有锚节点上,根据节点间测距结果使用 ABC算法(assumption based coordinates algorithm)建立局部坐标系统,然后将结果(以这个锚节点为原点的局部网络拓扑)传播到整个网络. 未知节点根据它所获得的网络拓扑确定其与锚节点的距离,当获得 4 个与锚节点的距离后,使用三边测量定位 自身.然后进入循环求精阶段. 与 Cooperative ranging 算法不同,为了克服锚节点稀疏问题,Two-Phase positioning 算法在启始阶段使用 Hop-TERRAIN算法(与DV-hop[22,23]类似)获得节点位置的粗略估算.在循环求精阶段,使用加权最小二乘法进行 三边测量以计算新位置.它有两个特点:(1) 给节点的位置估算增加了一个权值属性(锚节点为 1,未定位节点为 0.1;未知节点每执行一次定位计算后,将自身权值设为参与定位计算的节点的均值),利用加权最小二乘法进行 定位计算,使误差越大的节点对定位计算影响越小.(2) 对因连通度低导致定位误差大的节点,通过不让其参与 求精过程来消除它们的影响. 实验显示[3,6,44],Cooperative ranging算法定位精度可达到 5%(测距误差为 5%,而单纯使用 TERRAIN算法得 到的定位精度约为 39%).而 Two-Phase positioning算法在锚节点比例为 5%,测距误差为 5%,网络连通度约为 7 的条件下,定位精度约为 33%. 文献[43]中也提出了对多次测距结果进行平均来减少测距误差的思想,但仅适用于节点静止或低速移动的 环境. 3.6 AHLos(ad-hoc localization system)[33]和n-hop multilateration primitive[37]定位算法 加州大学洛杉矶分校的 Andreas Savvides等人设计了一种称为“Medusa”的无线传感器节点试验平台(配备 有射程 3m的超声波收发器,可使用 TDOA技术以 2cm的精度测量距离),并在该平台上开发了 AHLos和 n-hop multilateration primitive定位算法. 3.6.1 AHLos定位算法[33] AHLos算法中定义了 3种定位方式——原子式、协作式和重复式最大似然估计定位(atom,collaborative和 iterative multilateration).其中 atom multilateration就是传统的最大似然估计定位,如图 4(a)所示. Collaborative multilateration是指假如一个节点可以获得足够多的信息来形成一个由多个方程式组成并拥 有唯一解的超限制条件(over-determined)或限制条件完整(well-determined)的系统,那么就可以同时定位跨越多 跳的一组节点.图 4(b)就展示了 collaborative multilateration的一个二维拓扑示例,未知节点 2和 4都有 3个邻居 节点,且 1,3,5 和 6都是锚节点,根据拓扑中的 5条边建立拥有 4个未知数(节点 2和节点 4的二维坐标)的 5个 二次方程式,利用节点间协作计算出节点 2和节点 4的位置. Iterative multilateration 就是首先使用原子式和协作式定位,当部分未知节点成功定位自身后,将其升级为 锚节点,并进入下一次循环,直到所有节点定位或没有满足原子和协作式定位条件的节点存在时结束. 864 Journal of Software 软件学报 2005,16(5) Fig.4 Multilateration examples 图 4 最大似然估计定位示意 实验显示[33],在网络平均连通度约为 10,锚节点比例为 10%的条件下,该算法可使 90%的节点实现定位,定 位精度约为 20cm.AHLos 算法的缺点为:(1) 将已定位的未知节点直接升级为锚节点虽然缓解了锚节点稀疏问 题,但会造成误差累计－相对于测距精度,该算法的定位精度降低了一个数量级.(2) 在 AHLos 算法中并没有给 出一组节点能否执行 collaborative multilateration 的充分条件.如图 4(c)所示,如果执行协作式定位,节点 x 的解 并不唯一. 3.6.2 N-hop multilateration primitive定位算法[37] 在AHLos算法的基础上,Andreas Savvides等人又提出了 n-hop multilateration primitive定位算法.它不仅给 出了判定节点是否可参与 collaborative multilateration 的充分条件,并使用卡尔曼滤波技术循环定位求精,减小 了误差积累.该算法分为 3个阶段. (1) 生成协作子树:根据判定条件,在网络中生成多个由未知节点和锚节点组成的限制条件完整或超限制 条件的构形,称为协作子树.每个构形包括 n个未知变量(未知节点的坐标)和至少 n个非线性方程式,并确保每个 未知变量拥有唯一解.未被协作子树包含的节点在整个算法的后处理阶段进行定位. (2) 计算节点位置的初始估算:根据锚节点位置、节点间距离和网络连通性信息对每个节点的位置进行粗 略估算,结果作为第 3 阶段的输入.如图 5 所示,图中 A,B 为锚节点,C,D 为未知节点,测得节点间距 a,b,c,可推算 出节点 C 的 x 坐标取值范围为 ( )( )cbxax BA ++− , .但该方法有一个明显的缺点就是要求锚节点必须被部署在 网络边缘. (3) 位置求精:根据预设的定位精度,使用卡尔曼滤波技术在每个协作子树范围内(每个节点位置有唯一解) 对第 2阶段的结果进行循环求精,可选用分布式或集中式两种计算模式. 实验显示[37],该算法的定位精度可达 3cm(节点测距误差为 1cm,锚节点比例为 20%). Fig.5 Initial estimates of n-hop multilateration primitive 图 5 n-hop multilateration primitive中节点位置的初始估算 1 2 5 4 3 5 x x′ (c) (a) (b) Unknown node Anchor node a a a C c Db B b+cb+c x coordinate bounds for node C A 王福豹 等:无线传感器网络中的自身定位系统和算法 865 3.7 Generic Localized Algorithms[42] 前面分析了 Cooperative ranging算法使用循环求精来降低测距误差影响,AHLos算法利用将已定位的未知 节点升级为锚节点来解决锚节点稀疏问题.在此基础上,加州大学洛杉矶分校的 Seapahn Meguerdichian1等人提 出了通用型定位算法(generic localized algorithm),它的特点在于,详细指定了未知节点接受位置估算并升级为 锚节点的条件,以减少误差累计的影响. 该算法也由启始和循环两阶段组成.启始阶段中,将相邻节点少于 3 个的节点标记为 orphan,将锚节点标记 为 gotFinal.在循环阶段,首先相邻节点交换信息,假如一个未知节点的邻居节点中非 orphan 节点的数量小于 3, 就将其标记为 orphan节点.假如一个节点有 3个以上的邻居节点为 gotFinal,则该节点就从中随机选择 3个执行 多次三边测量定位.执行的次数依赖于 gotFinal 邻居节点的数量,并确定自身位置为多次定位结果的均值.然后, 该节点根据多次定位结果的一致性和 gotFinal 邻居节点的数量计算一个目标函数值.最后,相邻节点比较目标 函数值,那些目标函数值最低的节点将接受位置估算并升级为锚节点,而其他节点都丢弃它们的位置估算,进入 下一轮循环.因为每次循环都至少会有一个节点成为 orphan节点或升级为锚节点,所以循环最终会结束. 实验显示[42],Generic Localized Algorithm在锚节点定位误差为 10%,锚节点比例为 20%,测距误差在 25%条 件下,定位精度为 40%. 3.8 MDS-MAP定位算法[30] MDS-MAP是一种集中式定位算法,可在 range-free和 range-based两种情况下运行,并可根据情况实现相对 定位和绝对定位.它采用了一种源自心理测量学和精神物理学的数据分析技术——多维定标(multidimensional scaling),该技术常用于探索性数据分析或信息可视化. MDS-MAP算法由 3个步骤组成: (1) 首先从全局角度生成网络拓扑连通图,并为图中每条边赋予距离值.当节点具有测距能力时,该值就是 测距结果.当仅拥有连通性信息时,所有边赋值为 1.然后使用最短路径算法,如 Dijkstra 或 Floyd 算法,生成节点 间距矩阵. (2) 对节点间距矩阵应用 MDS技术,生成整个网络的 2维或 3维相对坐标系统. (3) 当拥有足够的锚节点时(2维最少 3个,3维最少 4个),将相对坐标系统转化为绝对坐标系统. 实验显示[30],当网络的节点密度减小时,定位误差增大,并且无法定位的节点数量增加;而当网络连通度达 到 12.2 时,几乎全部节点都可实现定位;在拥有 200 个节点(其中 4 个锚节点),平均连通度为 12.1 的网络中,在 range-free条件下,定位误差约为 30%;而在 range-based条件下,定位误差为 16%(测距误差为 5%). 3.9 小 结 根据以上论述可知,每种系统和算法都有各自的特点和适用范围,没有哪一种是绝对最优的. 从整体上看 ,近年来提出的一些循环求精算法 ,如 Cooperative ranging,Two-phase positioning,n-hop multilateration primitive,更加充分发挥了 WSN 的特点,即利用节点间的协同工作实现单个节点无法完成的任 务.它们在初始阶段着重于获得节点位置的粗略估算,并在求精阶段根据用户预设的精度门限循环求精;甚至还 可根据应用需求,将整个求精阶段作为一个可选阶段.这些算法不仅提高了定位精度,还给予用户更大的自由 度,正逐渐形成一个新的类别. 但我们还应看到,现有的定位系统和算法还存在如下一些问题: (1) 未知节点必须与锚节点直接相邻,锚节 点密度过高,例如 Cricket,Cooperative ranging.(2) 定位精度依赖于网络部署条件.例如,DV-Hop,DV-distance 仅 适用于密集部署的各向同性网络;n-hop multilateration primitive和凸规划算法要求锚节点必须部署在网络的边 缘.(3) 没有对距离/角度测量误差采取抑制措施,造成误差传播和误差积累,定位精度依赖于距离/角度测量的 精度.例如 AHLos,DV-distance,DV-Bearing,DV-Radial,SPA 及其改进算法.(4) 依靠循环求精过程抑制测距误差 和提高定位精度.虽然循环求精过程可以明显地减小测距误差的影响,但不仅产生了大量的通信和计算开销,而 且因无法预估循环的次数而增加了算法的不确定性 .例如 ,Cooperative ranging,Two-phase positioning,n-hop 866 Journal of Software 软件学报 2005,16(5) multilateration primitive.(5) 算法收敛速度较慢.例如,Generic Localized Algorithm算法在每次循环中,相邻节点 中仅有一个可实现定位并升级为锚节点. 仿真显示[53],许多算法和系统的定位精度都还有很大的提高空间.总之,无线传感器网络定位问题的研究仍 然是 WSN的一个技术难点,也是关键点之一. 4 展 望 近 10 年来,WSN 自身定位问题研究的进展十分可喜,取得了丰富的研究成果.特别是进入 21 世纪后,对 ad-hoc WSN的自身定位问题有了许多新颖的解决方案和思想.但是,这个领域的研究从总体上说尚处于一个起 步的阶段,已有的研究工作正在为该领域提出越来越多需要解决的问题.我们认为除了对定位算法本身的研究 外,可能的热点研究方向包括:(1) 定位算法性能评价的模型化和量化;(2) 建立标准的仿真技术和仿真系统来 模拟定位算法的实现;(3) 由成千上万节点组成的大规模或超大规模网络自身定位问题的低成本(时空、功耗、 价格)和高精度的实现;(4) 在移动网络环境下具有自调整性的定位算法的实现. References: [1] Ren FY, Huang HN, Lin C. Wireless sensor networks. Journal of Software, 2003,14(2):1148−1157 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/1148.htm [2] Bahl P, Padmanabhan VN. RADAR: An in-building RF-based user location and tracking system. In: Proc. of the IEEE INFOCOM 2000. Vol.2, Tel Aviv: IEEE Computer and Communications Societies, 2000. 775−784. http://research.microsoft.com/~padmanab/ papers/infocom2000.pdf [3] Beutel J. Geolocation in a PicoRadio environment [MS. Thesis]. Berkeley: UC Berkeley, 1999. [4] Bulusu N, Heidemann J, Estrin D. GPS-Less low cost outdoor localization for very small devices. IEEE Personal Communications, 2000,7(5):28−34. [5] Rabacy JJ, Ammer MJ, da Silva Jr. JL, Patel D, Roundy S. Picorodio supports ad hoc ultra-low power wireless networking. Computer, 2000,33(7):42−48. [6] Savarese C, Rabaey JM, Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Int’l Conf. on Acoustics, Speech, and Signal. Vol.4, Salt Lake: IEEE Signal Processing Society, 2001. 2037−2040. http://bwrc.eecs.berkeley. edu/Publications/2001/Locatng_distrb_ad-hoc_wrlss_snsr_ntwks/icassp2001_final.pdf [7] Capkun S, Hamdi M, Hubaux J-P. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002,5(2):157−167. [8] Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. In: Proc. of the IEEE INFOCOM 2001.