趙 荷， 蓋 玲

(1.成都東軟學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，四川 成都 611844;2.上海大學(xué) 管理學(xué)院，上海 200444)

?

基于連接矩陣的移動(dòng)Ad Hoc網(wǎng)絡(luò)可靠性評(píng)估方案*

趙 荷1*， 蓋 玲2

(1.成都東軟學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，四川 成都 611844;2.上海大學(xué) 管理學(xué)院，上海 200444)

移動(dòng)Ad Hoc網(wǎng)絡(luò)(MANET)的動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)使網(wǎng)絡(luò)可靠性評(píng)估較為困難，為此提出一種基于連接矩陣的MANET可靠性評(píng)估方案.首先，確定網(wǎng)絡(luò)中的源-終節(jié)點(diǎn)對(duì)和中繼節(jié)點(diǎn).然后，根據(jù)節(jié)點(diǎn)間歐式距離和通信范圍來(lái)檢測(cè)中繼鏈路狀態(tài)，并構(gòu)建連接矩陣.最后，根據(jù)連接矩陣判斷網(wǎng)絡(luò)連接性，以多輪連接性的均值作為網(wǎng)絡(luò)的最終可靠性.仿真實(shí)驗(yàn)中，評(píng)估了節(jié)點(diǎn)移動(dòng)模型、網(wǎng)絡(luò)大小、節(jié)點(diǎn)數(shù)量和通信范圍對(duì)網(wǎng)絡(luò)可靠性的影響，能夠?yàn)榫W(wǎng)絡(luò)設(shè)計(jì)者提供有力的依據(jù).

移動(dòng)Ad Hoc網(wǎng)絡(luò)；網(wǎng)絡(luò)可靠性；連接矩陣；節(jié)點(diǎn)移動(dòng)模型

移動(dòng)Ad Hoc網(wǎng)絡(luò)(Mobile Ad Hoc Network, MANET)是一種新型的移動(dòng)自組織網(wǎng)絡(luò)[1].對(duì)于拓?fù)浣Y(jié)構(gòu)不斷變化的MANET，網(wǎng)絡(luò)的可靠性是構(gòu)建網(wǎng)絡(luò)時(shí)需要考慮的一個(gè)重要指標(biāo)[2]，MANET中，節(jié)點(diǎn)間的鏈接是影響網(wǎng)絡(luò)可靠性的一個(gè)重要因素，而高度動(dòng)態(tài)特性使節(jié)點(diǎn)鏈接頻繁地?cái)嗔鸦蛑亟?，已成為系統(tǒng)可靠性評(píng)估的一個(gè)挑戰(zhàn)[3].對(duì)于MANET的可靠性計(jì)算，根據(jù)通信節(jié)點(diǎn)數(shù)量可分為2-終端、k-終端和全終端可靠性[4-5].其中，2-終端可靠性為一個(gè)特定節(jié)點(diǎn)對(duì)相互成功通信的概率.那么，網(wǎng)絡(luò)的可靠性可定義為網(wǎng)絡(luò)中每對(duì)節(jié)點(diǎn)相互成功通信的概率[6].目前，學(xué)者提出了多種MANET可靠性評(píng)估方法.例如，[7]提出了基于蒙特卡羅仿真的評(píng)估方法，考慮了隨機(jī)路點(diǎn)移動(dòng)模型，并使用橫向優(yōu)先搜索方法來(lái)檢查網(wǎng)絡(luò)中的連接.然而，該方法會(huì)隨著網(wǎng)絡(luò)尺寸的增加變得非常復(fù)雜，實(shí)用性不強(qiáng).[8]識(shí)別網(wǎng)絡(luò)中關(guān)鍵的鏈路，通過(guò)基于跳數(shù)的網(wǎng)絡(luò)連接來(lái)計(jì)算MANET的網(wǎng)絡(luò)可靠性.然而，該方案僅適用于跳數(shù)大于等于3時(shí)的場(chǎng)景.

本文提出了一種基于連接矩陣的MANET可靠性評(píng)估方法，以2-終端可靠性計(jì)算為基礎(chǔ)，研究了隨機(jī)路點(diǎn)移動(dòng)(Random Waypoint Mobility, RWPM)和高斯-馬爾可夫移動(dòng)(Gauss-Markov Mobility, GMM)模型對(duì)可靠性的影響.另外，還分析了網(wǎng)絡(luò)大小、節(jié)點(diǎn)數(shù)量和通信范圍對(duì)網(wǎng)絡(luò)可靠性的影響.為網(wǎng)絡(luò)設(shè)計(jì)者進(jìn)行可靠MANET的構(gòu)建和參數(shù)設(shè)定提供有力的依據(jù).

1 MANET網(wǎng)絡(luò)模型

1.1 網(wǎng)絡(luò)模型

給定一個(gè)具有n個(gè)移動(dòng)節(jié)點(diǎn)(Mobile Node, MN)的MANET，在任意時(shí)刻τ時(shí)，都可以將該網(wǎng)絡(luò)建模為一個(gè)固定的網(wǎng)絡(luò)幾何隨機(jī)圖G(U,L,τ).假設(shè)所有MN具備相等的傳輸范圍rj，且失效時(shí)間遵循威布爾分布，則可以基于節(jié)點(diǎn)位置、節(jié)點(diǎn)距離和傳輸范圍直接創(chuàng)建鏈路.

網(wǎng)絡(luò)節(jié)點(diǎn)的失效時(shí)間可以遵循多種分布，如指數(shù)、正態(tài)或威布爾分布.其中，在系統(tǒng)建模中，威布爾分布已廣泛用于作為組件的故障模式[9].所以，本文采用威布爾失效分布模式管理節(jié)點(diǎn)的失效時(shí)間.另外，由于RWPM模型、GMM模型在模擬節(jié)點(diǎn)移動(dòng)模式中有著廣泛應(yīng)用[10]，所以本文選擇這些模型.因此，對(duì)于MANET可靠性的評(píng)估，考慮了以下假設(shè)：

1.2 節(jié)點(diǎn)移動(dòng)模型

1.2.1 隨機(jī)路點(diǎn)移動(dòng)模型(RWPM) 在RWPM模型中，節(jié)點(diǎn)i通過(guò)選擇一個(gè)速度vi(τ)∈(Vmax,Vmin)和方向φi(τ)∈(0,2φ)移動(dòng)到下一個(gè)目的地[11].利用(1)式來(lái)表示每個(gè)Δτ增量區(qū)間處，下一個(gè)節(jié)點(diǎn)的位置.

xi(τ+Δτ)=xi(τ)+Δτvi(τ)cosφi(τ)，yi(τ+Δτ)=yi(τ)+Δτvi(τ)sinφi(τ)．

(1)

(2)

在上一時(shí)刻(τ-1)處的速度Sτ-1和方向φτ-1將影響當(dāng)前的速度Sτ和方向φτ.MN的運(yùn)動(dòng)模式隨著調(diào)優(yōu)參數(shù)α而變化，當(dāng)α=0時(shí)，MN的運(yùn)動(dòng)是完全隨機(jī)的；當(dāng)α=1時(shí)，MN的運(yùn)動(dòng)遵循之前運(yùn)動(dòng)方式，且進(jìn)行直線運(yùn)動(dòng).節(jié)點(diǎn)當(dāng)前位置的表達(dá)式如下：

xτ=xτ-1+sτcos(φτ)，yτ=yτ-1+sτcos(φτ).

(3)

2 MANET可靠性評(píng)估方案

2.1 網(wǎng)絡(luò)可靠性定義

(4)

式中Rui(τ)表示節(jié)點(diǎn)鏈路正常傳輸?shù)母怕?，定義如下：

(5)

(6)

當(dāng)中繼節(jié)點(diǎn)對(duì)(ui,uj)之間的歐式距離dij(τ)在MN的傳輸范圍內(nèi)時(shí)，則鏈路存在.因此，鏈路狀態(tài)Lij(τ)可定位為：

(7)

(8)

進(jìn)一步地，在時(shí)刻τ，可以將所有中繼節(jié)點(diǎn)對(duì)的鏈路狀態(tài)構(gòu)建成一個(gè)連接矩陣A(τ)，來(lái)表示網(wǎng)絡(luò)連接性.A(τ)大小為n×n，元素為L(zhǎng)ij(τ).利用連接矩陣A(τ)可以確定源-終節(jié)點(diǎn)對(duì)(s,t)之間的綜合連接性.其中，第q次迭代中時(shí)刻τ時(shí)的網(wǎng)絡(luò)連接性Cq(τ)狀態(tài)定義如下：

(9)

在每個(gè)時(shí)間增量Δτ時(shí)，即節(jié)點(diǎn)位置變化時(shí)，利用連接矩陣A(τ)表征網(wǎng)絡(luò)的連接性，一直持續(xù)到預(yù)定義的任務(wù)時(shí)間T.共執(zhí)行Q次迭代，最后，將任務(wù)持續(xù)時(shí)間中的每個(gè)時(shí)間段τ處的仿真結(jié)果取平均值，來(lái)定義MANET的網(wǎng)絡(luò)可靠性RG(τ)，定義如下：

(10)

Var(RG(τ))=RG(τ)(1-RG(τ))/Q.

(11)

本文MANET可靠性評(píng)估方案分為2類(lèi)，即不考慮節(jié)點(diǎn)移動(dòng)性和考慮節(jié)點(diǎn)移動(dòng)性的評(píng)估方案.

2.2 不考慮移動(dòng)性時(shí)的可靠性評(píng)估方案

在不考慮移動(dòng)性時(shí)，MANET中每個(gè)節(jié)點(diǎn)都具有固定的位置，根據(jù)網(wǎng)絡(luò)中鏈路的連接性來(lái)評(píng)估網(wǎng)絡(luò)可靠性，步驟如下：步驟1：初始化網(wǎng)絡(luò)參數(shù)：n,D,T,rj,θ,β,Cq(τ)=0,Q.步驟2：對(duì)于i=1,2，…，n，生成節(jié)點(diǎn)的隨機(jī)位置(xi,yi).步驟3：仿真節(jié)點(diǎn)狀態(tài)，如式(6).步驟4：利用式(8)，確定每對(duì)MN之間的歐式距離.步驟5：利用式(7)，通過(guò)比較歐式距離和傳輸范圍，檢查鏈路的存在性.步驟6：利用τ時(shí)刻的連接矩陣檢查網(wǎng)絡(luò)的連接性，若已連接，則根據(jù)式(9)將Cq(τ)加1，并更新τ=τ+Δτ.步驟7：返回步驟4，直到τ=T.步驟8：迭代執(zhí)行步驟2～步驟7，共執(zhí)行Q次迭代.步驟9：利用式(10)和(11)計(jì)算RG(τ)和Var(RG(τ)).

2.3 考慮移動(dòng)性時(shí)的可靠性評(píng)估方案

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

使用Matlab2012工具，在配備Intel Core i5 CPU、2.00 GHz主頻，Win7系統(tǒng)的PC機(jī)上執(zhí)行算法.MANET網(wǎng)絡(luò)中每個(gè)MN可以進(jìn)行自組網(wǎng)連接，仿真工作72 h.實(shí)驗(yàn)中，根據(jù)分析需要，設(shè)置每個(gè)MN的傳輸范圍rj為1～5 m， MN的移動(dòng)速度為5 m/h，網(wǎng)絡(luò)區(qū)域大小為100～1 600 m2的正方形區(qū)域，網(wǎng)絡(luò)中的MN數(shù)量為10～100個(gè)，MN按照RWPM模型和GMM模型移動(dòng).另外，失效時(shí)間遵循威布爾分布，其中參數(shù)θ=1 000、β=1.5.對(duì)于隨機(jī)度參數(shù)α(0≤α≤1)，本文設(shè)定α分別取值為0、0.5和1.

3.2 網(wǎng)絡(luò)可靠性評(píng)估

對(duì)于具備RWPM、GMM移動(dòng)模型和無(wú)節(jié)點(diǎn)移動(dòng)的MANET網(wǎng)絡(luò)，在不同網(wǎng)絡(luò)區(qū)域大小、傳輸范圍和節(jié)點(diǎn)數(shù)量下，分別利用提出的可靠性評(píng)估方法對(duì)網(wǎng)絡(luò)鏈接可靠性進(jìn)行評(píng)估.其中，為了區(qū)別RWPM模型，設(shè)定GMM模型中的α=0.5.在分類(lèi)實(shí)驗(yàn)中，網(wǎng)絡(luò)中默認(rèn)設(shè)置20個(gè)MN，每個(gè)MN的傳輸范圍為3 m，網(wǎng)絡(luò)區(qū)域大小為400 m2.圖1描述了不同網(wǎng)絡(luò)區(qū)域大小下，網(wǎng)絡(luò)的可靠性.可以看出，網(wǎng)絡(luò)可靠性隨覆蓋區(qū)域的增大而大幅度下降.這是因?yàn)?，網(wǎng)絡(luò)變大，但節(jié)點(diǎn)數(shù)量和通信范圍有限，致使一些節(jié)點(diǎn)間無(wú)法連接.另外，不同的移動(dòng)模型導(dǎo)致不同的網(wǎng)絡(luò)可靠性.其中，由于RWPM模型中節(jié)點(diǎn)無(wú)規(guī)則移動(dòng)，導(dǎo)致一些節(jié)點(diǎn)會(huì)移動(dòng)到邊緣地帶，從而無(wú)法連接，降低網(wǎng)絡(luò)可靠性.在無(wú)移動(dòng)場(chǎng)景中，初始階段均勻分布，網(wǎng)絡(luò)連接性較好.然而，當(dāng)網(wǎng)絡(luò)越來(lái)越大，即節(jié)點(diǎn)越來(lái)越稀疏時(shí)，相比于無(wú)移動(dòng)場(chǎng)景，節(jié)點(diǎn)的移動(dòng)性反而可以略微提高網(wǎng)絡(luò)可靠性.這是因?yàn)?，?jié)點(diǎn)的移動(dòng)可能會(huì)使部分節(jié)點(diǎn)移動(dòng)到相對(duì)集中的區(qū)域，提高連接線.

圖2描述了不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量下網(wǎng)絡(luò)的可靠性.可以看出，當(dāng)節(jié)點(diǎn)密度增加但覆蓋區(qū)域不變化時(shí)，可靠性有效增加.當(dāng)高節(jié)點(diǎn)密度(U=100)被部署到一個(gè)400 m2的覆蓋區(qū)域時(shí)，幾乎所有場(chǎng)景中的節(jié)點(diǎn)都能和鄰居節(jié)點(diǎn)相互連接，這使得網(wǎng)絡(luò)更加穩(wěn)定，其實(shí)際可靠性值近似達(dá)到了1.當(dāng)?shù)凸?jié)點(diǎn)密度(U=10)被部署到一個(gè)400 m2的覆蓋區(qū)域時(shí)，其實(shí)際可靠性值分別為0.427(RWPM模型)、0.452(GMM模型)、0.415(無(wú)移動(dòng)性)，表明網(wǎng)絡(luò)中只有小部分節(jié)點(diǎn)被連接起來(lái). 另外，與上一個(gè)實(shí)驗(yàn)類(lèi)似，不同的移動(dòng)模型對(duì)網(wǎng)絡(luò)可靠性具有一定的影響，且隨著網(wǎng)絡(luò)密度的不同而不同.

圖3描述了不同傳輸范圍下網(wǎng)絡(luò)的可靠性.可以看出，網(wǎng)絡(luò)可靠性隨著節(jié)點(diǎn)傳輸范圍的增加而單調(diào)增加.這是因?yàn)?，隨著傳輸范圍增加，更多活躍的節(jié)點(diǎn)會(huì)被連接起來(lái)，使網(wǎng)絡(luò)更穩(wěn)定.但傳輸范圍增加也會(huì)增加鏈路的傳輸能耗，所以可靠性會(huì)趨于穩(wěn)定.圖4描述了在整個(gè)作業(yè)持續(xù)時(shí)間內(nèi)，在默認(rèn)設(shè)置的網(wǎng)絡(luò)中，各種移動(dòng)模型下的網(wǎng)絡(luò)可靠性變化趨勢(shì).可以看出，隨著操作時(shí)間的增加，網(wǎng)絡(luò)可靠性有所降低.這是因?yàn)?，隨著長(zhǎng)時(shí)間的工作，有些節(jié)點(diǎn)可能出現(xiàn)故障，致使其無(wú)法與其他節(jié)點(diǎn)連接.另外，可以看出，不同的模型具有不同的網(wǎng)絡(luò)可靠性.

綜上所有實(shí)驗(yàn)表明，節(jié)點(diǎn)的移動(dòng)性對(duì)MANET連接可靠性的影響不是很大，而網(wǎng)絡(luò)的大小、節(jié)點(diǎn)數(shù)和通信范圍對(duì)可靠性影響較大.

4 結(jié)束語(yǔ)

該文提出一種基于網(wǎng)絡(luò)中各節(jié)點(diǎn)間鏈接可靠性分析的MANET可靠性評(píng)估方法，在RWPM和GMM移動(dòng)模型下，對(duì)具備不同的網(wǎng)絡(luò)大小、節(jié)點(diǎn)數(shù)量和傳輸范圍的網(wǎng)絡(luò)進(jìn)行可靠性評(píng)估.提出的方法計(jì)算簡(jiǎn)單，且可擴(kuò)展為以k-終端或全終端可靠性為基礎(chǔ)的網(wǎng)絡(luò)可靠性評(píng)估，為網(wǎng)絡(luò)設(shè)計(jì)者在參數(shù)選擇時(shí)提供有效依據(jù).

[1] 何暉, 王換招, 李昊,等. 增強(qiáng)Ad Hoc網(wǎng)絡(luò)穩(wěn)定性的移動(dòng)問(wèn)題解決策略[J]. 西安交通大學(xué)學(xué)報(bào), 2011, 45(4): 6-11.

[2] 梁廣民, 王健. 移動(dòng)自組網(wǎng)中兼顧通信可靠性和鏈路長(zhǎng)度的可信路由協(xié)議[J]. 南京大學(xué)學(xué)報(bào):自然科學(xué)版, 2012, 48(2): 206-213.

[3] CHATURYEDI S K,PADMAVATHY N. The influence of scenario metrics on network reliability of mobile ad hoc network[J]. International Journal of Performability Engineering, 2013, 9(1): 61-74.

[4] PADMAVATHY N, CHATURVEDI S K. Evaluation of mobile ad hoc network reliability using propagation-based link reliability model[J]. Reliability Engineering & System Safety, 2013, 115(7):1-9.

[5] 鄒青丙, 何明, 王琰,等. 無(wú)線多跳網(wǎng)絡(luò)可靠性評(píng)估方法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(5): 88-91.

[6] CHEN B, PHILLIPS A, MATIS T I. Two-terminal reliability of a mobile ad hoc network under the asymptotic spatial distribution of the random waypoint model[J]. Reliability Engineering & System Safety, 2012, 106(3):72-79.

[7] JASON L C, JOSE E R. Mobility and reliability modeling for a mobile ad hoc network[J]. Iie Transactions, 2012, 41(1):23-31.

[8] AHMAD M, KUMAR MISHRA D. A reliability calculations model for large-scale MANETs[J]. International Journal of Computer Applications, 2012, 24(9):17-21.

[9] 夏曉峰, 何常勝. LSM結(jié)合鄰居干擾抵抗模型的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)故障檢測(cè)[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2016, 38(1):101-105.

[10] 何明, 陳秋麗, 陳希亮,等. 魚(yú)群?jiǎn)l(fā)的三維Ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)移動(dòng)優(yōu)化模型[J]. 儀器儀表學(xué)報(bào), 2014，35(12):2826-2834.

[11] YOUNES O, THOMAS N. Analysis of the expected number of hops in mobile Ad Hoc networks with random waypoint mobility[J]. Electronic Notes in Theoretical Computer Science, 2011, 27(5):143-158.

責(zé)任編輯：龍順潮

The Reliability Evaluation Scheme for MANET Based on Connection Matrix

ZHAOHe1*,GAILing2

(1.Department of Computer Science and Technology, Chengdu Neusoft University, Chengdu 611844;2.School of management,Shanghai University,Shanghai 200444 China)

The dynamic topology of mobile Hoc Ad network (MANET) makes it difficult to evaluate the reliability of the network, so a reliability evaluation scheme for MANET based on connection matrix is proposed. First, the source-terminal node pair and relay nodes in the network are determined. Then, the relay link state is detected according to the Euclidean distance between nodes and the communication range, so as to construct the connection matrix. Finally, the network connectivity is determined based on the connection matrix, and the average of connectivity value in some rounds is regard as the reliability of the network. In the simulation experiment, the influence of the node mobility model, the network size, the number of nodes and the range of communication on the network reliability is evaluated, which can provide a strong basis for network designers.

mobile Ad Hoc network; network reliability; connection matrix; node mobility model

2016-03-22

四川省教育廳科研項(xiàng)目(14ZB0350)

趙荷(1982-)，女,四川 榮縣人，講師.E-mail:zhaohe@nsu.edu.cn.

TP393

A

1000-5900(2016)03-0113-05