（控制理论与控制工程专业论文）基于粒子滤波的无线传感器网络目标跟踪.pdf

中文摘要 擅要：无线传感器网络( w s n ) 作为2 l 世纪最具影响力的技术之一，应用领域十 分广泛，其中一个重要应用便是目标跟踪。目标跟踪模型通常情况下是非线性模 型，传统的卡尔曼滤波在解决非线性问题时有其局限性，并且当解决多目标跟踪 时，传统的数据融合方法也不能很好地解决非线性问题。另外，无线传感器网络 有其自身的特点，不同的传感器网络性能也不尽相同，比如可靠性、跟踪精度和 实时性等，若采用传统的单一类型节点的传感器网络，则很容易产生瓶颈问题， 从而影响整个网络的有效运作。 粒子滤波是一种基于递推计算的序列蒙特卡罗算法，它采用一组从概率密度 函数上随机抽取的并附带相关权值的粒子集来逼近后验概率密度，从而不受非线 性、非商斯问题的限制。虽然粒子滤波存在诸多优点，然而它仍然存在诸如粒子 数匮乏、滤波性能不高、实时性差等问题因此本文主要利用改进的粒子滤波算 法，来研究无线传感器网络单目标与多目标跟踪翘题。 本文在分析了无线传感器网络目标跟踪相关内容，研究了非线性滤波相关理 论后，提出将粒子滤波应用到等级结构的无线传感器网络目标跟踪模型中，并且 对现有基于粒子滤波多目标跟踪算法进行改进，提出了基于p f 、u p f 和改进的 u p f 算法的多目标跟踪算法。并且将三种算法进行比较，仿真实验证明，将改进 的粒子滤波算法应用到w s n 目标跟踪中是可行的，并且精度和实时性分别有所提 高。 关键词；非线性滤波；粒子滤波；u 粒子滤波；无线传感器网络；目标跟踪 分类号；u 2 8 3 1 a b s t r a c t ：a so n eo ft h em o s ti m p o r t a n tt e o h n o | o g i e so ft h e2 1 c e n t u r y , t h e w i r e l e s s8 c l k q o rn e t w o r k ( w s n ) h a sb e e nu s e di nm a n yf i e l d s o n eo fi 乜i l s e si st h e t a r g e tt r a c k i n g g e n e r a l l y , t h em o d e l so ft h et a r g e tl a r a c k i n g 玳n o n - l i n e a xa n d n o n g a u s s i a n , b u tk a h i l a nf i l t e r sa n dt r a d i t i o n a lm e t h o d so fd a t af u s i o nc s i i ln o ts o l v e n o n l i n e 越a n dn o n - g a u s s i a np r o b l e m se f f e c t i v e l y b e s i d e s d i f f e r e n tw i r e l e s ss 印s o f n e t w o r k sh a v ed i f f e r e n tp e r f o r m a n c e s , s u c ha sr e l i a b i l i t y , p l r 删o na n dr e a l - t i m e p e r f o r m a n c e i f w eu u n i f o r m 剐强1 9 0 幅i nt h ew h o l en e t w o r k , i t sq u i t ee a s yt op l o d t l c , e b o t t l e - n e c kp r o b l e m sa n dt h en e t w o r kw i l lb e o o i l l en o n e f f e c t i v e a p a r t i c l es e t , w h i c hi sr a n d o m l ys a m p l e d 丘o mp r o b a b i l i t yf u n c t i o na n dh a s c o r r e s p o n d i n gw e i g h t s ，i si n t r o d u c e dt oa p p r o a c ht h ep o s t e r i o rd i s t r i b u t i o n t h e r e f o r ei t 锄h a i l d l en o n l i n e a ra n dn o n - c r a u s s i a np r o b l e n sw i t h o u ta n yl i m i t s t h o u g ht h e p a r t i c l e6 l t 订h a s m a n ya d v a n t a g e s , t h e r ea r es t i l ls o i n ee x i s t i n gp r o b l e m s s u c ha s s a m p l ei m p o v e r i s h m e n t , l o wp e r f o r m a n c ea n db a dr e a l - t i m ep e r f o r m a n c e s i n c et h e a b o v ed i s a d v a n t a g eo fp a r t i c l ef i l t e r , s o i i l ei m p r o v e da l g o r i t i n n s 玳p r e s e n t e dt os t u d y t h ep r o b l e m so f w s nt a r g e tt r a c k i n g f i r s t l y ，t h i sp r o j e c th a ss t u d i e dw s ht a r g e tt r a c k i n gs y l j t 觚a n dt h e ni n t r o d u c e s p a r t i c l ef i l t e rt h e o r yb a s e do i lt h ea n a l y s i so f n o n - l i n e s xf i l t e r s i n c et h ed i s a d v a n t a g eo f m u l t i p l et a r g e t st r a c k i n ga l g o r i t h m s , s o i l l ei m p r o v e da l g o r i t h m s , b a s e do i lp a r t i c l ef i l t e r , u - p a r t i c l ef i l t e ra n di m p r o v e du - p e r c a l ef i l t e rh a v e b e e np r e s e n t e di nt h i sd i s s e r t a t i o n 1 1 ks i m u l a t i o nr e s u l ts h o wt h a tt h e s em e t h o d sp e r f o r mw e l li nw s n t a r g e tw a c k i n g k e y w o r d s ：n o n 4 i n e a r f i l t e r , p a r t i c l ef i l t e r , u p f w t r e l e s ss e n s o rn e t w o r k , t a r g e t t r a c k i n g c l a s s n o ：u 2 8 3 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：旁参 导师签名：1 锣幼司 签字日期：卿年j 抄月订日签字日期：砷陟月彩自 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：方致 签字日期：纱 年l y 月巧佃 致谢 深深感谢我的导师张三同副教授，正是张老师对我的指导、关怀和严格要求， 使我顺利完成了硕士阶段的学习和研究。在导师渊博的知识、严谨的工作作风， 敏锐的洞察力和高尚的师德的熏陶下，我的学识快速增长，提高了科研技能，具 备了科技人员的优良作风、品格和素质，树立了正确的人生观和世界观。正是张 老师的严格要求，通过两年半的潜心学习和研究，我才对粒子滤波算法及其应用 有了比较深入的研究，在无线传感器网络目标跟踪算法的改进方面提出了自己的 一些观点、见解和实施方案，完成了论文相关的科研工作和撰写工作。 张三同老师悉心指导我完成了实验室的科研工作，在学习上和生活上都给予 了我很大的关心和帮助，在此向张老师表示衷心的谢意。 在实验室工作及撰写论文期间，也感谢实验室各位同学对我的研究工作给予 的热情帮助，在此向大家表达我的感激之情。 最后我也要特别感谢我的亲人和朋友们，是他们给予我精神上、生活上极大 的支持与关怀，使我能安心从事学习和研究工作，才得以完成学业 1 引言 无线传感器网络是一种新兴的能够自组织的网络技术它不需要固定网络支 持，具有快速展开、抗毁性强、容错性高等特点，可广泛应用于军事、环境监测、 健康护理、工业控制领域，智能家居以及其它恶劣环境区域。定位和跟踪在实际 生活中有着广泛的应用，当前应用最广泛的定位跟踪技术是g p s ，对于野外的定 位估计，g p s 有广泛的应用，但是g p s 要求有很高的传输功率以及有时难以想象 的误差。对于室内的定位估计，g p s 效率较低，因此g p s 并不适合室内精确定位 由于传感器网络具有自组织性、鲁棒性、隐蔽性好、成本低以及易于布置等特点， 无线传感器网络非常适合于探测跟踪运动目标，例如在避免道路交通碰撞、监测 野战区域、入侵监测等等方面。在军事上可以监测敌方的兵力移动，野战区域内 狙击手的火力探测。因此，无线传感器网络目标跟踪问题已成为当前的热门研究 颁域。 1 1 课题研究背景及意义 无线传感器网络的基本思想起源于2 0 世纪7 0 年代。1 9 7 8 年，美国国防部高 级计划研究署( d a r - p a ) 成立了新一代分布式传感器网络工作组，拉开了w s n 研究的序科1 2 。无线传感器网络大致经历了如下发展历程例：第一代传感器网络 出现在2 0 世纪7 0 年代，使用具有简单信息信号获取能力的传统传感器，采用点 对点传输、连接传感控制器构成传感器网络；第二代传感器网络，具有获取多种 信息信号的综合能力，采用串，并接口如r s 2 3 2 r s - 4 8 5 与传感控制器相联，构成 有综合多种信息的传感器网络：第三代传感器网络出现在2 0 世纪9 0 年代后期和 本世纪初，用具有智能获取多种信息信号的传感器，采用现场总线连接传感控制 器，构成局域网络，成为智能化传感器网络；第四代传感器网络正在研究开发， 用大量的具有多功能、多信息信号获取能力的传感器，采用自组织无线接入网络， 与传感器网络控制器连接，构成无线传感器网络其主要应用如下： ( 一) 军事应用 军事应用是无线传感器两络技术的主要应用领域，主要体现在以下几方面： ( 1 ) 对友军军力、装备、弹药进行监控； ( 2 ) 对战场和敌占区进行快速侦察； ( 3 ) 对战斗损失进行评估； ( 4 ) 为智能型武器提供目标定位信息； ( 5 ) 侦察及判定核、生物及化学武器攻击 ( - - ) 环境应用 无线传感器网络是生态环境及地理监测的有力手段，主要应用在如下几方面： ( 1 ) 森林火灾、火山、洪水、泥石流监测及预报： ( 2 ) 复杂地表勘测； ( 3 ) 生物习性、农作物生长环境监测； ( 4 ) 海洋、大气成分监测： ( 5 ) 桥梁、建筑物、水利设施状态监测 ( 三) 医疗应用 无线传感器网络为未来的远程医疗提供了更加方便、快捷的技术手段，潜在 的应用主要包括： ( 1 ) 对人类生理数据进行无线监测： ( 2 ) 对医护人员和患者进行追踪和监控； ( 3 ) 医院药物管理。 ( 四) 其他应用 无线传感器网络还有许多应用点，如工业生产过程的监控、城市交通状况的 监控、外星及外太空的探索、家庭自动化控制等。在众多的领域中无线传感器网 络都将体现出它的优越性，随着无线传感器网络的发展，还会有许多新的设计和 应用模式出现。由于无线传感器网络具有潜在的巨大应用价值，它已经引起了世 界各国的军事部门，工业界和学术界的极大关注。但是，由于若干技术问题尚未 解决，目前，大部分无线传感器网络仍处于理论研究和小规模试验阶段，距离实 际应用尚存在一定距离1 4 本课题选取了w s n 目标跟踪这一研究方向，主要研究w s n 跟踪中需要应用 到的滤波算法与数据融合方法。目标跟踪模型通常为非线性模型，常用的k a l m a n 滤波并不能很好地解决非线性问题，处理一般的非线性滤波问题的一种较好的方 法是粒子滤波 5 1 ，也称顺序的蒙特卡罗方法s 。q u e 曲a im o n t ec a r l o ( s m c ) m e l h o d s 。这种方法利用一些随机样本( 粒子) 来表示系统随机变量的后验概率分 布，它通过非参数化的m o n t o - c a r l o 模拟方法来实现递推贝叶斯( b a y e s ) 滤波， 精度可以逼近最优估计，而且适用于任何能用状态空间模型表示的非线性系统 相对于扩展卡尔曼滤波，粒子滤波计算量较大，但随着计算机性能的极大提高和 并行计算技术研究的进展，计算量大已不再成为粒子滤波的瓶颈，粒子滤波的应 用领域将不断扩大。与传统滤波方法相比，粒子滤波在一般情况下非常灵活，容 易实现，可以并行化，使用性强，且加之其摆脱了解决非线性滤波问题时随机量 必须满足高斯分布的制约条件，并在一定程度上解决了粒子数样本退化问题，因 2 此近年来该算法在许多领域得到成功应用，如计算机视觉、航空导航及过程监控 等。目前已有许多会议和讨论组都将粒子滤波作为专题进行深入讨论和学术交流。 1 2 本文研究的主要内容 无线传感器网络( w s n ) 应用领域广泛，但现阶段还只是处于理论研究阶段， 实际应用还十分有限，还有许多具体问题亟待研究。因此本文选定了无线传感器 网络目标跟踪这一刚刚起步的领域进行理论研究。由于目标跟踪模型为非线性模 型，因此本文将粒子滤波算法引入w s n 目标跟踪。粒子滤波在解决非线性问题上 具有明显的优势，但也存在一些缺陷，尤其是粒子匮乏问题，因此改进的粒子滤 波算法在w s n 中的应用是本文研究的重点。本文研究的主要内容如下： l 、阐述w s n 目标跟踪的基本原理及特点； 2 、阐述w s n 的网络结构类型与特点； 3 、在介绍非线性滤波的基础上引入粒子滤波。首先介绍贝叶斯估计理论，以及蒙 特卡罗方法，然后介绍了粒子滤波算法与改进的粒子滤波算法； 4 、建立w s n 单目标多目标跟踪的非线性模型，并结合改进的粒子滤波算法进行 仿真，对已有的基于粒子滤波的多目标跟踪模型进行改进以提高实时性。将改 进的控子滤波算法与基本粒子滤波算法进行比较。改进的粒子滤波算法使跟踪 可靠性大大提高 2 无线传感器网络目标跟踪介绍 2 1 无线传感器网络目标跟踪原理及特点 传感器网络由大量体积小、成本低、具有感测、通信、数据处理能力的传感 器节点构成将大量传感器节点部署在监测区域内。自组织成网络后，经过多条路 由将数据传输到数据中心，供用户使用。传感器网络体系通常包括传感器节点、 汇聚节点和管理节点 6 1 。 在不同的应用中传感器网络节点的组成不同，但传感器节点都有传感器模块、 处理器模块、无线通信模块和能量供应模块，各模块作用见文献阴。根据不同的 应用采用不同的器类型，处理器大都选用嵌入式c p u ，通信模块采用睡眠唤醒机 制。各模块由一个微型操作系统控制，多数采用u c b e r k e l e y 公司开发的t i n y o s 操作系统。 传感器网络由大量部署在监测区域内的传感器节点组成，当有目标进入监溯 区域时，由于目标的辐射特性，通常足红外辐射特征、声传播特征和目标运动过 程中产生的地面震动特征，传感器会探测到相应的信号。 我们假定把n 个传感器节点部署在监控区域为s 的区域内，网络总的延时为 t 。传感器最大探测半径为r 。任一时刻t ，当有目标以速度甜进入传感器节点探 测半径内时传感器检测为l ，否则检测为0 。本文主要研究算法的应用，因此 忽略检测过程，在此不作赘述。当网络探测到目标后便开始利用特定的跟踪算法 与通信方式进行目标定位跟踪。 下面定性地讨论现有的三种跟踪策略，以比较其跟踪目标的有效性，节能性， 以及网络寿命： ( 1 ) 完全跟踪镱略：网络内所有探测到目标的传感器节点均参与跟踪。显然， 这种策略消耗的能量很大，造成了较大的资源浪费，为数据融合与消除冗余信息 增加了负担，但同时这种方法提供了较高的跟踪精度。 ( 2 ) 随机跟踪策略：网络内每个节点以概率参与跟踪，整个跟踪以平均概率进 行跟踪。显然，这种策略由于参与跟踪节点数目得到限制，因而可以降低能量消 耗，但是不能保证跟踪精度。 ( 3 ) 协作跟踪策略：网络通过一定的跟踪算法来适时启动相关节点参与跟踪。 通过节点间相互协作进行跟踪，既能节约能量又能保证跟踪精度。显然，协作跟 踪策略是跟踪算法的最好选择。 4 为了有一个基本的理解，首先简单说明一个目标跟踪的情况旧。假定一个物体 进入了事先布置和组织好的无线传感器网络监测区域，如果感测信息超出了门限， 这时每一个处于侦测状态的节点传感器能探测到物体，然后把探测信息数据包发 送给汇聚节点。汇聚节点从网络内收集到数据后对信息进行融合得出物体是否需 要被跟踪的结论，如果目标的确需要被监控其状态，传感器网络在监测区域内将 使用一个跟踪运动目标的算法，随着目标的运动，跟踪算法将及时通知合适的节 点参与跟踪，简要过程如下： ( 1 ) 网络内节点以一定的时间问隔从睡眠状态转换到监测状态，侦测是否有目 标出现。 ( 2 ) 传感器节点检测到目标进入探测范围后，通过操作系统唤醒通信模块并向 网络内广播信息包，记录下目标进入区域所持续的时间。信包中含有传感器节点 身份号码和传感器位置坐标以及目标在探测范围内持续的时间 ( 3 ) 当汇聚节点接收到k 个节点发送的信息后，由目标跟踪公式计算出目标 位置 ( 4 ) 汇聚节点根据接收到的信息和融合信息，使用跟踪算法启动相应节点参与 跟踪 ( 5 ) 当目标离开监测区域时，节点向汇聚节点报告自己的位置信息以及目标在 节点探测范围内所持续的时间汇聚节点综合历史数据和新信息形成目标的运动 趋势 2 2 无线传感器网络目标跟踪需要考虑的问题 传感器网络跟踪目标涉及到目标探测、目标定位、通信、数据融合、跟踪算 法的设计等很多方面的问题。根据前面讨论知道，如果选择不合适的节点参与跟 踪，不但跟踪精度较低甚至丢失目标，而且会过多消耗不必要的节点能量。同时 算法的优劣也直接影响着跟踪的效果。衡量一个跟踪策略是否具有较好的跟踪效 果，需要考虑以下问题： ( 1 ) 跟踪精度：本文通过计算均方根误差来衡量跟踪精度，具体公式见仿真 环节。当然并不是精度越高就越好，精度越高意味着算法融合的数据越多，这样 会增加能量消耗，使集中还要综合能量消耗，以综合评价跟踪算法优劣。 ( 2 ) 跟踪能量消耗：由于用无线传感器网络跟踪目标大都应用于实际环境， 节点的能量消耗是一个非常关键的问题。因而要求传感器节点最好不但能储备能 量( 电池) ，还要根据实际情况可以现场蓄能( 太阳能) 。跟踪过程中选择合适的节 点参与跟踪需要考虑该节点的通信能量消耗、感测能量消耗和计算能量消耗。其 北京交通大学硕士学位论文2无线传摩器网络目标跟踪介绍 中通信能量消耗是最主要的部分嗍。在设计考虑跟踪算法时要综合衡量考虑这几 种能量消耗，找到合适的比重，以满足较低的能量消耗。从而延长节点和网络的 寿命。 ( 3 ) 跟踪的可靠性：网络可靠性差对跟踪目标有很大影响。当前应用于目 标跟踪方法主要有集中式和分布式，集中式方法要求所有网络节点在探测到目标 后都要向汇聚节点发回探测结果，不但引入的通信开销大，而且计算开销也增加 很多。这样网络的可靠性下降很快。分布式方法是一种较好的选择，但是也要充 分考虑跟踪算法的鲁棒性，能适应环境的变化。以增强网络的可靠性。 ( 4 ) 跟踪的实时性：在实际应用中跟踪的实时性是一个很重要的指标，实 时性能主要由硬件性能，算法的具体设计以及网络拓扑等多方面决定，在硬件 技术飞速发展的今天，算法的实时性与网络拓扑结构的选择便越发显得重要。 2 3 本章小结 本章介绍了无线传感器网络目标跟踪的基本原理与特点，以及衡量目标跟踪 算法优劣时需要注意的问题通过上面的介绍可以看出，无线传感器网络结构大 体可以分为两种，即集中式与分布式网络结构。集中式网络结构要求所有探测节 点将探测到的或经过简单融合过的数据传输到同一数据处理中心，这一处理中心 统一处理数据并完成跟踪算法。这种网络结构的缺陷很明显，即在通信过程中消 耗了大量的节点能量，数据冗余度过高，实时性也相应受到影响。并且对路由选 择要求很高，否则容易产生瓶颈问题。而分布式结构采用局部网络数据处理方法， 并结合协作跟踪策略，节省网络中节点的能量，延长网络使用寿命，同时也能得 到良好的跟踪精度与可靠性。因此本文采用分布式网络结构思想，采用多个局部 网络分别处理数据，最后对局部处理的数据进行综合分析得出最后的结果。 6 3 蒙特卡罗方法 本章首先简要介绍贝叶斯原理与蒙特卡罗方法，为下一章引出粒子滤波奠定 理论基础 3 1 贝叶斯发展历史 贝叶斯( b a y e s ) 一词源于英国一名牧师t o m a sb a y e s 在1 9 3 6 年提出的贝叶斯定 理 s h 埘，而该原理成为一个正式的方法和理论应当归功于b r u n od ef i n e t t i 等人。贝 叶斯理论的充分发展是在1 9 5 0 年后，他首先在商业和社会科学中取得很大成功， 在物理学中也有很好的记录。六、七十年代以来，贝叶斯学派的发展达到鼎盛时 期，越来越多的科学家投身于其中并做出了巨大的贡献。其中h o w a r dr a 伍a 和 r o b e r ts c h a e f e r 等人对贝叶斯理论做了大量有意义的工作，使贝叶斯理论形成为一 个统一的理论体系和方法论。贝叶斯理论具有很强的适用性，其概念和方法在社 会许多领域得到应用，如通信、控制、人工智能、经济管理、气象预报等。进入 八十年代以后，由于处理复杂问题的需要，许多最新的理论知识被融入到贝叶斯 理论中来，其中最引人注目的当属随机模拟方法的广泛应用。我们应用的粒子滤 波算法便是贝叶斯理论的典型应用作为一门较新的科学。贝叶斯统计学在统计 学中占据了越来越重要的地位 经典贝叶斯理论的主要思想可用如下的贝叶斯定理简单描述： 风i ) 茁她i 一) p i 毛，一1 )( 3 - 1 ) 其中，表示t 时刻的状态参数，只表示观测向量，p i ，y 。) 为观测似 然函数，盹l y 。一) 为先验概率密度，p “ij ，。) 为后验概率密度。对于( 3 2 ) 、( 3 3 ) 这样的非线性模型( h ) ，g ( ) 为非线性函数) ，贝叶斯方法的应用受到了限制，进 入九十年代后，模拟方法的蓬勃发展给解决这一问题提供了良好的工具。 状态模型： = f “一1 ) + w t ，h 一( o ，形) 观测模型： ( 3 - 2 ) 只= g ( ) + v ，q r ( o ，巧)( 3 - 3 ) 对非线性动态模型，设任意时刻t ，可利用的所有信息为_ ) ，。，并设在t 一1 时刻 的后验概率密度为p ( 王，i y ) ，则在非线性动态模型背景下，要处理的主要计算 问题包括： 1 状态参数置的进化： p l j k - i ) = i 纠毛i k i ，) ，- i ) f ，【毛- ij j k - i ) l t 1 ( 3 - 4 ) 7 2 参数的修正：在得到y ，后，计算当前后验概率密度， p ( x , i y “，2 苗嵩兰群畿 。卸 3 求函数估计： p ( l ) 的估计： 风毛i d ) = q 山“i x a _ i ，i ) ，( 3 - 6 ) 其中，：出掣( 3 - 7 ) g t i i 上卜1 3 j 再对i “i 。) 进行抽样，假设得到的样本为j = w ，。， ，在得到观测 值y 后，可得到下式： 她l y e ) ；地粤趔址鲨d ( 3 - 8 ) i i v ，l ，y 甜- i ) 贝叶斯理论本身难以得到实现，在结合蒙特卡罗方法后，其应用范围得到很 大的扩展。 3 2 蒙特卡罗方法概述 蒙特卡罗方法( m o n t ec a r l o ，简称m c ) 又称随机抽样技巧或统计试验方法，是通 过随机模拟和统计试验方法来求解数学、物理等方面问题近似解的数值方法由 于蒙特卡罗方法能够逼真地描述事物的特点及物理实验过程，解决一些数值方法 难于或根本无法解决的问题，因此随着计算机的飞速发展，蒙特卡罗方法己在多 个领域中得到广泛的应用i i l 】。 这一方法源于美国在第二次世界大战中研制原子弹的。曼哈顿计划”。该计划 的主持人之一，数学家冯诺伊曼用驰名世界的赌城摩纳哥的m 彻伦c a r l o 来命名 这种方法，方法属于计算数学的一个分支，但它与一般计算方法有很大区别，它 是以概率统计理论为基础的一种方法。应该指出，用蒙特卡罗方法解题，不是通 常数理统计方法那样通过真实的实验来完成的，而是抓住事物运动过程的数量和 几何特征，利用数字方法来加以模拟，即进行一种数字模拟试验。按照模型所描 述的过程，通过部分模拟试验的结果，作为问题的近似解。固然，这种数字模拟 试验方法在蒙特卡罗方法出现之前就已出现，是非常简单的、基本的，可以看成 是蒙特卡罗方法的前身然而，由于试验次数不能太少，进行大量的模拟工作有 很大的运算量，加之要模拟取得近似真实情况，需要很多的数据。因此，在计算 机没有发明之前，该方法本身没有多大的发展，也没有得到大量的应用只是在 计算机出现和发展以后，才使得利用蒙特卡罗方法实现大量的模拟真实实验成为 可能。由此可见，蒙特卡罗方法是和计算机紧密地联系在一起的，是数理统计与 计算机相结合的产物，它利用了统计学中的许多方法但是作为它本身最独特的 东西却是用数学方法在计算机上实现数字模拟实验。 当所要求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时， 它们可以通过某种“试验”的方法，得到这种事件出现的频率，或者这个随机变 数的平均值，并用它们作为问题的解。这就是蒙特卡罗方法】的基本思想。蒙特卡 罗方法通过抓住事物运动的几何数量和几何特征，利用数学方法来加以模拟，即 进行一种数字模拟实验。它是以一个概率模型为基础，按照这个模型所描绘的过 程，通过模拟实验的结果，作为问题的近似解 3 3 蒙特卡罗方法基本思想 蒙特卡罗方法 6 1 - 旧的基本思想是：当所求问题的解是某个事件的概率，或者 是某个随机变量的数学期望，或者是与概率、数学期望有关的量时，通过某种试 验的方法，得出该事件发生的频率，或者该随机变量若干个具体观察值得算术平 均值，通过它得到问题的解。期望值由n 个观察值的平均值近似表示的数学表达式 为【l i 】= e o ) = j ，( 而) p “) * l y “) ( 3 - 9 ) 埘i = 1 以力= _ ) ，( 磅灭磅矗* 1 ，y 编) ( 3 t o ) ，l l 上两式分别对应于分离型随机变量和连续型随机变量，“而) 和y 分别表示 随机变量取值为和j 的函数；烈) 和( 力分别为离散型随机变量的概率函数和 连续型随机变量的概率密度函数。 3 4 蒙特卡罗解题思路 蒙特卡罗解题是以一个概率模型为基础的，按照这个概率模型所描绘的过程， 通过部分模拟试验的结果，作为问题的近似解因此，用蒙特卡罗方法解决问题 需要下述过程【l l 】： ( 1 ) 建立和构造问题的概率模型 对于本身不具有随机性质的确定性问题，如求定积分、线性方程组及偏微分 方程边值问题等，须人为的构造一个与问题相关的随机模型或概率过程，使得它 9 的某个随机变量的数字特征如期望值、二次矩等正好是所求问题的解。而对于本 身就具有随机性的闯题，则主要是正确地描述概率过程。这种构造和描述随机模 型的方法，正好与处理物理问题的经典方法相反，在那里，常常是把问题归纳为 确定性问题来求解。 ( 2 ) 大量的随机试验 确定了概率模型后，根据该模型要进行大量的随机试验，从而获得随机变量 的大量试验值。这一过程可以通过目前较为成熟的计算机技术通过随机模拟来完 成，即从已知的概率分布中进行随机抽样。其中的抽样方法是m c 方法的重要研究 课题，因为对于相同的数学或物理问题，由于抽样方法不同，即使在相同的计算 机里也会获得不同的计算精度 ( 3 ) 统计处理模拟结果，给出问题解及解的精度估计 确定随机变量作为所求问题的估计量，建立各种估计量，对模拟试验结果进 行考察和登记，从中得到问题的解。 3 5 蒙特卡罗方法的特点 对蒙特卡罗方法的特点进行一下简要总结： ( 1 ) 待解决模型的随机性。 在一个数学模型或者一个物理过程中，蒙特卡罗方法通过模拟这个问题的一 个随机变量的函数，并对这种模拟得到的样本进行统计处理、给出问题的解，不 受系统现性与非线性的限制，适应性强 ( 2 ) 独特的误差估计 事实上，许多情况下，蒙特卡罗方法就是利用计算机来进行的实验，因此， 有时也把蒙特卡罗方法称作蒙特卡罗实验。对于它的结果的处理，也应该用相同 于实验数据处理的方法，具体的误差估计见下一小节 ( 3 蒙特卡罗方法的计算结果误差与维数无关。 在一定的置信水平下，蒙特卡罗方法求得解的精度与模拟算法所抽取的随机 样本的容量- 隋关，而与这些点的维数无关也就是说，所研究问题的维数的变化， 除了引起抽样时间及计算估计量的时间有所改变外，不影响问题的误差。这样， 要达到同一精度，用蒙特卡罗方法选取的点数与维数无关，计算时间仅与维数成 比例。这决定了蒙特卡罗方法对多维问题的适用性 ( 4 ) 蒙特卡罗方法应用广泛 蒙特卡罗方法解一般物理问题，可以从物理问题本身直接模拟求解，而不一 定要求先得到物理问题的数学描述这与其他的数值方法解物理问题有着本质的 不同。因此，蒙特卡罗方法能解决其他数值方法很难或者根本不可解决的许多问 题，从而在各个领域中发挥越来越重要的作用【j 1 1 3 6 蒙特卡罗方法的收敛性和误差估计 ( 1 ) 收敛性： 蒙特卡罗方法是由随机变i x 的简单子样五，j r 2 ，的算术平均值： 叉* = i l n x i q 一1 1 ) 作为解的近似值由大数定律可知，若玉，五，耳独立同分布，且具有期 望值耳加 ，则 p 似甭；斗耳聊= l ( 3 - 1 2 ) 这表明，当随机变量x 的子样数n 充分大时，其均值以概率1 收敛于它的期望 值 ( 2 ) 误差估计： 蒙特卡罗方法的近似值与真值的误差，由概率论的中心极限定理给出： 烛p ( 瓜叫毛一甄别 x ) = l 2 v 匠x e - ：l d t ( 3 - 1 3 ) 其中，盯是随机变量x 的均方根误差， 仃2 = 联x 一耳幻) 2 = m e ( 柳) 2 ( f 渺 ( 3 1 4 ) 厂( d 是x 的分布密度函数。当n 充分大对，有如下近似式； 唯一一层蚓 焉) * 去”a r t 1 口( 3 - 1 5 ) 其中口称为置信度，l 一口称为置信水平。该式的含义是：在1 一口的置信水平 下，近似值与真值的误差为x c r l 。由问题的要求给出置信度水平后，查标准正 态分布表可得近似值与真值的误差： i 露一叫 焉( 3 - 1 0 上式中的盯是未知的，需用下式求出： 孑= 羼硒 ( 3 1 7 ) 这可在计算所求量的同时求出。从上述可知，蒙特卡罗方法的误差【1 1 1 为概率 误差。且误差与样本容量点数m 有关，而与问题的维数无关。即问题的维数改变， 除了引起抽样时间和计算估计量的时间有改变外，不影响问题的误差。这样，要 达到同一精度，用m c 方法选取的点数与维数无关，计算的时间仅与维数成比例 而对于确定性的数值计算方法，为达到同一精度所取点数与维数的幂次方成比例， 即计算量要随着维数的幂次方增加。这是蒙特卡罗方法优于其它数值方法的显著 之处 3 7 本章小结 蒙特卡罗方法是由于科学技术的发展和电子计算机的发明，而被提出的一种 以概率统计理论为指导的一类非常重要的数值计算方法，是指使用随机数( 或更常 见的伪随机数1 来解决很多计算问题的一种方法。蒙特卡罗方法的基本思想是当所 要求解的问题是某种事件出现的概率，或者是某个随机变量的期望值时，它们可 以通过某种“试验”的方法，得到这种事件出现的频率，或者这个随机变数的平 均值，并用它们作为问题的解。蒙特卡罗方法通过抓住事物运动的几何数量和几 何特征，利用数学方法来加以模拟，即进行一种数字模拟实验。它是以一个概率 模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近 似解。蒙特卡罗方法解题归结为三个主要步骤：建立和构造问题的概率模型，进 行大量的随机试验，统计处理模拟结果，给出问题解及解的精度估计。 传统的经验方法由于不能逼近真实的物理过程，很难得到满意的结果，而蒙 特卡罗方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符合，可 以得到很圆满的结果这也是最初我们采用该方法的原因通过介绍蒙特卡罗方 法的误差原理，进一步明确此方法的优越性。 和传统的数值方法相比，蒙特卡罗方法在解决超大计算量问题，包括优化和 积分等方面有很大的灵活性由于具备这些优点，近些年蒙特卡罗方法引起了信 号处理专家的重视。近些年，蒙特卡罗方法被大量应用于贝叶斯估计等统计信号 处理领域。粒子滤波算法正是基于贝叶斯估计与蒙特卡罗方法而发展起来的，下 一章我们将重点介绍粒子滤波算法。 1 2 4 一般粒子滤波算法 粒子滤波是一种基于递推计算的序列蒙特卡罗算法，它采用一组从概率密度 函数上随机抽取的并附带相关权值的粒子集来逼近后验概率密度，从而不受非线 性、非高斯问题的限制，目前已经广泛应用于自动控制、机器人技术、统计信号 处理、时序分析等研究领域 4 1 序贯蒙特卡罗 序贯学习与推论方法在许多应用领域都发挥着重要的作用如实时信号处理它 的数据是以序贯形式出现的进而人们希望采用一种序贯处理的策略去处理信号中 的非静态现象使得从较接近的过去信息中获得比较远的过去信息中相对较大的权 值。另外，形式上计算的简单性无需存储所有数据等优势构成序贯方法引起广泛 注意的又一重要因素。许多实际的信号处理问题中涉及到了非高斯非线性及非静 态等基本要素。因此基于标准的最大概率准则，最大后验准则或最小均方根误差 准则，通常不可能推导出精确的具有封闭形式的估计式。经典的次优方法，如扩 展的卡尔曼滤波与高斯和近似法虽然比较容易实现但是它们不能考虑所有的显著 统计特征，因此常常导致较差的结果。随着计算能力的迅速提高结合近来在应用 统计学中发展，激发了许多在序贯蒙特卡罗仿真领域的方法的进步。由于无需对 数据的概率分布做任何假设，蒙特卡罗方法具有很强的适应能力。此外实验结果 表明这类方法可以对结果进行改良，从贝叶斯理论的观点出发序贯蒙特卡罗方法 可以实现在线计算重要的后验概率分布，因此蒙特卡罗方法被广泛应用于诸如计 算机视觉，经济计量学，跟踪，通信，自动控制导航及神经网络训练等热门实际 问题中。 在序贯蒙特卡罗方法中粒子滤波技术是一种基于b a y e s 原理用粒子概率密度 表示的序贯蒙特卡罗模拟方法“”“”，适用于任何能用状态空间模型以及用传统卡 尔曼滤波解决的非线性系统，包括序贯重要性采样法及其各种修正算法等。在蒙 特卡罗仿真中用一组由后验分布中提取出的加权粒子样本将连续的积分映射到离 散的求和过程，即利用以下经验估计式近似后验概率： 上 风i y u ) = 1 屹屯( ) ( 4 - 1 ) i - i 。 其中，随机样本 矗：i = l ，册由后验分布中取出，6 ( d - ) 表示d i r a c - d e l t a 函 数。期望运算： e ( g ) ) = i g a ( ) 瓜iyh)dxo，(牝) 其近似式： e ( g ，( ) ) = 1 ， 匹g ，( 矗) m 根据大数定理，有 e ( g ，( ) ) 应e ( g ，) ) ( 4 - 3 ) ( 年4 ) 其中，一代表准一致收敛。若g ，( ) 的后验方差有界，则下面的中心极限定理满 足： 4 n ( e ( g ，) ) 一地) ) ) 忌( o w 饥) 瓴( ) ) ) 件5 ) 其中，j 表示分布收敛。这样可以利用一个定义在有限离散点上的函数近似后验 分布。因此随着样本数n 的增加，根据大数定理期望求解可以由求和运算得到。不 幸的是，直接从后验密度函数采样一般是不太可行的，然而可以通过从一个已知 的，容易采样的参考分布g ( i 儿) 并利用下列式子解决： e ( 函( ) ) = j g 、嘞示p ( i x o , 可ly 石e ) g ( 1 ) | n “ 。丘) 裂口帆 其中，q ( 嘞) 是已知的非规范化的重要性权重： q ，= 鬟笋 降刀 需要的期望值： i n e g ，( 如) q ( 乇) e ( 岛( 炉= 堕可一( 4 - 8 ) 1 q ( 乇) = 晶阮成陇) 其中规范化的重要性权重由下式得出： 4 2 序贯重要性采样 粒子滤波是一种基于蒙特卡罗方法和递推贝叶斯估计的滤波方法其中用到 的一个核心算法是序贯重要性采样算法。 序贯重要性采样算法( s 唧啪削h p o r c 姐s m p l i 雌，s 璐) 【1 7 是一种序列蒙特 1 4 乒酽 = 斛 卡罗方法，它通过蒙特卡罗模拟实现递推贝叶斯滤波，是序贯蒙特卡罗( s m c ) 滤波 的基础。这种s m c 方法在有些文章中也称b o o t s t r a p 滤波、粒子滤波等。其核心思 想是利用一系列随机样本的加权和表示所需的后验概率密度，得到状态的估计值 在以下假设条件下，( g 。( j 。) ) 可以满足一致收敛及中心极限定理： ( 1 ) 矗对应一组取自参考分布的独立同分布的样本，参考分布的定义域要包含后 验分布的定义域，以及e ( g ( ”存在且是有穷的 ( 2 ) 后验概率的以期望存在且是有穷的。 于是当n 趋于无穷时，后验概率密度函数可以作以下近似： 瓶2 善耐屯) ( 4 - 1 0 1 为了在不改变先前的模拟状态一。的情况下x c t 时刻后验概率计算一个序贯的估 计，要用到以下形式的参考分布： q ( x o ，i y h ) = q ( x o ，- li y b 1 ) 叮( 一l 】r 旧- l ，y h ) ( 4 1 1 ) 若状态对应着一个马尔可夫过程以及观测与给定的状态条件无关时，可以得到： p c ) = 烈而) i l 鹏i 誓) 降1 2 ) “i ) = n 础jixj)(4-13) 则对重要性权值的递推估计式推导如下： 峨：j 坐d 堕丝鱼l 叮【_ liy b 。) 鼋“l - l ，) ：珥。j 堑止血丝堡l 一“p o i 一i ) p ( - 1 ) g “l 嘞耽- 1 ) ：雩磐掣( 4 - 1 4 ) q i 耳tl 耳甜i ，y h j 上式给f l i t 在给定参考分布g ( i + 儿) 时，序贯更新重要性权重的机制。由于 可以从参考分布中提取样本并评估概率和转移概率，计算中所要做的就是生成一 个先验的样本集并递推计算重要性权重，这个过程被称作序贯重要性采样 ( s e q u e m i a i m p o r g a l l c es a m p l i n g , s x s ) 4 3 序贯重要性采样存在问题及解决方法 然而，s i s 算法在高维空间时通常效率很低，并且随着时间t 的增加，重要性 权值的分布变的越来越倾斜。实际上，几步之后，可能只有一个粒子有非零权值。 结果，算法不能充分表达出我们所期望的后验概率。这就是m s l s 粒子滤波器引起 的退化现象1 1 7 。经过几次迭代，除了一个粒子外，所有粒子只具有微小的权值。 退化问题意味着大量工作均消耗在对p ( i 儿) = 0 的粒子更新上。对退化现象一个 恰当的测度是引入有效采样尺度* l ( 叫) 2 ， 0s 小的意味着存在有严重的退化现象。即使一个抽样粒子的权值接近单位l ， 而其他粒子权值接近0 。如果粒子具有相同权值叫= i i n ，则 o = ；如果一个 粒子权值为1 ，则 0 = 1 因此，当 0 下降到某一门限值( 2 ) 时，我们可 以采取重抽样的方法来处理退化问题。 为了避免上述退化现象的产生，主要有两种方法，选取适当的重要性函数和 进行再采样。 ( 一) 选取适当的重要性密度函数 选择重要性密度函数的两个主要原则1 1 礓醐2 1 l ： 1 ) 使得权系数的方差最小； 2 ) 从重要性密度函数中抽样容