DTN中基于節(jié)點(diǎn)綜合性能的自適應(yīng)噴射等待路由算法

崔建群 孫佳悅 常亞楠 余東海 鄔 堯 吳黎兵

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

2(武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院 武漢 430072)

(jqcui@126.com)

延遲容忍網(wǎng)絡(luò)(delay tolerant network, DTN)是一種在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間難以形成穩(wěn)定的端到端連接鏈路、利用節(jié)點(diǎn)移動(dòng)帶來的相遇機(jī)會(huì)進(jìn)行通信的自組織網(wǎng)絡(luò)[1].正是由于DTN的這種通信特點(diǎn)，其采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的路由機(jī)制[2]，消息由中間節(jié)點(diǎn)攜帶并隨其移動(dòng)，直至到達(dá)目標(biāo)節(jié)點(diǎn).DTN適用于大傳輸時(shí)延、間歇性連接、高誤碼率的極限通信環(huán)境，在災(zāi)難應(yīng)急[3]、車載網(wǎng)絡(luò)[4]、星際網(wǎng)絡(luò)[5]、手持設(shè)備組網(wǎng)[6]等領(lǐng)域具有廣泛的應(yīng)用前景，并將成為未來普適計(jì)算和泛在網(wǎng)絡(luò)的重要接入技術(shù).因此DTN被認(rèn)為是實(shí)現(xiàn)“無處不在的網(wǎng)絡(luò)”的一項(xiàng)關(guān)鍵技術(shù)，具有重要的研究意義.

在DTN路由算法中，SaW(spray and wait)[7]算法能夠在控制消息副本的前提下實(shí)現(xiàn)消息的高效投遞.該算法在Spray(噴射)階段采用對(duì)稱分配消息副本數(shù)，在Wait(等待)階段進(jìn)行消息的被動(dòng)傳輸.文獻(xiàn)[7]證明了在獨(dú)立同分布的節(jié)點(diǎn)移動(dòng)模型中SaW算法是最優(yōu)的，但是在大多數(shù)情況下并不存在嚴(yán)格的獨(dú)立同分布移動(dòng)模型，因此SaW算法仍然有較大的改進(jìn)空間.

目前對(duì)SaW算法的改進(jìn)主要體現(xiàn)在3個(gè)方面：1)在Spray階段篩選中繼節(jié)點(diǎn)，根據(jù)效用函數(shù)選擇高效的候選節(jié)點(diǎn)作為下一跳，有利于提高消息投遞率[8]；2)在Spray階段噴射適當(dāng)比例的副本，根據(jù)不同節(jié)點(diǎn)的質(zhì)量和表現(xiàn)，分配不同的副本數(shù)量，使副本快速擴(kuò)散，有效傳遞[9-10]；3)改進(jìn)Wait階段的傳輸策略[11].然而，目前大多數(shù)SaW改進(jìn)算法只是根據(jù)其中的1個(gè)或2個(gè)方面進(jìn)行研究，很少考慮將這3個(gè)方面綜合起來對(duì)SaW進(jìn)行改進(jìn)，性能提高并不明顯.

基于以上分析，本文將中繼節(jié)點(diǎn)選擇、自適應(yīng)分配消息副本數(shù)量以及Wait階段的改進(jìn)綜合考慮進(jìn)來，提出一種基于節(jié)點(diǎn)綜合性能的自適應(yīng)噴射等待路由算法(adaptive spray and wait routing algorithm based on comprehensive performance of node, CPN-ASW).主要貢獻(xiàn)有5個(gè)方面：

1) 定義了節(jié)點(diǎn)相似度來反映節(jié)點(diǎn)運(yùn)動(dòng)軌跡的相似程度，利用節(jié)點(diǎn)相似度控制消息轉(zhuǎn)發(fā)條件，避免消息在運(yùn)動(dòng)軌跡相似的節(jié)點(diǎn)間傳輸，網(wǎng)絡(luò)開銷增大，投遞率無明顯變化情況的發(fā)生.

2) 引入節(jié)點(diǎn)活躍度概念來反映節(jié)點(diǎn)與其他節(jié)點(diǎn)的相遇能力，從而將較多的消息副本分配給活躍度高的節(jié)點(diǎn)，使消息能夠在短時(shí)間內(nèi)擴(kuò)散至較多的節(jié)點(diǎn)上.另外，采用劃分等長(zhǎng)的時(shí)間窗口來更加準(zhǔn)確地估計(jì)節(jié)點(diǎn)活躍度.

3) 結(jié)合節(jié)點(diǎn)活躍度和剩余緩存，提出節(jié)點(diǎn)相對(duì)效用值的概念.根據(jù)節(jié)點(diǎn)間的相對(duì)效用值自適應(yīng)分配消息副本數(shù)，給活躍度高、剩余緩存多的節(jié)點(diǎn)分配更多的消息副本，使消息在網(wǎng)絡(luò)中擴(kuò)散得更廣，進(jìn)而提高消息到達(dá)目標(biāo)節(jié)點(diǎn)的可能性.

4) 在Spray階段提出基于節(jié)點(diǎn)相似度和節(jié)點(diǎn)相對(duì)效用值的噴射策略，使在副本受限的情況下，消息得到有效擴(kuò)散.

5) 在Wait階段充分利用節(jié)點(diǎn)間的相遇機(jī)會(huì)，提出基于節(jié)點(diǎn)投遞預(yù)測(cè)值的主動(dòng)轉(zhuǎn)發(fā)策略，進(jìn)一步降低傳輸時(shí)延.

1 相關(guān)工作

目前，在DTN的研究中，路由算法主要分為單拷貝路由協(xié)議和多拷貝路由協(xié)議.典型的單拷貝路由協(xié)議有Direct Delivery[12]和First Contact[12].這2種路由協(xié)議網(wǎng)絡(luò)開銷小，但是傳輸時(shí)延很高，且消息成功到達(dá)目標(biāo)節(jié)點(diǎn)的概率很低.多拷貝路由協(xié)議中最具代表性路由協(xié)議有Epidemic[13]和Prophet[14].Epidemic是一種洪泛式路由算法，攜帶消息的節(jié)點(diǎn)向遇到的每一個(gè)節(jié)點(diǎn)都復(fù)制消息，其在網(wǎng)絡(luò)資源較充足的條件下投遞率較高，且傳輸時(shí)延低，但是在真實(shí)的網(wǎng)絡(luò)場(chǎng)景中，網(wǎng)絡(luò)資源往往受限，其盲目復(fù)制會(huì)導(dǎo)致網(wǎng)絡(luò)開銷巨大，最終降低網(wǎng)絡(luò)性能；Prophet算法利用節(jié)點(diǎn)間相遇歷史信息和傳遞性定義一個(gè)投遞預(yù)測(cè)值指標(biāo)來描述節(jié)點(diǎn)之間成功傳輸消息的概率，每當(dāng)2個(gè)節(jié)點(diǎn)相遇時(shí)，選擇到達(dá)目標(biāo)節(jié)點(diǎn)投遞預(yù)測(cè)值更高的節(jié)點(diǎn)作為消息中繼節(jié)點(diǎn)，但是Prophet本質(zhì)上仍是消息復(fù)制路由，相比Epidemic網(wǎng)絡(luò)開銷明顯減小，但由于進(jìn)行中繼節(jié)點(diǎn)篩選，消息到達(dá)目標(biāo)節(jié)點(diǎn)時(shí)延較大.

為了將Epidemic算法消息投遞的高效性與單副本直接傳輸?shù)暮?jiǎn)潔性相結(jié)合，相關(guān)研究者提出了SaW路由算法.該路由算法由Spray和Wait這2個(gè)階段組成，消息產(chǎn)生后，通過初始化消息副本數(shù)量來顯示消息轉(zhuǎn)發(fā)次數(shù).SaW算法采用了2種模式，即Binary和非Binary模式.Binary模式下，在Spray階段，攜帶某消息副本數(shù)大于1的節(jié)點(diǎn)向遇到的未緩存該消息的節(jié)點(diǎn)轉(zhuǎn)發(fā)此消息一半副本，自身保留剩下的消息副本；當(dāng)節(jié)點(diǎn)中某消息副本數(shù)為1時(shí)，節(jié)點(diǎn)轉(zhuǎn)入Wait階段，消息以Direct Delivery的方式進(jìn)行傳輸，即攜帶消息的節(jié)點(diǎn)直至遇到目標(biāo)節(jié)點(diǎn)才將消息轉(zhuǎn)發(fā)出去.Binary SaW可應(yīng)用于多類場(chǎng)景中，其綜合性能要高于Epidemic和Prophet.該算法適用于節(jié)點(diǎn)均等分布、運(yùn)動(dòng)隨機(jī)的延遲容忍網(wǎng)絡(luò)，然而在真實(shí)的網(wǎng)絡(luò)環(huán)境中，節(jié)點(diǎn)運(yùn)動(dòng)不完全隨機(jī)，且節(jié)點(diǎn)將消息傳輸?shù)侥繕?biāo)節(jié)點(diǎn)的能力是不同的，因此，SaW算法在Spray階段的對(duì)稱分配副本數(shù)是不靈活的，并且在Wait階段的被動(dòng)傳輸會(huì)進(jìn)一步增加傳輸時(shí)延.針對(duì)SaW算法的主要弊端，目前國內(nèi)外研究者已在SaW的改進(jìn)上取得了一些成果.

文獻(xiàn)[8]對(duì)Prophet算法中定義的投遞預(yù)測(cè)值做了進(jìn)一步改進(jìn)，節(jié)點(diǎn)間的投遞預(yù)測(cè)值不僅考慮相遇次數(shù)，還結(jié)合了節(jié)點(diǎn)間的連接時(shí)間.在Spray階段根據(jù)消息到目標(biāo)節(jié)點(diǎn)的投遞預(yù)測(cè)值篩選中繼節(jié)點(diǎn)，Wait階段同樣執(zhí)行此操作，直至消息到達(dá)目標(biāo)節(jié)點(diǎn).文獻(xiàn)[9]結(jié)合節(jié)點(diǎn)的投遞預(yù)測(cè)值和節(jié)點(diǎn)相似度作為節(jié)點(diǎn)效用值，按照此效用值自適應(yīng)分配副本數(shù).文獻(xiàn)[10]提出基于節(jié)點(diǎn)歷史相遇信息的路由算法EBR，該算法直接根據(jù)節(jié)點(diǎn)活躍度自適應(yīng)地分配消息副本數(shù)，將更多的消息副本分配給活躍度更高的節(jié)點(diǎn).文獻(xiàn)[15]提出一種基于節(jié)點(diǎn)社會(huì)性的噴霧等待路由協(xié)議BSW-SN，該算法在Spray階段根據(jù)節(jié)點(diǎn)的移動(dòng)模式和節(jié)點(diǎn)對(duì)消息的轉(zhuǎn)發(fā)效能來優(yōu)化對(duì)中繼節(jié)點(diǎn)的選擇，然后按照節(jié)點(diǎn)的活躍度自適應(yīng)分配消息副本數(shù).文獻(xiàn)[16]提出一種基于節(jié)點(diǎn)質(zhì)量度的路由算法QoN-ASW，在Spray階段考慮節(jié)點(diǎn)的質(zhì)量度作為消息副本分配的依據(jù)；在Wait階段將消息轉(zhuǎn)發(fā)給到目標(biāo)節(jié)點(diǎn)投遞預(yù)測(cè)值更高的中繼節(jié)點(diǎn)，從而減少消息傳輸時(shí)延.文獻(xiàn)[17]提出基于相遇概率的噴射等待路由算法PBSW，在Spray階段選擇與目標(biāo)節(jié)點(diǎn)相遇概率更高的相遇節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，然后根據(jù)兩者與目標(biāo)節(jié)點(diǎn)的相遇概率分配適當(dāng)比例的消息副本.然而，上述文獻(xiàn)只是從篩選中繼節(jié)點(diǎn)、靈活分配消息副本數(shù)、改進(jìn)Wait階段傳輸策略中的1個(gè)或2個(gè)方面進(jìn)行改進(jìn)，從而改進(jìn)策略不夠全面.

基于以上分析，本文綜合考慮中繼節(jié)點(diǎn)選擇、自適應(yīng)分配消息副本數(shù)量、改進(jìn)Wait階段傳輸策略這3個(gè)方面，提出一種基于節(jié)點(diǎn)綜合性能的自適應(yīng)噴射等待路由算法CPN-ASW.該算法在Spray階段根據(jù)節(jié)點(diǎn)間的相似程度是否超過給定閾值而采用不同的中繼節(jié)點(diǎn)選擇策略，考慮相遇節(jié)點(diǎn)間的活躍度和剩余緩存作為節(jié)點(diǎn)的相對(duì)效用值，當(dāng)節(jié)點(diǎn)間的相似程度小于給定閾值，直接根據(jù)節(jié)點(diǎn)的相對(duì)效用值自適應(yīng)地分配消息副本數(shù)，否則，選擇合適的中繼節(jié)點(diǎn)后再根據(jù)節(jié)點(diǎn)相對(duì)效用值分配消息副本數(shù)；進(jìn)一步為充分利用節(jié)點(diǎn)間的相遇機(jī)會(huì)，在Wait階段將副本數(shù)為1的消息轉(zhuǎn)發(fā)給到目標(biāo)節(jié)點(diǎn)投遞預(yù)測(cè)值更高的中繼節(jié)點(diǎn).

2 問題模型

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

假設(shè)網(wǎng)絡(luò)中包含n個(gè)節(jié)點(diǎn)，G=(V,E)為網(wǎng)絡(luò)拓?fù)鋱D，V={vi|1≤i≤n}表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為定義在G上的邊集，代表節(jié)點(diǎn)對(duì)之間的連接.每個(gè)節(jié)點(diǎn)vi維護(hù)一個(gè)歷史相遇節(jié)點(diǎn)集合Ei={vj|ni,j≠0}，該集合記錄從仿真開始節(jié)點(diǎn)vi遇到過的每個(gè)節(jié)點(diǎn).當(dāng)節(jié)點(diǎn)vi和vj進(jìn)入到彼此的通信范圍內(nèi)，vi檢測(cè)Ei中是否包含節(jié)點(diǎn)vj，若節(jié)點(diǎn)vj不包含在Ei中，則節(jié)點(diǎn)vi將vj添加到Ei中，并且將Ei中的ni,j值加1；若節(jié)點(diǎn)已包含在Ei中，說明兩節(jié)點(diǎn)曾經(jīng)相遇過，此時(shí)只將Ei中的ni,j加1.

2.2 節(jié)點(diǎn)相似度

我們?cè)诖蠖鄶?shù)的DTN應(yīng)用場(chǎng)景中，具有通信功能的移動(dòng)設(shè)備大多是由人類隨身攜帶的，人類的移動(dòng)模式不是完全隨機(jī)的，他們會(huì)表現(xiàn)出一定的社會(huì)特征.例如，如果2個(gè)人擁有1個(gè)或者多個(gè)共同的朋友，那么這2個(gè)人成為熟人的可能性很高，這種現(xiàn)象稱為“聚類”，即這2個(gè)人的運(yùn)動(dòng)軌跡相似.如果消息在運(yùn)動(dòng)軌跡相似的節(jié)點(diǎn)間轉(zhuǎn)發(fā)，那么在增大網(wǎng)絡(luò)開銷的同時(shí)，對(duì)提高投遞率并沒有實(shí)質(zhì)性的幫助.因此，在本文中提出節(jié)點(diǎn)相似度的概念來表示節(jié)點(diǎn)間運(yùn)動(dòng)軌跡的相似程度，如果2個(gè)節(jié)點(diǎn)間的相似度高，則需提高消息轉(zhuǎn)發(fā)條件，進(jìn)而減少不必要的轉(zhuǎn)發(fā)次數(shù).

定義1.節(jié)點(diǎn)相似度.節(jié)點(diǎn)vi與節(jié)點(diǎn)vj間的相似度是指節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的歷史相遇節(jié)點(diǎn)集合中擁有的共同歷史相遇節(jié)點(diǎn)的個(gè)數(shù)與這2個(gè)節(jié)點(diǎn)中較大歷史相遇節(jié)點(diǎn)集合中節(jié)點(diǎn)個(gè)數(shù)的比值，記為SD(i,j)，其表示為

(1)

如果SD(i,j)越大，即節(jié)點(diǎn)間的相似度越高，意味著節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的運(yùn)動(dòng)范圍和接觸節(jié)點(diǎn)越相似.

2.3 節(jié)點(diǎn)活躍度

在DTN中，活躍的節(jié)點(diǎn)能夠快速傳遞消息，使消息在較短的時(shí)間內(nèi)擴(kuò)散至較多的節(jié)點(diǎn)上，從而提高投遞率，降低傳輸時(shí)延.然而，DTN中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化，節(jié)點(diǎn)相遇其他節(jié)點(diǎn)的能力在較長(zhǎng)的仿真時(shí)間內(nèi)可能波動(dòng)比較大，因此，本文中通過劃分等長(zhǎng)的時(shí)間窗口來更加準(zhǔn)確估計(jì)節(jié)點(diǎn)活躍度，每當(dāng)1個(gè)時(shí)間窗口到期，就更新節(jié)點(diǎn)活躍度.節(jié)點(diǎn)活躍度反映了節(jié)點(diǎn)向網(wǎng)絡(luò)中擴(kuò)散消息的能力.

假設(shè)節(jié)點(diǎn)vi當(dāng)前運(yùn)動(dòng)時(shí)刻位于第k+1個(gè)時(shí)間窗口內(nèi)，在第k+1個(gè)時(shí)間窗口內(nèi)相遇節(jié)點(diǎn)的數(shù)量是未知的，本文通過歷史k個(gè)時(shí)間窗口算出的活躍度估計(jì)vi在當(dāng)前時(shí)間窗口內(nèi)的活躍度.

(2)

2.4 節(jié)點(diǎn)相對(duì)效用值

為了使CPN-ASW的Spray階段副本分配更具有合理性，本文根據(jù)節(jié)點(diǎn)間的相對(duì)效用值對(duì)副本進(jìn)行分配.節(jié)點(diǎn)的活躍度越高，則未來遇到目標(biāo)節(jié)點(diǎn)的可能性越大，則給活躍度高的節(jié)點(diǎn)分配更多的消息副本，這會(huì)造成活躍度高的節(jié)點(diǎn)易發(fā)生緩存溢出的情況，造成消息丟包次數(shù)較多，反而沒有體現(xiàn)出活躍度高的節(jié)點(diǎn)能使消息在網(wǎng)絡(luò)中快速擴(kuò)散的優(yōu)勢(shì).為了緩解活躍度高的節(jié)點(diǎn)上的擁塞程度，則同時(shí)將節(jié)點(diǎn)剩余緩存作為消息副本分配的依據(jù)，如果節(jié)點(diǎn)很活躍，但是剩余緩存已不足，則避免將較多的消息副本分配給此節(jié)點(diǎn)，防止節(jié)點(diǎn)頻繁擁塞導(dǎo)致消息丟包次數(shù)明顯增加，從而使較多的消息副本不能被有效傳遞.因此本文綜合利用節(jié)點(diǎn)的活躍度和剩余緩存，來體現(xiàn)節(jié)點(diǎn)相對(duì)效用值的高低.節(jié)點(diǎn)的活躍度越高，剩余緩存越多，其相對(duì)效用值越高,得到的轉(zhuǎn)發(fā)該消息的次數(shù)越多.

定義3.節(jié)點(diǎn)相對(duì)效用值.當(dāng)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj在第k+1個(gè)時(shí)間窗口內(nèi)相遇時(shí)，節(jié)點(diǎn)vi的相對(duì)效用值記為Ui，其計(jì)算為

(3)

2.5 節(jié)點(diǎn)投遞預(yù)測(cè)值

在DTN中，節(jié)點(diǎn)運(yùn)動(dòng)并非完全隨機(jī).如果節(jié)點(diǎn)vi和vj在過去的時(shí)間內(nèi)接觸比較頻繁，那么未來它們的相遇概率也會(huì)比較高.Prophet路由算法正是基于歷史預(yù)測(cè)策略的代表.該算法利用節(jié)點(diǎn)間的相遇歷史信息和傳遞性來定義投遞預(yù)測(cè)值(delivery probability)，利用投遞預(yù)測(cè)值來描述節(jié)點(diǎn)間的相遇概率.當(dāng)節(jié)點(diǎn)vi和vj相遇時(shí)，只有vj到消息目標(biāo)節(jié)點(diǎn)的投遞預(yù)測(cè)值更高時(shí)，vi才將消息傳輸給vj，通過這種有選擇地復(fù)制消息副本，有效地降低網(wǎng)絡(luò)開銷.

假如用P(i,j)來表示節(jié)點(diǎn)和節(jié)點(diǎn)間的投遞預(yù)測(cè)值，P(i,j)的計(jì)算分為3個(gè)過程：更新、衰減和傳遞性.

1) 更新.當(dāng)節(jié)點(diǎn)vi和vj相遇并建立連接時(shí)，更新投遞預(yù)測(cè)值：

P(i,j)=P(i,j) old+(1-P(i,j) old)×Pinit,

(4)

其中，P(i,j)表示節(jié)點(diǎn)vi和vj間的歷史投遞預(yù)測(cè)值，Pinit∈[0,1]是初始化常量.

2) 衰減.當(dāng)節(jié)點(diǎn)vi和vj在一段時(shí)間內(nèi)沒有遇到彼此，對(duì)投遞預(yù)測(cè)值進(jìn)行衰減：

P(i,j)=P(i,j) old×yc,

(5)

其中，y表示衰減因子，c表示節(jié)點(diǎn)vi和vj從上次相遇到目前為止所經(jīng)歷的時(shí)間塊的個(gè)數(shù).

3) 傳遞性.節(jié)點(diǎn)投遞預(yù)測(cè)值也具有傳遞性，根據(jù)觀察，如果節(jié)點(diǎn)vi經(jīng)常遇到節(jié)點(diǎn)vj，而節(jié)點(diǎn)vj經(jīng)常遇到節(jié)點(diǎn)vh，那么對(duì)目標(biāo)節(jié)點(diǎn)為節(jié)點(diǎn)vi的消息而言，節(jié)點(diǎn)vh可能是一個(gè)很好的中繼節(jié)點(diǎn).這種傳遞性如何投遞預(yù)測(cè)值P(i,h)：

P(i,h)=P(i,h) old+(1-P(i,h) old)×
P(i,j)×P(j,h)×β.

(6)

3 CPN-ASW路由算法

基于節(jié)點(diǎn)綜合性能的自適應(yīng)噴射等待路由算法CPN-ASW分為Spray和Wait這2個(gè)階段.在Spray階段，提出基于節(jié)點(diǎn)相似度和節(jié)點(diǎn)相對(duì)效用值的噴射策略；在Wait階段，提出基于節(jié)點(diǎn)投遞預(yù)測(cè)值的主動(dòng)轉(zhuǎn)發(fā)策略.

3.1 Spray階段

在真實(shí)的DTN應(yīng)用場(chǎng)景中，大量的移動(dòng)設(shè)備通過人來攜帶，人的行為具有很強(qiáng)的社會(huì)性.例如，擁有相同興趣愛好的人通常會(huì)聚集在一起，即這些人的運(yùn)動(dòng)軌跡相似.在副本受限的情況下，應(yīng)提高消息在相似度高的節(jié)點(diǎn)間的轉(zhuǎn)發(fā)條件，避免網(wǎng)絡(luò)開銷增大，投遞率卻無明顯提高情況的出現(xiàn).另外，不同種類的節(jié)點(diǎn)緩存、移動(dòng)速度不盡相同，因此承擔(dān)消息轉(zhuǎn)發(fā)任務(wù)的能力也有高低.在本文中通過定義節(jié)點(diǎn)相對(duì)效用值來描述節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的能力，給相對(duì)效用值高的節(jié)點(diǎn)分配更多的消息副本，有利于消息得到有效擴(kuò)散.

基于以上分析，本節(jié)提出一種基于節(jié)點(diǎn)相似度和節(jié)點(diǎn)相對(duì)效用值的噴射策略.根據(jù)節(jié)點(diǎn)相似度是否超過閾值采用不同的中繼節(jié)點(diǎn)選擇策略，確定好中繼節(jié)點(diǎn)后，按照節(jié)點(diǎn)相對(duì)效用值分配消息副本數(shù)量.具體噴射策略如下.

當(dāng)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相遇時(shí)，若節(jié)點(diǎn)vj不攜帶vi持有消息ml，節(jié)點(diǎn)vi向節(jié)點(diǎn)vj分配消息ml副本數(shù)量的步驟為：

1) 判斷節(jié)點(diǎn)vj是否是目標(biāo)節(jié)點(diǎn)，若是，則節(jié)點(diǎn)vi直接將消息的一個(gè)副本傳遞給vj，同時(shí)刪除該消息;否則，執(zhí)行步驟2)或步驟3).

2) 若節(jié)點(diǎn)間的相似度SD(i,j)≥τ,說明這2個(gè)節(jié)點(diǎn)相遇節(jié)點(diǎn)集合高度重疊，此時(shí)為減少消息在運(yùn)動(dòng)范圍大致重疊且相對(duì)效用值相差不大的節(jié)點(diǎn)間的轉(zhuǎn)發(fā)次數(shù)，若滿足：

Uj>Ui+Uth×SD(i,j),

(7)

則節(jié)點(diǎn)vi確定節(jié)點(diǎn)vj為中繼節(jié)點(diǎn)；否則，vi等待與目標(biāo)節(jié)點(diǎn)或其他節(jié)點(diǎn)相遇.其中，τ為相似度閾值，Uth為效用參數(shù).

若轉(zhuǎn)發(fā)條件滿足式(7)，根據(jù)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的相對(duì)效用值按比例分配消息副本數(shù)，設(shè)節(jié)點(diǎn)vi中的消息ml副本數(shù)為L(zhǎng)i old(ml)，分配給節(jié)點(diǎn)vj的消息副本數(shù)Ljnew(ml)為

(8)

節(jié)點(diǎn)vi自身保留消息ml副本數(shù)Li new(ml)為

Li new(ml)=Li old(ml)-Lj new(ml).

(9)

3) 若節(jié)點(diǎn)間的相似度SD(i,j)<τ，說明這2個(gè)節(jié)點(diǎn)的運(yùn)動(dòng)范圍相似性較小，此時(shí)為了消息的傳播范圍更廣，直接按照節(jié)點(diǎn)相對(duì)效用值在節(jié)點(diǎn)間按比例分配消息副本數(shù)，分配給vj的消息ml副本數(shù)Ljnew(ml)如式(8)所示，節(jié)點(diǎn)vi剩余消息ml副本數(shù)Li new(ml)如式(9)所示.

當(dāng)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相遇，vi向vj分配消息副本過程如算法1所示：

算法1.Spray階段算法.

輸入：節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相遇；

輸出：vi即將發(fā)送給vj的副本數(shù)大于1的消息集合MforwardList.

② 根據(jù)式(1)更新SD(i,j)；

③ 根據(jù)式(3)計(jì)算Ui,Uj；

④ FOR ?ml∈viandml?vj

⑤ IFLi old(ml)>1 THEN

⑥vd=ml.destination；

⑦ IFvd==vjTHEN

⑧ 節(jié)點(diǎn)vi將消息ml轉(zhuǎn)發(fā)給vj；

⑨ 節(jié)點(diǎn)vi刪除消息ml；

⑩ continue；

算法1中，行⑦～⑩表示當(dāng)相遇節(jié)點(diǎn)vj是消息目標(biāo)節(jié)點(diǎn)時(shí)，直接將消息轉(zhuǎn)發(fā)給vj并刪除節(jié)點(diǎn)vi中此消息；行～表示當(dāng)節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相似度大于閾值時(shí)，篩選合適中繼節(jié)點(diǎn)后再按照節(jié)點(diǎn)相對(duì)效用值計(jì)算分配消息副本數(shù)；行～表示vi和vj的相似度未超過閾值，直接按照節(jié)點(diǎn)相對(duì)效用值計(jì)算在節(jié)點(diǎn)間分配消息副本數(shù)；行～表示將符合條件的消息添加到MforwardList中；行～表示按照消息剩余生存時(shí)間從大到小的順序?qū)forwardList中消息轉(zhuǎn)發(fā)給vj.

假設(shè)網(wǎng)絡(luò)中的消息總數(shù)為M，在算法1中，主要時(shí)間消耗在行④～，時(shí)間復(fù)雜度為O(M)，因此，該算法的時(shí)間復(fù)雜度為O(M).

3.2 Wait階段

在傳統(tǒng)的SaW路由算法中，當(dāng)節(jié)點(diǎn)所攜帶的某個(gè)消息的副本數(shù)為1時(shí)，進(jìn)入到Wait階段，該階段存在弊端：節(jié)點(diǎn)攜帶消息直到遇到目標(biāo)節(jié)點(diǎn)才將消息轉(zhuǎn)發(fā)出去，沒有充分利用節(jié)點(diǎn)間的相遇機(jī)會(huì).

基于上述分析，本節(jié)提出基于節(jié)點(diǎn)投遞預(yù)測(cè)值的主動(dòng)轉(zhuǎn)發(fā)策略.在Wait階段利用Prophet路由算法中的投遞預(yù)測(cè)值來描述節(jié)點(diǎn)間成功傳輸消息的概率，當(dāng)節(jié)點(diǎn)vi中持有相遇節(jié)點(diǎn)vj中沒有的消息時(shí)，以相遇節(jié)點(diǎn)vj的緩存占用比來調(diào)節(jié)閾值大小，只有節(jié)點(diǎn)vj到消息目標(biāo)節(jié)點(diǎn)的投遞預(yù)測(cè)值大于節(jié)點(diǎn)vi到消息目標(biāo)節(jié)點(diǎn)的投遞預(yù)測(cè)值，并且兩者到消息目標(biāo)節(jié)點(diǎn)的投遞預(yù)測(cè)值區(qū)分度大于給定閾值時(shí)，節(jié)點(diǎn)vi才將消息ml轉(zhuǎn)發(fā)給相遇節(jié)點(diǎn)vj.

當(dāng)節(jié)點(diǎn)vi中的消息ml只剩下一個(gè)消息副本時(shí)，與未緩存消息ml的節(jié)點(diǎn)vj相遇，若滿足：

P(j,d)>P(i,d)+Pth×OBj,

(10)

則節(jié)點(diǎn)vi將該消息轉(zhuǎn)發(fā)給節(jié)點(diǎn)vj.其中，P(i,d)和P(j,d)分別表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj將消息ml成功投遞到目標(biāo)節(jié)點(diǎn)vd的概率;Pth∈[0,1]為預(yù)設(shè)參數(shù);OBj為相遇節(jié)點(diǎn)vj的緩存占用率.在轉(zhuǎn)發(fā)過程中通過利用相遇節(jié)點(diǎn)vj的緩存占用比來調(diào)節(jié)節(jié)點(diǎn)間的投遞預(yù)測(cè)值區(qū)分度，一方面避免消息在投遞概率近似的節(jié)點(diǎn)間轉(zhuǎn)發(fā)，另一方面隨著相遇節(jié)點(diǎn)vj的緩存占用率不斷增大，轉(zhuǎn)發(fā)條件越來越高，從而降低網(wǎng)絡(luò)開銷，較大程度上避免了擁塞情況的出現(xiàn).

在Wait階段，節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相遇時(shí)，節(jié)點(diǎn)vi執(zhí)行的消息轉(zhuǎn)發(fā)過程如算法2所示：

算法2.Wait階段算法.

輸入：節(jié)點(diǎn)vi和節(jié)點(diǎn)vj相遇；

輸出：vi即將發(fā)送給vj的副本數(shù)為1的消息集合SforwardList.

① 根據(jù)式(4)更新P(i,j)；

② 節(jié)點(diǎn)間相互交換變量OBi,OBj；

③ FOR ?ml∈viandml?vj

④ IFLi old(ml)==1 THEN

⑤vd=ml.destination；

⑥ IFvd==vjTHEN

⑦ 節(jié)點(diǎn)vi將消息ml轉(zhuǎn)發(fā)給vj；

⑧ 節(jié)點(diǎn)vi刪除消息ml；

⑨ continue；

⑩ ELSE IFP(j,d)>P(i,d)+Pth×OBj

THEN

算法2中，行⑥～⑨表示當(dāng)節(jié)點(diǎn)vj是消息目標(biāo)節(jié)點(diǎn)時(shí)，直接將消息轉(zhuǎn)發(fā)給vj并刪除節(jié)點(diǎn)vi中此消息；行⑩～表示當(dāng)節(jié)點(diǎn)vj不是消息目標(biāo)節(jié)點(diǎn)時(shí)，只有滿足式(10)才將消息轉(zhuǎn)發(fā)給vj，同時(shí)vi刪除此消息；行～表示按照消息剩余生存時(shí)間從大到小的順序?qū)forwardList中消息轉(zhuǎn)發(fā)給vj.

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

4.1 仿真環(huán)境配置

實(shí)驗(yàn)采用ONE[18]仿真平臺(tái)，將CPN-ASW與Epidemic，SaW，EBR，PBSW在相同實(shí)驗(yàn)環(huán)境下進(jìn)行對(duì)比.仿真采用ONE自帶的赫爾辛基市地圖作為移動(dòng)場(chǎng)景，大小為4 500 m×3 400 m，節(jié)點(diǎn)數(shù)量設(shè)置為126個(gè)，共分為3類節(jié)點(diǎn)：行人、出租車、有軌電車.其中行人組80個(gè)節(jié)點(diǎn)，出租車組40個(gè)節(jié)點(diǎn)，這2組按照基于地圖路線的最短路徑模型移動(dòng)，有軌電車組共6個(gè)節(jié)點(diǎn)，按照基于地圖的固定路線模型移動(dòng).具體的仿真參數(shù)設(shè)置如表1所示，其他參數(shù)采用ONE平臺(tái)自帶的默認(rèn)設(shè)置.對(duì)于初始常量Pinit、傳遞因子β、衰減參數(shù)y這3個(gè)參數(shù)設(shè)置可參考文獻(xiàn)[14]中設(shè)定的值，取Pinit=0.75,β=0.25,y=0.98.

Table 1 Simulation Parameters表1 仿真參數(shù)

4.2 評(píng)價(jià)指標(biāo)

1) 投遞率

投遞率=成功投遞到目標(biāo)節(jié)點(diǎn)的消息數(shù)量/網(wǎng)絡(luò)中源節(jié)點(diǎn)產(chǎn)生的消息數(shù)量.

2) 平均時(shí)延

平均時(shí)延=網(wǎng)絡(luò)中所有被成功投遞的消息從源節(jié)點(diǎn)產(chǎn)生開始到目標(biāo)節(jié)點(diǎn)完整接收到所經(jīng)過的平均時(shí)間.

3) 網(wǎng)絡(luò)開銷

網(wǎng)絡(luò)開銷.冗余的中繼轉(zhuǎn)發(fā)次數(shù)/成功投遞到目標(biāo)節(jié)點(diǎn)的消息數(shù)量.

4) 平均跳數(shù)

平均跳數(shù).網(wǎng)絡(luò)中所有被成功投遞的消息從源節(jié)點(diǎn)產(chǎn)生開始到目標(biāo)節(jié)點(diǎn)完整接收到所經(jīng)過的平均跳數(shù).

4.3 參數(shù)設(shè)置實(shí)驗(yàn)

4.3.1 活躍度平滑因子α設(shè)置

α的取值對(duì)CPN-ASW算法的實(shí)驗(yàn)效果影響較大，在表1參數(shù)設(shè)置條件下更改α取值，綜合考慮投遞率和平均時(shí)延，α=0.8時(shí)實(shí)驗(yàn)效果最佳.如圖1所示:

Fig. 1 Performance comparison of CPN-ASW under different α圖1 CPN-ASW在α不同取值下的性能比較

從圖1(a)中可以觀察到，α=0.6時(shí)投遞率最高，根據(jù)Markov預(yù)測(cè)法[19]，任何事件可通過其目前的狀況來預(yù)測(cè)該事件將來各個(gè)時(shí)刻(或時(shí)期)的變動(dòng)狀況.由此可知近期活躍度高的節(jié)點(diǎn)在未來一段時(shí)間內(nèi)也將延續(xù)較高的活躍性.當(dāng)α取值偏重于最近1個(gè)完整時(shí)間窗口活躍度時(shí)，更能準(zhǔn)確預(yù)測(cè)節(jié)點(diǎn)在未來一段時(shí)間的活躍度.但是同時(shí)觀察圖1(b)，α=0.6時(shí)投遞率最高，此時(shí)平均時(shí)延也最高.所以綜合考慮投遞率和平均時(shí)延，α=0.8時(shí)投遞率比α=0.6時(shí)要略低，但平均時(shí)延有了明顯的改善，所以本文中α=0.8時(shí)實(shí)驗(yàn)效果最佳.

4.3.2 相對(duì)效用值參數(shù)w設(shè)置

w的取值直接影響消息副本分配數(shù)量的合理性，本文通過在w不同取值下的投遞率變化，得出w=0.3時(shí)投遞率最高，如圖2所示:

Fig. 2 Delivery ratio of CPN-ASW under different w圖2 CPN-ASW在w不同取值下的消息投遞率比較

4.4 算法比較及分析

為了驗(yàn)證CPN-ASW算法的高效性，進(jìn)行了2組仿真實(shí)驗(yàn)，在不同的消息生存周期(TTL)、不同的節(jié)點(diǎn)緩存大小下對(duì)這5種算法在消息投遞率、平均時(shí)延、網(wǎng)絡(luò)開銷、平均跳數(shù)這4個(gè)方面進(jìn)行評(píng)估.實(shí)驗(yàn)結(jié)果表明CPN-ASW在提高消息投遞率、控制網(wǎng)絡(luò)開銷、降低平均時(shí)延方面效果顯著.

1) 不同消息生存周期

在4.1節(jié)的環(huán)境配置下，改變消息生存周期，對(duì)比各種算法在不同消息生存周期下消息投遞率(如圖3所示)、平均時(shí)延(如圖4所示)、網(wǎng)絡(luò)開銷(如圖5所示)、平均跳數(shù)(如圖6所示)這4個(gè)方面的變化情況.

Fig. 3 Delivery ratio under different TTL圖3 不同消息生存周期下的投遞率

圖3顯示了各種算法在不同消息生存周期下消息投遞率的變化情況.其中CPN-ASW算法的投遞率最高，相比Epidemic平均提高了58.55%，相比SaW平均提高了3.60%，相比EBR平均提高了1.20%，相比PBSW平均提高了11.22%.這主要?dú)w結(jié)于2個(gè)原因：1)CPN-ASW算法在Spray階段根據(jù)節(jié)點(diǎn)間相似程度是否超過閾值而采用不同的中繼節(jié)點(diǎn)選擇策略，并根據(jù)節(jié)點(diǎn)間相對(duì)效用值實(shí)現(xiàn)自適應(yīng)分配消息副本數(shù)，避免消息的盲目轉(zhuǎn)發(fā)；2)在Wait階段實(shí)現(xiàn)消息主動(dòng)轉(zhuǎn)發(fā)，選擇到目標(biāo)節(jié)點(diǎn)投遞預(yù)測(cè)值更高的中繼節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā).同時(shí)從實(shí)驗(yàn)結(jié)果可以看出，Epidemic算法的投遞率遠(yuǎn)低于其他算法，并且曲線呈現(xiàn)下降趨勢(shì)，這是因?yàn)榇怂惴]有限制消息副本的最大拷貝數(shù)，隨著消息生存周期的增加，消息在有限緩存中駐留時(shí)間更長(zhǎng)，盲目洪泛易導(dǎo)致網(wǎng)絡(luò)中擠壓大量消息副本，引起網(wǎng)絡(luò)擁塞，消息投遞率反而下降.

圖4評(píng)估了各個(gè)算法平均時(shí)延的變化情況.5種算法的平均時(shí)延隨著消息生存周期的增加大體上呈現(xiàn)增長(zhǎng)態(tài)勢(shì)，因?yàn)樵黾由嬷芷谑乖瓉碓诙虝r(shí)間內(nèi)不能到達(dá)目標(biāo)節(jié)點(diǎn)的消息能被成功投遞.其中CPN-ASW的平均時(shí)延最小，相比SaW下降了4.44%，相比EBR下降2.08%，相比PBSW下降9.67%.這主要是因?yàn)镃PN-ASW算法在Wait階段實(shí)現(xiàn)了消息主動(dòng)轉(zhuǎn)發(fā)，選擇更優(yōu)的中繼節(jié)點(diǎn)進(jìn)行傳輸，加快了消息到達(dá)目標(biāo)節(jié)點(diǎn)的速度.Epidemic算法采用洪泛機(jī)制，過多的復(fù)制消息容易使網(wǎng)絡(luò)陷入擁塞，故平均時(shí)延相比其他算法來說是最大的.

Fig. 4 Average delay under different TTL圖4 不同消息生存周期下的平均時(shí)延

圖5比較各個(gè)路由算法的網(wǎng)絡(luò)開銷.由于SaW，EBR，PBSW，CPN-ASW均在一開始限制了消息副本拷貝數(shù)，也就是限制了轉(zhuǎn)發(fā)次數(shù)，故網(wǎng)絡(luò)開銷遠(yuǎn)低于Epidemic算法.CPN-ASW算法網(wǎng)絡(luò)開銷相對(duì)SaW平均下降17.71%，這是因?yàn)橄鄬?duì)SaW算法在Spray階段盲目轉(zhuǎn)發(fā)，CPN-ASW算法在Spray階段避免消息在運(yùn)動(dòng)范圍相似的節(jié)點(diǎn)間轉(zhuǎn)發(fā)，在一定程度上減少了不必要的中繼轉(zhuǎn)發(fā)次數(shù)，在Wait階段自適應(yīng)控制轉(zhuǎn)發(fā)條件，最終網(wǎng)絡(luò)開銷較小.從圖5中還可看出，PBSW算法的網(wǎng)絡(luò)開銷最小，其原因主要體現(xiàn)在2個(gè)方面：1)Spray階段只將消息轉(zhuǎn)發(fā)給與目的節(jié)點(diǎn)相遇概率更高的節(jié)點(diǎn)，從而消息轉(zhuǎn)發(fā)次數(shù)受到限制；2)在Wait階段沒有任何優(yōu)化策略，直到與目的節(jié)點(diǎn)相遇時(shí)才將消息轉(zhuǎn)發(fā)出去，不存在冗余的中繼轉(zhuǎn)發(fā)次數(shù).

Fig. 5 Overhead ratio under different TTL圖5 不同消息生存周期下的網(wǎng)絡(luò)開銷

圖6比較了各個(gè)算法的平均跳數(shù).其中CPN-ASW相對(duì)SaW平均跳數(shù)下降4.22%，主要原因在于CPN-ASW在Spray階段當(dāng)節(jié)點(diǎn)間運(yùn)動(dòng)范圍高度相似時(shí)選擇更優(yōu)的中繼節(jié)點(diǎn)分配消息副本數(shù)，在Wait階段雖然進(jìn)行主動(dòng)轉(zhuǎn)發(fā)，但是自適應(yīng)控制轉(zhuǎn)發(fā)條件，最終平均跳數(shù)還是明顯低于SaW.其中PBSW的平均跳數(shù)最低，有2個(gè)原因：1)Spray階段對(duì)中繼節(jié)點(diǎn)的選擇更為苛刻，只給到目的節(jié)點(diǎn)投遞預(yù)測(cè)值更高的中繼節(jié)點(diǎn)分配消息副本；2)Wait階段被動(dòng)等待，直到遇到目的節(jié)點(diǎn)才進(jìn)行消息投遞.

Fig. 6 Average hop under different TTL圖6 不同消息生存周期下的平均跳數(shù)

總體來看，在不同的消息生存周期下，CPN-ASW相比其他4種算法均表現(xiàn)出較高的投遞率和較低的平均時(shí)延.并且在網(wǎng)絡(luò)開銷和平均跳數(shù)方面較SaW也表現(xiàn)出明顯的優(yōu)勢(shì).PBSW算法雖然在網(wǎng)絡(luò)開銷和平均跳數(shù)方面表現(xiàn)最優(yōu)，但是相對(duì)于其他3種限制消息副本數(shù)的算法(SaW，EBR，CPN-ASW)來說，投遞率和平均時(shí)延方面均表現(xiàn)出明顯的劣勢(shì).另外也可看出，Epidemic算法性能最差，說明在資源受限的真實(shí)場(chǎng)景中，洪泛式的轉(zhuǎn)發(fā)算法并不能取得良好的效果.

2) 不同節(jié)點(diǎn)緩存大小

在不同節(jié)點(diǎn)緩存大小下，比較和分析各個(gè)算法在消息投遞率(如圖7所示)、平均時(shí)延(如圖8所示)、網(wǎng)絡(luò)開銷(如圖9所示)、平均跳數(shù)(如圖10所示)這4個(gè)方面的變化情況.

圖7顯示了各個(gè)算法在不同節(jié)點(diǎn)緩存下消息投遞率的變化情況.5種算法的投遞率都隨著節(jié)點(diǎn)緩存的增加而提高，這是因?yàn)楣?jié)點(diǎn)緩存越大，其所能攜帶的消息數(shù)量也越多，由于網(wǎng)絡(luò)擁塞導(dǎo)致的丟包情況會(huì)逐漸緩解，其中CPN-ASW算法的投遞率最高，相比Epidemic平均提高了67.07%，相比SaW平均提高了5.28%，相比EBR平均提高了2.55%，相比PBSW平均提高了9.12%.

Fig. 7 Delivery ratio under different buffer sizes圖7 不同緩存大小下的投遞率

圖8比較了各個(gè)算法的平均時(shí)延.CPN-ASW的平均時(shí)延相比PBSW平均下降10.26%.從圖8中還可觀察到，在節(jié)點(diǎn)緩存小于12 MB時(shí)，CPN-ASW的平均時(shí)延略大于SaW；當(dāng)節(jié)點(diǎn)緩存超過12 MB，CPN-ASW的平均時(shí)延開始小于SaW的時(shí)延.這是由于CPN-ASW在Spray階段是按照節(jié)點(diǎn)間的相對(duì)效用值分配消息副本數(shù)，相對(duì)效用值綜合考慮節(jié)點(diǎn)活躍度和節(jié)點(diǎn)剩余緩存，當(dāng)節(jié)點(diǎn)緩存本身較小時(shí)，節(jié)點(diǎn)的緩存利用率一直都很高，相對(duì)效用值中活躍度因素的重要性更為突出，活躍度高的節(jié)點(diǎn)易形成擁塞，消息丟包次數(shù)變多，需要經(jīng)過更多的轉(zhuǎn)發(fā)次數(shù)才能到達(dá)目標(biāo)節(jié)點(diǎn)，傳輸時(shí)延較大；隨著節(jié)點(diǎn)緩存的增加，活躍度高的節(jié)點(diǎn)上擁塞情況得到緩解，再加上CPN-ASW在Wait階段選擇更優(yōu)的中繼節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，最終CPN-ASW在平均時(shí)延方面的優(yōu)越性得到體現(xiàn).

Fig. 8 Average delay under different buffer sizes圖8 不同緩存大小下的平均時(shí)延

Fig. 9 Overhead ratio under different buffer sizes圖9 不同緩存大小下的網(wǎng)絡(luò)開銷

圖9顯示的是網(wǎng)絡(luò)開銷隨節(jié)點(diǎn)緩存的變化情況.當(dāng)節(jié)點(diǎn)緩存逐漸增加，5種算法的網(wǎng)絡(luò)開銷都逐漸下降，這是因?yàn)榫彺婵臻g越小，節(jié)點(diǎn)就越有可能因?yàn)榫彺嬲紳M采用消息丟棄策略，使消息經(jīng)過較多的轉(zhuǎn)發(fā)次數(shù)才能到達(dá)目標(biāo)節(jié)點(diǎn).其中CPN-ASW的網(wǎng)絡(luò)開銷較Epidemic平均下降了69.55%，較SaW平均下降了17.99%.此外，通過觀察圖9可知，Epidemic算法的網(wǎng)絡(luò)開銷隨著緩存的增加而急速下降，這表明此算法適用于資源充足的網(wǎng)絡(luò)，在緩存較充足時(shí)能有效降低網(wǎng)絡(luò)開銷，發(fā)揮出較好的效果.

圖10比較各個(gè)算法的平均跳數(shù).其中PBSW的平均跳數(shù)最低，CPN-ASW平均跳數(shù)和EBR算法大致相同，CPN-ASW的平均跳數(shù)相對(duì)Epidemic平均下降了17.36%，相對(duì)SaW平均下降了2.50%.這說明了CPN-ASW算法采用的中繼節(jié)點(diǎn)選擇的合理性.

Fig. 10 Average hop under different buffer sizes圖10 不同緩存大小下的平均跳數(shù)

總體來看，在5種算法中，在不同節(jié)點(diǎn)緩存大小下，CPN-ASW算法消息投遞率最高，當(dāng)緩存較充足時(shí)平均時(shí)延最小，且在網(wǎng)絡(luò)開銷和平均跳數(shù)方面也表現(xiàn)優(yōu)越且穩(wěn)定.

5 結(jié)束語

本文針對(duì)DTN長(zhǎng)時(shí)延、間歇性連接等特點(diǎn)，提出一種基于節(jié)點(diǎn)綜合性能的噴射等待路由算法CPN-ASW.該算法在Spray階段根據(jù)節(jié)點(diǎn)間相似度是否超過給定閾值采用不同中繼節(jié)點(diǎn)選擇策略，并按照節(jié)點(diǎn)相對(duì)效用值自適應(yīng)分配消息副本數(shù)；在Wait階段將消息轉(zhuǎn)發(fā)給到目標(biāo)節(jié)點(diǎn)投遞預(yù)測(cè)值更高的中繼節(jié)點(diǎn).由對(duì)比算法分析得出，本文提出算法能夠有效提高消息投遞率，控制網(wǎng)絡(luò)開銷和降低平均時(shí)延.

然而，從實(shí)驗(yàn)中也可觀察到，CPN-ASW算法相對(duì)于傳統(tǒng)SaW來說，在節(jié)點(diǎn)緩存較小時(shí)平均時(shí)延較高.為進(jìn)一步降低平均時(shí)延，設(shè)置一種有效的緩存管理策略是下一步研究工作的重點(diǎn).

作者貢獻(xiàn)聲明：崔建群負(fù)責(zé)提出研究選題、優(yōu)化論文；孫佳悅負(fù)責(zé)設(shè)計(jì)算法、設(shè)計(jì)實(shí)驗(yàn)并開展實(shí)驗(yàn)分析；常亞楠負(fù)責(zé)設(shè)計(jì)論文框架；余東海、鄔堯負(fù)責(zé)調(diào)研整理文獻(xiàn)、協(xié)助論文實(shí)驗(yàn)；吳黎兵負(fù)責(zé)提出指導(dǎo)意見并修改論文.