0 引言

无线传感器网络(WSN)是由大量无处不在的、具有通信与计算能力的微小传感器节点密集布设在无人值守的监控区域而构成的能够根据环境自主完成指定任务的“智能”自治测控网络系统。无线传感器网络的随机布设、自组织、环境适应等特点使其在军事、环境、医疗、家庭和其它商用领域有广阔的应用前景和很高的应用价值。传感器节点通常使用容量有限、不可更换的电源，节点的计算、通信、存储能力也非常有限，这就要求WSN路由协议必须以节约能源为主要目标，最大限度地延长网络生存时间。在许多大规模WSN远程监控应用中，传感器需要将采集到的声音、振动等数据以无线多跳的通信方式传送到远程基站(BS)以便实现进一步的分析和处理．同时，BS的控制信息也通过节点间的协同交互传递到指定区域。由于通信损耗能量同传送的数据量和到达目标的距离平方成正比，采用基于分簇的路由算法相对平面路由算法具有更好的适应性和节能性。分簇路由的基本思想是通过簇首对簇内节点间的相关信息融合及转发机制减少数据的传输量和距离，进而降低通信能量，达到网络节能的目的。

LEACH算法是比较成熟且常用的分簇路由算法。但LEACH算法并没有考虑到每个节点的能量状态因而不能有效提高网络的生存时间，本文主要在能量的基础上对LEACH算法做出了改进。它基于无线电传输范围和簇成员数目形成簇，并在转发阶段引入CSMA/CD (载波监听多路访问/冲突检测)技术以减少冲突。仿真证实改进后的算法在能量消耗上比LEACH算法有了大大减少。

1 相关算法

在目前典型的分簇路由算法中，LEACH算法是Heinzelman等人提出的第一个基于多簇结构的路由协议，其成簇思想贯穿于其后提出的很多协议中。其中，文[3，4]采用了与LEACH相同的随机簇首选择机制，每个节点根据网络所决定的最优簇首概率P自主判定是否成为簇首，一旦选定簇首节点后便通过广播告知整个网络．随机簇首选择机制具有实现简单、操作灵活和可扩展性好等优点，但是却不能保证簇首节点的数目和分布，因此容易形成网络内节点能量损耗不均衡的状态，从而降低了网络的整体性能。文[5]提出了一种集中式的簇首选择机制LEACH-C，它要求只有能量高于网络平均剩余能量的节点才有可能成为簇首．为了评估网络剩余能量的平均值和优化簇首的选择，每个节点需要和BS直接通信来汇报自身的位置和能量信息，因此算法需要消耗较多的通信能量。文[6]构建了一种节能、分布式的成簇算法HEED，但在选择簇首时需要在一定的迭代次数内与周围邻居节点不断地进行信息交互，因此算法的实现也需要额外的通信代价。[1]

2 分层算法简介

2．1 LEACH算法

LEACH算法建立在所有节点都是平等且无线电信号在各个方向上能耗相同的假设上。在LEACH算法中，节点自组织成不同的簇，每个簇只有一个簇头。所有非簇头节点将自己的数据发给所属簇的簇头节点，为减少冗余数据的传输，簇头节点在数据融合后将数据发送给远方的接收器。这样，每个非簇头节点都只需要知道自己所属簇的簇头信息即可；簇头也只需要维持很小的路由表。在实际使用中，还可以根据需要建立更多层次。在LEACH算法中，为了避免簇头能量消耗过快，每个节点须轮流担任簇头。因此LEACH算法的实现分成一个个回合，每个回合又可分成簇形成阶段和簇稳定阶段。为了减少分簇带来的额外能耗，簇稳定阶段远远长于簇形成阶段。在簇形成阶段，每个传感器节点先生成O一1之间的随机数，如果生成的随机数小于阀值，那么这个节点就被选为簇头。阀值的大小下式确定：

其中：p是网络中簇头所占比例，r是目前进行的回合次，G是在最后1／p轮中没有成为簇头的节点集合。节点被选为簇头后，就向外发送广播信息；其它节点根据收到的广播信息的信号大小决定要加入的簇，并向簇头发送加入簇的请求。簇头收到请求后将节点加入自己的路由表并为每个节点设定一个TDMA时间表，再将该表发送给所有簇内节点。此后的簇稳定阶段，节点按照该表进行数据传输。每隔一定时间整个网络重新进入簇形成阶段开始新轮的簇头选举过程。

和平面路由算法相比，LEACH算法性能更好。但是，由于LEACH算法中簇头的产生具有极大的随机性，可能会出现部分簇头相距基站远近不一，或者节点相距簇头远近不一，以及每个簇中节点数目分布不均匀，网络拓扑结构分布不均匀使得节点消耗能耗不一，大大减少了网络生存时间。

另外在节点被选为簇头后，以另外的簇头为中转站向基站发送数据的时候，由于中转站节点有可能正在接收其他节点给它发送数据，容易导致冲突，影响网络作用。

正是基于LEACH算法的以上缺点，对它进行了改进，改进后的算法和LEACH算法采用相同的网络要求。

2．2 改进后的算法

   和LEACH算法一样，改进后的算法依然分成一个个回合，但这里把每个回合分成形成阶段、稳定阶段和转发阶段。同时在每个回合之前构建簇。

2．2．1簇的初始化

每个节点都向邻居发送HELLO信息，此信息的TTL域（Time to Live）被设置成1，意味着只需收集1跳的邻居数目，同时无线电传输范围也被设置成定值，这样做是为了把簇的范围限定在以该定值为半径的圆中，每个节点都记录下它周围一跳的邻居数目，同时定义一个系统参数CN，用它来记录簇的成员数目，当一个节点获得的邻居数目首先到达CN时，该节点就会向它周围一跳的邻居广播一个“我是簇头”的信息，所有收到此信息的节点记录下它，同时启动一个后退定时器，之后收到此广播的节点即使它们的邻居数目到达CN，也不会再宣布它们为簇头，因为算法硬性规定在无线电传输范围内只能存在一个簇头。在后退定时器时间到达以前，每个节点都会根据信号的强度来决定加入哪个簇，同时发送一个加入信息给簇头，这样每个簇头都会了解自己共有多少簇成员，同时记录下自己簇成员的数目，并将此数目广播给基站，基站会根据此数目计算每个簇需要的最大时间片，并通知簇头。

2．2．2形成阶段

     由于每个簇的最大成员数目已经被CN限制了，在每个回合中，每个簇头能够为簇成员调度TDMA时间片， 在此阶段，每个节点都会如LEACH算法中一样，打开接收器，然后，簇头会广播一个包含TDMA时间片的消息，每个簇成员都会了解属于自己的时间片，至此，簇成员会关闭接收器，直到自己的时间片到达，在时间片到达期间，簇成员能够传输数据以及它的剩余能量值，簇头保留了一个记录有在当前回合有最大能量值的节点的表，在簇头将数据传输到BS之后，它选择有最大剩余能量的节点作为下一个回合的簇头，在下一个回合的形成阶段，它会广播包含有当前回合的簇头的消息。   

2．2．3 稳定阶段

一旦簇头被建立，TDMA调度被固定，数据传输就开始了，假设节点一直都有数据去传输，它们在自己的时间片内传输数据和能量值到簇头，簇节点依据簇头广播信息的信号强度来动态的调整它的传输能量，在此阶段，仅仅是簇头一直开启它的接收器，其他节点只是在分配的时间片期间开启接收器。

2．2．4 转发阶段

此算法使用跳数和能量值两个参数去确定簇头之间的层次关系。接下来的步骤对此进行了详细说明。

第一步：BS周期性的广播HELLO信息。其中包含从BS到簇头的跳数，以及能量值， 前者被初使化为0，后者被初始化为无穷大。当收到此消息时，非簇头节点不会理睬此消息。但接收到此消息的簇头节点会将跳数加1，同时比较消息中的能量值和自身能量值，如果自身能量值更低，消息中的能量值被自身能量值替代。

第二步：在簇头收到HELLO信息后，簇头会记录下发送此消息的给它的簇头X，同时将此X作为簇头到BS的中转站。

第三步：如果一个簇头收到另外的HELLO信息，它会按照以下原则做出决定：

（1）       旧的跳数<新的跳数，什么也不做。

（2）       旧的跳数>新的跳数，替换此中转站簇头。

（3）       如果旧的跳数=新的跳数，但旧的能量≤新的能量，替换此中转站簇头，其余情况，什么也不做。

在簇头之间的层次关系建立以后，为了避免冲突，这个时候启用了CSMA/CD机制。一旦收集完数据的簇头发送数据到BS，它会选择另一个簇头节点做中转站。并在该中转站的两个时间片之间的间隔时间发送数据。它会根据该中转站在形成阶段广播的TDMA调度来估计是否该中转站是否处于两个时间片之间的空闲时间。如果它正在接收其它节点发送的数据，那么此簇头等待一段时间。直到监听到该中转站已经空闲，簇头才将数据发送到中转站节点，然后中转站节点又会用同样的方法来发送数据到BS。

3仿真和分析

3．1仿真环境介绍

    在仿真中使用了以下参数。网络大小为100*100平方米。共100个传感器，一个簇中成员数为15或者20。仿真使用40KBPS传输速率的无线模式。数据大小为36字节。网络拓扑是随机均匀分布。为了易于表示，用NEW来代替改进后的算法。

3．2性能估计和分析

图一和图二显示了能量消耗的仿真结果，最初，改进后的算法消耗了更多的能量，这是由于簇头的初始化消耗了能量，但是从长远来看，LEACH算法消耗了更多能量。

图一：15个簇成员的能量消耗

图二：20个簇成员的能量消耗

同时，这篇论文也总结了节点初使能量为025J，0.5J，1.0J的网络，第一个节点死亡时的结果，见表一，很明显，LEACH算法比改进后的算法更早出现节点死亡。

表一：网络中第一个节点死亡所需回合数

4总结和未来工作展望

本文作者创新点：针对LEACH算法中簇头产生具有极大的随机性，使得节点消耗能耗不一，以及在转发阶段容易发生冲突问题，从而导致减少网络生存时间。提出了改进的算法，仿真结果表明：改进后的算法使得能量消耗大大减少，延长了网络的生存时间；本文提出的在簇层次建立后引入CSMA/CD(载波监听多路访问/冲突检测)技术非常有创新意义。这一改进对以LEACH协议组网策略为基础的分层网络研究很有意义。

参考文献

[1] 张延虎，常宇健，杨卫东．磁阻传感器在机器人玩具中的应用[J]，微计算机信息，2005，3：103—105

[2] Jichuan Zhao, Ahmet T. Erdogan.”A Novel Self-organizing Hybrid Network Protocol for Wireless Sensor Networks”,,2006,IEEE.,Proceedings of the First NASA/ESA Conference on Adaptive Hardware and Systems.

[3] ManjeshwaR A。Agrawal D．TEEN：a protocol for enhanced efficiency in wireless sensor networks[A]．Proceedings of the 1 st International Workshop on Parallel and Distributed Computing

Issues in Wireless Networks and Mobile Computing[C]．New York。USA：ACM Press，2001．304—309．

[4] Bandyopadhyay S，Coyle E j．An energy efficient hierarchical clustering algorithm for wireless sensor networks[A]．Proceedings of the IEEE INFOCOM [C]．Piscataway，USA：IEEE。2003．17l3～l723．

[5] Heinzelman W。Chandrakasan A，Balakrishnan H．An application specific protocol architecture for wireless microsensor networks[J]．IEEE Transactions on Wireless Communications，2002，1(4)：660—670．

[6] Younis O，Fahmy S．HEED：a hybrid，energy—eficient，distributed clustering approach for ad hoc sensor networks[J]．IEEE Transactions on Mobile Computing，2004，3(4)：366—379．