分簇技术在无线传感器网络中的应用.docxVIP

分簇技术在无线传感器网络中的应用 0 节点防波剂分簇算法 由于无线传感器网络存在着严重的能量限制，我们主要目标是尽量减少节点的能量消耗，延长网络的生存时间。分簇机制是将网络划分成可以相互通信的,并覆盖网络中所有节点的多个簇,周期性地为每个簇选择簇头节点,这样可以均衡网络中的节点能量消耗。分簇算法是一个重要的研究方面。一个好的分簇算法能够形成优良的网络拓扑结构,提高路由协议及MAC协议的效率,为数据融合、时间同步和目标定位等提供基础。 研究表明,对于大规模的无线传感器网络,层次型分簇路由算法比平面路由算法具有更好的适应性和节能性。但是这就不可避免地导致“热区”问题,即邻近sink节点的簇头由于转发大量的数据,使其能量消耗过快,造成网络分割现象,降低网络存活时间。在网络中,大部分包碰撞、网络拥塞、包丢失都发生在距离基站节点几跳的范围之内,仅仅依靠分布式拥塞控制、层次式网络设计、数据融合等并不能彻底改善基站附近节点的瓶颈环境。所以对sink节点附近的节点进行负载平衡,不但可以对包碰撞、网络拥塞、包丢失的发生有所缓解,还可以平衡节点的能量消耗,延长传感器网络的生命期。 近年来,研究人员提出了多种传感器网络的分簇算法来缓解“热区”问题,其中文献提出了一种基于非均匀分簇(Energy-Efficient Uneven Clustering,EEUC)算法,靠近sink节点的簇的规模小于远离汇聚点的簇,因此靠近sink节点的簇头可以为簇间的数据转发预留能量,这在一定程度上平衡了簇头的能量消耗。但由于靠近sink节点的簇的成员数目较小,从而增加了簇的数量,不利于簇头进行数据融合,会增加数据的流量。在文献中提出了把剩余能量最大的两个簇员作为新的簇头和新的候选簇头算法,即双簇头算法,这种算法簇头耗能较快,因为算法结束时,簇头和候选簇头都要向本簇所有成员发出通告消息,能耗两倍于单簇头。但这种算法达到了负载平衡的目的。 有研究证明双簇头模型比单簇头模型更能延长网络的生存期,有更好的稳定性和安全性。由于网络边缘区域的簇头节点不转发或只转发少量的数据,“热区”内的簇头需要新一轮的选举时,“热区”外的簇头很可能还没有达到阈值。所以在“热区”内使用双簇头算法不但可以提高网络的稳定性和安全性,还能更好地平衡节点的能耗。 为了方便地把“热区”定量的划分出来,在文中使用GAF(geographical adaptive fidelity)算法将传感器网络划分成若干个簇。GAF算法是以节点地理位置为依据的分簇算法。该算法把监测区域划分成虚拟单元格,将节点按照位置信息划入相应的单元格;每个单元格为一个簇,每个簇中只有簇头节点保持活动,其他节点进入睡眠状态。 基于以上的考虑,提出了一种基于GAF的无线传感器网络分簇算法——簇头非均匀分布(Cluster Head Uneven Distributing,CHUD)算法,此算法将在“热区”内的簇执行双簇头算法,来实现负载平衡。这样“热区”内的簇就不必进行频繁的簇头轮换和簇重组,以延长网络的生存时间;在“热区”以外的簇执行单簇头算法,簇头工作时,其它节点处于休眠状态,以节约能耗。 1 传感器网络模型 首先,需要利用GAF算法将整个无线传感器网络划分成若干个正方形虚拟单元格。各节点再根据以下定理判断自己是否在“热区”内。 定理:假定sink节点O的坐标为(0,0),“热区”为H(m,n),若任意传感节点p(x,y) 是相对sink节点O的坐标,sink节点与传感节点有相同的通信半径R,当且仅当下式同时成立,称传感节点p(x,y)在“热区”内。 m≥?x/R5√m≥?x/R5,n≥?y/R5√n≥?y/R5; 其中“/”为除法运算符,“「?”为向上取整运算符。 证明:为了方便讨论,作出以下假设: (1)所有传感器网络中的节点随机分布在以sink节点为原点的二维坐标系上,节点都知道自己的地理位置,即自己的坐标,并且所有节点的各项性能参数相同。 (2)网络具有稳定的拓扑结构,即传感器节点部署之后不再移动。 (3)sink节点的能量是无限的,网络中其它所有节点的能量是有限的。 (4)节点有状态切换功能,当节点空闲时可以进入休眠状态以节省能量。 假设网络区域划分的正方形虚拟单元格边长为r(见图1),为了保证相邻两个单元格中任意两个节点能够直接通信,需要满足关系: r2+(2r)2=R2?r≤R5√r2+(2r)2=R2?r≤R5 从而易证以上定理。将邻近sink节点一跳范围称为“一跳热区”。由于网络中所有的数据都要经过“一跳热区”转发给sink节点,所以该区域能量消耗速度最快,如果“一跳热区”内的传感节点能量耗尽,网络中的数据就无法发送给sink节点,那么网络的生命期就此结束。因此在网络初始运行时,m,n的值一般不会太大,当邻近“热区