一种基于LEACH改进的均匀分簇路由算法

邹 虹，彭国龙

（重庆邮电大学通信与信息学院，重庆 400065）

一种基于LEACH改进的均匀分簇路由算法

邹 虹，彭国龙

（重庆邮电大学通信与信息学院，重庆 400065）

针对LEACH分簇算法簇头分布位置不均匀以及节点耗能不均衡等缺点，提出一种双SINK节点均匀分簇算法DSUC。该算法首先利用无信标节点ABC定位算法，计算出每个节点的坐标位置，再根据理论得出的最佳簇头数将整个无线网络区域尽可能地划分成均等的区域，然后SINK节点通过各节点坐标选举各区域内离质心最近的节点作为第一轮簇头节点。在区域的对称位置上设置2个SINK节点，轮流交替工作，能有效解决“热区”问题。

LEACH;双SINK节点;ABC无信标节点定位;均匀分簇

经过大量国内外研究人员的努力已经在LEACH（Low Energy Adaptive Clustering Hierarchy）算法的基础上研究出很多路由改进算法。LEACH作为第一个基于分簇的路由算法，该算法采用集中式分簇方式，通过每个节点产生一个0～1的随机数，与一个设定好的门限值T（n）相比较，小于当前轮的T（n）的节点就当选为簇头，LEACH没有考虑节点的剩余能量，能量少的节点当选簇头时会快速的消耗能量，而且很有可能两个簇头相隔很近甚至是邻居节点，造成簇头节点的重叠现象［1］。文献［2］提出一种以节点剩余能量和随机数共同来控制产生T（n）的算法DCHS，该算法进一步改进解决了当所有节点的能量都变的很少时，T（n）会变小从而导致当选簇头的机率变小的问题。文献［3］中提出一种基于双簇首的路由算法，主簇首负责接收簇内节点的数据，然后再由主簇首把数据发送给副簇首进行数据融合，该算法把接收和融合的步骤分开，节省簇头选举开销，但是大量数据从主簇首到副簇首的传输耗能非常大。文献［4］中针对热区问题提出一种非均匀的分簇方式，即离SINK节点越近组成的簇越小，越远簇越大，大簇中簇内节点通过多跳与簇头通信，且远簇头通过近簇头中继和SINK节点通信，该算法确实能起到均衡能量的作用，但是算法过于复杂，控制开销较大。

本文针对LEACH算法分簇不均匀以及靠近SINK节点和远离SINK节点的簇能耗不均衡等问题提出一种基于双SINK节点均匀分簇算法DSUC（Double Sink Uniform Clustering），通过 ABC定位算法确定节点坐标，SINK节点把网络区域尽量分成均等的若干小区域，选取处于各区域质心的节点或离质心最近的节点作为簇头节点，然后簇头节点广播当选簇头信息，节点根据接收到信息的强弱来决定加入到哪个簇，双SINK以固定时间间隔轮流工作，这个算法能使能量消耗更加均衡。

1 系统模型

1.1 网络模型

本文研究的网络为一个a×a的正方形区域，2个SINK节点位于区域左右边中垂线之上，处于对称位置上，如图1所示，为了便于研究和仿真，对网络参数和节点做如下假设:

1）所有节点同构，具有数据处理融合功能，能量有限且相等，处于同一平面上。

图1 DSUC算法网络区域划分图

2）节点能通过RSSI（接收信号强度指示）来计算与邻居节点以及基站的距离，发射功率可控。

3）普通节点较均匀布置，一旦布置就不再移动。

4）双SINK节点能量无限，位于网络区域外对称位置，且有一定的距离。

1.2 无线通信耗能模型及改进算法耗能分析

DSUC算法中节点的能量消耗采用无线传输能量消耗模型计算，发送数据耗能要稍大于接收数据所需能量，通信距离大于d0采用多径衰落信道模型，小于d0则使用自由空间模型。节点发送kbit数据的耗能为

式中:k为数据比特数，d为通信的距离，Eelse为收发电路的基本功耗系数，εfs，εamp分别为自由空间和多径衰落信道模型功率放大器的能量消耗常数。

节点接收节点发送kbit数据的耗能为作为DSUC算法的中SINK节点轮流工作的时间间隔。

2 改进算法描述及实现

2.1 簇区域的划分

2.2 ABC无信标节点定位算法

信标节点是已知自身绝对位置的节点，其坐标可通过GPS、北斗卫星导航等系统确定，通过信标节点为其他节点提供参考坐标，能得到各个节点在地球上的确切位置。带信标节点定位方法虽然能较精确地定位，但由于对节点的硬件条件要求高以及GPS等导航系统接收设备的成本高等不足，而且很多情况下不需要确切的位置，所以低成本的无信标定位算法得到了较好的研究和发展［8］。

ABC定位算法是一种基于无信标定位的算法，至少知道2个节点的坐标位置，从而推知其他节点的坐标，节点发送信息包括自己的坐标、离SINK节点的距离、节点ID号等，未确定坐标的节点接收其他节点的信息，若接收到的坐标信息为空，说明该节点亦未定位，则丢弃该信息，接到2个带坐标节点的信息后就可以确实自己的坐标。在正式进行坐标计算之前，假设:设最左下角的节点为坐标原点，所有其他的节点都在原点的右上方，且各节点通过RSSI已知到SINK节点的距离。由2个节点确定第三个节点坐标时有以下3种处理情况:

1）简单舍去多余值:A，B节点坐标以及2个点到C的距离已知，求C点的坐标，根据距离关系，除了C点以外还会有一个C'点，这2个节点关于AB直线对称，C'点可能只是C点一个镜像，也有可能正好有这么一个点，如果C'点的横坐标值为负，可以简单地舍去。

2）距离判断取值:若C'点的横坐标为正值，如果真有C'这个节点且2个点的横坐标不相等，那么可以通过节点和SINK节点的距离大小来判断到底哪个横坐标是属于节点C哪个是属于C'，即距离越小，横坐标就越大，相反就越小。

3）A，B节点处于同一水平面上，因此根据距离得到的C和C'的横坐标相等，那么就说明这2个点位于SINK节点的同一个辐射圆上，那么它们距SINK节点的距离相等，因此就无法判断出到底哪个坐标是属于哪个节点了。应该避免这种情况发生，具体做法是:节点对接收到的2个坐标信息比较其纵坐标，如果相等，则要丢弃一个，重新接收一个，直到不相等为止。

建立平面直角坐标系，如图1的坐标系，拟定2个节点的坐标位置，为了使计算通用化，设A（a，b），B（c，d）两点已知，其到节点C（x，y）的距离为l1，l2，根据距离公式得到

利用坐标移位技巧，即把ABC组成的三角形整体移位，将一个节点（选接收到第一个带坐标信息的节点）移到原点，计算出C的坐标后再逆向移回。把A点移到原点，得到下面2个等式:

令m=c－a，n=d－b，解得x，y后再分别加上a，b，最终得到的x，y为

确定好所有节点的坐标位置，是选举离质心最近的簇头的关键步骤，接下来的任务就是SINK节点把区域内各节点的坐标和已确定好的质心相比较，选一个最近的节点作为簇头，因为网络刚建立阶段各节点的能量是相等的，所以可以只考虑位置信息。

2.3 簇头节点的确定

簇区域划分后，然后利用定位算法把所有节点的坐标计算出来，各节点根据分簇区域的边界值数据，确定自己属于哪个簇区域，SINK节点再把各区域的质心确定出来，然后SINK节点将各个区域的质心坐标和区域内的节点依次比较，得到一个离质心最近的一个节点作为簇头，这样就完成了簇头节点的第一轮选举，接下来的第二轮、第三轮……，DSUC算法将由本轮簇头通过节点剩余能量以及离簇头节点的距离参数进行下轮簇头的选举。改进算法簇头选举经过划分均等区域、节点定位、簇头选举等过程，为了便于理解，画出算法簇头选举流程图如图2所示。

图2 簇头选举流程图

2.4 簇形成及数据传输

簇头选举好之后，簇头以区域半径广播当选信息给周围节点，节点根据接收信号强度决定加入哪个簇，边界上的节点存在竞争现象，可能加入其他簇中，数据传输采用和传统的LEACH相同传输方法，即簇头节点直接和SINK节点通信，簇内节点在自己的TDMA时隙单跳内发送数据给簇头节点，在其他节点时隙处于睡眠状态。

3 实验仿真及分析

本文采用NS2网络仿真工具进行仿真，对LEACH算法和DSUC算法进行性能比较，主要分析在单个SINK节点以及双个SINK节点下2个算法第一个节点死亡的时间和最后一个节点死亡时间，以及网络总能量的消耗等信息。

3.1 仿真场景及参数设置

3.2 仿真结果分析

图3对LEACH协议、DSUC协议下单个SINK节点情况和双SINK节点情况分别进行仿真，得出存活节点个数与仿真轮数的关系，从图中可以看出LEACH在300轮左右的时候就出现了第一个节点死亡，而单个SINK节点的改进算法第一个节点死亡出现在350轮左右的时候，有一定的提高，但双SINK节点的改进算法仿真到640轮的时候第一个节点才死亡，大大延长了网络的寿命，比LEACH第一个节点死亡延长一倍多，这是因为DSUC算法簇头选举不但参考了剩余能量，还使用了双SINK节点均衡节能解决了热区问题，之所以和理论有差别是因为SINK节点之间交替工作会产生额外的能量消耗，单SINK节点下的改进算法也比LEACH的时间延长了16%，当LEACH算法和单SINK节点的改进算法结束网络生命期时，DSUC算法还剩余100多个可用节点，可以看到LEACH节点的个数死亡的速度最快，单SINK节点的改进算法次之，双SINK节点下的DSUC算法下降最平缓。

图3 剩余节点个数随轮数变化的关系

图4是网络中整个网络消耗能量的多少和仿真轮数的变化关系，在仿真的开始发现DSUC算法单SINK节点和双SINK节点两种情况下耗能都要比LEACH算法稍多，这是因为初始化阶段改进算法要进行区域的划分及节点的定位会消耗少部分能量，随着仿真时间的延长，改进算法单SINK节点相对于LEACH有一定改善，这是因为采用最佳分簇数进行均匀分簇，从而缩短了通信距离，但是不能解决“热区问题”，因此在500轮之后，改进算法的双SINK节点情况优势越来越明显，这主要是因为采用双SINK节点使得簇头发送给SINK节点的平均距离减少，有效解决了“热区问题”，消耗的能量也减少了，相比后面延长网络寿命的功劳，DSUC算法初始化阶段所消耗的能量代价是值得的。将图3和图4相比较，当运行到1 800轮左右时，剩余节点的个数100多个，剩余能量应小于50 J，因为这100个节点运行时也要消耗能量，而从图4中的结果正好验证了理论的正确性，运行到1 600轮的时候能量就已经消耗了60 J了，说明剩余节点剩余的能量为节点初始能量的4/5左右。

图4 网络能量的消耗随轮数的变化

4 结束语

本文对LEACH算法进行了改进，提出了一种分簇均匀更加节能的路由协议，采用信标节点定位算法确定所有节点的位置，从而确定簇头节点的位置，达到均匀分簇，其次是采用双SINK节点均衡能量。该算法虽然能有效搞高网络寿命等性能，但也存在些许不足，比如定位以及仿真模型都定位在一个正方形的规则图形之内，现实中传感器的网络布置区域很少会有这个规则，因此如何计算不规则区域的节点坐标和簇区域的划分将是本课题下一步所要研究的内容。

:

［1］孙利民，李建中.无线传感器网络［M］.北京:清华大学出版社，2005.

［2］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，29（9）:57-60.

［3］李辉，李腊元，李方云.一种基于低能量的双簇首WSN路由算法［J］.武汉理工大学学报，2009，33（3）:450-453.

［4］吴振华，尹志军.基于优化簇半径的WSNs非均匀分簇路由［J］.计算机工程与设计，2010，31（15）:3374-3378.

［5］钟智，樊晓平，罗大庸，等.一种基于网格的无线传感器网络分簇路由协议研究［J］.传感器与微系统，2011，30（12）:18-20.

［6］HEINZELMAN W R，KULIK J，BALAKRISHNAN H.Adaptive protocols for information dissemination in wireless sensor networks［EB/OL］.［2012-06-20］.http://nms.1cs.mit.edu/papers/spin-mobicom99.html.

［7］何国圆，陈涤.基于最优簇首的高能效传感器网络路由协议［J］.传感器技术学报，2008，21（10）:1739-1743.

［8］黄小军，郑霖.无线传感器网络物理层的主从同步技术研究［J］.电视技术，2011，35（11）:92-94.

Improved Uniform Clustering Routing Algorithm Based on LEACH

ZOU Hong，PENG Guolong

（Communication and Information Sciences，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

In order to solve the problems that the position of cluster nodes distribute uneven and the nodes energy consumption imbalance，a uniform clustering algorithm with double SINK nodes（DSUC）is proposed.This algorithm includes three steps.Firstly，the no beacon node positioning algorithm ABC is used to calculating coordinate for each node.Then，according to the optimal cluster head nodes from survey papers，the entire wireless area divided into several small areas as much as possible the measure of each area is equal.Finally，the SINK node chose the node which is closest to the centroid of each small area as cluster head node in first round.In the region of the symmetric position two SINK nodes are set down，the two SINK nodes can effectively solve the problem of unbalanced energy consumption by work alternate.

LEACH;double SINK nodes;no beacon node positioning algorithm ABC;uniform clustering

TP393

A

【本文献信息】邹虹，彭国龙.一种基于LEACH改进的均匀分簇路由算法［J］.电视技术，2013，37（3）.

国家自然科学基金项目（61171190）

彭国龙（1985— ），硕士生，主研无线传感器网络;

邹 虹（1970— ），女，副教授，硕士生导师，主研移动通信和无线传感器网络。

责任编辑:任健男

2012－09－20