張作鋒　劉三陽

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

關(guān)鍵詞：簇首；網(wǎng)絡(luò)生命期；成簇算法；剩余能量

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：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 引 言

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

人們基于節(jié)能的考慮，提出了各種各樣的拓?fù)淇刂扑惴?。根?jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)劃分為平面算法和分簇算法［2］。平面拓?fù)淇刂扑惴ㄖ校鞴?jié)點地位相同，通過功率控制簡化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而減少沖突、干擾，達(dá)到節(jié)能的目的。典型算法有COMPOW［3］，LMA和LMN［4］等。分簇算法是無線傳感器網(wǎng)絡(luò)節(jié)省能量，延長網(wǎng)絡(luò)生命期的有效方法。節(jié)點分簇的主要思想是根據(jù)某種規(guī)則選擇出一些節(jié)點成為簇首，在剩余節(jié)點中繼續(xù)按某種規(guī)則選擇節(jié)點加入簇首，形成簇。

典型的分布式簇首選取算法有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算法中，所有節(jié)點輪流充當(dāng)簇首，網(wǎng)絡(luò)周期性地進行簇首選舉，每個周期稱為一輪(round)。在每輪中，各節(jié)點獨立運行公式產(chǎn)生一個數(shù)，再生成一個隨機數(shù)，通過兩個數(shù)的比較來判斷節(jié)點是否當(dāng)選簇首。在每輪中，所有簇首選舉后，進入穩(wěn)定工作階段。HEED算法中，簇首的選擇主要依據(jù)主、次兩個參數(shù)。主參數(shù)依賴于節(jié)點剩余能量，用于隨機選取初始簇首集合，具有較多剩余能量的節(jié)點將有較大的概率暫時成為簇首，而最終該節(jié)點是否成為簇首取決于剩余能量是否比周圍節(jié)點多得多；次參數(shù)依賴于簇內(nèi)通信開銷。DCHS算法針對LEACH算法中的不足，綜合考慮節(jié)點當(dāng)前能量和閾值對簇首選取的影響。

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

1 基本概念及相關(guān)知識

1.1 傳感器網(wǎng)絡(luò)生命期

根據(jù)服務(wù)類型的不同，傳感器網(wǎng)絡(luò)生命期的定義也不相同。這里定義從節(jié)點部署開始到第一個節(jié)點死亡為止。

1.2 最小鄰近簇半徑

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

用公式表示為:

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

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

1.3 LEACH算法

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

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

0,其他(2)

其中：p為簇首節(jié)點占網(wǎng)絡(luò)節(jié)點總數(shù)的百分比；r為當(dāng)前輪數(shù)；G表示網(wǎng)絡(luò)中最近1/p輪未當(dāng)選簇首的節(jié)點的集合。

LEACH算法如下：

設(shè)有n個節(jié)點：

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

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

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

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

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

Step6:若r

1.4 能量消耗模型

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

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

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

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

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

ERx(l)=lEelec(4)

2 ECR算法

2.1 簇首選舉的改進

由于LEACH算法沒有考慮到節(jié)點剩余能量的影響，并且隨機選取簇首使得其分布不均勻?？紤]修改式(2)和每個節(jié)點相應(yīng)的隨機數(shù)(rand)，使得能量和最小鄰近簇半徑對于簇首選舉的概率都有所影響，則對于每個節(jié)點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)越小，即當(dāng)前節(jié)點距離某個簇首的距離小于一個閾值Rd，則其成為簇首的可能性就降低。

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

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

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

2.2 簇內(nèi)結(jié)構(gòu)的改進和ECR算法

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

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

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

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

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

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

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

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

Step7:若r

3 仿真實驗

3.1 參數(shù)設(shè)定

由Matlab 7.1進行仿真實驗，在區(qū)域為100 m的正方形范圍內(nèi)，對100個節(jié)點進行仿真。其他參數(shù)設(shè)置如下：

基站坐標(biāo)：(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算法有如下仿真結(jié)果，如圖1，圖2所示。

圖1 ECR算法的一個實例圖

3.2 仿真結(jié)果分析

由圖1、圖2可看出簇首分布較均勻。當(dāng)所分簇數(shù)目較少時，由于簇首能耗負(fù)擔(dān)過大，則簇內(nèi)部分節(jié)點采取了多跳通信，即圖2所示。

由表1知ECR算法有效延長了網(wǎng)絡(luò)生命期，降低了網(wǎng)絡(luò)的能量消耗。

圖2 ECR算法改變簇內(nèi)結(jié)構(gòu)的一個實例圖

表1 不同的初始能量對應(yīng)的生命期

Eo算法生命期 /輪

0.5J

LEACH783

ECR828

1.0J

LEACH1529

ECR1801

4 結(jié) 語

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

參考文獻(xiàn)

［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］孫利民.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社,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］張怡,李云,劉占軍,等.無線傳感器網(wǎng)絡(luò)中基于能量的簇首選擇改進算法.重慶郵電大學(xué)學(xué)報,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年出生，黑龍江人，碩士研究生。主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)。

劉三陽 男，1959年出生，陜西西安人，教授，博士生導(dǎo)師。主要研究方向為最優(yōu)化計算方法，網(wǎng)絡(luò)優(yōu)化，無線傳感器網(wǎng)絡(luò)等。

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