1 Introduction

Wireless sensor networks (WSNs) consist a large number of small and tiny nodes which are scattered over the physical environment to monitor humidity, temperature, pressure, vibration, etc. [1]. These devices are highly resource constrained, equipped with small processors and wireless communication antennas, and battery powered. A sensor network is typically expected to perform multiple tasks [2, 3]. Tasks can be categorized into multiple sub-tasks. As an example, monitoring a large area can be categorized into monitoring multiple smaller areas. In heterogeneous networks, the requirement of a task is specified by its needs for different types of sensors [3]. In such cases, sensors must be bundled together before performing task assignments. Due to the limited number of sensors and potentially large number of tasks, competition will arise. Given all currently available information, the goal is to perform the best assignment of available sensors to tasks, to maximize the utility of the network [3, 4]. A large mass of sensor nodes are supposed to scatter in a geometric region, with nearby nodes communicating with each other directly. Without the help of a large amount of uniformly deployed seed nodes, this scheme fails in WSNs with possible holes [5]. The global geometry and topology of a WSN has a great influence on the design of basic networking functionalities, for example, point-to-point routing and data collecting mechanisms, or if we are desirous to spread some mobile sensors in an unknown region formed by static sensor nodes, knowing the border of the region permits us to guarantee that newly added sensors are deployed only in the expected region [5, 6].

Recently, they have found many attentions in the area of surveillance systems, which are used for security applications such as barrier monitoring [7]. These types of networks have many resource constraints, such as computing, transmission and power capabilities [8]. The main reason is that the nodes in the network will lose their power and cannot be used further. Therefore, WSNs need to exploit efficient techniques to decrease these limitations.

There are many issues in WSNs which have to be considered, such as coverage, lifetime, energy efficiency [9–11] and security. Among these concerns, lifetime and energy efficiency are the most crucial issues and they are related to the nodes’ battery usage. Energy-efficient routing protocols are used to transfer sensed data through networks’ nodes to the Base Station (BS) in the network. In this case, besides routing problem, increasing the network lifetime is another important issue. Lifetime of sensors constrains the amount of utility provided by the network. It has a close relationship with the energy efficiency of the WSN. In such way, some advanced nodes can transfer the network information via multi-hop communications to BS. To prolong network lifetime, hierarchical routing protocols such as Low-Energy Adaptive Clustering Hierarchy (LEACH) [12], LEACH with Deterministic Cluster-Head Selection (LEACH-DCHS) [13], Stable Election Protocol (SEP) [14], and Modified SEP (M-SEP) [15] can be used. In hierarchical routing protocols, the concept of clustering is used as basic concept to develop various protocols. In the clustering approach, some specific nodes are chosen as Cluster Head (CH) to transfer the network data to the sink node. Therefore, selecting some nodes as CH nodes in the deployed network is considered as one of the main targets of these research works, besides considering the lifetime issue.

As we know, sensors in the huge WSN face with unpredicted variety of data volume. It takes huge amount of time to process these information, therefore, the industries look forward to using some new trends such as Fog architectures (possibly, Fog computing) to decrease the processing time. The term “Fog computing” was first proposed by Cisco in [16] that enables a new breed of applications and services, and there is a fruitful interplay between the WSN and the Fog, particularly when it comes to data management and analytics. The Fog Nodes (FNs) closest to the network edge ingest the data from Internet of Things (IoT) devices. Combining the reliability requirements of cloud paradigms with the requirements of WSNs and actuators helps to design a reliable Fog computing platform [17].

On one hand, FNs can be deployed anywhere with a network connection: on a factory floor, on top of a power pole, alongside a railway track, in a vehicle, or on an oil rig. Any device with computing, storage and network connectivity can be an FN at the network edge. Examples include industrial controllers, switches, routers, embedded servers (see Fig. 1). According to Cisco, Fog node will be on-the-fly architecture which helps IoT to minimize latency, and avoiding the duplicated back and forth traffic between cloud and mobile users, not only the backbone bandwidth can be significantly saved, the energy consumption of core networks can also be greatly reduced, which contributes to the sustainable development of networking. We argue that the above characteristics make the Fog the appropriate platform for a number of critical IoT in general and Wireless Sensors location awareness. Several researches have been done in these topics such as [18–23], but most of them lack management of the CHs selection to prolong the aliveness in WSN. In addition, the research on Fog computing and related systems still remains at a very early stage. On the other hand, the WSN speeds up awareness and response to events in industries such as manufacturing, oil and gas. On a factory floor, a temperature sensor on a critical machine sends reading associated with imminent failure. In oil and gas exploration, sensors on oil pump slows down/raises up intake valve to control the system to prevent the disaster happen by monitoring the pump valve automatically. Therefore, the FNs closest to the grid sensors can look for signs of problems and if it happens then sends control commands to actuators to stop their actions. Therefore, we need to propose an energy-efficient solution to prolong the aliveness of the network. This research addresses the above issues.

Fig. 1
figure 1

The overall Fog structures and relation system architecture. Intra-Fog nodes architecture operate P-SEP. FN Fog node

Full size image

1.1 The goal of the paper

In this paper, we take energy efficiency and lifetime into consideration to propose a new approach for the mentioned problem. We devise an energy-aware Prolong Stable Election Protocol (P-SEP) for node clustering in WSNs, to maximize the network lifetime. We consider two-level heterogeneity of nodes which are called as normal nodes and advanced nodes, to devise a new approach. Fog infrastructure is, by definition, a location-aware system; it makes available the information about the Inter-sensor distances and sensor-to-sensor link gains which is exploited by the proposed CH election algorithm. This is the reason why our election algorithm well matches emerging Fog-supported WSNs. Our approach outperforms state-of-art works in this area in terms of network lifetime and number of CHs. The basic idea of the P-SEP protocol is the random selection of the number of the CH nodes at each round of the cycle, to achieve balance, reduce energy consumption and extend the lifetime of the network. The main contributions of the P-SEP can be summarized as follows: (1) P-SEP attempts to control the inherent randomness of the CH selection in each round; (2) P-SEP exploits heterogeneity energy threshold to avoid low-energy nodes to nominate CH in the next rounds; (3) P-SEP takes into account for the number of nodes that are associated with each CH and optimizes the minimum distance (md) between the CHs and FN; (4) using P-SEP at each round leads to nominate some CHs for the transmission of aggregated data to the FN, so that there is no the network freezing at each round; (5) there is no any priority considered for selecting CH between normal and advanced nodes, except that the node should be alive (its energy must be higher than the threshold) and should not have been CH in the previous round. We use this policy to avoid continuous selection of each node, regardless of its type; (6) P-SEP considers the average of the energy for each node to increase efficiency and reasonably decreases the overhead on each FN.

Remarkable features of the proposed protocol are its aliveness, fairness, full distribution in CH selection, prolongation of the lifetime, robustness of performance in the presence of energy heterogeneity, and ease of programming.

The rest of this paper is organized as follows. In Sect. 2, we shortly review the related work. In Sect. 3, we present our proposed clustering model and detail the Prolonged Stable Election Protocol, called P-SEP. In Sect. 4, we evaluate the performance of P-SEP via simulations and compare the results with most recent related ones. Finally, Sect. 5 concludes the paper and draws some possible future work.

2 Related work

Clustering and energy efficiency have been considered in wide area of WSN applications over the couple of years. The most important issues in the area of WSNs are energy efficiency, routing and coverage, because these issues have direct effect on the performance of network applications. In this section, we provide a review on research works that have been done in the literature on this topic.

A comprehensive and fine-grained survey on clustering routing protocols proposed in the literature for WSNs is presented in [24]. Authors of [24] point out the advantages and objectives of clustering for WSNs, and devise a novel taxonomy of WSN clustering routing methods based on complete and detailed clustering attributes. In the sequel, we review some of research literature that are related to our proposed algorithm. LEACH is the first hierarchical routing protocol for WSNs to improve the network lifetime [12]. In LEACH, authors generate a random number between 0 and 1 and compare it to a threshold as a base method to compute probability of nodes to be CH nodes. A Deterministic Cluster Head Selection based on LEACH, called (LEACH-DCHS), is proposed in [13]. Authors use the remaining energy level of each node to compute the probability of nodes to become CH. An Advanced LEACH (ALEACH) approach is proposed in [25] to extend the network lifetime. ALEACH rotate CH positions, to distribute the energy consumptions over all nodes.

There are many research works that have been done in the area of clustering in different aspects such as node deployment, energy consumption, nature of nodes and coverage. Here, we review the works that are related to the stability of networks. The stability of networks means that time interval from beginning before the first node exhausts its energy.

Stable Election Protocol (SEP) is a heterogeneity-aware protocol which extends the stability period (e.g., time interval before the death of the first sensor) of WSN [14]. This work is used as a basis work to propose a similar protocol with higher performance in different literature. It uses two levels of heterogeneity for the deployed nodes, e.g., advanced nodes and normal nodes. Advanced nodes have higher energy level than normal nodes and they compute the probability of nodes to be CHs in the network. In this approach, CH selection is done based on the probability value. Our method extends stability of network more than SEP by considering the average energy state of nodes for CH selection in each round.

A Modified Stable Election Protocol (M-SEP) for heterogeneous WSN is devised in [15]. M-SEP considers two types of nodes (i.e., advanced and normal nodes) with different initial energy. Advanced nodes have more initial energy than the normal ones at the beginning of the election algorithm. Therefore, those nodes have high probability to be CHs in this approach, because energy level is used as a factor to select CH in M-SEP. Although M-SEP is promising in network aliveness, it freezes the system in some cycles (or rounds) which is an idealistic condition. Moreover, compared to P-SEP, M-SEP is unable to keep aliveness of the network with an efficient energy reduction. Efficient modified version of SEP (EM-SEP) is introduced in [26] to improve the stability period of network by maintaining balanced energy consumption. EM-SEP has two main characteristics. First, advanced nodes have more possibility than normal nodes to become CH. Second, if two sensors have the same probabilities to become CH, the sensor with higher energy level is selected. Hence, EM-SEP suffers from keeping the system alive in long time and is unable to decrease the energy of the network in a smooth way which is accomplished by P-SEP. On the other hand, P-SEP can outperform all the mentioned methods in terms of network parameters which are mentioned in the work.

Fuzzy approach is used in some research works for clustering of the WSNs. A fuzzy-based clustering approach is proposed in [27] to improve the network lifetime. In this method, a super-CH (SCH) is elected among the CHs who can only send the information to the mobile BS by choosing suitable fuzzy descriptors, such as remaining battery power, mobility of BS, and centrality of the clusters. In the fuzzy engine, authors use Mamdani’s rule to select CHs. Authors devised a Fuzzy Relevance-based Cluster head selection Algorithm (FRCA) to solve the problems in existing wireless mobile ad hoc sensor networks [28]. In this method, fuzzy relevance is used to select the CHs for clustering of wireless mobile ad hoc sensor networks. Some other fuzzy-based works for clustering are introduced in [29–33]. The superiority of P-SEP over these approaches is that our method can use Fog technology to transfer data outside of network.

For the large WSNs, a clustering protocol which is called fan-shaped clustering (FSC) is proposed to partition a large-scale WSN into fan-shaped clusters [34]. FZ-LEACH is a LEACH-based protocol for clustering large-scale WSN which uses Far-Zone concept as a basic approach [35]. Far-Zone is a group of sensors which are placed at locations where their energies are less than a threshold. Multi-hop dynamic clustering LEACH (MDLEACH) is also used for clustering of large networks [36]. The main idea for MDLEACH relies on dynamic clustering and multi-hop transmission. With respect to efforts on the aforementioned techniques, P-SEP can work with FNs to take benefit of Fog computing which is never used in the recent clustering research works. Recently, some literature focuses on applying Fog technology to enhance the communication between the FNs [37–39]. Specifically, the authors of [37] present a joint controller for the adaptive, scalable and distributed management of the energy and bandwidth resources of inter FNs, to provide vehicular clients the mobile Internet access which is required by the emerging cloud-assisted FN applications. Moreover, [38] applies new fall detection algorithms and implements them into a distributed fall detection system in inter-FNs. On the other hand, the work [39] presents a predictable service demands of mobile users using Fog computing to deliver the localized service requests. The main focus of these works is on Mobile-Fog-Cloud architecture and rich potential applications, in both mobile networking and Internet-of-Things. They fail to consider the communication between the CHs and the way of CH selection. In a nutshell, these works are promising but none of them focus on the intra-FNs, the CH selection and data aggregation procedures over the Fog coverage areas [40, 41].

3 The proposed algorithm

This section is devoted to present the Fog-supported CH selection protocol (e.g., P-SEP). The goal is to prolong the network lifetime and decrease energy consumption.

3.1 The considered network model

The network infrastructure of the proposed algorithm is presented in Fig. 1. Figure 1 shows the main blocks which operate at the Middleware layer of the considered Fog infrastructure (see the gray rectangle in Fig. 1). Roughly speaking, the considered Fog Infrastructure (FI) is composed by several FN coverages (FNCs) (see the gray circles in Fig. 1). Hence, FNC is composed by: (1) several nodes (see the colored circle inside the Fog node coverage in Fig. 1) with low-level energy that require the information from the environment; (2) some CHs (see the red color circles inside FNCs of Fig. 1) with their sensing ranges (see the tiny gray color lines inside FNCs of Fig. 1), which are responsible to transmit the aggregated information to the FNs; (3) a network of wireless nodes and a fixed base station (possibly, WiFi) as a sink, which is called Fog Node (FN) (see the antenna in Fig. 1) with high energy. Each FNC covers n nodes with set \(\mathcal {N}=\{N_1,N_2,\ldots ,N_n\}\) under two-level heterogeneity sets (e.g., \(\mathcal {N}=\mathcal {NRM}\ \cup \ \mathcal {AD}\)); Normal nodes, \(\mathcal {NRM}\triangleq \{NRM_1,NRM_2,\ldots ,NRM_{\left| {\mathcal {NRM}}\right| }\}\) (e.g., the blue color circles inside each FNC of Fig. 1) and Advanced nodes \(\mathcal {AD}\triangleq \{AD_1,AD_2,\ldots ,AD_{\left| {\mathcal {AD}}\right| }\}\) (e.g., the green color circles inside each FNC of Fig. 1). In P-SEP, due to energy saving, some nodes will be selected as a CH using some policies, to transmit the received data from its neighbor nodes (e.g., which is called cluster as is shown in each section of the FNC in Fig. 1) directly to the FN. Therefore, P-SEP’s goal is to find the lower number of CHs in the WSN. Specifically, we presented how to obtain the optimal number of clusters, to increase energy efficiency and prolong the network.

First of all, we assume that advanced nodes’ locations are predetermined and normal nodes are placed randomly. The difference between advanced and normal nodes are their energy scales. The cardinality of \(\mathcal {AD}\), e.g., \(AD_{\left| {\mathcal {AD}}\right| }\), is a percentage of \(\mathcal {N}\) which is denoted by m. Let m be the fraction of the total number n of nodes and mn is the number of advanced nodes (i.e., \(n-mn\) is the number of normal nodes). Let M be the network space, where the space is assumed to be a rectangle. We denote \(r\in \mathcal {R}\) as the round (cycle) of the problem testing, where \(\mathcal {R}\triangleq \{1,\ldots ,r_{max}\}\) is a set of \(r_{max}\) cycles. In addition, we denote \(\alpha \) as the coefficient of the energy which is applied to the difference of advanced and normal nodes.

3.2 Advanced nodes distribution

Each node transmits data to closer CH and the CH performs data aggregation. The distance between FN and nodes is \(0<d_s<d_s^r\), where \(d_s^r\) is a fixed range considered to avoid data traffic jam of nodes in one cluster (i.e., \(d_s^r=10\)). The position of the advanced nodes are defined as: \(rp=\frac{M}{(mn+1)}\), and \(rp>i^2\), where i decides how many advanced nodes should be distributed in one \(rp(m^2)\). Hence, one node may become a CH with a probability p, where 1 / p is the epoch of the clustered sensor network, and totally the rate np would be the total probability of the WSN in one round. Note that, in P-SEP, one node cannot become a CH several times in a same round. We denote \(G_r\) as the set of binary values with length n for one node: if \(G_r(N_i), N_i\in \mathcal {N}\) is 1, it means the ith node becomes CH in the rth round, otherwise, it will not be CH in rth round and will be nomination to be a CH in the current round \((r+1)\), it guarantees that one alive node is able to be CH once in one round (the same policy applied in [5, 6]).

3.3 Nodes probabilities and energy definitions

Let m be the fraction of advanced nodes and the additional energy factor between advanced and normal nodes denoted by \(\alpha \). There are \(n(1+\alpha m)\) nodes with energy equal to the initial energy of a normal node (e.g., at round \(r=1\)), so \(\mathcal {E}_{nrm}^1\triangleq E_0\), where \(E_0\) is the initial energy considered for each node. The initial energy (e.g., at round \(r=1\)) of advanced nodes are defined as: \(\mathcal {E}_{adv}^1\triangleq E_0(1+\alpha )\). Let p be the probability of the nodes selection which influences on the normal and advanced node probability selections in rth round. To maintain the minimum energy consumption in each round within an epoch, the average number of cluster heads per round per epoch must be constant and equal to np. Let \(p_{nrm}\) and \(p_{adv}\) be the weighted probabilities for normal and advanced nodes, respectively. The weighted probabilities \(p_{nrm}\) and \(p_{adv}\) are defined as:

$$\begin{aligned} p_{nrm}= & {} \frac{p}{(1+\alpha m)},\end{aligned}$$
(1)
$$\begin{aligned} p_{adv}= & {} \frac{p(1+\alpha ){\overline{\mathcal {E}}_n(r)}}{(1+\alpha m){\mathcal {E}_{adv}^1}}, \end{aligned}$$
(2)

where \(\overline{\mathcal {E}}_n(r)\) is the average energy of all nodes (e.g., it includes normal and advanced nodes) in rth round which is defined as:

$$\begin{aligned} \overline{\mathcal {E}}_{n}(r)= & {} \frac{1}{n}\sum _{j=1}^{n}\mathcal {E}_{N_j}(r),\quad \text {if}\, \mathcal {E}_{N_j}(r)>0, \end{aligned}$$
(3)

where \(\mathcal {E}_{N_{j}}(r)\) is the energy of node \(N_j\) in rth round. In the heterogeneous scenario, the average number of cluster heads per round per epoch is equal to \(n(1 +\alpha m)p_{nrm}\) (i.e., each virtual node has the initial energy of a normal node).

To transmit information from each CH to the FN, we must consider some node characteristics and the distance from CH to FN. Indeed, each node has a radio energy dissipation to attain an acceptable signal-to-noise-ratio (SNR) transmitting k number of the bit message over a distance d (distance from CH to FN). We define \(\mathcal {E}_{Tx}\) and \(\mathcal {E}_{Rx}\) which are the energies consumed by the transmitter and receiver circuits in the network, respectively. In this model, we use the free space (\(f_s\)) (with \(d^2\) the coefficient of power loss) and the multi-path fading (mp) (with \(d^4\) the coefficient power loss) channel models depending on the distance for the \(\mathcal {E}_{TX}\) and \(\mathcal {E}_{RX}\) [14]. It means, when the distance d is less than \(d_0\), the \(f_s\) energy denoted by \(\varepsilon _{f_s}\) is used; otherwise, mp energy denoted by \(\varepsilon _{mp}\) is applied for calculating \(\mathcal {E}_{Tx}\). Therefore, the \(\mathcal {E}_{Tx}\) is calculated as in:

$$\begin{aligned} \mathcal {E}_{Tx}(k,d)\triangleq \left\{ \begin{array}{ll} k( \mathcal {E}_{elec}+\varepsilon _{fs} d^2), &{} \mathrm{if} \ d\le d_o,\\ k( \mathcal {E}_{elec}+\varepsilon _{mp} d^4), &{} \mathrm{if} \ d>d_o, \end{array}\right. \end{aligned}$$
(4)

where \(d_0\triangleq \sqrt{\varepsilon _{fs}/\varepsilon _{mp}}, \mathcal {E}_{elec}~\triangleq ~\mathcal {E}_{Tx}~+~\mathcal {E}_{DA}\), while \(\mathcal {E}_{DA}\) is the data aggregation energy for each node and \(\mathcal {E}_{elec}\) is the energy consumed in electronic circuit to transmit/receive the signal, and \(d \triangleq \) \(\sqrt{(X_{CH}-X_{FN})^2~+~(Y_{CH}-Y_{FN})^2}\). Finally, the receiver consumed energy is defined as: \(\mathcal {E}_{Rx}(k,d)\triangleq \mathcal {E}_{elec}k\).

The energy of CH (e.g., CH selection which is described in the next subsection) will be updated after the calculation d and \(\mathcal {E}_{Tx}\) as

$$\begin{aligned} \mathcal {E}_{N_i}(r)=\mathcal {E}_{N_i}(r-1)-\mathcal {E}_{Tx}, \end{aligned}$$
(5)

where \(\mathcal {E}_{N_i}(r)\) is the energy of ith node in the rth round.

3.4 CH selection using energy thresholds

We denote by \(Th(N^{nrm}_{i})\) and \(Th(N^{adv}_{i})\) the energy thresholds for the normal and advanced node to be selected as CH in the rth round, respectively. Eqs. (6) and (8) present thresholds \(Th(N^{nrm}_{i})\) and \(Th(N^{adv}_{i})\) for the normal and advanced nodes, respectively.

$$\begin{aligned} Th(N_i^{nrm})= & {} {\left\{ \begin{array}{ll} \frac{p_{nrm}}{1-p_{nrm}\left( r~mod~\frac{1}{p_{nrm}}\right) }\overline{\mathcal {E}}_{N_i}(r),&{} \text {if} \ N_i\in G_r^{\prime }\\ 0,&{} \text {otherwise}, \end{array}\right. } \end{aligned}$$
(6)

where \(Th(N_i^{nrm})\) is the threshold applied to \(n(1-m)\) normal nodes in the current round \(r;G_r^{\prime }\) is the set of nodes that do not become CHs in the last \(1/p_{nrm}\) rounds of the epoch; \(\overline{\mathcal {E}}_{N_i}(r)\) is the average of alive nodes starting from the first node selection to ith node in the rth round as shown in (7):

$$\begin{aligned} \overline{\mathcal {E}}_{N_i}(r)= & {} \frac{1}{n}\sum _{j=1}^{i}\mathcal {E}_{N_j}(r),\quad \text {if} \ \mathcal {E}_{N_j}(r)>0, \end{aligned}$$
(7)

This confirms that each normal node becomes a CH node at rate \(\frac{1}{p}(1+\alpha m)\) per epoch and the average number of CHs are normal nodes per round per epoch, which is equal to \(n(1-\alpha m)p_{nrm}\). In the same way, for the advanced nodes, we have

$$\begin{aligned} Th(N_i^{adv})={\left\{ \begin{array}{ll} \frac{p_{adv}}{1-p_{adv}\left( r~mod~\frac{1}{p_{adv}}\right) } 1/\overline{\mathcal {E}}_{N_i}(r),\quad &{} \text {if } N_i\in G_r^{\prime \prime }\\ 0,\quad &{} \text {otherwise}, \end{array}\right. } \end{aligned}$$
(8)

where \(Th(N_i^{adv})\) is the threshold for the advanced nodes at the round r, and \(G_r^{\prime \prime }\) is the set of advanced nodes that do not become CH in the last: \(1/p_{adv}\) rounds of the epoch. This guarantees that each advanced node will become a CH strictly once per \(\frac{1}{p}(1+\alpha m)/(1+\alpha )\) rounds, per epoch and per \(1/\overline{\mathcal {E}}_n(r)\). This confirms that P-SEP is capable to make fully distributed and suitable election of the CH under heterogeneous nodes (e.g., the nodes do not have the same initial energy levels). In order to minimize the total energy consumptions in the current network it is enough to elect the proper a CH.

3.5 Distance computation

In this subsection, we define the distance between CH and FN (denoted by \(d_{toFN}\)) and the minimum distance from the nodes to CHs (denoted by \(md_{toCH}\)), to find the minimum path to save energy for transferring the information to FN. In other words, using the Fog-based model, similar to [42], service stations with bound-less capacity are defined as between gateway and common nodes based on the largest hop count from the gateways, whereas in [42, 43] the other nodes are modeled as service stations with certain capacity and the nodes do not forward loads for other nodes in the same hop, as our model does. The goal is to minimize the communication cost. Then, we attempt to save the energy of the WSN to prolong WSN aliveness and keep nodes running more rounds (we find minimum distance of each node to the CH for each round). Specifically, at each round, we select the desired ratio of CHs randomly, then we start to the process of finding CH set \(\mathcal {CH}\) on the alive nodes. If we find a node that should be considered as a CH, then we add it into the \(\mathcal {CH}\) set and count the number of established CHs (i.e., \(CH\_ctr\)). We continue this loop to find at most the desired number of CHs (in each round), then stop the loop and calculate the required distances \(d_{toFN}\) and \(md_{toCH}\) in each round as in:

$$\begin{aligned} d_{toFN}= & {} \sqrt{(X_i-X_{FN})^2+(Y_i-Y_{FN})^2}, \forall (X_i,Y_i)\in \mathcal {N}{{\setminus }}\mathcal {CH},\end{aligned}$$
(9)
$$\begin{aligned} md_{toCH}= & {} \text {argmin}_{(X_i,Y_i)} \sqrt{(X_i-X_{CH})^2+(Y_i-Y_{CH})^2},\nonumber \\&\quad \forall (X_i,Y_i)\in \mathcal {N}{{\setminus }}\mathcal {CH}, \forall (X_{CH},Y_{CH})\in \mathcal {CH}, \end{aligned}$$
(10)

and

$$\begin{aligned} d_{min}=\min _{N_i\in \mathcal {N}{\setminus }\mathcal {CH}} (d_{toFN},md_{toCH}),\quad \forall N_i\in \mathcal {N}{\setminus }\mathcal {CH}, \end{aligned}$$
(11)

where \((X_{FN},\,Y_{FN})\) and \((X_{CH},\,Y_{CH})\) are the Cartesian coordinates of the FN and CHs, respectively. Specifically, in Eq. (9), we calculate the distance of each non-CH nodes (\(\mathcal {N}{{\setminus }}\mathcal {CH}\)) to FN. Then, Eq. (10) computes the distance of the nearest CH to each alive node. Finally, Eq. (11) selects the minimum between the values Eqs. (9) and (10) for each non-CH node on a per-round basis and calculate the energy according to Sect. 3.3.

Algorithm 1 presents the steps of the proposed P-SEP. The output of the algorithm is defined as: \(\mathcal {A} \triangleq \left. \{\overline{\mathcal {E}}_n(r),~\mathcal {E}_{N_i}(r),~ \overline{Alive},~\mathcal {CH}\right. \}\). Th1 and Th2 are threshold values for selecting normal and advanced nodes as CH, respectively.

figure a

3.6 Some explicative remarks about Algorithm 1

The Algorithm 1 points out the steps of the proposed method. Specifically, we define the set \(\mathcal {CH}\) as the list of nodes which are selected to be CH in rth round. Line 1 attempts to establish the advanced nodes as detailed in Sect. 3.2. Lines 2 starts a loop of the P-SEP to run on each node. Lines 6–8 show that we define a parameter, called \(no\_CH\), to keep the numbers of desired CH at each round as an uniform distribution (denoted by unif(., .) between \([CH_{min},~CH_{max}]\)). Lines 13–21 and Lines 22–26 detail the selection of normal nodes and advanced nodes as CHs, respectively. Note that distance is a Euclidean distance value which is calculated between the corresponding normal node: \(N_i\in \mathcal {NRM}{\setminus }{N_i}\) and other normal nodes. At the end, the last Lines 28–34 update the energy of the nodes which are not selected as a CH at rth round using minimum distance computations.

3.7 MAC setup for P-SEP

P-SEP relies on a time division multiple access (TDMA)/code-division multiple access (CDMA)-based MAC protocol to reduce inter-cluster and intra-cluster collisions. It consists of two time phases that is a steady-state phase and a setup phase. During the steady-state phase, the sensor nodes sense and transmit data to the CHs. The CHs compress the data arriving from nodes that belong to the respective cluster, and send a fused packet directly to the FN (Figs. 1 and 2).

Fig. 2
figure 2

Time chart of the operation of P-SEP

Full size image

After a time,Footnote 1 which is planned a priori, the network goes back into the setup phase again and enters another round of CH election. As an alternate analysis, the efficiency of the 802.11 MAC under different topologies and traffic patterns can be evaluated by measuring total one-hop network throughput, to transmit them as soon as possible and decreasing latency at each hop by balancing the network load among good forwarders [45, 46]. Therefore, the FN’s gateways reduce energy consumption and extends the lifetime of the cluster heads. The FN’s gateways decrease probability of failure nodes and prolong the time interval before the death of the first node and increasing the lifetime in heterogeneous WSNs. The use of TDMA/CDMA techniques allows a hierarchy and makes clustering on several levels, to save more energy.

About the P-SEP implementation complexity, we note that the convergence rate of the P-SEP is constant and related to the number of the iterations (rounds). In detail, P-SEP pursues a local strategy, in which nodes execute the algorithm independently and base their cluster membership decisions on their own state and the state of their neighbors. In P-SEP, since the decision to change the CH is probabilistic, there is a good chance that every node is selected as a CH regardless of its energy level. Furthermore, P-SEP forms one-hop intra- and inter-cluster topology, in which each node can transmit directly to the CH and thereafter to the FN. As a consequence, the per-round implementation complexity of the proposed algorithm is O(1).

4 Performance evaluation

This section presents the simulated performance of the P-SEP under various scenarios and compares it with SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13] performances.

4.1 Simulation setup

To analyze the performance of the P-SEP algorithm, we run the simulation under the MATLAB testbed. The network parameters used in our experiments are listed in Table 1. The simulated sensor networks include different fractions of advanced and normal nodes (\(m=\{0.1, 0.2, 0.3\}\), i.e., \(m=0.1\) means the ratio of the advanced node is \(10~\%\) of total nodes number and the rest all normal nodes). To evaluate P-SEP under different environments, we built up four scenarios, two of them with two case sensor densities: node numbers \(n=\{100, 200\}\), respectively, problem space/areas \(M=\{100\times 100, 200\times 200\}\), the number of iteration which is called rounds \(r=5000\), advanced node selection coefficients are \(\alpha =\{1, 2, 3\}\), and the sensing ranges of each node (\(d_0\)) is 5.28 (m) [47] in our implementations. Two other scenarios which are concentrate on the big-size network \(M = \{1000 \times 1000\}\) with \(n= 1000\) nodes and medium-size with \(M = \{500 \times 500\}\) with \(n = 500\), respectively.

Table 1 Default values of the main simulated parameters
Full size table

4.2 Numerical results

In the following, we test the P-SEP energy performance under various settings and compare the attained results against the aforementioned protocols.

4.2.1 Effect of parameter settings

In the first scenario, we aim at testing the performance of the P-SEP and evaluate the resulting average number of normal and advanced nodes, process the WSN with different \(\alpha \), n, m, and M under a synthetic (e.g., independent and identically distributed) information arrival and random sequence of normal nodes for 5000 rounds inspiring [12, 13]. Figure 3a, b reports the average of the normal \(\overline{\mathcal {NRM}}\) and advanced \(\overline{\mathcal {AD}}\) nodes, which are defined as: \(\overline{\mathcal {NRM}}\triangleq \overline{\mathcal {NRM}}_r=1/r\sum _{\tau =1}^{r}\mid \mathcal {CH}^{nrm}\mid _\tau \), and \(\overline{\mathcal {AD}}\triangleq \overline{\mathcal {AD}}_r=1/r\sum _{\tau =1}^{r}\mid \mathcal {CH}^{adv}\mid _\tau \), respectively, where \(\mid \mathcal {CH}^{nrm}\mid _\tau \) and \(\mid \mathcal {CH}^{adv}\mid _\tau \) are the number of normal and advanced nodes which are in the set \(\mathcal {CH}\) at the \(\tau \)th round, respectively. \(\overline{\mathcal {NRM}}\) and \(\overline{\mathcal {AD}}\) are selected as CH for various m and r under medium-size (\(n=500, M=500^2\)) and big-size (\(n=1000, M^2=1000\)) environments. In Fig. 3c, d, we present different \(\overline{\mathcal {E}}_n\)-vs.-r for various m for corresponding medium-size (\(n=500, M=500^2\)) and big-size (\(n=1000, M=1000^2\)) environments. We draw five conclusions from these figures. First, by increasing the round r the \(\overline{\mathcal {NRM}}\) (see three continuous downward plots in Fig. 3a, b) and \(\overline{\mathcal {AD}}\) (see three dashed upward plots in Fig. 3b) declines, due to death of normal and advanced nodes, which is influenced by the number of CH selections. This rate is higher for normal nodes, because their population is higher than the one of the advanced nodes. Second, the number of available advanced nodes will be higher for increasing m, and the decreasing rate will be smoothly lower at lower m values (see three dashed upward plots in Fig. 3a, b). Third, the comparison of Fig. 3a, b points out that when the network size and the number of nodes in the WSN increase, the probability of normal and advanced nodes to be CH increases. Fourth, in comparison between Fig. 3c and d, we elicit that, while r increases, the average energy of nodes: \(\overline{\mathcal {E}}_n\triangleq \overline{\mathcal {E}}_n(r)\) decreases. This is due to reduction of the alive nodes (as well as decreasing the CHs as are shown in Fig. 3a, b). Finally, the m values have direct impact on the number of CHs and the network energy reduction.

Fig. 3
figure 3

\(\overline{\mathcal {E}}_n\) and \(\overline{\mathcal {NRM}}/\overline{\mathcal {AD}}\) for different m in big-/medium-size problems

Full size image

Figure 4 reports the average energy usage of nodes (i.e., consumed energy) \(\overline{\mathcal {E}}_n^{Cons}\) and the average energy of nodes (i.e., residual energy) \(\overline{\mathcal {E}}_n^{res}= \overline{\mathcal {E}}_n\) at different nodes (100, 500, 1000) under the scenario of Table  1 different rounds. Specifically, Fig. 4 points out that: (1) when the number of rounds increases, \(\overline{\mathcal {E}}_n^{Cons}\) increases and \(\overline{\mathcal {E}}_n^{res}\) decreases; (2) when the number of sensor nodes increases, the energy consumption increases (see three upper most black continue plots of Fig. 4) and the \(\overline{\mathcal {E}}_n^{res}\) decreases (see three lower dashed plots of Fig. 4).

Fig. 4
figure 4

\(\overline{\mathcal {E}}_n^{Cons}\)-vs.-\(\overline{\mathcal {E}}_n^{Res}\)-vs.-r under the scenario of Table 1 at \(\alpha =m=0.1\)

Full size image

Figure 5 reports the average energy of nodes \(\overline{\mathcal {E}}_n\) for different \(\alpha ,n\) under various network sizes. Specifically, we conclude the following results: (1) while r increases, more nodes die and \(\overline{\mathcal {E}}_n(r)\) decreases; (2) at each round \(r^*\), when \(\alpha \) increases, the energy of advanced nodes (e.g., \(\mathcal {E}_{adv}^1\)) increases while the \(\overline{\mathcal {E}}_n(r^*)\) increases; (3) the comparison of Fig. 5a, b points out that, by increasing the values of n and M, the \(\overline{\mathcal {E}}_n(.)\) increases at each round \(r^*\), due to using more nodes and more network spaces.

Fig. 5
figure 5

\(\overline{\mathcal {E}}_n\) of P-SEP under the scenario of Table 1 at \(m=0.1\) with various \(\alpha \)

Full size image

4.2.2 Performance comparisons

In the next test scenario, we run the proposed algorithm and evaluate the resulting number of alive nodes and per-node average energy \(\overline{\mathcal {E}}_n\) over 5000 rounds under the simulated parameters of Table 1. The drained results are reported in Figs. 6 and 7. To carry out fair energy comparisons, all the energy values reported in this subsection also account for the energy wasted by the corresponding signaling tasks carried out by the simulated algorithms. Figure 6 shows that our P-SEP protocol outperforms other protocols in terms of stability and network lifetime. Specifically, Fig. 6 points out that: (1) when m increases, the node lifetime increases; (2) LEACH-DCHS, SEP, M-SEP are very sensitive to heterogeneity, so nodes die at a faster rate with result to P-SEP, which uses the fairness in CH selection among its two-level heterogeneity.

Figure 7 reports \(\overline{\mathcal {E}}_n\) in all the protocols. It shows that the average energy of each alive node decreases during the time (round), but P-SEP could keep more nodes alive, which is against other protocols which die soon and the network average energy goes to zero in less than 2000 rounds, in turn, P-SEP could be alive in all rounds and keeps the network energy especially when m is 0.2 and 0.3. Therefore, in this protocol, sensor nodes deplete their energy at very low rate. Overall, it may be concluded that P-SEP is more energy efficient, has longer stability period and longer lifetime than the other routing protocols.

Fig. 6
figure 6

Number of alive nodes (system lifetime) for P-SEP, SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13]

Full size image
Fig. 7
figure 7

\(\overline{\mathcal {E}}_n-vs.-r\) for P-SEP, SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13]

Full size image

Table 2 reports the maximum (e.g., \(\mathcal {E}_{max}\triangleq \sum _{i=1}^{n} \mathcal {E}_{N_i}(1)\) for \(r=1\)), minimum (e.g., \(\mathcal {E}_{min}\triangleq \sum _{i=1}^{n} \mathcal {E}_{N_i}(r_{max})\) for \(r=r_{max}\)) energies and average energy of the WSN under P-SEP, SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13] for different m values. In detail, we understand that at \(m=0.1\), the \(\overline{\mathcal {\mathcal {E}}}_n\) improvements of P-SEP compared to SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13] are of about 48, 46, 43 and 67 \(\%\), respectively. Furthermore, by increasing the number of advanced node to 3 times (i.e., \(m=0.3\)), the savings of the proposed algorithm compared with SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13] protocols with lower number of advanced node (i.e., at \(m=0.1\)) are of about 9, 35, 34, and 28  \(\%\), respectively. Moreover, we conclude that, when m increases, the minimum energy \(\mathcal {E}_{min}\) of the network for the P-SEP is higher than corresponding protocols, and this confirms that the P-SEP is able to prolong of the lifetime of the network.

Table 2 The maximum \(\mathcal {E}_{max}\), minimum \(\mathcal {E}_{min}\) energies of the WSN and \(\mathcal {\mathcal {E}}_n\) for different m among P-SEP, SEP [14], M-SEP [15], EM-SEP [26], and LEACH-DCHS [13]
Full size table

Table 3 reports the First Node Die (\({ FND}\)), Mean Node Die (\({ MND}\)), Last Node Die (LND), and the average of rounds taken each node among 100 nodes alive (\(\overline{Alive}\)) of the aforementioned protocols under various m and at \(M=100^2 (m^2)\). An examination of the numerical results reported in Table  3 leads to three main conclusions. First, \({ FND}\) and \({ MND}\) of the P-SEP are higher than other methods. It is important to stress that P-SEP attempts to adapt itself and prolong the network lifetime, especially at \(m=0.2\). It means that, although P-SEP first node dies sooner than other protocols, but the MND rate in P-SEP is higher than others, this confirms that, per-round, P-SEP elect suitable CHs to increase the aliveness of the network. Second, by increasing m, FND and MND increase too, due to the presence of more advanced nodes in the WSN. Third, the average number of alive nodes at each round (e.g., \(\overline{Alive}\)) in the P-SEP is higher than all other methods and this confesses P-SEP aliveness is higher than others. Figure 8 reports the solution of P-SEP algorithm (e.g., \(\mathcal {A}\)) at \((n, m, M, \alpha )=(200, 0.2, \{100^2, 200^2\}, 1)\) against the ones of the aforementioned protocols. Specifically, Fig. 8a–d reports three performance parameters (e.g., \(\#Alive,CHs\), and average energy of the network \(\overline{\mathcal {E}}_n\)) at \(M=100^2(m^2)\) and the next three plots are presented for \(M=200^2(m^2)\). Hence, from Fig. 8a vs. e and Fig. 8d vs. h, we conclude, while network size increases, the normal nodes dispersion increases and this leads to consume more energy to send the information through the nodes to CHs and/or CHs to FN. Hence, this situation leads to decrease the number of alive nodes as well as \(\overline{\mathcal {E}}_n\), and the interesting point is that P-SEP may use suitable CHs at each round, prolonging the network aliveness and even be alive, even after 5000 rounds compared to others which die. From the CH selection and packet transferring point of view, P-SEP could select CHs and send packets from CHs to FN with less fluctuations, especially within the first 2000 rounds comparing with other protocols (see Fig. 8c vs. g). This is due to the fact that the other protocols are unable to adapt nodes’ thresholds, to select the suitable CHs, while P-SEP adapts the thresholds (see Eq. (7)).

Table 3 Comparison of P-SEP and others protocols with \(r=5000\); NND \(:=\) node never die; FND \(:=\) first node die; MND \(:=\) mean node die; and, LND \(:=\) last node die, \(\overline{Alive}\) \(:=\) average nodes takes to be alive in each round
Full size table
Fig. 8
figure 8

Number of alive nodes (i.e., \(\#Alive\)), CHs number (i.e., CHs), and \(\overline{\mathcal {E}}_n\) versus r for P-SEP, SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13] for \(M=100^2\) (Fig. 8a–c) and \(M=200^2\) (Fig. 8d–f) at \(n=200,\alpha =1\), and \(m=0.2\)

Full size image

In the last simulation, Fig. 9 reports the total transferred packets (e.g., \(\#Pkts\)) under different protocols and at various m. We draw two remarks from this figure. First, CHs in P-SEP is lower than SEP [14], LEACH-DCHS [13], and M-SEP [15], due to the selection of optimal CHs. Second, P-SEP is lower than EM-SEP [26] (bits) because, at each round, P-SEP attempts to select some nodes as CHs that have not be selected in the previous round, to be fair, distribute the energy, and prolong lifetime of the network.

Fig. 9
figure 9

Total transferred packets in bits throw CHs between P-SEP, SEP [14], M-SEP [15] EM-SEP [26], and LEACH-DCHS [13] with different m

Full size image

The reported performance results support the conclusion that knowledge of energy level and network lifetime bring important advantages: our algorithm given both these values significantly outperforms the algorithm using heterogeneous energy levels. Indeed, P-SEP has better performance than traditional routing algorithms, such as SEP, LEACH-DCHS, M-SEP, and EM-SEP, especially in reducing the energy consumption and extends the lifetime of the network. Besides, the nodes’ survival rate is significantly higher in P-SEP under different spectrum of operating conditions.

5 Conclusion and future work

In this paper, we propose a new technique to organize the advanced nodes and to select the CHs in WSNs. We proposed two energy levels based on proposed Prolong SEP (P-SEP) for the normal and advanced nodes. P-SEP is completely fair for the CH selection between nodes, it means, all nodes have the same probability to be selected as CHs. The attained experimental results show that the proposed algorithm achieves much higher energy saving than the traditional ones. In the attained performance evaluation, we compared P-SEP against SEP, LEACH-DCHS, M-SEP and EM-SEP. We select the most eligible nodes as the CHs, the nodes die rate is less than the other protocols and incur good impact in case of data messages reception at the FN and save energy of the (advanced, normal) nodes and results in prolongation of aliveness of the WSN. In addition, P-SEP increases the stability period and packet transmission rate as compared with other routing protocols. In the future, we would like to process and send the information/request to the Internet throughout the FN where this protocol has the main control. Besides, we would like to focus on transfer protocol that comprises the energy and performance saving, and implement high-power sensors as a gateway between the CH and FN of Fog architecture.