三維環(huán)境中新的MAWN可靠性評估方法

何 明，陳國華，2，楊 飛，梁文輝，王秋陽

1.解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京 210007

2.解放軍65655部隊

3.解放軍91857部隊

三維環(huán)境中新的MAWN可靠性評估方法

何 明1，陳國華1，2，楊 飛1，梁文輝1，王秋陽3

1.解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京 210007

2.解放軍65655部隊

3.解放軍91857部隊

1 引言

移動自組織無線網(wǎng)絡(luò)（Mobile Ad-Hoc Wireless Network，MAWN）是一種具有自組織、無基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，通常是臨時組建，被認(rèn)為是未來移動通信技術(shù)的核心組成部分之一[1]。隨著移動自組織無線網(wǎng)絡(luò)在作戰(zhàn)偵察、應(yīng)急救援、臨時會議等重要領(lǐng)域應(yīng)用不斷深入，在三維環(huán)境下的網(wǎng)絡(luò)可靠性需求日漸迫切。探索影響網(wǎng)絡(luò)可靠性的各個因素之間的相互影響規(guī)律，對于指導(dǎo)MAWN在實際中的部署、實時監(jiān)控網(wǎng)絡(luò)運(yùn)行狀態(tài)、實時準(zhǔn)確地評估網(wǎng)絡(luò)的性能具有十分重要的意義。

2 國內(nèi)外研究現(xiàn)狀

傳統(tǒng)通信網(wǎng)絡(luò)可靠性評估研究相對成熟[2-5]，而目前針對MAWN可靠性研究的成果不多。Chen&Lyu在研究中把可靠性表示為一個與網(wǎng)絡(luò)中每個活躍節(jié)點(diǎn)的可靠性及網(wǎng)絡(luò)拓?fù)浯嬖跁r間占全部時間的比率相關(guān)的函數(shù)[6]。AboElFotoh等研究了無線廣播網(wǎng)絡(luò)可靠性計算，但只假設(shè)了節(jié)點(diǎn)失效，并未考慮節(jié)點(diǎn)移動導(dǎo)致的鏈路失效問題[7]。趙娟等提出了基于信息流動力學(xué)建立的通信網(wǎng)絡(luò)流量模型，并定義了信息流傳輸時延和分組丟失率表征網(wǎng)絡(luò)性能可靠性的指標(biāo)和評估模型[8]，但其成果是在通用通信網(wǎng)絡(luò)基礎(chǔ)上得出，并未擴(kuò)展到MAWN。趙蘊(yùn)平等提出了一種無線Mesh骨干層的2-終端可靠性計算策略[9]，考慮了無線環(huán)境下節(jié)點(diǎn)故障和節(jié)點(diǎn)間無線鏈路故障對網(wǎng)絡(luò)可靠性的影響，但對于節(jié)點(diǎn)處于移動狀態(tài)下的MAWN并無很好的適應(yīng)性。在前期的研究中提出了一種考慮節(jié)點(diǎn)移動的Ad Hoc網(wǎng)絡(luò)可靠性評估方法，但并未深入到三維環(huán)境[10]。總結(jié)現(xiàn)有評估方法，主要存在以下幾方面的不足：（1）未準(zhǔn)確描述節(jié)點(diǎn)移動對網(wǎng)絡(luò)可靠性的影響；（2）研究均局限于二維環(huán)境；（3）未考慮節(jié)點(diǎn)移動造成的網(wǎng)絡(luò)可靠性動態(tài)變化。

節(jié)點(diǎn)移動模型目前研究成果主要分為兩大類：基于知識積累的可提供準(zhǔn)確信息的軌跡模型和沒有軌跡知識基礎(chǔ)上試圖理想地表示節(jié)點(diǎn)移動的人工模型。自組織網(wǎng)絡(luò)研究中均采取了后者。已有移動模型的研究大都是在二維環(huán)境下進(jìn)行的，主要有單體模型和組模型。單體模型有隨機(jī)走動模型[11]、隨機(jī)路點(diǎn)遷移模型[12-14]、隨機(jī)方向模型[15]、無邊界模擬區(qū)域模型以及高斯-馬爾可夫移動模型[16]等。組模型包括指數(shù)相關(guān)隨機(jī)移動模型、游動社團(tuán)移動模型以及追蹤移動模型等。隨機(jī)路點(diǎn)遷移模型是目前進(jìn)行無線網(wǎng)絡(luò)各類性能仿真驗證、路由有效性研究中廣泛使用的模型。以上模型均建立在二維環(huán)境下，只考慮應(yīng)用于平面環(huán)境內(nèi)，現(xiàn)實應(yīng)用中，大量應(yīng)用背景是三維環(huán)境，因此，傳統(tǒng)二維環(huán)境下的節(jié)點(diǎn)模型無法準(zhǔn)確描述節(jié)點(diǎn)的移動規(guī)律，在未來的應(yīng)用中，急需建立三維環(huán)境節(jié)點(diǎn)移動模型。

3 三維空間考慮節(jié)點(diǎn)移動的MAWN可靠性評估方法

3.1 3D節(jié)點(diǎn)移動模型（3D-NMM）

在一個MAWN網(wǎng)絡(luò)G中，含N個節(jié)點(diǎn)，E條鏈路。V為節(jié)點(diǎn)集，節(jié)點(diǎn)i與節(jié)點(diǎn) j(i，j∈V)間的距離用dij表示，由式（1）可得：

定義節(jié)點(diǎn)i與節(jié)點(diǎn) j間的有效通信范圍為Rij。如式（2）所示，當(dāng)dij≤Rij時，節(jié)點(diǎn)i與節(jié)點(diǎn) j間存在鏈路，即lij=1，否則不存在，lij=0。

定義矩陣L，由lij組成(i，j∈V)，表示MAWN節(jié)點(diǎn)間鏈路的存在狀況。節(jié)點(diǎn)位置會受移動性影響而動態(tài)變化，因此表示網(wǎng)絡(luò)結(jié)構(gòu)的矩陣L也會動態(tài)變化。

提出如下移動模型：對于?i∈V，vi表示移動速率；αi表示水平方向角；φi表示垂直方向角。節(jié)點(diǎn)i每次經(jīng)過?t時間后，到達(dá)一個新位置，而后隨機(jī)選擇vi∈[ ] vmin，vmax、水平方向角和垂直方向角由式（3）、（4）、（5）計算出經(jīng)過?t后節(jié)點(diǎn)i的新位置，如圖1所示。

圖1 節(jié)點(diǎn)i經(jīng)?t后的位置變化示意

定義C代表網(wǎng)絡(luò)連通性向量，Ci(t)表示t時刻節(jié)點(diǎn)i到源節(jié)點(diǎn)的連通性。若t時刻節(jié)點(diǎn)i到源節(jié)點(diǎn)有一條路徑，則Ci(t)=1；否則Ci(t)=0。t時刻MAWN兩終端可靠性2TRm(t)由式（6）可得：

為了衡量全網(wǎng)可靠性，定義ξ表示網(wǎng)絡(luò)覆蓋率，即V中與源節(jié)點(diǎn)有路徑的節(jié)點(diǎn)數(shù)占全部節(jié)點(diǎn)數(shù)的比例。它可用來衡量較大規(guī)模網(wǎng)絡(luò)的可靠性。ξ(t)表示t時刻已根據(jù)節(jié)點(diǎn)移動性和運(yùn)行狀態(tài)確定了連通性的網(wǎng)絡(luò)覆蓋率，由式（7）可得：

3.2 算法流程

初始化：定義網(wǎng)絡(luò)參數(shù)，n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)；Rij為節(jié)點(diǎn)通信范圍；θ，β為韋伯分布參數(shù)；vmax、vmin為最大、最小速率；?t為時間增量；tmax為最大時間。

步驟1采用韋伯分布來模擬節(jié)點(diǎn)的可操作狀態(tài)，如式（8）所示：

在一輪仿真中，若根據(jù)韋伯分布確定某一節(jié)點(diǎn)初始狀態(tài)為不可操作，則在本輪后續(xù)仿真中保持狀態(tài)不變，即節(jié)點(diǎn)不可修復(fù)。

ni(t)←由θ，β決定的韋伯分布。

步驟2設(shè)定節(jié)點(diǎn)的位置，確定網(wǎng)絡(luò)拓?fù)?。lij(t)←所有節(jié)點(diǎn)對i，j，由式（2）計算得出。

步驟3廣度優(yōu)先搜索矩陣L，得到源節(jié)點(diǎn)的連通性向量C。以下偽代碼描述了對L的廣度優(yōu)先搜索，源節(jié)點(diǎn)作為第一個節(jié)點(diǎn)：

步驟4通過式（7），根據(jù)C(t)計算出ξ(t)。

步驟5基于3.1節(jié)中所提的MAWN節(jié)點(diǎn)移動方式，模擬網(wǎng)絡(luò)節(jié)點(diǎn)的移動性：

αi(t)←服從[ ]

0，2π上的均勻分布。

步驟6計算每個節(jié)點(diǎn)在下一個時間增量后的位置。分別使用公式（3）（4）（5）進(jìn)行計算。

步驟7t←t+?t，t從0→tmax不斷增大。隨著?t的不斷增加，重復(fù)進(jìn)行步驟1至步驟6。

步驟8從步驟1至步驟7重復(fù)仿真Q輪。計算t時刻從源節(jié)點(diǎn)到指定目標(biāo)節(jié)點(diǎn)的兩終端可靠性估值，q表示仿真的輪次序號：

3.3 復(fù)雜度分析

從算法各關(guān)鍵步驟來分析復(fù)雜度，其中步驟1節(jié)點(diǎn)可操作性初始化時間復(fù)雜度為O(n)，步驟2確定節(jié)點(diǎn)間鏈路存在性的時間復(fù)雜度為O(n2)，步驟3確定任一節(jié)點(diǎn)到源節(jié)點(diǎn)連通性的時間復(fù)雜度為O(n2)，步驟5和步驟6計算節(jié)點(diǎn)新位置的時間復(fù)雜度為O(n)。因此，實驗進(jìn)行Q輪，算法時間復(fù)雜度為Q·O(n2)。

4 實驗仿真及結(jié)果分析

4.1 實驗說明

為了驗證本文提出的三維環(huán)境下節(jié)點(diǎn)可移動的MAWN可靠性評估方法的正確性和有效性，利用MATLAB進(jìn)行了仿真實驗，模擬了節(jié)點(diǎn)數(shù)n=12的目標(biāo)網(wǎng)絡(luò)。假設(shè)運(yùn)動范圍為12 m×12 m×12 m的空間，設(shè)定節(jié)點(diǎn)初始坐標(biāo)如表1。各參數(shù)初始化設(shè)置如下：對于單位：

表1 節(jié)點(diǎn)初始位置坐標(biāo)

4.2 節(jié)點(diǎn)移動仿真及可靠性計算

根據(jù)門特卡羅概率算法，進(jìn)行Q=100輪仿真，分別計算了MAWN的兩終端可靠性2T?Rm隨時間的變化情況2T?Rm(t)及網(wǎng)絡(luò)覆蓋率ξ?隨時間的變化情況ξ?(t)。

圖2所示仿真結(jié)果，顯示了2T?Rm(t)和ξ?(t)的變化情況，兩曲線走勢基本一致，也即2T?Rm(t)和ξ?(t)均能很好地表示MAWN可靠性。圖3表示所有節(jié)點(diǎn)在仿真過程的運(yùn)動軌跡情況。

圖2 仿真初始節(jié)點(diǎn)配置情況

圖3 節(jié)點(diǎn)運(yùn)動軌跡仿真

為掌握節(jié)點(diǎn)通信范圍及移動速度等因素對網(wǎng)絡(luò)可靠性的影響，進(jìn)行如下仿真分析，圖4為在（單位：m/min）的情況下，分別選取通信范圍Rij=3 m和5 m時網(wǎng)絡(luò)可靠性的ξ?(t)曲線情況，可以看出，通信半徑越大，網(wǎng)絡(luò)可靠性越高；圖5是在的情況下，分別選?。▎挝唬簃/min）和（單位：m/min）時網(wǎng)絡(luò)可靠性曲線情況，可以看出，移動速度越慢，網(wǎng)絡(luò)可靠性越高。

圖4 通信半徑對可靠性的影響

5 結(jié)束語

本文提出了一種新的三維空間內(nèi)考慮節(jié)點(diǎn)移動的MAWN可靠性評估方法，并通過仿真實驗證明了該方法的有效性和可行性，同時探索了移動模型中各參數(shù)對可靠性的影響規(guī)律。本文研究成果對提升MAWN網(wǎng)絡(luò)性能以及合理部署網(wǎng)絡(luò)節(jié)點(diǎn)具有重要的指導(dǎo)意義。實際應(yīng)用環(huán)境中，節(jié)點(diǎn)間鏈路存在著一定的有效帶寬，而帶寬同樣影響著網(wǎng)絡(luò)服務(wù)能力，進(jìn)而間接影響網(wǎng)絡(luò)的可靠性，探索帶寬與可靠性的關(guān)系將是今后的一個研究切入點(diǎn)。

圖5 節(jié)點(diǎn)移動速度對可靠性的影響

[1]Chlamtac I，Conti M，Liu J J N.Mobile ad hoc networking：imperatives and challenges[J].Ad Hoc Networks，2003，1：13-64.

[2]Altiparmak F，Dengiz B，Smith A E.A general neural network model for estimation telecommunications network reliability[J].IEEE Transactions on Reliability，2009，58（1）：56-63.

[3]Botev Z I，L’Ecuyer P，Rubino G，et al.Static network reliability estimation via generalized splitting[J].INFORMS Journal on Computing，2012，24（2）：324-330.

[4]Goyal N K.Network reliability evaluation with changes in layout[J].International Journal of Performability Engineering，2010，6（1）：63-67.

[5]Li Ruiying，Kang Rui，Huang Ning，et al.A practical approach for network application reliability assessment[J].Maintenance and Reliability，2009，43（4）：17-27.

[6]Chen Xinyu，Lyu M R.Reliability analysis for various communicationschemesinwirelessCORBA[J].IEEE Transactions on Reliability，2005，54（2）：232-242.

[7]AboEIFotoh H M，Colbourn C J.Computing 2-terminal reliability for radio-broadcast networks[J].IEEE Transactions on Reliability，1989，38（5）：538-555.

[8]趙娟，郭平，鄧宏鐘，等.基于信息流動力學(xué)的通信網(wǎng)絡(luò)性能可靠性建模與分析[J].通信學(xué)報，2011，32（8）：159-163.

[9]趙蘊(yùn)平，單寶龍，高振國，等.無線Mesh網(wǎng)骨干層2-終端可靠性計算策略[J].計算機(jī)學(xué)報，2009，32（3）：424-430.

[10]何明，陳國華，梁文輝，等.物聯(lián)網(wǎng)感知層移動自組織網(wǎng)可靠性評估方法[J].計算機(jī)科學(xué)，2012，39（6）：104-106.

[11]Sanchez M，Manzoni P.Anejos：a java based simulator for ad-hocnetworks[J].FutureGenerationComputerSystems，2001，17（5）：573-583.

[12]Johnson D B，Maltz D A.Dynamic source routing in ad hoc wirelessnetworks[M].[S.l.]：KluwerAcademicPublishers，1996.

[13]Broch J，Maltz D A，Johnson D B，et al.A performance comparison of multihop wireless ad hoc network routing protocols[C]//Proceedings ofACM InternationalConference on Mobile Computing and Networks（MOBICOM），Dallas，TX，USA，1998.

[14]Musolesi M，Mascolo C.Mobility models for systems evaluationa survey[C]//Middleware for Network Eccentric and Mobile Applications，2009：43-62.

[15]Royer E，Melliar-Smith P M，Moser L.An analysis of the optimum node density for ad hoc mobile networks[C]//Proceedings of the IEEE International Conference on Communications（ICC），2001.

[16]Camp T，Boleng J，Davies V.A survey of mobility models for ad hoc network research[J].Wireless Communications& Mobile Computing，2002，2（5）：483-502.

HE Ming1,CHEN Guohua1，2,YANG Fei1,LIANG Wenhui1,WANG Qiuyang3

1.College of Command Information Systems,PLA Science and Technology University,Nanjing 210007,China
2.Unit 65655 of PLA,China
3.Unit 91857 of PLA,China

In order to deploy Mobile Ad-Hoc Wireless Network（MAWN）effectively in 3-D environment and improve its reliability,the Nodes Mobility Model（NMM）in 2-D environment is expanded to 3-D environment.A NMM in 3-D environment is established（3-D_NMM）,in which the nodes mobility characteristic is fully considered.A novel?t-based dynamic MAWN reliability evaluation method is proposed.The simulation results show that the MAWN reliability could be calculated within the timeQ·O(n2).

Mobile Ad-Hoc Wireless Network（MAWN）;reliability evaluation;nodes mobility model;link existence

為有效指導(dǎo)三維環(huán)境中的移動自組織無線網(wǎng)絡(luò)（MAWN）的部署并提高其可靠性，充分考慮節(jié)點(diǎn)移動特性，將節(jié)點(diǎn)在二維環(huán)境下的移動拓展到三維環(huán)境，構(gòu)建了一種新的三維環(huán)境中節(jié)點(diǎn)移動模型（3D_NMM），在該模型基礎(chǔ)上，提出了一種基于增量?t的動態(tài)可靠性度量方法。仿真驗證了方法的有效性和可行性，實驗結(jié)果表明該方法能在Q·O(n2)時間內(nèi)計算出MAWN的可靠性。

移動自組織無線網(wǎng)絡(luò)；可靠性評估；節(jié)點(diǎn)移動模型；鏈路存在性

A

TP302.1

10.3778/j.issn.1002-8331.1304-0395

HE Ming,CHEN Guohua,YANG Fei,et al.Novel MAWN reliability evaluation method in 3D environment.Computer Engineering and Applications,2013,49（23）：67-70.

國家自然科學(xué)基金面上項目（No.61174198，No.61203192）；江蘇省自然科學(xué)基金項目（No.BK2011124，No.BK2012326，No.BK2010129）。

何明（1978—），男，博士后，副教授，碩士生導(dǎo)師,研究領(lǐng)域為建模與仿真、信息物理融合系統(tǒng)；陳國華（1986—），男，碩士研究生，研究方向為物聯(lián)網(wǎng)、網(wǎng)絡(luò)安全；楊飛（1973—），女，講師，研究領(lǐng)域為計算機(jī)仿真。

2013-04-26

2013-07-01

1002-8331（2013）23-0067-04

CNKI出版日期：2013-09-05 http://www.cnki.net/kcms/detail/11.2127.TP.20130905.1047.002.html