北京航空航天大学学报 ›› 2013, Vol. 39 ›› Issue (7): 957-962.

• 论文 • 上一篇    下一篇

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

高智杰, 孙富春, 杨治安, 杨东方   

  1. 清华大学 计算机科学与技术系, 北京 100084
  • 收稿日期:2012-07-28 出版日期:2013-07-30 发布日期:2013-07-23
  • 基金资助:
    国家863计划基金资助项目(2008AA1102)

Applying of Groebner bases method in LEO satellite networks routing optimization

Gao Zhijie, Sun Fuchun, Yang Zhian, Yang Dongfang   

  1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Received:2012-07-28 Online:2013-07-30 Published:2013-07-23

摘要: 卫星网络中的服务质量(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保证.

Abstract: 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.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发