基于剩余能量與最小鄰近簇半徑的成簇算法

張作鋒　劉三陽

摘 要：針對LEACH算法在選舉簇首時沒有考慮節點的剩余能量，并且簇首的分布不均勻，簇內節點與簇首采取單跳通信，從而影響網絡生命期的問題，提出了利用剩余能量和最小鄰近簇半徑調整節點成為簇首的概率，并在簇內對部分節點采取多跳通信的成簇算法。仿真結果表明，該算法有效延長了網絡生命期，均衡了簇首的分布，并且改善了簇內的結構。

關鍵詞：簇首；網絡生命期；成簇算法；剩余能量

中圖分類號：TP393文獻標識碼：B

文章編號：1004-373X(2009)03-004-03

Clustering Algorithm Based on Residual Energy and Least Adjacent Clustering Radius

ZHANG Zuofeng,LIU Sanyang

(Xidian University,Xi′an,710071,China)

Abstract：As for the problem of LEACH clustering algorithm not considering the residual energy of nodes when selecting cluster heads,and the distributing of the heads not uniformity,members of the cluster communicating with the head by one-hop,which impacts lifetime of the network.A clustering algorithm is proposed which adjusts the probability of becoming cluster head by residual energy and least adjacent clustering radius,and takes multi-hop communicating for some nodes.The results of simulation prove that this algorithm can prolong the lifetime of network and balance distributing of the heads and improve structure of the members of cluster.

Keywords：cluster head;lifetime of network;clustering algorithm;residual energy

0 引 言

無線傳感器網絡(Wireless Sensor Networks,WSN)由部署在監測區域內的傳感器節點組成，它通過無線通信的方式形成一個網絡系統，在軍事國防、災難預警、環境控制、信息通信等各個領域都有著十分廣泛的應用［1］。傳感器節點體積小，能量有限，處理能力低，如何充分利用有限的能量，提高網絡生命期是傳感器網絡面臨的首要任務。

人們基于節能的考慮，提出了各種各樣的拓撲控制算法。根據網絡拓撲結構劃分為平面算法和分簇算法［2］。平面拓撲控制算法中，各節點地位相同，通過功率控制簡化網絡拓撲結構，從而減少沖突、干擾，達到節能的目的。典型算法有COMPOW［3］，LMA和LMN［4］等。分簇算法是無線傳感器網絡節省能量，延長網絡生命期的有效方法。節點分簇的主要思想是根據某種規則選擇出一些節點成為簇首，在剩余節點中繼續按某種規則選擇節點加入簇首，形成簇。

典型的分布式簇首選取算法有LEACH(Low-Energy Adaptive Clustering Hierarchy)［5］，HEED(Hybrid Energy Efficient Distributed Clustering)［6］和DCHS(Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection)［7］等。LEACH算法中，所有節點輪流充當簇首，網絡周期性地進行簇首選舉，每個周期稱為一輪(round)。在每輪中，各節點獨立運行公式產生一個數，再生成一個隨機數，通過兩個數的比較來判斷節點是否當選簇首。在每輪中，所有簇首選舉后，進入穩定工作階段。HEED算法中，簇首的選擇主要依據主、次兩個參數。主參數依賴于節點剩余能量，用于隨機選取初始簇首集合，具有較多剩余能量的節點將有較大的概率暫時成為簇首，而最終該節點是否成為簇首取決于剩余能量是否比周圍節點多得多；次參數依賴于簇內通信開銷。DCHS算法針對LEACH算法中的不足，綜合考慮節點當前能量和閾值對簇首選取的影響。

針對LEACH算法的不足和文獻只考慮剩余能量的不足，提出了基于剩余能量和最小鄰近簇半徑的成簇算法(Based on Residual Energy and Least Adjacent Clustering Radius,ECR)，并對簇內結構合理化。通過對LEACH算法的修改，使得最小鄰近簇半徑小的節點當選簇首的概率降低；剩余能量大的節點當選簇首的概率增大，并與能量消耗模型結合，以降低能量消耗為目的，改善簇內拓撲結構。通過與LEACH算法的比較，仿真結果表明，ECR算法延長了網絡生命期，均衡了簇首能耗負擔，簇首分布較均勻，簇內結構更加合理。

1 基本概念及相關知識

1.1 傳感器網絡生命期

根據服務類型的不同，傳感器網絡生命期的定義也不相同。這里定義從節點部署開始到第一個節點死亡為止。

1.2 最小鄰近簇半徑

在LEACH算法中，節點依據概率和一個閾值來決定是否成為簇首節點。假設已經選擇了m個簇首，當選舉第m+1個簇首時，要考慮當前節點到m個簇首的最小距離R(i)。這個距離定義為最小鄰近簇半徑。

用公式表示為:

R(i)=min1≤j≤mi≠j{dist}(1)

其中：node(i)為節點i；C(j)為簇首節點j；dist為歐氏距離。

1.3 LEACH算法

在LEACH算法中，對每一個節點i設定了一個閾值T(i):

T(i)=p1-pmod(r,1/p),i∈G

0,其他(2)

其中：p為簇首節點占網絡節點總數的百分比；r為當前輪數；G表示網絡中最近1/p輪未當選簇首的節點的集合。

LEACH算法如下：

設有n個節點：

Step1:r=1:rmax(rmax為最大輪數值);

Step2:對于node(i)∈G,根據式(2)算出T(i)，node(i)麲，則T(i)=0;

Step3:對于node(i)產生一個0~1之間的隨機數rand(i);

Step4:比較rand(i)與T(i)，若rand(i)

Step5:若i>n即本輪簇首選舉完成，進入穩定工作階段;

Step6:若r

1.4 能量消耗模型

這里采用文獻［9］所采用的無線信道模型及其能量公式。發送方傳輸l比特信息到距離為d的接收方時，發送能量開銷為：

ETx(l,d)=lEelec+lεfsd2,d

lEelec+lεmpd4,d≥do(3)

其中，do為環境因素決定的一個常數；Eelec為傳感節點電子能量消耗；εfs為自由空間無線電子信號放大所消耗能量；εmp對應于多徑衰落信道。即：當節點間距離d

接收方接收l比特的信息,需要接收能量開銷為：

ERx(l)=lEelec(4)

2 ECR算法

2.1 簇首選舉的改進

由于LEACH算法沒有考慮到節點剩余能量的影響，并且隨機選取簇首使得其分布不均勻。考慮修改式(2)和每個節點相應的隨機數(rand)，使得能量和最小鄰近簇半徑對于簇首選舉的概率都有所影響，則對于每個節點i有一個新的閾值：

T(i)=p1-pmod(r,1/p)flag,i∈G

0,其他(5)

其中：

flag=exp(R(i)/Rd)-1)， R(i)≠0

1，其他(6)

由式(5)和式(6)知，R(i)越小，則T(i)越小，即當前節點距離某個簇首的距離小于一個閾值Rd，則其成為簇首的可能性就降低。

根據剩余能量的大小，對于rand的修改式如下：

rand(i)=rand(i)exp(7)

其中：rand(i)為對于節點i所產生的隨機數；E(i)為節點i的剩余能量；E0為節點的初始能量。由式(7)知，節點剩余能量越大，rand(i)越小，則其值小于閾值T(i)的可能性越大，所以剩余能量越大的節點當選簇首的概率也就越大。

2.2 簇內結構的改進和ECR算法

由于在LEACH算法中，簇內節點與簇首單跳通信。此時，有部分節點與簇首距離大于式(3)中的do值，考慮讓這部分節點采取多跳通信，讓其與簇內最近成員節點通信，則可降低網絡能量消耗，減輕簇首負擔，均衡節點能量消耗。

由于概率的影響，某輪可能沒有節點充當簇首，故設定簇首總數為num，使得每輪中的簇首數目大于num值。設節點數為n，下面給出ECR算法：

Step1:r=1:rmax(rmax為最大輪數值);

Step2:對于node(i)∈G,根據式(5)算出T(i)，node(i)麲，則T(i)=0;

Step3:對于node(i)，按式(7)產生一個0~1之間的隨機數rand(i);

Step4:比較rand(i)與T(i)，若rand(i)

Step5:若i>n且num≥4，則本輪簇首選舉完成，進入穩定工作階段；此時節點發送信息時的能量消耗按式(3)計算；節點接收信息時的能量消耗按式(4)計算；節點與簇首通信，簇首與基站通信；轉Step7。

Step6:若i>n且num<4，則按rand(i)的取值由大到小選取對應的節點為簇首，直到num=4，本輪簇首選舉完成，進入穩定工作階段；轉Step7。

Step7:若r

3 仿真實驗

3.1 參數設定

由Matlab 7.1進行仿真實驗，在區域為100 m的正方形范圍內，對100個節點進行仿真。其他參數設置如下：

基站坐標：(50 m,50 m)；p=0.05；Eo=0.5 J；

Eelec=50 nJ/b；εfs=10 pJ/b/m2；

εmp=0.001 3 pJ/b/m4；l=4 000 b;do=45 m;

Rd=xm2=1002；由ECR算法有如下仿真結果，如圖1，圖2所示。

圖1 ECR算法的一個實例圖

3.2 仿真結果分析

由圖1、圖2可看出簇首分布較均勻。當所分簇數目較少時，由于簇首能耗負擔過大，則簇內部分節點采取了多跳通信，即圖2所示。

由表1知ECR算法有效延長了網絡生命期，降低了網絡的能量消耗。

圖2 ECR算法改變簇內結構的一個實例圖

表1 不同的初始能量對應的生命期

Eo算法生命期 /輪

0.5J

LEACH783

ECR828

1.0J

LEACH1529

ECR1801

4 結 語

按照針對LEACH算法的不足，提出了ECR算法，結合節點剩余能量和最小鄰近簇半徑調節節點選擇簇首的概率，通過對能量模型的分析，對簇內部分節點采取多跳通信。仿真結果表明，ECR算法有效地提高了網絡生命期，均衡了網絡中節點的能量消耗，促進了簇首分布均勻化。

參考文獻

［1］Cui L,Ju H L,Miao Y,et al.Overview of Wireless Sensor Networks［J］.Journal of Computer Research and Development,2005,42(1):163-174.

［2］孫利民.無線傳感器網絡［M］.北京:清華大學出版社,2005.

［3］Narayanaswamy S,Kawadia V,Sreenivas R S,et al.Power Control in Ad-Hoc Networks:Theory,Architecture,Algorithm and Implementation of the COMPOW Protocol.In:Proc.of the European Wireless Conf..Florence,2002:156-162.

［4］Kubisch M,Karl H,Wolisz A,et al.Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks.Proc.of the IEEE Wireless Communications and Networking Conf..New York:IEEE Press,2003:16-20.

［5］Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocol for Wireless Wensor Networks［A］.Proceedings of the Hawaii International Conference on System Sciences.Piscataway.IEEE,2000.

［6］Younis O,Fahmy S.HEED:A Hybrid,Energy-efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks［J］.IEEE Trans.on Mobil Computing,2004,3(4):366-379.

［7］Handym J,Haasem,Timmerma-NN D.Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-head Selection［A］.Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks.Stockholm:IEEE Communications Society,2002:368-372.

［8］張怡,李云,劉占軍,等.無線傳感器網絡中基于能量的簇首選擇改進算法.重慶郵電大學學報,2007,19(5):613-616.

［9］Heinzelman W,Chandrakasan A,HBalakrishnan.An Application Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans.on Wireless Communications,2002,1(4):660-670.

作者簡介

張作鋒 男，1982年出生，黑龍江人，碩士研究生。主要研究領域為無線傳感器網絡。

劉三陽 男，1959年出生，陜西西安人，教授，博士生導師。主要研究方向為最優化計算方法，網絡優化，無線傳感器網絡等。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。