星座网络的网关卫星选择问题

吴 俊 陆 延 李 斌

(扬州大学信息工程学院, 扬州 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.