WSN中一种改进的基于LEACH—C算法的簇间路由算法

【 摘 要 】 在WSN（Wireless Senor Network，无线传感器网络）中的分级路由算法中，如果簇头仅仅能够进行单跳通信或者多跳通信，都会造成网络负载不均衡以及簇头能量消耗过快的问题出现。针对这一问题，文章提出了一种改进的基于LEACH-C（Low Energy Adaptive Clustering Hierarchy Centralized，低功耗自适应集中分层型）算法的簇间路由（Cluster Routing based on LEACH-C Algorithm，简称CRLA）算法。该算法通过距离阀值来控制簇头是进行单挑通信还是多跳通信。仿真分析表明，CRLA算法能够实现网络负载的均衡以及减少簇头能量的消耗，从而实现网络生存时间的延长。
　　【 关键词 】 分级路由算法；无线传感器网络；簇；LEACH-C；阀值
　　1 引言
　　WSN是由众多的无线传感器节点所组成的无线网络，而这些节点以自组织的形式来实现对WSN覆盖范围内的感知对象信息的采集与处理，并将所得到的结果传递给所需用户。由于传感器节点的通信能力、存储能力与处理能力都十分的有限，并且有些节点的能源也是有限的，因此，WSN所使用的路由算法的性能直接关系到整个网络的性能。
　　而WSN常使用的路由算法可以分成两类：分级路由算法与平面路由算法。与平面路由算法相比，分级路由算法不仅具有更好的扩展性以及更易于管理与维护的优势，能够更好地均衡网络负载，减少节点的能量消耗，从而增加了网络的生存时间。正是由于分级路由算法的这些优点，使其得到了广泛地关注与应用。分级路由算法使用分簇算法将网络分成多个层次，即网络被分割成多个簇，每个簇由一个簇头与若干个簇内节点所构成。目前，比较常用的分级路由算法有TEEN路由算法、LEACH算法、LEACH-C算法、PEGASIS（Power-Efficient Gathering in Sensor Information Systems）路由算法等。
　　在分级路由算法中，簇头与汇聚节点的通信方式有两种：单跳通信与多跳通信。当采用单跳通信的方式时，簇头的网络负荷随簇头和汇聚节点的距离的增大而增大，造成离汇聚节点较远的簇头的网络负荷过重。而采用多跳通信的方式时，离汇聚节点较近的簇头除了需要发送本簇内的数据外，还需要转发其他簇的数据，造成网络负载的不均衡以及能量的大量消耗。针对单一的通信方式所存在的问题，本文提出了一种改进的基于LEACH-C的簇间路由（Cluster Routing based on LEACH-C Algorithm， 简称CRLA）算法。该算法通过距离阀值来控制簇头是进行单挑通信还是多跳通信。
　　2 LEACH-C算法
　　2.1 原理
　　LEACH-C算法是一种集中控制的分级路由算法，汇聚节点利用该算法来进行簇的划分以及簇头的选择，来实现网络负载的均衡。而使用该算法的前提讲条件：（1）网络中全部的节点都可以直接与汇聚节点进行通信；（2）网络中的全部节点都能够对自身的发射功率进行控制与调整。
　　在LEACH-C算法中，一个完整的通信过程被称为一“轮”。而每一轮又包含簇的建立阶段与数据传输阶段。在簇的建立阶段，汇聚节点首先会搜集网络中全部节点的地理位置与剩余能量信息，接着计算出整个网络的剩余能量的平均值，剩余能量大于平均值的节点构成备选簇头集；然后，LEACH-C算法以目标函数（目标函数的计算方法：簇头与簇内节点距离的平方和，其值越小则说明通信过程所消耗的能量越少。）最小为原则，利用模拟退火法从备选簇头集中找出簇头集，并将簇头集信息广播给所有的网内节点；而当网内节点收到簇头集时，首先会判断自身是否包含在该集合中，如果在其中，则当选为簇头，否则，该节点根据离簇头集中簇头距离的远近来判断自己加入距离最近的簇头所在的簇。最后，簇头为簇内的所有节点分配相应的传输时隙。
　　在数据传输阶段，为了保证簇内节点与簇头的通信互不干扰，簇内节点只能在所分配的时隙内向簇头发送数据，其它时间则处在休眠状态，而簇头将所接收到的所有数据进行处理，然后将处理后的数据直接发送给汇聚节点。经过一段时间的数传后，网络开始新的一轮，即重新进行簇的建立与数据传输。
　　2.2 能量消耗模型
　　LEACH-C算法所采用的能量模型为一阶无线电模型，它的前提条件为：（1）网内所有的节点都是能量受限并且其初始能量是一样的；（2）无线信号的损耗无方向性；（3）汇聚节点位置不变，并且其离WSN有一定的距离。
　　那么，发送数据所需花费的能量Etx（k，d）：
　　Etx（k，d）=Etx*k+α*k*dβ （1）
　　式中，k与d分别是发送数据的bit数与收发节点的距离，α为信号放大倍数，Etx为传输1bit数据发送电路所消耗的能量。dβ表示信号的衰减情况。
　　而接收数据所消耗的能量Erx（k）：
　　Erx（k）=Erx*k （2）
　　式中，Erx为接收1bit数据所消耗的能量。
　　为了便于分析，假设Erx=Etx，β=2，并且簇头把信息传给汇聚节点需要经过m-1跳，并且每跳的距离都为l，则在单跳通信的方式下，所消耗的总能量为：
　　Esingle=Etx*k+α*k*（m*l）2 （3）
　　而在多跳通信的方式下，所消耗的总能量为：
　　Emul=m*（Etx*k+α*k*（m*l）2 ）+ （m-1）*Etx*k （4）
　　3 CRLA算法
　　在CRLA算法中，当簇头与汇聚节点的距离小于阀值threshold时，簇头采用单跳通信方式与汇聚节点进行通信；而当簇头与汇聚节点的距离大于threshold时，则采用多跳通信方式。而在进行多跳通信时，假设与汇聚节点的距离大于threshold的簇头数目是n，且每个簇头除了包含自身的地理位置Di（xi，yi），其与汇聚节点的距离HBi，还包括其它簇头的信息Hi，以及这些簇头与汇聚节点的距离信息HDi。
　CRLA算法在进行多跳通信时，路由的建立过程为：首先，选取离汇聚节点最近的簇头，即选择{HB1，HB2，…}值最小的簇头，假设为j，接着选取HDj值最小的簇头k作为下一跳的节点，然后选取HDk值最小的簇头m作为下一跳的节点，以此类推，直到遍历所有的与汇聚节点距离大于threshold的簇头，最后得到所有簇头到汇聚节点的最短路径。
　　4 仿真分析
　　为了来验证CRLA算法的性能，本文从网络总耗能与剩余存活节点数两个方面对CRLA算法与LEACH-C算法中的单跳路由算法与多跳路由算法进行比较。
　　假设汇聚节点位 于（50，120）的位置设100个节点在100m×100m的区域，每个节点的初始能量都为1J，同时假设Etx=Trx=100nJ，α=100pJ，根据公式（3）与（4）可以得到threshold的值为40m。
　　如图1所示，给出了剩余节点数随轮数的变化情况。从图1中可以看出，在单跳路由算法下，网络中的最后一个节点在第26轮耗尽能量。在多跳路由算法下，网络中的最后一个节点在第28轮耗尽能量。而在CRLA算法下，网络中的最后一个节点在第30轮才耗尽能量，由此可见，CRLA算法能够有效地延长网络的存活时间。同时，从图1中还可以看出，CRLA算法下的剩余存活节点数在前期变化比较缓慢，而在后期出现了急剧下降，这是因为CRLA算法能够较好地均衡网络负载，避免了节点负载过重，能量消耗过快现象的出现。
　　图2给出了网络总能耗随轮数的变化情况。从图2中可以看出，在CRLA算法，网络的生存时间最长。
　　5 结束论
　　在WSN的分级路由算法中，如果簇头仅仅能够进行单跳通信或者多跳通信，都会造成网络负载不均衡以及簇头能量消耗过快。针对这一问题，本文提出了一种改进的基于LEACH-C算法的簇间路由算法CRLA。该算法通过距离阀值来控制簇头是进行单跳通信还是多跳通信。仿真分析表明，CRLA算法能够实现网络负载的均衡以及减少簇头能量的消耗，来延长网络生存时间。但CRLA算法是基于LEACH-C算法的，因此CRLA算法仍然是一种集中控制算法，使其只适用于规模比较小的网络，限制了该算法的使用范围。
　　参考文献
　　. 2004-5-28.
　　[2] 沈波， 张世永， 钟亦平. 无线传感器网络分簇路由协议[J].软件学报， 2006， 17（7）： 1588-1600.
　　.计算机工程， 2012， 38（14）： 79-81.
　　[4] 刘铁流， 巫咏群. 一种新的基于分簇的无线传感器网络多跳节能路由协议[J].信息与控制， 2012， 41（1）： 27-32.
　　[5] 佘静涛， 胡同森， 钟明霞. 无线传感器网络路由协议 LEACH 的研究与改进 [J].计算机系统应用， 2009，（2）： 67-72.
　　作者简介：
　　付垚（1978-），女，山东德州人，研究生在读，实验师；主要研究方向和关注领域：移动无线组网技术。