3.4　联合车辆分簇与功率控制方法

本节针对车联网系统中网络拓扑快速变化导致车辆通信不稳定的现象，提出基于簇稳定的车辆分簇方法。该方法充分利用了城市公交的优势，有效增加了簇结构的稳定性。在城市路网中，提出交叉口处车辆拥堵的分簇方法，并结合功率控制方法，在能耗较低的前提下可以缓解城市道路的交通拥堵问题。

3.4.1　运动态车辆分簇方法

1. 运动态车辆分簇模型

如图3-12所示，假设每辆车都装有卫星定位装置，能实时地确定自己的位置、速度和方向信息。驾驶人都采用导航地图，车辆能够获知自己的行驶路线与目的地。车辆可通过与周围车辆交换信息，计算出与邻近车辆的距离。当前路段共N辆车，分别用ui表示，i=1,…,N，这N辆车共可以分为M≤N个簇，用Sk表示，k=1,…,M，簇内车辆用uk,j表示，j=1,…,wk，wk为簇中车辆个数。

定义车辆信息Vinf，包含车辆此刻的速度v、车辆此刻的位置、当前道路预计行驶距离s、与附近簇头的距离d。定义车辆入簇因子ηk,i为

式中，为第i辆车的速度；为第k个簇的平均速度；S为车辆的广播范围，、和均为加权系数。车辆的入簇因子越小，则其加入该簇的概率越大，这是因为与的差值越小，越大，越小，车辆与簇内车辆成员具有更高的行为一致性。

城市中公交车数量远少于普通车辆，且公交车统一管理，能源充足，可以安装更强大的无线收发装置，鉴于以上特点，可优先考虑选取公交车作为簇头[25]。定义簇头因子为

式中，ni为簇内车辆的邻居车辆个数；Bi为公交参数，当该车辆为公交车时，Bi为0，否则Bi为1；ei、fi分别为第Sk辆车的簇头因子的加权系数。簇头因子k(k∈1,…,M)越小，该车辆的一跳通信范围覆盖的车辆越多，车辆行驶距离越长，车辆成为簇头的概率越大。

2. 运动态车辆分簇算法

对道路上的车辆进行分簇包含两个过程，分别为簇生成过程与簇维护过程。其中，簇生成过程是指新建一个簇的过程，包括簇头的选取、簇成员的确定等；簇维护过程是指簇成员数据的更新，包括簇内成员维护和新加入车辆入簇。

在网络初始阶段，道路上的车辆均为孤立节点，这些孤立车辆通过导航卫星等获得自身车辆信息，包括位置、速度、方向等，并向自身通信范围内的所有车辆广播含自身车辆信息的广播包。首先进行簇的初始化，根据位置相近原则将一定范围内的N辆车随机分成M个簇，分别为Sk，k∈1,…,M，簇内车辆个数为wk；然后进行簇头选取，初始化后的簇中，若无公交车，则选择簇头因子最小的车辆作为簇头；若初始化后的车辆簇中只有一辆公交车，则选择该公交车作为簇头；若初始化后的簇中不止一辆公交车，则选择簇头因子最小的公交车作为簇头。具体的算法流程如下。

簇生成算法的流程如图3-13所示。

3. 簇维护方法

簇维护方法包含对已在簇内车辆的处理和簇外想要入簇车辆的处理。

当车辆簇形成后，计算各簇的簇平均速度，并与簇成员车辆速度相比较，如果簇内车辆的速度与簇平均速度相差过大，就将该车辆从簇内剔除。具体的算法流程如下。

簇内车辆维护的流程如图3-14所示。

簇头车辆周期性广播自身簇头信息，其周围未加入任何簇的车辆主动上报自身车辆信息Vinf，并计算其入簇因子。若计算结果满足此簇的入簇门限ηth，则允许车辆加入此簇；否则自身成为一簇。具体的算法流程如下。

车辆入簇的流程如图3-15所示。

上述基于簇稳定的车辆分簇方法用以提高协作车辆通信可靠性。该方法优先采用公交车作为簇头，在一定范围内，若无公交车，则选择簇头因子最小的车辆作为簇头；这很好地考虑了车辆行驶过程中的关键因素d、v和s。因为簇内成员的相对速度较小，所以延长了车辆的持续通信时间，提供了相对可靠的连接，使簇的结构相对稳定，同时具有较小的复杂度。

3.4.2　准静态车辆分簇方法

1. 准静态车辆分簇模型

在城市路网中，基于交叉口处车辆拥堵的分簇场景如图3-16所示。城市道路交叉口作为交通流量集中和分散的重要节点，其在道路网络中的复杂位置很容易造成交通拥堵和交通事故。统计数据显示，在交叉口处的车辆拥堵占城市道路交通总延误的30%以上，交叉口处所发生的交通事故占总交通事故的50%以上[26]。因此，疏导交叉口处的车辆拥堵，对于提高交通效率和保障行车安全都具有十分重要的意义。

该场景由4条直路、十字路口、交通信号灯及众多车辆等元素组成。其中，黑色箭头所指的方向为车辆的运行方向；虚线椭圆所圈出的车辆处于同一个车辆集群；五角星所标记的车辆为簇头车辆（Cluster-Head Vehicles，CHV）。CHV作为每个车辆簇中最重要的“通信联络员”，承担了簇内广播和簇间通信的中继功能。例如，前方道路发生了交通事故、有障碍物或存在拥堵时，靠近事故发生区的簇头车辆可以将消息传送给其他未到达此路段的簇头车辆，然后簇头车辆将预警信息广播给簇内成员车辆，从而极大地提高了人们的出行效率和道路安全性。

2. 准静态车辆分簇算法

假设在道路交叉口附近有n辆车，每辆车用符号Mi代表，i=1,2,…,n(n＞k)，k为车辆集群的数目。车辆Mi与车辆Mn之间的距离dMi,n定义为[27]

式中，x和y分别为车辆的水平和竖直坐标。下面基于最大最小距离标准[28]来为k-means算法进行初始化，选出k个初始聚类中心，即说明道路上的车辆被划分为k个车辆集群。

随机选择某车辆作为第一个初始聚类中心，然后选择距离该车辆最远的车辆作为第二个初始聚类中心，两车之间的距离记为。计算道路上剩余的n-2辆车到初始聚类中心、的距离，并记为、。在和中分别找出各自的最小值和，比较两者大小并将其中的最大值所对应的车辆作为第三个聚类中心。根据此规则类推，分别计算道路上剩余的其他车辆到现有初始聚类中心的距离，记为（此时，）。找出各自的最小值，并进行大小比较，其中的最大值所对应的车辆则记为下一个初始聚类中心。定义最大值的通用公式为[29]

直到Dmax不满足式（3-88）时，停止生成新的初始聚类中心。

式中，DC为初始分簇的临界值；δ为分簇的权重参数，与车辆密度有关。

城市道路上，通过某一点的车辆数服从泊松分布[30]，由此，车辆Mi出现在车辆M1与车辆M2之间的概率为

式中，为路段当前的车辆密度。其泊松分布的期望值为

而车辆密度ρ又与车速vi（m/s）及车辆的到达率εi（m/s）有关，常表示为[31]

那么，车辆密度ρ与之间的关系记为

式中，θ为一个浮动误差参数。根据式（3-89）、式（3-91）、式（3-92）和式（3-93）可以得到

由于交通拥堵，车速和车辆的到达率几乎很小且相对恒定，因此从式（3-94）中可以看出，车辆分簇的权重参数δ与车辆数i成反比，即

接下来，如果按照传统的k-means算法[32]，其他成员车辆就会被直接划分给其距离最近的初始簇头车辆所在的集群，并不断调整聚类误差以选出最终的簇头车辆。在这种情况下，迭代过程会不可避免地引起一定程度的车间通信延迟。为了降低由复杂的迭代计算所带来的延迟，我们提出了一种优化的k-means算法，用于在时变环境中车辆拥堵场景的分簇。由于道路上的车辆密度直接反映了交通拥堵程度，所以把有关车辆密度的参数引入到挑选簇头车辆的衡量标准当中，既提高了算法的分簇效率，又符合实际场景的应用需求。下面，以上述由最大最小距离标准所选出的k个初始聚类中心为基础，对优化算法的迭代规则进行介绍。

类似于减法聚类[33]中的数据对象密度，将一个车辆簇中的车辆密度定义为

式中，w为集群中的车辆数目；为第i个集群中的成员车辆；为该集群此时尚未更新的聚类中心。根据式（3-92）、式（3-94）和式（3-95），可以得到车辆密度的校正比ψ，即

将ψ引入到聚类中心的更新标准中，有

式中，Cj为更新后的聚类中心，j=1,2,…,k。直到聚类误差平方和J不再变化，便可得到最终的k个聚类中心。

然而，新的k个聚类中心的坐标通常不是某一车辆所在的确切位置。所以，我们将最接近聚类中心的车辆视为CHV，则

综上，将分簇算法的整个流程描述如下。

步骤1：随机选取道路上某一车辆M1作为第一个初始聚类中心C1，并选择距离M2最远的车辆C2作为第二个聚类中心M1。

步骤2：计算道路上其他车辆到现有初始聚类中心的距离，找到它们各自的最小值，其中，

步骤3：从这些最小值中选出最大值Dmax。

步骤4：如果Dmax＞δ·‖C1-C2‖，则执行步骤5。

步骤5：最大值Dmax所对应的车辆M1则最作为下一个初始聚类中心Ck'。

步骤6：k'=k'+1，返回步骤2。

步骤7：否则，k=k'，k个初始聚类中心选择完成。

步骤8：道路上其他成员车辆被分配给距离其最近的初始聚类中心所在的车辆集群。

步骤9：每个车辆集群更新其聚类中心

步骤10：计算聚类误差平方和，

步骤11：重复步骤8～10，直到J不再变化。

步骤12：选择距离每个新聚类中心最近的车辆作为CHV，则

3.4.3　准静态车辆分簇下的功率控制

簇头车辆（CHV）承担了簇内广播和簇间通信的中继功能，负责集群内的传输调度和信道分配，并支持不同集群成员之间及不同车辆集群之间的通信。下面主要针对簇头车辆的通信性能展开研究。基于三端网络的双向车载中继协作通信模型，分为两个时隙完成CHV之间的信息传输，如图3-17所示。其中，CHV-A、CHV-B和CHV-C分别被视为源/目的节点S1、中继节点R及源/目的节点S2。

本小节提出一种基于中断概率约束的最小化CHV总传输功率的功率控制方案，从IHDAF、DF、AF这3种协作方式展开分析[34]。为了不失一般性，假设源节点CHV具有相同的发射功率，即PS1=PS2=PS。功率控制方案由下式给出

式中，Pt为CHV的总传输功率；ξ为系统中断概率pout的约束值。

对于IHDAF协作方式转发策略而言[34]，在β=1时，。基于拉格朗日函数可以得到

其中，λ≥0是拉格朗日参数。根据式（3-101）分别对、及λ求偏导，有

其中，，这里、和分别为信道衰落系数、和的方差，为噪声方差，对应的方差由式（3-102）计算可得，源节点和中继节点的最小发射功率分别为

在β=0时，，构造拉格朗日函数可得

其中，μ≥0为拉格朗日参数。根据式（3-105）分别对、及μ求偏导，有

其中，。由式（3-106）计算可得，源节点和中继节点的最小发射功率分别为

综上，在中断概率ξ的约束下，使用IHDAF协作方式转发策略的源节点和中继节点的最小传输功率分别为

同理，在中断概率ξ的约束下，基于AF协作方式转发策略的中断概率表达[34]可以构造拉格朗日函数，则源节点和中继节点的最小传输功率分别为

其中，

3.4.4　仿真结果与性能分析

在本小节中，提供了数值模拟结果来评估分簇算法和功率控制方法的性能。对于交通拥堵的情景，具有AWGN的瑞利衰落信道作为基础传输信道模型，车辆的速度vi和车辆到达率εi相对恒定，其他仿真参数如表3-2所示。

如图3-18和图3-19所示，车辆分簇算法的仿真结果在两种场景下实现：一种是基于交叉口的车辆分簇场景，每条主要道路的长度为285m，十字路口的范围为30m×30m，权重参数δ为0.275，所对应的车辆数为810辆；另一种是基于长度600m直路的车辆分簇场景，权重参数δ为0.320，所对应的车辆数为600辆。为了简化场景模型，采用散点来表示成员车辆，采用黑色的×来表示CHV（见图3-18）。其中，灰度深浅不同的点集代表不同的车辆集群，灰度深浅相同的散点属于同一车辆集群。

在图3-18中，800辆车随机分布在4条直路上，其余10辆车随机分布在十字路口。根据所提出的分簇算法，810辆车被自动划分为9个群集，并选出了对应的9个CHV。图3-18中，椭圆所圈出的3个CHV，它们基于三端网络的协作通信完成了3个集群之间的信息共享。因此，在低路由开销的前提下，簇头车辆可以实现整个交叉口道路的信息互联，协作车载通信系统的连通概率得到显著改善，且拥堵问题得到有效的缓解。

由于权重参数δ的取值不同，在图3-19中，600辆车同样被自动划分为9个车辆集群。从图3-19中可以看出，9个CHV均处于车辆密度较高且接近集群中心的位置，群集中的所有成员车辆都可以从自己所对应的CHV处接收到广播消息，大大降低了网络拓扑结构的复杂性。综上，数值模拟结果与理论分析之间存在一致性。

图3-20所示为不同瞬时信噪比下3种协作方式转发策略的中断概率的变化情况。这里，归一化之间的距离并设置如下参数：。信道环境被建模为具有方差d-α的复高斯分布，其中α为路径损耗因子，d为任意两个CHV之间的距离。从图3-20中可以看出，随着瞬时SNR从6dB增长到18dB，所采用的IHDAF协作方式转发策略一直优于其他两种传统的AF或DF协作方式转发策略。然而，当瞬时SNR接近6dB时，基于IHDAF和DF协作方式转发策略的系统中断概率也逐渐靠近。这是因为IHDAF协作方式转发策略正在使用DF协作方式在给定的SNR区域内传送信息。

图3-21所示为不同信息传输速率下3种协作方式转发策略的中断概率的变化情况。其中的参数取值为：，且每个传输链路的SNR设置为12dB。显然，随着信息传输速率的增加，3种协作方式转发策略的中断概率均在逐渐变大。从图3-21中还可以观察到，传输速率从0bit/s/Hz增加到1bit/s/Hz的过程中，IHDAF协作方式转发策略的中断概率始终低于0.011。因此，根据式（3-107）和式（3-108）得出，CHV的总功率可以降低到12dBm。

图3-22所示为不同的中继位置对系统中断概率所产生的影响。这里，归一化之间的距离且有如下参数设定：，每个传输链路的SNR为12dB。从图3-22中可以看出，基于IHDAF和AF协作方式转发策略的系统最小中断概率在处获得，而基于DF协作方式转发策略的系统最小中断概率在处获得。这对于车载协作通信系统选择具有最佳协作位置的“中继车辆”很有帮助。此外，无论中继车辆的位置如何变化，基于IHDAF协作方式转发策略的中断概率始终小于AF协作方式或DF协作方式转发策略，这充分证明了所采用的协作转发策略的优越性。