投术 New Technology 数据通信2010.4 无线传感器网络定位测量模型方法研究 何宛星’支永浩’傅鹏 李善仓。(1.中国移动通信集团云南有限公司 2.广东省电信规划设计院有限公司 3.西安交通大学电信学院) 摘要:首先论述了面向无线传感器网络定位技术的基本原理,对常见的定位方法做了综述;分类研究了 无线传感器网络中常见的定位模型和测量方法,对定位技术中应用到的基本测量技术和测量模型以及可能存 在的误差进行了分析;最后对衡量当前存在的定位系统和定位方法的标准做了讨论,并总结了定位系统优劣 的基本评价标准。 关键词:无线传感器网络;节点定位测量模型;误差估算方法 1无线传感器网络定位原理和方法 Davison提出的一种数据分析方法圈。其基本原理 在传感器网络的节点定位过程中,可以根据节 为从距离空间矩阵中挖掘出传感器节点间相对位置 是多 点间的距离测量来进行定位,即未知节点根据与邻 信息,即从高维距离矩阵中提取低维坐标信息,tidimensional Scaling)的核心r3_。 近参考节点之问的相对距离或相对角度来计算自身 维定标MDS(Mul传感器网络中节点定位方法很多,根据定位原 位置,也可以基于非测距方法来计算自身位置。基于 距离测量的定位方法有三边测量法、三角测量法、 理的不同可以分为以下7类:TOA、RSS、TDOA等;基于非测量的有质心法等。大部 基于测距(Range—Based)技术的定位和非测距 (Range—Free)技术的定位:基于测距定位通过测量 三角测量(Trilateration)主要采用参考节点与未 节点间距离或角度信息 运用三边测量、三角测量、知节点问方位角来确定未知节点的计算方法。根据 多边测量法或托格森方法计算节点位置,采用的测 TOA、TDOA、AOA。RSS功耗低、易 每个参考节点到未知节点的方位角,通过余弦定理 距技术主要有RSS、分节点定位方法均以下面几种定位原理实现。 求得未知节点的位置。 获得,但测距误差可能较大;TOA需要节点间精确的 三边测量法(Trilateration)是一种基于几何计算 时间同步,无法用于松散耦合型定位;而TDOA技术 AOA也易受外界环境影响 的定位方法,即已知A、B、C三个节点的坐标以及三 受限于超声波传播距离;且需要额外硬件,成本和功耗较高。基于测距的定位 点到未知节点D的距离,求节点D的坐标。 多边测量法(Muhrilateration)是三边测量法的一 机制可使用多次测量、循环定位求精等方式来减小 种延伸,也称为极大似然估计法【lJ。当未知节点与多 测距误差对定位的影响。非测距定位则无需距离和角度信息,仅根据网 个参考节点的距离可得时,可根据未知节点与参考 节点之间的距离关系建立方程组,使用标准的最小 络连通性等信息通过估计方法可以实现定位,这种 均方差估计方法得到节点D的坐标。 方法的计算量通常较大,而且距离和角度信息的测 phous 托格森方法(Torgensons Method)是由Mark L. 量精度对定位性能的影响很大。典型的有Amor14 i收稿日期:2010-07—05 c 新技术 2010.4数据通信 New Technology 算法、DV—Hop算法、凸规划、三角形内的点近似定位 式。典型的紧密耦合定位系统有AT&T的Active Bat、 (APIT)和MDS—MAP[ ̄等,其中MDS—MAP也可在基于 Active Badge、HiBall Tracked 等。这种定位方式的特 测距条件下实现。 点是适用于室内环境,具有较高的精确性和实时陛, 集中式计算与分布式计算:传感器网络的中心 时间同步和参考节点问的协调问题容易解决,但限 节点通常由运算、存储能力较强的节点担任,集中式 制了系统的可扩展性,成本较高,应用范围有限。 计算是指把定位所需的信息传送到中心节点,由中 物理定位与符号定位:定位系统通常可提供节 心节点统一对传感器网络的定位问题进行计算,中 点的物理位置和符号位置两种定位结果。考虑到大 心节点可以运行较为复杂的定位算法,其优点在于 部分定位系统均有一定的参考节点,可以方便通过 从全局角度统筹规划,可以获得相对精确的位置估 GPS等物理定位方式定位,因此物理定位是比较普遍 算。它的缺点是中心节点周围的节点会因为通信开 的定位方式;符号定位的典型系统和算法有Active 销大而过早消耗完电能,导致整个网络与中心节点 Badge[圳、微软的Easy Living等,MIT的Cricket定位系 信息交流的中断、无法实时定位等。集中式定位算法 统_l1】贝0可根据配置实现两种不同形式的定位。 有凸规划(Convex Optimization)、MDS—MAP等。 混合定位方法:由于目前传感器网络应用越来 分布式计算是指依赖节点间的信息交换和协 越广泛,其定位技术也不断提高,在实际应用中单纯 商,由节点自行计算的定位方式。这种机制中,每个 的某种方法也许不能满足网络的定位,因此出现了 节点需要计算自身或者邻居节点的位置,因此考虑 一些将多种定位方式结合起来进行定位的混合定位 到节点的运算能力、存储能力以及能量等因素,其运 方法。较常见的有将测距定位与非测距定位相结合、 行的算法需要简单高效,常见的分布式定位算法有 集中式与分布式定位方法相结合、绝对定位方式与 dwMDS算法等。将集中式与分布式结合起来,在网络 局部定位方式结合等。 中按照一定策略选择一些节点作为局部中心节点来计 算局部区域节点的位置,是一种非常有前景的方法。 绝对定位与相对定位:从参照系来讲,定位可分 2传感器网络定位中的测量模型 无线传感器网络中的定位问题可以描述为:由 为绝对定位和相对定位两种。绝对定位指定位算法 局部的、有限的位置信息计算出所有节点的位置信 可以提供未知节点的绝对位置,而相对定位通常以 息。在定位中首先要获得部分位置信息,包括距离、 网络中部分节点为参照系,建立相对坐标系。相对定 角度、连通性等,再通过节点定位算法的协同计算, 位和绝对定位可以互相转换,大多数定位系统和算 求解出待求节点的定位信息。传感器网络中定位信 法可以实现绝对定位服务。典型的相对定位算法和 息的测量对于节点定位性能、定位精度有至关重要 系统有SPAL ̄、LPS[ ̄、SpotONIs],而MDS—MAP定位算法l 5l 的影响,本文就定位信息的测量及可能产生的误差 可以根据网络配置的不同分别实现相对定位和绝对 进行分析。 定位。 静态定位和移动定位:虽然一般无线传感器网 2.1 接收信号强度 接收信号强度(RSS)主要由接收节点的信号强 络中节点部署完成后大部分呈静态,大部分定位方 度指示,可以以音频、射频或其他无线信号的接收功 法均认为参考节点或未知节点一旦部署后,其位置 率表示。在无线传感器网络中,节点与其邻居节点之 均固定不动,但在一些应用如移动目标检测等领域 问的无线通信以传输数据时射频信号的RSS功率作 要求支持移动节点的定位技术。该类技术主要有两 为测量的基础。RSs测量成本低廉并易于硬件实现, 类:一是未知节点具有一定运动时的定位;二是基于 是目前最常用的测距手段_ l2I。 移动参考节点的定位技术,这是一种全新思路的定 位技术,通过移动参考节点来弥补参考节点不足 。 无线信号在传播过程中,信号强度的衰减与距 离成比例,传播衰减因子通常在2~4之间Il3]。节点到 紧密耦合与松散耦合:紧密耦合定位指参考节 信号源的距离越近,由RSS偏差产生的绝对距离误差 点有一定的位置已知的基础设施支持,而松散型定 越小,当距离增加时,由RSS波动造成的绝对距离误 位系统的节点采用无控制中心的分布式无线协调方 差将会很大【15]。因此在定位算法中,参考节点对未知 数据通信2010.4 节点位置有不同的影响权值,RSS值越大的参考节点 够提供精确的定位精度 。在文献[151中提到当前基 影响权值越大。在Rss测距方法中,估计距离与实际 于UWB的定位算法的RMs测距误差达No.12~1.5m。 距离呈平方比例。RSS适用于节点分布稠密的无线传 2_5 AOA 感器网络中。 AOA是一种通过提供邻居节点的方位信息进行 2.2 TOA/_『‘DOA 定位的方法,可以作为TOA和RSS ̄JJ量定位的一种补 TOA是测量信号(射频、音频或其他类似信号) 充方法。通过估算邻居节点发送信号方向的技术,可 从发射节点到达接收节点的时间间隔。测量得到的 依靠天线阵列或多个接收器结合来实现,除定位外, TOA是传输时问与传播延迟时间的和㈣。从发射节点 还提供节点的方向信息。AOA技术会因受外界环境 i到接收节点i之间的延时Ti、Tj,等于二者问距与信号 噪声而影响测量结果,且传感器节点成本较高。 传播速度vp之比。这种基于时间的测量技术能够准 2.6混合型测量方法 确的估计视距LOS(Line—of-Sight)信号的到达时间。 最近有学者提出几种混合型方法。学者提 TOA的误差主要有两种:附加噪声和多径误差 出了使用到达信号的衰减差进行定位估计的方法 累计I 。在节点部署稠密的无线传感器网络中,当节 (SADOA)㈣,该方法结合到达时间差TDOA进行节点 点间距减小时,视距信号强度会增加,室内具有大量 的位置估计。其原理为SADOA使用参考节点与未知 链路时进行测量的结果表明 ,相对视距信号功率在 节点之问的信号衰减值,求出距离之问的比值从而 低路径长度时较高,当增加路径长度时视距信号的 产生一个圆,则未知节点的位置可能处于该圆上; 功率会降低。因此,视距问题在具有较大连通度的网 TDOA ̄I]定义出一条可能是未知节点位置的双曲线。 络中尤为严重。 然后使用泰勒级数将TDOA与SADOA产生的双曲线 2.3 Connectivity 线性化,然后利用最小二乘算法将估计所得的位置 基于Connectivity(连通性)进行节点定位的方法 节点位置迭代运算,这种算法无需精确路径衰减模 是一种比较新颖且具有实际意义的方法_】 。在RSS ̄,0 型,也无需在传感器网络中添加额外硬件,在非视距 量中两个节点可以通过接收功率来判断其是否进行 环境下所得定位精度较TDOA提高50%。 了通信。如果两个节点的距离过大,之间的通信链路 就很难建立。而节点连通性进行定位的思路:如果接 3定位系统性能评价标准及评价指标 收节点可以成功解调由发送节点发送的数据包,则 为了衡量传感器网络节点定位系统的优劣 ,从 认为两个节点是连通的,反之,如果接收节点RSS值 应用角度出发总结了5个基本标准: 太低,则认为这两个节点问的链路是不通的。 定位精度:定位精度一般用误差值与节点无线 2.4 UWB/_rOA 通信范围的比例表示。在无线传感器网络的各种应 UWB是一种高速、低成本、低功耗的无线通信技 用中,具体评价各种定位算法最常见的指标有均方 术。UWB信号带宽大于500MHz或基带带宽和载波频 差误差(MSE)、均方根误差(RMSE)、克拉美一罗下界 率的比值大于0.2的脉冲信号,具有很宽的频带范围, (CRB)、不规则性程度(DOI)、几何精度因子 FCC规定UWB的频带从3.1GHz~10.6GHz,并信 (GDOP)、圆误差概率(CEP)等。其中GDOP可以用于 号的发射功率在一41dBm以下。UWB聚焦在两个领域 衡量基站地理位置对定位准确度的影响。在实际应 的应用上,一是符合IEEE802.15.3a标准的短距离高 用中还常将定位误差的概率密度函数(PDF)、累积概 速数据通信,即无线无延迟地传播大量多媒体数据, 率分布函数(CDF)、相对定位误差(RPE)等也作为定 速率要达到100Mbit/s~500Mbit/s;另一个是符合 位算法的评价指标。 IEEE 802.15.4a的低速低功率传输,用于室内精确定 定位系统成本:主要包括计算成本、通信成本及 位,例如战场士兵的位置探测、工业自动化、传感器网 节点实现成本。计算成本主要包括定位系统所消耗 络、家庭/办公自动化、机器人运动跟踪等。UWB在定 的计算资源、能耗以及时间成本;通信成本指定位系 位上具有低成本、抗多径干扰、穿透能力强的优势, 统进行定位时网络中的节点间通信负载;实现成本 可以应用于静止或移动物体以及人的定位跟踪,能 则指实现定位系统或算法的基础设施、节点设备的 0I4 总体费用。 堡 一 New ech Proceeding of the 1 st IEEE Int’l Workshop on Sensor Network Protocols and Application.IEEE Communications Societies: 参考节点比例:参考节点能够自主获取自身位 置,通常依赖人工部署或辅助定位模块来实现。参考 Anchorage.2003:42—50 节点在整个网络中的比例是衡量节点算法的重要指 标,若一个算法要求参考节点所占比例高,则表明该 [8】李建中,李金宝.传感器网络及其数据管理的概念、问题与 进展[J]欺件学报,2003,14(10):1717—1727 【9]张正勇 智,等.基于移动锚节点的无线传感器网络节 算法对参考节点的依赖性较大,由于参考节点的成 本要高于未知节点,因此一个好的算法应该能在参 点定位【J1_清华大学学报(自然科学版),2007,47(4): 534—537 考节点比例较低的条件下也能进行一定精度的定 【10】Andy H,Andy H,Pete S,et .The anatomy of a context-aware 位。许多定位算法的精度受节点密度的影响,如 application【C].ACM/IEEE Internation Conference on Mobile DV—Hop【18算法仅在节点密集部署的情况下估算节点 位置。 Computing and Networking,ACM:Seattle,1999:59—68 【1 1]NB P,A C,H B.The cricket l0cati0n—supp0rt system【C].Pro— cedding of the 6th Annual Int‘l Conference on Mobile Comput- ing and Networking.ACM Press:Boston,2000:32—43 定位系统的可靠性及健壮性:定位系统还需要 具有一定的可靠性和健壮性。一般定位系统在真实 延、衰减、非视距、通信盲点等问题 ,尤其是当部署 在恶劣环境下的传感器网络会受到各种破坏而出现 部分节点无法工作。因此定位系统设计时必须具有 12]Destino G,Macagnano D,Abreu G,et a1.Localization and Track— 应用环境下常常会遇到开发初期的问题,如多径时 [ing for LDR—UWB Systems[C].16th IST of Mobile and Wireless Communications,2007:1-5 [1 3]Hashemi H.The indoor radio propagation channel[J】.Proceed- 可靠性和健壮性,当由于环境原因造成距离测量等 信息出现较大误差时,定位系统和算法依然能够提 供一定精度的定位服务。 定位系统功耗:功耗是传感器网络始终要考虑 ings ofthe IEEE,1993,81(7):943-968 【14】Costa JA,Patwari N,Hero AO,III.Achieving high-accuracy dis— tributed localization in sensor networks[C].IEEE International Conference on Acoustics,Speech,and Signal Processing(I— 的重要因素之一。由于节点一般由容量有限的电池 CASSP’05),2005:641—644 [1 5]Patwari N.ocaLtion estimation in sensor networks[D]:University of Michigan,2005 供电,其各个模块要尽量降低能耗以延长节点的生 命周期。设计定位系统和算法时,在保证定位精度的 [16】Robinson E,Quazi A.Effect of sound-speed profile on differen- 前提下,与功耗密切相关的定位所需的计算量、通信 tial tiem-delay estimation[J].Journal of the Acoustical Society 开销、存储开销、时间复杂性是关键性指标 。 of America,1985,77(3):1086 [17]Pahlavan K,Krishnamurthy P,Beneat J.wideband radio propa— 参考文献 gation modeling for indoor geolocation applications fJ].IEEE Communications Magazine,1 998:60-65 【1 8]Niculescu D,Nath B.Ad hoc positioning system(APS)[C].Glob- 【1]孙利民,李建中,陈渝等.无线传感器网络【M].清华大学出版 社:JL京,2005 al Telecommunications Confefence fGLOBECOM’O1),IEEE, 2001:2926-2931 [2]周光亚,夏立显.非定量数据分析及其应用【M].科学出版社: 北京,1993 【3】Davison M.Multidimensional Scaling[M].Wiley&Sons:New York, 1983 [19】Gezici S,Zhi T,Giannakis GB,et a1.Localization via ultra—wide band radios:a look at positioning aspects for future sensor net- works[J].Signal Processing Magazine,IEEE,2005,22(4):70—84 l4J王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和 算法『J]揿件学报,2005,1 6(5):857—868 棒性节点定位算法IJJ_自动化学报,2008,34(3):288—297 bile ad—hoc networks[J].Cluster Computing,2002,5(2):157-167 作者简介:何宛星,中国移动通信集团云南有限公司计划部, 信集团云南有限公司计划部.从事网络规划研究、计算机网络 [5]罗海勇,李,赵方等.一种基于加权多尺度分析技术的鲁 从事网络规划、支撑系统架构设计研究:支永浩,中国移动通 傅鹏,博士,广东省电信规划设计院有限公司,从事自组 【6]Capkun S,Hamdi M,Hubanx J-P.GPS-free positioning in mo— 研究:织网络、支撑系统架构设计研究;李善仓,博士,西安交通大学 从事传感器网络研究工作。一 [7]Niculescu D,Nath B.1ocalized positioning in ad hoe network[C]. 电信学院,【17 I