基于权值的无线传感器网络分簇算法

可形成最佳簇的中心控制分簇路由算法

LEACH虽节约能量，但它不能形成最佳簇。中心控制算法通过基站来控制形成最佳的簇。

LEACH－C中，每个节点发送包含自身位置信息和能量信息的消息给BS，位置信息可以保证形成优良的簇，为了将能耗平均分摊给所有节点，BS计算网络节点的平均能量，低于此能量的节点都不能做簇头，因此用LEACH－C可以形成比LEACH更优良的簇，它的其它阶段和LEACH一样。静态分簇（Static Clustering）中，簇形成方法和LEACH－C一样，只是这些簇头一旦形成，在整个网络生命期都固定不变，其余的数据传输方式和LEACH和LEACH－C一样，但是一旦簇头能量耗尽，簇内节点就失去了通信能力。

LEACH－C和LEACH在仿真时间内比Static Clustering明显可以发送更多的数据给BS，并且每单位能量可传送更多的数据，但LEACH－C性能最好。

由于LEACH在一些情况中所选的簇头可能全在区域的一端，在另一端的传感器节点可能侦听不到簇头发出的信息，而不能加入任何簇，因此提出了SC(Substractive Clustering)和LMSSC(Least Mean Squared Substractive Clustering)[9]分簇算法。

SC的思想是具有最多邻居数的节点被选为一个簇的中心，在一个确定半径内的其它节点归为它的簇，之后再寻找新的具有最多邻居的节点，这样一直持续下去直到80%的节点已被分簇。

LMSSC在SC上进行了修改以形成更好的簇，它的思想是在确定半径内与邻居节点的距离平方和平均值最小的节点被选为一个簇的中心，所有这个半径内的它的邻居节点被划为它的簇。这两种方法都是在簇形成以后再在簇内选择合适的簇头。簇头将收到的数据进行融合后直接或选择一条代价最小（到BS能量消耗最小）的路径将数据传给BS。

LMSSC中节点运行的周期比SC中的更长，所以LMSSC产生的簇更佳。并且，选择最小代价路径传送数据的SC和LMSSC比直接传送数据的SC和LMSSC性能更优。

HYENAS（Hybrid Energy-Aware Sensor Networks）[10]也是先形成簇，再选择簇头，但它用CBR（Case-Based Reasoning）作为一种决策方法来保证形成合适的簇，CBR技术通过吸取每轮结束时的错误经历来创建黑名单，黑名单是用来存放一组簇的。这些簇的簇成员所用的能量超过了网络中所有节点所用能量的平均值，当当前每个簇的特性（如：簇成员数，簇头到其它节点的距离平方和等）和黑名单中簇的特性有相似之处时，基站就会增加一个簇。如果有少数节点离开了原来的簇时，它们会自己形成子簇，子簇簇头会单独为子簇创建TDMA时间表，然后把这个消息传给它最初的簇头，簇头再传给基站。这种方法能处理少数移动节点的问题，还能大大减少簇头和移动节点的通信距离。

当第一个节点死亡或最后一个节点死亡时，HYENAS运行的轮数要比LEACH多。因此，它的网络寿命也就相应更长。

基于阈值信息的分簇路由算法

TEEN（Threshold Sensitive Energy Efficient Sensor Network Protocol）[11]协议在LEACH上进行了改进。它的分簇方法和LEACH一样，只是它的簇成员不像LEACH算法那样总是发送数据给簇头。它的每个节点设定了两个阈值，硬门限（HT）和软门限（ST），当节点监测到的数据大于HT并且与前次监测的数据变化值大于或等于ST时才发送数据给簇头，这样可以大大减少节点发射数据的次数，但节点不发送数据用户就会长时间收不到数据或者认为节点死亡。

APTEEN(Adaptive Periodic Threshold-sensitive Energy Efficient Sensor Network Protocol)[12]协议弥补了TEEN的缺点，簇成员节点除了在数据发生明显变化时发送外，还会周期性地发送消息，这样节点除了能节约能量外，用户收到发送来的消息后也可以周期性得获得已存储在基站的数据。

在每个节点的平均能量耗散和存活节点总数性能方面，APTEEN介于TEEN和LEACH之间，但TEEN性能最好，因为TEEN中簇内的节点发送数据的次数最少。

其它的分簇路由算法

PEGASIS（Power-Efficient Gathering in Sensor Information System）[13]的主要思想是每个节点从最近的邻居节点接收和发送数据给最近邻居节点，并且轮流发送融合后的数据给BS，这个方法可将能量负载均匀地分摊给网络中的所有节点。

PEGASIS：与LEACH相比，当相同数目的节点死亡时，PEGASIS比LEACH要运行多一倍的轮数。

基于蚁群算法的路由算法[14,15]是通过在整个网络内建立梯度（节点与相邻节点到基站的最小跳数之差称为梯度）和每个节点之间的信息素（提示数据包选择哪条路径的信息称为信息素）来进行路由选择。在设计信息素浓度的公式时，不仅考虑了节点间的梯度，还加入相邻节点剩余能量的因素。

该算法在尽量选择最短路径的同时，还考虑每个节点的能量消耗，以达到寻找最佳路由的目的。

EBRA(Energy-Based Radius Self-Adjust Routing Protocol)[16]中节点会选择一条平均单位跳数消耗最少能量的路径传送数据，当节点自身的能量降低到一定数值以后，它会向其邻居节点广播进行降低半径的请求来达到维护路由的目的。

Mobile Ad Hoc中的分簇路由算法

在无线传感器网络中少数节点移动的情况下，我们可以借鉴Mobile Ad Hoc网络中的分簇算法[17,18]。Mobile Ad Hoc中，由于节点的频繁移动，分簇的目的则是保证稳定的分簇结构，最小化簇建立和维护的开销，最大化系统中移动节点的寿命。DCA(Distributed Clustering Algorithm)[19]网络拓扑结构在算法执行期间不变，因此它对静态网络很有用。算法中，只有当节点的具有较大权值的邻居节点决定了它自己的角色时，节点才决定自己承担什么样的角色。相反，DMAC(Distributed and Mobility-Adaptive Clustering)适用于拓扑结构不断变化的网络，节点不仅对从其它节点发来的消息做出适当的反应，还对与其它节点连接的链路失败或新链路的出现做出适当的反应。DBCA（Distributed Weighted Clustering Algorithm for Mobile Ad Hoc）[20]的簇形成方法和DWBCP的相似，在簇维护阶段，当节点移出了它的簇边界时，它就广播一个消息要求加入一个新簇，任何收到该消息的簇头都会发送应答消息给该节点，节点根据消息选择加入具有最小权值的簇头的簇，如果在给定的时间内没收到任何消息，就宣布自己做为簇头。当簇头消耗的能量超过事先设定的阈值时，簇头就不再担任这个角色，该簇重新推选簇头。

基于权值的分簇算法

这里提出一种创新的分簇路由算法——基于权值的分簇路由算法。该算法主要研究的是簇头选举方法，每个节点根据自己的剩余能量、邻居数目、与所有邻居的平均距离、与基站的距离、以及能量消耗速度来计算出自己的权值：

其中Ev为节点v的剩余能量，Nv为节点v的邻居数目，即在节点v发射范围内的节点数目之和，δ为簇头能够处理的理想的节点数，Dnv与Dbv分别为节点v与邻居节点的距离之和，与基站的距离，R为簇覆盖范围的直径，Numv为节点v做过簇头的次数，Tv为节点v在现在的能量消耗速度下，直到能量水平达到最小可接受的阈值时的期望时间，W1—W6为权值因子，根据系统需要选择，它们之和为1。在邻居节点中具有最小权值的节点做为簇头，其它的过程，诸如数据传输过程都与LEACH中的一样。

来源：电子产品世界