足球比分直播

基于TDMA的Ad+Hoc网络分簇算法分析.pdf

返回
基于TDMA的Ad+Hoc网络分簇算法分析.pdf_第1页
第1页 / 共67页
基于TDMA的Ad+Hoc网络分簇算法分析.pdf_第2页
第2页 / 共67页
基于TDMA的Ad+Hoc网络分簇算法分析.pdf_第3页
第3页 / 共67页
基于TDMA的Ad+Hoc网络分簇算法分析.pdf_第4页
第4页 / 共67页
基于TDMA的Ad+Hoc网络分簇算法分析.pdf_第5页
第5页 / 共67页
点击查看更多>>
资源描述:
摘 要 I 摘 要 无线移动自组网络 ( Ad Hoc 网络)多采用分簇的分级结构。如果网络节点的信道接入采用 TDMA 方式,这就形成了基于 TDMA 的分簇算法设计问题。 一般的分簇结构中,每个簇使用互不干扰的 TDMA 方式接入,簇之间的通信由骨干网来完成。因此每个簇的大小决定了 TDMA 的帧长,同时簇的总个数也决定了骨干网成员数量。从簇内情形考虑,单个簇内的性能和簇成员的个数几乎成正比。从骨干网角度考虑,较小的分簇带来分簇数目的增加,骨干网的性能恶化。如果分簇算法以较小的分簇大小为标准,势必增加转发的业务。如果照顾网络全局性能表现,则影响本地簇的通信性能。如何 平衡二者之间的矛盾是分簇大小选择的关键。关于分簇大小如何选择尚未见其他论文涉及,本文研究的目的是通过数学方法建模推导出解决前述问题的最佳解决方案,并通过仿真实验验证该理论方案。 本论文首先概述了 Ad Hoc 网络的定义,特点,体系结构,以及协议栈结构。进而分析了 MAC 层的多种 TDMA 算法,接下来讨论基于 TDMA 的分簇算法。此过程中首先分析了分簇算法面临的各种问题,进而针对采用 TDMA 方式的分簇过程,构建了基于 TDMA 方式的分簇算法的数学模型,并推导出理论上的分簇大小最佳解决值,得出了分簇大小如何选择的最佳方案 。接着在 opnet 仿真平台验证理论推导的结果,并且设计了四个实验,分别从不同 TDMA 方式,数据业务负载变化,移动终端的移动轨迹三个方面考察了前述方案的适应性。实验结果表明数学模型所得理论值满足实际情形,对于各种因素的影响,有着良好的适应性,该理论方案具有很高的理论价值和广泛的工程意义。 关键词 Ad Hoc 网络,分簇算法, TDMA,分簇大小, opnet 万方数据ABSTRACT II ABSTRACT In many cases, the Ad Hoc network uses clustered hierarchal structure. If the nodes take TDMA to get media access control, this brings out a topic of the designing clustered hierarchal structure based on TDMA. In general clustered structure, each sub-cluster works on different TDMA mode, and communication between sub-clusters is managed by the backbone network. Therefore, the number of sub-cluster members determines the length of TDMA frame, and the number of sub-cluster meanwhile determines the number of backbone member. Considering the perance of a single sub-cluster, the structure of small sub-cluster which composes fewer members is preferred, but this is bound to increase the traffic load of the backbone network, and worsen the perance of the whole network. On the contrary, if considering the perance of the overall network as first, the local sub-cluster would suffer the loss of some perance. In this master thesis, the definition, features, structure and protocol architecture of Ad Hoc network are first introduced, then followed the analysis of several typical TDMA s, after this the discussion of clustering algorithm based on TDMA is approached. In order to figure out the optimum size of cluster, problems existed in cluster algorithm are first involved, and this thesis establishes a mathematical model of clustering algorithm, based on which, the theoretical solution of optimum size of the sub-cluster is then obtained. This solution is next verified by the opnet simulation experiments, which compares three factors that would influence the optimum size of sub-cluster. Each of the factors is different TDMA modes, the change of data traffic load, and trajectories of mobile terminals. The results of these experiments demonstrate that the optimum size of sub-cluster theory satisfies actual situation and its adaptability is able to meet variation of kinds of related factors. Such theory is of theoretical value and project significance. Key words Ad Hoc network, clustering algorithm, TDMA, the size of cluster, opnet 万方数据目 录 III 目 录 第一章 绪论 ................................................................................................................. 1 1.1 Ad hoc 网络概述 ............................................................................................. 1 1.1.1 Ad Hoc 网络概念 ................................................................................. 1 1.1.2 Ad Hoc 网络特点和协议分层体系 ............................................................. 1 1.1.3 Ad Hoc 网络的工程应用背景 ...................................................................... 4 1.2 基于 TDMA 方式的 分簇 算法国内外发展动态概述 ................................... 5 1.2.1 分簇算法国内外发展动态概述 ................................................................... 5 1.2.2 TDMA 算法 在分簇结构中应用的 国内外发展动态概述 ..................... 7 1.2.3 学术界关于分簇大小问题的 讨论 .............................................................. 7 1.3 课题研究目标和方法以及论文撰写的结构安排 ......................................... 8 1.3.1 课题研究目标和方法 .................................................................................... 8 1.3.2 论文撰写的结构安排 .................................................................................... 8 第二章 基于 TDMA 方式分簇算法的理论背景 ................................................... 10 2.1 分簇算法的一般思路 ................................................................................... 10 2.1.1 分簇算法的概念和目标 .............................................................................. 10 2.2 自适应按需加权分簇算法( AOW)分析 ................................................. 12 2.2.1 常见分簇算法举例 ...................................................................................... 12 2.2.2 自适应按需加权分簇算法( AOW) ..................................................... 14 2.3 分簇算法和 MAC 层协议之间的关系 ........................................................ 16 2.3.1 MAC 层协议分类讨论 ................................................................................. 17 2.3.2 TDMA 协议的分类 和讨论 ......................................................................... 25 2.4 分簇算法中如何选择分簇大小 ................................................................... 26 第三章 分簇大小最佳值问题的数学建模 ............................................................... 29 3.1 建模前提 ...................................................................................................... 29 3.1.1 影响分簇大小因素 的分析 .......................................................................... 29 3.1.2 建模中各项参数的设计 ............................................................................. 32 3.2 建立数学模型 .............................................................................................. 33 3.2.1 建立 网络最大吞吐率 的解析表达式 ....................................................... 33 万方数据目 录 IV 3.2.2 建立 节点平均通信时延 的解析表达式 ................................................... 34 3.3 有关模型结论的 数学分析 .......................................................................... 37 3.3.1 性能 1 倍恶化点 概念的提出 .................................................................... 37 3.3.2 有关 最佳值附近变化趋势 的讨论 ........................................................... 38 第四章 通信仿真实验的设计与实现 ....................................................................... 39 4.1 实验的总体 方案 设计 ................................................................................... 39 4.1.1 实验中通信场景设计思想 .......................................................................... 39 4.1.2 TDMA 方式 的选择 ....................................................................................... 42 4.1.3 opnet 程序中 移动模型 的设计思想 .......................................................... 43 4.2 仿真实验的实现 .......................................................................................... 44 4.2.1 软硬件环境及系统概述 ............................................................................. 44 4.2.2 主要数据结构和参数 ................................................................................... 44 4.2.3 opnet 模块的实现 .......................................................................................... 46 4.3 本章小结 ...................................................................................................... 48 第五章 通信仿真实验和实验结果讨论 ................................................................. 49 5.1 通信仿真实验目的 ...................................................................................... 49 5.2 仿真验证实验 .............................................................................................. 50 5.2.1 验证实验一理想前提下分簇大小对网络性能 的 影响 ................... 50 5.2.2 验证实验二 不同 TDMA 方式 下 分簇大小对网络性能 的 影响 .... 52 5.2.3 仿真实验三节点业务变化下分簇大小对网络性能 的 影响 .......... 54 5.2.4 仿真实验四网络拓扑变化下分簇大小对网络性能 的 影响 .......... 58 5.3 实验结论 ...................................................................................................... 60 第六章 总结 与展望 ................................................................................................... 61 6.1 总结 .............................................................................................................. 61 6.2 展望 .............................................................................................................. 61 致谢 ............................................................................................................................. 62 参考文献 ..................................................................................................................... 63 万方数据第一章 绪论 1 第一章 绪论 1.1 Ad hoc 网络概述 1.1.1 Ad Hoc 网络概念 Ad Hoc 网络 [13]( Ad Hoc 一词来源于拉丁语,意为“专用的、特定的”。)是由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。它的前身是分组无线网( packet radio network),分组无线网起源于军事上的需要。随着技术的发展,移动通信领域涌现出蜂窝移动通信系统、无线局域网( IEEE802.11 和HiperLAN)、蓝牙技术( Bluetooth)、家庭无线网( HomeRF)等等新技术。这其中有的就是 Ad Hoc 网络研究的范畴,有些和 Ad Hoc 网络在技术上有共同点。近几年, Ad Hoc 网络的研究更加全面、深入、细致,工程技术研究人员提出了各种适应新应用场景的协议和更多的改进算法。 Ad Hoc 网络的研究受到更多关注。 1.1.2 Ad Hoc 网络特点和协议分层体系 1.1.2.1 Ad Hoc 网络特点 一般来说, Ad Hoc 网络具有以下几个方面特点 1 独立组网 Ad Hoc 网络在组网布 置时,无需依赖任何预先设 置 的网络设备。网络内的节点在开始工作后,就可以快速,自动组成一个独立的网络进行通信。 2 自组织 Ad Hoc 网络没有严格的控制中心,所有节点通过分层和分布式算法协调各自的行为,实现快速自动组网。在分簇结构中,虽然有类似网络中心的簇头,但由于簇头并非一成不变,根据需要网络可以随时更换簇头。 3 多跳路由由于受限于节点发射机功率,各节点的覆盖范围有限 , 当两个相隔超出彼此覆盖范围的节点通信 时 , 就 需要中间 节 点转发, 此 即 为 多跳 路由。另有一种由分簇算法造成的多跳路由情形 根据算法的要求,簇内节点彼此 通信无需转发 ,而属于不同簇的节点,即使 在覆盖范围内,通信时 仍然 需要网关的转发。 万方数据电子科技大学硕士学位论文 2 4 动态拓扑 Ad Hoc 网络中,移动终端可能以多种任意方式移动,并且可以随时开关电台,再加上通信设备,例如发射却机功率变化,天线等,以及地形、天气因素的影响,使得网络的拓扑结构在不断地变化,变化的趋势有时可以预测,有时事先难以估计。 因此 需要制定专门的路由协议。 5 特殊的无线信道特征 Ad Hoc 网络采用无线通信技术 ,具有鲜明的无线信道特征,例如 可供通信的带宽远小于有线网络 ; 信号之间的冲突,信号衰减,噪音和干扰 等都反映出无线信道的特 点; 由于各通信终端的发射机接收机功率不同,网络中有双向和单向通信链路 , 例如车载设备接收发送 能 力大于手持设备,使得车载到手持终端这一通路是单向的 ; 由于节点的通信覆盖范围各自不同,一方面提高了信道的空间复用度,另一方面也使得报文的冲突与节点的地理位置息息相关。 6 移动终端的局限性移动设备小巧便携,这也使得它的能源受限,内存较小,CPU 处理能力弱,成本较高 , 从而给设计开发带来很大难度 , 同时受上述因素影响,不利于开展功能复杂的业务。便携设备一般使用电池供电,因此怎样节约能源延长设备的工作时间是设计的重点。 7 安全性差 Ad Hoc 网络由于采用无线信道、分布式控制,因此更容易被窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击。另外, Ad Hoc 网络中的节点自身担任路由器,不存在命名服务器和目录服务器等网络设备,也不存在网络边界的概念,这些使得 Ad Hoc 网络的安全问题变得异常复杂。不能仅靠传统的网络安全策略,还需要信道加密、抗干扰、用户认证、密钥管理、访问控制等手段的辅助。 1.1.2.2 Ad Hoc 网络的协议体系 类似于计算机通信网络, Ad Hoc 网络的协议栈体系可以分为常见的 5 层协议结构,如图 1-1 所示。下面分别 对各层的作用地位做简要叙述。 应用层 传输层 网络层(路由层) 媒体接入层( MAC 层) 物理层(无线信道环境) 图 1-1 Ad Hoc 网络协议栈体系 万方数据第一章 绪论 3 1 物理层 在 Ad Hoc 网络协议栈结构中,物理层负责频率的选择、无线信号的检测、调制解调、信道加密解密、信号发送和接收等。此外,还要确定采用哪种无线扩频技术 例如 直接序列扩频 DSSS 或是跳频扩频 FHSS,无线信道的各种参数直接影响着网络的通信性能表现。 2 信道接入层 MAC层 信道接入技术是 Ad Hoc 网络体系的基础。它控制着每个节点何时以何种方式接入信道,直接影响着通信的时延,网络的吞吐率,可以说对网络的性能起着决定性的作用。 Ad Hoc 网络的无线信道不同于一般的无线信道。它既不是共享广播信道,点对点无信信道,也不是蜂窝移动通信系统中由基站控制的无线信道。每一个节点的信息,有且仅有它的一跳邻居可以接收到。这样可以在不同的区域对信道进行空间复用。这就是多跳共享广播信道。虽然信道的空间复用程度得以增强,但同时也带来了隐终端和暴露终端问题 。关于隐终端和暴露终端问题在第二章做详细描述。 常见的 MAC 层算法有各种 CSMA 改进算法,各种 TDMA 算法等等。详 细描述见第二章。 3 网络层(路由层) Ad Hoc 网络的路由层承担着网络中的路由探测,路由部署以及路由维护功能。尤其在网络拓扑不断变化中,路由算法需要不断反映出当前的网络结构,并且不能占用太多的系统资源。路由算法在设计过程中面临以下几方面的困难 a 动态变化的网络拓扑结构 Ad Hoc 网络的拓扑变化主要体现在节点的移动,节点的加入或退出,链路权值系数变化,网络拥塞等方面。 b 系统开销由于 Ad Hoc 网络的动态拓扑,势必使得路由算法要不断维护网络的路由信息。 当网络在周期性地维护路由信息时,会占用大 量 的信道带宽,不但影响网络性能,而且可能由于路由算法不合理导致网络的带宽被系统开销全部占据导致通信崩溃。 c 算法的收敛性能路由算法要求必须很快收敛,否则路由信息刚刚部署完成,网络的拓扑结构又发生了变化。但是算法快速收敛并不能降低对算法的优化要求。 d 单向或是双向的无线信道在传统的网络路由协议中,通常认为节点 之 间的链路是双向链路。但是在实际的 Ad Hoc 网络中,由于无线收发设备的不同或周万方数据电子科技大学硕士学位论文 4 围环境的影响,很可能形成单向的无线传输信道。 正是由于以上各种原因,如果把传统的路由协议应用于 Ad Hoc 网络中,各种周期性控制信息将会占 用大量系统带宽,降低系统效率,甚至阻塞网络。所以必须结合 Ad Hoc 网络自身的特点制定路由策略。 常见的路由算法有矢量路由算法( DVA),链路状态路由算法( LSA),核心提取分布式自组织路由算法( CEDAR)等等。 4 传输层和应用层 传输层为源节点和目的节点提供可靠的端到端数据传输。而目前广泛使用的传输层协议是为计算机网络设计的。这些协议放在无线环境下性能明显下降。例如 TCP 协议 在无线环境下可能引起大量的重传并且带来更加繁琐的链路冲突,这样不但会降低网络的吞吐量、增加 时延 ,同时也会消耗有限的系统带宽,以及移动终 端的电池能量。可以 这样改进 减少端到端的重传机制来提高网络的工作效率 , 或是采用带有探寻机制的 TCP 协议 TCP-probing。该协议的工作原理是 当无线节点发现数据分组丢失或是延时较大时,并不直接进行拥塞控制,而是停止发送数据并开始进行探寻过程。在探寻过程中,源节点向目的节点发送探寻分组。该分组 由 TCP 报头扩展实现,本身并不携带数据分组。如果在两个往返时间内没有探寻分组丢失,则认为探寻前的数据分组丢失是由于偶然因素造成,节点继续传输数据。如果探寻失败,则进行传统的 TCP 拥塞控制。仿真结 果 表明,该 机制能显 著提高吞吐 率 ,并且降低移动终端的能量消耗。 应用层包含了所有的高层协议 , 例如文件传输协议 FTP,虚拟终端协议TELNET等。对于 Ad Hoc 网络,除了可以进行业务分类等操作,更应该结合移动网络的自身特点 , 例如根据节点当前的能量状况以及无线链路的状况,采用合适的压缩编码方式,同时也能对业务进行取舍 , 例如在低功耗的情况下, 禁止 视频业务 , 仅允许 进行 音频业务。 1.1.3 Ad Hoc 网络的工程应用背景 Ad Hoc 网络的自组织性提供了廉价并且快速部署网络的途径。其多跳和中间节点的转发特性可以在不降低网络覆 盖范围的条件下减少每个终端的发射功率,从而降低了天线和相关接收与发射射频终端的设计难度和成本,为移动终端的小型化、低功耗提供了可能。从用户的角度考虑,低功率的电磁波辐射对身体健康影响较小。总的来说, Ad Hoc 网络的应用背景可以归纳为下面的几类 万方数据第一章 绪论 5 1 军事应用军事应用是 Ad Hoc 网络的主要应用领域。目前的 Ad Hoc 网络将单兵、车载、指挥所等不同对象联系了起来,加强了各部门,各作战单位之间的联系,充分体现了现代信息化战争的技术特点。 2 传感网络传感网络主要由各种传感器组成。传感器的发射功率很小,而且分布不集 中, Ad Hoc 网络恰满足上述特点,因而得到广泛应用。 3 紧急和突发场合地震、洪水、泥石流等自然灾害的抢救,都需要临时搭建通信网络,原有的通信网要么毁坏,要么不满足要求,由于 Ad Hoc 网络易搭建、易拆除、移动性强等等优势,便成为首选。 4 野外地区在野外作业,包括勘探,科考,户外探险等等活动,由于野外地形复杂,地理位置偏僻,一般的移动蜂窝网络已不能满足通信的要求,此时可以使用便携移动终端组成小型的 Ad Hoc 网络满足基本的通信需求。 5 其他由于 Ad Hoc 网络的灵活性,不可能罗列所有应用场合。除了单独使用Ad Hoc 网络外,它还可以作为大型网络的末梢接入,拓展原有网络的通信范围和通信能力。随着移动技术的进步,势必会有更多的领域采用 Ad Hoc 网络技术。总之,从以上几点,可以看出研究 Ad Hoc 网络技术的必要性和重要意义。 1.2 基于 TDMA 方式的分簇算法 国内外发展动态概述 1.2.1 分簇算法国内外发展动态 概述 Ad Hoc 网络可以分为平面结构和分簇结构两种。如图 1-2 和图 1-3 所示。 152734图 1-2 Ad Hoc 网络平面结构 万方数据电子科技大学硕士学位论文 6 簇频 率 1频 率 2 簇 头 簇 成 员图 1-3 Ad Hoc 网络分簇结构 在平面结构中,所有节点的地位相同,原则上网络不存在瓶颈,网络健壮。但是它的缺点是可扩展性差,每一个节点都要维护全网络的路由信息。维护这些路由信息将带来很大的系统开销。在网络节点个数较少时,平面结构简单易于实施 , 同时由于网络规模小,维护路由的系统开销并不明显。但是随着网络规模的增大,可以预见网络的带宽将会被系统开销全部占据。在分簇结构中,每个节点只需维护本地簇成员的路由信息 ,这大大减少了全网络的控制信息开 销,不但在网络性能上得以提 高,也使得网络具有了很好的扩展性。分簇结构的每一个簇内的节点地位等同, 可以很方便地通信,而 簇与簇之间的通信通过具有网关作用的簇头来担任,这就在簇之间建立了二级网络。在网络拓扑结构复杂的情况下,这种分级可以继续进行。这种分级网络在分簇算法的支持下也可以 提高 网络 的健壮性能 , 不过缺点是担任簇头的节点将会成为全网络的瓶颈。簇头节点 除了 担任网关的任务 外 ,同时负责管理簇内的其他节点, 有更多的额外 能量消耗, 故而簇头的选举成为分簇算法的重点, 现有的分簇算法在很大程度上都在讨论簇头的选举,以 保证网络的负载平衡以及网络的拓扑结 构变换,同时还要考虑簇头节点的能量消耗问题。 到目前为止,工程技术人员已经提出了各种分簇算法 [413],例如基于节点 ID的分簇算法、基于节点连接度、基于节点移动特性,考虑簇头稳定的分簇算法、适合传感器网络的低功耗分簇算法、考虑地理因素的分簇算法等等。其中最具代表性的是自适应按需加权分簇算法( AOW, Adapted On-demand Weighting)。该算法将影响分簇和选举簇头的因素分为四大类,分别设置这些因素的权重因子,最万方数据
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播