Virtual Localization for Mesh Network Routing

Nick Moore / Ahmet Sekercioglu / Gregory K Egan

Addendum: 400-Node Random Mesh

A commonly used method for generating N-node random meshes is to pick N random locations within a square area. This method does nothing to prevent disjoint networks being generated, but for a high density of nodes this rarely occurs. This random scattering of nodes is not very realistic, although it might be similar to the distribution of small, rugged sensor motes scattered from an aeroplane.

Capkun, et al.[1] use this model, randomly distributing 400 nodes in a 1km x 1km square, and varying the link range to 90, 100 or 110m to tune network connectivity.

Once the nodes are placed, topological information is extracted and the original location information is forgotten. Figure 1 shows the result of placing 400 nodes in a square kilometre, with a link range of 100m. Snapshots of the virtual location of active nodes are shown for 1000, 2000 and 3000 elapsed milliseconds, and at bottom right is a representation of the actual layout of the network which was used to create the topology.

Some features of the original network are visible in the virtual layout, but it's not very clear. A more important metric of the performance of the algorithm is the number of routable nodes. Once the network has converged, 97% of nodes are routeable, with only 12 nodes, in a group at the center right, remaining unroutable. These nodes are well-located, so a more sophisticated location-based routing scheme should be able to determine routes to and from these nodes.

Figure 1A:

Figure 1B:

Figure 1C:

Figure 1D:

Figure 1: Nodes progressively discover their virtual locations (seen here at A: 1000, B: 2000 and C: 3000 ms) until the entire network has been virtually mapped. The root node is marked with a square, unrouteable nodes with circles. Note that these are 2D projections of the 3D virtual location, and have been manually rotated for clarity. The original 2D topology is included as D for comparison purposes.}

[1] Srdjan Capkun, Maher Hamdi, and Jean-Pierre Hubaux. GPS-free positioning in mobile ad-hoc networks. Hawaii Int. Conf. on System Sciences (HICSS-34), pages 3481-3490, January 2001.