【作者】 张帆；

【导师】 曹叶文；

【作者基本信息】 山东大学 ， 通信与信息系统， 2014， 博士

【摘要】 近年来,无线Ad hoc网络凭借其便捷性、及时性和移动性等特点得到了广泛关注与应用。而这些特点也为Ad hoc网络协议与算法的设计带来了难度。为了保证服务质量(Quality of Service, QoS),需要在开放式系统互联(Open System Interconnection, OSI)模型中为每一层设计适合Ad hoc网络的算法和层间协议。传统的无线网络媒体接入控制机制IEEE802.11MAC协议无法提供实时业务的QoS保证,因此需要在802.11协议框架下设计基于QoS保证的分组业务调度策略以提高Ad hoc网络系统整体性能。调度策略设计作为Ad hoc网络及下一代无线网络通信发展的一项关键技术,有效地减少了链路干扰和冲突,控制了队列拥塞,增大了网络容量,以全局的方式实现网络资源的优化配置。因此,在无线网络中,基于优化的思想,在保证特定QoS性能指标的前提下分时隙的完成分组调度,对有效改善无线Ad hoc网络性能具有重要意义。本论文以排队论和资源分配理论为基础,提出一套基于吞吐量和端到端平均时延保证的调度性能评估方法,并从理论分析和实际应用两方面对调度策略原理进行深入研究,考虑各种网络环境,针对不同实现方式提出基于不同QoS保证的调度算法。此外,在多跳多路径业务流情况下,提出了基于吞吐量保证的跨层联合方案,为下一代无线通信网络协议设计提供了一定的理论依据和技术基础。本论文的主要工作和技术创新如下：第一,针对单跳信息传输网络,根据分组调度不同的实现方式,分别就集中式与分布式调度策略进行数学建模。而后,针对多跳多路径网络环境,建立了基于吞吐量保证的跨网络层路由选择和链路层调度的跨层联合方案模型。该模型将网络层与链路层联系起来,通过层与层之间的相互合作提高系统整体性能。建立调度模型之后,以排队论、马尔科夫理论为基础,基于李雅普诺夫分析法提出了一套调度策略性能评估理论框架,通过对整个网络系统的稳定性分析考察调度算法或跨层联合方案的吞吐量和端到端平均时延这两项重要的QoS性能指标。此框架是分组调度研究的方法论,用于分析在不同网络环境和流量模型下网络系统的稳定性、调度算法的吞吐量和平均时延性能,具有重要的理论指导意义。第二,根据集中式调度模型和调度算法性能评估理论框架,在无线单跳Ad hoc网络环境中,提出了基于时延改进的最大权重调度算法(Delay-enhanced Maxmum Weight Scheduler, DMWS).该算法基于系统负载因子ρ优化了调度权重。通过使用李雅普诺夫分析法,证明了DMWS可以保证较之经典的最大权重调度(Maximum Weight Scheduler, MWS)更紧的端到端平均时延。同时DMWS被证明可实现最大吞吐量容量区域,即吞吐量最优。第三,考虑单接口多信道网络场景和单跳流量模型,提出了基于随机接入和退避时间技术的低复杂度分布式信道分配与调度联合控制策略(Low-complexity Distributed Channel-assignment and Scheduling Algorithm, LDCSA)。在LDCSA中,采用速率比分配方式进行数据流量分配,将数据包合理的分配至各信道队列。在信道分配与调度阶段,采用一种基于概率的竞争接入策略,该策略需要链路之间的信息交互,这种信息交互可由RTS/CTS机制实现。使用李雅普诺夫分析法可以证明LDCSA可以保证稳定的吞吐量容量区域。同时,LDCSA的实现复杂度不随网络规模大小和可用信道个数的改变而改变,适合大规模网络系统应用。最后,在无线多信道Ad hoc网络中考虑多跳多路径流量环境,即每个数据源节点到目的节点有多个备选多跳路径供数据传输。在这种环境下,需要将网络层路由选择与链路层调度策略结合起来,设计基于QoS保障的跨层联合方案,以保证系统整体性能。根据本文提出的跨层联合方案理论框架,分别针对多接口多信道网络和单接口多信道网络设计了基于吞吐量保证的跨层联合方案：改进版多路径(Multi-Path, MP)方案、分布式路由与信道分配与调度(Distributed Routing, Channel-assignment and Scheduling, DRCS)方案和多路径LDCSA方案(Milti-path LDCSA, M-LDCSA)。其中改进版MP方案是对现有多接口多信道网络跨层MP方案的一般性改进,取消了原始MP方案中不合理的假设条件。而针对单接口多信道网络,DRCS和M-LDCSA分别是对现有的基于单跳网络的速率比最大多信道调度算法(Rate-Proportional Maximal Multi-Channel Scheduler, RPMMC)和LDCSA调度的多跳多路径扩展。本文提出的跨层联合方案综合考虑了路由选择问题和调度问题,基于调度算法合理的设计了路由选择机制,保证了整体吞吐量性能。更多还原

【Abstract】 Recently, wireless Ad hoc networks have received wide attention and application because of their characteristics such as convenience, timeliness and mobility. These features also brought difficult designing of network protocols and algorithms for Ad hoc networks. To guarantee Quality of Service (QoS), it is required to design algorithms and layer-to-layer protocols that fit Ad hoc networks for each layer of the Open System Interconnection (OSI) model. Traditional wireless networks media access control mechanism IEEE802.11MAC is unable to provide QoS guarantee for real-time services. Therefore, it is required to design packet scheduling policies based on QoS guarantees in the framework of802.11to improve the overall performance of Ad hoc network systems. Scheduling policy, as a key technology for the development of Ad hoc netwokrs and the next-generation wireless network communications, effectively reduced link interference and conflict, controled the queue congestion, increased network capacity, optimized the allocation of network resources in a global approach. Therefore, in wireless networks, based on the idea of optimization, completing packet scheduling in each time-slot on the premise of ensuring specific QoS performance requirements, has great significance for improving the performance of Ad hoc networks. On the basis of queuing theory and the theory of resource allocation, this dissertation put forward a set of evaluation methods for scheduling performances based on throughput region and end-to-end expected delay, conducted thorough research of the principle of scheduling policies from aspects of both theory analysis and practical application, proposed scheduling algorithms according to different implementations, different QoS indicators and various network environments. In addition, in the case of multi-hop multi-path traffic flows, this dissertation put forward cross-layer joint scheme based on throughput guarantees, and provided a certain theory basis and technology foundation for the designing of the next-generation wireless communication networks. The main contributions and innovations of this dissertation are as follows: Firstly, in single-hop cases, based on different methods of implementation, mathematic models of both centralized and distributed scheduling policies are established. Then, for multi-hop multi-path network environment, a model of cross-layer scheme crossing network layer and link layer is built based considering throughput guarantees. This model combines the network and link layer to improve the overall system performance. After modeling the scheduling policies, based on queuing theory, Markov theory and Lyapunov analysis, a set of performance evaluation theory frameworks of scheduling algorithms is proposed, which investigates the throughput and end-to-end expected delay of the scheduling policies or the cross-layer schemes through analyzing the stability of the whole network system. This framework is the methodology of packet scheduling research and provides important theoretical guidance.Secondly, according to the centralized scheduling model and the theory framework of scheduling performance evaluation, in wireless Ad hoc networks with single-hop flows, a Delay-enhanced Maximum Weight Scheduler, named DMWS, is put forward. This scheduler optimizes the scheduling weights based on the system loading factor. Using Lyapunov analysis, DMWS is proved to achieve a tighter delay upper bound than traditional Maximum Weight Scheduler (MWS) as well as maximum throughput region.Thirdly, considering multichannel wireless networks with single-interface nodes and single-hop traffic flows, a Low-complexity Distributed Channel-assignment and Scheduling Algorithm, named LDCSA, is proposed based on random access and backoff time technology. Under LDCSA, a rate-proportional data allocation is adopted to assign data packets to each channel queue reasonably. For channel-assignment and scheduling, a novel access strategy based on probability is put forward. Such strategy requires information exchange between links, which can be implemented by RTS/CTS mechanism. LDCSA is shown to be provably efficient with low complexity independent of both network size and the number of available channels.Finally, considering multi-hop multi-path traffic flows in multichannel Ad hoc networks, each source node has multiple alternative paths to route packets to destination. Under such circumstances, it is required to combine the network layer and the link layer to design QoS-guaranteed cross-layer scheme. According to the principle framework of the cross-layer scheme proposed in this dissertation, three thoughput-guaranteed schemes, respectively named modified MP, DRCS and M-LDCSA, are put forward for multichannel wireless networks with both single-interface and multi-interface nodes. Modified Multi-Path (MP) scheme is a general version of the original MP scheme. For single-interface cases, Distributed Routing, Channel-assignment and Scheduling (DRCS) and Multi-path LDCSA (M-LDCSA) are respectively the multi-hop multi-path extension of Rate-Proportional Maximal Multi-Channel Scheduler (RPMMC) and LDCSA. The cross-layer schemes proposed combines the routing selection and the scheduling, ensures stable throughput capacity region.更多还原