無(wú)線自組網(wǎng)的分簇算法研究

解放軍理工大學(xué)通信工程學(xué)院 王海濤

一、引言

無(wú)線自組網(wǎng)（Wireless Self-organizing Network）是計(jì)算機(jī)網(wǎng)絡(luò)和移動(dòng)無(wú)線通信網(wǎng)絡(luò)相互融合發(fā)展的產(chǎn)物，其顯著特點(diǎn)是節(jié)點(diǎn)采用無(wú)線通信方式、網(wǎng)絡(luò)無(wú)中心、自組織和多跳中繼，無(wú)線自組網(wǎng)（MANET）、無(wú)線傳感網(wǎng)（WSN）和無(wú)線網(wǎng)狀網(wǎng)（WMN）都可歸屬于無(wú)線自組網(wǎng)這一范疇。為了提高無(wú)線自組網(wǎng)的可擴(kuò)展性和QoS保障能力，往往采用分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)。分簇算法按系統(tǒng)要求將眾多網(wǎng)絡(luò)節(jié)點(diǎn)組織成可管理的簇，是構(gòu)造分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)鍵技術(shù)，它的好壞直接影響著無(wú)線自組網(wǎng)的各種性能指標(biāo)。

基于簇的分級(jí)網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示，網(wǎng)絡(luò)劃分成若干個(gè)簇，每個(gè)簇由一個(gè)簇頭和多個(gè)普通節(jié)點(diǎn)組成，并且簇頭和網(wǎng)關(guān)/分布式網(wǎng)關(guān)形成高一級(jí)的虛擬骨干網(wǎng)（VBN）。在蜂窩網(wǎng)絡(luò)中，資源的分配比較容易實(shí)現(xiàn)，因?yàn)楦鱾€(gè)移動(dòng)終端可以直接或借助基站獲得對(duì)方的帶寬要求。通過(guò)把網(wǎng)絡(luò)劃分成簇可以將這種方法擴(kuò)展到無(wú)線自組網(wǎng)，在簇內(nèi)，簇頭可以控制節(jié)點(diǎn)的業(yè)務(wù)接入請(qǐng)求并合理地分配帶寬。基于分簇結(jié)構(gòu)，還可以采用混合式路由算法，簇內(nèi)采用先驗(yàn)式路由，而簇間使用反應(yīng)式路由來(lái)減少路由開(kāi)銷(xiāo)。此外，借助于虛擬骨干網(wǎng)可以提高業(yè)務(wù)的QoS保障。因此，通過(guò)分簇算法將網(wǎng)絡(luò)劃分成簇，可以在很大程度上提高無(wú)線自組網(wǎng)的性能和實(shí)用性，具有重要的意義。

圖1 無(wú)線自組網(wǎng)的分簇網(wǎng)絡(luò)結(jié)構(gòu)

二、分簇算法的原則和目標(biāo)

分簇算法根據(jù)系統(tǒng)要求按照某種規(guī)則將網(wǎng)絡(luò)劃分成可以相互連通并覆蓋所有節(jié)點(diǎn)的多個(gè)簇，并且在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時(shí)進(jìn)行簇結(jié)構(gòu)的更新以維護(hù)網(wǎng)絡(luò)的正常功能。簇的大小應(yīng)根據(jù)節(jié)點(diǎn)的傳輸功率和簇本身的特性來(lái)決定。如果簇過(guò)大，簇頭的負(fù)擔(dān)較重，并且普通節(jié)點(diǎn)到簇頭的距離過(guò)遠(yuǎn)而會(huì)消耗過(guò)多能量。如果簇較小，可以相應(yīng)增加信道的空間重用率，提高系統(tǒng)容量，并可以減少節(jié)點(diǎn)的傳輸功耗。但是簇的尺寸過(guò)小會(huì)導(dǎo)致網(wǎng)絡(luò)中簇的數(shù)目較多，源目的節(jié)點(diǎn)對(duì)之間的路由所經(jīng)過(guò)的跳數(shù)較多，從而會(huì)增加分組的投遞時(shí)延和中轉(zhuǎn)業(yè)務(wù)量。此外，在選擇簇的大小時(shí)還應(yīng)考慮簇頭的處理能力、功率損耗和地理環(huán)境等約束條件。

分簇算法要在拓?fù)涮綔y(cè)的同時(shí)完成分簇形成和分簇連接的工作。拓?fù)涮綔y(cè)指各節(jié)點(diǎn)通過(guò)收發(fā)探詢(xún)分組來(lái)獲得鄰節(jié)點(diǎn)以及整個(gè)網(wǎng)絡(luò)的拓?fù)溥B通情況。分簇形成是指按照某種規(guī)則選舉簇頭并劃分簇的過(guò)程，各種分簇算法的不同之處主要體現(xiàn)于此。分簇連接是指相鄰的簇選擇關(guān)聯(lián)節(jié)點(diǎn)的過(guò)程。為了減少關(guān)聯(lián)節(jié)點(diǎn)數(shù)過(guò)多引入的控制開(kāi)銷(xiāo)，網(wǎng)關(guān)節(jié)點(diǎn)和分布式網(wǎng)關(guān)節(jié)點(diǎn)的選取可以按照節(jié)點(diǎn)度最小的原則進(jìn)行。

分簇算法的目標(biāo)就是以較少的計(jì)算和通信開(kāi)銷(xiāo)來(lái)構(gòu)造和維護(hù)一個(gè)能夠覆蓋整個(gè)網(wǎng)絡(luò)的、可以較好支持資源管理和路由協(xié)議的相互連接的簇集合。為了減少分簇算法帶來(lái)的開(kāi)銷(xiāo)，分簇算法應(yīng)簡(jiǎn)單高效，并在只有很少的節(jié)點(diǎn)移動(dòng)和拓?fù)渥兓^慢時(shí)盡量維持原有結(jié)構(gòu)，從而減少重新生成簇引入的開(kāi)銷(xiāo)和提高網(wǎng)絡(luò)的總體效能。理想情況下，希望以最少的簇頭覆蓋整個(gè)網(wǎng)絡(luò)，即簇頭的集合為最小統(tǒng)治集（MDS）。滿(mǎn)足MDS的簇頭優(yōu)化選擇問(wèn)題是NP完全問(wèn)題，因此一般采用啟發(fā)式分簇算法。好的分簇機(jī)制應(yīng)盡量保持網(wǎng)絡(luò)拓?fù)浞€(wěn)定，減少重新分簇的次數(shù)，優(yōu)化簇內(nèi)和簇間連接，并且還應(yīng)考慮節(jié)點(diǎn)的能量級(jí)別、網(wǎng)絡(luò)的負(fù)載平衡以及對(duì)路由算法和信道接入?yún)f(xié)議的支持等方面。

三、無(wú)線自組網(wǎng)中分簇算法的分類(lèi)比較

迄今為止，針對(duì)無(wú)線自組網(wǎng)已經(jīng)提出了大量的分簇算法來(lái)構(gòu)建和維護(hù)分簇網(wǎng)絡(luò)結(jié)構(gòu)。分簇算法的選擇依賴(lài)于應(yīng)用的需求、網(wǎng)絡(luò)的環(huán)境和節(jié)點(diǎn)的特征。不同的分簇算法具有不同的優(yōu)化目標(biāo)，包括最小化簇計(jì)算和維護(hù)開(kāi)銷(xiāo)、最小化簇頭、最大化簇穩(wěn)定性和最大化節(jié)點(diǎn)生存時(shí)間等?？紤]到現(xiàn)存的分簇算法很多，下面按照簇頭選舉方式以及優(yōu)化目標(biāo)對(duì)它們進(jìn)行分類(lèi)和比較。

1. 基于節(jié)點(diǎn)ID的分簇算法

C.R. Lin提出的最小節(jié)點(diǎn)ID（LowID）分簇算法是基于ID的分簇算法的典型代表。LowID算法規(guī)定，相鄰節(jié)點(diǎn)中具有最小ID的節(jié)點(diǎn)作為簇頭，其一跳鄰居節(jié)點(diǎn)成為該簇頭所在簇的成員節(jié)點(diǎn)，并不再參與簇頭選舉過(guò)程，重復(fù)以上過(guò)程直到所有節(jié)點(diǎn)都加入某個(gè)簇。該分簇算法計(jì)算簡(jiǎn)單，實(shí)現(xiàn)方便。在移動(dòng)環(huán)境下，最小ID算法中簇頭更新的頻率較慢，維護(hù)簇所需花費(fèi)的開(kāi)銷(xiāo)較小。缺點(diǎn)在于這種算法傾向選擇ID較小的節(jié)點(diǎn)作為簇頭，使得這些節(jié)點(diǎn)消耗更多的能量，從而會(huì)減少整個(gè)網(wǎng)絡(luò)出現(xiàn)分區(qū)的時(shí)間，此外它沒(méi)有考慮網(wǎng)絡(luò)負(fù)載平衡等因素。

2. 最高節(jié)點(diǎn)度分簇算法

最高節(jié)點(diǎn)度分簇算法也稱(chēng)作最高連接度算法，目標(biāo)是提高網(wǎng)絡(luò)的控制能力和減少簇的數(shù)目。該算法規(guī)定：相鄰節(jié)點(diǎn)中具有最大節(jié)點(diǎn)度的節(jié)點(diǎn)被選為簇頭，節(jié)點(diǎn)度是指該節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)的數(shù)目，當(dāng)節(jié)點(diǎn)度相同時(shí)，則選擇ID最小的節(jié)點(diǎn)作為簇頭。簇頭的一跳鄰居節(jié)點(diǎn)則成為該簇的成員節(jié)點(diǎn)，并不再參與簇生成過(guò)程。這種算法的優(yōu)點(diǎn)在于網(wǎng)絡(luò)中簇的數(shù)目較少，即源目的節(jié)點(diǎn)對(duì)之間的平均跳數(shù)較少，從而減少了分組投遞時(shí)延。但是，較少的簇?cái)?shù)量也減少了信道的空間重用率。此外，當(dāng)節(jié)點(diǎn)移動(dòng)性較強(qiáng)時(shí)，簇頭更新頻率會(huì)急劇上升，簇結(jié)構(gòu)變化較快，引入了大量維護(hù)開(kāi)銷(xiāo)。最高節(jié)點(diǎn)度算法適用于移動(dòng)性較弱并且節(jié)點(diǎn)密度較低的場(chǎng)合。

3. 最低節(jié)點(diǎn)移動(dòng)性分簇算法

為適應(yīng)節(jié)點(diǎn)的移動(dòng)性，提高簇結(jié)構(gòu)的穩(wěn)定性，可以根據(jù)節(jié)點(diǎn)的移動(dòng)性為節(jié)點(diǎn)分配權(quán)重，并依據(jù)節(jié)點(diǎn)的權(quán)重來(lái)選舉簇頭。最低節(jié)點(diǎn)移動(dòng)性分簇算法規(guī)定：節(jié)點(diǎn)的移動(dòng)性越高，其分配的權(quán)重越低，選擇鄰居節(jié)點(diǎn)中具有最高權(quán)重的節(jié)點(diǎn)作為簇頭。在這種分簇算法中，需要一種機(jī)制來(lái)量化節(jié)點(diǎn)的移動(dòng)性。一種簡(jiǎn)單的方法規(guī)定任何節(jié)點(diǎn)對(duì)的移動(dòng)性為它們相對(duì)速度絕對(duì)值的時(shí)間平均，但是這種方法需要通過(guò)GPS來(lái)獲得節(jié)點(diǎn)的位置。為此，可以采用一種聚集本地移動(dòng)性指標(biāo)，節(jié)點(diǎn)通過(guò)比較收到的來(lái)自某一鄰居節(jié)點(diǎn)的連續(xù)兩次的信號(hào)的強(qiáng)度來(lái)估計(jì)它們之間的相對(duì)移動(dòng)性。在移動(dòng)性較強(qiáng)時(shí)，最低移動(dòng)性分簇算法可以明顯地減少簇頭更新頻率，它的缺點(diǎn)在于節(jié)點(diǎn)權(quán)重的更新較頻繁，簇頭的計(jì)算開(kāi)銷(xiāo)較大，并且沒(méi)有考慮系統(tǒng)的負(fù)載平衡和節(jié)點(diǎn)的能量損耗。

4. 組合加權(quán)分簇算法

簇頭的選舉對(duì)于網(wǎng)絡(luò)的性能至關(guān)重要，需要考慮多種因素，并基于網(wǎng)絡(luò)環(huán)境和業(yè)務(wù)需求進(jìn)行合理的折衷?；谝陨峡紤]，可以采用一種組合的加權(quán)分簇算法（WCA）。在WCA算法中，每個(gè)節(jié)點(diǎn)分配一個(gè)權(quán)值來(lái)指示該節(jié)點(diǎn)適合充當(dāng)簇頭的程度。每個(gè)節(jié)點(diǎn)的權(quán)值可以使用一個(gè)考慮多種因素的通用公式表示：Weight＝a×mobility+b×degree+c×power+d×e nergy-left，其中參數(shù)a，b，c，d由應(yīng)用和網(wǎng)絡(luò)環(huán)境決定；Mobility表示節(jié)點(diǎn)移動(dòng)的速度或相對(duì)鄰居節(jié)點(diǎn)的移動(dòng)性；degree表示節(jié)點(diǎn)度；power表示節(jié)點(diǎn)的傳輸功率；energyleft表示節(jié)點(diǎn)剩余的能量。此外，每個(gè)變量需要根據(jù)具體的應(yīng)用選用合適的單位，并且還可以根據(jù)需要增加更多的變量。

5. 無(wú)簇頭分簇算法

在實(shí)現(xiàn)分簇算法時(shí)，存在兩種觀點(diǎn)：不選舉簇頭或選舉簇頭。前者認(rèn)為簇頭承擔(dān)過(guò)重任務(wù)而可能成為網(wǎng)絡(luò)瓶頸，當(dāng)簇頭出現(xiàn)故障時(shí)，會(huì)嚴(yán)重影響網(wǎng)絡(luò)的性能。如果不選舉簇頭，簇內(nèi)每個(gè)節(jié)點(diǎn)需維護(hù)簇內(nèi)和簇間的路由信息，維護(hù)開(kāi)銷(xiāo)較大，并且不能充分利用分簇結(jié)構(gòu)帶來(lái)的好處，例如實(shí)施網(wǎng)絡(luò)管理和資源分配等。當(dāng)存在簇頭時(shí)，簇頭充當(dāng)簇內(nèi)的協(xié)調(diào)者和管理者，并可以和關(guān)聯(lián)節(jié)點(diǎn)構(gòu)成虛擬骨干網(wǎng)絡(luò)，從而方便地實(shí)現(xiàn)分級(jí)路由、移動(dòng)管理和資源分配，減少維護(hù)簇結(jié)構(gòu)所需的控制開(kāi)銷(xiāo)，特別是當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)。在網(wǎng)絡(luò)規(guī)模不大，節(jié)點(diǎn)密度較高并且節(jié)點(diǎn)的處理能力很低的情況下，為了防止簇頭成為瓶頸節(jié)點(diǎn)，可以考慮采用無(wú)簇頭分簇算法?；诜謪^(qū)的分級(jí)鏈路狀態(tài)路由協(xié)議（ZHLS）利用無(wú)簇頭分簇結(jié)構(gòu)來(lái)提高路由協(xié)議的性能，簇內(nèi)每個(gè)節(jié)點(diǎn)被同等對(duì)待，從而可以避免業(yè)務(wù)量瓶頸以增強(qiáng)系統(tǒng)的健壯性。

6. 考慮簇大小的分簇算法

大多數(shù)分簇算法產(chǎn)生的簇都是一跳有頭簇或兩跳無(wú)頭簇，這種分簇結(jié)構(gòu)實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，但是沒(méi)有考慮簇內(nèi)的節(jié)點(diǎn)數(shù)量，有時(shí)將會(huì)影響基于簇的網(wǎng)絡(luò)協(xié)議的性能。當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)過(guò)多時(shí)，將會(huì)導(dǎo)致簇頭負(fù)擔(dān)較重；簇內(nèi)節(jié)點(diǎn)數(shù)過(guò)少又使得簇的數(shù)量較多，簇的維護(hù)開(kāi)銷(xiāo)和分組投遞時(shí)延較大。因此，需要通過(guò)某種機(jī)制來(lái)控制簇的大小和簇的數(shù)量。一種解決方法是根據(jù)節(jié)點(diǎn)的密度和數(shù)量來(lái)確定簇內(nèi)節(jié)點(diǎn)與簇頭的最大距離d。Max-Min d跳分簇算法是一種基于節(jié)點(diǎn)ID來(lái)選擇簇頭的多跳簇分簇算法，該算法可以有效地減少簇頭數(shù)，算法的時(shí)間復(fù)雜性為O(d)。另外，還可以通過(guò)限制簇內(nèi)節(jié)點(diǎn)數(shù)來(lái)調(diào)節(jié)簇的尺寸，MMWN體系結(jié)構(gòu)通過(guò)簇的分離/合并來(lái)限制簇內(nèi)節(jié)點(diǎn)數(shù)。簇的分離和合并由三個(gè)參數(shù)控制：分離門(mén)限Nsplit，合并門(mén)限Nmerge和最佳尺寸Npref。如果一個(gè)簇的節(jié)點(diǎn)數(shù)超過(guò)Nsplit，那么將執(zhí)行簇分裂過(guò)程；當(dāng)簇內(nèi)節(jié)點(diǎn)的數(shù)小于Nmerge時(shí)，它可能與相鄰的簇合并，同時(shí)盡量使新簇的尺寸接近Npref。多跳簇可以減少簇的數(shù)量和分組的時(shí)延，但是會(huì)加重簇頭的負(fù)擔(dān)，并且簇結(jié)構(gòu)的產(chǎn)生和維護(hù)更加復(fù)雜，特別是當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)性較強(qiáng)時(shí)。因此，應(yīng)根據(jù)節(jié)點(diǎn)的密度、數(shù)量、運(yùn)動(dòng)模式和業(yè)務(wù)需求來(lái)確定簇的尺寸以?xún)?yōu)化網(wǎng)絡(luò)的性能。

7. 基于地理位置的分簇算法

上述的分簇算法沒(méi)有考慮節(jié)點(diǎn)的位置信息，如果可以借助GPS或者根據(jù)接收信號(hào)的強(qiáng)度來(lái)估算節(jié)點(diǎn)的位置坐標(biāo)，那么可以采用基于地理位置的分簇算法。郭虹等人描述了一種簡(jiǎn)單的基于節(jié)點(diǎn)位置坐標(biāo)進(jìn)行分簇的方法（參見(jiàn)圖2）：假定每個(gè)簇是正方形，互不交疊且大小相等，簇內(nèi)不存在簇頭，簇內(nèi)節(jié)點(diǎn)可以直接通信，即節(jié)點(diǎn)的通信范圍等于正方形簇的對(duì)角線長(zhǎng)度。那么節(jié)點(diǎn)可以按照下式來(lái)確定自己所在的簇：

式中，x和y為節(jié)點(diǎn)的物理坐標(biāo)；r為節(jié)點(diǎn)的通信范圍；floor表示下取整；(x'，y')表示節(jié)點(diǎn)所在的簇。

圖2 一種基于地理位置的分簇和信道分配

考慮到信道的空間重用，即相距兩跳以上的節(jié)點(diǎn)可以重用信道而不發(fā)生干擾。另外，在基于節(jié)點(diǎn)的位置信息劃分簇后，可以根據(jù)節(jié)點(diǎn)分布密度、移動(dòng)性和發(fā)送功率來(lái)動(dòng)態(tài)調(diào)整簇的大小以?xún)?yōu)化網(wǎng)絡(luò)性能。這種基于地理位置的動(dòng)態(tài)分簇算法能較好地對(duì)節(jié)點(diǎn)進(jìn)行管理，但是消息開(kāi)銷(xiāo)較大。當(dāng)節(jié)點(diǎn)的傳輸范圍動(dòng)態(tài)變化時(shí)，傾向于選擇基于圖的分簇算法，因?yàn)榛诘乩砦恢玫姆执厮惴ú荒芎芎玫剡m應(yīng)這種情況。

8. 被動(dòng)分簇算法

以上討論的分簇算法都可以看作主動(dòng)分簇算法，因?yàn)樗鼈兓蛘呒僭O(shè)知道鄰居節(jié)點(diǎn)信息，或者通過(guò)周期性交換控制分組來(lái)獲得鄰居節(jié)點(diǎn)信息。在這些分簇算法中，節(jié)點(diǎn)既使沒(méi)有發(fā)送數(shù)據(jù)，也會(huì)引入大量控制開(kāi)銷(xiāo)，特別是當(dāng)節(jié)點(diǎn)密度較高或移動(dòng)性較強(qiáng)時(shí)。對(duì)于一些特殊的應(yīng)用場(chǎng)合，如戰(zhàn)術(shù)通信網(wǎng)絡(luò)和傳感網(wǎng)絡(luò)，周期性的控制分組會(huì)暴露節(jié)點(diǎn)位置、造成信息泄密并會(huì)過(guò)多消耗傳感節(jié)點(diǎn)的能量。為此，可以采用被動(dòng)分簇算法，不使用專(zhuān)門(mén)的分簇控制消息，而是將數(shù)據(jù)的傳輸和分簇的形成緊密結(jié)合在一起。例如，基于信道接入的被動(dòng)分簇算法（ABCA）在簇形成過(guò)程中，每個(gè)節(jié)點(diǎn)都試圖接入控制信道來(lái)聲明自己是簇頭，一個(gè)節(jié)點(diǎn)如果在它的所有鄰居節(jié)點(diǎn)中最先成功地發(fā)送了簇頭聲明控制消息，那么它成為簇頭，即按照“最先聲明優(yōu)先”的規(guī)則來(lái)選舉簇頭。收到簇頭聲明消息的普通節(jié)點(diǎn)成為該簇頭的成員節(jié)點(diǎn)。一旦某個(gè)節(jié)點(diǎn)成為簇頭并且至少有一個(gè)成員節(jié)點(diǎn)，它將一直充當(dāng)簇頭直到它離開(kāi)網(wǎng)絡(luò)或者出現(xiàn)故障。當(dāng)一個(gè)節(jié)點(diǎn)剛加入網(wǎng)絡(luò)或想改變簇時(shí)，它可以根據(jù)接收到的簇頭聲明消息來(lái)選擇加入一個(gè)鄰居簇。被動(dòng)分簇的開(kāi)銷(xiāo)較小，但是被動(dòng)分簇算法得到的分簇結(jié)構(gòu)是用戶(hù)數(shù)據(jù)傳輸?shù)母碑a(chǎn)品，如果節(jié)點(diǎn)不發(fā)送數(shù)據(jù)則不能形成簇結(jié)構(gòu)。所以產(chǎn)生的簇的隨機(jī)性較大，簇結(jié)構(gòu)不夠優(yōu)化并不易控制，不能隨時(shí)利用分簇結(jié)構(gòu)帶來(lái)的好處。因此，這種被動(dòng)分簇通常用于提高廣播協(xié)議的效率和某些特殊的場(chǎng)合。

9. 比較分析

綜上所述，不同的分簇算法有不同的優(yōu)化目標(biāo)和使用場(chǎng)合，應(yīng)根據(jù)網(wǎng)絡(luò)環(huán)境和系統(tǒng)的要求進(jìn)行合理選擇。例如，最小ID分簇算法實(shí)現(xiàn)簡(jiǎn)單方便，但是沒(méi)有考慮節(jié)點(diǎn)的能量損耗和負(fù)載平衡。最高節(jié)點(diǎn)度分簇算法可以減少簇頭數(shù)，但是會(huì)進(jìn)一步加重簇頭的負(fù)擔(dān)。最小移動(dòng)性分簇算法能較好地適應(yīng)節(jié)點(diǎn)的移動(dòng)性，但是需要合理地估算節(jié)點(diǎn)的移動(dòng)性。組合加權(quán)分簇算法綜合考慮了影響分簇網(wǎng)絡(luò)結(jié)構(gòu)性能的多種因素，具有較高的靈活性和適應(yīng)性。調(diào)節(jié)簇尺寸的分簇算法可以用來(lái)優(yōu)化分簇結(jié)構(gòu)的性能，但是實(shí)現(xiàn)較復(fù)雜?；诘乩砦恢玫姆执厮惴ǜ訌?qiáng)調(diào)節(jié)點(diǎn)之間的地理分布，能更好地對(duì)節(jié)點(diǎn)進(jìn)行移動(dòng)管理，但是要求節(jié)點(diǎn)可以獲悉自己的位置坐標(biāo)，消息開(kāi)銷(xiāo)較大。無(wú)簇頭分簇算法和被動(dòng)分簇算法是兩類(lèi)比較特殊的分簇算法，前者的初衷是避免簇頭成為瓶頸節(jié)點(diǎn)，但是削弱了分簇結(jié)構(gòu)的效能；被動(dòng)分簇算法可以減少開(kāi)銷(xiāo)，但是簇結(jié)構(gòu)不夠優(yōu)化。

四、簇維護(hù)策略

在分簇網(wǎng)絡(luò)中，節(jié)點(diǎn)會(huì)經(jīng)常加入或離開(kāi)簇，更為嚴(yán)重的是，劇烈的節(jié)點(diǎn)移動(dòng)有時(shí)會(huì)導(dǎo)致簇頭的更新和網(wǎng)絡(luò)結(jié)構(gòu)的重新配置，從而引入較大的計(jì)算和通信開(kāi)銷(xiāo)，并且嚴(yán)重影響其他網(wǎng)絡(luò)協(xié)議的性能，如分組調(diào)度、路由和資源管理等。因此，需要合理的簇維護(hù)機(jī)制來(lái)盡量減量減少控制開(kāi)銷(xiāo)和維持簇結(jié)構(gòu)的穩(wěn)定?，F(xiàn)存的許多簇維護(hù)機(jī)制采用周期性重新分簇的方法，這種簇維護(hù)策略中，簇更新周期很難確定。如果更新頻率過(guò)低，簇結(jié)構(gòu)不夠優(yōu)化；否則，控制開(kāi)銷(xiāo)過(guò)大，并且在重新分簇的時(shí)候網(wǎng)絡(luò)無(wú)法獲得簇結(jié)構(gòu)帶來(lái)的好處。這種簇維護(hù)策略通常適用于節(jié)點(diǎn)數(shù)較少并且移動(dòng)性較低的場(chǎng)合。另一些機(jī)制需要每個(gè)節(jié)點(diǎn)了解其兩跳范圍內(nèi)鄰居節(jié)點(diǎn)的狀況，簇維護(hù)的原則是盡量使節(jié)點(diǎn)度最高的節(jié)點(diǎn)及其鄰節(jié)點(diǎn)保留在原簇中，以此來(lái)減少簇結(jié)構(gòu)的變化，但簇維護(hù)的開(kāi)銷(xiāo)仍較大并且獲得的簇結(jié)構(gòu)也不夠優(yōu)化。還有一些機(jī)制采用動(dòng)態(tài)的基于消息驅(qū)動(dòng)的簇維護(hù)策略，這種簇維護(hù)策略可以根據(jù)網(wǎng)絡(luò)環(huán)境和應(yīng)用的需要設(shè)置各種簇維護(hù)門(mén)限和條件，一旦超過(guò)預(yù)設(shè)門(mén)限或條件滿(mǎn)足時(shí)則觸發(fā)相應(yīng)的動(dòng)作，包括簇的調(diào)整或重新分簇。這種方法可以在一定程度上減少簇維護(hù)開(kāi)銷(xiāo)，保持簇結(jié)構(gòu)的相對(duì)穩(wěn)定，并能適應(yīng)節(jié)點(diǎn)的移動(dòng)和鏈路質(zhì)量的變化，是一種較好的簇維護(hù)策略。

具體而言，簇維護(hù)包括兩方面內(nèi)容：節(jié)點(diǎn)（鏈路）的管理和簇的管理。前者包括節(jié)點(diǎn)出現(xiàn)、消失和移動(dòng)；后者包括簇的消失、分裂和合并。由于鏈路的產(chǎn)生、故障、刪除、恢復(fù)對(duì)分簇結(jié)構(gòu)造成的影響包含在節(jié)點(diǎn)出現(xiàn)、消失和移動(dòng)造成的結(jié)果中，因此通常不再單獨(dú)考慮。

五、結(jié)束語(yǔ)

基于分簇算法的分簇結(jié)構(gòu)對(duì)于提高Ad Hoc網(wǎng)絡(luò)的性能至關(guān)重要，分簇結(jié)構(gòu)既有利于移動(dòng)管理、資源分配和信道接入，又可以比較方便地采用結(jié)合先驗(yàn)式和反應(yīng)式優(yōu)點(diǎn)的混合式路由，此外還可以用來(lái)提高廣播的效率和用于構(gòu)造藍(lán)牙網(wǎng)絡(luò)。但是分簇算法本身會(huì)帶來(lái)計(jì)算、通信和維護(hù)開(kāi)銷(xiāo)，為了減少分簇算法的負(fù)面影響，必須提高分簇算法的性能，特別是減少通信和維護(hù)開(kāi)銷(xiāo)。本文介紹、分析和比較了無(wú)線自組網(wǎng)中現(xiàn)存的多種分簇算法，包括有無(wú)簇頭、單跳簇和多跳簇、主動(dòng)分簇和被動(dòng)分簇算法等，它們各有優(yōu)缺點(diǎn)，必須根據(jù)用戶(hù)需求和應(yīng)用場(chǎng)合進(jìn)行合理的選擇。

見(jiàn)www.dcw.org.cn