V-NDN中熱點內容推送策略研究*

史錦山，李 茹，李瑛琦

內蒙古大學 計算機學院，呼和浩特 010021

1 引言

互聯網發展至今，其主要使用需求已經從計算資源共享轉變為內容的獲取和分發[1]。以內容為中心的命名數據網絡（named data networking，NDN）體系結構成為替代傳統互聯網的下一代網絡架構之一[2]。同時，NDN具有移動性、網絡地址無關性、連接會話的不依賴性和多尋址/多網絡等特點，在移動環境下更具優勢和發展潛力。而車輛自組織網絡（vehicular ad-hoc networks，VANET）作為具有節點移動速度快、網絡拓撲變化頻繁且數據承載量大等特點的網絡環境，非常適合使用NDN體系結構進行部署[3]。

在基于NDN的VANET（vehicular named data networking，V-NDN）中，由于車輛的高速移動而導致網絡環境具有網絡拓撲變化快、通信鏈路生存時間短的問題。因此在車輛節點發出興趣包后，由于通信鏈路持續時間的不穩定性以及網絡拓撲變化快而導致數據包傳輸路徑可能會發生變化，最終會導致未響應興趣包的概率大大增加[4]。目前的解決方法是車輛節點緩存所有收聽到的數據包[3]，但這種方法會使網絡中的節點緩存大量重復的數據包副本，極大地增加節點緩存（content store，CS）的開銷。然而在現實環境中車輛的CS是有限的，將緩存空間用于緩存大量無用的數據包副本可能會降低網絡的性能。

為了解決上述問題，本文提出了一種熱點內容推送算法。根據Adamic等人的研究，網絡中用戶的訪問行為一般服從Zipf定律[5]，即網絡中大部分的請求往往是針對少量的內容。在本文中，將網絡中大部分節點感興趣的內容稱之為熱點內容。通過熱點內容挖掘算法，將網絡中可能的熱點內容從大量的數據中挖掘出來，然后通過熱點內容推送算法將這些熱點內容推送到網絡中可能會訪問這些內容的節點上。這樣，當這些節點在訪問這些熱點內容的時候，就可以直接從自己本地的緩存中獲取內容，從而省去了節點發送興趣包，興趣包在網絡中傳播尋找內容以及找到所需內容后數據包返回請求者的時間開銷和網絡資源開銷，同時也降低了網絡中數據包副本的數量。實驗證明，通過熱點內容推送不僅提高了用戶的請求滿足率，而且提高了節點的緩存命中率，降低了網絡開銷。

2 相關工作

NDN網絡架構是一個以內容為中心的網絡架構，并保持了TCP/IP的沙漏模型。每個NDN節點都包含3個數據結構[2]：轉發信息表（forwarding information base，FIB），用來將請求數據包路由至可能的匹配數據源；轉發請求表（pending interest table，PIT）保存興趣包發送的上行信息，以確保數據包正確地返回給請求者；CS緩存接收到的數據。NDN利用這3個數據結構完成了信息的路由和轉發。

目前，轉發策略是V-NDN研究的一個熱點。加州大學洛杉磯分校的Wang等人提出了一種未來車載通訊系統的架構，首次將NDN體系結構應用于VANET，為了適應VANET環境的頻繁中斷網絡連接和網絡拓撲變化快的特點，對傳統的NDN模型進行了調整：V-NDN中每個節點會緩存所有聽到的數據包，而不是采用原始的只有在PIT中有轉發記錄的才緩存數據包[3]。而以上對NDN緩存的調整，Wang[6]、Grassi[7-9]在隨后的研究中都延續了下來。根據數據包轉發方式的不同轉發策略可以分為三類：盲目洪泛轉發策略[6-8]、基于啟發式信息的轉發策略[10-12]和基于地理位置的轉發策略[9,13]。在盲目洪泛轉發策略中，Wang等人將定時器應用于V-NDN中以協調廣播時間，避免數據包的沖撞[6]；Grassi等人在文獻[7-8]中延續了文獻[6]的工作，并將選擇距離最遠的節點轉發數據包的方式命名為貪婪轉發。基于啟發式信息的轉發策略中，Ahmed等人提出一種名為RUFS的興趣包轉發策略，來減輕興趣包轉發引起的廣播風暴[10]；Kalogeiton等人考慮到VANET的間歇連通性，提出了一種多跳和多路徑VANET路由算法，它利用多條路徑來實現更快的內容檢索[11]；鮮永菊等人提出了一種基于多屬性決策的道路拓撲轉發方案，通過多屬性決策方法選取最優的目的節點，以此對興趣包盲目洪泛轉發做出優化[12]。基于地理位置的轉發策略中，Grassi提出了一種城市道路中基于位置的數據包轉發機制，當數據包傳遞到十字路口時根據地理信息確定向哪個方法轉遞，命名為Navigo[9]；Bian等人提出了一種基于地理位置的轉發策略，同時提出了一種啟發策略來減少數據包傳輸路徑中不必要的緩存副本[13]。綜上所述，盲目洪泛轉發策略并沒有考慮網絡中緩存大量數據包副本數對網絡性能的影響，啟發式的轉發策略則利用啟發信息通過剪枝的方式降低網絡中緩存的數據包副本數，基于地理位置的轉發策略則利用地理位置信息控制了數據包轉發的方向，以此降低網絡中緩存的數據包副本數。目前并沒有通過推送熱點內容的方式優化V-NDN網絡性能的方法。

3 熱點內容推送策略

本文的目的是從網絡中的海量數據中找到多數用戶感興趣的內容，然后主動地將這些熱點內容推送給其他可能訪問這些內容的節點，以此來達到提高網絡性能的目的。首先，給出兩個前提條件：（1）在V-NDN中，每個車輛節點都有PIT、FIB和CS，遵循Wang等人對NDN模型做出的調整，V-NDN中每個節點都會緩存所有接收到的數據包，而不是采用原始的只用在PIT中有轉發記錄的才接收數據包。（2）車輛節點裝有定位裝置，如車載全球定位系統（global positioning system，GPS），可以隨時獲取車輛的地理位置信息。

本文將V-NDN中緩存或者生成內容的節點稱為該內容的數據提供者。在熱點內容推送過程中，數據提供者通過熱點內容挖掘算法找到熱點內容后，通過熱點內容推送算法將其推送給可能會請求這些熱點內容的節點上。接下來將詳細介紹熱點內容挖掘算法。

3.1 熱點內容挖掘算法

本文中熱點內容是通過內容的熱度來衡量，由于V-NDN中節點的高速移動性導致網絡的拓撲變化大、變化快，因此在進行熱點內容挖掘時無法得到網絡的全局信息，只能根據局部信息挖掘網絡中局部的熱點內容。

熱點內容挖掘周期如圖1所示，主要步驟分為四步：（1）收集興趣包信息。（2）統計興趣包數據。（3）挖掘熱點內容。（4）內容熱度消退。首先需要節點實時地收集興趣包信息，然后在節點收集所需信息后，對信息進行統計、分析是否有熱點內容。在挖掘出熱點內容后，同時要考慮熱度的消退。

Fig.1 Cycle diagram of hot content mining圖1 熱點內容挖掘周期圖

為了挖掘熱點內容，每個節點都會建立兩個表：內容熱度表和熱點內容表，如圖2和圖3所示。內容熱度表用來統計節點收集到的興趣包信息并計算其熱度，熱點內容表用來記錄已挖掘到的熱點內容的名稱，表中的時間戳用來進行內容熱度消退。

Fig.2 Format of content popularity table圖2 內容熱度表格式

Fig.3 Format of hot content table圖3 熱點內容表格式

熱點內容消退的原因有兩個：其一是因為網絡中的熱點內容一般都具有時效性；其次是因為熱點內容推送算法的需求，由于熱點內容推送算法的目標是將熱點內容推送到可能會訪問該內容但還沒有訪問的節點上，這就需要推送的不是網絡中大部分用戶都訪問過的內容，而是有可能會被大量用戶訪問但是還沒有訪問的內容，因此需要去除網絡中大部分用戶已經訪問過的熱點內容對熱點內容挖掘的影響。因此熱點內容消退主要由兩部分構成：第一部分是在熱點挖掘階段，過濾掉網絡中已經非常熱的內容，因為這些內容很有可能網絡中的大部分用戶已經訪問過了，已經沒有推送、擴散的必要；第二部分是在挖掘到熱點內容后，并不是無限制地推送下去，而是隨時間進行熱度消退，直到最后不再推送，變為普通內容。

基于以上分析，提出熱點內容挖掘算法，在本文中熱點的閾值為1.2倍的熱度均值，該值為經驗值，后續會繼續深入研究。算法步驟如算法1所示。

算法1熱點內容挖掘算法

輸入：車輛節點vi，vi的內容熱度表CLi，vi的熱點內容表HLi，內容名稱為n的興趣包In，熱點閾值HT。

3.2 熱點內容推送算法

考慮到需要將挖掘出來的熱點內容在V-NDN中大量用戶還沒有請求之前推送到這些節點的緩存中，因此需要以最快的方法將熱點內容擴散出去。因為在V-NDN中內容傳輸路徑中的節點都會緩存該內容，所以本文設計通過數據請求者來推送熱點內容。車輛節點通過熱點內容挖掘算法得到熱點內容表，然后將熱點內容表中內容名稱對應的數據包標記為熱點內容。在NDN中可以通過向熱點內容數據包添加標簽的方式標記熱點內容。同時，熱度消退問題通過熱點內容表中的時間戳控制。如圖4所示，A到H代表車輛節點，節點外的虛線圓代表該節點的通信范圍，c代表內容。其中G節點為數據請求者，G節點請求內容c，而內容c的數據提供者為節點D。當D節點通過熱點內容挖掘算法得出內容c為熱點內容后，會給內容c添加熱點標簽。G節點在收到內容c后發現是熱點內容，就會將其推送給節點F和H。在數據包傳輸路徑中的節點，例如節點B并不會推送該熱點向自己的鄰居節點。選擇這樣推送的原因是：（1）V-NDN中車輛節點的傳輸距離假設在100 m左右，車輛節點沿道路行駛，而道路對車輛節點行駛軌跡的約束導致熱點內容在沿道路傳輸時，路徑中的節點都會緩存該內容，因此熱點傳輸路徑中的節點并不會推送熱點內容。（2）為了將熱點內容推送到網絡中可能會訪問這些內容的節點上，需要擴大熱點內容在網絡中的分布范圍，同時為了降低網絡中數據包副本的數量，需要限制熱點內容推送的范圍，因此本文在熱點到達數據請求者時，由數據請求者將熱點內容推送給其鄰居節點，因為推送的位置處于熱點傳輸過程的末端，所以既擴大了網絡中熱點的分布范圍，又抑制了熱點內容數據包過度的擴散。

Fig.4 Schematic diagram of hot content push圖4 熱點內容推送示意圖

基于以上分析，提出熱點內容推送算法，算法步驟如算法2所示。

算法2熱點內容推送算法

輸入：車輛節點vj，vj的熱點內容表HLj，內容名稱為m的數據包Dm。

輸出：vj的熱點內容表HLj。

4 理論分析

4.1 V-NDN網絡建模

在對V-NDN網絡進行建模之前，需確定在VANET中時間是連續的，而本文在不影響建模真實度的情況下，將連續的時間劃分為等長的時間片，即，第k個時間段通過tk=[tk,tk+1)表示，下文中通過t表示時間。

本文將道路中所有安裝有NDN模塊的車輛組成的V-NDN，通過無向車輛圖G(V(t),Ev(t))表示。其中V(t)={v}表示在t時間V-NDN中車輛v的集合，VNDN中車輛的數量并不是固定的，而是隨著時間t不斷變化。，是邊的集合，邊表示在時間t車輛i與車輛j可直接通信。可知，Ev(t)的數量取決于車輛密度和每個車輛節點的通信范圍，隨著通信范圍的增大，導致可直接通信的車輛節點也會增多。同時V-NDN是隨著時間變化的，因此模型需要考慮時間t對模型的影響。如圖5所示，圖中的節點為車輛，節點之間的邊為一跳的可通信鏈路。

Fig.5 Undirected graph showing relationship of vehiclesG(V(t),Ev(t))圖5 無向車輛圖G(V(t),Ev(t))

V-NDN是內容為中心的網絡，因此需要明確網絡中節點與內容的關系。本文將車輛與內容的關系建模為一個車輛與內容關系的二分圖G(V(t),C(t),Ec(t))。其中V(t)={v}是車輛圖G(V(t),Ev(t))中的t時間V-NDN中車輛v的集合。C(t)={c}表示t時間V-NDN中內容的集合，同時需要注意在V-NDN中內容并不是固定不變的，會隨著時間產生或者消失，因而需要引入時間t。表示車輛v在t時間擁有的所有的內容Cv?C(t)，同時也可以表示在t時間擁有內容c的所有車輛的集合Vc?V(t)。如圖6所示，圖中上方的一行節點表示車輛，下方的一行節點表示內容，車輛節點和內容節點之間的邊表示該車輛節點擁有該內容。

Fig.6 Bipartite graph showing relationship between vehicles and contentG(V(t),C(t),Ec(t))圖6 車輛與內容關系的二分圖G(V(t),C(t),Ec(t))

為了表述時間t內容c在V-NDN的分布情況，對其建模形成內容分布情況的非連通圖G(Vc(t),Evc(t))，其中Vc(t)={vc(t)|vc∈V(t),c∈C(t)}表示在t時間擁有內容c的車輛的集合，表示在t時間擁有內容c的車輛i與車輛j之間可直接通信。如圖7所示，圖中節點表示在t時間擁有內容c的車輛，節點間的邊表示節點之間可直接通信。

Fig.7 Graph of content distributionG(Vc(t),Evc(t))圖7 內容分布情況圖G(Vc(t),Evc(t))

4.2 熱點挖掘建模

在熱點內容推送過程中，首先需要數據提供者通過熱點內容挖掘算法找到熱點內容，接下來將詳細講述熱點內容挖掘的理論分析。

假設車輛的通信范圍是一個圓，那么車輛v在道路行駛過程中，在時間t內可能有n個進入車輛v可通信范圍的車輛。可知車輛v在t時間遇到n個新的節點的概率服從泊松分布[14]，即：

其中，t為正數，λ為單位時間內車輛遇見新節點的次數，由車輛的通信范圍和道路上的車輛密度決定。

那么車輛v在t時間有n個鄰居節點時，接收到請求內容為c的興趣包的概率可由式（2）計算得出：

其中，內容c∈C(t)，S(t,c)為V-NDN中車輛節點在t時間內收到內容為c的興趣包的數量，S(t)為車輛節點在t時間內收到的所有興趣包的數量，通過兩者之間的比例可以簡單地計算出車輛在時間t內接收內容為c的興趣包的概率。S(t,c)和S(t)都需統計V-NDN全局信息得出，但是V-NDN中全局信息并不容易獲得，因此在本文中可將其看作常量。

通過式（1）和式（2），可以計算出車輛v在時間t接收到內容為c的興趣包的概率為：

即車輛v在時間t接收到內容為c的興趣包的概率可以將其轉化為分別計算每一種鄰居節點數量的情況然后將其求和的問題，因此可以通過全概率公式計算得出。同時由于車輛v在t時間有0個鄰居節點時，接收到請求內容為c的興趣包的概率Pv(c|N(t)=0)=0，因而式（3）從1開始累加。

車輛v中內容c在時間t成為熱點內容的概率，可通過馬爾可夫鏈計算。設V-NDN中的內容有兩個狀態：普通狀態和熱點狀態；1代表普通狀態，2代表熱點狀態。通過馬爾可夫鏈對內容c建模，其中c∈C(t)。可得狀態轉移概率矩陣Pc(t)：

可知當內容c在t-1時間為普通狀態，在t時間為熱點狀態的狀態轉移概率p12(t,c)可以通過如下公式計算：

可知p11(t,c)+p12(t,c)=1；由此可得狀態轉移概率：

同理，狀態轉移概率p21(t,c)、p22(t,c)通過如下公式計算：

本文中將以上四個狀態轉移概率的初始值設為0.5。

因此，車輛中內容c在時間t成為熱點內容的概率為：

最終可得車輛中內容c在時間t的熱度的Hv(t,c)計算公式為：

其中，γ∈[0,1]是調整上一時間t-1對這一時間t影響的參數。

通過式（10）可知車輛v在時間t的內容c的熱度Hv(t,c)，與車輛中內容c在時間t成為熱點內容的概率fv(t,c)成正相關，而fv(t,c)與車輛v在時間t接收到的請求內容c的興趣包頻率、車輛節點密度和傳輸范圍成正相關。

5 實驗驗證與結果分析

5.1 仿真場景

本文使用基于NS-3的NDN模擬器ndnSIM進行仿真實驗[15]。根據文獻[6]，本實驗使用IEEE 802.11a進行通信，車輛的通信范圍為120 m，具體參數如表1所示。

Table 1 ndnSIM experimental parameters表1 ndnSIM實驗參數

本文設計的算法針對的是城市道路場景，由于需要挖掘熱點并將其推送到還沒有請求它的節點上去，因此需要較大的實驗場景。本文模擬的城市道路場景大小為2 km×2 km，為了盡可能地貼近現實，城市場景中共設置雙向6車道13條，雙向4車道17條，雙向2車道2條。其中雙向6車道的允許的最高速度為120 km/h；雙向4車道為50 km/h；雙向2車道為30 km/h。但是根據《中華人民共和國道路交通安全法實施條例》城市中道路最高速度為70 km/h，因此節點的最高速度為70 km/h。車輛節點移動軌跡由 Vanetmobisim（vehicular ad hoc networks mobility simulator）生成，詳細參數如表2所示。為了模擬網絡中用戶的訪問習慣[5]，本實驗中數據請求者按照Zipf分布發送興趣包，數據請求者發送興趣包的頻率為每秒一個。

Table 2 Vehicle node movement trajectory parameters表2 車輛節點移動軌跡參數表

5.2 熱點內容推送實驗及分析

為了評估熱點內容推送算法的性能，在仿真中與貪婪轉發策略進行比較，貪婪轉發策略是由Wang等人在文獻[6]中提出，其團隊在之后的文獻[7]和文獻[8]中將其作為V-NDN的轉發策略。本實驗是在貪婪轉發策略的基礎上，添加了熱點內容推送算法。實驗中設置200個數據請求者，20個數據生產者。

首先考慮請求滿足率，請求滿足率是數據請求者收到數據包的個數與數據請求者產生興趣包個數的百分比。請求滿足率用來衡量數據請求者產生興趣包并獲得相應數據包的成功率。如圖8所示為請求滿足率對比圖，圖中虛線為貪婪轉發策略，實線為添加熱點內容推送后的結果，其中數據為每5 s的平均值。由本圖可知在60 s以后數據接近平穩，請求滿足率穩定在65%左右，添加熱點內容推送后請求滿足率的提升率在4.6%到14.1%之間。

接著考慮緩存命中率，在本文中緩存命中率為節點收到興趣包時緩存中有匹配數據包的個數與節點收到興趣包的個數的百分比。本文提出的熱點內容推送算法就是將熱點內容推送給可能會訪問的節點上，因此緩存命中率會有提高。如圖9所示，其中數據為每5 s的平均值，仿真數據在50 s后逐漸平穩，添加熱點內容推送后緩存命中率提升了16.6%到33.0%，其緩存命中率在80%左右。實驗證明熱點內容推送算法達到了預期目的。

Fig.8 Request satisfaction rate圖8 請求滿足率

Fig.9 Cache hit rate圖9 緩存命中率

最后通過興趣包滿足的平均延遲來對比分析熱點內容推送算法對貪婪轉發策略的優化程度。興趣包滿足平均延遲為節點發出興趣包到接收到數據包之間的時間。當節點的應用層發出興趣包后，在節點本地的CS中匹配到了所需的數據包，那么此興趣包滿足的延遲為0 s。如圖10為興趣包滿足的平均延遲，圖中數據每秒統計一次。由圖可知，在20 s左右首次找到了熱點內容，圖中實線有多個延遲為接近0 s的時間段，說明在這些時間段內，興趣請求者直接在自己的緩存中得到了所請求的數據，證明熱點內容挖掘的有效性，同時降低了興趣包滿足的延遲。

Fig.10 Average latency of interest package satisfaction圖10 興趣包滿足的平均延遲

6 結論

本文針對城市道路環境，提出基于熱點內容推送的V-NDN轉發策略優化方案。針對目前V-NDN中節點會緩存大量重復的數據包副本的問題，提出了一種熱點內容推送算法來解決此問題。首先通過熱點內容挖掘算法挖掘出V-NDN中的熱點內容，然后通過熱點內容推送算法將熱點推送到可能會訪問它的節點緩存中。隨后通過理論分析了熱點內容挖掘時需要考慮的影響因素。最后通過仿真實驗驗證了其有效性。