基于节点复合特性的端-边协同网络生成算法

张冰雪, 李希胜,2,*, 尤 佳, 宋委任

(1. 北京科技大学自动化学院, 北京 100083; 2. 北京市工业波谱成像工程技术研究中心, 北京 100083)

0 引 言

近年来,随着数据量剧增,对数据传输时效要求提高,采用云计算进行数据处理和分析的弊端逐渐显现,虽然大型云计算服务器对大量数据信息能够实现快速、准确的处理和分析,但云服务器通常设置在距离用户较远的地方,在传输数据的过程中会造成传输时间的延迟,同时在传输过程中会消耗较多的能源。因此,边缘计算的概念被提出[1],边缘计算通过在距离设备较近的位置上放置边缘节点,利用边缘节点上的边缘服务器对计算任务进行处理和分析。边缘计算操作的对象包括来自于云服务的下行数据和来自于万物互联的上行数据。边缘计算方案的使用能够缓解云计算中心的计算压力,解决云计算中存在的响应时间长、数据传输带宽成本高以及数据安全性差和隐私保护性差等问题[2],有效地提高数据的传输效率并降低传输能耗,在对传输时间要求较高的应用场景中具有较好的应用效果。

随着智能化与物联网的广泛应用,越来越多的城市交通系统中加入了智慧交通网络,面对复杂的交通路况,包括交通堵塞、交通事故等问题,需要能够快速地收集、提取和利用有效信息并及时进行分析、处理和反馈。因此,提高计算能力、减少数据传输过程中的通信时延是智慧交通网络系统研究的一个重要课题[3]。在车联网和智慧交通系统中,有大量终端设备和相关数据信息,利用边缘计算系统能够提供可靠的计算能力,而相对云计算系统可以减少端端通信延时、减少请求时间,节省网络带宽资源,更好地实时监测、快速识别及分析处理,针对交通拥堵、交通事故以及其他复杂交通状况等问题进行更高效的处理解决[4-5]。数据和任务在智慧交通网络系统中通过互连的通信链路实现传输,因此,选择更短距离的传输链路能够有效地缩短数据和任务在网络系统中的通信时间,实现降低时延的目的。

目前,多层复杂网络已常用于对现实系统进行刻画描述的研究之中,在城市交通网络研究中已被广泛应用[6],并在控制科学、计算机科学等领域中也受到了广泛关注[7-8]。多层复杂网络的研究[9]最初来源于单层复杂网络研究[10]。随着研究的深入,单层复杂网络已不能准确地描述现实系统中的网络关系,因此,多层网络的概念出现并被广泛使用、研究。Marceau等[11]基于单层复杂网络模型,提出了在网络间创建连接、实现多层复杂网络模型的建立方式。文献[12]针对5G超密集网络中的网络切片,提出了一个基于复杂网络的管理框架,通过这一框架描述切片网络的拓扑结构。在理论分析基础设施网络的性能方面,随机几何分析法是近年来研究分析使用的主要方法之一[13]。文献[14]设计了一种多层空间随机网络模型,并对电网和道路网络组成的基础设施系统进行了建模测试,这一模型能够很好地估计系统的拓扑特性。文献[15]对随机节点分布和随机计算任务生成的空间随机网络进行了建模,研究移动边缘技术网络的通信和计算等待时间。文献[16]在研究边缘计算网络中的卸载任务问题上设计了随机边缘计算网络模型,在此模型上提出了最大距离可分离编码技术,实现了将任务卸载至边缘节点并执行的目的。文献[17]通过随机概率刻画了多层网络间的关系,并分析了多层复杂网络的特性。文献[18]通过随机连接和按节点度大小择优方法在两个网络间建立连接了构建多层复杂网络模型。在上述研究中,多层网络模型构建以随机几何方法为主,对于节点的特征信息使用较少,没有充分描述节点在网络中的特性信息,在网络的数据、任务传输方面,利用节点特性对网络模型进行优化也是提高整个网络系统通信传输效率、降低时延的一种有效方法。因此,利用节点特性建立网络优化模型也是一个重要的研究内容。文献[19]使用聚类系数和节点中心性两种特性参数对复杂网络链路预测问题进行分析,相对其他只考虑节点度和节点中心性进行链路预测的算法,该方法取得了更好的链路预测效果。文献[20]建立了城市混合交通网络模型,并使用度中心性、聚类系数等多个参数识别混合交通网络中的关键节点,有助于优化混合交通网络中重要节点的资源分配问题。文献[19]和文献[20]为利用节点特性建立协作网络模型的研究提供了很好的思路。

针对以上问题,本文构建了端-边缘协同系统参考架构,以满足智慧交通系统的通信要求。基于复杂网络理论,对端-边缘协同系统模型化,重点研究系统不同层之间进行通信传输的链路连接问题。链路连接问题包括选择协作连接节点以及匹配网络间节点对完成连接。本文考虑节点特性信息对链路连接产生的影响,选择节点聚类系数和介数中心性两种特性描述节点信息,利用两种特性参数相结合的方法获取更全面的节点信息,对于多层网络模型建立和优化有更好的效果,从而实现降低数据任务在网络系统中的传输时延的目的。

1 系统架构与建模

本节考虑智慧交通系统的网络组成,设计了端-边缘协同系统参考架构,介绍系统架构的组成及功能,接下来基于多层复杂网络设计一个端-边缘协同系统协作架构的数学模型,通过模型可以更清晰地描述整个系统层内和层间的连接关系,从而进一步提出协作网络生成算法。

在对数据传输时间有要求的应用系统中,数据处理和分析工作将由边缘节点计算和部分智能设备直接完成。由此,结合边缘计算参考架构[21]设计了端-边缘协同系统,如图1所示。

图1 端-边缘协同系统参考架构Fig.1 End-edge collaborative system reference architecture

协同系统由设备层、边缘层和应用平台组成,以满足用户提出的多样的服务需求。首先,最底层为设备层,包含各种现场传感器、智能设备及其接口,各类设备主要负责各种数据的测量和采集,接口连接现场设备和边缘层,实现数据的通信和传输;其次,中间层为边缘层,由边缘管理器和边缘节点组成,边缘管理器完成资源管理与调度、用户任务分配等工作,边缘节点包含边缘网关、边缘控制器、边缘处理器等,边缘节点完成数据处理及分析工作,并与设备层和应用平台进行互联,实现数据传输;最后,最上层为应用平台,负责收集和显示所有用户的任务请求,能够为边缘层和检测设备下达任务指令。

根据各层节点和设备连接关系,可以得到端-边缘协同系统架构的节点网络图,如图2所示。

图2 端-边缘协同系统节点网络Fig.2 End-edge collaborative system node network

在端-边缘协同系统节点网络中,各层之间的数据传输与通信主要依靠各层的节点进行,由应用平台端节点将控制台的用户需求经边缘节点传输到边缘管理器中,各智能设备和传感器将采集到的数据信息从设备端传输节点传输到边缘节点上,由边缘节点完成数据处理等工作。

在协同系统节点网络中,本文重点关注多层网络间的层间连接关系,关注各层网络的节点特性在链路连接建立中的影响。因此,以系统中应用平台端节点、边缘节点以及设备端传输节点为传输网络的主要组成部分,利用复杂网络对传输网络进行建模,得到如图3所示的三层网络模型。

图3 多层复杂网络图Fig.3 Multilayer complex network diagram

在图3的三层复杂网络中,各点表示传输系统网络每层的节点,各层节点组成集合Ht,部分节点依照系统结构向外与传感器、边缘管理器及系统中心管理控制台相连,这部分不在后续研究问题中涉及,图3中未绘制。每层节点之间用实线表示层内连接关系,层内连接集合表示为Kt,不同层节点之间用虚线表示层间连接关系,层间连接集合表示为Ltr。

2 协作网络模型生成算法

本节基于多层复杂网络模型分析节点特性反映出的网络拓扑信息对网络层间协作连接建立的影响,针对网络模型中任意两个复杂网络之间协作连接的建立提出了一种基于节点复合特性的连接生成算法,建立和优化网络层间连接链路,满足降低数据传输时延、提高网络传输效率的需求。

层间连接的建立包括两个过程,首先在各个复杂网络中选择一定数量的节点作为协作连接点,其次将两个网络中的协作点集合通过一定的匹配方法组成协作点对,在协作点对间建立链路连接,实现两个复杂网络之间的连接及通信传输。

基于上节提出的端-边缘协同系统及多层复杂网络模型,为了满足智慧交通系统中低延时的要求,实现数据在网络间传输延迟的最小化,在多层复杂网络的各层网络之间任意两个节点间的路径距离应最短,即减少节点间最短路径值。本节提出了基于节点复合特性的协作网络模型生成算法。现有的通过随机概率连边和按节点度大小排序择优建立层间连接的方法都没有对节点重要性进行考虑,而重要性更高的节点在整个网络建模中将发挥更重要的作用。在重要程度高的节点上创建层间连接,协作网络间的通信、数据传输更高效。因此,本文通过计算节点特性参数值,将节点特性更突出、在网络中更重要的节点选作协作点。

2.1 网络协作点选择算法

网络协作点选择是在一个复杂网络中选择与其他复杂网络建立协作连接的节点,是协作网络模型建立的第一步。

复杂网络中常用的节点特征描述参数有节点度、聚类系数、节点中心性、平均路径长度等。聚类系数主要反映节点在网络中的局部的密集度信息[22],节点中心性则能够反映节点在整个网络中影响力的重要性[23]。所以,本节基于节点聚类系数和介数中心性两个参数对节点特性进行描述。

节点聚类系数CCi的计算如下:

(1)

式中:k表示节点i的邻居节点数;d表示在节点i的所有k个邻居间的边数。

节点介数中心性bi的计算公式如下:

(2)

式中:n表示网络中的节点总数,n(n-1)/2表示将节点介数中心性标准化;gjl是从节点j到节点l的最短路径总数;gjl(i)是从节点j经过节点i到节点l的最短路径数。

由此,本文基于节点聚类系数和介数中心性定义节点联合参数值φi以反映节点特性。节点i的联合参数值函数φi的定义为

φi=β1CCi+β2bi

(3)

式中:β1、β2分别表示节点聚类系数和介数中心性在节点联合参数值中所占的比例系数,β1+β2=1。

选择两种节点特征信息对节点在网络中的重要性进行描述,能够更好、更全面地描述节点特性。

根据节点联合参数值对网络节点进行排序,通过择优选择算法实现协作点选择。节点联合参数值越大,则该节点的特征性越明显、在整个网络数据传输过程中发挥的重要性越高。择优选择算法能够选择出在整个网络中重要性更大的节点,作为与其他网络建立协作连接的协作点集合。择优选择算法的流程图如图4所示。

图4 择优选择协作点算法流程图Fig.4 Flowchart of Preferential collaboration point algorithm

2.2 网络协作连接建立算法

协作连接建立是指在两个不同复杂网络之间将协作点组对并互相连接的过程,是协作网络模型建立的第二步。

在任意两个复杂网络之间,协作连接的数量反映两个网络之间的协作程度,在一定数量协作连接数量的情况下,协作连接建立问题可转换为两个复杂网络协作点集合之间的匹配问题。匹配理论能够描述互利关系的形成,早期常用于处理经济学问题[24]。近几年,匹配理论也在无线资源管理中实现了应用[25]。双边匹配算法能够利用匹配主体中的偏好信息,将偏好信息转化为满意度,建立匹配模型以解决匹配问题[26-27]。通过计算匹配主体满意度和最大以及两个匹配主体满意度差最小实现模型优化[28]。

本文使用节点聚类系数和介数中心性两种节点特征描述网络中节点的偏好信息,偏好值定义为节点联合参数值的线性相关函数。

(4)

(5)

在式(4)、式(5)中,节点联合参数值较高的协作点具有更高的偏好值,γ1和γ2表示节点联合参数值的系数,反映偏好值的倾向程度。

在智慧交通应用场景中,协作连接建立的重点需要满足降低时延、缩短传输路径的要求,因此,在两个网络间建立连接时,选择节点联合参数值更高且两个节点的联合参数值更相近的协作点为协作点对并创建协作连接,将更能够满足要求。基于此,多目标优化模型要满足两个复杂网络对于对方的节点特征偏好值尽量大,并且两个网络对于对方的节点特征偏好值差异尽量小,建立的优化模型可以表示为

(6)

优化目标的约束条件为每个复杂网络中的协作点与其他协作点之间最多可建立的协作连接数的限制o,以及两个不同复杂网络之间的协作连接总数不超过预设定值N。eik=1表示协作点i和协作点k之间建立连接,eik=0表示协作点i和协作点k之间没有建立连接。

通过线性加权法求解多目标优化模型(6),将多个优化目标进行加权求和,组合成单个目标,得到单目标优化模型:

(7)

(8)

多目标优化模型转化为单目标优化模型后,利用线性规划方法求解可得模型的解,该结果反映的就是网络间节点的匹配与连接关系,通过该解将合适的协作点对连接起来,实现多层网络的构建。

3 仿真测试与分析

基于以上系统建模及提出的算法,本文在Windows系统2.8GHz英特尔Core i7-1165G7、16G内存下通过Matlab 2019a进行编程仿真。系统仿真使用4种典型复杂网络模型来模拟具有不同结构特性的网络,分别为:Erdos-Renyi(ER)随机网络模型[29-30]、Barabasi-Albert(BA)无标度网络模型[31]、Watts-Strogatz(WS)小世界网络模型[22],Newman-Watts(NW)小世界网络模型[32]。

不同网络结构能够代表不同的实际网络需求和功能,以在不同结构的复杂网络之间建立协作连接,证明结合节点多种特征参数生成协作网络的算法的可靠性和有效性。

生成4种典型复杂网络模型的相关参数设置如表1所示。

表1 复杂网络模型参数

通过上述参数设置得到的4个复杂网络的节点聚类系数和介数中心性参数数值如图5、图6所示。

图5 各网络节点聚类系数参数值Fig.5 Parameter value of each network node clustering coefficient

图6 各网络节点介数中心性参数值Fig.6 Parameter value of each network node betweenness centrality

本文所提协作网络生成算法主要以降低系统数据传输时间、提高传输效率为目标。在仿真实验中,假设网络中的数据传输时间与其部署在网络上的链路路径长度成正比,各个节点间的距离相同,根据复杂网络的结构特征对协作网络进行性能分析。因此,网络中各节点到协作点的最短路径反映出系统中各设备和管理控制器将数据、任务传输到其他层时的传输距离和时间。在实验中,网络设置为无权图,各个节点之间都能进行通信传输,所以任意两个节点间的最短路径距离能够反映数据、任务从一个网络的节点传输到另一网络的路径及距离。传输路径越短,数据包传输的速度越快,在传输过程中的时延越低。因此,本文选择最短路径值作为衡量网络间传输性能的指标。

本文使用4种基本复杂网络,即ER随机网络、BA无标度网络、WS小世界网络和NW小世界网络能够组成6种协作网络:ER-BA、ER-WS、ER-NW、BA-WS、BA-NW、WS-NW协作网络。

由图5、图6可以看出,节点聚类系数和介数中心性在不同网络中表现出的差异程度不同,反映了在不同网络中这两个特征参数对节点重要性的影响程度不同。因此,设置不同的β1、β2系数值,也会对协作网络模型的传输性能产生影响。

图7 ER-WS协作网络在不同特征占比情况下的最短路径值分布情况Fig.7 Shortest road value distribution of the ER-WS collaborative network under different features proportion

近年来,网络模型在设计和部署方法上主要以随机几何方法为主,在网络中随机选择节点并在随机节点对之间建立连接,构成协作网络。随机连接法在网络模型构建方面缺少对节点特性的考虑,对系统的数据和任务传输效率有一定的影响。在考虑节点特性构建网络时,不同特性参数反映了节点的不同信息,综合两种节点特征能够更全面地描述节点特性。本文选择节点随机连接法和考虑节点单一特性的聚类系数特性网络生成算法、介数中心性特性网络生成算法作为节点复合特性网络生成算法的对比算法,分析本文算法的优势。

通过仿真实验,4种基础复杂网络通过上述4种方式生成多层协作网络后的节点间最短路径值与节点对数分布情况如图8(a)～图8(f)所示。

图8 各协作网络最短路径值分布情况Fig.8 Shortest road value distribution of each collaborative network

由图8可以看出,在加入节点特性参数作为节点重要性衡量指标后,网络中最短路径值为1或2的节点对明显增多,最短路径值为3及以上的节点对明显减少。同时,相比考虑一种节点特性参数所生成的协作网络模型,本文提出的基于节点复合特性的协作网络模型生成算法在节点间的最短路径上也有进一步的优化效果,低节点间最短路径值的节点对数更多,高节点间最短路径值的节点对数更少。由此,数据和任务在网络间能够通过更短的路径进行传输,实现降低传输时延、提高传输效率的目的,并能够减少传输能耗,获得更好的性能。

文献[33]提出的高速多层网络模型,通过增加度值高的节点平衡了网络间的负载问题,提高了网络的流量容量,提高了网络的传输能力,但未考虑网络间传输链路的选择问题。本文提出的基于节点复合特性的协作网络模型生成算法,优化了网络间的传输链路选择问题,对比于文献[33]更进一步缩短了网络系统数据传输时间,提高了传输效率。文献[34]利用随机几何和排队理论分析了边缘计算网络的通信成功概率,通过降低用户密度和提高边缘服务器密度,提高了网络的通信成功概率,这一方法也能够在一定程度上降低网络平均延迟,但并不适用于固定用户数量和边缘节点数量的系统网络。本文算法对于固定节点数量的多层网络进行层间链路连接上的优化,对比于文献[34]更利于在已确定用户节点和边缘节点数量的网络中降低数据传输时延、提高传输效率。文献[35]提出了基于复杂网络的多层城市增长与优化综合模型,在交通网络构建方面,该模型架构降低了网络建设投资成本,但忽略了交通网络对庞大数据量和降低时延的严苛需求,本文提出的端-边缘协同系统参考架构通过边缘计算系统满足这一需求,对交通网络的构建更加全面。

4 结束语

本文针对时延要求高的智慧交通系统构建了设备端和边缘节点协作运行的端-边协同系统,并基于复杂网络理论对协同系统进行了模型化。对于随机几何方法在网络模型构建方面缺乏节点特性信息使用的问题,提出了基于节点复合特性的协作网络模型生成算法,构建了优化的多层网络系统,实现降低时延、提高系统通信传输效率的目的。算法重点强调节点聚类系数和介数中心性两种特性参数对节点特性的共同影响。节点聚类系数反映了节点在网络局部的密集程度,介数中心性反映了节点在整个网络中的信息传播能力。本文构造了节点联合参数值,将两种特性参数进行了结合,更加全面地反映出各个节点在网络中的重要程度,弥补和改进了随机网络对节点信息描述和使用不足的问题。

本文使用4种典型复杂网络模型进行协作网络构建的仿真,对所提算法进行了验证。仿真结果表明,本文提出的节点复合特性协作网络生成算法与一般随机连接法生成网络以及单独使用节点聚类系数、单独使用介数中心性特征进行协作网络生成的算法相比,通过节点间最短路径值统计结果可以看出,本文算法有效地缩短了整体协作网络的节点间最短路径,因此,数据和任务能够更快地在网络间进行传输,降低传输时延,提高传输效率,节约传输能耗。

本文所提算法在网络层内及层间节点连接距离、节点容量方面仍存在不足,在实际部署的协作网络中,各节点间距离有一定差异,每个节点承载的容量也不完全相同,具有不同的执行任务的能力,这对节点在网络中的重要性也有一定影响,针对以上问题后续将继续开展相关研究。