基于混合進(jìn)化算法的衛(wèi)星網(wǎng)絡(luò)星間數(shù)傳方法

鄧 勇, 姚 鋒,*, 邢立寧, 何 磊

(1. 國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院, 湖南 長(zhǎng)沙 410073; 2. 西安電子科技大學(xué)電子工程學(xué)院, 陜西 西安 710075)

0 引 言

隨著科技的發(fā)展,衛(wèi)星網(wǎng)絡(luò)的應(yīng)用越來(lái)越廣泛,其重要性也日益顯現(xiàn)[1-5]。近年來(lái),國(guó)內(nèi)外出現(xiàn)了一批新型衛(wèi)星網(wǎng)絡(luò)的建設(shè)計(jì)劃。SpaceX公司、OneWeb公司分別提出了4.2萬(wàn)顆和648顆衛(wèi)星的網(wǎng)絡(luò)建設(shè)計(jì)劃[6],將為全球用戶(hù)提供互聯(lián)網(wǎng)接入服務(wù),可以解決地面通信不可達(dá)的問(wèn)題。國(guó)內(nèi),天地一體化信息網(wǎng)絡(luò)項(xiàng)目被列入國(guó)家“科技創(chuàng)新2030”重大項(xiàng)目,衛(wèi)星互聯(lián)網(wǎng)也被納入信息基礎(chǔ)設(shè)施的范疇,這些標(biāo)志著我國(guó)空間通信網(wǎng)絡(luò)的建設(shè)也踏上了新的征程[7]。然而,由于我國(guó)地面站的布局受到限制,境外獲取的任務(wù)數(shù)據(jù)難以直接傳輸?shù)降孛嬲?具有快速響應(yīng)要求的任務(wù)數(shù)據(jù)難以保證其時(shí)延要求。我國(guó)的北斗衛(wèi)星導(dǎo)航系統(tǒng),成功實(shí)現(xiàn)了通過(guò)星間鏈路進(jìn)行數(shù)據(jù)傳輸?shù)募夹g(shù),一定程度上能夠擺脫地面站局域分布的限制[8]。因此,研究具有星間鏈路的數(shù)據(jù)傳輸問(wèn)題,對(duì)我國(guó)構(gòu)建低軌互聯(lián)網(wǎng)、天地一體化網(wǎng)絡(luò)具有十分重要的意義。

衛(wèi)星網(wǎng)絡(luò)數(shù)據(jù)傳輸是指將衛(wèi)星生成的數(shù)據(jù)傳輸?shù)降孛嬲?。衛(wèi)星在繞軌道運(yùn)動(dòng)的過(guò)程中,衛(wèi)星與衛(wèi)星之間、衛(wèi)星與地面站之間的可見(jiàn)關(guān)系不斷變化,其鏈路隨著時(shí)間的變化而不斷地切換和重組?？刹捎脮r(shí)間切片[9]的方式,將規(guī)劃周期劃分為多個(gè)時(shí)間片,在每個(gè)時(shí)間片內(nèi)拓?fù)浣Y(jié)構(gòu)近似不變。將衛(wèi)星分為境內(nèi)星和境外星,在每個(gè)時(shí)間片內(nèi),與地面站建立星地鏈路的衛(wèi)星稱(chēng)之為境內(nèi)星,否則該時(shí)間片內(nèi)看作是境外星。衛(wèi)星在每個(gè)時(shí)間片都可能生成數(shù)據(jù),境內(nèi)星生成的數(shù)據(jù)可以直接傳輸?shù)降孛嬲?境外星生成的數(shù)據(jù)需要通過(guò)星間鏈路將數(shù)據(jù)傳輸給境內(nèi)星,然后通過(guò)境內(nèi)星的中轉(zhuǎn)傳輸給地面站。由于衛(wèi)星的運(yùn)動(dòng),境內(nèi)星、境外星之間的鏈路會(huì)間歇斷開(kāi)與重組,境外星、境內(nèi)星與地面站的可見(jiàn)性也是時(shí)變的,境內(nèi)星與境外星的角色會(huì)隨著時(shí)間變化而發(fā)生變化,境外星到地面站的端到端路徑也是時(shí)變的。

目前,已有大量的文獻(xiàn)對(duì)衛(wèi)星數(shù)據(jù)傳輸進(jìn)行了研究,提出了不少高效的算法,但是大部分集中在星地之間的數(shù)據(jù)傳輸,即利用衛(wèi)星與地面之間的可見(jiàn)時(shí)間窗,將衛(wèi)星生成的數(shù)據(jù)傳輸?shù)降孛嬲綶10-13]。近期,利用星間鏈路進(jìn)行數(shù)據(jù)的傳輸逐漸受到關(guān)注[14-18]。

針對(duì)低軌衛(wèi)星網(wǎng)絡(luò),文獻(xiàn)[19]研究了使用星間鏈路協(xié)作傳輸數(shù)據(jù)的問(wèn)題,以最大化數(shù)據(jù)下載量為目標(biāo),設(shè)計(jì)了迭代優(yōu)化算法,聯(lián)合調(diào)度星星、星地之間的鏈路,將數(shù)據(jù)從衛(wèi)星下載到地面站,并驗(yàn)證了算法的效率。Faire等[20]將鏈路分配與路由問(wèn)題相結(jié)合,提出了鏈路分配公平性與路由時(shí)延最小化的多目標(biāo)優(yōu)化模型,并設(shè)計(jì)了啟發(fā)式算法求解模型。針對(duì)全球?qū)Ш叫l(wèi)星系統(tǒng)的星間通信等問(wèn)題,Yan等[21]提出了一種基于模擬退火的啟發(fā)式算法來(lái)分配星間鏈路,優(yōu)化了星間通信時(shí)延。這些算法主要考慮了衛(wèi)星的收發(fā)器資源約束,忽略了衛(wèi)星網(wǎng)絡(luò)的鏈路容量和衛(wèi)星緩存的約束。然而有限的鏈路容量和衛(wèi)星緩存容量也是比較關(guān)鍵的約束條件,會(huì)影響數(shù)據(jù)傳輸時(shí)鏈路的選擇。

由于衛(wèi)星網(wǎng)絡(luò)具有時(shí)變特性,衛(wèi)星網(wǎng)絡(luò)被認(rèn)為是一種延遲容忍網(wǎng)絡(luò)[22],有不少文獻(xiàn)運(yùn)用時(shí)變網(wǎng)絡(luò)中的圖論相關(guān)知識(shí),研究時(shí)延容忍衛(wèi)星網(wǎng)絡(luò)中的路由規(guī)劃問(wèn)題。Huang 等[23]利用空時(shí)圖對(duì)衛(wèi)星網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)溥M(jìn)行建模,提出了基于貪婪算法的最短路徑路由規(guī)劃算法;Li等[24]提出了具有存儲(chǔ)時(shí)間聚合圖網(wǎng)絡(luò)模型,并利用該模型設(shè)計(jì)了時(shí)變網(wǎng)絡(luò)最大流路由算法。Zhang等[25]研究了衛(wèi)星網(wǎng)絡(luò)多任務(wù)傳輸?shù)姆?wù)質(zhì)量問(wèn)題,提出了以最大完成數(shù)為目標(biāo)且滿(mǎn)足時(shí)延要求的數(shù)據(jù)流調(diào)度算法。文獻(xiàn)[26]提出了一種基于接觸圖的能量感知路由算法。構(gòu)建基于圖模型的衛(wèi)星網(wǎng)絡(luò)拓?fù)?能夠較為精準(zhǔn)的刻畫(huà)其動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)。但是對(duì)于并發(fā)流、混合流等數(shù)據(jù)傳輸問(wèn)題,基于圖模型的路由策略,求解質(zhì)量難以得到保證。

因此,有必要在考慮衛(wèi)星網(wǎng)絡(luò)資源約束的條件下,針對(duì)并發(fā)數(shù)據(jù)流的傳輸問(wèn)題研究高質(zhì)量的算法。進(jìn)化算法是一種基于自然進(jìn)化和選擇的全局搜索優(yōu)化算法, 已經(jīng)成功應(yīng)用到多個(gè)現(xiàn)實(shí)問(wèn)題中, 并發(fā)揮了良好的應(yīng)用效果[27-29]。近年來(lái), 不少文獻(xiàn)利用歷史數(shù)據(jù)、信息和經(jīng)驗(yàn)中學(xué)習(xí)到的可存儲(chǔ)信息等知識(shí),輔助進(jìn)行決策,并成功解決了一些復(fù)雜的組合優(yōu)化問(wèn)題[30-32]。

基于以上分析,在資源有限的時(shí)變衛(wèi)星網(wǎng)絡(luò)中,針對(duì)星間數(shù)據(jù)傳輸存在的問(wèn)題,以最小化數(shù)據(jù)的傳輸時(shí)延為目標(biāo),構(gòu)建了具有節(jié)點(diǎn)緩存約束的時(shí)變網(wǎng)絡(luò)多商品流模型,并設(shè)計(jì)了知識(shí)型算子、路徑流量分配算法等,結(jié)合進(jìn)化算法,提出了知識(shí)型混合進(jìn)化算法(knowledge-guided hybrid evolutionary algorithm,KGHEA),能夠有效地解決星間數(shù)據(jù)傳輸問(wèn)題。文章的主要?jiǎng)?chuàng)新如下:

(1)采用存儲(chǔ)時(shí)間聚合圖描述衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),考慮衛(wèi)星網(wǎng)絡(luò)資源的約束,構(gòu)建了整數(shù)規(guī)劃數(shù)學(xué)模型,并將星間數(shù)據(jù)傳輸問(wèn)題轉(zhuǎn)化為具有節(jié)點(diǎn)緩存約束的時(shí)變網(wǎng)絡(luò)多路徑多源單匯的多商品流問(wèn)題。

(2)設(shè)計(jì)了基于知識(shí)的啟發(fā)式算法,提出了KGHEA。該算法融入了局部搜索算法、路徑流量分配算法、遺傳進(jìn)化算子、鄰域搜索算子和自適應(yīng)選擇算子,通過(guò)不同知識(shí)的引導(dǎo),獲得高質(zhì)量的數(shù)據(jù)傳輸方案。

(3)通過(guò)設(shè)計(jì)一系列仿真實(shí)驗(yàn),驗(yàn)證了KGHEA的有效性,分析了境外星數(shù)、時(shí)隙數(shù)、需求量、星間鏈路容量和衛(wèi)星緩存容量等參數(shù)對(duì)數(shù)據(jù)傳輸性能的影響。

1 模型構(gòu)建

1.1 衛(wèi)星網(wǎng)絡(luò)模型

考慮一個(gè)由中高軌道衛(wèi)星和地面站構(gòu)成的混合衛(wèi)星網(wǎng)絡(luò),其中中軌道衛(wèi)星采用Walker星座,含有多個(gè)衛(wèi)星軌道,每個(gè)軌道上分布著多顆衛(wèi)星,高軌道衛(wèi)星采用地球同步軌道衛(wèi)星和傾斜地球同步軌道衛(wèi)星。由于衛(wèi)星運(yùn)動(dòng)的周期性特點(diǎn),衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也是周期性變化的。因此,本文主要考慮一個(gè)周期內(nèi)的網(wǎng)絡(luò)拓?fù)錉顩r。采用時(shí)隙化系統(tǒng),將一個(gè)周期等分為若干個(gè)連續(xù)的時(shí)隙T={1,2,…,T},每個(gè)時(shí)隙的長(zhǎng)度為Δτ,每個(gè)時(shí)隙內(nèi)的拓?fù)浣Y(jié)構(gòu)認(rèn)為是固定的。將衛(wèi)星分為境內(nèi)星和境外星,境外星上生成的需求數(shù)據(jù),通過(guò)境內(nèi)星的中轉(zhuǎn)傳輸?shù)降孛嬲?。由于衛(wèi)星網(wǎng)絡(luò)的時(shí)變特性,境外星到地面站難以存在穩(wěn)定的端到端路徑。本文主要考慮境外星上的數(shù)據(jù)傳輸問(wèn)題,即在衛(wèi)星網(wǎng)絡(luò)拓?fù)鋾r(shí)變的條件下,考慮鏈路容量和衛(wèi)星緩存容量等網(wǎng)絡(luò)資源的約束,規(guī)劃數(shù)據(jù)傳輸路徑,以最小化傳輸時(shí)延為目標(biāo),將境外星上生成的數(shù)據(jù)傳輸?shù)降孛嬲尽?/p>

為了建立合適的數(shù)據(jù)傳輸模型,進(jìn)行如下的假設(shè):① 在進(jìn)行數(shù)據(jù)傳輸?shù)倪^(guò)程中,不考慮鏈路故障以及數(shù)據(jù)丟失的情況;② 只考慮由于鏈路中斷而引起的時(shí)延,忽略其他的時(shí)延,即數(shù)據(jù)傳輸時(shí)延以數(shù)據(jù)傳輸時(shí)所占用的時(shí)隙計(jì)算;③ 由于衛(wèi)星網(wǎng)絡(luò)資源的限制,每顆衛(wèi)星只有一條星間鏈路,每個(gè)境內(nèi)星與地面站也只有一條星地鏈路。

為了便于理解,圖1給出了衛(wèi)星網(wǎng)絡(luò)存儲(chǔ)時(shí)間聚合圖的例子。圖中網(wǎng)絡(luò)由3個(gè)境外星、2個(gè)境內(nèi)星和地面節(jié)點(diǎn)構(gòu)成,劃分為6個(gè)時(shí)隙。每條鏈路上標(biāo)有各個(gè)時(shí)隙的容量值構(gòu)成的容量時(shí)間序列,其中容量為零意味著該鏈路為斷開(kāi)狀態(tài),每個(gè)節(jié)點(diǎn)上標(biāo)有各個(gè)時(shí)隙的緩存容量構(gòu)成的緩存時(shí)間序列。

圖1 存儲(chǔ)時(shí)間聚合圖模型Fig.1 Storage time aggregated graph model

1.2 數(shù)據(jù)流模型

1.3 數(shù)據(jù)傳輸數(shù)學(xué)模型

基于存儲(chǔ)時(shí)間聚合圖模型,考慮鏈路容量、衛(wèi)星緩存容量等網(wǎng)絡(luò)資源的約束,以最小化境外星上所有需求的傳輸時(shí)延為目標(biāo),將數(shù)據(jù)傳輸問(wèn)題轉(zhuǎn)化成具有節(jié)點(diǎn)容量的多商品流問(wèn)題(multi commodity flow problem with node capacity,MCFPWNC),構(gòu)建了下列數(shù)學(xué)模型:

目標(biāo)函數(shù):

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

2 算法設(shè)計(jì)

本文設(shè)計(jì)局部搜索算法、不同的知識(shí)型啟發(fā)式算子等,并融入到進(jìn)化算法中,提出KGHEA,用以解決星間數(shù)據(jù)傳輸問(wèn)題。在KGHEA中,為了能夠減少不可行解,分兩步構(gòu)造問(wèn)題的解:第1步,采用實(shí)數(shù)編碼的方式,生成不同的需求序列;第2步,生成最短路徑,并進(jìn)行流量分配,獲取問(wèn)題的解。

本節(jié)主要設(shè)計(jì)了局部搜索算法、路徑流量分配算法,以及知識(shí)型算子,通過(guò)局部搜索算法獲取初始種群,利用路徑流量分配算法獲取問(wèn)題的可行解,使用知識(shí)型算子加強(qiáng)算法的局部搜索能力。KGHEA整體框架如圖2所示。首先,將需求編碼成個(gè)體,然后采用局部搜索算法生成初始種群;其次,執(zhí)行路徑流量分配算法,為每個(gè)需求生成最短路徑并分配流量,然后計(jì)算其適應(yīng)度值;最后,通過(guò)選擇、交叉、變異等算子的操作,生成下一代種群。

圖2 KGHEA框架Fig.2 KGHEA framework

2.1 設(shè)置初始種群

染色體采用實(shí)數(shù)編碼,每一個(gè)實(shí)數(shù)對(duì)應(yīng)一個(gè)需求編號(hào),一組需求序列代表一個(gè)個(gè)體,通過(guò)生成不同的需求序列來(lái)引導(dǎo)路徑流量分配算法生成不同的解。初始種群采用局部搜索算法生成。首先,將需求按照其出現(xiàn)的先后順序、其數(shù)據(jù)量的大小等規(guī)則進(jìn)行排列,生成一個(gè)初始個(gè)體,然后采用翻轉(zhuǎn)、塊交換等方式,生成若干鄰域,從中選擇若干較優(yōu)的個(gè)體,生成N個(gè)個(gè)體構(gòu)成初始種群。

2.2 執(zhí)行路徑流量分配算法,計(jì)算適應(yīng)度值

考慮到問(wèn)題的優(yōu)化目標(biāo)是最小化需求數(shù)據(jù)的傳輸時(shí)延,每個(gè)需求應(yīng)盡可能地選擇傳輸時(shí)延最短的路徑進(jìn)行傳輸,不妨將該路徑定義為最短路徑。在數(shù)據(jù)傳輸過(guò)程中,越短的路徑越優(yōu)先分配流量,這樣可以通過(guò)路徑的長(zhǎng)短來(lái)引導(dǎo)數(shù)據(jù)流量的分配。因此,首先使用深度優(yōu)先搜索算法為每個(gè)需求數(shù)據(jù)生成k條最短路徑集合,并將其作為路徑流量分配算法的輸入信息。

算法 1 路徑流量分配算法1. 輸入:需求數(shù)據(jù)序列D,存儲(chǔ)時(shí)間聚合圖 ( , , , , ),最短路徑集合P。2. 輸出:xh,duv,xh,dv。3. 初始化:xh,duv=0,xh,dv=0,chuv=0,bhv=0。 4. for d in D do:5. 將集合Pd={p1,p2,…,pk}中的路徑按照短到長(zhǎng)的順序排序,Pd∈P6. for p in Pd do:7. cp←min{chuv-chuv,bhv-bhv,ehuv,vh∈p}8. if fh,d>cp:9. xh,duv=xh,duv+cp10. xh,dv=xh,dv+cp 11. fh,d=fh,d-cp12. 更新chuv,bhv13. else: 14. xh,duv=xh,duv+fh,d15. xh,dv=xh,dv+fh,d16. fh,d=017. 更新chuv,bhv18. break19. end if20. end for21. end for

2.3 選擇操作

KGHEA采用改進(jìn)的錦標(biāo)賽選擇策略選擇較優(yōu)的個(gè)體進(jìn)入到下一代種群中。具體步驟為:每次隨機(jī)從父代和子代種群中各選擇n個(gè)個(gè)體進(jìn)行競(jìng)爭(zhēng),選擇其中適應(yīng)度較高的n個(gè)個(gè)體進(jìn)入下一代,參與競(jìng)爭(zhēng)的個(gè)體不再放回原種群中,經(jīng)過(guò)若干次競(jìng)爭(zhēng)與選擇,直到下一代個(gè)體滿(mǎn)足種群要求為止。該選擇策略能夠確保將父代的精英個(gè)體遺傳給下一代,加快了算法的收斂速度。

2.4 交叉操作

為了能夠更好地保留父代個(gè)體的順序關(guān)系,KGHEA采用順序交叉算子進(jìn)行父代與子代之間的交叉操作,形成下一代種群。具體操作為:首先,從父代1中隨機(jī)選擇兩個(gè)斷點(diǎn), 將兩斷點(diǎn)間的元素復(fù)制到子代1中, 然后在父代2中刪除這些重復(fù)的元素,并剩余元素遺傳給子代1,其繼承順序是從第二個(gè)斷點(diǎn)開(kāi)始到序列末端,然后再?gòu)男蛄惺级搜永m(xù)到第二個(gè)斷點(diǎn)位置,交換兩個(gè)父代的角色。同理生成子代 2,如圖3所示。

豐寧抽水蓄能電站巖錨梁混凝土防裂技術(shù)……………………………………吳慶樂(lè)，張瑞華，王建輝，等（2.54）

圖3 順序交叉操作Fig.3 Order crossover operation

2.5 自適應(yīng)變異操作

利用位置關(guān)系和鏈路性能等啟發(fā)式知識(shí),設(shè)計(jì)了3個(gè)變異算子,分別為兩點(diǎn)交換算子、移位插入算子,以及鏈路負(fù)載度算子,以不同的方式搜索解空間,增強(qiáng)算法的搜索能力。此外,還根據(jù)歷史收益知識(shí),設(shè)計(jì)了自適應(yīng)選擇算子,以便根據(jù)變異算子的貢獻(xiàn)度等歷史收益,自適應(yīng)地選擇變異算子進(jìn)行變異操作。

2.5.1 兩點(diǎn)交換算子

兩點(diǎn)交換算子的過(guò)程主要為從一個(gè)父代個(gè)體中隨機(jī)選取兩個(gè)位置,然后交換這兩個(gè)位置的元素,形成新的子代個(gè)體,如圖4所示。

圖4 兩點(diǎn)交換變異操作Fig.4 Two point exchange mutation operation

2.5.2 移位插入算子

移位插入算子的操作過(guò)程為從一個(gè)父代個(gè)體中隨機(jī)選取兩個(gè)位置,然后將其中一個(gè)位置的元素插入到另一個(gè)位置上,從而形成新的子代個(gè)體,如圖5所示。

2.5.3 鏈路負(fù)載度算子

鏈路容量的限制是影響需求數(shù)據(jù)傳輸?shù)闹饕蛩刂?當(dāng)鏈路負(fù)載達(dá)到鏈路容量上限后,會(huì)選擇下一條較短路徑進(jìn)行流量的分配,此時(shí)會(huì)導(dǎo)致個(gè)體的適應(yīng)度降低。為了降低鏈路滿(mǎn)負(fù)載的可能性,對(duì)父代個(gè)體執(zhí)行路徑流量分配算法時(shí),記錄所有星間鏈路的負(fù)載,將滿(mǎn)負(fù)載的鏈路對(duì)應(yīng)的需求序列取出來(lái),優(yōu)先進(jìn)行流量的分配。將這些需求序列隨機(jī)排列后,與剩下的需求序列合并重新組合,從而形成新的子代個(gè)體,其偽代碼見(jiàn)算法2。

算法 2 鏈路負(fù)載度算子1. 輸入:父代需求序列集PS,需求的路徑集P,鏈路(uh,vh)的負(fù)載chuv,第i個(gè)需求序列中需求d 的路徑Pi,d∈P。 2. 輸出:子代需求序列集OS。3. 初始化:OS=[ ]4. for PSi in PS do:5. OSi=[ ]6. ifchuv=chuv:7. for d in PSi do:8. if (uh,vh)∈Pi,dand d?OSi:9. OSi.append(d)10. PSi.remove(d)11. end if12. random.shuffle(OSi)13. OSi.extend(PSi)14. end for15. end if16. OS.append(OSi)17. end for

2.5.4 自適應(yīng)選擇算子

算法 3 自適應(yīng)選擇算子1. 輸入:父代集PS,變異算子集MS,種群數(shù)N。2. 輸出:子代集OS,自適應(yīng)選擇概率集PR。3. 初始化:Ri=N/3, PRi=Ri/sum(Ri)4. for PSi in PS do:5. MSi←Roulette(MS, PS)6. OSi←Mutation(PSi, MSi)7. OS.append(OSi)8. if fitness(OSi)>fitness(PSi):9. Ri=Ri+r10. PRi=Ri/sum(Ri)11. end if12. end for

3 實(shí)驗(yàn)設(shè)計(jì)與分析

為了驗(yàn)證所提KGHEA的性能,本節(jié)使用仿真軟件構(gòu)建了混合星座,設(shè)計(jì)了不同場(chǎng)景的實(shí)驗(yàn),進(jìn)行了多個(gè)算法的對(duì)比實(shí)驗(yàn),分析了算法的求解效果,并分析了各項(xiàng)參數(shù)對(duì)數(shù)據(jù)傳輸性能的影響。實(shí)驗(yàn)采用Python語(yǔ)言和優(yōu)化軟件CPLEX求解器[33],實(shí)驗(yàn)機(jī)器的配置為Inter Core i5處理器,1.19 GHz,8 GB內(nèi)存。

3.1 仿真場(chǎng)景

本實(shí)驗(yàn)使用仿真軟件構(gòu)建了30顆衛(wèi)星的混合星座,其中包括24顆中軌道衛(wèi)星(medium earth orbit, MEO),3顆地球同步軌道衛(wèi)星(geosynchronous orbit, GEO)和3顆傾斜地球同步軌道衛(wèi)星(inclined geosynchronous orbit, IGSO)?；旌闲亲闹饕獏?shù)如表1所示。選取北京站為仿真實(shí)驗(yàn)中的唯一地面站。

表1 混合星座的主要參數(shù)Table 1 Main parameters of hybrid constellation

根據(jù)星座的運(yùn)行特點(diǎn),系統(tǒng)周期規(guī)劃為168 h,時(shí)隙長(zhǎng)度設(shè)置為3 s,20個(gè)時(shí)隙(即1 min)構(gòu)成了一個(gè)拓?fù)渲芷?每種拓?fù)湓谝环N狀態(tài)下重用60次(即1 h),在整個(gè)系統(tǒng)周期內(nèi),一共可以獲得168個(gè)不同的拓?fù)浣Y(jié)構(gòu)。使用文獻(xiàn)[34]中的方法,可以獲得每個(gè)拓?fù)渲芷趦?nèi)的拓?fù)浣Y(jié)構(gòu),將其作為星間數(shù)據(jù)傳輸?shù)耐負(fù)漭斎搿?/p>

另外,在實(shí)驗(yàn)中,將衛(wèi)星之間的鏈路容量設(shè)置為80 MB,衛(wèi)星上的緩存上限設(shè)置為130 MB,星地鏈路容量設(shè)置為100 MB,匯點(diǎn)的緩存容量設(shè)置為設(shè)置無(wú)窮大。同時(shí),假設(shè)每個(gè)境外星生成的需求量均服從以35 MB為均值的泊松分布,數(shù)據(jù)傳輸時(shí)延不超過(guò)4時(shí)隙。此外,為降低算法計(jì)算量,將k最短路徑集合中每個(gè)需求的最短路徑數(shù)量設(shè)置為4。

3.2 算法參數(shù)配置

為了使KGHEA的性能達(dá)到最優(yōu),需要配置其相關(guān)參數(shù)值。將交叉和變異概率的取值分別從0.1到1,間隔為0.1,經(jīng)過(guò)100組的參數(shù)組合實(shí)驗(yàn),得到了KGHEA的交叉和變異概率最佳組合參數(shù)。圖6展示了5種典型參數(shù)組合的實(shí)驗(yàn)結(jié)果,由圖可知,在交叉率pc=0.7和變異率pm=0.5時(shí), 算法性能最佳。

圖6 5種典型參數(shù)組合的測(cè)試結(jié)果Fig.6 Test results of five typical parameter combinations

3.3 實(shí)驗(yàn)結(jié)果分析

由于MCFPWNC是一個(gè)整數(shù)規(guī)劃問(wèn)題, 采用優(yōu)化軟件CPLEX求解器對(duì)其進(jìn)行求解,獲取問(wèn)題的最優(yōu)解。同時(shí),選取基本混合進(jìn)化算法(basic hybrid evolutionary algorithm, BHEA)作為對(duì)比算法。BHEA中,隨機(jī)生成初始種群,采用錦標(biāo)賽選擇策略選取子代個(gè)體,并使用兩點(diǎn)交換算子執(zhí)行變異操作,而遺傳編碼、可行解的獲取以及交叉操作與KGHEA相同,交叉概率pc與變異概率pm分別取0.9和0.2。實(shí)驗(yàn)中,以數(shù)據(jù)流的平均時(shí)延、算法的運(yùn)行時(shí)間等為統(tǒng)計(jì)指標(biāo),分析境外星數(shù)、時(shí)隙數(shù)、需求量、星間鏈路容量和衛(wèi)星緩存容量等因素對(duì)數(shù)據(jù)傳輸性能的影響。實(shí)驗(yàn)結(jié)果如圖7～圖10所示,其中圖7為13至17個(gè)境外星數(shù)的實(shí)驗(yàn)結(jié)果,其他各圖均為17個(gè)境外星時(shí)的實(shí)驗(yàn)結(jié)果。

圖7 不同境外星數(shù)的實(shí)驗(yàn)結(jié)果Fig.7 Experimental results of different number of non-anchors

圖7給出了不同境外星數(shù)下數(shù)據(jù)傳輸時(shí)延結(jié)果和各算法的運(yùn)行時(shí)間。從圖7(a)中可以看出,隨著境外星數(shù)的增加,數(shù)據(jù)傳輸時(shí)延也在增加。這是因?yàn)樵诰W(wǎng)絡(luò)規(guī)模一定的情況下,境外星數(shù)越多,減少了境內(nèi)星數(shù),減少了中轉(zhuǎn)節(jié)點(diǎn)數(shù)量,增加了同一時(shí)隙發(fā)送的需求數(shù),增大了需求在路徑間發(fā)生沖突的概率,增加了網(wǎng)絡(luò)負(fù)載,由于星間鏈路容量有限,一部分?jǐn)?shù)據(jù)只能暫時(shí)存儲(chǔ)在中轉(zhuǎn)衛(wèi)星上,待有剩余鏈路容量時(shí)再繼續(xù)傳輸,從而增加了數(shù)據(jù)傳輸時(shí)延。另外,與BHEA相比,KGHEA的實(shí)驗(yàn)結(jié)果更加接近最優(yōu)值,當(dāng)境外星個(gè)數(shù)為13和14時(shí),其結(jié)果幾乎為最優(yōu)值。圖7(b)表明隨著境外星數(shù)的增加,各算法的運(yùn)行時(shí)間也增加。因?yàn)榫惩庑菙?shù)的增加,增加了需求的個(gè)數(shù),增加了問(wèn)題的求解量, 從而增加了算法的運(yùn)行時(shí)間。同時(shí)還表明,KGHEA與BHEA的求解時(shí)間接近,都低于CPLEX求解器的運(yùn)行時(shí)間。

圖8展示了不同時(shí)隙數(shù)的數(shù)據(jù)傳輸時(shí)延性能,以及算法的運(yùn)行時(shí)間。由圖8(a)可知,隨著時(shí)隙數(shù)的增加,平均時(shí)延有增有降,時(shí)隙的變化對(duì)數(shù)據(jù)傳輸時(shí)延具有一定的影響,但是影響規(guī)律不明顯。原因是隨著時(shí)隙數(shù)的增加,需求數(shù)也增加,同時(shí)需求數(shù)據(jù)的傳輸也會(huì)使用后一時(shí)隙的拓?fù)浣Y(jié)構(gòu),數(shù)據(jù)傳輸時(shí)延與后一時(shí)隙的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)密切相關(guān)。另外,KGHEA的實(shí)驗(yàn)結(jié)果與最優(yōu)值變化規(guī)律一致,且比BHEA具有更優(yōu)的實(shí)驗(yàn)結(jié)果,隨著時(shí)隙數(shù)的增加,它們與最優(yōu)值的差距逐步增大。圖8(b)表明隨著時(shí)隙數(shù)的增加,算法的求解時(shí)間也增加,因?yàn)樵诰惩庑菙?shù)一定的前提下,時(shí)隙數(shù)增加時(shí),需求數(shù)增加,問(wèn)題的求解量增多,從而增加了算法的運(yùn)行時(shí)間。同時(shí)還能看出,KGHEA與BHEA的求解時(shí)間接近,都低于CPLEX求解器的運(yùn)行時(shí)間。

圖8 不同時(shí)隙數(shù)的實(shí)驗(yàn)結(jié)果Fig.8 Experimental results of different number of timeslots

圖9給出了不同需求量的實(shí)驗(yàn)結(jié)果。從圖9(a)可以看出,平均時(shí)延隨著需求量的增加而增加。原因是由于網(wǎng)絡(luò)資源的限制,境外星上待傳輸?shù)男枨罅吭酱?增加了數(shù)據(jù)傳輸所使用的路徑數(shù),增大了使用最大時(shí)延路徑的概率,從而增加了數(shù)據(jù)的傳輸時(shí)延。另外,相比于BHEA,KGHEA的實(shí)驗(yàn)結(jié)果更加接近最優(yōu)值,在需求量為27、29、31時(shí),幾乎能夠達(dá)到最優(yōu)值。 圖9(b)表明隨著需求量的增加,各算法的運(yùn)行時(shí)間均比較穩(wěn)定,變化不大,KGHEA與BHEA的求解時(shí)間接近,都低于CPLEX求解器的運(yùn)行時(shí)間。

圖9 不同需求量的實(shí)驗(yàn)結(jié)果Fig.9 Experimental results of different demands

星間鏈路容量和衛(wèi)星緩存容量不同組合的數(shù)據(jù)傳輸平均時(shí)延性能及各算法的運(yùn)行時(shí)間見(jiàn)圖10。由圖10(a)可知,增加數(shù)據(jù)量為3的星間鏈路容量或衛(wèi)星緩存容量,均可減少數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延,但增加星間鏈路容量提升平均時(shí)延的性能更加明顯。因此,增加星間鏈路容量比增加衛(wèi)星緩存容量能帶來(lái)更加明顯的數(shù)據(jù)傳輸性能提升。另外,KGHEA的實(shí)驗(yàn)結(jié)果接近最優(yōu)值,比BHEA具有更優(yōu)的實(shí)驗(yàn)結(jié)果。圖10(b)表明各算法的運(yùn)行時(shí)間均比較穩(wěn)定,變化不大,KGHEA與BHEA的求解時(shí)間接近,都低于CPLEX求解器的運(yùn)行時(shí)間。

圖10 星間鏈路容量和衛(wèi)星緩存容量不同組合的實(shí)驗(yàn)結(jié)果Fig.10 Experimental results of different combinations of inter-satellite link capacity and satellite cache capacity

4 結(jié) 論

本文主要對(duì)拓?fù)鋾r(shí)變的衛(wèi)星網(wǎng)絡(luò)星間數(shù)據(jù)傳輸問(wèn)題進(jìn)行了研究。首先,通過(guò)存儲(chǔ)時(shí)間聚合圖建模衛(wèi)星網(wǎng)絡(luò),并將星間數(shù)據(jù)傳輸問(wèn)題建模為具有容量約束的多商品流問(wèn)題,構(gòu)建了整數(shù)規(guī)劃模型。其次,為了求解模型,設(shè)計(jì)了融入局部搜索算法、路徑流量分配算法和知識(shí)型算子的KGHEA。最后,設(shè)計(jì)了仿真實(shí)驗(yàn),與BHEA、CPLEX求解器的求解結(jié)果與運(yùn)行時(shí)間進(jìn)行了比較,并分析了境外星數(shù)、時(shí)隙數(shù)、需求量、星間鏈路容量和衛(wèi)星緩存容量對(duì)星間數(shù)據(jù)傳輸性能的影響。實(shí)驗(yàn)表明,KGHEA的求解結(jié)果非常接近最優(yōu)解,比CPLEX求解器具有求解效率優(yōu)勢(shì);KGHEA與BHEA在運(yùn)行時(shí)間方面差距不大,但是KGHEA具有更優(yōu)的求解質(zhì)量。同時(shí)還表明,境外星數(shù)、需求量對(duì)數(shù)據(jù)傳輸性能的影響較大;時(shí)隙數(shù)對(duì)數(shù)據(jù)傳輸性能有一定的影響,但是影響規(guī)律不明顯;與增加衛(wèi)星緩存容量相比,增加星間鏈路容量更加有助于提升數(shù)據(jù)傳輸性能。