Multi-hop clustering routing algorithm based on fuzzy inference and multi-path tree

Abstract

Wireless sensor network technologies have been widely used in modern life especially in Internet of Things. Since battery energy of sensor nodes is limited, balancing the energy consumption of each node on a transmitting path is an important issue. In this article, we propose a multi-hop clustering routing method with fuzzy inference and multi-path tree. The algorithm identifies the best path from the source node to the destination node by following two steps: (1) dividing the wireless sensor nodes by an efficient clustering routing method and (2) determining the optimal path by a combination of the fuzzy inference approach and multi-path method, taking into account the remaining energy, the minimum hops, and the traffic load of node. Simulation results show that the proposed protocol can efficiently reduce the energy consumption of the network, balance network load, and prolong the survival time of the network.

Introduction

Wireless sensor networks (WSNs) are composed of a large number of stationary or mobile sensor nodes based on the way of self-organization and multi-hop to constitute wireless networks. It can collaboratively gather, process, and transmit the information of perceived objects within the geographical area covered by networks, and eventually, provide the information to the terminal user. WSNs have been widely used in broad application prospects, such as habitat monitoring, ¹ wildfire monitoring, ² healthcare system,^3,4 and navigation. ⁵ Challenging issues in WSNs have been extensively studied, for example, power management is explored in Salvadori et al., ⁶ data gathering is addressed in Cheng et al.,^7,8 routing is studied in Karkvandi et al., ⁹ sensor deployment and coverage issues are explored in Chen et al. ¹⁰ as well as localization is studied in Ahn and Ko. ¹¹

The structure of WSNs and the involved components are shown in Figure 1, for example, sensor nodes, sink nodes, task management centers. A sensor node is composed of four components: a sensor module, a processor module, a wireless communication module, and a power supply module. The sensor module, which is made up of sensor and analog-to-digital converter, collects information within the monitoring area and converts the collected information to digital signals. Processor module is responsible for controlling and coordinating the operation of sensor nodes, storing as well as processing the data collected by itself or sent by other nodes. Wireless communication module is responsible for communication with other sensor nodes to exchange control information as well as receive and send the collected data. Power module provides the required energy for the sensor nodes.

Figure 1.

Components of a wireless sensor network.

WSNs are often deployed in severe environment or areas where it is not accessible for human. Sensor nodes may be exposed in the open air, suffering from sun exposure or rain, and network maintenance is extremely difficult. Once a WSN is deployed, its lifetime should be as long as possible given the initially provided amount of energy. Moreover, the nodes of WSNs are small and battery-powered, which leads to many problems. Energy efficiency is a critical issue in WSNs due to the limited capacity of the sensor nodes batteries. Unbalanced energy consumption reduces the network lifetime to a large extent. The main purpose of the WSN is to disseminate the information from targets to sink. The energy of the communication path will run out soon due to the high network traffic selecting the same path. Lifetime of WSN is a critical parameter for assessing the performance of routing protocols. Therefore, designing an effective routing method to control energy cost is important for prolonging the network lifetime.

G Smaragdakis et al. ¹² and X Fan and Y Song ¹³ proposed an uneven clustering routing algorithm stable election protocol (SEP). SEP algorithm divides the sensor nodes into normal nodes and advanced nodes so as to deal with energy heterogeneous problem of wireless sensor nodes, which is based on weighted election probabilities of each node to become a cluster head (CH) according to the remaining energy in each node. The nodes with more residual energy will have more chance to become a CH. Experimental results show that the SEP method is better than low-energy adaptive clustering hierarchy (LEACH) protocol to extend the network lifetime. This method transmits the information of the member node to the corresponding CH. However, the CH sends messages directly to the base station after fusing the received data. The energy of the CH will run out because of the long distance between the CH and base station, which will cause the node die soon. In Li et al., ¹⁴ the authors proposed an algorithm by setting the energy threshold of nodes using balanced grid to select the CH, which represents an energy-balanced routing algorithm. The algorithm is applicable to some extent in reducing the energy consumption of the network, but does not involve the selection of the optimal path. In Tsai et al. ¹⁵ an Axis-Based Virtual Coordinate assignment protocol (ABVCap) method and a routing protocols based on ABVCap virtual coordinate were proposed, which reducing the energy cost of end-to-end communication by minimizing the number of routing hops. The work in Park and Sahni ¹⁶ and Wu et al. ¹⁷ used another method to prolong the network life cycle, that is, the lesser energy nodes will be distributed the lesser traffic loads, on the contrary, the nodes with more energy will be distributed more. G Jiang et al. ¹⁸ used Energy-Efficient Optimal Multi-path (EEOM) Routing Algorithm which has improved the selection of the CH, the establishment of cluster, and the transmission of data. This article also introduced the concept of multi-path and reconstruction of the CH. The improved protocol which overcomes the potential problems of the LEACH and EECS routing protocols is not only for large-scale networks, but also conducive to energy balance. Nevertheless, the optimization model of describing multi-path feature of a WSN remains unclear. In another paper, ¹⁹ the authors proposed a multi-path-based reliable routing protocol which can guarantee a specified end-to-end target packet reception rate. This method is superior to both AODV and MAODV-SIM protocols in packet reception rate and maintains a target packet reception rate using multi-path-based reliable routing protocol in a network where the amount of traffic changes dynamically. However, there are difficulties for implementation, as the optimization model for the proposed approach is unknown. In Liu et al., ²⁰ the authors proposed a new routing protocol named the Security and Energy-efficient Disjoint Route (SEDR) which is a three-phase disjoint routing scheme to optimize the secret-sharing-based multi-path routing problem. The objective of this proposal is to maximize both network security and lifetime, subject to the energy constraints. SEDR method delivers sliced shares to the sink node with randomized disjoint multi-path routes using the available surplus energy of sensor nodes and demonstrates that the proposed scheme can maximize the network security without decreasing the network lifetime. This article focuses more on establishing disjoint links than the definition of multi-path, which should also be considered in the maximization of security and lifetime.

From the aforementioned literatures, we note that many routing algorithms minimize the average energy consumption in the network at the expense of non-uniform energy drainage in networks, which will bring about network broken due to the death of certain nodes in the efficient path. In many cases, the network lifetime will be shortened as soon as critical nodes run out of energy.

Aiming at avoiding network broken and prolonging the network lifetime, we propose a new method called SMF (multi-hop clustering routing algorithm based on fuzzy inference and multi-path tree) by combining Lower Energy Adaptive Clustering Hierarchy Enhancement (LEACHEN) method, multi-path algorithm, and fuzzy approach to select the optimal routing path from the source to the destination, which takes into account the highest residual energy, minimum number of hops, and minimum traffic numbers. The innovation points of the proposed SMF approach include the following points.

1. A new clustering method named LEACHEN is proposed based on the classical clustering LEACH algorithm. ²¹ LEACHEN method provides constraints and limits for balancing energy consumption, in order to extend the lifetime of the establishment phase.

2. An efficient evaluation function for multi-path algorithm is employed to seek the next hop, which balances the influence of the minimum hops, the traffic load, and the remaining energy.

3. In order to verify the performance of the proposed SMF algorithm, different network topologies are employed. We compare the proposed algorithm with the methods in AlShawi et al. ²² and Yuan et al. ²³ The results prove that the proposed algorithm is efficient to extend the lifetime of the network.

This article is organized as follows: section “Preliminaries” presents some assumptions, defines the concept of routing metrics, and describes the energy model. In section “SMF algorithm,” we put forward the SMF method, including LEACHEN clustering algorithm, fuzzy inference approach, and multi-path method by describing each part of the algorithm in detail. Then, the simulation environment and results are presented in section “Performance evaluations.” Finally, we provide our key conclusions and future directions in the last section of the article.

Preliminaries

Assumptions

We consider seven assumptions as follows:

• Case 1: the positions of the base station as well as the wireless sensor nodes are fixed and the base station is far away from the sensor nodes in the network. All sensor nodes in the network are identical, and the energy is limited.

• Case 2: radio signals have the same energy consumption in each direction and all sensor nodes have the same maximum transmission range and the initial energy.

• Case 3: all sensor nodes are randomly distributed, and they can acquire the position of their own and the corresponding neighbor nodes as well as the position of the base station.

• Case 4: a percentage of the node population is equipped with more energy than the rest of the nodes in the same network—this is the case of heterogeneous sensor networks and they are all uniformly distributed in space.

• Case 5: each node can be informed of the average energy in the network and set the probability of selected CH node according to their residual energy. ²⁴

• Case 6: each node has a certain amount of traffic pending in node’s queue. The node’s queue includes the application traffic and also the traffic that a node has already committed to forward.

• Case 7: all nodes are location-aware. They have knowledge about their positions in WSNs.

Metrics definition

Most of the literatures referenced in this article describe different metrics which have been used to prolong the lifetime of WSNs. In this article, three metrics have been employed to elect the best node in the optimal path. These metrics are as follows:

1. Remaining energy (RE). The D-value is between initial energy and energy consumption of the node. The main energy consumption for normal nodes is by sending data while for the CH node mainly include data aggregation and data receiving. In WSNs, energy efficiency is the critical aspect of routing protocols. In this standard, battery capacity of the current node is the core. Routing protocol using this measure tends to select path with maximum average energy from the source node to the destination node. That is, the node with more residual energy is much more likely to be selected as the optimal node in the best path.^25–27

2. Minimum number of hops (MH). Minimum number of hops is the common criteria of routing protocol which means the minimum number of relay nodes from the start node to the end node. The basic idea of this measurement is to obtain less relay nodes and less energy cost using the shortest path method, because the less forwarding nodes will consume less energy.^26–28

3. Traffic load (TL). The traffic load of the node can be defined as the pending amount of traffic in a node’s queue. These traffics include the amount of the transfer being sent and previously be transmitted. In the case of the concentrated events of particular sub-region, using the shortest path would cause implosion phenomenon on this path. High load will cause the sensor node data queue overflows, resulting in loss of important information. In addition, the entire sensor network lifetime will be shortened, due to the quick energy consumption of batteries in the sensor nodes.^25,27,29

Energy model

Once a node is placed, it often stays immobile and continues working until its energy reaches zero. The energy consumed at a sensor node can be modeled mathematically. This article utilized the first-order radio model ²¹ which is commonly used in the WSNs. The radio energy consumption model is shown in Figure 2.

Figure 2.

Radio energy dissipation model.

The energy consumed by the sensor nodes in this article is divided into two categories. The first category is the energy consumed by the normal or advanced node (non-CH and non-parent node (PN)). According to Figure 2, when the distance between the transmitter and the receiver is $d$ and transmit L-bit message, the energy required by common sensor nodes while transmitting electronics can be defined as

$$E_{\mathrm{NTx}}(L,d)=\{\begin{array}{cc}L·E_{\mathrm{elec}}+L·{\epsilon }_{\mathrm{fs}}·d^2\hfill & \mathrm{if}d\le d_0\hfill \\ \multicolumn{1}{c}{L·E_{\mathrm{elec}}+L·{\epsilon }_{\mathrm{mp}}·d^4}& \mathrm{if}d>d_0\hfill \end{array}$$

(1)

where $L$ is the packet size of transmitted data; d is the distance between the sender and the receiver; $E_{\mathrm{elec}}$ is power circuits for sending or receiving, determined by the digital coding, modulation, filtering, and spread signal and other factors; and $d_0$ is the distance threshold, when the transmission distance is less than the threshold using the free space channel model, on the contrary, using multi-path fading channel model. ³⁰ Amplifier power ${\epsilon }_{\mathrm{fs}}$ and ${\epsilon }_{\mathrm{mp}}$ is determined by transmission distance and the accepting error rate. When $d=d_0$ , let $d_0=\sqrt{{\epsilon }_{\mathrm{fs}}/{\epsilon }_{\mathrm{mp}}}$ .

The received electronic energy consumption when normal node receives L-bit message is given as

$$E_{\mathrm{NRx}}=L·E_{\mathrm{elec}}$$

(2)

The second category is the energy consumed by the CH or PN. As a CH or PN, in addition to sending and receiving consumes energy, the data processing also consumes the energy, and the energy consumed by the CH or PN while transferring L-bit data can be obtained via

$$E_{\mathrm{CHPTx}}(L,d)=\{\begin{array}{cc}L·E_{\mathrm{elec}}+L·E_{\mathrm{DA}}+L·{\epsilon }_{\mathrm{fs}}·d^2\hfill & \mathrm{if}d\le d_0\hfill \\ \multicolumn{1}{c}{L·E_{\mathrm{elec}}+L·E_{\mathrm{DA}}+L·{\epsilon }_{\mathrm{fs}}·d^4}& \mathrm{if}d>d_0\hfill \end{array}$$

(3)

where $E_{\mathrm{DA}}$ is the energy consumed by CH or PN while processing 1-bit message, and $d$ is the distance between the sender and the receiver. The received energy circuit consumption for CH or PN when receives L-bit message can be defined as

$$E_{\mathrm{CHPRx}}=L·(E_{\mathrm{elec}}+E_{\mathrm{DA}})$$

(4)

The values used in the first-order radio model are described in Table 2.

SMF algorithm

SMF algorithm includes two steps: first, divide the wireless sensor nodes in WSNs into clusters using LEACHEN method and then, use the method which is the combination of fuzzy inference approach and multi-path method (MF) to build a multi-path tree from the source node to the destination node.

LEACHEN clustering algorithm

The main purpose of LEACHEN method is to prevent the node with low energy from becoming the CH, and control the number of the CH to the optimal number as well as reduce the uneven distribution of CHs during every round. In this way, it can reduce the energy cost and extend the lifetime of the network.

The energy of CH will run out soon because CH nodes consume more energy than non-CH nodes. In order to solve this problem, researchers have proposed many protocols and algorithms about energy efficiency recently. Heinzelman et al. ²¹ proposed the LEACH algorithm which is an elegant cluster–based hierarchical protocol optimizing the energy efficiency in sensor network. The basic idea of this algorithm is randomly electing CH periodically and distributing the traffic numbers of the whole network evenly to each sensor node, which can reduce the network energy consumption and improve the network lifetime.

LEACH method reconfigures clusters repeatedly. Each period named “round” during which the LEACH algorithm elects the CH for each cluster and its member nodes transmit data to their corresponding CH. Then, the CH sends the aggregation data to the base station. Each round is composed of two stages: establishment phase and stabilization phase. During the establishment phase, each node generates a random value between 0 and 1. If the random number of a node is less than the threshold value $T(n)$ , then the node is the CH. $T(n)$ is calculated as

$$T(n)=\{\begin{array}{cc}\frac{P_{\mathrm{opt}}}{1-P_{\mathrm{opt}}·(r\mathrm{mod}\frac{1}{P_{\mathrm{opt}}})}\hfill & n\in G\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(5)

where $P_{\mathrm{opt}}$ is the ratio of the number of CH nodes over the average number of nodes, and $r$ is the current number of election rounds. $G$ is the set of nodes that have not been elected in the past $1/P_{\mathrm{opt}}$ election rounds.

In LEACH algorithm, each node has the same chance to be the CH, which can balance the energy cost of all nodes. However, it does not consider the residual energy of each node, if a low-power node is elected as CH, then it will accelerate the death of node and affect the network lifetime. In this article, we use the improved algorithm LEACHEN based on LEACH algorithm and SEP method ¹² to cluster the wireless sensor nodes. LEACHEN algorithm also uses the “round” concept, and every round consists of the cluster establishment phase and stabilization phase which is similar to LEACH method.

Establishment phase

The larger the stable region is, the better the reliability of the clustering process of the sensor network is. In this section, we describe the establishment phase of LEACHEN method, which improves the stabilization phase of the clustering hierarchy process using the characteristic parameters of heterogeneity. Let $m$ be the advanced node fraction of the total number of nodes $n$ and the advanced node has $\alpha$ times more energy than normal node. LEACHEN provides constraints and limits for balancing energy consumption, in order to extend the lifetime of establishment phase. The advanced node is more likely to become CH node than normal node, which is a fairly constraint for the energy consumption. If we initialize the energy of each node to $E_0$ , the energy of each advanced nodes is $E_0·(1+\alpha )$ . The average energy of the initial nodes in the network is described in equation 6.

$$\begin{array}{c}n·(1-m)·E_0+n·m·E_0·(1+\alpha )\hfill \\ =n·E_0·(1+\alpha ·m)\hfill \end{array}$$

(6)

And the average energy of LEACHEN is $(1+\alpha ·m)$ times larger than the average energy of LEACH. Let weighted selection probabilities of normal node be $P_{\mathrm{nrm}}$ , and weighted selection probabilities of advance node be $P_{\mathrm{adv}}$ . They are defined as in equations 7 and 8, respectively.

$$P_{\mathrm{nrm}}=\frac{P_{\mathrm{opt}}}{1+\alpha ·m}$$

(7)

$$P_{\mathrm{adv}}=\frac{P_{\mathrm{opt}}}{1+\alpha ·m}\times (1+\alpha )$$

(8)

where the ratio of advanced node in the total number of nodes is $m$ , and the energy of advanced node is $\alpha$ times larger than the normal node. $T(s_{\mathrm{nrm}})$ is the average probability of the normal node to be the CH when it has not yet become a CH in the $r$ round, that is, the threshold of the normal node. Set $T(s_{\mathrm{adv}})$ be the average probability of advanced node becoming the CH but in the $r$ round it has not yet become a CH, that is, the threshold of advanced node, both of them could be obtained by

$$\begin{array}{c}T(s_{\mathrm{nrm}})=\mathrm{aiadifa}\hfill \\ \{\begin{array}{cc}\frac{P_{\mathrm{nrm}}}{1-P_{\mathrm{nrm}}·\left(r\mathrm{mod}\frac{1}{P_{\mathrm{nrm}}}\right)}\times \frac{E_{\mathrm{nr}{m}_{\mathrm{current}}}}{E_{\mathrm{nr}{m}_{\mathrm{initial}}}}\hfill & \mathrm{if}{s}_{\mathrm{nrm}}\in G\prime \hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}\hfill \end{array}$$

(9)

where $r$ is the current round, and $G\prime$ is the set of normal node that has not been a CH in the last round of $1/P_{\mathrm{nrm}}$ at each step. $T(s_{\mathrm{nrm}})$ is to ensure that each normal node can have the opportunity to become the CH node in the $(1/P_{\mathrm{opt}})·(1+\alpha ·m)$ round at each step. $E_{\mathrm{nr}{m}_{\mathrm{current}}}$ is the current energy of the normal node and $E_{\mathrm{nr}{m}_{\mathrm{initial}}}$ is the initial energy of the normal node

$$T(s_{\mathrm{adv}})=\{\begin{array}{cc}\frac{P_{\mathrm{adv}}}{1-P_{\mathrm{adv}}·\left(r\mathrm{mod}\frac{1}{P_{\mathrm{adv}}}\right)}\times \frac{E_{\mathrm{ad}{v}_{\mathrm{current}}}}{E_{\mathrm{ad}{v}_{\mathrm{initial}}}}\hfill & \mathrm{if}{s}_{\mathrm{adv}}\in G\prime \prime \hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(10)

where $r$ is the current round, and $G\prime \prime$ is the set of advanced node which hasn’t been a CH in the last round of $1/P_{\mathrm{adv}}$ at each step. $T(s_{\mathrm{adv}})$ is to ensure that each advanced node can have the opportunity to become the CH node in the $(1/P_{\mathrm{opt}})·((1+\alpha ·m)/(1+\alpha ))$ round at each step. $E_{\mathrm{ad}{v}_{\mathrm{current}}}$ is the current energy of the advance node. $E_{\mathrm{ad}{v}_{\mathrm{initial}}}$ is the initial energy of the advance node. Figures 3 and 4 shows the effect of SMF algorithm after clustering, where “∘” represents normal nodes, “+” represents energy nodes,“*” indicates the CH, “·” represents the dead node, and “×” represents the sink node.

Figure 3.

Network with all the nodes alive.

Figure 4.

Network with some nodes dead.

Stabilization phase

In LEACH protocol, member nodes and CHs, CHs and the base station both use direct single-hop communication. Since the member nodes are close to their corresponding CH, it is appropriate to use the direct communication. However, the distance between the CH and the base station is often far, and transport energy consumption increases exponentially with the distance increasing. Therefore, direct communication will consume relatively larger energy of CH. In order to solve this problem, the SMF protocol in this article uses multi-hop communication to transmit data from the CH to the base station, which creates a multi-hop path tree using multi-path method and fuzzy approach. Only the root node of the path or independent node without parent needs long-distance communications with the base station, while other CHs only need for close communication within the sensing area. After a period of data transmission in the stabilization phase, the network will reenter the establishment phase due to some of the nodes running out of energy. The network will go to next cycle of refactoring cluster.

Fuzzy inference approach

There are diverse applications of intelligent techniques in WSNs. ³¹ One is the fuzzy logic control which is capable of making real time decisions, even information is not complete. Conventional control systems should have the accurate value of parameters in the environment, which generally does not exist in reality to get results. Nonetheless, fuzzy logic systems not only can manipulate the linguistic rules in a natural way, but also can be used for context by blending different parameters-rules combined together to produce the suitable result.

The fuzzy inference system (FIS) consists of four aspects, a fuzzifier, fuzzy rules, a fuzzy inference engine, and a defuzzifier. In Mamdani and Asilian, ³² the authors show that there are three kinds of commonly used fuzzy inference rules model: Mamdani model, Sugeno models, and Tsukamoto model.

This article selects Mamdani model due to its simplicity. ³³ The process is performed in five steps:

1. Fuzzification of the input. The first step of the FIS is taking the crisp inputs and determining the degree to which these inputs belong to each of the appropriate fuzzy sets. The reasoning of the FIS depends on many fuzzy inference rules and each rule depends on that inputs parse some different fuzzy sets. For example, if U is identified with the parameter measuring temperature, then fuzzy sets over U can be “cold, cool, moderate, warm, and hot.” After blurring the inputs according to the different semantic sets, we can process the calculation of the rules. Each input variable will be blurred according to the corresponding membership functions.

2. The application of the fuzzy operator. After the fuzzification of the inputs, we can know the satisfied extent of each part in antecedent for each fuzzy rule. If there are several parts of a given rule, the fuzzy operator can get one value which represents the result of the prerequisites to this rule. The input of the fuzzy operator is two or more membership values acquiring from the fuzzification input variables and the input is a separate real value.

3. Fuzzy reasoning. We should pay attention to the weight of the rule before using the fuzzy implication to do the fuzzy inference. Every rule has a weight, the range of which is [0, 1]. Generally, the weight value is 1. Once the weight value is 0, it will not have any effect during the process of fuzzy inference. Distributing the appropriate weight to the rules means achieving the fuzzy implication.

4. Aggregation of the rule outputs. Since the decision is made based on the process of testing all the rules in the FIS, we should find some way which can combine the rules to make decisions. Aggregation can combine the fuzzy sets. Generally, the execution order of the rules is not important because the method of aggregation can be exchanged.

5. Defuzzification. The input of the defuzzification process is a fuzzy set of the aggregate output of the last step and the output is a single crisp number. During the process of defuzzification, it finds the point where a vertical line would slice the aggregate set into two equal masses. However, the aggregation of the fuzzy set including many output values, we should defuzzify them and parse a single value from the fuzzy sets. Defuzzification method includes centroid method, bisector method, middle of maximum method, largest of maximum method, and smallest of maximum method. In this article, we adopt the most commonly used formula of gravity calculation, and the value of the node cost (NC) obtained using gravity method of defuzzifier could be represented as

$$\mathrm{NC}\_\mathrm{value}=\frac{\sum _{i=1}^n{U}_i·c_i}{\sum _{i=1}^n{U}_i}$$

(11)

where $U_i$ is the output of the rule base $i$ , and $c_i$ is the center of the output membership functions.

FIS employed in this article is shown in Figure 5 which constructs the fuzzy logic system with residual energy and traffic number as input, NC as output. The value range of remaining energy is [0, 10], and the value range of traffic load is [0, 10] as well as NC is [0, 1]. In the simulation environment, we select the field of fuzzy variable for input and output, when the environment changes, the value range can be modified.

Figure 5.

Fuzzy logic system.

The linguistic variables used to represent the node remaining energy and node traffic load are divided into five levels: very low, low, medium, high, and very high, respectively, and the outcome to represent the node cost is divided into five levels: very small, small, medium, large, and very large, respectively.

Membership function is a curve which defines how each point of input interval map to a membership degree which is between 0 and 1. This article selects the trapezoid membership function and triangle membership function. Equation (12) shows the trapezoid membership function while equation (13) is the triangle membership function

$$f(x;a,b,c,d)=\max \{\min \{\frac{x-a}{b-a},1,\frac{d-x}{d-c}\},0\}$$

(12)

where the parameters $a$ and $b$ are in the bottom of the membership function figure while $c$ and $d$ are in the top of the membership function figure, respectively

$$f(x;a,b,c)=\max \{\min \{\frac{x-a}{b-a},1,\frac{c-x}{c-b}\},0\}$$

(13)

where the parameters $a$ and $b$ are in the bottom of the membership function figure, respectively, while $c$ is in the top of the figure of membership function.

The fuzzy rule base currently includes rules like the following: if the remaining energy is very high and the traffic load is very low, then the node cost is very large. Based on the two fuzzy input variables, 25 fuzzy mapping rules are defined in Table 1. We use trapezoid membership functions to represent the fuzzy sets very low, very high, very small, and very large while triangle membership functions to represent other fuzzy sets. The corresponding linguistic states of the membership functions are represented in Figure 6 while the output surface of FIS with two inputs and one output is shown in Figure 7.

Table 1.

If-then rules.

No.	Antecedent		Consequent
	RE(n)	TL(n)	Node cost(n)
1	Very low	Very low	Small
2	Very low	Low	Very small
3	Very low	Medium	Small
4	Very low	High	Small
5	Very low	Very high	Small
6	Low	Very low	Medium
7	Low	Low	Medium
8	Low	Medium	Small
9	Low	High	Small
10	Low	Very high	Very small
11	Medium	Very low	Large
12	Medium	Low	Medium
13	Medium	Medium	Medium
14	Medium	High	Small
15	Medium	Very high	Small
16	High	Very low	Very large
17	High	Low	Large
18	High	Medium	Large
19	High	High	Medium
20	High	Very high	Medium
21	Very high	Very low	Very large
22	Very high	Low	Very large
23	Very high	Medium	Very large
24	Very high	High	Large
25	Very high	Very high	Large

Figure 6.

Membership functions of input and output variables.

Figure 7.

Output surface of fuzzy inference system with two inputs and one output.

Multi-path method

Due to the reliability of multi-path routing technology and the ability of balancing the traffic load in network, multi-path method is used in wired networks originally. In recent years, this technology has been applied to wireless ad hoc networks and WSNs to improve the efficiency of energy utilization and prolong the network lifetime. Multi-path method employs the evaluation function $W(i,j)$ to seek the next hop and formula (14) is the expression of the evaluation function

$$\begin{array}{c}\multicolumn{1}{c}{W(i,j)=\mathrm{factor}\times \left(\frac{\mathrm{cost}}{\mathrm{Max}\_\mathrm{cost}}\right)+(1-\mathrm{factor})}\\ \multicolumn{1}{c}{\times \left(\frac{\mathrm{Max}\_\mathrm{distance}-\mathrm{distance}}{\mathrm{Max}\_\mathrm{distance}}\right)}\end{array}$$

where $\mathrm{cost}$ is obtained using FIS which integrated the remaining energy and traffic load, and its domain is [0, 1]. The variable $\mathrm{distance}$ is the distance between the CH and one of its neighbor nodes, which is calculated using classical Euclidean distance method. ³⁴ $\mathrm{Max}\_\mathrm{cost}$ is the maximum cost of all the nodes, and $\mathrm{Max}\_\mathrm{distance}$ is the maximum distance in the test area. The variable $\mathrm{factor}$ is employed to balance the parameters of the energy and distance. Its value range is [0, 1].

After clustering with the algorithm in section “LEACHEN clustering algorithm” of this article, the cluster has been constructed. The CH $C(i)$ calculates the weight $W(i,j)$ and broadcasts messages which include the ID and the weight of the node to its neighboring CH. Each CH compares the weight sent by other CHs and selects one with the maximum weight called $\mathrm{NeiMax}$ . Then, comparing $\mathrm{NeiMax}$ with the weight of the CH itself, if $\mathrm{NeiMax}$ is larger, we will select the corresponding CH as the PN of the CH $C(i)$ . Otherwise, the PN of $C(i)$ is the base station. Sink node is the root node of the multi-path tree. Thus, the CH which is close to the base station and has enough energy will have more chance to be the PN. CH along this path will integrate the collected data and transmit them to the root node.

The specific process of multi-path algorithm adopted in this article is as follows:

Input:

1. The CH number N;

2. The information of CH including coordinates, cost values, and so on;

3. The information of sink node location.

Output: multi-path tree

The main steps of the algorithm are as follows:

1. Draw the Voronoi diagram according to the corresponding CHs: get the Voronoi diagram according to the corresponding coordinate position of the CHs in the test area. Then, the test area is divided into N small areas and there is only one CH in each small area.

2. Find the neighbor CHs of each CH $C(i)(i\in [1,N])$ : For any two CHs, if they have same edges in their corresponding polygons, that is, they have two or more common vertexes in their according polygons, the two CHs are neighbors, and the ID number of neighbor CH as well as the distance between them will be saved.

3. Calcuate the weight $W$ of each neighbor nodes of CHs: compute the weight $W(i,j)$ of the j (j ∈ [1, S], $S$ is the total number of neighbor nodes of $C(i)$ ) neighbor node of CH $C(i)$ using formula (14).

4. Determine the PN of each CH: traverse all the neighbor nodes $C(i)·\mathrm{neighbor}[j]$ of CH $C(i)$ and search the node with the maximum weight $W$ from its neighbor nodes as the PN of the CH. Otherwise, sink node is the PN of $C(i)$ .

5. Construct the multi-path tree: the PN of CH $C(i)$ is sink node or one of its neighbor nodes. Build the path from the node $C(i)$ to $C(i).\mathrm{father}$ according to the PN information recorded by the CH $C(i)$ . The algorithm flow chart of the combination of the fuzzy inference approach and multi-path method is shown in Figure 8.

Figure 8.

Flow chart of the combined methods of fuzzy inference and multi-path.

Performance evaluations

This section presents the experiment environment, parameters, metrics, and the experiment results.

Experiment environment

The SMF method is implemented in this article using MATLAB 2010a platform. The evaluation results are compared in terms of the time of the first node dead, average residual energy, the number of sensor nodes alive, and so on with the methods in AlShawi et al. ²² and Yuan et al. ²³ under the same experimental conditions. In order to verify the adaptive capacity of SMF algorithm under different network topologies, this article adopts two topological regions A and B. The region size of A is $100\mathrm{m}\times 100\mathrm{m}$ while the region size of B is $200\mathrm{m}\times 50\mathrm{m}$ . The positions of the sink node in A and B areas are (50, 200), (100, 100), respectively. The proposal considers the energy consumption of sending data, receiving data, and data fusion, but ignored the situation of potential data loss. The packet size is 2000 bit, and CH will consume the energy of 5 nJ when it fuses 1 bit data. The parameters used in the simulation are shown in Table 2. Once nodes are placed, they will not move any more. The node will dead when the energy value is zero. The energy consumption model used in this experiment has been explained in detail in section “Energy model.”

Table 2.

Simulation parameters.

Parameter			Value
Topographical area (m)	A		100 m × 100 m
	B		200 m × 50 m
Sink location	A		(50, 200)
	B		(100, 100)
Initial energy of node	MF, M		0.55 J
	LEACHEN, SMF, CF, CM	Normal node	0.5 J
		Advanced node	1 J
Radio model	$E_{\mathrm{DA}}$		5 nJ/bit
	$E_{\mathrm{elec}}^{\mathrm{Tx}}$ or $E_{\mathrm{elec}}^{\mathrm{Rx}}$		50 nJ/bit
	${\epsilon }_{\mathrm{fs}}$		10 pJ/bit/m2
	${\epsilon }_{\mathrm{mp}}$		0.0013 pJ/bit/m4
Number of nodes	100
Limit of transmission distance (m)	30 m
Packet data size	2 K bit
$P_{\mathrm{opt}}$	0.1
$m$	0.1
$\alpha$	1

Experiment results

Comparison of first node dies and half of the nodes alive in WSNs

In Tsai et al., ¹⁵ the authors employed the required rounds of the first node dies (FND) and half of the nodes alive (HNA) as the metrics to evaluate the advantages and disadvantages of the method. FND metric is useful in these scenarios where it is necessary that all nodes stay alive as long as possible, such as intrusion and fire detection. In addition, HNA metric is useful in these scenarios where sensors are placed in proximity to each other. Adjacent sensors could record related or identical data. In these cases, the whole network can still work normally, even with a single or few nodes dead. The round numbers of FND and HNA of Fuzzy and A-star (FA) algorithm ²² and Cluster, Fuzzy and A-star (CFA) method ²³ in the test areas A and B are shown in Figures 9 and 10, respectively.

Figure 9.

Experiment results of FND and HNA in the area A.

Figure 10.

Experiment results of FND and HNA in the area B.

In the region A, the analysis for FND shows that CFA and FA methods began to appear the death of the first node in 1857th round and 161th round, respectively, while SMF in 2083th round began to appear the death of the first node. As for FND, the SMF algorithm achieves 12.17% and 1193.79% improvements by comparing the methods of CFA and FA. The analysis and comparison by the HNA show that in round 2174th, CFA algorithm has half nodes survived and in round 789th, FA algorithm has half nodes survived, while the SMF algorithm has half of the surviving nodes in round 2418th. HNA improves by 11.22% and 206.46% compared with CFA and FA algorithm.

In the region B, the analysis for FND shows that CFA and FA methods began to appear the death of the first node in 1834th round and 156th round, respectively, while SMF in 1931th round began to appear the death of the first node. As for FND, the SMF algorithm achieves 5.29% and 1137.82% improvements by comparing the methods of CFA and FA. The analysis and comparison by the HNA shows that in round 2183th, CFA algorithm has half nodes survived and in round 756th, FA algorithm has half nodes survived, while the SMF algorithm has half of the surviving nodes in round 2382th. HNA improves by 9.12% and 215.08% compared with CFA and FA algorithm.

The analysis above demonstrates that SMF algorithm outperforms the CFA method and FA approach in terms of the metrics of FND and HNA in both A and B topological areas. Thus, the new method not only extends the stabilization phase of the network but also prolongs the network lifetime.

Comparison of remaining energy in the network in WSNs

Reducing energy consumption of the sensor nodes and network is one of the important factors considered in designing network. Figure 11 shows the average residual energy of the network in area A while Figure 12 shows the average residual energy of the network in area B. In both area A and area B, the average remaining energy of SMF algorithm is higher than that of CFA method and FA approach.

Figure 11.

Average remaining energy of nodes in area A.

Figure 12.

Average remaining energy of nodes in area B.

Comparison of surviving node numbers in WSNs

The number of nodes alive is one of the most important metrics to reflect the life cycle of the network. It can be seen from Figures 13 and 14 that the proposal outperforms the CFA method and FA approach in terms of the number of nodes alive. In addition, compared with the CFA method and FA approach, the algorithm proposed in this article has a shorter time of node death (i.e. the D-value between the time of all nodes death and the time of the first node death), which reflects the traffic load balance of the nodes of the proposal is superior to CFA method and FA approach.

Figure 13.

Number of nodes alive in area A.

Figure 14.

Number of nodes alive in area B.

The method in this article based on the uneven clustering LEACHEN algorithm can better balance the energy cost of CHs. It adopts the fuzzy inference method which takes into account the remaining energy, traffic load, and minimum hops, to select the optimal node of the multi-path tree. Using the SMF algorithm can improve the CHs energy consumption in the transmission route and balance the energy consumption of each node, as well as prolong the lifetime of the network. From the comparison of SMF algorithm, CFA method, and FA approach in Figures 9–14, we conclude that the performance of SMF algorithm is better than that of the CFA method and FA approach. Moreover, SMF method’s performance is very stable both in area A and area B, which demonstrates that the proposed algorithm can adapt different topological areas and has certain universality.

Conclusion and future directions

A new clustering method named LEACHEN as well as an efficient evaluation function for multi-path algorithm are proposed in this article to seek the next hop, which balances the influence of the minimum hops, the traffic load, and the remaining energy. The proposed SMF method uses LEACHEN method to divide the sensor nodes in WSNs and adopts multi-hops sending the message from CHs to base station during the stabilization phase. The method also uses the fuzzy inference method and considerate many factors, electing the best node in the multi-path tree from CHs. The simulation results shows that it is the root node of the tree which needs to communicate directly to the base station and other CHs only need transmit the message to their neighbors in the sensing area. Experiment results demonstrate that SMF method is superior to the CFA method and FA approach in the aspects of FND, HNA, average remaining energy, and the number of nodes alive. SMF routing algorithm not only extends the stabilization phase of the network but also reduces the energy cost, balances the traffic loads, and prolongs the network lifetime. However, in the real world, there are many factors that should be taken into account. On-going research will solve the practicability of using the SMF method for data gathering in the real environment.