3.4.4　基于地理位置的路由协议

1.GAF路由协议

GAF（Geographic Adaptive Fidelity，地理位置自适应保真），是一种基于地理位置的能量感知路由算法，最初的设计目的主要是在移动Ad-Hoc网络上应用，也适用于无线传感器网络。

GAF算法需要解决的问题包括：等价节点的确定、状态转移、对节点移动性的自适应、与现有路由协议结合等关键技术问题。

（1）等价节点的确定

在GAF路由算法中，网络区域首先被分为固定区域，并形成一个虚拟的网格。在每个区域中，传感器节点彼此协作并扮演不同的角色。例如，每个区域内的所有节点会选出一个传感器感应节点在每一段时间内保持活动状态，而其他节点都进入睡眠状态。被选中的节点代表该区域中的所有节点，负责监测和报告数据给基站，因此GAF路由算法是通过关掉网络中不必要的节点来节省能量，且不影响路由的保真度。其本质是，网络中的每个节点凭借GPS接收卡指示的位置信息将节点本身与虚拟网格中的某个节点关联映射起来。网络上与同一个点关联映射的节点对于分组路由的代价而言是等价的。为了节省能量，利用这种等价性可使某个特定网格的一些节点保持睡眠。这样，GAF路由算法随着网络节点数目的增加可以极大地提高网络的寿命。如图3-9所示，构造了三个虚拟网格A、B、C。根据虚拟网格的定义，节点1可以到达节点2、3、4中的任何一个，而节点2、3和4都可以到达5。因此节点2、3和4等价，其中任意两个可以关机。设虚拟网格为一个边长是r的正方形，无线通信的有效传播距离为R，则为了满足虚拟网格的定义，任意两个相邻网格中的两个相隔最远的节点间的距离不能超过R。网格B中的节点2和网格C中的节点5分别处于连接两个网格的对角线的两端，两者距离为最长。因此，可以得到r2+（2r）2≦R2，即。

（2）状态转移

GAF算法工作过程中GAF节点有三种状态：激活状态、休眠状态和发现状态。在GAF中，节点始终处于三种状态中的一种。图3-10给出了GAF的状态转换图，只有处于激活状态的节点才参与数据转发。

GAF算法中，每个网格只有一个定期选举产生的簇头节点处于工作状态，其他节点都进入休眠状态和发现状态。被选中的簇头节点代表该区域的所有节点，GAF算法就是通过关掉网络中不必要的节点来节省能量。GAF路由算法关键问题是如何分配节点，选出簇头。在发现目标时，簇头可要求该节点立刻转换为工作状态，并开始采集数据。然后，簇头把从簇内其他节点接收来的原始数据，进行检测和转发到汇聚节点，因此不会影响路由的保真度（Level of Routing Fidelity）。为了保持路由的保真度，激活节点会在离开网格之前唤醒其处于休眠状态的邻居节点，并让其中一个处于激活状态。

节点起始于发现状态，这时一个节点打开/收发信机并通过交换发现报文以发现相同网格内的其他节点。发现报文的内容包括节点ID、网格ID、估计的节点激活时间和节点的状态。

当节点进入发现状态时，为其设置一个长度为Td的定时器，定时器一旦到时，节点广播其发现报文，然后转入激活状态。定时器计时可以被其他节点的发现报文暂停。定时器的设置降低了发现报文相互冲突的可能性。

当节点进入激活状态时，为其设定另一个长度为Ta的定时器定义节点处于激活状态的时间。Ta时间到后，节点将返回发现状态。处于激活状态时，节点每隔Td时间重新广播其发现报文。

当处于发现或激活状态的节点找到处理路由的等价节点时，它自身会转入休眠状态。节点通过一种分级机制来决定哪个节点处理当前路由，处于激活状态的节点要比处于发现状态的节点的级别高。对于处于相同状态的节点，GAF规定拥有更长预期生存时间的节点有更高的级别。

当节点转入休眠状态时，就关闭收/发信机。处于休眠状态的节点在休眠一段时间Ts之后唤醒，同时重新转入发现状态。

Td、Ta、Ts都是由节点按照一定规则独自分布式确定。将Td设为一个均匀分布随机变量的取值，这样可以避免多个发现报文的冲突。这个随机变量取值范围受节点分级的影响，尽量使高级节点能够压制低级节点，促使它们尽快进入休眠。Ta可以设成节点的估计激活时间。节点休眠时间Ts可以设成处于0和当前激活节点的节点激活时间值之间的一个随机时间。

（3）对节点移动性的自适应

GAF尽量调节参与自组网路由的节点数，以使参与路由数据的节点数保持在一个相对稳定的水平。理想的情况是：在任何时间每一个网格中都有一个处于激活状态的节点。然而，随着节点的移动，处于激活状态的节点可能会移出其所在的网格。GAF通过使用预测并报告节点移动性的方式，解决节点移动带来的路由保真度被破坏的问题。具体而言，让每个节点预测其离开所在网格的时间并且将此信息写入发现信息中；当其他节点进入休眠状态时，它们休眠的时间长度取离开所在网格的时间和节点激活时间中较短的一个，这样就可以适应节点移动性的变化。这种修改没有改变节点的分级规则，但是节点的休眠时间可能变短了。

（4）与现有路由协议结合

准确地说，GAF本身不是一个路由协议，只是一个辅助路由协议节能的算法。因此，GAF要和现有的路由协议结合。

综上所述，GAF通过划分地理网格，让网格内尽量只有一个节点激活实现了节能的目的，而且一定程度上保证了网络的连续性。仿真表明GAF要比一个未改进的自组网网络协议节省40％～60％的能量。

2.GPSR协议

GPSR（Greedy Perimeter Stateless Routing，无状态贪婪周边路由）协议是一个典型的基于地理位置的路由协议。使用GPSR协议，网络节点都知道自身地理位置并被统一编址，各节点利用贪婪算法尽量沿直线转发数据。

使用贪婪转发模式时，当节点S需要向节点D转发数据分组时，它首先在自己的所有邻居节点中选择一个距节点D最近的节点作为数据分组的下一跳，然后将数据传送给它，中继转发节点也使用贪婪转发模式来确定下一跳节点。该过程一直重复，直到数据分组到达目的节点D。贪婪转发模式选择下一跳节点的情况如图3-11所示。

源节点与目的节点的距离小于源节点的邻居节点与目的节点距离时，使用贪婪转发模式会产生路由空洞现象，导致数据无法传输。如图3-12所示，SD的距离比XD和YD近，但D不在S的通信范围内，导致S无法转发数据，出现路由空洞。当出现这种情况时，空洞周围的节点能够探测到并利用右手法则沿空洞周围传输来解决此问题。

GPSR协议采用局部最优的贪婪算法，不需要维护网络拓扑，路由开销小，只依赖直接邻居节点进行路由选择，几乎是一个无状态的协议；且使用接近于最短欧氏距离的路由，数据传输时延小，并能保证只要网络连通性不被破坏，一定能够发现可达路由。但其不足也显而易见，当网络中的汇聚节点和源节点分别集中在两个区域时，由于通信量不平衡易导致部分节点失效，从而破坏网络连通性。另外，GPRS需要借助GPS定位系统或其他定位方法协助计算节点位置信息，从而使成本增加。

3.GEAR路由协议

在数据查询类应用中，汇聚节点需要将查询命令发送到事件区域内的所有节点。采用洪泛式将查询命令传播到整个网络，建立汇聚节点到事件区域的传播路径，这种路由建立过程的开销很大。地理位置和能量感知路由（Geographical and Energy Aware Routing，GERA）根据事件区域的地理位置信息，建立了从汇聚节点到事件区域的优化路径，避免了洪泛传播方式，从而减少路由建立的开销。GEAR路由假设已知事件区域的位置信息，每个节点都知道剩余能量信息和自己的位置信息，并通过一个简单的Hello消息交换机制知道所有邻居节点的剩余能量信息和位置信息。

GEAR路由协议的查询信息传播包括两个阶段：第一个阶段是查询消息传送到事件区域，即汇聚节点发出查询命令，并根据事件区域的地理位置将查询命令传送到区域内距离汇聚节点最近的节点，然后从该节点将查询命令传播到区域内的其他所有节点。第二个阶段是查询消息在事件区域内的传播，采集的数据沿着查询消息的反向路径向汇聚节点传播。

（1）查询消息传送到事件目标区域

GEAR路由协议用两种代价来表示路径代价：估计代价和实际代价。当没有建立从汇聚节点到事件区域的路径时，中间节点采用估计代价来决定下一跳节点。估计代价定义为归一化的节点到事件区域的距离以及节点的剩余能量两部分，节点到事件区域的距离用节点到事件区域几何中心的距离来表示。由于所有节点都知道自己的位置和事件区域的位置，因而所有节点都能计算出自己到事件区域几何中心的距离。

节点计算自己到事件区域估计代价的公式如式（3-2）所示：

c（N，R）=ad（N，R）+（1-a）e（N）　　（3-2）

式中，c（N，R）为节点N到事件区域R的估计代价；d（N，R）为节点N到事件区域R的距离；e（N）为节点N的剩余能量；a为比例参数。注意式中的d（N，R）和e（N）都是归一化后的参数值。

查询消息到达事件区域后，事件区域的节点沿查询路径的反方向传输监测数据，数据信息中“捎带”每跳节点到事件区域的实际能量消耗值。对于数据传输经过的每个节点，首先记录捎带信息中的能量代价，然后将信息中的能量代价加上它发送该消息到下一跳节点的能量消耗，替代信息中的“捎带”值来转发数据。

（2）查询消息在事件区域内传播

当查询命令传送到事件区域后，可以通过洪泛方式传播到事件区域内的所有节点。但当节点密度大时，洪泛方式开销比较大，这时可以采用迭代地理转发策略。

如图3-2所示，事件区域内首先收到查询命令的节点将事件区域分为若干子区域，并向所有子区域的中心位置转发查询命令。在每个子区域中，最靠近区域中心的节点（如图3-13中节点C）接受查询命令，并将自己所在的子区域再划分为若干子区域并向各个子区域中心转发查询命令。该消息传播过程是一个迭代过程，当节点发现自己是某个子区域内唯一的节点，或者某个子区域没有节点存在时，停止向这个子区域发送查询命令。当所有子区域转发过程全部结束时，整个迭代过程终止。

迭代地理转发机制和洪泛机制各有利弊。当事件区域内节点比较多时，迭代地理转发消息的转发次数少，而节点比较少时使用洪泛策略的路由效率高。GEAR路由可以使用如下方法在两种机制中做出选择：当查询命令到达区域内的第一个节点时候，如果该节点的邻居数量大于一个预设的阈值，则使用迭代地理转发机制，否则使用洪泛机制。

GEAR路由通过定义估计路由代价为节点到事件区域的距离和节点剩余能量，并利用捎带机制获取实际路由代价，进行数据传输的路径优化，从而形成能量高效的数据传输路径。GEAR路由采用的贪婪算法是一个局部最优的算法，适合无线传感器网络中节点只知道局部拓扑信息的情况，其缺点是由于缺乏足够的拓扑信息，路由过程中可能遇到路由空洞，反而降低了路由效率。如果节点拥有的相邻两跳节点的地理位置信息，可以大大减少路由空洞的产生。GEAR路由中假设节点的地理位置固定或变化不频繁，适用于节点的移动性不强的应用环境。