ABSTRACT

The performance of a Mobile Ad hoc Network (MANET) is closely related to the capability of the implemented routing protocol to adapt itself to unpredictable changes of topology network and link status. The Optimized Link State Routing (OLSR) protocol is a one key of the proactive routing protocols for MANETs. It is based on the multi-point relays (MPRs) technique to reach all nodes in the network with a limited number of broadcasts. In this paper, we propose new versions of the original OLSR protocol based on a new mobility parameter, in the goal to enhance and adapt it in the presence of the mobility. For this objective we define new three criterions for MPRs selection. The first criteria take for selection, just the mobility of nodes at one-hop. The two others criterions are based on both mobility of nodes at one-hop and two-hops.

1.  Introduction

A Mobile Ad hoc Network (MANET) is a collection of mobile nodes (MNs) that cooperatively communicate with each other without any pre-established infrastructures such as a centralized access point. These nodes may be computers or Devices such as laptops, PDAs, mobile phones, pocket pc with wireless connectivity are commonly used. Due to the fact that MNs change their physical location by moving around, the network topology may change unpredictably. This causes changes of link status between each MN and its neighboring. Thus, MNs which join and/or leave the communication range of MN in the network will surely change its relationship with its neighbors by detection of a new link breakages and/or link additions. In the same way, the change of the all routes printed by this MN is also based on the relationship. This change of routes is made with an overhead traffic in the process of maintenance routes assured by the implemented routing protocol in a MANET. For resume, the performance of a MANET is closely related to the capability of the routing protocols to adapt themselves to unpredictable changes of topology network and link status [23,24].

One of the most important aspects of the communication process is the design of routing protocols used to establish and maintain multi-hop routes to allow data communication between nodes. Several researches have been done in this area, and many multi-hop routing protocols have been developed. The Optimized Link State Routing (OLSR) protocol [1,2], Dynamic Source Routing protocol (DSR) [5], Ad Hoc on Demand Distance Vector protocol [6], Temporally Ordered Routing Protocol (TORA) [12], and others protocols that establish and maintain routes on a best-effort basis. There are three main categories of MANET routing protocols: Proactive (table-driven), Reactive (on-demand) and Hybrid. Proactive protocols build their routing tables continuously by broadcasting periodic routing updates through the network; reactive protocols build their routing tables on demand and have no prior knowledge of the route they will take to get to a particular node. Hybrid protocols create reactive routing zones interconnected by proactive routing links and usually adapt their routing strategy to the amount of mobility in the network.

In this paper, we present a new quantitative measure of node mobility reflecting the mobility degree at each node in the MANET. This node mobility degree is related to the link status change in the vicinity of the communication range. Therefore, based on this mobility quantification at each MN in the MANET, we have proposed three versions of the original OLSR protocol to enhance and adapt it in the presence of high mobility, i.e. high topology and link status changes.

The rest of this paper is organized as follows. Section 2 gives an overview of the original OLSR protocol. Section 3, presents our proposed node mobility degree. Section 4 presents performance metrics for evaluating performance of routing protocols. In Section 5, simulations and results are given. The last section concludes and presents some future works.

2.  Optimized Link State Routing Protocol

2.1.  Overview

The optimized link state routing (OLSR) protocol [1] is a proactive routing protocol that employs an efficient link state packet forwarding mechanism called multipoint relaying. This protocol optimizes the pure link state routing protocol. Optimizations are done in two ways: by reducing the size of the control packets and by reducing the number of links that are used for forwarding the link state packets. The reduction in the size of link state packets is made by declaring only a subset of the links in the link state updates. These subsets of links or neighbors that are designated for link state updates and are assigned the responsibility of packet forwarding are called multipoint relays. The optimization by the use of multipoint relaying facilitates periodic link state updates. The link state update mechanism does not generate any other control packet when a link breaks or when a link is newly added. The link state update optimization achieves higher efficiency when operating in highly dense networks. The Figure 1(a) shows the number of message transmissions required when the typical flooding-based approach is employed. In this case, the number of message transmissions is approximately equal to the number of nodes that constitute the network. The set consisting of nodes that are multipoint relays is referred to as MPRset. Each given node in the network selects an MPRset that processes and forwards every link state packet that this node originates (see Figure 1(b)). The neighbor nodes that do not belong to the MPRset process the link state packets originated by node P but do not forward them. Similarly, each node maintains a subset of neighbors called MPR selectors, which is nothing but the set of neighbors that have selected the node as a multipoint relay. A node forwards packets that are received from nodes belonging to its MPRSelector set. The members of both MPRset and MPRSelectors keep changing over time. The members of the MPRset of a node are selected in such a manner that every node in the node’s two-hop neighborhood has a bidirectional link with the node.

The selection of nodes that constitute the MPRset significantly affects the performance of OLSR because a node calculates routes to all destinations only through the members of its MPRset. Every node periodically broadcasts its MPRSelector set to nodes in its immediate neighborhood. In order to decide on the membership of the nodes in the MPRset, a node periodically sends Hello messages that contain the list of neighbors with which the node has bidirectional links and the list of neighbors whose transmissions were received in the recent past but with whom bidirectional links have not yet been confirmed. The nodes that receive this Hello packet update their own two-hop topology tables. The selection of multipoint relays is also indicated in the Hello packet. A data structure called neighbor table is used to store the list of neighbors, the two-hop neighbors, and the status of neighbor nodes. The neighbor nodes can be in one of the three possible link status states, that is, unidirectional, bidirectional, and multipoint relay. In order to remove the stale entries from the neighbor table, every entry has an associated timeout value, which, when expired, removes the table entry. Similarly a sequence number is attached with the MPRset which gets incremented with every new MPRset.

The MPRset need not be optimal, and during initialization of the network it may be same as the neighbor set. The smaller the number of nodes in the MPRset, the higher the efficiency of protocol compared to link state routing. Every node periodically originates topology control (TC) packets that contain topology information with which the routing table is updated. These TC packets contain the MPRSelector set of every node and are flooded throughout the network using the multipoint relaying mechanism. Every node in the network receives several such TC packets from different nodes, and by using the information contained in the TC packets, the topology table is built. A TC message may be originated by a node earlier than its regular period if there is a change in the MPRSelector set after the previous transmission and a minimal time has elapsed after that. An entry in the topology table contains a destination node which is the MPRSelector and a last-hop node to that destination, which is the node that originates the TC packet. Hence, the routing table maintains routes for all other nodes in the network.

2.2.  MPR Selection Algorithm

The computation of the MPR set with minimal size is a NP-complet problem [16]. For this end, the standard MPR selection algorithm currently used in the OLSR protocol implementations is as follows:

For a node x, let N(x) be the neighborhood of x. N(x) is the set of nodes which are in the range of x and share with x a bidirectional link. We denote by N2(x) the two-neighborhood of x, i.e, the set of nodes which are neighbors of at least one node of N(x) but that do not belong to N(x) (see Figure 2). 

Based on the above notations, the standard algorithm for MPR selection is defined as follows:

1)

2)

3)

a)

b)

4)

a)

b)

c)

5)

3.  Proposed Node Mobility Degree

Each node in a mobile ad-hoc network can be found in four states with its neighbor nodes: the node moves and its neighbors are static, the node is static and its neighbors move, the node and its neighbors move, the

node and its neighbors are static. Consequently, these four possible states result in a change of the link status of the node with its neighbors. So, as the nodes move in the mobile ad-hoc network, the link status changes in time.

Based on this observation, we define a mobility measure representing the degree of node mobility in the network. This mobility measure has no unit and don’t depend upon simulation artifacts such as mobility model parameters or movement patterns. Moreover its evaluation is done at discrete time intervals.

We define the mobility degree of a mobile node i at a time t by the following formula:

(1)

where:

: The number of nodes that joined the communication range of during the interval.

: The number of nodes that left the communication range of during the interval.

: The number of nodes in the communication range of at time t.

: The mobility coefficient between 0 and 1 defined in advance.

This node mobility degree is quantified locally and independently of the localization of a given node in the network. We represent this local and relative quantification by the change of the neighbors of each node. The node mobility degree at a given time t for node in the mobile ad-hoc network is defined as the change in its neighbors compared to the previous (state) at time. Thus, mobile nodes that join and/or leave the neighbors of node will surely have an impact on the evaluation of its mobility degree. Moreover, we have chosen the mobility coefficient between 0 and 1in order to have the node mobility degree at interval [0,1].

For illustration, let us take an example when node   is on the state shown in (Figure 3(a)) with 10 neighbors, and during interval, its neighbors will undergo the state changes shown in (Figure 3(b)): four nodes (with blue color) will leave the communication range, and two nodes (with red color) will join it. Consequently the node will be after (at time t) in the state (Figure 3(c)) with six changes. At the end of each time interval, the node will be able to make an evaluation of the change of its neighbors represented by this relative mobility, which is in our example equal to 13/40=32.5% (with).

Each node in the mobile ad-hoc network can make an autonomous and automatic evaluation of its mobility at regular time intervals (this evaluation can be periodically done while exchanging the Hello messages). Moreover the calculation and recalculation of the node mobility is

fast, and does not require enough consumption of resources (CPU and memory).

4.  Our Improvement

Mobility is a crucial problem in MANETs, and until now, the majority of routing protocols have shown some weaknesses to face a high mobility in some parts of the network. Our objective consists in positively using the mobility, in order to adapt and improve the performance of the OLSR protocol.

4.1.  Link Mobility Estimation

Some OLSR experiments [4,13] show that links must be more stable and less mobile to avoid fragile connections which involves data loss and frequent route changes. The OLSR protocol maintains constantly the shortest paths to reach all possible destinations in the network. So, it is more judicious to estimate the quality of links before adding them in the topological information that serves to calculate the best routes. The quality of a link can be estimated based on the power of the received signal. This information is provided by some wireless cards. If this information is not available, OLSR protocol estimates the link quality based on the number of control messages lost. A link failure can be detected using the timer expiry or by the link layer that informs upper layers of the failure with a neighbor node after reaching the maximal number of retries.

With an aim to estimate the quality of links in terms of mobility, we define the mobility of a link L between two nodes A and B as the average mobility of the involved nodes (see Figure 4), as showed in following equation:

(2)

This evaluation of the link mobility alone is not significant because we can have a normal value of the link mobility with a high mobility value of one of the involved nodes. The dependence between the mobility of nodes composing a link (in the network core) at the time t can be seen as mobility dependence of link L(A,B) as follows:

(3)

Therefore, a reliable symmetric link in terms of mobility can be seen as a link satisfying the two following conditions:

1) The average mobility of the link L(i,j) is lower than a threshold THRESHOLD_Link which depends on the characteristics of the wireless network (network density, network mobility, network scalability, network dimension, ...):

(4)

2) The mobility dependence of link L(i,j) is near to zero :

(5)

The choice of such a link satisfying these two conditions ensures the link to have a low mobility, with a strong dependence between the involved nodes.

4.2.  Proposed Mobility Criterions

In this section, we propose three new criterions for the operation of MPRs selection. The first criteria is direct because it selects as MPRs set, neighbor nodes with less mobility (Figure 5 (a)). Precisely the node selected as MPR node is a node where its mobility is the smallest (Equation 6). The two other criterions are based on the estimation of links quality between neighbors at one-hop and the neighbors at two-hop (Figure 5 (b)). The quality of the link in terms of mobility is given by the two conditions cited in the previous sub-section. So, the new selection of the MPR set is a compromise between the number of links towards the nodes at two-hops and its reliability in terms of mobility. The selection of a

neighbor as a MPR node can be viewed as an operation of maximization of the selection criteria. The second criteria suggested is based on sum (Equation (7)) and the third is based on the product (Equation (8)). The principal advantage of these three criterions is the facility on calculation and doesn’t require enough of resources in memory and CPU. Indeed, their evaluation is based on data base of neighbor nodes at one-hop and two-hop used by the OLSR protocol.

(6)

(7)

(8)

5.  Metrics of Performance

In this paper we have considered the most important metrics for analyzing and evaluating performance of MANET routing protocols during simulation. These considered metrics are:

Normalized Routing Overhead (NRL): It represents the ratio of the control packets number propagated by every node in the network to the data packets number received by the destination nodes. This metric reflect the efficiency of the implemented routing protocols in the network.

Packet Delivery Fraction (PDF): This is a total number of delivered data packets divided by total number of data packets transmitted by all nodes. This performance metric will give us an idea of how well the protocol is performing in terms of packet delivery by using different traffic models.

Average End-to-End delay (Avg-End-to-End): This is the average time delay for data packets from the source node to the destination node. This metric is calculated by subtracting ”time at which first packet was transmitted by source” from ”time at which first data packet arrived to destination”. This includes all possible delays caused by buffering during route discovery latency, queuing at the interface queue, retransmission delays at the MAC layer, propagation and transfer times.

6.  Simulations and Results

In this section we have compared the performance of the original OLSR protocol based on the MPR selection standard algorithm, and the two modified OLSR protocols related to the direct and product criterions: DIROLSR and PRD-OLSR protocols. In this study we have eliminated the sum criteria for his hard cost in terms of MPRs nodes number [18,19].

6.1.  Simulation Environment

For simulating the original OLSR protocol and the modified OLSR protocols related to our proposed criterions, we have used the OLSR protocol implementation [21] which runs in version 2.9 of Network Simulator NS2 [20] and uses the ad-hoc networking extensions provided by CMU, with a radio range of 250m.

We use a network consisting of 50 mobile nodes to simulate a high-density network. These nodes are randomly moved in an area of 1000m by 1000m according to the Random Waypoint (RWP) mobility model [22]. Moreover, to simulate a high dynamic environment (the worst case), we have consider the RWP mobility model with a pause time equal to 0. All simulations run for 300s.

A random distributed CBR (Constant Bit Rate) traffic model is used which allows every node in the network to be a potential traffic source and destination. The CBR packet size is fixed at 512 bytes. The application agent is sending at a rate of 10 packets per second whenever a connection is made. All peer to peer connections are started at times uniformly distributed between 5s and 290s seconds. The total number of connections and simulation time are 10 and 500s, respectively.

For each presented sample point, 50 random mobility scenarios are generated. The simulation results are thereafter statistically presented by the mean of the performance metrics. This reduces the chances that the observations are dominated by a certain scenario which favors one protocol over another. As we have interest in the case of high mobility (i.e. high link status and topology changes) we have reduced the HELLO interval and TC interval at 0.5s and 3s, respectively, for quick updates of the neighbors and topology data bases.

In particular, for the PRD-OLSR protocol related to the product criteria, we have choose THRESHOLD_Link= 0.05 as a threshold for evaluating the average mobility of links.

6.2.  Results and Discussion

To show how the modified version of the OLSR protocol is more adapted to the link status and topology changes comparing to the original OLSR protocol, we have made there performance comparison based on the three performance metrics cited in Section 5. Moreover, with the supposed configuration cited above, we have run simulations in different mobility levels by varying maximum speed of nodes between 0m/s (no mobility) to 50m/s (very high mobility) in steps of 10m/s. For given the same importance of mobile nodes leaving and joining the communication range at each node in the network we have choose the mobility coefficient equal to =1/2.

According to the Figure 6, the original OLSR, PRD-OLSR and DIR-OLSR protocols ensure in the whole the same packet delivery fraction for all maximum speeds. Indeed, it can be seen that the number of packets dropped along the path is quite similar for all maximum speed being approximately 42% at worst. Moreover, the ratio is worse for a continuously changing network (i.e. high maximum speed) than for the static path conditions, because the number of link failures grows along with the mobility. However, it is interesting to notice that even with static topology conditions, sending nodes do not achieve 100% packet delivery but only 81%-83%. This clearly shows the impact of the network congestion and packet interference as the load on the network increases.

Figure 7 shows that PRD-OLSR protocol ensures a good enhancement in terms of delay comparing to the DIR-OLSR and original OLSR protocols, where have globally the same delay for all maximum speeds. Precisely, the original OLSR protocol delay is around 2.7 seconds with higher mobility rate (maximum speed equal to 50m/s) and decreases to almost 1.2 seconds with static topology conditions. For DIR-OLSR protocol the delay gets more than twice as large being almost 2.65 sec for high mobility and surprisingly increasing to over 1.2 seconds when the mobility is decreased. For the intermediate speed (from 10m/s to 40m/s) al lightweight difference between them is found. This allows us to conclude that original OLSR and DIR-OLSR protocols ensures approximatively the same delay.

Unlike to the protocols above (i.e. original OLSR and DIR-OLSR protocols), the PRD-OLSR protocol delay is about 2.6s (enhancement by 0.05s and 0.1s comparing to DIR-OLSR and original OLSR, respectively) with high mobility, increasing to almost 0.9s-1.1s (unlike the DIR-OLSR and original OLSR protocols that their minimum delay is found at 1.2s) with lower maximum

speed. Moreover, this enhancement is more shown for all intermediate maximum speeds and particularly for the  two maximum speeds (10m/s and 30m/s). In short, we can say that the PRD-OLSR protocol is more adapted to all levels of mobility from 0m/s (no mobility) to 50m/s (very high mobility).

Figure 8 illustrates the normalized routing load (NRL) introduced into the network for the three versions of OLSR protocol, where the number of routing packets is normalized against sent data packets. A fairly stable normalized control message overhead would be a desirable property when considering the performance as it would indicate that the actual control overhead increases linearly with maximum speed of nodes due to the number of messages needed to establish and maintain connection. The OLSR protocol produces the lowest amount of NRL when compared to PRD-OLSR and DIR-OLSR protocols during all maximum speed values. Moreover, the PRD-OLSR protocol produces a lightweight routing load comparing to the DIR-OLSR protocol that produces more routing load. In the worst case (at the maximum speed value equal to 50m/s), the NRL increases to 5.5% for DIR-OLSR protocol, 4.8% for PRD-OLSR and 4.25% for the original OLSR. Precisely, comparing to the original OLSR protocol, the PRD-OLSR and DIR-OLSR protocols produce 12.94% and 29.41% routing packets, respectively. This explains that our two proposed criterions request more routing packets to establish and maintain routes in the network.

8.  Conclusions and Perspectives

This paper presents two versions of the original OLSR protocol, in the goal to adapt and enhance its performance to the dynamic nature of MANETs characterized by the link status and topology changes. These versions are based on a mobility degree that is quantified and evaluated in time by each mobile node in the network.

In the future works, we plan to continue this study by considering different configurations of MANETs for well understanding the behavior of each OLSR protocol version. Moreover, it is important to study the impact of the mobility coefficient (=1/2 in this work) by varying them into (0.00, 0.25, 0.75, 1.00). Finally, to implement an extension of the OLSR protocol supporting QoS, assuming that QoS requirements are expressed in terms of less mobility.

9.  References

[1]       T. Clausen and P. Jacquet ,“Optimized link state routing protocol (OLSR),” RFC 3626 Experimental, October 2003.

[2]       T. H. Clausen, G. Hansen, L. Christensen, and G. Behrmann, “The optimized link state routing protocol, evaluation through experiments and simulation,” In Proceedings of the IEEE Symposium on Wireless Personal Mobile Communications, September 2001.

[3]       F. Bai and A. Helmy, “A survey of mobility models in wireless ad hoc networks,” Wireless Ad Hoc and Sensor Networks, Chapter 1, Kluwer Academic Publishers, pp. 1-29, June 2004.

[4]       A. Laouiti, P. Muhlethaler, A. Najid, and E. Plakoo, “Simulation results of the OLSR routing protocol for wireless network,” 1st Mediterranean Ad-Hoc Networks Workshop (Med-Hoc-Net), Sardegna, Italy, 2002.

[5]       D. B. Johnson, D. A. Maltz, and Y. C. Hu. “The dynamic source routing protocol for mobile ad hoc networks (DSR),” Internet-Draft, Draft-Ietf-Manet-Dsr-10.txt, Work in Progress, July 2004.

[6]       C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (AODV) routing,” RFC 3561, Experimental, July 2003.

[7]       Y. Ge, T. Kunz, and L. Lamont, “Proactive QoS routing in ad-hoc networks,” The 2nd International Conference on Ad-Hoc Networks and Wireless, Montreal, Canada, October 2003.

[8]       T. Plesse, J. Lecomte, C. Adjih, M. Badel, et al., “OLSR performance measurement in a military mobile ad-hoc network,” Ad-Hoc Networks Journal Special Issue on Data Communication and Topology Control in Ad-Hoc Networks, October 2004.

[9]       T. Clausen, P. Jacquet, and L. Viennot, “Investigating the impact of partial topology in proactive MANET routing protocols,” The 5th International Symposium on Wireless Personal Multimedia Communications, 2002.

[10]    A. Tonnesen, “Implementing and extending the optimized link State Routing Protocol,” Master Thesis, Department of Informatics, University of Oslo, August 2004.

[11]    OOLSR, “Implementation of the OLSR, optimized link state routing protocol,” Hipercom Project, http://hipercom.inria.fr/oolsr/, November 2004.

[12]    V. Park and M. Corson, “Temporally-ordered routing algorithm (TORA): Version 1 functional specification,” Internet-Draft, IETF, Draft-Ietf-Manet-Tora-Spec-04.txt, July 2001.

[13]    A. Laouiti and C. Adjih, “Measures des performances du protocole OLSR,” IEEE SETIT2003 Tunisia, March 2003.

[14]    J. Haerri, C. Bonnet, and F. Filali, “OLSR and MPR: Mutual dependencies and performances,” In Proceedings of Med-Hoc Net 2005, June 2005.

[15]    A. Busson, N. Mitton, and E. Fleury, “Analysis of the multipoint relays selection in OLSR and implications,” In Proceedings of Med-Hoc Net 2005, June 2005.

[16]    Qayyum, L. Viennot, and A. Laouiti, “Multipoint relaying for flooding broadcast messages in mobile wireless networks,” in Proceedings of the Hawaii International Conference on System Sciences (HICSS’02), Big Island, Hawaii, January 2002.

[17]    S. Obilisetty, A. Jasti, and R. Pendse, “Link stability based enhancements to OLSR (LS-OLSR),” Vehicular Technology Conference, IEEE 62nd, pp. 28-25, September, 2005.

[18]    N. Enneya, A. Baayer, and M. Elkoutbi, “New criterion for MPR selection in OLSR protocol,” in Procceding of IASTED Wireless and Optical Communications, Monteral, Canada, pp. 416-421, May 30-June 1, 2007

[19]    N. Enneya, K. Oudidi, and M. Elkoutbi, “New mobility metrics for MPRs selection in the OLSR protocol,” 9th African Conference on Research in Computer Science and Applied Mathematics (CARI’08), Rabat, Morocco, October 27-30, 2008.

[20]    The VINT Project, “The network simulator ns-2,” http://www.isi.edu/nsnam/ns/, Page accessed on January 2008.

[21]    F. J. Ros, “UM-OLSR version 8.8.0,” University of Murcia, Spain, http://masimum.dif.um.es/?Software: UMOLSR, January 2008.

[22]    B. J. David and A. M. Daviv, “Dynamic source routing in ad hoc wireless networks,” in Mobile Computing. Kluwer Academic Publishers, pp. 153-181, 1996.

[23]    C. E. Perkins, E. M. Royer, S. R. Das, and M. K. Marina, “Performance comparison of two on-demand routing protocols for ad hoc networks,” IEEE Pers. Communication, Vol. 8, No. 1, pp 16-28, 2001.

[24]    B. J. Kawak, N. O. Song, and L. E. Miller, “A standard measure of mobility for evaluating mobile ad hoc network performance,” IEICE TRANSACTION COMMUNICATION, Vol. E86-B, No. 11, pp. 3236−3243, November 2003.