地理位置路由协议简介

在传感器网络中，结点通常需要获取它的位置信息，这样它采集的数据才有意义。如在森林防火的应用中，消防人员不仅要知道森林中发生火灾事件，而且还要知道火灾的具体位置。地理位置路由协议假设结点知道自己的地理位置信息以及目的结点或者目的区域的地理位置，利用这些地理位置信息作为路由选择的依据，结点按照一定策略转发数据到目的结点。地理位置的精确度和代价相关，在不同的应用中会选择不同精确度的位置信息来实现数据的路由转发。

1）GEAR路由协议

在数据查询类应用中，汇聚结点需要将查询命令发送到事件区域内的所有结点。采用洪泛方式将查询命令传播到整个网络，建立汇聚结点到事件区域的传播路径，这种路由建立过程的开销很大。GEAR（Geographical and Energy Aware Routing）路由协议根据事件区域的地理位置信息，建立汇聚结点到事件区域的优化路径，避免了洪泛传播方式，从而减少了路由建立的开销。

GEAR路由协议假设已知事件区域的位置信息，每个结点知道自己的位置信息和剩余能量信息，并通过一个简单的Hello消息交换机制知道所有邻居结点的位置信息和剩余能量信息。在GEAR路由协议中，结点间的无线链路是对称的。

GEAR路由协议中查询消息的传播包括两个阶段。首先汇聚结点发出查询命令，并根据事件区域的地理位置将查询命令传送到区域内距汇聚结点最近的结点，然后从该结点将查询命令传播到区域内的其他所有结点。监测数据沿查询消息的反向路径向汇聚结点传送。

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

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

结点计算自己到事件区域的估计代价的公式如下：

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

查询信息到达事件区域后，事件区域的结点沿查询路径的反方向传输监测数据，数据消息中“捎带”每跳结点到事件区域的实际能量消耗值。对于数据传输经过的每个结点，首先记录捎带信息中的能量代价，然后将消息中的能量代价加上它发送该消息到下一跳结点的能量消耗，替代消息中的原有“捎带”值来转发数据，下一次转发查询消息时，用刚才记录的到事件区域的实际距离d（N，R）来计算它到汇聚结点的实际代价。结点调用消息区域的优化路径。

从汇聚结点开始的路径建立过程采用贪婪算法，结点在邻居结点中选择到事件区域代价最小的结点作为下一跳结点，并将自己的路由代价设为该下一跳结点的路由代价加上到该结点一跳通信的代价。如果结点的所有邻居结点到事件区域的路由代价都比自己的大，则陷入了路由空洞（Routing Void）。如图3－18所示，结点C是结点S的邻居结点中到目的结点T代价最小的结点，但结点G、H、I为失效结点，结点C的所有邻居结点到结点T的代价都比结点C大。可采用如下方式解决路由空洞问题：结点C选取邻居中代价最小的结点B作为下一跳结点，并将自己的代价值设为B的代价加上结点C到结点B一跳通信的代价，同时将这个新代价值通知结点S。当结点S再转发查询命令到结点T时就会选择结点B而不是结点C作为下一跳结点。

图3－18　贪婪算法的路由空洞

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

当查询命令传送到事件区域后，可以通过洪泛方式传播到事件区域内的所有结点。但当结点密度比较大时，洪泛方式的开销比较大，这时可以采用迭代地理转发方式。如图3－19所示，事件区域内首先收到查询命令的结点将事件区域分为若干子区域，并向所有子区域的中心位置转发查询命令。在每个子区域中，最靠近区域中心的结点（如图3－19中结点N）接收查询命令，并将自己所在的子区域再划分为若干子区域并向各个子区域中心转发查询命令。该消息传播过程是一个迭代过程，当结点发现自己是某个子区域内唯一的结点或者某个子区域没有结点存在时，停止向这个子区域发送查询命令。当所有子区域转发过程全部结束时，整个迭代过程终止。

图3－19　区域内的迭代地理转发

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

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

2）GEM路由协议

传感器网络有三种存储监测数据的主要方式，分别是本地存储（Local Storage）、外部存储（External Storage）和数据中心存储（Data－centric Storage）。在本地存储方式中，结点首先将监测数据保存在本地存储器中，并在收到查询命令后将相关数据发送给汇聚结点。在外部存储方式中，结点在获得监测数据后，不论汇聚结点目前是否对该数据感兴趣，都主动地把数据发送给汇聚结点。在数据中心存储方式中，首先对可能的监测事件进行命名，然后按照一定的策略将每一个事件映射到一个地理位置上，距离这个位置最近的结点作为该事件的负责结点，结点在监测到事件后把相关数据发送到映射位置，负责结点接收数据，进行数据融合并存储在本地。

本地存储方式中，网络传输的数据都是汇聚结点感兴趣的数据，网络传输效率高，但是需要每个结点都具有相对较大的存储空间，数据融合只能在传输过程中进行，并且汇聚结点需要经过较长的延迟后才能获得查询数据。外部存储方式中，结点将采集数据及时传输给汇聚结点，可以提高传感器网络对突发事件的反应速度，但是监测数据不断发送给汇聚结点，一方面由于有些数据不是汇聚结点感兴趣的，造成了网络能量的浪费；另一方面容易使得汇聚结点附近形成网络热点，降低传感器网络的吞吐率。数据中心存储方式在网络中选择不同的负责结点实现不同事件监测数据的融合和存储，是介于本地存储和外部存储之间的一种方式，在查询延迟、能量消耗和存储空间等多项指标间进行折中。由于传感器网络处理的事件往往有多种，数据中心存储方式能够将网络通信流量、处理流量和存储流量在网络中均匀分摊，从而有效避免了网络热点的产生。

GEM（Graph Embedding）路由协议是一种适用于数据中心存储方式的地理路由协议。GEM路由协议的基本思想是建立一个虚拟极坐标系统（Virtual Polar Coordinate System，VPCS），用来表示实际的网络拓扑结构。网络中的结点形成一个以汇聚结点为根的带环树（ringed tree），每个结点用到树根的跳数距离和角度范围来表示，结点间的数据路由通过这个带环树实现。

（1）虚拟极坐标系统

虚拟极坐标系统的建立过程主要包括以下步骤：

第一步：生成树形结构。

汇聚结点设置自己的跳数距离为0并广播路由建立消息。该消息包含一个到汇聚结点跳数的域。与汇聚结点相邻的结点收到这个消息后，将汇聚结点作为自己的父结点，并设置自己到汇聚结点的跳数为1，然后继续广播路由建立消息。汇聚结点需要监听邻居结点的广播，并将发送跳数为1的路由建立消息的结点标记为子结点。这个过程一直扩展到整个网络，使得每个结点都知道自己的父结点和子结点以及到汇聚结点的跳数，直到所有结点加入这个树型结构为止。如果一个结点同时收到多个广播消息，则选择信号更强的结点作为父结点。结点广播路由建立消息后，如果没有收到跳数比自己更大的路由建立消息，则认为自己是叶结点。

第二步：反馈子树大小。

子树大小是指子树中包含的结点数目。在树形结构形成以后，从叶结点开始，结点将自己为根结点的子树的大小报告给它的父结点。叶结点向父结点报告的子树大小为1；中间结点将自己所有子树的大小相加，并加上1得到自己的子树大小，然后报告给它的父结点。这个过程从叶结点开始一直向汇聚结点进行，直到汇聚结点获得整棵树的大小。

第三步：确定虚拟角度范围。

汇聚结点首先决定整个虚拟极坐标系统的角度范围，例如［0，90］。这个角度只是一个逻辑角度，并不表示结点的实际方位。汇聚结点将角度范围分配给每个子结点，每个子结点得到的角度范围正比于以该结点为根的子树大小。每个子结点按照同样的方式将自己的角度范围分配给它的子结点。这个过程一直持续进行，直到每个叶结点都分配到一个角度范围。

经过上述步骤之后，每个结点都知道自己到汇聚结点的跳数和自己的逻辑角度范围，这样就可以用［跳数，角度范围］唯一表示每个结点。从图3－20（a）中可以看到，在按照上述步骤构造的树形结构中，跳数相同的结点角度范围可能是无序的。为此，结点可以根据一个统一规则（例如顺时针规则）为子结点设定角度范围，使得同一级结点的角度范围顺序递增或者递减。这样，到汇聚结点跳数相同的结点就形成了一个环形结构，如图3－20（b）所示。

图3－20　传感器网络虚拟角度原理图

（2）基于虚拟极坐标系统的路由算法

结点在发送消息时，如果目的位置的角度不在自己的角度范围内，就将消息传送给父结点，父结点按照同样的规则处理，直到该消息到达角度范围包含目的位置角度的某个结点，这个结点就是源结点和目的结点的共同祖先。消息再从这个结点向下传送，直到到达目标结点，如图3－21（a）所示。

上述算法需要上层结点转发消息，开销比较大。一个改进算法是：结点在向上传送消息之前首先检查邻居结点是否包含目标位置的角度。如果包含，则直接传送给该邻居结点而不再向上传送，如图3－21（b）所示。(www.xing528.com)

进一步的改进算法利用了上一节提到的环形结构，称作虚拟极坐标系路由算法（Virtual Polar Coordinate Routing，VPCR）。结点检查相邻结点的角度范围是否离目标位置更近，如果更近，就将消息传送给这个邻居结点，否则才向上层传送，如图3－21（c）所示。

图3－21　VPCR路由算法

（3）对网络拓扑变化的适应

由于路由算法建立在虚拟极坐标系统上，而虚拟极坐标系统是一个逻辑拓扑，所以当实际网络拓扑发生变化时，需要及时局部更新虚拟极坐标系统。虚拟极坐标系统的局部更新应满足下述一致性条件：

①除了汇聚结点外每个结点只有一个父结点；

②每个结点的跳数值为父结点的跳数值加1；

③每个结点的角度范围是父结点的角度范围的子集；

④每个结点的子结点的角度范围不相交。

一致性条件能够保证改变后的虚拟极坐标系统仍然是一个树形结构，不存在结点间的环路。

网络拓扑的变化主要包括结点失效和新结点加入两种情况。对结点失效的处理：当结点P失效时，P的所有子树包含的结点都成为孤儿结点。假设P的某个子结点Q可以连接到另一个非孤儿结点P1，则Q将P1作为父结点。为满足一致性条件，需要作一些属性调整：首先，Q的距离为P1的距离值加1，Q的子树都要作出相应的变化；其次，P1以及P1到汇聚结点路径上的所有结点需要将Q的角度范围加入自己的角度范围；然后，失效结点P的父结点需要将Q的角度范围从自己的角度范围内减去，这种改变同样要向上层结点传送，直到到达P和P1的共同祖先。若P的子结点Q不能连接到任何非孤儿结点，但是Q的子树上有结点C1可以连接到非孤儿结点P1，这时子树的结构要逆转过来，Q成为C1的子结点。C1作为子树的根结点继承Q的角度范围并进行角度范围的重新赋值，并按照上述的方法连接到P1上。

对结点增加的处理：假设结点C要加入树结构，并可以连接到结点P，P成为C的父结点并为C赋予跳数和角度范围值。跳数是P的距离值加1，角度范围可以有两种解决方法。一是在生成树形结构时预留一些角度范围，这时可以用来满足新结点；二是向上层结点申请更多的角度范围。这个过程可能一直持续到汇聚结点。

GEM路由协议根据结点的地理位置信息，将网络的实际拓扑结构转化为用虚拟极坐标系统表示的逻辑结构，即一个以汇聚结点为根结点的带环树结构，并在这个带环树上实现结点间的数据路由。GEM路由协议为数据中心存储的传感器网络提供了一种路由机制，它不依赖于结点精确的位置信息，采用虚拟极坐标的方法能够简单地将网络实际拓扑信息映射到一个易于进行路由处理的逻辑拓扑中，而且不改变结点间的相对位置。但是，由于采用了带环树结构，实际网络拓扑发生变化时，树的调整比较复杂，因此GEM路由协议适用于拓扑结构相对稳定的传感器网络。

3）边界定位的地理路由协议

在传感器网络的实际应用中，如果每个结点都需要知道自己的精确位置信息，那么路由代价比较大。地理位置路由研究中的一个重要方向就是如何在保证路由正确性的前提下，尽量减少需要精确位置信息的结点数目，以及路由机制对结点精确位置信息的依赖。参考文献［3］提出了一种只需要少数结点精确位置信息就可以进行正确路由的地理路由机制。其基本思想是首先通过网络中知道自身位置信息的结点确定一个全局坐标系，然后确定其他结点在这个坐标系中的位置，最后根据结点在坐标系中的位置进行数据路由。知道自身位置信息的结点通常是网络中较为特殊的信标结点。

当所有结点的坐标位置信息确定后，协议使用贪婪算法选择路由。因此，协议的关键部分是利用信标结点确定全局坐标系以及确定其他结点在坐标系中的位置。参考文献［3］给出了下面三种策略。

（1）边界结点均为信标结点

该策略假设网络实际边界上的结点都是信标结点，这些边界结点已经确定了一个全局坐标系。非边界结点需要通过边界结点确定自己的位置。在二维情况下，定义结点的位置为邻居结点坐标位置的平均值，公式表示如下：

计算结点坐标的过程是一个逐步求精的迭代过程，具体过程如下：

①在起始阶段，边界结点位置已经确定，设置所有非边界结点的坐标值相同，例如设置为（0，0）；

②在迭代阶段，非边界结点按照式（3－3）和式（3－4）计算自己的坐标，每次计算后邻居结点间都要相互交换计算出新坐标值，再进行下一步迭代；

③当达到一定的迭代次数，如1 000次，或者超过一个停止阈值，如当坐标的变化不超过5%时，迭代停止。此时，每个结点将计算出的坐标值作为自己在坐标系中的位置。

图3－22　边界结点确定非边界结点的坐标

上述迭代过程如图3－22所示，图中网络结点的实际分布为均匀分布。图3－22（a）、（b）和（c）分别显示了经过10次、100次和1 000次迭代计算后得到的结点位置情况。可见在迭代过程中，靠近边界的结点先确定自己的位置，处于网络中央部分的结点最后确定自己的位置。当迭代次数达到1 000次时，计算出的结点坐标已经很接近实际的位置。

（2）使用两个信标结点

在上述策略中，仍然需要网络边界上所有结点都知道自己的精确地理位置，网络部署的成本仍然很高。本策略只使用两个信标结点，而不再需要所有边界结点的精确位置信息，从而大大减少了网络部署的成本。

在本策略中，仍然将结点分为边界结点和非边界结点。边界结点只知道自己处于网络的边缘，但不知道自己的精确位置信息。首先通过边界结点间的信息交换机制建立全局坐标系，然后引入两个信标结点以减少全局坐标系的误差，最后按照前述方法计算非边界结点在全局坐标系中的位置。

边界结点间通过信息交换机制建立全局坐标系的过程如下：

①每个边界结点向整个网络广播Hello消息，中间结点在转发Hello消息时将该消息的跳数值加1。这样，每个边界结点都会收到其他所有边界结点发送的Hello消息，从而得到自己到所有其他边界结点的距离。边界结点将自己到所有其他边界结点的距离存储在一个列表中，称之为边界向量。

②每个边界结点向整个网络广播边界向量。这样，每个边界结点都会收到其他所有边界结点发送的边界向量，从而每个边界结点都能够知道任意两个边界结点之间的距离。

③每个边界结点利用定位算法中的三角形算法（triangular algorithm）计算所有边界结点的坐标，从而建立自己的全局坐标系。

在上述过程中，边界结点在交换距离信息时可能丢失消息，从而导致边界结点间计算出的坐标系不一致。为减少坐标系的不一致性，引入了两个信标结点。每个边界结点在按照上述三个步骤计算出全局坐标系后，首先计算出所有边界结点以及两个信标结点在该坐标系中的位置以及这些结点的重心，然后利用计算出的重心和两个信标结点重新建立全局坐标系。由于重心是所有边界结点以及信标结点位置的平均值，这样大大减少了由于少数边界结点位置信息的丢失对全局坐标系造成的影响，使得所有边界结点建立的坐标保持一致。

（3）使用一个信标结点

上述策略中假设结点知道自己是边界结点，实际网络中结点的部署具有随机性，不能确定自己是否为实际的网络边界结点。本策略利用一个信标结点确定一组边界结点，然后采用上述第二种策略介绍的算法确定全局坐标系并计算结点在坐标系中的位置信息。利用一个信标结点确定边界结点的过程如下：首先，信标结点向整个网络广播Hello消息，消息中包含跳数字段，中间结点将接收消息的跳数最小值加1后转发，从而网络中所有结点都知道自己到信标结点的最少跳数距离；然后，邻居结点间交换到信标结点的跳数距离，如果结点到信标结点的跳数在两跳邻居范围内最大，则标记自己为边界结点。

在建立全局坐标系和计算结点位置后，结点使用贪婪算法选择路径。为了减少路由空洞的可能性，结点交换两跳内邻居结点的位置信息。在选择路径时，结点将数据传送给两跳内距离目标位置最近的结点。如果结点本身是最近的结点，则将数据交给上层程序处理。如果上层程序认为该数据是需要的，就接收该数据；否则，则认为该数据传送陷入了路由空洞，此时结点需要在自己的两跳内邻居结点中找到离目标位置最近的结点，并更新自己的距离信息。为了避免数据由于路由空洞而一直在网络中循环转发，每个数据分组都设定一个TTL值，当TTL值降为0时丢弃该数据分组。

与GEAR路由协议相比，边界定位的路由协议只需要很少结点知道精确的位置信息，减少了对传感器结点的功能要求，降低了传感器网络的部署成本。但为了确定全局坐标系和结点在坐标系中的位置信息，结点需要进行大量的信息交换，通信开销很大。此外，由于算法采用了迭代过程确定结点的位置，计算出的结点位置精度和迭代次数相关。与GEM路由协议相比，边界定位的路由协议建立的全局坐标系更加接近结点实际位置，且对于网络拓扑的变化调整比较简单。