ZigBee網路之調控者輔助的分散式負載平衡機制

Abstract

本論文針對多重協調器（Multiple Coordinators）之ZigBee網路提出一套協調器負載平衡機制。ZigBee網路是由好幾個PAN組成，其中一個協調器負責一個PAN的資料接收，並且往後端的伺服器發送；當網路規模日益龐大之時，大量的負載常常集中於少數協調器。本機制由網路中的調控者（可能是後端伺服器等元件）輔助，與網路中的其他網路節點共同合作，決定出位於負載較重PAN中哪些節點需要切換到負載較輕的PAN，以達成負載平衡的目的。 本論文針對具有多個協調器（Coordinator）之ZigBee網路提出一套協調器負載平衡機制。ZigBee網路可以由好幾個個人區域網路(Personal Area Network;PAN)組成，其中一個協調器負責一個PAN的資料接收，並且往後端的伺服器發送。當網路規模日益龐大之時，如果網路節點(或流量)分配不均，會導致大量的負載集中於少數協調器。因此本論文提出一套平衡協調器負載的機制，藉由調控者(controller;一般是網路後端的伺服器）的輔助，網路中的網路節點會共同合作，決定出位於負載較重的PAN中，哪些節點需要切換到負載較輕的PAN，以達成負載平衡的目的。 目前各方所提的各種負載平衡機制，可以簡單分成兩大類，分別是集中式處理與分散式處理。如果採用集中式處理的方法，網路節點需要將負載資訊上傳至伺服器，這些負載更新訊息會造成網路很大的負擔；反之，如果採用分散處理的方法，網路節點則不需要上傳負載資訊到伺服器，但網路節點間卻需要交換較多的訊息才能完成負載平衡的動作。 在無線感測網路的架構下，對於協調器的負載情形，後端伺服器是較容易知道的，但是網路拓樸以及各自的負載情形卻是散佈於整個網路之中，這些資訊都是負載平衡動作所需要的，因此不論是集中式或分散式作法都需要許多的訊息來傳遞這些參數。本論文提出的這套機制就是希望能夠讓掌握資訊的角色各司其職與共同合作，以減少所需要的訊息。這套機制首先建立子樹負載資訊維持樹（Sub-tree based load information maintenance tree），使得每一節點能夠知道自己底下子樹的總負載量，同樣的伺服器也知道各個協調器的總負載量；之後再由掌握協調器負載情形的伺服器決定該轉換PAN的節點個數，至於該從何處，也就是到底哪些節點應該要轉換PAN，則由各個網路節點跟據自己的子樹總負載量與伺服器決定的量做個比較來作判斷，一次以一個子樹為單位來做切換PAN的動作。因此我們的機制是一套介於集中式與分散式處理的作法。 根據模擬結果顯示，我們提出的機制能夠達到跟集中式作法相同的良好平衡表現，在資料傳輸量（Throughput）和資料傳輸延遲（End to end delay）方面表現也良好，但是所需要的訊息量卻遠較集中式與分散式作法都還要來的少。

In this thesis, we propose a load-balancing mechanism for ZigBee networks with multiple coordinators. In general, a ZigBee network may consist of a number of Personal Area Networks (PANs) and each of which has a coordinator that is responsible for transmitting the data from the PAN to the fusion center or vice versus. As the size of a ZigBee network grows, some coordinators may be overloaded if too many sensor nodes join the same PANs. In order to overcome the multi-coordinator load unbalance problem of ZigBee networks, we propose a Controller-Assist distributed (CAD) load balancing scheme. In CAD, a controller, possibly a server on the network side, decides the amount of traffics of an overloaded PAN should be reduce, and other ZigBee nodes of the overloaded PAN determine autonomously which nodes should switch to which PAN. In general, we can classify the load-balancing mechanisms into two categories: centralized and distributed approaches. The centralized approach can achieve better load balance under the expense of more uplink traffic overhead for the ZigBee nodes to update load information in a centralized server. On the contrary, the distributed approach does not rely on a centralized server to collect load information from ZigBee nodes but requires each ZigBee node to exchange load information with its neighbors periodically, and may have ping-pong effects in balancing loads of multiple coordinators. Neither centralized nor distributed approach best fits the need of multiple coordinator load balance problem. According to the characteristics of ZigBee networks, the server can know the loads of coordinators easily, but not the loads of all other nodes or information delivery paths. On the other hand, each ZigBee node can know the loads of the nodes that have a direct connection with it, but not the global view of the loads of all PANs. Therefore, it is necessary to exchange many message with the load and topology information in both centralized and distributed approaches. In light of the above characteristics, the CAD scheme we proposed in this thesis makes each node in a ZigBee network play its role in accordance of its own knowledge of load information and cooperate with other nodes to archive multi-coordinator load-balancing. First, we established a sub-tree based load information maintenance tree so that each node knows the total loads of its sub-tree. Second, the server decides and informs an overloaded PAN how many loads it needs to reduced. Third, each node in the overloaded PAN determines, autonomously in a distributed manner, if it needs to switch to another PAN in accordance of the amount of traffic it needs to reduce and the load of its sub-tree. The simulation results show that the CAD scheme can achieve the same performance as the centralized approach does in balancing the loads of multiple coordinators, while incurring fewer control messages than both centralized and distributed approaches. Furthermore, it is also very effective in terms of throughputs and end-to-end delays.