Re: How to use road topology information for my geographical routing protocol? NS3

[Tommaso Pecorella]

Hi,

I didn't think it was possible to touch in a single post almost all the big issues of geographic routing. Gratz !

I'd start the reply with a statement. This.

Ok, now that we have the background set, let's do Science.

Geographic routing: or: I wanna send a packet to something and I may want to use the environment to do a better job.

E.g.: I am on a vehicle, running on a highway, and I need to communicate with another car out of my radio range (on my back). I can use another car passing by on the opposite lane to relay my messages.

This is a simple example of a geographical routing combined with a DTN.

Anyway, there are some major issues in georouting, and they can be grouped in:

1. The combination of network and physical words may not match.
2. Information can not travel faster than the speed of light.

Sometimes you can use some simplifications, but sometimes these makes the results... questionable.

To understand the problem, let's analyze your questions:

"I need to know the position and velocity of the node". Of what node ?

- Source node: in ns-3 you ask the node's mobility object. In real systems you ask something (e.g., GPS), and you can have your position (with a given accuracy).

- Destination node: in ns-3 you can use a Location Service, in real systems.... you do the same.

Now, the location service is The Problem. Usually most research papers assume that the node's location is known, i.e., that they have a "God Mode" Location Service.

The problem is that this is unlikely, because the information can't travel faster than light. Each node will need to update the Location Service regularly, and this service will reply to a request with a delay. All in all, you can know what is the foreseen position of a target node, with a varying degree of accuracy. Note that on some scenarios the accuracy may be high (e.g., on a highway you have a quite specific path and a standard speed), but on some cases (e.g., urban scenario) the forecasts are a bit problematic.

Second problem: you ask for an IP address or a node's identity ? Usually the second, as a node may vary its IP address over time. (the first problem I mentioned). Nobody seems to care about this point tho, so you can as well forget about it.

Anyway, back to your questions. You can use the Location Service model (and have a forecast of the node's position and speed), or you could try to add a second information bit - the user's destination and the forecasted path.

This is a HUGE privacy violation, but the NSA knows it all anyway, and so does Google. As a consequence, let's assume the user will not be too upset.

You could, for example, have a mixed scenario: users with no destination set and user with a known destination (e.g., Taxicab, people with navigator set, etc.). For the first ones you can have a very imprecise forecast, the second kind may have a very accurate forecast.

As you see the problem isn't simple, and it all gets down to predict where the nodes will be in x seconds. I'd suggest to check for open source route planners, but I fear that a fully functional one may be a bit too complex.Perhaps you may setup a simple scenario and vary the forecast accuracy degree for different users.

Hope this helps a bit,

T.

On Sunday, July 20, 2014 4:17:53 AM UTC+2, Ricardo G. wrote:

Hi, I'm working on a routing protocol for VANETs that uses geographical information. I'm done with the basics of the protocol (based on AODV), and I've implemented successfully maps imported from OpenStreetMaps using SUMO, I can see in the simulation in NetAnim the nodes sending packets and responding if they're in transmission range with each other, moving around the map.

Now I need to use geographical information to make routing decisions. I need to know the position and velocity of the node, the distance (road distance if possible) between two points, and finally if it is possible to know the route the node will follow, like in GPS generated routes, to know if the node will take the packet closer to the final destination.

Additionally I may need the road topology converted in a graph, to generate routes from the node to area of interest. Is there some software to generate this graphs from open street maps imported files or something similar?

Thank you in advance.
Saludos :)