基于消息重要性的機會網絡能量均衡路由算法

陳志剛，殷濱安，吳嘉

（1. 中南大學軟件學院，湖南 長沙 410075；2.“移動醫療”教育部—中國移動聯合實驗室，湖南 長沙 410083）

1 引言

機會網絡[1]具有間歇式連通網絡[2]和延時容忍網絡[3]的特征，它把節點的移動當作傳輸的機會，采用“存儲—攜帶—轉發”的模式進行通信。由于機會網絡不需要節點間直接存在完整的鏈路，近年來，已經成為無線通信領域內的研究熱點[4-7]。目前已經出現了基于機會網絡的具體應用。例如，在手持設備交換網PSN(pocket switched network)[8]中，智能終端節點通過人們的移動提供局部通信的機會；MIT開發的CarTel[9]系統中，車輛可以通過移動與其他車輛獲得局部通信的機會，或與道路旁安裝的無線智能傳輸設備進行通信，從而將車輛傳感器收集的路況和車輛狀態等信息傳輸至 Internet上的服務器。

機會網絡中的節點往往是手持或車載設備[10-11]，因此，節點間的數據傳輸是不穩定的，節點可能在數據傳輸完成前離開通信范圍，導致一部分消息未能發送給對方。因此，在節點間進行數據傳輸的過程中，應該充分利用節點相遇的機會，優先傳輸重要性較高的消息。在機會網絡的實際應用中，往往有一些消息是比較緊急、比較重要的。比如，在CarTel系統中，車輛故障信息要比路況信息更為重要，服務器只有收到車輛故障信息后才能采取緊急救援等措施。在手持設備交換網中，用戶根據消息內容的重要程度不同，往往希望重要性較高的消息得到優先傳輸。

本文將節點能量和緩存空間不足等[12-13]造成傳輸中斷的因素考慮在內，關注機會網絡的實際應用中消息重要程度不同的特點，研究在機會網絡單播模式下，即所有消息只有一個目的節點條件下的消息重要性度量方法，提出了基于消息重要性的機會網絡能量均衡路由算法 MIEBR(message importance based energy balanced routing algorithm)，解決了重要消息得不到優先轉發的問題。

2 相關工作

目前的機會網絡路由算法分為零信息型和信息輔助型兩大類[14]。零信息型路由算法是指在數據轉發過程中不需要額外的信息作為輔助。典型的零信息型路由算法有 Direct Delivery[15]、Epidemic[16]和Spray and Wait[17]等。

Direct Delivery的特點是，源節點不通過中間節點轉發消息，而是通過節點的移動，直到遇到目的節點時才傳輸消息。因此，網絡中不存在消息副本，網絡開銷最小，但傳輸延時最大，很難提高消息投遞成功率。Epidemic的思想是：在節點相遇時，互相發送對方沒有的信息。這種方式在不考慮節點緩存空間和能量等因素時，消息投遞成功率較高，傳輸延時較低。但是，在實際應用中，由于網絡中存在大量的消息副本，容易造成緩存不足、網絡擁塞，導致網絡性能急劇下降。Spray and Wait的思想是：在Spray階段采用噴灑的方式將源節點的信息傳輸給所有鄰居節點。若在Spray階段沒有將消息傳輸到目的節點，則進入 Wait階段，攜帶消息的節點通過移動直到遇到目的節點后將消息轉發給目的節點。該方法解決了Epidemic消息副本數過多的問題，但由于沒有利用節點和網絡狀態等信息，傳輸成功率往往不高。

由于零信息型算法沒有考慮到實際應用中節點、數據及網絡拓撲的特征，使該類算法往往在投遞成功率、網絡開銷、傳輸延時等3個方面達不到理想平衡。而信息輔助型路由算法則是結合節點的接觸歷史、剩余能量、移動速度、鄰居變化和社會關系等信息提出的算法。典型的信息輔助型算法有PROPHET[18]、PROPICMAN[19]和Bubble Rap[20]等。

PROPHET利用節點間的歷史接觸時長和接觸次數信息來預測節點間的相遇概率，使消息向與目的節點相遇概率高的中間節點傳遞。當兩個節點相遇時，它們的相遇概率增加，否則相遇概率隨時間衰退。該算法同時考慮了相遇概率的傳遞性。相比Epidemic，該算法大大降低了路由開銷，但由于未對消息副本數做出限制，隨著消息的傳播，網絡開銷依然較大。該算法未考慮到節點的社會屬性，單純依靠歷史相遇概率來選擇下一跳節點，存在一定的不合理性。

PROPICMAN是一個基于節點社會上下文的路由算法。其思想是：節點在轉發數據時，將目的節點社會上下文信息發送給兩跳以內的鄰居節點，鄰居節點比較自身和目的節點的社會上下文信息，并將結果返回給該節點，該節點選擇兩跳范圍內社會上下文信息符合程度最高的鄰居節點作為未來兩跳的路由中轉。該算法利用了社會上下文信息，在低路由開銷下具有較高的消息投遞成功率。但是，該算法未考慮到節點的能量對節點進行消息轉發的影響，可能出現因部分節點能量消耗過快而耗盡的現象。

Bubble Rap算法通過對節點進行聚類，并計算節點的全局和局部中心度。在轉發過程中，若消息沒有進入目的節點所在的社區，則將消息發送給全局中心度高的節點。若消息進入了目的節點所在的社區，則將消息發送給該社區局部中心度高的節點。該算法太過于依賴中心度高的節點，造成中心度高的節點繁忙，中心度低的節點空閑，從而使網絡負載不均衡。

文獻[21]提出了 TBR算法，該算法結合數據分組的TTL值、跳數和數據分組大小確定消息的優先級，優先向鄰居節點轉發優先級高的消息。該算法減小了具有較高優先級消息的傳輸延時。但是，該算法在確定消息優先級時，未考慮到消息內容的重要程度。

3 模型設計

本文使用到的數學符號說明如表1所示。

表1 符號說明

3.1 節點的社會屬性

網絡中的每個用戶節點在緩存中存儲一張自身社會屬性信息表，表中包含該節點用戶的姓名、住址、專業、工作單位和愛好等信息。本文將這些信息稱為社會上下文信息。每條信息包括屬性名(attriName)和屬性值(value)。為方便節點間進行屬性值的比較，同時保護用戶的社會上下文隱私，每個屬性值映射為長度固定的散列值(hashvalue)，并且保證網絡中的每一個用戶節點具有相同的屬性名和相同的排序。節點的社會屬性信息如表2所示。

表2 社會屬性信息

節點的第i項社會屬性散列值H(wi)是由屬性值wi映射得到的長度為32 bit的十六進制數，是數據唯一且極其緊湊的數值表示形式。本文采用MD5對wi進行映射。

例如，屬性名為愛好，屬性值為乒乓球，則H(乒乓球) 的值為32 bit的十六進制數且是唯一的571c4d3c50312404d3c82b8dc02e2805。

定義節點a與節點b的社會關系強度為

其中，用 δi∈(0,1)來區分不同屬性的重要程度，δi越大，表示該項屬性越重要。Ha(wi)表示節點a第i項屬性的散列值，l為節點社會屬性數，∧為邏輯與運算。由于每個節點的屬性個數和順序相同，因此只需要l次比較就可以得到R(a,b)。當兩節點所有屬性值都相同時，即對于i∈[1,l], 有Ha(wi)∧Hb(wi) ≡1，則Rmax(a,b)= 1 。對于i∈[1,l]，當Ha(wi)∧Hb(wi) ≡ 0 時，則Rmin(a,b) =0。所以，R(a,b)的值域為[0,1]。

3.2 消息重要性的度量

消息的重要性由兩方面共同決定：1) 消息內容的重要程度，由消息發送方決定；2) 由消息的TTL值、跳數和大小決定。由此，定義消息m的重要性度量值為

其中，θm表示消息發送方根據m的內容重要程度而設定的值， θm∈(0,1)，θm越大表示m的內容越重要。TTLm為m的剩余生存時間。需要注意的是，不同于TCP/IP協議中的TTL，TCP/IP協議中的TTL表示的是消息可轉發的最大跳數，機會網絡中的TTL表示的是消息的剩余生存時間。TTL值越小，表明消息離被刪除的時間越近，越需要被優先轉發。hm為m的跳數，hm越小，表明該消息被轉發的次數越少，越需要盡快轉發。sm為m的大小，sm越小，則m中每比特的消息重要程度越大。

3.3 消息的緩存價值

機會網絡中的節點緩存空間是有限的，當傳輸過程中接收方緩存不足時，需要刪除緩存中的部分消息，從而保證節點具有足夠的緩存空間接收數據。從緩存中刪除的消息，應該具有最低的緩存價值。

定義消息的緩存價值為

其中，TTLm越小，消息m被轉發過的概率越大。反之，TTLm越大，表明消息m被轉發的概率越小，則消息m越需要被優先保留。特別地，當TTLm減為0，說明該消息已超過其時效期限，緩存價值為0。mθ越大，即消息m的內容越重要，緩存該消息的價值也就越大。

3.4 能量消耗模型

機會網絡中的節點往往是移動設備，這些節點的能量是有限的。因此，必須考慮節點能量對消息轉發的影響。

一個數據分組在由節點a轉發至節點b的過程中的能量消耗，主要包括節點a轉發一個數據分組所消耗的能量ES，以及節點b接收一個數據分組所消耗的能量ER和返回ACK給節點a所消耗的能量EACK。由此，建立節點的剩余能量模型。

設消息m的字節數為Bm，一個數據分組的字節數為Bpkt，則節點a轉發m后的剩余能量為

節點b接收m后的剩余能量為

其中，Er(old),a表示節點a轉發m前的剩余能量，Er(old),b表示節點b接收m前的剩余能量。

定義節點a的剩余能量百分比為

其中，Emax為節點的最大能量值。

本文關注的是節點在傳輸消息的過程中的能量消耗，不考慮節點能量衰減等其他因素。

3.5 節點轉發消息的收益

節點a在轉發消息m至節點b時，若節點b是消息m的目的節點，則節點a轉發消息m的收益只由消息m的重要性度量值?m決定。

若節點b不是消息m的目的節點，則不能只憑消息重要性度量值來確定消息的轉發順序。顯然，節點轉發重要性較高的消息并成功投遞到目的節點，要比重要性較低的消息的成功投遞具有更高的收益。但是，若重要性較高的消息未能成功投遞到目的節點，則節點的收益為 0。同時，為均衡網絡中各節點的剩余能量，延長網絡的生命周期，需要將消息轉發給剩余能量較多的節點。

由此，定義消息m由節點a轉發至節點b的收益為

其中，消息m的目的節點為f。ηb表示節點b的剩余能量百分比。由基于社會上下文路由算法的有效性可知，與目的節點的社會上下文信息越相似，則節點與目的節點的相遇概率越高，消息投遞成功率也就越高。因此，用R(b,f)-R(a,f)表示消息投遞成功率的增量。

圖1給出了節點轉發消息的實例。節點a有兩條消息需要轉發給節點b，節點b不是這兩條消息的目的節點。設 ηb=0.8，按照式(7)計算得Gm1,b= 0 .064，Gm2,b= 0 .192。由此可見，雖然?m1＞?m2，但因Gm2,b＞Gm1,b，節點a應該優先選擇m2進行轉發。

圖1 節點轉發消息的實例

4 MIEBR設計

部分節點能量的過快消耗降低了網絡生命周期。在路由選擇時，結合消息重要性和節點能量因素設計路由策略，可均衡節點的能量消耗。結合消息緩存價值設計節點緩存替換策略，可高效利用緩存空間。本章首先設計能量均衡路由策略，然后設計緩存替換策略，最后給出相應的偽代碼并分析算法的開銷。

4.1 能量均衡路由策略

為了方便描述，記節點緩存中待轉發的消息集合為M= {m1,m2,… ,mu}，記M中目的節點地址集合為F= {f1,f2, … ,fd}，記當前時刻下的鄰居節點集合為V= {v1,v2,… ,vk}。下面描述能量均衡路由策略的具體步驟。

步驟1網絡初始化。當節點加入網絡時，將自己的社會上下文信息和地址進行廣播，并請求其他節點的社會上下文信息和地址。根據式(1)計算出節點與其他節點的社會關系強度，并存儲在緩存中。

步驟2節點a將F發送至{b|b∈V} 中的每個鄰居節點，并與鄰居節點相互發送消息匯總矢量SV(summary vector)。{b|b∈V} 中的每個鄰居節點將步驟1中計算得到的{R(b,f)|f∈F}，以及ηb發送給節點a。

步驟3節點a確定消息的轉發順序和下一跳節點。對于中的每一條消息，執行以下步驟。

① 在每個鄰居節點的消息匯總矢量SV中查找當前消息mi，記沒有當前消息mi的鄰居節點集為V0，對于 {b|b∈V0}中的每個鄰居節點，分別根據式(7)計算得到Gmi,b，取其中的最大值作為當前消息mi的轉發收益值Gm，即

若Gmi≤ 0 ，則不轉發該消息。② 取使Gmi達到最大值的鄰居節點作為當前消息mi的下一跳節點。因為使Gmi達到最大值的鄰居節點可能不止一個，因此記為節點集V*，即

步驟4節點a按照消息轉發收益值由大到小的順序依次向步驟 3中確定的下一跳節點轉發消息。若出現消息轉發收益值相同的情況，則依據消息在緩存中的起始地址由低位到高位的順序確定消息轉發的優先級。若下一跳節點為消息的目的節點，則下一跳節點在收到消息后以廣播的方式向網絡中發送接收確認ACK分組，網絡中各節點在收到接收確認ACK分組后在本地緩存中查找該消息，若緩存中存在該消息，則將該消息刪除。每條消息的轉發過程在消息傳輸完畢或傳輸鏈路中斷后結束。每條消息轉發過程結束后，消息轉發節點和接收節點分別按式(4)和式(5)更新節點的剩余能量信息。

步驟5節點a維護鄰居節點集V。節點a于每個周期T廣播Hello分組，Hello分組用來發現新的鄰居節點和確認鄰居節點是否離開通信范圍。鄰居節點若收到Hello分組，則向節點a回復Hello的ACK分組。若節點a發現新的鄰居節點，則將其加入V中。若節點a未收到鄰居節點回復的Hello的 ACK分組，則可認為該鄰居節點不在通信范圍內，將其從V中刪除。若鄰居節點集V有變動，則根據式(8)、式(9)更新緩存中消息轉發的順序和消息的下一跳節點。

下面結合具體的例子描述能量均衡路由策略的消息轉發過程。圖2中，節點a當前的鄰居節點為b和c，節點a緩存中有兩條消息m1和m2待轉發。對于消息m1，根據式(7)計算Gm1,b=0.1，Gm1,c= 0 .1，則根據式(8)知Gm1= 0 .1。對于消息m2，可得Gm2,b=0.02，Gm2,c= 0 .08，則Gm2= 0 .08。由Gm1＞Gm2可知，消息轉發順序為m1,m2。由式(9)可知，因為Gm1=Gm1,b=Gm1,c，則將m1轉發至節點b和c，因為Gm2=Gm2,c，則將m2轉發至節點c。

圖2 能量均衡路由策略消息轉發過程實例

4.2 緩存替換策略

節點b接收消息m前，比較m的大小sm與節點b的剩余緩存空間SL的大小。若sm≤SL，則節點b接收m；若sm＞SL，則節點b由于剩余空間不足不能直接接收m，但節點b可以將緩存價值較小的消息進行丟棄，滿足sm≤SL的條件后再接收m。由此，建立0-1背包問題模型。

其中，pm∈ { 0 ,1}，當m存入緩存中時，pm=1，否則，pm= 0 。

0-1背包問題是一個NP難題，可以使用動態規劃、記憶化搜索等算法求得該問題的精確解，但考慮到時間和空間復雜度，求精確解的方法是不實用的，本文采用修復法[22]求該問題的近似解。下面描述緩存替換策略的具體步驟。

1)D=?，D表示從A中刪除的元素集合。

2) 查找A中 ρm/sm最小的一條消息，記為mmin；若結果為空，則算法結束。

3)A=A {mmin}，D=D∪{mmin}。

4) 若SA＞S，則轉到步驟 2)；否則，說明緩存裝得下A中所有的消息，此時查看消息m在不在D中，若m∈D，則算法結束。若m?D，則執行C=CD，C=C∪{m} ，即刪除緩存中屬于D的消息，然后整理緩存空間，將緩存空間中的消息緊湊排列后，把m存入緩存中。

下面結合具體的例子描述緩存替換策略。圖3(a)描述了當前緩存的狀態，緩存中的消息為m1，m2和m3，此時m4待存入緩存，這4條消息按照 ρm/sm由大到小的排序依次為m1,m2,m4,m3。按照緩存替換策略，，此時并不真正從緩存中刪除m3，如圖3(b)所示。

此時比較SA和S的大小，分兩種情況分別討論。第一種情況為若SA＞S，則因為m4∈D，所以算法結束，緩存中不刪除任何消息。第二種情況為若SA≤S，因為m4?D，則刪除緩存中的m3，如圖3(c)所示，因為剩余緩存空間不連續，此時緩存還是存不下m4，必須對緩存消息進行整理，將消息緊湊排列后再存入m4，如圖3(d)所示。

圖3 緩存替換操作實例

4.3 算法偽代碼

根據以上的分析，MIEBR的思想可用如下偽代碼描述。

4.4 復雜度分析

MIEBR雖然提高了節點轉發消息的收益，均衡了節點的能量消耗，高效利用了節點的緩存空間，但也帶來了額外的開銷，一定程度上降低了消息的剩余生存時間。下面分析MIEBR的時間復雜度、空間復雜度和通信復雜度。

1) 時間復雜度

MIEBR在初始化時，需計算節點間的社會關系強度，設網絡中節點數為N，節點社會屬性數為l，計算兩節點間社會關系強度的時間復雜度為O(l)，每個節點需要計算與N-1個節點的社會關系強度，則時間復雜度為O(Nl)。在計算消息的轉發收益時，需要查詢k個鄰居節點的消息匯總矢量SV。因為消息匯總矢量SV的第x位用0或1代表該位置對應的消息分組在緩存中不存在或存在，所以，查詢一次消息匯總矢量SV的時間消耗僅為O(1)。緩存中共有u條消息，則計算節點緩存中所有消息的轉發收益的時間復雜度為O(uk)。節點按消息轉發收益大小確定消息轉發順序，排序算法采用歸并排序，時間復雜度為O(ul ogu)。緩存替換算法中的時間開銷主要用于遍歷A，時間復雜度為O(n)。

2) 空間復雜度

節點存儲自身的社會上下文信息需要的空間開銷為O(l)。網絡中的每個節點計算與其他節點的社會關系強度值后，需要存儲在緩存中，空間復雜度為O(N)。節點存儲k個鄰居節點發送的消息匯總矢量SV，設一個消息匯總矢量SV的長度為q，則空間復雜度為O(kq)。節點存儲消息的下一跳節點地址、消息重要性度量值和消息轉發收益值，需要空間為O(u)。采用歸并排序確定消息的轉發順序，輔助空間僅為O(1)。

3) 通信復雜度

通信復雜度是指MIEBR中傳輸控制消息的開銷，不包括傳輸數據消息的開銷。MIEBR傳輸控制消息的開銷主要來源于向鄰居節點發送的消息目的地址集F以及消息匯總矢量SV，則通信開銷為O(d+q)，以及鄰居節點返回的社會關系強度值和消息匯總矢量SV，也為O(d+q)。

5 仿真與分析

本文使用 ONE(opportunistic network environment)[23]對MIEBR進行仿真實驗，比較MIEBR與典型路由算法 Epidemic、PROPHET以及PROPICMAN的性能。為了更加真實的模擬現實生活中人們的移動規律，本文選擇芬蘭首都赫爾辛基地圖，采用Working Day Movement模型[24]進行仿真，仿真運行 10次后取平均值作為最終的結果。設置消息產生時的θ值在(0,1)上服從均勻分布。具體仿真參數設置如表3所示。

表3 仿真參數設置

5.1 能量均衡性能

本文用以下指標衡量算法的能量均衡性能。

1) 節點死亡收斂速率。用tα表示在死亡節點數量所占比率為α下的網絡運行時間。在一定的α下，tα越大，表示節點的平均生存時間越大。定義節點的死亡收斂速率為

設置網絡中節點數量為 260個，緩存大小為30 MB，網絡中死亡節點比率從0.1上升至0.5期間，每隔0.1的比率記錄不同算法的網絡運行時間。網絡運行時間從1 h到7 h，每隔1 h計算不同算法的節點剩余能量標準差。

由圖4可知，隨著死亡節點比率的增大，網絡運行時間都會有所增加，MIEBR的網絡運行時間最大，這是因為MIEBR控制了消息副本數量，傳輸消息次數較少，同時均衡了節點的能量消耗。MIEBR的網絡運行時間的增加最為緩慢。通過式(12)的計算，當死亡節點比率從0.1變化到0.5時，MIEBR、PROPICMAN、PROPHET以及Epidemic的φ值依次為 9 .3× 1 0-5、 2 .8× 1 0-5、 3 .0× 1 0-5和 3 .6× 1 0-5，表明MIEBR具有最快的節點死亡收斂速率，能量均衡性能最好。

圖4 不同死亡節點比率下的網絡運行時間

死亡節點比率從α變化到β時，φ越大，表示節點的死亡收斂速率越快，能量均衡性能越好。

2) 節點剩余能量標準差。節點剩余能量標準差體現了節點之間的剩余能量差異的大小，節點剩余能量標準差越小，表示能量均衡性能越好。節點剩余能量標準差為

由圖5可知，隨著網絡運行時間的增加，不同算法的節點剩余能量標準差都有所增加，MIEBR的節點剩余能量標準差最小，表明MIEBR的節點剩余能量分布相比之下更加均勻。這是因為MIEBR在路由的選擇時，結合了鄰居節點的剩余能量比率，避免了轉發能力較強節點能量的過快消耗而導致節點剩余能量差異過大的現象。

圖5 不同網絡運行時間下的節點剩余能量標準差

5.2 節點數量對算法性能的影響

節點數量的增加使節點間相遇次數增多。本節設置節點緩存空間為30 MB，隨著節點數量的增加，比較在不同的θ區間下 MIEBR的平均消息延時，比較MIEBR、PROPICMAN、PROPHET和Epidemic的消息投遞成功率、平均消息延時和網絡開銷比率。

圖6顯示的是MIEBR在不同的節點數量和不同的θ區間下的平均消息延時。從圖6中可知，不同θ區間的平均消息延時都隨著節點數量的增加而減小，θ值越大，則具有越低的平均消息延時。這是因為θ值越大，則消息重要性度量值就越大，在消息轉發和緩存替換中具有較高的優先級 。 θ ∈ ( 0.75,1)的 平 均 消 息 延 時 分 別 比平均降低了4%，9%和14%。

圖7顯示的是不同節點數量下的消息投遞成功率。從圖7中可知，MIEBR有著最高的消息投遞成功率，而Epidemic投遞成功率最低，并從節點數量為200以后開始下降。這是因為Epidemic的消息副本數最多，導致了緩存空間不足和能量的過快消耗，當網絡中較多的節點死亡后，投遞成功率將大幅下降。而MIEBR不但具有節點剩余能量均衡策略，還具有緩存消息替換策略，很好地解決了節點剩余能量不均衡和緩存空間利用不充分的問題。MIEBR的消息投遞成功率分別比 PROPICMAN、PROPHET和Epidemic平均提高了23%、31%和52%。

圖6 不同θ區間下的平均消息延時

圖7 不同節點數量下的消息投遞成功率

圖 8顯示的是不同節點數量下的平均消息延時。從圖 8中可知，MIEBR、PROPICMAN和PROPHET的平均消息延時都隨著節點數量的增加而快速下降。Epidemic的平均消息延時最高，并且先下降后增加。這是因為隨著節點數量的上升，節點相遇次數的增加導致了傳輸次數增多，使節點能量消耗過快，節點的過快死亡導致了平均消息延時的上升。同時，Epidemic大量的消息副本造成了緩存空間不足，影響了消息的接收和轉發。MIEBR的平均消息延時最低，且與PROPICMAN較為接近。MIEBR的平均消息延時分別比PROPICMAN、PROPHET和 Epidemic平均降低了2%、8%和19%。

圖8 不同節點數量下的平均消息延時

圖 9顯示的是不同節點數量下的網絡開銷比率。從圖9中可知，網絡開銷比率都隨著節點數量的增加而上升。Epidemic的網絡開銷比率最高，而且上升趨勢最明顯。這是因為Epidemic沒有控制消息副本的數量。MIEBR和PROPICMAN的網絡開銷比率相差不大，并且都比 PROPHET的要小。這是由于這兩種算法只選擇最佳的鄰居節點轉發數據，有效控制了網絡開銷。MIEBR的網絡開銷比率分別比Epidemic和PROPHET平均降低了70%和36%。

圖9 不同節點數量下的網絡開銷比率

5.3 緩存空間對算法性能的影響

節點緩存空間的大小是影響算法性能的一個重要的因素。緩存空間越大，則節點可存儲轉發的消息越多。本節設置節點數量為280個，研究緩存空間的變化對算法性能的影響。

圖 10描述了不同緩存空間下的消息投遞成功率。從圖10中可知，4種算法的消息投遞成功率都隨著緩存空間的增加而上升。MIEBR具有最高的消息投遞成功率。

圖10 不同緩存空間下的消息投遞成功率

圖11描述了不同緩存空間下的平均消息延時。從圖 11中可看出，平均消息延時隨緩存空間的增加而下降，Epidemic具有最高的平均消息延時，且下降趨勢最為明顯。MIEBR具有最低的平均消息延時，且變化較為平緩。

圖11 不同緩存空間下的平均消息延時

圖12描述了不同緩存空間下的網絡開銷比率。隨著緩存空間的增加，4種算法的網絡開銷比率都不斷下降。Epidemic的網絡開銷比率下降趨勢最為明顯，MIEBR和PROPICMAN的網絡開銷比率基本相同且下降趨勢較為平緩。

由以上結果可知，節點緩存大小一定程度上影響了算法的性能。在相同的網絡環境下，緩存空間越大，則節點可攜帶的消息越多，當遇到其他節點時，轉發的消息量也就越多，因此，消息投遞成功率越高，平均消息延時越低。在數據轉發的過程中，若鄰居節點緩存不足，PROPICMAN、PROPHET和Epidemic只能等待該鄰居節點因緩存中消息的TTL值減為0被刪除或該鄰居節點收到目的節點接收確認的ACK釋放出緩存空間后，繼續進行數據傳輸。因此，未采用緩存替換策略的PROPHET、PROPICMAN和Epidemic算法性能受緩存空間因素影響較大。而 MIEBR由于采用了緩存替換策略，使該算法在緩存空間不足時仍具有較好的性能。

圖12 不同緩存空間下的網絡開銷比率

6 結束語

本文提出的 MIEBR通過引入節點用戶對消息內容重要程度的設定，提出了消息重要性的度量方法；依據消息的緩存價值，設計了緩存替換策略；根據節點轉發消息的收益，設計了能量均衡路由策略。MIEBR提高了節點轉發消息的收益和緩存利用率。實驗結果表明，在緩存空間和能量受限的機會網絡中，MIEBR均衡了節點的能量消耗，降低了重要消息的傳輸延時，提高了消息投遞成功率，并具有較低的平均消息延時和網絡開銷。下一步的工作是設計安全機制和信用機制，保證節點用戶社會上下文隱私安全和促進節點用戶之間的合作。