星座網(wǎng)絡(luò)的網(wǎng)關(guān)衛(wèi)星選擇問題

吳 俊 陸 延 李 斌

(揚(yáng)州大學(xué)信息工程學(xué)院, 揚(yáng)州 225000)

近年來,隨著星間鏈路(ISL)技術(shù)的成熟[1]以及星上處理能力的增強(qiáng),衛(wèi)星系統(tǒng)的服務(wù)不再是簡單的彎管模式,星座網(wǎng)絡(luò)成為衛(wèi)星系統(tǒng)發(fā)展的重要趨勢[2-4]． 文獻(xiàn)[5-6]研究了基于IP的衛(wèi)星組網(wǎng)技術(shù);文獻(xiàn)[7-10]探討了衛(wèi)星網(wǎng)絡(luò)的路由問題．然而,隨著太空中衛(wèi)星的日益增多,衛(wèi)星系統(tǒng)的運(yùn)行管理成為一項(xiàng)極具挑戰(zhàn)的任務(wù)．地面站不僅投資巨大,運(yùn)營費(fèi)用也極其高昂．因此,如何對星座網(wǎng)絡(luò)進(jìn)行優(yōu)化、減少日益龐大的星座網(wǎng)絡(luò)對地面信關(guān)站的需求成為了一項(xiàng)重要的課題．

在二代衛(wèi)星系統(tǒng)中,利用星座網(wǎng)絡(luò)的星間鏈路可以有效減少星座系統(tǒng)對地面站資源的需求．在星間鏈路及組網(wǎng)技術(shù)的支持下,星座系統(tǒng)只需選取部分地面可觀測的衛(wèi)星建立星-地鏈接．這種與地面站有直接鏈路的衛(wèi)星被稱作網(wǎng)關(guān)衛(wèi)星,而其他衛(wèi)星的信息傳輸可以通過網(wǎng)關(guān)衛(wèi)星進(jìn)行中繼,這樣不僅可以突破衛(wèi)星服務(wù)必須地面可見的限制,還可以節(jié)省大量的地面站資源．

網(wǎng)關(guān)衛(wèi)星選擇問題是指如何在地面可見衛(wèi)星集合中選取一個子集作為網(wǎng)關(guān)衛(wèi)星．本文采用一種受限的支配集模型對網(wǎng)關(guān)衛(wèi)星的選擇進(jìn)行建模．首先,討論了網(wǎng)關(guān)選擇問題的復(fù)雜性,證明了網(wǎng)關(guān)選擇問題即使在每顆衛(wèi)星僅擁有3條鏈路時仍是NP完全的．然后,設(shè)計(jì)并分析了網(wǎng)關(guān)衛(wèi)星選擇問題的貪心算法．最后,通過仿真實(shí)驗(yàn)對貪心算法的平均性能進(jìn)行了評估．

1 問題定義

借助星間鏈路進(jìn)行衛(wèi)星組網(wǎng),不僅可以突破星地通信的可見性限制,而且可以減少衛(wèi)星網(wǎng)絡(luò)與地面信關(guān)站的連接數(shù)量．然而,在網(wǎng)關(guān)衛(wèi)星選取時,減少連接數(shù)量并不是唯一的考慮因素．盡量減少非網(wǎng)關(guān)衛(wèi)星與地面通信時的轉(zhuǎn)發(fā)跳數(shù)也是網(wǎng)關(guān)衛(wèi)星選擇時考慮的一個重要因素．顯然,減少地面站資源與減少轉(zhuǎn)發(fā)跳數(shù)是矛盾的．一個合理的折中是,任意星座中的衛(wèi)星與地面通信時,網(wǎng)關(guān)選擇后的轉(zhuǎn)發(fā)跳數(shù)至多增加1跳．這要求所有地面可見衛(wèi)星及與地面可見衛(wèi)星有鏈路相連的非地面可見衛(wèi)星均至少有1條鏈路連接到網(wǎng)關(guān)衛(wèi)星．

定義1(網(wǎng)關(guān)衛(wèi)星選擇問題) 給定圖G=(V,E),其中V=U∪W,?v∈W:?u∈U使得(u,v)∈E,且任意頂點(diǎn)的度小于等于常數(shù)k．尋找最小子集D?U滿足?v∈V:v∈D或者?u∈D,(u,v)∈E．

在定義1中,頂點(diǎn)集合U表示所有地面可見的衛(wèi)星,集合W表示所有與可見衛(wèi)星直接相連的不可見衛(wèi)星．由于受到衛(wèi)星上收發(fā)器數(shù)量的限制,目前1顆衛(wèi)星支持4條左右的星間鏈路,定義1中頂點(diǎn)度的約束k體現(xiàn)了這一限制．

2 NP完全性

網(wǎng)關(guān)衛(wèi)星選擇問題是一種受限的支配集問題,這種限制體現(xiàn)在以下2個方面:① 頂點(diǎn)度數(shù)的限制;② 支配集選擇范圍的限制,即支配集只能在集合U中選?。?/p>

網(wǎng)關(guān)衛(wèi)星選擇問題的一個特例是:當(dāng)集合W為空集時,該問題就是頂點(diǎn)度數(shù)受限的最小支配集問題．支配集問題的NP完全性并不能表明網(wǎng)關(guān)衛(wèi)星選擇問題的難解性．這主要因?yàn)?支配集問題的NP完全性是通過將最小集合覆蓋問題歸約到支配集問題而得到的．但這一方法無法保證頂點(diǎn)的度滿足k的限制．為了討論網(wǎng)關(guān)衛(wèi)星選擇問題的復(fù)雜度,將3-SAT問題多項(xiàng)式時間規(guī)約到該問題,以證明其NP完全性．對網(wǎng)關(guān)衛(wèi)星選擇問題的決策問題版本進(jìn)行定義．

定理1若k≥3,即使G|U(即頂點(diǎn)集合U在圖G上的導(dǎo)出子圖)是平面圖,網(wǎng)關(guān)衛(wèi)星選擇問題仍然是NP完全的．

然后,將3-SAT問題多項(xiàng)式規(guī)約到該問題．令一個3-SAT問題的實(shí)例為合取范式公式φ,其中包含m個變量和l個子句C1,C2，…,Cl,即變量集X={x1,x2,…,xm},每個子句里含有3個不相同的文字．設(shè)變量xi(1≤i≤m)在φ中總共出現(xiàn)ni次．通過φ構(gòu)造圖G的步驟如下:

圖1 xi出現(xiàn)3次時構(gòu)成的子圖Gi

圖2 基于φ構(gòu)造的G

圖3 Gi中支配點(diǎn)選取的2種情況

3 貪心算法

由于網(wǎng)關(guān)衛(wèi)星選擇問題是NP完全的,隨著衛(wèi)星網(wǎng)絡(luò)中衛(wèi)星數(shù)量的增加,尋找最優(yōu)解不太現(xiàn)實(shí)．另一方面,處于地面信關(guān)站觀察窗口中的衛(wèi)星集合變化也是頻繁的,這就要求網(wǎng)關(guān)衛(wèi)星選擇的決策需要實(shí)時計(jì)算．收斂慢的啟發(fā)算法不能滿足這一需求,因此本文重點(diǎn)研究了貪心算法．

傳統(tǒng)支配集的貪心算法是在圖G中選擇度數(shù)最大的頂點(diǎn)加入到解集合中,并在圖G中刪除該節(jié)點(diǎn)及其鄰居,重復(fù)這一過程,直到圖為空．然而,這一算法并不能直接用于網(wǎng)關(guān)衛(wèi)星選擇問題,其主要原因在于:① 在網(wǎng)關(guān)衛(wèi)星選擇問題中,圖G的頂點(diǎn)分為2個部分(集合U和集合W),網(wǎng)關(guān)節(jié)點(diǎn)不能選于集合W中,因?yàn)榧蟇中的衛(wèi)星是地面信關(guān)站不可見的．傳統(tǒng)的貪心算法依據(jù)度數(shù)最大的節(jié)點(diǎn)來選擇支配節(jié)點(diǎn),而此時度數(shù)最大的節(jié)點(diǎn)可能存在于集合W中．這一問題可以通過將支配集頂點(diǎn)的選取集合限制在集合U中來加以解決.② 傳統(tǒng)的貪心算法可能導(dǎo)致某些不可見的衛(wèi)星不能被支配(見圖4)．圖4中黑色節(jié)點(diǎn)為集合U中度數(shù)最大的節(jié)點(diǎn),將其加入支配集,刪去鄰居(灰色節(jié)點(diǎn))后,白色節(jié)點(diǎn)處于集合W中,但已沒有集合U中的節(jié)點(diǎn)與之鄰接,且白色節(jié)點(diǎn)并未被黑色節(jié)點(diǎn)支配．因此,必須對傳統(tǒng)算法進(jìn)行改進(jìn),思路是在貪心選擇時總是選擇支配集合W中頂點(diǎn)最多的支配點(diǎn)．

圖4 貪心算法失敗的例子

貪心算法的詳細(xì)步驟如下:

① 輸入圖G=(V,E),其中V=U∪W;置A=?．

④ 輸出A．

定義2給定圖G=(V,E),其中V=U∪W,A?U．定義D(A)={u∈V|u∈A∨?v∈A:(u,v)∈E}．

為了分析網(wǎng)關(guān)衛(wèi)星選擇問題貪心算法,將貪心算法轉(zhuǎn)化為最小次模覆蓋問題來進(jìn)行分析．

定義3(次模函數(shù)) 給定一個有限集合E,定義2E上的一個函數(shù)f:2E→Z．若f滿足?A,B?E，f(A)+f(B)≥f(A∪B)+f(A∩B),則稱f為次模函數(shù)．

定義了網(wǎng)關(guān)衛(wèi)星選擇問題中一個單調(diào)增的次模函數(shù),從而將該問題轉(zhuǎn)化為最小次模覆蓋問題．根據(jù)次模覆蓋定理,得到定理2．

定理2網(wǎng)關(guān)衛(wèi)星選擇問題的貪心算法解中的節(jié)點(diǎn)數(shù)不超過最優(yōu)解的H(k+1)倍,其中H為調(diào)和函數(shù)．

4 仿真實(shí)驗(yàn)

由于網(wǎng)關(guān)衛(wèi)星選擇問題具有NP完全性,最優(yōu)解不易計(jì)算,因此,將網(wǎng)關(guān)衛(wèi)星的選擇問題建模成線性規(guī)劃模型,以線性規(guī)劃松弛解作為參照．將圖G的鄰接矩陣修改后作為線性規(guī)劃的系數(shù)矩陣,將全1列向量作為右端向量,目標(biāo)函數(shù)是滿足所有衛(wèi)星都被支配(或自身為網(wǎng)關(guān)衛(wèi)星)時網(wǎng)關(guān)衛(wèi)星的個數(shù)最少．最后,由貪心算法仿真和線性規(guī)劃模型分別得出仿真結(jié)果．

本文通過隨機(jī)產(chǎn)生矩陣(產(chǎn)生過程要控制好各節(jié)點(diǎn)對度的限制)的方式來仿真衛(wèi)星網(wǎng)絡(luò),并對生成的矩陣分別采用貪心算法和線性規(guī)劃方法進(jìn)行計(jì)算．為了全面比較算法在平均情況下的性能,采用控制變量的方法對算法進(jìn)行分析,即控制可見衛(wèi)星占所有衛(wèi)星的百分?jǐn)?shù)P．

圖5給出了貪心算法和線性規(guī)劃方法的性能比較．由圖可知,衛(wèi)星總數(shù)較少時貪心算法得到的結(jié)果與最優(yōu)解的差距不大,但在衛(wèi)星總數(shù)相對稍多時,該結(jié)果與線性規(guī)劃松弛解的差距約為1.8倍,這與貪心算法在最壞情況下的性能界H(4)(k=3時)相差不大,表明在某些場合最壞情況下的性能界具有代表性．從圖中還可以看出,采用貪心算法進(jìn)行網(wǎng)關(guān)衛(wèi)星選擇大約能節(jié)省20%左右的星-地鏈路．

圖5 仿真結(jié)果

5 結(jié)語

近年來,星座網(wǎng)絡(luò)組網(wǎng)技術(shù)成為第二代衛(wèi)星網(wǎng)絡(luò)的關(guān)鍵技術(shù)．作為動態(tài)星座組網(wǎng)的一個方面,適當(dāng)?shù)剡x擇網(wǎng)關(guān)衛(wèi)星可以有效降低星座網(wǎng)絡(luò)對地面站資源的需求．本文采用受限的支配集模型為網(wǎng)關(guān)衛(wèi)星選擇問題建模,并證明了該受限支配集問題是NP完全的．分析了傳統(tǒng)支配集的貪心算法不適用于該問題的原因,進(jìn)一步提出適用于該問題的改進(jìn)貪心算法,并將該問題轉(zhuǎn)化為最小次模覆蓋問題,以分析貪心算法．模擬仿真實(shí)驗(yàn)結(jié)果顯示,貪心算法能夠節(jié)約20%左右的地面站資源．然而,貪心算法得到的結(jié)果與最優(yōu)解之間仍然存在著較大差距,如何尋找更優(yōu)的近似算法是下一步研究工作的重點(diǎn)．

)

[1] 王振永, 王平,顧學(xué)邁,等.衛(wèi)星網(wǎng)絡(luò)中永久星間鏈路的設(shè)計(jì)方法研究[J].通信學(xué)報,2006,27(8): 129-133.

Wang Zhenyong, Wang Ping, Gu Xuemai, et al. Research on design of permanent inter-satellite-links in satellite networks [J].JournalofCommunication, 2006,27(8):129-133.(in Chinese)

[2] Shahriar A M, Atiquzzaman M, Ivancic W. Network mobility in satellite networks: architecture and the protocol[J].InternationalJournalofCommunicationSystems, 2013,26(2): 177-197.

[3] Liu Z G, Xu K, Pan C S. Optimized resource in satellite network based on genetic algorithm[J].InternationalJournalofInnovativeComputingInformationandControl, 2012,8(12): 8249-8256.

[4] Alagoz F, Korcak O, Jamalipour A. Exploring the routing strategies in next-generation satellite networks [J].WirelessCommunications, 2007,14(3):79-88.

[5] Aftab F, Younas S, Aftab K. Communication issues in satellite links: a comprehensive survey[C]//Proceedingsof4thInternationalConferenceonWirelessCommunications,NetworkingandMobileComputing(WiCOM'08). Dalian, China, 2008: 1-6.

[6] Pacheco D M L, Thai T T. An IP-ERN architecture to enable hybrid E2E/ERN protocol and application to satellite networking[J].ComputerNetworks, 2012,56(11):2700-2713.

[7] Zhang Zhu, Guo Qing. An IP mobility management scheme with dual location areas for IP/LEO satellite network[J].JournalofZhejiangUniversity-ScienceC:Computers&Electronics, 2012,13(5):355-364.

[8] Gamvros I, Raghavan S. Multi-period traffic routing in satellite networks[J].EuropeanJournalofOperationalResearch, 2012,219(3):738-750.

[9] Yang D N, Liao W J. On multicast routing using rectilinear steiner trees for LEO satellite networks [J].IEEETransactionsonVehicularTechnology, 2008,57(4): 288-300.

[10] 吳國強(qiáng),孫兆偉, 趙丹,等. 編隊(duì)小衛(wèi)星星間通信系統(tǒng)的發(fā)展和趨勢[J].哈爾濱工業(yè)大學(xué)學(xué)報, 2007, 39(11):1699-1703.

Wu Guoqiang, Sun Zhaowei, Zhao Dan, et al. Development and trend research of inter-satellite communication system on formation small satellites[J].JournalofHarbinInstituteofTechnology, 2007,39(11):1699-1703.(in Chinese)

[11] 堵丁柱,葛可一,胡曉東.近似算法的設(shè)計(jì)與分析 [M].北京:高等教育出版社,2011:52.