一种集成网络编码的低轨卫星网络多径路由方法
杨 林1, 2，郑 刚2
(1. 国防科技大学 电子科学与工程学院，湖南 长沙，410073；
2. 中国科学院 软件研究所 综合信息系统技术国家级重点实验室，北京，100080)
摘 要：针对星际链路的时变性、不可靠性和间断性连接的特点使得在低轨卫星网络中应用多径路由技术产生报文乱序和报文丢失现象，提出一种集成网络编码的多径路由方法。理论分析表明，在同等多路径数目和报文丢失率条件下达到相等的报文投递率，该方法的传输性能优于传统的多径路由方法。通过扩展ns-2软件并进行仿真实验，比较2种方法在不同的多路径数目、冗余因子和链路报文丢失率条件下的报文投递性能，仿真结果验证了理论分析的正确性，表明采用该方法可显著提高多径路由传输的可靠性，节省星上通信资源并在一定报文丢失范围内提升多径路由的容错能力。
关键词：低轨卫星网络；网络编码；多径路由；可靠性
中图分类号：TN919 文献标识码：A 文章编号：1672-7207(2007)05-0950-06
A multi-path routing scheme integrated with network coding in low earth orbit satellite networks
YANG Lin1,2, ZHENG Gang2
(1.School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China;
2. National Key Laboratory of Integrated Information System Technology, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China)
Abstract: Inter-satellite links have characters of time-varying, unreliability and intermittent-connecting, so that applying the multi-path routing in the low earth orbit (LEO) satellite networks can make message disorder and message loss. A multi-path routing scheme integrated with network coding was proposed to solve this problem. It is proved that with the same multi-path number and path message loss rate，the scheme outperforms the traditional multi-path routing in terms of message delivery rate. Moreover, the performances of both schemes were evaluated by the extended ns-2 software in terms of message delivery rate under the conditions of different multi-path numbers, link message loss rates and redundancy factors. The result validates the theory analysis and shows that the scheme can efficiently improve the reliability and save the onboard communication resources as well as enhance the error control of multi-path routing with certain ranges of message loss.
Key words: low earth orbit satellite networks; network coding; multi-path routing; reliability
低轨卫星网络具有良好的全球覆盖特性，可提供不间断的全球无缝接入服务，已成为下一代网络的重要组成部分。但卫星网络拓扑动态变化，星际链路时延长、误码率高、间断性连接以及多跳通信等特性使得在低轨卫星网络中难以提供可靠的信息传输服务。设计高效稳定可靠的路由协议一直是卫星网络领域的研究热点。当前，针对卫星网络的路由协议研究主要集中于最小延时路由[1]、以切换频率和费用为优化目标的QoS路由[2-3]和借鉴Ad Hoc网络路由思想的分簇路由[4]以及多层卫星网络路由[5]等，关于多径路由技术的研究还较少[6]。事实上，在采用星座结构组网的低轨卫星网络中，任何一颗源端卫星到目的端卫星之间通常会有多条路径。相对于单径路由，多径路由技术在带宽有效使用、拥塞和突发流量处理，传输可靠性等方面都具有其独特的优势，但在低轨卫星网络中应用多径路由技术也面临一些新的挑战：一方面，由于多径路由技术采用并行方式传输数据报文，各路径的带宽、跳数以及节点处理能力的差异导致报文传输延时差别较大，在目的端会出现报文乱序现象；另一方面，卫星网络拓扑变化和链路差错引起的路径中断会导致某些路径拥塞，从而产生报文丢失现象。由于在低轨卫星网络中多跳通信的端到端时延很大，采用传统的解决方案如报文重排序和报文重传机制将极大地增加网络传输代价，因此，应用在卫星网络中具有一定的局限性。
针对上述问题，本文作者提出一种集成网络编码的多径路由方法，通过在源端和中继节点附加线性编码操作，使得目的端节点可从信息部分丢失的报文或乱序报文中恢复出原始报文信息。相对于传统多径路由，采用该方法在达到相等的报文投递率时，能有效减少源端发送的冗余报文数目，降低通信开销，并在一定的报文丢失范围内提升多径路由的容错能力。此外该方法还具备更高的安全性，可以防止窃听、重放等网络攻击手段[7]。
1 集成网络编码的多径路由方法
1.1 低轨卫星网络的多径路由
低轨卫星网络的路由策略大体可分为按系统周期分割的虚拟拓扑类型、按覆盖区域分割的虚拟节点类型以及针对卫星网络拓扑特性的特定路由协议3类[8]。在此，主要采用按系统周期分割的虚拟拓扑图策略，构建低轨卫星网络的多径路由。
根据低轨卫星网络的周期性,把卫星系统周期T划分为n个时间间隔, 即T0=[0, t1], T1=[t1, t2], …, Tn-1=[tn-1, tn],当时间间隔[ti-1, ti]足够小时，卫星网络的动态拓扑结构可以转化为固定的静态拓扑结构，并保证该间隔内各星间链路的代价恒定不变。根据卫星网络运转的周期性、可预测性和规律性，在离线状态下预先计算好任意一对源端和目的端之间链路不相交的K条最短路径[9]，然后将路由表装载到各卫星上。划分时间间隔的数目决定路由表的存储开销，而时间间隔的顺序及长度则决定路由的切换时机。
该方法本质上属于静态路由方法，具有计算简单、星上开销小的优点，通过对相邻时间片内若干内容相同的原始路由表进行合并，还可进一步简化星上路由表，减小星上存储开销。该方法的一个潜在缺陷是自适应性较差，当网络拥塞或链路长期故障时会导致性能下降，可能的解决方案有通过增加星间消息交互“在线”修正路由表或者定期 “离线”更新并重载路由表。
1.2 集成网络编码方案描述
集成网络编码的多径路由方法是在传统的多径路由基础上加入网络编码技术提高传输的可靠性。主要步骤如下：源端将原始的m个报文编为一组并编码成n(n≥m)个大小相等的新报文，然后并行多路径发送；中继节点对隶属同组的源端编码报文进行重编码并转发；目的端收到足够多的编码报文后利用解码算法恢复原始报文信息。详细描述如下。
1.2.1 源端编码
采用随机线性码[10]作为网络编码方案， 按照报文产生的先后顺序，源端将每m个报文编为一组，记为X1, X2, …, Xm，并赋予相同的组标识，组标识从0开始递增，直到增加到某个上限后重新归零。当源端要发送该组报文时，从有限域Fq中选取m个随机数作为编码系数(gi1, gi2, …, gim)，并按照式(1)进行线性编码生成同等大小的编码报文Yi，同时将编码系数和组标识添加到报文头部。
, i=1, 2, …, n。 (1)
网络编码的报文格式如图1所示。若要产生n个编码报文Yi共需进行n次相同的编码操作，n的大小根据网络状态决定。
图1 网络编码的报文格式
Fig.1 Message format of network coding
1.2.2 中继节点重编码
卫星中继节点对一定时间间隔内接收的编码报文进行缓存，并对具有相同组标识的编码报文进行重编码，其好处在于进一步降低编码报文间的线性相关性，可提高解码成功概率。假设中继卫星R收到k个来自编码报文Y1, Y2, …, Yk，每个报文Yi对应的编码系数为(gi1, gi2, …, gim)，其中i=1, 2, …, k。则卫星R按照公式(2)和(3)重新产生k个新的编码报文及编码系数(
,
,…,
)并继续转发，其中
是针对Yi从有限域Fq中产生的新的编码向量
与原始向量gij的内积。
, l=1, 2, …, k， (2)
。 (3)
1.2.3 目的端解码
当目的端接收到m(或大于m)份编码数据，就可以采用矩阵转换的方式恢复出原始的m个报文。假设接收节点接收到的m份数据分别是Y1, Y2, …, Ym，则接收节点进一步判断这m份数据的编码系数(gi1, gi2, …, gim) (i=1, 2, …, m)的线性相关性，若这m组编码系数组成的
维矩阵满秩，则可通过公式(4)恢复出原始的m个报文。
当目的端接收的编码数据小于m时，可通过消息反馈机制通知上游节点对缓存的同组编码数据进行重编码操作并转发，直至目的端能恢复出m个原始报文为止。
(4)
2 关键参数和传输性能 2.1 关键参数分析
有限域Fq的范围和冗余因子r的取值对方案的解码性能和传输代价影响较大，须合理设置。
有限域Fq的范围。Fq的取值范围决定编码系数的线性无关概率，进而影响到随机线性码的解码性能。如果取值过小，即使目的端接收到足够的编码报文，但由于编码系数线性相关性较高，仍会出现原始报文无法恢复的情况；如果取值过大，编码系数占用的字节数过多会导致报文中的有效数据比例下降，还会引发大的存储开销。q在不同的取值下产生的编码系数 的线性无关概率如表1所示[11]。当q的取值为
时，2个编码系数向量的线性无关概率高达
，可使原始报文以极高的概率被恢复，且仅占用1字节的存储开销。本文使用有限域
作为随机线性码的字母表，并采用查表机制简化有限域运算，减小计算开销。
表1 不同有限域范围下的系数向量线性无关概率
Table 1 Probability of linear independency for coefficient vectors with different finite field size (q)
b. 冗余因子r。将源端经过网络编码后产生的n个编码报文与m个原始报文的比值定义为冗余因子，并用字母r表示，则
冗余因子r决定单个原始报文的平均冗余度。r越大，则目的端接收正确的编码报文个数也会相应增加，这样，固然能够提高其中
组编码系数线性无关的概率，但也会造成不必要的资源浪费。因为除了该m组编码报文外，其余的编码报文都是无用的。若r过小，则目的端接收的编码报文个数可能小于m，导致无法解码，因此，该参数的取值非常重要。
2.2 传输性能分析
下面分析在相同的路径数和路径报文丢失率下，分别使用集成网络编码的多径路由和传统多径路由2种方法将源端的m个原始报文投递到目的端的传输性能，并假设单条路径单次仅能传输1个报文。采用冗余因子r作为传输性能指标，它反映可靠传输1个原始报文平均需要发送的报文数目。当目的端达到相同的报文投递率时，r越小的方案其传输性能越好。各符号具体定义如下：K为从源端到目的端的链路不相交的多路径数目；e为单跳链路的报文丢失率，假设所有链路的报文丢失率均相等，
；li为第
条路径的链路跳数；Pi为从源端到目的端的第i条路径的报文丢失率，
， i=1, 2, …, k；m为源端产生的原始报文数目；r为集成网络编码的多径路由方法的冗余因子；
为传统多径路由方法的冗余因子；s为集成网络编码的多径路由方法在源端的发送报文总数，
；
为传统多径路由方法在源端的发送报文总数, 
；Ps为集成网络编码的多径路由方法在目的端接收个原始报文成功的概率；
为传统多径路由方法在目的端接收个原始报文成功的概率；Pf为集成网络编码的多径路由方法在目的端接收m个原始报文失败的概率，
；
为传统多径路由在目的端接收m个原始报文失败的概率，
。
定理 1 在K和Pi均相同的情况下，若使目的端接收个原始报文成功的概率满足
，则使用集成网络编码的多径路由方法比传统多径路由方法具有更优的传输性能，即r≤r′。
证明 采用反证法。命题可转化为求证当r＝r′时，Pf ≤
，即当2种方法的冗余因子相等时，使用集成网络编码的多径路由方法在目的端接收m个原始报文失败的概率更低。此时，显然有
，下面分别对2种方法进行分析。
对于传统多径路由方法，每1个原始报文都被复制成K份拷贝，然后，通过K条路径并行发送，共发送m次。假设目的端接收m个原始报文失败的情况共有m类，分别对应仅接收0, 1, …, m-1个原始报文，而每类情况对应的可能性分别有M0, M1, …, Mm-1种，则
，同理，对于集成网络编码的多径路由方法可得
，其中Ni (i=0, 1, …, m-1)分别对应仅接收了0, 1, …, m-1个编码报文。
下面分别比较Mi和Ni。显然，i=0时，M0=N0=1；对于i=1, M1共有
种可能，表示m次发送中仅成功1次，但单次发送中可能收到多份拷贝的情况，而N1共有
种可能，表示在所有s=Km个编码报文中仅收到1个的情况，显然N1中的所有情况都是M1的子集，即N1≤M1；同理可得：Ni≤Mi (i=1, 2, …, m-1)。所以有Pf ≤，命题得证。
3 性能评价 3.1 仿真模型
仿真环境为一个类似于铱系统的
极轨卫星星座，低轨卫星网络的拓扑结构如图2所示，轨道高度为880 km，倾角为90?。每颗组网卫星具有6条星间链路，2条在同一轨道面内的星间链路，2条相邻轨道面的星间链路和2条两跳邻居轨道面的星间链路，其中两跳邻居轨道面是指相邻轨道面的邻居轨道面。图2中，第1和第7轨道面上的卫星由于逆向运动，且相对速度较大，它们之间无法建立星间链路。当卫星进入高纬度地区，即南北纬超过70?后，由于相对运动速度原因使得卫星仅能保存在同一轨道面内的星间链路。仿真选取的地面站的经纬度分别为北京(116.46?，39.92?)和美国亚特兰大(-82.50?，33.75?)，其中北京为源端，亚特兰大为目的端，业务流量模型采用指数分布模型。多径路由使用链路不相交的K最短路径算法。网络编码采用有限域范围内的随机线性码其中源端和卫星节点执行编码及重编码操作，目的端执行解码操作。所有的仿真实验均在扩展后的ns-2[12]平台上完成，仿真时间为1 000 s，图中结果均为30组独立实验的均值。
图2 
低轨卫星网络拓扑结构
Fig.2 Topology of LEO satellite networks
3.2 性能比较
在单跳链路报文丢失率为0.1和冗余因子相等的情况下，不同多路径数目对报文投递率的性能影响如图3所示。结果表明，随着路径数的增加，报文投递性能显著提高，且集成网络编码方法的报文投递性能均优于传统多径路由方法。集成网络编码的多径路由方法可显著提高多径路由传输的可靠性，验证了理论分析的正确性。
在单跳链路报文丢失率为0.1和使用4条路径情况下，冗余因子对报文投递率的影响如图4所示。可见，传统多径路由方法在冗余因子为4.0时，报文投递率恒定在0.93左右，而集成网络编码的多径路由方法在冗余因子为3.5时即达到该报文投递率，可减少12.5%的通信量。该结果表明集成网络编码的多径路由方法在达到同等性能要求下可有效节省星上通信资源，减少不必要的通信开销。
链路报文丢失率为0.1，冗余因子相等
图3 不同多路径数目下的链路报文投递率
Fig.3 Message delivery rate under different multi-path numbers
链路报文丢失率为0.1，多路径数目为4
图4 不同冗余因子下的报文投递率
Fig.4 Message delivery rate under different redundancy factors
当冗余因子和多径数目均为4时，在无消息反馈机制条件下，链路报文丢失率对报文投递率的性能影响如图5所示。可见，随着链路报文丢失率的递增，2种方案的报文投递性能均呈下降趋势。当链路报文丢失率从0增加到0.15时，集成网络编码方法的报文投递率比传统的多径路由方法的报文投递率高，但此后传统多径路由方法的报文投递性能反而下降得更慢。这说明集成网络编码的多径路由方法仅在一定的报文丢失范围内能提升多径路由的容错能力。用可靠性模型理论进行解释[13]，这是因为传统多径路由方法属于并联系统模型，而集成网络编码的多径路由方法属于从n中取r模型，当单条路径的可靠度下降到某个阈值后，并联模型可靠度的下降速度反而慢些。
多路径数目为4，冗余因子为4.0
图5 不同链路报文丢失率下的报文投递率
Fig.5 Message delivery rate under different link message loss rates
4 结 论
a. 提出一种集成网络编码的多径路由方法，通过在源端和中继节点使用随机线形编码，在目的端进行解码操作使得目的端能从乱序报文和信息部分丢失的报文中恢复出原始报文信息，提高了多径路由的可 靠性。
b. 理论分析表明在同等路径条件和报文投递性能要求下，集成网络编码的多径路由比传统的多径路由具有更优的传输性能，即成功发送单个原始报文所需发送的冗余报文数目更少，可有效节省星上通信资源。通过对ns-2软件扩展并进行仿真实验，结果进一步验证了理论的正确性，该方法能在一定的报文丢失范围内提升多径路由的容错能力。
c. 该方法适合于低轨卫星网络中FTP文件传输、星间代码分发等对数据完整性要求较高的应用场景。
参考文献：
[1] Ekici E, Akyildiz I F, Bender M D. Datagram routing algorithm for LEO satellite networks[C]//Raphael R. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. San Jose: IEEE press, 2000: 500-508.
[2] 许 辉, 吴诗其. LEO 卫星网络中基于蚂蚁算法的分布式QoS 路由[J]. 计算机学报, 2007, 30(3): 361-367.
XU Hui, WU Shi-qi. A distributed QoS routing based on ant algorithm for LEO satellite network[J]. Chinese Journal of Computers, 2007, 30(3): 361-367.
[3] 张 涛, 张 军. 柳重堪.基于卫星时变网络的时延受限最小费用路由算法[J]. 电子学报, 2006, 34(9): 1584-1589.
ZHANG Tao, ZHANG Jun, LIU Zhong-kan. A delay constraint minimum cost routing algorithm for satellite time-varying network[J]. Chinese Journal of Electronics, 2006, 34(9): 1584-1589.
[4] 李 喆, 李冬妮, 王光兴. LEO/MEO 卫星网络中运用自组网思想的动态路由算法[J]. 通信学报, 2005, 26(5): 50-56.
LI Zhe, LI Dong-ni, WANG Guang-xing. New dynamic routing algorithm based on MANET technology in the LEO/MEO satellite network[J]. Journal on Communications, 2005, 26(5): 50-56.
[5] Akyildiz I F, Ekici E, Bender M D. MLSR: a novel routing algorithm for multilayered satellite IP networks[J]. IEEE/ACM Trans on Networking, 2002, 10(3): 411-424
[6] BAI Jiang-jun, LU Xi-cheng, LU Ze-xin, et al. Compact explicit multi-path routing for LEO satellite networks[C]//Hamdi M. 2005 Workshop on High Performance Switching and Routing. San Jose: IEEE press, 2005: 386-390.
[7] Fragouli C, Boudec J-Y L, Widmer J. Network coding: an instant primer[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(1): 63-68.
[8] 孙利民, 卢泽新, 吴志美. 低轨卫星网络的路由技术[J]. 计算机学报, 2004, 27(5): 659-667.
SUN Li-min, LU Ze-xin, WU Zhi-mei. Routing technology for LEO satellite network[J]. Chinese Journal of Computers, 2004, 27(5): 659-667.
[9] Ruppert E. Parallel algorithms for the k shortest paths and related problems[D]. Toronto, Canada: University of Toronto, 1996.
[10] Ho T, Karger D R, Medard M, et al. The benefits of coding over routing in a randomized setting[C]// Hideki I. The 2003 IEEE International Symposium on Information Theory. San Jose: IEEE Press, 2003: 442-447.
[11] WANG Dan, ZHANG Qian, LIU Jiang-chuan. Partial network coding: theory and application for continuous sensor data collection[C]//Abdelzaher T. The 14th IEEE International Workshop on Quality of Service. San Jose: IEEE Press, 2006: 93-101.
[12] Network Simulator-ns2[EB/OL]. [2007-05-20]. http://www.isi. edu /nsnam/ns/.
[13] 金 星, 洪延姬, 沈怀荣, 等. 工程系统可靠性数值分析方法[M]. 北京: 国防工业出版社, 2002.
JIN Xing, HONG Yan-ji, SHEN Huai-rong, et al. Numerical analysis methods of reliability for engineering systems[M]. Beijing: National Defense Industry Press, 2002.
收稿日期：2007-03-10；修回日期：2007- 04-25
基金项目：中国科学院知识创新方向性项目(KGCX3-SYW-4**)
作者简介：杨 林(1981-)，男，湖南长沙人，博士研究生，从事网络编码与卫星网络研究
通信作者：杨 林，男，博士研究生；电话：010-62614140-8312(O); E-mail: yanglin_nudt@yahoo.com.cn
