黃沛昱，應 俊

(重慶郵電大學光電工程學院，重慶 400065)

0 引言

目前，研究人員提出了多種消息替換方法，文獻［2］將緩存空間劃分為若干個子空間并賦予不同的優(yōu)先級，當緩存溢出時，優(yōu)先級最低子空間中的消息會被丟棄。但是，劃分子空間的標準界限難以衡量。文獻［3］所提出的策略選擇剩余生存時間最小的消息進行替換，但消息的投遞狀態(tài)與多個因素直接相關，單獨使用剩余生存時間無法準確反映消息的當前狀態(tài)。利用隨機運動模型下節(jié)點相遇時間間隔成指數(shù)分布的性質(zhì)，文獻［4］提出了基于消息投遞概率的多隊列消息刪除管理機制，將緩存空間等分為3個空間區(qū)域，當空閑緩存大小不足時，優(yōu)先刪除等級最低的消息。但是該機制需預先將緩存區(qū)域等分，會造成有限資源的浪費。此外閾值的設定也是關鍵，閾值設置過小對于緩存管理沒有實質(zhì)改進，過大又會使得沒有成功投遞的消息被刪除，導致消息的成功投遞下降。文獻［5］根據(jù)經(jīng)濟學中的邊際效應理論，認為消息在網(wǎng)絡中副本數(shù)量越多，其成功投遞到目的節(jié)點的概率越大，進而設計了基于副本數(shù)量的消息替換策略。

顯然，機會網(wǎng)絡中的節(jié)點運行環(huán)境復雜，消息轉(zhuǎn)發(fā)過程受到多個方面因素的影響。因此，單純地根據(jù)某個條件來確定消息副本的替換難以有效地提高有限緩存的利用率。本文綜合考慮了消息的已生存時間(time to live，TTL)、跳數(shù)、副本數(shù)以及區(qū)域概率4個參數(shù)，對消息的投遞狀態(tài)及替換風險進行了估計，提出了一種基于消息替換風險估計的緩存管理策略(message replicating risk aware cache management，MRRCM)。

1 投遞狀態(tài)估計

如前所述，單純地根據(jù)某個消息狀態(tài)參數(shù)無法準確獲知其在網(wǎng)絡中的傳播狀態(tài)［6］，此外，此種“存儲－攜帶－轉(zhuǎn)發(fā)”架構(gòu)下的消息傳輸狀態(tài)與給定消息在某個區(qū)域的密度及區(qū)域內(nèi)節(jié)點與消息目的節(jié)點的相遇概率直接相關，稱之為消息i的區(qū)域概率。為了能夠準確地評估消息的傳輸狀態(tài)，本文綜合考慮消息的已生存時間、跳數(shù)、副本數(shù)及區(qū)域概率4個參數(shù)，以分布式的方式實現(xiàn)傳輸狀態(tài)估計，進而為消息替換提供依據(jù)。

1.1 權重分配

考慮到上述因素對于消息傳輸狀態(tài)的影響程度并不相同，本文運用層次分析法(analytic hierarchy process，AHP)確定各個參數(shù)的權重。

1 )構(gòu)造判斷矩陣。判斷矩陣如(1)式所示，表示本層所有因素針對上一層某一個因素相對重要性的比較。層次結(jié)構(gòu)如圖1所示，C1，C2，C3，C4代表各因素對目標O的重要性。

圖1 層次結(jié)構(gòu)圖Fig.1 Hierarchical chart

C1為消息已生存時間對傳輸狀態(tài)的影響因子，C2為跳數(shù)H對傳輸狀態(tài)的影響因子，該參數(shù)能夠反映消息的轉(zhuǎn)發(fā)深度，顯然，轉(zhuǎn)發(fā)深度較高的消息具有更高的成功投遞概率［7］。與文獻［6］所得到的結(jié)論類似，即以跳數(shù)為依據(jù)所獲得的消息投遞狀態(tài)更為準確，本文所建立的層次模型中，置a12=1/2。C3表示消息副本數(shù)M對其傳輸狀態(tài)的影響因子。根據(jù)機會網(wǎng)絡消息轉(zhuǎn)發(fā)過程的基本原理，若某個消息在網(wǎng)絡中的副本數(shù)越多，其成功投遞的概率也隨之增大［8］。相比于 C1，C2，消息副本的數(shù)量能夠更直接地反映其自身的傳輸狀態(tài)，因此，置a13=1/5，a23=1/3。C4表示區(qū)域密度及目的節(jié)點對于給定區(qū)域活躍程度對消息傳輸狀態(tài)的影響因子。消息傳輸包括存儲、攜帶及轉(zhuǎn)發(fā)3個過程，相比于 C1，C2，區(qū)域概率能夠反映更多的網(wǎng)絡連接狀態(tài)信息，因此，置a14=1/3，a24=1/2。而C3在感知范圍上顯著大于C4，置 a34=2。

2 )權重計算。根據(jù)判斷矩陣，可得最大特征根λ所對應的特征向量w，如式(2)所示。

這件事情翠姨是曉得的，而今天又見了我的哥哥，她不能不想哥哥大概是那樣看她的。她自覺地覺得自己的命運不會好的?，F(xiàn)在翠姨自己已經(jīng)訂了婚，是一個人的未婚妻；二則她是出了嫁的寡婦的女兒，她自己一天把這個背了不知有多少遍，她記得清清楚楚。

所求特征向量w經(jīng)歸一化即為各因素的權重分配。本文使用雅克比法得到 w為(0.0882，0.157，0.4829，0.272)T，λ =4.015。

3 )一致性檢測。為了驗證以上得到的權重分配結(jié)果是否合理，需要對判斷矩陣進行一致性檢測。一致性指標定義如式(3)所示

(3)式中:CI為一致性指標;n為矩陣維數(shù)。代入數(shù)值得到CI=0.005。當CI=0時，有完全的一致性，CI接近于0，表示判斷矩陣有滿意的一致性，CI越大，不一致程度越嚴重。為了衡量CI的大小，引入隨機一致性指標RI，1～9階判斷矩陣的RI值如表1所示。

表1 平均隨機一致性指標RI的值Tab.1 Values ofmean random consistency index RI

1.2 消息投遞狀態(tài)估計

如前所述，消息i的各維狀態(tài)參數(shù)數(shù)值越大，則該消息成功投遞的概率越高。因此，準確估計給定消息的傳輸狀態(tài)是評估消息冗余程度的關鍵。給定消息的狀態(tài)參數(shù)TTL和H可由封裝在分組頭部的消息產(chǎn)生時間及消息傳遞路徑獲知。狀態(tài)參數(shù)M及P的確定需要節(jié)點獲知網(wǎng)絡中全部節(jié)點的狀態(tài)信息，即網(wǎng)絡中所有節(jié)點的存儲情況及區(qū)域內(nèi)的節(jié)點相遇情況。受限于機會網(wǎng)絡的分布式特性，節(jié)點無法采用泛洪的方式將自身的狀態(tài)信息在整個網(wǎng)絡范圍內(nèi)及時、準確地擴散，因此，本文通過節(jié)點間的交互，以盡力而為的方式感知網(wǎng)絡狀態(tài)信息。每個節(jié)點本地維護相應的節(jié)點信息列表，其中相遇信息列表記錄了該節(jié)點與網(wǎng)絡中其余節(jié)點的相遇情況，包括相遇節(jié)點地址及相遇時間，歷史消息ID列表記錄了節(jié)點存儲過的消息。節(jié)點相遇之后將轉(zhuǎn)發(fā)更新時間大于對方的節(jié)點信息。按照上述方法，節(jié)點可近似獲得網(wǎng)絡中各個節(jié)點的狀態(tài)信息。

通過統(tǒng)計列表中存儲消息i的節(jié)點數(shù)量，節(jié)點可以得到消息i的狀態(tài)參數(shù)M在t時刻的估計值。文獻［9］提出使用全網(wǎng)消息經(jīng)歷T時間之后的平均m(T)值來估計消息i在T時刻的副本數(shù)mi(T)，并認為其能更準確地估計消息i被保存的次數(shù)。文獻［10］對估計的準確度進行了理論推導及仿真驗證，推導得到m(T)服從正態(tài)分布，由正態(tài)分布性質(zhì)可知，其參數(shù)數(shù)值絕大部分都分布在均值附近，可用其均值估計其分布中的各個數(shù)據(jù)的大小，即

此外，本文中所提出的消息區(qū)域概率估計過程分為2個部分，分別為消息i的區(qū)域密度及消息i的目的節(jié)點對于該區(qū)域的活躍程度。消息的局部密度可通過對本地保存列表內(nèi)的信息獲知。根據(jù)T時間內(nèi)相遇節(jié)點的個數(shù)N(T)及其中攜帶有消息i的節(jié)點個數(shù) Mi(T)，可獲知消息 i的局部密度MDi(T)，如式(4)所示。

區(qū)域活躍度Ai(T)描述了消息i的目的節(jié)點在T時間內(nèi)與區(qū)域內(nèi)N(T)個節(jié)點的相遇次數(shù)，通過對這N(T)個節(jié)點的相遇信息列表進行查詢，可以得到相遇次數(shù)C(T)，其估計方法如式(5)所示。

根據(jù)上述得到的權重，通過式(6)可以得到隊列中各個消息的狀態(tài)加權和。

(6)式中:wj為對應的權重大小;Cij為消息i的狀態(tài)。由于狀態(tài)TTL，H，M，P對于消息投遞狀態(tài)的影響均為正相關。因此，根據(jù)式(6)所得到的加權和越大，則表明消息被成功投遞的可能性越高，其在網(wǎng)絡中存在的重要性就越小，反之，效用越大。

1.3 消息替換風險估計

當節(jié)點所攜帶消息的效用值都比較低的時候，繼續(xù)替換投遞狀態(tài)加權和最大的消息副本將對其所存儲的消息投遞產(chǎn)生較大影響，因此，此種情況下還需要考慮替換消息所帶來的風險。若節(jié)點替換消息副本i，則對于這個消息來說可能造成的結(jié)果有2個:消息i仍然被成功投遞，沒有損失;消息i沒有被成功投遞，造成損失。由于狀態(tài)參量的大小無法準確地反映出替換消息所帶來的風險，本文運用數(shù)據(jù)挖掘的方法評估對給定消息替換的風險。對于每條消息的替換過程來說，節(jié)點需要記錄如下信息＜ID，TTL，H，mi(t)，Pi，β＞，其中 ID 為替換消息的編號，以唯一地標識給定消息，TTL，H，mi(t)以及Pi為替換消息i時的狀態(tài)，稱作替換特征。β為標簽，當節(jié)點因緩存擁塞而主動丟棄消息時，該參數(shù)β置為0，若后來收到與ID對應的確認消息，則將β重置為 1;當成功投遞未替換消息時，直接置β為1。

對于給定節(jié)點來說，若消息i與其歷史替換消息m具有相似的特征，則表明兩者在網(wǎng)絡中的投遞狀態(tài)相近。由機會網(wǎng)絡的傳輸原理可知，消息m具有與消息i類似的投遞機會，因此，可知替換消息i產(chǎn)生損失的概率與替換與i具有相似特征的歷史消息相近。按照上述結(jié)論，若有S個與消息i相似的歷史消息被替換，其中替換后造成損失的個數(shù)為Sloss，可以得到替換消息i的風險，如式(7)所示。

為了確定各個消息與消息i的相似程度，本文采用K－均值聚類法根據(jù)記錄樣本信息的特征對消息副本進行分類［11］，然后計算消息i與各個類別的相似度，確定消息i的歸屬類別。根據(jù)聚類的特點，同一類中的對象具有較高的相似度，而不同類中的對象相似程度較低。若消息歸屬于類Cj，可以認為消息i與Cj中的對象相似。

2 MRRCM基本原理

當節(jié)點的緩存占用超過預留的閾值θ時，節(jié)點會對自身攜帶的消息進行替換，以緩解節(jié)點緩存的擁塞。

在具體執(zhí)行過程中，首先節(jié)點計算緩存隊列中各個消息的投遞加權和，確定已成功投遞概率相對最大的消息i。根據(jù)消息i替換風險程度Riski的不同，可以劃分為3種級別:高風險(Riski＞HL)，一般風險(LL≤Riski＜HL)，低風險(Riski＜LL)。其中HL，LL為風險劃分閾值。

當替換消息i的風險程度為高時，表明此類消息在網(wǎng)絡中的擴散程度較低，替換此類消息將極度浪費上游節(jié)點在轉(zhuǎn)發(fā)過程中所耗費的網(wǎng)絡資源，同時嚴重降低消息的成功投遞率，因此，對于這種情況來說，節(jié)點將不替換該消息的副本。當風險程度一般時，節(jié)點首先將該消息副本轉(zhuǎn)發(fā)給緩存剩余空間最多并且可容納該消息的鄰居節(jié)點，避免消息成功投遞率降低的同時還可以對節(jié)點負載進行均衡。若沒有鄰居節(jié)點或鄰居節(jié)點的緩存均為擁塞狀態(tài)時，則不執(zhí)行此類消息副本的轉(zhuǎn)發(fā)操作，而將其直接替換。當替換風險為低時，節(jié)點將直接替換該消息，從而將有限的緩存資源分配給其他擴散程度不高的消息以提高整體的投遞率。

3 數(shù)值結(jié)果

本文通過機會網(wǎng)絡仿真平臺(opportunistic network environment，ONE)［12］對所提的緩存管理策略MRRCM進行了實現(xiàn)，并以消息成功投遞率、網(wǎng)絡負載率和網(wǎng)絡平均傳輸時延作為指標驗證MRRCM算法的相關性能［13］。仿真采用基于免疫的傳染路由算法(epidemic immunity)，具體參數(shù)如表2所示。

表2 仿真參數(shù)設置Tab.2 Design simulation parameters

仿真場景中的節(jié)點包含汽車節(jié)點和行人節(jié)點，都是隨機選擇一個目的節(jié)點，然后按照最短路徑移動到目的節(jié)點的方式進行運動。實驗在不同緩存大小的情況下，將DropOldest，基于歷史信息刪除策略(history based drop，HBD)，MRRCM 3種緩存管理策略進行了比較，其中HDB算法以最大全網(wǎng)投遞概率為優(yōu)化目標。

消息成功投遞率如圖2所示。從結(jié)果中可知，MRRCM總體的消息成功投遞率要優(yōu)于其他2種算法。同時，投遞率隨著節(jié)點緩存的增大而提高。圖3描述了各類機制的平均時延，從結(jié)果中可知，各個機制的時延基本相同，且呈現(xiàn)出一定的上升趨勢。網(wǎng)絡負載率如圖4所示，隨著緩存容量的增加，網(wǎng)絡負載逐漸降低。

圖2 消息成功投遞率Fig.2 Message delivery rate

圖3 網(wǎng)絡平均時延Fig.3 Average network delay

4 結(jié)論

為了解決節(jié)點擁塞導致的網(wǎng)絡性能降低的問題，本文首先提出了消息投遞狀態(tài)的估計方法，并對消息替換所帶來的風險進行了估計，根據(jù)消息投遞狀態(tài)和替換風險的不同，提出了一種基于消息替換風險估計的緩存管理機制。與典型的DropOldest算法和以最優(yōu)全網(wǎng)概率的HDB算法相比，本文所提機制可以有效地提高消息的成功投遞率并降低傳輸開銷。同時，該機制具有較強的擴展性，能夠適用于任何多副本路由機制。

圖4 網(wǎng)絡負載率Fig.4 Network load rate

［1］MCMAHON，F(xiàn)ARRELL S.Delay－disruption－tolerantnetworking［J］.IEEE Internet Computing，2009，13(6):82－87.

［2］WAHIDABANU R S D，F(xiàn)ATHIMA G.A new queuing policy for delay tolerant networks［J］.International Journal of Computer Applications，2010，1(20):56－60.

［3］劉期烈，潘英俊，李云，等.延遲容忍網(wǎng)絡中基于分離時間和副本控制的路由算法［J］.北京郵電大學學報，2011，34(2):113－117.

LIU Qilie，PAN Yingjun，LIYun，et al.A Routing Algorithm Based on Separation Time and Copy Control in Delay Tolerant Network ［J］.Chongqing University of Posts and Telecommunications，2011，34(2):113－117.

［4］RASHID S，HANAN A A，AYUB Q，et al.Dynamic Prediction based Multi Queue(DPMQ)Drop policy for Probabilistic routing protocols of delay tolerant network［J］.Journal of Network and Computer Applications，2013，36(5):1395－1402.

［5］LIU Y，WANG J，ZHANG S，et al.A Buffer Management Scheme Based on Message Transmission Status in Delay Tolerant Networks［C］//Global Telecommunications Conference.Houston，Texas，USA:IEEE，2011:1－5.

［6］YUENW H，SCHULZRINNE H.Performance evaluation of time－based and hop－based TTL schemes in partially connected ad hoc networks［C］//IEEE International Conference on Communications.Istanbul，Turkey:IEEE Press，2006:3844－3849.

［7］BURGESS J，GALLAGHER B，JENSEN D，et al.Max－Prop:Routing for Vehicle－Based Disruption－Tolerant Networks［C］//Proceedings of 25th IEEE International Conference on Computer Communications.Barcelona:IEEE Press，2006:1－11.

［8］ZHANG Z S.Routing in intermittently connected mobile Ad hoc networks and delay tolerant networks Overview and challenges［J］.IEEE Communications Surveys Tutorials，2006，8(1):24－37.

［9］KRIFA A，BARAKAT C，SPYROPOULOS T.Optimal buffer management policies for delay tolerant networks［C］//The 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks.San Francisco，California，USA:IEEE Press，2008:260－268.

［10］吳大鵬，周建二，王汝言，等.機會網(wǎng)絡中消息冗余度動態(tài)估計的緩存管理策略［J］.電子與信息學報，2012，34(1):101－107.

WU Dapeng，ZHOU Jianer，WANGRuyan，etal.Messageredundancy Estimating Adaptive Buffer Management Mechanism for Opportunistic Network［J］.Journal of Electronics ＆Information Technology，2012，34(1):101－107.

［11］HAN J，KAMBERM，PEIJ.Datamining:concepts and techniques［M］.San Francisco:Morgan kaufmann，2006:401－407.

［12］吳大鵬，張普寧，王汝言.節(jié)點連接態(tài)勢感知的低開銷機會網(wǎng)絡消息傳輸策略［J］.通信學報，2013，34(3):44－52.

WU Dapeng，ZHANG Puning，WANG Ruyan.Connection Status aware cost efficient message transmission mechanism in opportunistic networks［J］.Journal on Communications，2013，34(3):44－52.

［13］MUNDUR P，SELIGMAN M，LEE G.Epidemic routing with immunity in delay tolerant networks［C］//Military Communications Conference，2008.San Diego， CA:IEEE Press，2008:1－7.

(編輯:田海江)