1、毕业论文文献综述 计算机科学与技术 概率栅格移动预测模型在 Ad Hoc 网络中的应用 1 前言 随着科学技术的发展，网络特别是无线网络也迅猛的发展。由于无线网络相比于传统的网络具有十分快捷方便的特点，并且能在某些传统网络无法实现的特殊场合下进行数据通信，人们越来越倾向于使用无线网络并且对其进行了深入的研究探索。 目前，针对 Ad Hoc 网络己经开发出了基于不同策略的路由协议，将预测模型和节点的路由表变化相结合。大部分传统的 Ad Hoc 路由协议不考虑移动节位置信息，节点间的连接只能用图的形式抽象表示。本文在 利用基于四叉树算法在节点搜索方面做出了阐述和研究，并且通过简单的模拟实现了节点间
2、的搜索过程，相对于其他算法具有简单易懂的优点。 2 Ad Hoc 网络概述 Ad Hoc 网络是由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。移动终端具有路由功能，可以通过无线连接构成任意的网络拓扑，这种网络可以独立工作，也可以与 Internet 或蜂窝无线网络连接。 Ad Hoc 网络中，每个移动终端兼备路由器和主机两种功能 :作为主机，终端需要运行面向用户的应用程序 ;作为路由器，终端需要运行相应的路由协议，根据路由策略 和路由表参与分组转发和路由维护工作。在 Ad Hoc 网络中，节点间的路由通常是由多跳组成，由于终端的无线传输范围有限，两个无法直接通信的终端节点常常
3、通过 N 个中间节点的转发来实现通信，所以，它又称为自组织网、多跳无线网、对等网络或无固定设施的网络。 Ad Hoc 网络具备计算机网络和移动通信的特点，可以看作是一种另类的移动计算机通信网络。 3 基于位置的路由协议的基本理论 根据 Ad Hoc 网络的机制不同以及实现的原理不一样，一般来说 Ad Hoc 网络的路由协议可以分为两类 2：一类是基于拓扑结构的路由协议，另一类 是基于地理位置的路由协议。 基于拓扑结构的 Ad Hoc 网络路由协议是利用网络中的链路信息来进行报文的转发。这些路由协议又能分为表驱动型路由协议、按需驱动型路由协议和混合型路由协议 3。 与基于拓扑结构的路由协议不同的
4、是，基于地理位置的路由协议引入了每个节点的地理位置信息。每个节点都具备一个能获取自身地理位置信息的定位器，通过这些定位器不断更新移动中的节点的位置信息 4。每个节点周期性的向周围发送自己当前的状态、位置信息等的广播包，使得在节点信号所能覆盖的范围内通知他的相邻节点。这样所有的节点都能知道并记 录相邻节点的信息。当需要进行数据传输时，源节点只需要将目的节点的地理位置信息写入到数据包头部，通过定位服务首先确定目的节点的地理位置信息，然后更新数据报中的目的节点的位置信息，并且利用数据传输策略选择适合的节点进行转发传输，直到到达目的节点 5。 根据地理位置在路由协议中的应用一般可以分为两类 6：局部的
5、基于地理位置的 Ad Hoc网络路由协议和完全的基于地理位置的 Ad Hoc 网络路由协议。所谓局部的基于地理位置的Ad Hoc 网络路由协议就是在 Ad Hoc 网络路由协议中的某一过程中使用地理位置信息而不是在 所有的过程中一直使用。而完全的基于地理位置的 Ad Hoc 网络路由协议中，对于地理位置信息的运用则始终贯穿在路由协议的各个阶段 7。 4 移动预测 的概述 在基于位置的 Ad Hoc 网络协议中，每个节点都有自己的信息传播的范围，每个节点都能通过自带的获取位置信息的装置如 GPS9来获取自身节点的位置信息。在数据传输过程中，每个节点周期性的向周围发送自己当前的状态、位置信息等的广
6、播包，使得在节点信号所能覆盖的范围内通知他的相邻节点。源节点将目的节点的地理位置信息写入到数据包头部，通过定位服务首先确定目的 节点的地理位置信息，然后更新数据报中的目的节点的位置信息，并且利用数据传输策略选择适合的节点进行转发传输，直到到达目的节点。 Ad hoc 网络中节点的移动是完全可以预测的。在高斯马尔可夫行动预测模型中，移动节点的运动速率被看作时间上相关的高斯马尔可夫过程，并在此基础上推出了用于行动预测的所有参数的公式，进而可以预测节点的移动。 在这个过程中，只考虑目标节点和源节点的位置信息，而不考虑他们中间的间隔，到底是节点还是障碍物，也不需要他们中间节点的位置信息。 5 四叉树介
7、绍 在数据结构中，树形结构是一种很重要的非线 性数据结构。其中以树和二叉树最为常用。树是以分支定义的层次结构。在我们的客观世界中，树的结构普遍存在，如各类社会组织机构和人类的族谱都是以树的形式表示 16。 树的（ Tree）是 n(n 大于等于 0)个节点的有限集。四叉树（ Quad Tree）是一种树形结构，它的特点是每个节点至多只有四颗子树，具有栅格数据二维空间分布的特征。四叉树编码将整个图形区域按照四个象限分割成 2n*2n 象元阵列。四叉树形成过程是：将一个 2*2 的区域分解成大小相等的四个部分，每一个部分再分成大小相同的四个部分，这样一直分下去，直到分解到 需要的程度为止。 参考资
8、料 1David B. Johnson, David A. Maltz, Yih-Chun Hu. The Dynamic Source Routing Protocol for Mobile Ad Hoc Netvorks (DSR). Internet Draft,draft-ietf-manet-dsr-l0.txt. 19 July 2004 2S. Murthy and J.J. Garcia-Luna-Aceves. An Efficient Routing Protocol for Wireless Netvorks.ACM Mobile Netvorks and Applica
9、tions Journal. Oct. 1996. 3C. E. Perlixis and P. Bhagwat. Highly 街 namic destinationsequenced distance 一、ector routing(DSD for mobile computers. ACM Computer Communications Review. Oct. 1994. 4徐雷鸣，庞博，赵耀 .NS 与网络模拟，人民邮电出版社 .2003 年 11 月第一版 5郑少仁，土海涛，赵志峰等 .Ad Hoc 网络技术 .人民邮电出版社 .2005 年 1 月第一版 6方旭明，何蓉等 .短距
10、离无线与移动通信网络 .人民邮电出版社 .2004 年 8 月第一版 7土金龙，土呈贵，吴启晖，龚玉萍 .Ad Hoc 移动无线网络 .北京 :国防工业出版社， 2004. 8http:/www.ietf.org/html.charters/manet-charter.html 9朱华统 .GPS 坐标系统的变换 .测绘出版社 ,1994,75-89 10B.Krap and H.T.kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. Proceedings of the Sixth Annual ACM/
11、IEEE International Conference on Mobile Computing and Networking (MobiCom), Boston, USA, 2000:243-254 11秦政坤 ,王生生 .一种改进的区域四叉树空间搜索简易算法 .江西师范大学学报 ,2005,11 12江有福 ,吴伟志 .动态拓扑网络最短路径启发式算法 .计算机应用与软件 ,2008,5 13陈益富 ,卢潇 ,丁豪杰 .对 Dijkstra 算法的优化策略研究 .计算机技术与发展 ,2006 14江有福 ,吴伟志 .一种基于地理位置的启发式 Ad Hoc 路由协议 .计算机工程 ,2008 年 1 月 15杨琦 .一种基于地理位置的无线传感器网络路由协议 .湖南师范大学 ,2008 年 3 月 16严蔚敏 ,吴伟民 .数据结构 （ C 语言版） ,清华大学出版社 ,2007 年 4 月 ,118-121 17 Patrick Lester. A* Pathfinding for Beginners. Almanac of Policy Issues,2005,7
