基于信譽的延遲容忍網(wǎng)絡(luò)雙重Spray and Wait增強方案

張希，王曉飛，張權(quán)，唐朝京

（國防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院，湖南 長沙 410073）

1 引言

在各種無線網(wǎng)絡(luò)應(yīng)用中，節(jié)點移動特性、稀疏分布、無線設(shè)備射頻關(guān)閉或障礙物造成的信號衰減等因素都可能導(dǎo)致網(wǎng)絡(luò)的間歇性連通或長時間延遲。這類環(huán)境中，網(wǎng)絡(luò)報文傳輸所需的端到端路徑難以得到保證。為了有效解決受限環(huán)境中網(wǎng)絡(luò)連通性的難題，延遲容忍網(wǎng)絡(luò)（DTN, delay tolerant network）的研究[1,2]日益受到重視，并在軍事戰(zhàn)術(shù)網(wǎng)絡(luò)、野生物種追蹤、深空通信等領(lǐng)域初步展現(xiàn)了其應(yīng)用價值。

為了提高DTN的傳輸效率，Spyropoulos等人提出Spray and Wait(SW)多副本路由方案[3]，緩解了資源消耗和傳輸延遲的矛盾。SW 路由方案包含Spray和Wait 2個階段。在S階段，每個報文都會生成相應(yīng)的副本，并分發(fā)至多個不同的轉(zhuǎn)發(fā)節(jié)點。在 W 階段，如果報文轉(zhuǎn)發(fā)過程中始終沒有發(fā)現(xiàn)目的節(jié)點，則多個持有報文副本的節(jié)點切換至直接發(fā)送狀態(tài)，僅僅將報文轉(zhuǎn)發(fā)給目的節(jié)點。雙重 Spray and Wait（BSW）是SW路由協(xié)議族中的一種運行模式。該模式下，如果節(jié)點持有多份報文副本，即處于S階段，將每次轉(zhuǎn)發(fā)持有的副本數(shù)量的一半給其他轉(zhuǎn)發(fā)者。當(dāng)僅持有一份副本時，即處于 W 階段，節(jié)點等待目的節(jié)點的出現(xiàn)，并通過直接傳輸方式完成轉(zhuǎn)發(fā)。該方案提供了一種有效的多副本路由方式，在間歇連接的環(huán)境中得到較為廣泛的應(yīng)用。

這類多副本路由方案需要每個節(jié)點能夠共享其資源實現(xiàn)整個網(wǎng)絡(luò)的互聯(lián)互通，并承擔(dān)報文轉(zhuǎn)發(fā)的工作。很多研究表明，如果缺乏合適的激勵方案，網(wǎng)絡(luò)節(jié)點因自身傳輸帶寬、存儲空間和能耗等因素的限制，難于克服自私的天性，分享有效資源[4,5]。伴隨著自私節(jié)點數(shù)量的增多和自私行為的頻繁發(fā)生，網(wǎng)絡(luò)性能將受到嚴重影響，甚至妨礙整個網(wǎng)絡(luò)的運行。DTN本身所特有的網(wǎng)絡(luò)割裂和間歇中斷特性將使得這種危害進一步加劇[6,7]。信譽為抑制自私行為的發(fā)生提供了一種有效的解決辦法。通過對用戶行為的收集分析，提供信譽評分，作為節(jié)點行為的參考依據(jù)，判斷節(jié)點是否存在自私行為[8～10]。

然而，現(xiàn)有的針對無線自組織網(wǎng)絡(luò)和P2P網(wǎng)絡(luò)的信譽方案并不適用于 DTN環(huán)境。首先，現(xiàn)有方案都假設(shè)在源節(jié)點到目的節(jié)點之間存在一條端到端路徑。這種假設(shè)因為 DTN的網(wǎng)絡(luò)割裂和間歇鏈接的特性而不能成立。其次，現(xiàn)有方案大多基于單副本路由方式，而 DTN中為提高網(wǎng)絡(luò)性能和傳輸可靠性，一般采用多副本路由方式。這使得現(xiàn)有方案不能應(yīng)用于DTN環(huán)境。

本文將信譽與BSW相結(jié)合，以解決DTN環(huán)境中自私節(jié)點帶來的網(wǎng)絡(luò)性能下降甚至不可用的問題。首先，引入傳輸證據(jù)的概念，設(shè)計了觀測協(xié)議以解決 DTN環(huán)境下對節(jié)點行為的觀測問題，實現(xiàn)對節(jié)點行為的數(shù)據(jù)統(tǒng)計。其次，依據(jù)節(jié)點行為的統(tǒng)計數(shù)據(jù)對節(jié)點進行信譽評分，實現(xiàn)對自私節(jié)點的辨識，改變原有BSW的路由選擇過程；為BSW路由過程建模，通過概率計算確定信譽門限，避免了對門限的主觀性、經(jīng)驗型的選擇。最后，建立仿真實驗平臺，驗證了該方案能夠減少自私行為對 DTN性能的負面影響，提高網(wǎng)絡(luò)性能。

2 提出的方案

為實現(xiàn)信譽與BSW的融合，本方案設(shè)計了兩大模塊，即觀測處理模塊和信譽路由模塊。在觀測處理模塊中，設(shè)計了一種應(yīng)用于節(jié)點通信過程的觀測協(xié)議，協(xié)議提供了對鄰居節(jié)點行為監(jiān)測的方法，取代原有信譽方案對混雜監(jiān)聽模式的依賴。該模塊負責(zé)對統(tǒng)計數(shù)據(jù)的收集，以用于后續(xù)的信譽處理。在信譽路由模塊中，通過處理節(jié)點交互統(tǒng)計數(shù)據(jù)以計算評分，從而判斷節(jié)點是否有自私行為發(fā)生，優(yōu)化原有的BSW路由選擇。信譽與路由的結(jié)合，使得節(jié)點可以根據(jù)表征節(jié)點自私程度的評分判斷自私節(jié)點，避免了自私節(jié)點對網(wǎng)絡(luò)運行的危害。在方案的詳細表述之前，首先對系統(tǒng)配置進行說明。

2.1 系統(tǒng)配置

本方案設(shè)計中需要配置離線的私鑰生成器（OKG, offline key generator）負責(zé)節(jié)點注冊階段的密鑰生成。系統(tǒng)應(yīng)用了雙線性對技術(shù)，采用G1和G2分別表示q階的加法循環(huán)群和乘法循環(huán)群，用P表示加法循環(huán)群的生成元。雙線性對:G1×G1→G2能夠滿足雙線性、非退化性和可計算性。OKG選擇一個作為私鑰，計算其公鑰 Ppub=sP，并選取一個散列函數(shù)H :{0,1}*→G1。OKG采用{G1,G2,, P, Ppub,H}作為系統(tǒng)參數(shù)，在注冊過程中配置到DTN節(jié)點中。同時，OKG驗證節(jié)點身份信息，并根據(jù)其身份信息計算節(jié)點私鑰sk=sH( I D)，并以 pk = H( I D)作為節(jié)點公鑰。

當(dāng)一個節(jié)點i需要轉(zhuǎn)發(fā)一個報文B的時候，節(jié)點需要配置附屬消息Ai，由以下部分組成:BI包含報文基礎(chǔ)信息，其中有源節(jié)點、目的節(jié)點的身份信息，報文會話號等；FI，表示報文轉(zhuǎn)發(fā)相關(guān)信息，其中，包括報文轉(zhuǎn)發(fā)請求節(jié)點、接收節(jié)點以及下一跳的轉(zhuǎn)發(fā)節(jié)點的身份信息。TS和Sig分別表示時間戳和對報文的簽名。

2.2 觀測處理模塊

觀測處理模塊的設(shè)計主要解決 DTN環(huán)境下對節(jié)點行為觀測和統(tǒng)計的問題。節(jié)點行為的觀測方式是基礎(chǔ)信譽數(shù)據(jù)采集的關(guān)鍵，也是信譽在 DTN環(huán)境下應(yīng)用的瓶頸。頻繁的網(wǎng)絡(luò)割裂和機會鏈路的特性導(dǎo)致經(jīng)典的觀測方式——混雜監(jiān)聽模式和源路由模式難于應(yīng)用?；祀s監(jiān)聽模式下，節(jié)點緩存發(fā)送給鄰居節(jié)點的報文，截獲并比對所有通過的報文與原始報文的差異，以未發(fā)生偽造和篡改來確定鄰居節(jié)點的正常轉(zhuǎn)發(fā)行為。然而，網(wǎng)絡(luò)的間歇鏈接特性難以保證對無線鏈路的持續(xù)觀測?？偸谴嬖谝粭l端到端路徑的假設(shè)同樣不適用于DTN，因而導(dǎo)致源路由相關(guān)方案的應(yīng)用困難。

本方案引入轉(zhuǎn)發(fā)證據(jù)的概念，設(shè)計了對節(jié)點行為的觀測協(xié)議，將轉(zhuǎn)發(fā)證據(jù)的生成與傳播融入觀測協(xié)議中，且轉(zhuǎn)發(fā)證據(jù)的傳輸可以通過報文進行捎帶，減少了網(wǎng)絡(luò)資源的消耗。

以m→n→p 的報文傳輸過程為例描述觀測協(xié)議。節(jié)點 m確定下一個節(jié)點之后，隨機選擇r∈，計算σ1= skm+rH( B||BI||FI||TS )和σ2=rP ，得到對報文簽名 Sig=()。這里選擇Sakai-Ohgishi-Kasahara方案實現(xiàn)協(xié)議支持的簽名[11]。

1) m→n:B, Aim，其中，Aim=(BI||FI||TS||Sig)；

當(dāng)節(jié)點n接收報文和附屬信息后，將執(zhí)行以下步驟驗證。

①驗證報文基本信息的正確性，包括時間戳和TTL信息；

②驗證Aim時間戳正確性；

③通過檢查下式以便于確定簽名的正確性。

2) n→m:Fen, 其中，F(xiàn)en=(B I||S etid||TS||Sig)；

n→p:B, Ain, 其中，Ain=(B I||F I|| T S||S ig)；

驗證通過之后，節(jié)點n發(fā)送轉(zhuǎn)發(fā)證據(jù)Fe給節(jié)點m作為其成功轉(zhuǎn)發(fā)報文的響應(yīng)。Setid包括3個部分的身份信息，即報文轉(zhuǎn)發(fā)節(jié)點、接收節(jié)點以及需要提供傳輸證據(jù)的節(jié)點。

節(jié)點n選擇下一跳節(jié)點，重新計算附屬信息，繼續(xù)分發(fā)過程。

3) p→n:Fep, 其中，F(xiàn)ep=(BI||S etid||T S||；Sig)

節(jié)點p執(zhí)行同樣驗證過程。驗證通過后，發(fā)送傳輸證據(jù)Fe給節(jié)點n，其中，Setid包含了節(jié)點m,n和p的身份信息。

4) n→m:Fep, 其中，F(xiàn)ep=(BI||S etid||T S||Sig)；

節(jié)點m確認Fe簽名的正確性之后，確認節(jié)點n的轉(zhuǎn)發(fā)行為。該模塊將激活報文確認計數(shù)器，對相關(guān)統(tǒng)計數(shù)據(jù)進行操作。

針對BSW路由的兩個階段，模塊配置兩組統(tǒng)計量 (tsf,csf)和(tdt,cdt)分別對其進行統(tǒng)計。在節(jié)點i成功完成報文轉(zhuǎn)發(fā)之后，如果接收節(jié)點j獲得的報文副本數(shù)量大于1，則節(jié)點i對節(jié)點j配置的計數(shù)器tsf將增加，否則計數(shù)器 tdt增加。在節(jié)點 i驗證 Fe成功后，如果節(jié)點j執(zhí)行了擴散傳輸，則記錄S階段的確認報文數(shù)量的計數(shù)器 csf將增加1；如果其執(zhí)行直接傳輸，則計數(shù)器 cdt增加。

按照觀測協(xié)議設(shè)計，報文和傳輸證據(jù) Fe的成功傳輸都會激活該模塊對相關(guān)統(tǒng)計數(shù)據(jù)執(zhí)行操作。該模塊的狀態(tài)機模型以及觀測協(xié)議的處理如圖1所示。節(jié)點處于空閑狀態(tài)，將根據(jù)報文轉(zhuǎn)發(fā)、接收以及傳輸證據(jù)接收等行為而進入相關(guān)處理狀態(tài)；處理完畢將恢復(fù)空閑狀態(tài)。

2.3 信譽路由模塊

信譽路由模塊的設(shè)計主要解決信譽與BSW結(jié)合的問題。信譽提供了一種建立節(jié)點之間信任關(guān)系的有效方式，一種對節(jié)點合作性(或自私性)的度量方式。信譽的引入使得節(jié)點能夠有效分辨自私節(jié)點并給予懲罰，甚至將其排除網(wǎng)絡(luò)。信譽與路由的結(jié)合旨在提高網(wǎng)絡(luò)對自私行為的鑒別度和適應(yīng)度，從而提高網(wǎng)絡(luò)性能。

很多信譽方案的研究工作都集中在對復(fù)雜的數(shù)學(xué)表達式的探索，以期帶來的對節(jié)點自私行為更為精確、快速的評分，然而，卻采用經(jīng)驗型的信譽門限進行判斷[10,12]。DTN信譽的應(yīng)用環(huán)境與 P2P文件共享網(wǎng)絡(luò)存在較大差異。后者的場景中存在大量的報文交互。而 DTN一般配置在一個很大區(qū)域之中，2個特定節(jié)點的交互次數(shù)相對較小。因此，本方案的信譽設(shè)計應(yīng)用判別準(zhǔn)則取代復(fù)雜的計算公式，可以表示為

節(jié)點執(zhí)行報文轉(zhuǎn)發(fā)之前，都會按照判別準(zhǔn)則對轉(zhuǎn)發(fā)節(jié)點進行判定。如果節(jié)點i對節(jié)點j的兩組統(tǒng)計數(shù)據(jù)都超過了設(shè)定門限值，那么認為該節(jié)點是誠實理性的，將按照源BSW方案執(zhí)行路由；如果兩組數(shù)據(jù)中有一組低于設(shè)定門限，則認為節(jié)點j在轉(zhuǎn)發(fā)過程有不良行為發(fā)生。如果節(jié)點j被判定為自私節(jié)點，節(jié)點i將其加入黑名單，并拒絕節(jié)點j的所有轉(zhuǎn)發(fā)請求。同時，生成針對節(jié)點j的控告消息，在報文轉(zhuǎn)發(fā)的過程中進行捎帶，以提醒其他節(jié)點。如果針對節(jié)點j的控告節(jié)點數(shù)目超過一個特定門限值，則該節(jié)點將直接被加入黑名單。因此，在轉(zhuǎn)發(fā)過程中有不良表現(xiàn)的節(jié)點將最終被排除出網(wǎng)絡(luò)。

門限設(shè)定與路由兩個階段的情況直接相關(guān)。S階段要求節(jié)點將多余的報文副本盡快散發(fā)。節(jié)點可以輕易將報文副本分發(fā)完畢。csf/tsf近似于Fe的傳輸概率，可以表示為

其設(shè)定為確認自私行為的一種評判標(biāo)準(zhǔn)。α和PM分別表示容忍參數(shù)和網(wǎng)絡(luò)允許范圍內(nèi)的自私行為比率的上限。保證 α≥1-PM，以避免允許范圍之外的自私節(jié)點逃避檢測。

在 W 階段，要求節(jié)點通過直接傳輸?shù)姆绞綄⑽ㄒ坏膱笪母北巨D(zhuǎn)發(fā)給目的節(jié)點。因此，確認報文的傳輸概率可以表示為

其中，dtP表示報文從轉(zhuǎn)發(fā)節(jié)點到目的節(jié)點的直接傳輸概率。當(dāng)節(jié)點配置傳輸范圍為K的無線設(shè)備時，假設(shè)無線設(shè)備具有較高的傳輸速率且忽略信道干擾，則報文的直接傳輸問題轉(zhuǎn)化為在分布在一定區(qū)域內(nèi)的2個節(jié)點移動到直線距離小于K的范圍內(nèi)的問題。那么，該問題進一步映射為2個節(jié)點之間距離小于K的模型。因此，直接傳輸?shù)母怕蕟栴}最終被轉(zhuǎn)化為在一個廣大區(qū)域2個節(jié)點之間的距離小于K的問題。參考Bettstetter等在隨機路點移動模型(RWP, random waypoint)方面的研究[13]，得到了RWP模型的空間分布函數(shù)，且該分布與速度無關(guān)，該函數(shù)可以表示為

以近似節(jié)點在a×a的正方形范圍之內(nèi)的分布。其中，–a/2≤x≤a/2且–a/2≤y≤a/2。這個表達式非常接近真實仿真里的分布。根據(jù)前述的建模，在同樣的移動模型下，直接傳輸?shù)母怕士梢越Y(jié)合仿真場景得到

根據(jù)仿真場景的參數(shù)得到積分結(jié)果，則門限可以表述為

3 性能仿真

為了驗證增強方案的有效性，基于 ONE仿真平臺[14]，建立4000m×4000m的正方形仿真區(qū)域。按照RWP移動模型，配置250個移動節(jié)點，并設(shè)定其速度為10～50km/h，通信范圍為200m。按照一定比例選擇節(jié)點執(zhí)行自私行為，隨機丟棄轉(zhuǎn)發(fā)報文。在此環(huán)境下，與原始BSW方案進行對比試驗，驗證提出的方案對節(jié)點自私行為的有效性。

圖1 觀測處理模塊的狀態(tài)機模型

通過配置報文副本數(shù)目為4和16，仿真結(jié)果顯示了伴隨自私節(jié)點比率增加，分別應(yīng)用兩種方案的網(wǎng)絡(luò)性能變化。如圖2(a)所示，當(dāng)自私節(jié)點的比率由0%上升為30%時，原始方案的傳輸率由0.86下降為0.59，傳輸效率降低接近27%。由此可知，自私行為嚴重影響了 DTN網(wǎng)絡(luò)的性能。兩條虛線之間的差異同樣值得關(guān)注。低副本數(shù)目BSW方案因為較低的網(wǎng)絡(luò)消耗而在自私節(jié)點比率較低時，相對于高副本數(shù)目配置有一定優(yōu)勢。然而，伴隨自私節(jié)點數(shù)目的增加，高副本數(shù)目的BSW方案因自私行為對報文的丟棄反而有著更優(yōu)的傳輸效率。增強方案的下降趨于緩慢，兩種方案之間的差距隨著自私節(jié)點比率的增加而不斷擴大。在惡意節(jié)點的比率達到30%的時候，增強方案的傳輸效率仍然接近75%。不同于BSW方案，高副本數(shù)目的配置對于有自私行為檢測的增強方案而言，其網(wǎng)絡(luò)消耗一直都是一種浪費和負擔(dān)，因此其性能始終較低。

自私節(jié)點比率的增加使得網(wǎng)絡(luò)中的報文丟棄行為更加頻繁，從而影響到網(wǎng)絡(luò)中存在的副本數(shù)目。而增強方案因為對自私節(jié)點的辨識，一定程度上抑制了對報文的丟棄，反而使得網(wǎng)絡(luò)中副本數(shù)目較多，因而其消耗比率一直比同樣副本數(shù)目配置的原始方案高，如圖 2(b)所示。對于 DTN網(wǎng)絡(luò)的平均延遲和平均緩存時間而言，因為自私節(jié)點對報文的丟棄，使得網(wǎng)絡(luò)實際報文副本數(shù)目較少，因而增大了網(wǎng)絡(luò)成功傳輸?shù)臅r間以及報文的緩存時間，使得其相對于增強方案有著更高的延遲和緩存時間。然而，高副本配置的方案允許更多的網(wǎng)絡(luò)副本能夠盡快散播，大大降低了網(wǎng)絡(luò)整體的報文傳輸時間和緩存時間，因此，高副本配置的方案在平均延遲和緩存時間上有著更多優(yōu)勢，如圖2(c)和2(d)所示。

圖2 伴隨自私節(jié)點比率增加，網(wǎng)絡(luò)各項性能指標(biāo)變化情況

綜上所述，與原有的BSW方案相比，本文提出的增強方案能夠有效的區(qū)分和隔離自私節(jié)點，并且可以更好地容忍節(jié)點的自私行為，實現(xiàn)更佳的網(wǎng)絡(luò)性能。

4 結(jié)束語

信譽與BSW方案的結(jié)合使得增強方案能夠在自私節(jié)點存在的環(huán)境中有效的提高 DTN的性能，并且可以有效的激勵節(jié)點進行正常的網(wǎng)絡(luò)行為，培養(yǎng)節(jié)點之間的信任關(guān)系。節(jié)點的自私行為會導(dǎo)致網(wǎng)絡(luò)的排斥，在一定程度上抑制了自私行為的發(fā)生。延遲容忍網(wǎng)絡(luò)的自私行為模型和信譽應(yīng)用是下一步研究的重點。信譽在DTN中的應(yīng)用仍然是該領(lǐng)域一個開放性問題，值得更多研究者的關(guān)注。

[1]FALL K.A delay-tolerant network architecture for challenged Internets[A].Computer Communication Review[C].Karlsruhe,Germany, 2003.

[2]FALL K, FARRELL S.DTN:an architectural retrospective[J].IEEE Journal on Selected Areas in Communications, 2008, 26(5):828-836..

[3]SPYROPOULOS T, PSOUNIS K, PAGHAVENDRA C S, et al.Spray and Wait:an eff i cient routing scheme for intermittently connected mobile networks[A].ACM SIGCOMM Workshop on Delay-Tolerant Networking(WDTN)[C].USA, 2005.252-259.

[4]YOO Y, AGRAWAL D P, Why does it pay,to be selfish in a MANET[J].IEEE Wireless Communications, 2006, 13(6):87-97.

[5]MARIAS G F, GEORGIADIS P, FLITZANISD, et al.Cooperation enforcement schemes for MANETs:a survey, Wireless Communications& Mobile Computing, 2006,6(3):319-332.

[6]LU R, LIN X D, AHU H J, et al.Pi:a practical incentive protocol for delay tolerant networks[J].IEEE Transactions on Wireless Communications, 2010, 9(4):1483-1493.

[7]ZHU H J, LIN X D, LU R X, et al.SMART:a secure multilayer credit-based incentive scheme for delay-tolerant networks[J].IEEE Transactions on Vehicular Technology, 2009, 58(8):4628-4639.

[8]ZHOU Y, ZHAN H W.An incentive-based reputation mechanism for mobile ad hoc networks[A].20084th International Conference on Wireless Communications, Networking and Mobile Computing[C].Dalian, China, 2008.1-4

[9]ZHOU R F, HWANG K.PowerTrust:A robust and scalable reputation system for trusted peer-to-peer computing[J].IEEE Transactions on Parallel and Distributed Systems, 2007,18(4):460-473.

[10]ZHANG H, PUAN H X, LIU W.RRM:an incentive reputation model for promoting good behaviors in distributed systems[J].Science in China Series F-Information Sciences, 2008, 51(11):1871-1882.

[11]SAKAI R, OHGISHI K, KASAHARA M.Cryptosysytems based on pairing[A].Symposium on Cryptography and Information Security(SCIS)[C].Okinawa, Japan 2000.

[12]GANERIWAL S, BALZANO L K, SRVASTAVA M B.Reputation-based framework for high integrity sensor networks[J].Acm Transactions on Sensor Networks, 2008,4(3):1-37.

[13]BETTSTETTER C, WAGNER C.The spatial node distribution of the random waypoint mobility model[A].German Workshop on Mobile Ad Hoc Networks (WMAN)[C].Ulm, Germany, 2002.

[14]The one simulator.[EB/OL].http://www.netlab.tkk.f i/tutkimus/dtn/theone/.