Abstract:Interference among wireless signals hinders the concurrent transmission of signals and reduces the throughput of wireless networks. Link scheduling is an effective way to improve throughput and decrease transmission delay of wireless networks as the signal-to-interference-plus-noise ratio (SINR) model can accurately describe the inherent characteristics of wireless signal propagation and truly reflect the interference among wireless signals. Therefore, this study proposes an online distributed link scheduling (OLD_LS) algorithm in the dynamic wireless networks with the constant approximation factor of the SINR model. Specifically, online means that nodes can join and leave wireless networks at any time, and this arbitrary behavior of nodes reflects the dynamic characteristics of wireless networks. The OLD_LS algorithm partitions the network region into hexagons to localize the global interference of the SINR model. In addition, a leader election (LE) subroutine in dynamic networks is designed in this study. It is shown that as long as the dynamic rate of nodes is less than 1/ε, LE can elect a leader with a high probability in the time complexity of ${\rm{O}}(\log n + \log R)$, where ε is a constant satisfying $\varepsilon \leqslant {{5(1 - {2^{1 - {\alpha/ 2}}})} /6}$, with $\alpha $ being the path loss exponent, n the number of senders, and R the longest link length. To the best of our knowledge, the algorithm proposed in this study is the first OLD_LS algorithm for dynamic wireless networks.