（通信与信息系统专业论文）基于凸优化的无线传感与激励网络定位技术研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 无线传感与激励网络( w i r e l e s ss e n s o ra n da c t u a t o rn e t w o r k s ，w s a n ) 是在传统无 线传感网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 的基础上引入激励器而衍生出的一种全 新的网络。由于激励器的引入，w s a n 在极大地扩展了传感网络的功能和应用的同时， 也面临着异构节点间协调、通信、调度等诸多问题的挑战。另外，与w s n 应用相似， 对于大多数的w s a n 应用来说，没有位置信息的传感器测量数据同样是没有意义的。 因此，节点定位技术也是w s a n 的一项支撑技术。目前，基于w s a n 的定位技术， 特别是大规模网络环境下的定位技术还比较有限。为此，本文在分析研究传统w s n 相 关节点定位技术的基础上，对w s a n 节点定位技术展开了研究。在w s n 中的研究已 表明基于凸优化的定位方法在较少锚节点的情况下即能取得较好的定位性能，本文为 此借鉴w s n 中的研究思路和方法，并结合w s a n 自身的特点，研究了基于凸优化的 w s a n 定位算法及分布式节点定位技术。 首先，在查阅大量相关文献的基础上，本文综述了无线传感与激励网络技术在国 内外的研究现状，介绍了无线传感网络定位算法分类以及节点计算方法，并详细分析 了近年来具有代表性的算法和研究成果。 其次，本文介绍了传感网络节点定位的二阶锥规划模型( s o c p ) 、半定规划模型 ( f u l l s d p ) ，以及半定规划的两种松弛模型基于节点的s d p 模型( n s d p ) 禾d 基于边的 s d p ( e s d p ) 模型。模型中以最小化节点间距离误差为目标函数，节点间距离为约束， 将节点定位问题建模成一个凸优化问题，并利用相关松弛技术将模型松弛为容易求解 的问题。此外，本文还通过理论分析及仿真详细研究了各种相关的基于测距和无需测 距的凸优化定位方法。 然后，针对几种基于凸优化的分布式定位模型，通过理论分析、数学推导和仿真 实验验证了文中所提出的各类定位算法的有效性和适用性。对于大规模的传感网络定 位问题，将梯度搜索算法应用到基于簇的定位中，有效地改善了基于簇的s d p 分布式 定位算法的性能。将顺序贪婪优化算法应用到e s d p 定位中，得到的e s o c p 模型比分 布式s o c p 的定位性能更好，并且利用s g o 算法得到的求精算法能进一步改善定位效 果。仿真结果表明：将这些模型应用到无线传感与激励网络的定位问题中都取得了有 效的结果。 最后，本文对开展的工作进行了总结，并给出了进一步研究的内容和建议。 关键词：无线传感与激励网络；凸优化；二阶锥规划；半定规划；分布式定位算法 a b s t r ac t w i r e l e s ss e n s o ra n da c t u a t o rn e t w o r k ( w s a n ) i s ak i n do fn e wn e t w o r kd e r i v e df r o m t h et r a d i t i o n a l 、矾r e l e s ss e n s o rn e t w o r k ( w s n ) a n d b a s e do nt h ei n t r o d u c t i o no fa c t u a t o r 8 d u et ot h ei n t r o d u c t i o no fa c t u a t o r s ，w s a ne x p a n d st h es e n s o rn e t w o r k si nf u n c t i o n a l i t y a n da p p l i c a t i o na r e a st r e m e n d o u s l y b u t i ta l s of a c e sm a n yc h a l l e n g e s ，s u c h a st h e c o o r d i n a t i o n ，c o m m u n i c a t i o na n ds c h e d u l i n gp r o b l e ma r i s i n gf r o mh e t e r o g e n e o u sn o d e s i n a d d i t i o n t om o s to fa p p l i c a t i o n s ，i tm a k e s n os e n s ef o rw s a nt og a t h e rs e n s o rd a t aw l 也o u t s e n s o r1 0 c a t i o ni n f o r m a t i o n t h u s ，n o d el o c a l i z a t i o n i sa l s ot h es u p p o r t i n gt e c h n o l o g yt o w s a n a tp r e s e n t ，t h el o c a l i z a t i o nt e c h n o l o g ya b o u tw s a nn e t w o k se s p e c i a l l y i nt h e l a r g e s c a l en e t w o r k si s s t i l lr e l a t i v e l yl i m i t e d c o n s e q u e n t l y , r e s e a r c ho nt h e l o c a l l z a t l o n t e c h l l i a u e si nw s a ni sc o n d u c t e di nt h et h e s i so nt h eb a s i so ft h er e l a t e dn o d el o c a l i z a t i o n i n v e s t i g a t i o ni n w s n r e c e n tr e s e a r c ha b o u tw s n ss h o w st h a t c o n v e xp r o g r 锄m m g l o c a l i z a t i o nt e c h n i q u e sc a np r o v i d eb e t t e rl o c a l i z a t i o np e r f o r m a n c ew i t hl e s s a n c h o rn o d e s t h u s ，1 e 锄i n g 矗o mt h ei d e a sa n dm e t h o d so fr e s e a r c hi n w s n ，a n dc o m b i n e dw s a n o w n c h 撒c t e r i s t i c s ，t h ew s a nl o c a l i z a t i o nt e c h n i q u e sb a s e do n c o n v e xp r o g r a m m i n g a r em a i n l y s t u d i e di nt h et h e s i s f i r s to fa l l ，o nt h eb a s i so fr e a d i n gal o to f r e l e v a n ti n f o r m a t i o n ，t h i st h e s i sd e s c r i b e st h e r e s e a t c hs t a t u so f 也ew i r e l e s ss e n s o ra n da c t u a t o rn e t w o r ka t h o m ea n da b r o a d ，a n d c l a s s i f i c a t i o no ft h ew i r e l e s ss e n s o rn e t w o r kl o c a l i z a t i o na l g o r i t h ma n dn o d e sc a l c u l a t i o n m e t l l o da r ep r e s e n t e d m e a n w h i l e ，s o m er e p r e s e n t a t i v ea l g o r i t h m s a n da c h i e v e m e n to l r e s e a r c ha r em a i n l ys t u d i e di nt h et h e s i s s e c o n d l s e c o n d o r d e rc o n ep r o g r a m m i n g ( s o c p ) ，s e m i - d e f i n i t ep r o g r a m m i n ga n d t w ok i n d so fs d pr e l a x a t i o nm o d e l si n c l u d i n gn o d e b a s e ds d p a n de d g e - b a s e ds d pa r e d r e s e n t e d i nt h e s em o d e l s ，t h el o c a l i z a t i o np r o b l e mi s m o d e l e da sa c o n v e xo p t i m i z a t i o n d r o b l e mw h i c ht a k e st h em i n i m u md i s t a n c ee r r o ra st h eo b j e c t i v ef u n c t i o n ，a n dt h ed i s t a n c e b e t w e e nn o d e sa st h ec o n s t r a i n t s ，a n dt h e nr e l a x e dt oa ne a s yp r o b l e mb yr e l a t e dr e l a x a t i o n t e c h n i q u e s i na d d i t i o n ，t h r o u g h t h e o r e t i c a la n a l y s i s a n ds i m u l a t i o ns t u d y , s e v e r a l r a n g e b a s e da n dr a n g e f r e ec o n v e xo p t i m i z a t i o nl o c a l i z a t i o nm e t h o d sa r ei n v e s t i g a t e di nt h e t h e s i s t h e n t os e v e r a ld i s t r i b u t e d l o c a l i z a t i o nm o d e l sb a s e do nc o n v e xo p t i m i z a t i o n ， e 丘色c t i v e n e s sa n da p p l i c a b i l i t yo ft h ev a r i o u st y p e so fl o c a l i z a t i o na l g o r i t h m sh a v eb e e n v e r i f t e dt h r o u g ht h et h e o r e t i c a l ，m a t h e m a t i c a lf o r m u l aa 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 f o rt h el a r g e s c a l es e n s o rn e t w o r kp o s i t i o n i n g ，t h eg r a d i e n ts e a r c ha l g o r i t h m i sp r e s e n t e d a n da p p l i e dt ot h ec l u s t e r - b a s e dp o s i t i o n i n g ，w h i c he f f e c t i v e l yi m p r o v e st h ep e r f o r m a n c eo f t h ec l u s t e r - b a s e ds d pd i s t r i b u t e d p o s i t i o n i n ga l g o r i t h m s e q u e n t i a lg r e e d yo p t i m i z a t i o n ( s g o ) a l g o r i t h mi sp r e s e n t e da n da p p l i e dt ot h ee s d pp o s i t i o n i n ga n di t sp e r f o r m a n c ei s s i g n i f i c a n t l yb e t t e rt h a nt h ed i s t r i b u t e ds o c p , a n dt h er e f i n e m e n ta l g o r i t h mo fs g oc a n f u r t h e ri m p r o v et h ep o s i t i o n i n ge f f e c t it h es i m u l a t i o nr e s u l t ss h o wt h a tt h e s el o c a l i z a t i o n m o d e l sw h i c ha r ea p p l i e dt ot h ew i r e l e s ss e n s o ra n da c t u a t o rn e t w o r kh a v ea c h i e v e d e f f e c t i v er e s u l t s f i n a l l y , t h ew h o l ew o r ko ft h er e s e a r c hp r o je c t sc a r r i e do u ti ss u m m a r i z e di nt h et h e s i s a n da tl a s t ，t h et h e s i sp o i n t so u tt h ec o n t e n t sa n dr e c o m m e n d a t i o n sf o rf u r t h e rr e s e a r c h k e y w o r d s ：w i r e l e s ss e n s o ra n da c t u a t o rn e t w o r k ；c o n v e xo p t i m i z a t i o n ；s e c o n d o r d e r c o n ep r o g r a m m i n g ；s e m i d e f i n i t ep r o g r a m m i n g ；d 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 西南交通大学硕士研究生学位论文第1 页 11|1 1 1 课题研究背景和意义 第1 章绪论 近年来，计算机技术、微电子技术、无线通信等技术的进步，推动了低功耗、低 成本和多功能的传感器节点的发展，并且孕育了微机电系统( 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 ，m e m s ) 技术下的无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 。从改变了人 与人之间的沟通方式这种意义上可以说i n t e m e t 构成了逻辑上的信息世界，那么w s n 网络则将逻辑上的信息世界与客观物理世界融合在一起，将人类与自然界间的交互方 式作出了重大改变【l 引。 w s n 3 4 j 是由被随机部署在监测区域的大量传感器节点组成，通过无线通信方式形 成的一个多跳的自组织网络系统。近年来，无线通信技术和低功耗嵌入式技术的快速 发展，带来了信息感知的一场变革，为w s n 网络赋予了广阔的应用前景。虽然无线传 感器网络已经在众多领域得到了广泛的应用，但是越来越多的场景要求激励器( 也被 称为执行器节点) 与传感器结合使用。因此，无线传感与激励网络( w i r e l e s ss e n s o ra n d a c t u a t o r n e t w o r k ，w s a n ) 应运而生。无线传感与激励网络有传感器和激励器两类节点。 传感器节点从环境中采集数据信息，而激励器节点根据数据信息采取行动，进而改变 环境行为。与传统无线传感器网络一样，w s a n 在军事国际、工农业控制、城市管理、 环境监测、抢险救灾等许多领域有着十分广阔的应用前景。目前，已经出现了一些应 用于实际的w s a n 网络。例如，t w a r k 等人设计了一种应用于牧场中牛食物补充的 移动w s a n ，能有效防止牛因争抢食物而发生恶斗；当两头牛靠得很近时，附加在牛 身上的传感器节点会向激励节点发出激励请求，促使他们分开【5 】。c h r i s t o p h e rj r o z e l l 等人设计了一种w s a n 资源最优分配策略，确保在实施激励的状态下，全网络能达到 能耗最低【6 j 。p a v a ns i k k a 等人设计了一种大型的异构w s a n ，应用在农场的监控与管 理，能有效地实现土壤酸碱度测量，计算动物消耗食物和水分的数量，并能对动物进 行跟踪和激励【7 j 。 与无线传感器网络相似，节点定位技术也是w s a n 的一项关键支撑技术。对于大 多数的w s a n 应用，没有位置信息的数据毫无意义。在无线传感与激励网络中，一方 面，节点必须明确自身位置才能详细说明“在什么位置或者区域发生了某种特定事件”， 从而实现对外部具体环境的有效监测；另一个方面，也只有知道了节点位置信息，才 能有效的调度自身及周围的有关激励器节点对其事件信息采取及时有效的反馈动作。 全球定位系统g p s ( g l o b a lp o s i t i o ns y s t e m ) 是目前应用得最成熟最广泛的定位系统，其定 位精度高、实时性好、抗干扰能力强，但这是建立在高成本代价之上的，这个特性使 西南交通大学硕士研究生学位论文 第2 页 i r l -1 1i 其并不适用于对能耗、体积、成本等都有限制的传感网络。与无线传感器网络节点类 似，无线传感与激励网络节点一般也采用电池供电，受成本，功耗、节点体积、可靠 性等的限制，在节点上采用g p s 定位并不现实。高精度、低功耗的w s a n 定位技术是 w s a n 网络得到推广、应用需要研究的一项关键技术。 基于凸优化的定位算法因为其全局收敛特性，在无线传感器网络的定位技术研究 中受到人们的重视【8 j 。但在w s a n 定位技术研究中，这类研究还不多见。为此，本课 题开展了基于凸优化的w s a n 定位技术相关的研究；针对网络规模大时约束条件过多， 进而计算量也增大这个缺点，分析研究了相关分布式定位技术，以有效减小计算复杂 度，满足w s a n 网络对定位实时性的要求。本项研究对应丰富和发展w s a n 定位相 关技术，具有一定的理论和实践意义。 1 2 无线传感与激励网络概述 1 2 1 无线传感与激励网络的基本概念 w s n 系统中包括传感器节点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 和管理节点，典型 的网络结构如图1 1 所示。在传感器网络中节点被任意部署在监测区域内，节点通过 自组织形式构成网络，并通过多跳路由方式将其监测到的数据传输到汇聚节点，最终 再借助互联网、无线网络或卫星等将数据信号传送至管理节点。 图1 - 1w s n 体系结构图 传感器节点的组成：传感器模块、处理器模块、无线通信模块和能量供应模块。 体系结构如图1 2 所示。 西南交通大学硕士研究生学位论文第3 页 | 1 - - ：； h n e t h m ch 收发器 i i s e n s o r - l i m e m o r y a c d c r l i i i l 传感器模块 ： ： c p u ：无线通信模块 jl i jl ： 信息处理 ： ： 模块 ： l i 能量供应模块 图1 - 2 传感器节点体系结构 传感器节点因其自身的特点而导致的现实约束，使其在实现各种网络协议和应用 系统时有一些困难。如下： 电源能量有限传感器体积微小，其携带电池容量有限。集成电路工艺的进 步使得处理器和传感器模块的功耗很低，因此，大部分能量消耗在无线通信模 块。 通信能力有限通信模块的能量消耗与通信距离的关系为：e = k d ”，其中， 参数咒满足关系2 = x t x 可以等效地表示为一个线性矩阵不等式( l m i ) z - = 0 ，该问题等价 为如下问题： f i n d z 吼( ”2 ) 。( ”+ 2 j f ( 1 ；0 ；o ) 。z ( 1 ；0 ；0 ) = 1 ( o ；1 ；0 ) 。z ( 0 ；1 ；0 ) = 1 ( 1 ；1 ；o ) 。z ( 1 ；1 ；0 ) = 2( 3 2 0 ) ( 0 ；e i e j ) 。z ( o ；e i e j ) = d s i 2v ( j ，f ) n x ( a k ；一e j ) 。z ( a k ；一e j ) 7 - d j k 2 , v ( j ，尼) 虬 z - = 0 其中0 为所有元素都为零的零向量或者零矩阵，e ；为只有在第i 个位置上元素是1 ， 其他元素都为零的向量。 3 3 2 引入误差量的s d p 定位模型 锚节点a k 与未知- 1 丁+ 4 - - 点x j 之间的测距误差为0 ) i 。，未知节点x ；与未知节点x j 之间的测距误 差为，那么有： z 叫x 也颞) m 。2 d 其中d ( x j ，a 。) 和d ( x j ，a 。) 分别为节点x j 与节点a k 、节点x j 与节点x i 之间的距离函 数，即 m d ( x j , a k 沪) = 怯x ，j 圳- - a k x i12 p 2 2 ， d ( x j ，x j ) = 慨一 假定每个国廊n ( o ，仃肛2 ) ，且缈n ( o ，仃。2 ) ，其中n ( 0 ，万2 ) 是均值为0 ，方差为盯2 的正态分布，它们之间是相互独立的。使用所有的距离测量信息，得到估计值x 的最 大似然函数p ，如下： p ( ( 呶，( ，尼) m ；嘭，( ，f ) m ，x ) = m ；飘k ) e n o 击2 z 唧卜去c 颤卅( x j a ) ) 2j p 2 3 ， j 童j ， i 6 浓u 承 川如i 力- i 。以磊1 2 z 1 7e 卟一去( 妒嘶a i ) ) 2j ，7 ；( ，z ) 以 2 仃 二o ，f 那么其最大似然估计为： x 。l2a r gm x a x p ( ( d j ，( ，j j ) 虬；哆，( ，f ) 虬) ，x )( 3 2 4 ) 尽管该问题是一个非凸的问题，但是可以松弛为半定规划： 其中，有 衄n m 如朋e 虬去+ z j , i ；( j , o 。g 巧1 白 o j 文l 心。孑j k _ f丁j 1 s ( 一办；1 ) r d j ；( 一乃一) = 勺，v ( j ，f ) 札 ( 一办；1 ) 7 。d j k ( 一如；1 ) = ，v ( j ，七) 口 ( o ；e j e i ) 7 、z ( o ；e j e i ) = d j iv ( j ，f ) 札 ( a k ；一e j ) ，z ( a k ；一e j ) = 办2 ，v ( j ，尼) m d j i = o ，v ( j ，f ) n d j k = 0 ，v ( j ，尼) m i1 d 。= f 尹h ， i 1 d j t2 k z - = 0 舅 ，、 甜爻姝n x u l k 、 v ( j ，k ) 圯 另种最小化估计误差的表达式为： r a i n ，。；。，。，。 i 占2 ，r ，+ ，；。，。2 ， _ 一jpf ，t l ； ， ，一 盯j i x i - - x i 卜办2 = 勺，v ( ，z ) 札 ix j - - x k 卜吆2 = ，v ( 圳m f 3 2 7 ) f 3 2 s ) r 3 2 9 ) k ，、 = z 、ji，一、 那么目标函数可等价表示为： 如果假定慨一x ；l 卜嘭，且恢- - a k 忙呶，那么目标函数又可等价表示为： d 2 ( | | 】【j - x i 卜哆7 ) 2 + d 2 业( 忙- - a k 卜办) 2 ( 3 3 1 ) ，z ；【j ，7 ) e n r，7 ：( j ，k ) e n a 与式( 3 2 6 ) 中目标函数比较，可以发现，如果有o j ，= 1 1 以，和o j k = 1 c k ，那么该问 题实际上就是一个最大似然估计问题，其解也完全相同。因此，称式( 3 3 1 ) p - j 题为加权 最大似然估计。 那么上式的s d p 松弛为： m i n口 s f ( o ；e j e i ) 1z ( o ；e j e i ) 一哆，2 = 勺，v ( j ，i ) m ( 口女；一e j ) 。z ( a ；一e j ) 一d j k 2 = 啄，v ( j ，k ) 。 ( 3 3 2 ) ( ( f ，) 以占2 ，+ ( j 。虬占2 以) 经口 z - = 0 该问题仅仅是多了一个关于口的二阶锥约束，其它与前面介绍的s d p 松弛技术无 异，解决起来也一样简单。 如果距离测量值是精确的，那么传感网络能被唯一地定位。 3 3 3s d p 模型的两种松弛技术 为了得到一个近似解基于s d p 算法的计算复杂度至少为o ( n 3 ) ，其中t l 是未知节 点的个数。那么随着网络规模的增大，s d p 问题的规模也随之增加，矩阵锥的维数也 随之增加，并且未知变量的数量也以二次方的速度增长。为了减少计算负担，一个可 供选择的方法是进一步松弛基于测距的定位问题。在文献 2 4 中，提出了基于节点的 s d p 松弛即n s d p 和基于边的s d p 松弛技术即e s d p 。 n s d p 松弛： r a i n0 z n z ( 1 ：2 ) ( 1 = 2 ) 2 1 2 ( o ；e i - e j ) ( o ；e i e j ) 1 z = d 2 ，v ( i ，) 以 ( 3 3 3 ) ( - a k ；e i ) ( 一a k ；e i ) 。z = d 2 聃，v ( i ，k ) m z 1 = z ( 1 ，2 i ，n i ) ( 1 2 ，i ，n ；) - = o ，v f 其中与传感器节点i 有关联的节点集为 0 0 铲 r d j 办卜 i | _ k 墨 一 一 、 l 降卅 ， d 哆+ + i _ = 叫 i 川 x x 一 一，l降 利一 坂 匹 西南交通大学硕士研究生学位论文 第3 1 页 ii-f1 m = ：( i ，j ) m ) ( 3 3 4 ) 显然，此处( 2 + 刀) 维矩阵z 由船个小规模的3 + i f l 维矩阵锥来代替，其中每个小矩 阵都是矩阵z 的主子矩阵。 e s d p 松弛： r a i n0 z 肚z ( 1 ：2 ) ( 1 ：2 ) 。1 2 ( 0 ；e i e j ) ( o ；e i e j ) r z = d 2 , j , v ( i ，) 虬 ( 3 3 s ) ( - a k ；e i ) ( 一a k ；e i ) 丁z = d 2 i kv ( i ，七) m z ( 1 ，2 ，i ，j ) ( 1 ，2 ，i ，j ) - = 0 ，v ( i ，j ) n x 此处( 2 + 船) 维矩阵z 由l m l 个更小规模的4 维矩阵锥代替。显然每一个4 维矩阵也 都是矩阵z 的主子矩阵。 3 3 4 无需测距的s d p 定位模型 基于测距的定位需要已知距离测量信息或者是角度测量信息，常见测距技术有 r s s i 、t o a 、t d o a 、a o a 等。然而，这些测距技术严重地受到环境干扰，很大程度 上减少了测距精度，最终导致了较低的定位精度。与基于测距的定位方法相比，无需 测距的定位算法因其不需要额外的昂贵的硬件进行测距，代价比较低，而更加受欢迎。 无需测距的定位问题是一个单位圆盘图坐标实现问题的推广，本质上是一个带有二次 不等式的可行的问题，是一个n p 困难问题。尽管无需测距的定位与基于测距的定位相 比只能提供粗粒度的定位估计，然而，无需测距的定位方法的精度对于一些应用是足 够的，如基于位置的路由。 针对无需测距的定位问题提出了好几种方法，这些方法可以分为两类。第一类包 括质心算法、d v - h o p 算法、a p i t 方法和m d s m a p 方法。这类算法并不是通过求解 或者近似可行问题来估计每个节点的位置。在这些算法中，m d s m a p 方法在网络连 通度水平高而锚节点数量不多时性能最好。而质心算法、d v - h o p 方法和a p i t 方法只 有当网络中锚节点密度比较大时性能较好。然而，m d s m a p 并不适合于不规则的网 络定位。近来，o e o g e t t i 提出了针对低连通性的不规则的小规模网络的基于神经网络( 自 组织图，s o m ) 的方法。该方法也属于第一类。 无需测距定位方法的第二类是基于凸松弛的技术。这类算法通过近似n p 难的可行 性问题实现定位。 2 0 0 2 年，通过利用凸接近限制，d o h e r t y 将定位问题规划为一个凸优化问题，其能 利用s d p 或者s o c p 有效地求解。然而，该算法并没有考虑边界约束，边界约束在阻 止估计节点向中心聚拢上起到了很大的作用。因此，只有当锚节点部署在网络的边缘 西南交通大学硕士研究生学位论文筻3 2 页 时才能得到较好的定位结果。在文献 2 5 中，提出了s d p 方法近似可行性问题。为了 说明边界约束的作用并减少这种约束关于计算复杂性的影响，作者用一个分散最大化 的目标函数取代这些约束。算法描述如下： 假定w s a n 网络是在二维空间即r 2 ，共有m 个锚节点和胛个未知节点。锚节点的 位置坐标表示为a 。，k = 1 ，2 ，m ，未知节点的位置坐标表示为b j ，j = 1 ，2 ，胛。对于 任意一对未知节点b ；和b ；，若它们彼此能直接通信，那它们之间存在一个邻近约束， 这些所有约束的集合用。表示，同样地，锚节点a 。与未知节点b ；之间的约束集用虬表 示，即： 那么无需测距的w s a n 节点定位问题就可以描述为：找到一组x ，x ：，x 。r 2 ， 满足式( 3 - 3 7 ) 和式( 3 - 3 8 ) ，如下： 1 b j - b ；，v ( 叭 鲫1 i i b j a k 忙r ，v ( ，后) n o 。 ”b ；i i r ，v ( j ，啦m 隆3 8 ) l l b j - a k l l r ，v ( ，k ) 诺n o 、。 显然，传感网络的无需测距的定位问题是一个非凸的问题，但是可以通过凸松弛 技术如s d p 松弛近似地求解。 令a = a la 2 a 。 r 2 ，b = x 1x 2 x n 月2 “，且令x = ab r 2 ，其中 n = m + 胛，定义矩阵y 如下： y = x t x fa t aa t b1 一 ( 3 3 9 ) ib t ab t bj 0 = il = 那么，基于s d p 松弛技术，可以得到传感网络的无需测距的定位问题，如下： f i n dy r 。 s f y l ：m 1 ：。= a 1 a ( e 。+ i e m + j ) 2v ( e 。+ i e 。+ j ) r 2 ，v ( i ，) 6 ( e 。“一e t ) 2y ( e 。+ i e 女) r z , v ( i ，k ) 。 ( 3 4 0 ) ( e m + i e m + j ) 。y ( e 。+ i e 。+ j ) r 2 ，v ( f ，) 诺6 ( e m + i e 女) 7y ( e 。+ i e t ) r 2 ，v ( i ，k ) 诺n o y - = 0 利用内点算法上式半定规划定位模型能得到求解，然而，它最差情况下的复杂度 为o ( n 6 、，并且共有多于”2 2 个约束，这导致了相当大的计算量。尤其是边界约束的 劬 o 0 聆 一 一 j、， m 玎 一 - = 0 此时，式( 3 4 3 ) 的邻近约束通常为o ( n ) ，那么其计算复杂度为d ( 船3 ) 。此外，若传 感网络中没有有效的锚节点，那么可以直接将关于锚节点的约束去除，也可得到未知 节点的相对定位。 3 3 5 仿真与性能分析 本节中，我们在m a t l a b 2 0 1 0 b 环境中应用s e d u m i 优化工具箱对基于s d p 的相 关定位算法进行仿真，验证算法的有效性，并对相关仿真结果进行分析。 仿真实验 图3 8 所示的网络中有3 个锚节点，5 0 个未知节点，其坐标均随机产生，在不同 的通信半径情况下，利用基于测距的s d p 定位算法求解，定位结果如图3 8 所示：其 中( a h d ) 的定位精度分别为7 0 8 3 r ，9 8 0 r ，2 6 4 r ，1 5 5 9 8 e 0 4 r 。显然，随着 通信半径r 的增大，可以得到更多的定位约束条件，从而定位误差越来越小。当通信 半径增大到一定程度，如本次试验中通信半径为0 3 5 时，定位误差几乎为零，几乎可 以实现精确定位。图中锚节点位置坐标用黑色口表示，未知节点的真实位置坐标用红 色的o 表示，通过算法仿真得到的未知节点的估计坐标值用蓝色星号木表示，未知节点 真实值指向估计值的黑色的线表示两者之间的偏差，即两节点之间的定位误差值。 西南交通大学硕士研究生学位论文 篁3 4 页 c a ) r = 0 2 ：r 孓丁_ 一 o 9 | - - t 一一- 一t _ o8 。? j 一j 。j 审? 。? p：n： 。7e叠一r一06 一 - 幸 一j ：- + 羊- _ - 口一 耋。 i ：蔓蔓一j 一j 一i 一i 一i 。曼。! 。l 1 一l 一! 上曼；一i - o o- o - ；一。一。j 一j 。；一：曼；i ? 一；：- ：k 0 2 l ；。一；一：i ：- 上0 一 一；一 j 一! ：一；一一- ：， o l l l l l 生_ l _ 上j = 二圭- 。、 hn j - - 。一 。 口。 i 二 7 o 冀 口 ， 业r ( b ) r = 0 2 5 t l t , ri 。口。 。 一 0 i 一 。!k 一o ： $ ：。 ( c ) r = 0 3( d ) r = 0 3 5 图3 - 8 理想场景下基于测距的s d p 定位情况对比 锚节点位置不同时，对有测距误差情况下的仿真。锚节点个数为4 个，分别部署 在网络内部和网络边缘，未知节点个数为5 0 ，定位精度分别为2 3 0 9 r 、6 7 6 r ，仿 真结果如图3 - 9 所示。 ， 娥， l 。 屯 毒譬 节 气， l i 。t 。 j _ j 0 ： 一拿 ：， 苎 毫 恕 j ： 一量呻 。一矿 r h 、” j ， 蛩k ( a ) 锚节点部署在网络内部( b ) 锚节点部署在网络边缘 图3 - 9 通信半径r = 0 3n 卢o 1 图3 1 0 所示的网络中锚节点个数为7 ，未知节点个数为5 0 ，n f = - 0 1 时，不同r 情 况下定位算法仿真，结果如图3 1 0 所示。其中定位精度分别为6 3 0 2 r 、1 3 7 r 。 一一亘越大学硕士研究生学位论文 笛3 5 面i - - f l 7口 一 *h 盎! 忒。 、 夕列氏 三i 厶i i & 一 r 9 ；j 4 4 i r p z = 【7 ： l 。：， l 1口 磕i毒 。孓 e l_-】$ ，j _ 一 ：口 一 _ 鼹 i臻 ， 、 7 1 氰： 。l i 矿 ? 7 ，in ( a ) r = 0 2c o ) r = 0 3 图3 1 0n f = - o 。1 时不同r 定位结果对比 图3 1 1 所示传感网络中，锚节点为1 0 个，未知节点为9 0 个，节点通信半径为o 3 ， ( a ) 所示为只考虑节点连通性约束的情况下的定位结果，( b ) 为也有边界约束无需测距的 定位结果，它们的定位精度分别为7 8 6 3 r 、1 0 0 2 r 。从仿真结果可以看出，考虑了 边界约束之后无需测距方法的定位性能大为改善。 o n l yt h ec o n n e c t n k t yc o n s t r a i m t r a n g e _ f t e es d pl o c a l i z a t i o n 灏 囊_ 伊l 一 巷 鼍 等毡 0 矿：z ! - 黥：0 口鬻奄z 掣 矿墓 艴 ， & 蔓舟免 妒叼 、l 毒+ 口 ：? l i d ，矿 ( a )( b ) 图3 - i1 理想场景下定位结果 图3 1 2 所示为通信半径对基于测距与无需测距的s d p 定位算法的影响。网络中共 有5 0 个未知节点，3 个锚节点，通信半径分别为o 2 ，0 2 2 5 ，0 2 5 ，0 2 7 5 ，0 3 ，仿真 结果如图所示。从图中可以看出，无需测距的s d p 定位算法在不同通信半径下定位精 度都很差；且随着通信半径的增大，基于测距的s d p 定位算法的定位精度变化率比无 需测距的s d p 更快更明显，即基于测距的s d p 定位算法受通信半径的影响更明显。在 不同的通信半径情况下，对于无需测距的s d p 定位问题，考虑了边界约束( b o u n d i n g a w a y ) 之后，其定位精度明显提高，并且在较低的连通度水平( 即通信半径比较小) 情况 时，考虑了边界约束的无需测距的s d p 定位算法的定位精度比基于测距的s d p 算法精 度更高。因此对于连通度比较低且对实时性要求不高的w s a n 网络，可以利用考虑了 边界约束的无需测距的s d p 定位方法求解节点定位问题。 岔 邑 u j 越 骝 越 裂 l l _ 扣s d pr a n g e - b a s e d 【、 弋j _ 一s d pr a n g e - f r e e 卅卜s d pr a n g e - f r e e + b o u n d i n ga w a y 。 l 卜逛 呤 b “。j j 、j _ j v、 岔 零 肖 型 粱 堪 删 1 0 0 6 0 3r 一7 8 9 1 0 锚节点个数 图3 1 3 锚节点个数对s d p 定位方法的影响 一 西南交通大学硕士研究生学位论文 筻3 7 页 计算复杂度分析 根据文献的分析可知，采用内点法解决网络规模为胛个节点的传感网络定位问题 的计算复杂度为o ( n 3 ) 。而边界约束的个数一般为o ( n 2 ) ，那么考虑边界约束的s d p 定 位方法的计算复杂度为0 ( t 7 6 ) ，因此考虑边界约束的定位方法其运行时间远远多于其他 方法，这一结论也可以从表3 2 得出。表3 2 所示为在i n t e lc o r e2 0 0 g h zc p u ，1 9 9 g 内存的p c 上无需测距和基于测距的s d p 定位方法在不同网络规模情况时的运行时间。 表3 - 2s