Wireless Mesh Networking

From WirelessAfrica

Introduction

A network is made up of nodes. The complextiy of mesh routing would make it very difficult, if not imnpossible to configure and manage large mesh networks. Therefore, intelligence has to be built into the nodes so that they can handle some of the configuration and management of the network. This becomes more important when the users/owners of the network aren't very computer literate. There are several aspects to this intelligence including the routing algorithms that tell the node how to route information to other nodes. These algorithms are implemented in Mesh routing protocols.

These nodes also need to be affordable, especially in the case of rural networks.

Mesh Routing Protocols

A large amount of research at Meraka CSIR will go into comparing the performance of various mesh routing protocols and understanding their suitability to different networking scenarios such as network size, latency and throughput requirements and the amount of mobility. Below is a list of mesh networking protocols that will be tested on our testbed networks.

OLSR


Optimized Link State Routing was developed by P. Jacquet at INRIA in france. This is a proactive protocol that addresses the issue of flooding the network with link state information across the network. OLSR reduced the overhead of by requiring fewer nodes to forward the link state information. This is done broadcasting a lnk state from node X through select multipoint relays.

Optimised Link State Routing

More info: OLSR


AODV


Ad-hoc On-Demand Distance Vector Routing was developed by C. Perkins while working at Sun Microsystems Laboratories. This is a reactive protocol that attempts to improve on DSR by maintaining routing tables with one entry per destination at the nodes. When a source node needs a route to a destination, it initiates a route discovery process to locate the destination node. The source node floods a query packet requesting a route to be set up to the destination. A reply is sent back directly to the source node either by the destination itself or any other intermediate node that has a current route to the destination. Since nodes reply to the first arriving route request, AODV favours the least congested route instead of the shortest route.

Ad-hoc On-Demand Distance Vector Routing

HSLS


Hazy Sighted Link State Routing was developed by BBN and implemented by cuwireless(See CuWIN Visit). In general a reactive protocol is local (only knows about its immediate neighbours) and a proactive protocol is global (stores routing information for entire network). HSLS is neither glocal nor local, each node has a different view of the network. The link -state approach that is followed is: send an update every ti seconds with a network scope of ri hops. The HSLS algorithm finds ti and ri so that the performance is optimized. HSLS is performance-driven, focusing on average system performance instead of focusing on handling exceptional rare cases whose impact on the overall system performance is not clear.

Hazy Sighted Link State Routing


ZRP


The Zone routing protocol was developed by Z.J. Haas (Associate professor, Cornell University), a lead researcher in the field of Ad Hoc networking. The ZRP is an example of a hybrid reactive/proactive routing protocol. On one hand, it limits the scope of the proactive procedure only to the node’s local neighbourhood, minimizing the waste associated with the purely proactive schemes. On the other hand, the search throughout the network, although it is global, is performed by efficiently querying selected nodes in the network, as opposed to querying all the network nodes. The protocol identifies multiple loop-free routes to the destination, increasing reliability and performance. Routing is flat rather than hierarchical, reducing organizational overhead, allowing optimal routes to be discovered, and reducing the threat of network congestion. Haas explains that the most appealing feature of the protocol is that its behaviour is adaptive, based on the current configuration of the network and the behaviour of the users.

Zone Routing Protocol


This protocol is very attractive for a city type network which will consist of both static wireless nodes installed on structures such as houses and moving nodes which could be people or cars. The local neighbourhood to the moving nodes can be proactive and react quickly whereas the static intrazone backbone will operate on a proactive scheme.


Other


Mobile Mesh One of the first mesh routing implementations that was looked at is, MobileMesh for Linux and the Windows equivalent IpMesh. The interest/activity around these seemed to be fading with the implmentation of more popular routing protocols like OLSR.


Standardisation


The IEEE and IETF are working on Mesh Standards.

Network Simulation

Why? to simulate mesh networks, VOIP, etc, to determine placement of Internet access gateways, suitability for rural community access given terrain features, distance between participants and the like.

Requirements: We need to choose a simulator that is customisable, well-known so that we can export or share models, easy to use, inexpensive, has a predeveloped library of protocols, propagation characteristics, etc, that could be tweaked for our requirements. Should be able to incorporate terrain models (I think)

Someone should investigate the following options and provide comment here...

Proprietary candidates: - Opnet - Comnet III

Open Source candidates: - NS-2 - Ptolemy (Java based) - OMNet++ - CSim++ - SimJava - JavaSim. There is some confusion of packages here as Lund Institute of Technology (Sweden), Ohio State and University of Newcastle have all created something called JavaSim. Ohio State seem to have the most advanced package which they have since renamed to J-Sim.

There is a good listing of simulation languages, IDEs and simulators here

There is also a general purpose simulation language in Python called SimPy which appears to be rather interesting but without a lot of add-ons at this stage.

At this stage, Opnet, Ptolemy, SimJava and OMNet++ appear to be most interesting...

Network Visualisation

In order to get a better idea of what is going on within the inner workings of network routings, it is particularly useful to have a graphical representation thereof. Several options are being looked at into providing such a representation, including a plugin feature of the OLSR.org implementation of the OLSR protocol, called the OLSR Dot Draw plugin.

OLSR Dot Draw shows some of the work done in implementing a "first-cut" visualisation.

Outdoor mesh networks require planning and co-ordination and a visualisation tool combined with location information would be a valuable tool. Freifunk have implemented such a tool, which we may try on the Pretoria Mesh.

Test Networks

50-node Indoor Mesh

Pretoria Mesh

Mpumulanga Mesh

Network Services

VOIP

Internet Access

Security Surveilance

Local Content

Network Security

VPN(Virtual Private Networking) can be implemented on a mesh network to provide secure virutal networks within the bigger network. The HowTos page describes how to set one up.

Low-cost devices

Node

Several options are being looked at including Wireless Routers, SBC(Single Board Computers) and Open Hardware

Antennae

Home-Brew Antennae

User Terminals

Mobile Devices


See Links for other Mesh Network initiatives