高階馬爾可夫鏈無線鏈路連通性建模

陳冬明，汪 洋，張繼良，李 銀，向少華

(1.哈爾濱工業(yè)大學深圳研究生院，518055廣東深圳;2.深圳國家高技術產業(yè)創(chuàng)新中心，518063廣東深圳)

移動自組織網絡具有無中心、自組織、節(jié)點可移動等特點，受到廣泛關注［1］.在移動自組織網絡中，端對端的通信路徑由一個或多個無線鏈路組成，鏈路性能將直接影響網絡通信質量［2］.鏈路連通性是無線鏈路最基本特性［3］，鏈路連通性研究對網絡拓撲控制和路由協議分析等有著重要指導意義［4］.

目前，移動自組織網絡鏈路連通性研究方法主要有蒙特卡洛仿真和一階馬爾可夫模型.早期鏈路連通性研究主要采用蒙特卡洛仿真方法［5-6］.GERHARZ M 等［5］最早利用蒙特卡洛仿真方法，分析了不同運動模型下的鏈路特性.在此基礎上，BAI F等［6］基于蒙特卡洛仿真分析了通信路徑穩(wěn)定性，并改進路由協議.當仿真數據量足夠大時，蒙特卡洛仿真結果比較接近實際情況，但實驗所需的時間長、數據存儲空間大，形成研發(fā)瓶頸.為了有效評估移動自組織網絡的連通特性，需針對特定環(huán)境設計鏈路連通性模型.傳統(tǒng)的鏈路連通性建模主要采用一階馬爾可夫模型，可分為兩狀態(tài)一階馬爾可夫模型［7-8］和多狀態(tài)一階馬爾可夫模型［9-10］.最早，GRUBER I等［7］根據兩狀態(tài)一階馬爾可夫模型，結合節(jié)點傳輸范圍和節(jié)點移動模型，理論推導了鏈路剩余生命時間等鏈路特性函數.QIN M等［8］將兩狀態(tài)一階馬爾可夫模型應用于支持多媒體流的無線鏈路可用性預測.后來，SANLIN X等［9］量化了兩狀態(tài)一階馬爾可夫模型中的節(jié)點對間距，將兩狀態(tài)一階馬爾可夫模型擴展為多狀態(tài)一階馬爾可夫模型，提高模型準確性.基于多狀態(tài)一階馬爾可夫模型，ZHAO Ming等［10］研究了在平滑移動模型下，移動自組織網絡的拓撲動態(tài)特性.一階馬爾可夫模型具有算法簡單、運行速度快等優(yōu)點，但模型的鏈路連通概率只與前一時刻鏈路是否連通有關.然而，在實際場景下，鏈路連通概率不僅與前一時刻的連通狀態(tài)有關，也和前幾個時刻的連通狀態(tài)有關.因此，一階馬爾可夫模型精度低，無法模擬實際情況下的鏈路連通特性，進而制約無線網絡設計與評估.

為提高鏈路連通性模型精度，本文提出高階馬爾可夫鏈路連通性模型，并通過分析模型生成的鏈路生命時間精度與馬爾可夫鏈階數的對應關系，優(yōu)化鏈路連通性模型.本文首次針對鏈路連通性的時變特性進行建模，并且根據高階馬爾可夫鏈理論優(yōu)化模型，最終建立高精度時變鏈路連通性模型.通過實驗統(tǒng)計方法獲取模型參數，并利用該模型評估鏈路生命時間.通過與蒙特卡洛仿真、多狀態(tài)一階馬爾可夫模型實驗對比，驗證模型準確性，并分析模型精度與馬爾可夫鏈階數的對應關系.

1 基本假設

針對鏈路連通性問題研究，需要進一步對移動自組織網絡做以下假設:

1)網絡規(guī)模

網絡中有N個移動通信節(jié)點隨機分布在方形觀測區(qū)域Q內，區(qū)域面積A=l×l，通信節(jié)點坐標(X，Y)在區(qū)域Q內服從均勻分布.

2)節(jié)點傳輸范圍

網絡中所有節(jié)點具有相同結構，每個節(jié)點的傳輸范圍為R.如果兩個節(jié)點彼此進入各自傳輸范圍，節(jié)點間可直接相互通信，即節(jié)點間無線鏈路屬于連通狀態(tài)，否則為斷開狀態(tài).

3)節(jié)點移動特性

節(jié)點移動特性是影響移動自組織網絡性能的關鍵因素，它包括節(jié)點移動速度特性(高速、中速和低速)與移動模型.本文中，將通信節(jié)點移動速度分為兩種情況:低速的步行情景和中速的行車情景.節(jié)點移動模型符合半馬爾可夫平滑移動模型(semi-markov smooth，SMS)，該移動模型具有節(jié)點空間分布均勻、移動速率平穩(wěn)等優(yōu)點，已被廣泛應用于移動自組織網絡研究［11］.

4)邊界處理

當節(jié)點運動到觀測區(qū)域邊界時，其速度大小恒定，方向呈光線反射式變化.

2 鏈路連通性建模

鏈路連通性描述通信節(jié)點間是否可直接相互通信.通過圖論的鏈路連通概率向量介紹鏈路連通性［12］.

在移動自組織網絡中，無線鏈路的連通情況可由鏈路連通概率向量為

式中:Pr(·)是概率函數，ρ為節(jié)點對間距，R為節(jié)點傳輸范圍，S為無線鏈路的連通狀態(tài).當鏈路連通狀態(tài)S值為1時，表示鏈路連通，S值為0時，表示鏈路斷開.由式(1)可看出，鏈路連通性由節(jié)點移動性和節(jié)點傳輸范圍共同決定.

無線鏈路連通性模型是描述鏈路通斷情況隨時間變化的數學抽象模型.根據馬爾可夫鏈理論，鏈路連通概率隨著時間的變化可表示為轉移概率矩陣和上一時刻鏈路連通概率向量的乘積，即

式中:Fm為第m時刻鏈路連通概率向量，P1是一階馬爾可夫轉移概率矩陣，P1表達式為

式中:S為當前時刻鏈路連通狀態(tài)，S-1為上一時刻鏈路連通狀態(tài).一階馬爾可夫轉移概率矩陣P1是在已知上一時刻鏈路連通狀態(tài)的條件下，該時刻鏈路連通狀態(tài)的條件概率矩陣.

第m時刻鏈路連通狀態(tài)，即鏈路連通性模型為

式中:Y是服從0到1均勻分布的隨機數;Boole{·}是布爾型函數，如果布爾型函數{}里的條件成立輸出為1，否則為0;Fm(2)為鏈路連通概率向量的第2個元素，是第m時刻鏈路連通概率.

當第m時刻鏈路連通狀態(tài)確定時，第m時刻的鏈路連通概率向量需要進行相應的修正，其結果為

式中:當Sm=0時，1;當Sm=1時，0.

將修正后的鏈路連通概率向量代入式(2)，可求m+1時刻鏈路連通概率向量，再利用式(4)求出m+1時刻的鏈路連通狀態(tài)，如此循環(huán)迭代建立具有時變特性的鏈路連通性模型.

然而，在實際場景下，當前鏈路連通狀態(tài)不僅與前一時刻鏈路連通狀態(tài)有關系，還與前幾個時刻鏈路連通狀態(tài)都有關系.因此，為使模型更貼近實際，將一階馬爾可夫鏈路連通性模型擴展到高階馬爾可夫模型，提高模型精度.以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為當前時刻鏈路連通狀態(tài)，S-i為第前i時刻鏈路連通狀態(tài)，i=1，2，…，k.Pr(S|S-k，…，S-2S-1)為在已知前k個時刻鏈路連通狀態(tài)的條件下，當前時刻鏈路連通狀態(tài)出現的概率.

與一階馬爾可夫鏈路連通性建模相似，將式(6)獲得的鏈路連通概率向量代入式(4)，得到第m時刻鏈連通狀態(tài)，即k階馬爾可夫鏈路連通性模型，同理，如此循環(huán)迭代建立具有高精度和時變特性的高階馬爾可夫鏈路連通性模型.

3 仿真分析

通過蒙特卡洛仿真實驗得到不同時刻鏈路連通狀態(tài)，再應用統(tǒng)計方法獲取高階馬爾可夫鏈路連通性模型的參數——轉移概率矩陣.通過與多狀態(tài)一階馬爾可夫模型、蒙特卡洛仿真實驗對比，評估鏈路生命時間，驗證鏈路連通性模型生成的鏈路生命時間準確性，并分析鏈路生命時間精度與馬爾可夫鏈階數的對應關系.

3.1 模型參數

在1 000 m×1 000 m方形仿真區(qū)域，均勻分布100個傳輸范圍皆為100 m的移動通信節(jié)點.節(jié)點運動符合半馬爾可夫平滑移動模型.在勻加速階段，運動相位服從0～2π均勻分布;在勻加速階段和勻減速階段，節(jié)點運動時間皆服從1～5 s均勻分布;在中間平滑階段，運動時間服從60～120 s均勻分布，前后2個時刻節(jié)點運動的相關系數為0.5;節(jié)點總的運動時間為5 000 s，實驗考察步行和行車兩種情景.在步行情景下，節(jié)點勻加速階段目標速率為2 m/s，觀察時間間隔為1 s;在行車情景時，勻加速階段目標速率為20 m/s，觀察時間間隔為 0.1 s.

通過蒙特卡洛仿真實驗得到不同時刻鏈路連通狀態(tài)，利用統(tǒng)計方法獲得馬爾可夫轉移概率矩陣.列出一至四階馬爾可夫轉移概率矩陣的實驗統(tǒng)計結果，其中，Pk-Walk和Pk-Drive分別為步行和行車兩種情景下的k階馬爾可夫轉移概率矩陣.

3.2 模型分析

鏈路生命時間是移動自組織網絡鏈路重要特性［12］.為分析該鏈路連通性模型準確性和實用性，通過高階馬爾可夫模型、蒙特卡洛仿真和多狀態(tài)一階馬爾可夫模型評估鏈路生命時間.

鏈路生命時間是節(jié)點間鏈路開始連通到鏈路斷開所持續(xù)的時間，記為TL.鏈路生命時間統(tǒng)計分布函數可用來描述和分析其他鏈路特性，如鏈路剩余生命時間和鏈路到達率等［12］.鏈路生命時間概率密度函數為

式中:Nm為在一個長時間T里鏈路連通持續(xù)時間為m·t出現的次數，N為在長時間T內鏈路連通總次數.通過實驗仿真得到不同時刻鏈路連通狀態(tài)，采用統(tǒng)計方法獲得鏈路生命時間概率密度函數.

根據大量實驗逼近實際情況的蒙特卡洛仿真思想，采用觀察時間為5 000 s的蒙特卡洛仿真，數據樣本足夠多，實驗結果可近視為實際結果.根據ZHAO Ming等［2］研究結果表明，多狀態(tài)一階馬爾可夫模型的鏈路生命時間服從指數分布.使用多狀態(tài)一階馬爾可夫模型、蒙特卡洛仿真實驗和高階馬爾可夫模型3種方法，得到步行和行車2種運動情景下鏈路生命時間對數概率密度函數見圖1.

圖1 不同運動情景下鏈路生命時間對數概率密度分布

從圖1可看出，3種方法得到鏈路生命時間對數概率密度函數基本一致，從而驗證鏈路連通性模型的準確性.高階馬爾可夫模型結果比多狀態(tài)一階馬爾可夫模型更接近蒙特卡洛仿真，即高階馬爾可夫模型比多狀態(tài)一階馬爾可夫模型更能精確地評估鏈路生命時間.比較圖1(a)、(b)可看出，行車和步行2種運動情景下，高階馬爾可夫鏈路連通性模型得到鏈路生命時間對數概率密度函數都很好地吻合蒙特卡洛仿真結果，說明高階馬爾可夫模型對中、低速移動網絡都適用.

通過不同階數的高階馬爾可夫模型、蒙特卡洛仿真、多狀態(tài)一階馬爾可夫模型的實驗對比，分析了由鏈路連通性模型獲取的鏈路生命時間精度與馬爾可夫鏈階數的對應關系.實驗得到步行和行車2種情景下的鏈路生命時間概率累積分布分別見圖 2、3.

圖3 行車情景下鏈路生命時間概率累積分布

從圖2、3可看出，通過高階馬爾可夫模型、多狀態(tài)一階馬爾可夫模型、蒙特卡洛仿真得到的鏈路生命時間概率累積分布函數基本一致.隨著馬爾可夫鏈階數增加，高階馬爾可夫模型實驗所得鏈路生命時間累積分布函數與蒙特卡洛仿真結果越接近，說明鏈路生命時間精度隨著馬爾可夫鏈階數增加而提高.

為進一步分析鏈路生命時間精度與馬爾可夫鏈階數的對應關系，將蒙特卡洛仿真與高階馬爾可夫模型得到鏈路生命時間概率累積分布函數作差，將其差值的最大絕對值作為高階馬爾可夫模型的誤差，記為

式中:CMonteCarlo為蒙特卡洛仿真得到的鏈路生命時間概率累積分布函數，Ck-Markov為k階馬爾可夫鏈路連通性模型得到鏈路生命時間概率累積分布函數.

相似地，將蒙特卡洛仿真與多狀態(tài)一階馬爾可夫模型得到鏈路生命時間累積分布函數作差，將其差值的最大絕對值作為多狀態(tài)一階馬爾可夫模型誤差，記為M.相比多狀態(tài)一階馬爾可夫模型，四階馬爾可夫模型誤差降低

式中M4為四階馬爾可夫模型誤差.

仿真結果見圖4，隨著馬爾可夫鏈階數增加，基于高階馬爾可夫鏈的無線鏈路連通性模型誤差逐漸減小.當馬爾可夫鏈階數＞4時，高階馬爾可夫鏈路連通性模型誤差降低不明顯，并且出現波動狀態(tài).因為實驗仿真時間長度和計算機內存空間等有限，高階馬爾可夫轉移概率矩陣的統(tǒng)計樣本值不夠，導致轉移概率矩陣結果不夠精準.實驗結果表明，相比多狀態(tài)一階馬爾可夫鏈路連通性模型，四階馬爾可夫模型生成的鏈路生命時間誤差下降68%.具體應用時，折中考慮模型精度要求和算法復雜度，一般認為四階馬爾可夫鏈路連通性模型已滿足動態(tài)無線網絡對鏈路連通性建模的精度要求.

圖4 不同運動情景下模型誤差與馬爾可夫鏈階數關系

4 結語

本文綜合考慮無線傳輸環(huán)境和節(jié)點移動性對鏈路連通性的影響，結合馬爾可夫鏈理論，建立時變高階馬爾可夫鏈路連通性模型.通過與蒙特卡洛仿真、多狀態(tài)一階馬爾可夫模型實驗對比，驗證模型準確性，并分析模型生成的鏈路生命時間精度與馬爾可夫鏈階數的對應關系.實驗結果表明，鏈路連通性模型能夠有效描述時變的鏈路連通情況，且鏈路生命時間精度隨馬爾可夫鏈階數增加而提升.當馬爾可夫鏈階數＞4時，模型精度提升不明顯.相比多狀態(tài)一階馬爾可夫鏈路連通性模型，四階馬爾可夫模型生成的鏈路生命時間誤差下降68%.研究結果可用于指導移動自組織網絡路由協議設計與優(yōu)化、網絡拓撲結構控制和網絡性能分析.利用該鏈路連通性模型，可縮短協議設計周期、減少測試工作量.

［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］丁紅勇.衛(wèi)星通信鏈路連通性仿真模型設計［J］.系統(tǒng)仿真學報，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.