一种基于混沌策略的无线传感器网络分簇路由协议

徐兴东

(中南民族大学计算与实验中心，湖北武汉430074)

无线传感器网络(WSN)是由具有传感、数据处理和短距离无线通信等功能的传感器组成 .WSN是一种新型的无基础设施的无线网络，能够协作地实时监测、感知和采集各种环境或监测对象的信息，并对其进行处理，通过无线通信方式把信息传送到信息汇聚点［1］.随着国内外无线传感器网络的研究发展，已有许多用于无线传感器网络的路由协议.从网络的拓扑结构看可以分为两类［2］:平面路由协议和分簇路由协议 .在平面路由协议中，所有节点的地位是平等的，不存在等级和层次的差异 .平面路由协议的优点是简单、具有良好的健壮性，缺点是可扩展性差;在分簇路由协议中，簇头主要负责数据融合和将融合后的数据转发到基站.通过约定的协议，在整个网络覆盖范围内选举出一定数量的节点作为簇首，从而将网络划分为簇，它具有路由选择、资源管理以及数据融合等功能.分簇路由协议是目前公认的最有效的组织方式.

LEACH协议__［3］是由Heinzelman等人在2000年提出的一种低功耗自适应分簇路由协议.该算法的基本思想是:通过等概率的随机循环选择簇头节点，然后簇头收集簇内节点数据并融合，并将整个网络的能量负载均衡分配到每个传感器节点中，从而高效地使用传感器节点有限的能量，降低网络能量耗费，最大化网络的生命周期［4］.LEACH在簇头选举时缺乏对节点当前剩余能量的考虑，单纯地采用随机方式选择簇头，容易出现“能量空洞”现象 .LEACH这种选举簇头的随机性也会造成簇头在网络中的位置分布不佳，当簇头位置比较集中时，簇的覆盖区域将出现部分重叠的现象，还会造成簇头之间的无线信号干扰;当簇头分布在边缘区域时，簇内的某些成员节点到簇头的距离会变大，相应簇的能量开销也变大.混沌是非线性系统独有的一种运动形式，混沌运动具有遍历性、随机性、规律性等特点，能在一定范围内按其自身的规律不重复地遍历所有状态.混沌优化是一种新型搜索算法，它直接采用混沌变量对解空间进行搜索，具有对初值敏感、易于跳出局部最优解、搜索速度快和全局渐近收敛的特点，被广泛用于非线性优化领域［5］.

本文在LEACH协议基础上，利用混沌优化的遍历性等优点，将混沌搜索机制引入到分簇路由协议中，并提出了一种新的无线传感器节能算法——混沌LEACH协议(CLEACH).CLEACH协议结合了LEACH和混沌优化的优点，选择采用 LEACH中的使每个区域的节点数目大致相同，然后，在同一区域中选取簇头时采用 LEACH的簇头选择机制 .仿真实验表明:该路由协议能使簇头能量消耗更均衡，并且能有效延长WSN的寿命.

1 研究现状

目前，国内外已出现大量的分簇路由协议，从不同的角度来延长传感器网络的寿命 .文献［6］提出M-LEACH协议是一种多跳LEACH算法.该协议簇内的节点不再是以单跳的方式传输数据到簇头，而是通过簇内其他节点转发 .文献［7］在LEACH和PEGASIS算法基础上，提出了一种改进的有效路由LEACH-P算法.LEACH-P算法不仅改善了LEACH算法在大规模传感器网络中簇头节点能量消耗过大的问题，而且克服了PEGASIS算法在大规模传感器网络中实时性差的问题.为有效解决无线传感器网络中的“热区”问题，文献［8］提出了一种能量自适应的非均匀分簇路由协议.该协议采取非均匀的分簇结构，使靠近基站的簇范围减小到合理的范围 .文献［9］提出 EEUC算法利用非均匀的竞争半径，使得靠近汇聚点的簇的成员数目相对较小，从而簇头能够节约能量以供数据转发使用，达到均衡簇头能量消耗的目的.此外，在簇头选择其他节点时，不仅考虑候选节点相对汇聚点的位置，还应考虑候选节点的剩余能量.不同于LEACH，EEUC簇头通过局部竞争的方式产生，同时簇头间进行多跳数据转发.SAR协议通过构建以sink的单跳邻居节点为根节点的多播树实现传感器节点到vsink的多跳路径.它的特点是路由决策不仅要考虑到每条路径的能源，还要涉及端到端的延迟需求和待发送数据包的优先级［10］.SPIN路由算法的目标是通过使用节点间的协商制度和资源自适应机制，解决传统泛洪法存在的不足之处［11］.EARSN是基于3层体系结构的路由协议 .该协议将网络运行前由终端用户sink将传感器节点划分成簇，并通知每个簇首节点的ID标识和簇内所分配节点的位置信息［12］.在文献［13］中，卫琪等介绍和分析了 LEACH，PEGASIS和HEED 3种典型节能分簇路由协议，并通过对三者的综合比较总结出现有分簇路由协议存在的问题，并提出相应的解决思路.这里，主要分析与本文直接相关的LEACH协议.

在LEACH协议中，每个传感节点都有机会充当簇头节点，簇头节点进行轮换，以达到分散各节点能量消耗目的.簇头节点的选择主要依据网络中所需要的簇头节点总数和迄今为止每个节点已成为簇头节点的次数来判定.每个传感器节点在0～1之间随机选择一个数，如果选择的数小于规定阀值T(n)，那么该节点就成为簇头节点，并通过广播告知整个网络.网络中的每个非簇头节点根据收到信号的强度选择要加入的簇，并通知相应的簇头节点，自己则成为簇内组员.T(n)的计算公式如下:

其中，p表示在无线网络中簇头节点所占的百分比，r表示当前循环次数，G是在前1/p轮中未充当过簇头节点的集合.

LEACH协议通过设置T(n)值，以保证每个节点在1/p轮内都有机会充当一次簇头节点，从而平衡了节点的能量消耗 .LEACH协议提出后使得无线传感器网络性能得到很大的改善 .但是LEACH算法也存在许多不足，在刚开始假设每个节点的初始能量相同，在现实环境中很难做到;LEACH算法是随机选择一部分节点担任簇首，每个节点成为簇首节点的概率相同，这样可能导致一些高能量节点没机会成为簇首节点，而一些低能量节点成为簇首节点.一旦这些低能量节点成为簇首节点，将会很快耗尽其能量.虽然降低了算法的复杂度，却可能导致簇首都聚集在网络的一角，此时大量节点都需与距离较远的簇首通信，这样会使这些节点负载过重而较早死亡;簇首节点在通信过程中采用单跳与基站通信，这样就会导致较远的簇首节点能量消耗过大，而过早死亡，影响整个网络的性能 .由于LEACH协议假定所有节点能够与汇聚节点直接通信，并且每个节点都具备支持不同MAC协议的计算能力，因此该方法不适合在大规模的无线传感器网络中应用.

2 CLEACH路由算法

混沌优化算法的基本思想是将混沌状态引入到优化变量中，并把混沌运动的遍历范围“放大”到优化变量的取值空间，然后利用混沌变量搜索.我们利用Logistic混沌映射，即:

g:βk=αβk－1(1－βk－1)，βk∈［0，1］，k=1，2，… .其中，α为吸引子，当α=4时，Logistic混沌映射为满映射，系统处于完全混沌状态.我们利用混沌变量对初值的敏感性，赋n个微小差异的初值，得到n个混沌变量，并将它们作为CLEACH算法的初始种群.

CLEACH路由算法的流程如下:

(1)初始化控制参数.随机选取m个长度为1的二进制位串为初值，混沌迭代次数g=1，混沌扰动概率p，混沌吸引子α.

(2)计算种群P(g)中每个个体的适应度值.

(3)对种群P(g)进行选择操作，将适应度较大的个体保留到下一代，得到新的群体P'(g).

(4)对群体P'(g)中的个体进行混沌扰动操作.以混沌扰动概率p选取要进行混沌扰动的个体的每一个分量.设xi对应取值范围是［ai，bi］，那么经过混沌扰动操作后，xi=ai+α(bi－ai)βk(1－βk)，其中，βk是Logistic混沌映射为混沌初始值.经过混沌扰动操作后，得到下一代群体P(g+1).

(5)当g≥500时，算法自然结束，输出最优解;否则，g=g+1，返回到步骤(2).

3 仿真实验与结果分析

本文用Matlab对CLEACH路由协议进行仿真测试.选择节点分布在200m×200m的区域内，节点数N=200，基站位于(0，0)处 .每个节点的初始能量为0.5J，数据包大小为4000bit.

图1、2表示的是实验仿真结果 .从图1中不难看出，CLEACH路由协议中的第一个节点死亡的时间大概是900轮，LEACH和M-LEACH路由协议中的第一个节点死亡的时间分别是600轮和800轮，由此可见，CLEACH路由协议延长了第一个节点的死亡时间.图2表示的是在CLEACH路由协议和LEACH路由协议中簇头能量消耗 .CLEACH远低于LEACH.因为在LEACH协议中，簇头采用单跳通信将数据发往基站，同时由于簇头数目不稳定，导致簇头能耗消耗增大.而CLEACH采用多跳通信，节省了很多能量 .在 CLEACH中为候选节点设置一个等待时间，使它们按照次序传送报文 .在传播的过程中，同时完成簇的建立以及簇间通信，CLEACH协议的这个过程花费的开销也很低.

图1 轮数与存活的节点数比较Fig.1 Compare of the number of rounds and nodes alive

图2 基站收到的数据量比较Fig.2 Compare of the amount of data received by the base station

4 结语

无线传感器网络的路由协议是无线传感器网络研究中的热点和焦点问题.本文采用CLEACH路由算法，减小簇间多跳能量的消耗，从而延长了网络的生存时间.CLEACH协议从候选节点根据各自的等待时间按照一定的次序发送广播报文来竞争簇头，簇头选出后普通节点根据最近的簇头加入簇，为了进一步减少能量消耗和维持节点能量均衡，远离基站的簇头.实验结果表明:CLEACH协议通过多跳的方式经过其他簇头，将收集的数据传送到基站，从而有效提高网络性能.

［1］Younis M，YoussefM，Arisha K.Energy aware routing in cluster-based sensor networks［C］//The 10th IEEE International Symposium on Modeling Analysis and Simulation of Computer and Telecommunications Systems.Beijing:IEEE，2002:129-136.

［2］沈 波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1588-1600.

［3］Fan Yiming，Yu Jianjun.The communication protocol for wireless sensor network about LEACH［C］//CISW.Proceedings of 2007 International Conference on Computation Intelligence and Security Workshops.Mexico:CISW，2007:550-553.

［4］Cardei M，Wu J.Energy-efficient coverage problems in wireless Ad Hoc sensor networks ［J］.Computer Communications，2006，29(4):413-420.

［5］李 磊，滕春贤.一类两层多目标决策的全局优化方法［J］.哈尔滨理工大学学报，200l，6(6):25-28.

［6］Heinzelman W R，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless micro sensor networks［J］.IEEE Transactions on Wireless Networking，2002，1(4):660-670.

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

［8］李树华，刘振宇，李迎秋.能量自适应的无线传感器网络分簇路由协议［J］.计算机工程与设计，2010，31(3):504-507.

［9］李成法，陈贵海.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):88-91.

［10］吴 迪，胡 钢.无线传感器网络多路径簇头链分簇式路由算法［J］.计算机工程与科学，2008，30(6):101-105.

［11］SohrabiK，Gao J，Ailawadhi V，etal，Protocols for selforganization of a wireless sensor network［J］.IEEE Personal Communications，2000，5(7):16-27.

［12］Kulik J，Heinzelman W R，Balakrishnan H.Negotiation based protocols for disseminating information in wireless sensor networks［J］. Wireless Networks，2002，8(223):169-185.

［13］卫 琪，马 礼.无线传感器网络节能路由研究［J］.工业控制计算机，2011，24(2):1-3.