基于改进贪婪算法的测量节点选择优化方法

吴 上，盛益强，邓浩江

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190; 2.中国科学院大学，北京 100049)

0 引 言

随着互联网的不断发展和工业化水平的不断进步，人们对于确定性时延需求越来越大。然而现有名字解析系统(Name Resolution System, NRS)中普遍没有进行针对性设计。如何在一定规模的真实网络场景中构建网络模型，并进行快速测量节点选点计算，就成了一个值得研究的问题。本文将测量节点选点问题抽象为最小点覆盖问题，并结合具体场景对传统贪婪算法进行改进，从迭代周期、排序算法以及方案评价方面进行设计与实现，具有一定的应用价值。

1 背 景

互联网一直保持以主机为中心的模型。早期互联网在网设备数量少，设备之间可信度较高。互联网的设计原则使得互联网规模迅速增加。互联网的沙漏结构中增加了应用和服务的扩展性。不断发展的各种新应用和服务的发展带来了可扩展内容分发、移动性、安全性、可信性等问题。为了解决这些问题，互联网架构陷入了不断打补丁的泥潭。未来网络会存在越来越多的信息传播需求，而非主机间的成对通信需求。为此，信息中心网络(Information Centric Networking, ICN))应运而生。ICN通过在网络层对名字命名，天然地支持网内缓存、多播和移动性需求，能够应对未来网络需求[1]。

物联网(Internet of Things, IoT)特别是工业互联网(Industrial Internet of Things, IIoT)的快速发展，对现有网络架构也提出了更高的要求，不仅要求具有较低的平均网络延时，更要求实现确定性网络时延保障。尽管人们采用了包括边缘计算在内的新技术降低计算时延，但变化不定的网络传输时延仍是亟待优化的关键因素。因此，第5代通信技术(The Fifth Generation Communication Networks, 5G)作为下一代通信技术，其凭借超大规模并发连接，超低延时的特点受到了工业界的广泛关注和应用尝试[2]。

随着IMT-2020的不断推进，ICN也在不断地标准化以增强5G网络，例如文献[3]中要求，NRS必须实现低时延与扩展性的要求以满足IMT-2020中URLLC(Ultra Reliable and Low Latency Communication)和mMTC(Massive Machine Type Communication)的应用场景。同时还应具备移动性支持、路由支持和互操作性(Inter-operation)支持。文献[4]提出了确定性时延名字解析(Deterministic Latency Name Resolution, DLNR)，通过将物理网络划分为层级嵌套的层次弹性结构(Hierarchical Elastic Area, HEA)并为每个HEA部署服务于本层级的名字解析服务节点。在对物理网络的划分过程中，节点间时延是重要依据之一。

为了获取节点间时延，可以考虑在每个节点都部署测量程序，这在小规模的网络是可行的，但是测量成本会随着网络规模的扩大指数级别上升。文献[5-6]讨论了内容中心网络中少数关键节点是否在线会影响整个网络的连通性。为此，考虑到信息中心网络的特点及其时延测量的需求，本文将网络测量节点部署问题映射成为最小点覆盖问题，并基于传统的贪婪算法提出一种面向网络测量节点选取的改进贪婪算法，优化传统贪婪算法的迭代模块和排序算法以改进其在实际应用中的适配性，实验表明取得了预期的效果。

2 现有最小顶点覆盖求解算法

很多文献将非图论问题抽象为最小顶点覆盖问题求解，比如文献[7]将现实生活中的共享单车投放问题映射为求解图的覆盖问题，文献[8]利用子图分解研究了多运动目标视频跟踪问题，文献[9]利用图表示学习方法解决了动态网络异常检测问题等。

图的顶点覆盖指的是在图G=(V,E)中选出部分点的集合，使得图中所有的边都与之相连。最小顶点覆盖问题(Minimum Vertex Cover, MVC)是求解满足上述要求的最小点集。最小顶点覆盖有着非常多的应用场景，如文献[10]设计了一种扫描测试向量生成算法。如果按照解决问题的时间复杂度分类，不能在多项式时间内求解的问题叫做NP问题。对于这类问题，在待求解问题规模很大的情况下时间开销是难以接受的。NP完全问题包括2个基本要求，一个要求是问题本身必须为NP问题，另一个要求是应当可以在多项式时间内归约为NP问题[11]。文献[12]完成了最小顶点覆盖问题是NP完全问题的证明。因此，最小顶点覆盖问题可以通过精确算法和近似算法求解。虽然前者最终会得到精确的结果，但是在求解大规模问题时所耗费的计算能力和时间是难以接受的，故该类精确算法只适用于解决小规模问题。而后者则在牺牲了一定精度的情况下能够在多项式时间内求解相应问题，在实际中受到广泛应用。常见的近似算法有以下几种：

1)贪婪算法。贪婪算法是解决点覆盖问题的经典算法之一，最早在文献[13]中提出，后来文献[14]提出了MDA(Maximum Degree Algorithm)算法。其核心思想在于求解度最大的节点并依次迭代删去。文献[15]提出了VSA(Vertex Support Algorithm)算法，其主要工作在于设计了顶点支撑参数，定义顶点邻居的度数之和作为顶点支撑。文献[16]基于贪婪算法提出了MAMA(Maximum Adjacent Minimum degree Algorithm)算法，通过利用顶点支撑参数排序求解最小顶点覆盖问题，在小规模网络中有着较好的实验效果。

2)蚁群算法。文献[17]最早通过模拟蚂蚁经过路径上的信息素，使得群体具备一定的智能，经过一段时间，连续不断的正反馈就能形成一个近似解。文献[18]将分布式网络测量中的测量节点部署问题抽象为最小顶点覆盖，并基于蚁群算法提出了求解，以性能上的部分代价换取了更低的近似比。

3)遗传算法。文献[19]模拟了生物学中的“物竞天择，适者生存”，能够同时处理多个研究对象，有效扩大搜索范围，避免了陷入局部最优。

类似的还有基于膜系统的解决方法，如文献[20]。由于篇幅所限，不再一一说明。

以上算法大多只考虑了算法的一个方面，例如大多算法都在比较小规模场景中的近似比，试图将近似比向1逼近；部分算法考虑的应用范围过于局限，无法结合ICN名字解析系统的物理网络划分实际情况。为此，本文基于传统贪婪算法，通过优化算法结构，结合实际应用场景提出一种改进的贪婪算法(Improved Greedy Algorithm, IGA)。

3 算法内容

广义上来说，贪婪算法，其核心是通过迭代的方式，不断寻找当前的最优解，直到收敛为止。这是一个虽然简单但是十分有效的近似算法，试图以不断的局部最优结果逼近全局最优结果。本章分别介绍传统贪婪算法和改进的贪婪算法。

3.1 传统贪婪算法

传统贪婪算法通过计算各节点度数，将度数排序，循环选取度数最大的节点作为最小点覆盖集合，直至覆盖全部边。伪代码如下：

Input: G=(V, E)

Output: C

Begin:

1.C←∅; //一开始最小点覆盖为空集

2.While E≠∅ do {

3.n←|G(V,E)|

4.for i←1 to n {

5.d(vi) //计算每个节点的度数d

6.}

7.D←d(vi) //对所有点的度数进行排序

8.t←Δ(G) //选出一个节点度数最大的节点t

9.V←V-{t} //从全部节点中删除节点t

10.C←C∪{t} //将节点t加入最小点覆盖集中

11.Go to 2 }

12.Return C

End

以上伪代码对传统贪婪算法的原理做了详尽的说明。使用该算法对图1进行求解，可以推理出一种最小点覆盖的近似解。其中灰色节点为传统贪婪算法的求解结果。

图1 传统贪婪算法求解结果

经过分析，图1中的节点并非最小节点覆盖的精确结果。最小点覆盖集合如图2中灰色节点所示，对比可以发现：在给定图例中，传统贪婪算法求解结果比最优求解方案多出了14%的节点数量，说明即便在小规模图的求解精度上，传统贪婪算法也不是理想的选择。

图2 最小覆盖集最优结果

此外，该算法的扩展性较差，在最坏情况下运行复杂度为O(E2)，即便在中等规模验证中也不理想。计算时间与节点数量的关系如图3所示。

图3 节点数量与计算时间的关系

3.2 改进后的贪婪算法

下面从迭代周期优化，面向BA无标度网络模型的排序算法优化和方案选择等相关工作进行说明。

3.2.1 迭代周期优化

图3可以说明，若求解一定规模下的应用问题，选择传统贪婪算法进行计算是不切实际的。经实际代码分析，其扩展性差、运算开销大的原因是迭代过程开销过大。具体地，在求解Δ(G)的过程中涉及大量的排序计算，传统贪婪算法中每次循环过后都要重新求解度排序，这会消耗大量的计算资源。但事实上这样仅适用于小规模场景，当实验规模较大、节点数量较多时，删去某个特定节点及其边的过程并不会导致节点度排序的大量变化，从而不需要对节点度数再次排序，因此很多的排序过程是可以省略的。本文结合实际应用场景对迭代周期进行探索优化，通过设计合适的迭代周期，在提高计算速度的同时尽量降低迭代次数，减少对精度的不利影响，从而提高模型的求解速度。

3.2.2 面向BA无标度网络模型的排序算法优化

文献[21-24]介绍了ICN的结构，在此基础上，文献[25]介绍了一种ICN节点选择方法，文献[26]介绍了一种IoT环境下ICN名字解析方法。这些文献都没有考虑到现实网络的规模效应，常用的网络模型包括ER随机图模型、WS小世界模型、Waxman网络模型以及BA无标度模型等。ER随机图模型指的是任意生成一个含有N个节点的随机网络，其中节点间以概率p进行链接，此时其度分布比较接近泊松分布。WS小世界模型指的是节点间存在非常丰富的短路径，此时节点的度分布也比较接近泊松分布。Waxman网络模型与ER随机图模型类似，也是先假设节点规模，再以一定的概率决定节点间是否存在连接。BA无标度网络模型是一种用来解释复杂网络的生长型无尺度模型，指的是该网络上节点的度符合幂指数为3的幂律分布，并且赋予该网络一定量的初始节点，而后不断有新的节点加入，其包含2个重要的概念：增长(Growth)和链接倾向(Preferential Attachment)，二者均在现实世界中普遍存在。前者认为网络节点的数量随着时间增长而增长，后者认为如果一个节点所承担的链接任务越多，那么在新链接建立的过程中，该节点就更可能参与新链接，即节点的度越高，其获取新链接的能力越强[27]。BA无标度模型基于真实大型网络数据提出，因此本文采用BA无标度模型对物理网络进行建模仿真。根据定义，假设BA无标度网络模型初始节点为m0，新节点依次加入，新节点链接到节点i的概率为：

其中，ki代表节点i的度数，j表示已存在的节点的个数。

使用BA无标度模型构建100万个节点的样本，样本平均度为2。节点的度分布如图4所示。

图4 节点度分布

图4中横坐标表示节点度的数值，纵坐标表示样本中节点分布频率。由于样本数量已足够大，因此可以用频率估计概率，即大部分节点的度都集中在1～10之间，这其中大部分节点的度为1。而这也证实了BA无标度模型中的链接倾向概念。

以上说明了BA无标度模型中节点度分布的特殊性，即大量节点的度为1，但是个别节点的度较高。而传统贪婪算法对此并没有区分，在每次迭代中都尝试进行节点度排序。为此本文在算法设计方面做了改进，先对模型数据进行预处理，再使用改进贪婪算法进行迭代，具体步骤如下：

1)获取模型的邻接矩阵。

2)将邻接矩阵进行降维处理，剔除全部度为1的节点和与之相连的边，得到处理后的稀疏矩阵，此时经处理后的稀疏矩阵规模相比初始矩阵已经大大缩减。

3)对稀疏矩阵进行压缩、求解，得到节点度排序。

4)运行贪婪算法求解最小点覆盖。

5)在初始邻接矩阵中删去最小点覆盖集合和与之相连的边，再进行迭代排序，一次即可获得全部最小点覆盖集合。

后续实验证实，该场景中优化排序的时间复杂度仅为O(n)，具备良好的扩展性。

3.2.3 方案对比

实际物理网络测量中，决定节点是否为测量节点的因素除了度数之外，还应考虑节点本身的硬件条件。定义节点m权重如下：

其中：α、β、γ为参数对应的动态权重，可根据需要进行调整；Dm表示节点m的度数；Bm表示节点m的带宽因子，用节点间的带宽表示；Lm表示节点m的负载因子，用来表示节点的综合负载情况，为节点机器CPU占用率(pc)、内存利用率(pm)与磁盘利用率(ph)等因素加权表示，且：

Lm=pcm+pmn+phk,m+n+k=1

其中，m、n、k为参数对应的动态权重，可根据需要进行调整。

由于前述2种方案对算法求解速度有了较大提高，算法求解时可提供多套方案进行备选。本文定义了方案评价算法，能够对方案选择提供参考依据。

4 实验验证

4.1 具体实现

按照本文的设计，在实验平台运行改进的贪婪算法及评价方案，并在最后展示最终算法与原始算法的性能对比。

4.2 实验环境

硬件环境：台式计算机(Intel i7-8700K, 32 GB RAM, 1 TB SSD)及其相应配件。软件环境：Windows 10 64位平台，Python 3.7.6。本文所属实验均在相同硬件及软件环境下完成，下面分别进行说明。

4.2.1 迭代周期优化

使用生成节点数为5000的BA无标度网络模型，横向对比迭代次数p为1、5、10时，算法的求解速度不断加快。通过不同的迭代次数p，说明迭代次数的改进对于效率的影响程度。实验结果见表1。

表1 迭代周期与求解速度

从实验数据来看，调大贪婪算法中迭代周期会减小迭代次数，从而加速贪婪算法的求解速度。平均优化程度达到95%以上，但是可能会牺牲一定的求解精度。后续研究方向是寻找能够补偿求解精度的方法。

4.2.2 面向BA无标度网络模型的排序算法优化

使用BA无标度网络模型，分别创建3000、3500、4000、4500和5000个节点规模的网络模型，测试普通排序方法和优化后排序方法在本实验场景中不同规模下的性能差异。A代表普通排序算法，B代表优化后排序算法。实验数据如表2所示。

表2 排序算法优化对比

从实验数据来看，在10组对比项中，改进后的排序算法相对于普通排序算法在求解速度方面有较为明显的进步，取得了预期效果。但尽管如此，特定场景中可能存在更适合的排序算法。后续研究方向是进一步尝试优化其他排序算法在本场景下的效率。

4.2.3 方案选择优化

节点的硬件配置也会对测量节点的部署产生影响。实验假定节点负载分布服从[0.5，1]的均匀分布。α、β、γ、m、n、k均暂定为1/3。求解不同迭代周期下的节点平均度数、平均加权度数等参数，如表3所示，可供决策人员参考。可见随着迭代周期的增加，尽管计算时间在增加，但是节点平均度数和节点加权平均度数均在持续减少，这说明产生了一定比例的冗余节点。因此，实际应用中需要根据场景规模合理决定迭代周期的取值，适当的迭代周期可以在容忍部分冗余的情况下，加速问题的求解。节点负载使用均匀分布建模，可能与实际情况有偏差，有待后续研究。

表3 方案选择优化

5 结束语

本文设计并实现了一种面向名字解析系统测量节点选择求解最小点覆盖的优化方法，从算法迭代周期改进和结合实际场景优化排序算法以及方案评价方面对ICN中NRS前期测量节点的部署进行了研究。实验结果表明，相对于传统贪婪算法，改进后的贪婪算法在求解速度上得到了较大提升，能够达到预期效果。