基于虚拟拓扑的单层卫星网CEMR 路由算法

摘要：CEMR（Compact Explicit Multi-path Routing）路由算法即紧凑显式多路径路由算法，与MPLS比较，CEMR采用PathID编码方案，具有较小的信令开销，并能保证分组转发不形成环路。分析表明，该算法支持卫星网络中的流量负载平衡，在延时和丢包性能上具有优势，适合于高流量负载卫星网络。

关键词：虚拟拓扑；单层卫星网；CEMR

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）02-0365-02

基于虚拟拓扑的单层卫星网路由算法就是根据卫星网运行周期性特点，将卫星网系统周期划分为一系列的时间片段，在每个时间片段内，卫星网拓扑是固定不变的，卫星网拓扑的变化只发生在时间片切换点上，这样就可以采用最短路径算法找到最优路径和备选路径。

基于虚拟拓扑的单层卫星网路由算法有很多种，比较成熟的有DT-DVTR算法、FSA算法、CEMR算法、ELB路由算法等，在端到端延时和分组丢失率方面，CEMR算法具有明显的性能优势。

1 CEMR路由算法简介

CEMR路由算法是研究移动卫星网络中多路径路由问题的一种算法。它以单层类铱星（Iridium-like）极轨卫星星座为场景，该星座由6个倾角接近90°的轨道平面组成，每个轨道平面均匀分布有11颗卫星。同一轨道平面内的星间双向链路称为轨内星间链路（Inter-plane ISL），轨内星间链路可以一直保持着，其传播延时总是固定的。轨间星间链路的长度随着卫星的运动是变化的，所以随着卫星的运动，轨间星间链路的传播延时始终在变化。

CEMR算法通过动态虚拟拓扑研究拓扑动态性问题，卫星网络建模在一个系统周期T上，时间离散的卫星位置的快照。系统周期T可以分成n个时间间隔Δt [t0，t1]，[t1，t2]，…，[tn-1，tn]。在一个时间间隔Δt内，拓扑可以进一步用图G描述。链路状态改变仅发生在离散时间点t0，t1，t2，…，tn。时间间隔Δt足够小，以考虑每条星间链路的代价在整个时间间隔内是恒定的。

2 CEMR路由算法原理

CEMR路由算法分成3个部分：路由发现、路由维护以及流量分配。

与传统路由算法仅将传播延时作为路由代价度量不同，CEMR路由算法采用星间链路长度和流量负载两个因素影响的延时作为代价度量，而这两个对路由性能有重要影响的参数是动态改变的。第一个参数是传播延时Tp。第二个参数是排队延时Tq。假设在时刻t一个分组进入一个给定的链路队列，其期望队列延时Texp能够通过下面的公式计算得到：

4 CEMR路由算法总结

CEMR路由算法使用PathID全局路径标识实现卫星网络的多路径路由，流量分配到多个可行路径，降低了卫星网络延时，提高了吞吐量，实现了负载均衡功能。PathID验证算法确保了分组转发一致性，分析结果表明，CEMR路由算法提出的时间早，技术成熟，性能比较完善，在延时和丢包率方面相对于其他传统算法具有更好的性能。

参考文献：

[1] 王汝传，饶元，郑彦，等.卫星通信网路由技术及其模拟[M].北京：人民邮电出版社，2010（4）：61-65.

[2] 陈建州，王路，刘立祥，等.双层星座中负载均衡路由协议研究[J].宇航学报，2012（6）：746-753.

[3] 朱军，饶元，李绍稳，等.面向LEO卫星网的轻量级按需QoS源路由算法[J].计算机科学，2012（7）：64-68.

[4] 杨力，杨校春，潘成胜.一种GEO/LEO双层卫星网络路由算法及仿真研究[J].宇航学报，2012（10）：1445-1452.

[5] 朱军，饶元，傅雷扬，等.基于移动代理的卫星网路由性能研究[J].计算机工程与应用，2012（3）：69-72.