命名數(shù)據(jù)網(wǎng)絡(luò)中基于Dec-POMDP的緩存策略

姚進(jìn)發(fā)

(銳捷網(wǎng)絡(luò)股份有限公司 銳捷研究院，福建 福州350002）

0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展以及互聯(lián)網(wǎng)用戶的快速增加，網(wǎng)絡(luò)應(yīng)用的主體正逐步向內(nèi)容獲取和信息服務(wù)演進(jìn)。早期為解決端到端通信問(wèn)題而設(shè)計(jì)的基于TCP/IP的體系架構(gòu)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)性能的限制使得傳統(tǒng)互聯(lián)網(wǎng)難以滿足海量的網(wǎng)絡(luò)數(shù)據(jù)處理需求，這激發(fā)了人們對(duì)未來(lái)網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)的重新思考與研究。信息中心網(wǎng)絡(luò)(Information-Centric Networking，ICN）[1]作為一種“革命性”體系架構(gòu)，其以內(nèi)容為中心的特點(diǎn)無(wú)縫迎合了未來(lái)網(wǎng)絡(luò)的發(fā)展趨勢(shì)，因而受到研究學(xué)者的廣泛關(guān)注。在ICN體系的諸多部署方案中，命 名 數(shù)據(jù)網(wǎng)絡(luò)(Named Data Networks，NDN）因其先進(jìn)的設(shè)計(jì)理念、靈活的路由轉(zhuǎn)發(fā)機(jī)制以及分布式的網(wǎng)內(nèi)緩存方式等良好特性已經(jīng)成為ICN中的研究熱點(diǎn)。

為了滿足高效的內(nèi)容分發(fā)與獲取的需求，NDN在設(shè)計(jì)時(shí)通過(guò)引入網(wǎng)內(nèi)緩存(in-network caching）機(jī)制來(lái)減少不必要的網(wǎng)絡(luò)數(shù)據(jù)傳輸，從而提高數(shù)據(jù)傳輸效率，增強(qiáng)網(wǎng)絡(luò)的可擴(kuò)展性。在NDN中，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都具有一個(gè)內(nèi)容存儲(chǔ)庫(kù)(Content Store，CS），用于緩存經(jīng)過(guò)本地節(jié)點(diǎn)的數(shù)據(jù)，從而為后續(xù)與數(shù)據(jù)對(duì)應(yīng)的相關(guān)請(qǐng)求提供路徑緩存服務(wù)。然而，與海量的數(shù)據(jù)相比，網(wǎng)絡(luò)節(jié)點(diǎn)中CS的容量相當(dāng)有限，因此如何合理地進(jìn)行內(nèi)容放置和緩存決策，是影響NDN性能的關(guān)鍵因素。

NDN在設(shè)計(jì)之初默認(rèn)采用處處緩存(Cache Everything Everywhere，CEE）策 略[2]，但 該 方 法 會(huì) 導(dǎo) 致節(jié)點(diǎn)緩存內(nèi)容趨于同質(zhì)化，故無(wú)法充分發(fā)揮網(wǎng)內(nèi)緩存效率。近年來(lái)，學(xué)術(shù)界圍繞NDN緩存技術(shù)的研究已經(jīng)取得了不少成果。文獻(xiàn)[3]針對(duì)CEE策略的緩存冗余問(wèn)題，提出只在請(qǐng)求命中節(jié)點(diǎn)的直接下一跳緩存數(shù)據(jù)(Leave Copy Down，LCD），一定程度上提高了網(wǎng)絡(luò)緩存的利用率，但流行度高的內(nèi)容需要被訪問(wèn)多次才能緩存到邊緣節(jié)點(diǎn)上。文獻(xiàn)[4]提出了一種基于內(nèi)容流行度的協(xié)作緩存策略(WAVE），它根據(jù)內(nèi)容請(qǐng)求次數(shù)以指數(shù)方式逐步增加沿途節(jié)點(diǎn)上所緩存的數(shù)據(jù)包個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)在空間存儲(chǔ)位置上的差異化，但該方案并沒(méi)有考慮內(nèi)容請(qǐng)求序列的相關(guān)性。文獻(xiàn)[5]通過(guò)估算路徑的剩余存儲(chǔ)能力來(lái)計(jì)算同一路徑上的不同數(shù)據(jù)流在沿途各節(jié)點(diǎn)上的緩存概率，從而提出了一種兼顧不同數(shù)據(jù)流間存儲(chǔ)公平性的概率緩存策略(ProbCache）。文獻(xiàn)[6]提出了一種分布式沿途緩存策略，即最大增益網(wǎng)內(nèi)緩存(MAGIC）。網(wǎng)絡(luò)節(jié)點(diǎn)基于內(nèi)容流行度和路由跳數(shù)來(lái)計(jì)算內(nèi)容的緩存增益，并在數(shù)據(jù)傳輸路徑上選擇具有最大緩存增益的節(jié)點(diǎn)進(jìn)行內(nèi)容緩存，從而達(dá)到減少網(wǎng)絡(luò)帶寬消耗的目的。但該方案在進(jìn)行緩存決策時(shí)需要重新計(jì)算各內(nèi)容的流行度，因此計(jì)算量大，執(zhí)行復(fù)雜度高。文獻(xiàn)[7]提出了一種主動(dòng)緩存策略，其主要思想是利用熵來(lái)衡量移動(dòng)性預(yù)測(cè)的不確定性，并定位最佳的預(yù)取節(jié)點(diǎn)，從而降低服務(wù)器負(fù)載，并減少緩存冗余。

針對(duì)NDN的網(wǎng)絡(luò)架構(gòu)特性，本文提出了一種基于Dec-POMDP的NDN緩存策略。首先利用Dec-POMDP理論框架對(duì)NDN網(wǎng)絡(luò)的緩存問(wèn)題進(jìn)行建模，該模型考慮了緩存節(jié)點(diǎn)間的相互協(xié)作，以實(shí)現(xiàn)降低緩存內(nèi)容冗余度和內(nèi)容優(yōu)化存儲(chǔ)的目的。在此基礎(chǔ)上，通過(guò)限制節(jié)點(diǎn)的協(xié)作域的方法來(lái)避免引入過(guò)量的額外通信開(kāi)銷(xiāo)，進(jìn)而降低模型求解的復(fù)雜度。最后，本文給出了一種基于強(qiáng)化學(xué)習(xí)的局部近似最優(yōu)緩存策略的求解算法。仿真結(jié)果表明，該方法能夠有效增加緩存內(nèi)容的多樣性，提升緩存命中率，進(jìn)而減小用戶請(qǐng)求內(nèi)容的總跳數(shù)。

1 NDN工作原理

NDN網(wǎng)絡(luò)中的數(shù)據(jù)傳輸采用基于用戶驅(qū)動(dòng)的“拉”模式數(shù)據(jù)獲取方式。NDN中存在兩種數(shù)據(jù)包類(lèi)型 ： 興 趣 包 (Interest Packet）和 數(shù) 據(jù) 包 (Data Packet）。用戶通過(guò)發(fā)送包含內(nèi)容名稱(chēng)的興趣包來(lái)向網(wǎng)絡(luò)請(qǐng)求數(shù)據(jù)，該請(qǐng)求興趣包將被路由到存有對(duì)應(yīng)數(shù)據(jù)的鄰近節(jié)點(diǎn)或服務(wù)器節(jié)點(diǎn)；然后，攜帶該請(qǐng)求內(nèi)容的數(shù)據(jù)包沿著興趣包的反向路徑被逐跳傳送給數(shù)據(jù)請(qǐng)求者。

如圖1所示，當(dāng)請(qǐng)求興趣包到達(dá)時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)根據(jù)所請(qǐng)求的內(nèi)容名字依次在內(nèi)容存儲(chǔ)庫(kù)(Content Store，CS）、待定興趣表(Pending Interest Table，PIT）和轉(zhuǎn)發(fā)信息庫(kù)(Forwarding Information Base，F(xiàn)IB）中進(jìn)行匹配查詢。若CS中存在與該請(qǐng)求對(duì)應(yīng)的數(shù)據(jù)包則直接將數(shù)據(jù)傳回給請(qǐng)求者；否則，如果PIT中含有與該請(qǐng)求對(duì)應(yīng)的條目，則將該請(qǐng)求的進(jìn)入接口添加到對(duì)應(yīng)條目的接口列表中，然后將該請(qǐng)求拋棄；如果PIT也匹配失敗，則新建一個(gè)PIT條目并查詢節(jié)點(diǎn)的FIB，將請(qǐng)求轉(zhuǎn)發(fā)到下一跳節(jié)點(diǎn)。

圖1 NDN中請(qǐng)求包轉(zhuǎn)發(fā)過(guò)程

當(dāng)節(jié)點(diǎn)收到響應(yīng)數(shù)據(jù)包時(shí)，節(jié)點(diǎn)根據(jù)對(duì)應(yīng)的PIT表項(xiàng)中所記錄的請(qǐng)求接口列表進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，并根據(jù)相應(yīng)的存儲(chǔ)策略將其存儲(chǔ)在節(jié)點(diǎn)的CS中，如圖2所示。

圖2 NDN中數(shù)據(jù)包轉(zhuǎn)發(fā)過(guò)程

2 基于Dec-POMDP的NDN緩存策略

考慮一個(gè)離散時(shí)間的Dec-POMDP動(dòng)態(tài)系統(tǒng)。在每一個(gè)決策時(shí)刻，每個(gè)智能體首先從系統(tǒng)中獲取在當(dāng)前狀態(tài)下各自的觀測(cè)信息，然后做出決策并執(zhí)行動(dòng)作，系統(tǒng)根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)狀態(tài)，并獲得一個(gè)即時(shí)回報(bào)，整個(gè)過(guò)程周而復(fù)始。因此，一個(gè)Dec-POMDP模型通?？梢杂梢粋€(gè)7元組定義[8]：

其中，N={1，…，N}表示系統(tǒng)中所有智能體的集合。S={Si}表示一個(gè)有限的系統(tǒng)狀態(tài)集合，其中Si表示智能體i的內(nèi)部狀態(tài)集。A={Ai}表示所有智能體的聯(lián)合動(dòng)作集，其中Ai表示智能體i的可用動(dòng)作集。Ω={Ωi}表示系統(tǒng)聯(lián)合觀測(cè)的有限集，其中 Ωi為智能體 i的觀測(cè)集。P：S×A→[0，1]表示系統(tǒng)的狀態(tài)轉(zhuǎn)移函數(shù)，p(s′|s，a）表示系統(tǒng)在狀態(tài) s下采取聯(lián)合行動(dòng) a后轉(zhuǎn)移到新?tīng)顟B(tài) s′的概率。O：S×A×S→[0，1]表示系統(tǒng)的觀測(cè)函 數(shù)。 O(o|s，a，s′）表示狀態(tài)s中采取聯(lián)合行動(dòng)a后轉(zhuǎn)移到新?tīng)顟B(tài) s′時(shí)獲得聯(lián)合觀測(cè) o={o1，…，oN}∈Ω 的條件概率。 R：S×A→Z表示系統(tǒng)的效用函數(shù)。R(s，a）表示智能體集合在狀態(tài)s中采取聯(lián)合行動(dòng)a后所獲得的回報(bào)。H表示整個(gè)決策過(guò)程的總周期數(shù)，稱(chēng)為步數(shù)(Horizon）。下面給出關(guān)于NDN緩存問(wèn)題的Dec-POMDP模型中各元組定義。

2.1 網(wǎng)絡(luò)模型及相關(guān)假設(shè)

NDN網(wǎng)絡(luò)模型如圖3所示。網(wǎng)絡(luò)由源服務(wù)器節(jié)點(diǎn)、路由節(jié)點(diǎn)以及用戶節(jié)點(diǎn)構(gòu)成。源服務(wù)器節(jié)點(diǎn)是內(nèi)容數(shù)據(jù)的發(fā)布者，維護(hù)內(nèi)容數(shù)據(jù)的一個(gè)永久副本。路由節(jié)點(diǎn)具備存儲(chǔ)功能，可以緩存經(jīng)過(guò)節(jié)點(diǎn)的部分?jǐn)?shù)據(jù)。用戶節(jié)點(diǎn)通過(guò)邊緣路由節(jié)點(diǎn)向網(wǎng)絡(luò)請(qǐng)求數(shù)據(jù)。用戶請(qǐng)求被逐跳轉(zhuǎn)發(fā)至擁有該請(qǐng)求內(nèi)容的中間路由節(jié)點(diǎn)或源服務(wù)器節(jié)點(diǎn)，并觸發(fā)相應(yīng)數(shù)據(jù)包沿著請(qǐng)求興趣包的反向路徑傳送給請(qǐng)求者。

在NDN中每個(gè)內(nèi)容對(duì)象被劃分成若干相同大小的數(shù)據(jù)塊，并以數(shù)據(jù)塊為單位進(jìn)行存儲(chǔ)。假設(shè)網(wǎng)絡(luò)中共有M種不同的數(shù)據(jù)塊對(duì)象，記為M，且都具有一個(gè)固定的數(shù)據(jù)源?？紤]具有N個(gè)路由節(jié)點(diǎn)的網(wǎng)絡(luò)，節(jié)點(diǎn) n的緩存大小記為 Cn，且 Cn?M；節(jié)點(diǎn)接收來(lái)自本地用戶或相鄰下游節(jié)點(diǎn)所轉(zhuǎn)發(fā)的內(nèi)容請(qǐng)求。節(jié)點(diǎn)n上的轉(zhuǎn)發(fā)接口個(gè)數(shù)記為Fn。假設(shè)網(wǎng)絡(luò)中的用戶請(qǐng)求服從泊松分布，根據(jù)隨機(jī)服務(wù)系統(tǒng)原理，服從泊松分布的輸入流的輸出也服從泊松分布，因此鄰節(jié)點(diǎn)上未命中的請(qǐng)求序列也服從泊松分布。

圖3 NDN網(wǎng)絡(luò)模型

2.2 狀態(tài)和狀態(tài)空間

網(wǎng)絡(luò)中的所有節(jié)點(diǎn)構(gòu)成Dec-POMDP模型的智能體集合 N。記網(wǎng)絡(luò)節(jié)點(diǎn) n的狀態(tài)為 sn=[xn，yn]，其中 xn=[x11，…，x1M，…，xFn1，…，xFnM]表示當(dāng)前時(shí)刻節(jié)點(diǎn)n中各轉(zhuǎn)發(fā)接口上待響應(yīng)的內(nèi)容請(qǐng)求的情況，xfnm表示節(jié)點(diǎn)n中第fn個(gè)接口上關(guān)于數(shù)據(jù)塊m的待響應(yīng)請(qǐng)求數(shù)量；yn=[yn1，…，ynM}表示當(dāng)前時(shí)刻節(jié)點(diǎn) n上 CS中的緩存情況，ynm∈{-1，0，1}表示數(shù)據(jù)塊 m的緩存狀態(tài)。ynm=-1表示節(jié)點(diǎn)n上不存在數(shù)據(jù)塊m的副本；ynm=0表示節(jié)點(diǎn)n上擁有數(shù)據(jù)塊m的臨時(shí)副本，但數(shù)據(jù)塊m不被存儲(chǔ)于節(jié)點(diǎn)的CS中而是僅用于響應(yīng)當(dāng)前請(qǐng)求，且當(dāng)數(shù)據(jù)轉(zhuǎn)發(fā)完成后就會(huì)被立即刪除；ynm=1表示數(shù)據(jù)塊m被存儲(chǔ)于節(jié)點(diǎn)n的CS中。各網(wǎng)絡(luò)節(jié)點(diǎn)的狀態(tài)構(gòu)成當(dāng)前決策時(shí)刻的網(wǎng)絡(luò)狀態(tài)，記為 s=[s1，…，sN]。

2.3 決策時(shí)刻

2.4 行動(dòng)和行動(dòng)空間

由NDN的工作原理可知，當(dāng)收到響應(yīng)數(shù)據(jù)包時(shí)，節(jié)點(diǎn)根據(jù)其CS中的存儲(chǔ)剩余空間以及該內(nèi)容被訪問(wèn)的情況來(lái)決定是否緩存該數(shù)據(jù)包的副本。因此，本文定義NDN節(jié)點(diǎn)接收到響應(yīng)數(shù)據(jù)包的時(shí)刻為有效決策時(shí)刻。具體地，當(dāng)事件或事件發(fā)生時(shí)節(jié)點(diǎn)不進(jìn)行任何存儲(chǔ)決策，此時(shí)節(jié)點(diǎn)n的行動(dòng)記為an=。當(dāng)事件發(fā)生時(shí)，(1）若節(jié)點(diǎn) n的 CS具有剩余存儲(chǔ)空間則直接緩存該數(shù)據(jù)包副本而不需要任何決策，也即采取行動(dòng)an=；(2）若節(jié)點(diǎn) n的 CS中無(wú)足夠存儲(chǔ)空間且節(jié)點(diǎn)需要存儲(chǔ)該數(shù)據(jù)包，那么節(jié)點(diǎn)根據(jù)存儲(chǔ)策略選擇當(dāng)前CS中的某個(gè)數(shù)據(jù)包 k(k∈{1， … ，M}）進(jìn) 行 替 換 ，記為an=；(3）此外，令 an=表示節(jié)點(diǎn)n采取“不存儲(chǔ)該數(shù)據(jù)副本”的行動(dòng)。綜上，網(wǎng)絡(luò)節(jié)點(diǎn)n的行動(dòng)空間An可以表示為：{-1，0，1，…，M}}。進(jìn)而可得到所有網(wǎng)絡(luò)節(jié)點(diǎn)的聯(lián)合行動(dòng)為 a=[a1，…，aN]，以及網(wǎng)絡(luò)節(jié)點(diǎn)的聯(lián)合動(dòng)作

2.5 觀測(cè)空間

在每個(gè)決策時(shí)刻，網(wǎng)絡(luò)節(jié)點(diǎn)先獲取當(dāng)前網(wǎng)絡(luò)狀態(tài)的一個(gè)觀測(cè)然后再進(jìn)行存儲(chǔ)決策。假設(shè)同一時(shí)刻只有一個(gè)事件e∈E發(fā)生。定義節(jié)點(diǎn)的觀測(cè)表示當(dāng)前決策時(shí)刻下該節(jié)點(diǎn)上CS中緩存內(nèi)容的變化情況。具體地，當(dāng)事件生，即節(jié)點(diǎn)接收到數(shù)據(jù)請(qǐng)求或完成數(shù)據(jù)請(qǐng)求服務(wù)時(shí)，定義節(jié)點(diǎn) n的觀測(cè)為 on=yn。 當(dāng)事件生，即節(jié)點(diǎn)n接收到新響應(yīng)數(shù)據(jù)包時(shí)，定義節(jié)點(diǎn)n的觀測(cè)為 on=yn+2Bm，其中 Bi=(0，…，1，…，0）表示第i個(gè)元素為1的單位向量。根據(jù)上述定義可知，當(dāng)Σon≤Cn時(shí)，節(jié)點(diǎn)不需要進(jìn)行決策，當(dāng)Σon=Cn+1時(shí)，節(jié)點(diǎn)需要根據(jù)存儲(chǔ)策略刪除CS中的某個(gè)數(shù)據(jù)塊。進(jìn)而各網(wǎng)絡(luò)節(jié)點(diǎn)的本地觀測(cè)on構(gòu)成網(wǎng)絡(luò)的一個(gè)聯(lián)合觀測(cè) o={o1，…，oN}。

2.6 效用函數(shù)

網(wǎng)絡(luò)性能分析是網(wǎng)絡(luò)優(yōu)化的基礎(chǔ)，網(wǎng)絡(luò)性能評(píng)價(jià)指標(biāo)是判斷網(wǎng)絡(luò)優(yōu)化效果的依據(jù)。常用的評(píng)價(jià)指標(biāo)包括帶寬、時(shí)延、吞吐量等。本文考慮以緩存命中率以及網(wǎng)絡(luò)平均跳數(shù)作為聯(lián)合策略的衡量標(biāo)準(zhǔn)。定義節(jié)點(diǎn)n的效用函數(shù)為：

如果對(duì)于任意聯(lián)合策略向量ω(t），任意初始狀態(tài) s0，有 J(ω*(t），s0）≥J(ω(t），s0），那 么 策 略 ω*(t）為最優(yōu)聯(lián)合策略，其相應(yīng)的最優(yōu)性能值記為J*。

2.7 狀態(tài)轉(zhuǎn)移函數(shù)

由于當(dāng)Σyn≤Cn時(shí)節(jié)點(diǎn)n采用貪婪存儲(chǔ)策略，故不需要進(jìn)行存儲(chǔ)決策，僅考慮在Σyn=Cn+1的情況下，節(jié)點(diǎn)n在內(nèi)部狀態(tài)sn=[xn，yn]上采取行動(dòng)an后轉(zhuǎn)移到下一個(gè)狀態(tài)的概率。

2.8 觀測(cè)概率

定義M3={m|ynm=-1}表示不存在于節(jié)點(diǎn)n上的內(nèi)容集合。根據(jù)節(jié)點(diǎn)觀測(cè)狀態(tài)的定義，可得到如下節(jié)點(diǎn)觀測(cè)概率函數(shù)：

3 基于Dec-POMDP的分布式緩存協(xié)作策略搜索算法

Dec-POMDP模型最優(yōu)策略的求解是一個(gè)NEXP-complete問(wèn)題，即使是小規(guī)模的問(wèn)題也往往需要在巨大策略空間上進(jìn)行最優(yōu)策略搜索，從而限制了其在較大規(guī)模實(shí)際問(wèn)題中的運(yùn)用。鑒于Dec-POMDP模型精確求解所要求的時(shí)間和空間復(fù)雜度高，因此不少學(xué)者致力于模型近似解的研究，通過(guò)利用動(dòng)態(tài)規(guī)劃或者啟發(fā)式算法來(lái)搜索最優(yōu)策略，以緩解模型求解過(guò)程的維度災(zāi)難和計(jì)算復(fù)雜度的問(wèn)題。而Q學(xué)習(xí)算法作為經(jīng)典的強(qiáng)化學(xué)習(xí)算法，近年來(lái)被廣泛應(yīng)用于多智能體系統(tǒng)體系結(jié)構(gòu)模型的求解中[9-13]。此外，理想情況下，節(jié)點(diǎn)通過(guò)感知網(wǎng)絡(luò)全局狀態(tài)信息，并根據(jù)其他節(jié)點(diǎn)所采取的緩存策略進(jìn)行緩存決策，從而實(shí)現(xiàn)網(wǎng)內(nèi)緩存資源配置的全局最優(yōu)化。然而，這種全域節(jié)點(diǎn)間的相互協(xié)作會(huì)帶來(lái)大量的額外通信開(kāi)銷(xiāo)，因此實(shí)際中一般只考慮一定跳數(shù)范圍內(nèi)的節(jié)點(diǎn)協(xié)作方式。這里只考慮一跳的情況，即網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)與相鄰節(jié)點(diǎn)進(jìn)行緩存協(xié)作逐漸達(dá)到整個(gè)網(wǎng)絡(luò)的最優(yōu)聯(lián)合策略?；谏鲜隹紤]，本文采用一種近似的Q學(xué)習(xí)方法來(lái)求解局部最優(yōu)策略。

定義節(jié)點(diǎn)n的鄰居節(jié)點(diǎn)集合為Nn，根據(jù)文獻(xiàn)[14]，假設(shè)網(wǎng)絡(luò)狀態(tài)滿足狀態(tài)轉(zhuǎn)移獨(dú)立性，則可以得到近似局部聯(lián)合觀測(cè)概率為：

4 數(shù)值仿真

為了評(píng)估本方案的性能，本文采用基于NS-3的ndnSIM[15]進(jìn)行仿真。仿真拓?fù)涔灿?00個(gè)節(jié)點(diǎn)，其中1個(gè)源服務(wù)器節(jié)點(diǎn)和20個(gè)客戶端節(jié)點(diǎn)，其余為路由節(jié)點(diǎn)。源服務(wù)器節(jié)點(diǎn)中存儲(chǔ)5 000個(gè)不同的數(shù)據(jù)，每個(gè)數(shù)據(jù)包的大小均為1 024 KB，數(shù)據(jù)包的流行度服從Zipf分布，實(shí)驗(yàn)中參數(shù)α的取值范圍為0.7～1.3。除特殊說(shuō)明外，實(shí)驗(yàn)中路由節(jié)點(diǎn) CS的總?cè)萘吭O(shè)定為數(shù)據(jù)總數(shù)的10%，且初始為空?？蛻舳送ㄟ^(guò)邊緣路由節(jié)點(diǎn)向網(wǎng)絡(luò)請(qǐng)求數(shù)據(jù)，且請(qǐng)求到達(dá)率服從泊松分布。仿真時(shí)間為2 000 s，其余參數(shù)均為固定默認(rèn)值。下面給出本文所提出的基于Dec-POMDP緩存算法與CEE、LCD緩存策略的實(shí)驗(yàn)結(jié)果對(duì)比分析。首先定義如下性能指標(biāo)：

(1）平均緩存命中率：定義為由網(wǎng)內(nèi)路由節(jié)點(diǎn)服務(wù)的請(qǐng)求數(shù)與總的用戶請(qǐng)求數(shù)之比，即：

式中，Req_hitn表示在路由節(jié)點(diǎn)上命中的請(qǐng)求數(shù)量；Req_usern表示路由節(jié)點(diǎn)n上接收到的本地用戶請(qǐng)求個(gè)數(shù)。

(2）平均跳數(shù)減少率：反映由于緩存系統(tǒng)的加入使用戶請(qǐng)求內(nèi)容跳數(shù)減少的比率，定義為：

式中，hop_csi表示緩存命中節(jié)點(diǎn)到請(qǐng)求用戶間的跳數(shù)；hop_seri表示請(qǐng)求用戶到源服務(wù)器節(jié)點(diǎn)間的跳數(shù)；R_count表示總的用戶請(qǐng)求數(shù)。

圖4為不同緩存策略下，用戶請(qǐng)求在網(wǎng)內(nèi)的平均緩存命中率隨Zipf分布參數(shù)α變化的曲線。如圖所示，相比于另外兩種策略，基于Dec-POMDP的緩存策略能夠顯著提高用戶請(qǐng)求的緩存命中率。這是由于Dec-POMDP模型中節(jié)點(diǎn)在進(jìn)行緩存決策時(shí)考慮了鄰居節(jié)點(diǎn)間的緩存協(xié)作，因此能夠有效地減少緩存內(nèi)容的冗余度，提升緩存利用率。此外，隨著參數(shù)α的增大，三種策略的緩存命中率不斷增大；當(dāng)參數(shù)α大于1.1時(shí)，命中率增大的速率有所減緩，這主要是受限于網(wǎng)絡(luò)路由節(jié)點(diǎn)的緩存容量。

圖4 平均緩存命中率隨參數(shù)α變化曲線

圖5為不同緩存策略下，用戶請(qǐng)求的平均跳數(shù)減少率隨Zipf分布參數(shù)α變化的曲線。由于Dec-POMDP模型能夠更好地刻畫(huà)網(wǎng)絡(luò)狀態(tài)的不確定性和用戶請(qǐng)求的隨機(jī)性，因此Dec-POMDP策略能夠更準(zhǔn)確地預(yù)測(cè)請(qǐng)求內(nèi)容的流行度并有選擇性地緩存更有價(jià)值的內(nèi)容，從而有效減少用戶請(qǐng)求所需的跳數(shù)。

圖5 平均跳數(shù)減少率隨參數(shù)α變化曲線

圖6為不同緩存策略下，用戶請(qǐng)求在網(wǎng)內(nèi)的平均緩存命中率隨網(wǎng)內(nèi)存儲(chǔ)總?cè)萘孔兓那€。由圖可知，在不同網(wǎng)內(nèi)存儲(chǔ)容量配置下，基于Dec-POMDP的緩存策略的性能均優(yōu)于CEE和LCD，說(shuō)明本文提出的緩存策略能更有效地利用緩存資源。此外，對(duì)于CEE和LCD兩種緩存策略，當(dāng)網(wǎng)內(nèi)存儲(chǔ)容量小于15%時(shí)，網(wǎng)內(nèi)存儲(chǔ)容量的增加對(duì)平均緩存命中率的提升效果并不明顯；當(dāng)網(wǎng)內(nèi)存儲(chǔ)容量繼續(xù)增加直至達(dá)到35%時(shí)，網(wǎng)內(nèi)請(qǐng)求的平均緩存命中率有顯著提升；此后，網(wǎng)內(nèi)存儲(chǔ)容量繼續(xù)增長(zhǎng)，平均緩存命中率的增長(zhǎng)速度逐漸變緩。這是因?yàn)檫@兩種策略存在緩存冗余，因此無(wú)法充分利用網(wǎng)內(nèi)緩存資源。而基于Dec-POMDP的緩存策略由于能夠處理請(qǐng)求的動(dòng)態(tài)變化，因此在不同網(wǎng)內(nèi)存儲(chǔ)容量下均能更有效地利用緩存資源。

圖6 平均緩存命中率隨網(wǎng)內(nèi)存儲(chǔ)容量變化曲線

圖7為不同緩存策略下，用戶請(qǐng)求的平均跳數(shù)減少率隨網(wǎng)內(nèi)存儲(chǔ)總?cè)萘孔兓那€。從圖中可看出，在不同網(wǎng)內(nèi)存儲(chǔ)容量條件下，三種緩存策略的平均跳數(shù)減少率性能曲線與圖6中對(duì)應(yīng)的曲線趨勢(shì)相符。由于基于Dec-POMDP的緩存策略能夠有效地利用緩存資源，因此在不同網(wǎng)內(nèi)存儲(chǔ)容量下，基于Dec-POMDP的緩存策略相對(duì)于CEE和LCD能夠更有效減少用戶請(qǐng)求所需的跳數(shù)；且隨著網(wǎng)內(nèi)存儲(chǔ)容量的增加，基于Dec-POMDP的緩存策略與另兩種策略間的性能差異越明顯。

圖7 平均跳數(shù)減少率隨網(wǎng)內(nèi)存儲(chǔ)容量變化曲線

5 結(jié)論

NDN作為一個(gè)新型的網(wǎng)絡(luò)體系架構(gòu)，廣泛存在的網(wǎng)內(nèi)緩存是其最重要的特征之一。然而，必須合理地利用NDN中有限的網(wǎng)內(nèi)緩存資源才能充分發(fā)揮NDN網(wǎng)絡(luò)的性能。因此，本文將NDN中的網(wǎng)內(nèi)緩存問(wèn)題抽象為一個(gè)多智能體分布式協(xié)作的Dec-POMDP模型，并將其建模為一個(gè)多目標(biāo)優(yōu)化問(wèn)題?；诰彺嫘阅芘c網(wǎng)絡(luò)通信開(kāi)銷(xiāo)的權(quán)衡，本文僅考慮有限跳數(shù)范圍內(nèi)的網(wǎng)內(nèi)節(jié)點(diǎn)緩存協(xié)作并在該模型的基礎(chǔ)上提出了一種近似Q學(xué)習(xí)的強(qiáng)化學(xué)習(xí)算法以求解局部最優(yōu)緩存策略。仿真實(shí)驗(yàn)結(jié)果表明，基于Dec-POMDP緩存策略能夠根據(jù)用戶請(qǐng)求的動(dòng)態(tài)變化更好地分配緩存資源，從而提高了用戶請(qǐng)求的網(wǎng)內(nèi)緩存命中率，有效地緩解了服務(wù)器壓力。