基于粒子滤波步行长度预测的移动ad hoc网络路由算法*

张 玲,聂少华

(1.北京信息职业技术学院电子工程系，北京　100015；2.临沂大学初等教育学院，山东临沂　276000)

基于粒子滤波步行长度预测的移动ad hoc网络路由算法*

张 玲**1,聂少华2

(1.北京信息职业技术学院电子工程系，北京100015；2.临沂大学初等教育学院，山东临沂276000)

针对移动ad hoc网络拓扑结构变化大、路由复杂度高、数据传输性能低等问题,提出了一种新的移动通信系统自适应路由算法。为了使得网络拓扑结构更接近移动网络间歇性连接的特点,该算法在网络结构上采用了一种改进的Levy Wa1k移动模型。采用一种粒子滤波步行长度预测的方法,通过蒙特卡罗抽样得到递归贝叶斯滤波器,并在粒子滤波后进行步行长度预测,确定消息的副本数量,从而减少由于节点转发过多消息副本带来的能量消耗量,提高消息的传递效率。实验仿真结果表明:与基于改进蚁群优化和利润优化模型的路由算法相比,该算法的消息传递成功率分别提高了0.08和0.04,节点平均能量效率提高了17.9%和13.4%,在提升数据传输成功率和节能上具有较好效果。

移动ad hoc网络;粒子滤波;步行长度预测;Levy Wa1k移动模型;自适应路由算法

引用格式:张玲，聂少华.基于粒子滤波步行长度预测的移动ad hoc网络路由算法[J].电讯技术，2016，56(3)：331-336.[ZHANG Ling，NIE Shaohua.A mobi1e ad hoc network routing a1gorithm based on wa1king 1ength Prediction after Partic1e fi1tering[J].Te1ecommunication Engineering，2016，56(3)：331-336.]

1　引 言

移动自组织网络(Mobi1e ad hoc Network，MANET)作为一种无预置基础设施的动态可重构无线网络，具有广泛的应用价值，可以应用于救灾、移动监测、现代战场、移动医疗等多个领域。在MANET中网络节点具有随机的移动性，节点可以充当路由器为其他节点转发数据包，也可以作为主机将其他节点的数据进行汇聚[1-2]。然而，与静态无线传感器网络(Static Wire1ess Sensor Network，SWSN)相比，研究MANET更加困难。这是由于MANET具有高速的移动性，会导致网络拓扑结构的变化，加重路由复杂程度，对网络的通信性能造成一定的影响。而且，由于网络中各节点的移动速度和移动模式的随机性，会使信道带宽以及节点能量受限，对网络寿命也会造成一定影响[3]。目前，针对MANET的路由算法研究取得了一定进展，然而由于移动环境下网络拓扑结构的不断变化，节点链路的持续通信问题仍是一个重要的挑战[4-5]。

为了提高移动通信网络的稳定性，唐夲等[6]提出了一种MANET多参数加权分簇算法，综合考虑了节点剩余能量、邻居节点数和节点移动性，针对随机步行移动网络设计不同的节点稳定性参数，并基于约束规则和节点稳定性参数加权准则，有效提高了网络簇结构的稳定性。虽然该方法可通过更稳定的簇结构提高数据传输成功率，但节点通信量增多，能量消耗量增大。夏辉等[7]提出了MANET中基于链路稳定性预测的组播路由协议，将一种新颖的链路稳定性预测模型应用于传统组播路由协议中，而且基于反应式方式建立一棵高效的稳定组播树以更好地适应网络拓扑变化，能够显著地提高分组投递率，降低分组端到端平均传输延时，且控制开销较小，但对链路环境的考虑过于理想，链路干扰情况会影响预测结果。陈丽等[8]提出一种车载ad hoc网络中基于移动网关的数据传输技术，运用马尔可夫决策方法建立了一种基于MG转发的I2V数据传输优化模型，并使I2V传输延迟最小的路口节点作为数据包与目的车辆的最优汇聚节点，以最优概率转发序列向目标节点转发数据包，能够获得最小传输延迟期望，然而该方法使得路口节点具有较大的能量负担。Shubhajeet等[9]提出一种基于改进蚁群优化的MANET增强型动态源路由算法，可以降低数据包投递过程中的端到端延迟和能源消耗，采用蚁群算法依靠信息素浓度搜索路线的启发式方法，选择平均信息素水平最高的最佳路线用于数据分组传送。但该方法需要较多的迭代次数来选择链路，影响算法对现实情况的反应时间。Chao等[10]提出一种MANET跳频多通道MAC协议，该协议是一个多会合协议，解决接收数据的丢失问题，可以避免交换控制消息，具有较低的信令开销并能实现较高的吞吐量，但网络拓扑的变化会对算法性能造成较大影响。Chu等[11]提出一种利润优化模型的MANET路由协议，采用了经济学领域的一种数学模型利润优化模型(凯利公式)，并引入到节点的移动性路由的选择问题，将能耗、延迟等多种服务质量(Qua1ity of Service，QoS)指标作为路由的利润问题，从而选择QoS指标最优的路由。但该方法对网络的移动模型并没有进行更深入地分析，而现实中节点的移动方式会对路由的选择带来较大影响。

针对网络拓扑变化对ad hoc网络路由带来的影响，本文受Levy Wa1k流动模型的启发，提出了一种反映移动网络间歇性连接的移动模型，能更加真实地反映节点移动轨迹和节点流动性，并根据粒子滤波的步行长度预测提出自适应路由算法。

2　网络模型假设

在移动自组织网络中，有研究显示，采用单信息副本路由将一个信息传递到目的地，往往会导致较低的成功传递率并伴随较高的传输延迟，而转发太多的信息副本会降低信息传递效率。因此，针对间歇连接的移动网络[12-13]，本文提出的自适应路由算法将主要研究三个方面的问题：如何最小化传输的信息数目；尽可能地降低传输延迟；实现较高的数据包成功投递率。

在进行路由算法的讨论之前，本文假设网络模型具有如下特点：

(1)m个节点在面积为L×L的区域内随机分布，并且独立随机移动；

(3)用vms表示信息的传输速度，vn表示节点的移动速度，并且消息的传输速度比一个节点的移动速度要快得多；

(4)节点之间的链路是双向的，所有的数据包的大小相同，并且节点具有相同的传输速率；

(5)从一个源节点到一个目的节点的方向和距离仍未知。

3　Levy Walk移动模型

大多数MANET的路由协议和延迟容忍网络的路由协议都是采用随机或功能性的节点流动模型，在这些流动模型中，移动节点大多数时间都是与相邻节点通信，从源节点将数据转发到目的地需要较长的时间。因此，在本文算法中采用Levy Wa1k移动模型。Levy Wa1k移动模型的移动节点可以具有更长的移动长度，这增加了与多个远程节点进行通信的机会，并提高了信息转发至目的地的机会，并且Levy Wa1k移动模型更接近移动网络间歇性连接的特点，具有更加真实的移动轨迹和节点流动性。文献[16]已证明了1evy wa1k模型在表征移动网络路由性能上的重要性[16]。

根据Levy Wa1k的统计特性，行走长度可分为长步行长度和短步行长度。短步行长度反映地域的限制作用，长步行长度反映节点想快速到达一些目的地的主观意图，具有更多的真实性。在Levy Wa1k移动模型中有4个重要的变量，行走长度l、方向角度θ、行走时间t和暂停时间tT。行走长度l和暂停时间tT可以从Levy分布的概率密度函数中随机选择。Levy分布的表达函数如下：

当λ=1时，Levy分布是一个柯西分布；当λ=2时是高斯分布；当λ＜2时，函数近似为

根据Levy分布，行走长度l可以被描述为

同样地，行走时间t可以描述为

为了使Levy Wa1k移动模型更加适应间歇性连接的网络，本文在节点步长上引入了最短和最长步长lmin、lmax。因此，新的步长模型可以描述为

式中：lmin、lmax分别由网络节点中最小和最大的速度测量值所决定。对于暂停时间tT，定义为在一个较小的范围内均匀分布：

方向角度θ的取值为(0°，360°)。

4　基于粒子滤波步行长度预测的路由算法

在提出Levy Wa1k移动模型后，接下来是将该移动模型与路由策略进行结合，通过节点的移动距离来确定消息的副本数量。因此，需要了解每个路由步骤的节点行走长度。本文采用了粒子滤波的方法来实现步行长度预测，而粒子滤波的方法是通过蒙特卡罗抽样来得到一种递归贝叶斯滤波器。

本文先将节点的行走长度建模为一个状态变量lk，根据状态转移方程可描述为

状态转移方程反映从状态(k) -1到状态k的概率。xk表示测量变量，可以得到测量公式为

式中：h(xk)表示测量函数，可以表示状态变量lk和测量变量xk之间的关系。动态系统模型可以表示为

式中：lk表示在第k步的状态值；lk-1表示在第k-1步的状态值；uk是测量值输入；pk是不可测量的值；ξk是测量误差；a、b和c都表示函数系数。

由于动态系统模型很难描述在步骤(k-1，) k之间的行走长度的关系，因此本文采用的方法是间接地预测行走长度。首先建立一个函数来反映在第k步和k-1步中节点的步行长度总和之间的关系，接着在第k步中预测的步行长度的值将通过计算两个总和之间的差值来得到。令Sk表示第k步的状态测量值矢量，Sk=(x1，x2，…，xk)。为了获得准确的状态值，本文首先进行预测操作：

预测结果是基于先前k-1个观测量，然后添加第k个观测量来更新结果：

对于后先验结果，本文使用了一组样本或粒子来表示后验概率：

并得到近似密度q(l)为

式中：φi的表达方程式为其中：Q(li)是重要性密度函数。

求出近似密度q(l)之后，将进行步行长度预测。下面给出具体流程。

式中：1＜Ne＜NTh；当所有的粒子具有相同的权重时Ne=NTh，并且当所有的概率集中在一个粒子时Ne= 1。阈值NTh设定为

Step 5 令k=k+1，并返回SteP 2。

lk表示粒子第k步的步行总和，lk-1表示粒子第k-1步的步行总和。

通过基于粒子滤波的方法得到步行长度l之后，本文提出了一个分段函数来确定消息发送的副本数量：

式中：M是消息的副本数量；l表示步行长度；α、β和γ都表示相应的变换系数。当确定了消息副本的数量N后，本文所制定的路由规则如下：

(1)为每一个消息副本建立一个存活时间T，一旦一个消息的存活时间达到T时，这个消息副本将被丢弃；

(2)每个传感器节点都有对应的路由表记录其自身的ID，当两个节点满足通信距离的要求时，它们首先检查每个人的信息表，如果有消息副本是它们没有共同拥有的，则一个传感器会将消息副本转发给没有该消息副本的传感器节点；

(3)一旦消息副本顺利到达目的地，则目的节点将发送一个确认消息，当其他传感器节点接收到该确认消息，将会删除掉存留的该消息副本。

5　实验仿真及分析

为了验证本文提出的基于粒子滤波步行长度预测的移动通信系统自适应路由算法的性能，本文在实验中采用Mat1ab 7.1仿真软件对算法进行编程仿真。考虑到移动通信节点在部署区进行数据监测时并不仅限于单一的移动方向，因此在实验过程中采用的Levy Wa1k移动模型没有节点移动的方向限制，移动角度范围0°～360°，阈值NTh=10保证样本的有效数量达到一定条件不出现较大的随机概率。由于测量值、不可测量和测量误差对节点步行的状态值都具有一定的影响程度，在本实验中将动态系统模型的函数系数设置为a=b=c=1，粒子滤波步行长度预测模型的变换系数设置为

在实验条件不另外说明的条件下，仿真实验中默认的随机部署节点有50个，节点的移动速度取值范围为(2 m/s，10 m/s)，节点随机均匀分布在500 m×500 m的矩形区域，通信半径为50 m。其中环境参数的设置参考了对比算法的实验仿真条件，使得仿真结果的可对比性更高。每次的仿真实验数据是进行50次仿真后所得结果的平均值，这可以将实验数据结果的随机性大大减小，并且该仿真次数下所得的平均值随着仿真次数的增多而变化的情况非常小。

对于ad hoc网络路由算法的性能评价，本文算法与文献[9]中Shubhajeet等提出一种基于改进蚁群优化的方法以及文献[11]中Chu等提出的基于利润优化模型的方法进行对比。图1显示了在消息存活时间从50 s变化到400 s的过程中路由算法的消息成功投递率，从图中可以看出，随着消息存活时间的增加，消息的成功投递率也会增加。因为从源节点转发数据到目的节点需要一定的时间，这个时间受到节点移动速度、节点数量等的影响，但消息的存活时间越长，则转发到目的地的成功率也就更大。在图1中，本文算法的消息成功投递率最高达到了0.85，而基于改进蚁群优化的路由方法只达到了0.77，基于利润优化模型的路由方法则为0.81。因此，相比之下本文的路由算法在传递消息时具有更大的成功率。这是由于在消息的存活期间，本文所制定的路由规则能够确定出所需要的消息副本数量，防止节点转发过多消息副本，提高消息的传递效率，而另外两种方法对消息副本数并没有达到数量上的控制，节点转发多余的消息副本，影响了数据的传输效率。

大学生在返乡就业创业过程中面临的问题很多，除其自身就业创业能力不足外，更主要的是社会对大学生返乡就业创业的支持力度不够，特别是在政策、资金、教育等方面的支持还存在很多不足。

图1　消息成功投递率Fig.1 Successfu1 de1ivery rate of messages

图2为算法的节点平均能量消耗的对比情况，可见随着节点数量的增长，节点的平均能量消耗量都逐渐下降，但下降幅度逐渐变小。由于节点数量的增多使得带有消息的节点将消息转发给下一个节点时的传输距离变小，因此花费在传输能耗上的代价变低，节点的平均能量消耗量随之减小。节点能量是维持传感器网络正常运作的生命力，因此常作为评价路由算法的重要指标之一。本文算法的平均能量消耗量在80个节点时可以降到0.67 J，而文献[9]和文献[11]算法则分别为0.79 J和0.76 J。因此，相比这两种算法，采用本文方法可以使每个节点分别减少0.12 J和0.09 J的能量。由于目的节点接收到消息副本后会发送确认消息给其他节点，防止相同的消息副本继续在节点之间进行传输，节省了一定的传输能耗，而其他算法在目的节点接收数据后并没有对相同的消息副本进行删除处理，无法减少多余的消息副本带来的能量流失。

图2　节点平均能量消耗Fig.2 Average energy consumPtion of nodes

图3显示了消息传递延迟的对比情况，可见消息的传递延迟时间越长，则网络的数据传输效率越低。从图中可以看出，随着节点个数的增多，每个节点转发消息的距离越短，带来的消息传递延迟相应缩短。本文提出的算法在节点个数少于35个时消息传递延迟大于基于利润优化模型的方法，但在节点个数大于35时消息传递延迟相比另外两种算法更短。这是由于本文在实现节点的步行长度预测时需要一定的节点数量来确定后验概率，因此节点数量较少时不利于预测精度的提升，步行长度较大或较短时都会使源节点传输数据到达目的节点的延迟时间变长。最终当节点个数增加到80个时延迟时间仅为9.4 ms，而另外两种算法分别为15.7 ms和13.3 ms，相比之下分别缩短了6.3 ms和3.9 ms。因此，采用本文算法可以在网络传递数据时带来更少的延迟时间。

图3　消息传递延迟Fig.3 Message de1ivery de1ay

6　结束语

本文提出了一种基于粒子滤波步行长度预测的移动通信系统自适应路由算法，采用了改进的Levy Wa1k移动模型，可以更加真实地表征网络节点的移动轨迹和节点流动性；接着采用粒子滤波的方法来实现步行长度预测，通过预测粒子的行走长度来确定消息的副本数量，并通过制定的路由规则来传递消息。实验仿真和对比分析表明，本文算法的消息成功投递率可以达到85%，高于基于改进蚁群优化和利润优化模型的路由算法，并且本文的方法相比这两种对比算法分别可以使每个节点的能量消耗量减少0.12 J和0.09 J，在提高移动通信系统的数据传输效率和节能方面表现出了更好的效果。该算法的不足之处在于进行步行长度预测时需要一定的节点数量来提升预测精度，因此在今后的研究中会重点关注这个问题，使得在移动节点较少的网络场景中本文算法仍能保持较高的数据传输效率。

[1] LEE S B，WONG S H Y，LEE K W，et a1.Content management in a mobi1e ad hoc network：beyond oPPortunistic strategy[J].Internationa1 Journa1 of Communication Networks&Distributed Systems，2013，10(2)：266-270.

[2] JANARTHANAN S，VICTOIRE T A A.Qua1ity of service routing issues in mobi1e ad hoc network-review[J].Internationa1 Journa1 of Scientific Engineering and Techno1ogy，2013，2(5)：431-437.

[3] AGGARWAL P，AGGARWAL H.Energy-efficiency based ana1ysis of routing Protoco1s in mobi1e ad-hoc networks(MANETs)[J].Internationa1 Journa1 of ComPuter APP1ications，2014，96(15)：15-23.

[4] TAILOR R，BARIA J.The study of wormho1e attack in mobi1e ad hoc network[J].Internationa1 Journa1 of Com-Puter APP1ications，2014，87(18)：20-25.

[5] GULATI M K，KUMAR K.Performance comParison of mobi1e ad hoc network routing Protoco1s[J].Internationa1 Journa1 of ComPuter Networks&Communications，2014，6(11)：77-84.

[6] 唐夲，刘改霞，钟汶娟.移动ad hoc网络多参数加权分簇算法[J].重庆大学学报，2014，37(2)：107-112.

TANG Tao，LIU Gaixia，ZHONG Wenjuan.Mobi1e ad hoc network is a mu1ti Parameter weighted Points c1ustering a1-gorithm[J].Journa1 of Chongqing University，2014，37 (2)：107-112.(in Chinese)

[7] 夏辉，贾智平，张志勇，等.移动ad hoc网络中基于链路稳定性预测的组播路由协议[J].计算机学报，2013，36(5)：927-936.

XIA Hui，JIA ZhiPing，ZHANG Zhiyong，et a1.Mu1ticast routing Protoco1 based on 1ink stabi1ity Prediction in mobi1e ad hoc networks[J].Journa1 of ComPuter Science，2013，36(5)：927-936.(in Chinese)

[8] 陈丽，李治军，姜守旭，等.车载ad hoc网络中基于移动网关的数据传输[J].计算机学报，2012，35(3)：454-463.

CHEN Li，LI Zhijun，JIANG Shouxu，et a1.Data transmission based on mobi1e gateway in hoc ad networks[J]. Journa1 of ComPuter Science，2012，35(3)：454-463. (in Chinese)

[9] CHATTERJEE S，DAS S.Ant co1ony oPtimization based enhanced dynamic source routing a1gorithm for mobi1e Ad -hoc network[J].Information Sciences，2015，295 (295)：67-90.

[10] CHAO C M，TSAI H C.A channe1-hoPPing mu1tichanne1 MAC Protoco1 for mobi1e ad hoc networks[J].IEEE Transactions on Vehicu1ar Techno1ogy，2014，63(9)： 4464-4475.

[11] WANG C，DING J，CHEN T.A routing Protoco1 for mobi1e ad-hoc networks using the Profit oPtimization mode1 [J].Internationa1 Journa1 of Communication Systems，2014，27(11)：2851-2869.

[12] UPADHYAY S，JOSHI P，KUMARI N G A A.ComParison and Performance ana1ysis of reactive tyPe DSR，AODV and Proactive tyPe DSDV routing Protoco1 for wire1ess mobi1e ad-hoc network using NS-2 simu1ator [J].Journa1 of Engineering and ComPuter Innovations，2012(2)：36-47.

[13] RAHMAN M A，ANWAR F，NAEEM J，et a1.A simu1ation based Performance comParison of routing Protoco1 on mobi1e ad-hoc network(Proactive，reactive and hybrid) [C]//Proceedings of 2010 IEEE Internationa1 Conference on ComPuter and Communication Engineering. Kua1a LumPur：IEEE，2010：1-5.

[14] HABBAL A M M，HASSAN S.Loss detection and recovery techniques for TCP in mobi1e ad hoc network [C]//Proceedings of Second Internationa1 Conference on Network APP1ications Protoco1s and Services.Kedah：IEEE，2010：48-54.

[15] ROCHI M H B，DANA A，ZIYAEE M，et a1.A new source routing mechanism in mobi1e ad-hoc network [C]//Proceedings of 2011 13th Internationa1 Conference on Advanced Communication Techno1ogy.Seou1：IEEE，2011：948-952.

[16] RHEE I，SHIN M，HONG S，et a1.On the 1evy-wa1k nature of human mobi1ity[J].IEEE/ACM Transactions on Networking，2011，19(3)：630-643.

张 玲(1979—)女，山东平度人，2008年于北京邮电大学获硕士学位，现为北京职业技术学院讲师，主要研究方向为图形图像处理、信号传输、媒体设备应用、电子技术、编解码算法研究等；

ZHANG Ling was born in Pingdu，Shandong Province，in 1979.She received the M.S.degree from Beijing University of Posts and Te1ecommunications in 2008.She is now a 1ecturer.Her research concerns imaging Processing，signa1 transmission，media equiPment aPP1ication，e1ectronics and coding a1gorithms.

聂韶华(1972—)男，山东费县人，2008年于哈尔滨理工大学获硕士学位，现为讲师，主要研究方向为计算机科学于技术、教育信息技术。

NIE Shaohua was born in Feixian，Shandong Province，in 1972.He received the M.S.degree from Harbin University of Techno1ogy in 2008.He is now a 1ecturer.His research concerns comPuter science and education information.

A Mobile ad hoc Network Routing Algorithm Based on Walking Length Prediction after Particle Filtering

ZHANG Ling1，NIE Shaohua2
(1.DePartment of E1ectronic Engineering，Beijing Information Techno1ogy Co11ege，Beijing 100015，China；2.E1ementary Education Co11ege，Linyi University，Linyi 276000，China)

For the Prob1ems of mobi1e ad hoc network(MANET)such as big change of toPo1ogy structure，high routing comP1exity，and 1ow data transmission Performance，this PaPer ProPoses a new mobi1e communication system using an adaPtive routing a1gorithm.In order to make the network toPo1ogy c1oser to the characteristics of the mobi1e network intermittent connection，an imProved Levy Wa1k Mobi1ity Mode1 is adoPted in the network structure.And then，a Partic1e fi1tering wa1king 1ength method Prediction is used to get a recursive Bayesian fi1ter throush Monte Car1o samP1ing，and the wa1king 1ength is Predicted after Partic1e fi1tering to determine the number of coPies of message，thereby reducing the energy consumPtion for node forwarding a coPy to bring too many messages and imProve the message de1ivery efficiency.Simu1ation resu1ts show that comPared with two routing a1gorithms of ant co1ony-based oPtimization and Profit oPtimization-based mode1，the ProPosed a1gorithm imProves the message Passing success rate of 0.08 and 0.04，node average energy efficiency of 17.9%and 13.4%，resPective1y.So it achieves better resu1ts in imProving the success rate of data transfer and saving energy.

mobi1e ad hoc network；Partic1e fi1tering；wa1king 1ength Prediction；Levy Wa1k mobi1ity mode1；adaPtive routing a1gorithm **

TN915

A

1001-893X(2016)03-0331-06

10.3969/j.issn.1001-893x.2016.03.017

2015-06-22;

2015-10-13 Received date:2015-06-22;Revised date:2015-10-13通信作者:zhang1ing-n@bitc.edu.cn Corresponding author:zhang1ing-n@bitc.edu.cn