无线传感器网络低功耗分簇路由算法研究

1 相关研究
    针对无线传感器网络能量受限的特点，对适应其特点的低功耗算法研究也一直继续着。Heinzelman提出了LEACH(Low—Energy Adaptive Clustering Hierarchy，低能耗自适应分簇层次)算法。其核心思想是让每个节点轮流担当簇首，从而使得网络中的能量消耗尽可能均匀，减少网络失效时刻的能量浪费。LEACH算法只考虑了单跳模型，因此只适合于小型wSN网络。参考文献提出了M—LEACH(Multi—hop variant of LEACH，多跳LEACH)算法，簇内的节点不是以单跳的方式传输数据到簇首，而是通过簇内其他节点转发。参考文献提出了一个多跳簇首模型，采用从下到上的策略，逐层生成每一层的簇首，最终得到一个多层结构的WSN网络。参考文献采用基于代价的目标函数对传感器网络设计进行了分析，推导出单跳和多跳的适用范围，最后提出一种单跳多跳混合的路由算法，以解决网络中的“能量热点”问题。本文在前人研究的基础上提出一种适合无线传感器网络能量受限特点的低功耗路由算法。

2 网络模型
    无线传感器网络是由大量部署在观测环境中的微型、廉价、低功耗的传感器节点，以无线、自组织的方式，通过多跳通信而快速形成的网络系统。WSN的典型布撒是通过飞行器撒播、人工埋置和火箭弹射等方式来完成的。图1给出了传感器网络体系结构一般形式的描述。

    假定传感器网络中的各节点随机均匀分布在一个方形区域内，并且具有如下性质：
    ①惟一的基站部署在网络外部较远的位置；
    ②每个节点有惟一的标识；
    ③传感器节点部署后不再移动；
    ④所有节点平等，具有相同的计算和通信能力；
    ⑤节点的地理位置信息不可知；
    ⑥发射节点与不同距离的接收节点通信时，可以调整发射功率。

3 算法描述
    本算法采用LEACH算法中“轮”的思想，每一轮工作由2个阶段组成：一是簇的建立阶段；二是数据传输阶段。在簇的建立阶段，主要完成簇首的选取、簇的生成，以及时限的分配；在数据传输阶段，主要完成的是各个传感器节点把采集到的数据逐层上传到基站，其中包括必要的数据融合、数据加密等处理。
3．1 簇的结构及首轮簇首选举
    在无线传感器网络分簇算法的研究中，大部分都是在网络簇的同构模型上进行研究，例如如何使各个簇的节点数目尽量相同、簇的大小尽量相同，在此基础上有效地降低能量的消耗。多数的分簇算法都采用簇首多跳将数据传输到基站，使得距离基站较近的节点不但要收集本簇内节点传送上来的数据，而且同时要转发其他比它距离基站远的簇首节点发送的数据，这就使得距离基站较近的节点要比远离基站的簇首节点消耗更多的能量。如果采用簇结构同构的分簇方法，往往距离基站较近的簇首能量消耗要相对大，导致新一轮的簇首选举，造成整个网络暂停工作，甚至于节点早期进入死亡阶段。为了避免这种情况发生，本算法初步采用簇大小异构的方法，即距离基站远的簇结构比距离基站近的簇结构大，来均衡转发数据的能量消耗。
    在网络部署阶段，基站用一个给定的发送功率向网络内广播一个信号。每个传感器节点在接收到此信号后，根据接收信号的强度计算它到基站的近似距离。获得这个距离，不仅有助于传感器节点向基站传输数据时选择合适的发送功率以降低能量消耗，而且它还是算法构造大小非均匀的簇的必需信息之一。非均匀分簇网络结构如图2所示。

    靠近基站的候选簇首的竞争半径应该较小。随着候选簇首到基站距离的减小，其竞争半径亦应随之减小。设候选簇首的竞争半径的最大取值为R0c。其中，c用于控制取值范围的参数，在0～1之间取值。候选簇首si确定其竞争半径Rc的计算公式如下：

   
式中：dmax是距离基站最大的距离；dmin是距离基站最小的距离；d(si，DS)是簇首si到基站DS的距离。
    首轮簇首选举相对简单。根据簇首节点比例在网络中选举出簇首，在竞争半径内不允许存在其他簇首，接着竞选产生的簇首向全网广播其竞选获胜的消息CH_ADV_MSG；普通节点选择簇内通信代价最小(即接收信号强度最大)的簇首，发送加入消息JOIN_CLUSTER_MSG通知该簇首。
3．2 簇首生成树的建立及数据传输
    本文采用簇首多跳数据传输的方法，如何选举下一跳簇首节点是本部分要重点阐述的问题。首先引入一个阈值TD_MAX，若簇首到汇聚点的距离小于TD_MAX，则直接与汇聚点进行通信；否则，应该尽量使用多跳路由的方式将数据传送给汇聚点。
    假设d(A，DS)>TD_MAX，则在簇首A的临近簇首集里计算各个若簇首，带来的链路质量开销指标Erelay=d2(A，X)+d2(X，DS)。其中，d(A，X)是簇首A到簇首X的距离；d(X，DS)是簇首X到基站距离；d(A，DS)是簇首A到基站的距离。在Erelay值小的簇首节点中选择剩余能量最大的节点作为中继转发的簇首节点，将数据按照簇首生成树转发到基站。
3．3 各轮簇首选举
    为了延长网络的生命周期，应该尽量选择簇内节点中剩余能量最高的节点为簇首节点，并且让不同的节点轮转当选。本部分采用基于剩余能量的簇首簇内轮换的方法进行簇首选举。其主要思想：簇首在簇内负责收集簇内节点的数据。在节点向簇首发送数据时，在数据位后附加上本节点的剩余能量值位。簇首将数据进行处理转发后，对各节点的能量进行简单的排序，因为不用维持所有节点能量的全排序，只需要知道剩余能量比较高的几个节点，所以采用最大堆的排序方法。在通过数据应答包或者命令包中附加位的方法把这个排序中的前3名节点号及能量值广播到整个簇内，这样做就不会增加广播次数，只是以附带的方式就可以使整个簇内节点都有本簇内剩余能量较高节点的信息。即使簇首节点突然失效或发生异常，其他的节点可以很快根据能量信息选出新簇首。簇内节点保留的都是最近一次的能量信息，由于传感器网络休眠的时同比较长，即使簇首突然失效，信息的变化也不会很大，完全可以根据这次排序来选举出新的簇首。新簇首选出后，负责完成数据收发处理及能量排序等工作。
    通过本算法每次都选出剩余能量最多的节点当选簇首，使簇内信息收集和主干网络通信更加稳定，并避免了每轮簇首选举时所有节点相互交换能量信息所需的大量开销。

4 性能分析
    本部分比较各种分簇协议对网络存活时间的影响。图3显示了网络中存活节点数目的各轮变化情况。从图中可以看出，无论是第一个节点死亡的时间还是最后一个节点死亡的时间，本文算法均优于其他3种协议。节点死亡时间的跨度可以反映出网络中节点的能量均衡情况，时间跨度短说明网络的能量使用高效。本文算法不仅显著地延长了网络的生存时间，而且时间跨度也小于其他3种协议，这说明该算法很好地均衡了网络中所有节点的能量消耗。

    通过试验结果可以看出，本文提出的算法具有如下优点：分簇算法稳定，所生成簇的簇个数不变，能量消耗低，且有效平衡了簇首能量消耗，显著延长路网络的生存时间。总之，用网络的生存时间这一重要指标来衡量，其性能显著优于其他3种分簇协议。

5 总 结
    本文算法在初始化簇结构时，采用非均匀分簇的方法，避免了由于数据沿簇首生成树多跳传输而导致近基站簇首多余能量的消耗，解决了簇首能量不均衡的问题；采用基于剩余能量的簇首簇内选举的方法，避免了所有节点参与每轮的簇首选举过程带来的不必要的能量消耗，保证了剩余能量最多的节点担任下一任簇首；用簇首建立主干网络进行数据多跳传输，合理选择下一跳簇首节点，减少了簇头长距离传输数据的能量消耗。