一種基于分簇的車聯(lián)網(wǎng)對向協(xié)助下載方法*

趙征宇，張建軍，3，劉征宇

(1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥230009;2.合肥工業(yè)大學(xué) 機械與汽車工程學(xué)院，安徽 合肥230009;3.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心，安徽 合肥230009)

0 引 言

車聯(lián)網(wǎng)(vehicular Ad Hoc networks，VANET)環(huán)境下高速公路上的車輛可以通過路邊AP 接入點接入互聯(lián)網(wǎng)，由于在高速公路環(huán)境下，路邊的AP 站點非常少，分布稀疏，一般設(shè)立在加油站或者服務(wù)區(qū)。然而汽車的行駛速度快，AP 的通信范圍相對較小，導(dǎo)致汽車在AP 通信區(qū)域內(nèi)的時間較短，而在相鄰兩個AP 之間，AP 通信范圍以外的盲區(qū)(dead zone，DZ)行駛時間較長。當(dāng)汽車節(jié)點在一個AP 區(qū)域不能完成下載任務(wù)時，只能等待較長的時間，車輛進(jìn)入下一個AP 后，才能接著下載，因此，在高速公路上用戶使用網(wǎng)絡(luò)的延遲將非常的大。

為了解決等待延遲時間較長問題，國內(nèi)外研究學(xué)者們提出了許多協(xié)助下載方法。文獻(xiàn)［1］提出的SPAWN 協(xié)議采用結(jié)合位置感知的流言傳播機制，其主要適合P2P 場景下車輛都下載同一資源。文獻(xiàn)［2］提出了高速公路場景下的協(xié)助下載方法，同向協(xié)助下載時車輛的利用率較低，對向協(xié)助下載時沒有提出確切的數(shù)據(jù)攜帶算法。文獻(xiàn)［3］提出了一種高速公路下基于安全的協(xié)助下載方法，該方法主要考慮車輛從AP 獲取資源的安全性。文獻(xiàn)［4］提出了基于動態(tài)時槽協(xié)助下載方法，該方法采用單個車輛攜帶數(shù)據(jù)一次傳輸?shù)臄?shù)據(jù)較少。

為了有效利用協(xié)助車輛，本文提出了一種分簇算法用于判定車輛的分布情況，然后利用分簇的車輛為用戶協(xié)助下載數(shù)據(jù)。

1 基于動態(tài)相鄰節(jié)點間距的VANET 分簇算法

1.1 基于相鄰節(jié)點間距的VANET 分簇算法的問題

文獻(xiàn)［5］提出了一種基于相鄰間距的分簇算法。該分簇算法規(guī)定如果節(jié)點v 的前方距離d 內(nèi)沒有節(jié)點，則規(guī)定v為頭節(jié)點，并把頭節(jié)點標(biāo)志位HeadFlag 設(shè)為true。如果節(jié)點v 的后方距離d 范圍內(nèi)沒有節(jié)點，則規(guī)定v 為尾節(jié)點，并把尾節(jié)點的標(biāo)志位TailFlag 設(shè)為true。

每輛車輛周期性地廣播信標(biāo)信息，當(dāng)節(jié)點v 收到節(jié)點u 的信標(biāo)信息，節(jié)點v 將節(jié)點u 加入到自己的鄰居列表并計算節(jié)點之間的距離|d(v，u)|，如果|d(v，u)|＜d，則表明二者在同一個簇內(nèi)，更改相應(yīng)的標(biāo)志位。如果|d(v，u)|＞d，則表明二者已不在同一個簇，根據(jù)v 和u 的前后關(guān)系更改相應(yīng)的標(biāo)志位。

每個節(jié)點v 檢查自己的標(biāo)志位HeadFlag 和TailFlag，如果HeadFlag 為true，則v 為頭節(jié)點;如果TailFlag 為true，則v 為尾節(jié)點。一對頭尾節(jié)點確定了一個基于相鄰節(jié)點間距d 的分簇。

由于車輛的一跳通信距離遠(yuǎn)遠(yuǎn)大于公路的路寬，故VANET 可看成線性網(wǎng)絡(luò)結(jié)構(gòu)?；谙噜徆?jié)點間距的分簇算法很好地利用了此網(wǎng)絡(luò)特性，但是此算法沒有考慮到車流量對分簇算法的影響。在高速公路環(huán)境下，VANET 的拓?fù)浣Y(jié)構(gòu)和車輛的密度都是具有很高的變化率。如果還是采用固定的間距d 來分簇，當(dāng)車輛密度變得很高時，同一個簇所包含的車輛也會變得很多。如果一個簇中的車輛過多，那么，簇中車輛競爭信道的幾率將會大大提高，網(wǎng)絡(luò)延時將會變得嚴(yán)重，從而影響整個網(wǎng)絡(luò)的性能;當(dāng)車輛密度變得很低時，同一個簇中的車輛數(shù)目將會降低，從而導(dǎo)致總的分簇過多，產(chǎn)生更多的簇頭或孤立車輛(也作為一個特別的簇頭)。簇頭的增多將會導(dǎo)致簇頭所包含的路由表項增加，增加了網(wǎng)絡(luò)的負(fù)擔(dān)。為此，本文提出了一種基于動態(tài)相鄰節(jié)點間距的分簇算法，根據(jù)車輛的密度動態(tài)地調(diào)整間距d，使簇保持一個合適的大小。

1.2 基于動態(tài)相鄰節(jié)點間距的VANET 分簇算法

車輛在道路上行駛，必須保持一個安全距離。所以，相鄰節(jié)點距離d 的最小值dmin必須不小于車輛行駛的安全距離DL。為了讓車輛節(jié)點能夠根據(jù)一跳范圍內(nèi)的鄰居節(jié)點位置信息就能判斷出自己是否為頭尾節(jié)點，故相鄰節(jié)點距離d 的最大值dmax必須小于節(jié)點的通信半徑R。

當(dāng)車流量非常大時相鄰節(jié)點距離隨著車輛密度的增大而線性地減小，d 的實際值可按下式計算

其中，K 為車輛密度，dN和dc分別為新的鄰居相鄰間距和當(dāng)前相鄰距離，由文獻(xiàn)［6］可知當(dāng)K∈［0.8，1.0］時車流量是屬于大的范疇，式(1)也是在K∈［0.8，1.0］內(nèi)有效。當(dāng)車流量不大，即K∈［0，0.8］時，隨著車流量的減小相鄰節(jié)點距離指數(shù)級增大

由于相鄰節(jié)點距離在K=0.8 時是連續(xù)的，故將K=0.8分別帶入式(1)和式(3)可求得

車輛首先根據(jù)當(dāng)前的車輛密度計算出當(dāng)前合適的相鄰間距d，然后運用得到的d 采用相鄰節(jié)點間距的VANET 分簇算法找到一對頭尾節(jié)點形成一個簇，每個節(jié)點根據(jù)自己的鄰居節(jié)點列表信息運用文獻(xiàn)［7］中的簇頭選擇算法選擇簇頭。

車輛分簇完成以后，便進(jìn)入簇的維護階段。當(dāng)單個頭節(jié)點或尾節(jié)點離開簇或者有單個新成員加入簇時，不會對簇結(jié)構(gòu)產(chǎn)生影響，只需要根據(jù)簇的形成過程更新相應(yīng)的頭節(jié)點或尾節(jié)點，并更新簇成員的鄰居列表信息和簇頭的成員列表信息，而不需要更新簇頭和相鄰間距d。

當(dāng)兩簇車輛合并或者一個簇分裂時，簇的大小和結(jié)構(gòu)發(fā)生較大的改變，根據(jù)簇的形成過程，一對新的頭節(jié)點和尾節(jié)點維護了一個新的簇，簇成員更新自己的鄰居列表，根據(jù)鄰居列表信息運用文獻(xiàn)［7］更新新的簇頭，簇頭根據(jù)當(dāng)前的車流量，重新計算出當(dāng)前的相鄰間距d，并廣播給簇成員。簇成員收到廣播后，更新自己的相鄰間距d。

2 基于分簇的VANET 對向協(xié)助下載

2.1 協(xié)助車輛選擇

汽車在高速路上行駛?cè)鐖D1 所示，可從路邊單元APk下載數(shù)據(jù)，由于高速路上的AP 數(shù)量有限，不能覆蓋全路段，導(dǎo)致車輛與AP 之間間斷性連接。當(dāng)車輛進(jìn)入AP 通信范圍后，注冊自己車輛的idn，簇頭車輛pidn，速度vn和進(jìn)入此AP 的時間tn。AP 維護一個其通信范圍內(nèi)的所有汽車的速度和注冊時間列表List={(id0，pid0，v0，t0)…(idn，pidn，vn，tn)}。當(dāng)車輛在一個AP 區(qū)域內(nèi)提出下載請求，而在AP區(qū)域內(nèi)不能完成全部下載任務(wù)時，AP 通知沿著車輛行駛的方向的下一個AP，有車輛提出協(xié)助下載請求。

圖1 高速公路場景Fig 1 Highway scenario

根據(jù)高速公路的特性，通常情況下，相鄰AP 之間的車輛在對向行駛的過程中都會相遇，所以，本文考慮用對向行駛的一簇車輛作為協(xié)助車輛為單個目的車輛提供協(xié)助服務(wù)。當(dāng)下一個AP 收到協(xié)助下載請求時，計算每一簇車輛與用戶相遇的時間和結(jié)束時間，按照與用戶相遇的時間順序選取合適的簇，放入集合M={(pid0，v0，t0，B0，E0，T0)…(pidn，vn，tn，Bn，En，Tn)}，其中，Bn為相遇的時間，En為傳輸結(jié)束的時間，Tn為選車的時間。Bn和En可由式(5)和式(6)取得

其中，D 為盲區(qū)的長度，L 為AP 的通信范圍，n 為簇中的車輛數(shù)，vs和ts分別為目的車輛的速度和向AP 注冊的時間，vn和tn分別為簇頭的速度和簇頭向AP 注冊的時間由于分簇車輛的簇比較穩(wěn)定，而簇頭車輛的速度變化率更小，本文選取簇頭車輛的速度作為整個簇的速度。

為了防止選取的簇與簇之間在為目的車輛傳輸數(shù)據(jù)時重疊，因此，下一個協(xié)助簇車輛的傳輸開始時間必須晚于當(dāng)前協(xié)助簇車輛的傳輸結(jié)束時間，假設(shè)當(dāng)前的簇為m0=(pid0，v0，t0，B0，E0，T0)，則下一個簇mx=(pidx，vx，tx，Bx，Ex，Tx)必須要使選取的車輛滿足式(7)

為了保證協(xié)助下載全在盲區(qū)進(jìn)行，防止車輛在進(jìn)入AP區(qū)域后仍然有車輛為其提供下載任務(wù)而導(dǎo)致與從AP 的下載沖突，則被選中的最后一個簇必須滿足式(8)

根據(jù)簇的大小，AP 為不同的備選協(xié)助簇分配不同大小的數(shù)據(jù)，為了保證每簇車攜帶的數(shù)據(jù)量能夠在車輛相遇時傳完，則每簇車攜帶的數(shù)據(jù)量必須滿足下式

2.2 協(xié)助車輛與目的車輛通信

當(dāng)分簇的協(xié)助車輛進(jìn)入盲區(qū)后，在與目的車輛相遇時，把攜帶的數(shù)據(jù)傳輸給目的車輛。其傳輸過程如下:

1)簇成員定時發(fā)送信標(biāo)信息，為了能使目的車輛在和簇的通信范圍內(nèi)都能收到信標(biāo)信息，簇成員同時發(fā)送相同的信標(biāo)信息。信標(biāo)內(nèi)容包括簇頭的pid，簇頭車輛的速度v，車輛的位置loc，以及攜帶數(shù)據(jù)的目的車輛的id。

2)當(dāng)目的車輛收到包含自身id 的信標(biāo)信息時，表明分簇的協(xié)助車輛已經(jīng)在通信范圍內(nèi)，此時目的車輛一跳范圍內(nèi)廣播一個連接請求信息，信息內(nèi)容包括自身的車輛id，速度v，位置loc。

3)當(dāng)簇中車輛收到連接請求信息且包含的車輛id 與簇所攜帶數(shù)據(jù)的目的車輛id 相同時，簇中收到連接請求廣播的每個車輛分別計算各自與目的車輛的的通信帶寬wi和絕對距離Disi，如下式

其中，Data 為步驟(1)中簇成員廣播的信標(biāo)長度和步驟(2)中目的車輛廣播的連接請求信息長度的和，ti為簇成員收到連接請求的時間，t 為簇成員發(fā)送信標(biāo)的時間，loci為簇成員的位置，locs為目的車輛的位置。

簇頭節(jié)點選取wi值最大的節(jié)點作為網(wǎng)關(guān)節(jié)點，簇中攜帶的數(shù)據(jù)通過網(wǎng)關(guān)節(jié)點傳遞給目的車輛，當(dāng)簇中有兩個wi值相同，并且都是最大值時，選取Disi值較小的車輛作為網(wǎng)關(guān)節(jié)點。如果wi值和Disi值均相等時，考慮到車輛的相對運動，故選取行駛方向上的后車和靠近尾節(jié)點的車輛作為網(wǎng)關(guān)節(jié)點。

3 網(wǎng)絡(luò)仿真

本節(jié)通過NS2 仿真將本文提出的基于分簇的VANET對向協(xié)助下載方法和文獻(xiàn)［4］中提出的對向行駛車輛協(xié)助下載(ODCD)方法以及不使用協(xié)助下載方法進(jìn)行性能比較。假設(shè)高速公路上AP 站點的通信范圍為800 m，兩個相鄰AP 間距8 km，和高速公路上一般AP 均設(shè)置在加油站或服務(wù)區(qū)的實際情況相符合。車輛的通信半徑為250 m，AP區(qū)域車輛的下載速率設(shè)為150 kB/s，對向車輛協(xié)助下載速率設(shè)為50 kB/s，車速在90 ～150 km/h 之間隨機產(chǎn)生，在車速變化上，假定車速變化的概率為p，變化的范圍為90 ～150 km/h 之間，并且符合對數(shù)正態(tài)分布，假定用戶車速為90 km/h。

圖2 比較了在車速保持不變，車流在高速公路上服從泊松分布時，不采用協(xié)助下載方法、對向協(xié)助下載方法和分簇的對向協(xié)助下載方法的吞吐量情況。由圖2 可知，在0 ～30 s 內(nèi)車輛在AP 的通信范圍內(nèi)，車輛以150 kB/s 的速率下載數(shù)據(jù);30 s 以后車輛離開AP 的通信范圍，在不采用協(xié)助下載的情況下，車輛需要等待300 s 左右，等車輛到達(dá)下一個AP 區(qū)域才可以下載數(shù)據(jù)，延遲較大。在采用對向協(xié)助下載方法或者分簇協(xié)助下載方法情況下，車輛經(jīng)過100 s 左后就可以接收到協(xié)助車輛攜帶的數(shù)據(jù)。采用對向協(xié)助下載方法，在盲區(qū)用戶可從協(xié)助車輛上下載到7 MB 的數(shù)據(jù)，而采用分簇的協(xié)助下載方法，可以下載10 MB 的數(shù)據(jù)，該方法的吞吐量高于對向協(xié)助下載方法。顯然，采用分簇的協(xié)助下載方式提高了車輛下載的吞吐量，減少了延遲。

圖2 三種方法吞吐量比較Fig 2 Throughput comparison of three methods

為了比較分簇協(xié)助下載方法在下載實際文件時的延遲(delay，D)和平均帶寬(average bandwidth，AB)，分別使用三種方法下載長度為8.1，27，55.3 MB 的文件。由表1 可知，在不采用協(xié)助下載的情況下，隨著文件長度的增加平均帶寬逐漸減少，并且平均帶寬水平非常低。而使用對向協(xié)助下載方法和分簇協(xié)助下載方法時，隨著文件長度的增加，平均帶寬逐漸增大。當(dāng)下載大于27 MB 文件時，采用分簇協(xié)助下載方法的平均帶寬在48.3 kB/s 以上，明顯高于對向協(xié)助下載方法的39.5 kB/s 和不采用協(xié)助下載方法的15.2 kB/s，這是由于采用分簇協(xié)助下載的方法利用了比對向協(xié)助下載方法更多的車輛，因此，采用分簇的對向協(xié)助下載方法性能優(yōu)于對向協(xié)助下載方法。

表1 下載不同大小文件的延遲和平均帶寬Tab 1 Delay and average bandwidth of downloading file of different size

4 結(jié) 論

為了充分利用車輛在行駛過程中的分塊特性，本文提出了一種基于分簇的協(xié)助下載方法，利用該方法可以使更多的車輛參與協(xié)助下載，有效地提高了用戶下載數(shù)據(jù)的吞吐量，降低了用戶下載數(shù)據(jù)的延遲。對提出的方法進(jìn)行仿真實驗，驗證了其有效性。由于環(huán)境設(shè)定在高速公路上，速度的變化率相對較低，因此，忽略了車速變化對方法的影響。另外，該方法只適合一簇車輛為單個目的車輛協(xié)助下載，這是下一步工作需要考慮的問題。

［1］ Nandan A，Das S，Pau G，et al.Cooperative downloading in vehicular Ad－Hoc wireless network［C］∥International Conference on Wireless on Demand Network Systems and Services，St Moritz，Switzerland，2005:32－41.

［2］ Trulhils－Cruces O，Morillo－Pozo J，Barcelo J M，et al.A cooperative vehicular network framework［C］∥IEEE ICC’09，Dresden，Germany，2009.

［3］ Hao Yong，Tang Jin，Cheng Yu.Secure cooperative data downloading in vehicular Ad Hoc network［J］.IEEE Journal on Selected Areas in Communications/Supplement，2013，31:523－537.

［4］ 劉建航，孫江明，畢經(jīng)平，等.基于動態(tài)時槽的車聯(lián)網(wǎng)協(xié)助下載方法研究［J］.計算機學(xué)報，2011，34(8):1378－1386.

［5］ 陳 振，韓江洪，劉征宇.基于VANET 分簇的車輛碰撞警告信息傳輸［J］.電子測量與儀器學(xué)報，2013，27(5):396－402.

［6］ Ameneh Daeinabi，Akbar Ghaffar Pour Rahbar，Ahmad Khademzadeh.VWCA:An efficient clustering algorithm in vehicular Ad Hoc networks［J］.Journal of Network and Computer Applications，2011(34):207－222.

［7］ Basagni S.Distributed clustering for Ad Hoc networks［C］∥1999 International Symposium on Parallel Architectures，Algorithms and Networks，ISPAN’99，1999:310－315.