标题: ZigBee网路之调控者辅助的分散式负载平衡机制
A Controller-Assisted Distributed Load Balancing Scheme for ZigBee Networks
作者: 杨宗羲
Tsung-Hsi Yang
曾建超
Chien-Chao Tseng
网路工程研究所
关键字: 无线感测网路;负载平衡;闸道器;wireless sensor network;load balancing;load balance;gateway;coordinator;zigbee
公开日期: 2007
摘要: 本论文针对多重协调器(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009556522
http://hdl.handle.net/11536/39617
显示于类别:Thesis


文件中的档案:

  1. 652201.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.