一種基于分簇的車聯網對向協助下載方法*

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

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

0 引 言

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

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

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

1 基于動態相鄰節點間距的VANET 分簇算法

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

文獻［5］提出了一種基于相鄰間距的分簇算法。該分簇算法規定如果節點v 的前方距離d 內沒有節點，則規定v為頭節點，并把頭節點標志位HeadFlag 設為true。如果節點v 的后方距離d 范圍內沒有節點，則規定v 為尾節點，并把尾節點的標志位TailFlag 設為true。

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

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

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

1.2 基于動態相鄰節點間距的VANET 分簇算法

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

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

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

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

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

車輛分簇完成以后，便進入簇的維護階段。當單個頭節點或尾節點離開簇或者有單個新成員加入簇時，不會對簇結構產生影響，只需要根據簇的形成過程更新相應的頭節點或尾節點，并更新簇成員的鄰居列表信息和簇頭的成員列表信息，而不需要更新簇頭和相鄰間距d。

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

2 基于分簇的VANET 對向協助下載

2.1 協助車輛選擇

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

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

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

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

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

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

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

2.2 協助車輛與目的車輛通信

當分簇的協助車輛進入盲區后，在與目的車輛相遇時，把攜帶的數據傳輸給目的車輛。其傳輸過程如下:

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

2)當目的車輛收到包含自身id 的信標信息時，表明分簇的協助車輛已經在通信范圍內，此時目的車輛一跳范圍內廣播一個連接請求信息，信息內容包括自身的車輛id，速度v，位置loc。

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

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

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

3 網絡仿真

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

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

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

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

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

4 結 論

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

［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］.計算機學報，2011，34(8):1378－1386.

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