2. 国家电网 莱芜供电公司, 山东 莱芜 271100
2. Laiwu Electricity Corporation, State Grid Corporation of China, Laiwu Shandong 271100, China
车载自组织网络(Vehicular Ad Hoc Network，VANET)[1]，采用IEEE 802.11p[2]标准，实现车辆与车辆(Vehicle-to-Vehicle，V2V)或者车辆与路边单元之间(Vehicle-to-Infrastructure，V2I)的通信[3]。车载自组织网络继承了移动无线自组织网络的特性：分布式操作、宽带有限、节点移动性与网络拓扑动态性等[4]。除此之外，它还具有通信环境复杂、链路易断的难点[5]。因此，关注转发内容的数据分发方式将比规定目的地址的网络传输方式更适用于车载自组织网络。而命名数据网络(Named Data Networking，NDN)[6]关注的就是消息内容，因此命名数据网络技术在车载自组织网络中会有很大的应用前景。
对命名数据网络的研究也随着它的兴起越来越多，一些研究从优化兴趣列表入手[7]，另外也有关注消息存储列表的访问速度[8]。但是这些都只是关注命名数据网络本身，对于它的应用还没有进行太多讨论。关于命名数据网络技术在车载自组织网络的应用，近年来已经出现了相关的研究成果[9-11]：文献[9]提出了根据距离选择生产者发送数据的消息分发算法，文献[10]提出了通过针对不同类型的消息设置不同的定时器从而减少冲突的命名数据网络消息分发算法，文献[11]则提出了一种结合生产者地理位置的命名数据网络分发算法来提高分发效率。但是这些工作还只是简单地将NDN的方法应用到车载网络中，对于车载自组织网络与NDN结合之后影响数据分发的因素考虑得还不够全面，相关的算法和协议还不能很好地发挥车载自组织网络的特性。
本文设计并改进了基于命名数据网络的车载自组织网络数据分发机制，其主要创新在于结合了车载自组织网络的特点，根据路段建立路由，并根据车辆的自主接包功能实现建立和重建表格。另外，算法中消息的分发还综合采用了最远距离优先转发和设置定时器的思想，并且增加消息类型确保消息分发的稳定性。最后进行实验仿真，并与根据文献[12]提出的算法进行对比，分析算法性能。由于本文考虑的是一个连通的车载自组织网络之间的通信，而文献[12]中提出的“data mule”这一角色，是在两个不连通的网络中实现消息的传递，以达到资源共享的作用。“data mule”转发数据所带来的开销和延迟对于本文所有车辆都在一个连通的网络状态下来说，是没有意义的。因此，“data mule”这一角色不在本文的算法讨论范围内。
1 命名数据网络简介在基于TCP/IP协议的网络中，数据分组是以通信末端的IP地址命名的。但是随着互联网的发展，人们更注重于信息的获取，而不是仅仅关注两点之间的通信。命名数据网络(NDN)不关心消息存放的位置，而是关注消息的内容，因此很好地满足了人们对于信息检索的需求。图 1展示了IP协议架构和NDN架构的不同之处。从图中可以看出，在沙漏的细腰处，NDN的架构使用了内容模块替代了IP架构的IP地址。
|
图 1 IP协议与NDN架构的细腰沙漏模型 Figure 1 Waist hourglass of Internet protocols and NDN architecture |
命名数据网络架构包括两种消息类型、三种节点角色以及三种数据结构。
两种消息类型 兴趣包(Interest Packet)和数据包(Data Packet)。图 2展示了两种消息类型的数据结构。节点请求数据时，会发送兴趣包，其中记录着需要的数据的名字。如果节点收到兴趣包，且有对应的数据包，则会回复数据包，并根据兴趣包的转发路径原路返回到请求该数据的节点。
|
图 2 兴趣分组与数据分组的数据结构 Figure 2 Data structure of interest packet and data packet |
三种节点角色 生产者(Producer)、消费者(Consumer)和转发者(Forwarder)。生产者是产生并拥有某资源的节点，它定时广播信息告知其他节点自己拥有的资源。消费者是请求某资源的节点。而转发者是负责转发各种信息的节点。
三种数据结构 转发信息表(Forwarding Information Base,FIB)、待处理兴趣表(Pending Interest Table,PIT)和数据分组缓存(Content Store,CS)。FIB用于记录资源的路由信息，PIT用于记录收到的兴趣包及其转发路径上的上一跳，CS用于缓存数据包。
在命名数据网络中，生产者首先广播已有的资源，其他节点根据收到的消息，建立FIB。消费者需要某种数据时，发送兴趣包请求数据。收到兴趣包的节点，如果CS中有该数据，则直接回复数据包；如果没有，则把兴趣包信息加入到该节点的PIT中。然后查询FIB，如果有相应的数据表项，则从对应接口发出去，否则就丢弃。收到数据包的节点，如果该节点的PIT有对应的兴趣包表项，则缓存下来，并按照PIT中记录的接口发出去，否则就丢弃该数据包。图 3展示了以上路由形式。
|
图 3 命名数据网络路由示意图 Figure 3 Routing diagram of NDN |
本章将详细介绍基于命名数据网络的车载自组织网络数据分发算法。算法分设计分为三个方面：路由建立、资源探测以及数据请求。
2.1 基于命名数据网络技术的消息转发模型算法根据路段信息建立路由，并根据建立的路由转发数据。为了更好地理解该算法，首先对算法的模型进行介绍。
2.1.1 系统角色本文提出的算法沿用了命名数据网络中的三种节点角色：生产者(Producer)、消费者(Consumer)和转发者(Forwarder)。
生产者 产生并拥有某资源的车辆节点。当车辆产生并拥有了某个资源时，就会广播告诉其他车辆。当收到消费者发来的兴趣包时，回复对应数据包。当收到探测包时，回复确认包。
消费者 请求资源的车辆节点。当车辆节点需要某资源且FIB中有对应记录时，发送兴趣包请求资源。当FIB没有记录时，广播探测包寻找该资源。
转发者 转发消息的车辆节点。收到资源包时，根据资源包信息建立FIB。收到兴趣包时，根据FIB转发兴趣包，并建立PIT。收到数据包时，根据PIT转发出去，并按照规定缓存数据包到CS。同时还负责转发探测包和确认包。
2.1.2 消息类型除了沿用NDN中的兴趣包和数据包，本文提出的算法还包括另外3种消息类型：探测包(Detect Packet)、确认包(Confirm Packet)、心跳包(Hello Packet)。在本算法中，所有消息类型的最大转发跳数(Time To Live,TTL)均为15，即TTL不大于15，当转发的路段数到达15时，消息将不再被转发。
兴趣包 消费者需要某数据时，就会发送兴趣包请求该数据。格式如图 4所示。
|
图 4 兴趣包格式 Figure 4 Format of interest packet |
Name域保存的是数据名字；序列号(Nonce)保证兴趣包的唯一性；跳数标签(Hop Count Tag)保存的是该兴趣包被转发的次数，当到达最大值，该兴趣包将不会再被转发；当前路段(Current Section)保存的是兴趣包转发过来的路段；下一跳路段(Next Section)保存的是兴趣包即将发送到的路段，通过查询FIB得到。
数据包 生产者会根据收到的兴趣包回发数据包。格式如图 5所示。
|
图 5 数据包格式 Figure 5 Format of data packet |
数据包的名字(Name)和跳数标签(Hop Count Tag)的作用与上述兴趣包的一样。签名(Signature)用于保证数据包的唯一性；下一跳路段(Next Section)通过查询PIT得到该数据包的下一跳路段；载荷(Payload)保存了数据的内容。
资源包 资源包属于一种特殊的数据包，用于生产者广播告知其他车辆节点它拥有的资源数据，其结构与数据包一样。
探测包 当消费者想要某资源数据，但是它的FIB没有记录该资源时，广播探测包，寻找对应资源。格式如图 6所示。
|
图 6 探测包格式 Figure 6 Format of detect packet |
其中名字、序列号、跳数标签、当前路段与上文兴趣包的作用一样。路段列表(Section List)记录探测包走过的路段。
确认包 当有生产者收到探测包并拥有对应资源时，回复确认包。格式如图 7。
|
图 7 确认包格式 Figure 7 Format of confirm packet |
TTL保存的是消费者到资源拥有者的跳数，用于判断并找出跳数最小的路径。其他数据域与探测包的数据域作用一样。
心跳包 节点通过广播心跳包与通信距离内的车辆节点建立邻居关系，交换车辆的坐标、速度等信息。
2.1.3 数据结构本文提出的算法拥有三种数据结构：转发信息表(Forwarding Information Base,FIB)、待处理兴趣表(Pending Interest Table,PIT)和数据分组缓存(Content Store，CS)。
转发信息表(FIB) 当节点收到资源包时，根据资源包的信息建立FIB。转发信息表主要包含下一跳路段(next section)和到达该路段所需要的跳数(TTL)。当节点收到兴趣包时，根据FIB的记录，转发出去。数据结构如图 8所示。
|
图 8 转发信息表结构 Figure 8 Structure of forwarding information base |
待处理兴趣表(PIT) 当车辆节点收到兴趣包并且需要转发出去时，就在PIT中记录兴趣包的相关信息，包括资源名字、上一跳路段等。当该节点收到了兴趣包所对应的数据包时，就根据对应PIT表项记录的路段信息转发出去并删除该PIT表项。数据结构如图 9所示。
|
图 9 待处理兴趣表结构 Figure 9 Structure of pending interest table |
数据分组缓存(CS) 数据分组用于缓存节点收到的数据，并可以在需要的时候发送给消费者。本算法的缓存技术采用先进先出(First In First Out,FIFO)的替换策略，当缓存空间存满数据时，就采用FIFO的策略调整缓存数据。数据结构如图 10所示。
|
图 10 数据分组缓存结构 Figure 10 Structure of content store |
当生产者产生了某资源时，主动广播资源包，告知其他车辆节点所拥有的资源。为了保证网络的连通性，资源包的转发在每个十字路口的每个方向都存在，并且要求每个路段都有车辆参与转发。
算法的主要流程如下：
1) 生产者产生某资源时，广播资源包。
2) 车辆收到资源包，如果资源包无效(序列号重复且TTL大于或等于15) 则丢弃。否则查看自己的FIB，如果有对应的资源表项，则保存TTL更小的资源包信息；否则新建FIB表项。
3) 更新资源包中的必要信息，然后根据距离设置定时器，距离上一跳越远定时器越短。计时结束之前，若没有收到其他节点广播的同样的资源包，则将该资源包发送出去。
算法伪代码如算法1所示。
算法1 路由建立算法(资源包转发)。
Input: resource packet
Initialize: none
Function ForwardResourcePacket (ResourcePacket)
if repeat or TTL>15
return
if (!FIB.Find(ResourcePacket.GetName()))
FIB.Add(ResourcePacket)
else
FIB.Update(ResourcePacket)
set waiting timer
if no such forwarded package received from others in this section
forward(ResourcePacket)
return
end function
2.3 资源探测探测资源算法主要两个部分：探测包的转发和确认包的转发。
算法的主要流程：
1) 消费者发送探测包寻找资源。
2) 车辆收到探测包后，若无效将其丢弃。否则，查询自己的CS和FIB，如果有对应资源的记录，则回复确认包。否则将自己所在的路段加入探测包，并根据转发资源包的方法设置定时器转发该探测包。
3) 当车辆收到确认包时，如果FIB没有该确认包对应的资源表项，则建立FIB表项；否则，如果自己路段不在确认包中保存的下一跳路段上，则丢弃；若在，则设置定时器，按照转发探测包的方法转发。
探测包的转发算法伪代码如算法2，确认包的转发算法伪代码如表算法3。
算法2 探测包转发算法。
Input: detect packet
Initialize: none
Function ForwardDetectingPacket (DetectPacket)
if repeat or TTL>15
return
if (FIB.Find(DetectPacket.GetName()) or
CS.Find(DetectPacket.GetName()))
send(ConfirmPacket)
else
add this->section into packet
set waiting timer
if no such forwarded package received from others in this section
forward (DetectPacket)
return
end function
算法3 确认包转发算法。
Input: confirming packet
Initialize: none
Function ForwardConfirmingPacket (ConfirmPacket)
if (!FIB.Find(ConfirmPacket.GetName()))
FIB.Add(ConfirmPacket)
if this->section==next section
set waiting timer
if no such forwarded package received from others
forward (ConfirmPacket)
return
end function
2.4 数据请求数据请求算法主要包括兴趣包转发和数据包转发两个方面。
算法的主要流程：
1) 消费者需要某资源时，根据FIB记录发送兴趣包请求数据。
2) 车辆收到兴趣包后，判断是否有效。然后查询自己的CS，如果保存有该资源，则回复数据包；否则，判断路段信息，如果彼此路段不同，则丢弃。如果相同就检查PIT，若有对应资源记录则更新对应表项；否则查询FIB，如果存在对应的FIB表项，则根据该FIB表项记录设置定时器把兴趣包发送出去，并新建PIT表项。否则，丢弃该兴趣包。
3) 车辆节点收到数据包后查询自己的PIT，如果没有对应表项，则不处理。若有，将数据缓存到CS，并删除对应PIT表项，设置定时器，转发该数据包。
兴趣包的转发算法伪代码如算法4，数据包的转发算法伪代码如算法5。
算法4 兴趣包的转发算法。
Input: interest packet
Initialize: none
Function ForwardInterestPacket (InterestPacket)
if repeat or TTL > 15
return
if (CS. Find(InterestPacket.GetName())
send(DataPacket)
return
if this->section==next section
if PIT.Find(InterestPacket.GetName())
PIT.Update()
return
else
PIT.Add(InterestPacket)
set waiting timer
if no sunch forward package received from others
forward Interest Packet
return
end function
算法5 数据包转发算法。
Input: data packet
Initialize: none
Function ForwardDataPacket (DataPacket)
if PIT.Find(DataPacket.GetName())
CS.Add(DataPacket)
PIT.Delete(DataPacket)
Set waitint timer
Forward(DataPacket)
return
end function
2.5 对比实验由于命名数据网络是近年新兴的技术，对于其在车载自组织网络中的应用还是比较有限的。为了验证改进算法的有效性，采用了根据文献[12]提出的传统的命名数据网络数据分发算法作为对比。值得一提的是，文献[12]提出了“data mule”这一节点角色，该角色的主要作用是使得两个不连通的网络能够进行数据共享和传输，但是，本文的重点在于考虑一个连通网络中车辆之间的通信，“data mule”转发数据所带来的开销和延迟对于本文所有车辆都在一个连通的网络状态下来说，是没有意义的。所以，算法不考虑这一角色。本文主要将该算法与本文提出的改进算法应用于车载自组织网络数据分发中，并在相同的仿真环境下进行仿真实验，从而得出结论。
传统命名数据网络数据(Traditional Named Data Networking,TRA-NDN)分发算法与提出的改进算法(Improved Named Data Networking,Improved-NDN)最大的不同在于：TRA-NDN的FIB和PIT中记录的下一跳为某一节点，因此是以节点信息作为建立路由依据的；但是Improved-NDN是以路段为依据建立路由的。而且传统的命名数据网络的消息类型还不包括本文提出的改进算法中包含的探测包(Detect Packet)、确认包(Confirm Packet)和心跳包(Hello Packet)。但是为了实验在同一条件下进行，本文将这三种消息类型也加入到对比实验中。
2.6 网络连通性本文所提出的算法是假设网络始终联通的。在路由建立阶段，算法假设资源包的转发在每个十字路口的每个方向都存在。因为本文的算法考虑的是在一个密集而且连通的车载自组织网络中，任意两个节点都能彼此进行通信。
为了应对网络断连的情况，可以在本文算法中引入一些附加机制。一种方案是引入重传机制。根据链路的断开情况，重传数据包。如果断开的时间会比较久，可以考虑采用延容忍网络(Delay Tolerant Network，DTN)的存储—转发机制。由断连处的车辆节点携带数据包，遇到邻居节点后再进行转发。这方面已经有大量的研究和解决算法，就不具体讨论。
3 实验仿真结果与分析为了验证本文提出的基于命名数据网络技术的数据分发算法的性能，本章将对算法进行实验仿真。本次仿真采用基于ns-3模拟器的ndnSIM(Named Data Networking Simulator)仿真工具和SUMO(Simulation of Urban MObility)仿真器结合的方法在Linux系统下进行仿真实验。
3.1 仿真环境ns-3是一个离散时间模拟器，而ndnSIM是为了给NDN研究提供一个通用的仿真平台而开发的基于ns-3的模块化的仿真工具。SUMO是一个道路交通仿真软件。本实验通过SUMO产生车辆移动模型，并将其导入到ndnSIM仿真环境中，模拟出车载自组织网络中的车辆移动，并基于ndnSIM工具实现转发策略。
要特别说明的是SUMO生成的车辆网络拓扑中，道路是双向的，命名彼此不相同，但是本文提出的改进算法将其视为同一路段，即不考虑道路的方向问题。对比实验以节点作为建立路由依据，因此不考虑路段信息。
3.1.1 仿真配置本次的仿真实验，采用的是6×6的方格网状路网结构。在路网中，有7条垂直的道路和7条水平的道路。每条都是标准的8车道道路。两条道路的交叉点为十字路口。两个相邻的十字路口之间的道路为一个路段，长度固定为500 m。仿真选定9个固定节点作为生产者，产生10种资源，随机选择67个节点作为消费者对某一随机资源发送请求。所有节点都作为转发者。车辆移动的相关参数如表 1所示。
|
表 1 车辆移动仿真关键参数 Table 1 Key parameters of vehicular motivation simulation |
结合本章的数据转发算法的特点，仿真实验采用以下的指标评价算法性能。
1) 平均命中率(Average Hit Rate，AHR)。表示在发送兴趣包请求数据的节点中收到数据包的节点的比率，用来衡量转发算法的稳定性。该值越高，则说明所有请求数据的节点中收到对应数据包的节点越多，则算法越稳定。
2) 平均延迟(Average Delay，AD)。表示消费者发送兴趣包之后，收到对应的数据包所用的平均时间，用来衡量算法的转发速度。该值越小，说明接收数据所需的延迟越小，算法路由的速度越快。
3) 平均转发次数(Average Forward Times，AFT)。表示在一次数据请求的过程中，所有消息的转发次数，包括探测包、确认包、兴趣包以及数据包，用以衡量请求数据的平均开销。该值越小，则说明每次请求数据消息的转发次数越小，表示该算法的开销越小。
3.2 仿真结果根据两个算法的仿真实验得到的结果，对比分析出算法的优劣。
3.2.1 平均命中率平均命中率表示在发送兴趣包请求数据的节点中收到数据包的节点的比率。命中率越高，表示算法越稳定。
如图 11所示，传统NDN(TRA-NDN)算法在该实验中的命中率为14%左右，而本文改进的NDN算法(Improved-NDN)的命中率为66.7%。由于车载自组织网络链路的稳定性不好，车与车辆之间的邻居关系无法一直维持，所以传统NDN算法的命中率会明显偏低，仅为14%左右。但是基于路段建立路由的改进的NDN算法会找到固定的路段寻找到相关的资源，命中率较高。车辆移动速度也会影响命中率，车速越快，网络拓扑结构越不稳定，车辆邻居关系越难维持，命中率也就越低。
|
图 11 平均命中率对比 Figure 11 Comparison of average hit rate |
平均延迟表示所有消费者发送兴趣包之后，直到收到对应的数据包所需要的平均时间，平均延迟时间越短，表示算法路由速度越快。
实验结果如图 12，传统NDN算法平均延迟大约为0.4 s，而改进后的算法延迟为1.27 s。这是由于传统NDN算法是直接指定下一跳节点发送信息，没有设置优先级队列和定时器。但是改善后的算法，设置了转发的定时器，减少路由开销，所以延迟会稍高。这个实验结果符合预期。
|
图 12 平均延迟对比 Figure 12 Comparison of average delay |
平均转发次数表示一次数据请求的过程中，所有消息的转发次数，包括探测包、确认包、兴趣包以及数据包的转发次数。平均转发次数越少，表示用于请求数据的平均开销越小。
实验结果如图 13所示，传统NDN算法在实验中平均一次数据请求的消息转发次数为2.67，而改进后的算法为2.29，改进后平均消息转发次数明显降低，这是算法设计的路段路由及最远距离优先转发的策略能减少路由开销的体现。
|
图 13 平均转发次数对比 Figure 13 Comparison of average forward times |
本文将命名数据网络应用于车载自组织网络中，并根据车载自组织网络的特点对其进行改进，在命名数据网络的基础上，设计了新的消息类型，提出了以路段信息作为建立路由的依据，基于命名数据网络技术的车载网数据分发算法。与文献[12]提出的算法进行实验仿真。从结果可以看出，本文的优化算法具有更高的稳定性，能够使得数据访问及获取的效率更高，转发数据的开销更低。
除此之外，对于命名数据网络在车载自组织网络中的应用还有以下几方面值得研究和探讨：表格的设计和维护，包括更完善的表格设计与车辆进入了新路段时的表格建立；生产者的移动性；除了FIFO之外的缓存策略等。
| [1] | LIU Y, BI J, YANG J. Research on vehicular Ad Hoc networks[C]//CCDC' 09:Chinese Control and Decision Conference 2009. Piscataway, NJ, IEEE, 2009:4430-4435. |
| [2] | JIANG D, DELGROSSI L. IEEE 802.11 p:Towards an international standard for wireless access in vehicular environments[C]//VTC 2008:Proceedings of the 2008 Vehicular Technology Conference. Piscataway, NJ, IEEE, 2008. 2036-2040. |
| [3] | HARTENSTEIN H, LABERTEAUX K P. A tutorial survey on vehicular Ad Hoc networks[J]. IEEE Communications Magazine, 2008, 46 (6) : 164-171. doi: 10.1109/MCOM.2008.4539481 |
| [4] | 陈林星, 曾曦, 曹毅. 移动Ad Hoc网络--自组织分组无线网络技术[M]. 北京: 电子工业出版社, 2012 : 6 -7. ( CHEN L X, ZENG X, CAO Y. Mobile Ad Hoc Network-Self-Organized Packet Radio Network Technology[M]. Beijing: Publishing House of Electronics Industry, 2012 : 6 -7. ) |
| [5] | LI F, WANG Y. Routing in vehicular Ad Hoc networks:a survey[J]. IEEE Vehicular Technology Magazine, 2007, 2 (2) : 12-22. doi: 10.1109/MVT.2007.912927 |
| [6] | ZHANG L, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44 (3) : 66-73. doi: 10.1145/2656877 |
| [7] | YUAN H, CROWLEY P. Scalable pending interest table design:From principles to practice[C]//INFOCOM 2014:Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway, NJ:IEEE, 2014:2049-2057. |
| [8] | SO W, NARAYANAN A, ORAN D, et al. Toward fast NDN software forwarding lookup engine based on hash tables[C]//Proceedings of the Eighth ACM/IEEE Symposium on Architectures for Networking and Communications Systems. New York:ACM, 2012:85-86. |
| [9] | AMADEO M, CAMPOLO C, MOLINARO A. Enhancing content-centric networking for vehicular environments[J]. Computer Networks, 2013, 57 (16) : 3222-3234. doi: 10.1016/j.comnet.2013.07.005 |
| [10] | WANG L, AFANASYEV A, KUNTZ R, et al. Rapid traffic information dissemination using named data[C]//Proceedings of the 1st ACM Workshop on Emerging Name-Oriented Mobile Networking Design-Architecture, Algorithms, and Applications. New York:ACM, 2012:7-12. |
| [11] | GRASSI G, PESAVENTO D, WANG L, e t, a l. ACM HotMobile 2013 poster:vehicular inter-networking via named data[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2013, 17 (3) : 23-24. doi: 10.1145/2542095 |
| [12] | GRASSI G, PESAVENTO D, PAU G, et al. VANET via named data networking[C]//INFOCOM 2014:Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway, NJ:IEEE, 2014:410-415. |