《单片机原理与接口技术》期中论文
论文题目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—M
Abstract In LEACH , the number and the locations of
cluster-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) 时间区间,随机退避一段时间后,将数据包发送出去,这是取消自己作为簇头节点的声明。
②收到声明的非簇头节点将数据包声明取消的节点从自己的备
选簇头集合中删除。收到声明的簇头节点则更新自己的邻居簇头表,即将该节点从邻居簇头表中删除,同时将声明中最大权重节点的Cch
值加1。查看自己的当前紧密邻居节点数z ,若z = 0 ,或者z > 0 但v = 1 ,则转④;否则,转①,继续执行竞争过程。所不同的是,随机退避的时间限制在( T′, T1 ) 的区间内, T′为当前时间。
③在时刻T1 到来时, 非簇头节点检查自己的备选簇头节点集合,若该集合为空,说明需补充簇头节点。此时非簇头节点在( T1 , T2) 区间内随机选择一个时刻广播自己当选簇头节点的通告, 若在退避
等待过程中收到其他节点的通告,则放弃发送,将该节点加入自己的
备选簇头集合中。
④在时刻T2 ,簇头节点的选择工作已经完成。各非簇头节点在其备选簇头节点集合中,按下列公式找出权重最大者作为自己的簇头节点:
式中, d ( node , CH) 为该节点到簇头节点的距离, 可以通过分析
信号强度得到; Dn - ch为一常数, 是允许的节点到簇头距离的最大值;θ、δ为权重因子,满足θ+δ= 1 ,且θ、δ∈[0 ,1 ] ,具体取值根据应用环境决定,通常δ的取值要大于θ。其余符号的意义同上;
⑤以后的过程与LEACH 协议一样。
3仿真结果
图2 仿真结果
4仿真分析
本文采用NS2仿真工具建立了网络仿真模型,对改进算法和LEACH 路由算法进行了仿真和性能比较[6 ] 。模拟将100 个节点随机分布在(100 3 100)的空中,sink 节点的位置为(0 ,0) 。所有的节点都是静止的。带宽设置为1 Mbps , 消息的长度为500 byte ,发送与接收的时延均为25 s ,每个节点的初始能量相同,为2J 。指标主要有3 个:簇头数量方差、簇分布的均匀程度以及网络的生存期。其中簇头数量方差用前500 轮的统计数据,簇分布的均匀度用最小簇的直径与最大
簇的直径之比来表示。
仿真结果显示,LEACH 协议的簇头数方差为1186 ,LEACH-H 的簇头数方差为1103 ,簇头个数的稳定性有了很大改善。LEACH-H 协议的簇分布均匀度值平均为0181 ,而LEACH 协议的仅为0175 ,这表明簇的分布更趋均匀。图1显示了2 种协议的网络生命周期。从中可以看出,第一个节点死亡时间LEACH-H协议要晚于LEACH,全部节点死亡时LEACH-H比LEACH 多运行了23轮。这说明,新协议均衡簇头节点数量、平衡簇头节点分布的过程,虽然造成了一定的能量消耗,但是由于可以使能量损耗更加均匀的分布到所有的节点中,避免了单个节点因能量损耗过大而过早死亡,从而延长了网络的生存期。本文的仿真场景仅包含100个节点,当WSN网络规模更大时,网络的性能提升会更好。: 网络仿真性能评价指标为网络生存时间和Sink 节点接收数据总量与能耗，网络生存时间指网络中所有节点经数轮数据传输后，剩余节点个数的比率。如网络生存时间图所示，随着轮数的增加，改进后的算法较之传统LEACH 剩余的节点数更多，持续的时间更长，节点的死亡时间延迟了近20％，原因在于传统LEACH运行一段时间后，网内节点的剩余能量会不均衡，而改进后的协议能使簇内节点的能耗均衡，避免了盲节点的过早出现，延长了网络生存时间。
网络生存时间图
传统LEACH的单位比特能耗要低，即消耗相同量的能量改进后的LEACH协议比传统LEACH 有能力发送更多的数据。这是由于每次都会选择簇内剩余能量高的节点作为簇头节点，从而增加了向Sink 节点发送数据的数量。
5结束语
本文针对LEACH 簇头选择算法的不足,在簇头的选举过程中充分考虑簇头能量因素并引进簇头调整过程。仿真试验结果表明,新的算法在簇头节点数量的稳定性和簇头节点位置分布均匀性方面都有很大改进,从而均衡了网络的能量消耗,延长了生存期。
同时，传统LEACH 协议采用先定簇头后分簇的算法，导致簇头分布不均、信息采集不完全的问题。文中提出了先根据最优簇头数进行网内区域划分，然后通过剩余能量感知选择簇头的算法，对传统LEACH 簇头选择算法进行了改进。理论分析和模拟实验结果表明，该算法能够合理的均匀分布簇头，平衡网络负载，使网络具有更大的数
据传输量和更长的生存时间。图3 Sink 节点接收数据总量与能耗本文作者创新点：文中提出了先根据最优簇头数进行网内区域划分，然后通过剩余能量感知选择簇头的算法，对传统LEACH 簇头选择算法进行了改进。
参考文献
[1 ] LINDSEY S ,RAGHAVENDRA C S. PEGASIS: Power Efficient Gathering in Sensor Information Systems[C] . Proceedings of the IEEE Aerospace Conference ,Big Sky ,Montana ,2002 : 542 -571.
[2 ] HEINZELMAN W R ,CHANDRAKASAN A ,BALAKRISHNANH.Energy2 Efficient Communication Protocol for Wireless Microsensor Networks [ C ] . Proceedings of the 33rd HawaiiInternational Conference on System Sciences ,2000 :1 - 10.[3 ] 孙利民,叶驰,廖勇. 传感器网络的路由机制[J ] .计算机科学,2004 ,31 :542 - 571.
[4 ] 王声荣.无线传感器网络LEACH 协议的研究与改进[D] .济南:
山东大学硕士学位论文,2008 :27 - 32.
[5 ] 张悦. 无线传感器网络LEACH 协议群首算法的改进[J ] .微计算机信息,2006 ,26 (4 - 1) :183 - 185.
[6 ] 何美红,徐成谦,张东良. 基于NS2 的LEACH 协议仿真与分析[J ] . 电子测量技术,2009 ,32 (1) :40 - 42.
[7]王殊, 阎毓杰等.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社, 2007. 77。
[8]张悦.无线传感器网络LEACH 协议群首算法的改进[J].微计算机
信息, 2006, 4-1:183-185。
Ns2.34上leach协议的完美移植 经过几天的不断实验，以及网上各位前辈的帮助，终于成功将leach协议完美移植到ns2.34上，下面是我的安装笔记。 Step1 在ns-2.34的目录下新建一个leach文件夹，将leach.tar.gz放入这个文件夹 Step2 在终端中进入这个目录下，键入tar zxf leach.tar.gz Step3 ①将leach/mit整个目录复制到ns-allinone-2.34/ns-2.34中 ②将leach/mac目录下的https://www.doczj.com/doc/b58157476.html,, mac-sensor.h, https://www.doczj.com/doc/b58157476.html,, mac-sensor-timers.h四个文件复制到ns-allinone-2.34/ns-2.34/mac中 ③将leach/tcl/mobility目录下的四个文件复制到ns-allinone-2.34/ns-2.34/tcl/mobility中 ④将ns-allinone-2.34/ns-2.34/tcl/ex目录下的wireless.tcl重命名为wireless_1.tcl,再将leach/tcl/ex目录下的wireless.tcl复制到ns-allinone-2.34/ns-2.34/tcl/ex中⑤将leach目录下的test,leach_test,package_up三个文件复制到ns-allinone-2.34/ ns-2.34中 Step3 修改文件 ①需要修改的文件有: ns-allinone-2.34/ns-2.34/apps/https://www.doczj.com/doc/b58157476.html,,app.h ns-allinone-2.34/ns-2.34/trace/https://www.doczj.com/doc/b58157476.html,,cmu-trace.h ns-allinone-2.34/ns-2.34/common/https://www.doczj.com/doc/b58157476.html,,https://www.doczj.com/doc/b58157476.html,,packet.h ns-allinone-2.34/ns-2.34/mac/https://www.doczj.com/doc/b58157476.html,,ll.h,https://www.doczj.com/doc/b58157476.html,,https://www.doczj.com/doc/b58157476.html,,phy.h,wireless-phy.c c,wireless-phy.h ②修改方法: 对于leach目录下相应的文件(即刚才未复制的文件),将代码中以“#ifdef MIT_uAMPS”开始,并以“#endif”结束的部分复制到以上文件对应的位置 这个过此要小心核对修改，否则前功尽弃 ③特殊情况 <1> ns-allinone-2.34/ns-2.34/common/packet.h中大约185行,根据其他变量的格式将代码更改为 #ifdef MIT_uAMPS static const packet_t PT_RCA = 61; #endif 并将最后一个枚举值改为62 这个过程可以随情况改变，还要注意的是packet.h文件并不是只改这一部分，前面的修改依然要。 <2> ns-allinone-2.34/ns-2.34/mac/wireless-phy.h,给类WirelessPhy添加public变量,大约105行 #ifdef MIT_uAMPS MobileNode * node_;
LEACH协议的算法结构及最新研究进展 1 LEACH协议算法结构 LEACH这个协议的解释是：低功耗自适应集簇分层型协议。通过名字，我们就能想到这个协议的大概作用了。那么在这之中，我们先来研究一下它的算法。 该算法基本思想是：以循环的方式随机选择蔟首节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。仿真表明，与一般的平面多跳路由协议和静态分层算法相比，LEACH协议可以将网络生命周期延长15%。LEACH在运行过程中不断的循环执行蔟的重构过程，每个蔟重构过程可以用回合的概念来描述。每个回合可以分成两个阶段：蔟的建立阶段和传输数据的稳定阶段。为了节省资源开销，稳定阶段的持续时间要大于建立阶段的持续时间。蔟的建立过程可分成4个阶段：蔟首节点的选择、蔟首节点的广播、蔟首节点的建立和调度机制的生成。 蔟首节点的选择依据网络中所需要的蔟首节点总数和迄今为止每个节点已成为蔟首节点的次数来决定。具体的选择办法是：每个传感器节点随机选择0-1之间的一个值。如果选定的值小于某一个阀值，那么这个节点成为蔟首节点。 选定蔟首节点后，通过广播告知整个网络。网络中的其他节点根据接收信息的信号强度决定从属的蔟，并通知相应的蔟首节点，完成蔟的建立。最后，蔟首节点采用TDMA方式为蔟中每个节点分配向其传递数据的时间点。 稳定阶段中，传感器节点将采集的数据传送到蔟首节点。蔟首节点对蔟中所有节点所采集的数据进行信息融合后再传送给汇聚节点，这是一种叫少通信业务量的合理工作模型。稳定阶段持续一段时间后，网络重新进入蔟的建立阶段，进行下一回合的蔟重构，不断循环，每个蔟采用不同的CDMA代码进行通信来减少其他蔟内节点的干扰。 LEACH协议主要分为两个阶段：即簇建立阶段(setup phase)和稳定运行阶段(ready phase)。簇建立阶段和稳定运行阶段所持续的时间总和为一轮(round)。为减少协议开销，稳定运行阶段的持续时间要长于簇建立阶段。 在簇建立阶段，传感器节点随机生成一个0，1之间的随机数，并且与阈值T(n)做比较，如果小于该阈值，则该节点就会当选为簇头。在稳定阶段，传感器节点将采集的数据传送到簇首节点。簇首节点对采集的数据进行数据融合后再将信息传送给汇聚中心，汇聚中心将数据传送给监控中心来进行数据的处理。稳定阶段持续一段时间后，网络重新进行簇的建立阶段，进行下一轮的簇重建，不断循环。 2 LEACH协议的特点 1 为了减少传送到汇聚节点的信息数量，蔟首节点负责融合来自蔟内不同源节点所产生的数据，并将融合后的数据发送到汇聚点。 2 LEACH采用基于TDMA/CDMA的MAC层机制来减少蔟内和蔟间的冲突。 3 由于数据采集是集中的和周期性的，因此该协议非常适合于要求连续监控的应用系统。 4 对于终端使用者来说，由于它并不需要立即得到所有的数据，因此协议不需要周期性的传输数据，这样可以达到限制传感器节点能量消耗的目的。 5 在给定的时间间隔后，协议重新选举蔟首节点，以保证无线传感器网络获取同意的能量分布。
WSN中LEACH协议源码分析 分析(一) 首先对wireless.tcl进行分析，先对默认的脚本选项进行初始化： set opt(chan)Channel/\VirelessChannel set opt(prop) Propagatioii/TwoRayGround set opt(netif)PhyAVirelessPhy set opt(mac) Mac/802_l 1 set opt(ifq) Qucuc/DropTail/PriQueue set opt(ll) LL set opt(ant) Antenna/OmniAntenna set opt(x) 0 。# X dimension of the topography set opt(y) 0。# Y dimension of the topography set opt(cp),H, set opt(sc) N../mobility/scene/scen-670x670-50-600-20-2u。# scenario file set opt(ifqlen)50o # max packet in if set opt(nn) 51。# number of nodes set opt(secd) 0.0 set opt(stop) 10.0 o # simulation time set opt(tr) out.tr。# trace file set opt(rp) dsdv 。 # routing protocol script set opt(lm) M on H。# log movement 在这个wireless.tcl中设置了一些全局变呈:： # #Initialize Global Variables # set ns_ [new Simulator] set chan [new $opt(chan)] set prop [new $opt(prop)] set topo [newTopography] set tracefd [open Sopt(tr) w] Stopo Ioad_flatgrid $opt(x) $opt(y) Sprop topography Stopo 这些初始化将在后而的使用中用到，该文件最重要的是创建leach 17点：创建方法如下： } elseif { [string compare Sopt(rp) M leach,,]==0} { for {set i 0} {$i < $opt(nn) } {incr i} { leach-create-mobile-node $i } 如果路由协议是leach协议，则在Uamps.tcl中调用leach-create-mobile-node方法创建leach节点。将在第二小节讲如何创建leach节点。 for {set i 0} {$i < $opt(nn) } {incr i} { $ns_ at $opt(stop).000000001 M Snode_($i) reset”。〃完成后，重宜右点的应用
无线传感器网络LEACH协议的研究 摘要：无线传感器网络因其在军事、经济、民生等方面广阔的应用前景成为21世纪的前沿热点研究领域[1]。在传感器节点能量有限的情况下，提高路由效率，延长网络寿命成为无线传感器网络需考虑的问题。由于采取分簇，数据融合的思想，LEACH协议有着较高的路由效率，但在实际应用，尤其是大规模网络中，仍存在负载不均衡等问题。本文主要分析了LEACH协议的基本思想及优缺点，随后针对大规模的网络环境对其分簇算法进行改进。前人提出一种有效的方法计算最优簇首个数，本文推算出适合本文中网络环境的公式并加以应用。本文用NS2进行仿真，仿真后的结果表明，改进后的分簇算法更为有效，延长了网络寿命，增大了网络传送数据量。 关键词：无线传感器网络；路由协议；LEACH；分簇思想 Research on Routing Protocol of LEACH in WSN Shen Y uanyi Dept. of Information and Telecommunication,NUPT ABSTRACT：Nowadays, wireless sensor network has become a hot spot of 21st century because of its wide application on military, economy and human life. On the condition that the energy of a sensor node is limited, how to improve the routing efficiency and expand the network’s lifespan has been an important issue to consider. LEACH maintains quite high routing efficiency for its idea of clustering and data gathering. But in practical, it still has problems such as load unbalance especially in large scale network. The article mainly analyses the basic idea of LEACH, the benefits and drawbacks of it and later introduce an improvement on clustering algorithm according to large scale network. Key words：WSN；routing protocol; LEACH; clustering 1LEACH协议介绍与分析 1.1 LEACH算法思想 算法基本思想[2]是：以循环的方式随机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。LEACH在运行过程中不断的循环执行簇的重构过程，每个簇重构过程可以用回合的概念来描述[3]。每个回合可以分成两个阶段：簇的建立阶段和传输数据的稳定阶段。 1.2 LEACH算法的分析 LEACH协议的优点[4]有: （1）LEACH 通过减少参与路由计算的节点数目，减少了路由表尺寸。（2）LEACH协议是一种分簇路由协议，降低了非簇首节点的任务复杂度，不必对通信路由进行维护。（3）协议不需要周期性的传输数据。（4）在给定的时间间隔后，协议重新选举簇首节点，以保证无线传感器网络获取同意的能量分布。 由于LEACH算法是建立在一些假设上，所以在实际应用中LEACH协议存在一些问题：（1）在LEACH协议中，簇头的选举是随机产生的，这样的随机性可能会导致簇头
《单片机原理与接口技术》期中论文 论文题目 LEACH协议簇头 选择算法的改进 姓名 学号 学院电气工程学院 专业班级 2008级通信工程
目录 引言................................. 错误!未定义书签。 1 LEACH协议 .......................... 错误!未定义书签。 LEACH 协议介绍.................... 错误!未定义书签。 LEACH 协议的能量损耗模型.......... 错误!未定义书签。 LEACH 的不足在于：................ 错误!未定义书签。 LEACH 协议的优化.................. 错误!未定义书签。 基本思想....................... 错误!未定义书签。 改进细节........................ 错误!未定义书签。 2 簇头选择算法的改进LEACH-H ........... 错误!未定义书签。 簇头初选........................... 错误!未定义书签。 簇头调整过程....................... 错误!未定义书签。 3仿真结果 ............................ 错误!未定义书签。 4仿真分析 ............................ 错误!未定义书签。 5结束语 .............................. 错误!未定义书签。参考文献 ............................. 错误!未定义书签。
Ubuntu 13.10下安装ns-2.35及leach协议安装 powered by Hong Sheng , Jiangsu university ,Zhenjiang 583301743@https://www.doczj.com/doc/b58157476.html, Tue Nov 25 , 2013 之所以选择基于linux的操作系统ubuntu来安装ns2，是因为我个人特别讨厌Microsoft 开发的基于windows的cygwin软件，此软件安装的时候不仅有各种错误，UI也不够友好。而，有关ubuntu的安装，大家可以自行baidu或google之。下面只讲解ns-2.35和leach协议的安装过程。 1. Ubuntu 13.10下ns- 2.35安装 step 1:下载ns2.35，https://www.doczj.com/doc/b58157476.html,/s/1h8rj0#dir/path=%2FNS解压，放在home/xx下，xx是你的用户名 step 2:更新源包，终端输入：sudo apt-get update step 3:安装依赖包 sudo apt-get install tcl8.5-dev tk8.5-dev sudo apt-get install build-essential autoconf automake sudo apt-get install perl xgraph libxt-dev libx11-dev libxmu-dev step 4:修改ns-allinone-2.35中ls.h文件的代码 将void eraseAll() { erase(baseMap::begin(), baseMap::end()); } 改为： void eraseAll() { this->erase(baseMap::begin(), baseMap::end()); } step 5:sudo ls /usr/bin/gcc* //查看系统已经安装的gcc版本。Ubuntu 13.10默认安装了gcc-4.8 //和gcc-4.8版本的,如果是其他版本的linux操作系统且没有安装 //高于4.0版本的gcc/g++。则需要手动安装gcc/g++-4.8 sudo apt-get install gcc-4.8 g++-4.8 // 对于Ubuntu 13.10，此项是非必须的 sudo export CC=gcc-4.8 sudo export CXX=g++-4.8 //CC和CXX是全局变量，用来指定make将会用哪个版本的gcc/g++编译器生成 //makefile文件。如果没有这一步，保证你会makefile失败！！！因为，在ns-2.35文件夹//下的makefile.in 中要求配置全局变量。 echo $CC echo $CXX //查看全局变量导入成功了没有，如果成功，则执行 sudo ./install //开始进行安装，大概等5分钟左右。 ....... 出现以下的内容，每个人的/home/xx/不同，我的用户名是nan，所以，显示了以下信息。 Ns-allinone package has been installed successfully. Here are the installation places: tcl8.5.10: /home/nan/ns-allinone-2.35/{bin,include,lib} tk8.5.10: /home/nan/ns-allinone-2.35/{bin,include,lib} otcl: /home/nan/ns-allinone-2.35/otcl-1.14 tclcl: /home/nan/ns-allinone-2.35/tclcl-1.20 ns: /home/nan/ns-allinone-2.35/ns-2.35/ns nam:/home/nan/ns-allinone-2.35/nam-1.15/nam xgraph: /home/nan/ns-allinone-2.35/xgraph-12.2 gt-itm: /home/nan/ns-allinone-2.35/itm, edriver, sgb2alt, sgb2ns, sgb2comns, sgb2hierns
Matlab Code for LEACH NodeNums = 100; % the num of node AreaR = 100 ; % the area of simulate NodeTranR=10; % the transit Radius Elec=50 * 10^(-9); % Eamp=100*10^(-12); Bx=50; % The Postion of Baseation By=175; MaxInteral =700; % the leach simulate time Pch=0.05; % the desired percentage of cluster heads InitEn=0.5; % the init energy of all node Tr=30; TDMA=100; Kbit=2000; % the bits of a node transmiting a packet every time BandWitch = 1*10.^(6); % Channel Bandwitch TOS_LOCAL_ADDRESS = 0; for i=1:(MaxInteral) AliveNode(i)=NodeNums; AmountData(i)=0; end sym alldata; alldata=0; LAECH = zeros(1,MaxInteral); LAENO = zeros(1,MaxInteral); for i=1:1:NodeNums EnNode(i)=InitEn; % the init energy of all node StateNode(i)=1; % the State of all node 1: alive 0:dead ClusterHeads(i)=0; % the Set of Cluster Head ,1: cluster head 0 :node Rounds=0; % the round end Threshold=0; % the threshold of node becoming a cluster-head Node.x=AreaR*rand(1,NodeNums); % the position of node Node.y=AreaR*rand(1,NodeNums); Node.c=zeros(1,NodeNums); Node.d=zeros(1,NodeNums); Node.l=zeros(1,NodeNums); Node.csize=zeros(1,NodeNums); Node.initclEn=zeros(1,NodeNums); % for i=1:NodeNums % Node.c(i)=0; % the Cluster head of node
1 SEP:A Stable Election Protocol for clustered heterogeneous wireless sensor networks G EORGIOS S MARAGDAKIS I BRAHIM M ATTA A ZER B ESTAVROS Computer Science Department Boston University gsmaragd,matta,best@https://www.doczj.com/doc/b58157476.html, Abstract—We study the impact of heterogeneity of nodes, in terms of their energy,in wireless sensor networks that are hierarchically clustered.In these networks some of the nodes become cluster heads,aggregate the data of their cluster members and transmit it to the sink.We assume that a percentage of the population of sensor nodes is equipped with additional energy resources—this is a source of heterogeneity which may result from the initial setting or as the operation of the network evolves. We also assume that the sensors are randomly(uniformly) distributed and are not mobile,the coordinates of the sink and the dimensions of the sensor?eld are known.We show that the behavior of such sensor networks becomes very unstable once the?rst node dies,especially in the presence of node heterogeneity.Classical clustering protocols assume that all the nodes are equipped with the same amount of energy and as a result,they can not take full advantage of the presence of node heterogeneity.We propose SEP,a heterogeneous-aware protocol to prolong the time interval before the death of the?rst node(we refer to as stability period),which is crucial for many applications where the feedback from the sensor network must be reliable. SEP is based on weighted election probabilities of each node to become cluster head according to the remaining energy in each node.We show by simulation that SEP always prolongs the stability period compared to(and that the average throughput is greater than)the one obtained using current clustering protocols. We conclude by studying the sensitivity of our SEP protocol to heterogeneity parameters capturing energy imbalance in the network.We found that SEP yields longer stability region for higher values of extra energy brought by more powerful nodes. I.I NTRODUCTION Motivation:Wireless Sensor Networks are networks of tiny, battery powered sensor nodes with limited on-board process-ing,storage and radio capabilities[1].Nodes sense and send their reports toward a processing center which is called“sink.”The design of protocols and applications for such networks has to be energy aware in order to prolong the lifetime of the network,because the replacement of the embedded batteries is a very dif?cult process once these nodes have been deployed.Classical approaches like Direct Transmission and Minimum Transmission Energy[2]do not guarantee well balanced distribution of the energy load among nodes of the sensor https://www.doczj.com/doc/b58157476.html,ing Direct Transmission(DT),sensor nodes transmit directly to the sink,as a result nodes that are far away from the sink would die?rst[3].On the other hand, using Minimum Transmission Energy(MTE),data is routed This work was supported in part by NSF grants ITR ANI-0205294,EIA-0202067,ANI-0095988,and ANI-9986397.over minimum-cost routes,where cost re?ects the transmission power expended.Under MTE,nodes that are near the sink act as relays with higher probability than nodes that are far from the sink.Thus nodes near the sink tend to die fast.Under both DT and MTE,a part of the?eld will not be monitored for a signi?cant part of the lifetime of the network,and as a result the sensing process of the?eld will be biased.A solution proposed in[4],called LEACH,guarantees that the energy load is well distributed by dynamically created clusters,using cluster heads dynamically elected according to a priori optimal probability.Cluster heads aggregate reports from their cluster members before forwarding them to the sink.By rotating the cluster-head role uniformly among all nodes,each node tends to expend the same energy over time. Most of the analytical results for LEACH-type schemes are obtained assuming that the nodes of the sensor network are equipped with the same amount of energy—this is the case of homogeneous sensor networks.In this paper we study the impact of heterogeneity in terms of node energy.We assume that a percentage of the node population is equipped with more energy than the rest of the nodes in the same network—this is the case of heterogeneous sensor networks.We are motivated by the fact that there are a lot of applications that would highly bene?t from understanding the impact of such heterogeneity.One of these applications could be the re-energization of sensor networks.As the lifetime of sensor networks is limited there is a need to re-energize the sensor network by adding more nodes.These nodes will be equipped with more energy than the nodes that are already in use,which creates heterogeneity in terms of node energy.Note that due to practical/cost constraints it is not always possible to satisfy the constraints for optimal distribution between different types of nodes as proposed in[5]. There are also applications where the spatial density of sen-sors is a constraint.Assuming that with the current technology the cost of a sensor is tens of times greater than the cost of embedded batteries,it will be valuable to examine whether the lifetime of the network could be increased by simply distribut-ing extra energy to some existing nodes without introducing new nodes.1 1We also study the case of uniformly distributing such extra energy over all nodes.In practice,however,it maybe dif?cult to achieve such uniform distribution because extra energy could be expressed only in terms of discrete battery units.Even if this is possible,we show in this paper that such fair distribution of extra energy is not always bene?cial.
目录 一、Leach协议与NS的关系 (2) 二、算法设计思想 (3) 三、簇头建立算法流程图 (4) 四、难点解决 (6) 五、算法运行结果分析 (9) 参考文献 (9)
一、Leach协议与NS的关系 为了实现leach 协议，对ns进行扩展。在ns中增加了一个事件驱动模拟器支持模拟无线传感器网络协议。这些扩展包括MAC协议，用于计算和交互的能量分配模型和leach协议的体系结构。 网络拓扑结构可以通过简单的Nodes, Links, Agents和Applications 描述。Nodes相当于网络中的终端主机， Links 是用于Nodes交互的连接器, Agent用来实现不同网络协议，是支持分组产生和丢弃的节点。Applications 用来产生数据和实现不同的应用函数。一旦网络拓扑结构建立起来后，模拟通过启动节点上的Applications运行。 为了在ns中支持无线传感器网络，在ns中增加了 mobile nodes, MAC 协议和信道传播模型Channel 。 Applications类的头文件用Tcl语言写的，节点中的其他函数功能用C++语言写成的。 数据包的发送过程： Applications创建数据包（data packets）,然后发送给Agent. Agent执行协议栈中运输层和网络层的功能，将数据包发送给CMUTrace,。 CMUTrace将packets的统计数据写到trace 文件，然后将packets发至Connector。Connector将数据包传送给用于数据链路处理的链路层(LL).经过一小段时间的延迟后，数据包由LL发送给Queue缓冲队列。如果是还没有传送过的数据包，Queue将以队列进行存储。然后Queue将数据包出队列，发送到MAC层。然后开始运行MAC（媒体访问控制）协议。最终，packets被发送到网络接口层(Network Interface),网络接口层将packets加上正确的传输能量，然后将packets发送到Channel. Channel将packets进行拷贝，并发往连接信道的每一个节点。 发送过程可参考如下图1 数据包的接收过程： 数据包被节点的网络接口接收，并被向上传送至MAC层，Link-Layer, Connector, CMUTrace, 和Agent 函数. Agent 对数据包进行判定，并将数据包到达的信息通知给Application. 接收过程与发送过程传输的路径相反。