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

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

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

1 引 言

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

(1)

衰減：若節(jié)點(diǎn)Va和節(jié)點(diǎn)Vb在某段時(shí)間內(nèi)未相遇，那么他們?cè)俅蜗嘤龅母怕蕦⒔档停渫哆f概率的值按照公式(2)來(lái)進(jìn)行計(jì)算：

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

(2)

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

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

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

(3)

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

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

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

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

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

定義1.節(jié)點(diǎn)相遇持續(xù)時(shí)間

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

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

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

(4)

(5)

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

圖1 節(jié)點(diǎn)相遇持續(xù)時(shí)間統(tǒng)計(jì)Fig.1 Node encounter duration statistics

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

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

(6)

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

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

(7)

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

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

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

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

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

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

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

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

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

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

3.3 ACK刪除機(jī)制

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

表2 ACK刪除機(jī)制Table 2 ACK deletion mechanism

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

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

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

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

4.2 仿真結(jié)果分析

4.2.1 節(jié)點(diǎn)緩存對(duì)算法性能的影響

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

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

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

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

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

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

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

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

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

4.2.3 仿真時(shí)間對(duì)算法性能的影響

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

圖6 仿真時(shí)間對(duì)算法性能的影響Fig.6 Influence of simulation time on algorithm performance

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

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

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

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

圖7比較了改變消息產(chǎn)生間隔時(shí)各個(gè)算法的4項(xiàng)評(píng)估指標(biāo).在不考慮消息傳輸延遲的情況下，從圖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的過(guò)程中兩者較為接近，當(dāng)消息產(chǎn)生間隔為75s時(shí)，S-Prophet的傳輸延遲比Prophet要低，而此時(shí)Prophet的傳輸延遲比Epidemic高，就圖7(b)圖而言，總體來(lái)說(shuō)S-Prophet的傳輸延遲始終比Epidemic要低.

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

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

5 結(jié)束語(yǔ)

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