楊志偉，陳昊亮，張 波，吳麗娟，吳維剛

(1.仲愷農(nóng)業(yè)工程學(xué)院 計算科學(xué)學(xué)院，廣州 510225； 2.中山大學(xué) 數(shù)據(jù)科學(xué)與計算機學(xué)院，廣州 510006；3.國家電網(wǎng) 萊蕪供電公司，山東 萊蕪 271100)

(*通信作者電子郵箱wuweig@mail.sysu.edu.cn)

軟件定義車聯(lián)網(wǎng)的數(shù)據(jù)轉(zhuǎn)發(fā)機制

楊志偉1，陳昊亮2，張 波3，吳麗娟3，吳維剛2*

(1.仲愷農(nóng)業(yè)工程學(xué)院 計算科學(xué)學(xué)院，廣州 510225； 2.中山大學(xué) 數(shù)據(jù)科學(xué)與計算機學(xué)院，廣州 510006；3.國家電網(wǎng) 萊蕪供電公司，山東 萊蕪 271100)

(*通信作者電子郵箱wuweig@mail.sysu.edu.cn)

針對現(xiàn)有車聯(lián)網(wǎng)(VANET)中數(shù)據(jù)轉(zhuǎn)發(fā)效率低的問題，提出了軟件定義網(wǎng)絡(luò)(SDN)的數(shù)據(jù)轉(zhuǎn)發(fā)機制。首先，設(shè)計了軟件定義車聯(lián)網(wǎng)的分層次網(wǎng)絡(luò)模型，該模型由局部控制器和車輛組成，實現(xiàn)控制與數(shù)據(jù)轉(zhuǎn)發(fā)分離，具有可擴展性、獨行性等特點；其次，設(shè)計了車輛路由轉(zhuǎn)發(fā)機制，該機制采用動態(tài)規(guī)劃和二分搜索的方法，以實現(xiàn)高效的數(shù)據(jù)轉(zhuǎn)發(fā)；最后，通過仿真驗證，對比無線自組網(wǎng)按需平面距離向量路由(AODV)、目的節(jié)點序列距離矢量路由(DSDV)、動態(tài)源路由(DSR)和最優(yōu)鏈路狀態(tài)路由(OLSR)算法，所提的數(shù)據(jù)轉(zhuǎn)發(fā)機制在傳遞成功比上提高大約100%，而端到端延遲時間降低大約20%。實驗結(jié)果表明，軟件定義車聯(lián)網(wǎng)的數(shù)據(jù)轉(zhuǎn)發(fā)機制能夠提高路由轉(zhuǎn)發(fā)效率、減小延遲。

軟件定義網(wǎng)絡(luò)；車聯(lián)網(wǎng)；路由；數(shù)據(jù)轉(zhuǎn)發(fā)；二分搜索

0 引言

近年興起的車載自組織網(wǎng)絡(luò)原是移動自組織網(wǎng)絡(luò)的一個分支，隨著IEEE802.11p[1]、IEEE1609[2]等標(biāo)準(zhǔn)的起草以及逐步確立，車載自組織網(wǎng)絡(luò)逐漸從移動自組織網(wǎng)絡(luò)中獨立出來。車聯(lián)網(wǎng)(Vehicular Ad Hoc Network, VANET)是由車輛與路邊基礎(chǔ)單元組成的車載網(wǎng)絡(luò)，是以車載自組織網(wǎng)絡(luò)為基礎(chǔ)的多跳混合無線網(wǎng)絡(luò)。與其他無線網(wǎng)絡(luò)相比，如移動自組織網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)、無線網(wǎng)狀網(wǎng)絡(luò)等，車聯(lián)網(wǎng)具有網(wǎng)絡(luò)規(guī)模大、網(wǎng)絡(luò)拓?fù)涫芟蕖⒐?jié)點移動可預(yù)測性等特征，因此車聯(lián)網(wǎng)中的路由與轉(zhuǎn)發(fā)是一個難點，如何設(shè)計具備良好的動態(tài)自適應(yīng)性、高可靠性、高可擴展性的路由算法是車聯(lián)網(wǎng)研究的一個重點。

目前常用的移動自組織網(wǎng)絡(luò)路由協(xié)議有最優(yōu)鏈路狀態(tài)路由(Optimized Link State Routing, OLSR)協(xié)議、目的節(jié)點序列距離矢量路由(Destination Sequenced Distance Vector routing, DSDV)協(xié)議、無線自組網(wǎng)按需平面距離向量路由(Ad Hoc On-demand Distance Vector routing, AODV)協(xié)議和動態(tài)源路由(Dynamic Source Routing, DSR)協(xié)議。在OLSR[3]中，節(jié)點是通過定期廣播Hello包互相發(fā)現(xiàn)的，因而運行OLSR算法的節(jié)點并不能馬上知道鏈接的斷開，因此在模擬城市路況的密集路段上OLSR的性能非常不理想[4]。而DSDV[5]采用了Bellman-Ford算法尋路防止出現(xiàn)路由環(huán)，還采用了增量更新的方法更新路由信息，提高了尋路效率并減少了網(wǎng)絡(luò)開銷。然而DSDV并不能及時發(fā)現(xiàn)鏈路狀態(tài)的更新，同樣不適合在動態(tài)性高的車聯(lián)網(wǎng)使用[6]。在AODV[7]中，節(jié)點則是通過動態(tài)維護(hù)一張路由表來實現(xiàn)路由，然而在動態(tài)性高的網(wǎng)絡(luò)上，路由表的信息很快就失效，AODV需經(jīng)常重新找路。DSR則是更加純粹的需求驅(qū)動型路由協(xié)議[8-9]，它采用一種名為“源路由”的路由方式[10]，每個節(jié)點只知道通往目標(biāo)的下一跳是哪個節(jié)點，而不知道整條路經(jīng)的節(jié)點，然而路由存儲在路由緩存上，并會被加在每一個發(fā)送的數(shù)據(jù)包的包頭上。因此DSR的實現(xiàn)、發(fā)送開銷都更大。有不少學(xué)者設(shè)計車聯(lián)網(wǎng)路由中考慮車輛移動速度及位置[11]、概率論統(tǒng)計[12]、特殊車輛節(jié)點等因素[13]，然而都不能滿足車載網(wǎng)高動態(tài)性的需求。

軟件定義網(wǎng)絡(luò)(Software-Defined Network, SDN)是近年來興起的路由技術(shù)，主要應(yīng)用在有線網(wǎng)絡(luò)[14]，以提高其網(wǎng)絡(luò)帶寬的利用率。近幾年來，軟件定義無線網(wǎng)絡(luò)方面的研究逐漸成為熱點[15]，在多跳無線自組織網(wǎng)中，文獻(xiàn)[16]設(shè)計了基于SDN的路邊單元車載云，包含了OpenFlow控制器、云控制層和云資源管理，而數(shù)據(jù)傳輸包括了物理數(shù)據(jù)層面和抽象控制層面。文獻(xiàn)[17]設(shè)計了軟件定義無線網(wǎng)的編程抽象模塊，包括狀態(tài)管理、資源配置、網(wǎng)絡(luò)監(jiān)控和網(wǎng)絡(luò)重配置。而文獻(xiàn)[18]則針對無線融合網(wǎng)絡(luò)中的問題設(shè)計了抗災(zāi)網(wǎng)絡(luò)，該網(wǎng)絡(luò)使用了SDN技術(shù)去自動選擇狀態(tài)好的網(wǎng)絡(luò)連接，然后通過周期性監(jiān)測這些網(wǎng)絡(luò)連接上節(jié)點的網(wǎng)絡(luò)狀態(tài)，確定路由所經(jīng)過的節(jié)點。雖然軟件定義無線網(wǎng)絡(luò)相關(guān)研究不少，然而SDN在車聯(lián)網(wǎng)中應(yīng)用研究不多。

SDN能夠更好地實現(xiàn)網(wǎng)絡(luò)資源的彈性分配和控制，在可擴展性、效率等方面都有明顯的優(yōu)勢，這些技術(shù)優(yōu)勢正符合車載網(wǎng)絡(luò)在節(jié)點移動性、網(wǎng)絡(luò)動態(tài)性、網(wǎng)絡(luò)規(guī)模等方面的特征和需求，因而在車聯(lián)網(wǎng)中引入SDN的思想能夠更好地解決車聯(lián)網(wǎng)目前存在的難點。特別是SDN基于控制器的這種集中式管控思想，可以解決車聯(lián)網(wǎng)無中心、多變化導(dǎo)致的節(jié)點協(xié)同困難。然而SDN主要在有線網(wǎng)絡(luò)中應(yīng)用，其體系結(jié)構(gòu)考慮的是有線鏈接、固定設(shè)備的情況，網(wǎng)絡(luò)拓?fù)浞€(wěn)定。而車聯(lián)網(wǎng)基于車與車(Vehicle-to-Vehicle, V2V)和車與路邊(Vehicle-to-Roadside, V2R)單元通信組成的動態(tài)性強的無線網(wǎng)絡(luò)，拓?fù)鋭討B(tài)變化是一般的SDN未考慮的問題。這是在車輛網(wǎng)中應(yīng)用SDN的主要挑戰(zhàn)，也正是本文工作的主要目標(biāo)。自組織網(wǎng)絡(luò)中采用SDN技術(shù)已經(jīng)有一些工作[15-18],也是在動態(tài)拓?fù)湎逻M(jìn)行SDN實現(xiàn)。

為了滿足車聯(lián)網(wǎng)特性，把每條路段看成一個邏輯鏈路，整個車聯(lián)網(wǎng)看成由多個邏輯鏈路組成的網(wǎng)絡(luò)，而局部控制器負(fù)責(zé)維護(hù)鏈路的穩(wěn)定性。車聯(lián)網(wǎng)雖然網(wǎng)絡(luò)拓?fù)鋭討B(tài)性強，然而在每條路段中，可以選擇出相對穩(wěn)定的車輛，由這些車輛負(fù)責(zé)流數(shù)據(jù)的轉(zhuǎn)發(fā)，局部控制器負(fù)責(zé)這些車輛的選擇策略和維護(hù)，提高數(shù)據(jù)通信的可靠性。

因此，本文提出了軟件定義車聯(lián)網(wǎng)的數(shù)據(jù)轉(zhuǎn)發(fā)機制，本文的主要貢獻(xiàn)包括：1)設(shè)計了軟件定義車聯(lián)網(wǎng)的分層次網(wǎng)絡(luò)模型，該模型由局部控制器和車輛組成，實現(xiàn)控制與數(shù)據(jù)轉(zhuǎn)發(fā)分離，具有可擴展性、獨行性等特點；2)設(shè)計了車輛路由轉(zhuǎn)發(fā)機制，該機制采用動態(tài)規(guī)劃和二分搜索的方法，以實現(xiàn)高效的數(shù)據(jù)轉(zhuǎn)發(fā)；3)通過仿真驗證了本文設(shè)計的機制具有更好的效果。

1 系統(tǒng)模型

要把SDN引用到車聯(lián)網(wǎng)中，首先需要設(shè)計軟件定義車聯(lián)網(wǎng)的網(wǎng)絡(luò)模型，軟件定義車聯(lián)網(wǎng)網(wǎng)絡(luò)模型如圖1所示，具體假設(shè)如下：

1)整個車聯(lián)網(wǎng)分成多個路段，每個路段都有一個局部控制器，局部控制器的通信范圍能夠覆蓋整條路段，不同局部控制器負(fù)責(zé)的區(qū)域相互不重疊。

2)每個路段上有多個車輛，每輛車具有一定的通信范圍，車輛只能和通信范圍內(nèi)的其他車輛進(jìn)行數(shù)據(jù)分發(fā)，而不在通信范圍內(nèi)的車輛只能通過多跳轉(zhuǎn)發(fā)實現(xiàn)數(shù)據(jù)路由。每個車輛知道自身周圍鄰居車輛的ID和位置。

圖1 軟件定義車聯(lián)網(wǎng)的網(wǎng)絡(luò)模型

3)車輛進(jìn)入局部控制器通信范圍內(nèi)，能夠發(fā)現(xiàn)其所在區(qū)域的局部控制器，車輛和局部控制器進(jìn)行通信，車輛和局部控制器之間只能進(jìn)行控制信息通信，局部控制器不能幫車輛進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

4)局部控制器能夠知道其通信范圍內(nèi)每輛車的ID、位置以及運動速度，并動態(tài)維護(hù)一個車輛信息表，該信息表保存當(dāng)前時間內(nèi)位于其控制區(qū)域的車輛基本信息。

5)系統(tǒng)使用IEEE802.11p中指定的控制信道(Control CHannel, CCH)Ch.178發(fā)送路由協(xié)議控制信息，使用IEEE802.11p中指定的六條服務(wù)信道(Service CHannel, SCH)中的一條傳送數(shù)據(jù)信息。

2 軟件定義車聯(lián)網(wǎng)的數(shù)據(jù)轉(zhuǎn)發(fā)算法

2.1 協(xié)議概述

每輛車會定時發(fā)送Hello包給其范圍內(nèi)的局部控制器，報告自己的地理信息，當(dāng)局部控制器收集到來自自己的控制區(qū)域的Hello包后，會將車輛信息加入對應(yīng)控制區(qū)域的車輛信息表中，并根據(jù)車輛信息表的信息以及控制區(qū)域的范圍，返回AckHello包，AckHello內(nèi)包含該車輛的地理信息以及車輛所在的控制區(qū)域的范圍信息。車輛可以根據(jù)這些信息，判斷是否需要再次發(fā)送Hello包，更新控制器所掌握的自己的地理信息，確?？刂破鲗ψ约旱奈恢妙A(yù)測誤差在預(yù)設(shè)的范圍內(nèi)。車輛也可以根據(jù)這些信息，判斷自己是否已經(jīng)脫離了一個控制器的控制，重新定時發(fā)送Hello包直到下一個控制器返回AckHello包。

每個局部控制器為它所控制的控制區(qū)域維護(hù)一個車輛信息表，車輛信息表保存了其控制區(qū)域所有車輛的信息。當(dāng)局部控制器收到來自所在控制區(qū)域的車輛發(fā)來的Hello包時，會更新車輛信息，當(dāng)車輛離開控制區(qū)域時，車輛信息將從車輛信息表中刪除。局部控制器所維護(hù)的信息包括以下幾項：

1)定位信息，包括位置、速度；

2)選路過程中動態(tài)規(guī)劃時所產(chǎn)生的臨時變量，包括下一跳ID以及最小跳數(shù)；

3)車輛的“欽點”結(jié)果，指代這輛車是否被選擇為轉(zhuǎn)發(fā)車；

4)不轉(zhuǎn)發(fā)列表，僅當(dāng)車輛為轉(zhuǎn)發(fā)車時有意義，該轉(zhuǎn)發(fā)車將被要求不轉(zhuǎn)發(fā)在不轉(zhuǎn)發(fā)列表中的車發(fā)來的所有數(shù)據(jù)包，用以防止廣播風(fēng)暴。

2.2 數(shù)據(jù)轉(zhuǎn)發(fā)車輛選擇算法

2.2.1 算法描述

局部控制器根據(jù)其維護(hù)的車輛信息，選擇進(jìn)行信息轉(zhuǎn)發(fā)的車輛，其數(shù)據(jù)轉(zhuǎn)發(fā)車輛選擇算法可分為三個步驟：確定二份查找的搜索區(qū)間，進(jìn)行二分查找，根據(jù)結(jié)果選擇轉(zhuǎn)發(fā)車輛形成轉(zhuǎn)發(fā)鏈。

1)確定二份查找的搜索區(qū)間。

二份查找算法能高效地在區(qū)間中找出符合條件的結(jié)果。為此需要先確定搜索區(qū)間。區(qū)間的下界為0，代表不能建立任何的鏈接。算法的上界是目前有可能選出的最穩(wěn)定的轉(zhuǎn)發(fā)鏈可能維持的最長時間。這個時間由逗留在首保護(hù)區(qū)間最久的車輛的逗留時間確定，因為在這個時間之后，首保護(hù)區(qū)間中原有的車輛已經(jīng)全部離開首保護(hù)區(qū)間，必須重新在首保護(hù)區(qū)間選擇出轉(zhuǎn)發(fā)車，以保證路段之間的通達(dá)性。

2)二分查找。

根據(jù)確定的搜索區(qū)間，計算中值mid，然后計算在當(dāng)前控制區(qū)域內(nèi)是否存在一條能維持mid時間以上的轉(zhuǎn)發(fā)鏈，如果能，則更新區(qū)間下界為中值mid，否則更新區(qū)間上界為中值mid，然后根據(jù)區(qū)間范圍計算新的中值，循環(huán)計算，直到區(qū)間長度小于預(yù)先設(shè)定的σ，結(jié)束二分查找。

為了確定控制區(qū)域內(nèi)是否存在一條能維持x時間以上的轉(zhuǎn)發(fā)鏈，本文采用動態(tài)規(guī)劃的方法為控制區(qū)域內(nèi)的每一輛車計算若作為轉(zhuǎn)發(fā)車時的下一跳ID(next_id)以及最小跳數(shù)(minhop)。轉(zhuǎn)移方程如下：

next_idi,minhopi=

(1)

其中CHL(i,j,x)函數(shù)的計算如下：

vi、vj為車i、車j在當(dāng)前控制區(qū)域的速度，di、dj為車i、車j在當(dāng)前控制區(qū)域的距離。當(dāng)車i、車j與時間x滿足以下關(guān)系時CHL(i,j,x)的值為真，不滿足則為假。

a)dj-di

//當(dāng)前車i與車j能通信；

b)di+vi*x

//x秒后車i仍在當(dāng)前控制區(qū)域；

c)dj+vi*x

//x秒后車j仍在當(dāng)前控制區(qū)域；

d)|di+vi*x-dj+vi*x|

//x秒后車i與車j能通信；

e)minhopj+1

//使用車j作為下一跳點比當(dāng)前的選擇更佳。

在計算開始之前，除能在尾保護(hù)區(qū)間的逗留長于x時間的車初始化minhop=1外，所有車都初始化為minhop=INF；而所有車都初始化為next_id=null。

在對路段中所有車輛完成計算后，若能在首保護(hù)區(qū)間中找到有車輛的minhop

3)根據(jù)結(jié)果選擇轉(zhuǎn)發(fā)車輛。

如果區(qū)間下界仍為0，說明算法無法找到任何的鏈接，返回空的轉(zhuǎn)發(fā)鏈。

如果區(qū)間下界不為0，則說明存在鏈接，依照區(qū)間下界，再次運用上述的動態(tài)規(guī)劃計算控制區(qū)域中每一輛車的轉(zhuǎn)發(fā)信息，然后從首保護(hù)區(qū)間中選擇跳數(shù)最少的，預(yù)期逗留在首保護(hù)區(qū)間最久的車輛作為首輛轉(zhuǎn)發(fā)車，并根據(jù)其下一跳，遞歸選擇車輛生成轉(zhuǎn)發(fā)鏈，直到下一跳為空。

此時便獲得了一條完整的轉(zhuǎn)發(fā)鏈路，數(shù)據(jù)轉(zhuǎn)發(fā)車輛選擇算法偽代碼如下所示。

max_time:=0FOReachCarinThe_First_Section(TFS)DOtime_left_in_TFS:= (LengthOfTFS-PositionOfCar)/VelocityOfCar; IFtime_left_in_TFS>max_timeTHENmax_time:=time_left_in_TFS;L:=0;R:=max_time;

WHILER-L>σDOmid:=(L+R)/2;ALLminhop:=INF;FORi:=the_farthest_car-1 tothe_nearest_carDOFORj:=the_farthest_cartoi+1 DOIFdj-di

ALLminhop:=INF;

FORi:=the_farthest_car-1 tothe_nearest_carDOFORj:=the_farthest_cartoi+1 DOIFdj-di

TheFirstCar:=NIL;

FOReachCarinThe_First_Section(TFS)DOtime_left_in_TFS:= (LengthOfTFS-PositionOfCar)/VelocityOfCar;IF(time_left_in_TFS>L) && (minhopCar

Next:=TheFirstCar;

WHILENext≠NILDOappointmentNext=FORWARDER;Next=next_idNext;

2.2.2 舉例說明

為了方便理解，舉例說明。設(shè)路段長度為600m，通信距離為250m。搜索區(qū)間目標(biāo)長度σ=0.5按照前面的定義，首尾保護(hù)區(qū)間長度應(yīng)該是通信距離的一半，為125 m，但為了簡化例子，本例子設(shè)首尾保護(hù)區(qū)間長度都為200 m。車輛位置及連接關(guān)系如圖2所示。表1則給出了各車的準(zhǔn)確位置、速度以及根據(jù)位置和速度計算得出的車輛離開控制區(qū)域的時間以及車輛離開首保護(hù)區(qū)間的時間。表2則給出了車輛之間的連接的預(yù)測維持時間。

表1 各車的位置、速度以及在區(qū)域中的時間

圖2 各車的位置以及連接關(guān)系

表2 車輛之間的連接的預(yù)測維持時間

Tab.2 Predicted maintenance time of connection between vehicles

車輛1234561—1535．0———2——22．512．5——3———12．515．0—4————12．52．55—————2．56——————

由于在首保護(hù)區(qū)中，只有車1以及車2，其中預(yù)期逗留時間最長的車1在15 s后就會離開首保護(hù)區(qū)，所以這里的二分搜索的上界是15 s，即搜索區(qū)間為[0，15]，那么第一個中值是7.5，那么4 → 6和5 → 6兩條連接就被去掉了，變成如圖3所示，然后進(jìn)行動態(tài)規(guī)劃計算后結(jié)果如圖4所示。

圖3 進(jìn)行第一次二分搜索后的連接關(guān)系

圖4 第一次動態(tài)規(guī)劃計算的連接關(guān)系

由于有1 → 3 → 5這個通路連接首尾區(qū)間，而且車1離開首區(qū)間的時間是15 s、車5離開路段的時間是15 s都大于7.5 s，所以有一條可行的轉(zhuǎn)發(fā)鏈，那么就要更新搜索區(qū)間為[7.5，15] s，新的中值為11.25 s。由于在剛才的計算中，余下的連接的持續(xù)時間都大于11.25 s，所以這一回合并沒有去掉任何連接，依然能得到一條可行的轉(zhuǎn)發(fā)鏈，那么再次更新搜索區(qū)間為[11.25，15] s，新的中值為13.125 s。此時2 → 4、3 → 4和4 → 5三條連接就被去掉了，結(jié)果如圖5所示，動態(tài)規(guī)劃計算后的結(jié)果則如圖6所示。

圖5 進(jìn)行第四次二分搜索后的連接關(guān)系

圖6 第四次動態(tài)規(guī)劃計算后的連接關(guān)系

此時1 → 3 → 5這個通路仍然存在，那么即仍有可行轉(zhuǎn)發(fā)鏈，并且由于圖6即第四次二分后余下的所有連接的維持時間都大于等于搜索區(qū)間的上界15 s，所以直到搜索結(jié)束，余下的鏈路都如圖6所示。搜索一直進(jìn)行到區(qū)間為[14.53,15] s，區(qū)間長度小于σ=0.5，搜索結(jié)束。

選出轉(zhuǎn)發(fā)鏈后，控制器要將最新的轉(zhuǎn)發(fā)鏈廣播給鄰近的控制器，以便它們修改轄下車輛的不轉(zhuǎn)發(fā)表。

在最后一次動態(tài)規(guī)劃中，獲得了1 → 3 → 5這條轉(zhuǎn)發(fā)鏈，由于搜索區(qū)間下界是14.53,不為0，所以返回這條轉(zhuǎn)發(fā)鏈。那么現(xiàn)在只要讓車1、車3、車5在接下來的14.53 s中向前轉(zhuǎn)發(fā)數(shù)據(jù)包，就可以形成一條覆蓋全路段的虛擬網(wǎng)線了。

3 仿真結(jié)果及分析

本次模擬采用NS-3::FriisPropagationLossMode信號衰減模，介質(zhì)訪問控制(Media Access Control, MAC)層采用NS-3::NqosWaveMacHelper進(jìn)行配置，設(shè)備采用NS-3::Wifi80211pHelper進(jìn)行配置。SCH選擇IEEE802.11p中的Ch172信道，頻率中心點為5.860 GHz，CCH選擇IEEE802.11p中的Ch178信道，頻率中心點為5.890 GHz。CCH和SCH的信道編碼均為OfdmRate27MbpsBW10MHz。SCH上的設(shè)備的發(fā)射強度為23 dbm(測試通信范圍約為437 m)，CCH上的設(shè)備的發(fā)射強度為31 dbm(測試通信范圍約為1 089 m)。

系統(tǒng)網(wǎng)絡(luò)模型仿真如圖7所示。

實驗中配置了3條道路，道路1從(0，0)通往(1 000，0)，道路2從(1 000，0)通往(1 000，1 000)，道路3從(1 000，1 000)通往(2 000，1 000)。在每條路中間均安放了一個局部控制器，三個局部控制器的通信距離(signal_range)均為400 m。二分搜索算法的σ設(shè)置為0.5。

為了方便地獲取數(shù)據(jù)，在(0，0)安放了一個數(shù)據(jù)源(Source)，在(2 000，1 000)放置了一個數(shù)據(jù)接收終端(Sink)。在AODV、DSDV、DSR和OLSR的模擬中，Source和Sink均被當(dāng)作普通節(jié)點。而在本文設(shè)計的系統(tǒng)中，Source和Sink被當(dāng)作既不是局部控制器(Local Controller, LC)也不是車輛的第三類節(jié)點，只往SCH發(fā)包或監(jiān)聽SCH，不接收、不參與CCH的通信。ODV、DSDV、DSR和OLSR均只使用SCH。Source持續(xù)以500 000 b/s發(fā)送單個大小為512 B的UDP(User Datagram Protocol)數(shù)據(jù)包，當(dāng)運行AODV、DSDV、DSR和OLSR時，發(fā)送目標(biāo)為Sink的地址；當(dāng)運行本協(xié)議時，發(fā)送到廣播地址。

圖7 道路結(jié)構(gòu)及設(shè)備安放

模擬使用的數(shù)據(jù)集由道路交通仿真(Simulation of Urban MObility, SUMO)軟件生成，車流總是從(0，0)開往(2 000，1 000)。本文采用2類共8組數(shù)據(jù)對三個算法進(jìn)行測試。1)車速對照組：5 m/s、10 m/s、15 m/s、20 m/s；2)發(fā)車間隔(車輛密度)對照組：2 s、5 s、10 s、15 s。

1)發(fā)車間隔變化仿真結(jié)果。

圖8是傳遞成功比隨發(fā)車間隔變化結(jié)果，由圖8可知：本協(xié)議的傳遞成功比總是比其他四種分布式算法要高，特別是在車輛密度高時，本協(xié)議的傳遞成功比能達(dá)到0.9；而在車輛密度低，連接不穩(wěn)定時，本協(xié)議算法的傳遞成功比仍是最好的分布式算法(DSDV)的兩倍。

圖8 傳遞成功比隨發(fā)車間隔變化

圖9是平均端到端延遲隨發(fā)車間隔變化結(jié)果。

圖9 平均端到端延遲隨發(fā)車間隔變化

由圖9可以發(fā)現(xiàn)，本協(xié)議在發(fā)車間隔為2 s、5 s、15 s時，平均延遲均為最低，OLSR因在發(fā)車間隔為2 s、5 s時的高密度狀態(tài)下，發(fā)送成功率為0。而在發(fā)車間隔為10 s時，結(jié)合圖8可知，AODV、DSDV、DSR三種協(xié)議的傳遞成功比均不足0.1，而此時本協(xié)議的發(fā)送成功比接近0.2，即在連接不穩(wěn)定時，本協(xié)議雖然會花更長的時間傳遞，但傳遞成功比要比其他協(xié)議要高。

從圖8～9可以看出，傳統(tǒng)協(xié)議(特別是OLSR)在車輛密度過高、或者車輛密度過低(連接不穩(wěn)定)時，性能均會有所下降。同樣的結(jié)果也可以在文獻(xiàn)[19-21]中發(fā)現(xiàn)。這是因為車輛密度高后，傳統(tǒng)協(xié)議需要與更多地相鄰節(jié)點通信交流信息，路由開銷急劇變大。而采用了增量更新信息的DSDV雖然是在高密度環(huán)境下表現(xiàn)最好的，但性能依然無法比肩本協(xié)議。

2)車速變化仿真結(jié)果。

圖10是傳遞成功比隨車速變化結(jié)果，由圖10可以看出，本協(xié)議的傳遞成功比隨車速變化不大，而其他四種協(xié)議在車速變大后，傳遞成功比均出現(xiàn)了下降。在網(wǎng)絡(luò)結(jié)構(gòu)較為穩(wěn)定的車速5 m/s的環(huán)境下，四種對比協(xié)議都得了它們在幾個數(shù)據(jù)點中最好的結(jié)果，但隨著車速上升，網(wǎng)絡(luò)拓?fù)渥兊貌环€(wěn)定，出現(xiàn)了明顯的下降。而本協(xié)議的傳遞成功比一直很穩(wěn)定，遠(yuǎn)高于其他四個協(xié)議。

圖10 傳遞成功比隨車速變化

圖11是平均端到端延遲隨車速的變化結(jié)果。從圖11可以看到，除了本協(xié)議的平均端到端延遲隨著車輛的速度的增加而平穩(wěn)增加外，其他四種協(xié)議均在車速增加后，出現(xiàn)平均端到端延遲下降的情況。這是因為分布式算法在動態(tài)性較高的網(wǎng)絡(luò)環(huán)境中，只能成功傳遞少量的包，更多的包被丟棄了，只有最優(yōu)條件下(如主動式算法(AODV、DSR)恰好在找到路后，鏈路結(jié)構(gòu)未發(fā)生變化時、網(wǎng)絡(luò)質(zhì)量最好的一瞬間所發(fā)出的)的包才能到達(dá)目標(biāo)車輛，所以顯示的平均端到端延遲要比本協(xié)議低。而OLSR在速度為15 m/s以上的環(huán)境下，并不能成功傳遞任何的數(shù)據(jù)包，所以在圖11上顯示平均端到端延遲為0。同樣的結(jié)果也可以在文獻(xiàn)[22]中發(fā)現(xiàn)。

圖11 平均端到端延遲隨車速變化

3)二分搜索循環(huán)次數(shù)。

在模擬的過程中，程序也對LC每次尋路時的二分搜索循環(huán)次數(shù)進(jìn)行了統(tǒng)計(如表3)。二分搜索算法大多在進(jìn)行4到8次的搜索后便得到了結(jié)果，最大值不大于11，均值不大于8?？梢姸炙阉魉惴ㄔ谶@個應(yīng)用中也是十分高效的。

通過以上實驗結(jié)果可以看出，本文設(shè)計的軟件定義車聯(lián)網(wǎng)數(shù)據(jù)轉(zhuǎn)發(fā)機制在傳遞成功比和延遲上都有較大優(yōu)勢，本文設(shè)計的數(shù)據(jù)轉(zhuǎn)發(fā)機制比傳統(tǒng)的自組織網(wǎng)絡(luò)技術(shù)具有更好的效果，在傳遞成功比上提高大約100%，而端到端延遲時間降低大約20%。對比現(xiàn)有的車聯(lián)網(wǎng)路由轉(zhuǎn)發(fā)機制，機會網(wǎng)絡(luò)主要考慮在車聯(lián)網(wǎng)不連通的狀態(tài)，通過車輛的相遇機會完成車輛間的數(shù)據(jù)交換，而動態(tài)路由更多的是由車輛根據(jù)地理位置、速度等信息來選擇路由策略，車輛充當(dāng)車輛選擇和數(shù)據(jù)分發(fā)任務(wù)。車聯(lián)網(wǎng)的節(jié)點動態(tài)性很強，這些技術(shù)也同樣面臨節(jié)點頻繁移動，鏈路不穩(wěn)定等問題。本文設(shè)計的軟件定義車聯(lián)網(wǎng)數(shù)據(jù)轉(zhuǎn)發(fā)機制，使用分層次結(jié)構(gòu)，局部控制器負(fù)責(zé)路由選擇和控制信息發(fā)送，而車輛則只需要負(fù)責(zé)進(jìn)行流數(shù)據(jù)轉(zhuǎn)發(fā)，從而能夠?qū)崿F(xiàn)高效高可擴展高可靠的車聯(lián)網(wǎng)數(shù)據(jù)通信。

表3 二分搜索循環(huán)次數(shù)統(tǒng)計

4 結(jié)語

由于車載網(wǎng)具有高動態(tài)性、網(wǎng)絡(luò)拓?fù)涫芟薜忍卣?，現(xiàn)有的數(shù)據(jù)轉(zhuǎn)發(fā)技術(shù)無法滿足車載網(wǎng)的需求。軟件定義網(wǎng)絡(luò)能夠更好地解決有線網(wǎng)絡(luò)帶寬分配問題，其設(shè)計思想能夠更好地解決車載網(wǎng)問題，因此本文研究如何利用軟件定義網(wǎng)絡(luò)的思想來實現(xiàn)車載網(wǎng)中的數(shù)據(jù)轉(zhuǎn)發(fā)。首先，本文設(shè)計了一個分層次的軟件定義車載網(wǎng)模型，該模型具有可擴展行、獨立性等特征；其次，本文設(shè)計了一個完整的軟件定義車載網(wǎng)中數(shù)據(jù)轉(zhuǎn)發(fā)機制，在該機制中，控制和數(shù)據(jù)轉(zhuǎn)發(fā)獨立，以實現(xiàn)更高效的數(shù)據(jù)轉(zhuǎn)發(fā)；最后，本文使用NS-3進(jìn)行仿真，仿真結(jié)果表明，本文設(shè)計的數(shù)據(jù)轉(zhuǎn)發(fā)比傳統(tǒng)的數(shù)據(jù)轉(zhuǎn)發(fā)技術(shù)效果更優(yōu)。

軟件定義網(wǎng)絡(luò)技術(shù)能夠更好地解決車載網(wǎng)問題，目前有不少學(xué)者在研究如何更好地實現(xiàn)軟件定義車載網(wǎng)。下一個研究目標(biāo)是如何利用軟件定義網(wǎng)絡(luò)技術(shù)實現(xiàn)車載網(wǎng)的帶寬分配。

References)

[1] IEEE.IEEE 802.11p-2010—IEEE standard for information technology—local and metropolitan area networks—specific requirements—part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications amendment 6: wireless access in vehicular environments [S].Piscataway, NJ: IEEE, 2010.

[2] IEEE.IEEE 1609.IEEE Guide for Wireless Access in Vehicular Environments (WAVE)—architecture [S].Piscataway, NJ: IEEE, 2014.

[3] JACQUET P, MüHLETHALER P, CLAUSEN T, et al.Optimized link state routing protocol for Ad Hoc networks [C]// INMIC 2001: Proceedings of 2001 IEEE International Multi Topic Conference.Piscataway, NJ: IEEE, 2001: 62-68.

[4] KU I, LU Y, GERLA M, et al.Towards software-defined VANET: architecture and services [C]// MED-HOC-NET 2014: Proceedings of 2014 13th Annual Mediterranean Ad Hoc Networking Workshop.Piscataway, NJ: IEEE, 2014: 103-110.

[5] PERKINS C E, BHAGWAT P.Highly dynamic Destination-Se-quenced Distance-Vector routing (DSDV) for mobile computers [J].ACM SIGCOMM Computer Communication Review, 1994, 24(4): 234-244.

[6] ADE S A, TIJARE P A.Performance comparison of AODV, DSDV, OLSR and DSR routing protocols in mobile Ad Hoc networks [J].International Journal of Information Technology and Knowledge Management, 2010, 2(2): 545-548.

[7] PERKINS C, BELDING-ROYER E, DAS S.Ad-Hoc on-demand distance vector routing [C]// WMCSA’ 99: Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications.Washington, DC: IEEE Computer Society, 1999: 90-100.

[8] JOHNSON D B, MALTZ D A.Dynamic source routing in Ad Hoc wireless networks [J].IEEE Transactions on Mobile Computing, 1994, 353(1): 153-181.

[9] NASIPURI A, CASTANEDA R, DAS S R, et al.Performance of multipath routing for on-demand protocols in mobile Ad Hoc networks [J].Mobile Networks and Applications, 2001, 6(4): 339-349.

[10] PERKINS C E, ROYER E M, DAS S R, et al.Performance comparison of two on-demand routing protocols for Ad Hoc networks [J].IEEE Personal Communications, 2001, 8(1): 16-28.

[11] 趙海,田婷婷,樊景超,等.一種分布式車聯(lián)網(wǎng)多跳信息廣播協(xié)議[J].東北大學(xué)學(xué)報(自然科學(xué)版),2014,35(9):1244-1248.(ZHAO H, TIAN T T, FAN J C, et al.A multi-hop information broadcast protocol in distributed vehicular network [J].Journal of Northeastern University (Natural Science), 2014, 35(9): 1244-1248.)

[12] 賈建斌,陳穎文,徐明.基于預(yù)測的機會車載網(wǎng)絡(luò)中繼選擇策略研究[J].軟件學(xué)報,2015,26(7):1730-1741.(JIA J B, CHEN Y W, XU W.Prediction based relay selection method in opportunistic vehicular networks [J].Journal of Software, 2015, 26(7): 1730-1741.)

[13] LIU N B, LIU M, CHEN G H, et al.The sharing at roadside: Vehicular content distribution using parked vehicles [C]// Proceedings of the 31st Annual IEEE International Conference on Computer Communications: Mini-Conference.Piscataway, NJ: IEEE, 2012: 2641-2645.

[14] JAIN S, KUMAR A, MANDAL S, et al.B4: experience with a globally-deployed software defined WAN [J].ACM SIGCOMM Computer Communication Review, 2013, 43(4): 3-14.

[15] JAGADEESAN N A, KRISHNAMACHARI B.Software-defined networking paradigms in wireless networks: a survey [J].ACM Computing Surveys, 2014, 47(2): 1-11.

[16] MOHAMMAD A S, ALA A F, MOHSEN G.Software-defined networking for RSU clouds in support of the Internet of vehicles [J].IEEE Internet of Things Journal, 2015, 2(2): 135-146.

[17] RIGGIO R, MARINA M K, ZANDER J S, et al.Programming abstractions for software-defined wireless network [J].IEEE Transactions on Network and Service Management, 2015, 12(2): 146-162.

[18] SATO G, UCHIDA N, SHIBATA Y.Resilient disaster network based on software defined cognitive wireless network technology [J].Mobile Information Systems, 2015, 2015: Article ID 308194.

[19] CHOI J M, KO Y B.A performance evaluation for Ad Hoc routing protocols in realistic military scenarios [EB/OL].[2016-05-15].http://uns.ajou.ac.kr/publications/paper/C2004/cic2004.pdf.

[20] HAERRI J, FILALI F, BONNET C.Performance comparison of AODV and OLSR in VANETs urban environments under realistic mobility patterns [EB/OL].[2016-03-20].http://fethifilali.com/publications/papers/filali-medhocnet-2006.pdf.

[21] RAHMAN A H A, ZUKARNAIN Z A.Performance comparison of AODV, DSDV and I-DSDV routing protocols in mobile Ad Hoc networks [J].European Journal of Scientific Research, 2009, 31(4): 566-576.

[22] AL-MAASHRI A, OULD-KHAOUA M.Performance analysis of MANET routing protocols in the presence of self-similar traffic [C]// Proceedings 2006 31st IEEE Conference on Local Computer Networks.Piscataway, NJ: IEEE, 2006: 801-807.

This work is partially supported by the National Natural Science Foundation of China (6137915), the Science and Technology Planning Project of Guangdong Province (2015B010111001, 2015A010103007), the Science and Technology Planning Project of Guangzhou City (201510010068).

YANG Zhiwei, born in 1982, Ph.D.candidate, lecturer.His research interests include vehicular Ad Hoc network, cloud computing.

CHEN Haoliang, born in 1993.His research interests include vehicular Ad Hoc network, network.

ZHANG Bo, born in 1975, senior engineer.His research interests include network and its application.

WU Lijuan, born in 1974, senior engineer.Her research interests include network and its application.

WU Weigang, born in 1976, Ph.D., professor.His research interests include vehicular Ad Hoc network, cloud computing.

Data forwarding mechanism in software-defined vehicular Ad Hoc network

YANG Zhiwei1, CHEN Haoliang2, ZHANG Bo3, WU Lijuan3, WU Weigang2*

(1.CollegeofComputationalScience,ZhongkaiUniversityofAgricultureandEngineering,GuangzhouGuangdong510225,China;2.SchoolofDataandComputerScience,SunYat-senUniversity,GuangzhouGuangdong510006,China;3.LaiwuElectricityCorporation,StateGridCorporationofChina,LaiwuShandong271100,China)

Since the efficiency of data forwarding in Vehicular Ad Hoc Network (VANET) is low, a data forwarding mechanism in VANET based on Software-Defined Network (SDN) was proposed.Firstly, a hierarchical architecture of SDN based VANET was designed.This architecture was consist of local controller and vehicular, it could implement the separation of control and data forwarding, and also could achieve high scalability, reliability and efficiency.Secondly, a new data forwarding mechanism was proposed, which used dynamic programming and binary search.Finally, compared with Ad Hoc On-demand Distance Vector routing (AODV), Destination Sequenced Distance Vector routing (DSDV), Dynamic Source Routing (DSR) and Optimized Link State Routing (OLSR) algorithm, the proposed algorithm could improve packet delivery fraction and end-to-end delay.Therein, the average increase of packet delivery fraction was about 100%, while the average reduction of end-to-end delay was about 20%.The simulation results show that the data forwarding mechanism in software-defined VANET can effectively improve the packet delivery and reduce the end-to-end delay.

Software-Defined Network (SDN); Vehicular Ad Hoc Network (VANET); routing; data forwarding; binary search

2016-08-02;

2016-08-12。 基金項目:國家自然科學(xué)基金資助項目(61379157)；廣東省科技計劃項目(2015B010111001, 2015A010103007)；廣州市科技計劃項目(201510010068)。

楊志偉(1982—)，男，廣東茂名人，講師，博士研究生，主要研究方向：車聯(lián)網(wǎng)、云計算； 陳昊亮(1993—)，男，廣東肇慶人，主要研究方向：車聯(lián)網(wǎng)、網(wǎng)絡(luò)； 張波(1975—)，男，山東泰安人，高級工程師，主要研究方向：網(wǎng)絡(luò)及應(yīng)用； 吳麗娟(1974—)，女，山東泰安人，高級工程師，主要研究方向：網(wǎng)絡(luò)及應(yīng)用； 吳維剛(1976—)，男，山東泰安人，教授，博士，主要研究方向：車聯(lián)網(wǎng)、云計算。

1001-9081(2017)01-0084-06DOI:10.11772/j.issn.1001-9081.2017.01.0084

TP

A