无线传感器网络路由协议(下)

 

在无线传感器网络中很多应用都和节点的位置信息有关。甚至某些应用必须知道节点的位置信息后，传感器节点采集的数据才有真正的价值和意义，如水源监测和河流保护、森林防火及煤矿安全事故预警监测等。地理位置信息既可用于寻找达到基站或汇聚节点的最短路径，又可用于形成虚拟的网格，使得一次只有少量的节点处于激活工作状态。地理位置路由假设的前提是节点知道自己的位置信息，也知道目的节点和目的监测区域的地理位置。节点的位置确定通常有三种方法：使用全球定位系统(GPS)；利用三边测量技术使用超声波系统；使用信标。节点根据这些地理位置信息来寻址和作为路由的依据，并采取一定的策略转发数据到目的节点。值得注意的是基于地理位置的路由所需位置信息的精度和代价紧密相关，根据不同的应用需求选择合适精度的位置信息来实现数据的转发。常见的地理位置路由有以下几种。

 

    1．GAF

 

GAF(Geographic Adaptive Fidelity)是Y.Xu等人提出的基于位置的能量感知路由算法，最初主要是为移动Ad Hoc网络应用设计的，但也可以适用于无线传感器网络。其基本思想如下：

 

    ①网络区域主要首先被分成固定区域，并形成一个虚拟的网格。在每个区域里，传感器节点彼此协作，并且扮演不同的角色。例如，每个区域内所有节点会选出一个传感器感应节点在某一段时期内保持清醒状态，而其他节点都进入睡眠状态。被选中的节点代表该区域中所有的节点负责监测和报告数据给基站或汇聚节点。因此，GAF路由算法是通过关掉网络中不必要的节点来节省能量的，且并不影响路由的保真度(Level of RoutingFidelity)。

 

②网络中每个节点凭借GPS接收卡指示的位置信息将节点本身与虚拟网格中某个点关联映射起来。网格上面与同一个点关联映射的节点对于分组路由的代价而言是等价的。为了节省能量，利用这种等价性可使得某个特定网格区域的一些节点保持睡眠状态。这样，GAF路由算法随着网络节点数目的增加可以极大地提高网络的寿命。

 

GAF路由算法定义了三种状态，分别是发现状态、确定网格邻居的状态及主动地反馈路由参与的激活状态、睡眠状态三种。如图3-13所示给出了GAF路由协议算法的状态变迁示意图。

 

         

 

为了解决移动性问题，网格中的每个节点估计它们各自的网格离开时间并将该时间发送到它们的邻居。为了保持路由的保真度，正在睡眠状态的邻居相应地调整它们的睡眠事件。在激活的节点离开网格时间到期之前，唤醒睡眠的节点，并让其中一个处于激活状态。GAF路由算法的实现可以针对非移动性(GAF-basic)和移动性(GAF-mobility Adaptation)两类节点。如图3-14所示给出了类似文献[33]的应用于无线传感器网络固定区域的一个样例。其中，固定的簇都选成大小相等的正方形。正方形大小的选择取决于需要的发射功率和通信方向。当信号传播的距离为 时，就能够保证来自垂直和水平方向的通信。之所以这样选择，是为了保证任意两个相邻簇(无论水平的还是垂直相邻的)的两个传感器节点能够直接通信。而对于保证处于对角的节点通信的话，信号需要传播更小的距离。GAF路由算法关键的问题就是如何为节点分配角色，并选出簇头。簇头可以要求簇内传感器感应节点如果发现目标时立刻切换到工作状态并开始采集数据。然后，簇头负责接收从簇内其他节点发来的原始数据，并转发给本地基站或汇聚节点。

         

GAF路由算法的核心思想就是尽量通过使虚拟网格中每个区域的代表节点总是处于激活状态模式来保持网络互联。相比一般的Ad hoc路由协议，GAF路由算法保持了延迟和分组转发的性能，并且通过节能机制增加了网络的寿命。尽管GAF是一个基于地理位置的路由协议算法，但它也可用于分级分簇路由协议，因为簇的划分都是基于节点地理位置信息的。对每个特定的网格区，代表节点担当领导者(Leader)来发送数据给其他节点。然而，领导者节点并不像其他分级协议那样，GAF算法里面的领导者节点并不做任何数据汇聚或融合工作。

 

2．GEAR

 

前面提到的基于查询的路由协议，基站或汇聚节点需将查询消息发送到事件区域内的所有节点，即通过泛洪方式将查询命令消息传播到整个网络，建立基站或汇聚节点到事件区域的传播路径，这种路由建立过程开销较大。而Y.Yu等人提出的GEAR(Geographicaland Energy Aware Routing)路由协议就是根据事件区域的地理位置信息，建立基站或者汇聚节点到事件区域的优化路径，避免了泛洪查询消息，从而减少了路由建立的开销。GEAR协议假设了已知事件区域的位置信息，且节点都知道自己的位置信息和剩余能量。此外，节点可通过一个简单Hello消息交换机制就能知道所有节点的位置信息和剩余能量信息。GEAR协议和大多数Ad hoc网络路由协议一样，还假定了节点间无线链路是对称的。

 

GEAR协议中的查询消息包含了位置信息，且节点只需将其发送到网络指定的区域。转发查询消息到目的位置是通过某种概率选择邻居来实现的，且查询消息仅在目标区域内泛洪传播。每个传感器节点都需维持一个邻居表，表中包含了节点的剩余能量和每个邻居的位置信息，另外也包含了转发到每个邻居的代价。GEAR路由协议是通过能量感知和地理信息支持的邻居选择启发式方法来选择最小代价的节点来转发分组到邻居，从而达到目的地节点。其核心思想就是通过仅考虑某个区域而不是发送兴趣消息到整个网络的方式来限制定向扩散协议中的兴趣消息数，这样GEAR协议比定向扩散协议可节省更多的能量。   

 

GEAR路由协议中查询消息传播分为两个阶段。首先基站或汇聚节点发出查询消息指令，根据事件区域地理位置消息将查询指令传输到区域内距基站或汇聚节点最近的节点，然后从该节点将查询指令传播到区域内其他所有节点。采集的数据沿着查询指令的反向路径向基站或汇聚节点传播，如图3-15所示。

         

 (1) 将查询指令消息传送到事件目标区域

 

GEAR路由协议采用两种代价表示路径代价：获得代价(Learned Cost)和估计的代价(Estimated Cost)。估计代价是综合了节点剩余能量和到事件区域目的节点的归一化距离。节点到事件区域的距离用节点到事件几何中心的距离表示。由于所有节点都知道自己位置和事件区域位置，故所有节点都能计算自己到事件几何中心的距离。获得代价是对估计代价的一种提炼，考虑了网络绕洞的路由问题。所谓出现一个洞是指一个节点不存在任何比自身离目标区域更近的邻居节点的现象，或者说如果节点的所有邻居节点到事件区域的路由代价都比自己的大时，则陷入路由空洞(Routing Void)。克服这种现象可以使节点在邻居节点中选择到事件区域代价最小的节点作为下一跳节点，并将自己的路由代价设为该节点的一跳通信代价加上该下一跳节点的路由代价。当不存在洞现象时，估计代价刚好等于获得代价。每当分组到达目的节点获得代价就会向前回传一跳以至于下一个分组的路由建立需要调整。当还没有建立从基站或汇聚节点到事件区域的路径时，中间节点使用估计代价来决定下一跳节点。

 

节点计算自己到事件区域估计代价的公式(3-9)如下：

 

 

式中，C(N，R)为节点N到事件区域R的估计代价；D(N，R)为节点N到事件区域R的归

一化距离；E(N)为节点N的归一化剩余能量；α为比例参数。

 

当查询指令消息到达事件区域后，事件区域内节点沿着查询消息的方向路径传输监测数据，且数据中携带了每跳节点到事件区域的实际能耗值。数据传输经过的每个节点首先记录携带消息中的能量代价，然后将消息中的能量代价加上它发送该消息到下一跳节点的能耗，并更新原有携带消息的值来转发数据。节点下一次转发查询指令时，用刚才记录到的事件区域的实际能量代价代替式(3-9)中的D(N，R)，计算它到基站或汇聚节点的获得代价。节点用调整后的获得代价选择到事件区域的优化路径。

 

(2) 查询消息在事件目标区域内的传播

 

当查询指令消息到达事件区域后，可通过限制方式传播到事件区域内的所有节点。当节点密度较大时，泛洪开销太大，可采用递归地理转发策略。也就是说事件区域内首先收到查询指令的节点将事件区域划分为若干个子区域，并将所有子区域中心位置转发查询指令消息。在每个子区域中，最靠近区域中心的节点接收查询指令，并将自己所在子区域再划分为若干个子区域并向若干子区域中心转发查询指令。当全部子区域转发过程结束时，就停止递归转发过程。限制泛洪机制和递归地理转发机制各有自己的特点。当事件区域内节点分布密集时，采用递归地理转发的消息转发次数少，而节点分布较稀疏时，采用限制泛洪策略路由转发效率更高。存在一种简单方法可以灵活选择上面两种策略：当查询指令到达事件区域内的第一个节点时，判断该节点的邻居是否大于一个预先设定的阈值，如大于该阈值则采用递归地理转发机制，否则采用限制泛洪机制转发查询指令消息。

 

GEAR路由协议在路由建立过程中采用了局部最优的贪婪算法，适合无线传感器网络中节点只知道局部拓扑信息的情况，缺陷是可能缺乏足够的拓扑信息导致路由空洞现象出现，降低了路由效率。如果节点采用相邻两跳节点地理位置信息，就可大大降低路由空洞产生的概率。此外，GEAR路由协议假设节点地理位置固定或变化不频繁，适用于移动性较小的传感器网络应用环境。

 

在GEAR路由之前，B.Karp和H.T.Kung还提出一个与其类似的非能量感知的地理路由GPSR(Greedy Perimeter Stateless Routing)，它是利用平面图来解决路由空洞问题的。

 

对于GPSR路由，分组是沿着平面图的周边来寻找路由的。尽管该方法减少了节点维持的状态数，但最初设计主要是考虑用于移动Ad hoc网络，并且要求定位业务能够将定位和节点标识映射对应起来。相比之下，GEAR路由不仅减小了路径建立的能耗，而且在分组转发率方面优于GPSR路由。仿真结果也表明了对于非均匀的业务分布，GEAR路由比GPSR路由转发率高出70％～80％。对于均匀业务，GEAR路由比GPSR提高了25％～35％。

 

3．SPAN

 

B.Chen等提出了一种基于位置的路由算法SPAN，它是按照节点的位置来选取一些节点作为协调者(Coordinator)或者主管节点的。这些选出的主管节点形成一个网络骨干，专门负责转发消息。如果非主管节点的两个邻居不能彼此直接通信或者通过一到两个其他主管节点连通的话(即三跳可达性)，则该节点就应当成为一个新的主管节点。在复杂的SPAN算法中，新的和现有的主管节点不一定是邻居，实际上由于需要维护两到三跳邻居的位置信息，这种算法使得路由协议设计具有更差的有效节能性。

 

4．GEM

 

GEM(Graph EMbedding)路由协议是J.Newsome和D.Song提出的一种基于地理位置信息的适用于数据中心存储方式的路由机制。它们的研究将传感器网络存储监测数据分为三种方式，包括数据中心存储(Data-centric Storage)、本地存储(Local Storage)和外部存储(External Storage)三种。

 

数据中心存储方式是指在网络中选择不同的主管节点实现不同事件监测数据的融合和存储。该方式首先对可能的监测事件进行命名，然后按照某种策略将每一个事件映射到一个地理位置上，距离这个位置最近的节点作为该事件的主管节点。节点监测到事件方式后，把相关数据发送到映射位置。主管节点来接收数据，并进行数据融合，然后存储到本地。数据中心存储方式是在查询延迟、存储空间和能耗等多项指标进行了折衷平衡，是介于本地存储和外部存储之间的一种方式。

 

在本地存储方式中，节点首先将监测数据保存到本地存储器中，并在收到查询指令后，再将相关数据发送到基站或汇聚节点。由于网络传输的数据都是基站或汇聚节点感兴趣的数据，故网络传输效率高，但要求每个节点都有较大的存储空间，数据融合只能在传输过程中进行，且基站或汇聚节点要经过较长延迟后才能获得查询数据。

 

在外部存储方式中，节点获得监测数据后，都主动把数据发送给基站或汇聚节点。因节点将采集到的数据及时传给了基站或汇聚节点，从而可提高无线传感器网络对突发事件的响应速度。但是由于监测数据不断发送给基站或汇聚节点，一方面由于某些数据并非是基站或汇聚节点所感兴趣的，造成网络传输能量和带宽资源的浪费；另一方面也容易使得在基站或者汇聚节点附近形成网络热点拥塞区域，降低网络整体吞吐率。

 

GEM路由协议的核心思想就是建立一个虚拟的极坐标系统(VPCS，Virtual PolarCoordinate System)，用来代表实际的网络拓扑结构。整个网络节点形成一个以基站或汇聚节点为根的带环树(Ringed Tree)。每个节点极坐标用两个参数来表示：一个是距离树根的跳数距离；另一个是角度范围。节点间的数据路由是通过该带环树来实现的。下面详细介绍一下GEM路由的三个关键组成要素。

 

    (1) 虚拟极坐标系统的建立

 

    虚拟极坐标系统的建立需要三个阶段：生成树型结构、反馈子树大小和确定虚拟角度范围。

 

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

 

②反馈子树大小：所谓子树大小是指树中包含的节点数目。在树型结构建立后，从叶节点开始，节点就将以自己为根节点的子树的大小报告给它的父节点。叶节点向父节点报告的子树的大小为1，中间节点将自己的所有子树的大小相加，并加1就得到自己子树的大小，然后报告给它的父节点。依次类推，这个过程一直进行到基站或汇聚节点，最后基站或汇聚节点得到整棵树的大小。

 

③确定虚拟角度范围：基站或汇聚节点首先确定整个虚拟极坐标系统的角度范围，如[0,90]。注意到该角度仅仅是一个逻辑概念，并非实际的方位角。基站或汇聚节点将角度分配给每个子节点，每个子节点得到的角度范围与该节点为根的子树的大小成正比。然后每个子节点再重复这样的分配过程，即将其角度范围分配给它的子节点，如图3-16所示，该过程一直进行到每个子节点都得到一个角度范围。

         

经过上述阶段之后，网络每个节点都知道自己到基站或汇聚节点的跳数和逻辑角度范围，这样就可用一个坐标(跳数，角度范围)唯一表示每个节点。为了避免在树型结构当中，跳数相同的节点间角度范围乱序，可采用逆时针或者顺时针规则为节点分配角度范围，这样可使同一级节点角度范围顺序递增或递减，如图3-16所示采用的就是逆时针递增规则。可以看出，到基站或汇聚节点跳数相同的节点就形成一个环状结构。因此，GEM路由协议是通过带环的树来实现数据路由的。

 

(2) 虚拟极坐标路由算法

 

虚拟极坐标路由算法(VPCR，Virtual Polar Coordinate Routing)的基本过程如图3-17所示，节点发送消息时，若目的位置的角度不在自己角度范围内，就向父节点传递该消息，父节点也以同样的方式处理该消息，直到消息到达了角度范围包含目的位置角度的节点，该节点就是源节点S和目的节点D的共同祖先，如图3-17(a)中的节点R。

 

因最初的GEM路由算法需要上层节点转发消息，网络开销较大。一个改进的策略就是在节点上传消息之前，首先检查同一层的临近节点是否包含目的位置的角度范围。如有，则直接传给该临近节点，这样就避免了上传消息带来的较大开销，如图3-17(b)所示。

 

更进一步的GEM路由协议改进的算法利用了前面提到的环状结构，称为虚拟极坐标路由算法(VPCR)。节点查看相邻节点的角度范围是否离目的位置更近，如果是更近，就将消息传给该邻居节点，否则就向上层传输，如图3-17(c)所示。

    

(3) 对网络拓扑变化的适应

 

由于GEM路由算法是建立在虚拟极坐标系统上的，而系统是一个逻辑拓扑，故当实际网络拓扑发生变化时，需要及时局部更新虚拟极坐标系统。为了保证拓扑发生变化后的虚拟极坐标系统仍然是一个树型结构，避免环路路由发生，局部更新应当满足下列一致性条件。

 

    ① 除了基站或汇聚节点外，每个节点只有一个父节点。

    ② 每个节点跳数值为父节点跳数值加1。

    ③ 每个节点的角度范围是父节点的角度范围的子集。

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

 

对于网络拓扑的变化，主要考虑两种情况：节点加入和节点失效。

 

    ① 节点加入情况的处理：假如节点D要加入树结构，并可连接到节点R，R就成为节点D的父节点并为D赋予跳数和角度范围值。节点D的跳数是节点R的跳数距离加1，角度范围可有两种选择办法：一是在生成树结构时预留一些角度范围，此时可用来分配给新加入的节点。另外一种就是向上层节点申请更多的角度范围。这个过程或许要一直到基站或汇聚节点才能结束。

 

② 节点失效情况的处理：当节点R失效时，R的所有子树包含的节点都成为孤立节点。假定R的某个子节点E可以连到另外一个非孤立节点R₁，则E将R₁作为父节点。为满足拓扑更新一致性条件，需要修改一些属性：节点E的跳数距离为R1的跳数距离加1，且E的子树都要做相应的变化；R₁及R₁到基站或汇聚节点路径上的所有节点都需将E的角度范围加入自己的角度范围；失效节点R的父节点D需要将E的角度范围从自己的角度范围内减去，这种变化同样要向上层节点传送，直到到达R以及R₁的共同祖先。如果R的子节点E不能连接到任何非孤立节点，但是E的子树上有节点B₁可连到非孤立节点R₁，这时子树的结构要逆转过来，E成为B₁的子节点。B₁作为子树的根节点继承E的角度范围并进行角度范围的重新赋值，按照上述方法一直连接到R₁上。

 

GEM路由协议算法根据节点的位置消息，将实际网络拓扑结构转化为虚拟极坐标系统的以基站和汇聚节点为根的带环树逻辑结构，并在带环树逻辑结构上实现了相应的数据路由。GEM提供的路由机制不需节点精确的位置信息，且能够凭借VPCS简单地将实际网络拓扑信息映射到易于进行路由处理的逻辑拓扑，而不改变节点的相对位置。但是不足的是，带环树在实际网络拓扑发生变化时，树的调整相当复杂，因此，GEM路由协议比较适合于静态或拓扑结构相对稳定的无线传感器网络应用。

 

5．GRWLI

 

GRWLI(Geographic Routing Without Location Information)路由协议是A.Rao等人提出的一种只需要少数节点精确位置信息就可正确路由的地理路由机制。在无线传感器网络实际应用中，要让每个节点都知道自己的精确位置信息，这样就会给路由带来很大的代价。近年来，人们关注地理路由的一个主要话题就是如何在保证路由正确性的前提下，尽量减少需要精确位置信息的节点数目，以及路由机制对节点精确位置信息的依赖程度。

 

GRWLI路由协议的基本思想就是：首先通过网络中知道自己位置信息的节点(如边界节点)确定一个全局坐标系，然后再确定其他节点在这个坐标系中的位置，最后根据节点在坐标系中的位置进行数据路由。知道自己位置信息的节点通常是网络中较为特殊的信标节点。实际上，当所有节点的坐标消息确定后，GRWLI协议就可利用贪婪算法选择路由了。因此，该协议的关键就是如何利用信标节点来确定全局坐标系以及确定其他节点在坐标系中的位置。A.Rao等人在文献中给出了GRWLI的三种策略。

 

    (1) 确定边界节点都为信标节点

 

将网络实际边界上的节点都假设为信标节点，也就是说这些边界已经确定了全局坐标系。非边界节点须通过边界节点来确定自己的位置信息。在平面情况下，节点位置是通过邻居节点位置的平均值来计算的，如式(3-10)所示。

         

节点位置坐标的确定是个逐步求精的迭代过程：初始阶段，因边界节点位置已经确定，故只需设置所有非边界节点的坐标值相同，如均为(0,0)；迭代求精阶段，非边界节点按照式(3-10)来计算自己的坐标，每次计算后，邻居节点之间都需相互交换计算出新的坐标值，再进行下一步迭代。迭代结束的条件设置可通过迭代次数或迭代停止阈值来控制，如超过500次就停止迭代计算或者坐标变化不超过1％时停止迭代等。

 

(2) 使用两个信标节点

 

在上面策略(1)中，仍然需要网络边界所有节点都要知道自己精确位置信息，网络配置成本还是很高的。为进一步减少网络部署成本，策略(2)只采用两个信标节点。该策略网络边界节点只知道自己处于网络边界，并不知道自己的精确位置消息。其基本思想就是：首先通过边界节点交换信息建立全局坐标系，然后引入两个信标节点以减小全局坐标系的误差，最后按照策略(1)方法计算非边界节点在全局坐标系中的位置。策略(2)的关键在于边界节点信息交换机制，其交换过程包括以下三个阶段。

 

    ① Hello消息广播：每个边界节点都广播Hello消息，中间节点转发Hello消息时将该消息的跳数值加1，这样每个边界节点都知道自己到其他边界节点的距离，并将自己到所有其他边界节点的距离保存在一个称为边界向量的列表中。

 

② 广播边界向量：每个边界节点向整个网络广播边界向量，从而每个边界节点都知道任意两个边界节点之间的距离。

 

③ 三角定位法：每个边界节点利用三角形定位算法(Triangular Algorithm)计算所有边界节点的坐标，从而建立自己的全局坐标系。

 

由于上述信息交换过程容易丢失信息，导致计算的坐标系不一致。为了减少坐标系的不一致，故引入两个信标节点来帮助减小计算的误差。其具体操作是：当计算出全局坐标系后，首先计算两个信标节点和所有边界节点在坐标系中的位置以及这些节点的重心，然后利用计算出的重心坐标和两个信标节点坐标重新建立全局坐标系。由于重心是所有边界节点和信标节点位置的平均值，这样极大地减小了少数节点位置信息的丢失而导致的对全局坐标系的影响。

 

(3) 使用一个信标节点

 

由于实际网络节点部署具有随机性，节点并非知道自己是边界节点，故又提出了第三种策略，即只用一个信标节点确定一组边界节点，然后利用策略(2)确定全局坐标系并计算节点在坐标系中的位置。其基本过程如下。

 

    ① 首先，信标节点向全网广播包含跳数字段的Hello消息，中间节点将接收消息的跳数加1后转发，这样网络中所有节点都知道自己到信标节点的最少跳数距离；然后，邻居节点间交换到信标节点间的跳数距离。假如节点到信标节点的跳数在两跳邻居范围内最大，则标记自己为边界节点。

 

② 当建立了全局坐标系和计算节点位置后，节点就使用贪婪算法选择路由。为避免路由空洞现象，节点交换两跳内邻居节点的位置信息。在选择路由时，节点将数据发送给两跳内离目标节点最近的节点。如节点本身就是最近节点的话，则将数据交给上层程序处理。如上层程序认为该数据是需要的，就接收该数据。否则，就认为数据传输陷入路由空洞，此时，节点需要在自己两跳邻居中找到离目标位置最近的节点，并更新自己的跳数距离信息。为了避免路由空洞，每个分组都设有一个最大生命期TTL值，当TTL降为0时则丢弃该分组。

 

GRWLI协议与前面GEAR路由相比，只需少量节点就知道自己精确位置信息，降低了对传感器节点设计的功能成本和网络部署成本。但由于需要节点进行大量信息交换以确定全局坐标系和节点在坐标系中的位置，导致通信开销很大。另外，通过迭代计算的节点位置精度和迭代次数紧密相关。相比GEM路由，GRWLI路由协议建立的全局坐标系更接近实际位置，且对于网络拓扑变化的调整也要简单些。

 

6．GEDIR／MFR／DIR

 

I.Stojmenovic和X.Lin等在文献[39]中叙述并探讨了基本的定位路由算法，这些算法是和基本距离、变化和方位有关的。关键问题就是正向方位和反向方位。源节点和任何中间节点将按照某种准则选择其中一个邻居。属于这同一类的方法有MFR(Most ForwardWith Radius)、GEDIR(The Geographic Distance Routing)以及DIR(Compass RoutingMethod)。GEDIR是贪婪算法、两跳的贪婪算法和交替的贪婪算法和DIR算法的一种变体，因为GEDIR算法总是将分组发送到当前顶点的邻居节点，且保证当前顶点和目的节点距离最近。当分组连续两次跨过同一边时该算法失效。多数情况MFR和贪婪算法有相同的路径通往目的节点。在DIR算法当中，最佳邻居拥有离目的节点最接近的方位(也就是角度)。也就是说，离虚线最小角度距离的邻居加入当前的节点并且选定目的节点。在MFR算法中，最佳邻居A将会最小化点积DA·DS，其中分别是源节点和目的节点，并且SD代表两个节点S和D之间的欧氏距离。另外也可选择最大化点积SD·SA。当最佳选择将返回消息到一个以前的节点时，上面提到的每种方法都停止在该节点转发消息。GEDIR和MFR都是无环路由，而DIR算法却可能产生路由环，除非缓存先前的业务或者采用加强时戳。