一種適用于移動(dòng)對(duì)等網(wǎng)絡(luò)的分簇算法

楊忠儀，左 克

(1.國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073;2.湖南商務(wù)職業(yè)技術(shù)學(xué)院,湖南 長(zhǎng)沙 410205)

1 引言

硬件技術(shù)的快速發(fā)展使得移動(dòng)終端體積更小、更便攜、續(xù)航能力更強(qiáng);同時(shí),無線通信帶寬和范圍的增長(zhǎng)，使得原本為有線網(wǎng)絡(luò)設(shè)計(jì)運(yùn)行的應(yīng)用能夠逐漸部署運(yùn)行在無線網(wǎng)絡(luò)中。上述變革為移動(dòng)對(duì)等網(wǎng)絡(luò)MP2P(Mobile Peer-to-Peer)的存在和發(fā)展提供了可能[1～7]。

然而，移動(dòng)網(wǎng)絡(luò)的振動(dòng)性給MP2P網(wǎng)絡(luò)的網(wǎng)絡(luò)壽命及其路由性能帶來了挑戰(zhàn)。圖1描述了節(jié)點(diǎn)移動(dòng)對(duì)路由產(chǎn)生的影響。圖中有三個(gè)移動(dòng)節(jié)點(diǎn)A、B、C。箭頭指出節(jié)點(diǎn)的移動(dòng)方向，圓圈范圍表示節(jié)點(diǎn)的有效通訊范圍。節(jié)點(diǎn)移動(dòng)之前的路由情況如圖1a所示，從節(jié)點(diǎn)A到節(jié)點(diǎn)C存在兩條有效路由：多跳路由A-B-C或者一跳路由A-C；節(jié)點(diǎn)移動(dòng)之后的路由情況如圖1b所示，從節(jié)點(diǎn)A到節(jié)點(diǎn)C的有效路由只有多跳路由A-B-C。因此，需要設(shè)計(jì)一個(gè)高效的分簇算法，不但能夠在MP2P網(wǎng)絡(luò)中快速部署，還要有效管理、維護(hù)移動(dòng)節(jié)點(diǎn)組織結(jié)構(gòu)，敏捷反映MP2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，延長(zhǎng)網(wǎng)絡(luò)壽命。

Figure 1 Challenges of the MP2P network performance stability opposed by node mobility圖1 節(jié)點(diǎn)移動(dòng)性給MP2P網(wǎng)絡(luò)性能穩(wěn)定性帶來挑戰(zhàn)

層次性結(jié)構(gòu)(Hierarchical Architecture)作為一種經(jīng)典有效的節(jié)點(diǎn)組織方式，被廣泛使用在構(gòu)造大規(guī)模移動(dòng)網(wǎng)絡(luò)節(jié)點(diǎn)組織上；同時(shí)，分簇算法(Clustering)被認(rèn)為是一種有效的處理網(wǎng)絡(luò)壽命的機(jī)制。當(dāng)前MP2P網(wǎng)絡(luò)中廣泛使用分層管理機(jī)制來設(shè)計(jì)分簇算法[5,7,8]，研究人員通常根據(jù)已有的無線網(wǎng)絡(luò)類型和結(jié)構(gòu)化P2P抽象覆蓋網(wǎng)絡(luò)來設(shè)計(jì)MP2P系統(tǒng)以及節(jié)點(diǎn)管理機(jī)制[4,6,9]。近年來，Kautz圖[10,11]及其特殊的屬性，諸如優(yōu)化的網(wǎng)絡(luò)直徑、高效路由特性、較好的連通性和低擁塞等特性逐漸吸引MP2P研究者的注意，思考如何將這些優(yōu)秀的特性應(yīng)用到MP2P這類計(jì)算和帶寬資源均受限的特定環(huán)境中[11～13]；同時(shí)，以Kautz圖為原理開發(fā)的路由協(xié)議和應(yīng)用系統(tǒng)不斷涌現(xiàn)，例如，使用MP2P構(gòu)造的文件共享系統(tǒng)，能夠充分利用各個(gè)移動(dòng)終端的數(shù)據(jù)和存儲(chǔ)資源，在無線和移動(dòng)網(wǎng)絡(luò)上節(jié)點(diǎn)之間根據(jù)對(duì)不同數(shù)據(jù)類型的需求以及地理位置信息的不同進(jìn)行文件的直接共享和交換，實(shí)現(xiàn)靈活高效的數(shù)據(jù)共享，典型系統(tǒng)包括Google Open Spot和Nokia PeerBox 。此外，在開放環(huán)境(如在校園、野外、戰(zhàn)地和受災(zāi)地區(qū)等缺乏固定通信基礎(chǔ)設(shè)施的環(huán)境)中利用MP2P技術(shù)實(shí)現(xiàn)高效快捷的文件發(fā)布和共享，也是當(dāng)前重要的應(yīng)用，如Stanford校園Fring系統(tǒng)。

在本文中，我們基于Kautz圖及其特性設(shè)計(jì)了一個(gè)有效的分簇算法，并結(jié)合網(wǎng)絡(luò)路由協(xié)議VRR(Virtual Ring Routing)[9]進(jìn)行了實(shí)現(xiàn)和驗(yàn)證。本文的主要貢獻(xiàn)有：首先，依據(jù)Kautz空間，定義了可擴(kuò)展的地址空間樹和節(jié)點(diǎn)Kautz串標(biāo)識(shí)符；接著我們給出了分簇算法并理論證明了該算法的有效性，算法使用后根序和寬度優(yōu)先搜索算法遍歷地址空間樹，通過理論證明了設(shè)計(jì)的算法能夠滿足層次性結(jié)構(gòu)需要的特性；第三，設(shè)計(jì)了分簇算法管理和維護(hù)機(jī)制，以應(yīng)對(duì)網(wǎng)絡(luò)振動(dòng)問題；最后，通過路由協(xié)議驗(yàn)證和評(píng)估了分簇算法的有效性。

2 定義與定理

2.1 Kautz圖和地址樹

首先，給出Kautz圖的定義。

由Kautz圖的定義可知，其節(jié)點(diǎn)數(shù)接近Moore邊界[10]，最多可由N=dD+dD+1個(gè)節(jié)點(diǎn)構(gòu)成。另外，相比其他圖，Kautz圖還具有某些特性，諸如網(wǎng)絡(luò)直徑較短、有容錯(cuò)和負(fù)載平衡能力等。所有這些特性使得P2P網(wǎng)絡(luò)的設(shè)計(jì)者更多傾向于使用Kautz圖作為構(gòu)造P2P網(wǎng)絡(luò)的圖論基礎(chǔ)。下面根據(jù)Kautz串定義地址空間和地址樹。

定義2假設(shè)T(d,D)代表Kautz圖K(d,D)的地址樹，從上至下T(d,D)共分D+1層，其中只有第0層的根節(jié)點(diǎn)有d+1個(gè)子節(jié)點(diǎn)，樹中的其他節(jié)點(diǎn)只有d個(gè)子節(jié)點(diǎn)。從節(jié)點(diǎn)u到子節(jié)點(diǎn)的邊從非負(fù)整數(shù)集{0,1,…,d}選擇標(biāo)記，按照從左至右增序排列，并且要求標(biāo)記序列中沒有重復(fù)標(biāo)記。因此，除了根節(jié)點(diǎn)標(biāo)記為null，每個(gè)節(jié)點(diǎn)標(biāo)記是由從根節(jié)點(diǎn)到自身的邊的標(biāo)記組成的標(biāo)記串，即Kautz串。地址空間樹的所有葉節(jié)點(diǎn)的Kautz串，代表實(shí)際的空間地址集合。

圖2給出K(2,3) 和對(duì)應(yīng)的地址空間T(2,3)。圖2中，節(jié)點(diǎn)A的標(biāo)記是[010]，節(jié)點(diǎn)B的標(biāo)記是[021]，節(jié)點(diǎn)C的標(biāo)記是[x1x]，節(jié)點(diǎn)D的標(biāo)記是[20x]，x代表尚未確定，當(dāng)節(jié)點(diǎn)最終加入到地址樹葉節(jié)點(diǎn)后，x才會(huì)被確定。具體的節(jié)點(diǎn)加入過程將在第3.2.1節(jié)和第3.2.2節(jié)中詳細(xì)給出。

Figure 2 K(2,3)and space address tree of T(2,3)圖2 K(2,3)和對(duì)應(yīng)的地址空間T(2,3)

2.2 分簇算法

我們的算法實(shí)現(xiàn)在VRR(Virtual Ring Routing)[9]路由協(xié)議之上。作為第一個(gè)采用DHT(Distributed Hash Table)特點(diǎn)設(shè)計(jì)的網(wǎng)絡(luò)層路由協(xié)議，VRR根據(jù)隨機(jī)產(chǎn)生的非負(fù)整數(shù)標(biāo)志，將節(jié)點(diǎn)組織成一個(gè)虛擬環(huán)。而且，VRR中沒有設(shè)計(jì)網(wǎng)絡(luò)協(xié)議普遍采用的泛洪(Flooding)算法，因此VRR能夠獲得比其他路由協(xié)議更好的性能。

為了設(shè)計(jì)分簇算法，需要對(duì)VRR進(jìn)行兩方面的修改。首先，我們使用Kautz地址空間中的節(jié)點(diǎn)標(biāo)識(shí)替代VRR中隨機(jī)產(chǎn)生的非負(fù)整數(shù)標(biāo)識(shí)；第二，我們需要在路由表中添加一個(gè)標(biāo)識(shí)位flag，以標(biāo)注簇首。大多數(shù)移動(dòng)網(wǎng)絡(luò)中的分層cluster結(jié)構(gòu)普遍采用簇首[14～16]設(shè)計(jì)。我們的算法中，指定節(jié)點(diǎn)標(biāo)識(shí)K(d,D)的數(shù)值大小最接近MooreBound/2的節(jié)點(diǎn)作為簇首。 簇首節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)cluster內(nèi)所有節(jié)點(diǎn)信息，同時(shí)cluster內(nèi)每個(gè)節(jié)點(diǎn)會(huì)在自己的路由表中標(biāo)注簇首節(jié)點(diǎn)為ch_flah。

算法的執(zhí)行過程就是尋找Kautz圖K(d,D)中擴(kuò)展樹的過程。通過后根序和寬度優(yōu)先算法遍歷地址樹T(d,D)的方式，我們將Kautz圖中的所有節(jié)點(diǎn)進(jìn)行分簇。在算法的執(zhí)行過程中，必須保證標(biāo)識(shí)數(shù)值大小接近的節(jié)點(diǎn)被分在同一個(gè)簇內(nèi)，以便于之后快速構(gòu)造虛擬環(huán)。下面列出了算法中使用的簡(jiǎn)寫以及含義：

(1)非負(fù)整數(shù)k：用來約束每個(gè)簇的大小?？紤]到負(fù)載平衡和容錯(cuò)，產(chǎn)生的所有簇的大小必須能夠產(chǎn)生有效的路由。因此，我們?cè)O(shè)計(jì)最小的簇的大小等于最大簇的大小的一半。

(2)T：Kautz圖K(d,D)對(duì)應(yīng)的地址空間樹。

(3)T(x)：T的子樹，節(jié)點(diǎn)x作為子樹的根節(jié)點(diǎn)。

(4)Q：隊(duì)列類型的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)簇中的節(jié)點(diǎn)。采用隊(duì)列類型數(shù)據(jù)結(jié)構(gòu)而非其他數(shù)據(jù)結(jié)構(gòu)，因?yàn)槲覀儾坏枰褂藐?duì)列的FIFO方式保存節(jié)點(diǎn)信息，而且還可以為之后構(gòu)造虛擬環(huán)帶來便利。

(5)C：隊(duì)列型數(shù)據(jù)結(jié)構(gòu)，用于合并分簇。

(6)ClusterSet：算法產(chǎn)生的簇集合。

(7)UnpChildren：存儲(chǔ)某個(gè)節(jié)點(diǎn)尚未被分到某個(gè)簇中的所有子節(jié)點(diǎn)。

(8)PartialClusterSet：存儲(chǔ)當(dāng)前大小小于k的分簇集合。

(9)?：表示空集合。

下面的偽代碼對(duì)算法進(jìn)行了詳細(xì)的描述:

算法1Kautz-based Clutering (K,k)

1 foru∈K, in post-order travel ofT

2 if (|T(u)|≥k) then

3Q:=?;

4UnpChildren:=Children(u);

5 whileUnpChildren≠? and (?v∈UnpChildren,s.t.xhas an edge tow∈Children(u)∩Q) do

6 Enqueue nodes ofT(v)inQby the order from large to small and mark the one whose identifier is closest toMooreBound/2ofK(d,D)as clusterhead;

7 RemovevfromUnpchildren;

8 end while

9 if(|Q|≥k)then

10 OrganizeQas a virtual ring;

11ClusterSet:=ClusterSet∪Q;

12 Remove all substrees inQ;

13 else

14PartialClusterSet:=PartialClusterSet∪Q;

15 end if

16C:=MergeParticalClusterSet(u,k,PartialClusterSet,Q);

17 ifChildren(u):=? and (uhas been assigned to some cluster) then

18 Removeufrom the tree;

19 end if

20 end if

21ClusterSet:=ClusterSet∪C;

22 end for

算法2MergePartialClusterSet(u,k,P,ClusterSet)

1C:=?;

2 While (P≠?) do

3 Pick an arbitrary partial clusterpfromP;

4C:= orderly sorting nodes inCandpin the same order ofC;

5 RemovepfromP;

6 if (|C|≥k)then

7ClusterSet:=ClusterSet∪{C∪{u}};

8 Remove all subtrees inC;C:=?;

9 end if

10 end while

2.3 算法屬性證明

本節(jié)我們形式化證明算法的特性，這些特性為之后在實(shí)驗(yàn)評(píng)估中取得較好的測(cè)試結(jié)果提供了理論證明。

定理1算法保證所有節(jié)點(diǎn)都會(huì)被分配到某個(gè)簇中。

證明對(duì)任意節(jié)點(diǎn)u，如果u屬于某個(gè)子樹，則算法1的第4行保證他的所有子節(jié)點(diǎn)都已經(jīng)被分配到UnpChildren。UnpChildren中所有子樹的節(jié)點(diǎn)會(huì)被保存在隊(duì)列Q中，算法1的第11行保證Q中的每個(gè)節(jié)點(diǎn)最終被分配到某個(gè)簇中。證畢。

□

定理2算法保證每個(gè)簇中節(jié)點(diǎn)會(huì)被組織成一個(gè)邏輯環(huán)。

證明根據(jù)算法1的第6、第10行，可以得到該屬性。數(shù)據(jù)結(jié)構(gòu)隊(duì)列Q保證了該屬性的實(shí)現(xiàn)。證畢。

□

定理3算法保證任意兩個(gè)分簇之間只有一個(gè)公共節(jié)點(diǎn)。

證明我們采用反證法。如果存在兩個(gè)公共節(jié)點(diǎn)，則根據(jù)Kautz圖K(d,D)，這兩個(gè)簇不可能同時(shí)存在于一個(gè)地址空間樹T(d,D)中，因此定理3成立。證畢。

□

定理4算法保證只可能有一個(gè)簇的大小小于k，其他所有簇的大小介于k和2k之間。

證明算法1的第10～第16行中，ClusterSet中的簇大小均大于或等于k；同時(shí)PartialClusterSet中的簇大小小于k。如果存在兩個(gè)簇的大小小于k，則他們將會(huì)在算法2的第6行中被合并，因此只可能有一個(gè)簇的大小小于k，其他所有簇的大小介于k和2k之間。

對(duì)P中的任意簇p，如果算法1第10行沒有滿足條件，則其大小小于或等于k-1。算法2中，簇會(huì)被合并成大小為2(k-1)-1=2k-1，仍然小于2k，因而定理4成立。證畢。

□

2.4 算法收斂性分析

為分析算法1的收斂性，我們先分析算法2的收斂性。算法2的第3行、第4行和第7行的執(zhí)行為常數(shù)時(shí)間，第5行和第8行時(shí)間較少可忽略，因此算法2的時(shí)間收斂性主要依賴于P的大小，也就是PartialClusterSet的大小。因此，算法2的時(shí)間收斂性為O(n)。

算法1的收斂性的分析如下：從算法的偽代碼可知，算法的收斂性主要取決于第6行和第10行，其中第10行的收斂性由VRR得知是O(n/(rp))，其中，n為節(jié)點(diǎn)數(shù)，r是移動(dòng)終端通信半徑，p是路由長(zhǎng)度；算法的第6行約束p的大小為MooreBound/2ofK(d,D)，而d和D均小于或等于n。因此，我們?cè)O(shè)計(jì)的路由協(xié)議相比VRR而言，收斂性更好。

3 算法的實(shí)現(xiàn)

3.1 簇的產(chǎn)生

簇由上一節(jié)算法的分布式版本產(chǎn)生，當(dāng)出現(xiàn)虛擬環(huán)段時(shí)觸發(fā)算法執(zhí)行。算法執(zhí)行完畢時(shí)，會(huì)根據(jù)之前的約束從每個(gè)環(huán)段的節(jié)點(diǎn)中挑選出簇首，接著在簇中每個(gè)節(jié)點(diǎn)的路由表中用ch_flag進(jìn)行標(biāo)注。如果多個(gè)簇首同時(shí)觸發(fā)簇的產(chǎn)生過程，則每個(gè)簇首需要根據(jù)自己的標(biāo)識(shí)去發(fā)現(xiàn)地址空間樹的信息。因此，必須在簇首之間傳遞地址空間樹的發(fā)現(xiàn)數(shù)據(jù)，以便快速找出到地址空間樹根節(jié)點(diǎn)的最短路徑。

3.2 節(jié)點(diǎn)的加入和退出

當(dāng)將傳統(tǒng)的P2P協(xié)議思想應(yīng)用到MANET(Mobile Ad Hoc Networks)中時(shí)，往往因?yàn)橐苿?dòng)網(wǎng)絡(luò)節(jié)點(diǎn)的暫不可達(dá)性、受限的資源(例如電能)或是節(jié)點(diǎn)移動(dòng)性產(chǎn)生的網(wǎng)絡(luò)振動(dòng)和分割問題，實(shí)際使用時(shí)獲得的性能普遍不理想。VRR協(xié)議設(shè)計(jì)了簡(jiǎn)單的雙向故障檢測(cè)機(jī)制，能夠有效地發(fā)現(xiàn)上述問題并且修復(fù)路由狀態(tài)，保證虛擬環(huán)始終保持一致。基于VRR，我們?cè)O(shè)計(jì)了一系列有效的機(jī)制以應(yīng)對(duì)在維護(hù)簇結(jié)構(gòu)時(shí)面臨的網(wǎng)絡(luò)問題。

3.2.1 節(jié)點(diǎn)加入

準(zhǔn)備加入的節(jié)點(diǎn)u首先申請(qǐng)獲得一個(gè)全局惟一的Kautz串標(biāo)識(shí)S，之后周期地廣播加入請(qǐng)求，尋找已經(jīng)加入網(wǎng)絡(luò)并活躍的物理鄰居節(jié)點(diǎn)，作為加入網(wǎng)絡(luò)并獲取路由信息的代理節(jié)點(diǎn)。找到代理節(jié)點(diǎn)之后，u首先產(chǎn)生從代理節(jié)點(diǎn)到自身標(biāo)識(shí)S的路由，該路由按照后根序遍歷地址空間樹，并最終抵達(dá)一棵子樹，該子樹根節(jié)點(diǎn)W的標(biāo)識(shí)是u標(biāo)識(shí)S的前綴。接著W會(huì)發(fā)起一個(gè)join信息。從節(jié)點(diǎn)W開始，如果當(dāng)前節(jié)點(diǎn)有一個(gè)帶有大量未分配地址段的鄰居節(jié)點(diǎn)，則將join信息推送到該鄰居節(jié)點(diǎn)。該推送過程會(huì)一直持續(xù)，直到j(luò)oin信息抵達(dá)某個(gè)節(jié)點(diǎn)V，節(jié)點(diǎn)V沒有一個(gè)帶有大量未分配地址段的鄰居節(jié)點(diǎn)。接著，節(jié)點(diǎn)u被分配到包含節(jié)點(diǎn)V的簇中。接下來考慮簇的大小是否滿足約束條件，此時(shí)存在四種需要考慮的情況。最簡(jiǎn)單的情況是若此時(shí)簇的大小小于2k-1，且新加入的節(jié)點(diǎn)u不會(huì)成為新的簇首(Clusterhead)，則只要簡(jiǎn)單地將節(jié)點(diǎn)u加入到簇虛擬環(huán)的適當(dāng)位置即可；第二種情況，若當(dāng)且僅當(dāng)節(jié)點(diǎn)u成為新的簇首，則啟動(dòng)簇首替換過程；如果簇的大小大于2k-1，不論新加節(jié)點(diǎn)u的標(biāo)識(shí)是多少，當(dāng)前簇都需要被分隔成兩個(gè)新簇；加入簇后，新節(jié)點(diǎn)u需要初始化自身的路由表，并且更新同簇鄰居節(jié)點(diǎn)的路由表。

3.2.2 節(jié)點(diǎn)退出

當(dāng)有節(jié)點(diǎn)u脫離網(wǎng)絡(luò)，可根據(jù)自身的標(biāo)識(shí)采用兩種不同的機(jī)制完成。如果節(jié)點(diǎn)u是某個(gè)簇中的普通節(jié)點(diǎn)，他只需要簡(jiǎn)單地脫離網(wǎng)絡(luò)，我們使用VRR中已有的故障檢測(cè)和修復(fù)機(jī)制來維護(hù)虛擬環(huán)的一致性。如果節(jié)點(diǎn)u是簇首節(jié)點(diǎn)，則需要計(jì)算簇的新簇首，不過這個(gè)計(jì)算過程需要保證是非中斷式的，因?yàn)樾鹿?jié)點(diǎn)帶來的路由更新信息將在簇中傳播，而且所有被更新路由信息的節(jié)點(diǎn)地址不能被修改。

4 算法的實(shí)現(xiàn)

基于網(wǎng)絡(luò)模擬器NS-2.4[17]，我們?cè)u(píng)估了設(shè)計(jì)的分簇算法性能。實(shí)驗(yàn)中模擬的節(jié)點(diǎn)規(guī)模為200，均勻分布在300×300的正方形區(qū)域上。每次模擬隨機(jī)選擇兩個(gè)節(jié)點(diǎn)進(jìn)行路由，然后計(jì)算100次實(shí)驗(yàn)數(shù)據(jù)的平均值。每次實(shí)驗(yàn)運(yùn)行1 000 s，采樣最后的500 s作為評(píng)估值，不采樣之前500 s的實(shí)驗(yàn)數(shù)據(jù)是為了保證路由協(xié)議運(yùn)行達(dá)到穩(wěn)定狀態(tài)。同時(shí)，我們將路由協(xié)議VRR[18]和分簇路由協(xié)議的性能進(jìn)行了對(duì)比。

實(shí)驗(yàn)設(shè)計(jì)為：針對(duì)MP2P系統(tǒng)在校園網(wǎng)絡(luò)和車載網(wǎng)絡(luò)兩種典型環(huán)境中，研究手持移動(dòng)設(shè)備在不同速度模式下協(xié)議的性能。我們?cè)O(shè)計(jì)了低移動(dòng)(模擬在校園網(wǎng)絡(luò)中個(gè)人手持移動(dòng)設(shè)備時(shí)的速度，比如慢跑)和高移動(dòng)(車載網(wǎng)絡(luò)時(shí)的速度)兩種測(cè)試場(chǎng)景：低移動(dòng)場(chǎng)景中節(jié)點(diǎn)的移動(dòng)速度為5 m/s，高速移動(dòng)場(chǎng)景中節(jié)點(diǎn)的移動(dòng)速度為20 m/s。進(jìn)一步，我們分別測(cè)試了在網(wǎng)絡(luò)規(guī)模增加和載荷增加情況下協(xié)議的性能。

Figure 3 Performance with increasing number of CBR flows in high mobility圖3 低速情況下載荷增加時(shí)的性能

Figure 4 Performance with increasing number of CBR flows in high mobility圖4 高速情況下載荷增加時(shí)性能

在低速的情況下，一開始三種協(xié)議都能夠獲得較好的數(shù)據(jù)發(fā)送比率和低延遲，隨著載荷的增加，數(shù)據(jù)發(fā)送比率也隨之增加。圖3顯示，我們?cè)O(shè)計(jì)的分簇路由協(xié)議能夠獲得更低的延遲和更高的數(shù)據(jù)發(fā)送比率，這是因?yàn)镵autz圖的特點(diǎn)以及簇大小約束條件能保證更好的負(fù)載平衡。高速場(chǎng)景下的測(cè)試情況如圖4所示，從圖4中也能得到和圖3類似的結(jié)論。進(jìn)一步比較我們?cè)O(shè)計(jì)的分簇路由協(xié)議能獲得優(yōu)于VRR的性能，這是因?yàn)楫?dāng)網(wǎng)絡(luò)振動(dòng)問題頻繁出現(xiàn)時(shí)，分簇算法能夠保證路由協(xié)議具有更好的可擴(kuò)展性。

圖5和圖6顯示了當(dāng)保持載荷不變，增加節(jié)點(diǎn)數(shù)目對(duì)路由協(xié)議性能的影響。圖5中，當(dāng)節(jié)點(diǎn)數(shù)小于80時(shí)，我們?cè)O(shè)計(jì)的分簇路由協(xié)議能獲得較高的數(shù)據(jù)發(fā)送比率和較低的延遲。隨著節(jié)點(diǎn)數(shù)的增加，數(shù)據(jù)分發(fā)比率逐漸降低，延遲增加。相比其他兩個(gè)協(xié)議，我們?cè)O(shè)計(jì)的分簇路由協(xié)議能夠獲得更好的數(shù)據(jù)發(fā)送比率和延遲。高速場(chǎng)景下，圖6也顯示出和圖5相同的結(jié)論。

Figure 5 Performance with increasing size in low mobility圖5 低速情況下節(jié)點(diǎn)增加時(shí)性能

Figure 6 Performance with increasing size in high mobility圖6 高速情況下節(jié)點(diǎn)增加時(shí)性能

5 結(jié)束語

在本文中，我們根據(jù)Kautz圖設(shè)計(jì)了一個(gè)有效的分簇算法：首先定義了地址空間樹，接著使用Kautz結(jié)構(gòu)定義節(jié)點(diǎn)標(biāo)識(shí)，再使用后根序和寬度優(yōu)先算法遍歷地址空間樹產(chǎn)生簇。實(shí)驗(yàn)結(jié)果表明，與VRR和MADPastry相比我們的分簇算法能夠獲得更低的網(wǎng)絡(luò)延遲、更好的可擴(kuò)展性和性能。當(dāng)面對(duì)MP2P網(wǎng)絡(luò)的節(jié)點(diǎn)移動(dòng)和網(wǎng)絡(luò)振動(dòng)問題時(shí)，使用我們?cè)O(shè)計(jì)的分簇算法能夠表現(xiàn)出更好的總體性能。

[1] Zhang Shi-le, Wei Fang, Fei Zhong-chao. Study on architecture of video transmission optimisation on mobile internet[J]. Computer Applications and Software,2012,29(4):106-108. (in Chinese)

[2] Ni Ping, Wei Fang. A method for improving data pattern readability in wireless sensor networks[J]. Computer Applications and Software, 2012,29(10):148-151. (in Chinese)

[3] Chen Gui-hai,Li Hong-xing,Han Song,et al.Network coding-aware multipath routing in multi-hop wireless networks[J]. Journal of Software,2010,21(8):1908-1919. (in Chinese)

[4] Pucha H, Das S M, Hu Y C. Imposed route reuse in ad hoc network routing protocols using structured peer-to-peer overlay routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2006,27(12):1452-1467.

[5] Hu Y C, Das S M, Pucha H. Exploiting the synergy between peer-to-peer and mobile ad hoc networks[C]∥Proc of Workshop on Hot Topics in Operating Systems, 2003:37-42.

[6] Pucha H, Hu Y C. Ekta:An efficient DHT substrate for distributed applications in mobile ad hoc networks[C]∥Proc of the 6th IEEE Workshop on Mobile Computing Systems and Applications, 2004:163-173.

[7] Hu Y C, Das S M, Pucha H. Peer-to-peer overlay abstractions in MANETs[C]∥Proc of the 1st International Workshop on Decentralized Rosoune Sharing in Mobile Computing Networking, 2004:845-864.

[8] Gerla M, Lindemann C, Rowstron A. P2P MANETs-New research issues[M]∥Perspectives Workshop:Peer-to-Peer Mobile Ad Hoc Networks, TX:IBFI Press, 2005.

[9] Caesar M, Castro M, Nightingale E B, et al. Virtual ring routing:network routing inspired by DHTs[C]∥Proc of SIGCOMM’11, 2011:351-362.

[10] Miller M, Siran J. Moore graphs and beyond:A survey of the degree/diameter problem[J]. Electronic Journal of Combinatorics, 2005,61:1-63.

[11] Zhang Yi-ming. Distributed line graphs:A universal technique for designing DHTs based on arbitrary regular graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,24(9):1556-1569.

[12] Feng Huang. Fast data dissemination in Kautz-based modular datacenter network[C]∥Proc of 2012 International Conference on Systems and Informatics (ICSAI), 2012:1606-1610.

[13] Banerjee S, Khuller S. A clustering scheme for hierarchical control in multi-hop wireless networks[C]∥Proc of INFOCOM’01, 2001:1028-1037.

[14] Baker D J, Ephremides A. The architectural organization of a mobile radio network via a distributed algorithm[J]. IEEE Transactions on Communications, 1981,29(1):1694-1701.

[15] Baker D J, Wieselthier J, Ephremides A. A distributed algorithm for scheduling the activation of links in a self-organizing, mobile, radio network[C]∥Proc of IEEE ICC’82, 1982:1.

[16] Gerla M, Tsai J T-C. Multicluster, mobile, multimedia radio network[J]. Journal of Wireless Networks, 1995,1(3):255-265.

[17] Ns-2 network simulator[EB/OL].[2013-05-16].http://www.isi.edu/nsnam/ns/.

[18] The VRR Windows XP implementation[EB/OL].[2013-05-16].http://research.microsoft.com/vrr/.

[19] Yu C, Shin K G, Lee B, et al. Node clustering in mobile peer-to-peer multihop networks[C]∥Proc of IEEE Interna-

tional Conference on Pervasive Computing and Communications, 2006:130-134.

[20] Zahn T, Schiller J. MADPastry:A DHT substrate for practicably sized MANETs[C]∥Proc of the 5th Workshop on Applications and Services in Wireless Networks, 2009:1.

[21] Yoneki E, Bacon J. Dynamic group communication in mobile peer-to-peer environments[C]∥Proc of the 20th Annual ACM Symposium on Applied Computing,2005:986-992.

[22] Eriksson J,Faloutsos M,Krishnamurthy S.PeerNet:Pushing peer-to-peer down the stack[C]∥Proc of IPTPS’03, 2003:268-277.

[23] Pucha H, Das S M, Hu Y C. Imposed route reuse in ad hoc network routing protocols using structured peer-to-peer overlay routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2006,17(12):1452-1467.

附中文參考文獻(xiàn)：

[1] 張世樂 魏芳費(fèi) 仲超. 移動(dòng)互聯(lián)網(wǎng)視頻傳輸優(yōu)化的架構(gòu)研究[J]. 計(jì)算機(jī)應(yīng)用與研究，2012,29(4):106-108.

[2] 倪萍 魏芳.一種提高無線傳感網(wǎng)絡(luò)數(shù)據(jù)模式可讀性的方法[J]. 計(jì)算機(jī)應(yīng)用與研究，2012,29(10):148-151.

[3] 陳貴海,李宏興,韓松,等.多跳無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多路徑路由[J]. 軟件學(xué)報(bào)，2010,21(8):1908-1919.