鄒　鑫,符　敏,陳曉丹（華南師范大學　物理與電信工程學院，廣州　510006）

基于消息參數(shù)的機會網(wǎng)絡緩存隊列管理策略

鄒鑫,符敏,陳曉丹
（華南師范大學物理與電信工程學院，廣州510006）

摘要：為提高機會網(wǎng)絡的傳輸效率，根據(jù)消息路由跳數(shù)、數(shù)據(jù)大小與自身攜帶的TTL等參數(shù)計算副本的緩存參數(shù)與轉(zhuǎn)發(fā)效用值做出轉(zhuǎn)發(fā)或替換的決策，由消息目的節(jié)點與中繼節(jié)點的歷史相遇次數(shù)判斷消息副本與中繼節(jié)點的相關度，根據(jù)人類活動路徑特定的模式，設計出基于消息參數(shù)的緩存管理與隊列管理策略。仿真實驗顯示，此緩存策略可有效提高網(wǎng)絡的成功投遞率，降低平均投遞延遲，具有較好的網(wǎng)絡性能。

關鍵詞：機會網(wǎng)絡；權(quán)值估計；緩存隊列管理；消息效用

0　引言

機會網(wǎng)絡[1]的節(jié)點利用其移動性，在沒有完整鏈路的網(wǎng)絡中使用“存儲-攜帶-轉(zhuǎn)發(fā)”的路由方式傳遞消息?，F(xiàn)存的基本網(wǎng)絡管理策略有[2-3]：DL(DropLastReceived)：丟棄最新接收的副本；DLR(DropLeastRecentlyReceived)：丟棄在緩存中駐留最久的消息副本；DOA(DroptheOldest)：丟棄已生存時間最長的消息。KRIFA等人[4]根據(jù)副本的歷史信息估計其在網(wǎng)絡中的副本數(shù)，并推導出能滿足最小延遲以及最大傳輸率所需的刪除條件。文獻[5]提出了一種基于節(jié)點集群的緩存統(tǒng)一維護管理策略，利用P2P網(wǎng)絡[6]的相關技術(shù)，將相鄰的節(jié)點構(gòu)成一個簇，并將能量較高且較穩(wěn)定的一個節(jié)點作為簇頭，通過組網(wǎng)內(nèi)實時在簇頭節(jié)點上建立更新樹并發(fā)送更新的消息。請求節(jié)點與簇頭的路由距離比它到源節(jié)點的路由距離相對較短，因此這樣的策略使節(jié)點網(wǎng)絡連接更可靠、響應延遲更短和能量消耗更小。葉暉等人[7]提出ON-CRP (OpportunisticNetworkingCacheReplacementPolicy)機會網(wǎng)絡緩存替換策略，利用消息副本與不同目的節(jié)點的相關度來執(zhí)行緩存替換。由節(jié)點的社會屬性可找出節(jié)點的行為模式，然后以節(jié)點群組為目標進行消息遞交，但由于單一地依靠消息與節(jié)點的關聯(lián)度進行替換判斷，可能會使消息在緩存中保存時間過長，造成投遞延遲增加。

本文綜合消息的全局遞交率，根據(jù)人類移動模型[8]中表現(xiàn)出的節(jié)點移動規(guī)律，考察網(wǎng)絡中遞交消息副本的路由記錄與全局歷史緩存信息，利用消息參數(shù)反映的各中繼節(jié)點和目的節(jié)點間的相對關系提出MIPM（MessageInformationforPriorityManagement）緩存策略。根據(jù)參數(shù)進行緩消息存隊列的管理，由已傳遞消息的副本計算參數(shù)與路由向量記錄判斷消息送達的可能性，從而充分利用節(jié)點有限緩存，實現(xiàn)消息最大的成功投遞率并降低投遞延遲，以提高網(wǎng)絡整體性能。

1　基于消息參數(shù)的緩存管理

提出基于消息參數(shù)的緩存管理算法包括緩存管理替換與隊列管理兩個部分。其中替換策略的核心是通過估計副本緩存參數(shù)與緩存內(nèi)消息進行比較替換，各節(jié)點根據(jù)自身情況，結(jié)合緩存中的消息參數(shù)進行取舍判定；隊列管理采用路徑向量匹配排隊策略，根據(jù)節(jié)點維護的狀態(tài)信息結(jié)構(gòu)進行緩存隊列排序管理。

1.1副本緩存參數(shù)

在機會網(wǎng)絡中，網(wǎng)絡擁塞通常是由過多消息副本造成的。選取主要影響傳輸效率的兩個參數(shù)，消息副本數(shù)和傳遞深度進行緩存管理，通過控制消息副本數(shù)或根據(jù)消息參數(shù)變化找到傳輸較優(yōu)的平衡點。各參數(shù)定義如表1所示。

表1　緩存參數(shù)與定義

該策略在消息副本傳播時以副本的相關狀態(tài)參數(shù)作為其緩存參數(shù)的計算參數(shù)，使單個節(jié)點對任一消息i計算的緩存參數(shù)更符合當前網(wǎng)絡的傳輸優(yōu)化條件。緩存策略不控制消息副本轉(zhuǎn)發(fā)次數(shù)的條件下，消息i產(chǎn)生后會被各節(jié)點在相遇時復制并轉(zhuǎn)發(fā)。當每個節(jié)點收到新的消息時，根據(jù)副本攜帶的各參數(shù)來估算此消息在整個網(wǎng)絡中大致的副本數(shù)量nt(i)，并依此計算出在緩存內(nèi)分配的優(yōu)先值Uj(i)，進而在緩存溢出時根據(jù)Uj(i)對相應的副本做出取舍判斷。

消息i緩存參數(shù)的計算表達式：

其中Uj(i)表示消息i到達節(jié)點j時的緩存參數(shù)，pj(i)是節(jié)點j中消息副本i的效用值。由多副本傳輸機制，在任一時刻t，對于消息i可知其副本的消息剩余存活時間越小，則消息i在網(wǎng)絡中停留的時間越長，被節(jié)點復制轉(zhuǎn)發(fā)的副本越多，進而增大其成功投遞率。

由文獻[9]，[10]可知，在大多數(shù)的移動模型中，任意兩節(jié)點的相遇時間t服從指數(shù)分布，或在時間上表現(xiàn)出類似指數(shù)衰減的曲線，如隨機路點模型[11]、隨機路線模型、隨機方向模型、社區(qū)模型[12]，以及在現(xiàn)實生活中用移動設備采集的真實路徑模型[13-14]等。

假設網(wǎng)絡中共生成了Mt個互不相同的消息，在任一時刻t下，節(jié)點做出判斷，有可能會將生存時間為Tt(i)的消息i丟棄，對于任一消息i∈[1,Mt]，Dt(i)表示從消息產(chǎn)生至時刻t止，緩存過消息i的節(jié)點總數(shù)（源節(jié)點除外），nt(i)為在時刻t下攜帶有消息i副本的節(jié)點數(shù)，則整個網(wǎng)絡在t時刻對全部消息的平均全局遞交概率Wt由下式表示：

其中：

Lt為t時刻時網(wǎng)絡中的節(jié)點總數(shù)由以上定義描述可知，有nt(i)≤Dt(i)+1。由于兩節(jié)點間的相遇時間服從參數(shù)為λ的指數(shù)分布[15]，則消息i的一個副本投遞失敗的概率等價于此節(jié)點在下次相遇時碰到目標節(jié)點的時間大于消息剩余存活時間，即exp(-λRt(i))。

效用值uj(i)可看作是消息副本的臨界效用，是基于消息參數(shù)而得的某一副本相對當前節(jié)點內(nèi)全部緩存副本的一個評估值，在節(jié)點緩存溢出時的最佳緩存管理策略應是替換緩存內(nèi)效用值最小的副本，即有：

1.2隊列管理與替換算法

1.2.1入棧管理

本文MIPM算法的入棧管理中，設節(jié)點緩存內(nèi)已有n個不同的消息副本 i1～in，節(jié)點考察參數(shù)Ht(1)～Ht(n)，并將其按大小排序組成隊列。當節(jié)點j收到大小為Si0的消息i0時，首先判斷緩存容量，若BSj≥Si0，則可將i0直接放入緩存隊列；若BSjSi0，即可將i0放入緩存。

從一個消息產(chǎn)生開始，每個消息及其副本都帶有唯一的路由表，用以記錄此副本在網(wǎng)絡中經(jīng)過的節(jié)點。消息的路由表用一個一維數(shù)組RV表示，記作RV=[R1,R2,R3,...,Rn]。其中Ri(i=1,2,...,m)表示此副本經(jīng)過的第i個中繼節(jié)點的ID。隨著消息副本在網(wǎng)絡中的復制和傳遞，每到一個中繼節(jié)點，該節(jié)點即讀取此副本的目的節(jié)點ID和其路由數(shù)組RV，并將其加入自身維護的區(qū)域路由列表中，此表大小為n×m，不同節(jié)點的路由記錄來自緩存過的副本攜帶的路由表。

1.2.2出棧管理

當網(wǎng)絡中的節(jié)點移動時，它們相遇后可進行通信。假設某節(jié)點J碰到網(wǎng)絡中另一節(jié)點K時，兩節(jié)點在可進行消息交換的條件下，先獲取對方的ID，分別記作NA和NB，然后在各自的路由列表中查詢此ID。若ID存在，說明對方曾作為網(wǎng)絡中某條鏈路Ri的中繼節(jié)點Riy遞交過消息，它遇見Ri內(nèi)上下節(jié)點Riy+1和Riy-1的概率較其他隨機節(jié)點大。再讀取對方Ri的全部中繼節(jié)點ID，到緩存中匹配各消息副本的目的節(jié)點Dx，若存在，說明此副本到達其目的節(jié)點的鏈路在網(wǎng)絡中曾經(jīng)存在。同時，依照節(jié)點活動的社會規(guī)律性，同一鏈路中的各結(jié)點再次相遇的概率大于其他節(jié)點。因此可判斷對方結(jié)點是潛在的高效遞交中繼，即可把相應的消息副本發(fā)送給對方。若匹配失敗，說明對方節(jié)點是在本節(jié)點歷史鏈路中首次出現(xiàn)，則按消息副本緩存參數(shù)Uj(i)高低將緩存內(nèi)消息副本排序后，發(fā)送Uj(i)最高的副本給對方節(jié)點。

各節(jié)點相互傳遞消息副本之后，副本的Rv都會自動將接收方節(jié)點的ID記錄到向量末尾并更新一次路由列表。

2　仿真驗證與分析

2.1仿真環(huán)境設置

使 用 theONE(OpportunisticNetworkEnvironment)平 臺[16]作為網(wǎng)絡仿真工具。路由協(xié)議使用傳染病路由算法[17](Epidemic Immunity)，仿真區(qū)域為4500m×3400m的城市道路網(wǎng)，移動模型使用隨機路點模型RWP(RandomWayPoint)，仿真時間為43200秒。各個節(jié)點在本地對緩存內(nèi)的消息按優(yōu)先級排序，通信方式為藍牙傳輸，通信范圍10m，信道傳輸速率256KBit/s，初始化消息生存時間為18000s。默認節(jié)點緩存大小為20M，消息大小為500-1000kByte，產(chǎn)生間隔為25-35s。

2.2MIPM策略性能分析

本小節(jié)在不同的條件下對提出的緩存管理算法進行了仿真實驗。對比本文的MIPM策略和具有代表性的RO(RemovetheOldest)策略：丟棄在網(wǎng)絡中最長駐留時間的消息。本節(jié)主要以消息投遞率，網(wǎng)絡消耗量和傳輸延遲的性能指標對算法進行評估，仿真以上管理策略并對它們的網(wǎng)絡性能進行比較。

當節(jié)點緩存大小從20M增加至50M時，對比兩種策略的網(wǎng)絡投遞率。網(wǎng)絡中節(jié)點數(shù)固定為210個。從圖1中可看出，隨著節(jié)點緩存空間的增加，兩種策略的投遞率均有上升，而在緩存空間5M時MIPM策略的遞交率比RO策略高約154.5%，緩存到50M時同比高約31.9%，且在緩存大小超過25M后MIPM算法的遞交率上升變化趨緩，穩(wěn)定在90%左右。

在同樣的仿真設置中，考察各策略的網(wǎng)絡開銷。如圖2所示，當節(jié)點緩存僅有5M時，兩種策略所得網(wǎng)絡開銷較接近，且緩存在增加的過程中，RO的網(wǎng)絡消耗下降明顯，MIPM在節(jié)點緩存大于10M后即無明顯下降趨勢，在200附近上下波動，是因為算法本身的限制使得節(jié)點在碰到合適的中繼節(jié)點后繼續(xù)發(fā)送消息；RO策略在有足夠大的緩存時會減少節(jié)點的丟包次數(shù)，單個節(jié)點攜帶消息的平均時間更長，因此其網(wǎng)耗相對較小，在緩存50M時的網(wǎng)耗僅為MIPM的39.1%。

同樣的，在圖3中當節(jié)點數(shù)量恒定為210個時，不同算法的網(wǎng)絡遞交延遲有較大差別。當緩存為5M時MIPM的延遲約為RO策略的48.8%，隨著緩存的增加，其遞交延遲也增加。到緩存增為50M時MIPM平均延遲為RO的46.2%，RO上升58.5%，MIPM上升50%，但在這個方面MIPM有比較明顯的優(yōu)勢，能以更少的時間遞交信息。

在緩存固定為20M而節(jié)點數(shù)增加的條件下，兩種策略表現(xiàn)出較平穩(wěn)的網(wǎng)絡遞交率，從圖4看出，MIPM的遞交率在80%上下波動，而RO策略的遞交率在50%附近，有下降趨勢。節(jié)點數(shù)量的增加對兩種算法的網(wǎng)絡遞交率并無太大影響，MIPM因在隊列管理中加入消息參數(shù)信息的判斷因而能讓節(jié)點更有目的地投遞，使網(wǎng)絡有較高的遞交率。

同樣地，圖5顯示在緩存不變而節(jié)點數(shù)從100個增加到400個時，兩種策略的網(wǎng)絡消耗也隨之增大。當節(jié)點較少時，MIPM的網(wǎng)耗略大于RO算法，在節(jié)點為350以上時，MIPM表現(xiàn)出輕微優(yōu)勢，比RO的網(wǎng)耗低約7.5%。從圖中可看出MIPM算法的網(wǎng)絡開銷在節(jié)點數(shù)變化時其穩(wěn)定性不如RO算法。節(jié)點數(shù)從100個變化到400個的過程中，MIPM增加了246.2%，RO增加了1100%。

當節(jié)點數(shù)從100變?yōu)?00時，在恒定緩存20M的條件下，對比算法的網(wǎng)絡遞交平均延遲。從圖6中可知在節(jié)點數(shù)進階增加的條件下，兩種策略的平均延遲均呈類似下降趨勢。在節(jié)點數(shù)增加300%的過程中，MIPM策略的延遲下降60%，RO策略延遲下降30.8%，而橫向比較中MIPM在節(jié)點數(shù)為100時延遲為RO的60.6%，在節(jié)點數(shù)為400時為RO的33.3%。

通過仿真實驗，本文提出的MIPM機會網(wǎng)絡緩存管理算法相比傳統(tǒng)策略有較高的成功投遞率和較少的網(wǎng)絡消耗和網(wǎng)絡延遲。從整體上評價算法對網(wǎng)絡的改善效率，在考慮消息參數(shù)與其效用值的基礎上做出緩存替換決策能比傳統(tǒng)緩存管理策略提高網(wǎng)絡遞交率約15%至40%，同時能達到較低的網(wǎng)絡遞交延遲。結(jié)論證明本文提出的MIPM緩存管理算法在實驗條件下能有較優(yōu)的網(wǎng)絡性能。

3　結(jié)論

本文主要研究基于消息參數(shù)的機會網(wǎng)絡傳輸過程的緩存管理，通過消息參數(shù)來確定副本在網(wǎng)絡中的投遞狀態(tài)，以TTL0和Si等參數(shù)計算消息的效用值pj(i)以評估其緩存價值，進而節(jié)點根據(jù)pj(i)進行緩存參數(shù)計算與執(zhí)行替換策略。在隊列管理算法中，綜合考慮消息與節(jié)點的相關度，確定節(jié)點緩存的排隊序列與轉(zhuǎn)發(fā)順序。最后仿真實驗并對比分析了MIPM緩存管理算法的網(wǎng)絡性能，仿真結(jié)果顯示本文提出的策略相對傳統(tǒng)算法能較好的適應社會網(wǎng)絡消息的投遞。本算法的網(wǎng)絡消耗在節(jié)點數(shù)變化時較不穩(wěn)定，只能在特定環(huán)境中保證較高的遞交率，且尚未考慮在現(xiàn)實網(wǎng)絡中利用群組節(jié)點的社會關系和周期性相遇時間對某類特定消息的遞交效率的評估，作為進一步提高機會網(wǎng)絡傳輸效率的研究方向之一。

參考文獻:

[1]Pelusi L, Passarella A, Conti M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine, IEEE, 2006, 44(11): 134-141.

[2]Davis J A, Fagg A H, Levine B N. Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks[C]//Wearable Computers, 2001. Proceedings. Fifth International Symposium on. IEEE, 2001: 141-148.

[3]Lindgren A, Phanse K S. Evaluation of queueing policies and forwarding strategies for routing in intermittently connected networks[C]//Communication System Software and Middleware, 2006. Comsware 2006. First International Conference on. IEEE, 2006: 1-10.

[4]Krifa A, Barakat C, Spyropoulos T. Optimal buffer management policies for delay tolerant networks[C]//Sensor, Mesh and Ad Hoc Communications and Networks, 2008. SECON'08. 5th Annual IEEE Communications Society Conference on. IEEE, 2008: 260-268.

[5]謝高崗，李振寧，李嘉寧.MANET中基于族的緩存一致性維護策略[J].軟件學報,2008,19(11):3042_3052.

[6]牛新征, 佘堃, 秦科 等. 移動 P2P 網(wǎng)絡的協(xié)作緩存優(yōu)化策略[J]. 計算機研究與發(fā)展, 2008, 45(04): 656-665.

[7]葉暉, 陳志剛, 趙明. ON-CRP: 機會網(wǎng)絡緩存替換策略研究[J].通信學報, 2010 (05): 98-107.

[8]Gonzalez M C, Hidalgo C A, Barabasi A L. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782.

[9]Chaintreau A, Hui P, Crowcroft J, et al. Impact of humanmobility on opportunistic forwarding algorithms[J].Mobile Computing, IEEE Transactions on, 2007, 6(6): 606-620.

[10]Karagiannis T, Le Boudec J Y, Vojnovic M.Power law and exponential decay of intercontact times between mobile devices[J].Mobile Computing, IEEE Transactions on, 2010, 9(10): 1377-1390.

[11]Bettstetter C, Hartenstein H, Pérez-Costa X.Stochastic properties of the random waypoint mobility model[J].Wireless Networks, 2004, 10(5): 555-567.

[12] Spyropoulos T, Psounis K, Raghavendra C S.Performance analysis of mobility-assisted routing[C]//Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing.ACM, 2006: 49-60.

[13]McNett M, Voelker G M.Access and mobility of wireless PDA users[J].ACM SIGMOBILE Mobile Computing and Communications Review, 2005, 9(2): 40-55.

[14]Hui P, Chaintreau A, Scott J, et al.Pocket switched networks and human mobility in conference environments[C]// Proceedings of the 2005 ACM SIGCOMM workshop on Delaytolerant networking.ACM, 2005: 244-251.

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

[16]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.ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2009:55.

[17]Mundur P, Seligman M, Lee G.Epidemic routing with immunity in delay tolerant networks[C]//Military Communications Conference, 2008.MILCOM 2008.IEEE.IEEE, 2008:1-7.

作者簡介：鄒鑫（1988—），男，廣西南寧人，碩士，研究方向：機會網(wǎng)絡緩存優(yōu)化。