应用网络编码的空间信息网多径路由协议设计

韩欢 韩笑冬 王睿 安卫钰 张呈

(中国空间技术研究院通信卫星事业部，北京 100094)

空间信息网[1]是由地面站、卫星、空间站和载人飞船等具有空间通信能力的航天器共同组成的互联互通的网络信息系统，可实现天、空、地之间的通信。空间信息网具有覆盖面大、不受地理限制、组网灵活快速等特点，能为海、陆、空各种任务提供集成的通信服务，具有十分重要的应用价值。

受空天环境及低轨卫星网络拓扑动态变化的影响，空间信息网的误码率较高，易发生丢包现象，且链路时延大，时延抖动严重，采用传统的报文传输及重传机制将极大地增加网络的传输代价，因此，适合空间环境的路由技术一直是空间信息网研究的热点。当前，空间信息网的路由技术大多针对卫星网络，研究主要集中于服务质量(QoS)路由技术[2]、负载均衡路由技术[3]及多服务路由技术[4]3类，但是这些技术并未有效地解决空间信息网的长时延、高误码率等问题。为此，本文提出一种应用网络编码的空间信息网多径路由协议，采用流量分配的机制建立最优的3条路径，同时在数据传输过程中应用网络编码模式提高传输的可靠性，路由维护采用中间节点重传机制，可减少传统端到端重传的长时延和高开销。

1 多径路由建立

应用网络编码的多径路由协议，在路由的建立中主要以带宽时延作为接入限制，以跳数、误码率、路径可用度和吞吐率等参数作为重要因子，建立源节点与目的节点之间的多径路由。当源节点有数据需要向目的节点发送且没有到达该目的节点的路由时，源节点发起路由请求，开始路由的建立，具体步骤如下。

(1)源节点广播路由请求报文(Route Request，RREQ)，报文包含路径节点列表、最大跳数限制、节点拥塞度列表、链路丢包率、接入带宽限制等参数(见表1)，同时将当前时间填入到<发送时间>中。

表1 RREQ各域定义

(2)中间节点收到RREQ报文后判断本节点的拥塞度、带宽是否满足路由请求要求。若不满足上述两个条件，则丢弃报文；否则，更新路由并转发RREQ报文。

(3)目的节点收到第1个报文后启动定时器，记录TD(由目的节点D根据传输业务需求确定)时间内收到的所有RREQ中的路径信息，并对多条路径信息进行评估，根据路径可用度选择最优的3条节点不相交路径，最后沿着3条路径的反方向给源节点发送应答报文(Route Reply，RREP)。第I条路径的可用度用RI表示，其表达式为

(1)

(4)中间节点收到RREP报文后读取源节点和目的节点信息，建立到达目的节点的动态前向路由，并向下一跳转发RREP报文。

(5)源节点收到RREP报文后，获取路径信息，并通过链路的拥塞度及可用度对各路经进行合理的流量分配，实现负载的均衡，最终完成多径路由的建立。

2 应用网络编码的多径数据传输

2.1 基本思想

网络编码[5-6]的主要思想是网络中的各个节点对收到的数据进行线性或者非线性的组合后再转发，最后在目的节点解码恢复出原始的数据包。与传统的路由传输方式相比，网络编码可以提高信息传输率，节约传输所需能量，增加传输的可靠性和安全性，现广泛应用于Ad hoc等无线网络[7-8]。

多径路由传输思想如图1所示。其中：S为源节点；Z1，Z2，Z3为中间节点；Y为编码后的数据包。S采用3条不相交多径路由向目的节点D发送数据包A，B，C，对于采用传统传输方式的图1(a)，链路的误码率导致数据包A和B丢失，源节点需要重传丢失的数据，增加了信息传输的时延和网络开销；对于应用网络编码传输方式的图1(b)，由于源节点和中间节点对数据进行编码后再传输，最后目的节点接收到的多个数据包通过解码得到数据包A，B，C。由此可知，应用网络编码的多径路由传输，通过编码冗余可提高空间信息网数据传输的可靠性，减少了重传次数。

目前，应用网络编码的多径路由传输都是通过增加冗余包的数量来提高传输可靠性，增大了网络的开销，因此如何合理的对数据编码个数进行选取，在保证数据传输可靠性的同时又不会引起网络开销过大，是应用网络编码传输需要解决的一个难题。针对这一难题，本文提出一种综合考虑收到的数据包及链路误码率确定最优编码次数的策略。

图1 2种多径路由传输方式对比

2.2 数据传输

2.2.1 源节点编码

当源节点建立多条路径之后，开始对原始数据进行编码。

(1)对需要传输的数据包进行分组。源节点将N个数据包分成一组，记为X1，X2，…，XN，并赋予相同的组标志符(从0开始递增)；分组后根据链路状况确定编码个数，通过增加冗余来解决空间信息网高误码率带来的丢包问题。M(S)表示源节点实际要发送数据包的个数，计算公式为

(2)

式中：P[S,H]为源节点S与下一跳节点之间的链路传输成功率，其值可以通过周期性地向邻居节点发送HELLO包得到；E(S)为源节点S的所有下一跳节点集；min(P[S,H])为源节点S与下一跳节点链路状况最差值。

(2)选取编码系数。从有限域[9]F中随机选取M(S)组数，每组数中又包含N个系数(ki,1,ki,2,…,ki,N)，对数据包进行线性编码，产生新的数据包Yi，编码公式为

(3)

式中：j=1,2，…，N。

(3)发送数据。将组标志、编码向量等信息作为包头加入到生成的数据包中，并发送到网络中，如图2所示。在发送的过程中，源节点充分利用多径路由的优势，根据每条路径的路径可用度分配不同数目的数据包。这种传输方式将数据包分散到各节点上，且通过编码有效地保证了数据包的安全性。

图2 网络编码过程

2.2.2 中间节点重编码

中间节点根据收到的数据包及链路误码率确定最优的编码策略。当中间节点p收到第1个新批次的数据包时，启动一个定时器，对时间T内收到的数据进行重编码。T要保证下一跳能接收到足够多的数据包，因此T的计算公式为

T=M(u)·(T(p)-T(u))

(4)

式中：M(u)为节点p的上一跳节点u发送数据包的个数；T(p)为第1个数据包到达节点p的时间；T(u)为数据包从节点u出发的时间。

当计时结束时，中间节点就会对T时间内收到的数据包进行重编码，重编码的次数选取会影响到数据传输的可靠性，选择合适的编码个数可以有效地提高网络中数据传输的可靠性。因此，对于中间节点，根据收到的数据包及链路状况确定最佳的编码个数M(q)，其确定规则如下。

(1)若N(q)=1，则直接向下一跳节点转发，不再进行编码操作。

(2)若N(q)=2，编码次数计算公式为

(5)

(3)若N(q)>2且N(q)

(6)

(4)若N(q)>N/2，编码次数计算公式为

(7)

式中：N(q)为中间节点q在时间T内收到的来自上一跳节点u发送的具有相同组标志符数据包的个数；r为q的下一跳节点；P[q,r]为节点q与节点r之间的链路状况；W为不相交路径条数。

(8)

根据式(3)和式(8)，可以求出中间节点编码后的数据包和源节点发送的数据包之间的关系，可表示为

(9)

(10)

式中：m=1,2,…,N(q)。

图3 第M(q)个编码数据包格式

Fig.3 TheM(q)-th coding data packet format

2.2.3 目的节点解码

目的节点收到数据包之后先贮存。设在一定时间内收到的数据包个数为N(D)，若N(D)>N，且收到的N(D)个数据包的系数线性无关，则通过矩阵进行解码，恢复出原始数据包,解码公式见式(11)；反之，若收到的N(D)个数据包的系数线性相关，或者N(D)

(11)

2.3 数据重传机制

目前的数据重传机制大多采用端到端、跳到跳的重传机制，或者停等式重传机制及选择性重传机制。这些机制对数据包的处理比较单一，采用数据包单个处理的思想，对每一个数据包的传输、丢失和重传均逐一处理。而对于网络编码，其传输的数据包之间可以相互建立关系，节点可以从编码包中同时获取多个丢失的数据包。因此，可以对重传机制加以改进。

若采用源节点重新编码发送，则需要经历和原来数据包同样的传输过程，这不仅浪费带宽，也增大了开销。因此，利用网络编码传输机制中各个节点可以对数据包进行处理的特殊性，本文提出一种中间节点重传的方案，在使目的节点获得足够多可用于解码的数据包的同时，节省了网络的资源。

图4是应用网络编码的重传机制原理示意，源节点S与目的节点D间建立3条不相交路径，3条路径状况各不相同，其中S-Z1-D路径传输成功率最高。各节点采用网络编码对数据包进行传输，若目的节点未能收到可供解码的足够多的数据包，则等待Twait，见式(12)。

图4 应用网络编码的数据重传机制示意

(12)

Twait=0，表示节点无丢包，不需要请求重传。在经过Twait时间后，若Nmiss≠0，则生成反馈消息，包括丢失的数据包个数及组标志符。如图4所示，目的节点D将反馈信息发给传输成功率较高的Z1节点。Z1节点收到反馈信息之后，对缓存内的同一组标志符的数据包进行重编码，其编码次数ML计算公式为

(13)

式中：Nmiss为缺少的数据包个数；P[Z1,D]为上一跳节点Z1与目的节点D之间的链路状况。

3 仿真及性能分析

采用网络仿真-2(NS-2)平台对提出的路由设计进行仿真。仿真的拓扑模型包括3颗地球同步轨道卫星，50颗低轨道卫星，组成一个覆盖全球的卫星网络。为了有效地比较算法的性能，在仿真中设带宽为2 Mbit/s，单跳链路报文丢失率为0.1，随机设置10条恒定比特率(CBR)数据流，数据包发送速率为50 kbit/s，每个报文长度512 byte。通过改变每次的发包率(仿真中分别采用10包/秒，15包/秒，20包/秒，25包/秒，30包/秒，35包/秒，40包/秒)对应用网络编码的空间信息网多径路由协议(SMNC)和传统按需距离矢量多径路由协议(AOMDV)的分组投递率、路由开销及端到端的时延进行仿真。2种协议采用相同的仿真环境，且对一条链路设置相同的链路误码率，仿真时间为100 s。

图5为改变发包率时2种路由协议分组投递率的变化情况。当发包率较少时，2种路由协议的分组投递率都比较高；随着发包率的增加，网络拥塞现象日益突出，数据包丢弃率大大增加，分组投递率曲线呈下降趋势。从图5中可以看出：SMNC的分组投递率优于AOMDV，应用网络编码的路由，数据传输时通过综合考虑链路误码率增加了一定的冗余数据，优化了网络纠错的能力，提高了数据传输的成功率，减少了数据包的重传，使分组投递率较好；而AODMV由于网络拥塞及链路误码率等因素导致数据包频繁丢失，需要不停地重传，从而加重网络的负载，因此分组投递率下降得较快。

图6是随着网络发包率增大路由开销变化曲线。当发包率较少时，2种协议的开销主要来自路由建立时广播的请求报文；随着发包率的不断增加，网络负载也随之加重，路由开销曲线开始呈下降趋势。由图6可知：AOMDV的开销大于SMNC的路径，对于AOMDV来说，数据包在传输的过程受链路误码率及网络拥塞的影响，容易发生丢包现象，大量地重传请求增大了网络的开销；对于SMNC来说，采用网络编码的数据包传输通过冗余数据提高了传输的可靠性，冗余包、编码计算虽然增大网络的一部分开销，但与通信的整体能耗相比几乎可以忽略不计，同时网络编码的传输机制减少了数据重传的次数，从而减少了整个网络的开销，因此路由开销比AOMDV小。

图7是随着网络负载增大数据传输平均时延变化曲线。当网络的负载较轻时，2种路由协议的数据包传输的成功概率较大，时延较短；但因受无线信道的影响，AOMDV会有少量丢包，数据的重传会带来一部分时延，对于SMNC来说，数据的编解码也会带来一定的时延，因此2种路由协议的传输时延差不多。随着发包率的增加、负载的加重，2种协议的平均延迟曲线均呈上升趋势。对于AOMDV来说，重拥塞及高误码率带来的丢包，导致不停地从源节点进行重传，对于空间信息网来说，其链路本身时延就较大，因此重传更增大了传输的时延。而SMNC首先通过网络编码增加了一定的冗余数据包，加大了传输的成功率，减少了重传带来的时延；同时，应用网络编码的重传机制通过中间节点进行重传，大大缩短了数据包的传输时延。因此，应用网络编码的多径路由协议弥补了传统多径路由传输中存在的不足，有效地解决了空间信息网路由技术长时延、高误码率等问题，能为空间信息网提供可靠、可信、高效的数据传输。

图5 分组投递率

图6 路由开销

图7 平均时延

4 结束语

针对空间信息网高误码率、长时延等问题，本文提出了一种应用网络编码的空间信息网多径路由协议，通过带宽时延等关键参数作为路径可用度建立多条节点不相交的多径路由，同时在数据传输的过程中采用网络编码技术，增加网络传输的可靠性，减少数据重传的次数。另外，考虑到网络编码的优势，提出应用网络编码的重传机制，通过中间节点进行数据包的重传，减少数据重传的时延，改善空间信息网传输时延长的问题。应用网络编码的多径路由协议虽然提高了空间信息网的传输性能，但编码算法较为单一且计算量较大，加重了CPU的负担，因此未来需要继续进行网络编码的研究，降低网络编码的复杂度，优化编码策略，以最小的代价最大化地提升路由传输的能力。