鄭鑫　徐慧娟

摘 要： 車載自組網(wǎng)（VANET）是一種將高速移動車輛作為通信節(jié)點的自組網(wǎng)，動態(tài)的拓?fù)浣Y(jié)構(gòu)致使傳統(tǒng)的自組網(wǎng)路由機(jī)制不再適用。為此，提出基于分布式的分簇路由機(jī)制（DCRM）。DCRM首先引用RTB/CTB握手策略，源節(jié)點利用RTB/CTB數(shù)據(jù)包，獲取其一跳鄰居的信息，然后源節(jié)點根據(jù)每兩個鄰近節(jié)點間的距離小于門限值的原則，以分布式方式對這些鄰居節(jié)點進(jìn)行簇劃分。隨后，將每個簇中選擇一個離源節(jié)點最遠(yuǎn)的節(jié)點作為簇頭，源節(jié)點將消息傳輸至簇頭。接收消息后，簇頭成了源節(jié)點，重復(fù)此過程直至消息傳輸至目的節(jié)點。仿真結(jié)果表明，提出的DCRM提高了消息傳輸效率、降低了消息傳輸時延。

關(guān)鍵詞： RTB； CTB； 簇； 路由機(jī)制； 車載自組網(wǎng)

中圖分類號： TN911?34； TPT393 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）04?0016?05

Abstract： Vehicle?mounted Ad hoc network （VANET） is one kind of Ad hoc network， in which the rapidly moving vehicles are taken as communication nodes. Due to the dynamic topology structure， the traditional Ad hoc network routing mechanism is no more suitable for the current situation. Therefore， the distributed clustering?based routing mechanism （DCRM） is proposed in this paper. Firstly， the RTB/CTB handshake strategy is introduced into DCRM， and the RTB/CTB data package is utilized by source node to obtain the information of neighbor nodes. Secondly， if the distance between each couple of nearby vehicles is lower than a threshold value， the two vehicles will be considered to be the same cluster. The furthest vehicle inside each cluster is selected as the cluster?head （CH）， to which the data message is transmitted only. Upon receiving the data message， each CH will become the message source for the next contention phase， and the DCRM is repeated until data message is transmitted to the destination. The simulation result shows that the proposed DCRM can improve the efficiency of message transmission and reduce the time delay of message transmission.

Keywords： RTB； CTB； clustering； routing mechanism； VANET

0 引 言

車載自組網(wǎng)VANET（Vehicular ad Hoc Network）被認(rèn)為是應(yīng)用于未來智能交通系統(tǒng)的最有前景的技術(shù)，提供了多類的應(yīng)用服務(wù)，實現(xiàn)了車間短距離通信。如圖1所示，VANE中車輛裝有車載單元OBU（On?Board Unit），實現(xiàn)了車間通信V2V（Vehicle to Vehicle）和車與基礎(chǔ)設(shè)施通信V2I（Vehicle to Infrastructure）。有效的V2V通信能夠增強(qiáng)車輛行駛安全、提高交通效率[1?4]。然而，由于動態(tài)的拓?fù)?，變化的車速以及不均勻的車輛分布，維持不同簇內(nèi)的V2V通信存在巨大的挑戰(zhàn)。因此，多數(shù)路由機(jī)制采用廣播傳輸，進(jìn)而實現(xiàn)快速、實時地分享交通信息。但是，廣播傳輸一方面提高了共享消息的速率，另一方面引發(fā)信道頻繁的競爭以及數(shù)據(jù)包的碰撞，導(dǎo)致大量的冗余數(shù)據(jù)包，即廣播風(fēng)暴問題[5]。這直接影響了V2V通信效率。當(dāng)車輛廣播了一條消息，很有可能鄰居車輛之前已經(jīng)接收了此消息，這就導(dǎo)致消息傳輸冗余，降低信道資源利用率。

目前，已有較多針對傳統(tǒng)的MANET環(huán)境下的廣播風(fēng)暴的處理方案的文獻(xiàn)資料，但是針對VANET環(huán)境的文獻(xiàn)較少[6]。多數(shù)研究工作是以VANET作為連通順暢的網(wǎng)絡(luò)為前提。在間歇式連接的VANET中，設(shè)計一個可靠、有效的路由協(xié)議仍是一個挑戰(zhàn)。為此，提出基于分布式的分簇路由機(jī)制（Distributed Clustering?based Routing Mechanism，DCRM）。它充分利用車輛分布不均勻的特性，將鄰近的車輛看成一簇，并為每個簇選擇一個簇頭，由簇頭傳輸數(shù)據(jù)。DCRM采用源節(jié)點對其一跳鄰居節(jié)點進(jìn)行簇劃分，這種分布式的簇劃分有利用消息的快速傳輸，降低消息的傳輸時延、提高消息的傳輸效率。

1 相關(guān)工作

在VANET中，通常假定車間通信被分割成多個簇。簇內(nèi)的車輛能夠通過一跳或多跳方式與簇內(nèi)其他車輛通信，但是，簇與簇之間不存在直接連接，這便形成了基于簇的路由協(xié)議[7]，如圖2所示。

基于地理位置、移動方向以及其他信息，車輛形成不同的簇。簇提高了消息廣播、轉(zhuǎn)發(fā)效率，減少了不必要消息的復(fù)本的數(shù)目，降低了系統(tǒng)開銷。Ni等認(rèn)為每個簇內(nèi)有三類節(jié)點（車輛）[8]：簇頭、網(wǎng)關(guān)以及成員。網(wǎng)關(guān)車輛扮演著簇與簇間的連接角色。簇頭車輛是指其通信范圍能夠遍歷到簇內(nèi)的任何一個節(jié)點的車輛。簇內(nèi)成員就是非簇頭、網(wǎng)關(guān)的簇內(nèi)其他車輛。當(dāng)網(wǎng)關(guān)車輛從其他車輛接收到消息，就立即向簇頭傳遞，再通過簇頭向簇內(nèi)成員傳輸。但是，作者在文中并沒有給出簇頭的選擇過程。Fasolo等提出了智能廣播協(xié)議[9]。假定網(wǎng)絡(luò)被分割成不同的分區(qū)（Sector）。每個車輛能夠估計自己的位置，并且知道自己在哪個分區(qū)域。該協(xié)議利用競爭機(jī)制選擇轉(zhuǎn)發(fā)節(jié)點。盡管該協(xié)議看似有效，但是作者并沒有證實其網(wǎng)絡(luò)性能以及系統(tǒng)開銷。此外，Luo等也考慮了車輛的位置信息，提出了基于簇的路由協(xié)議[10]。將地理區(qū)域劃分為正方形網(wǎng)格（Foursquare gird）。簇頭依據(jù)鄰近的網(wǎng)格傳輸數(shù)據(jù)包。Sun等提出了基于RSU輔助的簇頭選擇機(jī)制[11]。通過部署RSU，并維持RSU與車輛間的連接，進(jìn)而選擇簇頭。上述研究并沒有考慮車輛的移動信息。實際上，車輛的移動影響了簇頭的選擇過程以及簇的穩(wěn)定性。Benslimane等利用車輛的移動方向、車間距離以及信號強(qiáng)度RSS（Received Signal Strength）信息構(gòu)建簇[12]。Gunter等在簇的碰撞階段考慮了車輛移動，并且簇頭具有最低的移動性以及離鄰居車輛的距離最近的特性[13]。此外，Kayis等將車輛分為速度群[14]。在同一個速度群內(nèi)的車輛在同一個簇內(nèi)。Koyamparambil等提出了基于簇的MAC協(xié)議，形成穩(wěn)定的簇[15]。利用車輛的位置、移動方向以及車道、速度信息劃分簇。Hafeeze等利用相對速度、車間距離選擇簇頭[16]。據(jù)此，本文以分布式方式，并充分結(jié)合車輛位置，提出了DCRM。

2 系統(tǒng)場景及約束條件

考慮混合交通場景：車輛的行駛速度隨機(jī)，車輛分布隨機(jī)，以接收真實的交通場景。提出的DCRM，基于以下假設(shè)：假定有N個車輛，每個車輛標(biāo)識為[υi]，[i=1，2，???，N，]其位置坐標(biāo)為[xi，yi]，本文車輛與節(jié)點概念等同，可以互換；所有車輛都具備GPS定位功能和無線局域網(wǎng)絡(luò)功能（WLAN capabilities）；每個車輛利用GPS系統(tǒng)獲取自己的位置；每個車輛通過交互beacon 消息，能夠獲取鄰居數(shù)；僅當(dāng)車輛[υi]與[υj]的距離[dij]小于通信范圍[R]，車輛[υi]與[υj]的通信鏈路才被建立。

3 DCRM

提出DCRM有兩個目的：避免重播消息，緩解廣播風(fēng)暴問題；快速、有效地進(jìn)行簇劃分。在DCRM中，僅選擇部分車輛進(jìn)行消息轉(zhuǎn)發(fā)，降低消息被重傳的次數(shù)。首先對網(wǎng)絡(luò)進(jìn)行簇劃分，每個簇產(chǎn)生一個簇頭。簇頭承擔(dān)著簇與簇之間的消息傳遞的任務(wù)。提出的DCRM主要分為四個階段：RTB傳輸，CTB傳輸、簇劃分以及簇頭選擇，如圖3所示。圖3（a）中，源節(jié)點（車輛）向一跳鄰居節(jié)點傳輸RTB控制包。隨后，鄰居節(jié)點通過設(shè)置等待時間輪流回復(fù)CTB控制包，如圖3（b）所示。源節(jié)點接收CTB控制包，從中提取鄰居節(jié)點的位置信息，并計算鄰近車輛間的距離，進(jìn)行簇劃分，并選擇離自己最遠(yuǎn)的車輛作為簇頭，如圖3（c）所示。最后，源節(jié)點向簇頭傳輸數(shù)據(jù)包，如圖3（d）所示。

3.1 RTB傳輸

當(dāng)源節(jié)點需要傳輸數(shù)據(jù)時，先向所有鄰居節(jié)點傳輸請求廣播RTB（Request?to?Broadcast）控制消息。RTB屬于MAC廣播包，包含了節(jié)點的地理位置信息，約7.5 B。

3.2 CTB傳輸

一旦接收到RTB消息，車輛就計算離源車輛的距離[d]，[d]能夠用于計算退避時間[tw]：

[tw=rtx-drtx?CWmax-CWmin+CWmin?tslot ]（1）式中：[rtx]為傳輸半徑；[CWmax]，[CWmin]分別表示競爭窗口的最大、最小尺寸。

當(dāng)退避時間[tw]計時完畢，車輛就向源節(jié)點回復(fù)CTB（Clear?to?Broadcast）數(shù)據(jù)包，其包含車輛ID以及離源車輛的距離，大小7.5 B。一旦收到有效了CTB數(shù)據(jù)包，車輛就退出競爭階段。

3.3 簇劃分

通過接收CTB數(shù)據(jù)包，源車輛獲取了鄰近車輛的位置以及距離信息，通過測量CTB消息的到達(dá)方向DOA（Direction of Arrival），源車輛計算鄰近車輛間的距離。如果鄰近區(qū)域的每兩輛車輛的距離小于門限值[Dmin]，這兩輛車輛將納入同一個簇。[Dmin]的選擇直接影響簇的數(shù)量。[Dmin]過大，每個簇內(nèi)成員數(shù)就越多，若[Dmin]趨近于零，每車輛能夠獨立形成一個簇如圖4所示。首先源節(jié)點對一跳鄰居節(jié)點的所有車輛依據(jù)DOA按降序從“0”開始編號，假定有N個一跳鄰居節(jié)點，對這些節(jié)點進(jìn)行0至N的編號。設(shè)定[N×N]維零矩陣A，相應(yīng)矩陣元素[Aij]的值為1，否則為0，如下所示：

依據(jù)矩陣A，算法2進(jìn)行簇劃分。矩陣[A]內(nèi)每一行元素值表示該行所對應(yīng)的節(jié)點離其他節(jié)點的距離是否小于門限值。檢測連續(xù)出現(xiàn)“1”的行（假定[i]行），然后將該行元素[Ai，：]與下一行元素[Ai+1，：]值一一對應(yīng)進(jìn)行或運(yùn)算，并進(jìn)行相加，如式（4）所示。

[Ii=j=0NAi，jAi+1，j] （3）

其中：[I]表示一維數(shù)組。如果[Ii=m]表示[m]個節(jié)點構(gòu)成一個簇，這[m]個節(jié)點的編號分別為[i]，[i]+1，…，[i+m-1]。

以式（3）為例，共檢查到有3行出現(xiàn)連續(xù)1，并且[I0=4]，[I4=2]，[I6=1]。因此，節(jié)點編號0，1，2，3為一簇；4，5為一簇，6為一簇，如下所示：

3.4 簇頭選擇

源節(jié)點對源節(jié)點進(jìn)行簇劃分后，就給每個簇選擇一個簇頭CH。每個簇內(nèi)離源車輛最遠(yuǎn)的車輛作為該簇的簇頭CH。隨后，源節(jié)點就將數(shù)據(jù)包傳輸?shù)酱仡^。數(shù)據(jù)包大小約1 526 B。一旦接收到了數(shù)據(jù)包，簇頭就變成下一輪源節(jié)點，類似，重復(fù)此過程，直接將數(shù)據(jù)包傳輸至目的節(jié)點。

4 數(shù)值分析

4.1 仿真場景

考慮高速場景，其基于中國上海的方形地圖，區(qū)域面積為15 km2。如圖5所示，該地圖來源于OSM（Open Street Map）網(wǎng)址，仿真時間為300 s，具體的仿真參數(shù)如表1所示。

選擇數(shù)據(jù)包傳輸率PDR（Packet Delivery Ratio）、端到端傳輸時延EED（End?to?End Delay）以及吞吐量（Through）三個性能指標(biāo)考察路由機(jī)制。數(shù)據(jù)包傳輸率PDR表示源節(jié)點發(fā)送的數(shù)據(jù)包與目的節(jié)點成功接收的比率，是衡量網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中信息包正確接收的性能參數(shù)。數(shù)據(jù)包傳輸率越大，路由機(jī)制的性能越好。端到端傳輸時延衡量傳輸效率，時延越短，表示傳輸效率越好。同時，與BBC[17]，SRB[18]進(jìn)行比較。仿真結(jié)果如圖6～圖8所示。

4.2 仿真結(jié)果分析

圖6描述了數(shù)據(jù)包傳輸率隨PDR隨節(jié)點數(shù)的變化曲線。從圖6可知，提出的DCRM的數(shù)據(jù)包傳輸率優(yōu)于BBC和SBP方案，隨著節(jié)點數(shù)的增加，優(yōu)勢隨之增加。原因在于DCRM充分利用節(jié)點的移動特性，通過簇頭轉(zhuǎn)發(fā)數(shù)據(jù)，提高路由的穩(wěn)定性，降低鏈路斷裂的概率，提高數(shù)據(jù)包傳輸?shù)男省?/p>

圖7顯示了吞吐量隨節(jié)點數(shù)的變化情況。從圖7可知，DCRM，BBC，SBP的吞吐量隨節(jié)點數(shù)的變化趨勢相同。當(dāng)車輛數(shù)少時，BBC的吞吐量略優(yōu)于DCRM，SBP。這主要是因為車輛密度小，發(fā)生信道競爭概率小，采用直接廣播的BBC存在優(yōu)勢。然而，隨著車輛密度的增加，DCRM的優(yōu)勢突顯出來，當(dāng)節(jié)點數(shù)達(dá)到120時，吞吐量是BBC，SBP的3倍。

圖8繪制了端到端傳輸時延EED隨節(jié)點數(shù)的變化情況。與圖7類似，DCRM，BBC，SBP的EED端到端傳輸時延隨節(jié)點數(shù)的變化情況相同。在車輛密度較大時，DCRM的EED明顯下降，比BBC下降約70%。

5 結(jié) 語

針對車載自組網(wǎng)VANET的消息傳輸機(jī)制問題，展開分析，并提出了基于分布式的分簇路由機(jī)制DCRM。DCRM以分布式方式對網(wǎng)絡(luò)節(jié)點進(jìn)行簇劃分。每個簇內(nèi)鄰近車輛間的距離小于門限值，并選擇離源節(jié)點最遠(yuǎn)的節(jié)點作為簇頭CH。簇頭CH承擔(dān)接連簇與簇間的通信，構(gòu)建了通信的主線。仿真結(jié)果表明，提出的DCRM在吞吐量、數(shù)據(jù)包傳輸率以及端到端傳輸時延方面的性能良好。將進(jìn)一步研究基于簇的路由機(jī)制，將其拓展至任何一個先應(yīng)式路由協(xié)議，進(jìn)而提高路由協(xié)議的性能。

參考文獻(xiàn)

[1] MISRA S， KRISHNA P V， SARITHA V. LACAV： an energy?efficient channel assignment mechanism for vehicular ad hoc networks [J]. Journal of supercomput， 2012， 62， （3）： 1241–1262.

[2] 夏梓峻，劉春鳳，趙增華，等.基于鏈路預(yù)測的VANET路由算法[J].計算機(jī)工程，2012，38（4）：110?114.

[3] KRISHNA P V， MISRA S， SARITHA V， et al. Learning automata?based virtual backoff algorithm for efficient medium access in vehicular Ad hoc networks [J]. Journal of systems architecture， 2013： 59（10）：968?975.

[4] 常促宇，向勇，史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J].通信學(xué)報，2007，11（5）：116?127.

[5] TONGUZ O， WISITPONGPHAN N， BAI F， et al. Broadcasting in VANET [C]// Proceedings of Mobile Networking for Vehicular Environment. [S.l.]： [s.n.]， 2007： 7?12.

[6] BUR K M. Evaluation of elective broadcast algorithms for safety application sin vehicular adhoc networks [J]. International journal of veh technol， 2011， 3（9）： 23?31.

[7] PALMA M E， VEGNI A M， NERI A. A fountain codes?based data dissemination techniqueinv ehicularad?hoc networks [C]// Proceedings of IEEE 11 International Conference on ITS Telecommunications. Saint?Petersburg， Russia： IEEE， 2011： 750?755.

[8] NI S， TSENG Y， CHEN Y， et al. The broadcast storm problem in a mobile Ad hoc network [C]// Proceedings on the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking（MobiCom）. [S.l.]： ACM， 2009： 151?162.

[9] FASOLO E， ZANELLA A， ZORZI M. An effective broadcast scheme for alert message propagation in vehicular ad hoc networks [C]// Proceedings on IEEE international conference on communications. [S.l.]： IEEE， 2006： 3960?3965.

[10] LUO Y， ZHANG W， HU Y. A new cluster based routing protocol for VANET [C]// Proceedings on Second International Conference on Networks Security Wireless Communications and Trusted Computing. [S.l.]： NSWCTC， 2010： 176?180.

[11] WU Y， XU J， XU Y. An RSU?assisted cluster head selection and backup protocol [C]// Proceedings on 26th International Conference on Advanced Information Networking and Applications Workshops. [S.l.]： WAINA， 2012： 581?587.

[12] BENSLIMANE T T， SIVARAJ R. Dynamic clustering?based adaptive mobile gatey management in integrated VANET?3G heterogeneous wireless networks [J]. IEEE journal of sel Areas Commun， 2011， 29（3）： 559?570.

[13] GUNTER Y， WIEGEL B， GROSSMANN H. Cluster?based medium access scheme for VANETs [C]// Proceedings on Intelligent Transportation Systems Conference. [S.l.]： [s.n.]， 2007： 34?45.

[14] KAYIS O， ACARMAN T. Clustering formation for inter?vehicle communication [C]// Proceedings on IEEE Intelligent Transportation Systems Conference. [S.l.]： ITST， 2007： 636?641.

[15] KOYAMPARAMBIL MAMMU A S， HERNANDEZ?JAYO U， SAINZ N. Cluster?based MAC in VANETs for safety applications [C]// Proceedings on International Conference on Advances in Computing， Communications and Informatics. [S.l.]： IEEE， 2013： 1424?1429.

[16] HAFEEZ K A， ZHAO L， LIAO Z， et al. A Fuzzy?logic?based cluster head selection algorithm in VANETs [C]// Proceedings on IEEE International Conference on Communications. [S.l.]： IEEE， 2012： 203?207.

[17] 宋軍，楊露霞，孫建樂，等.城市道路環(huán)境下的車載自組網(wǎng)分簇路由機(jī)制[J].重慶交通大學(xué)學(xué)報（自然科學(xué)版），2013，32（1）：108?113.

[18] MARIA V A， NATALIZIO E. Forwarder smart selection protocol for limitation of broadcast storm problem [J]. Journal of network and computer applications， 2015， 47（2）： 61?71.