三维环境中新的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