AD hoc networks assignment

computer_science

chapter6aAdHocNetworks.pdf

Home >Computer Science homework help >AD hoc networks assignment

Fund. Wireless & Mobile Protocol

COSC4301/5340

Ad Hoc Networks

Instructor: Dr. Xingya Liu

Department of Computer Science

Lamar University

Office: MAES 86 Phone: 409-880-8677

Email: [email protected]

Fund. Wireless & Mobile Protocol

Ad Hoc Networks

• An ad hoc network is a peer-to-peer network (no centralized server/backbone) set up temporarily to meet some immediate need.

– For example, a group of employees, each with a laptop or palmtop computer may convene in a conference room for a business or classroom meeting.

– The employees link their computers in a temporary network just for the duration of the meeting.

• Infrastructure-less wireless networks dynamically formed using only mobile hosts (no fixed routers)

• Network topology dynamic as all hosts are mobile

• Mobile hosts themselves double up as routers

• Multi-hop paths

• Highly resource constrained

Liu 2

Fund. Wireless & Mobile Protocol

Ad Hoc Networks

Liu

Fund. Wireless & Mobile Protocol

Applications

• Disaster recovery

• Battlefield

• Smart office

• Gaps in cellular infrastructure

• Virtual Navigation (cities, buildings, areas, etc..)

• Telemedicine (e.g., accident sites)

• Tele-Geoprocessing Applications

• Education via Internet

4Liu

Fund. Wireless & Mobile Protocol

Characteristics

• No wired backbone

• Dynamic Topology

• Routes between S-D nodes may contain multiple hops

• Mobile nodes with scarce resources

• May co-exist (and co-operate) with an infrastructure-based

network

• Broadcast Medium (IEEE 802.11 MAC protocol)

• Low bandwidth channels (1-10 Mbps)

5Liu

Fund. Wireless & Mobile Protocol

Differences between Ad-Hoc Networks and

Classical Wireless LANs

• The classical wireless LAN has a fixed infrastructure (backbone) consisting of one or more cells (coverage areas) with a control module for each cell.

• Within a cell (coverage area), there may be a number of fixed nodes.

• Stations/nodes can move from one cell to another.

• In contrast, there is no infrastructure for an ad-hoc network.

• Rather, a peer collection of stations within range of each other may dynamically configure themselves into a temporary network.

6Liu

Fund. Wireless & Mobile Protocol

What are the Challenges?

• Limited wireless transmission range

• Packet losses due to transmission errors

• Broadcast nature of the wireless medium

– Hidden/expose terminal problem

• Mobility-induced route changes

• Mobility-induced packet losses

• Battery constraints (Power Control)

• Ease of snooping on wireless transmissions (security hazard)

7Liu

Fund. Wireless & Mobile Protocol

Why is Routing in Ad Hoc Networks

Different ?

• Host mobility

– link failure/repair due to mobility may have different characteristics than those due to other causes

• Rate of link failure/repair may be high when nodes move fast

• New performance criteria may be used

– route stability

– energy consumption

• Many protocols have been proposed

– Some have been invented for mobile ad hoc networks (MANET)

– Others are adapted from older protocols for wired networks

• No single protocol works well in all environments

– some attempts made to develop adaptive protocols

8Liu

Fund. Wireless & Mobile Protocol

Traditional Routing Algorithms

• Distance Vector

– periodic exchange of messages with all physical neighbors that contain information about who can be reached at what distance

– selection of the shortest path if several paths available

• Link State

– periodic notification of all routers about the current state of all physical links

– router gets a complete picture of the network

• Example

– ARPA packet radio network (1973), DV-Routing

– every 7.5s exchange of routing tables including link quality

– updating of tables also by reception of packets

– routing problems solved with limited (controlled) flooding

9Liu

Fund. Wireless & Mobile Protocol

Problems of Traditional Routing

Algorithms

• Dynamic of the topology

– frequent changes of connections, connection quality, participants

• Limited performance of mobile systems

– periodic updates of routing tables need energy without contributing to the transmission of user data

– limited bandwidth of the system is reduced even more due to the exchange of routing information

– links can be asymmetric, i.e., they can have a direction dependent transmission quality

• Problem

– protocols have been designed for fixed networks with infrequent changes and typically assume symmetric links

10Liu

Fund. Wireless & Mobile Protocol

Ideal Routing Protocol

Objectives

• Low overhead route computation

• Ability to recover from frequent failures at low-cost

• Scalable (with respect to mobility and number of hosts)

• Robust

11Liu

Fund. Wireless & Mobile Protocol

Classification of Routing Protocols

12Liu

Fund. Wireless & Mobile Protocol

Classification of Routing Protocols

• Flat

– Proactive

• FSR – Fisheye State Routing

• FSLS – Fuzzy Sighted Link State

• OLSR – Optimized Link State Routing Protocol

• TBRPF – Topology Broadcast Based on Reverse Path Forwarding

– Reactive

• DSR – Dynamic Source Routing

• AODV – Ad hoc On demand Distance Vector

• Hierarchical

– CGSR – Clusterhead-Gateway Switch Routing

– HSR – Hierarchical State Routing

– LANMAR – Landmark Ad Hoc Routing

– ZRP – Zone Routing Protocol

• Geographic position assisted

– DREAM – Distance Routing Effect Algorithm for Mobility

– GeoCast – Geographic Addressing and Routing

– GPSR – Greedy Perimeter Stateless Routing

– LAR – Location-Aided Routing

13Liu

Fund. Wireless & Mobile Protocol

Types of Routing Protocols

• Reactive Protocols (seeks for routes only when required)

– Maintain routes only if needed

• Proactive Protocols (Actively seeks for routes)

– Determine routes independent of traffic pattern

– Traditional (link-state, distance-vector) routing protocols are proactive

• Hybrid Protocols

– Introduces hierarchy in the flat network

• Geographic Position Assisted Routing

– Why send packets north when the destination is south?

14Liu

Fund. Wireless & Mobile Protocol

Routing Protocols for

Ad Hoc Networks

• Reactive Routing Protocols

– DSR (Dynamic Source Routing)

– AODV (Ad-Hoc on-Demand Distance Vector)

• Proactive Routing Protocols

– DSDV (Destination Sequenced Distance Vector)

– OLSR (Optimal Link State Routing)

• Hybrid Routing Protocols

– ZRP (Zone Routing Protocol)

– TORA

– CEDAR (Core Extraction Distributed Ad-hoc Routing)

15Liu

Fund. Wireless & Mobile Protocol

Routing Protocols for Ad Hoc

Networks

• Proactive Routing Protocols

– Not well-suited for a dynamic network like Ad Hoc Networks

– For example, consider link-state routing that sends out network-wide

floods for every link-state change …

– Considerable overhead spent in maintaining “network state”

• Reactive (On-Demand) Protocols

– Compute routes only when needed

– Even if network state changes, any re-computation is done only when any

existing connections are affected

16Liu

Fund. Wireless & Mobile Protocol

Dynamic Source Routing (DSR)

• Based on source routing principle

• On-demand

• Route computation performed on a per-connection basis

• Split routing into two phases:

– Route discovery

– Route maintenance

• Source, after route computation, appends each packet with a source-route

• Intermediate hosts forward packet based on source route

17Liu

Fund. Wireless & Mobile Protocol

Dynamic Source Routing (DSR)

• Discover a path

– Only if a path for sending packets to a certain destination is needed and

no path is currently available

– On demand

• Maintaining a path

– Only while the path is in use, one has to make sure that it can be used

continuously

– On demand

• No periodic updates needed

18Liu

Fund. Wireless & Mobile Protocol

DSR Assumptions

• Small network diameter

• Speed of mobility is moderate

• Links may or may not be bi-directional

• A single address per node

19Liu

Fund. Wireless & Mobile Protocol

Dynamic Source Routing (DSR)

• When node S wants to send a packet to node D, but does not know a route to D, node S initiates a route discovery

• Source S floods (broadcasts) Route Request (RREQ) packet.

• RREQ packet contains Destination Address, Source Address and a unique Request ID determined by the sender.

• Each node receiving the packet checks whether it knows of a route to destination.

• If it does not, it appends/adds its own identifier (address) to the route record and broadcasts the RREQ packet.

• REMARK: To limit the number of route requests, a node only forwards the RREQ packet if the request has not yet been seen by the node and if the node’s address does not already appear in the route record.

20Liu

Fund. Wireless & Mobile Protocol

Route Discovery in DSR

S E

Represents a node that has received RREQ for D from S

Liu

Fund. Wireless & Mobile Protocol

Route Discovery in DSR

S E

Represents transmission of RREQ

Y Broadcast transmission

[S]

[X,Y] Represents list of identifiers appended to RREQ

Liu

Fund. Wireless & Mobile Protocol

Route Discovery in DSR

S E

• Node H receives packet RREQ from two neighbors:

potential for collision

[S,E]

[S,C]

[S,B]

Liu

Fund. Wireless & Mobile Protocol

Route Discovery in DSR

S E

• Node C receives RREQ from G and H, but does not forward

it again, because node C has already forwarded RREQ once

[S,C,G]

[S,E,F]

Liu

Fund. Wireless & Mobile Protocol

Route Discovery in DSR

S E

• Nodes J and K both broadcast RREQ to node D • Since nodes J and K are hidden from each other, their

transmissions may collide

[S,C,G,K]

[S,E,F,J]

Liu

Fund. Wireless & Mobile Protocol

Route Discovery in DSR

S E

• Node D does not forward RREQ, because node D

is the intended target of the route discovery

[S,E,F,J,M]

Liu

Fund. Wireless & Mobile Protocol

Route Reply in DSR

• Destination D on receiving the RREQ, sends a Route Reply (RREP)

• The destination node picks the shortest path

• RREP is sent on a route obtained by reversing the route appended to received RREQ

• RREP includes the route from S to D on which RREQ was received by node D

27Liu

Fund. Wireless & Mobile Protocol

Route Reply in DSR

S E

RREP [S,E,F,J,D]

Represents RREP control message

Liu

Fund. Wireless & Mobile Protocol

Route Reply in DSR

• Route Reply can be sent by reversing the route in Route Request (RREQ) only if links are guaranteed to be bi-directional (symmetrical)

– To ensure this, RREQ should be forwarded only if it received on a link that is known to be bi-directional

• If unidirectional (asymmetric) links are allowed, then RREP may need a route discovery for S from node D

– Unless node D already knows a route to node S

– If a route discovery is initiated by D for a route to S, then the Route Reply is piggybacked on the Route Request from D.

• If IEEE 802.11 MAC is used to send data, then links have to be bi-directional (since ACK is used)

29Liu

Fund. Wireless & Mobile Protocol

Data Delivery in DSR

• Node S on receiving RREP, caches the route included in the RREP

• When node S sends a data packet to D, the entire route is included in the packet header

– hence the name source routing

• Intermediate nodes use the source route included in a packet to determine to whom a packet should be forwarded

30Liu

Fund. Wireless & Mobile Protocol

Data Delivery in DSR

S E

DATA [S,E,F,J,D]

Packet header size grows with route length

Liu

Fund. Wireless & Mobile Protocol

DSR Optimization:

Route Caching

• Each node caches a new route it learns by any means

– When source S finds route [S,E,F,J,D] to node D, node S also learns route [S,E,F] to node F

– When node K receives Route Request [S,C,G] destined for node K, node K learns route [K,G,C,S] to node S

– When node F forwards Route Reply RREP [S,E,F,J,D], node F learns route [F,J,D] to node D

– When node E forwards Data [S,E,F,J,D] it learns route [E,F,J,D] to node D

– A node may also learn a route when it overhears Data packets

32Liu

Fund. Wireless & Mobile Protocol

Use of Route Caching

• When node S learns that a route to node D is broken, it uses another route from its local cache, if such a route to D exists in its cache.

• Otherwise, node S initiates route discovery by sending a route request RREQ

• Node X on receiving a Route Request for some node D can send a Route Reply if node X knows a route to node D

• Use of route cache

– can speed up route discovery

– can reduce propagation of route requests

33Liu

Fund. Wireless & Mobile Protocol

Use of Route Caching

S E

[…] Represents cached route at a node

(DSR maintains the cached routes in a tree format)

[S,E,F,J,D] [E,F,J,D]

[C,S]

[G,C,S]

[F,J,D],[F,E,S]

[J,F,E,S]

[K,G,C,S]

Liu

Fund. Wireless & Mobile Protocol

Use of Route Caching:

Can Speed up Route Discovery

S E

[S,E,F,J,D] [E,F,J,D]

[C,S]

[G,C,S]

[F,J,D],[F,E,S]

[J,F,E,S]

RREQ When node Z sends a route request for node C, node K sends back a route reply [Z,K,G,C] to node Z using a locally cached route

[K,G,C,S] RREP

Liu

Fund. Wireless & Mobile Protocol

Use of Route Caching: Can Reduce

Propagation of Route Requests

S E

[S,E,F,J,D] [E,F,J,D]

[C,S]

[G,C,S]

[F,J,D],[F,E,S]

[J,F,E,S]

RREQ

Route Reply (RREP) from node K limits flooding of RREQ.

[K,G,C,S]

RREP

Liu

Fund. Wireless & Mobile Protocol

Route Error (RERR) in DSR

S E

RERR [J-D]

J sends a route error to S along route J-F-E-S when its attempt to forward

the data packet S (with route SEFJD) on J-D fails

Nodes hearing RERR update their route cache to remove link J-D

Liu

Fund. Wireless & Mobile Protocol

Route Caching: Beware

• With passage of time and host mobility, cached routes may become invalid

• Stale (obsolete) caches can adversely affect performance

• A sender host may try several stale routes (obtained from local cache, or replied from cache by other nodes), before finding a good route

38Liu

Fund. Wireless & Mobile Protocol

Summary: DSR

• Path discovery

– broadcast a request with destination address and unique ID

– if a station receives a broadcast request

• if the station is the receiver (i.e., has the correct destination address) then return the reply to the sender (path was collected in the reply)

• if the request has already been received earlier (identified via ID) then discard the request

• otherwise, append own address and broadcast packet

– sender receives reply with the current path (address list)

• Optimizations

– limit broadcasting if maximum diameter of the network is known

– caching of address lists (i.e. paths) with help of passing packets

• stations can use the cached information for path discovery (own paths or paths for other hosts)

39Liu

Fund. Wireless & Mobile Protocol

Summary: DSR

• Maintaining paths: Route [S, node-1,node- 2,……,node-k, D]

– Hop-by-hop maintenance (MAC or network layer)

• How to find link [node-i, node-(i+1)] is down ?

– Utilize MAC level acknowledgement

– Insert a bit in packet header to ask an explicit acknowledgement from node (i+1)

– Passive acknowledge (overhearing node (i+1) re-transmission)

• How to send route error packet to S?

– Use the reverse route [node-i, node-(i-1), ……,node-1, S]

– Use node-i route cache to get a route to S

– Piggybacking route error packet in route discovery packet S

– End-to-end maintenance (transport or application layer): D sends ACK to S to indicate the route status. But S does not know which link is broken

40Liu

Fund. Wireless & Mobile Protocol

DSR: Advantages

• Routes maintained only between nodes who need to communicate

– reduces overhead of route maintenance

• Route caching can further reduce route discovery overhead

• A single route discovery may yield many routes to the destination, due to intermediate nodes replying from local caches

41Liu

Fund. Wireless & Mobile Protocol

DSR: Drawbacks

• Packet header size grows with route length

– particularly when data contents of a packet are small

• Care must be taken to avoid collisions between route requests (RREQ)

propagated by neighboring nodes

– insertion of random delays before forwarding RREQ

• Increased contention if too many route replies (RREP) come back due to

nodes replying using their local cache

– Route Reply Storm problem

– Reply Storm may be eased by preventing a node from sending RREP if it hears

another RREP with a shorter route

• An intermediate node may send Route Reply (RREP) using a stale cached

route, thus polluting other caches

– This problem can be eased if some mechanism to purge (potentially) invalid

cached routes is incorporated.

42Liu

Fund. Wireless & Mobile Protocol

DSR: Drawbacks

• The diameter of an ad-hoc network will not be too large

– Packet header will be larger than the payload if route is very longer

• The node’s speed is moderate

– Local route cache will become stale if node’s speed is high

• All nodes are overhearing (promiscuous)

– No energy saving

43Liu

Fund. Wireless & Mobile Protocol

Ad Hoc On-Demand Distance

Vector Routing (AODV)

• DSR includes source routes in packet headers

• Large headers can sometimes degrade performance

– Particularly when data contents of a packet are small

• AODV attempts to improve on DSR by maintaining routing tables at the nodes, so that data packets do not have to contain routes

• AODV retains the desirable feature of DSR that routes are maintained only between nodes which need to communicate

– On demand

44Liu

Fund. Wireless & Mobile Protocol

AODV

• Route Requests (RREQ) are forwarded in a manner similar to DSR

• When a node re-broadcasts a Route Request, it sets up a reverse path pointing towards the source

– AODV assumes symmetric (bi-directional) links

• When the intended destination receives a Route Request, it replies by sending a Route Reply

• Route Reply travels along the reverse path set-up when Route Request is forwarded

45Liu

Fund. Wireless & Mobile Protocol

Route Requests in AODV

S E

Represents a node that has received RREQ for D from S

Liu

Fund. Wireless & Mobile Protocol

Route Requests in AODV

S E

Represents transmission of RREQ

Y Broadcast transmission

Liu

Fund. Wireless & Mobile Protocol

Route Requests in AODV

S E

Represents links on Reverse Path

Liu

Fund. Wireless & Mobile Protocol

Reverse Path Setup in AODV

S E

• Node C receives RREQ from G and H, but does not forward

it again, because node C has already forwarded RREQ once

Liu

Fund. Wireless & Mobile Protocol

Reverse Path Setup in AODV

S E

Liu

Fund. Wireless & Mobile Protocol

Reverse Path Setup in AODV

S E

• Node D does not forward RREQ, because node D

is the intended target of the RREQ

Liu

Fund. Wireless & Mobile Protocol

Route Reply in AODV

S E

Represents links on path taken by RREP

Liu

Fund. Wireless & Mobile Protocol

Forward Path Setup in AODV

S E

Forward links are setup when RREP travels along

the reverse path

Represents a link on the forward path Liu

Fund. Wireless & Mobile Protocol

Route Reply in AODV

• An intermediate node (not the destination) may also send a Route Reply (RREP) provided that it knows a more recent path than the one previously known to sender S

• To determine whether the path known to an intermediate node is more recent, destination sequence numbers are used

• The likelihood that an intermediate node will send a Route Reply when using AODV is not as high as DSR

– An intermediate node which knows a route, but with a smaller sequence number, cannot send Route Reply

54Liu

Fund. Wireless & Mobile Protocol

AODV

• Each node maintains its own sequence number and a broadcast ID.

• The broadcast ID is incremented for every RREQ the node initiates and together with the node’s IP address, uniquely identifies an RREQ.

• Along with its own sequence number and broadcast ID, the source node includes in the RREQ the most recent sequence number it has for the destination.

source_addr

source_sequence _#

broadcast_id (incremented for each RREQ)

dest_addr

dest_sequence_#

hop_cnt

Liu

Fund. Wireless & Mobile Protocol

AODV

• Intermediate nodes can reply to the RREQ only if they have a

route to the destination whose corresponding destination

sequence number is greater than or equal to that contained in the

RREQ.

• During the process of forwarding the RREQ, intermediate nodes

recording their route tables the address of the neighbor from

which the first copy of the broadcast packet is received 

establishing a reverse path.

• If more same RREQs are received later, they are discarded.

• RREP packet is sent back to the neighbors and the routing tables

are accordingly updated.

56Liu

Fund. Wireless & Mobile Protocol

Data Delivery in AODV

S E

Routing table entries used to forward data packet. NOTE: Route is not included in packet header as in DSR.

DATA

Liu

Fund. Wireless & Mobile Protocol

Timeouts

• A routing table entry maintaining a reverse path is purged after a timeout interval

– timeout should be long enough to allow RREP to come back

• A routing table entry maintaining a forward path is purged if not used for an active_route_timeout interval

– if no data is being sent using a particular routing table entry, that entry will be deleted from the routing table (even if the route may actually still be valid)

58Liu

Fund. Wireless & Mobile Protocol

Link Failure Reporting

• A neighbor of node X is considered active for a routing table entry if the neighbor sent a packet within active_route_timeout interval which was forwarded using that entry

• When the next hop link in a routing table entry breaks, all active neighbors are informed

• Link failures are propagated by means of Route Error messages, which also update destination sequence numbers

59Liu

Fund. Wireless & Mobile Protocol

Route Error

• When node X is unable to forward packet P (from node S to node D) on link (X,Y), it generates a RERR message

• Node X increments the destination sequence number for D cached at node X

• The incremented sequence number N is included in the RERR

• When node S receives the RERR, it initiates a new route discovery for D using destination sequence number at least as large as N

• When node D receives the route request with destination sequence number N, node D will set its sequence number to N, unless it is already larger than N

60Liu

Fund. Wireless & Mobile Protocol

Link Failure Detection

• Hello messages: Neighboring nodes periodically exchange hello message to ensure symmetric links and detect link failures

• Absence of hello message is used as an indication of link failure

• Alternatively, failure to receive several MAC-level acknowledgement may be used as an indication of link failure

61Liu

Fund. Wireless & Mobile Protocol

Why Sequence Numbers in

AODV

• To avoid using old/broken routes

– To determine which route is newer, maintain freshness of routing

information

• To prevent formation of loops

– Assume that A does not know about failure of link C-D because RERR

sent by C is lost

– Now C performs a route discovery for D. Node A receives the RREQ

(say, via path C-E-A)

– Node A will reply since A knows a route to D via node B

– Results in a loop (for instance, C-E-A-B-C )

A B C D

Liu

Fund. Wireless & Mobile Protocol

Summary: AODV

• Routes need not be included in packet headers

• Nodes maintain routing tables containing entries only for routes

that are in active use

• Unused routes expire even if topology does not change

• Sequence numbers are used to avoid old/broken routes

• Sequence numbers prevent formation of routing loops

• At most one next-hop per destination maintained at each node

– DSR may maintain several routes for a single destination

63Liu