基于簇的骨干网构建与优化

分簇是以分层体系结构组织网络的骨干网中比较常用的一种。它可用来将网络节点划分为多个组（簇），在这些簇中，簇头负责支配其他节点。分簇提供了带宽的空间复用，众所周知，在无线传感器网络中，带宽是一种有限资源。同时，分簇提供了一种可实现高效路由的分层体系结构。现有的分簇方案通常由两个阶段构成：分簇建立和分簇维护。在第一阶段中，选出合适节点作为各簇的协调器（簇头）。簇头及其邻居节点形成一个簇。分簇建立后，由于存在节点移动性和节点失效的情况，因而需要通过分簇维护来重组各簇。

目前，存在着多种不同的簇结构。各个簇头可能是邻居，也可能不是邻居；其他节点可能一直与簇头建立连接，也可能不与簇头建立永久连接。例如，在参考文献（Heinzelman et al.，2000）提出的LEACH（Low Energy Adaptive Clustering Hier-archy，低功耗自适应集簇分层）协议中，节点随机决定是否成为簇头。决策中所用的参数是网络中预期簇头所占的百分比。决定担当簇头的传感器将其决定进行广播。每个节点以最高信号强度向簇头报告信息，这样簇就与簇头的Voronoi图相对应。簇头为其每个簇成员分配一个时隙，用于报告融合数据。簇头的选择周期性重复进行，以确保节点的能耗均衡。根据LEACH协议计算出的骨干网结构如图2-2所示。根据LEACH建立的簇结构效率不高，因为汇聚节点可能距离多个簇头都比较远。因此，直接报告会导致能耗极高，或者甚至不可能实现。同时，两个簇头可能互为邻居，且许多节点的直接邻居中不包含任何簇头。近年来发表的许多论文都对多跳报告或比LEACH协议更好的簇头决策方案进行了描述。特别需要指出的是，参考文献（Xia and Vlajic，2006）证实，只有那些能够在用于监测现象的异构簇中定位相应簇的分簇方案，才能保证降低节点的能耗，延长网络生命周期。该论文还提出了第一个以节点采集信息相似度作为簇形成主要标准的分簇算法。

图2-2 LEACH协议

一类分簇算法要求不存在两个互为直接邻居的簇头，且任何其他节点至少与一个簇头相邻。一个典型代表是由参考文献（Lin and Gerla，1997）提出的算法及其变形。该算法假定每个节点具有唯一的节点键值，且知晓其单跳邻居的键值。该簇头算法的基本思路是在选择每个簇的簇头时，将节点键值作为一种优先级指标。其工作原理如下：每个节点将其键值与邻居的键值进行对比。首先，所有节点都是未定的。如果一个未定节点在其未定邻居中具有最低键值，则该节点会生成自己的簇，广播决策信息及其键值，并将其键值作为簇键值。当收到来自于邻居宣布它是一个簇头的消息后，每个未定节点将声明自己是一个非簇头节点（从而变为确定节点），并通过发送一条消息通知其邻居。非簇头的声明信息将鼓励更多簇头形成簇。

(www.xing528.com)

图2-3 首轮中的簇头1、5、10、18和第二轮中的簇头3、15

在图2-3所示的实例中，节点的ID（Identifier，标识符）（编号从1到20）可用作节点键值进行自然排序（1＜2＜…＜20）。在首轮中，节点1、5、10、18在其邻居中具有最低键值，因而成为簇头。首轮中的簇头发送决策信息给其邻居，然后邻居节点宣称它们是非簇头节点，并通知其邻居。在第二轮中，由于节点3和15分别收到了来自于节点2和14的非簇头声明消息，它们生成自己的簇。因此，可以将节点划分为6个簇：{1，2}，{3，2，4，11}，{10，11，12，13，14}，{15，14，16，17}，{5，6，7，8，9，16}，{18，19，20}。任何接收到两个以上簇头声明信息的非簇头节点将宣布自己为网关节点，并属于所有对应簇（或者可以根据某些标准将该节点分配给某个簇）。在该实例中，节点2、6、11、14、16、20即为与簇头连接的网关节点。任意两个相邻簇头通常相距两跳或三跳。如果相邻簇头相距两跳（如路径1—2—3），则它们共用一个网关节点。相距三跳的两个簇头之间的某些路径，可能包含属于单个簇的节点。例如，路径18—20—6—5包含一个节点（如节点20）。这些节点也可以看做是网关节点，否则簇头和网关节点的网络可能处于非连通状态。

参考文献（Basagni，1999）提出了一种称为分布式移动自适应分簇（Distribu_- ted Mobility Adaptive Clustering，DMAC）的分布式分簇算法，该算法采用了一种与参考文献（Lin and Gerla，1997）提出的算法类似的簇构建机制。但是，在确定簇头时，它使用节点权重而不是节点标识符来作为键值。节点权重可以根据簇中剩余能量或节点容量来分配。在参考文献（Lin and Gerla，1997）提出的算法之后，开始使用这种权重而不是参考文献（Lin and Gerla，1997）中使用的最低原始标识符。基于DMAC算法，参考文献（Basagni et al.，2004）提出了一种称为S-DMAC的协议，该协议主要用于大型无线传感器网络的拓扑控制。该协议用于选择传感器节点子集来构建一个连通骨干网，并让所有其他节点切换到节能“休眠模式”。连通骨干网是由骨干节点和与骨干节点互连的网关节点，其中骨干节点是根据DMAC算法计算出来的簇头。S-DMAC通过限制使用“问候”消息，对骨干网建立和骨干网维护阶段邻居发现开销进行了优化。只有当引入比当前节点能量更高的批量新节点，或当骨干节点能量耗尽时，才需要对骨干网进行重组。仅当新骨干节点的剩余能量比原始节点能量高出预定阈值时，非骨干节点将加入新插入骨干节点。与GAF算法相比，S-DMAC提供了一种节点数量更少的连通骨干网。同时，它还减少了骨干网重组次数和交换的“问候”消息数量。

分簇是一种建立和维护阶段使用的准局部协议的典型实例（Simplot-Ryl et al.，2005）。它具有“联锁效应”：由一个边或节点失效/增加引起的简单变化，可能会通过信息传播来触发全局骨干网更新。通常，在牺牲簇结构质量的情况下，传播会受到抑制。另一个难点是通过网关节点将簇头接入到连通骨干网中。一般情况下，该过程要么需要使用太多网关，要么需要使用太多消息来减少使用网关数量。