19-09-2014, 10:47 AM
Face Routing in Wireless Ad-hoc Networks
[attachment=68152]
ABSTRACT
It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variantswhich simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedy face routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop.
1. INTRODUCTION
A wireless ad-hoc network consists of a collection of nodes that communicate with each other through wireless links without a pre-established networking infrastructure. It originated from battleelf communication applications, where infrastructured networks are often impossible. Due to its exibility in deployment, there are many potential applications of a wireless ad-hoc network. For example, it may be used as a communication network for a rescue-team in an emergency caused by disasters, such as earthquakes or oods, where xed infrastructures may have been damaged. It may also provide a communication system for pedestrians or vehicles in a city. Another example of a wireless ad-hoc network is a rooftop network [9, 12], which consists of a number of wireless nodes spread over an area to provide local networking service and access to wired networks, such as the Internet, for residents in the neighbourhood. Another application of wireless ad-hoc networks is a sensor network, which consists of a large number of small computing devices deployed in a region that collect data and may send the information to a central server
Related Work
Location-based routing is done using physical location information about nodes. This is a very dierent approach than traditional routing, in which nodes need to maintain routing information. Instead, location-based routing uses information about the geographic location of the neighbors of the current node to direct a packet to its destination.
In location-based routing protocols, it is assumed that nodes know their own locations and the source node knows the location of the destination node. A node equipped with a Global Positioning System (GPS) receiver can obtain its own geographic coordinates. When GPS support is unavailable, there are other localization techniques that mobile nodes can use. In order to obtain the location of the destination node, a location service is needed from which a node can query about the locations of other nodes. Most location-based routing protocols assume that a location service exists as an external resource. Indeed, in the literature, location service has often been considered as an independent research topic. For research in this area
3 Face Routing Variants
Face routing has been implemented in several variants which differ in the decision when current face traversal has to be interrupted and which face has to be explored next. In the following we list these face routing variants by re-ferrying to the well-established names of the entire protocols employing these strategies. It is important to note that the following descriptions explain the face routing part of these protocols only. The routing path in the accompanying examples might be different when running the entire protocol. However, as long it is clear from the context we interchange-ably use the well-established protocol names for both the entire protocol and its face routing part. As a general classification we can distinguish between face routing strategies which require that the message has to follow a sequence of adjacent faces which are intersected by the straight lines connecting the source node s with the destination node t. These strategies will be denoted as continuative strategies since they keep the line st as a reference during the whole routing process. In contrast, a volatile strategy will initialize planar graph routing each time a face change occurs. In other words, the node where a face change has occurred is treated as a planar graph routing start node again. According to this definition the first three of the following listed strategies are continuative while the remaining three are volatile ones.
Conclusions and Future Work
we presented our research on extending face routing to more general models of wireless ad-hoc networks. In order to investigate the extendibility of face routing, we developed a series of models with increasing generality. One important part of our research is to nd appropriate models through which we can better understand the difficulties of routing problems in more realistic network graphs than unit disk graphs. The graph models we considered gradually incorporate aspects of real networks, which en-abled us to identify deferent types of problems, to gain an understanding of the capability and limitations of face routing, and to nd techniques to extend the original face routing protocols.
We developed techniques that extend and generalize the face routing approach so that it can be applied directly on general non-planar network graphs, without separately constructing a plane routing sub graph. Our techniques also extend face routing to net-work graphs with unstable links that may change during the routing process. Using these techniques, we developed face routing protocols without the constraints suered by the face routing protocols in the literature.
We are interested in identifying conditions under which face routing can guarantee message delivery. Therefore, in our research, we focus on designing deterministic algorithms and providing theoretical proofs for guaranteed message delivery in each graph model. These results are important for applications where guaranteeing message delivery is critical.
Our results assumed that the destination node is stationary. With a mobile destination node, the routing problem becomes even more di cult. It is possible that face routing could be combined with an efficient location update scheme to guarantee message delivery in such networks. One example is the Last Encounter Routing scheme analysed in : a source node forwards a packet to the last known location of the destination node, which was its location at some time in the past. During routing, if a more up-to-date location of the destination is learned, then the packet is diverted to this new destination.
Another direction for future work is to in
[attachment=68152]
ABSTRACT
It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variantswhich simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedy face routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop.
1. INTRODUCTION
A wireless ad-hoc network consists of a collection of nodes that communicate with each other through wireless links without a pre-established networking infrastructure. It originated from battleelf communication applications, where infrastructured networks are often impossible. Due to its exibility in deployment, there are many potential applications of a wireless ad-hoc network. For example, it may be used as a communication network for a rescue-team in an emergency caused by disasters, such as earthquakes or oods, where xed infrastructures may have been damaged. It may also provide a communication system for pedestrians or vehicles in a city. Another example of a wireless ad-hoc network is a rooftop network [9, 12], which consists of a number of wireless nodes spread over an area to provide local networking service and access to wired networks, such as the Internet, for residents in the neighbourhood. Another application of wireless ad-hoc networks is a sensor network, which consists of a large number of small computing devices deployed in a region that collect data and may send the information to a central server
Related Work
Location-based routing is done using physical location information about nodes. This is a very dierent approach than traditional routing, in which nodes need to maintain routing information. Instead, location-based routing uses information about the geographic location of the neighbors of the current node to direct a packet to its destination.
In location-based routing protocols, it is assumed that nodes know their own locations and the source node knows the location of the destination node. A node equipped with a Global Positioning System (GPS) receiver can obtain its own geographic coordinates. When GPS support is unavailable, there are other localization techniques that mobile nodes can use. In order to obtain the location of the destination node, a location service is needed from which a node can query about the locations of other nodes. Most location-based routing protocols assume that a location service exists as an external resource. Indeed, in the literature, location service has often been considered as an independent research topic. For research in this area
3 Face Routing Variants
Face routing has been implemented in several variants which differ in the decision when current face traversal has to be interrupted and which face has to be explored next. In the following we list these face routing variants by re-ferrying to the well-established names of the entire protocols employing these strategies. It is important to note that the following descriptions explain the face routing part of these protocols only. The routing path in the accompanying examples might be different when running the entire protocol. However, as long it is clear from the context we interchange-ably use the well-established protocol names for both the entire protocol and its face routing part. As a general classification we can distinguish between face routing strategies which require that the message has to follow a sequence of adjacent faces which are intersected by the straight lines connecting the source node s with the destination node t. These strategies will be denoted as continuative strategies since they keep the line st as a reference during the whole routing process. In contrast, a volatile strategy will initialize planar graph routing each time a face change occurs. In other words, the node where a face change has occurred is treated as a planar graph routing start node again. According to this definition the first three of the following listed strategies are continuative while the remaining three are volatile ones.
Conclusions and Future Work
we presented our research on extending face routing to more general models of wireless ad-hoc networks. In order to investigate the extendibility of face routing, we developed a series of models with increasing generality. One important part of our research is to nd appropriate models through which we can better understand the difficulties of routing problems in more realistic network graphs than unit disk graphs. The graph models we considered gradually incorporate aspects of real networks, which en-abled us to identify deferent types of problems, to gain an understanding of the capability and limitations of face routing, and to nd techniques to extend the original face routing protocols.
We developed techniques that extend and generalize the face routing approach so that it can be applied directly on general non-planar network graphs, without separately constructing a plane routing sub graph. Our techniques also extend face routing to net-work graphs with unstable links that may change during the routing process. Using these techniques, we developed face routing protocols without the constraints suered by the face routing protocols in the literature.
We are interested in identifying conditions under which face routing can guarantee message delivery. Therefore, in our research, we focus on designing deterministic algorithms and providing theoretical proofs for guaranteed message delivery in each graph model. These results are important for applications where guaranteeing message delivery is critical.
Our results assumed that the destination node is stationary. With a mobile destination node, the routing problem becomes even more di cult. It is possible that face routing could be combined with an efficient location update scheme to guarantee message delivery in such networks. One example is the Last Encounter Routing scheme analysed in : a source node forwards a packet to the last known location of the destination node, which was its location at some time in the past. During routing, if a more up-to-date location of the destination is learned, then the packet is diverted to this new destination.
Another direction for future work is to in