陳秉試

（廈門海洋職業(yè)技術(shù)學(xué)院，福建 廈門 361012）

0 引 言

車聯(lián)網(wǎng)可實(shí)現(xiàn)車輛與車輛、人、路等多種網(wǎng)絡(luò)實(shí)體之間的聯(lián)系，提供更加安全、豐富、智能以及舒適的駕駛環(huán)境與服務(wù)，具有廣闊的市場(chǎng)前景[1-2]。但是，傳統(tǒng)基于TCP/IP的網(wǎng)絡(luò)架構(gòu)在車輛拓?fù)涓叨葎?dòng)態(tài)的情況下，不利于數(shù)據(jù)資源獲取和移動(dòng)節(jié)點(diǎn)管理。車載信息中心網(wǎng)絡(luò)（Vehicular Information Centric Network，VICN）中采用緩存機(jī)制將數(shù)據(jù)內(nèi)容放置于節(jié)點(diǎn)，緩存節(jié)點(diǎn)收到請(qǐng)求包后可以完成響應(yīng)，將響應(yīng)包通過(guò)路由發(fā)送給請(qǐng)求節(jié)點(diǎn)，降低了請(qǐng)求-響應(yīng)時(shí)延，更加適用于車聯(lián)網(wǎng)中移動(dòng)節(jié)點(diǎn)的場(chǎng)景[3-5]。

近幾年，人們?cè)跀?shù)據(jù)緩存與路由算法方面取得了諸多研究成果。文獻(xiàn)[6]針對(duì)節(jié)點(diǎn)具有移動(dòng)性的機(jī)會(huì)網(wǎng)絡(luò)中的路由傳輸效率問(wèn)題，綜合考慮節(jié)點(diǎn)間鏈路持續(xù)時(shí)間和剩余緩存等因素，提出了改進(jìn)的ProPhet路由算法，提高了消息傳遞成功率，降低了網(wǎng)絡(luò)能耗。文獻(xiàn)[7]在垂直及水平于請(qǐng)求路徑上結(jié)合緩存策略，提高了緩存利用率。其中，垂直于請(qǐng)求路徑方向上提出了基于最大內(nèi)容活躍因子的路徑緩存策略，評(píng)估請(qǐng)求源的分布；水平方向上采用Hash協(xié)同緩存。路由算法與緩存策略的結(jié)合，增加了用戶在附近獲取數(shù)據(jù)的可能性。文獻(xiàn)[8]利用節(jié)點(diǎn)之間緩存副本的交互，感知鄰居節(jié)點(diǎn)緩存分布情況，從而加快路由效率和減少服務(wù)器負(fù)載。文獻(xiàn)[9]針對(duì)ICN場(chǎng)景提出了啟發(fā)式路由機(jī)制，利用回溯條件優(yōu)化興趣包轉(zhuǎn)發(fā)接口，降低了網(wǎng)絡(luò)阻塞率，并利用鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息庫(kù)提高了緩存命中率。文獻(xiàn)[10]提出基于位置和定向泛洪的車聯(lián)網(wǎng)區(qū)域路由協(xié)議，根據(jù)節(jié)點(diǎn)運(yùn)動(dòng)位置關(guān)系降低路由發(fā)現(xiàn)頻率。非目的節(jié)點(diǎn)可直接應(yīng)答以加快路由發(fā)現(xiàn)，而節(jié)點(diǎn)的定向區(qū)域傳輸進(jìn)一步控制開銷。文獻(xiàn)[11]提出了基于時(shí)隙的流片裝箱算法（Flowlet-binned Algorithm based on Timeslot，F(xiàn)LAT），通過(guò)鏈路狀態(tài)信息優(yōu)化傳輸時(shí)隙分配，利用數(shù)據(jù)中心的冗余鏈路實(shí)現(xiàn)流量均衡，從而降低了丟包率并提升了吞吐量。文獻(xiàn)[12]將位置重要性、內(nèi)容時(shí)效性和興趣源距離作為考慮因素，優(yōu)化選擇緩存位置，并建模預(yù)測(cè)內(nèi)容流行度變化，提出基于ICN的協(xié)作緩存和路由機(jī)制，提升了緩存命中率，減少了平均路由跳數(shù)。文獻(xiàn)[13]將緩存放置策略與路由算法相結(jié)合，提出協(xié)作緩存路由機(jī)制，利用包標(biāo)簽評(píng)估沿途最大緩存收益區(qū)域，結(jié)合內(nèi)容全局活躍度和節(jié)點(diǎn)可用緩存空間優(yōu)化緩存放置，并與路由算法結(jié)合增大緩存資源利用率。

目前的研究在多緩存源響應(yīng)時(shí)產(chǎn)生的多路徑路由之間的協(xié)作方面仍有提升空間，并且在城市環(huán)境下的自適應(yīng)性尚不成熟。請(qǐng)求節(jié)點(diǎn)向外廣播請(qǐng)求，并經(jīng)過(guò)多跳傳輸后，將被多個(gè)緩存有所需內(nèi)容的節(jié)點(diǎn)響應(yīng)。此時(shí)，參與響應(yīng)的節(jié)點(diǎn)成為多源路由的源節(jié)點(diǎn)。傳統(tǒng)的響應(yīng)路由算法通過(guò)沿請(qǐng)求路徑返回的方式完成響應(yīng)，但在VICN中，車輛拓?fù)湓诓砺房趧×易兓?，容易發(fā)生請(qǐng)求路徑斷裂，從而導(dǎo)致響應(yīng)失敗。而在非岔路口的道路中，車輛拓?fù)浔３窒鄬?duì)穩(wěn)定，多源同時(shí)響應(yīng)又造成響應(yīng)冗余，浪費(fèi)網(wǎng)絡(luò)資源。因此，需要合理設(shè)計(jì)多源路由算法，優(yōu)化多緩存源的響應(yīng)時(shí)機(jī)，并根據(jù)車輛拓?fù)涮攸c(diǎn)在緩存源之間進(jìn)行協(xié)作，以提高數(shù)據(jù)包到達(dá)率，減少緩存響應(yīng)時(shí)延。

1 系統(tǒng)模型

城市環(huán)境中，岔路口處的拓?fù)渥兓o路由帶來(lái)挑戰(zhàn)，但是紅綠燈以及非岔路口的直行道路也創(chuàng)造了拓?fù)湎鄬?duì)穩(wěn)定的有利條件。

圖1 城市場(chǎng)景中的VICN多路徑路由

如圖1所示，設(shè)車輛節(jié)點(diǎn)通信半徑為R，請(qǐng)求節(jié)點(diǎn)D廣播請(qǐng)求包后，利用多跳轉(zhuǎn)發(fā)完成緩存發(fā)現(xiàn)，S1、S2和S3都緩存著對(duì)應(yīng)內(nèi)容文件，則均發(fā)起響應(yīng)。S1選擇駛向目的節(jié)點(diǎn)D的節(jié)點(diǎn)R1作為中繼節(jié)點(diǎn)；S2和S3都選擇距離目的節(jié)點(diǎn)D最近的節(jié)點(diǎn)R2作為中繼節(jié)點(diǎn)，而R2以一定概率轉(zhuǎn)發(fā)這些響應(yīng)包，而不是均轉(zhuǎn)發(fā)。由于R1和R2在相互的通信范圍內(nèi)均可監(jiān)聽到對(duì)方轉(zhuǎn)發(fā)響應(yīng)包，為避免重復(fù)發(fā)送但又保證一定的數(shù)據(jù)到達(dá)率，轉(zhuǎn)發(fā)概率將受到對(duì)方影響。

2 ICR-MCS機(jī)制

2.1 總體思想及流程

VICN中車輛拓?fù)渥兓诳臻g上呈現(xiàn)不同的動(dòng)態(tài)性，即岔路口處拓?fù)渥兓黠@，非岔路口道路中拓?fù)渥兓^弱。當(dāng)VICN中緩存具有一定的冗余度時(shí)，利用多緩存源均可接受請(qǐng)求并響應(yīng)的特點(diǎn)構(gòu)建多路徑路由，以提升在拓?fù)渥兓^大區(qū)域的數(shù)據(jù)達(dá)到率。VICN中車輛運(yùn)動(dòng)受到道路限速和道路空間約束，其運(yùn)動(dòng)軌跡具有較強(qiáng)的可預(yù)測(cè)性。因此，在多路徑路由轉(zhuǎn)發(fā)過(guò)程中，充分利用車輛的短時(shí)軌跡信息，可提高響應(yīng)包的回傳成功率。為了避免非岔路口道路中多路徑路由退化成泛洪廣播，導(dǎo)致網(wǎng)絡(luò)帶寬浪費(fèi)，利用無(wú)線傳輸?shù)奶烊粡V播特性，車輛節(jié)點(diǎn)通過(guò)監(jiān)聽響應(yīng)包的方式引入中繼抑制機(jī)制。節(jié)點(diǎn)轉(zhuǎn)發(fā)過(guò)程中，將對(duì)周圍節(jié)點(diǎn)在概率意義上產(chǎn)生抑制作用，降低響應(yīng)包重復(fù)傳播的概率，也實(shí)現(xiàn)了多源之間的隱式協(xié)作。

ICR-MCS的流程如圖2所示。當(dāng)節(jié)點(diǎn)收到請(qǐng)求包后，若本地未緩存相應(yīng)的內(nèi)容文件，則記錄該請(qǐng)求，以用于響應(yīng)包轉(zhuǎn)發(fā)和流行度統(tǒng)計(jì)，然后通過(guò)廣播的方式轉(zhuǎn)發(fā)請(qǐng)求包；反之，接收到請(qǐng)求包的節(jié)點(diǎn)將成為緩存源節(jié)點(diǎn)，采用基于運(yùn)動(dòng)預(yù)測(cè)的多路徑路由回傳響應(yīng)包。當(dāng)非目的節(jié)點(diǎn)的中繼節(jié)點(diǎn)收到響應(yīng)包后，將采用基于中繼抑制的方式得到轉(zhuǎn)發(fā)概率，并實(shí)現(xiàn)多緩存源之間的隱式協(xié)作。

圖2 ICR-MCS總體流程

2.2 基于運(yùn)動(dòng)預(yù)測(cè)的多路徑路由

車輛節(jié)點(diǎn)i發(fā)出的請(qǐng)求包中包含請(qǐng)求節(jié)點(diǎn)的ID、短時(shí)軌跡信息、請(qǐng)求內(nèi)容、時(shí)間戳τ0,i以及請(qǐng)求包生存周期Δτ。其中，短時(shí)軌跡信息定義為時(shí)間點(diǎn)(τ0,i+Δτ)時(shí)的位置坐標(biāo)(xi,yi)。參與響應(yīng)的緩存源節(jié)點(diǎn)和中繼節(jié)點(diǎn)可以根據(jù)短時(shí)軌跡信息，結(jié)合電子地圖中道路信息，大致估計(jì)車輛節(jié)點(diǎn)i的位置，然后采用貪婪轉(zhuǎn)發(fā)的方式實(shí)現(xiàn)多源響應(yīng)。

貪婪轉(zhuǎn)發(fā)過(guò)程中，將計(jì)算所有一跳鄰居的轉(zhuǎn)發(fā)價(jià)值，并選擇轉(zhuǎn)發(fā)價(jià)值最高的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)。設(shè)緩存源節(jié)點(diǎn)j的一跳鄰居集合為{πk,j}，其中k=1,2,…,K，K為一跳鄰居個(gè)數(shù)，πk,j表示第k個(gè)一跳鄰居。設(shè)節(jié)點(diǎn)最大通信距離為dmax，且πk,j在接收到待轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)位置坐標(biāo)為(xk,j,yk,j)。與傳統(tǒng)的貪婪轉(zhuǎn)發(fā)不同，候選下一跳節(jié)點(diǎn)將計(jì)算與目的節(jié)點(diǎn)在請(qǐng)求包生存周期結(jié)束時(shí)刻的歐氏距離dk,j。設(shè)緩存空閑率為γk,j，則πk,j的轉(zhuǎn)發(fā)價(jià)值Vk,j為：

其中，ωd及ωγ為權(quán)重因子，且有ωd+ωγ=1。

2.3 基于中繼抑制的多源協(xié)作

多個(gè)緩存源收到請(qǐng)求后，都將開始對(duì)請(qǐng)求進(jìn)行響應(yīng)。在岔路口等拓?fù)渥兓蟮膱?chǎng)景，多源多路徑路由可以提高數(shù)據(jù)包到達(dá)率。但是，在非岔路口的道路中，多源同時(shí)響應(yīng)浪費(fèi)帶寬。因此，通過(guò)中繼抑制機(jī)制自適應(yīng)地在不同場(chǎng)景中完成多緩存源在路由中的隱式協(xié)作。

在中繼抑制機(jī)制中，轉(zhuǎn)發(fā)的數(shù)據(jù)響應(yīng)包q除了數(shù)據(jù)內(nèi)容之外，還包含當(dāng)前轉(zhuǎn)發(fā)節(jié)點(diǎn)f的位置信息(xf, yf)、時(shí)間戳κ0,f以及請(qǐng)求包生存周期Δκ。設(shè)接收到響應(yīng)包的節(jié)點(diǎn)r位于(xr,yr)，計(jì)算該數(shù)據(jù)包對(duì)應(yīng)的中繼抑制因子εq：

其中，nr,q為截止到接收到當(dāng)前數(shù)據(jù)包q時(shí)刻κr,q，在過(guò)去的Δκ時(shí)間段內(nèi)節(jié)點(diǎn)r監(jiān)聽到響應(yīng)包q的次數(shù)，并對(duì)監(jiān)聽到所有響應(yīng)包中最大次數(shù)nr,max歸一化；dr,i為接收節(jié)點(diǎn)r與請(qǐng)求節(jié)點(diǎn)i之間的歐式距離；df,i為轉(zhuǎn)發(fā)節(jié)點(diǎn)f與請(qǐng)求節(jié)點(diǎn)之間的歐氏距離。設(shè)定節(jié)點(diǎn)r轉(zhuǎn)發(fā)響應(yīng)包q的概率為：

即中繼抑制因子值越大，節(jié)點(diǎn)r轉(zhuǎn)發(fā)響應(yīng)包q的概率越低，其中C為常數(shù)。從式（3）可以看出，若監(jiān)聽到相同的響應(yīng)包次數(shù)越多，則轉(zhuǎn)發(fā)的概率越低；接收節(jié)點(diǎn)r距離轉(zhuǎn)發(fā)節(jié)點(diǎn)f越遠(yuǎn)且距離請(qǐng)求節(jié)點(diǎn)i越近，則轉(zhuǎn)發(fā)的概率越高。

3 仿真及分析

3.1 仿真條件

在交通流仿真軟件（Simulation of Urban Mobility，SUMO）中搭建城市道路場(chǎng)景，如圖3所示，再將交通流軌跡數(shù)據(jù)導(dǎo)入NS2中進(jìn)行路由算法性能仿真比較。該網(wǎng)格狀道路模型中，網(wǎng)格邊長(zhǎng)設(shè)置為1 km，道路均為雙向四車道，各岔路口布設(shè)交通燈。節(jié)點(diǎn)通信半徑設(shè)為300 m，車輛最大限速為80 km/h，車輛長(zhǎng)度和車輛間最小安全距離均設(shè)為5 m。所有權(quán)重因子都設(shè)為0.5，中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率中C設(shè)為1。為測(cè)試不同車輛密度下路由性能，車輛密度變化范圍為10～100輛/km/車道，變化步長(zhǎng)為10輛/km/車道。

圖3 城市場(chǎng)景道路模型

本文提出的ICR-MCS將與多源貪婪轉(zhuǎn)發(fā)路由（Multisource Greedy Forwarding Routing，MGFR）算法在數(shù)據(jù)包到達(dá)率和平均請(qǐng)求-響應(yīng)時(shí)延方面比較。多源貪婪轉(zhuǎn)發(fā)算法是指多緩存源在收到請(qǐng)求包之后都將采用位置上的貪婪轉(zhuǎn)發(fā)進(jìn)行響應(yīng)。性能指標(biāo)方面，數(shù)據(jù)包到達(dá)率定義為緩存源響應(yīng)請(qǐng)求時(shí)發(fā)出的響應(yīng)包個(gè)數(shù)中能成功到達(dá)請(qǐng)求節(jié)點(diǎn)的比例。平均請(qǐng)求-響應(yīng)時(shí)延定義為統(tǒng)計(jì)平均下，請(qǐng)求節(jié)點(diǎn)在發(fā)出請(qǐng)求到獲得響應(yīng)包的時(shí)間間隔。

3.2 數(shù)據(jù)包到達(dá)率

數(shù)據(jù)包到達(dá)率反映的是路由傳輸?shù)挠行?。更高的?shù)據(jù)包到達(dá)率說(shuō)明傳輸路徑中可達(dá)路徑更多或者轉(zhuǎn)發(fā)過(guò)程中沖突及擁塞更少。不同節(jié)點(diǎn)密度下ICR-MCS和MGFR的數(shù)據(jù)包到達(dá)率性能如圖4所示。

圖4 不同節(jié)點(diǎn)密度下的數(shù)據(jù)包到達(dá)率

從圖4可以看出，隨著節(jié)點(diǎn)密度的增加，兩種算法的數(shù)據(jù)包到達(dá)率均呈現(xiàn)增加趨勢(shì)。原因在于更多的節(jié)點(diǎn)可提供更多的路徑選擇，并且能尋找到緩存源的概率逐步增大。但還可以看出，低節(jié)點(diǎn)密度下ICR-MCS與MGFR的數(shù)據(jù)包到達(dá)率較為接近，節(jié)點(diǎn)密度逐漸增大時(shí)，ICR-MCS的優(yōu)勢(shì)更加明顯。然而，隨著節(jié)點(diǎn)密度的進(jìn)一步增加，所提出的路由算法在數(shù)據(jù)包到達(dá)率上的優(yōu)勢(shì)略有減弱。這是因?yàn)樵诘凸?jié)點(diǎn)密度下，可供選擇的路徑較少，并且可找到緩存請(qǐng)求內(nèi)容的緩存源也較少，因此數(shù)據(jù)包到達(dá)率較低；節(jié)點(diǎn)密度增加后，可選路徑和有效緩存源增多，提高了數(shù)據(jù)到達(dá)率，且ICR-MCS在運(yùn)動(dòng)預(yù)測(cè)的機(jī)制作用下，選擇的中繼節(jié)點(diǎn)更加合理，因此優(yōu)勢(shì)逐漸明顯；但當(dāng)節(jié)點(diǎn)密度進(jìn)一步增加后，路徑數(shù)量和緩存源數(shù)量的增加提供的性能增益已趨于飽和，并且MGFR也能尋找到較多有效緩存源和路由路徑，因此ICR-MCS的優(yōu)勢(shì)逐漸減弱，但在中繼抑制的作用下，數(shù)據(jù)包之間的沖突更少，從而保持了更高的數(shù)據(jù)包到達(dá)率。

3.3 平均請(qǐng)求-響應(yīng)時(shí)延

平均請(qǐng)求-響應(yīng)時(shí)延反映的是路由傳輸?shù)臅r(shí)效性。更低的值意味著請(qǐng)求節(jié)點(diǎn)能更快獲得所需的內(nèi)容。不同節(jié)點(diǎn)密度下ICR-MCS和MGFR的平均請(qǐng)求-響應(yīng)時(shí)延性能如圖5所示。

圖5 不同節(jié)點(diǎn)密度下的平均請(qǐng)求-響應(yīng)時(shí)延

從圖5可以看出，隨著節(jié)點(diǎn)密度的增加，ICR-MCS和MGFR都能獲得更低的平均請(qǐng)求-響應(yīng)時(shí)延。這得益于更多的節(jié)點(diǎn)數(shù)量增大了可提供響應(yīng)包緩存源的概率，平均意義下緩存源的距離也更短。但是，同樣可以看出，ICR-MCS在中段的節(jié)點(diǎn)密度處優(yōu)勢(shì)更加明顯，這是因?yàn)樗岢龅穆酚伤惴軌蚋鼫?zhǔn)確判斷候選中繼節(jié)點(diǎn)的移動(dòng)方向，從而找出更有利于縮短轉(zhuǎn)發(fā)時(shí)間的中繼節(jié)點(diǎn)。在高節(jié)點(diǎn)密度區(qū)域，ICRMCS能夠利用基于中繼抑制的多源協(xié)作完成數(shù)據(jù)傳輸，使得響應(yīng)包在有效回傳的同時(shí)將網(wǎng)絡(luò)帶寬的消耗控制在更低的程度，也為其他響應(yīng)包傳輸提供了更多網(wǎng)絡(luò)資源，從而仍保持更低的平均請(qǐng)求-響應(yīng)時(shí)延。

4 結(jié) 語(yǔ)

在城市場(chǎng)景中，岔路口和非岔路口的道路結(jié)構(gòu)特點(diǎn)導(dǎo)致了VICN中車輛拓?fù)渚哂胁煌淖兓?guī)律，路由算法所需要解決的問(wèn)題也有所不同。所提出的ICR-MCS路由算法能夠利用車輛的運(yùn)動(dòng)預(yù)測(cè)有效縮短多緩存源的響應(yīng)路徑，并利用中繼抑制實(shí)現(xiàn)了多緩存源之間的隱式協(xié)作，充分發(fā)揮了網(wǎng)絡(luò)帶寬的潛力為更多節(jié)點(diǎn)提供服務(wù)，從而提高了數(shù)據(jù)包到達(dá)率和降低了平均請(qǐng)求-響應(yīng)時(shí)延。