基于NDN的區分調度提升樹轉發策略研究

魯 歡，郭永安，陳春玲

(南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210023)

0 引 言

車聯網(internet-of-vehicles，IoV)是物聯網在智能交通領域里的重要應用，受到了國內外研究人員的廣泛關注。車聯網通過使用GPS定位衛星、基站和路邊的設施來完成車輛和車輛之間，車輛和路邊單元(RSU)之間的通信，使車輛之間可以通信，交換數據、信息等，以提供道路安全、娛樂和其他路邊服務[1]。車聯網相較于一般的網絡具有網絡拓撲結構變化迅速，車輛之間短暫間歇性連接等特性。TCP/IP體系由于其設計之初的局限性，難以適應車聯網快速移動變化的特性，這使基于TCP/IP的車聯網面臨巨大的挑戰。

命名數據網絡(named data networking，NDN)[2]是信息中心網絡(ICN)[3]多個方案中比較突出的一個，是新一代網絡架構。NDN是一種以內容為中心的網絡，取代了端到端的通信模式[4]，同時，具有對移動性支持良好、不依賴網絡地址和會話連接，多網絡尋址等特點，在移動環境下更具優勢，且延遲低、擴展性強，使得網絡性能增強，給車聯網提供了新的可行方案。

在車聯網中，盡管基于NDN的車聯網能減少移動性的問題，但車輛在網絡中的快速移動，有時難以進行有效地通信和節點之間的數據傳輸[1]。此外，基于NDN的車聯網還面臨著車輛分布的隨機性和不均勻性、RSU設施和無線網絡的配置、車輛存儲空間不足等問題。因此，文中提出了區分調度提升樹轉發策略，其目的是為解決網絡擁塞、時延較高、緩存命中率不高等問題，提升轉發策略的性能，實現更高效的數據轉發。

1 NDN及其轉發策略

1.1 路由及轉發

NDN在功能上對其架構設計進行了分離，分為路由平面和轉發平面。路由平面指提供轉發數據可選擇的轉發端口的信息，轉發平面根據轉發策略從可選擇的轉發端口中選擇合適端口進行轉發[5]。NDN中有3種數據結構非常重要，分別為內容倉庫(content store，CS)、轉發興趣表(forwarding information base，FIB)以及轉發請求表(pending interest table，PIT)。CS保存路由節點的緩存內容；FIB保存了路由節點到達內容服務器的下一跳接口，為數據的轉發提供多路徑的選擇；PIT保存了未得到響應的興趣包的前綴信息及其到達的接口，以便數據包報文沿途返回[6]。這三個表項與NDN的路由、轉發和緩存都有著密切的聯系。

車聯網中，每個車輛節點都可能同時扮演著三種角色：數據的生產者、搬運者和請求者[7]。隨著車輛用戶需求的改變，其所對應的角色也隨之改變。數據生產者就是數據發布者，生產者根據自身的實際情況，隨時準備接收鄰居節點的數據請求并給出回應。搬運者的工作就是搬運，在其他節點需要數據時，將其所需數據搬運過去。車輛在行駛的途中，會存儲一些數據，當車輛收到廣播的數據請求時，如果CS中恰好有對應的數據，則直接搬運數據。數據的消費者既可以是最先發送興趣包的車輛節點，也可以是曾經搬運過興趣包的車輛節點。數據消費者推動網絡的正常運行。

1.2 轉發策略比較分析

目前車聯網環境下，在對基于NDN的轉發策略研究中，研究的重心主要在提升數據取回效率、降低數據取回時延等方面。根據內容發現方式的不同可以將基于車聯網的NDN轉發策略分為先應式轉發策略、反應式轉發策略和機會式轉發策略三個方面[5]。

先應式轉發策略中，節點主動廣告所持有數據的前綴信息或位置信息等，網絡中的其他節點在收到這些信息后，根據信息更新FIB，并構建更優的傳輸路徑，這會產生較大的廣告開銷。同時，先應式轉發策略本質上采用“拉”方式取回內容，會導致冗余的開銷。其中文獻[8]提出了一種針對流行內容使用布隆過濾器(bloom filter，BF)廣告命名前綴的方案BFR及其改進方案，這是最具代表性的轉發策略。由于車輛的快速移動，簇頭是短暫的，需要不斷地重新選取簇頭，轉發效率較低。

反應式轉發策略按照原路回復的策略轉發到網絡中，洪泛轉發(flooding)[9]是最基本的被動式轉發策略，這種方式為每個接口設置綠色、黃色、紅色三種狀態。路由節點將Interest包轉發給前綴匹配成功且接口狀態不是紅色的接口，但是數量較多，容易引發廣播風暴，網絡性能隨之大幅降低。智能洪泛(smart flooding)[9]是一種改進的洪泛方式，可以在一定程度上緩解網絡風暴，但由于節點狀態更新滯后，重傳次數明顯增加。同時，為了找尋更合適的下一跳節點或數據提供者，感知機制被用于轉發策略中，如距離感知、位置感知和鄰居感知。比較具有代表性的策略有CHANET[10](content-centric mobile ad-hoc networks)、LFBL[11](listen first，broadcast later)與BREB[12](best rout，error broadcast)三種。BRBE是針對CHANET和LFBL改進的轉發策略，保持了LFBL轉發策略下基于距離的設計思路，同時對CHANET轉發策略的三種數據結構進行了整合，增加了路徑恢復功能。該策略可以極大地減少數據的轉發跳數和相同興趣的冗余，但是在移動場景下表現較差，會導致超時重傳或重新選路。

機會式轉發策略采用“存儲-攜帶-轉發”模式，不再主動發現內容，而是使用被動發現的形式，避免了泛洪造成的巨大廣告開銷以及拓撲變化導致的路由失效，但是會產生巨大的傳輸時延。其中具有代表性的是STIR[13]轉發策略和STCR[14]轉發策略，STIR轉發策略使用了梯度場的概念，根據節點間的時空相關性構建生產者到提供者的梯度場，形成最小延遲的傳輸路徑，從而實現機會路由轉發。但此算法面臨收斂速度慢的缺陷，導致起始路徑的準確性較低。STCR轉發策略利用節點間的社會關系作為輔助，通過節點間的新鮮度和相遇頻率計算此節點的社會關系，在節點匹配時交換本地社交關系表并更新。但是此轉發策略只考慮了單個社區間的路由轉發，沒有考慮社區間的路由轉發。

這三類轉發策略普遍存在開銷較大、時延較高、網絡性能較低、冗余較多等問題，針對這些問題，提出一種區分調度提升樹算法，提高網絡性能和轉發性能。

2 區分調度提升樹算法

由于車聯網環境網絡拓撲變化快且車內節點緩存不足，利用傳統的轉發策略很難將數據信息快速、及時、準確地轉發出去。因此，針對當前轉發策略的缺點和問題，提出了一種區分調度提升樹算法(diffserv dispatch boosting decision tree，DDBDT)。該算法通過區分服務類型和服務緊急程度，使用調度算法生成優先權隊列，訓練樣本集，使用加權模型操作子決策樹生成提升樹，選擇最優轉發接口，實現最優轉發。

2.1 區分服務模型

區分服務模型中，逐跳行為主要有加速轉發(expedited forwarding，EF)、確保轉發(assured forwarding，AF)和盡力而為(best-effort，BE)三種類別[15-16]，三種類型的逐跳行為對于帶寬資源的優先權要求依次降低。EF是優先級最高的服務，它要求端口保證該類型的分組能夠實現較低時延和防抖，能夠保持配置的速率轉發出去。AF是優先級次高的服務，屬于AF的分組將盡量不被丟棄，基本上保證分組的轉發，AF中定義了四個子類和三個分組丟棄優先級，子類數字大的優先級高，分組丟棄優先級低的會優先被丟棄。必要時，AF所占用的帶寬資源可以暫時被更高優先級的服務占用。BE是優先級最低的行為，不會提供任何服務質量的保證。

具體車輛服務類型所對應的逐跳行為如表1所示。

表1 服務類型的具體逐跳行為

同時，根據服務的緊急程度從高到低分為一級(Ⅰ級)、二級(Ⅱ級)、三級(Ⅲ級)和四級(Ⅳ級)。同等類型下的服務，高緊急度的服務可以具有更高的優先權，可以進行前插操作，插入到低優先級服務之前，讓緊急程度高的服務更快速地被訪問和處理，實現服務的及時響應和帶寬的合理配置使用。

2.2 加權循環調度算法

加權循環調度算法(weighted round robin，WRR)[14]將不同服務類型、不同緊急程度的數據包進行分類，放在不同的優先級隊列中。相較于低優先級隊列服務，WRR算法會優先操作高優先級隊列服務，但是，在所有優先權隊列服務后通過輪詢的方式進行隊列調度，解決了PQ(priority queue)隊列中低優先級隊列可能餓死的情況。輪詢采用的方式是允許高優先級隊列發送多個數據包，同時，給予高優先級隊列更高的訪問次數，讓其享受更多的帶寬資源。WRR調度算法適用于大小固定的興趣包或差異不大的網絡。具體示意圖如圖1所示。WRR算法中，服務會采用先進先出的策略進入不同的優先級隊列中，之后進入隊列的服務，會比較服務的緊急程度，根據服務的緊急程度進行插隊服務，緊急程度高的服務可以插入到緊急程度低的服務之前，從而更快被訪問，提供更高效的服務。

圖1 WRR算法

2.3 提升樹

提升樹(boosting decision tree)是集成學習中的一個重要方法，是將弱分類器線性相加組裝成一個強分類器。提升樹是以決策樹為基樹的提升方法，采用加法模型和前向分步算法，損失函數使用平方誤差函數[17]。文中的提升樹采用4種屬性信息：端口平均時延、端口PI計數、數據的熱度值、興趣包的類別。RTT描述的是興趣包轉出到數據包返回的往返時間，可以了解端口的擁塞情況和時延。PI計數描述端口中已轉發但待返回的興趣包和數據包的個數，PI的數量反映了節點的擁塞情況。熱度描述的是此興趣包的請求頻率，反映了這段時間內用戶的需求。高熱度的數據請求頻率高，數據可能緩存在附近的節點，請求數據所需要的時延、跳數都會相應減少，反映了端口內的緩存情況。不同類別的數據對于網絡延時、擁塞、性能、開銷等方面的要求是不一樣的，興趣包的類別可以在一定程度上反映數據的分布情況和端口的選擇情況。具體提升樹流程如圖2所示。文中對訓練集集合分別隨機選擇屬性權重，使用權重處理樣本，計算損失函數，根據損失函數和樣本生成子決策樹；依據損失函數更新下一個屬性權重，生成帶權重的樣本，繼而生成另一個子決策樹，通過迭代生成所有子決策樹，采用加法模型操作子決策樹生成提升樹。

圖2 提升樹流程

2.4 區分調度提升樹流程

根據上述研究可得，區分調度提升樹執行過程如下所示：

算法：DDBDT算法

輸入：興趣包集合I

輸出：興趣包集合I所對應的轉發端口P

步驟1：興趣包進入端口，進行CS和PIT查詢，CS匹配成功，則直接傳回數據包；PIT匹配成功，則在PIT中記錄下請求端口并丟棄此興趣包；

步驟2：區分服務類型和緊急度，興趣包I選擇EF、AF、BE服務類型和緊急程度；

步驟3：興趣包I根據類型進入相對應優先權隊列，執行隊列調度算法；

步驟4：生成提升樹，選擇轉發端口進行數據轉發。

DDBDT算法的具體工作流程如圖3所示。

圖3 DDBDT流程

當節點收到興趣包后，先進行CS和PIT查詢匹配，若CS匹配成功，則直接返回數據包；若未匹配上CS，則查詢PIT，若PIT中存在表項，說明已有相同請求在處理，則丟棄興趣包并記錄興趣包來源。之后，對興趣包的服務類型和緊急程度進行分類，進入相對應的EF、AF、BE優先權隊列，使用WRR隊列調度算法進行出隊操作，依據屬性信息對樣本進行訓練，生成提升樹，選擇最優端口進行數據轉發。

3 實驗結果及分析

3.1 實驗設置

考慮車聯網節點的高移動性、間歇連續性，通過道路交通模擬軟件SUMO來獲取特定道路場景下汽車的移動情況，從而反映真實的實驗數據。圖4選取仙林大學城附近的一段交通道路，運用SUMO軟件生成的道路交通圖，設置了道路的車輛的流量和移動速度等多種信息。選取的道路交通圖是真實路段，有雙向單車道，有單向車道，也有雙向四車道。節點運動速度在40 km/h～80 km/h，初始位置是隨機分布的，內容請求者每秒發送一個請求，仿真時間為200 s。同時，該文采用基于NS-3的NDN模擬器ndnSIM，這是一個開源網絡仿真平臺，通過該平臺完成對NDN轉發策略性能的仿真和評估。

圖4 仿真道路交通圖

3.2 實驗結果及分析

該文選取經典的智能泛洪轉發策略、BRBE轉發策略作為對比策略，選取的評價指標有：

平均時延:從興趣包的發出到數據包的返回經過的時間。

興趣包滿足率:成功返回數據包的所對應的數據包的數量和實驗中全部興趣包的數量之間的比例。

興趣包滿足率與節點數目的關系如圖5所示。

圖5 興趣包滿足率

圖5中，DDBDT轉發策略隨著節點數目的增多興趣包滿足率不斷上升。當節點數目在40個時，DDBDT興趣包滿足率比智能泛洪轉發策略高5.2%，比BREB轉發策略高3.5%；而節點數目達到80個時，DDBDT興趣包滿足率比智能泛洪轉發策略高8.9%，比BREB轉發策略高5.1%。

隨著節點數目的增加，網絡的連通性更加完善，興趣包滿足率也隨之增加。智能泛洪轉發需要廣播大量節點以尋找目標節點，因此在節點數目較低時興趣包滿足率較高，但隨著節點數目的增加，需要廣播的節點太多，興趣包滿足率最低。車輛的快速移動導致車輛間距離不斷改變，BREB轉發策略會導致重傳，興趣包滿足率也相對較低。區分調度提升樹算法先對服務進行區分，更加具有針對性，同時決策選擇最優轉發接口，興趣包滿足率較高。

平均時延與節點數目的關系如圖6所示。

圖6 平均時延

圖6中，DDBDT轉發策略相較于Smart Flooding轉發策略在節點數目為40個時，平均時延低了10.9 ms；在節點數目為80個時，平均時延低了25 ms。DDBDT轉發策略在節點數目為40個時，平均時延相較于BREB轉發策略低了9.3 ms，在節點數目為80個時，DDBDT轉發策略相較于BREB轉發策略平均時延低了14.6 ms。

平均時延隨著節點數目的增加而不斷增加，智能泛洪轉發策略的節點狀態更新滯后，重傳次數明顯，需要耗費大量的時延。BREB轉發策略沒有充分使用節點中的緩存數據，同時在車輛快速移動環境下，距離的迅速改變，會導致重傳和重新選路，會產生較大的時延，該文提出的區分調度提升樹算法根據興趣包的內容、端口的實際狀況、端口內的緩存選擇最優的轉發接口，只產生較小的時延。

4 結束語

文中闡述了NDN在車聯網環境中發展的局限性以及NDN轉發策略研究的重要性，車聯網環境下車輛的快速移動，車輛間連接的不穩定性，NDN轉發策略存在時延較高、沒有充分利用節點內緩存等缺點，提出了一種區分調度提升樹算法。在ndnSIM平臺對該算法和兩種典型轉發策略進行仿真實驗，實驗表明區分調度提升樹算法具有更高的興趣包滿足率和更低的時延。

文中對轉發策略的時延、興趣包滿足率進行對比，在此基礎上，筆者將考慮將丟包率、冗余性、跳數等指標進行進一步的考量，同時將進一步優化算法，使其在車輛網環境下有更好的性能。