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

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

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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

2.1 協(xié)議概述

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

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

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

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

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

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

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

2.2.1 算法描述

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

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

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

2)二分查找。

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

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

next_idi,minhopi=

(1)

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

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

a)dj-di

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

b)di+vi*x

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

c)dj+vi*x

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

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

//x秒后車(chē)i與車(chē)j能通信；

e)minhopj+1

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

在計(jì)算開(kāi)始之前，除能在尾保護(hù)區(qū)間的逗留長(zhǎng)于x時(shí)間的車(chē)初始化minhop=1外，所有車(chē)都初始化為minhop=INF；而所有車(chē)都初始化為next_id=null。

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

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

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

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

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

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 舉例說(shuō)明

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

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

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

表2 車(chē)輛之間的連接的預(yù)測(cè)維持時(shí)間

Tab.2 Predicted maintenance time of connection between vehicles

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖10 傳遞成功比隨車(chē)速變化

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

圖11 平均端到端延遲隨車(chē)速變化

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

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

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

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

4 結(jié)語(yǔ)

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

軟件定義網(wǎng)絡(luò)技術(shù)能夠更好地解決車(chē)載網(wǎng)問(wèn)題，目前有不少學(xué)者在研究如何更好地實(shí)現(xiàn)軟件定義車(chē)載網(wǎng)。下一個(gè)研究目標(biāo)是如何利用軟件定義網(wǎng)絡(luò)技術(shù)實(shí)現(xiàn)車(chē)載網(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] 趙海,田婷婷,樊景超,等.一種分布式車(chē)聯(lián)網(wǎng)多跳信息廣播協(xié)議[J].東北大學(xué)學(xué)報(bào)(自然科學(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ù)測(cè)的機(jī)會(huì)車(chē)載網(wǎng)絡(luò)中繼選擇策略研究[J].軟件學(xué)報(bào),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。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61379157)；廣東省科技計(jì)劃項(xiàng)目(2015B010111001, 2015A010103007)；廣州市科技計(jì)劃項(xiàng)目(201510010068)。

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

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

TP

A