Mpr Selection In Olsr Protocol Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Mobile Ad-hoc Networks consists of large number of mobile nodes having limited number of resources like energy, storage capacity, processing capabilities and so on. MANET has lots of intrinsic qualities and offers a lot of advantages in terms of usage flexibility. However, they suffer from several problems such as the rapid change of network topology caused by the high mobility of nodes. It is required to improve the quality of service of these networks to make them adoptable. OLSR is one of the routing protocols mainly used for MANETs. The performance of OLSR protocol mainly relies on multipoint relay (MPR). Flooding efficiency, routing overhead and optimization of OLSR protocol depend on the effective MPR selection. Hence the paper concerns with the use of Fuzzy Logic in the selection of quality nodes as MPR for OLSR protocol one of the routing protocol for MANETs. In this research, fuzzy rule base is formulated and applied to predict the nodes that can serve as QMPR to make OLSR a quality one. The Fuzzy based mechanism for QMPR selection used in this paper gives quantitative results and improves the QoS of OLSR protocol.


A MANET is a multi-hop ad-hoc wireless network in which nodes can move arbitrary in the topology. The network does not require any given infrastructure and can be set up quickly in any environment. MANETs have shown to be increasingly interesting due to their intrinsic qualities such as user mobility, environment adaptability. Because of the limited radio range, they are generally multihop. Therefore, routing protocol is required in order to achieve communications between users in ad hoc networks. OLSR is one of the routing protocols that are widely used in MANET environment.

The OLSR routing protocol [1] has been standardized at IETF. OLSR is based on the MPR (Multipoint Relay) [2] concept to offer an efficient flooding technique and to build shortest routes. However, ad hoc networks should support application with QoS requirements such as multicast applications, VoIP. The MPR selection according to native OLSR is unable to build routes satisfying a given QoS request, because it only allows building the shortest routes which do not take into account any other route metrics like available bandwidth, delay. That is why, the MPR selection should be modified to provide QoS support as done in [3].

Whereas there are already existing analyses of MPR selection[4][5][6], in this paper, MPR selection analysis is extend to take into account QoS support using Fuzzy Logic and some modification are made in the MPR selection algorithm too. The quantitative results obtained by simulations are presented in the support of the proposed approach.

The rest of paper is organized as follows. In section 2, the main principles of the OLSR protocol are presented. In section 3 an overview with concept of Fuzzy Logic is given. In section 4, a modified Fuzzy based QoS MPR selection algorithm and analytical results for this QoS MPR selection are presented. Finally, paper is concluded in section 5.

OLSR Protocol

OLSR is also based upon the traditional link state algorithm. Each node maintains topology information about the network by periodically exchanging link state messages. The optimization introduced by OLSR is that it minimizes the size of each control message and the number of nodes re-broadcasting a message by employing the multipoint relay strategy. The local one hop and two hop neighbourhood is discovered through periodic exchange of HELLO messages. Thereafter each node selects someone hop neighbours to be its multi point relay in a way that all two hop neighbours can be reached through at least one of the selected members of the MPR set. Nodes that are not MPRs can receive and process each control packet but do not retransmit them and do not announce network topology to other nodes in the network. Nodes that are MPRs of at least one node forward packets for the nodes that selected them as MPRs and announce all nodes that selected them as MPR by topology content packets to the entire network. Based on its one hop and two hop neighbourhood and the topology information each node calculates an optimal route (with regard to hop count) to every known destination in the networks and stores it in its routing table.

Fig 1: A MPR ( Nodes) based OLSR protocol for flooding a packet

Architecture of the Fuzzy Logic based QMPR Selection for OLSR protocol

The concept of FL is given by Zadeh [7] to solve the vagueness in linguistic variables. It is based on implication and simulation of human knowledge as nature implements it in daily life. The core of the proposed methodology is the Fuzzy Inference System (FIS). It is a combination of fuzzification system, fuzzy inference engine & defuzzification system. The architecture of FIS as a combination of the three subsystems is shown in the figure 2.


Fuzzy Inference Engine


Membership Function

Fuzzy Rule Base

Input Constraints


Fig 2: Architecture of FIS

To predict and select the quality nodes as MPR for OLSR protocol from the MANET environment a fuzzy based system is formed. Various quality factors have been taken into consideration to select the best node to serve as MPR to improve the efficiency and life time of the whole network. The relationship between nodes attributes is represented as

,, (1)

In the above equation Qf represents the quality of a node and Xn ,Yn , Zn represents any three attributes of a node. For the proposed approach node energy, node mobility and node coverage has been taken into consideration. After applying the fuzzification process the crisp values of these attributes has been passed to the fuzzy inference engine where a check with the fuzzy rule base has been made based on the crisp inputs and quality of node has produced as output for the MPR selection. These crisp outputs again converted to the actual values using the defuzzification process. The system architecture of the used model is shown in figure 3.

Fig 3: System Architecture of OLSR based on FIS approach

Fuzzification Process: - In the fuzzification process three attributes node energy, node mobility and node coverage have been taken as input to form a fuzzy set. Based on the fuzzy set degree of membership of these attributes have been evaluated and converted into the crisp values.

Fig 4: Fuzzification function for Node-Energy

Fig 5: Fuzzification function for Probability of QMPR

Fuzzy Rule Base: - It is used to take the crisp values of attributes as an input and match them in the fuzzy rule base [8] for the predication of the quality nodes that can be used to server as QMPR. In the proposed approach 27 rules are formulated for the three input values. Some of the proposed rules are shown as:

Fig 6: Fuzzy Logic Rules for the Selection of QMPR for OLSR Protocol

Defuzzification Process: - It is the process of converting the crisp values into the actual values obtain from fuzzy inference engine and predict the best nodes. Here centroid method is used for the defuzzification process. After the defuzzification process the below formula is used to predict the quality nodes for the QMPR selection:-


QMPR Selection algorithm for OLSR Protocol

In this section a modified algorithm for QMPR selection based on Fuzzy Logic is presented. The algorithm helps in improving the life time of the whole network by minimizing the energy consumption of the network and the makes the OLSR protocol more reliable, efficient and prolong for the MANETs. The following terminology in used in describing this algorithm:-

N(x): The set of one hop neighbors of node x created by changing HELLO messages between nodes.

N2(x): The set of two hop neighbors of node x created by changing HELLO messages. It do not contain any one hop neighbor of node x.

D(x, y): The degree of hop neighbor y. The number of nodes in N2(x) that are covered by y.

D[x, y] = number of elements of N[y] - {x} â€" N[x]

1. Start with the empty set of MPR for a node X.

2. Calculate the value of D(x,y) and Qf for every node that has associated with N(x).

3. Arrange the value of Qf in decreasing order obtained from the step 2.

4. First select as MPRs that have highest value of Qf and nodes in N[x] which provides the “only path” to reach some nodes in N2[x]

5. While there still exists some nodes in N2[x] that is not covered by MPR[x]:

For each node in N[x], calculate the number of nodes in N2[x] which are not yet covered by MPR[x] and are reachable through this one hop neighbor;

Select as a MPR that node of N[x] which reaches the maximum number of uncovered nodes in N2[x]. In case of a tie, select that node as MPR whose D[x, y] is greater.

6. To optimize, process each node y in MPR[x], one at a time, and if MPR[x]-{y} still covers all nodes in N2[x] then remove y from MPR[x]

7. Go to step 4 until Qf becomes empty.

8. Stop the procedure.

Simulation Results

For the verification and validation of the proposed approach Maltlab 7.12 and ns2 is used. The results obtained by the proposed approach shows that if various attributes have been taken into consideration for the MPR selection for the OLSR protocol, it will improve the quality of the OLSR protocol and the quality of the network too.

Fig 7: Surface View of node-energy, node-mobility, nodeâ€"coverage with node probability of QMPR

The above result represent the relationship between the three attributes of a node and there probability for the selection as a QMPR. It also clarifies that a node that have higher energy and low mobility has the better chance to be elected as QMPR. Using the above formulation the QoS of the OLSR has been improved. It is shown in the figure 6 that by using this approach of QMPR selection the energy consumption rate moves to the lower side and hence an improved network life time and an improved OLSR.


Fig. 8: Energy Consumption


In this paper, we have computed the complexity of the selection of QoS MPRs using Fuzzy Logic, i.e., multipoint relays selected according to a QoS metric as for instance the node energy, node mobility and the node coverage. The approach helps in assign the higher responsibilities to the quality nodes and thus improving the quality of the OLSR protocol and the network. The fuzzy logic based OLSR protocol was proposed to make the OLSR a quality one for the MANETs. The network lifetime is increased by selecting the quality nodes to serve as MPRs. The proposed approach helps in increasing the throughput & lifetime of the network. In future different set of metrics can be used to improve the efficiency of the proposed fuzzy logic based approach for OLSR protocol.