（信息与通信工程专业论文）基于移动传感器网络的分布式节能目标跟踪研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 本文研究基于移动无线传感器网络的目标跟踪问题，即利用传感器节点的感知、通信、 计算和运动特性，对被探测区域内的未知运动目标进行连续跟踪。 移动无线传感器网络是由大量可移动的传感器节点所组成的无线网络。它最显著的特 点是节点资源有限，且抗毁性能很差。因此节能和分布式是必须考虑的因素。课题目的是 提出一种分布式自主目标跟踪方案，在各种复杂环境下( 如噪声、障碍物、扩散目标、多目 标等) ，对目标保证高跟踪精度的同时，尽量最小化节点运动能耗，并且优化网络配置，包 括始终保持网络连通、避免节点间以及节点与障碍物间发生碰撞等。 本文分三个部分解决以上问题。第一部分研究在理想状态下节能跟踪所能达到的最优 效果。首先证明节能跟踪问题的n p 完全特性，然后提出一种类似贪心算法的局部中心式 引导跟随算法，并且证明该算法的节点运动能耗在数值上逼近最小能耗，将其作为节能评 价的标准。第二部分研究更具实际意义的分布式节能跟踪算法。首先建立分布式系统模型， 规划节点间的信息交换机制，使得每时刻仅有少数节点处于活跃状态，自主运动来跟踪目 标，其它节点均保持空闲。然后给出活跃节点的运动策略，包括三个模块： ) 跟踪质量函 数反映网络的跟踪性能，圳连接势函数反映网络的连通状态，捌分布式节能运动策略。第 三部分考虑该分布式算法在复杂环境中的应用，将各种环境因素融入到算法的统一框架 中，包括在噪声探测模型、扩展目标和多目标环境中重新定义跟踪质量函数，在障碍物环 境中将障碍物作为虚拟邻节点加入连接势函数等。 本文的主要贡献可分为四个方面。首先，首次提出将节点运动节能作为移动传感器网 络跟踪的设计重点，而目前的移动传感器网络跟踪研究一般都只把跟踪性能作为唯一指 标。其次，首次提出将跟踪性能和各种跟踪约束( 包括节能、网络连通、避撞等) 用目标函 数量化表示，使跟踪问题可转化为经典的数学问题多目标优化问题。第三，提出了一 种完全分布式的跟踪算法，即每个节点仅依靠其邻节点信息决定自身控制输入，不存在任 何动态中心节点，所有节点地位平等，提高了系统的灵活性和鲁棒性。第四，建立了一个 全面的跟踪方案框架，适用于包括异构网络、噪声探测、障碍物、扩散目标、多目标等各 种复杂环境，不需要特别针对某种应用环境开发新的跟踪算法，具有良好的可扩展性。 主题词：移动无线传感器网络目标跟踪分布式n p 完全网络连通多目标优化 第i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t 1 1 1 i sd i s s e r t a t i o ns t u d i e st h ep r o b l e mo ft a 唱e t 仃a c l 【i i 玛u s i i 培m o b i l es e 吣o r 撒i t 、v or ：l 【s i t f o c u s e s0 n 吣m gt h ec 印a b i l i t i e so f n s i n g ，c 0 删叭面c 撕o na n dl o c o m o 吐o no f n s 0 rn o d e st 0 k e e p 仃a c l 【i i 培眦l l 【i l o 、 r i ll i l o b i l et a 唱e t s 、 ，i t l l i i l 血e 璐访ga r e 扎 an 1 0 b i l es e n s o r1 1 e t w o r ki saw i r e l e s s t 、v o r kc o n l p r i s i i l ga1 a 唱em m 慨ro fm o b i l es e n s o r n o d e s t h e n o d e sa r ea l w a y s1 0 w - p o w e r 锄dd e s 仇j c t i b l e s o 朗e r g ys a v i l l g 锄dd i 妤b u t e d c o m p u t a t i o n 玳t l l em o s ti l n p o r t a n tf i a c t o r si n 血e 衄c k i n gd e s i g n t l l i sd i s r t a t i o np r o p o s e sa m u yd i s t r i b u t e da l g o r i t l l mf o rt a r g e t 位l c l 【i n gu 瓜i i 玎c o i n p l i c a t e de n v i | - 0 m m n t 蚰c h 勰n o i 盯 s e 衄i n g ，o b s t a c l e ，d i m l s e dt a 玛e t ，e t c i t 仃i e st 0m a i l l t a i l lm et a 唱e t sb e i n gv i s i b l et o 圮m t 、) 1 7 0 r k a l lt h et i i l l ew i l i l ec o n s u r l l i n g 嬲l i t t l ei i l o t i o ne n e r g y 弱p o s s i b l e m e a r m 栖1 e l e 玳瓜o r k c o 衄e “v 时i sr n a i n t a i n e d ，n o d ec o l l i s i o ni sa v o i d e d ，e t c t 1 1 i sd i s s e r t a t i o n 、v o r ki sc o m p o s e do ft l l r e ep a r t s f i r 鸭w 1 1 i l em i i l i m i z i i 唱1 e 仃a c l ( i n g e n e r g yc o n s m n m i o nd u 血l gt 1 1 e 仃a c l 【i n gp r o c e s si sp r 0 v e dt ob en p - c o r n p l e t c ，姐印p r o 姒m a t e l y o p t i m a ls o l 面0 ni l a m e d b r e a d m f i r s tl e a d e 卜f o l l o w e ra l g o r i m mi sp r e s e n t e d i to i l l yc a i lb e r e a j i z e di i lal o c a l l yc e r l 仃诅i z e dm a n n e r w ep r o v et l l a ti t sc o i l s u m 讲i o ni s 埘m i i las c a l a rf a c t o r o f 让屺o p t i i n a lc o n s 唧p t i o n s e c o i l d ，、d 铋l 、i mt l l ed i s t r 伯u t e d 仃a c 虹n gp r o b l e mw i l i c hi s m o r ep r t i c a li i lr e 甜姆t h es y s t e mr n o d e l i i l gi s tu p 锄dt h ed a t a 位m s r n j s s i o ni ss c h e d m e d c a r e 如l l ys om a t0 1 1 l yaf e wi l o d e sa r ea c t i v a t e dw i l i l e o l e ri l o d e sk e e pi d l e t h e nai i l o t i o n 蚰例g yf o ra c t i v en o d e si sp r o p o 辩dw i l i c hi sm a d eu po fm r e ei n o d u l e s ：砂l e 仃a c l 【i n gq l l a l i 够 血n c t i o nw 1 1 i c hr e n e c t st h e 仃l d i 唱a c c u r a c y ，砂t 1 1 ep o t e n t i a l 胁c t i o nw h j c hr e n e c t sm e n e t w o r kc o m l e c t i v 时s t a t u s ，f 矽廿l ed i s t r i b u t e de n e r g ys a v i i l gn l o t i o n 蛐r a t e g y t 1 1 i r d ，l i s a l g o r i t l l mi se 】( t e r l d e dt 0c o i n p l i c a t e de r i r o r 吼e n t v a r i o u se r 的砌e m a lf k t o r sa r ea d d e dt 0 也e 嘶f o 皿仃a c l 【i n g 五e w o r k f o re x 砒n p l e ，w ei i n p r o v e 廿l e 仃a c l 【i i l gq u a l i 够劬c t i o nf o r l e n o i s ys e n s i i 培i n o d e l ，d i f m s e dt a 玛e ta n dn m l t i - t a r g e t a l s ot 1 1 eo b s t a c l ei sc o i l s i d e r e d 雒v i n u a l n e i g h b o r i n gn o d e s i nt 1 1 ep o t e n t i a l 缸t i o n t h em j o rc o i 确b u t i o no f “sd i s s en _ a t i o nl i e si i lf o u ra s p e c t s f i r s t ，i ti sm ef i r s t 、o r kt l l a t f o c u s e so n 也ee n e r g ys a v i l l gp r o b l e m 洫t a 唱e t 仃a c l ( i i 坞，w l l i l em o s te x i s t i n g 、) v o f i ( sm i i 唱r i l o b i l e n c 帅o r ko i d yl 砌tt l l e i rp r o b l e m so ni r l l p r o v m gt l l e 仃a c l ( i n ga c c u r a c y s e c o n d ，c e n a mo b j e c t i v e 缸l c t i o n sa r ed e f i n e dt 0q l 姗t i 匆t h em 血r e q u i r e m e n t sa n dc o m 触ss u c h 雒t i l e 缸a c 幽g q u a l i 够，t l l en e t 、0 r kc o n n e c t i v 时s t 咖sa n dm ec o l l i s i o na v o i d a 皿c e t h e y 眦l s f o mt l l e 仃a c m g i n t oac l a s s i c a lm u l t i - o b j e c t i v eo p t i 耐z a t i o np r o b l e m t 1 1 i r d ，m eo p t i 血z a t i o na l g o r i t l u l li sm l l y 第i i 页 国防科学技术大学研究生院博士学位论文 d i s 虹i b u ：t e d n oc 肌缸a l l z e dp r o c e s ro rd y m 咖cc e 加眦册l s1 w e u 蹦儿i l u 婀矾d “ 锄er 0 l e 。w h i c hm a k e s 血e 科s t 锄m o f o b u s ta n df l 耐b l e f o u r 电ag e 眦r a l 缸a c k m g 鼬e w o r ki ss e tu p i t 啪b e 哪l i e dt 0m a n yc o m p l i 咖e ds h 撕。璐呲h 嬲也ch c t c m g e n e 0 璐 n e t w o r k i s y 璐i i l g ，d i m 哟dt a r - g e t o b s t a c l e ，e t c w en e e dn o t t od e s i 印as p e c l a la j g o n t l l i n f o r 鼬a r p p l i c a ：c ：i o 如w h i c hm e a 璐o l l ra l g o r i t i 皿t 脚9 0 0 de x p 锄i b i l i 锣 k e yw b r d s ：m o b i i es e n s o rn e t v v o 水 t a r g e tt r a c k i n g d i s t r b u 制n p - m p i e t e n e t w o r i ( c 0 n n e c t i v 时 m u 嘶一o b j e c t i v eo p t i m 亿a “o n 国防科学技术大学研究生院博士学位论文 表目录 表2 1文中所使用的主要变量符号。1 6 表2 2b f s 搜索流程2 0 表4 1 仿真器部分代码6 7 第1 v 页 国防科学技术大学研究生院博士学位论文 图1 2 图2 1 图2 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 1 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 1 7 图4 1 8 图目录 本文主要工作示意图。9 几种邻近图定义l7 各邻近图拓扑比较1 8 理想环境下移动传感器网络的目标跟踪原理2 8 中心式目标跟踪系统框图2 9 节点分类方法描述3 5 b l f 算法节点运动策略3 6 b l f 算法执行流程3 7 b l f 算法与最优解的节点覆盖关系3 9 不同状态转移噪声方差i w i 时的运行结果4 2 不同状态转移噪声方差( a ) 和不同节点密度( b ) 时的网络能耗4 3 不同b f s 搜索基本图时的网络能耗4 4 不同时的网络能耗( 宽度优先搜索基本图分别为i 矾g ( a ) 和u d g ( b ) ) 。4 5 基于移动传感器网络的分布式跟踪系统框图4 8 节点状态切换流程4 9 分布式节能目标跟踪算法51 间距函数及其导数函数曲线示意图5 3 函数及其导数5 4 节点运动方向示意图5 6 连接势函数优化网络布局5 6 流体力学质量守恒定律的物理意义5 8 节点，以外的其他节点探测区域与节点，的探测区域相交5 8 网络覆盖区域分割及分割区域边界外向法线5 9 节点运动方向随节点位置变化的规律6 2 两种一维搜索算法的能耗比较6 5 分布式节点运动策略原理。6 5 事件调度器工作过程6 6 算法仿真运行截图6 9 分布式算法与中心式算法的跟踪性能比较7 0 取不同值时的跟踪性能7 0 r 眦取不同值时的跟踪性能7 1 第v 页 国防科学技术大学研究生院博士学位论文 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 l 图5 1 2 图5 1 3 图5 1 4 角度传感器示意图7 6 噪声探测模型下的跟踪质量函数求偏导流程7 8 取不同值时的网络跟踪性能8 0 探测噪声方差i v i 取不同值时的网络跟踪性能。8 1 障碍物产生虚拟邻节点8 2 障碍物位于网络探测区域内时的跟踪截图8 4 障碍物位于网络探测区域边缘时的跟踪截图8 5 扩散目标跟踪8 6 气体源位于网络初始覆盖区域内部时的跟踪截图。9 0 气体源位于网络初始覆盖区域边缘时的跟踪截图9 l 气体源运动时的跟踪截图9 l 三种节点运动策略的性能比较9 2 多目标跟踪截图1 ( 目标轨迹交叉) 9 4 多目标跟踪截图2 ( 目标运动方向相反) 。9 5 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 学位论文作者签 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查蒯和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 司以采用影印，缩印或扫描等复制手段保存，汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 基士整动篮壁墨旦垒的佥盔盘笪6 巳旦盘避壁叠窒 学位论文作者签名： 作者指导教师签名： 崩茗 埤辎 日期：、卯辟奉月日 矾) 吼徘牛眵日 国防科学技术大学研究生院博士学位论文 第一章绪论 与传统的跟踪方法相比，无线传感器网络以其良好的特性弥补了传统跟踪方法的不 足，在军事和民用上都具有广泛的应用前景。而目前的静止无线传感器网络逐渐无法满足 复杂跟踪环境的需要。网络中节点的移动特性的引入，可以将静止无线传感器网络转化为 移动无线传感器网络，提高了网络的自主优化能力，扩展了网络跟踪的应用领域，同时也 带来了技术上的挑战。因此本文将针对基于移动无线传感器网络的分布式节能目标跟踪技 术做深入研究。 1 1 课题研究意义 1 1 1 基于无线传感器网络的目标跟踪 无线传感器网络( w 喃l e s ss e 珊0 rn 舐v o r kw s 【1 】是由大量功率低、体积小、价格便宜、 具有感知、计算与通信能力的微小传感器节点构成的“智能”自治网络系统，通常用来监视 一个特定的地理区域。近年来，集成电路、微机电系统以及无线通信的发展使生产和推广 这种传感器网络成为现实。网络中的每个节点独立地监测周围环境，然后相互协作实现复 杂的功能，譬如闯入检测、目标跟踪与定位、环境监测、遥感等。无线传感器网络最初出 现在军事应用中，目前已经广泛应用于农业、健康护理、环境监测、智能家居、物流监测 等方面，以及一些缺乏传统的基础网络设施( 如i n t 锄e t 、g p s 和移动通信网等) 支持的领域， 如地球物理学( 例如地震监测) 、军用系统、抢险救灾、生物学研究等。目前，无线传感器 网络已经成为机器人学和电子工程领域的一个重要研究方向。 在无线传感器网络的许多应用领域中，往往需要对监测区域中的特定物理目标进行跟 踪和定位。比如抢险救灾中，灾区中布置的传感器网能够追踪医护人员的位置；战争中军 队可以在阵地上布置传感器网，用于追踪无g p s 支持( 可能被破坏) 的士兵、车辆等的位置， 监测战场上敌方的兵力移动、核生化气体浓度以及野战区域内狙击手的火力等；在禁入地 区可以用来监测和追踪闯入者等。 传统的目标跟踪系统，如雷达系统，通常由少数有限的有源探测站点( 雷达) 以及数据 处理中心构成，各探测站点会配置较高处理能力的设备以及相对充足的资源，不断地把采 第l 页 国防科学技术大学研究生院博士学位论文 集的原始数据传送给处理中心或者某一个探测站点集中处理，然后返回指令给相关站点。 跟踪算法一般都采用单传感器或者多传感器中心式数据融合算法。 而无线传感器网络最显著的特点是网络由众多资源有限的节点组成，因此跟踪方案的 设计存在很多限制。首先，网络整体拓扑信息未知，每个节点仅能通过与其邻节点的相互 通信获得网络局部信息；其次，通常为了节能的目的，节点只能得到精度不高的探测结果， 但是又不存在强大的中心处理设备来负责信息融合、计算和协调工作，因为系统处理的数 据量会随着目标数、节点数呈几何级数增加，节点只能依靠局部信息自主决策，即跟踪必 须是分布式的：第三，单个节点的通信带宽、能量等资源有限，如果大量节点之间进行数 据传输会造成网络通信的沉重负担，太大的数据量也会使节点电源很快消耗殆尽。这些限 制使得传统的中心式多传感器跟踪算法不再适合，需要重新设计。 当目标在网络中移动时，由于节点的覆盖区域有限，离目标较远节点的探测数据对跟 踪效果贡献很小，所以只需让目标周围的少数活跃节点参与跟踪，其余节点则进入休眠状 态( 承担通信任务的节点除外) ，从而最大程度降低系统的整体能耗，延长网络寿命。所以 基于无线传感器网络的目标跟踪过程大致为：当前活跃节点自主监测环境事件，一旦特定 现象被探测到，节点就相互协作估计目标位置，并将处理结果通过网络送到监控用户终端， 然后节点根据估计值预测目标将要到达的区域，激活该区域内的节点参与跟踪，自身则置 为休眠状态，随后进入新的循环。 与传统的集中式目标跟踪系统相比，基于无线传感器网络的目标跟踪系统具有许多优 势，归纳起来，主要有以下几点： 跟踪更精细：密集部署的传感器节点可以对移动目标进行精确传感，跟踪和控制，从 而可以更详细的显示出移动目标的运动情况。 力跟踪更可靠：由于移动传感器网络的自治、自组织和高密度部署，当节点失效或新的 节点加入时，可以在恶劣的环境中自动配置与容错，使得无线传感器网络在跟踪目标时具 有较高的可靠性、容错性和鲁棒性。 刃跟踪更及时：多种传感器的同步监控，使得移动目标的发现更及时，也更容易。分布 式的数据处理、多传感器节点协同工作，使跟踪更加全面。 卅跟踪更隐蔽：由于传感器节点体积小，可以对目标实现更隐蔽的跟踪，同时也方便部 署应用。 影低功耗：传感器节点的设计和无线传感器网络的设计都以低功耗为主要目标，适用于 第2 页 国防科学技术大学研究生院博士学位论文 在野外等没有固定电源或更换电池不便的跟踪应用。 铆低成本：单个传感器节点的成本低，从而降低了整个跟踪的成本。 1 1 2 基于移动传感器网络的目标跟踪的优势与挑战 目前基于无线传感器网络的目标跟踪研究主要是针对静态节点，即静止无线传感器网 络，简称静止传感器网络( s t a t i cs e n s o rn e 铆o r k ，s s n ) 。但是由于节点的探测区域有限， 节点数目通常不足以覆盖整个监控区域，而目标运动轨迹又无法预知，不可能保证其始终 处于网络的有效监控下。另外无线传感器网络中各节点的配置较低，抗毁性能较差，如果 因损坏或者电池耗尽等引起节点失效，就会在监控区域中形成监控盲区。在这些情况下， 如果节点具有移动特性，可以根据实测数据自主运动到感兴趣的区域，那么整个网络就可 以随时优化到最佳状态，这就是移动无线传感器网络，简称移动传感器网络( m o b i l es e n s o r n e t w o r k ，m s n ) 。 移动传感器网络由安装在空间分布的机器人群或其他移动平台上的一系列传感器节 点组成，因此除了静止传感器网络节点的感知、计算和通信能力以外，移动传感器网络节 点还拥有移动功能，这是移动传感器网络区别于静止传感器网络的主要特征，所以相比较 而言，移动传感器网络具有更好的环境覆盖能力、更快速的变化反应能力以及更主动的信 息获取能力。移动传感器网络的出现为无线传感器领域引入了新的研究热点，比如最大化 网络覆盖区域、网络修复、自主定位与跟踪等。 图1 1基于移动传感器网络的目标跟踪系统示意图 第3 页 国防科学技术大学研究生院博士学位论文 将移动传感器网络应用在目标跟踪，过程大体与静止传感器网络相同，并且可以利用 节点的移动特性保持目标始终对网络可见。另外，由于资源受限的单个节点只能得到精度 不高的探测结果，也可以通过移动节点来减小节点与目标的问距，从而获取更精确的目标 信息。图1 1 是基于移动传感器网络的目标跟踪系统示意图，目标( 图中红色小车) 沿着预定 轨迹移动( 图中桔色曲线) 。假设节点的探测模型是简单的圆盘模型( 图中灰色区域) ，所有移 动节点都能通过本地广播来相互通信( 图中蓝色有向线段) 。前一系统时刻的跟踪节点为节 点彳，当目标沿着轨迹向前移动时，节点彳预测目标下一时刻可能出现的区域，并通知距 该区域最近的节点曰，完成任务移交。节点丑收到后通知其附近节点丑j 、即、b 3 ，向目 标区域靠拢( 图中灰色有向粗线段) 。当目标移动到该区域时，被节点b 川屎测到。节点曰收 集附近节点探测数据，进行简单融合后经过网络送往监控中心q 。随后进入新一轮循环， 跟踪任务按照彳一b c d 的顺序依次移交。 从图中看出，当目标在红色位置时，正好在节点b 、b j 、船和彤的探测区域之外， 如果是静止传感器网络，不会有任何节点探测到目标，这就意味着从该时刻起目标丢失。 因此在目标跟踪应用中，移动传感器网络比静止传感器网络更加有优势，但是同时也带来 了一些挑战，涉及到节点移动所带来的一系列问题。比如，跟踪中的节点运动规划，网络 动态调整引起的通信拓扑变化，节点运动对整个系统稳定性的影响等，其中对节点运动的 节能考虑尤为重要。 由于传感器节点都采用容量有限的电池供电，而要在几年内将目前的电池可供电时间 提高3 0 都是很困难的。一旦电池耗尽，节点失效后就会在监控区域内形成监控盲区。这 些失效节点往往难以更换，特别是当网络布置在无人区或危险区时，这样网络的覆盖范围、 寿命和实用性就会大大降低。因此，在设计跟踪方案时，节能是必须考虑的因素。相对于 感知、通信、计算等能耗，运动能耗占整个节点能耗的最大比重。显而易见，提高跟踪效 果和减少运动能耗是两个相互对立的因素，如何能二者兼顾，成为移动传感器网络目标跟 踪中的一个非常关键的问题。 总之，基于移动传感器网络的目标跟踪研究有很重要的理论和实用价值。本课题的主 要目的就是提出一种分布式节能目标跟踪方案，对目标保证高跟踪精度的同时，尽量最小 化节点运动能耗，并且优化网络资源配置，包括始终保持网络连通、避免节点间以及节点 与障碍物间发生碰撞等。 第4 页 国防科学技术大学研究生院博士学位论文 1 2 相关领域的研究现状 移动传感器网络本质上是静止传感器网络和多机器人系统相结合产生的新的研究热 点，而目标跟踪是无线传感器网络领域的经典研究方向。下面我们分别从静止传感器网络 目标跟踪、多机器人系统目标跟踪与移动传感器网络目标跟踪等三个方面介绍近十年来的 主要研究成果。 1 2 1 静止传感器网络目标跟踪 最早的无线传感器网络目标跟踪研究出现于上世纪九十年代末美国d 舢冲a ( d e f e n s e a d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 的s e n s i t 项目中。相对于移动传感器网络，基于静止传 感器网络的目标跟踪近年来受到了较多关注。 z h a 0 等人断】提出一种信息驱动节点查询( i n f 0 肌撕0 nd r i v e ns e n rq 鹏r ) r 迦，i d s q ) 机制，成为无线传感器网络跟踪研究中最具代表性的算法。i d s q 采用节点之间进行跟踪 任务传递的方式，主要思想是将目标跟踪转化为经典序列贝叶斯滤波( s e q u c n c i a lb a y e s f i l t e m 曲问题，并提出信息增益( 熵、m a h a l a n o b i s 距离、期望后验概率等) 的概念。每次仅 有一个节点跟踪目标，该节点融合目标历史信息与其探测值，估计目标状态，并将该信息 传递给使信息增益和信息传递能耗加权值最小的节点，作为新一轮的跟踪节点。 基于任务传递的思路，r a m a n a ：t 1 1 加和b r o o l 【s 等人r 7 9 】提出了局部中心理论，将网络动 态分割成地理单元格，每个单元格都有一个中心节点，负责收集周围节点的探测数据进行 目标估计，预测目标未来可能区域，将该区域附近的节点激活。这些节点利用特定的路由 应答协议构建动态单元格，并选取中心节点，随后进入新的跟踪循环。与i d s q 机制的不 同点在于，每次位于某个单元格内的所有节点都跟踪目标，而不仅仅单个节点。这里的数 据处理方式采用的是扩展卡尔曼滤波( e ) ( t e n d e dk a l m a nf i l t e r ，e k f ) 。m o o r e 等人建立了一 个真实的分布式目标跟踪系统，对该算法的有效性作了实际测试【1 0 】。 c h e n 【1 2 1 将网络中的所有节点事先分为两类，一类是配置较高的节点充当簇头，负责信 息收集和融合，另类低配置节点负责向其簇头提供探测数据。当多个簇头的探测信号强 度超过一定门限时，算法基于v o r o n o id i a g 阳m 理论，选择其中一个作为当前簇头，它激 活附近的低配置节点建立动态簇跟踪目标。簇头与簇内的成员节点间的信息交换必须遵循 一定机制，来避免冲突和拥塞。随着目标的移动，根据探测信号的强弱自动调整簇头，不 第5 页 国防科学技术大学研究生院博士学位论文 存在跟踪任务的传递问题。 z l m g 【1 3 】提出用动态护卫树( c o n v o yt r e e ) 的概念在当前根节点周围建立动态路由树， 使得附近节点的探测数据能顺利传回根节点。随着目标移动，通过自动添加删减树枝节点 或者重置根节点，来优化树的结构，在保证对目标覆盖率的同时最小化根节点与树枝节点 的数据传输能耗。 y a n g 等人【1 4 l 【1 习用线性模型预测节点位置，选择离预测位置最近的节点作为下一时刻 中心节点，附近三个节点作为从属探测节点，算法考虑了节能和目标丢失后的恢复问题。 a s l 锄【1 6 】采用二进制传感器节点，该节点仅能测得目标是否朝向节点运动，将探测值 结合节点自身位置，利用几何理论估计目标位置和运动方向。 从以上看出，基于传感器网络的目标跟踪算法主要采用跟踪任务传递的动态局部中心 方式：中心节点收集探测数据，采用某种数据融合算法更新并预测目标状态，激活预测目 标区域附近的节点。这些节点采用某种应答协议选择新的中心节点，完成跟踪任务移交。 上述跟踪算法基本上都是围绕数据融合算法或者应答协议的设计所展开的。 近年来基于传感器网络的多目标跟踪【1 7 j 逐渐成为热门研究方向，它最大的难点就是多 传感器的数据关联问题。经典多目标跟踪算法如多重假设( m u l t i p l eh y p o t l l e s i st r a c l 【i n g ， m h t ) 【1 8 】或者联合概率数据分类理论( j o i n tp r o b a b i l i s t i cd a t aa s s o c i a t i o n ，j p d a ) 【1 9 】等，所需 的计算量和存储量过高，不适用于资源受限的传感器网络节点。s 等人【2 0 】提出身份管理 的思想，用简单的身份确信度方阵来表示每个估计目标对应每个真实目标的可信度，根据 探测数据来不断更新方阵元素。类似的还有 2 l 】 2 2 】。y o e 2 3 】也采用分簇方式，着重考虑 了跟踪过程中的节能要求，将节能跟踪问题看作一个分层m a r k o v 决策过程，用动态规划 算法解决。算法在减小节点探测速率节省系统能耗的同时，仍保持了较高的跟踪精确度。 t o m 【2 4 1 提出一种分布式的s i g i 】胁p o 血信息滤波算法，证明了当非线性动态扰动影响较大 时，该算法具有很高的鲁棒性和精确度，且计算量不超过传统的e k f 算法。s o n g h w a i 【2 5 之8 】 提出一种多层组合优化算法m 破o vc 1 1 a i l lm o n t ec 州。数据关联( m c m c d a ) 算法，避 免了目标候选轨迹的累积，被看作是贝叶斯滤波的近似最优实现方案。另外还有c h e n 【2 9 】 提出的基于几何模型的目标跟踪算法等。 1 2 2 多机器人系统目标跟踪 无线传感器网络中节点数目众多，而且有效通信距离有限，每个节点只能与其邻节点 第6 页 国防科学技术大学研究生院博士学位论文 通信。而多机器入系统中每个机器人相当于一个节点，它的区别在于机器人数目较少，资 源配置充足，且通常假设每两个机器人之间可以随时通信。 p a 成c r 【3 m 3 3 1 首先证明最大化目标被至少一个机器人跟踪的时间是n p 1 砌问题，然后 提出一种双层的分布式在线运动控制策略。底层控制力由机器人与目标之间的势场产生， 高层控制采用a l l l n c e 机制，考虑了与其他机器人间的协作关系，作为底层控制力的 加权系数，共同控制机器人运动。 m a l ( a r c n k 0 和b e i l 等人【3 伯7 】提出一种基于信息滤波器( i n f o 】加a t i o nf i n c r ，i f ) 的分布式数 据融合算法，机器人间互相发送自身探测新息，每个机器人将其接收到的新息与已有的目 标信息累加，建立信息熵增益目标函数，求出最优控制输入。 c h m g 等人【3 删用目标状态估计误差的方差矩阵绝对值作为目标函数，利用矩阵理论 中的链式求导法则设计分布式运动策略。使得目标函数沿该方向下降最快。算法还在目标 函数中加入机器人运动对网络通信质量的影响，取得提高跟踪精度和保证通信质量二者之 间的折衷最优效果。 类似地还有，s p l e t z e 一1 l 【4 2 1 预估节点位于候选区域时的探测值，结合目标的先验知识， 建立探测期望误差的面积分作为目标函数。 j u n g 【4 3 舶1 采用一种非常简单的区域跟踪方式，根据区域内目标密度和未发现目标的存 在概率分配机器人位置。 可以看出，基于多机器人系统的目标跟踪设计比传感器网络少了很多约束。比如机器 人能量相对不受限，所有机器人均处于活跃状态，随时跟踪目标，不需要采用跟踪任务传 递的方式；机器人之间可以随时相互通信，不需要设计专门的路由机制传递信息等。 1 2 3 移动传感器网络目标跟踪 基于移动传感器网络的目标跟踪系统融合了静止传感器网络和多机器人系统跟踪的 优点，具有很好的前景和未来。但是它作为一个较新的研究方向，目前的相关研究较少， 笔者仅发现以下几个文献。 s h u c k e r 等人h 9 】将网络抽象为一个虚拟弹性网格图，目标自身也被当作一个虚拟节 点，考虑了有限通信距离，网络在跟踪过程中保持连通。算法是分布式的，节点处的目标 浓度决定了该节点邻边的理想长度，浓度越高，该长度越大。节点与其邻节点协同运动， 使邻边逐渐趋向理想长度。该算法存在一个明显的缺点，当目标对网络不完全可见( 比如目 第7 页 国防科学技术大学研究生院博士学位论文 标位于网络覆盖区域边缘) 时，目标区域某些地方不存在节点，节点无法通过调整邻边长度 来覆盖目标。解决办法是对靠近未覆盖区域的节点施加额外作用力，将网络拉向该区域。 但是这样做无疑降低了系统的整体性和稳定性。另外算法假设网络始终可以获知目标准确 位置，这也是不实际的。 c o r t e s 【5 m 5 3 】将跟踪问题转化为在网络有效覆盖区域上对目标浓度的面积分的优化问 题。算法基于邻近图和v o r o n o i 分割理论，将该多目标全局优化问题转化为节点v o r o n o i 网 格与节点有效探测区域的交叉区域上的局部优化问题。然后利用梯度下降法将积分函数上 升最快的方向作为节点运动方向，最后从控制论角度证明了算法稳定性。该算法是完全分 布式的。其不足在于需要事先知道准确的目标浓度分布，且只适用于静止目标。 z o u 【5 4 】综合考虑了节点运动对目标跟踪性能的提高以及伴随而来的负面效果，包括能 耗、节点连接中断、覆盖面积损失等，建立一个简单的加权目标函数。该研究与本课题有 定相似之处，但是节点只能在几个有限的候选位置中做出选择，运动不连续。另外，该 算法并不是分布式的，并且未说明具体的网络信息交换机制。 另外还有一类研究，事先预测目标可能经过的区域，在该区域布设节点，防止目标逃 脱。目的是规划一个花费小且目标运动全程覆盖率高的节点布设方法，其本质上是一个传 感器网络覆盖的非自主优化问题，即节点一旦布设好，就不能改动，因此不属于本课题所 讨论的范畴。具体可参见文献【5 5 5 7 】。 从以上讨论看出，与静止传感器网络跟踪相比，基于移动传感器网络的目标跟踪虽然 具有很多优势，但目前的研究还远不够成熟，本课题就是在这样的背景下提出的。 1 3 本文主要工作和贡献 本文结合“国家8 6 3 项目 和“国家自然科学基金 等项目，研究了基于移动传感器 网络的目标跟踪问题，即利用移动传感器节点的感知、通信和运动特性，对被探测区域内 的未知机动目标进行连续跟踪。课题目的是提出一种有效的分布式自主目标跟踪方案，在 复杂环境下( 如噪声探测、障碍物、扩散目标、多目标等) ，对机动目标保证高跟踪精度的 同时，尽量最小化节点运动能耗，并且优化网络资源配置，包括始终保持网络连通、避免 节点间以及节点与障碍物间发生碰撞等。 主要工作如图1 2 所示。首先研究了在理想环境下的节能跟踪所能达到的最优效果， 第8 页 国防科学技术大学研究生院博士学位论文 并提出相应的局部中心式算法实现，在此基础上研究理想探测模型下的分布式节能跟踪， 并将该分布式算法作进一步改进，应用到各种复杂环境中。 理想环境下的局部中心式节能目标跟踪 7 自l 7 5， 7 廿 。7 ，：弱节能最踪问题的数学定义髟； 算法的近似最优特性证明鬈。 。 分布式节能目标跟踪 ； 溺分布式跟踪系统模型髟 ； 分布式信忠传递机制 隧“ 活跃节点运动策略 i 网络连通势函数 l 里墅蝉皇墨_ i 1 分布武运动策略i 复杂环境下的分布武节能目标跟踪 t 二_ - - - - - - - - - - 7 ：镯噪声探测模型良 二j 澄遴筮塑缕绥豳， 7 ”习障碍物环境彦7 ：。鋈夏瑟耍垂l 。：翻 扩散日标 。习多目标 图1 2本文主要工作示意图 本文的主要贡献包括以下四个方面： 第一，首次将节点运动节能作为移动传感器网络跟踪的设计重点之一，即保证网络跟 踪目标的同时，尽量最小化节点的运动耗能。而目前的移动传感器网络跟踪研究一般都只 把跟踪性能作为唯一指标。本算法也同样适用于非节能考虑的应用。 第9 页 国防科学技术大学研究生院博士学位论文 第二，以往的跟踪研究多为自发形式，即机器人或者节点依靠实时探测数据逐渐调整 与目标的相对距离，使其趋近于理想值，来保持目标持续可见。本文首次提出将网络跟踪 性能和各种跟踪约束( 包括节能、网络连通、避撞等) 用明确的目标函数量化表示，使跟踪 问题可转化为经典的数学问题多目标优化问题。 第三，提出了一种完全分布式的跟踪算法，即每个节点仅依靠其邻节点信息决定自身 控制输入。而目前的无线传感器网络跟踪研究一般采用动态局部中心式机制，每次都会选 择目标附近的一个节点作为中心节点，负责数据收集和信息处理。本算法不存在中心节点， 所有节点地位平等，很大程度上提高了系统的灵活性和鲁棒性。 第四，建立了一个全面的跟踪方案框架，将各种环境因素融入目标函数的设计中，适 用于包括异构网络、噪声探测、障碍物、扩散目标、多目标等常见复杂环境，不需要特别 针对某种应用环境另外开发新的跟踪算法，算法具有良好的可扩展性。 1 4 论文结构安排 本文结构安排如下： 第一章绪论，首先讨论课题的研究背景和意义，介绍相关方面的研究现状。然后简单 概括本文的主要工作和贡献，最后给出本文的结构安排。 第二章作为后续章节的基础，给出节能跟踪问题的定义，以及文章中的主要符号、模 型、假设。另外介绍了图论和最优化理