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

第 2 5卷 第 7期 2 0 1 2年 7月 传 感 技 术 学 报 C HI NE S E J O UR NAL O F S E NS OR S AND A C T UA T OR S Vo 1 2 5 No 7 J u 1 2 0 1 2 Th e De s ig n o f Ge o g r a p h ic a l Ro u t in g Al g o r it h m Ba s e d Hu l l Tr e e a n d Gr e e d y MA O Z H A O X ia o m in Y I J u n y a n X I A Min g L E I Y a n g W A N G Y a o C H E N Q i n z h a n g D e p a r t m e n t o f C o m p u t e r S c i e n c e a n d T e c h n o l o g y Z h i a n g U n i v e r s i t y of T e c h n o l o g y H a n g z h o u 3 1 0 0 2 3 C h i n a Abs t r a c t Ge o g r a p h ic a l r o u t i ng a l g o r it hm wit h t he a id o f t h e n o d e S g e o g r a p hi c a l p o s i t io n c a r r y o u t t he r o u t e d is c o v e ry a n d t h e d a t a f o r wa r d e d i n wir e l e s s s e ns o r n e t wo r k s Th is p a p e r pr o p o s e s a n a pp r o a c h o f g r e e d y g e o g r a ph ic r o u t in g a l g o r i t h m b a s e d o n H u l l t r e e G r e e d y H u l l T r e e G e o g r a p h ic R o u t in g G H T G R B y u s in g t h e c o n c e p t s o f c o n v e x h u l l in Gr a p h ic s di s t r i b ut e d e s t a b l is h in g Hu l l t r e e o n e a c h n o d e t o e x p l o r e l o c a l n e t wo r k t o po l o g y i n i t s in it ia l s t a g e I n t h e da t a f o r wa r d in g s t a g e b y s e a r c h in g in Hu l l t r e e t o l o o k f o r t h e n e x t ho p f o r wa r d i ng n o d e a n d c o mp l e t e t h e d a t a pa c k e t t r a n s mi s s io n S imu l a t io n e x p e r ime n t s s h o we d t h a t c o mp a r e d t o t h e e x is t in g g e o g r a p h ic a l r o u t i ng a l g o ri t h m GHTHR is a b l e t o c o r r e c t l y find d a t a f o rw a r d in g p a t h e f f e c t i v e l y r e d u c e e n e r g y c o n s u mp t io n a n d i mp r o v e t h e n e t wo r k t r a n s po r t p e r f o r ma n c e Ke y wo r ds g e o g r a p h ic r o u t in g c o n v e x hu l l Hu l l t r e e g r e e d y f o r wa r d i ng r ul e E E AC C 6 1 5 0 P 7 2 3 0 d o i 1 0 3 9 6 9 j is s n 1 0 0 4 1 6 9 9 2 0 1 2 0 7 0 2 6 采用 H u l l 树 的贪婪地理位置路 由算法 的设计 术 毛科技 赵小敏 衣俊艳 夏 明 雷艳静 王 尧 陈庆章 浙江工业大学计算 机科 学与技术学院 杭州 3 1 0 0 2 3 摘 要 地理位置路由算法是指借助节点获得的地理位置信息进行无线传感网络中的路由发现与数据转发工作 本文提出 一 种基于 H u l l 树的贪婪地理位置路由算法 G r e e d y H u l l T r e e G e o g r a p h i c R o u t in g G H T G R 通过图形学中凸包的概念 在 网络初始 阶段 分布式地在各节点上建立 H u l l 树 以探查 网络局部拓扑结构 同时在数据分组的路 由转发 阶段 通过 H u l l 树内的 搜索 寻找下一跳转发节点 完成数据分组的转发传输 通过仿真实验表明 与现有地理位置路由算法相 比 该算法能够正确 地寻找数据转发路径 有效地减少网络能耗 提高网络传输性能 关 键词 地理位置路由 凸包 H u l l 树 贪婪转发策略 中图分类号 T P 3 9 3 文献标识码 A 文章编号 1 0 0 4 1 6 9 9 2 0 1 2 0 7 1 0 0 7 0 7 无线传感 网络在森林 监测 气候监控 军事 战 场 数字城市方面有广泛的应用前景 在诸多应用 领域 中 不仅要求随时获取 目标的一些物理量数据 还要求得到 目标的地理位置 由此推出很多 WS N定 位技术 随着无线传感网络应用深人 很多应用不 仅要求携带地理位置信息 还要求数据能够根据地 理位置信息向特定 的地理位置转发 节点接收 由特 定地理位置传来的信息 数据沿着特定 的地理路径 传递 为 了满足这些应用需求 人们需要研究依靠 节点的地理位置信息来进行报文转发与数据寻路 的 路 由技术 这就是所谓基 于地理位置 的路 由协 议 地理位置路由协议一般可以分为使用地理位置信息 进行辅助路由寻路的路 由协议与基于地理位置信息 的路 由协议 两类l 1 后 者又可 以按其 主要 实现方 式不 同分为定 向区域泛洪 贪婪路 由算法和分层路 由算法等路由协议 基于贪婪路由算法的地理位置路由协议是 目前 研究 比较深入的一类地理位置路 由协议 此类协议 是在贪婪路由转发策略 的基础上 通过各种方法改 进其寻路表现 简单 的说 贪婪路 由转发策略就是 转发节点将数据传给离 目的节点更近的节点 地理 位置中的贪婪路 由算法主要面临的问题是如何解决 项 目来 源 浙江省教育厅项 目 Y 2 0 1 1 2 0 1 2 1 浙 江省公 益性技术应用 研究计 划项 目 2 0 1 1 C 2 1 0 1 4 浙江省 自然科学基 金项 目 Y1 1 1 0 6 4 9 Y1 1 0 1 0 6 2 Y 1 2 F 0 2 0 1 7 7 Q 1 2 F 0 2 0 0 8 7 浙江省钱江人 才计 划项 目 2 0 1 1 R 1 0 0 8 7 同家 自然科 学基金 项 目 6 1 0 0 1 1 2 6 收稿 日期 2 0 1 2 0 2 0 1 修改 日期 2 0 1 2 0 5 0 8 1 0 08 传感技术学报 W W W c h in a t r a n s d u c e r s c o n 第 2 5卷 由于实际节点布设位置不均匀而导致的网络拓扑结 构 中空旷域 V o id s 2 1 引起的路由转发失败的情况 为了解决这一问题 学者提出了一系列 的路 由算法 G F G g r e e d y f a c e g r e e d y 算法l 是最早提 出了采用 G G图 G a b rie l g r a p h 来平面化网络 图 从而在贪婪 路由寻路失败时使用 f a c e r o u t in g的寻路方法来继 续转发报文 的贪婪路 由协议 G P S R协议 l 4 采用类 似的方法 但是 由于在 网络的平 面化 以及寻路方式 细节方面的改变 使得 G P S R协议得到了更好 的性 能表现和实用性 从而成为在地理位置路 由领域最 为认可的协议之一 文献 5 6 提出了 f a c e r o u t in g 的寻路何时切换回贪婪路 由寻路 并在得 出切 换的 最佳 时机 上开 发 出了 G O A F R G r e e d y a n d O t h e r A d a p t iv e F a c e R o u t in g 与 G O A F R 路 由协议 MI T 的 B e n L e o n g 提 出了 G D S T R和 G S p r in g 算法 7 J 还 有基于散列值的路由协议l 8 基于能量优化 的路 由 算法 9 通过改进蚁群算法的路由算法 等 所谓空旷域 是指在实际的无线传感网络中 不 管是人工的放置节点在固定的位置 还是撒播 总会 遇见某些地方是节点无法存在的区域 或者是位于 此地的节点无法正常工作的区域 比如沼泽 湖泊 大河 高楼 具有强电磁 干扰 的地方 等 即使是均匀 的放置 也会由于网络 中某些节点 因为断 电或异 常 等情况失 效 从 而在 网络 中形成 大 小不 等 的 空 洞 在这些空洞 内部 没有节点来进行数据分组 的接力转发 在实际的路 由过程 中 往往需要绕过 这些空洞来转发数据 正如 图 l所表示 的那样 转 发节点 X 无法找到比自己距离 D点更近的节点 然 而确实存在这样 的一条路径 W V 可以使报文得 到顺利的转发 这时原有 的贪婪转 发策略就失败 了 需要新的方案来解决这一问题 图 1 至日 厂 域 V o i d 本文借用图形学上 凸包 c o n v e x h u l 1 的概念 结合原有的贪婪转发策略 提出了 G H T G R G r e e d y Hu l l T r e e G e o g r a p h ic R o u t in g 算法 这是一个面 向 无线传感 网络 的分布式地理路 由算 法 通过 H u l l 树 它构建一个 以本地节点为 中心的多层次凸包结 构 用于描述节点周 围的局部网络拓扑结构 报文只 需在节点内部的 H u l l 树内进行搜索 从而获得数据 分组的转发路径 包括绕过空旷域的路径 实验 表明 本算法相 比于 G P S R算法 不仅能够正确地寻 找到数据分组的转发路径 同时在初始的报文交换 方面 尽可能地将报文交换局限在局部区域以内 有 效地减少 了全 网报文广播对 网络负载 与性 能的影 响 由于此算法只需得知局部 的网络拓扑结构 从 而比之于 G P S R算法灵活性与适应性更高 1 算法的构建 1 1 平面化 网络 拓扑结构 与 凸包 对于 G P S R算法中 f a c e r o u t i n g方法来说 得 以 运行的一个首要条件就是要构造一个平面图来描述 实际的网络拓扑 这样 的图须满足 网络拓扑结构 应当是平面化 的 1 平 面图中任意两边都 不相交 平面图中不存在不封闭的多边形结构 任何基于网 络拓扑结构进行寻路的路 由协议 首先要解决的问 题就是如何将现实的 由节点之 间的通讯关 系所形 成的网络拓扑记录下来 并经过某种算法的处理 形 成节点可以识别 处理 存储 的平面图形结构 常用 的网络拓 扑 图l 1 的方 法有 U D G u n it d is k g r a p h 图 最小 生成树 MS T R N G图 R e l a t iv e N e ig h b o r G r a p h 与 G G图 G a b r ie l G r a p h 凸包 C o n v e x H u l 1 3 是这样的一个图形 给定 平面上的一个 有限 点集 即一组点 这个点集的 凸包就是包 含点集 中所有点 的最小面积的 凸多边 形 最小面积 这个 限制条件 保证 了凸包的唯一 性 因为除了凸包以外 还有无限多个包含点集 中所 有点的凸多边形 例如 只要画一个 面积足够大的 四边形 便可包围任意给定的点集 因此假如没有 这个限制条件 求凸包就变成非常容易但却没有 唯 一 解的运算 它的数学描述如下 在一个实数向量空间 中 对于给定集合 所 有包含 的凸集 的交集 S被称为 的凸包 S n K K V K i s C O n V e X 的凸包可以用 内所有点 一 的线性组合 来 构造 5 0 f I x j X 0 1 0 E o 1 1 J 1 在路由算法 中 凸包一般被应用于如下的场合 当节 点分布 比较密集时 逐个比较每个节点到 目标区域的 前进距离所需要的计算开销很大 而凸包是一个节 点集合中处于 外 围 的节点连线构成的凸多边形 当转发节点计算报文转发路径时 只需要 比较凸包上 1 01 0 传感技术学报 B r w g c h i n a t r a n s d u c e r s c o n 第 2 5卷 况下转人 2 第 种情况下转入 3 2 节点 P收到 H u l l 树构 建命 令 报文 H u ll b u i ld m e s s a g e 表示在这个局部范围内未构建 H u ll 树 于是 P首先 以 自己为根节点 接受足够数量 的 邻居 返 回报文 之后 建 立本 地 Hu ll树 并将 自身 H u ll树向邻居 节点广播 在 这个过程 中可能会 出 现以下两种情况 p节点只收到了返回的 H u l l树 构建命令报文 此时说 明 P的邻居节点 中都未构建 Hu ll 这时 P依据邻居节点的 H u ll 树构建命令报文 构建的 H u l l必然是一个一层无子树的 H u ll树结构 p节点收到的所有报文中 既有返 回 H u l l 树构建 命令报文 也有返 回的 Hu ll树报文 此时对 P来说 同样是先根据这些报文构建本地 Hu ll树 同时判断 哪些返回 H u ll树报 文的邻居节点是否是本地 H u ll 树 的子节点 如是 则将其 H u ll树添加进本地 H u ll 树 如否 则抛弃 3 节点 P收不到任何反馈报文 这说 明 P没 有任何邻居 此时建立的 H u u是一个仅有 以 P为根 节点的树 这个过程中 节点通过接收邻居节点的报 文 从中选择符合要求的 H u l l 树上 的 凸包上的 节 点加入 自身的 H u l l 树中 同时 通过交换初始报文 也很容易地为每个子节点添加上属于它 的 h u ll树结 构 网络初始时的 H u ll树构建过程 是一个较为漫 长的过程 在这个过程 中 节点要一直等待邻居节点 发来 的各类 报文 根 据 H u l l 树 构建算 法对 自身的 H u ll树进行修剪 再将 自身 的 H u ll树 向邻居节点广 播 本算法中采用包裹法构建 H u ll树的算法如下 算法 1 包裹法构建凸包 标记 p节点所有邻居节点 的链表 L i s t N1 N 2 N 3 N i 其中 N i 由节点标志与位置信息 x Y构成 存储凸包结构 H u llT r e e n o d e s St e p 1 W fi n d NI Y ma x L i s t Q fi n d Nl Y ra i n L i s t P u t W Q i n t o Hu l lT r e e t h e l i n e WQ d i v i d e t h e f a c e i n t o le f t a n d r i g h t f a c e S t e p 2 Ope r a t e n o d e s i n le ft f a c e lo o p W a s s t a r t no d e ma k e r a d i a ls f r o m W t o a n o t he r n o d e i n l e ft f a c e C h o o s e M M是与 X轴负方向夹角最小的射线的终点 M W b r o t he r W M C o n t i n u e u n t i l t h e W i n t o Hu 1 1 T r e e S t e p 3 Op e r a t e n o d e s i n r i g h t f a c e l o o p Q a s s t a r t n o d e ma k e r a d i a l s f r o m Q t o a n o t h e r n o d e i n le ft f a c e c h 0 o s e M M是与 X轴正方向夹角最小的射线 的终点 M Q b r o t h e r W Q C o n t i n u e u n t i l t h e Q i n t o H u ll T r e e 在完成了 H u l l树的构建工作之后 在整个路 由 算法运行过程之中 需要不停地依据实际情况维护 各节点上 H u ll树 一般有 如下三种情况并采取相 应的措施 新节点的加入 这种情况下 可以根据 以上 H u l l 构建阶段的方法 为节点构造 H u ll树 并 将其信息通知到各 个邻居节点 节点移动或者从 暂时的休眠中恢复 在这种情况下 节点仍保存有 原有 的 H u ll树 但 此时的 H u l l 树信息可能 已经过 时 应当重新发出查询请求报文来取得新位置下 邻 居节点的位置及其存储的 H u l l树信息 通过对 自身 原有 H u ll树的对 比 修正 自生 H u l l树 节点的离 开 节点为它的每个邻居节点设立一个时间阈值 这一阈值也是节点和它邻居节点进行信息交换的周 期 当节点在下一周期向某个邻居节点发出信息交 换请求而在限定时间 内未收到 回应时 将删去 自身 Hu ll树 中以这个邻居节点为根节点 的子树 并广播 自身状态信息 2 2 数据分组转发 阶段 当源节点 S 产生一个需要发往 目的节点 t 的数 据分组 M 时 它会为数据分 组添加上文 所述 的报 头 并将路由转发模式 R O U T E MO D E 设为初始的 T r e e模式 然后根据报文模式与节点 自身 的状态信 息 来判断下一步应采取的动作 同样 中间节点 v 收到由源节点 s 邻居节点 W发来 的目的节点 t 的报 文 M 也会检查报文中所标记 的路 由转发模式 进而 根据相关信息 自身 H u ll树 以及 目的节点 自身节 点的位置信息 选择下一步的行为 在此我们假设某一中间节点 v 收到由源节点 S 邻居节点 W发来的 目的节点为 t 的报文 M 具体来 说 报文在发送过程中 由于转发模式的不 同 大致 有以下几种情况 首先 节点 v检查 自身是否为报文 M的 目的节 点 若是 则接收报文并停止报文的转发 若否 则 检查是否是报文中 P N O D E域所表示的中间 目的节 点 若是 按照报文中所载的节点转发序列 向下一 跳节点转发报文 若否 则进入模式检查 检查报文 转发模式 1 T r e e 模式下 v 搜索 自身的 H U L L树 首先判断 目的节 点是 否是 v的邻居节点 目的节点是否在 H u ll树根节点 的直接子节点所构成 的凸包范围以内 若是 则 直 接广播报文即可 否则 判断 目的节 点 t 是否存在 v 第 7期 毛科技 赵 小敏等 采用 H u l l 树的贪婪地理位置路 由算法的设计 1 0 1 1 的 h u l l 树的子树所形成的凸包中 如果是 则将 v到 该子树根节点在 v的 Hu l l 树 中查找 的节点序列 作 为报文的转发路径 添加到报头的 P N O D E域 中 其 中 I D和 L o c a t i o n为子树根节点 的标识 与位置 t r a c e 域存储节点序列 然后转发报文到下一节点 否则设 报文模式为 T r e e G r e e d y 2 T r e e G r e e d y 模式下 节点搜索存储在本地 的 H u l l 树 选择其 中距离 目的节点位置最近的子节点作为报文在本模 式下所 传输的目的节点 其中从根节点到此叶子节点在 H u l l 树中查找到的节点序列 即为此报文的转发路径 这 一 模式采取的转发方式同单纯的贪婪法很像 都是寻 找距离 目的节点最近的节点 不 同的是 一般的贪婪 法是在邻居节点中寻找距离 目的节点更近的节点 然 而在本算法 中 是在节点本地的 H u l l 树 中搜索距 离 目的节点最近的节点 由于节点 H u l l 树中存储 的是 一 个局部网络拓扑 因此所查找到的转发路径就可以 保证数据分组被传递出更广的范围 同时 贪婪法需 要 比较 目的节点同中间转发节点的所有邻居节点的 距离 并从中选择距离 目的节点最近 的邻居节点 而 且在每经过一个节点时都需要做这样的比较 然而本 算法中只需判断是否在 H u l l 树 中规划的凸包 以内即 可 并在到达某个中间转发节点时才需要做位置比较 工作 大大提高了运行效率 3 G r e e d y 模式下 报文进人 G r e e d y 模式 就意味着数据报文在转 发时进入到了算法中止情况 算法 中止存在三种情 况 目的节点 的地理位置处于网络覆盖范围以内 网络中不存在 目的节点 此时 报文 已转发到某一 节点 q q对报文检查时发现 目的节点在其本地凸包 内 只需广播发送报文即可 然而广播此报文不能得 到回应 或者说 目的节点不存在 此时只需简单地丢 弃报文即可 当然 如果对路 由协议做可靠性扩展 可以要求 q向源节点返 回报文转发 失败 的信息 节点为网络 图的局部达到顶点 在这种情况下 报 文到达 的节点 v 将是网络拓扑的某个局部顶点 在 v自身的 H u l l 树中无法查找到 比 v距离 目的节点 t 更近的节点 当协议规定 v只存储一层 的 Hu l l 树 时 那么 H u l l 树就没法涵盖到 比 v节点距离 目的节 点更近的节点 X 显而易见 这是一 个 比较大 的空 旷域 如果增加节点中 H u l l 树 的层数 就可以增加 H u l l 树的覆盖范围 直至覆盖到一个 比当前节点更 靠近 目的节点 的转发节点 当然 这里既然出现了 空旷域 那么采用边界转发策略 同样也可以解决 问 题 目的节点的地理位置处于网络覆盖范围以外 出现这种情况 意味着 目的节点在网络之外时 数据 报文到达了整个网络的边缘 的某个节点 这个节点 相 比于网络 中其他节点 距离 目的节点最近 并且 显然 此时报文所在节点是它 H u l l 树中凸包上的节 点 并非位于凸包 的中心 在这种情况下 路由协议 简单地标记此报文的 目的节点不可达即可 3 算法仿真与分析 本论文基于 MA T L A B 7进行路 由算 法 的仿真 网络模 型为在一个覆盖 区域为 1 0 0 X1 0 0范 围内随 机生成由 5 0到 5 0 0数量不等节点组成 的网络 为 了保持网络通讯在节点密度较大时 不会 由于节点 通讯距离过长从而导致路径选择过早地拟合成为贪 婪法下的最优路径 因此随着网络节点密度的增大 将适当地减小节点间的通讯距离 节点分布图 a H u l l 树形状 节点路径转发 图 5 网络 中 的 Hu l l 树 结 构 以 及 算 法 两 点 路 由寻 路 路 径 图 5表示了一个面积为 1 0 0 x 1 0 0的网络区域 内 随机分布了 1 5 0个节点 每个节点的通讯距离为 1 5 单位的网络分布 图 5 a 表示出了初始化完成时 从全网络选 择某几个 节点 表现 出的 H u l l 树结构 当然 即使是选取的几个节点 也没有表现出它们所 有的 Hu l l 树结构 只是有 选择地 选取若 干子节 点 H u l l 树表现出来 图5 b 中实线线条表示 G H T G R 算法在运行时一次具体的路径转发 虚线线条表示 G P S R算法在相同节点下的转发路径 由图 5 b 中 可以看出 大多数情况下实线线条覆盖了虚线线条 这表示 G H T H R算法与 G P S R算法寻找到的转发路 径是一致的 由于 G P S R算法同样是以贪婪策略为 1 01 2 传感技术学报 W W W c h i n a t r a n s d u c e r s e o m 第 2 5卷 基础 的路 由转发 一般情况下 在贪婪模式下两算法 选择下一跳转发节点的差异不会很大 具体的差异 表 现在 G H T G R算法 在 H u l l 树查 询方 面 可能在 T r e e G r e e d y模式下 出现 H u l l 树第一层 的某子节点 的凸包上 的点 即 H u l l 树的第 2层 比其他子节点 凸包上 的点更 靠 近 目的节 点 然而 此 子节 点 在 H u l l 树第一层中 并非距离 目的节点更近节点 于 是 G H T G R算法会直接选择底层距离 目的节点最近 的孙子节点 在只有两层 的 H u l l 树结构 中就是第二 层 将根节点到此子节点的路径作为转发序列 而 不像 G P S R算法那样直接选取邻居节点中距离 目的 节点更近的节点 如图 6所示 当节点密度少于 1 2 0时 G H T G R算 法所采用的转发次数 比G P S R算法稍高 这是由于节 点密度很低时 网络中的空旷域 的面积会很大 而此 时 G P S R算法只要沿着空旷域的边缘来走 就会是最 短路径 G H T G R算法在 H u l l 树 中的搜索 或许会偏 离一到两次空旷域的边缘 因此转发次数稍多 随着 节点密度的增大 G H T G R算法的平均转发次数降至 了 G P S R的曲线 以下 说 明此 时 G H T G R 比 G P S R算 法更 能寻找到更短 的转 发路径 这 通常是因为在 G H T G R算法中 数据分组直接被送往凸包上的点 避 免了在节点直接通讯范围内的多次转发 当节点密 度增加到空旷域可以忽略不计时 即每个节点的直接 通讯范围内都可以找到符合贪婪法策略的下一跳节 点 G H T G R与 G P S R算法就向 G R E E D Y算法靠近 接 近于最短路径算法 从 图形上来看 G H T G R算法与 G P S R算法在路径转发次数 即路径选择 方面的差 距不是很大 这说明每个算法基本上都找到一条与节 点之间实际最短路径相近的路径 糕 蜱 图 6不 同算法节点转发 次数 比较 图 7表明了网络初始化时 G P S R算法形成网络 整体平面图所花费资源与 G H T G R通过交换报文形 成局部 H u l l 树所耗费资源的对比情况 具体的报文 转发数量受 限于网络通信 M A C层所使用的具体协 议 在这里我们衡量的报文数为节点向外广播它的 状态信息的报文数 实验表明 采用 G H T G R算法的 初始报文交换数量远远低于 G P S R算法的报文交换 数量 这是因为 G H T G R算法不要求每个节点获得 整个网络所有节点的平面化拓扑结构 从而将大多数 的报文局限在一跳或者两跳的范围之内 不会类似于 G P S R算法进行全网规模的数据报文交换 轻 餐 图 7 单位 区域 中不同节点密度报文转发数量 图 8表示了不同空旷域数量下的路 由路径选择 情况 可以看 到 当图中空旷域数量较小时 G P S R 算法所寻找到的转发路径与 G H T G R算法寻找到的 路径差不多 然而随着空旷域 的数量增多 G P S R算 法寻找路径的跳数 比 G H T G R算法的路径跳数增长 更快 这表明 随着空旷域的增加 在 G P S R算法寻 路过程中 数据报文仅仅依赖于空旷域 的边界转发 措施 导致数据分组的转发路径序列不一定会是到 达 目的节 点 转 发 的最 短 路 径 序 列 然 而 由于 G HT G R算法采用 了 H u l l 树 的搜索 当空旷域足够 小时 本地节点 H u l l 树 中所 寻找到 的节点 转发序 列 就 可 能 会 绕 过 此 空 旷 域 仿 真 结 果 表 明 G H T G R算法确实在多空旷域的数据寻路过程中 相 对于 G P S R算法找到了更好的转发路径 5 0 鳖 4 6 豁 淫4 2 3 8 3 4 3 O 0 2 4 6 8 l 0 空旷域数量 图 8 不 同空旷域数量 下节点转发路径跳数 4 总结 仿真实验表 明 相 比于 G P S R算法 G H T G R算 法在保证寻路正确性的基础上 较大地降低 了算 法 用于初始化网络拓扑结构所进行报文交换 的数量 当节点密度较大时 该报文交换被局限于局部范围 以内 不会引起报文的全 网广播 有效地限制了报文 增长的幅度 其 次 在 网络空 旷域 较多的情况下 第 7期 毛科技 赵小敏等 采用 H u l l 树的贪婪地理位置路 由算法的设计 1 0 1 3 G H T G R算法对路径的选择同样优于 G P S R算 法 这 是 由于规避了 G P S R算法引起的在空旷域边沿频繁 的模式切换 未来对于 G H T G R算法来说 如何与 地理 区域 广播 G E O C AS T 结合起来 进一步扩展地理路由算 法的使用范围 同时 针对实际应用 中可能 出现 的 当实际网络中出现例如电磁干扰 辐射危害 或者其 他虽然两点之间仍 可以通讯 但现实要求数据分组 不能经过这两点之间传播的特殊情形 如何增加适 当的权重 从而令算法能够选择更合适的转发路径 仍然是一个有待研究的问题 参考文献 1 2 3 4 张衡 阳 李莹莹 刘 云辉 基 于地理 位置 的无线传 感器 网络路 由协议研究进展 J 计算机应用研究 2 0 0 8 2 5 1 1 8 2 1 B r a d N e l s o n K a v p G e o g r a p h i c R o u t i n g f o r Wi r e l e s s N e t w o r k s D Ha r v a r d Un iv e r s it y 2 0 0 0 P r o s e n j i t B o s e A n d B r o d n i k S v a n t e C a r l s s o n e t a1 O n l in e R o u t i n g i n C o n v e x S u b d i v i s i o n s C I S A A C 2 0 0 0 B e r l i n He id e l b e r g S p ri n g e r Ve r l a g 2 0 0 0 4 7 5 9 Br a d Ka r p Ku n g H T GP S R Gr e e d y P e r ime t e r S t a t e l e s s Ro u t in g f o r Wi r e l e s s N e t w o r k s C A C M I E E E MO B I C O M B o s t o n A C M 毛科技 1 9 7 9 一 男 汉族 浙江 T业大 学计算机科学与技术学院助理研究员 博 士研究生 主要 研究 方 向 无线传 感 网络 数据挖掘 m a o k e j i z j u t e d u c n Pr e s s 2 0 0 0 2 4 3 2 5 4 5 F a b i a n K u h n R o g e r Wa t t e n h o f e r Y a n Z h a n g e l a 1 G e o m e t r