基于NS—2的DRA卫星网络路由算法研究与仿真

郑碧俊　余谅　田星

【摘要】 适用于地面固定网络的现有路由技术无法再适用于网络拓扑周期性变化的低轨卫星网络。路由技术是低轨卫星网络的关键技术之一。本文简单介绍了LEO卫星网络路由算法的设计难点，分析了DRA算法原理，并对DRA路由算法进行了仿真。

【关键词】 卫星网络 DRA

一、引言

现有的地面网络覆盖范围非常有限，目前仅能覆盖人口与通信任务比较密集的地区，其总面积仅占地球表面积的2%左右，另外98%的陆地和海洋都没有被覆盖。截至2013年，我国农村互联网普及率仅为27.5%，远低于城镇62%的互联网普及率，农村非网民人口仍有4.5亿，农村网民商务交易类应用率也远低于城镇网民[1][2]。鉴于我国特有的三级阶梯地貌和农村地广人稀的特点，依靠现有的地面通信技术实现组网在经济成本上十分不现实，但借助卫星通信则可以做到大范围的无缝网络覆盖。

本文簡单概述了LEO卫星网络路由算法的设计难点，分析了DRA[3]卫星网络路由算法原理，并通过NS-2对DRA算法进行了模拟。

二、DRA路由算法简介

2.1 LEO卫星网络路由设计的难点

卫星网络路由问题的难点主要体现在以下三个方面：

（1）卫星节点不断运动，网络拓扑发生周期性变化。

（2）星间链路可持续通信时间受限，低轨道卫星绕地公转周期短，不超过两个小时，在跨越极地地区时会断开相邻轨道间链路，反向缝链路因相邻轨道间卫星做反方向运动存在时间更短。

（3）星上设备的处理能力和存储容量有限，卫星一旦发射就很难进行硬件升级， 这就决定了路由算法的实现必须尽量简单，且具备良好的自适应性和抗毁性。

2.2 DRA路由算法原理

DRA（Datagram Routing Algorithm）算法是无连接的、分布式的。DRA路由算法定义左右相邻卫星处于同一维度，称为卫星网初始对准。同一纬度的卫星形成横向环，接近极地地区的横向环路径长度更短。DRA链路中分为横向跳跃和纵向跳跃，横向跳跃的代价在靠近极地地区时减小，纵向跳跃的代价保持不变。

DRA路由算法忽略星上处理时间，则端到端的延时将只涉及卫星之间的传播延时，即在空间上长度更短的路径具有更小延时，DRA多跳路径总传播延时是路径中的每一跳传播延时的总和。

最小传播延时路径是通过极地地区的最小传播延时路径和未通过极地地区的最小传播延时路径中延时更小的路径，即为空间距离最短的路径。在DRA路由算法中，当源卫星处在比目的卫星更高的维度时，假定源卫星离极地地区还有A跳，源卫星处于从极地数起的第k个横向环上，则当源卫星与目的卫星水平跳数nh满足式1时，最优路径为穿过极地地区的最优路径；当nh满足式2时，最优路径为不穿过极地地区的最优路径。

latmin表示最靠近极地地区的横向环维度，lat为源卫星所在横向环维度，其所在维度横向跳跃距离为a*cos（lat）。M为单轨道内卫星数目，N为轨道数目。

根据这两个定理，可以帮助决定下一跳，并且算法的时间复杂度为O（1），远低于Bellman-Ford最短路径算法。DRA路由算法分为方向预测阶段和方向增强阶段。在方向预测阶段，假定ISL具有相等长度，从而决定最小跳数路径。在方向增强阶段，认定ISL链路具有不同长度，在最小跳数路径的基础上选择链路长度更短的路径，从而获得最小传播延时路径。

三、仿真

仿真星座模型为由12个轨道、每个轨道24颗卫星组成的极地卫星星座模型，左右相邻轨道上的对应卫星处于同一纬度，轨道高度为1375km。

仿真选取数据包发送点为（31° N，104°E），接收点为（41°N，74° W）。Bellman-Ford算法平均延时为61.469ms，DRA算法平均延时为61.527ms。由此可知，DRA算法性能与Bellman-Ford算法性能十分接近，但是DRA算法平均时间复杂度为O（1）远低于Bellman-Ford算法，因此更适合资源有限的卫星网络。

参 考 文 献

[1]中国互联网信息中心.中国互联网络发展状况统计报告[R].2014，7.

[2]中国互联网信息中心. 2013年中国农村互联网发展状况调查报告[R].2014，5.

[3] Ekici E， Akyildiz I F，Bender M D. A distributed routing algorithm for datagram traffic in LEO satellite networks[J].IEEE/ACM Trans.Networking，2001，9（2）：137-147.