Transcript Introduction - School of Electrical Engineering and Computer Science

Self Organization in Ad Hoc Networks
BASIL SAEED, ATTA ZAINALDIN
Professor: ABDULMOTALEB EL SADDIK
Course: ELG 5121
November 26, 2010
Outline





Overview of Ad Hoc Networks
Self organization Ad hoc Networks
Problems with self organizing ad hoc networks
ZRP Protocol
Small World graph phenomenon
 Terminode Routing
 Grid Routing
 Comparison
 Conclusion
 References
Ad hoc Networks Overview

Local area network (LAN) that is built spontaneously as devices connect.

Instead of relying on a base station to coordinate the flow of messages to
each node in the network, the individual network nodes forward packets to
and from each other (act as routers).

A network can be integrated with existing infrastructure.
Self Organization Ad hoc Networks
 Decentralized and Non-authorized networks unlike internet that has
specific characteristics:
– Self-healing - mechanisms that allow to detect, localize, and repair failures
automatically; primarily distinguished by the cause of the failure
– Self-configuration - methods for (re-)generating adequate configurations depending on
the current situation in terms of environmental circumstances, e.g. connectivity, quality
of service parameters
– Self-management - capability to maintain devices or networks depending on the current
parameters of the system
– Self-optimization - similar to self-management but focuses on the optimal choice of
methods and their parameters based on the system behaviour
– Adaptation - adaptation to changing environmental conditions, e.g. the changing number
of neighbouring nodes
 Advantages:
– Scalability
Problems with Self Organization Ad hoc
Networks
 There are some problems that may occur when designing a self
organized ad hoc network;





Configuration
Discovery
Routing
Cooperation incentive
Security
Configuration
 DHCP is used in the internet
 DHCP cannot be used in self organizing networks
 Using Mobile IP:
 Designed to allow mobile device users to move from one network to
another while maintaining a permanent IP address.
 Adding care of address capability to DHCP
 An IP address associated with mobile node that is visiting a foreign
link.
Discovery
 A node has to be discovered and located in the network
Solution:
1) Global Positioning system (GPS)
 Bad Signal
2) A Self Positioning Algorithm (SPA)
 using the distance between nodes to form a coordinate system
which is then used to locate and discover the node.
 Uses time of arrival to obtain the distance between neighbors
Cooperation
 Ad hoc networks are highly cooperative
 Nodes are selfish
 Nodes tend to use services provided by other nodes, but not to provide
services for free to the community
 There should be a way to:
 Encourage users to provide services
 Discourage users to from overloading the network
 Cooperation incentives, i.e. Nuglet
 Nuglet: Virtual Currency
Security
 In self organized networks, the nodes are easy to be attack;
 The channel is wireless
 The network is decentralized
 Solution
 Node 1 asks for secure communication by send Cipher Suites
 Node 2 chooses the strongest Cipher and notifies node 1
 Node 2 send digital certificate
 Node 1 uses random number to encrypted the public key of node 2
 Node 2 decrypted the message using its private key
 From the random number, both node can encrypt and decrypt the data
Routing Protocols

There are two routing protocol categories for ad hoc networks:

Proactive Routing Protocols: maintain routing information
independently of need for communication i.e. OLSR

Reactive Routing Protocol: discover route only when you
need it researchers chose i.e. AODV
Cont.
 OLSR Protocol:
a HELLO message which is used to discover the
information about the link status and the host’s
neighbours
Topology Control message which is used to send
information all over the network about the node’s
neighbours
Cont.
 Pros.
 Low latency, suitable for real-time traffic
 Cons.
 Bandwidth might get wasted due to periodic updates
Cont.

AODV protocol contains 3 type of messages;




Route Request message (RREQ)
Route Reply message (RREP)
Route Error message (RERR)
Source node uses an expanding ring search technique to establish a route to13
the destination node.
Cont.
Pros.
 Saves energy and bandwidth during inactivity
 Less overheads which are needed to track the route from the source
to destination nodes.
 It responds fast in the topological changes, and updates only the
nodes that are involved in this change using RRER.
Cons.
 Significant delays may occur as a result of route discovery
14
Zone Routing Protocol
• Hybrid routing protocol uses both combination of proactive and reactive
routing protocols
• Uses reactive (inter-zone) and proactive (intra-zone) routing protocols to
maintain routes
• Nodes use intra-zone routing protocol to maintain local routing tables to
neighbours
• Nodes use inter-zone routing protocol to communicate with nodes outside
of their zone
Cont.
Inter Zone Routing
Intra Zone Routing
Zone Radius = 2
How ZRP works
 If destination is in same zone, the data is delivered directly
 If in different zone, source broadcasts Route Request to all nodes of its
zone
 If destination is in border node’s zone, border node responds with Route
Reply
 Source forwards data to appropriate border node to reach destination
Cont.
E
C
G
D
A
B
H
S
Advantages and Disadvantages
Advantages:
 The amount of the data stored in each node is smaller than using a pure
table-driven routing resulting in a faster protocol than using a pure reactive
routing protocol.
 Can use single and multipath
Disadvantages:
 Large overhead than proactive and reactive protocols
 If there are many zone overlaps, redundant Route Request messages are
flooded through the network (waste of Bandwidth)
 Large delay due to the procedure of discovering the route from source to
destination (reactive/inter-zone)
– Not applicable for multimedia applications
Regular Graph vs. Random Graph
- High characteristic path length
- High degree of clustering.
- Low characteristic path length
- Low degree of clustering.
Small World Graph
 Low characteristic path length
 High degree of clustering.
 Two types of routing protocols
which use Small World Graph:
1) Terminode Routing
2) GRID Routing
Terminode Routing
 Every Terminode uses two Addresses for Identification:
1) End System Unique Identifier (EUI): Permanent Address.
2) Location Dependent Address (LDA): Temporary Address.
- LDA address is obtained either by:
a) GPS (Global Positioning System).
b) No GPS (Self Positioning Algorithm SPA)
Cont.
 Packet forwarding is done using two routing categories:
 Terminode Local Routing (TLR):
Uses to reach the destination Distance Vector Intra Zone
Routing (Proactive) in ZRP via EUI permanent addresses
without using location information
 Terminode Remote Routing (TRR):
 Uses to reach the destination the geographical location
(LDA), which consists of
 Friend Assisted Path Discovery (FAPD)
 Anchored Geodesic Packet Forwarding (AGPF)
 Path Maintenance
 Multipath Routing
 TRR is perform until some node finds destination to be between 2
hops, from there on, only TLR is used
Anchored Geodesic Packet Forwarding (AGPF)
 Allow data to be sent to remote terminode based on locations of node
 Data be sent along the Anchored path
– Anchored path is the route from source to destination and provided with a list of Anchore
– Anchore point describe the geographical coordinates (LDA)
–
S
Good Anchore: Path that avoids obstacles and un-useful terminodes from source to destination
D
Other elements
 Friend assisted path discovery
 This method is used to obtain the Anchore paths
 The Terminode may contact its friends in order to find an
Anchored path to the destination of interest
 Path maintenances
 Allows a Terminode to improve the acquired paths
 Multipath routing
 Maintain several paths to a single destination
GPS and SPA
1) Global Positioning system (GPS)




Nodes know their geo coordinates
Route to move packet closer to end point
Propagate geo info by flooding
Not efficient with bad signals
2) A Self Positioning Algorithm (SPA)


Using the distance between nodes to form a coordinate system
which is then used to locate and discover the node.
Uses time of arrival to obtain the distance between neighbors
GRID Routing
 Divide the physical into squares called grids, with increasing the size of the grid
 Server location: Each Node selects location servers in each of the three sibling
squares in each level
 Ex: Node B selects at :
• Level 0: 10, 23 and 17, Level 1: 22,33 and 60 and Level 2: 19,21 and 28
Level 0
B
Level 1
7
44 10
23
67
17
54
45
33
80
60
34
19
Level 3
1
44
99
Level 2
22
77
47
88
84
21
56
26
Location Servers
28
27
49
50
Cont.
 Packet Forwarding: Sender forwards packets using geographic forwarding
to the least node greater than or equal to node desired destination ID.
• Ex: A sends packets to B using servers located at 26, 19 and 7
B
7
44 10
23
67
17
54
45
33
80
60
22
1
44
34
19
26
99
32
62
77
47
28
88
84
27
21
56
49
50
90
A
Comparison
 Terminode
 Hierarchical routing approach:
scalable
 No GPS: SPA
 Complex and more
information
 Always find a path to
destination
 GRID
 Hierarchical routing approach:
scalable
 No GPS: allows positionunaware nodes to use
position-aware nodes as
proxies
 Simpler and less information
 May Fail to find a path to
destination
Conclusion
 Self Organization Ad hoc Networks have some specific characteristics
 Small world graphs with low characteristic paths and high level of
clustering can organize a model for Self Organization Ad hoc
Networks
 Terminode and GRID routing can solve configuration, discovery, and
routing problems faced in self configured ad hoc networks
 When GPS is available, GRID routing is simpler to process.
 When GPS is not Available, Terminode routing is more robust
and has less probability of failure.
 Next step, look for solutions for cooperation and security problems
References
[1] Chlamtac I., Conti M., Liu J. J.-N.: "Mobile ad hoc networking:
imperatives and challenges". Ad Hoc Networks,Elsevier, Vol. 1, Issue
1, p. 13-64 (2003).
[2] F. Dressler, "Self-Organization in Ad Hoc Networks: Overview and
Classification," University of Erlangen, Dept. of Computer Science 7,
Technical Report 02/06, March 2006.
[3] L. Buttyán, J.-P. Hubaux, “Nuglets: a Virtual Currency to Stimulate
Cooperation in Self-Organized Mobile Ad Hoc Networks,” Technical
report No. DSC/2001/001, Swiss Federal Institution of Technology,
Lausanne, January 2001. http://icawww.epfl.ch/hubaux/
[4] Zhijiang Chang, G. Gaydadji ev, S. Vassiliadis, "Routing Protocols for
Mobile Ad hoc Networks: Current Development and evaluation.“
Computer Engineering laboratory, EEMCS, Delft University of
Technology, April 2005.
[5] J.Haas and M. R. Pearlman, "The Zone Routing Protocol (ZRP) for Ad
Hoc Networks," IETF Internet Draft, June 1999
Cont.
[6] Nature Publishing Grouping. “Collective dynamics of 'small-world' networks“.
From http://www.nature.com/nature/journal/v393/n6684/full/393440a0.html
[7] L. Blazevic, S. Giordano, J. Y. Le Boudec “Self organized terminode routing
simulation“ Proceedings of ACM International Workshop on Modeling Analysis
and Simulation of Wireless and Mobile systems (MSWiM 2001), Rome, Italy,
July 2001
[8] L. Blazevic, S. Giordano, J. Y. Le Boudec "Anchored Path Discovery in
Terminode Routing" The Second IFIP-TC6 Networking Conference
(Networking 2002) Proceedings, Pisa, May 2002
[9] L. Blazevic, L. Buttyan, S. Capkun, S. Giordano, J. Hubaux, and J.
Boudec,”Self-Organization in Mobile Ad-hoc Networks: The Approach of
Terminodes,"IEEE Communication Magazine, vol. 39, no. 6, pp. 166{174, June
2001.
[10] W.-H. Liao, Y.-C. Tseng, and J.-P. Sheu, “GRID: a fully location-aware routing
protocol for mobile ad hoc networks,” Telecommunication Systems, vol. 18,no.
1, pp. 37–60, Sep. 2001.
Questions