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

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

2.解放軍65655部隊

3.解放軍91857部隊

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

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

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

2.解放軍65655部隊

3.解放軍91857部隊

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法流程

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

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

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

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

步驟2設定節(jié)點的位置，確定網(wǎng)絡拓撲。lij(t)←所有節(jié)點對i，j，由式（2）計算得出。

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

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

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

αi(t)←服從[ ]

0，2π上的均勻分布。

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

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

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

3.3 復雜度分析

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

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

4.1 實驗說明

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

表1 節(jié)點初始位置坐標

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

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

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

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

圖3 節(jié)點運動軌跡仿真

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

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

5 結(jié)束語

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

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

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

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

[10]何明，陳國華，梁文輝，等.物聯(lián)網(wǎng)感知層移動自組織網(wǎng)可靠性評估方法[J].計算機科學，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

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

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

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.

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

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

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