Routing in Dense Wireless Multi-hop Networks
(Joint work with Prof. J. Virtamo)
Assume a large scale wireless multihop network:
- a large number of nodes, and
- a typical path between two nodes consists of large number of hops.
The network is said to be dense
when the number of nodes tends to infinity, n →∞.
In this setting, it is impractical to keep book of each node or
path individually.
A convenient modelling approach in the setting of a dense network is to assume that:
- Nodes exist everywhere as a continuous medium with certain density,
ρ(r) [node/m²].
- Rate of packets exchanged between two locations is defined by
traffic demand density, denoted by λ(r,x)
[pkt/s/m²/m²].
- Path between two locations is described by a continuous curve
p(r,x).
Spatial Traffic Load:
Traffic load (congestion) in this setting can be defined as scalar packet flux,
Φ(r). (in analogy, e.g., with neutron transport theory).
The scalar packet flux Φ(r)
corresponds to the arrival rate of packets into
a small d-disk about r multiplied by 2d,
λ′(r,x) = 2d ⋅ Φ(r)
when
d → 0 ⇒ Φ(r)
represents the spatial forwarding load.
Load balancing problem:
Find such paths that minimize the maximum traffic load Φ(r) in the network,
min max Φ(r)
When the task is to minimize the scalar packet flux ("traffic load per unit area"),
the node density ρ(r) just needs to be high enough to
ensure full connectivity and
that neighbouring nodes exist in every direction (dense network).
Several other relevant problem formulations
have been proposed.
For example, the task may be to maximize the expected life time of a sensor network,
or to deploy a given number of nodes into a certain area in order to maximize, e.g.,
the expected rate of information.
|
|
Figure: A sample paths avoiding the center of the disk.
Our publications
- E. Hyytiä and J. Virtamo,
On The Optimality of Field-Line Routing in Massively Dense Wireless Multi-Hop Networks,
Performance Evaluation, vol. 66, 3-5, pp. 158-172, Elsevier, 2009.
- E. Hyytiä and J. Virtamo,
On Traffic Load Distribution and Load Balancing in Dense Wireless Multihop Networks,
EURASIP Journal on Wireless Communications and Networking, vol. 2007, 2007,
Special Issue on Novel Techniques for Analysis & Design of Cross-Layer Optimized Wireless Sensor Networks.
- E. Hyytiä and J. Virtamo,
Near-Optimal Load Balancing in Dense Wireless Multi-Hop Networks,
in NGI 2008, pp. 181-188, 2008, Kraków, Poland.
- E. Hyytiä and J. Virtamo,
On Optimality of Single-Path Routes in Massively Dense Wireless Multi-Hop Networks,
in ACM MSWiM'07, pp. 28-35, 2007, Crete Island, Greece.
- E. Hyytiä,
Traffic Matrix Estimation in a Dense Multihop Wireless Network,
in ISCN'06, 2006, Istanbul, Turkey.
- E. Hyytiä and J. Virtamo,
On Load Balancing in a Dense Wireless Multihop Network,
in NGI 2006, pp. 72-79, 2006, València, Spain.
See load balancing in action (a simple java applet).
|
