一种基于随机线性网络编码的卫星网抗毁路由协议

郝选文，马建峰

(1.西安电子科技大学计算机网络与信息安全教育部重点实验室，陕西 西安 710071;2.陕西师范大学计算机科学学院，陕西 西安 710062)

随着航天技术的迅猛发展和快速应用，空间在军事、政治和经济等领域的战略地位日益重要，夺取空间优势成为世界各国发展航天力量的首要任务.发展以卫星系统为核心［1］的空间网络是世界各国发展航天力量的重要任务之一.空间网络作为一种新型的无线网络，易受到伪造、窃听、拒绝服务等攻击.由于路由交换部件担负着星间数据链路的实现、各种数据的安全监测与分发等重任，路由技术是空间网络得以持续、安全运转的关键所在.因此，开展在空间网络环境下的卫星网络的抗毁安全路由交换技术研究是非常必要的.目前国内外专家学者在卫星网络路由方面已经提出了许多算法［1－8］.根据算法的主要特征，现有路由算法可以划分为单层星座路由算法和多层星座路由算法.单层星座路由算法主要针对低轨道卫星构成的系统，比较有影响的单层星座面向连接的路由算法是Gounder提出的基于快照序列的路由［4］和Eylem Ekici提出的分布式路由［5］.多层星座路由算法的研究主要针对中轨道卫星和低轨道卫星两层星座构成的系统，算法多采用主从模式，以中轨道卫星为主干，低轨道卫星为接入卫星.比较有影响的多层星座路由算法是Ian F Akyildiz提出的多层卫星路由MLSR［6］.这些路由算法大多都没有充分考虑卫星节点失效的情况和路由信息的安全性，不能有效应对卫星节点被动失效对整个空间网络造成的影响，也不能有效地抵制路由篡改和伪造等攻击，没有防止路由黑洞、路由重播攻击的功能.针对以上协议的问题提出了一种基于随机线性网络编码的卫星网络抗毁路由协议.

文中以随机线性网络编码为基础，将其与卫星网络的路由协议相结合，提出基于随机线性网络编码的卫星网抗毁路由协议，最后对协议进行仿真分析.

1 GEO-LEO双层卫星网络设计

同步地球轨道卫星GEO(geosynchronous earth orbit，GEO)卫星轨道高，相对地面位置固定，3颗GEO卫星即可实现全球覆盖;低地球轨道卫星LEO(low earth orbit，LEO)的星地时延非常小，适合提供各类实时通信，地面用户使用手持设备即可接入LEO卫星网络.根据对卫星星座特性的研究，我们设计了一种GEO-LEO双层卫星网络.卫星网络由LEO卫星层和GEO卫星层所组成.GEO层包括卫星网络中所有的GEO卫星，轨道内的第i颗GEO卫星用Gi表示;LEO层包括卫星网络中所有的LEO卫星，在GEO卫星Gi覆盖下的第j颗LEO卫星用Lij表示.

卫星同层间的通信通过星间链路ISLs(innersatellite links，ISLs)来完成.在任何给定的时间内，每个LEO卫星通过同层的双向ISLs与它周围最临近的4个卫星链接.GEO卫星也是通过ISLs与相邻的两个卫星通信.GEO和LEO轨道层卫星间的通信通过轨间链路 IOLs(inner-orbital links，IOLs)完成.每个GEO卫星与低于它所在轨道且处在它覆盖区间的LEO卫星通过IOLs联接.用户通过用户数据链路 UDLs(user data links，UDLs)同LEO卫星网络通信，单个卫星能与多重地面用户保持UDLs.当有LEO卫星进入一颗GEO卫星的覆盖区域时，LEO卫星注册到该GEO卫星，这些在同一GEO卫星下的LEO卫星构成一个LEO卫星组，如图1所示.

图1 GEO-LEO双层卫星网络结构示意图

2 基于网络编码的抗毁路由协议

2.1 卫星网络中网络编码的选择

网络编码理论最早由Ahlswede等人［9］开始研究，他们提出，通过使用网络编码，网络的组播能力可以达到组播树的最大流最小割流量，而这种网络吞吐量是常规路由无法达到的.

将网络编码技术引入卫星网络能够有效地节省各种卫星网络资源.在线性网络编码中，首先由源节点启动一个多项式时间算法来确定和分配每个编码点的局部编码向量.这样就带来了许多不便之处.在多项式时间算法中，源节点需要了解整个网络的拓扑结构，确定编码点，能为每一个编码点所在的节点分配局部编码向量.线性网络编码的处理过程决定了它适用于网络拓扑结构稳定的情况.因此，线性网络编码主要适用于网络稳定的有线网络，难以分布式实现，不能适应网络的动态变化.随机线性网络编码不需要预先启动一个算法来分配局部编码向量.其局部编码系数都是从一个有限域中随机选取的.随机线性网络编码的特点决定了它可以适用于网络拓扑动态变化，网络链路变化频繁的卫星网络环境.

2.2 卫星覆盖域分时及相关定义

定义1 卫星覆盖域:在卫星网络运行的不同时刻，每颗卫星覆盖不同地面区域，把地球表面覆盖域划分成不同区域并给各个区域赋予不同的地址编号，该划分区域称为卫星覆盖域.

定义2 LEO卫星时间片:一颗LEO卫星从运行进入一个LEO卫星覆盖域到运行离开该覆盖域的时间称为LEO卫星时间片.定义［tl1，tl2］时间间隔为LEO卫星层时间片，该时间片内LEO卫星层内卫星位置保持相对不变.

将LEO卫星运行周期分为若干个LEO卫星时间片，将动态网络拓扑离散化为一系列静态网络拓扑，星际链路长度和通断仅在每个LEO卫星时间片的开始时刻发生改变.通过设立LEO卫星时间片，从LEO卫星真实位置的动态变化到与LEO卫星覆盖域相对静止的转化，屏蔽了LEO卫星星座的动态性.

定义3 LEO卫星网络虚拟拓扑图:根据LEO卫星星座运行的可预测性和周期性，在每一个时间片内，网络都可以被预先模型化为一个静态的加权无向图＜Gk=(L，N)＞，L为所有星间链路ISLs的集合，N为所有LEO卫星节点的集合，称该图为LEO卫星网络的虚拟拓扑图.

定义4 切换表:对于LEO节点Lij，定义切换表记录LEO卫星Lij的路由表切换时间，表项格式为＜STime，Num＞，其中 STime为切换时刻，Num为路由表编号.

2.3 密钥管理

2.3.1 密钥初始化

由 GEO 卫星生成一个 5 元组(e，G1，G2，g，p)，其中e为一个可计算的双线性映射e:G1×G1→G2，G1，G2为两个有着相同素数阶为p的乘法循环群.g是G1的生成器;选择随机的SK∈Zp作为私钥，计算PK=gSK作为公钥.

每颗LEO卫星在加入到一个GEO/LEO卫星组之前，首先需要通过GEO卫星的身份认证，经过认证后，在每个 LEO卫星时间片［tl1，tl2］周期起始STime，GEO卫星为覆盖其下的所以LEO卫星生成和分发密钥.

2.3.2 同态签名

LEO卫星路由发起过程中的签名以及中继LEO卫星节点和目的LEO卫星节点的签名验证采用罗海等［10］提出的网络编码同态签名方案.

2.4 LEO卫星单步邻接表

LEO层卫星维护一张单步邻接表，该单步邻接表如图2所示，用来记录该LEO卫星节点的同层一跳邻居LEO卫星节点的信息;每经过［tl1，tl2］时间间隔，LEO卫星节点向其他LEO卫星节点广播一条HELLO消息，当一个节点收到此消息后，更新其单步邻接表.

图2 单步邻接表示意图

在LEO卫星时间片初始对邻接表进行更新，可以实时保存LEO卫星局部虚拟拓扑信息.

2.5 报文格式

报文格式设计［11］如图3所示.

图3 报文格式

报文格式含义如下:MTime:报文产生时间，用于验证报文的新鲜性.SIP:发起路由请求的节点的IP地址.TIP:路由请求的目的IP地址.Step:LEO卫星跳数，通过LEO卫星的单步邻接表可以进行判断;当通信发生在一个LEO卫星的覆盖区域内，不需要路由，不需要进行网络编码，Step设置为0;当通信发生在两个邻接的LEO卫星的覆盖区域内，需要路由，但是网络编码没有意义，不需要进行网络编码，Step设置为1;当通信发生在两个不邻接的LEO卫星的覆盖区域内，需要路由，也需要进行网络编码，Step设置为2.NC:是否进行了网络编码，0表示未编码的报文，1表示编码的报文.NCSeq:若进行了网络编码，编码后的报文序列号.IDList:序列号列表，与源节点IP地址一起唯一确定了编码报文是由哪些RREQ报文线性编码而来的.HCou:用来记录编码RREQ报文后的跳数.Vec:从某个有限域中随机选取的编码系数，未编码时该项为空.RMes:封装的源RREQ报文.Sig:编码后报文的签名，Sig=Signature(Vec‖RMes).签名范围包括编码系数Vec及编码报文RMes.

2.6 路由建立

2.6.1 路由触发

在每个LEO 卫星时间片［tl1，tl2］起始 STime，路由查找产生路由表后，在该LEO卫星时间片内对该路由表进行存储，如果在该LEO卫星时间片内没有卫星节点失效或链路拥塞的情况出现，则各卫星节点间的相互关系保持不变，路由表保持不变.如果在该LEO卫星时间片之间出现卫星节点失效或链路拥塞等情况，则需要触发路由更新过程，重新进行路由查找，建立新的有效路由表.直到下个卫星周期开始，路由表切换时间为STime时再开始新的路由表建立过程.

2.6.2 路由发起

当源LEO卫星节点需要和目的LEO卫星节点的通信时，源LEO卫星通过其单步邻接表进行判断，若通信发生在其自身的覆盖区域内，不需要路由，不需要进行网络编码，直接进行消息转发;若通信发生在和其邻接的LEO卫星的覆盖区域内，则需要简单路由，网络编码仍然没有意义，源LEO卫星通过其邻接表的虚拟拓扑直接转发消息到邻接LEO卫星，不进行网络编码;若通信发生在两个不邻接的LEO卫星的覆盖区域内，需要路由，也需要进行网络编码，路由过程如下.

1)发送请求

当源LEO卫星节点需要选择到达目的LEO卫星节点的路由时，源LEO卫星节点Lij首先判断NC的值，若NC=1;接着产生RREQ请求报文Mi;进行编码时，首先从有限域GF(2s)中选取m个随机数，组成局部编码向量 a=(a1，a2，…，am)，然后，将报文进行线性编码运算;源卫星节点Lij使用签名算法对编码系数Vec与编码后的请求报文RMes使用Lij的私钥SKLij签名.

2)中继转发

中继LEO卫星节Lik在收到源LEO卫星节点Lij发送过来的编码包后，先通过Mtime验证报文是否新鲜，若不新鲜则直接丢弃;若未被丢弃，接着与之前已收到的同一数据段的编码包解码，利用源LEO卫星节点的公钥对接收的消息Mi和其签名Sig进行验证，如果验证不成功，丢弃该报文，否则中继LEO卫星节Lik对照其单步邻接表对收到的报文重新进行编码并转发出去.

3)解码回应

LEO卫星接收节点Lxy收到k个线性无关的编码包后解码出原始数据包，并利用源LEO卫星节点的公钥对收到消息的签名进行验证，若签名验证不成功，丢弃该分组，若签名验证成功，则接收节点Lxy回应RREP消息;LEO卫星接收节点Lxy收到RREQ后，将HCou加1并转发RREQ.

2.6.3 路由建立

源LEO卫星节点Lij收到RREP报文后，选择RREP报文中中跳数最小的路由作为最优路由.然后，LEO卫星节点Lij向选择的路由的下一跳LEO卫星节点Lik发送路由激活报文MACT.

2.6.4 路由维护

当某个有效路由上的链路由于LEO卫星节点自身故障或被攻击而失效导致链路损坏，或者链路拥塞，则其邻居LEO卫星节点利用错误消息ERR报告给GEO管理卫星.所有ERR消息均要求报告节点使用其私钥进行签名.GEO管理卫星收到两个以上的不同LEO卫星通过IOLs报告的ERR消息后，GEO管理卫星通过IOLs向所有LEO卫星广播吊销失效LEO卫星的密钥.

3 仿真结果分析

3.1 参数设置

第1轮第1次的仿真运行设定GEO卫星数目NGEO=3，LEO卫星数目为NLEO=48，单颗LEO卫星覆盖域为1.07 ×107km2，LEO 卫星时间片［tl1，tl2］为10 min，仿真场景如图4所示;设定LEO卫星的ISLs的数目为4，ISLs的带宽为10 Mb·s－1，平均链路传输时延为10 ms，各LEO卫星以恒定比特率发送数据，数据包大小为340 Byte，发包时间间隔为100 ms.

第1轮第2次仿真运行设定GEO卫星数目NGEO=3，LEO卫星数目为NLEO=75，单颗LEO卫星覆盖域为6.8×106km2，LEO 卫星时间片［tl1，tl2］为6 min，仿真场景如图5所示，其他参数设置不变.

第1次第3轮仿真运行设定GEO卫星数目NGEO=3，LEO卫星数目为NLEO=108，单颗 LEO卫星覆盖域为4.7 ×106km2，LEO 卫星时间片［tl1，tl2］为2 min，仿真场景如图6所示，其他参数设置不变.

第1轮的3次仿真结果如图7所示.其中NMessage为Message数量.

在第2轮的3次仿真运行中，分别随机指定1颗LEO卫星在LEO卫星时间片［tl1，tl2］内出现失效，其他参数设置不变，仿真结果如图8所示.

图4 NLEO=48时卫星组仿真示意图

图5 NLEO=75时卫星组仿真示意图

图6 NLEO=108时卫星组仿真示意图

图7 全部LEO卫星节点正常运行时的控制报文传输次数对比图

图8 指定1颗LEO卫星节点失效时的控制报文传输次数对比图

3.2 仿真结果分析

图7和8分别给出了文中提出的基于随机线性网络编码的卫星网抗毁路由协议与经典多层卫星网络路由协议MLSR在正常运行状态下和出现LEO卫星节点失效的情况下的控制报文传输次数对比.MLSR路由协议是采用卫星接收数据包驱动的计算卫星时延的汇聚路由协议，具有一定的抗毁性能，但是控制报文的传输次数较多.在文中提出的基于随机线性网络编码的卫星网抗毁路由协议中，由于在LEO卫星层的每个LEO卫星上使用了单步邻接表，按照LEO卫星时间片实时记录一跳邻居LEO卫星的信息，当需要路由的消息不在单步邻接表中时，在每个LEO卫星时间片起始发起路由查找，在路由请求阶段对RREQ报文采用随机线性网络编码.通过在LEO卫星上使用单步邻接表，当通信发生在单个LEO卫星覆盖域或两个相邻的LEO卫星覆盖域时，通过单步邻接表可以直接转发消息，而当通信发生在两个不邻接的LEO卫星的覆盖区域时，再进行网络编码路由，这样使得在有许多个用户通过UDLs接入的源LEO卫星节点和目的LEO卫星节点的卫星网络中，能够有效地减少控制报文的传输次数.

3.3 抗毁性能分析

文中提出的基于随机线性网络编码的卫星网抗毁路由协议的抗毁性能主要体现在我们在LEO卫星层的每个LEO卫星上使用了单步邻接表，该单步邻接表按照LEO卫星时间片实时记录了其一跳邻居LEO卫星的信息，单步邻接表在每个LEO卫星时间片［tl1，tl2］的起始时间 STime都会进行更新，当有LEO卫星发生失效时也会进行更新;在每个LEO卫星时间片［tl1，tl2］起始时间STime都会周期性发起路由查找，当有LEO卫星发生失效时也会促发新的路由查找，绕开故障LEO卫星节点，更新路由表;在路由查找时，报文中的报文产生时间Mtime能过很好地验证报文的新鲜性，在一定程度上抵御重放攻击;报文采用的私钥签名可以防止假的路由请求和应答，阻止敌对国恶意卫星节点或航天飞行器对路由信息的非法篡改，有效地增强了卫星网络的抗毁性能.

4 结论

1)在路由协议的设计中采用随机线性网络编码，在路由请求阶段对RREQ报文进行编码传送，能够有效减少消息传输次数.

2)通过在LEO卫星上设置按照卫星时间片动态更新的单步邻接表，对不需要执行网络编码的路由请求进行筛选，从而降低宇航芯片计算开销.

3)初步试验结果表明:新协议容错性强、可靠性高、信令开销小，可以有效提高卫星网的自适应性和抗毁性.

References)

［1］Long Fei，Sun Fuchun.A novel routing algorithm based on multi-objective optimization for satellite networks［J］.Journal of Networks，2011，6(2):238 －246.

［2］Liu Xiaoyue，Ma Jianfeng，Hao Xuanwen.Self-adapting routing for two-layered satellite networks［J］.China Communications，2011，8(4):116 －124.

［3］肖 甫，孙力娟，叶晓国，等.面向卫星网络的流量工程路由算法［J］.通信学报，2011，32(5):104 －111.Xiao Fu，Sun Lijuan，Ye Xiaoguo，et al.Routing algorithm for MPLS traffic engineering in satellite network［J］.Journal on Communications，2011，32(5):104 －111.(in Chinese)

［4］Gounder V V，Prakash R，Abu-Amara H.Routing in LEO-based satellite networks［C］∥Proceedings of IEEE Emerging Technologies Symposiumon Wireless Communications and Systems.Piscataway:IEEE，1999:91 －96.

［5］Akyildiz I F，Ekici E，Yue G F.A distributed multicast routing scheme for multi-layered satellite IP networks［J］.Wireless Networks，2003(9):535 －544.

［6］Akyildiz I F，Ekici E，Bender M D.MLSR:a novel routing algorithm for multilayered satellite IP networks［J］.IEEE/ACM Transactions on Networking，2002，10(3):411－424.

［7］Liu Xiaoyue，Ma Jianfeng，Hao Xuanwen.A self-adapting traffic class routing in LEO/MEO satellite networks［J］.Journal of Convergence Information Technology，2011，6(10):155 －163.

［8］郝选文，马建峰，刘小跃.空间信息网抗毁安全路由协议［J］.武汉大学学报:理学版，2011，57(5):413 －418.Hao Xuanwen，Ma Jianfeng，Liu Xiaoyue.An anti-damage routing protocol in space information network［J］.Journal of Wuhan University:Natural Science Edition，2011，57(5):413 －418.(in Chinese)

［9］Ahlswede Rudolf，Cai Ning，Li Shuo-Yen Robert，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204 －1216.

［10］罗 海，王彩芬，冯 帆，等.多源网络编码同态签名方案［J］.计算机应用研究，2011，28(4):1465 －1469.Luo Hai，Wang Caifen，Feng Fan，et al.On homomorphic signature scheme for multi-source network coding［J］.Application Research of Computers，2011，28(4):1465－1469.(in Chinese)

［11］陈继明，邹志文，潘金贵，等.基于自动机的XML路由改进算法［J］.江苏大学学报:自然科学版，2010，31(6):705－709.Chen Jiming，Zou Zhiwen，Pan Jingui，et al.An improved algorithm for XML routing based on finite automata［J］.Journal of Jiangsu University:Natural Science Edition，2010，31(6):705 －709.(in Chinese)