Introduction

A Mobile Ad hoc NETwork (MANET) is a wireless communication network system that is comprised of mobile devices like laptops, mobile phones, and drones, amongst others. These mobile devices are commonly referred to as nodes and they have the ability to communicate with other nodes without requiring any intermediate network infrastructure; hence, they are considered self-configuring or self-organizing networks (SON), which are easily deployable, that are capable of self-directed operations. Generally, wireless networks can be classified into four categories: Mobile Ad hoc Network (MANET), Wireless Sensor Network (WSN), Wireless Mesh Network (WMN), and Vehicular Ad hoc Network (VANET). In MANETs, nodes work together to deliver network access and resources without centralized management (Ilyas, 2003). Nodes in MANET are usually connected within a defined, but limited distance coverage area and they can freely join an ad hoc network, move within the network and leave the ad hoc network. A unique feature in MANETs is the ability to incorporate MANET nodes into cellular wireless networks. Incorporating MANET nodes into a cellular wireless network allows nodes to communicate directly with other nodes without going through base stations.

MANETs find their usefulness in areas where nodes are mobile and there is no pre-existing communication or network infrastructure, like military battlefield networks, collaborative robotic mobile networks and vehicular networks (VANET). Other application areas include where pre-existing communication infrastructure has been destroyed, as in disaster relief networks and sensor networks; or areas where it is not feasible for either financial reasons, physical constraints or mobility to use wired networks. A typical application scenario of MANET can be seen during the rescue of 12 teenage Thai footballers and their coach in a cave. This was an operation that involved about 10,000 workers working in an ad hoc manner (Smith, 2018). For proper communication and coordination of activities, a MANET network infrastructure becomes necessary. In another circumstance, the Carr wildfire of California (Morris, 2018) involved more than 27,000 fire fighters and logistic workers, some of whom were from other nations. For effective communication and coordination of activities, MANET network infrastructure also becomes vital.

For any MANET to be effective, a routing protocol is required for nodes in a network to communicate and create routes for data transmission. These paths are logically structured so that the data packets can travel over multiple hops to get to the destination node (Pattanayak et al., 2011). Routing is the process of creating a path in a network by using some predefined metrics with the aim of transmitting data from source to destination. The routing process is an important layer in the Open System Interconnect (OSI) reference model, and it is the nucleus to the proper functioning of any multi-hop network system like MANET. However, the design of an efficient routing protocol is confronted by several challenges due to the constrained resources of MANET devices, like limited memory, processing power, battery life and bandwidth (Pattanayak et al., 2011). Some MANET devices (nodes) die out during operation due to limited battery life, and getting a charging system in an ad hoc situation could prove challenging. It becomes imperative to design an energy-efficient MANET routing protocol that could provide a longer lifetime for MANET nodes. Therefore, this paper addresses this research gap.

The rest of the paper is organized as follows. A review of related energy-efficient protocols for ad hoc networks is discussed with a focus on the Power-Efficient Gathering in Sensor Information Systems (PEGASIS) and Energy Efficiency Dynamic State (EEDS) algorithm. Further, we propose and present our hybrid model, PEGADyn. Through NS2 simulation we demonstrate that our protocol (PEGADyn) provides better network lifetime, throughput ratio and packet drop rate compared with PEGASIS and EEDS.

Energy-based Routing Protocols in MANET

In MANETs, different metrics for finding routes from source to destination have been proposed (Boukerche et al., 2011; Aziz & Al-Akaidi, 2007; Son et al., 2014). MANET algorithmic routing methods include link-state and distance-vector algorithms. However, in this study, an exploration is undertaken of power-efficient protocols that could improve the battery life of nodes while providing good network throughput.

Low Energy Adaptive Clustering Hierarchy (LEACH)

Heinzelman, Chandrakasan & Balakrishnan (2000) presented a Low Energy Adaptive Clustering Hierarchy protocol, also referred to as the LEACH protocol. LEACH is a self-configuring and self-organizing hierarchical routing protocol. It uses a clustering system which uses a random-based mechanism for the selection of local cluster-heads that uniformly apportion the energy cost among network nodes. The LEACH algorithm process is divided into rounds (time steps performed during packet transmission) of configuration and each round consists of two phases. The first phase is the Cluster setup, while the second phase is the Steady-state phase. A node sends its data to a nearby cluster head, which in turn compresses the data and forwards the data to a base station. A fundamental assumption in LEACH is that the radio strength of each node is enough to reach any base station or at least to a nearby cluster head (CH). In the LEACH algorithm, a voting process occurs for the selection of a cluster-head at a specific time period. This is necessary to maintain a state of energy equilibrium among the CHs in the network. The voting process in LEACH is a weakness, as this causes additional energy and network overhead to be spent in the process.

Power-Aware Ad hoc On-Demand Distance Vector Routing (PAAODV)

Pattanayak et al. (2011) proposed a Power-Aware AODV (PAAODV) protocol, which is a power consumption improvement to the AODV routing protocol. The concept behind PAAODV is the regulation of the transmission power of nodes in the network to extend network lifetime and sustain network connectivity. PAAODV uses a node’s transmission power level to regulate the number of packets transmitted. The researchers submitted that regulating the transmit power of a node conserves a node’s energy and thus extends its network lifetime. They only compared the performance of PAAODV with AODV and other non-energy-based protocols. However, a true justification for the authors’ claim of improved network lifetime will be a benchmark against similar energy-based routing protocols, which was not provided.

Energy Efficiency Dynamic State (EEDS)

According to Gautam et al. (2016), the lifetime or energy of nodes in a network can be improved and maintained using the concept known as Energy Efficiency Dynamic State (EEDS). This concept uses three states, namely: the active state; the night state; and the discovery state. Nodes under EEDS are required to be in one of these states, while only nodes in the active (and ready) state can be considered for routing. Nodes in the night state are either depleted or recouping their energy. In EEDS, nodes are grouped into a predefined number of virtual grids based on their current positions. Nodes in the active state are involved in routing functions. Nodes in a grid can often transfer their tasks to other nodes in the active state within their own virtual smart grid once they observe their energy levels to be critical or depleted to 10%. Nodes with critical energy level then begin to transit into the night state where they are not involved in routing or any other tasks, in order to recoup their energy. Eventually, these nodes recoup their energy and thus move to the discovery state, where they are now ready to participate in routing tasks.

Table 1 provides a summary of some cluster-based protocol schema used in ad hoc networks. The table shows parameters used for CH selection based on CH identity (ID), permissibility of node to overlap between clusters, the density of nodes per cluster and the frequency of CH change.

Table 1. Energy-aware and Cluster-based Protocols. Adapted from Udaykumar & Thirugnanam (2015).

Clustering Schema

Based on

CH’s Selection

Overlap Cluster

Number of Nodes

CH Change

Power Efficient Gathering in Sensor Information System (PEGASIS)

To provide a significant refinement to the LEACH protocol, Lindsey & Raghavendra (2002) proposed a Power-Efficient GAthering in Sensor Information Systems (PEGASIS). The focus of PEGASIS is to organise the nodes so that each node takes its turn to receive and transmit packets to some nearby neighbour nodes. The collected data passes from one node to another, and ultimately a designated node transmits the collected data to a base station. In PEGASIS, nodes take their turn to transmit packets to the base station with the aim of minimizing the average energy spent by each node in transmitting from source to destination and back again (round trip time). In contrast to LEACH, the PEGASIS algorithm shows inherent benefits. First, it performs a localized node gathering where the distance covered to transmit data to the destination is much shorter in comparison to the LEACH protocol. Secondly, the number of rounds (time steps performed during packet transmission) made per node during packet transmission to the base station is kept minimal. Thirdly, since the selection of CH is made once, the probability of node overlap among cluster groups is eliminated.

There are, however, variants of the PEGASIS protocol and these are discussed below.

1. Improved PEGASIS Routing Protocol Based on Neural Network and Ant Colony Algorithm (ACON-PEG). ACON-PEG embeds the ant colony algorithm and neural network instead of using the greedy algorithm to build the network routes. ACON-PEG subdivides the route coverage area into multiple, but equal parts and creates a chain that makes the route path evenly spread while reducing the square of the total transmission radius. The protocol utilises the concept of a neural network algorithm to choose the chain head and applies the ant colony algorithm to discover the optimal path for sending data to the base station. Li et al. (2015) claim that, in comparison with PEGASIS by Lindsey & Raghavendra (2002), ACON-PEG achieves better route optimization.
2. Improved Energy-Efficient PEGASIS-Based Protocol. The Improved Energy-Efficient PEGASIS-based protocol (IEEPB) was proposed to address the problems of Energy-Efficient PEGASIS-Based protocol (EEPB), which was challenged with the sub-optimal election of leader node and long links of chain nodes. Sen, Bing & Liangrui (2011) use a weighting scheme to select the leader node by assigning every node a weight that demonstrates the node’s suitability to become a head/leader. The weight is based on a node’s properties, including its residual battery power and the distance between the node and the base station. The paper claims that IEEPB has higher energy efficiency and, hence, longer network lifetime.

PEGADyn: Hybridizing PEGASIS and Dynamic State Routing Algorithms

Our study into the PEGASIS algorithm shows it has some features that make it unique, although there are some aspects wherein energy is being wasted. Similarly, the virtual classification of nodes into grids in the Dynamic State (EEDS) algorithm provides an efficient topological structure for an optimized energy efficiency implementation. This study, therefore, explores and amalgamates the unique features of PEGASIS and EEDS to develop a new hybrid optimized energy-efficient algorithm called PEGADyn.

In PEGADyn, a virtual grid classification of nodes based on their current location is generated, and this is followed by a cluster formation of nodes in each virtual grid created. A virtual grid has a default radius of 50 metres, while a default cluster radius is 25 metres. In each cluster formed, a cluster head (CH) is selected based on the node with the highest energy level. The node with the second highest energy level is selected as the associate cluster head (aCH). Where there is a tie in energy level, an arbitrary selection is made by the algorithm.

Furthermore, to aid inter-virtual-grid communication, designated CHs (dCH) are selected from among CHs in each virtual grid. The selection of a dCH is a combination of minimal mobility of a CH node, and the CH with the highest energy level in a virtual grid. Thus, a dCH also doubles as the CH for its own cluster group. A dCH transmits packets for the cluster groups in its virtual grid. Inter-virtual-grid communication ensures that CHs communicate only with clusters in their own virtual grid. For communication with clusters or nodes outside their virtual grid, a node sends its packet to a CH it is associated with, and the CH in turn sends the packet to a dCH that routes the packet to another dCH (in a different virtual grid) that can fulfil the route request.

Figure 1. Virtual grid classification of nodes based on proximity.

All CHs advertise their route details to their cluster members and each node member aligns and sends its packet via the CH. Every CH also advertises its route details to other CHs. This way, a source-to-destination path is formed from one end node to another. Figure 1 shows the virtual grid classification based on proximity of nodes. Figure 2 shows the final cluster and network formation of nodes and inter-virtual-grid routing communication.

Figure 2. (a) Node deployment; and (b) Cluster formation and CH selection.

Since nodes are mobile within the network, when a node’s proximity threshold is reached (default is 50 metres), it switches its grid and cluster to join a new virtual grid and cluster. In this respect, a node identifies with a cluster group in order to identify a CH that it could use to route its traffic. A summary of the procedure for CH, aCH and dCH selection is given in Figure 3. When a CH is depleted in energy or moves away to another cluster, it becomes an ordinary node in the new cluster it joins and aligns itself with the CH in that cluster for packet routing. However, if there is no CH in that cluster, the node assumes itself as the CH and advertises its details to proximity nodes to form a cluster. The classification of the virtual grid is to create a proximity boundary, so that only two CHs communicate across the virtual grids. While CHs within a virtual grid can communicate as they want, inter-virtual-grid communication can only be performed by designated CHs (dCHs).

Figure 3. Virtual grid, cluster formation and CH selection in PEGADyn.

Figure 4. Flowchart for the creation of virtual grids and clusters; and selection of CHs, aCHs and dCHs selection.

The deployment of nodes and the creation of virtual grids and clusters is shown in Figure 4. At the start of the flowchart, the deployed nodes are initialised. This is followed by the formation of virtual grids (vs-grid) based on the positions of the deployed nodes. The virtual grids aid inter-virtual-grid communication.

Further to that, cluster formations are created within each virtual grid. This is to facilitate inter-nodal communication between CHs and nodes within each cluster. This phase forms the initial network topology formation.

Next, nodes within each cluster examine their energy levels to elect a CH and an aCH. The node with the highest energy level within a cluster is elected the CH, while the node with the second highest energy level is selected as the aCH. Now, within every virtual grid (vs-grid) a dCH is selected, which is a CH with the highest energy level. The dCH facilitates communication between virtual grids in the network. All CHs advertise their route details to the nodes within their cluster groups and to other CHs to form route paths to other virtual grids. To maintain network stability and to avoid becoming depleted of energy during the routing process, every CH shares network updates (synchronises) with its aCH. Once network convergence is achieved, nodes are able to transmit their packets via their CHs to other nodes within the cluster. However, packets destined to other virtual grids are sent from a CH to a dCH, which transmits the packet to a counterpart dCH that delivers the packet to the destined node within its cluster or forwards it to another dCH for onward delivery.

Energy efficiency plays an important role in ad hoc networks hence, the core of PEGADyn is to minimize the power consumption of nodes during network transmission. It achieves this by reducing inter-node communication by assigning the responsibilities to designated nodes at cluster and virtual grid levels. By this communication system, nodes take turns to become CHs, aCHs and/or dCHs to balance the energy requirement among all nodes. This way, the network lifetime is extended, and throughput is not compromised.

Our proposed system was compared through simulation with PEGASIS and the Dynamic State algorithm. The comparison was based on energy consumption, residual energy and network throughput.

Simulation and Results

The simulation setup was performed using NS2 version 2.34. No route overhead has been considered in the simulation because of the link stability and the route lifetime. The total coverage area was set at 500m x 500m, which is a realistic space to cover for an emergency or a disaster scenario. The NS2 simulator provides support for the multicast routing protocols and the IP protocols, such as TCP and UDP. A total of 50 nodes were deployed and each node has a transmission range of 100 metres; a mobility speed of 5 metres per second was assumed. Multiple simulation runs were performed, and the average results were computed and presented. A summary of network simulation parameter settings is presented in Table 2.

Table 2. Network Simulation Parameters

Simulation Settings

Simulation platform

NS2 v2.34

Coverage Area

500m x 500m

Antenna Type

Omnidirectional

Node Transmission range

100 metres

Node Speed

5 m/s

Number of Nodes

50

Traffic Type

UDP/CBR

Routing Protocols

EEDS, PEGASIS and PEGADyn

Simulation Time

500 seconds

Figure 2(a) shows the initial deployment of network nodes while Figure 2(b) shows cluster formation and the selection of CHs. CHs have been selected based on the energy of the nodes in the network. The node with the highest energy is selected as the CH for every cluster. Nodes of the same cluster group have the same colour (see Figure 2(b)). Hence, nodes in yellow belong to the same cluster, while nodes in red are in the same cluster group.

Power Consumption

Power consumption is the total amount of energy consumed by a node during packet transmission and reception. Figure 5 shows the graph of energy consumed (Joules) by PEGADyn is less compared to PEGASIS and Dynamic State. This supports our point that our proposed PEGADyn protocol has better energy efficiency in comparison to PEGASIS and Dynamic State algorithms.

Figure 5. Energy consumption comparison.

The virtual grid classification of nodes was a feature in Dynamic State algorithm, which was incorporated into PEGADyn and contributed to the improved energy efficiency of PEGADyn. The virtual classification provided an efficient structure of how each node could transmit its packets in the network, thus limiting excessive node communication and transmission within the network. As can be observed in Figure 5, the Dynamic State algorithm also had better energy savings over PEGASIS.

Minimum Residual Energy

The minimum residual energy indicates the overall lifetime extension of a node in an active state (Valikannu, George & Srivatsa, 2015). From our simulation results and as shown in Figure 6, PEGADyn had a higher amount of residual energy than PEGASIS and Dynamic State, an indication that nodes under PEGADyn experienced longer network lifetime. This is attributed to the classification of nodes into virtual grid and cluster groups, and the use of dCHs for inter-virtual-grid communication among cluster groups to minimize energy consumption. In addition, because every node takes its turn to become either a CH or dCH, this evenly distributes the energy consumption across all nodes in the network.

Figure 6. Residual energy comparison among protocols.

Throughput Ratio

The throughput ratio is the amount of data received at a node’s destination during a time period, which comprises host overhead and contention on the media link. Figure 7 shows the ratio of packets delivered by all three protocols. PEGADyn had consistently higher network throughput ratio than PEGASIS and Dynamic State protocols throughout the simulation period.

Figure 7. Throughput rates of PEGADyn, PEGASIS & Dynamic State.

Packet Drop Ratio

The Packet Drop Ratio shows the rate of dropped/lost packets to the total amount of packets sent. Every transmitted packet has a time-to-live period (TTL) in order to get to its destination (Das & Tripathi, 2018). Upon expiry of this time period and the packet’s inability to get to its destination (due to delay or collision etc.) the packet is dropped. Figure 8 shows PEGADyn having a better (lesser) packet drop rate than PEGASIS and EEDS. Over the simulation period, PEGADyn had drop rate that peaked at 42%, while PEGASIS’s drop rate peaked at 60%. However, EEDS had a higher drop rate of packets peaking at 72%. This clearly demonstrates PEGADyn as a better protocol in comparison to PEGASIS and EEDS.

Figure 8. Packet Drop Ratio with Time.

Simulations Study Analysis

To establish the accuracy of the simulation experiments performed in this research, the Confidence Level (CL), Standard Deviation, Sample Variance and Standard Error of measurements for statistical means were applied to the mean of generated simulation data. The CL presented in this study is based on the mean of the data set, given the sample’s size of 200 simulation runs. The simulation result presumes a Normal distribution from the sample data set analysed, and a 95% confidence level. A 95% confidence level indicates that 95% of our sampled data set contained the population mean with just 5% of our data set possibly outside the population sample.

Table 3 presents the statistical summary of the residual energy per round for all three protocols. The CLs for PEGADyn, PEGASIS and EEDS, which are 0.063, 0.062 and 0.065, respectively, reflect good confidence levels of generated data from simulations performed. In addition, the standard error values for PEGADyn (0.028), PEGASIS (0.027) and EEDS (0.029) and the standard deviations for PEGADyn (0.089), PEGASIS (0.087) and EEDS (0.091) show negligible sampling error.

Table 3. Statistical Summary of Residual Energy Per Round

Furthermore, Table 4 shows the statistical summary of the throughput ratios of PEGADyn, PEGASIS and EEDS. The standard deviation and standard error of measurement of sampled data for all three protocols showed insignificant error margins – PEGADyn (SD=0.089, SE=0.028), PEGASIS (SD=0.087, SE=0.027), EEDS (SD=0.091, SE=0.029) – an indication of consistency of data sampled across all three protocols. In addition, the CLs for all three protocols, including PEGADyn (0.020), PEGASIS (0.005) and EEDS (0.005), further attest to the high confidence of our sampled data.

Table 4. Statistical Summary of Throughput Ratio

Finally, the statistical analysis of the packet drop ratio in Table 5 shows that the standard deviation and standard error of measurement of sampled data for all three protocols also show insignificant error margins – PEGADyn (SD=0.019, SE=0.006), PEGASIS (SD=0.031, SE=0.012), EEDS (SD=0.039, SE=0.012) – an indication of consistency of simulation data across all three protocols. In addition, the CLs for all three protocols, including PEGADyn (0.013), PEGASIS (0.021) and EEDS (0.026), further attest to the high confidence of our sampled data.

Table 5. Statistical Summary of Packet Drop Ratio

Conclusion

In conclusion, this study has presented a hybrid version of PEGASIS and Dynamic State routing protocols to form a new energy efficient routing protocol, PEGADyn. PEGADyn minimizes energy consumption among nodes by creating virtual grids and cluster heads in order to form a hierarchical route path that is energy efficient and balances the energy requirements among nodes in the network. Results from our simulation using NS2 have shown that PEGADyn offers a more promising energy efficient routing protocol for ad hoc networks, especially in extending the lifetime of nodes within the network.

References

Aziz, M. & Al-Akaidi, M. (2007). Security Issues in Wireless Ad Hoc Networks and the Application to the Telecare Project, in Digital Signal Processing, 15^th International Conference on Digital Signal Processing, Cardiff, pp. 491-494.

Boukerche, A., Turgut, B., Aydin, N., Ahmad, M. Z., Bölöni, L. & Turgut, D. (2011). Routing protocols in ad hoc networks: A survey, Computer Networks, 55 (13), 3032-3080, September.

Das, S. K. & Tripathi, S. (2018). Intelligent energy-aware efficient routing for MANET, Wireless Networks, 24 (4), 1139-1159. DOI: 10.1007/s11276-016-1388-7

Gautam, J., Fathima, B. L., Sangeetha, K. & Muzammil, P. M. (2016). Energy Resource Optimization in Wireless Ad-hoc Network Using Dynamic States, International Conference on Engineering and Technology Systems, 13 (2), 57-61.

Heinzelman, W. R., Chandrakasan, A. & Balakrishnan, H. (2000). Energy efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI, USA.

Ilyas, M. (2003). The Handbook of Ad Hoc Wireless Networks. Boca Raton: CRC Press.

Li, T., Ruan, F., Fan, Z., Wang, J. & Kim, J. (2015). An Improved PEGASIS Routing Protocol Based on Neural Network and Ant Colony Algorithm, International Journal of Future Generation Communication and Networking, 8 (6), 149-160.

Lindsey, S. & Raghavendra, C. S. (2002). PEGASIS: Power-efficient gathering in sensor information systems, Proceedings in IEEE Aerospace Conference, Big Sky, MT, USA.

Morris, C. (2018). California's Mendocino Complex Fires Devoured 7,000 Acres While You Slept, Fortune Inc, USA, 7 August. [Online]. Available: http://fortune.com/2018/08‌/07/california-mendocino-complex-fires-latest-numbers/. [Accessed 10 August 2018].

Pattanayak, B. K., Mishra M. K.,Jagadev, A. K., & Nayak A. K. (2011). Power Aware Ad Hoc On-demand Distance Vector (PAAODV) Routing for MANETS, Journal of Convergence Information Technology, 6 (6), 212-220.

Sen, F., Bing, Q. & Liangrui, T. (2011). An improved Energy-Efficient PEGASIS-Based protocol in Wireless Sensor Networks, Eighth International Conference on Fuzzy Systems, Shanghai, China. July. DOI: 10.1109/FSKD.2011.6020058

Sen, S., Clark, J. A. & Tapiador, J. E. (2011). Security threats in mobile ad hoc networks, pp. 128-136 in Security of Self-Organising networks: MANET WSN WMN VANET, A. K. Pathan (Ed.), Boca Raton: Auerbach Publications.

Smith, N. (2018). Timeline: The full story of the Thai cave rescue, Stuff Limited, July. [Online]. Available: https://www.stuff.co.nz/world/105495849/timeline-the-full-story-of-the-thai-cave-rescue [Accessed 10 August 2018].

Son, T.T., Minh, H. L., Sexton, G. & Aslam, N. A. (2014). Novel Encounter-Based Metric For Mobile Ad-Hoc Networks Routing, Ad Hoc Networks (Elsevier), 14, March, 2-14.

Udaykumar K. & Thirugnanam, T. (2015). Analysis of Various Clustering Algorithms in Wireless Sensor Network. International Journal of Computer Science and Information Technologies, 6 (2), 1685-1691.

Valikannu, R., George, A., & Srivatsa, S. K. (2015). A novel energy consumption model using Residual Energy Based Mobile Agent selection scheme (REMA) in MANETs, 2nd International Conference on Signal Processing and Integrated Networks, Noida, India. DOI: 10.1109/SPIN.2015.7095410