史錦山，李 茹，李瑛琦

內(nèi)蒙古大學(xué) 計(jì)算機(jī)學(xué)院，呼和浩特 010021

1 引言

互聯(lián)網(wǎng)發(fā)展至今，其主要使用需求已經(jīng)從計(jì)算資源共享轉(zhuǎn)變?yōu)閮?nèi)容的獲取和分發(fā)[1]。以內(nèi)容為中心的命名數(shù)據(jù)網(wǎng)絡(luò)（named data networking，NDN）體系結(jié)構(gòu)成為替代傳統(tǒng)互聯(lián)網(wǎng)的下一代網(wǎng)絡(luò)架構(gòu)之一[2]。同時(shí)，NDN具有移動(dòng)性、網(wǎng)絡(luò)地址無關(guān)性、連接會(huì)話的不依賴性和多尋址/多網(wǎng)絡(luò)等特點(diǎn)，在移動(dòng)環(huán)境下更具優(yōu)勢(shì)和發(fā)展?jié)摿?。而車輛自組織網(wǎng)絡(luò)（vehicular ad-hoc networks，VANET）作為具有節(jié)點(diǎn)移動(dòng)速度快、網(wǎng)絡(luò)拓?fù)渥兓l繁且數(shù)據(jù)承載量大等特點(diǎn)的網(wǎng)絡(luò)環(huán)境，非常適合使用NDN體系結(jié)構(gòu)進(jìn)行部署[3]。

在基于NDN的VANET（vehicular named data networking，V-NDN）中，由于車輛的高速移動(dòng)而導(dǎo)致網(wǎng)絡(luò)環(huán)境具有網(wǎng)絡(luò)拓?fù)渥兓?、通信鏈路生存時(shí)間短的問題。因此在車輛節(jié)點(diǎn)發(fā)出興趣包后，由于通信鏈路持續(xù)時(shí)間的不穩(wěn)定性以及網(wǎng)絡(luò)拓?fù)渥兓於鴮?dǎo)致數(shù)據(jù)包傳輸路徑可能會(huì)發(fā)生變化，最終會(huì)導(dǎo)致未響應(yīng)興趣包的概率大大增加[4]。目前的解決方法是車輛節(jié)點(diǎn)緩存所有收聽到的數(shù)據(jù)包[3]，但這種方法會(huì)使網(wǎng)絡(luò)中的節(jié)點(diǎn)緩存大量重復(fù)的數(shù)據(jù)包副本，極大地增加節(jié)點(diǎn)緩存（content store，CS）的開銷。然而在現(xiàn)實(shí)環(huán)境中車輛的CS是有限的，將緩存空間用于緩存大量無用的數(shù)據(jù)包副本可能會(huì)降低網(wǎng)絡(luò)的性能。

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

2 相關(guān)工作

NDN網(wǎng)絡(luò)架構(gòu)是一個(gè)以內(nèi)容為中心的網(wǎng)絡(luò)架構(gòu)，并保持了TCP/IP的沙漏模型。每個(gè)NDN節(jié)點(diǎn)都包含3個(gè)數(shù)據(jù)結(jié)構(gòu)[2]：轉(zhuǎn)發(fā)信息表（forwarding information base，F(xiàn)IB），用來將請(qǐng)求數(shù)據(jù)包路由至可能的匹配數(shù)據(jù)源；轉(zhuǎn)發(fā)請(qǐng)求表（pending interest table，PIT）保存興趣包發(fā)送的上行信息，以確保數(shù)據(jù)包正確地返回給請(qǐng)求者；CS緩存接收到的數(shù)據(jù)。NDN利用這3個(gè)數(shù)據(jù)結(jié)構(gòu)完成了信息的路由和轉(zhuǎn)發(fā)。

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

3 熱點(diǎn)內(nèi)容推送策略

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

本文將V-NDN中緩存或者生成內(nèi)容的節(jié)點(diǎn)稱為該內(nèi)容的數(shù)據(jù)提供者。在熱點(diǎn)內(nèi)容推送過程中，數(shù)據(jù)提供者通過熱點(diǎn)內(nèi)容挖掘算法找到熱點(diǎn)內(nèi)容后，通過熱點(diǎn)內(nèi)容推送算法將其推送給可能會(huì)請(qǐng)求這些熱點(diǎn)內(nèi)容的節(jié)點(diǎn)上。接下來將詳細(xì)介紹熱點(diǎn)內(nèi)容挖掘算法。

3.1 熱點(diǎn)內(nèi)容挖掘算法

本文中熱點(diǎn)內(nèi)容是通過內(nèi)容的熱度來衡量，由于V-NDN中節(jié)點(diǎn)的高速移動(dòng)性導(dǎo)致網(wǎng)絡(luò)的拓?fù)渥兓?、變化快，因此在進(jìn)行熱點(diǎn)內(nèi)容挖掘時(shí)無法得到網(wǎng)絡(luò)的全局信息，只能根據(jù)局部信息挖掘網(wǎng)絡(luò)中局部的熱點(diǎn)內(nèi)容。

熱點(diǎn)內(nèi)容挖掘周期如圖1所示，主要步驟分為四步：（1）收集興趣包信息。（2）統(tǒng)計(jì)興趣包數(shù)據(jù)。（3）挖掘熱點(diǎn)內(nèi)容。（4）內(nèi)容熱度消退。首先需要節(jié)點(diǎn)實(shí)時(shí)地收集興趣包信息，然后在節(jié)點(diǎn)收集所需信息后，對(duì)信息進(jìn)行統(tǒng)計(jì)、分析是否有熱點(diǎn)內(nèi)容。在挖掘出熱點(diǎn)內(nèi)容后，同時(shí)要考慮熱度的消退。

Fig.1 Cycle diagram of hot content mining圖1 熱點(diǎn)內(nèi)容挖掘周期圖

為了挖掘熱點(diǎn)內(nèi)容，每個(gè)節(jié)點(diǎn)都會(huì)建立兩個(gè)表：內(nèi)容熱度表和熱點(diǎn)內(nèi)容表，如圖2和圖3所示。內(nèi)容熱度表用來統(tǒng)計(jì)節(jié)點(diǎn)收集到的興趣包信息并計(jì)算其熱度，熱點(diǎn)內(nèi)容表用來記錄已挖掘到的熱點(diǎn)內(nèi)容的名稱，表中的時(shí)間戳用來進(jìn)行內(nèi)容熱度消退。

Fig.2 Format of content popularity table圖2 內(nèi)容熱度表格式

Fig.3 Format of hot content table圖3 熱點(diǎn)內(nèi)容表格式

熱點(diǎn)內(nèi)容消退的原因有兩個(gè)：其一是因?yàn)榫W(wǎng)絡(luò)中的熱點(diǎn)內(nèi)容一般都具有時(shí)效性；其次是因?yàn)闊狳c(diǎn)內(nèi)容推送算法的需求，由于熱點(diǎn)內(nèi)容推送算法的目標(biāo)是將熱點(diǎn)內(nèi)容推送到可能會(huì)訪問該內(nèi)容但還沒有訪問的節(jié)點(diǎn)上，這就需要推送的不是網(wǎng)絡(luò)中大部分用戶都訪問過的內(nèi)容，而是有可能會(huì)被大量用戶訪問但是還沒有訪問的內(nèi)容，因此需要去除網(wǎng)絡(luò)中大部分用戶已經(jīng)訪問過的熱點(diǎn)內(nèi)容對(duì)熱點(diǎn)內(nèi)容挖掘的影響。因此熱點(diǎn)內(nèi)容消退主要由兩部分構(gòu)成：第一部分是在熱點(diǎn)挖掘階段，過濾掉網(wǎng)絡(luò)中已經(jīng)非常熱的內(nèi)容，因?yàn)檫@些內(nèi)容很有可能網(wǎng)絡(luò)中的大部分用戶已經(jīng)訪問過了，已經(jīng)沒有推送、擴(kuò)散的必要；第二部分是在挖掘到熱點(diǎn)內(nèi)容后，并不是無限制地推送下去，而是隨時(shí)間進(jìn)行熱度消退，直到最后不再推送，變?yōu)槠胀▋?nèi)容。

基于以上分析，提出熱點(diǎn)內(nèi)容挖掘算法，在本文中熱點(diǎn)的閾值為1.2倍的熱度均值，該值為經(jīng)驗(yàn)值，后續(xù)會(huì)繼續(xù)深入研究。算法步驟如算法1所示。

算法1熱點(diǎn)內(nèi)容挖掘算法

輸入：車輛節(jié)點(diǎn)vi，vi的內(nèi)容熱度表CLi，vi的熱點(diǎn)內(nèi)容表HLi，內(nèi)容名稱為n的興趣包In，熱點(diǎn)閾值HT。

3.2 熱點(diǎn)內(nèi)容推送算法

考慮到需要將挖掘出來的熱點(diǎn)內(nèi)容在V-NDN中大量用戶還沒有請(qǐng)求之前推送到這些節(jié)點(diǎn)的緩存中，因此需要以最快的方法將熱點(diǎn)內(nèi)容擴(kuò)散出去。因?yàn)樵赩-NDN中內(nèi)容傳輸路徑中的節(jié)點(diǎn)都會(huì)緩存該內(nèi)容，所以本文設(shè)計(jì)通過數(shù)據(jù)請(qǐng)求者來推送熱點(diǎn)內(nèi)容。車輛節(jié)點(diǎn)通過熱點(diǎn)內(nèi)容挖掘算法得到熱點(diǎn)內(nèi)容表，然后將熱點(diǎn)內(nèi)容表中內(nèi)容名稱對(duì)應(yīng)的數(shù)據(jù)包標(biāo)記為熱點(diǎn)內(nèi)容。在NDN中可以通過向熱點(diǎn)內(nèi)容數(shù)據(jù)包添加標(biāo)簽的方式標(biāo)記熱點(diǎn)內(nèi)容。同時(shí)，熱度消退問題通過熱點(diǎn)內(nèi)容表中的時(shí)間戳控制。如圖4所示，A到H代表車輛節(jié)點(diǎn)，節(jié)點(diǎn)外的虛線圓代表該節(jié)點(diǎn)的通信范圍，c代表內(nèi)容。其中G節(jié)點(diǎn)為數(shù)據(jù)請(qǐng)求者，G節(jié)點(diǎn)請(qǐng)求內(nèi)容c，而內(nèi)容c的數(shù)據(jù)提供者為節(jié)點(diǎn)D。當(dāng)D節(jié)點(diǎn)通過熱點(diǎn)內(nèi)容挖掘算法得出內(nèi)容c為熱點(diǎn)內(nèi)容后，會(huì)給內(nèi)容c添加熱點(diǎn)標(biāo)簽。G節(jié)點(diǎn)在收到內(nèi)容c后發(fā)現(xiàn)是熱點(diǎn)內(nèi)容，就會(huì)將其推送給節(jié)點(diǎn)F和H。在數(shù)據(jù)包傳輸路徑中的節(jié)點(diǎn)，例如節(jié)點(diǎn)B并不會(huì)推送該熱點(diǎn)向自己的鄰居節(jié)點(diǎn)。選擇這樣推送的原因是：（1）V-NDN中車輛節(jié)點(diǎn)的傳輸距離假設(shè)在100 m左右，車輛節(jié)點(diǎn)沿道路行駛，而道路對(duì)車輛節(jié)點(diǎn)行駛軌跡的約束導(dǎo)致熱點(diǎn)內(nèi)容在沿道路傳輸時(shí)，路徑中的節(jié)點(diǎn)都會(huì)緩存該內(nèi)容，因此熱點(diǎn)傳輸路徑中的節(jié)點(diǎn)并不會(huì)推送熱點(diǎn)內(nèi)容。（2）為了將熱點(diǎn)內(nèi)容推送到網(wǎng)絡(luò)中可能會(huì)訪問這些內(nèi)容的節(jié)點(diǎn)上，需要擴(kuò)大熱點(diǎn)內(nèi)容在網(wǎng)絡(luò)中的分布范圍，同時(shí)為了降低網(wǎng)絡(luò)中數(shù)據(jù)包副本的數(shù)量，需要限制熱點(diǎn)內(nèi)容推送的范圍，因此本文在熱點(diǎn)到達(dá)數(shù)據(jù)請(qǐng)求者時(shí)，由數(shù)據(jù)請(qǐng)求者將熱點(diǎn)內(nèi)容推送給其鄰居節(jié)點(diǎn)，因?yàn)橥扑偷奈恢锰幱跓狳c(diǎn)傳輸過程的末端，所以既擴(kuò)大了網(wǎng)絡(luò)中熱點(diǎn)的分布范圍，又抑制了熱點(diǎn)內(nèi)容數(shù)據(jù)包過度的擴(kuò)散。

Fig.4 Schematic diagram of hot content push圖4 熱點(diǎn)內(nèi)容推送示意圖

基于以上分析，提出熱點(diǎn)內(nèi)容推送算法，算法步驟如算法2所示。

算法2熱點(diǎn)內(nèi)容推送算法

輸入：車輛節(jié)點(diǎn)vj，vj的熱點(diǎn)內(nèi)容表HLj，內(nèi)容名稱為m的數(shù)據(jù)包Dm。

輸出：vj的熱點(diǎn)內(nèi)容表HLj。

4 理論分析

4.1 V-NDN網(wǎng)絡(luò)建模

在對(duì)V-NDN網(wǎng)絡(luò)進(jìn)行建模之前，需確定在VANET中時(shí)間是連續(xù)的，而本文在不影響建模真實(shí)度的情況下，將連續(xù)的時(shí)間劃分為等長的時(shí)間片，即，第k個(gè)時(shí)間段通過tk=[tk,tk+1)表示，下文中通過t表示時(shí)間。

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

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

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

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

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

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

4.2 熱點(diǎn)挖掘建模

在熱點(diǎn)內(nèi)容推送過程中，首先需要數(shù)據(jù)提供者通過熱點(diǎn)內(nèi)容挖掘算法找到熱點(diǎn)內(nèi)容，接下來將詳細(xì)講述熱點(diǎn)內(nèi)容挖掘的理論分析。

假設(shè)車輛的通信范圍是一個(gè)圓，那么車輛v在道路行駛過程中，在時(shí)間t內(nèi)可能有n個(gè)進(jìn)入車輛v可通信范圍的車輛?？芍囕vv在t時(shí)間遇到n個(gè)新的節(jié)點(diǎn)的概率服從泊松分布[14]，即：

其中，t為正數(shù)，λ為單位時(shí)間內(nèi)車輛遇見新節(jié)點(diǎn)的次數(shù)，由車輛的通信范圍和道路上的車輛密度決定。

那么車輛v在t時(shí)間有n個(gè)鄰居節(jié)點(diǎn)時(shí)，接收到請(qǐng)求內(nèi)容為c的興趣包的概率可由式（2）計(jì)算得出：

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

通過式（1）和式（2），可以計(jì)算出車輛v在時(shí)間t接收到內(nèi)容為c的興趣包的概率為：

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

車輛v中內(nèi)容c在時(shí)間t成為熱點(diǎn)內(nèi)容的概率，可通過馬爾可夫鏈計(jì)算。設(shè)V-NDN中的內(nèi)容有兩個(gè)狀態(tài)：普通狀態(tài)和熱點(diǎn)狀態(tài)；1代表普通狀態(tài)，2代表熱點(diǎn)狀態(tài)。通過馬爾可夫鏈對(duì)內(nèi)容c建模，其中c∈C(t)?？傻脿顟B(tài)轉(zhuǎn)移概率矩陣Pc(t)：

可知當(dāng)內(nèi)容c在t-1時(shí)間為普通狀態(tài)，在t時(shí)間為熱點(diǎn)狀態(tài)的狀態(tài)轉(zhuǎn)移概率p12(t,c)可以通過如下公式計(jì)算：

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

同理，狀態(tài)轉(zhuǎn)移概率p21(t,c)、p22(t,c)通過如下公式計(jì)算：

本文中將以上四個(gè)狀態(tài)轉(zhuǎn)移概率的初始值設(shè)為0.5。

因此，車輛中內(nèi)容c在時(shí)間t成為熱點(diǎn)內(nèi)容的概率為：

最終可得車輛中內(nèi)容c在時(shí)間t的熱度的Hv(t,c)計(jì)算公式為：

其中，γ∈[0,1]是調(diào)整上一時(shí)間t-1對(duì)這一時(shí)間t影響的參數(shù)。

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

5 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

5.1 仿真場景

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

Table 1 ndnSIM experimental parameters表1 ndnSIM實(shí)驗(yàn)參數(shù)

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

Table 2 Vehicle node movement trajectory parameters表2 車輛節(jié)點(diǎn)移動(dòng)軌跡參數(shù)表

5.2 熱點(diǎn)內(nèi)容推送實(shí)驗(yàn)及分析

為了評(píng)估熱點(diǎn)內(nèi)容推送算法的性能，在仿真中與貪婪轉(zhuǎn)發(fā)策略進(jìn)行比較，貪婪轉(zhuǎn)發(fā)策略是由Wang等人在文獻(xiàn)[6]中提出，其團(tuán)隊(duì)在之后的文獻(xiàn)[7]和文獻(xiàn)[8]中將其作為V-NDN的轉(zhuǎn)發(fā)策略。本實(shí)驗(yàn)是在貪婪轉(zhuǎn)發(fā)策略的基礎(chǔ)上，添加了熱點(diǎn)內(nèi)容推送算法。實(shí)驗(yàn)中設(shè)置200個(gè)數(shù)據(jù)請(qǐng)求者，20個(gè)數(shù)據(jù)生產(chǎn)者。

首先考慮請(qǐng)求滿足率，請(qǐng)求滿足率是數(shù)據(jù)請(qǐng)求者收到數(shù)據(jù)包的個(gè)數(shù)與數(shù)據(jù)請(qǐng)求者產(chǎn)生興趣包個(gè)數(shù)的百分比。請(qǐng)求滿足率用來衡量數(shù)據(jù)請(qǐng)求者產(chǎn)生興趣包并獲得相應(yīng)數(shù)據(jù)包的成功率。如圖8所示為請(qǐng)求滿足率對(duì)比圖，圖中虛線為貪婪轉(zhuǎn)發(fā)策略，實(shí)線為添加熱點(diǎn)內(nèi)容推送后的結(jié)果，其中數(shù)據(jù)為每5 s的平均值。由本圖可知在60 s以后數(shù)據(jù)接近平穩(wěn)，請(qǐng)求滿足率穩(wěn)定在65%左右，添加熱點(diǎn)內(nèi)容推送后請(qǐng)求滿足率的提升率在4.6%到14.1%之間。

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

Fig.8 Request satisfaction rate圖8 請(qǐng)求滿足率

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

最后通過興趣包滿足的平均延遲來對(duì)比分析熱點(diǎn)內(nèi)容推送算法對(duì)貪婪轉(zhuǎn)發(fā)策略的優(yōu)化程度。興趣包滿足平均延遲為節(jié)點(diǎn)發(fā)出興趣包到接收到數(shù)據(jù)包之間的時(shí)間。當(dāng)節(jié)點(diǎn)的應(yīng)用層發(fā)出興趣包后，在節(jié)點(diǎn)本地的CS中匹配到了所需的數(shù)據(jù)包，那么此興趣包滿足的延遲為0 s。如圖10為興趣包滿足的平均延遲，圖中數(shù)據(jù)每秒統(tǒng)計(jì)一次。由圖可知，在20 s左右首次找到了熱點(diǎn)內(nèi)容，圖中實(shí)線有多個(gè)延遲為接近0 s的時(shí)間段，說明在這些時(shí)間段內(nèi)，興趣請(qǐng)求者直接在自己的緩存中得到了所請(qǐng)求的數(shù)據(jù)，證明熱點(diǎn)內(nèi)容挖掘的有效性，同時(shí)降低了興趣包滿足的延遲。

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

6 結(jié)論

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