基于親和傳播算法的車輛自組織網(wǎng)絡(luò)分簇組網(wǎng)方法

李 軍，周舒雨，甄 越，肖 喜，彭泳卿

基于親和傳播算法的車輛自組織網(wǎng)絡(luò)分簇組網(wǎng)方法

李 軍1，周舒雨2，甄 越1，肖 喜2，彭泳卿1

（1 北京遙測技術(shù)研究所 北京 100076 2 清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084）

隨著5G通信和自動駕駛汽車的發(fā)展，車輛自組織網(wǎng)絡(luò)VANET（Vehicular Ad Hoc Network）作為一種新型的移動自組織網(wǎng)絡(luò)，因其在改善道路安全、為駕駛員和乘客提供便利方面的潛力，而引起學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。它可以通過提供交通流量、事故通知、危險警告、可能存在的定位偏差、天氣等信息來增強道路安全，從而提高交通效率。由于車輛的高速移動會經(jīng)常引起網(wǎng)絡(luò)拓?fù)渲袛?，因此一個設(shè)計良好的路由協(xié)議至關(guān)重要。提出了一種適用于車輛自組織網(wǎng)絡(luò)環(huán)境的基于分簇的路由協(xié)議，設(shè)計并實現(xiàn)了一種基于親和傳播算法的分簇組網(wǎng)模型V-APC（VANET-Affinity Propagation Clustering）。通過重新定義親和傳播算法的相似函數(shù)，設(shè)計了簇頭的選擇過程、簇的形成過程還有簇的維護過程。結(jié)果表明：采用上述方法形成的簇，在簇內(nèi)的通信性能和簇穩(wěn)定性方面具有顯著優(yōu)勢，使得該協(xié)議在路由延遲和數(shù)據(jù)包轉(zhuǎn)發(fā)成功率方面表現(xiàn)優(yōu)異。

車輛自組網(wǎng)；路由協(xié)議；分簇算法；親和傳播算法

引 言

隨著全球經(jīng)濟的快速發(fā)展，汽車保有量迅速增長。安全駕駛、交通擁堵和環(huán)境污染成為當(dāng)前困擾交通領(lǐng)域的三大問題。VANET因其可實時為客戶提供準(zhǔn)確的狀態(tài)數(shù)據(jù)，具有改善道路安全性以及為司機和乘客提供便利的潛力，在學(xué)術(shù)界和工業(yè)界均引起了廣泛關(guān)注[1]。但目前關(guān)于VANET的研究都集中在數(shù)據(jù)分布和聚合、通道訪問管理、交通安全、拓?fù)浒l(fā)現(xiàn)和路由協(xié)議等特定問題和應(yīng)用上。

VANET將道路上的各汽車視為移動節(jié)點，并使用這些節(jié)點創(chuàng)建了一個移動動態(tài)網(wǎng)絡(luò)。其目的是為車輛提供無線連接，并部署智能交通系統(tǒng)規(guī)定的防碰撞預(yù)警、安全分析、緊急預(yù)警和提高交通效率等各種應(yīng)用[2]。

近年來，智能城市的提出讓更多的人對VANET關(guān)注，VANET提供的服務(wù)也向著更可靠、更全面的娛樂和生活需求轉(zhuǎn)變，對有效的VANET路由協(xié)議的需求也日益強烈。為了適應(yīng)VANET的特點，并使路由協(xié)議在最小丟包率和負(fù)載控制的情況下達(dá)到最大的吞吐率[3-6]，有必要針對VANET開發(fā)適合自身網(wǎng)絡(luò)特點的路由協(xié)議。

由于VANET具有高移動性、動態(tài)的拓?fù)浣Y(jié)構(gòu)，易受建筑物遮擋、網(wǎng)絡(luò)節(jié)點隨機分布、無線傳輸間歇性中斷和陰影效應(yīng)等限制[7]，將數(shù)據(jù)包傳輸?shù)阶罱K目的節(jié)點存在許多挑戰(zhàn)。

考慮到道路上車輛的復(fù)雜移動和動態(tài)拓?fù)浣Y(jié)構(gòu)，設(shè)計高效的路由協(xié)議是車輛自組網(wǎng)中不可忽視的重要問題。首先，VANET有區(qū)別于其他類型自組織網(wǎng)絡(luò)和無線網(wǎng)絡(luò)的高移動性[8]，車速因路況而定，速度變化直接影響網(wǎng)絡(luò)的穩(wěn)定性并導(dǎo)致網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化；其次，VANET區(qū)域中車輛節(jié)點的密度不均勻，呈現(xiàn)出時空變化[9]，當(dāng)車輛密度低且不規(guī)則時，通常會發(fā)生網(wǎng)絡(luò)碎片化；最后，車輛在斷開的VANET中行駛，會導(dǎo)致端到端通信極其困難[10]。

鑒于上述問題和挑戰(zhàn)，本文針對性地開展了以下研究：

首先，通過引入與通信相關(guān)的三個參數(shù)來重新定義親和傳播AP（Affinity Propagation）分簇算法中的相似度函數(shù)，使得相對機動性低、通信性能好的車輛很容易被選為簇頭，這些健壯的簇頭有助于在簇形成階段提高簇的穩(wěn)定性。

其次，基于速度函數(shù)、位置函數(shù)和通信性能函數(shù)三個子函數(shù)，設(shè)計了一種加權(quán)機制，定量評估車輛加入對簇穩(wěn)定性的影響。這有助于從多個候選簇頭中選擇最佳簇頭。

最后，在VANET的混合分布式系統(tǒng)模型中定義了車輛的三種狀態(tài)，并設(shè)計了與之相關(guān)的完整轉(zhuǎn)換過程。在此基礎(chǔ)上，本文提出了一種V-APC（基于親和傳播算法的分簇組網(wǎng)模型）算法，該算法負(fù)責(zé)聚類過程的四個不同階段。V-APC算法的顯著特點是：當(dāng)車輛選擇加入簇時，簇中的所有車輛都將參與。與其他聚類算法相比，該算法不僅可以實現(xiàn)更好的聚類穩(wěn)定性，而且可以提高VANET的吞吐量，降低丟包率。大量的仿真可以驗證該算法的有效性。

本文的后續(xù)章節(jié)組織如下：第一節(jié)介紹了VANET路由協(xié)議領(lǐng)域的相關(guān)工作和成果。第二節(jié)詳細(xì)闡述了所提出的框架。第三節(jié)給出了所提出的V-APC模型和相關(guān)研究中常用的幾種聚類網(wǎng)絡(luò)模型的實驗。第四節(jié)對于工作進行了總結(jié)，并討論了未來工作的方向。

1 VANET相關(guān)工作和成果

1.1 VANET通信模式

在本文所提出的車輛自組織網(wǎng)絡(luò)分簇組網(wǎng)模型中，采用了混合式通信模式，如圖1所示，其采用車間通信長期演進LTE-V（Long Term Evolution-Vehicle）通信協(xié)議[11]。LTE-V包括集中式和分布式兩種工作模式。集中式使用基站來控制網(wǎng)絡(luò)中的車輛節(jié)點，該模式覆蓋范圍大、帶寬大，但是傳輸時延相對較高，不利于安全性信息在車輛間的傳輸；分布式則是車輛節(jié)點與車輛節(jié)點之間的直接通信，其優(yōu)點是無基站、成本低[12]。

圖1 車輛自組織網(wǎng)絡(luò)基于分簇的混合式系統(tǒng)模型

本文將V-APC模型中的車輛分為三類：非簇（UN）節(jié)點、簇頭（CH）節(jié)點和簇成員（CM）節(jié)點。每輛車的狀態(tài)可以在本文提出的分簇組網(wǎng)模型[13-15]中互換。

① UN節(jié)點可能是每個車輛在車輛自組織網(wǎng)絡(luò)啟動之初的狀態(tài)，也可能是分簇過程中某些車輛脫離網(wǎng)絡(luò)的狀態(tài)，UN節(jié)點是簇外節(jié)點，不屬于任何簇。

② CH節(jié)點負(fù)責(zé)管理簇及簇成員節(jié)點，一個CH節(jié)點只存在于一個簇中，一個簇中也只含有一個CH節(jié)點。CH節(jié)點可以使用LTE-V的分布式模式與同一簇中的每個CM節(jié)點以及其它相鄰簇的CH節(jié)點進行通信。此外，它還可以使用LTE-V的集中式模式與基站通信。

③ CM節(jié)點是簇中大多數(shù)車輛所處的狀態(tài)，CM節(jié)點只存在于一個簇中，它可以使用LTE-V的分布式模式與同一簇中的其它CM節(jié)點和CH節(jié)點進行通信。

1.2 VANET路由協(xié)議

目前，分簇路由是業(yè)界針對VANET的特點推出的一種新型路由協(xié)議。該類協(xié)議將網(wǎng)絡(luò)中的車輛節(jié)點劃分為簇。因此，車輛位置相對較近的節(jié)點容易形成一個簇，選擇其中一個車輛節(jié)點作為簇頭。簇的大小根據(jù)用于形成簇的標(biāo)準(zhǔn)而有所不同[16]，例如車輛的數(shù)量、地理位置、移動方向和速度可以作為將網(wǎng)絡(luò)劃分為簇的度量。在此之后，簇內(nèi)節(jié)點選舉一個簇頭節(jié)點負(fù)責(zé)管理簇，以完成簇間通信[17]。然后，在簇間通信中選擇最佳鄰居簇來轉(zhuǎn)發(fā)數(shù)據(jù)。基于分簇的路由協(xié)議比較適合車輛自組織網(wǎng)絡(luò)環(huán)境，其數(shù)據(jù)包轉(zhuǎn)發(fā)成功率相對較高，并且其路由開銷在合理范圍內(nèi)。

為了解決高速公路上快速行駛的車輛之間的數(shù)據(jù)交互問題，Santos首次將移動自組織網(wǎng)絡(luò)中的分簇思想應(yīng)用到VANET中，但是他設(shè)計的基于簇的位置路由分簇算法CBLR（Cluster-based Location Routing）僅根據(jù)簇成員的數(shù)量選擇簇頭，在簇的穩(wěn)定性和簇的規(guī)模方面都存在不足[18]。Gunter將與速度相關(guān)的參數(shù)引入到分簇過程中，提出了一種基于平均速度差和與相鄰節(jié)點距離的加權(quán)和來選擇簇頭的機制，有效避免了規(guī)模較大的簇[19]。針對城市十字路口對簇穩(wěn)定性的影響，Hadded提出了自適應(yīng)加權(quán)分簇算法AWCP（Adaptive Weighted Clustering Protocol），在簇生成過程和簇維護過程中考慮了與相鄰車輛具有相同公路ID和相同方向的車輛，并利用多目標(biāo)遺傳算法對算法的參數(shù)進行了優(yōu)化[20]。但是由于上述分簇算法只考慮單個時間點的指標(biāo)值，因此簇的穩(wěn)定性容易受到車輛運動的隨機性和瞬時性的影響。

2 方法論

2.1 親和傳播算法

親和傳播算法[21-23]是一種基于節(jié)點間消息傳遞的聚類算法。選擇該算法具有以下優(yōu)點：①不需要預(yù)先確定分簇組網(wǎng)模型的簇數(shù)，可以根據(jù)模型中的車輛節(jié)點數(shù)量自適應(yīng)確定簇數(shù)；②在基于親和傳播算法的分簇組網(wǎng)模型中選擇的CH是網(wǎng)絡(luò)中實際存在的車輛節(jié)點；③通過維護責(zé)任度矩陣和可信度矩陣，采用互評機制來改善簇穩(wěn)定性。

最后，為了避免信息更新過程中產(chǎn)生數(shù)值振蕩，親和傳播算法采用了阻尼消息更新機制，如下所示：

2.2 簇頭選擇過程

此外，在責(zé)任更新、可信度更新和簇頭節(jié)點選擇策略方面，本文提出的分簇組網(wǎng)模型與原親和傳播算法一致。綜上所述，通過對分簇組網(wǎng)模型的簇頭節(jié)點選擇過程的分析可以看出，相對移動性低、MTR值高的車輛節(jié)點更容易被選為簇頭節(jié)點。

2.3 簇形成過程

在分簇組網(wǎng)模型經(jīng)過簇頭節(jié)點的選擇過程后，車輛自組織網(wǎng)絡(luò)中會出現(xiàn)一個或多個簇頭節(jié)點。未定義節(jié)點將選擇其中一個簇頭節(jié)點作為自己的簇頭節(jié)點，并成為由簇頭節(jié)點管理的簇的簇成員節(jié)點。未定義節(jié)點添加到簇后，將變?yōu)榇爻蓡T節(jié)點狀態(tài)，這就是簇的形成過程。該過程如圖2所示。

圖2 UN與CM之間的狀態(tài)轉(zhuǎn)換過程

從式（7）可以看出，速度函數(shù)的值越小，對簇的穩(wěn)定性的負(fù)面影響越小。

從式（9）可以看出，位置函數(shù)的值越小，對簇穩(wěn)定性的負(fù)面影響越小。

通過對式（11）和式（12）分析可以看出，對于分簇組網(wǎng)模型中的某個車輛節(jié)點，其通信性能函數(shù)的值在0～1之間。該函數(shù)的值越小，對簇頭節(jié)點通信性能的負(fù)面影響越小。

綜合評價函數(shù)是基于上述三個函數(shù)（速度函數(shù)、位置函數(shù)、通信性能函數(shù)）的線性加權(quán)和來定量評價節(jié)點加入簇時對該簇的整體影響。綜合評價函數(shù)定義公式如下：

3 實驗和評估

在本節(jié)中，全面評估了所提出的V-APC模型。首先使用城市交通仿真平臺SUMO（Simulation of Urban Mobility）生成車輛移動數(shù)據(jù)，使用OMNET++網(wǎng)絡(luò)模擬器來模擬車輛自組織網(wǎng)絡(luò)環(huán)境，Veins提供了車輛自組織網(wǎng)路由的相關(guān)模塊。然后，對涉及簇穩(wěn)定性和通信性能的指標(biāo)進行了闡述，最后，將提出的V-APC模型的性能與經(jīng)典的分簇算法，移動度量分簇算法MOBIC（Mobility Metric Clustering）和平均精度均值算法MAP（Mean Average Precision）進行了比較，并根據(jù)仿真結(jié)果對不同的車流量場景進行了詳細(xì)分析[24]。

3.1 車載自組網(wǎng)交通場景

為了使仿真具有客觀性，使用數(shù)據(jù)集TAPASCologne來仿真車輛自組織網(wǎng)絡(luò)交通場景，并選擇該數(shù)據(jù)集一平方公里作為仿真區(qū)域[25]。為了與現(xiàn)有研究保持一致，根據(jù)所選區(qū)域的車輛行駛數(shù)據(jù)，構(gòu)建了分別對應(yīng)40輛、80輛、120輛、160輛和200輛車輛的五個交通流量仿真場景。在這些場景中，道路的最高限速是一個常數(shù)。本次仿真實驗的主要參數(shù)設(shè)置見表1。

表1 主要仿真參數(shù)設(shè)置

3.2 實驗評價指標(biāo)

在仿真實驗中，為了系統(tǒng)地評估本文提出的基于親和傳播算法的分簇組網(wǎng)模型（V-APC）的性能，從穩(wěn)定性能和通信性能的角度給出了車輛自組織網(wǎng)絡(luò)分簇研究中常用的8項性能指標(biāo)：

①穩(wěn)定性能指標(biāo)

簇的穩(wěn)定性由簇頭節(jié)點的穩(wěn)定性和簇成員節(jié)點的穩(wěn)定性組成，可以從簇的生存時間和簇的規(guī)模兩個方面評價[26-28]。在此基礎(chǔ)上，本文采用了四個可以描述簇穩(wěn)定性的參考指標(biāo)。

CH節(jié)點平均生存時間：分簇組網(wǎng)模型中所有CH節(jié)點的平均生存時間為所有CH節(jié)點生存時間之和除以CH節(jié)點個數(shù)。

CM節(jié)點平均生存時間：分簇組網(wǎng)模型中所有CM節(jié)點的平均生存時間為所有CM節(jié)點生存時間之和除以CM節(jié)點個數(shù)。

CH節(jié)點變化率：分簇組網(wǎng)模型中所有CH節(jié)點在單位時間內(nèi)的狀態(tài)變化的次數(shù)。通過用所有CH節(jié)點的狀態(tài)變化總數(shù)除以分簇周期的總時間計算。

分簇效率：是衡量分簇過程中有效狀態(tài)車輛程度的穩(wěn)定性指標(biāo)。通過用所有CH節(jié)點和CM節(jié)點的數(shù)量占分簇組網(wǎng)模型中節(jié)點總數(shù)的百分比計算。

②通訊性能指標(biāo)

吞吐量、丟包和包延遲一直是車輛自組織網(wǎng)絡(luò)的三個主要通信問題。本文使用了四個通信性能指標(biāo)。

CH節(jié)點平均吞吐量：指定時間內(nèi)所有CH節(jié)點的平均吞吐量。通過用仿真時間內(nèi)所有CH節(jié)點的簇內(nèi)吞吐量與簇間吞吐量之和除以CH節(jié)點數(shù)計算。

簇的平均吞吐量：指定時間內(nèi)所有簇的平均吞吐量。通過用仿真時間內(nèi)簇中所有CM節(jié)點的簇內(nèi)吞吐量之和除以簇數(shù)量計算。

簇的平均丟包率：指定時間內(nèi)所有簇的平均丟包率。通過用簇中所有節(jié)點的丟包率之和除以這些節(jié)點的總數(shù)計算。其中，節(jié)點的丟包率通過用仿真時間內(nèi)失敗的數(shù)據(jù)包數(shù)除以數(shù)據(jù)包總數(shù)的商來計算。

簇的平均包時延：指定時間內(nèi)所有簇的平均包延遲。通過用簇內(nèi)所有節(jié)點的包延遲之和除以這些節(jié)點總數(shù)計算。其中，車輛的數(shù)據(jù)包延遲通過用數(shù)據(jù)包發(fā)送和接收的時間間隔之和除以仿真時間內(nèi)的數(shù)據(jù)包總數(shù)計算。

3.3 仿真結(jié)果分析

為了消除仿真誤差對性能分析的影響，每個仿真進行了100次[29]?；谶@些仿真結(jié)果，對兩類性能指標(biāo)進行了詳細(xì)的對比分析如下。

3.3.1 穩(wěn)定性分析

圖3比較了這三種算法在五種交通流量條件下的生存時間穩(wěn)定性。具體而言，圖3（a）顯示V-APC模型在CH節(jié)點平均生存時間方面，比MOBIC算法和MAP算法分別長15%和20%。圖3（b）顯示V-APC模型與MOBIC算法和MAP算法對于CM節(jié)點的平均生存時間相似。圖3（c）顯示V-APC模型得到的CH節(jié)點變化率分別比MOBIC算法和MAP算法低83%和82%，并且?guī)缀醪浑S車流量的變化而變化。圖3（d）顯示在分簇效率方面，V-APC模型接近MAP算法，并比MOBIC算法高20%。

圖3 三種分簇算法的穩(wěn)定性比較

綜上所述，在簇的穩(wěn)定性方面，V-APC模型在五種車流量場景下的性能指標(biāo)均優(yōu)于MOBIC算法和MAP算法。分析如下：

① V-APC模型解決了異常鄰居節(jié)點對簇穩(wěn)定性的干擾。而MOBIC算法和MAP算法并沒有考慮到這一點；

② V-APC模型引入了節(jié)點的單跳有效距離，使得與其他節(jié)點相對移動性較低的節(jié)點作為簇頭；

③在簇形成過程中，V-APC模型通過選擇綜合評價函數(shù)值最小的簇來減少新增節(jié)點對簇穩(wěn)定性的負(fù)面影響。相比之下，MOBIC算法和MAP算法只考慮了新增節(jié)點對CH節(jié)點的負(fù)面影響，沒有考慮新增節(jié)點對簇的負(fù)面影響。

3.3.2 通信性能分析

圖4比較了三種算法在五種車輛流量條件下的通信性能。具體而言，圖4（a）顯示V-APC模型的CH節(jié)點的平均吞吐量比MOBIC算法和MAP算法分別高57%和64%。對于簇的平均吞吐量，圖4（b）顯示V-APC模型比MOBIC算法和MAP算法分別高26%和102%。圖4（c）顯示V-APC模型的簇平均丟包率比MOBIC算法和MAP算法分別低82%和74%。圖4（d）顯示V-APC模型的平均包延時比MOBIC算法多39%，比MAP算法少14%。

綜上所述，在簇的通信性能方面，V-APC模型在五個車流量場景下的性能值（除簇平均包時延外）和所有性能值的數(shù)值穩(wěn)定性均優(yōu)于MOBIC算法和MAP算法。分析如下：

圖4 三種分簇算法的通信性能比較

① V-APC模型較好的存活時間穩(wěn)定性使其具有比MOBIC算法和MAP算法更好的通信性能；

② V-APC模型相對較好的規(guī)模穩(wěn)定性也使其比MOBIC算法和MAP算法具有更好的通信性能；

③ V-APC模型考慮了CH節(jié)點的MTR參數(shù)，并通過相似度函數(shù)選擇MTR值最大的車輛作為CH節(jié)點，而MOBIC算法和MAP算法忽略了與通信相關(guān)的參數(shù)。

4 結(jié)束語

針對車輛高機動性對車輛自組織網(wǎng)絡(luò)通信的影響，本文提出一種V-APC模型。與傳統(tǒng)的分簇算法相比，該模型具有更好的分簇穩(wěn)定性和通信性能。一方面，V-APC模型利用信標(biāo)幀識別單跳距離內(nèi)的異常車輛，并為每輛車建立正常鄰居列表，避免了異常車輛對簇穩(wěn)定性的負(fù)面影響。另一方面，V-APC模型在原親和傳播算法的相似度函數(shù)基礎(chǔ)上重新定義了新的相似度函數(shù)，引入了與通信相關(guān)的參數(shù)。并設(shè)計了簇的CH節(jié)點選擇流程、簇的形成流程、簇的維護流程。在此基礎(chǔ)上，V-APC模型采用加權(quán)機制來定量評價車輛對簇穩(wěn)定性的影響，通過選擇綜合評價值最低的簇改進了原親和傳播算法的簇形成過程。在五種車流量場景下的仿真結(jié)果表明：V-APC模型在簇穩(wěn)定性和通信性能以及模型的魯棒性方面均優(yōu)于MOBIC算法和MAP算法。

[1] CHENG J J, CHENG J L, ZHOU M C, etal. Routing in internet of vehicles: A review[J]. IEEE Transactions on Intelligent Transportation Systems, 2015,16(5): 2339–2352.

[2] RAYENI M S, HAFID A. Routing in heterogeneous vehicular networks using an adapted software defined networking approach[C]// Fifth International Conference on Software Defined Systems (SDS), Barcelona, Spain, 2018: 25–31.

[3] CAO Z, SHI K, SONG Q, et al. Analysis of between vehicle density and network congestion in vanets[C]// 7th IEEE International Conference on Electronics Information and Emergency Communication (ICEIEC), Macau, China, 2017: 409–412.

[4] SENOUCI O, ALIOUAT Z, HAROUS S. A review of routing protocols in internet of vehicles and their challenges[J]. Sensor Review, 2019, 39(1): 58–70.

[5] AL-SULTAN S, AL-DOORI M M, AL-BAYATTI A H, et al. A comprehensive survey on vehicular ad hoc network[J]. Journal of Network and Computer Applications, 2014, 37:380–392.

[6] BALI R S, KUMAR N, RODRIGUES J. Clustering in vehicular ad hoc networks: Taxonomy, challenges and solutions[J]. Vehicular Communications, 2014, 1(3): 134–152.

[7] YANG P, WANG J, ZHANG Y, et al. Clustering algorithm in VANETs: A survey[C]// IEEE 9th International Conference on Anti-counterfeiting, Security, and Identification (ASID), Xiamen, China, 2015: 166–170.

[8] COOPER C, FRANKLIN D, ROS M, et al. A comparative survey of VANET clustering techniques[J]. IEEE Communications Surveys & Tutorials, 2017, 19(1): 657–681.

[9] HOSMANI S, MATHPATI B. Survey on cluster based routing protocol in VANET[C]//International Conference on Electrical, Electronics, Communication, Computer, and Optimization Techniques (ICEECCOT), Mysuru, India, 2017: 1–6.

[10] PAL R, PRAKASH A, TRIPATHI R, et al. Analytical model for clustered vehicular ad hoc network analysis[J]. ICT Express, 2018, 4(3): 160–164.

[11] EPHREMIDES A, WIESELTHIER J E, BAKER D J. A design concept for reliable mobile radio networks with frequency hopping signaling[J]. Proceedings of the IEEE, 1987, 75(1): 56–73.

[12] LIN C R, GERLA M. Adaptive clustering for mobile wireless networks[J]. IEEE Journal on Selected Areas in Communica- tions, 1997, 15(7): 1265–1275.

[13] CHATTERJEE M, DAS S K, TURGUT D. WCA: A weighted clustering algorithm for mobile ad hoc networks[J]. Cluster Computing, 2002, 5(2): 193–204.

[14] ZHANG Y, NG J M. A distributed group mobility adaptive clustering algorithm for mobile ad hoc networks[C]// IEEE International Conference on Communications, Beijing, China, 2008: 3161–3165.

[15] KONSTANTOPOULOS C, GAVALAS D, PANTZIOU G. Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction[J]. Computer Networks, 2008, 52(9): 1797–1824.

[16] SOOD M, KANWAR S. Clustering in MANET and VANET: A survey[C]// International Conference on Circuits, Systems, Communication and Information Technology Applications (CSCITA), Mumbai, India, 2014: 375–380.

[17] HAFEEZ K A, ZHAO L, LIAO Z, et al. A fuzzy-logic-based cluster head selection algorithm in VANETs[C]// IEEE International Conference on Communications (ICC), Ottawa, Canada, 2012: 203–207.

[18] ALSUHLI G, KHATTAB A, FAHMY Y. Double-head clustering for resilient VANETs[J]. Wireless Communications and Mobile Computing, 2019: 1–17.

[19] SULISTYO S, ALAM S, ADRIAN R J. Coalitional game theoretical approach for VANET clustering to improve SNR[J]. Journal of Computer Networks and Communications, 2019: 4573619.

[20] RAWASHDEH Y, MAHMUD S. A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[J]. EURASIP Journal on Wireless Communications and Networking, 2012, (1):15.

[21] CHENG X, HUANG B. A center-based secure and stable clustering algorithm for vanets on highways[J]. Wireless Communications and Mobile Computing, 2019: 1–10.

[22] SENOUCI O, HAROUS S, ALIOUAT Z. An efficient weight-based clustering algorithm using mobility report for IoV[C]// 9th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference(IEEE UEMCON 2018), New York, USA, 2018.

[23] SENOUCI O, ALIOUAT Z, HAROUS S. Mca-v2i: A multi-hop clustering approach over vehicle-to-internet communication for improving vanets performances[J]. Future Generation Computer Systems, 2019, 96: 309–323.

[24] SENOUCI O, HAROUS S, ALIOUAT Z. A new heuristic clustering algorithm based on RSU for internet of vehicles[J]. Computer Engineering and Computer Science, 2019, 44(11): 9735–9753.

[25] MEHTA S, SHARMA P, KOTECHA K. A survey on various cluster head election algorithms for MANET[C]// Nirma University International Conference on Engineering. Ahmedabad, Gujarat, India, 2011: 1–6.

[26] MAIZATE A, KAMOUN N E. A new metric based cluster head selection technique for prolonged lifetime in wireless sensor networks[J]. International Review on Computers and Software (IRECOS), 2013, 3(4): 227–236.

[27] NGUYEN V, KIM O, DANG D, et al. Application of the lowest-id algorithm in cluster-based tdma system for vanets[C]// International Conference on Information Networking (ICOIN), Cambodia, 2015: 25–30.

[28] FAN W, SHI Y, CHEN S, et al. A mobility metrics based dynamic clustering algorithm for vanets[C]// IET International Conference on Communication Technology and Application (ICCTA 2011), 2011: 752–756.

[29] AADIL F, AHSAN W, REHMAN Z, et al. Clustering algorithm for Internet of vehicles (IOV) based on dragonfly optimizer (cavdo)[J]. The Journal of Supercomputing, 2018, 74(9): 4542–4567.

A clustering networking method based on affinity propagation algorithm in VANET

LI Jun1, ZHOU Shuyu2, ZHEN Yue1, XIAO Xi2, PENG Yongqing1

（1. Beijing Research Institute of Telemetry, Beijing 100076, China;2. Dept. Computer Technology, Tsinghua University, Beijing 100084, China）

Intelligent transportation systems have received extensive attention in recent years by dealing with the complex relationships between vehicles, roads, pedestrians and other objects. Vehicle ad hoc networks (VANET) play an important role in intelligent transportation systems because they can provide accurate status data for all participants in real time, especially with the rise of autonomous vehicles and 5G communications. Vehicle ad hoc network is a new autonomous dynamic topology network, a special sub-category of mobile ad hoc network (MANET), it can enhance road safety and improve traffic efficiency by providing information about traffic flow, accident notification, danger warning, possible deviation or weather. Considering the mobility of road traffic, these networks have aroused widespread concern in academia and industry because of their potential to improve road safety and provide convenience for drivers and passengers. Due to the high-speed movement of vehicles in the vehicle ad hoc network, the network topology is frequently interrupted. Therefore, a well-designed routing protocol is essential. After a lot of literature research and analysis, we have concluded that the routing protocol based on clustering is suitable for the vehicle ad hoc network environment. Therefore, this paper proposes a routing protocol based on clustering. A clustering networking model based on affinity propagation algorithm is proposed. By reconstructing the similarity function of the affinity propagation algorithm, the cluster head selection process, cluster formation process and cluster maintenance process are designed. The formed cluster performs better in terms of stability and communication performance within the cluster. This protocol performs well in terms of routing delay and packet forwarding success rate.

VANET; Routing protocol; Cluster algorithm; Affinity propagation algorithm

Website: ycyk.brit.com.cn Email: ycyk704@163.com

TN915

A

CN11-1780(2022)06-0136-11

10.12347/j.ycyk.20220714001

李軍, 周舒雨, 甄越, 等. 基于親和傳播算法的車輛自組織網(wǎng)絡(luò)分簇組網(wǎng)方法[J]. 遙測遙控, 2022, 43(6): 136–146.

10.12347/j.ycyk.20220714001

: LI Jun, ZHOU Shuyu, ZHEN Yue, et al. A clustering networking method based on affinity propagation algorithm in VANET[J]. Journal of Telemetry, Tracking and Command, 2022, 43(6): 136–146.

彭泳卿（pengyongqing1980@163.com）

2022-07-12

2022-08-09

李 軍 1963年生，工程師，主要研究方向為特種元器件測試。

周舒雨 1994年生，碩士，主要研究方向為計算機技術(shù)。

甄 越 1999年生，碩士研究生，主要研究方向為無線傳感器。

肖 喜 1976年生，博士，副教授，主要研究方向為信息安全。

彭泳卿 1980年生，博士，研究員，主要研究方向為航天特種傳感器與傳感系統(tǒng)技術(shù)。

(本文編輯：傅 杰)