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