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

- half-duplex nodes (either transmit or receive),

- fair schedules

for radio in air at 1km, ∂t = 1000/3x10⁸ = 0.000000333 s

for sound in water at 1km, ∂t = 1000/1500 = 0.6667 s

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\)

- 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\)