（计算机应用技术专业论文）无线传感器网络自身定位算法研究(1).pdf

摘要 微机电系统( me ms , m i c r o - e l e c t r o - m e c h a n i s m s y s t e m ) 、片上系 统 ( i f l c , s y s t e m o n c h i p ) 和无线通信技术的进步孕育了无线传感器网络 ( ws n , wi r e l e s s s e n s o r n e t w o r k ) 。这种网络系统可被广泛地应用于国防军事、环境监测、交通管 理、医疗卫生、制造业、反恐抗灾等领域。ws n 作为 一 个全新的研究领域，r 1 科技工作者提出了大量的挑战性研究课题，网络 自身定位问题就是其中之一。 本论文的研究工作是围绕着无线传感器网络自身定位算法这一崭新的课题 进行的，主要完成的工作包括: 1 从距离 ( 或角度 )测量和定位计算两方面出发论述无线传感器网络 宵 点 定位的基本原理。 2 .综述了无线传感器网络自身定位算法和系统的性能评价指标、 分类方法， 以及现有的典型算法和系统，并对现有的成果进行总结。 3 .在现有 e u c l i d e a 。算法基础上，融入距离矢量路由和迭代循环的思想，设 计出一种新的定位算法， 称为h o p - e u c l i d e a n ， 对其核心思想讨沦 ， 并进 行仿真验证。结果显示该算法具有良好的定位精度和覆盖率。 4 .展望未来的研究工作和方向。 关键字:无线传感器网络、自身定位算法、自身定位系统 ab s t r a c t a d v a n c e s i n m e m s ( m i c r o - e l e c t r o - m e c h a n i s m s y s t e m ) 、s o c i s v s t e m o n c h i p ) a n d wi r e l e s s c o mm u n i c a t i o n s h a v e ma d e ws n ( wir e l e s s s e n s o r n e t w o r k ) p o s s i b l e , w h e r e e a c h s e n s o r n o d e i n d i v i d u a l l y s e n s e s t h e e n v i r o n m e n t b u t c o l l a b o r a t i v e l y a c h i e v e s c o mp l e x i n f o r m a t i o n g a t h e r i n g a n d d i s s e m i n a t i o n t a s k s . i n s t r u me n t i n g t h e p h y s i c a l w o r ld t h r o u g h l a r g e n e t w o r k s o f w i r e l e s s s e n s o r n o d e s r e q u i r e s t h a t t h e s e n o d e s b e v e r y s m a l l , l ig h tw e i g h t , u n t e t h e r e d , a n d u n o b t r u s i v e . t h e s e n e t w o r k e d s e n s o r n o d e s , h o w e v e r , p o s s e s s s e v e r a l c h a r a c t e r i s t i c s t h a t h a v e c h a l l e n g e d m a n y a s p e c t s o f t r a d i t i o n a l c o m p u t e r n e t w o r k d e s i g n . t h e p r o b l e m o f s e l f - lo c a l i z a t io n , t h a t i s , d e t e r m in i n g w h e r e a g iv e n n o d e i s p h y s ic a l l y o r r e la t i v e l y l o c a t e d i n a n e t w o r k , is o n e o f t h e c h a l le n g i n g t a s k s , a n d y e t e x t r e me l y c r u c i a l f o r ma n y a p p l ic a t i o n s . t h e r e s e a r c h o f t h i s t h e s i s i s b a s e d o n t h e a n a l y s i s o f a g r e a t d e a l o f r e c e n t t e c h n i c a l r e p o rt s a n d r e s e a r c h r e s u l t s o n w s n a n d it s m a i n w o r k i n c l u d e : 1 . f r o m t h e r a n g e f i n d i n g a n d l o c a l iz a t i o n in g m e t h o d , t h e f u n d a m e n t a l p r i n c i p l e s o f t h e s e l f - lo c a l i z a t io n t e c h n iq u e s o f a r e d e s c r i b e d . 2 . t h e e v a l u a t io n c r it e r i o n o f t h e p e r f o r ma n c e a n d t h e t a x o n o m y f o r wir e l e s s s e n s o r n e t w o r k s s e l f - l o c a l iz a t i o n s y s t e m a n d a l g o r it h ms a r e d e s c r ib e d , t h e p r i n c i p le s a n d c h a r a c t e r i s t ic s o f r e c e n t r e p r e s e n t a t i v e l o c a l i z a t i o n a p p r o a c h e s a r e d i s c u s s e d a n d p r e s e n t e d i n d e t a i l 3 . b a s e d o n t h e e u c l i d e a n a l g o r i t h m , u t i l iz e i n g t h e it e r a t i v e a p p r o a c h t o i m p r o v e t h e d e n s i t y o f a n c h o r n o d e s g r a d u a l l y , a n d t a k i n g a d v a n t a g e o f th e c o n c e p t o f d v r o u t i n g , a n o v e l d i s t r ib u t e d , h o p - b y - h o p , s i m p l e p o s it io n i n g a l g o r i th m, r e f e r r e d to a s h o p - e u c l i d e a n , i s p r e s e n t e d a n d s imu l a t e d . t h e r e s u lt s s h o w t h a t it h a s t h e g o o d p o s i t i o n i n g a c c u r a c y a n d c o v e r a g e - 4. th e d i r e c t io n s o f r e s e a r c h i n t h i s a r e a a r e in t r o d u c e d k e y w o r d s : w i r e l e s s s e n s o r n e t w o r k s , s e l f - l o c a l i z a t i o n a lg o r i th m , s e l f - l o c a l i z a t i o n s y s t e m 1 1 西 匕 _ 业人学硕士论文 无线传感器网络自身定位算法研究 竺 一 音已f 户 刁寻. f.j . 习 研究背景 无线传感器网络 ( w s n , w i r e l e s s s e n s o r n e t w o r k )是微机电系统 ( h e m s m i c r o - e l e c t r o - m e c h a n i s m s y s t e m ) 、 片上系统 ( s o c , s y s t e m o n c h i p ) 和无 线 通信技术高度集成而孕育出的一种新型信息获取和处理模式。 其典型工作方式如 下 : 使用飞行器将大量传感器节点 ( 数量从几百到几千个) 抛撒到感兴趣区域， 节点通过自组织快速形成一个无线网络。 随机分布的集成有传感器、 数据处理单 元和通信模块的微小节点借助于内置的形式多样的传感器测量所在周边环境中 的热、红外、声纳、雷达和地震波信号， 从而探测包括温度、湿度、噪声、光强 度、压力、土壤成分、移动物体的大小、 速度和方向等众多部署者感兴趣的物质 现象。在网络中，节点既是信息的采集和发出者，也充当信息的路由者，采集的 数据通过多跳路由到达网关。网关 ( 也称为 s i n k n o d e )是一个特殊的节点，可 通过 工 。 t e r n e t 、移动通信网络、卫星等与监控中心通信，也可利用无人机飞越 网络上空，通过网关采集数据。 无线传感器网络在环境、健康、家庭和其他商业领域有广阔的应用前景， 在 军事、 空间探索和灾难拯救等特殊领域有其得 天独厚的技术优势 。以军事 应用 为例，无线传感器网络将会成为 c 4 i s r t ( c o m m a n d , c o n t r o l , c o m m u n i c a t i o n , c o m p u t i n g , i n t e l l i g e n c e , s u r v e i l l a n c e , r e c o n n a i s s a n c e a n d t a r g e t i n g ) 系统不可或缺的一部分。c 4 1 s r t系统的目标是利用先进的高科技技术，为未来 的现代化战争设计一个集命令、 控制、通信、计算、 智能、监视、侦察和定位于 一体的战场指挥系统， 受到了军事发达国家的普遍重视。 因为无线传感器网络是 山密集型、 低成本、 随机分布的节点组成的，自组织性和容错能力使其不会因为 某些节点在恶意攻击中的损坏而导致整个系统的崩溃， 这一点是传统的传感器技 术所无法比拟的， 也正是这一点， 使无线传感器网络非常适合应用在恶劣的战场 环境中， 包括监控我军 兵力、装备和物资: 监视冲突区: 侦察敌方地形和布防; 定位攻击 目标;评估损失: 侦察和探测核、生物和化学攻击。在战场，指挥员往 往需要及时准确地了解部队、 武器装备和军用物资供给的情况， 敷设的传感器将 西 匕 _ 业人学硕士论文 无线传感器网络自身定位算法研究 竺 一 音已f 户 刁寻. f.j . 习 研究背景 无线传感器网络 ( w s n , w i r e l e s s s e n s o r n e t w o r k )是微机电系统 ( h e m s m i c r o - e l e c t r o - m e c h a n i s m s y s t e m ) 、 片上系统 ( s o c , s y s t e m o n c h i p ) 和无 线 通信技术高度集成而孕育出的一种新型信息获取和处理模式。 其典型工作方式如 下 : 使用飞行器将大量传感器节点 ( 数量从几百到几千个) 抛撒到感兴趣区域， 节点通过自组织快速形成一个无线网络。 随机分布的集成有传感器、 数据处理单 元和通信模块的微小节点借助于内置的形式多样的传感器测量所在周边环境中 的热、红外、声纳、雷达和地震波信号， 从而探测包括温度、湿度、噪声、光强 度、压力、土壤成分、移动物体的大小、 速度和方向等众多部署者感兴趣的物质 现象。在网络中，节点既是信息的采集和发出者，也充当信息的路由者，采集的 数据通过多跳路由到达网关。网关 ( 也称为 s i n k n o d e )是一个特殊的节点，可 通过 工 。 t e r n e t 、移动通信网络、卫星等与监控中心通信，也可利用无人机飞越 网络上空，通过网关采集数据。 无线传感器网络在环境、健康、家庭和其他商业领域有广阔的应用前景， 在 军事、 空间探索和灾难拯救等特殊领域有其得 天独厚的技术优势 。以军事 应用 为例，无线传感器网络将会成为 c 4 i s r t ( c o m m a n d , c o n t r o l , c o m m u n i c a t i o n , c o m p u t i n g , i n t e l l i g e n c e , s u r v e i l l a n c e , r e c o n n a i s s a n c e a n d t a r g e t i n g ) 系统不可或缺的一部分。c 4 1 s r t系统的目标是利用先进的高科技技术，为未来 的现代化战争设计一个集命令、 控制、通信、计算、 智能、监视、侦察和定位于 一体的战场指挥系统， 受到了军事发达国家的普遍重视。 因为无线传感器网络是 山密集型、 低成本、 随机分布的节点组成的，自组织性和容错能力使其不会因为 某些节点在恶意攻击中的损坏而导致整个系统的崩溃， 这一点是传统的传感器技 术所无法比拟的， 也正是这一点， 使无线传感器网络非常适合应用在恶劣的战场 环境中， 包括监控我军 兵力、装备和物资: 监视冲突区: 侦察敌方地形和布防; 定位攻击 目标;评估损失: 侦察和探测核、生物和化学攻击。在战场，指挥员往 往需要及时准确地了解部队、 武器装备和军用物资供给的情况， 敷设的传感器将 西 比 业人学硕十论文无线传感器网络 白身定位算法研究 采集相应的信息， 并通过汇聚节点将数据送至指挥所， 再转发到指挥部， 最后融 合来 自各战场的数据形成我军完备的战区态势图。 在战争中， 对冲突区和军事要 地的监视也是至关重要的， 通过铺设传感器网络以更隐蔽的方式近距离的观察 敌方的布防:当然，也可以直接将传感器节点撒问敌方阵地，在敌方还未来得及 反应的时间内迅速收集利于作战的信息。 由于无线传感器网络巨大的科学意义和应用价值， 它己经引起了世界发达国 家的学术界、 军事部门 和工业界的 极大关注。 从2 0 0 1 年开始， d a r p a ( 美国国 防 部高级研究计划署) 己把智能传感器网络作为一项最高优先发展的研究计划， 出 资近 7 亿美元， 在众多大学和研究机构展开传感器网络的基础研究， 以求获得瓦 角大楼想要的所谓战区“ 超视觉” 数据 . 2 0 0 2 年8 月， n s f ( 美国国家科学基金 会) 一期资助 4 0 0 0 万美元在u c l a成立了传感器网络研究中心， 联合周边大学( 包 括l c ed , u s c 和l s r 等) 展开 “ 嵌入式 智能 传感器” 的 研究 项甘， ， ，以 求利用传 感器网络对我们生活的物理世界实现全方位的测试与控制， 这也是美国国情咨文 中有关 n g 工 最主要的远景规划之一。美国英特尔公司、 微软公司等信息 l . 业界巨 头也开 始了传感器网络方面的 工作， 纷纷设立或 启动相 应的行动计划。日 本、 英 国、 意大利、巴西等国家也对传感器网络表现出了极大的兴趣， 纷纷展开了该领 域的研究工作。 无线传感器网络与传统的无线网络 ( 如 w l a n和蜂窝移动电话网络)有着不 同的设计目标， 后者在高度移动的环境中通过优化路由和资源管理策略最大化带 宽的利用率， 同时为用户提供一定的服务质量保证。 而无线传感器网络中除少数 节点需要移动外， 大部分节点 都是静 止的们 。 因为它们通常运行在人无法接近的 恶劣，县至危险的远程环境中， 能源无法替代，设计有效的策略延长网络的生命 周期成了无线传感器网络的核心问题。在研究初期，人们曾经一度认为成熟的 工 n t e r n e t 技术加上 a d h o c 路由机制对无线传感器网络的设计是足够充分的，但 深入的研究表明 别 : 无线传感器网络与传统无线网 络有着明显不同的技术要求， 前者以数据为中心，后者以传输数据为目的。一些为自组织的a d h o c 网络设计 的协议和算法并不适合传感器网络的特点和应用的要求。节点标识 ( 如地址等) 的作用在传感器网络中就显得不是十分重要， 因为应用程序不怎么关心单节点上 的 信 息; 中 间 节 点 上 与 具 体 应 用 胡关的 数 据处 理 、 融 合 和 缓 存 倒 显 得非 常 必 要 在密集性的无线传感器网络中， 相邻节点间的距离非常短， 低功耗的多跳通信橙 西北 f _ 业大学硕十论文无线传感器网络 自身定位算法研ih 式节省功耗， 同时增加了通信的隐蔽性， 也避免了 长距离的无线通信易受外界噪 声干扰的影响。 这些独特的要求和制约因素为无线传感器网络的研究提出了新的 技术问题。 . 2无线传感器 网络的自身定位 问题 作为 一种全新的技术， 无线传感器网 络位科技工作者提出了 许多具有挑战 性 的研究课题， 而定位就是其中之一。定位是大多数应用， 特别是军事应用的基础。 无线传感器网络中的定位机制与算法包括两部分 : 节点自身定位和外部目标定位， 前者是后 者的 基础司 。 对于大多数应用， 不知道传感器位置 而感知的数据是没有意义的了 。传感器 节点必 须明确自身 位置才能详细说明 “ 在什么 位置或区域发生了 特定事件” ，实 现对外部目 标的定 位和追 踪p q 。另 一方面，了 解传感器节点 位置信息还可提高路 由 效率tn , y ，为网络提供命名空间( m - 1 i ， 向部署 者报告网络的覆盖质量l ;, p l ， 实现 网 络的负载均衡f 13 , i6 ) 和网络拓扑的自 配置 1 7 1 w s n节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很大 限制，低功耗是其最主要的设计 目标。而人工部署和为所有网络节点安装 c p s 接收器都会受到成本、 功耗、 扩展性等问 题的限制， 甚至在某些场合可能根本无 法实现， 因此必须针对其密集性， 节点的计算、 存储和通信等能力都有限的 特点 设计有效的低功耗定位算法。 从 a t , p l ， 实现 网 络的负载均衡f 13 , i6 ) 和网络拓扑的自 配置 1 7 1 w s n节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很大 限制，低功耗是其最主要的设计 目标。而人工部署和为所有网络节点安装 c p s 接收器都会受到成本、 功耗、 扩展性等问 题的限制， 甚至在某些场合可能根本无 法实现， 因此必须针对其密集性， 节点的计算、 存储和通信等能力都有限的 特点 设计有效的低功耗定位算法。 从 a t , p l ， 实现 网 络的负载均衡f 13 , i6 ) 和网络拓扑的自 配置 1 7 1 w s n节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很大 限制，低功耗是其最主要的设计 目标。而人工部署和为所有网络节点安装 c p s 接收器都会受到成本、 功耗、 扩展性等问 题的限制， 甚至在某些场合可能根本无 法实现， 因此必须针对其密集性， 节点的计算、 存储和通信等能力都有限的 特点 设计有效的低功耗定位算法。 从 a t ( 2 )定位计算。本章就分别从这两个方面论述节点定位的基本 原理 。 2 . 1基本概念描述 通常， 无线传感器网 络中需要定位的节点称为未知节点 u n k n o w n n o d e ) ; 而通过人工部署或 g p s系统已知位置，并帮助未知节点定位的称为锚节点 ( a n c h o r ) ，也称为信标节点 ( b e a c o n ) .邻居节点指在一个节点通信半径内， 可 直接相互通信的节点。 节点的无线射 程使用r 表示。 测距误差和定位误差一般以 误差值与节点无线射程r 的比 例表示， 例如定位精度为2 0 % 表示定位误差相当于 节点无线射程的 2 0 % ，而测距精度为 2 0 % 则表示测距误差相当于节点无线射程的 2 0 %0 2 . 1节点间距离 ( 或角度)的测量方法 在 无 线 传感 器 网络 中 ， 节 点 间距 离或 角度 的测 量 技 术常 用 的 有 r s s i , t o a , t d o a 和 a o a . r s s i ( r e c e i v e d s i g n a l s t r e n g t h i n d i c a t o r ) :己 知发射功率，在 接收节点 测量接收功率， 计算传播损耗， 使用理论或经验的信号传播模型将传播损耗转化 为距离，该技术主要使用 r f 信号。因传感器节点本身具有无线通信能力，故其 是 一 种 低 功率 、 廉 价 的 测距 技术 ， r a d a r , s p o t o n 等许 多 项目 ,. _ 1- _4, 中 使 用了 该 技术。 它的主要误差来源是环境影响所造成的信号传播模型的建模复杂性: 反射、 多径传播、 非视距 n o n - l i n e - o f - s i g h t , n l o s ) ， 天线增益等问 题都会对相同距 离产生显著不同的传播损耗。 通常将其看作为一种粗糙的测距技术， 有可能产生 士 5 0 % 的 钡 临 巨 误差 . .u t o .a ( t i m e o f a r r i v a l ) :该技术通过测量信号传播时间 来测量距离。使用 t o a技术最基本的定位系统是 g p s , g p s系统需要昂贵、高能耗的电子设备来精 西北 业大学硕十论文 无线传感器网络自身定位算法研究 第二章 无线传感器网络节点定位基本原理 无线 传感器网络中 绝大多 数现有的 定位方法都包含两个基本步骤: ( 1 ) 距离 ( 或角度)测量; ( 2 )定位计算。本章就分别从这两个方面论述节点定位的基本 原理 。 2 . 1基本概念描述 通常， 无线传感器网 络中需要定位的节点称为未知节点 u n k n o w n n o d e ) ; 而通过人工部署或 g p s系统已知位置，并帮助未知节点定位的称为锚节点 ( a n c h o r ) ，也称为信标节点 ( b e a c o n ) .邻居节点指在一个节点通信半径内， 可 直接相互通信的节点。 节点的无线射 程使用r 表示。 测距误差和定位误差一般以 误差值与节点无线射程r 的比 例表示， 例如定位精度为2 0 % 表示定位误差相当于 节点无线射程的 2 0 % ，而测距精度为 2 0 % 则表示测距误差相当于节点无线射程的 2 0 %0 2 . 1节点间距离 ( 或角度)的测量方法 在 无 线 传感 器 网络 中 ， 节 点 间距 离或 角度 的测 量 技 术常 用 的 有 r s s i , t o a , t d o a 和 a o a . r s s i ( r e c e i v e d s i g n a l s t r e n g t h i n d i c a t o r ) :己 知发射功率，在 接收节点 测量接收功率， 计算传播损耗， 使用理论或经验的信号传播模型将传播损耗转化 为距离，该技术主要使用 r f 信号。因传感器节点本身具有无线通信能力，故其 是 一 种 低 功率 、 廉 价 的 测距 技术 ， r a d a r , s p o t o n 等许 多 项目 ,. _ 1- _4, 中 使 用了 该 技术。 它的主要误差来源是环境影响所造成的信号传播模型的建模复杂性: 反射、 多径传播、 非视距 n o n - l i n e - o f - s i g h t , n l o s ) ， 天线增益等问 题都会对相同距 离产生显著不同的传播损耗。 通常将其看作为一种粗糙的测距技术， 有可能产生 士 5 0 % 的 钡 临 巨 误差 . .u t o .a ( t i m e o f a r r i v a l ) :该技术通过测量信号传播时间 来测量距离。使用 t o a技术最基本的定位系统是 g p s , g p s系统需要昂贵、高能耗的电子设备来精 西北_ 业大学硕士论文无线传感器网络自身定位算法研究 确同步卫星时钟。因 w s n节点硬件尺寸、价格和功耗限制， g p s和其他 t o a技术 对无线传感器网络而言几乎是不可行的。 t d o a ( t i m e d i f f e r e n c e o n a r r i v a l ) : t d o a测距技术被广 泛应用在无线传 感器网 络的定位方案中。无线传感器网络 在利用t d o a 技术测量节点间 距时与 蜂 窝无线网络的移动台定位和机器人导航定位不同。 如图2 - 1 所示， 一般是在节点 上安装超声波收发器和r f收发器。 测距时， 在发射端两种收发器同时发射信号， 利用声波与电磁波在空气中传播速度的巨大差异在接收端通过记录两种不i司 信 号 ( 常使用 r f 和超声波信号)到达时间差异，基于已知信号传播速度，直接把 时间转化为距离。已 有多种定位算法 t0 , u . 2 4 - 2 fi 1 使用t d o a 实 现测距。 该技术的 测距 精度较r s s i 高l 州 ， 通常传播距离仅为 信号的传播影响。 可达到厘米级，但受限于超声波传播距离有限 ( 超声波信号 2 0 - 3 0 英尺，因而网络需要密集部署 )和 n l o s问题对超声波 虽然 己有发现并减轻 算和通信开销，不一定适用于低功耗的 n l o s影响的技术r - a . : v ; ， 但都需要大量 计 w s n 应用中。 图2 - 1 t d o a 测距技术 示怠 a o a ( a n g l e o f a r r i v a l 卜 这是一种估算邻居节点发送信号 方向的技术，可 通过天线阵列或多个接收器结合来实现，除定 位外，还能提供节点的方向 信息， 如 m i t的 t h e c r i c k e t c o m p a s : 等项目 ; 3 o9 中 就利用多个 接收 器提出了 基于 a o a 的 硬件解决方案，其原型系统可在士 4 0 “ 角内以士5 。的误差确定接收信号的方 向。同样，a o a 技术也受外界环境影响，如噪声、n l o s问题等都会对测量结果产 生不同影响。同时，a d a 需要额外硬件，在硬件尺寸和功耗上可能无法用于传感 器节点。 以 f 四种a ll 距方法各有利弊，以r s s i 和 t d o a两种方法最为常用。 2 . 2节点定位计算方法 在获得节点间的距离 ( 或角度) 后就可以 采用三角测量法( t r i a n g u l a t i o n ) , 三边测量法 ( t r i l a t e r a t i o n )或最大似然估计法 ( m u i c i i a t e r a t i o n s ) 计算节 西北_ 业大学硕士论文无线传感器网络自身定位算法研究 确同步卫星时钟。因 w s n节点硬件尺寸、价格和功耗限制， g p s和其他 t o a技术 对无线传感器网络而言几乎是不可行的。 t d o a ( t i m e d i f f e r e n c e o n a r r i v a l ) : t d o a测距技术被广 泛应用在无线传 感器网 络的定位方案中。无线传感器网络 在利用t d o a 技术测量节点间 距时与 蜂 窝无线网络的移动台定位和机器人导航定位不同。 如图2 - 1 所示， 一般是在节点 上安装超声波收发器和r f收发器。 测距时， 在发射端两种收发器同时发射信号， 利用声波与电磁波在空气中传播速度的巨大差异在接收端通过记录两种不i司 信 号 ( 常使用 r f 和超声波信号)到达时间差异，基于已知信号传播速度，直接把 时间转化为距离。已 有多种定位算法 t0 , u . 2 4 - 2 fi 1 使用t d o a 实 现测距。 该技术的 测距 精度较r s s i 高l 州 ， 通常传播距离仅为 信号的传播影响。 可达到厘米级，但受限于超声波传播距离有限 ( 超声波信号 2 0 - 3 0 英尺，因而网络需要密集部署 )和 n l o s问题对超声波 虽然 己有发现并减轻 算和通信开销，不一定适用于低功耗的 n l o s影响的技术r - a . : v ; ， 但都需要大量 计 w s n 应用中。 图2 - 1 t d o a 测距技术 示怠 a o a ( a n g l e o f a r r i v a l 卜 这是一种估算邻居节点发送信号 方向的技术，可 通过天线阵列或多个接收器结合来实现，除定 位外，还能提供节点的方向 信息， 如 m i t的 t h e c r i c k e t c o m p a s : 等项目 ; 3 o9 中 就利用多个 接收 器提出了 基于 a o a 的 硬件解决方案，其原型系统可在士 4 0 “ 角内以士5 。的误差确定接收信号的方 向。同样，a o a 技术也受外界环境影响，如噪声、n l o s问题等都会对测量结果产 生不同影响。同时，a d a 需要额外硬件，在硬件尺寸和功耗上可能无法用于传感 器节点。 以 f 四种a ll 距方法各有利弊，以r s s i 和 t d o a两种方法最为常用。 2 . 2节点定位计算方法 在获得节点间的距离 ( 或角度) 后就可以 采用三角测量法( t r i a n g u l a t i o n ) , 三边测量法 ( t r i l a t e r a t i o n )或最大似然估计法 ( m u i c i i a t e r a t i o n s ) 计算节 西北 卜 业大学硕士论文 点位置 口 无线传感器网络白身定位算法研究 2 .2 . 1 三角测量法 三角测量定位方法也称为信号到达角度 ( a o a )定位法或方位测量定位法l 伟 z . :川 。 该方法是通过未知节点接收器天线或天线阵列测出 锚节点发射电 波的入 射 角，从而构成一根从未知节点到锚节点的径向连线，即方位线。在二维平面中， 利用两个或更多锚节点的a o a 测量值， 按照a o a 定位算法确定多条方位线的交点， 即可计算出未知节点的估计位置。如图2 - 2 所示， c f - s- 一 一 扫呼 一 / a 才 丫吐 图2 - 2三角测量定位示意 假 设 未 知 节 点a ( 坐 标 为(x n , y o ) ) 分 别 测 得 锚 节 点b , c坐 标 分 别 为( x i , y l) ， ( xy z ) )发出信号的到 达角度 分别为。 . 和。 ， ，则式2 - 1 成立， t a n ( 8 , ) =x 。一x 少。一y, 1 , 2 2 一 ! 通过求解上述非线性方程， 可以 得到未知 节点的 位置( x , y o o 2 .2 .2 三边测量法与最大似然估计法 在三维空间中， 知道了一个点到四个锚节点的距离， 就可以确定该点的坐标， 这一点与全球定位系统 ( us )的 基本原理 一样。只不过在无线传感 器网络中， 坐标系大多是二维空间，也不需要时钟同步，因此， 只要知道了一个节点到三个 锚节点的距离就可以确定节点的位置。如图 2 - 3 ( a )所示，三边测量定位法的 基本原理就是求三个己知半径和坐标圆心的圆的交点。 少 协1势 一不 又才，声 西北_ t 业大学硕士论文无线传感器网络自身定位算法研究 图2 一 3三边测量定位与最大似然估计定位示意 但山于无线传感器网络节点的硬件和能耗限制，通常节点间测距误差较大， 因 此经常出现三个圆无法交于一点的情况，这时就需要使用最大 似然估计定 位 法， 其基本原理就是寻找一个使测距距离与估算距离之间差异最小的点，以该点 为未 知节点的 位置。 如图2 - 3 ( b ) , 假设。 为未知节点坐标是( x o , y o ) ， 而 1 , 2 , 3 , 4 均为 锚节点 坐标分别为( x i y l ) - ( x 2 , y 2 ) ( x 3 , y 3 ) ( x e y 4 ) , 0 节点 到四个 锚 节点 的 距 离 分 别是 p i ip 21 p 3 p ; 设 a n = p ， 一 ( ( x ， 一 x , ) 2 + ( y ， 一 y o ) 2 一 2 f 2,0 = ,0 2 一 ( ( x 2 一 x o ) 2 + ( y 2 一 y o ) 2 ) 2 一 3 f ,0 = p 3 一 ( ( x : 一 x a ) 2 + ( y 3 一 y o ) 2 ) 2 一 4 f 4o = p 一 ( ( x ; 一 x o ) 2 + ( y , 一 y o ) 2 ) 2 一 5 其 中夕 表 示 节 点i 与节 点。 的 测量 距 离， 而( x ; - x o ) 十 沙一 儿 ) ) 则 表 示 节 4 点i 与节 点。 的 估 算 距 离。 求 节点。 坐 标( x . , y o ) , 使艺天 。 之 和 最 小 。 即 f ( x o , y a ) = min ( f i 。 + 儿。 十 关; + 人。 ) 2 一 6 在上例中，根据二维空间距离计算公式，可以获得下面的方程组: 户1= p2= 2一7 p4= 式 2 - 7中，( x o , y o ) 是未知量， 这是非线性方程组，可以采 用线性化方法来 求 解。 如果 近 似知 道节点 的 估 计位 置， 可以 将 其真 实 位置( x o ,y o ) 和 近 似位 置 ( x o ,y o ) 之 间 的 偏 离 用 位移( a x , a y , ) 来 标记 。 将 式2 - 7 按 泰 勒 级 数 绕 近似 位置 展 开， 那么 便可将位置偏移( a x , d y o ) 表示为已 知坐标和距离测量值的线性函数: 西_ 1 匕 业 大学硕十论文 无线传感器网络 自身定位算法研究 单一测量距离可表示为: p ; = , ! ( x 一 x ) 2 + ( y ， 一 ， 。 ) ， 一 f (x , y . ) ， 二 1,2 ,3 ,4: 一 ， 单一近似距离可表示为: p ; 一 ( x 一 、 。 ) ， + (y 一 y a ) ， 一 f (x a iy o )， 二 1,2 ,3 ,4: 一 9 如上所述，节点的真实位置由近似分量和增量两个部分组成，即: x 0 = x , + a x , y o = 乡 。 十 妙n 2一1 0 因此 ，有 ax , y . ) =f ( x 0 + a x o , y o + 匀。 ) 上式右边函数用泰勒级数展开成: ， 、 o f ( z o , 夕 。 ) a f ( 瓦, 夕 n ) .1 ( x 。 十 公。 ， 夕 。 十 匀。 ) 二 f ( x o 乡 。 ) + 乙止 弓 l u l 位。 十 卫 牛 井 竺 竺细。 a x o”a y o 2一1 1 为了消除非线性， 上述展开式中截去了一阶偏导数之后的各项。 偏导数经计 算如下: 干 a f ( i , 夕 。 ) a x a f ( x n jo a y o 式2 - 1 2 中， p , : 可以得到: x; 一x , r ; y，一y o r ; 7 =1 , 2 , 3 , 42一1 2 。 将式 2 - 9 , 2 - 1 1 、 2 - 1 2 带入式 2 - 8 , p一 户一 x - x o o x - y， 一yo 汽 匆 2一1 3 这样就完成了 对式 2 - 8 相对于未知数( a x, a y . ) 的线性化。 将上述表达式重 新安排，使 己知量在左边，未知量在右边，得到: p， 一p;=x 一x , 只 4 x + y 二y o a y 2一1 4 为表达方便，引进下述新变量以简化上述公式: 西北 上 业大学硕十论文 无线传感器网络自身定位算法研究 户= 户一 p a ,. = 玉二 x 2一1 5 a 。 一 兰卫 干11，j、11卫|、 这样，式 2 - 1 5 可以表示为 o p , =a r 酝。 +a , 匀。 2一1 6 要在二维空间中确定一个点的坐标， 必须有至少三个参考点。 在无线传感器 网络中， 节点之间的连接很多， 大多数节点都可以直接或间接的获得到三个以上 参考点的不精确距离。因此可以得到一个方程组: ia p 竺 2 i o p , = a . 公。 + a , 匀。 = a ,y = 公。 + a , ,2 妙。 2一1 7 = a . ,v 公。 + a 匀。 当 n 3 时，上面就是过定义方程组。 而无线传感器网络内的距离测量由于存 在距离误差， 正好可以 利用 这样的 冗余获得更高的 精确 度。 在文献2 2 1 中， 作者收 集的数据显示了 在距离测量误差较大的 情况下 超过标准 .5 0 % ) , 在 2 维空间内 定位一个被 5 个或更多的已知位置节点包围的节点时， 所获得定位位置与实际位 置的平均偏差小于射频距离的 5 % 0 卜 i*讨宁望古程f 2 -1 7 可以伸用最小二乘法来求解，具体步骤如下: 艺sa p ， 一 ( a , a x , + a y ,a y o ) ) z 二 最 小 值二 .f ( a x , a y . ) 2一1 8 为了 求 得函 数f ( 4 x o , a y o ) 取 得 最小 值 时的a x . - a y , ， 对 函 数求 导 并 令 之 等 于 0 ，即: a f ( a -t o 匀( , ) a 么 x , 一 艺a , a p一 (a xo + “ * d y u ) l 一 。 2一1 9 a f ( a, 匀o ) a 匀 = 艺a y, o p ， 一 ( a x,4 x o + a ,a y . ) 一 0 2一2 0 式 2 -1 9 , 2 -2 0 经过整理，可以获得: 西北 业人学硕十论文 无线传感器网络白身定位算法研究 却 = “ 二 叉a 2 十 匆 。 艺a ., a y., a p 一 u .r 艺 a .x,a y , + a y o 艺 a 尸 2a y , 可以得到: 2一21 力vj ?万。n万。砒 几f日f卜卜匕由 艺a .,a p 艺a y 一 艺a y , a p 艺 a ., =上生一一 一一二= i- 一一 一1= 1 一 1= 1一一 a .,2 a y ， 一 (叉a 二 a ， ) zy , a s ,a y ,) j =i 1 =1 艺今 p 艺 气2a , , a p ; i a .; 一 y a , a p , y a . 2一22 气 艺 a , 艺 a y , 一 (艺 a f ,a y x 酝匀 护!.!哥.1.t 使用式2 -2 2 ，就可以求出估计节点位置与实际位置的大概偏差，如果精度 不满足要求，可以将矫正后的坐标代替估计坐标，进行进一步的矫正，直到 a % 匀。 小 于规定的门 限值结 束。 以 上过程仅描述了各个锚节点权值相等的情况， 在实际应用中， 可以 采用加 权最小二乘法，即 根据每个距离测量值的 精度 ( 可靠性) ， 在最小二乘中采用不 同的权值，以提高精度。理论己证明，当权值取值合理时，可使定位误差显著减 小，但具体如何定义与分配权值还有待研究。 西北 卜 业人学硕十论文 无线传感器网络 白身定位算法研究 第三章 无线传感器网络自身定位系统和算 法综述 从 a t 网络节点由于周围环境或 自身原因( 如电池耗尽、 物理损伤) 而出现失效的 问题: 外界影响和节点硬件精度限制造成节点间点到点的距离或角度测量误差增 大的问题。 由于 环境、 能耗和其他原因， 物理地维护或替换传感器节点或使用其 他高精度的测量手段常常是 十分困 难或不 可行的。因此，定位系统和算法的软、 硬件必须具有很强的容错性和自适应性， 能够通过自动调整或重构纠正错误、 适 应环境、减小各种误差的影响，提高定位精度。 功耗一 功耗是对 w s n的设计和实现影响最大的因素之一。由于传感器节点 电池能量有限， 因此在保证定位精度前 提下， 与功耗密切相关的定位所需的计算 量、通