基于節(jié)點(diǎn)復(fù)合特性的端-邊協(xié)同網(wǎng)絡(luò)生成算法

張冰雪, 李希勝,2,*, 尤 佳, 宋委任

(1. 北京科技大學(xué)自動(dòng)化學(xué)院, 北京 100083; 2. 北京市工業(yè)波譜成像工程技術(shù)研究中心, 北京 100083)

0 引 言

近年來,隨著數(shù)據(jù)量劇增,對(duì)數(shù)據(jù)傳輸時(shí)效要求提高,采用云計(jì)算進(jìn)行數(shù)據(jù)處理和分析的弊端逐漸顯現(xiàn),雖然大型云計(jì)算服務(wù)器對(duì)大量數(shù)據(jù)信息能夠?qū)崿F(xiàn)快速、準(zhǔn)確的處理和分析,但云服務(wù)器通常設(shè)置在距離用戶較遠(yuǎn)的地方,在傳輸數(shù)據(jù)的過程中會(huì)造成傳輸時(shí)間的延遲,同時(shí)在傳輸過程中會(huì)消耗較多的能源。因此,邊緣計(jì)算的概念被提出[1],邊緣計(jì)算通過在距離設(shè)備較近的位置上放置邊緣節(jié)點(diǎn),利用邊緣節(jié)點(diǎn)上的邊緣服務(wù)器對(duì)計(jì)算任務(wù)進(jìn)行處理和分析。邊緣計(jì)算操作的對(duì)象包括來自于云服務(wù)的下行數(shù)據(jù)和來自于萬物互聯(lián)的上行數(shù)據(jù)。邊緣計(jì)算方案的使用能夠緩解云計(jì)算中心的計(jì)算壓力,解決云計(jì)算中存在的響應(yīng)時(shí)間長、數(shù)據(jù)傳輸帶寬成本高以及數(shù)據(jù)安全性差和隱私保護(hù)性差等問題[2],有效地提高數(shù)據(jù)的傳輸效率并降低傳輸能耗,在對(duì)傳輸時(shí)間要求較高的應(yīng)用場景中具有較好的應(yīng)用效果。

隨著智能化與物聯(lián)網(wǎng)的廣泛應(yīng)用,越來越多的城市交通系統(tǒng)中加入了智慧交通網(wǎng)絡(luò),面對(duì)復(fù)雜的交通路況,包括交通堵塞、交通事故等問題,需要能夠快速地收集、提取和利用有效信息并及時(shí)進(jìn)行分析、處理和反饋。因此,提高計(jì)算能力、減少數(shù)據(jù)傳輸過程中的通信時(shí)延是智慧交通網(wǎng)絡(luò)系統(tǒng)研究的一個(gè)重要課題[3]。在車聯(lián)網(wǎng)和智慧交通系統(tǒng)中,有大量終端設(shè)備和相關(guān)數(shù)據(jù)信息,利用邊緣計(jì)算系統(tǒng)能夠提供可靠的計(jì)算能力,而相對(duì)云計(jì)算系統(tǒng)可以減少端端通信延時(shí)、減少請(qǐng)求時(shí)間,節(jié)省網(wǎng)絡(luò)帶寬資源,更好地實(shí)時(shí)監(jiān)測、快速識(shí)別及分析處理,針對(duì)交通擁堵、交通事故以及其他復(fù)雜交通狀況等問題進(jìn)行更高效的處理解決[4-5]。數(shù)據(jù)和任務(wù)在智慧交通網(wǎng)絡(luò)系統(tǒng)中通過互連的通信鏈路實(shí)現(xiàn)傳輸,因此,選擇更短距離的傳輸鏈路能夠有效地縮短數(shù)據(jù)和任務(wù)在網(wǎng)絡(luò)系統(tǒng)中的通信時(shí)間,實(shí)現(xiàn)降低時(shí)延的目的。

目前,多層復(fù)雜網(wǎng)絡(luò)已常用于對(duì)現(xiàn)實(shí)系統(tǒng)進(jìn)行刻畫描述的研究之中,在城市交通網(wǎng)絡(luò)研究中已被廣泛應(yīng)用[6],并在控制科學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域中也受到了廣泛關(guān)注[7-8]。多層復(fù)雜網(wǎng)絡(luò)的研究[9]最初來源于單層復(fù)雜網(wǎng)絡(luò)研究[10]。隨著研究的深入,單層復(fù)雜網(wǎng)絡(luò)已不能準(zhǔn)確地描述現(xiàn)實(shí)系統(tǒng)中的網(wǎng)絡(luò)關(guān)系,因此,多層網(wǎng)絡(luò)的概念出現(xiàn)并被廣泛使用、研究。Marceau等[11]基于單層復(fù)雜網(wǎng)絡(luò)模型,提出了在網(wǎng)絡(luò)間創(chuàng)建連接、實(shí)現(xiàn)多層復(fù)雜網(wǎng)絡(luò)模型的建立方式。文獻(xiàn)[12]針對(duì)5G超密集網(wǎng)絡(luò)中的網(wǎng)絡(luò)切片,提出了一個(gè)基于復(fù)雜網(wǎng)絡(luò)的管理框架,通過這一框架描述切片網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。在理論分析基礎(chǔ)設(shè)施網(wǎng)絡(luò)的性能方面,隨機(jī)幾何分析法是近年來研究分析使用的主要方法之一[13]。文獻(xiàn)[14]設(shè)計(jì)了一種多層空間隨機(jī)網(wǎng)絡(luò)模型,并對(duì)電網(wǎng)和道路網(wǎng)絡(luò)組成的基礎(chǔ)設(shè)施系統(tǒng)進(jìn)行了建模測試,這一模型能夠很好地估計(jì)系統(tǒng)的拓?fù)涮匦?。文獻(xiàn)[15]對(duì)隨機(jī)節(jié)點(diǎn)分布和隨機(jī)計(jì)算任務(wù)生成的空間隨機(jī)網(wǎng)絡(luò)進(jìn)行了建模,研究移動(dòng)邊緣技術(shù)網(wǎng)絡(luò)的通信和計(jì)算等待時(shí)間。文獻(xiàn)[16]在研究邊緣計(jì)算網(wǎng)絡(luò)中的卸載任務(wù)問題上設(shè)計(jì)了隨機(jī)邊緣計(jì)算網(wǎng)絡(luò)模型,在此模型上提出了最大距離可分離編碼技術(shù),實(shí)現(xiàn)了將任務(wù)卸載至邊緣節(jié)點(diǎn)并執(zhí)行的目的。文獻(xiàn)[17]通過隨機(jī)概率刻畫了多層網(wǎng)絡(luò)間的關(guān)系,并分析了多層復(fù)雜網(wǎng)絡(luò)的特性。文獻(xiàn)[18]通過隨機(jī)連接和按節(jié)點(diǎn)度大小擇優(yōu)方法在兩個(gè)網(wǎng)絡(luò)間建立連接了構(gòu)建多層復(fù)雜網(wǎng)絡(luò)模型。在上述研究中,多層網(wǎng)絡(luò)模型構(gòu)建以隨機(jī)幾何方法為主,對(duì)于節(jié)點(diǎn)的特征信息使用較少,沒有充分描述節(jié)點(diǎn)在網(wǎng)絡(luò)中的特性信息,在網(wǎng)絡(luò)的數(shù)據(jù)、任務(wù)傳輸方面,利用節(jié)點(diǎn)特性對(duì)網(wǎng)絡(luò)模型進(jìn)行優(yōu)化也是提高整個(gè)網(wǎng)絡(luò)系統(tǒng)通信傳輸效率、降低時(shí)延的一種有效方法。因此,利用節(jié)點(diǎn)特性建立網(wǎng)絡(luò)優(yōu)化模型也是一個(gè)重要的研究內(nèi)容。文獻(xiàn)[19]使用聚類系數(shù)和節(jié)點(diǎn)中心性兩種特性參數(shù)對(duì)復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測問題進(jìn)行分析,相對(duì)其他只考慮節(jié)點(diǎn)度和節(jié)點(diǎn)中心性進(jìn)行鏈路預(yù)測的算法,該方法取得了更好的鏈路預(yù)測效果。文獻(xiàn)[20]建立了城市混合交通網(wǎng)絡(luò)模型,并使用度中心性、聚類系數(shù)等多個(gè)參數(shù)識(shí)別混合交通網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn),有助于優(yōu)化混合交通網(wǎng)絡(luò)中重要節(jié)點(diǎn)的資源分配問題。文獻(xiàn)[19]和文獻(xiàn)[20]為利用節(jié)點(diǎn)特性建立協(xié)作網(wǎng)絡(luò)模型的研究提供了很好的思路。

針對(duì)以上問題,本文構(gòu)建了端-邊緣協(xié)同系統(tǒng)參考架構(gòu),以滿足智慧交通系統(tǒng)的通信要求?；趶?fù)雜網(wǎng)絡(luò)理論,對(duì)端-邊緣協(xié)同系統(tǒng)模型化,重點(diǎn)研究系統(tǒng)不同層之間進(jìn)行通信傳輸?shù)逆溌愤B接問題。鏈路連接問題包括選擇協(xié)作連接節(jié)點(diǎn)以及匹配網(wǎng)絡(luò)間節(jié)點(diǎn)對(duì)完成連接。本文考慮節(jié)點(diǎn)特性信息對(duì)鏈路連接產(chǎn)生的影響,選擇節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性兩種特性描述節(jié)點(diǎn)信息,利用兩種特性參數(shù)相結(jié)合的方法獲取更全面的節(jié)點(diǎn)信息,對(duì)于多層網(wǎng)絡(luò)模型建立和優(yōu)化有更好的效果,從而實(shí)現(xiàn)降低數(shù)據(jù)任務(wù)在網(wǎng)絡(luò)系統(tǒng)中的傳輸時(shí)延的目的。

1 系統(tǒng)架構(gòu)與建模

本節(jié)考慮智慧交通系統(tǒng)的網(wǎng)絡(luò)組成,設(shè)計(jì)了端-邊緣協(xié)同系統(tǒng)參考架構(gòu),介紹系統(tǒng)架構(gòu)的組成及功能,接下來基于多層復(fù)雜網(wǎng)絡(luò)設(shè)計(jì)一個(gè)端-邊緣協(xié)同系統(tǒng)協(xié)作架構(gòu)的數(shù)學(xué)模型,通過模型可以更清晰地描述整個(gè)系統(tǒng)層內(nèi)和層間的連接關(guān)系,從而進(jìn)一步提出協(xié)作網(wǎng)絡(luò)生成算法。

在對(duì)數(shù)據(jù)傳輸時(shí)間有要求的應(yīng)用系統(tǒng)中,數(shù)據(jù)處理和分析工作將由邊緣節(jié)點(diǎn)計(jì)算和部分智能設(shè)備直接完成。由此,結(jié)合邊緣計(jì)算參考架構(gòu)[21]設(shè)計(jì)了端-邊緣協(xié)同系統(tǒng),如圖1所示。

圖1 端-邊緣協(xié)同系統(tǒng)參考架構(gòu)Fig.1 End-edge collaborative system reference architecture

協(xié)同系統(tǒng)由設(shè)備層、邊緣層和應(yīng)用平臺(tái)組成,以滿足用戶提出的多樣的服務(wù)需求。首先,最底層為設(shè)備層,包含各種現(xiàn)場傳感器、智能設(shè)備及其接口,各類設(shè)備主要負(fù)責(zé)各種數(shù)據(jù)的測量和采集,接口連接現(xiàn)場設(shè)備和邊緣層,實(shí)現(xiàn)數(shù)據(jù)的通信和傳輸;其次,中間層為邊緣層,由邊緣管理器和邊緣節(jié)點(diǎn)組成,邊緣管理器完成資源管理與調(diào)度、用戶任務(wù)分配等工作,邊緣節(jié)點(diǎn)包含邊緣網(wǎng)關(guān)、邊緣控制器、邊緣處理器等,邊緣節(jié)點(diǎn)完成數(shù)據(jù)處理及分析工作,并與設(shè)備層和應(yīng)用平臺(tái)進(jìn)行互聯(lián),實(shí)現(xiàn)數(shù)據(jù)傳輸;最后,最上層為應(yīng)用平臺(tái),負(fù)責(zé)收集和顯示所有用戶的任務(wù)請(qǐng)求,能夠?yàn)檫吘墝雍蜋z測設(shè)備下達(dá)任務(wù)指令。

根據(jù)各層節(jié)點(diǎn)和設(shè)備連接關(guān)系,可以得到端-邊緣協(xié)同系統(tǒng)架構(gòu)的節(jié)點(diǎn)網(wǎng)絡(luò)圖,如圖2所示。

圖2 端-邊緣協(xié)同系統(tǒng)節(jié)點(diǎn)網(wǎng)絡(luò)Fig.2 End-edge collaborative system node network

在端-邊緣協(xié)同系統(tǒng)節(jié)點(diǎn)網(wǎng)絡(luò)中,各層之間的數(shù)據(jù)傳輸與通信主要依靠各層的節(jié)點(diǎn)進(jìn)行,由應(yīng)用平臺(tái)端節(jié)點(diǎn)將控制臺(tái)的用戶需求經(jīng)邊緣節(jié)點(diǎn)傳輸?shù)竭吘壒芾砥髦?各智能設(shè)備和傳感器將采集到的數(shù)據(jù)信息從設(shè)備端傳輸節(jié)點(diǎn)傳輸?shù)竭吘壒?jié)點(diǎn)上,由邊緣節(jié)點(diǎn)完成數(shù)據(jù)處理等工作。

在協(xié)同系統(tǒng)節(jié)點(diǎn)網(wǎng)絡(luò)中,本文重點(diǎn)關(guān)注多層網(wǎng)絡(luò)間的層間連接關(guān)系,關(guān)注各層網(wǎng)絡(luò)的節(jié)點(diǎn)特性在鏈路連接建立中的影響。因此,以系統(tǒng)中應(yīng)用平臺(tái)端節(jié)點(diǎn)、邊緣節(jié)點(diǎn)以及設(shè)備端傳輸節(jié)點(diǎn)為傳輸網(wǎng)絡(luò)的主要組成部分,利用復(fù)雜網(wǎng)絡(luò)對(duì)傳輸網(wǎng)絡(luò)進(jìn)行建模,得到如圖3所示的三層網(wǎng)絡(luò)模型。

圖3 多層復(fù)雜網(wǎng)絡(luò)圖Fig.3 Multilayer complex network diagram

在圖3的三層復(fù)雜網(wǎng)絡(luò)中,各點(diǎn)表示傳輸系統(tǒng)網(wǎng)絡(luò)每層的節(jié)點(diǎn),各層節(jié)點(diǎn)組成集合Ht,部分節(jié)點(diǎn)依照系統(tǒng)結(jié)構(gòu)向外與傳感器、邊緣管理器及系統(tǒng)中心管理控制臺(tái)相連,這部分不在后續(xù)研究問題中涉及,圖3中未繪制。每層節(jié)點(diǎn)之間用實(shí)線表示層內(nèi)連接關(guān)系,層內(nèi)連接集合表示為Kt,不同層節(jié)點(diǎn)之間用虛線表示層間連接關(guān)系,層間連接集合表示為Ltr。

2 協(xié)作網(wǎng)絡(luò)模型生成算法

本節(jié)基于多層復(fù)雜網(wǎng)絡(luò)模型分析節(jié)點(diǎn)特性反映出的網(wǎng)絡(luò)拓?fù)湫畔?duì)網(wǎng)絡(luò)層間協(xié)作連接建立的影響,針對(duì)網(wǎng)絡(luò)模型中任意兩個(gè)復(fù)雜網(wǎng)絡(luò)之間協(xié)作連接的建立提出了一種基于節(jié)點(diǎn)復(fù)合特性的連接生成算法,建立和優(yōu)化網(wǎng)絡(luò)層間連接鏈路,滿足降低數(shù)據(jù)傳輸時(shí)延、提高網(wǎng)絡(luò)傳輸效率的需求。

層間連接的建立包括兩個(gè)過程,首先在各個(gè)復(fù)雜網(wǎng)絡(luò)中選擇一定數(shù)量的節(jié)點(diǎn)作為協(xié)作連接點(diǎn),其次將兩個(gè)網(wǎng)絡(luò)中的協(xié)作點(diǎn)集合通過一定的匹配方法組成協(xié)作點(diǎn)對(duì),在協(xié)作點(diǎn)對(duì)間建立鏈路連接,實(shí)現(xiàn)兩個(gè)復(fù)雜網(wǎng)絡(luò)之間的連接及通信傳輸。

基于上節(jié)提出的端-邊緣協(xié)同系統(tǒng)及多層復(fù)雜網(wǎng)絡(luò)模型,為了滿足智慧交通系統(tǒng)中低延時(shí)的要求,實(shí)現(xiàn)數(shù)據(jù)在網(wǎng)絡(luò)間傳輸延遲的最小化,在多層復(fù)雜網(wǎng)絡(luò)的各層網(wǎng)絡(luò)之間任意兩個(gè)節(jié)點(diǎn)間的路徑距離應(yīng)最短,即減少節(jié)點(diǎn)間最短路徑值。本節(jié)提出了基于節(jié)點(diǎn)復(fù)合特性的協(xié)作網(wǎng)絡(luò)模型生成算法。現(xiàn)有的通過隨機(jī)概率連邊和按節(jié)點(diǎn)度大小排序擇優(yōu)建立層間連接的方法都沒有對(duì)節(jié)點(diǎn)重要性進(jìn)行考慮,而重要性更高的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)建模中將發(fā)揮更重要的作用。在重要程度高的節(jié)點(diǎn)上創(chuàng)建層間連接,協(xié)作網(wǎng)絡(luò)間的通信、數(shù)據(jù)傳輸更高效。因此,本文通過計(jì)算節(jié)點(diǎn)特性參數(shù)值,將節(jié)點(diǎn)特性更突出、在網(wǎng)絡(luò)中更重要的節(jié)點(diǎn)選作協(xié)作點(diǎn)。

2.1 網(wǎng)絡(luò)協(xié)作點(diǎn)選擇算法

網(wǎng)絡(luò)協(xié)作點(diǎn)選擇是在一個(gè)復(fù)雜網(wǎng)絡(luò)中選擇與其他復(fù)雜網(wǎng)絡(luò)建立協(xié)作連接的節(jié)點(diǎn),是協(xié)作網(wǎng)絡(luò)模型建立的第一步。

復(fù)雜網(wǎng)絡(luò)中常用的節(jié)點(diǎn)特征描述參數(shù)有節(jié)點(diǎn)度、聚類系數(shù)、節(jié)點(diǎn)中心性、平均路徑長度等。聚類系數(shù)主要反映節(jié)點(diǎn)在網(wǎng)絡(luò)中的局部的密集度信息[22],節(jié)點(diǎn)中心性則能夠反映節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中影響力的重要性[23]。所以,本節(jié)基于節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性兩個(gè)參數(shù)對(duì)節(jié)點(diǎn)特性進(jìn)行描述。

節(jié)點(diǎn)聚類系數(shù)CCi的計(jì)算如下:

(1)

式中:k表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù);d表示在節(jié)點(diǎn)i的所有k個(gè)鄰居間的邊數(shù)。

節(jié)點(diǎn)介數(shù)中心性bi的計(jì)算公式如下:

(2)

式中:n表示網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù),n(n-1)/2表示將節(jié)點(diǎn)介數(shù)中心性標(biāo)準(zhǔn)化;gjl是從節(jié)點(diǎn)j到節(jié)點(diǎn)l的最短路徑總數(shù);gjl(i)是從節(jié)點(diǎn)j經(jīng)過節(jié)點(diǎn)i到節(jié)點(diǎn)l的最短路徑數(shù)。

由此,本文基于節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性定義節(jié)點(diǎn)聯(lián)合參數(shù)值φi以反映節(jié)點(diǎn)特性。節(jié)點(diǎn)i的聯(lián)合參數(shù)值函數(shù)φi的定義為

φi=β1CCi+β2bi

(3)

式中:β1、β2分別表示節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性在節(jié)點(diǎn)聯(lián)合參數(shù)值中所占的比例系數(shù),β1+β2=1。

選擇兩種節(jié)點(diǎn)特征信息對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性進(jìn)行描述,能夠更好、更全面地描述節(jié)點(diǎn)特性。

根據(jù)節(jié)點(diǎn)聯(lián)合參數(shù)值對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序,通過擇優(yōu)選擇算法實(shí)現(xiàn)協(xié)作點(diǎn)選擇。節(jié)點(diǎn)聯(lián)合參數(shù)值越大,則該節(jié)點(diǎn)的特征性越明顯、在整個(gè)網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中發(fā)揮的重要性越高。擇優(yōu)選擇算法能夠選擇出在整個(gè)網(wǎng)絡(luò)中重要性更大的節(jié)點(diǎn),作為與其他網(wǎng)絡(luò)建立協(xié)作連接的協(xié)作點(diǎn)集合。擇優(yōu)選擇算法的流程圖如圖4所示。

圖4 擇優(yōu)選擇協(xié)作點(diǎn)算法流程圖Fig.4 Flowchart of Preferential collaboration point algorithm

2.2 網(wǎng)絡(luò)協(xié)作連接建立算法

協(xié)作連接建立是指在兩個(gè)不同復(fù)雜網(wǎng)絡(luò)之間將協(xié)作點(diǎn)組對(duì)并互相連接的過程,是協(xié)作網(wǎng)絡(luò)模型建立的第二步。

在任意兩個(gè)復(fù)雜網(wǎng)絡(luò)之間,協(xié)作連接的數(shù)量反映兩個(gè)網(wǎng)絡(luò)之間的協(xié)作程度,在一定數(shù)量協(xié)作連接數(shù)量的情況下,協(xié)作連接建立問題可轉(zhuǎn)換為兩個(gè)復(fù)雜網(wǎng)絡(luò)協(xié)作點(diǎn)集合之間的匹配問題。匹配理論能夠描述互利關(guān)系的形成,早期常用于處理經(jīng)濟(jì)學(xué)問題[24]。近幾年,匹配理論也在無線資源管理中實(shí)現(xiàn)了應(yīng)用[25]。雙邊匹配算法能夠利用匹配主體中的偏好信息,將偏好信息轉(zhuǎn)化為滿意度,建立匹配模型以解決匹配問題[26-27]。通過計(jì)算匹配主體滿意度和最大以及兩個(gè)匹配主體滿意度差最小實(shí)現(xiàn)模型優(yōu)化[28]。

本文使用節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性兩種節(jié)點(diǎn)特征描述網(wǎng)絡(luò)中節(jié)點(diǎn)的偏好信息,偏好值定義為節(jié)點(diǎn)聯(lián)合參數(shù)值的線性相關(guān)函數(shù)。

(4)

(5)

在式(4)、式(5)中,節(jié)點(diǎn)聯(lián)合參數(shù)值較高的協(xié)作點(diǎn)具有更高的偏好值,γ1和γ2表示節(jié)點(diǎn)聯(lián)合參數(shù)值的系數(shù),反映偏好值的傾向程度。

在智慧交通應(yīng)用場景中,協(xié)作連接建立的重點(diǎn)需要滿足降低時(shí)延、縮短傳輸路徑的要求,因此,在兩個(gè)網(wǎng)絡(luò)間建立連接時(shí),選擇節(jié)點(diǎn)聯(lián)合參數(shù)值更高且兩個(gè)節(jié)點(diǎn)的聯(lián)合參數(shù)值更相近的協(xié)作點(diǎn)為協(xié)作點(diǎn)對(duì)并創(chuàng)建協(xié)作連接,將更能夠滿足要求?；诖?多目標(biāo)優(yōu)化模型要滿足兩個(gè)復(fù)雜網(wǎng)絡(luò)對(duì)于對(duì)方的節(jié)點(diǎn)特征偏好值盡量大,并且兩個(gè)網(wǎng)絡(luò)對(duì)于對(duì)方的節(jié)點(diǎn)特征偏好值差異盡量小,建立的優(yōu)化模型可以表示為

(6)

優(yōu)化目標(biāo)的約束條件為每個(gè)復(fù)雜網(wǎng)絡(luò)中的協(xié)作點(diǎn)與其他協(xié)作點(diǎn)之間最多可建立的協(xié)作連接數(shù)的限制o,以及兩個(gè)不同復(fù)雜網(wǎng)絡(luò)之間的協(xié)作連接總數(shù)不超過預(yù)設(shè)定值N。eik=1表示協(xié)作點(diǎn)i和協(xié)作點(diǎn)k之間建立連接,eik=0表示協(xié)作點(diǎn)i和協(xié)作點(diǎn)k之間沒有建立連接。

通過線性加權(quán)法求解多目標(biāo)優(yōu)化模型(6),將多個(gè)優(yōu)化目標(biāo)進(jìn)行加權(quán)求和,組合成單個(gè)目標(biāo),得到單目標(biāo)優(yōu)化模型:

(7)

(8)

多目標(biāo)優(yōu)化模型轉(zhuǎn)化為單目標(biāo)優(yōu)化模型后,利用線性規(guī)劃方法求解可得模型的解,該結(jié)果反映的就是網(wǎng)絡(luò)間節(jié)點(diǎn)的匹配與連接關(guān)系,通過該解將合適的協(xié)作點(diǎn)對(duì)連接起來,實(shí)現(xiàn)多層網(wǎng)絡(luò)的構(gòu)建。

3 仿真測試與分析

基于以上系統(tǒng)建模及提出的算法,本文在Windows系統(tǒng)2.8GHz英特爾Core i7-1165G7、16G內(nèi)存下通過Matlab 2019a進(jìn)行編程仿真。系統(tǒng)仿真使用4種典型復(fù)雜網(wǎng)絡(luò)模型來模擬具有不同結(jié)構(gòu)特性的網(wǎng)絡(luò),分別為:Erdos-Renyi(ER)隨機(jī)網(wǎng)絡(luò)模型[29-30]、Barabasi-Albert(BA)無標(biāo)度網(wǎng)絡(luò)模型[31]、Watts-Strogatz(WS)小世界網(wǎng)絡(luò)模型[22],Newman-Watts(NW)小世界網(wǎng)絡(luò)模型[32]。

不同網(wǎng)絡(luò)結(jié)構(gòu)能夠代表不同的實(shí)際網(wǎng)絡(luò)需求和功能,以在不同結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)之間建立協(xié)作連接,證明結(jié)合節(jié)點(diǎn)多種特征參數(shù)生成協(xié)作網(wǎng)絡(luò)的算法的可靠性和有效性。

生成4種典型復(fù)雜網(wǎng)絡(luò)模型的相關(guān)參數(shù)設(shè)置如表1所示。

表1 復(fù)雜網(wǎng)絡(luò)模型參數(shù)

通過上述參數(shù)設(shè)置得到的4個(gè)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性參數(shù)數(shù)值如圖5、圖6所示。

圖5 各網(wǎng)絡(luò)節(jié)點(diǎn)聚類系數(shù)參數(shù)值Fig.5 Parameter value of each network node clustering coefficient

圖6 各網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)中心性參數(shù)值Fig.6 Parameter value of each network node betweenness centrality

本文所提協(xié)作網(wǎng)絡(luò)生成算法主要以降低系統(tǒng)數(shù)據(jù)傳輸時(shí)間、提高傳輸效率為目標(biāo)。在仿真實(shí)驗(yàn)中,假設(shè)網(wǎng)絡(luò)中的數(shù)據(jù)傳輸時(shí)間與其部署在網(wǎng)絡(luò)上的鏈路路徑長度成正比,各個(gè)節(jié)點(diǎn)間的距離相同,根據(jù)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特征對(duì)協(xié)作網(wǎng)絡(luò)進(jìn)行性能分析。因此,網(wǎng)絡(luò)中各節(jié)點(diǎn)到協(xié)作點(diǎn)的最短路徑反映出系統(tǒng)中各設(shè)備和管理控制器將數(shù)據(jù)、任務(wù)傳輸?shù)狡渌麑訒r(shí)的傳輸距離和時(shí)間。在實(shí)驗(yàn)中,網(wǎng)絡(luò)設(shè)置為無權(quán)圖,各個(gè)節(jié)點(diǎn)之間都能進(jìn)行通信傳輸,所以任意兩個(gè)節(jié)點(diǎn)間的最短路徑距離能夠反映數(shù)據(jù)、任務(wù)從一個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)傳輸?shù)搅硪痪W(wǎng)絡(luò)的路徑及距離。傳輸路徑越短,數(shù)據(jù)包傳輸?shù)乃俣仍娇?在傳輸過程中的時(shí)延越低。因此,本文選擇最短路徑值作為衡量網(wǎng)絡(luò)間傳輸性能的指標(biāo)。

本文使用4種基本復(fù)雜網(wǎng)絡(luò),即ER隨機(jī)網(wǎng)絡(luò)、BA無標(biāo)度網(wǎng)絡(luò)、WS小世界網(wǎng)絡(luò)和NW小世界網(wǎng)絡(luò)能夠組成6種協(xié)作網(wǎng)絡(luò):ER-BA、ER-WS、ER-NW、BA-WS、BA-NW、WS-NW協(xié)作網(wǎng)絡(luò)。

由圖5、圖6可以看出,節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性在不同網(wǎng)絡(luò)中表現(xiàn)出的差異程度不同,反映了在不同網(wǎng)絡(luò)中這兩個(gè)特征參數(shù)對(duì)節(jié)點(diǎn)重要性的影響程度不同。因此,設(shè)置不同的β1、β2系數(shù)值,也會(huì)對(duì)協(xié)作網(wǎng)絡(luò)模型的傳輸性能產(chǎn)生影響。

圖7 ER-WS協(xié)作網(wǎng)絡(luò)在不同特征占比情況下的最短路徑值分布情況Fig.7 Shortest road value distribution of the ER-WS collaborative network under different features proportion

近年來,網(wǎng)絡(luò)模型在設(shè)計(jì)和部署方法上主要以隨機(jī)幾何方法為主,在網(wǎng)絡(luò)中隨機(jī)選擇節(jié)點(diǎn)并在隨機(jī)節(jié)點(diǎn)對(duì)之間建立連接,構(gòu)成協(xié)作網(wǎng)絡(luò)。隨機(jī)連接法在網(wǎng)絡(luò)模型構(gòu)建方面缺少對(duì)節(jié)點(diǎn)特性的考慮,對(duì)系統(tǒng)的數(shù)據(jù)和任務(wù)傳輸效率有一定的影響。在考慮節(jié)點(diǎn)特性構(gòu)建網(wǎng)絡(luò)時(shí),不同特性參數(shù)反映了節(jié)點(diǎn)的不同信息,綜合兩種節(jié)點(diǎn)特征能夠更全面地描述節(jié)點(diǎn)特性。本文選擇節(jié)點(diǎn)隨機(jī)連接法和考慮節(jié)點(diǎn)單一特性的聚類系數(shù)特性網(wǎng)絡(luò)生成算法、介數(shù)中心性特性網(wǎng)絡(luò)生成算法作為節(jié)點(diǎn)復(fù)合特性網(wǎng)絡(luò)生成算法的對(duì)比算法,分析本文算法的優(yōu)勢。

通過仿真實(shí)驗(yàn),4種基礎(chǔ)復(fù)雜網(wǎng)絡(luò)通過上述4種方式生成多層協(xié)作網(wǎng)絡(luò)后的節(jié)點(diǎn)間最短路徑值與節(jié)點(diǎn)對(duì)數(shù)分布情況如圖8(a)～圖8(f)所示。

圖8 各協(xié)作網(wǎng)絡(luò)最短路徑值分布情況Fig.8 Shortest road value distribution of each collaborative network

由圖8可以看出,在加入節(jié)點(diǎn)特性參數(shù)作為節(jié)點(diǎn)重要性衡量指標(biāo)后,網(wǎng)絡(luò)中最短路徑值為1或2的節(jié)點(diǎn)對(duì)明顯增多,最短路徑值為3及以上的節(jié)點(diǎn)對(duì)明顯減少。同時(shí),相比考慮一種節(jié)點(diǎn)特性參數(shù)所生成的協(xié)作網(wǎng)絡(luò)模型,本文提出的基于節(jié)點(diǎn)復(fù)合特性的協(xié)作網(wǎng)絡(luò)模型生成算法在節(jié)點(diǎn)間的最短路徑上也有進(jìn)一步的優(yōu)化效果,低節(jié)點(diǎn)間最短路徑值的節(jié)點(diǎn)對(duì)數(shù)更多,高節(jié)點(diǎn)間最短路徑值的節(jié)點(diǎn)對(duì)數(shù)更少。由此,數(shù)據(jù)和任務(wù)在網(wǎng)絡(luò)間能夠通過更短的路徑進(jìn)行傳輸,實(shí)現(xiàn)降低傳輸時(shí)延、提高傳輸效率的目的,并能夠減少傳輸能耗,獲得更好的性能。

文獻(xiàn)[33]提出的高速多層網(wǎng)絡(luò)模型,通過增加度值高的節(jié)點(diǎn)平衡了網(wǎng)絡(luò)間的負(fù)載問題,提高了網(wǎng)絡(luò)的流量容量,提高了網(wǎng)絡(luò)的傳輸能力,但未考慮網(wǎng)絡(luò)間傳輸鏈路的選擇問題。本文提出的基于節(jié)點(diǎn)復(fù)合特性的協(xié)作網(wǎng)絡(luò)模型生成算法,優(yōu)化了網(wǎng)絡(luò)間的傳輸鏈路選擇問題,對(duì)比于文獻(xiàn)[33]更進(jìn)一步縮短了網(wǎng)絡(luò)系統(tǒng)數(shù)據(jù)傳輸時(shí)間,提高了傳輸效率。文獻(xiàn)[34]利用隨機(jī)幾何和排隊(duì)理論分析了邊緣計(jì)算網(wǎng)絡(luò)的通信成功概率,通過降低用戶密度和提高邊緣服務(wù)器密度,提高了網(wǎng)絡(luò)的通信成功概率,這一方法也能夠在一定程度上降低網(wǎng)絡(luò)平均延遲,但并不適用于固定用戶數(shù)量和邊緣節(jié)點(diǎn)數(shù)量的系統(tǒng)網(wǎng)絡(luò)。本文算法對(duì)于固定節(jié)點(diǎn)數(shù)量的多層網(wǎng)絡(luò)進(jìn)行層間鏈路連接上的優(yōu)化,對(duì)比于文獻(xiàn)[34]更利于在已確定用戶節(jié)點(diǎn)和邊緣節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)中降低數(shù)據(jù)傳輸時(shí)延、提高傳輸效率。文獻(xiàn)[35]提出了基于復(fù)雜網(wǎng)絡(luò)的多層城市增長與優(yōu)化綜合模型,在交通網(wǎng)絡(luò)構(gòu)建方面,該模型架構(gòu)降低了網(wǎng)絡(luò)建設(shè)投資成本,但忽略了交通網(wǎng)絡(luò)對(duì)龐大數(shù)據(jù)量和降低時(shí)延的嚴(yán)苛需求,本文提出的端-邊緣協(xié)同系統(tǒng)參考架構(gòu)通過邊緣計(jì)算系統(tǒng)滿足這一需求,對(duì)交通網(wǎng)絡(luò)的構(gòu)建更加全面。

4 結(jié)束語

本文針對(duì)時(shí)延要求高的智慧交通系統(tǒng)構(gòu)建了設(shè)備端和邊緣節(jié)點(diǎn)協(xié)作運(yùn)行的端-邊協(xié)同系統(tǒng),并基于復(fù)雜網(wǎng)絡(luò)理論對(duì)協(xié)同系統(tǒng)進(jìn)行了模型化。對(duì)于隨機(jī)幾何方法在網(wǎng)絡(luò)模型構(gòu)建方面缺乏節(jié)點(diǎn)特性信息使用的問題,提出了基于節(jié)點(diǎn)復(fù)合特性的協(xié)作網(wǎng)絡(luò)模型生成算法,構(gòu)建了優(yōu)化的多層網(wǎng)絡(luò)系統(tǒng),實(shí)現(xiàn)降低時(shí)延、提高系統(tǒng)通信傳輸效率的目的。算法重點(diǎn)強(qiáng)調(diào)節(jié)點(diǎn)聚類系數(shù)和介數(shù)中心性兩種特性參數(shù)對(duì)節(jié)點(diǎn)特性的共同影響。節(jié)點(diǎn)聚類系數(shù)反映了節(jié)點(diǎn)在網(wǎng)絡(luò)局部的密集程度,介數(shù)中心性反映了節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的信息傳播能力。本文構(gòu)造了節(jié)點(diǎn)聯(lián)合參數(shù)值,將兩種特性參數(shù)進(jìn)行了結(jié)合,更加全面地反映出各個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度,彌補(bǔ)和改進(jìn)了隨機(jī)網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)信息描述和使用不足的問題。

本文使用4種典型復(fù)雜網(wǎng)絡(luò)模型進(jìn)行協(xié)作網(wǎng)絡(luò)構(gòu)建的仿真,對(duì)所提算法進(jìn)行了驗(yàn)證。仿真結(jié)果表明,本文提出的節(jié)點(diǎn)復(fù)合特性協(xié)作網(wǎng)絡(luò)生成算法與一般隨機(jī)連接法生成網(wǎng)絡(luò)以及單獨(dú)使用節(jié)點(diǎn)聚類系數(shù)、單獨(dú)使用介數(shù)中心性特征進(jìn)行協(xié)作網(wǎng)絡(luò)生成的算法相比,通過節(jié)點(diǎn)間最短路徑值統(tǒng)計(jì)結(jié)果可以看出,本文算法有效地縮短了整體協(xié)作網(wǎng)絡(luò)的節(jié)點(diǎn)間最短路徑,因此,數(shù)據(jù)和任務(wù)能夠更快地在網(wǎng)絡(luò)間進(jìn)行傳輸,降低傳輸時(shí)延,提高傳輸效率,節(jié)約傳輸能耗。

本文所提算法在網(wǎng)絡(luò)層內(nèi)及層間節(jié)點(diǎn)連接距離、節(jié)點(diǎn)容量方面仍存在不足,在實(shí)際部署的協(xié)作網(wǎng)絡(luò)中,各節(jié)點(diǎn)間距離有一定差異,每個(gè)節(jié)點(diǎn)承載的容量也不完全相同,具有不同的執(zhí)行任務(wù)的能力,這對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性也有一定影響,針對(duì)以上問題后續(xù)將繼續(xù)開展相關(guān)研究。