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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1 模型構(gòu)建

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

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

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

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

圖1 存儲時間聚合圖模型Fig.1 Storage time aggregated graph model

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

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

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

目標函數(shù):

(1)

約束條件:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

2 算法設計

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

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

圖2 KGHEA框架Fig.2 KGHEA framework

2.1 設置初始種群

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

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

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

算法 1 路徑流量分配算法1. 輸入:需求數(shù)據(jù)序列D,存儲時間聚合圖 ( , , , , ),最短路徑集合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}中的路徑按照短到長的順序排序,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采用改進的錦標賽選擇策略選擇較優(yōu)的個體進入到下一代種群中。具體步驟為:每次隨機從父代和子代種群中各選擇n個個體進行競爭,選擇其中適應度較高的n個個體進入下一代,參與競爭的個體不再放回原種群中,經(jīng)過若干次競爭與選擇,直到下一代個體滿足種群要求為止。該選擇策略能夠確保將父代的精英個體遺傳給下一代,加快了算法的收斂速度。

2.4 交叉操作

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

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

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

2.5 自適應變異操作

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

2.5.1 兩點交換算子

兩點交換算子的過程主要為從一個父代個體中隨機選取兩個位置,然后交換這兩個位置的元素,形成新的子代個體,如圖4所示。

圖4 兩點交換變異操作Fig.4 Two point exchange mutation operation

2.5.2 移位插入算子

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

2.5.3 鏈路負載度算子

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

算法 2 鏈路負載度算子1. 輸入:父代需求序列集PS,需求的路徑集P,鏈路(uh,vh)的負載chuv,第i個需求序列中需求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 自適應選擇算子

算法 3 自適應選擇算子1. 輸入:父代集PS,變異算子集MS,種群數(shù)N。2. 輸出:子代集OS,自適應選擇概率集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 實驗設計與分析

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

3.1 仿真場景

本實驗使用仿真軟件構(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所示。選取北京站為仿真實驗中的唯一地面站。

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

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

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

3.2 算法參數(shù)配置

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

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

3.3 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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