  We study throughput-optimum localized link scheduling in wireless networks.
The majority of results on link scheduling assume binary interference models
that simplify interference constraints in actual wireless communication. While
the physical interference model reflects the physical reality more precisely,
the problem becomes notoriously harder under the physical interference model.
There have been just a few existing results on link scheduling under the
physical interference model, and even fewer on more practical distributed or
localized scheduling. In this paper, we tackle the challenges of localized link
scheduling posed by the complex physical interference constraints. By
cooperating the partition and shifting strategies into the pick-and-compare
scheme, we present a class of localized scheduling algorithms with provable
throughput guarantee subject to physical interference constraints. The
algorithm in the linear power setting is the first localized algorithm that
achieves at least a constant fraction of the optimal capacity region subject to
physical interference constraints. The algorithm in the uniform power setting
is the first localized algorithm with a logarithmic approximation ratio to the
optimal solution. Our extensive simulation results demonstrate correctness and
performance efficiency of our algorithms.
