Group:Lunch Meeting
Title: Path-Loss Fluctuations: Towards Robust Scheduling Algorithms in the SINR Model
Speaker: Guanyu Wang University
Time: 2011-12-22 12:00-2011-12-22 13:30
Venue: FIT 1-222

Abstract:
The SINR model has attracted much attention recently in the field of wireless networks. The path loss exponent in this model, usually denoted by \alpha, is generally treated as constant that lies between two and six. However, in real scenarios, the exact value of \alpha is hard to find; in addition the attenuation of signal powers transmitted through different areas vary, which may cause the value of \alpha to ebb and flow among all wireless requests.

In this paper, we initiate the study about the impact of the an $\alpha$ that fluctuates on the physical (SINR) model. We prove that for any given \alpha and its fluctuation \delta, i.e. a path loss exponent that may vary between \alpha-\delta and \alpha+\delta, a specific topology can always be constructed which is extremely vulnerable to the small change of \alpha. This results in all existing algorithms dealing with different wireless network problems, like the maximization of network capacity or wireless link scheduling, may perform dramatically poorly with inaccurate path loss exponent in the SINR model. We call algorithms that still perform well despite a fluctuating \alpha \alpha-Robust'' algorithms.

After showing the upper bound, O(\frac{n}{\delta}), of a maximum concurrent links. We propose an \alpha-Robust algorithm that schedule a maximal number of concurrent links for arbitrarily node deployment whose size is O(\frac{n}{\delta \log n \log \Delta}), where \Delta is the the ratio between the longest and the shortest links in a nearest neighbor tree of the points.

Joint work with Zhaoquan Guand and Amy Wang

Short Bio: