基于细胞膜优化算法的WSN分簇协议研究

覃海生,何传波,吴文俊,耿茂奎,蒋忠夏

(广西大学计算机与电子信息学院,南宁530004)

基于细胞膜优化算法的WSN分簇协议研究

覃海生,何传波,吴文俊,耿茂奎,蒋忠夏

(广西大学计算机与电子信息学院,南宁530004)

针对无线传感器网络能量受约束的问题,为实现节点均衡能耗,平衡网络簇头分布,并最大限度地延长网络寿命,提出一种基于细胞膜优化算法的无线传感器网络能量均衡分簇协议。细胞膜优化算法具有良好的全局寻优和快速收敛能力,通过浓度与能量因素对节点进行划分,并结合距离因素完成全局均衡分簇,能够解决传感器网络中簇头分布不均匀、全局能耗不均衡等问题。实验结果表明,该协议具有对无线传感器网络进行快速全局均衡分簇的能力,且与LEACH算法和LEAH-C算法相比,在均衡节点能耗和延长网络生存周期等方面具有更好的性能。

无线传感器网络;均衡能耗;细胞膜优化算法;LEACH算法;LEACH-C算法

1 概述

无线传感器网络［1］(Wireless Sensor Network, WSN)通过传感器节点感知、收集各种信息,并对其进行分析处理,从而实现远程目标监控,是集信息采集、信息处理、信息传输于一体的综合智能信息系统。由于节点多部署于无人看守区域,而且网络节点的能量、计算能力与存储能力都十分有限,特别是能量的限制,决定了网络的寿命。利用分簇的层次路由［2］已经被证明在无线传感网络的扩展性、节点平衡能耗与网络整体寿命的延长等方面有很好的优势。

LEACH［3］(Low-energy Adaptive Clustering Hierarchy)算法是最早提出的应用于无线传感网络的层次路由算法。LEACH-C［4］(LEACH-Centralized)是一种集中式的簇头选择算法,将节点当前能量作为簇头选取的条件,在高于全网平均能量的节点中寻找最佳的分簇方案、最小化的通信能量消耗。近年来,随着对群智能优化算法的深入研究,结合群智能算法具有较好的自适应性、鲁棒性强和可扩展性等特点,对基于群智能优化算法的无线传感器网络分簇路由算法的研究也取得了较大的成果。文献［5］提出了基于动态人工鱼群优化的WSN分簇算法。文献［6-7］分别提出了在节点群智能算法上改进的无线传感器网络分簇算法。文献［8-9］提出基于蚁群算法的对WSN分簇路由进行改进的算法。文献［10］在人体血管网络特性引入到无线传感器网络拓扑结构和分簇模式研究的基础上进行了无线传感器网络非均匀等级分簇拓扑结构的研究。细胞膜优化［11］(Cell Membrane Optimization,CMO)算法通过研究细胞膜的特性及其物质转运方式,从中进行提取优化模型,并结合全局优化算法的基本思想,提出了一种新型的全局优化算法,该算法具有很好的全局寻优能力、快速的收敛能力和获取高精度解的能力。本文根据细胞膜优化算法的思想,提出了一种基于细胞膜优化算法的无线传感网络分簇协议。

2 基于细胞膜优化算法的分簇协议思想

2.1 细胞膜优化算法思想

细胞膜优化算法是通过研究细胞膜的特性及其物质转运方式,从中进行提取优化模型,并结合全局优化算法的基本思想而提出的一种新型全局优化算法。细胞膜(Cell Membrane,CM)是细胞表面的一层薄膜。它是保证细胞内环境相对稳定的屏障,使细胞的各种活动能够有序地运行。物质转运方式主要有自由扩散、协助扩散、主动运输、入胞和出胞等,前3种方式是重点研究的。脂溶性物质由膜的高浓度侧向低浓度侧的扩散过程称为自由扩散。非脂溶性物质在膜蛋白(即载体)的帮助下,顺浓度差跨膜扩散的程称为协助扩散。离子或小分子物质在膜上“泵”的作用下,被逆浓度差的跨膜转运过程,称为主动运输。自由扩散不需要载体也不需要能量,协助扩散只需要载体不需要能量,主动运输既需要载体也需要能量［12］。

根据细胞膜转运物质的过程,把物质分为3种:高浓度脂溶性物质,高浓度非脂溶性物质和低浓度物质。在最优化问题时,根据物质的浓度因子大小划分为高浓度物质群和低浓度物质群,接着再把高浓度物质群进一步划分为高浓度脂溶性物质和高浓度非脂溶性物质2个子物质群。

2.2 优化协议分簇流程

基于细胞膜优化算法的一次分簇协议思想包括以下7个步骤:参数的设定和初始化,节点划分,脂溶性节点的运动,高浓度非脂溶性节点运动,低浓度节点运动,当前最优节点循环运动和节点的更新。协议流程见图1。

图1 优化协议流程

由协议可知,在每次循环结束后才对各节点群进行更新,算法结束的条件是满足最优条件或者达到最大循环次数。

3 基于CMO的分簇协议

3.1 参数设定与节点初始化

把无线传感网络中的每个节点都抽象成算法中的节点,有n个节点则节点总数量为n;每次选择簇头的最大迭代次数为Gmax;计算节点浓度采用的半径系数为r;当前最优节点停止搜索的临界值pa;搜索半径的收缩率为pb。

在无线传感网络中随机部署n个节点,根据半径系数r计算每个节点半径内生存节点的浓度con。如节点i的浓度con定义为:其半径内包含的所有有效节点到i节点的距离总和除以总节点数n乘以半径的比值,即:

e为每个节点的能量与网络平均能量的比值。每个节点因子值(p)由节点的浓度con与节点能量比值e确定,即p=a·con+b·e,其中,a+b=1且a,b都大于0。引入载体因子来调节节点运动的轨迹。每个节点的载体因子ε定义为:在2倍搜索半径(2r)内所有有效节点到本节点距离的倒数和与总节点数n的比值。如式(2)所示:

ε为平均距离参数,ε大则半径内的节点到本节点距离和较小,反之则较大。

3.2 节点的划分

在n个节点中,按照因子值(p)的大小进行排序,根据表1的比例来划分节点。

表1 节点划分方式

按照表1的方式划分出3种节点群,其中,X代表分配比例。最优解要通过多次迭代才能出现,所以不同的分配比例不会对每轮簇头数量与最优解产生太大的影响。不过偏低或过高的X都会导致3种节点群比例差距大、3种节点群间抖动频繁,延长最优解的迭代次数和3种节点群数稳定不变的迭代次数,增加计算量。综合考虑在实验中采用X为15%～20%的比例。

3.3 脂溶性节点的运动

每个高浓度脂溶性节点,如i节点,若半径范围内有低浓度节点群L或高浓度非脂溶性节点群HF的节点,保持脂溶性节点不变,并选择距离自己最近的一个节点作为自己的临时最优簇头。若在节点搜索半径内没有非脂溶性节点或低浓度节点时,节点根据自身的能量选择概率性扩散成为非脂溶性节点或保持不变。

3.4 高浓度非脂溶性节点的运动

高浓度非脂溶性节点在搜索半径内与所有低浓度节点比较载体因子(ε),若存在ε大于某个低浓度节点则运动成低浓度节点,否则向半径内的L群节点中选择一个最优节点,然后向其扩散,成为脂溶性节点。

若搜索半径内没有低浓度节点,则与半径距离内所有非脂溶性节点的ε比较,若自己最大则执行运输成为低浓度节点。否则保持非脂溶性节点不变。

高浓度非脂溶性节点运动存在2种类型的运动形式,一种是向低浓度节点方向的协助扩散运动,另一种是向当前全局最优节点方向的运动。

3.5 低浓度节点的运动

对于低浓度节点,先判断其能量是否满足条件,若其不满足大于平均能量的条件,直接变成脂溶性节点,并在半径内寻找最优L群和HF群节点作为自己的临时最优簇头。

对于满足能量条件的节点,算法同样引入载体因子,进一步对低浓度节点的运动形式进行限制。接着判断其是否满足ε条件,如是否满足在半径距离内所有低浓度节点中ε最优,若满足则依旧保留为低浓度节点,否则运动为高浓度非脂溶性节点。

低浓度节点运动存在3种类型的运动形式:第1种是节点在搜索域的随机运动成为脂溶性节点;第2种是向高浓度节点方向运动的主动运输成为高浓度非脂溶性节点;第3种是向当前全局最优节点方向的运动并保持低浓度节点的性质。

3.6 当前最优节点的循环运动

在优质节点附近往往会存在更优的节点,这样不仅充分发掘当前最优节点邻域内的节点空间,有利于种群的进化,更是对提高节点的精度有着重要的意义。

以低浓度节点作为当前最优节点并以其为中心,以半径R进行搜索,R为:

其中,r为半径系数,以pb=0.8的收缩速率进行。在半径小于等于pa时退出搜索。在搜索过程中若存在全局最优解半径和全局最优分簇,则接收这个解空间。在全局解空间中保存这个解和解半径。

主要思想是:在半径为2r开始比较簇头间的成簇能耗,随机试探性地在收缩半径内把多个簇进行合并,如果合并后的总能量消耗小于合并前的总能量消耗的90%以上,则把多个簇合并成一个簇,减少全局的能量消耗。合并会导致簇成员增加,所以选择出主从簇头,合并后的最优主簇头负责收集簇内成员的信息并融合,在多个簇中选择一个从簇头担任和基站的联系,这样会大大减少全局能量消耗。如果此时的全局解优于前面的全局最优解,则接受这个解并保存到全局最优解与最优半径中。继续循环直至到达退出条件。在全部循环结束以后会产生本次循环的最优分簇和最优半径。在最大循环次数的时候输出全局最优分簇和最优半径。

3.7 节点更新

在更新节点步骤中,把新的当前最优解和解半径与原来的比较,若当前最优则替换原来最优解与解半径,计数器重置为0;否则保留原最优解与解半径,计数器加1。由新的3种节点群替换原来各自旧的节点群。要注意的是,所有节点只有在节点更新步骤才能进行更新节点,这是为了保证前面节点运动的并行性,也就是说,当代节点的产生只与上一代的节点有关,不与当代其他任何节点的变化有关。例如,在高浓度脂溶性节点运动的步骤中,高浓度脂溶性节点的运动需要低浓度节点和非脂溶性节点的参与,也可能产生非脂溶性节点。而在低浓度节点的运动中,也会产生脂溶性节点和非脂溶性节点,它们之间存在着交叉依赖关系。若采用时时更新,那么节点运动步骤出现的先后顺序将影响进化的结果,同时也不利于算法的并行实现。

3.8 协议结束条件

在每次循环结束后都判断计数器的值是否大于3(实验统计3次以后还会产生可替代最优解的概率不到5%),大于3则认为满足最优解条件或达到最大迭代次数Gmax(根据每个实验环境测试决定),如果没有满足最优条件或未达到最大循环次数则转到3.3节的步骤继续执行。否则结束本轮簇头选择,输出本轮选择出的最优解和解半径,作为本轮分簇的最优分簇,并按这个解进行分簇。

4 实验结果与分析

4.1 实验环境与参数设定

为了测试基于CMO算法的分簇协议的性能,本文算法的仿真测试在处理器为英特尔G530、内存2 GB的PC上,基于Matlab R2009a的环境模拟实现。仿真参数设置如下:在［200,200］m区域内随机部署200个节点,Sink的初始位置在(0,0)m。半径系数r=40 m,节点的初始能量都为1 J。本文实验中所有轮数都是一次分簇包括5次数据传送。

4.2 结果分析

图2是本文算法的一次簇头分布,其中,星号表示簇头;圈表示普通节点。由图2可以看出,该算法在簇头节点的分布上相对比较均匀,这样有利于全局能耗的均衡。

图2 仿真模拟节点分布

为了解不同半径对本文协议的影响情况,实验对不同半径下的网络存活节点数进行了比较。

根据图3的实验结果表明,不同半径对网络的寿命还是有比较大的影响,因而在实际应用中针对实际的网络情况,通过比较选择出一个比较适合的半径也相当重要。在本文实验中半径在30 m左右取得比较好的使用寿命。

图3 本文协议在不同半径下的存活节点数比较

图4和图5分别给出了不同半径下每轮的簇头数。根据比较可以看出,在半径为30 m时,大部分时候簇头数目稳定在12个～18个,簇头数占总节点数0.6%～1%。但是半径为40的时候簇头数波动比较大,簇头数目相对于30 m时少了2个 ～3个。2个簇头数的比较:在半径为30 m的簇头数在300多轮的时候还保持了相对的稳定,而半径为40 m的时候,簇头数在200多轮的时候开始出现下滑趋势,表明了网络中开始出现死亡节点,也体现出半径为30 m时能更好地延长整个网络的寿命。

图4 半径为30 m的簇头数目

图5 半径为40 m的簇头数目

针对不同网络节点分布情况下最优簇头出现的迭代次数进行统计发现,最优的迭代次数多为6次～9次,而算法中3种节点稳定不变的迭代次数为10次～14次,表明了在产生最优解的时候3种节点还没有稳定,而在随后的迭代中没有产生更优的解。在这一方面还要做进一步的研究,以使算法在节点群没有稳定的时候产生更优解或者在节点群稳定的时候才应该产生最优解。

经过300次节点随机分布进行实验统计,图6给出本文协议、LEACH算法和LEACH-C算法每轮节点存活数的比较,大部分LEACH算法第1个节点死亡的轮数是105轮左右,LEACH-C算法第1个节点死亡的轮数是176轮左右,而本文算法的第1个节点死亡集中在300轮左右,很好地延长了第1个节点的死亡时间。在网络覆盖上,LEACH算法和LEACH-C算法网络的节点死亡都是在远离基站的节点先死亡,导致在网络节点数目下降的时候出现了覆盖漏洞,而本文算法的节点死亡是随机分布的,所以在较多的节点死亡情况下还能保持较好的覆盖率。根据图6也可以看出本文算法在网络的整体寿命上也有较好的表现,延长了网络寿命。

图6 算法仿真比较

5 结束语

本文通过分析细胞膜算法的特点并与无线网络分簇机制相结合,提出了一种基于细胞膜算法的无线传感网络分簇协议,对网络分簇与全局能耗进行优化。协议通过节点的覆盖率和剩余能量作为因子,利用细胞膜算法的全局寻优能力,在全局范围中进行最优的分簇和簇内最低能耗的簇头选择方式,克服了网络簇头分布不均衡、各分簇能量消耗不平衡、总体网络能耗达不到最优等问题。

通过实验证明,基于细胞膜算法的分簇协议不仅均衡了全局网络节点的能耗,还快速地对网络进行全局分簇,降低网络的总体能耗,延长了网络的寿命。但是其在分簇过程中没有考虑消息的路由传送,今后将进一步优化分簇协议,研究节点跳数与最优路径间的关系。

［1］ 邬春学,肖 丽.基于蚁群算法的低能耗LEACH协议分析［J］.上海理工大学学报,2010,32(1):99-102.

［2］ 闫效莺,程国建,孙 涛.一种能耗均衡的WSN分簇路由算法［J］.计算机工程,2012,38(14):79-81.

［3］ Heinzelman W,Chandrakasan A,Balakrishnan H.An Application-specific Protocol Architecture for Wireless MicrosensorNetworks［J］.IEEE Transactionson Wireless Communications,2002,1(4):660-670.

［4］ Siva D M G,Ma D C F.A Centralized Energy Efficient Routing Protocol for Wireless Sensor Networks［J］.IEEE Radio Communications,2005,43(3):8-13.

［5］ 刘向东,宋 欣,王翠荣.基于动态人工鱼群优化的WSN分簇算法［J］.微电子学与计算机,2011,28(8): 43-46.

［6］ 范兴刚,侯佳斌,介 靖,等.基于DPSO的智能WSN分簇路由算法［J］.传感技术学报,2011,24(4): 593-600.

［7］ 李洪兵,余成波,闫俊辉,等.基于改进节点群聚类的无线传感网络能量均衡分簇策略［J］.计算机应用研究,2011,28(2):657-660.

［8］ 廖明华,张 华,谢健全.基于蚁群算法的WSN能量预测路由协议［J］.计算机工程,2012,38(3):88-90.

［9］ 苏 兵,黄 娟.一种基于蚁群算法的WSN能效均衡路由［J］.微电子学与计算机,2012,29(11):50-52.

［10］ 李洪兵,熊庆宇,石为人.无线传感器网络非均匀等级分簇拓扑结构研究［J］.计算机科学,2013,40(2): 49-52.

［11］ 谭世恒,余卫宇.一种新型的全局优化算法——细胞膜优化算法［J］.计算机应用研究,2011,28(2): 455-457.

［12］ 谭世恒.一种新型的群智能优化算法——细胞膜优化算法及其应用［D］.广州:华南理工大学,2011.

编辑 任吉慧

Research on Clustering Protocol of WSN Based on Cell Membrane Optimization Algorithm

QIN Haisheng,HE Chuanbo,WU Wenjun,GENG Maokui,JIANG Zhongxia
(College of Computer and Electronic Information,Guangxi University,Nanning 530004,China)

Aiming at energy constrained problems in Wireless Sensor Network(WSN),in order to achieve a balanced energy consumption of nodes,balance cluster heads distribution,and maximize the network lifetime,this paper proposes a WSN energy balanced clustering protocol which is based on the Cell Membrane Optimization(CMO)algorithms.The CMO algorithm has good ability of global optimization,and fast convergence capability.The new clustering protocol divides the nodes through concentration and energy factors.Combined with the distance factor for global clustering balance,it can be a good solution to the uneven distribution for cluster head,imbalanced global energy and other issues.Experiments show that the protocol has the capability of balanced global clustering quickly.Compared with LEACH algorithm and LEACH-C algorithm,it has better performance in terms of balancing power consumption and prolonging the network lifetime.

Wireless Sensor Network(WSN);balanced energy consumption;Cell Membrane Optimization(CMO) algorithm;LEACH algorithm;LEACH-C algorithm

1000-3428(2014)11-0092-05

A

TP393

10.3969/j.issn.1000-3428.2014.11.018

国家自然科学基金资助项目(61262072)。

覃海生(1956-),男,教授,主研方向:网络与信息安全;何传波、吴文俊、耿茂奎、蒋忠夏,硕士研究生。

2013-09-27

2014-01-02E-mail:hechuanbo40701@126.com

中文引用格式:覃海生,何传波,吴文俊,等.基于细胞膜优化算法的WSN分簇协议研究［J］.计算机工程,2014, 40(11):92-96.

英文引用格式:Qin Haisheng,He Chuanbo,Wu Wenjun,et al.Research on Clustering Protocol of WSN Based on Cell Membrane Optimization Algorithm［J］.Computer Engineering,2014,40(11):92-96.