一種基于改進蜂群算法的網絡重構技術

2020-01-08 01:59:32潘成勝蔡睿妍

小型微型計算機系統 2020年1期

潘成勝,李金,2,蔡睿妍,2,楊力,2

1(大連大學通信與網絡實驗室,遼寧大連 116622)2(大連大學信息工程學院,遼寧大連 116622)

1 引言

隨著通信技術以及中國航空航天事業的迅猛發展,由海、陸、空所組成的新一代智能一體化通信網絡[1,2]框架已逐步形成,作為地面與太空通信的媒介-空間信息網絡,將承擔大量的信息獲取、傳送和分發的重任.然而,由于衛星節點的移動性、無線通信的脆弱性以及外太空空間內所存在的不確定性等因素影響,導致衛星網絡的通信性能會隨著拓撲結構的變化而變化,甚至有可能會因局部節點失效所引起的拓撲分割最終導致通信網絡的整體失效.因此,如何動態維持網絡拓撲結構的穩定性以及通信的可靠穩定性,成為了國內外研究熱點.空間信息網絡的拓撲重構問題是一個需要考慮衛星節點間的可見性、可連通時間以及連通度等多約束組合優化問題,其目標是在資源受限的前提下滿足鏈路連通時間和連通度的要求,通過將空間信息網絡中具有剩余連通度的衛星節點進行鏈路選擇鏈接,重構拓撲結構,提高空間信息網絡的抗毀性[3,4],保證網絡的通信效率.近年來,出現不少針對空間信息網絡拓撲重構重構算法研究.文獻[5]中通過動態路由的方式檢測故障鏈路,采用傳統功率控制方式(Transcation Power Control,TPC)進行鏈路重構,在節點損壞過少或不集中的情況下采用該算法重構效果頗有成效,但當節點損壞過多或損壞節點較為集中時則容易出現拓撲漏洞,整體重構效率較低.文獻[6]中提出一種利用蟻群算法(Ant Colony Algorithm,ACO)完成空間拓撲修復和預測網絡鏈路過載情況的方法,該算法整體效率偏優但存在著收斂時間過慢、易陷入局部最優的缺點.文獻[7]中通過遍歷選擇聚合度較大節點完成鏈路重構,忽略了節點連通時間,易造成多次拓撲重構,造成資源的浪費.

研究空間信息網絡重構問題的關鍵是在于建立有效的網絡模型、確立合適的評價指標,進而設計重構算法,使得空間信息網絡拓撲結構能在短時間內完成重構,以滿足工程應用需求.本文首先根據空間信息網絡的特點確立衛星網絡模型及節點模型,然后定義衛星可連通度約束、可連通時間約束和潛在鏈路發現約束,確立空間信息網絡的鏈路模型,最后確定合適的評價指標以及設計相關約束函數模型,使得該模型以盡可能提高網絡的抗毀性為目標.基于所建立的空間信息網絡拓撲模型,本文提出一種基于改進人工蜂群算法(Improved Artificial Bee Colony Algorithm,IABC)的節點重構技術.該方法首先將衛星網絡中的節點編碼,委派身份信息,然后利用蜂群算法對鏈路進行迭代更新,并以網絡效率高低作為為鏈接是否有效的判據.仿真表明,該算法在優化網絡拓撲結構、增強衛星網絡抗毀性的基礎上,還可以優化提高衛星網絡的通信效率.

2 空間信息網絡模型

本文所提算法主要解決的是空間信息網絡中的衛星網絡拓撲重構問題,地面網絡拓撲結構相對穩定故不考慮在內,所以該網絡模型[8]可簡化為:

G={Sat,Link}

(1)

其中,Sat代表空間信息網絡中所有的衛星節點的集合,Link表示網絡中鏈路的集合.

2.1 空間信息網絡節點模型

對于衛星節點,本文主要考慮其節點編號、衛星節點的連接度以及潛在鏈路個數,故衛星節點模型可表示為:

Sat={s,degree,latent}

(2)

其中,s表示衛星節點編號(s∈(1,2,…,N));degree為衛星節點的連接度;latent表示此節點存在潛在鏈路的個數.如果節點間的連接沒有度約束限制,完全圖具有最優的抗毀性[9],但在空間信息網絡的背景下,連接度受節點功率以及衛星自身表面積等因素影響,故該參數是在重構算法設計時所要考慮的重要約束條件之一.潛在鏈路的發現取決于可見性和鏈路的連接時間,具體定義如下:

定義1.衛星可見條件:

衛星節點在繞地球做周期性運動的過程中會受到來自地球和大氣層的遮擋,所以兩顆衛星所形成的鏈路長度存在一個最大值,即最大可見鏈路長度.其星間鏈路長度dAB可表示為公式(3):

(3)

其中,R為地球半徑;hA、hB分別為衛星A與衛星B所在的軌道高度;ξ為地心角.但在實際情況中,由于星間鏈路會受到地球的遮擋,故任意兩顆處于不同軌道的衛星在某一時刻,它們的之間的星間鏈路長度存在一個最大值,即為最大可見鏈路長度.假定此時衛星A與衛星B之間的鏈路長度dAB為其最大可見鏈路長度,可表示為:

(4)

同時,可以推出最大地心角可表示為:

(5)

當兩顆衛星間鏈路長度dAB滿足dAB≤dmax,地心角ξ滿足ξ≤ξmax時,兩顆衛星可見;否則,兩顆衛星不可見,即不存在潛在鏈路.

定義2.鏈路連接時間:

由于空間信息網絡的拓撲具有時變性,所以星間鏈路在連接和斷開兩個狀態間頻繁切換.若要建立穩定的網絡結構,則需對星間鏈路連接時間加以分析.鏈路連接時間TLink(i,j)是指衛星i和衛星j從建立鏈路開始,到鏈路斷開的這一段時間.可以用公式表示.

TLink(i,j)=Tend(i,j)-Tstart(i,j)

(6)

其中Tstart(i,j)和Tend(i,j)分別表示衛星i和j之間鏈路的建立時刻和鏈路斷開的時刻.為了減小星間鏈路頻繁切換,本文定義了最小連接時間Tmin,只有當TLink(i,j)≥Tmin時才具備建立鏈路的條件.

2.2 空間信息網絡鏈路模型

根據空間信息網絡特點,星間鏈路模型[10]可描述為:

Link={L(i,j),TLink(i,j),l(i,j),C(i,j)}

(7)

其中,L(i,j)表示si星和sj星之間的星間鏈路,l(i,j)表示此鏈路的長度,C(i,j)為鏈路容量.

2.3 評價指標

空間信息網絡拓撲G={Sat,Link}是由Sat=N個節點和Link=M條鏈路所組成.圖G中wij表示節點i和j之間的邊權值,其中邊權值用來表示節點之間信息流通的難易程度,數值越小信息流通越容易,網絡傳輸效率越高.本文定義邊權值為兩節點之間最短路徑上的邊數,用d表示.本文中網絡效率指標E[11]定義為

(8)

本文中定義移除節點k后網絡的魯棒性為:

(9)

(10)

其中,pk表示節點k被移除的概率.

2.4 問題建模

本文所提出的優化問題可形式化描述為:給定衛星網絡拓撲圖G(Sat,Link)和正整數q,如何合理的選擇有限節點集Sat′,添加有限邊集Link′(Link′≤q&& Link′∩Link==φ),使得重構后的拓撲圖G′(Sat,Link∪Link′)具有最優可生存性,其中網絡生存性用指標Q來衡量,即使Q(G′)取得最大值.

在有限資源的情況下可生存性可描述為:

Max Q(G′(Sat,Link∪Link′))

(11)

s.t. Link′={(u1,v1),(u2,v2),…,(us,vs)}

(11-a)

us,vs∈Sat,us≠vs,(u1,v1)?Link,s∈[1,N]

(11-b)

degree≤Maxdegree

(11-c)

TLink≥TLimit

(11-d)

dAB≤dmax

(11-f)

ξ≤ξmax

(11-g)

C(i,j)≥Cmin

(11-h)

其中,可生存性指標Q(0≤Q≤1)描述了節點移除對網絡通信效率的影響,反映了系統維持通信功能、適應環境變化的能力,在重構鏈路時必須滿足述約束關系式(11-a)-(11-f).

3 基于改進蜂群算法的網絡拓撲重構算法

3.1 優化目標及基本思路

為求解空間信息網絡拓撲重構問題,本文提出一種基于改進蜂群算法的拓撲重構方法.基本思想是在衛星網絡發生節點失效的情況下,以節點最大功率為搜索半徑尋找潛在可連通節點,以連可通時間和可連接度為約束條件篩選過濾節點,然后通過蜂群算法迭代出最優節點進行鏈路連接以完成網絡拓撲重構,使重構后的網絡具有良好的網絡效率和較高的抗毀性.在重構實現過程中,選擇適宜節點完成網絡拓撲重構有三方面的重構目標.其一,改善衛星網絡在隨機故障和選擇性攻擊情況下的網絡抗毀性;其二,通過改善網絡中節點之間通信狀態,提升網絡通信效率;其三,延長網絡生存時間.

為實現這些目標,本方法實現過程的基本思路如下:

1)改善網絡有效性,鑒于選擇性攻擊中,關鍵節點及其連接邊容易成為目標對象,而連通度較低的節點及連接邊更容易生存下來.在本方法中,我們更傾向于優先選擇連接那些連通度較低的節點.此外,連接那些連通度較低的節點也能有效地改善網絡中度分布的不均勻性,進而改善網絡抗毀性.

2)改善網絡傳輸效率,通過選擇適宜節點重構,使重構后所形成的網絡具有穩定高效的鏈路通信能力,保證數據穩定傳輸.

3)節約成本,在選擇節點重構時把可連通時間作為一個約束條件,使整個網絡的穩定通信時間延長,降低頻繁重構所帶來的不必要開銷.

3.2 人工蜂群算法簡介

人工蜂群算法(Artiticial Bee Colony Algorithm,ABC)[12-14]是一種根據蜜蜂采蜜行為所提出的群智啟發式迭代算法,其組成要素主要有食物源、引領蜂、跟隨蜂和偵察蜂,其中蜜蜂所搜尋的蜜源代表待求解問題的一個可能解,用適用度值的大小來描述該食物源豐富度等相關信息,通過不斷更新食物源的位置以及對其周圍進行鄰域搜尋的方式來更新局部最優解,從而獲得全局最優解.ABC算法在求解多約束優化問題方面的應用已較為成熟[15-17].下面闡述運用ABC算法求解空間信息網絡拓撲重構問題的具體過程.

3.3 改進的蜂群算法

3.3.1 解的描述

運用ABC算法進行空間網絡拓撲重構時,解(x)代表了待重構節點功率可達周圍內所有滿足約束模型的候選節點,比如:待重構節點周圍有N個后選節點,則重構問題的具有N個可能解,每一個解就代表重構時一種鏈路鏈接的可能,其適應度的大小代表重構后網絡狀態情況(計算過程見下3.3.2),該算法所求得使適應度值最大的函數解,即為在當下最優重構方案.

3.3.2 適應度相關表達式

對于一個待求解(x),其適應度計算表達式(即目標函數)為:

(12)

3.3.3 待求解(x)初始化

設置算法種群的規模(N),隨機從種群中選取N/2個初始解,依次與待重構衛星節點連接斷開測算,并計算各解所對應的適應度值,保留適應度的最大值和最小值最為鄰域搜索公式的xmin和xmax變量.

3.3.4 解的鄰域尋優

在ABC算法尋找最優食物源的過程中,需要在一個食物源的附近進行搜索更新,確保周圍是否存在比當前位置資源更豐富的食物源,將這種行為成為鄰域尋優行為,求得的問題解稱之為鄰域解,在ABC算法中解的鄰域操作是一個局部尋優的過程,所以選擇一個怎樣的鄰域更新方式對算法的性能表現具有很大的影響,本文采用等概率隨機抽取的方式來對當前食物源進行鄰域尋優操作,算法過程如下:取當前解對應的x,將該值經過等概率隨機選取函數處理后生成一個鄰域節點,即解(xp,xq).本文在進行鄰域操作時采用貪心算法來選擇較優解,計算比較二者的適應度值(f(xp),f(xq)).如果f(xp)>f(xq),則選擇xp,否則選擇xq.

3.3.5 最優解xbest

傳統的ABC算法存在容易陷入局部最優和后期較慢的問題,為克服該問題本文提出一種引入全局因子的位置更新公式:

Vij=xij+rij(xmj-xkj)+f(xbest,j-xij)

(13)

其中,Vij表示在當前食物源xij進行局部更新搜索所求出的新的待求解食物源位置;k,m∈{1,2,…,N},其中k,m,j都是通過等概率隨機選組函數所生成的隨機數,k、m和i三者互斥,rij∈[-1,1],xbest,j表示目前所求得的最優問題解.傳統蜂群算法在進行局部搜索更新操作時僅僅向著rij(xmj-xkj)所表示的矢量方向搜尋更新,尋找方向受到了限制,并且缺乏兩個鄰域解之間比較的過程.蜂群尋找最優食物源的過程是一種群體進化的過程,蜂群中每個蜜蜂都可以從其他蜜蜂尋蜜過程中獲得進步成長,但是傳統的蜂群算法缺乏這方面的考慮,僅僅比較每個蜜蜂每一次的尋蜜過程.所以在原公式的基礎上加上了全局引導因子xbest,j-xij,使蜜蜂的搜索行為具有了全局進行性,并且加強改善了方向性.通過加入影響因子φ來控制更新優化行為的大小.從位置更新公式的組成元素可以看出,當前位置和最優位置之間搜索距離大小是動態更新的.而且,為了避免算法在更新過程中發生丟棄局部最優解的情況,用一個局部變量lm來保存迭代過程中產生的最優重構方式,用xbest,j來保存全局最優解,該解對應的重構方案即為全局最優重構連接方案.

3.4 算法步驟

利用改進蜂群算法對衛星網絡進行拓撲重構的步驟如下:

1)當網絡拓撲中發生節點失效的情況時,網絡局部鏈路的時延會急劇上升.將涉及鏈路的節點編號為s(s=1…N),開始以Rmax(Rmax=k·Tmax·v均值,其中k為調節系數,v為網絡中節點可移動速度的平均值,Tmax最大可工作時間)為半徑搜索區域內可達節點,并以鏈接條件為約束(星間鏈路長度小于最大鏈路長度,星間鏈路鏈接時間大于最短鏈接時間),確立編號為1的種群規模ms,最大迭代次數Lmax,初始化ls用于記錄遍歷次數,令全局變量v=1.依次建立剩余編號衛星的待求解節點集合,直到所有節點遍歷完成.

4)xbest即為本次算法得到的最優解,對應的鏈路連接即為本次重構最優鏈路選擇.

5)分別以編號為2-n的衛星節點為初始節點,重復Step1.

6)根據Step 3的結果,如果存在衛星節點維持的星間鏈路數目大于4條的情況,則需要刪除多余的星間鏈路.刪除鏈路的依據是在衛星節點的整體可達性不變的情況下刪除被選擇概率p最小的鏈路.如果存在兩條可刪除的被選擇概率相同,則刪除節點剩余連通時間較小的鏈路.如果一個衛星節點存在的鏈路數目小于4,則建立被選擇概率最大的鏈路,以確保任意兩個衛星節點間的星間鏈路的數目均等于衛星節點的度,退出程序.

4 仿真分析

4.1 仿真平臺與仿真環境

本文所采用的仿真軟件為ONE1.5和STK,雖然ONE1.5仿真軟件對于DTN網絡具有良好的支持性,但其不支持衛星網絡.所以需要先通過STK軟件獲取當前衛星網絡節點分布及鏈路鏈接情況,導出并降維成二維直角坐標系上的數據,然后在OpenJUMP中進行編輯定義處理,最后,顯示出相關仿真結果.

本文所選衛星模型為銥星網絡模型,具體在參數如表1所示.

綜合考慮衛星網絡的連通性、系統成本以及衛星處理能力等因素,本文選取的衛星節點的最大連接度等于4.

4.2 算法重構時間仿真

由圖1中可以看出,ACO算法的收斂時間要高于其余兩種算法,其主要原因是傳統的ACO算法雖然具有良好的探索能力,但開發能力不足,在算法初期,由于鏈路上缺乏信息素引導,只能隨機的選擇下一節點連接, 故收斂時間較長.ABC算法通過迭代完成衛星的網絡重構,但隨著衛星個數的增多,其操作所需的時間增多,并且易陷入局部最優解,導致重構時間較長.本文所提出的IABC算法利用改變初始節點選取以及節點信息增量的方法,減少了算法的收斂時間,進而優化了整個網絡的重構時間.

圖1 重構時間仿真Fig.1 Reconstruction time simulation

表1 衛星網絡仿真參數Table 1 Satellite network simulation parameters

4.3 算法效率仿真

從圖2中可以看出,TPC算法分組投遞率會隨著損壞節點的數量增多而減小,這是由于當節點損壞較多時,單純的通過功率調節無法完成拓撲的重構,易產生拓撲漏洞,導致網絡整體效率降低;ACO算法當節點損壞較少時網絡效率可以接受,當節點損壞超過一定數目時,選擇節點時易陷入局部最優解問題,導致網絡效率下降.IABC算法根據篩選條件可過濾掉差、劣節點,使重構選擇節點時讓網絡效率大體上維持一個高位值.