节点位置信息已知的分簇算法

于南　周平

摘 要：无线传感器网络是一种无线自组织网络，并由大量的传感器节点构成。本文研究了典型的分簇协议，并在此基础上提节点位置信息已知的分簇算法出了一种新的分簇算法—— 最大最小距离分簇算法（max-min distance clustering algorithm）。该算法在节点位置信息已知的情况下，引入定位点为参量，可确保每轮选出理想的簇头个数。

关键词：无线传感器网络 分簇算法 LEACH协议 GAF协议 位置信息

中图分类号：TP39 文献标识码：A 文章编号：1672-3791（2014）08（a）-0192-02

无线传感器网络（Wireless Sensor Networks，WSNs）就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织的网络系统，其目的是协作地感知，采集和处理网络覆盖区域中感知对象的信息，并发送给观察者[1]。网络中节点通常只配备容量有限的电池提供能量，并且在使用过程中，对节点电池进行充电或更换电池几乎是不可能的[2]。所以网络生存期的长短是决定无线传感器网络功效的重要因素[3]。针对传感器网络的特殊环境，已经提出了许多适合于不同网络环境的路由协议，分簇路由协议具有能量利用高效、数据融合简单等优点，因此成为当前重点研究的路由算法[4]。

文章的结构安排如下：第一部分简要分析了相关工作。第二部分详细介绍了最大最小距离分簇算法。第三部分是仿真结果。第四部分是全文总结。

1 相关工作

分簇路由协议的设计大致包括以下3个阶段：（1）簇头的产生；（2）簇的形成；（3）簇的路由[5]。在现有的文献中，一部分文献提出的分簇算法的思想是先产生簇头，再形成簇，例如：LEACH协议，HEED协议，TEEN协议等。LEACH（Low Energy Adaptive Clustering Hierarchy）协议[6]是节点根据某个阈值自主决定是否当选簇头，簇头的选择具有随机性。HEED（A Hybrid， Energy-Efficient， Distributed Clustering Approach）协议[7]是通过节点之间的信息交互动态产生簇头，在簇头的选择过程中考虑了节点的剩余能量，并以主从关系引入了多个约束条件作用于簇头的选择过程。而TEEN协议[8]是针对事件监测类型的WSNs而设计的路由策略，它具有实时性，可以对突发事件做出快速反应。

在上述分簇算法中，簇头的产生是簇形成的基础。而另一部分文献则是先划分区域形成簇，再从每个区域中依照某种准则选择簇头。例如：GAF分簇协议。GAF（geographical adaptive fidelity）算法[9]是根据节点的位置信息将监测区域划分为虚拟正方形单元格，在每个单元格中定期选举出一个簇头节点。

2.2 算法描述

算法分为两个阶段：第一个阶段寻找划分区域的定位点，对网络进行分簇；第二个阶段是选举簇头。

第一个阶段寻找定位点分簇。网络中随机部署了N个节点，节点当选簇头的概率为P，最优簇头数为K，则有，每个簇内的节点总数理论上的最优值为N/K。设网络中存活的节点集合为G，首先进行第一次的区域划分，在G中随机选择一个节点A，由于网络节点位置信息已知，可计算出与A节点距离最远的节点B。因为B节点距离A点最远，所以不适宜把A，B两点划到同一个簇中，则A，B两点可分别为两个簇的定位点。A、B两点间的距离即“最大最小距离分簇算法”中的“最大距离”。之后A节点选择距离自己最近的（N/K-1）个节点，形成簇，Ga，此为“最小距离”之意。已经加入簇Ga的节点不能再加入其它的簇。同理以B节点为定位点，在节点集合（G-Ga）中找到距离自己最近的（N/K-1）个节点，形成簇Gb。节点A和B就是在第一次划分簇过程中所找到的一对定位点。第二次划分是在剩余的未加入簇Ga，Gb的节点集合（G-Ga-Gb）中找到距离最远的两个节点C和D，分别以节点C，D为定位点，形成簇Gc和簇Gd，成簇过程与Ga和Gb相同。如果K为偶数2n（n为自然数），则需要进行n划分，每次划分都会找到一对定位点，n次划分之后，网络中的所有节点都被划分到了相应的簇内。如果K为奇数2n+1（n为自然数），同样进行n次划分，每次划分找到一对定位点，但是与K为偶数不同的是，n次划分后，最后会剩下N/K个节点，则剩余的N/K个节点自然形成最后一个簇。

3 仿真结果

3.1 仿真参数设置

本文采用MATLAB对算法进行仿真。设节点总数N为100，节点的初始能量为0.2J，数据包大小为4000比特，基站的坐标位置为（50，175），理想簇头百分比P为0.05。

3.2 仿真结果

本文选取簇头数方差[3]作为分簇算法性能的度量标准。簇头数方差即簇头数占总节点的比值是反应了算法负载的一个重要指标，和设置的最优簇头比值越接近，算法效果就越好。

图1显示了LEACH算法，GAF算法和最大最小距离分簇算法在簇头数方差上的对比情况。实验中LEACH算法和最大最小距离分簇算法的最优簇头数都为5，GAF算法的最优簇头数为4。从图1中可以看出，LEACH算法的簇头数方差波动最大，GAF算法次之，最大最小距离分簇算法的簇头数方差波动最小，明显优于LEACH算法和GAF算法，说明该算法可以保证每轮都选出理想的簇头数目，抑制了所选簇头个数过多或过少，均衡了节点的能耗。

4 结语

针对无线传感器网络的可靠性和能量的有效性等问题，本文在对LEACH协议和GAF协议研究的基础上，提出了一种新的基于节点位置信息已知的分簇算法。算法引入了定位节点先划分簇，再从已划分得的簇中，选出最优位置的簇头。仿真证明，最大最小距离分簇算法与LEACH协议和GAF协议相比，可以确保每轮都选出最优的簇头数目，使得每轮节点的总能耗最小。

参考文献

[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

[2] 汤波，罗昌俊，周明天.无线传感器网络最小能量簇群构造策略[J].计算机应用，2007，27（1）：13-14.

[3] 何永刚，徐汀荣，彭俊.无线传感器网络分簇方法的优化[J].计算机工程与应用，2011，47（1）：92-94.

[4] 柳絮，李金宝，纪守领，郭龙江，惠丽.传感器网络簇头选举与调度策略研究[J].电子学报，2010，38（8）：1770-1774.