（控制理论与控制工程专业论文）基于图模型的受限网络检测算法研究.pdf

s t u d y o nn e t w o r k - c o n s t r a i n e d d e t e c t i o n a l g o r i t h m b a s e do n g r a p h i c a l m o d e l c a n d i d a t e ：f a n gz h e n g s u p e r v i s o r ：p r o f w e nc h e n g l i n n o v e m b e r , 2 0 10 硼 14 7 杭州电子科技大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人 或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：务正 日期：谚，年月名日 学位论文使用授权说明 本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密论文 在解密后遵守此规定) 论文作者签名：呖五 指导教师签名 日期：2 , ot1 年f 月名日 日期：加年【月l 妒 杭州电子科技大学硕士学位论文 摘要 无线传感器网络作为微型化设备和无线通信相结合的产物，已在地理、生物、 监视、故障检测等科学领域和工程应用中得到了广泛的探索和研究。由于节点的 能量供应有限，能量约束问题的研究具有重要的理论意义和较高的应用价值。 图模型理论是概率论和图论密切结合的产物，为涉及到概率推论的问题提供 了有效的解决方法。本文通过引入图模型，有望改进检测算法，提高检测性能。 为此，本文开展了如下研究工作： ( 1 ) 推导了在p - b 中最优条件下的队决策方法。由于传统决策方法没有完全 考虑节点间的因果关系，以及队决策求解( t e a md e c i s i o ns o l u t i o n ) 方法的局限性， 给定一些模型假设，从最小化风险函数出发，按照贝叶斯公式和相关的图模型理 论方法，进行详细的推导。通过仿真分析了相关性和信噪比等参数对该算法的影 响，验证了其有效性。 ( 2 ) 建立基于信道模型的队决策方法。由于环境的复杂，信号在信道的传输 中会发生衰减或者产生各种偏差，对此建立信道模型，推导决策方法，从而扩展 了队决策方法的应用范围，并以机动目标跟踪为背景展开分析。 ( 3 ) 提出一种新的机动目标跟踪问题跟踪方法一 l k f 。该方法是基于全局 风险最小准则设计的，旨在提高机动目标的跟踪精度。通过求解残差的类条件概 率分布，计算得到残差的阈值，确定目标的运动模型以及发生机动的时刻，再运 用k a l m a n 滤波进行跟踪算法研究。最后通过仿真分析和性能对比，说明该方法 的有效性和优越性。 关键词：传感器网络，图模型，网络检测算法，队决策理论，机动目标跟踪 杭州电子科技大学硕士学位论文 a bs t r a c t t h ev i s i o no f w i r e l e s ss e n s o rn e t w o r k s i sac o n f l u e n c eo f e m e r g i n gt e c h n o l o g y i nb o t hm i n i a t u r i z e d & v i c e sa n dw i r e l e s sc o m m u n i c a t i o n s i ti so fg r o w i n gi n t e r e s ti n av a r i e t yo fs c i e n t i f i cf i e l d sa n de n g i n e e r i n ga p p l i c a t i o n se g ，g e o l o g y , b i o l o g y , s u r v e i l l a n c e ，f a u l t - m o n i t o r i n ga n d s oo n f o rt h er e a s o no fe a c hn o d e sf i n i t ep o w e r , t h ea n a l y s i sa n dr e s e a r c ho nt h e e n e r g yc o n s t r a i n t sh a v ei m p o r t a n tt h e o r e t i c a l m e a n i n ga n dh i g hp r a c t i c a lv a l u e g r a p h i c a lm o d e l ( g m ) i sam a r r i a g eb e t w e e np r o b a b i l i t yt h e o r ya n dg r a p h i c a l t h e o r y i tp r o v i d e ss o m ee f f e c t i v em e t h o d st os o l v ef o rp r o b a b i l i t yi n f e r e n c ep r o b l e m ，n l ct h e s i sa i m st oi m p r o v et h ep e r f o r m a n c eo fd e t e c t i o na l g o r i t h ma f t e ri m p o r t i n gt h e g m t h e r e f o r e ，t h i st h e s i sw i l lb ec a r r i e do u ta sf o l l o w s ： ( 1 ) d e r i v et h en o wt e a md e c i s i o nm e t h o d sb a s e do np e r s o n - b y - p e r s o n0 p t h l l a j 时 r u l e a r e ra n a l y s i s , w ec a ns t h a tt h et r a d i t i o n a ld e t e c t i o na l g o r i t h md o e sn o t c o n s i d e rc o m p l e t e l ya b o u tt h er e l e v a n c ea m o n gt h en o d e s ，a n do r i g i n a lt e a md e c i s i o n m e t h o dh a si t sl i m i t a t i o n s g i v e ns o m em o d e la s s u m p t i o n s ，t om i n i m i z et h eb a y e s i a n r i s kf u n c t i o n , w ed e r i v et h ea l g o r i t h mi nd e t a i la c c o r d i n gt ot h eb a y e s i a nd e t e c t i o n p a r a d i g ma n ds o m eg m s a l g o r i t h m s l a s t l y , a n a l y z et h ei n f l u e n c et o d e t e c t i o n a l g o r i t h mf r o mp a r a m e t e r s ( s u c ha sc o r r e l a t i o n , s i g n a l - t o - - n o i s er a t i o ) a c c o r d i n gt oa s i m p l es i m u l a t i o ne x a m p l e ，a n dt h er e s u l t sa l s os h o wi t se f f i c i e n c y ( 2 ) d e v e l o pt h em o r ec o m p l e x i t yt e a md e c i s i o nm e t h o db a s e do nt h ec h a n n e l m o d e l s f o rt h ec o m p l e x i t yo fe n v i r o n m e n t , t h es i g n a lm a yo c c u rt oa t t e n u a t i o no r p r o d u c ek i n d so fb i a s e s i nt h i ss i t u a t i o n , a f t e rm o d e l i n gt h ec h a n n e l ，t h ea l g o r i t h m w i l lb ea p p l i e di n t om o r eg e n e r a ls c e n e ，a n dg i v e nt h ea n a l y s i sf o rt h em a n e u v e r i n g t a r g e tt r a c k i n gp r o b l e m ( 3 ) an e wt r a c k i n ga l g o r i t h mc a l l e dn - k fi sd e v e l o p e di np r o b l e mo ft h e m a n e u v e r i n gt a r g e tt r a c k i n g i ti sd e s i g n e db a s e do nt h em i n i m i z a t i o no ft h e 酉o b a l r i s k ，a n da i m st oi m p r o v et h ep e r f o r m a n c eo ft h et r a c k i n g a f t e rc o m p u t i n gt h e c o n d i t i o n a lp r o b a b i l i t yd i s t r i b u t i o na n dt h et h r e s h o l dv a l u eo ft h ei n n o v a t i o n , w ec a l l c h o o s et h em o d e la c c o r d i n gt ot h ed e c i s i o nr e s u r t h e nt r a c kt h et a r g e tb yt h e k a l m a nf i l t e r i n g 伥d l a s t l y ，t h en - k fi sc o m p a r e dw i t ht h ek ft h r o u g ht h et w o c l a s s i c a lm o d e l 争一- - - m a n e u v e r i n gm o d e la n dm u t a t i o nm o d e l ，t h er e s u l t ss h o w st l l e 杭州电子科技大学硕士学位论文 e f f i c i e n c ya n ds u p e r i o r i t yo ft h en - k f 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 , g r a p h i c a lm o d e l ，n e t w o r kd e t e c t i o na l g o r i t h m 。 t e a md e c i s i o nt h e o r y , m a n e u v e r i n gt a r g e tt r a c k i n g i h l 一 杭州电子科技大学硕士学位论文 目录 摘要i a b s t ra c t i i 目录 第1 章绪论1 1 1 研究背景及选题意义1 1 2 无线传感器网络简介。2 1 3 图模型简介4 1 4 基于多传感器网络检测算法综述。5 1 5 多传感器目标跟踪简述7 1 6 当前研究热点、难点与未来的研究方向8 1 7 本文的主要内容及章节安排9 1 8 本章小结1 0 第2 章基础知识1 1 2 1 图论基础知识1 1 2 2 二元检测基础1 2 2 3 图模型基础知识1 2 2 4 常见的贝叶斯决策1 4 2 4 1最小错误率贝叶斯决策1 5 2 4 2 基于最小风险的贝叶斯决策1 6 2 4 3 p e r s o n - b y - p e r s o n 最优1 8 2 5 几种检测方法综述。1 8 2 6 本章小结1 9 第3 章尸坫坷最优准则下的网络检测算法2 0 3 1 引言。2 0 3 2 贝叶斯风险及决策。2 l 3 2 1单传感器情形2 l 3 2 2 多传感器情形2 2 3 3 队决策方法2 4 3 4 计算量及能耗分析3l 3 5 实验验证。3 2 3 6 本章小结3 4 i v 杭州电子科技大学硕士学位论文 第4 章基于全局风险最小准则的机动目标跟踪算法3 6 4 1 引言3 6 4 2 问题描述。3 6 4 3 信道模型3 7 4 3 1 单父亲节点信道模型。3 7 4 3 2 多父亲节点信道模型3 8 4 4 队决策方法描述3 9 4 5 跟踪算法描述4 l 4 6 仿真验证4 5 4 6 1 仿真实验1 机动模型4 6 4 6 2 仿真实验2 突变模型4 8 4 7 本章小结5 0 第5 章总结与展望5 1 5 1 论文工作总结5 l 5 2 论文工作展望5 2 致 射5 3 参考文献5 4 附录5 8 v 的 感 基 础。它综合了无线通信技术、信息处理技术、嵌入式计算技术、传感器技术，可 以协作地实时监测、感知和采集各种环境或检测目标的信息，再对这些信息进行 综合处理，最后传递给用户【i 刁。传感器网络作为一个全新的研究领域，已引起 了社会的广泛重视，包括学术界、工业界，被认为是2 1 世纪最重要的技术之一 【3 4 】 o 作为微型化设备和无线通信结合的产物，无线传感器网络是由大量的体积较 小、价格便宜、能量有限( 由于电池等供电) 、具有无线通信和检测能力的传感器 节点构成的网络。为达到监测物理世界的目的，这些节点通常被大批量的放置在 监测区域。随着科学技术的不断发展和完善，各种传感器网络逐渐渗透社会的每 个角落、深入我们生活的每个环节，真实的体现了其巨大的应用前景。当前和潜 在的具体传感器网络的应用有：生物栖息地监控、工业控制和监视、智能农业、 森林防火、环境和污染监测、智能建筑、智能交通、个人健康检测和智能家居， 更重要的是在军事和安保方面的应用，例如军事目标包围、战场傍皂甲车辆或部 队的移动) 侦察监控、防范恐怖袭击、空中交通控制等。此外，传感器网络在地 理、生物、监视、故障检测等科学领域和工程应用中的应用也得到了显著的效果 【5 1 0 o 能量约束是阻碍传感器网络迅猛发展的一个关键问题【1 1 1 。如何在使网络的生 命周期最长或者最大化网络检测性能的要求下，高效地使用能量是传感器网络面 临的首要挑战。网络层的能量消耗和应用层的决策性能是一组不可协调的矛盾对 象，一方面，为了得到较好的决策性能就必须消耗大量的能量；另一方面，为了 节省能量就必然要以牺牲决策性能为代价。怎样权衡二者是个难点和热点。网络 检测算法一般可以分为离线计算和在线计算两部分，而且只有通过改进离线算法 才能在保证决策性能的条件下有效地节省能量。近年来，包括信息融合领域一些 著名学者在内的大量研究者积极开展传感器网络设计及检测算法的研究，获得了 一些重要的理论结果，并取得一些成功的应用。但是，基于传感器网络的检测方 法这一领域仍然处于起步阶段，无论在基础理论方面，还是在工程技术层面上， 或者其他领域的应用，都存在大量的问题亟待解决【1 2 ，1 4 】。 杭州电子科技大学硕士学位论文 因此，在国家自然科学基金重点项目“面向大型工程安全预测与评估的信息 融合方法( n o6 0 9 3 4 0 0 9 ) ”以及国家自然科学基金青年科学基金项目“多约束多传 感器网络融合及在船舶监控中的应用研究( n o 6 0 8 0 4 0 6 4 ) ”等相关项目的资助下开 展网络检测算法的研究工作，不仅在完善检测理论方面具有重要的理论意义，而 且在推动传感器网络的实际应用方面存在重大的应用价值。 1 2 无线传感器网络简介 一个无线传感器网络是由许多个功能相同或不同的无线传感器节点组成，这 些节点通常包括传感器节点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 和管理节点。大量 传感器节点被随机安放在监测区域内部或附近，能够通过自组织方式构成网络， 并对环境或者目标进行测量。传感器节点将这些测量得到的数据传输到汇聚节 点，最后通过互联网或卫星到达管理节点。用户可以通过管理节点对传感器网络 进行各种配置和管理，及时发布监测任务以及收集监测数据【l5 】。传感器网络的结 构如图1 1 所示。 图1 1 无线传感器网络体系结构 图 1 2 传感器节点结构图 传感器节点一般是由四部分构成的：功率单元、感知单元、处理单元、收发 信机 1 2 , 1 6 - 1 7 1 ，如图1 2 所示。这四个模块分别具有不同的功能：功率单元提供传 2 杭州电子科技大学硕士学位论文 感器节点运行所需的能量，通常为微型电池、太阳能电池等；感知单元是由传感 器和模数转换器( a d ) 两部分组成，前者对信息进行收集，后者进行数据转换， 然后传递给处理单元；处理单元负责控制整个传感器节点的操作( 如，发送、接 收、空闲和睡眠四种状态的控制) ，存储和处理本身采集的和其他节点发送过来 的数据；收发信机将节点连接到网络上，主要负责与其他节点间的通信，并进行 收发采集数据和减缓控制信息。 无线传感器网络的发展依赖于多种技术，包括无线通信、控制、监测、数据 采集等，其基本特征有 i z , 1 6 ： 1 ) 节点数目非常庞大( 成千甚至上万) ； 2 ) 网络节点密度高； 3 ) 由于环境影响和能量耗尽，节点更容易出现故障，进而失效； 4 ) 环境干扰和节点故障易造成网络拓扑结构的变化，且变化频繁； 5 ) 通常情况下，大多数传感器节点是固定不动的； 6 ) 节点主要采用广播通信方式，异于传统的点对点通信： 7 ) 传感器节点具有的能量、处理能力、存储能力和通信能力等都十分有限； 8 ) 寻址以数据为中心。 根据无线传感器网络的特有结构及应用的特殊要求，可以总结出无线传感器 网络系统的关键性能指标： 1 ) 网络的工作寿命( 布置在无人区域的节点的工作寿命需要数月甚至几 年) ； 2 ) 网络的覆盖范围以及可扩展性； 3 ) 网络搭建的成本和难易程度； 钔网络的响应时间； 5 ) 网络的检测性能。 无线传感器网络是涉及多学科交叉的一个崭新研究领域，在理论基础和工程 技术两个层面上，都有许多关键技术待发现或正在研究： 1 ) q o s ( 0 u a l i t yo fs e r v i c e ，服务质量) 保证； 2 ) 网络安全机制； 3 ) 网络拓扑控制： 4 ) 网络通信协议等无线通信技术； 5 ) 同步管理机制； 6 ) 定位技术； 刀嵌入式实时系统软件技术； 8 ) 数据处理( 包括数据融合、网络检测等) 技术； 3 杭州电子科技大学硕士学位论文 9 ) 相关的硬件技术。 传感器网络中存在多种形式的能量约束。为了能够有效地节省能量，需要尽 量减少传输的数据量，因此可利用节点的处理器模块处理各个节点收集的数据， 并做出局部决策，进而进行传递，最终做出全局决策。 1 3 图模型简介 图模型是统计学中一个崭新的研究领域，它是概率论和图论密切结合的产 物，可以看作是根据有向图或者无向图定义的一类概率分布【l 研。作为一种用图 的方式表示变量之间概率关系的模型，如图1 3 所示，图中节点可看作为随机变 量，边视为概率依赖关系或者变量之间的概率联系或相关性，可以用联合概率分 布来表示这些相互连接节点的子集上定义的相关函数的乘积。同时，基于模块化 的思想，通常可以把很复杂系统分解为若干个较简单的子系统。为了使复杂系统 的建模问题得以简化，图模型理论不仅利用了联合概率分解的方法把这些子系统 组合起来，同时利用图论定性地描述了这些子系统之间的相互关系。图模型理论 在人类基因、医学诊断、经济和金融的领域得到了的应用，已成为许多领域的热 门研究课题。特别是近年来，随着图模型推理和学习算法的深入研究，它在数据 发掘、知识发现、专家系统和模式识别等领域也发挥出越来越重要的作用【1 蛇3 1 。 对于信息论、机器学习、模式识别、统计学等领域中许多经典的多变量概率 系统均是图模型的特殊形式，包括隐马尔科夫链、b o l t z m a n n 机、谱系图、k a l m a n 滤波、进化树、马尔科夫随机场、隐马尔科夫模型等，图模型理论为这些模型提 供了统一的理论框架，即这些系统是图模型的一般基础形式的实例。基于图模型， 可以利用概率计算直接进行预测推理或诊断推理。2 l 世纪以来，随机逼近算法 的研究进展，促使图模型算法的推广速度也得到提高。图模型在专家系统、辅助 医学诊断系统等方面已有相当的应用【2 6 】。在生物信息学、情报检索、语音处理以 及图像处理等领域中，经常涉及到由大量随机变量通过多种复杂方式结合起来构 成的复杂模型【2 7 j ，图模型针对这些复杂模型提出了一般的近似解决方法。可以用 递归形式的方法来计算这些复杂模型所要求的统计量( 比如，似然比、普函数等) ， 而且可以统一用图模型的公式来表示这些方法。近年来，图模型在面向计算的领 域中也得到了极为广泛的应用，包括组合最优、统计物理学以及经济学等领域； 4 杭州电子科技大学硕士学位论文 同时，也可被用来评估计算复杂度和可行性，即，算法的运行时间或者错误范围 的量级可以被表示为图的结构性质【2 8 刎。另外，可以将某一领域已经得到发展的 特有技术转换到其他相关领域，拓展其应用空间，也为设计新的系统提供了一个 简单的框架。 概率图模型是一个相对很大的范畴，按照边的属性可以分为两种模型：无向 图模型和有向图模型。典型的无向图模型包括马尔科夫网络( m a r k o vn e t w o r k ) 、 马尔科夫随机场( m a r k o vr a n d o mf i e l d s ，脚等，在物理界和视觉领域得到了很 大的应用，其中无向图模型特例线性l o g 模型，在统计学领域也比较流行。 贝叶斯网络是最常用的有向图模型，而基于贝叶斯网络的信念传播( b e l i e f p r o p a g a t i o n ) 算法和相关的基于图的算法( 如消元法、变分法等) ，可以很好地解 决检测过程中的一些概率推论问题。例如，最大后验估计( m a p ) 是要求知道所有 隐藏节点的联合概率分布，极大后验边缘估计( m p m ) 估计是要求能通过计算得到 隐藏节点的边缘概率分布阱矧。 1 4 基于多传感器网络检测算法综述 2 0 世纪7 0 年代，美国科学家最早提出了“数据融合( d a t af u s i o n ) 这个概念。 数据融合最早应用在军事指挥系统中，它有效地提高了综合作战能力。随着科学 技术的进步，传感器技术的快速发展，近年来，该技术已经推广到民用领域，如 医疗、智能交通、故障诊断、工业控制等领域。而多传感器目标检测、目标跟踪 和数据关联、多假设滤波器、身份识别、条件事件代数、规划识别等理论构成了 其主要内容。 作为数据融合的重要组成部分，多传感器目标检测和跟踪已得到了快速的发 展和应用。常见的多传感器目标检测准则有纽曼皮尔逊( n e y m a n - p e a r s o n ，n p ) 准则，贝叶斯准则等【3 0 】。 当先验概率和风险都难以确定时，通常要求虚警概率竹尽可能小，而检测 概率n 尽可能大，即在保证虚警概率毋小于等于某一给定值( 只 p b 2l y ) ，则将 “归类于正常状态0 - 9 1 ，反之p 如。ij ，) ， 0 ( 1 ，+ 1 ) p ( j ，i + 1 ) + 口( 1 ，一1 ) p t y i 1 ) 一基 移项后，变成等价的门限值测试形式 躺= 捌。江币0 ( + i 翮, - i ) - 0 ( - - i , - i ) ( 3 4 ) 根据式( 3 4 ) 可知存在如下的特殊的分布 p o m 罗) = 协甜其= r 它t y ) 因此， p gix ；歹) = f p ( yjx 加qiy ；歹x 纱 ( 3 5 那么，将式( 3 4 ) 代入式( 3 5 ) ，可以求解出节点的检测概率n 和虚警概率竹 分别为 p 小p l a b , ) _ i x l = 小j p t y 咖= 粥二： 而且，在决策歹下的风险函数( 3 2 ) 可以写成 ，陟) = 秒) ，x ) p ( x v ) p ( y ) d y ( 3 6 ) 根据贝叶斯公式p g 陟砀) = p l 石b g ) ，带入式( 3 6 ) n - j 襁t j ，) = ，c 护) ，x 扫ix ) p ( x ) d y 按照式( 3 5 ) 对积分进行求解，得到最优决策歹下的风险函数为 伊) = 以) c 0 ，勘gl x ；力 3 2 2 多传感器情形 首先介绍两种常见的多传感器决策方法【6 。 例1 根据式( 3 2 ) 的形式，两种常用的b p 算法( 信念传递算法) 可化为： 对于极大后验估计( m a p ) ，如果代价函数满足： 如d = 三席枢纠嚣得吩“，i = 1 , 2 , - - - , n 得到最大化似然比决策： y ( y ) = a r g m a x p