Find in Library

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Δ_max^T + 1)δ log₂ Δ_max^T time slots for a constant δ. Specifically, Δ_max^T 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)Δ_max^T ln (Δ_max^T + 1) time slots. In addition, extensive simulations evaluate the performance of two proposed algorithms.