Wireless Mesh Networking; An
Investigation Into AODV Routing
Fourth Year Computer Systems Engineering Project By
Matthew Sinclair
Supervisors Firas Al-Ali & Amal Punchihewa
Institute of Information Sciences and Technology
Massey University
Overview
" Introduction
" Ad-Hoc On Demand Distance Vector (AODV)
Routing
" My AODV Project
" The Future of Mesh Networking
" Conclusion
Matthew Sinclair - 2003 2
Introduction to Wireless Networking
" Wireless networking; networking or connecting computers
together using radio transmissions, rather then electrical
signals through a wire, to send information.
" A wireless node, such as a computer, connects wirelessly
to a network of nodes through its wireless network interface
card (NIC).
" Currently a large variety of wireless networking techniques
and protocols exist.
Matthew Sinclair - 2003 3
Introduction to Wireless Networking
Wireless Networking
PAN LAN MAN Cellular Satellite
HomeRF 2G
GEO
Bluetooth LMDS
MEO
HIPERLAN 2.5G
IrDA MMDS
LEO
IEEE 802.11 3G
Matthew Sinclair - 2003 4
Introduction to Wireless Networking
" IEEE Working Group 802.11 is tasked with devising
wireless Local Area Networking standards
" Original 802.11wireless LAN protocol supported 1-2Mbps
transfer rate in the 2.4GHz frequency band
" Three extensions, 802.11b, 802.11a and 802.11g have
since been defined
Matthew Sinclair - 2003 5
Introduction to Wireless Networking
Protocol 802.11a 802.11b 802.11g
Raw Data Rate and Raw Data: 54Mbps Raw Data: 11Mbps Raw Data: 54Mbps
Actual Throughput
Actual: 27Mbps Actual: 5Mbps Actual: 10-20Mbps
Frequency Band Used 5GHz 2.4GHz 2.4GHz
Modulation Technique Orthogonal Frequency Direct Sequence Spread OFDM and DSSS CCK
Division Multiplexing Spectrum with
(OFDM) Complementary Code
Keying (DSSS CCK)
Maximum Radio Range 50m indoors 150m indoors 150m indoors
(Product Dependant) 200m outdoors 500m outdoors 500m outdoors
Other compatible HIPERLAN 802.11, 802.11g 802.11b
wireless protocols
General Cost of PCI $200 $150 $150
Wireless Network Card
Matthew Sinclair - 2003 6
Introduction to Wireless Networking
" 802.11 defines three different wireless network
configurations:
1) Independent Basic Service Set (IBSS).
Ad-Hoc mode; nodes connect directly to each other
2) Basic Service Set (BSS).
Infrastructure mode; nodes connect indirectly to each other
through an Access Point
3) Extended Service Set (ESS).
Multiple Basic Service Sets
Matthew Sinclair - 2003 7
Introduction to Mesh Networking
" Problems with conventional wireless networks:
" Infrastructure mode: Static and expensive Access Points are required to
extend the range of the network
" Ad-Hoc mode: Access Points no longer needed, but node can only
connect to other nodes within its personal radio transmission range
" Solution: Wireless Mesh Networking
" nodes have the ability to relay on data that isn t intended for them
personally to other nodes around them, extending the coverage of an Ad-
Hoc wireless network and creating a mesh of connections between
wireless nodes.
Matthew Sinclair - 2003 8
Introduction to Mesh Networking
" Conventional Ad-Hoc Wireless Networking
Range Of Wireless
Nodes
Wireless Node
Wireless Node
A : Sender
B: Receiver
Wireless Nodes are out of range of each other and so cannot
communicate. Conventional solution is to move nodes closer
or to add an Access Point in between.
Matthew Sinclair - 2003 9
Introduction to Mesh Networking
" Wireless Mesh Networking
Mesh enabled node is in range of both  connection
made between wireless nodes A and B.
Wireless Node
Mesh Enabled
Wireless Node
A : Sender
Node
B: Receiver
Matthew Sinclair - 2003 10
Introduction to Mesh Networking
MeshNetworks,
America
Locust World, UK
Mesh network solutions
Implementations
- Turning old computers with
for: - Military
Of Wireless
wireless cards into mesh
- Emergency response
Mesh
enabled  Access Points
Networking - Law Enforcement
MOTERAN Networks, Germany
- Installing mesh enabled devices in cars
- Combined effort between Mitsubishi and
Deutsche Telekom
Matthew Sinclair - 2003 11
Introduction to Mesh Networking
" Mesh enabled wireless nodes have the ability to relay or
route data and information on to other nodes around them.
 This ability doesn t come with standard wireless NICs
" It requires a routing protocol  a standard that controls how
data is moved or directed around a network  to be
installed on the wireless node.
Matthew Sinclair - 2003 12
Introduction to Mesh Networking
" What is involved when routing data in a wireless mesh
network?
 A source node wants to send data to a destination node
" Each node in a network has a unique address for that network
 The source node may have to go through it intermediate node to
reach an out of range destination node
" Needs a process to find a route i.e. what address to send the data to
 Solution: a wireless ad-hoc routing algorithm such as AODV
routing
Matthew Sinclair - 2003 13
AODV
On Demand route finding Comes from the DSDV
Designed for mobile, changing
algorithm compared to routing algorithm which
wireless networks
table based AODV is based on
Ad-Hoc On Demand Distance Vector
(AODV) Routing Algorithm
A current working item of the Mobile One of a number of ad-hoc wireless
Ad-Hoc Networks (MANET) working group routing algorithms. Chosen for
Authors C.Perkins, E.Royer, S.Das investigation due to its popularity and
availability of software implementations
Matthew Sinclair - 2003 14
AODV
Address Next
Hop
N1 N4
Route Request Route Request
Route Reply
N2 N4 N5
Route Reply
Route Reply
Route Error
N1
Route Request
Route Error
Route Request
N3
N6
N7
Route Request Route Request
Route Error (RERR)
Route Reply (RREP)
Route Request (RREQ)
Matthew Sinclair - 2003 15
My Project
" Aim: To implement and analyse and make recommendations for
a simple AODV wireless network
Hardware Used Software Used
" Three Pentium 4, 2.0GHz PCs " Mandrake Linux 9 operating system
" Each PC with an IEEE 802.11b compatible, " kernelAODV  AODV routing software from
MicroNet wireless PCI card. NIST
" DLink 802.11b wireless Access Point, used " IPTables  firewall to simulate node
for throughput comparison separation
" netPerf  network throughput analysis tool
Matthew Sinclair - 2003 16
Methodology
" General approach of project
 Installed wireless card and drivers
 Compiled and installed NIST AODV software
 Setup firewall to simulate distance between nodes
 Started AODV and ran tests
" Project Limitations
 Only three computers, maximum of only one intermediate node
 Simulated in a laboratory, not a real world simulation
" Distance separation between nodes simulated
" Nodes are static
Matthew Sinclair - 2003 17
Methodology
Node 1 Node 2 Node 3
Test Application e.g. Test Application e.g. Test Application e.g.
NetPerf Client NetPerf NetPerf Server
NIST AODV Routing NIST AODV Routing NIST AODV Routing
Software Software Software
IPTables IPTables IPTables
Wireless Card Wireless Card Wireless Card
Route Reply
Route Reply
Route Request
Route Request
Matthew Sinclair - 2003 18
Methodology
" Screen shot of wireless card configuration
Extended Service Set ID (ESSID) set the same
on all computers
Mode set
to Ad-Hoc
Control messages
and fragmentation
Bit Rate
turned off
set to 11Mb/s
Matthew Sinclair - 2003 19
Results
Route Request (RREQ)
10.0.0.1 = Node 1
generated for Node 3
by Node 1
10.0.0.3 = Node 3
10.0.0.2 = Node 2
Route Reply (RREP)
Node 2 also
generated for Node 1
generates a
by Node 2
gratuitous RREP
for Node 3
Matthew Sinclair - 2003 20
Results
Hop count = 2
Next Hop address = Node 2
Node 1 s AODV
Route Table
Node 2 s route table
shows the forwarding
it does for
nodes 1 and 3
Hop count = 2
Next Hop address = Node 2
Node 3 s AODV
Route Table
Matthew Sinclair - 2003 21
Results
" Network Throughput Results
AP AP
N2 N2
5
N3 N3
N1 N1
4
3
AP AP
N2 N2
2
N3 N3
N1 N1
1
0
N1 = Node 1
AP
Tests
N2 = Node 2
N2
N3 = Node 3
N3
N1
AP = Access Point
Matthew Sinclair - 2003 22
Mode
AODV:
N1 to N2
Standard Ad-Hoc
Mode
Throughput Mb/s
AODV:
AODV:
N1, N2, N3
N3, N2, N1
Infrastructure
Future Work
" More wireless nodes
" Mobile and changing nodes
" Experiment out of the laboratory
" AODV over long distance connections
Matthew Sinclair - 2003 23
The Future of Wireless Mesh
Networking
" How could wireless mesh networking help us?
" For New Zealand a current issue is fast rural
Internet
 One current solution is cellphone technology
" Problem: One cellphone tower costs around $100,000 and
provides maximum speeds up to 2 Mbp/s (3G cellphone
technology)
" Solution: Wireless mesh networking - one wireless card and
long range antenna costs $1000 and provides speeds up to
10 Mbp/s (802.11g)
Matthew Sinclair - 2003 24
Summary
" Wireless Networking
 Many protocols, this project concentrated on 802.11b
" Wireless Mesh Networking
 Wireless nodes being able to route data, forming a mesh of connections
" Ad-Hoc On Demand Distance Vector (AODV) Routing
 An ad-hoc, routing protocol suitable for wireless mesh networking
" AODV Project
 Implemented a simple wireless mesh network using the AODV routing protocol
" The Future of Mesh Networking
 A solution to rural Internet problems?
Matthew Sinclair - 2003 25
Conclusions
" The AODV routing algorithm is a suitable routing algorithm to
implement a wireless mesh network
" Further investigation into the impact of throughput as more hops are
added to a connection is needed for definite conclusions on how the
AODV routing algorithm affects throughput
" With further development and research, wireless mesh networking
could be an economical and feasible solution to wireless network
problems
Matthew Sinclair - 2003 26
Questions?
Matthew Sinclair - 2003 27
Wireless Networking Introduction
" Wireless nodes have to send and receive radio signals on
the same frequency or channel in order to be able to
connect to each other
" 802.11b frequency band
 2.4GHz to 2.497GHz
 Divided into 11 channels, each 22MHz
" Procedures that enables only one wireless node to use a
channel at a time to avoid interference between nodes is
part of 802.11
Matthew Sinclair - 2003 28
Wireless Networking Introduction
" Interference avoidance procedures in 802.11
 When in infrastructure mode the Access Point controls all activity
between nodes including when a node can use the channel
 When in Ad-Hoc mode, wireless nodes use two methods to avoid
interference:
" Simply check channel is free before transmitting, if busy then wait
" Use a combination of Request To Send, Clear To Send and Acknowledge
messages between nodes to coordinate communication
Matthew Sinclair - 2003 29
Introduction to Mesh Networking
" Mesh Networking Strength
 Increase of wireless range made possible without the need for
Access Points
" Mesh Networking Issues
 The use of personal resources for someone else's benefit
Matthew Sinclair - 2003 30