基于最大最小蚂蚁系统的容迟网络缓存机制

彭牧尧,魏建军,王乾舟,王 琨

(1.西安电子科技大学 通信工程学院,陕西 西安 710071;2.西安电子科技大学 杭州研究院,浙江 杭州 311231;3.西安电子科技大学 计算机科学与技术学院,陕西 西安 710071)

0 引言

难以估计的链接范围与成本巨大的硬件覆盖导致了容迟网络(Delay Tolerant Network, DTN)的出现。容迟网络具有网络资源有限、难以维持端到端的长时间稳定链接以及网络拓扑动态变化的特征,广泛存在于智慧城市网络[1]、深空通信网络[2-4]和野生动物追踪网络[5]等实际应用中。容迟网络的特性使得在该网络中信息的传递难以依赖传统的TCP/IP协议。为了进行消息的传递与交互,容迟网络通过“存储-携带-转发”的方式,在存储待传递消息的节点与目的节点相遇时进行消息传递。这种消息传递方式需要节点进行消息存储,从而导致网络中存在同一消息的多个副本,消息副本的增多将导致网络开销的增长,需设计合理的缓存管理方法,以进行消息副本的存储丢弃管理。

本文考虑信息的不同类别,提出了一种基于最大最小蚂蚁系统的容迟网络缓存机制(Cache Management Strategy Based on Max-Min Ant Colony System in Delay Tolerant Network)。基于消息的转发次数、消息大小与剩余生存时间等自身特征,定义不同类别信息的信息素浓度表达式。当节点缓存已满且有新的消息进入时,根据信息素浓度计算丢弃权重,并丢弃权重最小的消息。本算法考虑了消息自身的特征,并结合历史信息实现容迟网络中的缓存管理。

1 相关工作

1.1 容迟网络缓存机制

近年来,国内外有许多针对容迟网络缓存机制的研究。文献[6-7]阐述了现有的国内外容迟网络缓存机制,其中常用且具有代表性的机制包括:

① 先进先出(First In First Out,FIFO)或丢弃最先进入缓存中的消息(Drop Front,DF)算法。如果节点缓存已满且有新的消息到达,DF算法将丢弃最先进入缓存的消息。

② 随机丢弃(Drop Random,DR)算法。如果节点缓存已满且有新的消息到达,DR算法将随机丢弃缓存中的消息。

③ 丢弃最少生存时间消息(Drop Oldest,DO)算法。如果节点缓存已满且有新的消息到达,DO算法将丢弃缓存中剩余生存时间最小的消息。

对比以上的容迟网络缓存机制,DF和DO具有最好的效果,并且这两种容迟网络缓存机制被广泛应用于容迟网络中。

国内,崔苑茹等人[8]提出基于校园机会网络的协作小组缓存调度策略,结合校园协作学习背景,有效降低了消息的冗余程度并减少了由于缓存空间不足而出现的消息传输失败等问题。通过实验表明,该算法具有较优的网络指标。郑啸等人[9]提出了一个新的度量节点在协作缓存中重要程度的指标,即节点重要度。基于此指标,利用贪心算法选择初始缓存节点。同时,利用缓存节点相遇的机会,进行缓存数据的主动再分配,并且通过实验验证了提出的缓存协议能够有效提高数据访问效率。Zhang等人[10]基于分布式存储的思想提出了一种容迟网络缓存机制,当节点存在缓存压力时,将利用其可通信节点来存放接收的消息,仿真证明该算法可以有效增加消息到达率和缓存利用率。

国外,基于广义概率转发模型和拥塞指标,Goudar等人[11]通过预测网络中的拥塞点,自适应地调整节点的消息复制率,减少了不必要的缓存,防止数据包丢失;通过显示的数学公式对相遇概率、传递概率等进行了表述。Nănău等人[12]提出了一种名为“MaxDelivery”的方法,该方法有效释放了节点中的缓存,但是该方法引入了ACK确认机制,将导致网络中产生额外的ACK消息,使得网络开销增加。以上两种方法为了获得网络中更加多样化信息用于决策消息的丢弃,需要节点间交互额外的信息,这将导致网络开销的增加。文献[13]提出了一种基于多社区模型的资源优化协议,即社交相似度和优化资源(Social Similarity And Optimized Resource,SSAOR)协议,以有效利用容迟网络中的资源。该协议基于源节点和目标节点之间的位置关系,使用两种不同的策略来确定转发消息的顺序。

1.2 蚁群算法

蚁群算法的提出,为解决组合优化问题提供了新的思路,并且被逐渐应用到其他的优化问题中。但蚁群算法存在易陷入局部最优的问题,成为现有国内外学者研究的重点。

Akande等人[14]将蝠群算法与蚁群算法相结合,并通过仿真证明融合算法效果好于单一算法。但融合算法仍然存在陷入局部最优的问题。Ye等人[15]对蚁群算法的负反馈机制进行了改进,利用其提高解的多样性。同时,根据历史搜索信息,不断获取故障经验,解决了蚁群算法容易陷入局部最优的问题。李宪强等人[16]把蚁群算法应用于解决无人机三维路径规划问题,将蚁群算法与人工势场算法相结合,有效解决了蚁群算法易陷入局部最优和容易忽视节点周围障碍物的问题。Ding等人[17]将Q-learning算法引入蚁群算法当中,通过添加量子位启发因子避免蚁群算法陷入局部最优当中,提高了算法的优化能力和收敛速度;然而该算法仍然存在实际应用的挑战和问题。赵晶蕊等人[18]基于蚁群算法实现了负载均衡下的 QoS 保障路由算法。仿真结果表明,该算法能够有效实现网络负载的均衡,且同时在端到端时延、丢包率、剩余带宽等 QoS 需求的性能上有明显提升。

Stutzle[19]利用最大最小蚂蚁系统解决二次规划问题,并且取得了不错的效果。最大最小蚁群算法相较于蚁群算法有如下的改进:

① 最大最小蚂蚁系统规定了信息素浓度的上下界,设定最小信息素浓度有助于增加对更优解探索的可能性,设定最大信息素浓度保证经验对于蚁群的启发性。

② 信息素浓度初始值为信息素取值区间的上限,并伴随一个较小的信息素衰减系数。

③ 只允许迭代最优蚂蚁,或者至今最优蚂蚁释放信息素。

最大最小蚂蚁系统可以有效地减少蚁群算法局部收敛的问题,得到了广泛的应用。

通过查阅文献,有以下三点发现:

① 基于多效用值考虑的缓存管理机制有助于提升容迟网络性能。

② 蚁群算法在解决优化问题上有着优异的表现,可以很好地应用于容迟网络性能优化问题,但需要考虑其易陷入局部最优的问题。

③ 现有容迟网络缓存机制及蚁群算法少有考虑消息的类别。将消息分类引入容迟网络缓存机制,有助于将同类消息集中于特定的节点之上,便于为之分配特定资源,提升网络性能。

基于以上发现,本文将最大最小蚂蚁系统应用于容迟网络缓存机制当中,节点综合考量单条信息的信息素浓度与节点上同类信息的信息素浓度,自主地依照所求权重丢弃相应的消息,提高网络整体消息到达率并减少网络开销。

2 算法介绍

2.1 蚁群信息素浓度定义

本节定义了消息信息素浓度、同类消息信息素浓度以及丢弃权重的表达式。蚁群信息素浓度依赖于消息的相关特征,特征如下:

① 剩余生存时间(Time Till Lifetime,TTL)。剩余生存时间反映了消息在网络中可能继续被转发的概率。一般地,剩余生存时间越短,消息越难以被交付到目标节点。

② 缓存占用率(Cache Usage)。本机制定义缓存占用率为消息的大小与所到达节点缓存大小的比值,如式(1)所示。对于消息而言,缓存占用率越大,会使得消息所到达的节点更容易产生拥塞并丢弃缓存中原有消息,从而导致网络消息到达率下降。

(1)

式中:Cache_Usagei,j表示消息i在节点j的消息占用率,Sizei表示消息i的大小,Node_Cachej表示节点j的缓存大小。

③ 消息的转发次数。在本机制中,消息的转发次数被定义为消息经过的跳数。如果消息的转发次数越高,该消息在网络中则会具有更多的副本数。丢弃副本数较多的消息,对网络整体的消息到达率影响较小。

本机制认为单条消息的信息素浓度取决于上述三种特征。因此,使用式(2)定义单条消息的信息素浓度(Pheromone Concentration of Message,PCM):

(2)

式中:PCMt,i,j表示t时刻进入节点j的第i条消息的信息素浓度,TTLt,i表示t时刻进入节点j的第i条消息的剩余生存时间,Hopst,i表示t时刻进入节点j的第i条消息的转发次数。

如式(3)所示,本机制认为节点在t时刻的同类消息信息素浓度(Pheromone Concentration of the Same Category,PCSC)取决于t-1时刻的衰减后同类消息信息素浓度,与t时刻进入节点的同一类别的N条消息的信息素浓度。

(3)

式中:ρ表示历史信息素浓度的衰减系数,N表示t时刻进入节点的同一类别消息的数量,τmin表示信息素浓度范围的下限,τmax表示信息素浓度范围的上限。

如式(4)所示,总信息素浓度(Total Pheromone Concentration),即丢弃权重,决定了消息丢弃的优先级。丢弃权重越低的消息越容易被丢弃。

Weightt,i=PCMt,i,j+PCSCt-1,

(4)

式中:Weightt,i表示t时刻第i条消息的丢弃权重。

2.2 基于蚁群算法的容迟网络缓存机制

本节提出的缓存机制引入蚁群算法,机制有效考虑了信息的分类。节点维护不同类别信息的信息素浓度值。缓存机制流程如图1所示。缓存机制流程的具体步骤如下。

图1 基于蚁群算法的容迟网络图缓存机制流程示意图Fig.1 Flow diagram of delay tolerant network cache management strategy based on ant colony algorithm

步骤一:当有新消息到来时,会检查节点中的缓存是否已满。若缓存未满,则直接跳至步骤四;若缓存已满,则跳至步骤二。

步骤二:利用式(4)计算该条消息的丢弃权重,其中计算同类消息信息素浓度时不设定上下限。

步骤三:将步骤二中计算所得的丢弃权重与当前缓存中消息的丢弃权重进行比较,若新消息的权重为最小,则丢弃新消息;若不为最小,则丢弃缓存中原有消息中具有最小权重的消息并跳至步骤四。

步骤四:新消息进入缓存。

步骤五:利用式(3)更新缓存节点中的同类消息信息素浓度。

2.3 基于最大最小蚂蚁系统的容迟网络缓存机制

基于2.2节所提容迟网络缓存机制,将最大最小蚂蚁系统与缓存机制相结合,将节点上的同类信息素浓度限定在一定的范围内。基于最大最小蚂蚁系统的容迟网络缓存机制流程如图2所示。 缓存机制流程的具体步骤如下。

图2 基于最大最小蚂蚁系统的容迟网络缓存机制流程示意图Fig.2 Flow diagram of delay tolerant network cache management strategy based on max-min ant system

步骤一:按照消息的到达节点对消息进行分类。

步骤二:当有新消息到来时,步骤二会检查节点中的缓存是否已满。若缓存未满,则直接跳至步骤五;若缓存已满,则跳至步骤三。

步骤三:利用式(4)计算该条消息的丢弃权重。

步骤四:将步骤二中计算所得的丢弃权重与当前缓存中消息的丢弃权重进行比较,若新消息的权重为最小,则丢弃新消息;若不为最小,则丢弃缓存中原有消息中具有最小权重的消息并跳至步骤五。

步骤五:新消息进入缓存。

步骤六:利用式(3)更新缓存节点中的同类消息信息素浓度。当更新后的同类消息信息素浓度超出给定范围时,若超出上限,取给定信息素浓度范围的上限;若超出下限,取给定信息素浓度范围的下限。

3 仿真及分析

3.1 仿真环境

本文使用由赫尔辛基大学开发的ONE网络仿真平台进行仿真。仿真在4 500 m×3 400 m的区域内进行,持续7 200 s。网络中消息产生的间隔为25～35 s。实验中,将所有的节点分为4组,其中,A组和B组节点代表步行或奔跑的行人,其移动速度为 1～5 m/s;C组节点代表电动车或自行车,移动速度为 5～7 m/s;D组为有轨电车,移动速度为 7～10 m/s,拥有高速通信接口。具体参数设置如表1所示。

表1 仿真参数Tab.1 Simulation parameters

本文期望实现每类消息在适应自己的优势路径中传输。其中优势路径是指适应某类消息生存的中继节点所组成的路径,且不同类别消息之间的优势路径应该尽量减少重合,以减少不同类别消息间的资源竞争。为了简化分类标准,直接根据源节点与目的节点的不同来进行消息分类,就可以为不同类别消息赋予地域上的差异,使得不同类别消息形成各自的优势路径。因此,本文依照源节点与目的节点不同将消息分为16类。

同时,缓存大小及传输带宽都是网络拥塞的重要影响因素,因此本实验将讨论缓存大小以及传输带宽对消息到达率以及网络开销的影响。

3.2 结果及分析

网络指标随缓存及带宽大小变化如图3～图5所示,具体数值如表2和表3所示。

(a) 消息到达率随节点缓存大小变化

(b) 网络开销随节点缓存大小变化图3 网络指标随节点缓存大小变化Fig.3 Relationship between network indicators and cache size of nodes

(a) 消息到达率随带宽大小变化

(b) 网络开销随带宽大小变化图4 网络指标随带宽大小变化Fig.4 Relationship between network indicators and bandwidth

(a) 平均消息到达率随时间变化关系

(b) 平均网络开销随时间变化关系图5 网络指标随时间变化关系Fig.5 Relationship between network indicators and time

表2 不同缓存大小情况下网络指标具体值Tab.2 Specific values of network indicators under different cache sizes

表3 不同带宽大小情况下网络指标具体值Tab.3 Specific values of network indicators under different bandwidth sizes

从图3可以看出,4种缓存方法在消息到达率、网络开销方面的趋势相似。随着缓存大小的增加,消息到达率随之增高,网络开销随之变小。这是因为当缓存区大小变大时,节点的缓存中可以存储更多的信息,使得网络中同一个消息的副本数增加,进而增加了消息成功到达目标节点的概率。同时,缓存增加,缓存当中可以容纳更多消息,消息被丢弃的概率降低,重传的次数减少,使得网络开销减少。

从图4可以看出,随着带宽的增加,消息到达率与网络开销都随之增高。这是因为当传输带宽变大时,网络中的节点更加活跃,消息更容易在网络中进行传递,故而消息的到达率更高。因为更活跃,消息在网络中将进行更多次的传递,故而网络开销增加。

由图5可知,提出的基于最大最小蚂蚁系统的缓存管理机制明显优于其他机制。这是因为随着时间的推移,特定节点上某些类型消息的信息素浓度将继续增加,使这些节点更容易成为某些类型消息传输的中继节点,其他类型的消息将难以抢占此节点的缓存。这将使网络中的节点更难拥塞并丢弃消息,从而提高消息传递率。同时,基于最大最小蚂蚁系统的容迟网络缓存机制有效解决了蚁群算法易陷入局部最优的问题,随着时间的推移,基于普通蚂蚁系统的容迟网络缓存机制的性能在大约220 min达到收敛,而基于最大最小蚂蚁系统的容迟网络缓存算法在大约260 min达到收敛。

初始时刻,基于最大最小蚂蚁系统的容迟网络缓存机制相较于基于普通蚂蚁系统的容迟网络缓存机制在网络指标上表现较差,这是因为根据经验选取的初始信息素浓度值使得某些节点在初始时刻已经成为“最优”,陷入了局部最优,导致网络指标变差。后续工作将在已有研究的基础上探究利用网络及消息自身的相关指标对初始浓度设置,使得初始值浓度能够自适应地进行选取。

表2展示了当节点缓存大小为10 MByte和50 MByte时,4种缓存机制的网络指标的具体值。由表2可知,当缓存大小为10 MByte时,基于最大最小蚂蚁系统的容迟网络缓存机制比普通蚂蚁系统缓存机制在消息到达率方面提高了4.0%,在网络开销方面减少了8.4%;当缓存大小为50 MByte时,基于最大最小蚂蚁系统的容迟网络缓存机制比普通蚂蚁系统缓存机制在消息到达率方面提高了10.5%,在网络开销方面减少了10.0%。

表3展示了当带宽大小为50 kbit/s和500 kbit/s时,4种缓存机制的网络指标的具体值。由表3可知,当带宽大小为50 kbit/s时,基于最大最小蚂蚁系统的容迟网络缓存机制比普通蚂蚁系统缓存机制在消息到达率方面提高了13.2%,在网络开销方面减少了4.8%;当带宽大小为500 kbit/s时,基于最大最小蚂蚁系统的容迟网络缓存机制比普通蚂蚁系统缓存机制在消息到达率方面提高了2.7%,在网络开销方面减少了2.6%。

4 结束语

本文提出了一种基于最大最小蚂蚁系统的容迟网络缓存机制。该机制考虑信息的分类,使得同类别消息更容易通过同类信息素浓度高的节点进行传输。同时,本文定义了消息的信息素浓度、同类消息信息素浓度和总信息素浓度(丢弃权重)表达式,并利用总信息素浓度定义消息丢弃的优先级。仿真分析表明,基于最大最小蚂蚁系统的容迟网络缓存机制在消息到达率、网络开销方面具有比传统容迟网络算法更好的性能。

本文所提缓存机制只考虑了同类消息信息素对于网络指标的影响,并没有考到不同类别信息的信息素之间的影响。下一步工作将从以下三方面进行改进:

① 考虑不同类别消息的信息素之间的影响对容迟网络指标的影响;

② 结合实际场景对消息进行分类,使得分类标准更加明确,有效区别各类消息;

③ 对初始信息素浓度范围的取值进行研究。依据网络中的各类因素设置合适的信息素浓度初始值,避免基于最大最小蚂蚁系统的容迟网络缓存机制因初始信息素浓度过高而陷入局部最优。