1 引 言
随着高带宽、大容量卫星激光通信技术的快速发展[1-4]，利用星间激光链路实现多星组网与用户接入的天基激光网络成为重要发展趋势[5-6]。近几年，以欧洲为代表的发达国家相继开展了具有星间激光链路的数据中继卫星系统(TDRSS)的理论研究和星上演示验证[7-8]；同时我国也正在开展利用激光链路实现星间组网的论证工作，提出了将导航星座作为空间信息网的核心激光网络,实现定位与信息传输集成化的设想[9-10]。
而在这些天基激光网络中，用户的接入调度是实现数据可靠传输和资源高效利用的关键和难点所在。针对卫星资源调度问题，学者提出了一系列算法。文献[11-12]分析了卫星通信中任务调度的一些基本原则，并通过对冲突任务执行插空、交换等调整操作实现去冲突化，得到任务调度初始方案。文献[13]采用并行机调度理论对中继星调度问题进行研究，建立了考虑任务优先级的混合整数规划模型，并采用贪婪随机自适应搜索算法对模型进行求解，优化了调度方案，但该模型只局限于微波链路。文献[14-17]建立了微波/激光混合链路的中继卫星系统资源调度的多目标约束规划模型，并利用遗传算法求解得到优化的调度方案。文献[18]针对静态调度方案与实际应用中任务动态变化之间的矛盾，提出了动态插入快速启发式算法，一定程度上解决了激光/微波混合链路卫星网络的动态调度问题，但这种算法只是在静态调度方案的基础上，针对少量任务变化进行再适应操作，本质上仍为静态调度，不能适应任务随时发起的情况。
可见，当前关于天基网络接入调度问题的研究集中于节点数量较少的中继星系统，调度算法多为离线集中式算法(OCSA)。这类调度算法在调度开始前由控制中心计算生成调度方案，调度周期内卫星严格执行调度方案中分配的天线资源。当节点数量较多时，控制中心计算工作量大，且任务信息的收集、调度表的上传等具有较高的时间成本，不具备灵活性和便利性；另外，由于任务调度表的计算具有周期性，算法不能支持实时任务。而在未来天基激光网络中，网络节点和任务数量都会大大增加，对任务等待服务的时延也将提出新的要求，离线集中式接入调度算法将严重制约任务执行的实时性和网络资源调度的灵活、高效性。
基于此，本文对天基激光网络的在线分布式接入调度算法(ODSA)进行研究，通过引入排队机制实现了算法的在线和分布特性，并利用二维马尔可夫链理论分析模型得到了算法性能参数。
2 接入调度问题
未来天基激光网络架构主要分为骨干网和用户两部分，如图1所示(为方便作图，图中只给出了部分典型的激光星间链路)。其中跟踪与数据中继卫星系统(TDRSS)、通信卫星系统及导航星座中的中轨卫星(MEO)等数量众多的卫星节点通过激光链路连接起来构成天基激光网络的骨干网，为各类以低轨卫星为主体的用户提供接入与数据中继传输服务。天基激光网络接入调度问题属于资源调度类问题，被调度的资源为激光接入链路，调度目标为最小化任务的等待时延。天基激光网络接入调度问题具有如下特点：
1) 接入问题具有可见时间窗口约束。可见时间窗口是指骨干网节点对用户的覆盖时段，即二者可进行直接通信的时间段的集合。用户只有在可见时间窗口内，才能接入相应的骨干网节点接受服务，因此可见时间窗口是接入调度的一个重要约束条件。
2) 任务具有优先级约束。在天基激光网络中，任务可分为实时任务与非实时任务，实时任务对等待时延要求高，任务一经发起就希望马上得到服务，如实时侦察视频和图像数据的即时回传；非实时任务对等待时延要求不高，任务发起并等待一段时间后再接受服务，如环境观测卫星、电子测绘卫星等数据的回传。
3) 骨干网节点对用户形成多重覆盖。与地面蜂窝移动通信网和低轨卫星通信网的拼接覆盖模式不同，天基激光网络由于轨道高度较高，对低轨卫星形成多重覆盖。因此用户在接入时需要根据某种原则从多个可见接入节点中做出合理的选择。
4) 激光链路的单址特性和发散角小的特点使其不具备广播功能，这对于由控制中心进行链路统一调度的离线集中式调度算法不会产生影响，但对于在线调度算法，要实现激光链路的自动建立和调度算法的自主运行，在链路建立之前必须要进行必要的握手通信和可见用户任务信息的收集，该工作可由具备广播能力的低速率微波链路实现。在后续的算法讨论中，假设天基激光网络中的所有节点均具备支持算法实现的微波链路。
3 接入调度算法
为实现天基激光网络中任务的在线调度，受地面蜂窝移动通信网中的呼叫接入控制思想[19]启发，引入了排队模型，任务发起后选择一个可见的骨干网节点加入其等待队列，避免了控制中心集中规划计算的环节。为实现这一过程，将接入调度问题分为链路调度子问题和接入选择子问题。
3.1 链路调度算法
设网络中存在实时与非实时两种任务类型，由于激光接入链路为单址链路，一个接入节点上的实时与非实时任务需要共用一个唯一的信道，属于单服务台排队系统。为保证不同任务的不同要求，必须要采用合理的调度策略。
采用具有抢占优先权的链路调度策略，调度模型如图2所示。对于非实时任务，采用排队模型进行处理：任务接入某一骨干网节点后，进入队列等待接受服务，若
则任务服务失败，需重新发起接入请求。式中 Tc(t) 为当前时刻接入节点对用户的剩余覆盖时间，Tw(t) 为任务从当前时刻到被执行时刻所需要的等待时间，Ts 为任务执行所需的时间。(1)式的含义为：如果不能在可见时段内完成整个任务，则该任务将被从该队列中删除，并重新选择接入节点进行排队。该策略保证了非实时任务能在一个接入节点上完成传输，避免了正在传输时因为不满足可见时间窗口约束而发生中断的情况。
对于实时任务，任务发起后不允许等待，因此应赋予其抢占优先权，即任务到达后不参加排队等待，而是选择那些正在服务非实时任务的接入节点，并抢占其链路资源。若所有可见节点都正在服务实时任务，则没有资源可以抢占，接入请求被阻塞。为保证实时性，实时任务在接入时不受(1)式的约束，如果传输过程中当前节点不再可见，则需要从当前节点向其他节点切换。
3.2 接入点选择算法
在OCSA算法中，用户接入哪个骨干网节点由控制中心统一安排调度，而在ODSA中，用户需自主做出接入选择。通常采用的接入选择算法有距离优先算法、覆盖时间优先算法、仰角加权的覆盖时间优先算法[20]等。距离优先算法根据信号平均功率强度，在距离最近的卫星上寻找空闲信道；覆盖时间优先算法在呼叫建立时选取对当前呼叫覆盖时间最长的卫星优先接入，仰角加权的覆盖时间优先算法通过对覆盖时间、卫星仰角2个变量分别加权计算得到目标函数，作为多星选择的依据。这些算法主要针对近似拼接覆盖的低轨卫星星座，结合天基激光网络多重覆盖的特点，在这些算法的基础上提出了覆盖时间与队列长度相给合的接入选择算法。
设天基激光网络对用户的平均覆盖重数(即在任务发起时刻，用户卫星的平均可见骨干网节点数)为 Z ，覆盖时间为 T(i)c ，骨干网节点上的队列长度为 L(i)q ，其中 i = 1,2,?,Z 为接入节点序号。对于非实时任务，接入选择的目标函数 fN(Tc,Lq) 需满足
上述约束条件保证：1) 用户会选择覆盖时间长的卫星接入，从而减少任务因不满足时间窗口约束而重新发起的频率；2) 用户会选择队列长度小的卫星接入，从而降低自身的等待时延并实现骨干网节点间的负载均衡。考虑到非实时任务不允许在执行过程中发生接入节点间的切换，在接入选择时应保证覆盖时间大于任务执行所需时间，接入选择算法可描述为
式中 is 为被选择的接入节点。若在任务发起时所有可见接入节点上队列均已满，则接入请求被阻塞。
对于实时任务，由于具有抢占优先级，目标函数 fR(Tc) 不需要考虑队列长度的影响，当
实时任务允许发生节点间切换，接入时不需要考虑覆盖时间是否大于任务执行时间，接入选择算法可描述为
在任务发起或发生切换时，若所有可见接入节点都正在服务实时任务，则接入请求被阻塞。
4 算法性能分析
4.1 ODSA的性能分析
4.1.1 任务服务时间
设 TCR 为实时任务的持续时间，为分析方便，假设 TCR 服从期望 E(TCR) =1 μCR 的负指数分布；设 TCN 为非实时任务的持续时间，服从 E(TCN) =1 μCN 的负指数分布；设 Tc 为接入时骨干网节点对用户卫星的覆盖时长，服从 E(Tc) =1 μc 的负指数分布。
对于正在接受服务的实时任务，将一直占用链路直至服务完成或者因为与接入节点不再可见而切换至另一个节点。因此，实时任务在一个接入节点上的服务时间 TR 是 TCR 与 Tc 中的最小值。由于 TCR 与 Tc 相互独立，由指数分布的无记忆性可知，TR 也服从指数分布，期望为
对于未被实时任务抢占的非实时任务，它将一直占用链路直至服务完成，或者因为不能在当前链路上完成任务而被拒绝，因此，非实时任务在一个接入节点上的服务时间 TN 与 TCN 相同：
4.1.2 各种任务的到达过程
设整个网络中实时与非实时任务的到达过程是强度分别为 λOR′、λON′的泊松分布，并且位置分布是均匀的，骨干网节点总数为 M ，则对于单个接入节点，任务到达过程服从 λOR = λOR′ M 和 λON = λON′ M 的泊松分布。
对于实时任务，如果服务时间比覆盖时间长，则会向临近接入节点提出切换请求。假设天基激光网络中所有接入节点均相同，则对于任意接入节点来说，单位时间内进入该节点的切换请求平均数等于离开该节点的切换请求平均数。令 λHR 表示切换任务的到达强度，易得
式中 E(CR) 为链路上实时任务的占用率。
对于非实时任务，如果队列中排队等待的任务在接受服务之前离开了接入节点的可见范围，则该任务向其他节点重新发起接入请求，即被转移到其他接入节点。对于任意接入节点，设从其他节点转移过来的非实时任务到达强度为 λTN ，易得
式中 Lq 是队列平均长度。这里假设上述两种到达过程均服从泊松分布。
4.1.3 二维马尔可夫分析模型
利用非负整数对 v = (i,j) 表示接入节点的状态，i 表示系统中实时任务数，j 表示系统中非实时任务数（包括正在排队的任务和正在接受服务的任务），则 (i,j) 是一个二维马尔可夫链，状态空间 V 为
式中，QD 为队列容量。
在ODSA算法中，系统的状态转移由以下事件驱动：1) 新发起的非实时任务到达；2) 由其他节点转移到该节点的非实时任务到达；3) 新发起的实时任务到达；4) 切换到该节点的实时任务到达；5) 非实时任务离开；6) 实时任务离开。值得注意的是，3) 和4) 事件可能会引起非实时任务的中断，被中断的非实时任务返回到队列中进行等待。
为方便起见，做如下定义:
则系统的状态转移图如图3所示：
针对每个状态，根据流入速率等于流出速率的原则可以得到一个稳态时的平衡方程，这样共可得到2QD + 1个方程。其中，任一方程都可以由其他 2QD 个表示，任意去掉其中一个可得到 2QD 个不相关的方程。另有状态概率归一化条件：
4.2 OCSA的性能分析
为便于对比ODSA与OCSA算法的性能，将时延与阻塞率的概念引入到OCSA算法中。建立OCSA算法时延与阻塞率分析模型如下：
设OCSA算法的调度周期为 T ，任务到达过程服从参数为 λ的泊松分布。算法在每个调度周期的开始时刻收集上一个周期内发起的任务信息并计算生成调度表，然后开始按调度表执行这些任务，如图4所示。
图中 tk 为任务 k 发起与上一任务发起的时间间隔，服从1 λ的负指数分布。由上述分析可知，任务的等待时延 Td 由两部分构成，即任务发起时刻到控制中心开始计算调度表时的等待时间 Td1 和调度计算完成到该任务被执行的等待时间 Td2 。为便于计算，将模型作简化：Td = Td1 。令 n = λT 为一个调度周期内平均到达的任务总数，则当 n μ < T ，即 λ ≤ μ 时，所有任务均能在一个调度周期内完成；否则只能为 nmax = μT 个任务安排调度，因此OCSA算法的时延与阻塞率分别为
可见，OCSA算法中由于调度周期 T 的存在，任务平均等待时延大大增加，T 一般为小时量级，则等待时间也为小时量级，基本不具备实时性。
5 仿真及结果分析
5.1 仿真场景
采用27颗骨干网卫星、多颗低轨用户卫星的场景开展仿真实验，假设每颗卫星上均载有一个激光接入链路和用于传递握手信息的低速率微波链路。其中骨干网卫星包括由24颗中轨卫星构成的导航星座和由均匀分布在同步轨道上的3颗地球同步卫星构成的中继卫星星座，轨道参数如表1所示。利用轨道计算软件计算并统计得到覆盖重数 Z = 8 ，平均可见时间段长度 E(Tc) =1 μc = 1800 s 。
设实时与非实时任务的平均执行时间均为10 min，即 E(TCR) =1 μCR = 600 s ，E(TCN) =1 μCN = 600 s ，接入节点上队列容量 QD = 30 ，离线集中式算法调度周期 T = 1 h 。另外，定义 ρR = λOR E(TCR) 、ρN = λON E(TCN) (单位为erl，erl是话务量的单位，话务量为呼叫次数与每次呼叫的平均占用时长的乘积)分别为到达某一接入点的实时与非实时业务强度，ρ = ρR + ρN 为总业务强度。
图5和图6分别给出了平均队列长度和平均等待时延随总业务强度的变化曲线。从图中可以看出，非实时任务在任务发起后平均等待不到半小时的时间就可得到服务。另外，当业务强度增加时，队列长度和等待时延均随之增加，其中，业务强度中实时业务的成分越高，队列长度和非实时任务的等待时延就越大。
这是由实时业务具有抢占优先级造成的，当实时业务增加时，网络中更多的接入节点被抢占，从而导致非实时任务的等待时延变长。
图7给出了网络中实时任务和非实时任务的阻塞率随业务强度的变化曲线。图中显示，两种类型任务的阻塞率均随业务强度的增强而增加，其中实时任务阻塞率在0.1左右，明显大于非实时任务的阻塞率。因为实时任务不参加排队，要么被服务、要么被阻塞，因此更易被阻塞；但实时任务具有抢占优先权，因此受非实时任务强度的影响较小，阻塞率曲线与非实时任务相比更为平缓。
为了突出在线分布式调度算法在实时性上的优势，分析了离线集中式算法的性能分析模型并将二者进行对比，图 8和图 9分别给出了时延和阻塞率的对比结果。结果显示，ODSA算法将任务等待时延降低了10%以上，阻塞率降低了90%以上。仿真场景中OCSA算法调度周期设置为1 h，从实际操作的角度考虑，这已经是非常高的调度频率了，实际应用中调度周期可能会更长，任务等待接受服务的时间也将大幅增加，此时在线分布式算法的优势也就更明显。
6 结 论
针对离线集中式卫星资源调度算法不能有效适应未来天基激光网络任务与资源动态变化和不能满足任务高实时性的问题，提出了在线分布式接入调度算法。算法利用排队模型有效解决了在线接入调度问题，与传统的离线集中式算法相比，该算法避免了周期性的计算任务调度表，提高了任务调度效率，将任务等待时延缩减10%，阻塞率降低90%；该模型引入了实时与非实时两种不同的任务类型，通过赋予实时任务抢占优先权，使其能够在发起后马上得到服务，保证了实时性。在线分布式调度算法提高了用户接入调度的灵活性和实效性，对未来天基激光网络建设具有重要意义。下一步的研究将考虑引入调度优化机制，进一步优化任务等待时延，提高网络资源利用率。
参 考 文 献
1 R J Cesarone, D S Abraham, S Shambayati, et al.. Deep-space optical communications[C]. ICSOS, 2011: 410-423.
2 Zhao Shanghong, Wu Jili, Li Yongjun, et al.. Present status and developing trends of satellite laser communication[J]. Laser & Optoelectronics Progress, 2011, 48(9): 092801.
赵尚弘, 吴继礼, 李勇军, 等. 卫星激光通信现状与发展趋势[J]. 激光与光电子学进展, 2011, 48(9): 092801.
3 Zhang Zhen, Sun Jianfeng, Lu Bin, et al.. Costas optical phase lock loop system design in inter- orbit coherent laser communication[J]. Chinese J Lasers, 2015, 42(8): 0805006.
张 震, 孙剑锋, 卢 斌, 等. 星间相干激光通信中科斯塔斯锁相系统设计[J]. 中国激光, 2015, 42(8): 0805006.
4 S Chan, V W S Chan. Constellation topologies for a space-based information network backbone using optical intersatellite links[C]. MILCOM, 2004: 812-821.
5 Zhao Xin, Song Yansong, Tong Shoufeng, et al.. Dynamic demonstration experiment of acquisition, pointing and tracking system in space laser communications[J]. Chinese J Lasers, 2014, 41(3): 0305005.
赵 馨, 宋延嵩, 佟首峰, 等. 空间激光通信捕获、对准、跟踪系统动态演示实验[J]. 中国激光, 2014, 41(3): 0305005.
6 Jiang Huilin, Jiang Lun, Song Yansong, et al.. Research of optical and APT technology in one- point to multi- point simultaneous space laser communication system[J]. Chinese J Lasers, 2014, 42(4): 0405008.
姜会林, 江 伦, 宋延嵩, 等. 一点对多点同时空间激光通信光学跟瞄技术研究[J]. 中国激光, 2015, 42(4): 0405008.
7 T Hanada, S Yamakawa, H Kohata. Study of optical inter-orbit communication technology for nest generation space data relay satellite[C]. SPIE, 2011, 7923: 792308.
8 K Bohmer, M Gregory, F Heine, et al.. Laser communication terminals for the European data relay system[C]. SPIE, 2012,8246: 82460D.
9 Chang Qing, Li Xianxu, He Shanbao. Confer on the evolution of earth-space integrated information network of China[J].Journal of Telemetry, Tracking and Command, 2015, 36(1): 1-10.
常 青, 李显旭, 何善宝. 我国空间信息网发展探讨[J]. 遥测遥控, 2015, 36(1): 1-10.
10 Zhou Hongbin, Xiao Yongwei, Lu Shan. Development and enlightenment of integrated space-based information system[J].Radio Engineering, 2015, 45(4): 12-15.
周红彬, 肖永伟, 卢 山. 天基信息系统一体化发展与启示[J]. 无线电工程, 2015, 45(4): 12-15.
11 D Stottler. Satellite communication scheduling, optimization, and deconfliction using artificial intelligence techniques[C].AIAA Infotech@Aerospace, 2010: 1-9.
12 Chen Lijiang, Wu Xiaoyue, Li Yunfeng. Scheduling algorithm for relaying satellite based on temporal flexibility[J].Aeronautical Computing Technique, 2006, 36(4): 48-51.
陈理江, 武小悦, 李云峰. 基于时间灵活度的中继卫星调度算法[J]. 航空计算技术, 2006, 36(4): 48-51.
13 S Rojanasoonthon, J Bard. A GRASP for parallel machine scheduling with time windows[J]. Journal on Computing, 2005,17(1): 32-51.
14 Zhao Jing, Zhao Weihu, Li Yongjun, et al.. Multi-objective resources scheduling algorithm for microwave and laser hybrid links data relay satellite based on improved NSGA-II algorithm[J]. Chinese J Lasers, 2013, 40(12): 1205003.
赵 静, 赵卫虎, 李勇军, 等. 基于改进NSGA-II算法的微波/光混合链路中继卫星多目标资源调度算法[J]. 中国激光, 2013,40(12): 1205003.
15 Zhao Jing, Zhao Weihu, Li Yongjun, et al.. Schdeuling algorithm for data relay satellite with microwave and laser hybrid links [J]. Chinese J Lasers, 2013, 40(10): 1005005.
赵 静, 赵卫虎, 李勇军, 等. 微波/光混合链路数据中继卫星系统资源调度算法[J]. 中国激光, 2013, 40(10): 1005005.
16 Zhao Weihu, Zhao Jing, Zhao Shanghong, et al.. Resources scheduling for data relay satellite with microwave and optical hybrid links based on improved niche genetic algorithm[J]. Optik, 2014, 125(13): 3370-3375.
17 Zhao Jing, Zhao Weihu, Li Yongjun, et al.. Resources scheduling of data relay satellite with microwave and laser links based on adaptive niche genetic algorithms[J]. Journal of Optoelectronics·Laser, 2014, (1): 76-81.
赵 静, 赵卫虎, 李勇军, 等. 基于改进小生境遗传算法的微波/光混合链路中继卫星资源调度方法[J]. 光电子·激光, 2014, (1):76-81.
18 Zhao Weihu, Zhao Jing, Zhao Shanghong, et al.. Dynamic schdeuling fast heuristic algorithm for data relay satellite with microwave and laser hybrid links[J]. Chinese J Lasers, 2014, 41(9): 0905007.
赵卫虎, 赵 静, 赵尚弘, 等. 微波与激光混合链路中继卫星动态调度快速启发式算法[J]. 中国激光, 2014, 41(9): 0905007.
19 Gong Wenbin, Gan Zhongmin. Call admission control scheme in voice/data integration mobile communication system[J].Journal of China Institute of Communications, 2004, 25(3): 18-25.
龚文斌, 甘仲民. 多业务移动通信系统中的呼叫接入控制[J]. 通信学报, 2004, 25(3): 18-25.
20 Zhang Huatao, Sun Fuchun, Xu Fanjiang. Studies on access strategy of layered satellite networks[J]. Computer Engineering and Design, 2005, 26(5): 1121-1124.
张华涛, 孙富春, 徐帆江. 分层卫星网络中的接入策略研究[J]. 计算机工程与设计, 2005, 26(5): 1121-1124.