基于節(jié)點(diǎn)屬性的機(jī)會(huì)網(wǎng)絡(luò)節(jié)能路由算法

鄭永剛 孫文勝

(杭州電子科技大學(xué)通信工程學(xué)院 浙江 杭州 310018)

0 引 言

隨著智能移動(dòng)終端的普及和短距離無線通信技術(shù)的飛速發(fā)展，機(jī)會(huì)網(wǎng)絡(luò)這種新形式的網(wǎng)絡(luò)在過去幾年得到迅速發(fā)展。由于這種網(wǎng)絡(luò)的間歇性連接，源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間很少存在端到端的路徑[1]。在延遲容忍網(wǎng)絡(luò)和機(jī)會(huì)網(wǎng)絡(luò)中，為了解決節(jié)點(diǎn)移動(dòng)帶來的鏈路間歇性連接問題，基于存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)的數(shù)據(jù)傳輸模式引起研究者的關(guān)注。

由于機(jī)會(huì)網(wǎng)絡(luò)的載體往往為微型嵌入式移動(dòng)設(shè)備，因此節(jié)點(diǎn)的資源是有限的。資源有限主要分為兩個(gè)方面：一是節(jié)點(diǎn)的緩存空間是有限的。雖然目前存儲(chǔ)技術(shù)得到迅速發(fā)展，移動(dòng)節(jié)點(diǎn)的緩存空間也得到較大的提升，但是如果毫無節(jié)制地轉(zhuǎn)發(fā)、復(fù)制、攜帶消息，緩存終將會(huì)耗盡，對(duì)節(jié)點(diǎn)自身也會(huì)帶來較大的負(fù)擔(dān)。二是節(jié)點(diǎn)攜帶的能量是有限的。由于移動(dòng)節(jié)點(diǎn)一般采用電池來維持其通信所需的能量，再加上節(jié)點(diǎn)本身體積的限制，無法儲(chǔ)蓄太多電量。就機(jī)會(huì)網(wǎng)絡(luò)的實(shí)際應(yīng)用場景而言，節(jié)點(diǎn)通常會(huì)被放在人煙稀少或者條件惡劣甚至危險(xiǎn)的環(huán)境中，不易于更換電池或者進(jìn)行能量的補(bǔ)給。如果某些節(jié)點(diǎn)的能量或者緩存耗盡，整個(gè)網(wǎng)絡(luò)的性能會(huì)因?yàn)檫@些節(jié)點(diǎn)無法轉(zhuǎn)發(fā)消息而迅速下降，最終使得網(wǎng)絡(luò)不能保證預(yù)期的服務(wù)質(zhì)量[2]。

因此，在機(jī)會(huì)網(wǎng)絡(luò)當(dāng)中如何以有限的能量完成消息的高效傳輸，達(dá)到低時(shí)延、高傳遞成功率、低功耗等效果，成為當(dāng)前研究需要迫切解決的問題之一。

1 相關(guān)工作

為了應(yīng)對(duì)機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)資源過快耗盡的問題。研究者們提出了許多高效節(jié)能的路由算法。通過控制網(wǎng)絡(luò)中消息副本數(shù)量能夠有效地緩解緩存不足的問題。文獻(xiàn)[3]提出了一種基于節(jié)點(diǎn)質(zhì)量度的Spray and Focus改進(jìn)路由算法，該算法分為Spray和Focus兩個(gè)階段。在Spray階段時(shí)算法首先通過一個(gè)參數(shù)L限制網(wǎng)絡(luò)中消息的最大副本數(shù)，接著提取節(jié)點(diǎn)屬性值，計(jì)算每個(gè)節(jié)點(diǎn)的質(zhì)量度，并將消息轉(zhuǎn)發(fā)給質(zhì)量度高的節(jié)點(diǎn)，然后進(jìn)入Focus階段。在這個(gè)階段中，攜帶消息副本的節(jié)點(diǎn)只有在遇到目的節(jié)點(diǎn)時(shí)才會(huì)進(jìn)行消息傳輸。整個(gè)過程網(wǎng)絡(luò)中消息副本的數(shù)量是固定的，因此可以緩解節(jié)點(diǎn)緩存不足的壓力。

對(duì)于節(jié)點(diǎn)能量有限的問題，文獻(xiàn)[4]提出了一種基于接觸概率的低時(shí)延休眠算法。該算法通過預(yù)測節(jié)點(diǎn)之間的接觸概率來動(dòng)態(tài)地調(diào)整休眠時(shí)間，確保節(jié)點(diǎn)間在喚醒狀態(tài)下有更多接觸機(jī)會(huì)，在休眠節(jié)能的同時(shí)不降低網(wǎng)絡(luò)的性能。

以攜帶智能無線設(shè)備的人類作為節(jié)點(diǎn)載體的網(wǎng)絡(luò)是機(jī)會(huì)網(wǎng)絡(luò)應(yīng)用的重要領(lǐng)域之一。而人類的活動(dòng)一般具有社區(qū)性、中心性、相似性等特點(diǎn)，這些特性都會(huì)影響節(jié)點(diǎn)消息的傳遞成功概率和節(jié)點(diǎn)能量的消耗。研究者提出了許多基于節(jié)點(diǎn)社會(huì)屬性的路由算法。在文獻(xiàn)[5]中，作者提出的Bubble Rap算法充分考慮了節(jié)點(diǎn)的社會(huì)屬性，引入節(jié)點(diǎn)全局中心度和局部中心度兩個(gè)特性，決定消息的下一個(gè)傳輸節(jié)點(diǎn)。該算法使網(wǎng)絡(luò)性能得到了較好的提升，但由于在選擇中繼節(jié)點(diǎn)時(shí)沒有考慮節(jié)點(diǎn)剩余能量和可用緩存等自身屬性，頻繁接收或轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)將迅速耗盡能量和緩存空間而“死亡”。這可能導(dǎo)致消息傳輸失敗，進(jìn)而使得機(jī)會(huì)網(wǎng)絡(luò)的性能迅速下降。

為了解決上述問題，本文提出了一種更為實(shí)用的路由算法，稱為EABNA。該算法在選擇中繼節(jié)點(diǎn)時(shí)，充分考慮了節(jié)點(diǎn)本身的社會(huì)屬性，及剩余能量和緩存空間的動(dòng)態(tài)變化情況。由于選擇中繼節(jié)點(diǎn)時(shí)考慮到能量和緩存等因素，該路由算法實(shí)現(xiàn)了在降低消息時(shí)延和提高消息傳遞成功率的同時(shí)延長了節(jié)點(diǎn)在網(wǎng)絡(luò)中的生命周期。

2 網(wǎng)絡(luò)模型和節(jié)點(diǎn)屬性

2.1 網(wǎng)絡(luò)模型

將機(jī)會(huì)網(wǎng)絡(luò)抽象為對(duì)稱加權(quán)圖G(V,E)，V是節(jié)點(diǎn)集合，V={V1,V2,…，VN},N≥1，N是網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。E表示邊的集合，E={e12,e13，…，eij,…},i≠j，1≤i,j≤N，而eij表示節(jié)點(diǎn)i和j之間的權(quán)重。機(jī)會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的模型圖如圖1所示。該模型一共有五個(gè)節(jié)點(diǎn)，分別是1、2、3、4、5。每對(duì)節(jié)點(diǎn)之間的連線表示它們之間至少有一次物理接觸，連線上值表示兩個(gè)通信節(jié)點(diǎn)之間的權(quán)重。

圖1 機(jī)會(huì)網(wǎng)絡(luò)結(jié)構(gòu)模型

在機(jī)會(huì)網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)可以移動(dòng)，邊的權(quán)重eij被定義為節(jié)點(diǎn)i與節(jié)點(diǎn)j接觸的緊密程度，即到目前為止這兩節(jié)點(diǎn)之間的接觸次數(shù)在所有節(jié)點(diǎn)接觸次數(shù)中所占的比重。

2.2 節(jié)點(diǎn)屬性

在機(jī)會(huì)網(wǎng)絡(luò)中，哪個(gè)節(jié)點(diǎn)可以被選為最佳的中繼節(jié)點(diǎn)，何時(shí)以及如何傳遞消息是需要考慮的問題。為了解決這些問題，可以從網(wǎng)絡(luò)節(jié)點(diǎn)中提取一些屬性，并設(shè)計(jì)適當(dāng)?shù)霓D(zhuǎn)發(fā)策略。社會(huì)屬性，如社區(qū)和中心地位相對(duì)穩(wěn)定的節(jié)點(diǎn)，可以作為路由決策設(shè)計(jì)的基礎(chǔ)[6]；節(jié)點(diǎn)本身的屬性，例如能量和緩存空間是時(shí)變的，這些也是路由選擇的重要因素。以下是機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的幾個(gè)重要屬性的定義，可以根據(jù)這些屬性設(shè)計(jì)路由算法。

2.2.1 社 區(qū)

在實(shí)際應(yīng)用中，構(gòu)成機(jī)會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)通常是一些被人類攜帶的智能移動(dòng)設(shè)備，而由于興趣、工作和一些其他方面的原因，大多數(shù)人的活動(dòng)僅限于某一區(qū)域。整個(gè)網(wǎng)絡(luò)可以被劃分為若干個(gè)不同的社區(qū)，與社區(qū)之間的節(jié)點(diǎn)相比，社區(qū)內(nèi)部節(jié)點(diǎn)間的連接更為緊密，擁有更高的消息傳遞成功概率以及更低的消息時(shí)延。通過分析節(jié)點(diǎn)的移動(dòng)數(shù)據(jù)并提取其社區(qū)屬性，可以設(shè)計(jì)出更優(yōu)的路由算法。

2.2.2 節(jié)點(diǎn)的中心性

中心性[8]反映了機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的社會(huì)狀態(tài)。如果一個(gè)節(jié)點(diǎn)具有較強(qiáng)的中心性，則代表著它有更多的機(jī)會(huì)遇到其他節(jié)點(diǎn)，因此比較適合作為消息轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)。

本文中，使用中心度表示節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的關(guān)聯(lián)程度。在具有n個(gè)節(jié)點(diǎn)的無向圖中，一個(gè)節(jié)點(diǎn)的中心度指的是與該節(jié)點(diǎn)有直接接觸的相鄰節(jié)點(diǎn)的總數(shù)。通過歸一化消除節(jié)點(diǎn)之間的差異?？梢缘玫焦?jié)點(diǎn)的中心性表達(dá)式如下：

(1)

式中：xij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間是否存在直接接觸，如果它們之間存在直接接觸，則xij為1，否則為0。

由于節(jié)點(diǎn)具有社區(qū)屬性，根據(jù)節(jié)點(diǎn)是否處于社區(qū)當(dāng)中，可以將節(jié)點(diǎn)的中心性劃分為針對(duì)社區(qū)的局部中心和針對(duì)整個(gè)網(wǎng)絡(luò)的全局中心。相應(yīng)地，當(dāng)計(jì)算節(jié)點(diǎn)的全局中心度時(shí)，n指整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量；當(dāng)計(jì)算局部中心度時(shí)，n指當(dāng)前社區(qū)的節(jié)點(diǎn)數(shù)量。

2.2.3 剩余能量

在實(shí)際應(yīng)用環(huán)境中，任何節(jié)點(diǎn)的能量都是有限的，一旦節(jié)點(diǎn)的能量耗盡，將無法繼續(xù)工作。因此，設(shè)計(jì)路由策略時(shí)，能量也是一個(gè)需要關(guān)注的要素。假設(shè)節(jié)點(diǎn)的初始能量為Einit，能量消耗主要集中在消息轉(zhuǎn)發(fā)或接收、探測掃描周圍節(jié)點(diǎn)、響應(yīng)周圍節(jié)點(diǎn)掃描等方面。

假設(shè)節(jié)點(diǎn)待機(jī)狀態(tài)下的功耗為Ps，能量更新的周期為Tr；接收或發(fā)送一次消息時(shí)的能耗都為Et，Tr時(shí)間內(nèi)發(fā)送和接收消息的次數(shù)為Nt；掃描一次周圍節(jié)點(diǎn)的能耗為Es，Tr時(shí)間內(nèi)掃描的次數(shù)為Ns；響應(yīng)一次掃描的能耗為Er，Tr時(shí)間內(nèi)響應(yīng)掃描的次數(shù)為Nr。因此，根據(jù)上述條件能夠得出節(jié)點(diǎn)的剩余能量。剩余能量可以表示為[9]:

Enew=Eold-Et×Nt-Es×Ns-Ps×Tr

(2)

在初始階段Eold=Einit，當(dāng)在仿真過程中更新能量時(shí)將最后剩余能量值設(shè)置為Eold。

2.2.4 剩余緩存空間

在實(shí)際環(huán)境中，節(jié)點(diǎn)的緩存空間也是有限的。節(jié)點(diǎn)攜帶或者轉(zhuǎn)發(fā)消息都需要一定的緩存空間，一旦節(jié)點(diǎn)的緩存空間耗盡，在接收到新消息時(shí)就可能將有用的消息丟棄，導(dǎo)致網(wǎng)絡(luò)的性能下降[10]。因此在指定下一跳節(jié)點(diǎn)時(shí)，需要考慮節(jié)點(diǎn)的剩余緩存空間。假設(shè)每個(gè)節(jié)點(diǎn)的初始緩存空間相同并且都為Binit，每個(gè)消息的大小為Bp，節(jié)點(diǎn)中當(dāng)前攜帶的消息數(shù)量為Cn。因此，可以根據(jù)節(jié)點(diǎn)中攜帶的消息的數(shù)量來計(jì)算剩余緩存。節(jié)點(diǎn)的剩余緩存可以表示為：

Bres=Binit-Bp×Cn

(3)

仿真過程中在更新節(jié)點(diǎn)剩余能量的同時(shí)需要更新其剩余緩存空間的值。

3 EABNA算法設(shè)計(jì)

3.1 消息轉(zhuǎn)發(fā)度量

根據(jù)2.2節(jié)中定義的節(jié)點(diǎn)屬性，將消息的轉(zhuǎn)發(fā)度量如下定義：

Met=lg(aCD+10)lg(bE+10)lg(cB+10)

(4)

式中：CD代表節(jié)點(diǎn)的中心度，E代表節(jié)點(diǎn)的剩余能量，B代表節(jié)點(diǎn)的剩余緩存空間，a、b、c是調(diào)諧參數(shù)。對(duì)數(shù)運(yùn)算是為了消除參數(shù)的異方差性。從式(4)可以看出，如a=1、b=0、c=0時(shí)，則節(jié)點(diǎn)轉(zhuǎn)發(fā)度量Met僅由中心度CD決定，即為Bubble Rap算法的做法。因?yàn)殡S著存儲(chǔ)技術(shù)的發(fā)展，剩余緩存相比于節(jié)點(diǎn)中心度和剩余能量對(duì)整個(gè)網(wǎng)絡(luò)的性能的影響會(huì)稍差一些，因此可以取系數(shù)a=2、b=2、c=1。在后續(xù)的仿真實(shí)驗(yàn)中可以看出，使用三個(gè)系數(shù)CD、E和B來決定轉(zhuǎn)發(fā)度量可以獲得更好的網(wǎng)絡(luò)性能并達(dá)到節(jié)能的效果。當(dāng)CD為局部中心度時(shí)，可以通過式(4)計(jì)算得到局部轉(zhuǎn)發(fā)度量Met(Lo_Met)；當(dāng)CD表示節(jié)點(diǎn)的全局中心度時(shí)，可計(jì)算得出全局轉(zhuǎn)發(fā)度量Met(Glo_Met)。其中Met可以表示為二元組(Lo_Met，Glo_Met)。當(dāng)更新Met時(shí)，節(jié)點(diǎn)的局部和全局轉(zhuǎn)發(fā)度量值需要同時(shí)更新。

3.2 消息轉(zhuǎn)發(fā)策略

本文提出的EABNA算法實(shí)際上是對(duì)Bubble Rap算法的改進(jìn)。它采用簡單檢測算法，將網(wǎng)絡(luò)劃分成若干個(gè)社區(qū)，并且每個(gè)節(jié)點(diǎn)的社區(qū)信息會(huì)隨著自身的移動(dòng)實(shí)時(shí)更新。另外EABNA算法中存在兩張信息表，分別記錄了網(wǎng)絡(luò)中所有節(jié)點(diǎn)的全局轉(zhuǎn)發(fā)度量排名和局部轉(zhuǎn)發(fā)度量排名。該算法具體的轉(zhuǎn)發(fā)過程可以分為兩個(gè)階段：第一階段消息未進(jìn)入目標(biāo)節(jié)點(diǎn)的本地社區(qū)。當(dāng)攜帶消息的節(jié)點(diǎn)在移動(dòng)過程中遇到其他節(jié)點(diǎn)時(shí)，如果相遇節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)則直接進(jìn)行消息傳遞，本次通信結(jié)束，否則判斷相遇節(jié)點(diǎn)是否與目標(biāo)節(jié)點(diǎn)同屬一個(gè)社區(qū)。如果是，則將消息轉(zhuǎn)發(fā)給該節(jié)點(diǎn)，進(jìn)入第二階段，否則查詢節(jié)點(diǎn)的全局轉(zhuǎn)發(fā)度量排名表，將消息轉(zhuǎn)發(fā)給第一個(gè)排名比自己大的相遇節(jié)點(diǎn)，由該節(jié)點(diǎn)重復(fù)上述流程。第二階段是消息進(jìn)入目標(biāo)節(jié)點(diǎn)的本地社區(qū)之后。在這個(gè)階段，根據(jù)局部轉(zhuǎn)發(fā)度量進(jìn)行消息傳輸，節(jié)點(diǎn)在移動(dòng)過程中向局部轉(zhuǎn)發(fā)度量比自身高的節(jié)點(diǎn)發(fā)送消息，直到遇到目標(biāo)節(jié)點(diǎn)。EABNA算法轉(zhuǎn)發(fā)消息的具體過程如圖2所示。

圖2 EABNA算法示意圖

根據(jù)EABNA算法的轉(zhuǎn)發(fā)策略，總結(jié)其偽代碼如下：

ifj=Dthen

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

else ifComm(i)≠Comm(D) then

ifComm(j)=Comm(D) orGlo_Met(i)

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

else ifComm(j)=Comm(D) andLo_Met(i)

Forward(m,j);

Update(i,energy,buffer,Met);

Update(j,energy,buffer,Met);

end if

其中：Forward(m,j)表示將消息m轉(zhuǎn)發(fā)給節(jié)點(diǎn)j；Comm(j)=Comm(D)表示節(jié)點(diǎn)j和節(jié)點(diǎn)D在同一個(gè)社區(qū)當(dāng)中；Update(i,energy,buffer,Met)表示同時(shí)更新節(jié)點(diǎn)i的剩余能量、剩余緩存和轉(zhuǎn)發(fā)度量。

4 仿真和結(jié)果分析

4.1 仿真環(huán)境設(shè)置

為了評(píng)估EABNA算法的性能，本文采用ONE模擬器搭建仿真平臺(tái)[11]，并與其他兩種路由算法進(jìn)行對(duì)比。另外仿真中使用由Haggle Project收集的兩個(gè)實(shí)驗(yàn)數(shù)據(jù)集，稱為Cambridge[12]和Infocom06[12]。在Infocom06中，人們大多數(shù)時(shí)間處在相對(duì)集中的會(huì)議廳中，活動(dòng)范圍較小，節(jié)點(diǎn)之間的接觸比較密集。而Cambridge中由于實(shí)驗(yàn)對(duì)象大多為學(xué)生，他們的活動(dòng)范圍較大，因此該數(shù)據(jù)集中節(jié)點(diǎn)的接觸時(shí)間間隔較長。表1展示了兩個(gè)數(shù)據(jù)集的詳細(xì)信息。

表1 兩組實(shí)驗(yàn)數(shù)據(jù)的特征

由于ONE模擬器對(duì)于外部輸入數(shù)據(jù)的格式有特殊的要求，而從DTN 數(shù)據(jù)集的提供者CRAWDAD社區(qū)[13]下載的Infocom06和Cambridge數(shù)據(jù)集無法直接使用，需要將其格式化成表2。

表2 ONE數(shù)據(jù)集標(biāo)準(zhǔn)格式

仿真相關(guān)參數(shù)設(shè)置如下：每個(gè)節(jié)點(diǎn)的緩存為50 MB，每個(gè)消息的大小為500 KB，每個(gè)節(jié)點(diǎn)的緩存管理模式是FIFO。設(shè)定消息的通信速率為250 KB/s，每個(gè)消息都有一個(gè)對(duì)應(yīng)的TTL，用來表示它在網(wǎng)絡(luò)中的存活時(shí)長。當(dāng)TTL變?yōu)?時(shí)，該消息自動(dòng)被丟棄，節(jié)點(diǎn)屬性的更新周期為300 s。

根據(jù)在2.2.1節(jié)中對(duì)社區(qū)以及社區(qū)檢測的詳細(xì)介紹，仿真過程中社區(qū)檢測的相關(guān)參數(shù)設(shè)置如下：熟人個(gè)數(shù)的閾值α設(shè)置為5，即當(dāng)兩個(gè)節(jié)點(diǎn)的歷史相遇次數(shù)大于5時(shí)，將相遇節(jié)點(diǎn)加入到對(duì)方的熟人集合中。熟人節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)本地社區(qū)集合的閾值β設(shè)置為0.5。將相遇節(jié)點(diǎn)的本地社區(qū)與當(dāng)前節(jié)點(diǎn)的本地社區(qū)合并的閾值γ設(shè)置為0.5，即當(dāng)兩個(gè)節(jié)點(diǎn)本地社區(qū)的交集為并集的一半時(shí)，將兩個(gè)社區(qū)合并成一個(gè)本地社區(qū)。

網(wǎng)絡(luò)中節(jié)點(diǎn)工作時(shí)能量的消耗情況如表3所示。本文中節(jié)點(diǎn)攜帶的能量的初始值設(shè)定為100 kJ。

表3 節(jié)點(diǎn)能量消耗表

4.2 仿真結(jié)果與性能分析

EABNA算法是基于Bubble Rap改進(jìn)的節(jié)能路由算法，它借鑒了Bubble Rap算法的思想，將機(jī)會(huì)網(wǎng)絡(luò)分成多個(gè)社區(qū)。但在轉(zhuǎn)發(fā)消息的過程當(dāng)中不僅依靠節(jié)點(diǎn)的本地中心度和全局中心度等屬性，而且還考慮了節(jié)點(diǎn)的剩余能量以及剩余緩存空間。Epidemic算法是機(jī)會(huì)網(wǎng)絡(luò)中最為典型的一種路由算法，因此將Epidemic和Bubble Rap這兩種算法作為比較的對(duì)象來評(píng)價(jià)EABNA的性能。本文主要通過消息的傳遞成功概率、消息平均傳輸時(shí)延、節(jié)點(diǎn)存活率、路由開銷這四個(gè)指標(biāo)來體現(xiàn)EABNA算法的優(yōu)劣[14]。

(1) 消息傳遞成功率 圖3描繪了消息傳遞成功概率隨著消息存活時(shí)間(TTL)的變化情況。從整體上看三種路由算法在兩種數(shù)據(jù)集中的消息傳遞成功概率隨著TTL的增加而增加。當(dāng)TTL較小時(shí)，由于機(jī)會(huì)網(wǎng)絡(luò)中消息的整體時(shí)延較大，部分消息在未到達(dá)目標(biāo)節(jié)點(diǎn)時(shí)就提前失效，導(dǎo)致各種路由算法的消息傳遞成功概率也較低。但是隨著消息存活時(shí)間TTL的逐漸增加，有更多的消息成功到達(dá)目標(biāo)節(jié)點(diǎn)，因此，消息的傳遞成功概率也相應(yīng)地增大。

(a) 在Cambridge數(shù)據(jù)集中不同路由算法的消息傳遞成功概率

(b) 在Infocom06數(shù)據(jù)集中不同路由算法的消息傳遞成功概率圖3 消息傳遞成功概率

在相同的TTL下，Cambridge數(shù)據(jù)集中的消息傳遞成功概率會(huì)略小于Infocom06。因?yàn)镃ambridge數(shù)據(jù)集節(jié)點(diǎn)的分布比較稀疏，平均每天每對(duì)節(jié)點(diǎn)的接觸次數(shù)遠(yuǎn)小于Infocom06數(shù)據(jù)集。

對(duì)于實(shí)驗(yàn)中的數(shù)據(jù)集來說，Epidemic算法消息傳遞成功概率最差，Bubble Rap次之，EABNA最好。EABNA算法的傳遞成功概率比Epidemic高約32%、比Bubble Rap高約17%。根據(jù)3.2節(jié)中定義的轉(zhuǎn)發(fā)度量函數(shù)，在初始階段由于每個(gè)節(jié)點(diǎn)具有相同的剩余能量和緩存空間，所以中繼節(jié)點(diǎn)的選擇主要依賴于節(jié)點(diǎn)的中心度CD。隨著時(shí)間的推移，具有較高中心度的節(jié)點(diǎn)的剩余能量和緩存空間迅速下降，而具有較低中心度的節(jié)點(diǎn)仍然具有較大的剩余能量和緩存空間。此時(shí)，尚未成功傳遞的消息可以由具有略低中心度和較高剩余能量及緩存空間的節(jié)點(diǎn)傳遞，從而避免由于高中心度的節(jié)點(diǎn)過早“死亡”導(dǎo)致的消息傳遞成功率快速降低。因此，EABNA算法可以實(shí)現(xiàn)比Bubble Rap和Epidemic更高的消息傳遞成功率。

(2) 消息平均傳輸時(shí)延 兩種數(shù)據(jù)集中應(yīng)用不同的算法的消息平均傳輸時(shí)延如圖4所示。消息的平均傳輸時(shí)延隨TTL的增加而增大，到達(dá)一定值之后增長速度逐漸放緩。時(shí)延較大的消息在未到達(dá)目標(biāo)節(jié)點(diǎn)之前就會(huì)因?yàn)榇婊顣r(shí)間不足而被丟棄，而這部分消息并不計(jì)算在消息的平均時(shí)延之內(nèi)，因此消息的平均傳輸時(shí)延和TTL成正比關(guān)系。當(dāng)TTL到達(dá)一定值后大部分消息都能夠在此TTL之內(nèi)完成傳輸，于是消息平均時(shí)延的增速就會(huì)趨于平緩。

(a) 在Cambridge數(shù)據(jù)集中不同路由算法的消息平均傳輸時(shí)延

(b) 在Infocom06數(shù)據(jù)集中不同路由算法的消息平均傳輸時(shí)延圖4 消息平均傳輸時(shí)延

在相同TTL的條件下，Cambridge數(shù)據(jù)集中的消息平均時(shí)延會(huì)略大于Infoncom06數(shù)據(jù)集。造成這個(gè)結(jié)果的主要原因是Infoncom06數(shù)據(jù)集中的節(jié)點(diǎn)比較密集，消息有更多的機(jī)會(huì)傳輸?shù)侥繕?biāo)節(jié)點(diǎn)。

在兩種數(shù)據(jù)集當(dāng)中EABNA算法的表現(xiàn)均優(yōu)于Bubble Rap和Epidemic算法。從仿真結(jié)果來看，EABNA算法中消息的平均時(shí)延比Bubble Rap降低了10%左右，比Epidemic降低了28%左右。雖然在節(jié)點(diǎn)資源充足的情況下，Bubble Rap和Epidemic的消息時(shí)延都低于EABNA算法，但隨著部分節(jié)點(diǎn)資源耗盡，Epidemic和Bubble Rap算法的時(shí)延會(huì)迅速上升。因此，從整體上來看EABNA算法在消息平均時(shí)延方面的表現(xiàn)更好。

(3) 節(jié)點(diǎn)生存率 圖5反映了EABNA、Bubble Rap、Epidemic三種路由算法的節(jié)點(diǎn)存活率在兩種數(shù)據(jù)集中隨TTL的變化情況。從整體上來看，三種算法隨著消息存活時(shí)間TTL呈遞減趨勢，而且在Infocom06數(shù)據(jù)集中節(jié)點(diǎn)存活率下降的速度相對(duì)于Cambridge數(shù)據(jù)集較快。當(dāng)TTL維持在一個(gè)較小值時(shí)，由于消息快速失效，節(jié)點(diǎn)間的通信頻率較低，減少了對(duì)節(jié)點(diǎn)的資源如能量和緩存空間的消耗，延長了節(jié)點(diǎn)的存活時(shí)間。但隨著消息存活時(shí)間TTL的增大，網(wǎng)絡(luò)中節(jié)點(diǎn)間通信次數(shù)也會(huì)遞增并伴隨資源消耗的增加，導(dǎo)致節(jié)點(diǎn)存活率下降。在節(jié)點(diǎn)通信相對(duì)頻繁的Infocom06數(shù)據(jù)集中，節(jié)點(diǎn)更加容易“死亡”，其存活率比Cambridge數(shù)據(jù)集低。

(a) 在Cambridge數(shù)據(jù)集中不同路由算法的節(jié)點(diǎn)存活率

(b) 在Infocom06數(shù)據(jù)集中不同路由算法的節(jié)點(diǎn)存活率圖5 節(jié)點(diǎn)生存概率

從兩種數(shù)據(jù)集中都能夠得出，在相同的TTL下Epidemic算法的節(jié)點(diǎn)存活率最低，Bubble Rap次之，而EABNA算法的節(jié)點(diǎn)存活率最高。與其他兩種算法相比，EABNA算法的節(jié)點(diǎn)存活率可以提高245%左右，即在仿真結(jié)束時(shí)還有更多的節(jié)點(diǎn)仍然存活。Epidemic算法采用消息的泛洪傳輸機(jī)制，因此表現(xiàn)最差。而Bubble Rap算法中一味將消息轉(zhuǎn)發(fā)給中心度高的節(jié)點(diǎn)，導(dǎo)致這些節(jié)點(diǎn)轉(zhuǎn)發(fā)過多的消息而耗盡資源的不足。EABNA算法在選擇中繼節(jié)點(diǎn)時(shí)均衡了節(jié)點(diǎn)中心度、剩余能量、剩余緩存空間三者之間的關(guān)系，從一定程度上延長了網(wǎng)絡(luò)生命周期。

(4) 路由開銷 圖6為三種算法在路由開銷方面的仿真結(jié)果。顯然在任何數(shù)據(jù)集當(dāng)中，Epidemic的路由開銷是最大的，而Bubble Rap和EABNA算法的路由開銷的性能相差不大，都為Epidemic的1/3左右，并且隨著TTL的增大緩慢增加。因?yàn)镋pidemic在傳輸消息的過程中會(huì)大量復(fù)制消息副本，并發(fā)送給所有接觸的節(jié)點(diǎn)，大大增加了路由開銷。而EABNA算法的路由開銷略微的大于Bubble Rap算法。Bubble Rap算法對(duì)節(jié)點(diǎn)中心度的依賴更高，在資源充足的情況下可以減少消息的轉(zhuǎn)發(fā)次數(shù)。但是當(dāng)資源不足時(shí)，Bubble Rap算法的路由開銷會(huì)大于EABNA算法。綜合上述原因再結(jié)合仿真結(jié)果可得出EABNA和Bubble Rap算法的路由開銷基本相近。

(a) 在Cambridge數(shù)據(jù)集中不同路由算法的路由開銷

(b) 在Infocom06數(shù)據(jù)集中不同路由算法的路由開銷圖6 路由開銷

5 結(jié) 語

本文提出了一種基于節(jié)點(diǎn)屬性的高效節(jié)能路由算法EABNA。當(dāng)選擇中繼節(jié)點(diǎn)時(shí)充分考慮了節(jié)點(diǎn)的社會(huì)屬性和其本身屬性的動(dòng)態(tài)變化。本文使用兩種現(xiàn)實(shí)生活中的移動(dòng)數(shù)據(jù)集對(duì)EABNA、BubbeRap、Epidemic三種算法進(jìn)行仿真。通過詳細(xì)比較和分析實(shí)驗(yàn)結(jié)果，最終可以得出EABNA算法雖然略微犧牲了路由開銷方面的性能，但是其消息傳遞成功率、消息平均傳輸時(shí)延、節(jié)點(diǎn)存活率方面的性能都有較大的提升，延長了機(jī)會(huì)網(wǎng)絡(luò)生命周期。

機(jī)會(huì)網(wǎng)絡(luò)中在選擇消息轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)時(shí)還可以考慮更多的屬性，例如節(jié)點(diǎn)的時(shí)空屬性[15]等。通過這些屬性減少轉(zhuǎn)發(fā)次數(shù)，延長網(wǎng)絡(luò)的生命周期，達(dá)到一定的節(jié)能效果。