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

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

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

(jqcui@126.com)

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 問題模型

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

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

2.2 節(jié)點相似度

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

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

(1)

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

2.3 節(jié)點活躍度

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

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

(2)

2.4 節(jié)點相對效用值

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

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

(3)

2.5 節(jié)點投遞預(yù)測值

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

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

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

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

(4)

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

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

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

(5)

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

3) 傳遞性.節(jié)點投遞預(yù)測值也具有傳遞性，根據(jù)觀察，如果節(jié)點vi經(jīng)常遇到節(jié)點vj，而節(jié)點vj經(jīng)常遇到節(jié)點vh，那么對目標(biāo)節(jié)點為節(jié)點vi的消息而言，節(jié)點vh可能是一個很好的中繼節(jié)點.這種傳遞性如何投遞預(yù)測值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é)點綜合性能的自適應(yīng)噴射等待路由算法CPN-ASW分為Spray和Wait這2個階段.在Spray階段，提出基于節(jié)點相似度和節(jié)點相對效用值的噴射策略；在Wait階段，提出基于節(jié)點投遞預(yù)測值的主動轉(zhuǎn)發(fā)策略.

3.1 Spray階段

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

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

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

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

算法1.Spray階段算法.

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

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

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

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

④ FOR ?ml∈viandml?vj

⑤ IFLi old(ml)>1 THEN

⑥vd=ml.destination；

⑦ IFvd==vjTHEN

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

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

⑩ continue；

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

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

3.2 Wait階段

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

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

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

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

(10)

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

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

算法2.Wait階段算法.

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

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

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

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

③ FOR ?ml∈viandml?vj

④ IFLi old(ml)==1 THEN

⑤vd=ml.destination；

⑥ IFvd==vjTHEN

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

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

⑨ continue；

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

THEN

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

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

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

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

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

4.2 評價指標(biāo)

1) 投遞率

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

2) 平均時延

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

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

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

4) 平均跳數(shù)

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

4.3 參數(shù)設(shè)置實驗

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

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

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

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

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

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

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

4.4 算法比較及分析

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

1) 不同消息生存周期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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