稀疏场景下基于网络编码和RSU数据传输的研究

章圆圆 马 宁 束永安

(安徽大学计算机科学与技术学院 安徽 合肥 230601)

稀疏场景下基于网络编码和RSU数据传输的研究

章圆圆 马 宁 束永安

(安徽大学计算机科学与技术学院 安徽 合肥 230601)

车载自组织网中数据传输的场景主要包括车辆密集的城市道路场景和车辆稀疏的偏远地区，目前大多数研究针对的是车辆密集场景下数据传输。在车辆稀疏的车载自组织网中，车辆节点间相遇的概率受限，因此数据传输面临信道负载大、传输延时高、带宽利用率低等挑战。为了提高数据包在稀疏场景下传输性能，提出了基于代间渐进编码技术和RSU的传输策略RORLNC，通过各个编码代之间的渐进编码操作，可有效防止因丢包引起编码数据包无法被解码。另外借助RSU寻找最佳转发车辆节点，可有效避免编码数据包长期无法被转发。用NS-2和MOVE软件进行仿真实验。实验结果证明RORLNC比现有的DDR算法具有较高的吞吐率和较低的平均转发延迟。

车载自组织网 数据传输 代间渐进网络编码 路侧单元

0 引 言

车载自组织网的网络拓扑变化快、间断性连接、车辆节点分布不均匀等特点，使得传统的自组网转发算法[1]并不适用。在车辆密集场景中，前人从不同方面改进数据包的传输性能[2-4]，并取得了较大的成果。然而在车辆稀疏场景中，车辆节点间的距离远大于车辆节点的通信范围，从而无法直接将数据包转发给下一车辆节点，近年来学者对该场景的研究进展较为缓慢。本文提出了基于代间渐进编码和RSU的数据传输算法RORLNC，改进传统代内随机线性编码，采用代间渐进编码方式，即后一代数据包与前一代已编码的数据包再做线性处理，即使前一代编码丢失，也可以被目的车辆节点根据后一编码代恢复，借助RSU将编码数据包转发给可适度值最大的下一车辆节点，从而降低转发次数和提高数据传输的可靠性。

1 随机线性网络编码

随机线性网络编码[5]：从最小有限域GF(2)随机选择编码系数对信源节点要广播的数据包进行线性编码处理，图1展示了传统随机线性编码的过程。

图1 随机线性网络编码原理图

在图1中，假设源节点S将要转发的数据分成X1、X2，在有限域中分别选取ε1、ε2和ε3、ε4。向A节点广播的数据可表示为：Y1=ε1X1+ε2X2，向节点B广播的数据可表示为：Y2=ε3X1+ε4X2。节点C分别接收到A、B广播的数据包Y1、Y2，再对Y1、Y2编码处理，可表示为：Y3=ε5Y1+ε6Y2=ε5(ε1X1+ε2X2)+ε6(ε3X1+ε4X2)，由于节点D1、D2已经分别接收到Y1、Y2，通过解码分别得到X1和X2，因此可以达到理论上的最大流和最小割的上限。

2 RORLNC策略设计

2.1 基本思想

RORLNC算法在源车辆节点采用代间渐进编码对数据包线性处理，在车辆稀疏的高速路上的每段道路建有路侧单元RSU，RSU与通信范围内的车辆节点组成一个集群，由RSU管理集群内的车辆，掌握车辆的运动状态(速度、方向、位置、携带的编码数据包)。在RSU缓存中换分两个固定区域S1、S2，其中S1区域用来存储车辆节点转发来的编码数据包，并根据编码数据包的数量和重复转发的次数建立一个编码数据包优先级列表，S2区域建立一个车辆节点优先级列表，计算经过群集中各个车辆节点的可适度值，可适度值越大优先级越高。RSU将编码数据包及时转发给可适度值最大的车辆节点，进而提高数据包在车辆稀疏场景中传输效率和降低转发延迟。

2.2RSU群集建立

RSU定时广播Rreq消息，周围车辆节点接收到Rreq消息，立即发送Rres消息，并通过该消息建立通信连接，并且由RSU管理周围各车辆节点的运动状态，其中Rreq消息和Rres消息的主要内容如下：

Rreq {

Rreq_ID;

//RSU的ID

Rreq_addr;

//RSU的位置

Rreq_snum;

//RSU缓存中数据包的数量

Rreq_iaddr；

//请求RSU通信范围内车辆节点的位置

Rreq_ive;

//请求RSU通信范围内车辆节点的速度

Rreq_idir; //请求RSU通信范围内车辆节点的运动方向

}

Rres {

Rres_ID;

//与RSU通信的车辆节点ID

Rres_RSUaddr;

//与车辆节点通信的RSU位置

Rres_addr;

//与RSU通信的车辆节点位置

Rres_ve;

//与RSU通信的车辆节点速度

Rres_snum;

//车辆节点携带数据包的数量

Rres_mnum;

//车辆节点间相遇的次数

Rres_mdir;

//车辆节点的运动方向

}

2.3 源车辆节点的代间渐进式编码

建立一个简单的随机函数h(x)[6]对源数据包做初始化处理，主要目的是防止中间节点故意破坏数据包。设随机函数为h(x)=x+c，其中c为随机数，随机函数h(x)将与编码数据包一起被转发，由目的车辆节点根据接收到的h(x)和编码数据包还原出源数据包，有效提高编码数据包的可靠性。对每个编码代数据包编号，编码代源数据包表示为I=(I0,I1,…,IK-1)。令c为第1编码代数据包I0，则第i个编码代数据包的初始化表示如下：

(1)

源车辆节点不再是简单对每个编码代数据包单独进行线性编码操作，而是采用代间渐进式编码方式。具体编码过程如下：

(4) 同理后面编码代的数据包依次做代间编码操作，直至各个编码代的数据包都被线性编码处理，第k代数据包的编码结果表示为:

(2)

源车辆节点中各个编码代的编码数据包与编码系数存在线性组合关系，对应的编码矩阵可以表示为：

(3)

2.4 下一转发车辆节点的选择

车辆与附近的RSU建立了群集，保证了RSU可以管理其群集内的车辆节点。如图2所示，混合车载网中数据传输有两种方式，一种是车辆与车辆通信，另一种是车辆与RSU通信，通过RSU将编码数据包转发给最佳转发节点。受文献[7]的启发，本文提出了车辆节点运动状态相似度MS(Motion Similarity)的计算方法，通过车辆节点MS的值计算出各车辆节点的可适度VS(Vehicle Suitability)。在RSU中，以TTL为时间周期定时更新群集内各车辆节点的可适度值VSnew，同时根据车辆节点的可适度值建立一个车辆节点优先级列表PL(PriorityList)来显示每个周期中车辆节点转发编码数据包的优先顺序，车辆节点的可适度越大，其优先级越高，反之越低。

图2 车辆与RSU建立群集

当携带有编码数据包的转发车辆节点i与附近有车辆节点j相遇，则通过“hello”消息建立通信连接，车辆节点i根据“hello”消息中车辆j的运动方向做出判断。由于高速路上车辆节点间相对运动方向只存在相同或是相反，如果车辆节点j与i运动方向相同，这两个车辆相遇其他车辆是基本相同的，说明车辆节点j将编码数据包扩散到远处目的节点的机会较小，反之车辆节点i将编码数据包转发给车辆节点j。当转发车辆节点i周围不存在与之通信的车辆节点或存在车辆节点，但车与自己运动方向相同，车辆节点i则选择与所属群集的RSU建立连接。根据式(4)计算群集内车辆节点的运动状态相似度MS，RSU采用式(5)更新各车辆节点的可适度值。

(4)

(5)

在式(5)中，EN表示车辆节点与其他车辆节点相遇的次数，den表示车辆节点间相遇时运动方向不相同的次数。MS越大，车辆节点间运动方向相同的概率越大，此时编码数据包更不易被转发到远处的目的节点。在式(5)中，VSold表示车辆节点之前的可适度，初始值为0。其中参数α和β满足α+β=1(α∈(0,1),β∈(0,1))，α和β反映的是可适度VS和车辆节点运动状态相似度MS的相关程度，α的值越大，VS的值与车辆节点的运动状态相似度相关性越大，此时α和β的值是人工设置的。

2.5 目的车辆节点的解码

(6)

(7)

由于r(Z′)=k，根据可逆矩阵定理，满秩矩阵可逆。目的车辆节点根据解码式(8)解码出所有编码代的数据包。

(8)

⋮

3 仿真实验与结果分析

3.1 仿真场景描述

本文采用NS-2和MOVE仿真软件[9]在车辆稀疏模拟场景下对RORLNC进行仿真实验。本节采用MOVE仿真软件对某个区域的地图建立车辆节点移动模型，利用NS-2提供完整的网络模拟环境，因此网络模拟软件NS-2中的节点可以根据MOVE设置的车辆运动轨迹的方式运动，此时MOVE和NS-2是一种协作关系。将RORLNC和DDR在平均转发延迟、吞吐率、传输效率三个方面[10]比较分析。仿真试验区域为5 000 m×4 000 m的长方形，道路宽度和长度分别为20 m和5 000 m，并且道路采用双车道双向通行。车辆的通信范围为半径R=300 m的圆形区域，车辆运动速度为10～20 m/s随机变化，区域中的车辆的数量为0～120不等，并且车辆的密度随着场景的变化而改变，服从指数分布。本文建立的动态坐标轴的横轴长5 000 m,纵轴长4 000 m，坐标轴内单元格为10 m×10 m的矩形，车辆在该坐标轴内的运动方向有上、下、左、右。应用层生成大小为10 KB源数据，在传输层被分成10个编码代数据包，并采用UDP协议将数据包发送到网络层，编码系数从最小有限域GF(2)中随机选择。采用IEEE802.11b的MAC协议，车辆向附近车辆广播“hello”消息的周期TTL=0.5s。哈希函数为h(x)=x+c，其中c为随机常数，该函数随编码数据包一起转发给下一转发车辆节点，将此次仿真时间设置为400s。为了保证实验结果的客观性，在同一场景下进行10次仿真实验，并取其平均值作为本次试验结果。

3.2 实验结果分析

1) 吞吐率

如图3所示，在车辆节点数量为0时，在车载自组织网中只有路侧单元RSU，数据包无法进行传输。随着车辆节点数量的增多，RORLNC算法明显要优于DDR。在车辆数量为100时，本章提出的RORLNC算法吞吐率与DDR算法相比，提高了近60%。分析认为，DDR算法只是采用车辆节点作为转发节点，但在车辆稀疏场景下，车辆节点间大部分时间不能建立完整的数据传输路径，导致了车辆节点的吞吐率较低。而RORLNC算法首先借助RSU作为转发节点，并且对接收的编码数据包和经过群集中的车辆节点分别建立了优先级列表，在尽可能短的时间内将编码数据包转发给车辆节点，有效提高了吞吐率。另外在MOVE和NS-2两个仿真软件中的实验表明该传输策略较于DDR协议明显提高了吞吐率。

图3 车辆节点数量对吞吐率的影响情况

2) 转发平均时延

图4显示了两种算法的数据包平均转发延迟随车辆节点数量变化的曲线。从图中可知，当车辆节点数量极少时，由于车辆节点间相遇的机会有限，数据包转发的概率较低，两种算法的平均延迟都较高。随着车辆节点数量的增加，两种算法都有明显降低，但与车辆密集的场景相比，该场景下车辆节点的数量仍不能使数据包在车辆节点间直接进行传输。由于RORLNC借助了RSU，由RSU以TTL为周期选择本地群集中可适度最高的车辆节点(优先级最高)作为下一转发车辆节点，因此RORLNC算法的平均延迟整体上要低于DDR。MOVE和NS-2两个仿真软件中的实验表明该传输策略较于DDR协议，转发平均时延得到了降低。

图4 车辆节点数量对平均转发时延的影响情况

3) 数据传输效率

图5描述了数据传输效率与车辆节点数量的关系。从图中可以看出，两种算法的效率随车辆节点数量的增加，总体上呈上升趋势，原因是基于分簇和基于车辆路径近似度的思想都是与车辆建立连接，寻找最佳的转发车辆节点，可在车辆稀疏场景中，车辆间的连接机会较少，无法建立有效的连接进行数据的转发。RORLNC算法的效率明显较高，是因其设置了多个判断，当携带编码数据的车辆节点附近存在通信机会的车辆节点，则将编码数据包发送给行驶方向相反的下一车辆节点，否则与附近的RSU建立连接，由RSU将编码数据包在合适的时间转发给在时间TTL内优先级最高的车辆节点，从而提高数据的传输效率。MOVE和NS-2两个仿真软件中的实验表明该传输策略提高了数据包的传输效率。

图5 车辆节点数量对传输效率的影响情况

4 结 语

为进一步提高数据包在车辆稀疏场景下传输性能，本文首先在传统的随机线性网络编码基础上，提出了一种的基于RSU的代间渐进式网络编码RORLNC。在RORLNC中，首先建立一个哈希函数对源数据包初始化，防止数据包被窃听，然后依次对每个代间数据包做渐进编码操作，有效提高了编码数据包的可靠性传输，保证了编码数据包能被解码。关于转发车辆节点的选择，本文则借助RSU计算周围车辆节点的可适度值。通过MOVE和NS-2仿真软件对DDR和RORLNC的数据传输性能进行比较和分析，MOVE和NS-2仿真实验结果验证了ORLNC算法在整体性能上要优于DDR。

[1]IETF.MobileAdHocNetworks[OL].http://www.ietf.org/html.charters/manet-charter.html.

[2]ZhuH,ChangS,LiM,etal.Exploitingtemporaldependencyforopportunisticforwardinginurbanvehicularnetworks[C]//2011InternationalConferenceonComputerCommunications.IEEE,2011:2192-2200.

[3]ShafieeK,LeungVCM.Connectivity-awareminimum-delaygeographicroutingwithvehicletrackinginVANETs[J].AdHocNetworks,2011,9(2):131-141.

[4] 卢怡睿,俞研,吴家顺.基于网络编码与分簇的车载自组网数据分发算法[J].计算机应用,2014,34(S1):9-11,14.

[5]KumarR,DaveM.DDDRC:decentraliseddatadisseminationinVANETusingraptorcodes[J].InternationalJournalofElectronics,2015,102(6):946-966.

[6]MakTK,LaberteauxKP,SenguptaR.Amulti-channelVANETprovidingconcurrentsafetyandcommercialservices[C]//Proceedingsofthe2ndACMInternationalWorkshoponVehicularAdHocNetworks.ACM,2005:1-9.

[7] 胡皓.容迟网络的路由技术研究[D].北京:北京理工大学,2014.

[8] 俞美华.求逆矩阵的几种方法[J].科技视界,2015(31):177-178,224.

[9]AhujaB,GohilA,KumarR,etal.SimulationofVANETusingVanetMobiSimandNS-2[J].WirelessCommunication,2013,5(9):381-384.

[10]MartelliF,RendaME,RestaG,etal.Ameasurement-basedstudyofbeaconingperformanceinIEEE802.11pvehicularnetworks[C]//2012InternationalConferenceonComputerCommunications.IEEE,2012:1503-1511.

RESEARCH ON DATA TRANSMISSION BASED ON NETWORK CODING AND RSU IN SPARSE SCENE

Zhang Yuanyuan Ma Ning Shu Yongan

(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

The scene of data transmission in VANET mainly includes vehicle intensive urban road scenes and vehicle sparsely in remote areas. Nowadays, most of the research is focused on the data transmission in the vehicle intensive scene. In the sparse VANET, the probability of meeting between the nodes of the vehicle is limited, so the data transmission faces the challenges of large channel load, high transmission delay and low bandwidth utilization. In order to improve the transmission performance of the packet in the sparse scene, a transmission strategy RORLNC based on the inter-generation gradual network coding and RSU is proposed. Through the coding between the various code generation operation, can effectively prevent packet loss caused by the encoded data packet can’t be decoded. In addition, the best forwarding node can be found by RSU, which can avoid the long-term failure to forward the encoded data packet. The simulation experiment is carried out with NS-2 and MOVE software, and the experimental results show that RORLNC has higher throughput and lower average forwarding delay than the existing DDR algorithm.

VANET Data transmission Inter-generation gradual network coding RSU

2016-04-08。安徽省自然科学基金项目(1408085MF125)。章圆圆，硕士生，主研领域：无线网络。马宁，硕士生。束永安，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.06.048