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

趙 荷， 蓋 玲

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

?

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

趙 荷1*， 蓋 玲2

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

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

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

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

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

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

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

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

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

1.2 節(jié)點移動模型

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

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

(1)

(2)

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

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

(3)

2 MANET可靠性評估方案

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

(4)

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

(5)

(6)

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

(7)

(8)

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

(9)

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

(10)

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

(11)

本文MANET可靠性評估方案分為2類，即不考慮節(jié)點移動性和考慮節(jié)點移動性的評估方案.

2.2 不考慮移動性時的可靠性評估方案

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

2.3 考慮移動性時的可靠性評估方案

3 仿真實驗

3.1 實驗設(shè)置

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

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

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

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

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

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

4 結(jié)束語

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

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

[2] 梁廣民, 王健. 移動自組網(wǎng)中兼顧通信可靠性和鏈路長度的可信路由協(xié)議[J]. 南京大學(xué)學(xué)報:自然科學(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ǎng)絡(luò)可靠性評估方法研究[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é)點故障檢測[J]. 湘潭大學(xué)自然科學(xué)學(xué)報, 2016, 38(1):101-105.

[10] 何明, 陳秋麗, 陳希亮,等. 魚群啟發(fā)的三維Ad hoc網(wǎng)絡(luò)節(jié)點隨機移動優(yōu)化模型[J]. 儀器儀表學(xué)報, 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

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

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

TP393

A

1000-5900(2016)03-0113-05