基于路由考慮的人群網絡分類探索

盧華庭， 徐 亮， 王貴竹

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

0 引言

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

1 相關工作介紹

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

2 人群網絡分類探索

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

2.1 空間路徑網絡

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

圖1 空間路徑網絡模型

2.2 無需輔助節(jié)點網絡

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

圖2 無需輔助節(jié)點網絡模型

2.3 需要輔助節(jié)點網絡

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

圖3 需輔助節(jié)點網絡模型

2.4 人群網絡變化規(guī)律

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

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

圖4 社區(qū)網絡類型變化循環(huán)

3 結語

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

[1] 樊秀梅,單志廣,張寶賢,等.容遲網絡的體系結構及關鍵技術[J].電子學報,2008,36(01):161-170.

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

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

[4] 趙玲,劉占軍,李云,等.DTN中基于傳染路由的節(jié)點擁塞控制策略[J].通信技術,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.