Abstract : Clustering algorithm is a important techNIque used to reduce energy consumption,which can increase network scalability and lifetime. The protocol of LEACH (low-energyadaptive clustering hierarchy) is widely used in wireless sensor network. But it has thedisadvantage of unbalanced load. Based on LEACH, a new load-balanced LEACHcommunication protocol(CM-LEACH) is proposed，a new protocol adopt cross-multi-hopsalgorithm that an optimal path is formed among cluster heads which lead to path. Simulationresults demonstrate that our proposed approach is effective to balance the energy-consumingamong clusters and prolong the network lifetime.
Key words : wireless sensor network; load-balanced;cluster;cross-layer; multi-hops
0 引言
无线传感器网络是由一组传感器节点通过无线介质连接构成的无线网络，它采用ad hoc方式配置大量微型的智能传感节点，通过节点的协同工作来采集和处理网络覆盖区域中的目标信息[1]。网络的拓扑结构对网络的性能有重要的影响，传统上根据网络的逻辑结构把网络分层平面路由和层次路由。在平面路由里，网络中的所有节点的地位是同等的，它们通过相互之间的信息反馈及相应操作来实现路由，一般情形下，汇聚节点通过向目标节点发出查询信息，目标节点反馈监测的数据。在WSN 中，典型的平面路由算法有定向扩散路由协议DD(directed)[2]和信息协商协议SPIN(sensor protocols for interformation via negotitong)[3]等。
平面路由易部署、易扩展、健壮性比较好，但是没有对网络优化管理、对动态网络变化反应较慢。在分层路由协议里，网络中节点的功能是不同的，一般把节点分成汇聚节点和普通节点，汇聚节点实现数据的收集、处理和转发，普通节点实现区域内监测。聚类路由协议是比较常见的，一般是把网络中的节点分成簇头和簇内节点，每个簇内簇头节点管理普通节点，簇首节点把收集到的簇内几点的数据处理后发送给远处的基站。低功耗自适应分层协议LEACH(Low-Energy Adaptive Clustering Hierarchy)[4]是WSN 中比较典型的分层路由协议。
本论文通过对 LEACH 的阐述和分析研究，提出一种多层多跳的路由协议。本文首先介绍了LEACH 的协议体系，然后分析了此协议能耗不均匀的原因，最后对LEACH 协议进行了改进的实验模拟，并且对我的工作进行了总结和对未来的展望。
1 LEACH 协议体系及分析LEACH(Low-Energy Adaptive Clustering Hierarchy)[5]协议是由MIT 的Wendi B.
Heinzelman,等人首先提出的，基于聚类结构的分层技术协议。LEACH 协议的执行过程是周期的，它把一个周期叫做一轮，每轮分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段，随机产生簇头;在数据通信阶段，簇内节点把数据发给簇头，簇头进行数据融合后再发送给远处的汇聚节点。
簇头节点的选择具体过程[6]如下：节点产生一个0-1 之间的随机数，如果这个数小于阈值P(n),则发布自己是簇头节点。如果在本轮中已经当选过簇头的节点，则把P(n)设置为0，这样该节点不会再次当选为簇头。对于为当选过簇头的节点，则以概率P(n)当选，随着当选过簇头的节点数目的增加，剩余节点当选簇头的阈值P(n)随之增大，节点产生小于P(n)的随机数的概率随之增大。当剩余一个节点未当选时，则P(n)=1，即该节点一定当选。
公式中：p：网络中簇头数与总节点数的百分比;r：当前的轮数;G：最近1/p 轮中不是簇头的节点集。
节点当选簇头后，发布消息告知其它节点自己是簇头。非簇头根据接受信号的强度决定加入那个簇[7]，并通知簇头。最后簇头产生一个TDMA 定时消息，并且通知簇内节点。当簇内节点收到TDMA 同步消息后，它们将在各自的时间槽内发送数据，在时槽外是进入睡眠状态。
簇形成，TDMA 时刻表确定后，就进入了本轮的数据传输阶段。簇头节点把来自簇内节点的数据进行数据融合和压缩处理后，传给远处的基站。经过一个TDMA 时刻表后，新的一轮又开始了，如此循环运行，直到大多数节点能量耗尽为止。
协议在对节点通信时使用了第一无线电能量模型(fisrt order radio model)。能量消耗与通信的距离通信的影响遵循公式(2)，式中当距离d 比较小时，遵循自由空间能耗模式，n=2;当d 大于阈值dO时候，n=4，遵循多径衰落能耗模式。
假定本轮中在N个节点中有k个簇头CH，均匀的分布在M ? M 的区域内，则每个簇中CM的个数为( N / k ) ? 1 。由于基站距离节点比较远，所以能量消耗遵循多径衰落信道模式。
那么簇头消耗的能量为：
其中：l 是数据包的大小;EDA 是簇头进行数据融合的能量消耗; d toB S 簇头到BS的距离。簇内节点能量消耗为：
假定整个簇内是均匀分布的，分布密度为(x, y)的随机区域，每个簇所占面积为M2 / k，那么通过对帧内消耗总能量求导，可得出最佳的k 值：
2 CM-LEACH 自适应算法LEACH 算法采用层次结构,簇头通过数据融合机制,减少了数据通信量。LEACH 算法随机选取簇头,通过轮换选举将高能量消耗平均分布到网络的所有节点上,使因能量耗尽而失效的节点呈随机分布状态,因而与一般的多跳路由协议和静态聚类算法相比,LEACH 可以将网络生命周期延长[4]。
但是 LEACH 算法中，作者只是模拟了一个比较小的网络，当网络增大时，随着簇头的增多，那么许多簇头与基站进行远距离的数据传输，遵循多径衰落模型，这会导致能量的大幅度损耗，而且簇头的选择没有考虑节点的具体位置，这也将会导致网络中簇分布不均匀。
本文主要是通过多跳方式的设计来减少簇头与基站通信的能量消耗，这里我们假定簇头之间是遵循能耗的自由空间模式，簇头与基站之间是遵循能耗的多径衰落模式。而传统路由算法中，多跳的的最后都是通过一个或者二个节点将数据传给基站，这样应用与WSN 网络中时，必然会导致最后簇头形成“热点”问题。
为了避免这个现象，我们采用跨层处理，即少部分簇头作为大部分簇头和基站通信的中继节点。现在也有许多论文中采用了协助节点多跳的方[8]式改进通信，但是仍然会形成热点问题，而且会簇头和协助节点也增加了额外的能量的。
2.1 网络模型及设计策略本文采用跨层的结构的网络模型，簇头将经过处理的数据发给中继节点，中继节点同时也是簇头，在形成的路由网络中要限制路由跳数。中继节点通过多跳的方式发送给汇聚节点。
网络模型如图1 所示，汇聚节点也叫做基站(BS)。
根据上述分析，本文算法有如下原则：节点是静止的，簇头间及与普通节点在小于自由空间模式阈值dO里通信，汇聚节点可以和任意一个节点通信，网络中通信线路是对称的，网络中节点的初始能量相同而且有限，节点能自由选择发射的能量范围且支持休眠的MAC协议。
因此此处需要使用到的集合与变量定义如下：
d ：节点到基站的距离，初值为空。
ID ：节点的编码，设定是唯一的。
S1：簇内节点的集合，初值为空Er：节点的剩余能量，即能量的计数器。
T ：节点的路由表，初值为空，当为簇头时候，才会有值。
I s _ C H ：是否是簇头，初值为否。
Sink nodeCluster headCluster-member本文主要研究跨层设计问题，所以主要是将簇的形成阶段和数据传输阶段中加入了选取中继簇头。在簇的形成阶段，汇聚节点发送一个广播信息，所有节点通过信号的强弱，计算出到汇聚节点的距离。节点仍然由阈值p(n)选取出簇头，然后广播信息告知网络自己已经是簇头。其它节点有信号强度选择的加入某个簇，簇头在收到节点加入簇的请求后，为自己选定下的普通节点设定同步的TDMA 时刻表，并将时刻表发给簇内所有节点。TDMA 时刻表里要留出一个时隙用于路由表的建立。
定义：中继节点(relay node)选取。从簇头中选取少量的的簇头作为中继节点。本文采用选择中继簇头的指标为：
