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

張作鋒　劉三陽

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

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

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：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é)點(diǎn)組成，它通過無線通信的方式形成一個(gè)網(wǎng)絡(luò)系統(tǒng)，在軍事國防、災(zāi)難預(yù)警、環(huán)境控制、信息通信等各個(gè)領(lǐng)域都有著十分廣泛的應(yīng)用［1］。傳感器節(jié)點(diǎn)體積小，能量有限，處理能力低，如何充分利用有限的能量，提高網(wǎng)絡(luò)生命期是傳感器網(wǎng)絡(luò)面臨的首要任務(wù)。

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

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

針對LEACH算法的不足和文獻(xiàn)只考慮剩余能量的不足，提出了基于剩余能量和最小鄰近簇半徑的成簇算法(Based on Residual Energy and Least Adjacent Clustering Radius,ECR)，并對簇內(nèi)結(jié)構(gòu)合理化。通過對LEACH算法的修改，使得最小鄰近簇半徑小的節(jié)點(diǎn)當(dāng)選簇首的概率降低；剩余能量大的節(jié)點(diǎn)當(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)知識(shí)

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

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

1.2 最小鄰近簇半徑

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

用公式表示為:

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

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

1.3 LEACH算法

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

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

0,其他(2)

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

LEACH算法如下：

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

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

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

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

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

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

Step6:若r

1.4 能量消耗模型

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

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

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

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

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

ERx(l)=lEelec(4)

2 ECR算法

2.1 簇首選舉的改進(jìn)

由于LEACH算法沒有考慮到節(jié)點(diǎn)剩余能量的影響，并且隨機(jī)選取簇首使得其分布不均勻?？紤]修改式(2)和每個(gè)節(jié)點(diǎn)相應(yīng)的隨機(jī)數(shù)(rand)，使得能量和最小鄰近簇半徑對于簇首選舉的概率都有所影響，則對于每個(gè)節(jié)點(diǎn)i有一個(gè)新的閾值：

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é)點(diǎn)距離某個(gè)簇首的距離小于一個(gè)閾值Rd，則其成為簇首的可能性就降低。

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

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

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

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

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

由于概率的影響，某輪可能沒有節(jié)點(diǎn)充當(dāng)簇首，故設(shè)定簇首總數(shù)為num，使得每輪中的簇首數(shù)目大于num值。設(shè)節(jié)點(diǎn)數(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)生一個(gè)0~1之間的隨機(jī)數(shù)rand(i);

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

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

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

Step7:若r

3 仿真實(shí)驗(yàn)

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

由Matlab 7.1進(jìn)行仿真實(shí)驗(yàn)，在區(qū)域?yàn)?00 m的正方形范圍內(nèi)，對100個(gè)節(jié)點(diǎn)進(jìn)行仿真。其他參數(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算法的一個(gè)實(shí)例圖

3.2 仿真結(jié)果分析

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

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

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

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

Eo算法生命期 /輪

0.5J

LEACH783

ECR828

1.0J

LEACH1529

ECR1801

4 結(jié) 語

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

參考文獻(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ò)中基于能量的簇首選擇改進(jìn)算法.重慶郵電大學(xué)學(xué)報(bào),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)域?yàn)闊o線傳感器網(wǎng)絡(luò)。

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

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