异构网络下基于车辆权值的分簇算法

郭爱煌， 王 露， 黄 博， 左雨星

(1.同济大学 电子信息与工程学院，上海 201804；2. 轨道交通控制与安全国家重点实验室(北京交通大学)，北京 100044)

在汽车工业与通信技术蓬勃发展的今天，车联网逐渐成为时代发展的趋势.车联网提出的V2X(vehicle to X)主要包括车车通信(vehicle to vehicle, V2V)、车路通信(vehicle to infrastructure, V2I)、车人通信(vehicle to pedestrian, V2P)的短距离通信，以及车辆节点与其他网络之间的长距离通信.

在高业务密度的情景下，车辆节点信标产生碰撞，引起广播风暴.而在车辆节点稀疏的场景中，提供信息传输的车辆节点不足，导致信息丢失与车辆节点失联等问题.

在VANET网络中，为避免车辆节点周期性广播信息与突发性广播信息[1]造成信标拥塞，对车辆节点进行分簇管理，增强网络的可扩展性.目前，引入长期演进(long term evolution, LTE)基站辅助的异构网络分簇算法已成为研究热点.

分簇算法的主要工作在于簇头的选取，可简单抽象为簇头最大独立集的问题[2].文献[3]提出将车辆节点装备LTE与802.11p通信接口，为LTE(long term evolution)与车载自组织网络(LTE-vehicular Ad-Hoc network, LTE-VANET)异构网络下车辆节点分簇算法构建了基本框架.基站获取车辆节点的移动数据(floating car data，FCD)包括位置、速度大小、方向等参数，进行集中式分簇，大量增加了基站的分簇开销.文献[4]提出VMaSC-LTE算法，选择与相邻车辆节点间相对移动最小的车辆节点作为簇头，提高簇结构稳定性，但未考虑车辆节点与基站的通信效率.文献[5]中的Energy-Efficient Cluster分簇算法主要考虑簇头的传输功率，通过图论模型选择与邻居车辆节点总距离最小的车辆节点作为簇头，最小化信息传输的总功率.文献[6]提出一种自适应权值分簇协议，考虑车辆节点的编号、方向、速度大小及邻居车辆节点数目，采用遗传算法计算出最优分簇方案.但该方法的计算复杂度较高，迭代时间略长，不能很好满足实际应用需求.

传统的分簇方法针基于IEEE802.11p协议，主要考虑簇内车辆的稳定性而忽略了车辆节点与基站之间的信道状态与信道质量.在异构网络通信环境下，传统分簇算法无法确保车辆节点与基站之间的通信效率，造成LTE资源开销过大等问题.为优化簇稳定性，本文在文献[3]与文献[4]的基础上，改进车辆节点之间稳定性指标，更换成车辆节点相对移动性与相对置信距离作为新的分簇指标.另外，为提升簇头与基站间的信道质量，降低LTE基站消耗的通信开销，引入LTE接收参考信号质量及链路信道质量参数作为分簇属性，提出一种异构网络下基于车辆权值的分簇算法(heterogeneous network weighted clustering algorithm, H-WCA)，进行整体网络性能的优化.

1 系统模型及问题描述

1.1 系统模型

考虑车辆节点在双车道高速路面行驶环境下，对模型作出以下假设(如图1所示)：

(1)高速路面一侧部署了基站(evolved node B, eNodeB)，覆盖该段路面.

(2)车辆节点装有802.11p与LTE通信接口，车辆节点之间通过802.11p接口通信，车辆节点与eNodeB之间通过LTE接口进行通信.

(3)每辆车都装有通信单元(on board unit，OBU)用于V2V与V2I通信；传感器，如全球定位系统(global positioning system，GPS)，用于获取车辆节点的位置及速度信息；数据单元，如长度为L的缓存区，用于存储发送车辆节点的业务数据.

(4)车辆节点业务数据包的发送服从发送率为λt的泊松分布，每个时隙初期若缓存区队列非空，则立即发送数据包.

(5)车辆节点位置服从参数μ均匀分布.

图1 异构网络车辆节点分簇模型示意Fig.1 Heterogeneous network vehicle clustering model

1.2 权值分簇算法描述

由于分簇算法中存在多个属性影响分簇的性能，采用多属性权值分配的分簇算法，权衡制约各类属性.在VANET网络中，具有奠基意义的代表为Chatterjee等[7]提出的权值分簇算法(weighted clustering algorithm，WCA).WCA中分配不同属性权重，计算并选择最小权值车辆节点作为簇头.对车辆节点v的分簇权值Wv为

Wv=ω1Δv+ω2Rv+ω3Mv+ω4Pv

(1)

2 H-WCA算法描述

H-WCA算法引入置信距离、相对移动性、传输可达速率和信道质量指示作为分簇属性集，通过层次分析法确定各属性权值，利用序数偏好方法选取最优簇头.

2.1 置信距离描述

根据1.1节中描述的系统模型，以单向双车道行驶的车辆节点进行分簇，假设簇的传输范围为D，则簇内车辆节点数为

N=2μD

(2)

簇内车辆节点发送数据包服从发送率为λt的泊松分布，则簇头数据包亦服从到达率为λt的泊松分布，即

(3)

式中:λr=Nλt；Ar为簇头数据包到达个数；k为拟定达到数据包个数；ΔT表示簇内成员数据包发送间隔.

车辆节点网络模型可通过无向图G=(V,E)的节点与链路表示[7]，其中V为车辆节点集合，E为链路集合.车辆节点分簇问题可以抽象为限制条件下的图形分割问题，限定参数下的最小化分割图是一个NP-hard问题.车辆节点vi的邻居车辆(不包含vi)表示为

N(vi)={vj|d(vi,vj)

(4)

式中:d(vi,vj)表示车辆节点vi与车辆节点vj的距离;r802.11p表示802.11p定义的最大传输距离[5]，一般为300 m.

为提高传输稳定性，保证车辆节点传输的可靠性[8]，采用置信距离替代车辆节点相对距离.根据缓存区队列长度L，保证队列溢出概率小于阈值ρ.簇头数据包溢出的概率表示为

(5)

且P(Ar>L)<ρ结合式(2)与式(5)可得到车辆节点的置信区间(传输范围)D.根据车辆节点的最大传输距离r802.11p与置信区间D(如图2)，定义置信因子α>1，vi与vj的相对置信距离为

(6)

式中：Δd=d(vi,vj)-D.L(vi,vj)越小则表示vi与vj间的信任度越高.vi的相对置信距离为

(7)

图2 置信距离Fig.2 Distance in trust

2.2 相对移动性描述

车辆节点的移动造成网络拓扑结构变动，对簇稳定性产生影响.由于车辆节点并非匀速行驶，需对其运动状态进行预判.据此，采用高斯马尔科夫运动模型，预测车辆节点的运动状态[9].高斯马尔科夫运动速度模型可表示为

(8)

(9)

式中：δ为车辆位置更新间隔，通过预测vi位置，计算其相对移动性，即

(10)

2.3 可达速率描述

在LTE-VANET异构网络中，簇头收集簇内车辆节点的数据包，通过LTE上行链路发送至eNodeB[10].LTE采用2种参考信号(reference signal，RS)，分别为解调参考信号和探测参考信号，分别有对信号解调、确定服务信道的信道质量并进行信号调度等功能.

LTE系统结合当前的RSSI与RSRP的数值，计算信号强度与干扰比，引入参考信号接收质量(reference signal received quality, RSRQ). RSRQ能更贴切信道的链路状态，用于多小区通信场景下，作为移动用户的越区切换参数之一.假设有Y个LTE传输资源块，其计算公式为

RQ(vi)=YRP(vi)/Rs

(11)

式中：RQ(vi)表示车辆节点vi接收的RSRQ；RP(vi)表示车辆节点vi在其所处小区位置的RSRP强度；Rs表示该小区的RSSI.eNodeB根据用户接收的参考信号对传输链路进行信道估计.车辆节点的传输可达速率[12]为

S(vi)(1-τ-ζ

(12)

式中:τ为信道检测时间;ζ为能量传输时间.

由车辆节点vi的RQ(vi)计算获得从eNodeB到车辆节点传输可达速率S(vi)，作为分簇的属性之一，保证簇头与eNodeB间的信道传输容量.

2.4 信道质量指示描述

针对无线信道的时变特性，LTE系统建立闭环反馈的通信模式，通过自适应调整链路技术，实现传输最优配置.eNodeB依据车辆节点的反馈信息，分析当前信道参数及干扰模型，并自适应地调节上下行链路的传输参数.

信道质量指示(channel quality indicator，CQI)的量化等级为0～15，对应不同的传输编码策略，eNodeB通过车辆节点反馈的CQI自适应调整下行链路的调制方式和编码策略[13](如表1)，在传输块错误率不超过10%的前提下，提高资源使用率[14].

簇头传输信息量大，优先选择CQI较高的车辆节点，以降低LTE通信链路的资源块占用率.令车辆节点的平均CQI为C(vi).

表1 CQI与编码策略Tab.1 CQI and coding strategy

2.5 权值分配及簇头选择

2.5.1层次分析法

异构网络下车辆节点多属性权重分簇算法简单抽象为多属性、多目标的决策问题.建立层次分析法(analytic hierarchy process, AHP)模型[15]，按照实际模型得到目标层(簇稳定性、传输有效性、信道容量、资源利用率)、决策层(置信距离、相对移动性、可达速率、信道质量)和方案层(簇内车辆节点集).

通过比例标度表对各属性相对重要性赋值，构造归一化比较判断矩阵.计算出矩阵的最大特征值，进行一致性校验.若满足校验条件[15]，则各属性的权值分别为对应的判断矩阵的归一化的特征向量中各元素的值.

AHP将各参考元素分别在目标、准则、方案等层次上划分，为多目标、多属性的分簇问题提供简便的决策方案.

2.5.2序数偏好方法

序数偏好方法(technique for order preference by similarity to an ideal solution, TOPSIS)基于决策方案与理想方案的欧氏距离最小、与负理想方案距离最大理论[16].假设车辆节点的置信距离、相对移动性、传输可达速率及链路信道质量指示对应分配的权值分别为ω=[ω1，ω2，ω3，ω4].决策矩阵R的各元素计算为

(13)

式中：M为簇内车辆节点集合；xiq表示车辆节点vi的属性q的数值结果.决策矩阵R的每列与权值ωq相乘，建立加权标准化决策矩阵Z，即

(14)

通过矩阵Z确立理想解A+与负理想解A-，如

(15)

(16)

对于车辆节点vi与理想方案、负理想方案的欧氏距离分别为

(17)

(18)

则其与理想方案的接近程度为

(19)

最后选择最小Gi节点作为簇头.

在多属性决策问题上，AHP更为简便客观地计算各属性权值.在多目标的决策问题上，TOPSIS方法可有效地获取评测对象集合中的最优解.结合AHP和TOPSIS，选取路面环境中相对稳定且信道状态较理想的车辆节点作为簇头，稳定簇的生存周期以及提高LTE基站的传输效率及传输容量.

例如网络的车辆节点集为{m1,m2,m3}，假设根据式(13)计算得出车辆节点的决策矩阵为

由式(14)可计算获得对应的加权决策矩阵为

其理想方案为A+={0.022,0.044,0.076,0.384}，负理想方案为A-={0.088,0.176,0.046,0.258}.据式(17)、(18)、(19)可得，各簇内各车辆与理想方案的接近距离分别为{0.737,0.104,0.462}，因此选择车辆m2作为簇头.

3 H-WCA分簇算法实现

H-WCA算法考虑单跳连接方式，具体执行步骤如下.

当车辆节点进入小区内，当前车辆状态(car state)为独立簇头(stand head)，并向eNodeB申请簇ID(cluster ID)，并查询是否存在簇头(cluster head, CH).若其本身ID(my ID)与CH ID相同，则其车辆状态置为CH，否则置为簇成员(cluster member，CM)，执行过程如步骤1，即车辆节点状态选择.

1 For all the vehicle request CLUSTER ID;

2 if Car State == STAND HEAD

3 request and set Cluster ID;

4 end if;

6 if hasCH == true

7 if CH ID == my ID

8 Car State = CH;

9 else

10 Car State = CM;

11 end if;

12 end if;

13 end if;

若当前簇内无CH存在，则车辆节点相互间广播信标(broadcast beacon)，并计算各自的相对置信距离与移动参数，计算完成后向eNodeB发送申请CH请求，执行过程如步骤2，即车辆节点簇头申请.

1 For all Car State == STAND HEAD;

2 if hasCH == false

3 broadcast Beacon;

4 request CH;

5 wait and receive LTE message;

6 if CH ID == myID

7 Car State = CH;

8 broadcast CH message;

9 else

10 Car State = CM;

11 hasCH = true;

12 end if;

13 end if;

对于eNodeB接收到簇ID申请消息，返回簇ID及簇头ID.若eNodeB接收到簇头申请消息，则计算簇内车辆节点接近程度并选出CH，执行过程如步骤3，即eNodeB CH选择.

1 For eNodeB;

3 return Cluster ID;

4 if hasCH == true

5 return CH ID;

6 end if;

7 end if;

9 if hasCH == true

10 return CH ID;

11 else

12 calculate G;

13 if G(k) == min{ G }

14 CH ID = k;

15 end if;

16 hasCH = true;

17 return CH ID;

18 end if;

19 end if;

4 仿真及结果分析

采用Veins LTE仿真框架进行车辆分簇系统级仿真试验与数据分析.仿真参数符号及数值如表2所示.

车辆密度取值20～75辆·km-1，仿真比较分析H-WCA、传统WCA及最小ID分簇算法在LTE上行链路传输容量、上下行链路资源占用率及簇范围的区别.经计算，各属性权重为ω=[0.1,0.2,0.1,0.6].图3为不同分簇算法的上行链路传输总量与车辆节点密度曲线.经异构权值分簇算法选取的簇头节点与eNodeB之间的信道状态相对理想，信

表2 仿真参数Tab.2 Simulation parameters

道可传输容量也相对较大，在车辆密集的路面中，H-WCA算法可提供更大的传输容量上限.如图所示，当车辆节点密度增大，H-WCA算法在上行链路传输容量上性能提升明显，最高可增加34%左右.

图3 上行链路传输总量对比Fig.3 Total uplink transmission comparison

经典WCA算法以车辆节点距离、相对速度及电力资源作为分簇的参考属性，从而使得簇的稳定性最优.在异构网络通信环境中，需进一步考虑LTE的资源利用率.在H-WCA算法中，根据LTE的调制编码策略，引入了RSRQ与CQI作为分簇属性，通过选择联合属性权值最优的车辆节点，降低车辆通信的LTE资源块开销，最高可降低约22%的资源占用率.

3种算法在上下行链路的资源占用率方面的仿真比较如图4、图5所示.LTE基站根据上行链路反馈的CQI自适应调整下行链路的调制编码策略，在保证误块率的情况下改善资源传输效率.H-WCA选取相对较高CQI车辆节点作为簇头，提升了LTE链路的编码效率，减少资源块占用率.如图4、图5所示，H-WCA算法资源占用率相较于另外2种分簇算法有较大的降低，当车辆节点密度增加，其性能优势愈加明显.

为保证分簇的稳定性，尽可能增大分簇范围、减小簇头数量.H-WCA通过簇内车辆的置信距离与相对移动性预测车辆节点之间的运动状态，最大化簇头通信范围内的车辆节点数.由图6可得，H-WCA算法通过更新车辆相对置信距离与相对移动性的分簇属性，提升了分簇的稳定性，平均簇内车辆数目与WCA算法表现相近，但明显优于最小ID分簇算法.

图4 上行链路资源块占用率对比

Fig.4Uplinkresourceblockoccupancyratecomparison

图5 下行链路资源块占用率对比Fig.5 Downlink resource block occupancyrate comparison

图6 簇内成员平均数量对比Fig.6 Average number of members withinthe cluster contrast

文献[3]中主要通过LTE基站辅助降低了FCD丢包率，并且通过增加LTE链路的开销以降低VANET的通信开销.而本文的分簇算法，采用车辆节点自组织分簇，有效地降低了LTE的分簇开销，通过对簇头节点信号强度以及信道质量的评估，进一步降低了LTE链路的通信负载.文献[4]采用多簇的融合机制以及信号多跳的方式实现簇的稳定性最大化.但是若簇成员过多，会导致簇头的负载严重，因此仍采用节点间单跳的通信方式减小簇头的信息传输压力.文献[5]通过选取网络中相对最小距离节点作为簇头以降低簇头的能量开销.而H-WCA算法，在维持相同误码率的情况下，可通过减小簇头的发射功率降低簇头的能量消耗.综上所述，H-WCA在异构网络通信环境中性能表现更优.

5 结语

提出了一种异构网络下基于车辆权值的分簇算法.通过LTE基站辅助车辆节点分簇，引入车辆节点的置信距离、相对移动性、链路可达速率及上行链路CQI作为分簇参考属性，在保证分簇稳定的前提下，提高LTE传输容量，同时降低LTE资源块占用率.仿真结果所示，H-WCA在LTE传输速率及传输效率方面均有明显的提升.此外，通过仿真发现车辆节点的密度增加造成LTE资源占用率上升，因此下一步工作可以继续研究资源占用率的影响因素.

参考文献:

[1] ARANITI G, CAMPOLO C, CONDOLUCI M,etal. LTE for vehicular networking: A survey[J]. IEEE Communications Magazine, 2013, 51(5): 148.

[2] 林磊，肖晓强，徐明，等. 面向稳定性的基于权值的车辆自组网分簇算法——SWBCA[J]. 计算机应用, 2010, 30(7): 1711.

LIN Lei, XIAO Xiaoqiang, XU Ming,etal. SWBCA: Stability-oriented weight-based clustering algorithm for VANETs[J]. Journal of Computer Applications, 2010, 30(7): 1711.

[3] REMY G, SENOUCI S M, JAN F,etal. LTE4V2X: LTE for a centralized VANET organization[C]//Global Telecommunications Conference (GLOBECOM 2011). Houston: IEEE, 2011: 1-6.

[4] UCAR S, ERGEN S C, OZKASAP O. Multihop-cluster-based IEEE 802.11p and LTE hybrid architecture for VANET safety message dissemination[J]. IEEE Transactions on Vehicular Technology, 2016, 65(4): 2621.

[5] DONG Ping, DU Xiaojiang, SUN Jianan,etal. Energy-efficient cluster management in heterogeneous vehicular networks[C]//2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). Chengdu: IEEE, 2016: 644-649.

[6] HADDED M, ZAGROUBA R, LAOUITI A,etal. A multi-objective genetic algorithm-based adaptive weighted clustering protocol in vanet[C]// 2015 IEEE Congress on Evolutionary Computation (CEC). Sendai: IEEE, 2015: 994-1002.

[7] CHATTERJEE M, DAS S K, TURGUT D. WCA: A weighted clustering algorithm for mobile Ad Hoc networks[J]. Cluster Computing, 2002, 5(2): 193.

[8] AISSA M, BELGHITH A. An efficient scalable weighted clustering algorithm for mobile Ad Hoc networks[C]// 2013 3rd International Conference on Information Technology and e-Services (ICITeS). Jeju: IEEE, 2013: 1-6.

[9] CAI M, RUI L, LIU D,etal. Group mobility based clustering algorithm for mobile ad hoc networks[C]//2015 17th Asia-Pacific Network Operations and Management Symposium (APNOMS). Seoul: IEEE, 2015: 340-343.

[10] EL Mouna Zhioua G, TABBANE N, LABIOD H,etal. A fuzzy multi-metric QoS-balancing gateway selection algorithm in a clustered VANET to LTE advanced hybrid cellular network[J]. IEEE Transactions on Vehicular Technology, 2015, 64(2): 804.

[11] 栾林林. 支持高速切换的 TD-LTE 信令的设计及其优化的研究[D]. 北京: 北京邮电大学, 2013.

LUAN Linlin. Research on designing and optimization of signalling of TD-LTE based on high-speed handover[D].Beijing: Beijing University of Posts and Telecommunications, 2013.

[12] YANG G, HO C K, ZHANG R,etal. Throughput optimization for massive MIMO systems powered by wireless energy transfer[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(8): 1640.

[13] 3rd Generation Partnership Project. Evolved Universal Terrestrial Radio Access-3GPP. TS 36 213 V8. 8.0[S]. Valbonne: 3rd Generation Partnership Project, 2009.

[14] TURCANU I, SOMMER C, BAIOCCHI A,etal. Pick the right guy: CQI-based LTE forwarder selection in VANETs[C]//Vehicular Networking Conference (VNC), 2016 IEEE. Columbus: IEEE, 2016: 1-8.

[15] YARAGHI N, TABESH P, GUAN P,etal. Comparison of AHP and monte carlo AHP under different levels of uncertainty[J]. IEEE Transactions on Engineering Management, 2015, 62(1): 122.

[16] TIAN G, ZHANG H, ZHOU M C,etal. AHP, gray correlation, and topsis combined approach to green performance evaluation of design alternatives[J]. IEEE Transactions on Systems, Man and Cybernetics: Systems, 2017(99):1.