Applying of Groebner bases method in LEO satellite networks routing optimization
-
摘要: 卫星网络中的服务质量(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.
-
Key words:
- satellite networks /
- QoS (quality of service) /
- multi-objective routing /
- Groebner bases
-
[1] Xu Hui,Huang Fei,Wu Shiqi.A distributed QoS routing based on ant algorithm for LEO satellite network[J].Chinese Journal of Computers,2007,30(3):361-367 [2] Yang Denian,Liao Wanjiun.On multicast routing using rectilinear steiner trees for LEO satellite networks[J].IEEE Transactions on Vehicular Technology,2008,57(4):2560-2569 [3] Hueseyin U,Akyildiz I F,Bender M D.A routing algorithm for connection-oriented low earth orbit(LEO) satellite networks with dynamic connectivity[J].ACM Journal of Wireless Networks(WINET),2000,6(3):181-190 [4] Uzunalio H,Bender M,Akyildiz I.Routing algorithm for low earth orbit (LEO) satellite networks with dynamic connectivity[J].ACM-Baltzer Journal of Wireless Networks,2000,6(3):181-190 [5] Alagoz F.Exploring the routing strategies in next-generation satellite networks[J].IEEE Transactions on Wireless Communications,2007,14(3):79-88 [6] Long Fei,Sun Fuchun,Wu Fengge.A QoS routing based on heuristic algorithm for double-layered satellite networks //IEEE Congress on Evolutionary Computation(CEC 2008).Berlin:Springer,2008:1866-1872 [7] Xiao W,Soong B H,Law C L,et al.Evaluation of heuristic path selection algorithms for multi-constrained QoS routing //2004 IEEE International Conference on Networking,Sensing and Control.Belgium:Springer,2004:112-116 [8] Sun Yao,Wang Dingkang.Branch grobner bases algorithm over Boolean ring[J].Journal of Systems Science and Mathematical Sciences,2009(09):35-43 [9] Song Xuegui,Liu Kai,Zhang Jun,et al.Dynamic source routing algorithm for LEO satellite networks[J].Journal of Beijing University of Aeronautics and Astronautics,2006,32(12):1422-1426 [10] 王东明,夏壁灿,李自明.计算机代数[M].北京:清华大学出版社,2007:161-186 Wang Dongming,Xia Bican,Li Ziming.Computer algebra[M].Beijing:Tsinghua Publishing Company,2007:161-186(in Chinese) [11] Chan T H.A localized routing scheme for LEO satellite networks //ICSSC 2003.Yokohama:AIAA,2003:2357-2364 [12] Papapetrou E.Distributed on-demand routing for LEO satellite systems[J].Computer Networks,2007,51(15):4356-4376 -
点击查看大图
计量
- 文章访问数: 1669
- HTML全文浏览量: 289
- PDF下载量: 461
- 被引次数: 0
下载:
