Path-loss fluctuations towards robust scheduling algorithms in the SINR model

The SINR model has attracted much attention in the field of wireless networks. The path loss exponent α in the model is generally treated as a constant between two and six. However, in real scenarios, the path loss is influenced by many factors such as environment (vegetation and barriers), propagation medium (dry or moist air), the distance between the transmitter and the receiver, etc. Therefore, the exact value of α is hard to detect in real scenarios and the attenuation of signal powers transmitted through different areas varies, which causes the value of α to ebb and flow among all wireless requests. In this paper, we initiate the study about the impact of α that fluctuates on the SINR model. We prove that for any given and the fluctuation δ, a specific topology can always be constructed which is extremely vulnerable to the small change in α and all the existing algorithms dealing with wireless network problems perform dramatically poorly with the inaccurate α value. We call algorithms that can still perform well despite the fluctuating α "α-Robust" algorithms and we propose the first α-Robust algorithm for the Connectivity Problem which generates a link schedule with size of O(log n log Δ) even in the worst case, where Δ is the ratio between the longest and the shortest links in a nearest neighbor tree.