Lect_Intro-Unit-1-wirelessAdHocNetowrk.ppt

Ad hoc network course ppt

1. 1
Ad-hoc Networks
MCNE02
Subject Teacher: Dr. Shilpa Chaudhari

2. Unit-1
Chapter 5: Ad-hoc Wireless Networks
•Introduction,
•Issues in Ad-hoc Wireless Networks
•Ad-hoc Wireless Internet
Chapter 6: MAC Protocols for Ad-hoc Wireless Networks
•Introduction,
•Issues in Designing a MAC Protocol
•Design Goals of MAC Protocols
•Classification of MAC protocols
•Contention-Based Protocols
•Contention-Based Protocols with Reservation Mechanisms
•Contention-Based Protocols with Scheduling Mechanisms
•MAC Protocols that Use Directional Antennas.
2

3. 3
Chapter 5:
Mobile Ad hoc NETworks (MANETs)

evolution, characteristics,
applications and challenges

4. History
•The idea of ad-hoc networks is the multi-hop wireless relaying of messages:
• 500 B.C. Darius I, King of Persia:
–the principle of multi-hop relaying was introduced;
–messages from the capital to remote provinces have been relayed using line of
shooting men;
–more than 25 time faster than normal messengers available at that time;
–a lot of other ancient ad hoc systems: string of repeaters of drums, trumpets, or
horns.
•1970, Norman Abrahamson, ALOHAnet:
–aim: a network for University of Hawaii, to connect remote sites on islands;
–idea: xed single-hop wireless packet switching with multiple access;
–extension: idea is applicable for multi-hop relaying also;
–outcome: stimulated the research in multi-hop relaying leading PRNET project.
•Packet radio network (PRNET) sponsored by Defence Advanced Research
Project Agency.
4

5. History
•PRNET project
–Aim: developing packet wireless network for military applications;
–Idea: evolved from centralized control to distributed wireless multi-hop system;
–How: ALOHA and CSMA for access to a shared media, DSSS over the channel;
–Features: self-organization, self-configuration, detection of radio connectivity.
•The main issues that the RPNET faced were:
–obtaining, maintaining, and utilizing the topology information;
–error and flow control over the wireless links;
–reconfiguration of path to handle path breaks;
–processing and storage capability of nodes;
–distributed channel sharing.
•The successful demonstration of PRNET proved:
–feasibility and efficiency of infrastructure-less networks;
–applicability to civilian and military purposes.
5

6. History
•Just after PRNET: Survivable Radio Network (SURAN)
–What: extension of the DARPA PRNET project;
–Aim: providing efficiency in all aspects: size of devices, cost, scalability;
• In 1980th:
–What: military applications were extensively funded across the globe;
–Point: IETF created the WG called mobile ad-hoc network (MANET) group;
–Aim of MANET: provide standardized routing functionality for ad hoc networks.
• 1994: Bluetooth
–What: short-range, low-power, low-complexity radio;
–Aim: connectivity between heterogeneous devices;
–How: Special Interest Group (SIG): 3Com, Ericsson, IBM, Lucent, Motorola,
Nokia etc.
–Result: one of this first commercial realization.
•Note: Bluetooth is not ad hoc itself! Just a possible platform for ad hoc
networks.
6

7. History
•Bluetooth standardized two major nodes' formations:
–Piconet:
• single point-to-point wireless links formatted in group of
nodes;
• in piconet every node can reach every other node in a
group within a single hop.
–Scatternet:
•formation created by several piconets;
•multi-hop routing protocol should be used (not
standardized).
7

8. 8
Characteristics
•A mobile wireless ad hoc network (MANET) is a network of
mobile nodes that
–are connected via wireless links and
–exchange packets along multi-hop paths
–without the support of a fixed communication infrastructure
•There is no centralized control. Each node can act as router and
forward data for other nodes.
•Nodes are free to move randomly and organize themselves
arbitrarily.
•The network’s topology may change rapidly and unpredictably.

9. 9
Cellular vs. ad hoc wireless networks
Switching Center
+ Gateway
Infrastructure-dependent Infrastructure-less
Basestation
Basestation
Basestation

10. Cellular vs. ad hoc wireless networks
10

11. 11
Cellular Networks Ad Hoc Wireless Networks
Fixed infrastructure-based I infrastructure-less
Single-hop wireless links Multi-hop wireless links
Guaranteed bandwidth (designed for voice traffic) Shared radio channel (more suitable for best-effort data traffic)
Centralized routing Distributed routing
Circuit-switched (evolving toward packet switching) Packet-switched (evolving toward emulation of circuit switching)
Seamless connectivity (low call drops during handoffs) Frequency path break due to mobility
High cost and time of deployment Quick and cost-effective deployment
Reuse of frequency spectrum through geographical channel
reuse
Dynamic frequency reuse based on carrier sense mechanism
Easier to achieve time synchronization Time synchronization is difficult and consumes bandwidth
Easier to employ bandwidth reservation Bandwidth reservation requires complex medium access
control protocols
Application domains include mainly civilian and commercial
sector
Application domains include battlefields, emergency search and
rescue operation, and collaborative computing
high cost of network maintenance (backup power source,
staffing, etc.)
Self-organization and maintenance properties are built into the
network
Mobile hosts are of relatively low complexity Mobile hosts require more intelligence (should have a
transceiver as well as routing/switching capacity)
Major goals of routing and call admission are to maximize the
call acceptance ratio and minimize the call drop ratio
Man aim of routing is to find paths with minimum overhead and
also quick reconfiguration of broken paths
Widely deployed and currently in the third generation Several issues are to be addressed for successful commercial
deployment even though widespread use exists in defense

12. 12
Applications
•Smart cities
–Smart transport
–Smart buildings
•Environmental sensor networks
–Forests, rivers, lakes, ocean, volcanoes
•Quality control and efficiency
–Industrial processes
–Energy sector
•Safety and security
–Emergency (Search, rescue, crowd control, and commando operations; Support real-
time and fault-tolerant communication paths)
–Military (Establishing communication among a group of soldiers for tactical operations;
Coordination of military object moving at high speeds such as fleets of airplanes or ships.
Requirements: reliability, efficiency, secure communication, and multicasting routing)
What makes ad hoc so attractive:
quick deployment;
inexpensive deployment and
operation.

13. Wireless Mesh Networks
•An alternative of infrastructure for wireless network
•Deployment scenarios
–residential zones
–highways
–business zones
–important civilian regions
–university campuses
•Major advantages
–high data rate
–quick and low cost of deployment
–enhanced services
–high scalability , high availability
–easy extendibility , low cost per bit
13

14. Wireless Mesh Networks
•operate at license-free ISM bands 2.4GHz ~
5GHz
•data rate of 2Mps to 60Mbps can be supported
•Properties
–Incremental deployment or partial batch deployment can be done
–Deployment or data tx cost is economical
–Location service
–At region with high density of nodes, throughput and user
numbers can be enhanced
14

15. Wireless Sensor Networks
•A sensor network is a collection of a large
number of sensor nodes that are deployed in
a particular region
•Issues
–Mobility of nodes
–Size of the network
–Density of deployment
–Power constraints
–Data/information fusion
–Traffic distribution
15

16. Hybrid Wireless Networks
•Multi-hop cellular networks (MCNs), integrated cellular ad
hoc relay (iCAR) networks
•The capacity of a cellular network can be increased if the
network incorporates the properties of multi-hop relaying
along with the support of existing fixed infrastructure
•Major advantages
–High capacity due to increasing power range by cooperation with mobile
nodes
–Flexibility. We can find best suitable nodes for routing
–Reliability. When one BS fail, we can link to another BS through multi-hop
–Better coverage and connectivity
16

17. Issues in Ad Hoc Wireless Networks
•Medium access scheme
•Routing
•Multicasting
•Transport layer protocol
•Pricing scheme
•Quality of service provisioning
•Self-organization
•Security
•Energy management
•Addressing and service discovery
•Scalability
•Deployment considerations
17
NO SINGLE
SOLUTION TO
ANY OF THESE
PROBLEMS!

18. 5.2.1 Medium Access Scheme
•Why it is so important:
–MAC is responsible for shared use of the transmission medium;
–performance depends on MAC protocol (e.g. Token Ring vs. Ethernet).
•Major issues in medium access scheme
–Distributed operation
–Synchronization
–Hidden terminals, exposed terminals
–Throughput
–Access delay
–Fairness
–Real-time traffic support
–Resource reservation
–Ability to measure resource availability
–Capability for power control
–Adaptive rate control
–Use of directional antennas

19. 19
Hidden terminal problem: collisions  inefficient bandwidth utilization.
Exposed terminal problem: inability to transmit  inefficient bandwidth utilization.

20. 5.2.2 Routing
•Routing’s responsibilities
–Exchanging the route information
–Finding a feasible path
–Gathering information about path breaks
–Mending the broken paths
–Utilizing minimum bandwidth
•Major challenges for routing protocol
–Mobility
–Bandwidth constraint
–Error-prone and shared channel
–Location-dependent contention

21. 5.2.2 Routing (Cont.)
•Major requirements of a routing protocol in ad hoc
–Minimum route acquisition delay
–Quick route reconfiguration
–Loop-free routing
–Distributed routing approach
–Minimum control overhead
–Scalability
–Provisioning of QoS
–Support for time-sensitive traffic
–Security and privacy

22. 5.2.3 Multicasting
•Multicasting plays an important role in the typical
applications of ad hoc wireless networks, namely,
emergency search-and-rescue operations and military
communication
•Provisioning of multiple links among the nodes in ad hoc
results in a mesh-shaped structure
•The major issues in designing multicast
–Robustness
–Efficiency
–Control overhead
–Quality of service
–Efficient group management
–Scalability
–Security

23. 5.2.4 Transport Layer Protocols
•The main objectives of the transport layer protocols
include setting up and maintaining end-to-end
connections, reliable end-to-end delivery of data
packets, flow control, and congestion control
•Why not to go with UDP:
–does not perform ow and congestion control and reliable end-to-end
transfer;
–result: increase on contention ! losses.
•Performance degradation stems from:
–high error rate;
–frequent path breaks;
–presence of 'old' routing information;
–network partitioning.

24. 5.2.5 Pricing Scheme
•We need a pricing scheme for compensating
relaying node for their consumption of
resources such as battery charge and
computing power

25. 5.2.6 Quality of Service Provisioning
•QoS is the performance level of services
offered by a service provider or a network to
the user
•QoS parameters
•QoS-aware routing
•Qos framework

26. 5.2.7 Self-Organization
•One very important property that an ad hoc
should exhibit is organizing and maintaining
the network by itself
•Major activities in self organization
–neighbor discovery
–topology reorganization
–topology organization

27. 5.2.8 Security
•What makes ad hoc more vulnerable to attacks:
–lack of central coordination;
–shared wireless medium.
•The attacks against ad-hoc networks are generally classified into:
–passive attacks:
•how: malicious nodes attempt to obtain information relayed in the network;
•damage: no damage to operation of the network, just capture if information.
–active attacks: Active attacks disrupt the operation of the network and classfiied
into the following types:
•external attacks: attacks executed by nodes outside the network;
•internal attacks: attacks executed by nodes belonging to the same network
•Major security threats
–Denial of service
–Resource consumption (energy depletion and buffer overflow)
–Host impersonation
–Information disclosure
–Interference 27

28. 5.2.9 Addressing and Service Discovery
•No centralized control.
•The following features are required for ad-hoc addressing
scheme:
–Global unique address;
–Autoconfiguration of addresses;
–Duplicate address detection mechanism.
•The following features are required for ad-hoc network to be
meaningful:
–automatic service advertisement mechanism:
•should allow to identify the current location of the service;
•why current: it is not possible to assume static service locations in ad hoc
networks.
–integration of service discovery protocols and routing protocols:
–may allow to easily find the necessary service in a network;
–why not so good: violate the traditional design objectives of the routing protocol.

29. 5.2.10 Energy Management
•Energy management can be classified into
following categories
–Transmission power management
–Battery energy management
–Processor power management
–Devices power management

30. 5.2.11 Scalability
•When size of ad hoc wireless network
growing up, there are some problems such as
install, latency, periodic routing overhead
•Hierarchical topology system can improve
this problem

31. 5.2.12 Deployment Considerations
•The deployment of a commercial ad hoc wireless network has the
following benefits comparing to wired networks
–Low cost of deployment
–Incremental deployment
–Short deployment time
–Reconfigurability
•Issues of considering deployment of ad hoc
–Scenario of deployment
–Required longevity of network
–Area of coverage
–Service availability
–Operational integration with other infrastructure
–Choice of protocols

32. Ad Hoc Wireless in Internet
•Similar to wireless internet, the ad hoc wireless internet
extends the service of the Internet to the end user over
an ad hoc wireless network
•Issues to be consider for a successful ad hoc wireless
Internet:
–Gateways: entry points to the wired Internet
–Address mobility: similar to the Mobile IP
–Routing: major problem in ad hoc wireless Internet
–Transport layer protocol
–Load balancing, pricing/billing, security, QoS
–Service, address, and location discovery
32

33. 33

34. 34

35. 35
Summary
•Back in the 1970s, researchers started laying the foundations of
ad hoc wireless networks with projects like ALOHANet, PRNet,
etc.
•Mobile ad hoc networks consist of mobile nodes communicating
wirelessly in a multi-hop manner.
•They have many interesting applications, ranging from military
to sensor networks.
•They have many research challenges in terms of:
–communication
–positioning
–data management

36. 36
Related reading
•Chapter 5 of textbook:
–Ad Hoc Wireless Networks. Architectures and Protocols
(Prentice Hall Communications Engineering and Emerging
Technologies Series). C.Siva Ram Murthy and B.S. Manoj.
ISBN 0-13-147023-X, 2004.

37. Problems for MAC to deal with
•Aim of MAC: provide fair access to shared broadcast radio channel.
•Issues to deal with:
–Bandwidth efficiency: must be maximized.
–Real-time traffic support:: should be provided.
–Synchronization: sometimes needed, e.g. TDMA.
–Shared broadcast medium: collisions must be avoided/minimized.
–Lack of central coordination: fully distributed MAC design.
–Hidden node problem
–Exposed node problem
–Mobility of nodes
•loss of connectivity;
•network partitioning;
•bit errors.
37

38. MAC Design goals
•What we want from MAC protocol:
–allow fair access to the shared radio medium;
–operation of the protocol should be distributed;
–should support real-time traffic;
–the access delay must be minimized;
–available bandwidth must be utilized efficiently;
–fair bandwidth allocation to competing nodes;
–control overhead must be minimized;
–the effects of hidden/exposed terminals must be minimized;
–must be scalable;
–should minimize power consumption;
–should provide synchronization between nodes.
38

39. Classification of MAC protocols
•Contention-based protocols
–A node does not make any resource reservation a priori
–It cannot provide QoS guarantee
–Two types of random access
•Sender-initiated protocols
–Single-channel sender-initiated protocols
–Multi-channel sender-initiated protocols
•Receiver-initiated protocols
•Contention-based protocols with reservation mechanisms
–Support real-time traffic
–Reserve bandwidth a priori
–Synchronous protocols: Global time synchronization is difficult to achieve
–Asynchronous protocols: Not require global synchronization
•Contention-based protocols with scheduling
–Packet scheduling at nodes and
–Scheduling nodes for access to the channel
39

40. Classification of MAC protocols
40

41. Contention-Based Protocols
•The basic idea: contention for the resource, winning node transmits
•CSMA operates as follows:
–the sender sense the channel for the carrier signal;
–if the carrier is present it retries to sense the channel after some time (exp. back-
off);
–if not, the sender transmits a packet.
•The following shortcomings are inherent to CSMA/CA:
–hidden terminal problem leading to frequent collisions;
–exposed terminal problem leading to worse bandwidth utilization.
•To avoid it:
–virtual carrier sensing;
–RTS-CTS handshake before transmission.
41

42. MACA Protocol
•Multiple access collision avoidance protocol proposed by Karn in
1990
•MACA does not make use of carrier-sensing
•Request-to-send (RTS), clear-to-send (CTS), DATA messages
•Use binary exponential back-off (BEB) algorithm for retry
•Both the RTS and CTS packets carry the expected duration of
the data packet transmission
•A node near the receiver (overcome hidden node problem)
–Hearing the CTS packet, defers its transmission till the receiver receives
the data packet
•A node near the sender (overcome exposed node problem)
–A node that only hears the RTS is free to transmit simultaneously when
the sender is transmitting data
42

43. MACA Protocol
43

44. MACA Protocol
•Problem 1 of MACA: starvation of flows:
–both S1 and S2 have the high volume of traffic, S1 seizes the channel
first;
– packets transmitted by S2 get collided and it doubles CW (CW = 2CW);
–the probability that the node S2 acquiring the channel the channel is
decreasing- over the time it gets completely blocked
•Solution: Modify back-off algorithm
–the packet header contains the field set to the current back-off value of
the transmitting node;
–a node receiving this packet copies this value to its back-off counter
(fairness);
44

45. MACA Protocol
•Problem 2 of MACA: fast adjustment of CW:
–when a node successfully transmits a packet; CW = CWmin after
every successful transmission
–when a collisions is detected by a node.
–Solution: multiplicative (1.5) increase when collision, linear
decrease when success.
45

46. MACA Protocol
•Problem 3: per node fairness
–Solution: Implement per flow fairness as opposed to the per node
fairness
–Multiple queues at every node one for each data stream and
running back-off algorithm independently for each queue
–Top-most packets in queue gives how klo0ng node need to wait for
RTS transmission
•Problem 4: Recovering from transmission error lies with the
transport layer
–Solution: An extra control packet ACK used in data link layer
–If ACK is not received by sender, the sender would retry by
transmitting an RTS for the same packet and the back-off counter
is incremented
–The receiver, instead sending back a CTS, sends an ACK for the
packet received 46

47. MACA Protocol
•Problem 5 of MACA: an exposed node which received only the RTS not
CTS is free to transmit.
–node S2 hears RTS but not CTS (exposed node);
–S2 initiates transfer to R2;
–DATA from S1 and CTS from R2 may collide, CW unnecessary increases at
S2.
–Solution: – Before transmitting the data packet, the source node transmits the
data-sending (DS) – 30 bytes packet to ensure RTS-CTS exchange successful
47

48. MACA Protocol
•Problem 6 of MACA: neighbor receivers problem
–Solution: usage of request-for-request (RRTS) to send packets:
–if R1 had received RTS (S1) and did not respond due to R2-S2 it backs off
sends RRTS;
–R2 hears RRTS waits for successive RTS-CTS between S1 and R1;
–S1 hears the RRTS, transmits regular RTS and RTS-CTS-DATA-ACK
•Synchronization information needs to be propagated to the concerned
nodes
•If a node had received an RTS previously for which it was not able to
respond because there exists on-going transmission, then it waits for the
next contention period and transmits RRTS takes place.
48

49. MACA Protocol
49

50. MACAW
•MACAW Designed to overcome MACA problems
–Back-off algorithm has been modified
–To prevent large variations in the back-off values - A
multiplicative increase and linear decrease (MILD) is used
–Implement per flow fairness as opposed to the per node fairness
–An extra control packet ACK used in MACAW
–Exposed node problem - Before transmitting the data packet,
the source node transmits the data-sending (DS) packet to
ensure RTS-CTS exchange successful
–Another control packet: request for request to send (RRTS) -
Synchronization information needs to be propagated to the
concerned nodes
50

51. 51

52. 52

53. 53

54. 54

55. 55

56. 56

57. 57

58. 58

59. Contention-based protocols with
reservations
Use bandwidth reservation techniques:
• contention occurs here only at resource reservation
phase;
• once bandwidth is reserved a node gets an exclusive
access to the media.
59

60. 60

61. 61

62. 62

63. 63

64. 64

65. 65

66. Contention-based protocols with
scheduling mechanisms
Aim is on transmission scheduling at nodes considering
metrics:
• delay targets of packets;
• trac load at nodes;
• remaining battery power at nodes, etc.
66

67. 67

68. 68

69. 69

70. 70

71. 71

72. 72

73. 73

74. MAC protocols for directional
antennas
The following advantages can be achieved using the
directional antennas:
• reduced signal interference;
• increase in system throughput;
• improved channel reuse.
74

75. 75

76. 76

77. 77

78. 78

79. 79

80. 80

81. 81

82. 82

83. 83

84. 84

85. 85

86. 86

87. 87

88. 88

89. 89

90. 90

91. 91

92. 92

93. 93

94. 94

95. 95

96. 96