 Hans Journal of Wireless Communications 无线通信, 2011, 1, 11-15 http://dx.doi.org/10.12677/hjwc.2011.11003 Published Online August 2011 (http://www.hanspub.org/journal/hjwc/) Copyright © 2011 Hanspub HJWC A Stable Cluster Algorithms in Wireless Sensor Network Based on LEACH Bo Zhang, Tongrang Fan Shijiazhuang Tiedao University School of Information Science and Technology, Shijiazhuang Email: zhangbozhangyong@126.com Received: Jul. 25th, 2011; revised: Aug. 3rd, 2011; accepted: Aug. 7th, 2011. Abstract: For the shortage of random clusters and excessive consumption of energy when the election of cluster head in LEACH, this paper improved LEACH algorithms, the method is to optimize the number of cluster head, get the unequal clustering and keeping stable of the clustering, reduce over the election of clus- ter energy consumption. Simulation experiments show that the improved algorithm in the control node mor- tality has been improved. Keywords: WSN; LEACH; Energy Consumption; Stable Cluster 基于 LEACH 无线传感网络稳定簇算法研究 张 博，范通让 石家庄铁道大学信息科学与技术学院，石家庄 Email: zhangbozhangyong@126.com 收稿日期：2011年7月25 日；修回日期：2011 年8月3日；录用日期：2011 年8月7日 摘 要：针对 LEACH 算法中随机成簇的不足和簇头选举能量消耗过大的不足进行改进，采用的方法 是优化簇头的个数、不均匀成簇、最后保持已形成的簇的稳定，减少全网簇的选举消耗的能量。仿真 实验表明，改进后的算法在节点死亡率的控制方面有了提高。 关键词：无线传感网络；LEACH；能量消耗；稳定簇 1. 引言 无线传感网络作为二十一世纪最为重要的技术之 一，利用无线式的信息获取和信息处理手段，综合基 于微电子的传感器技术，分布式信息处理技术[1]，实 现了在确定区域内的环境和检测对象的信息采集的过 程[2]。无线传感网络具有十分广泛的应用前景,在军事 国防、工农业、城市管理、生物医疗、环境监测、抢 险救灾、危险区域远程控制等许多领域都有重要的理 论价值和巨大的实用价值,它已经引起了世界许多国 家军事界、学术界和工业界的高度重视[3]。 因为无线传感网络是由大量的传感节点组成，传 感节点的计算性能、数据存储和转发都受到节点的能 量限制，而节点的能量十分有限，用完节点死亡，不 能重复利用。所以如何规划、减少节点能量的消耗是 无线传感网络设计的重中之重。从整体上考虑网络的 能耗、通过规划路由策略来减少节点的能耗也成了无 线传感网络重要的研究内容。 本文在 LEACH 协议的基础上，更多的考虑了全 网能量消耗的问题，最终提出了稳定簇的概念，不再 进行全网的簇头选举，在已经优化形成的簇内进行簇 头选举，目的在于减少无线传感网络路由连接时所消 耗的能量，使得节点可以将本身的能量更多的用于数 据的采集和传输过程中。 2. 其他路由协议 2.1. LEACH LEACH[4]协议的基本思想是通过阈值和随机数来 产生簇头。在簇头选举阶段，每一个节点随机生成 一个  张博 等 基于 无线传感网络稳定簇算法研究 12 | LEACH 0~1 之间的数，通过与阈值 T(n)的比较，小于 T(n)的节 点选举为簇头。簇头在全网发送广播信息 ，宣布自己成 为这一轮的簇头。普通节点选择与自己距离最近的 簇头 加入，这样完成了全网簇头的选举，在下一轮过程 中重 复上述的操作重新选举簇头。 T(n)的公式为： 1(mod1) 0 otherwise pnG pr p Tn (1) 其中，P是网络中簇头数目与总节点数的百分比， r是当前的选举轮数， mod1rp代表这一轮循环中当 选过簇头的节点个数，G是这一轮循环中未当选过簇 头的节点集合。成为簇头的节点在全网广播一个消息 宣布自己成为簇头，其它非簇头节点根据接收到的簇 头的信号强度，加入其中一个簇。初始化阶段结束后， 网络被划分为多个簇，每个本轮未成为簇头的节点加 入且只加入其中一个簇。簇头根据加入本簇的节点数 目，建立一个 TDMA 调度表，并发送给簇内成员，该 调度表分配给每个成员节点一个传输时隙(timeslot)， 在稳定传输阶段，簇内节点将采集到的数据发送给簇 头节点，簇头节点将接收到的数据进行汇聚，融合， 统一发送给sink节点。由于簇头节点与sink节点距离 较远，并且一次发送的数据量大，所以簇头节点的能 量消耗较快。 LEACH 每轮选举的簇头数目是不确定的，这样 加大了簇头与sink 节点通信的开销。并且普通节点根 据距离最近的原则加入簇，没有考虑到簇头与sink节 点通信时数据量与距离的比例。在 LEACH 协议中能 量消耗模型符合文献[5]中提出的能量消耗模型，如公 式(2)所示。 2 0 4 0 ,, , , TxTx elecTx amp elec Fs elec mp EkdEk Ekd kEkd dd kEkd dd (2) 其中， 表示发射电路损耗的能量， elec E F s k ， 分别是不同模型功率放大所消耗的能量，k表示发送 的比特数，d表示发送的距离。 mp k 根据能量公式(2)可知，距离 sink节点近的簇头一 次性传输数据量越大全网的能量节省的越多。 2.2. EECS EECS[6]协议与LEACH 协议在簇头选择和普通节 点的加入方面存在差异。在簇头选择上，EECS 并没 有直接将随机数小于T(n)的节点指定为簇头，而是将 这些节点指定为候选簇头。候选簇头在半径R的范围 内广播竞争信息。包含自身标识符和节点剩余能量。 同为候选簇头的节点在收到竞争信息后先比较剩余能 量，剩余能量小的放弃簇头的竞争，如果剩余能量相 同，则自身标识符小的成为簇头。 在普通节点加入簇的过程中，EECS 不单是考虑 了节点与簇头的距离，还加入了簇头与 sink 节点的距 离，让更多的节点加入到簇头与sink节点距离近的簇 内，这样减少了簇头与sink节点通信时的能量消耗， 节省了全网能量。公式如下： , min max min min , max min 1 chchbs ch ch bs COSTchwfdwgd dd fd dd dd gd dd (3) 公式表示普通节点选择簇头CH 的代价，其中 f、 g分别代表对 、进行数值正规化的函数，w为 0到1之间的权值。f中的 、 分别代表聚类成 员距簇头的期望最大距离、最小距离，由节点密度决 定；g中的 、分别代表簇头到基站的最大距 离、最小距离，由区域A大小及基站的位置决定。 ch d max d ,ch bs d min d max dmin d EECS 簇头的选举是随机的，但是第一轮随机数 选举出来的簇头不是最终簇头，还要在一定范围内广 播自己的标示和剩余能量，来与其他成为候选簇头的 节点进行对比，以能量大的候选簇头成为最终簇头。 这样的缺点分为两个方面：一是二次广播所消耗的能 量不能忽略，这样加快了全网能量的消耗；二是候选 簇头在一定范围内进行广播，容易引起隐藏点的问题， 如图 1所示，节点 C在B的竞选半径内；节点 B在A 的竞选半径内，且剩余能量方面 A > B > C。在这种情 ABC Figure 1. Hidden nodes problem 图1. 隐藏节点问题 Copyright © 2011 Hanspub HJWC  张博 等 基于 无线传感网络稳定簇算法研究 13 | LEACH 况下，C收到 B的竞选消息退出竞选的同时，B收到 A的竞选消息退出竞选，这就会造成局部簇头分布漏 洞的情况。 3. LEACH协议的改进 本算法在 LEACH 的基础上，加入了最优簇头的 概念，改进 EECS 的节点加入方式，并提出了新的成 簇方式，通过最长时间的维持形成的簇的稳定性，减 少了簇形成阶段的能量消耗，仿真实验表明，网络的 节点死亡率较LEACH 有了大的下降。 稳定簇算法与传统的 LEACH 算法不同，它强调 了簇的稳定，但这个稳定又是相对的，也就是说通过 一定的方法，第一次选择出来了最优的簇头和最优的 加入节点，这个第一次形成的簇是合理的，所以在以 后的信息采集时保持这个簇的稳定，既能减少全网能 量的消耗，又能使得采集的数据更加快速，不会因为 网络的结构调整而过多的错过数据的采集。在各个稳 定簇内，不能因为某一个节点过多的担当簇头而消耗 能量过快，就根据剩余能量因数，在各个稳定簇内进 行临时簇头的选择。通过临时簇头的选择，可以平衡 各个稳定簇内能量的消耗，使得整个网络的能量负载 均衡，减少因为网络结构变化所消耗的能量。这就是 稳定簇是相对的稳定的原因。稳定簇的形成，一定要 通过最优簇头的选举，最优节点的加入，稳定簇内临 时簇头选举，数据采集这四个步骤组成，缺一不可。 下面就详细介绍一下稳定簇的算法。 3.1. 簇头的选择算法的改进 采用文献[7]中的计算方法来计算在一定条件下最 优簇头节点个数 k，其公式如下： λ π4λ 21 MAX, 1 241 fs amp toBSelec NN kM m dE (4) 式中，N为传感器节点总数，λ控制包与数据包的长度 比， f s 与amp 为常数， 为节点到基站距离的期望 值，M为检测区域边长，m为压缩比,即簇头节点最多 可把 m个长度为 L的数据包压缩为一个长度 L的数据 包。 4 toBS d 在簇头选择过程中，按照 LEACH 协议，第一轮 每个节点生成一个随机数，与 T(n)相比，小于 T(n)的 广播自己成为簇头，同时广播的还有本簇头的标示。 当簇头的数量成为 k，选举结束，保证全网内选出的簇 头数目最优。 3.2. 普通节点加入簇头的方法改进 LEACH 选择簇的标准只有普通节点与簇头的距 离。普通节点与任何一个簇头距离最近，就加入相应 簇头形成的簇。根据公式(3)，假设簇头与 sink 节点的 距离都大于，则簇头与sink节点之间的距离越近， 传输数据时所消耗的能量越小。所以普通节点选择簇 头时要考虑簇头与sink节点之间的距离。 0 d 普通节点同时还要考虑自身与簇头之间的距离。 如图 2所示，簇头 A与sink 之间的距离大于簇头 B与 sink 之间的距离，普通节点 C与簇头A之间的距离小 于与簇头B之间的距离，根据 EECS 算法，普通节点 C加入簇头B，因为簇头 B离sink 节点距离较近。如 果普通节点 C与簇头 B之间的距离大于 ，根据公式 (2)可知，C与簇头 B传递数据时的能量成指数级增加， 这大大增加了簇内数据通信能量的消耗。 0 d 本算法提出新的普通节点加入簇头的公式。公式 如下： 0 0 min max min min , max min ch ch ch ch JJ ch JJ SS ch bs SS f dd COST chd g dd dd fd dd dd gd dd d (5) 其中， J d表示普通节点到临时簇头的距离。 表 示簇头到基站的距离。 S d max J d、min J d分别代表普通节 点到临时簇头的期望最大距离、最小距离。、 max S d 簇头A 簇头B Csin k Figure 2. Cluster head and sink node distance 图2. 簇头与 sink 节点距离 Copyright © 2011 Hanspub HJWC  张博 等 基于 无线传感网络稳定簇算法研究 14 | LEACH min S d分别代表簇头到基站的最大距离、最小距离。 代表距离阈值，由公式(2)得出，距离大于 时通信时 路径所耗费的能量成指数级增长。 0 d 0 d 普通节点根据公式(5)选择最合适的簇头加入。这 样保证了在一个簇内所有的节点不会出现因为距离太 远而过多消耗能量的问题。同时也为下一步保持簇的 稳定做准备。 3.3. 稳定簇算法 基于上述簇头选举过程和普通节点加入簇头的过 程，整个无线传感网络被划分成了 n个独立的簇。 LEACH 和EECS 强调在每一轮完成后进行全网的重 新划分，这样进一步加快了全网的能量消耗。在全网 进行广播选举簇头的能量消耗要远大于簇内节点进行 簇头选举时的能量消耗，据此，本文提出了稳定簇的 概念。此后的每一轮簇头选举将在各个已经成簇的范 围内进行，进一步减少能量的消耗。 假设节点可以根据距离调整数据发送的功率，簇 内的节点在本簇内进行每一轮簇头的选举，根据公式 (6)进行簇头的选择： 1mod1 0 otherwise init current init pENERGYnN pr p Tn ENERGY EEE (6) 其中，P是网络中簇头数目与总节点数的百分比， r是当前的选举轮数， mod1rp 代表这一轮循环中当 选过簇头的节点个数，N是本簇中所有节点的集合， 代表簇内节点的初始能量 代表簇内节点当 前剩余能量。在簇头选举过程引入ENERGY 这个变 量可以使得簇头选举的过程中考虑节点的当前的剩余 能量的大小，使得剩余能量大的节点当选簇头的概率 增大，从而保证了成为簇头的节点能够正常的完成数 据汇集的工作，并且节省了簇内的全局能量的消耗。 init Ecurrent E 在每一轮选举前都要进行稳定簇内平均能量的计 算。根据文献[8]可知，簇头平均能量的计算方式如下： total round ErE AVERAGE N (7) 其中，AVERAGE 为簇内平均能量， 为簇一 开始形成的初始能量， 为节点每轮选举的能量， r为轮数，N为簇内节点的数量。 total E round E 当 A VERAGE 为初始的 30%时，说明这个簇的能 量消耗过快，数据采集过多，为了防止这样的簇能量 耗尽而不能进行数据采集，必须进行全网的簇的重新 选举。使得全网的能量的负载均衡。 从以上的过程可以看出：通过选择最优簇头数目 的方式产生的簇头，每轮的个数是固定的,都是当前情 况下的理想个数，而不像 LEACH 中每次都是不确定 的。通过新的普通节点加入簇头的算法，可以使簇内 的数据传递的代价最小，并且使得簇头与sink 节点的 通信代价降低。通过簇内的每一轮的选举，可以减少 全网每一轮簇头选举时广播帧的能量消耗，增加选举 的速度，保证每一轮的簇头的能量高于簇内节点的平 均能量。 4. 仿真与结果分析 本文利用 MATLAB 软件对改进算法与LEA CH 算法进行了仿真比较，从节点存活时间方面考虑,评价 改进算法的性能[9]。在传感区域为 100 m × 100 m 的空 间内有 300 个传感器节点，LEACH 协议中假设节点 不知其地理位置，且节点随机分布。本文采用 LEACH 协议中原有的参数来仿真改进前后的 LEACH 协议。 具体参数如表 1所示。 节点存活个数如图 3所示。LEACH 算法在 400 轮左右出现第一个死亡的节点，在 1500轮左右节点全 部死亡，改进后的协议在800 轮左右出现第一个死亡 的节点，在 1900轮左右节点全部死亡。通过图3可知， 改进后的节点的存活率比LEACH 协议提高了 80% ， 节点全部死亡的时间比 LEACH 协议减少，说明改进 后的协议在全网的能量负载比 LEACH 协议有所提 高，避免了单个节点能量损耗过大而过早死亡，从而 延长了网络的生存周期。 Table 1. The simulation used parameter values 表1. 仿真所用参数值 参数设置 参数值 基站位置 （50,175） 传感区域 100 × 100 节点总数(N) 300 节点初始能量(J) 0.5 数据包长度(bit) 4000 控制包长度(bit) 1000 数据融合消耗能量(nJ) 50 自由空间信号放大倍数(pJ/bit·m–2) 10 多径衰减信道信号放大倍数(Pj/bit·m–4) 0.0013 Copyright © 2011 Hanspub HJWC  张博 等 | 基于 LEACH 无线传感网络稳定簇算法研究 Copyright © 2011 Hanspub HJWC 15 Figure 3. Live node number contrast 图3. 存活结点个数对比 5. 结语 本文提出了基于 LEACH协议的稳定簇路由协议 算法，利用最优的簇头数目和最佳的节点加入方式， 得到稳定的簇。在簇内进行按轮的簇头选举、数据融 合。这样减少了全网重新进行簇头选举所消耗的能量， 提高了节点的存活率，使得网络中节点的能耗更加均 衡，从而使得网络的生存周期最大化。 6. 致谢 感谢我的导师对我的指导，感谢我所引用的文章 的作者，不是他们先前的工作也没有我现在的文章， 感谢我身边帮助过我的每一个人，感谢审稿的每一位 老师，感谢！ 参考文献 (References) 1] S. Tilak, N. B. Abu-Ghazaleh, and W. Heinzelman. A taxonomy of wireless micro-sensor network models. ACM Mobile Com- puting and Communications Review (MC2R), 2002, 6(2): 28-36. [2] 孙利民, 李建中, 陈渝等. 无线传感器网络[M]. 北京: 清华 大学出版社, 2006. [3] 崔莉, 鞠海玲, 李天璞等. 无线传感器网络研究进展[J]. 计算 机研究与发展, 2005, 42(1): 163-174. [4] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan. An application specific protocol architechture for wireless mi- crosensor networks. IEEE Transactions on Wireless Communi- cation, 2002, 1(4): 660-670. [5] A. Depedri, A. Zanella, and R. Verdone. An energy efficient protocol for wireless sensor neiworks. Proceedings of the IEEE IPCCC, New York, 2005: 535-540. [6] M. Ye, C. Li, G. Chen, et al. EECS: An energy efficient cluster scheme in wireless sensor networks. Proceedings of the IEEE IPCCC, New York, 2005: 535-540. [7] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. An- application-specific protocol architecture for wireless micro sensor networks. IEEE Transactions on Wireless Communica- tions, 2002, 1(4): 660-670. [8] L. Qing, Q. X. Zhu, and M. W. Wang. A distributed energy -efficient clustering algorithm for heterogeneous wireless sensor neiworks. Journal of Software, 2006, 17(3): 481-489. [9] 王春. 无线传感器网络路由协议的设计与仿真[D]. 沈阳: 东 北大学, 2004. [ |