（通信与信息系统专业论文）网络链路丢包率层析成像的应用研究.pdf

摘要 摘要 网络层析成像技术不需要中间节点的协作，通过网络边缘节点收集网络中端 到端的相关数据，采用统计推断等方法估计网络内部的状态参数。网络链路丢包 率层析成像是应用网络层析成像技术估计网络链路丢包率，可应用于路由选择、 优化网络、故障检测、流量工程、网络管理和控制等方面。本文将网络链路丢包 率层析成像应用于故障链路检测和无线传感网络路由选择中，提出了基于神经网 络进行故障诊断的方法和基于链路丢包率估计的定向扩散路由算法，并获得了良 好的效果。 首先，针对无线传感网络的有效性问题，提出了基于链路丢包率估计的定向 扩散路由协议，主要工作包括：( 1 ) 当采用定向扩散协议传输感知数据时，由于 每个节点都具有数据融合的功能，因此网络的逻辑拓扑形成了一棵以s i n k 节点( 汇 聚节点) 为根节点的反向多播树，s i n k 节点根据收到的感知数据，使用因子图的方 法估计链路的丢包率；( 2 ) 将监测任务用“属性值 对的命名机制描述为兴趣消 息，在一个固定的时间周期内，s i n k 节点对收集到的端到端信息进行分析并估计链 路的丢包率，丢包率信息将封装在兴趣消息中以广播的方式周期的向全网扩散； ( 3 ) 将链路丢包率信息纳入梯度管理中，在兴趣消息扩散过程中，收到兴趣消息 的节点建立到发送节点的梯度，同时记录到每个邻居节点的链路丢包率信息；( 4 ) 结合定向扩散中已经建立的时延信息并使用估计的链路丢包率信息进行选路，选 择低时延低丢包率的链路传输数据；( 5 ) 使用n s 2 网络仿真工具对该协议进行验 证，跟定向扩散路由协议相比该协议有效降低了端到端的平均丢包率，提高了网 络的可靠性。 其次，网络链路丢包率层析成像还可用于诊断故障链路，在本文中，提出了 使用神经网络进行故障诊断的方法，主要工作包括：( 1 ) 深入研究现有的两个经 典的故障链路诊断方法：s c f s ( s m a l l e s tc o n s i s t e n tf a i l u r es e t ) 算法和c l i n k ( c o n g e s t e dl i n k ) 算法，发现链路故障的先验概率是推断故障链路集合的前提条件； ( 2 ) 使用历史数据训练神经网络，获取链路状态的先验信息；( 3 ) 将后续的端到 端测量结果输入到训练好的神经网络，推断出故障链路集合；( 4 ) 使用m a t l a b 对提出的算法进行仿真，仿真结果显示该算法相对于c l i n k 算法能够更加有效的 摘要 诊断出网络中的故障链路。 关键词：网络层析成像，链路丢包率，路由选择，故障检测 h a b s t r a ( 了r a b s t r a c t n e t w o r kt o m o g r a p h yc a ne s t i m a t et h ei n t e r n a ls t a t eo ft h en e t w o r kp a r a m e t e r sb y m e t h o d so fs t a t i s t i c a li n f e r e n c eb a s e do nm ec o l l e c t i o no fe n d t o e n dr e l a t e d i n f o r m a t i o n ，w i t h o u tt h ec o l l a b o r a t i o no ft h ei n t e r n a ln o d e s i tc a nb eu s e dt oe s t i m a t e t h el i n k l o s sr a t ew h i c hc a nb ee x p l o i t e di nr o u t i n g ，n e t w o r ko p t i m i z a t i o n ，f a u l t d e t e c t i o n ，t r a f f i ce n g i n e e r i n g ，n e t w o r km a n a g e m e n ta n dc o n t r o la n ds oo n i nt h i sp a p e r , w ea p p l yt h el i n k - l o s si n f e r e n c et of a u l td e t e c t i o na n dw i r e l e s ss e n s o rn e t w o r k sr o u t i n g a n dp r o p o s et w oa l g o r i t h m s ，o n ei sn e u r a ln e t w o r kb a s e dc o n g e s t i o nl i n kd i a g n o s i sa n d t h eo t h e ri se s t i m a t e dl i n kl o s sr a t eb a s e dd i r e c t e dd i f f u s i o nr o u t i n gp r o t o c 0 1 1 1 1 et w o m e t h o d sh a v eb e e nv a l i d a t e db yd i f f e r e n ts i m u l a t i o nt o o l s a i m i n gt oe n h a n c et h ev a l i d i t yo fw i r e l e s ss e n s o rn e t w o r k s ，an e wp r o t o c o lw h i c h i sn a m e de s t i m a t e dl i n kl o s sr a t eb a s e dd i r e c t e dd i f f u s i o nr o u t i n gp r o t o c o lh a sb e e n p r o p o s e d t h em a i nt a s k si n c l u d e ： ( 1 ) s i n c ee v e r yn o d eh a st h ed a t af u s i o na b i l i t y , w h e ns e n s i n gd a t af l o wt os i n kn o d eb yu s i n gd i r e c t e dd i f f u s i o nr o u t i n gp r o t o c o l ，t h e l o g i c a lt o p o l o g yo ft h en e t w o r kf o r mar e v e r s em u l t i c a s tt r e ew h o s er o o ti ss i n kn o d e t h r o u g ha n a l y z i n gt h er e c e i v e dd a t ab yf a c t o rg r a p h ，t h el i n kl o s sr a t et a i lb ee s t i m a t e d ( 2 ) a s e n s i n gt a s ki sd e s c r i b e du s i n ga t t r i b u t e - v a l u en a m es c h e m e ，s u c had e s c r i p t i o n i sc a l l e da ni n t e r e s t d u r i n gaf i x e dp e r i o d ，t h el i n kl o s sr a t ei si n f e r r e da ts i n kn o d e t h r o u g ht h ee n d t o e n dd a t at r a n s m i s s i o ni n f o r m a t i o n ，t h e nt h ei n t e r e s tm e s s a g ew h i c h c o n t a i n st h el i n kl o s sr a t ew i l lb eb r o a d c a s tt ot h ee n t i r en e t w o r kp e r i o d i c a l l y ( 3 ) h l t h es t a g eo fg r a d i e n ts e t t i n gu p ，t h en o d ew h i c hr e c e i v e st h ei n t e r e s tw i l le s t a b l i s ht h e g r a d i e n tt ot h en o d ew h i c hs e n d st h em e s s a g ea n dr e c o r d st h el o s sr a t ei n f o r m a t i o no f e a c hn e i g h b o rn o d ef r o mt h ei n t e r e s tm e s s a g e ( 4 ) ，n l ed a t ap a c k e t sa r et r a n s m i t t e d a l o n gt h el i n kw i t ht h el o w e s tl i n kp a c k e tl o s sr a t ea n dd e l a y ( 5 ) t i l i sa l g o r i t h mc a n i m p r o v et h en e t w o r kq u a l i t yo fs e r v i c ei na s p e c t so fp a c k e tl o s sr a t ea n dl i n kd e l a y , a n d t h es i m u l a t i o nr e s u l t ss h o wt h a tt h i sp r o t o c o li ss u p e r i o rt od i r e c t e dd i f f u s i o np r o t o c o li n t e r m so fe n d - t o e n da v e r a g ep a c k e tl o s sr a t e l i n kl o s sr a t e st o m o g r a p h yc a na l s ob ea p p l i e dt of i n d i n gt h ec o n g e s t i o nl i n k i n i l l a b s t r a c t t h i sp a p e r , a na l g o r i t h mw h i c hc a l l e dn e u r a ln e t w o r kb a s e dc o n g e s t i o nl i n kd i a g n o s i s h a sb e e np r o p o s e d t h em a i nt a s k sc o n t a i n ：( 1 ) t h r o u g hi n d e p t hs t u d y i n go f t h es c f s ( s m a l l e s tc o n s i s t e n tf a i l u r es e t ) a l g o r i t h ma n dt h ec l i n k ( c o n g e s t e dl i n k ) m g o r i t h m w h i c ha r et w oc l a s s i cc o n g e s t i o nl i n kd i a g n o s i sm e t h o d s ，w ef i n dt h a tt h ep r i o r p r o b a b i l i t yi s t h ep r e c o n d i t i o no fi n f e r r i n gc o n g e s t e dl i n k ss e t ( 2 ) t h ep r i o r i n f o r m a t i o no fl i n ks t a t u si so b t a i n e db yt r a i n i n gt h en e u r a ln e t w o r k 、加lt h eh i s t o r i c a l d a t a ( 3 ) e x p l o i t i n gt h et r a i n e dn e t w o r k ，i n p u tan e we n d - t o e n dm e a s u r e m e n t st o d i a g n o s et h et r u ec o n g e s t e dl i n ks e t ( 4 ) c o m p a r e dw i t ht h ec l i n ka l g o r i t h m t h e s i m u l a t i o nh a ss h o w nt h a tt h ea l g o r i t h mw ep r o p o s e dh a sag o o dp e r f o r m a n c ei nf i n d i n g t h ec o n g e s t i o nl i n k k e y w o r d s ：n e t w o r kt o m o g r a p h y , l i n kl o s sr a t e ，r o u t e ，c o n g e s t i o nl i n kd i a g n o s i s i v 图目录 图目录 图2 1 网络逻辑拓扑结构一7 图2 - 2 多播网络链路丢包率估计网络拓扑结构l o 图2 - 3w s n 的数据融合机制1 5 图2 - 4 无线传感网络模型1 6 图2 5 函数z ( 西，x 2 ) l ( x ：，x 3 ) a ( x ：，_ ) 的因子图1 7 图2 6 函数兀吃( 群，炜旧( 础，群) 的因子图1 9 图2 - 7 简化后1 的因子图2 0 图3 1 兴趣消息扩散形式一2 3 图3 - 2 梯度信息网2 3 图3 3s i n k 节点加强的传输路径2 4 图3 - 4l r e - d d 协议工作流程2 5 图3 5 兴趣扩散2 8 图3 - 6 兴趣缓存格式2 8 图3 7 建立梯度3 0 图3 8 节点i 的梯度域3 0 图3 - 9 时延为标准选择路径3 1 图3 - 1 0 结合时延和丢包率为标准选择路径3 1 图3 1 1 端到端数据报文平均丢包率3 6 图3 - 1 2 平均链路丢包率3 7 图3 1 3 平均时延3 8 图3 1 45 0 个节点组成的网络的链路丢包率一3 8 图3 1 55 0 个节点组成的网络的端到端数据报文丢包率3 9 图3 1 61 0 0 个节点组成的网络的链路丢包率3 9 图3 1 71 0 0 个节点组成的网络的端到端数据报文丢包率4 0 图4 1 网络逻辑拓扑结构4 1 图4 2 最大坏子树4 3 图4 3 未使用s c f s 算法故障诊断结果4 4 i 图目录 图4 _ 4 使用s c f s 算法故障诊断结果4 4 图4 5 线性代数表示拓扑结构4 6 图4 6 神经元模型5 2 图4 7 硬限幅器函数5 3 图4 8 饱和线性激活函数5 3 图4 9 不同参数对应的双曲正切s 形函数5 4 图4 - 10 前馈三层感知器结构5 5 图4 1 1c l i n k 和n l i n k 故障链路检出率性能结果5 9 图4 1 2c l i n k 和n l i n k 误检率性能结果6 0 表目录 表目录 表3 - 1 无线节点配置3 3 表3 2 不同场景下2 5 个节点的链路丢包率3 4 表3 3 不同场景下2 5 个节点的端到端丢包率3 4 表3 _ 4 不同场景下5 0 个节点的链路丢包率3 4 表3 5 不同场景下5 0 个节点的端到端丢包率3 4 表3 6 不同场景下7 5 个节点的链路丢包率3 4 表3 7 不同场景下7 5 个节点的端到端丢包率3 5 表3 8 不同场景下10 0 个节点的链路丢包率3 5 表3 - 9 不同场景下10 0 个节点的端到端丢包率3 5 表3 1 0 不同场景下1 2 5 个节点的链路丢包率一3 5 表3 1 1 不同场景下1 2 5 个节点的端到端丢包率3 5 表3 1 2 不同场景下15 0 个节点的链路丢包率。3 5 表3 1 3 不同场景下1 5 0 个节点的端到端丢包率3 6 i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：庄垡嗍列啤占月；日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：庄遵 导师签名：逍佥迫 e t 期：弘l 口年占月弓日 第一章绪论 1 1 研究背景及意义 第一章绪论 网络内部状态参数( 如网络链路丢包率和时延等) 是衡量和评估网络性能的 重要依据，获取这些参数对及时发现网络故障、优化网络性能、提高网络服务质 量和重新布局新网络有重要的意义，已经成为国内外学术界和工业界研究的前沿 学科课题。目前，网络测型l 】是理解和认识网络行为和特征的有效方法之一，是估 计网络内部性能参数的主要方法，它对网络行为进行特征化、对各项性能指标进 行量化，是充分理解与准确认识网络的最基本的手段，涵盖的内容非常广泛，包 括网络链路丢包率、带宽、时延、距离测量、拓扑发现、路由器流量测量、路由 器调度策略和瓶颈缓冲器容量测量。 传统的网络测量【2 1 方法主要是在网络节点或网络节点之间直接主动或被动的 测量网络的各种性能参数。这种测量方法需要各个不同域内的通信节点进行充分 的协作，但是，实现各运营商共同协作测量网络参数是相当困难的，即使在同一 个运营商内部，考虑安全因素，通常也只会提供部分节点完成一定程度的协作工 作。由于传统的网络测量存在很多限制以及不适合大规模网络等缺点，引入了端 到端测量方法，该方法测量【2 】网络性能参数普遍依赖于i c m p 包，而从安全或性能 方面考虑，路由器会降低对i c m p 包的优先级，这样获得的测量数据不能完全表 征实际网络的状态参数；在某些情况下，路由器将过滤掉i c m p 包，甚至不响应 i c m p 包，这些原因都限制了该方法的应用。 传统网络测量和上述的端到端工具测量网络性能参数的方法在不同程度上都 存在有缺陷，而日益复杂和庞大的互联网系统导致对网络内部参数的测量越来越 困难，这些都促使国内外许多研究机构开始寻找其它的途径来研究网络内部性能 参数和网络整体性能，现在比较有效的技术为网络层析成像技术 3 - 5 】( n e t w o r k t o m o g r a p h y ) ，它成功的将医学、地震学、地质勘探等领域的成熟理论和方法应 用于通信网络领域，与以上提到的端到端测量方法相比，它不需要中间节点的协 作，通过网络边缘节点收集网络中端到端的相关数据，采用统计推断等方法估计 网络内部的状态参数。网络层析成像技术主要是用于估计链路级( l i n k l c v d ) 参 数睁1 0 】，通过主动发送探测包( p r o b ep a c k e t ) 给指定节点，收集和分析目的节点所 电子科大学硕士学位论文 得到的信息，或者采用被动的方式收集网络内部通信流量，最后利用统计学理论 推导出网络内各种链路参数；从其反问题求解的角度该技术也包括o d ( o r i g i n d e s t i n a t i o n ) 流的估计【1 1 】等，主要是利用测量的链路级数据估计路径级的 参数。网络层析成像为建立精确的网络模型提供了重要的手段，为网络优化设计、 提高网络的可靠性等提供了重要的前提，研究该技术的意义主要体现在： 1 ) 它是建立精确互联网网络行为模型的重要手段，为设计新的网络协议和开 发高性能网络设备提供理论基础； 2 ) 它是发现网络瓶颈、了解网络运行状况、进行宏观网络管理和控制及优化 网络资源的重要依据； 3 ) 它可应用于保障网络安全等方面，如网络链路丢包率层析成像在路由选 择、优化网络、故障检测、网络管理和控制等方面都具有重要作用。 本文研究重点是网络链路丢包率层析成像技术的应用，其一是利用链路丢包率 层析成像技术估计网络链路丢包率，然后将估计结果应用于无线传感网络路由选 择中；其二是利用网络链路丢包率层析成像对故障链路进行检测。 1 2 研究现状 1 2 1 网络链路丢包率层析成像研究现状 网络层析成像始于马萨诸塞州大学的m i n c t 程【1 2 】对多播网络层析成像的研 究并吸引了大量学者对该领域进行研究睁1 0 1 。 多播网络估计链路丢包率具有一个良好的特性，探测包在公共路径上的相关 性达到了1 0 0 ，利用这种相关性，r c a c e r e s 等人【6 】率先使用多播的方法计算链路 的丢包率，源节点通过主动向目的节点发送多播探测包，利用公共路径的相关性 建立高阶方程组，最后采用e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法求解方程组得到 每条链路的丢包率。文献 7 提到了另一种计算链路丢包率的方法，仍然通过主动 向网络中发送多播探测包建立节点与子节点之间的丢包相关性最后用m l e 方法计 算链路的丢包率。 使用多播的方法可以准确的估计出链路的丢包率，但现在多数网络的通信方 式都不支持网络级的多播，而且多播估计出来的丢包率与单播存在很大的差别， 当网络流量主要是由单播流量构成时，使用多播的方法观测到的链路丢包率就不 能反映网络的真实状况，以上局限性引出了端到端的单播测量方法的研究，单播 2 第一章绪论 网络链路丢包率层析成像的关键问题在于：使用单播不能得到网络的路径级到链 路级的唯一的映射，致使无法求解具体的丢包率值。 m c o a t e s 等人【8 】提出使用背靠背单播探测包测量链路丢包率的方法解决了单 播网络链路丢包率层析成像的欠定性方程问题，通过向网络中的节点主动发送背 靠背单播探测包( 背靠背包是在空间上挨的很近的两个包) ，虽然探测包的目的节 点可能不同，但会拥有一些共同的链路，在这些公共链路上，包的传输性能具有 很强的相关性，利用这种相关性来模拟多播网络中公共路径上的相关性，最后通 过求解最大似然方程来估计链路的丢包率。t i a nb u l 9 】等把该方法推广到一般网状 拓扑中使用e m 算法估计链路丢包率。n g d u f f i e l d 1 0 】提出采用三包组的方法探测 链路的丢包率，由于三包组更接近于多播，所以使用该方法提高了单播网络中的 丢包率估计的准确性，但要付出向网络中发送大量探测包的代价。 以上介绍的使用单播估计链路丢包率的方法都需要主动发送探测包，通过被 动抽取单播流量形成了单播被动网络链路丢包率层析成像，其实现方法是抽取网 络中的两个紧挨着的探测包作为背靠背包，一般选取t c p 包作为抽取对象来建立 链路丢包率关系方程，对于待估计参数是恒定的，可以采取最大似然方式求解， 对于待估计参数是时变的则采用贝叶斯方法求取链路的丢包率。文献 1 3 1 1 4 都是 采用被动的方法从网络中抽取单播探测包，然后前者使用e m 算法估计丢包率， 后者使用贝叶斯方法获取丢包率。 网络层析成像技术估计网络内部状态参数的方法同样可以应用于无线网络 中，y m a o 1 5 】等人针对无线传感网络，当源节点向s i n k 节点传输感知数据时，由 于使用数据融合机制网络的逻辑拓扑形成了一棵以s i n k 节点为根节点的反向多播 树，然后s i n k 节点统计分析收到的数据，使用因子图的方法估计链路丢包率。 1 2 2 网络链路丢包率层析成像应用研究现状 网络链路丢包率层析成像的应用非常广泛，如应用于提高网络服务质量，进 行故障链路检测等。 dg u o 等人【1 6 】使用网络层析成像技术估计网络链路丢包率，并将估计结果应 用于预测网络吞吐量性能。首先，将网络链路丢包率问题归结为贝叶斯估计问题， 然后使马尔可夫链蒙特卡洛( m c m c ) 算法解决该问题，最后基于估计的链路丢 包率参数进一步预测t c p 网络的吞吐量性能。 应用网络链路丢包率层析成像技术对故障链路进行检测。nd u f f i e l d 等人【1 7 】 3 电子科大学硕士学位论文 在假设故障链路先验概率相同的条件下提出了一个简单快速的推断网络中故障链 路的方法s c f s 算法，该算法使用端到端不相关测量方法估计网络中的故障链路， 对于无法判断性能的链路，首先找出最大坏子树，认为故障链路发生在最大坏子 树的主干链路上，而不是分支链路上。s c f s 算法在故障链路先验概率小的情况下， 可以有效的检测出网络中的故障链路，在先验概率为0 2 时，故障链路检出率仅有 3 0 ，因此h x n g u y e n 等人【l8 】在计算先验概率的基础上，提出了c l i n k 算法推 断网络中的故障链路，该算法通过在一个时间周期内对网络的多次测量来获得网 络中链路性能状态的先验概率，然后利用已知的先验信息对后续网络中的故障链 路进行检测，该算法跟s c f s 算法相比，能够更加有效的检测出网络中的故障链路。 dr u b e n s t e i n 等人 1 9 】使用端到端测量技术推断网络中共享链路的拥塞状况，网 络数据流之间协作的拥塞控制策略能够提高网络的性能。文献中首先定义了数据 流拥塞相同的概念：当相同资源集合中的两个数据流因从队列中溢出或备份而都 被丢弃或有较大的时延时，两个数据流的拥塞状况相同；然后使用端到端技术通 过在目的节点观测网络的链路丢包率或时延等参数推断在相同的网络资源下共享 链路是否拥有相同的拥塞状况。 1 3 本文主要研究内容和工作 获取网络的链路丢包率信息有助于网络管理员检测网络故障以保障网络的安 全可靠；在路由选择时避开丢包率大的链路以提高网络的服务质量；在规划和建 设网络时以满足网络预见性和应用可靠性的要求，因此网络链路级丢包估计是网 络层析成像技术研究的重要部分。本文主要研究内容是网络链路丢包率层析成像 的应用，其一是利用网络链路丢包率层析成像技术估计链路丢包率并将其结果应 用于无线传感网络路由选择中，其二是使用网络链路丢包率层析成像技术对故障 链路进行诊断，研究工作由以下组成： 首先，对网络链路丢包率层析成像技术做了深入的研究。目前，提出的用于 估计链路丢包率的方法有多播网络链路丢包率层析成像和单播网络链路丢包率层 析成像，在本文中，主要针对无线传感网络这一特殊的网络，介绍了使用因子图 估计传感网络链路丢包率的方法。首先，基于无线传感网络的数据融合机制，当 源节点向s i n k 节点传输感知数据时，网络的逻辑拓扑形成了一棵以s i n k 节点为根 节点的反向多播树；然后，通过在s i n k 节点分析收集到的端到端传输信息，使用 因子图的方法估计链路丢包率。 4 第一章绪论 其次，将链路丢包率估计结果应用于无线传感网络路由选择中，在定向扩散 路由协议的基础上，提出了基于链路丢包率估计的定向扩散路由协议( l r e d d ) 。 主要内容包括：将监测任务用“属性值对的命名机制描述为兴趣消息，由于 定向扩散路由协议采用了数据融合机制，因此在传输感知数据时网络的逻辑拓扑 为一棵以s i n k 节点为根节点的反向多播树，通过在一个固定的时间周期内，s i n k 节点对收集到的端到端信息进行分析就可以估计出链路的丢包率，丢包率信息将 封装在兴趣消息中以广播的方式周期的向全网扩散；将链路丢包率信息纳入梯 度管理中，在兴趣消息扩散过程中，收到兴趣消息的节点建立到发送节点的梯度， 同时记录到每个邻居节点的链路丢包率信息；结合定向扩散中已经建立的时延 信息并使用估计的链路丢包率信息进行选路，选择低时延低丢包率的链路传输数 据；通过n s 2 网络仿真工具对提出的协议进行验证，跟定向扩散路由协议相比 该协议有效的降低了端到端的平均丢包率，提高了网络的可靠性。 最后，应用网络链路丢包率层析成像技术对网络中的故障链路进行检测。在 本文中，提出了使用神经网络进行故障诊断的方法( m ，姗 f l2 n dp a c k e tp ( i ) 一f ) ( 2 6 ) 其中p ( i ) 一i 表示一个包从父节点p ( f ) 成功传输到节点f ，式2 - 6 所表示的含义为 包对中的第二个包成功接收的条件下，第一个包成功接受的概率是x ，此时丢弃 的概率是1 7 , - ，由第二个包成功到达节点f 说明当第一个包到达时链路i 的队列还 没有满，所以可以认为形一1 ，通过观测网络的行为，该结论已经得到了证明【1 8 1 。 使用y 兰 形匕表示所有链路条件成功接收概率集合。 假设有大量的背靠背包发往不同的目的节点，第一个发往目的节点s ，另一个 发往目的节点t ，两对背靠背包的发送间隔要大于两个包对之间的发送间隔。使用 咒。，表示目的节点t 成功接收到的第二个探测包的个数，使用m ，表示包对中的两个 包都分别成功到达各自目的节点的个数，即是说背靠背包中的第一个成功到达了 节点j 且第二个到达了目的节点t 的包对数。通过以上对栉。，和所。，的定义，在给定 刀，的条件下聊。的可能性使用二项式表示为 ，、 z ( 他。，l 体，f ，见，) = i ：jf 站7 ( 1 一只。) 吨。 ( 2 - 7 ) ”t 为了更好的说明式2 7 中的只j ，使用绋，吼分别表示从源节点发往目的节点 5 的路径和发往目的节点t 的路径，靠，表示吼和毋所拥有的公共链路的条件成功传 输概率之积，吼表示吼除掉与g f 的公共链路，剩下所有链路的成功传输概率之积， 同理定义，则见j 为哎q ，由此得出整体似然函数，使用函数2 8 表示 1 2 第二章网络链路丢包率层析成像理论 l ( mln ，p ) - - i i ，( i 吃，p k ) x h ，j z ( 一in , ，见j ) ( 2 8 ) 使用网络层析成像计算网络链路丢包率的问题就转变为计算向量y 和口使函 数2 8 达到最大值，由于单个似然函数j ( 他j ，见) 和z ( ，i 吩，只，) 是链路成功传 输概率口和( 或) 链路成功传输概率y 的乘积，所以计算似然函数的最大值是很困 难的，文献 7 】使用e m 算法求解参数y 和口，e m 算法具有稳定可扩展的程序并且 随着网络维数的增加复杂度是呈线性增加的，文献 1 3 】和【2 2 】通过收集源节点和目 的节点之间的t c p 连接流，使用n s 2 网络仿真软件对单播网络链路丢包率估计 进行了评估。 2 2 2 2 包组模型估计单播网络链路丢包率 使用单播网络层析成像估计链路丢包率实际上就是向单播网络中发送单播探 测包来模拟多播的特性，然而使用背靠背探测包并不能保证两个探测包在公共路 径上的相关性达到1 0 0 ，因此n g d i f f i e l d 等人【1o 】提出了使用包组来增加单播探 测包之间的相关性使对链路丢包率的估计更加的精确。 在使用背靠背探测包估计链路丢包率时xz1 ，并且定义了形是在第二个包成 功接受的条件下第一个包成功接受的概率，因为第二个包成功到达了目的节点i ， 所以断定在公共路径上第一个包也是成功传输的，但在不是完全相关的条件下， 第一个探测包在公共路径上的传输不一定成功，这些就导致了对x 的估计偏低从 而影响了对链路丢包率的估计，使用包组的方法增加了包之间的相关性，从而提 高了 ，使它更接近于多播。 最简单的使用包组的例子是向网络中发送三包组【l o 】，如图2 2 所示，发送三 包组 ，那么在第二个，第三个探测包到达目的节点的条件下，第一个到达 目的节点的概率也将更大。使用或表示由源节点发往目的节点的所有探测包， dcd o 表示通过链路z 到达目的节点的探测包。定义在某个节点的包组传输具有 结合性( c o a l e s c e n t ) ，如果对于通过节点z 的包组( ，；乞，r a ) 与dcd o 没有交集， 则有d 7 c d 且任意的d c d 满足下面的表达式 彤( d l d ) 以( d l d ) 结合性表明了在更多的包组成功通过某条链路的条件下，接下来的包组通过该链 路的可能性也更大。为了加强包组之间的相关性，文献 1 0 】对进一步增加包组的长 度进行了讨论，如发展为四包组、五包组等，发现随着包组长度的增加精度并没 有更多的提高，所以一般使用包组估计链路丢包率时就使用三包组。 1 3 电子科大学硕士学位论文 2 2 3 无线传感网络( w s n ) 链路丢包率估计 以上提到的使用网络层析成像的方法估计单播和多播网络链路丢包率的方法 一般都要主动向网络中发送探测包，这就非常不适用于节点处理能力和能量都受 限的无线传感网络【2 3 1 ，向网络中发送大量的探测包必然增重网络负载，占用网络 带宽，增大每个节点能量的消耗，而这些资源在无线传感网络中都是极其宝贵的； 无线传感网络中的节点主要是为了感知周围的信息然后传送给s i n k 节点，所以在 以数据为中心的w s n 中也不易收集到有关联的包对或包组，这样单播网络被动收 集数据信息估计链路丢包率的方法也不适用。文献【1 5 提出了使用数据融合技术构 建一棵以s i n k 节点为根的反向多播树，采集的数据信息沿着这棵树发送到s i n k 节 点，s i n k 节点根据收到的数据信息使用网络层析成像的方法计算链路丢包率，通过 正常的传感器节点向目的节点传输采集数据信息，不用增加任何网络的负担就可 以计算链路的丢包率，在本文中就是使用这种办法来估计链路丢包率的，并将估 计结果用于无线传感网络路由选择中。 2 2 3 1 估计模型 数据融创2 4 】【2 5 】( d a t aa g g r e g a t i o n ) 技术是设计w s n 路由协议时需要考虑到的 一个重要因素，无线传感网络节点众多，网络中有较大的冗余数据，数据融合是 从消除数据冗余的角度来减少数据传输量，达到节省能耗的目的，它只需要传感 器节点进行少量的计算和资源的消耗。数据融合处理数据的过程是：网络中的节 点等待一个时长或等收到所有叶子节点发送给自己的数据后，将所收到的数据和 自己的数据进行融合后再转发给下一个节点发往s i n k 节点，通过在每个节点都使 用数据融合技术就形成了一个以s i n k 节点为根的反向多播树【3 j 。图2 3 给出了一个 数据融合的例子，图中节点s 为s i n k 节点，其它为感知数据节点，节点a 将自己 的数据( a ) 发往s i n k 节点，下一跳是c ，节点b 发送自己的数据( b ) 给s i n k 节 点，下一跳是c ，节点c 将自己的数据( c ) 加上收到的数据( a ) 、( b ) 一起融 合成( a ，b ，c ) 发送给s i n k 节点。 1 4 第二章网络链路丢包率层析成像理论 o o o o s o o )o b o 传感器节点 。 图2 3w s n 的数据融合机制 为了便于研究和描述，使用有向图为无线传感网络建模，有向图中的点对应 于网络中的终端节点，路由器或者是s i n k 节点，每个有向边对应于网络中两个节 点之间的链路，方向表示链路上数据流动的方向。基于数据融合，无线传感网络 可以描述为一个以s i n k 节点为根的反向多播树，采集的数据信息由每个叶子节点 发往s i i l l 【节点。在以下本文中所提到的“链路”可以是一个由几条相连接的物理 链路组成的路径，只要在该路径的中间节点没有延伸出其它路径，“路径 是指从 一个终端节点开始到s i n k 节点结束的一个路径，节点成功接收数据包是指所有数 据包括融合的数据一起成功到达该节点。基于网络层析成像技术估计链路丢包率 的思想【l5 】是：所有终端节点都不间断的同步的给s i n k 节点发送包，如果在一个特 定的时间帧内没有收到包，则说明在传输路径的某条链路上发生了丢包，通过观 测每个从源节点到s i n k 节点的包是否成功到达可以在s i n k 节点推测网络中每条链 路的丢包率。 我们使用e 表示网络中所有链路集合，形表示所有路径集合。对于每个链路 e ee 都与一个状态t 相关联，t 的取值为0 或l ，o 表示链路e 处于“坏 链路 状态，所有由该链路传输的数据包都被丢弃，1 表示链路p 为“好链路，数据包 可以在该链路上成功传输，在本节的描述都将使用1 表示好链路，0 表示坏链路。 对于每个路径w ew ，它的状态可以表示为组成该路径的所有链路的逻辑与，记为 式2 - 9 ，其中。表示逻辑与，x 。，为路径w 的状态。 x ，= ox 。 ( 2 9 ) e r 如图2 - 4 所示为一个简单的无线传感网络模型图，有三条链路，、m 和以和两条路 径 z ，力】和 聊，z 】，链路状态和路径状态的关系是_ 抽，= 而o 且薯m ，= o 。当 且仅当路径w 的状态k 为1 时，所有以该路径传输的包不会被丢弃，由此使用某 1 5 电子科大学硕士学位论文 条路径传输的数据包是否被成功接收就能推断该条路径的状态。 图2 4 无线传感网络模型 在每个时间点，设链路状态t 为1 的概率为睨，则t 为0 的概率为1 一睨。可 以假定，在一个相对小的时窗内，当数以百计的数据包发往s i n k 节点时，每条链 路的睨是个常数，也就是说此时可以认为链路是准静态的。用表示链路e 在时 间点o = 1 ，2 ，行) 的状态，这样路径w 在时间点的状态表示为= o n 。当 在时间t ，所有终端都向s i n k 节点发送数据包时，通过观测数据包是否到达s i n k 节点可以获取所有路径在时间点t 的状态。记群# z o ：e ee ， 碟； ：w ew 】，霹j 净 群：j f f 】，砧j # 硝：s f 4 ， ：= ：e ee 1 。估计网络中链路丢包率的问题就转化为在观测霹川的基础上计 算诉的问题，进一步问题可以转化为，对于每个e e ，在观测碟川) 的条件下， 估计a e 的最大化后验概率研哎i 碟川 ，用吃表示，在本文中，介绍使用因子图的 方法计算允。 2 2 3 2 因子图与和积算法 因子图模型和用于解决因子图的和积算法几乎涵盖了用于通信领域的所有信 道译码算法，如v i t e r b i 算法、b c j r 算法、k a l m a n 滤波、f f t 等，因此因子图模 型被广泛的应用于电子工程和计算机科学。 因子刚2 6 】【2 7 】( 指乘积因子图) 表示把一个多元函数转化为函数乘积( 因子) 结构的二分图( b i - p a r t i t eg r a p h ) ，每个因子由变量子集构成，它由两种类型的节点 组成，变量节点对