命名數(shù)據(jù)網(wǎng)絡中利用緩存決策的PAWF策略*

葉小琴，　楊　震，　鮮　敏，　趙　麗

(1.四川省裝備制造業(yè)機器人應用技術(shù)工程實驗室，四川 德陽 618000;2.山西大學 軟件學院，山西 太原 030013)

命名數(shù)據(jù)網(wǎng)絡(named data networking，NDN)[1]在未來互聯(lián)網(wǎng)的信息中心架構(gòu)和無線自組織網(wǎng)絡方面具有非常廣闊的前景.NDN的特點是對易錯信道和時變拓撲結(jié)構(gòu)進行廣播，然而，現(xiàn)有的轉(zhuǎn)發(fā)策略對NDN網(wǎng)絡性能造成了諸多不利影響[2]，需要考慮新的NDN轉(zhuǎn)發(fā)準則以應對無線鏈路和節(jié)點移動性問題.有文獻提出了主動式轉(zhuǎn)發(fā)[3]，就是各節(jié)點周期性地通過網(wǎng)絡傳輸來控制數(shù)據(jù)包.每一個數(shù)據(jù)發(fā)送請求都能迅速地獲取源節(jié)點與目的地節(jié)點之間的路由.然而，這種持續(xù)主動的傳輸方式不適用于移動節(jié)點，且會導致大量的信息開銷.在反應式轉(zhuǎn)發(fā)中，節(jié)點在需要時才會傳輸其控制的數(shù)據(jù)包，這樣就可以節(jié)約更多帶寬.但是在路由發(fā)送數(shù)據(jù)之前，節(jié)點不得不等待相當長的一段時間才能對該路由進行評估.盲目轉(zhuǎn)發(fā)(blind forwarding，BF)方式[4]，則是通過一種最簡單的拓撲結(jié)構(gòu)未知策略，以解決低效廣播風暴問題，但是BF策略僅采用包監(jiān)聽和延遲定時器以支撐多條轉(zhuǎn)發(fā)，雖然能夠減少廣播風暴的發(fā)生率，但是不能消除擁堵和冗余度[5].因此，本文提出了利用緩存決策技術(shù)的提供商感知轉(zhuǎn)發(fā)(provider aware forwarding，PAWF)策略，該策略在轉(zhuǎn)發(fā)決策過程中利用一個或多個內(nèi)容來源的額外信息，即在轉(zhuǎn)發(fā)中融合了興趣/數(shù)據(jù)包的額外字段，而在額外字段中攜帶了準提供商的信息，使得提供商信息位于網(wǎng)絡的每個節(jié)點，并基于該額外信息做出最終轉(zhuǎn)發(fā)決策.仿真結(jié)果表明，PAWF可以進一步提高NDN信息傳送的性能.

1　提供商感知轉(zhuǎn)發(fā)策略

PAWF是一種基于先偵后播(listen first broadcast later，LFBL)[6]和E-CHANET策略的方法.LFBL最初的設計目的是作為多跳無線網(wǎng)絡的一種轉(zhuǎn)發(fā)策略，此處的多跳無線網(wǎng)絡采用數(shù)據(jù)為中心的尋址方式，并沒有對NDN體系結(jié)構(gòu)進行具體參考，即在最初的文獻中并沒有提到NDN表，包括轉(zhuǎn)發(fā)信息庫(forwarding information base，F(xiàn)IB)、內(nèi)容存儲(content store，CS)以及待定興趣表(pending interest table，PIT).唯一的強制性數(shù)據(jù)結(jié)構(gòu)是距離表(distance table，DT)，距離表中記錄了每個節(jié)點和通信端點間的距離信息[7].LFBL有三種包類型：數(shù)據(jù)請求REQ、數(shù)據(jù)回應REP，以及確認應答ACK.數(shù)據(jù)檢索步驟為：首先，在網(wǎng)絡中利用控制洪泛策略傳送REQ以發(fā)現(xiàn)可利用的提供商；然后，用戶選取一個提供商，并生成ACK包確認；最后，采用基于距離的轉(zhuǎn)發(fā)策略確認每個中間節(jié)點是否通過檢查其DT轉(zhuǎn)發(fā)后續(xù)REQ.類似地，在E-CHANET中也采用了一種基于距離的轉(zhuǎn)發(fā)策略.與LFBL方法不同的是，E-CHANET中參考了NDN的體系結(jié)構(gòu).

如圖1所示，給出了PAWF的主要處理過程.PAWF采用了LFBL和E-CHANET策略的主要原理，在BF機制上進行設計，并且融合了其他的NDN模型(緩存和數(shù)據(jù)結(jié)構(gòu)).除了傳統(tǒng)的NDN表之外，網(wǎng)絡中每個節(jié)點均保存DT、提供商標識符(provider identifier，ID)和跳距離.根據(jù)分層NDN命名策略，假設一組常見的數(shù)據(jù)內(nèi)容如視頻、文本或圖像等，與一個唯一的持久層次名稱如視頻Trip/Alice 2016相關(guān)聯(lián).而該給定的內(nèi)容可以劃分成多個碎片，這些碎片分布在多個數(shù)據(jù)包之中，對這些數(shù)據(jù)包進行連續(xù)編號，如視頻Trip/Alice 2016/0、視頻Trip/Alice 2016/1等.用戶C對第一個有興趣即進行視頻Trip/Alice 2016/0傳播請求，并且根據(jù)BF策略在網(wǎng)絡中對其進行散播.提供商P接收到這個請求，則以應答數(shù)據(jù)包進行回復，數(shù)據(jù)包含有兩個額外的字段以傳輸唯一ID，并且將跳距離初始化為1.一旦節(jié)點接收到數(shù)據(jù)，則每個維護PIT條目的節(jié)點N在DT過程中存儲整體數(shù)據(jù)內(nèi)容的名稱、視頻Trip/Alice 2016、P的標識符和到節(jié)點的距離.然后，N增加一條距離字段，并且通過計算TData的延遲時間周期性地對數(shù)據(jù)進行重新廣播.接收到數(shù)據(jù)之后，用戶在其DT中包含了提供商的信息，并且通過將提供商ID和到用戶的距離包含到興趣包中進行發(fā)送.利用Tinterest和TData的時間值分別表示興趣和數(shù)據(jù)的重播事件.由于NDN通信的局部多跳特性，可以發(fā)現(xiàn)多個提供商，用戶C能夠在這些提供商中選取距離自身最近的提供商.每個中間節(jié)點接收到興趣之后對DT進行檢查，這是為了驗證該中間節(jié)點到提供商的距離是否小于用戶到提供商的距離.如果驗證結(jié)果為真，則對距離字段進行更新，并計算出Tinterest的延遲時間以對興趣進行廣播.利用延遲窗口DW隨機地計算出Tinterest和TData，并利用一個整數(shù)表示時間間隔的長度，計算過程如下：

TData=rand[0,DW-1]-Ts,Tinterest=(DW+rand[0,DW])·Ts,

式中Ts延遲時隙表示一個較短的時間間隔.在不相交的間隔中選取Tinterest和TData，通過Tinterest>TData可以獲取對數(shù)據(jù)包的較高存取優(yōu)先級.TData對提供商來說就是一個擁堵避免定時器，而Tinterest對于轉(zhuǎn)發(fā)者來說是一個擁堵避免定時器，利用Tinterest可以進行興趣抑制.

PAWF采用了網(wǎng)絡中緩存決策技術(shù)，從而提高數(shù)據(jù)傳輸性能，一個保存了數(shù)據(jù)緩存副本的中間節(jié)點N能夠回應請求，且過程并不需要將興趣轉(zhuǎn)發(fā)給選取的提供商.

考慮N個節(jié)點和L個鏈路組成的NDN.網(wǎng)絡拓撲可使用無向圖G={N,L}表示，N={1,2,…,N},L={1,2,…,L}.令γk為鏈路k的數(shù)據(jù)傳輸率，k∈L，令F表示流量，則有

式中ρi,j表示節(jié)點i與j之間利用PAWF轉(zhuǎn)發(fā)的路徑，第i個節(jié)點的權(quán)重ωi定義為：

此外，在PAWF中還采用了一種額外特征，允許用戶知曉一些數(shù)據(jù)包或者所有數(shù)據(jù)內(nèi)容，但前提是這個節(jié)點位于其CS之中.如果節(jié)點N擁有所有數(shù)據(jù)內(nèi)容或者所有內(nèi)容的緩存，則將其標識符放置到數(shù)據(jù)包中，這樣用戶C即能夠選其為提供商完成后續(xù)的請求.如果節(jié)點N僅存儲了部分的數(shù)據(jù)內(nèi)容，則這個節(jié)點就將最初提供商的ID包含在數(shù)據(jù)包中，以避免用戶錯誤地將這個節(jié)點選作為提供商.如果節(jié)點的DT之中并不存在任何提供商的ID信息，那么節(jié)點N在其相關(guān)字段中不指定任何提供商，用戶C不對其DT中的信息進行更新.如果提供商沒有在指定的時間內(nèi)對興趣進行回復，則用戶認為這個提供商不可到達，然后在其DT之中選取其他的提供商作為其提供商.如果DT之中不存在任何的信息，那么用戶C重新開始盲目轉(zhuǎn)發(fā).

可見，PAWF有助于減少冗余度，而且由于存在隱含終端，PAWF不會完全阻止數(shù)據(jù)副本的存在，這些數(shù)據(jù)副本可以提高傳送的魯棒性.

2　仿真實驗及結(jié)果

為了對所提出的策略設計方法的性能進行測試和比較，需要采用一個仿真框架，這個仿真框架可以對一個NDN節(jié)點的數(shù)據(jù)結(jié)構(gòu)即CS、PIT和FIB進行復制，仿真框架中構(gòu)思的轉(zhuǎn)發(fā)策略需建立在IEEE 802.11之上，并且可以使用戶在不同的無線場景中移動.本文采用NDN軟件模塊，即ndnSIM[8]，這是一種最近發(fā)布的面向ns-3的網(wǎng)絡仿真，仿真環(huán)境遵從NDN通信模型，從而能夠確保獲取精確的試驗結(jié)果以及可再現(xiàn)性.實驗基于上述仿真環(huán)境對BF與PAWF兩種轉(zhuǎn)發(fā)策略的性能進行比較.

實驗采用的仿真場景環(huán)境為：Nn個配備有IEEE 802.11g接口的移動節(jié)點通過模擬拓撲結(jié)構(gòu)中的多條路徑進行通信，這些節(jié)點采用Levy-Walk模型以行人行走的速度移動.將這些節(jié)點的一個子集和NC個節(jié)點作為用戶，每個用戶都發(fā)出不同的內(nèi)容初始化請求，每個內(nèi)容存儲在單個提供商中.提供商放置在尺寸為600 m×600 m的模擬拓撲結(jié)構(gòu)中.每個節(jié)點采用的傳輸和接收設置中，名義上的覆蓋半徑為150 m，并通過瑞利衰落分布對傳播過程進行建模以模擬信道衰減.

實驗選擇在不同流量負載條件下對BF和PAWF策略的性能進行比較，其中用戶個數(shù)NC在2和20之間變化，拓撲結(jié)構(gòu)中的節(jié)點個數(shù)選取Nn=60、120.如圖2所示，網(wǎng)絡中流量負載的增加對BF策略的性能產(chǎn)生了較大的影響，隨著NC的增加，BF完成時間大幅度增加，在節(jié)點密集場景中完成時間變得更長.PAWF的完成時間隨著NC的增加而變化不大，且在節(jié)點密集場景時完成時間也沒有大幅增長.因此，相比于BF策略，PAWF策略擁有更短的完成時間.

節(jié)點密度的變化會影響兩個策略的數(shù)據(jù)冗余度[9].如圖3所示，當節(jié)點密度增加時，可以觀察到BF和PAWF策略數(shù)據(jù)冗余度的值均有增加，但是BF策略增加得更為明顯，這是由于潛在轉(zhuǎn)發(fā)者的個數(shù)增大，BF需要處理更多的內(nèi)容請求；而節(jié)點密度的變化對PAWF策略幾乎沒有產(chǎn)生任何的影響，這是因為PAWF策略試圖在用戶和提供商之間設置一個單一的路徑，避免了大量的內(nèi)容請求.因此，相比于BF策略，PAWF策略具有較低的數(shù)據(jù)冗余.

[1]周蕓韜. 基于MQAAR的移動自組織網(wǎng)絡路由方案[J]. 湘潭大學自然科學學報, 2016, 38(3): 69-73.

[2]QIAO X, NAN G, PENG Y, et al. NDNBrowser: an extended web browser for named data networking [J]. Journal of Network & Computer Applications, 2015, 50(6): 134-147.

[3]黃紹城, 馬林華, 宋博,等. 基于QOS的MPR優(yōu)化選擇算法[J]. 計算機仿真, 2015, 32(7):281-285.

[4]LANDICHO J A. VOISEE COMMUNICATOR: An android mobile application for hearing-impaired and blind communications[J]. International Journal of Interactive Mobile Technologies,2016, 10(4): 22-26.

[5]楊靜, 龔玲玲, 楊正川,等. 帶有模糊控制的機會網(wǎng)絡數(shù)據(jù)轉(zhuǎn)發(fā)控制策略[J]. 系統(tǒng)工程與電子技術(shù), 2016, 38(2): 392-399.

[6]AMADEO M, CAMPOLO C, MOLINARO A, et al. Content-centric wireless networking: A survey[J]. Computer Networks, 2014, 72(7): 1-13.

[7]DELAYE A, LEE K. A flexible framework for online document segmentation by pairwise stroke distance learning[J]. Pattern Recognition, 2015, 48(4): 1197-1210.

[8]劉總真, 葛敬國, 唐海娜,等. 命名數(shù)據(jù)網(wǎng)絡中面向移動用戶的內(nèi)容預取方法[J]. 計算機應用研究, 2016, 33(5): 1441-1445.

[9]陳樹, 韓進, 蔣偉. 低冗余度WSN非均勻分簇算法應用研究[J]. 計算機工程, 2014, 40(8): 10-14.