考慮相遇強(qiáng)度的約束擴(kuò)散路由算法*

張毅夫 劉 靜 余海健 朱子奇

（1.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430065）

（2.武漢科技大學(xué)大數(shù)據(jù)科學(xué)與工程研究院 武漢 430065）

（3.武漢科技大學(xué)智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室 武漢 430065）

1 引言

機(jī)會(huì)網(wǎng)絡(luò)［1］同時(shí)具備間歇式聯(lián)通網(wǎng)絡(luò)［2］和延時(shí)容忍網(wǎng)絡(luò)［3］的特征，采用“存儲(chǔ)—攜帶—轉(zhuǎn)發(fā)”的模式進(jìn)行通信，是一種不需要源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在完成鏈路，利用節(jié)點(diǎn)移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)通信的自組織網(wǎng)絡(luò)［4］。如圖1 所示，消息在源節(jié)點(diǎn)1 處產(chǎn)生，同一陰影內(nèi)的節(jié)點(diǎn)表明它們可以建立通信。在t1時(shí)刻，消息由源節(jié)點(diǎn)1轉(zhuǎn)發(fā)給節(jié)點(diǎn)3；緊接著，由于節(jié)點(diǎn)的移動(dòng)，在t2 時(shí)刻，消息攜帶節(jié)點(diǎn)3 與其節(jié)點(diǎn)4成功建立通信，并將消息交付給節(jié)點(diǎn)4；最終，在t3時(shí)刻，消息被成功的交付給目的節(jié)點(diǎn)7。

圖1 機(jī)會(huì)網(wǎng)絡(luò)示意圖

機(jī)會(huì)網(wǎng)絡(luò)非常契合拓?fù)渥兓膱?chǎng)景，具有極大的實(shí)用價(jià)值，目前已衍生出許多具體應(yīng)用，如手持設(shè)備組網(wǎng)PSN（Pocket Switched Network）［5］，車(chē)載網(wǎng)絡(luò)CarTel［6］，野生動(dòng)物追蹤機(jī)會(huì)網(wǎng)絡(luò)ZebraNet［7］，偏遠(yuǎn)地區(qū)網(wǎng)絡(luò)傳輸DakNet［8］等。同時(shí)，機(jī)會(huì)網(wǎng)絡(luò)受限于不穩(wěn)定的拓?fù)滏溄?、能量和?chǔ)存受限等原因，仍存在消息投遞率低、網(wǎng)絡(luò)負(fù)載高和平均時(shí)延高這些缺點(diǎn)。提高機(jī)會(huì)網(wǎng)絡(luò)的消息轉(zhuǎn)發(fā)效率是機(jī)會(huì)網(wǎng)絡(luò)中的重點(diǎn)研究問(wèn)題。

本文基于節(jié)點(diǎn)的歷史相遇信息提出了EICD算法。主要貢獻(xiàn)如下：

1）提出了相遇強(qiáng)度和其計(jì)算公式，相遇強(qiáng)度把時(shí)間作為計(jì)算的重要依據(jù)，能夠更準(zhǔn)確地評(píng)估兩個(gè)節(jié)點(diǎn)相遇的可能性。

2）針對(duì)多拷貝路由中存在的大量消息副本和已投遞消息的冗余副本，利用約束擴(kuò)散策略和去冗余策略來(lái)控制網(wǎng)絡(luò)中消息副本數(shù)量并及時(shí)刪除網(wǎng)絡(luò)中存在的冗余副本，降低網(wǎng)絡(luò)負(fù)載。

2 相關(guān)工作

機(jī)會(huì)網(wǎng)絡(luò)中，根據(jù)存在的消息副本數(shù)量將路由算法分為兩類(lèi)［9］：?jiǎn)慰截惵酚伤惴ê投嗫截惵酚伤惴ā?/p>

最典型的單拷貝路由算法當(dāng)屬Direct Delievery 算法［10］，該算法從消息在源節(jié)點(diǎn)生成直到投遞到目的節(jié)點(diǎn)，不再生成任何消息副本，也不借助任何中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)，源節(jié)點(diǎn)在移動(dòng)過(guò)程中只有遇到目的節(jié)點(diǎn)時(shí)才將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。該算法具備與單拷貝路由算法同樣的特性，可以大幅度減少網(wǎng)絡(luò)中的資源浪費(fèi)和網(wǎng)絡(luò)開(kāi)銷(xiāo)，但存在消息投遞率低、消息轉(zhuǎn)發(fā)時(shí)延高等缺陷。

在多拷貝算法中，Epidemic算法［11］是其中的典型。該算法的主要思想是當(dāng)兩個(gè)節(jié)點(diǎn)在移動(dòng)中相遇并建立通信時(shí)，節(jié)點(diǎn)會(huì)將自身攜帶且對(duì)方不存在的消息復(fù)制給對(duì)方。該算法會(huì)在網(wǎng)絡(luò)中產(chǎn)生大量的副本，從而造成極大的網(wǎng)絡(luò)資源浪費(fèi)。由于節(jié)點(diǎn)緩存空間與通信時(shí)間有限，大面積的丟包和無(wú)用的計(jì)算致使該算法存在投遞率低、網(wǎng)絡(luò)負(fù)載高等缺點(diǎn)。

Spray And Wait 算法［12］將路由分為“Spray”和“Wait”兩個(gè)階段，在“Spray”階段，先對(duì)消息進(jìn)行一定數(shù)量的復(fù)制，當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，節(jié)點(diǎn)轉(zhuǎn)發(fā)一半數(shù)量的消息副本給相遇節(jié)點(diǎn)，自身保留另一半，直至節(jié)點(diǎn)中僅剩一份消息副本。之后進(jìn)入“Wait”階段，即消息攜帶節(jié)點(diǎn)只在遇到目的節(jié)點(diǎn)時(shí)將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)。該算法將Direct Delievery 算法和Epidemic算法進(jìn)行結(jié)合，既能保證一定的消息投遞率又能適當(dāng)?shù)亟档途W(wǎng)絡(luò)負(fù)載和轉(zhuǎn)發(fā)時(shí)延。

Prophet 算法［13］是一種考慮相遇概率的路由算法。該算法通過(guò)節(jié)點(diǎn)間的歷史相遇信息來(lái)預(yù)測(cè)未來(lái)兩節(jié)點(diǎn)的相遇概率。當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，比較兩個(gè)節(jié)點(diǎn)與消息目的節(jié)點(diǎn)相遇的概率，依此來(lái)決定是否復(fù)制和轉(zhuǎn)發(fā)該消息。

MaxProp 算法［14］充分考慮節(jié)點(diǎn)的緩存資源，根據(jù)節(jié)點(diǎn)相遇概率和消息跳數(shù)（消息通過(guò)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的次數(shù)）來(lái)決定何時(shí)丟棄緩存中的消息。跳數(shù)越大，則消息的優(yōu)先級(jí)越低；跳數(shù)越小，則消息的優(yōu)先級(jí)越高。

在多拷貝路由算法中，為提高消息投遞率，將會(huì)生成大量的消息副本。在消息傳遞過(guò)程中，大量的消息副本和已投遞消息的冗余副本不僅占用了節(jié)點(diǎn)的緩存空間，還浪費(fèi)了大量的計(jì)算時(shí)間，這在一定程度上降低了消息投遞率、加大了網(wǎng)絡(luò)負(fù)載和轉(zhuǎn)發(fā)時(shí)延。鑒于此，本文利用約束擴(kuò)散策略和去冗余策略來(lái)控制網(wǎng)絡(luò)中消息副本數(shù)量并及時(shí)刪除網(wǎng)絡(luò)中存在的冗余副本，降低網(wǎng)絡(luò)負(fù)載。同時(shí)，提出考慮相遇強(qiáng)度的精準(zhǔn)傳遞策略來(lái)幫助消息更準(zhǔn)確地找到目的節(jié)點(diǎn)。

3 EICD算法

EICD 算法通過(guò)控制網(wǎng)絡(luò)中的副本數(shù)量和刪除網(wǎng)絡(luò)中冗余的消息副本兩種方式來(lái)降低網(wǎng)絡(luò)負(fù)載和轉(zhuǎn)發(fā)時(shí)延，同時(shí)充分考慮時(shí)間因素來(lái)評(píng)估節(jié)點(diǎn)間下次相遇的可能性。該算法將路由過(guò)程分為三個(gè)階段，分別為約束擴(kuò)散階段、考慮相遇強(qiáng)度的精準(zhǔn)傳遞階段和去冗余階段。

3.1 約束擴(kuò)散階段

靜態(tài)網(wǎng)絡(luò)常用度中心性、相似中心性和中介中心性［15～16］來(lái)衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的中心度。由于動(dòng)態(tài)網(wǎng)絡(luò)和靜態(tài)網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)浔举|(zhì)不同，這些指標(biāo)無(wú)法應(yīng)用于機(jī)會(huì)網(wǎng)絡(luò)。本文借鑒靜態(tài)網(wǎng)絡(luò)的度中心性等概念，提出節(jié)點(diǎn)活躍度Ac和其計(jì)算公式。Aci為節(jié)點(diǎn)Ni的活躍度，計(jì)算如式（1）：其中，a(Ni,Nj)代表節(jié)點(diǎn)Ni與節(jié)點(diǎn)Nj的連接情況。若建立過(guò)連接，則a(Ni,Nj)=1；否則a(Ni,Nj)=0。ω(Ni,Nj) 代表節(jié)點(diǎn)Ni與節(jié)點(diǎn)Nj建立連接的次數(shù)。一般來(lái)說(shuō)，活躍度高的節(jié)點(diǎn)能和更多的節(jié)點(diǎn)建立通信。

約束擴(kuò)散階段如算法1 所示。在約束擴(kuò)散階段，利用限制數(shù)量的消息復(fù)制策略去控制網(wǎng)絡(luò)中消息的副本數(shù)量，進(jìn)而提高整個(gè)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)效率。為避免在擴(kuò)散階段浪費(fèi)大量的網(wǎng)絡(luò)資源，故限制消息自源節(jié)點(diǎn)產(chǎn)生后，只有跳數(shù)為0 的消息才被允許去尋找活躍度更高的節(jié)點(diǎn)。消息跳數(shù)即消息由源節(jié)點(diǎn)產(chǎn)生到成功投遞到目的節(jié)點(diǎn)的過(guò)程中，經(jīng)過(guò)中繼節(jié)點(diǎn)的次數(shù)。

算法1 約束擴(kuò)散策略

輸入 源節(jié)點(diǎn)Ni，相遇節(jié)點(diǎn)Nj，節(jié)點(diǎn)活躍度Ac，源節(jié)點(diǎn)Ni攜帶的消息m。

輸出 源節(jié)點(diǎn)Ni中消息是否轉(zhuǎn)發(fā)給相遇節(jié)點(diǎn)Nj。

1）對(duì)源節(jié)點(diǎn)Ni中產(chǎn)生的消息m生民共s個(gè)副一

2）FOR源節(jié)點(diǎn)Ni的所有相遇節(jié)點(diǎn)NjDO

3）FOR源節(jié)點(diǎn)Ni中的所有消息m DO

4）IF相遇節(jié)點(diǎn)Ni是消息m的目的節(jié)點(diǎn)THEN

5）將消息m傳遞給相遇節(jié)點(diǎn)Nj

6）ELSE IF相遇節(jié)點(diǎn)Nj不存在消息m

7）&&Acj＞Aci

8）&&消息m的跳數(shù)為0 THEN

9）將消息m傳遞給相遇節(jié)點(diǎn)Nj

10）END IF

11）END IF

12）END FOR

13）END FOR

3.2 精準(zhǔn)傳遞階段

為了記錄節(jié)點(diǎn)的歷史相遇信息，本文針對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)建立了一張TEt 表，即。TEt 表中，表示節(jié)點(diǎn)Ni與節(jié)點(diǎn)Nj的第k 次相遇的時(shí)間，表示節(jié)點(diǎn)Ni與節(jié)點(diǎn)Nj第k+1次相遇強(qiáng)度，表示節(jié)點(diǎn)Ni與節(jié)點(diǎn)Nj第k 次通信持續(xù)的時(shí)間。相遇強(qiáng)度E是一個(gè)評(píng)估指標(biāo)，代表此節(jié)點(diǎn)在未來(lái)一段時(shí)間遇到其它某節(jié)點(diǎn)的機(jī)會(huì)。相遇強(qiáng)度越大則相遇可能性越高，反之亦然。相遇強(qiáng)度是節(jié)點(diǎn)選擇中繼節(jié)點(diǎn)的一項(xiàng)重要依據(jù)。本文充分考慮時(shí)間因素，將相遇強(qiáng)度的計(jì)算分為激勵(lì)和衰退兩部分。

用tit表示兩節(jié)點(diǎn)此次相遇距離上次相遇已經(jīng)過(guò)的時(shí)間，計(jì)算如式（2）：

用tst表示網(wǎng)絡(luò)中相遇的平均間隔時(shí)間，計(jì)算如式（3）：

用max_E表示網(wǎng)絡(luò)中歷史最大相遇強(qiáng)度，計(jì)算如式（4）。其中，K 為Ni和Nj的最大相遇次數(shù)；N為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合。

相遇強(qiáng)度的激勵(lì)策略部分計(jì)算如式（5）。Eold表示更新前的相遇強(qiáng)度；max_E為網(wǎng)絡(luò)中歷史最大相遇強(qiáng)度；e為激勵(lì)系數(shù)，若兩節(jié)點(diǎn)該時(shí)間間隔內(nèi)相遇，則在Eold的基礎(chǔ)上先提高e*Eold，再進(jìn)行額外的激勵(lì)增加。

當(dāng)相遇間隔時(shí)間tit∈(0,tst]時(shí)，給予相遇強(qiáng)度更大的激勵(lì)。此時(shí)兩個(gè)節(jié)點(diǎn)之間再次建立通信時(shí)間距離上次通信結(jié)束時(shí)間較短，短時(shí)間內(nèi)兩個(gè)節(jié)點(diǎn)多次通信意味著在未來(lái)一段時(shí)間內(nèi)，它們很可能再次建立通信。兩節(jié)點(diǎn)間的每次相遇都會(huì)對(duì)Eold有激勵(lì)作用。當(dāng)tit∈(tst,∞)時(shí)，兩節(jié)點(diǎn)間的相遇間隔時(shí)間較長(zhǎng)，將給予相遇強(qiáng)度更少的激勵(lì)。伴隨相遇間隔時(shí)間tit越來(lái)越長(zhǎng)，Eenc會(huì)越來(lái)越趨近于Eold，卻不會(huì)低于它。鑒于此，本文設(shè)立相遇強(qiáng)度衰退機(jī)制。即如果在較長(zhǎng)時(shí)間中兩個(gè)節(jié)點(diǎn)沒(méi)有相遇，就通過(guò)衰退策略不斷地降低相遇強(qiáng)度，衰退策略部分計(jì)算如式（6）。

其中γ表示衰退系數(shù)。當(dāng)兩個(gè)節(jié)點(diǎn)在衰退期相遇后，會(huì)在衰退后的相遇強(qiáng)度基礎(chǔ)上再進(jìn)行激勵(lì)策略。

算法2 精準(zhǔn)傳遞策略

輸入 節(jié)點(diǎn)Ni，相遇節(jié)點(diǎn)Nj，源節(jié)點(diǎn)Ni攜帶的消息m，消息的目的節(jié)點(diǎn)Nd。

輸出 節(jié)點(diǎn)Ni中消息是否轉(zhuǎn)發(fā)給相遇節(jié)點(diǎn)Ni。

1）FOR源節(jié)點(diǎn)Ni的所有相遇節(jié)點(diǎn)NiDO

2）根據(jù)公式（5）和（6）更新節(jié)點(diǎn)Ni與Nj之間的相遇強(qiáng)度

3）FOR源節(jié)點(diǎn)Ni中的所有消息m DO

4）令Ei，d=Ni與Nj在此時(shí)刻的相遇強(qiáng)度（不更新TEt 發(fā)表）

5）令Ei，d=Nj與Nd在此時(shí)刻的相遇強(qiáng)度（不更新TEt 發(fā)表）

6）IF Ei，d＜Ei，dTHEN

7）將消息m傳遞給相遇節(jié)點(diǎn)Nj

8）END IF

9）END FOR

10）END FOR

精準(zhǔn)傳遞算法如算法2 所示。當(dāng)兩個(gè)節(jié)點(diǎn)相遇后，首先根據(jù)式（5）和式（6）更新兩個(gè)節(jié)點(diǎn)的TEt表。然后，根據(jù)式（6）分別計(jì)算此時(shí)刻兩個(gè)節(jié)點(diǎn)和目的節(jié)點(diǎn)的相遇強(qiáng)度，由于兩個(gè)節(jié)點(diǎn)并未與目的節(jié)點(diǎn)相遇，所以此時(shí)不需要更新兩個(gè)節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的TEt 表。最后，根據(jù)此時(shí)刻兩個(gè)節(jié)點(diǎn)與目的節(jié)點(diǎn)的相遇強(qiáng)度大小來(lái)決定是否轉(zhuǎn)發(fā)消息。

3.3 去冗余階段

為了提高投遞效率，在消息產(chǎn)生時(shí)，往往會(huì)對(duì)消息m 進(jìn)行一定數(shù)量的復(fù)制。在消息m 成功投遞到目的節(jié)點(diǎn)后，網(wǎng)絡(luò)中剩余的消息副本仍然存在并占用網(wǎng)絡(luò)資源，它們不僅會(huì)占用緩存空間，而且還會(huì)增加計(jì)算量，所以需要及時(shí)地刪除網(wǎng)絡(luò)中冗余的消息副本。本文設(shè)計(jì)了一種去冗余策略來(lái)刪除成功投遞的消息在網(wǎng)絡(luò)中存在的冗余副本。

算法3 去冗余策略

輸入 節(jié)點(diǎn)Ni，相遇節(jié)點(diǎn)Nj，節(jié)點(diǎn)活躍度Ac，節(jié)點(diǎn)交付記錄DR、節(jié)點(diǎn)攜帶消息m、節(jié)點(diǎn)活躍度Ac。

輸出 去冗余后節(jié)點(diǎn)Ni、Nj的狀態(tài)。

1）當(dāng)節(jié)點(diǎn)Ni和節(jié)點(diǎn)Nj建立通信時(shí)

2）DRnew=DRi∪DRj

3）根據(jù)DRnew刪除節(jié)點(diǎn)Ni中已交付的消息

4）根據(jù)DRnew刪除節(jié)點(diǎn)Nj中已交付的消息

5）IF Aci＞AcjTHEN

6）DRi=DRnew

7）清空節(jié)點(diǎn)Nj的交付記錄DRi

8）END IF

9）IF Aci＜AcjTHEN

10）DRj=DRnew

11）清空節(jié)點(diǎn)Ni的交付記錄DRi

12）END IF

設(shè)DR（Delivery Record）為各節(jié)點(diǎn)的消息交付記錄，用來(lái)記錄本節(jié)點(diǎn)成功交付的消息。當(dāng)兩節(jié)點(diǎn)處于通信狀態(tài)時(shí)，交換彼此的DR，得到一個(gè)新的DRnew，節(jié)點(diǎn)Ni、Nj根據(jù)DRnew刪除節(jié)點(diǎn)中冗余的已交付消息副本；在刪除冗余消息副本后，為避免節(jié)點(diǎn)的DR 占用過(guò)多的節(jié)點(diǎn)緩存資源，將會(huì)刪除活躍度低的節(jié)點(diǎn)的DR，把活躍度高的節(jié)點(diǎn)的DR 更新為DRnew。去冗余算法如算法3所示。

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

4.1 仿真環(huán)境

本文使用The ONE（The Opportunistic Network Environment simulator）仿真平臺(tái)來(lái)進(jìn)行仿真實(shí)驗(yàn)。在分別改變節(jié)點(diǎn)緩存空間、消息生存周期以及節(jié)點(diǎn)數(shù)量對(duì)算法進(jìn)行多次對(duì)比仿真實(shí)驗(yàn)，實(shí)驗(yàn)仿真參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)設(shè)置

4.2 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文所提出的EICD 算法的有效性，將其與四個(gè)經(jīng)典的路由算法Epidemic、Spray And Wait、Prophet 以及MaxProp 進(jìn)行對(duì)比，并選用消息投遞率、網(wǎng)絡(luò)負(fù)載、平均轉(zhuǎn)發(fā)時(shí)延［17～18］三個(gè)機(jī)會(huì)網(wǎng)絡(luò)中重要的評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)算法的性能。

4.2.1 節(jié)點(diǎn)緩存空間對(duì)路由算法的影響

EICD 算法與其它經(jīng)典算法在不同節(jié)點(diǎn)緩存空間下的性能比較如圖2～圖4 所示。設(shè)定網(wǎng)絡(luò)中消息生存周期為150min，節(jié)點(diǎn)數(shù)量為240個(gè)。

圖2 不同緩存空間下的消息投遞率

圖3 不同緩存空間下的網(wǎng)絡(luò)負(fù)載

圖4 不同緩存空間下的平均轉(zhuǎn)發(fā)時(shí)延

實(shí)驗(yàn)結(jié)果表明，各算法的投遞率和平均轉(zhuǎn)發(fā)時(shí)延隨著節(jié)點(diǎn)緩存空間的增加而上升，網(wǎng)絡(luò)負(fù)載隨著節(jié)點(diǎn)緩存空間的增加而降低。EICD 算法的投遞率比MaxProp、Spray And Wait、Epidemic 和Prophet 等算法都有顯著提高。在網(wǎng)絡(luò)負(fù)載方面，EICD 算法強(qiáng)于MaxProp、Epidemic 和Prophet 算法，弱于Spray And Wait 算法。這是因?yàn)镾pray And Wait 算法在“Wait”階段只進(jìn)行一次到目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)，從而節(jié)省了大量的網(wǎng)絡(luò)資源。在平均轉(zhuǎn)發(fā)時(shí)延上，伴隨著緩存空間加大，平均轉(zhuǎn)發(fā)時(shí)延的增加幅度逐漸減小。

4.2.2 消息生存周期對(duì)路由算法的影響

EICD 算法與其它經(jīng)典算法在不同消息生存周期下的性能比較如圖5～圖7 所示。設(shè)定網(wǎng)絡(luò)中節(jié)點(diǎn)緩存空間為10MB，節(jié)點(diǎn)數(shù)量為240個(gè)。

圖5 不同消息生存周期下的消息投遞率

圖6 不同緩消息生存周期下的網(wǎng)絡(luò)負(fù)載

圖7 不同消息生存周期下的平均轉(zhuǎn)發(fā)時(shí)延

隨著節(jié)點(diǎn)消息生存周期的提高，算法投遞率整體呈上升趨勢(shì)，但是當(dāng)消息生存周期過(guò)大時(shí)，算法的投遞率會(huì)趨于平穩(wěn)，甚至略有降低。這是因?yàn)橄⑸嬷芷谶^(guò)長(zhǎng)，擠占了節(jié)點(diǎn)的緩存空間，使得節(jié)點(diǎn)沒(méi)有緩存空間接受新消息。在平均轉(zhuǎn)發(fā)時(shí)延上，消息生存周期過(guò)長(zhǎng)將不會(huì)過(guò)早地丟棄該消息，這使得成功投遞的消息投遞所耗時(shí)長(zhǎng)有所提升，從而提高了消息平均轉(zhuǎn)發(fā)時(shí)延。

4.2.3 網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量對(duì)路由算法的影響

EICD 算法與其它經(jīng)典算法在不同節(jié)點(diǎn)數(shù)量下的性能比較如圖8～圖10所示。設(shè)定網(wǎng)絡(luò)中節(jié)點(diǎn)緩存空間為10MB，消息生存周期為150min。

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

圖9 不同節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)負(fù)載

圖10 不同節(jié)點(diǎn)數(shù)量下的平均轉(zhuǎn)發(fā)時(shí)延

隨著節(jié)點(diǎn)數(shù)量的增加，所有網(wǎng)絡(luò)的整體性能普遍增高。伴隨著節(jié)點(diǎn)數(shù)量的增加，各算法的投遞率大體呈上升趨勢(shì)，EICD 算法投遞率高于其它算法。在網(wǎng)絡(luò)負(fù)載上，除Spray And Wait 算法外的其它拳法上升趨勢(shì)明顯。在平均轉(zhuǎn)發(fā)時(shí)延上，EICD算法明顯優(yōu)于其它算法。

5 結(jié)語(yǔ)

本文提出了一種考慮相遇強(qiáng)度的約束擴(kuò)散路由算法。在消息產(chǎn)生節(jié)點(diǎn)對(duì)消息復(fù)制s 個(gè)副本，然后僅進(jìn)行一次向活躍度高的節(jié)點(diǎn)的跳躍；接著當(dāng)兩個(gè)節(jié)點(diǎn)相遇時(shí)，根據(jù)提出的充分考慮時(shí)間因素的相遇強(qiáng)度計(jì)算策略來(lái)計(jì)算節(jié)點(diǎn)與消息目的節(jié)點(diǎn)在未來(lái)一段時(shí)間的相遇強(qiáng)度，并將消息轉(zhuǎn)發(fā)給具有更高相遇強(qiáng)度的中繼節(jié)點(diǎn)；在去冗余階段，節(jié)點(diǎn)會(huì)交換彼此的消息交付記錄并據(jù)此來(lái)刪除已投遞消息的冗余副本，降低網(wǎng)絡(luò)負(fù)載。仿真實(shí)驗(yàn)表明，EICD 算法在節(jié)點(diǎn)緩存空間不同、消息生存周期不同和節(jié)點(diǎn)數(shù)量不同等情況下，均能夠有效地提高消息投遞率、降低網(wǎng)絡(luò)負(fù)載和平均轉(zhuǎn)發(fā)時(shí)延。