基于消息重要性的機(jī)會(huì)網(wǎng)絡(luò)能量均衡路由算法

陳志剛，殷濱安，吳嘉

（1. 中南大學(xué)軟件學(xué)院，湖南 長沙 410075；2.“移動(dòng)醫(yī)療”教育部—中國移動(dòng)聯(lián)合實(shí)驗(yàn)室，湖南 長沙 410083）

1 引言

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

機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)往往是手持或車載設(shè)備[10-11]，因此，節(jié)點(diǎn)間的數(shù)據(jù)傳輸是不穩(wěn)定的，節(jié)點(diǎn)可能在數(shù)據(jù)傳輸完成前離開通信范圍，導(dǎo)致一部分消息未能發(fā)送給對方。因此，在節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)傳輸?shù)倪^程中，應(yīng)該充分利用節(jié)點(diǎn)相遇的機(jī)會(huì)，優(yōu)先傳輸重要性較高的消息。在機(jī)會(huì)網(wǎng)絡(luò)的實(shí)際應(yīng)用中，往往有一些消息是比較緊急、比較重要的。比如，在CarTel系統(tǒng)中，車輛故障信息要比路況信息更為重要，服務(wù)器只有收到車輛故障信息后才能采取緊急救援等措施。在手持設(shè)備交換網(wǎng)中，用戶根據(jù)消息內(nèi)容的重要程度不同，往往希望重要性較高的消息得到優(yōu)先傳輸。

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

2 相關(guān)工作

目前的機(jī)會(huì)網(wǎng)絡(luò)路由算法分為零信息型和信息輔助型兩大類[14]。零信息型路由算法是指在數(shù)據(jù)轉(zhuǎn)發(fā)過程中不需要額外的信息作為輔助。典型的零信息型路由算法有 Direct Delivery[15]、Epidemic[16]和Spray and Wait[17]等。

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

由于零信息型算法沒有考慮到實(shí)際應(yīng)用中節(jié)點(diǎn)、數(shù)據(jù)及網(wǎng)絡(luò)拓?fù)涞奶卣?，使該類算法往往在投遞成功率、網(wǎng)絡(luò)開銷、傳輸延時(shí)等3個(gè)方面達(dá)不到理想平衡。而信息輔助型路由算法則是結(jié)合節(jié)點(diǎn)的接觸歷史、剩余能量、移動(dòng)速度、鄰居變化和社會(huì)關(guān)系等信息提出的算法。典型的信息輔助型算法有PROPHET[18]、PROPICMAN[19]和Bubble Rap[20]等。

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

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

Bubble Rap算法通過對節(jié)點(diǎn)進(jìn)行聚類，并計(jì)算節(jié)點(diǎn)的全局和局部中心度。在轉(zhuǎn)發(fā)過程中，若消息沒有進(jìn)入目的節(jié)點(diǎn)所在的社區(qū)，則將消息發(fā)送給全局中心度高的節(jié)點(diǎn)。若消息進(jìn)入了目的節(jié)點(diǎn)所在的社區(qū)，則將消息發(fā)送給該社區(qū)局部中心度高的節(jié)點(diǎn)。該算法太過于依賴中心度高的節(jié)點(diǎn)，造成中心度高的節(jié)點(diǎn)繁忙，中心度低的節(jié)點(diǎn)空閑，從而使網(wǎng)絡(luò)負(fù)載不均衡。

文獻(xiàn)[21]提出了 TBR算法，該算法結(jié)合數(shù)據(jù)分組的TTL值、跳數(shù)和數(shù)據(jù)分組大小確定消息的優(yōu)先級，優(yōu)先向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)優(yōu)先級高的消息。該算法減小了具有較高優(yōu)先級消息的傳輸延時(shí)。但是，該算法在確定消息優(yōu)先級時(shí)，未考慮到消息內(nèi)容的重要程度。

3 模型設(shè)計(jì)

本文使用到的數(shù)學(xué)符號(hào)說明如表1所示。

表1 符號(hào)說明

3.1 節(jié)點(diǎn)的社會(huì)屬性

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

表2 社會(huì)屬性信息

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

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

定義節(jié)點(diǎn)a與節(jié)點(diǎn)b的社會(huì)關(guān)系強(qiáng)度為

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

3.2 消息重要性的度量

消息的重要性由兩方面共同決定：1) 消息內(nèi)容的重要程度，由消息發(fā)送方?jīng)Q定；2) 由消息的TTL值、跳數(shù)和大小決定。由此，定義消息m的重要性度量值為

其中，θm表示消息發(fā)送方根據(jù)m的內(nèi)容重要程度而設(shè)定的值， θm∈(0,1)，θm越大表示m的內(nèi)容越重要。TTLm為m的剩余生存時(shí)間。需要注意的是，不同于TCP/IP協(xié)議中的TTL，TCP/IP協(xié)議中的TTL表示的是消息可轉(zhuǎn)發(fā)的最大跳數(shù)，機(jī)會(huì)網(wǎng)絡(luò)中的TTL表示的是消息的剩余生存時(shí)間。TTL值越小，表明消息離被刪除的時(shí)間越近，越需要被優(yōu)先轉(zhuǎn)發(fā)。hm為m的跳數(shù)，hm越小，表明該消息被轉(zhuǎn)發(fā)的次數(shù)越少，越需要盡快轉(zhuǎn)發(fā)。sm為m的大小，sm越小，則m中每比特的消息重要程度越大。

3.3 消息的緩存價(jià)值

機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)緩存空間是有限的，當(dāng)傳輸過程中接收方緩存不足時(shí)，需要?jiǎng)h除緩存中的部分消息，從而保證節(jié)點(diǎn)具有足夠的緩存空間接收數(shù)據(jù)。從緩存中刪除的消息，應(yīng)該具有最低的緩存價(jià)值。

定義消息的緩存價(jià)值為

其中，TTLm越小，消息m被轉(zhuǎn)發(fā)過的概率越大。反之，TTLm越大，表明消息m被轉(zhuǎn)發(fā)的概率越小，則消息m越需要被優(yōu)先保留。特別地，當(dāng)TTLm減為0，說明該消息已超過其時(shí)效期限，緩存價(jià)值為0。mθ越大，即消息m的內(nèi)容越重要，緩存該消息的價(jià)值也就越大。

3.4 能量消耗模型

機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)往往是移動(dòng)設(shè)備，這些節(jié)點(diǎn)的能量是有限的。因此，必須考慮節(jié)點(diǎn)能量對消息轉(zhuǎn)發(fā)的影響。

一個(gè)數(shù)據(jù)分組在由節(jié)點(diǎn)a轉(zhuǎn)發(fā)至節(jié)點(diǎn)b的過程中的能量消耗，主要包括節(jié)點(diǎn)a轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)分組所消耗的能量ES，以及節(jié)點(diǎn)b接收一個(gè)數(shù)據(jù)分組所消耗的能量ER和返回ACK給節(jié)點(diǎn)a所消耗的能量EACK。由此，建立節(jié)點(diǎn)的剩余能量模型。

設(shè)消息m的字節(jié)數(shù)為Bm，一個(gè)數(shù)據(jù)分組的字節(jié)數(shù)為Bpkt，則節(jié)點(diǎn)a轉(zhuǎn)發(fā)m后的剩余能量為

節(jié)點(diǎn)b接收m后的剩余能量為

其中，Er(old),a表示節(jié)點(diǎn)a轉(zhuǎn)發(fā)m前的剩余能量，Er(old),b表示節(jié)點(diǎn)b接收m前的剩余能量。

定義節(jié)點(diǎn)a的剩余能量百分比為

其中，Emax為節(jié)點(diǎn)的最大能量值。

本文關(guān)注的是節(jié)點(diǎn)在傳輸消息的過程中的能量消耗，不考慮節(jié)點(diǎn)能量衰減等其他因素。

3.5 節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的收益

節(jié)點(diǎn)a在轉(zhuǎn)發(fā)消息m至節(jié)點(diǎn)b時(shí)，若節(jié)點(diǎn)b是消息m的目的節(jié)點(diǎn)，則節(jié)點(diǎn)a轉(zhuǎn)發(fā)消息m的收益只由消息m的重要性度量值?m決定。

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

由此，定義消息m由節(jié)點(diǎn)a轉(zhuǎn)發(fā)至節(jié)點(diǎn)b的收益為

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

圖1給出了節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的實(shí)例。節(jié)點(diǎn)a有兩條消息需要轉(zhuǎn)發(fā)給節(jié)點(diǎn)b，節(jié)點(diǎn)b不是這兩條消息的目的節(jié)點(diǎn)。設(shè) ηb=0.8，按照式(7)計(jì)算得Gm1,b= 0 .064，Gm2,b= 0 .192。由此可見，雖然?m1＞?m2，但因Gm2,b＞Gm1,b，節(jié)點(diǎn)a應(yīng)該優(yōu)先選擇m2進(jìn)行轉(zhuǎn)發(fā)。

圖1 節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的實(shí)例

4 MIEBR設(shè)計(jì)

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

4.1 能量均衡路由策略

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

步驟1網(wǎng)絡(luò)初始化。當(dāng)節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)，將自己的社會(huì)上下文信息和地址進(jìn)行廣播，并請求其他節(jié)點(diǎn)的社會(huì)上下文信息和地址。根據(jù)式(1)計(jì)算出節(jié)點(diǎn)與其他節(jié)點(diǎn)的社會(huì)關(guān)系強(qiáng)度，并存儲(chǔ)在緩存中。

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

步驟3節(jié)點(diǎn)a確定消息的轉(zhuǎn)發(fā)順序和下一跳節(jié)點(diǎn)。對于中的每一條消息，執(zhí)行以下步驟。

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

若Gmi≤ 0 ，則不轉(zhuǎn)發(fā)該消息。② 取使Gmi達(dá)到最大值的鄰居節(jié)點(diǎn)作為當(dāng)前消息mi的下一跳節(jié)點(diǎn)。因?yàn)槭笹mi達(dá)到最大值的鄰居節(jié)點(diǎn)可能不止一個(gè)，因此記為節(jié)點(diǎn)集V*，即

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

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

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

圖2 能量均衡路由策略消息轉(zhuǎn)發(fā)過程實(shí)例

4.2 緩存替換策略

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

其中，pm∈ { 0 ,1}，當(dāng)m存入緩存中時(shí)，pm=1，否則，pm= 0 。

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

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

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

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

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

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

此時(shí)比較SA和S的大小，分兩種情況分別討論。第一種情況為若SA＞S，則因?yàn)閙4∈D，所以算法結(jié)束，緩存中不刪除任何消息。第二種情況為若SA≤S，因?yàn)閙4?D，則刪除緩存中的m3，如圖3(c)所示，因?yàn)槭Ｓ嗑彺婵臻g不連續(xù)，此時(shí)緩存還是存不下m4，必須對緩存消息進(jìn)行整理，將消息緊湊排列后再存入m4，如圖3(d)所示。

圖3 緩存替換操作實(shí)例

4.3 算法偽代碼

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

4.4 復(fù)雜度分析

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

1) 時(shí)間復(fù)雜度

MIEBR在初始化時(shí)，需計(jì)算節(jié)點(diǎn)間的社會(huì)關(guān)系強(qiáng)度，設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為N，節(jié)點(diǎn)社會(huì)屬性數(shù)為l，計(jì)算兩節(jié)點(diǎn)間社會(huì)關(guān)系強(qiáng)度的時(shí)間復(fù)雜度為O(l)，每個(gè)節(jié)點(diǎn)需要計(jì)算與N-1個(gè)節(jié)點(diǎn)的社會(huì)關(guān)系強(qiáng)度，則時(shí)間復(fù)雜度為O(Nl)。在計(jì)算消息的轉(zhuǎn)發(fā)收益時(shí)，需要查詢k個(gè)鄰居節(jié)點(diǎn)的消息匯總矢量SV。因?yàn)橄R總矢量SV的第x位用0或1代表該位置對應(yīng)的消息分組在緩存中不存在或存在，所以，查詢一次消息匯總矢量SV的時(shí)間消耗僅為O(1)。緩存中共有u條消息，則計(jì)算節(jié)點(diǎn)緩存中所有消息的轉(zhuǎn)發(fā)收益的時(shí)間復(fù)雜度為O(uk)。節(jié)點(diǎn)按消息轉(zhuǎn)發(fā)收益大小確定消息轉(zhuǎn)發(fā)順序，排序算法采用歸并排序，時(shí)間復(fù)雜度為O(ul ogu)。緩存替換算法中的時(shí)間開銷主要用于遍歷A，時(shí)間復(fù)雜度為O(n)。

2) 空間復(fù)雜度

節(jié)點(diǎn)存儲(chǔ)自身的社會(huì)上下文信息需要的空間開銷為O(l)。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)計(jì)算與其他節(jié)點(diǎn)的社會(huì)關(guān)系強(qiáng)度值后，需要存儲(chǔ)在緩存中，空間復(fù)雜度為O(N)。節(jié)點(diǎn)存儲(chǔ)k個(gè)鄰居節(jié)點(diǎn)發(fā)送的消息匯總矢量SV，設(shè)一個(gè)消息匯總矢量SV的長度為q，則空間復(fù)雜度為O(kq)。節(jié)點(diǎn)存儲(chǔ)消息的下一跳節(jié)點(diǎn)地址、消息重要性度量值和消息轉(zhuǎn)發(fā)收益值，需要空間為O(u)。采用歸并排序確定消息的轉(zhuǎn)發(fā)順序，輔助空間僅為O(1)。

3) 通信復(fù)雜度

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

5 仿真與分析

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

表3 仿真參數(shù)設(shè)置

5.1 能量均衡性能

本文用以下指標(biāo)衡量算法的能量均衡性能。

1) 節(jié)點(diǎn)死亡收斂速率。用tα表示在死亡節(jié)點(diǎn)數(shù)量所占比率為α下的網(wǎng)絡(luò)運(yùn)行時(shí)間。在一定的α下，tα越大，表示節(jié)點(diǎn)的平均生存時(shí)間越大。定義節(jié)點(diǎn)的死亡收斂速率為

設(shè)置網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量為 260個(gè)，緩存大小為30 MB，網(wǎng)絡(luò)中死亡節(jié)點(diǎn)比率從0.1上升至0.5期間，每隔0.1的比率記錄不同算法的網(wǎng)絡(luò)運(yùn)行時(shí)間。網(wǎng)絡(luò)運(yùn)行時(shí)間從1 h到7 h，每隔1 h計(jì)算不同算法的節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差。

由圖4可知，隨著死亡節(jié)點(diǎn)比率的增大，網(wǎng)絡(luò)運(yùn)行時(shí)間都會(huì)有所增加，MIEBR的網(wǎng)絡(luò)運(yùn)行時(shí)間最大，這是因?yàn)镸IEBR控制了消息副本數(shù)量，傳輸消息次數(shù)較少，同時(shí)均衡了節(jié)點(diǎn)的能量消耗。MIEBR的網(wǎng)絡(luò)運(yùn)行時(shí)間的增加最為緩慢。通過式(12)的計(jì)算，當(dāng)死亡節(jié)點(diǎn)比率從0.1變化到0.5時(shí)，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具有最快的節(jié)點(diǎn)死亡收斂速率，能量均衡性能最好。

圖4 不同死亡節(jié)點(diǎn)比率下的網(wǎng)絡(luò)運(yùn)行時(shí)間

死亡節(jié)點(diǎn)比率從α變化到β時(shí)，φ越大，表示節(jié)點(diǎn)的死亡收斂速率越快，能量均衡性能越好。

2) 節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差。節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差體現(xiàn)了節(jié)點(diǎn)之間的剩余能量差異的大小，節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差越小，表示能量均衡性能越好。節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差為

由圖5可知，隨著網(wǎng)絡(luò)運(yùn)行時(shí)間的增加，不同算法的節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差都有所增加，MIEBR的節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差最小，表明MIEBR的節(jié)點(diǎn)剩余能量分布相比之下更加均勻。這是因?yàn)镸IEBR在路由的選擇時(shí)，結(jié)合了鄰居節(jié)點(diǎn)的剩余能量比率，避免了轉(zhuǎn)發(fā)能力較強(qiáng)節(jié)點(diǎn)能量的過快消耗而導(dǎo)致節(jié)點(diǎn)剩余能量差異過大的現(xiàn)象。

圖5 不同網(wǎng)絡(luò)運(yùn)行時(shí)間下的節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差

5.2 節(jié)點(diǎn)數(shù)量對算法性能的影響

節(jié)點(diǎn)數(shù)量的增加使節(jié)點(diǎn)間相遇次數(shù)增多。本節(jié)設(shè)置節(jié)點(diǎn)緩存空間為30 MB，隨著節(jié)點(diǎn)數(shù)量的增加，比較在不同的θ區(qū)間下 MIEBR的平均消息延時(shí)，比較MIEBR、PROPICMAN、PROPHET和Epidemic的消息投遞成功率、平均消息延時(shí)和網(wǎng)絡(luò)開銷比率。

圖6顯示的是MIEBR在不同的節(jié)點(diǎn)數(shù)量和不同的θ區(qū)間下的平均消息延時(shí)。從圖6中可知，不同θ區(qū)間的平均消息延時(shí)都隨著節(jié)點(diǎn)數(shù)量的增加而減小，θ值越大，則具有越低的平均消息延時(shí)。這是因?yàn)棣戎翟酱?，則消息重要性度量值就越大，在消息轉(zhuǎn)發(fā)和緩存替換中具有較高的優(yōu)先級 。 θ ∈ ( 0.75,1)的 平 均 消 息 延 時(shí) 分 別 比平均降低了4%，9%和14%。

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

圖6 不同θ區(qū)間下的平均消息延時(shí)

圖7 不同節(jié)點(diǎn)數(shù)量下的消息投遞成功率

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

圖8 不同節(jié)點(diǎn)數(shù)量下的平均消息延時(shí)

圖 9顯示的是不同節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)開銷比率。從圖9中可知，網(wǎng)絡(luò)開銷比率都隨著節(jié)點(diǎn)數(shù)量的增加而上升。Epidemic的網(wǎng)絡(luò)開銷比率最高，而且上升趨勢最明顯。這是因?yàn)镋pidemic沒有控制消息副本的數(shù)量。MIEBR和PROPICMAN的網(wǎng)絡(luò)開銷比率相差不大，并且都比 PROPHET的要小。這是由于這兩種算法只選擇最佳的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，有效控制了網(wǎng)絡(luò)開銷。MIEBR的網(wǎng)絡(luò)開銷比率分別比Epidemic和PROPHET平均降低了70%和36%。

圖9 不同節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)開銷比率

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

節(jié)點(diǎn)緩存空間的大小是影響算法性能的一個(gè)重要的因素。緩存空間越大，則節(jié)點(diǎn)可存儲(chǔ)轉(zhuǎn)發(fā)的消息越多。本節(jié)設(shè)置節(jié)點(diǎn)數(shù)量為280個(gè)，研究緩存空間的變化對算法性能的影響。

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

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

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

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

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

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

圖12 不同緩存空間下的網(wǎng)絡(luò)開銷比率

6 結(jié)束語

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