一種能量均衡的無線傳感器網絡分簇算法

（1.三峽大學 電氣信息學院， 湖北 宜昌 443002；2.武漢理工大學 計算機學院， 武漢 430063）

摘要：為了延長網絡的生存時間，提出了一種能量均衡的無線傳感器網絡分簇算法（EBCA），該算法優先選擇剩余能量較多的節點作為簇首，以平衡節點的能量消耗。仿真實驗結果表明：無論同構網還是異構網，該算法都能顯著地推遲網絡第一個節點的死亡時間，其性能明顯優于LEACH算法。

關鍵詞：無線傳感器網絡；能量均衡；分簇算法

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2008)11-3424-02



Energy-balanceable clustering algorithm for wireless sensor networks



GONG Ben-can1，2，LI La-yuan2，JIANG Ting-yao1，WANG Xiang-li2

(1.College of Electrical Engineering Information Technology， China Three Gorges University， Yichang Hubei 443002， China;2.College of Computer Science Technology， Wuhan University of Technology， Wuhan 430063， China)

Abstract:This paper presented an energy-balanceable clustering algorithm(EBCA) for wireless sensor networks to prolong the network lifetime. It preferentially chose those nodes with more energy as the cluster heads to balance energy dissipation in the nodes. Simulation results show that the proposed algorithm obviously postpones the death time of the first node for homogenous and heterogeneous wireless sensor networks， and performs much better than LEACH algorithm.

Key words:wireless sensor networks; energy-balanceable; clustering algorithm

無線傳感器網絡采用自組織方式，具有快速展開、抗毀性強等特點，廣泛應用于軍事偵察、環境監測、醫療監護、空間探索、災難搶險等領域。傳感器節點有嚴格的能量限制，且難以進行能量補充，如何合理地利用網絡能量是設計傳感器網絡所面臨的首要問題。將傳感器節點組織成簇的形式可以有效地減少能量消耗。許多高效的路由算法^[1~5]都是在簇結構的基礎上進行設計的，如LEACH^[1]、LEACH_C^[2]、PEGASIS^[3]等。

LEACH算法中，所有節點輪流擔任簇首以達到平衡節點能量消耗的目的。網絡的工作周期被分為若干輪，每輪由初始化和數據傳輸兩個階段組成。在初始化階段， 每個節點產生一個隨機數，并根據當前輪數計算出一個閾值，如果隨機數小于閾值，則該節點成為簇首，普通節點加入與之最近的簇。由于簇首的選擇是隨機的， 每輪選出的簇首數量相差很大，無法做到最優。LEACH_C算法是集中式的簇首產生算法。每輪開始時各個節點把自身位置和當前能量報告給基站，能量高于平均值的節點成為候選簇首；然后采用模擬退火算法從候選節點中選出數量合適且位置最優的節點成為簇首；最后，基站把分簇結果廣播給每個節點。LEACH_C算法每輪選出的簇首數量穩定且分布均勻，因此，其性能優于LEACH算法，但它需要網絡的全局信息，可擴展性差。PEGASIS算法按照距離最短的原則，通過貪婪算法將所有的節點組織成鏈狀，并隨機選擇一個節點作為簇首，鏈兩端數據沿鏈傳輸到簇首，并在傳輸過程中進行融合，最后由簇首將數據發送給基站。由于每個節點都以最小功率發送數據，它比LEACH和LEACH_C更能延長網絡的生存期，但PEGASIS需要全局的地理位置信息，并且數據沿一條鏈傳輸，具有很大的時延。本文提出的算法根據節點的剩余能量選取簇首，節點的剩余能量越高，當選為簇首的幾率越大，很好地平衡了節點的能量，延長了網絡的生存時間。

1系統模型

11網絡模型

N個傳感器節點隨機均勻地分布在一個正方形區域內，并且具有如下性質:a）所有傳感器節點部署后不再移動，基站惟一且位置固定；b)所有節點具有相似的通信和處理能力，沒有安裝GPS，無法知道其具體位置；c)所有節點都具備數據融合功能；d）節點的能量不能補充，節點可以根據它與接收者的距離遠近，自由調整發射功率以節省能量。

12無線通信模型

本文采用與文獻[2]相同的無線通信模型。發送方傳輸k bit的數據到距離為d的接收方所消耗的能量為

Et(k，d)=kEelec+kεfsd2d＜d0

kEelec+kεmpd4d≥d0(1)

其中:Eelec表示發射電路消耗的能量；εfs和εmp為功率放大器所消耗的能量；d0為常量。

節點接收k bit的數據所消耗的能量為

Er(k)=kEelec(2)

將m個長度為k的數據包融合所消耗的能量為

Ef(m，k)=mkEfusion(3)

其中:Efusion表示融合1 bit的數據所消耗的能量。

2EBCA及分析

與LEACH算法一致，EBCA同樣按輪運行。每輪分為簇生成（Tcluster）和數據傳輸（Tdata）兩個階段，為了保證網絡的有效工作時間，算法設置Tdata>>Tcluster，并且每輪運行Tcluster+Tdata后自動觸發，重新選擇簇首。EBCA以節點的剩余能量作為選擇簇首的依據，只有剩余能量不小于網絡平均能量的節點才能競爭簇首。一個節點成為簇首的門限值按式（4）計算:

Thead=Pinit×Eresidual/(4)

其中：Pinit為剩余能量高于網絡平均能量的節點成為簇首的概率；Eresidual為當前節點的剩余能量；為網絡平均能量。節點部署完畢后，由基站發送廣播信號，啟動所有傳感器節點運行，廣播包中包含Pinit和的初始值，Pinit固定不變，隨著網絡的運行，將逐漸變小，如何動態計算？一種方法是：所有節點在全網范圍內廣播其剩余能量，每個節點收到其他節點的能量值后計算網絡的平均能量。這種方法將帶來很大的控制開銷和網絡延遲。由于網絡分布均勻，可用簇內節點的平均能量來估算。EBCA簇生成算法的偽代碼如下:

以上代碼中，1~4表示節點接收基站的初始化廣播消息；5~9表示節點計算成為簇首的門限值，如果節點的剩余能量大于或等于平均能量且隨機數小于門限值，則該節點當選為簇首，并用設定的功率向全網廣播其成為簇首的消息；10~14表示當一個普通節點收到簇首公告消息后，根據接收信號的強度計算它與簇首的距離，并保留與之最近的簇首號；15~20表示簇首選舉的時間到期后，每個普通節點向簇首發送加入簇的消息，每個簇首則接收簇成員的加入；21、22表示簇成員加入后，簇首給每個簇成員分配TDMA時隙。

簇生成結束后，節點進入數據采集階段，每個成員節點在給定的時隙內采集數據，并根據自己與簇首的距離調整發射功率，將數據發送給簇首，其他時間則關閉收發電路，以節省能量；簇首將數據融合后直接發送給基站。為了降低簇生成開銷，每輪需連續采集若干幀后（實驗設為20）才轉入下一輪。在一輪結束前，每個簇成員采用捎帶方式向簇首報告其剩余能量，簇首計算簇內節點的平均剩余能量，并將其值廣播給每個成員節點。在EBCA中，基站發送了一個BS_msg，每個簇首發送了一個Head_Msg、一個TDMA時隙分配消息和一個平均剩余能量消息，每個簇成員發送了一個Join_msg，因此，其控制開銷為O(N)。其中：N為網絡節點數。

3仿真實驗

為了驗證本文算法的有效性，采用MATLAB編程，將EBCA與LEACH兩種算法進行了對比實驗。實驗中各項參數設置如表1所示。

實驗網絡分同構網和異構網兩類。同構網中所有節點的初始能量為2 J，異構網中所有節點的初始能量隨機分布在1~3 J。實驗結果如圖1、2所示。

圖1、2表明：無論同構網還是異構網，EBCA中第一個節點的死亡時間都晚于LEACH，并且所有節點的死亡時間更加集中，說明EBCA的性能更優，能量消耗更加均衡。由于傳感器網絡中節點的死亡會帶來傳感空洞，造成網絡質量的下降，通常用第一個節點的死亡時間來判斷分簇算法的性能。兩種算法中第一個節點的死亡時間如表2所示。

表2第一個節點的死亡時間

網絡類型LEACH/輪EBCA/輪性能提高率/%

從表2可以看出：對異構網而言，EBCA的性能提高更多。為了進一步驗證EBCA能量消耗的均衡性，本文對節點剩余能量的差異程度進行了對比實驗，實驗結果如圖3、4所示。

從圖3、4可以看出，對同構網，EBCA中所有節點的能量標準差相對穩定；而LEACH中能量標準差隨著網絡運行時間的延長而線性增長。這是因為LEACH算法中，雖然所有節點輪流作為簇首，但由于簇首按概率產生，每輪產生的簇首數量并不穩定。實驗發現最多時一輪產生的簇首數量高達10個，而最少時只有1個。當某一輪簇首較少時，簇內成員數必然增加，從而使簇首消耗更多的能量。對異構網，由于網絡節點的初始能量不同，EBCA中能量標準差開始時較大，但隨著網絡的運行，其值逐漸減小，而LEACH的能量標準差始終較大。這是因為EBCA優先選取剩余能量較多的節點作為簇首，而LEACH中所有節點輪流作為簇首。以上實驗結果說明：EBCA能很好地均衡節點的能量消耗，從而延長網絡壽命。

4結束語

無線傳感器網絡是一個能量受限系統，能量問題是算法設計時需要考慮的首要因素。本文提出了一種新穎的分布式無線傳感器網絡分簇算法，算法中節點根據其剩余能量的大小來競爭簇首，普通節點則加入與之最近的簇，并在簇內實行數據融合。為了節省開銷，簇生成的時間要遠小于數據采集的時間。實驗表明:EBCA算法中節點的能量消耗更加均衡，網絡壽命更長，特別是在能量異構的環境下，網絡生存時間是LEACH算法的兩倍以上。

參考文獻：

［1］HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences.Maui:IEEE Computer Society，2000:3005-3014.

[2]HEINZELMAN W，CHANDRAKASAN A，BALAKRISAN H.An application specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Networking，2002，1(4): 660-670.

[3]LINDSEY S，RAGHAVENDRA C S.PEGASIS:power-efficient gathe-ring in sensor information systems[C]//Proc of the IEEE Aerospace Conf. Montana:IEEE Aerospace and Electronic Systems Society，2002:1125-1130.

[4]YOUNIS O，FAHMY S.Heed:a hybrid，energy-efficient， distributed clustering approach for Ad hoc sensor networks[J].IEEE Trans on Mobile Computing，2004，3(4):660-669.

[5]卿利，朱清新，王明文.異構傳感器網絡的分布式能量有效成簇算法[J].軟件學報，2006，17(3):481-489.