基于權值的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )分簇算法

摘要：綜述了國際上無(wú)線(xiàn)傳感器網(wǎng)絡(luò )路由算法的主要成果，但重點(diǎn)分析更具有能量有效性的分簇路由算法，總結了各種算法的主要思想，并對其進(jìn)行了性能評價(jià)，提出了一種新的算法，及有待進(jìn)一步研究的問(wèn)題。
關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò )；分簇路由；分簇；能量有效

引言

　　近年來(lái)隨著(zhù)傳感器和無(wú)線(xiàn)通信技術(shù)的進(jìn)步，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )（WSN）技術(shù)發(fā)展迅猛，進(jìn)展很快，使我們可以把大量低成本的傳感器分布在廣闊的區域來(lái)監測我們所感興趣的環(huán)境。傳感器通過(guò)無(wú)線(xiàn)網(wǎng)絡(luò )連接起來(lái)形成無(wú)線(xiàn)傳感器網(wǎng)絡(luò )（WSN），WSN有一些自身的限制，如：有限的能量供應[1,2]，有限的計算能力和有限的連接傳感器的無(wú)線(xiàn)鏈路的帶寬，而且WSN的應用領(lǐng)域也給路由協(xié)議帶來(lái)了一些限制，比如說(shuō)，WSN可能隨意地分布在惡劣的或不可到達的環(huán)境中，人為維護十分困難，因此延長(cháng)網(wǎng)絡(luò )壽命是無(wú)線(xiàn)傳感器網(wǎng)絡(luò )協(xié)議設計的關(guān)鍵技術(shù)。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò )

　　無(wú)線(xiàn)傳感器網(wǎng)絡(luò )由大量傳感器節點(diǎn)和一個(gè)基站（BS）構成，基站是節點(diǎn)與其它網(wǎng)絡(luò )通信的出入口，傳感器節點(diǎn)監測環(huán)境并將收集的數據傳給基站。然而，它能量有限，直接將數據傳給基站會(huì )消耗很多能量（圖1）。采用多跳的路由方法也不理想，因為最接近基站的節點(diǎn)會(huì )因路由大量收到的數據而很快死亡，從而導致后來(lái)到達的數據不能傳給基站。其它的路由方法中[3,4]，PEGASIS中的節點(diǎn)只與鄰居節點(diǎn)通信，節點(diǎn)輪流發(fā)送融合后的數據給BS，基于蟻群算法的路由在盡量選擇最短路徑的同時(shí)考慮每個(gè)節點(diǎn)的能量消耗，以選出更合適的路徑。

　　本文中，我們重點(diǎn)評價(jià)更具有能量有效性的分簇路由算法，它將無(wú)線(xiàn)傳感器網(wǎng)絡(luò )分成若干簇，每個(gè)簇選舉出一個(gè)簇頭，簇頭作為本地基站將簇內節點(diǎn)傳給它的數據進(jìn)行數據融合[5]后再傳給基站（圖2），因而大大降低了節點(diǎn)消耗的能量，延長(cháng)了網(wǎng)絡(luò )壽命。

圖1  傳感器系統模型一

圖2  傳感器網(wǎng)絡(luò )系統模型二

無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中的分簇路由算法
傳統路由算法

　　直接路由算法中節點(diǎn)直接將數據傳送給基站，這樣遠離基站的節點(diǎn)會(huì )消耗很多的能量而很快死亡。而MTE(Minimum Transmission Energy)[6]是它的一個(gè)改進(jìn)，它采用多跳的方法傳送數據，每個(gè)節點(diǎn)運行建立路由以確定下一跳鄰居節點(diǎn)，這個(gè)鄰居節點(diǎn)是朝BS方向上離它最近的節點(diǎn)（假設每個(gè)節點(diǎn)都知道網(wǎng)絡(luò )中其它節點(diǎn)的位置），數據包通過(guò)下一跳鄰居節點(diǎn)傳送直到到達BS。

　　在MTE這種路由算法中最接近基站的節點(diǎn)會(huì )因路由大量傳來(lái)的數據而很快死亡，而直接通信中是離基站最遠的節點(diǎn)最快死亡。

最基本的分簇路由算法

　　為了解決傳統路由算法中的高能量耗散問(wèn)題，提出了LEACH（Low-Energy Adaptive Clustering Hierarchy）[7]—一種最基本的分簇路由算法，每個(gè)節點(diǎn)根據一定的概率周期性地輪換做簇頭，成為簇頭的節點(diǎn)用相同的發(fā)射功率給網(wǎng)絡(luò )中的所有節點(diǎn)廣播消息，非簇頭節點(diǎn)選擇加入收到信號最強的那個(gè)簇頭的簇并用CSMA MAC協(xié)議發(fā)消息給簇頭，通知其成為它的成員。之后，簇頭根據簇中節點(diǎn)數目創(chuàng )建TDMA[8]時(shí)間表告訴每個(gè)節點(diǎn)發(fā)送數據的時(shí)隙，以避免碰撞的發(fā)生。另外，簇頭還要通知簇成員使用哪種CDMA編碼，簇頭也使用這種編碼過(guò)濾收到的數據，這樣鄰居簇的信號就會(huì )被當為噪聲過(guò)濾掉，因此不會(huì )影響簇內通信。節點(diǎn)只在分配給它們的時(shí)隙內發(fā)送數據，其它時(shí)間關(guān)閉其無(wú)線(xiàn)發(fā)射機以節約能量，到此，簇就形成了。在數據發(fā)送階段，簇頭將成員節點(diǎn)傳給它的數據進(jìn)行融合后直接傳給BS。

　　在LEACH中，成員節點(diǎn)在分配的TDMA時(shí)隙內總有數據傳給簇頭，為了節約能量，節點(diǎn)也許只需在它檢測到有興趣的數據時(shí)才傳送數據，另外，算法周期性地分簇會(huì )消耗節點(diǎn)很多能量。因此，我們需要在以后的路由算法中在這些方面對它進(jìn)行改善。

可形成最佳簇的中心控制分簇路由算法

　　LEACH雖節約能量，但它不能形成最佳簇。中心控制算法通過(guò)基站來(lái)控制形成最佳的簇。

　　LEACH－C中，每個(gè)節點(diǎn)發(fā)送包含自身位置信息和能量信息的消息給BS，位置信息可以保證形成優(yōu)良的簇，為了將能耗平均分攤給所有節點(diǎn)，BS計算網(wǎng)絡(luò )節點(diǎn)的平均能量，低于此能量的節點(diǎn)都不能做簇頭，因此用LEACH－C可以形成比LEACH更優(yōu)良的簇，它的其它階段和LEACH一樣。靜態(tài)分簇（Static Clustering）中，簇形成方法和LEACH－C一樣，只是這些簇頭一旦形成，在整個(gè)網(wǎng)絡(luò )生命期都固定不變，其余的數據傳輸方式和LEACH和LEACH－C一樣，但是一旦簇頭能量耗盡，簇內節點(diǎn)就失去了通信能力。

　　LEACH－C和LEACH在仿真時(shí)間內比Static Clustering明顯可以發(fā)送更多的數據給BS，并且每單位能量可傳送更多的數據，但LEACH－C性能最好。

　　由于LEACH在一些情況中所選的簇頭可能全在區域的一端，在另一端的傳感器節點(diǎn)可能偵聽(tīng)不到簇頭發(fā)出的信息，而不能加入任何簇，因此提出了SC(Substractive Clustering)和LMSSC(Least Mean Squared Substractive Clustering)[9]分簇算法。

　　SC的思想是具有最多鄰居數的節點(diǎn)被選為一個(gè)簇的中心，在一個(gè)確定半徑內的其它節點(diǎn)歸為它的簇，之后再尋找新的具有最多鄰居的節點(diǎn)，這樣一直持續下去直到80%的節點(diǎn)已被分簇。

　　LMSSC在SC上進(jìn)行了修改以形成更好的簇，它的思想是在確定半徑內與鄰居節點(diǎn)的距離平方和平均值最小的節點(diǎn)被選為一個(gè)簇的中心，所有這個(gè)半徑內的它的鄰居節點(diǎn)被劃為它的簇。這兩種方法都是在簇形成以后再在簇內選擇合適的簇頭。簇頭將收到的數據進(jìn)行融合后直接或選擇一條代價(jià)最?。ǖ紹S能量消耗最?。┑穆窂綄祿鹘oBS。

　　LMSSC中節點(diǎn)運行的周期比SC中的更長(cháng)，所以L(fǎng)MSSC產(chǎn)生的簇更佳。并且，選擇最小代價(jià)路徑傳送數據的SC和LMSSC比直接傳送數據的SC和LMSSC性能更優(yōu)。

　　HYENAS（Hybrid Energy-Aware Sensor Networks）[10]也是先形成簇，再選擇簇頭，但它用CBR（Case-Based Reasoning）作為一種決策方法來(lái)保證形成合適的簇，CBR技術(shù)通過(guò)吸取每輪結束時(shí)的錯誤經(jīng)歷來(lái)創(chuàng )建黑名單，黑名單是用來(lái)存放一組簇的。這些簇的簇成員所用的能量超過(guò)了網(wǎng)絡(luò )中所有節點(diǎn)所用能量的平均值，當當前每個(gè)簇的特性（如：簇成員數，簇頭到其它節點(diǎn)的距離平方和等）和黑名單中簇的特性有相似之處時(shí)，基站就會(huì )增加一個(gè)簇。如果有少數節點(diǎn)離開(kāi)了原來(lái)的簇時(shí)，它們會(huì )自己形成子簇，子簇簇頭會(huì )單獨為子簇創(chuàng )建TDMA時(shí)間表，然后把這個(gè)消息傳給它最初的簇頭，簇頭再傳給基站。這種方法能處理少數移動(dòng)節點(diǎn)的問(wèn)題，還能大大減少簇頭和移動(dòng)節點(diǎn)的通信距離。

　　當第一個(gè)節點(diǎn)死亡或最后一個(gè)節點(diǎn)死亡時(shí)，HYENAS運行的輪數要比LEACH多。因此，它的網(wǎng)絡(luò )壽命也就相應更長(cháng)。

基于閾值信息的分簇路由算法

　　TEEN（Threshold Sensitive Energy Efficient Sensor Network Protocol）[11]協(xié)議在LEACH上進(jìn)行了改進(jìn)。它的分簇方法和LEACH一樣，只是它的簇成員不像LEACH算法那樣總是發(fā)送數據給簇頭。它的每個(gè)節點(diǎn)設定了兩個(gè)閾值，硬門(mén)限（HT）和軟門(mén)限（ST），當節點(diǎn)監測到的數據大于HT并且與前次監測的數據變化值大于或等于ST時(shí)才發(fā)送數據給簇頭，這樣可以大大減少節點(diǎn)發(fā)射數據的次數，但節點(diǎn)不發(fā)送數據用戶(hù)就會(huì )長(cháng)時(shí)間收不到數據或者認為節點(diǎn)死亡。

　　APTEEN(Adaptive Periodic Threshold-sensitive Energy Efficient Sensor Network Protocol)[12]協(xié)議彌補了TEEN的缺點(diǎn)，簇成員節點(diǎn)除了在數據發(fā)生明顯變化時(shí)發(fā)送外，還會(huì )周期性地發(fā)送消息，這樣節點(diǎn)除了能節約能量外，用戶(hù)收到發(fā)送來(lái)的消息后也可以周期性得獲得已存儲在基站的數據。

　　在每個(gè)節點(diǎn)的平均能量耗散和存活節點(diǎn)總數性能方面，APTEEN介于TEEN和LEACH之間，但TEEN性能最好，因為T(mén)EEN中簇內的節點(diǎn)發(fā)送數據的次數最少。

其它的分簇路由算法

　　PEGASIS（Power-Efficient Gathering in Sensor Information System）[13]的主要思想是每個(gè)節點(diǎn)從最近的鄰居節點(diǎn)接收和發(fā)送數據給最近鄰居節點(diǎn)，并且輪流發(fā)送融合后的數據給BS，這個(gè)方法可將能量負載均勻地分攤給網(wǎng)絡(luò )中的所有節點(diǎn)。

　　PEGASIS：與LEACH相比，當相同數目的節點(diǎn)死亡時(shí)，PEGASIS比LEACH要運行多一倍的輪數。

　　基于蟻群算法的路由算法[14,15]是通過(guò)在整個(gè)網(wǎng)絡(luò )內建立梯度（節點(diǎn)與相鄰節點(diǎn)到基站的最小跳數之差稱(chēng)為梯度）和每個(gè)節點(diǎn)之間的信息素（提示數據包選擇哪條路徑的信息稱(chēng)為信息素）來(lái)進(jìn)行路由選擇。在設計信息素濃度的公式時(shí)，不僅考慮了節點(diǎn)間的梯度，還加入相鄰節點(diǎn)剩余能量的因素。

　　該算法在盡量選擇最短路徑的同時(shí)，還考慮每個(gè)節點(diǎn)的能量消耗，以達到尋找最佳路由的目的。

　　EBRA(Energy-Based Radius Self-Adjust Routing Protocol)[16]中節點(diǎn)會(huì )選擇一條平均單位跳數消耗最少能量的路徑傳送數據，當節點(diǎn)自身的能量降低到一定數值以后，它會(huì )向其鄰居節點(diǎn)廣播進(jìn)行降低半徑的請求來(lái)達到維護路由的目的。

Mobile Ad Hoc中的分簇路由算法

　　在無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中少數節點(diǎn)移動(dòng)的情況下，我們可以借鑒Mobile Ad Hoc網(wǎng)絡(luò )中的分簇算法[17,18]。Mobile Ad Hoc中，由于節點(diǎn)的頻繁移動(dòng)，分簇的目的則是保證穩定的分簇結構，最小化簇建立和維護的開(kāi)銷(xiāo)，最大化系統中移動(dòng)節點(diǎn)的壽命。DCA(Distributed Clustering Algorithm)[19]網(wǎng)絡(luò )拓撲結構在算法執行期間不變，因此它對靜態(tài)網(wǎng)絡(luò )很有用。算法中，只有當節點(diǎn)的具有較大權值的鄰居節點(diǎn)決定了它自己的角色時(shí)，節點(diǎn)才決定自己承擔什么樣的角色。相反，DMAC(Distributed and Mobility-Adaptive Clustering)適用于拓撲結構不斷變化的網(wǎng)絡(luò )，節點(diǎn)不僅對從其它節點(diǎn)發(fā)來(lái)的消息做出適當的反應，還對與其它節點(diǎn)連接的鏈路失敗或新鏈路的出現做出適當的反應。DBCA（Distributed Weighted Clustering Algorithm for Mobile Ad Hoc）[20]的簇形成方法和DWBCP的相似，在簇維護階段，當節點(diǎn)移出了它的簇邊界時(shí)，它就廣播一個(gè)消息要求加入一個(gè)新簇，任何收到該消息的簇頭都會(huì )發(fā)送應答消息給該節點(diǎn)，節點(diǎn)根據消息選擇加入具有最小權值的簇頭的簇，如果在給定的時(shí)間內沒(méi)收到任何消息，就宣布自己做為簇頭。當簇頭消耗的能量超過(guò)事先設定的閾值時(shí)，簇頭就不再擔任這個(gè)角色，該簇重新推選簇頭。

基于權值的分簇算法

　　這里提出一種創(chuàng )新的分簇路由算法——基于權值的分簇路由算法。該算法主要研究的是簇頭選舉方法，每個(gè)節點(diǎn)根據自己的剩余能量、鄰居數目、與所有鄰居的平均距離、與基站的距離、以及能量消耗速度來(lái)計算出自己的權值：

　　其中Ev為節點(diǎn)v的剩余能量，Nv為節點(diǎn)v的鄰居數目，即在節點(diǎn)v發(fā)射范圍內的節點(diǎn)數目之和，δ為簇頭能夠處理的理想的節點(diǎn)數，Dnv與Dbv分別為節點(diǎn)v與鄰居節點(diǎn)的距離之和，與基站的距離，R為簇覆蓋范圍的直徑，Numv為節點(diǎn)v做過(guò)簇頭的次數，Tv為節點(diǎn)v在現在的能量消耗速度下，直到能量水平達到最小可接受的閾值時(shí)的期望時(shí)間，W1—W6為權值因子，根據系統需要選擇，它們之和為1。在鄰居節點(diǎn)中具有最小權值的節點(diǎn)做為簇頭，其它的過(guò)程，諸如數據傳輸過(guò)程都與LEACH中的一樣。

系統主要操作步驟：

　　Step1:根據以上的方法選取簇頭形成簇；

　　Step2:簇頭為每個(gè)簇成員分配TDMA時(shí)間表；

　　Step3:節點(diǎn)在分配的時(shí)隙內發(fā)送數據給簇頭；

　　Step4:簇頭將收到的數據進(jìn)行融合后通過(guò)單跳或多跳的形式傳給基站；

　　Step5:當簇頭的剩余能量小于等于本輪開(kāi)始時(shí)能量的某個(gè)百分比時(shí)，重新分簇。

　　基于權值的分簇路由算法考慮了形成簇頭的多種因素，如簇內通信代價(jià)、簇間通信代價(jià)、節點(diǎn)自身的能量狀況，而LEACH算法只根據節點(diǎn)做過(guò)簇頭的次數來(lái)決定簇頭的選舉，因此它選出的簇頭更合理，產(chǎn)生的簇也更佳。

結語(yǔ)

　　由于傳感器網(wǎng)絡(luò )通常分布在環(huán)境惡劣或人不可到達的地方，所以人為維護是困難的，因此在進(jìn)行數據通信的同時(shí)盡可能延長(cháng)網(wǎng)絡(luò )的壽命是我們需要解決的首要任務(wù)，分簇算法將無(wú)線(xiàn)傳感器網(wǎng)絡(luò )分成若干簇，每個(gè)簇選舉出一個(gè)簇頭，簇頭作為本地基站將簇內節點(diǎn)傳給它的數據進(jìn)行數據融合后再傳給基站，因而大大降低了節點(diǎn)消耗的能量，延長(cháng)了網(wǎng)絡(luò )壽命,本文綜述的分簇路由算法及提出的創(chuàng )新的分簇路由算法——基于權值的分簇路由算法，都是實(shí)現這種目標的有效算法。但后者選出的簇頭在節約能量方面最佳，更受推崇。

　　基于權值的分簇路由算法對權值因子的選擇是人為的，即認為哪個(gè)因素重要，就給相應的因素賦更大的權值，反之，賦更小的值，但這些值究竟應該多大，應該有一個(gè)更具說(shuō)服力的模型來(lái)描述，比如，在作戰環(huán)境、地震檢測、動(dòng)物移動(dòng)中應該具體用什么模型，以及它們對網(wǎng)絡(luò )壽命的影響，這些都是還需要進(jìn)一步研究的問(wèn)題。

　　無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中的路由算法對網(wǎng)絡(luò )的壽命起著(zhù)關(guān)鍵的作用，近年來(lái)，分簇路由算法已頻繁地用于無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中，因為它的路由算法更具有能量有效性。本文綜述了近年來(lái)分簇路由算法的主要成果，及它們的性能比較，并提出了一種在能量方面更有效的創(chuàng )新性算法，以及還需期待研究的問(wèn)題。

參考文獻：

[1] GUPTA G, YOUNIS M. Load-balanced clustering of wireless sensor networks. Communication, 2003. ICC ’03. IEEE International Conference, 2003,1848-1852.
[2] 何朝筍.傳感器網(wǎng)絡(luò )節點(diǎn)調度算法研究與實(shí)現[D].哈爾濱工業(yè)大學(xué),2006, U.D.C.: 681.324
[3] YOUNIS M, YOUSSEF M, ARISHA K. Energy-aware routing in cluster-based sensor networks. Modeling, Analysis and Simulation of Computer and Telecommunications Systems, 2002. MASCOTS 2002. Proceedings.10th IEEE International Symposium, 2002,129 – 136.
[4] 董婷.傳感器網(wǎng)絡(luò )中基于自適應的路由算法研究[D].湖南大學(xué)，2006
[5] TILLAPART P, THAMMAROJSAKUL S, THUMTHAWATWORN T. An approach to hybrid clustering and routing in wireless sensor networks. Aerospace Conference, 2005, 1-8.
[6] HEINZELMAN W R., CHANDRAKASAN A., BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Annual Hawaii International Conference, 2000, 10 pp.
Summary:?Wireless distributed microsensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. In this paper, we look at communication protocols, which can have significant impact on the overall en.....
[7] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H.. An application-specific protocol architecture for wireless microsensor Networks. Wireless Communications, 2002, 4(1): 660-670.
[8] REN Q C, LIANG Q L. An energy-efficient MAC protocol for wireless sensor networks. Global Telecommunications Conference, 2005, 5 pp.
[9] BASAGNI S. Distributed clustering for ad hoc networks. Parallel Architectures, Algorithms, and Networks, 1999.(1-SPAN’99) Proceedings. Fourth International Symposium, 1999, 310-315.
[10] TILLAPART P, THUMTHAWATWORN T, PAKDEEPINIT P. Method for cluster heads selection in wireless sensor networks. Aerospace Conference, 2004, 3615-3623.
[11]  MANJESHWAR A., AGRAWAL D P. TEEN: a routing protocol for enhanced efficiency in wireless sensor networks. Parallel and Distributed Processing Symposium, Proceedings 15th International, 2001, 2009-2015.
[12] MANJESHWAR A, AGRAWAL D P. APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks. Parallel and Distributed Processing Symposium, Proceedings of the International, 2002, 195-202.
[13] LINDSEY S, RAGHAVENDRA C S. PEGASIS: power-efficient gathering in sensor information systems. Aerospace Conference Proceedings, 2002, 1125-1130.
[14] DORIGO M., MANIEZZO V, COLORNI A. ant system: optimization by a colony of colony of cooperating agents. Systems, Man, and Cybernetics, Part B. IEEE Transaction, 1996, 1(26): 29-41.
[15]康望星.基于蟻群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )路由算法研究[D].哈爾濱工業(yè)大學(xué),2006
[16]柴云鶴.基于能量的半徑自適應傳感器網(wǎng)絡(luò )路由協(xié)議設計與實(shí)現[D].哈爾濱工業(yè)大學(xué),U.D.C. : 681.14，2006
[17] YANG W D, ZHANG G Z. A weight-based clustering algorithm for mobile ad hoc networks. Wireless and Mobile Communication, 2007. ICWMC’07. Third International Conference, 2007, 3-3.
[18] ZOUHAIR E B, KADOCH M, AGBA B L. A flexible weight based clustering algorithm in mobile ad hoc networks. Systems and Networks Communications, 2006. ICSNC’06. International Conference, 2006, 50-50.  
[19] HUANG G Y, LI X W, HE J. Energy-efficiency analysis of cluster-based routing protocol in wireless sensor networks. Aerospace Conference, 2006, 8 pp.
[20] CHOI W C, WOO M. A distributed weighted clustering algorithm for mobile ad hoc networks. Telecommunications, 2006. AICT-ICIW’06. International conference on Internet and Web Application and Services/Advanced International Conference, 2006, 73-73.