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)