車聯(lián)網(wǎng)協(xié)助下載傳輸規(guī)劃方法

李春雷，劉建航

（1.中國石化股份有限公司勝利油田分公司地質(zhì)科學(xué)研究院，山東 東營257000；2.中國石油大學(xué) 計算機(jī)與通信工程學(xué)院，山東 青島266555）

0 引 言

由于路邊接入點(diǎn) （AP）通信范圍有限，車載用戶使用Wi－Fi方式接入互聯(lián)網(wǎng)會導(dǎo)致間歇性連接。雖然Jorg Ott等提出了Disconnection－tolerant的方法在傳輸層保持連接，但仍然沒有從根本上減少延遲，提高用戶下載的數(shù)據(jù)量［1］。

為解決上述問題，Nanda等［2］第一次將協(xié)助下載方法引入車聯(lián)網(wǎng)。這種方法的基本思想是用戶進(jìn)入AP通信區(qū)后發(fā)送下載請求，當(dāng)用戶離開AP通信區(qū)，AP根據(jù)與用戶車相遇時間，在其通信區(qū)間內(nèi)選擇一組車輛攜帶用戶所需數(shù)據(jù)。當(dāng)協(xié)助車在盲區(qū)內(nèi)與目標(biāo)車相遇時，將攜帶的數(shù)據(jù)傳送給目標(biāo)車。顯然，這種方法可以延伸AP的通信區(qū)域，以便用戶收到更多的數(shù)據(jù)。

對于多用戶的應(yīng)用來說，一個關(guān)鍵的問題是當(dāng)多輛協(xié)助車和目標(biāo)車的通信區(qū)域重合時，誰將獲取信道？顯然，對于拓?fù)浣Y(jié)構(gòu)變化頻繁的車聯(lián)網(wǎng)來說，信道爭用方法如CDMA／CA協(xié)議并不適合作為通信協(xié)議，這是由于協(xié)助下載中協(xié)助車和目標(biāo)車通信時間較短，信道爭用會占用通信時間，減少吞吐量。

基于上述原因，本文提出了一種名為TS－Coop的數(shù)據(jù)傳輸規(guī)劃方法。TS－Coop建立了一個k級約束的路由規(guī)劃算法用于定義數(shù)據(jù)量的路由；在此基礎(chǔ)上，定義了一個基于動態(tài)規(guī)劃算法的傳輸規(guī)劃方法。通過分析測試車輛在2011年5月至2012年7月間G15運(yùn)行期間獲取的數(shù)據(jù)集，驗證了使用本文提出的方法可以有效提高系統(tǒng)吞吐量，減少由于頻繁碰撞所致的信道爭用帶來的影響。

相似的研究中［3］提出利用P2P的方式在車聯(lián)網(wǎng)中尋找其它資源進(jìn)行協(xié)助下載；文獻(xiàn) ［4］研究了高速公路環(huán)境下同向協(xié)助下載方法；A.Bal Subramanian等［5］提出了一種支持車內(nèi)用戶使用交互式應(yīng)用程序的方法，其主要工作是利用AP點(diǎn)分布的差異來減少沖突；M.Fiore等［6］提出了針對城市的車聯(lián)網(wǎng)協(xié)助下載方法，該方法通過將車速預(yù)測及其行駛路線和目標(biāo)車相遇時間作為部署AP的依據(jù)來評估不同協(xié)助車選擇算法及數(shù)據(jù)分塊方案；R.Mahajan等［7］的研究成果是針對車聯(lián)網(wǎng)特點(diǎn)提出了一種測量 Wi－Fi連通性的方法，從而決定節(jié)點(diǎn)連接時間；Y.Zhang等［8］車聯(lián)網(wǎng)用戶利用路邊基礎(chǔ)設(shè)施實(shí)現(xiàn)一種上傳和下載方案；DTcoop［9］通過協(xié)助下載的方式減少高速情況下丟包率，解決的是單向的信息廣播分發(fā)問題；DSRelay［10］提出了動態(tài)規(guī)劃DA下載區(qū)域算法。

1 傳輸規(guī)劃方法

為了滿足高速車聯(lián)網(wǎng)數(shù)據(jù)傳輸需求，滿足移動節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)奶攸c(diǎn)，首先建立高速車聯(lián)網(wǎng)傳輸系統(tǒng)模型，并針對在該模型基礎(chǔ)上建立k－約束路由樹，根據(jù)樹中的每個節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量為其規(guī)劃傳輸時間片，在此基礎(chǔ)上提出相應(yīng)的傳輸規(guī)劃算法。在道路上行駛的車輛分為兩類，一類是與目標(biāo)車同向行駛的，另一類是與目標(biāo)車對向行駛的。在兩個AP之間 （AP一般被設(shè)置在路口或者加油站），對向行駛的車輛一定會相遇，而同向行駛的車輛由于車速的不同，會發(fā)生超越目標(biāo)車或是被目標(biāo)車超越。如果對向行駛的車輛相遇過程中將數(shù)據(jù)下載給目標(biāo)車的過程稱為ODCD （opposite direction cooperative downloading），而 在同向行駛過程中趕超或被趕超時的協(xié)助下載過程成為SDCD （same direction cooperative downloading）［10］。高速公路環(huán)境下對向行駛的車輛一定會發(fā)生ODCD過程，而同向行駛的SDCD過程發(fā)生的條件僅當(dāng)協(xié)助車輛趕超目標(biāo)車或者被趕超時才會發(fā)生。

1.1 系統(tǒng)模型

為了清晰的描述該方法，我們首先假定在t時刻車輛i的位置為

隨著目標(biāo)車和協(xié)助車輛不斷移動，車輛i的行駛軌跡為

兩輛車i和j進(jìn)行通信的條件是其相對距離小于通信半徑R.如果能夠獲取車輛的行駛軌跡，我們可以得到一個n個時間片的拓?fù)湫蛄杏糜诮⒁苿油ㄐ磐負(fù)?（MCT）。MCT可以被定義為

式中：V——所有參與通信車輛的集合，L——所有通信鏈路的集合，｛i，j｜i，j∈V｝作為一個通信鏈路，即兩輛車i和j的通信距離小于通信半徑R.T是集合L中時間槽的集合。

在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，車輛的傳輸時間決定了是否會發(fā)生碰撞，用戶是否會收到數(shù)據(jù)。因此，如果我們對每輛車的傳輸時間都進(jìn)行規(guī)劃，那么就可以避免傳輸沖突。對于任一車輛i，我們用Ti作為該輛車傳輸時間的集合，W作為車輛集合與傳輸時間的映射，C為所有用戶的集合，則有

因此，每輛車的積累函數(shù)為

1.2 建立k－約束路由樹

對于樹結(jié)構(gòu)來說，傳輸沖突分為兩類。一類是樹內(nèi)沖突，即用戶在同一時刻只能獲取一輛協(xié)助車發(fā)過來的數(shù)據(jù)，如果多輛協(xié)助車同時發(fā)送數(shù)據(jù)，就會發(fā)生傳輸沖突。這意味著子節(jié)點(diǎn)不能同時給父節(jié)點(diǎn)傳輸數(shù)據(jù)。相反，父節(jié)點(diǎn)向子節(jié)點(diǎn)發(fā)送數(shù)據(jù)時則不會產(chǎn)生傳輸沖突。另一類是樹間沖突，即一個節(jié)點(diǎn)在與其父節(jié)點(diǎn)或者子節(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)的過程與其它分支的發(fā)送過程產(chǎn)生沖突。

為了避免上述兩種沖突，本文提出將每個樹內(nèi)節(jié)點(diǎn)加上一個傳輸約束。每個節(jié)點(diǎn)i在式 （3）中的最大連接數(shù)小于信道數(shù)量。這就保證了節(jié)點(diǎn)在發(fā)送數(shù)據(jù)時可以不與其父節(jié)點(diǎn)和鄰居節(jié)點(diǎn)的傳輸發(fā)生沖突。

我們使用αi作為節(jié)點(diǎn)i在移動通信拓?fù)渲械募s束級，使用βi作為節(jié)點(diǎn)i在樹結(jié)構(gòu)中的約束級，則

當(dāng)節(jié)點(diǎn)被規(guī)劃同時傳輸數(shù)據(jù)時，他們可以選擇不同的信道傳輸數(shù)據(jù)。信道選擇算法將在1.3中闡述。顯然鏈路數(shù)是建立k－約束樹的基本條件。

基于上述分析，本文提出式 （7）的建立約束樹規(guī)則。其中式 （7）中的每個節(jié)點(diǎn)必須滿足式 （6）的約束條件

建立約束樹的算法要保證至少有min｛αi－k，0｝個鄰居節(jié)點(diǎn)能夠作為子節(jié)點(diǎn)。這就保證了每個節(jié)點(diǎn)的鏈路數(shù)小于k。按照式 （4）的條件，一個節(jié)點(diǎn)可以選擇父節(jié)點(diǎn)，也就是集合中擁有最大值k的節(jié)點(diǎn)將被選擇作為父節(jié)點(diǎn)。

具體算法如圖1所示。

圖1 建立k級約束樹算法

首先設(shè)定節(jié)點(diǎn)集合和鏈路結(jié)合都為空，數(shù)據(jù)傳輸?shù)淖罱K用戶作為樹的根節(jié)點(diǎn)加入到節(jié)點(diǎn)的結(jié)合中。另外，對于每個新加入的節(jié)點(diǎn)i，比較其信道數(shù)量k和約束αi。如果k＞αi，任意選擇k－αi個鄰居節(jié)點(diǎn)作為其子節(jié)點(diǎn)。經(jīng)過排序后將選中的k－αi個節(jié)點(diǎn)加入到臨時集合V’中。對于其它未加入的節(jié)點(diǎn)，比較每個節(jié)點(diǎn)和已加入節(jié)點(diǎn)的鏈路數(shù)量，將鏈路數(shù)量小的節(jié)點(diǎn)替換出集合。循環(huán)該過程直到所有的節(jié)點(diǎn)都被計算。

1.3 傳輸規(guī)劃

建立好k級約束的路由樹，本節(jié)介紹在此結(jié)構(gòu)上規(guī)劃各個節(jié)點(diǎn)的傳輸時間。我們假定樹結(jié)構(gòu)為Т，節(jié)點(diǎn)i將要在時刻Т0發(fā)生數(shù)據(jù)di。則用戶j能獲取的數(shù)據(jù)最大值為式 （8）

當(dāng)子節(jié)點(diǎn)和父節(jié)點(diǎn)同時需要發(fā)送數(shù)據(jù)時，子節(jié)點(diǎn)的發(fā)送時間片比父節(jié)點(diǎn)短，這樣設(shè)置保證子節(jié)點(diǎn)可在父節(jié)點(diǎn)發(fā)送數(shù)據(jù)之前完成數(shù)據(jù)發(fā)送，因此傳輸規(guī)劃必須滿足式 （9）

另外一個約束條件是同一個父節(jié)點(diǎn)下的子節(jié)點(diǎn)不能同時發(fā)送數(shù)據(jù)，即滿足式 （10）

基于上述分析，本文提出了基于動態(tài)規(guī)劃算法的傳輸規(guī)劃方法，如圖2所示。

圖2 TS－Coop算法

首先，根據(jù)樹結(jié)構(gòu)中子節(jié)點(diǎn)與父節(jié)點(diǎn)的關(guān)系，將節(jié)點(diǎn)分為不同的層，葉子節(jié)點(diǎn)為第0層，父節(jié)點(diǎn)的層數(shù)為子節(jié)點(diǎn)中最大層數(shù)值加1。然后，計算當(dāng)每個子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的鏈路是可用的前提下的最大傳輸數(shù)量。用D ［i，T］s代表節(jié)點(diǎn)i在T時刻發(fā)送數(shù)據(jù)的最大值。假定節(jié)點(diǎn)i的父節(jié)點(diǎn)為pi，節(jié)點(diǎn)i的子節(jié)點(diǎn)集為Ci＝ ｛c0，c1，c2…ck｝。則傳輸時間相對應(yīng)的傳輸集合為T＝ ｛Tc0，Tc1，Tc2…，Tck｝。

2 實(shí)驗驗證

本文通過仿真實(shí)驗對該方法的性能進(jìn)行評估。車輛行駛數(shù)據(jù)一部分采用中國科學(xué)院電動汽車研發(fā)中心 （上海）在2010年9月～12月在高速公路G15上海段的測試數(shù)據(jù)，另一部分采用數(shù)據(jù)生成器自動生成的。實(shí)驗場景設(shè)定AP通信范圍d＝800m假設(shè)車輛間通信半徑r＝250m。本實(shí)驗將車輛間通信速率設(shè)為3.2Mbps［1］，AP下載速率為2.4 Mbps。用戶車速在90km／h～120km／h隨機(jī)產(chǎn)生，并且符合對數(shù)正態(tài)分布。

首先，我們使用兩種方法TS－Coop與DSRelay［10］比較節(jié)點(diǎn)數(shù)量對傳輸效率的影響。如圖3所示，隨著節(jié)點(diǎn)數(shù)量增加，DSRelay方法的效率不斷提高直到節(jié)點(diǎn)數(shù)量達(dá)到35，這是由于參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)的增加帶來了信道利用率的提高。而當(dāng)盲區(qū)資源達(dá)到飽和后，傳輸效率開始下降。節(jié)點(diǎn)數(shù)量從40增加到50個時，效率值下降到50%。

圖3 兩種方法中節(jié)點(diǎn)數(shù)量對效率的影響

相比較而言，由于對傳輸進(jìn)行了規(guī)劃，參與傳輸?shù)墓?jié)點(diǎn)數(shù)量越少，TS－Coop的傳輸效率越高，隨著節(jié)點(diǎn)的增加，盲區(qū)中時空資源利用率提高的同時，碰撞概率不斷提高，這導(dǎo)致使用傳輸效率不斷下降。然而，雖然TS－Coop的效率一直處于一個下降的趨勢，但是其效率值始終保持在70%以上，明顯優(yōu)于DSRelay方法。

相應(yīng)的，我們使用兩種方法測試了設(shè)置時延長度對效率的影響。圖4展示了測試結(jié)果，使用TS－Coop和DSRelay方法，效率隨時延長度的增加而不斷提高，當(dāng)時延長度小于3ms時，DSRelay的效率要高于TS－Coop。相比而言，當(dāng)時延長度大于4ms時，TS－Coop的增量要明顯高于DSRelay，這是由于建立k級約束路由樹所占用的時間被更低的碰撞率抵消的結(jié)果。延時達(dá)到9ms時，使用TS－Coop方法可將效率值提高到80%，而DSRelay的效率不足60%。

為了驗證使用TS－Coop方法，用戶車速對下載總量的影響，我們分別測試了用戶車速分別在90km／h、120km／h和150km／h時的下載吞吐量。

從圖5顯示的結(jié)果看，車速越快，用戶下載吞吐量越高。用戶車速快意味著用戶會在更短的時間內(nèi)與協(xié)助車相遇，因此可以在ODCD過程中獲取更多的數(shù)據(jù)；然而，車輛運(yùn)行速度快也意味著SDCD過程中更少的車輛能夠趕超用戶車輛，因此該過程獲取的數(shù)據(jù)會減少。協(xié)助車數(shù)量決定建立約束樹的成本與碰撞的發(fā)生率，因此用戶車速越慢獲取的數(shù)據(jù)量越多。

圖4 兩種方法中時延長度對效率的影響

圖5 使用TS－Coop方法不同車速獲取的數(shù)據(jù)量

3 結(jié)束語

為了有效利用高速公路環(huán)境下AP通信盲區(qū)的時空資源，減少傳輸沖突，在保證系統(tǒng)公平性的前提下盡可能提高用戶下載總量。本文針對車聯(lián)網(wǎng)協(xié)助下載方式提出了一種名為TS－Coop的傳輸規(guī)劃方法，該方法根據(jù)鏈路數(shù)量建立k級約束樹；然后根據(jù)每個節(jié)點(diǎn)的傳輸時間和任務(wù)為其規(guī)劃傳輸數(shù)據(jù)，從而避免傳輸沖突。仿真實(shí)驗結(jié)果表明了該方法可以有效地減少用戶獲取數(shù)據(jù)的延時，有效地提高了系統(tǒng)的吞吐量。該方法的提出將為解決車聯(lián)網(wǎng)協(xié)助下載相關(guān)研究提供關(guān)鍵技術(shù)和理論支持。

［1］Ott J，Kutscher D.A disconnection－tolerant transport for drive－thru internet environments ［C］／／Proc of IEEE INFOCOM，2005.

［2］Trullols－Cruces O，F(xiàn)iore M，Barcelo－Ordinas J.Cooperative download in vehicular environments ［J］.IEEE Transactions on Mobile Computing，2012，11 （4）：663－678.

［3］Liu Che－Liang，Wang Chih－Yu，Wei Hung－Yu.Mobile chord：Enhancing P2Papplication performance over vehicular Ad Hoc network ［C］／／Proceedings of IEEE GLOBECOM，2008：241－247.

［4］LIU Jianhang，BI Jingping，XU Peng.A method of cooperative downloading improving AP work efficiency ［J］.Science Technology and Engeering，2012，10 （26）：267－270 （in Chinese）.［劉建航，畢經(jīng)平，徐鵬.高速公路環(huán)境下車聯(lián)網(wǎng)同向協(xié)助下載方法研究 ［J］.科學(xué)技術(shù)與工程，2012，10 （26）：267－270.］

［5］Balasubramanian A，Mahajan R，Venkataramani A，et al.Interactive WiFi connectivity for moving vehicles ［C］／／Proceedings of SIGCOMM，2008：427－438.

［6］Fiore M，Barcelo－Ordinas JM.Cooperative download in urban vehicular networks ［C］／／Proceedings of IEEE MASS，2009：20－29.

［7］Mahajan R，Zahorjan J，Zill B.Understanding WiFi－based connectivity from moving vehicles ［C］／／Proceedings of IMC，2007.

［8］Zhang Y，Zhao J，Cao G.On scheduling vehicle－roadside data access ［C］／／Proceedings of VANET，2007：10－19.

［9］Liang Hao，Zhuang Weihua.DTcoop：Delay tolerant cooperative communications in DTN／WLAN integrated networks［C］／／Proceedings of Vehicular Technology Conference Fall，2010.

［10］LIU Jianhang，SUN Jiangming，BI Jingping，et al.VANET cooperative downloading approach study based on dynamic slot［J］.Tansaction on Computer，2011，34 （8）：1334－1344（in Chinese）.［劉建航，孫江明，畢經(jīng)平，等.基于動態(tài)時槽的車聯(lián)網(wǎng)協(xié)助下載方法研究 ［J］.計算機(jī)學(xué)報，2011，34（8）：1334－1344.］