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

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

移動自組織網(wǎng)絡(luò)具有無中心、自組織、節(jié)點(diǎn)可移動等特點(diǎn)，受到廣泛關(guān)注［1］.在移動自組織網(wǎng)絡(luò)中，端對端的通信路徑由一個(gè)或多個(gè)無線鏈路組成，鏈路性能將直接影響網(wǎng)絡(luò)通信質(zhì)量［2］.鏈路連通性是無線鏈路最基本特性［3］，鏈路連通性研究對網(wǎng)絡(luò)拓?fù)淇刂坪吐酚蓞f(xié)議分析等有著重要指導(dǎo)意義［4］.

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

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

1 基本假設(shè)

針對鏈路連通性問題研究，需要進(jìn)一步對移動自組織網(wǎng)絡(luò)做以下假設(shè):

1)網(wǎng)絡(luò)規(guī)模

網(wǎng)絡(luò)中有N個(gè)移動通信節(jié)點(diǎn)隨機(jī)分布在方形觀測區(qū)域Q內(nèi)，區(qū)域面積A=l×l，通信節(jié)點(diǎn)坐標(biāo)(X，Y)在區(qū)域Q內(nèi)服從均勻分布.

2)節(jié)點(diǎn)傳輸范圍

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

3)節(jié)點(diǎn)移動特性

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

4)邊界處理

當(dāng)節(jié)點(diǎn)運(yùn)動到觀測區(qū)域邊界時(shí)，其速度大小恒定，方向呈光線反射式變化.

2 鏈路連通性建模

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

在移動自組織網(wǎng)絡(luò)中，無線鏈路的連通情況可由鏈路連通概率向量為

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

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

式中:Fm為第m時(shí)刻鏈路連通概率向量，P1是一階馬爾可夫轉(zhuǎn)移概率矩陣，P1表達(dá)式為

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

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

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

當(dāng)?shù)趍時(shí)刻鏈路連通狀態(tài)確定時(shí)，第m時(shí)刻的鏈路連通概率向量需要進(jìn)行相應(yīng)的修正，其結(jié)果為

式中:當(dāng)Sm=0時(shí)，1;當(dāng)Sm=1時(shí)，0.

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

然而，在實(shí)際場景下，當(dāng)前鏈路連通狀態(tài)不僅與前一時(shí)刻鏈路連通狀態(tài)有關(guān)系，還與前幾個(gè)時(shí)刻鏈路連通狀態(tài)都有關(guān)系.因此，為使模型更貼近實(shí)際，將一階馬爾可夫鏈路連通性模型擴(kuò)展到高階馬爾可夫模型，提高模型精度.以k階馬爾可夫鏈路連通性模型為例，第m時(shí)刻鏈路連通概率向量為

式中:F(m-k)…(m-2)(m-1)為前k個(gè)時(shí)刻的聯(lián)合鏈路連通概率向量，Pk為k階馬爾可夫轉(zhuǎn)移概率矩陣.k階聯(lián)合鏈路連通概率向量F(m-k)…(m-2)(m-1)和k階馬爾可夫轉(zhuǎn)移概率矩陣Pk的表達(dá)式分別如式(7)、(8)所示.

k階聯(lián)合鏈路連通概率向量F(m-k)…(m-2)(m-1)是1×2k維的行向量，其第q個(gè)元素的表達(dá)式為

式中:q=1，2，3，…，2k;Qb為等于q-1 的二進(jìn)制表示.F(m-k)…(m-2)(m-1)描述了前k個(gè)時(shí)刻鏈路連通的情況.

k階馬爾可夫轉(zhuǎn)移概率矩陣Pk是2k×2維的矩陣，其表達(dá)式為

式中:S為當(dāng)前時(shí)刻鏈路連通狀態(tài)，S-i為第前i時(shí)刻鏈路連通狀態(tài)，i=1，2，…，k.Pr(S|S-k，…，S-2S-1)為在已知前k個(gè)時(shí)刻鏈路連通狀態(tài)的條件下，當(dāng)前時(shí)刻鏈路連通狀態(tài)出現(xiàn)的概率.

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

3 仿真分析

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

3.1 模型參數(shù)

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

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

3.2 模型分析

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

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

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

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

圖1 不同運(yùn)動情景下鏈路生命時(shí)間對數(shù)概率密度分布

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

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

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

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

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

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

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

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

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

圖4 不同運(yùn)動情景下模型誤差與馬爾可夫鏈階數(shù)關(guān)系

4 結(jié)語

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

［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)星通信鏈路連通性仿真模型設(shè)計(jì)［J］.系統(tǒng)仿真學(xué)報(bào)，2007，19(4):713-715，737.

［5］GERHARZ M，F(xiàn)RANK 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.