文档介绍：WSN拓扑控制
—GAF算法
第13小组
第一页，共10页。
GAF算法
GAF(Geographical Adaptive Fidelity)算法是用地理位置为依据来进行分簇的算法。它将监测区域划分为虚拟单元格，将节点按照位置信息划归相应的单元格。在每个单元格中定期选举出一个簇头节点，若簇头节点保持激活状态，其他节点则进入睡眠状态。
GAF算法
名词解释
第二页，共10页。
GAF算法中，节点的状态标记为三种状态：睡眠、发现和激活。传感器网络的初始状态是：所有的节点都处于发现状态。处于发现状态下的节点之间交换Discover消息，获取同一个虚拟单元格内其他节点的信息。 Discover消息包括以下几个部分的信息：节点自身的ID、所在虚拟单元格的ID、节点状态、节点激活时间的估值等。
GAF算法
基本思路
第三页，共10页。
节点状态的转换如左图所示。只要是节点处于发现状态，都会对应一个发现状态计时器。如果节点处于发现状态的时间超过设定值Td，该节点就广播发送Discover消息，并转换到激活状态。在没有超过发现状态计时器的设定值Td之前，如果收到了另外的节点已经成为簇头节点的消息后，发现状态计时器将关闭，无线通信发射模块也关闭，节点进入睡眠状态。
GAF算法
基本思路
第四页，共10页。
当节点进入激活状态后，激活状态计时器启动计时，设置一个Ta，若激活状态的持续时间超过Ta，则转入发现状态。当节点处于睡眠状态后，启动一个睡眠状态计时器，设置一个时间参数Ts，一旦睡眠状态持续时间超过Ts，节点就转入发现状态。处于激活状态的节点在Ta超时之前，定时向外广播消息通告自己处于活动状态，以使其他节点中处于发现状态的节点不要进入激活状态。
GAF算法
基本思路
第五页，共10页。
GAF算法在执行中分为两个阶段：虚拟单元格的划分和虚拟单元格中簇头的选择。在虚拟单元格的划分阶段，依据WSN节点的位置信息和通信覆盖范围，将节点的部署区域划分为若干个虚拟单元格，划分中要保证相邻虚拟单元格中的所有节点都能够相互及直接通信。
GAF算法
基本思路
第六页，共10页。
对于WSN中的一个成员节点，已知整个监测区域的位置信息和自身的位置信息，就可以根据这些信息通过计算来确定自己处于哪一个虚拟单元格中。假设所有的节点通信半径是R，虚拟单元格是边长为r的正方形区域，要使相邻的两个虚拟单元格内任意两个节点之间能够直接通信，必须满足以下关系：
GAF算法
基本思路
第七页，共10页。