基于合并的DTN訂閱查詢傳輸協議*

曹 佩，錢江波，陳葉芳，陳華輝

（寧波大學信息科學與工程學院 寧波 315211）

基于合并的DTN訂閱查詢傳輸協議*

曹 佩，錢江波，陳葉芳，陳華輝

（寧波大學信息科學與工程學院 寧波 315211）

DTN是從自組織無線網絡中抽象出來的網絡模型，它不要求網絡的全連通，因此更適合實際自組網的需求。大部分DTN傳輸協議研究的是如何把數據高效、無區分地傳給匯聚點。本文提出的基于合并的DTN訂閱查詢傳輸協議（如SMR），充分利用DTN節點自身的處理能力，能夠在有限的時間內利用節點間的每一次相遇機會盡可能多且有效地傳輸有用信息。實驗結果顯示，隨著傳輸時間的延長，SMR在DTN廣播式訂閱查詢系統和洪泛式訂閱查詢系統中都顯示了良好的性能，增強了DTN訂閱查詢系統的實時性需求。

延遲容忍網絡；訂閱查詢處理；信息合并

1 引言

無線網絡技術的發展促使許多新型無線網絡誕生，如車載網絡、外太空網絡、野生動物追蹤網絡和稀疏傳感器網絡等。這些網絡有一些共同的特點：間歇連接、長時延、不對稱數據速率、低信噪比、端到端的鏈接很多時候都是不存在的。DTN（delay tolerant network，延遲容忍網絡）就是從上述新型網絡中抽象出來的網絡模型。這類網絡利用節點移動帶來的相遇機會實現通信，按照“存儲—移動—轉發”的方式傳輸數據。傳輸方法如圖1所示：①試圖把數據傳送給⑤，但是由于通信距離有限，①無法直接與⑤通信，由于節點的移動，某一時刻①可以與②通信，然后②可以把數據傳給④，④再傳給⑤，從而完成數據的傳輸。

圖1 存儲—移動—轉發的數據傳輸

目前，DTN中數據傳輸協議的絕大部分研究是考慮如何把節點攜帶的數據沒有區分地、盡量地傳送到匯聚節點。但實際應用中單個節點收集的信息種類多，信息接收者可能只想接收某類信息，同時也為減少網絡中傳送的無用數據，此時需配置一種靈活的動態信息分發和處理系統，這樣的系統稱之為發布/訂閱系統。一個傳統網絡的發布/訂閱系統模型由3部分組成：代理節點（broker node）、事件發布者（publisher）、事件訂閱者（subscriber）。發布者以“事件”的形式將信息發布到系統中；訂閱者定義訂閱條件，表示對系統中某特定的事件感興趣。通常發布者首先發布信息給某些信息代理（中間的節點），然后訂閱者向該信息代理注冊訂閱，由信息代理進行過濾。

2 DTN中訂閱查詢處理的相關研究

由于DTN的間斷連通性，傳統的發布/訂閱路由技術在DTN環境下并不適用，目前有關DTN的查詢處理和發布/訂閱系統的研究較少。參考文獻[1]根據DTN的特點給出了 DTSN（delay tolerant sensor network）中發布/訂閱系統的網絡模型，進而提出了一種基于團體的發布/訂閱系統事件傳輸協議——CET協議 （community-based event transmitting protocol）。參考文獻[2]提出了一個 DTN中發布/訂閱通信的社會感知覆蓋。參考文獻[3]提出了一種新的傳輸協議 SPF（short-pass-feedback），它是一種基于時間數據收集、復制、分發的兩階段協議，能夠收集和分析與地理軌道有關的時間開銷。參考文獻[4]中使用DTN綁定協議，目標是使用戶查詢網絡中任意位置上其他節點存儲的內容，并評估節點獲得尋求信息的機會。參考文獻[5]研究了移動系統怎樣利用人們的社會交互性來改善系統性能和查詢命中率，建立了一個跟蹤驅動模擬器，使得人們能夠在社會環境下重建移動系統。參考文獻[6]用數據擴散減少DTN中的查詢時延，利用社會網絡追蹤分類以及研究社會網絡中以同質性現象為基礎的4種擴散方法。參考文獻[7]提出了一種新穎的方法支持DTN中的協同緩存，該方法以概率選擇為度量來協調多個緩存節點響應用戶查詢，優化平衡了數據訪問和緩存開銷。本文的訂閱查詢處理是指訂閱者發布的訂閱信息 （以下簡稱為查詢信息）中包含了某些查詢條件，系統節點之間在進行信息傳輸的過程中要根據訂閱信息進行查詢處理。與原有的發布/訂閱系統相比，本文的訂閱查詢處理系統側重于如何依據訂閱者發布的查詢信息進行信息傳輸。

大多數DTN的數據傳輸協議都要用到復本，利用復本進行傳輸又分為兩類：不限制復本的傳輸，典型代表就是ER(epidemic routing)[8]；限制復本的傳輸，典型代表是SWR(spray and wait routing)[9]。ER本質上是一種洪泛算法，每兩個節點相遇時都會交換對方沒有的信息。每個節點都會把攜帶的信息轉發給遇到的所有鄰居節點，讓網絡中盡可能多的節點存儲信息的復本，目的是提高信息的投遞概率，最終把信息傳輸給匯聚節點。如圖1中①把某一條信息傳給②后，下一時刻①、③相遇，③如果沒有收到此條信息，①可以繼續把該信息傳給③。SWR傳輸每條信息分為兩個階段：第一階段是spray階段，節點將信息分發到N（N為一條信息的最大拷貝數）個不同的、沒有存儲該信息的代理節點；第二階段是wait階段，N個不同的代理節點負責等待，直到把該信息轉發給目的節點。SWR的數據傳輸方式如圖2所示：源節點S想把某一信息傳給目的節點D，但它不能直接與D通信。假定復本數為3，第一階段S把信息轉發給沒有存儲該信息的前3個節點R，第二段由這3個R節點負責轉發該信息給D。

圖2 SWR數據傳輸協議示意

與原有的研究成果相比，本文的貢獻主要體現在以下兩方面。

·提出了DTN訂閱查詢傳輸協議SMR，該協議充分利用了節點自身的信息處理能力，能夠有效地降低傳輸時延，提高傳輸效率。

·模擬實現了廣播式訂閱查詢處理模型和洪泛式訂閱查詢處理模型。在這兩種模型下，SMR與傳統的DTN傳輸協議做了比較，實驗結果顯示，SMR性能明顯優于傳統的DTN傳輸協議。

3 網絡模型

假設網絡系統為一個二維區域，網絡模型如圖3所示。其中，灰色的節點為訂閱節點（subscribe node），在系統中充當訂閱者，也是發布信息的目的節點，主要用來發布查詢信息和收集自身感興趣的信息，當它需要某些特定信息時，就會生成查詢信息發布到系統中；黑色節點是信息發布節點（publish node），發布某些特定的信息，而且能夠生成符合查詢條件的信息；透明節點為代理節點，在系統中充當代理，主要是在保存自身事件信息的同時，負責協助查詢信息和發布信息的傳輸。

圖3 網絡模型示意

系統中每個節點都有一個信息隊列，用來存儲自身信息，每種信息都包含5個域，信息產生節點From，表示信息由哪個節點產生；信息目的節點To，表示一條信息最終應被傳送給哪個節點；信息產生的Id，表示一條信息區分其他信息的編號；信息字段MegField，表示信息域；信息的Size，表示信息大小。一條信息的結構如圖4所示。

圖4 信息的結構

根據訂閱節點傳輸信息距離的長短，訂閱查詢處理可以分為兩類：廣播式訂閱查詢處理和洪泛式訂閱查詢處理。廣播式訂閱查詢處理中，訂閱節點能夠傳輸查詢信息的距離很長；洪泛式訂閱查詢處理中，訂閱節點傳輸查詢信息的距離較短。

廣播式訂閱查詢處理的過程主要分為以下3個步驟。

（1）訂閱節點廣播查詢信息，代理節點和信息發布節點都可以收到此查詢信息。

（2）信息發布節點收到查詢信息后，如果自身能夠與訂閱節點通信，則直接把發布信息傳送給訂閱節點，否則先把發布信息傳送給代理節點，通過代理節點的幫助按照一定的數據傳輸協議（如SWR、ER）把發布信息反饋給訂閱節點。

（3）代理節點在接收一條信息之前，首先根據所接收查詢信息的查詢條件，判斷是不是訂閱節點所要接收的發布信息。如果是則接收，不是則丟棄。

洪泛式訂閱查詢處理的過程主要分為以下兩個步驟。

（1）訂閱節點生成查詢信息后，通過洪泛方式向其他節點發送，其他節點收到查詢信息后，亦通過洪泛方式向鄰居節點傳輸。

（2）每個節點準備接收一條信息時，首先檢測是不是查詢信息（檢測的依據為信息是否包含查詢條件）,檢測過程分為以下兩種情況。

·如果是則接收，然后檢測其信息隊列中有沒有符合查詢條件的信息。如果沒有，保存此查詢信息；如果有而節點又能夠直接與訂閱節點通信，就直接把信息傳送給訂閱節點，否則通過其他節點按照一定的數據傳輸協議尋找合適的機會傳送。

·如果不是，則檢測其信息隊列中是否保存有查詢信息。如果沒有，丟棄；如果有，需要與隊列中現存的查詢信息的查詢條件進行比對，判斷此信息是不是符合查詢條件的信息。如不符合則丟棄；如符合則先保存，等待合適的機會按照一定的數據傳輸協議進行傳送。

DTN的訂閱查詢系統要解決的關鍵問題是如何使訂閱者通過發布查詢高效、可靠地收集自己感興趣的信息。訂閱事件的收集成功率是最主要的設計目標，同時還要考慮事件信息的平均傳輸時延。

4 基于合并的DTN訂閱查詢傳輸協議SMR

因為DTN中節點間的相遇機會及通信時間都非常有限，所以要想在DTN中實現實時性比較難。如果想提高DTN中節點的數據信息傳輸效率、降低傳輸時延、增強實時性，可以充分利用節點自身處理能力，而以往DTN中的數據傳輸協議較少涉及DTN系統中的這些處理能力。

下面以A、B兩個節點之間的傳輸過程 （節點A與節點B建立連接，節點B向節點A傳送數據）為例，講述SMR的具體傳輸過程。其中，Id表示一個節點信息隊列中某一信息的編號，ID表示一個節點信息隊列中所有信息編號的集合，S表示某一集合，AddTo(Id,S)表示把某一編號對應的信息加入相應的集合，Delete(Id,S)表示從相應的集合中刪除某一編號對應的信息，Merger(Id1,Id2)表示合并兩個編號對應的信息，ST表示信息傳輸集合，SM為合并信息集合，SQ表示一個節點信息隊列中存儲的信息集合。具體的傳輸過程如下所述。

（1）節點A與節點B建立連接后，節點A檢測B.ID中的每一個B.Id，如果它不在A.ID中，節點B執行AddTo(B.Id,B.ST)。

（2）傳輸開始后，節點B傳輸B.ST中的信息到節點A。

（3）如果B.ST中某一B.Id對應信息的目的節點恰好為節點A，則在傳輸完成之后節點B執行Delete(B.Id,B.SQ），并且節點B會通知其他信息監聽節點此信息已被傳送到目的節點。整個數據傳輸過程如圖5所示。

圖5 SMR傳輸信息過程

（4）在節點A與節點B的傳輸結束，而節點A的下一次傳輸開始之前：如果節點A的信息隊列中沒有存儲訂閱者發布的查詢信息，則節點A直接等待下次信息傳輸，否則節點A需要對部分信息進行合并操作。合并過程分為信息查找和信息合并兩個步驟。

信息查找：節點A根據其信息隊列中存儲的查詢信息的查詢條件，對于每一個A.Id對應的信息，如果它符合查詢條件，則節點A執行AddTo（A.Id,A.SM）。信息查找過程如圖6第一階段所示。

信息合并：節點A對A.SM中的信息按照加入集合的先后順序進行合并，合并操作如圖6第二階段所示。合并操作分為以下5個步驟。

①節點 A 執行 Merger（A.SM.Id1,A.SM.Id2）后，判斷合并后信息的Size是否小于系統中信息的最大Size（目的是為了防止合并信息過長，一次相遇無法傳輸完而導致合并信息在傳輸過程中被丟棄，不能夠被接收節點接收）。

②如果小于信息的最大Size，節點A執行Delete（A.SM.Id1,A.SM）、Delete（A.SM.Id1,A.SQ）、Delete（A.SM.Id2,A.SM）、Delete（A.SM.Id2,A.SQ）后繼續合并上次合并后的信息與A.SM中的下一條信息。

③如果等于信息的最大Size，節點A停止合并，并把合并后的信息插入其信息隊列中，同時節點A執行Delete（A.SM.Id1,A.SM）、Delete（A.SM.Id1,A.SQ）、Delete（A.SM.Id2,A.SM）、Delete（A.SM.Id2,A.SQ），其余信息返回步驟①繼續合并。

圖6 信息合并過程

④如果大于信息的最大Size，則節點A會返回上一次合并后的信息，并把該信息插入其信息隊列中，其余信息返回步驟①繼續合并。

⑤重復步驟①、②、③、④、⑤，直至A.SM為空。

（5）如果節點A為訂閱節點，收到一條滿足其查詢條件的合并信息后，節點A需對此合并信息進行分割還原，獲取原信息。

通過對隊列中的信息進行合并操作，同時利用信息傳輸過程的代理節點及目的節點的自身處理能力，可以充分利用每次傳輸機會，使得一次能夠傳輸多條信息，從而縮短傳輸時延。

5 模擬實驗

利用第3節的網絡模型，筆者模擬采用ER、SWR、SMR 3種數據傳輸協議實現DTN中的廣播式訂閱查詢及洪泛式訂閱查詢，主要是查詢具有某個字段（MegField）的信息。從以下3個方面對實驗結果及性能進行分析。

·從整個系統訂閱節點成功訂閱信息的數目（即同等情況下事件的查詢結果）方面進行性能的比較。

·從系統中成功訂閱信息的平均傳輸延遲方面進行性能比較。

·SMR最大合并信息數目對其系統性能的影響。

5.1 實驗環境

實驗的軟件環境為Windows XP+JDK1.60+ONE+Eclipse-SDK-3.7.2-Win32。ONE[10]是一款專門針對 DTN的模擬器，它是基于離散事件模擬引擎的，每一步模擬時引擎都會更新許多模塊，從而實現整個模擬的功能。硬件環境 為 Intel Core2 Quad Q8400@2.66 GHz （4CPU），3 GB RAM的計算機。

實驗系統的區域面積為4500 m×3400 m，總共有31個節點，其中訂閱節點個數為1，代理節點個數為10。訂閱節點移動方式為random walk（節點持續選擇一個隨機的方向和速度移動），其余節點移動方式為random way point，即節點的移動重復3個步驟：首先，節點在網絡中隨機選取一個點；接著，節點隨機選擇一個速度朝著選取的方向移動；最后，節點在選取的點的位置上隨機停留一段時間。隊列的管理按照先進先出原則，廣播式訂閱查詢的廣播寬度覆蓋整個系統區域，其他實驗參數見表1，其中，預熱時間為仿真正式開始前系統中節點移動的時間。

表1 實驗參數

5.2 實驗結果

在同等網絡環境及配置下，改變仿真時間，利用ER、SWR、SMR 3種數據傳輸協議實現的廣播式訂閱查詢處理及洪泛式訂閱查詢處理，得到不同的實驗結果。盡管采用不同的訂閱查詢處理方式，但相同時間內系統中信息發布節點生成的符合查詢條件的總信息數目都是一樣的，因此，各個仿真時間與系統中生成的符合查詢條件的總信息數見表2。

表2 仿真時間與符合查詢條件的總信息數

成功訂閱信息數目為一定仿真時間內，訂閱節點成功接收到的符合其查詢條件的不同信息的數目。從圖7中可以看出，系統利用3種傳輸協議實現的2種訂閱查詢處理中，訂閱節點成功訂閱的信息數目均隨著仿真時間的延長而增加，但是在同樣的時間內同一種訂閱查詢處理中，采用SMR時訂閱節點成功訂閱的信息，比采用前兩種數據傳輸協議時訂閱節點成功訂閱的信息要多。這是因為SMR能夠有效地利用節點自身及節點間處理能力，根據訂閱查詢要求對有效信息進行合并操作，充分利用了節點之間的每次相遇機會增加有效信息傳輸量。對比分析圖 7（a）和圖 7（b），可以發現，同等情況下采用3種傳輸協議實現的洪泛式訂閱查詢處理中，SMR的性能優勢更加明顯。這是因為洪泛式訂閱查詢處理中，訂閱節點發布的查詢信息也需要借助其他節點進行傳輸，使系統中有效信息的傳輸條件更加苛刻，節點之間相遇且能夠傳輸有效信息的機會更加少，從而突出了SMR能夠充分利用節點間的每次相遇機會傳輸更多有效信息量這一特點。

圖7 成功訂閱信息數

成功訂閱信息的時延均值為成功訂閱的所有信息被訂閱節點接收的平均時延，如訂閱節點總共收到10條符合其查詢條件的不同信息，接收最后一條信息的時間距離系統開始仿真的時間為2 h，那么平均時延為0.2 h。由圖8可以看出，采用ER和SMR實現的兩種訂閱查詢處理中，成功訂閱信息的時延均值均隨著仿真時間的延長而縮短。這是因為仿真時間短時有些符合查詢條件的信息沒有被訂閱節點成功接收。采用SWR實現的兩種訂閱查詢處理中，成功訂閱信息的時延均值都呈現了一定的波動。這是因為SWR中每條信息的復本數目有限，節點自身也沒有對信息進行處理，同等情況下系統中訂閱節點成功接收到的訂閱信息數目有限，信息到達的時間會有不定的時延。對比分析圖 8（a）和圖 8（b），可以看出，SMR 實現的兩種訂閱查詢處理中，成功訂閱信息的延遲均值都是最短的，這還是因為 SMR能夠有效利用每次傳輸機會增加有效信息的傳輸量。

通過分析訂閱節點成功訂閱的信息數和成功訂閱信息的時延均值，可以得出，在訂閱查詢傳輸條件越嚴格的情況下，訂閱查詢時間越長，SMR性能越突出。

在本文提出的DTN中信息大小為500 KB、采用SMR仿真，仿真時間為22 h、網絡中信息的最大Size超過系統中最大信息傳輸量（500 kbit/s）時，不斷改變最大信息合并數所得的訂閱結果如圖9（a）所示。從圖中可以看出，當網絡中信息的最大Size超過系統中最大信息傳輸量，兩種訂閱查詢處理中信息最大合并數都為3時，同樣的時間內訂閱節點成功訂閱的信息數最大；當信息最大合并數大于3時，同樣的時間內訂閱節點成功訂閱的信息數明顯降低。這說明上述系統中當網絡中信息的最大Size超過系統中最大信息傳輸量時，把信息的最大Size定為信息Size的3～4倍時，能體現SMR的最佳性能。由此可以看出，并不是網絡節點每次傳輸的信息量越大，SMR的性能越佳。

圖8 成功訂閱信息的延遲均值

圖9 最大合并信息數與成功訂閱信息

信息大小為100 KB，采用SMR仿真，仿真時間為22 h，限制網絡中信息的最大Size超過系統中最大信息傳輸量時，不斷改變信息合并數所得的訂閱結果如圖9（b）所示。從圖中可以看出，當網絡中信息的最大Size不超過系統中最大信息傳輸量，廣播式訂閱查詢處理中信息的最大合并數為3時，訂閱節點成功訂閱的信息數最大；在洪泛式訂閱查詢處理中信息的最大合并數為2或3時，訂閱節點成功訂閱的信息數都是最大的。由此可以看出，并不是網絡中節點每次傳輸的信息量都達到系統中最大信息傳輸量時，才能使SMR體現最佳性能。之所以出現上述各種現象，是因為在DTN中采用SMR實現訂閱查詢處理時，最佳信息合并數目 （取得最佳訂閱結果的信息合并數）與DTN中節點緩存的大小、節點的數據傳輸率、節點的移動速度、節點的移動模式以及系統中信息本身大小等網絡參數都密切相關。

通過上述分析可以看出，在DTN中采用SMR進行信息傳輸時，存在一個信息最佳合并數值K，本文提出的DTN模型中，筆者通過反復實驗，得出K值為3，但在實際的網絡模型中，需要根據不同的實際情況調整K值，獲取最佳通信效果。

6 結束語

與傳統的無線網絡相比，DTN具有的獨特特性使得傳統的各種無線網絡中的數據傳輸協議不能適用于DTN，為了有目的、高效地進行DTN中的信息收集，本文提出了一種新的數據傳輸協議SMR，同時實現了兩種適用于DTN的訂閱查詢處理協議。但是，由于SMR沒有考慮能量方面的消耗，未來可考慮適合在能量敏感的DTN中進行信息收集的協議，同時考慮在復雜DTN環境下的訂閱查詢的實現。

1 朱金奇，劉明，龔海剛等.延遲容忍傳感器網絡中面向發布/訂閱系統的事件傳輸.軟件學報,2010,21（8）

2 Eiko Yoneki,Pan H,Chan S Y,et al.A socio-aware overlay for publish/subscri becommunication in delay to lerantnet works.Proceedings of the 2007 ACM MSWiM,Chania,Greece,2007

3 Rudi Ball,Naranker Dulay.Approximating travel times using opportunistic networking.Proceedings of International Conference on Advanced Information Networking and Applications Workshops,London,United Kingdom,2009

4 Pitkanen M,Karkkainen T,Greifenberg J,et al.Searching for content in mobile DTNs.Proceedings of IEEE International Conference on Pervasive Computing and Communications,Galveston,Texas,USA,2009

5 Andrew G M,Kiran K G,Kelvin K W C,et al.Exploiting social interactions in mobile systems.Proceedings of the 9th International Conference on Ubiquitous Computing,Innsbruck,Austria,2007

6 Zhang Y,Zhao J.Social network analysis on data diffusion in delay to lerantnet works.Proceedings of the Tenth ACM International Symposium on Mobile Ad Hoc Networking and Computing,Louisiana,USA,2009

7 Gao W,Cao G H,Arun Iyengar,et al.Supporting cooperative caching in disruption tolerant networks.Proceedings of 31st International Conference on Distributed Computing Systems,PA,USA,2011:151～161

8 Becker V D.Epidemic Routing for Partially Connected Ad Hoc Networks.Technique Report,CS-2000-06,Department of Computer Science,Duke University,Durham,NC,2000

9 Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks.Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking,Philadelphia,USA,2005

10 Ari Keranen,Jorg Ott,Teemu Karkkainen.The ONE Simulator for DTN Protocol Evaluation.SIMTools，2009

Merger-Based Subscription Query Transport Protocol in DTN

Cao Pei,Qian Jiangbo,Chen Yefang,Chen Huahui
(College of Information Science and Engineering,Ningbo University,Ningbo 315211,China)

DTN is a network model derived from self-organizing wireless networks.It is suitable for actual needs of self-organizing networks because it does not require network’s full connectivity.How to efficiently transport data to sink node without distinction is being considered in most studies of DTN transport protocols.A DTN’s merger-based subscription query transport protocol was presented,called SMR,which fully utilizes the processing capacity of the nodes themselves in the system.Experiment results show that the SMR protocol performs better than ER and SWR protocols in both DTN broadcast subscription query system and DTN flooding subscription query system.SMR could be a good candidate to enhance the real-time demand of DTN subscription query system.

delay tolerant network,subscribe query processing,message merger

10.3969/j.issn.1000-0801.2013.03.013

* 國家自然科學基金資助項目（No.60973047），浙江省自然科學基金資助項目（No.Y109118），浙江省科技廳基金資助項目（No.2011C21076），浙江省教育廳基金資助項目（No.Y201120729），寧波市自然科學基金資助項目（No.2012A610065）

book=325,ebook=325

曹佩，女，寧波大學信息科學與工程學院碩士研究生，主要研究方向為延遲容忍網絡的查詢處理等。

錢江波，男，博士，寧波大學信息科學與工程學院教授，主要研究方向為數據庫、數據流、邏輯電路設計等。

陳葉芳，女，寧波大學信息科學與工程學院講師，主要研究方向為數據流處理等。

陳華輝，男，博士，寧波大學信息科學與工程學院教授，主要研究方向為數據流處理和數據挖掘等。

2013-01-27）