ad-hoc网络--大学毕业论文设计.doc

导论
中文摘要
一个Ad Hoc网络就是许多通信设施或节点之间的通信，但是没有固定的物理设施或固定的连接关系。AODV算法是一个经典的路由算法，弄懂AODV算法的基本原理和程序实现对进一步掌握Ad Hoc网络技术是十分必要的，在这个前提下，本文对AODV算法思想，原理及程序实现进行了学习和研究。
首先，要学习AODV的思想和原理，为以后的程序分析做好知识准备。按需距离矢量（AODV）路由协议是Ad Hoc网络的一种动态路由协议，是在依据要求的基础上来进行Ad Hoc网络的路径路由的。AODV协议的操作是开环的。
其次，要弄清AODV的算法的流程。AODV算法分为两个部分，路由发现和路由的维护。AODV路径发现机制是依靠路由请求控制消息（RREQ），路由应答控制消息（RREP），和路由应答确认控制消息（RREP-ACK）来完成的。AODV 路由的维护是当网络中已建立路由发生变化的时候，网络对各节点的处理，其主要依靠对每个节点的路由表进行操作来完成的。
最后，就是要进行程序分析，分析程序的结构及所有的函数，弄清用计算机语言写成的程序是如何实现AODV算法的功能的，写出分析表格或者画出结构图。这些工作为进一步改进AODV算法做好分析的准备。

关键词：Ad Hoc网络 AODV 路由算法 程序分析

导论
目 录
第1章 导论 1
1.1 移动Ad Hoc网络简介 1
1.1.1 移动Ad Hoc网络发展历史简述 1
1.1.2 移动Ad Hoc网络具有的特点 3
1.2 AODV协议算法简介 5
1.3 研究动机 5
1.4 论文结构 7
第2章 路由算法分析 9
2.1 AODV原理 9
2.1.1 AODV算法基本流程 9
第3章 AODV协议程序分析 11
3.1 总体框架分析 11
l StartRouting函数 12
第4章 总结 XIII
参考文献 XV
致 谢 XVII

IX

第1章 导论
第1章 导论
1.1 移动Ad Hoc网络简介
20世纪70年代，美国国防部高级研究计划局(DARPA)启动了“战场环境中的无线分组数据网”项目，研究在战场环境下利用分组无线网进行数据通信。1983年和1994年，DARPA又分别于启动了抗干扰自适应网络项目SURAN(Survivable Adaptive Network)和全球移动信息系统GloMo(Globle Mobile Information Systems)项目，对能够满足军事应用需要的移动通信系统进行更深入的研究。后来，IEEE802.11[1]标准委员会采用了“Ad hoc网络”一词来描述这种特殊的自组织无中心多跳无线网络结构，Ad hoc网络由此诞生。
1.1.1 移动Ad Hoc网络发展历史简述
移动Ad Hoc 网络技术不是一种新技术，已有30年发展历史。下面图1-1给出了Ad Hoc网络的发展概况。

图1.1 移动Ad Hoc网络发展历史图
　 移动Ad Hoc网络的思想最早可追溯到1968年的ALOHA网络。ALOHA网络的研究目标是为了将夏威夷的教育设备连接在一起。ALOHA采用固定基站和分布式信道访问管理，为之后分布式信道访问技术的研究和开发提供了基础。ALOHA协议是单跳协议，不支持路由功能。受到ALOHA网络和早期固定分组交换网络开发成功的鼓舞，DARPA在1973年开始研制分组无线网络（Packet Radio Network,PRNET）。PRNET是多跳网络，提供集中式和分布式的操作管理机制。正是由于PRNET的研制成功，才使人们认识到多跳技术能够提高网络容量。在路由协议方面，PRNET首先引入了主动多跳路由算法，其工作原理如下：每个节点维护一张其相邻分组电台（Packet Radio,PR）和到达这些相邻ＰＲ的链路质量列表。通过ＰＲ主动的向其他所有ＰＲ广播其存在来建立路由。使用一种特定的分组无线组织包（Packet Radio Organization Packet,PROP）进行主动广播。但是，PROP广播导致传输大量的控制分组，这就限制了网络的扩展性。事实上，在PRNET中，网络中的PR数量不能够超过１３８个。相邻PR数量也被限制在１６个月内。PRNET中的分组电台和控制设备体积大，功耗大，从而限制了系统的处理能力。
抗毁无线网络（Survivable Radio Network,SURAN）是美国国防部高级研究计划局（DARPA）于１９８３年开发的，主要解决PRNET的遗留问题，网络扩展性，安全，处理能力以及能量管理。SURAN的主要研究目标是开发网络算法，采用这些网络算法使网络能够扩大到数万个节点；能够对抗安全攻击；能够采用低成本，低功耗小型电台支持复杂的分组无线网络协议。
到了２０世纪８０年代后期和９０年代初期，随着Internet基础设施的增长，微型计算机革命使得初期分组无线网络思想更加实用，更加切实可行。为了使全球信息基础设施支持无线移动环境，DoD在１９９４年启动了DAPRA全球移动信息（Global Mobile,GloMo）系统计划。GloMo计划的研究目标是支持无线装置之间随时随地的以太网类多媒体连接；解决所谓的移动Ad Hoc网络的（移动（Mobile），多跳（Multihop），多媒体（Multimedia））问题；美国陆军在1997年实现的战术Internet(Tactical Internet,TI)是迄今为止所实现的规模最大的移动无线多跳分组无线网络。TI采用直接序列扩频的时分多址电台，数据传输速率为几十kb/s，节点之间采用经过修改的商用Internet协议进行网络互联。这使我们认识到：商用有线协议不能处理拓扑变化问题以及数据速率低而比特误码率高的无线链路。1999年，美国海军陆战队提出了另外一个移动Ad Hoc网络，即增强型沿海战场先进概念技术示范（Extend the Littoral Bsttle-space Adanced Concept Technology Demonstration,ELBSCTD），用于演示海军舰艇部队作战概念。从海上舰队到地面，海军陆战队队员需要通过空中继续跨视距（Over The Horizon,OTH） 通信。
从上面可以看出，开发移动Ad Hoc网络具有很强的军事背景，其研究还在继续进行。即使是现在，DARPA也正在支持多种研究项目，例如，未来战斗系统（Future Combat System,FCS），联合战术电台系统（Joint Tactical Radio System,JTRS），美国空军（Future Combat System,USAF）航空网特别工作组织定的《航空网体系结构》，均包括了移动Ad Hoc网络问题。
1.1.2 移动Ad Hoc网络具有的特点
移动Ad Hoc 网络由一组无线移动节点组成，是一种不需要依靠现在固有通信网络基础设施的，能够迅速展开使用的网络体系，没有任何中心实体，自组织，自愈的网络；各个网络节点相互协作，通过无线电路进行通信，交换信息，实现信息和服务的共享；网络节点能够动态的，随意的，频繁的进入和离开网络，而常常不需要事先示警或通知，而且不会破坏网络中其他节点的通信。

图1.2 Ad Hoc网络示例
　　上图举例说明了一个有８个节点和他们之间相互连接的小的ａｄ　ｈｏｃ网络的例子，节点是可以发生移动的，如果他们之间有一条连接突然断掉了，另一条连接就会生成。在这里，Ｍ１从Ｍ２移开，断开与Ｍ２的连接，并与Ｍ７，Ｍ８建立新的连接。　大部分的算法都允许新节点的出现和旧节点的消失。这是因为一个ａｄ　ｈｏｃ网络没有一个中心控制和固定的物理结构。它的结构应该是分布式的，像寻址和鉴别应该设计在一个分布式的环境里。
移动Ad Hoc网络是对等网络。这是移动Ad Hoc网络与使用基站和固定基础通信设施的蜂窝网络之间的一个重要区别。移动Ad Hoc网络中的节点具有游牧特性，节点在一定区域内自由移动，动态的产生和拆毁其与其他节点的关系。与大多数传统无线网络相比，在设计和操作移动Ad Hoc网络中所遭遇的主要挑战来源于缺乏集中式实体，节点迅速移动的可能性，以及所有通信都是在无线媒介上进行的这个事实。基于Ad Hoc 网络本身特点，对Ad Hoc 网络具有以下要求：
（1） 具有强壮的路由算法和移动管理算法。
（2） 自适应算法和协议。
（3） 低开销的算法和协议。
（4） 源节点和目的节点之间的多条路由（截然不同的路由）。
（5） 强壮的网络体系结构。
多跳网络和单跳网络相比具有很多优点，如下表格：

表1.1 多跳网络和单跳网络的比较
多跳网络
单跳网络
增强了网络的扩展性
不易扩展
降低干扰
易受干扰
提高了整个网络的吞吐量
整个网络的吞吐量有限
延时较短
有较长延时
节能
能耗较大
从上面的描述可以总结到，Ad Hoc 网络至少应具备以下五个共同的特点：
（1） 分布式操作
（2） 宽带有限，链路容量易变
（3） 移动性与网络拓扑动态性
（4） 设备限制
（5） 物理安全有限
Ad Hoc网络在将来能满足人们很多通信的要求，但是，它也有许多问题有待解决，所以移动Ad Hoc网络面临许多挑战和问题。总体说来，要面临以下六方面的挑战：消费者应用；外来系统连接；宽带有限；扩展性；电池能量极其有限；安全。
1.2 AODV协议算法简介
按需距离矢量（AODV）路由协议是Ad Hoc网络的一种动态路由协议，是在依据要求的基础上来进行Ad Hoc网络的路径路由的。AODV协议的操作是开环的，在Ad Hoc网络拓扑变化之时，通过避免 Bellman-Ford“无穷计算”问题来提供快速收敛。AODV一个路由协议的一个明显特征是每个路由条目均使用一个目的节点序列号。目的节点序列号由目的节点产生，与目的节点发送给路由请求节点的任何路由信息组合在一起。使用目的节点序列号能够确保路由是开环的，并且编程简单。如果在到达同一个目的节点的两条路由中选择一条，那么要求路由请求节点选择序列号较大的那条路由。
1.3 研究动机
清华大学电子系研究人员杨帆，钟晓峰，王有政等人通过努力实现了Ad Hoc网络多层混合实验系统的设计。他们发表了一篇论文《Ad Hoc网络多层混合实验系统的设计实现》，这篇论文主要讲了三个部分：TTAS实验系统的整体结构；实验系统各模块的设计方法；TTAS系统的应用和总结。TTAS实验系统利用装有无线网卡的PC机（笔记本电脑）作为网络终端，每个终端单独加载实验系统的软件模块即可实现AdHoc网络的专有功能。TTAS实现系统分为硬件和软件两大部分，其中硬件部分主要是无线网卡，利用网卡的直连模式直接实现了点对点的传输，作为Ad Hoc网络多跳传输的基础。软件部分包括系统控制，协议实现，测试评估三部分。如下图：

图1.3 TTAS实验系统框图
对于系统模块设计部分，在硬件方面，系统实现了对网卡的透明性，软件部分采用C语言开发，系统软件部分结构如图：

图1.4 TTAS系统软件部分框图
在软件部分主要可以分为两个部分，一个是网卡驱动程序，另一个是路由程序。路由协议程序在整个系统的作用如上图，已经很明白的显示出来了。路由协议程序的上层和下层是ＮＤＩＳ路由接口驱动，上层的NDIS路由接口连接到ＩＰ协议层，下层的NDIS路由接口连接到虚拟无线网卡，再通过这个虚拟无线网卡接连到网卡，这些结构在程序中都有相应的体现。
TTAS系统是一个基于普通PC机Windows操作系统的多层混合ａｄ　ｈｏｃ网络实验系统，具有很多的优点和独创性。结构清晰，各模块采用统一的标准接口，系统扩充容易，易于二次开发。TTAS实验系统的路由协议部分采用的算法是AODV算法，我的任务就是对着干算法进行学习，对路由协议进行程序分析，为二次开发做一些前期准备工作。
1.4 论文结构
本文总共有四章，第一章是导论，第二章是路由算法分析，第三章是AODV程序协议分析，最后一章是总结。在第一章里，简要的介绍了无线网络及其发展历史，和AODV算法的一些简介，研究动机及论文结构。第二章着重介绍了AODV路由算法，包括算法思想及流程，在第三章内，对AODV程序进行分析，画出结构图，分析函数功能等，最后是总结，总结了这次综合训练的经过及收获以及自己的一些感悟。

7

第1章 导论
第2章 路由算法分析
2.1 AODV原理
2.1.1 AODV算法基本流程
在一个路由程序里，要承担了两大部分的功能：路由的发现与路由的维护。AODV算法与DSR算法根本的不同在于，前者主要靠中间节点转发数据包，而后者主要是靠源节点确定路由直接发送数据包，这两个不同模式有一个很好的比喻，前者可以比喻成邮递机制，后者可以比喻成坐火车机制。在AODV算法中，主要有路由的发现和路由的维护两大部分组成。下面分别介绍这两大部分的各自机制。

第2章 路由算法分析
第3章 AODV协议程序分析
3.1 总体框架分析
程序是从main() 函数开始的，所以先找到main() 函数，主函数在dllpart目录下的myuser.cpp内，在主函数内，服务器端要初始化TCP socket，开始监听（Initialize函数），这时接收客户端的连接，收取客户端传来的控制信息并存在buffer中，控制信息的首字节即buffer[0]决定相应处理,共有六种不同的处理，分别是虚拟网卡操纵，获得路由，开始路由，停止路由，设置路由，清除路由，和系统信息。作图如下：

图3.1 程序入口框架

下面分别介绍这几个函数：
l StartRouting函数

图3.2 StartRouting函数框图

AODV协议程序分析参考文献
第4章 总结
我们正处在一个科技发现和技术创新不断涌现的时代，网络的发展更是迅速，无线网络作为网络的一个重要分支，从诞生至今，不断有新技术突破，本论文先是在第一章综述了无线自组网Ad Hoc网络的发展历史及清华学者的最新研究成果，然后介绍本论文研究的重点——路由部分的AODV算法，在第二章详细的介绍了AODV的基本原理及前人的相关研究，然后根据这些原理去对AODV程序进行分析，这部分内容放在了第三章，最后一章是总结。我的研究就是学习AODV算法的基本特征和原理步骤，及程序实现，对程序进行分析。通过这次综合训练，我认为我有以下三方面的收获：
l 这是大学最大的一次科研实践，认识到科研与学习之间的区别和联系，为以后的学习和工作总结很好的经验和教训；
l 通过这次训练，更加熟悉了无线网络尤其是Ad Hoc网络方面的知识；
通过对程序的分析，熟悉了计算机语言的使用，并且对原理如何程序实验这一过程增加了不少了解。
2003年我进入清华大学电子工程系读书，转眼间4年过去了，我即将毕业。在大学四年时光里，我学到很多东西，关于学问的，更多是关于做人的，感谢清华大学给我营造一个自由的环境，让我在这里度过我人生的叛逆与反思期，学会了认识问题和分析问题的方法，思想逐渐成熟。在即将毕业的时候，我想对清华大学说：您像一个慈祥而充满智慧的母亲，在这四年里，是您，一直鞭策我，教育我，和呵护我，虽然，我不是一个听话好学的孩子，但我仍然会谨记您对我的教诲，并永远怀念这段时光。
在大学时间，我顺利修完大学所有课程，在大四下学期，要进行最后的综合训练，既是对大学所学知识的一个总结，也是为以后走向工作岗位进一步的科研工作做一些准备。我的毕业综合训练题目是《Ad Hoc网络路由程序分析》，对于Ad Hoc网络，我以前一点也没有接触，所以，通过这次训练，我对Ad Hoc网络的一些基本知识有了不少的了解，尤其是AODV算法的基本原理。我的任务是程序分析，这要求一定的语言基础。我在大一学过C语言，学得很一般，通过这次训练，我也学了不少编程方面的知识。总之，通过这次综合训练，我的收获很大。

总结参考文献
参考文献
[1] 陈林星 曾曦 曹毅.移动Ad Hoc网络-自组织分组无线网络技术.北京：电子工业出版社，2006
[2] Pillai Unnikrishnan. Introduction And Analysis Of DSR Protocol. Helsinki University of Technology.2004
[3] 彭伟.移动自组网络中的广播与路由技术研究.国防科技大学：全国优秀博士论文丛书.长沙：国防科技大学出版社，2004
[4] 郑莉 董渊.C++语言程序设计.北京：清华大学出版社，2004
[5] 黄维通.Visual C++面向对象与可视化程序设计.北京：清华大学出版社，2006

总结参考文献
致 谢
感谢清华大学无线中心钟晓峰老师一直给我的鼓励和帮助，在我遇到苦难，心生气馁的时候，钟老师一如既往地给我鼓励和帮助，这一点我十分感谢。另外还要感谢清华大学无线中心研究生王易风师兄，在自己任务很繁重的情况下，抽出时间给我答疑解惑，同王易风师兄一起交流，也学到很多东西，对王易风师兄我十分感谢。