论文部分内容阅读
摘 要：为了更高效地利用无线传感器网络节点的能量，均衡网络能耗，文中提出了一种基于泰森图的无线传感器网络非均匀分簇路由算法。该算法首先利用泰森图划分区域原理对区域内所有节点进行分簇，然后基于查询报文获取最小跳数的多径路由发现机制进行多路径搜索，搜索过程充分考虑了路径最大剩余能量、最小路由跳数和最近传输距离等因素，最后选出满足条件的最优路径，完成源目的节点间的信息传输。仿真结果表明，该算法能有效地均衡网络能耗，延长网络使用期限。
关键词：无线传感器网络；泰森图；查询报文；分簇路由
中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2016）08-00-04
0 引 言
无线传感器网络（Wireless Sensor Network，WSN）是由一定数量的传感器组成的智能无线网络系统[1]，它以无线通信的方式连接各传感器节点[2]，起到实时监测和采集数据的作用。无线传感器网络协议一直都是这个领域研究的热点。由于传感器节点能量十分有限，分布区域位置复杂，设计能均衡网络能耗、延长使用寿命和提供快捷实时的数据服务协议也就成了重点。
LEACH （ Low Energy Adaptive Clustering Hierarchy，LEACH） 是最早提出的低功耗自适应基于分簇的路由协议[3]，它随机选择簇头，让每一个节点都有机会当选为簇头，从而平衡了网络能耗。但在LEACH算法中，产生簇首的过程没有将节点自身的剩余能量计算在内，某个簇头可能因为能量很低无法担任数据传输任务，因此该算法不利于网络的能耗均衡。另外在LEACH算法中，簇首与汇聚节点间采用单跳数据传输，传输距离较远的节点能耗自然比较大，致使网络能量不能高效利用[4，5]。
针对LEACH算法的不足，文献[6，7]提出了对簇首选举时的门限值T（n）进行改进，这在一定程度上提高了高能量节点成为簇首的概率，有利于网络能量的平衡。Lindsey S.等人在LEACH的基础上提出了PEGASIS协议[8]，但该协议的前提是每一个节点都能够与Sink节点直接通信，这就限制了网络范围，扩展性较差。文献[9]提出了一种非均匀分簇的多跳路由协议EEUC，该协议的优点是考虑到了簇首均衡能耗的情况，平衡了网络能耗，源节点与汇聚节点之间采用多跳的方式传输数据，避免直接通信造成能量耗损过快。但该协议在簇的生成阶段涉及到簇间距离的限制，过程控制比较复杂。后来又有基于粒子群[9]的非均匀分簇算法和基于蚁群[10，11]的分簇算法，但他们的设计过程也都相对复杂。
本文对LEACH及PEGASIS协议进行分析，针对LEACH和PEGASIS协议在簇头选择以及数据传输过程中的不足，提出一种基于泰森图分簇的路由算法，该算法在分簇阶段采用泰森图的区域划分原理进行分簇，避免了传统分簇算法遇到的问题，在簇间路由阶段采用基于报文查询的机制获取最优传输路径，从而在网络能耗均衡方面相较优良，能够延长网络的使用期限。
1 泰森图分簇算法
1.1 泰森图介绍
泰森图是为解决这类问题而产生的几何图形[12]：平面中假设有n个点，给定任意点p，对于其他任意一点q，求距离p比距离q更近的点的几何。
若只有两个点p和q，作他们连线的垂直平分线，在平分线任意一侧的任意点c（假设在p点一侧），则cp的距离比cq距离近，而c点若在q一侧，则cq距离比cp距离近。
若现有一集合P{A，B，C，D，E}，此时的划分过程是：把所有点连接成凸或凹多边形，是凸多边形则在凸多边形内任意找一点，如果是凹多边形，则在凹的方向找一点补齐使之成为凸多边形，链接所有点成为不相交的三角形，作三角形各边的垂直平分线，所有平分线组成的几何图形就是一个简单的泰森图，如图1所示。
将上图由各三角形各边垂直平分线划分的区域图形称之为泰森图，P{A，B，C，D，E}成为泰森图母点几何，根据划分规则可以计算得到，在一个泰森图小区域内任意一点，它距离这个区域的母点的距离比距离其它区域内母点的距离都近。
1.2 基于泰森图原理分簇
1.2.1 最优簇头数
簇头数量过少将导致整个区域内划分后的区域过于稀疏，其中很多簇头收集本簇内的数据量将会变大。簇头数量过多，传输跳数随之变多，易耗损能量。因此，簇头数目应加以限制，研究表明，最优簇头数所占总结点数量在7%～12%之间比较合适，本文采用公式（1）确定最优簇头的数量。
平面区域内任意节点n产生的（0，1）区间的随机值δ（n）与阈值T（n）比较，如果满足δ（n） 通过以上对簇头节点随机数选取的改进可以看出，公式（1～2）中当E（n）值比平均水平低的幅度越大，节点n越难被选为簇头，从而均衡了节点的区域能量，保障了网络的能量均衡。
1.2.3 分簇及成簇
依据最优簇头数和簇头选举机制，我们选出了K簇头，将其作为母点，构建整个区域的泰森图。构建完毕后，得到分簇的结果，每个以簇首为母点的区域就是一个簇。
分簇完成后，需规划其成员节点。依据泰森图几何区域划分原理可以看出，在每个以簇首为母点的多边形区域内，成员节点距离簇首比距离其他任意簇首的距离都近，因此，我们就将处在这个多边形区域内的点划分到这个簇内。
泰森图分簇此时可以看到它的优点：
（1）分簇以及成簇过程容易。知道簇首节点的相对位置和簇头数量即可分簇，分簇完成后，成簇也完成了，处在以簇首为母点的多边形内的节点都是成员节点。 （2）实现动态划分，避免分簇不均匀。第一次分簇的结果是在最初确定簇头数的基础上确定的，它确保整个环境最优的K个节点先当选为簇首，虽然会造成簇头在某一区域拥挤或稀疏的情况，但泰森图是基于动态分簇的过程，在经过一段时间后簇首由于失效产生新的簇首，整个区域就再根据新的簇首进行区域划分，经历若干次划分后，就可以避免簇头分布不均匀的情况。
1.3 簇内路由
1.3.1 簇首备份
为防止频繁地选举簇头，造成数据传输中断，故引入簇首备份机制，在成簇阶段完成后即可进行簇首备份工作，簇首备份工作主要是在簇首节点里备份一个最优成员节点作为下一任簇首。备份簇首选举公式由公式（3）确定：
在公式（3）中，Nib表示邻居节点的数量，邻居节点越多，则该节点就越能联系更多的节点完成数据通信；dc表示簇首与备份簇首的距离，距离越近，则越有可能成为备份簇首，新形成的泰森图不会变化太多；a、b和c三个参数分别表示剩余能量，Nib和1/dc所占权重取决于 实际情况中考虑成为备份簇首的因素。
1.3.2 簇内路由过程
分簇完成后即可实现簇内数据的传输，簇成员节点发送消息报文给簇首告知要加入簇，簇首保存簇成员节点信息，采用 TDMA方式为簇成员节点进行时隙分配。簇成员节点采集数据后在自己的时间片内将数据传输给簇首，簇首将所有成员节点数据进行综合处理（融合或者压缩等），最后一并转发给其他簇首，直到传输给汇聚节点。
2 簇间路由建立
针对LEACH算法单跳传输的缺陷，本文采用的方法是进行多跳传输， 簇头将各自簇内节点发来的数据融合，然后发给下一跳路由，数据经过多个路由最终发到汇聚节点。进行多跳传输必然涉及到跳数多少的问题，跳数多和路径上剩余能量少都会影响到能耗均衡。因此本文采用一种基于报文查询更新节点跳数值从而获取Sink节点到目标节点最小跳数的路径路由机制，该机制不同于泛洪机制，泛洪是所有节点都接收报文消息，而基于查询的报文规定只允许簇头节点接收查询报文，其他非簇头节点可以自动根据报文头部信息拒绝接收。
成簇机制完成后，进入路由发现过程。由Sink节点发起报文查询，网络中的其他节点开始检查是否接收此查询报文，只有簇首会接收此报文信息，否则不接受。簇首节点接收到查询报文后，会依据报文中的跳数数据跟自身原本存储的跳数作对比，根据此比值结果做相应操作。当所有簇首节点完成报文查询后，便更新了自己原本保存的跳数值，同时也保存了邻居节点信息，最小跳数路径发现过程结束。路由发现阶段涉及的查询报文结构由帧序号、源节点ID、能量值、目的节点ID和转发跳数组成。节点的路由表结构包括路由序号、下一跳节点ID、下一跳节点地址和下一跳节点剩余能量。
具体的路由发现过程是：协议中的所有节点都有唯一的标识号ID，初始化Sink节点的跳数为0，其余节点的跳数设为极大值。Sink节点向网络广播查询报文，只有簇头节点能接收到查询报文数据，其他非簇头节点自动丢弃该报文。当邻居簇头节点接收到查询数据包时，将数据包中的跳数值加l作为新跳数值与自身存储跳数值相比较，若新跳数值小于原先存储的跳数值，则用新值替换原存储值；将数据包中的跳数值换作新值，并且用自己节点的ID号替换原来报文信息中的节点标识号ID。把Sink节点添加到自己的路由表中。然后依据节点信息修改查询报文的内容，将信息包中的hop值加1，信息包中原本保存有上一个节点为止所有节点的剩余能量总和值，将这个总和值加上当前节点剩余能量构成一个新的总剩余能量值，之后将新的总剩余能量及其自身ID写入消息包中，继续广播此查询消息。反之不作任何处理。其它节点都做上述同样的处理，此过程持续下去，因此每个节点均建立了到Sink节点的最小跳数路径并记忆了各条路径的剩余能量总和值。
当一个簇头节点到汇聚节点有多条相同的最小跳数时，比较这几条路径的总剩余能量，选择能量最高的作为最终路径。因此最后选择的路径是跳数最少路径上总能量最高的。路径发现过程结束后，数据沿反向路径传输到汇聚节点。
2.1 簇间数据传递
在簇间，簇首节点起到传递数据的作用，根据路由表将数据发送到下一跳节点，直到汇聚节点。整个数据传递阶段完成。
2.2 路由更新
路由更新会在下面两种情形下进行：
（1）路径上新的簇首形成。
（2）某些簇失去作用，需重新确定路径。
2.2.1 路径上新的簇首形成
当一轮数据传输完毕后选举一个新的节点担任簇首，新的簇首选举后它将向路径上游前一个路由节点发送自身节点信息，以保持整条路径畅通及整条路径跳数最少，虽然不能保证整条路径能量最优，但避免了频繁的报文查询机制。
2.2.2 某些簇失去作用
当某个簇内所有节点剩余能量均不足时，那么将这个簇划分为失效簇，之前经过这个簇的路径将失去联通。在这种情况下，目前采取的做法是重新启动查询报文机制，形成一条新的路由路径，完成数据传输。
3 算法仿真及分析
现在对LEACH及本文提出的协议进行仿真对比实验，仿真工具为NS2，仿真环境为150 m×150 m区域随机位置的300个节点，假设所有节点初始能量相同，忽略数据丢包、延迟、节点自然坏掉等因素。
图2所示为相同时间内节点死亡个数，在开始的一段时间内，网络消耗的能量不多，存活死亡数大致相当，越到后面本文提出的算法越体现出了其优越性，相比较LEACH算法而言，该算法在能量均衡方面做得更好，延长了网络使用寿命，死亡节点更少，有更多的节点存活下来。从图3中更可以直观地看到，在开始阶段根据报文查询最优路径的过程中消耗了部分能量，使得其剩余总能量几乎和LEACH相同，但是最优路径只是在开始阶段启用，到后面，本文算法在能耗均衡方面就比其它两个算法做得好，总剩余能量总比LEACH算法多，可节省能量。经实验结果分析可得出结论：新算法相比LEACH算法而言，在均衡网络能耗和延长网络使用寿命方面发挥了一定作用。 4 结 语
本文算法先根据泰森图分簇，在选出的簇首的基础上，基于报文查询机制搜索跳数最小、能量最优的多跳路径，之后在最优路径上传输数据至汇聚节点。最后在NS2环境下与LEACH算法进行对比试验分析，仿真结果表明，本文算法比LEACH算法在能耗均衡方面做的更好，可以有效延长网络的生命期。
参考文献
[1] IF Akyildiz，W Su，Y Sankarasubramanian，et al. Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）：393-422.
[2] R Xiao，WU Guozheng.A survey on routing in wireless sensor net-works [J].Progress in N atural Science，2007，17（3）：261-269 .
[3] Heinzelman W R.Energy-efficient communication protocol for wireless micro sensor networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Maui： IEEE，2000： 3005-3014.
[4] Weiya W ang，Weibing Li，Dongdong Chen，et a1.Ant colony based rounting algorithm for Multi_Sink[C].WRI World Congresson，2009：423- 429.
[5] Azim，Islam.Hybrid LEACH：A relay node based low energy adaptive clustering hierarchy for wireless sensor networks[C].M alaysia International Conference on，2009：911-916 .
[6] Hou Guofeng，Tang K.W.Evaluation of LEACH protocol subject to different traffic models [C].COIN-NGNCON 2006.Hyatt R egency jeju，Korea，2006：281-283.
[7] Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks wireless communications[J].IEEE Transactions on Wireless
Communications，2002，1（4）：660-670.
[8] I Shukla，N eghanathan.PEGASIS：power-efficient gathering in sensor information system[C].In：Proceedings of the IEEE Aerospace Conference.Montana：IEEE Aerospace and Electronic Systems Society，2 002：1125-1130 .
[9] Fuad Bajaber，Irfan Awan.EECPL：Energy Effcient Clustering Protocol to Enhance Lifetime of Wireless Sensor Network[J].J Ambient Intell Human Computing，2010，1（4）：229-238.
[10] 邹杰，史常琼，姬文燕，等.基于粒子群优化的非均匀分簇路由算法[J].计算机应用，2012，32（3）：131-133.
[11] DORIG0 M，BONABEAU E，THERAUIAZ G. Inspiration for optimization from social insect behavior[J].Nature，2000：39-42.
[12] 易琳.基于共形几何代数的多维统一Voronoi算法及其应用研究[D].南京：南京师范大学，2011.
关键词：无线传感器网络；泰森图；查询报文；分簇路由
中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2016）08-00-04
0 引 言
无线传感器网络（Wireless Sensor Network，WSN）是由一定数量的传感器组成的智能无线网络系统[1]，它以无线通信的方式连接各传感器节点[2]，起到实时监测和采集数据的作用。无线传感器网络协议一直都是这个领域研究的热点。由于传感器节点能量十分有限，分布区域位置复杂，设计能均衡网络能耗、延长使用寿命和提供快捷实时的数据服务协议也就成了重点。
LEACH （ Low Energy Adaptive Clustering Hierarchy，LEACH） 是最早提出的低功耗自适应基于分簇的路由协议[3]，它随机选择簇头，让每一个节点都有机会当选为簇头，从而平衡了网络能耗。但在LEACH算法中，产生簇首的过程没有将节点自身的剩余能量计算在内，某个簇头可能因为能量很低无法担任数据传输任务，因此该算法不利于网络的能耗均衡。另外在LEACH算法中，簇首与汇聚节点间采用单跳数据传输，传输距离较远的节点能耗自然比较大，致使网络能量不能高效利用[4，5]。
针对LEACH算法的不足，文献[6，7]提出了对簇首选举时的门限值T（n）进行改进，这在一定程度上提高了高能量节点成为簇首的概率，有利于网络能量的平衡。Lindsey S.等人在LEACH的基础上提出了PEGASIS协议[8]，但该协议的前提是每一个节点都能够与Sink节点直接通信，这就限制了网络范围，扩展性较差。文献[9]提出了一种非均匀分簇的多跳路由协议EEUC，该协议的优点是考虑到了簇首均衡能耗的情况，平衡了网络能耗，源节点与汇聚节点之间采用多跳的方式传输数据，避免直接通信造成能量耗损过快。但该协议在簇的生成阶段涉及到簇间距离的限制，过程控制比较复杂。后来又有基于粒子群[9]的非均匀分簇算法和基于蚁群[10，11]的分簇算法，但他们的设计过程也都相对复杂。
本文对LEACH及PEGASIS协议进行分析，针对LEACH和PEGASIS协议在簇头选择以及数据传输过程中的不足，提出一种基于泰森图分簇的路由算法，该算法在分簇阶段采用泰森图的区域划分原理进行分簇，避免了传统分簇算法遇到的问题，在簇间路由阶段采用基于报文查询的机制获取最优传输路径，从而在网络能耗均衡方面相较优良，能够延长网络的使用期限。
1 泰森图分簇算法
1.1 泰森图介绍
泰森图是为解决这类问题而产生的几何图形[12]：平面中假设有n个点，给定任意点p，对于其他任意一点q，求距离p比距离q更近的点的几何。
若只有两个点p和q，作他们连线的垂直平分线，在平分线任意一侧的任意点c（假设在p点一侧），则cp的距离比cq距离近，而c点若在q一侧，则cq距离比cp距离近。
若现有一集合P{A，B，C，D，E}，此时的划分过程是：把所有点连接成凸或凹多边形，是凸多边形则在凸多边形内任意找一点，如果是凹多边形，则在凹的方向找一点补齐使之成为凸多边形，链接所有点成为不相交的三角形，作三角形各边的垂直平分线，所有平分线组成的几何图形就是一个简单的泰森图，如图1所示。
将上图由各三角形各边垂直平分线划分的区域图形称之为泰森图，P{A，B，C，D，E}成为泰森图母点几何，根据划分规则可以计算得到，在一个泰森图小区域内任意一点，它距离这个区域的母点的距离比距离其它区域内母点的距离都近。
1.2 基于泰森图原理分簇
1.2.1 最优簇头数
簇头数量过少将导致整个区域内划分后的区域过于稀疏，其中很多簇头收集本簇内的数据量将会变大。簇头数量过多，传输跳数随之变多，易耗损能量。因此，簇头数目应加以限制，研究表明，最优簇头数所占总结点数量在7%～12%之间比较合适，本文采用公式（1）确定最优簇头的数量。
平面区域内任意节点n产生的（0，1）区间的随机值δ（n）与阈值T（n）比较，如果满足δ（n）
1.2.3 分簇及成簇
依据最优簇头数和簇头选举机制，我们选出了K簇头，将其作为母点，构建整个区域的泰森图。构建完毕后，得到分簇的结果，每个以簇首为母点的区域就是一个簇。
分簇完成后，需规划其成员节点。依据泰森图几何区域划分原理可以看出，在每个以簇首为母点的多边形区域内，成员节点距离簇首比距离其他任意簇首的距离都近，因此，我们就将处在这个多边形区域内的点划分到这个簇内。
泰森图分簇此时可以看到它的优点：
（1）分簇以及成簇过程容易。知道簇首节点的相对位置和簇头数量即可分簇，分簇完成后，成簇也完成了，处在以簇首为母点的多边形内的节点都是成员节点。 （2）实现动态划分，避免分簇不均匀。第一次分簇的结果是在最初确定簇头数的基础上确定的，它确保整个环境最优的K个节点先当选为簇首，虽然会造成簇头在某一区域拥挤或稀疏的情况，但泰森图是基于动态分簇的过程，在经过一段时间后簇首由于失效产生新的簇首，整个区域就再根据新的簇首进行区域划分，经历若干次划分后，就可以避免簇头分布不均匀的情况。
1.3 簇内路由
1.3.1 簇首备份
为防止频繁地选举簇头，造成数据传输中断，故引入簇首备份机制，在成簇阶段完成后即可进行簇首备份工作，簇首备份工作主要是在簇首节点里备份一个最优成员节点作为下一任簇首。备份簇首选举公式由公式（3）确定：
在公式（3）中，Nib表示邻居节点的数量，邻居节点越多，则该节点就越能联系更多的节点完成数据通信；dc表示簇首与备份簇首的距离，距离越近，则越有可能成为备份簇首，新形成的泰森图不会变化太多；a、b和c三个参数分别表示剩余能量，Nib和1/dc所占权重取决于 实际情况中考虑成为备份簇首的因素。
1.3.2 簇内路由过程
分簇完成后即可实现簇内数据的传输，簇成员节点发送消息报文给簇首告知要加入簇，簇首保存簇成员节点信息，采用 TDMA方式为簇成员节点进行时隙分配。簇成员节点采集数据后在自己的时间片内将数据传输给簇首，簇首将所有成员节点数据进行综合处理（融合或者压缩等），最后一并转发给其他簇首，直到传输给汇聚节点。
2 簇间路由建立
针对LEACH算法单跳传输的缺陷，本文采用的方法是进行多跳传输， 簇头将各自簇内节点发来的数据融合，然后发给下一跳路由，数据经过多个路由最终发到汇聚节点。进行多跳传输必然涉及到跳数多少的问题，跳数多和路径上剩余能量少都会影响到能耗均衡。因此本文采用一种基于报文查询更新节点跳数值从而获取Sink节点到目标节点最小跳数的路径路由机制，该机制不同于泛洪机制，泛洪是所有节点都接收报文消息，而基于查询的报文规定只允许簇头节点接收查询报文，其他非簇头节点可以自动根据报文头部信息拒绝接收。
成簇机制完成后，进入路由发现过程。由Sink节点发起报文查询，网络中的其他节点开始检查是否接收此查询报文，只有簇首会接收此报文信息，否则不接受。簇首节点接收到查询报文后，会依据报文中的跳数数据跟自身原本存储的跳数作对比，根据此比值结果做相应操作。当所有簇首节点完成报文查询后，便更新了自己原本保存的跳数值，同时也保存了邻居节点信息，最小跳数路径发现过程结束。路由发现阶段涉及的查询报文结构由帧序号、源节点ID、能量值、目的节点ID和转发跳数组成。节点的路由表结构包括路由序号、下一跳节点ID、下一跳节点地址和下一跳节点剩余能量。
具体的路由发现过程是：协议中的所有节点都有唯一的标识号ID，初始化Sink节点的跳数为0，其余节点的跳数设为极大值。Sink节点向网络广播查询报文，只有簇头节点能接收到查询报文数据，其他非簇头节点自动丢弃该报文。当邻居簇头节点接收到查询数据包时，将数据包中的跳数值加l作为新跳数值与自身存储跳数值相比较，若新跳数值小于原先存储的跳数值，则用新值替换原存储值；将数据包中的跳数值换作新值，并且用自己节点的ID号替换原来报文信息中的节点标识号ID。把Sink节点添加到自己的路由表中。然后依据节点信息修改查询报文的内容，将信息包中的hop值加1，信息包中原本保存有上一个节点为止所有节点的剩余能量总和值，将这个总和值加上当前节点剩余能量构成一个新的总剩余能量值，之后将新的总剩余能量及其自身ID写入消息包中，继续广播此查询消息。反之不作任何处理。其它节点都做上述同样的处理，此过程持续下去，因此每个节点均建立了到Sink节点的最小跳数路径并记忆了各条路径的剩余能量总和值。
当一个簇头节点到汇聚节点有多条相同的最小跳数时，比较这几条路径的总剩余能量，选择能量最高的作为最终路径。因此最后选择的路径是跳数最少路径上总能量最高的。路径发现过程结束后，数据沿反向路径传输到汇聚节点。
2.1 簇间数据传递
在簇间，簇首节点起到传递数据的作用，根据路由表将数据发送到下一跳节点，直到汇聚节点。整个数据传递阶段完成。
2.2 路由更新
路由更新会在下面两种情形下进行：
（1）路径上新的簇首形成。
（2）某些簇失去作用，需重新确定路径。
2.2.1 路径上新的簇首形成
当一轮数据传输完毕后选举一个新的节点担任簇首，新的簇首选举后它将向路径上游前一个路由节点发送自身节点信息，以保持整条路径畅通及整条路径跳数最少，虽然不能保证整条路径能量最优，但避免了频繁的报文查询机制。
2.2.2 某些簇失去作用
当某个簇内所有节点剩余能量均不足时，那么将这个簇划分为失效簇，之前经过这个簇的路径将失去联通。在这种情况下，目前采取的做法是重新启动查询报文机制，形成一条新的路由路径，完成数据传输。
3 算法仿真及分析
现在对LEACH及本文提出的协议进行仿真对比实验，仿真工具为NS2，仿真环境为150 m×150 m区域随机位置的300个节点，假设所有节点初始能量相同，忽略数据丢包、延迟、节点自然坏掉等因素。
图2所示为相同时间内节点死亡个数，在开始的一段时间内，网络消耗的能量不多，存活死亡数大致相当，越到后面本文提出的算法越体现出了其优越性，相比较LEACH算法而言，该算法在能量均衡方面做得更好，延长了网络使用寿命，死亡节点更少，有更多的节点存活下来。从图3中更可以直观地看到，在开始阶段根据报文查询最优路径的过程中消耗了部分能量，使得其剩余总能量几乎和LEACH相同，但是最优路径只是在开始阶段启用，到后面，本文算法在能耗均衡方面就比其它两个算法做得好，总剩余能量总比LEACH算法多，可节省能量。经实验结果分析可得出结论：新算法相比LEACH算法而言，在均衡网络能耗和延长网络使用寿命方面发挥了一定作用。 4 结 语
本文算法先根据泰森图分簇，在选出的簇首的基础上，基于报文查询机制搜索跳数最小、能量最优的多跳路径，之后在最优路径上传输数据至汇聚节点。最后在NS2环境下与LEACH算法进行对比试验分析，仿真结果表明，本文算法比LEACH算法在能耗均衡方面做的更好，可以有效延长网络的生命期。
参考文献
[1] IF Akyildiz，W Su，Y Sankarasubramanian，et al. Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）：393-422.
[2] R Xiao，WU Guozheng.A survey on routing in wireless sensor net-works [J].Progress in N atural Science，2007，17（3）：261-269 .
[3] Heinzelman W R.Energy-efficient communication protocol for wireless micro sensor networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Maui： IEEE，2000： 3005-3014.
[4] Weiya W ang，Weibing Li，Dongdong Chen，et a1.Ant colony based rounting algorithm for Multi_Sink[C].WRI World Congresson，2009：423- 429.
[5] Azim，Islam.Hybrid LEACH：A relay node based low energy adaptive clustering hierarchy for wireless sensor networks[C].M alaysia International Conference on，2009：911-916 .
[6] Hou Guofeng，Tang K.W.Evaluation of LEACH protocol subject to different traffic models [C].COIN-NGNCON 2006.Hyatt R egency jeju，Korea，2006：281-283.
[7] Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks wireless communications[J].IEEE Transactions on Wireless
Communications，2002，1（4）：660-670.
[8] I Shukla，N eghanathan.PEGASIS：power-efficient gathering in sensor information system[C].In：Proceedings of the IEEE Aerospace Conference.Montana：IEEE Aerospace and Electronic Systems Society，2 002：1125-1130 .
[9] Fuad Bajaber，Irfan Awan.EECPL：Energy Effcient Clustering Protocol to Enhance Lifetime of Wireless Sensor Network[J].J Ambient Intell Human Computing，2010，1（4）：229-238.
[10] 邹杰，史常琼，姬文燕，等.基于粒子群优化的非均匀分簇路由算法[J].计算机应用，2012，32（3）：131-133.
[11] DORIG0 M，BONABEAU E，THERAUIAZ G. Inspiration for optimization from social insect behavior[J].Nature，2000：39-42.
[12] 易琳.基于共形几何代数的多维统一Voronoi算法及其应用研究[D].南京：南京师范大学，2011.