Subject: [Ans-research] On the use of GPS for routing in heterogenous networks

From: Jakob Eriksson <[email-masked]>
Date: Tue, 8 Apr 2003 23:57:41 -0700

Hello again,

Not feeling adequately informed to take part in the charter / 
directions discussion, I'll just forge ahead and bring up some subjects 
I find interesting. I would like to continue the discussion on the use 
of GPS for routing in MANETs. Assuming that we aren't talking about a 
homogenous network of omnidirectional transceivers of equal power, I 
think the use of GPS
would add more problems than it solves. At the bottom of this email, 
there's a quick recap of the action so far.

First a disclaimer: There is not a doubt in my mind that GPS 
information will become increasingly available to consumer products as 
miniaturization and technological advances continue. This will most 
certainly have important implications for all kinds of applications, 
and bring unbounded joy to the general populous. :-)

However, I have serious doubts about the validity of using GPS for 
_routing_ in a heterogenous network, consisting of omnidirectional 
transceivers, directional transceivers, free-space optical links, 
satellites(?) and wires, among others. Beside the previously stated 
"obvious" problems, using geographical location information to guide 
routing may have disastrous
effects on routing performance. For example, consider this simple 
network topology*:

A ------ B ------ C ------ D ------ E ------ F ------ G ------ H
  |                                                                      
                   |
  -------------------------------------------------------------------

The link A-H is a fiber, whereas all the other links are 802.11 
wireless links. Now B wants to send a message to H. With a routing 
protocol based on geographical location, C is the proper next hop, and 
so on. While this is certainly very cheap in terms of routing overhead, 
it isn't a good route. A protocol based on network distance (hop count, 
delay, available bandwidth or whatever) would instead "back track" to 
A, and then use the available fiber link. This is a simplified example, 
but I'm sure the point gets through. Things get even worse for 
geo-routing when the G-H link breaks.

I can come up with any number of examples of where geographical 
location has little or nothing to do with the node's position in the 
network topology, which is what actually matters when routing packets. 
Any degree of dependence on such an unreliable guide seems very 
undesirable, (Einar: even silly *wink*), although I would very much 
like to be convinced otherwise.

Given the above problem, how do the geo-routing advocates in the 
audience propose to make use of GPS in routing?

Yours truly,

Jakob Eriksson

* just in case the "picture" gets garbled, it's supposed to be 8 nodes 
in a string, connected by wireless links, and an
additional optical link going from the head of the string to the tail 
of the string.

--- RECAP ---

I started out stating a candidate "Known Fact":

7. Last, but not least, routing protocols that rely on geographical 
location information are undesirable for many reasons. Beside the 
obvious problems (energy, bulk, cost, precision, indoor operation 
etc.), a geographic location does not reliably correspond to a location 
in a network topology. Two disjoint domains could very well coexist in 
the same geographical location, with an intersection in some other part 
of the world. Thus, relying on GPS or equiv. even for rough guidance, 
may be very harmful for large networks.

Anders Nilsson says:

"I can't say I agree with you here at all. The obvious problems you 
mentioned are so obvious at all. The GPS technology is developing all 
the time, and the devices themselves becomes smaller and more power 
conservative. In future there is a possibility that all network 
equipped devices will also include GPS or similiar devices. And what is 
the problem of having two disjoint domains coexisting in the same 
geographical area? Maybe, if you force the addressing scheme to stricly 
reflect your position, will you have problems with this. But that is an 
addressing problem, not a routing problem. The problem is how to 
determine the position of a node. There are numerous solutions to how 
this problem can be solved, and some of them work quite well. But there 
are reason for taking advantage of GPS information. There are many 
applications that could benefit from having an exact geographical 
position, not the least military applications, but also many civilian 
ones."

Einar Vollset agrees:

"I agree with Anders on this, I think location information will become 
more and more common (it is, after all one of the key points in the 
current push for pervasive/ubiquitous computing), and I think not 
making use of it would be rather silly :-)"

Sukantha Kumar Hazra says:

"But it may be less complex."

_______________________________________________
Ans-research mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ans-research

---

From: Anders Nilsson <[email-masked]>
Date: Wed, 09 Apr 2003 12:32:57 +0200

Hello,

This thread is starting to become interesting! :-)
First of all I would like to say that we should all be aware that what 
we say here is not the truth at all. It is only a good and healthy 
discussion on a particular subject. Research as I see it is to stretch 
the limits,  "To boldly go where no man has gone before". As such, I 
think we should investigate all the possibilities of using such a 
promising technology as GPS before throwing it away. Sure, there are 
some difficulties, but that is what makes things interesting.
 
For example, say we have a VERY large network of wireless nodes. 
Existing routing solutions today either depend on a reactive, proactive 
or hybrid (e.g. ZRP) routing scheme. All these schemes have commonly 
known problems with scalability because of flooding based searches, 
large overhead etc. For a geographic based scheme to work in such a 
network, basicly all that is needed is the GPS location of the 
destination. We can then use geographic forwarding when routing the 
packet to its destination. Of course, it is not as simple as that. Not 
at all. For example, how do we determine the location? How do we handle 
routing around "holes" etc. But it is a good start, and I don't think we 
should through it away untill it has proved to be totally useless, or at 
least very inadequate.

A heterogenous or hybrid network as the one you describe is a different 
case. I don't think future routing schemes will solely be based on one 
routing metric. That is, to not only rely on hop count, delay, 
bandwidth, signal strength or GPS information, but maybe a combination 
of all of them. They all have their strength' and weaknesses, including 
geographic forwarding. A hybrid network is as I see it, a special case, 
and not a "pure" ad hoc network as much of the research so far has been 
focused on. A node equipped with two network interfaces where one is 
fiberbased, is a strong indication that this node have special 
capabilities, maybe it is some kind of gateway,  or basestation etc. You 
don't just setup heterogenous nodes "ad hoc" just like that. They are 
proably there for a special reason, and are probably not very mobile. In 
that case, hybrid routing must be used. In your case, node B might be 
using node A as a default gateway, and could choose to forward the 
packet to A because the route to A is shorter, more cost effective, 
whatever, than the route through C.  What I mean is that you need a 
different scheme for routing in hybrid networks, than for "pure" ad hoc 
networks. We could in your case use GPS routing towards the 
heterogenerous/hybrid nodes, if those routes are shorter, and then 
normal GPS routing if the heterogenerous nodes are more distant or 
unavailable. The geographic forwarding is only the method we use to get 
packet to their waypoint, or even final destination.
If the link G-H breaks, we have a "hole", and how such problems can be 
solved have been studied in several papers.

> so on. While this is certainly very cheap in terms of routing 
> overhead, it isn't a good route. A protocol based on network distance 
> (hop count, delay, available bandwidth or whatever) would instead 
> "back track" to A, and then use the available fiber link. This is a 
> simplified example, but I'm sure the point gets through. Things get 
> even worse for geo-routing when the G-H link breaks.

Hetergenous networks consisting of many types of links and radios, 
produces challenges for all type of routing schemes, including GPS 
routing. These are challenges that should be challenged, and before any 
final judgements are made, especially about specific routing scheme, 
they should be investigated thoroughly.

> like to be convinced otherwise.

I can't really understand why you think this is such a big problem. 
Routing deals with the problem of getting packets to their intended 
destination. How is the network topology preventing us from using GPS 
routing? So, a nodes geographical position has nothing to do with its 
position in the topology, why should that prevent us from using GPS 
information in routing? If you use a hierarchical scheme, you can still 
use GPS routing within the hierarchy.

regards,

Anders

---

From: Einar Vollset <[email-masked]>
Date: Wed, 9 Apr 2003 13:32:34 +0100

Hello indeed :-)

Ok, in a heterogenous network, things are a little more complex, 
however, routing is essentially
about attempting to create a global view using local information.
Previously, when there were no or few wireless links in a network, 
knowing where a node is
physically made little sense, as it was the logical position of the 
node in the network which
mattered.
In a MANET, the position of a node determines it's connectivity (most 
of the time) and thus
recursively determines the global view.
It just seems to me that discarding the validity of location 
information in routing is like throwing
away perfectly good information. And that is what one craves, right? :-)

Cheers,

Einar

---

From: Joe Macker <[email-masked]>
Date: Wed, 09 Apr 2003 11:18:41 -0400

GPS is not receivable everywhere or reliable.  Building are problems as are many other real environments. Also, location doesn't necessarily reflect network topology (it may hint at it). 

Allowing location information to potentially help scaling may not be a bad idea but I think relying on it is a bad idea...its no magic bullet in a real RF and topographical environment.

-Joe

At 01:32 PM 4/9/2003 +0100, Einar Vollset wrote:

>Hello indeed :-)
>
>Ok, in a heterogenous network, things are a little more complex, however, routing is essentially
>Previously, when there were no or few wireless links in a network, knowing where a node is
>physically made little sense, as it was the logical position of the node in the network which
>mattered.
>In a MANET, the position of a node determines it's connectivity (most of the time) and thus
>It just seems to me that discarding the validity of location information in routing is like throwing

---

From: S Woodside <[email-masked]>
Date: Wed, 9 Apr 2003 16:43:21 -0400

On Wednesday, April 9, 2003, at 11:18  AM, Joe Macker wrote:

> GPS is not receivable everywhere or reliable.  Building are problems 
> as are many other real environments.

True, but there are other ways to get position. Just look up your 
address in mapquest is one ;-) Also, there's no need to build a GPS 
into a node, simply visiting and programming it in once is enough 
(assuming fixed nodes).

However it might be nice if the geographical scheme would allow a 
transition to a locally determined scheme once it reaches a certain 
precision. That might use building codes, room numbers etc.

> Also, location doesn't necessarily reflect network topology (it may 
> hint at it).

In a wireless environment it does especially in the case of a 
mesh-style network where the topology is determined in large part by 
the range of the radios.

> Allowing location information to potentially help scaling may not be a 
> bad idea but I think relying on it is a bad idea...its no magic bullet 
> in a real RF and topographical environment.

It certainly should be a component, because of the massive aggregation 
benefits it offers where it is useful.

--
      anti-spam: do not post this address publicly
www.simonwoodside.com -- 99% Devil, 1% Angel

---

From: John Stine <[email-masked]>
Date: Wed, 09 Apr 2003 17:56:44 -0400

> into a node, simply visiting and programming it in once is enough

Also, since we are talking about RF signals with ad hoc networks, we have
the perfect environment to develop location awareness by using the radio
itself.  Some systems that generate location awareness using RF signals
include  GPS, the U.S. Army's Enhanced Position Location Reporting System
(EPLRS), and from what I understand, ultrawideband radio systems.  For
EPLRS, two nodes are surveyed into a location and then the network
identifies all the locations of the hundreds of nodes that may be part of
the network using time of arrival of signals and a collateration algorithm.
When I worked at the U.S. Army's Test and Experimentation Command, those who
were testing this system said it only got better as the number of nodes
increased.  Location accuracy is advertised as being better than within 30
meters.  This also implies the clock accuracies are on the order of 100
nsecs.   This is not something that can be built easily on top of an 802.11
device but an inexpensive AH MAC/Radio could be developed that provides this
service.  In an indirect sense, it is a requirement for many military
systems since there is a need for timing synchronization for TRANSEC
implementation and synchronization and location awareness go hand-in-glove.

Don't forget that at least in military systems the "killer application" of
the ad hoc network is to develop situational awareness.  In other words,
where is everybody?

---

From: Joe Macker <[email-masked]>
Date: Wed, 09 Apr 2003 18:44:55 -0400

At 04:43 PM 4/9/2003 -0400, S Woodside wrote:

>>GPS is not receivable everywhere or reliable.  Building are problems as are many other real environments.
>
>True, but there are other ways to get position. Just look up your address in mapquest is one ;-) Also, there's no need to build a GPS into a node, simply visiting and programming it in once is enough (assuming fixed nodes).
>
>However it might be nice if the geographical scheme would allow a transition to a locally determined scheme once it reaches a certain precision. That might use building codes, room numbers etc.
>
>>Also, location doesn't necessarily reflect network topology (it may hint at it).
>
>In a wireless environment it does especially in the case of a mesh-style network where the topology is determined in large part by the range of the radios.

No way...

If I learned anything from grad school and plenty of years designing wireless systems at many different freq bands its the inevitable time-varying and environmental sensitive nature of wireless channels...take a typical campus at the 2G band...I can likely communicate very far down an open road and not very far around a particular building,etc.. (I am one who has actually measured this effect quite frequently and I am talking orders of magnitude)...sometimes ~/r**2, sometimes ~/r**4 its not a euclidean space in many cases.. Granted it might be in some ....In another case...take a set of nodes in a valley and one on a hill.  These are simple cases.

>It certainly should be a component, because of the massive aggregation benefits it offers where it is useful.

I think it can be a useful tool in the bag...

Einstein said "Make everything as simple as possible but not simpler"

---

From: S Woodside <[email-masked]>
Date: Mon, 14 Apr 2003 01:01:51 -0400

On Wednesday, April 9, 2003, at 06:44  PM, Joe Macker wrote:

> If I learned anything from grad school and plenty of years designing 
> wireless systems at many different freq bands its the inevitable 
> time-varying and environmental sensitive nature of wireless 
> channels...take a typical campus at the 2G band...I can likely 
> communicate very far down an open road and not very far around a 
> particular building,etc.. (I am one who has actually measured this 
> effect quite frequently and I am talking orders of 
> magnitude)...sometimes ~/r**2, sometimes ~/r**4 its not a euclidean 
> space in many cases.. Granted it might be in some ....In another 
> case...take a set of nodes in a valley and one on a hill.  These are 
> simple cases.

I'll give you that there's variability, maybe even lots. But very few 
microwave connections are going to be more than something like 50 km (I 
can't remember the exact number) due to the curvature of the earth and 
a certain reasonable limit on the height of towers. Practically 
speaking the current wisdom puts Wifi links at about 25-30km max before 
you really start to have trouble. Whereas, if you start putting bits 
down a wire, who knows where it's going to go? The circuit could be 
local or go to the other side of the world.

So that, at certain scales, the network and real-world topology are 
definitely going to be related.

simon

---

From: S Woodside <[email-masked]>
Date: Mon, 14 Apr 2003 01:36:23 -0400

On Wednesday, April 9, 2003, at 02:57  AM, Jakob Eriksson wrote:

>  I would like to continue the discussion on the use of GPS for routing 
> in MANETs.

A quick assumption check. Does this list require an assumption of 
"mobile" ... ad hoc networks don't necessarily have to be mobile, and I 
think it makes a difference in terms of routing because a fixed ad hoc 
network has a lot more time to decide on good routing pathways. The 
kind of network I'm interested in -- a community wireless-style 
network, would also have much higher link stability. Ad hoc can mean 
"for the purpose of" but also it is often used to indicate 
improvisation, in this context, perhaps, self-configuration.

> For example, consider this simple network topology*:
>
> wireless links.

Using a naive geographic scheme, I agree this topology would present 
problems for all nodes but A and H. So that, a naive geographic scheme, 
which simply forwards packets in the correct cardinal direction, would 
work ... non-optimally.

Two possible points of opportunity to optimize upon:
- the network isn't mobile (my assumption) therefore time is available 
to create better routing paths
- some kind of dual routing scheme could act to detect such situations 
and change the routing for them

> A ------ B ------ C ------ D ------ E ------ F ------ G ------ H

It would be interesting to get some idea of how far away from A and H a 
node has to be before it's more efficient to route over the fibre vs. 
geographically. There would be a critical point where the decision 
flips. What does that look like? Is there any kind of mathematical 
analysis that can be made about the function. For example if it's 
exponential then it might be worthwhile for A to tell B to send packets 
headed beyond a certain distance east to A instead of to C. That's a 
highly specific example but if such a scheme can be devised that sends 
these instructions out to a certain limited distance, so as to have a 
very low routing-table-size overhead, along with some scheme to resolve 
conflicts.

> Things get even worse for geo-routing when the G-H link breaks.

There are existing protocols that can circumnavigate around holes, 
e.g., Greedy Perimeter Stateless Routing.

> like to be convinced otherwise.

It depends on what undesirable means. The geographic scheme will still 
/work/ even if in a very sub-optimal way. And that's a Good Thing since 
it scales so nicely.

Simon