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 <nodes> -p <pause time> -M <max speed> -t <simulation

time> -x <max X> -y <max Y>

or

./setdest -v <2> -n <nodes> -s <speed type> -m <min speed> -M <max speed> -t

<simulation time> -P <pause type> -p <pause time> -x <max X> -y <max 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> <value>

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.

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 of packets received by the number of packet sent, in order to get the packet delivery rate. Use awk command could get the data of packet delivery rate, end to end average delay, routing overhead, the gawk script is shown below:

BEGIN {sendpacket = 0;

recvpacket = 0;

}

$0 ~/^s.* AGT/ {sendpacket ++ ; #Calculate the number of packets sent

}

$0 ~/^r.* AGT/ {recvpacket ++ ; #Calculate the number of packets received

}

END {printf “cbr send:%d recv:%d, getRatio:%.4f n”, sendpacket,

recvpacket,(recvpacket/sendpacket);

}

awk -f avdelay.awk out.tr > avdelay

awk -f getratio.awk out.tr > getratio

awk -f routeload.awk out.tr > routeload

Use of Gnuplot:

In obtaining the desired data, we can use the drawing tool Gnuplot to plot the quantitative data curve.

Through loading files to start graph plot, run load “gnuplot.plt.

gnuplot>load “gnuplot.plt

Obtain the packet delivery rate and analysis chart of 50 nodes. We should modify the coordinates, scale size and data file name in plotting, and highlight the key points.

Gnuplot.plt code is shown below:

unset xtics # keep all other things simple

set origin 0,0

set multiplot

set title “Paeket Delivery Fraetion”

set xlabel “speed(m/s)”

set ylabel “Paeket Delivery Fraetion(%)”

set xtics 5.0

set ytics 1000.0

set xrange[0:50]

set yrange[0:7000] #the two axes scale range are equal

set key top left

set key box

#===================================================

set size 0.5,0.5

set origin 0,0.5

plot “50MR.txt” using 1:2 title “aodv” w lp lt 3 lw 2 pt 3 ps 2

#The first chart occupies the top left quarter of the screen.

set size 0.5,0.5

set origin 0,0

plot “50MR.txt” using 1:3 title “dsdv” w lp lt 4 lw 2 pt 4 ps 2

# The second chart occupies the bottom left quarter of the screen

set size 0.5,0.5

set origin 0.5,0.5

plot “50MR.txt” using 1:4 title “dsr ” w lp lt 5 lw 2 pt 5 ps 2

# The third chart occupies the top right quarter of the screen

set size 0.5,0.5

set origin 0.5,0

plot “50MR.txt” using 1:5 title “tora” w lp lt 6 lw 2 pt 6 ps 2

# The forth chart occupies the bottom right quarter of the screen

#=====================================================

unset multiplot

Simulation results comparison and analysis

Delivery rate comparison of each protocol

Fig. 1.1.1 and fig 1.1.2 are showing the comparison of packet delivery rate for each protocol in case of speed changing in a small (20 nodes) and medium (50 nodes) scaled ad hoc network separately. The entire simulation lasts for 300 seconds. The horizontal axis is the node mobility speed (m/s), and the vertical axis is the value of packet delivery rate.

Fig.1.1.1: Packet Delivery Rate of each routing protocol in a small ad hoc network (20 nodes)

Analysis of above charts

In most cases, due to the frequent move of nodes, the routing table in the proactive routing protocol mechanism DSDV, will often become invalid therefore unable to identify the available routes which leads packet loss.

As the speed increases, the network topology changes more and more violent, there must be a great increase in number of route update packets in the wireless channels of the network, especially in routing protocol DSDV, as the table content is need to be updated every time the topology changes.

The mechanism of reactive routing protocols (AODV, DSR, and TORA) is better in inhibiting the possible circumstances of routing table entries failure. The route established only when a packet is needed to be sent. Therefore the sensitivity of reactive routing protocols to the network topology changes is much lower than proactive routing protocols.

Thus, in wireless ad hoc network, the packet delivery rate in proactive routing protocol (DSDV) is lower than reactive routing protocols (AODV, DSR and TORA). This result is agrees well with the previous routing protocol analysis.

In addition, we also found in each protocol that in the small ad hoc network (20 nodes), the packet delivery rate gets higher when the nodes are moving at a higher speed; but in the medium ad hoc network (50 nodes), the packet delivery rate is lower when the node movement speed gets higher.

The reason for this outcome may be: the greater network load leads more node energy consumption; the energy runs out before the packets arrived, which led to a lot of packet loss, therefore result a significant reduction in successfully received number of packets.

Analysis of Average end to end delay

Graphs fig.1.2.1 and fig 1.2.2 are showing the comparison of average end-to-end delay of each protocol in case of speed changing, for small (20 nodes) and medium (50 nodes) wireless ad hoc networks separately. The entire process of each protocol lasts for 300 seconds.

The horizontal axis represents the moving speed of nodes (in m/s), and vertical axis is the average end-to-end delay (in ms).

Fig. 1.2.1

Fig.1.2.2 Average end to end delay of each routing protocol in a medium ad hoc network (50 nodes)

Analysis of end-to-end average delay graph for each routing protocol

We have found that in the small ad hoc network (20 nodes), proactive routing protocol (DSDV) has the smallest end-to-end average delay, and the reactive routing protocol (AODV, DSR and TORA) has a bigger delay. The reason of this is that when the proactive routing protocol (DSDV) needs to send a packet, it gets the route directly from searching the routing table, therefore gets a smaller delay; in addition, this maybe related to the network topology and network scene as well.

DSR, AODV and TORA are reactive routing protocols, which look up the routes only when a packet is needed to be sent, therefore with a larger delay.

At the same time, we can see from the graph of medium ad hoc network (50 nodes), at a higher speed, proactive routing protocol (DSDV) end-to-end average delay increases and gets even higher than reactive routing protocol (TORA). Therefore the delay of proactive routing protocol (DSDV) increases along with the increase of network overload and speed of node movement.

In addition, the movement speed increase led frequent topology changes, which make the end-to-end average delay of each routing protocol relatively increase.

Routing overhead comparison of each routing protocol

In addition, the movement speed increase led frequent topology changes, which make the end-to-end average delay of each routing protocol relatively increase.

Graphs fig.1.3.1 and fig 1.3.2 are showing the comparison of routing overhead of each protocol in case of speed changing, for small (20 nodes) and medium (50 nodes) wireless ad hoc networks separately. The entire process of each protocol lasts for 300 seconds. In the graph generated, the horizontal axis represents the speed of node movement (in m/s), and vertical axis represents the routing overhead (unit: number of routing packet)

Fig.1.3.1: routing overhead comparison of each protocol in small ad hoc network (20 nodes).

Fig. 1.3.2: routing overhead comparison of each protocol in medium ad hoc network (50 nodes).

DSDV is a proactive routing protocol, in the medium sized ad hoc network (50 nodes), nodes periodically exchange routing information, and basically its overhead is not much influenced by the node movement. Under the same movement speed, reactive routing protocols (DSR, AODV and TORA) has a higher routing overhead than DSDV, TORA has the biggest overhead among them. With the speed increase, the overhead of on-demand routing protocols are getting higher and higher, but in contrast, the overhead of proactive routing protocol DSDV is on the decline, the main reason behind is that the process of routing request in reactive protocols corresponds to one route needed, and gets only one route each time, but the routing information updates in proactive protocols broadcasts all the paths, therefore multiple routes can be found in one update; therefore reactive routing protocol has a larger overhead, and at the same time the increase of node movement speed also increases the number of route discovery process in reactive routing protocol, which leads the rise of routing overhead.

But in DSDV protocol, the movement speed increase shows its advantage, the routing overhead declines. This is because that TORA, DSR and AODV are all on-demand routing protocols, their costs will decrease with the decrease of node movement, but increases with the increase of network load.

The overhead of routing protocol TORA consists of two parts, one part is constant overhead that is not related to the moving speed of nodes, and the other part is variable overhead that is associated with the movement of nodes. The first part is mainly according to the Directed Acrylic Graph of structure, once Directed acrylic graph established, there may be a multiple route available from the source node to the destination node. Therefore the overhead is mainly on the directed acrylic graph maintenance, this mechanism requires the node send at least one Hello packet in each signal cycle.

And the second part is the routing packets for TORA to generate and maintain the routes, and the retransmission and confirmation packets of MEP to ensure the reliable sequence transmission.

Therefore TORA has a relatively larger overhead, the routing overhead increases significantly in the beginning stage with the node speed increase.

DSR uses caching technology and mixed reception mode to listen to the routing request packets, and thus greatly reduces the routing overhead.

AODV has the similar characteristics with DSR, the performance is also similar, and both routing overhead is relatively low.

Conclusion

In the report, we have been tracking on the Ad hoc Network research, and use this as theoretical guidance for a systematic study. With the work requirements of this thesis, we have conducted a quantitative analysis for the four typical ad hoc routing protocols that have been proposed (DSDV, AODV, DSR, TORA).

Familiar with the basic NS2 simulation process and bring out the simulation with those for kinds of routing protocols.

Planning simulation steps and simulates in NS2 simulation software based on theoretical analysis, compared the performance of four existing ad hoc routing protocols. And made a comparison of quantitative analysis, and finally give a conclusion.

In the experiment, the numbers of nodes were set to 20 and 50 to represent the small and medium ad hoc network, and in the circumstances of speed changes in 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 (m/s), quantitatively analysed and compared the packet delivery rate, end-to-end average delay and routing overhead of each routing protocol through the simulation experiment. From the analysis of results, we can clearly see that because of the different protocol mechanisms, each protocol has the corresponding advantages and disadvantages in different performance indicators.

In general, reactive routing protocols (DSR, AODV, TORA) especially DSR and AODV have relatively higher packet delivery rate, while the packet delivery rate of DSDV is influenced by the network load. In terms of end-to-end delay, DSDV has the lowest average delay; and in terms of overhead, DSDV remains constant as it is not much affected by the network load.

Routing overhead of TORA increases with the increase of node number and node movement speed.

Due to the diversity of application environments of ad hoc wireless networks, resulting the pursuit of different requirements of performance. For example, the system’s survivability, concealment and confidentiality is more concerned in the military fields; but in wireless mobile conference systems, the end to end delay and packet delivery success rate is more stressed.

From the research and simulation results of above four types of routing protocols, we can see that different routing protocols has its own advantages and disadvantages, and thus adapt to different network environment.

However, the hope to have one routing algorithm to solve all the ad hoc network routing problems, and become the standard agreement of ad hoc routing protocol seems unrealistic at the current stage. The optimal routing algorithm should be selected based on the specific application environment. The Hybrid routing algorithm combines the advantages of both proactive and reactive routing protocols and its inherent flexibility, thus has a good application prospects.

¼ˆä¸‰¼‰è‡´è°¢

在论æ-‡çš„写作过程中¼Œé˜…读了不少æ-‡çŒ®¼Œå­¦ä¹ äº†ç»åŠ¨ Ad Hoc网络的一些理论¼Œå°¤

其是对现已提出的各çè·¯ç”±æŠ€æœ¯ã€‚由于本人属于跟踪学习阶段¼Œä¸»è¦å‚考了近年来的研

究成果。因此¼Œæ‰€åšçš„工作难免存在一些é-®é¢˜¼Œéœ€è¦åœ¨ä»¥åŽçš„工作和学习中ç»ç»­æ·±å…¥å­¦

习和研究¼Œè¿›ä¸€æ­¥æ”¹è¿›å’Œå®Œå-„。也敬请各位老师和同学提出宝贵意èã€‚

Section 4 – Simulation

Through NS2 simulation results, quantitatively analyse and compare the performance of various routing protocols.

Process of ad hoc simulation with NS2

Routing protocol comparison and performance analysis

Simulation configuration and parameters scripting

Process of simulation results files

Simulation model parameters and performance indicators

Simulation conditions

Calculation of Performance indicators

Simulation process in details

Generate traffic loads

TCL scripting animation simulation

Trace file analysis

Simulation results

– DSDV

– AODV

– DSR

– TORA

Gnuplot graph analysis

Comparison of packet delivery rate of each protocol

Average end to end delay comparison of each protocol

Comparison of overhead by speed increase

Section Six – Future research directions and work prospects

Section Seven – References

CWW.net

http://www.cww.net.cn/tech/html/2007/8/3/20078385592120_1.htm [Accessed in 17/05/2010]

Wikipedia

http://en.wikipedia.org/wiki/Mobile_ad_hoc_network [Accessed in 22/05/2010]

http://en.wikipedia.org/wiki/Destination-Sequenced_Distance_Vector_routing [Accessed in 20/05/2010]

http://en.wikipedia.org/wiki/Dynamic_Source_Routing [Accessed in 22/05/2010]

http://en.wikipedia.org/wiki/Ad_hoc_On-Demand_Distance_Vector_Routing [Accessed in 20/05/2010]

UNI.lu

http://wiki.uni.lu/secan-lab/Temporally-Ordered+Routing+Algorithm.html [Accessed in 20/05/2010]

Samuel Pierre, Michel Barbeau, Evangelos Kranakis [2003] Ad-hoc, mobile, and wireless networks: Second International Conference

George Aggelou [2005] Mobile ad hoc networks: from wireless LANs to 4Gnetworks‎

http://en.wikipedia.org/wiki/Ns_%28simulator%29