收 稿日期 : 2008-10-31; 修 回日期 : 2008-12-15 基 金项 目: 国 家自 然科学 基金 资助项 目( 60773208)
作 者简介 : 李蕊( 1980- ) , 男 , 湖南湘 乡人, 博 士, 主要研 究方 向为无 线网 络、普适计 算( hnlirui@ 163. net) ; 张焱( 1983- ) , 男, 硕士, 主要 研 究方 向
为无线 网络; 李 仁发( 1957- ) , 男 , 教授, 博导 , 主 要 研究 方 向 为 无线 网 络、嵌 入 式 计 算、数 字 媒 体 ; 李 永 亮 ( 1982- ) , 男 , 硕 士, 主 要研 究 方 向 为 普 适
计算.
基 于 DHT 策 略 的 MANETs 网 络 路 由 协 议 研 究
*
李 蕊, 张 焱, 李仁发, 李永亮
( 湖南大学 计算 机与 通信 学院 , 长沙 410082)
摘 要: 提出了一 种分 布式 MANETs 路由 协议 , 该 协议 综合 了基 于 DHT 的应用路 由协 议 Tapestry 和网络 层路 由
协议 AODV 的 优点 , 使用随 机路 标算 法对 网络 进 行 分簇 , 改 进 了 Tapestry 算法 使 其 在 分 簇 内 节 点间 共 享 对 象 指
针。 仿真实 验表 明本 协议 可以 有效 避免 覆盖 层与物 理层 匹配 失效 的问 题, 在节 点移 动速 度较 快时 仍 能 保持 较 高
的路 由查 找成 功率和 较低 的网 络开 销。
关键 词: 移 动自 组织 网络 ; 随 机路 标算法 ; 分 布式 哈希 表; 对 等网 络
中图 分类 号: TP393. 04 文献 标志 码: A 文章 编号 : 1001-3695( 2009) 07-2691-04
doi: 10. 3969/j. issn. 1001-3695. 2009.07.082
Research on DHT-based routing protocol for MANETs
LI Rui, ZHANG Yan, LI Ren-fa, LI Yong-liang
( School of Computer & Communication, Hunan University, Changsha 410082, China)
Abstract: This paper proposed a distributed MANETs routing protocol, which combining both the advantages of DHT-based
protocol Tapestry and AODV, clustering the network with random landmarking, improved Tapestry to make it share object
pointers between clustered nodes. Simulation experiments show thatthe proposed protocol could effectively avoid the mismatch
problemof overlay and physical layer. It can reach a high success ratio of objectsearch and maintain alow-cost network in spite
of a quick node speed.
Key words: mobile self-organizing networks( MANETs) ; randomlandmarking; DHT; peer-to-peer( P2P)
对等计算( P2P) 作为一种典型的 分布式计算 技术, 由 于无
集中控制点, 可避免 C/S模型的 服务器 瓶颈等 问题, 成为分 布
式计算技术的研究热点。P2P 所追求的 是一 个自 由的 互联 网
环境, 满足不同用户之间直接进行信息交换的要求。作为一种
广泛应用且被验证为高效的计算模型, 它亦可作为无线网络的
底层支撑技术。近年来 P2P 网络中提 出了一 些典型 的结构 化
算法, 如 Chord
[ 1]
、Pastry
[ 2]
、Tapestry
[ 3]
、CAN
[ 4]
等, 这 些算 法 均
引入了分布 式哈 希 表 ( distributed hash table, DHT) 思 想, 主 要
是因为分布式哈希表算法具 有平衡 性、单调性、分散 性和负 载
均衡等优势。DHT 的 核心 思想是 通过 将存 储对 象的 特征 ( 关
键字) 经过 哈希 运 算 得到 键 值, 依 据 键 值对 对 象 进 行 分 布 存
储。P2P技术广泛应用于内容发现 /定位、分布式 存储、协 同计
算等诸多分布式系统中。系统的实现方法是在 Internet应用层
上构建 DHT覆盖层, 作为 一个支 持层为 上层 应用 提供 路由 服
务。然而这些 P2P算 法 都是 为有 线 网络 设 计的, 几 乎不 考 虑
底层的物理路由过程和物理的拓扑结构。
移动应用环境逐渐成熟, 使研 究者关 注于分 布式更 强、参
与性 更 广、更 具 有 对 等 自 治 特 征 的 无 线 移 动 自 组 织 网 络
[ 5]
( MANETs) 。现在的 MANETs 网 络中 较为 广泛 应用 的路 由 协
议如 AODV
[ 6]
、DSR
[ 7]
等对分布式应用的 支持还不够。通 过研
究 MANETs 网络和 P2P网络可以发现两者拥 有一些 关键的 共
同点: 都要定位 和发现服务, 都是 自组织的、分布式的, 节点 既
是服务器, 又是客户端, 且 MANETs 网 络中的 节点还 担任路 由
的角色; 同时两者都面临相 同的基 础问题, 即 节点之 间的连 接
性检测和路由表 的更 新 等, 而对 两 者的 研究 却 被极 大地 分 开
了。由于 MANETs 网 络 的 广 泛 应 用 及 其 诸 多 优 点, 使 得 在
MANETs 网络中建立分布式系统变得非常有价值和 意义, 而 用
分布式哈希表( DHT) 来建立分布式应 用的方 法已经 被广泛 地
证明了。因此, 如何在 MANETs 中有 效地构 建 DHT 覆 盖层 成
为一 个新 的研 究工 作。将 P2P 应 用在 MANETs 中, 可 以减 小
移 动特性 对 MANETs 路由 的影 响, 有助 于增 强节 点之 间的 实
时通信
[ 8]
。但是 由于 MANETs 网 络与 因 特网 在 路由 协议、节
点 稳定 性、带宽 限 制 和能 量 限 制等 诸 多 方面 的 差 异, 使 得 在
MANETs 网络中实现 DHT覆盖层要更多 地考虑 MANETs 网 络
自身的特性。
1 相关研究
文献[ 9] 中提出了两 种将 DHT 与 MANETs 网络 结合的 方
法: a) 直接将 DHT应用在 MANETs网络之上, 类似于传统的将
DHT应用在 Internet之上。由于 DHT 是为 Internet 设计 的, 直
接部署于 MANETs 网络之上有些 不合适: 首先, DHT 层产生 的
路由花销实际上是全部来自于物理层的流量, 其本身是没有开
销的, 并且由于 DHT是 针对 Internet 设计 的, 在构 建覆 盖层 的
拓扑结构时不用过多地考虑拓扑结构, 这样做可能会导致覆盖
层上相近的节点在物理上相距很远的现象, 即出现物理层与覆
盖层不一致问题。其次, 由于节点的移动性, 每一次 DHT覆 盖
第 26 卷 第 7 期
2009 年 7 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 26 No. 7
Jul. 2009