《单片机原理与接口技术》期中论文论文题目LEACH协议簇头选择算法的改进姓名学号学院电气工程学院专业班级2008级通信工程目录引言 (4)1 LEACH协议 (4)1.1 LEACH 协议介绍 (4)1.2 LEACH 协议的能量损耗模型 (6)1.3 LEACH 的不足在于： (6)1.4 LEACH 协议的优化 (6)1.4.1 基本思想 (6)1.4.2改进细节 (7)2 簇头选择算法的改进LEACH-H (8)2.1簇头初选 (8)2.2簇头调整过程 (9)3仿真结果 (11)4仿真分析 (11)5结束语 (13)参考文献 (15)EACH协议簇头选择算法的改进专业：通信工程姓名：马进虎摘要LEACH 协议存在簇头节点个数和位置分布不稳定的现象。
在改进的LEACH-H 协议在簇头节点的选举过程中, 充分考虑了簇头节点剩余能量因素, 设定了簇头的能量阀值, 防止了低能量的节点成为簇头。
在此基础上引进簇头调整过程, 该过程通过排除紧密邻居簇头和增加必要的簇头, 在一定程度上解决了LEACH 协议存在的问题,从而达到均衡网络能量消耗, 延长生存期的目的。
网络仿真证明了新算法的可行性，具有更高的能量使用率和更长的生存时间。
关键词WSN; LEACH; 簇头选择; LEACH—MAbstract In LEACH , the number and the locations ofcluster-heads are both unstable. In order to avoid low energy cluster-head , inthe process of cluster-head electing , LEACH-H takes remaining energy into consideration , designs energy threshold of cluster-head. Acluster-head adjusting phase is devised , which can eliminate close neighbor cluster-heads and necessarily add cluster-heads. This phase willsolve the above problems to a certain extent , attain the load equilibrium and further lengthen the network lifetime. The simulation results showthat the new algorithm is feasible，higher energy usage and longer survival time.Key words WSN; LEACH; selecting cluster-heads ; LEACH-M引言LEACH(Low-Energy Adaptive Clustering Hierarchy)协议是无线传感器网络层次型自适应成簇路由协议。
它将传感器网络节点划分成“簇”,并引入了“轮”的概念,各节点独立地按照概率随机决定自己是否做“簇头”,通过周期性的簇头选举和网络重组过程,避免了簇头节点能耗过大,平衡了网络负载,大大节约了通信过程中的能量消耗。
另外,簇头节点在处理数据的时候用到了数据融合技术和数据压缩技术,使得传输的数据量大大减小。
因而与一般的多跳协议或者静态成簇算法相比,LEACH 可以将网络的生命周期延长15 % 。
然而,LEACH 选簇首的方法常常呈现不稳定状态,即在一次实现中会出现簇首个数远远偏离期望值和分布位置集中在网络覆盖区域一侧的现象。
本文对簇头选择算法进行改进,提出了新的协议LEACH—H。
1 LEACH协议1.1 LEACH 协议介绍LEACH 协议的每一轮可分成簇建立和稳定数据传输2个阶段。
在簇建立阶段,各节点自主地运行簇头选举算法以确定自己是否成为簇头节点。
成为簇头的节点向周围节点广播信息,其他节点根据接收到的广播信息的强度来选择它所要加入的簇,并告知相应的簇头。
在稳定数据传输阶段,簇内节点把数据发送给簇头,簇头进行数据融合并把结果以一跳通信方式发送给sink 节点。
簇头需要完成数据融合、与汇聚节点通信等任务,能量消耗较大。
因此,每一轮结束要按照上述方法重新选择簇头,以平均分担中继通信业务来均衡能量消耗。
LEACH的簇头选举算法是分布式的算法,没有任何中心节点控制选举或对选举进行协调。
每个节点独立自主地决定是否成为簇头。
选举时,节点产生一个0～1 之间的随机数,若该随机数小于阀值T( n) ,则发布自己是簇头的公告消息。
T( n) 的公式为:式中, p 为簇头节点在传感器网络所有节点中所占百分比的期望值; r 为当前选举的轮数; G 是在最近1/ p 轮中没有当选过簇头的节点集合。
通过该算法,每个节点都会在1/ p 轮中当选一次簇头节点。
通过研究发现LEACH 选簇首的方法无论从数量上还是分布的位置上都常常呈现不稳定状态。
当簇首个数太少时,失去分层的意义;当簇首个数太多时,由于簇首要直接与远端的sink 节点通信,发射功率较大,会导致整个网络能耗过大;簇首位置过偏会导致部分节点簇内通信半径过大,能耗不均匀,这都会影响网络寿命,使得网络的负载平衡程度下降。
研究发现,上述现象的发生源于每次簇首选举的过程完全依赖于各节点产生随机数的过程,由于随机数产生的不稳定性导致了簇首状态的不稳定性。
1.2 LEACH 协议的能量损耗模型图1 LEACH 协议的能量损耗模型LEACH 协议的能量损耗模型主要有接收机和发射机两部分组成。
发射机：发生电路发送放大器组成。
接收机主要是接收电路。
1.3 LEACH 的不足在于：（1）各节点自行随机决定是否成为簇头，导致簇头在某一区域特别集中，某一区域又特别稀疏。
（2）LEACH 假定所有节点初始能量相同，但实际上这点未必成立。
即使成立，由于消耗不均，运行一段时间后剩余能量也会不一致。
（3）簇头的选择没有考虑节点的剩余能量，有可能导致某些节点的能量提早耗尽。
（4）EACH 选簇首的方法无论从数量上还是分布的位置上都常常呈现不稳定状态。
1.4 LEACH 协议的优化1.4.1 基本思想针对不足，对LEACH 进行改进。
首先，为系统内节点添加定位装置（如GPS），使每个节点都有唯一的节点标识符node_id，接着以监测区域中心为质点，选定一起始半径，以2/kopt为定长进行等角度分区（kopt为网络最优簇头数），将整个区域分成多个均匀的子区域，避免了簇头分布不均。
此外，给每个子区域制定唯一的区域标识符area_id，使每个节点清楚自己的归属。
改进算法依旧采用“轮”的概念，每轮分为初始化和稳定工作两个阶段。
簇头的选择由节点剩余能量决定，每轮过后计算每个节点的剩余能量，区内节点把自身带有的node_id、area_id 和标示本身能量的信息传输给它的邻节点，这样同区域内的每个节点都相互知道其它节点的相关信息，比较同区域内其它节点的剩余能量，能量最高的为本轮簇头，如一轮中出现相同剩余能量的节点，且能量都为最高，则按节点的标识符选定簇头。
1.4.2改进细节（1）初始化最大节点数P，Eini（节点初始能量），Eres（节点剩余能量），节点初始能量与节点初始剩余能量相等，E0（剩余能量的阈值，小于此阈值，节点将不能选为簇头），Eelec（发送和接收电路消耗的能量），￡fs（信号放大器的通信功耗），每个数据包的大小。
（2）子区域划分，计算节点能量的消耗和剩余能量，确定簇头。
操作如下：①在特定网络区域中随机部署所有节点，确定节点的标识符和坐标。
②划分kopt个子区域，指定每个子区域的标识符。
划分子区域的前提在于最优簇头数的确定。
当分布区域确定后，假设有N 个节点均匀分布在M×M 区域内，如簇头数为k 个，则每个簇内平均节点数为N/k。
当Sink 点距离节点分布区域较远时，能量按距离的四次方衰减。
③计算节点能量的消耗和剩余能量，确定簇头。
2 簇头选择算法的改进LEACH—H采用无文献[4 ]中的计算方法来计算在一定条件下最优簇头节点个数k ,其公式如下:式中, N 为传感器节点总数;λ控制包与数据包的长度比;ε f s与εamp为常数; dtoBS为节点到基站距离的期望值; M 为检测区域边长; m 为压缩比,即簇头节点最多可把m 个长度为L 的数据包压缩为一个长度L的数据包。
在簇头选举过程中,借鉴文献[5 ] ,LEACH2H 协议引入簇头竞争调整过程,通过该过程的执行,可以在很大程度上均衡簇头节点的分布, 并提高网络的可靠性。
2.1簇头初选只有剩余能量大于阀值的节点才有资格成为簇头,能量阀值的计算公式如下:式中, r 为当前运行轮次; n 为无线传感器网络的预期运行轮次; E0 为节点初始能量; Eth为第r 轮的簇头节点能量门限。
通过引入能量门限,防止了低能量的节点成为簇头,这就避免了因为簇头死亡造成的重选举开销和数据丢失。
2.2簇头调整过程节点根据簇头选举规则成为备选簇头后,就向其通信范围内的节点发送广播包,广播包中含有自己的ID 号和剩余能量数据项,每个备选簇头节点根据收到的广播报文构建自己的邻居簇头表, 该表包括邻居节点ID、邻居节点剩余能量Er 、被选作为簇头的次数Cch 、是否是紧密节点Nclose四个数据项。
首先,备选簇头节点将广播报文中的邻居节点ID 号、邻居节点剩余能量写入邻居簇头表, 初始化Cch = 0 ,根据接收信号强度估算与邻居节点的距离,若距离小于指定距离D , 则该节点和它是紧密节点。
式中, M 为传感器网络覆盖区域的边长(假设为正方形) ; K 为簇头节点数; < 为调整因子。
D 的取值是为保证均匀分布的K 个簇刚好覆盖整个观测区域。
非簇头节点收到广播报文,则将该簇头节点加入自己的备选簇头集合中。
然后,传感器节点进入以下的流程:①备选簇头节点计算自己的紧密邻居节点个数n 。
若n = 0 , 则转④; 若n > 0 , 则根据下式计算其紧密邻居节点的当选权重:式中, Enode为节点初始能量; x , y 为引入的权重因子,且x 、y ∈[0 ,1 ] 。
其余符号意义同上。
通过计算可得到每个节点的当选权重。
选出其中权重最大的节点将其ID 号填入取消簇头数据包中。
取消簇头数据包由类型Type 、本节点ID、最大权重节点ID、节点紧密邻居个数v 四个数据项组成。
然后,节点在(0 , T1) 时间区间,随机退避一段时间后,将数据包发送出去,这是取消自己作为簇头节点的声明。