任熠營，陳玉冰，張立臣

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

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

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

2.1 覆蓋網(wǎng)

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

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

2.2 面向?qū)ぢ犯采w網(wǎng)模型

本文主要研究面向?qū)ぢ犯采w網(wǎng)如何選取固定數(shù)目覆蓋節(jié)點(diǎn)組成覆蓋路徑，使得源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路由數(shù)據(jù)網(wǎng)絡(luò)延時最小。為構(gòu)建基于基礎(chǔ)物理設(shè)施網(wǎng)絡(luò)結(jié)構(gòu)的面向?qū)ぢ犯采w網(wǎng)模型，給出以下定義：

定義1 基礎(chǔ)物理設(shè)施網(wǎng)絡(luò)定義為

G=(V,E)

(1)

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

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

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

(2)

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

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

(3)

(4)

3 面向?qū)ぢ犯采w網(wǎng)節(jié)點(diǎn)選擇方法

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

3.1 禁忌搜索算法

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

算法具體步驟如下：

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

(2)判斷當(dāng)前解是否滿足設(shè)定的終止準(zhǔn)則？如果是，輸出優(yōu)化之后計算所得的結(jié)果；否則進(jìn)入步驟(3)；

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

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

(5)轉(zhuǎn)到步驟(2)。

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

3.2 改進(jìn)禁忌搜索算法

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

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

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

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

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

4 仿真實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

4.3 算法對比

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

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

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

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

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

5 結(jié)束語

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

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