采用Hull树的贪婪地理位置路由算法的设计*

毛科技，赵小敏，衣俊艳，夏 明，雷艳静，王 尧，陈庆章

(浙江工业大学计算机科学与技术学院，杭州310023)

无线传感网络在森林监测、气候监控、军事战场、数字城市方面有广泛的应用前景。在诸多应用领域中，不仅要求随时获取目标的一些物理量数据，还要求得到目标的地理位置，由此推出很多WSN定位技术。随着无线传感网络应用深入，很多应用不仅要求携带地理位置信息，还要求数据能够根据地理位置信息向特定的地理位置转发，节点接收由特定地理位置传来的信息，数据沿着特定的地理路径传递。为了满足这些应用需求，人们需要研究依靠节点的地理位置信息来进行报文转发与数据寻路的路由技术，这就是所谓基于地理位置的路由协议。地理位置路由协议一般可以分为使用地理位置信息进行辅助路由寻路的路由协议与基于地理位置信息的路由协议两类［1］。后者又可以按其主要实现方式不同分为定向区域泛洪、贪婪路由算法和分层路由算法等路由协议。

基于贪婪路由算法的地理位置路由协议是目前研究比较深入的一类地理位置路由协议。此类协议是在贪婪路由转发策略的基础上，通过各种方法改进其寻路表现。简单的说，贪婪路由转发策略就是转发节点将数据传给离目的节点更近的节点。地理位置中的贪婪路由算法主要面临的问题是如何解决由于实际节点布设位置不均匀而导致的网络拓扑结构中空旷域(Voids)［2］引起的路由转发失败的情况。为了解决这一问题，学者提出了一系列的路由算法。GFG(greedy-face-greedy)算法［3］是最早提出了采用GG图(Gabriel graph)来平面化网络图，从而在贪婪路由寻路失败时使用face routing的寻路方法来继续转发报文的贪婪路由协议;GPSR协议［4］采用类似的方法，但是由于在网络的平面化以及寻路方式细节方面的改变，使得GPSR协议得到了更好的性能表现和实用性，从而成为在地理位置路由领域最为认可的协议之一。文献［5－6］提出了face routing的寻路何时切换回贪婪路由寻路，并在得出切换的最佳时机上开发出了GOAFR(Greedy and(Other A-daptive)Face Routing)与 GOAFR+路由协议。MIT的Ben Leong提出了GDSTR和GSpring算法［7］。还有基于散列值的路由协议［8］，基于能量优化的路由算法［9］，通过改进蚁群算法的路由算法［10］等。

所谓空旷域，是指在实际的无线传感网络中，不管是人工的放置节点在固定的位置，还是撒播，总会遇见某些地方是节点无法存在的区域，或者是位于此地的节点无法正常工作的区域，比如沼泽，湖泊，大河，高楼，具有强电磁干扰的地方等;即使是均匀的放置，也会由于网络中某些节点因为断电或异常等情况失效，从而在网络中形成大小不等的“空洞”。在这些空洞内部，没有节点来进行数据分组的接力转发。在实际的路由过程中，往往需要绕过这些空洞来转发数据。正如图1所表示的那样，转发节点x无法找到比自己距离D点更近的节点，然而确实存在这样的一条路径(x，w，v)可以使报文得到顺利的转发。这时原有的贪婪转发策略就失败了，需要新的方案来解决这一问题。

图1 空旷域(Void)

本文借用图形学上凸包(convex hull)的概念，结合原有的贪婪转发策略，提出了GHTGR(Greedy Hull Tree Geographic Routing)算法。这是一个面向无线传感网络的分布式地理路由算法。通过Hull树，它构建一个以本地节点为中心的多层次凸包结构，用于描述节点周围的局部网络拓扑结构，报文只需在节点内部的Hull树内进行搜索，从而获得数据分组的转发路径(包括绕过空旷域的路径)。实验表明，本算法相比于GPSR算法，不仅能够正确地寻找到数据分组的转发路径，同时在初始的报文交换方面，尽可能地将报文交换局限在局部区域以内，有效地减少了全网报文广播对网络负载与性能的影响。由于此算法只需得知局部的网络拓扑结构，从而比之于GPSR算法灵活性与适应性更高。

1 算法的构建

1.1 平面化网络拓扑结构与凸包

对于GPSR算法中face routing方法来说，得以运行的一个首要条件就是要构造一个平面图来描述实际的网络拓扑。这样的图须满足:网络拓扑结构应当是平面化的［11］;平面图中任意两边都不相交;平面图中不存在不封闭的多边形结构。任何基于网络拓扑结构进行寻路的路由协议，首先要解决的问题就是如何将现实的、由节点之间的通讯关系所形成的网络拓扑记录下来，并经过某种算法的处理，形成节点可以识别、处理、存储的平面图形结构。常用的网络拓扑图［12］的方法有 UDG(unit disk graph)图、最小生成树(MST)、RNG图(Relative Neighbor Graph)与GG图(Gabriel Graph)。

凸包(Convex Hull)［13］是这样的一个图形:给定平面上的一个(有限)点集(即一组点)，这个点集的凸包就是包含点集中所有点的最小面积的凸多边形。“最小面积”这个限制条件，保证了凸包的唯一性，因为除了凸包以外，还有无限多个包含点集中所有点的凸多边形。例如，只要画一个面积足够大的四边形，便可包围任意给定的点集。因此假如没有这个限制条件，求凸包就变成非常容易但却没有唯一解的运算。它的数学描述如下:

在一个实数向量空间V中，对于给定集合X，所有包含X的凸集K的交集S被称为X的凸包。

X的凸包可以用X内所有点(x1，…，xn)的线性组合来构造

在路由算法中，凸包一般被应用于如下的场合。当节点分布比较密集时，逐个比较每个节点到目标区域的前进距离所需要的计算开销很大。而凸包是一个节点集合中处于“外围”的节点连线构成的凸多边形。当转发节点计算报文转发路径时，只需要比较凸包上的点到目的节点的距离即可。在节点密度较大时，节点就不需要比较自己的所有邻居节点信息，大大降低了节点在寻找下一条转发路径计算量。常用的凸包构建算法有增量式算法(Incremental algorithm)、包裹法(Gift wrapping algorithm)、快包法(QuickHull)、分治法(Divide and Conquer algorithm)等多种方法。

1.2 Hull树存储结构与报文结构

在本算法中，采取了如图2所示的Hull树存储结构，以及如图3、图4报文结构。(表1与表2分别说明了这两种报文结构中各个域的功能定义)

图2 Hull树存储结构

图3 Hull树构建维护过程报文结构

图4 路由寻路过程数据分组报头

表1 Hull树构建维护过程报文格式及功能

表2 路由寻路过程数据分组报头格式及功能

2 算法设计

在介绍算法运行过程之前，首先介绍本算法运行的假设前提条件。正如大多数地理路由算法所要求的那样，实行地理路由算法的无线传感网络中的节点，应当具备通过独立设备或者交换报文从而得到节点地理位置信息的能力。同时，该网络的拓扑结构应当比较稳定，节点位置不会经常性地发生改变，一般处于静止固定的状态，不会长时间地处于移动状态之中［14］。

算法在实际运行过程中分为两个部分:①初始化阶段;②数据分组转发阶段。

2.1 初始化阶段

在初始化阶段，整个无线传感网络每个节点通过与相邻节点之间的报文交换，分布式地在每个节点上建立一个局部HULL树。具体实现过程如下:

(1)当节点p开启时，它首先向周围广播查询报文Inquiry message，询问所有邻居节点是否可以将其自身存储的Hull树寄送到p，以使p加入网络，并构建自身Hull树。当节点p广播查询报文Inquiry message时，任何邻居节点如果接收到这样的报文，则有以下三种反馈情况:①邻居w已经存储有Hull树，此时返回Hull树报文;②邻居节点并未构建Hull树，则返回Hull树构建命令报文(Hull build message);③p节点直接通讯范围之内没有任何节点，因此接受不到任何反馈报文。如果p接收到邻居反馈的Hull树报文(Hull tree message)，则等待足够数量的邻居发来Hull树报文之后，依据算法在其中构建一个凸包，并将凸包上的点的Hull树添加到p节点的Hull树中，再向周围邻居节点广播p的Hull树。第②种情况下转入(2)，第③种情况下转入(3)。

(2)节点 p收到Hull树构建命令报文(Hull build message)，表示在这个局部范围内未构建Hull树，于是P首先以自己为根节点，接受足够数量的邻居返回报文之后，建立本地Hull树，并将自身Hull树向邻居节点广播。在这个过程中可能会出现以下两种情况:①p节点只收到了返回的Hull树构建命令报文，此时说明P的邻居节点中都未构建Hull，这时p依据邻居节点的Hull树构建命令报文构建的Hull必然是一个一层无子树的Hull树结构;②p节点收到的所有报文中，既有返回Hull树构建命令报文，也有返回的Hull树报文，此时对p来说，同样是先根据这些报文构建本地Hull树，同时判断哪些返回Hull树报文的邻居节点是否是本地Hull树的子节点，如是，则将其Hull树添加进本地Hull树;如否，则抛弃。

(3)节点p收不到任何反馈报文。这说明p没有任何邻居，此时建立的Hull是一个仅有以p为根节点的树。这个过程中，节点通过接收邻居节点的报文，从中选择符合要求的Hull树上的(凸包上的)节点加入自身的Hull树中。同时，通过交换初始报文，也很容易地为每个子节点添加上属于它的hull树结构。网络初始时的Hull树构建过程，是一个较为漫长的过程，在这个过程中，节点要一直等待邻居节点发来的各类报文，根据Hull树构建算法对自身的Hull树进行修剪，再将自身的Hull树向邻居节点广播。本算法中采用包裹法构建Hull树的算法如下:

算法1 包裹法构建凸包

标记p节点所有邻居节点的链表List(N1、N2、N3…Ni)，其中Ni由节点标志与位置信息X、Y构成。

存储凸包结构HullTree(nodes)

在完成了Hull树的构建工作之后，在整个路由算法运行过程之中，需要不停地依据实际情况维护各节点上Hull树。一般有如下三种情况并采取相应的措施:①新节点的加入。这种情况下，可以根据以上Hull构建阶段的方法，为节点构造Hull树，并将其信息通知到各个邻居节点;②节点移动或者从暂时的休眠中恢复。在这种情况下，节点仍保存有原有的Hull树，但此时的Hull树信息可能已经过时，应当重新发出查询请求报文来取得新位置下，邻居节点的位置及其存储的Hull树信息，通过对自身原有Hull树的对比，修正自生Hull树;③节点的离开。节点为它的每个邻居节点设立一个时间阈值。这一阈值也是节点和它邻居节点进行信息交换的周期。当节点在下一周期向某个邻居节点发出信息交换请求而在限定时间内未收到回应时，将删去自身Hull树中以这个邻居节点为根节点的子树，并广播自身状态信息。

2.2 数据分组转发阶段

当源节点s产生一个需要发往目的节点t的数据分组M时，它会为数据分组添加上文所述的报头，并将路由转发模式(ROUTE MODE)设为初始的Tree模式，然后根据报文模式与节点自身的状态信息，来判断下一步应采取的动作。同样，中间节点v收到由源节点s、邻居节点w发来的目的节点t的报文M，也会检查报文中所标记的路由转发模式，进而根据相关信息(自身Hull树以及目的节点、自身节点的位置信息)选择下一步的行为。

在此我们假设某一中间节点v收到由源节点s、邻居节点w发来的目的节点为t的报文M。具体来说，报文在发送过程中，由于转发模式的不同，大致有以下几种情况。

首先，节点v检查自身是否为报文M的目的节点。若是，则接收报文并停止报文的转发;若否，则检查是否是报文中P NODE域所表示的中间目的节点。若是，按照报文中所载的节点转发序列，向下一跳节点转发报文;若否，则进入模式检查。检查报文转发模式。

(1)Tree模式下:

v搜索自身的HULL树，首先判断目的节点是否是v的邻居节点(目的节点是否在Hull树根节点的直接子节点所构成的凸包范围以内)，若是，则直接广播报文即可;否则，判断目的节点t是否存在v的hull树的子树所形成的凸包中，如果是，则将v到该子树根节点在v的Hull树中查找的节点序列作为报文的转发路径，添加到报头的P NODE域中，其中ID和Location为子树根节点的标识与位置，trace域存储节点序列，然后转发报文到下一节点;否则设报文模式为Tree-Greedy。

(2)Tree-Greedy模式下:

节点搜索存储在本地的Hull树，选择其中距离目的节点位置最近的子节点作为报文在本模式下所传输的目的节点，其中从根节点到此叶子节点在Hull树中查找到的节点序列，即为此报文的转发路径。这一模式采取的转发方式同单纯的贪婪法很像，都是寻找距离目的节点最近的节点。不同的是，一般的贪婪法是在邻居节点中寻找距离目的节点更近的节点，然而在本算法中，是在节点本地的Hull树中搜索距离目的节点最近的节点。由于节点Hull树中存储的是一个局部网络拓扑，因此所查找到的转发路径就可以保证数据分组被传递出更广的范围。同时，贪婪法需要比较目的节点同中间转发节点的所有邻居节点的距离，并从中选择距离目的节点最近的邻居节点，而且在每经过一个节点时都需要做这样的比较，然而本算法中只需判断是否在Hull树中规划的凸包以内即可，并在到达某个中间转发节点时才需要做位置比较工作，大大提高了运行效率。

(3)Greedy模式下:

报文进入Greedy模式，就意味着数据报文在转发时进入到了算法中止情况。算法中止存在三种情况:①目的节点的地理位置处于网络覆盖范围以内，网络中不存在目的节点。此时，报文已转发到某一节点q，q对报文检查时发现目的节点在其本地凸包内，只需广播发送报文即可，然而广播此报文不能得到回应，或者说目的节点不存在，此时只需简单地丢弃报文即可。当然，如果对路由协议做可靠性扩展，可以要求q向源节点返回报文转发失败的信息;②节点为网络图的局部达到顶点。在这种情况下，报文到达的节点v将是网络拓扑的某个局部顶点。在v自身的Hull树中无法查找到比v距离目的节点t更近的节点。当协议规定v只存储一层的Hull树时，那么Hull树就没法涵盖到比v节点距离目的节点更近的节点x。显而易见，这是一个比较大的空旷域。如果增加节点中Hull树的层数，就可以增加Hull树的覆盖范围，直至覆盖到一个比当前节点更靠近目的节点的转发节点。当然，这里既然出现了空旷域，那么采用边界转发策略同样也可以解决问题;③目的节点的地理位置处于网络覆盖范围以外。出现这种情况，意味着目的节点在网络之外时，数据报文到达了整个网络的边缘的某个节点，这个节点相比于网络中其他节点，距离目的节点最近。并且显然，此时报文所在节点是它Hull树中凸包上的节点，并非位于凸包的中心。在这种情况下，路由协议简单地标记此报文的目的节点不可达即可。

3 算法仿真与分析

本论文基于MATLAB7进行路由算法的仿真。网络模型为在一个覆盖区域为100×100范围内随机生成由50到500数量不等节点组成的网络。为了保持网络通讯在节点密度较大时，不会由于节点通讯距离过长从而导致路径选择过早地拟合成为贪婪法下的最优路径，因此随着网络节点密度的增大，将适当地减小节点间的通讯距离。

图5 网络中的Hull树结构以及算法两点路由寻路路径

图5表示了一个面积为100×100的网络区域内随机分布了150个节点，每个节点的通讯距离为15单位的网络分布。图5(a)表示出了初始化完成时，从全网络选择某几个节点表现出的Hull树结构。当然，即使是选取的几个节点，也没有表现出它们所有的Hull树结构，只是有选择地选取若干子节点Hull树表现出来。图5(b)中实线线条表示GHTGR算法在运行时一次具体的路径转发。虚线线条表示GPSR算法在相同节点下的转发路径。由图5(b)中可以看出，大多数情况下实线线条覆盖了虚线线条，这表示GHTHR算法与GPSR算法寻找到的转发路径是一致的。由于GPSR算法同样是以贪婪策略为基础的路由转发，一般情况下，在贪婪模式下两算法选择下一跳转发节点的差异不会很大。具体的差异表现在GHTGR算法在Hull树查询方面，可能在Tree-Greedy模式下，出现Hull树第一层的某子节点的凸包上的点(即Hull树的第2层)比其他子节点凸包上的点更靠近目的节点，然而此子节点(在Hull树第一层中)并非距离目的节点更近节点。于是，GHTGR算法会直接选择底层距离目的节点最近的孙子节点(在只有两层的Hull树结构中就是第二层)，将根节点到此子节点的路径作为转发序列，而不像GPSR算法那样直接选取邻居节点中距离目的节点更近的节点。

如图6所示，当节点密度少于120时，GHTGR算法所采用的转发次数比GPSR算法稍高，这是由于节点密度很低时，网络中的空旷域的面积会很大，而此时GPSR算法只要沿着空旷域的边缘来走，就会是最短路径;GHTGR算法在Hull树中的搜索，或许会偏离一到两次空旷域的边缘，因此转发次数稍多。随着节点密度的增大，GHTGR算法的平均转发次数降至了GPSR的曲线以下，说明此时GHTGR比GPSR算法更能寻找到更短的转发路径。这通常是因为在GHTGR算法中，数据分组直接被送往凸包上的点，避免了在节点直接通讯范围内的多次转发。当节点密度增加到空旷域可以忽略不计时，即每个节点的直接通讯范围内都可以找到符合贪婪法策略的下一跳节点，GHTGR与GPSR算法就向GREEDY算法靠近，接近于最短路径算法。从图形上来看，GHTGR算法与GPSR算法在路径转发次数(即路径选择)方面的差距不是很大，这说明每个算法基本上都找到一条与节点之间实际最短路径相近的路径。

图6 不同算法节点转发次数比较

图7表明了网络初始化时，GPSR算法形成网络整体平面图所花费资源与GHTGR通过交换报文形成局部Hull树所耗费资源的对比情况。具体的报文转发数量受限于网络通信MAC层所使用的具体协议。在这里我们衡量的报文数为节点向外广播它的状态信息的报文数。实验表明，采用GHTGR算法的初始报文交换数量远远低于GPSR算法的报文交换数量。这是因为GHTGR算法不要求每个节点获得整个网络所有节点的平面化拓扑结构，从而将大多数的报文局限在一跳或者两跳的范围之内，不会类似于GPSR算法进行全网规模的数据报文交换。

图7 单位区域中不同节点密度报文转发数量

图8表示了不同空旷域数量下的路由路径选择情况。可以看到，当图中空旷域数量较小时，GPSR算法所寻找到的转发路径与GHTGR算法寻找到的路径差不多，然而随着空旷域的数量增多，GPSR算法寻找路径的跳数比GHTGR算法的路径跳数增长更快。这表明，随着空旷域的增加，在GPSR算法寻路过程中，数据报文仅仅依赖于空旷域的边界转发措施，导致数据分组的转发路径序列不一定会是到达目的节点转发的最短路径序列。然而，由于GHTGR算法采用了Hull树的搜索，当空旷域足够小时，本地节点Hull树中所寻找到的节点转发序列，就可能会绕过此空旷域。仿真结果表明，GHTGR算法确实在多空旷域的数据寻路过程中，相对于GPSR算法找到了更好的转发路径。

图8 不同空旷域数量下节点转发路径跳数

4 总结

仿真实验表明，相比于GPSR算法，GHTGR算法在保证寻路正确性的基础上，较大地降低了算法用于初始化网络拓扑结构所进行报文交换的数量。当节点密度较大时，该报文交换被局限于局部范围以内，不会引起报文的全网广播，有效地限制了报文增长的幅度。其次，在网络空旷域较多的情况下，GHTGR算法对路径的选择同样优于GPSR算法，这是由于规避了GPSR算法引起的在空旷域边沿频繁的模式切换。

未来对于GHTGR算法来说，如何与地理区域广播(GEOCAST)结合起来，进一步扩展地理路由算法的使用范围。同时，针对实际应用中可能出现的当实际网络中出现例如电磁干扰、辐射危害，或者其他虽然两点之间仍可以通讯，但现实要求数据分组不能经过这两点之间传播的特殊情形。如何增加适当的权重，从而令算法能够选择更合适的转发路径。仍然是一个有待研究的问题。

［1］ 张衡阳，李莹莹，刘云辉.基于地理位置的无线传感器网络路由协议研究进展［J］.计算机应用研究，2008，25(1):18－21.

［2］ Brad Nelson Karp.Geographic Routing for Wireless Networks［D］.Harvard University，2000.

［3］ Prosenjit Bose，Andrej Brodnik，Svante Carlsson，et al.Online Routing in Convex Subdivisions［C］//ISAAC 2000.Berlin Heidelberg:Springer-Verlag，2000，47－59.

［4］ Brad Karp，Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks［C］//ACM/IEEE MOBICOM，Boston，ACM Press，2000.243－254.

［5］ Fabian Kuhn，Roger Wattenhofer，Yan Zhang，et al.Geometric Ad-Hoc Routing:Of theory and practice［C］//PODC 2003，Boston，Massachusetts，2003.63－72.

［6］ Ben Leong.Geographic Routing Network Simulator［EB/OL］.2004.http://web.mit.edu/benleong/www/netsim.

［7］ Ben Leong.New Techniques for Geographic Routing［D］.Massachusetts Institute of Technology，2006.

［8］ 毛科技，赵小敏，宦若虹，等.基于散列值的以数据为中心路由协议［J］.传感技术学报，2010，23(9):1308－1316.

［9］ 刘铁流，巫咏群.基于能量优化的无线传感器网络分簇路由算法研究［J］.传感技术学报，2011，24(5):764－770.

［10］杜群，李伟华，蒋卫华.一种适用于无线自组织网络的安全路由优化算法［J］.传感技术学报，2010，23(3):447－452.

［11］ Ozawa T，Takahashi H.A Graph-Planarization Algorithm and Its Application to Random Graphs［J］.Graph Theory and Algorithms，1981，108:95－107.

［12］路纲，周明天，牛新征，等.无线网络邻近图综述［J］.软件学报，2008，19(4):888－911.

［13］ Kin Yin Li.Convex Hull［J］.Mathematical Excalibur，2007，12(3):1－4.

［14］ Young-Jin Kim，Ramesh Govindan，Brad Karp，et al.Geographic Routing Made Practical［C］//Proceedings of the 2nd conference on Symposium on Networked Systems Design ＆ Implementation.Boston:ACM Press，2005，2:217－230.