Abstract: Mobile ad-hoc networks (MANETs) are self organizing network, which exchange data among themselves, through single hope or multi hope. Designing an effective routing protocol is a crucial issue in MANET, due to highly dynamic topology. The author proposes BEMPRs-OLSR protocols, which reduces control overheads, by selecting Multi point relays. Multipoint relays where selected, by considering the node which is having maximum out degree, if there is a tie in that value maxim-mum bandwidth node will be consider as MPRs. The path which was formed from source to destination through MPRs, should be a loop free path, this was achieved by maintaining more the one node as MPRs before breaking the tie among the nodes, that are competing for MPRs. Simulation was performed in network simulator 2, shows that BEMPRs-OLSR performs well when compare to any other protocols.
INTRODUCTION
Mobile Ad-hoc networks are topology free, self organizing networks. They can exchange data among themselves through single hope or through multi hope. It uses single hop, if target node is available within its transmission region, else it uses multi hope. The nodes that are not destinations can act as router, and they are used to forward the data and control packets form source to destination. MANET Topology is highly dynamic network, so transferring data between the nodes are difficult. Designing an effective routing protocol for such highly dynamic network was a difficult task. Since packet loss ratio, link failures, control overheads and packet re-transmission are very high (Abolhasan et al., 2004).
Ad hoc networks Routing Protocols are classified in to:
| • | Proactive Ex: Destination Sequence Distance Vector (DSDV) (Perkins and Bhagwat, 1994; Lakshmi and Sankaranarayanan, 2006) and Wireless Routing Protocol (WRP) (Murthy and Garcia-Luna-Aceves, 1996) |
| • | Reactive Ex: On demand Distance Vector (AODV) (Perkins and Royer, 1999; Hussain et al., 2007) Dynamic Source Routing (DSR) (Johnson and Maltz, 1996; Sesay et al., 2004) |
| • | Hybrid Ex: Zone Routing Protocols (ZRP) (Hass, 1997; Nazir et al., 2006), Zone based Hierarchical Link state (ZHLS) (Joa-Ng and Lu, 1999) |
The numbers of control packets used by these protocols for establishing the routes are high, so there is a need to develop a protocol which uses lesser overheads. An Efficient flooding mechanism was introduced, to establish the path for source to destination, so that it is possible to minimize the traffic of control packets (Perkins and Bhagwat, 1994).
Efficient flooding mechanism where introduced in Optimized Link State Routing (OLSR) (Clausen and Jacquet, 2003), Preferred Link-Based Routing (PLBR) (Jacquet et al., 2001; Clausen and Jacquet, 2003) and quality of service Qos-OLSR (Qayyum et al., 2000).
Optimized Link State Routing (OLSR) uses a table driven approach to establish a route from source to destination, effective flooding mechanism was used to reduce control packets. Effecting flooding mechanism were introduced by selecting the nodes as Multi Pont relays (MPRs) (Qayyum et al., 2000), among the nodes in the network. A node can act as multipoint relay, if it covers more number of nodes in next level.
MPRs reduces control overheads, since they are the only nodes that can forward the control packets in the network, remaining nodes can here the control packets, but they cant able to forward it (Clausen and Jacquet, 2003).
| Fig. 1: | Mobile ad hoc network |
Figure 1 shows a mobile ad hoc network, in which some of the nodes are selected as MPRs. Since, out degree of the nodes are high, i.e those nodes can cover more number of nodes in next level.
MPRs selection in OLSR will avoid the paths with high bandwidth, since the selection of multipoint relays doesn’t depends on any QoS metric like bandwidth, delay or any other metric (Badis et al., 2003).
In quality of service in optimized Link State Routing-Multi Point Relay 1(QOLSR-MPR1), Quality of Service in Optimized Link State Routing-Multi Point Relay 2 (QOLSR-MPR2) (Badis et al., 2003) the network over head (traffic) is less when compare with any other Table-driven protocols. Since forwarding the control packets can be done only by the MPRs which are similar to OLSR. The nodes that are not MPRS can process the packet but they can not forward the packet. So that network overhead is less. The author itself proved that QOLSR-MPR1 doesn’t select bandwidth efficient path, since whenever more than one node compete to act as MPRs, the tie was broken by considering higher band width. QOLSR-MPR2 while selecting the MPRs bandwidth, delay measures are used so that it will select the optimal path.
Selection of MPRs in QOLSR-MPR2
When node discovering a route to destination node it will select the path, the path should be a loop free path. The path formed by QOLSR-MPR2, ratio of loop formation is high, so the given QOLSR-MPR2 can not able to find a bandwidth efficient (Sharma et al., 2007) loop free path from source to destination. In this study loop formation ratio was minimized when compare to QOLSR (Sharma et al., 2006).
Bandwidth efficient multipoint relays in optimized link state routing (BEMPRS-OLSR): Loops that are formed by QOLSR-MPR2 can be reduced by changing the selection process of MPRs.
Selection of MPRs in BEMPRs-OLSR
BEMPRs selection algorithm
Input:
| • | Routing Table: consists of 1-hop node information and bandwidth |
| • | Neighbor Table: consist of neighbor’s information |
Output:
| • | Updated routing tables required for data transfer |
| • | Nodes which has been Selected as MPRs |
| Steps: | MPR(x) refers to the MPR set of node x |
|
| Step 1: | Initializing the multipoint set as null set EMPR set |
|
| Step 2: | If a 1-hop node exist in such a way that, it is the only node to reach
some nodes in next hop then add such a node to |
|
| Step 3: | While there exist some of the nodes which are not covered by any node in MPRs set | |
| • | For every 1-hop node which is not in MPRs set find the number of nodes it covers in next level | |
| • | If a node covers maximum number of nodes in next level consider that node in MPRs set | |
| • | If more than one nodes covers same number of nodes in next level | |
| • | Copy the entire nodes to MPRs and break the tie by selecting a node which is having higher bandwidth | |
| Step 4: | Repeat step 3 until all the nodes are covered by some MPRs | |
| Step 5: | While forming the path with the help of the nodes in the MPRs set if it form a loop | |
| • | If there is a possibility, another node can act as multipoint relay then select that node as MPR to form loop free path else go to step 1 |
| Fig. 2: | Weighted mobile ad hoc network |
| Table 1: | MPR selection in BEMPRs-OLSR |
| * Represent the selected MPR node due to tie | |
Proposed BEMPRs selection algorithm was applied to the ad hoc network shown in Fig. 2; the obtained MPRs are shown in Table 1.
Claim 1: Optimal path for k≥3 is μ
μ = (n1, n2,…,ni-1, ni, ni+1,…..nk), were, k is the number of nodes (Badis et al., 2003). In path μ, consider any intermediate node ni, which is not selected as MPRs by its previous node ni-1. So there exists another node zi, which as been selected as MPRs by ni-1.. Then there exist a path μ`= (n1, n2,…,ni-1, zi, ni+1,…..nk) has same band width.
Proof: Let μ = (n1, n2,…,ni-1, ni, ni+1,…..nk), be a optimal widest path for K = 3. If ni was not selected as multipoint relay by its previous node ni-1 , then there exist another node zi, which as been selected as MPR by ni-1, which in turn connected to ni+1. Let μ`= (n1, n2,…,ni-1, zi, ni+1,…..nk), K = 3. According to the selection of MPRs by BEMPRs-OLSR ni-1 selects zi instead of ni because:
| (1) |
or
| (2) |
From (1) outdeg (μ`) >outdeg (μ) and there is no guarantee about bandwidth
From (2)
In both the cases, outdeg (μ`) ≥outdeg (μ).Based on our assumption μ. So μ` is also an optimal path.
Claim 2: There exists an optimal widest path in entire network such that all the intermediate nodes are selected as MPR by their previous nodes (Badis et al., 2003).
Proof by recurrence: Let μ=(s, n1, n2,…,ni-1, ni, ni+1,…..nk,.....,nz,m), k< z an optimal path.
| • | First we prove that node a1 is selected as MPR by source s. Using claim 1 it is possible to find b1 selected as MPR by s have a path μ`= (s, n1, n2,…,ni-1, ni, ni+1,…..nk,.....,nz,m) has same band width performance. So source nodes are in optimal path. |
| • | We assume that all the nodes (n1, n2,…,ni-1, ni, ni+1,…..nk ) are selected as MPR by their previous node in the path μ. To prove that the next hop node of nk on μ was nk’s MPR. If nk+1 is not a MPR of ak, by claim 1 we can find a path μ`= (s, n1, n2,…,ni-1, ni, ni+1,…..nk,.....,nz,m) has same performance. So in an optimal path the (k+1)th |
Intermediate node is the MPR of the (k)th intermediate node.
From (a) and (b), in an optimal path al intermediate nodes are MPRs of the previous nodes.
| Table 2: | Performance cost table |
Path discovery:
| • | M-J-C-A |
| • | L-K-J-C-A |
| • | K-J-C-A |
| • | J-C-A |
| • | I-M-J-C-A |
| • | H-G-J-C-A |
| • | G-J-C-A |
| • | F-C-A |
| • | E-F-C-A |
Numerical estimation: Band of a path is defined as sum of bandwidth of all the edges in that path (Deepalakshmi and Radhakrishnan, 2009).
bandwidth (path (i, j)) = Bandwich (e) |
| • | Hop count is defined as number of intermediate node that are there in that path (Deepalakshmi and Radhakrishnan, 2009) hop count (path(i,j)) = {count(Nodes(path(i,j))}-S,D} |
Were, S and D are source and destination nodes, respectively.
| • | Bandwidth and hop count for the path <M-J-C-A> bandwidth = 10+6+2 = 18 hop count for path = 2 |
Performance evaluation: The Proposed BEMPRs-OLSR was compared width the protocols like OLSR, QOLSR-MPR1, QOLSR-MPR2 following. Simulations were carried out sing 2 with the parameters shown in Table 3.
The following performance metrics were used to compare BEMPRs-OLSR with the existing once.
Performance is characterized by
non optimal route: Routes that are having lower bandwidth, higher value denotes lower bandwidth path.
| Table 3: | Simulation parameters |
Optimal routes: Routes that are having higher bandwidth, higher value denotes maximum band width path.
Loop formation: Starting node and ending node of a path is same then it is called loop. Higher value denotes loop formation is high.
Cost is measured by
Number of control packet transferred: Number of control packets increased,
when ever there is more number of MPRs.
Number of MPRs: When ever node density in the network is high, number of MPRs also increases, since the nodes that are required to cover the network are also increases.
From Table 2 it was clear that, the worst performance protocol was OLSR since the value is high for Non-optimal path and loop formation. Both QOLSR-MPR2 and BEMPRs-OSLR always select the optimal path, but the percentage of loop formation is high in terms of QOLSR-MPR2.So the proposed BEMPRs-OSLR perform well when compare to any other protocol.
Figure 3 shows the variations in routing overheads due to mobility. When mobility is high link break will happen frequently, so frequent MPRs are to be found which increases routing overheads. Before route discovery process MPRs are to be selected, to reduce control overheads. The protocols that are selected for the comparison all are using effective flooding mechanism. So there is no much difference in control overheads.
| Fig. 3: | Routing overhead variations due to mobility |
| Fig. 4: | Variations in Packet delivery due to mobility |
| Fig. 5: | Variations in packet delivery ratio due to number of nodes |
| Fig. 6: | Effects of nodes on MPR selection |
Wireless network through put was calculated based on, average successful message delivered on that wireless channel. To find throughput of a network, it is necessary to analyze packet delivery ratio, which provides packet loss rate. The packet delivery ratio of all four protocols are shown in Fig. 4. It shows the variations in packet delivery ratio due to mobility, when mobility increases packet delivery ratio will decrease. In BEMPRs-OLSR formation of loop free path ratio is very high, so packet delivery ratio increases when compare to all other protocols. In a network when the number of nodes increases, packet delivery ratio will also increase, due to increase in intermediate nodes and availability of links, this can be observed form Fig. 5.
Figure 5 Variations in packet delivery ratio due to number of nodes.
Figure 5 state that there is no much variation in routing overheads of all four protocols, it shows that there won’t be many variations in selection of MPRs also which is shown in Fig. 6. Since OLSR, QOLSR-MPR1, QOLSR-MPR2 and BEMPRs-OLSR never discuss about efficient way of selection of MPRs. In OLSR MPRs are selected based on how many nodes it covers in next hop. In QOLSR-MPR1 and QOLSR-MPR2 MPRs were selected by considering band width has metric along with number of nodes covered in next hop. BEMPRs-OLSR protocol MPRs selection is similar to the previous protocols, but changes have been in selection of next hop nodes, so that the loop formation ratio varies. Because of these reasons there were no much variations in selection of MPRs.
CONCLUSION
Control overhead in any Ad-hoc network should be less, to achieve maximum Performance. MPRs were introduced in OLSR, but OLSR won’t select an optimal path. We have discussed BEMPRs-OLSR algorithm for selection of multi-point relays. The algorithm that was introduced in QOLSR-MPR1 doesn’t ensure that it will select an optimal path. QOLSR-MPR2 where introduce by considering band –width, delay as QoS metric, the possibility of loop formation is very high. Through simulations it has been, demonstrated that BEMPRs-OLSR perform well when compare to any other protocols.