基于混沌-量子粒子群的分簇路由算法

田思琪,郎百和,韩太林

0 引 言

无线传感网络(WSN:Wireless Sensor Network)中的传感器节点由于能量有限,在工作过程中不能进行二次充电或更换电池,因此,如何有效提高网络节点的能量利用率,延长节点的生命周期是无线传感网络路由算法的关键技术之一。路由的表现方式可分为层次路由与平面路由。层次路由相对平面路由具有扩展性好、建立维护路由的开销小、数据传输跳数少和适合大规模网络的特点。层次路由通常利用分簇方式提高能量利用率,延长生命周期。分簇路由协议的思想是:将网络中所有节点以一定的竞选方式选出N个最优节点作为簇头,然后其他节点在以一定的算法机制选择加入某个簇头形成簇,最终由簇头收集其他成员节点的信息并进行融合发送给汇聚节点。但采用分簇路由协议时,簇的维护开销较大,所以如何选取最优簇头是优化路由的关键。LEACH(Low-Energy Adaptive Clustering Hierarchy)是由Heinzelman等[1]首次提出的一种基于分簇的路由协议。但LEACH协议并没有规定簇头的分布范围并加以限定,从而导致选择的簇头会集中在某一区域,使整个传感网络能耗分布不均匀。因此,国内外学者在簇头选取方面选择粒子群、蚁群等智能算法[2-6],在成簇方式上选择K-Means、EECS(Energy-Efficient Clustering Scheme)等[7-11]聚类策略改善簇头分布不均的问题。

进化算法具有较强的全局收敛能力和鲁棒性,且不需借助特征信息,如导数等梯度信息。粒子群优化算法(PSO:Particle Swarm Optimization)[12]也是一类基于群体智能的随机优化算法,作为简单有效的随机搜索算法,在寻求函数最优解、神经网络训练和模式识别等领域具有很大应用潜力。粒子群算法是1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出的[13],其基本思想是受他们早期对鸟类群体行为研究结果的启发,并利用生物学家Frank Heppner的生物群体模型。与其他进化类算法相似,也是用群体与进化的概念,同样也是依据个体(微粒)的目标函数值大小进行操作。PSO算法由于其简单易懂在许多领域中都有应用,然而该算法也具有收敛速度慢、易陷入局部最优的缺点。在无线传感器网络路由算法中,利用PSO算法寻找最优簇头的过程中,会使网络节点能量消耗过快,引起无线传感网络节点能量消耗不均衡、造成传感节点呈现大面积平铺式的死亡等现象。文献[13]提出了一种PSO-C(Cluster setup using Particle Swarm Optimization Algorithm)分簇路由算法,在选取簇头时虽考虑了成员节点与簇头之间的距离,但忽略了簇头与汇聚节点的距离致使网络节点能量消耗过快,生命周期得不到保障;文献[14]提出的EBUCP(Energy-Balanced Unequal Clustering Protocol)算法综合考虑了能量、地理位置及簇头密度等因素,延长了网络的生命周期,但未改进PSO算法使算法容易陷入局部最优,导致网络能量消耗不均衡。

笔者对PSO算法的权重进行改进,采用收敛速度快的凹函数递减策略优化权重,并引入混沌因子与量子元素,构成双子粒子群(TSPSO:Two Subpopulation Particle Swarm Optimization)算法,改进了簇头选取模式,提高了节点的能量利用率,延长网络的生命周期。

1 粒子群优化算法

PSO算法的数学模型:假设在D维度空间中,有M个粒子,每个粒子的位置为

速度为

其中i=1,2,…,M。每个粒子经过的历史最优位置用pi表示,所有粒子经历过的最好位置用pg表示。每个粒子均按照

进行速度与位置的更新。其中w为惯性权重;c1与c2指自身继承及社会继承的学习因子;r1与r2是0～1之间的随机数。

1.1 改进的混沌粒子群

传统的粒子群算法初期收敛较快,而在后期容易陷入早熟状态,即导致局部最优。采用胥小波等[15]提出的混沌粒子群,不再利用混沌序列产生新粒子代替原粒子,而是将混沌态融入到粒子的运动过程中,使粒子在稳定与混沌状态间交替运动,在保证精度的前提下,避免算法产生初期收敛过快的现象。

为将粒子混沌化,采用Sole等[16]提出的混沌系统

其中x∈(0,1)表示混沌状态;μ∈[0,4]表示混沌系统的控制参量。引入混沌变量

在粒子运动过程中控制粒子的混沌状态。其中rid表示第i个粒子第d维的混沌因子,且是不大于1的正常数。

混沌粒子群优化系统中的速度更新采用与式(3)相同的方式,而位置更新方式为

其中ψd为搜索测度。当cid→0时,粒子的速度及位置分别按式(3)、式(4)更新;当cid→1时,粒子的速度及位置分别按式(3)、式(7)更新。

根据陈贵敏等[17]提出的关于惯性权重的理论,非线性惯性权重策略相比线性递减的惯性权重策略更能有效地控制粒子群算法的全局搜索以及局部搜索。采用凹函数非线性递减策略更新惯性权重,规则为

其中w∈[0.45,0.9];CCurCount为当前迭代轮数;CLoopCount为迭代总轮数。

1.2 量子粒子群

量子粒子群的思想是由Xu等[18]在2005年提出的,其从量子力学角度出发,使PSO算法中的粒子具有量子行为,用位移模型代替了速度-位移模型,具体迭代方法为

其中Pavebest表示种群平均的最优位置;M为种群大小;φ,μ为0～1之间的随机数;压缩-扩张因子

用于抑制粒子的速度。

2 基于混沌-量子的TSPSO分簇路由协议

分簇路由协议结构图如图1所示。TSPSO路由协议采用分簇的体系结构,将所有的网络节点分为两类:一类是簇头,簇头通过代价函数的约束选取,负责收集普通节点的消息,并将所有的消息融合后传送给基站;另一类是普通节点,根据分簇算法,寻找其所属簇头,并将消息传送给簇头。

图1 分簇路由协议结构Fig.1 Structure of clustered routing protocol

2.1 代价函数

为使传感网络能耗消耗均衡,并延长其生命周期,算法的代价函数定义如下。

分簇紧凑评价因子

其中d(ni,Hpj,k)表示普通节点到对应簇头的欧氏距离,Cpj,k为当前簇头所对应的成员个数,K为簇头个数。

能量评价因子

其中E(ni)为普通节点的能量,E(Hpj,k)为簇头的能量。

位置评价因子

其中d(B,Hpj,k)为基站与当前簇头的欧氏距离,d(B,N)为基站与网络中心的距离。

则当选簇头的代价公式为

其中a+b+c=1。

2.2 分簇算法

TSPSO实现的思想是,将初始化后的粒子等分成两个种群,分别为主粒子群和辅粒子群,主辅两种粒子群按自己的位置分别进行更新寻优,每次迭代更新后比较各自代价函数,代价函数值较优的粒子代替较差的,以此更新种群,从而加快粒子寻优的速度。

TSPSO算法中,主粒子群用改进的混沌粒子群寻优,辅粒子群用量子粒子群寻优。数据收集以“轮”的形式进行更新,具体算法如下。

1)根据节点能量,初始化M个粒子群。将节点能量大于节点平均能量的节点作为候选簇头,从候选簇头中随机选择K个节点作为一个粒子群。

2)利用式(13)～式(16)计算每个粒子的代价函数值。

3)确定每个粒子的个体最优解Pid和种群最优解Pgd。

4)根据式(4)～式(12)分别更新主、辅粒子群的速度与位置。

5)重复步骤2)与步骤3),直到达到最大循环次数MMaxIter。

迭代完成后,得到传感网络中最优簇头,根据就近原则,普通节点根据到各个簇头的欧氏距离大小选择加入哪个簇头。通过这种分簇结构,实现数据节点到基站(汇聚节点)的路由。

3 WSN模型及能耗模型

算法采用与文献[19]相同的传输能耗模型,定义节点发射l bit的数据到距离d的位置,能量消耗由发射电路损耗和功率放大损耗两部分组成,即

其中d0为发送者至接收者的距离阈值,根据不同的传输距离选择不同的能耗模型。εfs、εmp分别为两种模型下功率放大所需的能量消耗。阈值

节点接收l bit的数据消耗能量为

簇头融合数据消耗能量为

无线通信能耗模型仿真参数设置如表1所示。

表1 无线通信能耗模型参数设置Tab.1 Parameter of wireless communication energy consumption model

4 仿真与分析

4.1 参数设置

仿真在Matlab R2017a环境下进行,将N=200个网络节点随机洒落在200×200的方形区域内,基站坐标为(100,275),模型能耗的参数设置如表1所示。节点分布图如图2所示,且簇头个数

其中A为方形区域的边长,dtosink为簇头到基站的距离。

图2 节点分布图Fig.2 Node distribution map

4.2 仿真分析

笔者将算法与LEACH、PSO-C及EBUCP算法进行了仿真对比分析。图3为每轮节点的平均剩余能量,图4为每轮节点的存活个数。TSPSO协议在簇头选择上结合了节点的能量和位置信息以及与基站的距离,在节点初始能量相同的情况下,TSPSO协议每轮的能量消耗明显较其他3种协议少,保证了传感节点的生命周期。仿真结果证明,TSPSO协议的生命周期比LEACH协议、PSO-C协议分别延长了80.1%和41.4%。说明基于混沌-量子粒子群的TSPSO协议能更好地延长网络的生存时间。与EBUCP相比能更好地均衡网络中节点的能耗。图5是4种协议的能量方差,TSPSO协议由于采用了混沌与量子结合的两种模式,使粒子在混沌与量子形态中较快的寻找到最优簇头,能量方差较小。进一步说明了TSPSO协议在能量消耗的均衡性方面显著优于其他3种协议。

图3 节点平均剩余能量Fig.3 Node average residual energy

图4 节点存活个数Fig.4 Numberofnodessurviving

图5 能量方差Fig.5 Varianceofenergy

5 结 语

针对无线传感网络分簇路由协议,首次提出了混沌与量子结合的双粒子群模式,将改进的混沌粒子群作为主粒子群,量子粒子群作为辅粒子群。

当粒子群陷入早熟收敛时,利用混沌运动的随机性、对初始值敏感等特点,将混沌态融入到粒子的运动过程中,使粒子在混沌与量子状态间交替运动,以避免陷入局部最优,从而寻求更优解,达到在不影响精度的前提下,使粒子快速收敛的目的。综合考虑节点的能量以及位置寻找最优簇头,仿真结果验证了算法使无线传感网络节点能量消耗更加均衡,显著延长了网络生命周期。

[1]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHNAN H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]∥Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui,USA:IEEE,2000:3005-3014.

[2]ELHABYAN R.PSO-HC:Particle Swarm Optimization Protocol for Hierarchical Clustering in Wireless Sensor Networks[C]∥International Conference on Collaborative Computing:Networking,Applications and Worksharing.Miami,FL,USA:IEEE,2015:417-424.

[3]REN Z,WANG L,LEI H.A Study on Energy-Saving Routing Algorithms for Wireless Sensor Networks Based on Particle Swarm Optimization[C]∥Second International Conference on Instrumentation,Measurement,Computer,Communication and Control.Harbin,China:IEEE,2013:638-643.

[4]ZAHEERUDDIN,LOBIYAL D K,PRASAD S.Ant Based Pareto Optimal Solution for QoSAware Energy Efficient Multicast in Wireless Networks[J].Applied Soft Computing,2017,55:72-81.

[5]MAJUMDAR S,SHIVASHANKAR,PRASAD P R,et al.An Efficient Routing Algorithm Based on Ant Colony Optimization for VANETs[C]∥IEEE International Conference on Recent Trends in Electronics,Information&Communication Technology.Bengaluru,India:IEEE,2017:436-440.

[6]FARZANA A H F,NEDUNCHELIYAN S.Ant Based Mobility Aided Routing in Mobile Wireless Sensor Networks[C]∥International Conference on Information Communication and Embedded Systems.Chennai,India:IEEE,2016:1-5.

[7]PARK G Y,KIM H,JEONG H W,et al.A Novel Cluster Head Selection Method Based on K-Means Algorithm for Energy Efficient Wireless Sensor Network[C]∥International Conference on Advanced Information Networking and Applications Workshops.Barcelona,Spain:IEEE,2013:910-915.

[8]BIDAKI MOAZAM,GHAEMI REZA,TABBAKH SEYED REZA KAMEL.Towards Energy Efficient K-Means Based Clustering Scheme for Wireless Sensor Networks[J].International Journal of Grid and Distributed Computing,2016,9(7):265-276.

[9]YE M,LI C,CHEN G,et al.EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks[C]∥Performance,Computing,and Communications Conference.Phoenix,AZ,USA:IEEE,2005:535-540.

[10]王白婷,周占颖,苏真真,等.能耗均衡的非均匀分簇多跳路由协议[J].吉林大学学报:信息科学版,2016,34(2):174-181.WANG Baiting,ZHOU Zhanying,SU Zhenzhen,et al.Multi-Hop Unequal Clustering Routing Protocol Based on Energy Consumption Balance[J].Journal of Jilin University:Information Science Edition,2016,34(2):174-181.

[11]韩广辉,张丽翠.基于LEACH协议的无线传感网能效分簇算法[J].吉林大学学报:信息科学版,2017,35(1):26-31.HAN Guanghui,ZHANG Licui.Energy Efficient Clustering Algorithm for Wireless Sensor Networks Based on LEACH Protocol[J].Journal of Jilin University:Information Science Edition,2017,35(1):26-31.

[12]KENNEDY J,EBERHART R C.Particle Swarm Optimization[C]∥Proc of IEEE International Conference on Neural Networks.Perth,WA,Australia:IEEE,1995:1942-1948.

[13]LATIFF N M A,TSIMENIDIS C C,SHARIF B S.Energy-Aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization[C]∥Proc of the 18th IEEE International Symposium on Personal,Indoor and Mobile Radio Communications.Athens,Greece:IEEE,2007:1-5.

[14]蒋畅江,唐贤伦,向敏.基于PSO的无线传感器网络非均匀分簇路由协议[J].计算机应用研究,2012,29(8):3074-3077.JIANG Changjiang,TANG Xianlun,XIANG Min.Heterogeneous Clustering Routing Protocol for Wireless Sensor Networks Based on Particle Swarm Optimization[J].Application Research of Computers,2012,29(8):3074-3077.

[15]胥小波,郑康锋,李丹,等.新的混沌粒子群优化算法[J].通信学报,2012,33(1):24-30.XU Xiaobo,ZHENG Kangfeng,LI Dan,et al.New Chaotic Particle Swarm Optimization Algorithm[J].Journal on Communications,2012,33(1):24-30.

[16]SOLE R V,MIRAMONTESO,GOODWIN B C.Oscillations and Chaos in Ant Societies[J].Journal of Theoretical Biology,1993,161(3):343-357.

[17]陈贵敏,贾建援,韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报,2006,40(1):53-56.CHEN Guimin,JIA Jianyuan,HAN Qi.Study on Inertia Weight Decreasing Strategy of Particle Swarm Optimization Algorithm[J].Journal of Xi'an Jiaotong University,2006,40(1):53-56.

[18]XU W,SUN J.Adaptive Parameter Selection of Quantum-Behaved Particle Swarm Optimization on Global Level[J].Computer Engineering&Applications,2005,86(12):420-428.

[19]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-669.