鄭鑫　徐慧娟

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

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

中圖分類號(hào)： TN911?34； TPT393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ù)，實(shí)現(xiàn)了車間短距離通信。如圖1所示，VANE中車輛裝有車載單元OBU（On?Board Unit），實(shí)現(xiàn)了車間通信V2V（Vehicle to Vehicle）和車與基礎(chǔ)設(shè)施通信V2I（Vehicle to Infrastructure）。有效的V2V通信能夠增強(qiáng)車輛行駛安全、提高交通效率[1?4]。然而，由于動(dòng)態(tài)的拓?fù)?，變化的車速以及不均勻的車輛分布，維持不同簇內(nèi)的V2V通信存在巨大的挑戰(zhàn)。因此，多數(shù)路由機(jī)制采用廣播傳輸，進(jìn)而實(shí)現(xiàn)快速、實(shí)時(shí)地分享交通信息。但是，廣播傳輸一方面提高了共享消息的速率，另一方面引發(fā)信道頻繁的競(jìng)爭(zhēng)以及數(shù)據(jù)包的碰撞，導(dǎo)致大量的冗余數(shù)據(jù)包，即廣播風(fēng)暴問題[5]。這直接影響了V2V通信效率。當(dāng)車輛廣播了一條消息，很有可能鄰居車輛之前已經(jīng)接收了此消息，這就導(dǎo)致消息傳輸冗余，降低信道資源利用率。

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

1 相關(guān)工作

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

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

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

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

3 DCRM

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

3.1 RTB傳輸

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

3.2 CTB傳輸

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

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

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

3.3 簇劃分

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

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

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

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

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

3.4 簇頭選擇

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

4 數(shù)值分析

4.1 仿真場(chǎng)景

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

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

4.2 仿真結(jié)果分析

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

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

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

5 結(jié) 語

針對(duì)車載自組網(wǎng)VANET的消息傳輸機(jī)制問題，展開分析，并提出了基于分布式的分簇路由機(jī)制DCRM。DCRM以分布式方式對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行簇劃分。每個(gè)簇內(nèi)鄰近車輛間的距離小于門限值，并選擇離源節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)作為簇頭CH。簇頭CH承擔(dān)接連簇與簇間的通信，構(gòu)建了通信的主線。仿真結(jié)果表明，提出的DCRM在吞吐量、數(shù)據(jù)包傳輸率以及端到端傳輸時(shí)延方面的性能良好。將進(jìn)一步研究基于簇的路由機(jī)制，將其拓展至任何一個(gè)先應(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ù)測(cè)的VANET路由算法[J].計(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é)報(bào)，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é)報(bào)（自然科學(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.