In QPSOFL, n homogeneous nodes with unique ID are grouped into m clusters. Each cluster has only one CH, and each CM belongs to only one cluster. The special node BS can be deployed within or outside the network, and once deployed, neither the BS nor the nodes can move. The proposed protocol nominates the most appropriate nodes as CHs by using quantum particle swarm optimization algorithm and selects the optimal relay CHs based on fuzzy logic system to improve the network energy efficiency and maximize the network lifetime. The working of QPSOFL mainly consists of two phases, namely CH selection and relay finding.CH selectionSelecting the optimal CHs from the nodes by using QPSO is one of the objectives of QPSOFL so as to form energy efficient clusters. At first, a population comprising \({N}_{p}\) particles is initialized by using Sobol sequence with bounds in [1, n]. Each particle represents the set of nodes’ ID that are candidates for the CHs, which can be express as \({P}_{i}=({q}_{i,1}, {q}_{i,2},…,{q}_{i,m})\) where each component \({q}_{i,j} (1\le j\le m)\) denotes CH j in particle i. Note that the non-integer values are converted to the nearest integer in the implementation. Moreover, only the nodes whose energy is higher than the average are eligible to be candidate CHs for fast convergence.Next, the particles are evaluated by a fitness function which considers energy and distance simultaneously. High residual energy is the first significant factor to consider for CH selection because CH consumes additional energy for data aggregation and forwarding compared with CM. Besides, the average intra- and inter-cluster distance is another importance factor to be considered, the smaller the distance, the lower the network energy consumption and the better the energy efficiency. Thus, the fitness function can be formulated in Eq. (8).$$ f = \alpha \times \frac{1}{{\mathop \sum \nolimits_{i = 1}^{m} E_{res} \left( {CH_{i} } \right)}} + \left( {1 – \alpha } \right) \times \frac{{\mathop \sum \nolimits_{i = 1}^{m} \left( {\frac{{\mathop \sum \nolimits_{j = 1}^{k} d\left( {s_{j} , CH_{i} } \right)}}{k} + d\left( {CH_{i} ,BS} \right)} \right)}}{m} $$
(8)
where \({\text{E}}_{{{\text{res}}}} \left( {{\text{CH}}_{{\text{i}}} } \right)\) denotes the residual energy of CH i, \(d\left( {s_{j} , CH_{i} } \right)\) and \(d\left( {CH_{i} ,BS} \right)\) indicate the distances from CM j to CH i, and from CH i to the BS, respectively. k is the number of CMs in the corresponding cluster, and \(\alpha = 0.6\) is the co-efficiency ranging in [0, 1] used to regulate the factors of energy and distance. In order to obtain the residual energy of the nodes, energy model as the same in9,36 is utilized to calculate the energy consumption of data transmission with k bits over distance d between any two nodes i and j, and the energy consumption for data transmitting and receiving is expressed in Eqs. (9) and (10), respectively.$$ E_{{tr\left( {k,d} \right)}} = \left\{ {\begin{array}{*{20}c} {k*E_{elec} + k*\varepsilon_{fs} *d^{2} , d < d_{0} } \\ {k*E_{elec} + k*\varepsilon_{mp} *d^{4} ,d \ge d_{0} } \\ \end{array} } \right. $$
(9)
$$ E_{rc} \left( k \right) = k*E_{elec} $$
(10)
where \({E}_{elec}\) represents the electronics energy consumption used for transmitting or receiving \(1\)-bit data. \({\varepsilon }_{fs}\) and \({\varepsilon }_{mp}\) are the amplifier coefficients used for free space and multi-path model, and \({d}_{0}=\sqrt{{\varepsilon }_{fs}/{\varepsilon }_{mp}}\) is the distance threshold for the model determination. Besides, the energy consumed for k-bit data aggregation can be calculated by using Eq. (11).$$ E_{DA} = k*E_{pDb} $$
(11)
\({E}_{pDb}\) denotes the energy dissipated for fusing 1-bit data. Thereafter, the local best and global best can be obtained, and the new state of each particle in the next iteration also can be calculated by using Eq. (4). The process continues until the optimal solution is reached or the stopping condition is satisfied. The pseudo-code for CH selection in QPSOFL is given in Algorithm 1 below to demonstrate the steps used by QPSO technique for the calculation of the positions of the particles.Algorithm 1Pseudo-code for the CH selection using QPSOFinally, the particle with maximum fitness value becomes the global best \(gBest=({q}_{best,1,}{q}_{best,2}, …, {q}_{best,m})\). Once the CHs are selected, each CH sends an advertisement message to the nodes in its range announcing its CH identity, and the normal nodes join the nearest CH to form clusters. Furthermore, TDMA schedule mechanism is adopted by each CH to complete intra-cluster data transmission. That is to say each CM sends its sensed data to the CH in its assigned slot to avoid inference and collision, and the CH collects and aggregates the data from its CMs. Subsequently, the aggregated data is transmitted to the relay of the CH and till to the BS in the end.Relay findingIn QPSOFL, a Mamdani fuzzy inference system is introduced to find optimal relay for each CH so as to decrease and balance the energy consumption of the CHs by creating a best path from any source CH to the BS. The fuzzy inference system consists of four components: fuzzifier, accepting the normalized crisp inputs and converting them to linguistic variables; fuzzy rule base, obtaining a set of if–then rules used for decision making from expert experience; inference engine, reasoning using the fuzzy rules to obtain the fuzzy output; defuzzifier, converting the fuzzy output into crisp values \(Prob\). Residual energy \({E}_{res}({CH}_{i})\), energy deviation \({E}_{dev}({CH}_{i})\), and relay distance \({D}_{ry}({CH}_{i})\) are considered as inputs to the FIS for relay finding, then the framework of the FIS can be depicted in Fig. 2.Figure 2Fuzzy logic model in QPSOFL.The fuzzy inference system generates probabilities for corresponding candidate relays of each CH based on the residual energy, energy deviation, and difference of relay distance. The input parameters play a critical role in decision making for relay finding, which are normalized to the same domains ranging in [0, 1]. After that, the membership function based on the expert experience is utilized to perform fuzzification, which are described as follows.Residual energy \({E}_{res}({CH}_{i})\) denotes the remaining energy of candidate relay i of CH j, and it should be noted that only the neighbor CH i of CH j with residual energy higher than the average can become candidate relay. The relay needs more energy to forward data to the BS than the normal CHs, thus the more residual energy, the more likely the candidate relay is to become the final relay. Due to its importance for relay finding, three triangular and two trapezoidal membership functions are considered for residual energy, namely very less, less, normal, much, very much, which is shown in Fig. 3.Figure 3Membership function for residual energy.Energy deviation \({E}_{dev}({CH}_{i})\) denotes the deviation of energy consumption of candidate CH i, which indicates the consistency of energy consumption among the candidate CH i and its neighbor CHs. The smaller the standard deviation, the better the consistency of the energy consumption of these CHs, the better their balanced energy consumption, and even the less likely they are to cause hot spot problem. The energy deviation can be calculated by using Eq. (12).$$ E_{dev} \left( {CH_{i} } \right) = \left| {E_{ec} \left( {CH_{i} } \right) – \frac{{E_{ec} \left( {CH_{i} } \right) + \mathop \sum \nolimits_{j = 1}^{k} E_{ec} \left( {CH_{j} } \right)}}{k + 1}} \right| $$
(12)
k is the number of neighbor CH located in the range of CH i, \({\text{E}}_{\text{ec}}({\text{CH}}_{\text{i}})\) denotes the energy that has been consumed by CH i. Three triangular and two trapezoidal membership functions are also considered for energy deviation, namely very low, low, normal, high, very high as shown in Fig. 4.Figure 4Membership function for energy deviation.Relay distance \({D}_{ry}({CH}_{i})\) represents the sum of distances \({d}_{r}\) and \({d}_{p}\) as shown in Fig. 5. \({d}_{r}\) is the distance from the candidate CH j to the straight line between CH i and the BS. \({d}_{p}\) is the distance from candidate relay CH j to the crossover point CPi between the communication circle of CH i and the straight line between CH i and the BS. The combination of the two distances represent not only energy saving but also fast data forwarding. That is to say, the smaller the relay distance, the more energy is saved, and the faster the data is forwarded to the BS.Figure 5Relay distance considering energy saving and fast data forwarding.Due to its critical influence for relay finding, three triangular and two trapezoidal membership functions are considered for relay distance, too, namely very near, near, normal, far, very far, which is shown in Fig. 6.Figure 6Membership function for relay distance.After fuzzification of the input variables, 125 fuzzy rules based on expert experience are used for inference engine to obtain the fuzzy output, which is given in Table 4.Thereafter, the fuzzy output is converted to the crisp value \(Prob\) by using CoA21,45, who uses 5 triangular and 2 trapezoidal membership functions very low, low, quite low, normal, quite high, high, very high, as shown in Fig. 7.Figure 7Membership function for output \(Prob\).When a candidate relay has a greater value \(Prob\), it will have a greater probability of becoming a final relay. Once the relays are determined, the optimal path for data transmission from a source node to the BS is also decided. Each CM sends its sensing data to its CH at the allocated slot, and the CH aggregates all the data collected from its CMs, and then conveys the data to its relay, and so on until the data reaches the BS.Time complexityThe time complexity of the QPSOFL protocol involves evaluating its main operational phases: cluster formation, route finding, and cluster and route maintenance. During cluster formation, QPSOFL employs Quantum Particle Swarm Optimization, characterized by a time complexity of \(\text{O}(\text{n}\times {N}_{p}\times maxIter)\), where n denotes the number of sensor nodes, \(maxIter\) represents the maximum iterations, and \({N}_{p}\) denotes the population size utilized in the optimization process. Subsequently, in route finding, QPSOFL integrates fuzzy logic to determine optimal relays for each CH. This stage is associated with a time complexity of \(O({n}_{CH}\times {n}_{rules})\), where \({n}_{CH}\) stands for the number of CHs, \({n}_{rules}\) represents the size of fuzzy rules. Finally, for cluster and route maintenance, local cluster updates require minimal messaging, specifically \(O({n}_{CH})\), while from the BS, broadcasting involves one message and forwarding entails a maximum of \(O({n}_{CH}-1)\) messages. Therefore, the time complexity of QPSOFL is \(\text{O}(\text{n}\times {N}_{p}\times maxIter+{(n}_{CH}+1)\times {n}_{rules})\). In addition, \({n}_{p}\), \({n}_{CH}\), \(maxIter\) and \({n}_{rules}\) are much less than n.Human and animal rightsThis article does not contain any studies with human participants or animals performed by any of the authors. No violation of Human and animal rights is involved.
Energy efficient clustering and routing protocol based on quantum particle swarm optimization and fuzzy logic for wireless sensor networks
