（通信与信息系统专业论文）无线传感器网络中的节点定位方法研究.pdf

摘要 无线传感器网络在医疗卫生、环境监测和军事等领域有着广阔的应用前景， 是近年来研究的一个热门课题。在大多数应用中，如大范围的动物跟踪，敌占 区情报侦察，地质环境恶劣地区的环境监测等，节点定位都是一项必不可少的 关键技术。从1 9 9 2 年a t & tl a b o r a t o r i e sc a m b r i d g e 开发出室内定位系统a c t i v e b a d g e 至今，已经有许多定位系统和算法被陆续提出，都是分别针对不同的问 题和应用来解决无线传感器网络的节点自定位问题。 本文的研究工作就是围绕无线传感器网络的节点自定位问题而展开。由于 不同的应用对节点定位有不同要求，因此定位方法的研究应针对特定的应用场 景。本文考虑的应用场景是高密度高连接度的网络，相邻节点间能进行一定精 度的测距，不同的监测任务对节点定位精度有不同要求，定位糖度可由粗到细。 基于该应用场景，我们需要研究以下两个问题：一是研究具有较高的定位精度、 较少的通信量和计算量的定位方法；二是研究在一定通信量和计算量的约束条 件下具有灵活性的定位方法。 针对第一个问题，本文对现有的众多节点自定位方法进行了调研和分析后， 发现具有广泛适应性和鲁棒性的m d s 算法较适合本文提出的应用场景，因此 把它作为研究的起点。在对m d s 算法进行深入分析和研究后，本文确定了在 已知部分测距信息的情况下采取先求初值再进行迭代计算的基本定位模式，接 着对现有的几种初值计算方法进行了详细分析，并对其中一种初值生成算法进 行了改进，提出了a f l 直角坐标初值生成算法。随后，在m d s 算法的基础上， 本文提出了随机扩散的分布式定位算法，并对其进行了详尽的复杂度分析和广 泛的仿真试验。与同类算法相比，随机扩散的分布式定位算法只需更少的计算 量和通信量就能达到较高的定位精度。 针对第二个问题，本文提出了分层定位的思想，研究了一种集中与分布相 结合的定位方法。通过筛选具有吲定连接度的框架节点并分步定位，使得该方 法的计算复杂度与网络连接度无关，更能适用于高连接度的网络。由于采用了 分层定位的策略，该方法能快速获得整个网络框架结构的粗定位结果，并能根 据不同的要求实现部分节点或全部节点的定位，以及不同精度的定位，增加了 定位的灵活性。 最后，本文对分层定位方法的后续研究提出了几个方向。并对随机扩散分 布式定位算法与定向扩散路由协议的结合做了畅想，这些都有待后续的研究工 作进行深入分析。 a b s t r a c t 1 h ew i r e i e s ss e n s o rn e t w o r k sh a sa t t r a e t e dm o r ea n dm o r ea r e n t i o n si nr e c e n t y e a r s f o ral o to fa p p l i c a t i o n sd e p e n do ns e n s o r sl o c a t i o ni n f o r m a t i o n ，s e n s o r p o s i t i o n i n gb e c a m eaf u n d a m e n t a la n dc r u c i a li s s u ef o rw i r e l e s ss e n s o rn e t w o r l 【s s i n c et h ea t & tl a b o r a t o r i e sc a m b r i d g ed e v e l o p e da c t i v eb a d g es y s t e mi n1 9 9 2 ， m a r l yl o c a l i z a t i o ns v s t e m sa n da l g o r i t h m sw e r ep r o p o s e dt os o l v ev a r i a l l ts e n s o r n o d e s l o c a l i z a t i o np r o b l e m s t h i st h e s i sf o c a s e s0 ns e n s o rn o d e ss e l f - l o c a l i z a t i o nr e s e a r c h f i s r t , w e i n t r o d u c ec l a s s i f i c a t i o n 曲o u ts e n s o rn o d e sl o e a l i z a t i o na l g o r i t h m si nc h a p t e r1 a t i e re x t e n s i v ei n v e s t i g a t i o na b o u tp r e s e n tl o c a l i z a f i o na l g o r i t h m s ，w ec h o s e m d s b a s e da l g o r i t h ma so u rm a i ns o l u t i o nt oc o m p u t i n gt h es e n s o rn o d e s p o s i t i o n i nc h a p t e r2 i na d d i t i o n at w o s t a g el o c a l i z a t i o nm e t h o dw h i c hc o m p u t e si n i t i a l v a l u e so fn o d e s p o s i t i o ni nt h ef i r s ts t a g ea n do p t i m i z i n ge a c hn o d e sp o s i t i o nb y i t e r a t i o ni nt h es e c o n ds t a g ei sc h o s e na st h eb a s em o d eo fo t l rm e t h o d i nc h a p e r t3 ， w ea l i a l y s os e v e r a li n i t i a lv a l u eg e n e r a t ea l g o r i t h m s ，a n di m p r o v eo no n eo ft h e m n a m e da f l ( a n c h o r - f t e el o c a l i z a t i o n ) a l g o r i t h m b a s e do nt h ea n a l y s i sa n dr e s e a r c hi np r e v i o u sc h a p t e r ，ar a n d o md i f f u s i o n d i s t r i b u t e dl o c a l i z a t i o n ( r d d l ) a l g o r i t h mi sp r o p o s e di nc h a p t e r4 ，t h er d d l a l g o r i t h mc a nb u i l dg l o b a lm a pb yt h ec o m b i n a t i o no fl o c a lm a p s ，w h i c ha r e c a l c u l a t e db yl o o s ei t e r a t i v em d sa l g o r i t h m t h es i m u l a t i o n ss h o wt h a tt h eg l o b a l m a pc a l l b eo b t a i n e dq u i c k l yb e t hi nr e g u l a r l y - s h a p e da n di r r e g u l a r l y s h a p e d n e t w o r k s c o m p a r e dw i t ht h ee x t a n ta l g o r i t h m s t h er d d lh a sb o t ht h el o w e r c o m p u t i n gc o m p l e x i t ya n dc o m m u n i c a t i o ne o m l e x i t yi nt h ec a s eo ft h es a m e a c c u r a c yo fl o c a t i o ne i t o t i nc h a p t e r5 a n o t h e rm e t h o dc a l l e dh i e r a r c h i c a l l o c a l i z a t i o n ( h l ) m e t h o di sp r o p o s e dt os o l v et h en o d e s l o c a l i z a t i o np r o b l e mi n d e n s ew i r e l e s ss e n s o rn e t w o r k s t h el o c a l i z a t i o no fs e n s o rn o d e si sa ni m p o r t a n t t e c h n o l o g yi nw i r e l e s ss e n s o rn e t w o r k s t h eh lm e t h o dc l a s s i f i e sn o d e si n t o f r a m e w o r kn o d e sa n dn o r m a ln o d e sc e n t r a l i z e da n dd i s t r i b u t e dm e t h o d sa r eu s e dt o c o m p u t et h ef r a m e w o r kn o d e sl o c m i o na n dt h eb o n p , a ln o d e si o c a t i o nr e s p e c t i v e l y s i m u l a t i o n ss h o wt h a tt h em e t h o dp e r f o r m sw e l li nr e g u l a r l y - s h a p e da n dp a r t i a l i r r e g u l a r l y - s h a p e dn e t w o r k sc o m p a r e dw i t ht h ee x t a n tm e t h o d s t h eh lm e t h o d h a saf l e x i b l ei m p l e m e n t a t i o nf o rv a r i o u sa p p l i c a t i o n s a tl a s t , w et r yt oc o m b i n er d d la n dd i r e c td i f f u s i o nr o u tp r o t o c o l ，b u tt h i s w o r ke x p e c t sd e e p e rr e s e a t c h i n 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， e p ：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅或借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：五l 重盔 柙7 年6 月1 日 中圈科学技术大学硕士论文第1 章引言 第l 章引言 1 1 无线传感器网络简介 w i r e l e s ss e n s o rn e t w o r k s ，简称w s n ，即无线传感器网络，是由部署在监 测区域内的大量廉价微型传感器节点通过无线通信方式组成的自组织网络系 统。其目的是感知、采集和处理网络覆盖区域中被监测对象的信息，并通过多 跳中继方式将监测数据传送到s i n k ( 汇聚) 节点，最终借助长距离或临时建立 的链路将数据传送到远程中心进行集中处理【l 】【2 l 。图l 给出了传感器网络体系 结构一般形式的描述。 无线传感器网络的研究起步于2 0 世纪9 0 年代末期，被认为是2 l 世纪最重 要的技术之一，由于其在医疗卫生、环境监测和军事等领域广阔的应用前景， 引起了各国军事部门、工业界和学术界的极大关注，在基础理论和工程技术层 面提出了大量极具挑战性的研究课题。国际上最早开展无线传感器网络研究的 国家是美国，比较有代表性的项目有1 9 9 3 1 9 9 9 年间加州大学洛杉矾分校 ( u c l a ) 开展的w i n s 项目；1 9 9 9 - - 2 0 0 1 年间u c b e r k e l e y 开展的s m a r t d u s t 项目；1 9 9 8 - - 2 0 0 2 年加卅大学伯克利分校等2 5 个机构联合开展的s e n s j t 计划； 1 9 9 9 - - 2 0 0 4 年阃海军研究办公室的s e a w e b 计划；2 0 0 4 年哈佛大学启动的 c o d e b u l e 平台研究计划等p 】。欧洲对w s n 的研究紧随其后，2 0 0 2 - - 2 0 0 5 年间 开展了e y e s 研究计划。国内近年来对w s n 的关注也日益强烈，2 0 0 4 年国家 自然科学基金将无线传感器网络列为重点研究项目。2 0 0 5 年国家自然科学基金 资助的项目中，仅面上项目涉及传感器网络的就有】5 项之多。2 0 0 6 年国家自 然科学基金将水下移动传感器网络的关键技术列为重点研究方向。中国科学技 术大学、清华大学、中科院计算所，上海微系统所、沈阳自动化所等多家高校 和研究单位均已开展了无线传感器网络相关领域的研究。 图1 。传感器网络的体系结构 第l 页共6 7 页 中田科学技术大学顼士论文无线传感器网络中的节点定位方法研究 1 2 研究节点定位的意义 与传统的无线网络如移动通信网、无线局域网、蓝牙网络等相比，无线传 感器网络具有硬件资源受限、自组织、多跳、节点数量众多等特点。由于这些 特点，现有网络中的许多技术并不能直接应用于无线传感器网络，因此无线传 感器网络中有许多关键技术值得研究，节点定位技术就是其中之一。 无线传感器网络中的定位包括两个方面：一是对网络外的监测目标定位， 确定目标的位置或坐标，也叫跟踪检测；二是对网络中传感器节点的定位，获 取传感器本身的位置或坐标，即节点的自定位技术和方法，这是本文重点研究 的内容。 无线传感器网络中的大多数应用都需要知道节点的位置信息，传感器节点 必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对 外部目标的定位和追踪。另方面，节点位置信息还可以提高路由效率，向部 署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置等。要 获取节点的位置信息，最直接可靠且精度又高的方法是卫星定位，如覆盖全球 的g p s 定位系统、覆盖中国全境的“北斗一号”双星定位系统等。但无线传感 器网络是一个资源受限的网络，其节点一般都采用电池供电，且不可再次充电， 能耗要求极为严格，不能有效支持卫星通信设备。另外传感器节点设计要求廉 价，体积小巧，这也决定了网络中不可能对大量节点都配备卫星通信设备。总 之，人工部署和为所有网络节点安装卫星通信设备都会受到成本、功耗、扩展 性等诸多问题的限制，甚至在某些场合可能根本无法实现，因此必须采用一定 的机制和算法实现节点定位。 1 3 无线传感器网络的节点定位方法介绍 目前人们提出了多种无线传感器网络中的节点定位方法，这些方法按照不 同的准则可分为不同的类别，以下介绍几种主要分类方式。 1 3 1 绝对定位与相对定位 绝对定位与物理定位类似，定位结果是一个标准的坐标位置，如经纬度。 而相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。 绝对定位有广泛的应用领域，但相对定位也有自己的应用场合。尤其是基于地 理位置的路由，只需相对定位即可。典型的相对定位算法和系统有s 队 ( s e l f - p o s i t i o n i n ga l g o r i t h m ) ，l p s ( l o c a ip o s i t i o n i n gs y s t e m ) ，s p o t o n 等， m d s m a p 定位算法可以根据网络配置的不同分别实现两种定位。 实现绝对定位需要有部分已知位置的参考节点，又叫锚节点，这类节点一 般由人工部署在指定地点或者通过卫星定位系统获取绝对位置。其余的节点则 第2 页共6 7 页 中国科学技术大学硕士论文 第1 章弓l 言 利用锚节点的位置作参考实现绝对定位。 1 3 2 集中式定位与分布式定位 集中式定位是指把所需信息传送到某个中心节点上进行定位计算的方式。 集中式定位的优点在于从全局角度统筹规划，可以获得相对精确的位置估算。 它的缺点是网络的计算量分布不均，中心节点的计算负担较大，能耗较多，且 处于中心节点附近的节点通信开销较大。集中式定位算法包括凸规划算法、 m d s - m a p 算法等。 分布式定位与集中式定位相反，尽量将计算量分摊到网络中的各个节点上， 而不是在某一个节点上完成，以减小甚至消除对中心节点计算能力的要求，对 于资源受限和无中心自组织的无线传感器网络来说是比较理想的定位方法。典 型的分布式定位方法有a p s 、a f l 、e i g e n 、m d s m a p ( p , r ) 等。这些方法在 节点部署方式、信号复杂程度、定位精度等方面作了不同程度的折衷。 l ，3 3 基于测距的定位和无需测距的定位 根据定位过程中是否需要测量实际节点问的距离可以把定位算法分为基于 测距( r a n g e b a s e d ) 的定位算法和无需测距( r a n g e - f r e e ) 的定位算法。前者 通过测量节点间的距离或角度信息，使用三边测量法、三角测量法或最大似然 估计法计算节点位置：后者则无需距离和角度信息，仅根据网络连通性等信息 实现。下面分别介绍这两类方式中的典型定位算法 1 3 3 1 基于测距的定位【5 l r s s i ( 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 f 信号。因传感器节点本身具有无线通信能力， 故其是一种低功率、廉价的测距技术，r a d a r 、s p o t o n 等许多项目中使用了 该技术。但r s s i 得到的测距结果很粗糙，可产生5 0 的测距误差。 t o a ( t i m eo f a r r i v a l ) ：该技术通过测量信号传播时间来测量距离。使用 t o a 技术最著名的定位系统是g p s ，g p s 系统需要昂贵、高能耗的电子设备来 精确同步卫星时钟。 t d o a ( t i m cd i f f e r e n c eo na r r i v a l ) ：t d o a 测距技术被广泛应用在w s n 定位方案中，通过记录同一信号或两种不同信号的到达时间差，基于已知信号 传播速度，将时间转化为距离。常见的t d o a 技术使用r f 和超声波两种信号 进行测距，但超声波信号传播距离有限，且需考虑n l o s ( n o n l i n e - o f - s i g h t 非视距) 问题对信号的传播影响。 a o a ( a n g l eo f a r r i v a l ) ：这是一种估算邻节点发送信号方向的技术，可 第3 页共6 7 页 中国科学技术大学硕士论文无线传感器网络中的节点定位方法研究 通过天线阵列或多个接收器结合来实现。同样，a o a 技术也受外界环境影响， 如噪声、n l o s 问题等都会对测量结果产生不同影响。同时，a o a 需要额外硬 件，在硬件尺寸和功耗上可能无法用于传感器节点。 1 3 3 2 无需测距的定位 质心定位算法【5 j ：这是由南加州大学的n i m p a m ab u l u s u 等提出的一种仅基 于网络连通性的室外定位算法。该算法的核心思想是：锚节点每隔一段时间， 向邻节点广播一个信标信号，信号中包含自身i d 和位置信息。当未知节点接 收到来自不同锚节点的信标信号数量超过某一个预设门限或接收一定时间后， 该节点就确定自身位置为这些锚节点所组成的多边形的质心。该算法的优点是 算法简单，缺点是仅能实现粗定位，且需要较高的锚节点密度。 凸规划定位算法【5 】f 6 j ：加州大学伯克利分校的d o b e r t y 等人将节点问点到点 的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，从而将 节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到 一个全局优化的解决方案，求得节点位置。该算法的缺点是计算复杂，且最后 的定位精度与锚节点放置位置有很大关系。- a p s ( a dh o cp o s i t i o n i n gs y s t e m ) t 7 j ：美国路特葛斯大学的d r a g o sn i c u l e s c u 等人利用距离矢量路由和g p s 定位的原理提出了一系列分布式定位算法，合称 为a p s 。它包括6 种定位算法：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 ， d v - b e a r i n g 和d v - r a d i a l 。其中最有代表性的是d v - h o p 定位算法，它分为3 个阶段：第l 阶段，应用距离矢量交换协议使网络中所有节点获得距锚节点的 跳数；第2 阶段，在获得其他锚节点位置和相隔跳距后，锚节点计算网络平均 每跳距离，然后将其广播至全网，节点根据跳数与平均每跳距离计算与锚节点 之间的距离；第3 阶段，当未知节点获得与3 个或更多锚节点的距离时，则执 行三边测量定位。该算法的优点是计算简单，复杂度低：缺点是鲁棒性较差， 只有当网络均匀时才能合理地估算平均每跳距离。 a m o r p h o u s 算法1 5 】：该算法采用与d v h o p 类似的方法获得距锚节点的跳 数，称为梯度值。节点i 收集邻居节点的梯度值，计算关于某个锚节点的局部 梯度平均值& ，与d v - h o p 不同的是，他假设网络平均连接度已知，使用k s 公式在网络部署前离线计算平均每跳距离( h o p s i z e ) 。当获得三个或更多锚节 点的梯度值后，未知节点f 使用s i h o p s i z e 计算与每个锚节点的距离，并用最 大似然法估计自身位置。该算法的缺点是需要预知网络的平均连接度，且需要 较高的节点密度。 a p i t ( a p p r o x i m a t ep i tt e s t ) 算法【9 】【o l ：该算法将莱节点可能的位置区 域进行三角划分，取各部分的公共区作为节点位置的估计。在这种算法中，被 定位节点首先比较邻节点与锚节点的通信关系，然后判断自己是否处于多个锚 节点所围成的三角形内，最后取这些三角形的公共区域作为节点位置的估计 第4 页共6 7 页 中国科学技术大学硕士论文第1 章引言 该算法的缺点同样是要求较高的锚节点密度。 基于m d s 的系列算法f 3 】【1 3 - 1 2 1 】【2 6 1 1 2 7 1 0 4 1 ：m d s ( m u l t i d i m e n s i o n a ls c a l i n g ) 即多维定标技术，原先是用于心理学分析和经济领域的数据统计分析方法。密 苏里哥伦比甄大学的s h a n g 等人将经典m d s 算法应用于传感器网络的节点定 位中，提出了m d s m a p 定位算法。m d s m a p 为集中式算法，可在r a n g e - f r e e 和r a n g e b a s e d 两种情况下运行，并可根据不同的网络配置实现相对定位和绝 对定位。s h a n g 等人还提出分布式的m d s m a p ( p ) 算法，把全局地图划分为多 个局部地图进行计算后再合并。j ix 等人提出的定位算法也是通过合并局部地 图得到全局地图，但使用了迭代m d s 算法求解。还有j o s e 等人提出权重m d s ( d w m d s ) 求解方法，也属于迭代m d s 求解类型。m d s 算法作为一种分折数 据间相关性的数学方法，具有很好的鲁棒性，应用于节点定位时，能根据设定 的目标函数最大程度的拟合各点之间的距离。另外，m o s 算法具有很大的灵活 性，可以应用于几乎所有类型的定位方法中，不论是相对定位还是绝对定位， 不论是集中式计算还是分布式计算，不论是r a n g e b a s e d 还是r a n g e f r e e ，它都 能在其中完成部分或全体节点的定位计算工作。基于m d s 的各种定位方法所 得到的定位精度主要取决于节点闯的测距精度和定位方法所采取的整体策略， 而不是依赖于大量的锚节点。 1 4 本论文研究的意义和主要内容 目前的各种定位系统和算法都有各自的特点和适用范围，没有哪一种是绝 对最优的，许多算法的定位精度都还有很大的提高空闭。因此，针对特定的应 用，寻找具有更高定位精度和更低复杂度的定位方法，仍然有研究价值。 本文考虑的应用场景为高密度高连接度的网络，相邻节点间能进行一定精 度的测距，不同的监测任务对节点定位精度有不同要求，定位精度可由粗到细。 基于该应用场景，我们将研究以下两个问题：一是研究具有较高的定位精度、 较少的通信量和计算量的定位方法；二是研究在一定通信量和计算量的约束条 件下具有灵活性的定位方法。 如上一节所述，m d s 算法作为一种适应性强的具有鲁棒性的节点定位算 法，能灵活的应用于各种情况，同样也非常适用于本文考虑的应用场景，因此 我们将m d s 作为研究的起点，在此基础上研究以上两个问题。 本论文的章节安排如下： 第l 章首先介绍了什么是无线传感器网络，给出其常见的体系结构，简述 了国内外对无线传感器网络的研究历史与现状。然后阐述了无线传感器网络中 节点定位研究的意义与分类方法，并简要介绍了几种典型的无线传感器网络节 点定位算法。 第2 章介绍m d s 算法的分类和计量型m d s 的基本求解方法，分别对计量 第5 页共6 7 页 中圉科学技术大学硕士论文无线传感器网络中的节点定位方法研究 型m d s 的经典解法和迭代解法做了讨论。并比较了两种迭代解法的优劣。 第3 章研究了m d s 算法迭代初值对计算结果的影响，分析了现有的几种 初值生成算法，并对其中一种做了改进，提出了a f l 直角坐标初值生成算法， 最后通过m a t l a b 仿真比较了几种初值生成算法的优缺点。 第4 章针对第一个研究的问题提出了随机扩散的分布式定位算法，该算法 通过有限次的随机扩散，不断合并局部地图最终得到全局地图。与同类定位算 法相比，在取得同等定位精度的情况下该算法所需的通信量和计算量都更少。 第5 章针对第二个研究的问题提出了集中与分布相结合的分层定位方法， 针对高连接度的网络，结合集中式计算与分布式计算的优点，给上层应用提供 了高低两种精度的可选定位方案，增加了定位的灵活性。 第6 章总结全文，并展望后续工作。 第6 页共6 7 页 中国科学技术大学硕士论文 第2 章m d s 定位算法介绍 第2 章m d s 定位算法介绍 2 1m d s 简介 m d s ( m u l t i d i m e n s i o n a ls c a l i n g ) 在各类文献中的译名多达十数种，如： 多维等级分析、多维比例分析、多维缩放比例、多维排列分析、多维尺度分析、 多维定标法、多维标度法、多维尺度构成法、多元尺度法、多元度量法等。台 湾地区的翻译多以“多元”为主，而大陆常常叫“多维”，本文统称m d s 。 m d s 属于s c a l i n g ( 等级分析或尺度分析) 的一种，同聚类分析，回归分 析等一样是现代统计学中使用的众多方法中的一种。m d s 是市场研究行业中非 常重要的一种分析方法，它使用的数据是消费者对一些商品相似程度( 或差异 程度) 的评分，通过分析产生一张能够看出这些商品间相关性的图形( 感知图) 】其实质是把月个事物的相似性度量( 或相互之间的距离) 从一个未知维数 的高维空间中映射到一个较低维数( 一般取2 维或3 维) 的空间中，在一个较 低维数的空间中拟合他们之间的距离，得出各个点在低维空间中的相对坐标。 2 1 1m d s 的分类【1 2 l m d s 处理的原始数据是各对象点之间的相似性度量矩阵( 或距离矩阵) ， 根据输入矩阵的个数，数据的准确度以及分析的模式，m d s 有以下几种不同形 态的分类： 数据矩阵的个数以及分析模式： ( 1 ) 经典m d s ( c l a s s i c a lm d s ，c m d s ) ：一个矩阵，欧几里得模式。 ( 2 ) 复m d s ( r e p l i c a t e dm d s ，r m d s ) ：数个矩阵，欧几里得模式。 ( 3 ) 加权m o s ( w e i g h t m d s ，w m d s ) ：数个矩阵，加权欧几里得模式。 ( 4 ) 一般m d s ( g e n e r a l i z e dm d s ，g m d s ) ：数个矩阵，一般欧几里得模式。 根据距离( 或相似性度量) 的精确度： ( 1 ) 非计量m d s ( n o n m e t r i cm d s ) ，数据是次序性( 等级) 尺度。 ( 2 ) 计量m d s ( m e t r i cm d s ) ，数据是等距尺度或比例尺度。 一般非计量m d s 的数据是定性数据，只强调各个数据间的大小关系，其 数值不一定准确。比如对一个群体进行心理测试时得到的反馈数据，这些数据 是各个受测对象的主观感觉，并不一定能做到定量的准确性，把它作为定性的 数据来分析更具有实际意义。 。 而计量m d s 的数据具有一定的准确性，能在数量上反映出各个点间的相 似程度( 或距离) ，比如地图上测量各城市之间的实际距离所得到的数据。 第7 页共6 7 页 中国科学技术大学硕士论文无线传癌器列络中的节点定位方法研究 2 1 2m d s 在节点定位中的应用 密苏里哥伦比亚大学的s h a n g 等人首先将m d s 应用于传感器网络进行节 点定位，提出了m d s m a p 定位算法嘲。m d s m a p 是基于经典计量型 m d s ( c l a s s i em e t r i cm d s ) 的分析方法。m d s 。m a p 算法首先通过最短路径搜索 算法求出网络中任意两点间的距离，得到距离矩阵，求出矩阵特征值和对应的 特征向量后代入经典m d s 求解公式求得每个点的相对坐标。它与以往的定位 算法f 7 湘比，提高了算法对测距误差的容错性，只需少量的锚节点就能得到较 高的定位精度。而且，在没有锚节点时也能得到所有节点的相对坐标。但 m d s m a p 是一个集中式的算法需要把所有两点间的距离集中到一个中心节 点上进行计算，中心节点的计算负担较大，能耗较多，且处于中心节点附近的 节点通信开销也较大。 为适应大规模的网络节点定位，s h a n g 随后提出了m d s m a p 0 ) 定位方法 l i3 】，即分布式的m d s m a p 。m d s - m a p 以集中方式工作称作m d s m a p ( c ) ， 以分布方式工作称作m d s m a p ( p ) ，两种情况下再分别加入精细改善步骤则叫 做m d s m a p ( c ，r ) 和m d s m a p ( p ，融。m d s m a p ( p ) 是在m d s m a p 基础上的 改进，属于分布式的算法，克服了集中式计算的缺陷。分布式的m d s m a p 算 法在每个节点上都计算局部地图，然后每次选择有最多重合节点数的相邻子地 图进行合并，最终形成全局地图。这样虽然把中心节点上的计算复杂度分摊到 了各个节点上，但在每个节点上都计算子地图和繁琐的合并工作产生了大量的 通信开销和重复计算。 其后s h a n g 等人又提出了s h a r p 等多种以m d s 为基础或与之相关的定位 算法【1 4 h 1 9 1 。同时将m d s 技术应用于无线传感器网络节点定位的还有j ix 、j o s e 以及g e o r g i o s 等人口。卜】。j ix 用迭代m d s 代替了经典m d s ，使用 s m a c o f ( s c a l i n gb ym a j o r i z i n gac o m p l i c a t e df u n c t i o n ) 算法求解。j o s e 等人使 用的权重m d s ( d w m d s ) 求解方法也属于迭代求解类型。 基于m d s 的无线传感器网络节点定位算法的研究都集中在国外，国内目 前尚无专门研究基于m d s 的节点定位算法方面的文献。 2 2m d s 算法介绍 2 2 1 托格森经典解法( 经典m d s ) 1 3 0 l 2 2 1 1 欧氏距离情形 设n 个对象可用某一欧氏空间中的向量教”，鼍2 ) ，擞帕来表示，西是杈。 与蝴之间的欧氏距离，即 第s 页共6 7 页 中国科学技术大学硕士论文 第2 章m d s 定位算法介绍 司爿i ，) 一气，) i | 2 = 【) 一) 】 ) 一 ) 】 ( 1 ) 其中向量翻也即第i 个对象的坐标，任意固定一个对象点聊，并对任意 的上k - - 1 。2 w 定义： = 1 嘞2 + 兹一) ( 2 ) 将( 1 ) 式代入上式并整理化简后可得： = 【吒) 一矗】【气。) 一勃l 】 ( 3 ) 由它们构成的押阶方阵记为： 置= 6 i ， 6 2 。6 规 6 1 6 2 。 b m 屯：6 朋 y o u n g - h o u s e h o l d e r 定理证明了置的非负定性是 办 为欧氏距离的充要条 件，而且给出了相应的欧氏空间构造方法口o 】： 设局的秩为k 则它仅有，个正特征值a 五乃 o ，其他特征值 都为0 。用口i ，耽，u r 表示与上述特征值对应的正规直交特征向量，则可将 丑分解为： 骂= 【一，_ 卜日昭( 五，五，乃) 【嵋，吩，_ 】2 = ? r ( 5 ) 其中 x = = 【q ，心，u , d i a g ( f f - 石，石，历) = f 啊，五吩，4 埤l y o u n g - h o u s e h o l d e r 定理证明了由( 6 ) 式所确定的一个，维向量x o ) ，却) ， x ( n ) b 1 3 满足各点之间的距离关系。 即已知条件( 1 ) ，任意两点之间的欧氏距离，通过矩阵的特征值分解，由( 6 ) 式可求得这n 个点在r 维欧氏空间中的坐标。同时还需要说明的是，这样求得 的坐标原点在开始构造局矩阵时的第i 个点处，即i i t f ) 1 1 2 = 一t ，) o = 爵= o ，x ( o 是零向量。 以上公式是在任意指定一个对象点i 为中心点的情况得到的，为方便后面 公式的统一，我们先将坐标中心化。从上面的距离矩阵d = 出) 出发，在噩非 第9 页共6 7 页 中国科学技术大学硕士论文 无线传感器网络中的节点定位方法研究 负定的条件下，可算出各对象点，在，维空间中的坐标砌，使咖恰为对应的欧 氏距离，其中对象点i 相应于坐标原点。下面我们通过中心化变换将坐标原点 交到各个对象点的重心，这样处理可给问题讨论带来方便。 令c = 喜二。气胪即f 为疗个对象点的重心，作以下变换： 置，) ；鼍n c ( 7 ) 墨力作为对象点的中心化坐标其重心便是坐标原点。记中心化矩阵为： x = 锡， ； 筇， ( 8 ) 与上节讨论类似，叉由相应的中心化内积矩阵b 分解得到：嚣= x x 。，毋 中的元素可直接由下式确定： 以= 【屹，一c r l x c t ，一c 1 一吉( 靠一吉军兹一寺莩+ l _ _ 乍y 7 y d 。2 j 于是，可由距离按( 9 ) 式直接算出口，然后求占的正特征值a - 2 互， o 和对应的正规直交特征向量蟊，忍，茸，由此构造出： 叉= 【磊，如，影】掘g ( 无，互：，复，) = l 元甄，互z 也，互；霹l ( 1 0 ) 2 2 1 2 一般非欧氏距离情形 我们这里说的欧氏距离是指在几何空间中两点之间直线距离的精确值，它 们一定满足两边之和大于第三边，从而可以保证占为非负定矩阵。实际情况中 常常会遇到非欧氏距离的情形，比如以多个城市间的道路距离来作为输入矩阵 做m d s 分析时。由于道路距离往往不是直线距离，很有可能出现两个城市间 直接相连的道路长度比经过第三个城市周转的两条道路长度之和还大的情况。 还比如在无线传感器网络中，由于测距时信号传输信道的复杂性，也不能完全 保证测得的所有两两节点间距离都满足两边之和大于第三边，也即嚣可能不是 非负定的，我们称这种情况为非欧氏距离情形。 如果b 的秩是，若嚣不满足非负定的条件，则显然不可能在r 维空间中 求出这些点的坐标同时还满足它们原有的距离关系。这时的办法只有降维，在 低维欧氏空间中来拟合出这些点的坐标值，且最大程度的使它们之问的距离与 原始数据保持近似。 这时不管口是否非负定的，只要求它有p 个绝对值较大的正特征值 五 以 o ，再求出相应的正规直交特征向量组i l l ，h 2 ，即，按照定义： 第l o 页共6 7 页 舅= k 坞， 咖( 压，压，劢( 1 d 并以龛的各行向量锡( j = l ，2 ，一研) 作为各对象点在p 维空间中的坐标。 我们称囊为计量性m d s 的经典解，这种求解方法称为托格森方法 这时不能保证等式孟；戈叉1 精确成立，只能期望它近似成立。为度量其近 似程度，可采用以下两种指标( 马尔迪指标) ： = 器或= 嚣 c t 动 这两种指标都叫做用p 维构形殳拟合9 或云的拟合优度。在实际计算时， 可先根据这两种指标来选择维数p 2 2 1 3 托格森方法的计算步骤 ( 1 ) 从原始距离矩阵p = ( 如，出发，按( 9 ) 式求得矩阵曰= b k 】 ( 2 ) 求否的特征值 五以及对应的正规直交特征向量印l ，屹 ( 3 ) 取适当正数o t z 口或， 口 ( 4 ) 取a 五以对应的特征向量u l ，u 2 ，u p ，按( n ) 式构造n p 阶矩阵宕 ( 5 ) 取碧的各行向量) ( 卢1 ，2 ，一w ) 作为各对象点在p 维空间中的坐标。 2 2 2 迭代解法 经典m d s 的托格森解法虽然能求解一般非欧式距离的矩阵，但仍需要距 离矩阵中的每个距离都齐全，也即必须得到每两个对象点之间的距离。显然这 在我们将要应用于无线传感器网络的节点定位中是不现实的。当无法实现所有 两两节点都能进行测距时，得到的距离矩阵中的元素就会有缺失了，对于只有 部分距离的矩阵来说，人们更多的想到用迭代的方法来进行求解，而不是用经 典的闭式解。 2 2 2 1 最陡下降法i 硼 设第i 个对象点的坐标向量表示为：嗣矿k l 砌x t p t , 即枷表示第f 个 对象点的第p 维坐标值。且令毫n - 【霸毫：气】r 表示拟合出的第i 个对象点的 坐标向量。下面定义映射误差： 芷2 焘若半2 嘉孙埘 ， 第l l 页共6 7 页 里坠兰垫垄奎兰堡圭鎏老蚕丝堡矍兰里丝! 竺至堡星堡童鎏墼窑 其中胛= ：，嘭= ：l 。呜是标准化因子，旷l 西是权系数，毛为 原始数据经过映射到p 维欧氏空间后的节点间距离。w 。( d 毛) 2 可看作是归一 化后的误差，即相对误差。这个误差可作为求得结果与原数据拟合程度的评价。 通过使k 尽量小来确定迭代公式。 设，为迭代次数，有： 础2 击萎w 以妒毛( f ) 】2 ( 1 4 其中 句u ) = ：= 。u ) 一扎( ，) 】2 ( 1 5 ) 第1 + 1 次迭代结果应为 气( ，+ 1 ) = 气( 1 ) 一m f j i ( 1 6 ) 其中& i f 为控制收敛速度的常数，可经验地取0 3 或o 4 【3 0 i ，而 喇，= 器1 剖 ， 上面涉及到的两个偏导数计算公式为： 而ak(o：一三窆至箜【气一u)】nf 魄( f ) 一4 a f ( o ，一“”、( 1 8 ) 器一去，蠹赤 “伊专警隙峨c 臂 2 2 2 2 松弛法p 哪【3 t l 最陡下降法的基本特点是每一步迭代都需要把所有的距离d f ( ，) 都改换成 毛( f + 1 ) ，l f 栉，而且需要把原有的巩( ，) 都存储起来，这需要占用大量 机时和内存。松弛法是为克服上述缺点而提出的。 松弛法与最陡下降法的区别就在