负载均衡的高效传感器网络非均匀路由算法

刘雅娜，黄战华

(1.石家庄学院 理学院，河北 石家庄 050035；2.河北师范大学 职业技术学院，河北 石家庄 050024)

0 引 言

为了延长整个WSN的生命期[1-3]，许多研究人员开发了有效的网络协议，使全网的传感器能耗均衡，从而延长全网的生命期[4]。WSN的路由协议主要分为平面型路由协议与分层型路由协议两种[5]，平面型协议需要维持较大的路由表，占据较大的存储空间，因此并不适用于大规模的WSN中；而分层路由协议则通过相对较低的成本达到最大化网络生命期的目标[6]。

LEACH算法[7]是一个经典分簇路由协议，该协议采用分簇结构、本地数据联合处理以及动态分配簇头来实现网络的能耗均衡，但LEACH并未考虑节点的剩余能量、簇头分布等重要因素，因此性能一般。此外许多文献对LEACH算法进行了优化，逐渐地提高了LEACH协议的性能[8-10]。文献[11]提出一种基于粒子群的WSN分簇路由协议(PCR)，该协议充分地考虑了全网节点的剩余能量，有效地平衡了节点的能耗，其实验结果表明，该算法优于许多主流的WSN路由协议。文献[12]则进一步考虑了由控制消息传输所引起的能耗，以及基站附近的中继簇头容易过早死亡的问题，提出了一种去中心化的分簇路由协议(简称为DCR)。

MOIA算法(多目标免疫算法)是继遗传算法后的又一个重要的演化算法，MOIA具有几个特性[13,14]：①具有全局的搜索能力；②解集在收敛性、多样性、分布均匀性方面均具有较好的性能；③对于多目标约束的优化问题具有较好的健壮性；④可针对不同的目标问题，将种群大小调节至合理的大小，降低了目标评价函数的调用次数；⑤计算成本较低。

多跳的路由协议中，基站远端的簇头将基站附近的簇头作为中继节点，因此基站附近的簇头能耗高于远端的簇头，该情况称为WSN的“热点”问题。为了解决“热点”问题，本文设计了一种非均匀的分簇方案，基于区域与基站的距离以及节点的剩余能量值将整个区域划分为不同大小的簇，然后采用多目标免疫算法，在保证节点间连接性与最小化所有节点通信成本的条件下，搜索最优的分簇方案并建立最优的路由树。为了节约计算开销与时间开销，仅当当前簇头的剩余能量值低于指定阈值的情况下，才设置新簇头。基于多组仿真实验的结果表明，本算法有效地提高了网络生命期，解决了“热点”问题，并平衡了网络中节点的能耗，此外，本协议计算复杂度较低。

1 本文符号

假设WSN由一个BS(基站)与N个传感节点组成，分布于M1×M2的目标区域，首先作以下假设：①BS资源丰富，其消息可发送至网络中所有节点；②所有传感节点与BS是固定的；③所有传感器有一个ID；④传感节点具有能量控制机制，可根据传输距离调节发送的能量大小；⑤簇内的感知信息关联性高且可以融合，而簇间数据相差较大。

1.1 能耗模型

图1所示是WSN的无线通信模型，将k比特消息传输距离d的无线成本计算为

ETx(k,d)=ETx-elec(k)+ETx-amp(k,d)=kEelec+EAmpkdp

(1)

接收该消息的无线成本为

ERx(k)=ERx-elec(k)=kEelec

(2)

ESen(k)=kEsensing

(3)

因为簇内采集的信息十分相似，所以簇头(CH)可将不同节点的数据聚集为一个固定长度的数据包，聚集m个k比特的数据所引起的能耗计算为

Eagg(k)=mkEDA

(4)

假设网络分为L个簇，每个簇包含mi=(i=1,2,…,L)个成员节点，每个传感节点的数据包长度为k比特，簇内成员节点需采集数据并将数据传递至CH。所以簇内成员节点l通信的能耗为

Emen-i(l,k,d)=Esen(k)+ETx(k,d)=
(kEsensing)+(kEelec+EAmpk(d(l,i)p))

(5)

式中：d(l,i)是l与簇头i之间的距离。CH的能耗则包括簇内、簇间通信两部分，式(6)是CH的总能耗

ECH(i,k,d)=kEsensing+kEelecmi+kEDA(mi+1)+
kEelecrelay(i)+(relay(i)+1)(kEelec+EAmpk(d(i,NH))p)

(6)

式中：d(i,NH)是CH节点i与下一跳之间的距离，relay(i)是转发其它CH中继数据包的数量。

图1 WSN的无线通信模型

1.2 连接模型

为了保证传感节点间的连接，本协议的簇头应当覆盖网络的所有节点。簇头CHi(xi,yi)覆盖传感节点snl(xl,yl)的表达式可描述为

(7)

网络共有L个簇头，所以节点snl被覆盖的概率为

(8)

最终，将簇头覆盖的传感器数量与网络中总的活动节点数量(Nlive)的比例作定义为覆盖率(RCov)，如下计算

(9)

1.3 问题模型

协议将网络分簇为非均匀的L个簇，目标是满足节点间连接的情况下，最小化网络的通信成本，并平衡节点间的负载。本文WSN分簇路由协议主要有以下目标：

目标1：最小化协议每轮簇内所有节点的能耗

(10)

式中：ECH_CP(i,kCP,d)与Emem,CP-i(l,kCP,d)分别是簇头i成员节点l数据包所引起的能耗。

目标2：在网络中每个节点在与CH连接的前提下，最小化未覆盖传感节点的比例

min(RUncov=1-RCov)

(11)

目标3：搜索能耗最低的最优簇头数量CHs(L)，目标函数为

min(NCH=L/N)

(12)

最终，将3个目标总结为以下的总目标函数

F=w1Edisp+w2RUncov+w3NCH

(13)

式中：w1、w2与w3是权重因子，范围均为[0,1]，且w1+w2+w3=1。本文的第二个目标是使用非均匀分簇机制调节CH的簇内与簇间能耗来平衡节点的负载。

2 基于免疫的非均匀分簇路由协议

多跳路由具有“热点”问题，分簇网络中能耗不平衡的原因主要有两个：CH与成员节点的能耗不同；BS附近的CH中继远端CH数据包需要更多的能耗。本协议解决热点问题并平衡所有传感节点的能耗，具体方法为：①采用MOIA算法选择剩余能量较多的节点作为簇头，选择最优的簇头数量，为每个CH建立一个路由树，确保网络的连接并最小化数据与控制报文的开销；②周期地改变网络的CH；③根据各簇与BS的距离将网络分为非均匀的大小，并调节CH的簇内与簇间能耗；④从每个CH到BS的路由集中根据剩余能量与路由跳数选择最优的下一跳；⑤考虑簇建立阶段的距离与剩余能量。

如图2所示，本协议中每轮包含两个阶段：第一阶段为簇建立阶段(T1)，BS建立一个最优分簇方案与每个簇头的路由树；第二阶段为数据传输阶段(T2(T2>>T1))。为了减少簇建立阶段控制报文极大的计算开销与时间，仅当上一轮中CH的剩余能量低于阈值(Eth)触发簇建立阶段。密集型网络中搜索最优CH集合计算时间较长，所以本协议将传感区域划分为若干个虚拟网格，并选择各虚拟网络中剩余能量较高的节点建立候选传感器集(S)；然后，BS使用MOIA算法从集合S中选择最优的CH，同时，选择与每个CH最近的节点作为副CH，如果CH发生故障，则将副CH代替CH。图3所示是本协议的流程。

图2 本协议的时序

图3 本协议的总体流程

2.1 信息收集阶段

仅在第一轮的开始进行信息收集，BS收集所有节点的信息并将传感区域划分为若干个虚拟网格。首先，BS广播一个消息Reqst_Msg(ID,xBS,yBS)(其中包含其位置与ID)；收到该消息的节点回复一个消息Self_Info_Msg(ID,location,E0)(包含ID、位置与初始化能量(E0))，BS将所有节点的状态设为普通节点并将全网信息保存，分簇完成后，节点设为CH或成员节点。然后，BS将目标区域划分为ngrids个虚拟网格，如图4所示，ngrids值的计算方法如下所示

ngrids=ngrids_x×ngrids_y

(14)

式中：ngrids_x与ngrids_y分别是水平轴与垂直轴的虚拟网格数量，分别如下计算

(15)

图4 虚拟网格划分

2.2 分簇建立阶段

在簇建立阶段，BS建立最优的分簇方案并为每个簇头建立一个路由树。首先，基于每个节点与BS的距离及其剩余能量计算节点的Rc，计算方法如下

Rc(l)=

(16)

式中：l=1,2,…,Nlive，dmaxBS与dminBS分别是节点与BS间最长与最近的距离，d(l,BS)是节点l与BS的距离，Eres是节点的剩余能量，Emax是节点的最大剩余能量，α与β是[0,1]区间的常量，且α+β≤1。分析式(16)可看出，α、β与Rmax影响簇(Rc)的大小，Rmax是决定CH数量的关键参数，α与β则决定了节点-BS距离与剩余能量的权重。

BS使用MOIA算法搜索集合S中最优的CH与VCH，之后，每个CH中建立一个路由树，簇内路由的目标是最小化数据与控制报文的通信成本，因为控制报文能耗较大，所以本协议在CH选择程序中考虑控制消息的能耗。每轮CH与成员节点控制报文的能耗如下计算

ECH_CP(i,kCP,d)=2kCPEelec+kCPEelecmi+

(kCPEelec+EfskCP(Rc(i))p)

(17)

Emem_CP-i(l,kCP,d)=3kCPEelec+kCPEelec+EfskCP(d(l,i))p

(18)

2.2.1 簇头的选择

本协议采用MOIA搜索最优的CH与VCH，算法1所示是MOIA的主要步骤。

算法1: MOIA的主要步骤

输入：集合S中传感器的ID，位置与Eres

输出：主副簇头的ID

(1)设置免疫算法的参数；

(2)初始化种群；

(3)计算种群的目标函数值；

(4)WHILE(未达到结束条件) {

(5)gen=gen+1；

(6)pop_sel=RWS_selection(pop)；//轮盘赌选择种群

(7)pop_rep=replication(pop_sel)；//复制操作

(8)pop_clon=clone(pop_sel)；//克隆操作

(9)pop_hyper=hypermutation(pop_clon)；//高频变异

(10)pop_total=[pop_rep,pop_hyper]；//合并种群

(11)pop_off=mutation(pop_total)；//变异操作

(12)evaluate(pop_off)；//计算种群目标函数值

(13)pop=const_pop(pop,pop_off)；//建立下一代种群

(14)}

2.2.1.1 抗体种群的生成

将CH数量与其位置作为优化的目标参数，首先BS从每个虚拟网络选择剩余能量高于全网节点平均能量(Eavg)的传感器集合(S={s1,s2,…,sngen}(sngen≤N))，其中nvg(0≤nvg≤ngen/ngrids)，表示为下式

S={G1,G2,…,Gg,…,Gngrids}

(19)

式中：Gg是虚拟网格g的传感器集合，表示为

Gg={s1,s2,…,snvg}={snl|∀l∈[1Nlive]∧snl
∈Grid(g)∧Eres(l)≥Eavg}, (g=1,2,…,ngrids)

(20)

之后，BS使用二进制流将集合S内的节点编码，形成ps个抗体的种群，pop=(X1;X2;…;Xm;…;Xps)。每个CH抗体Xm为ngen个比特，每个比特(xb)对应S中一个传感器，1表示CH，0为普通节点。

2.2.1.2 种群评价函数

传感器的大部分能耗由通信引起[15]，因此每个抗体使用目标函数式(13)进行评价。

2.2.1.3 抗体选择

2.2.1.4 复制操作

2.2.1.5 高频变异的克隆扩增

2.2.1.6 变异操作

2.2.1.7 种群更新

(21)

2.2.1.8 结束条件

MOIA算法的结束条件定义为连续迭代之间种群F值变化不明显或者达到最大的迭代次数，表示为下式

pop*=

(22)

2.2.2 建立路由树

上文采用免疫算法获得了最优的簇头集，然后为每个簇头建立一个路由树，最小化簇内的能耗。本协议的目标是为每个CH选择最优的下一跳节点(NHbest)，每个CHi的NHbest应当保证连接性并节约能耗，总结为以下条件：①NH应当在其通信范围内(d(i,NHbest)≤Rr(i))；②NH应当在CHi到BS的方向上(d(NHbest,BS)

(23)

2.2.3 副簇头的选择

BS选择与各CH最近的节点作为副簇头(VCH)，簇头发生则采用VCH代替簇头，具体方法为BS发送CH_STAT_MSG(NH_ID,VCH_ID,RC)消息将节点状态从“普通节点”切换为“簇头”，VCH成为簇头之后，在其RC内广播消息Adv_Msg(CH_ID)。

2.2.4 分簇的建立

收到CH广播的消息后，普通节点发送消息Join_REQ_MEG(MN_ID)，消息包含ID及其最近的CH。如果一个节点l被多个(Lcov个)簇头覆盖，则选择最近且剩余能量较高的CH，计算方法如下

(24)

式中：d(l,i)是节点l与CHi的距离，dmaxCH是节点l与其簇头的最大距离。如果某个节点不在CH的覆盖范围内，将该节点作为新簇的簇头或加入最近的CH内。

2.2.5 数据传输阶段

传感器收到BS的消息Reqest_DATA_MSG()则唤醒成员节点采集数据，然后各节点将采集的数据及其剩余能量发送至CH。各簇使用不同的CDMA编码通信，从而降低不同簇节点间的干扰，CH收到成员节点采集的数据后，将数据重组为一个单数据包；然后，CH将总报文与成员节点的剩余能量基于路由树发送至BS。

3 仿真与结果分析

3.1 性能评价指标与实验环境

选择以下的指标评估本协议的性能[18]：①FDN：第一个死亡节点的轮数；②稳定期：网络启动到FDN的时间段；③LDN：所有节点死亡的轮数；④BEED：计算为(LDN-FDN)/LDN。

实验环境为CPU 2.7 GHz，4 GB内存，仿真平台为Matlab 2013b。为了消除实验误差，每组仿真独立地运行5次，将均值作为最终的统计结果。能量模型的参数设为：Eelec=50nJ/bit，Efs=10pJ/bit/m2，EDA=5nJ/bit/signal。参考文献[17]将MOIA的参数设为ps=30，pc=0.05，ph=10pm，Nclon=5，Maxgen=150。权重因子设为w1=0.4,w2=0.5,w3=0.1,a1=0.55,a2=0.25,a3=0.2,γ=0.6。

3.2 仿真结果

将本协议与LEACH、PCR、DCR进行比较，共设置100个异构传感节点，将各节点的初始化能量随机地初始化(范围为[1,3])，节点均匀地分布于200×200平方米的采集区域内。BS位于(100,250)米坐标处，报文大小统一为500个字节，Dth-BS值设为2Rmax，Esensing设为0.2 μJ/bit。

3.2.1α，β与Rmax的效果

为了研究α，β与Rmax这3个参数的效果，考虑两种α，β情况：(1)α=β=0，(2)α=β=0.3，然后对不同的Rmax值测试分簇的数量。图5所示是两种情况下CH数量与Rmax之间的关系，可看出第二种情况优于第一种，原因在于固定Rmax，簇的覆盖范围随α，β的增加而降低，此外，CH数量随着Rmax的增加而降低，由此说明生成的CH数量由Rmax，α，β三者决定。如果α，β固定，Rmax的增加导致Rc增加、CH下降。

图5 两种情况下CH数量与Rmax之间的关系

3.2.2 CH的分布

设置簇的数量为5，Rmax=100米，α=β=0.3。图6所示是随机地选择的30轮分布情况，可看出本协议每轮中获得的CH数量均接近5，而LEACH中CH数量变化较大，主要原因是LEACH通过随机数决定CH，同时其它3个协议将CH控制于覆盖范围Rc内。因为在MOIA算法的目标函数中考虑了能耗、未覆盖节点的比例以及CH数量，所以本协议的CH分布稳定性优于其它3种协议，每轮选择的CH数量较为稳定。

图6 随机地选择的30轮分布情况

3.2.3 稳定期与生命期

为了测试本协议对异构网络的性能，设置Rmax=100米，α=β=0.3。图7所示是4个协议的稳定期与生命期结果，可看出本协议的稳定期比LEACH、PCR、DCR分别增加了815、507、396轮，提高了总生命期。究其原因，本协议基于与BS的距离及其剩余能量决定每个节点的覆盖范围，此外，从高能量节点中选择了总能耗最低的CH组合。

图7 4个协议的稳定期与生命期结果

4 结束语

本文针对无线传感器网络分层路由协议的“热点”问题，提出基于免疫算法的非均匀分簇路由协议，该协议总体分为信息收集阶段、簇建立阶段与数据传递3个阶段。本文利用多目标免疫算法的诸多优点，对簇头的选择进行优化，将平衡全网的节点能耗，延长网络的生命期作为优化目标，获得了良好的效果。为了降低密集型网络中搜索最优CH集合的计算时间，本协议将传感区域划分为若干个虚拟网格，并选择各虚拟网络中剩余能量较高的节点建立候选传感器集，提高了协议的计算效率。多组仿真实验结果表明，本算法有效地提高了异构WSN网络与大规模WSN网络的网络生命期，并获得了理想的计算效率。

参考文献：

[1]QI Lin,HAN Yubing,ZHANG Xiaoshuan,et al.Real time monitoring system for aquatic cold-chain logistics based on WSN[J].Transactions of the Chinese Society of Agricultural Machinery,2012,43(8):134-140(in Chinese).[齐林,韩玉冰,张小栓,等.基于WSN的水产品冷链物流实时监测系统[J].农业机械学报,2012,43(8):134-140.]

[2]LIU Hongqing.Deployment of wireless sensor network nodes by particle swarm optimization algorithm based on cloud model[J].Journal of Huazhong Normal University:Nat Sci,2013,47(2):185-188(in Chinese).[刘红庆.基于云模型粒子群算法的WSN节点部署优化[J].华中师范大学学报:自然科学版,2013,47(2):185-188.]

[3]CHEN Liangyin,WANG Jinlei,ZHANG Jingyu,et al.Scheduling scheme algorithm in low-duty-cycle WSN[J].Journal of Software,2014,25(3):631-641(in Chinese).[陈良银,王金磊,张靖宇,等.低占空比WSN中一种节点休眠调度算法[J].软件学报,2014,25(3):631-641.]

[4]Malathi L,Chandrasekaran M K,Gnanamurthy R K.A novel routing protocol with lifetime maximizing clustering algorithm for WSN[C]//India Conference,2012:925-930.

[5]Mahapatra R P,Yadav R K.Descendant of LEACH based routing protocols in wireless sensor networks[C]//Procedia Computer Science,2015:1005-1014.

[6]Islam M M,Matin M A,Mondol T K.Extended stable election protocol (SEP) for three-level hierarchical clustered heterogeneous WSN[C]//Wireless Sensor Systems.IET,2012:43.

[7]Xu J,Jin N,Lou X,et al.Improvement of LEACH protocol for WSN[C]//International Conference on Fuzzy Systems and Knowledge Discovery,2012:2174-2177.

[8]DING Juan,LIU Sanyang,ZHANG Ping.A data gathering and fusion algorithm based on energy optimization for WSN[J].Application of Electronic Technique,2013,39(5):97-99(in Chinese).[丁娟,刘三阳,张平.基于能量优化的WSN数据收集和融合算法[J].电子技术应用,2013,39(5):97-99.]

[9]QIN Haisheng,HE Chuanbo,WU Wenjun,et al.Research on clustering protocol of WSN based on cell membrane optimization algorithm[J].Computer Engineering,2014(11):92-96(in Chinese).[覃海生,何传波,吴文俊,等.基于细胞膜优化算法的WSN分簇协议研究[J].计算机工程,2014,40(11):92-96.]

[10]HU Fengsong,XIAO Qiu.Multi-hop routing algorithm of energy-balancing based on LEACH[].Journal of Chinese Computer Systems,2014,35(1):70-73(in Chinese).[胡峰松,肖球.一种基于LEACH的能耗均衡多跳路由算法[J].小型微型计算机系统,2014,35(1):70-73.]

[11]Xia L,Wang G,Liu Z,et al.An energy-efficient routing protocol based on particle swarm clustering algorithm and inter-cluster routing algorithm for WSN[C]//Control and Decision Conference.IEEE,2013:4029-4033.

[12]Sabet M,Naji H R.A decentralized energy efficient hierarchical cluster-based routing algorithm for wireless sensor networks[J].AEU-International Journal of Electronics and Communications,2015,69(5):790-799.

[13]YUAN Jiaxin,ZHAO Zhen,FEI Wenli,et al.Pareto optimum control of inverter based on multi-objective immune algorithm[J].Transactions of China Electrotechnical Society,2014,29(12):33-41(in Chinese).[袁佳歆,赵震,费雯丽,等.基于免疫算法的逆变器多目标Pareto最优控制策略[J].电工技术学报,2014,29(12):33-41.]

[14]Lin Q,Zhu Q,Huang P,et al.A novel hybrid multi-objective immune algorithm with adaptive differential evolution[J].Computers & Operations Research,2015,62(C):95-111.

[15]Yao Y,Jiang N.Distributed wireless sensor network localization based on weighted search[J].Computer Networks,2015,86:57-75.

[16]Kumar R.Blending roulette wheel selection & rank selection in genetic algorithms[J].International Journal of Machine Learning and Computing,2012,2(4):365.

[17]Liang Z,Song R,Lin Q,et al.A double-module immune algorithm for multi-objective optimization problems[J].Applied Soft Computing,2015,35(C):161-174.

[18]Hari U,Ramachandran B,Johnson C.An unequally clustered multihop routing protocol for wireless sensor networks[C]//International Conference on Advances in Computing,Communications and Informatics.IEEE,2013:1007-1011.