Simulation Environment for an Ad-Hoc Wireless Network Running the AODV Routing Algorithm

EE6950: Wireless and Mobile Networking

Class Project Report

Sameh Asaad

1. Introduction

There are two distinct approaches for enabling wireless mobile computers to communicate with each other. The first is to utilize the existing cellular network infrastructure originally developed for voice communications using cellular phones. This approach benefits from exploiting existing infrastructure to carry data as well as voice. Among the major problems of this approach is the problem of handoff: As a mobile host moves out of the range of one base station and into the range of another, how should the connection be smoothly handed over to the new base station without noticeable delay or packet loss. The other approach is to let users who wish to communicate with each other form an ad-hoc network and collaborate amongst themselves to deliver data packets from a source to its destination possibly via one or more intermediate nodes. This form of networking, although limited in range by the individual node's transmission range, has several advantages when compared to traditional cellular systems. The advantages of ad-hoc networks include:

• On demand setup: Ad-hoc wireless networks don't rely on wired basestations and therefore are capable of being deployed in places with no existing infrastructures. This is particularly useful in two scenarios:
  • Disaster recovery situations in places with non-existing or damaged communications infrastructure and rapid deployment of a communication network is needed.
  • Conferencing among a group of people who wish to form a temporary network without necessarily engaging the services of any pre-existing network in the vicinity.
• Fault Tolerance: In a cellular system, a malfunction in the base station will impair all mobiles in its cell. In ad-hoc networks, a malfunction in one node can be easily overcome through network reconfiguration.
• Unconstrained Connectivity: Wireless ad-hoc networks take advantage of the nature of the wireless communication medium. In other words, in a wired network the physical cabling is done a priori restricting the connection topology of the nodes. This restriction is not present in the wireless domain and, provided that two nodes are within hearing distance of each other, an instantaneous link between them is automatically formed.

The objective of this project is to investigate the routing problem in an ad-hoc wireless network. In particular, a novel routing algorithm: Ad-Hoc On-Demand Distance Vector Routing (AODV) as proposed by Charles E. Perkins was implemented and simulated using a collection of wireless nodes. The simulation environment was designed from ground-up using Maisie programming language.

The remainder of this report is organized as follows: Section 2 describes the basic AODV algorithm showing its design goals, architectural assumptions and principle of operation. In section 3, the simulation environment is explained: First an overview of its software architecture is shown followed by a detailed presentation of each of the major components involved. Some preliminary test results are discussed in section 4. Finally, possible directions for future work is presented in section 5.

2. The AODV Routing Algorithm

2.1 Introduction

1. To eliminate the need for global broadcast of routing information throughout the ad-hoc network. This was a major drawback with the DSDV algorithm limiting its scalability to large populations of nodes.
2. To minimize the latency when new routes are needed.

2.2 Architectural Assumptions

• Neighboring nodes can hear each other's broadcast: Neighboring nodes are nodes separated by a distance less than the transmission range of each node.
• Links between neighboring nodes are symmetric: If node A can hear node B's transmission, this implies that node B can hear node A's transmission.

2.3 Principle of Operation

• All nodes agree to forward data and routing information even if they are not directly involved in the packet being transmitted.
• A source node wishing to communicate with a destination node will first consult its routing table. If it doesn't find routing information, it will broadcast a route request message to the neighboring nodes with the following format:

  

• As the route request propagates through the network, every receiving node will update its routing table with an entry for the source node. This is called reverse path setup and is shown in Figure 1.

  

• If a node receives a route request for a destination other than itself, it will consult its routing table. If it finds a route matching the requested destination, it will unicast a route reply packet back to the source that generated the request through the reverse path. The route reply packet format is as follows:

  

  The reply will have the same sequence number as the request.

• A node receiving a route request to itself will unicast a route reply back to the requesting node with the same sequence number of the original request.
• As the route reply packet propagates back to the source, every receiving node on the reply path will update their routing table with an entry for the destination, thus forming the forward path from source to destination as shown in Figure 2.

  

• Nodes that received a route request but no matching route reply will timeout after a certain time and delete the reverse path they prepared. The assumption made here is that either there exists no path from source to destination or that this node is not on the shortest path between source and destination.
• A node receiving route requests that it cannot fulfill will relay only the first copy of similar requests and ignore all others. Similar requests have the same source and sequence number. They can occur due to multiple paths from the source of the request to the receiving node. The assumption here is that the first copy will usually take the shortest path, i.e. least number of hops and therefore should be preferred.
• A node presented with more than one route to a certain destination, either through multiple route replies or through periodic hellos will always prefer the route with less number of hops unless the more recent reply has a newer sequence number.
• All routing information have lifetimes associated with them. Routes that are not being used expire after a certain time period and are deleted from the routing table.
• Every node will actively send a periodic hello message to its neighboring nodes. The hello message has the following format:

  

• A node receiving a hello message will update its list of neighbors and route table accordingly. This ensures up-to-date routes even while nodes are moving about.
• Neighbor lists for each node also have lifetimes associated with them. When a node doesn't receive the hello message from one of its neighbors, it assumes that this neighbor has moved or has been turned off and therefore deletes its neighbor and routing information. This early detection of link breakage can be used to signal other nodes that are relying on the absent node for their routing to take corrective action. However, this feature is not implemented yet in the current simulator.

2.4 Advanced AODV features

3. Wireless Ad-Hoc Network Simulation Environment

3.1 Overview

Figure 3 shows an overview of the software architecture of the simulation envirnoment. It is composed of a collection of maisie entities, each running autonomously in an infinite loop until stopped by an end of simulation signal. Communications among these entities is done through maisie messages. Most message tpyes have a direct relation to actual communication packets (e.g. hello, rreq, data_pkt) although some messages are strictly for simualtion use (e.g. send_data). The former will have a positive time-delay associated with them while the latter are assumed to be instantaneous.

The node entities represent the mobile hosts in the ad-hoc network, each having a transmitter and receiver sections. The nodes communicate with each other through the channel entity which represents the wireless medium. The LocationManager is an entity that simulates the motion of the nodes. It updates the current position of each node depending on user configurable motion parameters and saves the updated information in a global structure called the simulation table. This is in turn used by the channel to decide which nodes are within "hearing distance" of each other. The CommunicationManager simulates the network traffic (i.e. application layer communications). It stimulates the nodes to communicate with each other by invoking the source node with a send_data message telling it which node it should talk to and the length of the data packet.

Not shown in Figure 3 is the driver entity. This is the equivalent of the main() function of a C-program. The driver entity creates all other entities and prints out all network statistics when the simulation time is over.

3.2 Assumptions

• A node can transmit and receive at the same time. In other words, there are separate uplink and downlink channels. Furthermore, the node has separate data and routing channels, thus it can transmit and receive data and routing simultaneously. However, the node cannot transmit or receive more than one data or routing packet at the same time.
• The node is assumed to have infinitely large transmission and reception buffers. The packets get buffered until consumed by the node in case of reception or until the transmitter is ready in case of transmission.
• All network operations are communication bound. This means that the processing time of the routing and data packets is negligibly small compared to the communication time.
• Wireless channel impairements are not modeled. The channel will always forward the message from one node to the next provided that they are within hearing distance. Although this is not a practical scenario, it should not affect the simulation since we are only concerned with the routing algorithm efficiency.
• The maximum speed of motion of any node is much less than the speed of transmission of the longest data packet. Therefore no partial packets are received: Either the node will receive the whole packet if it is in the range of transmission of the sending node or it will receive nothing if it is out of range.
• Currently the routing algorithm does not make any retry attempts on failed transmissions. It merely reports the error condition for measurements. This will result in somewhat pessimistic measurements because some communication failures could be overcome by retransmission.

3.3 The Node Entity

• The number of hellos, rreqs, rreps sent or received
• The time spent in sending or receiving data or ack packets
• The time spent in sending or receiving routing packets
• The number of data packets sent by the original source
• The number of data packets received by the final destination
• The number of ack packets sent by the destination
• The number of ack packets received by the original source of data
• The number of failures to forward data or ack packets due to missing routing information
• The number of times a source times out while waiting for an ack signal from the destination after sending a data packet.

3.4 The Channel

Although currently very primitive, the idea of having a channel entity in the simulation environment is very useful for further development. It is in this entity where various channel impairements such as bursty noise profiles or multipath fading can be modeled. For a first implementation, however, it was decided not to include these factors until the basic routing algorithm becomes stable.

3.5 The LocationManager

Every node stays stationary for a random period of time between a lower limit, MINPAUSE, and an upper limit, MAXPAUSE. It then will choose an arbitrary direction and move in a straight line with a set speed for a set time. The speed is again chosen randomly but lying within the range MINVEL and MAXVEL and the motion time between MINMOVE and MAXMOVE. This way the nodes appear to exhibit a random walk pattern, pausing and moving alternately. By changing the pausing and moving time limits, different average network mobilities can be simulated. The average network mobility is defined as:

The idea is to study the performance of the AODV routing algorithm and see its behavior as the average mobility is increased.

3.6 The CommunicationManager

As the case with the mobility, the measured average communication load is directly related to the controlling parameters. The simulator will calculate average times for engaging in data communications and routing communications measured at each node as a percentage of the total time. This will enable measuring the performance of the AODV routing algorithm as the network traffic is varied.

4. Preliminary Results

• Number of Nodes: 16
• Total Area available: Square 9x9 m
• Minimum velocity of a moving node: 1 m/s
• Maximum velocity of a moving node: 2 m/s
• Total Simulation Time: 1000 msec

The following observations were made:

• Although the average number of routing messages is greater than the number of data packets, the actual time spent on routing packets is much less than the time spent sending or receiving data. This is because the average length of the data packets is an order of magnitude larger than that of routing messages. Although not shown in the figures, the above tests recorded that on the average, every node spent 36 % of the time sending or receiving data and only 1.6 % of the time sending or receiving routing messages.

• Examining Figure 5, the following anomaly was observed:

  When a node receives a route request for which it has the answer in its routing table, it replies with the route rather than forwarding it to the destination (so as to cut on the unnecessary propagation of further rreqs). Now the route reply is unicast back to the source and the source can in turn start to communicate with the destination. The problem here is that the reverse path is only set up to the point of the node that replied and may not be set up all the way to the destination. This manifests itself when the destination receives the packet, it sometimes cannot send an ack back to the source when it has no routing info for it. (Notice that the number of ACKs sent is less than the number of data packets received even with a fixed topology and no mobility where everything should be ideal ). A possible solution is to introduce a new type of routing message: This will get unicast to the destination from the node that replied. All nodes along the path will then update their routing info to the source.

5. Future Work

1. Enhancements of the current implementation of the AODV algorithm: As mentioned earlier, the current version of the simulation implements only the basic AODV algorithm and even that cannot be considered complete yet. Besides completing the basic algorithm, various advanced features as described in section 2 can be implemented and tested.
2. Enhancements to the simulation environment: Currently the simulator runs in batch mode. The user sets the desired parameters to control the environment, runs the simulation and examines the output at the end. A more interactive approach would be desirable, where one can single step through the simulation time and interactively set parameters and query node information. Furthermore, the current means to visualize the ad-hoc network is through netviz software. Although powerful and easy to use, it remains an output-only tool. A more elaborate graphical user interface is sought where the user can for example click on a node and query its routing table.
3. Restructuring the implementation of AODV so as to be able to run the same code on the simulator as well as on real wireless networks: Obviously, the role of the simulation ends after being satisfied with the performance of the AODV algorithm and the next step is to apply the code on actual hardware. By being able to use the same code, many potential problems of porting and code maintenance can be avoided.

Acknowledgements

References

1. Charles E. Perkins. Ad-hoc On Demand Distance Vector Routing (unpublished work).
2. Charles E. Perkins & Pravin Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, ACM Sigcomm , pp. 234-244, August 1994.
3. David Johnson & David Maltz. Dynamic Source Routing in Ad-Hoc Wireless Networks,Mobile Computing, Tomasz Imelinsky, editor. Kluwer Academic Publishers, 1996. To be published.
4. R. Bagrodia et al. A Hierarchical Simulation Environment for Mobile Wireless Networks,Proceedings of the 1995 Winter Simulation Conference , December 1995.
5. Maisie Programming Language.
6. NetViz : A network visualization tool from RoofTop Communications.