Performance characteristics of OLSR and AODV protocols in Wireless Mesh Network

Performance characteristics of OLSR and AODV protocols in Wireless Mesh Network

Navtej Singh Sandhu1, Navdeep Kaur Sandhu2, Ashwinder Singp

1. ech Student1 Guru Nanak Dev University Amritsar, Assistant Proffesor2 Chitkara University Rajpura, M.Tech Student3 Guru Nanak Dev University Amritsar

   Abstract A wireless mesh network (WMN) is a communications network made up of radi o nodes organize d in a mesh topology. Wireless mesh networks often consist of mesh clients, mesh routers and gate ways. The mesh clients are often laptops, cell phones and other wireless de vices while the mesh routers for war d tr affic to and from the gate ways which may but nee d not c onnect to the Interne t. The coverage area of the radi o nodes working as a single network is sometimes called a mesh cloud. Wireless mesh networks can be imple mente d with various wireless technology including 802.11, 802.15, 802.16, cellular technologies or combinations of more than one type . AODV is a very popular routing protocol for MANETs. It is a reactive routing protocol. OLSR is a popular proactive routing protocol for wireless ad hoc networks.

   1. INTR OD UCTION

      The mos t obv ious ad van tag e o f wire less n et wo rking is mo b ilit y . W ire less n et wo rk use rs can con nec t to e xis t in g net wo rks and are th en a llo we d to roa m fre e ly . A mob ile t e lephon e use r ca n d riv e mile s in th e cou rse o f a s in g le con ve rsat ion bec ause the ph one co nne cts t he use r t h rough c e ll to we rs. In it ia lly , mo b ile t e le phony was e xp ens iv e . Costs rest rict ed its use to h ig h ly mo b ile p ro fess iona ls s uch as sa les ma nag e rs and impo rt ant e xe cut ive de c is ion ma ke rs who might n eed to b e rea che d at a mo men t's no t ic e rega rd less o f t he ir lo cat ion . Mob ile t e le phony h as p ro ven to be a use fu l s erv ic e , h o we ve r, and no w it is re la t iv e ly c o mmo n in t he Un ite d Stat es and e xt re me ly co mmo n a mo ng Eu rop eans . W ire less n et wo rks typ ica lly ha ve a g re at de a l o f fle xib ility , wh ich ca n t ra nslat e int o rap id d ep lo y ment . Like wise , wire less d ata ne t wo rks fre e so ft wa re d ev e lop ers fro m t he teth e rs o f an Ethe rnet ca b le at a d esk. De ve lope rs can wo rk in the lib ra ry , in a con fe ren ce roo m, in th e p a rkin g lot , o r even in th e co ffee house

      a c ross th e st re et . Co mmo n ly av a ilab le e qu ip me nt c an e as ily c ove r a co rpo rate ca mpus; with so me wo rk, mo re e xot ic e qu ip me nt , a nd fa vo rab le t e rra in, yo u can e xte nd the range o f a n 802.11 n et wo rk up to a fe w miles .

   2. Comparis on be twee n Wire less Ad Hoc and Mes h Networks

      The ma jo r c ate go ries in t he mu lt i-h op wire less n et wo rks a re th e ad hoc wire less n et wo rks , W M Ns, wire less senso r ne t wo rks , and h yb rid wire less net wo rks. Th is p ape r ma in ly focus es on W M Ns. Ad ho c wire less ne t wo rks a re ma in ly in frast ruc tu re -less net wo rks with h igh ly dyn a mic to po log y . W ire less senso r ne t wo rks , fo rmed by t iny senso r nodes that ca n ga the r phys ic a l p a ra me te rs and t ra ns mit t o a c ent ra l mo n it o ring no de , c an us e e ithe r s ing le -hop wire less c o mmu n icat ion o r a mu lt i-ho p wire less re la y ing . Hy b rid wire less net wo rks ut ilize bo th s ing le & mu lt i-hop co mmu n ic at io ns s imu lta neo usly with in th e t rad it iona lly s in g le -hop wire less n et works su ch as ce llu la r ne t wo rks and wire less in lo ca l loops (W iLL).

      A wire less mesh net wo rk c an b e see n as a sp ec ia l ty pe o f wire less ad -h oc n et wo rk. A wire less mesh n et wo rk o ft en has a mo re p lann ed con figu ra t ion , a nd may b e d ep loyed t o p rov id e dyn a mic a nd cost e ffec t ive conn ec t iv it y ove r a c e rta in geo g raph ic a rea . An ad -ho c net wo rk, o n th e othe r ha nd , is fo rme d ad ho c when wire less de v ic es co me with in c o mmu n icat ion ran ge o f e ach ot he r. The mesh rou te rs ma y b e mob ile , and be mo ve d a cc o rd ing to spe c ific d e man ds a ris ing in the n et wo rk. Oft en t he me sh ro ute rs are no t limit ed in te rms o f reso u rces c o mpa red to oth e r nod es in the n et wo rk and thus c an be e xp lo it ed to pe rfo rm mo re resou rce in tens ive func t ions . In th is wa y , th e wire less mesh n et wo rk d iffe rs fro m an ad -ho c n et wo rk, s in ce

      th ese no des a re o ften const ra ine d by resou rces .

      Table 1: Difference Between Ad Hoc Wireless networks and Wireless Mesh Networks

   3. Routing Protocols

      This section will describe selected routing protocols for wireless multihop networks as an illustration of the general concepts of routing protocols as well as some special routing protocols for wireless mesh networks. A comprehensive overview of all routing protocols cannot be done due to limited space.

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

      AODV is a very popular routing protocol for MANETs. It is a reactive routing protocol. Routes are set up on demand, and only active routes are maintained. This reduces the routing overhead, but introduces some initial latency due to the on-demand route setup. The advantage of AODV is that it creates no extra traffic for communication along existing links. Also, distance vector routing is simple, and doesn't require much memory or calculation. However AODV requires more time to establish a connection, and the initial communication to establish a route is heavier than some other approaches. AODV uses a simple request-reply mechanism for the discovery of routes. It can use hello messages for connectivity information and signals link breaks on active routes with error messages. The routing information has a timeout associated with it as well as a sequence number. The use of sequence numbers allows detecting outdated data, so that only the most current, a variable routing information is used. This ensures freedom of routing loops and avoids problems known from classical distance vector protocols, such as

      counting to infinity.

      The source node S broadcasts a route request (RREQ) throughout the network In addition to several flags, a RREQ packet contains the hop-count, a RREQ identifier, the destination address and destination sequence number, and the originator address and originator sequence number.

      Figure 1: AODV r oute discover y: route re quest (left) and route re pl y (right)

      When a node receives a RREQ packet, it processes as follows:

      • The route to the previous hop from which the RREQ packet has been received is created orupdated.

      • The RREQ ID and the originator address are checked to see whether this RREQ has been already received. If yes, the packet is discarded.

      • The hop-count is incremented by 1.

      • The reverse route to the originator, node S, is created or updated.

      • If the node is the requested destination, it generates a route reply (RREP) and sends the RREP packet back to the originator along the created reverse path to the source node S.

      • If the node is not the destination but has a valid path to D, it issues a RREP to the source depending on the destination only flag. If intermediate nodes reply to RREQs, it might be the case that the destination will not hear any RREQ, so that it does not have a back route to the source. If the gratuitous RREP flag is set in the RREQ, the replying intermediate node will send a gratuitous RREP to the destination. This sets the path to the oiginatorof the RREQ in the destination.

      • If the node does not generate a RREP, the RREQ is updated and rebroadcast if TTL 1.

        On receipt of a RREP message, a node will create or update its

        route to the destination D. The hop-count is incremented by one, and the updated RREP will be forwarded to the originator of the corresponding RREQ. Eventually, the source node S will receive a RREP only if the path is available to the destination. The buffered data packets can now be sent to the

        destination D on the newly discovered path.

        In case of link failure the node before the broken link checks first whether any active route is using the broken link. If this was not the case, nothing has to be done. If there have been active paths, the node may attempt local repair. It sends out a RREQ to establish a new second half of the path to the destination. The node performing the local repair buffers the data packets while waiting for any route replies. If local repair fails or has not been attempted, the node generates a route error (RERR) message. It contains the addresses and corresponding destination sequence numbers of all active destinations that have become unreachable because of the link failure.

        Optimized Link State Routing Protocol (OLSR)

        OLSR is a popular proactive routing protocol for wireless ad hoc networks. It has been developed at INRIA and has been standardized at IETF. OLSR uses the classical shortest path algorithm based on the hop-count metric for the computation of the routes in the network. Since link-state routing requires the topology database to be synchronized across the network, OSPF and IS-IS perform topology flooding using a reliable algorithm. Such an algorithm is very difficult to design for ad-hoc wireless networks, so OLSR doesn't bother with reliability; it simply floods topology data often enough to make sure that the database does not remain unsynchronized for extended periods of time. However, the key concept of OLSR is an optimized broadcast mechanism for the network-wide distribution of the necessary link-state information. Each node selects the so-called multipoint relays (MPRs) among its neighbors in such a way that all 2-hop neighbors receive broadcast messages even if only the MPRs rebroadcast the messages. The forwarding of broadcast messages by MPRs only can significantly reduce the number of broadcast messages. Figure 2 shows an example where the numberof broadcast messages is reduced by half.

        Figure 2: Multi point rel ay selection in OLSR

        OLSR proposes a simple heuristic for the MPR selection in which is described below, but other algorithms are possible.

      • N: Neighbors ofthe node.

      • N2: The set of 2-hop neighbors of the node excluding (i) nodes

        only reachable by members of N with willingness WILL_NEVER, (ii) the nodes perform the computation, and (iii) all the symmetric neighbors: the nodes for which there exists a symmetric link to this node.

      • D(Y): Degree of 1-hop neighbor Y 2 N, which is the number of symmetric neighbors of Y excluding all members of N and excluding the node performing the computation

      • Step 1: Start with an MPR set consisting of all members of N with willingness =

        WILL_ALWAYS

      • Step 2: Calculate D(Y), for all Y 2 N

      • Step 3: Add to the MPR set those nodes in N, which are the only nodes to provide reachability to a node in N2

      • Step 4: Remove the nodes from N2 which are now covered by a node in the MPR set

      • Step 5: While there still exist nodes in N2 which are not covered by at least one node in the MPR set:

        For each node in N, calculate the reachability, i.e., the number of nodes in N2 that are not yet covered by at least one node in the MPR set, and which are reachable through this 1-hop neighbor.

        Select as an MPR the node with highest willingness among the nodes in N with nonzero reachability. In case of a tie, select the node that provides reachability to the maximum number of nodes in N2. In case of multiple nodes providing the same amount of reachability, select the node as MPR whose D(Y ) is the greatest. Remove the nodes from N2 that are now covered by a node in the MPR set

      • Step 6: As an optimization, each node Y in the MPR set can be checked for omission in increasing order of its willingness. If all nodes in N2 are still covered by at least one node in the MPR set excluding node Y, and if the willingness of node Y is smaller than WILL_ALWAYS, then node Y may be removed from the MPRset.

      The OLSR routing table that contains entries for all reachable destinations in the mesh network (proactive routing protocol) is computed from the link set, neighbor set, 2-hop neighbor set, and topology set with a classical shortest path algorithm (e.g., Dijkstra algorithm). If any of the above sets has changed, the routing table has to be recalculated. Furthermore, it might be useful to send a hello or TC message to propagate the change of the topology immediately.

      OLSR can also deal with multiple (OLSR) interfaces at a node. Such a node selects the address of any one of its interfaces as the main address and periodically broadcasts multiple interface declaration (MID) messages. MID messages distribute the relationship between the main address and other interface addresses. Obviously, a node with only a

      single OLSR interface does not have to send MID messages.

      In a wireless mesh network, some degradation in throughput might be expected over five or six hops. Channel interference could result in lower throughput if the nodes are too close to each other or if the power is too high for the area. WMN routing protocols should select paths based on observed latency and wireless environment as well as other performance factors, resulting in the best possible throughput across the network.

   4. Simulation Evaluation

      We performed simulation e xperiments using the 802.11s MAC protocol availab le in standard wireless library o f QualNet 5.0. We developed Multi Channel xTDMMA C Wireless Mesh Networks. The bit rate for each channel is 2 Mbps and the transmission range of each node is approximately 250 m. Each source node generates and transmits constant bit rate (CBR) t raffic. We ran each simu lation for 80 seconds of simu lated time. Each data point in the results is the average of 30 replications with diffe rent random seeds. Unless otherwise specified, the packet size was 512 bytes and the packet arrival rate fro m each node was 50 Pac kets/s. Simu lation e xperiments were performed for both single-hop and mu ltip le-hop network scenarios. For the single-hop network simulations, all nodes were within each the transmission range of all other nodes, thus every source node can reach its destination node in a single hop. For each scenario, half of the nodes were data sources and the other half were data destinations. We considered both stationary and mobile ad hoc networks for the multiple – hop network scenario. In the simulat ion of stationary nodes, nodes were randomly placed in a 1500 m by 1500 m square area and did not move. The random waypoint model was used for mobility with a pause time of 30- seconds and a ma ximu m node speed of 10 m/s. The developed scenario is imp le mented successfully.

      Performance Characteristics of routing protocols (OLSR, AODV)

      1. Per for mance Evaluati on of Thr oughput capacity.

         Figure 5, depicts a scatter plot comparing throughput for mu lti-hop bi-directional flows obtained, by applying the OLSR and AODV routing algorith m to the multi channel TDM MAC protocol. It is easily observable fro m the figure that the throughput capacity of OLSR (Pro -active routing) protocol is very much better than AODV (React ive routing). The variation in the overall throughput process depends on the number of hops in

         between the mesh source address and mesh destination address. The variations also depend on the number of receiving (RX), and transmitting (TX) channls per a slot in a TDM structure. For e.g. nodes 10 to 20 have a heavy full duple x traffic flow pe r node, so that the throughput is considerably low on that region. The nodes from 30-35 are located at 3 hop distance, this results into their throughput degradation as expectedly.

         Figure 3: xTDM MAC Thr oughput of OLSR and AODV

      2. Packet Loss Rati o

         We consider a chain topology of four nodes and evaluate the performance of the packets transmitting successfully in paralle l fro m the gateway node to the downstream network nodes. Figure 6, shows the diffe rence in packet loss in OLSR and AODV for xTDMMA C protocol. We observe that the average loss rates of OLSR achieves higher successful delivery ratio than AODV. The nu mber of successful delivery of packets in AODV is almost 0, and the average packet loss ratio is more in A ODV than co mpared with OLSR.

         Figure 4: Packet l oss ratio in be tween OLSR and AODV

      3. Mesh Manage ment Statistics collected by 802.11s

         Figure 5 shows difference in between the number of association requests enqueued for sending to mesh neighbors and the number of association requests received fro m mesh neighbors .

         Figure 5: Comparison in graphs of mesh associati on requests

   5. CONCLUSION

We evaluated the performance characteristics of AODV and OLSR routing algorith ms. The simu lation results show that proactive routing protocols have best performance rat io than reactive protocols for multi channel systems. We compared the mesh lin k status announcements forwarded and received for all mesh nodes with diffe rent hop count, the analysis of the graph proved that the designed mesh scenario is behaving in a proper way as per the 802.11s standard.

Thus we can say that if the Throughput and Packet loss

ratio results of these Protocols (OLSR and AODV) are imple mented by using a programmab le wire less platform on real time will provide a milli-level accuracy results.

REFERENCES

1. Ekram Hossain, Kin K. Leung "Wireless M esh Networks: Architectures and Protocols ", Springer | 2007-11-20 | ISBN: 0387688382 | 332 pages

2. A.A. Alahmadi, M .A. M adkour, Performance Evaluation of the IEEE 802.11e EDCA Access M ethod, International Conference of Innovation Technology, 2008, pp. 490-494

3. IEEE P802.11sTM /D0.01, draft amendment to standard IEEE 802.11TM : ESS M esh Networking, Nov. 2006.

4. Cai, J., and Goodman, D. J. General packet radio service in GSM . IEEE Communications M agazine, vol. 35, no. 10, October 1997, pp. 121-131.

5. C. Siva Ram M urthy and B.S. M anoj, Ad hoc Wireless Networks: Architectures and Protocols, Prentice Hall PTR, New Jersey, M ay 2004.

6. Dimitrios Koutsonikolas1, Theodoros Salonidis, Henrik Lundgren, TDM M AC Protocol Design and Implementation for Wireless M esh Networks , ACM CoNEXT 2008, December 10-12, 2008, M adrid, SPAIN , page(s): 97-108

7. J. Li, C. Blake, D.S.J. De Couto, H.I. Lee, and R. M orris,

   Capacity of Ad Hoc Wireless Networks, Procee dings of ACM Mobicom 2001, pp. 61-69, July 2001.

8. Y. Yang, J. Wang, and R. Kravets, Interference- aware Load Balancing for M ultihop Wireless Networks, Technical Report UIUCDCS-R-2005-2526, Department of Computer Science, University of Illinois at Urbana- Champaign, 2005.

9. Ashish Raniwala, Tzi-cker Chiueh,Architecture and Algorithms for an IEEE802.11-based Wireless M esh Network, Proceedings of IEEE Infocom, 2005.page(s):2223-2234

10. R. Draves, J. Padhye, and B. Zill, Routing in M ulti- radio, M ulti-hop Wireless M esh Networks, Proceedings of ACM Mobicom 2004, pp. 133-144, September 2004.

11. Guan-nan chen, Chiung-yung wang, and Ren-hung hwang, M ulti-hop Time Synchronization Protocol for IEEE 802.11. Wireless Ad Hoc Networks Journal of Information science and Engineering 23, 969-983 (2007)