Position-based routing protocols for Flying Object Ad-hoc Networks

Flying Ad-Hoc Networks are ad-hoc networks composed of flying objects (e.g., drones). In this context, we have 3D topologies in which it is interesting to study routing algorithms exploiting geographic information. 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 tries to send a packet to a neighbor node according to the rule specified by the algorithm.

Compared Routing Algorithms

We have implemented in NS-2 the following routing algorithms and performed a comparison over a common simulation scenario. 

1. 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 (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 Routing (MFR) 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. With Ellipsoid, the current node forwards the packet to the neighbor node that minimizes the sum of: (i) the distance from the current node to the neighbor node and (ii) the distance from the neighbor node to the destination node
5. Parametrized AB3D (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. 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. The Projective 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) (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) 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. 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. The PAB3D-CFace(1)-PAB3D algorithm hybridizes the Face strategy with randomized approaches.
12. PAB3D-CFace(3) is another hybrid algorithm that combines Face strategy with randomization.
13. LAR 3D is 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 is a hybrid variant combining PAB3D with LAR.

Implementation in NS-2

In this page, we provide the NS-2 (version 2.34) code of the position-based routing protocols considered in our study.

To use our code, first of all, you need to install M2ANET patch, which includes the third dimension in NS-2.

Our NS-2 modules are 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 implentation 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