Distributed Shortest Link Scheduling Algorithms With Constant Time Complexity in IoT Under Rayleigh Fading

Abstract

For the shortest link scheduling (SLS), i.e., scheduling a given set of links with minimum time slots, we consider the distributed algorithm design by using the locality of the protocol model with high fidelity under the Rayleigh fading. Different from most previous works, focusing on distributed algorithm design under the deterministic SINR model, which ignores the fading effects in signal propagation, we first show that a successful link of protocol model is also feasible under the deterministic SINR model, then it can be scheduled successfully with high probability under the Rayleigh fading, by upper-bounding interference outside interference range of protocol model. Then on the basis of this key conclusion, we design LLS-SLS algorithm to solve SLS within (2eΔmaxT + 1)δ log2 ΔmaxT time slots for a constant δ. Specifically, ΔmaxT is the number of a sender's neighbors within some certain range, and can be upper-bounded. Next, based on the concept of random contention, we design CLLS algorithm to schedule all links after costing 4(δ + 1)ΔmaxT ln (ΔmaxT + 1) time slots. In addition, extensive simulations evaluate the performance of two proposed algorithms.

Keywords

• Shortest link scheduling
• Rayleigh fading
• locality
• distributed algorithms