一種適用于移動對等網絡的分簇算法

楊忠儀，左 克

(1.國防科學技術大學計算機學院,湖南 長沙 410073;2.湖南商務職業技術學院,湖南 長沙 410205)

1 引言

硬件技術的快速發展使得移動終端體積更小、更便攜、續航能力更強;同時,無線通信帶寬和范圍的增長，使得原本為有線網絡設計運行的應用能夠逐漸部署運行在無線網絡中。上述變革為移動對等網絡MP2P(Mobile Peer-to-Peer)的存在和發展提供了可能[1～7]。

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

Figure 1 Challenges of the MP2P network performance stability opposed by node mobility圖1 節點移動性給MP2P網絡性能穩定性帶來挑戰

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

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

2 定義與定理

2.1 Kautz圖和地址樹

首先，給出Kautz圖的定義。

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

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

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

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

2.2 分簇算法

我們的算法實現在VRR(Virtual Ring Routing)[9]路由協議之上。作為第一個采用DHT(Distributed Hash Table)特點設計的網絡層路由協議，VRR根據隨機產生的非負整數標志，將節點組織成一個虛擬環。而且，VRR中沒有設計網絡協議普遍采用的泛洪(Flooding)算法，因此VRR能夠獲得比其他路由協議更好的性能。

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

算法的執行過程就是尋找Kautz圖K(d,D)中擴展樹的過程。通過后根序和寬度優先算法遍歷地址樹T(d,D)的方式，我們將Kautz圖中的所有節點進行分簇。在算法的執行過程中，必須保證標識數值大小接近的節點被分在同一個簇內，以便于之后快速構造虛擬環。下面列出了算法中使用的簡寫以及含義：

(1)非負整數k：用來約束每個簇的大小。考慮到負載平衡和容錯，產生的所有簇的大小必須能夠產生有效的路由。因此，我們設計最小的簇的大小等于最大簇的大小的一半。

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

(3)T(x)：T的子樹，節點x作為子樹的根節點。

(4)Q：隊列類型的數據結構，用于存儲簇中的節點。采用隊列類型數據結構而非其他數據結構，因為我們不但需要使用隊列的FIFO方式保存節點信息，而且還可以為之后構造虛擬環帶來便利。

(5)C：隊列型數據結構，用于合并分簇。

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

(7)UnpChildren：存儲某個節點尚未被分到某個簇中的所有子節點。

(8)PartialClusterSet：存儲當前大小小于k的分簇集合。

(9)?：表示空集合。

下面的偽代碼對算法進行了詳細的描述:

算法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 算法屬性證明

本節我們形式化證明算法的特性，這些特性為之后在實驗評估中取得較好的測試結果提供了理論證明。

定理1算法保證所有節點都會被分配到某個簇中。

證明對任意節點u，如果u屬于某個子樹，則算法1的第4行保證他的所有子節點都已經被分配到UnpChildren。UnpChildren中所有子樹的節點會被保存在隊列Q中，算法1的第11行保證Q中的每個節點最終被分配到某個簇中。證畢。

□

定理2算法保證每個簇中節點會被組織成一個邏輯環。

證明根據算法1的第6、第10行，可以得到該屬性。數據結構隊列Q保證了該屬性的實現。證畢。

□

定理3算法保證任意兩個分簇之間只有一個公共節點。

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

□

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

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

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

□

2.4 算法收斂性分析

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

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

3 算法的實現

3.1 簇的產生

簇由上一節算法的分布式版本產生，當出現虛擬環段時觸發算法執行。算法執行完畢時，會根據之前的約束從每個環段的節點中挑選出簇首，接著在簇中每個節點的路由表中用ch_flag進行標注。如果多個簇首同時觸發簇的產生過程，則每個簇首需要根據自己的標識去發現地址空間樹的信息。因此，必須在簇首之間傳遞地址空間樹的發現數據，以便快速找出到地址空間樹根節點的最短路徑。

3.2 節點的加入和退出

當將傳統的P2P協議思想應用到MANET(Mobile Ad Hoc Networks)中時，往往因為移動網絡節點的暫不可達性、受限的資源(例如電能)或是節點移動性產生的網絡振動和分割問題，實際使用時獲得的性能普遍不理想。VRR協議設計了簡單的雙向故障檢測機制，能夠有效地發現上述問題并且修復路由狀態，保證虛擬環始終保持一致。基于VRR，我們設計了一系列有效的機制以應對在維護簇結構時面臨的網絡問題。

3.2.1 節點加入

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

3.2.2 節點退出

當有節點u脫離網絡，可根據自身的標識采用兩種不同的機制完成。如果節點u是某個簇中的普通節點，他只需要簡單地脫離網絡，我們使用VRR中已有的故障檢測和修復機制來維護虛擬環的一致性。如果節點u是簇首節點，則需要計算簇的新簇首，不過這個計算過程需要保證是非中斷式的，因為新節點帶來的路由更新信息將在簇中傳播，而且所有被更新路由信息的節點地址不能被修改。

4 算法的實現

基于網絡模擬器NS-2.4[17]，我們評估了設計的分簇算法性能。實驗中模擬的節點規模為200，均勻分布在300×300的正方形區域上。每次模擬隨機選擇兩個節點進行路由，然后計算100次實驗數據的平均值。每次實驗運行1 000 s，采樣最后的500 s作為評估值，不采樣之前500 s的實驗數據是為了保證路由協議運行達到穩定狀態。同時，我們將路由協議VRR[18]和分簇路由協議的性能進行了對比。

實驗設計為：針對MP2P系統在校園網絡和車載網絡兩種典型環境中，研究手持移動設備在不同速度模式下協議的性能。我們設計了低移動(模擬在校園網絡中個人手持移動設備時的速度，比如慢跑)和高移動(車載網絡時的速度)兩種測試場景：低移動場景中節點的移動速度為5 m/s，高速移動場景中節點的移動速度為20 m/s。進一步，我們分別測試了在網絡規模增加和載荷增加情況下協議的性能。

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

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

在低速的情況下，一開始三種協議都能夠獲得較好的數據發送比率和低延遲，隨著載荷的增加，數據發送比率也隨之增加。圖3顯示，我們設計的分簇路由協議能夠獲得更低的延遲和更高的數據發送比率，這是因為Kautz圖的特點以及簇大小約束條件能保證更好的負載平衡。高速場景下的測試情況如圖4所示，從圖4中也能得到和圖3類似的結論。進一步比較我們設計的分簇路由協議能獲得優于VRR的性能，這是因為當網絡振動問題頻繁出現時，分簇算法能夠保證路由協議具有更好的可擴展性。

圖5和圖6顯示了當保持載荷不變，增加節點數目對路由協議性能的影響。圖5中，當節點數小于80時，我們設計的分簇路由協議能獲得較高的數據發送比率和較低的延遲。隨著節點數的增加，數據分發比率逐漸降低，延遲增加。相比其他兩個協議，我們設計的分簇路由協議能夠獲得更好的數據發送比率和延遲。高速場景下，圖6也顯示出和圖5相同的結論。

Figure 5 Performance with increasing size in low mobility圖5 低速情況下節點增加時性能

Figure 6 Performance with increasing size in high mobility圖6 高速情況下節點增加時性能

5 結束語

在本文中，我們根據Kautz圖設計了一個有效的分簇算法：首先定義了地址空間樹，接著使用Kautz結構定義節點標識，再使用后根序和寬度優先算法遍歷地址空間樹產生簇。實驗結果表明，與VRR和MADPastry相比我們的分簇算法能夠獲得更低的網絡延遲、更好的可擴展性和性能。當面對MP2P網絡的節點移動和網絡振動問題時，使用我們設計的分簇算法能夠表現出更好的總體性能。

[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.

附中文參考文獻：

[1] 張世樂 魏芳費 仲超. 移動互聯網視頻傳輸優化的架構研究[J]. 計算機應用與研究，2012,29(4):106-108.

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

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