Routing Protocol Simulation With NS2

Network simulation is a method of investigation in network technology. In the process of investigating a new technology, due to various reasons, it is costly and unrealistic to physically test a network system. In such situation, simulation becomes one of the best available solutions in testing, evaluation and validation. Network simulation has the features of small cycle and low cost, and it is easier for researchers to use other’s research, in order to concentrate on the particular part and no need to waste too much time on other part of the system.

NS2 is a simulation platform that is developed in free open source for network technologies. Researchers can easily use it for the development of network technology. Until today, NS2 contains rich modules that are almost related to all aspects of network technology.

Wireless network communications obtained a rapid development in recent years. Ad hoc networks do not need the support of cable infrastructure; the communication is achieved by free mobile network hosts. The emergence of ad hoc network has promoted the achievement of the process of free communication at any environment, at the same time it has also provided an effective communication solution of military, disaster relief and temporary communications.

Considering the ad hoc network is constantly moving, and the network topology is changing, therefore the traditional internet routing protocols (e.g. RIP, OSPF) are not be able to adapt into the actual need of ad hot networks. Therefore there are many specialised routing protocols are designed for the ad hoc network, the aim of this paper is to compare, analyse and evaluate the most popular routing protocols for ad hoc networks by running the simulation test with NS2.

Introduction

“A mobile ad hoc network (MANET), sometimes called a mobile mesh network, is a self-configuring network of mobile devices connected by wireless links.”

Along with the desire of get rid of the wired network constraints and be able to communicate at any time and any place, wireless network communications obtained a rapid development in recent years. Mobile communications can be achieved by portable computers with wireless interface equipped and PDAs. Most current mobile communications require a wired infrastructure, e.g. base station. To be able to communicate without fix infrastructure, a new network technology – Ad Hoc network technology arises at the historic moment. Ad hoc networks do not need the support of cable infrastructure; the communication is achieved by free mobile network hosts. The emergence of ad hoc network has promoted the achievement of the process of free communication at any environment, at the same time it has also provided an effective communication solution of military, disaster relief and temporary communications.

Each device in a MANET is free to move independently in any direction, and will therefore change its links to other devices frequently. Each must forward traffic unrelated to its own use, and therefore be a router. The primary challenge in building a MANET is equipping each device to continuously maintain the information required to properly route traffic.

Such networks may operate by themselves or may be connected to the larger Internet.

Ad-hoc network was originally used in the military field. With the developments of wireless networks, it has begun the development in the civilian fields. A mobile ad-hoc network does not need any infrastructures, any node can quickly and automatically form the network, and each node can move freely and is able to join or leave the network at any time. The characteristics and advantages of fast deployment, invulnerability makes mobile ad-hoc becoming more and more widely used in either military or civilian fields.

In recent years, as the emerging wireless communication network, Ad-hoc is gradually attracting more attention of the industry and become a research hotspot. Ad-hoc networking supports flexible and convenient communication without the support of infrastructure, this technique broadens the fields of mobile communications and has a bright future.

Ad hoc network can be regarded as the cross of mobile communication and computer network. In ad hoc networks, computer network packet exchange mechanism is used rather than circuit switching mechanism. Communication hosts are usually portable computer, personal digital assistants (PDA) and other mobile devices. Ad Hoc network is different from mobile IP network in the current Internet environment. In mobile IP networks, mobile hosts can link and access the network through fixed wired network, wireless link and dial up link, and in ad hoc network, these is only a wireless link connection. In mobile IP networks, the communication need to be supported by adjacent base stations and still using the traditional internet routing protocol, however, ad hoc networks do not have the support of these facilities. In addition, a mobile host in the mobile IP network is only an ordinary end device which does not have routing function. When the mobile host moves from one zone to another does not change the network topology, and in Ad Hoc networks the movement of mobile hosts would lead to topology change.

The thesis is to research on the Ad-hoc networking mode and its network layer through simulation with NS2, mainly focused on the comparison and analysis of the popular ad-hoc routing protocols. The aim of this article is to research and develop on the key technology of self-configuring network – routing protocols, based on ad-hoc network structure.

Wireless Ad-Hoc network – Structure and Characteristics

Ad Hoc wireless network has its own particularity, in the formation of actual use of the working network, the application size, scalability and the reliability and real-time requirements must be taken full account.

In addition, due to the unique structure of the ad hoc network, the characteristics of ad hoc network should be fully considered when design and build the network, which will help us to design a routing protocol that is suitable for particular network structure in order to maximise the performance across the network.

Ad-hoc network Structure

Ad Hoc wireless network topology can be divided into two kinds: Flat structure and hierarchical structure, in flat network structure, all network nodes have equal status.

However, in the hierarchical structure of the Ad Hoc wireless network topology, the whole network is composed of clusters for the subnet, each cluster consists of a cluster head and multiple cluster members, the cluster heads forms a higher level network. Each cluster head and cluster members are dynamic and automatic networking. The hierarchy is based on different hardware configurations, and hierarchical structure can be divided into single-band and multi-band classification structure. Single band hierarchy use single frequency in communication, all nodes use the same frequency. But in multi-band hierarchy, if there are two networks in different levels exist, the lower level network has a smaller communication range and higher level network has a larger communication range, cluster members use the same frequency to communicate, cluster head nodes uses one frequency to communicate with cluster members and another frequency to maintain the communication with cluster heads.

There are advantages and disadvantages exist in either flat or hierarchical network structures: the structure of flat structure network is simple, each node has an equal status, there are multiple paths exist in communication of the source node and destination node, therefore no network bottlenecks, and the network is relatively safe. However, the biggest drawback is the limited network size, when the network scale expanding, routing maintenance overhead exponential growth and consume the limited bandwidth; Hierarchical network structure is not limited by the scale of network, the scalability is good, and because of clustering, routing overhead is relatively smaller, although there is the need of complex cluster head selection algorithm in hierarchical structure, but because of hierarchical network structure with high system throughput, node localisation is simple, therefore ad hoc network is now increasingly showing grading trend, many network routing algorithms proposed are based on the hierarchical network structure model.

Ad-Hoc network Characteristics

Wireless ad hoc network is a combination of mobile communications and computer networks, each node in the network have both router and host functions. The characteristics of ad hoc networks in mainly in the following areas:

Dynamically changing network topologies:

Ad Hoc networks have no fixed infrastructure and central management communications equipment, network nodes can randomly move to any direction in any speed rate, coupled with the power change of wireless transmitter device, the environment impact and the signal mutual interference between each other, which all will result in dynamic changes of the network topology.

Limited resources:

the working energy provided to the mobile hosts in Ad Hoc networks are limited, and the mobile host with more energy loss, will reduce the Ad Hoc network functions; on the other hand, the network itself provides limited bandwidth and signal conflicts and Interference, which results the mobile host with limited available bandwidth which is normally far less than the theoretical maximum bandwidth.

Multi-hop communication:

if two network nodes are not in the same network coverage due to the limited resources available, multi-hop may be used in Ad Hoc network communication, in order to achieve the communication between the source host and destination host which are not in the same network coverage.

Limited physical security:

the communication of Ad Hoc network nodes are through the wireless channel, the information transmitted is very vulnerable, and eavesdropping, retransmission, falsify or forgery attack can be achieved easily, If routing protocol once suffered the malicious attacks, the whole self-organizing networks will not work properly.

These features of the Ad Hoc network have made a special request in the routing algorithm design. A reasonable routing algorithm must take the factors of limited network resources, dynamic network topology changes and improve the network throughput into account.

Ad-Hoc Wireless network routing protocols

The key issue in ad hoc network design is to develop a routing protocol that is able to provide high quality and high efficient communication between two nodes. The mobility characteristic in the network makes the network topology constantly changing, the traditional internet based routing protocol is unable to adapt to these characteristics therefore the routing protocol that is specialised for ad hoc networks is needed, According to earlier on the Ad Hoc network architecture and features described, the design of the routing protocol must meet the following conditions:

The need of rapid response capability for dynamic network topology, and try to avoid routing loops from occurring, and provide simple and convenient network node localise method.

Must be efficiently use of the limited bandwidth resources, and try to compress unnecessary overhead.

Limit the number of intermediate transfer during the implementation of multi-hop, generally not more than 3 times.

Must minimise the launch time and amount of launch data, in order to save limited working energy.

In possible conditions, make the design of routing protocol with securities to reduce the possibility of being attacked.

Routing Protocols

According to the specific characteristics of ad hoc wireless network routing protocols, in recent years, there are a variety of ad hoc network routing protocols have been proposed. IETF’s MANET working group is currently focused on research Ad Hoc network routing protocols, and protocols many protocol drafts, such as DSR, AODV, ZRP etc. in addition, the professional researchers also published a extensively amount of articles related to Ad hoc network routing protocols and proposed many network routing protocols for the ad hoc networks, such as DSDV, WRP etc. According to the routing trigger principle, the current routing protocols can be divided into three types: Proactive Routing protocol, Reactive routing protocol and Hybrid routing protocols.

Proactive Routing protocol

Proactive routing protocol is also known as Table-driven routing protocol, each node maintains a routing table that contains the routing information to reach the other node, and updates the routing table constantly according the network topology changes, and therefore the routing table can accurately reflect the topology structure of the network. Once the source code needs to send messages, the route to the destination node can be immediately obtained. This type of routing protocol is usually modified from the existing wired network routing protocol to adapt to the wireless ad hoc network requirements, such as the Destination-Sequenced Distance Vector protocol, which is modified from the Routing Information Protocol (RIP). Therefore, this type of routing protocol has a small delay, but requires a lot of control message, the overhead is large. Commonly used proactive routing protocols include DSDV, HSR, GSR, WRP etc.

Destination-Sequenced Distance Vector (DSDV)

DSDV avoids the generation of routing loops by set serial number for each route, using time-driven and event-driven technology to control the transfer of routing table, i.e. a routing table is kept in each moving node locally, it contains valid points, routing hops and destination routing serial number etc. destination routing serial number is used to distinguish old and new route to avoid routing loops.

Each node periodically sends the local routing table to the neighbour nodes, or when the routing table changes, the information will also be passed to neighbouring nodes, when there is no moving nodes, use a larger packet with longer interval to update the route. When the neighbouring node receives the information contains modified routing table, it will first compare the serial number of destination node, the routing with larger serial number will be used and the one with smaller serial number will be eliminated, and if the serial number are the same, the best optimised route (e.g. shortest path) will be used.

Each node must periodically exchange the routing information with adjacent nodes, the routing information update is also can be triggered by the changes in routing table. There are two ways to update the routing table, Full dump, i.e. the topology update message will include the entire routing table, which is mainly applied to the case of fast changing network. Another way is Incremental update, in which update message contains only the changed part in routing, such way is usually used in a network with slower changes.

Hierarchical State Routing (HSR)

HSR is a routing protocol that is used in hierarchical network, nodes at a higher level saves all the location information of its peers, logical sequence address is assigned along from the root node at the highest level to the leaf node at the lowest level, node address can be used by sequence address.

Global State Routing (GSR)

GSR protocol works similar with the DSDV mechanism, it uses link-state routing algorithm, but avoids the flooding of routing packets, which includes an adjacent node table, network topology table, next hop routing table and the distance table.

Wireless Routing Protocol (WRP)

WRP is a distance-vector routing protocol, each node maintains a distance table, routing table, link overhead table and packet retransmission table, through the Short Path Spanning Tree (SST) of the neighbouring node to generate its own SST, and then transmit updates. When there is no any change in the network routing, the receiver node must return an idle message to show the connection, otherwise modify the distance table to look for better route. The feature of this algorithm is that when any changes of the neighbouring node is detected, and then checks the sturdiness of all adjacent nodes in order to eliminate the loop, has a faster convergence.

Reactive Routing Protocol

Reactive Routing protocol is also known as on-demand routing protocol, it finds the route only when needed. Nodes do not need to maintain routing information constantly, it will initiate route look up only when the packet is need to be sent. Compare with proactive routing protocols, the overhead of reactive routing protocol is smaller, but the packet transmission delay is larger, which means it is not suitable for real time applications. Commonly used reactive routing protocols include AODV, DSR, TORA and so on.

2.2.2 Dynamic Source Routing (DSR)

“DSR is designed to restrict the bandwidth consumed by control packets in ad hoc wireless networks by eliminating the periodic table-update messages required in table-driven approach.”

DSR is composed of two main mechanisms – Route Discovery and Route Maintenance. The Route Discovery mechanism is used when the source node needs to send a packet to the destination node but does not know the route.

When the source node is using a source route to reach the destination node, source node uses the route maintenance mechanism to identify the route that cannot be used due to the topology changes.

In DSR, route discovery and route maintenance mechanisms are fully on-demand operation, DSR does not require any periodic routing broadcast packets and link state detection packets.

2.2.3 Temporally Ordered Routing Algorithm (TORA)

TORA is an adaptive distributed routing algorithm based on link reversal method, which is mainly used for high-speed dynamic multi-hop wireless network. As a source initiated on-demand routing protocol, it is able to find multi-paths from the source to the destination node. The main characteristics of TORA are, when topology changes, the control message transmission in local area of topology changes only. Therefore, the node only needs to maintain the information of adjacent nodes. The protocol consists of three parts: route generation, route maintenance and route deletion. In the initialisation stage, the transmission sequence number of the destination node is set to 0. The QRY packet which contains the destination node ID broadcast by the source end and a node with a transmission sequence number that is not 0 responses to the UDP packet. The node that receives UDP packet has the sequence number higher than the source node by 1, and the node with higher sequence number is set as the upstream node. Through this method, a Directed Acyclic Graph (DAG) from the source to the destination node can be created. When nodes move, routes need to be rebuilt. In the route deletion phase, TORA removes the invalid route by broadcasting a CLR. There is one problem that exists with TORA, which is when multiple nodes proceeds to route selection and deletion, routing oscillation will be produced.

2.2.4 Ad-hoc On-Demand Distance Vector Routing (AODV)

AODV is an improvement to the DSDV algorithm, but the difference with DSDV is that it is a Reactive routing protocol. In order to find the route leading to the destination node, the source end will broadcast a routing request packet, and adjacent in turn broadcast the packet to the surrounding nodes until the packet was sent to the destination node, or, to the intermediate node which has the routing information to the destination node. A node will discard duplicated request packet received, the serial number of routing request packet is to prevent routing loops, and is able to determine whether the intermediate node has responses to the corresponding routing requests. When a node forwards a route request packet, it will mark the ID of its upstream node into the routing table, in order to build a reverse route from the destination node to the source node. When the source end moves, it will re-initiate route discovery algorithm; if the intermediate nodes move, then the adjacent node will find the link failure and send the link failure message to its upstream node and spread the message all the way to the source node, afterwards the source node re-launches the route discovery process according to the circumstances.

The achievement of AODV is a combination of DSR and DSDV protocols. It has the features of route discovery and route maintenance in DSR, and at the same time use by-hop routing, sequence number and Beacon messages that adopted in DSDV.

Hybrid Routing Protocol

In wireless ad hoc networks, neither proactive nor reactive routing protocols alone can solve the routing problem completely, therefore hybrid routing protocols which combines the advantage of both proactive and reactive protocols have been proposed by the researchers, such as the Zone Routing Protocol (ZRP). ZRP is a combination of proactive and reactive routing protocols, all nodes within the network to themselves as the centre of a virtual zone, the number of nodes in the area is related to the radius set of the zone, and the areas overlap, this is the difference with clustering routing. It uses proactive routing algorithm within the zone, the centre node uses Intrazone Routing protocol to maintain in the zone.

Literature Review

Network Simulation Tool

The platform that will be used in simulation is Windows XP Professional + Cygwin + NS2.

NS2 is a simulation platform that is developed in free open source for network technologies. Researchers can easily use it for the development of network technology. Until today, NS2 contains rich modules that are almost related to all aspects of network technology. Since the release 2.26, NS2 has stopped support with Windows platforms, therefore to get the latest NS2 running on the Windows XP, Cygwin is needed. Cygwin is an UNIX emulator on Windows platform.

Implementation

Configure simulation platform

Normally, NS2 simulation can be divided into the following steps:

1. Compose necessary components: i.e. add or remove new components

2. Testing: test whether the component composed is validated. When the component in the library satisfies the simulation needs (e.g. simulation process based on existing protocols in the library),then the simulation starts from the third step.

3. Compose Otcl script file: configure the topology structure of the simulating network, and identify the basic link features, protocols that have been used by moving nodes, and number of nodes etc, and binding the terminal device protocol, setting the scene and traffic load of simulation (TCP stream or CBR stream), setting simulation start and end time etc, and set trace objects of the script file, trace file is the file that records all of the events of simulation process, and also can set the nam object at the same time, nam is the tool to demonstrate the network running animation.

4. Use NS command to execute script file: once executed, *.tr file will be generated in the same directory of the script file, to record the simulation results. if nam object is set in the script file, *.nam file will be generated in the same directory.

5. Analyse trace file: due to the large size of trace file, we will need to compose gawk program to process the data after simulation (calculate packet delivery date, routing overload, and throughput etc), then use the drawing tools to produce the graph for direct analysis.

In NS2 the classic routing protocols such as DSDV, DSR, TAORA and AODV are already integrated; the source code of routing protocols is located in C:cygwinhomeAdministratorns-allinone-2.34ns-2.34, show in figure 1.1

Take AODV as an example (fig. 1.2), within the ADOV folder, aodv.cc and aodv.h are the most important files, they defines the main functional features. Under general circumstances, we do not need to modify the source code of the protocols.

Fig.1.2 AODV Routing Protocol

Simulation scripting

According to the simulation model designed, each routing protocol (DSDV, DSR, AODV, and TORA) will be compared in small (20 nodes) and medium (50 nodes) ad hoc wireless network. The corresponding scripts composed are: dsdv.tcl, dsr.tcl, aodv.tcl and tora.tcl (see appendix).

Taking aodv.tcl as an example, the coding is show in fig.3.2.1

Partial scripts in aodv.tcl

Some script explanation of most important codes in aodv.tcl

set val(ifq)Queue/DropTail/PriQueue;

#Interface queue

set val(nn)50;

#Number of nodes in simulation scenario

set val(rp)AODV;

#Routing protocol to be simulated

set val(stop)300

#Simulation time length

set val(x)500;

#Length of scene

set val(y)500;

#Width of scene

set val(tr) out50.tr

#Output trace file

set val(nam) out50.nam

#Output nam file

set opt(cp) “cbr50”

#Stream file

set opt(sc) “scen50”

#Scene file

In addition, write the following statement in script head to generate a simulation ns_ object:

set ns_[new Simulator]

Tracking the file object is used to specify the Trace file (with .tr extension) in recording of the simulation data. NS2 supports record application layer, routing layer, MAC layer and node movement those four types of data in difference layers. The data that needs to be recorded can be specified in settings in the simulation process. The data in of each layer that trace object specified are all recorded in the trace file, labels are added to distinguish them. In addition, NS2 also supports NAM tool simulation process visualisation, such function needs to generate the NAM trace file object to specify the trace file of records of simulation data. The following statements are used to generate those two trace file object described.

#Generate trace file:

$ns_use-newtrace

set tracefd[open out50.tr w];

$ns_trace-all$tracefd

#Generate NAM trace file object:

set namtracefd[open out50.nam w]

$ns_namtrace-all-wireless$namtracefd$val(x)$val(y)

Data Stream Generation Tool

Data stream generation tool cbrgen is used to generate traffic loads, which can generate the TCP steam and CBR steam. Cbrgen.tcl file (see appendix) can be used as following:

Codes are defined as following:

-type

#TCP stream or CBR stream

-nn

#Number of nodes

-seed

#Specify number of random seeds

-mc

#Maximum connection of each node

-rate

#Overload of each stream connection

The format is used as following:

ns cbrgen.tcl [-type cbr|tcp] [-nn nodes] [-seed seed] [-mc connections] [-rate rate]

Movement Scene

./setdest is used to randomly generate the nodes movement scene needed form wireless network, used as following (2 versions):

./setdest -v <1> -n -p -M -t

time> -x -y

or

./setdest -v <2> -n -s -m -M -t

-P -p -x -y

Which “speed” type set to uniform/normal¼Œ”pause type” set to constant/uniform.

NAM animation

The NAM function is used to run the animation of specific trace output format, the output file can be based on real or simulated environment. For example, the trace file that is from the output of NS simulator.

The commands to control to control NAM animation in NS2 as following: nam out.nam

1. Node

$node color [color]

Setting the colour of node

$node shape [shape]

Setting shape of node

$node label [label]

Setting name of node

$node label-color [lcolor]

Setting display colour of node name

$node label-at [ldirection]

Setting display location of node name

$node add-mark [name] [color] [shape]

Add annotation

$node delete-mark [name]

Delete annotation

2. Link and Queue

$ns duplex-link

attribute: orient、color、queuePos、label

3.Agent

Use the following commands to make the agent you wish to display appears as AgentName in the box.

$ns add-agent-trace

$Agent AgentName

The parameters of movement scene and node flow are in the tables shown below:

Parameter of node movement scene:

Parameter

Number of nodes

Moving range

Resting time

Simulation time

Values set

20, 50

500 x 500 m

1 s

300 s

Parameter of node movement scene:

Parameter

Maximum moving speed

Packet size

Node communication distance

Type of service

Values set

5, 10, 15, 10, 25, 30-50

512 byte

250 m

CBR

Trace file analysis

Performance parameter analysis model

The indicator to measure the performance of ad hoc network routing protocol is commonly including qualitative indicator and quantitative indicator. Qualitative indicator describes the overall performance of a particular aspect of the network, such as the security, distribution operation, provide loop free route and whether to support single channel etc. and quantitative indicators can describe the performance of a certain aspect of the network in more details. The quantitative indicator of packet delivery ratio, average end to end delay and throughput etc are often used to measure the performance of network routing protocols.

Find Out How UKEssays.com Can Help You!

Our academic experts are ready and waiting to assist with any writing project you may have. From simple essay plans, through to full dissertations, you can guarantee we have a service perfectly matched to your needs.

View our services

a. Packet delivery ratio: is a ratio of the number of packet sent from the source node and the number of packet that have been received by destination node in the application layer, which not only describes the loss rate observed in the application layer, but also reflect the maximum throughput supported by the network. It is the indicator of routing protocol completeness and correctness.

End to end average delay:

it can be calculated with the following equation, which N represent the packets successfully delivered, rt represents the time that packet reached the destination node, and st represent packet sending time.

Routing overhead:

Routing overhead is the total number of control packets of all routes, in a multi-hop routing each hop transmission is equivalent to one packet transmission. Routing overhead can be used to compare the scalability, the ability to adapt to network congestion and the efficiency of different routing protocols. It can be calculated with the following formula:

Routing overhead = The Total number of routing control packets

Gawk code

The output file out.tr generated in simulation analysis will be filtered by selecting all of the packets in Agent layer, calculate all the number of data packets sent by this layer and the number of data packets that has been successfully received, and then divide the number

 

Share this: Facebook Twitter Reddit LinkedIn WhatsApp