speed of radio waves in air ~= 299792458 m/s
speed of sound waves in air ~= 343 m/s
speed of sound waves in water ~= 1500 m/s
one-way trip takes over 1300 ms
In this paper, we demonstrate the remarkable fact that, in a wireless network with nonnegligible propagation delays, the throughput performance has the potential to be significantly better than networks with negligible propagation delays
- half-duplex nodes (either transmit or receive),
- fair schedules
for radio in air at 1km, ∂t = 1000/3x108 = 0.000000333 s
for sound in water at 1km, ∂t = 1000/1500 = 0.6667 s
1 packet per ∂t seconds
2 packets per ∂t seconds!
nodes to transmit simultaneously and letting their packets “cross in flight”
the packet duration equal to the propagation delay leads to a fair and optimal schedule
What is the maximum throughput of a network with nonzero propagation delays?
What geometries and schedules achieve this maximum throughput?
Given a network geometry, how do we determine optimal or near-optimal schedules?
- nodes in the network are half-duplex
- the network carries only unicast messages
- message transmitted by a node reaches every other node
- if two messages overlap at the receiver node, that node is unable to receive either (interference)
- \(collision\) = two messages overlap at the receiver node
- \(interference\) = message received at all nodes other than destination node
- \(throughput\) = total number of bits successfully transmitted by all nodes per unit time, normalized by the link rate
- \(D_{ij}\) = propagation delay between every pair of nodes
- \(N\) node network
- \(β\) (bits/s) = constant link rate of network
- information carried by a link in \(µ\) seconds = \(βµ\)
- schedule ensures that the interference from other nodes only arrives when the node is transmitting
- let each node transmit messages of duration \(µ = a\)
- nodes can successfully transmit six messages with \(βµ\) bits each every \(T = 4µ\) seconds
- throughput, \(S = (6βµ/4µ)/β = 1.5\)
- 50% higher than the maximum throughput for a three- node network without propagation delay
- \(Q_{jt} = i \gt 0 \Rightarrow \) node \(j\) transmits to node \(i\)
- \(Q_{jt} = -i \lt 0 \Rightarrow \) node \(j\) receives from node \(i\)
- \(Q_{jt} = 0 \Rightarrow \) node \(j\) does nothing
- schedule repeats with a period, \(T \Rightarrow Q_{j,t+T} = Q_{jt} \)
- \(Q_{jt} = -i \Leftrightarrow Q_{i,t-D_{i,j}} = j \)
- schedule has equal number of transmits and receives \(\Rightarrow\)
\[ \sum\limits_{t} \sum\limits_{j} 1I(Q_{jt}^{(T)} < 0) = \sum\limits_{t} \sum\limits_{j} 1I(Q_{jt}^{(T)} > 0) \]
\[ 1I(n) = \begin{cases} 0 & \mbox{if \(n\) is \(false\) } \\ 1 & \mbox{if \(n\) is \(true\) } \end{cases} \]
- matrix of a perfect schedule has no zero entires \( \Rightarrow\)
\[ \sum\limits_{t} \sum\limits_{j} 1I(Q_{jt} = 0) = 0 \]
- a perfect schedule acheives the N/2 upper bound
Theorem 2: For networks with odd number of nodes, perfect schedules with odd period do not exist
Corollary 3: For a network with odd number of nodes \(N\) and a periodic schedule with an odd period \(T\) the throughput is upper bounded by \( (NT - 1)/2T \)
Theorem 4: For an \(N\)-node network, periodic per-link fair schedules can only exist for period \(T = 2k(N-1), k \in \mathbb{Z}^+\)
Theorem 5: Perfect schedules do not exist for \(N\)-node linear networks for \(N > 2\)
\(S = 3/2 = 1.5\)
\(S = 3/2 = 1.5\)
\(S = 3/2 = 1.5\)
\(S = 4/2 = 2\)
- optimization problem as a sequential decision problem and solve it using dynamic programming
- resulting solution is optimal, but computationally infeasible
- approximate solution that reduces the computational complexity
\[\textbf{Q}^{\{t+1\}} = \Gamma (\textbf{Q}^{\{t\}}, \textbf{x}^{\{t\}} ) \]
\[\Gamma() \mbox{ is the state transition function} \]
\[\textbf{Q}^{\{t\}} \mbox{ is the paritial schedule at time } t \]
\[\textbf{x}^{\{t\}} \mbox{ is a vector of actions to be taken at time } t \]
\[ C(\textbf{x}^{\{t\}}) = \sum\limits_{j=1}^{N} 1I(x_j^{\{t\}} > 0) \]
\[ S = \lim_{T \rightarrow \infty} \frac{1}{T} \sum\limits_{t=0}^{T} C( \textbf{x}^{\{t\}}) \]
\[ X^*(\textbf{Q}) = arg \max_{x \in \chi(\textbf{Q})} ( C(\textbf{x}) + V(\Gamma(\textbf{Q, x})) ) \]
using relative value iteration (iteratively estimate the value function \(V\))
resulting algorithm works in practice and yields optimal schedules for many small networks
cardinality grows very rapidly with \(N\) and \(G\)
decision space cardinality is \(\mathcal{O}(N^N)\)
If we know the value function, the problem simplifies to enumerating the decision space and finding the optimal decision
Rather than estimate the value function iteratively, it is possible to develop an approximate value function based on the structure of the problem
approximate value function based on an intuitive understanding of the problem
make transmission decisions such that the interference they cause overlaps as much as possible
use the interfered slots for additional transmissions
sequentually select transmission decisions from all allowable transmissions
every transmission reduces the potential for future transmissions (value function approximation)
transmission that has minimum impact on the potential future transmissions is chosen
low-impact transmissions = interference largely overlaps with interference from previous transmissions
complexity = \(\mathcal{O}(N^3)\)
large propagation delays in underwater networks, rather than being harmful, lead to significant performance gains as compared to wireless networks with negligible propagation delays
make interfering packets overlap in time at unintended nodes and leave desired packets are interference free at the intended node
utilize the interference laden time slots for transmission
upper bound on the throughput of a large propagation delay network of \(N\) nodes is \(N/2\)