一种用于VNETs的内容命名与路由方法

  • 投稿戒了
  • 更新时间2017-07-25
  • 阅读量761次
  • 评分4
  • 78
  • 0
1 引言(Introduction)

作为第一个实用的车联网系统,Telematics将各种通信方式与车辆信息系统融合,实现了追踪、导航、安全驾驶、车载无线通信等大量应用,但其主要是面向车辆运营服务的,强调“集成与融合”,对通信网络本身关注不足;在随后的一段时间内,CEN、ISO、IEEE等组织先后制定了适用于AVI和ETC等场景,涵盖从物理层到应用层的专用短距通信标准(DSRC)[1];作为针对车联网环境的深度改进协议,802.11p[2]得到了广泛的关注与研究,这使得车联网逐步走向实际应用。然而,上述系统、协议大多基于现有的网络体系架构,而基于TCP/IP的网络体系架构受限于“身份—位置”的绑定关系,对移动通信的支持较为欠缺。尤其是在智能车联网环境下,其通信效率不足以支撑未来的应用需求。

命名数据网络通过解耦“内容—位置”的强绑定关系,提出一种以数据为中心(data-centric)的网络体系结构[3],如图1所示。

 

 

 

 

 

 

 

 

图1 NDN基本结构框图

Fig.1 Basic structure diagram of NDN

本文基于NDN体系结构,研究并提出一种用于VNETs的内容命名与路由方法。

2 相关研究工作(Related work)

在智能车联网环境下,由于车辆的移动而导致各节点之间的通信链路具有较强的时空属性,网络拓扑结构呈现出非稳定状态,而满足约束条件的连通性拓扑又是实时寻址的基础。Hou等[4]研究了城市环境下的车联网连通性问题,引入速度、大小等度量值来描绘车辆移动与网络连通性并提出了相应的数学模型来表达二者之间的关系。Ait Ali K等[5]分析了车流的时空属性对网络拓扑结构和变化的影响,提出了一个适应于城市和郊区环境的移动模型(V-MBMM,Vehicular Mask-Based Mobility Model),基于实际数据的实验结果表明了该模型的适应性。杨放春等[6]提出了一种支持终端用户高速移动的垂直切换方法,根据网络属性和终端运动趋势建立相应的切换概率分布,然后根据用户偏好选择相应的决策树进行决策。Zhang等[7]提出并跟进研究“命名数据网络架构”,对设备与内容进行命名,名字具有层次化结构且对网络透明,可以有效地解耦内容与地址,能有效支持节点移动。张宏科等[8]提出了一种ICN环境下基于定位器的移动支持方案,可提供增强转发功能,对车联网实时寻址研究具有一定的借鉴意义。Grassi等[9]在NDN架构下,研究了车联网命名、寻址和安全等问题,并在UCLA的车联网试验环境下开展了可行性验证工作。

3 内容命名方法(Content naming method)

内容由提供者发布,其命名由“名字”“公钥”和“GUID”这三个要素组成,数据访问由用户驱动。本文采用基于多层P:L对结构的内容命名方法,实现匹配的粒度可选性,以满足不同量级的应用需求,提高灵活性,具体如图2所示。

 

 

图2 内容命名方法示意图

Fig.2 Content naming method diagram

其中,“P”是发布者公钥的密码哈希值,这是一个扁平化的结构,可利用加密哈希函数来实现名字与公钥的绑定,接收方可通过对应的哈希运算来校验接收到的“名字—公钥”绑定关系是否匹配,从而排除虚假的绑定声明,内在提供抵抗DoS攻击的能力;“L”是数据块的唯一识别标签。通过这种层次结构,能提供更强的内在安全特性。将“公钥—现实身份”之间的绑定独立于网络本身,由第三方CA提供,可以灵活地选择具体的认证方案并随同其一起更新、演进,而不用对网络基础结构做改动。同时,也能实现不同粒度的内容聚合,可以为同一路由记录匹配多种粒度的映射关系,在用户组织机构变更或是部署节点发生改变的情况下,甚至不用更新路由信息就能实现“粒度换灵活性”。

4 快速寻址与路由机制(Fast addressing mechanism)

为完成快速寻址与路由,设计了一种基于Bh数列的分档布鲁姆查询算法。

4.1 分档增量计数式布鲁姆过滤器

计数式布鲁姆过滤器能实现元素的插入、查询和删除等内容查找必需的基本操作,且具有较高的效率。但同时也存在内存消耗显著的问题。采用区分服务的思想,为P:L结构中不同Level(聚合粒度)的记录分配不同的权值N,按权值划分子集,为高代价子集分配较多的哈希函数(即k值较大)以便降低其假阳性概率;为低代价子集分配较少数量的哈希函数,用误报率换空间和时间,从而降低总的查询代价。按权值分档后的集合S描述为:

 

每个子集的元素个数,当子集Si中的元素查询失效时,所需要的额外I/O代价为,子集Si的哈希函数个数为,对应的假阳性概率为,则整个集合的查询失效代价之和定义为:

 

综合考虑每档子集合的最小误判概率,所需要的哈希函数个数可表示为:

 

 

 

 

此时,多档联合查询失效的总代价可表示为:

 

 

 

上述目标函数由参数来确定,求解目标函数的最小值,即可获得每档子集的哈希函数个数ki。

在计数式布鲁姆过滤器中,执行查询操作的基本流程如图3所示,逐一判断对应的k个计数器c的值是否都大于0,若否,则直接停止并返回false,否则继续,直到比较完成,判定命中。

 

 

 

 

图3 计数式布鲁姆过滤器查询流程图

Fig.3 Counting Bloom filter query flowchart

结合k值分档计算方法,采用如图4所示的增量式布鲁姆过滤器查询流程来实现。

 

 

 

 

 

图4 增量式布鲁姆过滤器查询流程图

Fig.4 Incremental Bloom filter query flowchart

图中黄色部分为新增的逻辑结构,新增一个具有k个哈希函数的集合,其中的计数器不采用加1的方式来实现插入操作,而是从一个Bh数列中选择一个增量值v来累加,第二个哈希函数集合可表示如下:

 

函数取值范围为,指向集合D。插入元素x时,新增计数器的累加增量来自于集合D,表示为,为G对应的哈希函数。在执行查询操作时,先计算c-v的值,然后判断其与0和L的关系即可,无须执行查表操作,如未命中则可直接返回消息。如果k个计数器都匹配通过,再进入最后的常规判定环节。采用此思路,可以充分利用Bh数列的特点来实现快速收敛,提高查询效率。

4.2 Bh数列

Bh数列由S.Graham于1995年提出,可以用来快速实现精确匹配操作,具有鲜明的特点和广泛的应用前景。定义如下:Bh数列为一整数集合,对任意的,集合中任意个元素的和都不同(例,即为一个B3数列,即为一个B2数列)。因此,只要给定个元素的和,即可判定元素是否为其中的一部分。该特性可用于如图4所示的逻辑实现,将Bh数列中的元素作为计数器的增量(Increment v),过滤器的误报率表示为:

 

 

则过滤器的误报率只与集合D的选择参数h和l相关,而与其具体的元素选择无关。

5 结论(Conclusion)

本文针对智能车联网环境下的高效通信机制开展研究,基于命名数据网络这种新型网络体系结构,提出了一种层次化的内容命名方法,设计了一种分档增量计数式布鲁姆过滤器结构。采用该方法与机制,可实现在车联网这类高度动态场景下的节点命名与自适应快速查找。

参考文献(References)

[1] W.Xinzhou,et al.Vehicular Communications Using DSRC:Challenges,Enhancements,and Evolution[J].IEEE Journal on Selected Areas in Communications(JSAC),2013,31:399-408.

[2] IEEE Guide for Wireless Access in Vehicular Environments (WAVE)-Architecture[J].IEEE Std 1609.0-2013,2014:1-78.

[3] L.Zhang,et al.Named data networking[J].ACM SIGCOMM Computer Communication Review,2014,44(4):66-73.

[4] X.Hou,et al.Modeling the Impact of Mobility on the Connectivity of Vehicular Networks in Large-Scale Urban Environment[J].IEEE Transactions on Vehicular Technology,

2016,65(4):2753-2758.

[5] Ait Ali K,Baala O,Caminada A.On the Spatiotemporal Traffic Variation in Vehicle Mobility Modeling[J].IEEE Transactions on Vehicular Technology,2015,64(2):652-667.

[6] 范存群,等.基于认知自选择决策树的垂直切换方法研究[J].通信学报,2013,34(11):71-80.

[7] Zhang L,et al.Named data networking[J].ACM SIGCOMM Computer Communication Review,2014,44(3):66-73.

[8] Rao Y,et al.LBMA:A novel Locator Based Mobility support Approach in Named Data Networking[J].Communications,China,

2014,11(4):111-120.

[9] Grassi G,et al.VANET via named data networking[C].IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS),2014:410-415.

作者简介:

杨 凤(1981-),女,硕士,副教授.研究领域:车联网,命名

数据网络.

刘金眉(1996-),女,本科生.研究领域:车联网.

黄珊珊(1996-),女,本科生.研究领域:车联网.