Routing Metric Designs for Greedy, Face and Combined-Greedy-Face Routing

Different geographic routing protocols have different requirements on routing metric designs to ensure proper operation. Combining a wrong type of routing metric with a geographic routing protocol may produce unexpected results, such as geographic routing loops and unreachable nodes. In this paper, we propose a novel routing algebra system to investigate the compatibilities between routing metrics and three geographic routing protocols including greedy, face and combined-greedy- face routing. Four important algebraic properties, respectively named odd symmetry, transitivity, source independence and local minimum freeness, are defined in this algebra system. Based on these algebraic properties, the necessary and sufficient conditions for loop-free and delivery guaranteed routing are derived when greedy, face and combined-greedy-face routing serve as packet forwarding schemes or as path discovery algorithms respectively. Our work provides essential criterions for evaluating and designing geographic routing protocols.