異構網絡下基于車輛權值的分簇算法

郭愛煌， 王 露， 黃 博， 左雨星

(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.