文档介绍：WSN 的 LEACH 算法的分析与改进一、研究背景 LEACH 简介 LEACH ( Low2Energy Adaptive ClusteringHierarchy )算法是由 MIT 的 Heinzelman 等人提出的一种低功耗自适应分簇算法。其基本思想是以循环的方式随机选择簇头节点, 将整个网络的能量负载均匀分配到网络中的每个传感器节点, 从而达到降低网络能耗, 提高网络生存周期的目的。运行原理 LEACH 在运行过程中不断地循环执行簇的重构。算法操作使用了“轮”的概念, 每一轮由初始化和稳定的工作两个阶段组成。在初始化阶段, 每个节点产生一个 0 ~1 之间的随机数, 如果某个节点产生的随机数小于所设的阈值 T(n) ,则该节点发布自己是簇头的消息。缺点在 LEACH 算法中,每一轮循环都要重新构造簇,而构造簇的能量开销比较大。其次, 远离汇聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量,造成网络分割。另外, LEACH 算法没有考虑簇头节点当前的能量状况, 如果能量很低的节点当选为簇头节点, 那么将会加速该节点的死亡,影响整个网络的生命周期。二、 LEACH 算法分析 LEACH 的运作以“轮”来实现, 每一轮开始是簇头的建立阶段, 其次传输数据到基站的稳态阶段。为了尽量减少开销,稳态阶段比簇建立阶段时间长。 2 .1 簇选举阶段簇头选举初始阶段, 每个节点根据所建议网络簇头的百分比( 事先确定) 和节点已经成为簇头的次数来确定自己是否当选为簇头。每个节点产生一个 0-1 的随机数字, 如果该数字小于阈值 T (N ) ,节点成为当前轮的簇头。阈值 T (n )= 其中, P 为预期的簇头百分比(例如, p= ),r 为当前轮数, G 是最近 1/p 轮里没有成为簇头的节点的集合。使用这个阀值, 每个节点会在 1/p 轮的某一轮成为簇头。在0 轮(r =0 ), 每个节点都有一个成为簇头的概率 P 。当选为簇头的节点不能在未来的 1/P 轮当选为簇头。因此,只有较少的节点有资格当选为簇头节点,剩余节点成为簇头的概率必然增加。 1/p-1 回合后对任意还没当选为簇头的节点 T (n ) =1 , 可见, 1/P 的回合后, 所有节点都再次有资格成为簇头。以后的工作中,我们会考虑到非均匀能量节点的以能量为基础的阀值。在这种情况下, 我们假设所有节点具有相同初始数量的能量, 每个簇头也消耗大约相同的能量。非簇头节点必须保持他们的接收器在此选举阶段听到所有的簇头节点的广告。这一阶段完成后, 每个非簇头节点决定在本轮中加入哪一个簇头节点。这一决定是基于对广告的接收信号强度。假设是对称的传播信道, 收到发送的广告信号强度最大的簇头就是要加入的簇头, 与其通信需要的能量最小。稳定之后表示簇头的随机选举完成了。 2 .2 簇建立阶段在每个节点已决定它属于哪个簇之后, 它必须告知簇头节点, 它将成为该簇的成员节点。每个节点再次使用 CSMA MAC 协议发送这个信息反馈给簇头。在这个阶段, 所有的簇头节点必须保持他们的接收器打开。 2 .3 时间表的创建簇头节点收到所有想加入该簇的节点的消息。基于这个簇的节点的数量, 簇头节点创建一个 TDMA 时间表告诉所有节点什么时候能开始传输数据。这个时间表广播给所有该簇的成员节点。 2 .4 数据传输图 LEACH 协议的时序图一旦簇创建和 TDMA 的时间表是固定的, 数据传输可以开始了。假设节点有数据要发送, 他们在分配给它们的传输时间内发送给簇头。这种传输使用少量的能源( 选择基于收到簇头广告的强度) 。每个非簇头节点的无线电可以关闭,直到分配给节点的传输时间到来,从而减少在这些节点的能量消耗。簇头节点必须保持其接收机接收到簇内所有节点的所有数据。当所有的数据已经收到, 簇头节点进行数据融合。例如, 如果簇头收到数据音频或地震信号, 簇头节点将这些收到的单个信号融合为一个复合信号。然后将这种复合信号发送到基站。但是由于基站远,这种传输是一种高能量的传输。以上是 LEACH 协议网络的稳定运行状态。经过一定时间后, 下一轮开始, 每个节点决定这轮自己是否能成为簇头, 然后广播这一消息, 2 .5 多个簇图 LEACH 协议过程前面介绍了如何在单个簇头内部之间进行通信的问题。然而, 无线电本质上是一种广播媒介。正因为如此, 在一个簇中的传输会影响( 因此降低) 附近的簇通信。为了减少这种干扰,每个集群通信使用不同的 CDMA 码。因此,当一个节点决定成为簇头,从扩频码的列表中随机选择。它通知在簇的所有节点传输, 使用这种扩频码。簇头会过滤所有收到的能源使用扩频码。因此邻近簇的无线电信号将被过滤掉, 而不会干扰临近簇的数据传输。