Geographic Routing in d-Dimensional Spaces With Guaranteed Delivery and Low Stretch

Almost all geographic routing protocols have been designed for 2-D. We present a novel geographic routing protocol, named Multihop Delaunay Triangulation (MDT), for 2-D, 3-D, and higher dimensions with these properties: 1) guaranteed delivery for any connected graph of nodes and physical links, and 2) low routing stretch from efficient forwarding of packets out of local minima. The guaranteed delivery property holds for node locations specified by accurate, inaccurate, or arbitrary coordinates. The MDT protocol suite includes a packet forwarding protocol together with protocols for nodes to construct and maintain a distributed MDT for routing. We present the performance of MDT protocols in 3-D and 4-D as well as performance comparisons of MDT routing versus representative geographic routing protocols for nodes in 2-D and 3-D. Experimental results show that MDT provides the lowest routing stretch in the comparisons. Furthermore, MDT protocols are specially designed to handle churn, i.e., dynamic topology changes due to addition and deletion of nodes and links. Experimental results show that MDT's routing success rate is close to 100% during churn, and node states converge quickly to a correct MDT after churn.