黃 瓊，衛(wèi)新新，唐 倫，唐廷燁，辛贊洋

(1.重慶郵電大學(xué)移動通信技術(shù)重慶市市級重點實驗室 重慶 400065，2.重慶大唐科技股份有限公司 重慶 400700)

0 引言

車載自組織網(wǎng)絡(luò)(vehicle ad hoc networks，VANETs)是一種大規(guī)模網(wǎng)絡(luò)，通常具有車輛節(jié)點移動性強的特點。與ad hoc網(wǎng)絡(luò)不同，車載自組織網(wǎng)絡(luò)具有很多優(yōu)勢，例如，車輛節(jié)點能量的消耗可以不予考慮、車輛可以配備有定位裝置。但是車載自組織網(wǎng)絡(luò)也有一些自身的缺點，例如，由于車輛的高速移動，信息在傳輸過程中容易產(chǎn)生衰落。

車輛之間在進行信息傳遞的時候，如果都采用廣播或者單播，將會引起大量的不必要的開銷和洪泛［1］。分簇的網(wǎng)絡(luò)結(jié)構(gòu)具有良好的擴展性，能夠提供方便的信息管理機制和廣播信息傳輸機制［2］。文獻［3-4］分析表明，Lowest-ID算法和 Highest-Degree算法在分簇的時候，并沒有很好地考慮無線信道的不穩(wěn)定性。在這種情況下所形成的簇結(jié)構(gòu)，并不能夠很好地維護簇的穩(wěn)定性，容易造成嚴(yán)重的數(shù)據(jù)衰落。文獻［5］分析表明，簇頭選舉和簇結(jié)構(gòu)變化時的維護開銷很大。因此，分簇算法要盡量減少簇結(jié)構(gòu)的變化，即減少成員節(jié)點的重關(guān)聯(lián)和簇頭的重新選舉。

在基于分簇算法的基礎(chǔ)上，根據(jù)802.11p協(xié)議的退避機制，可以得出每種接入類型的信息都有自己固定的競爭窗口。在文獻［6］中，提出利用相對速度和相對位置來調(diào)整初始化競爭窗口的值，以達到系統(tǒng)吞吐量的提升。在文獻［7］中，提出根據(jù)碰撞概率來估計網(wǎng)絡(luò)的負載狀況，并動態(tài)調(diào)整競爭窗口，以達到更加有效的共享信道。上述方法在進行競爭窗口調(diào)整的時候，只是動態(tài)地改變了競爭窗口的大小，并不能夠很好地保證緊急消息的及時發(fā)送。

基于上述問題，本文首先針對現(xiàn)有分簇算法穩(wěn)定性不足的問題，提出了一種基于多權(quán)值的分簇算法，其次，進一步對現(xiàn)有802.11p協(xié)議中的退避算法進行改進，以達到減小簇頭廣播消息傳輸時延的效果。

1 基于多權(quán)值的分簇算法

車輛在高速行駛的情況下，為了維護簇的穩(wěn)定性、減小簇的開銷和達到簇頭廣播消息的及時傳輸，本文在進行簇頭選舉的時候，綜合考慮了以下3種因素:①車輛節(jié)點度數(shù);②鏈路剩余時間;③信道的信噪比，并且，各因素的權(quán)重因子可以根據(jù)系統(tǒng)的要求進行動態(tài)的調(diào)整。

1.1 簇的形成

道路上的所有車輛廣播HELLO消息，HELLO消息中包含車輛自身的ID號、速度、自身的位置信息等。車輛節(jié)點n收到其周圍一跳鄰居車輛廣播的HELLO消息之后，計算自己的權(quán)值，下面是權(quán)值計算的具體過程。

1)車輛節(jié)點n確定自己的鄰居車輛節(jié)點數(shù)N，并將其作為車輛節(jié)點n的度數(shù)dn(本文所考慮的鄰居節(jié)點為車輛n周圍的一跳車輛節(jié)點)。

2)對于車輛節(jié)點n，計算其理想度數(shù)與其度數(shù)差值的比值Δv=δ/|dn－δ|，其中，δ定義為理想度數(shù)，表示一個節(jié)點所能處理的最高車輛節(jié)點數(shù)。

3)對于車輛節(jié)點n，計算其與所有鄰居車輛節(jié)點的總鏈路剩余時間Tn=，其中，ti=，表示車輛節(jié)點n與其鄰居車輛節(jié)點i的鏈路剩余時間，其中，vn，vi分別為車輛n和鄰居車輛i當(dāng)前的速度;800 m為車輛的最大通信范圍;dn，i為當(dāng)前車輛n和其鄰居車輛i之間的距離。

5)計算車輛節(jié)點n的綜合權(quán)值，Wv=w1Δv+w2Tn+w3Ψ(n)，其中，w1，w2，w3為系統(tǒng)參數(shù)的權(quán)值因子，并且w1+w2+w3=1。

車輛節(jié)點n在計算完自己的權(quán)值之后，與其周圍鄰居車輛節(jié)點進行權(quán)值的比較，選取具有最大Wv值的車輛作為簇頭，如果Wv相等，則選取具有較小ID的車輛作為簇頭。同時簇頭廣播其狀態(tài)的變化，并以簇頭(初始化化后ID號為1)為核心，按照距離簇頭的遠近，先初始化簇頭后面的車輛，再初始化簇頭前面的車輛。該簇頭的一跳鄰居節(jié)點成為該簇頭的成員節(jié)點，并且簇頭的鄰居節(jié)點不再參與簇頭的選舉。如果其一跳鄰居節(jié)點為空，則其自己成為獨立簇頭。

1.2 簇的維護

車輛在分簇之后，由于車輛在不斷的移動，所以隨時會導(dǎo)致簇的拓撲發(fā)生變化，因此，需要對簇進行必要的維護。在對簇進行維護的時候，通?？紤]以下3種情況。

1)簇形成之后，簇頭會自動維護一個鄰居列表，如果一定周期內(nèi)，簇頭沒有收到其成員節(jié)點發(fā)來的數(shù)據(jù)消息，簇頭自動會將從其鄰居表中刪除。

2)當(dāng)一個簇成員節(jié)點移出當(dāng)前簇的傳輸范圍，其會廣播一個Find-CH消息，F(xiàn)ind-CH消息中包含自身的ID號。如果有簇頭收到Find-CH消息，其將會回復(fù)一個CH-ACK消息，CH-ACK消息中包含自身的ID號和權(quán)值。簇成員節(jié)點選擇具有最大權(quán)值的簇頭作為其新的簇頭。這時，簇成員節(jié)點將會成為這個簇頭的成員節(jié)點。如果簇成員節(jié)點在一定的周期內(nèi)沒有收到來自簇頭的CH-ACK消息，它自己就會成為簇頭節(jié)點。

3)當(dāng)2個簇頭進入彼此的傳輸范圍時，如果其中一個為獨立簇頭，則該獨立簇頭將會成為另外一個簇的成員節(jié)點。如果2個簇頭都為獨立簇頭，則權(quán)值較大的簇頭成為新的簇頭，另外一個簇頭成為其成員節(jié)點。如果2個簇頭都非獨立簇頭，則重新進行分簇。

2 基于分簇算法的廣播協(xié)議

2.1 現(xiàn)有802.11p協(xié)議中的消息分類機制

在VANETs中，為了更加有效地傳輸消息，IEEE標(biāo)準(zhǔn)化組織于2010年7月正式頒布了IEEE 802.11p協(xié)議。在802.11p協(xié)議中，根據(jù)消息的緊急級別和時延的需要，802.11p協(xié)議定義了8個不同級別的用戶優(yōu)先級和4個不同的接入級別，8個不同級別的用戶優(yōu)先級映射到4個不同的接入級別的隊列中。4個不同的接入級別分別是AC_VO，AC_VI，AC_BE和AC_BK，他們使用不同的仲裁幀間間隔(AIFS)，最小競爭窗口(CWmin)和最大競爭窗口(CWmax)［8-9］。如表1和圖1所示。

表1 4類消息的競爭窗口Tab.1 Contention windows of different application categories

圖1 各種IFS之間的關(guān)系Fig.1 Some IFS relationships

從表1和圖1可以看出，傳輸?shù)南⒃骄o急，其優(yōu)先權(quán)越高，其擁有的競爭窗口和AIFS也越小，其信道接入和信息傳輸機會也就越大。例如:AC_VO的接入類型值最高，這也就意味著AC_VO將會取得最高的信道接入和信息傳輸機會。因此，在進行信道接入和信息傳輸時，也將會優(yōu)先對待高優(yōu)先級的接入類型，而不是低優(yōu)先級的接入類型。

2.2 消息的緊急程度

在VANETs中，簇頭往往需要及時地向簇成員廣播緊急消息、路況消息等一系列緊急消息。在現(xiàn)有的802.11p協(xié)議和分簇機制中，雖然簇頭所傳輸?shù)膹V播消息(緊急消息)的優(yōu)先級都比較高，但在高速行駛的公路上，并不能很好地保證廣播消息的及時傳輸。為了保證廣播消息得到及時有效地傳輸，本文在基于多權(quán)值的分簇算法的基礎(chǔ)上，提出了一個反映車輛傳輸信息緊急程度的公式，其具體的定義如下:(1)式中:Ωi為每個車輛所發(fā)消息的緊急程度;i為簇頭傳輸范圍內(nèi)每個車輛的ID號;K為當(dāng)前簇頭傳輸范圍內(nèi)的車輛密度，其計算公式為K=AN/TN，其中，AN為當(dāng)前簇頭傳輸范圍內(nèi)道路上實際車輛的數(shù)目;TN為當(dāng)前簇頭傳輸范圍內(nèi)道路上所能容納的最大車輛數(shù)。例如，當(dāng)前簇頭的傳輸范圍 TR為800 m，同一車道的車輛之間的安全距離為100 m。在雙車道的高速路上，TN=［800/100］×2=16，AN的值是簇頭通過獲取其傳輸范圍車輛的信息而得到。假設(shè)AN的值為10，則 K=AN/TN=10/16=0.625。公式(1)所反映的每輛車所發(fā)消息的緊急程度如圖2所示。

圖2 車輛消息的緊急程度Fig.2 Emergency level of the vehicle news

由于簇頭的ID號為1，從圖2可以看出，在車輛密度較小的時候，簇頭所傳輸?shù)膹V播消息的緊急程度較大，其它ID號的車輛所發(fā)消息的緊急程度則很小，幾乎為零且相同，說明此公式能夠很好地反應(yīng)廣播消息的緊急程度，有利于廣播消息的及時傳輸。在高速公路上，車輛往往比較稀疏，且簇頭(ID號為1)承擔(dān)著廣播消息的任務(wù)，采用消息緊急程度機制來初始化二進制退避算法的競爭窗口，有利于減小廣播消息的接入時延，從而達到廣播消息快速傳輸?shù)男Ч?/p>

2.3 改進的退避算法

在IEEE 802.11p協(xié)議中，每輛車在發(fā)送消息前，先檢測信道是否空閑，如果信道空閑，則在等待一段時間AIFS［i］后(如果這段時間內(nèi)信道一直是空閑的)就發(fā)送整個數(shù)據(jù)幀，并等待確認。如果檢測到信道忙或者車輛發(fā)送的消息因競爭信道而發(fā)生沖突，則進入退避過程，從 0和初始競爭窗口CW［AC］隨機選擇一個數(shù)作為退避計時器的初始值，即:CW［AC］的初始值設(shè)為 CWmin［AC］，當(dāng)檢測到信道持續(xù)空閑時，每經(jīng)過一個空閑時隙，就將其退避計數(shù)器的值減1，當(dāng)退避計數(shù)器的值為零時，這輛車才開始發(fā)送消息。若在退避計數(shù)器退避的過程中，信道變?yōu)槊Φ臓顟B(tài)，則凍結(jié)退避計數(shù)器，等到信道空閑后，再次啟動退避計數(shù)器，直到其值退避到0，這輛車才開始發(fā)送消息。當(dāng)再次檢測到信道忙或者車輛發(fā)送的消息因競爭信道而發(fā)生沖突，CW［AC］×(1－Ωi)的值就倍乘，即:(CW［AC］×(1－Ωi)+1)×2－1，當(dāng) CW［AC］×(1－Ωi)增加到 CWmax［AC］時，就維持CWmax［AC］的值不變，不再增加，直到數(shù)據(jù)被正確接收或者因重傳次數(shù)超過了最大值而被丟棄。當(dāng)消息發(fā)送成功后，競爭窗口恢復(fù)到初始化狀態(tài)—CW［AC］×(1－Ωi)。若多個退避計數(shù)器同時減為0，則高優(yōu)先級消息優(yōu)先接入信道。

3 仿真結(jié)果和性能分析

3.1 仿真模型

本文使用NCTUns 6.0仿真軟件進行仿真。在500 m×500 m一維區(qū)域內(nèi)布置一個單向雙車道(每個車道寬5 m)道路。車輛的速度在(15 m/s，30 m/s)隨機選擇。在道路上，隨機進行車輛的布置，選舉出的簇頭向其鄰居車輛廣播消息，同時其鄰居車輛也向簇頭傳輸消息。車輛節(jié)點的行駛路線在仿真的過程中自動生成。權(quán)值因子w1=0.2，w2=w3=0.4。其具體的仿真參數(shù)設(shè)置如表2所示。為了評估本協(xié)議的性能，在同一仿真場景下仿真5次，對其取平均值。

3.2 仿真結(jié)果

圖3是簇頭廣播消息的吞吐量在2種機制之間的比較。從圖3中可以看出，改進的退避算法能夠在一定程度上提高廣播消息的吞吐量。這主要是由于降低了廣播消息的競爭窗口，減小了其他車輛接入信道的概率所致。

圖4比較了2種機制的廣播消息的傳輸時延情況。從圖4中可以看出，改進的退避算法在車輛密度稀疏的環(huán)境中，能夠明顯地減小廣播消息的傳輸時延，這主要是由于在車輛稀疏的環(huán)境中，廣播消息的緊急級別明顯高于其他消息的緊急級別所致。

表2 仿真參數(shù)設(shè)置Tab.2 Simulation parameters

圖3 廣播消息的吞吐量Fig.3 Throughput of broadcast messages

圖4 廣播消息的時延Fig.4 Delay of broadcast messages

圖5是廣播消息的時隙利用率在2種機制方面的比較，由圖5可見，在車輛密度較高的環(huán)境中，改進的退避算法并沒有太多的優(yōu)勢，主要是因為在車輛密度高的環(huán)境中，信道負載較重，同時由于廣播消息的緊急級別不是很高，所以，隨著車輛密度的增大，廣播消息的時隙利用率就隨之減小。

因此，改進的退避算法在車輛密度稀疏的情況下，能夠有效地進行廣播消息的傳輸，有利于避免交通事故的發(fā)生。

圖5 廣播消息的時隙利用率Fig.5 Slot utilization of broadcast messages

4 結(jié)束語

本文所提出的簇機制，綜合考慮了車輛節(jié)點度數(shù)、鏈路剩余時間和信道的信噪比等因素，使得對簇頭的選取更為合理，能夠在最大的程度上提升簇的穩(wěn)定性，減小簇維護的開銷。基于此簇機制的改進的退避算法，能夠進一步減小廣播消息的傳輸時延。通過最后的仿真說明，基于此分簇機制的優(yōu)化的退避算法，能夠有效地減小廣播消息的傳輸時延、提高廣播消息的吞吐量和時隙利用率。但改進的退避算法，在信道接入方面，會對其他的車輛節(jié)點產(chǎn)生影響，以至影響其他車輛節(jié)點的公平性和傳輸效率。

［1］YUJI K，SASASE I.A stable clustering scheme by prediction of the staying time in a cluster for mobile Ad hoc networks［C］//IEEE.Asia-Pacific Conference on Communication(APCC).Tokyo:IEEE Press，2008:1-5.

［2］DROR E，AVIN C，LOTKER Z.Fast randomized algorithm for hierarchical clustering in Vehicular Ad-Hoc Networks［C］//IEEE.The 10th IFIP Annual Mediterranean.Sicily:IEEE Press，2011:1-8.

［3］MEHTA S，SHARMA P，KOTECHA K.A survey on various cluster head election algorithms for MANET［C］//IEEE.Nirma University International Conference on Engineering(NUiCONE).Gujarat:IEEE Press，2011:1-6.

［4］AKBARI A，KHOSROZADEH A，LASEMI N.Clustering algorithms in mobile ad hoc networks［C］//IEEE.Fourth International Conference on Computer Sciences and Convergence Information Technology(ICCIT).Seoul:IEEE Press，2009:1509-1513.

［5］NI Minming，ZHONG Zhangdui，WU Hao，et al.A new stable clustering scheme forhighly mobile ad hoc networks［C］//IEEE. Wireless Communications and Networking Conference(WCNC).Sydney:IEEE Press，2010:1-6.

［6］ALASMARY W，ZHUANG Weihua.The Mobility impact in IEEE 802.11p Infrastructureless vehicular networks［C］//IEEE.Vehicular Technology Conference(VTC).Ottawa:IEEE Press，2010:1-5.

［7］ROMDHANI L，NI Qiang，TURLETTI T.Adaptive EDCF:enhanced service differentiation for IEEE 802.11 wireless ad-hoc networks［C］//IEEE.Wireless Communications and Networking Conference(WCNC).New Orleans:IEEE Press，2003:1373-1378.

［8］IEEE Std 1609.11-2010，IEEE Standard for wireless access in vehicular environments(WAVE)-over-the-air electronic payment data exchange protocol for intelligent transportation systems(ITS)［S］.2011:1-62

［9］WANG Y，AHMED A，KRISHNAMACHARI B，et al.IEEE 802.11p performance evaluation and protocol enhancement［C］//IEEE.IEEE International Conference on Vehicular Electronics and Safety(ICVES).Columbus:IEEE Press，2008:317-322.