（通信与信息系统专业论文）无线传感器网络混合式定位算法研究.pdf

武汉理工大学硕士学位论文 摘要 定位是无线传感器网络中重要的研究方向之一。许多协议或服务都需要知 道节点的位置信息。作为一个综合性的研究课题，近年来许多定位算法得以提 出。测距无关定位算法虽然有良好的拓展性，但是在网络密度和锚节点密度较 低时难以达到较高的精度，而现有的高精度定位算法过多地依赖于节点间的测 距信息，使得算法无法应用于大规模和低成本的无线传感器网络。 提出了定位算法的本体论描述问题，并从概念、分类、评估指标、基本数 学工具等发面对无线传感器网络的定位算法进行了较全面的描述与分析，特别 对一些深入的研究问题如c r b ( c r a m 6 r - r a ob o u n d ) 、路径转发、随机游走等进 行了讨论，在此基础上提出了混合式高精度定位算法h i l s ，使由具有测距能力 的部分节点和无测距能力的普通节点构成的异构网络能够充分利用已有的到锚 节点的最短路径信息和测距信息进行迭代精确定位。算法的混合式特性体现在： 可利用测距信息和测距无关信息( 如连通度、最短路径) 和初始坐标估计( 如 d v - h o p 等) 来达到实际应用中异构网络的精度可控的定位问题。结果表明相比 于典型的测距无关的定位算法，提出的算法可以避免一般迭代过程中导致精度 不高的局部最小问题，解决了这一定位精度的瓶颈。虽然时间消耗与预设的精 度有关，但通过在初始阶段通过本体信息描述的节点间进行信息交换后对节点 进行优先计算排序和初始化坐标估计，其迭代时间可以明显缩短。实验证明算 法具有较理想的定位精度，解决了测距无关算法的精度难以控制的问题，并且 其精度与测距相关的算法相当，可扩展应用至分布式定位计算中。 关键字：无线传感器网络；定位；混合式算法；高精度算法 武汉理工大学硕士学位论文 a b s t r a c t c o n t e n t ：l o c a l i z a t i o ni so n eo ft h em o s ti n t r i n s i ci s s u e si nw i r e l e s ss e n s o r n e t w o r k s m a n yp r o t o c o l sa n ds e r v i c e sa l eb a s e do nt h ep r o v i d e dl o c a l i z a t i o n i n f o r m a t i o n a sac o m p r e h e n s i v ei s s u e ，m a n ya l g o r i t h m sh a v eb e e ns u g g e s t e di n r e c e n ty e a r s t h o u g hh o l d i n gt h eg r a c e f u lf l e x i b i l i t y , t h er a n g e f r e el o c a l i z a t i o n a l g o r i t h m sm a yf a i lt or e a c ht h ed e s i r e da c c u r a c yi nt h es i t u a t i o no fl o wd e n s i t yo f n e t w o r ko ra n c h o r s t h eh i g hc o s to fc a l i b r a t i o nd e v i c eh i n d e r st h el a r g e - s c a l ea n d l o w - c o s ta p p l i c a t i o n so f r a n g e b a s e da l g o r i t h m sw i t hb e t t e ra c c u r a c y i nt h i sp a p e r , t h eo n t o l o g i c a ld e s c r i p t i o no fl o c a l i z a t i o n , a n dt h et a x o n o m i c a l a n a l y s e si n c l u d i n gc o n c e p tc l a s s i f i c a t i o n , e v a l u a t i o ns c h e m e s ，a n d b a s i c m a t h e m a t i c a lt o o l sa n ds oo na r em a d e s o m er e c e n ti n - d e p t hs u b j e c t s ，i np a r t i c u l a r t h ec r a m r r - r a ob o u n d ，p o s i t i o nf o r w a r d i n g ，a n dr a n d o mw a l k , a r ea l s od i s c u s s e d b a s e do nt h o s ea n a l y s e s ，t h eh y b r i da l g o r i t h mh i l sw i m h i 曲a c c u r a c yi st h e r e f o r e p r o p o s e d w i t ht h eu t i l i t yo fn o d e sw i t ha n dw i t h o u tc a l i b r a t i o nc a p a b i l i t y n 地 h y b r i d c h a r a c t e r i s t i co f h i l sh o l d si nt w oa s p e c t s ：b e i n ga b l et ot a k ea d v a n t a g eo f b o t ht h er a n g e - b a s e di n f o r m a t i o na n dr a n g e - f r e ei n f o r m a t i o n , e g c o n n e c t i v i t ya n d s h o r t e s tp a t h ，a n dc a l c u l a t i n gt h ei n i t i a lc o a r s ec o o r d i n a t e s ，e g u s i n gd v - h o p ，t o u t i l i z et h ee r r o r - c o n t r o l l a b l el o c a l i z a t i o na l g o r i t h mi n h e t e r o g e n e o u sn e t w o r k s r e s u l t ss h o wt h a tc o m p a r e dw i t l lc l a s s i c a lr a n g e f r e ea l g o r i t h m , t h ep r o p o s e d a l g o r i t h mc a nm i t i g a t et h el o c a lm i n i m ap r o b l e mi nt h eg e n e r a li t e r a t i v ea l g o r i t h m s t h o u g ht h et i m ec o n s u m p t i o nr e f e r r e dt ot h ep a r a m e t e ro fd e s i r e da c c u r a c y , i tc a nb e r e d u c e db ye x c h a n g i n gt h eo n t o l o g yd e s c r i p t i o no fc o n s t r a i n sb e t w e e nn o d e st or a n k t h eo r d e rt ol o c a l i z e ，a n db yu s i n gt h eo p t i o n a li n i t i a le s t i m a t i o nw i t hs o m e l i g h t w e i g h tr a n g e f r e ea l g o r i t h m i ns u m , s i m u l a t i o nr e p r e s e n t st h a th i l s c a l la c h i e v e t h ei d e a la c c u r a c ya n dc a ns o l v et h ep r o b l e mo fu n c o n t r o l l a b l ee r r o ri nr a n g e f r e e a l g o r i t h m ，a sw e l la sb ea p p l i e dt ot h ed i s t r i b u t e ds i t u a t i o n k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；l o c a l i z a t i o n ；h y b r i da l g o r i t h m ； h i g ha c c u r a c ya l g o r i t h m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写的成果，也不包含为获得武汉理工大学或其它教育机构学 位证书而使用过的材料。与我一起工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 签名：日期：型! z ：! n 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 期：型n 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究背景和国内外研究现状 美国技术评论杂志2 0 0 3 年在论述未来新兴十大技术时，无线传感器网 络被列为第一项未来新兴技术。同年，美国商业周刊未来技术专版，认为 无线传感器网络是今后全球四大高技术产业之一。美国今日防务杂志更认 为无线传感器网络的应用和发展，将引起一场划时代的军事技术革命和未来战 争的变革。2 0 0 4 年( i e e es p e c t r u m ) ) 杂志发表一期专辑“传感器的国度”，论 述无线传感器网络的发展和可能的广泛应用。近几年来，在美国国防部高级规 划署( d a r p a ) 、美国自然科学基金委员会( n s f ) 和其它军事部门的资助下，美国 科学家对智能无线传感网络所涉及的各个方面进行了深入地研究。欧洲于2 0 0 4 年于1 月1 9 日至2 1 日在德国首都柏林举行了第一届“无线传感器网络论坛”， 有近百余名微电子、机械电子等方面的专家出席了论坛。在我国科技部发布的 国家中长期科学和技术发展规划纲要( 2 0 0 6 2 0 2 0 ) ) ) 中，也将无线传感器网络 及其多项关键技术列为重点研究方向，纲要中指出：“新一代宽带无线移动通信 网。研制具有海量通信能力的新一代宽带蜂窝移动通信系统、低成本广泛覆盖 的宽带无线通信接入系统、近短距离无线互联系统与传感器网络，掌握关键技 术，显著提高我国在国际主流技术标准所涉及的知识产权占有比例，加大科技 成果的商业应用，形成超过1 0 0 0 亿元的产值”。可见，由于无线传感器网络有 着诸多重要的理论及现实意义，国内外正积极开展相关研究。 然而，无线传感器的研究有着诸多问题需要解决，g a n e s a n 等人指出无线传 感器网络面l 临以下几个重要的挑战【l j ： ( 1 ) 支持有限能量消耗的无线电信号下的多跳通信； ( 2 ) 数据管理。包括基于特征的数据命名、路由和网内融合的框架； ( 3 ) 当节点已知自身位置时的地理路由设计； ( 4 ) 无线传感器网络动态、资源有限系统的监测和维护。 传统的计算机通信的局域网有着固定的拓扑和节点，设计这些网络一般尽 量使数据吞吐率最大。但是，多数传感器网络的目的是为了在未知环境下探测、 识别、定位、数据处理和跟踪静态的或移动的目标。因此，传统的计算机通信 武汉理工大学硕士学位论文 网络设计准则一般不适用于传感器网络【2 1 。定位简单的来说是节点( 相对) 位置 信息的确定，它是无线传感器网络的一个重要课题，许多协议和应用都依赖于 节点定位信息。例如地理辅助路由协议g e a r 、拓扑控制、数据融合，以及货物 管理、入侵检测、流量监测和危急情况下的人员定位中【3 】。在学术界，无线传感 器网络定位问题也成为近些年研究的热点，许多定位算法应运而生。图1 1 中显 示了s c ! 收录的定位论文呈逐年增长的趋势，并且表明其重要地位与路由和m a c 相当。 p u b i l s h e di t e m si ne a c hy e a r p u b l i s h e di t e m si ne a c h y e a r 艮 4 0 t 3 0 朋 1 ：两 l 暑；g=菩笤 y e a r $ ( b ) 路由 p u b l i s h e di t e m si ne a c hy e a r 薹 y e a r s ( c ) m a c 图1 1 截止0 7 年3 月s c i 中收录的关于无线传感器网络的论文统计 1 2 本文主要研究内容和组织结构 1 2 1 本文主要研究内容 由于无线传感器网络的定位算法众多， 同的性能。但是算法中都会用到最短路径、 2 而且针对不同的应用，算法有着不 连通度和测距信息中的一种或多种 瓣潺缀滋懑鋈- 瓣瓣 h蔫黎缀溱懑鬃遴誊一。戆纛程懿w霪h 誊盥鎏；矧 _ 蠢 幻 一暮h 曩_日誓h、；= 。 吕“ p。；。；。， 武汉理工大学硕士学位论文 作为定位算法的基本输入条件。另一方面，仅需要少数锚节点和连通度信息的 测距无关算法定位精度难以保证，而具有较高精度的测距信息要求节点装备有 昂贵的测距设备，不利于大规模应用。而将两种方法结合起来，根据应用中所 需的精度安排一定比例的安装有测距设备节点和不具备测距能力的一般节点的 异构网络在应用中是非常必要的。所以本文不针对应用进行一一分析，而是在 具有一般节点和有测距能力节点的异构网络下，研究能够保证定位的精度、又 能进行分布式和集中式应用的混合式定位算法。主要研究内容如下： ( 1 ) 无线传感器网络定位技术概述，包括对于算法的地位、研究进展、应用 和难点； ( 2 ) 无线传感器网络定位算法的分析，包括算法的本体论研究、评估指标、 数学工具、和随机游走、c r a m e r - r a o 下限和基于跳数估计的测距无关算法等关 键问题进行讨论和分析； r 3 1 提出了适用于由测距能力和无测距能力节点构成的异构网络的混合式 的高精度定位算法并对之进行实验对比分析。 1 2 2 论文组织结构 本文共分为6 章：第1 章对无线传感器网络中的定位问题进行了概述。第2 章就无线传感器网络的地位及应用作了讨论和研究。第3 章分析了无线传感器 网络定位问题的研究范畴和相关知识，分析讨论了定位中的一系列问题和数学 方法，并讨论了几种基于跳数估计的典型测距无关定位算法。第4 章中提出了 一种新的混合式定位算法h i l s ( h y b r i di l s ) ，并对之进行了分析。第5 章使用 m a t l a b 对h i l s 做了仿真和进一步的深入仿真分析。第6 章总结了全文研究工作 并对无线传感器网络中的定位技术进行了展望。 武汉理工大学硕士学位论文 第2 章无线传感器网络定位技术概述 定位是无线传感器网络中的一个重要问题，近年来得到了广泛的研究。许多 应用都依赖于节点的绝对或相对位置。例如，地理信息辅助路由协议g e a r 需 要利用节点的位置信息，避免信息在整个网络中扩散，网络管理中需要传感器 节点传回的位置信息构建拓扑图、实时统计网络覆盖情况，对节点密度低的区 域及时采取必要的措施等【4 】；同时火灾监测任务、敌方车辆监控也需要知道报警 节点的位置，否则监测信息毫无价值。 2 1 无线传感器网络定位技术的地位及应用 无线传感器网络由于其节点自身部署时不可充电( 能量有限) 、传感节点的 存储运算能力极为有限、和自组织无中心等特征，与传统的有线网络和a dh o e 网络有着很大的不同。虽然a dh o e 网络中定位算法可以加以改进运用到无线传 感器网络中，但是由于a dh o e 的节点有稳定的能量供给，故可以通过提高节点 的发射功率减少测距过程所受干扰、运用复杂的运算求解出具有较好精度的位 置信息。而这些对于传感节点自身的限制和大规模部署( 成百上千的节点) 的无线 传感器网络的应用来说是不实际的。所以无线传感器网络的定位技术具有必要 的独特性。 从总体上看，定位问题是一个一般性的问题，在a dh o e 网络和全球定位系 统g p s 中许多算法在许多年前就得以研究。而且通过g p s 的授时和测距，定位 相当精确。但是g p s 适合于无遮挡的室外环境，用户节点通常能耗高体积大， 成本也比较高，需要固定的基础设施等，不适合于低成本自组织的传感器网络1 4 。 具体来说，就是无线传感器网络节点的能量、运算能力、存储能力等资源是有 限的，大规模使用时不可能运用如g p s 那样特别昂贵的测量仪器，所以无线传 感器网络的定位问题有着与上述网络或技术有着截然不同的特点。再者，为了 提高效率，无线传感器网络的各层在实际设计时经常需要跨层操作，这样定位 协议算法在不同层次的协议中有着不同的地位。m i t 的s e n s i t 项目概览1 5 j 中将 无线传感器网络的应用( 开发) 场景表示成图2 1 所示的形式，事实上，由于如 地理信息路由( 如g e a r ) 和网络拓扑控制g a f 的这些路由层和m a c 层的协 4 武汉理工大学硕士学位论文 议都需要定位信息，所以定位( 服务) 的层次既可以位于m a c 层，也可以在路 由层，如图2 1 中左侧所加的箭头所指位置，同样也可以作为一个应用服务工作 在应用层。 e n e r g y e f f i c i e n td e c l a r a t i v e s e n s o rs i m u l a t i o ns e n s o rha r d - r a r e s e n s o rn e t w o r kn c r n t e c t u r ee x p e r i m e n t a lf r a m e w o 愀 e x p e r i m e n t a ls y s 把m 图2 1 传感器网络的应用( 开发) 场景及定位算法与网络服务、m a c 层、p h y 层 的关系 2 2 无线传感器网络中与定位技术相关的问题 无线传感器网络定位技术有其自身的特点，通常需要具备：自主组织性、健 壮性、能量高效、分布式计算的特点1 4 j 。所以无线传感器网络中的定位技术涉及 到其它领域的研究，是一个较综合的问题。同时，定位算法自身涉及到图论、 优化理论、计算复杂性问题等诸多领域的研究，又与生物信息学、数学等结合 紧密。而在无线传感器网络自身中，定位技术还涉及到能量问题 6 1 、路由和拓扑 控制。所以定位既可以作为一种高层的服务( 从而可以获得底层提供的这些信 息) ，也可以看作与各层协议不可分割、进行密切协作的机制。在图2 2 中可以 看到单个节点的构成和多个无线传感器网络之间的连接方式，在图2 2 ( a ) 中虚线 框中表示的是各种应用服务，为了简单起见只作出了定位系统和移动执行这两 个服务单元。图2 2 ( b ) 中所示的无线传感器网络通过s i n k 节点汇聚本网络信息， 武汉理工大学硕士学位论文 然后通过多a g e n t 系统( m a s ) 实现信息交互，协作完成传感任务。在这种网络结 构中，定位与人工智能领域的m a s 技术结合，并可综合网格技术，可有效地拓 展无传感器网络的应用范围。 ( a ) 单个节点的结构 ( b ) 网络结构 图2 2 无线传感器网络的节点结构和网络结构 2 3 利用定位技术在各领域开展的项目 无线传感器网络已经应用于许多领域，包括：军事、医疗、工业、环境、 农业、交通等。下面列举一些在以上的不同应用领域中已开展的项目： ( 1 ) 军事交通：t r a c k i n g ，w i n s ，a w a i r s ，n e s t ； ( 2 ) 医疗：r e s c u eo f a v a l a n c h ev i c t i m s ，t a ls i g n ； ( 3 ) 工业：c r o s s b o w 公司提供的可用于工厂的监测的解决方案； 6 武汉理工大学硕士学位论文 ( 4 ) 环境：g r e a td u c ki s l a n d ，z e b r a n e t ，o c e a n ，g l a c i e r ，v o l c a n o ； ( 5 ) 农业：g r a p e ，c a t t l eh e r d i n g ； 伯1 物流：s m a r tt o o lb o x ，s m a r ts u p p l yc h a i n 。 一些相关的综合研究项目还包括：加州大学洛杉矾分校和r o d w e l l 科学研究 所( r s c ) 开展的w i n s 项目( 由d a r p a 和军方研究实验室资助) 、a w a i r s ( 由 d a r p a 资助) 和c e n s ( n s f 资助) ，u c b e r k e l e y 的s m a r t d u s t 项目( 由d a r p a 资助) 和w e b s ，南加州大学信息科学研究所的a n r g ，m i t 的s e n s i t ，联合实 验室( a r e ) 高级传感项目的一些系统，英国政府的e p s r c 资助的一些项目等。 其中u c b e r k e l e y 开展的g r e a t d u c k i s l a n d 项目中，对于节点用g p s 固定了位置， 这种方式是实际运用中较为简单的一种方式，相同的部署方法还存在于结构健 康监测的应用中。主要依赖定位信息的项目如表2 1 所示【7 】： 表2 1 与定位有关的实际应用( 研究) 项目 项目移动性结构 拓扑 寿命融合方式 部署方式 g r e a t d u c k 静态基站、网关星型分簇7 个月全局扩散一次性手工 z e b r a n e t移动，被动基站、g p s图一 e全局扩散 一次性手工 g l a c i e r 移动，被动 基站、g p s 、星型数月全局扩散 一次性手工 m o n i t o r i n g g s m c a t t i c 移动，被动基站、g p s图数天数全局扩散一次性手工 h e r d i n g 星期 o c e a n 移动，被动卫星星型 4 5 氲 邻节点全随机，迭代 局扩散 g r a p e 静态基站树型数月全局扩散次性手工 a v a l a n c h e 移动，被动救援者 星型数天全局扩散 一次性手工 p d a v i t a s i g n 移动，被动 a d h o e 单跳数天数复合事手工 月件，扩散 t r a c k i n g 移动，被动无人驾驶飞图数天一数复合事随机 机u a v月件，扩散 t o o l b o x 移动，被动基站星型数月数全局扩敬 手工 焦 s u p p l yc h a i n 移动，被动基站星型数月数全局扩散手工 芷 v o l c a n o 静态基站星型数天数据流手工 7 武汉理工大学硕士学位论文 2 4 无线传感器网络定位技术的研究进展 n b u l u s u 博1 于2 0 0 0 年较早地提出了传感器网络的不依赖g p s 的定位算法 后，传感器网络定位算法的研究开始广泛地开展起来。测距无关的定位算法是 近几年普遍重点关注的定位机制，这些算法首先在初始阶段获得节点的连通度 信息，然后利用多个节点问每跳的平均距离来代替节点间的直线距离，从而可 以用质心法和三角形内测点法来估计节点的坐标( 或相对坐标) ，最后再逐步求 精。比较典型的算法有：d v - h o p 、h o p t e r r i a n 、a p i t 等。在这些经典算法 的基础上，结合了安全( 如s e r i _ x ，c p l ) 和能量有效的定位算法【1o 】研究非常普遍。 测距相关的定位算法( 如t o a 、t d o a 、a o a 等) 需要一些昂贵的辅助测量设备 来测量节点间的距离，且受环境影响较大，实际运用时有局限性。 近来，许多研究针对测距无关定位算法带来的精度不高的问题开展 1 1 - 1 5 1 。其 中m d s - m a p 1 1 ，1 2 1 及其分布式版本m d s - m a p ( p , * ) 1 1 ，1 3 1 ( 对m d s - m a p ( p ) 、 m d s m a p ( p , r ) 的简称，下同) 极大地改进了传统基于跳数的测距无关定位算法 的定位精度，后者的定位精度会随着跳数的增大或者网络密度的降低而急剧恶 化。m d s m a p 运用了数据分析技术m d s ，将未知节点的相对坐标利用锚节点 进行绝对坐标转换( 数学意义上称为坐标对齐) 。d w m d s 1 4 1 对m d s 进行了改 进，使用了更加有效的局部优化方法。i l s ”惧有误差精度可控的能力，具有良 好的精度，但需要节点具有测距能力。实际上，基于m d s 定位的思想加以变换 便可以将测距相关和测距无关的方法结合使用，f a s tm d s m a p 1 6 1 提出了一种简 单解决方案。根据不同的应用配备一定的测距设备是非常适合无线传感器网络 实际运用的，因为在实际中纯粹用测距相关方法需要传感器配备有较昂贵的电 子设备；纯粹用测距相关方法则达不到要求的精度，虽然增加网络密度可以提 高定位精度，但是其结果是精度不可控制，其应用范围受到了局限。还有可利 用具有移动能力节点辅助( m o t i o n - a i d e d ) 提高定位精度算法，节点可自行移动到 网络较稀疏的区域或者能够提高定位精度的区域。 2 5 无线传感器网络定位技术的难点 无线传感器网络中的定位技术包括定位算法和其中的协议。算法更偏重于 定位的基本理论依据，比如三边测量法、三角测量法和m d s 方法等。协议更偏 8 武汉理工大学硕士学位论文 重于定位初始化、消息传递等节点间的一系列协作过程，而这些又构成了算法 运用的一系列条件。所以，算法与协议构成了一个有机的整体。比如d v h o p 算法就基于三边测量法，而其平均跳数的获得则涉及到了节点间的信息交换过 程，m d s m a p 和i l s 算法在初始阶段用到了诸如d i j k s t r a 或f l o y d 算法获得最 短路径信息。所以定位问题的难点之一在于：如何将定位算法与其它各层的算 法和协议进行综合利用，利用已知的信息得出廉价和精确的定位结果，并且能 够在最大范围内适合于不同的应用场景。 2 6 本章小结 本章讨论了定位问题在无线传感器网络的地位、与各层之间的关系、已经 成功开展的在各行业中的应用项目和定位技术的研究进展和难点问题。不仅为 定位算法与各层之间的协作和跨层设计提供了系统的思路，也对定位算法的研 究方向作了分析。 9 武汉理工大学硕士学位论文 第3 章无线传感器网络定位算法分析 本章将结合目前定位算法的研究方向，对无线传感器网络定位算法的相关 问题进行讨论和思考，重点围绕其概念、本体论、评估指标、常用数学工具、 典型算法等方面进行展开论述。由于基于测距的定位算法和测距无关的定位算 法在某些程度上可以互补结合，本章将对这两种算法进行综合分析。 3 1 定位算法的本体论研究 本体( o n t o l o g y ) 的概念起源于哲学领域，是人类对自然界“存在论”的一种 哲学观点，它意味着知识和知晓( k n o w i n g ) 。2 0 世纪7 0 8 0 年代信息科学特别是 计算机科学开始了对自然世界认知的形式化的表示，即可被计算机表示、解释 和利用的知识的形式化的研究即本体。所以领域本体是结构化的领域知识， 并可以被计算机解释和利用。本体论就是用一系列的通用的定义来描述一个对 象【i ”。本体论的典型应用是在图书分类中，比如国际上通用的都柏林核心元( d c ： d u b l i nc o r e ) 对于书籍分类的描述，此外还有几年来发展起来的语义万维网 ( s e m a n t i cw e b ) 、多智能体系统( m a s ：m u l t i a g e n ts y s t e m ) 等。传感器网络的语义 研究也已经开展【1 8 】，但是在定位算法层面上还没有相关的论述。定位算法包括 其定义、约束和特征，但是由于其涉及到多种技术，定位算法还具有更多的意 义层面。由于认识层次和角度的不同，定位算法有着不同的本体论意义。本节 主要从分类、测距技术和定位算法所需的约束条件描述这几个方面作探索性的 初步研究分析。 3 1 1 定位算法的分类 由文献【4 】第6 章中对定位技术的分类方法，可对传感器网络中定位算法分为 以下几类： ( 1 ) 按照是否利用测距手段的分类方法将定位方法分为测距相关 ( r a n g e b a s e d ) 和测距无关( r a n g e - f r e e ) 两种方法。前者需要测量相邻节点间的绝对 距离或方位，并利用节点间的实际距离来计算未知节点的位置；后者无需测量 1 0 武汉理工大学硕士学位论文 节点间的绝对距离或方位，而是利用节点问的估计距离计算节点位置； ( 2 ) 按照节点定位的先后次序不同，把定位算法分为递增式的( i n c r e m e n t a l ) 和并发式的( c o n c u r r e n t ) 定位算法。递增式的定位算法通常从锚节点开始锚节点附 近的节点首先开始定位，依次向外延伸，各节点逐次进行定位；而并发式的定 位算法中所有的节点同时进行位置计算； ( 3 ) 根据定位过程中是否使用锚节点，把定位算法分为：基于锚节点的 ( a n c h o r - b a s e d ) 和无锚节点的( a n c h o r - f r e e ) 定位算法。前者在定位过程中以锚节点 作为定位参考，其它节点定位后产生一个整体绝坐标；后者指关心节点间的相 对位置，在定位过程中无须锚节点，各节点先以自身为参考，将邻近的节点纳 入自己定义的坐标系中，相邻的坐标系统一次转换合并，最后产生整体相对坐 标系统。 ( 4 ) 按照定位算法运行的协作方式可分为集中式算法、分布式算法。集中式 算法用网络中的一个( 如基站) 或固定几个节点将收集到的信息进行集中处理后 计算出坐标信息，扩展性不强，而且容易导致信息传递过程中能量的不均匀消 耗，而且可能会产生误差传播；而分布式算法将网络划分为簇后在各个簇中进 行坐标的计算，然后融合成全局的坐标，这种方法具有良好的扩展性，能够减 少误差的传播。 ( 5 ) 按照定为过程中节点是否能够移动( 如图3 1 所示) ，可分为：基于移动 辅助( m o t i o n - a i d ) 和不基于移动辅助的定位算法。 ( a ) 节点定位场景示意( b ) 具有移动能力的节点 图3 1 无线传感器网络节点定位场景示意和具有移动能力的节点 在测距相关的方法中，典型的有：t o a 、t d o a 、a o a 、r s s r s s i 等；测 武汉理工大学硕士学位论文 距无关的典型算法有i l 川：d v - h o p 、c e n t r o i d 、a p i t 、h o p t e r r i a n s e r i x ) c 、 m d s m a p 等。但是，以上的分类方法并不是绝对的，许多算法可能同时属于其 中的几类，比如m d s m a p 按照上述分类方法可称作“基于锚节点的测距无关 的集中式”算法。虽然测距无关的定位算法可以进行大规模低成本( 无需昂贵的 测距设备) 的运用，但是往往误差难以控制并达到相应要求，而且与网络密度相 关。 由于测距相关的定位算法需要一些昂贵的辅助测量设备来测量节点间的距 离，且受环境影响较大；而r s s r s s i 方法虽然实现简单，但是其精度和测距的 范围受到传感器节点的功率、网络密度、和环境的影响。所以测距方法实际运 用时有一定局限性。测距无关的定位算法是无线传感器网络定位问题中的研究 热点，这些算法首先在初始阶段获得节点的连通度信息，然后利用多个节点间 每跳的平均距离来代替节点间的直线距离，从而可以用质心法或三角形内测点 法等方法来估计节点的坐标( 或相对坐标) ，最后再逐步求精。 事实上，有很多应用需要精度较高的定位算澍14 1 5 , 2 0 l ，这些算法通常采用 迭代的方法，选择定位精度高的节点参与对未知节点的定位计算，这样的定位 精度将会大大提高，避免了盲目地增加节点密度提高节点定位精度。分类( 4 ) 中 的分布式定位中各定位自治域可以表示成图3 2 ( 每个自治域可能互相交叠) ，j l i u 等人【1 5 l 利用距离约束图( d c g ：d i s t a n c ec o n s 仃m n tg r a p h ) 来表示这一自治域， 然后针对d c g 中的可控精度和节点选择策略方面进行了进一步的研究。 将测距相关和测距无关的方法结合使用，根据不同的需求配置一定的测距 设备是一种增加精度的可行方案。因为，在实际中纯粹用测距相关方法需要传 感器配备有较昂贵的电子设备；纯粹用测距无关方法则达不到要求的精度，虽 然增加网络密度可以提高定位精度，但是其结果是精度不可控制，其应用范围 受到了局限。利用这种具有“异构”性质的传感器节点的定位算法，使得大规 模部署时可以获得一定的精度，本文将在第4 章更详细地讨论此问题。第( 5 ) 中 分类方法涉及了节点的移动，如节点根据需要可自行移动到网络较稀疏的区域， 其移动性将会涉及到路径规划等n p 问题。 1 2 武汉理工大学硕士学位论文 图3 2 无线传感器网络节点的分簇示意图 3 1 2 定位中的测距技术 本节从定位算法中的测距技术这一层面来接器典型的测距定位方法原理。 定位中一般使用的测距技术是r s s r s s i 、t o a 、t d o a ，许多研究口，1 4 1 5 , 2 】 都以这两种方法作为其测距手段；还有一些如a o a 之类的典型方法，但是需要 用到天线阵列等一些附加的设备。由于r s s r s s i 、t o a t d o a 会受到多径干扰 和衰减现象的影响，需要分析r s s r s s i 、t o a 及其测距的定位误差问题。 对于一个t o a 接收端来说，其目标是识别直接视线路径( d l o s ：d i r e c t l i n e o f - s i g h t p a t h ) 的到达时间t o a 。d l o s 总的能量可被接受端和发射端任何的 障碍物减弱。后到达的非视线关系( n l o s ) 多径干扰部分的信号将可能会比 d l o s 的能量还要强。在两个设备的距离增加时，后到达的部分将会使整个接受 能量增加一些。这种增加可以被测量能量延时的设备察觉。而且，研究人员已 经通过同步设备准确测量d l o s 信号后发现，整个接收能量中的n l o s 信号部 分会随着随路径长度的增加而增加。结合其它的噪声和干扰，这种n l o s 信号 能量呈现白干扰性，并会随着距离的增大而减少t o a 测量中的信噪比。 同样，基于r s s 的距离测量精度会随着距离的增大而下降。在接收端和发 送端周边的物体会由于多径效应以衰减因子的形式减少了信号能量。如此多的 乘积形式的累积结果导致了r s s 的对数正态分布。如果节点f 接收节点_ ，传送的 以毫瓦表示的功率为p o ( m w ) ，那么接收功率的对数形式为p o = 1 0 l o g l o p o ( m w ) 为正态的。由于射频信道测量表明 的方差在路径中是数值很大的常量，因此 _ p 。，通常可表示为： 弓( 弓，口名)，。、 乞= p o 一1 0 刀，l 0 9 1 0 ( 或d o ) 武汉理工大学硕士学位论文 其中，岛是距离为西的毫瓦的对数的平均功率，五是衰减的方差，p o ( d b m ) 是 距离西的接收功率，一般d o = l m ，而且凡常通过f r e es p a c e 路径衰落方程算出。 怖是与环境有关的路径衰落指数。 从上述西的函数接收能量模型中，距离的极大似然估计值为 乞= d o l 0 ( p o p y ) ( 1 0 n v ) ( 3 2 ) 如果只= 豆，那么最，= 吐，。当豆，可以推知为何测距误差会随着距离增大。 考虑接收能量测量时d b 误差不变：= 瓦一只，那么点，= 。d 一| 0 a ( i o n p ) ，这样实 际的距离就会乘上一个恒定的因子。事实上，测距估计误差点，一吐，直接正比于 西，比例系数为1 0 ，t ”一1 。假定接收功率的标准偏差仃。是恒定的，那么测距 误差的标准偏差也将与距离成正比。基于r s s 测距将会在长路径下导致非常大 的误差，因此会影响其应用范围。 卜# ? ? ? ： ：j ，。： ：蓦多 图3 3 发射功率水平( p o w e r l e v e l ) 不同产生的网络连通度也不同 从以上分析可知，以t o a 和r s s 作为测量手段都会得到不精确的测距结果。 当然，可以增加节点的密度来减少成对的测距误差( 也可以同通过提高发射功 1 4 武汉理工大学硕士学位论文 率达到增加节点密度的效果，如图3 3 所示) 。a s a v v i d e s l 2 6 1 通过实验作出了如 图3 4 中距离对测距误差的影响，三角标记线表示测量值，圆点标记线表示理论 值。在一定发射功率下，t o a 有效测量距离最大3 m ，准确测量2 m ；r s s 最大 2 0 m ，准确测量7 m 。他同时指出天线的方向对测量有影响，而接收机测量设备 的r x t x 对位置影响很小。 蔷 邮 垂i 言重 苫8 j 距离d i s t a n c e ( c m ) ( a ) t o a ( b ) r s s 图3 4t o a 和r s s 的定位结果与距离的关系 武汉理工大学硕士学位论文 3 1 3 定位算法中的约束条件 定位算法的设计与运行需要节点的参与，作为传感器网络的节点在能量、 体积、运算速度、通信半径等有着一系列的限制约束，而这些约束又不可避免 地对定位算法的设计产生影响，所以可以将节点的与定位算法有关的约束用一 种本体论来描述，即将物理的传感器节点的实体针对定位算法的研究需要进行 抽象后成为本体论化描述。另一方面，从无线传感器网络的层面来看，与定位 算法密切相关的还有网络的密度、锚节点的密度、网络的拓扑、具有不同能力 的异构节点的分布等一些约束，这些条件也对定位算法的性能。这样的本体论 描述，不仅可以对定位算法的评估有统一的平台与表示、适用范畴更加清晰， 也是理论研究中对定位算法形式化定量描述的重要部分，可以作为理论与实际 应用的桥梁。图3 5 中提出一种定位算法中的约束条件的本体描述。 图3 5 定位算法约束条件的本体论描述 本节仅对约束进行了初步探讨，随着研究目标和传感器节点硬件实体的不 同，将存在不同的描述形式。在第4 章提出的定位算法中，将利用与上述部分 的本体论描述相似的结构作为节点是否进行优先定位的评估指标。 3 2 无线传感器网络定位算法的评估指标 至今为止，已经有许多不同的定位算法，并且不同的算法适合于不同的应用 环境。所以衡量它们的定位精度、定位质量和其鲁捧性都是必要的。 1 6 武汉理工大学硕士学位论文 3 2 1 定位精度的表示 定位精度可以用定位误差表示，定位误差越低，定位精度越高；反之亦然。 单个节点的定位误差可以表示为： 虽然传感器节点在计算上所花费的能量相比与通信模块来说非常少，但是 这不意味着定位算法可以不考虑其复杂性问题，定位算法在某些特殊情况下必 须要求具有一定的响应速度。比如，在追踪敌方目标，或者需要立即找出火灾 区域的时候，如果定位算法有过长的延时，同样会导致重要信息的位置信息的 缺失，造成构成重要信息的时空信号的不完整。但是，由于无线传感器节点硬 件平台的差别，不同的处理芯片的速度不尽相同，所以难以对定位算法的响应 速度s 用精确的数学式表示，但是可以作出以下形式化的描述： j = ( 定位算法延时+ 硬件处理延时+ 其它模块的延时) 运行总时间 所以，对于特定硬件平台的硬件单元延时是难以克服的，所以必须尽量减 少定位算法导致的延时，也就是应该主要减少定位算法的时间复杂性。 3 2 3 定位算法的鲁棒性 定位算法的鲁棒性体现在定位算法在不同环境下的精度的波动范围。在本 文中，主要用定位算法在同一拓扑下的网络密度时算法精度的变化表示定位算 法的鲁棒性： d r m l r = 啪) 一e ( f + 1 ) l ( 3 5 ) 仁d ( 月) 其中，白。表示在诫d 种拓扑时算法的平均误差，衡量鲁棒性