基于分区策略的Adhoc网络分簇算法研究

摘要

Ad hoc网络是由一组具有无线收发装置的移动节点组成的一个多跳临时性自治系统。网络中的每个移动终端是主机也是路由器，并根据路由算法参与路由的建立和分组转发工作。作为一种无中心、自组织的无线移动通信网络，由于其高效的自组织性，以及动态变换的网络拓扑结构和多跳转发技术，已被广泛运用于军事战场、事故突发现场等紧急环境。
　　 早期的Ad hoc网络由于规模较小，大多基于平面结构。其优点是结构简单，不需要维护，但同时也限制了网络规模的发展。为了提高网络的可扩展性，大型Ad hoc网络通常采用分级结构。网络被划分成若干个簇，每个簇由一个簇头和多个普通节点组成。分级结构的网络规模将不受限制，路由和控制开销较小。目前，寻求合理的分簇算法来减少维护簇结构所需的开销，保持簇结构的稳定性，已经成为分簇算法研究的热点。
　　 为了将分簇算法更好的应用于Ad hoc网络，本文将网络区域划分为网格，在网格基础上结合地理定位和网格分区策略提出了一种基于网格分区策略的多簇头Ad hoc网络分簇算法。其思想是根据地理位置信息将网络划分成网格，若干个网格为一个簇。规定网格中的某区域为簇头生成区，每个簇生成多个簇头。本文提出了一种新的分级结构的路由协议CBGP(Cluster Based on Grid)。CBGP主要由簇头的选举和节点的路由查找两方面构成。簇头的选举采用了传统的加权组合算法，选取了移动性小，节点的连接度大和剩余能量比较多的节点来担任簇头。路由查找方面，确定以源节点和目的节点为顶点的矩形区域为路由查找范围，并将路由查找分为簇内查找和簇间查找两种。这种基于分区的多簇头分簇算法，有效地避免了簇与簇之间的节点重叠，延长了网络的生存时间，减少了分簇的开销。
　　 本文将这种分簇算法与CBRP(Cluster Based on Routing Protocol)协议中的最小ID分簇算法进行了比较。数值仿真表明本文提出的基于分区策略的多簇头分簇算法比最小ID分簇算法在分簇的控制开销上要小。在此基础上，运用NS2仿真平台，构建了网络仿真环境，利用随机生成的移动节点在网络中进行分簇和路由转发。通过仿真分析，得出了CBGP的分簇开销和簇的生存时间优于CBRP。
　　 最后，本文给出了该算法中有待解决的问题和改进建议。

目录

文摘

英文文摘

第一章 Ad hoc网络概述

1.1 Ad hoc网络的发展历史

1.2 Ad hoc网络的概念

1.3 Ad hoc网络的特点

1.4 Ad hoc网络的应用

1.5 选题的背景和意义

1.6 本文的主要工作和篇章内容与结构

第二章 Ad hoc网络结构和分簇算法

2.1 网络结构

2.2 Ad hoc网络分级问题

2.3 经典的分簇算法

2.4 经典分簇算法的改进

2.5 存在问题

2.6 本文的研究思路

2.7 本章小结

第三章 基于分区策略的多簇头分簇算法与路由协议

3.1 基于分区策略的分簇算法的进展

3.2 基于分区策略的网络结构

3.3 基于分区策略的多簇头的分簇算法

3.4 CBGP路由协议中的路由查找策略

3.5 本章小结

第四章 基于分区策略的多簇头分簇算法的参数确定与分簇开销的数值仿真

4.1 数学符号

4.2 基于分区策略的分簇算法的参数

4.3 CBRP协议中分簇开销的计算

4.4 CBGP协议与CBRP协议中分簇开销的数值仿真与比较

4.5 本章小结

第五章 网络仿真与NS2

5.1 仿真平台介绍与比较

5.2 NS2简介

5.3 NS2的原理

5.4 NS2网络仿真机制

5.5 OTcl实现仿真的过程

5.6 本章小结

第六章 基于分区策略的多簇头分簇算法及路由协议的NS2仿真

6.1 CBGP协议的实现步骤

6.2 总体分析

6.3 数据结构

6.4 分簇算法的执行

6.5 路由查找策略的实现

6.6 路由协议CBGP的仿真结果

6.7 基于分区策略分簇算法性能的主要特点

6.8 本章小结

第七章 结论与展望

参考文献

附录1

附录2

作者在研究生期间参与项目及发表论文

致谢