Mixing time and temporal starvation of general CSMA networks with multiple frequency agility

摘要

Mixing time is a fundamental property for a number of transient behaviors of stochastic processes, particularly, random access in CSMA networks. We use mixing time to characterize temporal starvation, which is a transient phenomenon where links can starve for prolonged periods indefinitely often despite having good stationary throughput. Considering a general CSMA network, we study a fundamental setting with multiple frequency agility, such that more than one frequency channel is available, and a link can transmit on at most one of the frequency channels not occupied by its neighbors. The characterization of throughput in such a setting is challenging, involving a hidden Markov chain of the associated stochastic process. This paper develops new results based on the mixing time of hidden Markov chains to shed light on the temporal starvation. Our analytical results quantify the effect of the number of frequency channels on temporal starvation. We provide sufficient and necessary conditions for fast mixing time of the corresponding hidden Markov chain.