Stochastic analysis of ant-based routing and probabilistic modeling of medium access control in wireless networks
Date
2015
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
In computer networks, routing determines how data move across a network from a source to a destination, while medium access control (MAC) defines when and how to transmit data from one node to another.Ant-based routing protocols have successfully provided an effective, if not optimal, solution to the routing problem by using control packets, called "ants", to explore networks, discover routes and reinforce the best routes. However, the modeling of ant-based routing in the context of wireless local area networks (WLANs) is challenged by the intrinsic complexity of wireless medium access control and its cross-layer interaction. Therefore, this dissertation mainly concerns two problems: improvement of an ant-based algorithm's performance on routing problem and mathematical characterization of medium access control for wireless local area networks. Our contributions are threefold. First we introduce a novel strategy for ant-based routing to achieve optimal solutions that have least hop count. Next, we modestly analyze the integrated behaviors of ant-based routing with medium access control based on the case investigations of a practical MAC protocol MACA (Multiple Access with Collision Avoidance). Finally, we develop a detailed Markov model according to the comprehensive descriptions of the Distributed Coordination Functions (DCF) in IEEE 802.11, an international standard that specifies access scheme for WLANs. This dissertation is organized as follows. Chapter 1 presents the background of routing and medium access control problems in WLANs, and reviews related research efforts on ant-based network routing and the IEEE 802.11 DCF. In Chapter 2, we show that our strategy leverages the previous efforts to model and analyze ant-based routing protocols on wired networks that explained how some critical parameters drive the network into near optimal route configurations. A simulation study of the strategy on both simple 5-node network and large 50-node network demonstrates a significant improvement on the discovery rate of stable single route solutions with minimum distance from a source to a destination as measured by hop count. In Chapter 3, we start by performing case studies to understand the MACA protocol based on a Markov chain analysis. The findings are incorporated into the previous analytical framework of ant-based routing protocol, and the predicted behaviors of the resulting integration model are validated through realistic simulations. A regression study is also conducted to evaluate MACA performance by packet delivery ratio in multi-hop wireless networks. Finally in Chapter 4, we give the detailed derivation of our new model for the IEEE 802.11 DCF. The validity of our model does not depend on the network parameters and topology. For steady state calculations, we approximate joint probabilities from marginal probabilities using product approximations. By assessing the model in a variety of representative networks, we find excellent agreement of equilibrium node states with realistic simulations of network traffic.