面向信息物理系统的覆盖网构造方法

陈玉冰，任熠营，卢楚杰，张立臣

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

1 引 言

信息物理系统(Cyber-Physical Systems，CPS)与物联网(Internet of Things，IoT)的主要特点之一是实时交互.实现CPS的实时交互依赖于多个IoT系统的协同作用，因此网络通信的质量直接影响CPS的性能和行为.在某些情况下(例如监视物理基础架构或控制生产活动)，这些系统使用大型网络基础架构来支持其组件之间的通信和协调[1].随着强大的通信基础设施的发展，我们对世界的认识和影响不断地提高，工业4.0推进了CPS与通信技术和计算技术的紧密集合，已广泛应用于工业控制、环境监测、智能医疗、智能交通、智能电网、智慧城市、军事侦察、航空航天等领域.Mohebbi等人[2]详细讨论了水基础设施、交通和网络基础设施3种不同类型的CPS系统在智慧和互联的城市中对网络、物理和社会的相互依赖关系.Zhang等人[3]指出将信息物理基础设施应用于地理空间传感器网络，革命性地构造了地理空间传感器网络，是万维网上一个新的网络物理时空信息基础设施.Yao等人[4]给出了工业4.0基于IoT与CPS的智慧制造系统架构，其中网络空间是指下一代网络基础设施，通信网络是指连接网络空间与现实世界的中间部分.

CPS的网络通信方案通常有3种：利用现有的因特网、创建一个新的网络和构造一个覆盖网络.覆盖网络可以忽略下层网络的路由路径，在上层网络中利用因特网将节点通过虚拟的逻辑链接，控制消息需要经过的覆盖节点而完成端到端的数据传输，所以面向物理设施和网络环境复杂的智能CPS，利用覆盖网可以在不改变现有的物理设备拓扑结构的基础上提高网络的通信性能，满足系统实时交互的需求.

近年来国内外学者提出了一些基于覆盖网的路由策略方法.本文针对CPS覆盖网的构造，提出一种智能优化选择方法.利用目标函数在覆盖网的候选节点集中选择有固定数量的覆盖节点集，使得源节点到目标节点的路径最优，该方法有效降低了网络延时，提高了网络的性能.

早在二十世纪九十年代，Savage等人[5]证明了覆盖网络中覆盖路由能够在不需要进一步先进设备的情况下降低端到端的延迟.Mayer等人[6]开发了一个基于Web标准和协议的物联网基础设施分层架构，提出可伸缩的查找机制.但这方法是基于传统的路由技术来构造覆盖网，对于现代化智能网络具有一定的滞后性.Wan等人[7]提出了一种局部搜索算法布置覆盖节点集，并给出覆盖节点放置问题是NP完全问题的形式化证明.但是单一的局部搜算法容易令结果陷入局部最优值.Guan等人[8]从拥塞和容错能力方面考虑，提出了一种基于空间几何的多路径路由方法，减弱了单路径路由的负面影响，提高了网络并发链路的利用率，但未指出该路由路径是否为覆盖网络中的最短路径.Rai等人[9]开发了一种基于经典的对偶次梯度下降方法的分布式动态路由算法，基于网络的吞吐量解决了覆盖网络中最佳路由的问题.张青等人[10]面向云制造搭建覆盖网解决了容器集成的问题，但此覆盖网仅能应用在节点集极少的情况，并不适用于现代的大型智能信息物理系统网络.蔡沂[11]面向云制造提出基于REST架构的3层P2P覆盖网，解决了异构IoT子网的兼容通信、网络资源的整合和虚拟组实体复用的问题，但没有提出面向大型网络的覆盖网问题的解决方案.赵俊等人[12]基于软件定义网络提出隧道协议映射的覆盖网.大多数覆盖网通信的研究是基于覆盖网已知的情况下对覆盖路由的研究，缺乏对覆盖网覆盖节点构造研究.

CPS有着各种各样的系统，小至心脏起搏器，大如大型分布式网络(如智能电网、电力基础设施网络等).针对CPS的基础设施网络通信，面向CPS的覆盖网构造方法的关键问题是如何在基础设备中选择一组关键节点作为覆盖节点，使得网络的路由路径最优.此类问题已被证明是NP难题.应用变邻域搜索算法解决优化各类NP难题一直是国内外研究的热点.Hansen等人[13]指出了变邻域搜索算法对于大型的数据集的组合优化具有良好的效果.Ramli[14]等人基于智能电网提出了一种变量归一化的改进VNS方法解决大规模并行调度的优化问题.Brimbery[15]等人提出了嵌套的VNS框架，可以在VNS中嵌套一个VNS或者其他的局部搜索算法，但增加了算法的时间复杂度.Olender[16]等人针对离散有序的中值问题引入了正则化的概念，提出了一种修正的VNS方法.文献[17，18]通过提出不同的领域结构和抖动过程改进了VNS.可见，运用变邻域搜索算法解决信息物理系统和物联网的相关问题具有一定的研究价值.

考虑到CPS智能化、实时协同等特点，传统的覆盖网构造方法已经无法满足日益增长的通信需求，本文提出了基于改进的变邻域搜索算法的智能优化算法覆盖节点选择方法，通过修改变邻域搜索算法的领域算子和抖动过程，将邻域算子设计为一种递减式的邻域交换和将抖动方式设为随机更换初始值，以使算法跳出局部最优值的限制，然后利用目标函数优化了覆盖节点集的选择策略，从而优化网络的通信延时，并通过仿真实验验证了所提算法的有效性.

2 覆盖网络构造模型

为构造面向信息系统基于客户端-服务器的基础设施网络覆盖网络模型，给出以下定义：

定义1.将底层物理网络定义为图：

G=(V,E)

(1)

其中V表示为有N个节点的基础设施节点集，E表示为节点V间的链路连接.在此，链路E的权重e表示为网络通信的延迟.

定义2.将客户端(C)-服务器(S)对的集合，即网络中源节点(Client)和目标节点(Server)对定义为：

C=V×V

(2)

定义3.将I⊆V表示为有可能的候选的覆盖节点集，0⊆I表示所选的覆盖节点集，该覆盖节点集的数量为k.

定义4.定义函数L(c,s)表示客户端节点和服务器节点相连，其中每个客户端节点c∈C都有相应要路由的目标节点s∈S.则覆盖节点集通过逻辑链接形成覆盖网，每个源节点c∈C都可以通过覆盖网中的覆盖节点集O来路由数据到对应的目标节点s∈S.

定义5.假设从客户端c到服务器s的L(c,s)最短路径为(c,o1,o2…，ok,s)，则定义：

(3)

定义6.当覆盖节点的最短路径大于或者等于两节点间的路径时，令式(3)为：

(4)

其中当时C=S，则令：

(5)

定义7.综上，可将覆盖网节点的选择问题定义为在给定覆盖节点数k的情况下，找出最短的路由路径节点集O.因此，目标函数为：

(6)

3 覆盖节点的选择方法

文献[7]证明了覆盖网络中节点集的选择是一个NP难题，解决NP难题常用的方法有近似算法和启发式算法.本文提出了改进的变邻域搜索算法通过不同的邻域结构对复杂网络进行交替搜索，降低解集陷入局部最优的可能性，优化了覆盖节点集的选择方法，改进了网络的通信延迟问题.

3.1 变邻域搜索算法

变邻域搜索算法(Variable Neighborhood Search，VNS)[13]是局部搜索算法的扩展，通过系统地改变邻域来探索求解空间，既在局部搜索算法内，也在每次扰动期内摆脱局部最优.与其他基于局部搜索方法的元启发式算法不同的是VNS不局限于仅在一条轨迹上搜索最优值，而是探索当前现有解决方案的距离不断增加的邻域，当且仅当结果得到改进时，才从该解决方案跳到新的解决方案.VNS有两个主要的步骤：Shaking和变邻域下降(Variable Neighborhood Descent，VND).Shaking是一个抖动阶段，用于摆脱局部最优；VND以确定的方法系统地变化领域结构，探索几个不同的邻域直到所有考虑的邻域找到局部最优解.VNS伪代码如下：

算法：VNS

初始化：给定一组邻域结构N_k,k=1,…,kmax；给定初始解x；设定停

止条件.

REPEAT

k=1;

REPEAT

SHAKING：在x的第k个邻域结构中随机生成x′(x′∈N_k(x));

LOCAL SEARCH BY VND：在x′的邻域结构N_i(x′)中找到最优解x′′;

IFf(x′′)

ELSEk=k+1;

UNTILk>kmax

UNTLI STOPPING CONDITION

RETURNx

3.2 改进的变邻域搜索算法

上述研究对VNS的改进普遍适用于有多变量、多条件限制、无特定节点数和有特定访问顺序节点离散中值问题或哈密顿中值问题的优化，不适用于覆盖网节点集少变量、少条件限制、有特定节点数和无序的优化问题.因此，本文基于面向信息物理系统的覆盖网节点的特点对VNS做出了以下改进：

1)VND中常见的多种不同的领域结构，如交换已被选候选节点的顺序；随机选取两个未被选择的候选节点插入到已被选择的节点集中等邻域结构明显不适合解决覆盖网覆盖节点选择的策略.本文提出了一种递减式交换邻域结构方法，如图1，当有k个节点在VND变换邻域的过程时，第1次变换邻域为随机选取i个节点与候选节点集交换，第2次变换邻域随机选取i-1个节点集交换，依次递减直到i为1(2≤i≤k).图1中实心三角形与实心圆形表示经过一次邻域变换后新的所选覆盖节点集O；空心圆形表示有可能的覆盖节点集I；空心三角形表示经过邻域交换后的由覆盖节点变为候选节点；实心圆形表示经过邻域交换后由候选节点变为覆盖节点；虚线表示为节点交换.

图1 递减式邻域交换Fig.1 Descending exchange neighborhood

2)Shaking函数则为随机选取解x，既保证了VNS能跳出局部路径寻找新路径的最优解，避免了循环，又使算法更加简单高效.改进的VNS通过Shaking跳到另一个邻域中寻找局部最优值.

考虑到VND中邻域结构越多，算法的时间花销会越大并且对结果的提高没有明显帮助，本文中只对VND进行了两次邻域结构变化，即i=2.这里将VNS的结束条件设为连续抖动5次邻域后均无更新最优解则输出结果，即k_max=5.改进后的VNS算法流程见图2.

图2 算法流程Fig.2 Algorithm flow

4 实验分析

4.1 实验环境

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

实验使用了10个物理网络节点大小不同的数据集，分别对构造具有k(k=1,…,10)个覆盖节点集的覆盖网络选择进行了100次实验，最后实验结果取平均值.并将本文提出的改进变邻域搜索算法结果与遗传算法和混合算法对比.实验结果表明，改进变邻域算法在实验结果和时间花销均优于其余两种优化算法.

4.2 实验结果

实验的数据集为基于MATLAB随机生成的大小不同的节点集，采用两节点间的度量空间作为网络通信延时度量.部分实验结果见图3，忽略底层物理节点的拓扑结构，根据目标函数选出覆盖节点集，该覆盖节点集优化了底层物理网络的通信延时.当源节点向目标节点路由数据时，先由源节点路由到覆盖节点，然后在覆盖网上通过逻辑链接将数据包传输到目标节点.通过覆盖网路由数据可以有效减少延迟，提高通信效率.

图3 构造覆盖网Fig.3 Building overlay networks

实验结果见图4，随着覆盖节点数的增加，网络延时降低.当k≤4时，网络延时变化相对较明显，当k≥5时，网络延时变化变缓.

图4 改进的变邻域搜索算法结果Fig.4 Improved VNS result

图5表明，随着物理网络节点数的增加和覆盖节点的增加，算法的时间花销增加.当k≤4时，时间花销增加明显；当k≥5时，节点数<500的时间花销增加不明显.特别的，k=5和k=6时，时间花销基本相等.

图5 时间花销Fig.5 Time cost

对于所提出的算法，因为存在随机的过程，所以每次得到的结果会有所波动.表1给出了当覆盖节点k=5时不同数据集每100次迭代测试的平均值、第95个百分位数和95%置信区间，实验结果显示算法的结果仅在很小的范围内波动，根据中心极限定理，95%置信区间存在合理性.因此，改进的变邻域搜索算法是稳定的.

表1 算法的稳定性Table 1 Stability of improved VNS

4.3 算法对比

局部搜索算法是从一个初始解的邻域解空间中选择一个最好的邻居解直至局部解最优；遗传算法是改进的局部搜索算法之一，通过模拟生物自然进化的过程搜索最优解；改进的变邻域搜索算法跳出了局部搜索算法的局限，通过改变邻域结构改变搜索空间，减少算法结果陷入局部最优解的可能.这3种优化算法的结果均依赖于初始解的选择和邻域结构的定义，初始解的好坏是决定算法结果好坏的关键因素之一.混合算法是由两种优化算法组合而成，先通过遗传算法得到局部最优解，然后再将该解作为局部搜索算法的初始解再次进行优化得到该算法的最优解.

将遗传算法和混合算法与本文提出的改进变邻域搜索算法优化覆盖节点集的选择作对比，实验结果见图6.固定覆盖节点数k=5，变邻域搜索算法和混合算法的网络延时基本相同，变邻域搜索算法的结果略优于混合算法.遗传算法的结果无论物理网络节点数大小均差于其它两种算法.特别地当网络节点数偏大时，遗传算法的结果显著差于其他两种算法.

图6 k=5,算法结果对比Fig.6 k=5,Algorithm results comparison图7 k=5,时间花销对比Fig.7 k=5,Time cost comparison

图7是当覆盖节点数k=5时，3种算法的时间花销对比.从图中可知，随着数据集变大，遗传算法和混合算法所需的时间花销显著增加，改进的变邻域搜索算法的时间花销远低于遗传算法和混合算法.实验结果表明，改进变邻域搜索算法在覆盖网节点集选择的应用是3种算法中最优的.

5 结 论

本文将智能优化算法应用于面向信息物理系统的基础设施的覆盖网构造方法，提出了改进的变邻域搜索算法，通过不同邻域结构和随机抖动的方式，使覆盖节点集跳出局部搜索的局限，进而优化结果.给出实验结果平均值及其置信区间，证明了该算法的稳定性.实验表明所提方法有利于网络通信的优化，所提算法相较于遗传算法和混合算法，在实验结果方面明显优于遗传算法，略优于混合算法，时间花销方面显著优于遗传算法和混合算法.