基于路由考慮的人群網(wǎng)絡(luò)分類探索

盧華庭， 徐 亮， 王貴竹

（安徽大學(xué) 計算智能與信號處理教育部重點實驗室，安徽 合肥 230039）

0 引言

容遲網(wǎng)絡(luò)是一個新興的研究領(lǐng)域，由 Kevin Fall等人首次提出。在這種網(wǎng)絡(luò)中，端到端的路徑并不一直穩(wěn)定存在，甚至可能一直不會出現(xiàn)。節(jié)點之間的連接經(jīng)常是斷斷續(xù)續(xù)的，而且有著較大的延遲。傳統(tǒng)的基于 TCP/IP路由協(xié)議通常不適用于這種網(wǎng)絡(luò)[1-2]。因此，研究者提出了各種DTN網(wǎng)絡(luò)中的路由算法，例如基于報文拷貝傳輸?shù)?Epidemic、散發(fā)-等待路由以及基于先驗知識的MED、ED、EDLQ、EDAQ等[3-4]。由于人群網(wǎng)絡(luò)中人的移動性導(dǎo)致網(wǎng)絡(luò)拓撲結(jié)構(gòu)時刻變化，有時會具有容遲網(wǎng)絡(luò)的特點。因此，人群網(wǎng)絡(luò)也屬于容遲網(wǎng)絡(luò)的研究范疇。

1 相關(guān)工作介紹

文獻[5]中，作者提出了路由度和節(jié)點度的概念，通過對Dartmouth學(xué)院收集到的學(xué)生網(wǎng)絡(luò)的數(shù)據(jù)進行研究，提出在路由設(shè)計時，如果能夠事先知道這些節(jié)點，可能會大大改善網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)难舆t和成功率。文獻[6]中，作者通過多倫多大學(xué)搜集的學(xué)生蹤跡分析，提出了鏈路-狀態(tài)路由協(xié)議。文獻[7]中，作者提出嵌套2跳路由算法（2-MH＊），并在相關(guān)項目所搜集的人群移動蹤跡上進行了仿真、性能分析。在文獻[8]中，作者提出對無線移動網(wǎng)絡(luò)進行分類，根據(jù)端到端之間的連接性能由好到壞，依次為SPN、strictU -DTN 、U-DTN、strict A-DTN、A-DTN。由于人群網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化性，一個特定的路由算法很難一直保持好的性能。因此，基于對路由算法設(shè)計的考慮，我們提出應(yīng)首先對人群網(wǎng)絡(luò)的變化規(guī)律進行分類，然后在不同的時間段使用不同的適當(dāng)?shù)穆酚伤惴ǎ词褂枚喾N路由算法切換機制，從而在整體上提高網(wǎng)絡(luò)的路由性能。

2 人群網(wǎng)絡(luò)分類探索

根據(jù)現(xiàn)實中人的移動及分布情況，我們假定：人群網(wǎng)絡(luò)的分布特點以天為單位不斷循環(huán)。因此，本文提出在研究人群網(wǎng)絡(luò)中路由算法時，根據(jù)節(jié)點間建立連接的路徑類型，對人群網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行分類。根據(jù)文獻[8]中對無線移動網(wǎng)絡(luò)的分類定義，本文提出把人群網(wǎng)絡(luò)的變化分為3類：空間路徑網(wǎng)絡(luò)（Space-Path Networks）、無需輔助節(jié)點網(wǎng)絡(luò)(U-DTN：unassisted DTN)、需要（或帶有）輔助節(jié)點網(wǎng)絡(luò)(A-DTN：assistance-needed DTN)。本文以社區(qū)人群網(wǎng)絡(luò)的分布特點為例，介紹人群網(wǎng)絡(luò)的分類。

2.1 空間路徑網(wǎng)絡(luò)

在社區(qū)人群網(wǎng)絡(luò)中，上、下班時間段，節(jié)點移動活躍，節(jié)點與節(jié)點之間碰面的概率很大，節(jié)點的分布有利于報文的傳輸。此時，在一個時刻，網(wǎng)絡(luò)中節(jié)點與節(jié)點之間直接或者通過多跳可以建立起端到端的空間連接[8]，并能維持通信所需要的時間?t。在這種情況下，適合采用MANET網(wǎng)絡(luò)中基于端到端連接的AODV等路由協(xié)議。如圖1所示：源端A發(fā)報文給目的端B，可以通過空間路徑建立端到端的連接。

圖1 空間路徑網(wǎng)絡(luò)模型

2.2 無需輔助節(jié)點網(wǎng)絡(luò)

在上午、下午工作時間段，社區(qū)內(nèi)節(jié)點數(shù)目相對減少，而且部分節(jié)點趨于靜止，部分節(jié)點移動。此時，網(wǎng)絡(luò)中大部分節(jié)點間不能通過多跳建立空間路徑。需要利用人的移動性，在可容忍時間t內(nèi)，在源端和目的端之間通過建立時空路徑[8]來傳輸報文。如圖2所示：源端A傳報文給目的端B，但是在當(dāng)前時刻tk，A與B之間并不能通過多跳建立端到端的連接。此時，節(jié)點A將報文傳給中間節(jié)點C，經(jīng)過一段可容忍時間t，利用節(jié)點C的移動性，當(dāng)其到達與節(jié)點B能進行通信的范圍內(nèi)，將報文傳遞給 B。在這種情況下，適合采用MEED、MED等基于先驗知識的路由算法。

圖2 無需輔助節(jié)點網(wǎng)絡(luò)模型

2.3 需要輔助節(jié)點網(wǎng)絡(luò)

在夜晚時間段，此時，人群網(wǎng)絡(luò)分為一個個小群體（例如人群分布在2棟居民樓內(nèi)）。在小群體之間，由于移動節(jié)點稀少，無法在可容忍時間t內(nèi)，在源端和目的端之間建立時空路徑，如圖 3所示。在這種網(wǎng)絡(luò)拓撲結(jié)構(gòu)下，群體之間的通信無法取得較好性能。為此，人們提出利用擺渡節(jié)點、數(shù)據(jù)騾子等輔助節(jié)點，在一定程度上改善網(wǎng)絡(luò)中的路由性能。

圖3 需輔助節(jié)點網(wǎng)絡(luò)模型

2.4 人群網(wǎng)絡(luò)變化規(guī)律

由于人群網(wǎng)絡(luò)拓撲結(jié)構(gòu)以天為單位周期性變化，針對人群網(wǎng)絡(luò)中路由算法的研究，本文提出利用人群網(wǎng)絡(luò)的變化規(guī)律，對人群網(wǎng)絡(luò)按照時間段進行細化。采用多種路由機制，在不同時間段間進行切換，有利于改善網(wǎng)絡(luò)的路由性能。

圖4給出了社區(qū)網(wǎng)絡(luò)網(wǎng)絡(luò)類型變化循環(huán)圖。由于人的日常生活規(guī)律及其移動性，該網(wǎng)絡(luò)類型按照圖中所示數(shù)字順序循環(huán)變化。這給設(shè)計多路由算法循環(huán)切換機制帶來了可行性。需說明的是，由于網(wǎng)絡(luò)中節(jié)點的移動性，人群網(wǎng)絡(luò)劃分為哪種類型，并不是指在該時間段內(nèi)任意時刻都屬于該類型，而是指大部分時間段以該類型為主。

圖4 社區(qū)網(wǎng)絡(luò)類型變化循環(huán)

3 結(jié)語

在對人群網(wǎng)絡(luò)的研究中，使用一種固定的路由算法，往往并不能一直保持較好的性能。針對這個問題，本文提出新的思路，根據(jù)人群網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化規(guī)律，對人群網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行分類，這對人群網(wǎng)絡(luò)路由算法設(shè)計具有重要的指導(dǎo)意義。在今后的工作中，將根據(jù)真實的人群網(wǎng)絡(luò)移動蹤跡情況進行分析實現(xiàn)，并通過仿真比較多路由算法機制切換機制與單一路由算法機制在延遲、遞交率、網(wǎng)絡(luò)上節(jié)點存儲占用開銷等方面的性能。

[1] 樊秀梅,單志廣,張寶賢,等.容遲網(wǎng)絡(luò)的體系結(jié)構(gòu)及關(guān)鍵技術(shù)[J].電子學(xué)報,2008,36(01):161-170.

[2] 閆魯生,劉尚麟.容斷網(wǎng)絡(luò)技術(shù)在岸海數(shù)據(jù)通信中的應(yīng)用研究[J].通信技術(shù),2009,42(12):197-200.

[3] 陳 飄,盧漢成,李津生,等.用于延時可容忍網(wǎng)絡(luò)的增強型 MED路由算法[J].計算機工程,2007,33(11):90-98.

[4] 趙玲,劉占軍,李云,等.DTN中基于傳染路由的節(jié)點擁塞控制策略[J].通信技術(shù),2009,42(02):136-140.

[5] Roth M,Vidales P.Defining and Exploiting Network Topologiesin Human Networks[C]//World of Wireless,Mobile and Multimedia Networks,2007.Helsinki,Finland:IEEE International Symposium,2007:1-6.

[6] Su J,Goelt A,Lara E de.An Empirical Evaluation of the Student-Net Delay Tolerant Network[R].San Jose, California: 2006 Third Annual International Conference, 2006.

[7] Conan V,Leguay J,Friedman T.Fixed Point Opportunistic Routing in Delay Tolerant Networks[C]//IEEE Journal on Selected Areas in Communications. La Jolla,California:IEEE,2008:773-782.

[8] Borrel V,Mostafa H A, Zegura E W.Understanding the Wireless and Mobile Network Space:A Routing-centered Classification[C]//Proceedings of the second ACM workshop on Challen-ged Networks.New York:ACM,2007:11-18.