LEACH协议的改进算法
夏北浩
（湖南大学信息科学与工程学院长沙410082）
摘要：首先介绍了LEACH协议的工作原理，性能分析以及不足。之后介绍了LEACH的改进算法。
关键词：无线传感器网络,LEACH协议,改进算法,能量消耗
Improved algorithm of LEACH
Xia Beihao
(The College of Information Science and Engineering, Hunan University 410082) Abstract: This paper firstly introduce the content of the working principle of LEACH , the analysis of performance and discourages,following the introduction of the improved algorithm LEACH .
Key: wireless sensor networks, LEACH protocol,Improved Algorithm,Energy consumption
1 引言
近年来，由于无线技术、计算机技术与传感器技术的迅猛发展和快速融合，无线传感器网络应运而生。无线传感器网络技术作为一种新型网络技术受到研究者的普遍重视和广泛研究。但传感器网络也有一些固定的缺点：能量利用率低、生存周期短、抗干扰能力差。通过良好的算法不仅可以减少传感器节点的能耗，还可以降低通信干扰，提高mac协议和路由协议的效率。因此，提出一个高效稳定合理的算法便成为迫切需要解决的问题。
2 LEACH协议的介绍
2.1 LEACH协议
LEACH是WSN中第一个基于分簇的路由算法，它将网络中的节点分为簇头节点和簇内节点。由于簇头节点需要协调簇内节点的工作，负责数据的融合和转发，能量消耗相对较大，所以LEACH采用周期性地随机选择簇头节点以均衡网络中节点能量消耗。从而达到延长网络生命周期目的。LEACH协议以“轮”作为运
作周期，每一轮分成两个阶段：建立阶段和稳定传输阶段，为了节省频繁选择簇头带来的能量开销，数据的稳定阶段的持续时间要长于建立阶段的时间。在每轮的建立阶段，所有节点用CSMA 的MAC 协议广播“短消息”通信，自组织成簇，每个簇选取一个节点作为簇头节点。簇形成之后，簇头节点负责为簇内节点建立一个TDMA 时隙表。簇建立完成后，簇内节点根据簇内TDMA 方案将每帧采集的数据发送给簇头节点，簇头节点对接收到的数据经过过滤冗余数据融合处理后传送给基站。
2.1.1 簇建立阶段
首先每个节点首先每个节点产生0．1之间的一个随机数，如果这个数小于阈值)(n T ，则向所有节点广播自身成为当前轮的簇头信息。阈值)(n T 计算方法如下：
???????∈-=其他
0)1mod (1)(G n p r p p n T 其中，P 为预设的簇头节点在所有传感节点中所占的概率，r 是当前轮数，G 是在前1／轮中尚未成为簇头节点的节点集合。
从阈值)(n T 的计算公式中可以看出，在每轮循环中，如果当前节点已担任过簇头，则把)(n T 设为0，表示该节点一定不会再次当选。对于尚未当选过的节点，则以概率担任簇头，式中使每个节点在一定轮数内只成为一次簇头节点。当r=0时，由式得)(n T =P ，即首轮每个节点成为簇头节点的概率为p ；随着轮数的增加，阐值T(n)也随之增大，剩余节点当选簇头的概率将会逐渐增大。当1/1-=p r 时，即第p /1轮时，)(n T =l ，表示前(1/1-p )轮尚未当选过簇头节点此轮必定当选。
2.1.2 稳定传输阶段
若网络中簇已经形成，并且簇头节点已经生成TDMA 时隙表，就进入数据的稳定传输阶段。
假设传感器节点有连续数据需要发送，成员节点根据簇内TDMA机制，在属于自己的时隙里，将每帧采集的数据发送给自己的簇头节点。若属于自己的时隙尚未到来，则成员节点可以关闭收发器以节省能耗。但在整个传输阶段的过程中，簇头节点的接收器必须一直处于工作状态，用于接收来自不同成员节点的数据。在一轮的数据传输完成后，簇头节点将对接收到的数据进行融合处理，压缩成一个新的复合信号发送到基站。持续一段时间后，开始新的一轮，整个网络进入下一轮运作周期。在网络处于正常工作状态时，一般有多个簇同时工作，簇与簇之间难免会相互受到影响。
2.1.3 LEACH协议性能的分析
LEACH动态随机选取簇头节点，由不同的节点以概率当选簇头节点，将消耗能量较多的融合、转发任务轮流地分配给网络中的节点，有效避免了某些节点能量过快耗尽，能够较好地均衡网络负载，提高整体网络的性能；采用分层结构，节点不需要储存大量的路由信息，也不需要很复杂的计算功能，路由信息的储存以及路径的选择简单明了，非常适用于结构简单的传感器网络；簇头节点对接收的数据也进行压缩融合处理，大大减少了网络原始数据传输通信量。因此，LEACH 在性能上要大大优于直接通信协议和静态簇首协议。研究表明：LEACH协议比平面直接通信协议网络寿命(首节点能量耗尽时间)延长了约8倍，比分簇路由算法中固定簇首协议网络寿命延长了约10倍。但是，LEACH算法周期性随机选取簇头节点也会带来一些问题可能会出现部分簇头节点相距基站较远，若此时簇头节点与基站通信仍然采用单跳路径模式，则会消耗较多能量，而且扩展性较差，不适合较大规模的网络；网络中簇头节点的位置经常会发生变化，可能某些处于网络边缘的节点不在任何簇首节点的通信范围之内，被网络所分离；当节点的通信距离有限时，还可能出现簇头节点不能与基站顺利通信等等。
2.1.4 LEACH协议的不足
在LEACH 算法中,每一轮循环都要重新构造簇,而构造簇的能量开销比较大。其次, 远离汇聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量, 造成网络分割。另外,LEACH算法没有考虑簇头节点当前的能量状况,如果能量很低的节点当选为簇头节点,那么将会加速该节点的死亡,影响整个网络的生命周期。
3 LEACH 协议的改进算法
3.1 改进算法的介绍
这种算法主要是保证簇群的稳定，每次簇首的选择都在同一个簇群中，即在首次簇群建立完成后保持簇群的稳定。免大量广播信息耗费的能量，减少成簇复杂性。
3.1.1 簇首的选择
在选择簇首时，要充分考虑到节点的当前能量和节点的剩余能量。通过改变阈值T （n ），让剩余能量多的节点额能充当簇首，保证各点平均分担通信任务。
?????∈-=其他情况0)]/mod([)(int G n E E k N r k N
k n T current
其中，Ecurrent 是节点的当前能量，Eint 是节点的初始能量。从公式看，当前能量大的节点有更大的概率成为簇首节点，随着节点充当簇首的次数增加，节点成为簇首的概率变小。
3.1.2 簇首的个数选择
文献[2]可知，簇首所占百分比为5%时，整个网络的能耗最优。每个簇内成
员最大数目为。），（]1,0[a a 119max ∈+=N 我们假设簇内节点是分布均匀的
（a=0.5），则N=30。当簇内成员达到最大个数时，拒绝其他节点的加入。
3.1.3 保持簇群的稳定
簇内区域的划分在第一轮完成，一旦划分完毕，在整个网络生命周期内将不再变动，形成优化的簇类结构。由于簇类已经固定。在每一轮的初始化阶段（除
第一阶段）完成的工作只是簇首的选择，减少了每轮广播带来的能耗。
参考文献
[1]Tillett J. Rao R, Sahin F. . Cluster-head identification in ad hoc sensor networks using particle swarm optimization. In:Proceedings of the IEEE International Conference on PersonalWireless Communications, Singapore, 2002, 201～205
[2] 陈静,张晓敏.无线传感器网络簇头优化分簇算法及其性能仿真.计算机应用, 2006,26(12): 2787-2792
[3]C.E. Price ， K.M. Sivalingam ， J.-C ， Chen ， P. Agrawal. Power-aware scheduling algorithms for wireless networks. Proc. Intl. Conference on Intelligence Computing and VLSI ， Kalyani ，
India， 2001
[4]廖明华,张华,王东.基于LEACH协议的簇头选举改进算法.计算机工程,2011,7（37）:112-114
专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日
48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n 仿真一：在100*100的区域内随机生成100个节点 （matlab仿真代码： clear; xm=100;%x轴范围 ym=100;%y轴范围 sink.x=0.5*xm;%基站x轴 50 sink.y=0.5*ym;%基站y轴 50 n=100; E0=0.02; for i=1:1:n S(i).xd=rand(1,1)*xm; S(i).yd=rand(1,1)*ym; S(i).G=0;%每一周期结束此变量为0 S(i).E=E0;%设置初始能量为E0 S(i).type='N';%节点类型为普通 plot(S(i).xd,S(i).yd,'o'); hold on; end %设置SINK节点的坐标 S(n+1).xd=sink.x; S(n+1).yd=sink.y; plot(S(n+1).xd,S(n+1).yd,'*');%绘制基站节点仿真结果图片：（‘O’代表随机散布的节点，‘*’代表SINK节点） 仿真二：LEACH 分簇效果图（matlab 代码见附件） 仿真结果：(p=0.1) 1、簇头个数14. 0102030405060708090100 2、簇头个数：11 3、簇头个数：12 0102030405060708090100 4、簇头个数：10 10 20 30 40 50 60 70 80 90 100 (p=0.05) 1、簇头=6 10 20 30 40 50 60 70 80 90 100 2、簇头=7 3、簇头=12 4、簇头=8 10 20 30 40 50 60 70 80 90 100 5 、 010203040 5060708090 100 102030405060708090100x y LEACH 分簇算法成簇效果图 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i LEACH算法的学习摘要 一、LEACH的定义 LEACH:低功耗自适应路由算法 二、LEACH算法的工作流程 1.总述 LEACH路由协议主要分为两个阶段：即簇建立阶段(setup phase)和稳定运行阶段(ready phase)。簇建立阶段和稳定运行阶段所持续的时间总和为一轮(round)。为减少协议开销，稳定运行阶段的持续时间要长于簇建立阶段。 2.簇建立阶段 在簇建立阶段，传感器节点随机生成一个0，1之间的随机数，并且与阈值T(n)做比较，如果小于该阈值，则该节点就会当选为簇头。T(n)按照下列公式计算： 式中：P为节点成为簇头节点的百分数，r为当前轮数，G为在最近的1/p 轮中未当选簇头的节点集合。簇头节点选定后，广播自己成为簇头的消息，节点根据接收到的消息的强度决定加入哪个簇，并告知相应的簇头，完成簇的建立过程。然后，簇头节点采用TDMA的方式，为簇内成员分配传送数据的时隙。 3.稳定阶段 在稳定阶段，传感器节点将采集的数据传送到簇头节点。簇头节点对采集的数据进行数据融合后再将信息传送给汇聚节点，汇聚节点将数据传送给监控中心来进行数据的处理。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一轮的簇重建，不断循环。 三、LEACH算法的优点 1.LEACH算法属于分层路由协议，节点之间反应速度快，簇头进行轮转性选举，能够保证无线传感器网络中各个节点能量均衡的消耗，从而有效地延长无线传感网络的生命周期，低功耗的目的。 2.各个节点之间不再是无序的建立通信路由，数据信息的传递具有一定的规则，普通节点只能向上一级簇头传送数据信息，一级粗托只能向二级簇头传送数据信息。很大程度上节省了能量，减少了能量的浪费。 3.相近的节点之间接收到的数据信息有可能相同或相近，这就需要簇头进行必要的数据融合。更好的提升了能量的利用率。 4.每个簇头都要进行数据融合，因为每个簇头接收到的都是局部数据信息，所以数据信息都是比较相关，给数据的融合带来了较快的速度。 5.LEACH路由算法采用TDMA和CDMA的MAC层机制进行各个节点间的数据信息的传递，保证了簇内各个节点有序的跟簇头节点的传递数据，也保证了簇头Sink节点进行有序的信息传递，从而避免了簇内和簇间的相互通信冲突。 6.LEACH路由协议感应外界的环境信息，是周期性的进行检测，各个周期之间不间断地进行。LEACH协议非常适合长期、连续性的进行环境的检测。为野外长时间、不间断地检测提供了保证。 7.有些检测不需要随时获取检测的数据信息，只是当环境中有意外、异常情况发生时，才进行必要的检测盒数据信息的传递。这种不需要周期性的信息传递，减少了无线传感器网络的能量消耗，提高了网络的生命周期。 8.每进行完一轮数据信息的传送，网络进行重新的簇头选举，保证了各个节点之间能量的均衡消耗，提高了能量的利用率。 四、LEACH算法的缺点 1.LEACH路由协议算法中没有说明簇头节点如何进行选举分配，才能保证网络数 无线传感器网络LEACH算法的综合改进 陈楠，徐塞虹 北京邮电大学计算机科学与技术学院，北京（100876） E-mail：chennan6062@https://www.doczj.com/doc/5915137304.html, 摘要：本文通过研究无线传感器网络的层次型路由协议LEACH算法，指出了其存在的一些缺点，并对其某些改进算法进行深入研究，在此基础上进一步改进，吸取已有算法的优点，弥补其中的不足，提出了一种新的分簇算法及簇的维护算法。 关键词：无线传感器网络，层次型路由协议，LEACH算法，改进 中图分类号：TP393 1.引言 传感器技术、通信技术和计算机技术是现代信息技术的三大支柱，它们分别完成对被 测量对象的信息提取、信息传输及信息处理。将这三种技术融合在一起的无线传感器网络技术给人们生活的各个领域带来了极大的影响。作为一种全新的技术，无线传感器网络给科技工作者提出了很多具有挑战性的课题，其中路由协议就是热点之一，传统网络的路由协议远远不能满足无线传感器网络的特点和要求，因此，该领域具有很大的研究价值[1]。本论文在已经提出来的分层次路由协议的基础上进行进一步改进，从而使网络性能又进一步的提升。 2.研究背景 无线传感器网络是由大量功率低、体积小、价格便宜的传感器节点组成的，这些节点实时监测、感知和采集网络分布区域内的各种环境或者被监测对象等诸多用户所感兴趣的信息，并对这些信息进行分布式处理，随后传递给用户，使用户随时随地都可以获取所需的信息。由于传感器网络所具有的特点，其应用前景十分广泛。 但是由于无线传感器网络这些特点的存在，导致节点能量资源、计算能力和带宽等资源都非常有限，尤其是其有限的能量直接影响传感器网络的生命周期以及网络的信息质量。因此，设计有效的策略，降低节点能源损耗，提高网络生命周期成为无线传感器网络的核心问题。 影响节点能源损耗的因素有很多，其中最重要的就是路由协议以，但是传统的那些路由协议应用于无线传感器网络中在某些方面存在一定的缺陷，所以基于传统路由协议，W.R Heinzelman等人提出了低功耗自适应集群型分层路由协议（Low Energy Adaptive Clustering Hierarchy Protocol），LEACH协议[2]是第一个在无线传感器网络中提出的层次式路由协议，其后的大部分层次式路由协议都是在它的基础上发展而来的。该算法主要是通过随机选择簇头，平均分担中继通信业务来实现能量消耗的减少，与一般的平面多跳路由协议和静态成簇算法相比，LEACH可以将网络的生命周期延长15%。 3.LEACH算法概述 LEACH（Low energy adaptive clustering hierarchy）是一种以最小化传感器网络能量损耗为目标的分层式协议，它既可以作为一种传感器网络的基本路由协议，也可以作为传感器网络的拓扑控制算法，因为协议在形成分层式拓扑结构的同时，也确定了簇首，决定了网络的路由。 leach_mit结构图 从wireless.tcl文件中分析leach的具体流程 在wireless.tcl文件中首先初始化了很多无限仿真的配置。引用了一些外部脚本——source tcl/lib/ns-mobilenode.tcl（主要是包含移动节点类Node/MobileNode的一些otcl类函数的定义）、source tcl/lib/ns-cmutrace.tcl（trace文件的tcl脚本）、 source tcl/mobility/$opt(rp).tcl（将几种不同的协议的具体应用的外部脚本引用，$opt(rp)是协议名称）。当一些变量初始化过后，通过 elseif { [string compare $opt(rp) "leach"] == 0} { for {set i 0} {$i < $opt(nn) } {incr i} { leach-create-mobile-node $i 建立我们仿真的节点，最主要的函数是leach-create-mobile-node（这个函数的定义在uamps.tcl中） 分析uamps.tcl中是如何定义节点的？？？ 在uamps.tcl中初始化了bsnode的应用类型（Application/BSApp）、定义了二个能量传输模型（自由信道和多径衰落、Efriss_amp和Etwo_ray_amp）和很多参数。而真正创建节点是在函数leach-create-mobile-node中。而这个函数中调用了uamps.tcl中的sens_init，这个函数的功能是清除上一次模拟时留下的trace文件。在创建节点时候，sens_init函数调用一次。leach-create-mobile-node函数解释如下： 1、节点定义： if {$id != $opt(nn_)} { puts -nonewline "$id " set node_($id) [new MobileNode/ResourceAwareNode] #将前opt(nn_)-1个点定义为一般节点 } else { puts "($opt(nn_) == BS)" set node_($id) [new MobileNode/ResourceAwareNode $BS_NODE] #将第 opt(nn_)个节点定义为最终的sink节点 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; * https://www.doczj.com/doc/5915137304.html, * * Created on: 2011-4-17 * Author: syj */ #include 算法是，对特定问题求解方法和步骤的一种描述，它是有限指令的有限序列，其中每个指令表示一个或多个操作。 算法与程序的比较 ?算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。 ?程序是用某种程序设计语言对算法的具体实现。 ?程序 = 数据结构 + 算法 算法的特性 一个算法必须具备以下五个重要特性： ?有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ?确定性算法中每一条指令必须有确切的含义，没有二义性，在任何条件下只有唯一的一条执行路径，即对相同的输入只能得到相同的输出。 ?可行性算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 ?输入一个算法有零个或多个输入 ?输出一个算法有一个或对个输出 算法设计有正确性（Correctness）、可读性（Readability）、健壮性（Robustness）、高效性（Efficiency）的基本要求。 一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。 算法效率分析 算法效率主要从一下两个方面来考虑： 1.时间效率：指的是算法所耗费的时间； 2.空间效率：指的是算法执行过程中所耗费的存储空间。 时间效率和空间效率有时候是矛盾的。 时间效率分析 一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行简单操作次数的乘积。 算法运行时间 = 一个简单操作所需的时间 x 简单操作次数， 也就是算法中每条语句的执行时间之和 每条语句执行一次所需的时间，一般是随机器而异的，取决于机器的指令性能、速度以及编译的代码质量，是由机器本身软硬件环境决定的，它与算法无关。所以，可以假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论改算法中所有语句的执行次数了。 例如：两个n x n矩阵相乘的算法课描述为： for(i=1;i<=n;i++) //n+1次 for(j=1;j<=n;j++) //n(n+1)次 { c[i][j]=0; //n*n次 for(k=0;k 目录 一、Leach协议与NS的关系 (2) 二、算法设计思想 (3) 三、簇头建立算法流程图 (5) 四、难点解决 (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, 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的 输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1）.数据：运算序列中作为运算对象和结果的数据?2）.运算：运算序列中的各种运算：赋值,算术和逻辑运算 3）.控制和转移：运算序列中的控制和转移. 算法分类 从解法上：数值型算法：算法中的基本运算为算术运算；非数值型算法：算法中的基本运算为逻辑运算. 从处理方式上：串行算法：串行计算机上执行的算法；并行算法：并行计算机上执行的算法 算法的五个重要的特性 （1）有穷性: 在有穷步之后结束。 （2）确定性: 无二义性。 （3）可行性: 可通过基本运算有限次执行来实现。 （4）有输入 f表示存在数据处理 （5） 伪代码 有输出A 程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言 （例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1）使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2）以自然语言的自由语法描述了处理过程；3）数据声明应该既包括简单的也包括复杂的数据 结构；4）使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度。 #define MAX 20 //定义最大的方阶 void matrixadd (int n,int A[MAX][MAX], int B[MAX][MAX],i nt C[MAX][MAX]) { int i,j; for (i=0;i LEACH协议的改进算法 夏北浩 （湖南大学信息科学与工程学院长沙410082） 摘要：首先介绍了LEACH协议的工作原理，性能分析以及不足。之后介绍了LEACH的改进算法。 关键词：无线传感器网络,LEACH协议,改进算法,能量消耗 Improved algorithm of LEACH Xia Beihao (The College of Information Science and Engineering, Hunan University 410082) Abstract: This paper firstly introduce the content of the working principle of LEACH , the analysis of performance and discourages,following the introduction of the improved algorithm LEACH . Key: wireless sensor networks, LEACH protocol,Improved Algorithm,Energy consumption 1 引言 近年来，由于无线技术、计算机技术与传感器技术的迅猛发展和快速融合，无线传感器网络应运而生。无线传感器网络技术作为一种新型网络技术受到研究者的普遍重视和广泛研究。但传感器网络也有一些固定的缺点：能量利用率低、生存周期短、抗干扰能力差。通过良好的算法不仅可以减少传感器节点的能耗，还可以降低通信干扰，提高mac协议和路由协议的效率。因此，提出一个高效稳定合理的算法便成为迫切需要解决的问题。 2 LEACH协议的介绍 2.1 LEACH协议 LEACH是WSN中第一个基于分簇的路由算法，它将网络中的节点分为簇头节点和簇内节点。由于簇头节点需要协调簇内节点的工作，负责数据的融合和转发，能量消耗相对较大，所以LEACH采用周期性地随机选择簇头节点以均衡网络中节点能量消耗。从而达到延长网络生命周期目的。LEACH协议以“轮”作为运 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模 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 在给定的时间间隔后，协议重新选举蔟首节点，以保证无线传感器网络获取同意的能量分布。 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)=√n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题 实验3 LEACH的分簇功能实现 实验目的： 本次做的是LEACH的分簇功能实现的实验。LEACH算法是一种无线传感器网络路由协议，来源于Wendi RabinerHeinzelman, AnanthaChandrakasan, 和HariBalakrishnan三人在2000年Proceedings of the 33rd Hawaii International Conference on System Sciences上的一篇文章Energy-Efficient Communication Protocol for Wireless Microsensor Networks。LEACH协议的解释是：低功耗自适应集簇分层型协议，该算法基本思想是：以循环的方式随机选择蔟首节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。仿真表明，与一般的平面多跳路由协议和静态分层算法相比，LEACH 协议可以将网络生命周期延长15%。而本次实验中我们仅仅需要实现该算法的分簇功能，接待你的通信功能不做要求。 实验方法： 在簇建立阶段，传感器节点随机生成一个0，1之间的随机数，并且与阈值T(n)做比较，如果小于该阈值，则该节点就会当选为簇头。T(n)按照下列公式计算： 式中：P为节点成为簇头节点的百分数，r为当前轮数，G为在最近的1/p轮中未当选簇头的节点集合。簇头节点选定后，广播自己成为簇头的消息，节点根据接收到的消息的强度决定加入哪个簇，并告知相应的簇头，完成簇的建立过程。整个算法实现de流程图如下所示： 实验内容： clear; pm=100; %概率范围 xm=100; %x轴范围 ym=100; %y轴范围 line=10; %连线距离初始值 sink.x=0.5*xm; %基站x轴50 sink.y=0.5*ym; %基站y轴50 n=100; p=0.08; for i=1:1:n %随机产生100个点 《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j]LEACH算法仿真结果
算法分析与设计习题集整理
LEACH算法的学习摘要
无线传感器网络LEACH算法的综合改进
Leach算法分析
数据结构与算法分析习题与参考答案
LEACH算法源代码
算法与算法分析
Leach代码分析
算法分析与设计
LEACH算法的改进
算法设计与分析学习总结
LEACH协议的算法结构及最新研究进展
算法设计与分析课后习题
实验3 LEACH的分簇功能实现
《算法分析与设计》作业参考答案
相关主题
文本预览