基于改进蚁群算法的卫星光网络波长分配方法

王蔚龙,李勇军,赵尚弘,辛 宁,赵海燕

(1.空军工程大学信息与导航学院通信系统教研室,陕西 西安 710038;2.中国空间技术研究院通信卫星事业部,北京 100094)

1 引 言

随着卫星网络视频和云服务的快速增长,以及对气象,环境和军事服务的需求多样化,卫星网络中数据量急剧增加,而星间激光链路将成为未来空间网络的关键组成部分[1]。相比星间微波链路通信,星间激光通信分布式卫星系统的终端质量、尺寸和功耗都较小,且具有高速率、大带宽和抗毁性强的优势[2]。通过在卫星星座上形成灵活和透明光传输网络,可以采用多波长和波长路由分配技术(Routing And Wavelength Assignment,RWA)来确保卫星之间的通信连接[3]。RWA是实现下一代卫星光网络波长资源分配的核心问题之一[4-5]。

在分布式卫星光网络中,路由技术是决定影响网络性能的重要因素。波长路由具有粗交换粒度,对于具有大量遥感探测和视频信息的业务,能够避免频繁的复用和解复用过程,提升数据传输效率。RWA问题的挑战性在于同时涉及到达业务的路由计算和波长分配两个问题。Dijkstra算法[6],首次命中波长分配方法[4],整数线性规划模型方法[7],遗传算法(Genetic Algorithm,GA)和分图层模型方法[8]能够从多个角度出发,解决不同应用场景中的RWA问题,但是在计算效率和全局最优性方面仍然存在问题。

蚁群优化(Ant Colony Optimization,ACO)算法是一种模仿蚁群行为的启发式算法,可以并行解决复杂的组合优化问题,为解决卫星光网络RWA问题提供了新思路[9-11]。动态ACO算法可以适应动态RWA问题网络状态的实时变化,与Dijkstra算法相比,可以有效降低网络拥塞概率[11]。ACO也可应用于卫星光网络,但是近期研究没有考虑激光链路上波长负载均衡对通信性能的影响[12-13]。另外,鉴于卫星的高动态特性,卫星光网络中的RWA问题对ACO算法的执行效率有较高要求。

本文针对卫星光网络RWA问题,建立波长转换器稀疏分布的全光卫星网络系统模型。考虑卫星节点距离,通信延迟,链路波长负载平衡和算法执行效率,提出了一种可以同时进行波长分配与路由选择的SAC-RWA算法。

2 卫星光网络系统模型

2.1 卫星光网络拓扑结构

卫星光网络系统的结构如图1所示,它由卫星光网络,地面信关站(Gateway Earth Station,GES)和卫星用户组成。网络中卫星之间通过激光链路相互连接,为用户提供全球通信服务,而卫星与地面用户利用微波链路进行通信。假设有用户需要从节点s发送数据到d时,根据波长可用状态选择波长λ3建立光路径(s→v1→v2→v3→v4→d)。

图1 卫星光网络系统结构

图2 卫星光网络拓扑结构

如图2所示,卫星光网络物理拓扑由2π星座构成,这种星座可以被视为使用激光链路双向曼哈顿街网络。2π星座包含P个轨道平面,每个轨道包括S个卫星节点,这些节点通过光链路连接到与其相邻的四个卫星。卫星之间进行通信连接的激光链路分为轨内星间链路(Inter-Satellite Link,ISL)和轨间ISL有两种。前者的链路长度固定,将同一轨道面内卫星互连；而后者的链路长度随时间变化,用于连接不同轨道面是的卫星节点。虽然网络中卫星的位置是不断变化的,但是卫星光网络的拓扑结构会随时间呈现周期性的变化,因此可以预测卫星光网络的拓扑结构。将卫星在网络中的功能简化为卫星终端和地面终端之间的接口和数据传输的中继,本文重点讨论卫星的中继功能。假设ISL拥有相同数量的波长,且支持具有波长分配功能的WDM结构。多个光路可以共享同一条物理光链路,但需要为各条光路分配不同的波长。

2.2 卫星光网络波长与路由分析

令无向图G=(V,E)表示星座的网络模型,其中V={1,2,…,n}表示节点集合,E={1,2,…,l}表示链路集合。每个节点都有两个表,分别用于登记链路信息和对应的信息素信息。Ωij={λij1,λij2,…,λijv}表示节点间链路上的波长资源,其中v是光链路上的波长数。pi=1表示节点i装备有波长转换器,pi=0则表示没有波长转换器。eij表示从节点i到j的边,eijw是边eij上波长w的波长链路。拥塞率表示失败的通信请求数与通信请求总数之比,资源利用率是系统当前占用的波长通道数与波长通道总数之比,本章的目的是为通信请求寻找资源消耗最小的波长路径。

t时刻从节点i到j的传输延迟为Tij(t),它由信号通过链路lij的传输延迟和信号由中间节点i转发而产生的处理延迟组成:

(1)

为了缓解因波长连续性限制而导致的光链路波长利用率低和网络拥塞率高的问题,提出了一种稀疏全光波长转换器部署方案。如图3所示,在双主星结构DSC的网络中,在轨道平面内每间隔一个节点部署一个光波长转换器；对于不同的轨道,光波长转换器按照间隔一个轨道的规则放置。对于包含两个波长链路eijw和ejkw’(w≠w′)的光路径,节点j必须具有波长转换功能,以便可以将来自eij且使用波长w的数据通过波长w′转发到节点k。

图3 波长转换器部署

3 基于蚁群算法的波长分配方法机制

3.1 波长分配初始化与状态转移规则

卫星光网络中的每个节点都有一个信息素表,将节点i到节点j光波长w上的信息素值表示为τijw(t),其值根据路径长度来确定。利用合理的启发式方法初始化信息素的值,能够减少寻找次优甚至最优解所需的时间。考虑到最小化光网络服务请求的通信成本,将波长链路eijw上的初始信息素表示为[9]:

(2)

其中,c(eij)为通信成本,取卫星光网络中链路eij长度的整数。如果λijw=0,则意味着波长链路eijw不可用,因此禁止蚂蚁通过该不可用的波长链路；如果波长链路可用(λijw=1),则根据式(2)初始化信息素,使通信成本较低的链路在蚂蚁出发之前就具有较高的信息素浓度。

将t时刻节点i和节点j之间的波长空闲率表示如下[14]:

(3)

其中,v是链路eij的波长总数；而wij是链路eij当前被占用的波长数。位于节点i的蚂蚁根据下一跳的候选节点和通往这些节点链路的波长使用情况计算通信链路的波长空闲率。将波长空闲率作为新的约束条件引入波长链路的状态转移函数中,则t时刻的转移概率可表示为[12]:

(4)

其中,α≥0是描述先前蚂蚁留下痕迹重要性的信息启发因子,它体现了链路上遗留的信息素对当前蚂蚁运动的影响,即α越大,当前蚂蚁越倾向于重复选择先前蚂蚁经过的路径。β≥0是描述启发信息对蚂蚁选路重要程度的期望启发因子,即β越大,寻路过程越遵循贪心原则。节点i和节点j之间的启发信息定义为ηij,通常用节点间距离的倒数来表示。τijw(t)是从节点i到节点j间波长w的信息素值,A表示当前时刻下一跳可用节点的集合。

当蚂蚁到达中间节点n时,将根据如下状态转换规则选择下一跳的节点:

(5)

3.2 光链路信息素更新规则

为避免算法过早收敛于局部最优解和防止启发信息被之前蚂蚁遗留的信息所淹没,分别提出了本地更新规则和全局更新规则。如果蚂蚁成功找到下一跳波长链路,则在离开当前节点前启动本地更新规则,以避免过早收敛。算法根据蚂蚁通过后产生的信息更新信息素浓度τijw(t),信息素浓度采用如下方式进行更新:

为防止启发信息被之前蚂蚁遗留的剩余信息淹没,需要在每个蚂蚁的循环周期结束后,更新剩余信息。因此全局更新规则在蚂蚁到达目的卫星节点时被激活,该规则的思想是增加之前蚂蚁经过的波长链路上的信息素浓度,同时降低未访问的波长链路上的信息素浓度。链路信息素的全局更新规则如下所示[12]:

(7)

(8)

其中,Q表示蚂蚁在一次循环中在路径上释放的信息素,Jx是蚂蚁x在当前寻路周期中走过的路径长度。当蚂蚁完成一次波长链路搜索后,信息素增量按照式的规则均匀分布在蚂蚁经过的路径上,而其他路径上的信息素则保持不变。

3.3 卫星光网络请求区域受限策略

随着未来全球卫星星座通信系统的发展,卫星星座中节点数量的增加将导致SAC-RWA计算量的急剧增加。特别是当节点使用具有双主星DSC结构时,更为复杂的网络结构会算法的收敛速度并增加节点处理延迟。对于给定的源卫星节点和目的卫星节点,通信成本最短的路径通常位于以这对节点为对角所确定的矩形区域中。因此,本文采用请求区域受限(Restricted Request Area,RRA)策略限制蚂蚁活动范围,进而简化计算,加速算法的收敛。如图4所示,RRA策略将蚂蚁寻路的区域限制在矩形方框内。为了确保蚂蚁通过的节点都在受限的矩形区域内,对转移概率式(4)进行如下修改:

j∈A∩As

(9)

其中,As是由RRA策略确定的矩形区域中的节点集合。由于只有根据源-目的节点对所确定区域中的节点才可以选择作为下一跳节点,因此RRA策略减少了蚂蚁下一跳的候选节点数量,能够降低算法的计算量,提高算法的收敛速度。

图4 请求区域受限策略

3.4 链路波长负载平衡分析

z=(y+ex-1)x-y

(10)

图5 z=(y+ex-1)x-y的函数图像

SAC-RWA算法的执行步骤表示如下,算法的停止条件是达到指定的迭代次数。

SAC-RWA算法1: loop:服务请求到达并获得源/目的节点2: 初始化网络,设定蚂蚁数量和算法迭代次数;3: repeat4: repeat5: 获取蚂蚁活动范围并选取波长waveNo;6: while 当前节点不是目的地 do7: 记录当前节点和waveNo,获取下一跳可用节点集合Sava;8: ifSava ≠ Ø then9: if 当前节点部署了波长转换器then10: 利用式(4)选择下一跳节点且全部波长可用;11: else12: 利用式(4)选择下一跳节点且只有waveNo可用;13: end if14: 得到下一跳节点与波长waveNo,利用式(6)更新信息素;15: 将当前节点放入Tabu(t);16: 蚂蚁移动至下一跳节点; 17: else18: break;19: end if20: end while21: 利用式式(7)更新信息素;22: until 所有蚂蚁都被发出23: 计算本次迭代的最佳波长链路;24: until 满足停止条件25: if 最佳波长链路存在then26: 建立传输路径;27: else28: 当前服务请求被阻塞;29: end if30: end

当节点具有波长转换功能时,在最差的情况下,每个蚂蚁的计算复杂度为Ο(VW),小于文献[15]中的计算复杂度。由于SAC-RWA算法的最大迭代次数为Ni,蚂蚁数为Na,因此整个算法的计算复杂度为Ο(VWNiNa)。

4 仿真结果与分析

以具有120个节点的2π星座为例,评估所提出算法的性能。为了简化分析过程,假设卫星网络在一段较小的时间间隔内被认为是静止的,网络中各元素的连接关系在这段小时间间隔内保持不变。2π星座参数如表1所示,采用稀疏全光波长转换器部署方案。假设所有节点都没有排队等待机制,服务请求一旦被拒绝就立即将其丢弃。星间链路最大可用波长数为16[3],信号由节点的转发而产生的处理延迟同一设置为10 ms[4],卫星光网络的传输延迟阈值设置为300 ms[16]。根据初步试验,将算法中的参数设置如下α=0.3,β=0.5,φ=0.9,ρ=0.7和r0=0.5。将算法的迭代次数设为100,每个迭代周期释放20只蚂蚁。在2π星座中随机选取源-目的节点对,算法能够获得统计平均的优化结果。

表1 2π星座参数表

图6比较了2π星座网络中不同算法的拥塞率,每条链路都有8个可用波长。将业务强度定义为网络每小时占用的波长信道数与每次占用的平均时间的乘积。从图6可以看出,由双主星DSC结构SAC-RWA算法获得的波长与路由分配结果的拥塞率最低,特别是当业务强度为160 Erl时,相比于Dijkstra+FF算法,双主星DSC结构SAC-RWA算法将拥塞率降低了69.06 %。此外,随着业务强度增加,双主星DSC结构SAC-RWA算法和考虑延迟约束的RWA算法(DRWA-DC)[9]之间的性能差距不断变大。这是因为DRWA算法在构造转移概率函数时没有将式所示的波长空闲率考虑在内,造成了链路的波长负载不均衡,在业务强度高时链路的可用波长信道不足,致使拥塞率增长得更快。根据图6还可以得出,小窗口策略RWA算法(SWS-RWA)[12]求出的波长与路由分配结果的拥塞率高于双主星DSC结构SAC-RWA算法获得的拥塞率,这是由于在小窗口策略RWA算法中,蚂蚁收集的信息素是整个链路的,没有将信息素细化到链路上的各个波长,而且链路波长随机选择,未考虑链路上的波长负载状态。

图6 不同算法的拥塞率性能比较

图7所示为2π星座网络中不同算法得出的波长与路由分配结果的波长利用率,每条链路都有8个可用波长。当业务强度为265 Erl时,与Dijkstra+FF,DRWA和单卫星结构SAC-RWA相比,双主星DSC结构SAC-RWA的资源利用率分别提高了31.37 %,9.56 %和13.28 %。因此可以得出结论,双主星DSC结构SAC-RWA算法优于其他三种算法。随着业务强度的增加,链路的可用波长数量减少,并且只能以较少的跳数建立光链路,长距离数据传输链路难以被建立。而对于双主星DSC结构SAC-RWA算法,一方面,在寻找最佳数据传输光路径时会考虑波长空闲率,因此蚂蚁选路时倾向于选择链路波长负载较小的节点；另一方面,双主星DSC结构可确保在选择下一跳时存在更多的候选节点,网络链路资源更多,从而在网络负担较重的场景下可建立长距离多跳数的光传输路径。因此,双主星DSC结构SAC-RWA的波长利用率曲线在高业务强度下具有更好的表现。

图7 不同算法的资源利用率比较

图8所示为双主星DSC结构SAC-RWA算法的收敛性能,并与未采用RRA策略[13]和单卫星结构情况下的算法性能进行了比较。仿真选择了源卫星节点(11,2)和目的卫星节点(3,9)进行收敛性能的分析。在收敛时,采用单卫星结构算法的迭代次数比采用双主星结构算法的迭代次数减少了8次。这是由于单卫星结构只有四条通信链路,选择下一跳通信链路时可用的节点较少,所以单卫星结构容易陷入局部最优,而双主星结构可以避免这种情况。虽然采用单卫星结构的算法更早达到收敛,但是求出最优光路径的跳数增加了2跳。双主星结构的SAC-RWA算法具有更多的候选通信链路,从而增加了选路的多样性与灵活性,能够得出性能更好的波长分配结果和数据传输路径,算法综合性能更好。如图8所示,在收敛时,采用RRA策略得出的迭代次数比没有采用RRA策略时的迭代次数少10次,这表明RRA策略影响了算法的收敛速度。

图8 算法的收敛性

由于RRA策略限制了蚂蚁在光网络中寻找数据传输链路时的活动范围,进而减少了下一跳候选节点集中的无效节点,因此提升了计算的效率。

图9进一步比较了有无RRA策略对数据传输链路长度和网络拥塞率的影响,其中纵坐标分别为50对源-目的节点的最优光路径的平均跳数和网络拥塞率。由图9可得,当平均波长利用率为0.66时,使用RRA策略发现的波长链路跳数比不使用RRA策略的跳数少28.4 %,而使用RRA策略得出的拥塞率比没有使用RRA策略得出的拥塞率高8.2 %。在不同的平均波长利用率下,使用RRA策略发现的波长链路跳数比不使用RRA策略发现的波长链路跳数短；但是,采用RRA策略后网络拥塞率会略有下降。造成这种结果的原因是,RRA策略在指定蚂蚁的搜索区域时会为下一跳的选路排除一些潜在的可用节点。这些潜在的可用节点一大部分是无效的,排除后能够提高收敛效率并降低计算量,但是RRA策略影响了下一跳节点选择的范围和多样性,算法性能的提升是以稍微降低的拥塞率为代价来实现的。此外对于光路径平均跳数和网络拥塞率,随着平均波长利用率的提高,有RRA策略和无RRA策略算法之间的性能差距先增大后减小。

图9 光路径跳数和拥塞率随波长利用率的变化情况

5 结 论

为解决卫星光网络中的路由与波长分配问题,本文提出了一种基于启发式思想的SAC-RWA算法。在卫星光网络中引入了基于DSC的双主星节点结构,以提升可供选择链路的数量。建立卫星光网络系统模型时考虑了传输延迟和波长连续性对网络性能的影响,将波长空闲率引入状态转移函数来实现链路上的波长负载均衡,同时利用RRA策略以提高算法计算效率。仿真结果表明,与不考虑波长空闲率和单卫星结构节点的情况相比,双主星DSC结构的SAC-RWA算法在拥塞率和资源利用方面具有更好的性能。在使用双主星DSC结构和RRA策略之后,网络性能和收敛速度有了较大的提升。尽管RRA策略略微降低了拥塞率性能,但是算法的计算量因此大大降低,提升了蚂蚁选路的效率,实现了拥塞率与收敛速度之间的折衷平衡。