一种基于sdn与ndn的卫星网络多约束路由方法
技术领域
1.本发明涉及卫星通信网络技术领域，具体涉及一种基于sdn与ndn的卫星网络多约束路由方法。
背景技术：
2.近年来，随着空间技术的飞速发展，卫星网络已成为全球通信的重要组成部分。路由协议作为卫星网络通信协议的核心，在提高卫星网络数据传输效率和可靠性方面意义重大。同时，用户对视频、语音等多媒体内容的需求飞速增长，而基于ip的卫星网络在内容传输上存在固有缺陷，即“身份-位置”的绑定使网内重复传输大量相同内容，极大浪费星上带宽资源。因此，在卫星网络环境中，需要一种新型的网络架构来克服上述问题。
3.命名数据网络(ndn，named data )作为以数据为中心的未来网络架构，将内容与位置解耦，并支持网络内缓存，极大地缓解了传统tcp/ip网络所存在的传输效率问题。ndn现有的转发方法在拓扑结构稳定的场景下具有一定优势。wang l等人提出基于ospf的命名数据网络路由协议，通过洪泛来分发路由消息，实现内容分发。zhang l通过周期性广播链路状态信息创建网络拓扑并进行包的分发，利用逐跳转发代替基于ospf的周期性前缀公告泛洪。在卫星网络拓扑高动态变化的环境下，已有的静态映射和泛洪路由或基于链路状态广播的路由机制都难以适用，因为存在以下问题：1)兴趣包的频繁广播或多播将导致多个数据源重复回应请求，造成数据的冗余传输。2)卫星链路频繁中断导致数据包可能无法按照兴趣包的传输路径反向回传。
4.针对上述问题，国内外许多研究人员都展开了研究。hasan ma islam等人针对ndn在频繁中断环境下数据包无法及时得到回复而重发的问题，将ndn与dtn相结合以解决ndn无法适应频繁中断的问题。刘迪等人根据可预知的卫星链路切换状态，以时变图的方式进行建模，动态计算时间相关的最快路径实现包的传输，但其只考虑单个目标优化，而且联络拓扑时变性大使得路由效率较低。zhou y等人根据卫星间连接计划采用连接图路由计算方法制定数据包转发路径，并采用最优及次优两条路径同时转发，但其动态性差且对卫星节点要求较高。
技术实现要素：
5.针对上述问题，本发明提出一种基于sdn与ndn的卫星网络多约束路由方法( multi- ，)，其基于sdn集中控制并利用改进的蚁群算法获取满足时延、带宽和丢包率多约束的代价最小路径，实现包的高效传输。
6.为实现上述目的蚁群算法最短路径java，本技术提出一种基于sdn与ndn的卫星网络多约束路由方法，包括：
7.基于sdn的多约束路由动态构建fib与pit表；
8.根据卫星网络链路多约束信息建立多约束路由模型；
9.结合所述链路多约束信息对蚁群算法进行改进，防止陷入局部最优解；
10.利用改进后的蚁群算法对所述多约束路由模型进行求解。
11.进一步的，动态构建fib表，具体为：
12.当卫星节点收到兴趣包后，首先查找内容缓存表cs，若在该表中获取到命中内容，则将包含所述命中内容的数据包按原路返回，此时用户请求得到满足；否则，查找请求状态表pit，若该表中存在此兴趣包内容的pit条目，则添加进入接口信息到相应条目；否则，继续查找转发表fib，若在该表中找到此兴趣包内容转发接口信息，则按照所述接口信息进行转发；否则，将兴趣包转发到geo卫星控制器，该控制器根据解析出的内容名获取内容源卫星节点，并根据当前全局网络状态信息执行多约束路由计算兴趣包的最优转发路径，下发流表给相应的leo卫星完成转发；否则，将兴趣包回溯或者丢弃。
13.进一步的，动态构建pit表，具体为：
14.当网络拓扑稳定时，若有数据包满足对应的兴趣包，则其会沿着兴趣包的反向路径传输。但卫星网络拓扑动态变化，数据包在返回之前兴趣包传输路径的反向路径可能已经不存在。因此，需动态构建pit表。
15.当卫星节点收到数据包后，首先查看内容缓存表cs中是否存在此数据包，若存在则丢弃该数据包；否则，查找请求状态表pit，若该表中记录的兴趣包入口链路仍然有效，则按照请求状态表pit完成数据包的转发与缓存；否则，向geo卫星控制器请求执行多约束路由计算数据包的最优转发路径；若计算成功，则leo卫星节点按照流表转发数据包，并按照相应的缓存策略进行缓存；否则蚁群算法最短路径java，节点向上反馈否定确认nack( )报文通知发送节点重传。
16.进一步的，根据卫星网络链路多约束信息建立多约束路由模型，具体为：
17.获取通信时延、剩余可用带宽、丢包率；所述通信时延dealy(p(s,d))为路径传输时延与节点排队时延之和；剩余可用带宽ban(k,l)为链路总带宽与已用带宽之差，属于凹性参数；丢包率loss(p(s,d))为传输数据包中丢失的数量占总数量的比值，属于可乘性参数；
18.定义最优路径的评判指标为路径代价cost(k,l)，即通信时延、剩余可用带宽、丢包率的加权之和；
19.建立满足通信时延、剩余可用带宽、丢包率要求的路径代价最小的多约束路由模型。
20.进一步的，结合所述链路多约束信息对蚁群算法进行改进，防止陷入局部最优解，具体为：
21.基于先验知识与概率驱动的蚂蚁状态转移规则得到蚂蚁下一条转发节点l；
22.获取当前迭代的路径代价值cost
(k,l)
(t)，并更新链路信息素；当所选链路属于当前循环最优路径，则信息素增量δτ
(k,l)
(t)＝ρ
·
[1/cost
(k,l)
(t)]，ρ为信息素挥发因子；当所选路径代价越小时，该路径上的信息素浓度增加越多，从而启发更多的蚂蚁选择该条路径；同时，为避免信息素浓度过高或过低导致算法过早陷入局部最优或停滞搜索，本发明中将各条寻优路径上的信息素量限制在[τ
min
,τ
max
]范围内，当超出这个范围时，信息素量被强制限定为τ
min
或τ
max
。
[0023]
进一步的，利用改进后的蚁群算法对所述多约束路由模型进行求解，具体为：
[0024]
删除网络中不满足多约束条件的链路，得到一个新的网络拓扑，然后基于新的网络拓扑g(v,e)'开始搜索；
[0025]
将源节点s设置为蚂蚁的当前节点，并加入禁忌表中，设置迭代次数nc＝nc+1；
[0026]
根据蚂蚁状态转移规则和多约束条件选择下一跳节点，并将选择的节点加入禁忌表中；
[0027]
蚂蚁判断当前节点是否为目的节点，若是，则宣布寻路成功，目的节点d根据路径代价cost(p(s,d))选择一条最优路径，将蚂蚁按原路返回，并按照式(10)更新信息素；否则，蚂蚁判断当前节点的precq集合是否为空，若为空，则宣布寻路失败；否则，根据状态转移规则和多约束条件继续选择下一跳节点。
[0028]
本发明采用的以上技术方案，与现有技术相比，具有的优点是：本发明方法基于sdn的集中控制与全局视图，通过建立多约束路由模型，并根据链路多约束信息对基本蚁群算法进行改进，利用改进的蚁群算法对模型进行求解，获得满足通信时延、剩余可用带宽、丢包率多约束的代价最小路径。在ndn包逐跳转发的过程中动态构建fib表和pit表，实现包的高效可靠转发。
附图说明
[0029]
图1为基于sdn的多层卫星网络架构图；
[0030]
图2为基于的fib构建流程图；
[0031]
图3为基于的pit构建流程图；
[0032]
图4为实施例中多约束路由模型中参数α、β设置图；
[0033]
图5为实施例中多约束路由模型中参数ρ设置图；
[0034]
图6为实施例中算法收敛性比较图；
[0035]
图7为实施例中不同路由算法的传输时延对比图；
[0036]
图8为实施例中本发明中算法与aco算法和dsp算法的带宽利用率对比图；
[0037]
图9为实施例中不同路由算法的丢包率对比仿真图；
[0038]
图10为实施例中不同卫星网络架构下在网络环境稳定情况下的请求命中率对比图。
具体实施方式
[0039]
为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本技术，并不用于限定本技术，即所描述的实施例仅仅是本技术一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本技术实施例的组件可以以各种不同的配置来布置和设计。
[0040]
因此，以下对在附图中提供的本技术的实施例的详细描述并非旨在限制要求保护的本技术的范围，而是仅仅表示本技术的选定实施例。基于本技术的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本技术保护的范围。
[0041]
实施例1
[0042]
如图1所示，本发明设计了基于sdn的多层卫星网络架构( based on sdn)。三颗geo卫星作为局部控制器，负责获取leo卫星的实
时状态信息，并对网络进行路由计算与管理；转发层由leo卫星节点组成，负责根据geo卫星下发的流表进行数据传输；地面控制中心作为全局控制器负责集中控制和管理整个卫星网络。本实例提供一种基于sdn与ndn的卫星网络多约束路由方法，包括如下步骤：
[0043]
s1：基于sdn的多约束路由动态构建fib与pit表；
[0044]
具体的，在卫星网络场景下，兴趣包的广播式转发将导致多个数据源重复回应请求，造成数据冗余传输，浪费星上带宽资源。因此，本发明通过将兴趣包转发到geo卫星控制器获取内容源卫星节点，并执行多约束路由计算得到兴趣包的最优转发路径，由此更新/修改fib表；故动态构建fib表过程为：
[0045]
如图2所示，当卫星节点收到兴趣包后，首先查找内容缓存表cs，若在该表中获取到命中内容，则将包含所述命中内容的数据包按原路返回，此时用户请求得到满足；否则，查找请求状态表pit，若该表中存在此兴趣包内容的pit条目，则添加进入接口信息到相应条目；否则，继续查找转发表fib，若在该表中找到此兴趣包内容转发接口信息，则按照所述接口信息进行转发；否则，将兴趣包转发到geo卫星控制器，该控制器根据解析出的内容名获取内容源卫星节点，并根据当前全局网络状态信息执行多约束路由计算兴趣包的最优转发路径，下发流表给相应的leo卫星完成转发；否则，将兴趣包回溯或者丢弃。
[0046]
具体的，卫星网络拓扑动态变化，数据包在返回之前兴趣包转发路径的反向路径可能已经不存在。因此，需要动态构建pit表。由于ndn本地支持内容级别的重路由，因此当pit表需要更新时，仅需通过geo卫星控制器执行路由计算即可。故动态构建pit表过程为：
[0047]
如图3所示，当卫星节点收到数据包后，首先查看内容缓存表cs中是否存在此数据包，若存在则丢弃该数据包；否则，查找请求状态表pit，若该表中记录的兴趣包传输链路存在，则按照请求状态表pit完成数据包的转发与缓存；否则，向geo卫星控制器请求执行多约束路由计算数据包的最优转发路径；若计算成功，则leo卫星节点按照流表转发数据包，并按照相应的缓存策略进行缓存；否则，节点向上反馈否定确认nack( )报文通知发送节点重传。
[0048]
s2：根据卫星网络链路多约束信息建立多约束路由模型；
[0049]
为保证兴趣包和数据包的高效可靠传输，本发明提出一种多约束路由计算方法。首先建立卫星网络多约束模型。将leo卫星系统建模为图g＝(v,e),v为卫星节点集合,e为星间链路集合。(k,l)表示节点k和节点l之间的链路，p(s,d)表示从源节点s到目的节点d的一条路径。
[0050]
s2.1相关定义如下：
[0051]
定义1：通信时延dealy(p(s,d))：表示路径传输时延与节点排队时延之和。其计算公式如下：
0052
其中，dealy
tra
(k,l)为路径的传输时延，dealy
que
(v)为路径中节点排队时延。
[0054]
定义2：剩余可用带宽ban(k,l)：表示链路总带宽与已用带宽之差，属于凹性参数。其计算公式如下：
[0055]
ban(k,l)＝b(k,l)-b
used
(k,l)
ꢀꢀ
(2)
[0056]
其中，b(k,l)表示链路总带宽，b
used
(k,l)表示链路已用带宽。
[0057]
定义3：丢包率loss(p(s,d))：传输数据包中丢失的数量占总数量的比值，属于可乘性参数。其计算公式如下：
0058
其中，loss(k,l)是单位时间内路径p(s,d)中链路(k,l)的丢包率。
[0060]
定义4：路径代价cost(k,l)：为通信时延、可用带宽、丢包率的加权之和。其计算公式如下：
0061
其中，delay(k,l)为链路(k,l)的通信时延，d
min
为当前卫星网络中的最小通信时延；ban
max
为当前卫星网络链路中可用带宽的最大值，ban(k,l)为链路(k,l)的剩余可用带宽；loss(k,l)为链路(k,l)的丢包率，l
min
为当前卫星网络中的最小丢包率；ωi(i＝1,2,3)分别表示时延、可用带宽、丢包率的相对权重，且∑ωi＝1；
[0063]
s2.2多约束路由模型如下：
0064[0066]
其中，d
max
、b
min
、l
max
分别表示传输业务对通信时延、可用带宽、丢包率的约束阈值。
[0067]
s3：结合链路多约束信息对基本蚁群算法进行改进；
[0068]
基本的蚁群算法以寻找最短路径为目标，并且容易陷入局部最优解。本发明将多约束条件与蚁群算法相结合，在寻路过程中充分考虑链路多约束信息以高效求解满足时延、带宽、丢包率多约束的最优路径。
[0069]
s3.1基于先验知识与概率驱动的状态转移规则计算蚂蚁下一跳节点。
[0070]
基本的蚂蚁状态转移规则仅按照概率来选择下一跳节点，算法随机性高，收敛速度慢。因此，本发明采用先验知识选择与概率驱动方式来确定蚂蚁的下一跳移动方向，比基本蚁群算法更好的利用蚂蚁正反馈机制。改进后的蚂蚁状态转移规则如式(7)：
0071[0073]
其中，p为[0,1]内均匀分布的随机数；p0为状态转移因子，如式(8)，n
max
为最大迭
代次数，nc为当前迭代次数。当p≤p0时，利用先验知识采用非随机的搜索方式，即按照信息素与启发式函数乘积最大的节点进行状态转移；当p＞p0时，按照式(9)计算满足约束条件的所有节点的随机转移概率按照概率大的节点进行状态转移。
[0074]
其中，
0075
其中，为蚂蚁q从卫星k转移到卫星l的概率；precq为蚂蚁q等待访问节点集合；τ
(k,l)
(t)为t时刻链路(k,l)上的信息素浓度；α为信息素启发因子，反映转移规则受到信息素浓度的影响程度；η
(k,l)
(t)为t时刻节点k到节点l链路上的启发度，本发明中定义η
(k,l)
(t)＝1/cost
(k,l)
(t)，即路径代价越小对蚂蚁的启发作用越大；β为启发函数因子，反映启发信息对转移规则的影响程度。
[0077]
通过上述改进，在算法迭代初期，p0取值较大，使得节点以大概率选择确定转移，加快了局部最优路径搜索；迭代后期，p0取值较小，以增大随机转移概率，防止陷入局部最优。因此，改进的状态转移规则通过动态调整状态转移因子，使蚂蚁按照不同方式选择下一跳节点，丰富了下一跳节点的可选择性，并防止算法陷入局部最优。
[0078]
s3.2基于多约束链路代价进行信息素更新。
[0079]
基本的信息素更新方式仅考虑单一的路径长度因素，不适用于求解多约束路由路径，因此，本发明将多约束条件与信息素更新方式相结合，使蚁群实时感知路径的时延、带宽和丢包率等参数，指导蚁群及时调整路径搜索策略。因此，改进的信息素更新规则如式(10)所示：
[0080]
τ
(k,l)
(t+1)＝(1-ρ)τ
(k,l)
(t)+δτ
(k,l)
(t)
ꢀꢀ
(10)
0081
其中，cost
(k,l)
(t)为当代最优解蚂蚁的路径代价值，如式(4)。当所选路径代价越小时，该路径上的信息素浓度增加越多，从而启发更多的蚂蚁选择该条路径。同时，为避免信息素浓度过高或过低导致算法过早陷入局部最优或停滞搜索，本发明将各条寻优路径上的信息素量限制在[τ
min
,τ
max
]范围内，当超出这个范围时，信息素量被强制限定为τ
min
或τ
max
，如式(12)所示：
0083
s4：利用改进蚁群算法对模型进行求解；
[0085]
s4.1基于改进的蚁群算法求解最优路径步骤如下：
0086
附表1为仿真场景参数设置，为卫星数目、轨道数、每个轨道卫星数等参数进行了设定。仿真过程中卫星网络通过3颗geo卫星作为控制器来实时控制整个网络，leo卫星采用铱星星座模拟转发层，通过geo卫星控制器收集leo网络中的节点链路信息。图4和图5为模型参数设置，对α、β和ρ做出了设定。
[0088]
表1卫星网络轨道参数
0089
图6为算法收敛性比较。随着蚂蚁数的增加，本发明中算法达到最优解时的迭代次数均少于aco算法。当蚂蚁数为45时蚁群算法最短路径java-一种基于SDN与NDN的卫星网络多约束路由方法，本发明中算法迭代6次左右就收敛到最优解。这是由于本发明中算法改进了基本蚁群优化算法，根据先验知识与概率选择相结合的方式选择下一跳节点，加快了局部最优解的搜索；同时，结合链路多约束信息优化了信息素更新方式，并设置了信息素浓度的上下界，避免算法陷入局部最优或停止搜索。因此，算法的收敛速度较快。
[0091]
图7为仿真模拟了100个静态网络拓扑下的不同路由算法的传输时延对比图。可以看出，本发明中算法的传输时延始小于另外两种算法。具体来说，aco算法和dsp算法的平均传输时延分别为0.10s和0.12s，本发明中算法的平均传输时延为0.076s。当网络负载较大时，由于aco算法和dsp算法仅根据路径距离进行路径选择，容易导致链路拥塞，时延较大。而本发明中算法将时延作为优化目标，更倾向于选择较低时延的链路，因此路径时延性能较好。
[0092]
图8为本发明中算法与aco算法和dsp算法的带宽利用率对比图。当业务请求数小于250时，3种算法的带宽利用率相差不大。当业务请求数超过250之后，aco算法和dsp算法的带宽利用率增大趋势变小。由于aco算法和dsp算法均为基于最短路径算法，优先将数据流路由到一条最短路径。相比之下，本发明中算法带宽利用率性能较好，因为本发明中算法考虑了链路带宽因素，在计算路径时绕过了拥塞的链路，将更多的链路作为路径选择。
[0093]
图9为不同路由算法的丢包率对比仿真图。随着网络负载的增大，3种路由算法的丢包率均逐渐增大；在网络负载较轻时，3种路由算法的丢包率相差不大；随着网络负载的增大，本发明中算法的丢包率增大速率相比aco算法和dsp算法变小，分别降低了26％和17％。这是由于aco算法和dsp算法在搜索最短路径时，不考虑链路丢包率条件，只选择一条距离最短的路径，而这些最短路径上很容易产生网络拥塞，丢包率增大；本发明中算法综合考虑了链路的丢包率，在进行路径选择时更倾向于选择较低丢包率的非阻塞路径，因此丢包率比较小。
[0094]
图10为不同卫星网络架构下在网络环境稳定的情况下的请求命中率的对比图。在sdn卫星网络架构下，由于转发节点不具备缓存功能，并且请求内容的提供者由源节点指定，因此该架构下请求在卫星网络中被命中的概率比较低；而在架构下，转发节点引入缓存功能后充分利用网内节点缓存，有效提高了卫星网络中请求的命中率。但本发明中架构中控制器的全局视图与集中控制，能够更好的利用内容缓存实现内容查找与回传，因此请求的命中率更高。
[0095]
前述对本发明的具体示例性实施方案的描述是为了说明和例证的目的。这些描述并非想将本发明限定为所公开的精确形式，并且很显然，根据上述教导，可以进行很多改变
和变化。对示例性实施例进行选择和描述的目的在于解释本发明的特定原理及其实际应用，从而使得本领域的技术人员能够实现并利用本发明的各种不同的示例性实施方案以及各种不同的选择和改变。本发明的范围意在由权利要求书及其等同形式所限定。
