機會網(wǎng)絡(luò)中基于節(jié)點相似率的概率路由算法

崔建群,吳淑慶,常亞楠,黃東升

(華中師范大學(xué) 計算機學(xué)院，武漢 430079)

1 引 言

隨著無線網(wǎng)絡(luò)的快速發(fā)展，機會網(wǎng)絡(luò)[1]成為了近幾年來無線網(wǎng)絡(luò)研究領(lǐng)域的熱點之一.機會網(wǎng)絡(luò)采用存儲-攜帶-轉(zhuǎn)發(fā)的模式進行消息的傳輸，不存在固定的端到端傳輸路徑，不同于傳統(tǒng)網(wǎng)絡(luò).在傳統(tǒng)網(wǎng)絡(luò)中，源節(jié)點和目的節(jié)點處于互不連通的狀態(tài)時無法進行通信.而機會網(wǎng)絡(luò)中，由于節(jié)點不停的進行移動，因此可以將信息攜帶到可以進行互相通信的范圍，完成消息的傳輸.機會網(wǎng)絡(luò)是為了解決實際自組織網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)無法保持長時間連通的情況下的數(shù)據(jù)通信問題，可在沒有固定路由的情況下實現(xiàn)消息的逐跳轉(zhuǎn)發(fā)，最終將消息傳輸?shù)侥康墓?jié)點.

目前機會網(wǎng)絡(luò)的可應(yīng)用場景也越來越多.例如，在災(zāi)難應(yīng)急[2]，車載網(wǎng)絡(luò)[3，4]以及星際網(wǎng)絡(luò)[5]等領(lǐng)域都具有非常廣闊的市場前景和應(yīng)用價值.

機會網(wǎng)絡(luò)中的節(jié)點普遍具有較高的移動性，而且機會網(wǎng)絡(luò)具備連接間歇性，網(wǎng)絡(luò)延遲大等特點，因此尋求合適的中繼節(jié)點將消息準確快速的投遞到目的節(jié)點，是路由算法中最迫切關(guān)注的問題.傳統(tǒng)的基于歷史預(yù)測策略的概率路由(Probabilistic routing Protocol using history of encounters & transitivity,Prophet)[6]算法，沒有考慮節(jié)點的相遇持續(xù)時間，只是利用節(jié)點相遇頻率作為傳遞概率，這未免考慮不夠周全，同時Prophet沒有對成功傳遞的消息進行有效的控制，從而導(dǎo)致存在很多已經(jīng)被成功投遞的消息仍然存在網(wǎng)絡(luò)中，使得網(wǎng)絡(luò)開銷過大，同時成功投遞的消息仍然存在節(jié)點中，在節(jié)點緩存較小的情況下，這些成功投遞的消息占用過多的節(jié)點緩存，導(dǎo)致節(jié)點無法接收新消息.本文將結(jié)合Prophet算法，分析其存在的問題，提出了一種基于節(jié)點相似率的概率路由算法(Probabilistic routing algorithm based on node similarity rate in opportunistic network，S-Prophet)算法，引入節(jié)點相似率進行消息傳遞概率的設(shè)計，并添加ACK確認機制刪除成功投遞的消息，以減輕節(jié)點緩存的負擔(dān)，減少網(wǎng)絡(luò)開銷，從一定程度上彌補了Prophet算法概率計算不準確，以及節(jié)點緩存被成功投遞的消息過多占用的問題.

2 相關(guān)工作

機會網(wǎng)絡(luò)中經(jīng)典算法有Direct Delivery[7]、Epidemic[8]以及Prophet等.

Direct Delivery(直接傳輸)算法的主要思想是，源節(jié)點只有與目的節(jié)點相遇的時候，才將消息進行轉(zhuǎn)發(fā)給對方.Direct Delivery是一種單拷貝路由方式，其優(yōu)點是簡單直接，缺點是消息完全依賴源節(jié)點和目的節(jié)點的相互通信，若源節(jié)點始終無法遇到目的節(jié)點，則消息將永遠無法送達目的節(jié)點.由于機會網(wǎng)絡(luò)中節(jié)點是不斷移動的，這將導(dǎo)致消息的延遲較大，消息容易在生存周期過期后仍無法傳遞到目的節(jié)點，從而導(dǎo)致較低的投遞成功率.Epidemic算法則相反，通過提高副本傳播的數(shù)量來提高數(shù)據(jù)成功率，不管相遇節(jié)點是否為目的節(jié)點，攜帶消息的節(jié)點都會將消息傳遞給與其相遇的所有節(jié)點，鄰居節(jié)點繼續(xù)通過這種方式進行下一步的傳遞.這種方式解決了Direct Delivery算法中依賴于源節(jié)點與目的節(jié)點相遇才將消息轉(zhuǎn)發(fā)的問題，但是帶來了另外一個問題，網(wǎng)絡(luò)中存在大量冗余消息，很快便造成網(wǎng)絡(luò)擁塞節(jié)點緩存負擔(dān)過大，甚至有可能導(dǎo)致網(wǎng)絡(luò)癱瘓.

Prophet算法是通過總結(jié)節(jié)點間歷史相遇的規(guī)律來預(yù)測未來的傳輸路徑，其主要工作在于提出了節(jié)點間成功傳輸消息概率的一個指標——投遞預(yù)測值(deliver probability).與傳染病路由算法(Epidemic)相比，當(dāng)兩個節(jié)點Va和Vb相遇時，不僅要交換兩者的向量外，而且要交換投遞預(yù)測值，只有在Va到目的節(jié)點的投遞預(yù)測值大于Vb到目的節(jié)點的投遞預(yù)測值時才將消息傳遞給節(jié)點Vb.本文將使用投遞概率代表投遞預(yù)測值這一概念.

投遞概率的計算通常分3種情況討論：更新、衰退以及傳遞性.當(dāng)且僅當(dāng)節(jié)點間相遇時，根據(jù)不同情況更新概率預(yù)測值.

更新：當(dāng)節(jié)點Va和節(jié)點Vb相遇，根據(jù)公式(1)更新它們之間的投遞概率，其中Pinit∈[0,1]，是一個人為規(guī)定的常數(shù)，是節(jié)點間傳輸率的初始值.

P(a,b)=P(a,b)old+(1-P(a,b)old)×Pinit

(1)

衰減：若節(jié)點Va和節(jié)點Vb在某段時間內(nèi)未相遇，那么他們再次相遇的概率將降低，其投遞概率的值按照公式(2)來進行計算：

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

(2)

公式中的γ是衰減參數(shù)，k則是表示從最后一次相遇到當(dāng)前時間所經(jīng)歷的時間塊的個數(shù)，γ∈[0,1]是常數(shù).

傳遞性：節(jié)點概率的傳遞性是指不但節(jié)點Va經(jīng)常遇到節(jié)點Vb，而且節(jié)點Vb也能經(jīng)常遇到節(jié)點Vc，那節(jié)點Vc可能是轉(zhuǎn)發(fā)消息到達目標節(jié)點Va的比較好的中轉(zhuǎn)節(jié)點.節(jié)點間的概率傳遞性計算如公式(3)所示，其中β∈[0,1]是常數(shù)，它的大小是衡量傳遞性對投遞預(yù)測概率的影響的一個重要指標.

P(a,c)=P(a,c)old+(1-P(a,c)old)×P(a,b)×P(b,c)×β

(3)

通過總結(jié)節(jié)點間歷史相遇的規(guī)律來預(yù)測未來的傳輸路徑，通過計算投遞概率，選取概率大的節(jié)點作為中繼節(jié)點，一定程度上避免了Epidemic算法在選擇中繼節(jié)點的盲目性.但Prophet算法沒有考慮節(jié)點的相遇持續(xù)時間，只是利用節(jié)點相遇頻率作為傳遞概率，這未免考慮不夠周全.同時，Prophet算法沒有對成功傳遞的消息進行有效的控制，從而導(dǎo)致存在很多已經(jīng)被成功投遞的消息仍然存在網(wǎng)絡(luò)中，使得網(wǎng)絡(luò)開銷過大，同時成功投遞的消息仍然存在節(jié)點中，在節(jié)點緩存較小的情況下，這些成功投遞的消息占用過多的節(jié)點緩存，導(dǎo)致節(jié)點無法接收新消息.

近年來，對于Prophet算法的改進有很多種形式.段宗濤[9]等提出概率路由中基于連接時間的機會轉(zhuǎn)發(fā)算法，該算法考慮了相遇持續(xù)時間，在設(shè)計節(jié)點投遞概率時增加了節(jié)點間連接時間占空比的影響因素，并未討論緩存管理對投遞率的影響.張峰[10]等針對上述問題進一步研究，在節(jié)點投遞概率計算部分引入相遇持續(xù)時間重新設(shè)計概率計算公式，在選擇中繼節(jié)點時，雖然考慮了節(jié)點緩存對投遞概率的影響，但是沒有對已經(jīng)成功投遞的消息進行刪除，未能從根本上解決當(dāng)節(jié)點緩存被占用過大時，無法有效轉(zhuǎn)發(fā)消息的問題.馬慧[11]等提出基于節(jié)點的歷史吞吐率的 Prophet 路由策略，在消息傳遞的過程中，在與目標節(jié)點相遇概率相同的節(jié)點中選擇吞吐率較大的節(jié)點作為中繼節(jié)點.雖然該算法考慮了消息傳遞過程中節(jié)點的吞吐率問題，但是在計算吞吐率的時候未能考慮到時間片對吞吐率的影響，因此在消息投遞率上并未有明顯提高.

本文在此基礎(chǔ)上，提出了一種基于節(jié)點相似率的概率路由算法.在計算消息轉(zhuǎn)發(fā)概率時考慮了節(jié)點歷史相遇情況，引入了節(jié)點相似率的定義.由于在預(yù)估兩個節(jié)點的投遞概率的時候，Prophet算法中使用的參數(shù)Pinit是固定的，不能真實反映兩個節(jié)點之間的動態(tài)變化關(guān)系，本文將使用節(jié)點相似率來對概率公式(1)中的參數(shù)Pinit進行設(shè)計，關(guān)于節(jié)點相似率的定義將在3.2節(jié)進行闡述.同時，使用節(jié)點相遇持續(xù)時間對衰減公式(2)中γk的參數(shù)k進行重新設(shè)計，為了減少傳輸成功的消息副本對網(wǎng)絡(luò)資源的占用，本文采用了ACK刪除機制，來保證及時清除已經(jīng)傳輸成功的消息副本，然后使用ONE仿真平臺進行實驗，對比改進前后算法之間的性能.

3 機會網(wǎng)絡(luò)中基于節(jié)點相似率的概率路由算法

3.1 基于節(jié)點相似率的概率路由算法S-Prophet

定義1.節(jié)點相遇持續(xù)時間

節(jié)點相遇持續(xù)時間為兩個節(jié)點之間建立連接后進行通信所持續(xù)的時間，在機會網(wǎng)絡(luò)中由于節(jié)點是移動的，因此造成節(jié)點之間每次相遇后進行通信所持續(xù)時間可能不同，在本文中，統(tǒng)計每個節(jié)點與其他節(jié)點之間建立連接通信的次數(shù)，以及總相遇持續(xù)時間，如圖1所示.

假設(shè)節(jié)點Va與節(jié)點Vb總共建立連接n次，則它們之間的總相遇持續(xù)時間為:

T(a,b)=T1+T2+…+Tn-1

(4)

(5)

其中，T為時間間隔周期，T(a,b)表示節(jié)點Va和節(jié)點Vb總的相遇持續(xù)時間.

圖1 節(jié)點相遇持續(xù)時間統(tǒng)計Fig.1 Node encounter duration statistics

定義2.節(jié)點的相似率

節(jié)點Va和節(jié)點Vb的相似率是指節(jié)點Va與節(jié)點Vb擁有的共同相遇節(jié)點個數(shù)與它們兩個節(jié)點分別相遇的節(jié)點總數(shù)的比值.令集合Na={Vc|na,c≠0,1≤c≤n}表示節(jié)點Va在時間間隔周期T內(nèi)所遇到的相遇節(jié)點集合，其中na,c表示節(jié)點Va與節(jié)點Vc的相遇次數(shù)，其初始值為0，每當(dāng)節(jié)點Va與節(jié)點Vc相遇，則次數(shù)加1.同理集合Nb表示節(jié)點Vb在時間間隔周期T內(nèi)的相遇節(jié)點集合.當(dāng)統(tǒng)計的時間超過時間間隔T則會將原先的集合清空并重新開始統(tǒng)計，節(jié)點Va與節(jié)點Vb的相似率計算方法見公式(6)：

(6)

本文使用公式(7)作為兩個節(jié)點之間的傳輸概率公式，不再使用公式(1).

圖2 節(jié)點相似率的統(tǒng)計Fig.2 Statistics of node similarity rate

(7)

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

接下來我們將介紹S-Prophet路由算法的消息轉(zhuǎn)發(fā)步驟以及消息轉(zhuǎn)發(fā)流程.

消息轉(zhuǎn)發(fā)流程，如圖3所示.

步驟1.在攜帶消息的節(jié)點Va遇到節(jié)點Vb時，首先要判斷Vb是否為目的節(jié)點，是則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟2.

圖3 基于節(jié)點相似率的概率路由算法消息轉(zhuǎn)發(fā)流程Fig.3 Probability routing algorithm based on node similarity rate message forwarding process

步驟2.計算節(jié)點Va遇到節(jié)點Vb同目的節(jié)點之間的相遇概率.

步驟3.要判斷節(jié)點Vb和目的節(jié)點的概率P(Vb)是否大于節(jié)點Va和目的節(jié)點的概率P(Va)，是則轉(zhuǎn)步驟4，否則結(jié)束.

步驟4.將消息轉(zhuǎn)發(fā)給節(jié)點Vb，結(jié)束.

表1 S-Prophet算法Table 1 S-Prophet algorithm

表1中算法第1行表示任意兩個節(jié)點Va與Vb相遇并且建立連接，算法第2行，記錄節(jié)點Va與節(jié)點Vb相遇的開始時間，算法3～7行進行判斷，如果節(jié)點Va與Vb的相遇時間間隔大于設(shè)定的時間周期閾值T，則將Va的相遇節(jié)點列表清空，否則將該相遇節(jié)點添加到相遇節(jié)點列表中.因為本文只記錄時間周期T內(nèi)的相遇節(jié)點信息.算法第8行，記錄節(jié)點Va與Vb斷開連接的時間.算法第12行，統(tǒng)計集合Na和Nb中節(jié)點相遇持續(xù)時間.算法第13行，計算集合中節(jié)點相似率.算法第14行，根據(jù)節(jié)點相似率來進行節(jié)點投遞率的計算，在計算之前會根據(jù)節(jié)點相遇持續(xù)時間先更新節(jié)點衰減概率.算法第15行，計算節(jié)點傳遞概率.算法第17～21行，遍歷節(jié)點轉(zhuǎn)發(fā)列表，根據(jù)節(jié)點傳遞概率將消息轉(zhuǎn)發(fā)給比當(dāng)前節(jié)點概率大的節(jié)點.由于本算法需要進行節(jié)點相遇持續(xù)時間的統(tǒng)計以及節(jié)點相似率計算，因此本算法時間主要耗費在11～16行，假設(shè)共有n個節(jié)點，則S-Prophet算法的時間復(fù)雜度為O(n2).

3.3 ACK刪除機制

為了減少冗余副本在網(wǎng)絡(luò)長時間保留造成節(jié)點緩存占用過多的不良影響，降低網(wǎng)絡(luò)開銷，本文將使用ACK刪除機制來刪除已經(jīng)成功傳遞的消息副本.給每個節(jié)點設(shè)置一個ACK列表，當(dāng)消息成功傳輸?shù)侥康墓?jié)點時，該消息就被加入到ACK列表中，當(dāng)兩個節(jié)點相遇時，交換它們的ACK列表，然后從緩存中刪除對應(yīng)的消息.具體算法如表2所示，算法第1～3行表示，當(dāng)消息成功投遞之后，判斷消息是否已經(jīng)到達目的節(jié)點，如果消息到達目的節(jié)點，則將消息添加到ackMessage列表中.算法4～9行表示當(dāng)任意兩個節(jié)點Va與節(jié)點Vb相遇，首先互相交換其ackMessage列表中的信息，然后刪除ackMessage列表中已經(jīng)被成功投遞到目的節(jié)點的消息.假設(shè)ackMessage列表中的消息共有n個，則本文的ACK刪除機制時間復(fù)雜度為O(n).

表2 ACK刪除機制Table 2 ACK deletion mechanism

4 仿真實驗及結(jié)果分析

4.1 仿真的參數(shù)設(shè)置

本文的所有實驗都是采用機會網(wǎng)絡(luò)環(huán)境仿真平臺ONE(Opportunistic Network Environment)來進行，本文對經(jīng)典路由算法Epidemic、Prophet以及本文算法S-Prophet利用ONE仿真平臺分別從節(jié)點緩存空間、消息生存周期、仿真時間、消息產(chǎn)生間隔4個不同角度對算法性能的影響進行比較分析，主要將消息投遞率、傳輸延遲、平均跳數(shù)、網(wǎng)絡(luò)開銷作為路由算法的衡量指標，表3為本文仿真時設(shè)置的具體參數(shù).

表3 仿真參數(shù)設(shè)置Table 3 Simulation parameter setting

4.2 仿真結(jié)果分析

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

圖4是3種算法的路由性能隨著節(jié)點緩存空間的變化情況，從圖中可以看出本文提出的S-Prophet路由算法在投遞率、網(wǎng)絡(luò)開銷和平均跳數(shù)及傳輸延遲等方面都取得了較好的仿真結(jié)果，從而證實了考慮節(jié)點間相似率在路由選擇方面發(fā)揮的主觀作用.圖4(a)的仿真結(jié)果表明，當(dāng)節(jié)點緩存為2MB時，S-Prophet算法比Prophet算法提高了20%，比Epidemic算法提高了66%.當(dāng)節(jié)點緩存為10MB時，S-Prophet算法比Prophet算法提高了58%，比Epidemic算法提高了48%.隨著緩存空間的增加，Epidemic、Prophet、S-Prophet算法的消息投遞率一直在持續(xù)增長，由于緩存空間的增加，可攜帶的消息也增多，從而提高了總的消息成功投遞率.

圖4 節(jié)點緩存對算法性能的影響Fig.4 Effect of node caching on algorithm performance

圖4(b)中的仿真結(jié)果表明，當(dāng)節(jié)點緩存從2MB變化到4MB時，3種算法的傳輸延遲都有降低，特別是S-Prophet算法有明顯的降低，這是因為在緩存為2MB時，S-Prophet需要統(tǒng)計節(jié)點的相遇記錄用于計算節(jié)點相似率，會因此占用一部分節(jié)點緩存，從而導(dǎo)致消息傳輸延遲會比較高.當(dāng)節(jié)點緩存從4MB開始增加到10MB的過程中，S-Prophet算法傳輸延遲逐漸增加，但仍然比Epidemic、Prophet要低，這是因為在S-Prophet算法中利用了節(jié)點相似率改進了兩個節(jié)點間傳輸概率更合理的決策出下一跳中繼節(jié)點.

圖4(c)的仿真結(jié)果表明，S-Prophet路由算法在網(wǎng)絡(luò)開銷方面表現(xiàn)最優(yōu)，S-Prophet比Epidemic要小83%～85%，比Prophet要小64%～81%，這是因為在S-Prophet算法中不僅增加了節(jié)點相似率作為節(jié)點傳輸概率的影響因素，而且增加了ACK刪除機制，有效的減少了網(wǎng)絡(luò)中冗余副本的數(shù)量，從而降低了網(wǎng)絡(luò)開銷.

從圖4(d)中可以看出，當(dāng)緩存空間加大時，消息在網(wǎng)絡(luò)中的平均傳輸跳數(shù)會隨此降低，這是因為節(jié)點可存放的消息數(shù)量增多.對于Epidemic越有利，對S-Prophet和Prophet算法的平均跳數(shù)影響并不大.其中S-Prophet算法始終維持在2～3跳之間，而Prophet算法始終維持在3～4跳之間.跳數(shù)越少說明路由算法更有效，從圖中可以直觀看出S-Prophet算法性能略優(yōu)于Prophet，因為S-Prophet在選擇下一跳的指標上利用到了節(jié)點相似率這一因素.

4.2.2 消息生存周期對算法性能的影響

圖5描述了各個算法在不同消息生存周期下的路由表現(xiàn).從圖5(a)中可以看出，隨著消息生存周期從100min增加

圖5 消息生存周期對算法性能的影響Fig.5 Effect of message lifetime on algorithm performance

到300min的過程中，Epidemic算法和Prophet算法的投遞率在降低，這是因為當(dāng)節(jié)點緩存空間較小的情況下，如果消息生存周期比較高，會使大量已經(jīng)成功投遞的消息仍然存在網(wǎng)絡(luò)中，這對于Epidemic和Prophet算法來說是非常不利的，Epidemic和Prophet算法并沒有采取有效的措施來控制消息冗余數(shù)量，不可避免的產(chǎn)生更多的消息副本，而S-Prophet算法的投遞率在逐漸上升，且S-Prophet算法的投遞率在消息生存周期大于150min之后一直比Prophet和Epidemic算法的投遞率高，這是因為在S-Prophet算法中有ACK刪除機制，一定程度上減少了冗余副本的數(shù)量，從而提高消息投遞率.此外，從圖5可以看出，隨著消息生存周期的增加，S-Prophet算法仍然保持了它在傳輸延遲、平均跳數(shù)、網(wǎng)絡(luò)開銷上的優(yōu)勢，均低于Prophet算法和Epidemic算法.

4.2.3 仿真時間對算法性能的影響

圖6描述了各個算法在不同仿真時間下的路由表現(xiàn).從圖6(a)中可以看到，在隨著仿真時間的增多，S-Peophet、Prophet以及Epidemic算法的投遞率也在逐漸的提高，但是當(dāng)仿真時間為8h的時候，S-Prophet算法已經(jīng)達到飽和狀態(tài)，本文所提出的S-Prophet算法相較于Epidemic算法和Prophet算法更為穩(wěn)定，且S-Prophet算法的投遞率一直高于其他兩種算法.在仿真時間為6h的時候，S-Prophet算法比Epidemic算法的投遞率高53.2%，比Prophet算法的投遞率高65%，當(dāng)仿真時間達到8h的時候，S-Prophet算法比Epidemic算法投遞率高53.3%，比Prophet算法投遞率高74%.

圖6 仿真時間對算法性能的影響Fig.6 Influence of simulation time on algorithm performance

從圖6(b)中可以看出，當(dāng)仿真時間在6h時候，S-Prophet算法的傳輸延遲介于Prophet與Epidemic之間，當(dāng)仿真時間從10h開始，S-Prophet算法的傳輸延遲就一直低于Prophet與Epidemic，這是由于隨著仿真時間的增加，S-Prophet算法收集到的節(jié)點信息越來越多，更能夠準確的預(yù)估下一跳節(jié)點，將消息準確送達目的地.

從圖6(c)中可以看出，隨著仿真時間的增加，S-Prophet算法的網(wǎng)絡(luò)開銷越來越低，且均低于25，而Prophet算法和Epidemic算法兩者都比較高，雖然Prophet算法網(wǎng)絡(luò)開銷比Epidemic的要稍微低一些，但是由于Prophet算法沒有進行消息冗余控制，因而S-Prophet算法在路由性能的表現(xiàn)上更具優(yōu)勢.

從圖6(d)中可以看出，隨著仿真時間的增S-Prophet算法的平均跳數(shù)均在3以下，而Prophet算法與Epidemic算法的平均跳數(shù)均在3～4之間，平均跳數(shù)越少，說明路由性能越好.

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

圖7比較了改變消息產(chǎn)生間隔時各個算法的4項評估指標.在不考慮消息傳輸延遲的情況下，從圖7(a)中可以看出，S-Prophet算法的路由性能是最優(yōu)的，且穩(wěn)定的保持較高的消息投遞率，而Epidemic和Prophet算法投遞率都比較低，且兩者都比較接近.S-Prophet算法的投遞率比Epidemic的高53%～57%，比Prophet的高62%～67%.從圖7(b)中可以看出，在傳輸延遲方面，S-Prophet算法與Prophet相比，在消息產(chǎn)生間隔為60s～70s的過程中兩者較為接近，當(dāng)消息產(chǎn)生間隔為75s時，S-Prophet的傳輸延遲比Prophet要低，而此時Prophet的傳輸延遲比Epidemic高，就圖7(b)圖而言，總體來說S-Prophet的傳輸延遲始終比Epidemic要低.

圖7 消息產(chǎn)生間隔對算法性能的影響Fig.7 Influence of message generation interval on algorithm performance

從圖7(c)和圖7(d)中可以看出，S-Prophet算法的性能更加穩(wěn)定，網(wǎng)絡(luò)開銷和平均跳數(shù)一直保持較低水平，其網(wǎng)絡(luò)開銷只有Epidemic的17%、Prophet的19%.導(dǎo)致這些路由性能差異的關(guān)鍵原因是，在消息生存時間間隔較小的情況下，整個網(wǎng)絡(luò)會產(chǎn)生較多的消息，由于缺乏控制消息冗余的機制和受限的緩存空間，Epidemic會丟棄大量的消息包，Prophet利用節(jié)點間傳輸概率來篩選更有的中繼節(jié)點，一定程度上比Epidemic的盲目性要好一些，因而路由性能上要由于Epidemic，但仍然要弱于S-Prophet.因為S-Prophet借助節(jié)點相似率來設(shè)計節(jié)點傳輸概率，從而篩選出更好的中繼節(jié)點，以此獲得了更好的路由性能，并且通過ACK刪除機制，有效避免過多的冗余消息副本，從而提高網(wǎng)絡(luò)資源的利用率.

5 結(jié)束語

本文結(jié)合Prophet路由算法的優(yōu)勢，針對其中存在的問題，提出了一種考慮相遇節(jié)點歷史連接情況以及ACK確認機制的路由算法，并進行了仿真實驗.實驗證明，相對于傳統(tǒng)的Prophet算法和Epidemic算法而言，本文提出的S-Prophet算法在路由性能上更好一些，但仍然存在一些不足的地方，比如整體而言，傳輸延遲均偏大，在這方面仍有較大的改進空間，這是下一步研究工作的重點.