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

摘要：

为了既能获得较好的星座网络星地通信延迟性能又能较少地占用地面站资源，提出了网关卫星选择问题。将网关选择问题建模成一种受限的支配集模型，对该问题的复杂性和贪心选择算法进行了研究。通过将3-SAT 问题多项式时间规约到网关卫星选择问题，从而证明了网关卫星选择问题是 NP 完全的。同时，设计了网关卫星选择问题的贪心算法，理论分析表明，若每颗卫星最多支持 k 条星间链路，则贪心选择算法是 H（k ＋1）近似的，其中 H 表示调和函数。仿真实验结果表明，贪心算法在星座规模中等时性能接近最优解，在星座规模相对较大时性能接近 H（k ＋1）的近似界。在平均规模情况下，采用贪心算法进行网关卫星选择能节省20％左右的星地链路资源。

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

分类号：TP393(计算技术、计算机技术)

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

在线出版日期：2013-12-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1152-1156