扬州大学信息工程学院，江苏 扬州

收稿日期：2022年6月20日；录用日期：2022年7月19日；发布日期：2022年7月26日

摘要

命名数据网络采用由内容请求者驱动的通信机制，针对转发过程中路由准确性问题现有研究并没有给出具体解决方案。本文提出了一种多因素综合考虑的蚁群路由优化算法。借鉴传统蚁群生态行为和遗传算法中的精英策略，综合考虑了各节点之间路径上的信息素浓度、邻居节点间路径长度以及请求节点与转发节点间的内容相似度等因素，采用可选下一跳方法将兴趣蚂蚁往高概率节点进行转发方式来确定最佳的兴趣蚂蚁路由路径；利用内容聚合和节点转换控制的方法进行拥塞控制保证网络传输的稳定性。仿真实验结果表明，在有限网络空间资源条件下，兴趣蚂蚁请求数量增加到一定阈值时，本算法对比蚁群算法平均路由命中率提高了14%，平均路由时延降低了25%，可以更有效避免网络拥塞。

关键词

命名数据网络，路由算法，精英策略，蚁群算法，拥塞控制

NDN Routing Policy Converged Congestion Control

Li Liu, Yiqi Gui

College of Information Engineering, Yangzhou University, Yangzhou Jiangsu

Received: Jun. 20^th, 2022; accepted: Jul. 19^th, 2022; published: Jul. 26^th, 2022

ABSTRACT

Named data network adopts communication mechanism driven by content requester. Existing research does not provide a specific solution for the problem of routing accuracy in the forwarding process. In this paper, an ant colony algorithm for routing optimization is proposed. Referring to the traditional ant colony ecological behavior and the elite strategy in genetic algorithm, taking into account the pheromone concentration on the path between nodes, the path length between neighbor nodes and the content similarity between requesting nodes and forwarding nodes, the optional next hop method is used to forward the interest ants to high probability nodes to determine the best interest ant routing path; Content aggregation and node switching control are used to control congestion and ensure the stability of network transmission. The simulation results show that when the number of interested ant requests increases to a certain threshold under the condition of limited cyberspace resources, the average routing hit rate of this algorithm is increased by 14% and the average routing delay is reduced by 25% compared with ant colony algorithm, which can more effectively avoid network congestion.

Keywords:Named Data Network, Routing Algorithm, Elite Strategy, Ant Colony Algorithm, Congestion Control

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着数据及用户的不断增长，现有的TCP/IP网络架构存在的缺陷愈发明显，其网络安全性问题和较差的扩展性成为限制互联网继续发展的因素。为了打破当前“主机到主机”的通信模式，实现互联网数据处理的强大功能，信息中心网络(Information-Centric Network, ICN) [1] 作为一种革命式的新型网络体系结构应运而生。其中命名数据网络(Named Data Network, NDN) [2] 是一类ICN网络架构。NDN旨在构建基于内容寻址的网络服务，网络虚拟化和SDN技术使得现有网络进行NDN服务构建成为可能。

基于内容寻址的网络架构有两大核心机制，分别为内容路由 [3] 和网内缓存 [4]。本文主要研究命名数据网络路由的策略，NDN路由转发可以视为在缓存普遍存在的前提下，面向内容的寻址方式。Cheng等人 [5] 研究了NDN中自适应转发的问题，利用数据包自带寻址的操作控制网络的路由规模，缺点是存在技术可行性和环境适应性的问题。一种同时考虑缓存与路由的策略 [6] 提出一种新的路由协议方式以改善缓存同时提高路由效率，不足之处在于对于多路径路由转发缺乏实用性。全转发策略 [7] 是NDN网络中比较原始的路由方式，对于单个内容请求的兴趣包，节点向转发信息表(Forwarding Information Base, FIB)中所有对应的接口转发该兴趣包，缺点是路由过程中会造成大量的数据冗余。随机转发策略 [8] 针对单个兴趣包，路由节点选择转发信息表中随机接口请求数据转发，降低了时延，但无法保证用户获得稳定的网络性能。一种基于优先级计算的兴趣转发策略 [9] 选择最佳的兴趣转发传出接口以便转发兴趣数据包，然而该策略在高带宽要求下未能表现出良好的性能。

NDN的路由优化问题 [9] 引申出不同种类的仿生解决方案。相较于其它仿生策略，蚁群中蚂蚁的觅食行为类似于NDN的路由过程。将蚁群算法应用于命名数据网络的研究中，Zhang等人 [10] 提出改善下一跳选择的代价，一定程度上缩短了请求的时延，然而没有考虑不在传输路径上的节点缓存；将信息素分为不同等级的理念，使用多级别信息素替代传统单一信息素，在较低复杂网络的前提下性能得到提升，作为一种非混合式蚁群路由优化策略 [11] 并不适用于大型复杂网络；一种以内容为中心，面向服务的路由策略 [12] 可以在NDN上添加一个控制层来操作底层FIB，采用基于蚁群算法的机制收集服务信息。A. Z. Khan等人 [13] 提出了一种基于ACO的服务质量(QoS)感知路径选择方案，使用具有较高信息素的传出接口进行转发具有较高概率的兴趣包；Huang等人 [14] 基于概率提出了一种使用蚁群算法的自适应转发策略以减少传输延迟和网络开销。

上述这些路由方式存在一些缺点，比如无法利用临近缓存、收敛速度过慢等。本文借鉴遗传算法中的精英选择策略，即把适应度最好的个体保留到下一代种群中的方法，加快蚁群收敛速度。另一方面，在使用精英策略转发兴趣蚂蚁时进行适当聚合保持下一跳节点可选，设置节点拥塞度 [15] 来控制拥塞，提升网络稳定性。采用熵权法对上述两方面结合优化，最终得到整体最优的性能。

2. 携带精英策略的蚁群路由算法

算法策略的思路源自蚁群算法，将不同节点内容的差异性作为转发概率的衡量标准之一，引入精英策略思想将成功进行最优路径选择的蚂蚁命名为精英蚂蚁并且精英蚂蚁走过的路径进行额外的信息素更新，为了减少路由表规模膨胀的影响进行适当的内容聚合且做出精准的拥塞控制，最后使用熵权法对实验指标建模得出综合最优。

2.1. 改进蚁群路由算法

通过模拟自然界蚁群合作觅食的行为，仿生出一种人工蚁群算法。基本原理是通过多次迭代计算出从当前节点i到它的邻居节点j的状态转移概率以做出选择进行下一跳，综合考虑各节点之间路径上的信息素浓度、邻居节点间路径长度以及请求节点与转发节点间的内容相似度，其转移概率公式为：

$P_{ij}^k=\{\begin{array}{ll}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\epsilon }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }{\left[{\cos }_{ij}\left(\theta \right)\right]}^{\gamma }}{{\displaystyle \sum _{s\in a_k}{\left[{\tau }_{is}\left(t\right)\right]}^{\epsilon }{\left[{\eta }_{is}\left(t\right)\right]}^{\beta }{\left[{\cos }_{ij}\left(\theta \right)\right]}^{\gamma }}},\hfill & j\in a_k\hfill \\ 0,\hfill & 其它\hfill \end{array}$ (1)

其中， ${\alpha }_k$ 为当前节点i非禁忌可选下一跳节点的集合； ${\tau }_{ij}\left(t\right)$ 是路径 $\left(i,j\right)$ 上的信息素强度，在迭代开始前默认每条路径的初始信息素强度相同； ${\eta }_{ij}\left(t\right)$ 为启发式因子，与路径长度有关； $\cos \left(\theta \right)$ 为代表内容差异性的余弦相似度。参数 $\epsilon$ 、参数 $\beta$ 和参数 $\gamma$ 分别代表信息素因子、启发式因子和内容相似度因子对于转移概率的权重影响。

2.2. 精英选择策略

为提高寻找最优解的速度，本文引用精英蚂蚁，即为带精英策略的蚁群算法。为精英蚂蚁走过的路径进行额外的信息素更新，带精英策略的蚂蚁系统信息素更新方式如下：

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+\Delta {\tau }_{ij}+\Delta {\tau }_{ij}^{\ast }$ (2)

${\tau }_{ij}\left(t\right)={\displaystyle \underset{k=1}{\overset{m}{\sum }}\Delta {\tau }_{ij}^k}$ (3)

上式中 $\rho$ 代表信息素衰退程度， $1-\rho$ 则表示信息素残留系数。 $\Delta {\tau }_{ij}^{\ast }$ 表示精英蚂蚁在节点i和j路径上的信息素增量。 $\Delta {\tau }_{ij}^k$ 则表示第k只兴趣蚂蚁在本次迭代中为路径 $\left(i,j\right)$ 带来的信息素增量。当精英蚂蚁数量过多，局部最优路径上的信息素浓度增长速度过快，从而出现搜索早熟收敛的情况，需要对精英蚂蚁的数量进行合适的取值，同时考虑到节点负载问题，对蚁群进行分批次迭代实验，迭代次数为 $N_C$。

$\Delta {\tau }_{ij}=\{\begin{array}{ll}E/R_k\hfill & 第k只蚂蚁从节点i到节点j\hfill \\ 0\hfill & 其它\hfill \end{array}$ (4)

$\Delta {\tau }_{ij}^{\ast }=\{\begin{array}{ll}M\cdot E/R^{\ast }\hfill & 节点i和j之间为最优路径\hfill \\ 0\hfill & 其它\hfill \end{array}$ (5)

式(4)中E表示信息素强度；式(5)中M表示精英蚂蚁的个数， $R^{\ast }$ 是本次迭代最优解的路径长度。考虑到信息素随着时间流逝不停挥发，构建相邻节点间的内容浓度更新模型。节点的信息不但根据自身请求获得的数据蚂蚁进行更新，还要叠加其它节点经过的蚂蚁(具体算法见算法1)。内容的差异性使得数据规模庞大间接导致时延的增加，因此在路由时需考虑避免网络拥塞，为降低网络负载本文选择在路由时对数据内容进行聚合，同时使用控制节点转换的方法进一步降低拥塞。

算法1精英策略路由算法

输入：起始节点a₁，目的节点a_j和实验参数

输出：接收到目的节点的数据包

1)put Ant on start point a₁ , $N_C=\text{1}$

2)for Ant k in M Do

3) Use formula 2 calculate the probability and transition

4) if Ant i reach to a_j

5) $k=k+1$

6) Update pheromone

7) else continue routing

8)Record optimal path and Update Elite pheromone

9)if $N_C<N_{CMAX}$

10) $N_C=N_C+\text{1}$

11)end if

3. 基于熵权法的拥塞控制

节点的拥塞会给路由的稳定性带来较大的隐患。针对NDN节点的拥塞控制本文分为两个部分，分别是内容聚合和节点转换。考虑到不同的节点拥塞阈值会对实验整体性能产生影响，本文使用熵权法对实验指标进行建模价并得出综合评价最优的取值。

3.1. 内容聚合

内容节点的多样性和差异性使得路由表规模易急剧膨胀，不能及时处理数量巨大的条目使得网络延迟逐步增加。本文采用可选下一跳FIB聚合来解决数据膨胀的问题，对命名内容进行相应规则的聚合用以提高路由表项的利用率。聚合需要满足的规则首先是内容命名具有相同的前缀，其次是二者路由时具有相同的下一跳。

3.2. 节点转换控制

为进一步实现拥塞控制，节点在转发的过程中，设定判定节点是否拥塞的两个阈值(C_max, C_min)，通过屏蔽拥塞度达到C_max的节点的方式，将数据回转到次最优节点，而屏蔽节点拥塞度降到C_min后重新启用(算法2)。本文使用拥塞度C代表节点在一个周期t内处理兴趣包的能力，其变化过程可用下式表示：

$C=C_{\min }+\left(C_{\max }-C_{\min }\right)\frac{D_t}{D_s}$ (6)

其中，D_t表示当前周期内节点累积需要转发的兴趣包总数，而D_s则表示节点历史最大累积转发总数。节点状态转换如图1所示。

图1. 节点状态转换图

算法2拥塞控制算法

输入： $C_{\min }$，兴趣蚂蚁 $An{t}_i$，周期t，最优次优节点 $a_c,a_v$

输出：实时最优 $C_{\max }$ 的值，

1) $D_t=0$，$D_s=300$

2) For i = 1

3)IF $An{t}_i$ aggregate with $An{t}_{i+1}$，$An{t}_i$ reach $a_c$

4) $D_t=D_t+1$

5) $i=i+2$

6) Calculate C by using formula 8

7) if $C<C_{MAX}$

8) continue

9) else find and select $a_v$ as the suboptimal node by using formula 2

10)if $C\le C_{MIN}$

11) reuse $a_c$ instead of $a_v$

12) end

3.3. 熵权法建模

本文使用熵权法对实验四个评价指标进行建模，通过实验得出最优的阈值取值。使用熵权法的步骤如下：首先是构建初始矩阵，实验中原始矩阵的构建信息可以通过实验中阈值数和评价指标数得出：

$z=\left[\begin{array}{cccc}{z}_{11}& z_{12}& z_{13}& z_{14}\\ z_{21}& z_{22}& z_{23}& z_{24}\\ z_{31}& z_{32}& z_{33}& z_{34}\\ z_{41}& z_{42}& z_{43}& z_{44}\end{array}\right]$ (7)

矩阵Z表示实验时阈值的取值有4个，其范围为{0.7, 0.8, 0.9,1}，而评价指标有4个，分别为命中率、路由跳数、路由时延和通信开销。由于命中率是正向指标，而路由时延、路由跳数和通信开销是负向指标，所以需要进行标准化处理。

$Q_{ij}=\{\begin{array}{l}\frac{z_{ij}-\min \left(z_i\right)}{\max \left(z_i\right)-\min \left(z_i\right)}\left(正向\right)\\ \frac{\min \left(z_i\right)-z_{ij}}{\max \left(z_i\right)-\min \left(z_i\right)}\left(负向\right)\end{array}$ (8)

其中， $Q_{ij}$ 为归一化处理之后的第i个节点的第j个指标， $\max \left(z_i\right)$ 、 $\min \left(z_i\right)$ 表示指标最大最小值。根据信息熵的定义，一组数据的信息熵 $E_j$ 如式(9)。式(10)中 $S_{ij}$ 表示指标j在方案i下所占比值。如果 $S_{ij}$ 的值是0时，那么 $E_j$ 也为0，代表着此指标的信息熵为0。

$E_j=-\ln {\left(n\right)}^{-1}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{s}_{ij}\ln s_{ij}}$ (9)

$s_{ij}=\frac{Q_{ij}}{{\displaystyle \underset{i}{\overset{n}{\sum }}{Q}_{ij}}}$ (10)

得到信息熵 $E_j$ 后可以计算各个指标的权重并得出不同取值对应的综合评价。式(11)、(12)分别是权重公式以及综合评价公式，式中 $w_j$ 为各指标的权重， $T_i$ 为各阈值取值下的综合评分，其中k为指标个数等于m。

$w_j=\frac{1-E_j}{k-\sum E_j}$ (11)

$T_i={\displaystyle \underset{j=1}{\overset{m}{\sum }}{w}_j\cdot Q_{ij}}$ (12)

4. 仿真实验

本文提出的EACO路由算法在使用python语言在Pycharm中模拟数据命名网络的环境下进行仿真实验。数据命名网络节点的内容符合Zipf分布，其中Zipf参数 $\alpha$ 默认设置值为1.0，Zipf分布的特性使得更少的节点被更多的用户访问，具有无标度特性。本算法使用networkx [16] 生成一个小型无标度网络，同时刻画出对应拓扑a (见图2)，为与其产生对比实验引入复杂网络拓扑b (见图3)分别进行了模拟仿真。实验参数如表1所示。为了评估算法的性能，实验中将路由命中率、路由跳数 [17]、路由时延和通信开销 [18] 作为性能评价指标。实验中引入全转发策略(Full Forwarding strategy, FFS)，随机转发策略(Random forwarding strategy, RFS)，和蚁群路由算法(Ant colony routing algorithm, ACO)并进行了对比。

图2. 拓扑a

图3. 拓扑b

表1. 参数表

对比实验前通过引入熵权法的实验确定阈值 $C_{\max }$ 的取值。图4和图5分别代表在拓扑a和拓扑b中不同迭代次数下，增大阈值取值得出的综合评分。实验结果表明，拓扑和迭代次数得变化都不太改变整体效果格局，随着阈值的增大， $T_i$ 大体也随之增大。拓扑a和b中 $T_i$ 上升下降趋势相同，拓扑b中 $T_i$ 整体取值大于拓扑a，造成这种现象的原因是两种拓扑结构的差异导致四种评价指标的差异较明显。可以观察发现，在拓扑a中，除了迭代次数为1的情况下， $C_{\max }$ 取0.9的综合评分是最高的；而在拓扑b中，除迭代次数为1和2的情况下，0.9作为取值仍是最优。因此实验表明，阈值 $C_{\max }$ 的取值是和拓扑结构以及实验迭代次数相关的，在后续实验中本文对照图5和图6选择合适的取值 $C_{\max }$ 进行实验。

图4. 拓扑a评分图

图5. 拓扑b评分图

4.1. 平均路由命中率

平均路由命中率ARHR (Average route hit rate)定义为成功检索到所需求的内容的兴趣蚂蚁占总迭代的兴趣蚂蚁的比例如下式：

$\text{ARHR}=\frac{N_C\cdot {\displaystyle \underset{i=1}{\overset{n}{\sum }}r}}{N}$ (13)

其中n为每次迭代兴趣蚂蚁数，实验中取600，N_C为迭代次数，N为蚂蚁总数，r表示兴趣蚂蚁是否成功命中，其值为0或1，为1时表示命中，为0时表示路由失败。图6和图7对应拓扑a和b的路由命中率对比。在两种不同拓扑结构网络下，ACO和EACO的路由命中率都远大于FFS和RFS，原因在于FFS和RFS都无法针对所需的内容节点进行最优路由选择。FFS会造成多余的路由冗余，略好于RFS，但也无法获得较为稳定的网络性能。经过多次迭代实验后，ACO和EACO保持路由命中率持续升高，且EACO的命中率升高速率大于ACO，这是由于EACO在ACO基础上进行改进，加入了精英蚂蚁，使得命中率收敛速度大幅度提高。

图6. 拓扑a ARHR折线图

图7. 拓扑b ARHR折线图

4.2. 平均路由跳数

平均路由跳数ARH (Average routing hops)定义为路由成功的兴趣蚂蚁平均跳数。可用下式表示：

$\text{ARH}=\frac{{\displaystyle \underset{i=1}{\overset{N}{\sum }}f\left(i\right)}}{N_C\cdot {\displaystyle \underset{i=1}{\overset{n}{\sum }}r}}$ (14)

上式中 $f\left(i\right)$ 表示成功命中的兴趣蚂蚁转发的跳数， $r_s$ 则表示路由成功的次数。平均路由跳数能够表达路由路径的优劣性。图8和图9均路由跳数随请求迭代次数变化的情况，本文所提出的路由机制的平均路由跳数在拓扑a中下降了24.6%，拓扑b中下降了19.3%。其中FFS和RFS表现相对较差且不会受到迭代次数增加的影响而降低跳数。EACO优于ACO的关键仍是精英策略对最优路径加速收敛的作用。

图8. 拓扑a ARH折线图

图9. 拓扑b ARH折线图

4.3. 平均路由时延

平均路由时延ARD (Average routing delay)，定义为所有兴趣蚂蚁从出发到停止搜索下一跳所经历的时间的平均值。兴趣蚂蚁停止搜索的情况有两种：第一种，携带此兴趣包的兴趣蚂蚁已检索其所需的内容节点；第二种，携带此兴趣包的兴趣蚂蚁在未找到其所需内容所在节点前无非禁忌下一跳节点。

$\text{ARD}=\frac{N_C\cdot {\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(S_i/v\right)}}{N}$ (15)

其中， $S_i$ 是兴趣蚂蚁路由总路程，v是路由速率，时延的单位为毫秒。

EACO和ACO的平均路由时延远低于FFS和RFS且随着迭代次数增加越来越低。由于EACO考虑了路径长度，综合的信息素浓度以及节点间内容的相似度，因此能有效避开拥塞程度相对高的节点，找到最优选择的路径，在兴趣蚂蚁请求数较多情况下，大大节约了兴趣包等待时间。图10、图11表明，在不同拓扑下，考虑节点的内容相似度和加入精英蚂蚁都会使得EACO比ACO更早进入收敛。

图10. 拓扑a ARD折线图

图11. 拓扑b ARD折线图

4.4. 通信开销

通信开销COH (Communication overhead)定义为网络中所有生成的包被转发的次数与成功命中的包的比值。

$\text{COH}=\frac{{\displaystyle \underset{i=1}{\overset{N}{\sum }}F\left(i\right)}}{N_C\cdot {\displaystyle \underset{i=1}{\overset{n}{\sum }}r}}$ (16)

其中， $F\left(i\right)$ 表示第i个节点路由过程中所转发的次数。FFS、RFS、ACO和EAOC在两种拓扑下的通信开销如图12和图13所示。对比几种策略可以发现ACO和EACO的通信开销是低于FFS和RFS的，这得益于蚁群算法对路由的精准性提升，而RFS相比较于FFS减少了部分无效路由，相比较而言通信开销也有所降低。观察可以发现，一方面图12区别于图13，EACO的通信开销随着兴趣蚂蚁数量增加逐渐超过ACO，考虑到EACO策略中加入了节点控制转换的操作，导致在路由过程中存在增加网络开销的情况，另一方面图13显示在复杂网络下，EACO整体通信开销还是低于ACO的，表明在阈值实验中选取不同的拥塞控制阈值也会影响网络的通信开销。EACO考虑了单个节点负载情况，避免了局部拥塞节点的出现，更好地促进了兴趣蚂蚁的转发，降低了网络的整体负载，尽管在小型拓扑中相比于ACO有着较高通信开销，但总体性能仍然优于其他策略。

图12. 拓扑a COH折线图

图13. 拓扑b COH折线图

5. 总结

蚁群算法具有并行性、较强的鲁棒性、良好的全局搜索能力并能应用在众多领域中，本文提出一种结合精英策略对传统蚁群算法进行改进的NDN路由机制，综合考虑各节点间路径上的信息素浓度、邻居节点间路径长度以及请求节点与转发节点间的内容相似度；同时，在路由选择时针对路由的盲目性问题采用可选下一跳节点FIB聚合方法，针对拥塞问题提出节点控制转换的方法。提出使用熵权法综合考虑四个性能指标，控制两种方法的组合最优的前提下保证路由命中率和路由时延的同时控制了网络的拥塞。仿真实验结果表明，在网络空间资源有限、网络开销合理的前提下，不断增加请求数据包的情况下，本文使用的策略相比另外三种路由策略有着较大的性能提升。在未来工作中，我们考虑进一步优化算法，通过引入其它协同策略提高性能。

基金项目

江苏省自然科学基金(BK20150459)；未来网络科研基金项目(FNSRFP-2021-YB-48)。

文章引用

刘 立,桂易琪. 融合拥塞控制的NDN路由策略
NDN Routing Policy Converged Congestion Control[J]. 计算机科学与应用, 2022, 12(07): 1781-1794. https://doi.org/10.12677/CSA.2022.127179

参考文献