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

(重慶大學(xué) a.計(jì)算機(jī)學(xué)院；b.軟件學(xué)院，重慶 400044)

1 概述

Ad Hoc網(wǎng)絡(luò)(MANET)是由一組可同時(shí)充當(dāng)普通終端和路由器的無線節(jié)點(diǎn)構(gòu)成的多跳、自組織的移動(dòng)網(wǎng)絡(luò)。Ad Hoc網(wǎng)絡(luò)具有部署簡單、成本低、自愈能力強(qiáng)等特點(diǎn)，在軍事、搶險(xiǎn)救災(zāi)和民用等領(lǐng)域都有廣泛的應(yīng)用[1]。由于網(wǎng)絡(luò)中節(jié)點(diǎn)可任意移動(dòng)，沒有固定拓?fù)浜椭鞲?，路由策略設(shè)計(jì)便成為MANET的核心問題。目前，研究者提出了很多適合MANET的路由協(xié)議，如目的節(jié)點(diǎn)序列距離矢量(Destinationsequenced Distance-vector Routing,DSDV)協(xié)議、動(dòng)態(tài)源路由(Dynamic Source Routing,DSR)協(xié)議、按需距離矢量(Ad Hoc On-demand Distance Vector Routing,AODV)協(xié)議等。但這類算法開銷不容忽視，尤其不適應(yīng)節(jié)點(diǎn)規(guī)模大、拓?fù)浣Y(jié)構(gòu)變化快的Ad Hoc網(wǎng)絡(luò)。

Ad Hoc網(wǎng)絡(luò)分簇是一種降低路由開銷的有效方法。分簇將集中控制的思想運(yùn)用于分布式管理中，把網(wǎng)絡(luò)的重構(gòu)限制在局部范圍內(nèi)[2]，能有效減少局部拓?fù)渥兓鹑肿兓F(xiàn)象的發(fā)生，從而降低網(wǎng)絡(luò)的整體路由開銷。在分簇的MANET中，每個(gè)簇由一個(gè)簇首和多個(gè)簇成員組成。簇首負(fù)責(zé)維護(hù)簇內(nèi)拓?fù)浣Y(jié)構(gòu)，并為簇間通信提供支持。

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

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

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

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

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

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

2.1 相關(guān)定義

定義 1(強(qiáng)連通簇) 在一個(gè)簇結(jié)構(gòu)中，簇內(nèi)節(jié)點(diǎn)集合為S，若任一節(jié)點(diǎn)v∈S可到達(dá)簇首節(jié)點(diǎn)，則該簇為強(qiáng)連通簇。

定義 2(弱連通簇) 在一個(gè)簇結(jié)構(gòu)中，簇內(nèi)節(jié)點(diǎn)集合為S，若存在一節(jié)點(diǎn)v∈S必須通過簇外節(jié)點(diǎn)才可到達(dá)簇首，則該簇為弱連通簇。

圖1為兩跳強(qiáng)連通簇，圖2為兩跳弱連通簇，其中，節(jié)點(diǎn)13需通過簇外節(jié)點(diǎn)8才能到達(dá)簇首節(jié)點(diǎn)7。對于兩跳弱連通簇而言，簇內(nèi)成員節(jié)點(diǎn)至多通過一個(gè)簇外節(jié)點(diǎn)到達(dá)簇首。

圖1 兩跳強(qiáng)連通簇

圖2 兩跳弱連通簇

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

定義3(最佳簇大小) 簇內(nèi)成員的最佳個(gè)數(shù)。

當(dāng)網(wǎng)絡(luò)規(guī)模一定時(shí)，簇成員最佳個(gè)數(shù)一般為常值，根據(jù)文獻(xiàn)[10]，其計(jì)算公式為：

其中，W1、W2表示簇內(nèi)、簇間的通信帶寬；N為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。通過最佳簇大小可限制簇內(nèi)成員個(gè)數(shù)，防止簇內(nèi)節(jié)點(diǎn)過多而導(dǎo)致簇頭負(fù)載過大[11]。

定義 4(簇首候選標(biāo)準(zhǔn)) 自由狀態(tài)下節(jié)點(diǎn)本身的簇首衡量指標(biāo)。計(jì)算公式如下：

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

定義 5(簇頭潛力規(guī)則) 在簇首候選標(biāo)準(zhǔn)的基礎(chǔ)上，簇頭潛力規(guī)則考慮了節(jié)點(diǎn)簇狀態(tài)、簇結(jié)構(gòu)制約因素，具體如下：

(1)簇成員節(jié)點(diǎn)簇首潛力為 0，即簇成員節(jié)點(diǎn)在未脫離簇之前不會(huì)成為簇首。

(2)對于已是簇首的節(jié)點(diǎn)而言，若簇內(nèi)成員個(gè)數(shù)超出上限C△，則簇首潛力為0，即節(jié)點(diǎn)不會(huì)加入滿員的簇。

(3)Pv越大節(jié)點(diǎn)簇頭潛力越大。

(4)未加入簇的節(jié)點(diǎn)其簇內(nèi)成員節(jié)點(diǎn)默認(rèn)為0。

(5)若 Pv相等，且簇內(nèi)成員個(gè)數(shù)未超出上限 C△，簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)越小的節(jié)點(diǎn)簇頭潛力越大。

2.2 鄰居表的設(shè)計(jì)

本文的鄰居表為十字鏈表結(jié)構(gòu)的兩跳鄰居表，其邏輯結(jié)構(gòu)如圖 3所示，縱向?yàn)殡p向鏈表，表示節(jié)點(diǎn)兩跳內(nèi)的鄰居；橫向?yàn)楣?jié)點(diǎn)到達(dá)相應(yīng)的鄰居節(jié)點(diǎn)的中間節(jié)點(diǎn)。一跳鄰居的橫向鏈表為空。鄰居表的結(jié)構(gòu)如圖4所示。

圖3 兩跳內(nèi)的鄰居表邏輯結(jié)構(gòu)

圖4 鄰居表節(jié)點(diǎn)結(jié)構(gòu)

鄰居表節(jié)點(diǎn)各個(gè)字段意義如下：

(1)節(jié)點(diǎn)標(biāo)識(shí)符(NID)：節(jié)點(diǎn)的唯一標(biāo)識(shí)符。

(2)簇狀態(tài)(CS)：節(jié)點(diǎn)當(dāng)前的簇狀態(tài)，若為簇首則為1，若為簇成員則為0，若未加入簇則為?1，剛加入網(wǎng)絡(luò)的節(jié)點(diǎn)其初始狀態(tài)為?1。

(3)所屬簇標(biāo)識(shí)符(CID)：節(jié)點(diǎn)所屬的簇ID，簇標(biāo)識(shí)符由簇首節(jié)點(diǎn)的NID決定，若節(jié)點(diǎn)未加入簇，則該字段置空。

(4)所屬簇簇成員數(shù)(N)：簇內(nèi)成員個(gè)數(shù)，CS為?1的節(jié)點(diǎn)簇成員個(gè)數(shù)默認(rèn)為0。

(5)簇首候選標(biāo)準(zhǔn)：標(biāo)識(shí)節(jié)點(diǎn)本身可當(dāng)選簇首的衡量指標(biāo)，由式(2)算出。

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

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

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

上述的鄰居節(jié)點(diǎn)插入規(guī)則有如下優(yōu)點(diǎn)：節(jié)點(diǎn)兩跳范圍的最佳簇頭節(jié)點(diǎn)在鄰居表第一個(gè)元素、鄰居表的最后一個(gè)元素及節(jié)點(diǎn)本身這 3個(gè)節(jié)點(diǎn)中誕生，而不必遍歷整個(gè)鄰居表，效率更高。

2.3 分簇算法描述

CACWC以節(jié)點(diǎn)能量及節(jié)點(diǎn)兩跳內(nèi)鄰居的布局作為選擇簇頭的量化指標(biāo)，該算法在各節(jié)點(diǎn)分布式地執(zhí)行。各節(jié)點(diǎn)根據(jù)本地信息按需執(zhí)行分簇算法，具有較強(qiáng)適應(yīng)性。

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

(1)若節(jié)點(diǎn)簇狀態(tài)CS為?1，則分簇算法開始。

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

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

1)若節(jié)點(diǎn)S本身當(dāng)選簇首，則更新本地節(jié)點(diǎn)信息，并廣播更新報(bào)文。

2)若節(jié)點(diǎn)選擇加入現(xiàn)有簇，則發(fā)送請求報(bào)文至簇首C，如果收到節(jié)點(diǎn)C的確認(rèn)報(bào)文，則更新本地節(jié)點(diǎn)信息，并廣播更新報(bào)文。

3)若節(jié)點(diǎn)選擇未加入簇的節(jié)點(diǎn) N為簇首，則發(fā)送請求報(bào)文至節(jié)點(diǎn)N，若收到節(jié)點(diǎn)N的確認(rèn)報(bào)文，則節(jié)點(diǎn)更新本地節(jié)點(diǎn)消息，并廣播更新報(bào)文

若節(jié)點(diǎn)發(fā)出請求報(bào)文，最終未收到確認(rèn)報(bào)文，則執(zhí)行步驟(4)。

(4)選擇次優(yōu)的節(jié)點(diǎn)作為簇首，并執(zhí)行步驟(3)。

(5)節(jié)點(diǎn)收到請求報(bào)文，若節(jié)點(diǎn)當(dāng)前處于未加入簇狀態(tài)，則更新節(jié)點(diǎn)本地信息，將自己置為簇首，并發(fā)送確認(rèn)消息至源節(jié)點(diǎn)；若節(jié)點(diǎn)當(dāng)前為簇首，則判斷自己能否納入新成員，若能則更新本地鄰居表，并發(fā)送確認(rèn)消息至源節(jié)點(diǎn)。

2.4 簇的維護(hù)

簇的維護(hù)內(nèi)容如下：

(1)簇首丟失

若簇成員發(fā)現(xiàn)簇頭在兩跳范圍內(nèi)不可達(dá)，則將自己的簇狀態(tài)(CS)置為?1，自發(fā)執(zhí)行分簇算法。

(2)中間節(jié)點(diǎn)連接丟失

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

(3)孤立簇首節(jié)點(diǎn)的處理

孤立簇首節(jié)點(diǎn)是指無簇成員的簇首[12]。孤立簇首每隔一段時(shí)間將自己的簇狀態(tài)置為?1，并進(jìn)行分簇算法，若選自己為簇首，則進(jìn)行二進(jìn)制指數(shù)退避算法延遲一段時(shí)間再次將自己的簇狀態(tài)置為?1，直至有其他節(jié)點(diǎn)加入本簇或經(jīng)過分簇算法選擇其他節(jié)點(diǎn)作為簇首。

3 分析與證明

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

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

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

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

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

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

(4)兼容弱連通簇的 Ad Hoc網(wǎng)絡(luò)比強(qiáng)連通的網(wǎng)絡(luò)具有更優(yōu)的穩(wěn)定性。證明：由證明(3)可知，兼容弱連通簇的Ad Hoc網(wǎng)絡(luò)孤立簇首數(shù)不大于強(qiáng)連通簇結(jié)構(gòu)的Ad Hoc網(wǎng)絡(luò)，因此，在其他條件不變的情況下，兼容弱連通的網(wǎng)絡(luò)中簇結(jié)構(gòu)分布更加均衡。此外，在兼容弱連通簇的條件下，節(jié)點(diǎn)無強(qiáng)連通的限制，節(jié)點(diǎn)在兩跳范圍內(nèi)簇首的候選更多，且根據(jù)簇頭潛力規(guī)則選擇最優(yōu)節(jié)點(diǎn)作為簇首。最優(yōu)節(jié)點(diǎn)具有能量、拓?fù)涞确矫娴膬?yōu)勢，有效存活時(shí)間更長。因此，兼容弱連通的Ad Hoc網(wǎng)絡(luò)負(fù)載更加均衡，并具有較好的持續(xù)性和穩(wěn)定性。證畢。

4 結(jié)束語

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

[1]王海濤.移動(dòng)Ad Hoc網(wǎng)絡(luò)的分簇算法及性能比較[J].北京郵電大學(xué)學(xué)報(bào),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]楊衛(wèi)東.考慮節(jié)點(diǎn)能量狀態(tài)的 Ad Hoc網(wǎng)絡(luò)分簇算法[J].計(jì)算機(jī)工程,2010,36(12): 119-122.

[6]張 麗,余鎮(zhèn)危,張 揚(yáng).移動(dòng)Ad Hoc網(wǎng)絡(luò)的一種自適應(yīng)權(quán)值分簇算法[J].西安電子科技大學(xué)學(xué)報(bào): 自然科學(xué)版,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.