一种基于能量感知的无线传感器网络混合路由协议*

刘广聪，陈平华，胡志斌

（广东工业大学计算机学院，广东广州 510006）

0 引言

为了延长整个网络的生存期，无线传感器网络的路由协议不仅关心单个节点的能量消耗，更要考虑整个网络能量的均衡消耗。无线传感器网络的路由协议分为三大类:平面路由协议、层次化路由协议及地理位置路由协议。在平面路由协议中，靠近Sink的节点在执行本身任务的同时还作为路由节点为远离Sink的节点转发数据，能量会很快耗尽而引起网络瘫痪，从能源有效性角度来看，平面路由协议并不适用于大规模密集部署的无线传感器网络［1，2］。层次化路由协议分簇算法的簇头是随机产生的，无法约束簇头的位置，不能保证簇头节点的均匀分布。如果节点密集处产生多个簇头会形成簇头冗余而造成能量的不合理开销，并导致某些节点不属于任何簇而处于孤立状态，使节点的数据无法到达Sink节点［3］，低功耗自适应集簇分层型［4］（low energy adaptive clustering hierarchy，LEACH）协议是一种典型的分层路由协议。文献［5］中提出的PEGASIS协议是一种地理位置路由协议，它借鉴了LEACH中聚簇的思想，文献［6］对这类协议给出类似于旅行商问题。

无线传感器各个节点可能具有不同的特性和初始条件（即异构节点），由于网络中各节点的资源局限性、移动性及不稳定性，要求路由协议具有可靠的链路发现和良好的路由节能能力。路由协议中各节点的能量保持与感知方法是路由协议设计的第一考虑要素，基于能量有效性的路由［7］利用剩余能量信息验证能量的有效性。本文针对能量有效性路由的不足，采用节点信号强度与阈值感应分数建立路由链路，使路由信息验证效率更高。

1 分布式数据处理模型

1．1 数据处理方式

常见的典型场景是具有N个节点的网络，每一个节点可以收集到M个测量数据。如果需要这些测量值的平均值，存在3种方法获取数据［8］:

1）节点将所有的数据发送给中央处理器，由中央处理器进行计算。假设每次采样的 bit数一定，则需要有O（MN）bit需要传输，其传输距离为固定长度，不受网络属性的影响，即为O（1）。

2）传感器节点首先计算自己的平均值，然后再将平均值传输给中央处理器，由它计算最终的平均值。显示需要O（N）bit需要传输，传输距离与第1种方法相同。

1．2 能耗分析

上述无线传感器网络的数据处理方式可分为集中式数据处理与分布式数据处理。对于多跳通信方式，其计算能源消耗模型为ε（n）=c（n）×h（n）×e（n），其中，c（n）为传输的bit数目，h（n）为传输的平均跳数，e（n）为每一跳传输1bit需要消耗的能源。

1）集中式算法的能耗计算

2）分布式算法的能耗计算

通过数据量和能耗分析比较可见，对于大规模无线传感器节点的网络，分布式算法比集中式算法整体上更具优越性。

2 混合路由协议算法

本文采用分布式数据处理方式，在路由协议的构建中，把网络中的每个节点接收信号级值设定为若干个梯度值如下所示

每个梯度代表一个级别的节点通信强度值。

2．1 路由建立

考虑一个节点数为N的网络，把整个网络看成是一个无向图G=（V，E），V表示图中顶点的集合，E表示图中边的集合。N（i，j）表示节点N（i，j）的下一跳邻居节点j的集合，其中，i，j∈V。w（u，v）表示边（u，v）的权值（两节点间的信号强度值SI），其中，边w（u，v）∈E。Sink节点向周围的传感器节点发起通信请求时，Sink节点开始其路由过程。

构造一个Sink节点到源节点s的路由。图1中Sink节点用s表示，实线上的数字标号表示该节点感知上一跳节点的信号强度（即SI值）。Sink节点首先广播数据信息请求包（DRREQ）到邻居节点集N（i，j）={i，j;i，j∈V}，在节点i，j收到DRREQ后，立即查看其Rid是否过期，如没有则继续查看所需信息是否自己所载信息，若是则给Sink节点数据应答包（DRREP）;若Rid没有过期且所需信息不是自己所载信息，则继续向图中的k，u节点路由，由于节点k，u并没有携带Sink节点所需信息，继续向其邻居节点集N（u，ov）和N（k，vw）转发，当节点o，v，w收到 DRREQ 并检测到自己都载有Sink节点所需的部分信息时，选取首个SI值最大的节点v作为簇头节点并告知其邻居节点o，p，w，q，用于v收集整合Sink节点所需的信息。当节点o，p，w，q收到节点v的DRREQ信息时，将各自携带的部分信息按要求返回给簇头节点v，节点v将这些信息进行整合后按保存路由路径（s，i，k，u，v）的反转路径返回 Sink 节点所需信息。

图1 路由建立Fig 1 Routing setup

2．2 路由维护

本文的路由维护采用“最少修改原则”，如某链路出现了问题，该链路的始端节点广播一个在线节点探寻信号ONCI，在该节点收到其邻居节点返回的应答信号PACI时，继续转发给Sink节点，查看返回给PACI的应答节点是否在该链路的路由表中，若在，则将该节点加入到路由表的path中，修改从Sink节点到节点v的路由，更新路由表。

图2详细说明了该协议的路由维护。假设某时刻节点k已退出网络（睡眠或关机等），此时Sink节点向节点v查询相关信息，在Sink节点按路由表中的路径发送试探信号后，由于节点k不能正常工作，链路R（i，k）和E（k，u）相继中断，使得节点v接收不到Sink节点的试探信号CI，也无法返回相关的应答信号PACI。于是路由表中首先被中断的链路E（i，k）的始端节点i，广播一个在线节点探寻信号ONCI给其邻居节点u，节点u在收到信号ONCI后，经节点i返回给Sink节点一个应答信号PACI，由“最少修改原则”将节点i加入路由表替换节点k，同时置SI值为最大进行该链路的维护。

图2 路由维护Fig 2 Routing maintenance

3 协议仿真与分析

比较 DECDC 协议［10］、文献［11，12］中的协议，采用NS—2和Matlab软件从簇头的生成效率、成功数据交付率、网络负载及平均能量消耗等四方面进行评估与分析。

3．1 仿真环境

在仿真实验中，传感器节点被部署在一块500 m×500 m的矩形目标区域中，为了更好地与其他协议进行比较和分析，仿真忽略由信号碰撞和无线信道干扰等随机影响带来的干扰。实验参数设置如表1所示。

表1 仿真参数表Tab 1 Parameters of simulation

3．2 仿真结果与分析

从图3可以看出:本协议的簇头生成效率在节点密度为20以后明显高于其他3种协议，原因是其他3种协议在整个网络的通信中都是先成簇，再由簇头负责其区域内的数据采集、整合，然后将信息传回给Sink节点。本文方法采用“尽力而为”和“不得已而为”的思想，采用Sink节点一次通信从某个节点获取所需的全部信息，直接把信息返回给Sink节点，如果失败，再以路由过程中SI值最大的节点动态自适应生成簇头进行局部的信息采集和整理，最后将信息传回Sink节点。

图3 簇头节点生成率Fig 3 Production rate of cluster head node

如图4所示，正是本文这种“尽力而为”方式，在成功传输数据方面显得更为有效。其他3种协议考虑到合理的簇头分布，算法较为复杂，增加了网络通信量。文献［12］计算存储空间大，但一旦路由建立数据交付率就很高，从图4看出:在网络存活节点达80之后文献［12］高于其他3种协议，随着节点数和无线通信量的增加，所有协议的数据传递率也逐渐下降。

图4 成功报文交付率Fig 4 Successful packet delivery rate

图5是4种协议的能耗比较。DECDC协议需时刻关注每节点到簇头的距离和每节点的位置，这在节点逻辑位置不确定性的自组网中，需要消耗网络大量的能量;文献［11］采用基于网格算法来产生簇头和路由，其计算量也相对较大;文献［12］主要能耗是节点建立生成树的计算和簇头节点路由的消耗，相对前2种协议能耗小。从仿真结果可知，本文相对简单的簇头产生算法和节点状态约束，使节点的休眠、关机和失效对通信没有影响，可扩展性好。

图5 网络能耗Fig 5 Energy consumption of network

4 结论

本文以剩余能量和节点间距离为参考因子的簇头产生算法，把感知节点剩余能量强度和“尽力而为”的方法用于簇头选择和网络数据查询，避免了先成簇再路由的某些缺陷。仿真实验结果表明:本协议的簇头产生效率和数据交付成功率高，能有效降低节点能耗。

［1］ 崔 莉，鞠海玲，苗 勇，等．无线传感器网络研究进展［J］．计算机研究与发展，2005，42（1）:163 －174．

［2］ 唐 勇，周明天，张 欣．无线传感器网络路由协议研究进展［J］．软件学报，2006，17（3）:410 －421．

［3］ Manjeshwar A，Agrawal D P．TEEN:a routing protocol for enhanced eficiency in wireless sensor networks［C］∥Proceedings of the 15th International Parallel and Distributed Processing Symposium，San Francisco，2001:2009 －2015．

［4］ Heinzelman W，Chandrakasan A，Balakrishnan H．Energy-efficient communication protocol for wireless microsensor networks［C］∥Proc of the 33rd Annual Hawaii Int’1 Conf on System Sciences，Maui:IEEE Computer Society，2000:3005 －3014．

［5］ Lindsey S，Raghavendra C S．PEGASIS:Power-efficient gathering in sensor information systems［C］∥Proceedings of the IEEE Aerospace Conference，New York:IEEE Press，2002:1125 －1130．

［6］ 蔡海滨，琚小明，曹奇英，等．多级能量异构无线传感器网络的能量预测和可靠聚簇路由协议［J］．计算机学报，2009，32（12）:2393－2402．

［7］ Chatterjea S，Nieberg T．A distributed and self-organizing scheduling algorithm for energy-efficient data aggregation in wireless sensor network［J］．ACM Trans on Sensor，2008，4（4）:20—1—20—4．

［8］ Shakkottai S．Asymptotics of search strategies over a sensor network［J］．IEEE Trans on Automatic Control，2005，50（5）:594 －600．

［9］ Intanagonwiwat C，Govindan R，Estrin D．Directed diffusion:A scalable and robust communication paradigm for sensor networks［C］∥Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking，Boston，2000．

［10］ Jing Weipeng，Liu Yaqiu．DECDC:An energy-aware route protocol for wreless sensor networks［C］∥The 2nd Internation Symposium on Systems and Control in Aerospace and Astronautics，Shenzhen，2009:1－6．

［11］ Liu Shu，Zhuang Yanyan．Grid-based energy-aware routing in wireless sensor networks［J］．Journal of Southeast University:English Edition，2009，25（4）:445 －450．

［12］ Karthickraja N P，Sumathy V．A study of routing protocols and a hybrid routing protocol based on rapid spanning tree and cluster head routing in wireless sensor networks［C］∥International Conference on Wireless Communication and Senesor Computing，Chennai，2010:1 －6．