The proliferation of wireless and sensor networks has intensified the need for intelligent design of their infrastructure. For any particular communication burst, it is best to involve only a small collection of nodes and links, in order to reduce interference and to lower node power (battery) demands. However, it is also best to use as short a path between nodes as possible. Simultaneously achieving these (and other) various operational goals in network design requires a deep understanding of what are called ?proximity structures,? mathematical models that encapsulate the relevant geometric and communication relationships in a network. Such understanding leads to network designs and routing algorithms that achieve nearly optimal tradeoffs among the conflicting criteria.
This research investigates network topologies and algorithms for wireless ad hoc/sensor networks, with the goal of constructing and handling dynamic updates of sparse distributed structures that achieve optimum interference, spanner paths between pairs of nodes, low weight (within a constant factor of the weight of a minimum spanning tree) and bounded degree. Efficient local constructions of optimal interference topologies will be integrated with pruning mechanisms to filter out unnecessary edges and with link redistribution methods to reduce the maximum degree at each node. These methods seek to achieve low communication complexity (constant to polylogarithmic number of communication rounds) to be employable in large scale networks. This research work also investigates extensions to the concept of wireless localization motivated by security issues in wireless networks.
