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

近年来随着传感器和无线通信技术的进步，无线传感器网络（WSN）技术发展迅猛，进展很快，使我们可以把大量低成本的传感器分布在广阔的区域来监测我们所感兴趣的环境。传感器通过无线网络连接起来形成无线传感器网络（WSN），WSN有一些自身的限制，如：有限的能量供应[1,2]，有限的计算能力和有限的连接传感器的无线链路的带宽，而且WSN的应用领域也给路由协议带来了一些限制，比如说，WSN可能随意地分布在恶劣的或不可到达的环境中，人为维护十分困难，因此延长网络寿命是无线传感器网络协议设计的关键技术。
无线传感器网络
　　无线传感器网络由大量传感器节点和一个基站（BS）构成，基站是节点与其它网络通信的出入口，传感器节点监测环境并将收集的数据传给基站。然而，它能量有限，直接将数据传给基站会消耗很多能量（图1）。采用多跳的路由方法也不理想，因为最接近基站的节点会因路由大量收到的数据而很快死亡，从而导致后来到达的数据不能传给基站。其它的路由方法中[3,4]，PEGASIS中的节点只与邻居节点通信，节点轮流发送融合后的数据给BS，基于蚁群算法的路由在尽量选择最短路径的同时考虑每个节点的能量消耗，以选出更合适的路径。
　　本文中，我们重点评价更具有能量有效性的分簇路由算法，它将无线传感器网络分成若干簇，每个簇选举出一个簇头，簇头作为本地基站将簇内节点传给它的数据进行数据融合[5]后再传给基站（图2），因而大大降低了节点消耗的能量，延长了网络寿命。

图1  传感器系统模型一

图2  传感器网络系统模型二
无线传感器网络中的分簇路由算法
传统路由算法
　　直接路由算法中节点直接将数据传送给基站，这样远离基站的节点会消耗很多的能量而很快死亡。而MTE(MinimumTransmissionEnergy)[6]是它的一个改进，它采用多跳的方法传送数据，每个节点运行建立路由以确定下一跳邻居节点，这个邻居节点是朝BS方向上离它最近的节点（假设每个节点都知道网络中其它节点的位置），数据包通过下一跳邻居节点传送直到到达BS。
　　在MTE这种路由算法中最接近基站的节点会因路由大量传来的数据而很快死亡，而直接通信中是离基站最远的节点最快死亡。
最基本的分簇路由算法
　　为了解决传统路由算法中的高能量耗散问题，提出了LEACH（Low-Energy Adaptive Clustering Hierarchy）[7]—一种最基本的分簇路由算法，每个节点根据一定的概率周期性地轮换做簇头，成为簇头的节点用相同的发射功率给网络中的所有节点广播消息，非簇头节点选择加入收到信号最强的那个簇头的簇并用CSMAMAC协议发消息给簇头，通知其成为它的成员。之后，簇头根据簇中节点数目创建TDMA[8]时间表告诉每个节点发送数据的时隙，以避免碰撞的发生。另外，簇头还要通知簇成员使用哪种CDMA编码，簇头也使用这种编码过滤收到的数据，这样邻居簇的信号就会被当为噪声过滤掉，因此不会影响簇内通信。节点只在分配给它们的时隙内发送数据，其它时间关闭其无线发射机以节约能量，到此，簇就形成了。在数据发送阶段，簇头将成员节点传给它的数据进行融合后直接传给BS。
　　在LEACH中，成员节点在分配的TDMA时隙内总有数据传给簇头，为了节约能量，节点也许只需在它检测到有兴趣的数据时才传送数据，另外，算法周期性地分簇会消耗节点很多能量。因此，我们需要在以后的路由算法中在这些方面对它进行改善。
可形成最佳簇的中心控制分簇路由算法
　　LEACH虽节约能量，但它不能形成最佳簇。中心控制算法通过基站来控制形成最佳的簇。
　　LEACH－C中，每个节点发送包含自身位置信息和能量信息的消息给BS，位置信息可以保证形成优良的簇，为了将能耗平均分摊给所有节点，BS计算网络节点的平均能量，低于此能量的节点都不能做簇头，因此用LEACH－C可以形成比LEACH更优良的簇，它的其它阶段和LEACH一样。静态分簇（StaticClustering）中，簇形成方法和LEACH－C一样，只是这些簇头一旦形成，在整个网络生命期都固定不变，其余的数据传输方式和LEACH和LEACH－C一样，但是一旦簇头能量耗尽，簇内节点就失去了通信能力。
　　LEACH－C和LEACH在仿真时间内比Static Clustering明显可以发送更多的数据给BS，并且每单位能量可传送更多的数据，但LEACH－C性能最好。
　　由于LEACH在一些情况中所选的簇头可能全在区域的一端，在另一端的传感器节点可能侦听不到簇头发出的信息，而不能加入任何簇，因此提出了SC(Substractive Clustering)和LMSSC(Least Mean Squared SubstractiveClustering)[9]分簇算法。
　　SC的思想是具有最多邻居数的节点被选为一个簇的中心，在一个确定半径内的其它节点归为它的簇，之后再寻找新的具有最多邻居的节点，这样一直持续下去直到80%的节点已被分簇。
　　LMSSC在SC上进行了修改以形成更好的簇，它的思想是在确定半径内与邻居节点的距离平方和平均值最小的节点被选为一个簇的中心，所有这个半径内的它的邻居节点被划为它的簇。这两种方法都是在簇形成以后再在簇内选择合适的簇头。簇头将收到的数据进行融合后直接或选择一条代价最小（到BS能量消耗最小）的路径将数据传给BS。
　　LMSSC中节点运行的周期比SC中的更长，所以LMSSC产生的簇更佳。并且，选择最小代价路径传送数据的SC和LMSSC比直接传送数据的SC和LMSSC性能更优。
　　HYENAS（Hybrid Energy-Aware SensorNetworks）[10]也是先形成簇，再选择簇头，但它用CBR（Case-BasedReasoning）作为一种决策方法来保证形成合适的簇，CBR技术通过吸取每轮结束时的错误经历来创建黑名单，黑名单是用来存放一组簇的。这些簇的簇成员所用的能量超过了网络中所有节点所用能量的平均值，当当前每个簇的特性（如：簇成员数，簇头到其它节点的距离平方和等）和黑名单中簇的特性有相似之处时，基站就会增加一个簇。如果有少数节点离开了原来的簇时，它们会自己形成子簇，子簇簇头会单独为子簇创建TDMA时间表，然后把这个消息传给它最初的簇头，簇头再传给基站。这种方法能处理少数移动节点的问题，还能大大减少簇头和移动节点的通信距离。
　　当第一个节点死亡或最后一个节点死亡时，HYENAS运行的轮数要比LEACH多。因此，它的网络寿命也就相应更长。