Maximal throughput scheduling based on the physical interference model using learning automata

Wireless link scheduling is one of the major challenging issues in multi-hop wireless networks when they need to be designed in distributed fashion. This paper improves the general randomized scheduling method by using learning automata based framework that allows throughput optimal scheduling algorithms to be developed in a distributed fashion. A distributed scheduling algorithm that operates on more realistic conflict graph was proposed based on the physical interference model. This model uses a combination of a distributed learning automata based on the pick algorithm and an algorithm that compares successive scheduling solutions. Comparison was made by creating spanning tree on the conflict graph of the two consecutive schedules. Briefly, a distributed scheduling schemes was proposed, that: (i) is throughput optimal, (ii) intelligently choose links for new schedule, and (iii) message and time complexity is in O(n3).