周春月，龐 迪

(北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

隨著傳感器、微電子、通信、人工智能、邊緣計算等技術(shù)的飛速發(fā)展，物聯(lián)網(wǎng)理論與技術(shù)日趨成熟，已經(jīng)廣泛應(yīng)用于智能家居、智慧城市、車聯(lián)網(wǎng)、工業(yè)生產(chǎn)等領(lǐng)域[1-2].而傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)或移動自組織網(wǎng)絡(luò)(Mobile Ad Hoc Networks，MANETs)[3]由于網(wǎng)絡(luò)拓?fù)涞臅r變性、節(jié)點資源受限性等特點，在某些場景下無法有效運行.智能手機(jī)、平板電腦、智能車載終端等智能便攜式設(shè)備的迅速普及，使得通信、感知和計算的能力不斷提高，利用這些智能便攜式設(shè)備組成的機(jī)會網(wǎng)絡(luò)[4]更符合實際環(huán)境下的自組網(wǎng)需求，近年來成為國內(nèi)外學(xué)術(shù)界關(guān)注的熱點.

機(jī)會網(wǎng)絡(luò)(Opportunistic Networks，OppNets)是一種不需要源節(jié)點和目的節(jié)點之間存在持續(xù)連接的完整路徑，在間歇式連通的網(wǎng)絡(luò)連接狀況下，利用節(jié)點移動所帶來的接觸機(jī)會實現(xiàn)通信的自組織網(wǎng)絡(luò)[5].目前，機(jī)會網(wǎng)絡(luò)研究的熱點問題主要集中在路由技術(shù)、移動模型、安全問題等方面.由于機(jī)會網(wǎng)絡(luò)間歇式連接、節(jié)點動態(tài)變化、節(jié)點能量及存儲空間有限等特點，機(jī)會網(wǎng)絡(luò)中消息的成功傳輸面臨巨大挑戰(zhàn).

傳統(tǒng)的路由算法無法適用于機(jī)會網(wǎng)絡(luò)環(huán)境，機(jī)會網(wǎng)絡(luò)路由采取了“存儲-攜帶-轉(zhuǎn)發(fā)”的模式[6].近年來，學(xué)者們提出了大量針對機(jī)會網(wǎng)絡(luò)的新的路由算法，如Epidemic[7]、 Spray and Wait[8]、PRoPHET[9](Probabilistic Routing Protocol using History of Encounters and Transitivity)等.其中典型代表之一是PRoPHET路由算法，該算法利用歷史信息對消息傳輸成功的概率進(jìn)行估算，一段時間內(nèi)兩節(jié)點相遇次數(shù)越多，傳輸成功概率越大，否則概率隨時間衰退.與Epidemic算法相比，PRoPHET算法具有更低的網(wǎng)絡(luò)負(fù)載和更高的平均消息送達(dá)率，但是傳統(tǒng)的PRoPHET路由算法有如下不足：

1)沒有考慮節(jié)點的異構(gòu)性以及節(jié)點資源的狀況.網(wǎng)絡(luò)中不同通信能力的節(jié)點承擔(dān)相同的通信任務(wù)，且節(jié)點轉(zhuǎn)發(fā)消息不考慮下一跳節(jié)點資源狀態(tài)，會造成網(wǎng)絡(luò)資源浪費并增加網(wǎng)絡(luò)開銷.

2)缺少有效的緩存管理措施.已送達(dá)消息副本會大量存在于網(wǎng)絡(luò)節(jié)點中，消耗網(wǎng)絡(luò)資源，且節(jié)點中的消息按照FIFO隊列存儲，缺少合理的調(diào)度策略.

近年來，有很多學(xué)者都對PRoPHET算法[10-14]進(jìn)行了改進(jìn).文獻(xiàn)[10]提出了一種學(xué)習(xí)控制的轉(zhuǎn)發(fā)策略，通過機(jī)器學(xué)習(xí)的方式設(shè)置網(wǎng)絡(luò)中傳輸成功概率的門限值，當(dāng)某條消息的傳輸路徑上傳輸成功概率總和大于門限值的時候，就停止轉(zhuǎn)發(fā)，直到與目的節(jié)點相遇.該算法限制了網(wǎng)絡(luò)中不必要消息的傳播，但是會增加消息傳輸?shù)难訒r.文獻(xiàn)[11]采用Epidemic算法來加速PRoPHET算法的轉(zhuǎn)發(fā)，為每條消息設(shè)置復(fù)制次數(shù)與轉(zhuǎn)發(fā)次數(shù)計數(shù)器，當(dāng)計數(shù)器的值小于閾值的時候就采用Epidemic算法，大于閾值時則使用PRoPHET算法，這樣可以在網(wǎng)絡(luò)開始運行時提高消息送達(dá)率，但是也增加了網(wǎng)絡(luò)的開銷.文獻(xiàn)[12]提出了一種基于上下文感知的路由算法，在PRoPHET算法的基礎(chǔ)上為網(wǎng)絡(luò)中的電車節(jié)點設(shè)置更高的優(yōu)先級，令消息的轉(zhuǎn)發(fā)更傾向于利用資源豐富的電車作為中繼節(jié)點.與PRoPHET算法相比，該算法在消息送達(dá)率和網(wǎng)絡(luò)負(fù)載方面都有不錯的表現(xiàn).文獻(xiàn)[13]提出了一種利用歷史傳送概率的路由算法，當(dāng)兩節(jié)點相遇時更新彼此的傳送概率，并記錄最大的歷史傳送概率，依據(jù)這兩個值來限制網(wǎng)絡(luò)中消息的泛洪，降低網(wǎng)絡(luò)負(fù)載，改善了PRoPHET算法的性能.文獻(xiàn)[14]提出了一種基于調(diào)度機(jī)制的路由算法，在源節(jié)點與目的節(jié)點之間尋找一條傳送概率最高的路徑，并引入緩存管理措施，從網(wǎng)絡(luò)中刪除已送達(dá)的消息，有效降低了網(wǎng)絡(luò)負(fù)載.

如何高效利用網(wǎng)絡(luò)資源以及降低網(wǎng)絡(luò)負(fù)載，是機(jī)會網(wǎng)絡(luò)路由算法改進(jìn)的關(guān)鍵.本文作者以經(jīng)典的PRoPHET路由算法為基礎(chǔ)，提出了基于節(jié)點屬性和緩存管理的路由算法(OANBM)，一方面利用節(jié)點類型、電量和緩存信息指導(dǎo)網(wǎng)絡(luò)中消息的轉(zhuǎn)發(fā)，提高網(wǎng)絡(luò)資源利用效率；另一方面優(yōu)化了消息的發(fā)送和刪除隊列，并加入了從網(wǎng)絡(luò)中刪除冗余消息的措施，降低網(wǎng)絡(luò)負(fù)載.

1 OANBM算法

1.1 基于節(jié)點屬性的概率預(yù)測

令網(wǎng)絡(luò)中的每個節(jié)點都記錄到網(wǎng)絡(luò)中其他節(jié)點的概率預(yù)測值，如P(a,b)∈[0,1]代表節(jié)點A到節(jié)點B的預(yù)測概率，當(dāng)節(jié)點A與節(jié)點B相遇時交換各自的消息向量Va、Vb、各自的節(jié)點屬性信息以及到其他節(jié)點的概率預(yù)測值，只有當(dāng)B到達(dá)目的節(jié)點的概率預(yù)測值高于A時，A才將消息傳輸給B.

節(jié)點間概率預(yù)測的計算分為更新、衰退和傳遞性三部分.當(dāng)兩個節(jié)點A、B相遇時，首先利用歷史相遇信息計算兩節(jié)點間的投遞概率如下

P(a,b)=P(a,b)old+(1-P(a,b)old)·Pint

(1)

式中：Pint∈[0,1]表示初始常量；P(a,b)old為上一次的相遇概率.假如兩個節(jié)點頻繁相遇，那么他們彼此之間的投遞概率越高.

假如兩個節(jié)點一段時間沒有相遇，那么他們互相不太可能傳輸信息，因此得出衰減投遞概率為

P(a,b)=P(a,b)old·γk

(2)

式中：γ為衰減參數(shù)；k為兩個節(jié)點最后一次相遇到當(dāng)前時刻所經(jīng)歷的時間塊個數(shù).

此外，投遞概率具有傳遞性，如果節(jié)點A與節(jié)點B頻繁相遇，且節(jié)點B和節(jié)點C頻繁相遇，那么節(jié)點A和節(jié)點C之間的投遞概率也應(yīng)該提高，由此得

P(a,c)=P(a,c)old+(1-P(a,c)old)·

P(a,b)·P(b,c)·β

(3)

式中：T∈[0,1]是度量參數(shù)，它決定了傳遞性對投遞概率影響的比重.

最后得出結(jié)合節(jié)點屬性信息更新的投遞概率為

ω1·P(a,b)+ω2·T+ω3·B+ω4·E

(4)

式中：β∈[0,1]、B∈[0,1]、E∈[0,1]分別為另一節(jié)點的類型值、剩余緩存百分比和剩余電量百分比；權(quán)值ω1～ω4為初始常量且ω1+ω2+ω3+ω4=1，權(quán)值的大小反映了各屬性對投遞概率的影響程度.

1.2 緩存管理機(jī)制

由于機(jī)會網(wǎng)絡(luò)具有間歇式連接、節(jié)點存儲受限且采用“存儲-攜帶-轉(zhuǎn)發(fā)”的路由模式等特點，使得消息可能會長時間駐留在節(jié)點緩存中，因此設(shè)計有效的緩存管理機(jī)制是改進(jìn)路由算法的關(guān)鍵.緩存管理機(jī)制主要分為消息的調(diào)度和刪除兩部分，其中消息的調(diào)度是節(jié)點按照優(yōu)先級依次發(fā)送緩存中的消息；消息的刪除是當(dāng)節(jié)點緩存耗盡時，按照一定次序刪除緩存中的部分消息來接收新的消息，以及當(dāng)消息送達(dá)到目的節(jié)點時，從網(wǎng)絡(luò)中刪除已送達(dá)的消息.

1)消息調(diào)度機(jī)制的設(shè)計.

選擇優(yōu)先傳輸預(yù)測概率大的消息，因為預(yù)測概率大的消息可以很容易送達(dá)目的節(jié)點，減少消息副本的產(chǎn)生，降低網(wǎng)絡(luò)負(fù)載.此外考慮消息存活率即消息有效存活時間和初始存活時間的比值，存活率高代表消息新生成，優(yōu)先傳送存活率高的消息可以使新消息更容易得到傳輸?shù)臋C(jī)會，加速新消息的傳播，提高消息送達(dá)率.因此，根據(jù)式(5)設(shè)置消息發(fā)送優(yōu)先級，根據(jù)優(yōu)先級排序，選出發(fā)送的消息.

(5)

式中：Psp為發(fā)送優(yōu)先級：Tttl為消息有效存活時間；Tittl為消息初始存活時間；P′∈[0,1]為消息投遞概率.

2)節(jié)點緩存耗盡時消息刪除的順序.

首先考慮刪除跳數(shù)大的消息，因為消息的跳數(shù)越大，代表它在網(wǎng)絡(luò)中產(chǎn)生的副本越多，所以它已經(jīng)獲得了足夠多的傳輸機(jī)會，優(yōu)先刪除.其次考慮刪除停留時間長的消息，消息在某個節(jié)點停留時間越長，獲得的傳輸機(jī)會越多，也應(yīng)該優(yōu)先刪除.因此根據(jù)式(6)設(shè)置刪除優(yōu)先級，根據(jù)優(yōu)先級排序，選出刪除的消息.

Pdp=H+Tst

(6)

式中：Pdp為刪除優(yōu)先級；H為消息的跳數(shù)；Tst為消息的停留時間.

3)從網(wǎng)絡(luò)中刪除已經(jīng)送達(dá)的消息.

網(wǎng)絡(luò)中的每個節(jié)點都維護(hù)一個確認(rèn)消息ACK(Acknowledge)列表，當(dāng)節(jié)點將消息發(fā)送到目的節(jié)點時，就在發(fā)送節(jié)點的ACK列表添加相應(yīng)消息的ACK，并刪除該消息，并且目的節(jié)點也在自己的ACK列表中添加該消息的ACK.節(jié)點相遇時交互各自的ACK列表，并從緩存中刪除已送達(dá)的消息，簡要過程如圖1所示.

圖1(a)中展示了A、B、C三個節(jié)點當(dāng)前的狀態(tài)，外圈為節(jié)點的通信范圍.圖1(b)中節(jié)點A將消息M1傳送給節(jié)點C，傳輸完成后兩個節(jié)點在ACK列表中添加了M1，節(jié)點A將消息M1從緩存中刪除.圖1(c)中節(jié)點C和節(jié)點B交互ACK列表信息，節(jié)點B收到消息M1的ACK，將消息M1從緩存中刪除，節(jié)點C將消息M2傳送給B，傳輸完成后兩個節(jié)點在ACK列表中添加了M2，節(jié)點C將消息M2刪除.

圖1 刪除已送達(dá)消息過程Fig.1 Process of deleting delivered messages

1.3 轉(zhuǎn)發(fā)過程

圖2展示了OANBM算法的流程.

圖2 OANBM算法轉(zhuǎn)發(fā)流程Fig.2 OANBM protocol forwarding process

以節(jié)點A為例，當(dāng)節(jié)點A、B相遇進(jìn)入通信范圍時，首先交互各自的信息，包括消息向量、ACK列表以及節(jié)點屬性信息.隨后兩節(jié)點根據(jù)式(7)～式(4)更新各自的預(yù)測概率，并根據(jù)ACK列表刪除緩存中已經(jīng)送達(dá)的消息.如果節(jié)點A中有目的節(jié)點為B的消息就直接傳輸，否則根據(jù)預(yù)測概率進(jìn)行判斷.如果P′(B,D)>P′(A,D)，其中D表示Destination，即從節(jié)點B到達(dá)目的節(jié)點的預(yù)測概率大于從節(jié)點A到達(dá)目的節(jié)點的預(yù)測概率，就將該消息加入發(fā)送隊列，否則就判斷下一條消息，直到所有消息都判斷完成則結(jié)束.其中加入到發(fā)送隊列的消息按式(5)排序，決定下一次發(fā)送的消息，當(dāng)節(jié)點緩存溢出時根據(jù)式(6)決定優(yōu)先刪除哪條消息.

假設(shè)兩個節(jié)點有足夠的通信時間，節(jié)點A、B相遇轉(zhuǎn)發(fā)消息的簡單實例如圖3所示，其中圖3(a)中展示了節(jié)點A、B相遇前的狀態(tài)，外圈為節(jié)點通信范圍.圖3(b)中兩個節(jié)點相遇，首先交互必要的信息，更新預(yù)測概率.節(jié)點A中消息M5目的節(jié)點為B，節(jié)點B中的消息M3目的節(jié)點為A，M5和M3優(yōu)先傳輸后從緩存中刪除.然后根據(jù)預(yù)測概率，節(jié)點A將消息M2傳送給B，節(jié)點B將消息M6傳送給A.

圖3 OANBM算法轉(zhuǎn)發(fā)示意圖Fig.3 Diagram of the OANBM protocol forwarding process

2 仿真實驗及性能分析

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

本文采用機(jī)會網(wǎng)絡(luò)仿真平臺TheONE(Opportunistic Network Environment)進(jìn)行仿真實驗.TheONE是一個基于Java環(huán)境開發(fā)的開源仿真平臺，它支持多種移動模型和機(jī)會網(wǎng)絡(luò)中經(jīng)典的路由算法，具有良好的可拓展性，可以根據(jù)實驗需要創(chuàng)建所需的仿真環(huán)境并進(jìn)行仿真分析，相關(guān)實驗的仿真場景設(shè)置為：采用Helsinkicity仿真地圖；仿真時間為12 h；仿真面積為10000 m×8000 m；消息存活時間(Tttl)為5 h；消息大小為500 kB～1 MB；消息產(chǎn)生間隔為15～25 s.

節(jié)點參數(shù)設(shè)置如表1所示，實驗中電量的設(shè)置只考慮行人，其他類型節(jié)點的電量不限.節(jié)點的默認(rèn)傳輸速度為250 Kb/s，有軌電車和靜態(tài)節(jié)點擁有高速傳輸模式，傳輸速度為2 Mb/s.算法的初始參數(shù)設(shè)置為Pint=0.75，β=0.25，γ=0.98.關(guān)于式(4)中權(quán)值的設(shè)置方案，重點考慮預(yù)測概率P(a,b)的權(quán)值，相遇機(jī)會對與機(jī)會網(wǎng)絡(luò)中消息的成功傳輸起著至關(guān)重要的作用.其次考慮節(jié)點類型值T的權(quán)值，因為網(wǎng)絡(luò)中不同節(jié)點之間傳遞消息的能力相差很大，選擇傳遞消息能力強(qiáng)的節(jié)點有助于提高消息的送達(dá)率.最后考慮節(jié)點的緩存百分比B和電量百分比E的權(quán)值，因為參考節(jié)點緩存和電量的目的是避免消息向剩余緩存小、電量低的節(jié)點傳輸，從而減少網(wǎng)絡(luò)開銷，間接增加消息送達(dá)率.根據(jù)仿真環(huán)境和假設(shè)，在經(jīng)過多次的實驗調(diào)整后，選擇將式(4)中的權(quán)值設(shè)置為ω1=0.4，ω2=0.3，ω3=0.15，ω4=0.15.在仿真性能分析中證明了這樣的設(shè)置方案可以有效提高消息送達(dá)率，并且降低網(wǎng)絡(luò)的開銷.如果要將本文中算法應(yīng)用到其他場景，則應(yīng)該結(jié)合場景特點調(diào)整權(quán)值的設(shè)置方案，否則可能會影響算法的性能.

表1 節(jié)點參數(shù)設(shè)置Tab.1 Node parameter settings

2.2 性能分析

為了更好地展示算法性能，選取Epidemic算法、PRoPHET算法和OANBM算法，從不同節(jié)點數(shù)量、不同節(jié)點緩存、不同消息存活時間和不同消息產(chǎn)生間隔四方面對路由算法進(jìn)行分析比較.路由算法性能評估指標(biāo)包括：

1)消息投遞率Mdr.仿真時間內(nèi)從源節(jié)點產(chǎn)生并成功送達(dá)到目的節(jié)點的消息數(shù)量Md，與網(wǎng)絡(luò)中產(chǎn)生的所有消息數(shù)量Mt之比.

(7)

2)網(wǎng)絡(luò)負(fù)載率O.網(wǎng)絡(luò)中冗余消息和未送達(dá)消息的數(shù)量Mr-Md(其中Mr表示已轉(zhuǎn)發(fā)的消息數(shù)量)，與送達(dá)消息的數(shù)量Md之比.

(8)

3)平均時延La.每個消息從源節(jié)點發(fā)出到送達(dá)目的節(jié)點所花費的時間L(i)之和，與所有送達(dá)消息的數(shù)量Md之比.

(9)

4)平均跳數(shù)Ha.網(wǎng)絡(luò)中所有消息的跳數(shù)總和Ht，與所有生成的消息數(shù)量Mc之比.

(10)

首先在不同節(jié)點數(shù)量的網(wǎng)絡(luò)環(huán)境下對3種路由算法進(jìn)行了仿真，不同節(jié)點數(shù)量的設(shè)置情況見表2.

表2 不同節(jié)點數(shù)量設(shè)置Tab.2 Different node density settings

2.2.1 節(jié)點數(shù)量對算法性能的影響

圖4中展示了不同節(jié)點數(shù)量時，3種算法的性能表現(xiàn).從圖4(a)中可以看出在節(jié)點數(shù)量較少時，3種算法的消息投遞率比較接近，隨著節(jié)點數(shù)量的增加，Epidemic算法和PRoPHET算法的消息投遞率先有所上升，接著又呈現(xiàn)下降趨勢，維持在0.3左右，而OANBM算法的消息投遞率明顯提高并高于Epidemic算法和PRoPHET算法10%～40%.這是因為節(jié)點數(shù)量越大，節(jié)點之間的交互越多，節(jié)點的耗電量就越大，當(dāng)節(jié)點電量耗盡時無法進(jìn)行傳輸，導(dǎo)致消息投遞率變低.此外，節(jié)點數(shù)量越大，網(wǎng)絡(luò)中產(chǎn)生的冗余消息越多，也會降低消息投遞率.OANBM算法考慮節(jié)點剩余電量并增加了緩存管理機(jī)制，減少了不必要的傳輸和網(wǎng)絡(luò)中的冗余消息，保證了較高的消息投遞率.

從圖4(b)中的結(jié)果可以看出，隨著節(jié)點數(shù)量的增大，3種算法的網(wǎng)絡(luò)負(fù)載率都不斷升高，但OANBM算法的網(wǎng)絡(luò)負(fù)載率明顯低于其他兩種算法，這是因為Epidemic算法和PRoPHET算法在傳輸?shù)倪^程中不斷增加消息副本，而本文提出的算法中引入了緩存管理機(jī)制，有效減少了冗余消息的傳輸.

如圖4(c)中的仿真結(jié)果所示，當(dāng)節(jié)點數(shù)量較少時，OANBM算法和Epidemic算法的平均時延低于PRoPHET算法，當(dāng)節(jié)點數(shù)量增加時，OANBM算法的平均時延介于其他兩種算法之間.總體看來，改進(jìn)后的算法與傳統(tǒng)的PRoPHET算法在平均時延方面的表現(xiàn)大致相同.

圖4 不同節(jié)點數(shù)量仿真Fig.4 Simulation of different node densities

圖4(d)中的結(jié)果表明與Epidemic算法和PRoPHET算法相比，OANBM算法的平均跳數(shù)最小，Epidemic算法的平均跳數(shù)最大.因為Epidemic算法采用泛洪的方式傳輸消息，并沒有對下一跳節(jié)點進(jìn)行選擇，而OANBM算法基于歷史接觸信息及節(jié)點屬性對下一跳節(jié)點進(jìn)行選擇，并且增加了節(jié)點發(fā)送隊列的優(yōu)先級措施，在很大程度上減小了傳輸消息的盲目性因此效果最好.

2.2.2 節(jié)點緩存對仿真算法性能的影響

為了展示節(jié)點緩存大小對路由算法的影響，在節(jié)點數(shù)為150的情況下，按照表3的緩存設(shè)置對3種路由算法進(jìn)行了仿真，仿真結(jié)果如圖5所示.

表3 不同緩存設(shè)置Tab.3 Different cache settings MB

圖5展示了節(jié)點緩存由小變大過程中3種算法的性能表現(xiàn)，從圖5(a)中可以看出隨著節(jié)點緩存的增加，3個路由算法的投遞率先明顯增加，然后又趨于平緩.這是因為節(jié)點緩存越大，節(jié)點所能攜帶的消息就越多，但是當(dāng)節(jié)點緩存增加到可以承載所有消息時，再增加節(jié)點緩存就無法改善網(wǎng)絡(luò)性能了.節(jié)點緩存足夠大時提出的算法投遞率明顯高于其他兩種算法，證明基于節(jié)點屬性選擇下一跳節(jié)點可以有效提高消息投遞率.

圖5(b)顯示了不同算法網(wǎng)絡(luò)負(fù)載率的變化，隨著節(jié)點緩存的增加，節(jié)點緩存大小不再是網(wǎng)絡(luò)性能的限制因素，所以3種算法的網(wǎng)絡(luò)負(fù)載率都呈下降趨勢，而OANBM算法得益于有效的緩存管理機(jī)制，網(wǎng)絡(luò)負(fù)載率明顯低于其他兩種算法.

從圖5(c)中可以看出隨著節(jié)點緩存的增加，節(jié)點所攜帶的消息增多，導(dǎo)致3種算法的平均時延都有所增加，而OANBM算法采用發(fā)送隊列優(yōu)先級的措施，一定程度上可以減輕這種影響.

圖5(d)顯示了不同節(jié)點緩存對平均跳數(shù)的影響，從圖中可以看出OANBM算法明顯優(yōu)于其他兩種算法，證明借助節(jié)點屬性篩選下一跳節(jié)點可以減小平均跳數(shù).

圖5 不同緩存仿真Fig.5 Simulations of different cache settings

2.2.3 消息存活時間對算法性能的影響

將網(wǎng)絡(luò)中的節(jié)點數(shù)設(shè)定為150，節(jié)點緩存設(shè)置為表4中的設(shè)置5，改變消息生存時間，對3種算法進(jìn)行仿真，結(jié)果如圖6所示.

圖6 不同消息存活時間仿真Fig.6 Simulation of different message survival times

從圖6(a)和(b)中可知，在消息生存時間很短的時候，消息的投遞率很低且網(wǎng)絡(luò)負(fù)載很高，這是因為消息還沒有送達(dá)就被銷毀，網(wǎng)絡(luò)中存在大量不能送達(dá)的消息.當(dāng)消息的生存時間很長的時候，網(wǎng)絡(luò)中的冗余消息不會被刪除，增加了網(wǎng)絡(luò)負(fù)載，從而降低了消息投遞率.本文提出的算法可以有效刪除冗余消息，在消息存活時間為7 h時，消息投遞率高于其他兩種算法15%，網(wǎng)絡(luò)負(fù)載率低于其他兩種算法30%.平均時延的表現(xiàn)如圖6(c)所示，3種算法大致相同，增加消息存活時間會直接增加平均時延.從圖6(d)中可以看出增加消息存活時間也會導(dǎo)致平均跳數(shù)的增加，OANBM算法可以有效刪除網(wǎng)絡(luò)中已送達(dá)的消息，并且設(shè)置了消息對列刪除優(yōu)先級，因此表現(xiàn)最好.

2.2.4 消息產(chǎn)生間隔對算法性能的影響

消息產(chǎn)生間隔對算法性能的影響如圖7所示.從圖7(a)和圖7(b)中可以看出，隨著消息產(chǎn)生間隔的增加，網(wǎng)絡(luò)中新生成的消息變少，消息副本的數(shù)量增加，因此消息投遞率變高，網(wǎng)絡(luò)負(fù)載增加.OANBM算法基于節(jié)點屬性和發(fā)送隊列優(yōu)先級傳送消息，并且借助緩存管理機(jī)制刪除冗余消息，所以投遞率最高，負(fù)載率最低.從圖7(c)和圖7(d)中可以看出當(dāng)消息生成間隔很小的時候，OANBM算法可以達(dá)到最低的平均延時和最低的平均跳數(shù)，這是因為OANBM算法加速了新生成消息的傳播，并且及時剔除網(wǎng)絡(luò)中的冗余消息.

圖7 不同消息產(chǎn)生間隔仿真Fig.7 Simulations of different message generation intervals

3 結(jié)論

1)提出了一種基于節(jié)點屬性和緩存管理的機(jī)會網(wǎng)絡(luò)路由算法(OANBM)，該算法在傳統(tǒng)的PRoPHET算法基礎(chǔ)上進(jìn)行改進(jìn)，在選擇下一跳轉(zhuǎn)發(fā)節(jié)點的環(huán)節(jié)上考慮了節(jié)點類型、節(jié)點緩存和節(jié)點電量，并且增加了緩存管理機(jī)制.

2)在模擬的城市交通環(huán)境下對Epidemic、PRoPHET和OANBM算法進(jìn)行分析比較，仿真結(jié)果表明OANBM算法有效提高了消息投遞率，降低了網(wǎng)絡(luò)負(fù)載，并在平均跳數(shù)方面也有良好的表現(xiàn).

未來的工作中將優(yōu)化算法中參數(shù)的設(shè)置，使算法更加完善.