衛(wèi)星網(wǎng)絡(luò)中基于雙向?qū)?yōu)粒子群優(yōu)化算法的連接計(jì)劃設(shè)計(jì)

戴翠琴，唐煌，郭林峰

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

1 引言

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

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

基于圖1 所示的衛(wèi)星通信網(wǎng)絡(luò)，圖2 連接拓?fù)洳糠纸o出了包含衛(wèi)星、數(shù)據(jù)采集點(diǎn)和地面站的節(jié)點(diǎn)間連接拓?fù)洌换诰W(wǎng)絡(luò)連接拓?fù)?，圖2 連接計(jì)劃部分給出了考慮星地鏈路、星間鏈路、數(shù)據(jù)采集鏈路及任務(wù)路徑后的CP，其中所有CP 的鏈路都是通過連接拓?fù)渲械臐撛阪溌分刑暨x出來的。同時(shí)，考慮到衛(wèi)星的資源受限，衛(wèi)星節(jié)點(diǎn)在同一時(shí)間內(nèi)僅能建立一條鏈路，如式(1)所示。

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

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

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

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

3.1 BPSO 流程

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

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

3.2 CP 的表示

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

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

圖3 BPSO 流程

圖4 CP 表示過程

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

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

3.3 基于任務(wù)時(shí)間特性的評(píng)價(jià)函數(shù)

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

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

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

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

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

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

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

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

在求取粒子群的平均位置前，先引入以下幾個(gè)統(tǒng)計(jì)參數(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ù)；當(dāng)前粒子CPi在狀態(tài)c建立的鏈路數(shù)；粒子群在狀態(tài)c建立的鏈路總數(shù)；粒子CPi在狀態(tài)c第j個(gè)比特的值。 各參數(shù)之間的關(guān)系如圖5 所示。

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

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

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

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

圖6 平均位置計(jì)算流程

其中，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)來計(jì)算自身的位置。

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

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

5 仿真與分析

為了驗(yàn)證本文模型及所提算法的有效性，本文利用Matlab 和衛(wèi)星工具箱（STK,satellite tool kit）進(jìn)行聯(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ù)建立，軌間鏈路會(huì)在2 個(gè)極區(qū)上方關(guān)閉。衛(wèi)星工具箱（STK,satellite tool kit）模擬場(chǎng)景共設(shè)置3個(gè)數(shù)據(jù)采集區(qū)域，分別位于印度、澳大利亞和美國，任務(wù)發(fā)起的具體位置在采集區(qū)域內(nèi)隨機(jī)產(chǎn)生；各采集區(qū)域分別發(fā)起20 個(gè)數(shù)據(jù)采集任務(wù)。所有任務(wù)共包含1 000 個(gè)數(shù)據(jù)分組，各任務(wù)的發(fā)起時(shí)間和待采集數(shù)據(jù)分組數(shù)量均服從泊松分布[22]。以實(shí)驗(yàn)仿真的起始時(shí)刻為起點(diǎn)，各任務(wù)的發(fā)起時(shí)間與仿真起始時(shí)間之間的最短間隔不超過7 200 s。地面站分別位于和田（37.11°N，79.92°E）、密云（40.45°N，116.86°E）和西安（34.45°N，109.49°E）。簡便起見，假設(shè)各鏈路每秒傳輸一個(gè)數(shù)據(jù)分組[21]，各數(shù)據(jù)分組的生存時(shí)間為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ā)式算法作為對(duì)比算法。為了提高可比性，對(duì)比算法的相關(guān)參數(shù)的設(shè)置盡可能地與BPSO 相同，無法設(shè)置為相同的參數(shù)則設(shè)置為常用取值。GA 的交叉率和變異率分別設(shè)置為0.6 和0.05，采用精英策略選取子代。PSO 算法的慣性權(quán)重設(shè)置為0.7。除了沒有BPSO 為各任務(wù)設(shè)計(jì)的罰函數(shù)，對(duì)比算法的評(píng)價(jià)方式與BPSO相同，以便直觀地對(duì)比算法之間的性能差異。

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

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

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

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

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

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

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

圖11 3 種算法的鏈路消耗變化對(duì)比

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

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

6 結(jié)束語

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