随着自动驾驶技术^[1]的高速发展，智能交通系统中的车辆自组织网络(vehicular ad hoc network, VANET)能够显著提升用户娱乐满意度，受到了广泛的关注和研究^[2]. 在VANET中，配备无线接口的车辆可以通过车对车(vehicle to vehicle, V2V)通信方式直接与附近的车辆通信；同时，也可以与固定的路边单元(road side unit, RSU)进行通信，称为车辆对基础设施(vehicle to infrastructure, V2I)通信方式^[3]. 当车辆高速移动时，拓扑持续变化，V2V和V2I通信方式存在传输链路不稳定甚至中断的问题，已经成为面向应用的VANET亟待解决的瓶颈问题.

分簇算法将具有相似特性的车辆集聚在一起^[4]，通过单个集群内部簇头与簇员之间交互以及多个集群间簇头的数据交互，能够有效解决上述VANET中信息传输链路不稳定的问题. 最小编号分簇算法^[5]是最早提出的经典分簇算法，仅利用车辆的编号进行分簇，其簇头选取指标维度单一且未考虑车辆速度、加速度和距离等物理属性，难以应用于实际VANET中. Ren等^[6]所提分簇方案将车辆移动方向、相对速度、相对距离和链路寿命作为筛选指标，Kang等^[7]将车辆的行驶轨迹作为分簇依据，Sennan等^[8]在动态场景下，通过对智能算法的应用将距离作为唯一因素进行簇头、簇员的筛选，得到的簇头移动相似性较强，在VANET中的适用性有所提高.

随着万物联网和人工智能的迅猛发展，上述仅考虑物理属性的分簇算法已经无法满足未来车联网中分簇人性化和簇内高亲密度的需求. 因此，近年来国内外学者将社交属性的概念引入VANET中，研究具有社交属性的新型车辆分簇算法. Daeinabi等^[9]提出基于权重的车辆分簇算法，将不信任值引入分簇算法，计算车辆不信任值、熵值、邻居数量和相对位置的加权和，分值最小者当选簇头，该算法可以实现对系统中恶意节点的筛选. Garbiso等^[10]将社区中心度作为簇头筛选指标之一，在拓扑结构角度寻找最稳定的簇头，但是并未考虑车辆自身的“社交意愿”是否强烈以及个人喜好是否能够实现可信存储的问题.

近年来，作为分布式账本^[11]被人熟知的区块链技术逐渐被广泛研究，应用于不同场景的基于区块链的车联网架构逐渐被提出^[12-13]. 依赖于区块链加密、共识和智能合约等关键技术，基于区块链的车联网可以实现不可信节点之间的可信交易^[14].

为了实现可信且人性化的分簇，同时提高簇内亲密度，提出活跃度感知社交车辆分簇算法，主要工作如下：1) 构建社交车联网3层体系架构，由区块链、物理实体层、社交关系层3层组成. 针对物理实体层，进行系统模型的详细介绍. 2) 设计活跃度感知的社交车辆分簇算法，由簇的形成、簇头选举和簇的维护三阶段构成。在簇的形成阶段，车辆通过周期性广播信标消息判断周围车辆的属性信息。在簇头选举阶段，在同时考虑车辆移动相似性分值和社交相似性分值的基础上，判断车辆的活跃度进行簇头筛选，以保证所得集群成员间的稳定性和亲密度。在簇的维护阶段，当簇头未及时响应消息或出现异常行为时，重分簇过程将会启动. 3) 利用OMNet++、Veins和SUMO软件实现车辆分簇算法的动态性仿真，搭建基于802.11p协议的仿真环境，较好地还原道路上车辆行驶的真实场景，验证本研究所提分簇算法的有效性.

提出区块链辅助的分布式车载社交网络架构，旨在实现对具有社交属性的车辆进行人性化分簇及隐私信息的安全可信存储. 区块链辅助的车载社交网络架构如图1所示，整体网络架构分为3层，区块链层、物理层与社交关系层.

1) 物理层. 车辆作为通信节点通过建立V2V、V2I链路与车辆或者基站进行资源交互；基站作为路边通信单元为车辆提供资源，同时作为分布式数据库存储车辆的隐私状态之类的数据. 在车载社交网络中，车辆的兴趣点与活跃度2个社交属性被考虑进系统，通过区分颜色和大小将通信节点的社交属性映射至社交关系层. 为了实现车辆信息的全局可查询，由基站维护的区块链层被构建.

2) 社交关系层.由车辆映射出的虚拟节点构成，不同颜色代表不同的兴趣点，节点的大小差异反映车辆自身活跃度的强弱. 物理层中车辆触发分簇过程后，社交关系层中节点会进行动态、实时的映射，直观展示社交相似性、活跃度在簇头选举过程的影响与作用.

3) 区块链层. 由区块链节点构成，区块链节点由基站进行维护. 车辆的分簇、状态、兴趣点等隐私信息经过簇头加密后发送至基站，基站在将其存储至本地数据库的同时添加索引. 为了实现车辆信息的全局可查询，基站通过存储证明(proof of storage, PoS)达成节点共识，将加密内容的索引存储至新的区块中，进而构成区块链. 其中，全局可查询的实现分为3步：车辆对基站发出查询请求；基站通过智能合约访问区块链中存储的索引；基站按照获取到的索引信息进行数据查询与获取.

基于所提出的架构模型，构建具有社交属性的车辆自组织网络系统. 在物理层中，假设道路上有 $ N $辆车，表示为 $ {{V}}{\text{ = \{ }}{v_1}{\text{,}}{v_2}{\text{,}}{v_3}{\text{,}} \cdots {\text{,}}{v_N}{\text{\} }} $，每辆车都具有自己的属性集 $ {S_i} = \left\{ {S_i^{{\text{Phy}}},S_i^{{\text{Soc}}}} \right\} $， $ S_i^{{\text{Phy}}} $为车辆的物理属性集， $ S_i^{{\text{Soc}}} $为车辆的社交属性集. 物理属性集 $S_i^{{\text{Phy}}} = \left\{ {{\rm{I}}{{\rm{D}}_i},S_i^{{\text{Loc}}},S_i^{{\text{Vel}}},S_i^{{\text{Acc}}},S_i^{\rm{t}}} \right\}$包含车辆的身份信息、位置信息、速度信息、加速度信息及时间戳信息. 其中， $ S_i^{{\text{Loc}}} = \left\{ {{x_i},{y_i}} \right\} $，坐标值表示车辆 $ i $在时刻 $t$的位置. $ {S}_{i}^{\text{Soc}}=\left\{{I}_{i,j}^{\text{s}}，Q(i,{f}_{j})\right\} $表示车辆的社交属性集，包含车辆 $ i $与其一跳邻居车辆 $ j $关于某个兴趣点的相似度 $I_{i,j}^{\rm{s}} $以及车辆 $ i $对基站或者路边单元 $ {f_j} $的资源请求次数 $ Q(i,{f_j}) $.

在本研究所提活跃度感知的社交车辆分簇算法中，每辆车配备有车载单元(on board unit, OBU)无线接收器和发射器，同时配备有全球定位系统(global positioning system, GPS)以及时更新车辆的位置信息. 可以计算每辆车与一跳邻居车辆的相对速度及相对距离.

在车载社交网络中，分簇过程可以分为簇头选择及簇员选择2个过程，为了使簇更加稳定，所设定指标筛选出的簇头应当与簇内其他车辆具有较高的社交相似性及移动相似性，即倾向于选择社交中心度高、辐射范围大的车辆. 簇员则是从簇头的一跳邻居车辆中以一定指标进行选择.

如图2所示，车辆以时间间隔 ${t_{\rm{I}}}$接连进入长度为 $L$的一段道路，车辆行驶速度最大为120 km/h. 假设每辆车发送的信息都是可信的，在每个信标间隔（beacon interval, ${\text{BI}}$），车辆会将信标消息 $ {{\rm{Beacon}}\_{\rm{Msg}}} $进行广播. 每辆车根据对其物理相似性和社交相似性的判断，选择分值最高的车辆. 而后再对其进行活跃度筛选，活跃度越高映射到社交层的节点越大. 图2中，2个簇 ${C_i}$和 ${C_{i + 1}}$已经用矩形框标出，簇头的社交活跃度最高位于中心位置，具有相同兴趣的车辆构成一个簇，其中，簇头与组员之间的距离 $ {D_{{v_i},{v_j}}} $小于车辆间的稳定通信范围 $ D_{\rm{v}}^{{\text{st}}} $.

在所提分簇算法中，车辆的4种状态转换如图3所示，状态的详细说明如表1所示. 图中，T_UD为刚进入系统中处于UD状态的车辆的倒计时器所代表的时间，CML为一跳邻居列表， $S_i^{{\rm{Act}}}$为车辆的活跃度表达化.

如图3所示，所有车辆进入系统后的初始状态为未定义状态，随即计时器 $ {T_{{\rm{UD}}}} $开始计时. 在计时结束时若收到来自簇头的信标消息 $ {{\rm{Beacon}}\_{\rm{Msg}}} $，状态转换至CM；若未收到，车辆会计算自身的综合分值及活跃度值，超过设定阈值的车辆成为簇头候选者，簇头候选者中活跃度最高者成为簇头. 若在计时结束时车辆仍处在未定义状态，则会单独成簇作簇头，但一跳邻居表为空的簇头最终会进入别的簇成为簇员.

初始状态为UD的车辆在进入系统后会周期性地广播信标消息 $ {{\rm{Beacon}}\_{\rm{Msg}}} $，消息中包含车辆的物理属性（车辆ID、位置、速度、方向）、社交属性及状态信息. 信标消息在一跳邻居车辆中进行广播以建立、更新一跳邻居列表(cluster member list, CML). 车辆在进入网络后会等待 $ {T_{{\rm{UD}}}} $时间，如果在这期间收到了来自CH的信标消息 $ {{\rm{Beacon}}\_{\rm{Msg}}} $，同时车辆与CH方向相同、社交相似性高，车辆将传回 $ {{\rm{Ack}}\_{\rm{Msg}}} $加入簇，否则会忽略该信标消息.

当前大多研究工作仅仅考虑移动相似性即相对速度、相对加速度以及行驶方向等因素作为簇头选择的依据，而忽略车辆在行驶时处理数据的能力等级与社交关系的影响. 在车载社交网络中，选择稳定可靠的簇头尤为重要，因此本研究设计了一种活跃度感知的社交车辆分簇算法. 其中，簇头筛选过程如图4所示，分为3个阶段：相似性分值计算、簇头候选者选举及活跃度值计算.

在第1阶段，考虑由相对加速度、相对速度和相对距离构成的移动相似性分值以及由兴趣相似度定义的社交相似性分值. 在第2阶段，利用基数排序算法对上述两值加权求和得到车辆总相似性分值进行排序并筛选出分值最高的车辆作为簇头候选者. 在第3阶段，引入由车辆历史数据处理量和车辆请求资源次数构成的活跃度的概念，对簇头候选者进行活跃度值判断，筛选出真正有社交意愿和能力的簇头.

1）第1阶段，相似性分值计算. 当车辆收到信标消息，感知到道路情况且已经建立了自己一跳邻居列表后，每辆车都能够计算出一个归一化的相似性分值，由移动相似性和兴趣相似度两部分构成. 其中，移动相似性包含车辆对其一跳邻居相对速度、相对距离及相对加速度的计算. 兴趣相似度包含两车对某一内容感兴趣程度的计算. 车辆与其一跳邻居车辆的速度、加速度及距离越接近，一跳邻居越多，则其相似性分值越高，就越有机会成为簇头. 相似性分值的表达式如下：

(1) $ S_i^{{\text{tot}}} = p{S_i} + q{I_i} . $

式中： $ p $、 $q$为权重因子， $p + q = 1.0$， $ p,q \in \left[ {0,1.0} \right] $；S_i为移动相似性；I_i为兴趣相似度.

移动相似性表达式如下：

(2) $ {S_i}{\text{ = }}{{\sum\nolimits_j {{M_{i,j}}} } \mathord{\left/ {\vphantom {{\sum\nolimits_j {{M_{i,j}}} } {{D_i}}}} \right. } {{D_i}}} . $

式中： $ {M_{i,j}} $为车辆 $ i $、 $ j $之间的移动相似值， $ {D_i} $为车辆 $ i $可通信范围内一跳邻居的数量.

(3) $ {M_{i,j}} = {{{a_{i,j}}v_{i,j}^{{\text{vel}}}} \mathord{\left/ {\vphantom {{{a_{i,j}}v_{i,j}^{{\text{vel}}}} {{d_{i,j}}}}} \right. } {{d_{i,j}}}} . $

式中： $ {a_{i,j}} $为两车之间的相对加速度， ${a_{i,j}} = {\min\;  ({a_i},{a_j})} / $ $ {\max \; ({a_i},{a_j})}$； $ v_{i,j}^{{\text{vel}}} $为两车之间的相对速度^[15]， $v_{i,j}^{{\text{vel}}} = $ $ {{\min\;  (v_i^{{\text{vel}}},v_j^{{\text{vel}}})} / {\max\;  (v_i^{{\text{vel}}},v_j^{{\text{vel}}})}}$； $ {d_{i,j}} $为两车之间的相对距离， $ {d_{i,j}} = {\left[ {{{\left( {{x_i} - {x_j}} \right)}^2} + {{\left( {{y_i} - {y_j}} \right)}^2}} \right]^{1/2}} $.

针对某一兴趣点 $ \alpha $，相似度表达式^[16]如下：

(4) $ {I_i}{\text{ = }}{{\sum\nolimits_j {I_{i,j}^{\text{s,}\alpha}}} \mathord{\left/ {\vphantom {{\sum\nolimits_j {{M_{i,j}}} } {{D_i}}}} \right. } {{D_i}}} . $

(5) $ \begin{split} I_{i,j}^{\text{s,}\alpha} =\;& {\rm{sim}}\; \left( {{v_{\alpha i}},{v_{\alpha j}}} \right) =\hfill \\ \;& \frac{{{{\boldsymbol{I}}_{{v_{\alpha i}}}} \cdot {{\boldsymbol{I}}_{{v_{\alpha j}}}}}}{{\left\| {{{\boldsymbol{I}}_{{v_{\alpha i}}}}} \right\| \left\| {{{\boldsymbol{I}}_{{v_{\alpha j}}}}} \right\|}} = \frac{{\displaystyle \sum\limits_\alpha {{{{I}}_{{v_{\alpha i}}}} \times {{{I}}_{{v_{\alpha j}}}}} }}{{\sqrt {\displaystyle \sum\limits_\alpha {{{I}}_{{v_{\alpha i}}}^2} } \sqrt {\displaystyle \sum\limits_\alpha {{{I}}_{{v_{\alpha j}}}^2} } }} . \end{split} $

式中： $I_{i,j}^{{\rm{s}},\alpha }$为车辆i、j之间关于兴趣点α的兴趣相似度； ${v_{\alpha i}}$为车辆i对兴趣点α的兴趣度， ${{\boldsymbol{I}}_{v_ {\alpha i}}}$为车辆i对于兴趣点α的兴趣度的向量.

2）第2阶段，簇头候选者选举. 当刚驶入道路处于UD状态的车辆在 $ {T_{{\rm{UD}}}} $内，对车辆与其一跳邻居的相似性分值进行计算，如第1阶段所述，将计算得出的分值利用基数排序算法进行排序，相似值得分最高者状态转换至簇头候选者CHc. 若多辆车的相似性分值相同，则多辆车状态都转换为CHc，而后通过计算车辆的活跃度来判断其是否有资格成为CH.

3）第3阶段，活跃度值计算. 为了考虑车辆的实际属性，对车辆的活跃度进行建模，可以计算出每辆车归一化后的活跃值. 本研究中活跃度主要考虑车辆节点与其他车辆交互的历史数据计算量以及向路边单元或基站请求资源的次数. 活跃度表达式如下：

(6) $ S_i^{{\text{Act}}} = \frac{1}{{{{\log }_2}\;\left( {1 + \sqrt 2 } \right)}}{\log _2}\;\left( {1 + \sqrt {A_i^{{\text{nor}}} + Q_i^{{\text{nor}}}} } \right) .$

式中： $ A_i^{{\text{nor}}} $表示车辆 $ i $过去3 d处理数据量的归一化数值， $ Q_i^{{\text{nor}}} $表示车辆过去3 d与路边单元或基站的交互次数.

车辆的归一化数据量 $ A_i^{{\text{nor}}} $可以体现出车辆实际传输数据的能力，表达式如下：

(7) $ A_i^{{\text{nor}}} = \frac{{A_i^{{{d}}\max } - {A_i}}}{{A_i^{{{d}}\max } - A_i^{{{d}}\min }}} .$

式中： ${A_i^{{{d}}\max}}$为车辆当日处理数据量最大值； ${A_i} = $ $ \;\beta {\bar A_i^{{{d}}3}} + \left( {1 - \;\beta } \right)A_i^{{d}}$， $\;\beta$为权重系数， $\;\beta = \left( {\beta _1} + {\beta _2} + {\beta _3} \right) /3 $， ${\bar A_i^{{{d}}3}}$为过去3 d处理数据量的加权平均值， $A_i^{{d}}$为车辆 $ i $当日累积处理数据量.

(8) $ {\bar{A}_i^{{{d}}3}} = \frac{{{\beta _1}A_i^{{{d}} - 1} + {\beta _2}A_i^{{{d}} - 2} + {\beta _3}A_i^{{{d}} - 3}}}{{{\beta _1} + {\beta _2} + {\beta _3}}} . $

式中： $A_i^{d - 1}、A_i^{d - 2}、A_i^{d - 3}$为过去3 d每天的当日累积处理数据量；每天数据量的权重根据艾宾浩斯^[17]曲线占比确定，即 $ {\;\beta }_{1}\text{=}0.337，{\beta }_{2}\text{=}0.278，{\beta }_{3}\text{=}0.272 $.

(9) $ A_i^{{d}} = {R_i} {T_i} . $

式中： $ {R_i} $为车辆 $ i $的数据传输速率， ${R_i} = B{\log _2}\;\left( 1 + $ $ {\rm{SN}}{{\rm{R}}_{i,j}} \right)$，B为系统带宽， $ {\rm{SN}}{{\rm{R}}_{i,j}} = {P_i}{h_{i,j}}/{N_0} $， $ {P_i} $为 $ {v_i} $的传输发射功率， $ {h_{i,j}} $为车辆 $ i $与车辆 $ j $的传输信道增益^[18]， $ {N_0} $为高斯白噪声功率； $ {T_i} $为车辆 $ i $与其他车辆交互的总时间， ${T_i} = \displaystyle \sum\nolimits_j {{t_{i,j}}}$， $ {t_{i,j}} $为车辆 $ i $与某一车辆 $ j $的交互时间.

(10) $ Q_i^{{\rm{nor}}} = \frac{{Q_i^{{{d}}\max } - {Q_i}}}{{Q_i^{{{d}}\max } - Q_i^{{{d}}\min }}} . $

式中： $ {Q_i} $为交互次数， ${Q_i} = \gamma {\bar{Q}_i^{{{d}}3}} + \left( {1 - \gamma } \right)Q_i^{{d}}$. $ \gamma $为权重系数， $ \gamma = \left( {{\gamma _1} + {\gamma _2} + {\gamma _3}} \right)/3 $； ${\bar{Q}_i^{{{d}}3}}$表示过去3 d交互次数的加权平均值 ${\bar{Q}_i^{{{d}}3}} = $ $ \left( {{\gamma _1}Q_i^{{{d}} - 1} + {\gamma _2}Q_i^{{{d}} - 2} + {\gamma _3}Q_i^{{{d}} - 3}} \right)/ $ $ \left( {{\gamma _1} + {\gamma _2} + {\gamma _3}} \right)$； $Q_i^{{d}}$表示车辆 $ i $当日向所有基础设施请求资源的总次数， $Q_i^{{d}} = \displaystyle \sum\nolimits_j {Q\left( {i,{f_j}} \right)}$， $ Q\left( {i,{f_j}} \right) $表示车辆 $ i $向某一基础设施 $ {f_j} $请求资源的次数.

若选举出的CHc的活跃度值大于 $ {\text{ActThre}} $，则CHc被选举为簇头CH，若有多个CHc活跃度值都满足阈值，则选择活跃度值最高的作为CH. 随即，CH会广播自己成为簇头的通知消息 ${\rm{CH}}\_ $ $ {\rm{Notification}}$，其一跳邻居列表中的车辆成为其簇员CM. 活跃度感知的社交车辆分簇算法流程如下.

1. 车辆属性初始化，状态初始化为 ${\rm{U}}{{\rm{D}}_i}$，设置定时器 ${T_{{\rm{UD}}}}$

2. 车辆周期性广播 ${{\rm{Beacon}}\_{\rm{Msg}}}$告知周围车辆自身属性

3. $if$车辆 ${v_i}$的 $\;{T_{{\rm{UD}}}} = = 0:{\rm{U}}{{\rm{D}}_i} \to {\rm{C}}{{\rm{H}}_i}$

4. $end\;if$

5. $if$车辆 ${v_i}$的 $\;{T_{{\rm{UD}}}} > 0$

6. $if$车辆 ${v_i}$未收到 $ {\text{service}}\;{\text{message}} $

7. 监听并解析 ${{\rm{Beacon}}\_{\rm{Msg}}}$，将消息中的车辆属性信息存入车辆集合

8. $if\quad N > {\text{threshold}}$

9. 计算集合内车辆的 $S_i^{{\text{tot}}}$

10. $if\;S_i^{{\text{tot}}}{\text{ = MAX}}\;\left( {S_i^{{\text{tot}}}} \right)$

11. 车辆 ${v_i}$: ${\rm{U}}{{\rm{D}}_i} \to {\rm{CH}}{{\rm{c}}_i}$

12. $if\;S_i^{{\text{Act}}} > {\text{ActThre}}$

13. 车辆 ${v_i}$: $ {\rm{CH}}{{\rm{c}}_i} \to {\rm{C}}{{\rm{H}}_i}$，车辆向一跳邻居广播 $ {\text{service}}\;{\text{message}} $，宣布 ${\rm{CID}}$、 ${\rm{CH}}$的ID和 ${\rm{CM}}$的ID

14. $end\;if$

15. $end\;if$

16. $end\;if$

17. $else\;if$车辆 ${v_j}$收到 $ {\text{service}}\;{\text{message}} $

18. $if\quad {\text{ID}}\left( {{v_j}} \right){\text{ = ID}}\left( {{\rm{C}}{{\rm{H}}_i}} \right)||{\text{ID}}\left( {{v_j}} \right){\text{ = ID}}\left( {{\rm{C}}{{\rm{M}}_i}} \right)$

19. 车辆 ${v_j}$: ${\rm{U}}{{\rm{D}}_j} \to {\rm{C}}{{\rm{H}}_j}||{\rm{U}}{{\rm{D}}_j} \to {\rm{C}}{{\rm{M}}_j}$

20. $else\;$

21. 车辆 ${v_j}$维持 ${\rm{U}}{{\rm{D}}_j}$状态至 $\;{T_{{\rm{UD}}}} = = 0$，而后执行步骤2）.

22. $end\;if$

23. $end\;if$

24. $end\;if$

25. $end$

当簇已经形成且簇头选举完成后，就会进入簇的维护阶段. 在该阶段，维持簇的高稳定性是主要目标，以便于后续车辆间的数据传输操作. 在本研究中，CM通过周期性与CH进行实时属性消息的交互来确保整个簇的稳定性. 如果CH收到消息未进行响应或者CH出现一些异常行为，重分簇过程将会启动. 按照本研究提出的分簇算法选举出新的簇头，而后再进行簇内数据和信息交互.

为了验证本研究所提算法的有效性，借助SUMO^[19]和Veins^[20]实现仿真场景的生成，而后通过OMNet++仿真平台对算法进行动态仿真.

如图5所示为仿真过程使用的道路截图. 总长度为5 km的双车道双向道路上行驶着车辆，如黄色箭头所示，其长度为5 m. 具体的仿真参数如表2所示.

分别从稳定通信距离 $D_{\rm{v}}^{{{{{\rm{st}}}}}}$、车辆行驶最大速度 ${V_{{\text{MAX}}}}$和不同算法对比3个方面对本研究所提算法进行稳定性分析.

在仿真过程中，道路上总车辆数为 $ N $，不同状态车辆平均数量表达式如下：

(11) $ \overline N _{s}^{}{\text{ = }}{{\sum\limits_{{\rm{\omega}} = 1}^{\rm{\xi}} {N_{s,\omega}^{}} } \mathord{\left/ {\vphantom {{\sum\limits_{\omega = 1}^\xi {N_{s,\omega}^{}} } \xi }} \right. } {\rm{\xi}} }. $

式中：ξ为算法的迭代次数； $ N_{s,\omega}^{} $为处于不同状态的车辆在第ω次迭代时的数量， $ s \in \left\{ {\rm{{UD,CH,CM}}} \right\} $， $ \overline N _{{\rm{CH}}}^{} $、 $ \overline N _{{\rm{CM}}}^{} $和 $ \overline N _{{\rm{UD}}}^{} $分别表示分簇仿真过程中，簇头车辆、簇员车辆和未定义状态车辆的平均数量.

处于不同状态车辆的平均持续时间占比表达式如下：

(12) $ \overline T _{s}^{{\text{dur}}}{\text{ = }}{{\left( {\sum\limits_{\omega = 1}^\xi {T_{s,\omega}^{{\text{dur}}}/{T^{{\text{sim}}}}} } \right)} \mathord{\left/ {\vphantom {{\left( {\sum\limits_{\omega = 1}^\xi {T_{s}^{{\text{dur}}}/{T^{{\text{sim}}}}} } \right)} \xi }} \right. } \xi }. $

式中： $ s \in \left\{ {{\rm{UD}},{\rm{CH}},{\rm{CM}}} \right\} $， $ T_{s,\omega}^{{\text{dur}}} $为处于不同状态的车辆在第ω次迭代时的持续时间， $T^{\text{sim}}$为设定的分簇仿真时间. 在分簇过程中， $ \overline T _{{\rm{CH}}}^{{\text{dur}}} $为簇头的平均持续时间占比， $ \overline T _{{\rm{CM}}}^{{\text{dur}}} $为簇员的平均持续时间占比， $ \overline T _{{\rm{UD}}}^{{\text{dur}}} $为未定义状态车辆的平均持续时间占比.

在分簇过程中， $ D_{\rm{v}}^{{\text{st}}} $和 ${V_{{\text{MAX}}}}$都是变量，对其调节，观察其对分簇过程的影响.

当 ${V_{{\text{MAX}}}}$=60 km/h时，车辆i做簇头时与周围n个一跳邻居车辆形成的簇中车辆总数量 ${C_{i,n}}$随 $ D_{\rm{v}}^{{\text{st}}} $变化的情况如图6所示. 可以看出，随着 $ D_{\rm{v}}^{{\text{st}}} $的增加， ${C_{i,n}}$的范围在扩大，最小值为2，最大值由7增至10.

在本研究所提分簇算法下，不同状态车辆的持续时间及数目的变化情况如图7所示. 可以看出，当 ${C_{i,n}} \geqslant 3$时，CM持续时间占比随着 ${C_{i,n}}$的增大呈现出缓慢上升趋势，CH持续时间呈缓慢下降趋势，UD的持续时间占比较小. 在分簇过程中，3种状态车辆的持续时间占比并未随着 $D_{\rm{v}}^{{\text{st}}}$的变化出现剧烈波动情况，说明所提算法在分簇时表现较稳定.

稳定通信距离和成簇数对集群车辆数量的影响如图8所示. 可以看出，当 ${C_{i,n}}{\text{ = }}2$时，CH和CM数目大致相同；当 ${C_{i,n}} \geqslant 3$时，CH数量呈缓慢下降趋势，CM数量呈缓慢上升趋势. 即不论 $ D_{\rm{v}}^{{\text{st}}} $的大小，处于不同状态车辆的数目趋势大致相同，说明文中所提算法的效果较稳定，分簇结果并不会因为通信距离 $ D_{\rm{v}}^{{\text{st}}} $的变化而产生剧烈的波动.

由图6可知，在 $ D_{\rm{v}}^{{\text{st}}} $变化过程中， ${C_{i,n}}$的中位数为4~6. 因此，在后续的仿真参数中，选择 ${C_{i,n}} = 5$， $ D_{\rm{v}}^{{\text{st}}} = 300\;{\text{m}} $^[22]作为典型场景进行仿真.

如图9(a)、(b)所示分别为车辆分簇过程中不同状态车辆持续时间占比及数目随 ${V_{{\text{MAX}}}}$变化的情况. 如图9(b)所示，在 ${V_{{\text{MAX}}}}$由30 km/h增至120 km/h的过程中，不同状态下的车辆数目并未出现明显的波动，说明本研究所提分簇算法稳定性较好，不会受到车辆 ${V_{{\text{MAX}}}}$的影响.

为了更好地对本研究所提算法的稳定性进行分析，选择3种算法进行仿真对比，包括自适应分簇算法^[10]、动态分簇算法^[6]和经典最小编号算法^[5]，观察不同分簇算法下，在 ${V_{{\text{MAX}}}}$变化过程中，不同状态下的车辆数目和持续时间占比的变化情况.

在 ${C_{i,n}} = 5$、 $D_{\rm{v}}^{{\text{st}}} = 300\;{\text{m}}$的条件下，CH、CM和UD状态的持续时间随 ${V_{{\text{MAX}}}}$的变化情况如图10所示. 曲线走势越平稳、起伏越少，CH持续时间与CM持续时间的比值越接近于1∶4，则算法表现越优秀. 可以看出，与其他3种算法不同，使用动态分簇算法，CH平均持续时间呈下降趋势，CM持续时间呈上升趋势，UD持续时间呈缓慢上升趋势. 这是因为在动态分簇算法中，当 $ {T_{{\rm{UD}}}} $倒计时结束后，车辆状态将直接由UD转换为CH. 在相同时间内， ${V_{{\text{MAX}}}}$小则车辆间距离远无法成簇，故大部分车辆都转换为独立CH. 当 ${V_{{\text{MAX}}}}$较大时，相同时间内车辆间距离缩短，形成正常集群的车辆居多，独立CH数量减少. 因此，CH持续时间呈下降趋势，CM、UD持续时间呈上升趋势. 而在使用本研究分簇算法、经典最小编号分簇算法和自适应分簇算法3种算法时，CH、CM持续时间占比整体呈平缓下降趋势，UD持续时间呈平缓上升趋势. 因为上述3种算法较少出现独立CH的情况，即3种状态的持续时间不会受 ${V_{{\text{MAX}}}}$的影响而产生剧烈波动，说明算法较稳定. 其中，经典最小编号分簇算法稳定性最好，本研究所提分簇算法的稳定性位居第2.

4种分簇算法在 ${C_{i,n}} = 5$、 $D_{\rm{v}}^{{\text{st}}} = 300\;{\text{m}}$的条件下，CH、CM和UD的车辆数量随 ${V_{{\text{MAX}}}}$的变化情况如图11所示. 可以看出，当使用动态分簇算法时，算法集群数即CH数量呈下降趋势；CM数量呈平缓上升趋势；UD状态车辆逐渐增多. 产生上述情况的原因是，该算法中规定车辆满足一定的等待时间后即会自动转为簇头，故在车辆行驶速度缓慢、车辆之间相遇时间较长时，簇头数量最多. 同时也意味着单辆车形成的簇居多，真正具有簇员的簇数量较少. 而后随着车速的增加，车辆间等待时间变短，单辆车形成的簇数量减少，CM数量逐渐增多. 采用本研究所提分簇算法、经典最小编号分簇算法和自适应分簇算法，簇头数量都呈缓慢上升趋势，CM和UD车辆数量呈缓慢下降趋势. 说明随着 ${V_{{\text{MAX}}}}$变快，车辆之间相遇时间变短、车辆间距离拉长，同样范围内集群的数量有所增加. 3种算法都处于平缓变化中，并未随着速度的增加而出现剧烈波动，说明3种算法的分簇效果较为稳定. 其中，经典最小编号分簇算法稳定性能最好，其次是本研究所提算法.

总相似性分值 $ S_i^{{\text{tot}}} $的判断是本研究算法区别于其他算法的创新点之一，分别从权重因子取值分析、场景分析、算法对比三方面进行阐述.

对式(1)中权重因子的取值进行分析，观察权重因子 $q$取值对车辆各类分值 $ S_i^{{\rm{Score}}} $以及CH的选择情况的影响. 其中， $ S_i^{{\rm{Score}}} $包括移动相似性分值 $ {S_i} $、社交相似性分值 $ {I_i} $、总分值 $ S_i^{{\text{tot}}} $和活跃度值 $ S_i^{{\text{Act}}} $. 选定一个簇，满足 ${V_{{\text{MAX}}}}{\text{ = }} $ $ 60\;{\text{km}}/{\text{h}}$、 ${C_{i,n}} = 5$、 $ D_{\rm{v}}^{{\text{st}}} = 300\;{\text{m}} $的条件，簇内5辆车编号 $ {\rm{ID}}_i^{\rm{v}} $为V1~V5.

由于在本研究所提算法的簇头选举过程中社交相似性权重因子 $q$是可变的，须对其取值进行分析. 随着 $q$在0~1.0变化，每辆车的 $ S_i^{{\text{tot}}} $变化如图12所示. 可以看出，随着社交相似性权重因子的增加，相似度分值是逐渐降低的. 根据簇头筛选原则，分值最高者可以成为簇头候选者，则在此簇内根据 $ S_i^{{\text{tot}}} $最大值降序排名的车辆编号 $ {\rm{ID}}_i^{\rm{v}} $为V3、V4、V5、V2、V1.

图中车辆V3、V4相似度分值的曲线存在1个交点，说明随着 $q$取值的变化，簇头候选者发生了一次转换. 当 $ 0 \leqslant q < 0.16 $时，该簇内的簇头候选者是V3；当 $ q \geqslant 0.16 $时，簇头候选者由V3转换成V4，说明移动相似性和社交相似性无法兼得，须折中考虑. 若按照相同比重来选择簇头，车辆间的相似性分值会普遍降低，进而影响集群的稳定性，因此，在 ${V_{{\text{MAX}}}}{\text{ = }}60\;{\text{km}}/{\text{h}}$、 ${C_{i,n}} = 5$、 $D_{\rm{v}}^{{\text{st}}} = 300\;{\text{m}}$的条件下， $q \geqslant 0.2$为最优取值范围.

按照上述分析过程，对3种典型道路场景进行分析，并确定对应场景下的权重因子取值范围.

3种典型道路场景分别为：早、晚高峰堵车道路、正常城市道路、高速道路. 条件依旧为成簇数 ${C_{i,n}} = 5$. 最大通信距离与最大速度的差异如表3所示. 3.2.1节的分析恰好与第2种典型场景对应，按照相同分析方法，堵车道路场景、高速道路场景下不同车辆相似性分值随着 $q$取值的变化情况如图13所示.

如图13(a)所示，堵车道路下 $ S_i^{{\text{tot}}} $随 $q$增大而减小，这是由于堵车道路上车辆距离近、移动速度缓慢，车辆的移动相似性相较于车辆在其他场景下的数值要高. 图中， $q = 0.1$代表了堵车过程中会出现的极端的停车情况，相当于一条分界线，在其前后CHc发生了一次转变. 因此， $q$的取值范围为(0.1,1.0]. 如图13(b)所示为高速道路下 $ S_i^{{\text{tot}}} $随 $q$增大的变化情况. 由于高速道路场景下车辆间距较远、移动速度快，5辆车的初始移动相似性数值相较于其他场景下的低，此时要在优先满足移动相似性的前提下再考虑社交相似性. 图中V1和V4与其他车辆的变化趋势不同，是因为上述2辆车的社交相似性高，受影响的程度大. 因此，在高速道路场景下， $q$的取值范围如表3所示，为(0, 0.2].

针对常见的城市道路场景，基于上述场景的条件分别对4种算法选出的簇头参数进行对比.在对比前，首先对簇内5辆车的相似性分值 $ S_i^{{\text{tot}}} $、移动相似性分值 $ {S_i} $、社交相似性分值 $ {I_i} $以及活跃度值 $ S_i^{{\text{Act}}} $进行研究. 如图14所示为簇内车辆V1~V5的 $ S_i^{{\text{tot}}} $、 $ {S_i} $、 $ {I_i} $和 $ S_i^{{\text{Act}}} $. 可以看出， $ {S_i} $最高，V4的 $ S_i^{{\text{tot}}} $和 $ {I_i} $都最高，V5的 $ S_i^{{\text{Act}}} $最高. 即综合相似性分值 $ S_i^{{\text{tot}}} $最高的车辆不一定同时具有最高的 $ {S_i} $和 $ {I_i} $. 对4种不同算法选出的簇头进行数值对比，如表4所示. 可以看出，本研究所提算法选出的簇头ID（ID_CH）为V4，经典最小编号分簇算法选出的簇头ID为V1，自适应分簇算法和动态分簇算法选出的簇头ID为V3. 其相对应的 $ S_i^{{\text{tot}}} $、 $ {S_i} $、 $ {I_i} $和 $ S_i^{{\text{Act}}} $如表4所示.

可以看出，经典最小编号分簇算法由于仅考虑簇头编号最小的原则，选出的簇头V1的 $ S_i^{{\text{Act}}} $最低，同时 $ S_i^{{\text{tot}}} $、 $ {S_i} $和 $ {I_i} $也都是最低的；自适应分簇算法和动态分簇算法仅仅考虑了距离、相对速度、加速度等物理属性相似性，选出的簇头V3的 $ {S_i} $最高，但 $ {I_i} $和 $ S_i^{{\text{Act}}} $都不突出， $ S_i^{{\text{tot}}} $也并非最高. 而本研究所提分簇算法在考虑移动相似性的基础上，还考虑了车辆社交相似性以及活跃度的阈值判断，选出的簇头V4的 $ S_i^{{\text{tot}}} $和 $ {I_i} $最高， $ {S_i} $次高. 与其他分簇算法相比，采用本研究所提分簇算法，在保持了稳定性的同时，集群的亲密度相较于经典最小编号算法提升了5.8%，相较于动态分簇算法、自适应分簇算法提高了11.7%.

本研究提出了一种活跃度感知的社交车辆分簇算法. 利用基数排序算法对由移动相似性和社交相似性构成的车辆总相似性分值进行排名，得到簇头候选者. 利用车辆活跃度值对簇头候选者进行筛选. 仿真结果表明，相较于经典最小编号算法、动态分簇算法和自适应分簇算法，本研究所提分簇算法在保证集群稳定性的前提下，提升了簇内亲密度.

本研究中未考虑簇头车辆的负载均衡问题，在未来的研究中，将研究不同场景下考虑负载均衡的活跃度感知分簇算法，使得算法具有更广的应用价值.