马 宁，张义兵，束永安

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

基于网络编码的车载网数据传输性能的研究

马 宁，张义兵，束永安

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

车载网通过车辆与车辆(Vehicle to Vehicle，V2V)或车辆与路侧单元(Vehicle to Infrastructure,V2I)之间的数据传输实现通信。车载网络不同于传统无线网络，具有网络拓扑变化快、节点受限、网络间断性联通等特点。由于车辆高速移动以及街道障碍物阻挡等原因,车载网络分割现象更加严重,路由问题更加复杂。因此车载网中数据传输性能面临着信道负载大、传输延时高、带宽利用率低等的挑战。为了提高车载网数据传输的效率并降低转发延时，文中在混合通信结构(V2V&V2I)中，提出了一种改进的随机线性网络编码(Optimized Random Linear Network Coding，ORLNC)技术，同时采用车辆路径近似度来确定下一转发车辆节点。NS-3和MOVE仿真实验表明，ORLNC与现有的DDR协议算法相比，明显降低了转发延时，提高了传输效率，同时该协议算法不仅适用于密集车载网，也适用于稀疏场景中数据的传输。

车载网；车辆与车辆；车辆与路侧单元；混合通信结构；改进的随机线性网络编码

0 引 言

车载自组织网络(VANET)不同于无线Mesh网，它具有能量足、计算能力强、网络拓扑变化快、网络间断连通性、节点受限运动等特点。因此车辆间数据传输性能面临较大的挑战。

诸多学者基于随机线性网络编码提出了多种新协议算法[1-3]。其中,Mirani F利用随机线性网络编码结合基于延时中枢机制协议提出了基于延时的机会网络编码协议—DONC[4]，基于延时广播机制是建立在发送方与接收方之间距离的基础上。实验已证明DONC协议的数据传输性能优于传统的基于延时的广播协议，但转发延时高和传输效率低等仍是车载网数据传输性能的主要影响因素。文献[5]提出了基于网络编码与分簇的分发算法—DDR，利用粒子群算法优化簇头的选举，其中周期性动态选举簇头需花费大量时间，延时性较高。

文中对适用于无线Mesh网中的随机线性网络编码进行了改进，在混合通信结构中提出了ORLNC算法并且采用基于车辆路径近似度的车辆选择协议。该协议算法可以进一步降低转发延时并提高传输效率。

1 随机线性网络编码

随机线性网络编码[6-7]：对信源节点要广播的数据包进行线性编码处理，其中编码系数从最小有限域GF(2n)中随机取得。

图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)

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

由于节点D,E已经分别接收到Y2,Y1，通过解码分别得到X1和X2，因此可以达到理论上的最大流和最小割的上限，实现数据传输在转发延时、系统容量和均衡负载方面的性能提高。

车载网络：车载网是最近兴起的自组织网络结构，它广泛应用于交通运输类、交通安全类和信息服务类。车载网不同于传统的无线网络，具有网络拓扑变化快、节点运动受限、网络间断连通性、能量足、计算能力强、自组织和自管理的特点，可以实时广播道路交通状况，有效提高交通安全。车载网作为新型的通信网络，可以实现车辆与车辆(V2V)的通信、车辆与基础设施(V2I)的通信和混合通信(V2V&V2I)。但其传输效率和传输延时不能满足日益增大的数据传输量。文中是在混合通信结构中基于改进的随机线性网络编码对数据传输性能的研究，达到提高传输速率和降低转发延时的目的。

2 ORLNC协议算法

2.1 场景描述

随着3G网的全覆盖和4G网的普及，无论在城市车辆密集地区还是在车辆稀疏的偏僻区域，保证数据传输的实时性和准确性都是比较难实现的。传统的实现方法主要通过基站的覆盖，由于成本太高，因此很多地方很难覆盖，数据很难得到高效传输。网络编码的应用可以有效解决网络负载和延时等问题。但随着数据信息量不断的增加，高延时性和低传输效率等问题还是存在。可借助路侧单元(RSU)[8]结合改进的随机线性网络编码进行数据转发。文中在车辆密集场景下研究数据传输性能。

将整个区域划分成若干个小区域，每个小区域由多个路侧单元负责该区域内车辆的运行轨迹的跟踪。整个区域内的路侧单元由一个控制中心控制，从而控制该区域里的车辆间的数据传输。当车辆转发数据给另一车辆，若都在控制中心A区域内，区域内的车辆将自己的运动状态(车辆ID、运动方向、运动速度、所在位置)发送到RSU，RSU可根据车辆的运动状态，采用车辆路径近似度确定下一个转发车辆节点。当中间车辆节点接收到多个编码数据则根据目标车辆的轨迹选择进行再编码处理或者直接转发，直至目标车辆接收到编码数据包。如果目标车辆已经离开A区域，则RSU将车辆的运动状态发送到控制中心，由各控制中心通过卫星GPS相互交换信息，从而指导各区域的RSU，进而控制车辆间数据的传输，保证数据传输的时效性和安全性。

2.2 ORLNC协议算法描述

可以将数据的传输过程分为三个阶段:

(1)编码数据包阶段。

首先将源数据X分成n份，即X=(X1,X2,…,Xn)，每一份数据包有m个数据，则第i个数据包可以表示为：Xi=(xi,1,xi,2,…,xi,m)。为了防止数据在传输过程中被破坏丢失，建立一个多元函数h(x,y)对源数据包进行初始化处理[9-10]。以第一个数据xi,1作为初始随机数,处理过程如下：

(1)

其中，h(x,y)为多元函数。

考虑到多元函数的计算复杂度，文中建立二元随机函数h(x,y)=x+y+c，其中c为随机常数。则式(1)中Yi可以进一步表示为：

(2)

其中i∈[1,n]，将二元函数h(x,y)同编码数据包一起转发给下一车辆节点。

(2)中继车辆节点选取阶段。

该协议算法采用路径近似度[12-13]确定下一转发车辆节点，各车辆以“hello”的会话消息形式周期性将自己的运动状态广播给该区域的RSU，RSU根据附近车辆的运动状态(车辆ID、所在位置、运动方向、运动速度)建立局部动态坐标轴，见图2。

图2 基于路径近似度的车辆运动坐标示意图

中间车辆节点的路径近似度可表示为：

(3)

其中：i为中继车辆；obj为目标车辆；s为源车辆；TTL为车辆向RSU发送消息的周期时间；dmin(i,obj)为中间车辆与目标车辆最短路径近似度。

(4)

(5)

式(4)、(5)分别是求初始时刻源车辆与目标车辆的近似距离和t时刻中继车辆与目标车辆的近似距离。

图2中，车辆的路径近似度越高表示它经过目标车辆附近的概率就越大，将中继车辆中路径近似度最大的车辆作为下一转发车辆节点。在路径近似度相同的情况下，考虑将时间效率高的车辆选择为下一转发车辆节点，即达到路径近似度最高时最短时间的车辆，时间效率可表示为：

(6)

RSU根据式(3)计算结果确定下一转发车辆节点，在转发中继车辆节点中又接收到多个有效编码数据包的车辆，则再进行编码处理。此时编码系数不需再从最小有限域中随机选取，而是使用源车辆选取的编码系数。若在选择下一转发节点时，出现相同的路径近似度的两辆车，根据式(6)计算出车辆与目标车辆近似度最大时，选择时间效率较高的车辆为下一转发车辆节点。

(3)解码数据包阶段。

ORLNC实现数据传输步骤如下：

①源车辆对要转发的数据进行拆分和线性编码处理，同时将自己的运动状态广播给附近RSU，进入步骤②。

②RSU通过周围车辆的运动状态建立车辆局部动态坐标轴，该坐标轴是动态的，每隔一定的时间重新创建新的坐标轴。进入步骤③。

③RSU根据车辆的运动状态计算出周围车辆节点的路径近似度，选择下一转发车辆节点。如果目标车辆节点与源车辆不在同一区域，则进入步骤④，否则进入步骤⑤。

④此时各区域中的控制中心通过卫星GPS通信，交换各区域车辆运动状态。源车辆区域中的RSU根据控制中心反馈的另一区域的车辆运动状态，计算各车辆的路径近似度，选择路径近似度最大的车辆作为下一转发车辆节点，进入步骤⑤。

⑤判断编码数据包是否已经被目标车辆成功接收，若是则进入步骤⑥，否则进入步骤③。

⑥目标车辆接收到足够多的编码数据包后，通过h(x,y)=x+y+c和Xi,k=Yi,k(εi,1,εi,2,…,εi,m)-1解码出源数据包。

3 仿真实验与结果分析

采用MOVE和NS-3[15-17]进行仿真实验，评估文中提出的ORLNC协议算法性能。MOVE仿真软件针对VANET快速构造车辆移动模型，NS-3则提供完整网络模拟环境。因此网络模拟软件NS-3中的节点可以根据MOVE设置的车辆运动轨迹的方式运动。将仿真实验的场景设置如下：

仿真实验区域为5 000m×5 000m的正方形区域，并将正方形区域划分成四个2 500m×2 500m的小正方形区域，每个小正方形区域分别有一个控制中心M和多个RSU控制着各区域车辆的数据传输。采用IEEE802.11的MAC协议，每个小区域的车辆分数目别为10,20,30,40，车辆运动速度在5～30m/s中随机取值。数据包的大小设为2kB,1kB,512byte。车辆的通信范围为半径R=300m的圆形区域。车辆向附近RSU以“hello”方式通信的周期TTL=2s，最小有限域设置为GF(2n)。二元函数为h(x,y)=x+y+c，可传递重复使用。仿真时间设置为400s。

文中将ORLNC协议算法与DDR协议算法在传输延时、数据传输效率方面进行比较分析。

DDR算法通过速度矢量聚类算法对邻近范围内的车辆分簇，节点采用基于粒子群优化选举算法周期性计算簇头，由簇头将编码数据包广播给簇内的目标车辆，这样分簇和寻簇头将花费较多的时间，导致车辆间数据转发延时较大。

文中提出的ORLNC协议算法首先在随机线性网络编码上做了改进，改变每次编码时都在最小有限域中随机选取编码系数，而是在初始选择的编码系数中再次使用，可以有效减少选取系数的时间。并且采用基于车辆路径近似度选择下一转发车辆节点，而这路径近似度计算过程由车辆周围的RSU完成，只需将计算结果反馈给车辆，比较结果如图3所示。

图3 转发延时比较图

由图可见，ORLNC的转发延时相较于DDR算法明显降低了。

数据包在网络传输中，会遇到各种外界的干扰，如黑客攻击、数据包丢失等。DDR算法只是将源数据编码处理再转发，有可能编码数据包在传输中发生丢失和破坏，而需再次重传，无法保证数据的正确性和安全性。文中提出的ORLNC协议算法克服了DDR算法消极的保护数据的措施，创建二元函数h(x,y)=x+y+c对源数据包进行初始化处理，相当于对数据包进行加密处理，起到了较好的保密作用。比较结果如图4所示。

由图可见，编码数据包的传输效率明显高于DDR算法。

4 结束语

文中基于随机线性网络编码，提出了一种改进的随机线性网络编码—ORLNC，同时采用基于路径近似度的车辆选择协议。根据车辆能量充足、计算能力强等特点，为确保数据包的稳定性，ORLNC创建了一个二元函数h(x,y)对源数据做初始处理，进而提高车辆通信的准确性和安全性。同时也对初始处理后的数据包编码也做了改进优化，下一次编码时不再从最小有限域中随机选取编码系数，而是使用上一次编码时选取的编码系数。ORLNC协议算法是在车辆密集的场景下提出的，也适用于车辆稀疏场景。最后通过MOVE和NS-3仿真实验，证明了ORLNC协议算法较于DDR可以进一步降低转发延时，提高传输效率。

[1]YeF,RoyS,WangH.Efficientdatadisseminationinvehicularadhocnetworks[J].IEEEJournalonSelectedAreasinCommunications,2012,30(4):769-779.

[2]ZhangX,LiB.Optimizedmultipathnetworkcodinginlossywirelessnetworks[J].IEEEJournalonSelectedAreasinCommunications,2009,27(5):622-634.

[3]HassanabadiB,ValaeeS.ReliableperiodicsafetymessagebroadcastinginVANETsusingnetworkcoding[J].IEEETransactionsonWirelessCommunications,2014,13(3):1284-1297.

[4]MiraniF,BussonA,AdjihC.Improvingdelay-baseddatadisseminationprotocolinVANETswithnetworkcoding[J].REVJournalonElectronicsandCommunications,2013,2(3-4).

[5]HoT,KoetterR,MedardM,etal.Towardarandomoperationofnetworks[J].IEEETransactionsonInformationTheory,2004,50(3):532-537.

[6] Ho T,Médard M,Koetter R,et al.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[7] Kumar R,Dave M. DDDRC:decentralised data dissemination in VANET using raptor codes[J].International Journal of Electronics,2015,102(6):946-966.

[8] Guclu S S,Altilar D T.Downlink utilization with R2V2V communications in clustered vehicular networks[C]//Proc of 9th international symposium on communication systems,networks & digital signal processing.[s.l.]:IEEE,2014:99-104.

[9] 朱闻亚.数据加密技术在计算机网络安全中的应用价值研究[J].制造业自动化,2012,34(6):35-36.

[10] 魏瑞良.计算机网络通信安全中数据加密技术的研究与应用[D].北京:中国地质大学,2013.

[11] 杨 军.网络编码的若干关键问题研究[D].武汉:华中科技大学,2013.

[12] Hult R,Campos G R,Falcone P,et al.Approximate solution to the optimal coordination problem for autonomous vehicles at intersections[R].Sweden:Chalmers University of Technology,2015.

[13] 丁 郁.基于机会通信的车载网络路由关键技术研究[D].北京:北京邮电大学,2013.

[14] 臧新建.从一道证明题来看基础解系的一般证法[J].数学学习与研究,2014(5):74-74.

[15] Henderson T R,Lacage M,Riley G F,et al.Network simulations with the NS-3 simulator[C]//Proc of SIGCOMM demonstration.[s.l.]:[s.n.],2008.

[16] Lan K,Chou C M.Realistic mobility models for vehicular ad hoc network (VANET) simulations[C]//Proc of 8th international conference on ITS telecommunications.[s.l.]:IEEE,2008:362-366.

[17] 陈 林,石林祥,孔亮亮.车辆自组织网络的仿真研究[J].上海第二工业大学学报,2013(1):6-11.

Research on Data Transmission Performance in VANET Based on Network Coding

MA Ning,ZHANG Yi-bing,SHU Yong-an

(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

Through data transmission between Vehicle to Vehicle (V2V) or Vehicles to Infrastructure (V2I) roadside units,vehicular network achieves communication.Vehicular network is different from traditional wireless networks,which has the unique characteristics,such as fast network topology changes,node constraints,intermittent network connectivity and so on.Due to the high speed of vehicle and the obstruction of the barrier in the streets,the vehicle network segmentation is more serious and the routing problem is more complex.Data transmission performance in vehicle network faces change,including channel load,high transmission delay,low bandwidth utilization and so on.In order to improve the efficiency of data transmission and reduce the forwarding delay，an Optimized Random Linear Network Coding (ORLNC) is proposed in the hybrid communication structure (V2V&V2I).Simulation experiments by NS-3 and MOVE show that ORLNC significantly reduces forwarding delay and improves transmission efficiency compared with the DDR.At the same time,this algorithm is not only applied in dense vehicular networks,but also suitable for the transmission of data in sparse scenario.

VANET;V2V;V2I;hybrid communication structure;ORLNC

2015-07-25

2015-10-27

时间：2016-03-22

安徽省自然科学基金项目(1408085MF125)

马 宁(1990-)，男，硕士，研究方向为无线网络；束永安，教授，研究方向为无线网络、下一代网络体系结构。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.098.html

TP393

A

1673-629X(2016)05-0036-04

10.3969/j.issn.1673-629X.2016.05.008