网络通信信道的隐马尔科夫模型.ppt

HiddenMarkovModelingfornetworkcommunicationchannels 网络通信信道的隐马尔科夫模型 Authors Kav Salamatian SandrineVatonPresentedby Xubo 2008年7月15日 网络通信信道的隐马尔科夫模型 2 主要内容 需要解决的问题马尔科夫链隐马尔科夫链 HMM 利用HMM解决问题 网络通信信道的隐马尔科夫模型 3 需要解决的问题 IPPM定义了许多不同的端到端性能指标 时延 丢包率 可用带宽 时延抖动 网络状态 网络通信信道的隐马尔科夫模型 4 需要解决的问题 网络通信信道的隐马尔科夫模型 5 需要解决的问题 网络通信信道的隐马尔科夫模型 6 需要解决的问题 时延 丢包率 可用带宽 时延抖动 模型 网络状态 网络通信信道的隐马尔科夫模型 7 马尔科夫链 1870年 俄国有机化学家VladimirV Markovnikov第一次提出马尔科夫模型 网络通信信道的隐马尔科夫模型 8 马尔科夫链 马尔可夫性如果一个过程的 将来 仅依赖 现在 而不依赖 过去 则此过程具有马尔可夫性 或称此过程为马尔可夫过程X t 1 f X t 网络通信信道的隐马尔科夫模型 9 马尔科夫链 时间和状态都离散的马尔科夫过程称为马尔科夫链 记作 Xn X n n 0 1 2 在时间集T1 0 1 2 上对离散状态的过程相继观察的结果链的状态空间记做I a1 a2 ai R 条件概率Pij m m n P Xm n aj Xm ai 为马氏链在时刻m处于状态ai条件下 在时刻m n转移到状态aj的转移概率 网络通信信道的隐马尔科夫模型 10 马尔科夫链 转移概率矩阵 阴天 晴天 下雨 晴天阴天下雨晴天0 500 250 25阴天0 3750 250 375下雨0 250 1250 625 网络通信信道的隐马尔科夫模型 11 马尔科夫链 转移概率矩阵由于链在时刻m从任何一个状态ai出发 到另一时刻m n 必然转移到a1 a2 诸状态中的某一个 所以有当Pij m m n 与m无关时 称马尔科夫链为齐次马尔科夫链 通常说的马尔科夫链都是指齐次马尔科夫链 网络通信信道的隐马尔科夫模型 12 HMM实例 网络通信信道的隐马尔科夫模型 13 HMM实例 在上述实验中 有几个要点需要注意 缸间的转移不能被直接观察从缸中所选取的球的颜色和缸并不是一一对应的每次选取哪个缸由一组转移概率决定 网络通信信道的隐马尔科夫模型 14 HMM概念 HMM的状态是不确定或不可见的 只有通过观测序列的随机过程才能表现出来观察到的事件与状态并不是一一对应 而是通过一组概率分布相联系HMM是一个双重随机过程 两个组成部分 马尔可夫链 描述状态的转移 用转移概率描述一般随机过程 描述状态与观察序列间的关系 用观察值概率描述 网络通信信道的隐马尔科夫模型 15 HMM的基本要素 用模型五元组 N M A B 用来描述HMM 或简写为 A B 网络通信信道的隐马尔科夫模型 16 HMM可解决的问题 问题1 给定观察序列O O1 O2 OT 以及模型 A B 如何计算P O 问题2 给定观察序列O O1 O2 OT以及模型 如何选择一个对应的状态序列S q1 q2 qT 使得S能够最为合理的解释观察序列O 问题3 如何调整模型参数 A B 使得P O 最大 网络通信信道的隐马尔科夫模型 17 HMM建模 本文研究报文丢失过程及网络状态和参数估计问题使用open close过程可以描述因特网中的报文丢失过程 但是有时候报文的丢失率会有较大的波动 作者认为网络信道具有隐藏的不同状态 在不同的状态下 报文的丢失率会有所不同 状态的转换会引起丢失率的波动 网络通信信道的隐马尔科夫模型 18 HMM建模 假定丢失过程为 如果第t个报文到达了接收端 则Xt 0 否则Xt 1马尔科夫链的状态空间为S 1 2 3 K 共有K个状态 它们之间的转换由马尔科夫链Y Yt 所决定随机过程的状态转移矩阵表示为其中这个马尔科夫链是均匀的 各态遍历的 状态收敛的 它的稳态分布表示为 网络通信信道的隐马尔科夫模型 19 HMM建模 在每一种状态下 信道都会有blocking和passing两种状态使用矩阵P来表示信道的丢失概率 则有 P 1 i k 其中 表示信道处于i状态时 第t个报文丢失的概率 网络通信信道的隐马尔科夫模型 20 HMM建模 通信信道模型 状态个数K 状态转移矩阵 信道的丢失概率矩阵P 网络通信信道的隐马尔科夫模型 21 HMM状态个数统计量 为了给HMM选择一个恰当的状态数目 需要一个基于已经观察到的丢失过程X的无偏估计量 离散型随机变量X的熵定义为稳态随机变量X Xi 的熵定义为 1 J ZivandN Merhav Estimatingthenumberofstatesofanite statesource IEEETrans Info Theory vol IT 38 pp 61 65 January1992 网络通信信道的隐马尔科夫模型 22 HMM状态个数统计量 根据文献 2 中介绍的AEP 渐进均分割性 如果随机过程X是有限的 稳态的 各态遍历的 那么就会有下面的推导 根据前面的推导 作者定义了HMM状态个数K的估计量公式 2 T CoverandJ Thomas ElementsofInformationtheory JohnWileyandSons 1991 网络通信信道的隐马尔科夫模型 23 HMM状态个数统计量 这个式子确切的说就是在参数为 状态数为j的情况下 输出序列为x的最大概率 如何选择参数 使得出现观察序列x的可能性最大 如何估计随机过程的熵H 使用文献 4 中介绍的通用压缩编码的方法 Lempel Ziv 使用文献 5 中介绍的算术译码的方法来解决 3 J ZivandN Merhav Estimatingthenumberofstatesofanite statesource IEEETrans Info Theory vol IT 38 pp 61 65 January1992 4 J ZivandA Lempel Auniversalalgorithmforsequentialdatacompression IEEETrans Info Theory vol IT 23 pp 337 343 May1977 5 A Moat Lineartimeadaptivearithmeticcoding IEEETrans Info Theory vol IT 36 pp 401 406 March1990 网络通信信道的隐马尔科夫模型 24 使用EM算法推断信道参数 由于马尔科夫链的状态是不明显的 必须使用隐藏在丢失过程中的信息来估计参数集合 作者使用EM 最大似然估计 的方法来估计这个参数集合 EM算法是一个估计各种马尔科夫模型参数的最大似然估计方法 它有很多的优点 特别是它的稳定性 每一次的反复都将提高模型的似然度 这就保证了算法的收敛 网络通信信道的隐马尔科夫模型 25 推断信道状态 作者使用两种算法推断信道状态MPM MarginalPosteriorMode 边界后验模式 根据观察到的丢失过程来估计当前最有可能的状态Viterbi算法使用丢失过程来估计最有可能的状态序列 网络通信信道的隐马尔科夫模型 26 MPM 时刻t的最优状态估计值 这个估计量可以用在自适应程序中 用来实时的计算信道状态 可以将作为网络拥塞的标识 它比使用单个报文判断网络状态要准确很多 网