戴翠琴，賀黎明，羅 屹

重慶郵電大學通信與信息工程學院，重慶400065

近年來，低軌（low earth orbit,LEO）衛(wèi)星網(wǎng)絡憑借傳輸時延小、組網(wǎng)靈活、不易受地理環(huán)境影響的優(yōu)勢在災害救援、環(huán)境監(jiān)測、情報偵察中發(fā)揮著關鍵作用。然而，LEO 衛(wèi)星網(wǎng)絡中節(jié)點的相對運動導致的網(wǎng)絡拓撲時變和鏈路連接瞬斷會給LEO 衛(wèi)星網(wǎng)絡通信的可靠性和有效性帶來巨大影響。在LEO 網(wǎng)絡中，“連接”用于表示衛(wèi)星網(wǎng)絡中節(jié)點間相對運動軌跡在時間和空間上具有交集的一系列通信機會，但是網(wǎng)絡拓撲和星間鏈路（inter-satellite links,ISL）的時變性、衛(wèi)星節(jié)點能源和負載的有限性限制了LEO 衛(wèi)星之間建立連接的機會，使得衛(wèi)星通信中可用連接計劃（contact plan,CP）時變且有限，進而導致衛(wèi)星網(wǎng)絡連接和系統(tǒng)性能受到嚴重影響。為解決以上問題，連接計劃設計（contact plan design,CPD）得到了廣泛關注[1]。

目前，LEO 衛(wèi)星網(wǎng)絡中的CPD 按優(yōu)化目標可以分為兩類：1）基于網(wǎng)絡連接優(yōu)化的CPD方案[2-13]，如最小化網(wǎng)絡連接瞬斷概率[2-10]和最大化連接公平性[11-13]；2）基于系統(tǒng)性能優(yōu)化的CPD 方案，如最大化能源效率[14-16]、最小化時延[17-20]和最大化吞吐量[21-22]的CPD方案。

第1 類CPD 方案是最小化網(wǎng)絡連接瞬斷概率，即最小化ISL 連接中斷概率。文獻[2] 考慮隊列長短和流量大小提出了一種基于流量感知的層間連接選擇方法，該方法雖然提升了網(wǎng)絡吞吐量，但是增加了系統(tǒng)交付時延。文獻[3] 提出一種改進的基于協(xié)同進化機制的多衛(wèi)星協(xié)同任務規(guī)劃算法，提高了任務收益，但是并未考慮衛(wèi)星間因ISL 沖突而導致的傳輸阻塞問題，該問題可能會導致高延遲。文獻[4] 提出連接圖路由的替代方案，提高了機會路由算法的數(shù)據(jù)傳輸效率，但是并未給出校驗數(shù)據(jù)是否到達目標點的方法，同時也未驗證方案在時延方面的表現(xiàn)。文獻[5] 基于馬爾可夫決策過程理論模型，確定了故障下的最佳路由策略，但并未考慮到LEO 衛(wèi)星的移動性問題，這是CPD 問題需要重點考慮的內容。文獻[6] 綜合考慮時變拓撲、間歇性連接和不同天氣條件下的自適應傳輸，提出了兩種啟發(fā)式的CPD 方案，解決了有限資源條件下的CPD 問題，但是該方案并不適用對時延有嚴苛要求的應用。文獻[7] 提出了基于遺傳算法（genetic algorithm,GA）的多任務規(guī)劃方案，解決了任務重規(guī)劃問題，但是對任務進行重規(guī)劃會超出用戶程序所能容忍的時間限制，因此會降低用戶體驗。文獻[8] 將時空圖中的流量優(yōu)化問題視為與隊列穩(wěn)定性相關的隨機優(yōu)化問題，提升了網(wǎng)絡穩(wěn)定性，但是該方案優(yōu)先保證衛(wèi)星連接的公平性，可能出現(xiàn)某顆衛(wèi)星空閑，但是因排隊導致無法及時傳輸數(shù)據(jù)，造成了時延的增大。文獻[9] 將節(jié)點的運動特性建模為有限狀態(tài)自動機（finite state automaton,FSA），設計了一種基于模擬退火（simulated annealing,SA）算法的CPD 方案，SA 會進一步增加衛(wèi)星的能耗，一般并不適用資源受限的小型衛(wèi)星網(wǎng)絡。文獻[10] 考慮兩層空間網(wǎng)絡，并提出了3 種可以提高連接可靠性、降低成本和降低無效概率成本的CPD 方案，該方案問題分析較為單一，并未綜合考慮可靠性和成本問題下的CPD 問題。最大化連接公平性，指的是最大化ISL 連接的公平性，保證各個節(jié)點建立ISL 的概率是相同的。文獻[11] 將一個大的連接計劃拆分成幾個部分，提出了一種多層衛(wèi)星網(wǎng)絡的分布式連接計劃設計方案。文獻[12] 提出了一個優(yōu)化模型形式化問題，并提出當出現(xiàn)大量CP 時，將其作為一個匹配問題解決。文獻[13]提出基于路由感知的CPD，利用SA 優(yōu)化衛(wèi)星網(wǎng)絡整體端到端傳輸時延。文獻[11-13] 僅僅將公平性放在首位，不僅未考慮延遲和衛(wèi)星能耗的問題，而且還存在因長時間等待連接分配而導致流量阻塞的問題。以上文獻為優(yōu)化網(wǎng)絡連接性能做了大量貢獻，但是均存在可以改進的地方：1）僅僅考慮連接是不夠的，因為保證衛(wèi)星網(wǎng)絡連接的最終目的是傳輸數(shù)據(jù)，而數(shù)據(jù)的傳輸過程又需要考慮到網(wǎng)絡吞吐量的表現(xiàn)；2）主要針對空間層的數(shù)據(jù)傳輸，均未給出如何判斷流量阻塞和解決流量阻塞的方法。

對于第2 類CPD 方案，已有的研究主要圍繞能耗、時延和吞吐量3 個方面進行。最大化能源效率指的是最大化衛(wèi)星能源利用率。文獻[14] 設計了基于電池感知的CPD 方案，以保證最大化通信資源的利用率，并且提出采用電池安全裕量的方法，從而保證衛(wèi)星能源不會被耗盡，但是方案只考慮能效不考慮拓撲特性，未能給出具體的CPD 方案，缺乏一定的說服力。文獻[15] 設計了一種適用于延遲容忍網(wǎng)絡（delay tolerance network,DTN）的能源感知路由算法，使衛(wèi)星始終具有充足的能力轉發(fā)數(shù)據(jù)，該方案并不適用于大型衛(wèi)星星座，因為目前大型星座并不需要以“存儲– 攜帶– 轉發(fā)”的方式傳輸數(shù)據(jù)。文獻[16] 利用粒子群優(yōu)化（particle swarm optimization,PSO）算法處理因拓撲時刻變化而產(chǎn)生的復雜的路由問題，減少了衛(wèi)星網(wǎng)絡能耗，該方案重點考慮了路由，并未考慮到衛(wèi)星節(jié)點的特性，比如系統(tǒng)容量和轉發(fā)器狀態(tài)。為最小化時延，文獻[17] 提出一種基于離散的PSO（discrete particle swarm optimization,DPSO）方案以解決多任務規(guī)劃問題，方案雖然降低了時延，但是多任務規(guī)劃問題的空間復雜度往往較高，給衛(wèi)星的計算能力帶來很大挑戰(zhàn)。文獻[18] 提出了一種基于CP的延遲約束路由算法，滿足了具有時延限制服務的需求，但是方案僅僅適用于時延敏感型任務。文獻[19] 采用遺傳啟發(fā)的CPD 方案，以減少傳輸時延，但是運行算法本身的能源消耗可能會超出衛(wèi)星本身可承受范圍，因此可能會對衛(wèi)星能耗算法提出更高的要求。文獻[20] 首次提出了適用于全球導航衛(wèi)星系統(tǒng)的分布式CPD 方案，但是該方案并未考慮導航系統(tǒng)在不同天氣時的性能不穩(wěn)定問題，需要進一步驗證所提方案的有效性，因此缺乏一定的說服力。為最大化吞吐量，文獻[21-22] 提出接入衛(wèi)星選擇和數(shù)據(jù)下載策略。其中，為解決星地鏈路穩(wěn)定性和流量平衡問題，文獻[22] 提出一種去中心化的預測算法，用于估計衛(wèi)星之間的CP，但是該方案并未對所提算法在時延方面的表現(xiàn)進行仿真驗證，因此可能并不適用于對時延要求比較嚴苛的任務和應用程序?？傊陨匣谙到y(tǒng)性能優(yōu)化的CPD 研究工作所考慮的問題均較為單一，仍存在以下局限性：1）未考慮到衛(wèi)星網(wǎng)絡不同于地面網(wǎng)絡，衛(wèi)星網(wǎng)絡中各個衛(wèi)星的能源本身是受限的；2）未考慮到數(shù)據(jù)傳輸過程中需要兼顧衛(wèi)星節(jié)點負載狀態(tài)和ISL 的連接狀態(tài)，可能會發(fā)生鏈路沖突，進而造成網(wǎng)絡阻塞。

本文針對資源受限的LEO 衛(wèi)星網(wǎng)絡連通性和數(shù)據(jù)阻塞的問題，考慮了網(wǎng)絡拓撲的時變性、衛(wèi)星資源的有限性，提出了一種基于數(shù)據(jù)校驗時空圖的CPD 方案。首先，為表征衛(wèi)星網(wǎng)絡資源和網(wǎng)絡瞬時拓撲，在最大化電池能效的基礎上建立了一種基于電池模型的數(shù)據(jù)校驗時空圖；其次，將CPD 問題建模為以ISL 和能源為約束、以最大化吞吐量為目標的約束優(yōu)化問題；接著，通過該模型比較校驗層的校驗數(shù)據(jù)和傳輸層的轉發(fā)數(shù)據(jù)進而判斷是否發(fā)生了流量擁塞，并綜合ISL 和節(jié)點負載狀態(tài)，對錯誤CP 進行初步修復，生成可用CP；最后，利用適應度函數(shù)評價修復后可用CP 的優(yōu)異程度，并利用DCGA 算法生成使得吞吐量最大化的最佳CP。仿真結果表明了該方案可以提升網(wǎng)絡吞吐量和降低交付時延。

1 系統(tǒng)模型

給出了LEO 衛(wèi)星網(wǎng)絡模型，并設計了一種改進的電池模型，在最大化衛(wèi)星能源效率的基礎上，利用基于電池模型的數(shù)據(jù)校驗時空圖（data check time-space graph,DCTSG）表征LEO 衛(wèi)星網(wǎng)絡資源和瞬時拓撲結構。

1.1 網(wǎng)絡模型

如圖1 所示，LEO 網(wǎng)絡模型主要由3 個部分構成：1）數(shù)據(jù)發(fā)送區(qū)域，從該區(qū)域通過LEO網(wǎng)絡向地面站發(fā)送數(shù)據(jù)，并且通過地面網(wǎng)關向數(shù)據(jù)中心發(fā)送數(shù)據(jù)的簡要信息，包括數(shù)據(jù)大小、類型和內容等；2）資源受限的LEO 衛(wèi)星，主要負責從數(shù)據(jù)發(fā)送區(qū)域接收任務數(shù)據(jù)，并發(fā)送到地面站；3）地面站，主要接收LEO 衛(wèi)星通過ISL 轉發(fā)的任務數(shù)據(jù)，并發(fā)送到數(shù)據(jù)中心處理。

圖1 LEO 衛(wèi)星網(wǎng)絡模型Figure 1 LEO satellite networks model

在圖1 的網(wǎng)絡模型中，LEO 衛(wèi)星從數(shù)據(jù)發(fā)送區(qū)域收集數(shù)據(jù)，并傳輸?shù)降孛嬲?，最后發(fā)送到數(shù)據(jù)中心。數(shù)據(jù)中心比較校驗數(shù)據(jù)和從LEO 衛(wèi)星接收的數(shù)據(jù)是否相同，進而判斷是否需要進一步處理該數(shù)據(jù)。當發(fā)送區(qū)域在LEO 衛(wèi)星觀測范圍之內時，衛(wèi)星從發(fā)送區(qū)域采集數(shù)據(jù)。之后的數(shù)據(jù)傳輸主要包含兩種情況：1）若此時該衛(wèi)星在目標地面站的觀測范圍之內，則該衛(wèi)星將收集到的數(shù)據(jù)直接發(fā)送到地面站；2）若此時該衛(wèi)星不在地面站觀測范圍之內，則該衛(wèi)星需要經(jīng)過ISL 的一系列轉發(fā)后，才能將任務數(shù)據(jù)送達到目標地面站。針對第2 種情況，尤其是在衛(wèi)星資源受限的情況下，制定合適的CPD 方案，可以有效地防止衛(wèi)星之間出現(xiàn)間歇性連接，從而避免數(shù)據(jù)在傳輸時出現(xiàn)連接中斷，甚至丟失。

1.2 電池模型

為確保衛(wèi)星節(jié)點的可用性，首先需要對傳統(tǒng)的電池模型[15]進行改進，得到改進的電池模型（improved-battery model,IBaM），該模型能夠最大化電池效率、最小化電源耗盡概率，從而能夠保證衛(wèi)星節(jié)點的可用性。

IBaM 如圖2 所示，其存儲的電荷分為兩個部分：1）可用電荷k(t)，該部分電荷直接受到負載的影響，通過電壓表顯示可用電量；2）束縛電荷s(t)，該部分的電荷以化學能的形式存儲在電池內，不直接受到負載的影響。當束縛電荷和可用電荷存在高度差時，將發(fā)生電荷的擴散作用：若束縛電荷高度高于可用電荷，則束縛電荷內穩(wěn)定的化學能將通過擴散作用轉化為可用電荷；反之，可用電荷將轉化為束縛電荷。電荷的恢復效應和容量效應分別遵循的兩個耦合的微分方程為

圖2 電池模型Figure 2 Battery model

式中：f(t) 為電池上的負載，其擴散速度由非負參數(shù)p調節(jié)，并與k(t) 和s(t) 高度差成正比；c為可用電荷的比例，其范圍為[0,1]。

為保證電池的可用性，引入安全閾值ymin。當ymin＞0 時認為電池能源是能夠進行數(shù)據(jù)轉發(fā)的；當ymin=0 時認為電池能源被耗盡。但在此模型中，即使可用電荷k(t)＜ymin，電池內部右側以化學能形式存儲的s(t) 仍能夠轉化為可用電荷以達到安全閾值，從而保證了衛(wèi)星電池的可用性，即不存在失效的衛(wèi)星節(jié)點。

1.3 數(shù)據(jù)校驗時空圖

電池模型能夠最大化電池效率，確保在時空圖中不存在失效的節(jié)點，時空圖表征了網(wǎng)絡資源和網(wǎng)絡瞬時拓撲。如圖3 所示，使用DCTSG 表征網(wǎng)絡資源以及網(wǎng)絡瞬時拓撲。拓撲采用的是時間間隙的模式，該模式將拓撲中的時間劃分為n個時間間隙，即t ∈ˉλ={Δτ,2Δτ,···,nΔτ}，每個時間間隙的長度為Δτ，在每個間隙內網(wǎng)絡拓撲被看作是固定的。DCTSG 是由n個時間間隙構成的有向圖，記為G(V,?)，頂點V=Vg ∪Vo ∪Vs，具體公式為

式中：g為地面站，O為觀測目標，S為衛(wèi)星?？紤]到衛(wèi)星資源的有限性，鏈路在調度過程中可能會發(fā)生沖突，因此需要考慮從DCTSG 中選擇可行的CP 方案。顯然，可行的CPD 方案是DCTSG 的子圖，圖3 中方案1 和2 是可行的兩種方案。

在圖3 中，有4 種頂點和5 種鏈路弧線。4 種頂點分別為觀測目標O，衛(wèi)星S，地面站g以及數(shù)據(jù)中心D。采用時間間隙的模式，在每個間隙中拓撲可以看作是固定的，采用上下標區(qū)分每個節(jié)點的不同狀態(tài)，其中表示衛(wèi)星1 在第2 個間隙中的狀態(tài)，以此類推，表示地面站2 在第1 個間隙中的狀態(tài)，表示目標區(qū)域3 在第2 個間隙中的狀態(tài)。5 種鏈路弧線包括機率鏈路弧線和存儲弧線，分別為：1）橘黃色線，表示在每個時間間隙內，小衛(wèi)星從觀測目標區(qū)域收集任務數(shù)據(jù)的幾率；2）綠線，表示衛(wèi)星之間通過ISL 建立連接的概率和衛(wèi)星轉發(fā)任務數(shù)據(jù)到地面站的概率；3）紅線，代表同一衛(wèi)星在不同時刻的變化；4）藍線，表示任務1 和2的可行數(shù)據(jù)傳輸路徑，即可行的CP 方案；5）紫線，表示將校驗數(shù)據(jù)發(fā)送給數(shù)據(jù)中心，其中校驗數(shù)據(jù)包含了要傳輸任務的數(shù)據(jù)大小、數(shù)據(jù)類型、數(shù)據(jù)名稱等簡要信息。

數(shù)據(jù)校驗的原因和過程：任務從數(shù)據(jù)發(fā)送地經(jīng)過LEO 衛(wèi)星網(wǎng)絡的傳輸?shù)綌?shù)據(jù)接收地（地面站），但是在任務傳輸過程中可能因為ISL 沖突等原因發(fā)生流量阻塞，因此需要進行數(shù)據(jù)校驗，以確定數(shù)據(jù)接收地接收到了數(shù)據(jù)發(fā)送地的所有數(shù)據(jù)。數(shù)據(jù)校驗的過程為：當數(shù)據(jù)發(fā)送地發(fā)送數(shù)據(jù)到LEO 衛(wèi)星網(wǎng)絡（橘黃色線），會同時發(fā)送簡短的信息（類似報文）到數(shù)據(jù)接收地（紫線），一般來說，地面網(wǎng)絡的傳輸時延小于衛(wèi)星網(wǎng)絡的傳輸時延，因此并不會影響對于整體延遲的判斷；接著數(shù)據(jù)中心接收到校驗數(shù)據(jù)后會實時比較校驗數(shù)據(jù)和轉發(fā)數(shù)據(jù)（經(jīng)過LEO 網(wǎng)絡轉發(fā)到地面站，再到數(shù)據(jù)中心）是否一致，若在時延容忍范圍內兩者數(shù)據(jù)不一致，則判定任務在LEO 衛(wèi)星網(wǎng)絡中發(fā)生了阻塞，因此需要進一步對其進行CPD。

2 問題描述

基于DCTSG 將ISL 和衛(wèi)星能源作為約束條件，以最大化吞吐量為優(yōu)化目標，將CPD 問題建模為約束優(yōu)化問題。

2.1 相關約束

由于LEO 衛(wèi)星網(wǎng)絡中的資源是有限的，因此往往需要考慮在有限資源約束下進行CPD，本文主要考慮ISL 約束和衛(wèi)星能源約束下的CPD 問題，以下為具體的約束條件：

1）ISL 資源約束 考慮衛(wèi)星資源的有限性，假設每顆衛(wèi)星有兩個轉發(fā)器，在同一時間最多只能建立兩條鏈路：衛(wèi)星到衛(wèi)星之間的ISL 和衛(wèi)星到地面的星地鏈路（satellite-ground link,SGL）?；诖思僭O，引入布爾型變量表示衛(wèi)星節(jié)點的轉發(fā)器是否被占用，公式為

假設一個衛(wèi)星在某一時刻最多只能建立1 條ISL 和1 條SGL，于是有如下約束：

同時，1 個地面站在1 個時間間隙內，最多只能和1 個衛(wèi)星建立連接，于是有如下約束：

2）能量約束 假設電池的最大放電深度為A，則衛(wèi)星i在第t個時間間隙的剩余電量可表示為

式中：EBimax為衛(wèi)星i的電池容量。

2.2 問題建模

式中：F為所有任務流f在時間ˉλ上的集合，Ese為衛(wèi)星從目標點收集數(shù)據(jù)弧線的集合。

假設衛(wèi)星i從觀測目標點收集數(shù)據(jù)消耗的功率和接收功率分別為Psc和Psr，則在時間間隙Δτ內衛(wèi)星i收集數(shù)據(jù)和接收數(shù)據(jù)的能量大小為

式中：Ess為ISL 弧線的集合。

假設衛(wèi)星i正常運行的功率為Pn，則在一個時間間隙內衛(wèi)星運行消耗的能量可表示為

假設在t－1 個時間間隙結束時衛(wèi)星i的剩余能量為，在第t個時間間隙內衛(wèi)星i通過太陽板收集的能量為，則衛(wèi)星i在第t個時間間隙的能源約束可表示為

根據(jù)以上約束條件，在DCTSG 的基礎之上，將CPD 建模為基于DCTSG 的最大化吞吐量問題，最大化吞吐量問題可表示為

根據(jù)以上約束條件和優(yōu)化目標可知，CPD 中的吞吐量問題需要確定大量的整數(shù)變量，而且式(13) 是一個整數(shù)線性規(guī)劃問題，且該問題是NP-hard 問題，難以求解。

3 基于DCTSG 的連接計劃設計

由第2 節(jié)可知，CPD 中的吞吐量問題是NP-hard 問題，求解該問題的時間復雜度較高。因此，提出了一種基于DCTSG 的CPD 方案，旨在求解出LEO 網(wǎng)絡中吞吐量最大化的最佳CP。

3.1 DCTSG-CPD 整體方案

DCTSG-CPD 整體方案框圖如圖4 所示，在DCTSG 的基礎上，首先通過比較校驗數(shù)據(jù)和轉發(fā)數(shù)據(jù)判斷LEO 網(wǎng)絡的連通性，若此時網(wǎng)絡處于阻塞狀態(tài)，則需要通過綜合ISL 和衛(wèi)星負載狀態(tài)對當前錯誤CP 進行初始化、編碼和修復，并通過適應度函數(shù)判斷修復后CP 的優(yōu)異程度，然后利用基于數(shù)據(jù)校驗的遺傳算法（data check genetic algorithm,DCGA）算法求解出吞吐量最大化的最佳CP，下面將展開對整體方案的具體描述。

3.2 網(wǎng)絡連通性判斷

在DCTSG 的基礎上，LEO 衛(wèi)星、數(shù)據(jù)發(fā)送地和數(shù)據(jù)中心被表示為網(wǎng)絡節(jié)點，但是此時網(wǎng)絡可能存在數(shù)據(jù)傳輸擁塞的問題，因此需要進一步分析網(wǎng)絡的連通性。提出將網(wǎng)絡模型分為兩層：通過LEO 衛(wèi)星網(wǎng)絡轉發(fā)數(shù)據(jù)的轉發(fā)層和地面發(fā)送地發(fā)送數(shù)據(jù)的數(shù)據(jù)校驗層。轉發(fā)層負責將大規(guī)模流量轉發(fā)到地面站，并由地面站進一步傳輸?shù)綌?shù)據(jù)中心處理；數(shù)據(jù)校驗層主要負責將任務的簡要信息（如任務的大小、類型和名稱等）發(fā)送到數(shù)據(jù)中心，數(shù)據(jù)中心通過比較接收到的檢驗數(shù)據(jù)和轉發(fā)數(shù)據(jù)的一致性，進而判斷是否發(fā)生了流量阻塞（這里不考慮網(wǎng)絡的其他傳輸問題，如衛(wèi)星信道狀況等），若數(shù)據(jù)一致，則轉到3.3 節(jié)介紹的字符串更正和適應度判斷；若發(fā)現(xiàn)校驗數(shù)據(jù)和轉發(fā)數(shù)據(jù)不一致，則判斷空間傳輸層發(fā)生了流量阻塞。流量阻塞的原因可能有兩種：1）因鏈路沖突而導致的阻塞，假設每個LEO 衛(wèi)星最多只能建立一條ISL 和一條SGL，此時可能存在多個衛(wèi)星同時和某個衛(wèi)星建立ISL 的情況，因此會因鏈路沖突而發(fā)生網(wǎng)絡阻塞；2）衛(wèi)星滿負載，即已無法接收其他衛(wèi)星通過ISL 傳輸?shù)臄?shù)據(jù)，此時衛(wèi)星會因為等待而導致網(wǎng)絡阻塞。

3.3 字符串更正和適應度判斷

根據(jù)以下方法對錯誤CP 進行修復。首先，把一對潛在連接隨機表示為二進制字符，離散拓撲中所有的連接被表示為隨機的二進制字符串。但是該過程并未考慮約束條件，因此接下來還需要對該二進制字符串加以更正，一個離散拓撲被編碼為二進制字符串的過程如圖5所示。

圖5 二進制編碼和修復Figure 5 Binary encoding and repair

由圖5 可知，一串二進制字符串由多個單個字符組成，字符串的狀態(tài)代表部分離散拓撲的瞬時連接狀態(tài)，更正后的單個二進制字符代表衛(wèi)星節(jié)點之間實際的連接狀態(tài)：1 代表可建立ISL 傳輸數(shù)據(jù)，0 代表不可以建立ISL 傳輸數(shù)據(jù)。以為例，上標t表示第t個時間間隙，1 代表衛(wèi)星S1和S3的轉發(fā)器處于空閑狀態(tài)，初始化生成的字符為1，表示衛(wèi)星S1和S3之間正在通過ISL 進行數(shù)據(jù)傳輸。但是生成的字符串并沒有考慮CPD 的約束，因此需要對其進行更正。更正需要考慮兩個方面的因素：1）節(jié)點的鏈路狀態(tài)，系統(tǒng)的傳輸方式為半雙工傳輸，一個衛(wèi)星節(jié)點在某一時刻只能使用一個轉發(fā)器傳輸數(shù)據(jù)；2）鏈路的負載狀態(tài)，若鏈路的負載狀態(tài)為0，則不建立鏈路，避免造成鏈路資源的浪費。只有滿足鏈路狀態(tài)和節(jié)點狀態(tài)同時為1 時，該鏈路才會建立。

經(jīng)過以上步驟會更正錯誤的CP，生成大量的可行CP。但并不是所有可行CP 都是最優(yōu)的，為了比較單個可行CP（個體）在所有可行CP（群體）中的優(yōu)異程度，需要使用適應度函數(shù)進行判斷。因為優(yōu)化目標為最大化吞吐量，所以優(yōu)化目標是非負的，故將目標函數(shù)作為個體適應度的判斷函數(shù)，適應度函數(shù)如式(18) 所示，適應度函數(shù)的值越大，表明該CP 的適應性越高，越符合最大化吞吐量的要求。

3.4 DCGA 算法

DCGA 算法流程如圖6 所示。在判斷網(wǎng)絡阻塞狀態(tài)和二進制字符串適應度的基礎上，本節(jié)進一步利用GA 中的選擇、交叉和變異操作，生成滿足適應度函數(shù)的更優(yōu)解。

圖6 DCGA 算法流程Figure 6 Process of DCGA algorithm

由于更正后的二進制字符串（即可行CP）無法保證LEO 衛(wèi)星網(wǎng)絡是連通的，因此需要進一步根據(jù)校驗數(shù)據(jù)和轉發(fā)數(shù)據(jù)判斷網(wǎng)絡阻塞狀態(tài)，同時若LEO 網(wǎng)絡是非阻塞狀態(tài)，則進一步判斷字符串的適應度，若滿足字符串的適應度閾值，為進一步求得滿足吞吐量最大化的最佳CP，則繼續(xù)進行遺傳算法中的選擇、交叉和變異步驟，步驟具體過程描述如下：

步驟1選擇

選擇的目的是把優(yōu)秀的CP 留給下一代。輪盤賭選擇法是最常見、最簡單的選擇方法，它通過個體適應度與群體適應度之和的比率來確定每個CP 被選擇的概率。CP 被選中的概率為

由式(19) 可以看出，個體被選擇的概率與它在群體中的適應度比例成正比，個體的適應度越大，被選中的概率也就越大。

步驟2交叉和變異

交叉操作的目的是將優(yōu)良的基因結合在一起，產(chǎn)生具有新的基因組合的個體。單點交叉是遺傳算法中最常用的交叉方法，它是隨機產(chǎn)生一個交叉位點，并在交叉點前后進行基因交換，可以使后代方便有效地保存親本基因。

為了防止遺傳算法在優(yōu)化過程中陷入局部最優(yōu)解，增強搜索全局最優(yōu)解的可能性，在搜索過程中，需要對個體CP 進行變異，變異操作主要采用單點變異，也叫位變異，即只需要對基因序列中某一個位進行變異，二進制編碼表示為：0 變?yōu)?，1 變?yōu)?。交叉和變異步驟與傳統(tǒng)的遺傳算法相似，此處不再贅述。

在完成一系列遺傳操作后，會得到一個比親本群體更大的新群體。根據(jù)初始群體的大小和個體的適應度，將個體從前到后進行選擇，準備進入下一次迭代。由于在算法實施前無法知道優(yōu)秀CP 的適應度，所以采用靜態(tài)終止準則，即達到最大迭代次數(shù)時，算法終止。

4 仿真實驗與結果分析

本節(jié)介紹仿真環(huán)境和具體的參數(shù)設置，然后從平均適應值、任務平均交付時間和任務數(shù)據(jù)到達率3 個方面進行了實驗，并且對DCTSG 和DCGA 在這3 方面的表現(xiàn)進行分析。

4.1 仿真實驗

為了驗證DCTSG 和DCGA 的有效性，本文利用MATLAB 和衛(wèi)星工具箱進行了仿真。

仿真場景由66 顆LEO 衛(wèi)星構成的Iridium 二代衛(wèi)星星座構成。該星座包含6 條極軌軌道，每條軌道擁有11 顆衛(wèi)星，衛(wèi)星軌道高度為780 km，軌道傾角為86.4°，仿真時長為24 000 s，具體仿真參數(shù)如表1 所示。假設建立ISL 的最大距離為4 000 km，衛(wèi)星可以與同一軌道內相鄰衛(wèi)星和相鄰軌道距離最近的衛(wèi)星建立ISL，并且一顆衛(wèi)星同一時刻最多建立一條ISL 和SGL。場景中共設置3 個觀測目標區(qū)域，分別位于華盛頓、阿姆斯特丹和莫斯科，地面站分別位于重慶、北京和西安，每個數(shù)據(jù)分組的大小為1 Mbit，鏈路的數(shù)據(jù)傳輸速度為1 Mbit/s，所以鏈路每秒可以傳輸一個數(shù)據(jù)分組。3 個目標區(qū)域各發(fā)起30 個采集任務，所有任務共包含1 500 個數(shù)據(jù)分組。

表1 LEO 衛(wèi)星網(wǎng)絡相關參數(shù)Table 1 Parameters of LEO satellite networks

4.2 仿真結果分析

為了說明所提DCTSG-CPD 方案的優(yōu)越性，將其在平均適應值、任務平均交付時間和任務數(shù)據(jù)到達率方面與TSG-CPD 和CPD 方案進行了對比分析。此外，為了證明所提DCGA算法的性能，將其與引入模擬生物競爭的GA 算法和基于演化計算的PSO 算法進行對比分析。

4.2.1 DCTSG-CPD 和TSG-CPD、CPD 的性能對比及分析

為體現(xiàn)出DCTSG-CPD 方案的性能優(yōu)勢，選取TSG-CPD 和CPD 方案作為對比。為保證仿真的準確性，以上3 種方案采取的算法均為DCGA 算法，除DCTSG-CPD 方案含有數(shù)據(jù)校驗功能的數(shù)據(jù)中心、TSG-CPD 含有時空圖和CPD 無時空圖外，其他所有的參數(shù)設置均相同。仿真分別在平均適應值、任務平均交付時間和任務數(shù)據(jù)到達率3 個方面進行了大量CPD 實驗。具體的仿真結果如圖7～9 所示。

圖7 平均適應值曲線Figure 7 Average fitness curve

圖7 的平均適應值指的是可行CP 的平均適應值。由圖7 可以看出，3 種方案的平均適應值都隨著迭代次數(shù)的增加而增加。DCTSG-CPD 在迭代350 次后趨于穩(wěn)定，TSG-CPD 在迭代200 次后趨于穩(wěn)定，CPD 在迭代150 次后趨于穩(wěn)定。但是，DCTSG-CPD 方案的適應值高于TSG-CPD，TSG-CPD 方案的適應值高于CPD。這是因為DCTSG-CPD 方案采用了糾正錯誤CP 的方法，使得每次迭代得到的可行CP 都是在滿足適應度函數(shù)條件且沒有ISL 沖突的最優(yōu)CP，其他兩種方案均未考慮利用衛(wèi)星負載狀態(tài)和ISL 狀態(tài)對錯誤CP 進行糾正，因此平均適應值較低。TSG-CPD 方案相比較于DCTSG-CPD 方案，前者缺少糾正CP 的步驟，因此平均適應值低于后者。但是相比于CPD 方案，TSG-CPD 存在對衛(wèi)星網(wǎng)絡中可用資源的抽象化分析，且建立CP 的嘗試次數(shù)少于無TSG 的CPD 方案，因此適應值也較高。

圖8 是數(shù)據(jù)分組從數(shù)據(jù)發(fā)送地到達地面站平均消耗的時間。由圖8 可以看出，隨著迭代次數(shù)的增加，3 種方案的任務平均交付時間均先減少再趨于穩(wěn)定。其中DCTSG-CPD 方案在迭代300 次后趨于穩(wěn)定，TSG-CPD 方案在迭代200 次后趨于穩(wěn)定，CPD 方案在迭代250 次后趨于穩(wěn)定。由以上分析可知，相比其他兩種方案，DCTSG-CPD 方案采用了糾正錯誤CP的方法，可以在更短的時間內選取無沖突的可用CP，TSG-CPD 方案雖然無糾正CP 的步驟，但是依然能夠通過多次嘗試找到可用的CP，CPD 方案不存在主動尋找可用CP 的步驟，于是在無可用ISL 的條件下，擁有負載的衛(wèi)星節(jié)點會選擇等待，流量被阻塞在衛(wèi)星中，直到有可用的ISL 為止。因此，DCTSG-CPD 方案的交付時延小于TSG-CPD，TSG-CPD 方案的交付時延小于CPD。

圖8 任務平均交付時間Figure 8 Average task delivery time

圖9 是3 種方案數(shù)據(jù)分組到達率的對比。由圖9 可以看出，隨著迭代次數(shù)的增加，3 種方案的任務到達率均先增加再趨于穩(wěn)定。圖9 中，DCTSG-CPD 和TSG-CPD 方案在迭代250次后趨于穩(wěn)定，CPD 方案在迭代100 次后趨于穩(wěn)定，由此可見，與TSG-CPD 方案和CPD方案相比，DCTSG-CPD 方案能夠在更短的時間內選取無沖突且適應度更高的CP。另外，如果采用單雙工的傳輸模式，即同一時刻不存在多條ISL，那么更短傳輸時延的方案能夠在相同的時間內傳輸更多的數(shù)據(jù)量，數(shù)據(jù)的到達率和吞吐量也就更高。因此，DCTSG-CPD 方案的吞吐量大于TSG-CPD，TSG-CPD 方案的吞吐量大于CPD。

圖9 數(shù)據(jù)到達率Figure 9 Data arrival ratio

4.2.2 DCGA 算法和GA、PSO 算法的性能對比及分析

為體現(xiàn)出DCGA 算法性能的優(yōu)越性，本文選取了PSO[18]和GA[20]算法這兩種啟發(fā)式算法作為對比算法。在設置參數(shù)時，GA 的參數(shù)和本文算法相同，而PSO 的最小慣性權重、最大慣性權重、局部學習因子和全局學習因子分別設置為0.6、0.8、2 和2。此外，算法中的種群大小為100，最大迭代次數(shù)為500，交叉率和變異率分別設置為0.6 和0.05。圖10 為DCGA算法和GA、PSO 算法的性能對比。

圖10 DCGA 算法和GA、PSO 算法的性能對比Figure 10 Performance comparison of DCGA algorithm with GA and PSO algorithm

圖10(a) 中的平均適應值指的是CP 的平均適應值。由圖10(a) 可以看出，3 種算法的平均適應值都隨著迭代次數(shù)的增加而增加。但是GA 并未考慮到鏈路狀態(tài)和負載狀態(tài)，因此每次更新完比特序列之后，該算法需要對大部分的序列進行修復，導致該算法的迭代效率低于PSO 算法和DCGA。由于PSO 算法只受歷史最優(yōu)信息的影響，因此該算法的平均適應值很快收斂且落后于DCGA。又由于PSO 算法在每次迭代后會選擇適應度高的CP，因此其尋優(yōu)能力和整體的平均適應值也高于其他兩種算法。

圖10(b) 是數(shù)據(jù)分組到達地面站平均消耗的時間。由圖10(b) 可以看出，3 種算法的時間變化規(guī)律基本與平均適應值的變化類似。整體的適應值越高，算法對應的數(shù)據(jù)分組到達地面站的傳輸時間越短。GA 算法因為沒有考慮衛(wèi)星負載和鏈路的狀態(tài)，可能會發(fā)生鏈路阻塞，因此需要更多的迭代次數(shù)才能夠收斂。DCGA 算法的傳輸時間小于PSO 算法，這是因為前者考慮到了節(jié)點負載狀態(tài)和鏈路狀態(tài)，能夠更快地選擇出適應值更高且在傳輸過程中無ISL 沖突的路徑，能夠有效地避免因數(shù)據(jù)在一條鏈路上長時間等待而導致鏈路阻塞的問題，因此交付時間更短。

圖10(c) 是3 種算法數(shù)據(jù)分組到達率的對比。從圖10(c) 中可以看出，所提算法的數(shù)據(jù)到達率明顯高于其他兩種算法。這是因為該算法考慮了鏈路狀態(tài)和節(jié)點負載狀態(tài)，在相同的時間內，本文算法中的數(shù)據(jù)分組并不會出現(xiàn)長時間等待的現(xiàn)象，當節(jié)點負載已滿或者該鏈路處于忙碌狀態(tài)被占用時，會立即尋找其他傳輸路徑，直到有可行的ISL 為止，使得在相同時間內能夠傳輸更多的數(shù)據(jù)，因此數(shù)據(jù)傳輸?shù)倪_到率也較高。

5 結語

針對資源受限的LEO 衛(wèi)星網(wǎng)絡時空連通性和流量阻塞的問題，提出了一種基于數(shù)據(jù)校驗時空圖的CPD 方案。首先，構建了基于電池模型的DCTSG，并對CPD 問題進行建模；其次，給出了判斷網(wǎng)絡是否發(fā)生了流量擁塞的方法；接著，提出對錯誤CP 進行修復的方法；最后，設計了DCGA 算法求得最佳CP。仿真結果表明了該方案的有效性。