Ad Hoc Networks

Ad Hoc Networks

Wireless Ad Hoc Networks Bibliography

An important direction: cross-layer optimization.

1. Physical layer
   • Joint design of physical layer and link layer can achieve higher
     efficiency, reliability.
2. Link layer
   • MAC layer design: how to strike a balance among the three opposing
     objectives as below:
     • Efficiency: Use multiuser detection to achieve higher throughput
     • QoS
     • Fairness
   • Two problems for CSMA/CD
     • Hidden terminal problem: causes collision, resulting in loss of efficiency (reduction
       of
       throughput)
       • solution: use signaling RTS/CTS
         • may not work well in multihop ad-hoc network, due to the
           difference between the transmission range and sensing/interference
           range.
       • limitation: induce overhead of signaling
     • Exposed node problem: not use the free channel, resulting in loss
       of efficiency.
       • solution: use scheduler to schedule transmission-receiver
         pairs (to achieve both QoS and fairness).
       • hidden terminal problem and exposed node problem are
         conflicting.  
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:

• Power control
• Multiuser detection
• Directional antenna
• Software radio

Link layer:

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

Objectives of MAC:

• Efficiency (minimize collision, maximize throughput)
• Fairness
• QoS

Technical difficulties in MAC design:

• Hidden terminal problem
• Exposed node problem
• Distributed control

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:

• Efficiency (minimize signaling overhead in route discovery and route
  maintenance)
• Stability (in computing routes, the routes eventually converge)
• Fast convergence rate
• QoS (find routes that support requested QoS)
• Scalability (whether the network is able to provide an acceptable level of
  service to packets even in the presence of a large number of nodes in the
  network)
• Energy efficiency

Technical difficulties in designing routing protocols:

• Efficiency and fast convergence rate are conflicting objectives. 
  Trade off between communication overhead and computation effort.  
  The more routing information distributed, the less computation required at
  each node.
• Scalability

Interaction between routing and MAC layer:

• Formulate the optimal routing problem as a min-cost flow problem, i.e.,
  constrained optimization problem (Bertsekas).
  • If the cost is linear, it is a linear program.
  • If the cost is convex and the constraint is convex (the constraint may
    not be convex even though it is polygon), it is a convex program.
• Different from the wired case, the capacity of a wireless link in an ad
  hoc network is not fixed; the link capacity is determined by MAC layer (which
  determines transmission schedules) and power control (which determines
  transmission range/interference range).   For a fixed 
  transmission schedule and power, we can solve the optimal routing problem and
  obtain one solution.   By iteratively changing MAC and power, we can
  obtain, hopefully, convergent solutions, which converge to the global minimum. 
  How to design such an iterative algorithm and how to prove its convergence is
  still an open problem.

Transport layer:

The following two cases need different approaches:

• TCP over wired/wireless networks with one wireless link on the path, e.g.,
  802.11 WLAN and Personal Communication Services (PCS) cellular network.
• TCP over ad hoc networks, where all the links on the path are wireless.

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:

• Performance of Transport Layer Protocols (TLP) over one-hop and multihop
  satellite networks, including constellations
• Performance of TLP over one-hop and multihop ad hoc networks
• Performance of new TCP versions over wireless networks
• TCP-friendliness in ad hoc wireless networks
• Collaboration among layers to improve transport layer performance
• Performance of TLP over different interconnecting wireless networks
  including wired and wireless
• Performance of TLP under vertical handovers between UMTS and WLANs
• TLP under dynamic traffic conditions, such as flash crowds, short-lived
  and long-lived flows, DoS attacks
• TLP for wireless sensor networks
• TLP for wireless WANs, LANs and PANs
• Modeling of TLP over wireless networks
• TLP over high speed wireless networks
   

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)