Statistical delay budget partitioning in wireless mesh networks

Wireless Mesh Networks (WMNs) are currently attracting strong attention due to their great potential in supporting multimedia applications with real-time transport with last-mile Internet access. Multimedia end-to-end transmission requires Quality of Service (QoS) guarantees. Mapping end-to-end QoS requirements into link QoS requirements is an important step for providing QoS in WMNs. Despite the importance of this functionality, it is yet to be addressed in WMNs or, more generally, in multihop wireless networks. Such mappings, however, have resulted in several algorithms being proposed for connection-oriented wired networks. The algorithms proposed, nevertheless, are either near-optimal or heuristics, and provide solutions for only one end-to-end requirement. In this paper, we propose a partitioning algorithm that is capable of partitioning multiple end-to-end QoS requirements simultaneously. We define QoS as the pair of the required end-to-end delay and the violation probability of meeting the required end-to-end delay. Our approach is motivated by experiments decisively showing that the delay probability distribution can be accurately characterized by a gamma or logistic distribution, thus there is not a specific one distribution that can characterize the delay. This conclusion is used to formulate a mathematical linear program that optimally partitions the end-to-end delay and the violation probability into link delays and link violation probabilities without imposing any specific delay distribution. Extensive simulation verified the effectiveness of the algorithm compared to two representative QoS partitioning algorithms. The proposed algorithm outperforms the other algorithms for loose and stringent QoS requirements, and over different path lengths.