兼容弱連通簇的Ad Hoc網絡分簇算法

肖 磊，符云清，鐘明洋，王興芹

(重慶大學 a.計算機學院；b.軟件學院，重慶 400044)

1 概述

Ad Hoc網絡(MANET)是由一組可同時充當普通終端和路由器的無線節點構成的多跳、自組織的移動網絡。Ad Hoc網絡具有部署簡單、成本低、自愈能力強等特點，在軍事、搶險救災和民用等領域都有廣泛的應用[1]。由于網絡中節點可任意移動，沒有固定拓撲和主干，路由策略設計便成為MANET的核心問題。目前，研究者提出了很多適合MANET的路由協議，如目的節點序列距離矢量(Destinationsequenced Distance-vector Routing,DSDV)協議、動態源路由(Dynamic Source Routing,DSR)協議、按需距離矢量(Ad Hoc On-demand Distance Vector Routing,AODV)協議等。但這類算法開銷不容忽視，尤其不適應節點規模大、拓撲結構變化快的Ad Hoc網絡。

Ad Hoc網絡分簇是一種降低路由開銷的有效方法。分簇將集中控制的思想運用于分布式管理中，把網絡的重構限制在局部范圍內[2]，能有效減少局部拓撲變化引起全局變化現象的發生，從而降低網絡的整體路由開銷。在分簇的MANET中，每個簇由一個簇首和多個簇成員組成。簇首負責維護簇內拓撲結構，并為簇間通信提供支持。

根據簇結構的大小，分簇算法可分為單跳簇結構分簇算法和多跳簇結構分簇算法。其中，國內外比較受認可的單跳分簇算法主要有以下3類，即基于最小ID的分簇算法(Minimum ID Clustering Algorithm,MIDCA)、基于最大節點度的分簇算法(Highest Degree Clustering Algorithm,HDCA)、多因素加權的分簇算法(Weighted Clustering Algorithm,WCA)。

基于最小ID的分簇算法MIDCA根據節點的ID來生成簇[3]。節點與鄰居的ID進行比較(已是簇成員的鄰居節點不參與比較)。若自己 ID最小，則成為簇首并廣播消息；若其ID不是最小，則等待，直到收到簇首廣播消息，此時節點可加入該簇。該算法實現簡單、收斂快，但網絡中ID較小的節點傾向當選簇首，容易因能量消耗過快而死亡，具有很大的不公平性。基于最大節點度的分簇算法依據節點的度來成簇[4]。其算法過程與基于最小ID的分簇算法類似，不同的是節點在獲取鄰居矩陣后需計算自己的度，即鄰居的個數，并選擇度最大的節點作為簇首。該算法收斂較快，但該算法傾向于度較大的節點為簇頭，簇內節點過多將導致簇內節點吞吐量降低。多因素加權的分簇算法主要的思想是對節點的多種網絡參數(如帶寬、剩余能量、節點度、移動性等)進行加權求和，權值最大的節點為簇首[5-6]。該算法考慮因素全面、簇首選擇更優，但多種網絡參數的變化，造成其權值變化較快、收斂相對較慢，因此，網絡情況的變化對算法性能影響極大。

單跳簇結構覆蓋范圍小，簇內節點活動范圍相對較小、易脫離簇首，為優化整個網絡的簇劃分，提高簇結構穩定性，近年來多跳分簇算法也引起了廣泛研究。多跳分簇算法為單跳分簇算法的擴展，即簇首在節點多跳范圍內進行選擇。文獻[7]提出一種基于主宰樹的分簇算法(Dominating Tree Based Clustering Algorithm,DTCA)，利用節點在兩跳范圍的度(即兩跳范圍內的鄰居個數)選擇出主宰節點構成網絡虛擬骨干網，并根據平均鄰居(是關于節點兩跳鄰居個數的函數)將主宰節點進行劃分，得到簇的骨干樹結構，其余非主宰節點為骨干樹的葉子節點，即普通簇成員。樹根為簇首，其他主宰節點則為備選簇首節點。該算法分布式執行的，無法保證主宰節點構成的虛擬骨干網覆蓋整個網絡，即無法使所有非主宰節點到該虛擬骨干網的距離為一跳。文獻[8]根據節點的度和節點的剩余能量構成的綜合指標來構成主宰集，并最終生成多跳的簇結構，該算法能保證主宰集的連通性，但簇結構維護開銷較大。

目前，主流的多跳分簇算法是在單跳分簇算法的基礎上進行擴展，選擇主宰節點構成網絡的虛擬主干網[9]，并最終生成多跳簇。利用主宰集可保證簇結構的連通性，即形成強連通簇。由于算法分布式執行，這類旨在構造強連通簇的分簇算法不能保證選擇最優的節點作為簇首。為解決這一問題，并提高簇結構穩定性，本文提出一種兼容弱連通簇的分簇算法(Clustering Algorithm Compatible with Weak Connection Cluster,CACWC)。

2 兼容弱連通簇的分簇算法

單跳簇結構簇覆蓋范圍較小，簇成員更容易移動出簇，不利于將網絡的重構限制在局部，并且分簇數過多，簇間通信延遲較大，而多跳簇結構簇覆蓋多跳節點，雖能減少分簇數，但覆蓋的跳數越大，簇結構維護開銷就越大，簇首資源消耗也更快，因此，著重研究兩跳范圍的分簇算法。在不構建主宰集的前提下，生成兩跳簇結構，任一簇成員到達簇首的最大距離為兩跳，簇內節點間的最大距離為4跳。但是，CACWC并不是使得最終的簇結構均是弱連通簇，而是弱連通簇與強連通簇并存。

2.1 相關定義

定義 1(強連通簇) 在一個簇結構中，簇內節點集合為S，若任一節點v∈S可到達簇首節點，則該簇為強連通簇。

定義 2(弱連通簇) 在一個簇結構中，簇內節點集合為S，若存在一節點v∈S必須通過簇外節點才可到達簇首，則該簇為弱連通簇。

圖1為兩跳強連通簇，圖2為兩跳弱連通簇，其中，節點13需通過簇外節點8才能到達簇首節點7。對于兩跳弱連通簇而言，簇內成員節點至多通過一個簇外節點到達簇首。

圖1 兩跳強連通簇

圖2 兩跳弱連通簇

分簇算法弱連通簇存在的必要性分析如下：在多跳簇中，弱連通簇與強連通簇相比，簇成員可通過簇外節點到達本簇簇首，能夠選擇更優的節點作為簇首，如圖 2的兩跳簇中，節點兩跳范圍內有2個簇首節點2、節點7，由于分簇算法分布式執行的原因，現除節點13外，其他節點都已加入簇。設對于節點13來說，節點7比節點2更適合作其簇首(根據剩余能量、帶寬等因素判斷)，此時，若必須滿足強連通條件而選擇節點2作為簇首，則將加重節點2的負擔，甚至導致節點 2的能量快速耗盡。若以弱連通的選擇標準，則可選擇節點7作為簇首，節點13通過另一簇的簇內成員節點8與簇首通信。這樣簇首節點2、節點7的負載相對更均衡，有利于簇結構的穩定。

定義3(最佳簇大小) 簇內成員的最佳個數。

當網絡規模一定時，簇成員最佳個數一般為常值，根據文獻[10]，其計算公式為：

其中，W1、W2表示簇內、簇間的通信帶寬；N為網絡節點個數。通過最佳簇大小可限制簇內成員個數，防止簇內節點過多而導致簇頭負載過大[11]。

定義 4(簇首候選標準) 自由狀態下節點本身的簇首衡量指標。計算公式如下：

本文自由狀態下的節點即是指未加入簇結構的節點。其中，Ev表示節點v的剩余能量；N1-hop表示距離節點v的一跳的節點個數；N2-hop表示距離節點v的兩跳節點個數。節點剩余的能量越高，一跳鄰居數占節點v兩跳范圍內鄰居總數的比例越大，其當選簇首的可能性越大。能量越高表明，其當選簇首的時間將更長，N1-hop/(N1-hop+N2-hop)越大，則當選簇首后，簇內節點到達簇首路徑將多樣化，簇結構將更健壯。

定義 5(簇頭潛力規則) 在簇首候選標準的基礎上，簇頭潛力規則考慮了節點簇狀態、簇結構制約因素，具體如下：

(1)簇成員節點簇首潛力為 0，即簇成員節點在未脫離簇之前不會成為簇首。

(2)對于已是簇首的節點而言，若簇內成員個數超出上限C△，則簇首潛力為0，即節點不會加入滿員的簇。

(3)Pv越大節點簇頭潛力越大。

(4)未加入簇的節點其簇內成員節點默認為0。

(5)若 Pv相等，且簇內成員個數未超出上限 C△，簇內節點個數越小的節點簇頭潛力越大。

2.2 鄰居表的設計

本文的鄰居表為十字鏈表結構的兩跳鄰居表，其邏輯結構如圖 3所示，縱向為雙向鏈表，表示節點兩跳內的鄰居；橫向為節點到達相應的鄰居節點的中間節點。一跳鄰居的橫向鏈表為空。鄰居表的結構如圖4所示。

圖3 兩跳內的鄰居表邏輯結構

圖4 鄰居表節點結構

鄰居表節點各個字段意義如下：

(1)節點標識符(NID)：節點的唯一標識符。

(2)簇狀態(CS)：節點當前的簇狀態，若為簇首則為1，若為簇成員則為0，若未加入簇則為?1，剛加入網絡的節點其初始狀態為?1。

(3)所屬簇標識符(CID)：節點所屬的簇ID，簇標識符由簇首節點的NID決定，若節點未加入簇，則該字段置空。

(4)所屬簇簇成員數(N)：簇內成員個數，CS為?1的節點簇成員個數默認為0。

(5)簇首候選標準：標識節點本身可當選簇首的衡量指標，由式(2)算出。

(6)中間節點集：到達該鄰居節點的所有中間節點，若該鄰居節點為一跳鄰居，則該字段為空；若為兩跳鄰居，則為到達該鄰居的所有中間節點的NID。

(7)中間節點：當前用于與該鄰居節點通信的中間節點，若該鄰居節點為一跳鄰居，則該字段為空；若為兩跳鄰居，則為到達該鄰居的中間節點的NID，來源于中間節點集。

鄰居表的構造規則如下：節點鄰居表結構由Hello機制更新，Hello響應消息包括節點自身信息及其一跳鄰居的信息。在構造鄰居表時，若是一跳鄰居則縱向鏈表頭部開始插入，具體插入位置以鄰居節點簇頭潛力排列，潛力越大的鄰居節點越靠近鏈表頭部；若是兩跳鄰居則從鏈表尾部開始插入，具體插入順序以鄰居節點簇頭潛力排列，潛力越大的鄰居節點越靠近鏈表尾部。

上述的鄰居節點插入規則有如下優點：節點兩跳范圍的最佳簇頭節點在鄰居表第一個元素、鄰居表的最后一個元素及節點本身這 3個節點中誕生，而不必遍歷整個鄰居表，效率更高。

2.3 分簇算法描述

CACWC以節點能量及節點兩跳內鄰居的布局作為選擇簇頭的量化指標，該算法在各節點分布式地執行。各節點根據本地信息按需執行分簇算法，具有較強適應性。

分簇算法步驟的描述如下：

(1)若節點簇狀態CS為?1，則分簇算法開始。

(2)廣播Hello消息，根據收到的Hello消息響應更新本地鄰居表。

(3)比較鄰居表的第一個節點S1、最后一個節點Sn及節點本身S，選擇最適合的節點為簇首。如果該簇首與S的距離為兩跳，則只要 S存在某一條鄰居作為中間節點到達該簇首(該中間節點可為其他簇的簇內節點)，該簇首就合法。三者按簇頭潛力規則進行比較排列：

1)若節點S本身當選簇首，則更新本地節點信息，并廣播更新報文。

2)若節點選擇加入現有簇，則發送請求報文至簇首C，如果收到節點C的確認報文，則更新本地節點信息，并廣播更新報文。

3)若節點選擇未加入簇的節點 N為簇首，則發送請求報文至節點N，若收到節點N的確認報文，則節點更新本地節點消息，并廣播更新報文

若節點發出請求報文，最終未收到確認報文，則執行步驟(4)。

(4)選擇次優的節點作為簇首，并執行步驟(3)。

(5)節點收到請求報文，若節點當前處于未加入簇狀態，則更新節點本地信息，將自己置為簇首，并發送確認消息至源節點；若節點當前為簇首，則判斷自己能否納入新成員，若能則更新本地鄰居表，并發送確認消息至源節點。

2.4 簇的維護

簇的維護內容如下：

(1)簇首丟失

若簇成員發現簇頭在兩跳范圍內不可達，則將自己的簇狀態(CS)置為?1，自發執行分簇算法。

(2)中間節點連接丟失

若距離簇首兩跳距離的節點發現當前到達簇首的中間節點不可達，則將搜索鄰居表中到達簇首的中間節點鏈表，并選擇其中一個節點作為到達簇首的中間節點(中間節點可以屬于其他簇)，更新節點本地信息，若不存在到達簇首的中間節點則按簇首丟失處理。

(3)孤立簇首節點的處理

孤立簇首節點是指無簇成員的簇首[12]。孤立簇首每隔一段時間將自己的簇狀態置為?1，并進行分簇算法，若選自己為簇首，則進行二進制指數退避算法延遲一段時間再次將自己的簇狀態置為?1，直至有其他節點加入本簇或經過分簇算法選擇其他節點作為簇首。

3 分析與證明

下面采用非形式化的證明方法，證明CACWC的正確性和優越性：

(1)CACWC中節點查找候選簇頭的時間復雜度為常數。證明：CACWC中構造了如圖 3所示的十字鏈表結構的兩跳鄰居表，按照提出的鄰居表的構造規則，簇頭潛力最大的一跳鄰居位于縱向鏈表頭部，簇頭潛力最大的兩跳鄰居位于縱向鏈表的尾部。而縱向鏈表為雙向鏈表結構，故獲取最佳候選簇首(最佳候選包含節點本身)的時間復雜度為O(1)。證畢。

(2)算法最壞情況下時間復雜度是O(n2)，n為節點規模。證明：假設網絡規模為n，第i個節點的兩跳范圍內鄰節點數為Ni，且由算法保證每個節點至多發送2條消息就可完成分簇過程，因此，第i個節點至多發送的消息條數為2×Di，則全網完成分簇至多發送的消息條數為所以，算法最壞情況下時間復雜度為證畢。

(3)兼容弱連通簇的 Ad Hoc網絡中的孤立簇首數不大于強連通簇結構的Ad Hoc網絡。證明：先由節點選擇簇首的角度分析。在兼容弱連通簇的網絡中，簇首選自鄰接表縱向鏈表的首部、尾部以及節點本身。先假設三者當選簇首的概率分別為 Phead、Ptail、Pself，且滿足 Phead+Ptail+Pself=1。設強連通簇結構的網絡中對應的概率分別為 Phead’、Ptail’、Pself’，且滿足 Phead’+Ptail’+Pself’=1。由于強連通簇要求簇內成員到簇首的中間節點也屬于該簇，而兼容弱連通簇的網絡則無該強制條件，因此有 Ptail≥Ptail’，則有 Phead+Pself≤Phead’+Pself’。在其他因素保持不變的情況下，Pself≤Pself’，即在兼容弱連通簇的條件下，節點自身當選簇首的概率更小，即最多相等(結論1)。

現由節點已成為簇首的角度分析。假設節點N兩跳鄰居內包含簇首節點H，且兩者距離為Distance(N,H)=2。在強連通簇結構中，若節點 N、H之間無節點 V滿足Distance(N,V)=1且 Distance(V,H)=1(節點V∈CH)，則 N 將不會選擇節點H作為簇首。相反在弱連通簇結構下，只要存在任一節點U滿足Distance(N,U)=1，且Distance(U,H)=1，節點N即可能選擇H作為簇首。因此，兼容弱連通簇的網絡中簇首節點獲得簇成員的概率更小，即最多相等(結論2)。

綜合結論1、結論2可知，在其他因素不變的情況下，兼容弱連通簇的 Ad Hoc網絡選擇自己單選簇頭的概率相對更小，且更容易吸收簇成員，故孤立簇首數不大于強連通簇結構的Ad Hoc網絡。證畢。

(4)兼容弱連通簇的 Ad Hoc網絡比強連通的網絡具有更優的穩定性。證明：由證明(3)可知，兼容弱連通簇的Ad Hoc網絡孤立簇首數不大于強連通簇結構的Ad Hoc網絡，因此，在其他條件不變的情況下，兼容弱連通的網絡中簇結構分布更加均衡。此外，在兼容弱連通簇的條件下，節點無強連通的限制，節點在兩跳范圍內簇首的候選更多，且根據簇頭潛力規則選擇最優節點作為簇首。最優節點具有能量、拓撲等方面的優勢，有效存活時間更長。因此，兼容弱連通的Ad Hoc網絡負載更加均衡，并具有較好的持續性和穩定性。證畢。

4 結束語

本文提出一種兼容弱連通簇的Ad Hoc網絡分簇算法。在兩跳范圍內允許弱連通簇存在，簇結構不以主宰域為基礎，因此，節點能夠選擇更適合的節點作為簇首，并降低節點改變簇首的次數，使簇結構更加穩定。分析結果表明，該算法限制了簇成員個數，防止生成過大的簇，避免了簇首資源過快消耗，使得簇的有效存活時間更長。對整體網絡而言，盡可能地減少了孤立簇首節點的出現，優化了網絡的簇劃分。然而，在CACWC算法的實現中，分簇算法僅考慮了兩跳范圍的簇，鄰居表的設計擴展性較差，在面臨諸如三跳及以上的簇結構時，鄰居表的維護開銷過大，明顯影響算法的效果。因此，如何設計一個合理的可擴展鄰居表結構是今后的研究方向。

[1]王海濤.移動Ad Hoc網絡的分簇算法及性能比較[J].北京郵電大學學報,2004,27(1): 93-97.

[2]Richard C L,Mario G.Adaptive Clustering for Mobile Wireless Networks[J].IEEE Journal on Selected Areas in Communications,1997,15(7): 1265-1275.

[3]Jane Y Y,Petr H J.A Survey of Clustering Schemes for Mobile Ad Hoc Networks[J].IEEE Communications Survey and Tutorials,2005,7(1): 32-48.

[4]Dai Fei,Wu Jie.On Constucting K-connected K-dominating Set in Wireless Network[C]//Proc.of the 19th IEEE International Parallel and Distributed Processing Symposium.[S.l.]: IEEE Press,2005.

[5]楊衛東.考慮節點能量狀態的 Ad Hoc網絡分簇算法[J].計算機工程,2010,36(12): 119-122.

[6]張 麗,余鎮危,張 揚.移動Ad Hoc網絡的一種自適應權值分簇算法[J].西安電子科技大學學報: 自然科學版,2008,35(3): 572-576.

[7]Drira K,Lyon D,Kheddouci H.A New Clustering Algorithm for MANETs[C]//Proc.of the 14th International Telecommunications Network Strategy and Planning Symposium.[S.l.]: IEEE Press,2010.

[8]Zheng Chan,Yin Ling,Sun Shixin.Construction of D-hop Connected Dominating Sets in Wireless Sensor Networks Procedia Engineering,2011,15: 3416-3420.

[9]Cokuslu D,Erciyes K.A Hierarchical Connected Dominating Set Based Clustering Algorithm for Mobile Ad Hoc Networks[C]//Proc.of IEEE International Symposium on Modeling Analysis and Simulation of Computer and Telecommunication Systems.Istanbul,Turkey: [s.n.],2007.

[10]Xu Kaixin,Hong Xiaoyan,Gerla M.An Ad Hoc Network with Mobile Backbones[J].IEEE International Conference on Communications,2002,5: 3138-3143.

[11]Chatterjee M,Das S K,Turgut D.WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks[J].Cluster Computing,2009,5(2): 193-204.

[12]Srivastava S,Gohsh R K.Distributed Algorithms for Finding and Maintaining a K-tree Core in a Dynamic Network[J].Information Processing Letters,2003,88(4): 187-194.