車聯網協助下載傳輸規劃方法

李春雷，劉建航

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

0 引 言

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

為解決上述問題，Nanda等［2］第一次將協助下載方法引入車聯網。這種方法的基本思想是用戶進入AP通信區后發送下載請求，當用戶離開AP通信區，AP根據與用戶車相遇時間，在其通信區間內選擇一組車輛攜帶用戶所需數據。當協助車在盲區內與目標車相遇時，將攜帶的數據傳送給目標車。顯然，這種方法可以延伸AP的通信區域，以便用戶收到更多的數據。

對于多用戶的應用來說，一個關鍵的問題是當多輛協助車和目標車的通信區域重合時，誰將獲取信道？顯然，對于拓撲結構變化頻繁的車聯網來說，信道爭用方法如CDMA／CA協議并不適合作為通信協議，這是由于協助下載中協助車和目標車通信時間較短，信道爭用會占用通信時間，減少吞吐量。

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

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

1 傳輸規劃方法

為了滿足高速車聯網數據傳輸需求，滿足移動節點數據傳輸的特點，首先建立高速車聯網傳輸系統模型，并針對在該模型基礎上建立k－約束路由樹，根據樹中的每個節點傳輸的數據量為其規劃傳輸時間片，在此基礎上提出相應的傳輸規劃算法。在道路上行駛的車輛分為兩類，一類是與目標車同向行駛的，另一類是與目標車對向行駛的。在兩個AP之間 （AP一般被設置在路口或者加油站），對向行駛的車輛一定會相遇，而同向行駛的車輛由于車速的不同，會發生超越目標車或是被目標車超越。如果對向行駛的車輛相遇過程中將數據下載給目標車的過程稱為ODCD （opposite direction cooperative downloading），而 在同向行駛過程中趕超或被趕超時的協助下載過程成為SDCD （same direction cooperative downloading）［10］。高速公路環境下對向行駛的車輛一定會發生ODCD過程，而同向行駛的SDCD過程發生的條件僅當協助車輛趕超目標車或者被趕超時才會發生。

1.1 系統模型

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

隨著目標車和協助車輛不斷移動，車輛i的行駛軌跡為

兩輛車i和j進行通信的條件是其相對距離小于通信半徑R.如果能夠獲取車輛的行駛軌跡，我們可以得到一個n個時間片的拓撲序列用于建立移動通信拓撲 （MCT）。MCT可以被定義為

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

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

因此，每輛車的積累函數為

1.2 建立k－約束路由樹

對于樹結構來說，傳輸沖突分為兩類。一類是樹內沖突，即用戶在同一時刻只能獲取一輛協助車發過來的數據，如果多輛協助車同時發送數據，就會發生傳輸沖突。這意味著子節點不能同時給父節點傳輸數據。相反，父節點向子節點發送數據時則不會產生傳輸沖突。另一類是樹間沖突，即一個節點在與其父節點或者子節點發送和接收數據的過程與其它分支的發送過程產生沖突。

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

我們使用αi作為節點i在移動通信拓撲中的約束級，使用βi作為節點i在樹結構中的約束級，則

當節點被規劃同時傳輸數據時，他們可以選擇不同的信道傳輸數據。信道選擇算法將在1.3中闡述。顯然鏈路數是建立k－約束樹的基本條件。

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

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

具體算法如圖1所示。

圖1 建立k級約束樹算法

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

1.3 傳輸規劃

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

當子節點和父節點同時需要發送數據時，子節點的發送時間片比父節點短，這樣設置保證子節點可在父節點發送數據之前完成數據發送，因此傳輸規劃必須滿足式 （9）

另外一個約束條件是同一個父節點下的子節點不能同時發送數據，即滿足式 （10）

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

圖2 TS－Coop算法

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

2 實驗驗證

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

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

圖3 兩種方法中節點數量對效率的影響

相比較而言，由于對傳輸進行了規劃，參與傳輸的節點數量越少，TS－Coop的傳輸效率越高，隨著節點的增加，盲區中時空資源利用率提高的同時，碰撞概率不斷提高，這導致使用傳輸效率不斷下降。然而，雖然TS－Coop的效率一直處于一個下降的趨勢，但是其效率值始終保持在70%以上，明顯優于DSRelay方法。

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

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

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

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

圖5 使用TS－Coop方法不同車速獲取的數據量

3 結束語

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

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

［2］Trullols－Cruces O，Fiore 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］.科學技術與工程，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］.計算機學報，2011，34（8）：1334－1344.］