A novel energy efficient obstacle aware routing algorithm for MANET

Abstract

In Mobile Adhoc Network (MANET), all nodes are energy and mobility constrained. The presence of obstacles in MANET severely degrades the efficiency of routing protocols in MANETs and consumes more energy for searching new routes. The high energy consumption of wireless nodes makes the MANET routing unpredictable. Therefore, it is important to consider the presence of obstacles in the network while evaluating the performance of the MANET. In this work, we have developed an Energy Efficient and Obstacle Aware Routing Algorithm (EEOARA) for MANET. For obstacles avoidance, the concept of Bezier curve based on DeCasteljau algorithm is used. In the proposed algorithm, to increase the availability of routes and to reduce the number of non-participating nodes, minimum energy consuming path which has maximum residual energy is preferred and selected. The performance of MANET is evaluated using NS2 simulator. Simulation results show that the proposed EEOARA reduces energy consumption, network overhead, delay and increases data delivery in the network.

Keywords

Energy efficiency DeCasteljau algorithm Bezier curve obstacles

1. Introduction

In Mobile Ad-hoc Networks (MANETs), a number of battery-powered mobile devices communicate without having a centralized administration. In MANET, routes frequently break due to the presence of obstacles in the network. Search of new routes consumes lots of energy and therefore, energy of many nodes falls below a pre-defined threshold value and the nodes become inactive. This degrades the performance of the MANET. Hence, to overcome this problem in this work, a novel energy efficient and obstacle aware routing algorithm (EEOARA) is developed considering obstacles in real MANET terrain. The main contributions of the paper are mentioned as below.

1.
Irregular sized obstacles are assumed to be placed in the MANET terrain. Location details of vertices of these non-moving obstacles are known. Trace path of Bezier curve is prepared avoiding obstacles using RMDA model [8]. From the trace path, special list of nodes are prepared, which contain all the connected nodes along the Bezier curve.
2.
A novel energy efficient and obstacle aware routing algorithm (EEOARA) is developed with special list of nodes, which selects the route, avoiding obstacles, having maximum residual energy that reduces route break. So requirement new route search reduces and energy consumption by the nodes for searching new route also reduces.

The paper is organized as follows. Section 2 describes the proposed EEOARA based on RMDA model for avoiding obstacles. Section 3 analyses the results. Section 4, concludes the work.
2. Related works

The portion of the section summaries the related works proposed by different authors on both plain and obstacle terrains.

In [1], authors have addressed energy and mobility aware routing protocol to measure the link stability among nodes in the network. In this paper, Semi-Markov Smooth mobility model is used to increase the performance of the nodes in MANET. However, the protocol lacks energy efficiency and moreover, the routing protocol is developed neglecting the presence of obstacles on the route. In [2], authors have addressed energy efficient multipath routing protocol using the fitness function. The fitness function is utilized for discovering the best possible path from sender to receiver. It improves the network lifetime and reduces the individual node energy consumption. However, in this work the routes may take longer hops and consume more bandwidth in the network. Moreover, the protocol has neglected the presence of obstacles in the network. In [3], authors have addressed energy-efficient scheduling method to efficiently schedule the mobile nodes for discovering an obstacle-avoiding shortest path. The node connection graph is developed by reducing the search space. However, the method is proposed for wireless sensor network. In [4], authors have addressed a dynamic and autonomic detection of obstacles technique in an optimized link state routing. The technique accurately specifies the obstacle area with high coverage and efficient precision ratios. However, authors have not addressed energy efficient routing. In [5], authors have proposed an environment-aware mobility model, which is applied to various environments. In this model, route and hotspot models are used to observe the node mobility in particular environments. However, the scheme does not suggest any energy efficient route selection method. In [6], authors have proposed a path planning technique using Ant Colony Optimization (ACO) technique to discover optimal sequence of points in a network. In this technique, rational Bezier curves helps to detect the obstacles. However, the technique does not suggest any energy efficient route selection method. In [7] Obstacle-avoiding Connectivity Restoration strategy is utilized mobility technique avoiding any arriving curved obstacle conditions. A backup selection algorithm proactively determines the cut-vertex sensors within the network and assigns a backup sensor to each cut-vertex node. Then, a selected backup sensor avoiding obstacles uses a gyroscopic force controller displaced restoring the disturbed connectivity. It provides restore connectivity with guaranteed collision avoidance. Moreover it does not provide any method to make energy efficient.

A Realistic Mobility model with irregular obstacle constraints based on Bezier curve (RMBC) is addressed in [8]. The obstacles are used both to define the movement pathways of the mobile nodes, and to obstruct the transmission. This method avoids node collision. However, it does not provide any technique to improve energy efficiency of the nodes in route.

3. Proposed energy efficient and obstacle aware routing algorithm (EEOARA)

In the proposed EEOARA, we have used the concept of Bezier curve to find special list of nodes to form a route. Then, the path having maximum residual energy is selected to increase the availability of routes and to reduce the number of non-participating energy deficient nodes.

3.1 Routing in realistic environment with obstacle

The realistic mobility model based on Bezier curve (RMBC) is used for collision-free realistic node movement in presence of obstacles [8]. Here, prior knowledge about the location of obstacles is known. Furthermore, it is assumed that the obstacles are stationary. In MANET, a node route breaks, during its random movement, when comes close to an obstacle. To avoid the route break, a special list of nodes are created, which are close to Bezier curve path trace. These nodes carry data to a destination to avoid data loss.

Figure 1 depicts the tracing of Bezier curve path using RMBC model as shown below [8]. To trace Bezier curve, a dummy node $N_{j}$ is assumed to be placed at point $PN_{i(j)}$ initially, in the $i^{\text{th}}$ step, it is allotted a random destination at $PN_{i+1(j)}$ . It moves towards $PN_{i+1(j)}$ at a tangent speed $v_{i}(j)$ , which ranges uniformly between [ $v_{\min}$ , $v_{\max}$ ]. Assume that there is an irregular obstacle present between $PN_{i(j)}$ and $PN_{i+1(j)}$ . In this paper, obstacle geometric centre and radius are represented as $O_{i}$ and $r_{i}$ respectively.

Figure 1.

Bezier curves in the presence of obstacles [8].

To avoid collision in movement from $PN_{i(j)}$ to $PN_{i+1(j)}$ , $N_{j}$ follows Bezier curve as shown in Fig. 1, which is qualified through a control point represented by $PN_{i\times(j)}$ . The waypoints $PN_{i(j)}$ and $PN_{i+1(j)}$ , in the $i^{\text{th}}$ step are indicated by two dimensional (2D) coordinates i.e. $X_{i(j)}$ , $Y_{i(j)}$ and $X_{i+1(j)}$ , $Y_{i+1(j)}$ respectively.

Thus the step curve segment followed by $N_{j}$ moving from $PN_{i(j)}$ to $PN_{i+1(j)}$ comprises a set of points that is given by Eq. (1) [7].

$\displaystyle\left[{\begin{array}[]{l}X(j)\\ Y(j)\\ \end{array}}\right]=\sum\limits_{k=0}^{3}{\left[{\begin{array}[]{l}XK(j)\\ YK(j)\\ \end{array}}\right]}{}\times BK^{3}\tau^{K}(i-\tau)^{(3-k)}$ (1)

Where, $\tau$ [0, 1] represents curve parameter that lies between 0 and 1 at the initial and the final waypoints $PN_{i(j)}$ and $PN_{i+1(j)}$ respectively in the $i^{\text{th}}$ step and $B_{K}^{3}$ is a Bernstein polynomials of degree 3.

The control point $PN_{i\times(j)}$ plays the key role in determining the step curve section. With the unequal obstacle constraints over the path, $PN_{i\times(j)}$ is jointly determined by $O_{i}$ and $r_{i}$ . With the prior knowledge of the location of obstacles and the assigned destination, the node $N_{j}$ moves on the curve section. $PN_{i\times(j)}$ is measured by $P_{i,(i+1})(j)$ that intersects two lines $PN_{i(j)}P_{i,1(j)}$ and $PN_{i+1(j)}P_{i,2}(j)$ within the terrain area ‘ $\omega$ ’.

The two lines are tangential to circular boundary of the obstacle at the points indicated by $P_{i,1(j)}$ and $P_{i,2}(j)$ correspondingly, which are collectively decided by the obstacle center $O_{i}$ , $r_{i}$ and the associated waypoints.

The boundary of the obstacle (Boci) can be approximately expressed as below in Eq. (2).

$\displaystyle(x-x_{i})^{2}+(y-y_{i})^{2}=r_{i}^{2}$ (2)

where ( $x_{i}$ , $y_{i}$ ) is the co-ordinates of an obstacle.

Then the segment of curve can be derived as shown below in Eq. (3).

$\displaystyle\textit{CSi}(j)=\{X,Y|(x,y)=\tau\textit{PNi}(j)+(1-\tau)\textit{% PNi}+1(j)\}i+1$ (3)

The collision free resolution to construct new via-points is established if $\textit{CSi}(j)\cap\textit{Boci}=\phi$ .

To make the path as smooth as possible, the resulted segment should minimize the cost function $C(j)$ , which is expressed in Eq. (4).

$\displaystyle C(j)=\sigma\int\limits_{Xi}^{Xi+1}\int\limits_{Yi}^{Yi+1}|k(x,y)% |\textit{dxdy}+(1-\sigma)\int\limits_{Xi}^{Xi+1}\int\limits_{Yi}^{Yi+1}|% \textit{CSi}(j)-Ii(j)|\textit{dxdy}$ (4)

Where, $\sigma$ [0, 1], $k(x,y)$ and $Ii(j)$ arethe curve of the section and centre section among obstacles respectively. Once the mobile node arrives at $PN_{i+1(j)}$ and completes a round trip on $CS(j)$ in i-th step, it chooses the destination $N_{i+2}(j)$ for $(i+1)^{\text{th}}$ step, and so on. In every step, the control point series is separated into various subsequences for piecewise Bezier curves creation, and these piecewise Bezier curves are associated to create the whole Bezier curve. The complete movement trace of mobile nodes is a sequence of trajectories, which is denoted by

$\displaystyle\{{CS1(j),CS2(j),\ldots\textit{CSi}(j)}\}$

Movement trajectories of mobile nodes for $r^{\text{th}}$ route is shown as below in Eq. (5) [8].

$\displaystyle U_{j=1}^{N}U_{i=1}^{M}\textit{CSi}(j)$ (5)

Now nodes close to Bezier curve trajectory are searched and these nodes are called special list of nodes, which construct route that avoids obstacles. Formation of alternative route using special list of nodes along Bezier trace is shown in the Fig. 2 below [8].

Figure 2.

Formation of alternative route using special list of nodes along Bezier trace.

Similarly, some more special list of nodes for alternative route is searched. Among these routes most energy efficient route is selected as is discussed in the next section.

3.2 Selecting energy efficient route

The maximum residual energy path among all alternative routes is selected as described in Section 3.1. The nodes having maximum residual energy will be selected, which reduces the chance of route break due to energy deficiency at nodes.

Let us assume total ‘ $n$ ’ number of alternate routes available.

Let $R_{r}(N_{o}\ldots N_{k})$ be the $r^{\text{th}}$ route having total $k$ nodes (i.e. $N_{0}$ to $N_{k}$ ) and it is denoted by

$\displaystyle R_{r}({N_{o},N_{k}})={N}_{0},N_{1},\ldots N_{k}$

Residual energy of each node is estimated for $r^{\text{th}}$ path, which is denoted by $R_{\textit{rre}}(N_{i})$ and is expressed in Eq. (3.2) as below [4].

$\displaystyle R_{\textit{rre}}({N_{i}})=N_{IE}-R_{r}({N_{i}}),$

(6) $\displaystyle\text{ For }i=0,1,2,3\ldots k.$

Where, ‘ $N_{IE}$ ’ is initial energy of node and ‘ $R_{r}(N_{i})$ ’ is available energy of $i^{\text{th}}$ node in the $r^{\text{th}}$ path.

$R_{\textit{rre}}(N_{i})$ of all the nodes in the route are estimated and compared with the pre-defined threshold energy ( $N_{TH}$ ) as shown below.

$\displaystyle R_{\textit{rre}}({N_{i}})>N_{TH}\text{ For }i=0,1,2,3\ldots k.$

A node that possesses energy below ‘ $N_{TH}$ ’ is not eligible to participate in communication.

If all the nodes of a path possesses energy above the threshold energy ‘ $N_{TH}$ ’, then total residual energy of the path is estimated.

Total residual energy of $j^{\text{th}}$ path designated as ‘ $R_{\textit{rreT}}$ ’ is estimated as shown in Eq. (7)

$\displaystyle R_{\textit{rreT}}=R_{\textit{rre}}({N_{0}})+R_{\textit{rre}}({N_% {1}})+R_{\textit{rre}}({N_{2}})\ldots{}+R_{\textit{rre}}({N_{k}})$ (7)

This equation is simplified and expressed in Eq. (8) [5].

$\displaystyle R_{\textit{rreT}}({N_{i}})=\sum_{i=0}^{k}R_{\textit{rre}}({N_{i}})$ (8)

In the proposed EEOARA, the path with maximum total residual energy is selected for routing.

$R_{S}=\text{Max}[R_{\textit{rreT}}]$ , Where ‘ $R_{S}$ ’ is the path selected finally for energy efficient routing. The flow chart of the proposed EEOARA is depicted in Fig. 3.

Figure 3.
EEOARA algorithm flow chart.

4. Simulation setup and performance evaluation

4.1 Simulation setup

The simulation of the proposed is validated using the network simulator NS2. The performance of the proposed EEOARA in terms of Packet Delivery Ratio, Average End to End Delay, Control Overhead and Average Energy Consumption is analysed and compared with the existing AODV protocol simulation in plain terrain (AODV) and AODV protocol simulation with obstacle in terrain without avoidance model (AODV-OT) [9]. In this work, Random Way Point (RWP) is used as mobility model. The parameters used for the simulation are depicted below in Table 1. In each of the experiments, simulation is run five times and the average value is taken to plot the graphs.

Table 1
Simulation parameters [10]

Parameter	Value
Channel	Wireless channel
Simulation span	500s
Number of mobile nodes	50
Number sources	5
Pause time (s)	0, 100, 200, 300, 400, 500
Max. speed	30 m/s
MAC protocol	802.11
Routing protocol	AODV
Traffic type	CBR
Initial node energy (J)	100 Joules
Packet size (Bytes)	512
Terrain area	1000 m $\times$ 1000 m
Transmission range	250 m
Network interface	Wireless phy
Mobility model used	RWP

Figure 4.

a. PDR for 50 nodes with 5 sources. b. Avg. Delay for 50 nodes with 5 sources. c. Avg EC for 50 nodes with 5 sources. d. Routing overhead for 50 nodes with 5 sources. e. PDR for 50 nodes with 5 sources. f. Avg. Delay for 50 nodes with 5 sources. g. Avg EC for 50 nodes with 5 sources. h. Control overhead for 50 nodes with 5 sources.

4.2 Performance analysis

4.2.1 Varying mobility (varying pause time)

In this experiment, 5 senders and 5 receivers are assumed with total 50 nodes MANET. Mobility of nodes is varied by varying pause time and performance of EEOARA is analysed and compared with AODV and AODV-OT.

The simulation results are listed in Table 2. It is observed in plot Fig. 4a that the PDR (%) of AODV is 96.85% at pause time ‘0 sec’ and becomes 96.13% at pause time 500 sec, which is because when pause time is ‘0 sec’, the mobility is high so link break is also more so PDR (%) is low. PDR of AODV-OT is less than AODV and is 84.49%. This is because of link breakage in presence of obstacles in realistic terrain. Same trend is observed for all the pause times. PDR of EEOARA is more than AODV and is 97.56%. The Packet Delivery Ratio of EEOARAis 0.85% more than AODV.

Table 2
Simulation results with varying pause time

Pause	Packet delivery ratio (%)			Average delay (ms)			Energy consumed (j)			Routing overhead
time (s)	AODV	AODV_OT	EEOARA	AODV	AODV_OT	EEOARA	AODV	AODV_OT	EEOARA	AODV	AODV_OT	EEOARA
0	96.85	84.49	97.56	89.6	99.6	88.5	12.65	21.34	11.96	0.99	2.02	0.96
100	97.09	86.76	97.88	75.3	92.61	74.1	10.38	19.58	9.84	0.86	1.83	0.78
200	97.28	87.07	98.09	58.9	65.07	57.8	8.42	17.65	7.82	0.73	1.52	0.7
300	97.59	88.42	98.39	52.1	63.43	51.2	6.39	15.46	5.98	0.64	1.43	0.57
400	97.02	89.11	98.15	41.2	52.75	40.3	4.85	10.23	4.13	0.52	1.29	0.49
500	96.53	90.48	97.25	30.1	42.34	29.6	3.87	8.49	3.99	0.41	1.16	0.39

Table 3

Simulation results with varying node density

No.	Packet delivery ratio (%)			Average delay (ms)			Energy consumed (j)			Routing overhead
nodes	AODV	AODV_OT	EEOARA	AODV	AODV_OT	EEOARA	AODV	AODV_OT	EEOARA	AODV	AODV_OT	EEOARA
10	95.13	82.49	96.04	37.92	51.23	36.54	3.54	9.34	2.97	0.29	0.91	0.25
20	95.63	84.76	96.42	46.23	60.56	42.11	5.08	13.13	4.17	0.41	1.01	0.37
30	96.12	87.07	96.78	57.56	69.88	52.68	6.93	15.32	5.99	0.61	1.22	0.47
40	96.72	89.42	97.43	66.49	81.57	62.43	8.85	17.23	7.54	0.69	1.56	0.64
50	97.09	91.11	97.88	75.3	92.44	74.22	10.38	19.58	9.54	0.86	1.83	0.81

At the same time ‘Average Delay’ is 89.6 ms for AODV at pause time is ‘0 sec’, it decreases as pause time increases because of fewer link breakages. Figure 4b shows the variation of Average Delay with respect to pause time. ‘Average Delay’ of AODV-OT is more than AODV i.e. 99.6 ms at pause time ‘0 sec’. ‘Average Delay’ of EEOARA is 88.5 ms at pause time is ‘0 sec’, which is less than AODV. The Average Delayof EEOARA is 1.64% less than AODV.

Average Energy Consumed by AODV at pause time ‘0 sec’ is 12.65 Joules. Average Energy Consumed by AODV-OT at pause time ‘0 sec’ is 21.34 Joules. The increase in energy consumption is because of rerouting in case of link breaks in presence of obstacles. In case of EEOARA average energy consumption at pause time ‘0 sec’ is 11.96 Joules. Aaverage energy consumptionin EEOARA decreases because of reduction of link breaks. The Average Energy Consumptionof EEOARA is 6.09% less than AODV.

Routing Overhead (Normalised Routing Overhead) of AODV at pause time ‘0 sec’ is 0.99. Routing Overhead of AODV-OT at pause time ‘0 sec’ is 2.02. In case of EEOARA, Routing Overhead at pause time ‘0 sec’ is 0.96. Routing Overhead decreases because of reduction of link breaks. The Routing Overheadof EEOARA is 6.26% less than AODV.

From the above results, it is clear that the improvement in PDR, Average Delay, and Energy Consumption and Control overheads of EEOARA is due to reduction in link failures.

4.2.2 Varying node density

In the experiment, 5 senders and 5 receivers are assumed with a pause time fixed at 100 sec and with varying 10–50 nodes MANET. The performance of EEOARA is analysed and compared with AODV and AODV-OT.

The simulation results are listed in Table 3. Figure 4e shows the variation of PDR% with respect to number of Nodes. It is observed that the PDR (%) of AODV is 95.13 when total number of nodes 10 and increases slowly to 97.09% at 50 nodes. The increase of PDR (%) is due to increase in node density that increases network connectivity. PDR of AODV-OT is less than AODV and is 82.49%. This is because of more links break in presence of obstacles in realistic terrain. Same trend is observed when node density increases. PDR of EEOARA is more than AODV and is 96.04% for 10 nodes. The Packet Delivery Ratio of EEOARA is 0.8% more in comparison to AODV.

Figure 4f shows the variation of Average Delay with respect to number of nodes. It is observed that the Average Delay of AODV is 37.92 ms when total numbers of nodes are 10 and increase slowly to 75.3 ms at 50 nodes. The increase of Average Delay is due to increase of network traffic that increases network congestion and hence, Average Delay.Average Delay of AODV-OT is more than AODV and is 51.23 ms at 10 nodes. Average Delay of EEOARA is less than AODV and is 36.54 ms for 10 nodes. The Average Delay of EEOARA is 5.47% less in comparison to AODV.

Figure 4g shows the variation of Average Energy consumed (Energy consumed) with respect to number of Nodes. It is observed that the Average Energy consumed of AODV is 3.54 J at 10 nodes and increase slowly to 10.38 J at 50 nodes. Average Energy consumption of AODV-OT is more than AODV and is 9.34 J for 10 nodes. Average Energy consumption of EEOARA is less than AODV and is 2.97 J. The Average Energy consumption of EEOARA is 13.13% less in comparison to AODV.

Figure 4h shows the variation of Normalised Routing Overhead (Routing Overhead) with respect to number of Nodes. It is observed that the Normalised Routing Overhead of AODV is 0.29 at 10 nodes and increases to 0.86 at 50 nodes. Normalised Routing Overhead of AODV-OT is more than AODV and is 0.91. This is because of more numbers of link breaks in presence of obstacles in realistic terrain. Normalised Routing OverheadforEEOARA is less than AODV and is 0.25. The Normalised Routing Overhead of EEOARA is 11.18% less in comparison to AODV.

5. Conclusion

The proposed Energy Efficient Obstacle Aware Routing (EEOARA) for MANET shows appreciable improvement in terms of Average Delay, Average Energy Consumption, and control overhead compared to AODV and AODV-OT in presence of obstacles. Here improvement observed in Packet Delivery Ratio is low. Hence more research work need to be done to further improve performance of MANET in presence of obstacles in terrain area.

References

Rashid

Waqar

and Kiani

A.K.

, Mobility and energy aware routing algorithm for mobile ad-hoc networks, in: International Conference on In Electrical Engineering (ICEE), Vol. 10, 2017, pp. 1–5.

Taha

Alsaqour

Uddin

Abdelhaq

and Saba

, Energy efficient multipath routing protocol for mobile ad-hoc network using the fitness function, IEEE Access 5 (2017), 10369–10381.

Xie

and Pan

, Energy-efficient scheduling for mobile sensors using connection graphs in a hybrid wireless sensor network with obstacles, International Journal of Distributed Sensor Networks 2014 (2014), 1–9.

Belghith

Belhassen

Dhraief

Dougui

N.E.

and Mathkour

, Autonomic obstacle detection and avoidance in MANETs Driven by Cartography Enhanced OLSR, in: Mobile Information Systems, Vol. 2015, 2015, pp. 1–18.

Manson

and Belis

, Mobility modeling in mobile ad hoc networks with environment-aware, Journal of Networks 1(1) (2006), 54–63.

Alves

J.M.M.

, Path Planning and Collision Avoidance Algorithms for Small RPAS. MS Thesis. Instituto Superior Tecnico 2017, Universidade de Lisboa, Portugal.

Yang

and Yang

J.Y.

, Restoring connectivity of mobile robotic sensor networks while avoiding obstacles, IEEE Sensors Journal 15(8) (2015), 4640–4650.

Wang

and Zhang

, A realistic mobility model with irregular obstacle constraints for mobile ad hoc networks, Wireless Networks 23 (2017), 1–20.

Amjad

W.K.

Ali

Jabbar

Hussain

Rho

and Kim

, Impact of dynamic path loss models in an urban obstacle aware ad hoc network environment, Journal of Sensors 2015 (2015), 1–8.

10.

Royer

E.M.

and Perkin

C.E.

, An Implementation Study of AODV Routing Protocol, in: Proceeding of IEEE Wireless Communication and Networking Conference (WCNC 2000), San Diago, Califernia, Vol. 3, pp. 1003–1008.