三維環境中新的MAWN可靠性評估方法

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

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

2.解放軍65655部隊

3.解放軍91857部隊

三維環境中新的MAWN可靠性評估方法

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

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

2.解放軍65655部隊

3.解放軍91857部隊

1 引言

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

2 國內外研究現狀

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

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

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

3.1 3D節點移動模型（3D-NMM）

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

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

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

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

圖1 節點i經?t后的位置變化示意

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

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

3.2 算法流程

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

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

在一輪仿真中，若根據韋伯分布確定某一節點初始狀態為不可操作，則在本輪后續仿真中保持狀態不變，即節點不可修復。

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

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

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

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

步驟5基于3.1節中所提的MAWN節點移動方式，模擬網絡節點的移動性：

αi(t)←服從[ ]

0，2π上的均勻分布。

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

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

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

3.3 復雜度分析

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

4 實驗仿真及結果分析

4.1 實驗說明

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

表1 節點初始位置坐標

4.2 節點移動仿真及可靠性計算

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

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

圖2 仿真初始節點配置情況

圖3 節點運動軌跡仿真

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

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

5 結束語

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

圖5 節點移動速度對可靠性的影響

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

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

[10]何明，陳國華，梁文輝，等.物聯網感知層移動自組織網可靠性評估方法[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

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

移動自組織無線網絡；可靠性評估；節點移動模型；鏈路存在性

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—），男，博士后，副教授，碩士生導師,研究領域為建模與仿真、信息物理融合系統；陳國華（1986—），男，碩士研究生，研究方向為物聯網、網絡安全；楊飛（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