Performance Optimization of Wireless Infrastructure and Mesh Networks using ODSDV

Performance Optimization of Wireless Infrastructure and Mesh Networks using ODSDV

Manoj P. Munde, V. S. Jadhav

MAEERs Maharashtra Institute Of Technology, Kothrud, Pune, India.

Department of Electronics & Telecommunication, Pune University, Pune, India.

WMNs which are self-organizing and self-

Abstract – Wireless mesh networks (WMNs), which are consisted of mesh routers and mesh clients, have emerged as a key technology for next-generation wireless networking. In WMNs, routing mechanisms can significantly affect WMNs performance and optimal routing mechanisms are imperative to gain the potential advantages of WMNs. Wireless mesh networks (WMN) are a promising technology which provides wireless broadband connectivity to the Internet. In these networks, if any intermediate node fails to successfully transmit a packet to the next hop node after a certain number of retransmissions, the link layer reports a transmission problem to the network layer. Reactive routing protocols systematically consider this as a link breakage. In this paper novel optimization models are proposed for Wireless Mesh Networks (WMNs), where the objective is to minimize the network installation cost while providing full coverage to wireless mesh clients. Finally, the quality of the planned networks is evaluated under different conditions through detailed system level simulations. In this paper, the performance analysis is carried out on Ad-hoc On- demand Distance Vector (AODV), Destination Sequenced Distance Vector (DSDV) and Optimised Destination Sequenced Distance Vector (ODSDV) protocols using NS2 simulator. The delay, throughput, routing overhead and packet delivery ratio are the four common measures used for the comparison of the performance of above protocols. Our simulation results demonstrate that our statistical problem formulation could effectively incorporate the traffic demand uncertainty in routing optimization and its algorithm outperforms the algorithm which only considers the static traffic demand. Simulation results show substantial performance improvement compared to classical DSDV algorithm.

General Terms: Algorithm, Design, Performance,

Verification.

Keywords: ODSDV, WMNs, NS2, Performance evaluation.

1. INTRODUCTION

   WMNs, which can be considered as a mixture of the advantages of the WLAN and the mobile ad hoc network (MANET), have become a key technology used for wireless area network. In WMNs, the nodes automatically establish an ad hoc network and maintain the mesh connectivity. That is, WMNs are dynamically self-organized and self- configured. WMNs are comprised of two types of nodes: mesh routers and mesh clients.[1]

   configure, increases the coverage of wireless LAN

   standard (802.11n) to the wireless mesh MAN (802.11s) without significant additional infrastructure deployment. It also offers a good platform for promoting social partnerships in urban and rural areas. In the non-meshed WLANs, stations must associate with an access point (AP) to access the network and these stations depend on this access point with which they have come together to communicate. In a mesh APs can communicate with each other directly without going through an external network.[2] [3]

   Fig 1: Hierarchical architecture of WMNs.

   One of the main concerns for WMNs is the reduction of the overall network capacity due to interferences between adjacent nodes. To mitigate wireless interferences, several techniques can be used including multiple radios directional antennas and MIMO (multiple input multiple output). However, such physical layer solutions alone are not enough. To maximize the network utilization while preserving fairness requirements, efficient routing scheme is critical. To address this need, we propose a simple and effective routing optimization scheme via which the network utilization is maximized while providing fairness and bandwidth guarantees.

   Fig 2: Overview of Wireless Mesh Networks

   Routing is a fundamental characteristic of WMNs. The routing protocols strengths and weaknesses are reflected directly in the WMNs characteristics. Several advantages of WMNs over competing technologies are directly enabled by the routing protocol:

   Reliability: The routing protocol should be able to reroute fast around failed nodes and broken links; upon the failure of a gateway, it should be able to redistribute the orphaned clients among neighbouring gateways. For this property, fast reconfiguration and support of multiple gateways is essential.

   Scalability/efficiency: If the routing protocol has a high overhead, it will be impossible to scale the WMN to a large number of nodes.

   QoS: In addition to support from the medium access control (MAC) layer and the forwarding engine, selecting the best routes for different traffic classes is an essential ingredient for QoS support. Taxonomically, WMNs are a particular type of mobile ad hoc network (MANET). WMNs share the same multi-hop characteristics and mobility-related issues as MANETs. However, there are also significant differences between WMNs and general MANETs:

   Gateways (Mesh Routers): Most WMNs are designed to provide connectivity to a distribution system (usually connected to the Internet). Therefore, they have specialized nodes (the gateways) that provide connectivity to the distribution system.

   Traffic pattern: In WMNs, most of the traffic is expected to flow between the clients and the Internet (via the gateways).

   In general MANETs, the common assumption is that any node is equally likely to be the source or the destination of a traffic flow.

   Mobility: In most WMNs, nodes belong to two distinct categories: either stationary (e.g., on lamp poles, rooftops, etc.) or mobile, capable of roaming in the coverage area provided by the stationary nodes.[5] [6]

   Due to the above referred characteristics, WMNs attract lots of attention among worldwide researches. Given the characteristics of WMNs, we can conclude the similarities and differences between WMNs and MANET in Table 1.

   Comparison	WMNs	MANET
   Mobility	Mesh routers	User nodes as
   	as the main	the main
   	network part,	network part,
   	minimal	high mobility;
   	mobility; no	constraints of
   	constraints of	power
   	Power	consumption.
   	consumption.
   Network	Large number	Small number
   scalability	of nodes;	of nodes,
   	interconnection	usually several
   	of various	decade nodes;
   	kinds of	only one kind
   	wireless	of wireless
   	networks.	network
   Service type	Providing	Providing node
   .	access for	to multi-node
   	client nodes;	transmission;
   	wireless sub-	providing the
   	network access	functio of
   	to network	user access.

   Table No. 1: Comparison of WMNs with MANET.

2. Related work.

   Wireless ad-hoc network that do not require infrastructure to operate have been the subject of significant research. Very little attention has been given on pro-active (or table driven protocols). Generally a lot of emphasis is given on link state, ad-hoc & distance vector routing protocols which are operating on reactive routing protocols. Reactive or on demand protocols often results in short lived long routing loops, which disappear on link update. This results in very difficult for maintaining inter-nodal co-ordination mechanism.

   The optimization of pro-active routing protocols, e.g. DSDV is proposed to eliminate these short lived loops, lack of inter nodal co-ordination & to make the information available to maintain consistency of routing table. The solution for this is implemented in NS2.33 & the results are

   evaluated by the network optimization parameters comparative analysis like –

   1. Delay

   2. Packet loss

   3. Packets delivery ratio.

   4. Routing packets etc.

   The results are obtained by comparing the reactive protocol AODV with the pro-active protocols like DSDV and optimized DSDV.

   DSDV optimize Load Balancing Algorithm MS-Source

   MR-Destination MN-Mesh network iNode-Nodes MN==INode

   Collect Network _Discovery

   If (Ms->MR) then

   Find Possible Route Selection Send Data Transmission

   Else if(Update_neighbor_hop->true) then Update_neigbor_list Route_update() Route_discovery()

   End if

   If(Loadbalance->True) then Schedule.update()

   Throuhput performance optimize End If

   End if

3. PROTOCOL DESCRIPTION

   1. Destination Sequenced Distance Vector routing mechanism (DSDV):

      DSDV is a table-driven routing mechanism and is a typical proactive routing mechanism based on Bellman-Ford algorithm [9]. In DSDV, there are two types of updating routing tables which are time-driven update and event-driven update. For DSDV routing mechanism, each node maintains a routing table and periodically broadcasts update messages to adapt to the mobile network topology, which is called time-driven update. In other cases, if the trigger of the routing update is based on the network topology, it is called event-driven update. In DSDV, the employment of destination sequence number can avoid time-out routes, which can avoid the invalid routes. Each destination node creates and records an individual

      destination sequence number. When a node receives another route entry to the same destination, it will substitute the route entry with the newer received one only if the sequence number is newer than the previous one. If the sequence number is the same as the previous one, it depends on the parameter of hop count to choose the less hop count route. If both the sequence number and the hop count are equivalent, the table

      entry would remain the same without any change. The characteristics of DSDV are shown as follows:

      1. Low delay to obtain routes which is appropriate for real-time services. Low delay is owing to that DSDV routing mechanism could choose an invalid route after the previous route fails.

      2. The destination sequence number can not only identify the sequences of route entries, but also avoid route loops.

      3. Each node maintains a routing table, which records the destination address, hop count to the destination and a sequence number received from the destination node.[4]

      4. Two kinds of updating routing tables: time- driven and event-driven. The time-driven update means periodically broadcasting messages to update routing tables, which is convenient and easy for new-coming nodes to know the whole network topology and hence preferred in the highly changeable networks. The event-driven update indicates when the network topology changes, this event would trigger the update event, which can quickly correspond to the topology change and hence its more applicable for slowly changeable network.

      From the conclusions above, we can deduce that DSDV has low end-to-end delay, which is suitable for improving the QoS of real-time services. The two kinds of routing updates can make the routing table return to the stable state in a very short period after updates. Therefore, this paper chooses DSDV as the mechanism for mesh routers to achieve better performances. The previous work on performances evaluation of ad hoc routing showed that DSDV is more appropriate for minimal mobility networks and it has low end-to-end delay. Based on the characteristics of WMNs and DSDV described above, there is the potential to integrate DSDV into WMNs to achieve a better performance. After examining the feasibility of applying DSDV into WMNs, we combine the DSDV and Optimised DSDV for performance evaluation.[5] [6]

   2. Ad-hoc On-demand Distance Vector Routing Protocol (AODV):

      AODV is a reactive on-demand routing protocol which builds on both DSR and DSDV. AODV is an improvement on DSDV as it minimizes the number of required broadcasts by creating routes on demand basis. It is also an improvement on DSR as a node only needs to maintain routing information about the source and destination as well as next hop, thereby largely cuts back the traffic overhead. The process of route discovery is similar to DSR. Route request (RREQ) packets are broadcasted for

      route discovery while route reply (RREP) packets are used when active routes towards destination are found. HELLO messages are broadcasted periodically from each node to its neighbours, informing them about their existence.[4]

4. SIMULATION ENVIRONMENT.

   Currently the performance evaluation was carried out using simulation experiments. The simulation focuses on packets transmissions from Backbone mesh router (BMR) to mesh routers (MR). Mesh Clients (MCs) are generated at the start of the simulation within the simulation environment. Each MC is associated with the closest MR and each MR routes its packets to the Backbone MR. After the optimization of DSDV, the simulation results are compared with the AODV, DSDV and ODSDV.

   Parameter	Value
   Network Simulator	NS-2.34
   Channel	Channel/Wireless Channel
   Propagation Type	TwoRayGround
   Routing protocol	AODV/DSDV/ODSD V
   No. of nodes	20
   Simulation area	900 by 800
   Traffic type	CBR(UDP)
   Bandwidth	2.0 Mbps
   Data payload	512 bytes
   MAC Protocol	Mac/802_11
   Link Layer Type	LL
   Interface Queue Type	Queue/DropTail/PriQu eue
   Interface Queue Length	50
   Antenna Type	Antenna/OmniAntenna

   Table No 2: Parameter values for creating simulation environment.

   Evaluation Metrics: We define some performance evaluation metrics. These are the following:

   • Packet delivery ratio:

     The packet delivery ratio (PDR) is defined as the ratio between the total number of data packets received at the destination to the total number of data packets sent from the source.

     Number of received packets PDR= ————————————

     Number of sent packet

   • Average Latency:

     The mean time (in seconds) taken by packets to reach their respective destinations.

   • Path Optimality:

     The ratio between the length (number of hops) of the shortest possble path and the actual path taken by the packets.

   • Throughput:

     the throughput is defined as the aggregate throughput achieved in Kb/s at the destination nodes for the whole network

     i.e. for all the flows.

   • End-to-end delay:

     this is the average end-to-end delay for all the network flows in milliseconds. The delay is calculated per packet for all the packets arriving at the destinations and the result is the average of all the packets of all the flows.

   • Routing overhead:

     we consider routing overhead as the total number of non-data and non-ACK packets that are generated in the network. These include the routing packets of the protocol and the probe packets used by the ERM (Hello mechanism).

   • Route lifetime:

     we define route lifetime as average duration for which a route remains intact

     i.e. without a breakage. The obtained result is an average of the route lifetimes for all the flows traversing the network. This metric would give an idea about the route stability.[7] [8]

5. SIMULATION RESULTS.

   When deciding on simulation environments to use for implementing the experiments, we reviewed Network Simulation 2 (NS2) extensively since in the past this has been the standard tool used for wireless network simulation. One main advantage of using NS2 is the large number of protocols and modules which have been created over the years. For instance it supports popular routing protocols such as ad-hoc on-demand distance vector routing (AODV) and dynamic distance-sequenced distance-vector routing (DSDV). However, there are several problems with NS2 that make other options more attractive. NS2 was designed originally to be a wired network simulation. All of

   the wireless capabilities were added during later updates to the software and because of this, much of the code for wireless is not consistent. In many cases, modules have been written by many people and in many different styles and coding standards. When trying to extend this work, it takes a great deal of time to understand how the different objects interact. Furthermore, NS2 uses two different languages. The main simulation program is written in the C programming language, however, the scenarios which define the environment, nodes, applications and other entities is written in the TCL scripting language. There is a complex interface between these two languages which makes using NS2 even less intuitive to use and extend. This was especially true in modifying the MAC layer, which is where much of our extensions are applied.

   The following four tests were conducted to evaluate the performance of the ODSDV protocol under varying mobility and traffic load conditions as well as different node configurations:

   • Test 1: Varying MESH_CLIENT speeds

   • Test 2: Varying traffic load

   • Test 3: Varying packet size

   • Test 4: Varying the number of radios per MESH_ROUTER

   Fig 3: A Screenshot of Network Animator.

6. PERFORMANCE EVALUATION.

   In this section, we simulate the performances of the reactive protocol AODV, proactive original DSDV and optimised protocol DSDV (ODSDV) with NS2 in different scenarios. Firstly, we modify the DSDV source code to ODSDV in NS-2 platform and then we build the scenarios of simulation for AODV, DSDV and ODSDV. And we establish ad hoc networks with minimal mobility to simulate the wireless backhaul network environment of WMNs.

   Then we simulate the performances of AODV, DSDV and ODSDV in the scenarios respectively for 50 times and analyze the average results. Based on the average results of the simulation, we compare the network performances in terms of packet delivery ratio, end-to-end delay and routing overhead. Analysis is done by the calculations of the readings from the trace files generated after the simulation.

   1. Normalised Routing Load:

      The number of routing packets transmitted per data packet delivered at the destination. Each hop -wise transmission of a routing packet is counted as one transmission. The first two metrics are the most important for best-effort traffic. The routing load metric evaluates the efficiency of the routing protocol. Note, however, that these metrics are not completely independent. For example, lower packet delivery fraction means that the delay metric is evaluated with fewer samples. In the conventional wisdom, the longer the path lengths, the higher the probability of a packet drops. Thus, with a lower delivery fraction, samples are usually biased in favour of smaller path lengths and thus have less delay. The ODSDV is having the lowest routing load and proves to be efficient.

      Fig 4: Normal Routing Load

   2. Throughput:

      Throughput is the ratio of the total amount of data that a receiver receives from a sender to a time it takes for receiver to get the last packet. A low delay in the network translates into higher throughput. Delay is one of the factors effecting throughput, other factors are routing overhead, area and bandwidth which is not the scope of our thesis. Throughput gives the fraction of the channel capacity used for useful transmission and is one of the dimensional parameters of the network.

      Fig 5: Throughput.

   3. Packet Delivery Ratio (PDR):

      This is the ratio of total number of packets successfully received by the destination nodes to the number of packets sent by the source nodes throughout the simulation. ODSDV shows the better results for PDR.

      Number of received packets PDR= ————————————

      Number of sent packet

      Fig 6: Packet Delivery Ratio

   4. Average end to end delay:

   Fig 6: End- to – End delay

   This is defined as the average delay transmission of a packet between two nodes and is calculated as follows-

   (time Packet Received time Packet Sent) AED = —————————————————

   Total Numbe r Of Packets Receive

   The results show that ODSDV is having lowest delay and it travels to destination using minimum hops.

7. Conclusions and Future Work

The minimum hop metric tends to select paths with long slow links. As a result, these paths have low effective throughput and increase total network congestion. In addition, these paths are likely to contain long links that result in low reliability. We have presented a new metric, an improved technique for route selection in variable rate wireless mesh networks. The proposed Metric is proportional to the time it takes to transmit a packet on a given link. This metric selects paths that have the highest effective capacity. Thus the proposed optimization metric satisfy the desirable properties such as Ensuring route stability, Determined minimum cost/weight paths, Efficient algorithms for calculation of minimum cost/weight paths available, Ensuring loop free forwarding. The optimized DSDV is more reliable than the previous DSDV and reactive protocol AODV.

Our future work is to investigate the performance of all of the existing metrics in real mesh networks based on actual hardware measurements.

References:

1. M.L. Sichitiu, Wireless mesh networks: opportunities and challenge, in Proceedings of the Wireless World Congress, Palo Alto, CA, May 2005.

2. I.F. Akyildiz, X. Wang, W. Wang, Wireless mesh networks: a survey, Computer Networks (2005) Mesh Networks website. Available from:

   <http://www.meshnetworks. com>.

3. Draves R, Padhye J, Zill B. Comparison of routing metrics for static multi-hop wireless networks, ACM Annual Conference of the Special Interest Group on Data Communications (SIGCOMM), Aug 30-Sep 3, 2004, New York. USA: ACM, 2004, 34(4): 133144.

4. Zhao S, Wu Z, Acharya A, et al. A PHY/MAC aware routing metric for ad hoc wireless networks with multi-rate radios, IEEE International Symposium on a World of Wireless, Mobile and Multimedi Networks, June 13-16, 2005, Taormina. USA: IEEE, 2005: 286 292.

5. Amir Esmailpour & Nidal Nasser, Tarik Taleb, Topological-Based Architectures for wireless mesh networks, IEEE Wireless Communications, February 2011.

6. Perkins Charles E, Bhagwat Pravin: Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, London England UK, SIGCOMM 94-8/94.

   <http://www.cise.ufl.edu/~helal/6930F01/papers/DSDV. pdf>

7. Adel.S.El ashheb1, Performance Evaluation of AODV and DSDV Routing Protocol in wireless sensor network Environment, International Conference on Computer Networks and Communication Systems (CNCS 2012) IPCSIT vol.35(2012) © (2012) IACSIT Press, Singapore.

8. Kevin Fall and Kannan Varadhan. The ns Manual. The VINT Project, May 2010, day = 9, file = http://www.isi.edu/nsnam/ns/doc/ns doc.pdf, keywords = Simulation, ns-2, Manual.