基于网络编码的优化V2R数据传输性能的研究
吴芬芬+王嫣
摘 要： 将路侧设备RSUs作为车载网络VANETs的缓冲点，可缓解车与车V2V之间连通的间歇性问题。然而，由于车辆的快速移动以及RSU短的传输距离，车辆驻留同一个RSU的时间很短。尽管广播技术能够有效地提高广播带宽利用率以及系统响应时间。但RSU采用广播技术前需要获取车辆缓存数据项的先验知识。因此，车辆需要向RSU服务器上传缓存信息，浪费了带宽。为此，针对基于RSUs的VANETs，提出基于网络编码的车与路边设施V2R通信的数据传输算法NCDD。NCDD算法允许车辆不必向RSU服务器上传它们的缓冲信息，并利用网络编码提高RSU的广播性能，仿真结果也证实了NCDD算法能够有效地降低截止期错失率和系统响应时间。
关键词： 车载网络； 路侧设备； 数据传输； 网络编码； 截止期错失率
中图分类号： TN919.3+1?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）11?0127?05
Research on V2R data transmission performance optimization based on network coding
WU Fenfen1， WANG Yan2
（1. Department of Traffic Information Engineering， Henan Communication Vocational Technology College， Zhengzhou 450000， China；
2. School of Information Engineering， Zhongzhou University， Zhengzhou 450044， China）
Abstract： The road side units （RSUs） acting as a buffer point of VANETs （vehicular Ad Hoc networks） can alleviate the intermittent connectivity issue of vehicle?to?vehicle （V2V）. The vehicle spends short time on stopping at the same RSU due to the fast vehicle mobility and short RSU transmission range. Although the broadcast technology can improve the broadcast ban?dwidth usage efficiency and system response time effectively， but the RSU before using broadcast technology needs to acquire the prior knowledge of vehicle′s cached data items. Therefore， the vehicle needs to upload the cache information to the RSU server， which wastes the bandwidth. Aiming at VANETs based on RSUs， a network coding?based data dissemination （NCDD） algorithm of V2R is proposed. The NCDD algorithm allows vehicles not to upload their cache information to RSU server. The network coding is used to improve the RSU broadcast performance. The simulation results verify that the NCDD algorithm can reduce the deadline miss ratio and system response time.
Keywords： vehicular Ad Hoc network； road side unit； data transmission； network coding； deadline miss ratio
0 引 言
作为智能交通系统ITS（Intelligent Transportation System）最有前景的技术，车载网络VANETs（Vehicular Ad Hoc Networks）受到广泛关注。VANETs属于移动自组织网络的特例，其能够提供多类服务，包括安全、交通管理、舒适驾驶以及娱乐[1?3]。典型的VANETs结构如图1所示，车与车之间构成车间通信V2V（Vehicle?to?Vehicle），车与路边设施之间构成V2R（Vehicle?to?RoadSide）通信。
然而，与移动自组织网络不同，VANETs存在鲜明的特性。首先，车辆的快速移动，加剧了网络拓扑变化；其次，VANETs采用基于IEEE 802.p无线通信技术[4]。短的通信距离导致车间连通时间非常短。
为此，在路邊部署RSU，将其作为静态单元，起到通信缓冲作用。在这种情况下，在RSU与车辆间完成有效的数据传输是非常必要的，否则车辆将不能及时获取其所需的数据，这也违背了部署VANETs的目的。为此，本文以V2R通信为对象，研究V2R的数据传输。
按需广播技术广泛应用于无线环境[5]，用于大面积的传输数据。然而，由于传统广播技术每次广播时，仅广播一条数据项DAIT（Data Item）。这种广播策略不能最大化广播信道带宽，可能也无法保持截止期错失率DMR（Deadline Miss Ratio）和系统响应时间的性能。而网络编码是解决此问题的可行办法之一。
利用网络编码技术，将多个DAIT编码成一个广播包，然后再广播[6]。然而，RSU服务器在应用网络编码时，需要获取车辆的请求和缓冲区内的DAIT所有信息[7?8]。将车辆缓存信息上传至服务器，增加了额外开销，也降低了RSU服务器的带宽资源。
为此，本文引用网络编码技术，致使车辆不必上传它们的缓存信息。RSU服务器跟踪车辆请求的DAIT，并利用主干连接[9]向邻居RSU发送缓存更新。此外，假定RSU能够维持在其通信覆盖内的车辆以及它们的位置[10]。本文提出NCDD算法的目的就是减少DMR，并降低系统响应时间。
1 系统模型及约束条件
系统模型如图2所示。每个RSU由请求信道ReqCH（Request CHannel）和响应信道ResCH（Respone CHannel）两个信道组成。当一车辆驶入RSU覆盖范围内，若该车辆在其局部缓冲区内未找到其所需的数据项DAIT（Data Item），它就通过RSU的信道ReqCH发送请求DAIT。
此外，每个RSU为请求包设定了一个服务队列。当不能满足车辆所请求的请求包时，RSU就将该请求包从服务队列中移除。依据调度算法[11]，RSU先选择一个合适的DAIT，然后根据这些被选的DAIT，利用低开销的XOR操作编码，将这些DAIT编码成一个数据包，最后，通过ResCH信道广播该已编码的数据包。
一旦接收了已编码数据包，车辆就利用自己缓存区内的DAIT进行解码，获取自己所需的DAIT，并再存入缓存区。此外，RSU能够知道是哪辆车接收了哪个DAIT。
系统采用文献[12]的LRU（Least Recently Used）缓存替代政策。若已满足请求，就从服务队列移除。此外，若车辆移出当前RSU覆盖范围，进入新的RSU覆盖范围内时，当前RSU就向新RSU发送相应的缓存信息。
2 NCDD算法
2.1 请求包的格式
假定网络内辆车，即个RSU，即若车辆向递交一个请求，且表示为。请求的格式如下所示：
（1）
式中：为的ID号；表示请求的数据DAIT号；表示产生的时间。
假定服从均匀分布：
（2）
式中：表示驻留在RSU内的最长时间，定义如下：
（3）
式中：表示RSU通信覆盖的半径；表示的移动速度。
式（2）中，表示需求的服务时间；表示的截止时间。一旦到达RSU就把从服务队列中移出。而表示移动的方向。
2.2 网络编码
为了编码决策，RSU服务器需要获取车辆的请求和缓冲DAIT信息[7]。因此，引用图论理论[8]。假定，其中顶点集表示车辆产生的请求DAIT集合，具体而言，表示车辆产生的DAIT 同时，利用边集反映内两顶点间关系。
对于任意两个顶点如果满足以下两个条件中的任何一个条件，就存在有向边。
（1） 如果且，即两辆不同的车请求相同的DAIT，则在和间存在边；
（2） 如果且车辆在其缓存区内有DAIT 同时车辆在请求DAIT 而车辆在其缓存区内有DAIT 同时车辆在请求DAIT 换而言之，这两个车辆缓存彼此所请求的DAIT。在这种情况下，在和间也存在边。RSU服务器只要广播车辆通过简单的XOR操作分别可提取DAIT。
针对图，定义一个子图，致使该子图内每两个顶点均有边连通。假定是内的任意一个子图，即相应地，在内请求数据DAIT集表示为
（4）
相应地，假定内所包含的车辆集表示为。
如图3，图4所示，其描述一个图论示例。首先，图2显示了一个RSU包含了5个车辆所请求的DAIT。如车辆请求DAIT为，而车辆请求DAIT为。相应地，图3的右边显示了各车辆的缓存DAIT，如车辆缓存区域存有。
将图3所示5个车辆转化成图，如图4所示。依据各个车辆所请求的DAIT关系，构建车辆的边。其中，黑粗线构成了子图。
令表示一个编码包。在子图内，每个顶点代表一辆车。依据子图的特性对任何车辆如果它便能够从编码包内提出自己所需的DAIT 。因此，只要在內广播编码包，就能使得各相应车辆获取自己所需的数据。
2.3 最大化
接下来，需要讨论的是将多少个DAIT编码成一个数据包。从编码的角度，每个已编码的数据包包含DAIT的个数越多越好，即最大化问题。该问题等价于最大化子图。
对于任意顶点（车辆请求的DAIT为），从图中寻找最大子图。然后，再将中的DAIT集产生一个编码包最后广播此编码包。如图4所示，黑色粗线表示一个最大子图。从图4可知，相应地，最后，RSU服务器就编码内的数据，即然后广播编码数据包。
在图中寻找最大化子图是个NP问题[13]。据此，研究人员提出不同的近似算法。本文采纳文献[14]提出的近似算法求解。
2.4 缓存区域信息更新
由于车辆是非静态的，沿着道路移动。为此，本文引用Manhattan 移动模型[4]模拟车辆移动。NCDD算法利用RSU管理车辆缓存区内的信息，而不是每次在决策编码前，由RSU向车辆申请，并由车辆上传缓存区域信息。如图5所示，最初，没有关于车辆的缓存区域信息。当车辆进入的通信范围内，就产生请求再等待是否能满足其需求。一旦满足，就更新和的缓存区域信息。
当离开的覆盖区域时，RSUi就利用主干连接，先联系到覆盖的下一RSU（RSUj），然后再向其传输车辆的缓存区域信息。注意到，RSUi能够利用知道将驶入新的RSU（RSUj）。随着时间的推移，车辆越来越靠近。
2.5 NCDD算法流程
NCDD算法流程如图6所示。
NCDD算法流程的步骤如下：
步骤1：当RSU从邻居RSU接收到车辆更新缓存信息时，就更新车辆的缓存信息；
步骤2：在RSU的服务队列内增添请求，然后再更新请求的DATI；
步骤3：确认每条请求的服务可行性，即判断每条请求的剩余有效期，移除剩余有效期短于请求服务时间的数据请求；
步骤4：判断RSU服务队列是否为空，如果不为空就依据区域内的DATI和缓冲区域信息构建圖；
步骤5：通过调度算法从服务队列中选择DATI ；
步骤6：找到覆盖的最大子图再编码成一个数据包 然后广播编码包；
步骤7：判断车辆是否离开的覆盖范围。如果没有，回到步骤2；否则就将车辆的缓存信息传输至车辆的下一个RSU（）。
3 性能分析
3.1 仿真平台
本节分析在V2R通信中基于网络编码的数据传输性能，即分析网络编码对数据传输性能的影响。将NCDD算法应用于文献[5]的SIN方案中，记为SIN?NCDD，而没有采用NCDD算法的记为SIN。
仿真场景如图7所示，其中24个RSU，40～120辆车。每个RSU的通信距离为800 m，而车辆的通信范围为300 m。每次独立仿真重复10次，取平均值作为最终的仿真数据。
同时，选择截止期错失率DMR（Deadline Miss Ratio）、期望响应时间ERT（Expected Response Time）、节省带宽率SBR（Saved Bandwidth Ratio）以及平均编码长度AEL（Average Encode Length）分析网络编码算法的性能。其中，DMR等于截止时期错失的请求与总的请求数之比。提出NCDD算法的主要目的就是降低DMR。
3.2 仿真结果
3.2.1 截止期错失率DMR
图8为车辆数的变化对DMR性能的影响。从图8可知，车辆数的增加，增加了截止期错失率。原因在于车辆数的增加提高了网络系统的负担，进而提高了截止期错失率。然而，将SIN?NCDD与SIN方案对比不难发现，SIN?NCDD具有更低的DMR，这说明通过网络编码能够降低错失率，进而提高数据传输性能。SIN?NCDD的平均DMR比SIN降低了近20%。
3.2.2 期望响应时间ERT
期望响应时间ERT随车辆数的变化曲线如图9所示。与截止期错失率类似，期望响应时间ERT随车辆数的增加而上升。此外，不难发现，通过网络编码能够有效地提高系统响应速度，降低响应时间。SIN?NCDD响应时间比SIN降低约18%。
3.2.3 带宽节省率SBR
图10为带宽节省率随车辆数的变化情况。从图10可知，车辆数的增加，提高了带宽节省率。原因在于：车辆数的增加，加大了网络负担，增加了RSU服务队列的请求数，相应地也提高了满足请求的概率。此外，从图10可知，通过网络编码能够有效地提高带宽节省率。
3.2.4 平均编码长度AEL
最后分析了平均编码长度随车辆数的变化情况。平均编码长度越长，编码性能越好，所传输的编码数据包越少。从图11可知，通过网络编码技术使得每广播一个数据包，其包含更多的数据项DATI，反之，没有采用网络编码技术，每次只广播一个数据项，限制了带宽利用率。
图11 平均编码长度
4 结 语
在传统的基于多RSU的车载网络中，一个RSU每广播一个数据包只能传输一个数据项，这限制了广播带宽利用率，也约束了响应时间。为此，本文提出新的编码算法。在编码过程中，无需车辆向RSU上传缓存区域信息，提高了带宽利用率，也降低了响应时间。将NCDD算法应用于SIN方案进行实验。实验数据表明，通过融入网络编码算法，截止期错失率下降了20%，带宽节省率提高了近30%。
参考文献
[1] DING G， WANG J， WU Q， et al. Spectrum sensing in opportunity?heterogeneous cognitive sensor networks： how to cooperate [J]. IEEE sensors journal， 2013， 13（11）： 4247?4255.
[2] MALEKI S， PANDHARIPANDE A， LEUS G. Energy?efficient distributed spectrum sensing for cognitive sensor networks [J]. IEEE sensors journal， 2011， 11（3）： 565?573.
[3] SHARMA R K， WALLACE J W. Correlation?based sensing for cognitive radio networks： bounds and experimental assessment [J]. IEEE sensors journal， 2011， 11（3）： 657?666.
[4] BARBA C， MEZHER A M， IGARTUA M， et al. Available bandwidth?aware routing in urban vehicular Ad?Hoc networks [C]// Proceedings of 2012 IEEE Vehicular Technology Confe?rence. [S.l.]： IEEE， 2012： 1?5.
[5] XU J， TANG X， LEE W C. Time?critical on?demand data broadcast algorithms， analysis and performance evaluation [J]. IEEE transactions on parallel and distributed systems， 2016， 17（1）： 3?14.
[6] AHLSWEDE R， CAI N， LI S Y R， et al. Network information flow [J]. IEEE transactions on information theory， 2010， 46（4）： 1204?1216.
[7] BIRK Y， KOL T. Coding on demand by an informed source for efficient broadcast of different supplemental data to caching clients [J]. IEEE/ACM transactions on networking， 2015， 14（SI）： 2825?2830.
[8] CHEN J， LEE V C S， LIU K， et al. Efficient processing of requests with network coding in on?demand data broadcast environments [J]. Information sciences， 2013， 232（5）： 27?43.
[9] ALI G G M N， CHAN E， LI W Z. Supporting real?time multiple data items query in multi?RSU vehicular Ad Hoc networks [J]. Journal of systems and software， 2013， 86（8）： 2127?2142.
[10] LIU Z Y， ZHOU J G， ZHAO T， et al. An opportunistic approach to enhance the geographical source routing protocol for vehicular ad hoc networks [C]// Proceedings of 2009 IEEE 70th Vehicular Technology Conference. [S.l.]： IEEE， 2009： 1?5.
[11] ALI N， RAHMAN A， CHONG J， et al. On efficient data dissemination using network coding in multi?RSU vehicular Ad Hoc networks [J]. IEEE transactions on computer， 2016， 3（4）： 45?51.
[12] ZHAN C， LEE V C S， WANG J， et al. Coding?based data broadcast scheduling in on?demand broadcast [J]. IEEE tran?sactions on wireless communications， 2011， 10（11）： 3774?3783.
[13] KARP R. Reducibility among combination orial problems [J]. Complexity of computer computations， 2013（2）： 85?103.
[14] DHARWADKER A. The clique algorithm [EB/OL]. [2016?05?12]. http：//www.Dharwadker.org/clique/，2016.
摘 要： 将路侧设备RSUs作为车载网络VANETs的缓冲点，可缓解车与车V2V之间连通的间歇性问题。然而，由于车辆的快速移动以及RSU短的传输距离，车辆驻留同一个RSU的时间很短。尽管广播技术能够有效地提高广播带宽利用率以及系统响应时间。但RSU采用广播技术前需要获取车辆缓存数据项的先验知识。因此，车辆需要向RSU服务器上传缓存信息，浪费了带宽。为此，针对基于RSUs的VANETs，提出基于网络编码的车与路边设施V2R通信的数据传输算法NCDD。NCDD算法允许车辆不必向RSU服务器上传它们的缓冲信息，并利用网络编码提高RSU的广播性能，仿真结果也证实了NCDD算法能够有效地降低截止期错失率和系统响应时间。
关键词： 车载网络； 路侧设备； 数据传输； 网络编码； 截止期错失率
中图分类号： TN919.3+1?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）11?0127?05
Research on V2R data transmission performance optimization based on network coding
WU Fenfen1， WANG Yan2
（1. Department of Traffic Information Engineering， Henan Communication Vocational Technology College， Zhengzhou 450000， China；
2. School of Information Engineering， Zhongzhou University， Zhengzhou 450044， China）
Abstract： The road side units （RSUs） acting as a buffer point of VANETs （vehicular Ad Hoc networks） can alleviate the intermittent connectivity issue of vehicle?to?vehicle （V2V）. The vehicle spends short time on stopping at the same RSU due to the fast vehicle mobility and short RSU transmission range. Although the broadcast technology can improve the broadcast ban?dwidth usage efficiency and system response time effectively， but the RSU before using broadcast technology needs to acquire the prior knowledge of vehicle′s cached data items. Therefore， the vehicle needs to upload the cache information to the RSU server， which wastes the bandwidth. Aiming at VANETs based on RSUs， a network coding?based data dissemination （NCDD） algorithm of V2R is proposed. The NCDD algorithm allows vehicles not to upload their cache information to RSU server. The network coding is used to improve the RSU broadcast performance. The simulation results verify that the NCDD algorithm can reduce the deadline miss ratio and system response time.
Keywords： vehicular Ad Hoc network； road side unit； data transmission； network coding； deadline miss ratio
0 引 言
作为智能交通系统ITS（Intelligent Transportation System）最有前景的技术，车载网络VANETs（Vehicular Ad Hoc Networks）受到广泛关注。VANETs属于移动自组织网络的特例，其能够提供多类服务，包括安全、交通管理、舒适驾驶以及娱乐[1?3]。典型的VANETs结构如图1所示，车与车之间构成车间通信V2V（Vehicle?to?Vehicle），车与路边设施之间构成V2R（Vehicle?to?RoadSide）通信。
然而，与移动自组织网络不同，VANETs存在鲜明的特性。首先，车辆的快速移动，加剧了网络拓扑变化；其次，VANETs采用基于IEEE 802.p无线通信技术[4]。短的通信距离导致车间连通时间非常短。
为此，在路邊部署RSU，将其作为静态单元，起到通信缓冲作用。在这种情况下，在RSU与车辆间完成有效的数据传输是非常必要的，否则车辆将不能及时获取其所需的数据，这也违背了部署VANETs的目的。为此，本文以V2R通信为对象，研究V2R的数据传输。
按需广播技术广泛应用于无线环境[5]，用于大面积的传输数据。然而，由于传统广播技术每次广播时，仅广播一条数据项DAIT（Data Item）。这种广播策略不能最大化广播信道带宽，可能也无法保持截止期错失率DMR（Deadline Miss Ratio）和系统响应时间的性能。而网络编码是解决此问题的可行办法之一。
利用网络编码技术，将多个DAIT编码成一个广播包，然后再广播[6]。然而，RSU服务器在应用网络编码时，需要获取车辆的请求和缓冲区内的DAIT所有信息[7?8]。将车辆缓存信息上传至服务器，增加了额外开销，也降低了RSU服务器的带宽资源。
为此，本文引用网络编码技术，致使车辆不必上传它们的缓存信息。RSU服务器跟踪车辆请求的DAIT，并利用主干连接[9]向邻居RSU发送缓存更新。此外，假定RSU能够维持在其通信覆盖内的车辆以及它们的位置[10]。本文提出NCDD算法的目的就是减少DMR，并降低系统响应时间。
1 系统模型及约束条件
系统模型如图2所示。每个RSU由请求信道ReqCH（Request CHannel）和响应信道ResCH（Respone CHannel）两个信道组成。当一车辆驶入RSU覆盖范围内，若该车辆在其局部缓冲区内未找到其所需的数据项DAIT（Data Item），它就通过RSU的信道ReqCH发送请求DAIT。
此外，每个RSU为请求包设定了一个服务队列。当不能满足车辆所请求的请求包时，RSU就将该请求包从服务队列中移除。依据调度算法[11]，RSU先选择一个合适的DAIT，然后根据这些被选的DAIT，利用低开销的XOR操作编码，将这些DAIT编码成一个数据包，最后，通过ResCH信道广播该已编码的数据包。
一旦接收了已编码数据包，车辆就利用自己缓存区内的DAIT进行解码，获取自己所需的DAIT，并再存入缓存区。此外，RSU能够知道是哪辆车接收了哪个DAIT。
系统采用文献[12]的LRU（Least Recently Used）缓存替代政策。若已满足请求，就从服务队列移除。此外，若车辆移出当前RSU覆盖范围，进入新的RSU覆盖范围内时，当前RSU就向新RSU发送相应的缓存信息。
2 NCDD算法
2.1 请求包的格式
假定网络内辆车，即个RSU，即若车辆向递交一个请求，且表示为。请求的格式如下所示：
（1）
式中：为的ID号；表示请求的数据DAIT号；表示产生的时间。
假定服从均匀分布：
（2）
式中：表示驻留在RSU内的最长时间，定义如下：
（3）
式中：表示RSU通信覆盖的半径；表示的移动速度。
式（2）中，表示需求的服务时间；表示的截止时间。一旦到达RSU就把从服务队列中移出。而表示移动的方向。
2.2 网络编码
为了编码决策，RSU服务器需要获取车辆的请求和缓冲DAIT信息[7]。因此，引用图论理论[8]。假定，其中顶点集表示车辆产生的请求DAIT集合，具体而言，表示车辆产生的DAIT 同时，利用边集反映内两顶点间关系。
对于任意两个顶点如果满足以下两个条件中的任何一个条件，就存在有向边。
（1） 如果且，即两辆不同的车请求相同的DAIT，则在和间存在边；
（2） 如果且车辆在其缓存区内有DAIT 同时车辆在请求DAIT 而车辆在其缓存区内有DAIT 同时车辆在请求DAIT 换而言之，这两个车辆缓存彼此所请求的DAIT。在这种情况下，在和间也存在边。RSU服务器只要广播车辆通过简单的XOR操作分别可提取DAIT。
针对图，定义一个子图，致使该子图内每两个顶点均有边连通。假定是内的任意一个子图，即相应地，在内请求数据DAIT集表示为
（4）
相应地，假定内所包含的车辆集表示为。
如图3，图4所示，其描述一个图论示例。首先，图2显示了一个RSU包含了5个车辆所请求的DAIT。如车辆请求DAIT为，而车辆请求DAIT为。相应地，图3的右边显示了各车辆的缓存DAIT，如车辆缓存区域存有。
将图3所示5个车辆转化成图，如图4所示。依据各个车辆所请求的DAIT关系，构建车辆的边。其中，黑粗线构成了子图。
令表示一个编码包。在子图内，每个顶点代表一辆车。依据子图的特性对任何车辆如果它便能够从编码包内提出自己所需的DAIT 。因此，只要在內广播编码包，就能使得各相应车辆获取自己所需的数据。
2.3 最大化
接下来，需要讨论的是将多少个DAIT编码成一个数据包。从编码的角度，每个已编码的数据包包含DAIT的个数越多越好，即最大化问题。该问题等价于最大化子图。
对于任意顶点（车辆请求的DAIT为），从图中寻找最大子图。然后，再将中的DAIT集产生一个编码包最后广播此编码包。如图4所示，黑色粗线表示一个最大子图。从图4可知，相应地，最后，RSU服务器就编码内的数据，即然后广播编码数据包。
在图中寻找最大化子图是个NP问题[13]。据此，研究人员提出不同的近似算法。本文采纳文献[14]提出的近似算法求解。
2.4 缓存区域信息更新
由于车辆是非静态的，沿着道路移动。为此，本文引用Manhattan 移动模型[4]模拟车辆移动。NCDD算法利用RSU管理车辆缓存区内的信息，而不是每次在决策编码前，由RSU向车辆申请，并由车辆上传缓存区域信息。如图5所示，最初，没有关于车辆的缓存区域信息。当车辆进入的通信范围内，就产生请求再等待是否能满足其需求。一旦满足，就更新和的缓存区域信息。
当离开的覆盖区域时，RSUi就利用主干连接，先联系到覆盖的下一RSU（RSUj），然后再向其传输车辆的缓存区域信息。注意到，RSUi能够利用知道将驶入新的RSU（RSUj）。随着时间的推移，车辆越来越靠近。
2.5 NCDD算法流程
NCDD算法流程如图6所示。
NCDD算法流程的步骤如下：
步骤1：当RSU从邻居RSU接收到车辆更新缓存信息时，就更新车辆的缓存信息；
步骤2：在RSU的服务队列内增添请求，然后再更新请求的DATI；
步骤3：确认每条请求的服务可行性，即判断每条请求的剩余有效期，移除剩余有效期短于请求服务时间的数据请求；
步骤4：判断RSU服务队列是否为空，如果不为空就依据区域内的DATI和缓冲区域信息构建圖；
步骤5：通过调度算法从服务队列中选择DATI ；
步骤6：找到覆盖的最大子图再编码成一个数据包 然后广播编码包；
步骤7：判断车辆是否离开的覆盖范围。如果没有，回到步骤2；否则就将车辆的缓存信息传输至车辆的下一个RSU（）。
3 性能分析
3.1 仿真平台
本节分析在V2R通信中基于网络编码的数据传输性能，即分析网络编码对数据传输性能的影响。将NCDD算法应用于文献[5]的SIN方案中，记为SIN?NCDD，而没有采用NCDD算法的记为SIN。
仿真场景如图7所示，其中24个RSU，40～120辆车。每个RSU的通信距离为800 m，而车辆的通信范围为300 m。每次独立仿真重复10次，取平均值作为最终的仿真数据。
同时，选择截止期错失率DMR（Deadline Miss Ratio）、期望响应时间ERT（Expected Response Time）、节省带宽率SBR（Saved Bandwidth Ratio）以及平均编码长度AEL（Average Encode Length）分析网络编码算法的性能。其中，DMR等于截止时期错失的请求与总的请求数之比。提出NCDD算法的主要目的就是降低DMR。
3.2 仿真结果
3.2.1 截止期错失率DMR
图8为车辆数的变化对DMR性能的影响。从图8可知，车辆数的增加，增加了截止期错失率。原因在于车辆数的增加提高了网络系统的负担，进而提高了截止期错失率。然而，将SIN?NCDD与SIN方案对比不难发现，SIN?NCDD具有更低的DMR，这说明通过网络编码能够降低错失率，进而提高数据传输性能。SIN?NCDD的平均DMR比SIN降低了近20%。
3.2.2 期望响应时间ERT
期望响应时间ERT随车辆数的变化曲线如图9所示。与截止期错失率类似，期望响应时间ERT随车辆数的增加而上升。此外，不难发现，通过网络编码能够有效地提高系统响应速度，降低响应时间。SIN?NCDD响应时间比SIN降低约18%。
3.2.3 带宽节省率SBR
图10为带宽节省率随车辆数的变化情况。从图10可知，车辆数的增加，提高了带宽节省率。原因在于：车辆数的增加，加大了网络负担，增加了RSU服务队列的请求数，相应地也提高了满足请求的概率。此外，从图10可知，通过网络编码能够有效地提高带宽节省率。
3.2.4 平均编码长度AEL
最后分析了平均编码长度随车辆数的变化情况。平均编码长度越长，编码性能越好，所传输的编码数据包越少。从图11可知，通过网络编码技术使得每广播一个数据包，其包含更多的数据项DATI，反之，没有采用网络编码技术，每次只广播一个数据项，限制了带宽利用率。
图11 平均编码长度
4 结 语
在传统的基于多RSU的车载网络中，一个RSU每广播一个数据包只能传输一个数据项，这限制了广播带宽利用率，也约束了响应时间。为此，本文提出新的编码算法。在编码过程中，无需车辆向RSU上传缓存区域信息，提高了带宽利用率，也降低了响应时间。将NCDD算法应用于SIN方案进行实验。实验数据表明，通过融入网络编码算法，截止期错失率下降了20%，带宽节省率提高了近30%。
参考文献
[1] DING G， WANG J， WU Q， et al. Spectrum sensing in opportunity?heterogeneous cognitive sensor networks： how to cooperate [J]. IEEE sensors journal， 2013， 13（11）： 4247?4255.
[2] MALEKI S， PANDHARIPANDE A， LEUS G. Energy?efficient distributed spectrum sensing for cognitive sensor networks [J]. IEEE sensors journal， 2011， 11（3）： 565?573.
[3] SHARMA R K， WALLACE J W. Correlation?based sensing for cognitive radio networks： bounds and experimental assessment [J]. IEEE sensors journal， 2011， 11（3）： 657?666.
[4] BARBA C， MEZHER A M， IGARTUA M， et al. Available bandwidth?aware routing in urban vehicular Ad?Hoc networks [C]// Proceedings of 2012 IEEE Vehicular Technology Confe?rence. [S.l.]： IEEE， 2012： 1?5.
[5] XU J， TANG X， LEE W C. Time?critical on?demand data broadcast algorithms， analysis and performance evaluation [J]. IEEE transactions on parallel and distributed systems， 2016， 17（1）： 3?14.
[6] AHLSWEDE R， CAI N， LI S Y R， et al. Network information flow [J]. IEEE transactions on information theory， 2010， 46（4）： 1204?1216.
[7] BIRK Y， KOL T. Coding on demand by an informed source for efficient broadcast of different supplemental data to caching clients [J]. IEEE/ACM transactions on networking， 2015， 14（SI）： 2825?2830.
[8] CHEN J， LEE V C S， LIU K， et al. Efficient processing of requests with network coding in on?demand data broadcast environments [J]. Information sciences， 2013， 232（5）： 27?43.
[9] ALI G G M N， CHAN E， LI W Z. Supporting real?time multiple data items query in multi?RSU vehicular Ad Hoc networks [J]. Journal of systems and software， 2013， 86（8）： 2127?2142.
[10] LIU Z Y， ZHOU J G， ZHAO T， et al. An opportunistic approach to enhance the geographical source routing protocol for vehicular ad hoc networks [C]// Proceedings of 2009 IEEE 70th Vehicular Technology Conference. [S.l.]： IEEE， 2009： 1?5.
[11] ALI N， RAHMAN A， CHONG J， et al. On efficient data dissemination using network coding in multi?RSU vehicular Ad Hoc networks [J]. IEEE transactions on computer， 2016， 3（4）： 45?51.
[12] ZHAN C， LEE V C S， WANG J， et al. Coding?based data broadcast scheduling in on?demand broadcast [J]. IEEE tran?sactions on wireless communications， 2011， 10（11）： 3774?3783.
[13] KARP R. Reducibility among combination orial problems [J]. Complexity of computer computations， 2013（2）： 85?103.
[14] DHARWADKER A. The clique algorithm [EB/OL]. [2016?05?12]. http：//www.Dharwadker.org/clique/，2016.
