张文柱 赵贝

(西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安710071)

容迟网络(DTN)是一种新型无线网络体系结构［1］．它泛指无线网络节点间链路频繁中断、传输延迟巨大、可靠通信与端到端连接不能保证的一类网络，包括星际网络﹑战争网络﹑移动Ad hoc网络(MANET)和无线传感网络等．为DTN网络提供一定质量的网络服务，已经成为国内外研究的重点．

DTN网络的路由问题，以容迟、容断为前提，以链路状态及网络拓扑描述为基础，以路由决策为核心，实现分组高效转发，达到提高网络吞吐量的目标［2］．为此，人们提出了多种基于泛洪和委托转发思想的路由算法．文献［3］中利用传染泛洪算法有效地解决了链路通断导致的拓扑变化问题;文献［2，4］中分别以链路的平均延迟和预测延迟为网络量度来描述网络拓扑，引导单一分组转发;文献［5］中提出了一种基于概率和新鲜度的梯度路由算法，以避免网络资源的浪费;文献［6］中用多分量来描述网络环境，可反映网络拓扑的变化，通过加权综合各分量得到传输成功概率，并将其作为分组转发的依据．但这些算法存在占用大量网络资源、网络拓扑描述单一且不够精确﹑多分量网络描述下的综合算法不具有智能性、分组转发策略效率低等缺点．

为此，文中提出了基于梯度和模糊神经网络决策的容迟网络路由算法(RBGFNN)．首先，采用节点信息及节点间链路状态信息来描述网络，以改进网络描述向量［7-8］;接着，采用有限历史信息的动态平均结合精确预测的方式来自适应维护网络描述向量的各分量，以提供更准确的网络量度;然后，采用具有丰富的逻辑规则库和强化学习能力的模糊径向基函数(RBF)神经网络进行路由决策，以实现路由决策过程的智能化;最后，以节点间多跳传输成功概率为依据引导分组沿梯度方向转发，以提高分组转发效率，进而实现提高全网整体吞吐量．

1 网络状态模式识别算法

DTN是一个包含多种传统网络形态的综合概念，单纯一种路由算法很难有效解决网络在所有状态下的路由问题．因此，应该在网络状态模式识别的基础上选择使用不同的路由算法．

文中采用模糊逻辑对网络状态进行识别．定义两个逻辑输入:(1)δ=/d，δ反映网络内各链路状态变化的方差，v为节点运动速度，d为节点间距离;(2)各链路连接的平均时长反映了网络内各链路状态的平均值．定义模糊规则如表1所示．以预测性能极强及预测性极差的典型网络(如MANET和低轨通信)的δ/为标准点，将逻辑输入划分 L、M、H模糊类，如图1所示．将DTN网络分为3种可识别网络状态模式:频繁移动预测性能极差(ER)﹑移动规律预测性能极强(PR)﹑运动复杂预测性能适中(UR)．根据识别结果，ER模式应采用泛洪类算法，PR模式应采用预测性算法，而文中算法适用于UR模式，如图2所示．

表1 模糊逻辑规则Table 1 Fuzzy logic rules

图1 模糊类的划分Fig．1 Division of fuzzy class

图2 网络状态模式Fig．2 Model of network status

2 描述网络状态变化的多维向量

在DTN中，链路常常处于断开状态，并且链路状态经常变化．单一的网络状态参数(如链路通断、延迟大小、队列长短等)不能精确描述DTN的状态．为全面描述DTN的拓扑，为路由决策提供精确的量度，应该使用新的网络描述方法．在机会网络思想［6］的基础上，文中将DTN看成一个全连通网络，利用一个能反映节点及链路整体特性的多维向量来描述各节点间的连通特性，并构建一个虚拟拓扑．该拓扑能有效反映各链路变化中的整体统计特性和应对在动态网络中路由决策的需求．文中假设各节点具有电量感知能力并能提供相应参数采集．

2．1 各分量的设计

存储分量为RB=Brem/Btotal，其中Brem为剩余存储空间，Btotal为总存储空间．将能够反映全网分组生存性的节点存储空间作为描述网络拓扑的分量之一，可有效解决繁忙的优秀节点因存储空间溢出而出现网络分组生存性下降的问题．

电量分量为RP=Prem/Ptotal，其中Prem为剩余电量，Ptotal为总电量．为避免网络中那些具有优异的委托转发性能的节点因过度繁忙而携带着大量待转发分组“死亡”，电量也是一项有效描述网络、保证网络整体性能的重要分量．

时延分量为RD=(Dmax－Dreal)/Dmax，其中Dreal为传输的实际时延，Dmax为节点通信范围内的最大传输时延．当链路处于断开时，Dreal=Dmax，RD=0．该时延分量是为路由过程提供高效转发的重要依据．在其它因素被弱化时，该分量反映的可信链路代价，将引导分组沿着代价最小、成功概率最大的方向高效转发．

距离分量为RL=(Lmax－Lreal)/Lmax，其中 Lreal为节点间实际距离，Lmax为网络中节点的最大距离．节点通过自身的全球定位系统(GPS)等传感器得到的数据推导出该分量，对应网络中预设的地理信息，得到其与目的节点的距离参数［9］．文中假设不考虑通信中障碍物的影响，距离越近的节点通信成功概率越大．因此，在没有足够的时延信息情况下，距离分量用于将分组转发给离目的节点更近的委托节点，以实现沿成功概率梯度方向转发．

2．2 各分量的平均预测处理

上述各分量的采集均源自网络的动态历史信息．为得到能应对网络拓扑变化的未来信息，文中提出了一种能够动态地将有限的历史信息进行平均处理与精确预测结果相结合的措施，以此来平衡预测的不可靠性和平均处理的不精确性问题．

首先对有限的历史信息进行加窗平均处理，再对历史信息进行卡尔曼预测处理．为能反映现有数据的可预测性，定义一个结合系数

式中:cov(xi(t)，xi(t+k))为分量xi(t)相差k时刻的协方差，k为采集信息间隔;var(xi(t))为参量xi(t)的方差．最后将历史平均信息与预测结果相结合，得到

完成以上工作后，多维向量已经能够全面描述DTN的动态拓扑，该拓扑表征了DTN中决定路由成功的各个因素，并能够反映网络的动态特性．

3 基于梯度和模糊神经网络的路由决策

为获得反映网络连通特性的节点间单跳传输成功概率，文中采用5层模糊RBF神经网络结合Q学习算法［10］对多维向量进行综合处理，获得各分量的优先顺序以及在决策过程中所产生的影响．然后，节点通过迭代得到自身到达网络中其它节点的多跳传输成功概率，并以此为节点间分组委托转发的判定门限，引导分组沿梯度方向转发，实现更加高效的转发策略．

文中所提算法由网络描述和路由决策两部分组成，如图3所示．

图3 RBGFNN功能框图Fig．3 Functional diagram of RBGFNN

3．1 单跳传输成功概率

首先，构建5层模糊RBF神经网络［11］(如图4所示):

图4 模糊RBF神经网络Fig．4 Fuzzy RBF neural network

(1)第1 层为输入层，第 i(i=1，2，3，4)个节点代表第i个分量x'i的清晰值．

(2)第2层为隶属度函数层，该层的每个节点对应某一分量的某一模糊类．节点的输入为某分量的清晰值，输出为清晰值在相应模糊类中的隶属度．每个模糊类的隶属度函数为可微的高斯函数，即其中 mij和 σij分别为第 i个分量xi的第j个模糊类对应的隶属度函数的中心和宽度．

(3)第3层为适应度计算层，该层的每个节点对应一条逻辑规则，节点的输入为规则的前件，输出为各逻辑前件隶属度确定条件下规则逻辑输出的适应度，即

(4)第4层为规则内部离散概率竞争层，该层节点对应每条逻辑规则的后件．节点根据规则所对应的输出模糊类的评价Q值分布，竞争得到规则局部最优概率，如pr=max()，表示第r条规则所对应Q值最大的概率，n为输出模糊类中各清晰概率点的序号．

将各分量的清晰输入定义为模糊类(如图5所示);然后为整个综合过程设计逻辑规则库［12］(如表2所示)，将输出的概率值划分为离散模糊类，并初始化其Q值，如图6所示．

图5 各分量的离散模糊类Fig．5 Discrete fuzzy classes of each component

表2 逻辑规则库Table 2 Database of logic rule

图6 输出的概率值与离散模糊类Fig．6 Output probability values and discrete fuzzy classes

3．2 参数学习

函数．定义TD误差为

式中:γ为折扣因子，0≤γ≤1;Rt+1为状态与输出的强化信号函数，Rt+1=RD(t+1)－RD(t)，即t+1与t时刻的时延分量差．

根据TD误差，利用直接梯度下降算法来调整逻辑后件中离散概率对应的Q值

式中，βm与βσ分别为隶属度函数的中心与宽度的学习率．

3．3 基于多跳传输成功概率的转发策略

每个节点拥有自身到达网络内其它节点的单跳传输成功概率后，就可以通过交换各自的网络连通信息来得到以单跳传输成功概率描述的全连通网络拓扑图．

当有节点进入一个参考节点的通信范围内时，参考节点首先判断对方是否为待发分组的目的节点，如果是则直接发送该分组，否则比较自身及对方到达待发分组的目的节点的多跳传输成功概率．如果自身值大于对方值，则参考点不发送该分组;如果对方值大于自身值，则参考点委托该节点转发该分组．按此转发策略引导分组转发到目的节点．

4 仿真与结果分析

为评估文中算法的性能，采用网络仿真软件OPNET对文中算法﹑Epidemic算法及典型梯度路由(CAR)算法进行仿真，并对其分组递交率及转发分组数进行了比较．

首先建立一个边长为3km的正方形仿真平面，并划分出9个直径为100 m的虚拟区域，每个区域内初始化20个DTN节点(其中19个节点以1～2m/s的速度随机移动，1个节点固定在区域的中心)．另外，10个节点以仿真平面中心为圆心，以等间距的半径做5～10 m/s的同心圆运动．节点通信范围为50m，信息传输速率为250 kB/s，分组大小为10～100kB．

在各分量维护中，信息采集间隔k=1 s;Q学习算法的学习率β=0．8，折扣率γ=0．9，TD误差0=0．1;多跳成功概率迭代中，p0i=1．

然后，考察在节点电量不受限制、存储空间受限情况下的网络性能，仿真结果如图7所示．从图7可以看出，在这种情况下，转发缺乏目的性的Epidemic算法性能受到严重的影响，递交率低于CAR和RBGFNN算法，而后两种梯度路由算法均表现出稳定的性能;RBGFNN算法保持了经典梯度路由算法的特点，在低转发分组数下保证较稳定的分组递交率，性能优于CAR算法．

图7 存储空间受限时的分组递交率和节点转发分组数Fig．7 Packet delivery ratio and forwarding packet number of node in limited storage space

接着考察节点存储空间固定为60 MB、节点电量是确定有限值情况下的网络性能，仿真结果如图8所示．从图8可以看出，在这种相对复杂的网络条件下，随着分组生存时间的变化，各算法的分组递交率都有所升高;由于RBGFNN算法改进了CAR算法的网络描述和路由决策方式，因而转发更精确，获得了接近Epidemic算法的递交率，还保持着与CAR算法几乎相同水平的转发分组数．这说明RBGFNN算法在继承传统梯度路由算法优点的情况下，还明显提高了其分组递交率．

图8 复杂网络条件下的分组递交率和节点转发分组数Fig．8 Packet delivery ratio and forwarding packet number of node in complex network

最后，考察节点存储空间固定为10 MB、电量为前一场景确定有限值的50%﹑分组生存时间为2 h且业务量较重情况下的网络性能，仿真结果如图9所示．在这种更为苛刻的网络条件下，随着业务量的增加，各算法的分组递交率急剧下降，分组平均延迟明显增加，但RBGFNN算法有效避免了分组的盲目转发，及时更新了在资源受限情况下的路由决策原则，因而提高了分组的生存性，获得了较其它两种算法更高的分组递交率和更低的分组延迟．

综上所述，文中提出的RBGFNN算法采用了CAR算法的基本框架，因此保持了分组转发的低代价、高效率特性．同时，RBGFNN算法以预测与平均相结合的方式来维护网络拓扑的描述分量，提高了网络模型的精确度;以模糊神经网络对各分量进行动态智能综合决策，提高了路由决策的灵活度;因而，RBGFNN算法的网络性能优于CAR算法．

图9 苛刻网络条件下的分组递交率和分组平均时延Fig．9 Packet delivery ratio and average delay in bad network

5 结语

文中提出了基于梯度和模糊神经网络决策的容迟网络路由算法RBGFNN．该算法使用历史信息的动态平均与精确预测相结合的多维向量来描述网络拓扑的动态变化;采用智能的模糊神经网络来实现路由决策的智能化;依据多跳传输成功概率引导分组沿梯度方向转发以提高分组转发的效率．该算法能够适应DTN的拓扑变化，具有强化学习功能，可实现对DTN中分组的高效低代价转发，获得了良好的网络性能．

［1］ Cerf V，Burleigh V，Hooke A，et al．Delay-tolerant networking architecture［R/OL］．(2007-04-30)［2010-09-10］．http:∥www．rfc-editor．org/rfc/rfc4838．txt．

［2］ Jones Evan P C，Li Lily，Schmidtke Jakub K，et al．Practical routing in delay-tolerant networks［J］．IEEE Transactions on Mobile Computing，2007，6(8):943-959．

［3］ Lu Xiaofeng，Hui Pan．An energy-efficient n-epidemic routing protocol for delay tolerant networks［C］∥Proceedings of the 5th IEEE International Conference on Networking，Architecture，and Storage．Macau:IEEE，2010:341-347．

［4］ Yuan Q，Cardei I，Wu J．An effiicient prediction-based routing in disruption-tolerant networks［J］．IEEE Transactions on Parallel and Distributed Systems，2012，23(1):19-31．

［5］ 段鹏瑞，马华东，罗红．基于梯度的 DTN路由算法［J］．北京邮电大学学报，2011，34(2):63-66．Duan Peng-rui，Ma Hua-dong，Luo Hong．A gradient based routing algorithm for delay tolerant networks［J］．Journal of Beijing University of Posts and Telecommunications，2011，34(2):63-66．

［6］ Huang T K，Lee C K，Chen L J．PRoPHET+:an adaptive PRoPHET-based routing protocol for opportunistic network［C］∥Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications．Perth:IEEE，2010:112-119．

［7］ Musolesi M，Hailes S，Mascolo C．Adaptive routing for intermittently connected mobile ad hoc networks［C］∥Proceedings of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks．Taormina:IEEE，2005:183-189．

［8］ Poor D．Gradient routing in ad hoc networks［R/OL］．(2000-12-31)［2011-02-28］．http:∥www．media．mit．edu/pia/Research/ESP/texts/poorieeepaper．pdf．

［9］ Yasmeen F，Urushidani S，Yamada S．A probabilistic position-based routing scheme for delay-tolerant networks［C］∥Proceedings of the 12th International Conference on Computers and Information Technology．Dhaka:IEEE，2009:88-93．

［10］ 张吉礼．模糊－神经网络控制原理与工程应用［M］．哈尔滨:哈尔滨工业大学出版社，2004:24-59．

［11］ Fan Yuan-yuan，Sang Ying-jun．The research of nonlinear control based on fuzzy neural network［C］∥Proceedings of International Conference on Electrical and Control Engineering．Wuhan:IEEE，2010:2417-2420．

［12］ Zuo J，Ng S X，Hanzo L．Fuzzy logic aided dynamic source routing in cross-layer operation assisted ad hoc networks［C］∥Proceedings of IEEE the 72nd Vehicular Technology Conference Fall．Ottawa:IEEE，2010:1-5．