VICN中多緩存源的隱式協(xié)作路由算法*

陳秉試

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

0 引 言

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

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

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

1 系統(tǒng)模型

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

圖1 城市場景中的VICN多路徑路由

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

2 ICR-MCS機(jī)制

2.1 總體思想及流程

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

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

圖2 ICR-MCS總體流程

2.2 基于運動預(yù)測的多路徑路由

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

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

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

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

多個緩存源收到請求后，都將開始對請求進(jìn)行響應(yīng)。在岔路口等拓?fù)渥兓蟮膱鼍埃嘣炊嗦窂铰酚煽梢蕴岣邤?shù)據(jù)包到達(dá)率。但是，在非岔路口的道路中，多源同時響應(yīng)浪費帶寬。因此，通過中繼抑制機(jī)制自適應(yīng)地在不同場景中完成多緩存源在路由中的隱式協(xié)作。

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

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

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

3 仿真及分析

3.1 仿真條件

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

圖3 城市場景道路模型

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

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

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

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

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

3.3 平均請求-響應(yīng)時延

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

圖5 不同節(jié)點密度下的平均請求-響應(yīng)時延

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

4 結(jié) 語

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