1、毕业论文文献综述 计算机科学与技术 自组网位置服务中基于哈希函数的位置分配和检索方法 一、前言 传统的网络是有中心且需要基础设施支持的，而 Ad Hoc 网络是无中心且无需基础设施支持的。对于一些特殊的环境或情况，如在大海上，我们就不可能建立基础设施来支持船舶通讯，而 Ad Hoc 网络的特点就可以很有效地解决这个问题。在未来， Ad Hoc 网络必定成为我们必不可少的网络。 在 Ad-hoc 网络中，由于节点是可移动的，所以对于节点的发现和选择是一个比较困难的问题。本文提出了基于哈希函数的位置分配和检索方法，目的是在位置 服务中利用哈希函数的特征来提高路由的发现和位置分配的效率。 二、 Ad
2、-hoc 网络相关概述 Ad-hoc 网络的主要特征：（ 1）独立性，（ 2）动态拓扑，（ 3）多跳通讯，（ 4）带宽受限、链路容量动态变化，（ 5） 节点功耗受限，（ 6）分布式特性，（ 7）生存周期短（ 8）有限的安全性和服务质量。 1,2 Ad-hoc 网络的关键技术：（ 1）信道接入技术，（ 2）路由协议，（ 3）网络体系结构，（ 4）QoS 保证，（ 5）广播和多播，（ 6）安全问题，（ 7）网络管理，（ 8）能耗节省机制。 2,3 Ad-hoc 网络的应用：（ 1）家庭 联网，（ 2）紧急服务，（ 3）传感器网络，（ 4）个人域网络，（ 5）军事无限通讯，（ 6）其他商业应用。 2
3、,4 三、 Ad-hoc 网络位置服务相关概述 在移动 Ad-hoc 网络中将遇到的最大难题：各个节点并不知道其它节点的位置，这与传统网络节点是固定的有很大区别，因此，在 Ad-hoc 网络中对于路由的发现和维护所产生的网络资源耗费将大于传统网络。但是随着信息技术的发展，全球定位系统（ GPS）也逐步成熟和完善，把这种技术加入到移动节点中，我们便可以准确的获取节点的位置信息，这十分有利于路由的发现和维护。 位置服务是一 类位置信息发布与查询机制，节点通过位置服务把自身位置信按照一定的方式发布到网络中，通过位置服务，节点可随时查询网络中其他节点的位置。在移动 Ad Hoc网络位置服务中，节点通过
4、 GPS 等方法获取自己的位置，位置服务来获取目的节点的位置，邻居节点的位置可通过一跳广播来获取。在 Ad Ho 网络中利用位置信息，可以使节点在寻找目的节点时避免简单的洪泛；利用相邻节点或目的节点的位置信息，可以提高路由寻找的效率。 5 常见的几种位置服务： Quorum 位置服务 5， ZHLS 位置服务 5， GLS 位置服务 16， DREAM 位置服务 17， GPSR 位置服 18， LAR位置服务 19。 移动 Ad Hoc 网络的位置服务可根据参与节点的数目分为四种类型：（ 1）部分节点参与的部分节点位置服务，典型代表是 Quorum 位置服务；（ 2）部分节点参与的全部节点位
5、置服务，典型代表是 ZHLS 位置服务；（ 3）所有节点参与的部分节点位置服务，典型代表是 GLS 位置服务；（ 4）所有节点参与的所有节点位置服务，典型代表是 DREAM 位置服务。 5 移动 Ad Hoc 网络的位置服务可根据基于位置信息的完全与否分为两类；（ 1）局部的基于位置信息的位置服务 ，如 LAR 和 DREAM；（ 2）完全的基于位置信息的位置服务，如 GLS 和 GPSR。7 虽然 Ad Hoc 网络中的这些位置服务都各有优点，但是也存在着不少的缺点，不过相比之下，我们可以发现 GLS 位置服务是一种比较好的位置服务，究其原因是因为在 GLS 位置服务中采用了哈希函数的特性来
6、分配节点。由于 Ad Hoc 网络无中心的特点也让我们不得不考虑以共享方式来获取资源，而这种方式正是对等网络（ P2P）的强项，并且我们获知在 P2P 网络中同样存在采用哈希函数的位置服务路由协议 Chord，这种环形的路由协议必定有着其不可小觑的高效性。在文献 9102021中有详细介绍这种位置服务路由协议。 四、 Ad-hoc 网络检索方法相关概述 在 Ad-hoc 网络中，对于节点的查找和路由的发现是比较困难的事情，寻找一种相对高效的检索方法是解决的这个问题的关键。本文将采用 P2P 网络中的 Chord 路由算法，以此通过环路优化检索方法，因为这种算法是结合了哈希函数特性的一种高效算法
7、。在 Chord 路由算法模型中，每个节点标识符和存储数据的关键字标识符将通过哈希运算分别映射成一个长度为 M 的二进制序列 NID 和 KID。在 M 位命名空间里，我们会 选取一些节点作为中心节点，它们是整个 Ad-hoc 网络的中心，这些节点兼有服务器和路由功能，它们既能存储信息也能转发信息，在环形网络中它们还将充当引导节点的作用，可以引导新节点的加入和退出，这样便能很好地适应 Ad-hoc 网络节点的频繁变化和路由表的快速更新。 节点和节点之间可以形成小环路，并选择其中一个节点作为该小环路的代理来存储该小环路的数据和信息，一个个小环路可以形成一个大环路，再找到代理，如此循环，直至所有节
8、点分配完毕。这就是我们所做的 结合哈希技术并通过环路来优化检索方法。当我们要进行查询时，节点首先 会询问自己所在环路的代理，如果没有目标节点，再访问上一级的环路代理，直至查询到目的节点或反馈查询失败的信息。 五、总结 现代无线网络和传统网络虽然高速发展着，但是它们仍需基础设施，在一些紧急状况和特殊环境下，它们根本无法发挥作用。比如船载通讯，在茫茫大海中，我们不可能建立基础设施来保持船只的通信；比如车载通讯，由于车载通讯网络的拓扑变化十分快，路由表更新频率快，维护困难。而 Ad-hoc 网络无需基础设施便能快速组建网络，而它的动态节点也需要良好的路由协议的支持来减少路由表更新时所产生耗费，于此同
9、时随着信息技术 的提高，全球定位系统（ GPS）可以帮助我们解决动态节点难定位的问题。因此， Ad-hoc 网络在未来必定可以发挥很大的作用，成为必不可少的一部分。 未来， Ad-hoc 网络的研究重点将会放在如何解决一些关键技术的问题上，只有解决了Ad-hoc 网络中遇到的一些关键技术， Ad-hoc 网络才能更好地发展。 参考文献 1 王海涛 .Ad Hoc 网络 .电信技术 ,2005 2 雷春娟 ,李承恕 .移动 Ad-hoc 网络及其关键技术 .电信技术 ,2002.12 3 朱亚静 .Ad Hoc 网络技术浅析 .价值工程 ,2008 第 11 期 4 方旭明 .移动 Ad Hoc
10、 网络研究与发展现状 .数据通信 ,2003 第 4 期 5 魏文彬 .移动 Ad Hoc 网络分布式位置服务研究 .2008.6 6 袁锦绣 .基于移动 ad hoc 网络服务发现的研究 .2007.6 7 张建 .基于位置信息的无线自组织网络路由技术的研究 .北京邮电大学 ,2007.3 8 沈长星 .基于地理位置的移动 Ad Hoc 网络路由协议研究 .北京邮电大学 ,2006.3 9 邹东尧 ,宋美娜 ,宋俊德 .一种基于物理网络拓扑的高效 Chord 模型 .计算机工程 ,2008.3 10 陈宏亮 ,李杰 ,王桃 .基于位置的层次式 Chord 模型 .计算机工程 ,2009.11
11、 11 王成 ,刘金刚 .Ad Hoc 无线网络及其路由协议分析 .计算机应用及软件 ,2006.8 第 8 期 12 刘元安 ,唐碧华 ,胡月梅 .Ad hoc 网络中的路由算法 .北京邮电大学学报 ,2004.4 13 沈军 ,曹元大 ,张树东 .移动 Ad Hoc 网络中基于预测及适时更新的位置信息服务 .北京理工大学学报 ,2005.12 第 12 期 14 袁锦绣 ,钱雪忠 ,王锦岭 .一种基于位置和 DHT 的移动 ad hoc 网络服务发现算法 .微电子学和计算机 ,2006 第 9 期 15 王志明 ,刘传情 .基于网格的 Ad hoc 网络混合位置服务算法 .信阳师范学院学报
12、 ,2009.4 16 Jinyang Li. A Scalable Location Service for Geographic Ad Hoc Routing.1998 17 Stefano Basagni,Imrich Chlamtac,Violet R.Syrotiuk,et al.a distance routing effect algorithm for mobility (DREAM).1998 18 Brad Karp,H.T.Kung.GPSR;Greedy Perimeter Stateless Routing for Wireless Networks.2000 19 Young-Bae Ko and Nitin H. Vaidya .Location-Aided Routing (LAR) in mobile ad hoc networks.1998 20 姜守旭 ,韩希先 ,李建中 .一种改进的 Chord路由算法 .计算机应用 ,2006.4 21 董芳 ,费新元 ,肖敏 .对等网络 Chord 分布式查找服务的研究 .计算机应用 ,2003.11
