內(nèi)容中心容遲網(wǎng)絡(luò)中基于訂閱時效的緩存管理機制

羅熹，安瑩，黃家瑋，王建新

?

內(nèi)容中心容遲網(wǎng)絡(luò)中基于訂閱時效的緩存管理機制

羅熹1, 2，安瑩3，黃家瑋1，王建新1

(1. 中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙，410083；2. 湖南警察學(xué)院信息技術(shù)系湖南長沙，410138；3. 中南大學(xué)信息安全與大數(shù)據(jù)研究院，湖南長沙，410083)

基于用戶興趣的時效性對緩存管理決策有著極為重要的影響，將用戶興趣的有效時間運用到消息的丟棄決策中，并提出一種新的基于訂閱時效性的緩存管理機制。該機制定義一個多屬性的效用，從節(jié)點、數(shù)據(jù)消息和用戶興趣等多個角度綜合決定消息的丟棄優(yōu)先級。仿真結(jié)果表明：采用該機制所得消息到達率和分發(fā)速度大，網(wǎng)絡(luò)開銷小。

內(nèi)容中心網(wǎng)絡(luò)；容遲網(wǎng)絡(luò)；訂閱發(fā)布系統(tǒng)；緩存管理；擁塞避免

移動、無線網(wǎng)絡(luò)技術(shù)的快速發(fā)展極大地改變了分布式系統(tǒng)的應(yīng)用范圍和規(guī)模，使大規(guī)模的信息發(fā)布訂閱(publish/subscribe)系統(tǒng)如股票與個性化新聞訂閱系統(tǒng)、分布式拍賣系統(tǒng)、電子市場和電子商務(wù)等得到廣泛應(yīng)用[1]。但由于網(wǎng)絡(luò)拓撲的高動態(tài)性以及節(jié)點多樣性等特征，傳統(tǒng)的基于主機(host centric/host-to-host)的通信方式已無法滿足大規(guī)模、異步和多點松散通信的需求。在發(fā)布訂閱系統(tǒng)中，網(wǎng)絡(luò)用戶往往僅關(guān)心數(shù)據(jù)的內(nèi)容而非內(nèi)容存放的具體位置。Jacobson等[2]提出了內(nèi)容中心網(wǎng)絡(luò)(CCN，content centric networking)的概念，以發(fā)布訂閱方式代替?zhèn)鹘y(tǒng)的端到端通信方式。它將網(wǎng)絡(luò)看成是數(shù)據(jù)內(nèi)容的源，通信的參與者僅需根據(jù)自己的興趣連接到相應(yīng)的內(nèi)容空間來獲取數(shù)據(jù)，而無需預(yù)先建立源端和目的端的連接以及其他先驗知識。通常CCN中包含2種類型：一種是訂閱興趣(interest)，用于描述節(jié)點感興趣的數(shù)據(jù)類型；另一種是數(shù)據(jù)消息(data)，它包含了實際的數(shù)據(jù)內(nèi)容，發(fā)布者產(chǎn)生數(shù)據(jù)消息而無需知道消息訂閱者的具體信息；另一方面，訂閱者通過合適的訂閱信息描述他們的訂閱興趣。在通信過程中，訂閱者向網(wǎng)絡(luò)中廣播他們的興趣分組來訂閱相應(yīng)的內(nèi)容。任何收到該訂閱興趣并擁有相應(yīng)數(shù)據(jù)內(nèi)容的節(jié)點都將予以響應(yīng)，返回對應(yīng)的數(shù)據(jù)分組。網(wǎng)絡(luò)將數(shù)據(jù)消息向感興趣的訂閱節(jié)點交付的過程是基于內(nèi)容而非節(jié)點的地址。當(dāng)2個節(jié)點相遇時，雙方首先交換彼此的訂閱興趣，若節(jié)點緩存中存在匹配興趣的數(shù)據(jù)內(nèi)容，則進行相應(yīng)的數(shù)據(jù)交換。此外，若與之相遇的另一節(jié)點對某個消息不感興趣，但具有比當(dāng)前節(jié)點更高的可能性完成消息交付，當(dāng)前節(jié)點也會將該消息推送給對方，選擇其作為消息的轉(zhuǎn)發(fā)節(jié)點。通過對消息的發(fā)布者(publisher)和訂閱者(subscriber)在時間和空間上的解耦[3]，這種通信方式具有更好的網(wǎng)絡(luò)擴展性及對動態(tài)網(wǎng)絡(luò)的適應(yīng)性，這使得它同樣適用于延遲容忍網(wǎng)絡(luò)(DTNs)的間歇性連通的動態(tài)網(wǎng)絡(luò)環(huán)境。這種通過以內(nèi)容為中心的發(fā)布訂閱方式進行內(nèi)容/服務(wù)訪問的間歇性連通網(wǎng)絡(luò)稱為內(nèi)容中心的延遲容忍網(wǎng)絡(luò)(content centric delay/ disruption tolerant networks, CCDTNs)[4]。在CCDTNs環(huán)境下，節(jié)點間往往缺乏穩(wěn)定的端到端路徑，消息的發(fā)布者和訂閱者可能無法確切知道對方存在，因此，該類網(wǎng)絡(luò)中通常采用存儲—攜帶—轉(zhuǎn)發(fā)機制，利用節(jié)點間機會性的接觸完成消息的交換，并通過多副本路由方式來提高消息的到達率。但隨著網(wǎng)絡(luò)規(guī)模的不斷擴大，訂閱、發(fā)布的消息數(shù)量急劇膨脹，使得節(jié)點資源消耗迅速增加，從而導(dǎo)致網(wǎng)絡(luò)擁塞發(fā)生，因此，消息丟棄機制是實現(xiàn)擁塞避免的一種必要手段。在現(xiàn)有的丟棄策略中，丟棄決策通常依據(jù)節(jié)點的接觸范圍、消息的傳播程度或訂閱節(jié)點的數(shù)量等測度，主要從節(jié)點或數(shù)據(jù)消息的角度來考慮丟棄消息的選擇問題。然而，一些與用戶興趣相關(guān)的重要因素如用戶興趣的有效時間往往被忽略。實際上，用戶興趣的持續(xù)時間可能各不相同。這就是說，對某個消息的訂閱信息也有生存時間，超過該時間，用戶就會失去對該類消息的興趣而不再訂閱。本文提出一種基于訂閱時效性的緩存管理機制(temporal validity based buffer management, TVBBM)。該機制從節(jié)點、數(shù)據(jù)消息以及用戶興趣相關(guān)特性的角度來選擇合適的消息進行丟棄。通過對現(xiàn)有丟棄策略所使用的常用測度的分析，設(shè)計一個新的綜合效用，稱為丟棄效用(dropping utility)。該效用函數(shù)的計算不僅考慮了消息訂閱量、消息的轉(zhuǎn)發(fā)次數(shù)以及節(jié)點的接觸歷史信息，更重要的是考慮了節(jié)點興趣的時效性對消息交付的影響，將節(jié)點興趣的有效時間作為效用計算的重要參數(shù)。該效用可以從節(jié)點自身的角度反映各消息的攜帶價值，從而在擁塞發(fā)生時以此確定消息的丟棄順序，避免擁塞。

1 相關(guān)工作

容遲網(wǎng)絡(luò)中的數(shù)據(jù)分發(fā)往往通過復(fù)制的方式來實現(xiàn)。利用節(jié)點間機會性的接觸，通過同一消息的多個副本在多條路徑上的傳輸增加消息的傳播機會，克服鏈路連接不穩(wěn)定造成的消息到達率不高的缺陷，然而，這同時也增加了資源消耗，從而引發(fā)網(wǎng)絡(luò)擁塞。當(dāng)節(jié)點緩存不足以容納新到達的消息時，必須通過有效的緩存管理機制來選擇消息進行丟棄以釋放緩存空間，避免緩存溢出。目前，許多研究人員針對延遲容忍環(huán)境下的緩存管理機制進行研究，而這些工作的重點主要集中在采用什么測度或標(biāo)準(zhǔn)來對丟棄的消息進行最合理的選擇。現(xiàn)有的丟棄策略中采用的測度大多依據(jù)節(jié)點或消息的相關(guān)特征，據(jù)此，將這些測度分為2類：節(jié)點相關(guān)的測度和消息相關(guān)的測度。

1.1 節(jié)點相關(guān)的測度

部分消息丟棄策略依據(jù)節(jié)點狀態(tài)的相關(guān)測度選擇丟棄行為，因此，將這一類測度稱為節(jié)點相關(guān)的測度(node-related metrics)。典型節(jié)點相關(guān)的測度包括以下內(nèi)容。

1) 節(jié)點接觸歷史。在機會社會網(wǎng)絡(luò)中，節(jié)點間的接觸往往具有一定的社會性。Sammou等[5?8]提出了許多基于節(jié)點接觸歷史的路由算法，通過統(tǒng)計節(jié)點的相遇頻率、接觸范圍等信息來確定消息的轉(zhuǎn)發(fā)順序。然而，它很少應(yīng)用于消息丟棄決策中。直覺上，1個與某消息的目的節(jié)點相遇概率低的節(jié)點在今后一段時間內(nèi)攜帶該消息完成消息交付的概率也很小，因此，本文考慮將節(jié)點的接觸歷史應(yīng)用于消息丟棄算法的設(shè)計中。

2) 流行度。在內(nèi)容中心網(wǎng)絡(luò)環(huán)境下，數(shù)據(jù)是根據(jù)用戶興趣(訂閱信息)來進行分發(fā)的。消息的流行度被定義為網(wǎng)絡(luò)中對該消息感興趣的節(jié)點數(shù)量即該消息訂閱節(jié)點的數(shù)量，它反映了網(wǎng)絡(luò)用戶對某類特定內(nèi)容的需求程度。Bjurefors等[9]提出了2種基于流行度的消息丟棄算法：一種是DMI(drop most interested)，選擇流行度最高的消息予以丟棄。該算法為訂閱節(jié)點數(shù)量少的消息提供了更多的轉(zhuǎn)發(fā)機會，有利于保持網(wǎng)絡(luò)中消息的多樣性，但對消息的整體到達率有一定的負面影響；另一種算法是DLI(drop least interested)，與DMI相反，它選擇丟棄流行度最低的消息。然而，該機制可能導(dǎo)致那些訂閱節(jié)點數(shù)少或關(guān)注度低的消息消亡。

3) 隊列輸入/輸出速率。節(jié)點的隊列長度體現(xiàn)了網(wǎng)絡(luò)通信量負載情況，然而，該測度具有一定的滯后性，無法實時地反映網(wǎng)絡(luò)的擁塞變化趨勢。Burleigh等[10]提出一種基于規(guī)則的自治擁塞控制機制(ACC)。該機制利用隊列的輸入/輸出速率來評估接收新消息的風(fēng)險值，據(jù)此作出消息的接納決策。盡管隊列輸入/輸出速率能實時地捕捉網(wǎng)絡(luò)的擁塞狀態(tài)，但它無法用于選擇丟棄消息的決策。

1.2 消息相關(guān)的測度

消息相關(guān)的測度指與數(shù)據(jù)消息自身屬性相關(guān)的測度，如時間順序、消息的副本數(shù)量及生存周期等。在現(xiàn)有研究中，這類測度主要包括以下內(nèi)容。

1) 副本數(shù)量。由于存儲資源有限，消息的復(fù)制容易導(dǎo)致?lián)砣虼耍瑢崿F(xiàn)擁塞避免的關(guān)鍵之一是控制消息的副本數(shù)量。消息副本的數(shù)量可以反映網(wǎng)絡(luò)中數(shù)據(jù)分發(fā)的深度和廣度。Bjurefors等[9]提出的DMF(drop most forwarded)算法在緩存不足時選擇丟棄具有最大副本數(shù)的消息。這不僅可以釋放緩存空間，緩解局部擁塞，而且能避免消息的過度復(fù)制。然而，在容遲網(wǎng)絡(luò)中很難獲得像消息副本數(shù)量這樣的網(wǎng)絡(luò)全局信息。因此，現(xiàn)有的研究中該測度往往利用本地節(jié)點統(tǒng)計的消息轉(zhuǎn)發(fā)次數(shù)來近似表達。Krifa等[11?13]還提出其他典型的基于副本數(shù)的丟棄算法。

2) 消息的到達時間。采用這一測度的丟棄策略主要根據(jù)消息進入緩存隊列的時間先后來確定消息的丟棄順序，如Lindgren等[14]提出的DL(drop last)和DF(drop front)算法。前者選擇最近到達的消息進行丟棄；而后者則相反，越早進入隊列的消息越先被丟棄。

3) 消息生存時間(TTL)。不論數(shù)據(jù)分發(fā)方式如何不同，消息的交付都必須在其TTL之內(nèi)完成。剩余生存時間在一定程度上反映了該消息的轉(zhuǎn)發(fā)機會。Lindgren等[14]中提出的DY(drop youngest)和DO(drop oldest)就是基于消息生存時間的丟棄策略的典型代表。其中，DY認為消息的剩余生存時間越長，其可能得到的轉(zhuǎn)發(fā)機會越多，因此，節(jié)點應(yīng)該優(yōu)先丟棄剩余生存時間最長的消息而盡可能地為剩余生存時間短的消息提供更多的轉(zhuǎn)發(fā)機會；而DO則認為剩余生存時間越短，在該消息過期之前完成交付的可能性也就越小。因此，選擇緩存中剩余生存時間最短的消息予以丟棄以節(jié)省資源。

1.3 用戶興趣的時效性

除了以上提到的測度外，用戶興趣的時效性也是一個對于丟棄決策很有意義卻往往被忽略的重要因素。在現(xiàn)有研究中，通常假設(shè)用戶興趣是長期不變的。然而，實際上，用戶對某類事件的訂閱可能只會持續(xù)一段時間，即用戶興趣同樣具有不同的有效時間，超過該時間，興趣可能發(fā)生變更而失效。例如，1個音樂迷對音樂有著長期興趣，但對于籃球比賽可能僅在某些時候發(fā)生短期興趣。另外，手機用戶有可能花幾十分鐘在視頻網(wǎng)站上搜索感興趣的視頻，但是他們在手機上的注意力集中時間沒有那么長。若用戶在數(shù)分鐘內(nèi)無法獲得并觀看其想要的內(nèi)容，他們就會對此失去興趣。因此，數(shù)據(jù)在用戶失去興趣后才到達是沒有意義的。為此，假設(shè)每個用戶興趣均具有一個特定的有效時間，并稱其為訂閱時間(subscription period)。類似于基于消息生存時間的消息丟棄策略，剩余訂閱時間越短的消息在將來一段時間內(nèi)完成交付的概率也會越低。因此，當(dāng)節(jié)點緩存不足時，丟棄策略應(yīng)該考慮消息的訂閱期限，優(yōu)先丟棄那些剩余訂閱時間最短的消息。

針對CCDTNs中發(fā)布訂閱通信方式的特點，本文提出一種基于訂閱時效性的緩存管理機制。該機制在綜合使用多個與節(jié)點和消息相關(guān)的測度基礎(chǔ)上，進一步考慮了用戶興趣的有效時間，進而設(shè)計了一個丟棄效用。節(jié)點將自治地計算每個消息的丟棄效用值，并優(yōu)先丟棄效用值最高的消息以避免緩存溢出。

2 TVBBM機制

2.1 效用的計算

影響緩存管理決策的因素并不是單一的。為了產(chǎn)生更合理的決策，實現(xiàn)網(wǎng)絡(luò)性能的優(yōu)化，定義了一個多屬性的效用來選擇合適的消息進行丟棄。

第1個效用屬性是消息的轉(zhuǎn)發(fā)次數(shù)。令M表示滿足興趣的數(shù)據(jù)消息，f為M的轉(zhuǎn)發(fā)次數(shù)。在初始狀態(tài)下，所有消息的轉(zhuǎn)發(fā)次數(shù)設(shè)為1。消息每被轉(zhuǎn)發(fā)1次，其轉(zhuǎn)發(fā)次數(shù)就相應(yīng)加1。當(dāng)采用多副本機會轉(zhuǎn)發(fā)機制時，該屬性在某種程度上反映了該消息在網(wǎng)絡(luò)中的副本數(shù)量。而丟棄副本數(shù)多的消息顯然比丟棄副本數(shù)少的消息對到達率的影響更小。

第2個屬性是消息的流行度。假設(shè)興趣的訂閱者集合為S={s1,s2, …, s, …}，那么，消息M的流行度可以表示為S的基數(shù)，即集合S的成員個數(shù)，記為p。為了保持消息的多樣性，避免某些冷門消息因丟棄而消亡，具有最高流行度的消息應(yīng)被優(yōu)先丟棄。

第3個屬性是接觸比例，它被定義為某消息的所有訂閱節(jié)點中，與當(dāng)前節(jié)點相遇的訂閱節(jié)點所占的比例。從消息的角度來說，與消息訂閱節(jié)點的接觸比例越大的節(jié)點越適合作為中繼節(jié)點來攜帶該消息。因為這個節(jié)點更有可能與對該消息感興趣的訂閱節(jié)點相遇，完成消息的交付，從而達到更高的消息到達率。因此，節(jié)點應(yīng)優(yōu)先丟棄與其訂閱節(jié)點接觸比例最小的消息。假設(shè)在一段時間內(nèi)，對匹配興趣的消息感興趣的訂閱節(jié)點中與當(dāng)前節(jié)點相遇的節(jié)點數(shù)量為c，表示其接觸比例，則

最后，將消息的剩余訂閱時間作為第4個效用屬性，并賦予剩余訂閱時間更短的消息以更高的丟棄優(yōu)先級。假定sub表示集合S中由第個訂閱節(jié)點產(chǎn)生的對匹配興趣的消息的訂閱信息，T表示sub的訂閱時間，R則代表其剩余訂閱時間。那么，sub的剩余訂閱時間比可以表示為

(2)

由于在多對多的通信方式下可能存在多個對同一類型消息感興趣的訂閱節(jié)點，并且它們的訂閱時間也可能完全不同，一般的方法是計算各個訂閱者剩余訂閱時間比的平均值來評價興趣有效時間。然而，前節(jié)點與各訂閱節(jié)點之間可能具有不同的接觸頻率，而接觸頻率反映了節(jié)點間聯(lián)系的緊密程度。與當(dāng)前節(jié)點接觸頻率越高的訂閱節(jié)點，其剩余訂閱時間在平均值計算中所占的比例就越大，因此，簡單的算術(shù)平均是不合適的。本文采用各節(jié)點剩余訂閱時間比例的加權(quán)平均值來表示該效用屬性。其權(quán)重由各訂閱節(jié)點與當(dāng)前節(jié)點的接觸頻率決定。

假定當(dāng)前節(jié)點與第個訂閱節(jié)點的相遇次數(shù)為n，則各節(jié)點剩余訂閱時間比例的加權(quán)平均值可由

計算得到。因此，M的丟棄效用的計算公式為

(4)

2.2 算法設(shè)計

當(dāng)新消息到達時，TVBBM處理消息的具體過程如下。

1) 首先，節(jié)點將檢查所有消息(包括新到的消息以及存儲于緩存中的其他消息)的TTL，所有過期的消息都將立即丟棄。

2) 若新到達的消息并未過期，同時節(jié)點緩存較充足，則接收該消息。

3) 若新到達消息未過期但節(jié)點緩存不足，則節(jié)點將根據(jù)式(4)計算各消息的丟棄效用值，然后選擇效用值最高的消息進行丟棄。

3 性能評估

3.1 實驗環(huán)境

使用赫爾辛基大學(xué)開發(fā)的ONE (opportunistic networking environment)[15]simulator進行仿真實驗。將TVBBM與DMF(drop most forwarded)，DMI(drop most interested)及RANDOM的消息丟棄機制進行比較。TVBBM算法的優(yōu)勢主要是利用消息的訂閱時間來輔助消息丟棄的決策。為了定量研究使用該測度的優(yōu)點，在實驗中增加1個不考慮消息訂閱時間的簡化算法即TVBBM*作為另一個比較對象。同時，對于實驗中使用的路由協(xié)議，分別采用DTN環(huán)境下2種最具代表性的路由算法：Epidemic[16]和Prophet[6]。選擇以下3個主要的性能指標(biāo)來評估上述機制的優(yōu)劣。

1) 消息到達率。單個消息的到達率指成功接收了某個消息的訂閱節(jié)點數(shù)量占該消息訂閱節(jié)點總數(shù)的比例。網(wǎng)絡(luò)中總的平均消息到達率即為各消息到達率的平均值。

2) 消息分發(fā)速度，指給定時間內(nèi)網(wǎng)絡(luò)中成功到達的消息數(shù)。

3) 網(wǎng)絡(luò)開銷，指消息成功到達其訂閱節(jié)點所需的平均轉(zhuǎn)發(fā)次數(shù)。

采用的仿真場景具體如下：125個節(jié)點被分成6組在1個4 500 m×3 400 m的區(qū)域內(nèi)移動，節(jié)點的運動采用ONE 默認的基于赫爾辛基城市地圖的移動模型。節(jié)點通信范圍為0~100 m，數(shù)據(jù)傳輸速率為2 MB/s。其中，第1和第2組節(jié)點代表步行者，其移動速度為1.8~5.4 km/h；第3和第4組節(jié)點代表汽車，移動速度為10.0~50.0 km/h；最后2組為有軌電車，移動速度為25.0~36.0 km/h。

在仿真過程中，每個節(jié)點各擁有3類不同的興趣并能周期性地生成2類不同的數(shù)據(jù)消息。節(jié)點興趣以及消息的類型均從1個容量為100個的主題池中以隨機方式選出。仿真時間為12 h，節(jié)點每隔25～35 s生成1個100 Kb的消息，消息的TTL為6 h。此外，用戶興趣在仿真過程中可能過時，其有效時間服從 [0.5, 6.0] h區(qū)間上的均勻分布。消息只有在其訂閱節(jié)點的訂閱時間內(nèi)到達才算作1次成功交付。

3.2 仿真結(jié)果及分析

3.2.1 消息到達率

圖1所示為節(jié)點緩存量為10 MB時，各消息丟棄機制獲得的消息到達率。由于TVBBM機制在消息丟棄決策時全面地考慮了多個相關(guān)因素，因此取得了最佳的效果。以使用Prophet路由協(xié)議的場景為例，TVBBM的到達率比TVBM*，DMF，DMI和RANDOM分別高4.0%，10.4%，18.5%和13.0%，這也證實了將消息訂閱時間作為決策依據(jù)的有效性。各機制下的消息到達率隨節(jié)點緩存容量變化的情況如圖2和圖3所示。從圖2可見：在使用Prophet路由協(xié)議時，所有的5種丟棄機制在節(jié)點緩存容量較小時的到達率均較低；隨著緩存的增加，各機制的消息到達率隨之增加，同時TVBBM的優(yōu)勢越明顯。DMF選擇丟棄轉(zhuǎn)發(fā)次數(shù)最多的消息，避免了消息的過度復(fù)制并為流行度低的消息提供了相對公平的傳輸機會。而DMI選擇了最感興趣的消息進行丟棄，但是，訂閱節(jié)點數(shù)量最多的消息不一定是復(fù)制次數(shù)最多的消息。有時，DMI可能丟棄一個流行度高但副本數(shù)很少的消息，從而在一定程度上影響了它的消息到達率，因此，DMF的到達率略比RANDOM的高，而DMI獲得的到達率最低。圖3所示為采用Epidemic路由協(xié)議時的到達率，得到了與圖2所示相似的結(jié)果，只是消息到達率稍比圖2中的低。這主要是兩者所采用的轉(zhuǎn)發(fā)策略不同造成的。Epidemic路由協(xié)議采用了簡單的洪泛的方式進行消息轉(zhuǎn)發(fā)，而Prophet路由協(xié)議則僅將消息轉(zhuǎn)發(fā)給更有可能完成消息交付的節(jié)點。因此，在緩存資源有限的情況下，這5種丟棄機制在采用Prophet路由協(xié)議時的到達率略比采用Epidemic時的高。

圖1 各丟棄機制在10 MB緩存下的消息到達率

1—TVBBM*; 2—TVBBM; 3—DMF; 4—DMI; 5—RANDOM

1—TVBBM*; 2—TVBBM; 3—DMF; 4—DMI; 5—RANDOM

3.2.2 消息分發(fā)速度

圖4和圖5所示為以上5種丟棄機制的累積到達率與平均延遲的關(guān)系。通常，消息的轉(zhuǎn)發(fā)次數(shù)越多，說明它停留在網(wǎng)絡(luò)中的時間越長，因而，DMF丟棄轉(zhuǎn)發(fā)次數(shù)最多的消息也就意味著剩余TTL更長的消息將得到優(yōu)先的轉(zhuǎn)發(fā)機會，因此，DMF獲得了比DMI和RANDOM更短的到達延遲。而TVBBM*和TVBBM在丟棄消息的選擇時，不僅考慮了消息的轉(zhuǎn)發(fā)次數(shù)，而且綜合了消息的流行度以及節(jié)點接觸歷史信息，為交付概率高的消息提供了更多的轉(zhuǎn)發(fā)機會，因此，顯著地提高了轉(zhuǎn)發(fā)效率，同時，分發(fā)速度也明顯比其他3種機制的高。此外，由于進一步考慮了消息的訂閱時間，TVBBM賦予剩余訂閱時間更長的消息和更高的轉(zhuǎn)發(fā)優(yōu)先級，因此，它獲得了最快的消息分發(fā)速度。由圖4和圖5可知：在相同時間內(nèi)，TVBBM完成了最多的消息交付。以圖4為例，當(dāng)平均延遲達到3 000 s時，TVBBM成功地交付了70%的消息，分別超過同時刻TVBBM*，DMF，ANDOM和DMI交付比例的4.4%，10.8%，18.5%和23.6%。

1—TVBBM*; 2—TVBBM; 3—DMF; 4—DMI; 5—RANDOM

1—TVBBM*; 2—TVBBM; 3—DMF; 4—DMI; 5—RANDOM

3.2.3 網(wǎng)絡(luò)開銷

由于緩存資源受限，節(jié)點不得不丟棄某些消息以避免緩存溢出，并通過重傳來確保較高的消息達到率，因此，完成消息的交付所需的平均轉(zhuǎn)發(fā)次數(shù)反映了各機制消息分發(fā)的網(wǎng)絡(luò)開銷。Prophet和Epidemic路由協(xié)議下不同緩存時的網(wǎng)絡(luò)開銷分別如圖6和圖7所示。從圖6和圖7可見：隨著緩存容量增加，為消息提供了更多的存儲空間，這導(dǎo)致消息丟棄和重傳減少，因而各機制的開銷比逐漸降低；TVBBM綜合考慮了多個相關(guān)因素，選擇丟棄效用最高的消息進行丟棄，有效地減少了由于丟棄而造成的消息重傳，從而以最少的轉(zhuǎn)發(fā)完成了消息交付。從圖6可見：在節(jié)點緩存為10 MB時，TVBBM平均經(jīng)過3.44次轉(zhuǎn)發(fā)完成消息的交付，轉(zhuǎn)發(fā)次數(shù)比TVBBM*，DMF，RANDOM和DMI分別降低約2.47%，10.88%，14.21%及18.48%。Epidemic路由協(xié)議下不同緩存時的網(wǎng)絡(luò)開銷得到了與Prophet路由協(xié)議相似的結(jié)果。然而，由于Prophet具有選擇性的轉(zhuǎn)發(fā)策略，它更好地控制了資源的消耗，因此，Prophet路由下各機制的開銷略低于采用Epidemic路由時的開銷。

1—TVBBM*; 2—TVBBM; 3—DMF; 4—DMI; 5—RANDOM

1—TVBBM*; 2—TVBBM; 3—DMF; 4—DMI; 5—RANDOM

4 結(jié)論

1) 用戶興趣的時效性是一個非常重要的影響因素，消息丟棄策略中將其作為相關(guān)的測度有利于決策的優(yōu)化。為此，考慮了節(jié)點、消息的有關(guān)特性以及用戶興趣的時效性，提出了一個基于訂閱時效性的緩存管理機制即TVBBM。

2) 與其他機制相比，TVBBM機制獲得了較高的消息到達率、較快的消息分發(fā)速度以及較小的網(wǎng)絡(luò)開銷比。

參考文獻：

[1] Bulut A, Singh A K, Vitenberg R. Distributed data streams indexing using content-based routing paradigm[C]// Proceedings of 19th IEEE Int Parallel and Distributed Processing Symposium (IPDPS05). NJ: IEEE, 2005: 94?95.

[2] Jacobson V, Smetters D K, Thornton J D, et al. Networking named content[C]// Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies. New York: ACM Press, 2009: 1?12.

[3] Eugster P, Felber P, Guerraoui R, et al. The many faces of publish/subscribe[J]. ACM Computing Surveys, 2003, 35(2): 114?131.

[4] Nguyen A D, Senac P, Diaz M. STIgmergy Routing (STIR) for content-centric delay-tolerant networks[C]//Proceedings of Latin-American Workshop on Dynamic Networks (LAWDN). 2010.

[5] Sammou EI M, Abdelmounaim A. Rouring in delay tolerant networks (DTN) improved routing With Prophet and the model of transfer by delegation (Custody transfer)[J]. International Journal of Computer Networks, 2012, 4(6): 240?248.

[6] Ayub Q, Zahid M S M, Rashid S, et al. Threshold based locking routing strategy for delay tolerant network[J]. Wireless Networks, 2013, 19(8): 2067?2078.

[7] 劉耀, 王建新, 黃元南. 延遲容忍網(wǎng)絡(luò)中基于社會屬性的負載感知路由[J]. 系統(tǒng)工程與電子技術(shù), 2012, 34(1): 185?190. LIU Yao, WANG Jianxin, HUANG Yuannan. Social-based load aware routing in delay tolerant networks[J]. Systems Engineering and Electronics, 2012, 34(1): 185?190.

[8] Lin K C J, Chen C W, Chou C F. Preference-aware content dissemination in opportunistic mobile social networks[C]// Proceedings of the IEEE INFOCOM’12. Piscataway, NJ: IEEE, 2012: 1960?1968.

[9] Bjurefors F, Gunningberg P, Rohner C. Congestion avoidance in a data-centric opportunistic network[C]// Proceedings of the ACM SIGCOMM work-shop on Information-centric networking (ICN’11). New York: ACM Press, 2011: 32?37.

[10] Burleigh S, Jennings E, Schoolcraft J. Autonomous Congestion Control in Delay-Tolerant Networks[C]// Proceedings of 9th International Conference on Space Operations. 2006: 70?79.

[11] Krifa A, Barakat C, Spyropoulos T. Message drop and scheduling in DTNs: Theory and Practice[J]. IEEE Transactions on Mobile Computing, 2012, 11(9): 1470?1483.

[12] Naves J F, Moraes I M, Albuquerque C. LPS and LRF: Efficient buffer management policies for delay and disruption tolerant networks[C]// Proceedings of the 37th Conference on Local Computer Networks (LCN’12). 2012: 368?375.

[13] Elwhishi A, Ho P, Naik K, et al. A novel message scheduling framework for delay tolerant networks routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(5): 871?880.

[14] Lindgren A, Phanse K S. Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks[C]// Proceedings of the 1st International Conference on Communication System Software and Middleware (COMSWARE). Delhi, India: IEEE Computer Society, 2006: 1?10.

[15] Ker?nen A, Ott J, K?rkk?inen T. The ONE simulator for DTN protocol evaluation[C]// Proceedings of the 2nd International Conference on Simulation Tools and Techniques. Brussels: ICST, 2009: 1?10.

[16] Vahdat A, Becker D. Epidemic routing for partially connected ad hoc networks[R]. Durham NC: Duke University. Department of Computer Science, 2000: 1?14.

Buffer management scheme in content-centric DTNs based on temporal validity of subscription

LUO Xi1, 2, AN Ying3, HUANG Jiawei1, WANG Jianxin1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2. Department of Information Technology, Hunan Police Academy, Changsha 410138, China;3. Institute of Information Security & Big Data, Central South University, Changsha 410083, China)

Considering that the temporal validity of user interest plays an important role in buffer management decisions, the validity duration of user interest in message dropping decision was applied and buffer management scheme based on a novel temporal validity was presented. In this scheme, a multi-attribute utility was designed to decide the dropping priority of messages from the standpoints of node, message and interest. The simulation results prove that the scheme has high delivery ratio and dissemination speed, and low overhead.

content-centric networks; delay tolerant networks (DTNs); publish/subscribe system; buffer management; congestion avoidance

10.11817/j.issn.1672-7207.2015.07.015

TG111.3

A

1672?7207(2015)07?2487?07

2014?08?10；

2014?10?21

國家自然科學(xué)基金資助項目(60873265)；國家高技術(shù)研究發(fā)展計劃(863計劃)項目(2009AA112205)；國家自然科學(xué)基金創(chuàng)新群體科學(xué)基金資助項目(70921001)；湖南省科技計劃項目(2012FJ3045) (Project(60873265) supported by the National Natural Science Foundation of China; Project(2009AA112205) supported by the National High Technology Research and Development Program(863 Program) of China; Project(70921001) supported by the National Natural Science Foundation of Innovation Groups; Project(2012FJ3045) supported by Plan Program of Science and Technology of Hunan Province)

安瑩，博士，從事延遲容忍網(wǎng)絡(luò)擁塞控制等研究；E-mail: anan1428@163.com

(編輯 陳燦華)