Algorithmic Models for Wireless Networks

Abstract:
The design and analysis of algorithms requires appropriate models --
models that capture reality, yet are algorithmically usable; general,
yet analyzable.
The wireless setting has proved most challenging in this regard.

We first examine some of the recent progress on fundamental problems
in the so-called SINR or physical model. It captures some essential
aspects of reality, yet is usually coupled with an unrealistic
geometric assumption. We then indicate how this assumption can be
overcome, obtaining a model that fits closely with experimental
results. Perhaps surprisingly, nearly all the known theory of SINR
algorithms carries over without modification.

Finally, we brainstorm about extended models that capture more of the
challenging nature of wireless environments and technology.