Graph-Theoretic Complexity Reduction for Markovian Wireless Channel Models

Abstract

Accurate simulation and analysis of wireless networks are inherently dependent on accurate models which are able to provide real-time channel characterization. High-order Markov chains are typically used to model errors and losses over wireless channels.However, complexity (i.e., the number of states) of a high-order Markov model increases exponentially with the memory-length of the underlying channel. In this paper, we present a novel graphtheoretic methodology that uses Hamiltonian circuits to reduce the complexity of a high-order Markovmodel to a desired state budget.We also demonstrate the implication of unused states in complexity reduction of higher order Markov model. Our trace-driven performance evaluations for real wireless local area network (WLAN) and wireless sensor network (WSN)channels demonstrate that the proposed Hamiltonian Model, while providing orders of magnitude reduction in complexity, renders an accuracy that is comparable to the Markov model and better than the existing reduced state models.