0 引言

车载自组织网络(Vehicle Ad hoc Network, VANET)^[1]作为一种特殊的移动Ad Hoc网络，它是在车辆环境中实现的动态转发数据的移动网络。在VANET中，在一定的区域内使用无线网络通信技术将车辆与车辆以及车辆与固定基础设施连接在一起，从而能快速地在现有的道路上建立一个车辆间多跳通信的动态网络，且该网络具有自组织、分布式控制的特点。美国联邦通信委员会(Federal Communications Commission, FCC)于1999年将从5.85 GHz到5.925 GHz的共75 MHz频段划分出来用于车辆环境下的专用短距离通信频段(Dedicated Short Range Communications,DSRC)^[2]。DSRC通信范围扩展到1 000 m，数据传输速率也提高到6～27 Mb/s。之后DSRC发展成为车载无线接入(Wireless Access in Vehicular Environments, WAVE)系统^[3]。2009年，国际互联网工程任务组(Internet Engineering Task Force, IETF)制定了由802.11标准扩充的WAVE，又称IEEE 802.11p，这不仅为行车环境下的无线接入提供便利，而且为未来智能交通系统的诸多应用提供了技术支持。由于VANET在社会和经济方面的巨大价值,已成为学术界、工业界和各国职能部门的热点研究领域^[4]。

由于车辆的高速运动，无线通信设备通信距离有限，且无线信道易受道路上各类障碍物阻拦，都会导致VANET的网络拓扑随时间剧烈变化。因此，如果能够掌握VANET拓扑结构的动态特性，就可以设计高效的拓扑控制算法，优化网络连通性，使网络能够持续稳定提供可靠的服务。中心性是评价网络拓扑特征的主要指标之一，通过中心性的研究可以挖掘网络中的重要节点，从而可以采取一系列有效的措施来提高网络的性能，优化网络拓扑结构，保证网络的稳定的通信能力，这对拓扑动态变化的VANET协议开发和网络管理有着重要的意义。

目前，对VANET拓扑结构的研究主要是基于复杂网络理论分析其度分布、聚类系数、路径长度等。文献[5]以多Agent微观交通仿真器为仿真工具，研究了车载自组织网络的瞬时特性，研究结果表明网络节点数服从参数幂律分布,VANET不存在小世界特性。文献[6]中利用出租车全球定位系统(Global Positioning System, GPS)数据分析了城市环境下VANET的度分布、聚类系数、特征路径长度等拓扑特性。文献[7]应用Barabasi和Albert提出的BA(Barabasi-Albert)无标度网络对VANET拓扑进行建模分析，认为VANET具有小世界特性。相比之下，VANET中心性的研究比较少。文献[8]研究了德国科隆的交通网络的瞬时拓扑结构，其主要刻画参数包括最大连通分支、度及介数中心性等，分析结果表明VANET不具有小世界特性。文献[9]以城市道路交通仿真软件为仿真工具研究了VANET的中心性。但是，这些中心性的研究仅仅考虑了VANET静态网络结构或瞬时网络拓扑结构，没有考虑网络拓扑的动态性。事实上，VANET为含有时间的复杂网络，即时序复杂网络(temporal complex network)^[10]。一方面，静态网络数据的不全面性会导致实际的动态网络丢失大量有价值信息，因此有必要对网络的动态变化深入研究；另一方面，瞬时网络拓扑表示动态网络中当前时刻拓扑结构与上一个时刻的网络结构完全无关，虽然瞬时网络拓扑特征的研究能够分析动态网络随时间的一些变化趋势，但是割裂了当前时刻的网络拓扑结构与历史时刻网络拓扑之间的某种内在的联系。本文研究VANET动态中心性问题，评价VANET中节点的重要性，特别研究关键节点随时间的演化特征，期望能够利用这一特征更好地确定信息传播中的中继节点，从而实现信息的成功投递，为开发新的VANET路由算法提供指导。

1 VANET时序网络建模

定义1 时序网络。时序网络G_[0,T]^D=(G,T,ρ)必须满足以下性质^[11]：

1) 基本静态图G=(V,E)；

2) T是时间轴；

3) 边存在函数ρ:E×ΔT→{0,1}，在给定的时间窗内给定一个边是否存在。

其中：V是网络的节点集，E是网络的边集。将时间轴T离散为时间点的0≤t₁＜t₂＜…＜t_n=T，记时间窗ΔT={Δt_i|t_i-t_i-1,i=1,2,…,n}，假设网络拓扑结构在每个时间窗Δt_i内保持相对稳定，ρ(e,Δt_i)=1表明在时间Δt_i内图G中的边是存在的，ρ(e,Δt_i)=0则表示边不存在。在VANET中，假设节点的通信半径为R，则网络边存在的集合为E={∃e_uv(△t_i)|u,v∈V,‖u-v‖≤R}。那么在时间T内，VANET拓扑结构可表示为一个时间序列图G_t1,G_t2,…,G_tn。如图 1所示，将时间窗Δt_i内的网络拓扑图G_ti称作时刻t_i时瞬时图。

2 动态中心性研究方法

目前，中心性研究领域已有很多成熟的算法^[12]，包括Katz status score、α-中心性(α-centrality)、介数中心性(betweenness centrality)、接近度中心性(closeness centrality)、PageRank算法及一些基于随机游走的中心性算法，其中最著名的是谷歌的评价页面重要性的PageRank算法，这些中心性算法仅适用于静态网络。本文采用动态网络的时序中心性^[13]研究VANET的动态拓扑特征。

2.1 α-中心性

α-中心性定义为节点i和节点j之间任意长度的衰落路径的总数,具体的计算公式如下：

${{\mathit{\boldsymbol{C}}}^{s}}\left( \alpha ,\beta \right)=\beta \mathit{\boldsymbol{A+}}\beta \alpha {{\mathit{\boldsymbol{A}}}^{2}}+\cdots +\beta {{\alpha }^{n}}{{\mathit{\boldsymbol{A}}}^{n+1}}$

(1)

其中:A为网络的邻接矩阵，α指的是在一条路径中沿着无向边的衰落因子，β指的是在一条路径中沿着有向边的衰落因子。式(1) 中的第一项表示的是从节点i到节点j之间长度为1的路径总数，第二项表示的是从节点i到j之间长度为2的路径总数，其他项以此类推。

在动态网络中，当前时刻的网络结构与历史时刻的状态有某种内在的联系。对于历史时刻的网络而言，与当前时刻的时间距离越远，则对当前时刻的影响力越小。用参数α刻画当前网络拓扑受到历史网络影响的大小。当α=0时，α-中心性衰减为权重为β的度中心性。随着α的增长，α-中心性逐渐演化成一个更全局的测量指标，因为当α越大时，说明当前网络拓扑受到历史网络拓扑影响的时间长度越长。

2.2 无记忆的动态中心性

设假设网络的未来状态G_tk+1只取决于当前网络G_tk，与过去的网络状态都没有关系。此时，在网络中建立的信息传播模型可以作为一个无记忆的动态过程。假设：1) 一个节点在t_k时刻给邻居节点发送信息的概率是β_tk；2) 一个节点将它在t_k时刻收到的信息在t_k+1时刻发送给邻居节点的概率为α_tk+1。为简单起见，假设α_ti=α,β_ti=β。则节点i在t₁时刻开始发送信息到节点j在t_n时刻收到信息的平均信息量可以通过动态中心矩阵表示，即：

$\begin{align} & \mathit{\boldsymbol{C}}_{{{t}_{1}}\to {{t}_{n}}}^{d}(\alpha ,\beta )=\beta \mathit{\boldsymbol{A}}({{t}_{1}})+\beta \alpha \mathit{\boldsymbol{A}}({{t}_{1}})\mathit{\boldsymbol{A}}({{t}_{2}})+ \\ & \cdot \cdot \cdot +\beta {{\alpha }^{n-1}}\mathit{\boldsymbol{A}}({{t}_{1}})\cdot \cdot \cdot \mathit{\boldsymbol{A}}({{t}_{n}}) \\ \end{align}$

(2)

即信息在t_k(1≤k≤n)时刻从任意节点i开始传播在t_n时刻到达任意的节点j。则在时间段T内从节点i发送到节点j的总的信息量可以由累积动态中心矩阵来表示，即

$\mathit{\boldsymbol{C}}_{ij}^{d}(\alpha ,\beta ,T)=\sum\limits_{k=1}^{n}{\mathit{\boldsymbol{C}}_{{{t}_{k}}\to {{t}_{n}}}^{d}}(\alpha ,\beta )$

(3)

2.3 有记忆的动态中心性

在许多动态网络中，网络的未来状态G_tk+1不仅仅取决于它的当前状态G_tk，也有可能取决于它过去的状态G_ti(i＜k)，一般情况下，距离越近，影响越大。另外，为在VANET下实现端到端的车辆间数据投递，国内外研究人员尝试将延迟容忍网络(Delay Tolerant Network, DTN)下的“存储-转发”模式引人到车载数据转发中，并已成为目前VANET下的主要数据转发模式。因此，在VANET中建立的信息传播的模型为一个有记忆的动态过程。首先作如下假设：1) 信息存储的概率为γ，存储的时间长度为m(m∈1,2，…,n)个时隙；2) 一个节点在t_k时刻给邻居节点发送信息的概率是β；3) 一个节点将它在t_k时刻收到的信息在t_k+1时刻发送给邻居节点的概率为α。那么，在t_n时刻信息存储的邻接矩阵取决于先前时间段的一系列邻接矩阵，即：

$\begin{array}{l} \mathit{\boldsymbol{R}}({t_n},\gamma ) = \\ \left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{A}}({t_n}) + \gamma \mathit{\boldsymbol{A}}({t_{n - 1}}) + \cdots + {\gamma ^{m - 1}}\mathit{\boldsymbol{A}}({t_{n - m + 1}}),}&{m ＜ n}\\ {\mathit{\boldsymbol{A}}({t_n}) + \gamma \mathit{\boldsymbol{A}}({t_{n - 1}}) + \cdots + {\gamma ^{n - 1}}\mathit{\boldsymbol{A}}({t_1}),}&{m \ge n} \end{array}} \right. \end{array}$

(4)

由式(2) 可以得到信息存储动态中心矩阵的计算公式为：

$\begin{align} & \mathit{\boldsymbol{RC}}_{{{t}_{1}}\to {{t}_{n}}}^{d}(\alpha ,\beta ,\gamma )=\beta \mathit{\boldsymbol{R}}({{t}_{1}},\gamma )+\beta \alpha \mathit{\boldsymbol{R}}({{t}_{1}},\gamma )\mathit{\boldsymbol{R}}({{t}_{2}},\gamma )+ \\ & \beta {{\alpha }^{2}}\mathit{\boldsymbol{R}}({{t}_{1}},\gamma )\mathit{\boldsymbol{R}}({{t}_{2}},\gamma )\mathit{\boldsymbol{R}}({{t}_{3}},\gamma )+\cdots + \\ & \beta {{\alpha }^{n-1}}\mathit{\boldsymbol{R}}({{t}_{1}},\gamma )\cdots \mathit{\boldsymbol{R}}({{t}_{n}},\gamma ) \end{align}$

(5)

那么，信息存储累积动态中心矩阵为：

$\mathit{\boldsymbol{RC}}_{ij}^{d}(\alpha ,\beta ,\gamma ,T)=\sum\limits_{k=1}^{n}{\mathit{\boldsymbol{RC}}_{{{t}_{k}}\to {{t}_{n}}}^{d}}(\alpha ,\beta ,\gamma )$

(6)

2.4 动态网络中重要节点的度量

在一个动态网络中，某个节点传输信息的能力越大，则表示该节点越重要，因此，可使用动态中心性指标对节点的重要性进行排名。假设在t₁时刻节点i发送了一个单位的信息，那么，在时间段T内从节点i发送到节点j的平均信息量为RC_ij^d(α,β,γ,T)，进一步，在T内从节点i发送信息到网络中其他所有节点的总信息量可以用动态中心性表示，即：

$D{{C}_{i}}(\alpha ,\beta ,\gamma ,T)=\sum\limits_{j}{\mathit{\boldsymbol{RC}}_{ij}^{d}(\alpha ,\beta ,\gamma ,T)}$

(7)

其中：DC_i代表在时间T内节点i动态中心性的值，该值刻画了在过去T时间段内，节点i与网络中其他节点信息的传输能力。DC_i的值越大，节点i越重要。因此，用该指标能够确定在过去一段时间内网络中最具影响力的节点。

3 仿真实验与结果分析 3.1 VANET仿真环境

本文采用VanetMobisim^[14]软件建立VANET环境，仿真中车辆的移动采用移动模型刻画。文献[15]和^[16]对各类移动模型的性能作了详细比较，移动模型主要分为以下五类：1) 随机移动模型，该模型没有任何限制条件；2) 时间依赖模型，节点当前时刻的移动受到以往时刻移动的影响，比如平滑移动模型(Smooth Mobility Model, SMM)；3) 空间依赖模型，移动受到周围节点的影响，比如车流交通模型(Fluid Traffic Model,FTM)；4) 地理限制模型，移动位置受到地图的限制,比如基于图的移动模型(Graph-Based Mobility Model, GBMM)；5) 混合移动模型，即将时间依赖、空间依赖和地理限制相结合的模型,比如智能驾驶员模型(Intelligent Driver Model with Lane Changes, IDM-LC)^[17]。表 1给出了各移动模型的宏观和微观移动特性，√表示模型具有该属性，×表示模型不具备该属性。鉴于这些模型中IDM-LC最能准确刻画车辆的移动特征，因此，本文采用IDM-LC研究VANET动态拓扑特征。

IDM-LC模型是一种微观交通流模型，是在IDM的基础上增加了车辆在十字路口的管理及车辆换道功能的智能移动模型，使得其更加符合真实的交通场景。IDM-LC移动模型中车辆长度为5 m，加速度a和减速度b分别为0.6 m/s²和0.9 m/s²，礼貌参数p为0.5，其他参数设置如表 2所示。

3.2 VANET动态中心性分析

VANET时序网络建模过程中，假设网络拓扑结构在每个时间窗Δt_i内保持相对稳定。由于车载自组织网络中车辆移动速度比较快，拓扑结构变化较快，因此Δt_i的值越小，得出的研究结论越精确，仿真实验中假设时间窗Δt_i=1 s。节点动态中心性评价模型中包括了四个参数α、 β、γ和m，每个节点中心性的值通过式(7) 得到。由于β的值不影响重要节点的排名，不失一般性，令β=1。衰落因子α描述了当前网络拓扑与历史网络拓扑之间的联系。信息存储概率γ和存储时间长度m能够刻画VANET中信息的存储转发机制，这两个参数也体现了信息在网络中的记忆性，即信息存储概率γ和存储时间长度m越大，信息被记忆和保留的时间越长，成功转发的概率越大。下面研究节点动态中心性与这些参数之间的关系。

图 2为衰落因子α对VANET动态中心性(DC)的影响，其中信息存储概率γ=0，信息保留时间m=50 s。由图 2可知，随着α的增加，网络中各节点动态中心性的值也在逐渐增大，相应的各节点的排名情况也发生变化。如节点16，当α=0.2时，DC₁₆=551.141，且它在整个网络中的排名最高；当α=0.4,0.6,0.8时，DC₁₆的值分别为： 64 460.341、 142 811 257 731 289、 3.604 089 454 264 42e+25，节点16对应的排名分别为1、5、4、4，由此也可知，尽管随着α的变化，节点16的动态中心性也发生了变化，但它在整个网络中的重要性排名仍然靠前。由于样本较少，用Lilliefors检验方法检验DC的统计特征，检验结果表明不同α时，DC并不具有正态性。

图 3为α不同时VANET中重要节点排名随时间变化的情况，选取排名前五位的重要节点。由图 3(a)知，当α=0.2时，网络中重要节点的排名随时间的变化波动比较大，如节点42，在前30 s排名第一，而到了后面排名逐渐降低，但它仍是网络中比较重要的节点。由图 3(b)可知，当α=0.4时，重要节点排名情况相较于α=0.2时有细微变化，排名前五位的重要节点由42、16、27、35、20变化为42、17、48、8、16。图 3(c)和图 3(d)相比较可发现，当α≥0.6时，网络中重要节点的动态中心性排名整体上基本趋于稳定，重要节点排序不变，依次为42、8、35、16、27。在VANET中，这些节点表示的车辆在信息传送时起着至关重要的作用，如果某个重要节点受到干扰或破坏，整个网络的连通性和数据传输效率都会受到较大的影响，因此，在真实的VANET中，为了提高网络效率，可以加强对这些节点的保护措施。由于这些相对重要的节点趋于网络的中心地位，在网络的信息传播中也起着关键的作用，所以在信息传送时，也可以尽可能地将一些比较重要的信息传送给这些节点，由此来提高网络信息传送的效率。如果遇到紧急情况时，提高网络信息传送效率也可以避免一些不必要的损失。

图 4表示的是在衰落因子α=0、信息保留时间m=50时，信息存储概率γ对VANET动态中心性的影响。由图 4可知，随着信息存储概率γ的增加，网络的动态中心性也逐渐增大，但网络各节点的排名趋势基本是一致的，节点的重要性没有发生变化。从图 4中可以看出，在整个网络中，节点42排名最高，相对重要的节点依次还有35、16、20、27。用Lilliefors检验方法检验不同γ时DC的正态性，检验结果表明DC服从正态分布，γ为0、0.5和1时，其正态分布的均值的置信区间(95%)分别为[41.425，59.855]、[81.153，117.527]和[932.139,1 344.340]。方差的置信区间(95%)分别为[27.086,40.406]、[53.457,79.745]和[605.787,903.699]。

图 5为γ分别为0、0.5和1时重要节点排名。仿真结果表明虽然γ的值不同，但重要节点的排名次序没有发生任何变化(不同γ值的曲线完全重合)。由此可见，节点重要性具有稳定性，且信息存储概率γ对其没有影响。

图 6是衰落因子α=1和信息存储概率γ=1时，信息存储时间m对VANET动态中心性的影响。由图 6可知：信息存储时间m越大，网络的动态中心性也越大；当信息存储时间超过整个网络的时间时，动态中心性的值不再发生变化。尽管节点动态中心性的值随着m的增加逐渐增大，但网络中各节点的排名情况没有发生变化，即信息存储时间对VANET中重要节点排名影响不大。由图 6中可以看出节点42的排名还是最高的，相对重要的节点依次还有8、27、16、35。

上述实验研究了衰落因子、车辆间信息存储概率以及车辆间信息存储时间等因素对VANET的动态中心性的影响，实验结果表明，与其他社会网络(比如引文网^[12])不同,随时间的演化，VANET中的重要节点保持相对稳定的状态，利用该特征可有效提高VANET数据包的传输效率。

4 结语

动态变化的网络拓扑结构是车载自组织网络的重要特点之一。本文主要介绍VANET动态中心性的研究方法，给出了VANET动态中心性测度指标，应用VanetMobisim车辆仿真软件研究了衰落因子、车辆间信息存储概率以及车辆间信息存储时间等因素对VANET动态中心性的影响。通过对VANET动态中心性的研究，我们发现网络中的重要节点具有良好的稳定性，一方面，利用这一特征能更好地确定信息传播中的中继节点，从而实现信息的成功投递，为开发新VANET的路由算法提供指导；另一方面，通过加强对这些重要节点的保护措施，可以提高VANET的网络生存性和抗毁性。