Position-based routing protocols implementation on NS-2 (resources)

Context

Scalable routing for wireless communication systems is a compelling and challenging task. To this aim, routing algorithms exploiting geographic information have been proposed. These algorithms refer to nodes by their location, not address, and use those coordinates to route greedily, when possible, towards a destination. We are focused on the state-of-the-art, stateless geographic packet routing protocols conceived or adapted for three-dimensional network scenarios. Each protocol is based on a specific forwarding algorithm, which try to send a packet to the best current neighbor node, according to the rule specified by the algorithm.

A taxonomy of the considered forwarding algorithms is shown below.

Forwarding algorithms implemented

1. Greedy

Greedy is a simple progress-based forwarding strategy. A node forwards the packet to the neighbor node that minimizes the distance to the destination node. In general, if there is no neighbor node closer to the destination (i.e., there is a void), the algorithm fails and the node keeping the packet is called local minimum.

2. Compass

Compass (or Directional, DIR) uses the direction of nodes to select the best forwarding node. Each node uses the location information of the destination to calculate its direction.

3. Most Forward

Most Forward, (MFR - Most Forward Routing) is very similar to Greedy, but, in this case, the current node forwards the packet to the neighbor node whose projection on the line from the current node to the destination is closer to the destination.

4. Ellipsoid

With Ellipsoid, the current node forwards the packet to the neighbor node that minimizes the sum of:

• the distance from the current node to the neighbor node
• the distance from the neighbor node to the destination node

5. Parametrized AB3D (PAB3D)

PAB3D is a randomized algorithm that tries to solve the local minimum problem described previously, by randomly choosing the next node from a subset of the current neighboring nodes to make progress toward a destination.

6. Greedy-Random-Greedy

The Greedy-Random-Greedy (GRG) algorithm belongs to the progress/randomization-based class and uses Greedy as the primary stage and a randomized algorithm (PAB3D) as a recovery strategy.

7. Projective Face

The Face algorithm works on the connected planar subgraph of UBG, called Gabriel Graph (GG), which contains only non-crossing edges. With Face, the packet is routed over the faces of a GG that are intersected by the line connecting the source node and the destination node. Each face is traversed using the right-hand rule. Projective Face is a first of a set of 3D forwarding algorithms that use the Face process to reach the destination. The nodes of the network are projected onto one plane that contains the segment [source-destination] and a third point chosen randomly. Then, Face is performed on this projected graph. If the routing fails, the nodes are then projected onto a second plane, orthogonal to the first one and Face is performed again.

8. CoordinateFace(3)

CoordinateFace(3) (CFace(3)) uses another set of projection planes, which is composed by the planes xy, xz and yz for the projection of the nodes.

9. Adaptive Least-Square Projective Face (ALSP Face)

ALSP Face is a proposal that includes additional heuristics to modify and improve the Projective Face algorithm, in order to enhance the chance to reach the destination.

10. Greedy-Face-Greedy

The Greedy-Face-Greedy algorithm (GFG), also referred to as Greedy Perimeter Stateless Routing (GPSR) for 2D networks, uses a combination of greedy and face methods. In a 3D context, GFG uses ALSP Face, which offers the best performance in terms of delivery rate.

11. PAB3D-CFace(1)-PAB3D

This algorithm hybridizes the Face strategy with randomized approaches.

12. PAB3D-CFace(3)

Another hybrid algorithm that combines Face strategy with randomization.

13. LAR 3D

The extension of LAR in 3D space, the source node computes a rectangular box (with source node at one corner and destination node at the opposite corner) which is the area in which flooding can occur. This is called a restricted flooding technique, meaning that the flooding is restricted only within the box.

14. PAB3D-LAR

PAB3D-LAR is a hybrid variant combining PAB3D with LAR.

The resources

In this page, we provide the implementation of the position-based routing protocols considered in our study. In particular we have created some modules for the code integration on Network Simulator 2 (version 2.34).

First of all, you need to install "M2ANET" patch, which includes the third dimension in NS-2. The patch can be downloaded from here. Follow the instructions included to install it.

The geo protocol module is composed by:

• geo_utility.h: includes utility geometrical functions, such as the projection of a 3D graph to a 2D one and the distance function between two nodes.
• geo_pkt.h: includes the definition of the new geo packet header.
• geo_node.h and geo_node.cc: include the definition and implemtation of the geographic node (position, neighbor list, etc.).
• geo.h and geo.cc: include the definition and implememtation of the geographic agent prototype.
• geo_next_node.h and geo_next_node.cc: include the definition and implementation of the forwarding algorithms considered in our state-of-the-art study.

The instructions to install and use our files are reported in the README file.

A simulative configuration sample can be found here and you can compare your output trace with that created by us.

All the files, instructions to install and use our files, and the simulative configuration example can be found altogether in geo.zip.

References

If you use our module for a scientific publication, please cite our papers. Questions, comments, criticisms, etc. can be directed to dronzani @ math.unipd.it