分簇机制在计算机网络中的应用

分簇机制在计算机网络中的应用

0分簇机制原理在实际应用中，无线传感器网络（无线传感器网络）中的大量节点通常能量有限，并且往往无法重复使用。因此如何合理利用有限能量来延长网络寿命是路由协议设计面临的首要问题。分簇被证明是节省能耗和提高网络寿命的一种基本机制。所谓分簇,就是将节点划分成许多称之为簇的组,每个簇都有一个簇头和许多簇成员。成员将收集到的数据发送给簇头,簇头对数据进行融合后直接或者通过其他簇头发送到基站。通过分析现有WSNs分簇协议,揭示了分簇算法的本质,并基于分簇算法本身和分簇技术的应用两方面对这些协议进行了分类和介绍,最后引导了下一步的研究方向。1网络拓扑的优势分簇的目标往往根据具体的应用而设定,例如文献中将分簇目标总结为负载均衡、增加连通度、最小化簇数目以及最大化网络寿命等。对于大规模WSNs而言,分簇网络拓扑在拓扑管理、可扩展性和能量效率等方面都具有明显优势。1)分簇可将网络分为多个小规模的网络,从而可降低拓扑管理的难度。2)较好的可扩展性使分簇更适用于大规模WSN应用场景。3)簇内引入节点睡眠机制,簇头保持唤醒状态,成员按调度向簇头发送信息,既不影响网络连通性又能节省能量。4)簇头对数据进行融合,降低了数据冗余,减少了数据通信量。5)只有簇头参与路由大大减少了路由表尺寸,降低了通信开销和内存开销。2节点分簇算法近年来分簇算法取得了大量优秀的研究成果。按不同方面可将现有分簇算法进行如下分类。1)根据算法的执行方式可分为集中式分簇和分布式分簇。集中式分簇算法需要掌握网络全局信息,因此可获得好的簇头分布但在大规模网络中的应用有限。分布式分簇算法中节点根据局部信息独立分簇,开销小,更适合大型网络。LEACH是最为经典的按轮执行的分布式分簇协议,每轮由簇的建立和数据传输两阶段组成。在前一阶段,节点生成一个之间的随机数,若此数小于阈值T(n)则成为簇头。在后一阶段,成员将数据发送给簇头,簇头对数据进行融合后直接发送至基站。簇头角色全网内周期性轮转。该协议结构简单且不需要较大通信开销,然而它在簇头选举时未考虑节点剩余能量。学者们针对其提出了一些改进协议,如在簇头竞选时文献同时考虑了节点剩余能量和距基站距离的。文献同时考虑了节点位置和剩余能量。2)根据分簇的层数不同可分为单层分簇和多层分簇。单层分簇将网络分为两层,簇头为高层,成员为低层,所有节点由一层簇头和归属于这些簇头的成员组成,算法实现简单,开销较小。多层分簇中低层簇头通常作为高层簇头的成员,因此可进一步降低节点能耗,但实施复杂且开销较大。文献采用自顶向下的方式构造多层分簇拓扑。在簇的建立阶段节点以1p(u)的概率成为第一层簇头,其他节点成为第一层簇成员。第一层簇头通知其成员进行第二层簇头选举,第一层成员以2p(u)的概率成为第二层簇头,剩余节点成为第二层簇成员,依次进行直到簇内节点数小于等于3时停止。数据传输阶段,T层成员将数据发送到T层簇头,T层簇头对数据进行融合后发送至T-1层簇头,依此类推,最后由第一层簇头将数据进行融合后发送给基站。3)根据簇头轮转特点可分为时间驱动型分簇算法和能量驱动型分簇算法。前者指簇头按照一定时间周期在全网内轮转。后者指当簇头能量低于预设能量阈值时在局部轮转。文献中簇头依据节点剩余能量在簇内选择备份簇头,在簇头能量达到阈值或簇头意外失效的情况下,备份簇头迅速代替原簇头成为新簇头,并接管大部分原簇成员,无法接入新簇头的节点选择加入邻居簇,从而在局部完成拓扑重建工作。4)根据簇头选举参数可分为以节点ID、节点度、节点剩余能量和节点相对剩余能量等为簇头竞选参数的分簇算法。文献以节点相对剩余能量为簇头竞争参数。在簇的建立阶段每个节点vj广播包含自身ID和剩余能量的E_Msg消息,同时也收到所有邻居的E_Msg消息。vj基于此计算自己的相对剩余能量和发送簇头消息的时刻t,若节点在t之前没有收到邻居的簇头消息,则广播簇头消息成为簇头,否则退出簇头竞争。5)根据簇的大小规模可分为均匀分簇算法和非均匀分簇算法。均匀分簇算法中簇的大小是均匀的。非均匀分簇算法则通过控制簇的大小来均衡簇头间能耗。文献中的算法是典型的分布式非均匀分簇算法,每轮开始节点si以T的概率成为候选簇头,每个候选簇头si根据自身到基站的距离计算它的竞争半径Rc。并以Rc为半径广播一条包含自身ID和剩余能量的簇头竞选消息。同时si根据收到的来自其邻居的簇头竞选消息定期更新自己的簇头邻居集合si.SCH。如果si的剩余能量大于si.SCH中所有节点的剩余能量就广播一条簇头消息宣布成为簇头。3分簇控制及融合技术近年来对基于分簇技术设计的算法也取得了不少研究成果。考虑不同的应用对这类算法进行如下分类。1)安全分簇。文献提出了基于秘密共享的CA证书方案和自组织证书方案。文献中则提出一种基于簇的平面Merkle哈希树的Sybil攻击防御机制。2)覆盖度。通常算法是先采用分簇的方式将覆盖区域划分成许多子区域,然后进行细粒度的网络监测与覆盖控制。文献中利用最大熵原理对整个网络进行预分簇得到临时簇头,在保证网络覆盖度的前提下获取各分簇内活跃节点的连通支配集。3)连通度。基于连通度约束的分簇算法可以保证簇头等骨干节点之间的连通性。文献是利用分簇技术对网络进行划分后在保证网络连通度的前提下,找出可以达到最大覆盖度的最少活动节点数。4)移动模型。针对网络中由少数节点移动的情况,文献提出一种基于权值的分布式分簇算法,文献提出了一个适用于同时包含固定和移动传感器节点的WSN的移动簇头通信协议。5)数据收集。分析对以分簇为基础的收集融合算法可以减少网络中的数据传输总量,文献算法提出了一种在分簇路由协议支持下的时间、空间多维度的数据压缩算法。文献设计出一种基于分簇结构的混合型数据收集协议。6)能量补给。已有的分簇路由协议大都是基于节点能量受限设计的,但现有的一些采能技术已经可以为节点提供适量的能量补给。文献中提出的具有能量补给的分簇路由算法综合考虑了节点的能量起伏变化以及能量补给水平,修正了现有簇头选择机制和非簇头归属机制。4网络模型和能量模型仍面临一定的问题通过对现有的大量研究成果进行分类总结。归纳了今后对WSNs研究需关注的几方面问题。1)如何在网络中出现死亡节点的情况下,仍能保持连通性,使全网能正常运行,是一个有待解决的