1 Introduction

A mobile ad hoc network (MANET) [1] is characterised by a set of mobile nodes communicating using wireless channels. The flexibility and ease of communication provided by MANETs has led to their widespread use specifically in communication sector. Since the exchange of information in MANETs is based on finding routes between the sender and receiver, an ideal routing protocol should find optimal and loop free routes quickly. However, the issues like node mobility, limited computation power, and wireless link characteristics that are inherent to MANETs cause route breakage and makes routing a challenging task [2].

There exist several methods of routing in MANETs [3]. These can be classified into three broad categories-proactive, reactive and hybrid routing protocols. The proactive protocols like DSDV [4] and OLSR [5] follow table driven approach in which information about network topology is stored at every node in the form of topology tables. These tables are periodically refreshed so that any changes due to node mobility are accommodated and the current view of topology is maintained. The reactive protocols like AODV [6] and TORA [7] follow on demand routing. Topology tables are not maintained in these protocols, and routes are fetched by using connection establishment between source and destination on the fly. The hybrid routing protocols like ZRP [8] incorporate the benefits of both, reactive and proactive routing to establish routes.

Most of these algorithms make the best effort to generate routes. Because of the flexibility and ease of deployment, the use of MANETs has been growing exponentially in applications like remote surveillance, environmental or wildlife monitoring, rescue operations, tele medicine in adverse environments, collaborative unmanned remote exploration, Internet of Things (IoT), etc. Real time applications like IoT impart an idea of designing an integrated and automated world by interconnecting several devices that work in coordination. Such applications are sensitive to bandwidth and delay constraints and have minimal tolerance for network disruptions. Therefore it becomes necessary for these applications to achieve determinism in their performance to be of practical use. In order to accommodate the rising expectations for guaranteed performance, the trend in communication technology has been shifting from best effort service to providing service guarantees, in terms of Quality of Service (QoS). The QoS attempts to shape the network parameters in order to achieve deterministic behaviour so that users can benefit by demanding services as per requirements of their applications. The performance can be measured in terms of different metrics like bandwidth availability, delay, etc. depending upon the requirement. Despite of the uncertain behaviour of MANETs, various QoS solutions exist. These have been designed even for applications deployed in challenging environments like deep sea monitoring and telecommunications to ensure certainty in their performance [9].

The paper addresses QoS provisioning in routing for MANETs and is organised as follows. Section 2 discusses existing QoS solutions. Then a novel heuristic based on OLSR routing protocol is proposed in Sect. 3. Further in Sect. 4, the performance of proposed heuristic is compared with the standard protocol by using computer simulations. Two variations of A-OLSR are also introduced and are compared to analyse performance. Simulation results for comparison between OLSR and another QoS based routing protocol called AOMDV are also stated. Section 5 contains the proof that A-OLSR is indeed optimal for scalable architectures. Finally, Sect. 6 presents the conclusions.

2 Related Work

Quality of Service aims to align the services of network according to the user requirements. Despite of the challenges posed due to the uncertain nature of MANETs, several QoS mechanisms exist in literature.

Ideas from evolutionary techniques have been used to serve the basis of QoS in routing. In [10], the authors present an ant colony algorithm (ACA) to address the problem of multicast routing. ACA avoids congestion of the network’s traffic load by achieving appropriate balance by applying constraints on the network QoS parameters. In [11], Lu et al. discuss a genetic algorithm for conserving the energy at every node to prolong the life of network. This is achieved by balancing the energy consumption load between the nodes and optimizing the size of control headers, reducing the transmission of control messages, etc. The authors in [12] bridge the gap between Qos sustainability to provide sub optimal solutions using genetic algorithms and clustering techniques. Clustering techniques have also been used to find optimal routes for exchanging information in networks. In [13], the authors discuss a SBHC technique involving three different stages of clustering formation, software-based clustering, and heuristic clustered routing protocol to improve the network performance by using quality of service parameters. The authors in [14] discuss an algorithm to overcome the challenge of supporting transmission of multiple video streams with appropriate QoS over ad hoc networks by using video coding techniques that provide multiple routing paths.

QoS can be introduced in several ways across the layers of network protocol stack. Most of the work has attempted to incorporate QoS parameters at the MAC layer or at the network layer. Adapting QoS at MAC layer involves monitoring and managing the network resources for efficient utilisation by providing traffic prioritisation, service differentiation, link adaptation or bandwidth reservation. Several protocols have been designed to tailor the specific needs of applications like bottleneck bandwidth, and delay constraints [15]. The algorithm discussed in [16] assigns priorities to nodes dynamically based on the role performed by the node (packet forwarding node, source or receiver) and the type of traffic: real time or non real time. By differentiating between these traffic classes, the protocol provides fairness among flows and achieves better network metrics like low delay and high throughput. The protocol in [17] adapts to various traffic classes and reduces energy consumption, while obeying the QoS constraints. A thorough survey of QoS based MAC layer protocols is provided in [18].

At network layer, QoS provisioning aims to find routes between the sender and receiver that either explicitly satisfy user QoS requests, or implicitly improve the existing network performance. Routing in wireless scenario is far more challenging as the traditional IP routing cannot be used because it is based on infrastructure networks. In case of wireless networks, managing bandwidth utilisation, conserving energy while prolonging the network lifetime becomes a concern because of the limited computation and processing power of the nodes. Thus, designing QoS enabled routing protocols for wireless sensor networks is still a vastly unexplored area of research. The paper [19] presents a detailed classification of various QoS enabled routing protocols. The protocols have been classified based on their architecture (flat/hierarchical), location awareness, multipath capability, etc. AOMDV [20] is a multipath protocol that deals with networks that are highly mobile and prone to link failures. Like in AODV [6], loops are avoided by using sequence numbers. However, AOMDV finds multiple loop free and link disjoint routes between the source and destination pairs in order to increase the fault tolerance and improve performance in case of link failures. The authors in [21], use fuzzy logic to improve the performance of AODV in order to scale the algorithm for larger networks. Kuppusamy et al. [22] compares the performance of AODV, OLSR and TORA to show that OLSR has higher PDR, lower routing overhead and lesser delay in comparison to TORA and AODV protocols for different mobility scenarios. This improved performance is credited to the selection of MPR sets which diffuse control information throughout the network. Leguay et al. [23] proposed modifications in OLSR to support different traffic classes by creating a reliable broadcast mechanism and modifying link announcements. The work [24] discusses variations in MPR selection criteria for improving the network parameters by finding better routes as compared to OLSR for static networks.

The cross layer designs for QoS routing aim at establishing routes by coordinating the use of available resources at different layers of the protocol stack. Routing in cognitive radio adhoc networks (CRAHN) is provided by using opportunistic transmissions. The authors in [25] design a cross layered opportunistic routing protocol for CRAHN by including physical layers spectrum sensing, MAC layers opportunistic link discovery and network layers opportunistic data transmission. The optimum path through opportunistic link discovery is formed with the availability of the maximum spectrum opportunity (SOP) at each hop with the best probability of delivery. This enhances the overall performance of the network. The paper [23] discusses a modified mechanism of OLSR to create a reliable broadcast structure and employ link announcements using parameters from network layer and MAC layer.

From the above discussion it has been observed that OLSR is a widely used protocol for routing. Several works focus on improving the MPR selection criteria to accommodate QoS parameters. Authors in [26] discuss a variation of OLSR called QOLSR, which aims at finding routes of minimum delay by integrating bandwidth and delay parameters in MPR selection criteria. In [27], the performance of OLSR has been improved by using clustering. [28] proposes On-Demand Multicast Routing Protocol (ODMRP) which selects a mesh topology based MPRs which are classified according to their enhancement in routing mechanism. The MPR selection in OLSR is based on covering two-hop neighbours. However, increasing the degree of coverage can improve the network performance which is used as the basis of our proposed work, A-OLSR.

3 Proposed Work: A-OLSR

OLSR [5] is a link state routing protocol. Because it is also proactive, the routes are readily available. Moreover, OLSR obtains optimisation over classical link state protocols in two ways. First it minimises the control overhead by transmitting information about only a subset of nodes called the Multi-Point Relay’s (MPRs), rather than flooding information about the entire neighbourhood. Second, only the MPR set is used to broadcast information instead of using blind flooding like in link state protocols. OLSR is based on RFC 3626 [5], which provides it’s detailed description and operation. It is also widely accepted because of it’s adaptive yet stable nature. The nodes in MPR set are used for transmitting the control information in network and for establishing routes.

The standard protocol works by including those nodes in the MPR which provide coverage to the two-hop neighbours. In this work, we have introduced A-OLSR which tries to improve the MPR selection criteria by including coverage to the three-hop neighbourhood. Such an MPR set would imply better coverage and connectivity of the network. Some amount of redundancy is introduced in the MPR sets as the selected nodes would also cover the two-hop neighbourhood. This redundancy helps to provide more stable routes which can improve performance even in the case of highly mobile networks. Thus, A-OLSR not only retains the benefits of OLSR, but also integrates QoS by improving connectivity of the network and introducing redundancy for reliable delivery.

First, the standard MPR computation of OLSR is discussed and then the proposed modifications are presented.

The standard-OLSR MPR selection criteria is as follows:

For every node of the network, MPR selection uses information about one-hop neighbourhood (N1(x)), and two-hop neighbourhood (N2(x)) of that node. D(y) represents the count of symmetric neighbors of a node y and is called degree of node y (y is a member of N1).

MPR set computation

  1. 1.

    Initially the MPR set is empty.

  2. 2.

    Compute D(y).

  3. 3.

    The nodes in N1 which form the only route to nodes in N2 are added to the MPR.

  4. 4.

    Remove the nodes from N2 which are now covered by a node in the MPR set. This gives the set of uncovered two-hop neighbours.

  5. 5.

    While the set of uncovered two-hop neighbours is not NULL:

    1. (a)

      For each node in N1, calculate the number of reachable nodes in the set of uncovered two-hop neighbours.

    2. (b)

      Add that node to the MPR set which has the maximum count in previous step. In case of a tie, select the node as MPR whose D(y) is greater.

The A-OLSR MPR selection criteria is as follows:

For every node x in the network, A-OLSR’s MPR selection uses information about the one-hop neighbourhood (N1(x)), two-hop neighbourhood (N2(x)), and three-hop neighbourhood (N3(x)) of that node. D(y) is the degree of a 1-hop neighbour node y as in case of OLSR protocol.

MPR set computation

  1. 1.

    Initially the MPR set is empty.

  2. 2.

    Compute D(y).

  3. 3.

    Add to the MPR set those nodes in N1, which are the only nodes to provide reachability to a node in N3.

  4. 4.

    Remove the nodes from N3 which are now covered by a node in the MPR set. This gives the set of uncovered three-hop neighbours.

  5. 5.

    While the set of uncovered three-hop neighbours is not NULL:

    1. (a)

      For each node in N1, calculate the number of reachable nodes in the set of uncovered three-hop neighbours.

    2. (b)

      Add that node to the MPR set which has the maximum count in previous step. In case of a tie, select the node as MPR whose D(y) is greater.

Fig. 1
figure 1

MPR selection

Full size image

In the above algorithm for A-OLSR’s MPR selection, point (2) reflects addition of those nodes in MPR set that can cover the three-hop neighbourhood. Intuitively, this MPR set should also cover some of the two-hop neighbours. Point (4) ensures complete coverage of the three-hop neighbourhood. Since the three-hop neighbours would be connected through some intermediate two-hop neighbours, the MPR set obtained at the end of this algorithm includes those one-hop neighbours that provide coverage to both, three-hop and two-hop neighbourhood. This is expected to improve the network performance.

The operation of A-OLSR can be better understood with the help of Fig. 1. Consider the network in Fig. 1a. The blue nodes represent the one-hop neighbours of X. Green nodes are the two-hop neighbours of X and yellow nodes are the three-hop neighbours. Bi-directional links are indicated with a simple line while, unidirectional links are indicated with an arrow.

Consider the MPR selection criteria of standard OLSR for the network diagram in Fig. 1a. As shown in Fig. 1b, the MPR set consists of those nodes that can provide coverage to the two-hop neighbourhood. Since nodes {1,2,3} are connected to X with bi-symmetric links, provide complete coverage to the two-hop neighbourhood and have the maximum degree, therefore they form the MPR set for X.

Now consider the MPR selection criteria of A-OLSR for the same network in Fig. 1a.

  • In the first step (Fig. 1c), those one-hop neighbours which are the only nodes to provide coverage to three-hop neighbours are added to the set. This implies that the MPR set now consists of nodes {1,2} since they cover the three-hop neighbours of X through symmetric links of 2-hop neighbours {3,4,5}. Note that the MPR set selected in this step {1,2} also covers the two-hop neighbours {3,4,5,6}.

  • In this step, complete coverage of two-hop neighbourhood of node X is ensured. As shown in Fig. 1d, node {8} is included to the MPR set so that the entire two-hop neighbourhood gets covered.

  • The MPR set consists of nodes {1,2,8}.

However the redundancy introduced provides greater degree of coverage and some amount of fault tolerance. The simulation results of various metrics are presented in the next section.

4 Results and Discussion

4.1 Simulation Network Scenario

The performance of A-OLSR is analysed by extensive simulations using Network Simulator (NS-2.35) [29]. NS is widely used by the research community for both wired and wireless simulations. It has inbuilt functions for most of the MAC layer and Network layer protocols. For implementing A-OLSR, first the OLSR patch for NS-2.35 is integrated with the NS module and then necessary modifications are accommodated for A-OLSR. The parameters used for implementing A-OLSR are specified in Table 1.

Table 1 Parameters used in simulation
Full size table

The nodes are deployed in an area of (\(600 \times 600\))m. To generate mobility, nodes pick random destinations after fixed intervals of time and move towards their chosen destinations at a speed of 15 m/s. The traffic generating source is Constant Bit Rate (CBR) traffic which uses UDP agents. The number of nodes are varied by passing it as an argument inline.

In order to analyse the improvement achieved in QoS support capability by using A-OLSR, two network scenarios are considered. The first scenario (Scenario-1) represents a low traffic and low mobility network. The second scenario (Scenario-2) depicts the case of a high traffic and high mobility network. The results of A-OLSR and standard best effort OLSR are compared for both network scenarios in terms of Normalised Routing Load (NRL), Packet Delivery Ratio (PDR), Throughput, Average Energy Consumption per node and End-to-End Delay (E2E-Delay) with varying Number of Nodes (nn). The metrics are plotted against number of nodes in order to understand scalability of the algorithm. These network metrics are chosen as they reflect a realistic measure of quality of network. Also, the performance A-OLSR is compared with the extended versions which cover four-hop and five-hop neighbours. To further evaluate the reliability of A-OLSR, it has been compared with AOMDV [20], a protocol that offers multiple disjoint paths to provide QoS routing (Table 2).

4.2 Simulation Results

4.2.1 Analysis of A-OLSR and OLSR

The following figures show the relative performance of A-OLSR and OLSR routing protocols. For each simulation, the Number of Nodes (nn) are varied till 100 and the results for low traffic, low mobility and high traffic, high mobility scenarios are plotted.

Figure 2 represents the Normalized Routing Load (NRL) for the two scenarios. As evident from the graphs, average NRL for two protocols is roughly the same. This implies that A-OLSR does not introduce any additional routing overhead to OLSR.

Fig. 2
figure 2

Normalised routing load

Full size image

Figure 3a depicts the PDR in case of low traffic and low mobility environment. The results of both protocols are comparable as they compute similar routes. The similarity of route computation is accounted to sparsity of links and stability of routes due to reduced mobility. The significance of including three-hop neighbourhood coverage by the MPRs becomes more pronounced as the mobility of nodes and density of links is increased. This is evident from Fig. 3b. In this case, A-OLSR selects routes which provide better coverage and connectivity. A-OLSR ensures deterministic delivery upto three hops of the sender which accounts for the higher PDR. This also leads to higher throughput for A-OLSR as shown in Fig. 4.

Fig. 3
figure 3

PDR

Full size image
Fig. 4
figure 4

Throughput

Full size image

The graphs in Fig. 5 represent Average Energy Consumed per node. The energy consumption for both routing protocols in low traffic and low mobility scenario is almost similar. However, as traffic and mobility is increased, the graph in Fig. 5b shows that energy consumption for A-OLSR is comparatively lower to OLSR. Energy is consumed in transmission and reception of packets, besides route computation which involves packet processing. Lesser energy consumption is attributed to reduced routing calculations at nodes. A noteworthy point for energy calculations is that in case of both protocols, the energy is consumed by nodes uniformly. Nodes running out of energy non-uniformly can create energy holes in the network and lead to route breakage as nodes with zero energy cannot receive, transmit or process packets. Since in OLSR energy holes are not formed, it inherently elongates the life of network.

Fig. 5
figure 5

Energy

Full size image

The graph for Delay in Fig. 6 shows that A-OLSR has lower average delay. This is because the routes selected by A-OLSR are better as the probability of selecting shorter routes increases due to improved connectivity.

Fig. 6
figure 6

Delay

Full size image

Table 3 summarises the results from previous section.

Table 2 Results of simulations
Full size table

Observations for A-OLSR from the implementation and simulation results are as follows

  • A-OLSR does not introduce any additional routing overhead to OLSR. Moreover it obtains optimization over OLSR by introducing coverage to three-hop neighbours which leads to better route selection.

  • In case of low mobility and low traffic networks, the values for PDR and throughput are comparable for OLSR and A-OLSR because of less mobility of nodes and reduced route breakage.

  • In highly dense and mobile environment, A-OLSR gives higher PDR and throughput as compared to OLSR. This is because the MPR set of A-OLSR selects better routes which are more stable by including three-hop neighbours.

  • The performance of A-OLSR is better than OLSR in terms of end to end delay and energy consumption in case of low mobility and low traffic networks. When the nodes are less mobile and network traffic is low, the routes formed by A-OLSR are shorter. The energy consumption is less due to reduced route computation overhead.

  • In highly dense and mobile environments, A-OLSR has relatively low end to end delay and energy consumption as compared to OLSR. Since A-OLSR converges to shorter routes by considering reachability upto three-hop neighbours, it reduces the average end to end delay. The routes so established are more stable which reduces the energy consumption at every node.

4.2.2 Analysis of A-OLSR and It’s Variants

The results of previous section have established that A-OLSR outperforms OLSR for multiple network metrics. This enhancement in performance is credited to the modified MPR selection criteria whereby the MPR set for every node is constructed by including the one-hop neighbours that cover it’s three-hop neighbourhood. In order to verify the optimality of MPR selection criteria used in A-OLSR, simulations have been carried out with it’s extended versions, A\('\)-OLSR and A\(''\)-OLSR. In case of A\('\)-OLSR, MPR set is constructed by including one-hop neighbours that cover a node’s four-hop neighbourhood. Similarly, in case of A\(''\)-OLSR coverage of five-hop neighbourhood is considered. The comparison has been drawn for both scenarios- low traffic, low mobility and high traffic, high mobility.

Figure 7 represents the Normalized Routing Load (NRL) for the two scenarios. As evident from the graphs, the NRL for A\('\)-OLSR and A\(''\)-OLSR is higher as compared to A-OLSR. The increase in NRL signifies the overhead of communicating control messages between the nodes in order to ensure reachability beyond two-hop neighbours.

Fig. 7
figure 7

Normalised routing load

Full size image

Figure 8 depicts the comparison of PDR. As it can be observed from the graphs, packet delivery ratio drops for A\('\)-OLSR and A\(''\)-OLSR in both scenarios. This is because the routes so formed are unreliable and prone to breaking. Intuitively, ensuring coverage of four-hop or five-hop neighbours is a difficult task due to the dynamic nature of MANETs. Even if the candidate MPRs are selected to ensure coverage, the network topology might change after the routes are selected and before the actual transmission of data takes place. This is because a node as far as the fourth hop neighbour might walk out of the communication range and hence break the route. The probability of such behaviour is less while ensuring coverage upto three-hop neighbours as the routes are established quickly and the transmissions begins soon after. The same reason holds for the lower values of throughput in Fig. 9.

Fig. 8
figure 8

PDR

Full size image
Fig. 9
figure 9

Throughput

Full size image

The graphs in Fig. 10 represent Average Energy Consumed per node. The energy consumption increases for A\('\)-OLSR and A\(''\)-OLSR. This is attributed to the increased computation overhead incurred for calculating routes in these protocols. High energy consumption for finding routes eventually drains out the energy from nodes and the overall lifetime of the network also reduces.

Fig. 10
figure 10

Energy

Full size image

The graph for Delay in Fig. 11 shows a significant increase in the delay for A\('\)-OLSR and A\(''\)-OLSR. The increased delay is caused because route computation consumes significant time and the routes so established are prone to breaking which further introduces delays.

Fig. 11
figure 11

Delay

Full size image

The above analysis show that providing coverage to four-hop and five-hop neighbourhood is a computationally intensive task and introduces a high routing overhead. Moreover, the routes so established are not reliable which is understood from the low values of PDR and throughput. Therefore, it is established that selection of MPRs based on the criteria for providing coverage to three-hop neighbours is the optimal choice.

4.2.3 Analysis of A-OLSR and Other Protocols

In order to further analyse the reliability of A-OLSR, it has been compared with other routing protocols in literature. The Ad hoc On Demand Distance Vector (AODV) [6] routing algorithm is an on demand algorithm, and maintains these routes as long as they are needed by the source. Additionally, AODV forms trees to connect multicast group members. Also, it uses sequence numbers to ensure the freshness of routes. It is loop-free, self-starting, and scales to large numbers of mobile nodes. The AODV protocol uses route request (RREQ) messages flooded through the network in order to discover the paths required by a source node. An intermediate node that receives a RREQ replies to it using a route reply message only if it has a route to the destination whose corresponding destination sequence number is greater or equal to the one contained in the RREQ. The RREQ also contains the most recent sequence number for the destination of which the source node is aware. A node receiving the RREQ may send a route reply (RREP) if it is either the destination or if it has a route to the destination with corresponding sequence number greater than or equal to that contained in the RREQ. Table summarises the comparison of A-OLSR and AODV protocols (Table 4).

Table 3 Performance comparison for low traffic and low mobility
Full size table
Table 4 Performance comparison for high traffic and high mobility
Full size table

AOMDV [20] is a variant of AODV and it imparts QoS by finding multiple loop-free and link disjoint paths. AOMDV improves the performance of AODV by reducing the network load and improving the end-to-end delay. Because of it’s scalable nature and widespread applications the performance of AOMDV and A-OLSR have been compared. The results of comparison indicate that A-OLSR outperforms AOMDV in case of high traffic, high mobility network. A-OLSR has the advantage of quickly adapting to the changes in topology by transmitting control packets. Although AOMDV offers multiple routes but it invests significant time in searching for an alternate route in case the primary route fails. This accounts for comparatively higher delay and lower PDR. Moreover, multiple route computation leads to higher routing load. Since A-OLSR adapts to network changes quickly, it offers overall better throughput than AOMDV. The results from simulation are summarised in Table 5.

Table 5 Performance comparison for A-OLSR and AOMDV
Full size table

5 Correctness of A-OLSR

From the simulation, we find that A-OLSR finds optimal routes that produces higher throughput and lower delay without introducing routing load even in highly dense and dynamic networks. The scalable nature of A-OLSR is attributed to it’s ability to find best connected routes that reduce the probability of route breakage and hence reduce overheads of routing and energy consumption by avoiding unnecessary delays.

(\(\textit{1}\hbox {-}h= one\hbox {-}hop \, neighbour\), \(\textit{2}\hbox {-}h= two\textit{-}hop \, neighbour\), \(\textit{3}\hbox {-}h= three\hbox {-}hop \, neighbour\))

TheoremA-OLSR finds the optimal connected routes using 3-h coverage MPR selection.

Lemma 1

The intermediate on the most optimal path are all selected as MPRs by previous nodes on the path.

A node may not be considered as a candidate for MPR if the node does not provide connection to it’s 3-hop neighbours. This situation is addressed in the following proof.

Proof

A-OLSR works by selecting the 1-h nodes that are the only ones to cover 3-h neighbours. Coverage to 3-h nodes would be done by intermediate 2-h nodes. Therefore the selected 1-h nodes cover the neighbourhood upto three hops away. This can be understood with the help of the graph in Fig. 12. □

Fig. 12
figure 12

a’s one-hop, two-hop and three-hop information

Full size image

In the graph, node b connects to node a’s two-hop neighbour: d. The standard MPR selection criteria would proceed by picking node b as the MPR. However in case of A-OLSR’s MPR selection criteria, the routing is done through node c as it covers node a’s the three hop neighbour: d. Considering the two possible paths from a to d: a \(\rightarrow\) b \(\rightarrow\) d and a \(\rightarrow\) c \(\rightarrow\) e \(\rightarrow\) d.

According to the network parameters defined in Table 1, the node b has a high probability to move away from communication range of node a since \(\angle\)abd is acute. If the path a \(\rightarrow\) b \(\rightarrow\) d breaks, then node b which forms the MPR for node a, can no longer be used for routing. This would introduce an overhead of re-computation for finding the MPR set and re-routing control information throughout the network.

Using the A-OLSR’s computation mechanism for the above scenario, probability of route breakage while routing through c is reduced as route a \(\rightarrow\) c \(\rightarrow\) e \(\rightarrow\) d is better connected. This is because, max(distance(ab,bd)) < max(distance(ac,ce,ed)). Since the nodes are at lesser hops away, the probability of route breakage is comparatively reduced. Therefore, A-OLSR forms such sub-optimal MPR selections, which eventually lead to better choices that offer overall performance gains.

Lemma 2

A node can correctly compute the optimal path for the whole network.

Proof

As shown by the above theorem, a node is capable to compute the optimal path on the known partial network topology. There exists an optimal path such that all the intermediate nodes are MPR of the previous node on the same path. So the optimal path for the entire network is created using the partial topology information at each node. This implies, a node can correctly compute the most connected path for the entire network topology. □

6 Conclusion

The tremendous rise of real-time applications using MANETs has necessitated the need of QoS provision for guaranteed performance. In this paper a QoS based routing protocol, called A-OLSR is discussed. The operation of A-OLSR is based on OLSR routing protocol which is an optimisation over classical link-state routing. Therefore, A-OLSR inherits the benefits of OLSR. OLSR selects MPRs which are used for packet forwarding and routing. In case of standard best effort OLSR, the MPR set is constructed by selecting the subset of one-hop neighbours that provide complete coverage to the two-hop neighbours. The heuristic proposed in this paper for A-OLSR aims at fetching optimal connected routes and constructs the MPR set by considering coverage to three-hop neighbours. Providing reachability to three-hop neighbours introduces some level of redundancy in the MPRs which helps to build more stable and reliable routes as compared to OLSR without introducing any control overhead.

The performance of A-OLSR is examined through computer simulations by using QoS routing metrics. The effect of new MPR selection criteria on routing has been analysed for two network scenarios, first in case of less dense and static network and then in case of highly dense and mobile network. Results of simulations show that A-OLSR performs significantly better than the standard protocol in terms of PDR, Throughput, Energy Consumption and Delay. The improvement in performance is more pronounced as the density of links and mobility of nodes is increased. This shows the scalability capability of the algorithm as it’s performance remains consistent with the increasing network size. Two variants, A\('\)-OLSR and A\(''\)-OLSR, are introduced to find the optimal number of neighbours whose coverage should be considered while constructing the MPR set. Simulations show that A-OLSR, which considers coverage upto three-hop neighbours gives better results than it’s variants which consider coverage upto four-hop and five-hop neighbours. Further, OLSR is compared with another existing QoS enabled protocol called, AOMDV. The results prove that A-OLSR performs slightly better than AOMDV for highly dense networks. Therefore, A-OLSR guarantees performance gains for static as well as highly dynamic networks. This work is supported by UPE-II, JNU.