Research On Technologies In Wireless Ad Hoc Network Based On Quasi-birth- And -death Process

Wireless Ad Hoc network is widely used in both military and civil area due to its inherent deployment flexibility and survivability characterisic. The rapid changed topology, limited bandwith/resources together with transmission confliction upon shared wireless channel bring big challenges to further development of Ad Hoc network, meanwile, make related technologies research focus.In this dissertation, based on birth-and-death and quasi-birth-and-death stochastic process, research has been performed on several Ad Hoc network technologies including clustering algorithm, node failure/maintainence policy and medium access control protocol. Specifically, the studies are composed of following aspects:1) A birth-and-death model is established to describe the request handling process of cluster head node in a hierarchical Ad Hoc network employing multi-channel mechanism. Based on probability analysis, blocking probability and average utilization of channel are introduced as addtional cluster head election factors to improve Adaptive On-demand Weighted(AOW) algorithm. Simulation results show that it can effectively eliminate blockings due to the limitation of cluster head capacity and at same time can boost the average service time of cluster head.2) Due to the fact that failure of any node may cause communication link broken, which in turn results in route re-discovery, re-transmission of data packet, and finally degration of netowrk performance, repairation/maintainence process should be triggered in time when node failure is detected, while on the other hand, the process triggering should be limited to avoid over-burden. A Sub-Tree-BD model is created for spanning tree during on-demand routing in Ad Hoc network, matrix analysis is performed to get the solution of corresponding differential equation for the model and the birth and death of spanning tree in the network. Based on Sub-Tree-BD model, a quasi-birth-and-death model is created for node failure and sub-tree maintainence process. Probability analysis is then performed and the relationship expressions between node failure rate, sub-tree maintainence idel policy and system overhead are obtained.3) Research upon 802.11 Distributed Coordination Function(DCF) protocol is performed, by considering packet arrival rate, maximum retry time and buffer size, quasi-birth-and-death models are established to accurately describe node packet transmission procedure, for single-hop network and multi-hop network, respectively. Research is then be categorized by whether buffer size is infinite:when buffer size is infinite, the saturation condition is obtained and the equations to determinate packet arrival threshold is provided; when buffer size is finite, stationary distribution is solved and probability expression for packet loss rate, average delay are provided. Model effectiveness is proven by simulations. The results can be used to prevent network saturation by restraining data rate and to verify whether a routing protocol is suitable for a particular network size.4) Based on the finite quasi-birth-and-death model of multi-hop network and the Binary Exponential Backoff(BEB) algorithm, a dynamic maximum retry time back off algorithm upon MAC layer is proposed, which attempts to find an adaptable maximum retry time based on transient packet arrival rate to satisfy Quality of Service(QoS) requirements on both packet delay and packet loss. If the maximum retry time can be found, it will then be used to control transmission retries; otherwise, a back feed will be generated for upper layer to slow down the packet generation rate. Simulations show that the algorithm can effectivly balance average delay and packet loss requirement under lower data rate.