基于運動相似性的機會網絡緩存管理策略

張 力，陳瀅生，王言通

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

0 引 言

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

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

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

1 消息擴散程度估計

機會網絡消息擴散過程模型與傳統網絡模型相比，無論是網絡規模還是網絡中消息傳輸方式都存在很大差異。傳染病模型理論是被廣泛使用研究消息傳輸的理論。最早是由Kermack等在研究物種繁殖和死亡過程時提出的。該模型中將個體所處的狀態劃分為3種：易傳染，感染和治愈，個體總是處在3種狀態中的某一個狀態。在傳播過程中，個體存在著被感染概率、傳播概率以及治愈概率。近幾年，研究人員將傳染病模型引入到機會網絡，并且取得一些研究成果。如文獻[9]提出了一種自適應概率感染和自適應限時消息轉發的路由機制，實現了更為高效、可靠的網絡信息傳播的動態解決方案。

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

(1)

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

(2)

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

由此可知，網絡中節點的相遇頻率與節點相對移動速度、節點的通信半徑成正比，與網絡面積成反比。

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

(3)

傳染模型可以擴展到概率轉發路由機制中，即兩節點相遇時，感染節點根據概率值p值將消息轉發給易傳染節點。擴展模型表示如下

(4)

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

(5)

根據概率轉發消息的路由是將消息轉發給與目的節點相遇概率更高的節點。本文以傳染模型的概率擴展模型作為研究基礎，將節點運動相似性作為擴展模型中的“概率”，估計到網絡中傳輸的消息副本數目

(6)

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

2 運動相似性計算

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

2.1 節點運動相似性

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

(7)

2.2 消息運動相似性

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

(8)

2.3 節點與消息運動相似性

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

(9)

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

(10)

3 消息傳輸概率計算

3.1 消息成功傳輸概率計算

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

(11)

式中：r為當前副本經過的節點數。

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

(12)

3.2 消息成功傳輸概率計算

消息離開節點概率，即消息在未來一段時間內成功傳遞給下一跳節點的概率。機會網絡中無法確定消息傳輸的下一跳節點，本文從相遇節點入手，綜合考慮在D時間范圍內相遇節點與該節點間的關系。

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

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

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

(13)

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

因此，節點i、j在t時刻相遇的概率密度函數為

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

(14)

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

(15)

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

網絡中消息的剩余時間可能會小于當前消息平均每跳所用時間，此時，時間D的取值D=TTLm_left

(16)

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

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

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

(17)

式中：wij為節點i中消息m與節點j運動相似性所占的相對權重

(18)

3.3 消息等待傳輸概率計算

(19)

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

(20)

4 消息轉發效用與存儲效用計算

為了提高消息傳輸的有效性，有必要對消息進行篩選，進而得到應該傳輸哪些消息以及按照怎樣的順序進行傳輸。

網絡節點i與節點j相遇，存儲在節點i緩存中消息，利用得到節點j的運動信息，計算經由節點j轉發的效用值。消息m轉發效用值為

(21)

在節點i的緩存溢出時，節點i中各個消息計算其轉發效用。節點i中的消息m的存儲效用為

(22)

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

(23)

5 CMA-MS消息管理過程

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

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

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

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

(5)節點i按照轉發列表進行消息傳輸。

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

同理節點j向節點i發送消息存在類似的消息管理過程。

6 仿真與分析

采用機會網絡環境模擬器[13]對本文的算法在消息交付率、開銷比、傳輸時延等性能指標方面進行仿真驗證。仿真參數設置見表1。

表1 參數設置

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

為了分析緩存管理策略在不同場景設置下性能表現，本小節仿真從節點緩存空間大小、網絡中節點數目驗證CMA-MS策略的網絡性能，并將其與CMA-MS策略與DY策略、FIFO策略以及EBMP策略的網絡性能進行比較。

(1)緩存空間對的網絡性能的影響

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

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

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

圖3 不同緩存空間大小的網絡開銷比較

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

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

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

(2)網絡節點數目對網絡性能的影響

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

圖4 不同節點數目的投遞率比較

圖5 不同節點數目的平均時延比較

圖6 不同節點數目的網絡開銷比較

由圖4消息投遞率隨網絡節點數量增加的變化趨勢可以看出投遞率隨網絡規模的增大而呈現上升趨勢。相比于EBMP策略、FIFO策略以及DY策略，CMA-MS策略的消息投遞率分別提升了8.1%、32.65%和54.38%。

由圖5消息平均傳輸時延隨節點數目增加的變化趨勢可以看出平均傳輸時延隨著網絡規模的增大均呈現出先下降后上升的趨勢，當節點數目為140時，CMA-MS策略、EBMP策略、FIFO策略以及DY策略的平均傳輸時延達到最小。CMA-MS策略的平均傳輸時延在網絡節點數目處在140-180時，網絡平均傳輸時延在基本保持不變，大約為2700 s。CMA-MS策略的平均傳輸時延性能指標優于EBMP策略、FIFO策略以及DY策略。

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

7 結束語

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