||Mobile applications, such as cellular phone service, digital imaging, and portable computing are driving the need for high-bandwidth wireless communication networks. Wireless communication introduces new (spatial) constraints on the design and operation of communication networks. For example, the power required to transmit information via radio waves is heavily dependent on the Euclidean distance between the sender and the receiver(s). Important challenges range from very basic tasks, involved in building the infrastructure between the network nodes, to high level tasks, involved in routing signals. An example of a low-level task is the assignment of frequencies or time slots such that no interference between nearby stations occurs. An example of a high level task is routing messages from node A to node B using at most k intermediate stations and minimizing the amount of energy required to transmit messages. Since wireless nodes in a network are typically battery-powered devices, the efficient power management of these units becomes a major issue when designing network topologies and protocols.
We are exploring a new approach to wireless networking by combining computational geometry with algorithm theory to develop new and interesting protocols and network designs. For example, we recently created a new datastructure that, for a given wireless network topology, answers k-hop queries for energy-efficient paths in constant time. We plan to extend our approach to other communication networks, such as those involved in broadcasting.