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

陳秉試

（廈門海洋職業技術學院，福建 廈門 361012）

0 引 言

車聯網可實現車輛與車輛、人、路等多種網絡實體之間的聯系，提供更加安全、豐富、智能以及舒適的駕駛環境與服務，具有廣闊的市場前景[1-2]。但是，傳統基于TCP/IP的網絡架構在車輛拓撲高度動態的情況下，不利于數據資源獲取和移動節點管理。車載信息中心網絡（Vehicular Information Centric Network，VICN）中采用緩存機制將數據內容放置于節點，緩存節點收到請求包后可以完成響應，將響應包通過路由發送給請求節點，降低了請求-響應時延，更加適用于車聯網中移動節點的場景[3-5]。

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

目前的研究在多緩存源響應時產生的多路徑路由之間的協作方面仍有提升空間，并且在城市環境下的自適應性尚不成熟。請求節點向外廣播請求，并經過多跳傳輸后，將被多個緩存有所需內容的節點響應。此時，參與響應的節點成為多源路由的源節點。傳統的響應路由算法通過沿請求路徑返回的方式完成響應，但在VICN中，車輛拓撲在岔路口劇烈變化，容易發生請求路徑斷裂，從而導致響應失敗。而在非岔路口的道路中，車輛拓撲保持相對穩定，多源同時響應又造成響應冗余，浪費網絡資源。因此，需要合理設計多源路由算法，優化多緩存源的響應時機，并根據車輛拓撲特點在緩存源之間進行協作，以提高數據包到達率，減少緩存響應時延。

1 系統模型

城市環境中，岔路口處的拓撲變化給路由帶來挑戰，但是紅綠燈以及非岔路口的直行道路也創造了拓撲相對穩定的有利條件。

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

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

2 ICR-MCS機制

2.1 總體思想及流程

VICN中車輛拓撲變化在空間上呈現不同的動態性，即岔路口處拓撲變化明顯，非岔路口道路中拓撲變化較弱。當VICN中緩存具有一定的冗余度時，利用多緩存源均可接受請求并響應的特點構建多路徑路由，以提升在拓撲變化較大區域的數據達到率。VICN中車輛運動受到道路限速和道路空間約束，其運動軌跡具有較強的可預測性。因此，在多路徑路由轉發過程中，充分利用車輛的短時軌跡信息，可提高響應包的回傳成功率。為了避免非岔路口道路中多路徑路由退化成泛洪廣播，導致網絡帶寬浪費，利用無線傳輸的天然廣播特性，車輛節點通過監聽響應包的方式引入中繼抑制機制。節點轉發過程中，將對周圍節點在概率意義上產生抑制作用，降低響應包重復傳播的概率，也實現了多源之間的隱式協作。

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

圖2 ICR-MCS總體流程

2.2 基于運動預測的多路徑路由

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

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

其中，ωd及ωγ為權重因子，且有ωd+ωγ=1。

2.3 基于中繼抑制的多源協作

多個緩存源收到請求后，都將開始對請求進行響應。在岔路口等拓撲變化大的場景，多源多路徑路由可以提高數據包到達率。但是，在非岔路口的道路中，多源同時響應浪費帶寬。因此，通過中繼抑制機制自適應地在不同場景中完成多緩存源在路由中的隱式協作。

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

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

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

3 仿真及分析

3.1 仿真條件

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

圖3 城市場景道路模型

本文提出的ICR-MCS將與多源貪婪轉發路由（Multisource Greedy Forwarding Routing，MGFR）算法在數據包到達率和平均請求-響應時延方面比較。多源貪婪轉發算法是指多緩存源在收到請求包之后都將采用位置上的貪婪轉發進行響應。性能指標方面，數據包到達率定義為緩存源響應請求時發出的響應包個數中能成功到達請求節點的比例。平均請求-響應時延定義為統計平均下，請求節點在發出請求到獲得響應包的時間間隔。

3.2 數據包到達率

數據包到達率反映的是路由傳輸的有效性。更高的數據包到達率說明傳輸路徑中可達路徑更多或者轉發過程中沖突及擁塞更少。不同節點密度下ICR-MCS和MGFR的數據包到達率性能如圖4所示。

圖4 不同節點密度下的數據包到達率

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

3.3 平均請求-響應時延

平均請求-響應時延反映的是路由傳輸的時效性。更低的值意味著請求節點能更快獲得所需的內容。不同節點密度下ICR-MCS和MGFR的平均請求-響應時延性能如圖5所示。

圖5 不同節點密度下的平均請求-響應時延

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

4 結 語

在城市場景中，岔路口和非岔路口的道路結構特點導致了VICN中車輛拓撲具有不同的變化規律，路由算法所需要解決的問題也有所不同。所提出的ICR-MCS路由算法能夠利用車輛的運動預測有效縮短多緩存源的響應路徑，并利用中繼抑制實現了多緩存源之間的隱式協作，充分發揮了網絡帶寬的潛力為更多節點提供服務，從而提高了數據包到達率和降低了平均請求-響應時延。