OCIGM:面向DTN路由的优化控制信息生成方法
王贺哲, 王慧强, 朱金美, 冯光升, 吕宏武     
哈尔滨工程大学 计算机科学与技术学院, 哈尔滨 150001
摘要

在延迟容忍网络(DTN)中,现有路由算法大多仅考虑网络的局部资源状况进行中继节点的选择,无法使全局网络性能达到最优或次优。对此,提出面向DTN路由的优化控制信息生成方法(OCIGM)。该方法能评估不确定的全局网络状态,进而生成对DTN路由的优化控制信息。移动终端根据优化控制信息通过限制消息的副本数调整路由策略。仿真结果表明,喷雾等待路由算法在OCIGM优化控制信息生成方法的作用下,其网络开销、消息丢包率有所降低,消息转发成功率有所提高。

关键词: 延迟容忍网络     路由协议     优化控制    
中图分类号:TN911.22 文献标志码:A 文章编号:1007-5321(2017)01-0079-05 DOI:10.13190/j.jbupt.2017.01.014
OCIGM:an Optimized Control Information Generation Method for DTN Routing
WANG He-zhe, WANG Hui-qiang, ZHU Jin-mei, FENG Guang-sheng, LÜ Hong-wu     
College of Computer Science and Technology, University of Harbin Engineering, Harbin 150001, China
Abstract

In delay tolerant network (DTN), most of the existing routing algorithms only consider the local resource status of the network to select the relay nodes, which can not make the global network performance optimal or sub-optimal. According to this problem, an optimal control information generation method (OCIGM) for DTN routing was proposed. The method can evaluate the global network state and generate the optimized control information for the DTN routing. The mobile terminal adjusts the routing policy by limiting the number of replicas of the message according to the optimization control information. Simulations show that the spray and wait (SAW) routing algorithm reduces the network overhead and packet loss ratio under the OCIGM optimal control information generation method. Meanwhile, the delivery ratio of message is improved.

Key words: delay tolerant network     routing protocol     optimized control    

对于传统网络的体系结构,如Internet体系结构、移动自组织网络等主要是解决传输时延小、错误率低、节点间存在链路等问题[1].但在灾难场景、偏远地区等网络环境下,这些传统的体系结构将不再适用,延迟容忍网络 (DTN,delay tolerant network)[2-3]的出现很好地解决了上述问题. DTN是一种新型网络,不同于传统网络,具有高延迟、高错误率、低传输率、可能不存在端到端的连接通路等特性[4-5].合理的DTN路由策略能利用DTN中有限的资源,根据一定的转发策略进行消息转发.但是,目前的DTN路由策略还存在很多不足,仅考虑网络的局部资源状况进行中继节点的选择,导致路由策略的传输性能具有很大局限.因此,笔者提出面向DTN路由的优化控制信息生成方法,对全局网络状态进行评估,进而生成DTN路由策略的优化控制信息,从而解决DTN路由策略仅仅考虑局部节点资源的问题.

1 相关工作

优化控制技术是通过相关算法实现相应的优化,使相关算法能在尽可能少的人为干预下智能化地实现对目标的自动控制[6].在优化控制技术方面,已有大量相关研究.目前已有的优化控制技术主要是针对网络资源分配等,而在网络的路由优化控制相对较少.黎峰等[7]为解决由机会网络拓扑时变性带来的最优路径较难选择的问题,提出了一种优化的机会网络高效路由算法.该路由算法主要是利用粒子协同识别方法,计算出机会网络中的最优移动节点方向.张礼莉等[8]提出了一种机会网络中高效可靠混合路由优化算法,利用生存时间 (TTL,time to live) 值自适应调整机制和跨层感知机制解决机会网络混合路由算法 (CAR,context-aware routing) 的网络控制开销较大、消息转发成功率较低等问题.

目前,针对网络优化控制机制的研究相对较少,尤其是针对DTN中路由优化控制机制的相关研究更为少见.但是,DTN的间歇性连接、链路时断时续、拓扑时变性等网络特性使路由策略选择中继节点时具有很大的局限性.路由策略仅能根据局部网络资源进行中继节点选择,只能做到中继节点选择的局部最优,而无法使全局网络性能最优或次优.在资源受限 (资源不足、资源分布不均衡) 的DTN中,这种局限性问题愈发明显.因此,笔者提出了面向DTN路由策略的优化控制信息生成方法 (OCIGM,optimal control information generation method).

2 OCIGM优化控制信息生成方法 2.1 OCIGM的作用

OCIGM的作用是生成对移动终端的路由策略的优化控制信息.根据优化控制信息,移动终端中的路由策略通过限制消息的副本数进行路由策略的调整.根据优化控制信息的不同类型,限制副本数的情况分为以下3种.

假设接收到该次优化控制信息之前和之后消息的副本数分别为ncnCA,不确定性的全局网络状态 (NS,network status) 为{消息转发成功率mDe,网络开销mO,网络丢包率mDr}.

情况1  优化控制信息是提高消息转发成功率

消息转发成功率是成功交付的消息数与网络中产生的消息数的比值,因此当移动终端接收到的优化控制信息是提高消息转发成功率时,可通过一定程度上增大消息副本数来提高消息交付成功的概率,利用式 (1) 进行副本数的控制.

${n_{{\rm{CA}}}} = \frac{{{\alpha _1}}}{{{m_{{\rm{De}}}}}}{n_{\rm{c}}}$ (1)

其中:α1为事先设定的阈值,且全局网络状态NS中消息转发成功率mDe < α1 < 1.

情况2  优化控制信息是降低网络开销

网络开销为中继消息总数和成功交付消息总数的差值与成功交付消息总数的比值.当降低网络中消息的副本数时,网络中继消息总数会随之下降,虽然成功交付消息总数也会随之下降,但是中继消息总数下降的幅度较大.因此,当移动终端接收到的优化控制信息是降低网络开销时,可通过降低消息副本数来降低网络开销,利用式 (2) 进行副本数的控制.

${n_{{\rm{CA}}}} = \frac{{{\alpha _2}}}{{{m_{\rm{O}}}}}{n_{\rm{c}}}$ (2)

其中:α2为事先设定的阈值,且全局网络状态NS中网络开销mO > α2.

情况3  优化控制信息是降低网络丢包率

网络丢包率是网络中丢弃消息总数与网络中产生消息数的比值.网络中各个节点丢弃消息的主要原因是节点的缓存有限、可存储携带的消息数有限.因此,当节点收到的优化控制信息是降低网络丢包率时,可通过降低消息副本数降低网络的丢包率,利用式 (3) 进行副本数的控制.

${n_{{\rm{CA}}}} = \frac{{{\alpha _3}}}{{{m_{{\rm{Dr}}}}}}{n_{\rm{c}}}$ (3)

其中:α3为事先设定的阈值,且全局网络状态NS中网络丢包率mDr > α3.

2.2 OCIGM的主要思想

OCIGM充分利用混合拓扑下的弱反馈性质.所谓弱反馈是指移动节点可以通过弱连接 (直接链路和机会链路组成的混合链路) 的方式将消息交付情况发送至控制中心,控制中心却无法和网络中所有节点直接取得联系,更无从获知所有移动节点的当前状态.在这种情况下,控制中心可根据消息交付情况来评估全局网络状态,从而产生相应的优化控制信息.然后通过单向链路 (如卫星链路) 向网络中各个移动节点发送优化控制信息.受移动节点自身发送功率的限制,上行卫星链路对其并不适用.

网络拓扑结构主要包括控制中心、卫星、移动终端,且移动终端具有位置感知能力.

控制中心的主要功能是根据移动终端通过机会链路发送来的消息交付情况mS{消息成功交付数、消息交付开销、丢弃消息数},并每隔时间t1根据移动终端mt1至mtN发送来的消息交付情况评估不确定性的全局网络状态 (NS),有

${m_{{\rm{De}}}} = \sum\limits_1^N {\frac{{{n_{{\rm{De}}}}}}{N}} $ (4)
${m_{\rm{O}}} = \sum\limits_1^N {\frac{{{o_{\rm{D}}}}}{N}} $ (5)
${m_{{\rm{Dr}}}} = \sum\limits_1^N {\frac{{{n_{{\rm{Dr}}}}}}{N}} $ (6)

其中:nDe为消息成功交付数,oD为消息交付开销,nDr为丢弃消息数.

如果没有移动终端向控制中心发送mS,控制中心将向移动终端发送自行控制命令.然后根据不确定性的全部网络状态生成优化控制信息{提高消息转发成功率、降低网络开销、降低网络丢包率},并将其交付至卫星,利用卫星的直接链路将优化控制信息发送至各个移动终端.

卫星的主要功能是提供控制中心和移动终端之间的直接链路,将控制中心的消息发送至各个移动终端.卫星接收控制中心的优化控制信息,通过直接链路传送至各个移动终端.

移动终端首先通过机会链路以时间t2为周期定期向控制中心发送该移动终端在t2周期内的消息交付情况mS,并接收卫星传输的优化控制信息.移动终端根据优化控制信息,以优化全局网络效用为目标进行路由策略的调整.其中全局网络效用被定义为

$ {m_{{\rm{De}}}}/{\alpha _1}/\left( {{m_0}/{\alpha _2} + {m_{{\rm{Dr}}}}/{\alpha _3}} \right) $

注意:OCIGM方法设置每隔t1时间进行全局网络状态的评估,并设置每隔t2时间移动终端定期发送该移动终端的消息交付情况.因为面向的网络环境是具有弱反馈和资源受限的特性,所以提出的OCIGM方法是分布式的,为了节约资源且评估的准确度,设定评估周期t1和移动终端的发送周期t2.

2.3 OCIGM的流程

OCIGM方法根据控制中心所接收的全局网络状态NS,以优化全局网络效用为目标,独立地做出对DTN路由优化控制的决策,决策集P为{提高消息转发成功率pDe,降低网络开销pO,降低网络丢包率pDr}.在受限的DTN中,消息成功交付至目的节点是重中之重,因此OCIGM方法首先是观察全局网络状态NS中消息转发成功率mDe;其次,观察全局网络状态NS中网络开销mO;最后,观察全局网络状态NS中网络丢包率mDr.

OCIGM方法流程如下:

1) 移动终端通过机会链路向控制中心发送消息交付情况mS

2) 控制中心根据接收到的消息交付情况,评估不确定性的全局网络状态NS,如果控制中心未按时收到移动终端发送的新消息交付情况,则向移动终端发送自行控制命令;否则执行3);

3) 判断全局网络状态NS中消息转发成功率mDe是否大于α1(0 < α1 < 1,α1为事先设定的阈值),如果是,则执行4);否则,调度决策集P中的提高消息转发成功率pDe决策,执行6);

4) 判断全局网络状态NS中网络开销mO是否小于α2(α2 > 0,α2为事先设定的阈值),如果是,则执行5);否则,调度决策集P中的降低网络开销pO决策,执行7);

5) 判断全局网络状态NS中网络丢包率mDr是否小于α3(α3>0,α3为事先设定的阈值),如果是,则发送自行控制,并结束;否则,调度决策集P中的降低网络丢包率pDr决策,执行8);

6) 用式 (1) 对路由策略进行副本限制,结束;

7) 用式 (2) 对路由策略进行副本限制,结束;

8) 用式 (3) 对路由策略进行副本限制,结束.

3 仿真结果 3.1 仿真环境设置

笔者结合喷雾等待 (SAW,spray and wait) 路由协议,通过机会网络环境 (ONE,opportunistic network environment) 仿真器对OCIGM优化控制信息生成方法进行实验仿真.仿真中节点组共分4组:第1组节点模拟行人;第2组节点模拟电车;第3组和第4组共投放2个固定节点模拟控制中心及卫星.仿真参数设置如表 1所示.仿真时,1组、2组产生消息交付情况时间间隔为1 000 s,交付情况生命周期为1 000 s,初始设置α1=0.5,α2=3,α3=2.

表 1 OCIGM的仿真参数

利用以下性能参数评价OCIGM生成的优化控制信息对喷雾等待路由SAW的作用:

$ 消息转发成功率 = \frac{{成功递交给目的节点的消息个数}}{{生成的消息总数}} $

网络开销=(网络中被中继的消息数量-成功递交的消息数量)/成功递交的消息数量

网络丢包率=丢弃数据包的数量/生成的消息总数

3.2 实验结果分析

1) 消息产生间隔变化对优化控制信息生成方法OCIGM的影响

设置初始副本数为100,改变网络中消息产生间隔进行实验仿真.将消息产生间隔从8 s增加至30 s,对比有无优化控制信息生成方法OCIGM对喷雾等待路由SAW路由策略的性能影响.

图 1~图 3所示分别为消息产生间隔变化对消息转发成功率、网络开销、网络丢包率的影响.从图 1可以看出,随着消息产生间隔的不断增大,SAW和SAW-OCIGM的消息转发成功率首先是先增大后减小,当消息产生间隔为25 s时,两者的消息转发成功率达到最大.从图 2可以看出,随着消息产生间隔的不断增大,SAW和SAW-OCIGM的网络开销有所增加.从图 3可以看出,随着消息产生间隔的不断增大,SAW和SAW-OCIGM的网络丢包率呈波浪型变化. 图 1~图 3表明,受OCIGM优化控制信息生成方法作用的SAW路由策略性能明显高于不受OCIGM作用的SAW路由策略.其中,消息转发成功率提高了1.2%,网络开销降低了4.07%,网络丢包率降低了1.8%.

图 1 消息转发成功率

图 2 网络开销

图 3 网络丢包率

2) 节点数变化对优化控制信息生成方法OCIGM的影响

为了进一步验证OCIGM优化控制信息生成方法的有效性,将α1设置为0.6,α2设置为3,α3设置为2,初始副本数设置为100,消息产生间隔设置为25 s.改变Group1中的节点数,即改变节点密度进行实验.将网络中组1的节点数从5逐渐增加为11,网络性能的变化如图 4~图 6所示,显示出了节点个数变化对消息转发成功率、网络开销、网络丢包率的影响.

图 4 消息转发成功率

图 5 网络开销

图 6 网络丢包率

通过图 4发现,当节点数为8时,消息转发成功率最高,且SAW-OCIGM的消息转发成功率高于不受OCIGM作用的SAW路由策略.从图 5图 6可见,受OCIGM方法控制的SAW网络开销和丢包率低于不受OCIGM作用的SAW路由策略.相比于传统的SAW,受OCIGM控制的SAW将消息转发成功率提高了0.34%,将网络开销降低了4.2%,将网络丢包率降低了3.9%.

4 结束语

针对目前DTN中的路由策略仅考虑局部资源,不对全局网络状态作相应考虑,只能做到局部网络性能最优,而无法使得全局网络性能最优或者次优的问题,提出了面向DTN路由的OCIGM. OCIGM可对全局网络状态进行评估,生成DTN路由策略的优化控制信息,移动终端根据优化控制信息调整各自的路由策略,从而解决DTN路由策略仅考虑局部节点资源的问题.通过仿真实验发现,就消息转发成功率、网络开销、消息丢包率而言,SAW路由策略在OCIGM优化控制信息生成方法的作用下所表现出的性能要优于SAW路由策略.

参考文献
[1] 马华东, 袁培燕, 赵东. 移动机会网络路由问题研究进展[J]. 软件学报, 2015, 26(3): 600–616.
Ma Huadong, Yuan Peiyan, Zhao Dong. Research progress on routing problem in mobile opportunistic networks[J]. Journal of Software, 2015, 26(3): 600–616.
[2] Mao Yuxin, Zhu Ping. A game theoretical model for energy-aware DTN routing in Manets with nodes' selfishness[J]. Mobile Networks and Applications, 2015, 20(5): 593–603. doi: 10.1007/s11036-015-0610-7
[3] Li Yong, Hui Pan, Jin Depeng, et al. Delay-tolerant network protocol testing and evaluation[J]. IEEE Communications Magazine, 2015, 53(1): 258–266. doi: 10.1109/MCOM.2015.7010543
[4] Silva A P, Hirata C M, Burleigh S, et al. A survey on congestion control for delay and disruption tolerant networks[J]. Ad Hoc Networks, 2015, 25(PB): 480–494.
[5] Iranmanesh S. A novel queue management policy for delay-tolerant networks[J]. EURASIP Journal on Wireless Communications and Networking, 2016, 2016(1): 1–23. doi: 10.1186/s13638-015-0498-8
[6] 辛斌, 陈杰, 彭志红. 智能优化控制:概述与展望[J]. 自动化学报, 2013, 39(11): 1831–1848.
Xin Bin, Chen Jie, Peng Zhihong. Intelligent optimized control:overview and prospect[J]. Acta Automatica Sinica, 2013, 39(11): 1831–1848.
[7] 黎峰, 周丹. 一种优化的机会网络高效路由算法仿真分析[J]. 计算机仿真, 2013, 30(10): 318–321.
Li Feng, Zhou Dan. Simulation and analysis of optimized network efficient routing algorithm[J]. Computer Simulation, 2013, 30(10): 318–321. doi: 10.3969/j.issn.1006-9348.2013.10.072
[8] 张礼莉, 汪栋. 机会网络中高效可靠混合路由优化算法[J]. 现代计算机:专业版, 2014, 10(6): 17–24.
Zhang Lili, Wang Dong. Effective and reliable hybrid routing optimization algorithm in opportunistic networks[J]. Modern Computer:Professional Edition, 2014, 10(6): 17–24.