基于信譽的延遲容忍網絡雙重Spray and Wait增強方案

張希，王曉飛，張權，唐朝京

（國防科學技術大學 電子科學與工程學院，湖南 長沙 410073）

1 引言

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

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

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

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

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

2 提出的方案

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

2.1 系統配置

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

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

2.2 觀測處理模塊

觀測處理模塊的設計主要解決 DTN環境下對節點行為觀測和統計的問題。節點行為的觀測方式是基礎信譽數據采集的關鍵，也是信譽在 DTN環境下應用的瓶頸。頻繁的網絡割裂和機會鏈路的特性導致經典的觀測方式——混雜監聽模式和源路由模式難于應用。混雜監聽模式下，節點緩存發送給鄰居節點的報文，截獲并比對所有通過的報文與原始報文的差異，以未發生偽造和篡改來確定鄰居節點的正常轉發行為。然而，網絡的間歇鏈接特性難以保證對無線鏈路的持續觀測。總是存在一條端到端路徑的假設同樣不適用于DTN，因而導致源路由相關方案的應用困難。

本方案引入轉發證據的概念，設計了對節點行為的觀測協議，將轉發證據的生成與傳播融入觀測協議中，且轉發證據的傳輸可以通過報文進行捎帶，減少了網絡資源的消耗。

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

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

當節點n接收報文和附屬信息后，將執行以下步驟驗證。

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

②驗證Aim時間戳正確性；

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

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

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

驗證通過之后，節點n發送轉發證據Fe給節點m作為其成功轉發報文的響應。Setid包括3個部分的身份信息，即報文轉發節點、接收節點以及需要提供傳輸證據的節點。

節點n選擇下一跳節點，重新計算附屬信息，繼續分發過程。

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

節點p執行同樣驗證過程。驗證通過后，發送傳輸證據Fe給節點n，其中，Setid包含了節點m,n和p的身份信息。

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

節點m確認Fe簽名的正確性之后，確認節點n的轉發行為。該模塊將激活報文確認計數器，對相關統計數據進行操作。

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

按照觀測協議設計，報文和傳輸證據 Fe的成功傳輸都會激活該模塊對相關統計數據執行操作。該模塊的狀態機模型以及觀測協議的處理如圖1所示。節點處于空閑狀態，將根據報文轉發、接收以及傳輸證據接收等行為而進入相關處理狀態；處理完畢將恢復空閑狀態。

2.3 信譽路由模塊

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

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

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

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

其設定為確認自私行為的一種評判標準。α和PM分別表示容忍參數和網絡允許范圍內的自私行為比率的上限。保證 α≥1-PM，以避免允許范圍之外的自私節點逃避檢測。

在 W 階段，要求節點通過直接傳輸的方式將唯一的報文副本轉發給目的節點。因此，確認報文的傳輸概率可以表示為

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

以近似節點在a×a的正方形范圍之內的分布。其中，–a/2≤x≤a/2且–a/2≤y≤a/2。這個表達式非常接近真實仿真里的分布。根據前述的建模，在同樣的移動模型下，直接傳輸的概率可以結合仿真場景得到

根據仿真場景的參數得到積分結果，則門限可以表述為

3 性能仿真

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

圖1 觀測處理模塊的狀態機模型

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

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

圖2 伴隨自私節點比率增加，網絡各項性能指標變化情況

綜上所述，與原有的BSW方案相比，本文提出的增強方案能夠有效的區分和隔離自私節點，并且可以更好地容忍節點的自私行為，實現更佳的網絡性能。

4 結束語

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

[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/.