Ad Hoc Networks

Wireless Ad Hoc Networks Bibliography

An important direction: cross-layer optimization.

  1. Physical layer
  2. Link layer
  3. Network layer
  4. Transport layer
  5. Application layer

Physical layer:

The physical layer may need to adapt to rapid SNR changes in wireless links and mobility.  Techniques include:

Link layer:

The function of MAC is to coordinate the access of multiple nodes to a shared (wireless) medium.

Objectives of MAC:

Technical difficulties in MAC design:

MAC design can be formulated as a coloring problem, which is NP-complete.   However, if you can utilize the information that is unique to ad hoc networks, (e.g., location info obtained by GPS), the complexity may be reduced to polynomial time.

Transmission range: the range within which signal-to-noise-ratio (SNR) is greater than or equal to a threshold \gamma_t so that transmitted message can be correctly received with high probability.  (interference free)

Sensing range: the range within which the signal-to-noise-ratio (SNR) is greater than or equal to a threshold \gamma_s (typically smaller than \gamma_t) so that a transmitter can withhold its transmission and avoid interfering ongoing transmissions between another pair of nodes.  Sensing is used in CSMA/CD (802.11).

Interference range: the range within which transmission from an interferer makes the signal-to-interference-and-noise-ratio (SINR) of the legitimate receiver smaller than \gamma_t, so that the legitimate receiver cannot correctly receive the message from the legitimate transmitter.

Network layer:

The functions of the network layer are to 1) provide (IP) addresses to end hosts, and 2) set up routes between sources and destinations, proactively (routes ready-to-use) or reactively (routes on-demand).   To set up a route, we need route discovery; to make routes ready to use, we need route maintenance.

Objectives of the network layer:

Technical difficulties in designing routing protocols:

Interaction between routing and MAC layer:

Transport layer:

The following two cases need different approaches:

TCP combines error control (ARQ), flow control (not over-running the receiver buffer), and congestion control (not clogging the network, not overloading the capacity in the routers).   TCP enjoys simplicity of control and gains widest acceptance.   However, this simplicity of control is at the cost of efficiency loss.   TCP is not able to distinguish the presence of congestion in wired networks, mobility, collision in wireless links, and bit errors due to poor quality of wireless links.   Single bit error could trigger congestion control mode (TCP getting into slow start phase); even fast retransmit/fast recovery is not effective in coping with packet/bit errors.

TCP needs to handle delay (RTT) and packet loss statistics that are very different from those in wired networks.

Research topics:

Reference on Analytical Modeling of TCP/IP.

Application layer:

Applications need to be designed to handle 1) frequent disconnection and reconnection with peer applications, 2) time-varying delay and packet loss statistics.

Factors that can change the topology of an ad-hoc network:

  1. Mobility of nodes
  2. Change of Power (also note that different criterion of error-free reception results in different topology)
  3. MAC layer (different schedule for the contending nodes, results in different topology)
  4. Flow dynamics (flows come and go; if a node has nothing to transmit, its links are gone from the topology.)
  5. Mode of nodes (sleeping/active mode; if a node goes to a sleeping mode, its links are gone from the topology)

Note that routing does not change the network topology but it uses the topology to find certain feasible/optimal paths.

Infrastructure-less property of ad hoc networks

Fixed infrastructure is a pre-defined topology, which characterizes fixed connectivity and does not change during the life time of a connection; in other words, a fixed infrastructure is independent of the above five factors (mobility of nodes, etc).   Internet, cellular networks, and wireless LAN have fixed infrastructures.  Ad Hoc Networks have no fixed infrastructure, making their deployment fast and easy.   At any time instant, the connectivity of an ad hoc network can be characterized by a graph (connectivity topology), which is time-varying.

Estimation of the average loss rate or average data transmission rate:

  1. Exponential smoothing: low pass filter
  2. Sliding window average:

Cross-layer optimization for video transmission:

minimize distortion, over physical/link/network/transport/application layer.   The error protection strategies at each layer are listed as below:

  1. At the physical layer, one can use adaptive modulation to cope with varying received SNR.
  2. At the link layer, one can use hybrid ARQ.   The MAC can schedule the users so as to maximize throughput.
  3. At the application layer, one can also use hybrid ARQ.

Security in Ad Hoc Networks

cryptology= cryptography +cryptanalysis (design schemes to attack cryptographic systems)