（电路与系统专业论文）无线传感器网络定位算法研究[电路与系统专业优秀论文].pdf

无线传蓐器网络定位算法研究 摘要 无线传感器网络作为一种新型的数据采集技术，综合了微电子、无线通信 和无线网络等多门学科，在军事、工业控制、环境监测、医疗救助等领域都有 广泛的应用前景。在大多数应用中，获得传感器节点的物理位置是最基本的要 求，然而，由于传感器节点数量庞大、随机分布，并且软硬件资源有限，因此 研究有效的定位算法来确定每个节点的位置具有重要的理论意义与实用价值。 本文首先分析了无线传感器网络的特点和目前已有的各类定位算法的基本 思想及性能，然后提出了一种基于信标节点多维定标( m d s ) 的无线传感器网 络分布式节点定位算法( b m d s ) ，它利用信标节点位置和节点间的距离信息实 现对未知节点的绝对定位。该定位算法的核心是本文在s m a c o f 算法的基础 上推导出的一种基于信标节点的重复优化方法，并利用距离平滑技术解决重复 优化方法中存在的局部最小值问题，提高了优化结果的精确度。 最后，本文从理论分析和m a t l 曲仿真实验两个方面评估了所提出的定位算 法的性能。验证结果表明，所提出的定位算法具有定位精度高、计算和通信复 杂度低的特点。 关键词：无线传感器网络；定位算法；多维定标；重复优化；距离平滑 一i 一 无线传癌嚣同络定位算法研究 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k , an o v e ld a t aa c q u i s i t i o nt e c h n i q u e ，i n t e g r a t em u l t i f o l d s u b j e c t si n c l u d i n gm i c r o e l e c t r o n i c ，w i r e l e s sc o m m u n i c a t i o na n dw i r e l e s sn e t w o r k , a n di sw i d e l yu s e di nm i l i t a r y , i n d u s t r i a lc o n t r o l l i n g , e n v i r o n m e n t a lm o n i t o r i n ga n d m e d i c a la s s i s t a n c ef i e l d s i nm o s ta p p l i c a t i o n s , d e t e r m i n i n gt h ep h y s i c a lp o s i t i o n so f s e n s o rn o d e si st h eb a s i cr e q u i r e m e n t s h o w e v e r , al a r g en u m b e ro fs e n s o rn o d e sa l e d e p l o y e dr a n d o m l y , f u r t h e r m o r et h en o d e sh a v el i m i t e ds o f t w a r ea n dh a r d w a r e l 陀s o u r c e s , t h e r e f o r e ，i ti sm e a n i n g f u lt od e s i g na l le f f e c t i v el o c a l i z a t i o na l g o r i t h mt o i d e n t i f yt h ep o s i t i o no f e a c hn o d e i nt h i sp a p e r , w ef i r s ta n a l y z et h ef e a t u r e so f w i r e l e s ss e n s o fn e t w o r k , t h em a i n i d e aa n dp e r f o r m a n c eo fe x i s t i n gp o s i t i o n i n gm e t h o d s , t h e np r e s c mab e a c o n s c a l i n gm d s b a s e dn o d el o c a l i z a t i o na l g o r i t h mt h a ti sb a s e do nm u l t i d i m e n s i o n a l s c a l i n g ( m d s ) w i t hb e a c o nn o d e sa n dd e r i v ea b s o l u t ec o o r d i n a t e so f9 既卿n o d e s u s i n gt h ep o s i t i o n so f b e a e o nn o d e sa n dt h ed i s t a n c e sb e t w e e nn o d e s i ti st h ec o r e o ft h e p r o p o s e dl o c a l i z a t i o na l g o r i t h m t h a tan e wb e a c o nb a s e di t e m t i v e m a j o r i z a t i o nm e t h o dw h i c hi sd e r i v e do nt h eb a s i so fs m a c o fa l g o r i t h m b e s i d e s , w em a k e 峨o fd i s t a n c es m o o t h i n gt e c h n i q u et os o l v et h el o c a lm i n i m ap r o b l e m , c o n s e q u e n t l y , t h er e s u l to f m a j o r i z a t i o ni si m p r o v e d f i n a l l y , w ee v a l u a t et h ep e r f o r m a n c eo ft h ep r o p o s e da l g o r i t h mf r o mb o t h t h e o r e t i c a la n a l y s i sa n ds i m u l a t i o ne x p e r i m e n t s i ti sd e m o u s w a t e dt h a tt h ep r o p o s e d a l g o r i t h mh a sh i 曲a c c u r a c y , l o wc o m p u t a t i o na n dc o m m u n c a t i o nc o m p l e x i t y k e y w o r d s ：w i r e l e s ss 豇l s o rn e t w o r k ；l o c a l i z a t i o na l g o r i t h m ；m u l t i d i m e n s i o n a l s c a l i n g ；i t e r a t i v em a j o r i z a t i o n ；d i s t a n c es m o o t h i n g 一 无线传感器网络定位算法研究 第一章绪论 1 1 背景介绍 无线传感器网络是目前r r 领域的一个研究热点，它分别被美国商业周刊 和m r r 技术评论杂志评为2 1 世纪最重要和最有影响力的十大新兴技术之 - - h 近年来无线通信、微电子和嵌入式计算等技术的进步，推动了低成本、低 功耗和多功能传感器节点的发展，使其能够在微小体积内集成了信息采集、数 据处理和短距离无线通信等多种功能 2 】。无线传感器网络就是由大量的传感器 节点组成的，它们分布在某一监测区域内，通过临近节点间的无线通信形成一 个多跳的自组织网络，从而协作地完成采集数据、处理数据等功能。无线传感 器网络提供了一种新的获取信息和传播信息的方式【3 】，通过这种方式，人们可 以更加全面、深入地感知和认识物理世界，其巨大的应用价值引起了世界上许 多国家的军事部门、工业界和学术界的极大关注【4 】。 无线传感器网络的研究始于2 0 世纪8 0 年代【5 】，经过二十多年的努力，无 线传感器网络得到了长足的发展。目前的传感器节点通常由微控制单元 ( m c u ) 、传感器、射频通信模块和能量供应模块四个部分组成【2 】，如图1 1 所示。微控制单元( m c u ) 负责控制传感器节点的各种行为，存储和处理来自 传感器或射频通信模块的数据；传感器负责采集目标区域内的数据；射频通信 模块负责与其它传感器节点进行无线通信，收发数据和控制信息；能量供应模 块为整个传感器节点提供运行所需的能量，通常采用微型电池。 图1 i 传感器节点结构 一1 一 无线传感器网络定位算法研究 无线传感器网络通常被部署在一些不容易管理的区域。如森林、战场、大 型建筑物等【6 ，7 】。为了能够方便观察者向网络发送控制命令，以及接收采集到 的数据，无线传感器网络还需要一套管理系统的支持，如图1 2 所示。它通常 包括任务管理节点( t a s k m a n a g e r n o d e ) 、网关节点( s i n k ) 和传感器节点。这 样观察者( u s e r ) 就可以通过管理节点对传感器网络进行管理和配置，以及发 布监测任务。同时传感器节点采集并处理后的数据首先通过多跳通信的方式在 不同的传感器节点之间传输，当沿着某一条通信路径到达一个能与网关节点直 接通信的传感器节点上时，这些数据就可以通过网关节点、互联网或卫星传输 到管理节点。传感器节点除了要完成本地数据采集和处理外，还要对其它节点 发送过来的数据进行存储、融合及转发，并与其它传感器节点合作，以完成某 些复杂的任务。 图1 2 无线传感器网络及其管理系统结构【2 】 无线传感器网络的应用根据目的不同可以分为三类：数据采集、环境监视 和目标跟踪。 数据采集主要是在科学研究领域，比如生物学家为了研究某个种群，需要 采集有关这一种群的各种数据；农业学家希望采集农田土壤的数据，来研究化 肥对土质的影响。以上这些科学研究活动都可以在相应的区域部署无线传感器 网络来实现。图1 3 是一个利用无线传感器网络采集土壤信息的模型 8 】。 一2 一 无线传感器网络定位算法研究 图1 3 利用无线传感器网络采集土壤数据 环境监视应用是把传感器节点分布在某一固定区域，持续地监视这一区域 内的情况，当检测到有异常情况发生时，传感器网络就发送报告给观察者。室 内导航( i n d o o rn a v i g a t i o n ) 是m i t 的一个无线传感器网络项目 9 】，它把传感 器节点分布在一幢建筑物中，用来监测里面的各种移动物体，同时可以按照观 察者的要求提供这些物体的具体位置。无线传感器网络还可以用于大型建筑的 安全监测、自然灾害的防范等领域。 目标跟踪是无线传感器网络的一个非常重要的应用，这种应用主要是在军 事领域。比如一个战术系统利用无线传感器网络跟踪敌军的行动，如图1 4 所 示。另外，无线传感器网络还可以代替士兵在危险区域巡逻、到敌后侦查等。 图1 4 利用无线传感器网络跟踪敌军的行动 1 0 】 一3 一 无线传感器网络定位算法研究 1 2 研究意义 定位算法的研究对无线传感器网络的应用和发展都具有重要的意义。 在无线传感器网络中，节点定位算法是一个至关重要的问题。首先它是各 种应用的基础。在无线传感器网络的各种应用中，采集数据的节点位置是需要 知道的最基本的信息之- 1 1 ，在环境检测、目标跟踪等应用中如果不知道采 集点的位置，那么所采集的数据将是毫无意义的 1 2 1 ；其次，无线传感器网络 的很多关键技术都需要利用节点位置信息。例如，地理路由协议需要直接利用 节点位置信息进行数据传递，以避免信息在整个网络中的扩散，并可以实现定 向的信息查询【1 3 】，有些路由协议 1 4 ，1 5 也需要节点位置信息来提高路由效率； 网络拓扑控制机制需要利用节点位置信息构建拓扑结构图，并评估节点的分布 情况。 同时定位问题也是一个技术难点。在无线传感器网络中，节点数量往往成 百上千，并且大多数节点都是随机分布的，而应用环境经常是那些人类难以进 入或管理的区域，因此很难预先布置好每个节点的位置，同时，为了尽可能地 降低成本，每个节点的处理器性能、存储器容量、无线收发器的通信距离以及 电池能量都是极其有限的，如果让所有节点都安装全球定位系统( g p s ) 【1 6 ， 不仅增加了成本，而且会使节点的能量很快消耗殆尽，因而这种方法不适合实 际使用。传感器节点能力的限制也要求定位技术尽可能地降低计算复杂度和节 点间的通信开销，以降低功耗，延长整个网络的生命周期。另外，由于没有基 础设施的协助 1 7 1 ，各种协议和算法应该采用分布式计算方式，这对定位技术 又提出了更高的要求。 由此可见，无线传感器网络迫切需要一种精度高、分布式、复杂度低和容 错能力强的定位算法来得到所有未知节点的位置，这一方面能够提高无线传感 器网络的性能，另一方面也能降低成本，有利于它的大规模应用。 1 3 研究内容和方案 本课题的研究内容首先是分析现有定位算法的基本原理和性能，然后提出 种新的定位算法，最后通过m a t l a b 程序设计实现所提出的定位算法，并对其 性能进行分析。 - - 4 - - 无线传感器网络定位算法研究 通过对已有定位算法的分析，针对其存在的缺点，本文提出了一种新的基 于信标节点多维定标的分布式节点定位算法( b e a c o ns c a l i n gm d sb a s e dn o d e l o c a l i z a t i o na l g o r i t h m ，b m d s ) 。该定位算法的基本思想是利用信标节点多维 定标技术直接得到未知节点的绝对坐标，避免了复杂的局部坐标系统融合以及 相对坐标到绝对坐标的转换过程，因此与基于坐标系统转换的定位算法 【1 8 ，1 9 ，2 0 】相比，b m d s 定位算法降低了复杂度和通信开销。该定位算法的核心 是一种新的基于信标节点的重复优化方法，而此方法是本文在研究了s m a c o f 重复优化方法 2 1 1 的基础上推导得到的。另外，重复优化方法存在局部最小值 问题，使得它的精确度很难提高。人们提出了很多方法来解决这个问题，其中 一种简单而有效的方法是距离平滑( d i s t a n c es m o o t h i n g ) 技术 2 2 1 ，然而因为它 只在s m a c o f 重复优化算法中得到了实现，所以我们将把它应用到新提出的 基于信标节点的重复优化算法中，从而改进我们的重复优化方法，提高其精确 度。当然，在一些极端的节点分布情况下，如信标节点位置重叠、共线等，许 多定位算法的定位精确度不高，适应能力较差，而本文根据所提出的定位算法 的特点，利用了基于阈值的选择方法来排除这些极端情况，从而进一步提高了 定位精确度。理论分析和m a t l a b 仿真实验研究表明，所提出的定位算法的计算 复杂度与m d s - m a v 0 ) 算法【2 0 】相当，而通信复杂度更低，并且在距离测量误 差、网络连通度和信标节点密度相同的情况下具有更高的定位精确度。 1 4 论文章节安排 论文第二章介绍无线传感器网络定位算法的基本原理、研究进展；第三章 详细阐述本文所提出的定位算法；第四章对所提出的定位算法进行仿真实验并 与经典算法在定位性能方面进行比较、分析：最后给出本文的结论与下一阶段 的研究内容。 一5 一 无线传感器网络定位算法研究 第二章定位算法原理介绍 2 1 基本原理 定位算法的基本原理是直接或间接测量节点之问的距离、方位或者其它连 接性信息，然后再根据这些信息计算网络中的所有节点的位置，最后对得到的 位置值进行修正，提高定位精度减小误差 2 3 】。 假设一个d 维空间中的无线传感器网络由m 0 个信标节点( 编号1 m ) 和 - m ( 驴忉) 个未知节点( 编号加+ l 玎) 组成， y 1 沈，加 表示这行个节点 的位置，秒1 以，j 讲表示聊个信标节点的位置，z 表示所有节点之间的距离向 量，那么定位问题就可以用下面的关系式来表示： y 。，y ：，y ，z 上寸 ) ，。，y ：，y 。 定位问题的关键就是要找到转化关系，使这个关系式的前后保持一一对 应，转化关系，在具体的算法中可以是矩阵方程、坐标图等等 2 2 三类定位算法 针对无线传感器网络本身的特点以及所应用的环境，已经提出了多种不同 的定位算法，这些定位算法主要分为三类：基于直接测量距离或角度的定位、 基于多跳通信的定位和基于坐标系统转换的定位。 2 2 1 基于直接测量距离或角度的定位算法 第一类定位算法根据测量距离和角度的技术不同可以进一步分为：利用 r s s i 的定位【2 4 】、利用t o a 的定位【2 5 】、利用t d o a 的定位 2 6 】和利用a o a 的定位【2 7 】。这类定位算法通常是三步法定位：第一步是测量未知节点到信标 节点的距离或角度；第二步是利用三边测量法、三角测量法或极大似然估计法 计算未知节点的坐标；第三步是利用未知节点到邻居节点的距离修正未知节点 的坐标。基于直接测量距离或角度的定位算法一般需要较高的信标节点密度或 者计算和通信能力较强的信标节点，而且除了r s s i 测距技术外，其它三种都 要求额外的软硬件支持。 一6 一 无线传感器网络定位算法研究 r a d a r 定位系统 2 4 中利用了基于r s s i 直接测距的定位算法，在这个系统 中，未知节点定期发射信号，发射功率预先知道，基站接收到信号后测得其接 收功率，从而可以计算出信号的传播损耗，然后利用信号传播模型来计算发射 节点的位置。 所用到的信号传播模型有两种：经验模型和理论模型。如果利用经验模型， 则需要建立一个位置和信号功率的关系数据库。其方法是，在室内选取几个测 试点，记录在这些点上各基站接收到的信号功率，实际定位时根据测得的信号 功率和数据库中记录的信号功率进行比较，把两者均方差最小的那个信号功率 所对应的位置作为节点的位置。理论模型即信号衰减与传播距离之间的关系式 如下： 删，c 锄，= 眠，c d b m - 1 吣刳一般筹：关；c 眩- ， p 似) 表示基站接收信号功率，p 俐表示参考节点发射的信号功率，1 7 表示 路径长度和路径损耗的比率，西表示参考节点和基站之间的距离，力表示节点 和基站之间的墙壁个数，c 表示信号穿过墙壁个数的阈值，历伊表示信号穿过 墙壁的衰减因子，d 表示未知节点和基站之间的距离。基站在测得接收信号功 率后利用这个模型就可以计算出未知节点和基站的距离，当计算出节点与三个 基站的距离后，利用三边测量法计算节点的位置。 利用理论模型计算节点位置的方法精度比前一种方法差，因为在实际环境 中各种因素的不确定性导致了理论模型往往与实际情况相差很远。有很多文献 对这个方面作了研究，文献 2 8 中提出的s p o to n 定位系统利用的信号衰减模 型结合了理论模型( 1 r 2 ) 和实际环境。文献 2 9 中提出的l a n d m a r c 定位系统 和文献 3 0 中提出的f e r r e t 系统则对信号衰减模型进行动态校准，通过这种方 法尽管能够提高定位精度，但需要在网络中布置大量额外的接收节点，增加了 网络配置的成本。 2 2 2 基于多跳通信的定位算法 第二类定位算法原理上与第一类基本相同，不同之处在于未知节点到信标 节点的距离或角度是通过多跳通信的方式间接获得的，这类算法包括d v - h o p 一 一 无线传感器网络定位算法研究 和d r - d i s t a n c e 3 1 ，d v - b e a r i n g 和d v - r a d i a l 3 2 ，h o p - t e r r a i n 3 3 。定位的 第一步是信标节点把它的位置信息扩散到整个网络中，同时获得未知节点到信 标节点的距离或角度，这个过程称为矢量路由，最后每个未知节点计算它的坐 标。矢量路由使得一个信标节点以多跳通信的方式被网络中所有节点所利用， 因而相对于第一类算法，它需要的信标节点密度大大下降，而且不需要信标节 点有更强的能力，可以和未知节点完全一样在节点密度高、分布均匀的网络 中，这类算法的定位性能较好，但是在节点密度低和不规则网络中，它的定位 精确度下降，因为在矢量路由过程中的累积误差使得最后得到的距离或角度误 差很大。 d v - h o p 定位算法利用信标节点到未知节点的跳数来推断距离。它包括三 个个阶段： 第一阶段，每个信标节点通过扩散法向网络中的节点广播消息，每一个节 点监听这些消息并记录它到每一个信标节点的最小跳数。如果节点收到了一个 最d , l g 数值就把它广播给它的邻居。 第二阶段，当一个信标节点接收到其它信标广播的消息时，它就计算每跳 的平均距离，称为校准因子( c o r r e c t i o nf a c t o r ) ，然后它把这个校准因子发送到 网络中。其它节点只接收第一个到达的校准因子，丢弃后来到达的，这样就保 证了大多数节点可以从最近的信标节点接收到校准因子。当接收到校准因子后， 节点根据跳数计算它与信标节点之间的距离。 第三阶段，未知节点如果获得了与至少3 个信标节点的距离，那么就利用 三边测量法或极大似然估计法计算自己的位置。 d v - h o p 算法实现简单，对节点的硬件要求较低，但是它用跳段距离代替 未知节点到信标节点的直线距离，而且它把每跳的距离设定为相同的平均距离， 在节点分布不均匀的环境中其定位精度会大大地降低。 d h l 算法 3 4 1 是另一种基于多跳通信的定位算法。这种算法考虑了节点分 布的密度，把某一节点所处区域的密度定义为单位射频发射范围内的邻居节点 的数量n n g b r ，并把密度分为三类：当n n g b r q 时，为高密度区域；当p o 时 = d o 何蛾( z ) ( 3 1 1 ) ( - - x j a ) z 。一z 豇) 一d f ( j r ) 一墨孑i i ；厂 3 。1 2 而当d o ( z ) = 0 时，一办( 工) o 成立 与式( 3 9 ) 同理可得 o h - x a x z m z 一) = t r ( x a j ) ( 3 1 3 ) 口。l 由式( 3 1 2 ) 、( 3 1 3 ) 可得 一n ( 石) = 嘞毛白( j ) i f f i lj = i + l 兰嘻嚣哪审， = 螂c 喜喜箍舭， = 研蜀( z ) z 】 ( 3 1 4 ) 当且仅当z = x 时，等式成立。 式中：最( z ) = 】。， 。f 一嘞岛d f ( z ) ，f j j t d u ( z ) 0 2 1 0 ，i j r d f ( z ) ：o = 一b o 1 8 一 无线传感罂网络定位算法研究 根据式( 3 8 ) 、( 3 1 0 ) 和( 3 1 4 ) 可得目标函数的最小化不等式为 c r r ( 抑= 【岛一如( j ) 】2 “l m l = 醒+ t r ( x v , x ) - 2 t r x 且( z ) z 】 ( 3 1 5 ) 孵+ t r ( x v , x ) - 2 t r x 马( z ) z 】_ z ( x ，z ) 则乃俾刁就是目标函数q ( 幻的优化函数t 它是关于矩阵x 的二次函数， 因此它的最小值点可以通过设它的导数为零来求解，即 掣笋：2 v , x 一2 b , ( z ) z ：0 ( 3 1 6 ) 砑 由上式可得 v , x = b i ( z ) z ( 3 1 7 ) 由于乃是非满秩矩阵，因此它的逆矩阵不存在，但是可以在上式两边同乘 以乃的m o o r e p c n r o s c 逆矩阵 k + = ( 巧+ k ) 一一万- 2 x ( 3 1 8 ) 式中：鬈n x n 的矩阵，所有元素均为l 。 这样就得到重复优化公式 x = 瞄马( z ) z ( 3 1 9 ) 那么s m a c o f 重复优化算法如下： z = x ( o ) ，k = g 一= 田( x o ) ； w h i l e ( k o 或( 一- t ) 一砖 刮巨七最大循环次数) ) 缸+ + ； 根据( 5 9 ) 式的重复优化公式更新未知节点坐标矩阵x ； 一= 巳( x ) ； z = x ( k ) ； ) j 是初始的未知节点坐标矩阵，可以是随机矩阵，也可以由其它算法得到， 阈值p 是一个较小的正值，一般凭经验来设定此算法最后计算出未知节点坐 一1 9 无线传感器网络定位算法研究 标矩阵j ，所有坐标值都是相对坐标。s m a c o f 重复优化算法的流程图如图 3 2 所示。 圈3 2s m a c o f 重复优化算法的流程嘲 由重复优化原理和s m a c o f 算法我们可知，要推导出重复优化算法，关 键是得到目标函数的优化函数，而要得到优化函数首先要找到目标函数的最小 化不等式，对于我们所要优化的目标函数a ( x ) ，可以把它分为前后两部分来 分别求解。 式( 3 3 ) 的前一部分只与未知节点有关，因此它就是s m a c o f 重复优化 算法的目标函数，即 q ( = q ( 西= 嘞嗡- a o ( x ) 2 ( 3 2 0 ) i = 1j = i + t 一2 0 一 无线传感嚣网络定位算法研究 它的最小化不等式为 a , ( x 3 t l ( 五z ) 当且仅当2 鼍x 时，等号成立。 下面我们来求式( 3 3 ) 的后一部分的最小化不等式。 吼( 并) = h - d 。( x ，o 】2 扭lt c l = 群+ r 2 ( d - 2 以。d 由式( 3 2 ) 可知 ( 3 2 1 ) ( 3 2 2 ) 以( x ，c ) = ( 一) 2 a - i = ( 以e f 。q ) 2 o l ， = ( e ，x o 一厂。e ) - ( p 。；以一广。c ) ( 3 2 3 ) o i - - z ( z 色丘一z 瓯e c 虮以+ c ，肚c | ) d = t r ( x b z ) 一t r ( x 瓯c ) 一t r ( c h n 硼+ t r ( c 五c ) 式中：e , - - e l e t ，瞰= 0 乏船0 ，民= f g k ， 由此可得 蹿2 ( 柳= d ：( x ，0 i = li t l ；o m t r ( x 露x ) 一2 t r ( x 瓯c ) + 护( c | 凡c ) 】 ( 3 2 4 ) t * 1 “ 。t r ( x 匕x ) 一2 t r ( x 巧c ) + t r ( c o 式中；匕= i v o 】。 以；【】。，= ； 一2 l 一 ， 挣 仉。m = = ，-fjl 无线传摩器网络定位算法研究 匕= 【】。， 根据c a u c h y - s c h w a r z 不等式可以得到 n n n ( 一) ( z 。- - c 。) ( 眈一) 2 ) 2 ( ( 气一气) 2 ) 2 a 一1a = la - i = d a ( j ，c ) 以( z ，c ) ( 3 2 5 ) 当且仅当z = x 时，等式成立。则 n ( x 。- c u ) ( z 。一c b ) “m c ) 堕1 历万一 ( 3 2 6 ) l d a ( z ，c ) = ( ( - - c l a ) 2 ) i o a - 1 与式( 3 2 3 ) 同理可得 a - | o - 一c b ) ( z m c h ( 3 2 7 ) = 护( x e d z ) 一l ，。( x g * c ) 一t r ( z g n c ) + t r ( c f k c ) 由式( 3 2 6 ) 、( 3 2 7 ) 可得 一p ( x ) = 一i 。1 k f f i l 丸( 石，c ) ( 3 2 8 ) p 且| | s 最大循环次数) ) 伍+ + 根据式( 3 3 2 ) 计算出未知节点坐标矩阵z ( ； d ( t ) = c r ( r 仲) ； z # x ( i ) ： 珂是初始的未知节点坐标矩阵，可以是随机矩阵，也可以由其它算法得到。 阈值p 是一个较小的正值，一般凭经验来设定。此算法最后计算出未知节点坐 标矩阵j ，所有坐标值都是绝对坐标。 重复优化算法经常使目标函数趋向于一个局部最小值，而不是一个全局最 一2 3 无线传感嚣同络定位算法研究 小值 2 1 1 ，这样得到的j 并不是最优化的，为了解决这个问题，我们将利用距 离平滑( d i s t a n c es m o o t h i n g ) 技术。 3 2 改进型重复优化算法 本节我们将详细阐述重复优化算法的一个重要的技术特性一局部最小值问 题，即目标函数存在多个局部最小值，而上一节提出的重复优化算法得到的最 终结果有可能是这些局部最小值中的任何个，因此如果目标函数的局部最小 值越多，重复优化算法的最终结果是全局最小值的概率就越小，这将严重影响 算法的精确度。在说明了局部最小值问题之后我们将利用一种现有的技术一距 离平滑一来改进上一节提出的重复优化算法，得出新的算法。 3 2 1 重复优化算法中的局部最小值问题 重复优化算法有时候得到的是一个全局最小值，这是最理想的结果，有时 候得到的是一个局部最小值，这个结果并不是完全不可接受的，如果它小于我 们设定的阈值，那么我们仍然认为它是一个符合要求的结果。为了更加简单和 直观，我们以一个单变量函数的重复优化来举例说明这个问题。如图3 3 所示， 目标函数俐在毒鼍【处取得局部最小值，在工弼处取得全局最小值，优化函数 蚋砂与刷的左侧分支相交，即z 的初始值位于最左边，这样重复优化算法产 生的目标函数值序列倒、佑、m 7 是在刷的左侧分支上取得的，最终重复 优化算法将在得到局部最小值形后停止。优化函数g c x , z ) 与f c x ) 的右侧分支相 交的情况如图3 4 所示，显然在这种情况下，重复优化算法将在得到全局最小 值删后停止由这两个例予可见，优化函数中z 的初始值对于重复优化算法 最终停止于目标函数的局部最小值还是全局最小值有至关重要的影响，显然随 机取一个z 的初始值不利于重复优化算法得到全局最小值，如果目标函数的局 部最小值很多，那么重复优化算法就很少有机会得到全局最小值了，因此我们 应该合理地取这个值，在3 3 节中，我们根据提出的定位算法的特点取定了一 个初始值。 一2 4 无线传感嚣网络定位算法研究 图3 3 函数删在赴处取得局部最小值，在拓处取得全局最小值 j g ( 纠 | | ； j 、 | ! s ( x , x * y | 、| i， 、一 一、 ”、。彳 7 ! 图3 4 函数倒在札处取得局部最小值，在却处取得全局晟小值 除了合理地选择坐标矩阵z 的初始值外，人们提出了多种不同的方法来解 决重复优化算法的局部最小值问题，这些方法有：维度逐步缩减法、多个随机 初始值试探法、隧道效应( t u n n e l l i n g ) 法和距离平滑法。在这些方法中，距离 平滑方法相对简单并且效果也较好，因此我们利用这种方法来解决局部最小值 问题，并推导出新的重复优化算法。 一2 5 无线传感器同络定位算法研究 3 2 2 距离平滑技术 距离平滑技术最初是p l i n e r 于1 9 9 6 年提出的，他的目的是为了解决一维定 标( u n i d i m e l l s i o n a ls c a l i n g ) 中的局部最小值问题，即n 个点位于一条直线上。 坐标矩阵x 是由n 个点的坐标构成的列向量，两个点之间的距离为 办( 柳刊而一j ( 3 3 3 ) 则目标函数为 q ( 幻= ( 磊一i _ 一td 2 “+ 1 ( 3 3 4 ) = 哆彰2 + 哆( 而一_ ) 2 - 2 嘞岛i 而一- i j - lj = i + li l lj = i + li - lj t + l p l i n e r 用一个平滑后的距离邑( 而一t ) 来替换原来的距离略( x ) ，其中 g 。( f ) ：j ! 笋+ 詈，i ，l 占 那么目标函数就变为 巳皤) - - z 嘞嗡- g 。“- x j ) 2 “，“1 ( 3 3 6 ) = 霹+ 繇2 “一_ ) 一2 吩岛& “- x j ) i l lj ，i + li - iy - “i “i 肼l 再对这一新的目标函数作重复优化。p l i n e r 进行的数值实验显示，运用距 离平滑的重复优化算法几乎能够1 0 0 地找到全局最小值。然而他只把距离平 滑技术运用在一维定标中，对于多维定标的情况他只是作了简单的推广，所提 出的重复优化算法，为了保证其收敛性，在每一重循环时都需要一个步长搜寻 过程，时间开销和计算量都比较大，不适合实际使用。 1 9 9 9 年g r o e n e n 等人在p l i n e r 研究的基础上，把这一思想运用到多维定标 中，提出了更为简单和有效的重复优化算法。他们用另外一个函数 。( f ) 来平滑 距离d 。( x ) ，它的定义如式( 3 3 7 ) 所示。 一2 6 无线传感器罔络定位算法研究 啪) ：睡+ 主巾即 ( 3 3 7 ) u f l ， i t 臣占 即用 。( 一石膏) 来替换1 - - x j ai ，则距离如( 工) 就被替换为 d o ( x ，占) ：( 兰 ；( 毛一b ) ) ； ( 3 3 8 ) 下面我们来考察一下，作这样的替换会有什么效果。图3 5 显示了函数i t i 和h ，似，可以看到，当h 大于等于时，h ，与吲相等，当h 小于s 时，h ，是 大于m 的二次曲线，这样原来i t i 函数的折线形状变成h ，渺函数的平滑曲线形状。 由h ，俐的定义式( 3 3 7 ) 可知，当p 为大于零的任何值时，h ，例总是大于零并 且处处可导，因此它的图形总是一条平滑的曲线，的大小决定了平滑程度， c 的值越大，h ，彬对的平滑程度就越高，并且当i t l d 于f 时，h ，彤比l f | 大得越 多，而当为零时，h ，f j ：j 就等于m 即此时没有平滑。图3 6 ( a ) 和( b ) 分别 显示了r 为2 和5 时的平滑情况。 太 勃。 0 图3 5 函数m 和hr 彤 一2 7 无线传感嚣网络定位算法研究 图3 6 ( a ) 图显示了e - - - = 2 时的平滑情况，图显示了e 硝时的平滑情况 我们再用一个例子来考察一下距离平滑对式( 3 3 ) 所示类型的目标函数的 酬小c = 豳 一2 8 无线传_ 眵器网络定位算法研究 那么目标函数为 c y ( x 4 i ，j 4 2 ) = ( 5 一【o 1 一o ) 2 + ( 一0 ) 2 】2 ) 2 i + ( 3 一 ( j r 4 l - 5 ) 2 + 0 4 2 0 ) 2 】2 ) 2 l + ( 2 一【( l - 2 ) 2 + ( + 1 ) 2 】2 ) 2 l 误差项( 5 - ( x 。- o ) 2 + ( 工。一o ) 2 】2 ) 2 的图形表示如图3 7 所示。当点4 的位 置在以( o ，o ) 为圆心，5 为半径的圆上时，这个误差项的值最小，而当点4 位于( o ，o ) 上时，它的值最大，另外在图中也可以看到，这个误差项图形的 最高点在原点处。其它两个误差项的特点与此类似，当我们把三个误差项的图 形叠加起来时就得到了目标函数仃( _ 。，, x 4 2 ) 的图形表示，如图3 8 所示。由图中 可见，这个图形非常不规则，有几处很明显的凸起，这些凸起部分就是三个误 差项图形的最高点。这样导致了这个目标函数存在一个局部最小值和一个全局 最小值。根据我们的仿真实验可知，如果以初始的未知节点坐标矩阵j 为随 机矩阵来执行重复优化算法b m d s w i t h o u t s m o o t h i n g ，那么得到目标函数全局 最小值近似值的可能性不到5 0 。 l 图3 7 误差项( 5 一【( x 。一o ) 2 + ( x 一o ) 2 1 i ) 2 的图形表示 一2 9 一 争i_咨乙零了n一。0潭一一_rg】 无线传感器同络定位算法研究 8 气6 孳4 菩2 o - 2 图3 8 目标函数仃( 工4 1 ，扎) 的图形表示 现在我们运用距离平滑技术，即距离白( x ) 披替换为毛【x 力，那么误差 项 l ( 5 一 ( j _ i o ) 2 + o 一o ) 2 】z ) 2 就变为 i ( 5 一 醒( _ 。一o ) + 圮一o ) 】- ) 2 我们以e 的值为2 来画出它的图形，如图3 9 所示，由图中可见，在( o o ) 点 处，与原来的误差项图形相比它比较平坦和圆滑，这是因为当h 1 0 1 2 或者 i x 2 - o l 【( 确一o ) 2 + ( 石：一o ) 2 】- l 并且 醒( 鼻。一0 ) + 醒( 一o ) 】2 是关于x 4 1 和x 4 2 的二元二次函数。另外根据平滑 l 函数玉，的性质我们可以得到平滑后的误差项( 5 一【砖( 。一o ) + 形( 一。烀) 2 与的关系：f 越大，它的图形在( 0 ，0 ) 点处就越平坦，即平滑程度越高，而 当p 为零时，它与原来的误差项完全相等，即此时没有平滑。其它两个误差项 的情况与此类似，那