徐双¹, 王兴伟², 黄敏³
1.东北大学 计算机科学与工程学院， 辽宁 沈阳 110169;
2.东北大学 软件学院， 辽宁 沈阳 110169;
3.东北大学 信息科学与工程学院， 辽宁 沈阳 110819
收稿日期: 2015-10-27
基金项目: 国家杰出青年科学基金资助项目(61225012, 71325002); 国家自然科学基金资助项目(61572123); 辽宁省百千万人才工程项目(2013921068)。
作者简介: 徐 双(1990-),女,河北秦皇岛人,东北大学博士研究生;
黄 敏(1968-),女,福建长乐人,东北大学教授,博士生导师;
王兴伟(1968-),男,辽宁盖州人,东北大学教授,博士生导师。

摘要: 由于低轨道卫星星上功率和带宽资源有限，设计有效的资源分配方法具有重要的意义.基于此提出了一种低轨道星间功率带宽资源联合分配方法，提高了星间资源分配的公平性和网络业务承载能力.该方法应用地面站数目和星地链路存在时间刻画星间链路容量的比例，将星间资源分配问题归纳为非线性混合整数规划问题.通过引入动态可行域，定义二元变量更新操作来改进燕子群算法，用于优化模型求解.仿真得出卫星瞬时吞吐容量和瞬时网络容量变化具有周期性，并伴有随机波动，所提方法牺牲了网络容量，获取了星间资源分配的公平性.
关键词：低轨道卫星功率带宽联合分配燕子群优化
Power and Bandwidth Joint Allocation Method for LEO Satellites
XU Shuang¹, WANG Xing-wei², HUANG Min³
1.School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
2.School of Software, Northeastern University, Shenyang 110169, China;
3.School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: WANG Xing-wei. E-mail:wangxw@mail.neu.edu.cn
Abstract: Onboard power and bandwidth of low earth orbit (LEO) satellite networks are limited, thus designing an efficient resource allocation method is of great significance. A power and bandwidth joint allocation method for LEO satellites was proposed, and improved the resource allocation fairness among satellites and network service carrying ability were improved. The ground stations number and user data links life time were used to describe proportional constraints of intersatellite links capacity, and satellite resources allocation problem was formulated as a nonlinear mixed integer programming problem. Swallow swarm optimization (SSO) was improved by introducing dynamic feasible region and defining binary variable update operation, then the optimization model was solved by using this method. Simulations demonstrate satellite instantaneous throughput capacity and network instantaneous capacity change periodically with random fluctuations. The method achieves the resource allocation fairness among satellites at cost of network capacity.
Key Words: low earth orbit (LEO) satellitespowerbandwidthjoint allocationswallow swarm optimization
低轨道卫星网络由LEO卫星组成，卫星运行速度快，拓扑频繁变化，星地往返延迟小，对天线尺寸和传输功率要求低，在快接入、广覆盖，以及高带宽实时服务中发挥着重要的作用，但LEO卫星星上资源有限，设计有效的星间网络资源分配算法，有利于提高网络的业务承载能力和资源利用率.
文献[1]设计了保证卫星资源有效利用的带宽和功率分配算法.文献[2]考虑QoS需求，用拉格朗日启发算法求解低轨道卫星网络子载波分配问题.文献[3]考虑延迟对实时业务的影响，提出了一种功率和带宽资源分配方法，实现了吞吐量和延迟间的平衡.文献[4]提出了一种多波束卫星网络的功率和带宽分配方法，提高了波束间容量的公平性.上述方法主要面向下行链路资源，不适于星间链路.
本文提出一种面向网络容量的低轨道星间功率和带宽资源联合分配方法.首先，将带宽分配转化为子信道分配，将低轨道星间资源分配问题归纳为一个以最大化卫星节点吞吐容量为目标的非线性混合整数规划问题.其次，综合考虑星地链路存在时间和卫星覆盖的地面站数目，刻画相邻卫星间星际链路容量比例公平性约束.最后，受智能优化方法在此类问题求解中成功应用^[5-7]的启发，本文引入动态可行域，定义二元参数更新操作，采用燕子群优化(swallow swarm optimization，SSO)算法^[8-9]求解此问题.在铱星和全球星系统上仿真该算法，并用4个不同指标评价该算法性能.
1 问题描述1.1 低轨道卫星网络构成低轨道卫星网络的LEO卫星之间凭借星际链路互相通信，网络拓扑周期性变化.链路距离的变化和通断，造成网络容量波动.每颗LEO卫星与同一轨道上前后两相邻卫星间建立的持续连接链路称为同轨链路，与左右轨道上的两卫星建立的链路称为异轨链路，随卫星的绕行断开或重连.
1.2 容量分析假设卫星s_i0j0总带宽为B，相邻卫星数为N_nei.将s_i0j0总带宽均分给N_sub个正交子信道，通过分配子信道来分配带宽资源.子信道分配结果C表示为C=[c_{1, 1}, c_{1, 2}, …, c_{1, Nsub}, c_{2, 1}, c_{2, 2}, …, c_{2, Nsub}, …, c_{Nnei, 1}, c_{Nnei, 2}, …, c_{Nnei, Nsub}].其中，c_{k, i}∈{0, 1}, k∈[1, N_nei], i∈[1, N_sub]，c_{k, i}=1表示第i个子信道被分配给第k颗相邻卫星.功率分配结果为P=[p₁, p₂, …, p_Nsub]，且，p_i为分配给子信道i的发射功率，p_total为s_i0j0的总功率.
定义t时刻s_i0j0与第k个相邻卫星间的链路容量T_k^link为s_i0j0分配给该相邻卫星的子信道容量和：

(1)

其中, SNR_{k, i}为第k个相邻卫星的第i个子信道的信噪比.
s_i0j0的瞬时吞吐容量
根据拓扑中链路是否发生切换，将网络周期T划分成若干时间片，每个时间片内，网络容量较稳定.每个时间片内设置若干采样点，应用采样点容量近似计算T内的平均吞吐容量SATC_i0j0，如式(2)所示：

(2)

其中：S_sample为采样时刻集合；|S_sample|为采样点数.
t时刻的瞬时网络容量INC(t)=，其中|S|为卫星数目.周期T内的平均网络容量.
1.3 链路存在时间地面用户通过地面站接入卫星系统，而卫星不断绕地球转动，故不同时刻同一卫星覆盖的地面站不断变化.假设当前时刻t_now地面站G₀位于卫星S₀的覆盖范围内，时刻t_end时S₀恰好不再覆盖G₀，则定义时间长度t_end－t_now为星地链路存在时间T_lfp.假设t_begin时刻G₀恰好进入S₀的覆盖范围，则定义时间长度t_end－t_begin为星地链路最大存在时间T_mlfp.
1.4 问题建模同一卫星可能同时覆盖多个地面站，并与这些地面站同时通信.所以卫星覆盖的地面站数越多，卫星传输的业务量越大，需要分配的资源越多.此外，星地链路存在时间越长，被用来传输数据的概率越大，所需分配的资源越多.本文采用卫星覆盖的地面站数和星地链路存在时间刻画比例系数，从而表征相邻卫星间链路容量的比例约束，提高资源分配中各卫星间的公平性.以最大化节点吞吐量为目标，建立带宽功率联合优化模型如下：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式(6)为星际链路正常通信的信噪比约束，式(9)为相邻卫星间星际链路的容量比例约束，比例系数φ_k的计算如式(10)所示：

(10)

其中:β_gst为地面站对链路容量的影响因子;集合Ω_G表示s_i0j0的第k颗相邻卫星覆盖的地面站.
2 方法设计上述模型属于非线性混合整数规划问题，本文采用SSO算法求解.
2.1 动态可行域和适应度函数SSO算法寻优中，可行解和非可行解并存，而进化后期种群中基本都是可行解，但这些可行解的质量可能很差，导致最终收敛到局部最优解.可行域附近的非可行解违反约束程度低，目标函数值接近最优值，能为搜索过程提供较多信息.故本文引入动态可行域，即由可行域和可行域附近的部分非可行解组成的集合，使得搜索过程从可行解和非可行解两个方向同时逼近最优解.
动态可行域的设置需考虑非可行解的个数和选择准则.迭代初期，选择较多的非可行解组成动态可行域，可以增加种群的多样性，但由于约束问题的最优解必须是可行解，所以随着迭代次数的增加，非可行解的个数逐渐减小，使动态可行域逐渐收缩到实际可行域.非可行解的个数N_select变化如下：

(11)

其中:N_lea为领队燕子数(详见2.3节)；iter为当前迭代次数；maxIter为最大迭代次数.
将优化模型中的约束整理为不等式约束g₁(X)和等式约束g₂(X)，构造违反约束程度Con(X)，如式(12)~式(14)所示：

(12)

(13)

(14)

构造目标函数Obj(X)=SITC_i0j0，并归一化为，用G(X)=归一化违反约束程度.
根据F(X)和G(X)构造评判函数Est(X_inf)为

(15)

计算各非可行解的评判函数值并排序，选取前N_select个非可行解组成动态可行域D_fea.
根据动态可行域构造适应度函数：

(16)

2.2 解的初始化燕子的位置对应优化问题中的解，每个解X=(C, P)由整数向量C和实数向量P构成，根据式(17)和式(18)初始化C和P.燕子飞行速度分解为沿主要领队燕子方向的速度v_HL和沿局部领队燕子方向的速度v_LL，初始化方式与解的初始化方式相同.

(17)

(18)

2.3 领队燕子领队燕子包括主要领队燕子和局部领队燕子.SSO算法将整个燕子种群分成多个部分，每个部分有1只局部领队燕子，整个种群有1只主要领队燕子，引导整个燕子群的运动方向，其他燕子的速度主要受二者影响.根据燕子适应度值对所有燕子进行排序，把适应度值最大的燕子设为主要领队燕子，再按照排序依次选取N_lea－1个燕子作为局部领队燕子.在迭代的过程中，根据上述原则重新排序所有燕子，选取新的主要领队燕子和局部领队燕子.
2.4 探索燕子探索燕子是燕子群中的主要部分，负责搜索状态空间.探索燕子根据飞行速度v^new飞到新位置X^new，v^new沿主要领队燕子方向的速度为v_HL^new和沿局部领队燕子方向的速度为v_LL^new.
v_HL^new和v_LL^new的实数向量v_PHL^new和v_PLL^new更新方式为

(19)

其中：v_P^old是探索燕子当前速度沿领队燕子方向的实数部分；rand()是[0,1]内的随机数；X_P^His是该探索燕子历史最优位置的实数部分;X_P是领队燕子位置的实数部分；X_P^old是探索燕子当前位置的实数部分；α和β是探索燕子沿领队燕子方向速度收敛参数，调整方式如下：

(20)

(21)

其中，a₁=0.5，a₂=2.5.
定义二元变量更新操作DisOpe如下：
将C变换成N_nei×N_sub的矩阵，依次对比矩阵中每一列的值，如果矩阵l列的值均相等，则输出矩阵l列的值；否则，分别计算出所有矩阵每行第l个元素之和.如果所有和中存在唯一最大值，且位于第row行，则把输出矩阵中第row行l列的值设为1，其他位设为0；否则，从这些最值所在行中随机选择一行，把输出矩阵中该行的第l列的值设为1，其他位设为0.根据DisOpe(v_CHL^old)和DisOpe(v_CLL^old)更新v_HL^new和v_LL^new的整数向量v_CHL^new和v_CLL^new.
v^new的实数向量v_P^new=v_PHL^new+v_PLL^new，整数向量v_C^new=DisOpe(v_C^old), v_C^old为探索燕子当前速度和整数部分.X^new的实数向量和整数向量部分分别为X_P^new=X_P^old+v_P^new和X_C^new=DisOpe(X_C^old), X_C^old为探索燕子当前位置的整数部分.
根据探索燕子X^exp与局部领队燕子X^LL之间的距离判断探索燕子是否属于某一局部领队燕子，距离计算式如下：

(22)

2.5 无目标燕子把适应度函数值较差的燕子设置为无目标燕子，采取随机飞行寻找被忽略的解空间.飞行后的新位置X^new′中实数向量更新方式如下：

(23)

其中：rand{－1, 1}表示随机生成-1或1；rand(0, p_total)表示生成[0, p_total]区间中的随机数.X^new′的整数向量X_C^new′=DisOpe(X_C^old′)，其中X^rand是按照解初始化方式随机生成的位置值.
2.6 算法伪代码算法1 低轨道星间带宽功率联合分配算法：
输入：p_total, N_sub, N_nei, N_lea, N_exp, N_aim，maxIter
输出：C和P
1. 初始化燕子群S_pop中燕子的位置X, v_HL和v_LL，iter=1；
2. FOR iter≤maxIter;
3. 构造动态可行域D_fea；
4. 按照式(16)计算所有个体的适应度函数值Fit(X)；
5. 根据Fit(X)分类种群S_pop中的燕子；
6. 对于探索燕子根据式(22)找出距离最近的局部领队燕子；
7. 计算α_HL，β_HL，α_LL和β_LL，并更新探索燕子位置；
8. 更新无目标燕子位置；
9. iter++；
10. END FOR
11.根据最优个体计算C和P，并返回.
3 仿真与性能分析采用STK为仿真提供卫星运动轨迹、可见性和拓扑数据.用仿真平台Eclipse实现最大化卫星瞬时吞吐容量的资源分配方法(maximum capacity based resources allocation method，MCRAM)和基于比例公平性的资源分配方法(proportional fairness based resources allocation method，PFRAM).铱星系统为极轨道星座，全球星系统为Walker星座，故本文采用上述两种星座作为仿真拓扑用例.仿真参数如表 1所示.
表 1(Table 1)

表 1 仿真参数Table 1 Simulation parameters 参数名称 参数值 (铱星/ 全球星) 卫星数 66/48 轨道面数 6/8 相位因子 —/2 轨道倾角/(°) 86.4/52 带宽/Mbps 200/200 探索燕子数 250 地面站数 100 轨道面内卫星数 11/6 轨道高度/km 780/1414 系统周期/min 100.45/114.09 边界纬度值/(°) 60/48 领队燕子数 20 无目标燕子数 50 最大迭代次数 1000

表 1 仿真参数 Table 1 Simulation parameters

3.1 卫星瞬时吞吐容量从铱星系统和全球星系统周期中分别均匀选取154和144个采样点，并随机选取1颗从高纬地区向低纬地区运动的卫星，分析其瞬时吞吐容量变化，结果如图 1所示.由图 1可知，铱星系统卫星瞬时吞吐容量曲线开始平稳，因为卫星位于高纬地区，只有2条距离不变的同轨链路.当卫星向赤道运行时，两异轨链路重新建立，卫星瞬时吞吐容量变大.当卫星靠近赤道时，异轨链路距离变大，卫星瞬时吞吐容量减小.卫星经过赤道后，异轨链路距离变小，卫星瞬时吞吐容量变大.再次进入高纬度地区时，异轨链路断开，卫星瞬时吞吐容量迅速减小，上述过程周期性重复出现.PFRAM考虑了地面站的影响，曲线在整个周期内出现随机波动.全球星系统的卫星瞬时吞吐容量曲线波动较复杂，因为其异轨链路断开或重连的时刻不同，当一端的卫星进入高纬度地区时，卫星仍能保持3条通信链路，导致曲线出现先下降后升高的情况.
图 1(Fig. 1)

图 1 卫星瞬时吞吐容量Fig.1 Satellite instantaneous throughput capacity

3.2 卫星平均吞吐容量对比卫星功率为20，60，100W时，两卫星系统的卫星平均吞吐容量如图 2所示.由图 2可知，增加卫星功率可提高卫星平均吞吐容量.当卫星功率相同时，MCRAM的卫星平均吞吐容量较大，是因为PFRAM考虑了卫星链路间的公平性，增强了约束性，导致卫星平均吞吐容量偏小，但在整个周期内卫星覆盖的地面站数和链路可用时间不断变化，导致两种方法的卫星平均吞吐容量差异较小.PFRAM充分考虑覆盖的地面站数和星地链路存在时间，均衡合理地分配更多资源给覆盖区域内业务需求多且链路稳定的卫星.因此，PFRAM的卫星平均吞吐容量虽然降低了，但提高了资源分配的公平性及合理性.
图 2(Fig. 2)

图 2 平均吞吐容量Fig.2 Average throughput capacity

3.3 瞬时网络容量对比分析两卫星系统周期内的瞬时网络容量，仿真结果如图 3所示.由图 3可知，MCRAM的瞬时网络容量曲线具有很强的规律性，但由于地面站分布不均，PFRAM的曲线伴有一定的随机波动.这是因为系统中星际链路频繁切换，导致瞬时网络容量增大或减小.当有较多卫星在高纬度地区时，星际链路较少，星上资源得不到有效利用，瞬时网络容量较小.当这些卫星离开高纬度地区时，链路重连，瞬时网络容量增大.随着卫星不断进出高纬度地区，瞬时网络容量值规律性波动，但由于链路长度变化导致轻微波动.
图 3(Fig. 3)

图 3 瞬时网络容量Fig.3 Instantaneous network capacity

3.4 平均网络容量对比卫星功率为20，60，100W时，两卫星系统的平均网络容量如图 4所示.由图 4可知，增加卫星功率可提高平均网络容量.当卫星功率相同时，MCRAM的平均网络容量较大，这是因为PFRAM考虑卫星链路间的公平性，增强了约束性，导致平均网络容量偏小.资源分配的公平性保证了地面站数较多、星地链路存在时间较长的区域能获得更多的网络资源，服务质量提高；反之分配较少的网络资源，但在整个周期内卫星覆盖的地面站数和链路可用时间不断变化，导致两种方法的平均网络容量差异较小.PFRAM通过牺牲平均网络容量获得网络资源分配公平性，提高了资源利用率.
图 4(Fig. 4)

图 4 平均网络容量Fig.4 Average network capacity

4 结 论本文结合卫星拓扑变化特点，设计网络容量分析方法，刻画比例公平性约束，构建资源分配优化模型，改进燕子群算法，提出一种低轨道星间功率带宽资源联合分配方法.仿真分析得出卫星瞬时吞吐容量和网络瞬时容量变化具有周期性和随机性，所提资源分配算法通过牺牲网络容量获得卫星间资源分配的公平性.在实际应用背景下验证并改进本文方法的实用性是今后研究工作的重点.
参考文献

[1]	Nakahira K, Abe J, Mashino J. Novel channel allocation algorithm using spectrum control technique for effective usage of both satellite transponder bandwidth and satellite transmission power[J]. IEICE Transactions on Communications , 2012, 95(11): 3393–3403.
[2]	Wu X L,Chen Y Y,Gao L Q,et al.A utility-based OFDM resource allocation scheme for LEO small satellite system[C]// International Conference on Cyberspace Technology.Stevenage:IET,2014:68-73.
[3]	Ji Z, Wang Y Z, Feng W, et al. Delay-aware power and bandwidth allocation for multiuser satellite downlinks[J].IEEE Communications Letters , 2014, 18(11): 1951–1954.DOI:10.1109/LCOMM.2014.2363111
[4]	Wang H, Liu A J, Pan X F. Optimization of joint power and bandwidth allocation in multi-spot-beam satellite communication systems[J].Mathematical Problems in Engineering , 2014, 2014: 1–9.
[5]	Wang X W, Wang X Y, Che H, et al. An intelligent economic approach for dynamic resource allocation in cloud services[J].IEEE Transactions on Cloud Computing , 2015, 3(3): 275–289.DOI:10.1109/TCC.2015.2415776
[6]	Wang X W, Cheng H, Li K Q, et al. A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks[J].Journal of Parallel and Distributed Computing , 2013, 73(6): 807–822.DOI:10.1016/j.jpdc.2013.02.010
[7]	Wang X W, Cheng H, Huang M. Multi-robot navigation based QoS routing in self-organizing networks[J].Engineering Applications of Artificial Intelligence , 2013, 26(1): 262–272.DOI:10.1016/j.engappai.2012.01.008
[8]	Neshat M, Sepidnam G, Sargolzaei M. Swallow swarm optimization algorithm:a new method to optimization[J].Neural Computing and Applications , 2013, 23(2): 429–454.DOI:10.1007/s00521-012-0939-9
[9]	Kaveh A, Bakhshpoori T, Afshari E. An efficient hybrid particle swarm and swallow swarm optimization algorithm[J].Computers & Structures , 2014, 143: 40–59.