# Presentation: 323887

## Ad Hoc Networks - A New Communication Paradigm?

- Prof. Zygmunt J. Haas
*Wireless Networks Laboratory*
- School of Electrical Engineering
- Cornell University, Ithaca, NY 14853
***haas@ee.cornell.edu***
***http://www.ee.cornell.edu/~haas/wnl.html***

- Cornell University

- Prof. Zygmunt J. Haas

## Introduction to Ad-Hoc Networks ?

- Ad-hoc networks are network architecture:
- that can be rapidly deployed
- that do not rely on pre-existing infrastructure
- whose set of nodes is continuously changing
- which self-adapts to the connectivity and propagation patterns, and
- which adapts to the traffic and
-    mobility patterns
- Establishment of the *IEFT *MANET Working Group to study IP-based routing in ad-hoc networks

- Cornell University

- Prof. Zygmunt J. Haas

## Use of the Ad-Hoc Technology for Military Communications

- Cornell University

- Prof. Zygmunt J. Haas

## Ubiquitous networking

***Ubiquitous networking***

- Cornell University

- Prof. Zygmunt J. Haas

## Applications of Ad-Hoc Networks

- Application of the ad-hoc network technology is appropriate when a network needs to be rapidly deployed without prior planning and to provide reliable communication in harsh propagation conditions.
- Example of applications:
- Military: for tactical communications
- National security: in times of natural disaster or global war
- Rescue missions: in lieu of adequate wireless coverage
- Law enforcement: similar to tactical communications
- Commercial use: for setting up sales presentations
- Education: wall-free (virtual) classrooms
- Local Area Networks (LANs): for limited-coverage communication
- Sensor Networks
- Extension of the cellular technology

- Cornell University

- Prof. Zygmunt J. Haas

## Challenges in Ad-Hoc Networks[Z.J. Haas and S. Tabrizi, “On Some Challenges and Design Choices in Ad-Hoc Communications,” IEEE MILCOM’98]

- The challenges in the design of Ad-Hoc networks stem from the following facts:
- the lack of centralized entity  self-organizing and distributed protocols
- the possibility of rapid platforms movement (highly versatile topology)  efficient and robust protocols
-  _all_ communication is carried over the wireless medium  power and spectrum efficient communications
- Compare this with the fixed (cellular) networks ...

- Cornell University

- Prof. Zygmunt J. Haas

## Characteristics of Ad-Hoc Networks

- The distinctive differences between ad-hoc networks and cellular networks are:
- no fixed infrastructure is present
*multi-hop routing* (network diameter >> node transmission range)
- peer-to-peer operation
- frequent changes of associations

- Cornell University

- Prof. Zygmunt J. Haas

## Challenges of Ad-Hoc Networks?

- Application/Market penetration
- is multihop technology commercializable?
- Design/Implementation
- reliable, manageable, survivable, and secure
- Operational/Business-related
- how to manage the network? how to bill for services?

- Cornell University

- Prof. Zygmunt J. Haas

## Some Ad-Hoc Architectural Design Choices

- Routing/Mobility Management:
- Proactive vs. Reactive Routing Protocol
- Medium Access Control:
- “To Sense or Not to Sense, this is a question!”
- Multimedia Traffic:
- How to handle QoS for real-time traffic? Is it possible at all?
- Security:
- Authentication, Authorization, Privacy, in the ad hoc networking environment.

- Cornell University

- Prof. Zygmunt J. Haas

## An Introduction to Ad-Hoc Networks

- _Selected examples of ad-hoc architectural choices_:
- flat vs. hierarchical (multi-tiered) network
- proactive vs. reactive routing protocols
- degree of globalization in topological changes
- frequency of communication of topological changes
- criteria for route selection / max route determination
- sizing of nodal transmission radius
- synchronized vs. unsynchronized operation
- CSMA vs. dialog-based MAC

- Cornell University

- Prof. Zygmunt J. Haas

## The Ad-Hoc Networks Design Choices

**The *****Flat***** Network Architecture**

- Cornell University

- Prof. Zygmunt J. Haas

## The Ad-Hoc Networks Design Choices

**Hierarchical Ad-Hoc Network Architecture**

- Cornell University

- Prof. Zygmunt J. Haas

## Proactive Vs. Reactive Routing

*Proactive Protocols*
- continuously update the “reachability”
-     information at all the network nodes
- when a route is requested, it is immediately available
- examples of proactive protocols are: *Distance-Vector (DV), Shortest Path First (SPF), Open Shortest Path First (OSPF)*
- Proactive protocols are inappropriate for the ad-hoc networking environment as _they waste too much wireless resources_, especially for large, highly mobile network.

- Cornell University

- Prof. Zygmunt J. Haas

## Proactive Vs. Reactive Routing

- discover routes _only_ upon demand
- involve some sort of “global search”
- there may be a significant delay
-     associated with the route discovery
- examples of reactive protocols are the family of *flooding* protocols
- Reactive protocols are inappropriate for the ad-hoc networking environment as they are too slow and consume too much network resources, especially for large, highly mobile network.

***Proactive Vs. Reactive Routing***

- Cornell University

- Prof. Zygmunt J. Haas

## Routing Protocols for Ad-Hoc Networks

- The following are few examples of routing protocols
- for ad-hoc networks:
- 		 OLSRP = Optimized Links State Routing Protocol
- 			*draft-ietf-manet-olsrp-04.txt*
- 		 DSR = Dynamic Source Routing
- 			*draft-ietf-manet-dsr-05.txt*
- 	       AODV = Ad-hoc On-Demand Distance Vector
- 			*draft-ietf-manet-aodv-08.txt*
- 		 TORA = Temporary-Ordered Routing Algorithm
- 			*draft-ietf-manet-tora-spec-03.txt*
- 		 ZRP = Zone Routing Protocol
*	**	**	**draft-ietf-manet-zone-ierp-01.txt **	**	**	**	**	**draft-ietf-manet-zone-iarp-01.txt**	**	**	**	**	**draft-ietf-manet-zone-brp-01.txt*

- Cornell University

- Prof. Zygmunt J. Haas

## Optimized Link State Routing Protocol (OLSRP)

- The OLSRP is a proactive protocol.
- It is an optimization based on the pure link state routing algorithm.
- It uses the Multi-Point Relays (MPRs) to determine the route to a destination in the network. (MPRs are selected nodes that forward messages as part of the flooding process.)
- An OLSRP route consists of the identity of the MPRs.
- OLSRP is particularly suitable for large and dense networks.** **

- Cornell University

- Prof. Zygmunt J. Haas

## Common Features of Reactive Routing Protocols (i.e. AODV, DSR, TORA)

- Route discovery process is initiated only when a route is needed.
- Route discovery is based on the exchange of queries and replies.
- Route queries are broadcast.
- Route discovery process may produce multiple routes.
- Protocol design ensures loop freedom of routes.
- A route maintenance mechanism is provided to inform nodes of invalid routes.

- Cornell University

- Prof. Zygmunt J. Haas

## Zone Routing Protocol (ZRP) [Z.J. Haas and M.R. Pearlman, "The Performance of Query Control Schemes for the Zone Routing Protocol," ACM/IEEE Transactions on Networking, August 2001]

- The Zone Routing Protocol (ZRP) is a hybrid between the proactive and reactive protocol schemes. A salient feature of the protocol is that it can adjust to the network, traffic, and mobility conditions based on sizing a single parameter - the *Zone Radius**.*

- Cornell University

- Prof. Zygmunt J. Haas

## The Notion of a Routing Zone

-     A *routing zone* is defined for each node and includes the nodes whose _minimum_ distance _in hops_ from the node in question is _at most_ some predefined number, which is referred to here as the *zone radius.**** ***

**S**

**B**

**J**

**L**

**K**

**C**

**D**

**A**

**E**

**G**

**I**

**F**

**H**

**Definition of a **

***Zone Radius***

***Zone***

***Radius***

- Cornell University

- Prof. Zygmunt J. Haas

## The Notion of Peripheral Nodes

**    **
**   **
**   **
-    Nodes, whose minimum distance from the node in question is _exactly equal_ to the *zone radius* are referred to as *peripheral nodes.*

**S**

**B**

**J**

**L**

**K**

**C**

**D**

**A**

**E**

**G**

**I**

**F**

**H**

**Definition of a **

***Zone Radius***

***Zone***

***Radius***

- Cornell University

- Prof. Zygmunt J. Haas

## The Bordercasting Operation

***  ***
***  ***
*  **Bordercasting* is an operation of sending a location query by a node to all or some of its peripheral nodes**.**

**S**

**B**

**J**

**L**

**K**

**C**

**D**

**A**

**E**

**G**

**I**

**F**

**H**

**Definition of a **

***Zone Radius***

***Zone***

***Radius***

- Cornell University

- Prof. Zygmunt J. Haas

## The Operation of the ZRP

***D***

***A***

***E***

***F***

***G***

***H***

***B***

***S***

***C***

**An example of IERP operation**

- Cornell University

- Prof. Zygmunt J. Haas

## The ZRP Constituents 

*ZRP *consists of two subprotocols:
*IntrA-zone Routing Protocol (IARP) **and *
*IntEr-zone Routing Protocol (IERP):*
- Using *IARP, *a node learns the topology of its zone only. Since the zone is much smaller than the network, the amount of the control traffic is _significantly_ reduced.
- Using *IERP, *a destination beyond the source’s zone is efficiently searched. Since the search progresses in “quantum” of zone radius, it is fast and consumes much less resources.

- Cornell University

- Prof. Zygmunt J. Haas

## How to terminate the search?

***Desired***

***search***

***direction***

***Desired***

***search***

***direction***

***Desired***

***search***

***direction***

***Desired***

***search***

***direction***

***Desired***

***search***

***direction***

***source***

**. . .**

**.**

**.**

**.**

**.**

**.**

**.**

**. . .**

**. . .**

**Guiding the search in desirable directions**

- Cornell University

- Prof. Zygmunt J. Haas

## ... Flood termination techniques

- Loopback Search Prevention # 1: A bordercasted-to node that receives a query checks whether any nodes in the *Accumulated Route *are within its *routing zone.**** ***

- Cornell University

- Prof. Zygmunt J. Haas

## Some Representative ZRP Performance Results

- ZRP traffic relative to flood search vs routing zone radius

- ZRP route query response time vs routing zone radius

- Cornell University

- Prof. Zygmunt J. Haas

## Typical ZRP Characteristic Curves

***zone radius***

***control traffic volume***

***proactive***

***reactive***

***optimal zone radius***

- Cornell University

- Prof. Zygmunt J. Haas

## CSMA vs. RTS/CTS-based  access ...

- Collisions occur at the receiver, not at the transmitter
-    The above observation results in two access problems:
- the hidden terminal problem, and
- the exposed terminal problem

- Cornell University

- Prof. Zygmunt J. Haas

## The hidden-terminal problem

- Cornell University

- Prof. Zygmunt J. Haas

## The exposed-terminal problem

***B***

***C***

***A***

***?***

***D***

- Cornell University

- Prof. Zygmunt J. Haas

## The RTS/CTS - dialogue

- An alternative to Carrier Sensing was proposed in which the coordination among the stations is performed by two basic control messages: Request-To-Send and Clear-To-Send.
- These messages “reserve” spatially and temporarily the channel for the about-to-communicate nodes.

- Cornell University

- Prof. Zygmunt J. Haas

## The RTS/CTS - dialogue

**A**

**B**

***RTS***

***CTS***

***DATA***

**A**

**B**

**C**

**D**

**E**

**C**

**E**

**D**

- Cornell University

- Prof. Zygmunt J. Haas

## MAC Protocols for Ad-hoc Networks

-     The following are examples of MAC protocols, as they might apply to the ad-hoc communication environment.
- 		 MACA
- 		 MACAW
- 	 	 FAMA
- 		 DBTMA

- Cornell University

- Prof. Zygmunt J. Haas

## Dual Busy Tone Multiple Access(Z.J. Haas and J. Deng, “Dual Busy Tone Multiple Access (DBTMA): A New Medium Access Control for Packet Radio Networks,” IEEE Transactions on Communications)

- DBTMA solves the hidden and the exposed terminal problems by separating the two communication directions through the use of two *Busy Tones *- a receive busy tone (BTr) and a transmit busy tone (BTt).
- In DBTMA, data packets are never destroyed and the exposed terminal problem is addressed.

- Cornell University

- Prof. Zygmunt J. Haas

## Dual Busy Tone Multiple Access(DBTMA) (con’t)

***Dual Busy Tone Multiple Access******(DBTMA) (con’t)***

- Use two busy tones:
- BTr set up by receiver, protecting data packets
- BTt set up by transmitter, notifying neighbor nodes
- Nodes sensing these tones need to defer

- Cornell University

- Prof. Zygmunt J. Haas

## DBTMA performance

-  Nodes in N independent groups competing to send to a common receiver
-  Each group contains large number of nodes
-  Comparison of the performance of DBTMA with different busy tone sensing delay and other schemes

- Cornell University

- Prof. Zygmunt J. Haas

## Supporting QoS in Ad Hoc Networks

- Due to the frequent reconfiguration rate of ad hoc networks, the lifetime of links (and correspondingly of paths) tend to be limited. As such, a natural question arise whether it is possible to support QoS communication in such a dynamic network topology.
- A more general question is what are the ranges of the network parameters (e.g., network size, number of nodes, nodal mobility, etc) for which some definition of QoS communication can be supported.

- Cornell University

- Prof. Zygmunt J. Haas

## What is Multipath Routing? [A. Tsirigos and Z.J. Haas “Using Multipath Routing In a Mobile Ad Hoc Network EnvironmentNetworks,” MILCOM’01]

- Instead of using a single path (route) between source and destination, many - preferably disjoint - paths are utilized in order to send data.
- The goal is to provide load balancing, reduced end-to-end delay and _improved packet delivery ratio_ (reduced probability that the message needs to be dropped).

***path****** 3****** ***

***path 1***

***path 2****** ***

***Source***** **

***Destination***** **

- Cornell University

- Prof. Zygmunt J. Haas

## The routing scenario 

- Assume that *n* paths are available from source to destination, with max number of paths *n**max*
- The *i-th* path has a probability of failure *p**i* ( equivalently the success probability of each path is *q**i** = 1-p**i *)
- Each packet at the source is fragmented into multiple blocks and a certain number of overhead blocks is computed (*Diversity Coding*)

- Cornell University

- Prof. Zygmunt J. Haas

## Performance Improvement

- The maximum gain is defined as:

- 0.4

- 0.5

- 0.6

- 0.7

- 0.8

- 0.9

- 1

- 0

- 0.05

- 0.1

- 0.15

- 0.2

- 0.25

- 0.3

- 0.35

- Maximum gain for r < 2

- q - path success probability

- G

- max

-  - maximum gain

- n

- max

- =10

- n

- max

- =20

- n

- max

- =30

- Cornell University

- Prof. Zygmunt J. Haas

##  QoS in Ad Hoc Networks through the use of Multipath Routing

- The use of multiple paths along with diversity coding increases the packet delivery ratio.
- The evaluation of the packet delivery ratio can be achieved even when only general information about the path quality (average and standard deviation) is available.
- Improvement in the packet delivery ratio can also be achieved when the paths are not independent, but experience some correlation.

- Cornell University

- Prof. Zygmunt J. Haas

## Securing Ad-Hoc Networks [L. Zhou and Z.J. Haas, “Securing Ad Hoc Networks,”IEEE Network Magazine, vol. 13, no.6, November/December 1999]

- Secure lower layers (e.g., MAC)
- Secure routing
- _Secure high-level communication_
- Availability
- Authentication
- Integrity                           Public Key Infrastructure
- Confidentiality
- Nonrepudiation

- Cornell University

- Prof. Zygmunt J. Haas

## Securing Ad-Hoc Networks (con’t)

- Security is important for many ad hoc networks application; e.g., military communications, but it’s also a tough problem
- The main problems in securing ad hoc communications are:
- lack of a central element; e.g., no CA
- frequent changes of topology; trust relations are change frequently as well
- vulnerable wireless transmission medium; e.g., easy eavesdropping, denial of service, impersonation, replay, etc, attacks
- scalability to large networks is required

- Cornell University

- Prof. Zygmunt J. Haas

## Securing Ad-Hoc Networks (con’t)

- Our approach is to rely on two principles:
- (1) high degree of redundancy in the network topology
- (2) distribution of trust among many network nodes, rather than relying on a single or small set of nodes
- (2) assumes that if the probability of having *t* nodes being compromised at any point in time is small, distributing the trust among *t+1* nodes suffices to ensure sufficient level of security

- Cornell University

- Prof. Zygmunt J. Haas

## Some final thoughts ...

- Although the ad hoc networking technology is an exciting new direction ... do not tear down your cellular infrastructure yet ... 
- The most promising direction (in my opinion) for wide commercial technology transfer is the extension of the cellular infrastructure (4G systems (?)) and extensions of current wireless LAN technologies.

- Cornell University

- Prof. Zygmunt J. Haas

## Some final thoughts ...(con’t)

- The hot topics in studying the ad hoc networking technology are (still):
- _scalable_ routing/mobility management
- multicasting
- integration with other wireless/wired technologies
- support for real-time multimedia traffic (QoS)
- security and access control
- service discovery and node configuration

- Cornell University

- Prof. Zygmunt J. Haas

## Thank you for listening!

**Happy Summer Vacation!**

- Cornell University

- Prof. Zygmunt J. Haas