CCN中一种非混合式蚁群路由优化策略

刘期烈，诸葛丽强，夏远鹏，秦庆伟，邢峰英

(重庆邮电大学 移动通信重点实验室，重庆 400065)

0 引 言

随着网络快速的发展，如今网络的使用已经由内容的分发和检索所支配，而网络技术仍然是主机连接之间的通信。访问内容和服务需要将用户所关心的事物映射到网络所在处。在这种背景下，信息中心网络(information centric networking，ICN)作为一个革命式的未来互联网而诞生，让数据内容本身成为网络通信的主体单元，目前已经被一些研究会和研究项目进行了大量深入研究。其中热度最高的一个模型就是由Van Jacobson提出的CCN[1-2]构架，和TCP/IP构架有着相同的“细腰”模式，但其在数据传输时依赖的是内容而不是IP。CCN路由是基于命名的内容块，且CCN节点能够储存频繁请求的内容，如此便能够加速用户对于缓存内容的请求和减少网络的流量。

CCN节点主要由3个数据结构组成：转发信息表(forword information base,FIB)，未决兴趣表(pending interest table,PIT)，内容存储器(content store,CS)[3]。①FIB用来转发兴趣包到匹配数据的潜在内容源。它和IP的FIB几乎相同，一点除外：它允许多个转发接口而不是单单一个。②每一个PIT条目都是一个面包屑，用来追踪转发到上游内容源的兴趣包，这样就可以将返回的数据包发送到下游的请求者。一旦它们被用来转发一个匹配的数据包后，PIT条目立即被清除。③CS与IP路由器的缓冲存储器相同，但是有着不同的替换策略。都是保持存储内容与其名字之间的对应关系，并响应用户请求。当某个节点收到一个兴趣包后，首先查询CS中是否储存有所需内容，如果有，则直接返回，如果没有，则接着访问PIT；如果PIT中有所需数据，则等待数据包返回，否则继续查询FIB；如果FIB中有匹配的条目，则直接从相应端口转发出去，如果没有，则当TTL(time to live)截止后自动删除。

内容中心网络相对于传统互联网的一个重大改进就是引入了节点缓存功能，每个节点中暂存数据副本都可以作为用户的数据源，所以CCN中的路由过程已经转变成节点缓存普遍存在前提下，寻找优质的内容源。内容中心网络基本的路由策略采取洪泛的方式转发兴趣包，即当相同的内容请求到达该节点后，将会被复制后转发到所有的相关接口，并且引导大量相同的数据包返回到该节点处。虽然上述特性带来了数据传输的有效性和多样性，但会在网络中带来大量冗余流量，进而引发网络拥塞，降低了网络转发效率。因此，需要对CCN网络路由节点进行适当的扩展，优化兴趣包路由转发过程，以避免同一个Interest请求被多个资源重复响应，从而得到一个分布式、可扩展以及可容错的网络系统。

当前，CCN中现有的路由优化策略中，基于蚁群优化(ant colong optimization,ACO)的转发策略能够很好地满足上述优化要求。

ACO最先由M.Dorigo提出[4]，用来解决一些高难度的组合优化问题。ACO算法受自然界中蚂蚁搜索食物行为启发。蚂蚁寻求到达食物来源的最短路径，并通过遗留化学物质(信息素)与其他蚂蚁分享信息。一般情况下，蚂蚁优先选取那些有着较高信息素的路径。在同样的时间里，较短路径比起较长路径上有着更多的蚂蚁经过，这导致较短路径上遗留下更多的信息素，从而引导后续蚂蚁优先选择它们，进而不断的强化它们。CCN路由与蚁群寻路问题十分类似，都是为了找出能够到达目的地的最优路径。

虽然有关ACO的研究众多，但收敛性和最优性的理论分析仍然缺乏[5-7]。在众多蚁群优化算法中，只有2个蚁群系统(ACS[7](ant colong system)和最大最小蚂蚁系统[9](max-min ant system,MMAS)已被证明收敛于全局最优[10-11]，尽管他们的收敛性质较弱[12]。实际上，虽然ACS和MMAS确保最终获得全局最优解，但他们的收敛时间相当长。由于ACO过度的参数敏感性，通过微调ACO不能够有效地解决问题。由于算法的随机分量占据主导地位，过于强烈的收敛性导致其停滞在次优解，而偏弱的收敛过程可能得不出结果。文献[5]详细地讨论了上述问题。一个可能的解决方案就是混合ACO算法与其他方法[13],我们称其为混合式蚂蚁算法。

混合式蚂蚁算法倾向于产生高质量的解，通常优于同类型的非混合式算法。然而，在CCN路由领域它们有着诸多不足。文献[14]提出的混合式蚂蚁算法SoCCeR(services over content-centric routing)，用综合性服务路由决策扩展CCN，利用蚁群优化来解决服务路由和服务选择问题，但其收敛质量一般，并且在算法执行过程中产生过多数量的前向蚂蚁，增加了整个网络的负担。更重要的是，节点缓存的生存时间是被忽视的，一旦缓存过期，则选择的最优路径将失效。

为了解决上述问题，本文提出一种非混合式蚁群路由优化策略，即刺激蚂蚁架构(irritant ant framework，IAF)。IAF提供了ACO机制一个新的维度，扩展经典、单一信息素模型为动态多级别信息素模型；同时，将节点缓存特性与信息素更新规则相结合。以非混合式框架改善蚁群优化的收敛性能，提升CCN网络整体路由性能。

1 IAF架构

1.1 概述

传统ACS使用单一信息素值来标记蚂蚁轨迹。然而，现在已经证明[15-18]使用多个信息素类型有利于蚁群优化，并且它更能反映出现实中蚂蚁的真实行为[19]。

在蚁群算法中，信息素等级的角色是不同的。2个主要方案分别是：使用2种类型的信息素(吸引的和排斥的[15])或者每个请求都有信息素等级[16-18]。但多等级信息素方案带来限制：信息素等级的数量必须提前确定，还需要专门制定信息素挥发和累积策略以及状态转移方案。在本文架构中，允许IAF按照需求增长信息素等级L的数量，并且每个节点都是从L=1开始。

信息素等级并没有预先指定的角色，其创建的目的是为了提高效率和防止算法停滞在局部最优值[5]。并且本架构允许独立的蚂蚁探索，包括新产生等级的蚂蚁探寻低等级信息素轨迹。在算法执行过程中以非零概率确保新等级的产生，因此，停滞时间总是有限的。据了解，到目前为止在ACO中此种形式的动态性仍未被研究。

动态等级的创造受限于现存信息素提供的信息熵太高。将等级创造和熵的测量联系到一起的决定是基于生物学和心理学理由。如果我们考虑一个节点i并希望它如此，即过一段时间后，一个端口依据信息素值支配其他端口。然而，当某个节点请求获得最优路径，许多其他节点并没有形成优势明显的支配端口，或者最优的信息素值可能反复变化。清晰路径的缺乏表现出的是一种高信息熵或者混乱状态，这会在生物中导致刺激。因此，本文模型命名IAF。

在任何特定时间，一个蚂蚁被分配一个唯一的信息素等级。蚂蚁a(l)即蚂蚁a在等级l下被路由，并使用其对应的等级信息素值。蚂蚁a和等级l之间的配对，是在等级分配矩阵M(r)的协助下建立起来的。每个用户请求节点i都会保存和存储M(r)。在特定的情况下蚂蚁会改变他们的等级并产生新的等级。

1.2 状态转移规则

(1)

接口转发策略依据上述方法获得每个接口相应的转发概率值，进而根据需要选取概率值较大的一个或者多个接口转发兴趣包，转变传统CCN网络向所有接口发送兴趣包的策略。

(2)

1.3 节点缓存特性

对于任意的单个网络缓存节点i，蚁群算法构建到达该节点缓存的最优路径，如果不考虑缓存内容在节点中的持续时间长短，则会造成许多最优路径刚建立不久就失效。所以，本文提出一种全新的信息素更新方式，将该节点处缓存的命中概率考虑进来。

CCN中大多使用最近最少使用(least recently used,LRU)策略，本文也是在LRU缓存策略的前提下分析节点缓存特性对信息素更新策略的影响。

对于节点i上的任一内容c，将内容c在CS中的位置(ξ=1,2,…,N表示内容在CS中的位置)看作马尔科夫链的状态(内容c不在CS中的状态设为0)，建立起马尔科夫链模型，进而研究节点的缓存特性。假设内容c的请求速率为λ，迫使内容c存储位置下降的其他内容的请求速率为μ，且内容请求到达遵循Poisson分布，则内容c的状态转移如图1所示。

图1 CCN节点缓存马尔科夫链模型Fig.1 Markov chain model of CCN nodes cache

根据马尔科夫链的定义，图1为齐次马尔科夫链，其状态转移矩阵为

基于状态转移矩阵Φ，计算出平稳分布矢量[20]π=(π0,π1，…,πN)，且

(3)

(4)

平稳分布π反应了节点i上内容c缓存在各个位置的概率，尤其，π0表示内容不在缓存中的概率，即内容c的缓存丢失概率。所以，相应可得内容c的命中率为

Hc,i=1-π0

(5)

通过文献[21]可知，假设节点的内容请求中仅有少部分请求位于CS中，则μ可近似为节点上除了内容c以外其他所有内容的请求速率。本文采用上述近似方法得到λ和μ的值，从而取得节点i上各内容对象的命中概率Hc,i。

1.4 信息素更新规则

节点i收到返回的后向蚂蚁后，确定该Data包的可用性并读取其中的路由时延和负载信息，然后更新端口j的信息素值。

信息素更新公式为

(6)

(7)

(8)

(9)

(9)式中：x代表网络负载和往返时延，即x∈{load,delay}；Hc,i为节点i上各内容对象的命中概率。

缓存命中率Hc,i与信息增量成正比，前向蚂蚁从网络节点缓存处获得所需数据后，生成后向蚂蚁并且读取内容条目的缓存命中率，沿途更新端口信息素值。Hc,i的值越大，说明内容在该节点处存留的时间越长，通往该处缓存的最优路径的可靠性就越高，所以信息素的增量就越大。Hc,i的值越小，说明该节点缓存很快会被替换，那么到达该节点的大量相同的后续请求将会扑空，所以信息素的增量就越小。此外，当Interest包从服务器处获得请求内容时，Hc,i=1，这是由于服务器中的内容条目永远不会被替换掉。因此，相对于网络节点缓存，服务器的信息素值增加速度更快，并且由于大量的用户请求最终都是由服务器提供，考虑了缓存命中率的信息素增量公式将大大加快蚁群的收敛速度。

1.5 等级分配矩阵M(r)

蚂蚁生成后，在等级分配矩阵M(r)的帮助下,被分配予信息素等级。每个节点r都存储有一个大小为L×Q的矩阵ML×Q(r)。在节点r中，M(r)的各行相当于信息素的各等级；而M(r)的各列相当于起源自节点r的所有请求q。矩阵初始化为1×1:M1×1(r)=I0，并且能够按照需要动态增长。

假设矩阵M(r)有m个等级，n个请求，则

当节点r发起一个请求q，即产生一个蚂蚁aq。基于呈现在矩阵M(r)中的信息，节点决定蚂蚁应该被分配予何种等级。蚂蚁aq分配到任何一个等级的概率为

(10)

蚂蚁没有选中任何一个等级的概率为

(11)

在这种情况下，最优的可能等级依据下方公式选取

Ml′q(r)}

(12)

Mlq(r)←Mlq(r)+Δx

(13)

Mq(r)←(1-ρ*)·Mq(r)

(14)

在任何一个节点，如果l>L(返回的蚂蚁已经升级了一个等级)或者q>Q(一个请求第一次在节点发起)，则矩阵M通过拓展行和列来满足要求的新概念

Mlq=(Il×L×ML×Q)×IQ×q

(15)

1.6 蚂蚁等级变化

(16)

然后

(17)

(18)

2 仿真及性能分析

2.1 拓扑环境

为了评估算法的有效性，本文使用ndnSIM进行仿真实现。网络拓扑由GT-ITM工具生成30个节点的随机网络拓扑图。主要实验参数如表1所示。

表1 实验参数

在网络中选择2个边缘节点作为数据源节点，再随机选择5个网络节点作为数据请求节点，其他节点均为路由节点。内容的总数N设为6 000个，大小为10 kByte。节点的缓存容量相同，CS均设为100(节点可缓存的内容个数)，缓存策略为LRU。内容请求服从λ=20个/s的泊松过程,并且用户的访问模式遵循Zipf分布。

根据高铁系统所需求的滤波器指标,先评估指标通带的实现方案,再根据指标通带远端抑制的要求考虑是否级联低通滤波器。

2.2 性能评价

为了评价IAF算法的性能优劣，本文选取的性能评价指标包括平均请求时延(average request delay,ARD)，缓存命中率(cache hit ratio,CHR)和代价开销(cost)。

ARD:整个算法仿真过程中，用户成功取得请求数据所消耗时间的平均值。其计算公式为

(19)

CHR：即成功请求中从网络节点直接获取请求内容的请求数与请求成功数的比值。

(20)

cost：蚁群算法在提升性能的同时，都或多或少地引入了额外开销代价，主要包括节点存储开销，蚁群探索开销以及内容请求开销。

下面对各种开销进行具体分析：

1)节点存储开销(CC)。在SoCCeR和IAF算法中，节点建立信息素表格时，既要记载对应的内容名称，也要记载转发接口以及每个接口相应的信息素值大小，因此带来了额外开销。开销大小(单位为bit)与储存内容名字、接口信息以及信息素值的数量和大小有关。

(21)

(21)式中：Ln，Lf和Lp分别表示内容名字、接口信息和信息素值的大小；u，v，w分别为对应的储存数量。

(22)

(22)式中：S(q)为探索报文长度；d为探索报文路由跳数；J为仿真周期数；K为网络节点数量。

3)内容请求开销(CR)。CR定义为用户请求过程中，Interest包和Date包分别与其传输路程的乘积之和，开销单位(bit·hop)为包大小(bit)与传输跳数(hop)的乘积。

CR=(SInt+SDat)·d

(23)

(23)式中：SInt，SDat分别表示兴趣请求包和数据应答包的长度；d为相应的路由传递跳数。

2.2.1 用户平均请求时延对比

图2对比了各算法的平均请求时延。仿真运行中，采用已完成的累积请求来计算平均延时，只统计用户发出的请求，不包含节点发出的探索蚂蚁。从图2可以看出，仿真初始阶段平均时延都相对较高，随着节点信息素不断更新，最优传输路径逐渐确立，时延不断下降。此外，IAF算法下降的速度要快于SoCCeR，且收敛解的质量也优于SoCCeR。这也很容易解释，首先IAF使用全新的信息素更新公式，将节点缓存特性考虑进来，使得通过源节点获得数据内容的路径信息素增幅高于网络节点缓存(大部分请求还是从源节点获得所需数据)，从而加快了蚁群收敛速度；其次，IAF使用多等级信息素，增加蚂蚁路由选择，增强其对于当前路径之外的探索，避免其过早收敛并提高解的质量。当算法运行到75 s时，增大部分链路带宽，IAF算法在短暂时间段内平均时延略高于SoCCeR，之后两算法很快又趋于稳定。

图2 用户平均请求时延对比Fig.2 Average request delay comparison

2.2.2 缓存命中率对比

图3给出了不同Zipf指数下各算法缓存命中率的对比情形。从图3中可以看出，IAF算法的缓存命中率总是高于SoCCeR，这是由于IAF算法在更新信息素值的时候考虑了节点缓存特性，使得存储时间更久的节点缓存提供服务，增加了路径的稳定性、可靠性。随着δ的增大，2种算法的缓存命中率呈现出上升趋势，这是由于内容请求的局域性和集中性增强，高热度资源在缓存中的驻留及响应几率变大。

图3 缓存命中率对比Fig.3 Cache hit ratio comparison

2.2.3 代价开销对比

表2给出了2个算法的开销对比。2个算法在节点存储开销CC和内容请求开销CR方面差距微小。在IAF中没有探索蚂蚁机制，所以不会带来额外的探索开销CE，而SoCCeR算法在加快路径信息素更新速度的同时带来了大量的探索开销。

综合评估CC，CE，CR可以看出，2个算法开销的主要差距在于探索开销CE，并且SoCCeR远高于IAF。

此外，随着Zipf参数增大，多数内容请求集中在少数热点对象上，节点缓存上的内容存储时间更长，路径更加稳定，请求命中率更高。进而使得CE，CR都有着下跌趋势，尤其CR跌幅最大。

表2 代价开销对比

3 结 论

为了实现低代价开销获得高效可观的网络性能，在CCN中提出了一种非混合式蚁群路由优化策略。首次提出多等级信息素概念，将传统单级别信息素上升为多级别信息素，有效地抑制了蚁群早熟停滞；同时引进全新的信息素更新公式，改善了蚁群的收敛速度并且提升了节点缓存命中率。整个算法在较低开销的前提下获得了内容分发性能的显著上升，仿真结果证明了其有效性。后续工作是将此路由算法应用到实际网络环境(如PlanetLab)中进一步分析验证其性能和开销。