1 Introduction

Wireless sensor networks (WSNs) are composed of a finite set of sensor nodes (SN), and each node collects the stockpile data from the place where it was deployed and transmit it to the base station (BS) or sink (Akyildiz et al. 2002; Praveen Kumar et al. 2019; Cui et al. 2020; Sah and Amgoth 2020; Bhola et al. 2020). The data communications between the SN and BS uses either direct or multi-hop manner. Due to the energy constraint of the SNs, a multi-hop interface consumes more energy during the data transmissions (Yetgin et al. 2017). Notably, the SNs near the BS are more affected than the other nodes in the network, leading to the energy-hole problem (Salarian et al. 2014; Wen et al. 2017; Praveen Kumar et al. 2018; Zhao et al. 2020). The energy-hole problem detaches the sink from network and stops the data gathering process. Therefore, it is imperative to balance the energy of the SNs among them to prolong the network lifetime and data gathering process. However, using single-hop communication avoids the hotspot problem, and placing the BS with this requirement is very difficult. A mobile sink (MS) has been initiated to collect the data from the SNs by traveling over the network periodically. Visiting every node in the network is not a feasible solution, and it leads to an unacceptable delay of the MS.

The MS can visit a set of SNs instead of visiting all the nodes in the WSN to avoid delay of data collection called the rendezvous points (RPs) (Wen et al. 2017; Roy et al. 2020; Habib et al. 2018; Singh and Kumar 2020). The non-RPs of the WSNs transmit their stockpile data to the proximate RP. However, selecting such an finest set of RPs is a challenging task. The nodes around the MS traveling path are considered virtual rendezvous points (VRPs), which directly transmit their data to the MS rather than communicating with the RPs. The best set of VPRs minimizes the multi-hop transmissions between the node and RP along with the data loss and also handles the disconnected nodes (Zhang et al. 2015; Donta et al. 2020). Keeping the same SN as an RP for a longer time during data collection will unbalance the energy of the SNs. Especially, the nodes around the RPs are more extensive in this context. However, the selection and re-selection of RPs and VRPs is further arduous task. Besides, determining the best path between the RPs is also a challenging problem, and it is more complected in non-uniform data constraints.

There are several articles published recently to address some of the above discussed challenges such as weighted rendezvous planning (WRP) (Salarian et al. 2014), energy-aware path construction (EAPC) (Wen et al. 2017), ant colony optimization based Mobile sink path determination (ACO-MSPD) (Praveen Kumar et al. 2018), and hierarchical agglomerative clustering based data collection (HACDC) (Donta et al. 2020). In WRP Salarian et al. (2014), the Authors determine the RPs and the path between them. The path computation in the WRP is high, and it uses the traveling salesman (TSP) approach. The EAPC Wen et al. (2017) also identifies the RPs and the path between then, whereas the path computation strategy is low computational. The ACO-MSPD Praveen Kumar et al. (2018) mechanism included RP’s re-selection strategy along with RPs selection and also determine the path of MS with reasonable computational complexity. The HACDC Donta et al. (2020) computes the VRPs selection strategy along with the RPs and path determination with low time complexity. In the literature, there is no algorithm to adopt the RPs and VRPs selection and re-selection, along with the MS traveling path. This article extends an existing ACO-MSPD (eACO-MSPD) for achieving better network performance. The objective of the proposed eACO-MSPD is to pick the best RPs and VRPs sets dynamically, along with the delay aware MS traveling path. Besides, the eACO-MSPD also adopts dynamic RPs and VRPs re-selection process for energy balancing between the nodes. The extended version of the eACO-MSPD algorithm is compared with the ACO-MSPD through simulation tests and based on various metrics such as average networks energy consumption, fairness index, network lifetime, etc. The major contributions of the eACO-MSPD over the existing are summarized as follows.

  • We consider the new probability functions to compute the best set of RPs.

  • We propose a novel probability function to compute the efficient path of the mobile sink with minimal iterations of the ACO.

  • We extended the algorithm with finest set of VRPs selection strategy for minimizing the unnecessary data transmissions between the nodes and RPs.

The remaining sections of this paper structured as follows. In Sect. 2 we presented the literature work. In Sect. 3 we highlight the system model and problem formulation. In Sect. 4, we propose an algorithm for determining the visiting points (RPs) of MS followed by the visiting order. It also describes the VRPs selection and re-selection strategies. In Sect. 5, we evaluate the experimental results of the proposed algorithm. Finally, in Sect. 6, we concluded the report.

2 Related work

In this section, we review recent and related algorithms for RPs selection and the path construction strategies for MS in WSNs.

In Zhang et al. (2015), authors have proposed the NMCDC strategy for WSNs to collect data using MS efficiently through RPs. This method adopts the hierarchical clustering and routing algorithm for selecting RPs. The NMCDC also proposes a low computational traveling path determination approach. However, this approach does not consider the RPs re-selection mechanism. A tree cluster routing algorithm has been introduced using a dynamic sorting approach for the MS to perform the data collection process (Chang and Shen 2016). The primary objective of this approach is to control the data transfer distance between the SNs. In this method, the authors did not adopt the RPs re-selection and VRP selection strategies. In Yang et al. (2016), the delay-aware low computational, high-throughput data collection approach is proposed for MS in the WSNs. This approach works for an arbitrary topological network with a minimum number of MSs. The VRP selection and RP re-selection strategies are not adopted in this approach. An efficient cluster head selection for MS to visit and collect the data from it for WSN is proposed in Chauhan and Soni (2019). In this, the authors used low-energy adaptive clustering hierarchy (LEACH) to select the cluster heads. An efficient cluster head selection algorithm has been proposed for WSNs for collecting the data using a mobile sink in Prabaharan and Jayashri (2020).

A variable dimension PSO (VD-PSO) has been proposed in Wang et al. (2017) for WSNs. The VD-PSO was designed for MS to equilibrium the energy between the SNs efficiently. In this, each particle in the particle swarm optimization (PSO) was treated as the RP node. In other words, the dimensionality of the PSO indicates the number of RPs. This method is high computational because of the TSP. In Tang et al. (2017), clustering-based routing and cluster head selection method is proposed for MS in the WSNs. An integer non-linear programming (INLP) method is used to reduce the tour length of the MS. Authors in Jan et al. (2017) has proposed an energy-aware hole alleviating approach for WSNs using an MS. This method adopts a data transmission route along with the MS’s optimal traveling distance under the non-uniform data sizes. The EAPC has been proposed in Wen et al. (2017) for identifying the best RPs set and the traveling path of the MS. This approach uses a convex hull method to construct the route of the MS. In Kumar and Kumar (2019), delay-aware data aggregation with improved lifetime mechanisms has proposed for WSNs using MS. Khan and Kumar (2020) has proposed an efficient data gathering process in the agriculture field using a mobile sink. This method mainly focuses on the sensor nodes’ path to the base station and data forwarding route to optimize the energy consumption of the sensor nodes and the mobile sink.

In Praveen Kumar et al. (2018), an ACO-MSPD algorithm is proposed for MS path construction using ACO for MS under non-uniform data generation of the WSNs. This approach adopted RPs re-selection for efficient energy balancing and the dynamic traveling tour of the MS. A firefly based MS scheduling strategy has been developed in Yogarajan and Revathi (2018) for WSNs to perform the energy balancing between the SNs by avoiding the data losses. This approach computes the optimal visiting order of the MS in the WSNs. An intelligent data gathering scheme (IDGS) has been proposed in Wang et al. (2019b) for efficient data fusion from the SNs using MS for WSNs. This method uses a virtual grip mechanism to identify the visiting points called cluster heads. Later, it determines a static path between them for data fusion. In He et al. (2019), an energy-aware MS traveling plan approach has proposed using multi-objective PSO for MS in WSNs. This method optimizes the traveling length by choosing the overlap points of the SNs instead of choosing the node’s location. In Wang et al. (2018), ACO based cluster head selection and path construction for mobile sink have determined for WSNs. This method does not involve the re-selection of RPs or VRP selection methods to improve performance. An opportunistic corona-based optimal routing strategy is proposed for mobile sink for efficient data collection in WSNs (Thyagarajan and Kulanthaivelu 2020). This method efficiently minimizes the energy-hole problem for WSNs.

A query-driven grid-based data collection scheme has been proposed in Khan et al. (2019) for improving the MS data dissemination process. In this, the algorithm chooses the cluster heads based on the virtual grid clustering approach. In Wang et al. (2019a), an energy-aware cluster-based RPs selection and mobile sink traveling path are proposed for WSNs. A load-balanced cluster head selection based on artificial bee colony (ABC) and differential evolution in Gupta and Saha (2020) for MS-based data collection in WSNs. The ABC has also been used for MS path determination in this approach. A fuzzy logic-based clustering algorithm has been used for cluster head selection for an MS for data collection from the SNs using MS for WSNs Verma et al. (2020). This method computes the CHs depending on the consumption of energy among the SNs in the WSNs. In Donta et al. (2020), a hierarchical clustering method has been used for for RP selection for data collection. In this approach, the authors used a statistical method to decide the best RPs based on the network size. The analytical method also determines the VRPs based on the chosen path of the MS. This method also provides the minimum computational complexity for the MS path construction. A data gathering maximization with least consumption of energy has been proposed in Kumar and Dash (2020) for WSNs.

From the above discussion, most of the existing approaches are focused on the RPs selection and MS traveling paths. Of course, most of the methods are energy efficient and efficiently manages the data losses, and there is a possibility to enhance the performance still. The proposed eACO-MSPD extended the probability functions of the RPs selection and re-selection strategies along with the MS path construction. It also adopts the VRPs selection for minimizing the data transmissions between the SNs and the RPs.

3 System model and problem formulation

A graph \({\mathcal {G}}({\mathcal {S}}, {\mathcal {D}})\) is considered as a WSN, where \({\mathcal {S}}\) indicates set of SNs and the sink (\({\mathcal {S}}_0\)). All the \(n = (|{\mathcal {S}}|-1)\) SNs and the BS are randomly deployed at fixed locations. The n SNs are of the same category, but the nodes’ data collection is based on the event’s occurrence at various periods. The distance matrix of the SNs is indicated by \({\mathcal {D}}\), which includes the \({\mathcal {S}}_0\). The \(d_{ij} \in {\mathcal {D}}\) indicate the Euclidean distance between two SNs i and j. In case, the SNs i and j are not in the communication range r, then we consider the distance as \(\infty \). \({\mathcal {M}}\) is denoted as the set of RPs, where the RP is to collect data from SNs and VRPs. The set of VRPs is considered as \({\mathcal {V}}\), where the VRPs transmits their data directly to MS or closest RP. The relation among the \({\mathcal {M}}, {\mathcal {V}}\) and \({\mathcal {S}}\) are represented as \(({\mathcal {M}} \cup {\mathcal {V}}) \subseteq {\mathcal {S}} \forall {\mathcal {M}} \ne {\mathcal {V}}\). The MS collects the data from RPs or VRPs and submit them to the \({\mathcal {S}}_0\). The MS travels from \({\mathcal {S}}_0\) by visiting \({\mathcal {M}}\) and returns to the BS called a tour. The MS travelling length is initialized before constructing the path i.e. \({\mathbb {T}}_{ml}\). The MS communication range indicated as \({\mathbb {R}}\). The MS tour length and time are computed as per the ACO-MSPD (Praveen Kumar et al. 2018). The notations used in this article are listed in Table 1 for reader convenient.

Table 1 Notations used in this article
Full size table

The SN’s initial energy is considered as \({\mathcal {E}}_0\), and it drains mainly during the data sensing, processing, and communications. The energy model for the proposed eACO-MSPD is to adopt the free space energy model (Amgoth and Jana 2015; Praveen Kumar et al. 2018). The energy required for the amplification process is \(\alpha _{a}\), energy require to process a bit of data is \(\alpha _{t}\), and the circuit requires \(\alpha _{r}\) energy to receive a bit. The energy consumption (EC) of the node i, while transferring \({\mathcal {B}}\) bits to the node j is computed as shown in Eq. (1)

$$\begin{aligned} {\mathcal {E}}_{t}(i,j) = (\alpha _{t} \times {\mathcal {B}}) + (\alpha _{a}\times d_{ij}^2 \times {\mathcal {B}}) \end{aligned}$$
(1)

The node i consumes energy as shown in Eq. (2) while receiving \({\mathcal {B}}\) bits from the node j.

$$\begin{aligned} {\mathcal {E}}_{r}(i) = \alpha _{r} \times {\mathcal {B}} \end{aligned}$$
(2)

The EC of a node i in the tour k during the data communication is calculated using Eq. (3)

$$\begin{aligned} {\mathcal {E}}_{ik} = {\left\{ \begin{array}{ll} \left( \omega _i \times {\mathcal {E}}_{t}(i,j)\right) +\left( (\omega _i-{\mathbb {W}}_i) \times {\mathcal {E}}_{r}(i) \right) &{} \text {iff } {\mathcal {C}}_i \ne \phi \\ {\mathbb {W}}_i\times ({\mathcal {E}}_{t}(i,j) + {\mathcal {E}}_{r}(i)) &{} \text {Otherwise} \end{array}\right. } \end{aligned}$$
(3)

where \(\omega _i\) is the node i’s forwarding load, and it is computed using Eq. (4).

$$\begin{aligned} \omega _i = {\left\{ \begin{array}{ll} \left( \sum \limits _{j\in {\mathcal {C}}_i} \omega _j + {\mathbb {W}}_i \right) &{} \text {iff } {\mathcal {C}}_i \ne \phi \\ {\mathbb {W}}_i &{} \text {Otherwise} \end{array}\right. } \end{aligned}$$
(4)

where \({\mathbb {W}}_i\) is the packet size of the node i at a particular period, and \({\mathcal {C}}_i\) is the child nodes of i. The lifetime of the WSN (\({\mathcal {N}}\)) is considered as the time till the first SN dies, and it is measured in terms of Minutes (Legakis et al. 2008; Praveen Kumar et al. 2018). It is computed, as shown in the Eq. (5).

$$\begin{aligned} {\mathcal {N}} = \sum \limits _{k=1}^{\lceil \delta \rceil } \lambda _k \end{aligned}$$
(5)

where \(\lambda _k\) denotes the time taken to complete a tour by the MS, \(\lceil \delta \rceil \) indicates the total number of trips done by the MS when the first SN die. Therefore, the goal of the proposed eACO-MSPD is to prolong the \({\mathcal {N}}\) and degrades the delay of data collection. Finally, the problem statement is to select the best set of RPs, i.e., set \({\mathcal {M}}\), in order to maximize \({\mathcal {N}}\) for event-driven applications, where the packet sizes are varied. The assumptions considered for the eACO-MSPD are listed as follows.

  1. 1.

    The sink knew all the SN’s information such as position, available energy, etc.

  2. 2.

    The time spent by the MS at the RP is enough to collect the data.

  3. 3.

    The MS has enough space to store the collected data from the SNs.

  4. 4.

    No obstacle on the MS trajectory.

4 Extended ACO-MSPD

The proposed extended ACO-MSPD (eACO-MSPD) is progressed using the construction of a directed spanning tree (DST) (Praveen Kumar et al. 2018), RP selection, and path construction of the MS. Later it computes the VRPs according to the selected MS path. During the iterations, the RP, VRPs, and route dynamically change according to the change in the data size and network properties.

4.1 DST construction

The DST of a WSN is constructed as per the ACO-MSPD algorithm (Praveen Kumar et al. 2018). The goal of the DST is to circumvent the ambivalence in the data forwarding route to the MS. This data forwarding node selected by exchanging the data between the neighbor nodes. The DST construction phase generates a tree \({\mathcal {T}}\) using the \({\mathcal {G}}\) using two rounds. Figure 1 shows the illustration of the DST construction. Figure 1a is an example WSN, considered as a graph (\({\mathcal {G}}\)). In Fig. 1a, the numbers inside the circles indicate the node identification number. The numbers outside the circles are indicated as the \({\mathbb {W}}_i\) of each SN at time t. In the first round, the i chooses its forwarding node if \({\mathbb {W}}_i<Max({\mathbb {W}}_j),\ \forall j \in AN(i)\), where AN(i) is the set of adjacent nodes of i. The node i chooses the nearest nodes a forwarding node when the two nodes are equal maximum weights. After the first round, the tree \({\mathcal {T}}\) is shown in Fig. 1b. In this round, node 2 and node 10 are isolated. The node 2 is isolated because of high weight than its neighbor nodes 1, 3, and 6. Similarly, node 10 is isolated because of its neighbor (node 5 and node 11) are having the less weight then node 10. If there are any isolated nodes in the \({\mathcal {G}}\) after the first round, they chose the neighbor nodes forwarding node with maximum weight. In this, two nodes are isolated to choose the neighbor nodes forwarding node with maximum weight. So, node 2 chose node 6 as its forwarding node because node 6 parent node 9 has the highest weight. Similarly, the node can choose either node 5 or node 11, and here we choose node 5 because it is nearer. After processing the second round, the \({\mathcal {T}}\) becomes as shown in Fig. 1c.

Fig. 1
figure 1

Illustration a an example WSN as a \({\mathcal {G}}\). b The DST of the given \({\mathcal {G}}\) after the first round. c The DST of the given \({\mathcal {G}}\) after the second round (Praveen Kumar et al. 2018)

Full size image

4.2 RPs selection and MS path determination

The RPs selection and path determination of MS in the proposed algorithm gives the best performance of the event-driven WSNs. Similar to ACO-MSPD, the extended version also uses the ant colony optimization (Dorigo et al. 1996) approach to achieve the goal. In this phase, we consider \({\mathcal {G}}\) as an input, and the expected output is to determine \({\mathcal {M}}, {\mathcal {V}}\), and the path between SNs of \({\mathcal {M}}\cup {\mathcal {S}}_0\). The DST tree \({\mathcal {T}}\) is used to compute the forwarding weight w of an SN, and it is used in this phase to determine the RPs. The proposed eACO-MSPD uses the ACO to generate the solution by updating the ant’s pheromone value iteratively. The pheromone value \(\tau _{ij}^{a}\) between the node i and j is updated by an ant a using Eq. (6).

$$\begin{aligned} \tau _{ij}^{a} = (1-\rho )\tau _{ij} + \sum \limits _{a=1}^{m}\varDelta \tau _{ij}^{a} \end{aligned}$$
(6)

where \((1-\rho )\) is the pheromone’s evaporation rate of unit time, m indicates the total number of ants used in eACO-MSPD. The notation \(\tau _{ij}\) is the pheromone value between nodes i and j deposit by all the ants. The pheromone’s quantity is computed using the Eq. (7). The decay of the pheromone \(\rho \) is in the range of (0, 1).

$$\begin{aligned} \varDelta \tau _{ij}^{a} = {\left\{ \begin{array}{ll} 0 &{} \hbox {if ant } a \hbox { does not use the edge } i\hbox { to }j\\ \frac{Q}{L_a} &{} \text {Otherwise} \end{array}\right. } \end{aligned}$$
(7)

where \(L_a\) is the total trajectory distance by the ant a, and Q is a constant value, for example, 100. The probability function to choose a further node j from the node i is shown in Eq. (8).

$$\begin{aligned} p_{ij}^{a}(t) = {\left\{ \begin{array}{ll} \frac{\tau _{ij}^\alpha \eta _{ij}^\beta \omega _{j}^\gamma }{\sum _{C_{i\zeta } \in N(S^p)}\tau _{ij}^\alpha \eta _{ij}^\beta \omega _{j}^\gamma } &{} \text {iff }C_{i\zeta }\in {\mathbf {N}}(S^p)\\ 0 &{} \text {Otherwise} \end{array}\right. } \end{aligned}$$
(8)

The \(\eta _{ij}\) indicates the emphasis on the importance of heuristic data, and it is computed as shown in the Eq. (9). The \(\eta _{ij}\) also helps us to drive the best RPs set from the present network situation.

$$\begin{aligned} \eta _{ij} = \frac{1}{d_{ij}} \end{aligned}$$
(9)

The SN, which is not yet visited by any ant a, is represented as \(\zeta \). The \({\mathbf {N}}(S^p)\) contains the choice of the solution, and a stochastic construction monitors it by using the \(\tau \) value. The relative importance of the \(\tau _{ij}\) and \(\omega _j\) are denoted using \(\alpha \) and \(\gamma \), respectively. The ant a considers the next RP form the current node using the Eq. (8)’s the highest value. Once the algorithm chooses an RP, it starts calculating the MS trajectory length. The probability function to construct the MS path is shown in the Eq. (10).

$$\begin{aligned} \psi _{ij}^{a}(t) = {\left\{ \begin{array}{ll} \frac{\tau _{ij}^{\alpha } \eta _{ij}^{\beta } \omega _{j}^\gamma }{\sum \limits _{C_{i\zeta }\in N(M)}\tau _{ij}^{\alpha } \eta _{ij}^{\beta } \omega _{j}^\gamma } &{} \text {iff }C_{i\zeta }\in N(M)\\ 0 &{} \text {Otherwise} \end{array}\right. } \end{aligned}$$
(10)

In case of exceeding the MS tour length, this approach removes the RP from \({\mathcal {M}}\), and continues the same process with another node with the highest probability. In each round of the MS, depending on the variations of the data sizes, the proposed eACO-MSPD re-selects the RPs and re-constructs the trajectory path. After the path construction, the eACO-MSPD initiates the VRPs section around the MS traveling route.

The major improvements over the probability functions \(p_{ij}^{a}(t)\) and \(\psi _{ij}^{a}(t)\) over the existing ACO-MSPD are the distance and weights. The probability function \(p_{ij}^{a}(t)\) consider distances between the SNs while choosing the RPs set. The distance parameter considers the RPs according to the \(T_{ml}\) so that the RPs set selection process will be optimized. The probability function \(\psi _{ij}^{a}(t)\) uses the weight of the SNs while constructing the tour. Adding this parameter to the probability function benefited from reducing the tour length of the MS by selecting an optimal set of RPs. The variations of the probability values during the RPs selections are listed in the Table 2.

Table 2 Variation of probability values in ACO-MSPD and eACO-MSPD
Full size table

4.3 VRPs selection

The VRPs selection is the add-on to the traditional ACO-MSPD in the proposed eACO-MSPD. It increases the data gathering speed by avoiding the data loss and unnecessary data transmissions between the SNs and the RPs. The VRPs are the SN, which transmit their data directly to the MS when the MS is in its communication range. The VRPs in eACO-MSPD are \(({\mathcal {V}}\in {\mathcal {S}}) \wedge ({\mathcal {V}}\nsubseteq {\mathcal {M}})\). The VRP selection of the proposed algorithm depending on the MS transmission range and the available time using the SNs distance from the path \(\xi \). The \(\xi \) is decided based on the data available at the SN vs its transmission rate and the amount of the time MS available in SNs communication range. We choose the VRPs based on the \(\xi \) while MS traveling through the determined path.

Fig. 2
figure 2

Computing the minimum distance between the MS trajectory to the SN

Full size image

Initially, we choose the path between two RP nodes from \({\mathcal {M}}\) and assume a line as shown in Fig. 2. Assume the RP locations as \({\mathcal {M}}_1(x_1,y_1)\) and \({\mathcal {M}}_2(x_2,y_2)\). We choose the SNs one by one which are surrounded by \( \overline{{\mathcal {M}}_1{\mathcal {M}}_2}\) and determine whether they are in the communication range of the MS or not. The communication range is identified by comparing the minimum distance (\(\xi \)) between the \({\mathcal {S}}(x_i, y_i)\) to the \( \overline{{\mathcal {M}}_1{\mathcal {M}}_2}\) is less than or equal to the MS communication range. Firstly, we construct the line \({\mathcal {L}}\) using the \(\overline{{\mathcal {M}}_1{\mathcal {M}}_2}\) using Eq. (11) as shown below

$$\begin{aligned} {\mathbb {M}}(x-x_1)-y + y_1 = 0 \end{aligned}$$
(11)

where \( {\mathbb {M}}\) indicate the slope of the \({\mathcal {L}}\) and it is computed as shown below.

$$\begin{aligned} {\mathbb {M}} = \frac{y_2-y_1}{x_2-x_1} \end{aligned}$$
(12)

after substituting the \((x_1, y_1)\) and \((x_2, y_2)\), we assume the Eq. (12) gives \(\frac{a}{b}\), where a and b are constants. After substituting the \( {\mathbb {M}}\) value in Eq. (11), it become as shown in Eq. (13)

$$\begin{aligned} a*(x-x_1) - b*y + b*y_1 = 0 \end{aligned}$$
(13)

where the value of \(b*y_1\) is a constant. Once the line \({\mathcal {L}}\) is determined, we find the shortest distance (\(\xi _i\)) of the a node i to the \({\mathcal {L}}\) using Eq. (14).

$$\begin{aligned} \xi _i = \frac{|a*(x_i-x_1) - b*y_i + b*y_1|}{\sqrt{a^2+b^2}} \ \forall \ i\in ({\mathcal {S}}\cap {\mathcal {M}}) \end{aligned}$$
(14)

If \(\xi _i \le {\mathbb {R}}\), then we consider node i as a VRP and add it to the \({\mathcal {V}}\). In case \(\xi _i > {\mathbb {R}}\), the node i is not considered as a VRP at this stage. Repeat the above process until the MS start from base station and return it back to its starting position. These optimal set of VRPs will reduce the unnecessary data transmissions to the RPs and will reduce the unnecessary energy consumption.

4.4 Illustration of eACO-MSPD

The proposed and existing approaches are compared with an illustration for a better understanding. Table 2 shows the probability values of both ACO-MSPD and eACO-MSPD algorithms of each round while choosing the RP node from the SNs set. Figure 3 illustrates the first iteration of the ACO-MSPD choosing the RP nodes and path construction. The proposed eACO-MSPDs RPs selection path construction is illustrated in Fig. 4. In both the illustrations, we consider the running example (Fig. 1a) with fifteen nodes and the maximum MS tour length i.e., \({\mathbb {T}}_{ml}=120\,\mathrm{{ units}}\). We assume that the SNs generate data unevenly and are deployed randomly. The relative information of the heuristic data such as \(\alpha \), \(\beta \), and \( \gamma \), is considered as 0.2, 0.4, and 0.4, respectively. In both the existing and eACO-MSPD, the base station is considered as an RP, i.e., \({\mathcal {M}}=[{\mathcal {S}}_0]\).

The ACO-MSPD chooses the RPs to set a step by step process, as shown in Fig. 3. Each step calculates the probability value and chooses the node with the highest probability as an RP node. After choosing the RP node, it constructs the tour between the RP set; if the tour length is between the selected RPs is less than the \({\mathbb {T}}_{ml}\), further repeat the same. If the tour length is more than the \({\mathbb {T}}_{ml}\), it removes the currently chosen node and chooses the next highest probability value.

Fig. 3
figure 3

First iteration of ACO-MSPD’s RP selection and path construction a \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}]\), b \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}, {\mathcal {S}}_{9}]\), c \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}, {\mathcal {S}}_{9}, {\mathcal {S}}_{6}]\), d \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}, {\mathcal {S}}_{9}, {\mathcal {S}}_{6}, {\mathcal {S}}_{5}]\), e \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}, {\mathcal {S}}_{9}, {\mathcal {S}}_{6}, {\mathcal {S}}_{5}]\), f \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}, {\mathcal {S}}_{9}, {\mathcal {S}}_{6}, {\mathcal {S}}_{5}, {\mathcal {S}}_{8}]\), g \({\mathcal {M}}^a=[{\mathcal {S}}_{0}, {\mathcal {S}}_{12}, {\mathcal {S}}_{9}, {\mathcal {S}}_{6}, {\mathcal {S}}_{5}, {\mathcal {S}}_{8}, {\mathcal {S}}_{7}]\)

Full size image
Fig. 4
figure 4

First iteration of eACO-MSPD’s RP selection and path construction a \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9]\), b \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6]\), c \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2]\), d \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5]\), e \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5]\), f \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5, {\mathcal {S}}_8\), g \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5, {\mathcal {S}}_8, {\mathcal {S}}_7]\)

Full size image

The weight (\({\mathbb {W}}_i\)), forwarding load (\(\omega _i\)) and the probability (\(p_{ij}^a\)) of each node from the \({\mathcal {S}}_0\) is represented in Table 2. The illustration explains the first iteration of an artificial ant a from the sink \({\mathcal {S}}_0\) as shown in Fig. 4. Initially, \({\mathcal {M}}=[{\mathcal {S}}_0]\) is the RPs set of eACO-MSPD. Using Eq. (8), the maximum probability value is considered for choosing an RP in each step of the iteration process. From Table 2, the highest probability value return by the node \({\mathcal {S}}_9\) is chosen and used to construct the tour between the \({\mathcal {S}}_0\) and \({\mathcal {S}}_9\). It return the tour length as 60 i.e < 120. Therefore, the node \({\mathcal {S}}_9\) is chosen as an RP and the RP set becomes \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9]\). After updating the probability function, the node \({\mathcal {S}}_6\) return the highest value. The tour length after choosing node \({\mathcal {S}}_6\) is 73 i.e \(< 120\). Therefore the \({\mathcal {M}}^a\) becomes \([{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6]\). According to the updated probability values, the node \({\mathcal {S}}_2\) has the highest probability and tour length which is 89 i.e < 120. We can consider it as an RP and the RPs set become \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2]\). The tour length after choosing the highest probability node \({\mathcal {S}}_5\) is 107 i.e < 120. Therefore the RP set becomes \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5]\). After choosing the next highest probability value, return node i.e. \({\mathcal {S}}_{12}\) , the tour length is 133 i.e > 120. So, we do not consider it as an RP. The next highest probability returned by the node \({\mathcal {S}}_8\), and tour length is 112 i.e < 120. Therefore the RPs set after this step is \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5, {\mathcal {S}}_8]\). Similarly, we repeat the process until all the SNs are covered, and final RPs set is \({\mathcal {M}}^a=[{\mathcal {S}}_0, {\mathcal {S}}_9, {\mathcal {S}}_6, {\mathcal {S}}_2, {\mathcal {S}}_5, {\mathcal {S}}_8, {\mathcal {S}}_7]\) with the tour length of 112.

The SNs are generate the data non-uniformly based on the event occurrence. Due to this, the node weights change during the time. When the loads change, the previous RPs set needs to updated, and the re-selection of RPs is required to achieve the best performance. When the nodes change their weights, the DST reconstruction is also required. So, the whole eACO-MSPD algorithm needs to be repeated.

4.5 Complexity analysis

The computational complexity of the proposed eACO-MSPD is the combination of \({\mathcal {T}}\) construction, RPs selection, MS path construction, VRPs selection and RPs and VRPs re-selection. The computational complexity of the DST tree \({\mathcal {T}}\) with n nodes is O(n). The RPs selection and path determination use ACO and its time complexity is calculated as per the (Attiratanasunthron and Fakcharoenphol 2008), i. e \(O\left( \frac{1}{\rho }\left( mnqlog n\right) \right) \). Here, m is the number of ants, q indicates the number of edges and \(\rho \) is the pheromone’s evaporation rate. The value of m is always less than n. The time complexity for the VRPs selection is O(n). Therefore, the computational complexity of the eACO-MSPD is similar to ACO-MSPD, i.e. \(O\left( \frac{1}{\rho }(mnqlog n)\right) \).

5 Experimental results

The proposed eACO-MSPD algorithm’s performance is evaluated with the existing ACO-MSPD (Praveen Kumar et al. 2018) approach using simulation runs. The performance of both the algorithms is tested for the SNs with two scenarios of data constraints i.e., uniform and non-uniform. The network EC, the standard deviation (SD) of EC, the lifetime of the network and the average trajectory length are computed and compared for both existing and proposed works. We consider two scenarios of the networks based on their size in terms of \(\mathrm{sq. m}\) i.e. WSN#1 with the area \(20\times 20\) \(\mathrm{m}^2\) and WSN#2 with the area of \(200\times 200\) \(\mathrm{m}^2\). In the WSN#1, the n value various between 7 and 20, and in WSN#2, the n value varies from 100 to 200. Both the WSN#1 and WSN#2 use the tree topology.

The SNs data generation depends on the event occurrence, and it is assumed between 0 and 10 packets per second in the simulations. The size of the each packet is considered as 30 bytes. The data transmission rate is considered to be 80–250 kbps (Amrizal et al. 2019). The MS traveling tour length is restricted and set to 35 m for WSN#1 and 300 m for WSN#2. The initial energy (\(E_0\)) of all the SNs is equal and i.e., 100 J. The energy consumption of \(\alpha _{t}\), \(\alpha _r\) are 42 mW (0.042 J) and 29 mW (0.029 J) respectively. The communication range of the SNs various in different simulations i.e. from 15 to 50 m. The relative heuristic information of the ACO such as \(\alpha \), \(\beta \) and \(\gamma \) are 0.2, 0.4 and 0.4, respectively. The MS traveling speed during the data collection is set to 1 meter per second. Both the ACO-MSPD and eACO-MSPD are simulated using Python programming.

5.1 Network’s average energy consumption

The network’s average EC \(\mu _e\) is computed until the first SN dies in the network to the energy consumed by all the SNs in the WSNs.

$$\begin{aligned} \mu _e = \sum \limits _{i=1}^{n}\sum \limits _{k=1}^{\delta } \frac{E_{ik}}{\delta \times n} \end{aligned}$$
(15)
Fig. 5
figure 5

Network’s average EC under the scenario of uniform data rate a WSN#1, b WSN#2

Full size image
Fig. 6
figure 6

Network’s average EC under the scenario of non-uniform data rate a WSN#1, b WSN#2

Full size image

The \(\mu _e\) is tested for both the scenarios by varying the n and deployed randomly. Figure 5 compares the existing ACO-MSPD and proposed eACO-MSPD under a uniform data generation of the SN in the network. From Fig. 5a, we observe that the EC of the SNs is degraded by 10–15% as compared to the ACO-MSPD approach, 12–38% as compared to EAPC, and 15–45% as compared to WRP. Similarly, Fig. 5b shows that the proposed method improves performance by reducing the \(\mu _e\) by 8–15% approximately as compared to ACO-MSPD. Similarly, eACO-MSPDs AEC grew by 10–22% than EAPC and 12–36% than WRP. Figure 6 shows the \(\mu _e\) of WSN#1 and WSN#2 under the non-uniform data constraints. As per the results shown in Fig. 6a, the proposed eACO-MSPD reduces the consumption of the energy by 9–17% for the WSN#1 compared to ACO-MSPD, 11–23% compared to EAPC and 14–41% compared to WRP algorithms. From Fig. 6b, we found that the power consumption of the proposed eACO-MSPD is minimized around 6–13% compared to the ACO-MSPD. Similarly, the improvement over the EAPC and WRPs are 8–21% and 11–37%, respectively.

5.2 Standard deviation of EC

The standard deviation (SD) of the EC (\(\sigma _e\)) is used to measure the bottleneck of EC among the SNs in the WSNs. Higher the \(\sigma _e\), more energy is consumed in the network and degrade the network lifetime and vice versa. Other words, the \(\sigma _e\) is directly proportional to \(\mu _e\) and inversely proportional to the \({\mathcal {N}}\). The \(\sigma _e\) in this approach is computed, as shown in the Eq. (16)

$$\begin{aligned} \sigma _e = \sqrt{\frac{\sum \limits _{i=1}^{n} \left( \frac{\sum \limits _{k=1}^{\delta } E_{ik}}{\delta } - \mu _e\right) ^2}{n}} \end{aligned}$$
(16)
Fig. 7
figure 7

Standard deviation of node’s EC under the scenario of uniform data rate a WSN#1, b WSN#2

Full size image
Fig. 8
figure 8

Standard deviation of node’s EC under the scenario of non-uniform data rate a WSN#1, b WSN#2

Full size image

The \(\sigma _e\) of the WSN#1 and WSN#2 are tested for both the uniform and non-uniform data scenarios of the WSNs. Figure 7 shows a comparison of \(\sigma _e\) under the uniform data scenario for both WSN#1 and WSN#2. From Fig. 7a, we observed that the proposed eACO-MSPD’s \(\sigma _e\) are always lower than the existing ACO-MSPD, EAPC, and WRP algorithms. Similarly, from Fig. 7a the SD of the EC is better than the existing ACO-MSPD, EAPC, and WRP algorithms. The \(\sigma _e\) of the non-uniform data constraints are compared in Fig. 8. From Fig. 8a and b, we noticed that the proposed eACO-MSPD is always producing the less \(\sigma _e\) when compared to the ACO-MSPD, EAPC and WRP algorithms. The improved performance of the eACO-MSPD is due to the optimal selection of RPs, and its path and optimal VRPs selection. The data collected with VRPs always balances the energy due to direct data transmission to the MS.

5.3 Network lifetime

The lifetime of WSN (\({\mathcal {N}}\)) is computed as the time (in minutes) from the start of simulation till the first node dies. It is an important measure to compare the performance of the network. Increasing \({\mathcal {N}}\) also increases the WSNs performance, vice versa. It is calculated using the Eq. (5).

Fig. 9
figure 9

Network Lifetime under the scenario of uniform data rate a WSN#1, b WSN#2

Full size image
Fig. 10
figure 10

Network Lifetime under the scenario of non-uniform data rate a WSN#1, b WSN#2

Full size image

The \({\mathcal {N}}\) of the proposed eACO-MSPD is compared with the existing under uniform and non-uniform data scenarios of WSN#1 and WSN#2. The \({\mathcal {N}}\) of uniform data constraint of the networks are compared in Fig. 9. As shown in Fig. 9a, the \({\mathcal {N}}\) in the proposed work improves approximately 8–57% for the uniform data constraints when compared to WSN#1. The improvements in each of the existing methods are noticed compared to ACO-MSPD, EAPC, and WRP are 8–10%, 16–39%, and 19–57%, respectively. Figure 9b, we notice that the improvement of \({\mathcal {N}}\) over the existing method is around 6–43% for the WSN#2 under the non-uniform data scenario. The improvements in each of the existing methods are noticed compared to ACO-MSPD, EAPC, and WRP are 6–11%, 13–29%, and 17–43%, respectively. Figure 10 shows the \({\mathcal {N}}\) of both WSN#1 and WSN#2 under the non-uniform data scenario. The improved performance of the WSN#1 under the non-uniform scenario is shown in Fig. 10a. The improvement over the existing ACO-MSPD is 7–33% approximately. The improvements in each of the existing methods are noticed compared to ACO-MSPD, EAPC, and WRP are 7–10%, 11–26%, and 14–33%, respectively. Figure 10b, we identified that the proposed method is approximately 6–10% improved compared with the existing ACO-MSPD algorithm. Similarly, the performance improvement of the eACO-MSPD is 9–19% compared to the EAPC and 12–27% compared to the WRP algorithms. These improvements are observed based on the selection process of the RPs and VRPs and its re-selections.

5.4 Buffer utilization

The buffer utilization (BU) is defined as the amount of the buffer used during the unit time. The BU is always directly proportional to the data gathering process. The buffer capacity also effects on choosing the number of RPs. Increasing the Buffer size will reduce the number of RPs. Due to this, the tour length of the MS also may be reduced. The average BU of the proposed work and existing are computed at time t using Eq. (17).

$$\begin{aligned} BU = \frac{\sum \limits _{i=1}^{n}p_i}{b\times n} \end{aligned}$$
(17)

In both scenarios, if the \(p_i > b\), the SN drop the packets. This situation arise mostly due to the delay of the MS visit. Figures 11 and 12 evaluates the buffer utilization of uniform and non-uniform data rates of the proposed and existing ACO-MSPD, EAPC, and WRP algorithms. Figure 11a, the buffer utilization of the small network with a uniform data rate is compared. The BU of the eACO-MSPD always higher compared to the existing ACO-MSPD, EAPC, and WRP algorithms. The performance improvement is observed approximately 1.5–3% compared to ACO-MSPD, 2.5–6.5% compared to EAPC, and 7–11.5% compared to the WRP algorithms. Similarly, Fig. 11b compare the BU of the more extensive network with more sensor nodes under the uniform data rate of the SNs. The percentage of the buffer utilization of eACO-MSPD improved by 2–3.8% than ACO-MSPD, 4.5–6.5% than EAPC, and 6–11% than the WRP algorithms. The efficient buffer utilization indicates the efficient data gathering by the MS.

Fig. 11
figure 11

Buffer Utilization under the scenario of uniform data rate a WSN#1, b WSN#2

Full size image
Fig. 12
figure 12

Buffer Utilization under the scenario of non-uniform data rate a WSN#1, b WSN#2

Full size image

Figure 12 shows the buffer utilization of the proposed and existing ACO-MSPD, EAPC, and WRP algorithms under the non-uniform data constraints. Figure 12a, the buffer utilization of the small network with a uniform data rate is compared. The BU of the eACO-MSPD always higher compared to the existing ACO-MSPD, EAPC, and WRP algorithms. The performance improvement is observed approximately 2.5–3.8% compared to ACO-MSPD, 4.5–7.5% compared to EAPC, and 10–14.5% compared to the WRP. Similarly, Fig. 12b compares the BU of the more extensive network with more number of sensor nodes under the uniform data rate of the SNs. The percentage of the buffer utilization of eACO-MSPD improved by 2.8–4.3% than ACO-MSPD, 6.5–9% than EAPC, and 9.5–17% than the WRP algorithms. The improvement of the buffer utilization also enhances the data gathering process by increasing the NL and EC of the WSNs.

5.5 Average tour length

The tour length of the MS is initialized before constructing the trajectory. However, in all the cases, it need not cover the distance, which is fixed initially. As shown in the Illustration (Sect. 4.4) we initialize the tour length as 120 units. But it cover only 112 units. Similarly, during each re-selection of RPs, the path length of the MS also changes. The average tour length (\(\mu _t\)) is the ratio of the distance traveled by the MS until the first node dies and the \(\delta \). It is computed using the Eq. (18).

$$\begin{aligned} \mu _t = \frac{\sum \limits _{k=1}^{\lceil \delta \rceil } \chi _k}{\lceil \delta \rceil } \end{aligned}$$
(18)
Fig. 13
figure 13

Average tour length under the scenario of non-uniform data rate. a Area in square meters vs. average tour length. b Transmission range of SNs vs. average tour length

Full size image

We have examined \(\mu _t\) of WSN#2 under the non-uniform scenario and compared with the network having different area sizes in Fig. 13a. The area sizes considered for both the existing and proposed varies from 100 to 500 sq. m. We observe from Fig. 13b that the proposed method slightly decreasing the value of \(\mu _t\). Similarly, the transmission range of the SN is also an important parameter that affects \(\mu _t\). We examine the value of \(\mu _t\) by varying the transmission range from 30 to 50 m. From Fig. 13b, we observe that the proposed eACO-MSPD gives the minimum tour length compared to the existing ACO-MSPD, EAPC, and WRP algorithm. The minimum tour length of the MS will increase the data gathering process and reach the RPs before it overflows the buffer.

The improvement of the proposed algorithm is mainly because of introduction of the VRPs selection. The VRPs directly transmit their data to MS instead of communicating with RPs when MS is in the range of SNs. In this case, the SNs energy and relay node usage are minimized. The probability function is also much crucial in the proposed work to choose the RPs. The probability function identifies the best RPs set with the minimum number of iterations of the ACO. The analysis of other ACO-MSPD parameters such as \(m, \alpha , \beta , \gamma \), and \(\tau \) is does not varies in the proposed approach.

6 Conclusion

In this article, we have extended an existing ACO-MSPD algorithm called eACO-MSPD for event-driven WSNs under the uneven data generation of the sensor nodes. The proposed approach has adopted the feature of directed spanning tree construction to compute each node’s forwarding weight. The proposed eACO-MSPD determines the RPs set and path construction using a modified ACO algorithm. The probability function to choose the RPs from the sensor nodes and path construction is changed from the existing one to improve the network’s performance. The eACO-MSPD balances the energy among the sensor nodes by adopting the RPs re-selection strategy. This approach also enhanced the VRP selection, where the SNs directly transmit the data to the mobile sink instead of communicating with the RPs. The proposed and existing methods are compared with an illustration for a better understanding of the algorithm. The proposed eACO-MSPD algorithm performed better in terms of EC and lifetime is compared with the existing approaches. In the future, the proposed work extended by embedding wireless energy transmitter to the MS, and it recharge the critical sensor nodes in the WSNs.