This project develops efficient routing schemes for large scale multi-hop wireless sensor networks with a complex shape. As sensor networks grow large in size, terrain features or non-uniform energy usage may leave the network with holes. Efficient routing becomes difficult as some knowledge of how to "get around" the holes is needed.
The novelty of this project is to use conformal geometry to compute a proper embedding of the network such that simple, distributed greedy routing schemes achieve desirable properties. Conformal geometry shows that any surface can be deformed to three canonical shapes: the sphere, the plane and the disk. Thus, one can "regulate" any sensor field shape to be of a canonical, simple form. The complexity of the routing problem and the domain specifics are encapsulated in the embedding such that routing decision becomes trivial. The conformal mapping of a sensor network is computed using Ricci curvature flow, an intrinsically distributed computation routine that can easily incorporate the dynamic changes of wireless links. This project focuses on conformal mapping and the companion greedy routing solutions that guarantee delivery, achieve good load balancing, facilitate in-network storage and data-centric routing, are resilient to network failures, and generalize to both 2D and 3D networks.
This project explores the unique cross-disciplinary area of wireless networking and differential geometry. Although the main thrust of this proposal is theoretical, it is expected that the project can also provide practical routing solutions for large scale sensor networks.
This project produced a systematic set of solutions for efficient routing in large scale wireless sensor networks, using mapping of spaces through conformal geometry. A wireless sensor network aims to provide high resolution, blanket coverage of a target domain of interest by wireless sensor nodes. When a sensor network spans to cover a large domain, it is common to expect that the domain is non-homogeneous such that the presence of special domain features (e.g., obstacles) forbids sensor placement. The network is thus dense everywhere except a few of these large `holes’. How to handle these holes in network management, when the nodes have limited resources, becomes very challenging. Take the example of a very intuitive routing strategy named greedy routing. A node delivering a message towards a destination will pick its neighbor whose Euclidean distance to the destination is the smallest. In other words, the message moves in a greedy manner, minimizing the distance to the destination in each hop. However, when the network has holes, greedy routing may get stuck at a hole, when all neighbors are further away from the destination. How to revive the message in this situation has been a popular research topic in the recent years. In this project we provided a family of solutions using conformal geometry which enables us to compute a global mapping of the original domain to a target, `virtual’ domain with a nicer shape. For example, we can make all holes circular in the virtual domain, since greedy routing in such a circular domain never gets stuck. This would eliminate the need of any recovery scheme from the local minima entirely and present an extremely simple routing solution. We show that the computation of this mapping can be carried out in two different ways. In the first method, all nodes collaboratively compute the mapping in a distributed manner. Each node arrives at its own virtual coordinate at the end of the iterative, gossiping process. In the second method, we show that this conformal mapping of the continuous underlying domain could be pre-computed and stored in a compact form on all sensor nodes before their deployment. Thus a node can easily calculate its new virtual coordinate upon location change, extending the scheme for routing in mobile networks. Beside guaranteed delivery, we can also achieve multiple additional desirable routing objectives, all derived from the unique property of a conformal mapping. For example, greedy routing on a circular domain may accumulate high traffic load on the interior hole boundaries. To alleviate that, we can reflect the network along a hole boundary using a Mobius transformation and map a copy of the network to cover the interior of the hole, recursively. Routing on this universal covering space makes traffic load more balanced as hole boundaries essentially `disappear’. In another case, when there are sudden link or node failures, we can apply a Mobius transformation to generate a different circular domain, with the sizes and positions of the holes rearranged, on which greedy routing generates a different path. Thus quick recovery from a spontaneous failure is possible. We also applied hyperbolic conformal mapping to map the domain with the holes cut open to a convex polygon that can tile up the entire hyperbolic plane. This mapping supports greedy routing with specified `homotopy types’, i.e., routes that go around holes in different ways. Hyperbolic embedding can be generalized to 3D sensor networks with complex topology as in the case of monitoring underground tunnels [6]. Advanced applications of conformal geometry include generation of `space filling curves’ for arbitrary domains, traffic analysis of random walks for location of message sources, etc. In summary, using continuous mapping of the sensor field to `simplify’ a sensor network shape proves to be useful for numerous fundamental networking problems. The abstraction of the network shape separates the low-level, fuzzy, dynamic, complex behaviors of wireless communication, from the high-level, stable, resilient global topological features. Our innovative use of such abstraction enabled a unique set of scalable, lightweight solutions for resource constraint sensor nodes.
