基于动态规划思想的天基卫星网络路由优化策略研究

基于动态规划思想的天基卫星网络路由优化策略研究汤绍勋1易先清2冯明月3(1．国防科技大学信息系统与管理学院重点实验室二室,湖南省长沙市410073；2．国防科技大学信息系统与管理学院重点实验室二室,湖南省长沙市410073；3．国防科技大学信息系统与管理学院重点实验室二室,湖南省长沙市410073）联系作者e-mail:[e-mail]摘要:基于“离线”式计算的卫星网络路由算法中，卫星节点的动态运动导致路由的频繁变更，新路径的建立以及旧路径的释放和删除会增加许多额外的信令开销，消耗了一部分有限的星座网络资源；另外，它也将会引起相应卫星节点业务流量负荷的突然变化，如果这种突变导致某卫星节点超载，则连接的服务质量急剧降低，流量控制也很复杂，还会引起抖动的问题。基于动态规划思想的卫星网络路由优化策略，充分利用星座网络运行的周期性和规律性，以牺牲一定的通信时延为代价，能够大大降低了星座网络运行过程中的路径切换频率和时延的抖动。关键词:卫星网络；路由切换；优化策略中图法分类号:TP393文献标识码:AResearchonsatellitenetworksroutingoptimizedstrategybasedondynamicprogrammingideologyTANGShao-xun1YIXian-qing2FENGMing-yue3（1．DepartmentofManagementScienceandEngineeringSchoolofInformationSystemandManagement,NationalUniversityofDefenseTechnology,410073,China;2．DepartmentofManagementScienceandEngineeringSchoolofInformationSystemandManagement,NationalUniversityofDefenseTechnology,410073,China;3．DepartmentofManagementScienceandEngineeringSchoolofInformationSystemandManagement,NationalUniversityofDefenseTechnology,410073,China）Abstract:Intheroutingalgorithmbasedon“offline”computeinthesatellitenetworks,themovementofsatelliteresultsinroutingfrequentlychanging,foundingnewpathsanddeleteoldpathswillincreasemuchextrasignalcontrolspendingandconsumesomenetworksresources.Inaddition,itwillbringsuddenlychangesintheoperationflows,ifthechangesresultinnodeoverloading,thequalityofservicewillrapidlydrop,flowcontrolbecomecomplex,andsoon.Consideringperiodicityandforeseeofsatellitenetwork,theroutingalgorithmcanbeoptimizedapplyingtheideologyofdynamicprogramming.Androutinghandoffanddelayjitterdramaticallydecreaseinthecourseofdatatransmissionafterapplyingit.Keywords:satellitenetworks,routinghandoff,optimizedstrategies收稿日期：2006-12-00；修订日期：2006-12-00作者简介:汤绍勋((1980.8—),男,湖南宁乡人,硕士,主要研究方向：指挥自动化系统、信息支持与辅助决策；易先清(1966—),男,湖南常德人,副教授,博士,主要研究方向：指挥自动化系统.1卫星网络中路径切换优化问题的提出基于“离线”式计算的卫星网络路由算法中，卫星节点的动态运动导致路由的频繁变更，新路径的建立以及旧路径的释放和删除会增加许多额外的信令开销，消耗了一部分有限的星座网络资源；另外，它也将会引起相应卫星节点业务流量负荷的突然变化，如果这种突变导致某卫星节点超载，则连接的服务质量急剧降低，流量控制也很复杂，还会引起抖动的问题。因此，如何选择一条持续时间较长或者说切换率较低的路径，成为我们关注的一个问题。可以基于这样的考虑：根据星座运行时变规律，将动态变化的星座拓扑离散化为一系列静态的拓扑快照，并且为每个快照周期的源节点和目的节点找到一个最佳路径集合。即每个离散时刻除选出第一最佳路由外，还可以选出第二、第三甚至第四最佳路由，每一后续路由都是将前面已选出的路由排除在外后选出的，每一时刻实际选出的用于通信的路由并非都是第一最佳路由，而是按照一定的优化方法从多个最佳路由中选取，从而达到降低切换率以及通信时延的目标。表1是某一时刻t，卫星节点0和卫星节点15之间的路径选择情况。表1卫星节点0和卫星节点15之间的路径选择情况。快照i（t时刻）快照（i+1）快照（i+2）快照（i+3）path10-1-150-14-150-14-150-14-15path20-14-150-1-150-1-150-20-15path30-13-14-20-150-13-14-20-150-20-150-1-15优化前path1path1path1path1优化（一）path1path2path2path3优化（二）path2path1path1path1表1是节点0与节点15之间在第i个快照周期及其以后3个快照周期内的星间链路情况，源节点与目的节点每步（即每个快照周期）选出三条最佳路径，从表中可以清楚地看出优化前后路由选择情况的变化。如果在数据传输的每个快照周期内，路由选择不作优化，即所有快照周期都选择第一最佳路由用于实际通信，则第i快照与第i+1快照之间需要进行一次链路切换，即由经过节点1切换为经过节点14；而优化后（两种优化算法）不必进行链路切换，在连续的4个快照周期内，源节点0直接经过节点1或节点14到达目的节点15。2基于动态规划思想的优化策略如何从整个系统周期或者连续几个快照周期来考虑选择一条路径切换频数较低且通信（如时延）代价不是太大的最优路径，是整个优化策略的核心。可以作这样的假设：每个快照周期代表着一个阶段k，快照周期内某条备选路径代表某个阶段的某一状态kS，最佳路径集合代表某个阶段可能的状态集合()kkDS。因此，路径优化的问题可转化成为一个多阶段决策的过程，可以采用动态规划的思想来进行优化。本节将运用这种优化思想对卫星网络中的路由优化问题作了初步的探索和研究。（1）阶段的划分把所给问题的过程，恰当的分为若干联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策的过程。本文根据星座运行的周期性和规律性来进行阶段的划分，认为每个快照周期就是代表的一个阶段。如图3-10所示，快照i代表第一阶段，k=1。（2）状态的定义状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称为不可控因素。描述过程状态的变量程为状态变量，它可用一个数、一组数或一个向量来描述。常用Sk表示k阶段的状态变量。在文中，一个状态就是某个快照周期的一条可选路径，如图3-10，在第i个快照周期中选出了三条备选路径，表示第一阶段有三个状态A1、A2和A3，1123{,,}SAAA。为了计算方便，图中还增加了起点和终点两个虚状态S、D，它不代表任何含义。（3）决策与决策变量决策表示当过程处于某个阶段的某个状态时，可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，它可用一个数、一组数或一个向量来描述。常用()kkus来表示第k阶段当状态处于ks的决策变量。在实际问题中，决策变量的取值往往限制在某一范围内，此范围称之为允许决策集合。常用()kkDs表示第k阶段从状态ks出发的允许决策集合，显然有()()kkkkusDS。如图3-10，在第i+1个快照中，即第二阶段，若从状态B1出发，就可做出三种不同的决策，即其允许决策集合21123(),,DBCCC，若选取的点为2C，则2C是状态1B在决策21()uB作用下的一个新的状态，记作212()uBC。（4）策略策略是按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的k子过程。由每段决策按顺序排列组成的决策序列11(),(),,()kkkknnusususLL称为k子过程策略，简称子策略，记为,()knkPs。即：,11()(),(),,()knkkkkknnPsusususLL。当k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为1,1()nPs。即：1,11122()(),(),,()nnnPsusususLL。在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，从允许策略集合中找出达到最优效果的策略称为最优策略。（5）状态转移方程状态转移方程是确立过程由一个状态到另一个状态的演变过程。若给定k阶段状态变量ks的值，如果该阶段决策变量ku一经确定，第k+1阶段的状态变量(1)ks的值也就完全确定。如例中，状态转移方程为(1)()kkksus。（6）指标函数和最优值函数指标函数是用来衡量所实现过程优劣的一种数量指标。常用,knV表示。常用的指标函数有和形式与积形式，本例中采用和形式，过程的指标是它所包含的各阶段的指标的和。即：,1,1(,,,)(,)nknkkkniiiikVsussvsuL1(,)kkkdss表示第k阶段由状态ks至第k+1阶段状态1ks的阶段指标值，即“距离”；指标函数,knV就表示在第k阶段由状态ks至第n阶段终点状态的过程指标和。在不同的问题中，指标函数的定义也不同，它可以是距离、利润、成本，产品的产量或资源消耗等。在本文提出的问题中，由于我们主要是要降低路径的切换率，因此，应把切换频数作为主要指标，我们考虑相邻快照周期里所选择的路径是否相同，即是否需要切换，若不相同则定义这两种状态之间的指标值（即“距离”）为0，否则定义为1。指标函数的最优值，称为最优值函数，记为()kkfs，表示从第k阶段的状态ks开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即：,1,1()((,,,))kkknkkknfsoptVsussL3优化计算过程与结果分析依据如前所述的假设和定义，多快照动态拓扑结构的星座网络路由优化问题转化成一个用动态规划方法求解最短路线的问题。一、优化计算过程首先，将表1转化为网络图的形式，如图1所示。根据前面的假设以及定义，增加起点和终点两个虚拟状态以便于计算，并标出各相邻状态之间的指标值，假设起点至各邻状态之间以及终点与各邻状态之间的指标值均定义为0。快快i(k=2)快快快i+1快(k=3)快快快i+2快(k=4)快快快快快快快快快快快快快快快快快快快快S快快G0001010110110011101110001111111001A2A3A3B2B1B1C2C3C3D2D1D快快快快(k=1)快快快i+3快(k=5)图1星座网络路由优化的网络图下面按照动态规划的方法，进行优化计算：当k=5时，由1D至终点G只有一条路径，故51()0fD。同理，52()0fD，53()0fD。当k=4时，出发点有1C、