面向寻路覆盖网节点选取方法

2022-10-17任熠营陈玉冰张立臣

计算机工程与设计 2022年10期

任熠营，陈玉冰，张立臣

(广东工业大学计算机学院，广东广州 510006)

0 引言

5G时代的来临助推工业4.0的快速发展，给互联网底层物理设施带来日益陡增的网络需求压力，从单一数据到多媒体信息传输，信息物理系统(cyber-physical systems,CPS)在其中扮演着重要角色。为满足各式业务的QoS需求，减少对现有网络基础架构的大幅度调整，CPS通信方案之一的覆盖网备受瞩目。覆盖网(overlay network)是一种构建在现有物理网络之上的虚拟网络，可以在不改变现在底层物理网络拓扑架构基础上提供网络服务，提高网络性能。不同覆盖网可以使用相同的物理链路进行数据传输，也可以部署在相同的物理节点上，物理节点的利用率得到大幅度提高，服务更加可靠且容错性高[1]。

覆盖网根据服务场景分为面向寻路、面向内容和面向语义3种类型。其中，面向寻路覆盖网络侧重对路由性能的考量，通过寻找最大化路由性能要求的最优覆盖节点，使用物理链路将相关覆盖节点链接而成最佳覆盖路径，最后经由路径上的覆盖节点对应的真实底层物理节点，将用户自定义的数据从客户端经覆盖节点和路径，转发到接收端。面向寻路的覆盖网路由机制的重点：在底层真实物理节点的映射中，选择若干合适真实物理节点成为覆盖节点进而转发数据。本文重点研究面向寻路覆盖网。

1 相关工作

近年来国内外学者针对智能电网[2]、在线学习[3]、交互式多媒体平台[4]、机器人[5]、商用设备[6]等不同领域面向寻路覆盖网进行了深入研究。但大多数研究都是默认覆盖网已知或者底层物理网络与覆盖网之间为全映射关系的情况，缺乏对覆盖节点选取的研究。

面向寻路覆盖网构建的关键问题在于：如何从底层物理网络的拓扑映射中寻找一组关键节点成为覆盖节点，使得覆盖网中路由路径最优。对此，Rai等[7]基于对偶次梯度下降法提出分布式动态路由算法，算法通过增加覆盖节点本身直接路由和其它覆盖节点的间接路由数量构建覆盖网，实现网络吞吐量最大化；Guan等[8]针对单路径路由面临的局限性，基于空间几何坐标构建了多节点多路径覆盖网，通过寻找相关性较小的路径提高并发链路利用率，降低单路径的负面影响，有效提高了覆盖网多路径传输的效率；陈玉冰等[9]提出基于改进变邻域搜索算法的覆盖网构建方法，算法利用递减式邻域交换改变邻域结构，同时算法抖动方式设置为随机更换初始值，借助目标函数优化覆盖节点集的选取，提高了网络通信效率，降低了算法时间花销；廖怡等[10]针对基于网络测量的覆盖网络问题，提出不完全可测网络环境中覆盖网构建算法，基于网络时延构造树形拓扑结构，算法设置高精度节点加入和低精度加入两种方法，在不同网络拓扑结构模型中获得较高时延伸缩比例。

面向寻路覆盖网节点选择问题已经被验证是NP难题[9]，使用禁忌搜索算法(Tabu search，TS)解决各种NP难题一直是研究的热点。Ark等[11]将遗传算法嵌入TS中，结合中交叉和变异等进化策略，提出基于种群的禁忌搜索算法，用以解决车间调度问题；陆佳炜等[12]针对云计算平台下任务调度问题，提出时间贪心策略改进初始解、结合任务完成总时间等多因素的禁忌搜索算法，缩短了任务调度时间，资源负载更均衡；刘景发等[13]结合邻域启发式布局策略，改进禁忌搜索算法中禁忌对象和终止准则选择策略，解决不等面积动态设施布局干涉约束问题；Amina等[14]在多播路由延迟约束代价最小化问题中，使用边介数改进KMB算法测量给定路径边值，并采用禁忌搜索算法对解进行改进，缩短了网络延迟。以上问题均为NP难题，可见使用禁忌搜索算法解决面向寻路覆盖网节点选取问题具有一定的研究价值。

本文针对面向寻路覆盖网少条件限制、有特定节点数的特点，提出一种改进禁忌搜索算法对覆盖网节点进行选取。算法首先结合A*算法对节点进行预处理，选取最优解作为禁忌搜索算法初始解；然后提出递减式概率化方案对邻域解进行选择，降低算法陷入局部最优的风险；最后通过设置动态禁忌长度，控制禁忌对象存储时间，缩短算法运行时间。通过仿真实验验证了本文算法的可行性。

2 覆盖网构造模型

2.1 覆盖网

覆盖网包括一组根据自身相关性能要求选定的覆盖节点和不同节点按需求组成的覆盖链路，其中覆盖节点为底层真实物理节点映射的虚拟节点，覆盖链路为不同虚拟节点间一条或多条的虚拟链路，相邻覆盖节点路由数据的最终方式则是通过底层真实物理节点。覆盖节点既可以是不同类型客户端节点或终端主机节点，也可以是不同服务器节点，不同的节点都具有一定的功能，例如转发处理和路由数据等。

以图1例，覆盖链路既可以对应物理网络一条物理链路(如覆盖链路D′到B′，对应物理链路D到B)，也可以对应多条物理链路(如覆盖链路D′到A′，对应物理链路D到C再到A，其中C为中继节点)。覆盖网具有自身独立的路由机制，可以根据对覆盖网的自身特定性能要求计算出从终端主机节点到接收端最优的路由路径；在覆盖网中，发送端节点的数据经过自身性能要求计算所得最优路径中的多个覆盖节点逐跳转发传输到接收端节点，而相邻覆盖节点之间的数据传输则由底层真实物理节点组成的底层真实物理路径实现，物理传输的过程由自身特定性能决定，对用户完全透明[15]。

2.2 面向寻路覆盖网模型

本文主要研究面向寻路覆盖网如何选取固定数目覆盖节点组成覆盖路径，使得源节点到目标节点路由数据网络延时最小。为构建基于基础物理设施网络结构的面向寻路覆盖网模型，给出以下定义：

定义1 基础物理设施网络定义为

G=(V,E)

(1)

其中，V表示有E个节点的基础物理设施节点集,E表示基础物理设施节点之间的物理链路连接集。

定义2 定义从源节点到目标节点，由若干覆盖节点和覆盖链路组成覆盖网S

G(S)=(V(S),E(S))

(2)

其中，V(S)表示按要求选定的所有覆盖节点的集合；E(S)表示覆盖链路的集合，覆盖节点集通过不同覆盖链路形成覆盖网G(S)，覆盖节点和物理节点之间为一一映射的关系，不同覆盖链路对应一条或多条底层真实物理链路。

定义3 覆盖网S的最短覆盖路径集合为R(S)∈E(S)，r(S)∈R(S)表示覆盖网S中的一条覆盖路径， |R(S)| 表示覆盖网S中所有覆盖路径数。

(3)

(4)

3 面向寻路覆盖网节点选择方法

文献[9]验证了面向寻路覆盖网构造中覆盖节点的选取是一个NP难题，启发式算法及其衍生算法是目前解决NP难题被使用最多的方法。本文将改进禁忌搜索算法，通过目标函数实现对覆盖节点的选取。

3.1 禁忌搜索算法

一般情况下，设计禁忌搜索算法主要需要考虑以下内容：①初始解和评价函数；②邻域构型和候选解；③禁忌对象和禁忌长度；④禁忌表和藐视(特赦)准则；⑤终止准则。

算法具体步骤如下：

(1)给定算法参数，设置禁忌表长度，随机初始解，同时置空禁忌表；

(2)判断当前解是否满足设定的终止准则？如果是，输出优化之后计算所得的结果；否则进入步骤(3)；

(3)根据设定邻域构型规则，由当前解生成不同数量邻域解，由评价函数通过计算全部邻域解，选择最优邻域解成为候选解；

(4)判断候选解是否满足藐视准则？如果满足藐视准则，忽略候选解自身的禁忌属性，将满足藐视准则的候选解替换为当前解和当前最优解，替换掉最早进入禁忌表的对象，禁忌表中不同禁忌对象的任期全部减一，并且释放禁忌表中任期为0的禁忌对象；否则，在候选解中选择不在禁忌表中的最优解为当前解，并将其替换掉禁忌表中最早进入的禁忌对象，将禁忌表中不同禁忌对象的任期全部减一，释放任期为0的禁忌对象。

(5)转到步骤(2)。

一般情况下，工匠精神主要是指在具体的工作中，工匠们可以对设计具有独特的见解，能够严格的控制质量，并随着时代的发展，可以对相关技术进行积极的完善和革新，保证可以有效提升制作的效果和水平，促进企业的可持续发展。新时期也赋予了工匠精神新的含义。对于工匠精神来说，其是现代精神与传统职业价值有效融合的结果。在现代的社会中，工匠精神除了要具备尊师重教的精神，还应该具备较高的创新精神，保证可以提升工作的高效性，推动企业发展进程。

3.2 改进禁忌搜索算法

禁忌搜索算法作为一种元启发式算法，具有优秀的局部搜索能力，但初始解选取[16]、邻域构型变化[17]以及禁忌长度设置[18]都直接影响算法的搜索效率。为此，本文结合面向寻路覆盖网节点选取问题对禁忌搜索算法提出以下改进：

(1)结合A*算法选取初始解。传统禁忌搜索算法随机选取初始解的方式显著降低了算法在解空间的搜索效率。A*算法作为一种静态路由网中求解最短路径最有效的启发式的图直接搜索算法，算法从初始节点开始，通过对周围节点的评估，选取最优节点进行拓展，直到寻找到目标点，然后由目标点回溯，最终形成完成的全局规划路线。A*算法虽然不一定能寻找到最佳的路径，但能尽可能找到最短路径，并且算法运行速度快，适合作为预处理操作选取初始解。因此，本文使用A*算法对初始解进行选取，降低了禁忌搜索算法对于初始解的强依赖，提高了算法执行速度，克服了禁忌搜索算法从劣解开始搜索而不利于全局的问题。

(2)改进邻域构型以增强搜索能力。邻域构型是从一个给定解到另一个解的规则，邻域解为给定解经过一次变换规则所得，局部搜索过程如何从一个解跳转到另一个解由邻域构型决定，因此，邻域构型的构造方法直接影响局部搜索的算法的效率[18]。常见邻域构型如交换相邻候选节点、将候选解点插入节点集和交换头部或尾部部分节点等，但以上改变邻域构型方案明显不适合面向寻路覆盖网节点选取策略。

因此，本文根据面向寻路覆盖网少条件限制、有特定节点数的特点，提出递减式概率化邻域构建方案，即在有M个节点的禁忌搜索算法邻域变换中，第一次邻域变换中将随机选取N个节点与候选节点进行交换，由目标函数计算每个邻域解的估值，根据估值进行轮盘赌策略概率化选择邻域解成为候选解；第二次邻域交换将交换N-1个节点，重复上述概率化选择，依次递减直至N=1。图2为递减式概率化邻域变换N=3的情况，具体操作为：第一次邻域交换中，随机选取3个覆盖节点与候选节点进行交换，计算交换后每条覆盖路径目标函数估值，然后采用轮盘赌概率化选择邻域解为候选解，判断候选解是否满足藐视准则，更新禁忌表；第二次邻域交换两个覆盖节点，重复上述过程。其中，实心三角形和实心圆形为经过邻域变换后的覆盖节点集合V(S)；空心三角形为表示经过邻域变换后由覆盖节点变成候选节点；空心圆形表示有可能的覆盖节点；实心圆形表示经过邻域变换后由候选节点变成覆盖节点v。概率化选择的优势在于选取邻域解不再直接选取最优解为候选解，而是给予劣解一定的概率被选为候选解，加大搜索范围，避免算法陷入局部最优。

(3)设置动态禁忌长度。禁忌表主要是为了减少算法搜索过程中的反复计算，避免陷入局部最优，禁忌长度是禁忌表中禁忌对象的存储时间长短，禁忌长度太短，搜索容易陷入循环；禁忌长度太长，搜索时间便会变长，所以禁忌长度的优劣直接影响算法效率。前期测试发现，由于路由节点数目远大于覆盖网节点数目，在保证算法结果最优解情况下，禁忌长度设置为L=1.5*[10+N/M] 较为合适，其中N为基础物理设施节点数，M为覆盖网节点数；同时将用前缀树代替禁忌表对禁忌对象进行存储。本文取L为禁忌长度。图3为改进禁忌搜索算法流程图。

4 仿真实验分析

4.1 实验环境

实验采用MATLAB随机生成5个仿真数据集，物理节点分别为200个、1000个、2000个、3000个和5000个，对应构建覆盖节点数为k(k=3、5、7、10、15、20、30)的面向寻路覆盖网。采用节点间的度量作为节点间通信延时度，节点延时主要模拟实际运行中节点产生物理延误。实验运行50次，最终实验结果取均值。将在算法时间和网络延时两方面，分别对比本文算法、遗传算法(genetic algorithm，GA)、模拟退火算法(simulated annealing algorithm，SA)以及禁忌搜索算法(TS)。

实验采用64位的Ubuntu 16.04 LTS操作系统，硬件配置为GeForce GTX 1080 Ti，CPU为12核的Intel Core i7-7800X，15.4 GB内存。

4.2 实验结果

改进禁忌搜索算法实验中，将对比5个数据集在不同覆盖节点中算法时间和网络延时。仿真数据集将以无向加权图的形式模拟底层物理节点拓扑结构，根据目标函数P(S)计算最优解，寻找目标覆盖节点，最终组成最优覆盖路径。路由数据将从源节点发送出去，经由覆盖网中覆盖节点到达目标节点。

本文算法网络延时如图4所示，随着覆盖节点数的增加，网络延时稳定下降；当覆盖节点数从3个增加到30个，网络延时下降至少40%。

本文算法运行时间如图5所示，随着覆盖节点的增加，算法运行时间明显变长。当物理节点数为200时，算法时间稳定在3 s以下；当物理节点数大于3000时，算法时间维持在50 s以上。当覆盖节点个数在15个以内时，算法运行时间增长缓慢。

4.3 算法对比

算法对比实验中，将对比遗传算法、禁忌搜索算法和本文算法在1000个物理节点数据集中，覆盖节点为k(k=3、5、7、10、15、20、30)的情况。

遗传算法通过模拟自然界生物进化中基因选择、交叉等过程，挑选优秀个体遗传给下一代，实现优胜劣汰，具有优秀的全局搜索能力，能很大程度避免陷入局部最优；模拟退火算法借助固体退火原理，从较优解开始，结合概率突破特征在解空间中随机寻找目标函数的全局最优解；禁忌搜索算法从一个选定初始解出发，通过对邻域构型启发式布局寻找最优邻居，直至局部最优。

由图6各算法网络延时和图7各算法运行时间图可知，遗传算法在不同的节点中网络延时低于禁忌搜索算法，但算法时间花销高于禁忌搜索算法，原因在于遗传算法通过优秀个体改良解集，不断提高优势解适应度，指导优化的搜索空间，自适应调整算法搜索方向，增强了全局搜索能力，因此网络延时整体较低，但随着节点数的增加，遗传算子中选择、交叉和变异等操作将消耗大量算法运行时间，而且会有早熟收敛问题的发生；禁忌搜索算法根据候选解对比禁忌表即可确定最优解，算法运行时间相对遗传算法有所减少，但每次仅寻找最优邻居使得算法容易陷入局部最优，因此网络延时高于遗传算法；相较于遗传算法全局寻优和禁忌搜索算法局部寻优，模拟退火算法在局部最优状态下概率突破，趋于全局最优，而且局部搜索策略也加快了算法执行速度，因此网络延时低于禁忌搜索算法，运行时间快于遗传算法，但模拟退火算法对整个解空间状态并不了解，搜索效率不高。

本文算法针对禁忌搜索算法容易陷入局部最优的缺陷，根据覆盖网特点，采用递减式交换候选节点、概率化的寻优方法改进邻域构型，以一定的方式接受劣解，降低陷入局部最优风险。由图6可知，本文算法网络延时在节点较少时微劣于遗传算法，原因在于节点较少时覆盖节点的选择相对局限；随着覆盖节点的选择更加多样，本文算法显著优于遗传算法、模拟退火算法和禁忌搜索算法，侧面说明本文算法跳出了局部最优，全局寻优能力得到增强。

在算法执行速度方面，本文通过改进初始解获取方式，使算法以较优的解开始迭代，有利于提前达到终止条件中对象最大记忆频率，即当最佳目标值频率达到阈值则认定为全局最优解；同时动态设置禁忌表长度，进一步加快达到目标迭代数的时间，禁忌对象以前缀树形式存储，方便对禁忌对象的快速查找，相较于表格形式存储，前缀树在大规模数据中将是不同量级的提升。因此，如图7所示，本文算法运行时间均远低于对比算法。