（检测技术与自动化装置专业论文）无线传感器网络基于聚类的分布式定位算法.pdf

中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 无线传感器网络基于聚类的 分布式定位算法 硕士：孙晴 专业：检测技术与自动化装置 指导老师：王国利教授 摘要 无线传感器网络是近年来最有发展前景的技术之一。许多传感器网络的应用 都要求感知数据流附上所在节点对应的物理位置。考虑到费用、功率、体积大小 等因素的限制，使用全球定位系统( g p s ) 对自组织传感器网络进行节点定位变 得不现实，在这种情况下，寻找一种无需配置g p s 的定位算法十分重要。 本文提出了一种新的分布式定位算法，基于聚类的无需锚点的定位算法，简 称为c a f l 。该算法的基本思想是，将整个传感器网络划分为多个簇，每个簇的 内部节点并发地计算和修正自身位置，建立簇的局部坐标系统。在此基础上，调 整局部坐标架的方向，使得整个网络收敛至一个全局坐标系统。该算法借助聚类 的手段有效解决了无锚点定位算法在网络规模可扩展方面存在的局限性。 最后，本文针对不同的节点密度、测距误差、网络面积参数进行了仿真对比 研究。实验结果表明，c a f l 算法是一个稳健的定位算法，具有很强的扩展性， 适用于大规模的传感器网络。 关键字：无线传感器网络，定位，无需锚点，簇 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 c l u s t e r i n g - b a s e dd i s t r i b u t e dl o c a l i z a t i o na l g o r i t h m i nw i r e l e s ss e n s o rn e t w o r k s n a m e ：s u n q i n g m a j o r ：m e a s u r e m e n tt e c h n o l o g ya n da u t o m a t e de q u i p m e n t s u p e r v i s o r ：p r o f w a n gg u o l i w i r e l e s ss e n s o rn e t w o r k so v s ni s b e c o m i n go n eo ft h em o s tp r o m i s i n g t e c h n o l o g i e si nr e c e n ty e a r s m a n yw s na p p l i c a t i o n sr e q u i r et h a ts e n s o rs t r e a m s s h o u l db ea n n o t a t e dw i t ht h ep h y s i c a ll o c a t i o n so ft h ec o r r e s p o n d i n g n o d e s p o s i t i o n i n g w i t h o u tt h ea i do fg l o b a lp o s i t i o n i n gs y s t e m ( g p s ) i sc r u c i a lw h e ng p sb e c o m e s i m p r a c t i c a ld u e t ot h el i m i t a t i o n so fc o s t ，p o w e r , f o r mf a c t o re t c t h i st h e s i sp r o p o s e san e wd i s t r i b u t e dl o c a l i z a t i o na l g o r i t h m ，c l u s t e r i n g b a s e d a n c h o r - f r e el o c a l i z a t i o n , b r e v i t y , c a f l t h eb a s i ci d e ao fc a f li st od i v i d et h e w h o l es e n s o rn e t w o r ki n t oan u m b e ro fc l u s t e r s ，i nw h i c ht h en o d e sc a l c u l a t ea n dr e f i n e t h e i rr e l a t i v ec o o r d i n a t e si np a r a l ms o a st os e tu pt h el o c a lc o o r d i n a t ef r a m e s f u r t h e r m o r e ，a l ll o c a lc o o r d i n a t ef r a m e sa r er e o r i e n t e ds ot h a tt h ew h o l en e t w o r k c o n v e r g e st oas i n g l eg l o b a lc o o r d i n a t es y s t e m t h ep r o p o s e da l g o r i t h me m p l o y st h e c l u s t e r i n gt e c h n o l o g yt or e m o v et h el i m i t a t i o no ft h ea f la l g o r i t h mi ns c a l a b i l i t yo ft h e w s n ss i z e f i n a l l y , c o m p a r a t i v es i m u l a t i o ns t u d i e sa r ec o n d u c t e di nt e r m so fav a r i e t yo fn o d e d e n s i t i e s ，r a n g ee r r o r s ，n e t w o r ks i z e s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tc a f li sa r o b u s tl o c a l i z a t i o na l g o r i t h ma n di ss i g n i f i c a n t l ys c a l a b l e ，e s p e c i a l l yf o rt h el a r g es i z e l i e t w o r k s k e y w 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 ，a n c h o r - f r e e ，c l u s t e r 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 第1 章概述 无线传感器网络是在微电机系统、无线通信和数字电子技术的推动下迅速发 展起来的。它由部署在监测区域内大量廉价、低功耗、多功能的微型传感器节点 组成，通过无线通信方式形成一个多跳的自组织的网络系统。目的是协作地感知、 采集和处理网络覆盖区域中感知对象的信息，并将信息发送给观察者，由观察者 根据获取的信息采取下一步的行动。这些体积微小的传感器节点集成了信息采集、 数据处理和无线通信等多种功能【1 1 。 在美国技术评论杂志上列出的影响世界的十大新兴技术里，无线传感器 网络名列榜首，它将影响到计算、医疗、制造、运输和能源基础设施等各个领域 【2 】。 1 1 无线传感器网络的特点 无线传感器网络是数据和无线网络的结合，与以往传统的计算机网络相比， 它更以通信为中心。其主要特点【3 l 是： ( 1 ) 基于应用的网络 无线传感器网络将传感技术、计算处理技术及通信技术相结合，应用领域广 泛。与传统网络“以一适全”的模式不同的是，针对不同应用，无线传感器网络 需要调整自身的配置，如使用不同的数据融合、节点密度、定位技术、自适应协 议等，即具体应用具体配置。 ( 2 ) 与物理世界交互 无线传感器网络与物理世界紧密耦合，物理现象取代人成为网络的中心。在 无人值守的情况下，网络应该能主动感知外界的环境状况，对外界环境变化做出 实时反应，并具有根据物理环境的改变决定自身系统状态的能力。即采取情景自 觉计算，监测对象为中心，实时动态地根据周围的情景执行相应的动作。在各种 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 情景中，监测对象的位置和运动轨迹是最重要的信息之一，如何方便、准确、动 态地获取位置信息已受到研究者的高度关注。 ( 3 ) 网络自组织、自维护 传感器节点可以通过随机撒播自组成网，形成大面积的监控网络，并以a d h o c 方式进行自我配置。在任一时刻，每个传感器节点中运行的特殊算法都能计算出 该节点和中心节点问的跳数，且能判断出哪一个相邻节点能在任何特定时间提供 到中心节点的最经济路由。一旦环境发生变化，如监测对象改变、节点失效或者 节点移位，网络拓扑能随时问动态地改变，也就是说，网络应该具备维护动态路 由的能力。 ( 4 ) 节点能量、处理能力和存储空间有限 节点依靠电量有限且不可更换的电池来提供工作所需的能量。对于在大多恶 劣环境中的网络应用，更换电池是不现实的，因此需要最大可能地节省电能开销。 节点数量比传统的a dh o c 网络高出许多个数量级，单个节点的成本价格低， 节点的计算能力和存储空间非常有限，而且节点上一般不配置昂贵的基础设施， 如全球定位系统( g p s ) 。 ( 5 ) 以数据为中心 在无线传感器网络中，能源消耗最大的过程是通信过程。在能量受限的情况 下，无线传感器网络的路由应符合既保证数据传输又减少通信量的要求。节点数 量大、密度高，建立全局地址不现实，需要研究有效的分布式数据流的管理、查 询方法。 ( 6 ) 网络的协作性 单个节点计算能力有限，需要大量节点进行数据交换以及协同的信号和信息 处理。如何使用大量节点进行分布式信息处理是面临的挑战之一。 1 2 无线传感器网络的体系结构 无线传感器网络自身的特点决定了它有别于传统网络的体系结构 4 1 ： ( 1 ) 节点功能结构 2 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 在不同应用中，传感器网络节点的组成不尽相同，但一般都由数据采集、数 据处理、数据传输和电源这四部分组成。根据具体的应用需求，可能会有定位系 统以确定传感器节点的位置，有移动单元使得传感器可以在待监测区域中移动， 有供电装置以从环境中获得必要的能源等。此外，还有一些与应用相关的部分。 例如，某些传感器节点有可能出现在化学或生物污染的地方，这就需要在传感器 节点的设计上采用一些特殊的防护措施。 ( 2 ) 网络拓扑结构 网络中的各个节点具有数据收集和将数据路由到接收器的功能。接收器可以 通过有线网络或卫星与任务管理节点通信。 ( 3 ) 通信体系结构 传感器网络需要根据用户对网络的需求设计适应自身特点的网络体系结构， 为网络协议和算法的标准化提供统一的技术规范，使其能够满足用户的需求。 传感器网络体系结构具有二维结构，即横向的通信协议层和纵向的传感器网 络管理面。通信协议层可以划分为物理层、链路层、网络层、传输层、应用层； 而网络管理面可以划分为能耗管理面、移动性管理面及任务管理面。管理面的存 在主要是用于协调不同层次的功能以求在能耗管理、移动性管理和任务管理方面 获得综合考虑的最优设计。 1 3 无线传感器网络的应用畸1 1 3 1 军事领域的应用 早在3 0 多年前，从研究a dh o c 网络开始，美国军方就已经一直在关注无线 自组织网络在军事上的应用，并持续到今天，所以无线传感器网络同样倍受军方 关注，并已成立多个项目将传感器网络技术充分地运用到军事领域。它的密集型、 低成本、随机分布以及它的自组织性、抗毁性和强大容错能力是为军方首要利用 的。可以实现的功能有： 敌我军情监控：在友军的人员、装备及军火上加装传感器节点以供识别，随 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 时掌控自己的情况。通过在敌方阵地部署各种传感器，在确定敌方武器部署后第 一时间内做出决策，做到知己知彼。 战场状况监控：在战场上、自己的阵地周围以及敌人可能的行军路线上布设 大量的传感器，既可以了解目前的战地情况，目标破坏程度，战场技术数据统计 以及敌人的最新动向，及时调整自身兵力部署。 此外，无线传感器网络还可以作为智慧型军火的引导器，以及代替专业人员 收集到战场上核、生物化学攻击现场的详细数据。它与独立的卫星和地面雷达相 比较有以下几个方面的潜在优势：独立卫星和地面雷达难以提高的信噪比由于分 布节点中多角度和多方位信息的综合得以有效的提高；由于节点的近距离探测， 可以有效地减少环境噪声对系统的影响；在卫星和雷达系统中有时候因为地域性 问题造成部分阴影或盲点，但在传感器网络中各节点的位置是可以任意移动的， 这样可以根据不同位置的调整而扫除这些阴影和盲点。如果传统的雷达或卫星系 统配合无线传感器网络技术共同应用到侦测中，其效果及可靠性都会大幅提升。 美国陆军在2 0 0 1 年提出了“灵巧传感器网络通信”计划，己被批准为2 0 0 1 财政年度的一项科学技术研究计划，并在2 0 0 1 - - 2 0 0 5 财政年度期问实施。近期 又确立了“无人值守地面传感器群”项目，其主要目标是使基层部队指挥员具有 在他们所希望部署传感器的任何地方灵活地部署传感器的能力。最近又确立了“战 场环境侦察与监视系统”，该系统是一个智能化传感器网络，可以更为详尽、准确 地探测到精确信息。它通过“数字化路标”作为传输工具，为各个作战平台与单 位提供“各取所需”的情报服务，使情报侦察与获取能力产生质的飞跃。 1 3 2 生态环境监测 随着科学技术的飞速发展，生态环境逐渐被越来越多的人所关注，从研究到 保护都需要掌握大面积地域中的各种数据，甚至有些勘测区域是人类无法触及到 的，而传感器网络的特性正好适应了这样一种需求。 我们可以根据需要在待监测区域安放不同功能的传感器来组成无线传感器网 络，可以长时期大面积地监测微小的气候变化，包括温度、湿度、风力；跟踪野 生动物的栖息、觅食习惯等；在某河流沿线分布区域布设传感器节点，随时监测 4 中山大学硕士学位论文无线传感器厢络基于聚类的分布式定位算法 水位、相关水纹及被污染的信息；在山区中泥石流、滑坡等自然灾害容易发生的 地方布设传感器节点，这样可提前发出预警报告以做好准备或采取相应措施防止 灾害进一步的发生；还可以在重点保护林区铺设大量节点随时监控内部火险隋况， 一旦有可能酿成火灾，立刻发出警报并给出具体方位及当前火势大小。 2 0 0 2 - - 2 0 0 3 年，由英特尔的研究小组和加洲大学伯克利分校及巴港大西洋大 学共同完成了用传感器网络实现对大鸭岛的生态环境监测的项目。夏威夷大学在 夏威夷火山国家公园内铺设传感器网络以监测那些濒临灭种的植物所在地微小的 气候变化。美国俄勒冈洲研究生院在哥伦比亚河设置了1 3 个站节点来监测每个站 所在区域的流速、盐度、温度及水位。 1 3 3 交通管理 1 9 9 5 年，美国交通部提出了“国家智能交通系统项目”规划，预计到2 0 2 5 年 全面投入使用。这种新型系统将有效地使用无线传感器网络技术进行交通管理， 不仅可以使汽车按照一定的速度行驶、前后车距自动地保持一定的距离，还可以 提供有关道路堵塞的最新消息，推荐最佳行车路线以及提醒驾驶员避免交通事故 等。由于该系统将应用大量的传感器与各种车辆保持联系，人们可以利用计算机 来监视每一辆汽车的运行状况，如制动质量、发动机调速时间等。根据具体情况， 计算机可以自动进行调整，使车辆保持在高效低耗的最佳运行状态，并就潜在的 故障发出警告，或直接与事故抢救中心取得联系。目前在美国的宾西法尼亚洲的 匹兹堡市就已经建成有这样的交通信息系统，并且通过电台等媒体附带产生了一 定商业价值。 1 3 4 其他应用领域 除以上应用外，在医疗、智自旨家居、工业生产等领域也可以广泛地应用无线 传感器网络技术。例如，在住院病人身上安装具有特殊用途的传感器节点，如心 率和血压监测设备，利用无线传感器网络，医生可以随时了解被监护病人的病情， 进行及时处理。还可以利用传感器网络长时间地收集人的生理数据，有助于医疗 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 工作者研制新药品。此外，在药物管理等诸多方面，将节点按药品类别安放，与 计算机系统连接后可以辨认所开药品，避免开错药或拿错药。 美国英特尔公司曰前透露，该公司开发了一套用于家庭护理的无线传感器网 络系统。据了解，该系统是为应对老龄化社会技术项目的一个环节而开发的。根 据演示，试制系统通过在鞋、家具和家用电器中嵌入半导体传感器，帮助老年人、 阿尔茨海默氏病患者以及残障人士的家庭生活。该系统利用无线通信将各传感器 联网，可高效传递必要的信息，从而方便病人接受护理，减轻护理人员的负担。 此外，现在许多工厂里从生产流水线到一台复杂的机器设备，都安装了传感 器节点以便时刻掌握机械设备的工作状况，及早发现问题及早处理，从而有效地 降低事故发生率。 1 4 无线传感器网络定位的意义和挑战 无线传感器网络的定位问题分为两类【6 】：一类是无线传感器网络对自身传感 器节点的定位：另一类是无线传感器网络对外部目标的定位。本文主要讨论前者。 传感器节点准确地自身定位是无线传感器网络应用的重要条件。由于节点的 工作区域或者是人类不适合进入的区域，或者是敌对区域，传感器节点有时候甚 至需要通过飞行器抛撒于工作区域，因此节点的位置是随机并且未知的。然而在 许多应用中，节点所采集到的数据必须结合其在测量坐标系内的位置信息才有意 义。换言之，如果不知道数据所对应的地理位置，数据就失去了意义。如战场侦 察、生态环境监测、地震洪水火灾等现场的监控等应用都需要知道传感器节点的 位置信息，才能获知信息来源的准确位置或相对位置。除此以外，节点的位置信 息还可以辅助实现地理路由。 如前所述，由于节点受到成本、能量和体积的限制，所以无线传感器网络的 定位技术也遇到了新的挑战。采用g p s 是获得位置信息的一种方法，但是由于传 感器节点的数量非常巨大，达到数千甚至数万，若每个节点都配置g p s 系统，那 样产生的高成本会无法被接受。另外，传感器节点是采用电池供电，其电能不仅 十分有限且不能补充或更换，因此不适宜每个节点都装各如此高能耗的设备。目 6 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 前主要的研究工作是利用传感器网络中少量已知位置的节点( 它们的位置可以通 过g p s 或人工部署事先获取，称为锚点) 来获得其他未知节点的位置信息。 节点之间的无线通信所消耗的电能比其它部件所消耗的电能要大得多，所以 应尽量减少节点之间的无线通信量。同时，也不宜将大量的通信和计算固定于某 个或者某些节点，否则，这些节点的电能会很快耗尽，出现网络的“空穴”。这些 特点决定了要尽量使用分布式定位算法来代替集中式定位算法，目的是尽量延长 传感器网络的生命周期。通过少量锚点的分布式定位算法已经成为无线传感器网 络定位算法研究的热点。 本文在前人提出的无需锚点的定位算法( a n c h o r - f r e el o c a l i z a t i o n ，a f l ) 基 础上，提出了一种新的基于聚类的f l 算法，称为c a f l ( c l u s t e r i n g b a s e d a f l ) 。 把无线传感器网络分成多个簇( c l u s t e r ) 分别进行定位，这种方法改进了a f l 算 法的可扩展性，适用于大规模的传感器网络。本文的组织结构如下：第二章介绍 无线传感器网络定位的背景知识；第三章则对本文的算法进行详细的阐述；第四 章将展示该算法的实验仿真结果；最后一章对算法进行总结，并提出对将来研究 工作的展望。 7 中山大学硕士学位论文无线传感器网络基于聚娄的分布式定位算法 第2 章无线传感器网络的定位问题 2 1 无线传感器网络定位的背景知识 2 1 1 测距方法 定位算法通常需要预先拥有节点与邻居节点之间的距离或角度信息，因此测 距是算法执行的基础和前提。常用的测距方法及其优缺点【6 】分析如下： ( 1 ) 接收信号强度指示法( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ，r s s d 已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验 的信号传播模型将传播损耗转化为距离。例如，在自由空间中，距发射机d 处的 天线接收到的信号强度是： 删= 篙簧 ( 2 - ) 其中，只为发射机功率；c 是在距离发射机d 处的接收机功率；q 、g ，分别是发 射天线和接收天线的增益；d 是距离；l 是与传播无关的系统损耗因子：a 是波长。 由公式可知，在自由空间里，接收机功率随发射机与接收机距离的平方衰减。通 过测量接收信号的强度，再利用式( 2 1 ) 就能计算出收发节点间的大概距离。 然而，公式( 2 1 ) 只是电磁波在理想的自由空间中传播的数学模型，实际应 用中的情况要复杂得多，尤其是在分布密集的无线传感器网络中，反射、多径传 播、非视距( n o n l i n e o f - s i g h t ，n l o s ) 、天线增益等问题都会对相同距离产生显 著不同的传播损耗。因此这种方法的主要误差来源是环境影响所造成的信号传播 模型的复杂性。信号强度测距法通常属于一种粗糙的测距技术，但是由于其不需 要节点配置昂贵或特殊的装置，因此在无线传感器网络中普遍使用。 ( 2 ) 到达时间或时间差测距法( t i m eo f a r r i v a l ，t o a 或t i m ed i f f e r e n c eo f 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 a r r i v a l ，t d o a ) t o a 技术通过测量信号传播时间来测量距离。在t o a 方法中，若电波从锚 点到未知节点的传播时间为t ，电波传播速度为c ，则锚点到未知节点的距离为t c 。t o a 要求接收信号节点知道信号开始传输的时间，也就是对时间同步技术 的要求很高，也就是要求节点有着非常精确的时钟。 使用t o a 技术比较典型的定位系统是g p s 。g p s 系统需要昂贵高能耗的电 子设备来精确同步卫星时钟。在无线传感器网络中，节点间的距离较小，采用t o a 测距的难度较大，同时节点硬件尺寸、价格、功耗等限制也决定了t o a 技术对无 线传感器网络是不太可行的。 t d o a 测距技术通过记录两种不同信号( 常使用无线电信号和超声波信号) 的到达时间差异，根据已知的两种信号的传播速度，直接把时间差转化为距离。 该技术受到超声波传播距离的限制和非视距问题对超声波信号传播的影响，不仅 需要精确的时钟记录两种信号的到达时间差异，还需要传感器节点同时具备感知 两种不同信号的能力。 ( 3 ) 到达角度测距法( a n g l eo f a r r i v a l ，a o a ) a o a 法通过配备特殊的天线阵列来估测未知节点发射的无线信号的到达角 度。同样，它的硬件要求较高，每个节点需安装昂贵的天线阵列和超声接收器， 因此也不太适用于无线传感器网络。 2 1 2 三边或三角测量法原理 在后叙提到的无线传感器网络自身定位算法中，有不少经典算法最后都要依 靠三边测量法或三角测量法对未知节点进行定位。如图2 1 所示，m 是未知节点， 若它距离锚点a 1 、a 2 和a 3 的距离已知，那么m 的位置唯一。 然而在现实生活中，未知节点到各个参考节点的距离是通过测距系统获得的， 带有误差，因此不可能得到唯一解。大多会通过对多个锚点获取到的测距信息采 用最小均方算法来获取未知节点的位置估计值。原理如下m ： 9 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 图2 1 三角测量法定位示意 给定一组参考节点( 五，x ，z 1 ) 和一组测量距离足，建立下面的方程组： “一叱) 2 + ( ) ，一) 2 + 编一叱) 2 o 吐一q ) 2 + ( ) ，：一h ，) 2 + ( 乞一“：) 2 ： 也一m ，) 2 + ( ) ，。一q ) 2 + 瓴一叱) 2 ( 2 2 ) 其中， ，咒，五) 是第i 个锚点的坐标，而0 ，“，“；) 是未知节点的坐标，是未知 节点u 到第i 个锚点的测距。 方程组中的各行减去最后一行，并进行线性变换，可以得到下列关系式： 其中 4 ；6 瓴一) a = - 2 + 降一毛) i ： 魄一n ) ( y 2 一以) ： 眩一乙) ( z ：一乙) ： 阮。一) 帆一。一只) ( 乙一，一乙) 壮吲 1 0 ( 2 - 3 ) ( 2 4 ) ( 2 5 ) 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 6 置 2 - r 2 一鼍2 + 2 一h 2 + y 一2 一彳+ 乙2 厂2 2 一2 一屯2 + 瓦2 一y 2 2 + n 2 一z 2 2 + 2 i g n _ 1 2 一2 一1 2 + 2 一y 一- 1 2 + 靠2 一毛- 1 2 + 气2 采用最小二乘法，就可获得未知节点的坐标u ： “= 口) 4 + 爿b 其中a 为a 的转置矩阵。 2 2 无线传感器网络自身定位算法的性能标准 ( 2 6 ) ( 2 7 ) 无线传感器网络自身定位算法的性能直接影响其可用性。没有最好与最坏的 定位算法，只有最合适与最不合适的定位算法。如何评价它们，如何根据需求寻 找最合适的算法是值得我们深入研究的问题。下面定性地讨论几个常用的评价标 准【8 】： ( 1 ) 定位精度 定位技术首要的评价指标就是定位精度，一般用定位误差值与节点无线射程 的比例来表示。例如，定位精度为2 0 ，表示定位误差的大小相当于节点无线射 程的2 0 。 ( 2 ) 定位规模 不同的定位算法定位规模都不同，可在园区内、建筑物内、一层建筑物或仅 仅是一个房间内实现定位。另外，给定一定数量的基础设施，或给定一段时间， 一种技术可以定位多少目标也是一个重要的评价指标。例如，r a d a r 系统只能 够在建筑物的一层内实现目标定位；剑桥的a c t i v eo f f i c e 定位系统每2 0 0 m s 定位 一个节点。 ( 3 ) 锚点密度 如前所述，锚点就是事先已经知道自身绝对位置的传感器节点，它的定位通 常由人工部署或者g p s 实现。人工部署锚点的方式受网络部署环境的限制，无线 传感器网络分布的区域大多都是一些恶劣甚至极度危险的环境，人类无法到达甚 1 1 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 至靠近，更不用说通过人工来部署锚点，除此之外，这种方式还严重制约了网络 和应用的可扩展性。而使用g p s 定位，锚点的费用会比普通节点高两个数量级， 这意味着即使仅有1 0 的节点是锚点，整个网络的价格也将增加1 0 倍。因此，锚 点密度也是评价定位系统和算法性能的重要指标之一，通过极少量的锚点进行定 位，是该领域研究的主要目标。 ( 4 ) 节点密度 在无线传感器网络中，节点密度增大不仅意味着网络部署费用的增加，而且 会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平均 连通度来表示。许多定位算法的精度受节点密度的影响，如d v - h o p 9 】算法仅在节 点密集部署的情况下才能合理地估算节点位置。 ( 5 ) 容错性和自适应性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设 备，但在真实应用场合中常会有诸如以下的问题：外界环境中存在严重的多径传 播、衰减、非视距、通信盲点等问题；网络节点由于周围环境或自身原因( 如电 池耗尽、物理损伤) 而出现失效的问题；外界影响和节点硬件精度限制造成节点 间点到点的距离或角度测量误差增大的问题等等。由于环境、能耗和其他原因， 物理地维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难或不 现实的。因此，定位算法的软、硬件必须具有很强的容错性( 或称健壮性) 和自 适应性，能够通过自动调整或重构纠正错误以提高定位精度。 ( 6 ) 功耗 功耗是对无线传感器网络的设计和实现影响最大的因素之一。由于传感器节 点电池能量有限，而由人工为节点进行电池替换不现实，因此在保证定位精度的 前提下，与功耗密切相关的定位所需要的计算量、通信开销、存储开销、时间复 杂性是一组关键性的指标，一般来说，算法的功耗越小越好。 ( 7 ) 代价 定位算法的代价可从几个不同方面来评价。时间代价包括一个系统的安装时 间、配置时间、定位所需的时间。空间代价包括一个定位算法所需的基础设施和 网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位算法的基础设施、 节点设备的总费用。 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 上述7 个性能指标不仅是无线传感器网络自身定位系统和算法的评价标准， 也是其设计和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需 要完成。同时，这些性能指标都是相互关联的，必须根据应用的具体需求做出权 衡，以选择和设计合适的定位技术。 2 3 无线传感器网络自身定位算法的分类 无线传感器网络自身定位算法的分类有以下几种【8 1 ： ( 1 ) 物理定位与符号定位( p h y s i c a la n ds y m b o l i c ) 定位系统可提供两种类型的定位结果：物理位置和符号位置。例如，某个节 点位于4 7 。3 9 1 7 n ，1 2 2 。1 8 2 3 ，这个就是物理位置；而某个节点在建筑物的1 2 3 号房间，这是符号位置。在一定条件下，物理定位和符号定位可以相互转换。与 物理定位相比，符号定位更适于某些特定的应用场合，例如，在安装有无线烟火 传感器网络的智能建筑物中，管理者更关心某个房间或区域是否有火警信号，而 不是火警发生地的经纬度。 ( 2 ) 绝对定位与相对定位( a b s o l u t ev sr e l a t i v e ) 自 绝对定位与物理定位类似，定位结果是一个标准的坐标位置，如经纬度。而 相对定位通常是以网络中部分节点为参考点，建立整个网络的相对坐标系统。 绝对定位可为网络提供唯一的命名空间，受节点移动性影响较小，但它需要 利用锚点来帮助其他节点获取绝对坐标。然而相对定位的应用范围同样非常广泛， 因为当某个事件发生时，只要知道它相对于某个建筑物的位置，就可以立即采取 下一步行动。相对定位还能够实现部分路由协议，尤其是基于地理位置的路由 ( g e o - r o u t i n g ) ，而且相对定位不需要锚点。 大多数定位系统和算法都可以实现绝对定位服务，典型的相对定位算法有 s p a t l o l ，l p s 1 1 】等。而m d s m a p l l 2 1 定位算法可以根据网络配置的不同分别实现 两种定位。 ( 3 ) 紧密耦合与松散耦合( t i 曲t l yc o u p l e dv sl o o s e l yc o u p l e d ) 所谓紧密耦合定位是指锚点不仅被仔细地部署在固定的位置，并且通过有线 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 介质连接到中心控制器；而松散型定位系统的节点采用无中心控制器的分布式无 线协调方式。 典型的紧密耦合定位系统包括a t & t 的a c t i v eb a t 和a c t i v eb a d g e 等。它们 的特点是适用于室内环境，具有较高的精确性和实时性，时间同步和锚点间的协 调问题容易解决。但这种部署策略限制了系统的可扩展性，代价较大，无法应用 于布线工作不可行的室外环境。 近年来提出的许多定位系统和算法，如c r i c k e t 1 3 1 ，a h i o s 1 4 1 等都属于松散耦 合型解决方案。它们以牺牲紧密耦合系统的精确性为代价而获得了部署的灵活性， 依赖节点间的相互协调和信息交换实现定位。在松散耦合系统中，因为网络以a d h o c 方式部署，节点间没有直接的协调，所以节点会竞争信道并相互干扰。 这种分类方法与基于基础设施和无需基础设施的分类方法相似，所不同的是， 后者是以整个系统除了传感器节点以外是否还需要其他设旖为标准。 ( 4 ) 集中式计算与分布式计算( c e n t r a l i z e dv sd i s t r i b u t e d ) 集中式计算是指把所需信息传送到某个中心节点，并在那里进行节点定位计 算的方式；分布式计算是指依赖节点问的协调和信息交换，由节点自行计算自身 位置的定位方式。 集中式计算的优点在于从全局角度统筹规划，计算量和存储量几乎没有限制， 可以获得相对精确的位置估算。缺点包括与中心节点位置较近的节点会因为通信 开销大而过早地消耗完电能，导致整个网络与中心节点信息交流的中断。对于分 布式计算来说，由于传感器节点的计算和存储能力有限，因此要求分布式定位算 法的通信量、计算量、存储量都要尽量小，而优点在于减轻了中心节点及附近节 点的负荷，降低了整个网络与中心节点信息交流中断的可能性，同时由于所有节 点相互协作定位，也使得整体的定位时间得到缩短。 集中式定位算法包括凸规划【1 5 】，m d s m a p 等。分布式定位算法包括a h l o s ， a f l 1 6 1 ，a p s l 9 i ，a p i t t l 7 】等。n 。h o pm u l t i l a t e r a t i o np r i m i t i v e 1 8 】定位算法可以根据应 用需求采用两种不同的计算模式。 ( 5 ) 递增式定位与并发式定位( i n c r e m e n t a lv sc o n c u r r e n t ) 递增式算法从三个或四个已知坐标的中心节点开始，寻找合适的新节点，通 过测量距离并实施三边测量法来求解新节点的位置，再将这些节点加入中心节点 1 4 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 组，层层“扩散”，逐步得到整个网络所有节点的坐标。缺点是测距误差被逐步放 大，距离中心节点越远的节点定位误差越大。有些递增式算法设置了一个优化过 程来减缓这种误差的积累，但是这个优化过程可能会产生局部最优解。并发式算 法实际上就是分布式算法，这里不再重复。 递增式定位算法包括a b c l l 9 1 ，t e r r a i n l 7 等。 ( 6 )基于测距技术的定位和无需测距技术的定位( r a n g e - b a s e dv s r a n g e f r e e ) 基于测距的定位通过测量节点之间点到点的距离或角度信息，使用三边测量、 三角测量或最大似然估计法来计算节点的位置。而无需测距的定位则无需距离和 角度信息，仅根据节点之间的连通性即可实现。 前面已经提过，基于测距的定位常用的测距技术有r s s i 、t o a 、t d o a 和 a o a 。它们各自有优缺点：r s s i 虽然符合低功率、低成本的要求，但有可能产生 5 0 的测距误差；t o a 需要节点间精确的时间同步，无法用于松散耦合型定位： t d o a 受限于超声波传播距离有限和n l o s 问题对超声波信号传播的影响；a o a 也需要额外硬件，在硬件尺寸和功耗上可能无法用于无线传感器节点。除上述测距 技术的局限性以外，基于测距的定位机制通常需要使用各种优化方法来减小测距 误差对定位的影响，包括多次测量、循环定位求精等，而这些都会产生大量计算 和通信开销。所以，基于测距的定位机制虽然在定位精度上有可取之处，但并不 适用于低功耗、低成本的应用领域。 因功耗和成本因素的限制以及粗精度定位对大多数应用来说已经足够，因此 无需测距的定位方案越来越受欢迎。d v - h o p 、h o p - t e r r a n 7 1 、凸规划等就是典 型的无需测距的定位算法，其中m d s m a p 还可以在基于测距的条件下实现更精 确的定位。 ( 7 ) 粗粒度定位与细粒度定位( f m e 一孕a m e dv sc o a r s e 一铲a m e d ) 依据定位所需信息的粒度可将定位算法分为两类：根据测距系统来度量节点 间距离的称为细粒度定位技术；根据接近度( p r o x i m i t y ) 或称连通度来度量的称 为粗粒度定位技术。 ( 8 ) 静止节点定位与移动节点定位( s t a t i c v sm o b i l e ) 【2 0 】 多数定位方案属静止节点定位算法，即传感器处于静止状态。虽然在移动机 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 器人领域已有许多关于移动定位的成熟方案，但机器人器件的内存大，且c p u 可 进行计算量很大的运算，这些方案不能直接移植到无线传感器网络的定位系统。 现已有少量算法用于求解移动传感器的定位。在b e r g a m o 等的研究中，网络有两 个固定锚点不断向网络广播坐标信息，其余处于运动状态的节点则根据接受的信 号强度进行自身定位。移动节点的定位算法尚待进一步研究。 2 4 典型的自身定位算法 2 4 1 质心法口” 质心法是南加州大学n i r u p a m ab u l u s u 等提出的一种仅基于网络连通性的室 外定位法。该算法的中心思想是：未知节点以所有在其通信范围内的锚点构成的 多边形的几何质心作为自己的估计位置。具体过程是：锚点每隔一段时间就向邻 居节点广播一个信标信号( b e a c o n ) ，信号中包括了锚点自身的i d 和位置信息。 当未知节点在一段侦听时间内接收到来自锚点的信标信号数量超过某一个预设的 门限值后，该节点就认为与此锚点连通，并将自身位置确定为所有与之连通的锚 点组成的多边形的质心。 质心法最大的优点是简单，计算量小，完全基于网络的连通性，但需要较多 的锚点。 2 4 2 自组织定位算法( a dh o cp o s i t i o n i n gs y s t e m ，a p s ) 阴 美国路特葛斯大学( r u t g e r su n i v e r s i t y ) 的d r a g o sn i c u l e s c u 等利用距离矢量路 i 拍( d i s t a n c ev e c t o rr o u t i n g ) 和g p s 定位原理提出了一系列分布式定位算法，合称为 a p s 。它包括4 种定位算法：d v - h o p ，d v - d i s t a n c e ，e u c l i d e a n ，d v - c o o r d i n a t e 。 i d v - h o p 定位算法 d v - h o p 算法是4 种算法中最基本的算法，由三个环节组成。第一步，通过采 1 6 中山大学硕士学位论文 无线传感器网络基于聚类的分布式定位算法 用经典的距离矢量交换协议使得网络中的所有节点都获得距离锚点的跳数。每个 节点都将所有锚点的坐标以及距离它们的跳数记录下来，并把该信息与邻居节点 交换以更新信息。第二步，对于任意一个锚点来说，当它积累足够多的信息以后， 就可获得距离其他锚点的跳数，此时，该锚点可以利用它们之间的欧几里得距离 之和除以它们间的跳数之和来计算该锚点在网络中的平均每跳距离，并将其作为 一个校正值( c o r r e c t i o n ) 广播至网络中。校正值采用可控泛洪法( c o n t r o l l e d f l o o d i n g ) 在网络中传播，意味着一个节点一旦获得并转发了第一个校正值，就丢弃所有后 来者，确保了绝大多数节点可从最近的锚点处接收唯一一个校正值。在大型网络 中，可通过为数据包设置一个t 儿域来减少通信量。当接收到晟近锚点发来的校 正值以后，未知节点就可以利用它距离各锚点的跳数乘以该校正值来计算它到各 锚点的距离。当未知节点求得与三个或更多锚点的距离时，则在第三步执行三边 测量法进行定位。 图2 2d v - h o p 定位算法示意 如图2 2 所示，已知锚点l 1 距离l 2 、l 3 之间的跳数和为( 2 + 6 ) ，欧几 里得距离和为( 4 0 + 1 0 0 ) ，则l 1 的校正值( 即平均每跳距离) 为( 4 0 + 1 0 0 ) ( 2 + 6 ) = 1 7 5 ，同理可知l 2 和l 3 的校正值分别为1 6 4 2 和1 5 9 。由于l 2 距离a 最近，所以a 最先获得1 2 发给它的校正值，因此它与3 个锚点之间的距离分别 为l 1 3 1 6 4 2 ，l 2 2 1 6 4 2 ，1 3 3 1 6 4 2 ，最后使用三边测量法确定节点a 的 位置。 d v - h o p 算法的定位精度约3 3 ( 网络平均连通度为1 0 ，锚点比例为1 0 ， 测距误差小于1 0 ) 。其缺点是仅在各向同性的密集网络中，校正值才能合理地 估算平均每跳距离。 1 7 中山大学硕士学位论文无线传感器网络基于聚类的分布式定位算法 i i d v - d i s t a n c e 定位算法 d v - d i s t a n c e 算法与d v - h o p 类似，区别在于相邻节点之间的距离不用跳数表 示，而用测距表示。d v - d i s t a n c e 算法也仅适用于各向同性的密集网络。该算法精 度提高了，但是如果测距有误差，该算法就会受到影响。实验显示，该算法的定 位精度为2 0 ( 网络平均连通度为9 ，锚点比例为1 0 ，测距误差小于1 0 ) 。 随着测距误差的增大，定位误差也急剧增大。 i i i e u c l i d e a n 定位算法 e u c l i d e a n 算法给出了与锚点相隔两跳的未知节点位置的计算方法。假设未知 节点a 是锚点l 的两跳邻居，b 、c 是a 与l 的“桥梁”。通过节点间交换信息， a 可以获取a c 、a b 、b c 、b l 、c l 的测量距离，对于四边形a b l c 来说，四条 边的长度和其中一条对角线的长度已知，就可以利用三角形原理计算出另一条对 角线a l 的长