基于非均等分区的无线传感器网络路由协议
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于非均等分区的无线传感器网络路由协议范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：针对无线传感器网络（WSN）存在簇头节点分布不合理以及节点负载不均形成的“热点”问题，提出了一种基于非均等分区的非均匀分簇路由协议（UAUC）。UAUC通过非均等分区对网络进行划分，并在每个区域中根据能量因子、距离因子以及密集程度因子选择合适的簇头节点。此外，在簇头节点之间构造一棵负载均衡路径树，解决数据传输时存在的“热点”问题。仿真实验中，与低功耗自适应集簇分层（LEACH）协议，分布式能量有效非均匀成簇（DEBUC）协议以及基于非均匀分簇的无线传感器网络分层路由协议（HRPNC）相比，UAUC协议的簇头节点分布更加合理；UAUC在生存周期上较LEACH协议，DEBUC协议与HRPNC协议分别提高了88%，12%与17.5%；UAUC的节点平均剩余能量高于LEACH协议，DEBUC协议和HRPNC协议，并且节点剩余能量方差小于LEACH协议，DEBUC协议和HRPNC协议；UAUC协议在数据包接收量上较LEACH协议，DEBUC协议和HRPNC协议提高了400%，87.5%与25%。实验结果表明，UAUC能够有效地提高能量效率和数据包接收量，均衡能量消耗，延长网络的生存周期。
关键词：无线传感器网络；路由协议；分簇；多跳；能量有效
中图分类号：TP393
文献标志码：A
文章编号：1001-9081（2016）11-3010-06
0 引言
无线传感器网络（Wireless Sensor Network，WSN）是由部署在监测区域内大量的传感器节点组成，通过无线通信方式，监测和收集区域内对象信息的多跳自组织网络系统。随着信息技术的发展，WSN在生物医疗、国防军事、环境检测、抢险救灾、城市管理、智能家居、工农业控制等领域有着广泛的应用前景。无线传感器网络最突出的特点是传感器节点能量有限且不可再生，所以在无线传感器网络中，降低网络能量消耗、延长网络生存周期是面临的重要挑战[1]。
层次路由协议通过分簇在一定程度上延长了无线传感器网路的生存周期。其中低功耗自适应集簇分层（Low Energy Adaptive Clustering Hierarchy， LEACH）[2]协议通过随机选择一小部分节点作为簇头节点并采用周期轮换机制，但由于随机选择簇头节点导致簇头节点分布不合理。此外，在数据传输阶段，簇头节点与汇聚节点直接通信，导致簇头节点的能量消耗过快。吕涛等[3]通过引入簇成员数门限和合并极小簇的方法，避免存在极大簇和极小簇。文献[4]针对LEACH协议频繁地选择簇头节点消耗过多的能量提出了一种基于LEACH的簇头连任协议（cluster head Reappointment protocol based on LEACH， LEACH-R），有效地延长了网络的生存周期。
针对均匀分簇存在簇间能耗不均衡的问题，李成法等[5]提出了一个能量高效的非均匀分簇（Energy-Efficient Uneven Clustering， EEUC）算法。EEUC通过使用非均匀的竞争范围来构造大小不等的簇，使得靠近汇聚点的簇的规模小于远离汇聚点的簇，均衡了簇头节点的能量消耗。尚凤军等[6]提出了分布式能量有效非均匀成簇（Distributed Energy Efficient Unequal Clustering， DEEUC）算法，在选择簇头时，加入了平均能量因子平衡全网节点的剩余能量，并通过调节簇头竞争半径调节簇的大小，在一定程序上缓解了能耗不均衡的问题，但离基站比较近的簇头频繁转发其他簇头发送的数据包，因此消耗更多的能量，使得离基站近的簇头容易死亡，产生“热点”问题。蒋畅江等[7]提出了能量均衡的无线传感器网络非均匀分簇路由（Distributed Energy-Balanced Unequal Clustering routing， DEBUC）协议。DEBUC在选择簇头时，参考候选簇头的剩余能量和邻居节点的剩余能量，采用基于时间的簇头竞争算法，通过控制候选簇头的竞争范围，使得距离基站较近的簇规模较小。数据传输时，簇头节点根据节点剩余能量、簇内通信代价和簇间通信代价，在邻居簇头中选择中继节点作为下一跳； 但存在离基站较远的簇规模过大，节点能量消耗过多的问题。文献[8]中提出了能量有效的LEACH改进协议（Energy Efficient Extended LEACH， EEE LEACH）。EEE LEACH采取分层的思想，在簇头节点之间选取一些主簇头节点。簇内节点将数据发送给簇头节点，簇头节点将融合后的数据发送给距离最小的主簇头节点，主簇头节点将接收的数据包发送给汇聚节点。但是EEE LEACH存在主簇头节点选择不合理以及主簇头节点能量消耗过大的问题，影响网络的生存周期。黄廷辉等[9]提出了基于非均匀分簇的无线传感器网络分层路由协议（Hierarchical Routing Protocol based on Non-uniform Clustering， HRPNC）。HRPNC在分层的基础上改进了DEBUC协议的竞争半径，控制了节点竞争半径的范围，避免了大规模网络中离基站远的节点竞争半径过大的问题。在簇头选择时，HRPNC随机选择一些节点作为候选簇头节点，再依据节点竞争半径选择簇头节点，而节点的基准竞争半径取决于每层的面积和节点数目。由于HRPNC没有考虑节点的能量以及密集程度，存在簇头节点选择不合理的问题。
针对以上一些协议的不足，为了解决簇头节点选取不合理以及能量消耗不均的“热点”问题，本文提出了一个非均等分区的非均匀分簇路由协议（Unequal partition Area Uneven Clustering routing protocol， UAUC）。UAUC通过结合非均等分区以及综合考虑能量因子、距离因子以及密集程度因子选择簇头节点，使簇头节点分布更加合理。在数据传输时，通过构建合理的路径树，均衡节点之间的能量消耗，提高网络的生存周期。
1 网络与能耗模型
1.1 网络模型
本文假设无线传感器网络中所有节点随机分布在一个矩形区域内，网络模型具有以下性质：
1）节点随机均匀地分布在监测区域中。
2）基站位于监测区域底边中点处，且位置固定。
3）基站具有较强的计算能力、存储能力，且能量不受限制。
4）所有节点都具有唯一的标识（ID），能量受限。
5）节点可以通过计算得出当前的剩余能量。
6）节点不具有位置感知能力。
7）节点具有相同的通信能力。
1.2 能耗模型
本文采用与文献[2]中相同的无线通信能耗模型。如图1所示，该模型考虑了无线传输中发射电路发射信号的能耗，功率放大器的能耗以及接收电路中接收信号的能耗。功率放大器的能耗与传输距离d有关：当d
2 基于非均等分区的路由协议UAUC
本文提出的基于非均等分区的路由协议UAUC分成三个阶段：第一阶段，非均等分区阶段；第二阶段，选择簇头节点以及簇的形成阶段；第三阶段，数据传输阶段。
路径树的构建流程如下：
步骤1 开始，节点初始化。
步骤2 簇头节点广播数据包，找到邻居节点，构造出关系图G。
步骤3 根据关系图G，对节点进行分级。与基站可直接通信即图G中与基站Sink直接有边相连的节点定义为一级节点，与一级节点有边相连的节点定义为二级节点，依次确定所有节点的等级。
步骤4 以基站Sink为根，一级节点作为树的第一层节点，二级节点以一级节点作为父节点。当二级节点只与一个一级节点有边相连，则直接选择此一级节点作为父节点；否则在一级节点中选择使WL（i）最大的节点作为父节点，直到所有节点遍历完成。
步骤5 结束。
以图3为例，图3（a）表示一个基站与簇头节点之间的关系图G，0号节点表示基站，1号节点到16号节点表示簇头节点。根据关系图G，可得到节点的等级数。一级节点为：1号节点、2号节点、3号节点和4号节点；二级节点为：5号节点、6号节点、8号节点、9号节点和10号节点；三级节点为：7号节点、11号节点、12号节点、14号节点、15号节点和16号节点；四级节点为：13号节点。一级节点作为路径树的第一层，二级节点作为路径树的第二层，依此类推。根据路径树的构建流程构造出一棵以基站为根节点的路径树，如图3（b）所示。簇头节点依照构建出的路径树，将数据包发送给自己的父节点。
2.4 算法分析
UAUC先将网络进行非均等分区，对每个区域选出合适的簇头节点，其他节点不考虑所在区域直接选择离自己最近的簇头加入成簇。数据传输时，簇内节点将数据包发送给簇头节点，簇头节点将接收到的数据包进行融合，然后按照构建的路径树将数据包发送给自己的父节点，直到将数据包发送给基站。
为了避免簇头节点能量消耗过快死亡，UAUC采用簇头轮换机制。与LEACH协议不同，UAUC协议用区平均能量表示该区域中所有节点的平均能量。当有簇头节点的能量小于所在区域的区平均能量时，对该区域的簇头节点进行重新选取，重新计算该区域中节点的value值，选择value值最大的节点替换原来的节点作为新的簇头节点。避免每轮全部选取新的簇头所消耗的能量和代价。
UAUC的伪代码如下所示，其中：n（i）.AreaNum代表节点n（i）所在的区域号， EnergyAvg（j）代表区域Aj的区平均能量，Nj表示区域Aj的节点数目。
程序前
ClusterHead selection algorithm
For every area Aj
For every node n（i）
If （n（i）.AreaNum==Aj）
Calculate value（i） according Eq（10）；
Else
Continue
End
End
Sort value（i），get the ClusterHead for the Aj；
End
Forming Cluster algorithm
For every ClusterHead（k）
Broadcast ClusterHead-MSG（ID）；
End
For every node n（i）
If n（i） ClusterHead（k）
Receiving all ClusterHead-MSG；
Calculate Distance To ClusterHead d（i，k）；
Select the ClusterHead with min d（i，k）；
Add n（i） to ClusterHead（k） and broadcast the
Join-ClusterHead-MSG（ID）；
End
End
Forwarding Message algorithm
For every node n（i）
If n（i）ClusterHead（k）
Forwarding（msg） to it’s ClusterHead（k）；
Else
Receiving the msg and Data fusion；
And Forwarding（msg） to parentNode in T；
End
End
Cluster head rotation algorithm
For every area Aj
EnergyAvg（j）=∑Nji=1n（i）.energy/Nj；
End
For every ClusterHead（k）
If ClusterHead（k）.Energy
Calculate value（i） in Aj according Eq（10）；
Select max value（i）；
ClusterHead（k）=ClusterHead（i）；
End
End
程序后
性质 UAUC的消息复杂度是O（n）。
证明 基站广播一个数据包，让所有节点计算到基站的距离；假设网络中有n个节点，则广播n个数据包，让所有节点计算密度因子。其中有k个节点被选作为簇头节点，簇头节点广播ClusterHead-MSG消息，宣布自己成为簇头节点。其余n-k个非簇头节点广播Join-ClusterHead-MSG消息，成簇。数据传输阶段，簇头节点广播一个数据包，确定自己的邻居节点。因此UAUC的消息复杂度是：1+n+k+（n-k）+k=2n+k+1，因此UAUC的消息复杂度是O（n）。
3 仿真与实验
为了验证UAUC的性能，本文使用Matlab作为仿真工具，与经典的LEACH协议、DEBUC协议和HRPNC协议进行性能比较，从簇头节点分布、网络生存周期、节点剩余平均能量、节点剩余能量方差和数据包接收量等方面评估本文提出的UAUC协议的性能。实验参数设置如表1所示。
在100m×100m的监测区域上随机部署200个节点，根据式（4）～（9），可得到参数r=20，那么区域数目k=12。
图4显示了LEACH协议、DEBUC协议、HRPNC协议和UAUC协议簇头节点分布对比情况，如图4（a）所示，LEACH协议由于随机选择簇头节点，导致簇头节点分布不合理。如图4（b）所示，DEBUC协议中竞争半径逐渐增大，使得离基站远的簇规模过大，尤其在规模比较大的网络中，容易出现极大簇，影响网络生存周期。如图4（c）所示，HRPNC协议通过改进DEBUC协议的竞争半径，缓解了DEBUC协议中离基站远的簇规模过大的问题，但簇头节点的分布仍存在问题。图4（d）显示了UAUC协议的簇头分布情况。UAUC协议通过对网络进行分区，在每个区域中选择合适的节点作为簇头节点，使得簇头节点分布更加合理。
图5显示了4种算法存活节点数量的变化曲线。从图5中可以看出，UAUC运行到约2000轮时才出现第一个节点死亡，约4200轮时，50%的节点死亡，直到4700轮，节点完全死亡。UAUC算法的网络生存周期相对于LEACH算法、DEBUC算法与HRPNC算法分别提高了88%，12%与17.5%。DEBUC算法仅仅通过节点与基站之间的距离控制簇头节点的分布，而UAUC算法通过非均等分区以及综合考虑多个因素选择簇头节点，使得簇头节点比DEBUC簇头节点分布更加合理，因此提高了网络的生存周期。
图6显示了4种算法节点平均剩余能量的对比曲线。从图6中可以看出，与LEACH算法、DEBUC算法和HRPNC算法相比，UAUC算法的节点剩余能量明显较高。DEBUC算法选择代价函数值最小的邻居节点作为下一跳，但中继节点并不进行数据融合而直接发送数据包，造成数据冗余。UAUC算法通过构建负载均衡路径树实现多跳传输并且进行数据融合，有效地提高了网络的能量效率。
图7显示了4种算法节点剩余能量方差随轮数变化的对比曲线。从图7中可以看出，LEACH协议的节点剩余能量方差最大，DEBUC协议与HRPNC协议的节点剩余能量方差较小，UAUC协议的剩余能量方差最小，且变化不大。表明UAUC协议通过构建合理的路径树实现多跳传输，有效地均衡了网络中节点能量消耗。
图8显示了4种算法数据包接收量的对比曲线。从图8中可以看出，随着仿真轮数的增加，存活节点数量减少，数据包接收量也随之减少。UAUC算法在数据包接收量上较LEACH协议，DEBUC协议以及HRPNC协议分别提高了400%，87.5%与25%。表明UAUC算法通过构建路径树有效地提高了数据包接收量。
4 结语
针对簇头节点分布不合理和节点能量消耗不均衡的问题，本文提出了一个基于非均等分区的路由协议UAUC。通过非均等分区，综合考虑能量因子，距离因子和密集程度因子选择合适的簇头节点，并且基于负载均衡的路径树实现簇间多跳数据传输。通过仿真验证，UAUC算法使得簇头节点分布更加合理，提高能量效率和数据包接收量，均衡能量消耗，延长网络生存周期。但是UAUC协议假设网络中的节点一直不间断地向基站发送数据包，并且该算法在大规模无线传感器网络中性能有所下降。
在今后的工作中，考虑针对大规模无线传感器网络，加入节点睡眠机制，当节点不需要发送和接收数据包时，使节点进入睡眠状态，节约节点的能量消耗；当要发送和接收数据包时，结束睡眠状态，进入活跃状态。怎样制定合理的状态转换机制将是下一步工作。
参考文献：
[1] 洪锋，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述[J].计算机研究与发展， 2010， 47（S2）：81-87.（HONG F， CHU H W， JIN Z K， et al. Review of recent progress on wireless sensor network applications[J]. Computer Research and Development， 2010， 47（S2）：81-87.）
[2] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications， 2002， 1（4）：660-670.
[3] 吕涛， 朱清新， 张路桥. 一种基于LEACH协议的改进算法[J]. 电子学报， 2011， 39（6）：1405-1409.（LYU T， ZHU Q X， ZHANG L Q. An improved LEACH algorithm in wireless sensor network[J]. Acta Electronica Sinica， 2011， 39（6）：1405-1409.）
[4] LI Y Z， ZHANG A L， LIANG Y Z. Improvement of LEACH protocol for wireless sensor networks[C]// Proceedings of the 3rd International Conference on Instrumentation， Measurement， Computer， Communication and Control. Piscataway， NJ： IEEE， 2013：322-326.
[5] 李成法， 陈贵海， 叶懋，等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报， 2007， 30（1）：27-36.（LI C F， CHEN G H， YE M， et al. An uneven cluster-based routing protocol for wireless sensor networks[J]. Chinese Journal of Computers， 2007， 30（1）：27-36.）
[6] 尚凤军， ABOLHASAN M， WYSOCKI T. 无线传感器网络的分布式能量有效非均匀成簇算法[J].通信学报， 2009， 30（10）：34-43. （SHANG F J， ABOLHASAN M， WYSOCKI T. Distributed energy efficient unequal clustering algorithm for wireless sensor networks[J]. Journal on Communications， 2009， 30（10）：34-43.）
[7] 蒋畅江， 石为人， 唐贤伦，等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报， 2013， 34（5）：1222-1232.（JIANG C J， SHI W R，TANG X L， et al. Energy-balanced unequal clustering routing protocol for wireless sensor networks[J]. Journal of Software， 2013， 34（5）：1222-1232.）
[8] SHARMA M， SHARMA K. An Energy Efficient Extended LEACH （EEE LEACH）[C]// Proceedings of the 2012 International Conference on Communication Systems and Network Technologies. Piscataway， NJ： IEEE， 2012： 377-382.
[9] 黄廷辉， 伊凯， 崔更申，等. 基于非均匀分簇的无线传感器网络分层路由协议[J]. 计算机应用， 2016， 36（1）：66-71.（HUANG T H， YI K， CUI G S， et al. Hierarchical routing protocol based on non-uniform clustering for wireless sensor network[J]. Journal of Computer Applications，2016， 36（1）：66-71.）
[10] RAGHUVANSHI A S， TIWARI S， TRIPATHI R， et al. Optimal number of clusters in wireless sensor networks： an FCM approach[C]// Proceedings of the 2010 International Conference on International Conference on Computer and Communication Technology. Piscataway， NJ： IEEE， 2010：817-823.
[11] SALIM A， OSAMY W， KHEDR A M. IBLEACH： intra-balanced LEACH protocol for wireless sensor networks[J]. Wireless Networks， 2014， 20（6）：1515-1525.
[12] LI B， WANG W J， YIN Q Y， et al. An energy-efficient geographic routing based on cooperative transmission in wireless sensor networks[J]. Sciece China Information Sciences， 2013， 56（7）：1-10.
[13] 孙彦清， 彭舰， 刘唐，等. 基于动态分区的无线传感器网络非均匀成簇路由协议[J]. 通信学报， 2014， 35（1）：198-206.（SUN Y Q， PENG J， LIU T， et al. Uneven clustering routing protocol based on dynamic partition for wireless sensor network[J]. Journal on Communications， 2014， 35（1）：198-206.）
[14] GNAWALI， OMPRAKASH， FONSECA， et al. Collection tree protocol[C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. New York： ACM， 2009：1-14.
[15] SALEEM F， MOEEN Y， BEHZAD M， et al. IDDR： improved density controlled divide-and-rule scheme for energy efficient routing in wireless sensor networks[J]. Procedia Computer Science， 2014， 34（7）：212-219.
[16] RAZA W， KHAN I， ARSHAD F， et al. THEEM： threshold-sensitive energy efficient multi-hop routing protocol for WSNs[C]// Proceedings of the 2014 Ninth International Conference on Broadband and Wireless Computing， Communication and Applications. Piscataway， NJ： IEEE， 2014：20-25.
[17] TUNCA C， ISIK S， DONMEZ M Y， et al. Ring routing： an energy-efficient routing protocol for wireless sensor networks with a mobile Sink[J]. IEEE Transactions on Mobile Computing， 2015， 14（9）： 1947-1960.
[18] PANT M， DEY B， NANDI S. A multihop routing protocol for wireless sensor network based on grid clustering[C]// Proceedings of the 2015 Applications and Innovations in Mobile Computing. Piscataway， NJ： IEEE， 2015：137-140.
[19] PEI E， HAN H Z， SUN Z H， et al. LEAUCH： low-energy adaptive uneven clustering hierarchy for cognitive radio sensor network[J]. EURASIP Journal on Wireless Communications & Networking， 2015， 2015（1）：122.
[20] 白乐强， 王玉涛. 基于非均匀分簇机制的ZigBee混合路由算法[J]. 计算机应用， 2016，36（1）：81-86.（BAI L Q， WANG Y T. ZigBee hybrid routing algorithm based on uneven clustering mechanism[J]. Journal of Computer Applications， 2016，36（1）：81-86.）
[21] MAMMU A S K， UNAI H J， NEKANE S， et al. Cross-layer cluster-based energy-efficient protocol for wireless sensor networks[J]. Sensors， 2015， 15（4）：8314-8336.