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

Gateway satellite selection problem in constellation networks

作　　者：吴俊[1] 陆延[1] 李斌[1] 

机构地区：[1]扬州大学信息工程学院,扬州225000

出　　处：《东南大学学报（自然科学版）》2013年第6期1152-1156,共5页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(61070210;61070133);江苏省网络与信息安全重点实验室开放课题基金资助项目(BM2003201-201001)

摘　　要：为了既能获得较好的星座网络星-地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题.将网关选择问题建模成一种受限的支配集模型,对该问题的复杂性和贪心选择算法进行了研究.通过将3-SAT问题多项式时间规约到网关卫星选择问题,从而证明了网关卫星选择问题是NP完全的.同时,设计了网关卫星选择问题的贪心算法,理论分析表明,若每颗卫星最多支持k条星间链路,则贪心选择算法是H(k+1)近似的,其中H表示调和函数.仿真实验结果表明,贪心算法在星座规模中等时性能接近最优解,在星座规模相对较大时性能接近H(k+1)的近似界.在平均规模情况下,采用贪心算法进行网关卫星选择能节省20%左右的星-地链路资源.In constellation networks,to consume less ground station resources and get lower latency of communications between satellites and ground stations,a gateway satellite selecting problem is proposed.The complexity and the greedy algorithm of this problem is thoroughly investigated by modeling the gateway satellite selecting problem as a constrained dominating set problem.The NP （nondeterministic polynomial time）-completeness of the gateway satellite selecting problem is proved by a polynomial time reduction from 3-SAT（satisfiability）problem.To deal with the difficulty of the problem,a greedy algorithm is designed.The theoretical analysis results show that when the maximum number of inter-satellite links supported by a satellite is less than k,the greedy algorithm is H（k ＋1）-approximation,where H is the harmonic function.The simulation results show that the greedy algorithm is nearly optimal when the scale of a constellation network is medium.However, the number of gateway satellites found by the greedy algorithm is about H（k ＋1）times that of opti-mal solution when the scale of a constellation network is huge.In an average scale of the constella-tion network,about 20% ground station resources can be saved when gateway satellites are chosen by the greedy algorithm.

关 键 词：网关卫星 NP完全性 贪婪算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]