 Computer Science and Application 计算机科学与应用, 2012, 2, 172-177 http://dx.doi.org/10.12677/csa.2012.24031 Published Online October 2012 (http://www.hanspub.org/journal/csa.html) An Optimal Mechanism for the Cluster-Heads Selection of LEACH Protocol in Wireless Sensor Networks* Xuhui Chen1,2, Zhiming Yang2, Peiqiang Yu2 1The Key Lab of the Internet of Things Application Technology, Xiamen University of Technology, Xiamen 2College of Computer and Communication, Lanzhou University of Technology, Lanzhou Email: Xhchen84@gmail.com Received: May 2nd, 2012; revised: Jun. 16th, 2012; accepted: Jun. 27th, 2012 Abstract: The energy issues of low energy adaptive clustering hierarchical protocol (LEACH) was analyzed for wire- less sensor networks (WSN), a way for the cluster-heads selection was proposed, and using the residual energy of sen- sors and network weighting coefficients to adjust the threshold. This scheme can make the high energy sensors be elected the cluster-heads, and the whole network energy can be distributed to each sensor node to balance the network load effectively. In this basis, an optimal cluster-heads selection mechanism can be further shown. According to simula- tion results, the algorithm performance is improved and further extends the network lifetime. Keywords: Wireless Sensor Networks; LEACH Protocol; Optimal Cluster-Heads; Network Lifetime 无线传感器网络 LEACH 协议簇首优化选择机制* 陈旭辉 1,2，杨志明 2，余培强 2 1厦门理工学院福建省高校物联网应用技术重点实验室，厦门 2兰州理工大学计算机与通信学院，兰州 Email: Xhchen84@gmail.com 收稿日期：2012 年5月2日；修回日期：2012年6月16 日；录用日期：2012年6月27日 摘 要：对无线传感器网络分簇路由 LEACH 算法能耗问题进行了分析，提出了簇首选择方法，并通过传感器 节点剩余能量和网络加权系数重新设定阈值，使剩余能量较大的传感器节点被选作簇首节点，将网络内的能量 平均分配到每个传感器节点上，有效地平衡网络负载，在此基础上，给出了优化簇首选择方法，仿真结果表明 算法的性能得到了较好的改善，延长了网络的生命周期。 关键词：无线传感器网络；LEACH 协议；优化簇首；网络生命周期 1. 引言 随着传感器技术、嵌入式技术、自动控制以及低 功耗无线技术的发展，生产具备感应、无线通信以及 信息处理能力的微型无线传感器已成为可能。这些廉 价的、低功耗的传感器节点共同组织成无线传感器网 络(WSN)。通过节点间的相互协作、将其监测和感应 的多种环境信息(如温度、湿度等)传送到基站进行处 理。无线传感器网络具有广泛的应用场景。可以应用 在国防军事、救灾、环境监测、医疗卫生等各个领域。 由于其巨大的应用价值，WSN 已 经引起了 各国军 事 部门、工业界和学术机构的极大关注，并纷纷展开该 领域的研究工作。目前由微型传感器节点组成的无线 传感器网络已经发展成一个重要的计算机平台[1,2]。 *基金项目：国家自然科学基金资助项目(61065007)；人社部留学人 员科技项目(0814GS005)；甘肃省高校科研业务费项目；厦门理工 学院科研资助项目。 在无线传感器网络体系结构中，网络层的路由技 术对 WSN 的性能好坏有着重要影响。最主要的原因 Copyright © 2012 Hanspub 172  无线传感器网络 LEACH协议簇首优化选择机制 就是在监测区域内工作的传感器节点都是由电池供 电，当传感器网络工作在边远地区或者危险区域的时 候，工作人员无法对传感器节点进行电池的更换，除 此之外，由于一个传感器网络有成千上万个节点，所 以更换传感器节点的电源将耗费巨大的资源。因此， 节约能量是无线传感器网络面临的一大挑战。 目前，国内外许多学者提出了各种各样的路由协 议，从总体上来看，可以分为两种：一是所有网络节 点的地位是平等的，不存在等级和层次差异，它们通 过相互之间的局部操作和信息反馈来生成路由，这样 的路由技术被称作平面路由协议；二是分簇路由协 议，在这种技术中，网络通常被划分为簇，每个簇由 一个簇首和多个簇内成员组成，低一级网络的簇首是 高一级网络中的簇内成员，由最高层的簇首与基站通 信。通过实验仿真可知，与一般的平面路由协议相比， 分簇路由协议可以将网络生命周期延长约 15%[3]。 文献[4]通过修改阈值来有效地控制节点中的能 量，使网络中的能量平均分配到每个传感器节点，进 而有效地延长网络生命周期；文献[5]使用了定时器来 控制网络内节点能否被选举为簇首节点。通过实验仿 真，这两种方法都能节约网络内传感器节点的能量消 耗，有效地延长网络的生命周期。但是，由于忽略了 整个网络簇首节点的数目，因此在一定程度上限制了 网络内能量的有效分配，本文提出了一种优化簇首节 点数目算法，通过仿真可知，最优簇首数目的选取能 够节约网络内传感器节点的能量消耗，进一步延长网 络的生命周期。 2. LEACH协议 2.1. 算法描述 LEACH 是MIT 的Chandrakasan 等人为无线传感 器网络设计的低功耗自适应分层路由算法。它的基本 思想是以循环方式、随机选择簇首节点，将整个网络 的能量负载平均分配到每个传感器节点中，从而达到 降低网络能量消耗、提高网络整体生存时间的目的[3]。 LEACH 在运行过程中不断地循环执行簇的重构 过程。每个簇重构过程可以用“回合(round)”的概念 来描述。而每个回合又可分为簇的建立阶段(包括簇首 节点的选择阶段、簇首节点的广播阶段、簇的建立阶 段和调度机制的生成)和传输数据的稳定阶段。 为了节省资源开销，稳定阶段的持续时间要大于 建立阶段的持续时间[2,3]。 簇首节点的选择依据网络中所需要的簇首节点 总数和迄今为止每个节点已称为簇首的次数来决定。 具体的选择方式是：每个传感器节点随机选择0~1 之 间的一个值，如果选择的值小于某一个阈值 T(n)，那 么这个节点成为簇首节点。T(n)值计算方法如下： if mod 0othe knG Nkr Nk Tn rwise d (1.1) 其中，N为网络中传感器节点的总数；k为一个回合 网络中的簇首节点数；r为已完成的回合数。 选定簇首节点后，通过广播告知整个网络。网络 中的其他节点根据接收信息的信号强度选定从属的 簇，并通知相应的簇首节点，完成簇的建立。最后， 簇首节点采用 TDMA 方法为簇中每个节点分配向其传 送数据的时间片。 在稳定阶段中，传感器节点将采集的数据传送到 簇首节点。簇首节点对簇中所有节点所采集的数据进 行数据融合后再传送给汇聚节点，这是一种减小通信 业务量的合理工作模式。稳定阶段持续一段时间后， 网络重新进入簇的建立阶段，进行下一回合的簇重 构，不断循环。每个簇采用不同的CDMA 代码进行 通信来减少其他簇内节点的干扰。 2.2. 能量计算模型 为了能够进一步分析节点在动态网络中能量消 耗，本文采用一阶无线电模 型 [2](first order radio model) 作为能量计算模型。LEACH 协议使用这个模式是基 于以下假设： 1) 网络里所有节点完全相同并且能量非常有限； 2) 无线电信号在各个方向上能量消耗相同； 3) 汇聚节点(基站)是固定的，并且离整个无线传 感器网络较远。 传感器节点发送ω*bit 数据所消耗的能量为： sendelec amp EE (1.2) 传感器节点接收ω*bit 数据所消耗的能量为： receive elec EE (1.3) 其中 amp 是信号放大器的放大倍数。 是发送电路 elec E Copyright © 2012 Hanspub 173  无线传感器网络 LEACH协议簇首优化选择机制 和接收电路消耗的能量。而 是由无线电通道决定的 常量。d是信号传输距离。其中， elec amp kE kd 2 ， 这意味着，信号传输距离越短，能量消耗越少。在发 送距离较近时，适用自由空间 信道模型，取 ； 而当发送距离较远时，适用多径衰落信道模型，取 4 ，也称之为双路径模型。 2.3. 能量计算模型 由1.1 节讨论可知，在无线传感器网络中使用 LEACH 路由协议时，每个传感器节点都有相同的概 率被选作簇首节点，并且能将网络中的能量平均分配 到每个传感器节点，有效地节约了网络中的能量，但 是仍存在下列情况。 第一、由于簇首节点的随机选择性，因此当某一 传感器节点能量较低并且被选做簇首节点时，那么当 节点工作一段时间后，该节点就会因能量的耗尽而死 亡，随之由该节点监测的区域就会与用户终端失去联 系。 第二、当传感器节点分布在监测区域的边缘且被 选为簇首节点时，那么该簇首节点不仅与簇内节点传 送数据需要消耗较大的能量，而且必须遍历较长的路 径与汇聚节点进行数据信息的交换。 3. LEACH协议簇首优化选取准则机制 3.1. LEACH协议最优簇首数目选取方法 最优簇首数目的选取主要是基于以下考虑[6]，一 是使每轮中的能量消耗达到最少；二是使网络中的能 量平均分配到每个传感器节点上，进而有效地延长整 个网络的生命周期。 为了简化算法，本文做如下假设： 1) 每个簇有相同数量的传感器节点，并且在 N × N的区域大小分布有M个传感器节点。假设无线传感 器网络包含有k个簇，则有 M k个传感器节点被分布 在该簇内，其中包括 1 M k 2 个非簇首节点和一个簇 首节点； 2) 假设所有的传感器节点分布在一个圆形区域， 那么有，其中 R为该圆的半径，可得： 2 πRN πRN； 3) 假设网络中的传感器节点呈均匀分布，那么节 点分布概率密度 2 1N 。 根据 LEACH 路由协议的成簇算法和一阶无线电 模型可知，每个簇首节点的能量消耗包括接收普通传 感器节点发送的监测信息，数据融合以及将融合后的 数据信息传送到汇聚节点。此外，由于簇首到汇聚节 点之间的传输距离较远[6,7]，因此本文采用多径效应来 计算簇首节点的能量消耗。因此在一帧内任一簇首节 点能量消耗可以通过式(1.4)计算。 4 CHelecDAelecamp toBS 1 MMl ElElEE d kk (1.4) 其中 为数据信息包的长度，dtoBS 是簇首到汇聚节点 的距离，EDA 是簇首为每一数据信号进行数据融合所 消耗的能量， l 为数据融合系数。 考虑到在每个簇内非簇首节点和簇首节点进行 数据信息交换的传输距离较近，因此本文采用自由空 间模型来计算非簇首节点进行数据信息传输所消耗 的能量，如式(1.5)所示： 2 non-CHelecamf toCH ElEld (1.5) 其中，dtoCH 为簇内非簇首节点到簇首节点的距离。 根据前面假设可以进一步得出： 2 non-CHelec amf 1 2π N ElEl k (1.6) 因此可以计算在每簇内共消耗的能量(包括簇首 节点能量消耗和非簇首节点能量消耗)为： cluster CHnon-CH 1 M EE E k (1.7) 因此，假设包含有 k个簇的无线传感器网络共消 耗的能量为： 2 non-CHelecamf 1 2π N ElEl k (1.8) 则一个簇内消耗的能量为： total clusterelecelecDA 22 amf 4 amfelecamp toBS 22 2π2π EkEMlEklE MlE Nkl MNl lEdk (1.9) 为了计算网络中最小能量消耗，根据最小优化准 则可以得出最优簇首数目，即式(1.11)： total cluster cluster dd 0 dd EE Ek kk (1.10) Copyright © 2012 Hanspub 174  无线传感器网络 LEACH协议簇首优化选择机制 2 amf opt 4 elecamp toBS 2π MN kEd (1.11) 3.2. LEACH协议簇首选择的方法 根据 1.3 节讨论可知，簇首节点的选择需要考虑 网络内传感器节点的能量消耗，以避免剩余能量较小 的传感器节点被选做簇首节点，这样就会导致这些节 点由于能量的消耗而提前死亡，使得由这些簇首节点 监测的区域与用户终端失去联系。为了进一步讨论如 何实现簇首节点的选择方法，下面定义如下变量： 1) E0：网络中任一传感器节点的初始能量； 2) E_node：当前某一传感器节点的剩余能量。 那么利用公式： 0 _nodeEE (1.12) 来衡量当前某一传感器节点的剩余能量百分比。 进一步考虑到簇首节点的能耗，使剩余能量较大 的传感器节点被选做簇首节点，这样才能将网络内的 能量平均分配到每个传感器节点，有效地平衡网络负 载，进而进一步延长网络的生命周期，为了避免由于 某一簇首节点的死亡导致被监控区域与用户终端失 去联系，现将阈值计算准则定义为式(1.13)。 0 new_leach0 , mod 0, k GG Nkr Nk Tn nG 2 nG (1.13) 其中 G0，G2为网络加权系数。 先讨论如下两种情况： 1) 当G0 = 1，G2 = 0 时，式(1.13)演化为式(1.14)： new_leach 1 , mod 0, knG Nkr Nk Tn nG (1.14) 该式在文献[8]中表明，利用传感器节点的剩余能量作 为衡量簇首节点选择的一个因素，能有效地平衡网络 负载，但是通过仿真发现，当网络运行一定的轮数后， 整个传感器网络就会阻塞，尽管网络中仍有一部分剩 余能量较高的传感器节点满足需求。导致这种情况是 由于通过式(1.14)计算的阈值较低，为了避免这种情 况，本文采用 G0，G2作为网络加权系数重新设定簇 首阈值计算准则。 2) 当G2 ≠ 0时，就 而言，式(1.13)将进一 步演化为式(1.15)： nG 02 new_leach 2 0 2 2 21 mod 1 mod 1 mod k Tn GG Nkr Nk Gk GGNkr Nk k GG Nkr Nk (1.15) 根据簇首阈值标准及上述分析可知， new_leach1 new_leach2 01Tn Tn 11G21G ，计算可得网络加权 系数必须满足： ，，。 12 1GG 4. 仿真结果分析 使用 Matlab 按照表 1设置的网络参数进行实验仿 真。此外根据 1.3节描述可知，网络中簇首数目的多 少将会影响网络的性能，并在2.1 节给出了最优簇首 数目的理论选取方法，现假设数据融合系数 η为 100%，那么可以计算配置表 1的无线传感器网络最优 簇首数目为30 个。 从图 1可以看到，簇首数目的多少会影响到全网 的性能，最优簇首数目可以进一步有效地延长网络的 生命周期。图 2则进一步验证了在不同簇首数目下网 络中的能量消耗，可以看到簇首数目大约在 30 个左 右时全网能量消耗较少。 为了进一步平衡全网中能量的消耗，有效地将全 网中的能量平均分配到每个传感器节点，本文在最优 簇首数目基础上验证了以节点剩余能量选择簇首的 方法，网络配置参数见表1。 Table 1. Network parameter of LEACH simulation 表1. LEACH仿真网络参数 网络参数 取值 网络区域大小 300 (m) × 300 (m) 传感器节点数 N 300 (个) 初始能量 E0 2 (J) 数据包长度 4000 (bit) 控制信息包长度 200 (bit) εamf 10 nJ/bit/m2 εamp 0.0013 pJ/bit/m4 全网能量 E_total 600 (J) Copyright © 2012 Hanspub 175  无线传感器网络 LEACH协议簇首优化选择机制 05001000 15002000 25003000 0 50 100 150 200 250 300 Rounds LEACH LE ACH Figure 1. Simulation of network lifecycle 图1. 网络生命周期仿真结果 246810 2 3 4 5 6 (J) Figure 2. The differ ent cluster number of energy consume in LEACH protocol 图2. 不同簇首数目下 LEACH 协议能量消耗 从图 3可知，和最优簇首数目LEACH 协议相比， 采取节点剩余能量作为选择簇首的方法能够有效地 延长网络的生命周期，但是网络大约经历在第 1500 轮左右时，整个无线传感器网络的性能所有下降，导 致这种现象的主要原因是簇首选择阈值较低，因此本 文采取网络加权系数进一步调节簇首选择阈值，由图 3可知，利用网络加权系数和节点剩余能量能够进一 步延长网络的生命周期，并且不会出现网络阻塞的情 况。 本文采用第一个节点死亡(FND)和有一半节点死 亡(HNA)所经历的轮数衡量一个网络的生命周期，表 2记录了 5次实验仿真的平均值。 对平均 FND 而言，New-LEACH1和New- LEACH2 相对于最优簇首LEACH 协议使网络生命周 期分别提高 21.7%和29.1%；对平均 HNA 而言，则分 别提高 12.3%和18.0%。因此，通过使用传感器节点 剩余能量和网络加权系数来修订阈值可以有效地延长 05001000 1500 2000 2500 3000 0 50 100 150 200 250 300 Rounds LEACH New-LEACH1 New-LEACH2 New_leach1 为式 1.14，New_leach2 使用式 1.15，G1 = 20，G2 = 0.05。 Figure 3. Simulation of network lifecycle of new LEACH 图3. 改进后 LEACH 协议网络生命周期仿真结果 Table 2. LEACH simulation 表2. LEACH协议仿真结果 阈值类型 T(n) T(n)new_leach1 T(n)new_leach2 FND (rounds)350 426 452 HNA (rounds)1364 1532 1610 网络生命周期，进一步平衡网络负载，将全网中的能 量平均分配到每个传感器节点上。从而也验证了簇首 数目的多少能够平衡整个网络的性能。 5. 结论 本文针对 LEACH 协议存在的缺陷，提出了一种 优化簇首节点算法，并且在此基础上，给出了利用传 感器节点剩余能量和网络加权系数来选择簇首节点 的方法。通过仿真实验可知，通过该方法能够在一定 程度上节约网络内的能量，进一步延长网络的生命周 期。 参考文献 (References) [1] F. Ian, S. Weilian, S. Yogesh and C. Erdal. A survey on routing protocols for wireless sensor networks. IEEE Communications Magazine, 2002, 40(8): 102-114. [2] W. Heinzelman, A. Chandrakasan and H. Balakrishnan. Energy- efficient communication protocols for wireless sensor networks. IEEE Proceedings of the Hawaii International Conference Sys- tem Science, 2000: 3005-3014. [3] 于海斌, 曾鹏, 梁炜. 智能无线传感器网络系统[M]. 北京: 科学出版社, 2006, 1: 119-139. [4] M. J. Handy, M. Haase and D. Timmermann. Low energy adap- tive clustering hierarchy with deterministic cluster-head selec- tion. 4th International Workshop on Mobile and Wireless Com- munication Network, 9-11 September 2002: 368-372. [5] X. Y. Cui. Research and improvement of LEACH protocols in Copyright © 2012 Hanspub 176  无线传感器网络 LEACH协议簇首优化选择机制 Copyright © 2012 Hanspub 177 wireless sensor networks. International Symposium on Micro- wave, Antenna, Propagation and EMC Technologies for Wire- less Communications, 16-17 August 2007: 251-254. [6] 莫宵雁. 无线传感器网络分簇式路由协议的研究和设计[D]. 浙江大学, 2006: 1-10. [7] W. Heinzelman, A. Chandrakasan and H. Balakrishnan. Energy- scalable algorithms and protocols for wireless microsensor net- works. Proceedings of International Conference on Acoustics, Speech, and Signal Processing, June 2000: 660-760. [8] M. J. Handy, M. Haase and D. Timmermann. Low energy adap- tive clustering hierarchy with deterministic cluster-head selec- tion. 4th International Workshop on Mobile and Wireless Com- munication Network, 9-11 September 2002: 368-372. |