基于蚁群优化的命名数据网络QoS路由研究

侯 睿，邵 瑞，郑明明，张 晴

(中南民族大学 计算机科学学院，武汉 430074)

命名数据网络NDN是一种在寻址方式上不同于传统IP网络的新型网络结构，传统IP网络的IP数据报格式以IP地址(目的地址和源地址)作为标识，而NDN则以URL分级结构的包名信息作为路由标识.

兴趣包和数据包是NDN中的两种基本包格式，其中数据包是用户想要获取的资源，而兴趣包的功能则是探寻数据包.为了获取数据包，首先需要广播相应的兴趣包，以探寻数据包[1].例如，用户想要从谷歌中获取某一个图片的数据，那么用户就要发送名字为URL格式的兴趣包来探寻数据包，若探寻到相同名字信息的数据包，便按照兴趣包所走路径的相反方向将数据包发送给用户.

基本的NDN节点包含3个数据结构表：转发信息表(FIB)，待定请求表(PIT)，内容存储器(CS)[2].FIB中存储的是路由节点到达内容服务器的下一跳的接口，PIT存储的是已从节点转发到下一节点的兴趣包的名字信息，以使数据包能够沿着原路径返回，CS中存储的是缓存的内容.当节点从一个接口收到一个兴趣包时，将根据它所包含的内容名进行最大匹配查询，而后根据查询结果进行下一步的操作.查询的优先级顺序依次为CS、PIT、FIB.

NDN具有多样的路由转发策略，并获取了丰富的研究成果，但目前的研究都还处于发展阶段，因此路由策略有很大的研究空间.由于因特网的快速发展，多样化的用户需求，特别是实时多媒体的应用对QoS的需求越来越高[3]，如何实现QoS路由显得尤为重要.QoS路由的任务就是对网络中的资源进行优化配置以寻找一条向用户提供端到端服务质量保证的路由.网络的路由问题与蚁群寻路的问题有很大的相似性，都是寻找可以到达目的地的最优路线，而且模拟蚁群寻路的ACO算法在解决路由问题上具有分布式、正反馈、全局收局收敛等优点，因此，本文将利用ACO来实现NDN中的QoS路由.

1 ACO_QoS路由策略

1.1 路由转发机制

对于节点的设计，依然采用文献[7]中SoCCeR算法所采用的节点设计方法.在SoCCer算法中，节点新增了信息素浓度表(PT)，PT中包含了服务的名字、对应的接口信息、接口所对应的信息素浓度值以及根据信息素浓度所计算出来的每个接口相应的选择概率.对于每一个服务请求，节点按照概率选择某一个接口将其添加到FIB中，并沿着FIB中的接口转发出去.PT对应的转发接口如图1所示，其中P0>P1>P2，P3>P1.

图1 PT及其对应的转发接口Fig.1 PT and the forward interface

在基于QoS服务的NDN中，为了获取数据包，首先需要发送一个带有QoS约束的兴趣包，兴趣包在各个节点通过NDN转发机制转发，当节点接收到兴趣包时，将根据内容名进行最大匹配查询，然后进行下一步操作.为了释放探寻失败的兴趣包所占用的PIT空间，本文新增了兴趣包探寻失败的响应报文，该报文中只包含与兴趣包相同的名字信息，如果探寻失败，当前路由器便会产生一个响应报文沿着兴趣包的反方向依次释放路由节点PIT中的兴趣包接口，这一点跟数据包的功能一样.操作流程如图2所示.

图2 NDN节点转发模型Fig.2 Forward model in NDN nodes

(1) 节点接收到兴趣包后，首先查询CS中是否包含兴趣包所请求的内容，若包含，则将请求的内容反向发送给用户，并沿途消耗对应的兴趣包.否则，转到⑵；

(2) 继续查询PIT中是否已经包含兴趣包对应的接口信息，若包含，则表明已经有与之相同名字信息的兴趣包在等待数据的相应，直接舍弃兴趣包,并将接口信息添加到PIT中.否则，转到⑶；

(3) 继续查询PT中是否包含与兴趣包对应的接口信息，若包含，则按照概率转移规则从PT中选择某一接口将兴趣包转发出去，并在PIT中新增该接口信息.若不包含，则表明无法探寻下一跳的接口，直接丢弃兴趣包，并在当前路由节点产生与兴趣包名字信息相同的响应报文，沿着兴趣包的反方向释放兴趣包所对应的接口信息；

(4) 兴趣包探寻结束.

因此，知识可视化和网络媒介素养教育的目的是一致的，都是为了知识的传播和知识的创造。知识可视化是从知识呈现的形式上的视觉化来促进知识的传播；网络媒介素养教育是从技术手段上促进知识的传播。如果把二者结合起来，快速传播的网络媒介技术承载着易懂的可视化的信息，人们既可以快速地获取信息，又能快速地解读信息，使得人们在信息时代中所面临的更快、更多地掌握知识的难题得到了解决。

1.2 QoS要求及信息素更新

1.2.1 QoS要求

本文将NDN网络模型表示为一个有向图G=(V，E),E表示NDN中的节点集合，E表示相邻节点所对应的边的集合.对于任意一个节点n∈V,包含两个QoS指标：节点丢失率Lost(n)、节点时延抖动Delay_Jitter(n)；对于任意一个边e∈E，也包含两个QoS指标：可用带宽Bandwidth(e)、链路费用Cost(e).对于一个包含QoS要求的兴趣包Interest(QoS)，其中QoS=(Lmax,DJmin,Bmin)分别表示最大丢失率、最小时延抖动以及最小带宽限制，QoS路由算法的目的就是能够找到一条费用(Interest(cost))最小并且满足QoS要求的路径L(V′,E′)，其中V′⊆V表示Interest(QoS)所经过的节点集合，E′⊆E表示Interest(QoS)所经过得边的集合.QoS要求如下：

(1)

(2)

(3)

(4)

1.2.2 状态转移规则

(5)

ηnk(t)=[Lost(k)]β[DelayJitter(n)]γ·

[Bandwidth((n,k))]δ,

(6)

其中α为信息启发因子，其值的大小反映了在选路过程中信息素的重要程度；公式(6)是启发函数，表示兴趣包从节点选择下一个接口的期望程度，β、γ、δ为期望启发因子；q服从的0～1均匀分布，q0∈[0,1]是一个特定的参数，可以调节兴趣包随机选路的比率.

1.2.3 信息素更新规则

(7)

(8)

Q表示信息素强度增加系数,costbest表示本轮迭代中最佳路由的费用的总和.

算法运行机制如下：

(1) 通过删除带宽小于需求带宽的链路，把网络过滤成一个新的简单的网络；

(2) 初始化网络拓扑中各边的相应信息素；

(3) 数据请求节点发送兴趣包探寻数据源，网络中的每个节点接收到兴趣包后根据公式(5)从PT表中选择接口u，将u添加到FIB中并将兴趣包从此接口转发；

(4) 一轮迭代结束后，对兴趣包经过的路径按公式(7)进行信息素的更新，并重新计算转移概率；

(5) 重复步骤(3)和(4)，直到网络运行结束.

2 仿真算例

图3为实验所用的网络拓扑，图中每个节点的值表示的是包丢失率和时延抖动，每条边上的值表示的是费用和带宽.

图3 网络拓扑及其参数Fig.3 Network topology and the parameters

为了与NDN中的随机转发模式比较兴趣包探索数据包的成功率，本文定义投递成功率(Success_Delivery_Ratek)如下：

(9)

其中Data_Countk表示第k次迭代过程中探寻到的数据包的数目，Interest_Countk表示第k次迭代过程中兴趣包的数目.

假定节点1处与用户直接相连，节点7、节点10分别与两个内容服务器相连，节点1处的用户需要获取节点7和节点10处的内容服务器中的内容.它们的QoS要求是：Lmax=10-5，DJmin=3，Bmin=80，简化后的网络拓扑如图4所示.

图4 简化后的网络拓扑Fig.4 The simplified network topology

仿真获得的全局优化路线如表格1所示，在对内容服务器7请求数据时，存在路由1→4→7，该条路由的费用只有3，但是其包丢失率达到了10-3，因此没有选择该路由.图5是本文所采用的ACO_QoS转发和NDN中另一种随机转发的投递成功率的对比，从图中可以得到，ACO_QoS转发随着迭代次数的增加投递成功率越来越高，这是因为后来的兴趣包根据先验经验选择符合QoS要求的路线的概率增大了；而随机转发的投递成功率基本维持在50%左右，大大影响了网络的性能.图6是对于内容服务器7和内容服务器10的请求的费用收敛曲线，从图中可以看出，对于内容服务器7的请求的费用收敛的较快，这是因为其最佳路径的费用相对于其它路径的费用要小的多，从而能够很快地寻找到最佳路线；而对于内容服务器10的请求，由于多条路径所需的费用的差距很小，因此在探寻最佳路线时要花费更长的时间.

表1 ACO_QoS路由结果

图5 ACO_QoS转发与随机转发投递成功率比较Fig.5 The comparison of Success_Delivery_Rate between ACO_QoS and random forwarding

图6 费用收敛曲线Fig.6 Average cost of ACO_QoS routing

3 结语

为了克服传统IP网络的缺陷，以内容为中心的命名数据网络成为一种新型的未来网络体系结构，其中命名数据网络中的路由是研究的一大热点.本文利用蚁群算法实现了命名数据网络中基于QoS机制的路由选择问题，能够选择出一条满足QoS的路由以提高数据包的投递成功率，并且使路径的费用和时延能够快速的收敛到较低的水平.

参 考 文 献

[1] Zhang L X,Estrin D, Burke J, et al. Named data networking (ndn) project[R]. California:PARC, 2010.

[2] 林 啸.以内容为中心的新一代互联网体系架构研究[J].电信科学,2010,5: 1-7.

[3] Zhang M W, Sun X M, Lv X Y. A QoS routing algorithm based on culture-ant colony algorithm[C]//IEEE.International Conference on Computer Application and System Modeling(ICCASM).Taiyuan: IEEE, 2010: 198-201.

[4] Ding G, Shi L, Wu X, et al. Improved ant colony algorithm with multi-strategies for QoS routing problems[C]//IEEE. International Conference on Natural Computation (ICNC).Chongqing:IEEE, 2012: 767-771.

[5] 林 闯,王元卓,任丰原.新一代网络QoS 研究[J].计算机学报,2008, 31(9):1525-1535.

[6] Yuan H, Song T, Crowley P. Scalable NDN forwarding: Concepts, issues and principles[C]//IEEE.International Conference on Computer Communications and Networks (ICCCN).Munich: IEEE, 2012: 1-9.

[7] Shanbhag S, Schwan N, Rimac I, et al. SoCCeR: Services over content-centric routing[C]//ACM.Proceeding of the ACM SIGCOMM workshop on Information-Centric Networking (ICN).Toronto:ACM,2011:62-67.

[8] 叶润生, 徐明伟. 命名数据网络中的邻居缓存路由策略[J]. 计算机科学与探索, 2012, 6(7): 593-601.

[9] Li Y, He Z. Improved ant colony algorithms with chaotic selection strategy for solving QoS routingproblems[J]. Energy Procedia, 2011, 13: 5890-5897.

[10] Sabrina F. A novel resource scheduling algorithm for QoS-aware services on the Internet[J]. Computers & Electrical Engineering, 2010, 36(4): 718-734.

[11] Triay J, Cervelló-Pastor C. An ant-based algorithm for distributed routing and wavelength assignment in dynamic optical networks[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(4): 542-552.