摘 要: 在“ferry”概念的基礎上，提出容遲網絡中一種新的路由算法CB-NIMF（Cluster-Based Node Initiated Message Ferrying），在該算法下，利用普通節點之間的網絡拓撲結構和通信能力，縮短了數據采集網絡中普通節點向“ferry”移動的非正常工作時間，降低了隱性的數據丟失，增加了節點的工作時間以及采集的數據量。?
關鍵詞: 容遲網絡； ferry； 簇； 路由
?
Internet作為當今全球信息交互的工具，無疑已經取得了巨大的成功。它使用了大量的通信協議（TCP/IP協議族）來確保通信的正常工作。組成Internet的成千上萬的子網內的所有設施都使用這些協議來進行數據路由以及確保信息交換的可靠性。不過，Internet上工作的協議都是基于一個假設才能正常工作的：所有的通信鏈路都穩定地、不間斷地連接在一起。近幾年，無線傳感器網絡、移動Ad-Hoc網絡等發展迅速，不過這類網絡都存在著相同的問題，即網絡的鏈路連接是間斷性的，傳統Internet上的協議并不能直接使用。針對以上問題，FALL K于2003年在參考文獻[1]中給出了一個解決該問題的框架，即DTN網絡。之后，關于DTN網絡的研究越來越受到重視[2-6]。
2004年， ZHAO Wen Rui提出了“ferry”的概念[2]： “ferry”的移動路徑是固定的，不存在隨機性，該路徑稱為路由路徑，并且假設網絡中的其他正常節點只產生數據，并不參與路由過程。“ferry”路由的基本思想是：整個網絡的路由由快速移動的“ferry”節點完成，當經過某一個節點時，“ferry” 節點從該節點上獲取要傳輸的數據，然后沿著路由路徑移動。當遇到目的節點時，把數據傳輸給目的節點。在參考文獻[2]中，提出了一種普通節點和“ferry”節點信息通信的路由算法：NIMF(Node-Initiated Message Ferrying)。在NIMF路由算法中，當節點上有數據要傳輸時，它將停止當前工作并向“ferry”的路由路徑移動；在“ferry”節點要傳輸數據給普通節點時，也需要普通節點移動到“ferry”的路由路徑。如圖1所示，其中黑點表示節點，黑色方塊表示“ferry”，實圓圈是“ferry”的路由路徑。當有數據傳輸時，所有節點都會獨自按照最短的距離移動到圓圈的位置，然后等待“ferry”。
?
當一個用于數據采集的DTN網絡使用NIMF進行路由時，可以把數據丟失分為兩部分：由于路由超時而導致的數據丟失,對此本文稱之為顯性數據丟失；由于節點移動,節點離開工作地點到再次返回工作地點這段時間稱為節點的非正常工作狀態，由此導致的數據丟失本文稱之為隱性數據丟失。如果節點離 “ferry”路由路徑很遠，往返的時間將會嚴重影響數據采集的正常工作，隱性數據丟失問題將會比較嚴重，其影響甚至可能超過了顯性數據的丟失。而且，隨著網絡規模的增大，節點數目增多，這種損失就會越大。針對NIMF在節點移動時間上的缺陷，本文利用節點之間的網絡結構，將節點按位置先組成一個個簇，并且在簇內建立一個邏輯樹，讓節點也參與數據路由，以減少網絡中節點的移動時間，從而有效降低節點因移動而導致的隱性數據丟失。由于節點的非正常工作時間減少，因節點處于正常工作狀態的時間就會相應增多，這也增大了節點在固定時間內的數據采集量。
1 CB-NIMF的設計
當網絡規模比較大，節點和“ferry”路由路徑離得較遠時，節點的非正常工作時間會比較長，因此會造成隱性數據丟失問題。對此，本文提出一種新的路由: CB-NIMF。在一個用于數據收集的DTN網絡中，節點分布一般會有一定的規律，比如，在比較重要的區域，一般會有較多的節點，即節點的分布一般是不均勻的，很容易形成一個個區域簇。在這些簇內，各個節點和路由路徑的距離是不相同的，有些離節點很近甚至就在節點的路由路徑上，而有些節點則離得比較遠。CB-NIMF利用網絡中節點與“ferry”路由路徑之間距離的差異讓普通節點也進行數據路由工作，盡量減少由于節點移動而導致的隱性數據丟失。在CB-NIMF中，對“ferry”的功能進行一定的強化。“ferry”除了進行數據路由之外，還將進行網絡分簇并替簇內的節點建立一個邏輯樹。
1.1 分簇
在CB-NIMF中，假設每個節點都知道了“ferry”的路由路徑，同時都能準確定位自己在網絡中所處的位置——可以通過GPRS之類來獲得。在布置網絡的時候，每個節點首先獲取自己的位置坐標，計算與“ferry”路由路徑之間的距離，然后通過一次長距離的通信，將該坐標和距離發送給“ferry”節點?！癴erry”在收集到網絡中節點的坐標位置后，根據節點的位置分布，將距離比較靠近的節點分配成一個簇。如圖2所示，其中虛線圓圈覆蓋的范圍是一簇。當某個節點位于兩個簇之間時，“ferry”節點將根據以下方法來確定將該節點加入哪一個簇：
(1)當某個簇A中不存在與該節點距離比較小的節點，
而在另一個簇B中存在與該節點距離較小的節點時，“ferry”將會把該節點加入簇B的樹。
(2)當該節點在２個網絡簇中都存在與它距離差不多一樣的節點時，“ferry”節點將分別比較該節點在２個樹中的深度，同時選擇將其加入深度較小的那個邏輯樹所在的簇。如果該節點在兩棵邏輯樹中的深度一樣時，“ferry”將會把該節點加入節點數目較少的那個簇。
?
1.2 邏輯樹的形成
當“ferry”接收到所有節點的坐標，并把節點分配到相應的簇之后，它將根據節點與自己路由路徑的距離，建立一棵邏輯樹。首先，簇中距離最小的節點將會成為該簇與“ferry”通信的門節點。以門節點為根，將簇內其他所有節點以距離為因素來組成邏輯樹:在形成的樹中，父節點與“ferry”路由路徑的距離總是比其子節點與“ferry”路由路徑的距離要短。為了使簇內所有節點的移動距離總和最小化，可以使用Prim算法來生成一棵最小生成樹。在成功建立了樹之后，“ferry”替每個節點計算它們各自在樹中的深度，然后用深度來標記節點。如果2個節點在樹中的深度一樣，就稱這2個節點在樹中屬于同一層次。然后，“ferry”把節點的深度以及其父節點和子節點的坐標位置都通過一次長距離通信發送給節點。最終結果如圖3所示，其中虛圓包圍的是簇，a、b、c、d、e是各個簇的門節點，虛線形成的是一個邏輯樹。
?
1.3?網絡中的數據傳輸
??? 當把網絡分成N個簇之后，整個網絡中的數據傳輸主要可以分為兩類：簇內數據傳輸和簇間數據傳輸。當一個節點有數據需要傳輸時，它首先判斷目的節點和自己是不是屬于同一個簇，如果是同一個簇內的節點，則按照簇內數據傳輸的方式進行路由。發送節點首先判斷自己與目的節點之間深度的大小，當目的節點深度比自己小時，發送節點將向父節點移動，把數據傳輸給父節點后返回原位置正常工作；當目的節點深度比自己大時，發送節點將向自己一個子節點移動，把數據傳輸給自己的子節點后返回原位置正常工作；當目的節點深度和自己一樣時，發送節點將向與自己最為臨近的同層次節點移動，數據傳輸完成后返回原位置正常工作。
當發送節點和目的節點不屬于同一個簇時，路由過程將經由門節點和“ferry”來完成。當一個簇內有節點要傳輸數據后，它將會向父節點移動，在與父節點相遇后，把數據傳輸給父節點，然后返回原位置開始正常工作；而父節點在接收到數據后，將會開始新一輪的路由選擇過程，這一過程將一直持續到數據到達門節點。當門節點要傳輸數據時，它將會向“ferry”的路由路徑移動，成功地把數據傳輸給“ferry”后，返回正常工作。而“ferry”將會把要路由的數據按照目的節點所在簇分類，當遇到一個簇的門節點時，將所有目的節點位于該簇內的數據轉發給該門節點。然后該門節點將按照簇內數據路由的過程將接收到的數據發送到各個目的節點。如圖4所示，其中路徑1屬于簇內數據傳輸，不需經過 “ferry”；路徑2屬于簇間數據傳輸，經由門節點和“ferry”來完成。
?
2 節點平均的非正常工作時間?
在CB-NIMF路由方式中，筆者把普通節點N的非正常工作時間分成兩個部分TNm和TNw,其中，TNm是節點N移動到父節點所需要的時間，這個時間當網絡初始化完成之后就是固定不變的，可以用兩個節點之間的距離來衡量；TNw是節點N在父節點的初始位置等待父節點的時間。這樣，節點N的非正常工作時間為：
對于門節點，Tw是 “ferry” 沿路由路徑移動一圈所需時間的一半。假設“ferry”移動一圈所需要的時間是T，則門節點的平均等待時間Tw=T/2。那么門節點移動一次的非工作時間的平均值是：
??? 
??? 從上述不等式(9)右邊的最后一項可以看出，在簇內層次越高的節點，其移動時間受“ferry”路由周期的影響就越低。事實上，當n≥3時，T/(2×4n)≤T/192，當且僅當Twk=Tab時取等號，而且，在一個正常工作的網絡中， Twk>>Tab，則不等式的最后一項其分母將會變得更大，因此，可以認為當節點在簇內的層次k≥3之后，節點的非正常工作時間就與“ferry” 的路由周期關系不大，甚至可以忽略 “ferry”的路由周期的影響，只與節點間的距離有關而已。
3 仿真結果
??? 本文使用了C語言實現了CB-NIMF的仿真過程。為了簡化非正常工作時間的分析，在仿真過程中，并沒有把能量和延遲等因素考慮在內。
??? 系統概述：
在假設的DTN網絡模型中，所有節點隨機分布在網絡內， “ferry” 的路由路徑是固定的。
(1)將整個網絡分成50×50的方格，只有處于同一個方格內的節點才能進行正常通信。
(2)每個節點都擁有與 “ferry”進行長距離通信的能力，不過由于長距離通信消耗的能量比正常通信消耗的能量大得多，節點只會在網絡初始化時期通過該長距離通信向 “ferry”通知自己的坐標數據以及從 “ferry”處獲取初始化信息。
(3)在模型中，ferry每一個系統時間前進一個單位格，即ferry在當前的方格只停留一個單位時間，普通節點只有與ferry處于同一方格內才能進行普通數據傳輸。
(4)每個節點的移動速度是每個單位時間可以前進一個單位格，包括斜對角方向的單元格。
為了比較網絡中節點數目導致的NIMF和CB-NIMF兩種算法節點移動時間的差異，當網絡中節點數目分別為10、25、50、75、100、125、150、175、200時，分別仿真了兩種算法下節點的移動時間，結果如圖5所示:當網絡中節點數目較少時，CB-NIMF和NIMF 兩種方式中的總節點移動時間相差不多，但是隨著網絡中節點數目增加，CB-NIMF 方式下總節點移動時間將會比NIMF方式下總節點移動時間越來越少，也就是說，當節點數目比較大的時候，CB-NIMF比NIFM具有明顯的優勢。這也與前面的分析一致，當節點的數目增多，簇內節點的數目相應增多，高層次的節點將會增加，而層次越高的節點，其非正常工作時間與“ferry”路由周期T的關系就越小，甚至可以說只與節點間的距離有關。而在一個基于NIMF的DTN網絡中，每個節點的非正常工作時間都與 “ferry” 路由周期T密切相關，導致網絡中所有節點的非正常工作時間總和與節點數目以及T成正比。
當節點數目較少時，每次簇內的節點會比較少甚至可能只有1~2個節點存在。因為本算法規定每個簇內只有一個節點能與“ferry” 節點進行直接通信，如果簇內節點很少時，采用CB-NIMF方式并不合適。不過，一般用于數據采集的傳感器網絡，其節點數目都比較多。而從前面的研究中看出，隨著網絡中節點數目的增加，CB-NIMF的優勢也會逐漸增加。因此，CB-NIMF相比較于NIMF還是有巨大優勢的。
本文針對用于數據采集且基于“ferry”的容遲網絡中采用NIMF路由時節點移動時間過長的缺陷，根據網絡中普通節點也可以進行數據路由以及網絡分布的特點，提出新的基于簇的路由算法CB-NIMF，理論推導和仿真結果說明，CB-NIMF能有效地減少節點的移動時間，從而增加節點在固定時間內的數據采集量。
參考文獻
[1] ?FALL K. A delay-tolerant network architecture for challenged internets. In Proc.SIGCOMM 2003,2003.
[2] ?ZHAO Wen Rui. Mostafa ammer ellen zegura. A message ??ferrying approach for data delivery in sparse mobile Ad?Hoc networks. In ACM MobiHoc 2004,2004.
[3]?GU Y, BOZDAG D, EKICI E, et al. Partitioning based?mobile element scheduling in wireless sensor networks. In?Proc.2nd Annual IEEE Conference on Sensor and Ad Hoc ?Communications and Networks,2005.
[4]?ZHAO W, AMMAR M, ZEGURA E. Controlling the?mobility of multiple data transport ferries in a delay-tolerant?network. In Proc.INFOCOM 2005,2005.
[5]?JEA D,SOMASUNDARA A, SRIVASTAVA? M. Multiple?controlled mobile elements(data mules) for data collection
?in sensor networks. In DCOSS 2005,2005.
[6]?ZHANG Zhen, FEI Zong Ming. Route design for multiple?ferries in delay tolerant networks. Wireless Communications?and Networking Conference, 2007. WCNC IEEE, 2007.