楼宇WSN 能量均衡路由算法

尚志文，李晓卉，赵 兵，梁晓兵

（1.武汉科技大学 信息科学与工程学院，湖北 武汉430081；2.中国电力科学研究院，北京100192）

0 引 言

如何设计更加优化的楼宇无线传感器网络 （wireless sensor networks，WSN）［1，2］路 由、平 衡 网 络 能 量 消 耗 是 降低楼宇WSN 节点的能耗、延长网络生存期的重要问题。

WSN 路由主要分为两个大类，分簇路由［3］和平面路由［4，5］。分簇路由是以LEACH 算法为代表的一系列WSN分簇路由，该算法簇头选择随机性太大，若簇头相距过近或者簇头处于网络边缘，则部分远离簇头的节点容易能耗过大而提前死亡［6］，并且该算法通常应用在大规模WSN中，而楼宇WSN 属于小型WSN。以AODVjr协议［7］和DD协议［8］等为代表的平面路由协议主要都是通过发现一条距离最短、能耗最小的路径来路由数据包，但是单条路径能耗最小并不代表能延长整个WSN 的生命期，倘若频繁地使用同一条路径，会使该条路径上的节点过早耗尽电能，从而缩短了整个网络的生命期。

为解决以上问题，本文提出一种适用于楼宇WSN 的能量均衡路由算法 （energy－balancing routing for WSN using in building，EBR－WSNB）。该算法在平面路由协议的基础上，引入路由负载的概念，通过路由负载值修改路由表，使网络达到负载均衡，延长整个网络生命期。

1 网络模型

本文旨在研究楼宇WSN［9］，其特点是该网络模型是由一个汇聚节点和m 行n 列的N（N＝m×n，其中m、n 均为大于2的正整数）个节点组成的网络。假设有一栋3层高的楼宇即m＝3，每层楼4个房间即4个无线传感器节点，n＝4。采用ZigBee布网［10］，协调器 （coordinator）位于中间楼层的最顶端，用于运行路由算法、控制整个网络以及采集网络数据。因此该网络模型可等效为3行4列一共12个节点和一个汇聚节点的网络，如图1所示。

图1 3行4列的楼宇WSN 拓扑结构

从图1所示的网络模型可以看出，该网络是一个布局规则的网络。在实际生活中，楼宇WSN 中各个节点位置相对固定，因此它们都可以等效成与图1类似的规则网络。

2 楼宇WSN 能量均衡路由算法 （EBR－WSNB）

2.1 路由负载 （RL）

有关研究结果表明，WSN 中处理器和各种传感器模块的功耗随着技术的进步越来越低，无线通信模块是WSN 中最消耗能量的部分［11］。而节点的能耗则与路由的数据包数量有关，一个节点路由的数据越多，消耗的能量就越多，这必然导致网络中各个节点能耗不均衡。

为了更清楚的观察节点能耗，本文定义路由负载RL（routing load）来衡量通过某个节点i的数据包量占路由数据包总量的比例。楼宇WSN 中内层节点既要发出本节点的数据包，又要接收并转发上一跳节点上传的数据包，而终端节点只发出本节点数据包，因此节点i的路由负载RLi的数学模型应该由两部分组成

式中：Di——节点i每秒路由的数据包数目；li——节点i所在网络层数depth；iLH——节点i的上一跳节点的集合；x——节点i的上一跳节点的集合中的一个节点；xNH——节点x 的下一跳节点；RLx——节点x 的路由负载；NxNH——节点x 的下一跳节点个数，N——子节点的总个数。

需要注意的是，由式 （1）可以看出，计算某个节点i的RLi需要先计算出该节点的上一跳节点的RLx值，所以计算时应从终端节点逐层往上层计算。

假设在如图1 所示的网路中运行ZigBee 网络中的AODVjr路由算法找到了一条最短路径，设定每个节点每秒发出一个数据包。下面计算depth＝3 层的各个节点的RL值

从上面的计算结果可以看出，除了根节点所在层以外，同层节点的路由负载不均衡，同理可以算出其它层节点路由负载也是如此，因为中间部分节点的上一跳节点数较多，负载的数据包也就相对较多，自然就会消耗更多能量，造成网络能量消耗不均衡的现象。

2.2 EBR－WSNB算法步骤

为了平衡楼宇WSN 中各个节点的能耗，需要有效均衡WSN 中节点的RL。因此本文提出一种通过减少网络逻辑链路达到修正RL的方法来建立路由表。

EBR－WSNB算法实现过程如下：

（1）算法初始化

初始化网络，汇聚节点在收集到网络拓扑信息后，将网络配置成m 行n 列的基本的网络拓扑，并在每个节点的路由表中添加 “路由次数”条目。

（2）建立优化的网络拓扑

在初始网络拓扑的基础上，根据式 （1）计算每层各个节点的RL，并计算该层各个节点RL 值的方差基本值。利用RL值的方差来判断当前层的负载是否均衡，方差越小则表示本层各个节点的RL 值越相近，本层节点的负载也就越均衡。RL的方差越大说明当前层负载不均衡。此时若每层只存在一个RL最大的节点，需要将该RL最大的节点与其上一跳节点间的逻辑链接依次删除，删除后重新计算本层各节点的RL 和方差，如果方差达到最小，则保存此时的路由表，如果方差没有达到最小，则恢复之前路由表，重复进行删除操作，直到删除某条逻辑链路之后，当前层节点的RL 值的方差达到最小时，保存此时的路由表；若每层存在两个以上RL 最大的节点，则对除去最高一行和最低一行以外的所有中间行节点同时进行上述删除操作，直到当前层节点的RL 值的方差达到最小时，保存此时的路由表。

（3）数据传递

无论是发送数据包还是接收数据包，都要在发送和接收到数据包的节点的路由表的 “路由次数”条目上加1，节点向下一跳节点发送数据包时，优先选择 “路由次数”最小的节点进行传递，若存在两个以上 “路由次数”最小的节点，则依次选择进行传递。

EBR－WSNB算法如图2所示。

图2 EBR－WSNB算法

该算法的核心是删除了负载最大的节点的逻辑链接之后，同层节点的RL 值会相对均衡，按新的网络逻辑链接更新路由表。由于设备可能随机的选择可以连接的下一跳节点，节点每发送或者接收一次数据包，就在 “路由次数”条目上加1计数，当某个节点要选择下一跳节点时，优先选择 “路由次数”小的节点连接，即剩余能量较多的节点进行传输，即可进一步达到能耗均衡。

将以上算法应用到图1所示网络中，对于depth＝1层的节点，节点2的RL 值最大，依次删除节点2与节点4、节点5和节点6的逻辑链接，并重新计算各个节点的RL和该层各节点RL 的方差，最后由计算结果可以看出，在删除节点2和节点5的逻辑链接后，depth＝1层的节点的RL的方差达到最小，因此保存移除节点2和节点5的逻辑链接之后的路由表，以此类推，对depth＝2和depth＝3层的节点也进行以上操作，直到depth＝2和depth＝3层中的节点的RL都达到相对均衡即方差最小后，保存路由表，即可得到如图3所示的网络拓扑结构。

图3 运行EBR－WSNB算法之后的网络拓扑

计算图3所示网络拓扑结构中各个节点的RL值，并且将其与AODVjr算法即图1所示网络拓扑结构相比，结果见表1。

表1 AODVjr算法与EBR－WSNB算法RL值对比

通过表1可以看出在AODVjr算法中，depth＝4层的节点RL 值相同，因为它们没有上一跳节点。越往高层，RL值相对越大，即消耗的能量就越多，因为内层累积数据量越来越大。节点2、节点5和节点8的RL 值分别大于与它们同层的其它两个节点，因为它们可连接的上一跳节点数较多，正因为如此，节点2、节点5和节点8耗能就会比跟它们同层的其它两个节点更快，所以就造成了网络能量消耗不均匀的现象，最终就会导致整个网络过早瘫痪。这就是传统AODVjr算法应用在此网络中的缺陷。

由表1可以看出EBR－WSNB算法明显均衡了网络各层中节点的RL，使各层中的各个节点可以均衡消耗能量，但是它在降低中间节点RL 值的同时，增大了该层其它节点的RL值，这是由于其它节点分担负载导致的，而每层以及整个网络的路由负载总量并没有改变，由此说明，整个网络耗能总量是没有变的，该算法只是均衡了负载，从而达到延长网络生命期的目的。

3 算法仿真

3.1 仿真场景及参数

本文仿真的实验场景是一座3层高的教学楼，每层楼4个教室，每个教室一个ZigBee传感器节点，而coordinator安装在中间楼层即第二层的最顶端。初始网络拓扑如图1所示。传感器运行过程中，每秒发送一个数据包。每个节点的初始能量为2J，每发送一个数据包耗能1mJ，每接收一个数据包耗能0.5mJ，直到任何一个节点耗尽能量为止结束仿真。实验通过对比本文算法和AODVjr算法性能，验证本文算法的优越性。

3.2 仿真结果分析

3.2.1 网络生命期比较

分别在仿真场景中运行AODVjr算法和EBR－WSNB算法，直到出现第一个耗尽能量的节点为止，记为整个网络的生命期，仿真结果见表2。

表2 网络生命期对比

通过表1和表2可以看出，虽然整个网络耗能总量没有变，但是通过EBR－WSNB算法使各个节点分担路由量，能量得以均衡消耗，从而整个网络生命期有了大幅度的提升。

3.2.2 各节点耗能比较

由表2知，在AODVjr算法下，该仿真网络生命期只有157s，下面对比两种算法在第157s时各个节点的能耗总量。如图4所示。

由图4 可以看出，AODVjr算法下，各层中各个节点的能耗非常不均衡，正因为如此，才会出现某个节点提前耗尽能量而 “死亡”的现象，从而导致整个网络瘫痪。正如图4中的节点1，在第157s已经耗尽能量，而与它同层的节点3耗能却还很少，节点1 “死亡”之后，尽管它的上一跳节点还可以选择其它的路径传递数据，但是之后整个网络的数据全都负担到了节点2和节点3上，加速了它们的能量消耗，整个网络也会很快陷入瘫痪。然而在EBRWSNB算法下，各层中各个节点能耗均衡，不会出现某一个节点提前耗尽能量的现象，从而整个网络生命期得以延长。

图4 在第157s时两种算法下各节点耗能量比较

3.2.3 网络节点数变化影响比较

本文前面的讨论和仿真都建立在3 行4 列的网络中，实际应用中网络规模可能更大。在上面仿真场景其它条件不变的情况下，增加网络节点个数，然后在比较两种算法下网络生命期，结果如图5所示。

图5 节点数变化对网络生命期的影响

从图5可以看出，随着网络节点数的增加，网络生命期逐渐减小，因为节点数越多，网络数据量越大，越靠近汇聚节点的节点路由负载越大，自然耗能就越快。但是无论节点数怎么变化，整个网络在本文所述的EBR－WSNB算法下比传统的AODVjr算法网络生命期长，体现了本文所述算法的优越性。

需要说明的是，当楼层过高时，若把汇聚节点安放在中间楼层，上、下部分楼层将连接不到汇聚节点，这时需要在depth＝1 层节点与汇聚节点之间再安置足够数量的router保证数据能顺利传送到汇聚节点。

4 结束语

本文提出一种基于路由负载RL 的路由建立算法，该算法通过更新RL 值动态修改路由表达到能量均衡的路由选择。算法仿真结果表明，相比于传统的AODVjr路由算法，该算法在楼宇WSN 中能更好的均衡网络能量消耗，延长网络生命期。

不可忽略的是，该算法是以较大的路由表的存储空间换取网络生命期的延长，在算法运行过程中要执行一定的运算，因此未来将进一步简化运算过程并在实际的楼宇网络中验证算法的有效性。

［1］ZHAO Wenjing，QIN Huibin，WU Jianfeng，et al.The design of intelligent building environment monitoring system based on ZigBee technology ［J］.Mechanical and Electrical Engineering，2010 （8）：114－117 （in Chinese）.［赵文静，秦会斌，吴建锋，等.基于ZigBee技术的智能楼宇环境监测系统的设计［J］.机电工程，2010 （8）：114－117.］

［2］LEI Juan，CHEN Yang.The applications of sensors in intelligent building ［J］.Silicon Valley，2012 （2）：116 （in Chinese）. ［雷娟，陈阳.传感器在智能楼宇中的应用 ［J］.硅谷，2012 （2）：116.］

［3］Liu X.A survey on clustering routing protocols in wireless sensor networks［J］.Sensors，2012，12 （8）：11113－11153.

［4］Saravanan T，Saritha G，Srinivasan V.An analysis of flat routing protocols in sensor N／W ［J］.Middle－East Journal of Scientific Research，2014，20 （12）：2566－2570.

［5］LI Yuntao，ZHU Min，LIU Haolin，et al.Wireless sensor network routing algorithm based on energy equilibrium ［J］.Journal of Sichuan University （Natural Science Edition），2012（1）：69－74 （in Chinese）.［李运涛，朱敏，刘昊霖，等.基于能量均衡的无线传感网络路由算法 ［J］.四川大学学报 （自然科学版），2012 （1）：69－74.］

［6］CHEN Xiaojuan，WANG Zhuo，WU Jie.An improved WSN routing algorithm based on LEACH ［J］.Journal of Sensing Technology，2013 （1）：116－121 （in Chinese）. ［陈晓娟，王卓，吴洁.一种基于LEACH 的改进WSN 路由算法 ［J］.传感技术学报，2013 （1）：116－121.］

［7］Niu Yingqi，Bie Hongxia.An improved AODVjr algorithm for extending network lifetime［C］／／3rd IEEE International Conference on Network Infrastructure and Digital Content，2012：18－21.

［8］Tang Junhua，Dai Sisi，Li Jianhua，et al.Gossip－based scalable directed diffusion for wireless sensor networks ［J］.International Journal of Communication Systems，2011，24 （11）：1418－1430.

［9］Ahamed SI，Wang W，Hong J.Recent advances in energy－efficient sensor networks ［J］.International Journal of Distributed Sensor Networks，2013.

［10］Guo X，Liu H，Zhou P，et al.Design of building energy consumption monitoring system based on ZigBee technology［J］.Computer Measurement ＆ Control，2011，19 （3）：551－553.

［11］MENG Xiaoyan.Simulation of wireless sensor network communication node optimization selection algorithm ［J］.Computer Simulation，2013，30 （2）：205－208 （in Chinese）.［孟小艳.无线传感网络通信节点优化选择算法仿真 ［J］.计算机仿真，2013，30 （2）：205－208.］