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

?

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

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

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

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

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

1 引言

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

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

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

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

2 模型分析

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

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

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

(1)禁忌表Tabu()用來(lái)存儲(chǔ)時(shí)刻螞蟻已經(jīng)到達(dá)過(guò)的所有節(jié)點(diǎn)。

(3)D()表示時(shí)刻節(jié)點(diǎn)和間的距離。

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

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

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

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

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

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

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

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

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

2.3 小窗口策略

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

圖1 波長(zhǎng)分配示意圖

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

圖2 網(wǎng)絡(luò)虛擬拓?fù)?/p>

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

圖3 小窗口策略示意圖

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

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

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

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

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

3 仿真分析

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

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

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

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

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

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

圖4 擁塞率對(duì)比??????????????圖5 資源利用率對(duì)比

圖6 不同波長(zhǎng)數(shù)目時(shí)擁塞率對(duì)比

圖7 收斂性能對(duì)比

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

4 結(jié)論

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

[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] 李世強(qiáng), 禹衛(wèi)東. 分布式衛(wèi)星SAR相位同步的實(shí)現(xiàn)方案及試驗(yàn)驗(yàn)證[J]. 電子與信息學(xué)報(bào), 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] 程希, 沈建華. 一種基于改進(jìn)蟻群算法的光網(wǎng)絡(luò)波長(zhǎng)路由分配算法[J]. 電子與信息學(xué)報(bào), 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ò)中動(dòng)態(tài)及分布式RWA問(wèn)題的方法[J]. 北京理工大學(xué)學(xué)報(bào), 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

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

The National Natural Science Foundation of China (61231012)

董 毅： 男，1987年生，博士生，研究方向?yàn)榧す饪臻g信息技術(shù).

趙尚弘： 男，1964年生，教授，博士生導(dǎo)師，研究方向?yàn)榧す馀c光通信技術(shù).

李永軍： 男，1979年生，副教授，碩士生導(dǎo)師，研究方向?yàn)楣馔ㄐ偶夹g(shù).

趙 靜： 女，1988年生，博士生，研究方向?yàn)榧す饪臻g信息技術(shù).

鄧博于： 男，1991年生，碩士生，研究方向?yàn)榧す饪臻g信息技術(shù).