基于ZigBee技术的分簇算法研究

赖 毅，唐 毓

（1.四川省电力公司 简阳电业局，简阳 641400；2.四川省电力公司 成都电业局，成都 610031）

0 引言

无线传感器网络(Wireless Sensor Network，WSN)是传感器技术、无线通信技术 计算机技术、嵌入式计算技术结合的产物。利用分布在监测区域中的多个传感器节点，WSN能够感知、监测和采集相关环境或对象的信息。这些信息经过融合之后以多跳中继的方式传递到用户终端，供用户决策使用。WSN改变了人与自然界交互的方式，它在环境监测、军事国防、城市管理、抢险救灾等领域有很高的实用价值。无线传感网络的体系结构如图1所示[1]。

图1 无线传感网络体系

1 ZigBee网络体系结构

ZigBee网络是一种无线自组织的网络，网络中的节点之间通过单跳或者多跳的方式进行相互通信，在网络构成上，灵活多变，整个网络支持多种拓扑结构[2]，在组网方式上，常见的有三种不同类型的网络，包括星状网、树状网以及网状网。

2 ZigBee路由协议简介

现有的ZigBee协议主要采用的泛洪的模式[3]。协调器广播一个消息给网内他所能到达的节点，如图2所示，源节点S如果要向目的节点D发送消息，首先源节点S会想其相邻的节点A、B广播一个消息，当节点A、B收到消息再转发给他们的邻居节点C，由于C是A、B节点共用的邻居节点，根据协议，C节点将抛弃后面所接收到的相同的消息，直到消息传送到目的节点D，当D收到消息后，再按原路径返回给源节点S，当源节点S收到消息后再按ZigBee协议中规定的路由方式选择最好的路径到目的节点D[4]。

图2 ZigBee路由选择方式

综合上面的分析，发现ZigBee的泛洪方式虽然实现起来比较简单，不需要去维护路由而消耗很大的能量，但是总体来说也存在一些问题，比如“热点”问题，对数据的丢包率有很大的影响，为了让ZigBee网络发挥到更大的作用，我们就必须自己设计协议，对ZigBee的网络按一定的方法进行分簇设计，解决上面提到的问题。一个典型的网络分簇拓扑结构如图3所示。

图3 典型的分簇拓扑结构图

3 算法设计

3.1 网络模型

本协议规定所有节点都分布在一定规模的区域，然后我们通过一个圆将所有节点包围在里面。该协议的运行前提是在以下四个条件下进行。

1）网络中的所有节点被包含在一个圆形的区域内，并且位置都不变，每个节点通过坐标节点都能计算出自己的位置；

2）节点的发射和接收功率足够的大，可以直接单跳与网络中的所有节点直接通信；

3）每个节点都要具备数据融合的能力；

4）网络中每个节点的初始能量相同。

3.2 簇的具体划分

由于协调器节点的能量是无限的，本协议采用集中式方法对节点进行分簇以及簇头的选取，当网络初始化时，协调器节点集中式的对整个区域根据一定的规则进行簇的划分。大体的划分是规则是：以协调器为中心，建立一个二维坐标轴，并在坐标轴的两端各布置一个参考节点，每个参考节点已知自己在坐标轴上的相对位置，在开始时我们可以对节点位置进行固化，根据监控区域的大小进行设置，圆形区域半径为R，然后通过定位方法得到每个节点的坐标位置，在对节点定位有很多种方案，有直接定位和间接定位，直接定位中可以采用GPRS对节点进行定位，而间接定位主要分为基于距离关系定位、基于信标节点的定位，在本算法中我们采用了基于RSSI测距的三边定位法，在距离的测量中，我们选用了如公式的模型[5]。

则距离发射点的距离d的大小为：

公式（2）中A为发射器发射给1m处的节点的信号强度的大小，其取值范围在45-49之间，n为一个常数，代表信号传输与环境有一定的关系，其取值大小在3.25～4.5之间。通过公式（1）、（2）计算出节点到发射点节点之间的距离后，再根据三边定位算法求出网络中所有节点的坐标值。

在按根据项目的具体需要将网络分为K等分，这样做的目的是为了让整个网络的分簇更加均匀，避免了簇的重叠；使网络拓扑更加均衡， 假设将整个网络分成均匀的n等份，即n个簇，则每个簇的扇形角度θ的大小为：

我们定义在y轴上半区域与x轴正半轴夹角为θ的区域为簇1，然后依次划分为簇2，簇3，…，簇n，网络中得节点坐标假设为（x，y），则其与x轴的夹角θ'，则：

由式（4）可知：

具体簇的表示如图4所示，根据此方法可以将整个网络分成具有簇表示符的区域。

图4 簇标识符示意图

3.3 簇头节点选取方法

簇头节点是整个ZigBee网络分簇中的关键部位，簇头节点的选择算法是整个算法的核心，选择是否合理直接对整个网络有很大的影响，在本算法中，我们采用了节点加权值来确定簇头节点，主要关心以下两个方面。

1）节点的剩余能量；

2）各节点到协调器的距离。

在这里我们定义i表示某个节点，j表示网络划分的某个簇，r表示簇轮换的次数。

关于剩余能量Ei(r)我们可以根据下面的公式（7）求得：

其中，ei(r)为节点i的剩余能量，_表示节点i所在的第j簇中所有节点的平均能量，的大小为：

Nj(i)表示第j簇中有i个节点。

由于本算法在一段时间后会进行簇的轮转，能量不均对整个网络的影响不是很大，所以，我们在确定代价函数cost(i,j)(r)的公式时，只有代价函数的值越大，当选簇头节点的概率就越大，代价函数cost(i,j)(r)cost的公式如下：

在公式中，必须满足α+β=1，当如果网络中遇到同时有两个节点cost(i,j)(r)值的大小相同时，这时我们再以节点的ID大小来选择簇头节点。节点ID小的当选为簇头节点。

当网络中得簇头节点选择完毕以后，簇头节点将向簇内的每个节点广播一个数据包，在这个数据包中包括了自己已经是簇头节点的消息，其他节点将不在竞争簇头节点。并允许簇中得其他节点加入本簇，并且够建一个簇内节点的邻居表，为了让整个簇内的能耗更少，非簇头节点可以选择定时的休眠唤醒对数据进行采集和传送，这就需要簇头节点给簇内成员分配一个TDMA的序列，簇内的节点根据这个TDMA序列进行数据的传输，没轮到自己传输数据的时候，节点将进行休眠，更加降低簇内节的能耗，让整个簇的生命周期更长。同时为了保证数据传输的准确性，簇内每个节点收到簇头消息的时候，将返回一个ACK对消息进行确认已经收到。

3.4 簇的轮转

当网络中的簇头工作一定时间后其剩余能量较小，这是如果还继续担任簇头节点，不但容易导致簇头节点过快死亡，而且由于簇头节点的能量迅速耗尽，将会对整个网络的稳定性产生一定的影响，许多协议都采用了轮换簇头的方式来解决这一问题[7]，但是这些轮换簇头的方法都是在同一个簇内选取剩余节点能量较多的节点来当选簇头节点，并且每个节点只能当选一次簇头，但是由于网络中每个节点都在进行数据的传递，能量都有所消耗，这样一来必定导致每个簇的总体能量都会下降，直到最后每个节点能量都比较少时，不能选出簇头节点，该区域将会成为一个死区，导致网络的稳定性和生命周期，为了解决该问题，我们采取对簇头节点的轮换思想，但唯一不同的时，对整个区域进行重新划分，再对整个簇进行簇头节点的选取。我们采用了根据坐标按相应的规则进行轮转，这样节点位置没有发生变化，但是处于某个簇已经发生该变，具体示意如图5所示。

图5 簇的转示意图

整个分簇的重新轮转是由协调器发送一个命令进行轮转，这个轮转的时间是随机的，在这里我们设置为T1,轮转时间的值取决于整个网络的生命周期的长短，其值大小将在后面仿真进行取值，当分簇轮转开始时，协调器将发送命令对整个簇进行重新的架构，首先它发送命令给网络中的节点，让网络中的每个节点在现有的角度上加上a度，然后再根据公式（10）判断现在自己属于哪个簇。

注意在簇的轮转中，为了是簇尽量避免轮转后的簇同以前的簇重回，我们设定的轮转角度a不应该与θ的值大小相同，应根据整个网络中布置的节点的数量来设置a的大小。当分簇轮转完成以后，将重复上一节的簇头选择标准进行簇头节点的选取。

4 算法仿真

由于Matlab2007的Trutime工具箱中有完整的物理层以及MAC层的模块，非常方便对于协议栈中的网络层进行仿真，本算法基于MATLAB2007的平台进行仿真，为了评估本算法的优越性，特采用了现有的ZigBee路由算法AODV以及现有的经典分簇路由算法LEACH与本算法进行仿真比较，由于仿真的模型采用了三种不同的协议，为了实现同等条件下进行比较，我们假定所有的参数都是固定不变的，这其中包括物理层、MAC以及其他的层，在仿真过程中，节点的能耗模型采用了一阶能耗的模型[8]，仿真环境的参数如表1所示。

表1 仿真环境的参数

考虑通信模块的工作模式和收发能耗很关键。根据仿真参数设置，通过公式我们可以得到

其中εfs代表无线电路的能量消耗，εamp代表放大器的参数，通过带入表中的数值可以知道d0=87.8，也就是说当簇头节点与协调器节点的距离小于87.8m时，节点的通信模式采用自用空间模型模型，节点的能耗损失最小。

4.1 仿真结果分析

由于评价ZigBee路由协议的指标相当的多，在这里我们主要从簇的建立时间、每种算法工作一段时间后网络中存活的节点数以及算法在运行过程中整个网络消耗的能量为主要指标来对比分析本算、LEACH算法以及现有的ZigBee路由协议。通过仿真分析，节点想有机会竞选簇头，至少要满足开始设置的阈值，在本算法仿真中，我们设计节点每隔30ms发送一次数据大小为128bit的数据。在仿真时，我们先确定当α、β的大小，通过仿真分析，当α取0.6时，整个网络的生命周期最长，因此，决定簇头选择标准的权值公式中α=0.6，β=0.4，此后的仿真都采用此数值。

4.2 轮转时间T1的确定

在本算中，我们设计了整个簇不断的轮转来平衡整个网络的能量消耗，但是轮转时间T1的取值不能随意设置，如果这个时间设置过长，有可能网络中某个簇头节点的能量已经消耗的相当多了，而其他簇的能量消耗较少，影响其他簇的节点能量平衡，而当时间设置过短时，有可能整个网络的能量消耗速度加快，因为在本算中，整个网络中簇的重新划分消耗的能量是比较大的，所以在本算法设计中，应该尽可能选择合适的轮转时间周期，以使整个网络的性能更加良好，达到延长网络生命周期的目的。在这里我们选择轮转周期T1的值主要通过仿真来确定，通过设置不同的T1值来观察整个网络中第一个节点的死亡时间，仿真结果如图6所示。

图6 轮转周期值的确定

通过图中可知，在后面的仿真过程中，T1的取值为120s时，整个网络的生命周期最长。

4.3 节点存活数情况

由于ZigBee网络中节点的能量是有限的，因此我们在设计协议时应该以降低网络的能耗以及延长整个网络的生命周期为目标，而节点在工作状态中存活数量的多少直接对整个网络的生命周期有直接的影响，是评价一个路由协议的主要指标[11]如图所示，该图给出了三种算法中，根据网络中节点运行的时间长短，来对整网络中节点的存活数量进行对比，在仿真开始之处，我们设定了节点死亡的定义，如果节点的剩余能力为初始能量的10%时，即认为该节点已经死亡，不在进行数据的采集及传输，仿真结果的曲线如图7所示。

图7 节点存活数仿真结果

从图中我们可以看见，本算法中节点存活的数量相对其他两种算法，随着时间的推移，当网络运行20s的时候，AODV的路由协议最先出现节点的死亡，这是因为没有对网络分簇，有可能网络中某种节点承担着大量的数据转发，使节点的能耗变大，造成节点的死亡，而本算法第一个节点的死亡时间产生的时间在40s左右而，而LEACH协议的第一个节点的死亡时间在25s左右，这是由于LEACH只在固定区域内对簇投节点的选择进行轮转，而本算采用簇整体轮换的思想，避免了因为某个簇的能量过低而造成节点的大面积死亡，延长了节点的工作时间，在提高了整个网络的负载均衡性，每个节点的能量都得到充分的应用，并使整个网络的生命周期变长，

4.4 网络总能耗分析

在ZigBee网络中，我们最关心整个网络的总体能耗大小，只有减少了网络整体能耗，才能对延长网络的生命周期有决定性的影响，我们不但要尽可能的减少整个网络的总体能耗，还要使网络中每个节点的能耗均匀分别，仿真结果如图8所示。

图8 网络总能耗仿真结果

从图中我们可以发现，AODV协议的能耗是最高的，这是因为该算法没有对数据进行融合，大量的冗余数据被转发，导致整个网络的能耗增高。而LEACH算法以及本算法都对数据进行了相关的融合，以致整个网络的总体能耗比AODV要低，在网络组建之初，使用AODV协议以及LEACH算法的能耗要低于本算法的能耗，但是随着时间的推移，本算法中的能量消耗呈现缓慢递增的情况，而LEACH算法和AODV协议的能耗都直线上升，这是因为本算法在组网开始阶段，要对每个簇内的簇头选择消耗一定的能量，但是当选择完毕后，网络中的节点负载都比较均衡，能耗降到最低。

5 结束语

分簇算法的设计对网络的性能以及稳定性的提高有很大的意义，如果整个网络使用了分簇算法，不但有利于资源分配，降低数据传输时延，还能够采用混合式的路由，这对网络的扩展性有很大的好处，所有，分簇算法的设计有很广泛的应用，但是分簇协议的设计会带来更多的计算和维护通信的开销，增大网络的能量消耗，因此，为了尽可能的降低分簇算法所带来的一些影响，我们 必须提高分簇算法的性能。在未来，分簇算法的研究和设计应该重点注意以下两个方面。

1）应该根据不同的应用环境设置不同的分簇算法，在大规模的网络中，节点一跳到达协调器的几率比较小，这就需要对整个网络进行分层的设计，在每层选择一个簇头，簇头之间组成MESH网络进行通信。因此，在本算法中加入分层思想是下一步的主要研究方向；

2）应充分考虑节点的移动性，节点静止不动适用的范围一般用于定位或者数据的采集方面，但是在某些场合，节点需要移动，这时在设计分簇算法时，应根据节点的移动速度来设计分簇算法。

[1]孙利民, 李建中.无线传感器网络[M].北京: 清华大学出版社, 2005: 156-161.

[2]戚剑超, 魏臻.ZigBee树型路由算法的改进[J], 合肥工业大学学报(自然科学版) 第33卷第4期, 2010, 4.

[3]王胜平, 胥布工, ZigBee网络路由发现广播策略[J], 计算机工程, 36(11).

[4]周武斌, 罗大庸.ZigBee路由协议的研究[J], 计算机工程与科学, 2009, 31(6).

[5]朱明辉, 张会清.基于RSSI 的室内测距模型的研究[J],传感器与微系统, 2010, 29(8).

[6]Heinzelman W, Chandrakasan A, Balakrishnan H.Energy efficient communication Protocol for wireless microsensor networks[J], In: Proceedings of the 33rd Hawaii International Conference on System Sciences Maui: IEEE Computer Society, 2000.3005-3014.

[7]Shu-bo QIU, Yuan XU, Xiu-wei YANG.A Novel Cluster Head Selection Method Using Energy for ZigBee Cluster-Tree Network[J], IEEE International Conference on Automation and Logistics Chongqing, China, August 2011.

[8]李善仓, 张克旺.无线传感器网络原理与应用[M], 北京,机械工业出版社, 2008: 12-20.

[9]Heinzelman W, Chandrakasan A, Balakrishnan H.Energy efficient communication Protocol for wireless microsensor networks[J], In: Proceedings of the 33rd Hawaii International Conference on System Sciences Maui: IEEE Computer Society, 2000.3005.

[10]黎天人, 罗娟, 李仁发.基于通信范围约束的传感器网络多层分簇算法[J], 计算机工程与应用, 2009(4): 9.

[11]Handy M J; Haase M,Timmermann D.Low Energy Adaptive Clustering Hierarchy with Deterministic Clusterhead Selection[A].Germany: 2002.368-372.