东北大学学报:自然科学版  2016, Vol. 37 Issue (8): 1084-1088  
0

引用本文 [复制中英文]

赵海, 于冲, 司帅宗, 彭海霞. VANET运动模型解析解与数值解的比照分析[J]. 东北大学学报:自然科学版, 2016, 37(8): 1084-1088.
[复制中文]
ZHAO Hai , YU Chong , SI Shuai-zong , PENG Hai-xia . Contrast Analysis of Analytical Solution and Numerical Solution to the VANET Mobility Model[J]. Journal Of Northeastern University Nature Science, 2016, 37(8): 1084-1088. DOI: 10.3969/j.issn.1005-3026.2016.08.005.
[复制英文]

基金项目

辽宁省科学技术计划项目(2015401039)

作者简介

赵海(1959-),男,辽宁沈阳人,东北大学教授,博士生导师。

文章历史

收稿日期: 2015-05-12
VANET运动模型解析解与数值解的比照分析
赵海, 于冲, 司帅宗, 彭海霞    
东北大学 计算机科学与工程学院,辽宁 沈阳 110819
摘要: 依据车载自组织网络(VANET)的高移动性特征分别建立VANET运动解析模型与运动仿真模型.通过两种运动模型得到VANET度分布的解析解与数值解.对它们进行比照分析,发现两种度分布曲线均呈现出小度值的节点个数众多、大度值节点个数较少的特点,符合幂律函数分布,由此证明VANET是一个无标度网络.另外,从理论分析与仿真实验两个角度证明,VANET对随机性攻击具有较高的鲁棒性,但对针对性攻击则表现出网络的脆弱性.
关键词车载自组织网络(VANET)    运动模型    度分布    解析解    数值解    
Contrast Analysis of Analytical Solution and Numerical Solution to the VANET Mobility Model
ZHAO Hai, YU Chong, SI Shuai-zong, PENG Hai-xia    
School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: YU Chong, E-mail: 1179710249@qq.com
Abstract: Considering the high mobility characteristics of vehicular ad-hoc network (VANET), a mobility analytical model and a mobility simulation model were established. The analytic solution and the numerical solution of the VANET degree distribution were obtained by the two proposed mobility models. Comparing the two degree distribution curves, it is shown that there are lot of nodes with small degree values, while a few nodes with huge degree values, which means that the degree distribution follows the power law function, proving that the VANET is a scale-free network. And the theoretical analysis and simulation experiment verified the high robustness of the VANET against random attacks and its vulnerability when facing targeted attacks.
Key Words: VANET(vehicular ad-hoc network)    mobility model    degree distribution    analytical solution    numerical solution    

车载自组织网络(vehicular ad-hoc network,VANET)是无线自组织网络根据最新研究提出的一类新的网络,具有移动迅速、网络拓扑变化频繁等特点.这类网络可用于车辆之间的无设施通信,改善交通环境,提高驾车安全等.目前,对VANET的研究已经引起各国学者的普遍关注[1].

现有的VANET研究多为对MAC层协议和路由协议的研究[2-3],在车辆道路移动场景仿真、可拓展性和信息传输安全等方面也略有涉及[4-5].研究无线自组织网,通常使用运动模型来描述节点在网络中的运动规律,进而对网络性质加以分析[6-7].当前普遍公认的运动模型有随机游走移动模型、随机路点移动模型[8].本文在现有的无线自组织网运动模型基础上,结合VANET自身性质,构建VANET运动模型,并试图从运动模型的解析解与数值解两个方面探讨VANET度分布等相关特征.

1 车载自组织网运动解析模型

车辆按照一定规律逐次进入车道后,按照分簇协议组簇,多个簇单元组成的车载网络由此形成.本文依照这一思想,构建VANET运动解析模型.

设定车道初始时刻存在m0辆车,从t=0时刻开始,每一时间步向车道中添加一辆车,则在时间步t时刻车道中的车辆总数为

(1)

相对于整个网络数目,m0非常小,因此可以忽略初始时刻网络中边的连接.假设初始状态网络中存在0条边,每辆新加入的车都与已存在的m辆车相连,即每一时间步增加m条边,则有

(2)

网络中的总度值是网络中总边数的2倍,所以t时刻网络中的总度值为

(3)

由于车辆通信能力的限制,网络中的车辆只能与在其通信半径范围内的车辆通信,这就意味着一台新的车辆进入车道时,只能选择与在其通信半径范围内的车辆进行连接,即在其局域世界内进行连接.由于VANET采用分簇结构,因此网络中车辆与新加入的车辆相互连接的概率与车辆本身度值大小成正比:

(4)

式中:表示在新加入的车辆的局域世界内车辆的度值总数.式(5)中kj表示整个网络的度值总数.

(5)

道路中的车辆不断运动,导致车辆的出簇与入簇.假设网络中车辆发生出簇的平均概率为dd受车辆的通信半径和车辆间相对速度的影响:车辆通信半径越小,相对速度越大,车辆越容易离开簇首的通信范围,d越大.当一台车辆离开了簇首的通信范围时,它与簇首之间的连接断开,车辆从该簇中脱离,同时在其新的局域世界内重新选择簇首进行连接.在整个过程中,网络中边的总数、总度值均保持不变.

根据连续场理论,假设网络中度值的变化是连续的,可以得到如下方程:

(6)

将式(1),式(3)~式(5)代入式(6):

(7)

显然式(7)是一个微分方程,初始条件为车辆vi在时刻tiki(ti)=m加入车道,解式(7)得

(8)

式中:β=α=.

由式(8)可以得出,车辆连接度ki(t)小于某定值k的概率为

(9)

因此,

(10)

t→∞时,

(11)

由初始条件可得p(k)=,(k=m),所以VANET中的度分布为分段函数:

(12)

这里有一点值得注意,由于采用在局域世界内选择连接的方式,车辆能够连接的数目受到通信半径和车辆间安全距离的限制,因此网络中的最大度值不会超过车辆通信半径内包含的最大车辆数.

2 车载自组织网运动仿真模型

VANET仿真包括两方面:交通仿真与网络仿真[9],其中网络仿真又涵盖了对链路层的仿真和网络层的仿真.现有的典型仿真工具SUMO[10],NS2等,大多只能对其中一个方面进行仿真,造成两种仿真分别独立,兼容性差的局面,无法有效体现交通仿真与网络仿真间的相互影响.为了更加真实地反映VANET构建过程,获取更加可靠、完整的VANET运动仿真结果,本文提出一种同时基于交通仿真与网络仿真的VANET运动仿真模型.

2.1 交通仿真设计

交通仿真是VANET仿真中至关重要的一部分,是整个仿真实验的主体,更是网络仿真的基础.交通层的仿真包括车道的生成以及车辆属性的设定.目前,VANET交通仿真主要包括两种,一种是城市交通仿真,另一种是高速公路交通仿真.城市交通仿真中存在有设施通信和无设施通信,高速公路交通仿真中只存在无设施通信.为了充分体现无设施VANET性质,排除有设施通信的影响,在本模型中,选择对高速公路交通情况进行仿真.为了模拟真实的道路情况,每个车道都被限定了安全距离,避免车距过近造成危险.由于双向车道相对速度过大,极易导致网络结构维持时间短,给获取网络拓扑、研究网络性质带来困难,因此选用双排单向车道,其中双排车道的右侧车道为行驶车道,左侧车道为超车道.设定生成的双排单向直线车道长度为l,模型中的车辆按照泊松分布进入车道,每辆车都被赋予唯一的ID号,所有车辆均沿车道直线行驶,且行驶方向一致,车速在[vmin, vmax]间均匀分布.车道中的车辆要时刻与周边车辆进行速度比较并及时做出调整:若后车车速大于前车车速且超车道允许超车,则后车从超车道超车,超车一段时间后,若行驶车道允许,则变回行驶车道,否则继续在超车道行驶,直到行驶车道允许变回;若后车车速大于前车车速但超车道不允许超车,则后车车速降低至前车车速,与前车之间保持安全距离,跟车行驶.

2.2 链路层仿真设计

链路层仿真采用802.11p协议,该协议可以降低实现和部署成本、提高带宽,有利于实时收集交通信息.802.11p协议支持车辆在VANET规定的频率上进行通信,为DSRC(专用短程通讯)或者面向车载通信提供了基础.对802.11p协议的通信半径R进行设定,由于该协议支持的最大传输距离为1000m,因此0 < R≤1000.协议规定,只有在同一通信半径范围内的车辆才能进行通信.

2.3 网络层仿真设计

网络层的主要任务是组建VANET通信结构,其关键技术是分簇算法.使用分簇算法可降低VANET中的拓扑变化,便于车辆管理,提高网络的可扩充性,减少路由和控制开销,适应VANET的高移动性.VANET运动仿真模型选用最大连接度分簇协议,分簇算法的工作流程如下:

1)初始化车道,初始时刻车道中车辆均为孤立节点(IN),初始状态均为IN.比较所有孤立节点车辆的度值k,选出度值最大的车辆Kmax作为簇首(CH),并将Kmax的状态更新为CH;

2)将Kmax通信半径内的车辆设定为簇成员(CM),并将其状态更新为CM.

3)重复步骤1)和步骤2),直到网络中不存在状态为IN的车辆为止.

由于车辆间不断的相对运动,网络中存在簇的破裂与重组,当一个CM脱离了它原本CH的通信范围时,它的状态将更新为IN,同时寻找并请求加入其通信半径范围内的其他CH,加入新的簇后状态更新为CM;如果其通信半径内不存在其他CH,则该车辆自成独立簇,并将状态更新为CH.至此,网络层的仿真设计工作基本完成.

3 对比分析 3.1 度分布的解析解与数值解比照分析

依据运动解析模型,假设m0=3,m=1,d=0.2,时间步t=1000,利用MATLAB描绘解析解度分布曲线,如图 1所示.由式(11)可以看出,VANET运动解析模型度分布满足幂律分布.

图 1 度分布解析解 Fig.1 Analytic solution of degree distribution

利用已搭建好的VANET运动仿真模型生成网络.设定道路长度为l=10km,802.11p协议下的通信半径为R=300m,从t=0时刻开始,不断地按泊松分布向车道中添加车辆,直到车道中车辆数达到最大值.采集100组VANET度值分布数据,描绘100组数据的度分布散点图,通过多次重复实验,得到分布情况如图 2所示.

图 2 度分布数值解 Fig.2 Numerical solution of degree distribution

图 2可以发现,多次实验的网络度分布走势几乎一致:度分布随着度值的增加而变小.网络的最大度值在20左右,这是因为车辆间的连接受到车辆通信半径和安全距离的限制,通信半径内分布的车辆数目有限,因此网络中的最大度值不会超过车辆通信半径内包含的最多车辆数.这一分布结果与VANET运动解析模型得到的度分布十分相似,由此可以设想,运动仿真模型的度也满足幂律分布.

假设某一函数具有幂律规律y=bxa,对该函数两边同时取对数:lny=alnx+lnb,即得到一条斜率为a、截距为lnb的直线.为验证运动仿真模型的度是否满足幂律分布,对采集到的度分布数据取双对数,并描绘网络的度分布散点图,如图 3所示.

图 3 取对数的度分布数值解 Fig.3 Numerical solution of degree distribution with logarithm method

图 3可以看出,点的分布大致呈一条直线.对散点进行拟合,得到y=-1.9x-0.17,拟合度大于0.9,充分证明这些散点呈线性分布,验证了该运动仿真模型的度分布符合幂律函数.

通过对比分析解析解与数值解,证明了VANET度分布符合幂律分布.由于多次仿真实验存在随机误差,解析解的幂律指数-2与数值解的幂律指数-1.9之间存在合理范围内的误差.由此可以得出结论,VANET度分布满足幂律分布,幂指数大约为-2.

3.2 VANET鲁棒性与脆弱性的理论分析与仿真实验

实际应用中,VANET的网络性能受到道路维修、交通事故等不可抗因素的影响.因此,分析VANET在受到攻击时的网络特征有现实意义.

根据运动解析模型的构建方法及度分布曲线可知:网络中少数重要节点具有较高的度值,它们负责几乎整个网络的连接与通信任务,而大多数节点具有较小的度值,它们只负责本身与簇首节点的通信工作.因此,当网络受到随机攻击时,网络中大度值节点受到攻击的概率较小,而度值较小的节点受到攻击的概率较大,所以随机攻击对网络整体性能影响不大;而当网络受到针对性攻击时,网络中的大度值节点受到破坏,与之连通的链路全部断开,造成网络大范围瘫痪.由上述分析可以推断,在面对随机攻击时,VANET表现出鲁棒性;在面对针对性攻击时,VANET则表现出脆弱性.

运用本文建立的运动仿真模型生成网络,将网络拓扑输入到MATLAB中,仿真攻击实验.假设去除的节点数占原始网络总节点数的比例为f,选用平均路径长度L和最大连通子图的相对大小S来度量网络的鲁棒性.从图 4可以看出,面对随机攻击时,随着f的增加,L变化比较平稳,S下降的速度也较为缓慢,当f大于0.75时,S≈0,说明VANET对随机攻击表现出很好的鲁棒性.在面对针对性攻击时,随着f的增大,L迅速增大,这是由于网络中度值大的节点被破坏,部分链路完全断开所致.当f增大到0.1时,L随着f的增大而减小,此时网络中几乎不存在大度值节点,大部分为孤立节点;当f大于0.3时,L基本为0,S随着f的增大而急剧下降;当f达到0.15时,S≈0,显示出VANET在面对针对性攻击时的脆弱性.

图 4 网络的鲁棒性 Fig.4 Robustness of VANET
4 结论

1)依据VANET的形成过程与高移动性特点构建出VANET运动解析模型与仿真模型.

2)利用运动模型分析了VANET的度分布及其鲁棒性和脆弱性.

3)对比运动模型度分布的解析解与数值解发现,两者的度分布曲线均呈现出小度值的节点数量众多、大度值节点数量较少的特点,符合幂律函数分布!

4)理论分析与仿真实验证明了VANET对随机性攻击具有较高的鲁棒性,而对针对性攻击具有高度的脆弱性.

综上所述,VANET具有无标度网络性质,是一种复杂网络.

参考文献
[1] Zeadally S, Hunt R, Chen Y S, et al. Vehicular ad hoc networks (VANETS):status, results, and challenges[J]. Telecommunication Systems , 2012, 50 (4) : 217–241. DOI:10.1007/s11235-010-9400-5 (0)
[2] Rawashdeh Z Y, Mahmud S M. A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[J]. EURASIP Journal on Wireless Communications and Networking , 2012, 2012 (1) : 1–13. DOI:10.1186/1687-1499-2012-1 (0)
[3] Taleb T, Sakhaee E, Jamalipour A, et al. A stable routing protocol to support ITS services in VANET networks[J]. IEEE Transactions on Vehicular Technology , 2007, 56 (6) : 3337–3347. DOI:10.1109/TVT.2007.906873 (0)
[4] Engoulou R G, Bellaïche M, Pierre S, et al. VANET security surveys[J]. Computer Communications , 2014, 44 : 1–13. (0)
[5] Su H, Zhang X. Clustering-based multichannel MAC protocols for QoS provisionings over vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology , 2007, 56 (6) : 3309–3323. DOI:10.1109/TVT.2007.907233 (0)
[6] Roy R R. Handbook of mobile ad hoc networks for mobility models[M]. New York: Springer Science & Business Media, 2010 . (0)
[7] Hong X, Gerla M, Pei G, et al.A group mobility model for ad hoc wireless networks[C]//Proceedings of the 2nd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems.New York:ACM, 1999:53-60. (0)
[8] Camp T, Boleng J, Davies V. A survey of mobility models for ad hoc network research[J]. Wireless Communications and Mobile Computing , 2002, 2 (5) : 483–502. DOI:10.1002/(ISSN)1530-8677 (0)
[9] Fiore M, Harri J, Filali F, et al.Vehicular mobility simulation for VANETs[C]// 40th Annual Simulation Symposium.Norfolk, VA, 2007:301-309. (0)
[10] Krajzewicz D, Bonert M, Wagner P.The open source traffic simulation package SUMO[J/OL].[2015-04-16]. (0)