星座網絡的網關衛星選擇問題

吳 俊 陸 延 李 斌

(揚州大學信息工程學院, 揚州 225000)

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

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

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

1 問題定義

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

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

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

2 NP完全性

網關衛星選擇問題是一種受限的支配集問題,這種限制體現在以下2個方面:① 頂點度數的限制;② 支配集選擇范圍的限制,即支配集只能在集合U中選取．

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

定理1若k≥3,即使G|U(即頂點集合U在圖G上的導出子圖)是平面圖,網關衛星選擇問題仍然是NP完全的．

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

圖1 xi出現3次時構成的子圖Gi

圖2 基于φ構造的G

圖3 Gi中支配點選取的2種情況

3 貪心算法

由于網關衛星選擇問題是NP完全的,隨著衛星網絡中衛星數量的增加,尋找最優解不太現實．另一方面,處于地面信關站觀察窗口中的衛星集合變化也是頻繁的,這就要求網關衛星選擇的決策需要實時計算．收斂慢的啟發算法不能滿足這一需求,因此本文重點研究了貪心算法．

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

圖4 貪心算法失敗的例子

貪心算法的詳細步驟如下:

① 輸入圖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}．

為了分析網關衛星選擇問題貪心算法,將貪心算法轉化為最小次模覆蓋問題來進行分析．

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

定義了網關衛星選擇問題中一個單調增的次模函數,從而將該問題轉化為最小次模覆蓋問題．根據次模覆蓋定理,得到定理2．

定理2網關衛星選擇問題的貪心算法解中的節點數不超過最優解的H(k+1)倍,其中H為調和函數．

4 仿真實驗

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

本文通過隨機產生矩陣(產生過程要控制好各節點對度的限制)的方式來仿真衛星網絡,并對生成的矩陣分別采用貪心算法和線性規劃方法進行計算．為了全面比較算法在平均情況下的性能,采用控制變量的方法對算法進行分析,即控制可見衛星占所有衛星的百分數P．

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

圖5 仿真結果

5 結語

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

)

[1] 王振永, 王平,顧學邁,等.衛星網絡中永久星間鏈路的設計方法研究[J].通信學報,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] 吳國強,孫兆偉, 趙丹,等. 編隊小衛星星間通信系統的發展和趨勢[J].哈爾濱工業大學學報, 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] 堵丁柱,葛可一,胡曉東.近似算法的設計與分析 [M].北京:高等教育出版社,2011:52.