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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 協(xié)助車輛選擇

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

圖1 高速公路場(chǎng)景Fig 1 Highway scenario

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

［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)平，等.基于動(dòng)態(tài)時(shí)槽的車聯(lián)網(wǎng)協(xié)助下載方法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(8):1378－1386.

［5］ 陳 振，韓江洪，劉征宇.基于VANET 分簇的車輛碰撞警告信息傳輸［J］.電子測(cè)量與儀器學(xué)報(bào)，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.