戴翠琴，唐煌，郭林峰

（重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065）

1 引言

近年來，隨著人們對空域信息傳輸需求的與日俱增，低軌（LEO,low earth orbit）衛(wèi)星網(wǎng)絡(luò)以軌道高度低、通信時延小、覆蓋方位廣、受地理環(huán)境影響小和組網(wǎng)靈活的優(yōu)勢受到了越來越廣泛的應(yīng)用[1-2]。但是，由于衛(wèi)星節(jié)點間的相對運動容易導(dǎo)致星間鏈路（ISL,inter-satellite link）連接中斷，使衛(wèi)星網(wǎng)絡(luò)拓撲時變、路由表頻繁更新、空間信息傳輸效率降低。此外，由于衛(wèi)星在能耗、轉(zhuǎn)發(fā)器數(shù)量等資源上的限制，使空間節(jié)點在同一時間內(nèi)不能同時建立多條鏈路來傳輸數(shù)據(jù)[3]。針對以上問題，考慮到衛(wèi)星網(wǎng)絡(luò)拓撲動態(tài)、連接間斷及資源受限的特性，為了通過空間鏈路的優(yōu)化調(diào)度來最大化網(wǎng)絡(luò)傳輸效率，連接計劃設(shè)計（CPD,contact plan design）引起了研究者們的關(guān)注[4]。

目前，已有少量文獻對衛(wèi)星網(wǎng)絡(luò)中的CPD 展開了研究[5-10]。文獻[5]根據(jù)衛(wèi)星節(jié)點的本地拓撲信息計算不相交路徑（或節(jié)點），并以此構(gòu)建連通圖（CG,connected graph）來增強衛(wèi)星網(wǎng)絡(luò)拓撲的穩(wěn)健性及鏈路連接的可持續(xù)性。文獻[6]根據(jù)衛(wèi)星節(jié)點的軌道運動特性將LEO 網(wǎng)絡(luò)建模為有限狀態(tài)自動機（FSA,finite state automaton），基于FSA 的每個狀態(tài)采用模擬退火（SA,simulate anneal）算法，避免了在狀態(tài)轉(zhuǎn)換期間鏈路分配的不穩(wěn)定行為。由以上文獻可知，通過CG 和FSA 均能實現(xiàn)衛(wèi)星網(wǎng)絡(luò)動態(tài)拓撲的靜態(tài)離散化，但是，二者都沒法有效地體現(xiàn)連續(xù)拓撲的時間演變性，使空間通信資源不能得到充分利用，尤其是當使用CG 構(gòu)建大規(guī)?？臻g網(wǎng)絡(luò)時，空間節(jié)點間連通數(shù)量的增多會使網(wǎng)絡(luò)成本效益急劇下降。針對網(wǎng)絡(luò)成本效益問題，文獻[7]基于一系列以時間為序的靜態(tài)拓撲構(gòu)建了同時具備時間和空間信息的動態(tài)時空圖（STG,space-time graph），并在保持原始網(wǎng)絡(luò)拓撲節(jié)點間連通性的同時稀疏了拓撲結(jié)構(gòu)，降低了拓撲維持成本?？紤]到衛(wèi)星節(jié)點故障及移動性帶來的連接不可靠問題，文獻[8]通過設(shè)計加權(quán)有向STG 來分析不同時隙中連接的可靠性，并引入生成樹（ST,spanning tree），通過生成比率保證網(wǎng)絡(luò)可靠性的同時優(yōu)化了路由成本效益?；阪溌愤B接容量的時變性，文獻[9]提出了一種時間拓展圖（TEG,time-expanded graph），有效地解決了衛(wèi)星網(wǎng)絡(luò)吞吐量優(yōu)化問題。文獻[10]通過對數(shù)據(jù)流和能量流分別對TEG 進行了建模優(yōu)化，區(qū)分了各拓撲結(jié)構(gòu)的狀態(tài)持續(xù)時間，并將連接計劃（CP,contact plan）中數(shù)據(jù)的傳輸過程看作一個動態(tài)隨機隊列優(yōu)化問題，通過逐時隙地設(shè)計CP 來最大化吞吐量。

在衛(wèi)星網(wǎng)絡(luò)CPD 的研究中，除了要考慮網(wǎng)絡(luò)拓撲的時變性和空間鏈路連接的瞬斷性，還需要考慮空間節(jié)點通信資源的有限性[11-14]?？紤]到衛(wèi)星網(wǎng)絡(luò)的資源受限問題，文獻[11]基于遺傳算法（GA,genetic algorithm）提出了一種CPD 方案來最小化網(wǎng)絡(luò)的多對多時延；文獻[12]提出了一種公平連接計劃（FCP,fair contact plan）設(shè)計方案，通過最小邊緣容量最大化和最大鏈路容量最小化的鏈路選擇機制來平衡ISL 的連接時間。文獻[13]將FCP 與時空路由感知相結(jié)合，采用SA 算法求解衛(wèi)星網(wǎng)絡(luò)中CPD 與路由的組合優(yōu)化問題，在最大化公平性的同時改進了CP 整體的端到端時延。針對導(dǎo)航衛(wèi)星系統(tǒng)中的數(shù)據(jù)傳輸問題，文獻[14]基于SA 算法提出了一種啟發(fā)式CPD 方案來優(yōu)化空間數(shù)據(jù)傳輸時延。以上已有的衛(wèi)星網(wǎng)絡(luò)中的CPD 主要針對動態(tài)網(wǎng)絡(luò)拓撲、間斷鏈路連接和空間資源有限這三方面問題進行了優(yōu)化設(shè)計，并沒有考慮衛(wèi)星網(wǎng)絡(luò)中空間任務(wù)需求的多樣性和網(wǎng)絡(luò)規(guī)模大小對數(shù)據(jù)傳輸?shù)挠绊?。當網(wǎng)絡(luò)規(guī)模較小時，在任務(wù)傳輸時間和鏈路消耗上無法滿足空間任務(wù)中大量數(shù)據(jù)的傳輸。另一方面，如果不考慮空間任務(wù)需求的差異性，設(shè)計的CP 將影響任務(wù)的到達率。

粒子群優(yōu)化（PSO,particle swarm optimization）算法以其收斂速度快、并行計算能力強、具有動態(tài)的搜索能力等優(yōu)點[15]，適用于滿足衛(wèi)星網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中對傳輸時間、能量消耗和數(shù)據(jù)存儲的需要[16-20]。文獻[16]采用PSO 算法去解決由空間環(huán)境和快速拓撲變化引起的多約束條件下衛(wèi)星網(wǎng)絡(luò)路由的能耗問題。文獻[17]針對衛(wèi)星網(wǎng)絡(luò)中多任務(wù)協(xié)調(diào)規(guī)劃問題，提出了一種具有變異算子的離散粒子群優(yōu)化（DPSO,discrete particle swarm optimization）方案。文獻[18]基于DPSO 算法，引入分支定界算法來提高局部搜索能力的同時，采用局部鄰域拓撲來避免早期收斂陷阱。文獻[19]采用多目標粒子群優(yōu)化（MOPSO,multi-objective particle swarm optimization）算法優(yōu)化衛(wèi)星系統(tǒng)有效荷載參數(shù)進行地球觀測任務(wù)。文獻[20]采用改進的PSO 算法，提出了一種基于壓縮感知的衛(wèi)星導(dǎo)航信號采集方法（NSA-CSIPSO,navigation signal acquisition-compressed sensing using improved particle swarm optimization），確保衛(wèi)星導(dǎo)航信號恢復(fù)準確性的同時減少接收機所需的空間數(shù)據(jù)量。以上文獻的衛(wèi)星網(wǎng)絡(luò)中PSO 的算法研究主要針對路由能耗、任務(wù)協(xié)調(diào)、對地觀測、信號采集等問題提出了解決方案，并沒有考慮衛(wèi)星網(wǎng)絡(luò)拓撲動態(tài)、連接間斷及由此引起的CPD 問題。

本文針對空間任務(wù)的多樣性與衛(wèi)星網(wǎng)絡(luò)的資源受限問題，綜合考慮到PSO 算法的收斂速度與衛(wèi)星網(wǎng)絡(luò)狀態(tài)的時變性、PSO 算法的內(nèi)存空間占用小與衛(wèi)星網(wǎng)絡(luò)的資源有限性，在傳統(tǒng)PSO 算法的基礎(chǔ)上，結(jié)合任務(wù)傳輸時效的特點和CP 中鏈路的稀疏性，提出了一種基于雙向?qū)?yōu)粒子群優(yōu)化（BPSO,bi-directional particle swarm optimization）算法，來優(yōu)化數(shù)據(jù)在衛(wèi)星網(wǎng)絡(luò)中的傳輸效率。首先，針對LEO 衛(wèi)星網(wǎng)絡(luò)拓撲的時變性，建立了基于任務(wù)類型的TEG 模型，定義各狀態(tài)的連接容量和負載約束。其次，基于離散拓撲對CP 進行初始化、編碼及修復(fù)操作之后，通過構(gòu)建基于差異化任務(wù)的評價函數(shù)及雙向迭代過程來指引粒子的尋優(yōu)方向，使整個粒子群逐漸接近最優(yōu)位置，進而提升算法的持續(xù)尋優(yōu)能力及網(wǎng)絡(luò)性能。最后，通過仿真驗證了BPSO 算法具有很好的任務(wù)傳輸時間和任務(wù)到達率，更適合于在資源受限的LEO 衛(wèi)星網(wǎng)絡(luò)中傳輸大量帶有時效要求的數(shù)據(jù)。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

由于衛(wèi)星節(jié)點圍繞地球周期性運動的特性，使網(wǎng)絡(luò)拓撲結(jié)構(gòu)具有動態(tài)變化、ISL 頻繁切換和通斷關(guān)系隨時間動態(tài)變化的特點。此時，如果LEO 衛(wèi)星和地面站直接建立通信鏈路，信道狀態(tài)會隨著衛(wèi)星運動而動態(tài)變化，繼而影響到網(wǎng)絡(luò)的整體性能。因此，為了解決資源受限情況下LEO 衛(wèi)星網(wǎng)絡(luò)中數(shù)據(jù)采集和傳輸?shù)膯栴}，本文研究并提出了一種基于BPSO 的CPD 方案。

圖1 所示的衛(wèi)星通信網(wǎng)絡(luò)由四類節(jié)點構(gòu)成：1)地面數(shù)據(jù)待采集的源節(jié)點，此類節(jié)點可被看作一個小范圍的數(shù)據(jù)待采集區(qū)域，并令其僅能與衛(wèi)星節(jié)點建立上行鏈路；2)任務(wù)處理中心（MOC,mission operation center），主要用于數(shù)據(jù)處理、制定CP 和CP 的播發(fā)，可以和衛(wèi)星節(jié)點與地面節(jié)點進行雙向通信；3)LEO 衛(wèi)星節(jié)點，主要用于采集和傳輸數(shù)據(jù)，可以與地面站、衛(wèi)星、MOC 建立雙向鏈路；4)地面站目的節(jié)點，主要用于接收數(shù)據(jù)和播發(fā)CP，可以和衛(wèi)星與MOC 建立雙向鏈路。

在如圖1 所示的衛(wèi)星通信網(wǎng)絡(luò)中，數(shù)據(jù)采集和傳輸?shù)倪^程可分為如下步驟。

步驟1任務(wù)源向MOC 發(fā)起任務(wù)請求。

步驟2MOC根據(jù)任務(wù)源發(fā)來的任務(wù)請求和當前衛(wèi)星的傳輸狀態(tài)制定CP，并將計算所得的CP 傳輸?shù)叫l(wèi)星節(jié)點。

步驟3衛(wèi)星根據(jù)接收到的CP 進行一系列數(shù)據(jù)采集和傳輸，并同時將所采集的數(shù)據(jù)傳輸?shù)降孛嬲尽?/p>

步驟4地面站通過地面網(wǎng)絡(luò)將衛(wèi)星采集傳輸過來的數(shù)據(jù)傳輸?shù)組OC 進行統(tǒng)一處理。

圖1 網(wǎng)絡(luò)模型

2.2 基于任務(wù)類型的TEG 模型

如前所述，由于ISL 會因為衛(wèi)星之間的相對運動頻繁地斷開，LEO 衛(wèi)星網(wǎng)絡(luò)的拓撲結(jié)構(gòu)具有時變性，因此，采用TEG[9]來表示隨時間變化的拓撲結(jié)構(gòu)，如圖2 所示。圖2 中a表示待采集的數(shù)據(jù)源節(jié)點，g表示地面站，s表示衛(wèi)星?？紤]到MOC 在數(shù)據(jù)傳輸過程中與地面站功能相當，在圖2 中將其可視為地面站，故未單獨列出。此外，各節(jié)點表示符號的上標表示當前節(jié)點所處的狀態(tài)，下標為當前節(jié)點的索引號，例如表示第3 個狀態(tài)中的衛(wèi)星節(jié)點2。假設(shè)在一個狀態(tài)內(nèi)節(jié)點之間的連接是連續(xù)且恒定的[21]，則各狀態(tài)的持續(xù)時間稱作是連接容量。TEG 通過連接容量的累加來區(qū)分各節(jié)點狀態(tài)，當節(jié)點之間的連接狀態(tài)發(fā)生改變時，網(wǎng)絡(luò)就切換狀態(tài)。將圖2 中節(jié)點狀態(tài)標注為C1,C2,…,Cn，其對應(yīng)的連接容量分別為 CT1,CT2,…,CTn。

基于圖1 所示的衛(wèi)星通信網(wǎng)絡(luò)，圖2 連接拓撲部分給出了包含衛(wèi)星、數(shù)據(jù)采集點和地面站的節(jié)點間連接拓撲；基于網(wǎng)絡(luò)連接拓撲，圖2 連接計劃部分給出了考慮星地鏈路、星間鏈路、數(shù)據(jù)采集鏈路及任務(wù)路徑后的CP，其中所有CP 的鏈路都是通過連接拓撲中的潛在鏈路中挑選出來的。同時，考慮到衛(wèi)星的資源受限，衛(wèi)星節(jié)點在同一時間內(nèi)僅能建立一條鏈路，如式(1)所示。

其中，Pc,n,m表示節(jié)點n和節(jié)點m在狀態(tài)c時建立的鏈路數(shù)量，Ns表示衛(wèi)星節(jié)點的數(shù)量。

圖2 基于任務(wù)類型的TEG 模型

此外，網(wǎng)絡(luò)節(jié)點的負載變化必須滿足式(2)所示的流量守恒原則。

其中，表示在狀態(tài)c時，節(jié)點n負載任務(wù)類型為y的數(shù)據(jù)分組數(shù)量；表示在狀態(tài)c時，任務(wù)y在鏈路m-n上傳輸?shù)臄?shù)據(jù)分組數(shù)量。需要注意的是，由于各狀態(tài)的連接容量有限，故各狀態(tài)傳輸數(shù)據(jù)分組的數(shù)量應(yīng)不大于連接容量，即

3 方案描述

在LEO 衛(wèi)星網(wǎng)絡(luò)中，節(jié)點間的連接會因為節(jié)點的周期性運動而呈現(xiàn)出周期性斷開的特點，且同一時間可建立連接的數(shù)量也受到了嚴格的限制。因而，在采用LEO 衛(wèi)星網(wǎng)絡(luò)進行大規(guī)模數(shù)據(jù)采集和傳輸時，需要針對空間任務(wù)的多樣性和動態(tài)的資源限制設(shè)計來滿足傳輸需求的CP。本文基于傳統(tǒng)PSO 算法的思想，結(jié)合空間任務(wù)傳輸?shù)臅r效性和CP 中鏈路的稀疏性，提出了基于BPSO 的CPD 方案，旨在根據(jù)空間任務(wù)和CP的特點求解出適合在LEO 衛(wèi)星網(wǎng)絡(luò)中執(zhí)行各類空間任務(wù)的CP。

3.1 BPSO 流程

基于BPSO 的CPD 方案的基本思想為：考慮到衛(wèi)星網(wǎng)絡(luò)中CP 的特點，將CP 視作粒子群，引入PSO 算法制定CPD；同時，根據(jù)數(shù)據(jù)采集和傳輸任務(wù)的特點，對粒子進行評價和選擇性保存，進而迭代式地調(diào)整粒子的速度和位置，使粒子群逐漸靠近系統(tǒng)最優(yōu)解。

BPSO 的流程如圖3 所示，其具體實現(xiàn)步驟包括：1)初始化，對BPSO 進行初始化操作，即對BPSO 輸入離散拓撲、任務(wù)屬性、相關(guān)參數(shù)等；2)編碼，根據(jù)生成的初始粒子群的負載情況和連接拓撲結(jié)構(gòu)對CP 進行二進制序列編碼；3)修復(fù)，由于隨機生成的粒子可能打破系統(tǒng)的傳輸要求，需要對粒子進行修復(fù)操作；4)計算最終適應(yīng)值，根據(jù)到達時間和任務(wù)特點計算粒子群內(nèi)各粒子的最終適應(yīng)值，并通過各粒子的最終適應(yīng)值區(qū)分粒子在粒子群中的優(yōu)劣；5)判斷是否終止算法，判斷當前迭代次數(shù)是否滿足終止條件，如果滿足則跳出循環(huán)終止算法，否則進入下一步；6)雙向?qū)?yōu)，BPSO 根據(jù)評價結(jié)果和歷史信息來保存歷史極值以及對應(yīng)的比特序列，同時計算出當前粒子群的平均位置，然后隨機生成一個二進制值randB，如果randB=1，粒子則根據(jù)最優(yōu)位置進行尋優(yōu)，否則粒子根據(jù)最差位置中的待校正比特位置進行尋優(yōu)，至此各粒子根據(jù)隨機二進制數(shù)和保存的歷史信息即可調(diào)整自身的速度和位置。

3.2 CP 的表示

CP 的表示包含初始化模塊、編碼模塊及修復(fù)模塊，在完成這3 個模塊后，CP 才能滿足系統(tǒng)傳輸要求并被合理的表示。

在初始化階段，不僅需要提前確定BPSO 在執(zhí)行尋優(yōu)步驟所要用到的影響因子、慣性權(quán)重等參數(shù)，還需要通過離散拓撲結(jié)構(gòu)確定各狀態(tài)的狀態(tài)長度及比特序列中各比特的表示鏈路。編碼是通過確定的狀態(tài)長度和離散拓撲把CP 轉(zhuǎn)換成一個二進制序列，以使計算機在算法迭代過程中更方便地進行處理。因為初始的隨機序列未考慮系統(tǒng)的傳輸要求，故接下來還需要對序列進行修復(fù)。圖4 通過一個示例闡述了CP 的表示過程。

圖3 BPSO 流程

圖4 CP 表示過程

圖4 描述了一個六節(jié)點網(wǎng)絡(luò)從初始化到修復(fù)的CP 表示過程。首先，BPSO 通過離散連接拓撲各狀態(tài)的連接情況，逐個狀態(tài)依次提取出潛在的可用鏈路，并根據(jù)狀態(tài)內(nèi)鏈路來構(gòu)建連接矩陣，以便管理沖突鏈路。需要注意的是，本文的潛在的鏈路均是有向鏈路，故一條鏈路需向連接矩陣中填2 個元素。然后，根據(jù)仿真時間統(tǒng)計潛在鏈路的總數(shù)，該數(shù)是各CP 的序列長度。最后，BPSO 根據(jù)粒子群大小及序列長度生成一定數(shù)量的隨機二進制序列作為初始序列。

3.1節(jié)描述了BPSO 在初始化和生成隨機序列的執(zhí)行步驟。但是，由于執(zhí)行步驟并未考慮CPD的半雙工傳輸限制，也未考慮到傳輸效率的問題，因此完成隨機初始化的CP 需執(zhí)行修復(fù)操作以滿足系統(tǒng)的傳輸要求。BPSO 的修復(fù)主要考慮2 個方面：一方面為了滿足系統(tǒng)半雙工傳輸限制對產(chǎn)生建立沖突的鏈路進行管理；另一方面為了提高傳輸效率避免建立空負載鏈路。對于沖突管理而言，如果按照序列從左到右的順序管理建立需求，則處在狀態(tài)起始端的鏈路勢必更容易建立，而處于末端的鏈路則會因為發(fā)送節(jié)點或接收節(jié)點被占據(jù)而放棄建立。因此，在沖突管理之前，BPSO 需要有一個大小為當前狀態(tài)長度的隨機順序序列，并按隨機生成的順序及對應(yīng)的二進制值來確定哪條鏈路應(yīng)該優(yōu)先建立。建立鏈路后，將連接矩陣鏈路對應(yīng)的行/列元素全設(shè)置為不可用，以防止其他有需求的沖突鏈路誤建立。對于空負載鏈路而言，如果當前發(fā)送節(jié)點為空負載，則默認不建立該鏈路，以此來提升鏈路的使用效率。

3.3 基于任務(wù)時間特性的評價函數(shù)

完成修復(fù)后的序列為完整且可行的CP，為了區(qū)分各粒子在粒子群中的優(yōu)劣，下面對粒子進行評價。基于傳統(tǒng)智能算法的CPD 方案通常僅利用數(shù)據(jù)分組的傳輸狀態(tài)來評價CP 的優(yōu)劣[11-14]，忽略了不同任務(wù)的數(shù)據(jù)分組可能擁有不同的時間要求，這導(dǎo)致網(wǎng)絡(luò)中數(shù)據(jù)分組的到達率降低。為此，本文提出了一種考慮任務(wù)到達時間、數(shù)據(jù)分組傳輸狀態(tài)及數(shù)據(jù)分組生存時間的綜合評價方式來提升任務(wù)數(shù)據(jù)的到達率，具體實現(xiàn)如式(4)所示。

其中，F(xiàn)為適應(yīng)值，該值的大小表示粒子的優(yōu)劣程度；Tc為狀態(tài)c的起始時間；是任務(wù)y的任務(wù)發(fā)起時間；φ(TAy)為任務(wù)y的罰函數(shù)，其計算式為

其中，為任務(wù)y的生存時間；為任務(wù)y需傳輸?shù)乃袛?shù)據(jù)分組的數(shù)量；為傳輸時間超出生存時間數(shù)據(jù)分組的數(shù)量；為超出生存時間的分組的平均傳輸時間，其計算式為

完成評價后，BPSO 判斷當前是否滿足迭代結(jié)束的條件。本文采用靜態(tài)終止條件來決定算法是否結(jié)束，即達到一定迭代次數(shù)后，BPSO 終止，否則，進入第4 節(jié)的尋優(yōu)流程。

4 基于CP 鏈路稀疏性的雙向?qū)?yōu)

在傳統(tǒng)PSO 中，粒子的速度和位置通常都基于歷史最優(yōu)信息進行更新，這種方法可以快速地調(diào)整粒子的運動方向，使粒子快速地朝著自身認為的最優(yōu)位置方向移動[15]。在衛(wèi)星網(wǎng)絡(luò)的CPD 中，粒子中各比特的值會因為系統(tǒng)中衛(wèi)星轉(zhuǎn)發(fā)器數(shù)量的限制而相互制約，如果直接采用傳統(tǒng)PSO，雖然可以簡單快速地調(diào)整粒子運動軌跡，但是會導(dǎo)致粒子的比特串中大規(guī)模出現(xiàn)0 值，進而縮小粒子之間的差異，使粒子極有可能過快地進入局部優(yōu)化，從而難以獲得一個傳輸效率高效的CP。為此，本文提出了一種基于CP 鏈路稀疏性的雙向?qū)?yōu)機制來引導(dǎo)粒子的運動方向。

通過將粒子的當前位置與歷史最差或最優(yōu)位置進行比較，可以有效地引導(dǎo)粒子的運動方向，并逐漸靠近最優(yōu)位置。因此，完成評價后對粒子的歷史信息進行更新，并根據(jù)這些更新后的最優(yōu)/最差位置動態(tài)地調(diào)整粒子自身的速度和位置。各粒子一共需保存四類極值及極值所對應(yīng)的位置，這四類極值分別是全局最優(yōu)值、全局最差值、局部最優(yōu)值和局部最差值，其中，全局極值及位置由粒子群共享，而局部極值及位置則由各粒子自身的歷史信息決定。

從圖4 中的示例看到，系統(tǒng)的限制條件會使可行CP 的比特串中大比例出現(xiàn)0 值。即使是擁有歷史最差值的粒子，其序列串中的大量0 值都會因為空負載而禁止建立鏈路。換言之，低適應(yīng)值粒子也擁有大量與高適應(yīng)值粒子相同比特位置的0 值，也即可用CP 中的鏈路具有稀疏性。如果此時直接按最差位置來反向調(diào)整粒子速度，最差粒子的稀疏鏈路會影響各粒子的位置向1 值靠近，從而大范圍地打破系統(tǒng)限制，最終，各粒子需要大量的修復(fù)才能滿足傳輸要求，使網(wǎng)絡(luò)性能惡化。因此，BPSO 在利用最差位置對各粒子進行尋優(yōu)方向引導(dǎo)時，需提前找出最差位置中能夠正確引導(dǎo)粒子方向的比特位置。為此，BPSO 引入了平均位置的概念，并根據(jù)平均位置與最差位置的對比來確定最差位置中待校正的比特。

在求取粒子群的平均位置前，先引入以下幾個統(tǒng)計參數(shù)：狀態(tài)c下鏈路n-m在粒子群中建立的次數(shù)Nc,n,m；狀態(tài)c下鏈路n-m關(guān)聯(lián)鏈路的類型數(shù)；狀態(tài)c的鏈路類型數(shù)（狀態(tài)長度）；狀態(tài)c下鏈路n-m的關(guān)聯(lián)鏈路在粒子群中建立的次數(shù)；當前粒子CPi在狀態(tài)c建立的鏈路數(shù)；粒子群在狀態(tài)c建立的鏈路總數(shù)；粒子CPi在狀態(tài)c第j個比特的值。 各參數(shù)之間的關(guān)系如圖5 所示。

圖5 平均位置相關(guān)統(tǒng)計參數(shù)的關(guān)系示意

圖5 描述了圖4 中初始狀態(tài)的首個比特平均位置的相關(guān)參數(shù)之間的關(guān)系。由于該狀態(tài)中第一個比特表示鏈路1 -2，可能與其產(chǎn)生沖突的相關(guān)鏈路分別是2 -1 、1 -6 、6 -1 、2 -5 和5 -2 。如果簡單按照建立當前鏈路的粒子總數(shù)是否超過粒子群數(shù)量的一半來決定當前比特的均值是否為1，則粒子群的均值只會有極少的比特值為1，進而導(dǎo)致許多有效鏈路閑置，最終錯誤地引導(dǎo)粒子的運動方向。為此，在求取平均位置時，BPSO 不僅考慮了當前鏈路在狀態(tài)內(nèi)的建立情況，還考慮了與其沖突的關(guān)聯(lián)鏈路建立情況，使平均位置能夠合理地表示出粒子群在當前迭代的平均狀態(tài)。平均位置的計算流程如圖6所示。在計算平均位置時，先通過式(7)計算當前鏈路獎勵數(shù)量比，再用式(8)計算當前鏈路類型數(shù)量比

通過對比式(7)和式(8)的計算結(jié)果，可以判斷出粒子群中當前鏈路n-m是否被大多數(shù)粒子所建立。而利用式(9)的計算結(jié)果與比較，可以判斷出粒子群中當前鏈路n-m是否在其相關(guān)鏈路集合中被大比例地建立。

在傳統(tǒng)PSO 中，粒子的速度與位置僅通過最優(yōu)歷史信息來更新，這種方法能夠快速地調(diào)整粒子的運動方向，使粒子迅速地朝歷史最優(yōu)位置的方向移動。但是，由于該方法對粒子運動的影響方式單一，容易限制粒子的搜索空間使其過早地進入局部優(yōu)化，從而影響系統(tǒng)的性能。為此，BPSO 設(shè)計了基于CP 鏈路稀疏性的雙向?qū)?yōu)方法來更新粒子的速度與位置，具體如式(10)和式(11)所示。

圖6 平均位置計算流程

其中，wmin和wmax分別是輸入系統(tǒng)的最小慣性權(quán)重和最大慣性權(quán)重；fmin(iter)和fave(iter)分別是第iter 次迭代粒子群的最小適應(yīng)值和平均適應(yīng)值；是第iter 次迭代粒子CPi的適應(yīng)值。

完成速度和權(quán)值更新的粒子根據(jù)式(15)來計算自身的位置。

由于各比特最終的展現(xiàn)形式是二進制數(shù)，則最終粒子的第j比特的值通過式(16)來計算。

由于僅依靠歷史信息更新的位置并沒有考慮系統(tǒng)在轉(zhuǎn)發(fā)器數(shù)量上的限制，故BPSO 需重新對新生成的序列進行修復(fù)，基于CP 鏈路稀疏性的雙向?qū)?yōu)過程一直迭代至滿足算法的終止條件，得到的最終CP 為擁有全局最優(yōu)適應(yīng)值的粒子位置。

5 仿真與分析

為了驗證本文模型及所提算法的有效性，本文利用Matlab 和衛(wèi)星工具箱（STK,satellite tool kit）進行聯(lián)合仿真。

LEO 衛(wèi)星網(wǎng)絡(luò)采用Iridium 星座，即6 條極軌軌道，各軌道擁有11 顆衛(wèi)星。LEO 衛(wèi)星網(wǎng)絡(luò)中的各衛(wèi)星分別能與同軌道的相鄰衛(wèi)星和相鄰軌道距離最近的衛(wèi)星建立通信鏈路。其中，軌內(nèi)鏈路可以持續(xù)建立，軌間鏈路會在2 個極區(qū)上方關(guān)閉。衛(wèi)星工具箱（STK,satellite tool kit）模擬場景共設(shè)置3個數(shù)據(jù)采集區(qū)域，分別位于印度、澳大利亞和美國，任務(wù)發(fā)起的具體位置在采集區(qū)域內(nèi)隨機產(chǎn)生；各采集區(qū)域分別發(fā)起20 個數(shù)據(jù)采集任務(wù)。所有任務(wù)共包含1 000 個數(shù)據(jù)分組，各任務(wù)的發(fā)起時間和待采集數(shù)據(jù)分組數(shù)量均服從泊松分布[22]。以實驗仿真的起始時刻為起點，各任務(wù)的發(fā)起時間與仿真起始時間之間的最短間隔不超過7 200 s。地面站分別位于和田（37.11°N，79.92°E）、密云（40.45°N，116.86°E）和西安（34.45°N，109.49°E）。簡便起見，假設(shè)各鏈路每秒傳輸一個數(shù)據(jù)分組[21]，各數(shù)據(jù)分組的生存時間為4 800 s。在BPSO 中，粒子群大小、最小慣性權(quán)重、最大慣性權(quán)重、局部學(xué)習(xí)因子和全局學(xué)習(xí)因子分別設(shè)置為100、0.6、0.8、2 和2。LEO 衛(wèi)星網(wǎng)絡(luò)的軌道相關(guān)參數(shù)如表1 所示。

表1 LEO 衛(wèi)星網(wǎng)絡(luò)軌道相關(guān)參數(shù)

此外，本文選取GA[11]和PSO 算法[15]這2 種經(jīng)典的啟發(fā)式算法作為對比算法。為了提高可比性，對比算法的相關(guān)參數(shù)的設(shè)置盡可能地與BPSO 相同，無法設(shè)置為相同的參數(shù)則設(shè)置為常用取值。GA 的交叉率和變異率分別設(shè)置為0.6 和0.05，采用精英策略選取子代。PSO 算法的慣性權(quán)重設(shè)置為0.7。除了沒有BPSO 為各任務(wù)設(shè)計的罰函數(shù)，對比算法的評價方式與BPSO相同，以便直觀地對比算法之間的性能差異。

圖7 中的平均適應(yīng)值指的是粒子群的平均適應(yīng)值，圖8 中的最優(yōu)適應(yīng)值指的是歷史最優(yōu)個體的適應(yīng)值。由于在迭代過程中都保存了優(yōu)秀個體，3 種算法的平均適應(yīng)值和最優(yōu)適應(yīng)值都隨著迭代次數(shù)的增長而逐漸增加。由于GA 的交叉和變異操作可以大范圍地重組比特序列，其平均適應(yīng)值和最優(yōu)適應(yīng)值在200 次迭代后還能夠持續(xù)增長。但由于該算法盲目的變異和交叉很容易打破系統(tǒng)傳輸限制，每次更新完比特序列后，GA 都需要大面積修復(fù)，這也決定了該算法迭代效率落后于 PSO 算法和BPSO。對于PSO 算法而言，由于算法只受歷史最優(yōu)信息的影響，故其平均適應(yīng)值和最優(yōu)適應(yīng)值很快收斂并最終落后于BPSO。由于BPSO 的粒子受到兩類極值的影響，故該算法的尋優(yōu)能力更強，并最終在適應(yīng)值上高于其他2 種對比算法。

圖7 粒子群的平均適應(yīng)值

圖8 歷史最優(yōu)個體的適應(yīng)值

圖9 的傳輸時間表示的是LEO 衛(wèi)星網(wǎng)絡(luò)傳輸完所有數(shù)據(jù)分組所耗費的時間，圖10 是每個數(shù)據(jù)分組到達地面站平均耗費的時間。如圖9 和圖10 所示，各算法傳輸時間變化的趨勢基本與圖7中平均適應(yīng)值的變化趨勢保持一致，平均適應(yīng)值越高，數(shù)據(jù)分組傳遞時間越小。GA 需更久的迭代次數(shù)才能收斂，PSO算法快收斂但最終傳輸時間不如BPSO。需要指出的是，對于PSO 算法和BPSO 在平均傳輸時間上的對比，算法之間的差距并沒有傳輸時間那么大。這是因為平均適應(yīng)值更容易被傳輸時間較長的數(shù)據(jù)分組影響，而較早到達的數(shù)據(jù)分組并不能顯著地提升平均適應(yīng)值。

圖9 所有數(shù)據(jù)分組傳輸完成的耗費時間

圖10 各數(shù)據(jù)分組到達地面站的平均耗時

圖11 描述了3 種算法的鏈路消耗數(shù)量隨迭代次數(shù)增加而變化的趨勢。相較于PSO 算法，BPSO在鏈路消耗數(shù)上并不占優(yōu)勢，這是因為BPSO 為了到達率和傳輸時間上的優(yōu)勢，所生成的CP 會避開跳數(shù)較少但更擁堵的路徑，選擇跳數(shù)相對較多但不擁塞的路徑來換取傳輸時間。

圖11 3 種算法的鏈路消耗變化對比

從圖12 可以明顯地看出，BPSO 的到達率明顯優(yōu)于其他2 種對比算法，甚至在迭代初期，BPSO的迭代效率也優(yōu)于PSO 算法。這是因為BPSO 利用各任務(wù)數(shù)據(jù)的時間特點來對粒子個體進行懲罰，使算法能夠快速地挑選出到達率更高的粒子，而且這些粒子能夠在迭代過程中高效地引導(dǎo)其他粒子運動，最終使粒子群的到達率得到一個迅速且持續(xù)地提升。

圖12 各數(shù)據(jù)分組的到達率

6 結(jié)束語

本文針對資源受限衛(wèi)星網(wǎng)絡(luò)中數(shù)據(jù)傳輸效率低的問題，提出了一種基于BPSO 的CPD 方案。首先，基于網(wǎng)絡(luò)拓撲分析了衛(wèi)星網(wǎng)絡(luò)中的CP 特性，根據(jù)CP 特征通過編碼修復(fù)操作生成了可用CP；然后，根據(jù)空間任務(wù)類型的不同制定了評價函數(shù)，并根據(jù)評價函數(shù)所得的適應(yīng)值區(qū)分CP 的優(yōu)劣；最后，考慮到CPD 中鏈路稀疏的特點，通過計算所得的平均位置和保存的最差位置來確定最差位置的待糾正比特，進而通過最差位置的反向引導(dǎo)和最優(yōu)的正向引導(dǎo)來調(diào)整粒子的尋優(yōu)方向，最終獲得一個適合傳輸任務(wù)數(shù)據(jù)的CP。仿真結(jié)果表明，與經(jīng)典優(yōu)化算法PSO 和GA 相比，本文提出的BPSO 利用了較小的鏈路開銷來換取傳輸時間及到達率的優(yōu)勢，更適合于資源受限衛(wèi)星網(wǎng)絡(luò)中傳輸大量帶有時效要求的數(shù)據(jù)。