Algorithms for ad hoc and sensor networks

Wireless and mobiles networks are excellent playground for researchers with an algorithm background. Many research problem turn out to be variants of classic graph theory problems. In-particular the rapidly growing areas for ad hoc and sensor networks demand new solutions for timeless graph theory problems, because: (i) wireless devices have lower bandwidth and (ii) wireless devices are mobile and therefore the topology of the network changes rather frequently. As a consequences, algorithms for wireless and mobile networks should have: (i) as little communication as possible and should (ii) run as fast as possible. Both goals can only be achieved by developing algorithms requiring a small number of communication rounds only (so-called local algorithm). In the work we present a few algorithmic applications in wireless networking, such as clustering, topology control and geo-routing. Each section is supplemented with an open problem. (c) 2005 Elsevier B.V. All rights reserved.