基于反向传播的卫星分布式路由算法的改进方法

摘要

本发明提供一种基于反向传播的卫星分布式路由算法的改进方法。具体为（1）为分布式算法加入了反向修正的步骤，增加了对全局负载的考虑；（2）针对卫星分布式路由算法，提出了修正概率、发送概率的计算方法，使得报文的发送受到负载均衡的控制；（3）为修正概率之间创建了联系，让报文在各个方向的发送得以相互关联，适应网络的动态变化。本方法既保持了分布式路由算法的特性，如无需考虑拓扑变化、对星上存储要求较小等特点，又有效地避免了全局负载的不平衡导致的链路利用率和端到端时延等路由指标的下降。

说明书

技术领域

本发明涉及卫星路由算法领域，特别是针对基分布式路由算法的负载均衡优 化领域，具体是指一种基于反向传播的卫星分布式路由算法的改进方法。

背景技术

在单层卫星网络中，研究对象主要集中在单层圆极轨道低轨道(Low Earth  Orbit,LEO)卫星网上。这种采用圆极轨道布星的星座，卫星节点组成一个规则的 网状结构。由于卫星轨道的平行分布，相邻轨道间的星间链路可以继续保持，极 大地减少了网络中的链路切换和重建路由次数，降低了协议涉及的复杂度。目前 已经提出的单层LEO卫星网络路由协议算法有DRA(Distributed Routing  Algorithm)、MASSR(distributed Soft routing algorithm combined with multi-agent  system)、CGR(Contact Graph Routing)、X-YBRA(X-Y Boundary Routing Algorithm) 等多种。然而，卫星网络仍然面临不少问题。随着全球业务与日俱增，业务种类 也在不断扩展，使得对服务质量的要求也日益提高。另外，城市业务密集，乡村 业务稀疏，甚至在占地球表面积达到75%的海洋地区几乎没有业务，这将导致全 球部分区域上空的卫星出现拥塞，而部分卫星利用率过低的现象。

如何合理地设计卫星路由，尽可能地减少网络拥塞、增加对全局负载的考虑， 提高网络资源利用率是卫星路由算法亟待解决的难题。在上述的众多LEO层的路 由算法中，由Ekici E等人提出的DRA算法具有能动态选路、适应时变网络拓扑等 优点，得到了广泛应用。但该算法缺乏对全局负载的考虑，并且整个网络路由状 态具有不稳定性。具体表现为通信链接时的不稳定性，可能造成不必要的报文丢 失，甚至严重时链路中断。

发明内容

本发明的目的是提出一种基于反向传播(Back Propagation，BP)的卫星分布式 路由算法的改进方法，对DRA算法进行了负载均衡的优化，增加了发送概率、 修正概率的参量，用以衡量卫星以及卫星星群是否处于过载状态，通过反馈修正 概率修改发送概率，利用发送概率来控制发送报文方向,延长过载卫星处理拥塞 信息的时间，使改进后的路由算法(BP-DRA)增加对全局负载的考虑，更好地服 务于卫星通信。

首先给出相关定义：

（1）为卫星周围每个方向添加1个修正概率。对于单个报文，只用到当前 首要方向的修正概率ρ_r。修正概率预测了该方向上下一跳卫星负载情况，负载越 重，修正概率越大。

（2）对某一报文，送入相应方向输出缓冲区之前，计算其首要方向和次要 方向的发送概率ρ_t，报文会根据发送概率以拥塞的方式送入首要方向或次要方向， 例如，当某方向修正概率为80%时，以该方向为首要方向的报文，每10个报文 中会有8个送入该方向，而2个送入报文的次要方向。下式中为首要方向发 送概率，为次要方向发送概率，ρ_r为首要方向的修正概率。

${\rho }_{t_1}=1-{\rho }_r$

${\rho }_{t_2}=0+{\rho }_r$

（3）当卫星发现首要方向和次要方向都拥塞，或者各个方向的修正概率都 超过警戒线的状态，称为过载。过载的作用是让附近的卫星尽量避免转发报文至 该卫星。当前卫星的各个方向修正概率表明了各个方的拥塞情况，当其均超过警 戒线时，要尽量避免报文进入当前卫星。

可见，在无修正概率的时候，报文只会送入首要方向。添加了修正概率的基 于BP的反向修正流程，如图1所示。

步骤110：路由算法开始。

步骤120：卫星A向卫星B发送报文。

步骤130：检测卫星B是否过载，当卫星B过载时执行步骤140；否则执行 步骤150。

步骤140：对于新到达的报文回传一个过载信号给前一卫星A，过载信号包 括该报文的两个可选方向；然后执行步骤160。

步骤150：沿用DRA算法；然后跳转步骤180。

步骤160：未收到过载信号的卫星A，根据之前的修正概率来计算发送概率， 并发送报文。收到过载信号的卫星A，先分析信号信息，得知原先报文的两个可 选方向。

步骤170：卫星A将回传卫星B的方向修正概率增加1%，并将另一个可选方 向的修正概率减少1%。

步骤180：每个一段时间，将卫星A各个方向的修正概率下调1%。

步骤190：等待下一条信号，重新开始算法。

这样，对于首要方向处于过载的卫星B的报文，其就减小了，而则增 加了。发向过载区域的报文减少了，则收到过载信号的频率也会降低，修正概率 增加的速度也逐渐减缓。但是修正概率的增加不是无止尽的，当不再有过载信号 传回(意味着前方通信状况好转)时，修正概率就不会变化了。另外，如果相邻方 向过载，也会减少该方向的修正概率。这样，每个方向的修正概率最后会达到一 种动态均衡，以尽可能避免进入过载区域，并充分利用相邻路径。

（4）为了防止大范围拥塞减缓后，各方修正概率不下降，导致报文不选择 最少跳数路径的情况，卫星每隔一定时间将所有方向的修正概率按幅度1%递减 直至0。显然，如果前方依旧过载，这个减小量很快就会被抵消。如果前方正常 通信，卫星也会在一段时间后恢复到选择最短路径的方案。

附图说明

图1基于BP的反向修正流程；

图2基于BP-DRA方案记忆过程一；

图3基于BP-DRA方案记忆过程二；

图4基于BP-DRA方案记忆过程三。

具体实施方式

下面结合附图对本发明做进一步说明。

本发明的目的是基于反向传播的卫星分布式路由算法的改进方法。具体为当 卫星B没有过载时，不做出其它动作，沿用DRA算法。当卫星B过载时，对于新 到达的报文回传一个过载信号给前一卫星A。过载信号包括该报文的两个可选方 向。对于未收到过载信号的卫星A，根据之前的修正概率来计算发送概率，并发 送报文。对于收到过载信号的卫星A，先分析信号信息，得知原先报文的两个可 选方向。将回传卫星B修正概率增加1%，并将另一个可选方向的修正概率减少 1%。最后为了防止大范围拥塞减缓后，各方修正概率不下降，导致报文不选择最 少跳数路径的情况，卫星每隔一定时间将所有方向的修正概率按幅度1%递减直 至0。显然，如果前方依旧过载，这个减小量很快就会被抵消。如果前方正常通 信，卫星也会在一段时间后恢复到选择最短路径的方案。

假设：

（1）为使过载情况不再恶化，所有卫星对A送入的数据最大处理能力为每 时隙8个报文，并且除了接收中心卫星的报文，没有其他任务。

（2）上方卫星初始状态为过载。

（3）卫星A发送的报文首要方向都是上方，次要方向都是右方。

如图2所示，第1时隙时，卫星A送出了10个报文，根据所 以10个报文送入上方，超过处理能力，每个报文都在过载状态，传回10个过载 信号，上方的修正概率变为10%。

在图3所示，第2时隙时，卫星A送出了10个报文，根据所以其中9个报文送入上方，超过处理能力。我们可以发现，当上方卫星已经处 在过载状态时，再以每时隙9个报文送入数据，必将导致每个报文都在过载状态， 这样就会传回9个过载信号，上方修正概率变为19%。1个报文送入右方，无过 载信号传回。

如图4所示，第3时隙时，卫星A送出了10个报文，此时修正概率为19%， 根据所以其中8个送入上方，由于刚好符合处理能力，报文不 再处于过载状态，也就不回传过载信号，上方修正概率保持为0.81，2个报文送 入右方，无过载信号传回。

第4时隙及以后，可见最佳非过载分配方案是10个报文中8个发向上方， 而2个报文发向右方。若负载情况不变，则一直不会再有过载信号，卫星A也就 记住并维持该方案。

在此说明书中，本发明已参照特定的实施实例做了描述。但是，很显然仍可 以做出各种修改和变换而不背离本发明的精神和范围。因此，说明书和附图应被 认为是说明性的而非限制性的。