Research On QoS-Guaranteed Scheduling Technology For Wireless Ad Hoc Networks

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.