Source: http://technodocbox.com/Computer_Networking/65516555-Routing-metric-designs-for-greedy-face-and-combined-greedy-face-routing.html
Timestamp: 2019-04-24 12:06:02+00:00

Document:
Download "Routing Metric Designs for Greedy, Face and Combined-Greedy-Face Routing"
1 Routing Metric Designs for Greedy, Face and Combined-Greedy-Face Routing Yujun Li, Yaling Yang, and Xianliang Lu School of Computer Science and Engineering, University of Electronic Science and Technology of China, China Dept. of Electrical and Computer Engineering, Virginia Polytechnic Institute and State University, USA Abstract 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-greedyface 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. Index Terms geographic routing, routing algebra, loopfreeness, delivery guarantee. I. INTRODUCTION Geographic routing, also called position-based routing, has received significant attention since it was originally proposed in   in the 980s. Compared with topology-based routing  , geographic routing has two unique benefits, especially for large-scale, highly dynamic and energy-constraint wireless networks. First, in geographic routing, a forwarding node transmits a packet only based on the positions of the destination node and its one-hop neighbors. The size of routing tables and the overhead of routing control messages are minimal. Second, the convergence time for geographic routing can be neglected. This is very attractive for highly dynamic wireless networks since it is extremely difficult to design fast-convergent topology-based routing protocols. These two benefits coupled with the progress on Global Positioning System (GPS) and self-configuring localization mechanisms   have promoted geographic routing as a promising solution for many wireless networks. The dominant design of geographic routing, which is also the focus of this paper, is Combined-Greedy-Face (CGF) routing, which is a combination of two routing schemes: greedy routing and face routing. Greedy routing tries to bring the message closer to the destination in each step using only local information. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view. Face routing helps to recover from dead end situation, where greedy routing hits a void and cannot find a suitable neighbor to the destination. Various methods can be used to define the most suitable neighbor for greedy routing, the time to switch between greedy routing and face routing, and the faces to be traversed by face routing. These methods are named routing metrics in this paper. Besides location information, many performance-affecting characteristics have been taken into account in the design of routing metrics for CGF routing recently. The performance of wireless networks can improve a lot due to these more complicated routing metrics  . However, the design of routing metrics cannot be arbitrary due to potential incompatibility with CGF routing, which may greatly degrade network performance and even create routing loops. For example, it has been pointed out in  that a projected-distance-based routing metric can create routing loops between two intermediate connected nodes in CGF routing. Unfortunately, despite the potential serious impact of routing metric designs on greedy, face and CGF routing, systematic analysis of such impact is still lacking in the current literature. The goal of this paper, hence, is to fill in this void and present an in-depth analysis about greedy, face and CGF routing s compatibility constraints on the design of routing metrics. This paper will focus on two aspects of the compatibility: loop-freeness and delivery guarantee. Loop-freeness refers that a routing protocol should never create any forwarding loop in any network topology at its stable state, and a forwarding loop indicates that a packet will be endlessly forwarded among several nodes which form a circle until the packet will be forcedly dropped due to lifetime is expired. Delivery guarantee refers that a packet initiated from any source node must be relayed to its destination by a routing protocol as long as there does exist a path between the source and the destination. To realize this goal, this paper proposes a novel routing algebra for greedy, face and CGF routing analysis. Using this algebra, four important routing algebraic properties, including odd symmetry, transitivity, source independence and local minimum freeness, are identified. These algebraic properties determine the compatibility between routing metrics and greedy, face and CGF routing. The remainder of this paper is organized as follows. Section II briefly introduces greedy, face and CGF routing. Section III establishes network model and proposes a routing algebra. Section IV systematically analyzes the requirements for realizing compatibilities when greedy, face and CGF routing are used as packet forwarding schemes. If greedy, face and CGF routing are regarded as path discovery schemes, the requirements for realizing compatibilities when combined with source routing and hop-by-hop routing are discussed in section V and VI respectively. Section VII illustrates the application of our theoretical resluts. Section VIII concludes our work and discusses the future directions.
2 Fig.. Most Forward Face Routing Fig.. Baseline for MFF Routing II. OVERVIEW OF GREEDY, FACE AND CGF ROUTING In this section, we first briefly discuss the design of greedy, face and CGF routing, and then discuss their roles in a routing system. A. The Design of of Greedy, Face and CGF Routing At each relaying node, greedy routing selects the locally optimal next hop from a set of candidate neighboring nodes, in the hope that it can approximate global optimal path. Although greedy routing is simple, it does not provide delivery guarantee. Different from greedy routing, face routing itself can be delivery guaranteed in a planar graph constructed using various existing methods (see a survey in ). There are several different variants of face routing which mainly differ in the decision about when and which face to traverse next. Due to space limitation, we just discuss a simple face routing scheme in this paper. Others can be analyzed in a similar way. In this routing scheme, the best neighboring face to the destination will be the next to traverse after the current face is completely explored. We called this routing scheme as Most Forwarding Face (MFF) routing. The face switching process of MFF can be illustrated by the following example. Assume there is a flow f s,d that needs to be delivered in a wireless network G(V, E). The reduced planar graph from G(V, E) is illustrated as Fig.. As a complete routing scheme, MFF routing starts at node s, and ends at node d. The dashed line sd is the baseline which decides the faces to be traversed by MFF routing. Face f is the first intersected face by sd. There are 3 intersection points y, y and y 3 between sd and the edges of face f. According to the well-known right hand rule, MFF routing first traverses all the edges of face f in clockwise order su, u u,..., u 5 u 6 and u 6 s, and then finds y 3 is the best intersection point to the destination d based on a routing metric definition. Hence, f 4 becomes the next explored face by MFF routing, and u 3 u 8 is the first traversed edge in f 4. MFF routing is similar to compass routing II . The only difference is that the baseline joining MFF routing s starting node and destination may not be a straight line segment. For instance, consider a wireless sensor network with a compromised zone as illustrated in Fig.. It is undesirable to route flows into the compromised zone. Hence, the solid curve is much better than the dashed straight line as a baseline for MFF routing, since the chance of passing nodes located in the compromised zone is much higher if the dashed straight line is used as a baseline. How to choose between all the possible baselines is the design issue of face routing s metrics. As a packet forwarding scheme, greedy routing is simple but provides no packet delivery guarantee. On the other hand, MFF routing provides packet delivery guarantee but is complicated and may create very inefficient paths. Hence, greedy routing and MFF routing often are combined together to form CGF routing where MFF routing is used as a recovery scheme for greedy routing and starts at dead ends for greedy routing. Note that MFF routing s routing metric may be different from greedy routing. B. The Roles of Greedy, Face and CGF Routing The compatibility between greedy, face and CGF routing schemes and routing metrics depends on how these geographic routing schemes are used in a routing system. There are two fundamentally different ways of applying these routing schemes. The first approach is to treat these routing schemes as packet forwarding schemes so that for every arriving packet, a relaying node locally decides and forwards the packet to this next-hop neighbor. The benefit of this approach is that a node does not need to keep any routing state regarding destinations or flows. On the other hand, since no routing state is kept in each node, techniques  that can shorten pure CGF routing s paths cannot be used. In the second approach, these geographic routing schemes can be used as on-demand route discovery mechanisms and be combined with different traditional packet forwarding schemes to form various routing systems. By maintaining a small amount of routing states, various techniques  can be used to optimize pure geographic routing paths. Two widely used packet forwarding schemes can be combined with geographic routing. The first scheme is source routing, where a source node caches paths discovered by geographic routing and includes path information in its packet headers. Intermediate nodes then relay the flow based on the path information carried in forwarded packets. The second scheme is hop-by-hop routing, where soft states about the next hop is set along the path discovered by geographic routing. A source node only appends the destination address of a flow in its packet headers, and an intermediate node relays the flow based on its local soft states about the next-hop to reach the destination node. For both packet forwarding schemes, while a small number of soft states of discovered paths have to be maintained in either source nodes or relaying nodes, the benefit of reduced per-packet computation and message overhead as well as the enabling of path optimization techniques can be significant. III. NETWORK MODEL AND ROUTING ALGEBRA Greedy, face and CGF routing schemes have different compatibility requirements on routing metric design and their requirements also depend on their roles in a routing system. In this section, we introduce our network model and a novel routing algebra. They will be used to systematically analyze these compatibility requirements in the remainder of this paper.
3 3 A. Network Model A wireless network is modeled as a connected directed graph G(V, E) with cardinalities V and E. V is the set of vertices, and every vertex in the graph represents a node in the wireless network. Every link in the wireless network is mapped to a directed edge between the corresponding vertices. If nodes u and v can communicate directly, i.e. one is in another s physical radio range, there are two links with inverse direction between nodes u and v. The link uv is responsible for transmitting packets from node u to v, and the link vu is responsible for the inverse packets transmission. The link uv is called node u s out-going link and the link vu is called node u s in-coming link. In this paper, we assume edge-symmetrical graph where there must be an edge uv from vertex u to v if there is an edge vu from vertex v to u. Vertex v is named a neighbor of vertex u if there is an edge uv from the vertex u to v. The neighbor set N(u) of vertex u is the collection of its neighbor vertices. A path from the source vertex u to the destination u n can be represented by a sequence of vertices u u...u n where there is an directed edge from vertex u k to u k+ for k n. A path is simple if all vertices are distinct. A cycle is a path where all vertices are distinct except for the source vertex and the destination vertex. B. Routing Algebra The routing algebra, based on the connected directed graph, is a 4-tuple L, F, w,, where L : a set of labels, F : a set of traffic flows, w : a link weight function, : an order relationship. A label l uv in L describes the characteristics of the link uv, such as the geographical positions of nodes u and v, and packet loss ratio, energy consumption and the channel frequency. Each link in the wireless network is coupled with a label. Hence, the set L captures all the communication characteristics of the network. Furthermore, for face routing, to facilitate the representation of the conditions for face switching and greedy routing resuming, virtual links between locations that do not have nodes are introduced in the algebra. A virtual link xy between any points x and y in the network area is associated with a label l xy which captures the characteristics of its end points, such as their distance to the destination or compromised zones. The label of any virtual link is also included in the set L. A flow f s,d in F represents that there is traffic that needs to be delivered from node s to node d. The cardinality of F is less than or equal to V ( V ). w( ) is a function that calculates the weight of a link for different flows. w( ) has two variables. One is the label of a link and another is the flow. For example, for a flow f s,d, the weight of node u s out-going link uv is w(l uv, f s,d ), where l uv L denotes the label of link uv, and f s,d F indicates the existence of traffic demand between the source node s and the destination node d. is used to compare all the out-going links of a forwarding node based on w( ), so that the forwarded packets can be relayed through the lightest weight (i.e. best) link. If w(l uv, f s,d ) w(l ux, f s,d ), we say that link uv is lighter or equal to (i.e. not worse than) link ux for flow f s,d. Note that for greedy routing, not all the out-going links can be regarded as candidates for packet relaying. It is only those links who are strictly lighter than a threshold value φ can forward packets. φ is also tightly related to the switch point between greedy routing and face routing. Using the above novel routing algebra, we can discuss compatible routing metric design based on the following properties. Definition : Odd symmetry: l uv, l vu L, f s,d F, w(l uv, f s,d ) φ implies w(l vu, f s,d ) φ. Definition : Transitivity: l u u, l u u,..., 3 l u k u k L, f s,d F, w(l u u, f s,d ) φ, w(l u u, f 3 s,d ) φ,..., and w(l u k u, f k s,d ) φ imply w(l u u, f k s,d ) φ. Definition 3: Source independence: f s,d, f s,d F, l uv L, w(l uv, f s,d ) = w(l uv, f s,d ) is always satisfied. Definition 4: Local minimum free: f s,d F, l L, ud there does not exist a local minimal point for w( ) except the global minimal point d. Here node u may or may not be the node s. Note that x is a local minimum point of w( ) if there exists some ɛ > 0 such that x in x x < ɛ, we have w(l ux, f s,d ) w(l ux, f s,d ). The odd symmetry property states that for two links with opposite directions, only one of them can be in the candidate set of greedy routing. The transitivity property ensures that the progress to the destination is monotonic. The source independence property ensures that the selection of the nexthop for a packet is irrelevant to its source. The local minimum free property ensures the existence of monotonic progress between any two nodes along a baseline. It is worth noting that our routing algebra is different from Sobriho s routing algebra  , which focuses on analyzing the compatibility issues for link-state, distance vector and path vector protocols  . Geographic routing are substantially different from these routing protocols and, hence, cannot be captured by Sobrinho s routing algebra. IV. REQUIREMENTS WHEN GREEDY, FACE OR CGF ROUTING USED AS A PACKET FORWARDING SCHEME Odd symmetry, transitivity, source independence and local minimum freeness are important algebraic properties that determine compatibilities between geographic routing and routing metrics. In this section, we systematically analyze the requirements for realizing compatibilities when greedy, face or CGF routing is used as a packet forwarding scheme. The requirements for realizing compatibilities when these routing schemes are used as path discovery algorithms will be discussed in sections V and VI. Without loss of generality, our discussion of face routing is based on the representative MFF routing, whose design is introduced in section II-A.
7 7 w g (l v v, f s,d ) w g (l v u, f s,d ), w g (l, f wd s,d ) φ w g (l wv, f s,d ) w g (l wv, f s,d ). Hence, the path s uv v wd is discovered by the greedy routing algorithm for flow f s,d, while the path s uv v wd is discovered for flow f s,d due to the lack of source independence property. Assume flows f s,d and f s,d occur simultaneously. The route reply messages for f s,d and f s,d are respectively M sd and M sd. After setting up the routing table in node v as destination = d, next hop = w, M sd leaves for node v. At the same time, M sd sets up the routing table in node v as destination = d, next hop = w, and leaves for node v. After M sd reaches node v, the routing table in node v is renewed as destination = d, next hop = v. The same thing happens when M sd arrives at node v, and the routing table in node v is updated as destination = d, next hop = v. After the route discovery phases of these two flows are finished, a loop between nodes v and v is created for both f s,d and f s,d. Considering the complications of traffic flows, this case is possible to happen in real networks. Theorem 8: A greedy routing based forward building hopby-hop routing protocol GR is loop-free if and only if the routing metric has two properties: odd symmetry and transitivity. The proof for necessary condition is straightforward since without odd symmetry and transitivity, a loop may be created in the route discovery phase as illustrated in the proof of theorem. To prove that a loop cannot exist, we next show that any forwarding path created by nodes routing entries must be in the increasing order of these entries latest setup times. Take any routing entry E i,d in node u i as an example, where E i,d specifies node u i s next hop denoted as u i+, to destination d. Assume that the latest setup time of E i,d is t i and the latest setup time for u i+ s entry E i+,d is t i+. This implies that at t i, a route confirmation message M sxd caused by flow f sx,d visited u i and set up E i,d. Message M sxd then would be forwarded to the next hop u i+ and set the routing entry E i+,d at a time t i+. We always have t i+ > t i since a message M sxd itself cannot create a routing loop with the odd symmetry and transitivity properties. The latest setup time of E i+,d, possibly done by another confirmation message M syd caused by a different flow f sy,d, hence is lower bounded by t i+. Hence, we have t i+ t i+ > t i. Given a cycle of forwarding path u, u,..., u k, u, their corresponding forwarding entries latest set up times must satisfy t < t, t < t 3,..., t k < t k and t k < t. We can then desire the contradiction that t < t k and t > t k. Hence a cycle does not exist. Theorem 9: A MFF routing based backward building hopby-hop routing protocol F R may create routing loops even if the routing metric has local minimum free property. We prove it through a simple example. Consider the example in Fig. 5 which is a planar graph. Assume flows f s,d and f s,d occur simultaneously. The curves s d and s d are the baselines for MFF routing, and they are local minimum free with d as the global minimum point. The curve s d only intersects one face, i.e., the exterior face f 4. According to the right hand rule, the path s s u u u 3 d is discovered for flow f s,d. The curve s d intersects 3 faces, i.e., f, f and f 3. Based on the right hand rule, the simple path s s u 5 d is discovered for flow f s,d. Hence, the route reply message M sd to the source node s carries the path s s u u u 3 d, and the route reply message M sd to the source node s carries the path s s u 5 d. In the routing tables building process, consider the possibility that M sd arrives at node s and M sd reaches node s at the same time. Hence, the routing table in node s is set to destination = d, next hop = u and then M sd leaves for node s. At the same time, the routing table in node s is set to destination = d, next hop = u 5 and then M sd leaves for node s. Once M sd reaches node s, the routing table in node s is renewed as destination = d, next hop = s. The same thing happens when M sd arrives at node s, and the routing tables in node s is updated as destination = d, next hop = s. After the route discovery phase of these two flows finishes, a loop between nodes s and s is created for both f s,d and f s,d. Considering the complications of traffic flows, this case is possible to happen in real networks. Theorem 0: A MFF routing based forward building hopby-hop routing protocol F R is loop-free and packet delivery guaranteed if and only if the routing metric has the local minimum free property. Obviously, if the routing metric lacks the local minimum free property, a loop may be created or MFF routing will incorrectly end in route discovery phase. Hence, we only need to prove the sufficient condition. Based on the theorem, a path can be discovered by MFF routing F R between any two nodes in a wireless network if the routing metric has the local minimum free property. Furthermore, packet delivery guarantee can be proved in a similar way as the proof in theorem 8. In a similar discussion, we can draw the following conclusion. Theorem : A CGF routing based forward building hopby-hop routing protocol R is loop-free and packet delivery guaranteed if and only if the routing metric for its greedy routing algorithm GR has the odd symmetry and transitivity properties, and the routing metric for its MFF routing algorithm F R has the local minimum free property. VII. CASE STUDIES In this section, we show how to use our theoretical results to analyze routing metrics by using four routing metrics as examples. A. Most Forward within Radius (MFR) MFR metric is originally designed for greedy routing where a packet is forwarded to the closest node to the destination among all the neighbors of the forwarding node that are closer to the destination than the forwarding node .
8 8 For MFR metric, the label of a link l uv is defined as l uv = (x u, y u ), (x v, y v ), where (x u, y u ) and (x v, y v ) are the geographic position of nodes u and v respectively. The w( ) function of MFR metric is defined as: w(l uv, f s,d ) = v, d u, d = (x v x d ) + (y v y d ) (x u x d ) + (y u y d ) () where v, d is the Euclidean distance between nodes v and d. The preference operator is the common less than or equal to ( ) operator for real numbers. The threshold φ for greedy routing is 0, i.e., it is only when w(l uv, f s,d ) < 0 is satisfied that a packet of f s,d can be relayed through link uv. The baseline for face routing is the straight line segment joining the MFF routing s starting node and the destination, which is local minimum free and the global minimal point is the destination. It is easy to know that MFR metric has odd symmetry, transitivity, source independence and local minimum freeness properties. Hence, we can conclude as follows: i: As packet forwarding schemes, greedy routing with MFR metric is loop-free. MFF routing and CGF routing with MFR metric are loop-free and packet delivery guaranteed. ii: Treating greedy routing as the path discovery algorithm, its combination with source routing and MRF metric is loopfree. MFF routing or CGF routing coupled with MFR metric and source routing is loop-free and packet delivery guaranteed. iii: Treating greedy routing as the path discovery algorithm, its combination with backward building hop-by-hop routing and MRF metric is loop-free. The combination of either MFF routing or CGF routing with MFR metric and backward building hop-by-hop forwarding scheme may create routing loops. iv: Treating greedy routing as the path discovery algorithm, its combination with forward building hop-by-hop routing and MRF metric is loop-free. The combination of either MFF routing or CGF routing with MFR metric and forward building hop-by-hop forwarding scheme is loop-free and packet delivery guaranteed. Same conclusions can be drawn for NFR , GRS , GEAR , the best P RR distance  and NADV  metrics through similar analysis. B. Random Progress Forwarding (RPF) RPF metric is a greedy routing metric . In RPF, a packet is forwarded to the neighbor who has the maximum positive projected progress on the straight line segment joining the forwarding node and the destination. In another word, the w( ) in RPF is: w(l uv, f s,d ) = u, v cos ud, uv ud, uv () = (x v x u ) + (y v y u ) cos ud, uv is the angle from the edge ud to uv, and the where is the operator in real numbers. The threshold φ for greedy routing is also 0. We can show that RPF metric lacks the odd symmetry property by Fig. 6. ' ' Greedy Routing Loop Based On RPF Metric Fig. 6 where both w(l uv, f s,d ) = u, v < 0 and w(l vu, f s,d ) = v, u < 0 are satisfied. However, RPF metric has the local minimum free property. For any two nodes, the straight line segment joining these two nodes has no local minimum and the destination node is the global minimum point based on RPF metric. Hence, we can conclude as follows: i: Either as packet forwarding schemes or as path discovery algorithms, greedy routing and CGF routing with RPF metric are not loop-free. That is to say, RPF is not a usable metric for greedy routing and CGF routing. ii: Either as a packet forward scheme or as a path discovery algorithm combined with source routing or forward building hop-by-hop routing, MFF routing with RPF metric is loopfree and packet delivery guaranteed. However, if combined with backward building hop-by-hop routing, MFF routing with RPF metric may create routing loops. C. Line Progress Forwarding (LPF) LPF metric is also based on the projected distance, however, other than RPF metric, it is a usable metric for greedy routing in some cases. The only difference between LPF and RPF is that, for LPF metric, it is the straight line segment joining the source and the destination where the progress is projected. Hence, the w( ) function of LPF metric is: w(l uv, f s,d ) = u, v cos sd, uv = (x v x u ) + (y v y u ) cos sd, uv (3) where sd, uv is the angle from the edge sd to uv. It is easy to know that LPF metric has odd symmetry, transitivity and the local minimum freeness properties, but lacks source independence property. Hence, we can conclude as follows: i: As packet forwarding schemes, greedy routing with LPF metric is loop-free, and both MFF routing and CGF routing with LPF metric are loop-free and packet delivery guaranteed. ii: As on-demand path discovery algorithms, greedy routing with LPF metric and source routing is loop-free, and both MFF routing and CGF routing with LPF metric and source routing are loop-free and packet delivery guaranteed. iii: As on-demand path discovery algorithms combined with backward building hop-by-hop routing, greedy routing, MFF routing and CGF routing may create routing loops when they are coupled with LPF metric. iv: As on-demand path discovery algorithms combined with forward-building hop-by-hop routing, greedy routing with LPF metric is loop-free, and both MFF routing and CGF routing with LPF metric are loop-free and packet delivery guaranteed.
9 9 D. Virtual Force Forwarding (VFF) Consider the example in Fig, where there is a compromised zone that a routing protocol may want to avoid routing its packets through. A novel routing metric that reflects this consideration can be defined as: where α is a tradeoff coefficient, (x d, y d ) and (x h, y h ) are the coordinations of the destination and the center of the compromised zone, respectively. The component related to (x d, y d ) reflects the forwarding progress to the destination while the component related to (x h, y h ) captures the potential damage from the compromised zone. The preference operator is again the in real numbers. The threshold φ for greedy routing is 0. The baseline for face routing does exist but may not be a straight line segment, and it is a gradient curve joining MFF routing s starting node and destination. It is easy to know that VFF metric has odd symmetry, transitivity, source independence and the local minimum freeness properties. Hence, we can conclude as follows: i: As packet forwarding schemes, greedy routing with VFF metric is loop-free, MFF routing and CGF routing with VFF metric are loop-free and packet delivery guaranteed. ii: As on-demand path discovery algorithms combined with source routing, greedy routing with VFF metric is loop-free, MFF routing and CGF routing with VFF metric are loop-free and packet delivery guaranteed. iii: As on-demand path discovery algorithms combined with backward building hop-by-hop routing, greedy routing with VFF metric is loop-free, MFF routing and CGF routing with VFF metric may create routing loops. iv: As on-demand path discovery algorithms combined with forward building hop-by-hop routing, greedy routing with VFF metric is loop-free, MFF routing and CGF routing with VFF metric are loop-free and packet delivery guaranteed. VIII. CONCLUSIONS In this paper, we firstly discuss the necessity to analyze routing metric s impact on routing protocols, and then discuss the possible roles of greedy, face and CGF routing in a routing system. We propose a novel algebra and defined different algebraic properties to investigate compatibilities between routing metric and the three geographic routing protocols including greedy routing, MFF routing and CGF routing. The necessary and sufficient conditions for loop-free and delivery guaranteed routing are derived when greedy routing, face routing and CGF routing serve as different roles in a routing system. The applications of these conditions are illustrated by some different routing metric which are respectively based on Euclidean distance, projected distance and field of forces. Our work provides essential criterions for evaluating and designing geographic routing protocols. In our future work, we would like to analyze more variants of face routing with our algebra. ACKNOWLEDGMENT This work was supported in part by the US National Science Foundation (NSF) under grant CNS , by the Institute for Critical Technology and Applied Science (ICTAS) of Virginia Tech, and by China Scholarship Council. w(l uv, f s,d ) REFERENCES α = [ (x u x d ) + (y u y d ) α (x u x h ) + (y u y h ) ]  H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Transactions on Communications, vol. 3, no. 3, pp , 984. α [ (x v x d ) + (y v y d ) α (x v x h ) + (y v y h ) ] (4)  T.-C. Hou and V. Li, Transmission range control in multihop packet radio networks, IEEE Transactions on Communications, vol. 34, no., pp , 986.  D. B. Johnson and D. A. Maltz, Dynamic source routing in ad hoc wireless networks, Mobile Computing, vol. 353, 996.  C. E. Perkins and E. M. Royer, Ad-hoc on-demand distance vector routing, in Second IEEE Workshop on Mobile Computer Systems and Applications, 999.  S.-J. Lee and M. Gerla, Dynamic load-aware routing in ad hoc networks, Communications, 00. ICC 00. IEEE International Conference on, vol. 0, pp vol.0, 00.  H. Hassanein and A. Zhou, Routing with load balancing in wireless ad hoc networks, in MSWIM 0: Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems. New York, NY, USA: ACM, 00, pp  R. Draves, J. Padhye, and B. Zill, Routing in multi-radio, multi-hop wireless mesh networks, in MobiCom, 004.  P. Misra and P. Enge, Global Positioning System: Signals, Measurements and Performance. Ganga-Jamuna, 00.  A. Savvides, C.-C. Han, and M. B. Strivastava, Dynamic fine-grained localization in ad-hoc networks of sensors, in MobiCom, 00.  N. Bulusu, J. Heidemann, and D. Estrin, Gps-less low-cost outdoor localization for very small devices, Personal Communications, IEEE, vol. 7, no. 5, pp. 8 34, Oct  K. Seada, M. Zuniga, A. Helmy, and B. Krishnamachari, Energyefficient forwarding strategies for geographic routing in lossy wireless sensor networks, in SenSys 04: Proceedings of the nd international conference on Embedded networked sensor systems. Baltimore, MD, USA: ACM, 004, pp. 08.  Y. Yu, R. Govindan, and D. Estrin, Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks, UCLA Computer Science Department, Technical Report, 00.  S. Lee, B. Bhattacharjee, and S. Banerjee, Efficient geographic routing in multihop wireless networks, in MobiHoc, 005.  H. Frey, Scalable geographic routing algorithms for wireless ad hoc networks, Network, IEEE, vol. 8, no. 4, pp. 8, July-Aug  T. Melodia, D. Pompili, and I. F. Akyildiz, Optimal local topology knowledge for energy efficient geographical routing in sensor networks, in INFOCOM, 004.  H. Frey and I. Stojmenovic, On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks, in MobiCom, 006.  E. Kranakis, S. O. C. Science, H. Singh, and J. Urrutia, Compass routing on geometric networks, in In Proc. th Canadian Conference on Computational Geometry, 999, pp  B. Leong, S. Mitra, and B. Liskov, Path vector face routing: geographic routing with local face information, in ICNP, 005.  J. L. Sobrinho, Algebra and algorithms for qos path computation and hop-by-hop routing in the internet, INFOCOM, 00. , Network routing with path vector protocols: theory and applications, in SIGCOMM, 003.  T. G. Griffin and J. L. Sobrinho, Metarouting, in SIGCOMM, 005.  J. L. Sobrinho, An algebraic theory of dynamic network routing, Networking, IEEE/ACM Transactions on, vol. 3, no. 5, pp , Oct  Y. Yang and J. Wang, Design guidelines for routing metrics in multihop wireless networks, in INFOCOM, 008.  G. G. Finn, Routing and addressing problems in large metropolitanscale internetworks, ISI, Reports - Research, 987.  R. Nelson and L. Kleinrock, The spatial capacity of a slotted aloha multihop packet radio network with capture, IEEE Transactions on Communications, vol. 3, no. 6, pp , 984.
Power Aware Routing using Power Control in Ad Hoc Networks Eun-Sun Jung and Nitin H. Vaidya Dept. of Computer Science, Texas A&M University, College Station, TX 77843, USA Email: esjung@cs.tamu.edu, Dept.
Keywords-IEEE , multiradio wireless mesh networks (mr-wmns), Routing, selfreconfigurable networks, wireless link failures.

References: v. 
 v. 
 v. 
 v. 
 v. 
 v. 
 V.