A Novel Multi-Objective Optimization-Based Path Formulation for Mobile Sink in Wireless Sensor Networks

Abstract

As a consequence of the limited battery life of sensor nodes ( $\mathbb{S}\mathbb{N}$s) in wireless sensor networks ($\mathbb {WSN}$s), the $\mathbb{S}\mathbb{N}$s nearby the sink exhaust rapidly and exhibit the hot spot problem. The mobile sink ($\mathbb{M}\mathbb{S}$) is proposed to be the solution as it helps in decreasing the energy consumption of $\mathbb{S}\mathbb{N}$s. This further results in an increased network lifetime. Moreover, some sensor applications require a precise data collection time and hence need to optimize the path length of the $\mathbb{M}\mathbb{S}$. This ensures that $\mathbb{M}\mathbb{S}$ will collect data from all the $\mathbb{S}\mathbb{N}$s in a certain threshold time. In the proposed approach, we use the concept of the Voronoi diagram and consider their vertices as the probable set of rendezvous points ($\mathbb{R}\mathbb{P}$s) for the mobile sink to collect data from $\mathbb{S}\mathbb{N}$s. These rendezvous points are further optimized using a cost function which is generated by using several parameters that affect the performance of each rendezvous point. The final set of rendezvous points resulting in the longest path within permissible delay is then finalized. The proposed method is simulated and compared with the existing approaches. The comparison is performed under different parameters like network lifetime, number of hop count, number of alive $\mathbb{S}\mathbb{N}$s, and so on.

1 Introduction

With a large application domain of wireless sensor networks ($\mathbb {WSN}$s) in various sectors such as environment surveillance[1, 2], health care monitoring[3], disaster management[1], target detection[4], and so on, it has attracted many researchers to perform their work in this field. In $\mathbb {WSN}$s, the $\mathbb{S}\mathbb{N}$s are in charge of sensing data from the surroundings and pass it to the sink node/base station either via one hop or multi-hops. The $\mathbb{S}\mathbb{N}$s are equipped with batteries for the power supply and thus saving their energy is considered one of the most critical issues to enhance the lifespan of the network. In multi-hop communication, it may be observed that the $\mathbb{S}\mathbb{N}$s nearer to the sink node act as the bridge between the sink node and the remaining part of the network. This overburdens the data relaying nodes as the rest of the network forwards their data via these nodes. As a result, there is a rapid depletion of their battery’s power and they become dead and $\mathbb {WSN}$ faces the network partition problem. In [5], the author discussed that the $\mathbb{S}\mathbb{N}$s located far from the sink node retain about 93 percent of their initial energy at the time when one hop $\mathbb{S}\mathbb{N}$s deplete completely. Due to network partitioning, the sink node is not receiving any data from the remaining $\mathbb{S}\mathbb{N}$s. Such type of issues occurring in $\mathbb {WSN}$ is defined as a hot spot or sinkhole problem [6, 7]. To resolve the hot spot problem, researchers [4, 8,9,10,11,12,13,14,15,16,17,18] suggested using a mobile sink ($\mathbb{M}\mathbb{S}$) instead of a static sink. An $\mathbb{M}\mathbb{S}$ is a regular sink affixed to a vehicle that moves in the transmission range of every $\mathbb{S}\mathbb{N}$ to gather information directly through them. Hence, $\mathbb{S}\mathbb{N}$ and $\mathbb{M}\mathbb{S}$ communicate directly with each other. This eliminates multi-hop communication and saves a considerable amount of $\mathbb{S}\mathbb{N}$s’ energy and enhances the network’s life. The use of $\mathbb{M}\mathbb{S}$ has some additional benefits, it reduces the flow of a huge amount of data at the vicinity of the sink [19] to avoid congestion, and it also reduces packet losses by minimizing the multi-hop communications[20]. As the $\mathbb{M}\mathbb{S}$ gathers information by reaching very near to each $\mathbb{S}\mathbb{N}$s, there is a decrease in energy depletion of the $\mathbb{S}\mathbb{N}$s, and thus the lifetime of the network increases. However, at the same time, the route length of the $\mathbb{M}\mathbb{S}$ increases resulting in a huge delay in data delivery. Therefore, trajectory design for the $\mathbb{M}\mathbb{S}$ becomes a challenging issue to maintain the balance between different factors like network lifetime, energy consumption, delay, etc. For the trajectory design of $\mathbb{M}\mathbb{S}$, some researchers considered the concept of random mobility [21], and some others considered controlled [22] mobility of the $\mathbb{M}\mathbb{S}$. Although it is simple to use the random mobility approach, it has some demerits like an increase in delay during data collection, uncontrolled behavior of $\mathbb{M}\mathbb{S}$ and also buffer overflow that occurred on the sinks. In the controlled mobility approach, certain researchers suggested that the $\mathbb{M}\mathbb{S}$ collects data by visiting every $\mathbb{S}\mathbb{N}$[23]. Within this approach, balanced energy is maintained in the $\mathbb{S}\mathbb{N}$s and thus there is an increase in network lifetime. However, visiting each $\mathbb{S}\mathbb{N}$ creates a longer path which leads to a large delay in data delivery and this delay increases when it is used for large scale networks. Thus, this approach does not apply to critical applications [24,25,26] where the delay is considered the main concern. Thus, finding a route for $\mathbb{M}\mathbb{S}$ for delay-bound applications becomes a challenging task. In [27, 28], the researchers solve this problem by using the idea of rendezvous points ($\mathbb{R}\mathbb{P}$s) which are the limited number of locations within the network region where the $\mathbb{M}\mathbb{S}$ approaches and gathers information through the $\mathbb{S}\mathbb{N}$s via either single- or multiple-hop communication. Although reducing the number of $\mathbb{R}\mathbb{P}$s by considering some specified positions as the $\mathbb{R}\mathbb{P}$s gives a shorter path length for the $\mathbb{M}\mathbb{S}$, there will be unbalanced energy consumed by the $\mathbb{S}\mathbb{N}$s and thus there is a decrease in network lifespan. Hence, during the process of trajectory design of the $\mathbb{M}\mathbb{S}$, both the factors, i.e. number of $\mathbb{R}\mathbb{P}$s and route length for $\mathbb{M}\mathbb{S}$, are taken into consideration to maintain a balance between them. However, picking the best $\mathbb{R}\mathbb{P}$ positions seems to be an NP-Hard problem. In this paper, we aim to find the smallest set of $\mathbb{R}\mathbb{P}$s from pool of probable $\mathbb{R}\mathbb{P}s$ and then to create the trajectory for the $\mathbb{M}\mathbb{S}$ in such a way that the data collection is performed within permissible time delay which is achieved either by using one-hop or multi-hop data transmission. Figure 1 depicts a route design for an $\mathbb{M}\mathbb{S}$. The selection of $\mathbb{R}\mathbb{P}$’s is done based on some constraints and the $\mathbb{R}\mathbb{P}$ with the least cost function value is selected first. Various parameters are taken into account when designing the cost function to calculate the cost for every probable $\mathbb{R}\mathbb{P}$ location. The parameters have been chosen with the target of decreasing the hop counts as well as decreasing the distance between the $\mathbb{R}\mathbb{P}$ location and $\mathbb{S}\mathbb{N}$s. The major implication aimed from the proposed technique is an improved sensor network life.

Fig. 1

Wireless sensor network with Mobile sink

The route for $\mathbb{M}\mathbb{S}$ is obtained from the final collection of $\mathbb{R}\mathbb{P}$s which is a set of $\mathbb{R}\mathbb{P}$s with the least cost values. In our approach, the concept of the Voronoi diagram and Delaunay triangulation is used where the vertices of the Voronoi diagram and Delaunay triangulation is taken as initial probable locations for the $\mathbb{R}\mathbb{P}$s. The proposed algorithms are simulated, and their outcomes have been compared to the existing approaches such as CCH[29], WRP[4], CB[19], and DBRkM[13] over different performance metrics using MatLab as a simulation tool.

1.1 Contribution

In short, the below points constitute the major contributions of our proposal:

• - In the proposed proposal, we address the issue of the hot spot problem. This is a critical issue in any sensor network deployed in a hostile environment. The hot spot problem leads to a reduced network life.

• - We propose to use the vertices of the Voronoi and Delaunay triangulation to obtain a potential pool of $\mathbb{R}\mathbb{P}$s through which the route of $\mathbb{M}\mathbb{S}$ is designed.

• - We employ a series of metrics to determine the cost of prospective $\mathbb{R}\mathbb{P}$ and then select the most appropriate $\mathbb{R}\mathbb{P}$ from them.

• - The trajectory constructed from the collection of chosen $\mathbb{R}\mathbb{P}$s guarantees the delay bound.

• - The simulation of the proposed algorithms is performed on different network deployment scenarios and compared with the existing works.

• - The simulation results are represented graphically, demonstrating the efficacy of the proposed Multi-objective optimization-based path design algorithms across a variety of performance parameters.

1.2 Paper Organization

The following is the outline of the paper. Section 2 discusses the proposal’s relevant literary works. The idea for using the Voronoi diagram & Delaunay triangulation is highlighted in Sect. 3. Section 4 outlines the preliminary work, as well as the work models. The work model has sections explaining the network model and energy model. Section 5 discusses the problem formulation. It explains several terms used within the paper and provides the pseudo-code along with a flowchart for the proposed scheme. The simulation-based comparison outcomes are shown in Sect. 6. Finally, the graphical conclusion and rationality are presented in Sect. 7.

2 Related Works

Several models for the trajectory design for the $\mathbb{M}\mathbb{S}$ have been developed by researchers [4, 8, 10, 11, 13,14,15,16,17,18, 30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48, 55] for productive and efficient data collection in $\mathbb {WSN}$s. $\mathbb{M}\mathbb{S}$ mobility becomes a significant concern that is usually divided into two groups: spontaneous [21] and controlled mobility [22]. Although it is simple to implement a spontaneous mobility-based strategy, it causes an unnecessarily long delay in the data collection process due to the uncertain path of $\mathbb{M}\mathbb{S}$. It features flaws such as uncontrollable behavior, $\mathbb{S}\mathbb{N}$ buffer overflow, and poor performance. In light of these flaws, the researchers argued for the adoption of controlled mobility to enhance network performance. Although in the case of random mobility, the path of the$\mathbb{M}\mathbb{S}$ is decided based on some pre-specified positions called $\mathbb{R}\mathbb{P}$s [49]. In [49, 50], authors used the stationary route for the $\mathbb{M}\mathbb{S}$ taking the concept of $\mathbb{R}\mathbb{P}$s. Once the route is designed, the $\mathbb{S}\mathbb{N}$s are arranged somewhere along it. The authors categorize $\mathbb{S}\mathbb{N}$s into two classes, within the first category, those $\mathbb{S}\mathbb{N}$s are considered which have direct communication occurring with $\mathbb{M}\mathbb{S}$, and within the second category $\mathbb{S}\mathbb{N}$s away from the route are considered. The $\mathbb{M}\mathbb{S}$ do not come under their communication range, and hence they transmit their information to $\mathbb{M}\mathbb{S}$ via the first category $\mathbb{S}\mathbb{N}$s. Since the path length is fixed and there is no constraint on path length, this approach is not suitable for critical applications where time is considered a critical parameter. In [10], the author proposed a route for $\mathbb{M}\mathbb{S}$ by considering the Hilbert curve in which the $\mathbb{M}\mathbb{S}$ collects data by each $\mathbb{S}\mathbb{N}$ using a single hop. Using such a method shows a longer path for $\mathbb{M}\mathbb{S}$; as a result, there is a large delay in data transmission and so it has no relevance to critical applications. It’s also worth noting that Hilbert’s space-filling curves have isothetic properties which can create needlessly longer pathways for the dense networks. However, this approach can be useful in a dense network, because of the extended network lifetime. During the formation of the $\mathbb{M}\mathbb{S}$ path, the authors in [4, 19] considered the path length issue. Salarian et al. [4] discussed the delay-restricted path using weighted rendezvous planning (WRP) in which every $\mathbb{S}\mathbb{N}$ acquires a weight value. The weight value for an $\mathbb{S}\mathbb{N}$ is determined by measuring the hop length through the closest $\mathbb{R}\mathbb{P}$s as well as by using the node’s packet transmission rate. However, the running time complexity of the algorithm is extremely large, i.e. O($n^{5}$) for n $\mathbb{S}\mathbb{N}$s which is not applicable for the huge $\mathbb {WSN}$s. In [19], the author discussed a cluster-based (CB) approach in which the minimum number of $\mathbb{R}\mathbb{P}$s is calculated based on a binary search technique. Here one node from every cluster is chosen as $\mathbb{R}\mathbb{P}$s for creating the path for the $\mathbb{M}\mathbb{S}$. In [51], the authors used the concept of the voronoi diagram and uses its vertexes as probable potential $\mathbb{R}\mathbb{P}$s positions. In their method, they considered that no two adjacent vertices are selected as $\mathbb{R}\mathbb{P}$s and also they did not consider the transmission range of $\mathbb{S}\mathbb{N}$. As a result, the outcome of their approach gave a large number of $\mathbb{R}\mathbb{P}$s for the dense network with a large path length for $\mathbb{M}\mathbb{S}$, so their method is not applicable for the application where the delay is considered the main concern. In [29], the authors used the concept of the convex hull, a computational geometry approach to produce a certain number of Concentric convex hulls (CCHs) which act as probable routes for the $\mathbb{M}\mathbb{S}$ for the given set of $\mathbb{S}\mathbb{N}s$. They selected the final route for the $\mathbb{M}\mathbb{S}$ from these probable routes based on some optimized criteria. In their work, they do not consider the $\mathbb {TSP}$ concept as used by the many existing proposals. The authors in [13] proposed an algorithm named DBRkM for designing a delay-bound efficient trajectory. This is an effective route-defining technique for $\mathbb{M}\mathbb{S}$ based on $\mathbb{R}\mathbb{P}$s. In their study, they employed a weight function that took numerous network metrics to pick $\mathbb{R}\mathbb{P}s$ efficiently and guarantee complete network coverage. However, in their analysis, they assumed that each $\mathbb{S}\mathbb{N}$ had an equivalent burden of data creation. Our proposed work is inspired by the DBRkM. All the above-discussed methods have successfully created the path for $\mathbb{M}\mathbb{S}$ by taking into account several factors that influence their performance. Unlike the previous techniques, the proposed approach considers the vertices that are formed by the Voronoi diagram over the deployed $\mathbb{S}\mathbb{N}$s as the possible location for the $\mathbb{R}\mathbb{P}$s. The efficacy of every location is evaluated using several parameters to obtain the cost function. Thus, the cost function helps in choosing the lowest set of $\mathbb{R}\mathbb{P}$s from the set of available locations.

Fig. 2

Voronoi approach

3 Outline of Voronoi Diagram and Delaunay Triangulation

3.1 Voronoi Diagram

The Voronoi diagram [52] is a part of computational geometry and is used extensively in the field of architecture, databases, networking, etc. In this paper, we consider the Voronoi diagram to split the entire target region into the Voronoi cells [refer to Fig. 2] based on the placements of the deployed $\mathbb{S}\mathbb{N}$s. Let $\mathbb {S}$= { $SN_{1}$, $SN_{2}$,..., $SN_{n}$ } represents a collection of n $\mathbb{S}\mathbb{N}$s. Now, the Voronoi diagram for the set $\mathbb {S}$ spits the target region into n Voronoi cells known as Vor($SN_{i}$) where, $1\le i \le n$, in such a way that every $\mathbb{S}\mathbb{N}$ comes under any of the one Voronoi cells and also, any points within the cell Vor($SN_{i}$) are closer to $SN_{i}$, but not closer to any other sensor node $SN_{j}$, $\forall SN_{j} \in \mathbb {S}$ and $j \ne i$. Now, let d(a, b) denotes the distance between any two locations a and b in the target region, then the location c lies in the cell Vor($SN_{i}$), iff $d(c,SN_{i}) < d(c,SN_{j})$ for any $SN_{j} \in \mathbb {S}$ and $j \ne i$. It’s worth noting that the Voronoi diagram for any given set of points would be unique. It has been seen that the areas of the Voronoi cells might be bounded or unbounded. A Voronoi vertex is a point in a Voronoi diagram that connects three or more Voronoi cells. If the number of points in the Voronoi diagram is p, then the maximum number of Voronoi vertices is $2 * p - 5$.

3.2 Delaunay Triangulation

Delaunay triangulation [52] represents the dual graph for the Voronoi diagram for a similar collection of locations. According to the Delaunay condition, Delaunay triangulation is a triangular mesh that links a collection of points in the plane in such a way that no point in the collection comes under any circle of triangle mesh. Through the Delaunay triangulation [see Fig. 3] method, minimal triangles’ angles so formed in the triangular mesh are maximized, and as a result, the narrow triangles are avoided. Let $\mathbb {S}$ = { $SN_{1}$, $SN_{2}$,..., $SN_{n}$} represent a collection of n sensor nodes. Therefore, the Delaunay triangulation for $\mathbb {S}$ must satisfy the aforementioned Delaunay criterion.

Fig. 3

Delaunay approach

Any triangle’s circumcircle has just three points. Therefore, whenever 4 or more four points are present upon a similar circle, Delaunay triangulation is not thought to be unique. The placement of a point within the circumcircle of a triangle with three vertices may be determined for a given collection of points by utilizing the condition for the creation of a Delaunay triangle. The positions of the $\mathbb{S}\mathbb{N}$s serve as the Delaunay vertices in Delaunay triangulation. We further explored the centroid of this triangulation as a potential position and called it Delaunay Centroid.

4 Preliminaries

4.1 Basic Assumptions

In this paper, we propose a novel strategy for route formulation of an $\mathbb{M}\mathbb{S}$ effective in delay constrained work environment. To illustrate the efficacy of this strategy, we consider the following environmental constraints:

• - Each $\mathbb{S}\mathbb{N}$ has a spherical sensing range and is identifiable by a unique ID in the network.

• - Most of the time, the $\mathbb{S}\mathbb{N}$s are deployed randomly using airplanes, drones, helicopters, etc. After deployment, it is assumed that the positions of these $\mathbb{S}\mathbb{N}$s are not changed i.e. they remain stationary.

• - The centralized monitoring system knows the positions of every $\mathbb{S}\mathbb{N}$s through the GPS component which is embedded with the $\mathbb{S}\mathbb{N}$s.

• - The power source for all the $\mathbb{S}\mathbb{N}$s is the same.

• - Once the sensor’s power source is depleted, it is considered inactive or dead.

• - While communicating with other nodes, each $\mathbb{S}\mathbb{N}$ spends some energy and is determined by the distance between these two nodes.

• - The centralized system is responsible for determining the route for the $\mathbb{M}\mathbb{S}$. Once calculated using the proposed algorithm, the $\mathbb{M}\mathbb{S}$ follows the route and has no power constraints.

• - Whenever $\mathbb{M}\mathbb{S}$ arrives at the $\mathbb{R}\mathbb{P}$, it gathers information from nearby $\mathbb{S}\mathbb{N}$s.

4.2 Work Model

4.2.1 Network Model

In our proposal, we assume that the considered $\mathbb {WSN}$ is homogenous and is made up of a random collection of $\mathbb{S}\mathbb{N}$s distributed over the monitored zone. The data produced by the $\mathbb{S}\mathbb{N}$s are accumulated by the $\mathbb{M}\mathbb{S}$. The $\mathbb{M}\mathbb{S}$ moves at a steady speed, and it is considered as it has sufficient energy to run constantly. The following are a few more assumptions that were employed in this proposal:

• - Any communication among the pair of nodes takes place through the wireless networks, and the communication takes place only when both nodes come under the transmission range of each other.

• - The network is assumed to be operational up to the time when half of the total number of $\mathbb{S}\mathbb{N}$s are alive.

• - The wireless links have been considered uniform so that every node can calculate the approximate distance from another node using the incoming signal intensity [17].

• - $\mathbb{M}\mathbb{S}$ is aware of where $\mathbb{S}\mathbb{N}$s are located.

• - $\mathbb{M}\mathbb{S}$ follows a pre-defined path consisting of $\mathbb{R}\mathbb{P}$. The $\mathbb{M}\mathbb{S}$ on reaching any of the $\mathbb{R}\mathbb{P}$ communicates with the $\mathbb{S}\mathbb{N}$s nearby that $\mathbb{R}\mathbb{P}$. The $\mathbb{S}\mathbb{N}$s then start sending their data to $\mathbb{M}\mathbb{S}$ either through one-hop or by multiple-hop transmission.

• - We consider the data collection time called the halt time of the $\mathbb{M}\mathbb{S}$ on every $\mathbb{R}\mathbb{P}$ to be very small and is regarded as adequate for data collection.

4.2.2 Energy Model

The energy model followed in the proposed work utilizes [53] energy strategy for calculating and updating the energy consumption of the $\mathbb{S}\mathbb{N}$s. The use of energy in data transmission between $\mathbb{S}\mathbb{N}$s is depicted in Fig. 4. The energy consumption in $\mathbb {WSN}$s is generally divided into two components: transmitter energy and receiver energy. The transmitter energy may be determined by taking into account the energy needed for signal creation and amplification. For any $\mathbb{S}\mathbb{N}$’s amplification, power is directory proportional to the transmission distance ’d’ and is limited by the transmission distance threshold $d_{th}$. Thus, the energy required for the amplification is calculated based on the separation between the transmission device and the reception device. If this separation is smaller as compared to a threshold $d_{th}$ value, a free space (fs) approach is considered, and if not, the multipath (mp) approach is considered in calculating the amplifier’s energy. The energy of the amplifier $E_{Tx-amp}$ might be $n \epsilon _{fs}d^2$ or $n \epsilon _{mp}d^4$ depending upon the free space or multipath conditions. Thus energy consumed during transmission ($E_{Tx}$) for n bit of data through an $\mathbb{S}\mathbb{N}$ is evaluated as follows:

$$\begin{aligned} E_{Tx}(n,d)= & {} E_{Tx-elec}(n)+E_{Tx-amp}(n,d) \nonumber \\= & {} n \times E_{elec} + n \epsilon _{fs}d^2, d < d_{th} \end{aligned}$$

(1)

$$\begin{aligned} E_{Tx}(n,d)= & {} E_{Tx-elec}(n)+E_{Tx-amp}(n,d) \nonumber \\= & {} n \times E_{elec} + n \epsilon _{mp}d^4, d \ge d_{th} \end{aligned}$$

(2)

In equation (1), free space model is considered, whereas equation (2) considered the multipath model. Energy consumed while receiving n bit data packet is expressed in equation (3).

$$\begin{aligned} E_{Rx}(n)=n \times E_{elec} \end{aligned}$$

(3)

where the $d_{th}$ is given by $d_{th} = \sqrt{ \epsilon _{fs} / \epsilon _{mp} }$

Table 1 Notations used

4.3 Terminologies and Problem Formulation

Table 1 shows the notations used to describe the terminology used to formulate the proposed algorithms.

The Static $\mathbb{S}\mathbb{N}s, \mathbb {S} = \{ SN_{1},SN_{2},......,SN_{n} \}$ are being placed to monitor a certain region. It is assumed that the $\mathbb{S}\mathbb{N}$s are transmitted just one packet [54] of their sensed data to the $\mathbb{M}\mathbb{S}$ in every data collecting cycle of the $\mathbb{M}\mathbb{S}$. The $\mathbb{M}\mathbb{S}$ travels across the targeted territory on a predetermined route, pausing at several rendezvous points ($\mathbb{R}\mathbb{P}$s). When the $\mathbb{M}\mathbb{S}$ arrives at any $\mathbb{R}\mathbb{P}$, it collects the sensed data through the $\mathbb{S}\mathbb{N}$s via one-hop or multi-hop communications, as shown in Fig. 1. The set of probable $\mathbb{R}\mathbb{P}$s in our approach is considered as the vertices of the Voronoi diagram and then these vertices are optimized using numerous parameters. The terminologies used to describe the parameters are presented in Table 1.

Definition 1

(Data Transmission Length- $\mathbb {DTL}$) The data sensed by the $\mathbb{S}\mathbb{N}$s is transmitted to the $\mathbb{M}\mathbb{S}$ through the one-hop or multiple-hop transmission. The term $\mathbb {DTL}$ represents the length of separation between the data-sharing entities. The energy spent by the $\mathbb{S}\mathbb{N}$s in the data propagation is proportional to the $\mathbb {DTL}$. Within our proposed approach, the collection of $\mathbb{R}\mathbb{P}$s is selected in such a way that the sum of $\mathbb {DTL}$ is minimum.

Fig. 4

Energy model

Definition 2

(Hop Count-$\mathbb{H}\mathbb{C}$) In the case of delay-bound application, the $\mathbb{M}\mathbb{S}$ cannot collect data by visiting every $\mathbb{S}\mathbb{N}$ in the target area therefore some of the $\mathbb{S}\mathbb{N}$s transmit sensed information to the $\mathbb{M}\mathbb{S}$ via the multiple-hop communications. As a result, there is an increase in the network’s total hop count. Because the total energy expended by $\mathbb{S}\mathbb{N}$s is directly proportional to the network’s hop count, within our proposed approach, we intend to decrease the number of hop counts.

Definition 3

(Centre of the target area - ($\mathbb {CTA}$) Generally, the $\mathbb{S}\mathbb{N}$s are placed within the target area, and the $\mathbb{M}\mathbb{S}$ reached there to gather data from the $\mathbb{S}\mathbb{N}$s. To collect consistent and correct data, the $\mathbb{M}\mathbb{S}$ should have a path around the $\mathbb {CTA}$. The co-ordinate of $\mathbb {CTA}$ is obtained from the coordinates of the deployed $\mathbb{S}\mathbb{N}$s in the target region. The average of the x- and y-coordinates of the $\mathbb{S}\mathbb{N}$s give the coordinates of $\mathbb {CTA}$ which are calculated using Equation (4) as follows:

$$\begin{aligned} x_{\mathbb {CTA}} = \frac{1}{n}\sum _{i=1}^{n}x_{i} , y_{\mathbb {CTA}} = \frac{1}{n}\sum _{i=1}^{n}y_{i} \end{aligned}$$

(4)

Definition 4

(Subscribing Edges—$\mathbb{S}\mathbb{E}$) Since $\mathbb{S}\mathbb{N}$s are used to monitor the target area, their position coordinates are used to find out the subscribed area. This area is indicated by eight points whose coordinates are obtained from the $\mathbb{S}\mathbb{N}$s’ position coordinates. These eight points are represented as ($x\_min$,$y\_min$) ($x\_min$,$y\_max$/2), ($x\_min$,$y\_max$ ), ($x\_max/2$,$y\_max$ ), ($x\_max$,$y\_max$), ($x\_max$, $y\_max/2$), ($x\_max$,$y\_min$), ($x\_max/2$,$y\_min$) where $x\_min$ (or $x\_max$) represents the minimum (or maximum) values of x-coordinates and $y\_min$ (or $y\_max$) represents the minimum (or maximum) values of y-coordinates, respectively, of the deployed $\mathbb{S}\mathbb{N}$s in the target area.

Definition 5

(Direct communicating $\mathbb{S}\mathbb{N}$s—$\mathbb {DCSN}$) The collection of $\mathbb{S}\mathbb{N}$s that directly communicate with any $\mathbb{R}\mathbb{P}$ is referred to as direct communicating $\mathbb{S}\mathbb{N}$s.

Definition 6

(Optimal Route Radius- $\mathbb {ORR}$) In delay-aware applications, finding a route for $\mathbb{M}\mathbb{S}$ is a major challenge. Any route exceeding or underneath $\mathbb {ORR}$ increases the network’s overall Hop Count which leads to more energy depletion by the $\mathbb{S}\mathbb{N}$s. Consequently, there is a reduction in network lifespan. Thus, a circular path is chosen in the target area in such a way that this path is not very near or far from the $\mathbb {CTA}$ and $\mathbb{S}\mathbb{E}$. The radius of the circular path $\mathbb {ORR}$ is obtained by taking the average of mid-distance between $\mathbb {CTA}$ and $\mathbb{S}\mathbb{E}$.

$\mathbb {ORR}$ is mathematically formulated in Equation (5).

$$\begin{aligned} \mathbb {ORR}=\frac{\sum _{i=1}^{x}\frac{dist(\mathbb {CTA},\mathbb{S}\mathbb{E}_{i})}{2}}{x} \end{aligned}$$

(5)

where x represents the number of extreme vertices = 8.

Definition 7

(Coverage) An $\mathbb{S}\mathbb{N}$ is said to be covered when a minimum one $\mathbb{R}\mathbb{P}$s comes under its communication range.

Definition 8

(Indegree) The total number of $\mathbb{S}\mathbb{N}$s that communicate with a particular $\mathbb{R}\mathbb{P}$ is said to be indegree for that $\mathbb{R}\mathbb{P}$.

Definition 9

(Maximum Tour Length Permitted—$\mathbb {MTLP}$) The maximum permitted tour length may be computed using the speed of $\mathbb{M}\mathbb{S}$ for the specified maximum acceptable delay $\mathbb{M}\mathbb{D}$ which is calculated in Equation (6).

$$\begin{aligned} \mathbb {MTLP}=\mathbb{M}\mathbb{D} \times \mathbb {SMS} \end{aligned}$$

(6)

Definition 10

(Traveling salesman path—$\mathbb {TSP}$) It is a function that receives a collection of points as input and gives the shortest route for the given points.

5 Proposed Method

5.1 Voronoi Diagram-Based Technique

Based on the positions of $n \ \ \mathbb{S}\mathbb{N}$s, the whole target area is divided into n Voronoi cells and the vertices of the Voronoi cell are considered as the set of potential $\mathbb{R}\mathbb{P}$s. Now, we select the $\mathbb{R}\mathbb{P}$’s from the set of potential $\mathbb{R}\mathbb{P}$s in incremental order. Now, the $\mathbb{R}\mathbb{P}$s will be chosen based on the constraints that the maximum $\mathbb{S}\mathbb{N}$s are covered in the one-hop communication range and the average hop distance is minimum. Now, at end of every round, we apply the $\mathbb {TSP}$ on the selected $\mathbb{R}\mathbb{P}$s to get the path for $\mathbb{M}\mathbb{S}$. This process is repeated to select the next $\mathbb{R}\mathbb{P}$ until the length of the route is not greater than the permissible delay-bound path. During the selection of any $\mathbb{R}\mathbb{P}$s, if the path length is found to be greater than the permissible delay-bound threshold value, then that $\mathbb{R}\mathbb{P}$ is discarded from the set of $\mathbb{R}\mathbb{P}$s. The selection of $\mathbb{R}\mathbb{P}$s is performed using the cost function which is dependent on various parameters. To find the cost function for any $\mathbb{R}\mathbb{P}$, the following parameters are taken into consideration:

(i) Numbers of Direct communicating $\mathbb{S}\mathbb{N}$s- $\mathbb {DCSN}$: In our proposed work, the $\mathbb{R}\mathbb{P}$s are selected from the pool of potential $\mathbb{R}\mathbb{P}$s at which $\mathbb{M}\mathbb{S}$ can halt and collect data from a maximum number of $\mathbb{S}\mathbb{N}$s. At the same time, it is considered that the number of $\mathbb{R}\mathbb{P}$s is kept as high as possible to balance the network traffic. Thus, the $\mathbb{R}\mathbb{P}$ position which covers the maximum number of $\mathbb{S}\mathbb{N}$s in one hop is considered the best $\mathbb{R}\mathbb{P}$ and it is assigned a least cost function value. It is mathematically represented in Equation (7) as follows:

$$\begin{aligned} \mathbb{C}\mathbb{T}(i) \propto \frac{1}{\mathbb {DCSN}_i} \end{aligned}$$

(7)

(ii) Average $\mathbb {DTL}$—With the larger value of $\mathbb {DTL}$, more energy is consumed by the $\mathbb{S}\mathbb{N}$ during the data transmission and reception. The larger the communication distance between $\mathbb{S}\mathbb{N}$ and $\mathbb{R}\mathbb{P}$, the more energy is consumed in data communication; as a result, network lifetime decreases. Thus, a larger average $\mathbb {DTL}$ value for any $\mathbb{R}\mathbb{P}$ gives a high-cost function value for that potential $\mathbb{R}\mathbb{P}$ which is mathematically expressed by using Equation (8)

$$\begin{aligned} \mathbb{C}\mathbb{T}(i) \propto \ \mathbb {AVG}(\mathbb {DTL}_i) \end{aligned}$$

(8)

Fig. 5

The proposed algorithm’s flowchart

(iii) Distance from $\mathbb {ORR}$ ($\mathbb {DORR}_{i}$): In the proposed work, our motive is to choose the $\mathbb{R}\mathbb{P}$s with least hop count. Thus we try to reduce the multi-hop communication which saves a considerable amount of energy leading to an increase in network lifetime. Thus, the placements of $\mathbb{R}\mathbb{P}$s are not very near or far from the $\mathbb {ORR}$ it may be somehow closer to the $\mathbb {ORR}$. Therefore, the cost function value of the $\mathbb{R}\mathbb{P}$ is assigned minimum when the $\mathbb{R}\mathbb{P}$ is the least distance from $\mathbb {ORR}$ which we represented mathematically in Equation (9).

$$\begin{aligned} \mathbb{C}\mathbb{T}(i) \propto \ \mathbb {DORR}_{i} \end{aligned}$$

(9)

(iv) The numbers of $\mathbb{S}\mathbb{N}$s handled, $\mathbb {SNH}_{i}$: In our proposed work, we consider the delay bound path so some $\mathbb{S}\mathbb{N}$ convey their data to the $\mathbb{R}\mathbb{P}$ via multiple-hop. Thus, we aim to select the $\mathbb{R}\mathbb{P}$ from the potential $\mathbb{R}\mathbb{P}$s which have the minimum number of multi-hop communication. The relationship between $\mathbb{C}\mathbb{T}$(i) and the maximum number of $\mathbb{S}\mathbb{N}s$ handled $\mathbb {SNH}_i$ may be expressed mathematically in Equation (10).

$$\begin{aligned} \mathbb{C}\mathbb{T}(i) \propto \frac{1}{\mathbb {SNH}_i} \end{aligned}$$

(10)

To create a single cost function, we must combine all of the parameters stated in equations (7),(8),(9), and (10). Furthermore, because each of these metrics has a distinct range, they must all be normalized. For the normalization, the range of the metrics is taken from 0 to 1. The normalized value is described as follows.

$$\begin{aligned} \mathbb {DCSN}_i^{'}= & {} \frac{|\mathbb {DCSN}_i|}{maximum(|\mathbb {DCSN}|)} \end{aligned}$$

(11)

$$\begin{aligned} \mathbb {AVG}(\mathbb {DTL}_i)^{'}= & {} \frac{\mathbb {AVG}(\mathbb {DTL}_i)}{maximum(\mathbb {AVG}(\mathbb {DTL}))} \end{aligned}$$

(12)

$$\begin{aligned} \mathbb {DORR}_i^{'}= & {} \frac{\mathbb {DORR}_i}{maximum(\mathbb {DORR})} \end{aligned}$$

(13)

$$\begin{aligned} \mathbb {SNH}_i^{'}= & {} \frac{\mathbb {SNH}_i}{maximum(\mathbb {SNH})} \end{aligned}$$

(14)

Now, bringing the equations (11),(12),(13) and (14) together, we get Equation (15).

$$\begin{aligned}{} & {} \mathbb{C}\mathbb{T}(i) \propto \frac{\mathbb {AVG}(\mathbb {DTL}_i)^{'} * \mathbb {DORR}_i^{'}}{\mathbb {DCSN}_i^{'} * \mathbb {SNH}_i^{'} } \end{aligned}$$

(15)

$$\begin{aligned}{} & {} \mathbb{C}\mathbb{T}(i)=ct * \frac{\mathbb {AVG}(\mathbb {DTL}_i)^{'} * \mathbb {DORR}_i^{'}}{\mathbb {DCSN}_i^{'} * \mathbb {SNH}_i^{'} } \end{aligned}$$

(16)

where ct is a constant of proportionality whose value is taken as unity because the cost function used here is only for the comparisons, without considering any generality. Therefore,

$$\begin{aligned} \mathbb{C}\mathbb{T}(i)= \frac{\mathbb {AVG}(\mathbb {DTL}_i)^{'} * \mathbb {DORR}_i^{'}}{\mathbb {DCSN}_i^{'} * \mathbb {SNH}_i^{'} } \end{aligned}$$

(17)

This proposal’s flowchart is shown in Fig. 5.

Table 2 Simulation parameters

The pseudo-code for the proposed algorithm is presented in Algorithm 1.

We utilize the above algorithm with three different input potential positions of RPs. The proposed algorithm with Voronoi vertices as the potential positions is named as MOOVor. However, the other two utilizing the vertices of Delaunay Triangulation and Delaunay Centroid are named as MOODel and MOODelCen, respectively. The above algorithms aim to minimize the path length of $\mathbb{M}\mathbb{S}$ considering a cost function. This cost function is fabricated using different parameters affecting the decision for the selection of $\mathbb{R}\mathbb{P}$s.

6 Simulation Results

Under this section, we first define the simulation scenario and thereafter give the performance evaluation using extensive simulation of the proposed and other existing algorithms.

6.1 Simulation Setup

We used MATLAB R2012a 64-bit (win64) to execute the comprehensive simulations of the proposed and existing approaches on the Windows 10 platform. The computer has 6 GB of RAM, a 1.60 GHz processor, and an Intel Core i5-8265U CPU. In the proposed work, we consider homogeneous $\mathbb {WSN}$s in which the route for the $\mathbb{M}\mathbb{S}$ is constructed. The simulation results of the proposed algorithms were compared with several existing algorithms such as CCH (Concentric Convex Hull)[29], WRP (Weighted rendezvous point)[4], CB(cluster-based algorithm)[19], and DBRkM (delay-bound reduced k-means)[13]. To provide a fair comparison, the proposed as well as the existing approaches are simulated over a similar network configuration. Considering random deployment, the results are recorded as the average of 15 simulations runs. This average of 15 simulation is motivated by several existing works [13, 29]. Moreover, the argument for using the number 15 is the observation that output begins to converge after these many runs and has a minute or no modification further in the results of further simulations. The simulation parameters are listed in Table 2. These parameters are inspired by some of the existing research works such as [10, 14].

Fig. 6

Simulation instances of CCH, WRP, CB, DBRKM, MOOVor, MOODel, and MOODelCen (In order of Left to right, top to down)

The following metrics were used to evaluate the algorithms’ performance.

• 1. Total Number of $\mathbb{R}\mathbb{P}$s: In the proposed work, $\mathbb{R}\mathbb{P}$ is considered as the specific position in the target area where $\mathbb{M}\mathbb{S}$ stays for a sojourn time and collects data from the neighboring $\mathbb{S}\mathbb{N}$s. The cumulative sojourn time is negligible in comparison with the overall permitted delay. With the increase in the number of $\mathbb{R}\mathbb{P}$s, the number of $\mathbb{S}\mathbb{N}$s interacting in a single hop increases; as a result, there is an increase in the network lifespan. So we aim to increase the number of $\mathbb{R}\mathbb{P}$s as compared to the other existing approaches.

• 2. Number of Hop Count: The direct data transmission from an $\mathbb{S}\mathbb{N}$ to an $\mathbb{M}\mathbb{S}$ is referred to as a one-hop communication. However, some of the $\mathbb{S}\mathbb{N}$s send their data to the $\mathbb{M}\mathbb{S}$ via multi-hop communication in which the intermediate nodes act as relay nodes. Thus, some of the $\mathbb{S}\mathbb{N}$s consume more energy as they transmit their sensed data as well as relay data of other $\mathbb{S}\mathbb{N}$s. Thus, as the number of hops increases to deliver data to $\mathbb{M}\mathbb{S}$, the energy consumption of the network also increases. Hence, we aim to reduce the number of hops in our proposed technique.

• 3. Network Lifetime: The network lifetime is defined in terms of rounds, where the round is the time duration between two consecutive data transfers that occurs between $\mathbb{S}\mathbb{N}$s to $\mathbb{M}\mathbb{S}$. Within our proposed work, we defined the lifetime of the network as the total number of rounds until which half of the $\mathbb{S}\mathbb{N}$s completely exhaust their energy. Since $\mathbb {WSN}$s are expensive, for maximum utilization, we aim to improve the network lifetime.

• 4. Number of Alive Nodes: The energy consumption of each $\mathbb{S}\mathbb{N}$ is different as their distance from $\mathbb{R}\mathbb{P}$ are different. Also, some of the $\mathbb{S}\mathbb{N}$s perform some extra work as they act as a relay node to relay the data to other $\mathbb{S}\mathbb{N}$s and consume more of their energy than other $\mathbb{S}\mathbb{N}$s. Thus, due to the different roles and positions of the $\mathbb{S}\mathbb{N}$s, the energy depletion of each $\mathbb{S}\mathbb{N}$s is different for every round. Due to variations in their energy consumption, some of the $\mathbb{S}\mathbb{N}$s become non-functional very early. At every time period, an algorithm with the fewest non-functional $\mathbb{S}\mathbb{N}$s is preferred better than the other algorithms.

• 5. Energy Consumption: It is the average of the total energy used by every $\mathbb{S}\mathbb{N}$ until a certain round. We favor network designs that consume the least amount of energy, as this might result in a longer network lifetime.

• 6. Standard Deviation of Remaining Energy: It is defined as the standard deviation of residual energy of $\mathbb{S}\mathbb{N}$ in each round from the average remaining energy of the $\mathbb{S}\mathbb{N}$ of the whole network. A network with the lowest standard deviation of residual energy is always preferable since it can result in a longer network life.

6.2 Simulation Results

In the proposed technique, we consider the $\mathbb{S}\mathbb{N}$s are deployed randomly in the $\mathbb{T}\mathbb{A}$. Figure 6 depicts the simulated instance of $\mathbb{S}\mathbb{N}$s with random deployment. The simulation result represented in the graphs is the mean of 15 different simulations run. The proposed approach works for route designing of $\mathbb{M}\mathbb{S}$ considering a delay-bound environment. The existing and the proposed algorithms were simulated in MATLAB, and the results are then compared with the different existing algorithms using several performance metrics.

6.2.1 Comparison in Terms of the Total Number of $\mathbb{R}\mathbb{P}$s

The lifetime of the network increases with the increase in the number of one-hop communication. However, the number of one-hop communication increases with the increase in the number of $\mathbb{R}\mathbb{P}$s. Figures  and depict the plotted graph between the total number of expected $\mathbb{R}\mathbb{P}$s for all the proposed and existing algorithms over different numbers of $\mathbb{S}\mathbb{N}$s and variable communication ranges. Figure  demonstrates that the MOOVor demonstrates the best result among the proposed methods. This method is 17.3%, 237%, 28.5%, and 116% better than CCH, WRP, CB, and DBRKM respectively. Moreover, Fig.  exhibits that MOODelCen performs best among the proposed methods. It outperforms CCH by 38%, WRP by 246%, CB by 48.50%, and DBRKM by 108%. The rationality of the improved performance is the symmetrical locations for the probable set of potential $\mathbb{R}\mathbb{P}$s.

Fig. 7

Total number of $\mathbb{R}\mathbb{P}$s for various algorithms with varying numbers of $\mathbb{S}\mathbb{N}$s

Fig. 8

Total number of $\mathbb{R}\mathbb{P}$s for various algorithms with a varying communication range of $\mathbb{S}\mathbb{N}$s

6.2.2 Comparison in Terms of Hop Count

The $\mathbb{S}\mathbb{N}$s consume most of their energy during the data transmission, and the amount of data packet transmission increases with the increase in hop counts. Hence, the researchers aim to reduce the number of hop counts. Figures 9 and 10 depict the plotted graph between the total number of Hop counts for all the proposed and existing algorithms over different numbers of $\mathbb{S}\mathbb{N}$s and various communication ranges. The analysis clearly shows that the proposed Delaunay centroid, Voronoi diagram, and Delaunay triangulation techniques outperform the existing algorithms. However, the MOODelCen performs the best. It outperforms CCH, WRP, CB, and DBRKM with a percentage of 11.8%, 40.2%, 21%, and 15.3%, respectively, for different SNs deployment and with 23.4%,150 %,29.6%, and 20.4%, respectively, for different communication ranges. The reason for such outcomes is the cost function that aims to select $\mathbb{R}\mathbb{P}$s based on the least distance from $\mathbb{S}\mathbb{N}$s.

Fig. 9

Hop counts for various algorithms with varying numbers of $\mathbb{S}\mathbb{N}$s

Fig. 10

Hop counts for various algorithms with a varying communication range of $\mathbb{S}\mathbb{N}$s

6.2.3 Comparison in Terms of Network Lifetime

The network lifetime of a $\mathbb {WSN}$ is calculated as the number of rounds until which half of the $\mathbb{S}\mathbb{N}$s are operational. Figures 11 and 12 show the results of simulating the network lifespan for all the proposed and existing algorithms using various node densities and communication ranges. The graphs illustrate that the proposed algorithms have a longer network lifetime in terms of the number of rounds than the other existing approaches. Moreover, MOODelCen has registered the best result among the proposed methods. This method outperforms the existing CCH, WRP, CB, and DBRKM algorithms by 0.8%, 5%, 2.8%, and 2.5%, respectively, over different SNs deployment. For different communication ranges, the MOODelCen performs 1.5%, 5.0%, 2.2%, and 2.9% better than CCH, WRP, CB, and DBRKM, respectively. The result acquired is due to the assured least hop counts with the proposed algorithm.

Fig. 11

Network lifetime for various algorithms with varying numbers of $\mathbb{S}\mathbb{N}$s

Fig. 12

Network lifetime for various algorithms with a varying communication range of $\mathbb{S}\mathbb{N}$s

6.2.4 Comparison in Terms of Energy Consumption

It is typically preferred to lengthen the network lifetime to enhance network performance. It is feasible if the $\mathbb{S}\mathbb{N}$s’ energy consumption is maintained to a minimum, which is accomplished by effective network configuration. Figure 13 shows the average energy consumption of $\mathbb{S}\mathbb{N}$s for the number of rounds in the network. The graph clearly shows that the proposed algorithm performs better as compared to other existing algorithms and consumes the least amount of energy at the end of every round.

Fig. 13

Average energy consumption for various algorithms with varying number of rounds

6.2.5 Comparison in Terms of Standard Deviation of Remaining Energy

Generally in the case of uniformly distributed $\mathbb {WSN}$, every $\mathbb{S}\mathbb{N}$ is anticipated to use the same quantity of energy in every round, resulting in an equal amount of residual energy, which contributes to the network’s smooth operation. However, in the real-world scenarios, we have to randomly deploy the $\mathbb{S}\mathbb{N}$s. This leads to a different distance between each $\mathbb{S}\mathbb{N}$s and the respective $\mathbb{R}\mathbb{P}$s. As a result, there is a variation in energy consumption, correspondingly the variation in residual energy of the $\mathbb{S}\mathbb{N}$s after every round. In our proposed work, we consider the standard deviation of remaining energy which is defined as the difference between the residual energy of every $\mathbb{S}\mathbb{N}$ and the average residual energy of each $\mathbb{S}\mathbb{N}$s in the network. Figure 14 depicts the average standard deviation of $\mathbb{S}\mathbb{N}$’s residual energy for the random deployment of $\mathbb{S}\mathbb{N}$s. The graph clearly shows that the residual energy in the proposed algorithm is more balanced than the existing techniques.

Fig. 14

Standard deviation of $\mathbb{S}\mathbb{N}$s’ remaining energy for various algorithms

Fig. 15

Number of alive SNs for first 10000 rounds with various algorithms

6.2.6 Comparison in Terms of Number of Alive Nodes

Figure 15 depicts the simulation outcome of the number of alive $\mathbb{S}\mathbb{N}$s during the first 10,000 rounds of the random deployment of $\mathbb{S}\mathbb{N}$s. The graph shows that over the majority of the rounds, the number of alive $\mathbb{S}\mathbb{N}$s is slightly superior to the existing algorithms. The reason for the better result of our proposed algorithm is the symmetry in the $\mathbb{R}\mathbb{P}$ selection which forces the $\mathbb{S}\mathbb{N}$s to consume energy in a balanced manner [11, 55].

7 Conclusion and Future Work

In this paper, we discussed the hot spot problem and proposed an $\mathbb{M}\mathbb{S}$-based solution to solve it. We designed an algorithm for generating a delay constraint energy-efficient path for the $\mathbb{M}\mathbb{S}$ using the concept of $\mathbb{R}\mathbb{P}$s. We considered the vertices of the Voronoi diagram as the set of probable $\mathbb{R}\mathbb{P}$s. This set of $\mathbb{R}\mathbb{P}$s is then optimized using a cost function. This is calculated by considering various parameters affecting the performance of $\mathbb{R}\mathbb{P}$s. The $\mathbb{R}\mathbb{P}$s are selected in the increasing order of their cost functions, and then the $\mathbb {TSP}$ algorithm is applied to obtain the optimized path of $\mathbb{M}\mathbb{S}$ under the delay-bound constraint. The simulation of the proposed algorithms and the existing algorithms are done and then compared with other existing algorithms. The comparison results under various parameters were plotted graphically. They exhibit that the proposed work performs better than the existing techniques. In further, we would like to use multiple $\mathbb{M}\mathbb{S}$ to enhance the performance of the network in the case of delay-bound applications.