基于能量效率的非均匀分簇无线传感器路由算法

李建奇, 曹斌芳, 王 立, 王文虎



基于能量效率的非均匀分簇无线传感器路由算法

李建奇1, 曹斌芳2, 王 立1, 王文虎1

(1. 湖南文理学院 电气与信息工程学院,湖南 常德, 415000; 2. 湖南文理学院 物理与电子科学学院,湖南 常德, 415000)

自然环境中的监控节点分布具有天然的不均匀性, 如南方有大量水塘的区域, 典型的层次路由协议普遍存在节点分簇中的“热区”情况. 针对这种监控对象特点, 为了提高能量效率确保区域覆盖的有效性和时效性, 本文提出了一种改进的非均匀分簇无线传感器网络路由算法. 改进算法首先结合节点分布密度优化簇头选举, 再对簇的竞争半径进行控制实现非均匀分簇, 然后由各簇头计算距离系数和离散系数来确定各簇内部通信方式, 最后在簇头之间采用单跳和多跳结合的传输机制. 模拟实验结果表明, 改进算法能较好地提高网络的能量效率, 能显著地延长网络整体的生存时间.

无线传感器网络; 非均匀分簇; 离散系数; 能量效率

由于无线传感器网络(WSN, Wireless Sensor Network)广泛的应用, 其相关的理论和技术研究一直非常活跃. 一些重要的基本问题包括能量的优化、传感器部署和数据融合等是当前的研究热点. 在一些研究中, 最重要的问题是提高受限的节点能源使用(传感器节点一般通过电池供电)[1-6]. 网络分级层次结构被应用来提高节点能量消耗效率, 从而实现网络的可扩展性[4-9]. 在分级结构中, 传感器网络节点被按簇的方式组织, 每个簇由簇头节点和成员节点组成, 层次结构可以逐层递推. 通过追求网络簇头和成员节点的负载均衡化可以实现最大化网络整体生存时间. 簇头可以通过静态事先指定, 但是更一般情况是通过算法动态确定[2].

经典同构网络分簇协议(如LEACH、HEED等)一般通过周期性的选举来完成簇头更新. 在每轮传输中, 簇头耗费的能量包括簇内部处理和发送信息. 已有研究表明在簇头与基站通信时采取多跳的方式更有助于提高能耗效率(能耗效率指网络传输单位数据量所消耗的能量), 但是这种机制使得距离网关的较近簇头不仅需要将本簇中的数据传输给网关, 而且还需要融合转发较远簇头的发送过来的数据, 以实现多跳传输, 这就是“热区”问题[8-12]. Soro等人首先对这个问题进行了研究, 并提出了非均匀的分簇模型UCS[3]. 研究人员提出一系列相关的改进非均匀分簇算法[4-12], 其基本思路是依据节点距基站的远近构造大小不等的簇, 离基站越近各簇组成成员越少, 以节约簇内能量开销供转发使用. 这样分簇模式使得近距离簇头可以减少簇内信息处理所带来的能量开销, 为簇间信息的融合转发提供能量保障, 从而使得网络节点整体负载大致均衡, 能量消耗速率相对均匀, 避免热点问题的发生. 但是如何合理的进行簇的半径参数选取和在特定条件下有效分簇以及适当的簇间通信依然是难题.

本文在典型的非均匀分簇路由协议基础上, 针对现实环境下监控区域中存在某区域由于自然或者其他原因出现不存在传感器节点的情况(如在南方农村地区中广泛存在大小水塘), 并定义这种节点空白区域为空洞区域. 如图1所示, 监控区域在现实监控中具有一定的代表性. 由于WSN一般部署在环境恶劣的区域, 因此假定基站位置远离监控区域是合理的. 从图1中可以很容易观察到和区域都是聚集是比较集中的, 而区是在节点分布呈环形. 本文所提出算法正是针对此种情况设计了优化的非均匀分簇的路由协议. 本文主要思路是在采用优化的竞争算法来控制簇的半径, 再根据距离和节点能量构建非均匀簇, 通过估计各簇内的节点形态分布以确定簇内通信模式, 可采用单跳或者基于改进PEGASIS协议的链式传输方式. 最后根据簇头与网关之间距离选择单跳或者多跳方式来实现信息的传输.

图1 网络节点位置分布示意图

1 监控网络对象模型

本文监控网络假定网络中有个传感器节点, 节点随机的分布一个×区域内, 该区域中存在不存在节点的空洞区域. 其基本模型图如图2所示. 网络对象满足以下假设: 节点为静态布设, 布设后不再进行人工维护; 所有节点具有相同结构与功能, 初始能量相同. 所有节点具备与网关直接通信能力, 且能自主调整发射功率; 各监测节点单位片段中需要发送数据; 网关位置固定且位于传感器监测区域以外, 其具有无限能量; 各节点均有足够的计算能力完成相应的MAC协议和数据处理融合; 各节点采用全向天线, 节点间为对称通信链路.

图2 传感器网络非均匀分簇模型

本文中所假定的网络节点能耗能量模型采用文献[3], 如式(1)-(3)所示. 式(1)中,为传输距离,TX(,)代表传感器节点间距离为时bit 数据传输的能耗, 包括发射电路能耗和功率放大能耗. 功率放大能耗根据发送节点和接收节点之间距离的远近采用自由空间模型或者多路径衰减模型.elec为发射电路的能耗,fs和mp代表两种信道模型下不同功率放大能量系数. 式(2)表示接收bit数据的所需能量, 主要为电路耗损. 式(3)为处理个节点发送过来的×bit数据以及与自身数据融合所耗费能量.

数据发送:

2 改进的路由协议

本文针对真实环境下节点分布不均匀的特点, 结合非均匀分簇算法理论, 提出了一种改进的基于节点形态分布的高能量效率非均匀分簇算法. 该算法首先通过控制簇竞争半径, 优化非均匀分簇结构, 然后计算各簇中节点密度来优化簇的产生, 再根据簇内节点分布形态采用不同的簇内通信方式, 该算法能有效优化能耗. 改进协议以轮作为数据传输的单位, 每轮包括4个阶段, 分别为非均匀簇头的产生、簇内部传输拓扑的形成、簇头间路由的优化和数据传输阶段.

2.1 基于竞争半径的非均匀簇头选举

研究表明传感器网络中应用典型非均匀分簇协议后, 各簇头的负担较重, 它不仅需要对簇进行管理, 而且需要协调簇内成员的数据传输和融合成员数据, 还可能需要转发其他簇头数据[12-13]. 改进算法采用分布式的竞争算法, 以节点的剩余能量、网关距离和节点密度为主要依据. 每轮由网关用恒定功率的向全网广播本轮分簇的信号, 启动分簇选举. 广播信息中包含网络节点平均能量av. 定义节点剩余能量低于av为低能量节点, 所有低能量节点不参与簇头选举, 反之则定义为优势节点. 每个优势节点在接收到分簇命令后, 根据网关信号的强度估算自身距网关近似距离dg. 通过分布式的方法来调整簇头的竞争半径, 从而获得非均匀的分簇结构, 其竞争半径R的计算公式为:

其中max与min表示网络中节点到网关的最大距离与最小距离,ig表示节点到网关的距离,为预设参数,comp为节点的最大竞争半径. 每个优势节点向自己的竞争半径内广播存在信号.

在各竞争半径内的所有优势节点产生一个在0~1之间的随机数, 当节点随机数小于阈值(), 该节点将入选为临时簇头节点, 反之该节点成为本轮普通节点, 簇头选举阈值()由式(5)决定[9]:

其中E表示节点的剩余能量,Eav表示为网络节点的平均能量, 本算法中由本轮竞争范围内节点的平均能量近似. CH_Times表示该节点已当选簇头的次数. 各簇头选举完成后, 各自广播当选簇头的信号(advertisement message, ADV), 其半径内的节点收到信息后, 停止竞争, 发送加入信息, 该加入信息包括簇头节点ID和本节点ID外, 还包括剩余能量数、距离簇头的距离和距离网关的距离[7]. 当竞争半径内出现多个侯选簇头节点时候, 处于较高密度节点区域当选簇头获胜, 簇头附近节点密度分布通过加入节点信号强度和多少近似估计. 低密度节点区域的节点应该保存能量, 因为没有替代节点, 一旦死亡意味着覆盖范围的缩小.

2.2 簇内路由的建立

各簇中的普通节点将其距网关距离的告知簇头, 同时簇头计算本节点的距离系数,=dg/max,max为网络标准距离(网络最大距离),dg为第个簇头距离网关的距离. 当值小于或等于0.6时, 即该簇头被定义为近距离簇头节点, 其竞争半径较小, 其内部包含的节点数目较少, 内部节点采用单跳与簇头直接通信. 当系数大于0.6, 该簇头被定义为远簇头节点, 其远离网关. 对于远簇头节点将通过式(6)计算簇的离散系数, 离散系数用来描述簇内成员节点的分布形态. 式(6)中ic为第个簇中内部节点至该簇簇头的距离,dav为第个簇内各节点与簇头的平均距离. 通过对各簇内节点距离簇头与簇内所有节点距离簇头平均值的比例求和, 再除以簇内节点数. 通过离散系数远簇被分成紧密簇和离散簇.

当该超过指定阈值后, 簇内继续采用单跳直接通信, 将会加大能耗的开销, 当离散系数小于0.65时, 则认为该远离簇内部存在空洞区域, 该簇将使用PEGASIS协议采用贪婪法构成链式通信, 同时该簇簇头进行移交, 由该簇距离网关最近的优势节点接任, 并由新簇头通知网关更新簇头列表并在网关上簇头列表上进行标记.

2.3 簇头间路由拓扑的构造

各簇建立完成后, 各簇头广播一个非持续性强度信息, 该信息包含簇头的ID, 各簇头接收到邻居簇头的信号强度, 然后各簇头各自估计出彼此间模拟距离并记录, 最后所有簇头把各自估计的模拟距离发送给网关, 同时捎带节点自身剩余能量以及本簇平均剩余能量[14-16]. 网关接收到信息报告后采用文献[13]算法, 计算出全网络簇头链路拓扑结构, 同时对剩余能量不足的簇头进行记录. 最后将网络链路结构广播至各簇头, 至此网络主干数据传输链路形成. 在各簇头首先对内部节点数据进行融合, 再使用多跳方式发送至网关. 簇间的链路多跳路由拓扑如图3所示.

图3 网络簇头路由拓扑结示意图

采用单跳的传输簇内节点与簇头传输类似LEACH协议, 每个簇内节点根据簇头广播的TDMA时隙表, 在各自的时间片内向簇头传输数据. 采用链式通信的簇内部, 采用令牌的方式依顺序向簇头方向传输数据. 簇头接收完簇内成员的数据, 经融合后, 沿各自链路向网关发送,当簇头节点接收上一跳簇头节点数据后, 先进行数据融合, 然后再发送给下一跳[10-12]. 为避免传输中数据丢失的问题, 发送节点完成数据发送后, 还会继续暂存该数据, 同时开启一个超时定时器. 在定时器超时前收到下一跳簇头节点反馈信息, 则清除暂存数据, 否则重发该数据, 若定时器超时计数大于3后, 则增强发射功率, 直接将数据发送给链路表中的该目标簇头的下一跳簇头节点. 同时, 各簇头节点均开启了接收数据定时器, 若定时器超时前未接收到上一跳簇头的数据, 则直接将自己的数据发送给下一跳节点, 避免出现无限等待的情况. 每轮数据传输完成后, 网关调整链首节点, 更新网络簇头能量匮乏表信息,避免个别簇头已经能量匮乏后继续承担链首的管理工作. 由这个新链首节点开始网络主干路由新一次的数据传输, 当所有优势节点簇头充当过链首之后, 网络将进入新一轮分簇和路由的更新, 循环往复.

3 算法仿真与分析

为了验证本文提出的改进非均匀分簇路由协议的有效性, 本文将改进算法(EUUC&N)与文献[4]中的经典EUUC算法进行了比较, 算法性能从网络生存周期和数据传输时延两方面来评价进行. 实验环境为:工作软件为Matlab R2011b, 主机为AMD Athlon 64×2 dual 5 200+2.7 GHz, 内存为DDR2-SDRAM 800 MHz 2GB. 仿真算法中采用理想MAC协议和理想的无线链路, 无丢包错误发生. 通过统计网络节点发送数据、接收数据和融合数据所耗费的能量, 统计网络生存时间(以轮数来计算)来分析协议的能量效率性能. 仿真场景为100 m × 100 m的矩形区域内, 在区域中随机产生1个10 m × 10 m空洞区域, 该区域不布设节点. 节点被随机分布到剩余区域内, 网关位置固定为(0 m, 0 m), 所有节点初始能量设为0.5 J,elec= 50 nJ/bit,fs= 10 pJ/bit/m2,mp= 0.001 3 pJ/bit/m4, 数据融合GX= 5 nJ/bit,仿真最大轮数为5 000轮. 为了消除随机因素的影响, 便于进行性能比较, 对2个算法各运行50次, 取数据结果的统计平均值.

改进的(EUUC&N)算法通过对簇头节点和普通节点的进行负载均衡, 提高能耗效率来延长网络生存时间为主要设计目标. WSN的网络生存时间(轮数)定义为从开始运行到出现死亡20%节点的轮数. 考虑到WSN网络中节点随机分布造成的单次生存时间有较大波动, 图4-图6中的数据是运行50次后得到的统计平均值. 从图4可以看出, EUUC&N协议的生存时间比EUUC协议明显提高, 大大迟延了网络初始死亡节点出现轮数, 同时占网络节点总数20%和50%死亡节点的轮数也得到了明显推迟, 这些指标的改进主要是因为降低了经典算法中能耗大节点和低能量簇头承担簇头管理工作的概率.

图4 改进协议和EUUC对应的轮数(NT)和死亡节点(Nd)关系

图5 网络节点平均剩余能量Eav 曲线图

从图5可以看出改进协议(EUUC&N)与经典EUUC协议生命周期相比, 网络的单位数据量通信的整体能耗降低. 由于改进协议(EUUC&N)的簇内采用了改进规则, 特别是对于有空洞的区域而言, 改进算法使各节点能更为合理进行了负载均衡. 图6是网络节点间的剩余能耗的方差图, 从该图中的对比曲线, 可以观察到网络节点能耗得到了更好的均衡, 各节点的能量更为均衡使用.

图6 网络节点能量方差s2每百轮消耗曲线图

对于经典EUUC协议由于没有采用有效均衡机制, 导致网络生存期进入中期后出现了节点能耗方差的明显增大, 分析认为是这个时期各个节点间的剩余能量有了较大的差别, 而经典算法依然让各节点轮流承担簇头的管理工作, 导致节点能量差异不断扩大, 导致死亡节点提前出现, 而改进算法考虑了节点由于位置和随机性造成能耗差异, 通过均衡消耗各节点的能量, 使得第一个死亡节点出现明显滞后, 确保了网络覆盖的完整性和有效性. 在经典EUUC协议中簇头的选择主要只考虑与网关的距离, 而未考虑簇头的剩余能量情况和其消耗速率, 而这可能导致非优势节点当选簇头, 进而导致低能量节点提前死亡, 整个网络的生命周期缩短. 在簇构造阶段, EUUC&N算法通过对能耗效率分析和自动簇头更新, 进一步使得节点能耗均衡. EUUC&N能耗速率计算简单, TDMA分配并不增加经典EUUC计算的开销, 因此整体上计算复杂性增加很小. 在理论分析中PEGASIS性能是非常好的, 但是现场应用时会带来较大的滞后性, 特别对于比较广阔的监控区域, 系统实时性将难以满足, 同时一旦出现中间节点的失效, 会导致该轮数据采集的无法完成. 改进算法针对存在空洞区域的监控对象, 利用PEGASIS比较适合稀疏网络的特性, 在局部特殊区域应用链路传输策略, 有效地提高了能耗效率, 其实时性也带来了保证. 同时可以很直观分析到改进算法(EUUC&N)比PEGASIS协议在传输实时性上有明显的优势.

4 结束语

本文针对存在空洞区域的监控对象, 分析了层次路由协议中分簇时会出现的“热区”问题, 提出了一种改进非均匀分簇的路由协议, 通过构造一个基于能量效率的非均匀的分簇机制, 优化簇头的产生机制和簇内通信方式, 较好地避免了传感器网络中“热区”问题的发生, 主干路由的传输机制, 既减少了由于分簇活动带来的开销, 又使得各簇头能量消耗相对均衡. 理论分析和实验仿真结果表明改进算法(EUUC&N)较好地优化了节点负载, 提高了网络节点的能耗效率, 延迟了网络节点死亡时间, 有效延长了网络整体生命周期, 提升了监控区域有效覆盖时间.

[1] Akyildiz I F,Su W L,Yogesh S. A Survey on Wireless Sensor Networks[J]. IEEE Communication Magazine,2007, 40(8):102-114.

[2] Heinzelman W B, Chandrakasan A P, Balakrisham H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communication, 2002, 1(4): 660-670.

[3] Soro S, Heinzelman W B. Prolonging the lifetime of wireless sensor networks via unequal clustering[A]. Proc. of the 19th IEEE Int′l on Parallel and Distributed Processing Symposium[C]. San Francisco: IEEE Computer Society Press, 2005: 236-240.

[4] 李成法, 陈贵海, 叶懋, 等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报, 2007, 30(1): 27-36.

[5] 黄河清, 沈杰, 马奎, 等. 无线传感网基于梯度的非均匀分簇[J]. 光学精密工程, 2009, 17(8): 2053-2058.

[6] 曾志文, 陈志刚, 刘安丰. 无线传感器网络中基于可调发射功率的能量空洞避免[J]. 计算机学报, 2010, 33(1): 12-22.

[7] 吴小兵, 陈贵海. 无线传感器网络中节点非均匀分布的能量空洞问题[J]. 计算机学报, 2008, 31(02): 1-8.

[8] 赵学健, 庄毅, 欧阳键, 等. 无线传感器网络能量空洞问题缓解策略分析[J]. 四川大学学报: 工程科学版, 2010, 42(3): 151-158

[9] 李超良, 胡春华. 无线传感器网络中面向动态多跳的非均匀分簇路由[J]. 中南大学学报: 自然科学版, 2011(07): 2048-2053.

[10] Heinzelman W B, Chandrakasan A P, Balakrisham H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communication, 2002, 1(4): 660-670.

[11] 刘群, 白全炜, 曾宪华, 等. 能量感知的WSN节点分类控制路由算法[J]. 传感技术学报, 2011, 24(7): 1053-1059.

[12] 朱丁丁, 金心宇, 张昱. 基于能量优先分簇算法的WSN分层路由协议[J]. 传感技术学报, 2009, 22(4): 579-585.

[13] 张震, 闫连山, 潘炜. 基于LEACH和PEGASIS的簇头成链可靠路由协议研究[J]. 传感技术学报,2010, 23(8): 1173-1178.

[14] Tian Ying, Wang Ying, Zhang Shu-Fang. A Novel Chain-Cluster Based Routing Protocol for Wireless Sensor Networks[J]. WiCOM, 2007: 2456-2459.

[15] Luo H, Luo J. Adaptive datafusion for energy efficient routing in wireless sensor networks[J]. IEEE Transactions on Computers, 2006, 55(10): 1286-1299.

[16] 王洪玉, 刘爽. WSN中基于融合代价和传输代价的分簇算法[J]. 大连理工大学学报, 2010, 50(4): 591-596.

An improved uneven for uneven regional clustering wireless sensor routing algorithm

LI Jian-qi1, CAO Bin-fang2, WANG Li1, WANG Wen-hu1

(1. Department of Electronic Engineering, Hunan University of Arts and Sciences, Changde 415000, China; 2. Department of Physics and Electronics, Hunan University of Arts and Sciences, Changde 415000, China)

Monitoring nodes distributed in the natural environment with natural inhomogeneities (such as the South area of the pond) and widespread clustering nodes “hot zone”, while the typical hierarchical routing protocols.This paper presents an improved non-uniform sub-cluster wireless sensor network routing algorithm for this monitoring object characteristics, in order to improve energy efficiency to ensure the effectiveness and timeliness of regional coverage. Improved algorithm firstly generate by optimizing the cluster head according to the density of nodes; then control the competitive radius of unequal cluster; after that, calculate the distribution coefficient of the cluster which is away from the gateway so as to determine the different forms of communication within the cluster; finally, use the transmission mechanism combined with single-hop and the multi-hop between the head of cluster. The simulation studies show that the improved algorithm can improve the energy efficiency of the network better, thus prolong the life of the entire wireless sensor network significantly.

wireless sensor network; uneven clustering; distribution coefficient; energy-efficient

TN 919.2

1672-6146(2012)04-0044-05

10.3969/j.issn.1672-6146.2012.04.009

2012-11-06

湖南省科技计划项目(2012SK3131)

李建奇(1980), 男, 硕士, 副教授, 主要研究方向为无线传感器网络. E-mail: li_jianqi@126.com

(责任编校:刘刚毅)