徐晓旭 图雅

摘  要： 在无线传感网络中，节点的资源限制给路由协议的设计提出了挑战。在高数据率应用场景中，带宽和存储容量成为其主要问题。为此，提出基于多信道协作负载均衡算法（M?CoLBA）的路由协议来提升网络带宽，并避免因队列溢出导致的数据包丢失。M?CoLBA协议先利用拥塞感知的动态路由度量均衡流量负载，再依据队列时延选择下一跳转发节点。实验数据表明，与单一信道路由协议（S?CoLBA）和多信道协议（M?HopCount）相比，提出的M?CoLBA协议具有较高的数据包传递率。

关键词： M?CoLBA; 无线传感网络; 路由协议; 多信道; 负载均衡; 队列时延; 数据包丢失

中图分类号： TN919.2?34; TP393                     文献标识码： A                  文章编号： 1004?373X（2019）09?0005?06

Multichannel collaborative load balancing?based routing protocol

used in wireless sensor networks

XU Xiaoxu， TU Ya

（College of Mechanical and Electrical Engineering， Inner Mongolia Agricultural University， Hohhot 010018， China）

Abstract： The design of routing protocols is challenged by limited node resources in wireless sensor networks （WSNs）， and the bandwidth and storage capacity become its main obstacles when WSNs are used in high data rate application scenarios. Therefore， the multichannel collaborative load balancing?based algorithm （M?CoLBA） routing protocol is proposed to promote the network bandwidth， and avoid the data packet loss caused by queue overflow. The dynamic routing metric with congestion perception is used in M?CoLBA protocol to balance the traffic load， and then the next?hop forwarding node is selected according to queue delay. The experimental data shows that， in comparison with S?CoLBA protocol and M?HopCount protocol， the proposed M?CoLBA protocol has higher data packet transfer rate.

Keywords： M?CoLBA; wireless sensor network; routing protocol; multichannel; load balancing; queue delay; data packet loss

0  引  言

无线传感网络（Wireless Sensor Networks，WSNs）已广泛应用于各个领域，如环境、工业。对于不同的应用，对WSNs的性能要求也不同。对于低数据率、小型智能家居的应用，依据ZigBee标准[1]就可满足要求。然而，其他应用可能受端到端时延的限制，如工业应用、数据采集与监视控制系统（Supervisory Control and Data Acquisition，SCADA）。而有些应用具有高数据率要求[2?4]，如视频监视、振动测量。

此外，IEEE 802.15.4标准已广泛应用于低功率低损网络（Low Power and Lossy Networks，LLNs），如WSNs。当将此标准应用于共享、未注册2.4 GHz带宽时，可提供250 Kb/s的链路吞吐量。然而，此带宽也被其他通信技术使用[5]，如IEEE 802.11（WiFi）和IEEE 802.15.1（藍牙）。不同技术共存于同频带宽就导致网络间干扰和碰撞，最终会引起数据包丢失和网络性能的下降。而利用多信道通信技术有助于减少网间干扰和网内干扰。如多信道媒体接入协议（Medium Access Control，MAC）有助于提高吞吐量，也增加了数据流量负载[6]。但是，高流量负载容易导致拥塞，也可能会引起数据包队列溢出。

目前，为了提高WSNs的性能，研究人员提出不同的多信道协议。如文献[7]提出的基于多信道MAC的负载平衡路由，旨在平均所有潜在链路的流量负载。然而，该路由是针对无线Mesh网络，并没有考虑到WSNs的特性。此外，文献[8]也提出面向单跳多信道WSNs的认知负载平衡算法。该算法利用网络基站情况的负载分布选择通信信道，这利于降低部分信道过载的概率。然而这些算法均是针对单跳WSNs。由于多跳WSNs的复杂性，现有的这些算法难以直接应用于多跳WSNs环境。

此外，在WSNs中的多对一（也在文献中称为融合）通信是非常普遍的。在具有融合的重流量场景中，需要先融合来自叶节点的数据，再将融合后的数据传输至信宿。依据不同的路由策略[9]，一些节点可能超载，而其他节点可能轻负载。而超负载节点可能经历队列溢出和数据丢失。

为此，针对多跳WSNs，本文提出基于多信道协作负载均衡的路由协议（Multichannel Collaborative Load Balancing?based routing，M?CoLBA）。M?CoLBA算法引用新的动态度量平衡流量负载，目的就是解决因队列溢出而导致的拥塞和数据包丢失问题平衡网络吞吐量。同时，利用WSNs中的多信道MAC协议提高吞吐量。

M?CoLBA通过利用拥塞感知动态路由，避免拥塞和队列溢出问题，进而平衡所有潜在下一跳邻居节点间的数据流量。在MAC层，M?CoLBA协议利用半动态信道分配的多信道协议;网络层引用基于平均数据包队列时延的拥塞感知动态路由。实验数据表明，提出的M?CoLBA路由平衡了流量，提高了数据包传递率。

1  M?CoLBA协议

M?CoLBA协议先通过交互beacon包发现邻居节点，一旦建立邻居节点集后，就进入数据传输阶段。换而言之，每个节点的活动周期可划分为beacons阶段和数据阶段，如图1所示。beacons阶段交互beacons包，数据阶段传输数据。

图1  节点活动周期

此外，M?CoLBA协议引用具有三个无线接口的信宿，使得信宿从不同信道同时接收数据。

1.1  发现邻居

通过发现邻居节点，可避免已被邻居节点使用的信道。因此，网络内除信宿外的所有节点必须发现一跳 （1?hop）、二跳（2?hop）和三跳（3?hop）邻居节点。利用beacon包发现这些邻居节点。每个节点先利用它从邻居节点接收的数据包建立1?hop邻居集。然后，将1?hop邻居集载入beacon包，再广播。一旦接收了此包后，节点就能建立2?hop邻居集。再将2?hop邻居集载入beacon包中，并广播此包。接收到此包的节点就能建立3?hop邻居节点集。

然而，在网络内难免会出现孤立节点。通常将一跳范围内无邻居节点的节点称为孤立节点，即一跳邻居集为空。对于此类节点，采用存储?转发机制。一旦孤立节点需要传输数据，它先存储数据包，直至遇到节点才进行转发。

1.2  信道分配

在最初的建立阶段，给每个节点分配一个2 B整数的唯一ID号。ID号对节点选择信道有重要影响。最初依据节点进入网络的时间进行编号，最先进入的节点的ID号最小，最后进入的节点的ID号最大。在选择信道时，在同等条件下，具有最小ID号的节点最先接入信道。下文将进一步分析。

节点依据ID号、有序方式选择信道。首先，由3?hop邻居节点中具有最小ID号的节点先选择信道[10?11]。只要它的前任（predecessor）没有宣布它所选择的接收信道，节点就不能选择信道。一个节点的predecessor是该节点的1?hop、2?hop和3?hop邻居节点中ID号离自己最近，且比自己ID号小的节点。值得注意的是，本文从3跳范围避免冲突，原因在于文献[12]所分析的：3?hop邻居节点重复使用信道会导致碰撞。通过扩大避免冲突范围，降低信道碰撞率。

例如，如图2所示节点8的1?hop，2?hop和3?hop邻居节点为4，5，11，14，15，16和27。因此，节点5是节点8的predecessor。在节点5选择信道之前，节点8不能选择接收信道。

当在同一个网络内使用多个信道时，每个节点必须知道它的邻居所选择的信道，否则容易导致信道碰撞和拥塞。这就要求邻居节点间相互共享信道分配信息。M?CoLBA协议分配信道的目的就是尽可能地避免邻居节点重复使用同一个信道。

图2  节点的predecessor示意图

首先，每个节点从1?hop，2?hop和3?hop邻居节点内寻找未使用的信道。如果没有未使用的信道，再从1?hop，2?hop邻居节点集内选择未使用的信道。如果在1?hop，2?hop邻居集内所有信道已被使用，则节点就只从1?hop邻居集内选择可用信道。如果没有可用信道，就从1?hop邻居集内选择重复使用率低的信道。

依之前所提到的，作为特殊节点，信宿具有3个无线接口。信宿首先選择三个接收信道，然后在beacon包内广播此信息。随后，没有predecessor的节点就选择它们的接收信道，再在beacon包内广播它们的选择。此过程一直重复，直到网络内所有节点选择它们的接收信道。

1.3  路由指标

WSNs中的节点通信范围是有限的，而作为数据包的目的节点，信宿可能不在网络内多个节点的通信范围内。这就要求通过多跳通信才能完成数据的转发。通过连续地选择下一跳节点，进而构成多跳通信。M?CoLBA协议将平均媒体接入时延作为路由指标，并依据此指标选择路由。

由于信宿的1?hop邻居节点能够与信宿直接通信，它们不需要选择下一跳转发节点。当它们完成了信道分配后，信宿的1?hop邻居节点就进入数据传输阶段，并开始向信宿传输数据。致使它们必须从信宿的三个接口中选择一个接口，然后再切换至该接口的接收信道。为了避免多个节点选择同一个接收信道发生碰撞，M?CoLBA协议引用CSMA/CS策略接入信道。

非信宿的1?hop邻居节点必须要选择下一跳转发节点，才能完成数据的转发。M?CoLBA协议通过时延选择下一跳转发节点。具体而言，节点将所产生的或需要转发的数据压入数据包队列中，然后再利用先进先出（FIFO）的原则传输数据包。利用节点局部时钟记录数据包压入数据包队列的时间和出列时间。这两个时间差就是数据包队列时延。

将最近10个数据包的队列时延称为该节点时延[d]。如果节点队列中没有10个数据包，则节点时延就等于已出列数据包的平均时延。如图3所示，设最近5个数据包的队列时延的权重为2，将其他5个数据包队列时延权重设为1。换而言之，最近数据包的队列时延对节点时延的影响更大，这也符合实际情况。因为最近队列时延反映当时的网络条件。因此，节点时延定义如下：

式中：[queueing delay（i）]为第[i]个数据包队列时延;[λ]，[β]分别表示两类时延的权重，在仿真中考虑它们对总时延比重相同，因此，各取为0.5。

一旦节点已出列了10个数据包，它就利用滑动窗口记录最近的10个数据包。此外，值得注意的是，選用10个数据包的平均时延作为节点时延，原因在于连续10个数据包时延能够反映情况，如果选用的数据包过少，就不能反映网络环境的真实情况;若选用过多的数据包，必然增加了统计开销。此外，通常节点缓存区域过小，也无法存储过多的数据包。

图3  节点的队列时延

估计完节点时延后，再估计路径时延[D]。估计路径时延的原则如下：信宿的1?hop邻居节点路径时延等于节点时延。如图4所示。信宿节点[A]的一跳邻居节点[B]，[F]，[C]连通节点[A]的路径时延等于它们的队列时延。例如，节点[B]的队列时延[d=8]、路径时延[D=8]。

图4  路径时延

信宿的一跳邻居节点利用beacon包自己的路径时延。当二跳邻居节点接收了此beacon包，就从一跳邻居节点中选择路径时延最小的节点作为下一跳转发节点。那么，该节点连通信宿的路径就等于自己的队列时延加上一跳邻居节点的路径时延。例如二跳邻居节点[G]，它选择[F]作为自己的下一跳节点，因为[F]离信宿的路径时延最短。节点[G]连通信宿的路径时延[D=7+4=11]。

2?hop邻居节点也广播自己的路径时延，它的叶节点（3?hop节点）接收后，再计算自己连通信宿的路径时延。直到网络内所有节点已获取了离信宿的最短时延路径。

1.4  队列溢出的避免策略

依据网络拓扑，每个节点可能有多个连通信宿的下一跳节点。M?CoLBA协议选择路由的原则是：选择路径时延最短的路径传输数据。然而，总是以最小时延选择下一跳节点在密集网络中会发生振动[11]。为此，M?CoLBA协议中除了信宿和一跳邻居节点外，其他节点需要建立top?list邻居节点集。top?list内包含了最小路径时延[Dmin]的邻居节点。同时，M?CoLBA协议规定top?list也包含比最小路径时延[Dmin]最多大于2 ms的路径[13]。为了避免top?list的下流节点，允许2 ms路径时延，进而保证无循环路由。

因此，为了避免振动，每个节点从top?list中随机选择一个邻居节点作为下一跳转发节点。以图4为例，节点[H]有三个潜在的下一跳转发节点[B]，[F]，[C]。它们的路径时延分别为8，4，6。因此，节点[H]的[top?list=F，C]。如果节点[H]有数据需要传输，它将从[top?list]中随机选择一个节点作为下一跳转发节点。通过[top?list]机制和随机选择方式平衡流量负载和队列溢出。

2  性能仿真

2.1  仿真环境

利用Cooja建立仿真平台，进而分析M?CoLBA协议性能。仿真中引用IEEE 802.15.4MAC协议和物理层。同时，节点利用无槽的CSMA/CA算法接入媒体。具体的仿真参数如表1所示。值得注意的是，数据包队列尺寸为8个数据包。之所以考虑8个数据包，主要是因为考虑到WSNs中传感节点是微型设备，不宜具有大的缓存区域。

表1  仿真参数

为了更好地分析M?CoLBA协议性能，选择单信道的CoLBA协议[13]和多信道路由协议作为参照，它们在仿真图中分别标记为S?CoLBA协议和M?HopCount协议[14]。M?HopCount协议依据路由跳数决策路由，并且M?HopCount协议与M?CoLBA协议的信道分配策略相同。

在200 m×200 m区域内随机部署传感节点，但保证不存在孤立节点。仿真中传感节点数分别为10，20，40，80，且信宿具有3个无线接口。同时，引用数据包传递率、数据包丢失率和端到端传输时延作为性能指标。每次实验独立重复10次，取平均值作为最终的实验数据。

2.2  实验一

本节实验考查三个协议的数据包传递率。数据包传递率是指信宿所接收的数据包与网络内所有节点产生的数据包间的比值。

在低數据流量场景下（每个节点每秒产生5个数据，简写为5 Packet Per Second Per Node），数据包传递率数据如图5所示。

图5  数据包传递率

从图5可知，在低数据流量下，提出的M?CoLBA协议的数据包传递率只略高于S?CoLBA和M?HopCount协议。原因在于：低数据流量使得网络内所传输的数据包数较少，因此媒体在多数时间内是空闲的，这就降低了碰撞风险和数据包丢失率。以图5a）为例进行说明，节点数的增加降低了数据包传递率，并且在节点数变化期间，M?CoLBA协议传递率较高于S?CoLBA协议和M?HopCount协议。同时观察图发现，M?CoLBA协议传递率较为稳定，并没有随节点数的增加而迅速下降。

随着数据流量的增加，M?CoLBA协议在数据包传递率方面上的优势逐渐呈现。注意到，当每秒产生5个、10个数据包时，M?CoLBA协议的吞吐量比M?HopCount协议分别提高2%，12%。原因在于M?HopCount协议选择静态路由指标，导致低的数据包传递率。

2.3  实验二

本次实验考查因队列溢出而导致的数据包丢失。图6显示了在每秒5个数据包、每秒10个数据包环境下的数据包丢失率。

图6  数据包丢失率

从图6a）可知，S?CoLBA和M?CoLBA协议的队列溢出几乎为零。对于S?CoLBA而言，网络内所有节点使用同一个信道通信。当队列快溢出时，就发送预警消息。由于M?CoLBA协议使用多个信道，广播预警消息是复杂的，这也导致节点不可能同时收到预警消息。这也能解释为什么在节点数为80时，每秒产生10个数据包时，S?CoLBA的数据包丢失率低于M?CoLBA协议。

而M?HopCount协议具有高的数据包丢失率，原因在于M?HopCount协议的路由指标是静态的，并且节点总是选择同一个下一跳节点。此外，M?HopCount协议并不允许传输预警消息。

2.4  实验三

最后，分析M?CoLBA协议的端到端传输时延。端到端传输时延是指产生数据包的时间与信宿接收此数据包的时间差。图7分别显示了10个节点、每秒产生1个数据包和80个节点、每秒产生10个数据包的端到端传输时延。将前者称为场景一、后者称为场景二。

图7  端到端传输时延

从图7可知，相比于S?CoLBA协议，M?CoLBA和M?HopCount协议具有更高的端到端传输时延。M?CoLBA和M?HopCount协议的高传输时延主要来自beacon阶段。beacon阶段维持了2 s，而在此阶段并没有传输数据包。而S?CoLBA协议并没有额外时延，因为S?CoLBA协议内所有节点使用同一个信道，无需广播控制消息。

3  结  语

针对WSNs的高数据率应用，提出M?CoLBA协议。M?CoLBA协议利用多信道和负载均衡技术提高网络性能。实验数据表明，提出的M?CoLBA协议避免了因队列溢出而产生的数据包丢失。在后期，将评估网络内每个节点的能耗，进而分析M?CoLBA协议的能量效率。

从实验数据可知，提出的M?CoLBA协议在数据包传递率方面优于同类协议，但是时延仍较高，需要进行控制。此外，本文重点分析研究负载均衡对网络性能的影响，即从负载角度提高网络性能。后期，将扩大研究内容，考虑循环路由问题，进而提高M?CoLBA协议的路由性能。

参考文献

[1] CHI Q， YAN H， ZHANG C， et al. A reconfigurable smart sensor interface for industrial WSN in IoT environment [J]. IEEE transactions on industrial informatics， 2014， 10（2）： 1417?1425.

[2] 范敏，谢思佳.基于空洞模型的地理位置路由改进算法研究[J].传感技术学报，2012，25（11）：1556?1561.

FAN Min， XIE Sijia. An improved geographic routing algorithm based on hole modeling [J]. Chinese journal of sensors and actuators， 2012， 25（11）： 1556?1561.

[3] STINE J A. Exploiting smart antennas in wireless mesh networks using contention access [J]. IEEE wireless communications， 2016， 13（2）： 38?49.

[4] SHIN J， LEE H， NA J， et al. Load balancing among internet gateways in Ad Hoc networks [C]// Proceedings of 2005 IEEE the 62nd Vehicular Technology Conference. Dallas： IEEE， 2015： 1677?1680.

[5] KYASANUR P， VAIDYA N H. Capacity of multi?channel wireless networks： impact of number of channels and interfaces [C]// Proceedings of 2015 IEEE the 11th Annual International Conference on Mobile Computing and Networking. [S.l.]： IEEE， 2015： 43?57.

[6] DIAB R， CHALHOUB G， MISSON M. Enhanced multi?channel MAC protocol for multi?hop wireless sensor networks [C]// 2014 IEEE IFIP Wireless Days. Rio de Janeiro： IEEE， 2014： 34?41.

[7] WANG X， TAN M. A load?balancing routing algorithm for multichannel wireless mesh networks [J]. International journal of sensors networks， 2015， 17（4）： 249?255.

[8] SONG M， ZHAO Y， WANG J. A high throughput load balance algorithm for multichannel wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Communications. Dresden： IEEE， 2015： 1?5.

[9] CHEN J， YU Q， CHAI B， et al. Dynamic channel assignment for wireless sensor networks： a regret matching based approach [J]. IEEE transactions on parallel and distributed systems， 2015， 26（1）： 95?106.

[11] BANIMELHEM O， KHASAWNEH S. GMCAR grid?based multipath with congestion avoidance routing protocol in wireless sensor networks [J]. Ad Hoc networks， 2012， 10（7）： 1346?1361.

[11] 刘卉，李泽军.基于投影矢量的双组播树高效路由数据收集[J].传感技术学报，2013，26（4）：570?577.

LIU Hui， LI Zejun. High?efficiency routing data collection of dual multicast tree based on the projection vector [J]. Chinese journal of sensors and actuators， 2013， 26（4）： 570?577.

[12] DIAB R， CHALHOUB G， MISSON M. Hybrid multi?channel MAC protocol for wireless sensor networks： interference rate evaluation [C]// 2013 IEEE the 78th Vehicle Technology Conference. Las Vegas： IEEE， 2013： 1?6.

[13] TALL H， CHALHOUB B， MISSON M. CoLBA： a collaborative load balancing algorithm to avoid queue overflow in WSNs [C]// 2015 IEEE International Conference on Data Science and Data Intensive Systems. Sydney： IEEE， 2015： 682?687.

[14] TALL H， CHALHOUB G， MISSON M. Implementation and performance evaluation of IEEE 802.15.4 unslotted CSMA/CA protocol on Contiki OS [J]. Annals of telecommunications， 2016， 71（9）： 517?526.