車聯(lián)網(wǎng)中基于K均值聚類的擁塞控制方法

李國欽，孫友偉，柴永平

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

0 引 言

在車聯(lián)網(wǎng)運行中，車輛節(jié)點動態(tài)變化，路邊設(shè)施(RSU)固定不動。在十字路口由于道路的時分復(fù)用，道路擁堵導(dǎo)致暫停車輛產(chǎn)生大量數(shù)據(jù)，迫使網(wǎng)絡(luò)擁塞性能退化[1-4]。

近年來，業(yè)界有利用車輛發(fā)送信息的發(fā)射功率，公平性和優(yōu)先性提出了靜態(tài)D-FPAV方法和動態(tài)D-FPAV方法進行車聯(lián)網(wǎng)擁塞控制方法，有基于車輛發(fā)送信息的發(fā)射速率的算法提高網(wǎng)絡(luò)可靠性等方法，以及通過線性增加相鄰車輛的數(shù)量來獲得最小的爭用窗口等算法。但上述算法均沒有考慮信息的傳輸范圍和網(wǎng)絡(luò)沖突概率[5-8]。

針對上述問題，提出基于K-means聚類的車聯(lián)網(wǎng)擁塞控制方法，在802.11p模型中引入擁塞控制模塊同步處理高并發(fā)數(shù)據(jù)，通過K-means聚類算法對幀進行分類完成最優(yōu)解決方案的計算。

1 車聯(lián)網(wǎng)擁塞模型

1.1 車聯(lián)網(wǎng)仿真系統(tǒng)架構(gòu)

本文仿真實驗中，MAC層和物理層的每個功能均以獨立實現(xiàn)。由于每個車輛信息只是提取聚類算法所需的特征，所以利用多線程方法進行高并發(fā)模式下的特征提取，滿足高密度車輛下的同步計算，改善了標(biāo)準模型中因計算時延導(dǎo)致的通信擁塞情況，車輛模型架構(gòu)如圖1所示。信息在模型中的處理過程如下：

步驟1 物理層將接受到的信息經(jīng)過地址過濾提供給MAC層接收模塊；

步驟2 在MAC層查看幀間距，將幀間距不符的信息丟棄，完成分組交換到接收控制模塊；

步驟3 接收控制模塊將CTS和ACK幀發(fā)送到傳輸模塊來響應(yīng)接受到的RTS和DATA幀，并將CTS和ACK幀發(fā)送給傳輸控制模塊；

步驟4 信道狀態(tài)管理模塊保持對信道的監(jiān)聽，接收幀的持續(xù)時間域和物理層信道狀態(tài)，若監(jiān)聽到擁塞則觸發(fā)擁塞控制模塊的高并發(fā)數(shù)據(jù)處理模式；

步驟5 傳輸模塊利用接收到的通信參數(shù)控制數(shù)據(jù)傳輸。

圖1 車聯(lián)網(wǎng)仿真系統(tǒng)架構(gòu)

1.2 建立物理層模型

車聯(lián)網(wǎng)節(jié)點r在每一時刻的累積噪聲為

(1)

其中，F(xiàn)r(t) 是所有在時間節(jié)點r相互干擾幀的集合。

節(jié)點接收幀時所處的SINR為

(2)

車聯(lián)網(wǎng)廣播傳輸滿足Nakagami分布(m=3)，則單跳廣播分組的接收功率

(3)

其中，x表示發(fā)送者與接收者之間的距離，φ為距離表示的傳輸功率，單位為m。

在考慮通信密度的情況下，最終構(gòu)造物理層經(jīng)驗?zāi)Ｐ腿缦?/p>

(4)

基于場景配置的擬合參數(shù)法則

(5)

其中，ε=φ·f·σ,i+k≤4。

根據(jù)上述兩點，搭建十字路口下的車聯(lián)網(wǎng)擁塞模型如圖2所示。

圖2 車聯(lián)網(wǎng)擁塞模型

2 擁塞控制方法

本文提出的KCC策略包括擁塞檢測，K-means均值分類和擁塞控制單元。在檢測到信道發(fā)生擁塞后，利用K均值聚類算法對車輛節(jié)點進行分類，最后由擁塞控制單元將最優(yōu)解決方案分發(fā)給各類節(jié)點。

2.1 擁塞檢測

本文采用監(jiān)控信道利用率來判斷是否發(fā)生擁塞，當(dāng)檢測到的結(jié)果大于預(yù)先設(shè)定好的閾值時則認為信道發(fā)生擁塞，開始收集擁塞數(shù)據(jù)，本文中信道擁塞閾值為0.7[9]。

2.2 K-means聚類算法

在802.11p協(xié)議中的數(shù)據(jù)轉(zhuǎn)發(fā)機制為通信范圍內(nèi)的節(jié)點信息先進行分簇，形成穩(wěn)定的簇拓撲，再由簇頭轉(zhuǎn)發(fā)各簇中的節(jié)點信息。本文在網(wǎng)絡(luò)層數(shù)據(jù)轉(zhuǎn)發(fā)的過程中根據(jù)V2V的相對距離進行分簇，因此在MAC層使用K-means聚類算法進行幀分類,節(jié)省了計算車輛間的相對距離,提高了平均時延性能。

K-means聚類算法為了將車輛節(jié)點信息按照不同特征進行分類，劃分為K個N={nk,i=1,2,…,k} 類，每個類nk的聚類中心ck通過N次循環(huán)迭代，使每一個節(jié)點xi到ck的相對距離歐氏距離和J(N)最小。K-means聚類算法分類過程如圖3所示

(6)

(7)

圖3 K-means聚類算法流程

2.2.1 數(shù)據(jù)采集

在檢測到網(wǎng)絡(luò)發(fā)生擁塞后，可以采用兩種方法進行擁塞數(shù)據(jù)的收集，第一種是在檢測到擁塞后100 μs內(nèi)RSU收集到的所有車輛節(jié)點信息，第二種是紅燈亮了以后RSU收集到的以及緩沖池中的所有數(shù)據(jù)，兩種情況都會產(chǎn)生圖2所示擁塞區(qū)域。將幀校驗序列錯誤的信息過濾后進行聚類，在同一網(wǎng)絡(luò)分別進行仿真，丟包率性能如圖4所示，平均時延性能如圖5所示。

圖4 不同狀態(tài)的丟包率

圖5 不同狀態(tài)的平均時延

根據(jù)上述仿真結(jié)果表明，紅燈亮后的丟包率及平均時延較好，主要原因在于紅燈亮后車輛處于有序的靜止?fàn)顟B(tài)，數(shù)據(jù)轉(zhuǎn)發(fā)時簇頭穩(wěn)定，所以本文采用紅燈亮后采集到的車輛節(jié)點信息作為擁塞模型的數(shù)據(jù)。

2.2.2 特征選擇

本文選擇的特征為信息大小、信息種類、車輛和RSU之間的距離、信息有效性和發(fā)送端行駛方向。在車聯(lián)網(wǎng)中，安全信息大小為300 bytes，信標(biāo)信息大小為400 bytes，服務(wù)信息的大小可能為1000 bytes,1024 bytes,1400 bytes這3種情況[10]。信息有效性指在自組織網(wǎng)絡(luò)中信息允許的最大跳數(shù)。車聯(lián)網(wǎng)中發(fā)送的位置信息來自于GPS定位，精度為厘米級。本文進行仿真時，分別使用0001，0010和0100表示安全信息、信令信息和服務(wù)信息。使用0001，0010，0100，1000分別表示東、南、西、北4個不同行駛方向。

2.2.3 聚類種類個數(shù)

本文中對類別個數(shù)k使用貪婪準則進行選擇。當(dāng)網(wǎng)絡(luò)產(chǎn)生沖突時最少為兩類信息，所以初始化類別個數(shù)k最小為2，隨著k的增大分別計算網(wǎng)絡(luò)丟包率和平均時延，結(jié)果分別如表1和表2所示。

表1 系統(tǒng)丟包率與種類個數(shù)

表2 系統(tǒng)平均時延/ms與種類個數(shù)

表1為丟包率與種類個數(shù)。結(jié)果表明，隨著種類個數(shù)增加相同車輛個數(shù)下丟包率減小。表2為平均時延(ms)與種類個數(shù)。結(jié)果表明，當(dāng)車輛數(shù)不大于200時，平均時延隨著種類個數(shù)增加而減小，當(dāng)車輛數(shù)大于200時，在種類個數(shù)為4時平均時延為最小值。因此，本文選取種類個數(shù)設(shè)置為4。

根據(jù)上述仿真結(jié)果表明，丟包率在相同數(shù)目的車輛節(jié)點下，隨著種類個數(shù)的增加而減小。平均時延在大于300個車輛節(jié)點時，在種類個數(shù)為4時達到最優(yōu)，主要原因為種類個數(shù)過小時，產(chǎn)生過多無效分組，導(dǎo)致多次迭代增加計算時延。種類個數(shù)過大時，計算車輛節(jié)點間的區(qū)分度復(fù)雜增加計算時延。因此，本文K-means聚類算法采用4個節(jié)點特征進行分類。

2.3 擁塞控制

本文中決定網(wǎng)絡(luò)性能的參數(shù)為信息傳輸速率、傳輸范圍、競爭窗口和仲裁幀間間隔(AIFS)，其中，速率和范圍是影響網(wǎng)絡(luò)性能的主要因素。傳輸速率過大時使網(wǎng)絡(luò)傳輸信道負載過大導(dǎo)致網(wǎng)絡(luò)擁塞，傳輸速率過小時不能及時傳遞網(wǎng)絡(luò)拓撲動態(tài)變化情況。傳輸范圍過大時信道爭用性增大且沖突概率增大影響網(wǎng)絡(luò)可靠性，傳輸范圍過小時導(dǎo)致網(wǎng)絡(luò)邊緣車輛收到的擁塞信息無效。另外，競爭窗口和AIFS的大小對網(wǎng)絡(luò)性能也會產(chǎn)生影響。

根據(jù)IEEE802.11p的DSRC規(guī)定，傳輸速率標(biāo)準值為3 Mb/s，4.5 Mb/s，6 Mb/s，9 Mb/s，12 Mb/s，18 Mb/s，24 Mb/s，27 Mb/s，傳輸范圍的標(biāo)準值為10 m，50 m，100 m，150 m，210 m，300 m，350 m，380 m，450 m，550 m，650 m，750 m，850 m，930 m，971 m，1000 m，競爭窗口標(biāo)準值為(3,7)，(7,15)，(15,1023)，AIFS標(biāo)準值為1，2，3，7。

將上述4個通信參數(shù)的組合生成擁塞控制解決方案，對各類車輛節(jié)點選擇最小時延和最小丟包率的解決方案，將最優(yōu)方案與對應(yīng)類別生成列表存入寄存器中，再次碰到相同種類節(jié)點信息直接分配最優(yōu)方案。

3 仿真及結(jié)果分析

3.1 性能指標(biāo)

采用平均時延，平均吞吐量，丟包數(shù)，丟包率與沖突概率綜合評估本文提出的KCC方法的性能，平均時延和平均吞吐量評估算法的有效性，丟包數(shù)，丟包率和沖突概率評估算法的可靠性。

3.1.1 平均時延(T)

平均時延指從車輛開始發(fā)送數(shù)據(jù)算起，至另一車輛完全接收到該數(shù)據(jù)的時間

T=n(Tcl+Tpd+Tcs+Tcb)

(8)

其中，n為發(fā)送過程中的跳數(shù)，Tcl為處理時延，Tpd為排隊時延，Tcs為傳輸時延，Tcb為傳播時延。

3.1.2 平均吞吐量(AT)

平均吞吐量指車輛之間實際數(shù)據(jù)的傳輸速率，即單位時間內(nèi)實際傳輸?shù)臄?shù)據(jù)量

(9)

其中,DATA_MAX為DATA幀中記錄的數(shù)據(jù)大小。

3.1.3 丟包數(shù)和丟包率(PR)

丟包數(shù)指在車輛發(fā)送的數(shù)據(jù)中丟失的數(shù)據(jù)量。

丟包率指丟包數(shù)占車輛發(fā)送的所有數(shù)據(jù)包總數(shù)的比值

(10)

3.1.4 沖突概率(CP)

沖突概率指的是車輛發(fā)送的數(shù)據(jù)在傳輸過程中可能發(fā)生碰撞的概率

(11)

3.2 實驗參數(shù)及參數(shù)設(shè)置

針對十字路口下的車聯(lián)網(wǎng)擁塞場景，采用城市道路仿真軟件SUMO構(gòu)建曼哈頓道路模型及NS3網(wǎng)絡(luò)仿真軟件模擬交通狀態(tài)，從而實現(xiàn)動態(tài)雙向聯(lián)動仿真，其中曼哈頓道路模型選取8個十字路口。表3是完整的仿真參數(shù)。

表3 仿真模型參數(shù)

為了更好地評估本文提出的策略性能，與 IEEE802.11p中的CSMA/CA進行比較，CSMA/CA的仿真實驗中采用NS3提供的IEEE802.11p標(biāo)準模型。

3.3 實驗結(jié)果分析

圖6為不同策略下平均時延性能。結(jié)果表明，當(dāng)車輛從50增加到500輛的過程中，KCC策略的平均時延從 9.3 ms 增加到103.4 ms，而CSMA/CA相對應(yīng)為19.4 ms增加到1054.7 ms，總體來看，KCC方法始終低于CSMA/CA的平均時延，主要因為K-means聚類算法分類時利用了網(wǎng)絡(luò)層分簇時V2V的相對距離數(shù)據(jù)，減小了在MAC層的計算時延，從而使得網(wǎng)絡(luò)的平均時延減小。

圖6 不同策略的平均時延

圖7為不同策略下平均吞吐量性能。結(jié)果表明，當(dāng)車輛個數(shù)從50增加到500時，KCC策略平均吞吐量增加了27.9%，而CSMA/CA策略相對應(yīng)增加了7.7%?？傮w來看，KCC方法平均吞吐量始終大于CSMA/CA策略，主要原因在于K-means聚類算法將相似度高的車輛節(jié)點分為一類，在擁塞控制階段不用對每一個節(jié)點進行參數(shù)計算，增大了網(wǎng)絡(luò)吞吐量。

圖7 不同策略平均吞吐量

圖8為不同策略下丟包率性能。結(jié)果表明，當(dāng)500輛車時KCC策略丟包率為17.2%，而CSMA/CA策略的丟包率為57.4%，總體來看，KCC方法丟包率始終小于CSMA/CA策略，主要因為引入處理高并發(fā)數(shù)據(jù)的多線程方式，可以滿足網(wǎng)絡(luò)拓撲的動態(tài)性。

圖8 不同策略丟包率

圖9為不同策略下沖突概率性能。結(jié)果表明當(dāng)500輛車時KCC策略沖突概率為0.18，而CSMA/CA策略的沖突概率為0.96，總體來看，KCC方法沖突概率始終小于CSMA/CA策略，多線程處理車輛節(jié)點信息的模式使得V2V之間信息交互同步，降低了因爭用信道而產(chǎn)生沖突。

圖9 不同策略沖突概率

4 結(jié)束語

本文提出基于K-means聚類的車聯(lián)網(wǎng)擁塞控制方法，解決十字路口下車輛密度過大時造成的車聯(lián)網(wǎng)擁塞問題。本文基于IEEE802.11P協(xié)議的車聯(lián)網(wǎng)仿真架構(gòu)在處理車聯(lián)網(wǎng)擁塞發(fā)生時的大規(guī)模數(shù)據(jù)時引入多線程處理模式，使得V2V通信同步。擁塞檢測單元根據(jù)信道的使用情況判斷是否發(fā)生阻塞。K-means聚類時利用網(wǎng)絡(luò)層分簇的相對距離數(shù)據(jù)減輕MAC層計算負載，降低網(wǎng)絡(luò)的平均時延。擁塞控制單元確定各類網(wǎng)絡(luò)擁塞參數(shù)：傳輸速率、傳輸范圍、競爭窗口和仲裁幀間間隔形成最優(yōu)解決方案存儲在寄存器中，為同種類節(jié)點節(jié)省計算時延。綜合NS3與SUMO的動態(tài)雙向聯(lián)動仿真實驗結(jié)果，KCC策略的平均時延降低，吞吐量增大，丟包率減小，沖突概率減小。