無線傳感器網(wǎng)絡(luò)由大量傳感器節(jié)點和一個基站（BS）構(gòu)成，基站是節(jié)點與其它網(wǎng)絡(luò)通信的出入口，傳感器節(jié)點監(jiān)測環(huán)境并將收集的數(shù)據(jù)傳給基站。然而，它能量有限，直接將數(shù)據(jù)傳給基站會消耗很多能量（圖1）。采用多跳的路由方法也不理想，因為zui接近基站的節(jié)點會因路由大量收到的數(shù)據(jù)而很快死亡，從而導(dǎo)致后來到達的數(shù)據(jù)不能傳給基站。其它的路由方法中[3,4]，PEGASIS中的節(jié)點只與鄰居節(jié)點通信，節(jié)點輪流發(fā)送融合后的數(shù)據(jù)給BS，基于蟻群算法的路由在盡量選擇zui短路徑的同時考慮每個節(jié)點的能量消耗，以選出更合適的路徑。
　　
　　本文中，我們重點評價更具有能量有效性的分簇路由算法，它將無線傳感器網(wǎng)絡(luò)分成若干簇，每個簇選舉出一個簇頭，簇頭作為本地基站將簇內(nèi)節(jié)點傳給它的數(shù)據(jù)進行數(shù)據(jù)融合[5]后再傳給基站（圖2），因而大大降低了節(jié)點消耗的能量，延長了網(wǎng)絡(luò)壽命。　　　
　　傳統(tǒng)路由算法
　　
　　直接路由算法中節(jié)點直接將數(shù)據(jù)傳送給基站，這樣遠離基站的節(jié)點會消耗很多的能量而很快死亡。而MTE（MinimumTransmissionEnergy）[6]是它的一個改進，它采用多跳的方法傳送數(shù)據(jù)，每個節(jié)點運行建立路由以確定下一跳鄰居節(jié)點，這個鄰居節(jié)點是朝BS方向上離它zui近的節(jié)點（假設(shè)每個節(jié)點都知道網(wǎng)絡(luò)中其它節(jié)點的位置），數(shù)據(jù)包通過下一跳鄰居節(jié)點傳送直到到達BS。
　　
　　在MTE這種路由算法中zui接近基站的節(jié)點會因路由大量傳來的數(shù)據(jù)而很快死亡，而直接通信中是離基站zui遠的節(jié)點zui快死亡。
　　
　　zui基本的分簇路由算法
　　
　　為了解決傳統(tǒng)路由算法中的高能量耗散問題，提出了LEACH（Low-EnergyAdaptiveClusteringHierarchy）[7]—一種zui基本的分簇路由算法，每個節(jié)點根據(jù)一定的概率周期性地輪換做簇頭，成為簇頭的節(jié)點用相同的發(fā)射功率給網(wǎng)絡(luò)中的所有節(jié)點廣播消息，非簇頭節(jié)點選擇加入收到信號zui強的那個簇頭的簇并用CSMAMAC協(xié)議發(fā)消息給簇頭，通知其成為它的成員。之后，簇頭根據(jù)簇中節(jié)點數(shù)目創(chuàng)建TDMA[8]時間表告訴每個節(jié)點發(fā)送數(shù)據(jù)的時隙，以避免碰撞的發(fā)生。另外，簇頭還要通知簇成員使用哪種CDMA編碼，簇頭也使用這種編碼過濾收到的數(shù)據(jù)，這樣鄰居簇的信號就會被當為噪聲過濾掉，因此不會影響簇內(nèi)通信。節(jié)點只在分配給它們的時隙內(nèi)發(fā)送數(shù)據(jù)，其它時間關(guān)閉其無線發(fā)射機以節(jié)約能量，到此，簇就形成了。在數(shù)據(jù)發(fā)送階段，簇頭將成員節(jié)點傳給它的數(shù)據(jù)進行融合后直接傳給BS。
　　
　　在LEACH中，成員節(jié)點在分配的TDMA時隙內(nèi)總有數(shù)據(jù)傳給簇頭，為了節(jié)約能量，節(jié)點也許只需在它檢測到有興趣的數(shù)據(jù)時才傳送數(shù)據(jù)，另外，算法周期性地分簇會消耗節(jié)點很多能量。因此，我們需要在以后的路由算法中在這些方面對它進行改善。
　　
　　可形成*簇的中心控制分簇路由算法
　　
　　LEACH雖節(jié)約能量，但它不能形成*簇。中心控制算法通過基站來控制形成*的簇。
　　
　　LEACH－C中，每個節(jié)點發(fā)送包含自身位置信息和能量信息的消息給BS，位置信息可以保證形成優(yōu)良的簇，為了將能耗平均分攤給所有節(jié)點，BS計算網(wǎng)絡(luò)節(jié)點的平均能量，低于此能量的節(jié)點都不能做簇頭，因此用LEACH－C可以形成比LEACH更優(yōu)良的簇，它的其它階段和LEACH一樣。靜態(tài)分簇（StaticClustering）中，簇形成方法和LEACH－C一樣，只是這些簇頭一旦形成，在整個網(wǎng)絡(luò)生命期都固定不變，其余的數(shù)據(jù)傳輸方式和LEACH和LEACH－C一樣，但是一旦簇頭能量耗盡，簇內(nèi)節(jié)點就失去了通信能力。
　　
　　LEACH－C和LEACH在仿真時間內(nèi)比StaticClustering明顯可以發(fā)送更多的數(shù)據(jù)給BS，并且每單位能量可傳送更多的數(shù)據(jù)，但LEACH－C性能。
　　
　　由于LEACH在一些情況中所選的簇頭可能全在區(qū)域的一端，在另一端的傳感器節(jié)點可能偵聽不到簇頭發(fā)出的信息，而不能加入任何簇，因此提出了SC（SubstractiveClustering）和LMSSC（LeastMeanSquaredSubstractiveClustering）[9]分簇算法。
　　
　　SC的思想是具有zui多鄰居數(shù)的節(jié)點被選為一個簇的中心，在一個確定半徑內(nèi)的其它節(jié)點歸為它的簇，之后再尋找新的具有zui多鄰居的節(jié)點，這樣一直持續(xù)下去直到80%的節(jié)點已被分簇。
　　
　　LMSSC在SC上進行了修改以形成更好的簇，它的思想是在確定半徑內(nèi)與鄰居節(jié)點的距離平方和平均值zui小的節(jié)點被選為一個簇的中心，所有這個半徑內(nèi)的它的鄰居節(jié)點被劃為它的簇。這兩種方法都是在簇形成以后再在簇內(nèi)選擇合適的簇頭。簇頭將收到的數(shù)據(jù)進行融合后直接或選擇一條代價zui小（到BS能量消耗zui小）的路徑將數(shù)據(jù)傳給BS。
　　
　　LMSSC中節(jié)點運行的周期比SC中的更長，所以LMSSC產(chǎn)生的簇更佳。并且，選擇zui小代價路徑傳送數(shù)據(jù)的SC和LMSSC比直接傳送數(shù)據(jù)的SC和LMSSC性能更優(yōu)。
　　
　　HYENAS（HybridEnergy-AwareSensorNetworks）[10]也是先形成簇，再選擇簇頭，但它用CBR（Case-BasedReasoning）作為一種決策方法來保證形成合適的簇，CBR技術(shù)通過吸取每輪結(jié)束時的錯誤經(jīng)歷來創(chuàng)建黑名單，黑名單是用來存放一組簇的。這些簇的簇成員所用的能量超過了網(wǎng)絡(luò)中所有節(jié)點所用能量的平均值，當當前每個簇的特性（如：簇成員數(shù)，簇頭到其它節(jié)點的距離平方和等）和黑名單中簇的特性有相似之處時，基站就會增加一個簇。如果有少數(shù)節(jié)點離開了原來的簇時，它們會自己形成子簇，子簇簇頭會單獨為子簇創(chuàng)建TDMA時間表，然后把這個消息傳給它zui初的簇頭，簇頭再傳給基站。這種方法能處理少數(shù)移動節(jié)點的問題，還能大大減少簇頭和移動節(jié)點的通信距離。
　　
　　當*個節(jié)點死亡或zui后一個節(jié)點死亡時，HYENAS運行的輪數(shù)要比LEACH多。因此，它的網(wǎng)絡(luò)壽命也就相應(yīng)更長。
　　
　　基于閾值信息的分簇路由算法
　　
　　TEEN（ThresholdSensitiveEnergyEfficientSensorNetworkProtocol）[11]協(xié)議在LEACH上進行了改進。它的分簇方法和LEACH一樣，只是它的簇成員不像LEACH算法那樣總是發(fā)送數(shù)據(jù)給簇頭。它的每個節(jié)點設(shè)定了兩個閾值，硬門限（HT）和軟門限（ST），當節(jié)點監(jiān)測到的數(shù)據(jù)大于HT并且與前次監(jiān)測的數(shù)據(jù)變化值大于或等于ST時才發(fā)送數(shù)據(jù)給簇頭，這樣可以大大減少節(jié)點發(fā)射數(shù)據(jù)的次數(shù)，但節(jié)點不發(fā)送數(shù)據(jù)用戶就會長時間收不到數(shù)據(jù)或者認為節(jié)點死亡。
　　
　　APTEEN（AdaptivePeriodicThreshold-sensitiveEnergyEfficientSensorNetworkProtocol）[12]協(xié)議彌補了TEEN的缺點，簇成員節(jié)點除了在數(shù)據(jù)發(fā)生明顯變化時發(fā)送外，還會周期性地發(fā)送消息，這樣節(jié)點除了能節(jié)約能量外，用戶收到發(fā)送來的消息后也可以周期性得獲得已存儲在基站的數(shù)據(jù)。
　　
　　在每個節(jié)點的平均能量耗散和存活節(jié)點總數(shù)性能方面，APTEEN介于TEEN和LEACH之間，但TEEN性能，因為TEEN中簇內(nèi)的節(jié)點發(fā)送數(shù)據(jù)的次數(shù)zui少。
　　
　　其它的分簇路由算法
　　
　　PEGASIS（Power-EfficientGatheringinSensorInformat*tem）[13]的主要思想是每個節(jié)點從zui近的鄰居節(jié)點接收和發(fā)送數(shù)據(jù)給zui近鄰居節(jié)點，并且輪流發(fā)送融合后的數(shù)據(jù)給BS，這個方法可將能量負載均勻地分攤給網(wǎng)絡(luò)中的所有節(jié)點。
　　
　　PEGASIS：與LEACH相比，當相同數(shù)目的節(jié)點死亡時，PEGASIS比LEACH要運行多一倍的輪數(shù)。
　　
　　基于蟻群算法的路由算法[14,15]是通過在整個網(wǎng)絡(luò)內(nèi)建立梯度（節(jié)點與相鄰節(jié)點到基站的zui小跳數(shù)之差稱為梯度）和每個節(jié)點之間的信息素（提示數(shù)據(jù)包選擇哪條路徑的信息稱為信息素）來進行路由選擇。在設(shè)計信息素濃度的公式時，不僅考慮了節(jié)點間的梯度，還加入相鄰節(jié)點剩余能量的因素。
　　
　　該算法在盡量選擇zui短路徑的同時，還考慮每個節(jié)點的能量消耗，以達到尋找*路由的目的。
　　
　　EBRA（Energy-BasedRadiusSelf-AdjustRoutingProtocol）[16]中節(jié)點會選擇一條平均單位跳數(shù)消耗zui少能量的路徑傳送數(shù)據(jù)，當節(jié)點自身的能量降低到一定數(shù)值以后，它會向其鄰居節(jié)點廣播進行降低半徑的請求來達到維護路由的目的。
　　
　　AdHoc中的分簇路由算法
　　
　　在無線傳感器網(wǎng)絡(luò)中少數(shù)節(jié)點移動的情況下，我們可以借鑒AdHoc網(wǎng)絡(luò)中的分簇算法[17,18]。AdHoc中，由于節(jié)點的頻繁移動，分簇的目的則是保證穩(wěn)定的分簇結(jié)構(gòu)，zui小化簇建立和維護的開銷，zui大化系統(tǒng)中移動節(jié)點的壽命。DCA（DistributedClusteringAlgorithm）[19]網(wǎng)絡(luò)拓撲結(jié)構(gòu)在算法執(zhí)行期間不變，因此它對靜態(tài)網(wǎng)絡(luò)很有用。算法中，只有當節(jié)點的具有較大權(quán)值的鄰居節(jié)點決定了它自己的角色時，節(jié)點才決定自己承擔什么樣的角色。相反，DMAC（DistributedandMobility-AdaptiveClustering）適用于拓撲結(jié)構(gòu)不斷變化的網(wǎng)絡(luò)，節(jié)點不僅對從其它節(jié)點發(fā)來的消息做出適當?shù)姆磻?yīng)，還對與其它節(jié)點連接的鏈路失敗或新鏈路的出現(xiàn)做出適當?shù)姆磻?yīng)。DBCA（DistributedWeightedClusteringAlgorithmforAdHoc）[20]的簇形成方法和DWBCP的相似，在簇維護階段，當節(jié)點移出了它的簇邊界時，它就廣播一個消息要求加入一個新簇，任何收到該消息的簇頭都會發(fā)送應(yīng)答消息給該節(jié)點，節(jié)點根據(jù)消息選擇加入具有zui小權(quán)值的簇頭的簇，如果在給定的時間內(nèi)沒收到任何消息，就宣布自己做為簇頭。當簇頭消耗的能量超過事先設(shè)定的閾值時，簇頭就不再擔任這個角色，該簇重新推選簇頭。
　　
　　基于權(quán)值的分簇算法
　　
　　這里提出一種創(chuàng)新的分簇路由算法——基于權(quán)值的分簇路由算法。該算法主要研究的是簇頭選舉方法，每個節(jié)點根據(jù)自己的剩余能量、鄰居數(shù)目、與所有鄰居的平均距離、與基站的距離、以及能量消耗速度來計算出自己的權(quán)值：　　
　　其中Ev為節(jié)點v的剩余能量，Nv為節(jié)點v的鄰居數(shù)目，即在節(jié)點v發(fā)射范圍內(nèi)的節(jié)點數(shù)目之和，δ為簇頭能夠處理的理想的節(jié)點數(shù)，Dnv與Dbv分別為節(jié)點v與鄰居節(jié)點的距離之和，與基站的距離，R為簇覆蓋范圍的直徑，Numv為節(jié)點v做過簇頭的次數(shù)，Tv為節(jié)點v在現(xiàn)在的能量消耗速度下，直到能量水平達到zui小可接受的閾值時的期望時間，W1—W6為權(quán)值因子，根據(jù)系統(tǒng)需要選擇，它們之和為1。在鄰居節(jié)點中具有zui小權(quán)值的節(jié)點做為簇頭，其它的過程，諸如數(shù)據(jù)傳輸過程都與LEACH中的一樣。
　　
　　系統(tǒng)主要操作步驟：
　　
　　Step1:根據(jù)以上的方法選取簇頭形成簇；
　　
　　Step2:簇頭為每個簇成員分配TDMA時間表；
　　
　　Step3:節(jié)點在分配的時隙內(nèi)發(fā)送數(shù)據(jù)給簇頭；
　　
　　Step4:簇頭將收到的數(shù)據(jù)進行融合后通過單跳或多跳的形式傳給基站；
　　
　　Step5:當簇頭的剩余能量小于等于本輪開始時能量的某個百分比時，重新分簇。
　　
　　基于權(quán)值的分簇路由算法考慮了形成簇頭的多種因素，如簇內(nèi)通信代價、簇間通信代價、節(jié)點自身的能量狀況，而LEACH算法只根據(jù)節(jié)點做過簇頭的次數(shù)來決定簇頭的選舉，因此它選出的簇頭更合理，產(chǎn)生的簇也更佳。
　　
　　結(jié)語
　　
　　由于傳感器網(wǎng)絡(luò)通常分布在環(huán)境惡劣或人不可到達的地方，所以人為維護是困難的，因此在進行數(shù)據(jù)通信的同時盡可能延長網(wǎng)絡(luò)的壽命是我們需要解決的首要任務(wù)，分簇算法將無線傳感器網(wǎng)絡(luò)分成若干簇，每個簇選舉出一個簇頭，簇頭作為本地基站將簇內(nèi)節(jié)點傳給它的數(shù)據(jù)進行數(shù)據(jù)融合后再傳給基站，因而大大降低了節(jié)點消耗的能量，延長了網(wǎng)絡(luò)壽命,本文綜述的分簇路由算法及提出的創(chuàng)新的分簇路由算法——基于權(quán)值的分簇路由算法，都是實現(xiàn)這種目標的有效算法。但后者選出的簇頭在節(jié)約能量方面*，更受推崇。
　　
　　基于權(quán)值的分簇路由算法對權(quán)值因子的選擇是人為的，即認為哪個因素重要，就給相應(yīng)的因素賦更大的權(quán)值，反之，賦更小的值，但這些值究竟應(yīng)該多大，應(yīng)該有一個更具說服力的模型來描述，比如，在作戰(zhàn)環(huán)境、地震檢測、動物移動中應(yīng)該具體用什么模型，以及它們對網(wǎng)絡(luò)壽命的影響，這些都是還需要進一步研究的問題。
　　
　　無線傳感器網(wǎng)絡(luò)中的路由算法對網(wǎng)絡(luò)的壽命起著關(guān)鍵的作用，近年來，分簇路由算法已頻繁地用于無線傳感器網(wǎng)絡(luò)中，因為它的路由算法更具有能量有效性。本文綜述了近年來分簇路由算法的主要成果，及它們的性能比較，并提出了一種在能量方面更有效的創(chuàng)新性算法，以及還需期待研究的問題。
　　
　　作者：王斯瑤吳援明謝光忠電子科技大學光電信息學院