基于多信道協作負載均衡的WSN路由

徐曉旭 圖雅

摘 ?要： 在無線傳感網絡中，節(jié)點的資源限制給路由協議的設計提出了挑戰(zhàn)。在高數據率應用場景中，帶寬和存儲容量成為其主要問題。為此，提出基于多信道協作負載均衡算法（M?CoLBA）的路由協議來提升網絡帶寬，并避免因隊列溢出導致的數據包丟失。M?CoLBA協議先利用擁塞感知的動態(tài)路由度量均衡流量負載，再依據隊列時延選擇下一跳轉發(fā)節(jié)點。實驗數據表明，與單一信道路由協議（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）已廣泛應用于各個領域，如環(huán)境、工業(yè)。對于不同的應用，對WSNs的性能要求也不同。對于低數據率、小型智能家居的應用，依據ZigBee標準[1]就可滿足要求。然而，其他應用可能受端到端時延的限制，如工業(yè)應用、數據采集與監(jiān)視控制系統(tǒng)（Supervisory Control and Data Acquisition，SCADA）。而有些應用具有高數據率要求[2?4]，如視頻監(jiān)視、振動測量。

此外，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環(huán)境。

此外，在WSNs中的多對一（也在文獻中稱為融合）通信是非常普遍的。在具有融合的重流量場景中，需要先融合來自葉節(jié)點的數據，再將融合后的數據傳輸至信宿。依據不同的路由策略[9]，一些節(jié)點可能超載，而其他節(jié)點可能輕負載。而超負載節(jié)點可能經歷隊列溢出和數據丟失。

為此，針對多跳WSNs，本文提出基于多信道協作負載均衡的路由協議（Multichannel Collaborative Load Balancing?based routing，M?CoLBA）。M?CoLBA算法引用新的動態(tài)度量平衡流量負載，目的就是解決因隊列溢出而導致的擁塞和數據包丟失問題平衡網絡吞吐量。同時，利用WSNs中的多信道MAC協議提高吞吐量。

M?CoLBA通過利用擁塞感知動態(tài)路由，避免擁塞和隊列溢出問題，進而平衡所有潛在下一跳鄰居節(jié)點間的數據流量。在MAC層，M?CoLBA協議利用半動態(tài)信道分配的多信道協議;網絡層引用基于平均數據包隊列時延的擁塞感知動態(tài)路由。實驗數據表明，提出的M?CoLBA路由平衡了流量，提高了數據包傳遞率。

1 ?M?CoLBA協議

M?CoLBA協議先通過交互beacon包發(fā)現鄰居節(jié)點，一旦建立鄰居節(jié)點集后，就進入數據傳輸階段。換而言之，每個節(jié)點的活動周期可劃分為beacons階段和數據階段，如圖1所示。beacons階段交互beacons包，數據階段傳輸數據。

圖1 ?節(jié)點活動周期

此外，M?CoLBA協議引用具有三個無線接口的信宿，使得信宿從不同信道同時接收數據。

1.1 ?發(fā)現鄰居

通過發(fā)現鄰居節(jié)點，可避免已被鄰居節(jié)點使用的信道。因此，網絡內除信宿外的所有節(jié)點必須發(fā)現一跳 （1?hop）、二跳（2?hop）和三跳（3?hop）鄰居節(jié)點。利用beacon包發(fā)現這些鄰居節(jié)點。每個節(jié)點先利用它從鄰居節(jié)點接收的數據包建立1?hop鄰居集。然后，將1?hop鄰居集載入beacon包，再廣播。一旦接收了此包后，節(jié)點就能建立2?hop鄰居集。再將2?hop鄰居集載入beacon包中，并廣播此包。接收到此包的節(jié)點就能建立3?hop鄰居節(jié)點集。

然而，在網絡內難免會出現孤立節(jié)點。通常將一跳范圍內無鄰居節(jié)點的節(jié)點稱為孤立節(jié)點，即一跳鄰居集為空。對于此類節(jié)點，采用存儲?轉發(fā)機制。一旦孤立節(jié)點需要傳輸數據，它先存儲數據包，直至遇到節(jié)點才進行轉發(fā)。

1.2 ?信道分配

在最初的建立階段，給每個節(jié)點分配一個2 B整數的唯一ID號。ID號對節(jié)點選擇信道有重要影響。最初依據節(jié)點進入網絡的時間進行編號，最先進入的節(jié)點的ID號最小，最后進入的節(jié)點的ID號最大。在選擇信道時，在同等條件下，具有最小ID號的節(jié)點最先接入信道。下文將進一步分析。

節(jié)點依據ID號、有序方式選擇信道。首先，由3?hop鄰居節(jié)點中具有最小ID號的節(jié)點先選擇信道[10?11]。只要它的前任（predecessor）沒有宣布它所選擇的接收信道，節(jié)點就不能選擇信道。一個節(jié)點的predecessor是該節(jié)點的1?hop、2?hop和3?hop鄰居節(jié)點中ID號離自己最近，且比自己ID號小的節(jié)點。值得注意的是，本文從3跳范圍避免沖突，原因在于文獻[12]所分析的：3?hop鄰居節(jié)點重復使用信道會導致碰撞。通過擴大避免沖突范圍，降低信道碰撞率。

例如，如圖2所示節(jié)點8的1?hop，2?hop和3?hop鄰居節(jié)點為4，5，11，14，15，16和27。因此，節(jié)點5是節(jié)點8的predecessor。在節(jié)點5選擇信道之前，節(jié)點8不能選擇接收信道。

當在同一個網絡內使用多個信道時，每個節(jié)點必須知道它的鄰居所選擇的信道，否則容易導致信道碰撞和擁塞。這就要求鄰居節(jié)點間相互共享信道分配信息。M?CoLBA協議分配信道的目的就是盡可能地避免鄰居節(jié)點重復使用同一個信道。

圖2 ?節(jié)點的predecessor示意圖

首先，每個節(jié)點從1?hop，2?hop和3?hop鄰居節(jié)點內尋找未使用的信道。如果沒有未使用的信道，再從1?hop，2?hop鄰居節(jié)點集內選擇未使用的信道。如果在1?hop，2?hop鄰居集內所有信道已被使用，則節(jié)點就只從1?hop鄰居集內選擇可用信道。如果沒有可用信道，就從1?hop鄰居集內選擇重復使用率低的信道。

依之前所提到的，作為特殊節(jié)點，信宿具有3個無線接口。信宿首先選擇三個接收信道，然后在beacon包內廣播此信息。隨后，沒有predecessor的節(jié)點就選擇它們的接收信道，再在beacon包內廣播它們的選擇。此過程一直重復，直到網絡內所有節(jié)點選擇它們的接收信道。

1.3 ?路由指標

WSNs中的節(jié)點通信范圍是有限的，而作為數據包的目的節(jié)點，信宿可能不在網絡內多個節(jié)點的通信范圍內。這就要求通過多跳通信才能完成數據的轉發(fā)。通過連續(xù)地選擇下一跳節(jié)點，進而構成多跳通信。M?CoLBA協議將平均媒體接入時延作為路由指標，并依據此指標選擇路由。

由于信宿的1?hop鄰居節(jié)點能夠與信宿直接通信，它們不需要選擇下一跳轉發(fā)節(jié)點。當它們完成了信道分配后，信宿的1?hop鄰居節(jié)點就進入數據傳輸階段，并開始向信宿傳輸數據。致使它們必須從信宿的三個接口中選擇一個接口，然后再切換至該接口的接收信道。為了避免多個節(jié)點選擇同一個接收信道發(fā)生碰撞，M?CoLBA協議引用CSMA/CS策略接入信道。

非信宿的1?hop鄰居節(jié)點必須要選擇下一跳轉發(fā)節(jié)點，才能完成數據的轉發(fā)。M?CoLBA協議通過時延選擇下一跳轉發(fā)節(jié)點。具體而言，節(jié)點將所產生的或需要轉發(fā)的數據壓入數據包隊列中，然后再利用先進先出（FIFO）的原則傳輸數據包。利用節(jié)點局部時鐘記錄數據包壓入數據包隊列的時間和出列時間。這兩個時間差就是數據包隊列時延。

將最近10個數據包的隊列時延稱為該節(jié)點時延[d]。如果節(jié)點隊列中沒有10個數據包，則節(jié)點時延就等于已出列數據包的平均時延。如圖3所示，設最近5個數據包的隊列時延的權重為2，將其他5個數據包隊列時延權重設為1。換而言之，最近數據包的隊列時延對節(jié)點時延的影響更大，這也符合實際情況。因為最近隊列時延反映當時的網絡條件。因此，節(jié)點時延定義如下：

式中：[queueing delay（i）]為第[i]個數據包隊列時延;[λ]，[β]分別表示兩類時延的權重，在仿真中考慮它們對總時延比重相同，因此，各取為0.5。

一旦節(jié)點已出列了10個數據包，它就利用滑動窗口記錄最近的10個數據包。此外，值得注意的是，選用10個數據包的平均時延作為節(jié)點時延，原因在于連續(xù)10個數據包時延能夠反映情況，如果選用的數據包過少，就不能反映網絡環(huán)境的真實情況;若選用過多的數據包，必然增加了統(tǒng)計開銷。此外，通常節(jié)點緩存區(qū)域過小，也無法存儲過多的數據包。

圖3 ?節(jié)點的隊列時延

估計完節(jié)點時延后，再估計路徑時延[D]。估計路徑時延的原則如下：信宿的1?hop鄰居節(jié)點路徑時延等于節(jié)點時延。如圖4所示。信宿節(jié)點[A]的一跳鄰居節(jié)點[B]，[F]，[C]連通節(jié)點[A]的路徑時延等于它們的隊列時延。例如，節(jié)點[B]的隊列時延[d=8]、路徑時延[D=8]。

圖4 ?路徑時延

信宿的一跳鄰居節(jié)點利用beacon包自己的路徑時延。當二跳鄰居節(jié)點接收了此beacon包，就從一跳鄰居節(jié)點中選擇路徑時延最小的節(jié)點作為下一跳轉發(fā)節(jié)點。那么，該節(jié)點連通信宿的路徑就等于自己的隊列時延加上一跳鄰居節(jié)點的路徑時延。例如二跳鄰居節(jié)點[G]，它選擇[F]作為自己的下一跳節(jié)點，因為[F]離信宿的路徑時延最短。節(jié)點[G]連通信宿的路徑時延[D=7+4=11]。

2?hop鄰居節(jié)點也廣播自己的路徑時延，它的葉節(jié)點（3?hop節(jié)點）接收后，再計算自己連通信宿的路徑時延。直到網絡內所有節(jié)點已獲取了離信宿的最短時延路徑。

1.4 ?隊列溢出的避免策略

依據網絡拓撲，每個節(jié)點可能有多個連通信宿的下一跳節(jié)點。M?CoLBA協議選擇路由的原則是：選擇路徑時延最短的路徑傳輸數據。然而，總是以最小時延選擇下一跳節(jié)點在密集網絡中會發(fā)生振動[11]。為此，M?CoLBA協議中除了信宿和一跳鄰居節(jié)點外，其他節(jié)點需要建立top?list鄰居節(jié)點集。top?list內包含了最小路徑時延[Dmin]的鄰居節(jié)點。同時，M?CoLBA協議規(guī)定top?list也包含比最小路徑時延[Dmin]最多大于2 ms的路徑[13]。為了避免top?list的下流節(jié)點，允許2 ms路徑時延，進而保證無循環(huán)路由。

因此，為了避免振動，每個節(jié)點從top?list中隨機選擇一個鄰居節(jié)點作為下一跳轉發(fā)節(jié)點。以圖4為例，節(jié)點[H]有三個潛在的下一跳轉發(fā)節(jié)點[B]，[F]，[C]。它們的路徑時延分別為8，4，6。因此，節(jié)點[H]的[top?list=F，C]。如果節(jié)點[H]有數據需要傳輸，它將從[top?list]中隨機選擇一個節(jié)點作為下一跳轉發(fā)節(jié)點。通過[top?list]機制和隨機選擇方式平衡流量負載和隊列溢出。

2 ?性能仿真

2.1 ?仿真環(huán)境

利用Cooja建立仿真平臺，進而分析M?CoLBA協議性能。仿真中引用IEEE 802.15.4MAC協議和物理層。同時，節(jié)點利用無槽的CSMA/CA算法接入媒體。具體的仿真參數如表1所示。值得注意的是，數據包隊列尺寸為8個數據包。之所以考慮8個數據包，主要是因為考慮到WSNs中傳感節(jié)點是微型設備，不宜具有大的緩存區(qū)域。

表1 ?仿真參數

為了更好地分析M?CoLBA協議性能，選擇單信道的CoLBA協議[13]和多信道路由協議作為參照，它們在仿真圖中分別標記為S?CoLBA協議和M?HopCount協議[14]。M?HopCount協議依據路由跳數決策路由，并且M?HopCount協議與M?CoLBA協議的信道分配策略相同。

在200 m×200 m區(qū)域內隨機部署傳感節(jié)點，但保證不存在孤立節(jié)點。仿真中傳感節(jié)點數分別為10，20，40，80，且信宿具有3個無線接口。同時，引用數據包傳遞率、數據包丟失率和端到端傳輸時延作為性能指標。每次實驗獨立重復10次，取平均值作為最終的實驗數據。

2.2 ?實驗一

本節(jié)實驗考查三個協議的數據包傳遞率。數據包傳遞率是指信宿所接收的數據包與網絡內所有節(jié)點產生的數據包間的比值。

在低數據流量場景下（每個節(jié)點每秒產生5個數據，簡寫為5 Packet Per Second Per Node），數據包傳遞率數據如圖5所示。

圖5 ?數據包傳遞率

從圖5可知，在低數據流量下，提出的M?CoLBA協議的數據包傳遞率只略高于S?CoLBA和M?HopCount協議。原因在于：低數據流量使得網絡內所傳輸的數據包數較少，因此媒體在多數時間內是空閑的，這就降低了碰撞風險和數據包丟失率。以圖5a）為例進行說明，節(jié)點數的增加降低了數據包傳遞率，并且在節(jié)點數變化期間，M?CoLBA協議傳遞率較高于S?CoLBA協議和M?HopCount協議。同時觀察圖發(fā)現，M?CoLBA協議傳遞率較為穩(wěn)定，并沒有隨節(jié)點數的增加而迅速下降。

隨著數據流量的增加，M?CoLBA協議在數據包傳遞率方面上的優(yōu)勢逐漸呈現。注意到，當每秒產生5個、10個數據包時，M?CoLBA協議的吞吐量比M?HopCount協議分別提高2%，12%。原因在于M?HopCount協議選擇靜態(tài)路由指標，導致低的數據包傳遞率。

2.3 ?實驗二

本次實驗考查因隊列溢出而導致的數據包丟失。圖6顯示了在每秒5個數據包、每秒10個數據包環(huán)境下的數據包丟失率。

圖6 ?數據包丟失率

從圖6a）可知，S?CoLBA和M?CoLBA協議的隊列溢出幾乎為零。對于S?CoLBA而言，網絡內所有節(jié)點使用同一個信道通信。當隊列快溢出時，就發(fā)送預警消息。由于M?CoLBA協議使用多個信道，廣播預警消息是復雜的，這也導致節(jié)點不可能同時收到預警消息。這也能解釋為什么在節(jié)點數為80時，每秒產生10個數據包時，S?CoLBA的數據包丟失率低于M?CoLBA協議。

而M?HopCount協議具有高的數據包丟失率，原因在于M?HopCount協議的路由指標是靜態(tài)的，并且節(jié)點總是選擇同一個下一跳節(jié)點。此外，M?HopCount協議并不允許傳輸預警消息。

2.4 ?實驗三

最后，分析M?CoLBA協議的端到端傳輸時延。端到端傳輸時延是指產生數據包的時間與信宿接收此數據包的時間差。圖7分別顯示了10個節(jié)點、每秒產生1個數據包和80個節(jié)點、每秒產生10個數據包的端到端傳輸時延。將前者稱為場景一、后者稱為場景二。

圖7 ?端到端傳輸時延

從圖7可知，相比于S?CoLBA協議，M?CoLBA和M?HopCount協議具有更高的端到端傳輸時延。M?CoLBA和M?HopCount協議的高傳輸時延主要來自beacon階段。beacon階段維持了2 s，而在此階段并沒有傳輸數據包。而S?CoLBA協議并沒有額外時延，因為S?CoLBA協議內所有節(jié)點使用同一個信道，無需廣播控制消息。

3 ?結 ?語

針對WSNs的高數據率應用，提出M?CoLBA協議。M?CoLBA協議利用多信道和負載均衡技術提高網絡性能。實驗數據表明，提出的M?CoLBA協議避免了因隊列溢出而產生的數據包丟失。在后期，將評估網絡內每個節(jié)點的能耗，進而分析M?CoLBA協議的能量效率。

從實驗數據可知，提出的M?CoLBA協議在數據包傳遞率方面優(yōu)于同類協議，但是時延仍較高，需要進行控制。此外，本文重點分析研究負載均衡對網絡性能的影響，即從負載角度提高網絡性能。后期，將擴大研究內容，考慮循環(huán)路由問題，進而提高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.