OJTT  >> Vol. 7 No. 5 (September 2018)

    基于朋友关系的车联网广告投递研究
    Research on Vehicle Network Advertising Delivery Based on Friends Relationship

  • 全文下载: PDF(1121KB) HTML   XML   PP.359-369   DOI: 10.12677/OJTT.2018.75044  
  • 下载量: 107  浏览量: 181   科研立项经费支持

作者:  

侯煜欣,杨贵草:西安理工大学,系统工程,陕西 西安;
樊秀梅:西安理工大学,自动化与信息工程系,陕西 西安

关键词:
车联网机会网络社会关系Internet of Vehicles Opportunistic Network Social Relationship

摘要:

车联网的快速发展随之也引发了很多应用问题的讨论和研究。本文针对商场的广告投递需求,提出了基于车联之间的社会关系的车联网路由算法,主要是针对车联网网络中的投递率和网络能耗进行优化和改进。首先,利用车辆之间的接触时间和频率来确立和维护车辆之间的朋友关系。其次,在每一个车辆节点内维护一张车辆节点社会距离表。这样可以使得车辆节点间的信息交换次数减少,从而减少整网的消耗、然后,将车辆节点在过程中接收的数据按条记录在其维护的表内,用于进行不同链路的传输。当车辆节点与其接触的节点中有社会距离为1的朋友节点时,计算其中可用链路与数据之间的效用值,并进行转发。最后,数据包被转发至靠近目标节点直至到达目的节点。其实验结果分析表明:辅助信息交换次数有相对的减少,在维持高效的数据包投递率情况下可以将整网的开销降低,达到预期的目标。

The rapid development of the Internet of Vehicles has also led to discussions and research on many application issues. This paper aims at the advertising delivery demand of shopping malls and proposes a vehicle networking routing algorithm based on the social relationship between vehicles, which mainly optimizes and improves the delivery rate and network energy consump-tion in the network of vehicles. First, the contact time and frequency between vehicles are used to establish and maintain a friend relationship between vehicles. Second, a vehicle node social distance table in each vehicle node is maintained. This can reduce the number of information ex-changes between vehicle nodes and reduce the overall network energy consumption. The data received by the vehicle node in the process is then recorded in a table maintained by it for the transmission of different links. When there is a friend node with a social distance of 1 in the node with which the vehicle node is in contact, the utility value between the available link and the data is calculated and forwarded. Finally, the packet is forwarded close to the target node until it reaches the destination node. The analysis of the experimental results shows that the number of auxiliary information exchanges is relatively reduced, and the overhead of the whole network can be reduced to achieve the expected goal while maintaining efficient delivery rate of data packets.

1. 引言

车联网是一种全新的应用技术,是物联网技术应用于智能交通领域的集中体现。指装载在车辆上的电子标签通过无线射频等识别技术,实现在信息网络平台上对所有车辆的属性信息和静、动态信息进行提取和有效利用,并根据不同的功能需求对所有车辆的运行状态进行有效的监管和提供综合服务。车联网可以实现车与车之间、车与建筑物之间,以及车与基础设施之间的信息交换,它甚至可以帮助实现汽车和行人、汽车和非机动车之间的“对话”。就像互联网把每个单台的电脑连接起来,车联网能够把独立的汽车联结在一起 [1] 。

机会网络(Opportunistic Network)是移动自组织网络中的一种特殊情况。在机会网络中,节点之间通信很难去找到一条稳定的链路来维护通信,所以一般会在网络中利用车辆节点间运动形成的通信链路进行逐跳传输,以“存储–携带–转发”的路由模式实现节点间的数据传输通信。由于节点的移动性和不确定性,网络中的链路会呈拓扑结构的动态变化,因此该网络可以在很多特殊环境下完成通信。例如:深海中的网络通信、战场等无法铺设基础设施的场景中通信和车辆节点之间的通信。而车联网中以车为主要节点,决定了网络的高动态性和频繁拓扑,它与机会网络的契合度很高,因此将机会网络运用在车联网中是一个良好的方案。车联网的发展和研究逐渐增多,需要拓宽的方面也逐渐增多,机会网络在车联网中的应用也变得越来越多,是近几年来的研究热点。

由于车联网网络的高动态性和频繁拓扑,导致了维护稳定链路的想法实现基本是不可能的。所以,如何在这种网络条件下寻找一条能够提供较稳定的链路来进行数据传输是研究的主要问题之一,并且希望这一链路的寿命尽可能的久,这样可以提供更多的稳定传输。因此,将机会网络的特性运用在车联网中来解决这一问题是本文的主要思路。如何设计合理的路由协议,以实现数据的高效传输是问题的重点。本文主要针对固定位置商场向周围范围内车辆发送相关广告这一场景为前提来研究路由。因此,一些关于场景上的考虑均以此为标准。本文提出了一种利用节点间的社会关系来发现相对稳定的链路和对数据包进行转发的路由机制,利用维护多表来保证数据包传输的高效性,减少数据交换的次数,提高传输效率。实验仿真结果表明,该辅助路由算法在传输过程中投递率有一定的提升,辅助信息交换次数明显减少,节省了全网资源。

2. 相关研究背景及成果

机会网络的部分概念来源于延迟容忍网络的研究 [2] 。机会网络是一种特殊的网络传输结构,利用一些方法和辅助性信息来达到对网络性能的改善是主要的研究手段,以下为一些相关研究成果介绍。

洪泛网络 [3] 具有最好的数据包投递率和最小的投递延迟等特性,但它存在于网络中庞大的数据包备份给网络性能带来了很大的负担,代价太大。广告信息的投递是不会被允许对整网造成过大的负荷的。在机会网络中,要尽可能地减少数据包无用复制,即减少在无用链路上的投入,并且在有效链路中可以有一个合理的复制转发,这样对网络整体性能有着很大的提升。

而在这一方面,相关研究人员还提出了更加合理化的方法来改进机会网络。文献 [4] 对移动社会网络做出了深入的分析和总结,将其体系结构分为三种:中心式、分布式和混合式。其中分布式结构的网络中节点以自组织方式组网,具有极高的鲁棒性,但内容上有些不足。BSIF (Based-Stranger Incentive Forwarding algorithm)算法 [5] 利用车辆间的陌生人的社会关系来建立一种弱连接 [6] ,对陌生节点通过一种属性计算来得到陌生值然后排序筛选进行转发,但其中并没有考虑到陌生节点的随机性运动导致的随机游走。文献 [7] 中节点与邻居相互接触检测,分布式地计算基于中心度和相似度,从二者中提炼出基于中心度和相似度的路由算法。当两节点相遇则交换各自范围的知识信息,计算中心度与相似度,再把数据包发送给节点效用值高的节点。文献 [8] 中的SRBRA (Social-Relations-Based Routing Algorithm)算法通过对移动节点的实时数据进行分析,得到影响这些节点移动的因素,然后对这些因素的复杂性和动态性进行评估,得到它们的社会关系值。最后梳理网络拓扑信息,选择最佳下一跳进行路由。但为了获得辅助信息造成的多步数据信息交换,也是影响网络性能的因素之一。文献 [7] 的SimBet方法利用桥接的形式构成一条新的链路,将源节点与目标节点间利用社交相似性重新确立转发的节点或节点集群。但这一方法主要讨论的网络环境是稀疏移动节点网络。文献 [9] 中提出了一种基于节点兴趣匹配的机会网络分发机制,从节点行为规律和兴趣爱好两个方面对网络进行分析。设计消息属性与节点兴趣匹配优先的消息分发策略,能够保证较高的分发效率和覆盖率。该方法避免了单个节点所获取的信息不完整和计算力不足的问题。

上述一些方法主要关注问题点在于网络能耗、数据包转发和合理链路选择三个问题上。在节点间信息交换次数上也有做一定优化,但仍有提升空间。并且对于多个数据包的同时传输并未做过多详细讨论。本文的路由方法主要是致力于商场的广告投递,因此数据包以及目的地并不统一,所以在数据包传输时需要考虑到不同数据包的不同路径选择问题。其次,由于传输信息的不重要性,所以需要尽可能地降低它对网络的能耗来节省成本。所以,在方法中会尽可能地减少信息交换次数。尤其是数据包交换次数。

3. 基于朋友关系的车联网广告投递

在以往的一些路由算法中,信息的交换往往类似于通信的握手机制,当信息传输至节点后节点需要返回传输成功信息,之后源节点收到确认之后再将其删除。而在实际情况的机会路由中并不具备三次传输的条件,在过程中就有可能链路已断裂。并且在过程中,数据包的空间占用率过大,这也会影响数据分组传递时的效率。本方法节省了路由传递时节点间传输时间,提高传输效率,并在此基础上做出了查重,减少了数据包过量无用复制,具体详细叙述见下。

3.1. 节点间朋友关系识别

在机会网络中要保证信息的稳定传输前提就是寻找一条稳定的链路,但由于车联网网络中的节点都是具有自主移动能力的车辆,速度快,网络频繁变化,因此直接寻找一条可以进行稳定传输数据的链路可行性非常低。所以针对这种复杂网络需要提出一些辅助性信息,以此来评估链路的传输稳定性,从而保证信息传递的准确性 [10] 。本文利用节点间的接触时间作为基础信息,将其进行一系列计算得到两个节点间的信息熵。如果两个节点它们节点之间接触时间充足或者接触频率频繁且趋于稳定,那么它们的熵值较高,熵值较高代表它们之间之后接触的概率高,链路稳定的时间也久,则它们互相定义为“朋友”。它代表着这两个节点之间能够具有一定程度的可靠传输条件,让数据包在具有朋友节点间的链路进行传输可以尽可能保证数据传递的交付率。并且,靠节点之间相互检测存在性来确认二者之间的关系并不需要节点之间的通信,只需记录自身检测的信息进行收集和计算,从而减少通信中数据交换的次数和频率。

本文以图1为例来详细介绍确立朋友关系的方法。图1中描述了节点a和b在同一网络下的19 s内的接触时间,图a表示两节点接触稀疏的情况;图b表示两节点接触密集的情况。图中每一格代表1秒的时间间隔,总共为19秒。假设a,b节点从第i秒开始进行通信,那么图a中平均每次建立通信的平均可用时间为1.34秒,而图b中的平均时间为5.34秒,显而易见图b的情况可以完全满足一次通信的时间,保证了a,b之间传输通信链路的稳定。不仅如此,在固定一段时间内节点接触的时间越多,越能保证它们之间信息的实时性与准确性,从而给其他链路利用它们转发消息做出了一定的保障。

并且,利用它们的接触时间及间隔也可以为它们下次接触可能性做出判断。其中设X为节点间间隔时长,一段时间内a与b共有k次接触, C o n a , b l 代表a,b间第l (其中 l [ 1 , k ] )次接触时长, T a , b 表示该段

时间内接触的时间总和,则第l次接触间隔的概率分布为: P a , b l = [ P ( P = C o n a , b l ) = C o n a , b l ] 。以此可以得出

节点a与节点b接触间隔事件的信息熵:。当熵值越大时,那么它们的接触间隔概率分布也越均匀,那么可以理解为下一次接触的概率越大,越有可能再次接触。因此,熵值越大可以表现为接触越有规律性。

3.2. 节点间社会距离表

顾名思义,社会距离一词代表着人与人的社会关系距离远近。本人与父母及亲兄弟姐妹之间关系最为亲近,那么定义他们之间的关系距离为1。而从父母角度来看,父母与他的父母和兄弟姐妹的血缘关系也是最近,那么它们的关系距离也为1。这样的情况下,本人与父母的兄弟姐妹和父母的关系距离即为相加关系得出的2。以此为基础,可以定义网络中车辆节点之间的社会距离关系。

在车联网网络中,当一个节点a检测信息并与周围节点b建立了朋友关系,那么它们的关系距离是直接的,因此距离为1。之后节点a获取了节点b的朋友节点信息条目,那么这些条目便是经过a,b链路之后的链路,因此在节点a的节点社会距离表中将从b中获取的信息社会距离 + 1。以此类推,就可以

Figure 1. Vehicle node contact time distribution

图1. 车辆节点接触时间分布

构建一张完整的节点社会距离表。当一个节点失去了与另一个朋友节点的连接时,将它们的节点社会距离变为∞,防止其他节点使用该链路。

假设车辆均在网络 G ( V ) 中,其中一个节点 a V 需要来记录并维护与它有关的车辆节点信息。那么,节点a需要维护一张社会距离表来完成这些操作。表中的每一行代表着一条信息,要将车辆关系完整的记录下来需要以下几点:

1) 目标节点:即可以到达的节点的位置信息。

2) 社会距离:节点自身与目的节点之间的社会距离。

3) 直属节点:节点自身到目标节点这条链路中节点自身的下一跳节点。

其具体构建过程如下所示:

以车辆节点a为例:车辆节点a开始进行检测收集,T0时刻,车辆节点a,b和a,c被识别为朋友关系,节点a将b,c添加进自身的社会距离表,其社会距离为1,如图2中T0时刻表中所示。本次接触为a,b和a,c开始将对方识别为朋友,因此在T0时刻还没有开始进行信息交换。接下来进入T1时刻,车辆节点a与b,c进行社会距离表交换信息,并各自对自身数据进行更新。更新过后车辆节点a的社会距离表如图2中T1时刻表所示。而节点b中之前包含有d,e两个朋友节点信息,所以会将d,e添加到节点a的表中,它们的社会距离为2,直属节点为b。此时车辆节点f并没有与c建立起朋友关系,所以没有将它加入到表1内。T2时刻车辆节点c将f更新至它自身的社会距离表,并将新的信息更新至车辆节点a,所以表a内更新到了车辆节点f的信息,并且其社会节点距离为2。在T3时刻,节点e与节点b失去了朋友关系,b更新了自身的距离表,并与a进行信息更新,将a与e的社会关系更新为∞。

3.3. 数据分组摘要表

由于本文的路由环境背景是基于用户兴趣的车联网广告投递,因此数据包并不会如地域群播那样对一个固定区域的单一数据包传输,而是根据不同用户不同兴趣会产生多条信息不同的数据包。因此,基于此情况下,为了数据包传递时的准确性,提出建立一张数据分组摘要表来维护路由中的数据包信息。

Figure 2. Establishment and maintenance of vehicle relationships

图2. 车辆关系建立与维护

Table 1. System resulting data of standard experiment

表1. 标准试验系统结果数据

表中每一行代表一条数据包,其表中包含以下信息:

1) 数据条编号:从1开始编号方便调用。

2) 目标节点:所要发送到的目标节点位置信息和车辆信息。

3) 数据包信息:所要发送的数据包。

这样车辆节点就可以将信息间独立分开,并且有助于链路效用值的计算。示例如表2

3.4. 免疫信息表

免疫信息表主要是记录免疫信息。该表记录了送达数据分组的免疫信息,是当目标节点成功接收数据信息之后由目标信息产生的。其表中数据结构与数据分组摘要表相同,这样更方便于删除。当两个节点接触后,判断对方是否为目标分组的目的节点,如果满足条件,则将数据送达目的节点。当目的节点收到数据包后产生对应的免疫信息,添加至自身免疫信息表内。该节点在之后的运动中遇到其朋友节点,则接收对方的免疫信息表,更新至自身表内,再删除已送达但还存在于缓存内的数据分组信息条目。

创建该表主要是为了减少网络内传输时数据包的传输,比起辅助信息之间的交换更新操作,减少数据包的多余转发对网络性能的优化会更加明显。

3.5. 传输效用计算

数据包的传输依赖于其计算出来的效用值,如果在该检测范围内有多条链路,那么将分别计算它们对于数据包的效用值,并选择最优的方案进行传输。例如图2中T2时刻,对于车辆节点a来说它检测到的可用链路一共有5条a → b、a → c、a → c → f、a → b → d、a → b → e,也就是说对于需要转发的数据包来说会选择三条链路中效用值最高的进行传输。假设a → b → e为最优,节点a会将数据发送至b,b收到信息之后会根据重新更新的社会距离表再次判断该链路是否仍为最优。如果依然是,那么就继续将数据包发送至e;或者发送至再次计算的最优值。这样的方式可以使数据包在传输中按照最优的路径来进行选择,并且在动态移动的网络中改善了因为节点移动性而导致的链路误差。

在整个路由过程中,共维护了三张表的辅助信息来保证传输。免疫信息表用于最初交换来判断数据分组表内数据条的有效性,而社会距离表和数据分组表中的信息会参与到计算中来。所以,在实际计算

Table 2. Data group summary table

表2. 数据分组摘要表

过程中,节点会从判断过后的免疫表中第一条信息开始对每条链路进行计算,所以节点需要计算的数据复杂度为 O ( n 2 ) 的级别。对于文献 [5] [7] [11] 中的方法复杂度进行计算,最高有 O ( n 2 × M ) 的复杂度,因此计算的复杂度不宜再过增加,会影响到其流畅度。所以,以最直观方便的距离作为效用值的衡量标准,以上段假设为例,a为源节点,e为目标节点,t为数据包所要到达的目的节点,即 U a = ( d e t d a t )

3.6. 具体操作步骤

节点a,b互为朋友节点,当a,b相遇后互相交换信息,二者的操作流程相同,流程如下:

步骤1:节点a,b相遇后,节点a获取b的免疫信息表,并检查自身数据分组摘要表,删除已送达的数据分组信息。

步骤2:节点a向b请求它的节点社会距离表,将表内信息添加到自身,并把表b中的信息条目社会距离均增加1 (即增加了从a到b的社会距离)。

步骤3:节点a检查自身的数据分组摘要表,遍历每一条数据,并计算它和节点社会距离表内每条链路效用值(即到目的节点的距离)。

步骤4:节点a转发满足条件的数据表条目给对应的中继节点。

流程图如图3所示。

4. 仿真实验及结果分析

4.1. 仿真环境

本文通过ONE仿真软件 [12] 对提出方法的性能进行仿真和验证,并且将其与Epidemic、BSIF、社会距离算法进行一些方面的比较。仿真场景设置为5000 m × 5000 m的移动场景,一共设置了最多240个车辆节点。每个移动车辆节点的缓存大小设置为100 M,节点的无线传输距离设置为200 m,移动速度为1~10 m/s之间随机整数值,带宽为2 M/s,将广告数据包大小设置为5 M。具体见表3

4.2. 性能对比参数

投递率:目的节点收到的数据包与源节点发送出的数据包数量的比值。

辅助信息交换次数:为了建立和维护网络中相对稳定的链路所需得到的信息,例如免疫信息表的交换;朋友节点间的社会距离表维护和更新。

路由开销:信息在网络传输过程中进行数据及交换和数据包转发所消耗的网络能量。

4.3. 仿真结果分析

图4中描述了在车辆节点不断增加的情况下,三种方法不同阶段的数据投递率关系图。总体来说,随着车辆节点的增加,本文提出的方法与BSIF陌生人算法都呈现出较高的投递率。而Epidemic传染路由呈现降低的趋势,这是由于在车辆节点增多后,洪泛导致数据包数量急剧增加,而每个车辆的数据缓存为固定的100 M,从而导致网络拥塞,数据无法转发,投递率下降。本文提出的方法在80个车辆节点以下的仿真结果是低于BSIF陌生人算法的。主要原因是由于车辆节点过少,在地图上的分布过于稀疏,不容易产生过多朋友节点。而这也是由于朋友关系的门限值设定导致的,如果该设定值变低,前期的投递率的确会有略微上升,因为可以参与到本方法进行传输的车辆变多,链路也变多,但过低的门限值会导致产生的链路并不那么稳定,效果并不明显,并且提高了开销。在车辆节点数量增多时,该方法表现出稳定、良好的效果。

图5中为网络中固定车辆节点数情况下总的辅助信息交换次数与时间的关系图,由于Epidemic传染路由和BSIF中没有辅助信息,因此未进行对比。理论来说,社会距离 [13] 和本文算法的理想结果应该都呈现一次函数的曲线,实际情况略有偏差。图中数据显示本文提出方法在减少辅助信息交换次数上相比社会距离算法确实有明显减少。该方法相对于社会距离辅助信息的减少主要是因为它对于节点的朋友要求让进行信息交换的车辆数减少,而从算法上来看它们的辅助信息交换次数相差不多。

图6中为网络传输总的路由开销与车辆节点数关系图,该图中Epidemic由于传染方式使得开销爆炸式增长,相比于其他三个方法相差过多。本文提出的方法在节省路由开销方面效果良好,不仅是从节省辅助消息和数据包传输都做出了改善,因此是四个方法中结果最佳的。

Figure 3. Routing flow chart

图3. 路由流程图

Table 3. Simulation parameter table

表3. 仿真参数表

Figure 4. Relationship between delivery rate and number of vehicle nodes

图4. 投递率与车辆节点数量关系

Figure 5. Auxiliary information exchange times

图5. 辅助信息交换次数

Figure 6. Routing cost

图6. 路由开销

5. 结论

机会网络在车联网中的应用已经十分频繁了,由于车辆移动性导致的网络拓扑环境频繁变化使得机会网络适合在车联网中应用。本文提出的基于车辆社会网络的数据分组路由方法,通过网络中构建的社会节点关系来找出其中稳定的传输链路。然后数据分组各自利用效用值高的链路来进行数据传输,从而提高网络路由效率。由仿真实验数据分析得出,本文方法可以在维持高的数据包投递率情况下将网络中的数据传输消耗降低,实现了最终的目标。之后还有许多可以改进优化的空间,如何更有效的维护社会距离表,以此来减少效用值计算阶段的计算量;如何做到相同数据包不同目标节点的数据条结构优化;并且在最优链路的寻找方法中还有优化空间。

基金项目

本研究工作受到以下项目资助:陕西省“百人计划”、陕西省重点研发计划重点项目(2017ZDCXL-GY-05-01)。

NOTES

*通讯作者。

文章引用:
侯煜欣, 杨贵草, 樊秀梅. 基于朋友关系的车联网广告投递研究[J]. 交通技术, 2018, 7(5): 359-369. https://doi.org/10.12677/OJTT.2018.75044

参考文献

[1] 王建强, 吴辰文, 李晓军. 车联网架构与关键技术研究[J]. 微计算机信息, 2011, 27(4): 156-158.
[2] Jia, X.U., Sun, L.J., Wang, R.C., et al. (2010) Adaptive Seed Spray Routing for Opportunistic Networks. Acta Electronica Sinica, 38, 2315-2321.
[3] Mundur, P., Seligman, M. and Lee, G. (2008) Epidemic Routing with Immunity in Delay Tolerant Networks. 2008 IEEE Military Communications Conference, San Diego, 16-19 November 2008, 1-7.
[4] Kayastha, N., Niyato, D., Wang, P., et al. (2011) Applications, Architectures, and Protocol Design Issues for Mobile Social Networks: A Survey. Proceedings of the IEEE, 99, 2130-2158.
https://doi.org/10.1109/JPROC.2011.2169033
[5] 刘慧, 张振宇, 杨文忠, 等. 机会网络中基于陌生人的转发算法[J]. 计算机工程与设计, 2017, 38(4): 893-897.
[6] Luis, R., Mejia, G., Cruz, C., Berrone, P., et al. (2011) The Bind That Ties: Socioemotional Wealth Preservation in Family Firms. Academy of Management Annals, 5, 653-707.
https://doi.org/10.5465/19416520.2011.593320
[7] Daly, E.M. and Haahr, M. (2007) Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs. ACM International Symposium on Mobile Ad Hoc Networking & Computing, Montreal, 9-14 September 2007, 32-40.
[8] Wu, X.H., Gu, X.F. and Poslad, S. (2015) Routing Algorithm Based on Social Relations in Opportunistic Networks. 2015 12th International Computer Conference on Wavelet Active Media Technology and Information Processing, Chengdu, 18-20 December 2015, 146-149.
[9] 张淯舒, 王慧强, 冯光升, 等. 基于兴趣匹配的机会社会网络消息分发机制[J]. 计算机研究与发展, 2016, 53(6): 1365-1375.
[10] 李捷, 陈阳, 刘红霞. 基于社交效用向量的机会网络路由算法[J]. 河南大学学报(自然科学版), 2016, 46(2): 196-201.
[11] 彭碧涛. 接触概率和数据分组新鲜度感知的机会网络路由算法[J]. 小型微型计算机系统, 2017, 38(7): 1459-1463.
[12] 王文涛, 郑芳, 王奇枫, 等. 基于ONE平台的机会网络路由协议仿真分析[J]. 中南民族大学学报(自然科学版), 2014(3): 110-114.
[13] 袁培燕, 宋明阳. 移动机会网络中一种轻量级的分布式社会距离路由算法[J]. 计算机应用, 2018(1): 13-19.