基于蟻群算法的分布式衛(wèi)星光網(wǎng)絡(luò)波長路由分配技術(shù)研究

董 毅 趙尚弘 李勇軍 趙 靜 鄧博于

?

基于蟻群算法的分布式衛(wèi)星光網(wǎng)絡(luò)波長路由分配技術(shù)研究

董 毅*趙尚弘 李勇軍 趙 靜 鄧博于

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院 西安 710077)

為了解決分布式衛(wèi)星光網(wǎng)絡(luò)波長路由分配復(fù)雜的問題，論文提出基于小窗口策略的蟻群優(yōu)化算法。采用鏈路可持續(xù)時間和波長空閑率作為啟發(fā)函數(shù)，在實現(xiàn)負載均衡的同時，降低網(wǎng)絡(luò)的擁塞率；引入小窗口策略引導(dǎo)螞蟻在最小路由請求區(qū)域內(nèi)進行選路，提高了算法的收斂速度；通過計算相鄰鏈路空閑波長的交集，實現(xiàn)了由單只螞蟻同時完成路由選擇和波長分配。對單主星和雙主星兩種場景下的算法性能進行了仿真分析，結(jié)果表明：與經(jīng)典的Dijkstra+FF算法相比較，單主星和雙主星時的網(wǎng)絡(luò)擁塞率最高分別降低了0.5和0.7，網(wǎng)絡(luò)資源利用率改善最高可達到0.45和0.50。

分布式衛(wèi)星光網(wǎng)絡(luò)；波長路由分配；蟻群算法；小窗口策略；擁塞率

1 引言

氣象、環(huán)境和軍事領(lǐng)域應(yīng)用的不斷拓展，一方面使衛(wèi)星傳輸?shù)男畔⒘砍尸F(xiàn)出爆炸式的增長，另一方面，對衛(wèi)星的功能也提出了新的要求，如立體成像、精確定位等。這對于目前基于微波鏈路的衛(wèi)星網(wǎng)絡(luò)提出了挑戰(zhàn)。而基于激光鏈路的分布式衛(wèi)星系統(tǒng)由于能夠提供雷達探測所需要的各種基線組合，具有抗摧毀性強，技術(shù)更新快，成本低等優(yōu)勢，同時兼具光通信高速率、寬帶寬的特點，能夠很好地滿足未來各種空間業(yè)務(wù)的技術(shù)要求。

在分布式衛(wèi)星光網(wǎng)絡(luò)中，路由技術(shù)是決定整個網(wǎng)絡(luò)性能的重要方面。其中，波長路由能夠提供粗的交換粒度，對于具有大量遙感探測和視頻信息的業(yè)務(wù)，能夠避免頻繁的復(fù)用和解復(fù)用過程，提高路由的效率。波長路由的核心問題是波長和路由的分配(RWA)問題，而動態(tài)的RWA問題已經(jīng)被證明是NP-hard問題[4,5]。最初的解決辦法是將RWA問題分解為路由選擇和波長分配兩個問題，即先選路，再根據(jù)一定的策略對路徑進行波長分配。分圖層模型[6]通過將物理拓撲映射成多個分層圖的方法，將動態(tài)的RWA問題分解成一個3維模型；整數(shù)線性規(guī)劃(ILP)方法[7,8]是通過求解多約束條件下目標(biāo)函數(shù)的最大或最小化問題來處理RWA問題。盡管兩種方法都能最終找到最優(yōu)的解，但是算法耗時過長，對于大型網(wǎng)絡(luò)是不可接受的。利用遺傳算法解決動態(tài)RWA問題能夠縮短選路的時間，但是算法的收斂性較差，存在容易陷入局部最優(yōu)的問題。采用蟻群算法不僅可以實現(xiàn)負載均衡和多目標(biāo)優(yōu)化，而且可以使路由選擇和波長分配同時完成，為解決動態(tài)RWA問題提供了一種新的思路。

然而，到目前為止，有關(guān)波長路由的研究大都是基于地面光纖網(wǎng)絡(luò)的，對衛(wèi)星光網(wǎng)絡(luò)的波長路由問題研究卻非常少。事實上，衛(wèi)星光網(wǎng)絡(luò)中的動態(tài)RWA問題是一個比地面光網(wǎng)絡(luò)更加復(fù)雜的問題，因為它要同時考慮多個因素的限制，例如：星間距離處在不斷變化中；衛(wèi)星的持續(xù)運動造成不同鏈路的可持續(xù)時間是不一樣的；衛(wèi)星網(wǎng)絡(luò)中對光通路的評價需要綜合考慮跳數(shù)、路徑可持續(xù)時間以及延時等多個因素。尤其是分布式衛(wèi)星網(wǎng)絡(luò)中衛(wèi)星數(shù)目增多，信息交換更加頻繁，進一步增加了RWA的復(fù)雜性。

基于此，本文提出了一種基于小窗口策略的蟻群優(yōu)化算法，來解決分布式衛(wèi)星網(wǎng)絡(luò)中RWA的復(fù)雜性問題。算法通過將螞蟻選路限制在最小路由請求區(qū)域內(nèi)，降低了運算量，提高了路由搜索的收斂速度。

2 模型分析

2.1 轉(zhuǎn)移概率函數(shù)

蟻群優(yōu)化算法是模擬自然界中螞蟻尋找路徑行為得到的一種仿生算法。研究人員經(jīng)過不斷的追蹤，發(fā)現(xiàn)螞蟻群體總能在一定時間內(nèi)找到從蟻穴到食物源的一條最短通路。這是因為螞蟻在覓食的過程中會在所走過的路徑上留下一些被稱作“信息素”的揮發(fā)性化學(xué)物質(zhì)。而這些“信息素”會被同一群體中后續(xù)的螞蟻感知到，并影響后續(xù)螞蟻的尋路行為。實驗證明，螞蟻選擇信息素濃度高的路徑的概率要比選擇信息素濃度低的路徑概率大。將網(wǎng)絡(luò)中尋找路由的過程抽象成螞蟻的覓食過程，轉(zhuǎn)移概率函數(shù)用來衡量螞蟻從一個節(jié)點向下一跳節(jié)點轉(zhuǎn)移的概率大小。假設(shè)網(wǎng)絡(luò)中每一條鏈路都有相同數(shù)目的可用波長，每一個節(jié)點都維持一張路由表用來存放可選節(jié)點的地址和相應(yīng)的轉(zhuǎn)移概率。當(dāng)每一只螞蟻到達一個節(jié)點時，首先要判斷該節(jié)點是否為目的節(jié)點，如果不是，那么就將該節(jié)點放入禁忌表中并依據(jù)轉(zhuǎn)移概率大小前往下一節(jié)點。以此重復(fù)，直到到達目的節(jié)點為止。

為了給出轉(zhuǎn)移概率函數(shù)的表達式，首先對算法中涉及到的概念和主要參數(shù)進行說明。

(1)禁忌表Tabu()用來存儲時刻螞蟻已經(jīng)到達過的所有節(jié)點。

(3)D()表示時刻節(jié)點和間的距離。

(4)波長空閑率I()表示時刻節(jié)點和間空閑波長數(shù)占總波長數(shù)的概率，由式(1)給出：

式中，為節(jié)點間的波長總數(shù)，n()為時刻節(jié)點和間被占用的波長數(shù)。

(5)TK()表示從時刻算起，鏈路L可持續(xù)的時間。在極軌星座中，由于衛(wèi)星運行到極地地區(qū)時相對速度比較高，相鄰軌道間衛(wèi)星通信設(shè)備處于關(guān)閉狀態(tài)，因此即將進入極地地區(qū)的軌間鏈路可持續(xù)時間將小于赤道附近軌間鏈路的可持續(xù)時間。

綜合考慮星間距離、鏈路可持續(xù)時間和波長空閑率的限制，節(jié)點間的概率轉(zhuǎn)移函數(shù)為

為了能夠利用前面螞蟻選路留下的信息，在每一代螞蟻完成選路后需要對信息素進行更新。更新的原則為：被前面螞蟻選到的鏈路，其信息素適當(dāng)?shù)卦黾樱瑳]有被前面螞蟻選到的鏈路，其信息素適當(dāng)?shù)販p少。假設(shè)為上一代螞蟻選路時鏈路L上的信息素，則這一代螞蟻選路時的信息素更新為

對于單只螞蟻在鏈路L上產(chǎn)生的信息素的計算，采用基于全局信息的Ant-Cycle模型能夠保證信息素和期望值的均衡發(fā)展，其表達式為

式中，為上一代螞蟻完成選路留下的總的信息素，J為螞蟻經(jīng)過的路徑長度。

2.2 波長和路由分配規(guī)則

為了實現(xiàn)路由選擇和波長分配由一只螞蟻同時完成，本文采用可用波長求交集的思想。當(dāng)螞蟻到達每一個節(jié)點時，首先查找以該節(jié)點為端點的各個鏈路的可用波長情況，然后決定前往哪一個節(jié)點。如果各條鏈路均沒有可用波長，則宣告本次選路失敗。具體過程如圖1所示。螞蟻從節(jié)點1出發(fā)，當(dāng)?shù)竭_節(jié)點2時，首先搜索拓撲情況并對照禁忌表確定可選的下一跳節(jié)點。然后分別計算12上可用波長(1,2)與23,24,25上可用波長(2,3),(2,4),(2,5)的交集。由于3個交集均不為空，因此節(jié)點3, 4, 5都可作為下一跳節(jié)點。假設(shè)依據(jù)狀態(tài)轉(zhuǎn)移概率選擇了節(jié)點5，記錄當(dāng)前可用波長集合(1,2)∩(2,5)，并計算(1,2)∩(2,5)與(5,6),(5,7),(5,8) 的交集。此時發(fā)現(xiàn)，節(jié)點6和節(jié)點8仍然能夠滿足要求，而(5,7)與(1,2)∩(2,5)的交集為空，所以節(jié)點7不能作為下一跳節(jié)點。以此類推，在每一個節(jié)點上重復(fù)該過程，當(dāng)螞蟻到達目的節(jié)點時就可以同時完成路由的選擇和波長的分配。

2.3 小窗口策略

為了后文表述清楚，先對星座和星群的概念加以區(qū)分。星座是指為了增加衛(wèi)星對地面的覆蓋區(qū)域或縮短重訪時間，由多顆衛(wèi)星稀疏分布組成的衛(wèi)星空間結(jié)構(gòu)，星座中各衛(wèi)星之間無動力學(xué)聯(lián)系，根據(jù)需要星間通信可有可無；星群是指為了實現(xiàn)一個大的“虛擬衛(wèi)星”功能，由多顆衛(wèi)星密集分布組成的衛(wèi)星空間結(jié)構(gòu)，星群中各衛(wèi)星之間滿足嚴格的動力學(xué)關(guān)系和約束條件，各星之間分布距離短，且需要通過頻繁的星間通信和信息交換共同完成空間任務(wù)。本文提到的星群實際包含兩個層面：首先是單個星群，即分布在很小空間范圍內(nèi)的、類似于一個大“虛擬衛(wèi)星”的編隊衛(wèi)星；其次，是由多個星群組成的一個大的星座，每一個星群相當(dāng)于星座中的一個衛(wèi)星。

圖1 波長分配示意圖

為了實現(xiàn)分布式星群內(nèi)部以及星群之間的通信，目前主要采用兩級結(jié)構(gòu)的網(wǎng)絡(luò)拓撲，即每個星群內(nèi)有一個“主星”，負責(zé)管理群內(nèi)各顆衛(wèi)星之間的通信并與其它星群的主星相互交換信息。然而，當(dāng)數(shù)據(jù)量較大時，一顆主星既要與星群內(nèi)部多顆衛(wèi)星通信，又要負責(zé)星群間的通信，通信阻塞的概率和風(fēng)險隨之增大。基于此，研究人員又提出了“雙主星”的結(jié)構(gòu)，用于提高通信的靈活性和分擔(dān)風(fēng)險。圖2給出了單主星和雙主星兩種結(jié)構(gòu)下星群間通信的虛擬拓撲。單主星結(jié)構(gòu)時受天線數(shù)目限制，每個星群只能與前后左右4個星群建立鏈路，如圖2(a)所示；采用雙主星結(jié)構(gòu)時，由于可用的天線數(shù)目翻倍，并且兩顆主星可以分別控制所屬天線的姿態(tài)，每個星群可以與周圍8個星群建立鏈路，如圖2(b)所示。

圖2 網(wǎng)絡(luò)虛擬拓撲

蟻群算法在解決RWA問題時螞蟻的選路是基于全網(wǎng)所有的可達節(jié)點，而隨著節(jié)點數(shù)目的增加，算法的運算量將按指數(shù)形式增長。當(dāng)網(wǎng)絡(luò)規(guī)模比較大，或者采用雙主星結(jié)構(gòu)時，大的運算量將使算法的收斂速度降低，影響路由的時效性。為了降低運算量，提高算法的收斂速度，本文借鑒輔助定位按需路由(LAOR)算法中限定請求區(qū)域的方法，將路由選擇的開銷保持在最低限度。該方法的理論基礎(chǔ)是，對于給定的源和目的衛(wèi)星節(jié)點，基于傳輸延時的最短路徑通常位于由該目的和源節(jié)點確定的最小矩形區(qū)域內(nèi)，稱為最小路由請求區(qū)域(MRRR)。根據(jù)源節(jié)點和目的節(jié)點的位置，MRRR的確定可以分為兩種情況，如圖3所示。圖中為一個軌道內(nèi)衛(wèi)星的個數(shù)。如果源/目的節(jié)點的坐標(biāo)滿足不等式，則MRRR如圖3(a)所示；如果滿足，則MRRR如圖3(b)所示。

圖3 小窗口策略示意圖

MRRR限制了路由搜索的范圍，為了保證算法實現(xiàn)過程中每只螞蟻的選路都能在MRRR規(guī)定范圍內(nèi)的節(jié)點進行，需要對轉(zhuǎn)移概率函數(shù)進行適當(dāng)?shù)匦薷?，如?5)所示：

式中，M表示由源/目的節(jié)點(,)確定的MRRR內(nèi)的節(jié)點集合。MRRR就像為每一只螞蟻安裝的窗戶一樣，只有落在窗口內(nèi)的節(jié)點才能被選擇為下一跳節(jié)點，因此我們稱這種算法為基于小窗口策略(Small Window Strategy, SWS)的蟻群算法。

值得一提的是，基于蟻群算法的波長路由技術(shù)在每個節(jié)點的選路策略均是基于全網(wǎng)信息進行的；在這種場景中，如果不加任何限制，對于分布式衛(wèi)星網(wǎng)絡(luò)節(jié)點數(shù)目多、信息交換頻繁的情況，由全網(wǎng)信息更新產(chǎn)生的額外開銷將是非常巨大的。針對這一問題，我們在網(wǎng)絡(luò)信息更新時也采用了類似于小窗口策略的思想，對網(wǎng)絡(luò)信息交換的范圍進行了一定的限制，具體方法為：當(dāng)網(wǎng)絡(luò)中任意兩個節(jié)點需要進行通信時，以該源/目的節(jié)點連線為對角線畫矩形區(qū)域，在本次鏈路建立過程中，當(dāng)前節(jié)點選路所需要的“全網(wǎng)信息”都只限定在該矩形區(qū)域內(nèi)；并且只有當(dāng)路徑請求產(chǎn)生時才進行“全網(wǎng)信息”的更新，無請求則不更新。基于該思想獲得的更新信息不僅能滿足文中蟻群算法的應(yīng)用需求，而且大大降低了傳統(tǒng)全網(wǎng)信息交換造成的巨大額外開銷。

根據(jù)以上分析，基于SWS的蟻群算法偽代碼如表1所示，終止條件為達到迭代次數(shù)。

表1小窗口策略(SWS)的蟻群算法偽代碼

3 仿真分析

本文以極軌星座的分布式衛(wèi)星網(wǎng)絡(luò)為例對基于小窗口策略的蟻群算法性能進行仿真，包括單主星和雙主星兩種結(jié)構(gòu)，虛擬拓撲如圖2中所示。仿真中，假設(shè)星群內(nèi)部信息交互暢通，因此將每一個分布式星群抽象為一個衛(wèi)星節(jié)點，對于雙主星結(jié)構(gòu)按照圖2(b)中8條星間鏈路的方式處理。星座包含6個軌道面，每個軌道面內(nèi)12個節(jié)點。反向縫兩側(cè)的衛(wèi)星無法建立星間鏈路，當(dāng)衛(wèi)星運行至南北緯時軌間鏈路關(guān)閉。對于星間距離，建立星間距離鄰接矩陣，將每顆衛(wèi)星周圍能與之建立鏈路的衛(wèi)星星間距離按照大小比例設(shè)置為有限常數(shù)，距離較遠而無法通信的衛(wèi)星星間距離設(shè)為無窮大。對于鏈路可持續(xù)時間，建立鏈路可持續(xù)時間的鄰接矩陣，同一軌道內(nèi)前后兩顆衛(wèi)星鏈路可持續(xù)時間為1；按照大小比例，不同軌道間兩個衛(wèi)星越向著極地運動，鏈路可持續(xù)時間越小。對于波長空閑率，每只螞蟻在當(dāng)前節(jié)點根據(jù)下一跳可到達節(jié)點及通往該節(jié)點的波長使用情況，計算每一個可用波長的空閑率。所有節(jié)點沒有波長轉(zhuǎn)換能力和排隊等待機制，因此光通路必須遵循波長連續(xù)性限制，并且路由請求一旦被拒絕，將立即被拋棄。仿真中設(shè)定迭代次數(shù)為100次，每次迭代共有30只螞蟻。由于仿真中源和目的節(jié)點是隨機產(chǎn)生的，所有的結(jié)果將通過統(tǒng)計平均得出。

圖4給出了單主星和雙主星情況下網(wǎng)絡(luò)的擁塞率性能，Dijkstra+FF算法用于對比參照。仿真中，每顆衛(wèi)星與相鄰衛(wèi)星之間有4個可用波長?？梢钥闯觯诤艽蟮臉I(yè)務(wù)強度范圍內(nèi)蟻群算法的擁塞率要明顯低于Dijkstra+FF算法，單主星時，擁塞率改善最高可以達到50%，而雙星是可高達70%。與單主星的情況相比，雙主星的網(wǎng)絡(luò)擁塞率在低業(yè)務(wù)強度時只是略有改善，但當(dāng)業(yè)務(wù)強度比較大時擁塞率改善十分顯著。這是因為當(dāng)業(yè)務(wù)強度比較低時，無論是單主星還是雙主星，網(wǎng)絡(luò)可用資源都比較多，出現(xiàn)擁塞的概率也比較??；但是當(dāng)業(yè)務(wù)強度比較大時，雙主星的可用網(wǎng)絡(luò)資源要明顯多于單主星，因此擁塞率也明顯要低。

圖5為3種場景下網(wǎng)絡(luò)資源利用率的對比情況。從圖中可以看出，單主星和雙主星情況下，蟻群算法的資源利用率都要明顯高于Dijkstra+FF算法，在不同的業(yè)務(wù)強度下最大可分別高出0.45和0.50。同時，單主星時利用率隨著業(yè)務(wù)強度的增加單調(diào)下降，而雙主星時利用率先增大，隨后開始減小。這是因為隨著業(yè)務(wù)強度的增加，越來越多的波長信道不斷被占用，單主星時由于可用的網(wǎng)絡(luò)資源相對較少，因此距離較遠的源/目的節(jié)點由于受波長連續(xù)性限制難以找到光通路，因此對網(wǎng)絡(luò)資源的利用率逐漸減??；雙主星時，由于增加了與傾斜方向4顆衛(wèi)星之間的鏈路，相同業(yè)務(wù)強度條件下網(wǎng)絡(luò)資源要明顯多于單主星，業(yè)務(wù)強度開始增加時并不影響源/目的節(jié)點的找路，但當(dāng)業(yè)務(wù)強度增加到一定程度時網(wǎng)絡(luò)資源出現(xiàn)短缺，因此出現(xiàn)了類似于單主星時利用率下降的情況。

圖6給出了單主星和雙主星情況時不同波長數(shù)目條件下網(wǎng)絡(luò)的擁塞率對比，圖中所標(biāo)注的波長數(shù)均指單顆衛(wèi)星之間的可用波長數(shù)。從圖中可以看出，兩種情況下，增加波長數(shù)均能降低網(wǎng)絡(luò)的擁塞率；對于單主星的情況，業(yè)務(wù)強度在130 Erl以下，擁塞率保持緩慢增長，超過130 Erl后增長較快；雙主星時由于增加了可用的鏈路數(shù)，業(yè)務(wù)強度在210 Erl時擁塞率仍然保持緩慢增長，并且在100 Erl以下出現(xiàn)了“0”擁塞的情況。

圖7對比了基于小窗口策略和無小窗口策略的蟻群算法在單主星和雙主星網(wǎng)絡(luò)中應(yīng)用時的收斂特性。為了充分觀察算法的性能，仿真中選取距離較遠的(7,1)和(2,6)兩個節(jié)點分別作為源節(jié)點和目的節(jié)點(如圖2中所示)，網(wǎng)絡(luò)業(yè)務(wù)強度設(shè)置為170 Erl。從圖中可以看到，對于單主星的情況，無小窗口策略時算法在第55次迭代時收斂于最佳路徑，而帶小窗口策略時在第25次迭代時就開始收斂，減少了30次迭代；對于雙主星的情況，無小窗口策略時算法收斂于75次迭代，而小窗口策略時收斂于48次迭代，減少了27次迭代。另外，與單主星情況相比，雙主星由于增加了傾斜方向上的4條鏈路，最佳路徑的跳數(shù)變?yōu)?跳，比單主星減少了3跳；然而，也正是由于可選的鏈路數(shù)增加，無小窗口和有小窗口策略時其收斂的時間也分別推遲了20和23次迭代。

圖8以單主星情況為例，對基于小窗口策略和無小窗口策略的蟻群算法性能做了進一步的對比。圖8(a)給出了兩種情況下最佳路徑跳數(shù)的對比，其中橫坐標(biāo)為整個網(wǎng)絡(luò)的平均波長利用率，縱坐標(biāo)為通過計算100對源/目的節(jié)點得到的最佳路徑跳數(shù)的平均值。從圖中可以看出，小窗口策略得到的最佳路徑跳數(shù)要少于無小窗口的情況。圖8(b)為兩種情況下的擁塞率對比?？梢钥闯?，隨著網(wǎng)絡(luò)平均波長利用率從0.1增加到0.8，無小窗口時的擁塞率始終略低于小窗口策略時。這是因為MRRR限制了路由選擇的區(qū)域，將一部分可選的節(jié)點排除在外。也就是說，小窗口策略是通過犧牲一定的擁塞率來降低蟻群算法的運算量，提高路由搜索的收斂速度。

圖4 擁塞率對比??????????????圖5 資源利用率對比

圖6 不同波長數(shù)目時擁塞率對比

圖7 收斂性能對比

圖8 最佳路徑跳數(shù)和擁塞率對比

4 結(jié)論

為了解決分布式衛(wèi)星光網(wǎng)絡(luò)波長路由分配復(fù)雜的問題，本文設(shè)計了一種基于小窗口策略的蟻群優(yōu)化算法，并對算法在單主星和雙主星網(wǎng)絡(luò)結(jié)構(gòu)中的性能進行了仿真分析。與經(jīng)典的Dijkstra+FF算法相比，單主星和雙主星時的網(wǎng)絡(luò)擁塞率最高分別降低了0.5和0.7，網(wǎng)絡(luò)資源利用率改善最高可達到0.45和0.50。盡管引入小窗口策略后一定程度地犧牲了網(wǎng)絡(luò)擁塞率，但是無論是單主星還是雙主星結(jié)構(gòu)，算法的收斂速度都顯著提高，這對于網(wǎng)絡(luò)規(guī)模大、節(jié)點數(shù)目多的分布式衛(wèi)星網(wǎng)絡(luò)具有很好的現(xiàn)實應(yīng)用價值。

[1] Dang Zhao-hui and Zhang Yu-lin. Optimization of communication network topology for navigation sharing among distributed satellites[J]., 2013, 51(1): 143-152.

[2] 李世強, 禹衛(wèi)東. 分布式衛(wèi)星SAR相位同步的實現(xiàn)方案及試驗驗證[J]. 電子與信息學(xué)報, 2012, 34(2): 356-360.

Li Shi-qiang and Yu Wei-dong. Implementation and verification for phase synchronization of distributed satellite SAR[J].&, 2012, 34(2): 356-360.

[3] Sandau R. Status and trends of small satellite missions for Earth observation[J]., 2010, 66(1/2): 1-12.

[4] 程希, 沈建華. 一種基于改進蟻群算法的光網(wǎng)絡(luò)波長路由分配算法[J]. 電子與信息學(xué)報, 2012, 34(3): 710-715.

Cheng Xi and Shen Jian-hua. An improved ant colony algorithm for routing and wavelength assignment in optical networks[J].&, 2012, 34(3): 710-715.

[5] Karasan E and Ayanoglu E. Performance of WDM transport networks[J]., 1998, 16(7): 1081-1096.

[6] Xu Shi-zhong, Li Le-min, and Wang Sheng. Dynamic routing and assignment of wavelength algorithms in multifiber wavelength division multiplexing network[J]., 2000, 18(10): 2130-2137.

[7] Yetginer E, Liu Ze-yu, and Rouskas G N. Fast exact ILP decompositions for ring RWA[J]., 2011, 3(7): 557-586.

[8] Krishnaswamy R M and Sivarajan K N. Algorithms for routing and wavelength assignment based on solutions of LP- relaxations[J]., 2001, 5(10): 435-437.

[9] Zang S, Martel C, and Mukherjee B. Dynamic traffic grooming in elastic optical networks[J].,, 2013, 31(1): 4-12.

[10] Qin H, Zhang S, and Liu Z. Dynamic routing and wavelength assignment for limited-rang wavelength conversion[J]., 2003, 7(3): 136-138.

[11] Shen G, Bose S K, Cheng T H,.. Effcient heuristic algorithms for light-path routing and wavelength assignment in WDM networks under dynamically varying loads[J]., 2001, 24(3): 364-373.

[12] Ming Tsung-chen, Lin B M T, and Tseng Shian-shyong. Ant colony optimization for dynamic routing and wavelength assignment in WDM networks with sparse wavelength conversion[J]., 2011, 24(2): 295-305.

[13] Triay J and Cervelló-Pastor C. An ant-based algorithm for distributed routing and wavelength assignment in dynamic optical network[J]., 2010, 28(4): 542-552.

[14] 鄭滟雷, 顧畹儀, 連偉華, 等. 采用蟻群算法解決光網(wǎng)絡(luò)中動態(tài)及分布式RWA問題的方法[J]. 北京理工大學(xué)學(xué)報, 2009, 29(12): 1104-1109.

Zheng Yan-lei, Gu Wan-yi, Lian Wei-hua,.. Ant colony algorithm-distributed strategy for solving RWA problem in optical WDM network[J]., 2009, 29(12): 1104-1109.

Research on Routing and Wavelength Assignment Based on Ant Colony Optimization in Distributed Satellite Optical Network

Dong Yi Zhao Shang-hong Li Yong-jun Zhao Jing Deng Bo-yu

(,,’710077,)

To solve the complexity of Routing and Wavelength Assignment (RWA) in distributed satellite optical network, the Ant Colony Optimization (ACO) based on Small Window Strategy (SWS) is put forward. The link duration and the wavelength idle ratio are used as the heuristic functions for load balancing and decreasing the blocking probability. The small window strategy is introduced to limit the routing in the Minimum Routing Request Range (MRRR) and promote the convergence speed. By calculating the intersection of idle wavelengths on the adjacent links, the algorithm can accomplish the routing selection and wavelength assignment by a single ant. The properties of the algorithm in both single and double master satellites cases are analyzed, and the results show that compared with Dijkstra+FF algorithm, the blocking probability of ACO can reduce at most 0.5 and 0.7 for single and double master satellites respectively, and the improvement of resource utilization ratio can reach to 0.45 and 0.50.

Distributed satellite optical network; Routing and Wavelength Aassignment (RWA); Ant Colony Optimization (ACO); Small Window Strategy (SWS); Blocking probability

TN915.63

A

1009-5896(2015)11-2650-07

10.11999/JEIT150252

2015-02-22；改回日期：2015-07-03；

2015-08-24

董毅 dongyi_19870129@sina.com

國家自然科學(xué)基金(61231012)

The National Natural Science Foundation of China (61231012)

董 毅： 男，1987年生，博士生，研究方向為激光空間信息技術(shù).

趙尚弘： 男，1964年生，教授，博士生導(dǎo)師，研究方向為激光與光通信技術(shù).

李永軍： 男，1979年生，副教授，碩士生導(dǎo)師，研究方向為光通信技術(shù).

趙 靜： 女，1988年生，博士生，研究方向為激光空間信息技術(shù).

鄧博于： 男，1991年生，碩士生，研究方向為激光空間信息技術(shù).