节点分布不均匀的无线传感网络低功耗算法

张双双，王延年

（西安工程大学 电子信息学院，陕西 西安710048）

0 引 言

无线传感网络（Wireless Sensor Network，简称WSN）的目的是收集和处理目标检测区域内被感知对象的相关信息，并将处理过的信息传送至基站［1］.WSN中的节点在自身能量有限的条件下，要不断获取信息并传送给基站，这样就必须考虑节点的能量消耗问题.要延长WSN的网络生命周期就必须尽量降低节点功耗［2］.

目前，针对无线传感网络节点能量、储存能力和计算能力有限的特点，学者们提出了很多适合无线传感器网络的路由算法［3-5］.分层路由主要包括低功耗自适应分簇路由算法（LEACH）和门限敏感高效能耗传感网络算法（TEEN）［6］.TEEN算法通过合理的设置硬门限和软门限，仅仅传输用户感兴趣的信息，从而可以有效地降低系统的能耗［7］.LEACH路由算法是具有代表性的层次路由，该算法采用轮概念，在每一轮数据采集过程中随机选举簇首，使网络节点都有机会分担通讯任务.但是，LEACH算法存在一些不足：无线传感器节点数目大且分布不均匀，从而导致簇首节点负载不均衡，并且长距离的数据传输会加速一些远距离节点的死亡，缩短网络生存时间.

本文针对经典的LEACH算法存在的不足，提出了一种改进的LEACH算法.通过对传统的簇首随机选择机制进行改进，将节点的剩余能量考虑在内，这样就可以尽量避免低能量的节点成为簇首；并且在簇间构造多跳通信路径，这样可以降低网络能量消耗，延长网络生存周期.

1 无线传感网络路由协议

1.1 LEACH算法

LEACH协议采用分布式成簇技术，因此，簇头节点在整个网络中的作用很重要.

LEACH分为初始化阶段和稳定阶段两个阶段.在初始化阶段，传感器节点选择一个［0，1］之间的随机数.如果这个随机数比门限T（n）要小，它就被选为簇头.T（n）的计算公式［8］为

其中，P为节点中成为簇头的百分比；r为目前轮数；G为过去1／P轮中没有被选中为簇头的节点集.

簇头被选出来之后，它们就会通知网络中的所有节点.一旦节点接收到簇头的通知，节点就会根据与簇头之间通信的强弱来选择它要加入的分组，并通知簇头它将成为该管辖区内的成员.然后，簇头通过时分复用的方式为每个成员分配通信的时隙.在稳定阶段，节点根据时隙表中分配的时间发送数据，其余时间内都处于休眠状态［9-10］.簇头将自己区域内所有节点的数据进行汇集，然后发送给基站.持续一段时间后，整个网络进入下一轮的工作周期，重新选择簇头.

无线传感网络LEACH算法中，簇首的选取依靠随机数与阀值的比较，具有很大的随机性，使得部分簇首相距过近或部分簇首距离基站过远，以及每个簇中节点数目分布不均匀，这样就会加重个别簇首的负担，降低网络的负载平衡程度.另外，没有考虑节点的剩余能量，如果剩余能量过低的节点当选为簇首时，就会加速该节点的死亡，影响整个网络的生命周期.

1.2 能量消耗模型

2 LEACH算法改进

本文对经典的LEACH算法进行改进，在LEACH算法计算公式中，并没有考虑各个节点的剩余能量，要想每个节点消耗的能量值相等，必须网络中所有节点初始能量都相等，并且保证网络任何一个簇首在向基站传输数据的过程中消耗的能量一样.这样就必须要求每个簇的大小相同，距离基站的距离相同.显然，是不符合实际情况的，这必然导致网络能量分布不均匀的情况.

2.1 簇首选择

如式（4）所示，在簇头选举的过程中考虑到节点当前的剩余能量，所有节点必须监控各自的能量变化情况，若能量低于平均能量水平，降低其成为簇首的概率，以保证每轮中能够选举出剩余能量较多的节点为簇首节点.

其中，Ecur为第r轮开始时节点剩余的能量；Eave为第r轮节点的平均能量.

2.2 簇的形成

当节点当选为簇首之后，每个簇首用非持续CSMA（carrier-sense multiple access）MAC以相同的传输能量向剩余节点广播自己成为簇首的消息，此消息称为ADV，此消息包括簇首节点的ID号和包头标示，其他节点接收到簇首的ADV消息，在一定的时间内可以接收到多个ADV消息，然后根据接收到的ADV消息强度来决定加入离自己最近的那个簇.节点发送加入簇的JOIN请求信息，此消息包括节点的ID号和簇首的ID号［12］.簇首接收到所有JOIN请求信息之后，根据成员节点的数目，簇头为簇内每个节点分配TDMA时间表，并用广播的形式发送到簇内所有的节点，这就可以保证簇内的每个节点只在相应的时隙内进行数据传输，而在其他时间内进入休眠状态，从而减小了能量的消耗.每个节点得到自己的时隙表消息后，无线传感网络就进入了数据传输阶段.

2.3 数据传输阶段

无线传感器网络节点在完成簇的形成之后，需要各个簇与Sink节点进行通信.对LEACH簇间通信方式进行改进，利用Prim算法在簇头之间构造最小生成树，采用多跳路的通信方式，减少簇头和sink节点之间直接通信所消耗的能量.

（1）在进行Prim算法时，首先选择一个簇头作为起始点，选择簇头的当前能量剩余状况和它到基站的距离作为参考值，两个参考值的关系Pi［13］：

其中，Ecurrent为当前节点剩余能量；lBE为簇头节点距离基站的距离.比较Pi值的大小，选用最大的Pi值作为多跳的起始点，也就是最小生成树的顶点.

（2）以簇头之间的通信距离作为路径权值，选择权值最小的簇头作为下一跳的子节点.

（3）继续寻找该子节点的下一跳：选择权值最优的节点成为它的下一跳，找到的下一跳节点作为它的子节点，依次执行下去.

在树形路由建立以后，簇首节点将融合处理后的数据沿着多跳树形方向向该簇头的父节点传输，最后，起始节点把数据发送至基站.

在无线传感器网络中，基站一般都远离信息采集区域，而我们知道信号传输距离越短，能量消耗越少，所以利用最小生成树算法选取的最优多跳路径可以减少因为距离而产生的能量消耗.

3 仿真与讨论

本文使用Matlab仿真工具对改进好的算法进行仿真实验.在100m×100m的范围内，随机部署了100个传感器节点.节点分布如图1所示，每个节点的初始能量为2J；每个节点在每轮数据传输阶段传输的数据位100bit；最大运行轮数r为1 500.

图2为节点存活个数与网络生存时间的关系图.在同样网络初始条件下对LEACH算法和改进后的算法进行了仿真实验，比较两者网络生存时间.从图2可以看出，LEACH网络中出现第一个死亡节点在250轮左右，而改进后的网络中出现第一个死亡节点是在接近于500轮，使网络的生命周期延长了将近1倍.在1 000轮左右时，LEACH算法的节点已经全部死亡，改进算法节点的存活率仍然将近80%.这是由于改进算法在簇头选举过程中考虑到节点的剩余能量，避免了剩余能量过低的节点被选作为簇头节点.并且改进后的算法在簇头与基站的通信过程中，簇头节点并不直接与基站进行数据传输，而是采用多跳路的通信方式，由能量的消耗公式可知，通信距离的远近对节点能量的消耗有很大的影响，多跳路的通信方式就大大减少了远距离数据传输对节点能量的消耗.说明改进后的算法不但能进一步降低网络的能量消耗，有效地延长了网络的生命周期，还使得整个网络能量分布更加均衡.

图1 节点分布图

图2 网络生存时间图

4 结束语

本文对经典LEACH路由算法进行改进，提出一种改进的分簇路由算法.改进的分簇路由算法考虑到节点的剩余能量，并且在数据传输的过程中采用多跳路的通讯方式，减少了节点能量，特别是簇头节点的能量消耗，从而延长网络生存时间，能够很好地改善无线传感网络的能量负载平衡问题.

［1］ 牛瑛琦.无线传感器网络低功耗路由算法研究与仿真实现［D］.北京：北京邮电大学，2013：12-18.NIU Yingqi.Research and simulation on a low-power cluster routing algorithm for wireless sensor networks［D］.Beijing：Beijing University of Posts and Telecommunications，2013：12-18.

［2］ 宋杭选，李儒，牛斗.无线传感器网络低功耗分簇路由算法研究［J］.单片机与嵌入式系统应用，2009（3）：17-19.SONG Hangxuan.LI Ru，NIU Dou.Research on a low-power cluster routing algorithm for wireless sensor networks［J］.Microcontrollers &Embedded Systems，2009（3）：17-19.

［3］ 宋旭文，李晓伟，沈冬冬，等.一种低功耗的多跳无线传感网时间同步算法［J］.电子科技，2014，27（4）：9-11.SONG Xuwen，LI Xiaowei，SHEN Dongdong，et al.A low power time synchronization algorithm for the multi-hop wireless sensor networks［J］.Electronic Science and Technology，2014，27（4）：9-11.

［4］ 郭振格.无线传感网络中低功耗协议的优化策略研究［D］.秦皇岛：燕山大学，2011：16-18.GUO Zhenge.Optimization strategies for low-power protocols based on wireless sensor networks protocols［D］.Qinhuangdao：Yanshan University，2011：16-18.

［5］ SINGH M，SETHI M.A Tree based routing protocol for mobile sensor networks（MSNs）［J］.International Journal on Computer Science and Engineering，2010，2（SI）：55-60.

［6］ 王璨，骆坚，张大方，等.一种基于移动性的无线传感器网络分簇路由协议［J］.计算机工程与科学，2012，34（3）：6-12.WANG Can，LUO Jian，ZHANG Dafang，et al.A mobility-based cluster routing protocol for mobile wireless sensor networks［J］.Computer Eenineering &Science，2012，34（3）：6-12.

［7］ 张源.一种 TEEN协议的节能型改进算法［J］.现代计算机，2009（5）：61-64.ZHANG Yuan.An improved energy-saving algorithm based on TEEN［J］.Modern Computer，2009（5）：61-64.

［8］ 陶骏.WSN中LEACH路由算法的改进及应用研究［D］.苏州：苏州大学，2010：6-8.TAO Jun.The application and improvement on the LEACH routing protocol in wireless sensor networks［D］.Suzhou：Suzhou University，2010：6-8.

［9］ 顾明霞.一种新的基于LEACH 的 WSN路由算法［J］.计算机仿真，2011，28（8）：129-133.GU Mingxia.New LEACH-based algorithms for wireless sensor networks［J］.Computer Simulation，2011，28（8）：129-133.

［10］ 孔令荣，王昊，庄涛.基于 WSN的分簇路由协议研究与改进［J］.无线电工程，2014，44（12）：48-51.KONG Lingrong，WANG Hao，ZHUNAG Tao.Research and improvement of clustering routing protocol based on WSN［J］.Radio Engineering，2014，44（12）：48-51.

［11］ 赵凡.一种能量均衡的无线传感器网络多跳分簇路由算法［D］.哈尔滨：哈尔滨理工大学，2014.ZHAO Fan.An energy-balanced multi-hop clustering routing algorithm in wireless sensor neiworks［D］.Harbin：Harbin University of Science and Technology，2014.

［12］ LIU Zhixin，DAI Lili，MA Kai，et al.Balance energy-efficient and real-time with reliable communication protocol for wireless sensor network［J］.The Journal of China Universities of Posts and Telecommunications，2013，20（1）：37-46.

［13］ 徐建军，沙力妮，张艳，等.一种新的最小生成树算法［J］.电力系统保护与控制，2011，39（14）：107-112.XUN Jianjun，SHA Lini，ZHANG Yan，et al.A new algorithm of the minimum spanning tree［J］.Power System Protection and Control，2011，39（14）：107-112.