CAREER: Geometric Algorithms for Wireless Sensor Networks

Embedded networked sensing devices are becoming ubiquitous across many activities that are important to our economy and life. The physical locations of the sensor nodes greatly impact the system design in all aspects from low-level networking and organization to high-level information processing and applications.

This project takes a geometric approach to study algorithms in sensor networks and investigates a number of fundamental ideas about

o how the geometric embedding of sensor networks influences how the network can operate?

o how to exploit the geometric characteristics for efficient and scalable network design?

The project addresses a number of important architectural components where geometry has a fundamental influence, including localization, topology discovery, naming and routing, information discovery and brokerage, and mobility, in a harsh environment in which sensor networks operate:inaccuracy or unavailability in location information, limited resources such as bandwidth and energy, noisy or incomplete data, preferable distributed computation and high link or node failure rate. Expected results include the exploration of new models and abstractions, and novel geometric algorithms with provable performance guarantee in a probabilistic, dynamics and information incomplete world.

We expect that the exploration of sensor networks' rich geometric properties will reveal key insights that enable the creation of large-scale sensor networks. In addition, this interdisciplinary project provides a bridge between communities of computational geometry and wireless networking - identifying important geometric problems for the computational geometry community as well as supplying efficient algorithmic solutions for the networking community.