An Improved OLSR Protocol for Reducing the Routing Overhead in MANETs

Abstract

Manets consists of collection of nodes which can move freely. The communication in manet is done via a wireless media. Due to high mobility in manets, there exist frequent link breakages which lead to frequent path failures and route discoveries. Due to demanding real timjnie multimedia applications, quality of services (qos) support in such infrastructure less networks have become essential. Qos routing in mobile ad-hoc networks is challenging due to rapid change in network topology. The purpose of this paper is to provide a better quality of the package delivery rate and the throughput, that is in need of powerful routing protocol standards, which can guarantee delivering of the packages to destinations, and the throughput on a network. We focus on the inaccuracy of state information, more specifically the residual energy level of nodes that is collected by the control messages of olsr. Inaccurate information affects the efficiency of olsr protocol. We study some parameters of olsr that forces the inaccuracies in the energy level information of neighboring nodes and show the comparison between ideal and realistic version of olsr. Our study concluded that tuning of olsr improves the residual energy information of nodes and simulation results demonstrated a significant improvement in the criteria of package delivery rate and throughput.

Keywords

qos routing, optimized link state routing (OLSR), multi point relay (MPR), dynamic topology.

INTRODUCTION

Wireless technology is one of the most emerging technologies today. It provides ease of use and mobility to the users. Ad hoc networks are the branch of the wireless technology which provides facility to communicate with the other systems without using any fixed infrastructure. Each node has to perform as Sender, receiver as well as a relaying node which makes the system complex. Routing the data between the nodes is the most difficult part of the communication. Routing can be done by using the proactive as well as the reactive protocols.

Routing protocols in mobile ad hoc networks can be divided into two categories: table-based or proactive protocols and need-based protocols. The table-based or proactive protocols are used for periodic updating of the links; the route information is kept in a table and is used whenever they are needed. However, need-based protocols do not require keeping the routes data and whenever a route is needed, they start to explore a route based on the source location. Optimized Link State Routing (OLSR) is a table driven proactive routing protocol for MANET. A mobile ad hoc network (MANET) is a self-configuring wireless network of mobile hosts connected through arbitrary topology without the aid of any centralized administration. It is an optimization of link-state routing. In a classic link-state algorithm, link-state information is flooded throughout the network. OLSR uses this approach as Well, but the protocol runs in wireless multi-hop scenarios, the message flooding in OLSR is optimized to preserve bandwidth. The optimization is based on a technique called Multipoint Relaying. The nodes are free to move randomly and organize themselves arbitrarily and treating each mobile host as a router. In this all the nodes contain pre-computed route information about all the other nodes in the network. This information is exchanged by protocol messages after periodic time. OLSR performs hop-by-hop routing, where each node uses its most recent topology information for routing.

Each node selects a set of its neighbor nodes as MPRs (Multi point relays). Only nodes selected as MPRs are responsible for forwarding control traffic. MPRs are selected such that 2-hop neighbors must be reachable through at least one MPR node and OLSR provide shortest path routes to all destinations by providing link-State information for their MPR selectors. Nodes which have been selected as MPRs by some neighbor nodes announce this information periodically in their control messages. MPRs are used to form the route from starting Node to destination node in MANET. All this information is announces to neighboring MPRs through control messages. The purpose of selecting MPR is to reduce flooding overhead and provide optimal flooding distance. The Fig. 1 shows nodes and selection of MPRs for flooding of control messages.

We use the OLSR routing protocol [5] that is known as one of the best active and real-time protocol. In this protocol, all nodes constantly communicate with all destinations by exchanging the protocol messages periodically. Consequently, if there were a necessity in emergencies, they would have pre-computed routes and broadcast the topological changes to the other nodes. In this paper, we improved the OLSR routing protocol by eliminating the unnecessary loops, and simulation results shows a considerable improvement in the criteria of package delivery rate and throughput. The rest of the paper is organized as follows: section 2 describes the related work, section 3 clarifies the Routing protocols in Mobile Ad Hoc Networks and the proposed method (improving the OLSR protocol), and section 4 describes the OLSR efficiency and energy level accuracy and section 5 draws the simulation environment and explains about the parameter evaluation and results.

II.RELATED WORK

OLSR is a routing protocol for mobile ad hoc network that has been presented by the MANET working group in the IETF [6]. This protocol acts responsively. OLSR will harm by high variability that is caused by the topology and nature of the traffic. This suggests that, the service quality characteristics may be affecting the performance of OLSR protocol.

In [11], the nodes, based on their existing resources, are divided into three categories of service quality nodes, router nodes and receiver nodes. Nodes declare and report their characteristics to their neighbors by sending HELLO massages. Each node can specify the categories of its neighbors by receiving the HELLO message from them. Only the service quality nodes can participate in the service quality routing operation. The OLSR routing method is employed for routing. In [14] this is shown that, the OLSR has capability for the quality of routing. In [14] it is also proven that, the existence of more accurate frequent updating will cause positional information throughout the network. General Electronics Company and colleagues [12], create a model of OLSR protocol based on bandwidth of the status link in terms of service quality criteria. This protocol tries to find routes that have the highest bandwidths in bottlenecks. To provide a better service quality (i.e. to provide the route with optimum bandwidth), it is necessary to broadcast the bandwidth changes to calculate the best route with bandwidth correctly. The study that was carried out in [3] has been further developed in the research [6]. This research emphasizes studying the effect of MPR coverage parameters and TC redundancy adjustments on the OLSR performance. The above-mentioned research suggests that the delivery level will not be affected by overload that is caused by redundant promotional data. Both references [3, 6] emphasize having more detailed information on the network surface and about how it effects on the routing protocol performance. In other words, they study the impact of OLSR protocol parameters adjustment in terms of the network status (i.e. nodes and links) rather than the situational information of nodes and links.

Several robust protocols have been proposed in recent years besides the above optimization issues for broadcasting. [17] Proposes an AODV protocol with Directional Forward Routing (AODV-DFR) which takes the directional forwarding used in geographic routing into AODV protocol. While a route breaks, this protocol can automatically find the next-hop node for packet forwarding. [13] Proposes two deterministic timer-based broadcast schemes: Dynamic Reflector Broadcast (DRB) and Dynamic Connector-Connector Broadcast (DCCB). They pointed out that their schemes can achieve full reach ability over an idealistic lossless MAC layer, and for the situation of node failure and mobility, their schemes are robustness. [11] Proposes a Robust Broadcast Propagation (RBP) protocol to provide near-perfect reliability for flooding in wireless networks, and this protocol also has a good efficiency. They presented a new perspective for broadcasting: not to make a single broadcast more efficient but to make a single broadcast more reliable, which means by reducing the frequency of upper layer invoking flooding to improve the overall performance of flooding. In our protocol, we also set a deterministic rebroadcast delay, but the goal is to make the dissemination of neighbor knowledge much quicker. [4] Proposes Gossip-based ad hoc routing technique to reduce the routing protocol overhead. Every node forwards a message with some probability. In some executions, the gossip dies out quickly and hardly any node gets the message and other nodes get the message in the remaining executions. Gossiping is very useful in large networks and it is robust and able to tolerate faults. [9] Proposes, to discover the route better than broadcasting methodology rebroadcasting can be done with the help of neighbor knowledge methods. If a mobile node is positioned in the area closer to sender, then it has small additional coverage and rebroadcast from this node can reach less additional nodes, so its rebroadcast probability will be set lower. On the other hand, if a mobile node is located in the area far from sender, then the additional coverage from this node is large, its rebroadcast probability will be set higher. By using the distance between the sender and receiver, the coverage area is calculated and the distance can be calculated by signal strength or global positional system. This approach combines the advantages of probabilistic and area based approach. [19] Proposes the NCPR (Neighbor Coverage based Probabilistic Rebroadcast Protocol) protocol to reduce the routing overhead. The goal of this protocol is to make the quicker propagation of neighbor knowledge. The number of rebroadcasts should be limited in order to optimize the broadcasting. The routing overhead is very large in high dynamic networks.

III. IMPROVED OLSR

Routing in the suggested algorithm is based on routing is established upon demand. Each node has a routing table in which the node keeps its own routing information [17]. The routing table contains the fields such as the destination node address, the next node address, the sequence number, the distance, the minimum requested bandwidth, the maximum permitted delay, the stream type and the route validity period.

The Optimized Link State Routing (OLSR) protocol, developed by the French National Institute for Research in Computer Science and Control (INRIA), was developed for mobile ad-hoc networks. It operates in a table-driven and proactive manner, i.e., topology information is exchanged between the nodes on periodic basis. Its main objective is to minimize the control traffic by selecting a small number of nodes, known as Multi Point Relays (MPR) for flooding topological information. In route calculation, these MPR nodes are used to form an optimal route from a given node to any destination in the network. This routing protocol is particularly suited for a large and dense network. OLSR generally proposes four types of periodic control messages, namely:

 Hello messages

 Topology Control (TC) messages

 Multiple Interface Declaration (MID) messages

 Host and Network Association (HNA) messages

In our suggested method [18], when a node sends a package to other nodes within its own radio range, packages will be transmitted by nodes called MPR to the other nodes. Consequently, if the package falls into a loop, then two cases occur; (1) if the package used less number of steps (less than 255 steps) to reach the destination, and the package is IP Header, then we set dynamically its number of steps to zero to give the package the second chance to reach the destination, and (2) if the package used more number of steps (more than 255 steps), and the subjected package isn’t IP Header, then we eliminate the package, because, otherwise, many packages will remain in the network and this will cause network traffic, bandwidth occupation, high level of delay in the package delivery, and finally, the reduction of package delivery rate and network payload rate.

A. HELLO MESSAGE

Hello messages are periodically exchanged within the one-hop neighborhood to obtain the neighborhood information. Using this neighborhood information, each node in the network selects a subset of one-hop away neighbors known as the MPR set. In the MPR set, all two-hop away neighbors are reachable through any member of the MPR set. Hello messages are used for finding the information about the link status and the host’s neighbors. With the Hello message, the Multipoint Relay (MPR) Selector set is constructed which describes which neighbours has chosen this host to act as MPR and from this information the host can calculate its own set of the MPRs. The Hello messages are sent only one hop away but the TC messages are broadcasted throughout the entire network. TC messages are used for broadcasting information about its own advertised neighbours which includes at least the MPR Selector list. A HELLO-message contains:

i. A list of addresses of neighbors, to which there exists a symmetric link.

ii. A list of addresses of neighbors, which have been "heard".

iii. A list of neighbors, which have been selected as MPRs.

B. TOPOLOGY CONTROL (TC) MESSAGES

In order to build the topology information base needed, each node which has been selected as MPR, broadcasts Topology Control (TC) messages. TC messages are flooded to all nodes in the network and take advantage of MPRs. TC messages are generated and retransmitted for flooding topological information in the whole network only through MPR nodes. Also, MID (Multiple Interface Declaration) and HNA messages are relayed only by MPR nodes. Therefore, OLSR optimizes the control traffic overhead by minimizing the size of the MPR set. An MPR member generates and retransmits TC messages. These messages provide each node in the network with sufficient link-state information to allow route calculation.

C. MULTIPLE INTERFACE DECLARATION (MID) MESSAGES

MID messages are generated by an OLSR node with multiple OLSR interfaces to notify other OLSR nodes about its interfaces participating in the OLSR routing domain. There is also Multiple Interface Declaration (MID) messages which are used for informing other host that the announcing host can have multiple OLSR interface addresses. The MID message is broadcasted throughout the entire network only by MPRs.

D. HOST AND NETWORK ASSOCIATION (HNA) MESSAGE

There is also a “Host and Network Association” (HNA) message which provides the external routing information by giving the possibility for routing to the external addresses. The HNA message provides information about the network- and the net mask addresses, so that OLSR host can consider that the announcing host can act as a gateway to the announcing set of addresses. The HNA is considered as a generalized version of the TC message with only difference that the TC message can inform about route canceling while HNA message information is removed only after expiration time.

E. SHORTEST PATH ROUTING

The general principle of this algorithm [5] is at step i to look for the shortest path Pi to the destination d. Then the edges in Pi or pointing to Pi have their cost increased in order to prevent the next steps to use similar path. fp is used to increase costs of arcs belonging to the previously path Pi (or which opposite arcs belong to it). This encourages future paths to use different arcs but not different vertices. fe is used to increase costs of the arcs who lead to vertices of the previous path Pi. We can choose different fp and fe to get link-disjoint path or node-disjoint routes as necessary.

In Fig. 2, Dijkstra(G,n) is the standard Dijkstra’s algorithm which provides the source tree of shortest paths from vertex n in graph G; GetPath(S,T,d) is the function that extracts the shortest-path to n from the source tree ST; Reverse(e) gives the opposite edge of e ; Head(e) provides the vertex edge e points to.

The simulation result of the algorithm is the scenario of 300 nodes. As shown in the figure, by using the Multipath Dijkstra’s Algorithm, we can get three node-disjoint routes. When the number of routes required comes to ten, we get ten optimal routes (some nodes might be shared when node-disjoint routes are unavailable) according to the cost Functions. In this article, only three or four routes are used.

IV. OLSR EFFICIENCY & ENERGY LEVEL ACCURACY

Here we will see the performance changes in OLSR and how performance depends on residual energy of nodes. Some of the factors on which OLSR efficiency vary are discussed in this section. We have various MPR selection techniques and path determination algorithms available. In Modified Routing, original MPR selection criteria are combined with new path determination algorithm. And in a other variation Modified MPR/Routing new MPR selection and the new path determination algorithm are combined. These variations affect performance of OLSR a lot. Also we can vary the protocol on the basis of “How old the information about Residual energy” is. In one we use the residual energy at that time when MPR was selected, is Ideal version. In realistic version, data about residual energy collected by protocol message exchange. Also change in topology impact the number of packets delivered and accuracy of the residual energy level. Packet latency also affect accuracy of data collected. Comparing the performance of ideal and realistic version of OLSR under different traffic rate. We are comparing the performance of network in terms of packet delivered with respect to variation in packet interval time. As Packet interval time decreases (X-Axis), no more packets are delivered and more recent information about residual energy is collected by nodes in MANET. So inaccuracy is less and system performance increases. This is true in both ideal and realistic approach, as packet interval time decreases performances increases. But when we compare ideal with realistic, Ideal outperforms realistic for every piece of data. It means it is sufficient to collect residual energy information at the time when MPR was selected.

V. SIMULATION PLATFORM AND MODELS

The performance of Optimized Link State Routing protocol was evaluated by using experimental and simulation results. The experiments are carried out in Jist/SWANS simulator using selected simulation time. When there was a comparison between experimental and simulation results for the same set of parameters, no packet loss was observed. But packet loss was observed when the simulation time or number of nodes is increased. When the simulation ran, we count the number of packets, which are gone through and received by each node. We also assessed its delay and delivery of the received packets. This information is included in the data files.

The first performance metric we would like to measure is the Packet Delivery Ratio (PDR). It is calculated using the formula:

PDR= (Total Number of Received Packet / Total Number of Sent Packet) * 100

The second performance metric we would like to measure is the packet transmission Delay. It is calculated using the formula:

Delay= (Packet Received Time- Packet Sent Time)

The third performance metric is Throughput. Throughput is defined as the amount of broadcast data (bits) transmitted during a second in the MANET. The throughput (X) is calculated by using the following formula:

X = C / T

Where X is the throughput, C is the number of requests that are accomplished by the system, and T denotes the total time of system observation.

Standard OLSR: At first glance, it may seem strange that a network with a node transmission range of 200 M has the highest overhead. Intuitively, the denser the network is, the higher the overhead: for the same number of nodes and area size, the network contains more edges if the transmission range of a node is higher (see Table 1). However, the result can be explained as follows: in general, the more MPRs are selected, the higher the overhead. In a higher density network (such as for a node transmission range of 300 M), node connectivity is also high, so a node may need fewer MPRs to cover its 2-hop neighbors. On the contrary, in lower density networks (such as for a node transmission range of 100 M), because of the lower connectivity, a node may have fewer 2-hop neighbors, therefore it also needs less MPRs. However, the transmission range of 200 M falls within these two extremes, so it may well result in the largest number of MPRs to produce the highest overhead. This situation is not found in the Pure Link State Algorithm, where a node’s entire neighbor set is its MPR set. So the denser the network is, the more neighbors/MPRs a node have, resulting in a higher overhead.

VI. CONCLUSION

In MANET, the state information such as residual energy level plays an important role in route selection. If latest information is not collected by nodes then performance may degrade. We also evaluated the effect of time at which state information was collected in ideal and realistic approach. And concluded that although ideal approach is better than realistic but increase in frequency of packets improve the performance very little and also increase traffic overhead. As a solution we used prediction mechanism and smart prediction mechanism which performs better than EOLSR (Enhanced Optimized Link State Routing) protocol and reduce traffic load. Also we cannot calculate 100 % accurate state information as topology changes very frequently but we can maximize it by using some other technique also that may be even better than the prediction mechanism.

The reason for this improvement is that, instead of eliminating all of the packages that fell into the loop, we gave theses package, by setting conditions, the second chance to reach the destination and consequently, in this case, more packages reached to the destination and finally, the package delivery rate and the throughput is improved by about 20 percent in comparison with the conventional OLSR.

Tables at a glance

Table 1 Table 2

Figures at a glance

Figure 1 Figure 2

References

1. J.D. Abdulai, M. Ould-Khaoua, L.M. Mackenzie, and A. Mohammed, “Neighbour Coverage: A Dynamic Probabilistic Route Discovery for Mobile Ad Hoc Networks,” Proc. Int’l Symp. Performance Evaluation of Computer and Telecomm. Systems (SPECTS ’08), pp. 165-172, 2008.
2. T. Clausen, P. Jacquet, “Optimized link state routing protocol”, IETF RFC3626, 2003.
3. T. Clausen, P. Jacquet, L. Viennot, “Investigating the impact of partial topology in proactive MANET routing protocols”, in Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications, vol. 3, October 2002, pp. 1374–1378.
4. Z. Haas, J.Y. Halpern, and L. Li, “Gossip-Based Ad Hoc Routing,” Proc. IEEE INFOCOM, vol. 21, pp. 1707-1716, 2002.
5. Ivascu G. L., Pierre S., Quintero A., "Qos Support based on a Mobile Routing Backbone for Ad Hoc Wireless Networks", IWCMC, Canada, July 2006
6. D. Johnson, Y. Hu, and D. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) for IPv4”, IETF RFC 4728, vol. 15, pp. 153-181, 2007.
7. Keshavarz-Haddady, V. Ribeirox, and R. Riedi, “DRB and DCCB: Efficient and Robust Dynamic Broadcast for Ad Hoc and Sensor Networks,” Proc. IEEE Comm. Soc. Conf. Sensor, Mesh, and Ad Hoc Comm. and Networks (SECON ’07), pp. 253-262, 2007.
8. J. Kim, Q. Zhang, and D.P. Agrawal, “Probabilistic Broadcasting Based on Coverage Area and Neighbor Confirmation in Mobile Ad Hoc Networks,” Proc. IEEE GlobeCom, 2004.
9. Y. Ge, T. Kunz, L. Lamont, “Proactive QoS routing in ad-hoc networks”, in Proceedings of the 2nd International Conference on Ad-Hoc Networks and Wireless, Montreal, Canada, October 2003.
10. S. Mahfoudh, P. Minet, “EOLSR: an energy efficient routing protocol in wireless ad hoc sensor networks”, Journal of Interconnection Networks 9 (4) (2008) 389–408.
11. F. Stann, J. Heidemann, R. Shroff, and M.Z.Murtaza, “RBP: Robust Broadcast Propagation in Wireless Networks,” Proc. Int’l Conf. Embedded Networked Sensor Systems (SenSys ’06), pp. 85-98, 2006.
12. Li Tingjun ―Study On Airborne Single passive location Technologyǁ Applied Mechanics and Materials Vols.58（2011) pp2006-2009.
13. Li Tingjun ―The Phonetic Complex Data Based on FPGA Key Engineering Materialsǁ, Vols 475(2011), pp1156-1160.
14. Li Tingjun, Lin Xueyuan, GPS/SINS Integrated Navigation System Based on Multi-Scale Preprocessingǁ, Journal of Wuhan University, 2011, Vols 36(1): pp6-9.
15. P.E. Villanueva-Pena, T. Kunz, P. Dhakal, “Extending network knowledge: making OLSR a quality of service conductive protocol”, in Proceedings of the International Conference on Communications and Mobile Computing, Vancouver, Canada, July2006, pp. 103–108.
16. B. Williams and T. Camp, “Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks”, Proc. ACM MobiHoc, pp. 194- 205, 2002.
17. Shahram Behzad, Reza Fotohi, Shahram Jamali “Improvement over the OLSR Routing Protocol in Mobile Ad Hoc Networks by Eliminating the Unnecessary Loops” I.J. Information Technology and Computer Science, 2013, 06, 16-22 Published Online May 2013 in MECS (http://www.mecs-press.org/)DOI: 0.5815/ijitcs.2013.06.03
18. Xin Ming Zhang, En Bo Wang, Jing Xia, and Dan Keun Sung.”.A Neighbor Coverage based Probabilistic Rebroadcast for Reducing Routing Overhead in Mobile Ad hoc Networks”, 2012.
19. Dharam Vir, 1 Dr. S.K.Agarwal, 2 Dr. S.A.Imam3 “Power Management in Optimized Link State Routing (OLSR) Protocol”, International Journal of Modern Engineering Research (IJMER) www.ijmer.com, Vol.3, Issue.1, Jan-Feb. 2013 pp-275-283, ISSN: 2249-6645.
20. Padmavathi.K, Thivaharan.S “A SURVEY ON REDUCING ROUTING OVERHEAD IN MOBILE AD HOC NETWORKS”, International Journal of Advanced Computing, Engineering and Application( IJACEA), ISSN: 2319-281X, Vol. 2, No. 5, October 2013.