论文部分内容阅读
广播是无线自组织网络(简称无线自组网)中最基本的数据传输方式之一，常用于消息扩散、路由建立、数据查询、服务发现等多种场景，是无线自组网的一个重要研究方向。近年来，作为一种有效的节能方式，睡眠调度技术在无线自组网中得到了广泛应用。然而，在节省能源的同时，睡眠调度也为广播问题的研究带来了新的挑战。在带有睡眠调度的无线自组网中，由于受到节点周期性睡眠的影响，广播问题变得比在一般无线自组网中更加复杂。传统的广播算法不需考虑睡眠状态，即假设节点始终处于唤醒状态，因此在采用了睡眠调度的无线自组网中应用时会出现时延增加、甚至发送不成功等问题。如何在带有睡眠调度的网络环境中设计有效的广播算法，成为了无线自组网中广播问题研究的新难点。 本文针对无线自组网睡眠调度感知的广播问题进行了深入研究，探讨在给定节点睡眠调度规律的情况下，如何设计有效可行的广播算法，并针对广播问题的两大关键性能指标传输次数和广播时延进行了优化。具体贡献可以概括为以下三个方面: (1)针对睡眠调度带来的节点周期性可用问题，我们对如何设计合理的睡眠调度感知广播算法进行了研究。首先对睡眠调度感知的广播算法问题进行分析，并详细讨论了算法设计的具体目标，进而根据讨论的结果，提出了一种睡眠调度感知的局部化广播算法SALB。SALB借助于经典的连通支配集局部化构造方法来生成广播虚拟主干，并采用根据节点唤醒时刻进行发送的数据转发机制，使广播数据包能够正确地在网络中进行传输。进一步，我们采用启发式方法减少了广播的冗余和时延。理论分析和模拟实验证明了SALB算法在传输次数和广播时延上均具有良好的表现。 (2)针对广播传输次数的优化问题，我们对睡眠调度感知的最少传输广播问题(Sleeping Schedule-aware Minimum Transmission Broadcast-MTB-SA)进行了研究。我们首先证明了MTB-SA问题是NP难的，然后在对带有睡眠调度网络中节点传输特性进行考察的基础上，提出了一种新的基于集合覆盖的近似方案，并根据此方案分别设计了集中式和分布式的广播算法:CSCA和DSCA。理论分析证明此两种算法具有良好的近似率。模拟实验表明了两者的性能均比传统算法有了较大提升。 (3)针对广播传输时延的优化问题，我们对睡眠调度感知的最短时延广播问题(Sleeping Schedule-aware Minimum Latency Broadcast-MLB-SA)进行了研究。我们首先对MLB-SA问题进行描述和建模，并证明了它也是一个NP难的问题。接着在网络中构造一棵以广播源节点为根的最短路径树(Shortest Path Tree-SPT)以确定数据发送的最优节点次序，并在此基础上采用分层着色的方法进行冲突调度，循序渐进地提出了两种近似算法:简单的和改进的分层着色广播算法SLAC与ELAC，并通过理论分析和模拟实验对算法的近似率和性能进行了分析和比较。实验结果表明两者均有效地节省了广播的时延。