版权信息
省级大型综合性科技类期刊
主管部门:自治区科技厅
主办单位:自治区科学技术信息研究院 
协办单位:自治区科学技术情报学会
编辑出版:科技期刊编译室
刊社地址:呼和浩特新城西街149号本刊杂志社
邮政编码:010000
电      话:0471-2536371

E-mail  :

nmgkjzz@vip.163.com 

网站地址:www.nmgkjzz.com


往期杂志
当前位置: 首页>往期杂志>详细介绍

一种带有孤立节点的DEEC改进算法

时间:2016-11-28来源: 作者: 点击: 202次

朱丽华  姜真

(池州职业技术学院,安徽 池州 247100

 

摘要:针对无线传感器网络能量受限的问题,在DEEC算法的基础上,提出了一种带有孤立节点的分簇算法。以DEEC算法确定簇头后,改进节点加入簇的机制,分别计算节点到区域内各个簇头以及到sink节点的通信距离,通过最短距离原则使某些节点成为孤立节点,以最小功率直接和sink节点通信,从而降低节点的能耗,延长网络的生存时间。仿真实验结果表明,与LEACH和DEEC分簇算法相比,网络生存时间延长了约30%,在数据传输效率、负载均衡度、网络能耗等方面具有更好的性能。

关键词:无线传感器网络;分簇算法;孤立节点;DEEC;网络生存时间

中图分类号:TP301.6     文献标识码:A    文章编号:

 

An Improved DEEC Algorithm With Isolated Nodes

ZHU Li-hua

Chi Zhou vocational & technical college, chizhou, 247100 ,China

 

Abstract: Aim at the characteristic of energy heterogeneous for wireless sensor network, a clustering algorithm with isolated nodes based on the DEEC algorithm is proposed. The mechanism of nodes joined in cluster is improved. The cluster heads are selected with the DEEC algorithm firstly, then the distances of nodes to clusters and sink are calculated. Some of the nodes become isolated nodes based on the shortest distance principle, they communicate with sink directly with the minimum power. So the energy consumption is reduced, the network lifetime is prolonged. Simulation results show that the network lifetime is prolonged about 30%, compared with LEACH and DEEC algorithms. There is a better network performance than the LEACH and DEEC algorithms in data transmission efficiency, energy consumption, load balancing degree, etc.

Keywords: wireless sensor network; clustering algorithm; isolated nodes; DEEC; network lifetime

 



0 引言

无线传感器网络(Wireless Sensor Network,WSN)是由一组传感器节点自组织形成的一个无线网络。传感器节点能量受限,而且能量难以补充,决定了传感器网络的生存时间是有限的。实验表明,传输一个比特所消耗的能量比运算处理一个比特消耗的能量大[1],为了延长网络的生存时间,除了设计低功耗的传感器节点外,还需要设计能量有效的网络通信协议。

基于分簇的路由协议是将网络划分为不同的簇(cluster)。在簇内选举出一个簇头(cluster head),簇内节点直接和簇头通信,而簇头之间采用单跳或者多跳技术与sink节点通信,减少通信量,有利于减少节点参与路由计算的数量,降低整个网络的能量开销,延长网络的生存时间,适合大规模网络[2]

分布式能量有效成簇算法DEEC(Distributed Energy-Efficient Clustering Algorithm)是一种典型的基于分簇的路由算法。其基本思想是通过所有节点轮流成为簇头,以达到节点均匀消耗能量、延长网络生存时间的目的。而选举簇头节点的概率与节点当前剩余的能量直接相关,每个节点成为簇头节点的轮数根据其初始能量和剩余能量的差别而不相同,即簇头轮转周期适应节点的能量变化,具有较高初始能量和剩余能量的节点比低能量节点有更多的机会成为簇头节点[3,4]

本文在DEEC算法的基础上,提出了一种带有孤立节点的改进算法,称之为DEEC-WIN(DEEC Algorithm With Isolated Nodes)算法。仿真实验结果表明,DEEC-WIN算法与LEACH和DEEC分簇算法相比,网络生存时间提高了30%在数据传输效率、负载均衡度、网络能耗等方面具有更好的性能。

1 典型分簇算法

在分簇算法中,簇内节点将采集到的信息传输给相应的簇头,由簇头对收集到的信息进行数据的融合处理,将处理好的数据发送给基站。比较典型的是W.Heinzelma 等人提出的一种低功耗自适应分簇算法LEACH[2],该算法是让网络中的节点自组织地形成簇,簇头是随机产生的。它在节约能耗方面,比传统平面路由协议提高了近8倍,但是由于簇头选举的随机性使得网络的簇头需要负担的节点数不同,加重了个别簇头节点的负担,使得网络的负载平衡程度下降,在簇头选举策略中没有考虑到所有节点的剩余能量问题,也不能优化簇内结构,从而影响整个网络的能耗。于是,提出了改进算法LEACH-C[5],该算法由sink节点作出簇头选择决定,健壮性较好,解决了LEACH算法中“节点根据随机数决定是否当选为簇头” 以及“每轮产生的簇头没有确定的数量和位置”等方面的问题,大大提高了簇的生成质量。但由于每个节点都须向基站周期性地报告它们的能量和位置等信息,成簇开销较大,网络流量、时间延迟以及信号干扰的概率都会增加。文献[6]给出了一个LEACH的改进算法LEACH-M,在建立网络初期,要求每个节点告知基站,自己的地理位置和状态,这在一定程度上增加了整个网络的能量消耗,虽然在网络生存期和数据传输量都优于原来的LEACH算法,但是引入了额外的能量开销,不利于网络的能量优化。文献[7]HEED算法是完全分布式的成簇算法,它随机选择簇头节点,选举概率与该节点的剩余能量直接相关,通过降低低能量节点成为簇头的概率来保证网络内能量负载的平均分布,从而进一步延长网络生存时间。但HEED在选择簇头时,节点需要在一定的迭代次数内与周围邻居节点不断地进行信息交互,因此算法的实现需要额外的通信代价,不适合大型无线传感器网络。

DEEC算法是由卿利等人提出的分簇路由算法,该算法基于节点剩余能量与网络节点的平均能量的比例来选举簇头节点,适用于异构无线传感器网络[3,4]本文从降低网络能耗,优化网络结构对DEEC算法进行改进,以期进一步降低网络能耗,延长网络生存时间。

2 DEEC-WIN算法

2.1 基本思想

DEEC-WIN算法保留了DEEC算法中的簇头选举机制,但是对节点加入簇的机制进行了优化。首先,据DEEC算法确立簇头;然后,计算普通节点与sink节点的距离,以及与所有簇头的距离。如果普通节点与sink节点的距离,比普通节点与任一簇头的距离都短,则该节点不加入任何簇而成为孤立节点。孤立节点以最短路径直接和sink节点通信,从而使节点在保证通信的同时把能量消耗降到最低,达到延长网络生存时间的目的。

2.2 无线通信模型

LEACHDEEC等算法一样,DEEC-WIN算法采用的无线通信模型如图1所示[2-5]

 

节点发射k比特的数据到距离为d接收端,消耗的能量发射电路和功率放大器的能耗两部分组成 [3-5]

  1

其中,Eelec表示节点电路发送和接收每比特数据的耗能;为距离阈值,当收发节点间的距离小于时,采用自由空间信道模型,当收发节点间的距离大于等于时,采用多径衰落信道模型;表示放大器在自由空间信道模型下的能耗;表示放大器在多径衰落信道模型下的能耗。

2.3 网络模型

假设传感器网络有N个普通节点和1sink节点,传感器节点随机均匀分布在M´M的正方形区域内,sink节点位于区域正中,同时,有如下假设:

1)传感器网络使用相同的能量受限的节点,且每个节点均可以与sink节点直接通信。

2)传感器网络为能量异构网络,即每个节点的初始能量不同,但都具备数据融合功能。

3)节点部署后网络无需人为维护,进行自组织管理,且假定节点是微移动或者静止不动的。

4)节点可以自适应调节发射功率,即根据接收方的距离,调节到恰好满足通信距离要求的发射功率。

2.4 算法实现

DEEC-WIN算法在运行中不断进行簇的重构过程,每个簇重构过程用“轮”来描述[2-5],每一轮分为簇头选择、簇生成和数据通信三个阶段。选定簇头之后,剩余节点根据距离判决机制,来决定是否加入该簇。若在一轮周期内,该区域内至少存在一个簇头到节点的距离小于节点到sink节点的距离,则节点加入距离簇头最近的簇;若该区域内没有一个簇头到节点的距离小于节点到sink节点的距离,则节点不加入任何一个簇,成为孤立节点,直接和sink节点进行通信,以降低自身能量消耗。最后,sink节点收到的信息包含两部分:各簇头融合本簇内各节点数据和孤立节点的信息。

算法可分为以下4个阶段进行:

1)节点分布阶段。在M´M的区域内,随机分布N个节点,节点Si存储自身的坐标信息(Si.xSi.y)。在(M/2M/2)坐标位置布置sink节点。

2)簇头选举阶段。在DEEC算法中,区域内节点根据自身的剩余能量,由簇头判决门限来选举簇头,簇头的判决门限[3,4]

2

其中,r为当前的轮数,G为在最近(r mod (1/Pi))轮中没有成为簇头的节点集合,从而每个节点都有机会轮流成为消耗能量较多的簇头节点。Pi 表示节点Si在第r轮当选簇头的概率

 3

其中,Popt表示簇头优化比例,当Pi=Popt 时,网络达到最优化状态。表示网络在第r轮的平均能量,Ei(r)表示节点Si在第r轮的剩余能量。

式(3表示当节点的剩余能量比平均能量大时该节点的平均选举概率Pi将比Popt增加相应比例的值当节点的剩余能量比平均能量要小时节点的平均选举概率Pi将比Popt减少相应比例的值

3)节点选择簇头阶段。先计算出节点Sisink节点的通信距离ds,再分别计算出节点Si与区域内各个簇头的距离dhi。其中,节点Si与簇头的最短距离为h为簇头数)。若ds<dhmin,则节点Si就为孤立节点;若ds>dhmin,则节点根据最短路径原则加入该簇。

4)数据通信阶段。在网络的一轮周期内,假设孤立节点有n个,到sink节点的距离为dsi(i=1,2,…,n),成员节点向簇头节点发送k比特的信息,孤立节点也向sink节点也发送k比特的信息,于是网络在一轮中消耗的能量为N-n个簇内节点分别与h个簇头通信能耗、h个簇头与sink通信能耗和n个孤立节点直接与sink通信能耗,具体计算公式如下:

4

其中EDA为簇头进行数据融合的能耗,dtoBS为簇头到sink节点的平均距离dtoCH为簇内成员节点到簇头的平均距离假设节点均匀分布可以得到[5,8]

          5

         6

对于DEEC算法,网络一轮消耗的能量总和为[3,4]

   7

因为di(i=1,2,…,n)<dtoBS,所以,从式(4)和式(7)可看出:所以采用DEEC- WIN算法在网络的每轮运行中,都可以降低网络的能量消耗,从而延长网络生存时间。

3 仿真实验结果与分析

3.1 评价指标

根据算法对于网络运行性能的影响与影响程度,主要选择以下4个方面的评价指标:

1网络生存时间。在排除网络受外界干扰的情况下,当节点的能量为0时,就认定该节点死亡。从网络运行到第一个节点死亡的时间间隔,为网络第一生存时间,以及从第一个节点死亡到10%节点死亡的时间间隔为第二生存时间,最后到节点全部死亡,为整个网络的生存时间。

2数据传输量。sink节点收到的数据量,收到的数据量越大则说明节点转发数据的路径越高效

3)负载均衡度每轮中簇覆盖节点的平均程度也会影响网络的生存时间,只有将网络负载平均分布到每一个节点,避免少数节点过早的死亡,才能提高网络性能。负载均衡度以负载平衡因子LBFLoad Balance Factor)表征

        8

其中,h为簇头数,Xi是第i个簇头的簇内节点数,m=(N-h)/h 表示每个簇头的平均簇内节点数。显然,LBF越大,负载均衡度越好。理想情况下,LBF为无穷大。

4网络能量消耗。在网络生存期内,网络中所有的节点的能耗总和。

3.2 仿真环境

为了便于将DEEC-WIN算法与DEECLEACH算法进行性能比较和分析,本文设置上述三种分簇算法的仿真条件一致。假设网络节点数为N=100,随机分布在100m´100m的区域内,sink节点位于区域的中心坐标为(50, 50)。传感器网络为能量异构网络,各节点初始能量为随机值E0(1+rand),其中,E0为节点初始能量的最小值,rand(0,1)之间的随机数。

本文以MATLAB 7.6作为仿真工具,节点网络参数设置见表1

1 仿真实验参数设置

Table 1  Parameters used in simulations 

参数

数值

参数

数值

E0

0.5J

EDA

5nJ/bit

Eopt

0.1

efs

10pJ/bit/m2

Eelec

50nJ/bit

emp

0.0013pJ/bit/m4

k

4000bits

N

100

3.3 结果与分析

   1)网络生存时间比较。图2LEACH、DEEC和DEEC-WIN三种算法的生存时间实验结果对比,可以看出,DEEC-WIN算法的节点死亡速率明显比DEEC低,其网络生存时间比DEECLEACH算法大约多750轮,延长了约30%

 

     2 网络生存时间对比

   Fig.2 Network lifetime comparison chart

2数据传输量比较。3是三种算法sink节点接收的数据量比较,可以看出在网络生存期内,sink节点接收到的数据随时间的变化而增加,采DEEC-WIN算法sink接收到的数据量远远大于采用DEECLEACH算法sink节点接收到的数据量

3)负载均衡度比较。4是三种算法负载均衡度实验结果对比,为避免LBF为无穷大时作图困难,图中以LBF-1作为纵坐标。可以看出,DEEC-WIN算法在网络的有效生存期内的曲线比DEECLEACH算法数值小且曲线变化幅度小,说明DEEC-WIN算法在负载均衡度上比DEEC有了明显的改善。

 

3 数据传输对比

Fig.3 Data transmission comparison chart

 

4 负载均衡度对比

Fig.4 Load balancing degree comparison chart

 

5 网络能耗对比

Fig.5 Network energy consumption comparison chart

4网络能量消耗比较。5是三种算法网络能量消耗的实验结果对比,可以看出,采用DEEC -WIN算法,网络的能量消耗速度要慢于采用LEACHDEEC算法的能量消耗。

4 结束语

   本文基于最低能耗原则,在DEEC分簇算法的基础上,提出了带孤立节点的改进算法DEEC–WIN,在分簇过程中,通过改进加入簇的机制,使孤立节点直接与sink节点进行通信。仿真实验结果表明,DEEC-WIN算法在网络生存时间数据传输量、负载均衡度、网络能量消耗等方面的性能优于DEEC算法和LEACH算法。

参考文献

[1] Pottie G J, Kaiser W J. Wireless integrated network sensors[J]. Communications of the ACM2000, 43(5): 51-58.

[2] Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-Efficient Communica -tion Protocol for Wireless Microsensor Networks[C]. 33rd Hawaii International Conference on System Sciences. Maui, 4-7 January 2000, Volume 8, pp. 8020

[3] Li Qing, Qingxin Zhu, Mingwen Wang. Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J]. Computer Communications, 2006, 29: 2230-2237

[4] 卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效成簇算法[J]. 软件学报, 2006, 17(3): 491-489

[5] Wendi B. Heinzelman, Anantha P. Chandrakasan, Hari Balakrishnan. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4) :660-670.

[6] 余静涛,胡同森,钟明霞.无线传感器网络路由协议LEACH的研究与改进[J].计算机系统应用,20092

[7] David Braginsky, Deborah Estrin. Rumor Routing Algorithm for Sensor Networks[C]. Proc. of the 1st Workshop on Sensor Networks and Applications. Atlanta, Georgia, USA. 2002:22-31.

[8]  Mhatre V, Rosenberg C. Design guidelines for wireless    sensor networks: communication, clustering and aggregation. Ad Hoc Network Journal, 2004,2(1):45−63.

                                                      

 

作者简介:

朱丽华1985-),安徽池州人,池州职业技术学院教师,主要研究方向为传感器技术及应用。

姜真(1988-),男,安徽池州人,池州职业技术学院教师,主要研究方向为自动化生产线安装与调试。

 

 

本刊创刊于1982年,是由自治区科技厅主管、自治区科技信息研究院主办,由自治区科技情报学会协办、国内外公开发行的省级综合性科技刊物,是反映内蒙古自治区科技与经济发展的窗口。杂志入选《中国期刊全文数据(CJFD)》全文收录期刊和《中国学术期刊综合评价数据(CAJCED)统计刊源期刊,《中国核心期刊(遴选)数据库》收录。本刊是公开发行的综合性科技期刊,为月刊,大16开本。本刊坚持以科技创新为目标,融科技、经济、信息、产业、市场为一体,是促进科技成果转化、推动科技进步、加强技术创新,促进经济发展的专业性期刊。