高阶马尔可夫链无线链路连通性建模

陈冬明，汪 洋，张继良，李 银，向少华

(1.哈尔滨工业大学深圳研究生院，518055广东深圳;2.深圳国家高技术产业创新中心，518063广东深圳)

移动自组织网络具有无中心、自组织、节点可移动等特点，受到广泛关注［1］.在移动自组织网络中，端对端的通信路径由一个或多个无线链路组成，链路性能将直接影响网络通信质量［2］.链路连通性是无线链路最基本特性［3］，链路连通性研究对网络拓扑控制和路由协议分析等有着重要指导意义［4］.

目前，移动自组织网络链路连通性研究方法主要有蒙特卡洛仿真和一阶马尔可夫模型.早期链路连通性研究主要采用蒙特卡洛仿真方法［5-6］.GERHARZ M 等［5］最早利用蒙特卡洛仿真方法，分析了不同运动模型下的链路特性.在此基础上，BAI F等［6］基于蒙特卡洛仿真分析了通信路径稳定性，并改进路由协议.当仿真数据量足够大时，蒙特卡洛仿真结果比较接近实际情况，但实验所需的时间长、数据存储空间大，形成研发瓶颈.为了有效评估移动自组织网络的连通特性，需针对特定环境设计链路连通性模型.传统的链路连通性建模主要采用一阶马尔可夫模型，可分为两状态一阶马尔可夫模型［7-8］和多状态一阶马尔可夫模型［9-10］.最早，GRUBER I等［7］根据两状态一阶马尔可夫模型，结合节点传输范围和节点移动模型，理论推导了链路剩余生命时间等链路特性函数.QIN M等［8］将两状态一阶马尔可夫模型应用于支持多媒体流的无线链路可用性预测.后来，SANLIN X等［9］量化了两状态一阶马尔可夫模型中的节点对间距，将两状态一阶马尔可夫模型扩展为多状态一阶马尔可夫模型，提高模型准确性.基于多状态一阶马尔可夫模型，ZHAO Ming等［10］研究了在平滑移动模型下，移动自组织网络的拓扑动态特性.一阶马尔可夫模型具有算法简单、运行速度快等优点，但模型的链路连通概率只与前一时刻链路是否连通有关.然而，在实际场景下，链路连通概率不仅与前一时刻的连通状态有关，也和前几个时刻的连通状态有关.因此，一阶马尔可夫模型精度低，无法模拟实际情况下的链路连通特性，进而制约无线网络设计与评估.

为提高链路连通性模型精度，本文提出高阶马尔可夫链路连通性模型，并通过分析模型生成的链路生命时间精度与马尔可夫链阶数的对应关系，优化链路连通性模型.本文首次针对链路连通性的时变特性进行建模，并且根据高阶马尔可夫链理论优化模型，最终建立高精度时变链路连通性模型.通过实验统计方法获取模型参数，并利用该模型评估链路生命时间.通过与蒙特卡洛仿真、多状态一阶马尔可夫模型实验对比，验证模型准确性，并分析模型精度与马尔可夫链阶数的对应关系.

1 基本假设

针对链路连通性问题研究，需要进一步对移动自组织网络做以下假设:

1)网络规模

网络中有N个移动通信节点随机分布在方形观测区域Q内，区域面积A=l×l，通信节点坐标(X，Y)在区域Q内服从均匀分布.

2)节点传输范围

网络中所有节点具有相同结构，每个节点的传输范围为R.如果两个节点彼此进入各自传输范围，节点间可直接相互通信，即节点间无线链路属于连通状态，否则为断开状态.

3)节点移动特性

节点移动特性是影响移动自组织网络性能的关键因素，它包括节点移动速度特性(高速、中速和低速)与移动模型.本文中，将通信节点移动速度分为两种情况:低速的步行情景和中速的行车情景.节点移动模型符合半马尔可夫平滑移动模型(semi-markov smooth，SMS)，该移动模型具有节点空间分布均匀、移动速率平稳等优点，已被广泛应用于移动自组织网络研究［11］.

4)边界处理

当节点运动到观测区域边界时，其速度大小恒定，方向呈光线反射式变化.

2 链路连通性建模

链路连通性描述通信节点间是否可直接相互通信.通过图论的链路连通概率向量介绍链路连通性［12］.

在移动自组织网络中，无线链路的连通情况可由链路连通概率向量为

式中:Pr(·)是概率函数，ρ为节点对间距，R为节点传输范围，S为无线链路的连通状态.当链路连通状态S值为1时，表示链路连通，S值为0时，表示链路断开.由式(1)可看出，链路连通性由节点移动性和节点传输范围共同决定.

无线链路连通性模型是描述链路通断情况随时间变化的数学抽象模型.根据马尔可夫链理论，链路连通概率随着时间的变化可表示为转移概率矩阵和上一时刻链路连通概率向量的乘积，即

式中:Fm为第m时刻链路连通概率向量，P1是一阶马尔可夫转移概率矩阵，P1表达式为

式中:S为当前时刻链路连通状态，S-1为上一时刻链路连通状态.一阶马尔可夫转移概率矩阵P1是在已知上一时刻链路连通状态的条件下，该时刻链路连通状态的条件概率矩阵.

第m时刻链路连通状态，即链路连通性模型为

式中:Y是服从0到1均匀分布的随机数;Boole{·}是布尔型函数，如果布尔型函数{}里的条件成立输出为1，否则为0;Fm(2)为链路连通概率向量的第2个元素，是第m时刻链路连通概率.

当第m时刻链路连通状态确定时，第m时刻的链路连通概率向量需要进行相应的修正，其结果为

式中:当Sm=0时，1;当Sm=1时，0.

将修正后的链路连通概率向量代入式(2)，可求m+1时刻链路连通概率向量，再利用式(4)求出m+1时刻的链路连通状态，如此循环迭代建立具有时变特性的链路连通性模型.

然而，在实际场景下，当前链路连通状态不仅与前一时刻链路连通状态有关系，还与前几个时刻链路连通状态都有关系.因此，为使模型更贴近实际，将一阶马尔可夫链路连通性模型扩展到高阶马尔可夫模型，提高模型精度.以k阶马尔可夫链路连通性模型为例，第m时刻链路连通概率向量为

式中:F(m-k)…(m-2)(m-1)为前k个时刻的联合链路连通概率向量，Pk为k阶马尔可夫转移概率矩阵.k阶联合链路连通概率向量F(m-k)…(m-2)(m-1)和k阶马尔可夫转移概率矩阵Pk的表达式分别如式(7)、(8)所示.

k阶联合链路连通概率向量F(m-k)…(m-2)(m-1)是1×2k维的行向量，其第q个元素的表达式为

式中:q=1，2，3，…，2k;Qb为等于q-1 的二进制表示.F(m-k)…(m-2)(m-1)描述了前k个时刻链路连通的情况.

k阶马尔可夫转移概率矩阵Pk是2k×2维的矩阵，其表达式为

式中:S为当前时刻链路连通状态，S-i为第前i时刻链路连通状态，i=1，2，…，k.Pr(S|S-k，…，S-2S-1)为在已知前k个时刻链路连通状态的条件下，当前时刻链路连通状态出现的概率.

与一阶马尔可夫链路连通性建模相似，将式(6)获得的链路连通概率向量代入式(4)，得到第m时刻链连通状态，即k阶马尔可夫链路连通性模型，同理，如此循环迭代建立具有高精度和时变特性的高阶马尔可夫链路连通性模型.

3 仿真分析

通过蒙特卡洛仿真实验得到不同时刻链路连通状态，再应用统计方法获取高阶马尔可夫链路连通性模型的参数——转移概率矩阵.通过与多状态一阶马尔可夫模型、蒙特卡洛仿真实验对比，评估链路生命时间，验证链路连通性模型生成的链路生命时间准确性，并分析链路生命时间精度与马尔可夫链阶数的对应关系.

3.1 模型参数

在1 000 m×1 000 m方形仿真区域，均匀分布100个传输范围皆为100 m的移动通信节点.节点运动符合半马尔可夫平滑移动模型.在匀加速阶段，运动相位服从0～2π均匀分布;在匀加速阶段和匀减速阶段，节点运动时间皆服从1～5 s均匀分布;在中间平滑阶段，运动时间服从60～120 s均匀分布，前后2个时刻节点运动的相关系数为0.5;节点总的运动时间为5 000 s，实验考察步行和行车两种情景.在步行情景下，节点匀加速阶段目标速率为2 m/s，观察时间间隔为1 s;在行车情景时，匀加速阶段目标速率为20 m/s，观察时间间隔为 0.1 s.

通过蒙特卡洛仿真实验得到不同时刻链路连通状态，利用统计方法获得马尔可夫转移概率矩阵.列出一至四阶马尔可夫转移概率矩阵的实验统计结果，其中，Pk-Walk和Pk-Drive分别为步行和行车两种情景下的k阶马尔可夫转移概率矩阵.

3.2 模型分析

链路生命时间是移动自组织网络链路重要特性［12］.为分析该链路连通性模型准确性和实用性，通过高阶马尔可夫模型、蒙特卡洛仿真和多状态一阶马尔可夫模型评估链路生命时间.

链路生命时间是节点间链路开始连通到链路断开所持续的时间，记为TL.链路生命时间统计分布函数可用来描述和分析其他链路特性，如链路剩余生命时间和链路到达率等［12］.链路生命时间概率密度函数为

式中:Nm为在一个长时间T里链路连通持续时间为m·t出现的次数，N为在长时间T内链路连通总次数.通过实验仿真得到不同时刻链路连通状态，采用统计方法获得链路生命时间概率密度函数.

根据大量实验逼近实际情况的蒙特卡洛仿真思想，采用观察时间为5 000 s的蒙特卡洛仿真，数据样本足够多，实验结果可近视为实际结果.根据ZHAO Ming等［2］研究结果表明，多状态一阶马尔可夫模型的链路生命时间服从指数分布.使用多状态一阶马尔可夫模型、蒙特卡洛仿真实验和高阶马尔可夫模型3种方法，得到步行和行车2种运动情景下链路生命时间对数概率密度函数见图1.

图1 不同运动情景下链路生命时间对数概率密度分布

从图1可看出，3种方法得到链路生命时间对数概率密度函数基本一致，从而验证链路连通性模型的准确性.高阶马尔可夫模型结果比多状态一阶马尔可夫模型更接近蒙特卡洛仿真，即高阶马尔可夫模型比多状态一阶马尔可夫模型更能精确地评估链路生命时间.比较图1(a)、(b)可看出，行车和步行2种运动情景下，高阶马尔可夫链路连通性模型得到链路生命时间对数概率密度函数都很好地吻合蒙特卡洛仿真结果，说明高阶马尔可夫模型对中、低速移动网络都适用.

通过不同阶数的高阶马尔可夫模型、蒙特卡洛仿真、多状态一阶马尔可夫模型的实验对比，分析了由链路连通性模型获取的链路生命时间精度与马尔可夫链阶数的对应关系.实验得到步行和行车2种情景下的链路生命时间概率累积分布分别见图 2、3.

图3 行车情景下链路生命时间概率累积分布

从图2、3可看出，通过高阶马尔可夫模型、多状态一阶马尔可夫模型、蒙特卡洛仿真得到的链路生命时间概率累积分布函数基本一致.随着马尔可夫链阶数增加，高阶马尔可夫模型实验所得链路生命时间累积分布函数与蒙特卡洛仿真结果越接近，说明链路生命时间精度随着马尔可夫链阶数增加而提高.

为进一步分析链路生命时间精度与马尔可夫链阶数的对应关系，将蒙特卡洛仿真与高阶马尔可夫模型得到链路生命时间概率累积分布函数作差，将其差值的最大绝对值作为高阶马尔可夫模型的误差，记为

式中:CMonteCarlo为蒙特卡洛仿真得到的链路生命时间概率累积分布函数，Ck-Markov为k阶马尔可夫链路连通性模型得到链路生命时间概率累积分布函数.

相似地，将蒙特卡洛仿真与多状态一阶马尔可夫模型得到链路生命时间累积分布函数作差，将其差值的最大绝对值作为多状态一阶马尔可夫模型误差，记为M.相比多状态一阶马尔可夫模型，四阶马尔可夫模型误差降低

式中M4为四阶马尔可夫模型误差.

仿真结果见图4，随着马尔可夫链阶数增加，基于高阶马尔可夫链的无线链路连通性模型误差逐渐减小.当马尔可夫链阶数＞4时，高阶马尔可夫链路连通性模型误差降低不明显，并且出现波动状态.因为实验仿真时间长度和计算机内存空间等有限，高阶马尔可夫转移概率矩阵的统计样本值不够，导致转移概率矩阵结果不够精准.实验结果表明，相比多状态一阶马尔可夫链路连通性模型，四阶马尔可夫模型生成的链路生命时间误差下降68%.具体应用时，折中考虑模型精度要求和算法复杂度，一般认为四阶马尔可夫链路连通性模型已满足动态无线网络对链路连通性建模的精度要求.

图4 不同运动情景下模型误差与马尔可夫链阶数关系

4 结语

本文综合考虑无线传输环境和节点移动性对链路连通性的影响，结合马尔可夫链理论，建立时变高阶马尔可夫链路连通性模型.通过与蒙特卡洛仿真、多状态一阶马尔可夫模型实验对比，验证模型准确性，并分析模型生成的链路生命时间精度与马尔可夫链阶数的对应关系.实验结果表明，链路连通性模型能够有效描述时变的链路连通情况，且链路生命时间精度随马尔可夫链阶数增加而提升.当马尔可夫链阶数＞4时，模型精度提升不明显.相比多状态一阶马尔可夫链路连通性模型，四阶马尔可夫模型生成的链路生命时间误差下降68%.研究结果可用于指导移动自组织网络路由协议设计与优化、网络拓扑结构控制和网络性能分析.利用该链路连通性模型，可缩短协议设计周期、减少测试工作量.

［1］RUBINSTEIN M G，MORAES I M，CAMPISTA M E M，et al.A survey on wireless ad hoc networks［C］//IFIP 19th World Computer Congress.Santiago(Chile):IEEE，2006(211):1-33.

［2］ZHAO Ming，LI Yujin，WANG Wenye.Modeling and analytical study of link properties in multihop wireless networks［J］.IEEE Transactions on Communications，2012，60(2):445-455.

［3］ BARGHI S，BENSLIMANE A，ASSI C.A lifetimebased routing protocol for connecting VANETs to the Internet［C］//Proceedings of IEEE International Symposium onaWorldofWireless，Mobileand Multimedia Networks＆ Workshops.Kos(Greece):IEEE，2009:1-9.

［4］丁红勇.卫星通信链路连通性仿真模型设计［J］.系统仿真学报，2007，19(4):713-715，737.

［5］GERHARZ M，FRANK M，MARTINI P，et al.Link stability in mobile wireless ad hoc networks［C］//Proceedings of the 27th Annual IEEE Conference on Local Computer Networks.Tampa Florida(USA):IEEE，2002:30-39.

［6］BAI F，SADAGOPAN N，KRISHNAMAEHARI B，et al.Modeling path duration distributions in MANETs and their impact on reactive routing protocols［J］.IEEE Journal on Selected Areas in Communications，2004，22(7):1357-1373.

［7］GRUBER I，LI Hui.Link expiration times in mobile ad hoc networks［C］//Proceedings of the 27th Annual IEEE Conference on Local Computer Networks.Tampa Florida(USA):IEEE，2002:743-750.

［8］ QIN M，ZIMMERMANN R，LIU L.S.Supporting multimedia streaming between mobile peers with link availability prediction［C］//Proceedings of the 13th annual ACM international conference on Multimedia.New York(USA):ACM，2005:956-965.

［9］ SANLIN X，BLACKMORE K L，JONES H M.An analysis framework for mobility metrics in mobile ad hoc networks［J］. EURASIP Journal on Wireless Communications and Networking，2007:1-16.

［10］ZHAO Ming， WANG Wenye. Analyzing topology dynamics in ad hoc networks using a smooth mobility model［C］//Proceedings of Wireless Communications and Networking Conference.Shanghai(China):IEEE，2007:3279-3284.

［11］ZHAO Ming，WANG Wenye.A unified mobility model for analysis and simulation of mobile wireless networks［J］.Wireless Networks archive，2009，15(3):365-389.

［12］BETTSTETTER C，HARTMANN C.Connectivity of wireless multihop networks in a shadow fading environment［J］.Wireless Networks archive，2005，11(5):571-579.