面向尋路覆蓋網(wǎng)節(jié)點選取方法

任熠營，陳玉冰，張立臣

(廣東工業(yè)大學 計算機學院，廣東 廣州 510006)

0 引 言

5G時代的來臨助推工業(yè)4.0的快速發(fā)展，給互聯(lián)網(wǎng)底層物理設施帶來日益陡增的網(wǎng)絡需求壓力，從單一數(shù)據(jù)到多媒體信息傳輸，信息物理系統(tǒng)(cyber-physical systems,CPS)在其中扮演著重要角色。為滿足各式業(yè)務的QoS需求，減少對現(xiàn)有網(wǎng)絡基礎架構的大幅度調整，CPS通信方案之一的覆蓋網(wǎng)備受矚目。覆蓋網(wǎng)(overlay network)是一種構建在現(xiàn)有物理網(wǎng)絡之上的虛擬網(wǎng)絡，可以在不改變現(xiàn)在底層物理網(wǎng)絡拓撲架構基礎上提供網(wǎng)絡服務，提高網(wǎng)絡性能。不同覆蓋網(wǎng)可以使用相同的物理鏈路進行數(shù)據(jù)傳輸，也可以部署在相同的物理節(jié)點上，物理節(jié)點的利用率得到大幅度提高，服務更加可靠且容錯性高[1]。

覆蓋網(wǎng)根據(jù)服務場景分為面向尋路、面向內容和面向語義3種類型。其中，面向尋路覆蓋網(wǎng)絡側重對路由性能的考量，通過尋找最大化路由性能要求的最優(yōu)覆蓋節(jié)點，使用物理鏈路將相關覆蓋節(jié)點鏈接而成最佳覆蓋路徑，最后經(jīng)由路徑上的覆蓋節(jié)點對應的真實底層物理節(jié)點，將用戶自定義的數(shù)據(jù)從客戶端經(jīng)覆蓋節(jié)點和路徑，轉發(fā)到接收端。面向尋路的覆蓋網(wǎng)路由機制的重點：在底層真實物理節(jié)點的映射中，選擇若干合適真實物理節(jié)點成為覆蓋節(jié)點進而轉發(fā)數(shù)據(jù)。本文重點研究面向尋路覆蓋網(wǎng)。

1 相關工作

近年來國內外學者針對智能電網(wǎng)[2]、在線學習[3]、交互式多媒體平臺[4]、機器人[5]、商用設備[6]等不同領域面向尋路覆蓋網(wǎng)進行了深入研究。但大多數(shù)研究都是默認覆蓋網(wǎng)已知或者底層物理網(wǎng)絡與覆蓋網(wǎng)之間為全映射關系的情況，缺乏對覆蓋節(jié)點選取的研究。

面向尋路覆蓋網(wǎng)構建的關鍵問題在于：如何從底層物理網(wǎng)絡的拓撲映射中尋找一組關鍵節(jié)點成為覆蓋節(jié)點，使得覆蓋網(wǎng)中路由路徑最優(yōu)。對此，Rai等[7]基于對偶次梯度下降法提出分布式動態(tài)路由算法，算法通過增加覆蓋節(jié)點本身直接路由和其它覆蓋節(jié)點的間接路由數(shù)量構建覆蓋網(wǎng)，實現(xiàn)網(wǎng)絡吞吐量最大化；Guan等[8]針對單路徑路由面臨的局限性，基于空間幾何坐標構建了多節(jié)點多路徑覆蓋網(wǎng)，通過尋找相關性較小的路徑提高并發(fā)鏈路利用率，降低單路徑的負面影響，有效提高了覆蓋網(wǎng)多路徑傳輸?shù)男?；陳玉冰等[9]提出基于改進變鄰域搜索算法的覆蓋網(wǎng)構建方法，算法利用遞減式鄰域交換改變鄰域結構，同時算法抖動方式設置為隨機更換初始值，借助目標函數(shù)優(yōu)化覆蓋節(jié)點集的選取，提高了網(wǎng)絡通信效率，降低了算法時間花銷；廖怡等[10]針對基于網(wǎng)絡測量的覆蓋網(wǎng)絡問題，提出不完全可測網(wǎng)絡環(huán)境中覆蓋網(wǎng)構建算法，基于網(wǎng)絡時延構造樹形拓撲結構，算法設置高精度節(jié)點加入和低精度加入兩種方法，在不同網(wǎng)絡拓撲結構模型中獲得較高時延伸縮比例。

面向尋路覆蓋網(wǎng)節(jié)點選擇問題已經(jīng)被驗證是NP難題[9]，使用禁忌搜索算法(Tabu search，TS)解決各種NP難題一直是研究的熱點。Ark等[11]將遺傳算法嵌入TS中，結合中交叉和變異等進化策略，提出基于種群的禁忌搜索算法，用以解決車間調度問題；陸佳煒等[12]針對云計算平臺下任務調度問題，提出時間貪心策略改進初始解、結合任務完成總時間等多因素的禁忌搜索算法，縮短了任務調度時間，資源負載更均衡；劉景發(fā)等[13]結合鄰域啟發(fā)式布局策略，改進禁忌搜索算法中禁忌對象和終止準則選擇策略，解決不等面積動態(tài)設施布局干涉約束問題；Amina等[14]在多播路由延遲約束代價最小化問題中，使用邊介數(shù)改進KMB算法測量給定路徑邊值，并采用禁忌搜索算法對解進行改進，縮短了網(wǎng)絡延遲。以上問題均為NP難題，可見使用禁忌搜索算法解決面向尋路覆蓋網(wǎng)節(jié)點選取問題具有一定的研究價值。

本文針對面向尋路覆蓋網(wǎng)少條件限制、有特定節(jié)點數(shù)的特點，提出一種改進禁忌搜索算法對覆蓋網(wǎng)節(jié)點進行選取。算法首先結合A*算法對節(jié)點進行預處理，選取最優(yōu)解作為禁忌搜索算法初始解；然后提出遞減式概率化方案對鄰域解進行選擇，降低算法陷入局部最優(yōu)的風險；最后通過設置動態(tài)禁忌長度，控制禁忌對象存儲時間，縮短算法運行時間。通過仿真實驗驗證了本文算法的可行性。

2 覆蓋網(wǎng)構造模型

2.1 覆蓋網(wǎng)

覆蓋網(wǎng)包括一組根據(jù)自身相關性能要求選定的覆蓋節(jié)點和不同節(jié)點按需求組成的覆蓋鏈路，其中覆蓋節(jié)點為底層真實物理節(jié)點映射的虛擬節(jié)點，覆蓋鏈路為不同虛擬節(jié)點間一條或多條的虛擬鏈路，相鄰覆蓋節(jié)點路由數(shù)據(jù)的最終方式則是通過底層真實物理節(jié)點。覆蓋節(jié)點既可以是不同類型客戶端節(jié)點或終端主機節(jié)點，也可以是不同服務器節(jié)點，不同的節(jié)點都具有一定的功能，例如轉發(fā)處理和路由數(shù)據(jù)等。

以圖1例，覆蓋鏈路既可以對應物理網(wǎng)絡一條物理鏈路(如覆蓋鏈路D′到B′，對應物理鏈路D到B)，也可以對應多條物理鏈路(如覆蓋鏈路D′到A′，對應物理鏈路D到C再到A，其中C為中繼節(jié)點)。覆蓋網(wǎng)具有自身獨立的路由機制，可以根據(jù)對覆蓋網(wǎng)的自身特定性能要求計算出從終端主機節(jié)點到接收端最優(yōu)的路由路徑；在覆蓋網(wǎng)中，發(fā)送端節(jié)點的數(shù)據(jù)經(jīng)過自身性能要求計算所得最優(yōu)路徑中的多個覆蓋節(jié)點逐跳轉發(fā)傳輸?shù)浇邮斩斯?jié)點，而相鄰覆蓋節(jié)點之間的數(shù)據(jù)傳輸則由底層真實物理節(jié)點組成的底層真實物理路徑實現(xiàn)，物理傳輸?shù)倪^程由自身特定性能決定，對用戶完全透明[15]。

2.2 面向尋路覆蓋網(wǎng)模型

本文主要研究面向尋路覆蓋網(wǎng)如何選取固定數(shù)目覆蓋節(jié)點組成覆蓋路徑，使得源節(jié)點到目標節(jié)點路由數(shù)據(jù)網(wǎng)絡延時最小。為構建基于基礎物理設施網(wǎng)絡結構的面向尋路覆蓋網(wǎng)模型，給出以下定義：

定義1 基礎物理設施網(wǎng)絡定義為

G=(V,E)

(1)

其中，V表示有E個節(jié)點的基礎物理設施節(jié)點集,E表示基礎物理設施節(jié)點之間的物理鏈路連接集。

定義2 定義從源節(jié)點到目標節(jié)點，由若干覆蓋節(jié)點和覆蓋鏈路組成覆蓋網(wǎng)S

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

(2)

其中，V(S)表示按要求選定的所有覆蓋節(jié)點的集合；E(S)表示覆蓋鏈路的集合，覆蓋節(jié)點集通過不同覆蓋鏈路形成覆蓋網(wǎng)G(S)， 覆蓋節(jié)點和物理節(jié)點之間為一一映射的關系，不同覆蓋鏈路對應一條或多條底層真實物理鏈路。

定義3 覆蓋網(wǎng)S的最短覆蓋路徑集合為R(S)∈E(S)，r(S)∈R(S)表示覆蓋網(wǎng)S中的一條覆蓋路徑， |R(S)| 表示覆蓋網(wǎng)S中所有覆蓋路徑數(shù)。

(3)

(4)

3 面向尋路覆蓋網(wǎng)節(jié)點選擇方法

文獻[9]驗證了面向尋路覆蓋網(wǎng)構造中覆蓋節(jié)點的選取是一個NP難題，啟發(fā)式算法及其衍生算法是目前解決NP難題被使用最多的方法。本文將改進禁忌搜索算法，通過目標函數(shù)實現(xiàn)對覆蓋節(jié)點的選取。

3.1 禁忌搜索算法

一般情況下，設計禁忌搜索算法主要需要考慮以下內容：①初始解和評價函數(shù)；②鄰域構型和候選解；③禁忌對象和禁忌長度；④禁忌表和藐視(特赦)準則；⑤終止準則。

算法具體步驟如下：

(1)給定算法參數(shù)，設置禁忌表長度，隨機初始解，同時置空禁忌表；

(2)判斷當前解是否滿足設定的終止準則？如果是，輸出優(yōu)化之后計算所得的結果；否則進入步驟(3)；

(3)根據(jù)設定鄰域構型規(guī)則，由當前解生成不同數(shù)量鄰域解，由評價函數(shù)通過計算全部鄰域解，選擇最優(yōu)鄰域解成為候選解；

(4)判斷候選解是否滿足藐視準則？如果滿足藐視準則，忽略候選解自身的禁忌屬性，將滿足藐視準則的候選解替換為當前解和當前最優(yōu)解，替換掉最早進入禁忌表的對象，禁忌表中不同禁忌對象的任期全部減一，并且釋放禁忌表中任期為0的禁忌對象；否則，在候選解中選擇不在禁忌表中的最優(yōu)解為當前解，并將其替換掉禁忌表中最早進入的禁忌對象，將禁忌表中不同禁忌對象的任期全部減一，釋放任期為0的禁忌對象。

(5)轉到步驟(2)。

一般情況下，工匠精神主要是指在具體的工作中，工匠們可以對設計具有獨特的見解，能夠嚴格的控制質量，并隨著時代的發(fā)展，可以對相關技術進行積極的完善和革新，保證可以有效提升制作的效果和水平，促進企業(yè)的可持續(xù)發(fā)展。新時期也賦予了工匠精神新的含義。對于工匠精神來說，其是現(xiàn)代精神與傳統(tǒng)職業(yè)價值有效融合的結果。在現(xiàn)代的社會中，工匠精神除了要具備尊師重教的精神，還應該具備較高的創(chuàng)新精神，保證可以提升工作的高效性，推動企業(yè)發(fā)展進程。

3.2 改進禁忌搜索算法

禁忌搜索算法作為一種元啟發(fā)式算法，具有優(yōu)秀的局部搜索能力，但初始解選取[16]、鄰域構型變化[17]以及禁忌長度設置[18]都直接影響算法的搜索效率。為此，本文結合面向尋路覆蓋網(wǎng)節(jié)點選取問題對禁忌搜索算法提出以下改進：

(1)結合A*算法選取初始解。傳統(tǒng)禁忌搜索算法隨機選取初始解的方式顯著降低了算法在解空間的搜索效率。A*算法作為一種靜態(tài)路由網(wǎng)中求解最短路徑最有效的啟發(fā)式的圖直接搜索算法，算法從初始節(jié)點開始，通過對周圍節(jié)點的評估，選取最優(yōu)節(jié)點進行拓展，直到尋找到目標點，然后由目標點回溯，最終形成完成的全局規(guī)劃路線。A*算法雖然不一定能尋找到最佳的路徑，但能盡可能找到最短路徑，并且算法運行速度快，適合作為預處理操作選取初始解。因此，本文使用A*算法對初始解進行選取，降低了禁忌搜索算法對于初始解的強依賴，提高了算法執(zhí)行速度，克服了禁忌搜索算法從劣解開始搜索而不利于全局的問題。

(2)改進鄰域構型以增強搜索能力。鄰域構型是從一個給定解到另一個解的規(guī)則，鄰域解為給定解經(jīng)過一次變換規(guī)則所得，局部搜索過程如何從一個解跳轉到另一個解由鄰域構型決定，因此，鄰域構型的構造方法直接影響局部搜索的算法的效率[18]。常見鄰域構型如交換相鄰候選節(jié)點、將候選解點插入節(jié)點集和交換頭部或尾部部分節(jié)點等，但以上改變鄰域構型方案明顯不適合面向尋路覆蓋網(wǎng)節(jié)點選取策略。

因此，本文根據(jù)面向尋路覆蓋網(wǎng)少條件限制、有特定節(jié)點數(shù)的特點，提出遞減式概率化鄰域構建方案，即在有M個節(jié)點的禁忌搜索算法鄰域變換中，第一次鄰域變換中將隨機選取N個節(jié)點與候選節(jié)點進行交換，由目標函數(shù)計算每個鄰域解的估值，根據(jù)估值進行輪盤賭策略概率化選擇鄰域解成為候選解；第二次鄰域交換將交換N-1個節(jié)點，重復上述概率化選擇，依次遞減直至N=1。 圖2為遞減式概率化鄰域變換N=3的情況，具體操作為：第一次鄰域交換中，隨機選取3個覆蓋節(jié)點與候選節(jié)點進行交換，計算交換后每條覆蓋路徑目標函數(shù)估值，然后采用輪盤賭概率化選擇鄰域解為候選解，判斷候選解是否滿足藐視準則，更新禁忌表；第二次鄰域交換兩個覆蓋節(jié)點，重復上述過程。其中，實心三角形和實心圓形為經(jīng)過鄰域變換后的覆蓋節(jié)點集合V(S)；空心三角形為表示經(jīng)過鄰域變換后由覆蓋節(jié)點變成候選節(jié)點；空心圓形表示有可能的覆蓋節(jié)點；實心圓形表示經(jīng)過鄰域變換后由候選節(jié)點變成覆蓋節(jié)點v。 概率化選擇的優(yōu)勢在于選取鄰域解不再直接選取最優(yōu)解為候選解，而是給予劣解一定的概率被選為候選解，加大搜索范圍，避免算法陷入局部最優(yōu)。

(3)設置動態(tài)禁忌長度。禁忌表主要是為了減少算法搜索過程中的反復計算，避免陷入局部最優(yōu)，禁忌長度是禁忌表中禁忌對象的存儲時間長短，禁忌長度太短，搜索容易陷入循環(huán)；禁忌長度太長，搜索時間便會變長，所以禁忌長度的優(yōu)劣直接影響算法效率。前期測試發(fā)現(xiàn)，由于路由節(jié)點數(shù)目遠大于覆蓋網(wǎng)節(jié)點數(shù)目，在保證算法結果最優(yōu)解情況下，禁忌長度設置為L=1.5*[10+N/M] 較為合適，其中N為基礎物理設施節(jié)點數(shù)，M為覆蓋網(wǎng)節(jié)點數(shù)；同時將用前綴樹代替禁忌表對禁忌對象進行存儲。本文取L為禁忌長度。圖3為改進禁忌搜索算法流程圖。

4 仿真實驗分析

4.1 實驗環(huán)境

實驗采用MATLAB隨機生成5個仿真數(shù)據(jù)集，物理節(jié)點分別為200個、1000個、2000個、3000個和5000個，對應構建覆蓋節(jié)點數(shù)為k(k=3、5、7、10、15、20、30)的面向尋路覆蓋網(wǎng)。采用節(jié)點間的度量作為節(jié)點間通信延時度，節(jié)點延時主要模擬實際運行中節(jié)點產生物理延誤。實驗運行50次，最終實驗結果取均值。將在算法時間和網(wǎng)絡延時兩方面，分別對比本文算法、遺傳算法(genetic algorithm，GA)、模擬退火算法(simulated annealing algorithm，SA)以及禁忌搜索算法(TS)。

實驗采用64位的Ubuntu 16.04 LTS操作系統(tǒng)，硬件配置為GeForce GTX 1080 Ti，CPU為12核的Intel Core i7-7800X，15.4 GB內存。

4.2 實驗結果

改進禁忌搜索算法實驗中，將對比5個數(shù)據(jù)集在不同覆蓋節(jié)點中算法時間和網(wǎng)絡延時。仿真數(shù)據(jù)集將以無向加權圖的形式模擬底層物理節(jié)點拓撲結構，根據(jù)目標函數(shù)P(S)計算最優(yōu)解，尋找目標覆蓋節(jié)點，最終組成最優(yōu)覆蓋路徑。路由數(shù)據(jù)將從源節(jié)點發(fā)送出去，經(jīng)由覆蓋網(wǎng)中覆蓋節(jié)點到達目標節(jié)點。

本文算法網(wǎng)絡延時如圖4所示，隨著覆蓋節(jié)點數(shù)的增加，網(wǎng)絡延時穩(wěn)定下降；當覆蓋節(jié)點數(shù)從3個增加到30個，網(wǎng)絡延時下降至少40%。

本文算法運行時間如圖5所示，隨著覆蓋節(jié)點的增加，算法運行時間明顯變長。當物理節(jié)點數(shù)為200時，算法時間穩(wěn)定在3 s以下；當物理節(jié)點數(shù)大于3000時，算法時間維持在50 s以上。當覆蓋節(jié)點個數(shù)在15個以內時，算法運行時間增長緩慢。

4.3 算法對比

算法對比實驗中，將對比遺傳算法、禁忌搜索算法和本文算法在1000個物理節(jié)點數(shù)據(jù)集中，覆蓋節(jié)點為k(k=3、5、7、10、15、20、30)的情況。

遺傳算法通過模擬自然界生物進化中基因選擇、交叉等過程，挑選優(yōu)秀個體遺傳給下一代，實現(xiàn)優(yōu)勝劣汰，具有優(yōu)秀的全局搜索能力，能很大程度避免陷入局部最優(yōu)；模擬退火算法借助固體退火原理，從較優(yōu)解開始，結合概率突破特征在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解；禁忌搜索算法從一個選定初始解出發(fā)，通過對鄰域構型啟發(fā)式布局尋找最優(yōu)鄰居，直至局部最優(yōu)。

由圖6各算法網(wǎng)絡延時和圖7各算法運行時間圖可知，遺傳算法在不同的節(jié)點中網(wǎng)絡延時低于禁忌搜索算法，但算法時間花銷高于禁忌搜索算法，原因在于遺傳算法通過優(yōu)秀個體改良解集，不斷提高優(yōu)勢解適應度，指導優(yōu)化的搜索空間，自適應調整算法搜索方向，增強了全局搜索能力，因此網(wǎng)絡延時整體較低，但隨著節(jié)點數(shù)的增加，遺傳算子中選擇、交叉和變異等操作將消耗大量算法運行時間，而且會有早熟收斂問題的發(fā)生；禁忌搜索算法根據(jù)候選解對比禁忌表即可確定最優(yōu)解，算法運行時間相對遺傳算法有所減少，但每次僅尋找最優(yōu)鄰居使得算法容易陷入局部最優(yōu)，因此網(wǎng)絡延時高于遺傳算法；相較于遺傳算法全局尋優(yōu)和禁忌搜索算法局部尋優(yōu)，模擬退火算法在局部最優(yōu)狀態(tài)下概率突破，趨于全局最優(yōu)，而且局部搜索策略也加快了算法執(zhí)行速度，因此網(wǎng)絡延時低于禁忌搜索算法，運行時間快于遺傳算法，但模擬退火算法對整個解空間狀態(tài)并不了解，搜索效率不高。

本文算法針對禁忌搜索算法容易陷入局部最優(yōu)的缺陷，根據(jù)覆蓋網(wǎng)特點，采用遞減式交換候選節(jié)點、概率化的尋優(yōu)方法改進鄰域構型，以一定的方式接受劣解，降低陷入局部最優(yōu)風險。由圖6可知，本文算法網(wǎng)絡延時在節(jié)點較少時微劣于遺傳算法，原因在于節(jié)點較少時覆蓋節(jié)點的選擇相對局限；隨著覆蓋節(jié)點的選擇更加多樣，本文算法顯著優(yōu)于遺傳算法、模擬退火算法和禁忌搜索算法，側面說明本文算法跳出了局部最優(yōu)，全局尋優(yōu)能力得到增強。

在算法執(zhí)行速度方面，本文通過改進初始解獲取方式，使算法以較優(yōu)的解開始迭代，有利于提前達到終止條件中對象最大記憶頻率，即當最佳目標值頻率達到閾值則認定為全局最優(yōu)解；同時動態(tài)設置禁忌表長度，進一步加快達到目標迭代數(shù)的時間，禁忌對象以前綴樹形式存儲，方便對禁忌對象的快速查找，相較于表格形式存儲，前綴樹在大規(guī)模數(shù)據(jù)中將是不同量級的提升。因此，如圖7所示，本文算法運行時間均遠低于對比算法。

5 結束語

本文針對面向尋路覆蓋網(wǎng)節(jié)點選取NP難題，提出一種通過A*算法計算初始解、遞減式概率化變換鄰域構型和設置動態(tài)禁忌長度的改進禁忌搜索算法，仿真實驗結果表明：相較于遺傳算法、模擬退火算法和禁忌搜索算法，改進禁忌搜索算法能有效降低網(wǎng)絡延時，減少算法開銷。

實驗期間發(fā)現(xiàn)，禁忌搜索算法僅僅使用單一串行的搜索方式將在計算階段耗費大量時間，極大影響了算法的效率，后續(xù)將在算法搜索方式層面提升算法尋優(yōu)能力。