（计算机软件与理论专业论文）基于连通性的无线传感网络节点定位问题研究.pdf

摘要 摘要 无线传感网络具有可快速部署、易组网、不受有线网络约束等优点，因此 具有广泛的应用前景。在这些实际应用中，节点定位有着广泛的需求，是无线 传感网络的关键问题。为了有效的解决节点定位问题，研究者提出了大量的定 位算法。这些算法通常被分为基于测距的算法和无需测距的算法。基于测距的 定位算法需要测量节点之间的距离或角度信息才能计算出未知节点的位置。这 类算法虽然在定位精度上有一定的优势，但需要额外的硬件设备和大量的复杂 计算，因此并不适用于低功耗、低成本的实际应用。而无需测距的定位算法( 本 文就是指基于连通性的定位算法) 仅利用节点之间连通信息进行定位，硬件需 求简单，计算量小，对于普通的传感节点来说更为实用。然而，基于连通性的 节点定位算法普遍存在定位精度不高的问题。为了提高定位精度，新的基于连 通性的定位算法开始加入大量复杂的计算和额外的消息传递，丽这对于计算和 存储能力有限的传感节点来说是个很难完成的任务。因此，本文试图在不增 加复杂计算和通信开销的条件下，改进基于连通性的节点定位算法，提高定位 精度。同时提高算法的实用性，力求将定位算法应用到实际的定位系统中。围 绕以上目标，本文对基于连通性的节点定位问题展开以下的研究： ( 1 ) 研究无线传感网络节点定位问题的相关工作。目前为止，节点定位问 题已经形成了一套比较完善的理论体系，其中包括定位算法的分类， 定位算法的性能评价标准以及典型的定位算法和系统。 ( 2 ) 针对质心系列算法在区域边界定位误差大的问题，提出了基于冗余节 点的质心算法。利用功能简单的冗余节点来改进算法在区域边界的定 位精度，并调节冗余节点的信号射程及摆放形式来深入分析定位效果。 此外，提出了一种新的定位算法评价标准，力求准确体现算法在整个 定位区域的效果。 ( 3 ) 针对基于跳数的定位算法，在节点稀疏排列或不规则排列的网络中定 位效果差的问题，提出了基于邻居信息校正的跳数定位算法。在基于 跳数信息的定位算法基础上，利用未知节点估算的邻居情况与真实收 集到的邻居情况进行对比，选取相似程度高的节点作为准锚节点。再 用节点间邻居表的相似程度表示它们的远近程度，然后利用远近程度 分配权值。最后，用锚节点和准锚节点对其它节点进行加权质心定位， 校正其它节点的位置，从而提高算法的整体定位精度。 ( 4 ) 综合运用多种定位方法，开发了一个基于连通性的节点定位原型系统。 摘要 本文主要介绍系统的需求分析，软硬件平台，以及系统的设计与实现。 本文研究中的贡献和创新点包括： 利用功能简单的冗余节点，在不增加复杂计算的条件下，提高了质心 算法的定位精度。 关键词： 提出了一种定位算法的评价标准，从新的角度来评价算法性能。 在不增加通信开销的情况下，利用邻居信息改进基于跳数的节点定位 算法，提高了定位精度。 在定位原型系统中，设定了接收信号强度的高可信阈值，并综合 运用了多种定位算法。 无线传感网络节点定位连通性邻居节点跳数质心算法 a b s t r a c t a b s t r a c t 、矾r e i e s ss e n s o rn e t w o r k s ( w s c a l lb ed e p l o y e dq u i c “y ，e s t a b l i s h e de a s i l y a n dn o tr e s t r a i n e db yw i r e dc o 肌e c t i o n ，s ot l l e yh a v eab r o a dp r o s p e c to f a p p l i c a t i o n l 0 c a l i z a t i o ni sn e e d e db ya l lk i n d so fa p p l i c a t i o n sa n dt h u sak e yp r o b l e mi nw s n i no r d e rt os o l v et h el o c a j i z a t i o np r o b l e me f f i c i e n t l y ，r e s e a r c h e r sp r o p o s e dal o to f l o c a l i z a t i o na l g o r i t h m s t h e yc a no r e nb ec a t e g o r i z e di n t om g e - b a s e da l g o r i t h s a n dr a n g e - f r e ea l g o r i t h m s r a j l g e - b a s e do n e sn e e dt oe s t i ma _ t et h ed i s t a l l c eo ra i l g l e b e t w e e nn o d e sf o rl o c a l i z a t i o n t h o u g hr a 【n g e b a s e da l g o r i t l l i i l sh a v ea d v a n t a g e si n a c c u r a c y ，t h e yn e e da d d i t i o n a lh a r d w a r ea j l dc o m p l e xc o m p u t m i o na 1 1 dt l l u sa r en o t a d a p t a b l e t o e n e 唱y l i m i t e da n dl o w c o s t 印p l i c a t i o n s 1 1 1c o n t r a l s t ，啪g e - f b e a l g o r i t h m s ( i nt h j st h e s i s ，t 1 1 e ym e a l lc o l l i l e c t i v i 锣- b a s e d1 0 c a l i z a t i o na l g o r i m m s ) m e r e l ym a k eu s eo fc o r m e c t i v i t yi i l f - 0 册a t i o nb e t w e e nn o d e s ，s ot i l e yn e e dn o a ( i d i t i o n a lh 削w a r ea j l dh a v en oc o m p l e xc o m p u t a t i o nw h i c ha r em o r ep r a c t i c a l h o 、v e v e r ，t 1 1 ea c c u r a c yo fc o n n e c t i v i t y - b a s e da l g o r i t h m si sl o w mo r d e rt oi m p r o v e t h ea c c u r a c y ，n e wa l g o r i t sa d dp l e n t yo fc o m p l e xc o m p u t a t i o na n da d d i t i o n a l c o m m u n i c a t i o no v e r h e a d b u ti ti san o n a c c o m p l i s h a b l et a s kf o rc o m m o ns e n s o r 1 1 0 i d e sw i t hl i m i t e d c a p a b i l i t yo fc o m p u t a t i o na r l ds t o r a g e t h e r e f o r e ，、奶，t 0 i m p r o v et h ea c c u r a c yo fc o 衄e c t i v i t y - b a s e da l g o r i t h n l sw i t h o u ta d d i n gc o m p l e x c o m p u t a t i o na n dc o m m u n i c a t i o no v e r h e a d a l s o ，w ew a n tt od e s i g np r a c t i c a l a l g o r i t h m sw h i c hc a nb ea d o p t e db yr e a l 印p l i c a t i o ns y s t e m s t 0 如l n l lg o a l sm e n t i o n e da b o v e ，t h i st h e s i sr e s e a r c h e si n t ot h ef o l l o w i n g a s p e c t so fc o n n e c t i v i t ) ，- b a s e dl o c a l i z a t i o np r o b l e mi nw s n ： ( 1 ) w ei n v e s t i g a t ei n t or e l a t e dw o r ko fl o c a l i z a t i o ni nw s n s o 虹n o d e l o c a l i z a t i o nh a sf 0 n n e da i l i n t e g r a t e d t h e o r e t i c a l s y s t e mi n c l u d i n g c l a s s i f i c a t i o n s ，e v a l u a t i o nm e t r i c s ，r e p r e s e n t a t i v ea l g o r i t h ma n ds y s t e m s ( 2 ) i no r d e rt os o l v et h e p r o b l e mt h a t c e n t r o i da l g o r i t h mh a sap o o r p e r f o n i l a n c e i n b o r d e r o ft h el o c a l i z a t i o na r e a ，w ep r o p o s e dt h e r e d u n d a n t m o t e - b a s e dc e n t r o i da l g o r i t h m ( r m b c ) w em a k ei l s eo f l o w - c o s tr e d u n d a n tm o t e si m p r 0 v et h ea c c u r a c ya n da d 印tt h e 聊1 9 ea n d d e p l o y m e n to ft h em o t e sf o r 向r t h e ra n a l y s i s i no r d e rt oe v a l u a t e l o c a l i z a t i o na l g o r i t h m sc o m p r e h e n s i v e l y ，w ea l s op r o p o s ean e wm e t r i c c a l l e d c o v e r a g eo fl o c a l i z a t i o n ” i i i a b s t r a c t i no r d e rt os o l v et h ep r o b l e mt h a th o p - c o u n t - b a s e di o c a l i z a t i o na l g o r i t h m s a r en o te 伍c i e n ti nt h e i 玎i ：g u l a ro rs p a r s en e t w o r k s ，w ep r o p o s e dt h e n e i g h b o r - b a s e d l o c a l i z a t i o n s y s t e ma l g o r i t h m ( n b l s ) b a s e do n h o p c o u n t b a l s e dl o c a l i z a t i o na l g o r i t s ，、cm a k eu s eo ft h es i m i l a r i t y b e t 、v e e ne s t i m a t e da i l d p r a c t i c a ln e i g h b o ri n f o m a t i o n ， t os e l e c t q u a s i - a 1 1 c h o rn o d e s a r e n a r d s ，w i mt h eh e l po fa n c h o ra n dq u a s i a n c h o r n o d e s ，、v ea d o p tw c e n n 。o i dt or e v i s el o c a t i o n so fo t h e rn o d e s d e v e l o pac o i u l e c t i v i t y - b a s e dl o c a l i z a t i o nd e m os y s t e mw h i c hi n t e 伊a t e s v a r i o u sa l g o r i t h m st 0m e e tt h en e e do fl o c a l i z a t i o n t 1 1 i st h e s i sm a i n l y i n t r o d u c e so u rs y s t e m sr e q u i r e m e ma n a l y s i s ，s o f t w a r e 1 1 a r d w a r ep l a t f 0 h 1 1 ， d e s i g na n di m p l e m e n t a t i o n 。 c o n t r i b u t i o n sa n di n n o v a t i o n so ft h i st h e s i si n c l u d e ： w i t ht h eh e i po fr e d u n d a n tm o t e s ，i m p r o v et h ea c c u r a c yo fc e n t r o i d a l g o r i m mw i t h o u ta n yc o m p l e xc o m p u t a t i o n p r o p o s e an e wm e t r i cw h i c h “a l u a t e sl o e a | i z a t i o na l g o r i t h m s 如man e w d i m e n s i o n i m p r o v et h ea c c u r a c yo fh o p - c o u n t b a s e da l g o r i t l u l l sw i t h o u ta d d i t i o n a l c o m m u n i c a t i o no v e r h e a d ， b yt a k i n gn e i g h b o r i b r n l a t i o ni m o c o n s i d e r a t i o n i nt h el o c a l i z a t i o nd e m os y s t e m ，d e f i n eah i g h - r e l i a b l et h r e s h o l do fr s s i a n di n t e g r a t ev a r i o u sa l g o r i t m s k i yw o r d s ：、杭玎e l e s ss e n s o rn e t 、v o r k ，l o c a l i z a t i o n ，c o n n e c t i v i t y ；n e i g h b o rn o d e ，h o p c o u m c e n t r o i d ) ) 0 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：垄耋查 王口o g 年6 月2 5 日 第1 章绪论 第1 章绪论 本章摘要无线传感网络作为一个新兴的研究领域，具有广泛的应用前景。在这 些实际应用中，节点定位有着广泛的需求，是无线传感网络研究中的关键问题。 本章首先介绍无线传感网络的研究背景，接下来介绍研究节点定位问题的意义， 常用的术语以及问题的基本定义。然后，讨论节点定位的研究的现状和存在的 问题，从而引出本文的主要内容基于连通性的传感网络节点定位问题研究。最 后，介绍本文的主要工作及安排。 1 。1 研究背景 伴随着无线通信技术的不断成熟以及嵌入式系统的快速发展，无线传感网 络应运而生。它是一个由计算机科学，电子工程，无线通信，环境科学，智能 交通等多个学科协同发展的研究领域，其中蕴含了巨大的创新空间。无线传感 网络将数据采集、数据传输与数据处理三个功能集于一身，它可以帮助人们更 快速，更直接的感知周围环境的信息，最大限度的发挥人们认识世界和改造世 界的能力。无线传感网络不同于传统的有线网络，它无需固定设备支撑，可以 快速部署并自行组网。因此，它的应用领域极其广泛，包括军事、环境、经济 和社会生活的方方面面。作为一种全新的普适计算模式，无线传感网络已经成 为国际上的研究热点。 无线传感网络的出现源于美国国防部为军事应用而提出的研究计戈i j 【1 0 j 。此 项技术一经提出，便受到了广泛的关注，并且得到了迅速的发展。无线传感网 络先后入选美国商业周刊评出的2 l 世纪最具影响力的技术和美国技术评 论杂志评出的改变人类生活的十大新兴技术1 3 】。到了2 0 0 3 年，美国自然科学 基金投资超过3 0 0 0 万美元，大力推动无线传感网络相关的基础理论研究。为了 利用无线传感网络节省能源并提高工业效率，美国能源部也投资超过一千万美 元进行这方面的研究。同时，在商业需求的驱动下，英特尔，微软，朗讯和i b m 等美国著名公司纷纷加入到无线传感网络的研究中来。加州大学伯克利分校， 麻省理工大学，加州大学洛杉矾分校，弗吉尼亚大学等世界著名高校也很早就 参与到无线传感网络的研究之中，并取得了大量高水平的成果。随后，越来越 多的美国大学投入到各类与无线传感网络相关的研发计划中。 随着无线传感网络在美国的迅速兴起，世界各国也开始了相关的研究。在 欧洲，以瑞士洛桑联邦工业大学为代表的研究团队。在无线传感网络的基础理 第l 章绪论 论研究方面做出了巨大的贡献。在亚洲，日本和韩国也都开展了与无线传感网 络相关的研究计划。我国的无线传感网络研究开始的相对较早。上世纪末，无 线传感网络就已经被中国科学院列为信息领域未来的重点研究课题。同时，中 科院计算技术研究所开始了无线传感网络的全面研究，主要包括自主开发传感 节点和传感器，建立无线传感网络分析与管理平台s n a m p 和开发多种无线传 感网络的应用系统。随着国家自然科学基金、9 7 3 计划、8 6 3 计划对无线传感网 络投入大量资金，清华大学、中国科大、哈工大、浙江大学、北京邮电大学、 上海交大、南京大学等国内著名高校也纷纷加入到无线传感网络研究的队伍之 中。2 0 0 6 年国家9 7 3 计划项目“无线传感网络的基础理论及关键技术研究集 中了国内多个实力雄厚的研究团队重点攻关，力求取得具有国际影响力的理论 成果。同时，国家发改委c n g i 计划设立了多项与无线传感网络相关的示范工 程，这也大大推动了无线传感网络在国内的实际应用。 目前本文作者参与的项目包括9 7 3 项目“无线传感网络的基础理论及关键 技术研究和国家发改委项目“基于c n g i 和w s n 的矿山井下定位与应急联 动系统”。定位问题是这两个项目的重要组成部分。本文的目标是不仅要研究基 础理论和关键技术，还要将理论技术与实际系统相结合，做出对社会有实用价 值的成果。 1 2 无线传感网络节点定位问题概述 1 2 1 研究意义 无线传感网络被广泛地应用于环境科学、农业发展，煤矿安全、预防火灾、 医疗救护和战场监控等方面。在这些无线传感网络的应用中，节点定位有着广 泛的需求，因此是无线传感网络中的关键问题。 在环境科学方面【4 】，无线传感网络使原本复杂的户外长期数据采集过程变 得极为容易。比如监测土壤的成分和水源环境，跟踪野生动物，研究植物的生 长情况等。对于以上的这些应用场景，只有快速准确的定位传感节点，才能够 有效地帮助人们发现特殊情况及时采取措施。 在农业发展方面，无线传感网络也可以应用在农业发展中，监测农作物是 否受到害虫的侵害、土壤的酸碱度和施肥状况等。我们承担的c n g l 0 5 项目精 准农田灌溉系统就是一个典型的应用。为了达到准确灌溉的目的，系统需要利 用节点定位技术发现灾害或干旱的地点。 在煤矿安全方面【5 1 ，节点定位也是一个至关重要的问题。矿井属于事故高 2 第1 章绪论 发区域，只有及时准确的找出事故的发生地点，才能及时采取措施，减小事故 带来的损失。然而，目前矿井中还无法提供具有无线通信功能的井下定位系统， 地面人员很难及时找出事故的发生地点。针对这个情况，可以在井下部署无线 传感网络，利用节点定位技术实现对井下人员的实时监控。我们承担的c n g i 0 6 项目“基于c n g i 和w s n 的矿山井下定位与应急联动系统”就是这方面的一 个典型系统。 在预防火灾方面，无线传感网络可以部署在保护建筑或货物仓库，利用无 线传感节点感知周围的温度和烟雾情况，从而判断是否有火灾发生。当监控中 心接收到发生火灾的数据信息后，必须利用节点定位技术获得火灾发生的地点。 准确的定位可以帮助人们及时采取措施，减少火灾带来的损失，避免人员伤亡。 在医疗救助方面，无线传感节点体积小，携带方便的特点，因此可以让每 个病人随身配备一个无线传感节点。同时在医院的走廊和病房也部署大量位置 固定的传感节点。利用节点定位技术，医生就可以及时发现病人的位置，并可 以根据节点上的传感器采集的数据，判断病人的身体状况。 在战场监控方面【6 j ，无线传感网络也受到极高的重视。因其具有隐蔽和组 网迅速的优点，非常适用于战场监控。部队可以利用飞机从空中播撒传感节点， 在战场区域形成一个大规模的无线传感网络。然而这些节点的位置都是不可预 知的，因此只有利用定位技术获得传感节点的位置信息后，中心指挥部才能够 区分出散布于战场各个角落的传感节点，从而实现对敌军的人员调拨和武器运 输进行实时的监控。 综上所述，无线传感网络节点定位在众多领域内都有着十分重要和紧迫的 应用需求，因此有必要对此问题进行更加深入和透彻的研究，为社会进步和国 家发展做出贡献。 1 2 2 常用术语 锚节点( a n c h o rn o d e ) ：无线传感网络中，位置信息己知的节点( 配有g p s 定位装置或摆放位置已知) 。 未知节点( u n k n o w nn o d e ) ：无线传感网络中，初始状态没有位置信息， 需要通过定位算法获得定位的节点。 基站( b a s e ) ：通过程序烧制板m i b 5 1 0 ，与服务器相连的传感节点。 邻居节点烈e i 曲b o rn o d e ) ：能够互相直接通信的节点，互为邻居节点。 连通性( c o n n e c t i v i t y ) ：如果两个节点互为邻居，他们就是连通的。 跳数( h o pc o u n t ) ：两个节点之间传递消息，总共经历的节点个数( 不包 括起始节点) 。 第1 章绪论 到达时间( t i m eo fa r r i v a l ，t o a ) ：信号从一个节点到另一个节点所需 的时间。 到达时间差( t i m ed i 虢r e n c eo f a 盯i v a l ，) o a ) ：两种速度不同的信号， 从一个节点到另一个节点所需要的时间差。 到达角度( a n g l eo fa r r i v a l ，a o a ) ：节点接收到的信号相对于自身轴 线的角度。 接收信号强度( r e c e i v e ds i g l l a ls t r e n g t hi n d i c a t o r ，r s s d ：节点接收到的 射频信号强度，单位为d b m 。 紧密耦合：指锚节点不仅被仔细地部署在固定的位置，并且通过有线 介质连接到中心控制器。 松散耦合：指所有节点采用无中心控制器的分布式无线协调方式进行 工作。 1 2 3 问题定义 传感节点的放置大部分采用随机放置( 如空中抛撒) 的方法部署，而且节点 的位置可能随时问推移有所改变，所以要想得到所有传感节点的位置信息并不 是一项容易的任务。因为它数目众多，考虑到成本问题，每个节点都带有定位 系统( g p s ) 是不可能的。通常采用的方法是让小部分节点带有定位系或者是位置 预先设定且不再移动。这种节点称为锚节点，可以通过携带g p s 定位设备等手 段获得自身的精确位置。定位问题的主要研究方向是如何利用这些锚节点提供 的位置信息和所有节点之间消息传递，计算出未知节点的位置信息。 节点定位问题的基本定义l7 j 就是利用少量己知自身位置的锚节点( 采用g p s 定位或者预先放置的节点) ，来获得未知节点的位置信息。节点定位主要分为两 个步骤：( 1 ) 借助未知节点与锚节点之间某种形式的通信( 如无线电或声波通信 等) ，测量出未知节点到邻近锚节点的距离，或获得邻近的锚节点和未知节点之 间的信号到达角度，或未知节点与锚节点之间的连通性信息；( 2 ) 通常使用三边 测量法，三角测量法或极大似然估计法【8 】来计算未知节点的位置。三边测量法 的理论依据是如果知道了一个节点到三个以上参考点的距离，就可以确定该点 的位置。与三边测量法类似，三角测量法是指如果知道三个以上参考点到一个 节点的角度，就可以确定该点的位置。 4 第1 章绪论 i， 麟卜7 角度 ： t l ， 距多一入 巳，一乏度 距离叫o ：，一，厦 ，角度 l 一一二一锚节点 丫 ，桨 、 图1 1 节点定位问题的基本定义 也有一些系统( 如s p o t l i 曲t 【9 】和l i 曲t 1 1 0 u s e 【1 0 】) 并没有锚节点，而是加入了能 够发射激光束的中心设备。这些系统成本较高，并不适用普通节点组成的传感 网络。 1 2 4 研究现状和存在的问题 最早的无线传感网络定位系统是由a t & t 剑桥实验室开发的室内定位系 统a c t i v eb a d g e 【“】。从那之后，研究者们开始了无线传感网络中的节点定位问 题研究，相继出现了微软公司开发的r a d a r 【1 2 l ，m i t 开发的c r i d k e t 【h l4 1 ，哈 佛大学开发的m o t e l r a c k 【1 5 】，弗吉尼亚大学开发的s p o t l i g l l t 【9 j 等定位系统。近几 年来，无线传感网络中的定位问题的研究已经不再局限于紧密耦合型【l6 】和基于 基础设施的定位方法，而更重视对松散耦合型和无需基础设施的定位方法的研 究。前者的代表性研究成果包括a c t i v eb a d g e 【l i 】，黜如a r 【1 2 j ，s m a nr o o m s 州， a c t i v eo m c e 【1 引，s m a r tf 1 0 0 r 【19 1 ， s p o t 0 n f 2 0 1 ，h i b a l lt r a c k e r 【2 1 1 等。而后者的研 究成果包括麻省理工学院开发的c r i c k e t 定位系统1 1 3 ，1 4 】，瑞士洛桑联邦工业大学 提出的s p a 相对定位算法1 2 2 1 ，加州大学伯克利分校提出的凸规划定位算法【2 3 刀l ， 路特格斯大学开发的a p s 定位系统和d v 系列算法【2 5 ，2 6 1 ，加州大学洛杉矶分校 开发的a h l o s 定位系统【2 7 1 ，通用型定位算法【2 8 】，密苏里大学提出的m d s m a p 定位算法1 2 9 1 ，弗吉尼亚大学提出的a p i t 定位算法【3 0 j 和s m c 定位算法【3 1 1 。 最常用的分类方式是把所有算法分为基于测距的算法和与无需测距的算法 【3 0 】两大类。基于测距的定位算法需要测量节点之间的距离或角度信息，然后利 用三边测量法，三角测量法或极大似然估计法【3 2 】计算出未知节点的位置。典型 的测距方法包括接收信号强度测量法1 3 3 】，到达时间测量法【3 4 1 ，到达时间差测量 法【3 5 1 ，到达角度测量法【3 6 】。接收信号强度测量法虽然实现简单，但测距误差很 大田j ，很难满足定位需求；到达时间测量法需要节点间精确的时间同步，对于 无需基础设施的普通传感网络来说很难实现；到达时间差测量法要求节点能够 同时处理射频和超声波两种信号，不仅需要额外的硬件设备，而且超声波存在 5 第l 章绪论 传播距离有限和受非视距影响大的问题；到达角度测量法也会受外界环境影响， 而且需要额外硬件。此外，基于测距的定位方法为了减小测距误差对定位的影 响，加入许多复杂的处理机制( 如多次测量，循环定位求精【3 7 ，3 8 】) ，同时增加了 算法的计算量和通信开销。所以，基于测距的定位机制虽然在定位精度上有一 定优势，但并不适合功能简单，成本低廉的普通传感节点。而无需测距的方法( 即 基于连通性的算法) ，它不需要距离或角度信息，仅利用节点之间连通信息( 即 能否相互通讯) 进行定位。基于连通性的节点定位算法具有计算量小，实施成 本低的优势，对于计算能力有限的普通传感节点来说更为实用。因此，此类算 法成为了定位问题研究的主流方向。典型基于连通性的算法包括质心算法【3 9 1 ， d v - h o p 【2 5 1 ，m d s m a p 【2 9 】，a m o r p h o u s 【4 0 1 ，h c r l 4 。 目前，基于连通性的定位算法普遍精度不高，这是亟待解决的问题。于是， 如何提高基于连通性定位算法的精度，成为研究者们的重点课题。为了提高基 于连通性的定位算法的精度，研究者们加入了大量的复杂计算和额外的消息传 递，而这对于计算和存储能力有限的节点来说是一个很难完成的任务。因此， 本文试图在几乎不增加运算复杂性和通信代价的情况下，改进基于连通性的定 位算法精度。同时提高算法的可用性，力求将定位算法应用到我们的实际系统 中。 1 3 主要工作及安排 针对无线传感网络定位算法的研究现状和存在的问题，本文做了相应的研 究，主要工作如下： ( 1 ) 研究无线传感网络节点定位问题的相关工作。其中包括定位算法的分 类，定位算法的性能评价标准以及典型的定位算法和系统。 ( 2 ) 在不增加复杂计算的情况下，改进质心算法的定位精度。在质心算法 的基础上，加入少量功能简单成本很低的冗余节点。通过调整冗余节 点的覆盖范围、摆放形式来校正未知节点位于区域边缘时的定位，从 而提高算法的整体定位精度。 ( 3 ) 在不增加通信开销的条件下，改进基于跳数信息的定位算法，提高定 位精度。在基于跳数信息的定位算法基础上，利用未知节点估算的邻 居情况与真实收集到的邻居情况进行对比，选取相似程度高的节点作 为准锚节点。再用节点间邻居表的相似程度表示它们的远近程度，然 后利用远近程度分配权值。最后，利用锚节点和准锚节点对其它节点 进行加权质心定位，校正其它节点的定位位置。 6 第l 章绪论 ( 4 ) 综合多种定位方法，开发无线传感网络节点定位原型系统。这个系统 是基于c n g i 和w s n 的矿山井下定位与应急联动系统的前期任务。未 来，这个定位原型系统将作为定位子系统镶嵌到基于c n g i 和w s n 的 矿山井下定位与应急联动系统中。 本文的组织如下： 第一章为本文的绪论部分，介绍了传感网络定位问题的研究背景和研究趋 势。 第二章介绍无线传感网络节点定位问题的相关工作。 第三章介绍基于冗余节点的质心算法。利用冗余节点，降低当未知节点位 于定位区域边缘时的定位误差。并通过模拟试验证明基于冗余节点的质心算法 的定位精度明显高于质心算法。 第四章介绍基于邻居信息校正的跳数定位算法。利用邻居信息校正基于跳 数信息的定位，并将算法应用在实际的传感网络中进行测试和分析。 第五章介绍无线传感网络节点定位原型系统，主要包括系统的需求分析、 软硬件平台、以及系统的设计与实现。 第六章对本文进行了总结，提出了一些需要进一步研究的问题。 7 第2 章节点定位闯题的相关工作 第2 章节点定位问题的相关工作 本章摘要节点定位是无线传感网络应用中的关键问题，因此研究者们很早就开 始了定位问题的研究。目前为止，节点定位已经形成了一套比较完善的理论体 系，那么想要开展定位问题的研究，就必须深入了解已有的相关工作。本章首 先介绍无线传感网络节点定位算法的分类，然后列举出定位算法的性能评价标 准。最后，对典型的定位算法和系统进行了详细的介绍和分析。 2 1 定位算法的分类 伴随着无线传感网络的快速发展，研究者提出了大量的节点定位算法。为 了深入研究定位问题，也为了方便不同的应用场景选择定位方法，通常研究者 要对定位算进行分类。然而，从不同的角度和方面分析定位算法，就会产生不 同的分类方式。在国内外已有工作的基础上，王福豹等人在文献 4 2 】中归纳出7 种无线传感网络节点定位算法的分类方式，本节主要介绍其中常用的5 种。 2 ，1 1 基于测距的定位与无需测距的定位口0 1 这是一种最常用的定位算法分类方式。基于测距( r a n g e b a s e d ) 的定位先测 量节点之间的距离或角度信息，然后利用三边测量、三角测量或最大似然估计 法计算未知节点的位置。典型的测距方法包括接收信号强度测量法，到达时间 测量法，到达时间差测量法，到达角度测量法。基于测距的定位算法虽然在定 位精度上有一定优势，但因需要附加硬件，并不适合有功能简单，成本低廉的 普通传感节点。而无需测距的方法( 即基于连通性的算法) ，它不需要距离或角 度信息，仅利用节点之间连通信息( 即能否相互通讯) 进行定位。基于连通性 的节点定位算法具有计算量小，实施成本低的优势，对于计算能力有限的普通 传感节点来说更为实用。因此，此类算法成为了定位问题研究的主流方向。质 心算法( c e n t r o i dm e t h o d ) f 捌，d v - h o p f 2 卯，m d s m a p 【2 9 】，a p i t f 3 0 1 ，a m o r p h o u s f 4 0 1 ， h c r l 等都是典型的基于连通性的定位算法。 2 1 2 集中式定位与分布式定位 把无线传感网络采集的各种信息都发送到中心服务器，并在中心服务器上 进行节点定位计算，这就是集中式定位。集中式定位能够收集到所有节点的数 8 第2 章节点定位问题的相关工作 据进行综合分析和计算，而且定位计算在服务器上完成，可以加入大量复杂计 算和循环求精过程以获得更高的定位精度。然而，集中式定位有一个明显的缺 陷，就是所有的数据消息都要通过基站发送到中心服务器。那么，基站转发的 消息数量远远高于其它传感节点，相应的能量消耗也比其它节点快。一旦，基 站的能量消耗殆尽，将导致整个网络与中心服务器无法通信，定位也就无法完 成。为了避免基站失效带来的严重影响，研究者们又提出了一类节点之间通过 消息传递自行完成定位计算，无需中心服务器参与的定位算法，也就是分布式 定位。分布式定位很难达到集中式定位精度，这是因为传感节点的计算能力和 存储空间有限，无法完成比较复杂的计算。但分布式定位算法不存在基站的能 量瓶颈，因此分布式定位的健壮性更高。典型的集中式定位有质心算法1 3 驯， 如s m a p 定位算法【2 9 1 。而典型的分布式定位包括d v 二h o p 【2 5 】定位算法和 m o t e l r a c k 定位系统【”j 。 2 1 3 绝对定位与相对定位阳1 绝对定位是将未知节点定位在一个实际存在的空间位置，定位结果具有唯 一性，其它节点的移动不会对它产生影响。目前，大部分定位算法提供的都是 提供绝对定位。另外一些算法是以无线传感网络中的部分传感节点的位置作为 参考建立一个相对的坐标系，给出的定位结果是一个相对坐标，这种定位被称 为相对定位。相对定位不需要为锚节点配备g p s 定位装置，可以节省网络的成 本。而且一些应用场景( 如路由) 并不需要节点的绝对位置，相对定位的结果 已经可以满足需求【删。典型的相对定位算法包括s p a 定位算、法【2 2 1 ，l p s 定位系 统【4 5 1 。而m d s m a p 定位算法【2 9 】在执行过程中，如果网络中有足够多的锚节点 就可以提供绝对定位，否则提供相对定位。 2 1 4 物理定位与符号定位嘲 不同的应用场景对定位的结果要求也不相同，有些情况下定位结果必须是 一个物理上的绝对位置坐标，而有些情况只需要结果是未知节点位于某一个区 域或某一个房间。前者被称为物理定位，后者则被称为符号定位。例如，未知 节点的定位结果是直角坐标系中的( 1 2 ，1 6 ) ，这就是物理定位；而未知节点的定 位结果是在大楼的3 0 5 号房间就是符号定位。般来说，只要知道定位区域的 结构，物理定位很容易转换为符号定位。目前，大多数定位系统和算法都提供 物理定位服务。提供符号定位的系统包括c d c k e t 定位系统和我们开发的定位原 型系统。 9 第2 章节点定位问题的相关工作 2 1 5 粗粒度定位与细粒度定位洲 定位算法也可以根据定位所需信息的粒度进行分类。其中，通过测量未知 节点与锚节点之间距离或角度信息来进行定位的算法称为细粒度定位算法。此 外，信号模式匹配的方法也属于细粒度定位，例如微软开发的r a d a r 定位系 统和哈佛大学开发的m o t e t r a c k 定位系统。基于连通性的节点定位算法则是粗 粒度的定位，例如凸规划算法【2 3 】、质心算法【3 9 】等。 2 2 定位算法的性能评价标准m 1 无线传感网络节点定位算法的性能是决定算法是否可用的关键，因此如何 评价定位算法的性能是一个需要深入研究的问题。文献 4 2 】中给出了以下6 种 定位算法的评价标准： ( 1 ) 定位精度。定位精度是评价定位算法最重要的指标，一般用定位误差 的平均值或者定位误差值与传感节点无线信号射程的比例表示。 ( 2 ) 网络规模。不同的定位算法应用场景不同，传感网络的规模也不同。 例如，m o t e t r a c k 定位系统仅在建筑物的一层内实现定位，而s p o t l i g h t 定位系统可以在一个体育场进行定位。 ( 3 ) 锚节点比例。锚节点的位置通常依赖人工部署或配置g p s 获得的。锚 节点数量在网络中所占的比例将直接影响网络部署的成本。 ( 4 ) 网络节点密度。网络节点密度通常以网络的平均连通度来表示。如果 节点密度不同，很多定位算法的精度也会有比较大的差异。 ( 5 ) 健壮性。在研究过程中，研究者通常假设定位系统和算法运行在比较 理想的无线通信环境和稳定可靠的传感节点上。但在真实应用的场景 中，很多假设无法完全满足。因此，定位算法的必须具有很强的容错 能力，以保证算法能够正常运行，并获得理想的定位效果。 ( 6 ) 能量消耗。传感器节点一般靠电池供电，并没有持续的能量供给，因 此节能是无线传感网络中必须考虑的问题。同样，节点定位算法也应 该尽可能的降低计算量、通信开销、运行时间等与能量相关的指标。 上面介绍的6 个性能标准是相互关联的。一般来说，定位算法很难在所有 标准上都令人满意，而是必须根据实际应用的需求进行权衡。 2 3 常用的定位算法介绍 l o 第2 章节点定位问题的相关工作 根据本文的研究需要，本节主要介绍常用的基于连通性的节点定位算法。 2 i3 1 质心算法口帕 质心算法是由美国南加州大学提出的，它是最简单的基于连通性的定位算 法。算法中，未知节点通过收集锚节点发送来的信息，判断自己能够与哪些锚 节点进行通信。然后，计算所有锚节点位置的质心作为自己的定位位置。算法 实现起来非常简单，如果锚节点的摆放位置恰当，算法的定位误差能够达到很 小。但如果是随机部署，算法的定位效果并不理想。质心算法的具体实现和分 析，本文将在第3 章进行详细的介绍和讨论。 2 3 2m d s m a p 定位算法池 7 1 m d s 是一种心理测量学和精神物理学的数据分析技术，密苏里大学基于这 种技术提出了一种集中式的定位算法m d s m a p 。m d s m a p 定位算法在全局 的网络拓扑连通图，利用节点之间的连通信息生成网络的节点间距离矩阵。然 后，对节点间距矩阵应用m d s 技术，生成整个网络相对坐标系。如果有足够 多的锚节点，算法可以将相对坐标系转化为绝对坐标系。m d s m a p 算法在对 节点进行定位时，需要利用所有节点之间的连通性信息，这种固有的集中计算 性质使它在许多应用上收到限制。因此，算法的作者又提出一个改进的方案 m d s m a p (