本文是一篇计算机论文，计算机人工智能化是未来发展的必然趋势。现代计算机具有强大的功能和运行速度，但与人脑相比，其智能化和逻辑能力仍有待提高。（以上内容来自百度百科）今天为大家推荐一篇计算机论文，供大家参考。
第 1 章 绪论
1.1 无线自组织网络介绍
无线自组织网络(Wireless ad hoc network)是基于无线方式通信的，由大量无线终端（或称为节点）组成的，一种非集中式的多跳无线网络[1, 2]。无线自组织网络不依赖于任何现有架构，如路由器或接入点等。无线自组织网络是“自组织”的，是指网络中的两个节点间通信时，需要其它的一系列节点作为中继帮助完成消息传递。也就是说，与传统的有线网络不同，无线自组织网络中的每个无线节点都参与到路由的过程中，并共同实现路由功能。关于无线自组织网络的研究最早始于 1973 年 DARPA(Defense AdvancedResearch Projects Agency)的分组无线网络(Packet radio network)[3, 4]。值得一提的是，最早的关于分组无线网络的研究始于互联网之前，并且是作为原始 Internet协议构建的动机的一部分。之后 DAPRA 又进行了可存活自适应网络(SurvivableAdaptive Network)[5]和全球移动信息系统(Global Mobile Information Systems)[6]等项目的研究，这些都是无线自组织网络的一些相关的早期研究。直到 1991 年，IEEE802.11 标准委员会正式采用“ad hoc network”来描述这种自组织的多跳对等式无线网络。近年来，随着无线通信技术的进步，无线网络以其相比于有线网络更加灵活和便捷的通信模式，获得了迅速的发展和大量的应用。传统的蜂窝通信网络等无线网络仍然无法摆脱基站等通信设施的束缚。
..........
1.2 虚拟骨干网与连通支配集
受到有线网络中骨干网概念的启发，无线自组织网络中采用虚拟骨干网(Virtual backbone)来解决无线自组织网络通信过程中信号干扰、能耗、动态拓扑控制等问题。虚拟骨干网中的骨干节点作为中继节点以完成通信过程中消息传递的任务(如图 1.1)。将无线自组织网络将路由任务限制在骨干节点上，可以有效的提高网络的路由效率：将数据传递限制在少量骨干节点上，可以有效的解决网络中“广播风暴”(Broadcaststorm)的问题。当网络规模增加时，如果每个节点都对广播数据进行转发，则广播所带来的通信冗余会快速增加。虚拟骨干网将消息传递限制在较小规模的骨干子网上从而解决这一问题。通过减少通信冗余，虚拟骨干网可以有效缓解广播过程中信号干扰和信道竞争的问题。
........
第 2 章 国内外研究现状
本章介绍无线自组织网络中虚拟骨干网构建的相关工作。第 1 节首先对无线自组织网络的常用模型进行了介绍。第 2 节介绍了支配集、最大连通支配集、最大独立集等基本概念，这些概念及其相关算法是目前无线自组织网络中虚拟骨干网构建方法的理论基础。第 3 节介绍了近年来关于最小连通支配集构建的近似算法的研究现状。
2.1 无线自组织网络模型
在无线自组织网络中，无线节点之间通过天线进行通信。这些天线分为两种：全向天线和定向天线。对于采用全向天线的无线自组织网络，一般可以将其抽象为无向图：将无线终端用图中的点表示，将可以相互通信的每对点用边相连。单位圆盘图模型（如图 2.1）是无线自组织网络最常用，也是被研究最为广泛的模型[29-36]。单位圆盘图模型假定网络中的节点的通信范围相同，将每个节点通信的覆盖范围看成一个单位圆盘，即当且仅当一个节点位于以另一个节点为圆心的单位圆内部时，认为这两个节点相邻。可见，单位圆盘图是一种同构无线网络模型。
........
2.2 构建最小连通支配集的近似算法研究现状
计算连通支配集的近似算法分为两类：集中式算法(Centralizedalgorithms)[10,46, 47]和非集中式算法(Decentralizedalgorithms)(如图 2.4)。其中，非集中式算法又可以分为分布式算法(Distributed algorithms)[21, 25, 26, 28, 35, 48-55]和局部算法(Localized algorithms)[56-59]。一般来说，集中式算法能够获得更好的近似度，但是集中式算法需要知道整个网络的拓扑结构，这在实际中往往是难以实现的。在分布式算法和局部算法中，算法结果通过节点之间的消息传递(Message passing)完成，因此在实际应用中一般采用分布式和局部算法。特别地，局部算法作为特殊的分布式算法，在确定一个节点是否是支配节点时仅仅使用它的常数跳的邻居信息。
........
第 3 章 节点间通信延迟不同的异构无线自组织网络............29
3.1 问题概述 ...........29
3.2 模型构建 ...........32
3.3 CDS-LO-1..........33
3.4 CDS-LO-2..........3
3.5 CDS-LO-43..........42
3.6 模拟实验 ...........46
3.6.3 三维网络中算法的性能对比............49
3.7 本章总结 ...........50
第 4 章 节点通信范围不同的异构无线自组织网络中连通支配集的构建......53
4.1 问题概述 ...........53
4.2 圆盘图中连通支配集的构建..........54
4.3 球体图中连通支配集的构建..........57
4.4 本章总结 ...........79
第 5 章 节点能量异构的无线自组织网络中里连通支配集的构建........81
5.1 问题概述 ...........81
5.2 CDS-LL 算法 ....82
5.3 E-CDS-LL 算法...........88
5.4 模拟实验 ...........90
5.4.4 E-CDS-LL 算法的测试...........93
5.5 本章总结 ...........94
第 5 章 节点能量异构的无线自组织网络中连通支配集的构建
5.1 问题概述
能耗是无线自组织网络的核心问题。无线自组织网络由无线节点组成，这些节点往往是一些便携设备，较小的体积和重量能够有效的提高它们的可用性，这就极大的限制了无线节点的计算能力、存储容量和能量存储能力。无线节点所携带的电池的能量存储非常有限，因此，无线网络的生存时间极大的受到其能耗效率的限制。在基于虚拟骨干网的无线自组织网络中，骨干节点由于负担路由任务，比非骨干节点具有更高的能耗。根据文献[27]，若无线节点为休眠状态，其能耗为 0.03瓦；若为工作状态，其能耗区间在 0.38 瓦到 0.7 瓦。节点的异构性，如电池容量和通讯设备功率的不同，也造成节点能耗与剩余能量的不同。如果使用固定的虚拟骨干网，那么骨干节点会很快耗尽能量导致网络瘫痪。在本章中，提出了两个算法，CDS-LL(CDSwithLongLifetime)和 E-CDS-LL，来实现节点的负载均衡，从而提高网络的生存时间。CDS-LL 算法是一个基于最大独立集的两阶段算法。给出了 CDS-LL 算法的集中式版本和分布式版本。除了以连通支配集中节点数量较少为优化目标，CDS-LL 算法选择剩余能量较多的节点来在算法的两个阶段中延长骨干节点的生存时间。来实现生存时间和连通支配集中节点数量两个优化目标之间的交换。
........
总结
相比于同构无线自组织网络，异构无线自组织网络具有节点通信范围不同、点对点通信延迟不同、节点剩余能量不同等特点。针对这些特点，本文对异构无线自组织网络中虚拟骨干网的构建进行了研究。本文首先对高延迟的异构无线自组织网络进行了研究。以水声通信网络为例，本文将高延迟网络建模为边带权的图，并设计了三个算法来构建延迟优化(Latency-Optimal)的连通支配集：CDS-LO-1，CDS-LO-2，CDS-LO-3。这些算法在优化虚拟骨干网大小的同时，优化了另外两个与延迟相关的参数：连通支配集的半径和路由开销 CDS-LO-1 对连通支配集的半径具有 2 的近似度，但对连通支配集的大小不具有常数近似度；CDS-LO-2 对连通支配集的大小具有 140 的近似度，对路由开销具有 6 的近似度；CDS-LO-3 对连通支配集的节点数量具有10.197 的近似度，对连通支配集的半径具有 12 的近似度。实验证明 CDS-LO-1、CDS-LO-2、CDS-LO-3 实现了对连通支配集大小和延迟之间的性能交换：以虚拟骨干网的大小为标准，算法性能为 CDS-LO-1<CDS-LO-2<CDS-LO-3；以虚拟骨干网的延迟为标准，算法性能为 CDS-LO-1>CDS-LO-2>CDS-LO-3。用户可以根据需要选择合适的连通支配集算法来构建网络的虚拟骨干网，例如对于实时性要求较高的应用，可以采用延迟低的骨干网构建算法；对于实时性要求较低的应用，可以采用骨干节点数量更少的算法从而节约网络能耗。本文的第二个主要工作是对通信范围不同的异构无线自组织网络中的虚拟骨干网构建算法进行了研究。基于经典数学问题“圆包装”(Circlepacking)、“球包装”(Spherepacking)、和“球编码”(Sphericalcode)，本文在节点通信范围不同的无线自组织网络中给出了基于最大独立集的上界，证明了基于最大独立集的连通支配集算法在节点通信范围不同的情形下仍然能够得到较低的常数近似度。#p#分页标题#e#
..........
参考文献（略）
