劉冰怡，王璐琦，郭 薇，朱維各

（1.上海交通大學(xué)區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海 200240；2.上海衛(wèi)星工程研究所，上海 200240）

引 言

對(duì)月球的探測(cè)是人類向深空邁出的第一步。早在20世紀(jì)60年代，美國(guó)和前蘇聯(lián)就開始了一系列對(duì)月球的探測(cè)活動(dòng)。從21世紀(jì)初開始，許多國(guó)家也紛紛開展各自的探月研究項(xiàng)目，深空探測(cè)也被列為中國(guó)21世紀(jì)發(fā)展戰(zhàn)略之一。

2018年5月21日，中國(guó)發(fā)射了“鵲橋號(hào)”衛(wèi)星，該衛(wèi)星圍繞月球背面的地月拉格朗日點(diǎn)運(yùn)動(dòng)，采集到的月球背面的科學(xué)數(shù)據(jù)，由“鵲橋號(hào)”中繼，以點(diǎn)對(duì)點(diǎn)的通信方式，通過星地鏈路回傳到地面站。當(dāng)?shù)孛嬲倦S著地球自轉(zhuǎn)運(yùn)動(dòng)到與鵲橋號(hào)衛(wèi)星不可見的位置時(shí)，通信鏈路中斷。在通信鏈路中斷時(shí)間段內(nèi)，鵲橋號(hào)采集到的數(shù)據(jù)將無法回傳。由此可見，該地月通信架構(gòu)無法滿足面向月球的全時(shí)域、多節(jié)點(diǎn)、全覆蓋的通信要求[1-2]，無法支持未來日益復(fù)雜的人類探月活動(dòng)所帶來的遙測(cè)、遙控、導(dǎo)航、語(yǔ)音等通信類業(yè)務(wù)。

孫晨華等[2-3]指出，由多顆月球中繼衛(wèi)星、地球中繼衛(wèi)星和地面站組成的地月空間信息網(wǎng)絡(luò)在對(duì)星球的覆蓋范圍、測(cè)控時(shí)間、傳輸可靠性、節(jié)點(diǎn)冗余性等方面較其它地月通信架構(gòu)更有優(yōu)勢(shì)。然而基于該架構(gòu)下，目前并沒有研究具體指出應(yīng)該構(gòu)建一個(gè)怎樣的地月空間信息網(wǎng)絡(luò)拓?fù)洹?/p>

在設(shè)計(jì)衛(wèi)星網(wǎng)絡(luò)拓?fù)鋾r(shí)，通常關(guān)心的性能指標(biāo)有網(wǎng)絡(luò)的平均點(diǎn)到點(diǎn)通信延遲（在衛(wèi)星網(wǎng)絡(luò)中，傳播時(shí)延是產(chǎn)生通信時(shí)延的主要因素[4]）、網(wǎng)絡(luò)連通性等。本文設(shè)計(jì)的地月空間信息網(wǎng)絡(luò)旨在為地球與月球之間的通信類業(yè)務(wù)提供遠(yuǎn)距離中繼服務(wù)，主要關(guān)注地月之間的通信質(zhì)量。因此，在設(shè)計(jì)網(wǎng)絡(luò)拓?fù)鋾r(shí)，選擇平均月球中繼衛(wèi)星節(jié)點(diǎn)到地面站的路徑距離來計(jì)算該網(wǎng)絡(luò)的平均傳播時(shí)延，并以最小化該平均距離為優(yōu)化目標(biāo)，以滿足未來地月遙測(cè)、遙控、語(yǔ)音和視頻等實(shí)時(shí)通信類業(yè)務(wù)的需求。同時(shí)為了使該網(wǎng)絡(luò)能夠?yàn)榈卦轮g提供持續(xù)通信，設(shè)計(jì)拓?fù)鋾r(shí)還應(yīng)滿足月球中繼衛(wèi)星與地面站之間的連通性約束，即每顆月球中繼衛(wèi)星總存在一條到地面站的連通路徑。

因功率、重量和成本等因素的限制，每顆衛(wèi)星所允許攜帶的通信終端數(shù)目是有限的（建立一條鏈路的同時(shí)需要占用該鏈路兩端節(jié)點(diǎn)上各一個(gè)通信終端），但是能夠與這些衛(wèi)星建立通信鏈路的節(jié)點(diǎn)數(shù)目往往超過其所攜帶的終端數(shù)目。因此，如何分配每個(gè)衛(wèi)星節(jié)點(diǎn)上有限的通信終端建立鏈路，從而構(gòu)建一個(gè)性能良好的地月空間信息網(wǎng)絡(luò)拓?fù)?，成為了一個(gè)有意義的研究問題。

本文所研究的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)問題即通信鏈路的分配問題。對(duì)此，針對(duì)由多顆月球中繼衛(wèi)星、地球中繼衛(wèi)星和地面站節(jié)點(diǎn)組成的地月空間信息網(wǎng)絡(luò)，本文設(shè)計(jì)了兩種鏈路分配算法：基于競(jìng)爭(zhēng)決策思想的鏈路分配算法（Link Assignment Algorithm Based On Competitive Decision，LAA-CD）和基于模擬退火法的鏈路分配算法（Link Assignment Algorithm Based On Simulated Annealing，LAA-SA），旨在解決地月空間信息網(wǎng)絡(luò)衛(wèi)星通信終端數(shù)目有限情況下的鏈路分配問題。算法以最小化平均月球中繼衛(wèi)星節(jié)點(diǎn)到地面站距離為優(yōu)化目標(biāo)，在保證月球中繼衛(wèi)星與地面站連通性的同時(shí)，每顆衛(wèi)星所連接的鏈路數(shù)目不超過其攜帶的通信終端數(shù)目。

在地月空間信息衛(wèi)星網(wǎng)絡(luò)中，衛(wèi)星與衛(wèi)星、衛(wèi)星與地面站之間的可見性隨著地球自轉(zhuǎn)和衛(wèi)星運(yùn)動(dòng)而不斷變化，只有當(dāng)兩個(gè)節(jié)點(diǎn)彼此可視時(shí)，才有可能建立鏈路。因此，每個(gè)節(jié)點(diǎn)將會(huì)隨著與其可視的節(jié)點(diǎn)集合的變化而動(dòng)態(tài)地建立和刪除鏈路。為了便于為一個(gè)動(dòng)態(tài)的網(wǎng)絡(luò)設(shè)計(jì)拓?fù)洌瑢⒁欢螘r(shí)間內(nèi)的網(wǎng)絡(luò)劃分為若干個(gè)時(shí)隙如圖1（a），時(shí)隙的劃分由可見關(guān)系的變化觸發(fā)，一個(gè)時(shí)隙內(nèi)所有節(jié)點(diǎn)之間的可視關(guān)系不發(fā)生變化。圖1（b）分別對(duì)應(yīng)圖1（a）中時(shí)隙i和時(shí)隙j下的可視關(guān)系，虛線表示節(jié)點(diǎn)之間可視，當(dāng)S3 運(yùn)動(dòng)到與S4可視的位置時(shí)，即進(jìn)入一個(gè)新的時(shí)隙。

圖1 時(shí)隙的劃分Fig.1 Division of time slots

1 相關(guān)研究

目前，網(wǎng)絡(luò)鏈路分配問題的研究對(duì)象主要包括某些具有高動(dòng)態(tài)性的網(wǎng)絡(luò)（如Ad Hoc 網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)）和近地衛(wèi)星網(wǎng)絡(luò)。在以Ad Hoc 網(wǎng)絡(luò)或傳感器網(wǎng)絡(luò)為研究對(duì)象的拓?fù)湓O(shè)計(jì)研究中[5-7]，拓?fù)湓O(shè)計(jì)的優(yōu)化目標(biāo)通常為提高網(wǎng)絡(luò)連通性、降低能耗等。文獻(xiàn)[8]以最小化地面站管理資源為優(yōu)化目標(biāo)，提出了一種基于煙花算法的鏈路分配算法，但是沒有考慮衛(wèi)星終端數(shù)目的約束；Lansard等[9]針對(duì)由低軌、中軌衛(wèi)星組成的網(wǎng)絡(luò)，介紹了距離優(yōu)先的貪婪鏈路選擇策略；Liu 等[10]中要求將每顆衛(wèi)星上所有的終端都用于建立星間鏈路，提出了一種基于拓?fù)鋱D完美匹配模型的鏈路分配算法；Tan等[11]提出了一種通過為可視的衛(wèi)星之間隨機(jī)分配星間鏈路，直到被通信終端的占用率達(dá)到某個(gè)給定值的鏈路分配算法；NOAKES 等[12]以保證網(wǎng)絡(luò)拓?fù)湔w的連通性為目標(biāo)，設(shè)計(jì)了一種針對(duì)動(dòng)態(tài)衛(wèi)星網(wǎng)絡(luò)的鏈路分配算法，根據(jù)網(wǎng)絡(luò)狀態(tài)的變化決定鏈路的建立和連接；Harathik等[13]針對(duì)具有兩個(gè)軌道平面，并且兩個(gè)軌道平面上的衛(wèi)星數(shù)目相同的衛(wèi)星星座，以最大化通信終端的利用率為優(yōu)化目標(biāo)，研究了當(dāng)衛(wèi)星的可視節(jié)點(diǎn)數(shù)目多于其星載通信終端數(shù)目情況下的鏈路分配問題；Watts 等[14-16]的鏈路分配算法均以平均點(diǎn)到點(diǎn)距離最小為優(yōu)化目標(biāo)，但是都沒有考慮到該方法實(shí)際情況下衛(wèi)星上終端數(shù)目的約束，且計(jì)算平均點(diǎn)到點(diǎn)距離最小的優(yōu)化目標(biāo)并不適用于地月通信場(chǎng)景；Fraire 等[17]的算法雖然能夠提高拓?fù)涞倪B接密度，但是仍然不能保證網(wǎng)絡(luò)的連通性；Huang等[18]針對(duì)DTN（Delay Tolerant Networks）衛(wèi)星網(wǎng)絡(luò)，考慮到衛(wèi)星節(jié)點(diǎn)可視關(guān)系動(dòng)態(tài)變化的特點(diǎn)，以最小化連接數(shù)為優(yōu)化目標(biāo)設(shè)計(jì)拓?fù)?，但仍然忽略了通信終端數(shù)目的約束。

上述鏈路分配相關(guān)研究并沒有綜合考慮衛(wèi)星網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)問題中的多個(gè)因素，如平均時(shí)延、衛(wèi)星所攜帶的通信終端數(shù)目限制、連通性等，且在平均時(shí)延和連通性的定義上，地月空間信息網(wǎng)絡(luò)拓?fù)洳煌谄渌W(wǎng)絡(luò)，本文關(guān)注的是月球中繼衛(wèi)星與地面站之間的平均距離和連通性，而非所有網(wǎng)絡(luò)節(jié)點(diǎn)之間的平均距離和連通性。因此，以上研究中的算法并不適用于本文研究場(chǎng)景，需要設(shè)計(jì)一種針對(duì)地月空間信息網(wǎng)絡(luò)場(chǎng)景的鏈路分配算法。此外，地月空間信息網(wǎng)絡(luò)方面的研究大多關(guān)于衛(wèi)星星座架構(gòu)設(shè)計(jì)方面，具體拓?fù)湓O(shè)計(jì)的研究目前仍出于空白階段。

2 基于競(jìng)爭(zhēng)決策思想的鏈路分配算法（LAA-CD）和基于模擬退火法的鏈路分配算法（LAA-SA）

2.1 符號(hào)說明

地月空間信息網(wǎng)絡(luò)鏈路分配問題中的參數(shù)和含義如下：

vstation：地面站節(jié)點(diǎn)；

Vm：月球中繼衛(wèi)星節(jié)點(diǎn)集合；

Ve：地球中繼衛(wèi)星節(jié)點(diǎn)集合；

m：月球中繼衛(wèi)星數(shù)目；

n：地球中繼衛(wèi)星數(shù)目；

N：每顆衛(wèi)星允許攜帶的通信終端數(shù)目上限；

d(v)：衛(wèi)星節(jié)點(diǎn)v的度數(shù)，即v所連接的鏈路的條數(shù)，v∈Vm∪Ve；

V：加權(quán)可視矩陣。當(dāng)節(jié)點(diǎn)i和j彼此之間可視時(shí)，V(i,j)大小等于i與j之間的距離；反之，V(i,j)=∞；

G：網(wǎng)絡(luò)拓?fù)渚仃?。?dāng)為節(jié)點(diǎn)i和j之間分配了一條鏈路時(shí)，G(i,j)=V(i,j)；反之，G(i,j)= ∞；

a(i,j)：表明節(jié)點(diǎn)i和j之間是否連通。當(dāng)i和j之間存在至少一條通路時(shí)，a(i,j)= 1，否則a(i,j)= 0；

p1(i,j)：節(jié)點(diǎn)i到j(luò)的最短路徑；

dist(i,j)：表示p1(i,j)的距離；

h(i,j)：從節(jié)點(diǎn)i到j(luò)最短路徑的跳數(shù)；

p2(i,j)：節(jié)點(diǎn)i到j(luò)的次短路徑；

distsec(i,j)：表示p2(i,j)的距離；

n(v)：v∈Vm，表示月球中繼衛(wèi)星v到vstation的最短路徑與其它月球中繼衛(wèi)星到vstation最短路徑的公共節(jié)點(diǎn)數(shù)目。

2.2 數(shù)學(xué)模型

基于上述問題描述和符號(hào)說明，地月空間信息網(wǎng)絡(luò)鏈路分配算法的優(yōu)化目標(biāo)可以表示為

約束條件為

由于每顆衛(wèi)星攜帶的終端數(shù)目是相同的，且鏈路是雙向的，上述加權(quán)可視矩陣V和網(wǎng)絡(luò)拓?fù)渚仃嘒均是一個(gè)大小為(m+n+ 1)×(m+n+ 1)的對(duì)稱矩陣。利用Dijkstra 算法，可以計(jì)算出每顆月球中繼衛(wèi)星到地面站的最短路徑距離。

約束條件C1 確保了網(wǎng)絡(luò)的連通性，即每顆月球中繼衛(wèi)星都存在一條與地面站之間的連通路徑；C2則是考慮到了衛(wèi)星攜帶終端數(shù)目的限制，在設(shè)計(jì)算法的過程中需要保證每顆衛(wèi)星連接不超過N條鏈路。

2.3 基于競(jìng)爭(zhēng)決策思想的鏈路分配算法LAA-CD

在設(shè)計(jì)鏈路分配方案的過程中，為了減少月球中繼衛(wèi)星節(jié)點(diǎn)到地面站路徑的平均長(zhǎng)度，希望盡可能縮短每顆月球中繼衛(wèi)星到地面站的路徑。當(dāng)根據(jù)加權(quán)可視矩陣V計(jì)算出多個(gè)月球中繼衛(wèi)星到地面站對(duì)應(yīng)的路徑都經(jīng)過某個(gè)衛(wèi)星節(jié)點(diǎn)，以致超出其度數(shù)約束時(shí)，為這些路徑所經(jīng)過的節(jié)點(diǎn)之間分配鏈路顯然是不合理的。如圖2（a），假設(shè)衛(wèi)星的度約束為4，圖2中月球中繼衛(wèi)星S1、S2、S3到地球中繼衛(wèi)星S4的帶箭頭虛線表示它們到地面站的最短路徑所需要經(jīng)過的一段可視鏈路，黃色連線表示已經(jīng)存在的鏈路，可見若按照每個(gè)月球中繼衛(wèi)星的最短路徑向經(jīng)過的節(jié)點(diǎn)之間分配鏈路，S4 將超出其度約束（稱在節(jié)點(diǎn)S4 發(fā)生沖突），3顆月球中繼衛(wèi)星中必然將至少有一顆不能夠與S4建立星間鏈路，該情況下各個(gè)月球中繼衛(wèi)星之間存在著對(duì)節(jié)點(diǎn)S4的競(jìng)爭(zhēng)

圖2 超出節(jié)點(diǎn)度約束情況示意圖Fig2 Schematic diagram of exceeding the degree constraint

為了解決上述問題，設(shè)計(jì)了一種基于競(jìng)爭(zhēng)決策思想[19]的鏈路分配算法LAA-CD。競(jìng)爭(zhēng)決策算法模擬了一種多個(gè)競(jìng)爭(zhēng)者競(jìng)爭(zhēng)一個(gè)或多個(gè)資源的過程，按照優(yōu)勝劣汰的決策原則使一部分競(jìng)爭(zhēng)者獲得資源而增加實(shí)力，另一部分競(jìng)爭(zhēng)者失去資源而減弱實(shí)力甚至死亡。決策算法由以下幾部分組成：①競(jìng)爭(zhēng)力函數(shù)：代表競(jìng)爭(zhēng)者對(duì)某種資源具有的競(jìng)爭(zhēng)力；②決策函數(shù)：根據(jù)競(jìng)爭(zhēng)力函數(shù)值的大小來決定把資源分配給哪一個(gè)競(jìng)爭(zhēng)者；③初始格局——在某一輪競(jìng)爭(zhēng)開始前各個(gè)競(jìng)爭(zhēng)者對(duì)資源的占有情況。算法通常設(shè)計(jì)多個(gè)競(jìng)爭(zhēng)力函數(shù)、決策函數(shù)和初始格局，共進(jìn)行round（round=競(jìng)爭(zhēng)力函數(shù)個(gè)數(shù)·決策函數(shù)個(gè)數(shù)·初始格局個(gè)數(shù)）輪競(jìng)爭(zhēng)，最后根據(jù)目標(biāo)函數(shù)選取較優(yōu)解。

在本文的LAA-CD算法中，共有m個(gè)競(jìng)爭(zhēng)者，即所有的月球中繼衛(wèi)星。初始格局下不為網(wǎng)絡(luò)分配額外的鏈路，且a(v,vstation)= 0,?v∈Vm，即在初始拓?fù)渚仃嘒下，所有競(jìng)爭(zhēng)者都無法與地面站連通。可以根據(jù)每一輪的競(jìng)爭(zhēng)力和決策函數(shù)，依次為每個(gè)競(jìng)爭(zhēng)者分配資源，即為當(dāng)前競(jìng)爭(zhēng)者向拓?fù)渚仃嘒中分配的其最短路徑所經(jīng)過的鏈路。當(dāng)然，在分配鏈路的過程中，需要保證每個(gè)衛(wèi)星節(jié)點(diǎn)的度數(shù)不超過N，因此本算法中引入了一種可視關(guān)系刪除的做法，在為每一個(gè)競(jìng)爭(zhēng)者分配資源前，都需要找出當(dāng)前d(v)=N的節(jié)點(diǎn)v和與v可視但是彼此之間未分配鏈路的節(jié)點(diǎn)u，并從當(dāng)前的加權(quán)可視矩陣V中刪除v和u之間的可視關(guān)系，如圖2（b）。令V(v,u)= ∞，那么在為下一個(gè)競(jìng)爭(zhēng)者分配資源時(shí)，將不可能另外分配一條與節(jié)點(diǎn)v相連的鏈路，避免了v超出度約束問題的發(fā)生。競(jìng)爭(zhēng)結(jié)束時(shí)，每個(gè)競(jìng)爭(zhēng)者都分配了一條到地面站的路徑，且滿足了約束條件C2，得到一種鏈路分配方案。

2.3.1 競(jìng)爭(zhēng)力函數(shù)

本算法采用如下4個(gè)競(jìng)爭(zhēng)力函數(shù)為

衛(wèi)星節(jié)點(diǎn)v到vstation的最短路徑的距離越小，競(jìng)爭(zhēng)力越大，則越應(yīng)該優(yōu)先分配這條最短路徑所經(jīng)過的鏈路。

根據(jù)Yen算法分別求出次短路徑與最短路徑的長(zhǎng)度，且二者差值越大，說明由于拒絕該競(jìng)爭(zhēng)者的最短路徑而增加的距離越大，因此可以考慮優(yōu)先分配該競(jìng)爭(zhēng)者的最短路徑所經(jīng)過的鏈路。

競(jìng)爭(zhēng)者v到vstation最短路徑與其他競(jìng)爭(zhēng)者到vstation最短路徑的公共節(jié)點(diǎn)數(shù)越少，那么在所經(jīng)過的中間節(jié)點(diǎn)發(fā)生沖突的概率則越小，其競(jìng)爭(zhēng)力可能更大。

競(jìng)爭(zhēng)者v到vstation最短路徑的跳數(shù)越少，發(fā)生節(jié)點(diǎn)沖突的概率越小，競(jìng)爭(zhēng)力越大。

2.3.2 決策函數(shù)

本算法采用如下兩個(gè)決策函數(shù)

1）根據(jù)初始的加權(quán)可視矩陣V計(jì)算出每個(gè)競(jìng)爭(zhēng)者的競(jìng)爭(zhēng)力，按照從大到小排序依次向拓?fù)渚仃嘒中分配每個(gè)競(jìng)爭(zhēng)者由加權(quán)可視矩陣V計(jì)算得到的最短路徑所經(jīng)過的鏈路；

2）每為一個(gè)競(jìng)爭(zhēng)者分配最短路徑后，根據(jù)更新的加權(quán)可視矩陣V重新計(jì)算剩余競(jìng)爭(zhēng)者的競(jìng)爭(zhēng)力，選擇當(dāng)前最具競(jìng)爭(zhēng)力的競(jìng)爭(zhēng)者分配資源，直到?jīng)]有競(jìng)爭(zhēng)者剩余。

2.3.3 算法流程

算法流程如圖3所示。

圖3 LAA-CD算法流程Fig.3 Algorithm flow of LAA-CD algorithm

2.4 基于模擬退火法的鏈路分配算法LAA-SA

文獻(xiàn)[20]～[21]研究了在不考慮衛(wèi)星終端約束下的衛(wèi)星網(wǎng)絡(luò)鏈路分配問題。模擬退火算法在得到一個(gè)新的解時(shí)，若新解的目標(biāo)函數(shù)值優(yōu)于舊解，接收新的解；反之，則以一定的概率來接受一個(gè)比當(dāng)前解要差的解，從而有可能跳出局部最優(yōu)解。接收較差解的概率為

其中：ΔD表示新舊解目標(biāo)函數(shù)的差值大?。粶囟葏?shù)T在每一次迭代后，乘以某個(gè)小于1的降溫系數(shù)逐漸減小。

當(dāng)?shù)螖?shù)達(dá)到上限或目標(biāo)函數(shù)不再改善時(shí)，停止迭代。算法流程如圖4 所示。在選擇初始拓?fù)鋾r(shí)，以任意順序依次為網(wǎng)絡(luò)中的衛(wèi)星隨機(jī)選擇可視節(jié)點(diǎn)并建立鏈路。當(dāng)某顆衛(wèi)星的可視節(jié)點(diǎn)（且有空閑終端）數(shù)大于其空閑終端數(shù)目時(shí)，與該衛(wèi)星所連接的節(jié)點(diǎn)數(shù)等于其空閑終端數(shù)目；當(dāng)可視節(jié)點(diǎn)數(shù)小于剩余終端數(shù)目時(shí)，則與其所有可視節(jié)點(diǎn)建立鏈路；當(dāng)某顆月球中繼衛(wèi)星與地面站可見時(shí)分配一條星地鏈路。然后通過分支交換的方式，如圖5產(chǎn)生一個(gè)新的拓?fù)?，并迭代若干次的退火過程。

圖4 LAA-SA算法流程圖Fig.4 Flowchart of LAA-SA algorithm

圖5 分支交換Fig.5 Branch and exchange

3 實(shí)驗(yàn)仿真與分析

本節(jié)中對(duì)比分析了LAA-CD、LAA-SA 和LAA-greedy算法在月球中繼衛(wèi)星到地面站路徑的平均距離D方面的性能。假設(shè)每顆衛(wèi)星允許攜帶的終端數(shù)目上限N為4。在LAA-SA 算法中，根據(jù)多組參數(shù)設(shè)置下的實(shí)驗(yàn)結(jié)果對(duì)比，發(fā)現(xiàn)當(dāng)設(shè)置退火前的初始溫度為1 000、降溫系數(shù)為0.99 且迭代次數(shù)為50 次時(shí)，能夠得到最小的D在仿真時(shí)間段內(nèi)的均值-D，因此選擇在此參數(shù)設(shè)置下與LAA-CD 和LAA-greedy 進(jìn)行對(duì)比。LAA-greedy 算法基于優(yōu)先為到地面站路徑距離較短的衛(wèi)星分配路徑的思想，依次為該最短路徑所經(jīng)過的節(jié)點(diǎn)之間分配鏈路

為了考察算法的有效性，同時(shí)保證中繼衛(wèi)星能夠?qū)υ虑虮砻婧偷厍虮砻娴娜采w，選擇了兩種目前提出較為可行的中繼衛(wèi)星星座，如表1所示。

表1 衛(wèi)星星座構(gòu)成Table 1 Satellite constellations

6顆月球極軌道衛(wèi)星的軌道參數(shù)[3]如表2中所示，4 顆圍繞以地月拉格朗日點(diǎn)衛(wèi)星圍繞以L1、L2、L4和L5 為中心的Halo 軌道運(yùn)行[22]，地球中繼衛(wèi)星星座包 含 3 顆 GEO 衛(wèi) 星 ， 分 別 位 于 110°E、 10°W 和130°W。設(shè)置地面站位于北京 （N38°39′6.48″，E104°04′35.11″）。假設(shè)在進(jìn)行分配鏈路前，位于同一軌道平面內(nèi)的3顆衛(wèi)星之間已經(jīng)存在固定的星間鏈路，4顆地月拉格朗日點(diǎn)衛(wèi)星之間連成一個(gè)環(huán)狀，且GEO1存在一條到地面站的固定的星地鏈路。

選擇未來2020年1月1日0點(diǎn)－2020年1月2日0點(diǎn)內(nèi)的網(wǎng)絡(luò)情況進(jìn)行仿真實(shí)驗(yàn)。在一個(gè)時(shí)隙內(nèi)，以15 min的時(shí)間間隔粒度對(duì)所有節(jié)點(diǎn)之間的距離進(jìn)行采樣（若該時(shí)隙時(shí)間長(zhǎng)度大于15 min），最終得到仿真時(shí)間內(nèi)各時(shí)隙起止時(shí)間點(diǎn)和采樣時(shí)間點(diǎn)下的距離數(shù)據(jù)并計(jì)算。

表2 月球極軌道衛(wèi)星軌道參數(shù)Table 2 Orbit parameters of polar orbit satellites

3.1 鏈路分配算法性能對(duì)比

1）基于月球極軌道星座的鏈路分配算法對(duì)比

在星座1 下，對(duì)比了3 種算法在月球中繼衛(wèi)星到地面站平均距離D方面的性能。仿真結(jié)果如圖6所示。對(duì)LAA-CD、LAA-SA 和LAA-greedy 算法得到的D計(jì)算仿真時(shí)間段內(nèi)的均值，得到的分別為 4.388 9× 105km、4.382 7× 105km 和 4.437 9×105km。

圖6 星座1下LAA-CD、LAA-S和LAA-greedy算法性能Fig.6 Algorithm performances of LAA-CD、LAA-SA and LAA-greedy in Constellation 1

根據(jù)仿真結(jié)果計(jì)算可知，LAA-CD和LAA-SA算法得到的α分別約為1.1%和1.2%，可見LAA-SA 和LAA-CD 均優(yōu)于 LAA-greedy，且 LAA-SA 算法略優(yōu)于LAA-CD。

2）基于地月拉格朗日點(diǎn)Halo軌道星座的鏈路分配算法對(duì)比

分析實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，在兩種星座下LAA-SA 和LAA-CD算法所的到的拓?fù)涞脑虑蛑欣^衛(wèi)星到地面站路徑平均距離總是小于LAA-greedy。同時(shí)，橫向?qū)Ρ缺疚奶岢龅膬煞N算法，發(fā)現(xiàn)LAA-CD算法在平均距離方面略大于LAA-SA算法，但是能夠極大降低算法的時(shí)間復(fù)雜度，在星座1 下的算法運(yùn)行時(shí)間約為L(zhǎng)AA-SA的1/6，星座1下約為L(zhǎng)AA-SA的1/13。這是因?yàn)長(zhǎng)AA-SA算法需要隨機(jī)選擇一對(duì)鏈路進(jìn)行分支交叉變換，并循環(huán)若干次后才能獲得較優(yōu)解，而LAACD 算法通過引入若干個(gè)競(jìng)爭(zhēng)力函數(shù)和決策函數(shù)，使得算法能夠更具有目的性、更高效地尋找到新的較優(yōu)解。

圖7 星座2下LAA-CD、LAA-SA和LAA-greedy算法性能Fig.7 Algorithm performances of LAA-CD、LAA-SA and LAA-greedy in Constellation 2

3.2 衛(wèi)星終端數(shù)目約束對(duì)算法性能的影響

上節(jié)的實(shí)驗(yàn)結(jié)果是基于所有衛(wèi)星所搭載的通信終端數(shù)目均相同時(shí)的條件下得到的。然而，當(dāng)每個(gè)衛(wèi)星上的通信終端數(shù)目不相同時(shí)，本文提出的LAA-SA和LAA-CD算法是否仍然具有較好的性能呢？因此，本小節(jié)將主要考慮不均等的星上通信終端分配對(duì)算法性能的影響，分別在2種星座構(gòu)成下對(duì)比了3種算法在月球中繼衛(wèi)星到地面站平均距離D方面的性能表現(xiàn)。

當(dāng)某顆衛(wèi)星上的某個(gè)或某幾個(gè)通信終端出現(xiàn)故障時(shí)，如果此時(shí)把該條星間鏈路所連接的另一端的衛(wèi)星上的通信終端關(guān)閉，這樣很有可能會(huì)對(duì)網(wǎng)絡(luò)的整體性能產(chǎn)生巨大影響，同時(shí)也是對(duì)星上通信終端資源的一種浪費(fèi)，因此需要考慮重新進(jìn)行鏈路分配。本小節(jié)側(cè)重于如何在通信終端數(shù)約束不同的情況下分配鏈路。在星座1 中，隨機(jī)選擇2 個(gè)僅有2 個(gè)通信終端正常工作的衛(wèi)星節(jié)點(diǎn)，和3個(gè)僅有3個(gè)通信終端正常工作的衛(wèi)星節(jié)點(diǎn)，即隨機(jī)產(chǎn)生2 個(gè)f(v)= 2，?v∈Vm∪Ve的衛(wèi)星節(jié)點(diǎn)和3 個(gè)f(v)= 3，?v∈Vm∪Ve的衛(wèi)星節(jié)點(diǎn)，剩下5個(gè)f(v)= 4，?v∈Vm∪Ve的衛(wèi)星節(jié)點(diǎn)。

根據(jù)仿真結(jié)果，在星座1下，三種算法得到的D的均值分別為 4.638 4× 105km、4.5514× 105km和4.9658× 105km，LAA-CD和LAA-SA算法的性能提升比率α分別約為6.6%和8.3%。類似的，在星座2下，分別為 5.258 7 × 105km、5.1331× 105km 和5.412 4 × 105km，LAA-CD 和LAA-SA 算法的性能提升比率α分別約為2.8%和5.2%。由此可見，在星載通信終端數(shù)目不等的情況下，本文提出的兩種LAASA和LAA-CD算法仍然均優(yōu)于LAA-greedy。

3.3 星座架構(gòu)對(duì)比分析

兩種星座的性能對(duì)比如表3。基于本文實(shí)驗(yàn)結(jié)果，可以得出以下結(jié)論：基于月球極軌道衛(wèi)星的星座相比地月拉格朗日點(diǎn)Halo 軌道衛(wèi)星星座，具有更短的平均月球中繼衛(wèi)星到地面站距離。

表3 兩種星座下的性能對(duì)比Table 3 Performance comparison between two constellations

4 結(jié) 論

本文針對(duì)由多顆月球中繼衛(wèi)星、地球中繼衛(wèi)星和地面站組成的地月空間信息網(wǎng)絡(luò)中，衛(wèi)星可視節(jié)點(diǎn)數(shù)目多于所攜帶的通信終端數(shù)目時(shí)的拓?fù)湓O(shè)計(jì)問題，提出了基于競(jìng)爭(zhēng)決策思想的鏈路分配算法LAA-CD和基于模擬退火法的鏈路分配算法LAA-SA，并與貪婪算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果證明，LAA-CD與LAA-SA均比貪婪算法具有更小的平均月球中繼衛(wèi)星到地面站距離。同時(shí)，LAA-CD算法相比LAA-SA具有較低的時(shí)間復(fù)雜度，而LAA-SA算法能夠得到更小的平均距離。通過實(shí)驗(yàn)對(duì)比兩種星座架構(gòu)，可以發(fā)現(xiàn)，若從降低地月通信時(shí)延的角度出發(fā)，構(gòu)建一個(gè)基于月球極軌道衛(wèi)星星座的地月空間信息網(wǎng)絡(luò)拓?fù)涓鼮楹线m，可為地月空間信息網(wǎng)絡(luò)分配提供技術(shù)支持。