论文部分内容阅读
随着二十一世纪科技的飞速发展和硬件实现技术的不断成熟,无线自组网具备部署简单、组网灵活、易于扩展和鲁棒性强等特点,因而引起了学术界研究人员的高度关注,并在军事和商用领域中展现出广阔的应用前景。广播和数据聚合是无线自组网的重要操作。广播操作负责将节点的数据分发到整个网络中,经常用于传输路由控制信息、重要程序代码以及最新安全补丁等,是决定网络性能的重要因素。数据聚合操作首先利用聚合函数对网络节点要发送和已接收的数据进行聚合,然后将聚合后的数据传输给网关节点,是聚合无线自组网节点数据的重要手段,因而也是决定无线自组网性能的重要因素。在无线自组网的一些应用中,因为节点由电池供电,所以其能量非常有限。为了达到节能的目标,常见的方法包括:采用网络编码技术来减少节点的报文传输次数以及让节点定期睡眠处于占空比感知的场景等,其中占空比表示节点活跃时间与整个调度时间之比。本文围绕这两种节能场景,以提高报文接收率、降低能耗和延迟为目标,研究了无线自组网广播和数据聚合的多个最优化问题,并提出了高效的解决方案。主要研究工作包括以下四个方面。(1)在广播算法中应用网络编码是减轻并发传输对广播算法性能影响的有效手段。但是,很少研究工作对所提出的网络编码算法的最优性进行过系统的分析,从而其提出的网络编码算法往往不能获得最优的性能。因此,本文首先证明了在广播算法中应用网络编码所涉及的最优化问题是NP完全问题,然后提出了一种网络编码算法COMP。该算法利用贪婪集合配置算法和贪婪集合覆盖算法的基本思想来尽可能多地挖掘网络编码机会。最后,本文将COMP算法应用到现有广播算法中。仿真实验结果表明,COMP算法显著地提高了现有广播算法的性能,而且其获得的性能提高超过了现有的网络编码算法,在网络规模比较大、节点最大传输范围比较小以及会话比较多的场景中效果更显著。(2)针对占空比感知的无线自组网,本文研究了冲突避免最低延迟广播调度问题,目标是提供无冲突的广播调度,同时使得广播延迟最低。本文证明了一对全和全对全两类占空比感知的最低延迟广播调度问题都是NP完全问题。针对一对全广播调度问题,本文提出了一种近似算法OTAB。该算法根据节点之间的通信延迟构建最短路径树,然后利用最短路径树对节点进行分层、着色以及构建广播树,并基于广播树中父节点的颜色进行逐层广播调度,从而有效地避免了广播传输之间的信号冲突,并且降低了广播延迟。针对单位大小和无限大小两种报文模型下的全队全广播调度问题,本文分别提出了两种近似算法UTB和UNB。两种算法都包括两个过程:全对一数据收集和一对全广播。本文通过理论分析证明了三种算法都提供了正确的无冲突的广播调度,并给出了三种算法的近似比和时间复杂性,其中近似比表示近似算法与最优算法的广播延迟之比。另外,本文证明了三种算法的传输总次数最多都是最优算法的最小传输总次数的常数倍。仿真实验结果表明,OTAB算法的广播延迟和传输总次数都要低于现有算法,而UTB算法的广播延迟和传输总次数比UNB算法更容易受到网络参数的影响。(3)除了信号冲突之外,信号干扰也容易导致报文传输的失败,从而影响到网络性能。针对节点的干扰范围大于其传输范围的场景,本文研究了占空比感知的干扰避免最低延迟广播调度问题,并证明了一对全和全对全两类最低延迟广播调度问题都是NP完全问题。针对一对全广播调度问题,本文提出了一种直接从源节点进行广播调度的近似算法SIFBS。该算法采用一种合适的六边形布置和着色方法对节点进行着色,利用与节点之间通信延迟相关的最短路径树对节点进行分层并构建最大独立集,最后基于最大独立集中的节点颜色进行逐层广播调度,从而避免了广播传输之间的信号干扰,并且降低了广播延迟。为了降低最高广播延迟,本文还提出了另一种近似算法TCABS。TCABS算法基于延迟偏差条件来利用树中心节点协助源节点进行广播。针对无限大小报文模型下的全对全广播调度问题,本文提出了一种近似算法MILD。该算法通过两个过程来完成广播调度:数据收集过程和广播过程。本文通过理论分析证明了三种算法都提供了正确的无干扰的广播调度,并给出了三种算法的近似比和时间复杂性。另外,本文证明了三种算法的传输总次数最多都是最优算法的最小传输总次数的常数倍。仿真实验结果表明,SIFBS和TCABS两种算法的广播延迟和传输总次数都优于现有算法,TCABS算法的性能最好,而MILD算法的性能优于一种随机选取一个节点进行数据收集和广播的算法。(4)针对占空比感知的无线自组网,本文研究了如何提供数据聚合延迟最低的调度方案,使得所有网络节点的数据经过聚合后能快速地传输到网关节点并且所调度的传输之间互不干扰。本文证明该问题是NP完全问题,并提出了两种近似算法SDAS和CDAS。SDAS算法直接将所有网络节点的数据传输给网关节点。CDAS算法首先将所有网络节点的数据传输到网络的图论中心节点,然后通过最短路径将聚合后的数据从该图论中心节点传输到网关节点。本文通过理论分析证明了SDAS和CDAS两种算法都提供了正确的无干扰的数据聚合调度,并给出了两种算法的近似比、最大传输总次数以及时间复杂性。仿真实验结果表明,两种算法的数据聚合延迟明显地低于现有算法的扩展版。另外,除了节点传输半径比较大的场景,CDAS算法的数据聚合延迟都要低于SDAS算法。