4.4.3　基于地理位置信息的路由协议

在前面介绍的无线传感器网络路由协议中，节点根据自己的逻辑地址，通过相邻节点之间的通信探测到所有网络节点之间的路由，这种方式相对来说比较简单。随着现代技术的发展，节点的定位技术已经实现，节点能够很容易地知道自己所处的位置，利用这些位置数据，节点可以确定自己的路由协议，提高网络的性能。

同时，在很多应用中，无线传感器节点需要精确地知道自己所处的位置，例如，在森林防火的时候，消防人员可通过无线传感器节点精确地知道火灾发生的位置。基于地理位置的路由协议假设节点已经知道了自身的地理位置信息和自己所要传送数据的目的节点所在的位置，从而利用这些已知的地理位置信息来选择自己的路由策略，高效地将数据从远端发送到指定目标区域，减小路由选择过程中所需要的时间和成本代价。

基于地理位置的路由协议一般分为两类，一类是使用地理位置协助改进其余路由算法，以约束网络中路由搜索的区域，减少网络不必要的开销，主要代表协议为GAF路由算法；另一类路由协议直接利用地理位置来实现自己的路由策略，代表协议是GEAR路由协议。

1. GEAR路由协议

GEAR路由协议是一种典型的基于地理位置来实现自己路由策略的协议，它结合了定向扩散路由算法的思想，在路径选择时甚至加入了能量的因素。

1）基本思想

GEAR路由协议根据事件所在区域的地理信息，实现从Sink节点到事件所在地区节点的路径，这样就能实现Sink节点向某个特定区域发送数据，避免了泛洪似的全网广播数据，同时借鉴了SPIN中查询节点剩余能量值的方法，建立从Sink节点到目标区域的最优路径。

GEAR路由协议通过周期性地泛洪广播一个Hello消息来通知相邻节点自己所在的位置和自己的能量消耗情况，保证链路的对称。

2）关键技术

GEAR路由协议在已知事件所在位置信息的情况下，每个节点都知道自己的位置信息和剩余能量值，在自己的缓存中也保存了所有相邻节点所在的位置信息和剩余能量值。GEAR路由协议要求每个节点维护一个预估路径代价和一个通过相邻节点到达目的节点的实际路径代价。预估代价要使用节点的剩余能量值和发送节点到目的节点的距离来进行计算，而实际代价则是对网络中围绕在洞（Hole）周围的路由所需预估代价的改进。所谓“洞”是指某个节点的周围没有任何相邻节点比它到事件区域的路径所耗费的路径代价更大。如果洞现象不发生，那么实际代价将会与预估代价一致。当数据包成功到达目标区域之后，该节点的实际代价就要传播到上一跳节点，用来调整下一次发送时路由的优化。GEAR路由协议需要解决两个关键性的技术问题：向目标区域传送查询消息和查询消息在事件区域内的传播。

（1）向目标区域传送查询消息。从Sink节点到事件区域传送数据采用的是贪婪算法。节点在自己所有的相邻节点中选择到事件区域内代价最小的节点，以此节点作为自己的下一跳节点，并将自己的路径代价设置为自己到该节点路径的代价与该节点到目标区域的代价之和。如上所述，如果出现空“洞”现象，如图4.6所示，节点C是节点S的相邻节点中到达目的节点T代价最小的节点，节点G、H、I已经失效，不能够作为节点C的下一跳节点，因此节点C再也找不到比它距离目标区域节点T代价小的节点，即出现了路由空洞。GEAR路由协议采用的方法是：节点C选取相邻点中代价最小的节点B作为下一跳节点，并将自己的代价值设置为节点C到节点B的一跳代价值和节点B的代价值之和，同时将这个新代价值通知给节点S。当节点S需要再次转发查询命令到节点T时，它就会根据这次的预估代价和实际代价来综合比较，选择直接通过节点B来转发查询消息，而不是节点C。

（2）查询消息在事件区域内的传播。当事件区域接收到查询消息后，如果采用泛洪的方式将此查询消息传送给事件区域内的所有节点，则所需要的代价比较大，尤其在节点密度比较大、规模较为庞大时。GEAR路由协议针对这种情况提出了一种区域内迭代地理转发的算法，如图4.7所示。我们假设事件所在区域是一个矩形，该区域收到查询消息后将该区域划分为若干个子区域，图4.7中为4个，并向每一个区域中心转发此查询消息，在子区域中每个最靠近区域中心的节点接收该查询消息后，采用同样的方法将自己的子区域再划分为若干个子区域，这样就形成了一级一级的迭代过程，直到节点发现该子区域内除了自己再也没有其余的节点时，该查询消息停止转发。当所有区域内转发过程全部停止时，整个迭代过程完成。

GEAR路由协议通过维护预估代价和实际代价，优化了数据传输的路径，采用贪婪算法均衡网络负载，提高了网络能效。贪婪算法虽然可以算是局部最优算法，但却会产生路由空洞。GEAR路由协议采用了一种新方法—局部优化算法解决了这个问题，终端节点由于缺乏足够的拓扑信息，所以只适用于节点移动性不强的应用中，对移动节点网络的应用还需要进一步提高。

2. GAF路由算法

GAF（Geographical Adaptive Fidelity）路由算法是一类使用地理位置信息来辅助路由选择的算法，在该算法中，地理位置不但可以帮助优化路由，还可以用来选择等价节点。

1）基本思想

一般情况下，节点在发送和接收数据的过程中最为消耗能量，节点在空闲时也需要消耗能量，根据最新的测量结果，节点在空闲、接收数据和发送数据时消耗的能量之比为1：1.2：1.7，节点只要处于启动状态就一定要消耗能量，GAF路由算法在地理位置信息的帮助下，关闭一定量的节点，以此来节省能量，提高网络的性能。

GAF路由算法考虑到无线传感器网络中节点的冗余性，在保证网络正常流通的情况下，适当关闭一些节点可降低能量消耗，延长节点的生存时间，从而延长网络的生命周期。GAF路由算法利用节点的位置信息，组成一个虚拟的网格，网格中的节点对于数据的转发来说是等价的，无论选择哪个节点，所耗费的时间和能量也大致相同，因此这些节点可以通过协商轮流地工作，不工作的节点就被关闭，同时确定好激活的时间，通过周期性轮换，就能够提高节点的能效。

2）主要问题

在GAF路由算法中，节点的关闭需要考虑以下几个问题：确定等价节点、轮换协商算法，以及移动节点的自适应算法。

（1）确定等价节点。等价节点，通俗来讲就是一个节点可以代替另外一个节点，同时两者消耗的能量和耗费的代价也大致相同。因此，只要能够完成数据的转发功能，使用等价节点中的任何一个节点对网络性能都不会产生明显的影响，并且等价节点与源节点和目标节点无关。为了达到这个目的，在GAF路由算法中，协议将整个区域分成若干个虚拟网格，虚拟网格中的任意一个节点都可以与相邻网格内的节点进行通信，因此对于每个网格中的节点来说，都可以实现路由的连通，这些节点可以说是等价节点。

如图4.8所示，有三个虚拟网格A、B、C，假设每个虚拟网格都为正方形，边长为r，根据虚拟网格的要求，节点1和节点5可以和节点2、3、4中任意一个节点通信，因此节点2、3、4是等价节点，任意一个节点都可以实现路由的连通。在这种情况下，节点5需要跟中间区域中的任意一个节点进行通信，就必须保证节点5能和节点2进行通信，因为两个节点距离最远，可以看成两个网格的对角线距离，假设节点的通信最远距离为R，则要求。

（2）轮换协商算法。在GAF路由协议中，节点有三种状态：发现状态、激活状态和睡眠状态，图4.9为GAF路由算法中节点状态转换图，只有处于激活状态的节点才能够正常进行数据的通信。

在初始化时，节点处于发现状态，在这个状态下，节点打开收发信机，通过交换发现报文来发现相同网格内的其他节点。发现报文的内容包括节点的ID、网格ID、节点的预估激活时间和节点的状态信息。节点利用自己的位置信息和网格的大小来确定网格的ID。

当节点进入发现状态时，设定了一个长度为TD的定时器，这个定时器就是节点距离激活剩余的时间，当定时器溢出时，节点进入激活状态，广播发送自己已经发现的数据。定时器定时期间，如果有需要，其余节点发现的报文可以令定时器暂停，延长节点发现状态的时间。为了避免多个发现报文发生冲突，TD会选择一个随机量，服从[0，常数]之间均匀分布。当一个节点发送了发现报文后，其余的等价节点将会进入睡眠状态，只有发送发现报文的节点被激活，进入激活状态。节点进入激活状态之后，节点会设定一个时间为TA的定时器，定义节点此次将要激活的时间，定时器时间到达后，节点将返回发现状态。当处于激活状态时，节点每隔TA时间重新广播它的发现报文。

根据这种机制，整个网格内只有一个节点处于激活状态，网格内的数据转发功能就由此节点来完成。对于处于发现状态的节点，节点通过接收其余节点的发送报文来感知是否有比自己拥有更长生命周期的节点，即剩余能量值比自身大的节点，如果有，则此节点转入睡眠状态，发现状态中生命周期最长的节点就被预计作为下一个激活的节点。当节点进入睡眠状态时，关闭收发信机，通过设置一个定时器在TS时间后自动唤醒节点，进入发现状态。节点的睡眠时间也是采用节点激活时间内均匀分布的一个随机数。一般情况下，节点的激活时间要比自己的生命周期短得多，以此来多次进行激活完成工作。

（3）移动节点的自适应算法。根据以上协议的规定，GAF路由算法最理想的情况就是每个网格内只有一个处于激活状态的节点，尽量少的节点处于发现状态。但是对于移动无线传感器网络来说，有些节点可能移动，尤其是对于网格内的激活节点来说，如果激活节点移出网格，那么该网格内的通信路由将被中断，从而降低路由的可靠性，同时丢包率也会升高。因此，GAF路由算法要能够调节网格内处于激活状态的节点数，使参与路由的节点数保持在一个相对平衡的状态。

对于节点移动的情况，GAF路由算法通过预测和报告节点规律的方法，来解决节点移动带来的网格内的路由中断问题。GAF路由算法让每个节点预测其可能离开网格的时间，并且将此信息加入发现信息中，发送给其余节点。当其余节点进入睡眠状态后，其睡眠时间会考虑到激活节点的离开时间，使睡眠时间小于节点的离开时间，当此激活节点还未离开时就会有节点处于发现状态，及时解决激活节点离开所带来的激活节点缺失的情况。当然这种修改在一定程度上缩短了节点的睡眠时间，这对于静态的无线传感器网络节点的应用来说是没有必要的。

严格来说，GAF路由算法不属于路由协议，因为它没有确定整个网络内的路由，只是针对局部路由进行的一种节省能量的技术，但是这种算法在节点分布比较密集的区域中能够取得很好的效果，可以说是一种辅助型的路由算法。GAF路由算法通过对网络进行地理划分，让网格内只有一个节点处于激活状态，来完成网格区域内数据的转发，节省能量，GAF路由算法的这种思想可以用在许多路由算法中。GAF路由算法还需进一步改进，最好能够找到一种不需要或者需要比较少的地理位置信息就能够实现网络内等价节点互换的办法，这些办法最好能够与具体的路由情况无关，与MAC层独立存在，同时希望增加的时延尽可能小，能效更高。