One of the challenging tasks in the deployment of dense wireless networks (like sensor networks) is in devising a routing scheme for node to node communications. Important considerations are scalability, routing complexity, the length of the communication paths and the load sharing of the routes. In this paper, we show that a compact and expressive abstraction of network connectivity by the medial axis enables efficient and localized routing. The main contribution in this paper is MAP, a Medial Axis based naming and routing Protocol that is location-free (no location information is needed), makes routing decisions locally, and achieves good load balancing. In its preprocessing phase, MAP constructs the medial axis of the nodes, defined as the set of nodes with at least two closest boundary nodes. The medial axis of the network captures both the complex geometry and non-trivial topology of the sensor field. It can be represented compactly by a graph whose size is comparable with the complexity of the geometric features (e.g., the number of holes). Each node is then given a name related to its position with respect to the medial axis. The routing scheme is derived through local decisions by the names of the source and destination nodes and guarantees delivery with reasonable and natural routes. We show by both theoretical analysis and simulations that our medial axis based geometric routing scheme is scalable, produces both short routes and excellent load balancing, and is very robust to variations in network model.

---

Locating and Bypassing Holes in Sensor Networks

In real sensor network deployments, spatial distributions of sensors are usually far from being uniform. Such networks often contain regions without enough sensor nodes, which we call holes. In this paper, we show that holes are important topological features that need to be studied. In routing, holes are communication voids that cause greedy forwarding to fail. Holes can also be defined to denote regions of interest, such as the "hot spots" created by traffic congestion or sensor power shortage. In this paper, we define holes to be the regions enclosed by a polygonal cycle which contains all the nodes where local minima can appear. We also propose simple and distributed algorithms, the TENT rule and BOUNDHOLE, to identify and build routes around holes. We show that the boundaries of holes marked using BOUNDHOLE can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.