Groebner基方法在LEO卫星网络路由优化中的应用

卫星网络中的服务质量(QoS,Quality of Service)多目标约束路由问题已被证明是一个非确定性多项式完全(NPC,Non-deterministic Polynomial Complete)问题.根据低轨(LEO,Low Earth Orbit)卫星网络拓扑变化有规律、可预知的特点,将Groebner基方法引入满足QoS多目标约束的路由算法中,应用算法前将QoS多目标约束问题转化为单目标约束问题,使它能够被多项式的最短路径优先(SPF,Shortest Path First)路由算法求解,从而通过Groebner基方法解决QoS多目标约束路由问题,保证了QoS参数的有效性.最后,将所提出的算法与启发式算法和最短路径优先算法进行了仿真比较.仿真实验结果表明,Groebner基方法有效降低了星上计算的难度,比传统方法能提供更好的QoS保证.

Applying of Groebner bases method in LEO satellite networks routing optimization

The multi-objective quality of service(QoS) routing problem in low earth orbit (LEO) satellite networks was convinced as a non-deterministic polynomial complete (NPC) problem. Based on the regular and predictable features of topology changes in low earth orbit (LEO) satellite networks, the Groebner based method was utilized to solve the multi-objective routing problem. The algorithm is able to transform the multi-objective problem into the single-objective problem, and the corresponding single-objective problem can be resolved by shortest path first (SPF) algorithm. Thus the Groebner based method was herein used to solve the multi-objective QoS routing problem, in which the effectiveness of QoS parameters was guaranteed. The performance comparison of the algorithm with Heuristic algorithm and SPF algorithm was evaluated by simulation. The results show that the Groebner based method greatly decreases the difficulty of the calculation and provide more QoS guarantees than traditional algorithms.