基于双重虚拟力算法的移动自组织网络节点移动策略研究*

赵克华,刘半藤

(浙江树人大学信息工程学院,杭州 310015)

随着信息技术的高速发展,无线自组织网络MANETs(Wireless Mobile Ad Hoc Networks)已经逐渐发展成为21世纪信息产业的重要支柱。由于MANETs具备节点移动灵活、不受固有通信设施影响等特点,被广泛地应用于军事、民用、商业等领域。由于MANETs节点移动过程带来的不确定性容易出现连通性、覆盖率、生存时间等网络性能下降,专家学者开展了针对性的研究[1-7],也提出了多种节点移动策略,虚拟力移动策略就是其中的典型代表。

魏连锁等[1]对传统的虚拟力进行改进,将网络节点的邻居节点数量以及到邻居节点的距离进行属性加权修正虚拟力数值,提出一种锚节点移动策略。目前,基于虚拟力算法制定的节点移动策略多以提高网络整体覆盖率为研究目标[7-18]。张颖等[8]采用一种改进的虚拟力和果蝇优化算法对水下传感器网络进行节点部署。首先,将节点随机散布在网络中;然后,网络中的每个节点都按照虚拟力的方式进行定向移动,直至最优位置,从而实现整体网络的高效覆盖。王雪[9]等结合粒子群算法与虚拟力算法,提出了一种虚拟力导向微粒群优化策略,提高整体网络覆盖率,加快算法收敛速度。王婷婷[10]等提出了一种基于Voronoi多边形形心引力的虚拟力覆盖优化算法,可以有效地降低覆盖盲区,提高网络覆盖率。滕志军[11]等利用节点自身密集度来选择虚拟力模型中最优距离阈值,从而改进传统的虚拟力模型,最终实现网络节点的部署优化。Hamid Mahboubi[12]等采用多权重的Voronoi方法计算传感器的传感范围,提高网络覆盖的有效性。JIANG Yibo[13]等提出一种基于虚拟势场的虚拟力增强覆盖算法,对虚拟力的方向进行分解,再根据双节点覆盖模型,引入质心计算,通过虚拟势场修正虚拟力指标,对网络进行部署,以消除目标区域内的盲区和重叠区,提高网络覆盖率。GUAN Zhiyan[14]等提出了一种基于差分进化和混合虚拟力的定向传感器网络覆盖算法,利用差分进化模型和混合虚拟力来避免局部次优解,减少重叠面积,提高网络有效覆盖率。传统的虚拟力算法通过采集邻居节点的信息,并与事先确定的阈值进行比较判断,确定节点所受斥力或者引力的大小及方向。节点根据所受力的大小及方向进行定向移动。但传统的虚拟力阈值设置方式较为单一,主要考虑节点间的距离或者节点密度。MANET性能指标较多,区域覆盖率、节点连通性、网络生存时间等都需要考虑。因此,网络节点的最优移动策略属于多目标优化问题,一种NP-hard问题。为此,本文提出了一种双重虚拟力算法DVFA(Dual Virtual Force Algorithm),同时考虑网络节点密度分布与网络生存时间两项指标,计算节点所受到的斥力与引力,将两种不同属性的虚拟力进行融合,从而制定节点移动策略。

1 节点模型

1.1 节点移动模型

假设在区域为Sa×Sb的矩形MANET中部署N个可自由移动的节点,并为每个节点标号为1,2,…,N。在时刻t,标号为i的节点坐标表示为(xi(t),yi(t))。网络中的每个节点每隔Δt时间进行一次移动,节点的最大移动速率为vmax。节点的基本移动方式可以表达如下:

式中,(xi(t+Δt),yi(t+Δt))表示标号为i的节点移动后的坐标。假设节点移动过程中遇到网络边界时便进行反向移动。θi(t)表示标号为i的节点在时刻t的移动方向。vi(t)表示标号为i的节点在时刻t的移动速率,vi(t)∈[0,vmax]。节点移动策略就是确定各节点各时刻的移动方向和移动速率。

1.2 节点连通性模型

假设MANET中每个节点都具有相同通信半径Rcom以及相同覆盖半径Rcov,如图1所示。如果两个节点之间的距离小于通信半径Rcom,则认为此两个节点相互之间一跳连通。

图1 节点连通半径和覆盖半径示意图

由于节点处于移动状态,网络的连通矩阵也将随着时间推移发生变化。时刻t,网络节点之间的一跳(one hop)连通矩阵CO(t)=[coij(t)]N×N计算方式如下:

如果cij(t)=1,说明时刻t标号为i与标号为j的节点之间可以直接通信。

MANET中,节点具备信息收发与信息中转双重功能。不在一跳通信范围内的两个节点之间,可以通过其他节点作为中间节点转发信息实现通信业务。时刻t,节点之间的多跳(multi hops)连通矩阵CM(t)=[cmij(t)]N×N计算方式如下[19]:

式中,TM(t)=[tmij(t)]N×N为临时变量,表示节点之间通过N跳转发实现通信业务的情况。如果cmij(t)=1,说明时刻t标号为i与标号为j的节点之间可以通过多跳转发实现通信业务。时刻t,MANET的节点连通性指标LT(t)计算方式如下:

1.3 网络覆盖率模型

MANET中,每个节点都可以采集覆盖半径Rcov区域内的信息。网络覆盖率可以用被覆盖面积与整体网络面积之比进行衡量。考虑到连续性给覆盖率指标计算带来的复杂性,本文采用一种离散方式近似计算网络覆盖率[20-21]。将Sa×Sb的MANET以 1 m 为步长划分为网格,共计M个格点,并为每个格点标号为1,2,…,M,如图2所示。以被覆盖的格点数量与格点总数之比衡量网络覆盖率。

图2 MANET离散示意图

划分后的网格中,第i个格点的坐标表示为(pxi,pyi)。格点的坐标不随时间推移而发生变化。时刻t,节点与格点的覆盖矩阵F(t)=[fij(t)]N×M计算方式表达如下:

如果fij(t)=1,说明时刻t标号为i的节点可以覆盖标号为j的格点。当格点被一个及以上的节点覆盖时,可以认为该格点被覆盖。MANET覆盖矩阵G(t)=[gi(t)]M计算方式如下:

如果gi(t)=1,说明时刻t标号为i的格点可以被有效覆盖。因此,MANET的网络在时刻t覆盖率指标FG(t)计算方式如下:

图3 一阶能量消耗模型示意图

1.4 节点能耗模型

假设MANET中节点传输信息服从一阶能量消耗模型[22-23]。节点发送信息能耗包括发射电路能耗、放大电路能耗两部分,节点接收信息能耗仅为接收电路能耗,如图3所示。

一阶能量消耗模型计算公式如下所示:

式中,ETx表示节点发送信息能耗,Eelec表示发射电路和接收电路能耗,l表示发送数据的比特数,efs表示能耗常数,ds表示发送节点与接收节点之间的距离。

除发送信息和接收信息的能量消耗外,假设节点移动的能耗为一固定值,且由于节点待机时能耗较少,故本文假设待机能耗忽略不计。

2 双重虚拟力移动模型

2.1 双重虚拟力的基本思想

MANET中的每个节点都可以感知其通信范围内邻居节点的相关信息。虚拟力的基本思想可以归纳为:每个节点都将受到邻居节点的影响,这种影响以“力”的方式改变节点的移动方式。本节主要讨论与距离相关的“距离虚拟力”和与能量相关的“能量虚拟力”的设置方式,将两种属性的虚拟力进行融合提出了一种双重虚拟力算法DVFA。通过DVFA制定节点移动策略,从而确定节点的移动方向与移动速率。

MANET的节点分布不能过于密集,否则将造成MANET的覆盖率指标下降。同时,节点分布也不能过于稀疏,否则将造成MANET的连通性指标下降。为此,需要为每个节点配置距离阈值Td。当邻居节点与本地节点之间的距离超过距离阈值时,本地节点将向靠近该邻居节点方向移动;当邻居节点与本地节点之间的距离低于距离阈值时,本地节点将向远离该邻居节点方向移动,如图4所示。图中标号为1的节点通信范围内有4个邻居节点,可以感知此4个邻居节点到节点1的距离。节点2和节点5到节点1的距离小于距离阈值Td,节点1将向远离节点2和节点5的方向移动;节点3和节点4到节点1的距离大于距离阈值Td,节点1将向靠近节点3和节点4的方向移动。

图4 距离阈值示意图

由于网络中节点承担着信息转发的业务,需要避免低能量节点被频繁地作为中间节点转发信息,而降低网络生存时间。为此,需要为每个节点配置能量阈值tei。当邻居节点的剩余能量高于能量阈值时,本地节点将向靠近该邻居节点方向移动;当邻居节点的剩余能量低于能量阈值时,本地节点将向远离该邻居节点方向移动,从而降低该低能量节点作为中间节点转发信息的概率,如图5所示。图中标号为1的节点通信范围内有4个邻居节点,可以感知此4个邻居节点的剩余能量。节点3和节点5的剩余能量超过能量阈值te1,节点1将向靠近节点3和节点5方向移动;节点2和节点4的剩余能量低于能量阈值te1,节点1将向远离节点2和节点4的方向移动。

图5 能量阈值示意图

综上所述,节点1的移动方式受到其四个邻居节点的影响。这种影响通过能量与距离两种方式施加于节点1对其产生“能量虚拟力”与“距离虚拟力”,节点1将在两者合力的作用下进行移动,这就是本文的双重虚拟力算法DVFA。

2.2 双重虚拟力的参数设定

首先,讨论距离阈值Td的设定方式。距离阈值设定的目的是为达到节点均匀地分布于MANET。因此,可以考虑将节点均匀分布时,相邻两节点之间的距离作为距离阈值Td。在区域为Sa×Sb的MANET中部署N个节点,每个节点的覆盖范围用正六边形近似替代,如图6所示。因此,距离阈值Td的计算方式如下所示:

图6 距离阈值计算示意图

然后,讨论能量阈值tei的设定方式。以i表示本地节点的标号,Ui表示节点i的邻居节点集合。能量阈值设定的目的是为本地节点拉近高能量邻居节点,远离低能量邻居节点,延长网络生存时间。故可以考虑将时刻t节点i的邻居节点集Ui平均能量作为节点i的能量阈值tei(t)。由于每个节点的邻居节点集合不同,使得每个节点的能量阈值各不相同,且随着时间推移而发生变化。因此,能量阈值tei(t)的计算方式如下所示:

其中,Ej(t)表示时刻t邻居节点j的剩余能量。由于节点能量随着时间而下降,节点的能量阈值也将随着时间推移而发生变化。

3 数值仿真

为评估本文所提出的双重虚拟力DVFA而制定的节点移动策略对MANET整体性能产生的影响,本节采用MATLAB软件进行网络性能的数值仿真。在一个300 m×300 m的正方形网络区域,随机散布80个节点。以节点模块CC1100[25]作为参考,设定节点的最大移动速度为1 m/s,节点覆盖半径为60 m,通信半径为覆盖半径的1.2倍,统计进行节点100次移动的轨迹。与传统虚拟力算法VFA(Virtual Force Algorithm)[26]、改进的虚拟力算法TVFA(Triangulation for Virtual Force Algorithm)[27]相比较,在双重虚拟力DVFA作用下节点连通性随时间变化如图7所示,网络覆盖率随时间变化如图8所示。

图7 网络覆盖率指标随移动次数变化趋势图

图8 网络连通度指标随移动次数变化图

从图7、图8中可以发现:相较于其他两种虚拟力算法,DVFA移动策略可以获得更大的网络覆盖率(稳定在97%以上)。采用DVFA提升仿真效果主要有以下两点因素:①阈值设定方式;②虚拟力构造形式。这也是区别VFA和TVFA的主要不同所在。相比不同的阈值设定方式,非线性加权构造虚拟力模型使得仿真效果提升更加明显。DVFA所带来的节点连通性也更加稳定,连通度85%以上。

图9 网络覆盖率指标随节点数量变化趋势图

对于部署不同节点数量,分析获得的网络覆盖率与节点连通性变化趋势如图9、图10所示。从图9、图10中可以发现:相较于其他两种虚拟力算法,DVFA带来的网络性能提升优势较为明显。随着节点数量增长,网络覆盖率与节点连通度都将明显提高。在各节点数量,DVFA带来的网络覆盖率与网络连通度都高于VFA与TVFA。当在网络中部署100个节点时,可以实现网络覆盖率与节点连通度两项指标同时逼近100%。

图10 网络连通度指标随节点数量变化趋势图

对于为节点配置不同的覆盖半径,分析获得的网络覆盖率与节点连通性变化趋势如图11、图12所示。从图11、图12中可以发现:相较于其他两种虚拟力算法,DVFA带来的网络性能提升优势较为明显。随着覆盖半径增加,网络覆盖率与节点连通度都将明显提高。当覆盖半径增加时,网络覆盖率的指标差异性变小。

图11 网络覆盖率指标随覆盖半径变化趋势图

图12 网络连通度指标随覆盖半径变化趋势图

假设每个节点的初始能量为10 J。在信息传输采取最小跳数路由协议,且传输过程节点位置不发生移动。信息业务的源节点与目的节点随机产生,服从均匀分布,数值仿真800次业务传输。定义网络节点中能量最低的节点为瓶颈节点。由于节点能量时刻发生变化,瓶颈节点的标号也随时间发生变化。节点瓶颈能量变化随时间变化如图13所示,网络中生存节点数量随时间变化如图14所示。

图13 瓶颈节点随传输轮数变化趋势图

图14 生存节点数量随传输轮数变化趋势图

从图13、图14中可以发现:相较于其他两种虚拟力算法,DVFA可以有效降低瓶颈节点的能量消耗,保持网络中足够多的生存节点数量,延长网络生存时间。这是由于DVFA构造过程中考虑了“能量虚拟力”,降低低能耗节点作为中间节点转发信息的概率,避免节点过早地因为能量耗尽而退出网络,使得网络中节点能耗尽可能均衡。

4 结论

本文考虑能量与距离双重因素,提出一种基于双重虚拟力算法的节点移动策略。在节点移动时计算其邻居节点的距离与邻居节点的剩余能量,以非线性的方式构建“距离虚拟力”与“能量虚拟力”。通过将两种不同属性的虚拟力进行融合,确定节点移动的方向与速率。数值仿真显示,本文提出的策略可以提高网络覆盖率与节点连通性,并提高网络的生存时间。真实环境中,可能还需考虑的其他指标都可以加乘在虚拟力公式中,从而构成多重虚拟力移动模型。本文中提出的虚拟力模型具有较好的推广性。