3.1 Generic Path Sets
Shortest Paths are the most obvious choice for paths i.e., in this context, straight line segments between the source and the destination. These paths minimize the mean path length (obviously), but at the same time the center of the area becomes congested. [1,2].Heat Conduction: This path set has its origins in a physical system. Assume that the whole surface is heated at constant rate, i.e., there are small heat sources everywhere, and that there is a point heat sink at r. This induces a heat flow towards r which field lines then correspond to the paths to r. The medium is assumed to have a constant heat conductivity. The resulting paths are smoothly curving and possess reasonably good performance. [4,5]. By definition, these paths exist also for unit square.
Optimized Paths: These paths are obtained by taking some initial path set which is then modified by using a parameterized family of functions. The initial solution can be, e.g., the shortest paths or paths according to the heat conduction. The latter yields a somewhat better performance at the price of more complicated formulae. In general, the resulting traffic load distribution is amazingly flat and very close to the global optimum. See [5] for details.
3.2 Unit Disk Specific Paths
Radial (Ring) Paths: With radial ring paths packets first travels radially to the correct distance from the origin and then along the ring to the destination, or vice versa. Thus for each pair of nodes two such routes exists. Radial-in paths are such that order of transition phases is such that the ring closer to the origin is always chosen, while the radial-out paths choose the path with the outer ring. Due to their elementary form these path sets are straightforward to analyze: at each point of the network packets are flowing only in exactly 4 directions (instead of all directions). [1,2].Radial-linear paths are a simple variation of the above. In polar coordinates, let (r,α) denote the source and (x,β) the destination point. For 0 ≤ α, β ≤ π the path is then defined by t(x,β) + (1-t)(r,α), where 0≤t≤1. In general case one just needs to take care that the "circle" is travelled in the shorter direction. The resulting paths are smoothly curving paths, which, however, yield a rather poor performance.
Randomized Multi-Path Sets: Two multi-path sets are given in [1,2], which obtain rather good performance in terms of max. traffic load. The first set, referred to as Rnd1, combines shortest paths (SP) and radial-out paths in proportions of 0.61 and 0.39, respectively. Even better performance was obtained by the second path set Rnd2, where shortest paths were combined with both radial-out and radial-in paths with proportions of 0.5027, 0.3763, and 0.121, respectively.
Circular Paths: Consider circles which cross the unit disk at opposite points. For example, there is infinitely many circles which cross the unit disk at points (-1,0) and (1,0). However, given two points r and x inside the unit disk, there is exactly one such circle which also cuts the unit disk at opposite points, say z and -z where |z|=1. The circular paths are defined as the proportion from r to x in the circumference of the particular circle. These paths are smoothly curving and the maximum spatial traffic load is considerably lower than with the shortest paths. [1,2].
Unit Circle paths (based on the idea from Durocher et al.) are heuristic paths defined also by following a circumference of some circle from the source r to the destination x. In this case the radius of the circle is fixed to one, R=1, which ensures that the path r to x stays within the area of the network for all node pairs. Note that two unit circles always exist which go through both locations r and x, and if the path is chosen randomly the resulting performance is rather poor. However, by choosing the unit circle which center is closer to the origin pushes the traffic gently away from the congested center and yields relatively good performance.
In general case radius R=R(r,x) can be seen as a free optimization parameter
rendering both circular and unit circle paths as special cases of this general
family of path sets. At the limit R→∞ the paths also converge to the shortest paths.
Curveball Paths:
Curveball routes proposed by Popa et al. in [3]
are an interesting practical solution for the load balancing problem.
The (x,y)-plane is first projected on a (Riemann) sphere
where the shortest paths are defined by the great circles.
These paths are then projected back to the plane.
The radius r of the sphere is an open parameter
which can be optimized.
For uniform setting in unit disk
the authors found value r = 1/1.2 to be optimal.
3.3 Unit Square Specific Paths
Manhattan Paths are designed for square (or rectangular) area where each path consist of initial horizontal transition and then vertical, or vice versa (in [6] these paths are referred to as one-turn rectilinear routing). For each pair of nodes there is two equally long path alternative, and consequently, the mean path length with all possible variations is always 2/3. With Random Manhattan paths the choice between the alternative paths is made randomly with both options having an equal probability. The performance is slightly better than with the shortest paths. With Outer Manhattan paths the path which turning point is further away from the origin is chosen [6,7].
The Diagonal Manhattan paths, proposed by Durocher et al. in [6],
are an elegant path set where the first transition is in horizontal direction
if the source is located in either of the triangles defined by the lines
x+y=0,
x-y=0, and y=±½,
and otherwise the initial transition is in vertical direction.
From the load balancing point of view it is clearly equivalent to
base this decision on the location of the destination instead of the source.
Hence, in the applet these two cases are identified with src and dst, respectively.
The difference is that for the latter path set the forwarding
decision at each point is the same independently from where a given packet is coming from
(destination based forwarding).
Field-line applied to Manhattan Paths:
This path set is derived from the (multi-path) Random Manhattan paths by
redirecting the packets with the same destination into a single-path
at each point according to the corresponding destination flow [4,7].
Multipath (SP+MH):
This is a heuristic combination of shortest paths and diagonal Manhattan paths.
If the source and destination are located in the same sector/triangle defined by
the lines x+y=0 and x-y=0, then a direct path is used.
Also, in any case with a probability of 16% a shortest path is used.
Otherwise the path is chosen according to Diagonal Manhattan paths.
As a result the performance is somewhat improved.
| path set | max Φ(r) | length |
|---|---|---|
| Shortest: | 0.637 ⋅ Λ | 0.905 |
| Radial-in: | 0.507 ⋅ Λ | 1.104 |
| Radial-out: | 1.000 ⋅ Λ | 1.523 |
| Heat: | 0.424 ⋅ Λ | 0.983 |
| Unit circle: | 0.424 ⋅ Λ¹ | 0.976 |
| Circular: | 0.424 ⋅ Λ | 0.936 |
| Rnd1 (multi-path): | 0.397 ⋅ Λ | 1.146 |
| Rnd2 (multi-path): | 0.376 ⋅ Λ | 1.162 |
| Optimized (heat): | 0.329 ⋅ Λ | 1.032 |
| path set | max Φ(r) | length |
|---|---|---|
| Shortest, SP: | 1.148 ⋅ Λ | 0.521 |
| Manhattan, Random: | 1.000 ⋅ Λ | 0.667 |
| Field-line (MH): | 0.854 ⋅ Λ | 0.594 |
| Manhattan, Diagonal: | 0.777 ⋅ Λ | 0.667 |
| Heat: | 0.770 ⋅ Λ | 0.561 |
| Optimized (SP): | 0.671 ⋅ Λ | 0.612 |
| Optimized (heat): | 0.650 ⋅ Λ | 0.574 |
¹) based on numerical simulations.
References:
[1] Esa Hyytiä and Jorma Virtamo. On load balancing in a dense wireless multihop network. In NGI 2006, 2nd Conference on Next Generation Internet Design and Engineering, Valéncia, Spain, April 2006.
[2] Esa Hyytiä and Jorma Virtamo. On traffic load distribution and load balancing in dense wireless multihop networks. EURASIP Journal on Wireless Communications and Networking, Special Issue on Novel Techniques for Analysis & Design of Cross-Layer Optimized Wireless Sensor Networks, June 2007.
[3] Lucian Popa, Afshin Rostami, Richard M. Karp, Christos Papadimitriou, and Ion Stoica. Balancing the traffic load in wireless networks with curveball routing. In Proc. the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Montréal, Canada, September 2007.
[4] Esa Hyytiä and Jorma Virtamo. On optimality of single-path routes in massively dense wireless multi-hop networks. In The 10th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), Crete Island, Greece, October 2007.
[5] Esa Hyytiä and Jorma Virtamo. Near-Optimal Load Balancing in Dense Wireless Multi-Hop Networks. In NGI 2008, 4th Conference on Next Generation Internet Networks, Krakow, Poland, April 2008.
[6] S. Durocher, E. Kranakis, D. Krizanc and L. Narayanan. Balancing Traffic Load Using One-Turn Rectilinear Routing. In Fifth Annual Conference on Theory and Applications of Models of Computation (TAMC 2008), Xi'an, China, April 2008.
[7] E. Hyytiä and J. Virtamo. On the Optimality of Single-Path Routes in Massively Dense Wireless Multi-Hop Networks. extended version submitted for journal publication, February 2008.