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

1、节点位置信息已知的分簇算法摘要:无线传感器网络是一种无线自组织网络，并由大量的传感器节点构成。本文研究了典型的分簇协议，并在此基础上提节点位置信息已知的分簇算法出了一种新的分簇算法一一最大最小距离分簇算法(max-mindistaneeclusteringalgorithm该算法在节点位置信息已知的情况下，引入定位点为参量，可确保每轮选出理想的簇头个数。关键词:无线传感器网络分簇算法LEACH协议GAF协议位置信息无线传感器网络(WirelessSensorNetworks,WSNs)就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织的网络系统，其目的是协

2、作地感知，采集和处理网络覆盖区域中感知对象的信息，并发送给观察者1。网络中节点通常只配备容量有限的电池提供能量，并且在使用过程中，对节点电池进行充电或更换电池几乎是不可能的2。所以网络生存期的长短是决定无线传感器网络功效的重要因素3。针对传感器网络的特殊环境，已经提出了许多适合于不同网络环境的路由协议，分簇路由协议具有能量利用高效、数据融合简单等优点，因此成为当前重点研究的路由算法4。文章的结构安排如下：第一部分简要分析了相关工作。第二部分详细介绍了最大最小距离分簇算法。第三部分是仿真结果。第四部分是全文总结1相关工作分簇路由协议的设计大致包括以下3个阶段:(1)簇头的产生；(2)簇的形成；(

3、3)簇的路由5。在现有的文献中，一部分文献提出的分簇算法的思想是先产生簇头，再形成簇，例如丄EACH协议，HEED协议,TEEN协议等。LEACH(LowEnergyAdaptiveClusteringHierarchy)协议6是节点根据某个阈值自主决定是否当选簇头，簇头的选择具有随机性。HEED(AHybrid,Energy-Efficient,DistributedClusteringApproach)协议7是通过节点之间的信息交互动态产生簇头，在簇头的选择过程中考虑了节点的剩余能量，并以主从关系引入了多个约束条件作用于簇头的选择过程。而TEEN协议8是针对事件监测类型的WSNs而设计的路

4、由策略，它具有实时性，可以对突发事件做出快速反应。在上述分簇算法中，簇头的产生是簇形成的基础。而另一部分文献则是先划分区域形成簇，再从每个区域中依照某种准则选择簇头。例如:GAF分簇协议。GAF(geographicaladaptivefidelity)算法9是根据节点的位置信息将监测区域划分为虚拟正方形单元格，在每个单元格中定期选举出一个簇头节点。2最大最小距离分簇算法2.1能量消耗模型算法采用简单的能量消耗模型10,仅考虑节点的通信能耗。设两节点间的距离为，当时，能量消耗与成正比，当耳寸，能量消耗与成正比。则节点发送信息所消耗的能量如公式（1）所示：其中表示发送或接收每比特数据时的电路能量

5、消耗，和是根据所使用的发送放大器的模型不同而采用的不同参数。节点接收信息的能量消耗如公式（2）所示：通过式（1）、（2）节点可以根据信息长度和传输距离来计算通信能耗。假设节点已知网络中其他节点的位置信息，因此，根据公式可以计算出任意两点间的距离。2.2算法描述算法分为两个阶段：第一个阶段寻找划分区域的定位点，对网络进行分簇;第二个阶段是选举簇头。第一个阶段寻找定位点分簇。网络中随机部署了N个节点,节点当选簇头的概率为P最优簇头数为K,则有,每个簇内的节点总数理论上的最优值为N/K。设网络中存活的节点集合为G首先进行第一次的区域划分，在G中随机选择一个节点A,由于网络节点位置信息已知，可计算出与

6、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,成簇

7、过程与Ga和Gb相同。如果K为偶数2n（n为自然数），则需要进行n划分，每次划分都会找到一对定位点,n次划分之后，网络中的所有节点都被划分到了相应的簇内。如果K为奇数2n+1（n为自然数），同样进行n次划分，每次划分找到一对定位点，但是与K为偶数不同的是,n次划分后，最后会剩下N/K个节点，则剩余的N/K个节点自然形成最后一个簇。区域划分后，算法进入第二个阶段选簇头。以簇Ga为例,首先在簇Ga中找到距离最远的两个成员节点和。然后再找第三个成员节点，必须满足公式（4）:即节点是簇Ga内距离，最远的成员节点。以”为顶点的三角形一定存在着唯一的外接圆，该三角形不一定能够完全覆盖簇Ga,但是其外接圆一

8、定会覆盖簇Ga。设该外接圆圆心为OGa,则把OGa称为簇Ga的伪簇头。在簇Ga中，距离伪簇头OGa最近的节点，即为簇Ga的簇头节点CH(Ga)。至此，簇Ga的簇头寻找完毕。同理可找到簇Gb,Gc,Gd等簇的簇头节点。3仿真结果3.1仿真参数设置本文采用MATLAB对算法进行仿真。设节点总数N为100，节点的初始能量为0.2J,数据包大小为4000比特，基站的坐标位置为(50,175),理想簇头百分比P为0.05。3.2仿真结果本文选取簇头数方差3作为分簇算法性能的度量标准。簇头数方差即簇头数占总节点的比值是反应了算法负载的一个重要指标，和设置的最优簇头比值越接近，算法效果就越好。图1显示了LE

9、ACH算法,GAF算法和最大最小距离分簇算法在簇头数方差上的对比情况。实验中LEACH算法和最大最小距离分簇算法的最优簇头数都为5,GAF算法的最优簇头数为4。从图1中可以看出丄EACH算法的簇头数方差波动最大,GAF算法次之，最大最小距离分簇算法的簇头数方差波动最小，明显优于LEACH算法和GAF算法,说明该算法可以保证每轮都选出理想的簇头数目，抑制了所选簇头个数过多或过少，均衡了节点的能耗。4结语针对无线传感器网络的可靠性和能量的有效性等问题，本文在对LEACH协议和GAF协议研究的基础上，提出了一种新的基于节点位置信息已知的分簇算法。算法引入了定位节点先划分簇，再从已划分得的簇中，选出最优位置的簇头。仿真证明，最大最小距离分簇算法与LEACH协议和GAF协议相比，可以确保每轮都选出最优的簇头数目，使得每轮节点的总能耗最小。参考文献孙利民，李建中，陈渝，等.无线传感器网络M.北京:清华大学出版社,2005.汤波，罗昌俊,周明天.无线传感器网络最小