存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)路由中基于消息優(yōu)先級(jí)的緩存管理算法

林 勇，王玉玨，吳慶州

(1. 重慶電子工程職業(yè)學(xué)院，重慶 401331;2.南京理工大學(xué)，江蘇 南京 210046)

0 引 言

近期，稀疏移動(dòng)自組網(wǎng)(Sparsely Populated Mobile ad-hoc Network)受到研究人員的廣泛關(guān)注[1-2]。稀疏移動(dòng)自組網(wǎng)是典型的時(shí)滯容錯(cuò)網(wǎng)絡(luò)(Delay Tolerant Networks, DTN)網(wǎng)絡(luò)[3]。在稀疏移動(dòng)自組網(wǎng)內(nèi)，由于節(jié)點(diǎn)密度低，節(jié)點(diǎn)間的連接在多數(shù)時(shí)間內(nèi)處于斷裂狀態(tài)。然而，由于節(jié)點(diǎn)的移動(dòng)，兩節(jié)點(diǎn)可能偶爾處于彼此的通信范圍內(nèi)，進(jìn)而形成間歇性的連通。在這種情況下，節(jié)點(diǎn)間能夠通信。由于是間歇性通信，常采用存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)路由。利用節(jié)點(diǎn)機(jī)會(huì)性的連通機(jī)會(huì)，攜帶數(shù)據(jù)轉(zhuǎn)發(fā)，完成消息的傳輸[4]。

在存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)路由協(xié)議中，當(dāng)節(jié)點(diǎn)接收或產(chǎn)生了消息，先將此消息緩存于緩沖區(qū)，并攜帶此信息進(jìn)行移動(dòng)，直到它遇到合適的節(jié)點(diǎn)。如果相遇了合適的節(jié)點(diǎn)，它就向此節(jié)點(diǎn)轉(zhuǎn)發(fā)。為了提高將消息成功傳輸至目的節(jié)點(diǎn)的概率，也采用多復(fù)本路由策略[3]。蔓延路由就是典型的多復(fù)本路由[4]。

在蔓延路由策略中，攜帶消息的節(jié)點(diǎn)只要遇到另一節(jié)點(diǎn)，它就將自己的消息復(fù)本傳輸至該節(jié)點(diǎn)。如果節(jié)點(diǎn)的緩存區(qū)足夠大的話(huà)，蔓延路由能夠獲取低的傳輸時(shí)延，但這也是建立在消耗大量緩存資源的基礎(chǔ)上。一旦節(jié)點(diǎn)緩存區(qū)容量不足夠大時(shí)，緩存區(qū)就會(huì)溢出。因此，必須采用有效的緩存管理策略[5-8]，進(jìn)而防止溢出問(wèn)題。

然而，用于傳統(tǒng)通信網(wǎng)絡(luò)的緩存管理策略并不適用于稀疏移動(dòng)自組網(wǎng)[9-10]。此外，現(xiàn)存的緩存管理策略是基于所有節(jié)點(diǎn)均能直接相遇的假設(shè)。顯然，在稀疏移動(dòng)自組網(wǎng)內(nèi)，節(jié)點(diǎn)無(wú)法與網(wǎng)絡(luò)另一部分節(jié)點(diǎn)直接相遇。

因此，在真實(shí)環(huán)境中，考慮了部分節(jié)點(diǎn)可能無(wú)法直接相遇，丟棄部分消息復(fù)本是合理。因?yàn)椋@些消息復(fù)本不能提高將消息傳輸至目的節(jié)點(diǎn)的概率。然而，當(dāng)網(wǎng)絡(luò)內(nèi)只有一條消息復(fù)本時(shí)，若刪除此消息復(fù)本，則此消息就無(wú)法傳輸至目的節(jié)點(diǎn)。具有消息復(fù)本數(shù)越小的消息，消息也就越稀罕。因此，越稀罕的消息，就應(yīng)越謹(jǐn)慎刪除此消息復(fù)本。

為此，本文面向稀疏移動(dòng)自組網(wǎng)，并考慮到消息的復(fù)本數(shù)，提出基于消息優(yōu)先級(jí)的緩存管理算法(Buffer Management Policy based on Message Priority, BMP-MP)。BMP-MP算法將網(wǎng)絡(luò)內(nèi)擁有復(fù)本消息數(shù)越少的消息，賦予高的優(yōu)先級(jí)。而緩存區(qū)優(yōu)先保存優(yōu)先級(jí)高的消息。在消息未被傳輸至目的節(jié)點(diǎn)前，盡可能地不讓消息從網(wǎng)絡(luò)內(nèi)消失。實(shí)驗(yàn)數(shù)據(jù)表明，提出的BMP-MP算法能夠有效地降低未傳遞消息率和傳輸時(shí)延。

1 系統(tǒng)模型

假定網(wǎng)絡(luò)內(nèi)有N個(gè)節(jié)點(diǎn)，且引用節(jié)點(diǎn)集V。網(wǎng)絡(luò)內(nèi)任意兩個(gè)節(jié)點(diǎn)的相遇服從泊松分布，且分布率為λ。具體而言，兩個(gè)節(jié)點(diǎn)?、ω(?,ω∈V、ω)的相遇率表示為λ?,ω。

此外，每個(gè)節(jié)點(diǎn)均有緩存區(qū)存儲(chǔ)消息，且所有節(jié)點(diǎn)的緩存區(qū)尺寸均為B。假定每條消息尺寸為常數(shù)，且表示1/B。因此，每個(gè)節(jié)點(diǎn)的緩存區(qū)能存儲(chǔ)B條消息。

假定在時(shí)刻t，網(wǎng)絡(luò)內(nèi)的消息集表示M(t)。而節(jié)點(diǎn)?在時(shí)刻t擁有的消息集為M?(t)?M(t)。網(wǎng)絡(luò)內(nèi)所產(chǎn)生的消息可表示為M?(t)?M(t)。

2 BMP-MP算法

2.1 消息稀罕度

BMP-MP算法在緩存區(qū)管理時(shí)，考慮了消息稀罕性。為此，引用消息稀罕度變量。假定NC(m,t)表示在時(shí)刻t，網(wǎng)絡(luò)內(nèi)擁有消息m的復(fù)本數(shù)。NC(m,t)值越小，消息的稀罕度越高。當(dāng)NC(m,t)=1，則表明網(wǎng)絡(luò)內(nèi)只含一條消息復(fù)本，那此類(lèi)消息稱(chēng)為極稀消息。一旦刪除極稀消息復(fù)本，網(wǎng)絡(luò)內(nèi)再也無(wú)此消息復(fù)本[9]，此消息將從網(wǎng)絡(luò)內(nèi)消失。因此，BMP-MP算法對(duì)極稀消息賦予最高的優(yōu)先權(quán)。換而方言之，稀罕度越高，消息優(yōu)先權(quán)越高。

此外，在執(zhí)行BMP-MP算法時(shí)，無(wú)需準(zhǔn)確地計(jì)算NC(m,t)值，只需要判斷NC(m,t)是否等于1。原因在于：BMP-MP算法給消息設(shè)置優(yōu)先級(jí)時(shí)，只考慮了NC(m,t)=1和NC(m,t)≥2兩種情況。換而言之，當(dāng)NC(m,t)不等于1，則NC(m,t)≥2。

因此，BMP-MP算法引用委派機(jī)制(Delegation Mechanism)判斷NC(m,t)值。在擁有消息m復(fù)本的節(jié)點(diǎn)中，只有一個(gè)節(jié)點(diǎn)是委派者(Delegator)，而其他節(jié)點(diǎn)稱(chēng)為輔助節(jié)點(diǎn)(Auxiliary node)。當(dāng)Delegator將消息復(fù)本轉(zhuǎn)發(fā)至另一個(gè)節(jié)點(diǎn)，它就決定此接收節(jié)點(diǎn)是否能成為繼承它，成為新一輪的Delegator。

為了能識(shí)別Delegator節(jié)點(diǎn)，引用一個(gè)布爾變量am∈{0,1}，并將am載入每條消息m的首部。如果am=1，則該節(jié)點(diǎn)成為Delegator節(jié)點(diǎn)，否則它就成為輔助節(jié)點(diǎn)。

一旦產(chǎn)生了消息，該消息的源節(jié)點(diǎn)就是此消息的Delegator節(jié)點(diǎn)。具體而言，源節(jié)點(diǎn)就擁有消息m的復(fù)本，且am=1。當(dāng)Delegator節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，則將接收該消息節(jié)點(diǎn)設(shè)為Delegator節(jié)點(diǎn)，而自己成為輔助節(jié)點(diǎn)，即自己的am設(shè)為0。

2.2 鄰近集

為了提高消息的傳遞率，引用鄰近集變量。鄰近集是基于消息的目的節(jié)點(diǎn)。具體而言，假定消息m的目的節(jié)點(diǎn)為dm。鄰近集表示具有消息m的復(fù)本、且能與目的節(jié)點(diǎn)dm相遇的節(jié)點(diǎn)集。

具體而言，假定節(jié)點(diǎn)?擁有消息m的復(fù)本，且NC(m,t)=1。消息m的傳遞成功率取決于節(jié)點(diǎn)?是否能與目的節(jié)點(diǎn)dm相遇。因此，消息m的鄰近集GH(m)定義如式(1)所示：

GH(m)={?|λ?,dm≥th,?∈V}

(1)

其中λ?,dm表示節(jié)點(diǎn)?與目的節(jié)點(diǎn)dm相遇概率，而th表示相遇概率閾值[10]。

如果?∈GH(m)擁有極稀消息m，當(dāng)節(jié)點(diǎn)?相遇其他節(jié)點(diǎn)時(shí)，它就更好地?fù)碛邢的復(fù)本。相反，若節(jié)點(diǎn)?不在GH(m)內(nèi)，但它擁有消息m的復(fù)本，在這種情況下，當(dāng)節(jié)點(diǎn)?相遇節(jié)點(diǎn)ω∈GH(m)，則節(jié)點(diǎn)?就將消息復(fù)本傳輸至節(jié)點(diǎn)ω，然后節(jié)點(diǎn)?就從緩存區(qū)內(nèi)刪除消息m的復(fù)本。

2.3 消息優(yōu)先級(jí)

BMP-MP算法對(duì)緩存區(qū)管理時(shí)，考慮了消息優(yōu)先級(jí)。為此，對(duì)緩存區(qū)內(nèi)消息進(jìn)行優(yōu)先級(jí)進(jìn)行設(shè)置。先定義親近Λ變量。Λm(t)表示相遇目的節(jié)點(diǎn)dm的所有節(jié)點(diǎn)集，其定義如式(2)所示：

(2)

其中Sm(t)表示在時(shí)刻t，擁有消息m的節(jié)點(diǎn)集。

假定這有兩條消息m1、m2，且NC(m1,t)≥2、NC(m2,t)≥2。如果Λm1(t)<Λm2(t)，則消息m1的優(yōu)先級(jí)高于消息m2。這是基于一個(gè)事實(shí)：如果將具有小Λm(t)的消息丟棄，則增加了將此消息傳遞至目的節(jié)點(diǎn)概率。

總之，將稀罕消息設(shè)置最高的優(yōu)先級(jí)。具體而言，節(jié)點(diǎn)?將具有NC(m,t)=1、λ?,dm>th的消息的優(yōu)先級(jí)最高，它的目的節(jié)點(diǎn)能夠頻繁地相遇節(jié)點(diǎn)?，如圖1所示。次高優(yōu)先級(jí)賦予具有NC(m,t)=1、λ?,dm≤th的消息；依次是NC(m,t)≥2、λ?,dm>th；NC(m,t)=1、λ?,dm≤th。而具有NC(m,t)≥2、λ?,dm≤th的消息的優(yōu)先級(jí)設(shè)為最低。

圖1 節(jié)點(diǎn)?的優(yōu)先級(jí)設(shè)置

2.4 緩存區(qū)管理

緩存區(qū)管理的目的在于防止緩存溢出。當(dāng)接收消息或產(chǎn)生了新消息，就利用緩存區(qū)管理策略，進(jìn)而預(yù)防溢出問(wèn)題。

首先，考慮產(chǎn)生新消息情況。當(dāng)節(jié)點(diǎn)?持有|M?(t)|=B條消息時(shí)，它產(chǎn)生了新消息mnew。在這種情況下，節(jié)點(diǎn)?必須將新產(chǎn)生的消息mnew與原存儲(chǔ)的消息M?(t)進(jìn)行優(yōu)先級(jí)比較，并從M?(t)∪mnew中選擇優(yōu)先級(jí)最低的消息，再丟棄此消息，進(jìn)而防止緩存區(qū)溢出。

若沒(méi)有產(chǎn)生新消息，而是接收了消息。假定節(jié)點(diǎn)?、ω在時(shí)刻t相遇，并需要交流一些消息。圖2顯示了它們交互消息的過(guò)程。

圖2 節(jié)點(diǎn)?、ω間消息交互過(guò)程

一旦相遇節(jié)點(diǎn)ω，節(jié)點(diǎn)?就從M?(t)內(nèi)選擇消息F?,ω，再將F?,ω的ID號(hào)l(F?,ω)傳輸至節(jié)點(diǎn)ω。消息F?,ω的傳輸過(guò)程取決于路由策略。若是采用蔓延路由，則F?,ω=M?(t)。

當(dāng)節(jié)點(diǎn)ω接收了l(F?,ω)，先判斷是否滿(mǎn)足式(3)。如果滿(mǎn)足，則即使節(jié)點(diǎn)ω接收F?,ω內(nèi)所有消息，也不會(huì)發(fā)生溢出。為此，為了能接收F?,ω消息，節(jié)點(diǎn)ω就將l(F?,ω)再發(fā)送至?。

|F?,ω∪M?(t)|≤B

(3)

圖3 消息Hω的選擇

3 數(shù)值分析

3.1 仿真場(chǎng)景

利用Matlab軟件建立仿真平臺(tái)，并考慮隨機(jī)場(chǎng)景。在隨機(jī)場(chǎng)景中，利用隨機(jī)圖構(gòu)建稀罕矩陣Λ。且節(jié)點(diǎn)數(shù)|V|=101，同時(shí)，節(jié)點(diǎn)能夠相遇網(wǎng)絡(luò)內(nèi)一部分節(jié)點(diǎn)。而消息產(chǎn)生率為1。對(duì)于每條消息m，它的目的節(jié)點(diǎn)dm從網(wǎng)絡(luò)內(nèi)隨機(jī)選擇。

此外，為了更好地分析BMP-MP算法，選擇基于丟棄最舊的(Drop Oldest, DO)[10]、基于驅(qū)除最先擁有(evict Most Founded First, MOFO)[11]、基于全局知識(shí)的丟失策略(Global Knowledge-based Drop-Loss, GBD-L)[9]和基于全局知識(shí)的時(shí)延策略(Global Knowledge-based Drop-delay, GBD-D)[9]緩存區(qū)管理策略作為參照，并分析它們未傳遞消息率和平均傳輸時(shí)延E[TD]。而TD表示從消息的產(chǎn)生至此消息被傳輸至目的節(jié)點(diǎn)所消耗的時(shí)間。未傳遞消息率是指未傳遞消息數(shù)與總的消息數(shù)之比。

3.2 未傳遞消息率

圖4分析了未傳遞消息率隨緩存區(qū)尺寸B的變化情況，其中“Proposal”表示本文提出的BMP-MP算法。從圖4可知，在緩存區(qū)尺寸B的整個(gè)變化區(qū)間內(nèi)，“Proposal”算法的未傳遞消息率低于現(xiàn)存算法。原因在于：給稀罕消息設(shè)置優(yōu)先級(jí)，對(duì)緩存區(qū)的管理非常有效。此外，DO和GBD-L算法的未傳遞消息率小于MOFO算法。這主要是因?yàn)椋涸陔S機(jī)場(chǎng)景中，網(wǎng)絡(luò)更接近于同構(gòu)網(wǎng)絡(luò)。

圖4 未傳遞消息率

3.3 傳輸時(shí)延

圖5 傳輸時(shí)延

圖5顯示了各算法的E[TD]隨緩存區(qū)尺寸B的變化情況。從圖5可知，“Proposal”算法的E[TD]小于GBD-L和GBD-D算法，這些數(shù)據(jù)說(shuō)明， “Proposal”算法能夠有效地降低傳輸時(shí)延。然而，“Proposal”算法的傳輸時(shí)延高于MOFO算法。注意圖4，MOFO算法的未傳遞率很高，這也說(shuō)明MOFO算法只將具有小時(shí)延的消息傳輸至它們的目的節(jié)點(diǎn)。

4 結(jié) 語(yǔ)

針對(duì)稀疏移動(dòng)自組網(wǎng)的存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)路由，提出基于消息優(yōu)先級(jí)的緩存管理算法BMP-MP。BMP-MP算法給每條消息賦予不同的優(yōu)先級(jí)，再依據(jù)優(yōu)先級(jí)決定從緩沖區(qū)內(nèi)刪除的順序。實(shí)驗(yàn)數(shù)據(jù)表明，提出的BMP-MP算法能夠有效地降低未傳遞概率和傳輸時(shí)延。