基于運動相似性的機會網(wǎng)絡(luò)緩存管理策略

張 力，陳瀅生，王言通

(1.重慶人文科技學(xué)院 計算機工程學(xué)院，重慶 401524；2.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

機會網(wǎng)絡(luò)[1](opportunistic network)采用與傳統(tǒng)傳輸不同的“存儲-攜帶-轉(zhuǎn)發(fā)”方式完成消息傳輸[2]，這使得節(jié)點需要較長時間存儲來自網(wǎng)絡(luò)中其它節(jié)點中轉(zhuǎn)的消息，同時為了增加消息成功投遞的概率，常采用多副本的消息傳輸策略。多副本的策略增加了網(wǎng)絡(luò)資源的消耗，經(jīng)常使得節(jié)點因緩存剩余空間不足而發(fā)生擁塞，需要丟棄節(jié)點攜帶的部分消息，以釋放緩存空間用以接收新消息[3,4]。為了提升機會網(wǎng)絡(luò)消息傳輸性能，需選擇合適的消息進行丟棄和傳輸策略，因此，高效的緩存管理策略對網(wǎng)絡(luò)性能具有十分重要的作用。

國內(nèi)外研究者對機會網(wǎng)絡(luò)的緩存管理策略開展研究并提出了多種緩存管理策略。劉期烈等[5]提出了根據(jù)消息優(yōu)先級的緩存調(diào)度策略。該策略利用網(wǎng)絡(luò)消息副本的數(shù)量、消息的生存時間以及產(chǎn)生的時間計算消息傳輸概率值。然后利用傳輸概率定義消息的優(yōu)先級，根據(jù)消息優(yōu)先級進行消息轉(zhuǎn)發(fā)與傳輸。文獻[6]分析了增強的緩存管理策略(enhanced buffer management policy，EBMP)，該策略利用網(wǎng)絡(luò)中消息的副本數(shù)量、消息的生存時間以及剩余生存時間建立消息的投遞效用方程和延遲效用方程，根據(jù)效用方程值決定是否轉(zhuǎn)發(fā)消息。王慧強等[7]利用消息在網(wǎng)絡(luò)中轉(zhuǎn)發(fā)的次數(shù)和消息在網(wǎng)絡(luò)中的生存時間，計算消息的生存效用值。根據(jù)效用值大小確定需要丟棄消息的順序。吳大鵬等[8]提出基于消息冗余度的緩存管理策略。作者根據(jù)節(jié)點的活躍程度以及消息在網(wǎng)絡(luò)中的副本數(shù)目估計消息的冗余度，根據(jù)消息的冗余度進行消息管理和調(diào)度。然而，這些緩存管理算法沒有對消息運動軌跡與節(jié)點運動的關(guān)系、節(jié)點是否適合轉(zhuǎn)發(fā)消息進行考慮，消息傳輸?shù)姆较蚺c節(jié)點運動方向不相匹配，使得消息傳輸效率不高，存在網(wǎng)絡(luò)資源浪費，消息傳輸時延較高的問題。

針對上述問題，本文從消息、節(jié)點運動特性著手，評估消息在網(wǎng)絡(luò)中擴散程度以及消息在未傳輸成功條件下，在D時間內(nèi)被傳輸出去的概率。進一步利用運動相似性計算消息的效用值，依據(jù)效用值進行消息調(diào)度和丟棄，提出了一種基于運動相似性的機會網(wǎng)絡(luò)消息緩存管理策略(cache management algorithm based on mobility similarity，CMA-MS)。

1 消息擴散程度估計

機會網(wǎng)絡(luò)消息擴散過程模型與傳統(tǒng)網(wǎng)絡(luò)模型相比，無論是網(wǎng)絡(luò)規(guī)模還是網(wǎng)絡(luò)中消息傳輸方式都存在很大差異。傳染病模型理論是被廣泛使用研究消息傳輸?shù)睦碚摗Ｗ钤缡怯蒏ermack等在研究物種繁殖和死亡過程時提出的。該模型中將個體所處的狀態(tài)劃分為3種：易傳染，感染和治愈，個體總是處在3種狀態(tài)中的某一個狀態(tài)。在傳播過程中，個體存在著被感染概率、傳播概率以及治愈概率。近幾年，研究人員將傳染病模型引入到機會網(wǎng)絡(luò)，并且取得一些研究成果。如文獻[9]提出了一種自適應(yīng)概率感染和自適應(yīng)限時消息轉(zhuǎn)發(fā)的路由機制，實現(xiàn)了更為高效、可靠的網(wǎng)絡(luò)信息傳播的動態(tài)解決方案。

網(wǎng)絡(luò)節(jié)點分為易傳染節(jié)點、感染節(jié)點以及治愈節(jié)點。以傳染路由為基礎(chǔ)建立模型，傳染路由將消息轉(zhuǎn)發(fā)給其所遇到的節(jié)點，此時網(wǎng)絡(luò)中僅僅存在感染節(jié)點和易感染節(jié)點。假設(shè)網(wǎng)絡(luò)t時刻時感染節(jié)點數(shù)I(t)，易傳染節(jié)點數(shù)S(t)，感染節(jié)點數(shù)目的變化率為I′(t)。當(dāng)感染節(jié)點遇到易傳染節(jié)點時，感染的節(jié)點數(shù)目將增加1，易傳染節(jié)點數(shù)目減少1，I′(t)的表達式如下

(1)

β為節(jié)點連接的間隔頻率，β反映節(jié)點移動性，β越大，網(wǎng)絡(luò)節(jié)點相遇越頻繁，消息擴散的速度越快。β的值由節(jié)點的移動模型決定，在機會網(wǎng)絡(luò)中，β是一個固定值(網(wǎng)絡(luò)中節(jié)點的移動模型都是確定的)，文獻[11]給出隨機游走模型中β的計算方法

(2)

其中，A為場景面積，R為節(jié)點的通信半徑，ω為移動模型決定的常量，E[V′]為網(wǎng)絡(luò)中節(jié)點相對移動的平均移動速度。

由此可知，網(wǎng)絡(luò)中節(jié)點的相遇頻率與節(jié)點相對移動速度、節(jié)點的通信半徑成正比，與網(wǎng)絡(luò)面積成反比。

在初始時刻，網(wǎng)絡(luò)中感染節(jié)點只有源節(jié)點一個，即I(0)=1，P(0)=0，帶入求解式(1)和式(2)，解得的表達式為

(3)

傳染模型可以擴展到概率轉(zhuǎn)發(fā)路由機制中，即兩節(jié)點相遇時，感染節(jié)點根據(jù)概率值p值將消息轉(zhuǎn)發(fā)給易傳染節(jié)點。擴展模型表示如下

(4)

初始條件相同情況下，解得微分方程

(5)

根據(jù)概率轉(zhuǎn)發(fā)消息的路由是將消息轉(zhuǎn)發(fā)給與目的節(jié)點相遇概率更高的節(jié)點。本文以傳染模型的概率擴展模型作為研究基礎(chǔ)，將節(jié)點運動相似性作為擴展模型中的“概率”，估計到網(wǎng)絡(luò)中傳輸?shù)南⒏北緮?shù)目

(6)

式中：psim為消息攜帶節(jié)點與目的節(jié)點運動相似性。

2 運動相似性計算

機會網(wǎng)絡(luò)中，不同節(jié)點相遇的同一節(jié)點成為共遇節(jié)點，尤其是處在同一片區(qū)域的節(jié)點相遇頻率更高，其共遇節(jié)點也更多。分析共遇節(jié)點的數(shù)目可以作為判斷兩節(jié)點相遇可能性的一個參考依據(jù)。將某個節(jié)點所遇到的節(jié)點看作該節(jié)點運動的軌跡，通過分析兩個節(jié)點運動軌跡的相似性估計節(jié)點相遇概率。同時，將消息傳輸經(jīng)過的節(jié)點看作消息的運動軌跡，通過分析不同消息間運動軌跡的相似性以及消息與節(jié)點間運動的相似性，為消息調(diào)度提供參考依據(jù)。

2.1 節(jié)點運動相似性

節(jié)點運動相似性是指兩節(jié)點歷史所遇節(jié)點中共同相遇節(jié)點所占的比例。若兩節(jié)點運動具有高相似性，則它們具有較為相似的移動范圍，反之，若兩節(jié)點運動相似性較低則其移動范圍的交疊區(qū)域較小，利用該特點選擇與消息攜帶節(jié)點運動相似性較低的節(jié)點作為下一跳消息轉(zhuǎn)發(fā)節(jié)點，從而可以有效提高機會網(wǎng)絡(luò)消息傳播的范圍。令Sni和Snj分別表示節(jié)點i和節(jié)點j在時間T內(nèi)所遇到的節(jié)點，節(jié)點i計算的節(jié)點運動相似性Simnode(i,j)定義如下

(7)

2.2 消息運動相似性

消息運動相似性是指兩個消息在傳輸過程中所遇節(jié)點中相同節(jié)點所占的比例。為了能評估消息運動相似性，在消息的頭部增加了一個記錄消息經(jīng)過節(jié)點的報文。將消息經(jīng)過的節(jié)點作為消息的運動軌跡，進而分析消息運動相似性。若兩個消息運動具有高相似性，則它們具有較為相似的傳輸路徑，傳輸?shù)较嗤膮^(qū)域也具有較高的可能性，在消息傳輸時，可以將兩個消息同時交給一個節(jié)點。令Smi和Smj分別表示消息mi和消息mj在傳輸過程中所遇到的節(jié)點，消息運動相似性Simmessage(mi,mj)定義如下

(8)

2.3 節(jié)點與消息運動相似性

節(jié)點與消息運動相似性是指節(jié)點運動軌跡與消息轉(zhuǎn)發(fā)軌跡的重合部分占總運動軌跡比值。該比值越高則攜帶消息節(jié)點的運動范圍與消息傳播的范圍的重疊范圍越大，消息轉(zhuǎn)發(fā)至目的節(jié)點成功的概率越高。節(jié)點i與消息mi的運動相似性Match(i,mi)為

(9)

消息攜帶節(jié)點a與目的節(jié)點d運動相似性psim

(10)

3 消息傳輸概率計算

3.1 消息成功傳輸概率計算

由于機會網(wǎng)絡(luò)中不存在完整的端到端鏈路、網(wǎng)絡(luò)延時大等特點，網(wǎng)絡(luò)采用多跳方式進行消息的轉(zhuǎn)發(fā)。通過分析消息在網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)方式，進而估計消息副本在網(wǎng)絡(luò)中的擴散程度，從而估計出消息遞交概率。假設(shè)網(wǎng)絡(luò)中共有N個節(jié)點，消息其它副本在時刻t的擴散范圍為I(t)，進而估計其它消息副本擴散范圍為I(t)/N-r，因此，消息的成功傳輸概率如式(11)所示

(11)

式中：r為當(dāng)前副本經(jīng)過的節(jié)點數(shù)。

綜合式(6)、式(11)，可得消息傳輸成功率概率

(12)

3.2 消息成功傳輸概率計算

消息離開節(jié)點概率，即消息在未來一段時間內(nèi)成功傳遞給下一跳節(jié)點的概率。機會網(wǎng)絡(luò)中無法確定消息傳輸?shù)南乱惶?jié)點，本文從相遇節(jié)點入手，綜合考慮在D時間范圍內(nèi)相遇節(jié)點與該節(jié)點間的關(guān)系。

(1)節(jié)點i僅存在一個相遇節(jié)點j

文獻[11,12]指出機會網(wǎng)絡(luò)節(jié)點相遇時間間隔具有近似服從參數(shù)為λ的冪指數(shù)指數(shù)分布的特點，節(jié)點i與節(jié)點j之間相遇時間間隔Δtij的概率密度函數(shù)為

fij(Δtij)=λije-λijΔtij,Δtij=tnext-tlast

(13)

式中：λij為節(jié)點i、j節(jié)點間相遇率，tnext為節(jié)點i、j下一次相遇時刻，tlast為節(jié)點i與節(jié)點j上一次相遇時刻。

因此，節(jié)點i、j在t時刻相遇的概率密度函數(shù)為

fij(t)=λije-λij(t-tlast)

(14)

則在D時間范圍內(nèi)消息m成功離開節(jié)點i的概率估計為

(15)

式中：t1為當(dāng)前時刻，D為消息歷史平均每跳的所需時間。

網(wǎng)絡(luò)中消息的剩余時間可能會小于當(dāng)前消息平均每跳所用時間，此時，時間D的取值D=TTLm_left

(16)

式中：TTLm_init為為消息初始生存時間，hopm為消息m已傳遞跳數(shù)，TTLm_left為消息的剩余生存時間。

(2)節(jié)點i存在n個相遇節(jié)點

進一步考慮節(jié)點i存在n個相遇節(jié)點時消息m成功離開節(jié)點i的概率。即在D時間內(nèi)節(jié)點i將消息傳遞給其任意一個相遇節(jié)點的概率，傳遞給其所有相遇節(jié)點的概率期望值

(17)

式中：wij為節(jié)點i中消息m與節(jié)點j運動相似性所占的相對權(quán)重

(18)

3.3 消息等待傳輸概率計算

(19)

結(jié)合式(6)，式(17)及式(19)可以得到

(20)

4 消息轉(zhuǎn)發(fā)效用與存儲效用計算

為了提高消息傳輸?shù)挠行?，有必要對消息進行篩選，進而得到應(yīng)該傳輸哪些消息以及按照怎樣的順序進行傳輸。

網(wǎng)絡(luò)節(jié)點i與節(jié)點j相遇，存儲在節(jié)點i緩存中消息，利用得到節(jié)點j的運動信息，計算經(jīng)由節(jié)點j轉(zhuǎn)發(fā)的效用值。消息m轉(zhuǎn)發(fā)效用值為

(21)

在節(jié)點i的緩存溢出時，節(jié)點i中各個消息計算其轉(zhuǎn)發(fā)效用。節(jié)點i中的消息m的存儲效用為

(22)

式中：Sim(m)max為節(jié)點i的其它消息與消息m運動相似性的最大值

(23)

5 CMA-MS消息管理過程

利用節(jié)點i與節(jié)點j相遇時消息傳輸過程闡述CMA-MS策略，節(jié)點i與節(jié)點j傳輸消息的交互過程如下：

(1)借助于掃描機制，節(jié)點i、j彼此發(fā)現(xiàn)對方，并將以對方節(jié)點作為目的節(jié)點的消息傳輸給對方。

(2)節(jié)點i、j交換各自相遇節(jié)點集信息(相遇次數(shù)、平均相遇間隔時間、最近一次相遇時刻等)。

(4)節(jié)點i利用步驟(2)所獲得的信息，計算各消息的轉(zhuǎn)發(fā)效用VT(m,j)并進行降序排序，根據(jù)節(jié)點j中可用緩存空間大小以及消息轉(zhuǎn)發(fā)效用值，得到消息轉(zhuǎn)發(fā)列表。

(5)節(jié)點i按照轉(zhuǎn)發(fā)列表進行消息傳輸。

(6)當(dāng)節(jié)點i的緩存溢出時，計算節(jié)點i中的各個消息的存儲效用VC(m,i)并進行降序排序，優(yōu)先丟棄存儲效用較低的消息。

同理節(jié)點j向節(jié)點i發(fā)送消息存在類似的消息管理過程。

6 仿真與分析

采用機會網(wǎng)絡(luò)環(huán)境模擬器[13]對本文的算法在消息交付率、開銷比、傳輸時延等性能指標(biāo)方面進行仿真驗證。仿真參數(shù)設(shè)置見表1。

表1 參數(shù)設(shè)置

仿真場景設(shè)置如下：仿真場景區(qū)域為3400 m×4000 m的方形區(qū)域，區(qū)域中分布著N個節(jié)點，節(jié)點的數(shù)目依據(jù)場景需要可以進行修改。網(wǎng)絡(luò)中節(jié)點移動模型為RWP，路由協(xié)議采用改進的概率路由，信道傳輸速率為2 Mbps，仿真時間設(shè)定為43200 s(12 h)，消息大小設(shè)定為500 K-1 M，不考慮節(jié)點通信半徑的影響，節(jié)點的通信半徑為10 m。CMA-MS策略不考慮消息生存時間差異，TTL設(shè)置為3600 s。

為了分析緩存管理策略在不同場景設(shè)置下性能表現(xiàn)，本小節(jié)仿真從節(jié)點緩存空間大小、網(wǎng)絡(luò)中節(jié)點數(shù)目驗證CMA-MS策略的網(wǎng)絡(luò)性能，并將其與CMA-MS策略與DY策略、FIFO策略以及EBMP策略的網(wǎng)絡(luò)性能進行比較。

(1)緩存空間對的網(wǎng)絡(luò)性能的影響

對不同節(jié)點緩存空間大小下的網(wǎng)絡(luò)性能進行仿真，其中網(wǎng)絡(luò)中節(jié)點數(shù)量設(shè)置為固定值120，節(jié)點緩存空間大小的變化范圍：5 M～40 M，每次增幅為5 M。網(wǎng)絡(luò)性能仿真結(jié)果如圖1～圖3所示。

圖1 不同緩存空間大小的投遞率比較

圖2 不同緩存空間大小的平均時延比較

圖3 不同緩存空間大小的網(wǎng)絡(luò)開銷比較

圖1描述了消息投遞率隨節(jié)點緩存空間增加的變化趨勢。從整體看，4種管理策略的投遞率變化趨勢一致，隨著節(jié)點緩存空間增大而呈現(xiàn)上升的趨勢。從局部看，相比于EBMP策略、FIFO策略以及DY策略，CMA-MS策略的消息投遞率整體高于其它3種管理策略，其性能分別提升了5.1%、18.19%和32.83%。

消息平均傳輸時延隨節(jié)點緩存空間增加而增大的趨勢如圖2所示，當(dāng)節(jié)點緩存空間增至30M左右時，CMA-MS策略、EBMP策略以及DY策略的平均傳輸時延基本保持不變，F(xiàn)IFO策略的平均時延還在緩慢增加。綜合比較，CMA-MS策略的平均傳輸時延低于EBMP策略、FIFO策略以及DY策略，管理策略的性能優(yōu)于其它3種路由。

圖3描述了網(wǎng)絡(luò)開銷比在節(jié)點緩存空間不斷增加情況下的變化趨勢。在節(jié)點緩存空間不斷增加的過程中，CMA-MS策略、EBMP策略以及FIFO策略的網(wǎng)絡(luò)開銷比呈現(xiàn)出下降趨勢，DY策略雖有起伏，但也呈現(xiàn)下降趨勢。從局部看，DY策略的開銷比變化波動比其它3種策略要大，4種緩存管理策略網(wǎng)絡(luò)開銷比都存有一個近似的最優(yōu)緩存大小(CMA-MS策略為35 M，EBMP策略為30 M，F(xiàn)IFO策略為25 M，DY策略為10 M)，同時CMA-MS策略的網(wǎng)絡(luò)開銷比整體上較小，優(yōu)于其它3種緩存管理策略。

(2)網(wǎng)絡(luò)節(jié)點數(shù)目對網(wǎng)絡(luò)性能的影響

通過仿真分析不同網(wǎng)絡(luò)規(guī)模情況下的網(wǎng)絡(luò)性能，設(shè)置消息大小為500 kb-1 Mb，緩存設(shè)置為32 M，節(jié)點數(shù)目取值60-200，每次增幅為20。網(wǎng)絡(luò)性能的仿真結(jié)果如圖4～圖6所示。

圖4 不同節(jié)點數(shù)目的投遞率比較

圖5 不同節(jié)點數(shù)目的平均時延比較

圖6 不同節(jié)點數(shù)目的網(wǎng)絡(luò)開銷比較

由圖4消息投遞率隨網(wǎng)絡(luò)節(jié)點數(shù)量增加的變化趨勢可以看出投遞率隨網(wǎng)絡(luò)規(guī)模的增大而呈現(xiàn)上升趨勢。相比于EBMP策略、FIFO策略以及DY策略，CMA-MS策略的消息投遞率分別提升了8.1%、32.65%和54.38%。

由圖5消息平均傳輸時延隨節(jié)點數(shù)目增加的變化趨勢可以看出平均傳輸時延隨著網(wǎng)絡(luò)規(guī)模的增大均呈現(xiàn)出先下降后上升的趨勢，當(dāng)節(jié)點數(shù)目為140時，CMA-MS策略、EBMP策略、FIFO策略以及DY策略的平均傳輸時延達到最小。CMA-MS策略的平均傳輸時延在網(wǎng)絡(luò)節(jié)點數(shù)目處在140-180時，網(wǎng)絡(luò)平均傳輸時延在基本保持不變，大約為2700 s。CMA-MS策略的平均傳輸時延性能指標(biāo)優(yōu)于EBMP策略、FIFO策略以及DY策略。

圖6描述了網(wǎng)絡(luò)開銷比在節(jié)點數(shù)目不斷增加情況下的變化趨勢。在節(jié)點數(shù)量不斷增加的過程中，4種緩存管理策略的網(wǎng)絡(luò)開銷比都呈現(xiàn)出不斷增加的趨勢。從局部看，EBMP策略、FIFO策略以及DY策略的增長率隨著節(jié)點數(shù)目增多在不斷減少，在總體上CMA-MS管理策略的開銷比較小，優(yōu)于其它3種管理策略。

7 結(jié)束語

針對機會網(wǎng)絡(luò)節(jié)點緩存管理中存在的節(jié)點盲目攜帶和轉(zhuǎn)發(fā)消息而使得網(wǎng)絡(luò)有限的資源浪費的問題，通過研究節(jié)點移動特征，提出了一種基于運動相似性的緩存管理策略，該方法充分考慮了節(jié)點運動與消息轉(zhuǎn)發(fā)路徑的相似性，可有效減少節(jié)點盲目攜帶和轉(zhuǎn)發(fā)消息，減少不必要的網(wǎng)絡(luò)資源消耗。通過仿真驗證了策略的有效性，能夠有效提升網(wǎng)絡(luò)投遞率，降低網(wǎng)絡(luò)開銷和傳輸時延。未來的工作可在運動相似性研究的基礎(chǔ)上，進一步研究傳輸消息的相關(guān)性并優(yōu)化緩存管理策略。