Modeling and test generation for worst-case performance evaluation of MAC protocols for wireless ad hoc networks

We propose a novel framework to critically analyze a given MAC protocol for wireless ad hoc networks with respect to its correctness criteria and performance metrics. The framework is composed of wanted state generation and test scenario generation algorithms. The wanted state generation algorithm generates a set of conditions that meet our study objective. The test generation algorithm then generates complete test scenarios that satisfy our objective, e.g., minimize the value of a particular performance metric. The core of our search engine utilizes novel algorithms that use combinations of goal-oriented backward and forward search and implications as well as heuristics that enable the generation of worst case scenarios in manageable complexity for our practical purposes. We demonstrate the effectiveness of our approach by using our framework to analyze the worst case performance, in terms of throughput and fairness of IEEE 802.11 for ad hoc networks. For all topologies, the worst case scenarios generated by our framework show the worst performance among all scenarios that we generate. The scenarios generated by our framework include the scenarios typically used for performance evaluation of IEEE 802.11 protocol. The case study of IEEE 802.11 shows that the complexity of our novel algorithms are quite practical.