Proposal 1

Implementation of a new Algorithm for MPR selection in an OLSR protocol based Wireless Mesh Network Prashanth Gopinath, Srikanth Subramanian and Janani Swaminathan Department of Electrical and Computer Engineering, University of Florida

Abstract In this project we aim to implement a new algorithm for the selection of Multi Point Relays (MPRs) in the OLSR protocol. This would involve detailed background study about wireless mesh networks and the OLSR protocol. Further we will describe the proposed algorithm to update the MPR tables maintained by the OLSR protocol and the procedure for implementing this on a router. We also aim to provide a comparison between the performance of two networks, one running on conventional OLSR and the other with the modified OLSR.

1. Introduction OLSR protocol (Optimized Link State Routing Protocol) is a classic table driven, proactive protocol that works efficiently. The routing strategy of OLSR protocol is similar to traditional routing protocols. Each node broadcasts control packets periodically, exchanges nodes‟ information and discovers routes proactively and independently. Compared with the classical flooding mechanism, OLSR protocol reduces routing overhead with the help of its key concept – MPR (Multi Point Relay). Each node in the network selects part of its symmetric neighbors as MPR with MPR selection algorithm. Only MPRs are allowed to diffuse topology information. An optimization is achieved by minimizing the number of control messages flooded in the network. MPR also reduces the size of the topology control message by reporting links between itself and its MPR selectors instead of links to all symmetric neighbors. OLSR operates in three main steps:  Neighbor sensing. This is achieved by exchanging HELLO messages between all one-hop neighbors in a network. Through periodic HELLO messages received from its one-hop neighbors, a node is able to select its MPRs. Then a link state database and a neighborhood database are established by each node based on neighbor sensing.  TC messages dissemination. Each node, through its MPRs, periodically advertises its link information to all other nodes inside the network. As a consequence, all nodes inside a network have necessary topology



information for all links between any two nodes inside the same network. Routing table calculation. Based on TC messages received from other nodes, a node is able to compute its shortest-path routes to all reachable nodes in the network, by using an algorithm similar to the Dijkstra‟s algorithm. The shortest-path in terms of the number of hops is used for route calculation in OLSR.

Furthermore, two other messages are defined in OLSR, i.e. Multiple Interface Declaration (MID), and Host and Network Association (HNA). MID messages are used when a node is equipped with multiple interfaces, i.e. multiple wired or wireless cards. However, only one interface is selected as the ID (main address) of the node. HNA messages are used when a node functions as a gateway node, and it is especially useful when an ad hoc network is connected to the Internet. Gateway here means the nodes which provide connectivity between an ad-hoc and external networks, e.g. the Internet. OLSR maintains the following set of tables: Tables Neighbor table 2 Hop Neighbor table MPR table MPR selector table

Topology table Routing table Duplicate table

Details State of neighbors State of 2 hop neighbors Information about MPR of own node Neighboring nodes which select this node as their MPR Information acquired from TC messages received Routing information Information about most recently received messages

2. Proposed Modification The existing MPR tables can be optimized by using this algorithm that generates a reduced set of MPRs which result in reduced overhead in the network when link state information is transmitted to all the nodes in the network. The existing method of selecting MPRs is based on Greedy Algorithm. Its step could be stated as follows.





Step 1: Select all one hop neighbors that could provide the only reach ability to some two hop neighbors as MPRs. Step 2: If there are still some two hop neighbors that are not covered by MPR, select that one hop neighbor which covers the most uncovered two hop neighbors as MPR. Now repeat this step until all two hop neighbors are covered by MPRs.



Fig.1 below is an example of selecting MPRs using the above heuristic. As shown in the figure the one hop neighbor set of A includes the nods {B C D E F} while MPR set of A is {B C D}.

reach-ability to some nodes in the set of second hop neighbors, select these nodes as MPRs. Then delete all two hop neighbors that are covered by these nodes from N2(x). Now if there is no node in N2(x) then stop else go to step 3 Step 3: Recalculate D(x,y) for all nodes in N(x) and choose the nodes with the minimal degree. If there is only one node with minimal degree delete it from N(x) and recalculate D(x,y) for all nodes in N2(x) and go to step 2, else using rule I break the tie and delete the selected node from N(x). Now again recalculate D(x,y) for all nodes in N2(x) and go to step 2.

Where N(x) is the set of first hop neighbors for node x, N2(x) is the set of second hop neighbors for node x excluding any node already in N(x). D(x,y) is the degree of node x‟s one hop neighbor y. This is the number of nodes in N2(x) that are covered by y. All these sets can change during the course of selection of MPRs. Rule I: If D(x,y1) = D(x,y2) then for yi(i ɛ {1,2})   

 It is obvious that {B C D} is not the MPR set of minimal size. It is easily seen that we require only the two nodes {C D} to cover all two hop neighbors. The Greedy algorithm cannot select the optimal MPR set {C D} as the algorithm uses cover ability as the heuristic. However there occurs an overlap as the nodes covered by B are also covered by C. This limitation of the Greedy algorithm not being able to always arrive at the optimal solution is addressed by the Necessity First Algorithm(NFA). The NFA decreases the number of MPRs significantly. Its description is as follows. The NFA chooses from a different angle trying to overcome the problem of Greedy Algorithm. NFA is based on “necessity of selecting” unlike GA which is based on cover ability. According to this basis,  

Step 1: Calculate N(x), N2(x), D(x,y) for all nodes in N(x). Step 2: If there are any nodes in the set of one hop neighbors who are the only nodes providing

Step 1: Find all nodes in N2(x) that are covered by yi. Step 2: Find all nodes in N(x) that could cover any of the two hop neighbors found in step 1. Step 3: Calculate the number of two hop neighbors in N2(x) covered by the one hop neighbors found in step 2. Step 4: Select that node which has a bigger number as a result in step 3.

3. Related Work OpenWRT: Setting up a build environment

OpenWRT is a Linux based firmware program which is used to customize embedded devices and residential gateways. OpenWRT is the platform being used on the netgear WGT634u routers. The website www.qcsmesh.com provides step by step instructions of how to create a „build environment‟ that provides a platform for one to add additional packages to the already existing basic packages that OpenWRT provides. This freedom of customization allows one to use a device in ways never envisioned. The QCS Mesh routers in essence have their wireless 802.11 protocols used in the netgear routers replaced with OLSR protocol. This enables them to be a part of an ad-hoc mesh network where one of the routers acts as a gateway. This makes it possible to extend a physically constrained network connection, eg. an internet gateway, over to a larger area thus providing extensive connectivity.

To compile customized OpenWRT firmware, a build environment has to be setup. This process involves installing the OpenWRT toolchain, necessary to build a OpenWRT image and packages that can be later installed on the netgear device, on a host unix system. Upon completion of the installation, the particular build of OpenWRT can be configured by using the configure menu. Later additional packages can be added depending on customization desired. In this particular case, the olsrd package is installed and the image file is compiled by using the „make‟ command. This file can be then flashed on to the device using either of the steps mentioned below. Configuring a router to be a part of a mesh network

This process involves setting up a connection between the router and the computer with OpenWRT. This is achieved using a serial console built using a RS232 complaint cable a MAX3232 IC for level conversion of voltage between the two. The whole console is comprised of a MAX3232 converter pcb with a serial input and serial output connection. This is connected to the pc using a usb to rs232 serial cable adapter. The other end of the max3232 ic is connected to the serial port of the netgear wgt634u router. This method is one of the two methods available for flashing images onto the device. The schematic for the max3232 pcb package is as shown in fig.2. The other method that is easier, faster and generally used more often is the direct update of the firmware by writing it on the device by connecting to it through a standard Ethernet cable. This does not require a serial to a usb converter (in case the computer has a serial port, we would still need level conversion). But this method can be used only in the case of flashing precompiled packages available on the OpenWRT website.

The OLSR protocol: An Overview of the code

The Olsrd package provided by www.olsr.org contains the C code of the OLSR algorithm that needs to be modified. The OLSR daemon provided by olsr.org is an implementation of the Optimized Link State Routing protocol. It provides for routing of mobile ad-hoc networks and is driven by a technique called multipoint relaying. Olsrd is a well structured and well coded implementation that is easy to maintain, expand and port to other platforms. The implementation is RFC3626 compliant with respect to both core and auxiliary functioning. Olsrd supports use of loadable plug-ins. These can be used to handle and generate custom packet types that can be carried by olsr‟s MPR flooding scheme or any other desired functioning. Olsrd is an ongoing open source project. Olsrd is on layer 3 and is highly portable. It can run on a variety of platforms which include Windows, Linux, OS X, VxWorks, NetBSD, FreeBSD, OpenBSD etc. The entire Olsrd package consists of approximately over ninety source and header files. The selection of MPRs is governed by a set of around 20 source and header files that contain the definition of all different functions, procedures and class definitions that are used to store topology information in the form of a number of tables as mentioned in previous sections. The olsr.c file contains function definitions which process changes when there are any updates in the neighborhood and/or topology. It recalculates the topology and calls the corresponding functions to update the routing tables. Routing table entries consist of calculating initial values of the tables, initial selection of the MPR set and other calculations. olsr_protocol.h contains values and packet formats as proposed in RFC3626 and miscellaneous values and data structures used by the olsr.org olsr daemon. The central focus of this particular modification would revolve around the following few files. olsr_spf.c: This part of the code calculates and assigns a

„cost function‟ for each node in the topology. Initially all nodes are initialized to infinite cost. First the heap of reachable nodes is collected. The heap implementation is based on an AVL tree which provides interesting performance characteristics for the frequent operations of minimum key extraction and re-keying. Next all neighbors are explored and put on the heap if the cost of reaching them is better than the current candidate node. The SPF (Shortest Path First) calculation is terminated if there are no more nodes on the heap. mpr.c : This file consists of code which is used to select 2 hop neighbors based on the cost and willingness of the node. The willingness of a node is determined based on the power status of the node. This calculation is based on the greedy algorithm. The 2 hop neighbor table is used for the mpr table updation. This is generated by the code in 2_hop_neighbor_table.c. olsr_cfg.h : This file defines default values for the parameters used in the olsr_cfg.c file which haven‟t been initialized to any particular value. The above files are the ones we aim to modify in order to produce a difference in the mpr selection table entries.

4. Anticipated Results The OLSR protocol based on the new algorithm selects a fewer number of MPRs while maintaining the connectivity of every node to every one of its 2 Hop neighbors as per protocol requirements. This is expected to be less than the number of MPRs selected by the OLSR protocol employing the greedy algorithm introduced in RFC 3626.

5. Conclusion and Future Work Further work will include modifying the C code as previously mentioned in the earlier sections to obtain increased performance through decreased number of MPRs. A comparison of the performance of the old and modified OLSR also seems in order. Finally a wireless mesh network consisting of nodes following the modified OLSR protocol on netgear WGT634U routers will be implemented.

6. References [1] Yan Wen, Guo Wein and Liu Jun, “An Implementation and Study of OLSR protocol in Linux OS”, 4th International Conference on Wireless Communications, Networking and Mobile Computing 2008, WiCom ‟08, Oct 2008. [2] Zheng Li, Nenghai Yu, Zili Deng, “NFA: An Algorithm to select MPRs in OLSR”, 4th International Conference on

Wireless Communications, Networking Computing 2008, WiCom ‟08, Oct 2008.

and

Mobile

[3] Dang Nguyen and Pascale Minet, “Analysis of MPR selection in the OLSR protocol”, 21st International Conference on Advanced Information Networking and Application Workshops (AINAW‟07), 2007. [4] Frank Y. Li, Lorenzo Vandoni, Giampietro Zicca, and Stefano Zanoli, “OLSR Mesh Network for Broadband Access: Enhancements, Implementation and Deployment”, 4th IEEE International Conference on Circuits and Systems for Communication, 2008. ICCSC 2008. May 2008. [5] Mounir Frikha, and Manel Maamer, “Implementation and Simulation of OLSR protocol with QoS in Ad Hoc Networks”, Higher School of Communication of Tunis, Network Department. [6] http://openwrt.org/ [7] http://www.olsr.org/ [8] www.members.shaw.ca/swstuff/wgt634u.html [9] http://qcsmesh.com/twiki/bin/view/QCSMesh/WebHome