# CAF: Cluster Algorithm and A-Star with Fuzzy Approach for Lifetime Enhancement in Wireless Sensor Networks

Authors: Yali Yuan; Caihong Li; Yi Yang; Xiangliang Zhang; Lian Li
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Energy is a major factor in designing wireless sensor networks (WSNs). In particular, in the real world, battery energy is limited; thus the effective improvement of the energy becomes the key of the routing protocols. Besides, the sensor nodes are always deployed far away from the base station and the transmission energy consumption is index times increasing with the increase of distance as well. This paper proposes a new routing method for WSNs to extend the network lifetime using a combination of a clustering algorithm, a fuzzy approach, and an A-star method. The proposal is divided into two steps. Firstly, WSNs are separated into clusters using the Stable Election Protocol (SEP) method. Secondly, the combined methods of fuzzy inference and A-star algorithm are adopted, taking into account the factors such as the remaining power, the minimum hops, and the traffic numbers of nodes. Simulation results demonstrate that the proposed method has significant effectiveness in terms of balancing energy consumption as well as maximizing the network lifetime by comparing the performance of the A-star and fuzzy (AF) approach, cluster and fuzzy (CF)method, cluster and A-star (CA)method, A-star method, and SEP algorithm under the same routing criteria.


---

## Body

## 1. Introduction

In recent years, wireless sensor networks have gained the worldwide attention. In particular with the development of microelectromechanical system (MEMS) technology, more and more intelligent sensors have come into being. These sensors are small, with limited processor and computing resources, and are cheaper than traditional sensors. Smart sensor nodes can be used to detect, measure, and gather information from the surrounding environment. They can pass the collected data to the user through a number of local decision-making systems.As a new mode of information acquisition and processing, wireless sensor networks (WSNs) [1] have now become a hot research of concern at home and abroad. WSN collects the information of perceived objects in the network coverage area through large numbers of sensor nodes deployed in the monitoring region and periodically provides the end users with information which has been collected and processed by means of the multihop wireless communication method. WSNs, which do not acquire the support of the fixed network, have features of fast expansion and strong survivability and also have a wide field of applications for military target tracking and monitoring [2, 3], natural disasters rescue [4], biological medical health monitoring [5, 6], dangerous environmental exploration and remote earthquake sensing [7], environmental monitoring [8, 9], and special fields like these. In large-scale data acquisition networks, the energy of sensor nodes is provided by a small inexpensive battery which can run a long time [10]. Figure 1 shows the schematic of WSN, which consists of sensor nodes, base station, task management centers, and so on.Figure 1
Components of a wireless sensor network.WSNs are always deployed at a remote location where people are unable to get close and energy cannot be replaced. Wireless sensor nodes are small and battery-powered, which leads to many problems, such as limited capacity of single node processing and storage, limited communication range, and limited energy. The energy issue is the most critical. Uneven energy consumption is an inherent problem in multihop WSNs. Imbalance in energy consumption reduces the network lifetime to a large extent. The whole network can be split because of the death of some nodes, ultimately leading to the termination of the entire network. The lifetime of a wireless sensor network is a critical parameter for evaluating the performance of routing protocols [11, 12]. Therefore, designing an effective policy to control energy loss is the core issue for prolonging the network lifetime [13, 14].In order to solve this problem in WSNs, researchers have proposed a variety of methods. In [15], the authors proposed to shorten the hop count of the route to reduce the energy consumption of end-to-end transmission and used the ratio of currently selected path hops and the shortest path as metrics. The authors of [16] presented the optimized forwarding by fuzzy inference systems (OFFIS) for flat sensor networks. OFFIS protocol favors four descriptors (small hops, shortest path, maximum remaining battery power, and link usage) to select the best node from candidate nodes in the forwarding paths. A link-aware clustering mechanism (LCM) for energy-efficient routing in WSNs is proposed to determine an energy-efficient and reliable routing path [17]. The LCM algorithm evaluated the qualification of cluster head (CH) nodes and gateways to construct clusters. Liao et al. [18] used a balanced clustering algorithm with distributed self-organization for WSNs on the basis of their distance and density distribution, taking into account the optimal configuration of clusters. This makes it essentially different from the previous clustering algorithms. A Stable Election Protocol (SEP) for clustered heterogeneous WSNs is used to prolong the time interval before the death of the first node, which is crucial for many applications where the feedback from the sensor network must be reliable. SEP is based on weighted election probabilities of each node to become a CH according to the remaining energy in each node [19]. Some of the researchers adopted the combination of fuzzy and clustering method. In [20], Gupta et al. proposed to use three fuzzy descriptors (residual energy, concentration, and centrality) during the cluster-head selection. In [21], a fuzzy-logic-based clustering approach with an extension to the energy predication (LEACH-ERE) has been proposed to prolong the lifetime of WSNs using the fuzzy method to evenly distribute the workload. It selects the CHs considering expected residual energy of the sensor nodes. Rana and Zaveri [22] exploited the A-star method to search the optimal route from the source to destination. If the sensor node’s residual energy level is below the predefined minimum energy level, it would not participate in routing. The work in [23] presented a combination of a fuzzy approach and an A-star algorithm (AF) in terms of balancing energy consumption and maximization of network lifetime. The authors used three fuzzy descriptors (the highest remaining battery power, minimum number of hops, and minimum traffic loads) and compared the proposed approach with the A-star search algorithm and fuzzy approach using the same routing criteria in two different topographical areas.From the aforementioned literatures, we note that most of the present routing algorithms are routing methods based on flat multipath routing protocols or routing protocols with simple clustering. As for the WSNs with large sensor nodes, uneven nodes distribution density, and real-time changing network topology, the flat multipath routing methods may cause network partition because some nodes that are part of the efficient path are drained from their battery energy quicker. In many cases, the lifetime of a sensor network is over as soon as the battery power in critical nodes is depleted. The simple clustering routing protocols send the merging data directly to the sink node. However, most of the cluster heads are far away from the sink node and the energy cost by transmission is index times increasing with respect to distance. As to the above problems, this paper presents a new routing method called CAF which means a cluster algorithm and A-star with fuzzy approach for lifetime enhancement in WSNs. The CAF routing method, which takes into account the advantage of SEP algorithm, A-star method, and fuzzy inference approach by favoring the remaining power, the minimum hops, and the traffic numbers of nodes, provides a good solution to the problem of uneven energy consumption and prolongs the lifetime of the network effectively. The proposal adopts a method of single hop within clusters and multihop among clusters to communicate.The rest of this paper is organized as follows. Section2 describes the concept of routing metrics and presents some assumptions. In Section 3, the SEP method is put forward, fuzzy approach, and A-star algorithm by describing each part in detail. In Section 4, the CAF algorithm is proposed. Then, a radio energy dissipation model and the simulation results based on simulation environment, parameters, and metrics are presented in Section 5. Finally, Section 6 concludes this paper.


## 2. Preliminaries

This section describes the concept of routing metrics which have been used to prolong the lifetime of WSNs and presents some assumptions on which all works have been done in this paper.


### 2.1. Assumptions

(a)
The sensors are randomly (uniformly) distributed and are not mobile, the coordinates of the sink and the dimensions of the sensor field are known, and the sink is not energy limited (at least in comparison with the energy of other sensor nodes) [19]. The base station’s position is fixed and far from sensor nodes in the network.
(b)
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 [19].
(c)
Each node can be informed of the total energy in the network and set the probability of selected CHs according to their residual energy [24].
(d)
All sensor nodes are randomly distributed in the area and each sensor node is assumed to recognize its own position as well as that of its neighbors and the sink [23].
(e)
Each node has a certain amount of traffic pending in the node’s queue. The node’s queue includes the application traffic and also the traffic that a node has already committed to forward [23].
(f)
The base station prepares the routing schedule and broadcasts it to each node. The A-star algorithm which is used to find the optimal route from the node to the base station is applied to each node [23].


### 2.2. Definition of Terminology

(a)
Remaining power (RP): in WSNs, the most critical aspect of routing is energy efficiency. Under this standard, the size of the battery capacity in the current node is in focus. Routing protocols adopted by this measure tend to select a path which has maximum total energy from the source node to the destination node. That is, the node which has more residual energy is more likely to be selected as the node in the best path [25, 26].
(b)
Small multiple hops (SMH): the SMH are a common standard in routing protocols which passes through a minimum number of relay nodes from the source node to the destination node. The basic idea of this measure is that it takes the shortest path to get end-to-end relay nodes and uses less resource consumption, because of a minimum of forwarding nodes involved [15, 25–27].
(c)
Traffic numbers (TN): the node traffic numbers can be defined as the pending amount of traffic in a node’s queue. These traffic numbers include the amount of the transfer being sent and previously being transmitted. In the case of the concentrated events of a particular subregion, using the shortest path would cause an implosion phenomenon on this path. High loading will cause sensor node data queue overflows, resulting in the loss of important information. In addition, the entire sensor network lifetime would be shortened, due to the quick energy consumption of batteries in the sensor nodes [26–28].
(d)
Stable phase: it is the time interval between the operation of the network and the death of the first sensor node in the network.
(e)
Period of instability: it is the time interval between the death of the first node and the death of the last one in the network.
(f)
Network lifetime: it is the time interval between the operation of the network and the death of the last sensor node in the network.


## 2.1. Assumptions

(a)
The sensors are randomly (uniformly) distributed and are not mobile, the coordinates of the sink and the dimensions of the sensor field are known, and the sink is not energy limited (at least in comparison with the energy of other sensor nodes) [19]. The base station’s position is fixed and far from sensor nodes in the network.
(b)
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 [19].
(c)
Each node can be informed of the total energy in the network and set the probability of selected CHs according to their residual energy [24].
(d)
All sensor nodes are randomly distributed in the area and each sensor node is assumed to recognize its own position as well as that of its neighbors and the sink [23].
(e)
Each node has a certain amount of traffic pending in the node’s queue. The node’s queue includes the application traffic and also the traffic that a node has already committed to forward [23].
(f)
The base station prepares the routing schedule and broadcasts it to each node. The A-star algorithm which is used to find the optimal route from the node to the base station is applied to each node [23].


## 2.2. Definition of Terminology

(a)
Remaining power (RP): in WSNs, the most critical aspect of routing is energy efficiency. Under this standard, the size of the battery capacity in the current node is in focus. Routing protocols adopted by this measure tend to select a path which has maximum total energy from the source node to the destination node. That is, the node which has more residual energy is more likely to be selected as the node in the best path [25, 26].
(b)
Small multiple hops (SMH): the SMH are a common standard in routing protocols which passes through a minimum number of relay nodes from the source node to the destination node. The basic idea of this measure is that it takes the shortest path to get end-to-end relay nodes and uses less resource consumption, because of a minimum of forwarding nodes involved [15, 25–27].
(c)
Traffic numbers (TN): the node traffic numbers can be defined as the pending amount of traffic in a node’s queue. These traffic numbers include the amount of the transfer being sent and previously being transmitted. In the case of the concentrated events of a particular subregion, using the shortest path would cause an implosion phenomenon on this path. High loading will cause sensor node data queue overflows, resulting in the loss of important information. In addition, the entire sensor network lifetime would be shortened, due to the quick energy consumption of batteries in the sensor nodes [26–28].
(d)
Stable phase: it is the time interval between the operation of the network and the death of the first sensor node in the network.
(e)
Period of instability: it is the time interval between the death of the first node and the death of the last one in the network.
(f)
Network lifetime: it is the time interval between the operation of the network and the death of the last sensor node in the network.


## 3. SEP Method, Fuzzy Approach, and A-Star Algorithm

### 3.1. SEP Method

Organizing WSNs into clusters enables the efficient utilization of the limited energy resources of the deployed sensor nodes. Low energy adaptive clustering hierarchy (LEACH) protocol is an application-specific protocol architecture [24, 29]. LEACH protocol is the first one to raise the hierarchical routing protocol of data aggregation which is to balance the energy consumption of each node in the network. Periodically, CH is elected in each round, and each round of elections is as follows. Each node generates a random number in the range (0,1], if a number is less than a threshold T(n), then the node would be seen as a CH in the current round. The threshold is set as
(1)T(n)={popt1-popt·(rmod⁡(1/popt))ifn∈G0otherwise,
where popt is the probability of becoming a CH, n is the token of the node, r is the number of the current round of elections, and G is the most recent 1/popt round of the set of the CH.The clustering method in this paper uses the SEP algorithm in [19] which is an improved algorithm based on the protocol of LEACH. SEP improves the stable region of the clustering hierarchy process by the characteristic parameters of heterogeneity in which m is the advanced nodes fraction and α is the additional energy factor between advanced and normal nodes.To achieve the goal of extending the time of stable phase, advanced nodes have more chance to become cluster heads than the normal nodes, which is equivalent to a fairness constraint on energy consumption. The new heterogeneous setting which consists of advanced and normal nodes has no effect on the spatial density of the network so the priori setting ofPopt has the same value as the one from (1). SEP method is based on the weighted election probabilities of each node in order to become a CH according to the residual energy in each node.The main objective of the SEP method is to avoid the node with low energy becoming a CH and control the number of the CHs to the optimal number as well as reducing the uneven distribution of CHs during every round. In this way, it can reduce the energy cost and extend the life of the network.


### 3.2. Fuzzy Approach

Fuzzy inference is an approximate inference that simulates people’s everyday inference, which is booming in the mathematical core of fuzzy control technology. Zadeh introduced fuzzy logic in the 1960s to represent and use fuzzy and uncertain knowledge [30]. From the early 1980s, there have been many scholars engaged in research on artificial intelligence and committed to the study of the fuzzy logic method application in the field of artificial intelligence. These provide the basis for further improvement of the fuzzy inference or incorporation into the appropriate logical framework [31–33]. In recent years, many academicians have gradually made various improved methods of the fuzzy inference [34–36]. At present, in the research of the fuzzy theory and its applications, fuzzy logic and fuzzy inference have achieved certain results and are moving in the direction of the development of axioms, intelligence, and information. Fuzzy logic has been successfully used in a variety of areas, including communication systems [37] and prediction of water level in reservoirs [38], and as a classifier in fault diagnosis of roller bearing [39]. All of these studies have achieved good results.The fuzzy logic system, a nonlinear input-output mapping as a whole, processes information by using fuzzy set. The fuzzy setF in universe U is expressed as a membership function μF, the value of which is in the interval [0,1]. F can be expressed as F={(u,μF(u))/u∈U}.The two most important concepts in fuzzy logic are fuzzy language variables and fuzzy inference rules.Fuzzy language variables refer to words or sentences in a statement. Their value is not a usual number, but a fuzzy set is represented in fuzzy language. This value is a description to some extent. For example, the language variable “age” can be referred to as “young,” “middle,” or “old.” Language variable is an important concept, which provides a formal way to quantize language description.The fuzzy inference rule which is also named as the “if-then” rule is the core of fuzzy logic. For example, ifx is A, then y is B. In this example, A and B are language values defined, respectively, in the X,Y range by a fuzzy set. The if part “x is A” in the fuzzy rule is known as the premise or assumption of the rule, and then the part “y is B” is known as the result or conclusion. In essence, this expression describes the relationship between variables x and y. Therefore, the if-then rule can be defined as binary fuzzy relations.There is a fuzzy control rule, “ifx is Ai and y is Bi, then z is Ci,” which is achieved by a fuzzy implication (fuzzy relation) Ri and is defined as
(2)μRi≜μ(Ai,Bi→Ci)(u,v,w)i=[μAi(u),μBi(v)]⟶μCi(w),
where Ai and Bi is a fuzzy set Ai×Bi in U×V, Ri≜(AiandBi)→Ci is a fuzzy implication (relation) in U×V×W, and → represents a fuzzy implication function.The most widely used application in engineering is a rule-based fuzzy inference system (FIS), which has the following four basic elements, as shown in Figure2.Figure 2
Fuzzy system structure.The fuzzy system contains all of the applicable fuzzy algorithms and the necessary ingredients resolving all related ambiguities. It consists of the following four basic elements.(1)
Knowledge base: it includes the definition of fuzzy sets and fuzzy operators.(2)
Inference mechanisms: they perform all of the output calculation.(3)
Fuzzifier: it represents the true input value as a fuzzy set.(4)
Defuzzifier: it transfers the output fuzzy sets into real value.Knowledge base contains the definitions for each of the fuzzy sets and maintains a system operator to achieve the basic logic (AND, OR, etc.), as well as expressing fuzzy rules mapping with a rule reliability matrix. Inference units with fuzzifiers and antifuzzies calculate real output values from the real input values. The fuzzifier represents the input as a fuzzy set, making the inference unit match with it in the rules stored in the knowledge base. Then, inference units calculate the strength of each rule and output a fuzzy distribution.


### 3.3. A-Star Algorithm

Peter Hart, Nils Nilsson, and Bertram Raphael of Stanford Research Institute (now SRI International) first described the A-star algorithm in 1968 [40]. It is a combination of heuristic methods such as BFS and methods like Dijkstra algorithm [41].A-star search method is a highly efficient heuristic algorithm used in the graph searching algorithm and it is also used in finding a variable or low cost path. Noted for its performance and accuracy, it is widely used in WSNs. In practical systems, it can preprocess the graph to attain better performance [42].A-star method uses a best-first search and finds a least-cost path from a given initial node to a one goal node (out of one or more possible goals). As the A-star traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.A-star method uses a knowledge-plus-heuristic cost function of noden (usually denoted by f(n)) to determine the order in which the search visits the nodes in the tree. The cost function is a sum of two functions. Consider the following.(a)
The past path-cost function is the known distance from the starting nodes to the current node n (usually denoted by g(n)).(b)
A future path-cost function is an admissible “heuristic estimate” of the distance fromn to the goal (usually denoted by h(n)). h(n) depends on the heuristic information. In the heuristic function, the more the heuristic information (the problem of knowledge) is, the less the extending node will be, so the destination node can be searched quickly.The evaluation function used in the paper is given as(3)f(n)=g(n)+h(n).Theh(n) part of the f(n) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application-like routing, h(n) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two nodes.In short, A-star algorithm firstly creates two lists, an open list and a closed list. The open list corresponds to a container of nodes that will be checked. The closed list corresponds to a container of nodes that have already been examined. Initially, put the starting node into the open list. Then, extending the starting node means to calculate the evaluation function of all adjacent nodes. Assuming that the adjacent nodes are not in the closed list, if the evaluation function values of the nodes are larger than the values of nodes in the open list, replace the nodes in the open list, and,if not, add them to the open list. When it iterates, the optimal node will take the top of the priority list. Then, check whether it is the destination node. If so, the algorithm is finished. Otherwise, repeat the above operations. If it does not find a solution, then it can guarantee that no such solution exists. A-star algorithm will find a path with the lowest possible cost. It looks for the shortest path with minimum cost, which mainly depends on the choice of the evaluation function [43].A-star method can be accomplished as follows.(1)
Put the initial nodeS into the open list; let g^(S)=0 and f^(S)=0.(2)
If the open list is empty, then exit the algorithm and return false.(3)
Move out the first noden from the open list, which has the smallest f^(n) value; let it be best node, and put it into the closed-list.(4)
If best node is the target node, then exit the algorithm, and return to the target node.(5)
Otherwise, extend the best node. If the node does not have the successor node, go to (2).
(a)
Otherwise, generate its entire legal successor nodes. For each successor nodensuc, calculate g=g^(Best-node)+c(Best-node,nsuc).(b)
If it neither belongs to the open list nor to the closed list, then letg^(nsuc)=g and f^(nsuc)=g+h^(nsuc), and put nsuc into the open list.(c)
Ifnsuc belongs to either the open list or the closed list, and g^(nsuc)>g, then let g^(nsuc)=g and f^(nsuc)=g+h^(nsuc), and if nsuc belongs to the open list, then it is retained. If it belongs to the closed list, then it will be moved out from the closed list into the open list.(d)
Reorder thef^(n) values of the nodes in ascending order in the open list.(e)
Go to (2).


## 3.1. SEP Method

Organizing WSNs into clusters enables the efficient utilization of the limited energy resources of the deployed sensor nodes. Low energy adaptive clustering hierarchy (LEACH) protocol is an application-specific protocol architecture [24, 29]. LEACH protocol is the first one to raise the hierarchical routing protocol of data aggregation which is to balance the energy consumption of each node in the network. Periodically, CH is elected in each round, and each round of elections is as follows. Each node generates a random number in the range (0,1], if a number is less than a threshold T(n), then the node would be seen as a CH in the current round. The threshold is set as
(1)T(n)={popt1-popt·(rmod⁡(1/popt))ifn∈G0otherwise,
where popt is the probability of becoming a CH, n is the token of the node, r is the number of the current round of elections, and G is the most recent 1/popt round of the set of the CH.The clustering method in this paper uses the SEP algorithm in [19] which is an improved algorithm based on the protocol of LEACH. SEP improves the stable region of the clustering hierarchy process by the characteristic parameters of heterogeneity in which m is the advanced nodes fraction and α is the additional energy factor between advanced and normal nodes.To achieve the goal of extending the time of stable phase, advanced nodes have more chance to become cluster heads than the normal nodes, which is equivalent to a fairness constraint on energy consumption. The new heterogeneous setting which consists of advanced and normal nodes has no effect on the spatial density of the network so the priori setting ofPopt has the same value as the one from (1). SEP method is based on the weighted election probabilities of each node in order to become a CH according to the residual energy in each node.The main objective of the SEP method is to avoid the node with low energy becoming a CH and control the number of the CHs to the optimal number as well as reducing the uneven distribution of CHs during every round. In this way, it can reduce the energy cost and extend the life of the network.


## 3.2. Fuzzy Approach

Fuzzy inference is an approximate inference that simulates people’s everyday inference, which is booming in the mathematical core of fuzzy control technology. Zadeh introduced fuzzy logic in the 1960s to represent and use fuzzy and uncertain knowledge [30]. From the early 1980s, there have been many scholars engaged in research on artificial intelligence and committed to the study of the fuzzy logic method application in the field of artificial intelligence. These provide the basis for further improvement of the fuzzy inference or incorporation into the appropriate logical framework [31–33]. In recent years, many academicians have gradually made various improved methods of the fuzzy inference [34–36]. At present, in the research of the fuzzy theory and its applications, fuzzy logic and fuzzy inference have achieved certain results and are moving in the direction of the development of axioms, intelligence, and information. Fuzzy logic has been successfully used in a variety of areas, including communication systems [37] and prediction of water level in reservoirs [38], and as a classifier in fault diagnosis of roller bearing [39]. All of these studies have achieved good results.The fuzzy logic system, a nonlinear input-output mapping as a whole, processes information by using fuzzy set. The fuzzy setF in universe U is expressed as a membership function μF, the value of which is in the interval [0,1]. F can be expressed as F={(u,μF(u))/u∈U}.The two most important concepts in fuzzy logic are fuzzy language variables and fuzzy inference rules.Fuzzy language variables refer to words or sentences in a statement. Their value is not a usual number, but a fuzzy set is represented in fuzzy language. This value is a description to some extent. For example, the language variable “age” can be referred to as “young,” “middle,” or “old.” Language variable is an important concept, which provides a formal way to quantize language description.The fuzzy inference rule which is also named as the “if-then” rule is the core of fuzzy logic. For example, ifx is A, then y is B. In this example, A and B are language values defined, respectively, in the X,Y range by a fuzzy set. The if part “x is A” in the fuzzy rule is known as the premise or assumption of the rule, and then the part “y is B” is known as the result or conclusion. In essence, this expression describes the relationship between variables x and y. Therefore, the if-then rule can be defined as binary fuzzy relations.There is a fuzzy control rule, “ifx is Ai and y is Bi, then z is Ci,” which is achieved by a fuzzy implication (fuzzy relation) Ri and is defined as
(2)μRi≜μ(Ai,Bi→Ci)(u,v,w)i=[μAi(u),μBi(v)]⟶μCi(w),
where Ai and Bi is a fuzzy set Ai×Bi in U×V, Ri≜(AiandBi)→Ci is a fuzzy implication (relation) in U×V×W, and → represents a fuzzy implication function.The most widely used application in engineering is a rule-based fuzzy inference system (FIS), which has the following four basic elements, as shown in Figure2.Figure 2
Fuzzy system structure.The fuzzy system contains all of the applicable fuzzy algorithms and the necessary ingredients resolving all related ambiguities. It consists of the following four basic elements.(1)
Knowledge base: it includes the definition of fuzzy sets and fuzzy operators.(2)
Inference mechanisms: they perform all of the output calculation.(3)
Fuzzifier: it represents the true input value as a fuzzy set.(4)
Defuzzifier: it transfers the output fuzzy sets into real value.Knowledge base contains the definitions for each of the fuzzy sets and maintains a system operator to achieve the basic logic (AND, OR, etc.), as well as expressing fuzzy rules mapping with a rule reliability matrix. Inference units with fuzzifiers and antifuzzies calculate real output values from the real input values. The fuzzifier represents the input as a fuzzy set, making the inference unit match with it in the rules stored in the knowledge base. Then, inference units calculate the strength of each rule and output a fuzzy distribution.


## 3.3. A-Star Algorithm

Peter Hart, Nils Nilsson, and Bertram Raphael of Stanford Research Institute (now SRI International) first described the A-star algorithm in 1968 [40]. It is a combination of heuristic methods such as BFS and methods like Dijkstra algorithm [41].A-star search method is a highly efficient heuristic algorithm used in the graph searching algorithm and it is also used in finding a variable or low cost path. Noted for its performance and accuracy, it is widely used in WSNs. In practical systems, it can preprocess the graph to attain better performance [42].A-star method uses a best-first search and finds a least-cost path from a given initial node to a one goal node (out of one or more possible goals). As the A-star traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.A-star method uses a knowledge-plus-heuristic cost function of noden (usually denoted by f(n)) to determine the order in which the search visits the nodes in the tree. The cost function is a sum of two functions. Consider the following.(a)
The past path-cost function is the known distance from the starting nodes to the current node n (usually denoted by g(n)).(b)
A future path-cost function is an admissible “heuristic estimate” of the distance fromn to the goal (usually denoted by h(n)). h(n) depends on the heuristic information. In the heuristic function, the more the heuristic information (the problem of knowledge) is, the less the extending node will be, so the destination node can be searched quickly.The evaluation function used in the paper is given as(3)f(n)=g(n)+h(n).Theh(n) part of the f(n) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application-like routing, h(n) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two nodes.In short, A-star algorithm firstly creates two lists, an open list and a closed list. The open list corresponds to a container of nodes that will be checked. The closed list corresponds to a container of nodes that have already been examined. Initially, put the starting node into the open list. Then, extending the starting node means to calculate the evaluation function of all adjacent nodes. Assuming that the adjacent nodes are not in the closed list, if the evaluation function values of the nodes are larger than the values of nodes in the open list, replace the nodes in the open list, and,if not, add them to the open list. When it iterates, the optimal node will take the top of the priority list. Then, check whether it is the destination node. If so, the algorithm is finished. Otherwise, repeat the above operations. If it does not find a solution, then it can guarantee that no such solution exists. A-star algorithm will find a path with the lowest possible cost. It looks for the shortest path with minimum cost, which mainly depends on the choice of the evaluation function [43].A-star method can be accomplished as follows.(1)
Put the initial nodeS into the open list; let g^(S)=0 and f^(S)=0.(2)
If the open list is empty, then exit the algorithm and return false.(3)
Move out the first noden from the open list, which has the smallest f^(n) value; let it be best node, and put it into the closed-list.(4)
If best node is the target node, then exit the algorithm, and return to the target node.(5)
Otherwise, extend the best node. If the node does not have the successor node, go to (2).
(a)
Otherwise, generate its entire legal successor nodes. For each successor nodensuc, calculate g=g^(Best-node)+c(Best-node,nsuc).(b)
If it neither belongs to the open list nor to the closed list, then letg^(nsuc)=g and f^(nsuc)=g+h^(nsuc), and put nsuc into the open list.(c)
Ifnsuc belongs to either the open list or the closed list, and g^(nsuc)>g, then let g^(nsuc)=g and f^(nsuc)=g+h^(nsuc), and if nsuc belongs to the open list, then it is retained. If it belongs to the closed list, then it will be moved out from the closed list into the open list.(d)
Reorder thef^(n) values of the nodes in ascending order in the open list.(e)
Go to (2).


## 4. Proposed CAF Algorithm

The lifetime of a wireless sensor network is a critical parameter for assessing the performance of routing protocols. Imbalance in energy consumption reduces the network lifetime to a large extent. Therefore, designing an effective routing method to control energy loss is the core issue for prolonging the network lifetime.The primary goal of this paper is to design a protocol which can extend the network lifetime by limiting energy consumption and balance the distribution of energy cost. This paper proposes the CAF routing method which makes use of the SEP method, fuzzy approach, and A-star algorithm. The proposal selects the optimal node to construct the multihop tree by considering the three routing criteria mentioned in Section2.2 (i.e., highest remaining power, minimum number of hops, and lowest traffic numbers). The implementation of the proposal includes four parts.


### 4.1. Implementation of the SEP Method

As with LEACH, SEP in each round consists of two phases: set-up phase and stability phase.


#### 4.1.1. Set-Up Phase

The set-up phase is essentially the preparation stage of data transmission. This stage is primarily for the transmission of the control information, the formation of the clusters, and the random generation of the CHs. This stage, without data transmission, but with a series of preparatory work prior to data transmission, fully prepares for the data transfer.This paper optimizes the CH selection algorithm and aims to let the nodes with more energy rather than less energy become the first cluster head in the clusters, thus avoiding the lesser energy node’s premature death because of the fast energy consumption while being elected as the CH and subsequently affecting the network lifetime. Therefore, the energy factor can be added during the process of the choosing CHs which ensures that the node with more residual energy can be elected to be the CH and all nodes run out of energy almost at the same time.The critical aspect of the cluster set-up phase is to set the threshold asT(n). The selection of the CH in the SEP method is carried out from the advanced node and the normal node. The ratio of the advanced node in the total number of nodes is m. Set the total nodes as n. The energy of the advanced node is α times larger than the normal node.SEP provides constraints and limits for balancing energy consumption in order to extend the lifetime of the steady state. The advanced node is more likely to become a CH node than a normal node, which is fairly a constraint for the energy consumption. If the energy of each node is initialized toE0, the energy of each advanced nodes is E0·(1+α). The total energy of the initial nodes in the network is n·(1-m)·E0+n·m·E0·(1+α)=n·E0·(1+α·m).Total energy of the SEP is(1+α·m) times larger than the total energy of the LEACH.Let the weighted selection probabilities of the normal node bepnrm and let the weighted selection probabilities of the advanced node be padv. They are defined as
(4)pnrm=popt1+α·m,padv=popt1+α·m×(1+α),
where the ratio of the advanced node in the total number of nodes is m and the energy of the advanced node is α times larger than the normal node.T
(
s
nrm
), the threshold of the normal node, is the average probability of the normal node which has not yet become the CH in the r round to be the CH. T(sadv), the threshold of advanced node, is the average probability of the advanced node which has not yet become the CH in the r round to be the CH. They could be obtained by (5) and (6). Consider
(5)T(snrm)={pnrm1-pnrm·(rmod⁡(1/pnrm))iifsnrm∈G′0otherwise,
where r is the current round and G′ is the set of normal nodes that have not been CHs within the last 1/pnrm round at each step. T(snrm) is to ensure that each normal node can have the opportunity to become the CH node in the (1/popt)·(1+α·m) round at each step
(6)T(sadv)={padv1-padv·(rmod⁡(1/padv))ifsadv∈G′′0otherwise,
where r is the current round and G′′ is the set of advanced nodes that have not been CHs in the last 1/padv round at each step. T(sadv) is to ensure that each advanced node can have the opportunity to become the CH in the (1/popt)·(1+α·m)/(1+α) round at each step.Figures3 and 4 have shown the different situation of the cluster figures using the CAF algorithm. In these two figures, the Voronoi diagram was used to cluster the nodes in WSN. Consider a set of coplanar points P. For each point Px in the set P, you can draw a boundary enclosing all the intermediate points lying closer to Px than to other points in the set P. Such a boundary is called a Voronoi polygon, and the set of all Voronoi polygons for a given point set is called a Voronoi diagram which is composed of many Voronoi cells. Each cell has a CH.Figure 3
A clustering wireless sensor network with all nodes being alive.Figure 4
A clustering wireless sensor network with some nodes being dead.In these two figures, “∘” is a normal node, “*” is a CH, “+” is an advanced node, and “∙” is a dead node. If the nodes are alive, the nodes which are in the same Voronoi cell will report messages to the CH of this cell.


#### 4.1.2. Stability Phase

The stability phase is the cluster communication phase. In the LEACH protocol, between the node in the cluster and the CH and between the CH and the base station both use direct single hop communication. The node in the cluster is close to the CH, so the easy direct communication can be used. However, the CH node is often far from the base station, and the transport energy consumption increases exponentially as the distance increases. Therefore, direct communication will consume a relatively large amount of energy of the CH. To solve this issue, the CAF protocol in this paper uses multihop communication to transmit data from the CH to the base station, which creates a multihop path tree using A-star method and fuzzy approach. Only the root node of the path or the independent node which has no parent node needs a long distance communication with the base station, while other CHs only need close communication within the sensing area.After a period of the stability of the data transmission phase, the network reenters the set-up phase of the cluster and goes to the next cycle of the cluster of refactoring. The flowchart of the SEP method is shown in Figure5.Figure 5
Flowchart of the SEP method.


### 4.2. Implementation of Fuzzy Approach

Find the best node by integrating several factors in the problem, such as residual energy, traffic numbers, and minimum number of hops. This is equivalent to finding the optimal path from the start node to the sink node. For the fuzzy method, the fuzzy value is processed by FIS, which includes a rule base and various ways to infer these rules. There are a series of if-then rules in rule base, and fuzzy sets are combined with the input and output fuzzy language variables which are described by the fuzzy implication operator to construct the FIS jointly.To handle uncertainties, this paper has used the FIS for the probability computation of each node as shown in Figure6. The two input variables for the FIS are the residual energy and the traffic numbers, and the single output parameter is the probability of a node to be selected as the best node in the optimal path. The greater the probability value will mean that the node has more chance to be a best node. The value range of RE is [0,10], the value range of TN is [0,10], and the probability is [0,1]. According to the current simulation environment, the fields of fuzzy variables are selected for inputs as well as outputs. When the environment changes, the value ranges can be modified as well.Figure 6
Fuzzy structure with two inputs and one output.The values of the residual energy for fuzzy input variables are very low (VL), low (L), medium (M), high (H), and very high (VH). The values of the traffic number for fuzzy input variables are very low (VL), low (L), medium (M), high (H), and very high (VH). The values of the node probability for fuzzy output variables are very small (VS), small (S), medium (M), large (G), and very large (VG). Membership function (MF) is a curve, and it defines how each point of the input space is mapped to a membership between 0 and 1. This paper selects the Gaussian membership function as the membership function for input and output variables. Equation (7) shows the Gaussian membership function as follows:
(7)u(x;σ,c)=exp⁡(-[(x-c)σ]2),
where c and σ are the center and standard deviation of membership function, respectively.The membership functions of the input-output fuzzy variables and surface viewer of the FIS are given in Figures7 and 8, respectively. Nodes with small probability would not be selected as the next hop.Figure 7
Membership functions of the input-output fuzzy variables.Figure 8
Surface viewer of the FIS with two inputs and one output.The probability calculation is accomplished using predefined fuzzy if-then mapping rules to handle the uncertainty. Based on the two fuzzy input variables, 25 fuzzy mapping rules are defined in Table1. From the fuzzy rules, the fuzzy variable probability can be obtained which has to be transformed to a single crisp number that is a form which can be used in practice. In the CAF approach, the process of output in fuzzy inference is actually a defuzzifier process. Generally, fuzzy rules can be generated either from heuristics or from experimental data. Fuzzy rules are used with the principle: a node which holds more remaining power and lower traffic numbers has a higher probability. The greater the probability of nodes as well as the lower the node hops is, the easier the node will be selected to be the next hop in the optimal path.Table 1
If-then rules.
Number
Antecedent
Consequent
RP(n)
TN(n)
Probability(n)
1
VL
VL
S
2
VL
L
VS
3
VL
M
VS
4
VL
H
VS
5
VL
VH
VS
6
L
VL
M
7
L
L
M
8
L
M
S
9
L
H
S
10
L
VH
VS
11
M
VL
G
12
M
L
M
13
M
M
M
14
M
H
S
15
M
VH
S
16
H
VL
VG
17
H
L
G
18
H
M
G
19
H
H
M
20
H
VH
M
21
VH
VL
VG
22
VH
L
VG
23
VH
M
VG
24
VH
H
G
25
VH
VH
GThe defuzzification method adopted in this paper is the most commonly used formula of gravity calculation. The value of the probability obtained using the gravity method of the defuzzifier could be represented as(8)pro_value=∑k=1nUk·ck∑k=1nUk,
where Uk is the output of the rule base k and ck is the center of the output membership functions. The flowchart of the AF algorithm is shown in Figure 9.Figure 9
Flowchart of the AF algorithm, where distance(i,j) is the distance between the node i and one of its neighboring nodes j. RP(i,j) and TN(i,j) are the remaining energy and traffic load of the neighboring node j of node i, respectively. Pro(i,j) is the node cost of the neighboring node j of node i.


### 4.3. Implementation of A-Star Algorithm

A-star algorithm which is used to find the optimal route from the CHs to the base station is applied to each CH and builds a multihop transmission path among CHs using a weight functionf(i). Evaluation function f(i) can be obtained via
(9)f(i)=w·(cos⁡t(i)max_cos⁡⁡t(i))+(1-w)·(Dmax⁡-h(i)Dmax⁡),
where cos⁡t(i)=w·(Nc(i)/max_cos⁡⁡t(i))+(1-w)·((Dmax⁡-g(i))/Dmax⁡) and cos⁡t(i) is cost of the CH node of the i. The value of Nc(i) is obtained by the fuzzy inference algorithm which considers the residual energy, the minimum number of hops, and the traffic numbers of each node. Its range is [0,1]. The maximum cost of the node i is max_cos⁡⁡t(i).D
max
⁡ is the maximum distance from the base station in the network. The actual cost from the initial node (start node) to the next node i is g(i). The estimated cost of the optimal path from node i to the target node (destination node) is h(i), which depends on the heuristic information of the problem area [44]. In the above formula, w is a constant, 0<w<1, which is used to balance the energy cost of the node and distance parameters. Clearly, the node with a larger cost will be closer to the base station.


### 4.4. Implementation of CAF Algorithm

CAF algorithm is divided into two steps. Firstly, apply the Stable Election Protocol (SEP) algorithm to the wireless sensor network in order to cluster. The nodes are divided into advanced nodes and normal nodes. The advanced node’s energy is two times the normal node. It is proposed to let the candidate nodes run for the CH based on the residual energy within a certain range, to make the even distribution of the CH. Secondly, among the CH nodes, the combined algorithms of the fuzzy inference and A-star method are used, taking into account the residual energy, minimum hops count, and traffic loads of each CH and looking for the best path from the source node to the destination node. Figures10 and 11 present the results using the CAF routing method to find the optimal route. The pseudocode of the proposed CAF routing method is described as Algorithm 1.Algorithm 1:Proposed CAF method.
Input:
N: a network
p: optimal election probability of a node to become a
CH
n: number of nodes in the field
m: percentage of nodes that are advanced
a: multiple of the advanced node is α times greater
than the normal node
r: the number of rounds
output:
NA(r): the number of alive nodes in each round
RP(r): the remaining power of each node in
each round
R_FND: the round of first node are dead
R_HNA: the round in which half of the nodes are alive
Function:
FuzzyLogic(Remain_Power, Traffic_Number);
Insert_Open(xval, yval, parent_xval, parent_yval,
hn, cost, xn)
Expand_Array(node_x, node_y, hn, xTarget,
yTarget, (LOSED, MAX_X, MAX_Y, exp_neibor)
Max_Fn(OPEN, OPEN_COUNT,xTarget, yTarget)
Seek_Node_Id(C, xval,yval)
Node_Index(OPEN,xval, yval)
Arrow(Pstart, Pend);
Initialization:
(1)r←0;
(2)K←n*p;
(3)  RP←(S(C(i)·id)·E)*10;
(4)  TN← rand(1) * 10;
(5)  Pro(i) ← FuzzyLogic(RP, TN);
(6)W_cost2dis ← 0.7
Main:
(7)  Fori=1 : 1 : n
(8)   If (temp_rnd >=m*n+1)
(9)S(i).type ←Nnor;
(10)  elseS(i).type ←Nadv;
(11)   end if
(12) end for
(13)/* for every clustering round */
(14) Fori=1 : 1 : n
(15)  if((S(i).type==Nnor && (temp_rand <= (pnrm/
(1 –pnrm * mod(r, round(1/pnrm)))))))
(16)S(i).type ←Nch; //Election CHs from normal nodes
(17)  end if
(18)  if((S(i).type == Nadv && (temp_rand <= (padv/
(1-padv*mod(r, round(1/padv)))))))
(19)S(i).type ←Ach; //Election CHs from advanced nodes
(20)  end if
(21) end for
(22) Voronoi(X,Y);
(23)[v, c]← voronoin([X;Y]′);
(24) Fork=1 : 1 : cluster -1
(25)/*Find the optimal route using the A-star method*/
(26)  MH(i)← sqrt((S(C(i)·id)·xd-(S(n+1)·xd))∧2+(S(C(i)·id))·yd
-(S(n+1).yd))∧2);
(27)  NC(i) ←W_cost2dis*(Pro(i)/Max_cost) + (1 − W_cost2dis)
* ((Max_distance-MH(i))/Max_distance);
(28)C(i).ver ←[v(c{i}, 1), v(c{i}, 2)];
(29)  if the polygoni and j have two same vertexes or more
(30)C(i).neighbor(nNei) ←j; // Find the neighbor of each CH
(31)   end if
(32)  while((xNode ~= xTarget ||y Node ~= yTarget) &&
NoPath == 1)
(33)   if nodei is in Exp_Array table and not in OPEN table
(34)     OPEN(OPEN_COUNT,:)← Insert_Open(
Exp_Array(i, 1), Exp_Array(i, 2), xNode,
yNode, Exp_Array(i, 3), Exp_Array(i, 4), Exp_Array(i, 5));
(35)   end if
(36)   index_max_node← Max_Fn(OPEN, OPEN_COUNT,
xTarget, yTarget);
(37)   if (index_max_node ~= −1)
(38)     CLOSED(CLOSED_COUNT,1)←xNode;
(39)     CLOSED(CLOSED_COUNT,2)←yNode;
(40)   else NoPath← 0;
(41)   end if
(42)  end while
(43)  while(parent_x ~= xStart || parent_y ~= yStart)
(44)   parent_x← OPEN(Node_Index(OPEN, xval, yval),4);
(45)   parent_y← OPEN(node_index(OPEN, xval, yval),5);
(46)inode ← node_index(OPEN, parent_x,parent_y);
(47)pStart ←[parent_x, parent_y];
(48)pEnd ←[xval, yval];
(49)   Arrow(pStart,pEnd);
(50)  end while
(51) end forFigure 10
The CAF routing method result with all nodes being alive.Figure 11
The CAF routing method result with some nodes being dead.


## 4.1. Implementation of the SEP Method

As with LEACH, SEP in each round consists of two phases: set-up phase and stability phase.


### 4.1.1. Set-Up Phase

The set-up phase is essentially the preparation stage of data transmission. This stage is primarily for the transmission of the control information, the formation of the clusters, and the random generation of the CHs. This stage, without data transmission, but with a series of preparatory work prior to data transmission, fully prepares for the data transfer.This paper optimizes the CH selection algorithm and aims to let the nodes with more energy rather than less energy become the first cluster head in the clusters, thus avoiding the lesser energy node’s premature death because of the fast energy consumption while being elected as the CH and subsequently affecting the network lifetime. Therefore, the energy factor can be added during the process of the choosing CHs which ensures that the node with more residual energy can be elected to be the CH and all nodes run out of energy almost at the same time.The critical aspect of the cluster set-up phase is to set the threshold asT(n). The selection of the CH in the SEP method is carried out from the advanced node and the normal node. The ratio of the advanced node in the total number of nodes is m. Set the total nodes as n. The energy of the advanced node is α times larger than the normal node.SEP provides constraints and limits for balancing energy consumption in order to extend the lifetime of the steady state. The advanced node is more likely to become a CH node than a normal node, which is fairly a constraint for the energy consumption. If the energy of each node is initialized toE0, the energy of each advanced nodes is E0·(1+α). The total energy of the initial nodes in the network is n·(1-m)·E0+n·m·E0·(1+α)=n·E0·(1+α·m).Total energy of the SEP is(1+α·m) times larger than the total energy of the LEACH.Let the weighted selection probabilities of the normal node bepnrm and let the weighted selection probabilities of the advanced node be padv. They are defined as
(4)pnrm=popt1+α·m,padv=popt1+α·m×(1+α),
where the ratio of the advanced node in the total number of nodes is m and the energy of the advanced node is α times larger than the normal node.T
(
s
nrm
), the threshold of the normal node, is the average probability of the normal node which has not yet become the CH in the r round to be the CH. T(sadv), the threshold of advanced node, is the average probability of the advanced node which has not yet become the CH in the r round to be the CH. They could be obtained by (5) and (6). Consider
(5)T(snrm)={pnrm1-pnrm·(rmod⁡(1/pnrm))iifsnrm∈G′0otherwise,
where r is the current round and G′ is the set of normal nodes that have not been CHs within the last 1/pnrm round at each step. T(snrm) is to ensure that each normal node can have the opportunity to become the CH node in the (1/popt)·(1+α·m) round at each step
(6)T(sadv)={padv1-padv·(rmod⁡(1/padv))ifsadv∈G′′0otherwise,
where r is the current round and G′′ is the set of advanced nodes that have not been CHs in the last 1/padv round at each step. T(sadv) is to ensure that each advanced node can have the opportunity to become the CH in the (1/popt)·(1+α·m)/(1+α) round at each step.Figures3 and 4 have shown the different situation of the cluster figures using the CAF algorithm. In these two figures, the Voronoi diagram was used to cluster the nodes in WSN. Consider a set of coplanar points P. For each point Px in the set P, you can draw a boundary enclosing all the intermediate points lying closer to Px than to other points in the set P. Such a boundary is called a Voronoi polygon, and the set of all Voronoi polygons for a given point set is called a Voronoi diagram which is composed of many Voronoi cells. Each cell has a CH.Figure 3
A clustering wireless sensor network with all nodes being alive.Figure 4
A clustering wireless sensor network with some nodes being dead.In these two figures, “∘” is a normal node, “*” is a CH, “+” is an advanced node, and “∙” is a dead node. If the nodes are alive, the nodes which are in the same Voronoi cell will report messages to the CH of this cell.


### 4.1.2. Stability Phase

The stability phase is the cluster communication phase. In the LEACH protocol, between the node in the cluster and the CH and between the CH and the base station both use direct single hop communication. The node in the cluster is close to the CH, so the easy direct communication can be used. However, the CH node is often far from the base station, and the transport energy consumption increases exponentially as the distance increases. Therefore, direct communication will consume a relatively large amount of energy of the CH. To solve this issue, the CAF protocol in this paper uses multihop communication to transmit data from the CH to the base station, which creates a multihop path tree using A-star method and fuzzy approach. Only the root node of the path or the independent node which has no parent node needs a long distance communication with the base station, while other CHs only need close communication within the sensing area.After a period of the stability of the data transmission phase, the network reenters the set-up phase of the cluster and goes to the next cycle of the cluster of refactoring. The flowchart of the SEP method is shown in Figure5.Figure 5
Flowchart of the SEP method.


## 4.1.1. Set-Up Phase

The set-up phase is essentially the preparation stage of data transmission. This stage is primarily for the transmission of the control information, the formation of the clusters, and the random generation of the CHs. This stage, without data transmission, but with a series of preparatory work prior to data transmission, fully prepares for the data transfer.This paper optimizes the CH selection algorithm and aims to let the nodes with more energy rather than less energy become the first cluster head in the clusters, thus avoiding the lesser energy node’s premature death because of the fast energy consumption while being elected as the CH and subsequently affecting the network lifetime. Therefore, the energy factor can be added during the process of the choosing CHs which ensures that the node with more residual energy can be elected to be the CH and all nodes run out of energy almost at the same time.The critical aspect of the cluster set-up phase is to set the threshold asT(n). The selection of the CH in the SEP method is carried out from the advanced node and the normal node. The ratio of the advanced node in the total number of nodes is m. Set the total nodes as n. The energy of the advanced node is α times larger than the normal node.SEP provides constraints and limits for balancing energy consumption in order to extend the lifetime of the steady state. The advanced node is more likely to become a CH node than a normal node, which is fairly a constraint for the energy consumption. If the energy of each node is initialized toE0, the energy of each advanced nodes is E0·(1+α). The total energy of the initial nodes in the network is n·(1-m)·E0+n·m·E0·(1+α)=n·E0·(1+α·m).Total energy of the SEP is(1+α·m) times larger than the total energy of the LEACH.Let the weighted selection probabilities of the normal node bepnrm and let the weighted selection probabilities of the advanced node be padv. They are defined as
(4)pnrm=popt1+α·m,padv=popt1+α·m×(1+α),
where the ratio of the advanced node in the total number of nodes is m and the energy of the advanced node is α times larger than the normal node.T
(
s
nrm
), the threshold of the normal node, is the average probability of the normal node which has not yet become the CH in the r round to be the CH. T(sadv), the threshold of advanced node, is the average probability of the advanced node which has not yet become the CH in the r round to be the CH. They could be obtained by (5) and (6). Consider
(5)T(snrm)={pnrm1-pnrm·(rmod⁡(1/pnrm))iifsnrm∈G′0otherwise,
where r is the current round and G′ is the set of normal nodes that have not been CHs within the last 1/pnrm round at each step. T(snrm) is to ensure that each normal node can have the opportunity to become the CH node in the (1/popt)·(1+α·m) round at each step
(6)T(sadv)={padv1-padv·(rmod⁡(1/padv))ifsadv∈G′′0otherwise,
where r is the current round and G′′ is the set of advanced nodes that have not been CHs in the last 1/padv round at each step. T(sadv) is to ensure that each advanced node can have the opportunity to become the CH in the (1/popt)·(1+α·m)/(1+α) round at each step.Figures3 and 4 have shown the different situation of the cluster figures using the CAF algorithm. In these two figures, the Voronoi diagram was used to cluster the nodes in WSN. Consider a set of coplanar points P. For each point Px in the set P, you can draw a boundary enclosing all the intermediate points lying closer to Px than to other points in the set P. Such a boundary is called a Voronoi polygon, and the set of all Voronoi polygons for a given point set is called a Voronoi diagram which is composed of many Voronoi cells. Each cell has a CH.Figure 3
A clustering wireless sensor network with all nodes being alive.Figure 4
A clustering wireless sensor network with some nodes being dead.In these two figures, “∘” is a normal node, “*” is a CH, “+” is an advanced node, and “∙” is a dead node. If the nodes are alive, the nodes which are in the same Voronoi cell will report messages to the CH of this cell.


## 4.1.2. Stability Phase

The stability phase is the cluster communication phase. In the LEACH protocol, between the node in the cluster and the CH and between the CH and the base station both use direct single hop communication. The node in the cluster is close to the CH, so the easy direct communication can be used. However, the CH node is often far from the base station, and the transport energy consumption increases exponentially as the distance increases. Therefore, direct communication will consume a relatively large amount of energy of the CH. To solve this issue, the CAF protocol in this paper uses multihop communication to transmit data from the CH to the base station, which creates a multihop path tree using A-star method and fuzzy approach. Only the root node of the path or the independent node which has no parent node needs a long distance communication with the base station, while other CHs only need close communication within the sensing area.After a period of the stability of the data transmission phase, the network reenters the set-up phase of the cluster and goes to the next cycle of the cluster of refactoring. The flowchart of the SEP method is shown in Figure5.Figure 5
Flowchart of the SEP method.


## 4.2. Implementation of Fuzzy Approach

Find the best node by integrating several factors in the problem, such as residual energy, traffic numbers, and minimum number of hops. This is equivalent to finding the optimal path from the start node to the sink node. For the fuzzy method, the fuzzy value is processed by FIS, which includes a rule base and various ways to infer these rules. There are a series of if-then rules in rule base, and fuzzy sets are combined with the input and output fuzzy language variables which are described by the fuzzy implication operator to construct the FIS jointly.To handle uncertainties, this paper has used the FIS for the probability computation of each node as shown in Figure6. The two input variables for the FIS are the residual energy and the traffic numbers, and the single output parameter is the probability of a node to be selected as the best node in the optimal path. The greater the probability value will mean that the node has more chance to be a best node. The value range of RE is [0,10], the value range of TN is [0,10], and the probability is [0,1]. According to the current simulation environment, the fields of fuzzy variables are selected for inputs as well as outputs. When the environment changes, the value ranges can be modified as well.Figure 6
Fuzzy structure with two inputs and one output.The values of the residual energy for fuzzy input variables are very low (VL), low (L), medium (M), high (H), and very high (VH). The values of the traffic number for fuzzy input variables are very low (VL), low (L), medium (M), high (H), and very high (VH). The values of the node probability for fuzzy output variables are very small (VS), small (S), medium (M), large (G), and very large (VG). Membership function (MF) is a curve, and it defines how each point of the input space is mapped to a membership between 0 and 1. This paper selects the Gaussian membership function as the membership function for input and output variables. Equation (7) shows the Gaussian membership function as follows:
(7)u(x;σ,c)=exp⁡(-[(x-c)σ]2),
where c and σ are the center and standard deviation of membership function, respectively.The membership functions of the input-output fuzzy variables and surface viewer of the FIS are given in Figures7 and 8, respectively. Nodes with small probability would not be selected as the next hop.Figure 7
Membership functions of the input-output fuzzy variables.Figure 8
Surface viewer of the FIS with two inputs and one output.The probability calculation is accomplished using predefined fuzzy if-then mapping rules to handle the uncertainty. Based on the two fuzzy input variables, 25 fuzzy mapping rules are defined in Table1. From the fuzzy rules, the fuzzy variable probability can be obtained which has to be transformed to a single crisp number that is a form which can be used in practice. In the CAF approach, the process of output in fuzzy inference is actually a defuzzifier process. Generally, fuzzy rules can be generated either from heuristics or from experimental data. Fuzzy rules are used with the principle: a node which holds more remaining power and lower traffic numbers has a higher probability. The greater the probability of nodes as well as the lower the node hops is, the easier the node will be selected to be the next hop in the optimal path.Table 1
If-then rules.
Number
Antecedent
Consequent
RP(n)
TN(n)
Probability(n)
1
VL
VL
S
2
VL
L
VS
3
VL
M
VS
4
VL
H
VS
5
VL
VH
VS
6
L
VL
M
7
L
L
M
8
L
M
S
9
L
H
S
10
L
VH
VS
11
M
VL
G
12
M
L
M
13
M
M
M
14
M
H
S
15
M
VH
S
16
H
VL
VG
17
H
L
G
18
H
M
G
19
H
H
M
20
H
VH
M
21
VH
VL
VG
22
VH
L
VG
23
VH
M
VG
24
VH
H
G
25
VH
VH
GThe defuzzification method adopted in this paper is the most commonly used formula of gravity calculation. The value of the probability obtained using the gravity method of the defuzzifier could be represented as(8)pro_value=∑k=1nUk·ck∑k=1nUk,
where Uk is the output of the rule base k and ck is the center of the output membership functions. The flowchart of the AF algorithm is shown in Figure 9.Figure 9
Flowchart of the AF algorithm, where distance(i,j) is the distance between the node i and one of its neighboring nodes j. RP(i,j) and TN(i,j) are the remaining energy and traffic load of the neighboring node j of node i, respectively. Pro(i,j) is the node cost of the neighboring node j of node i.


## 4.3. Implementation of A-Star Algorithm

A-star algorithm which is used to find the optimal route from the CHs to the base station is applied to each CH and builds a multihop transmission path among CHs using a weight functionf(i). Evaluation function f(i) can be obtained via
(9)f(i)=w·(cos⁡t(i)max_cos⁡⁡t(i))+(1-w)·(Dmax⁡-h(i)Dmax⁡),
where cos⁡t(i)=w·(Nc(i)/max_cos⁡⁡t(i))+(1-w)·((Dmax⁡-g(i))/Dmax⁡) and cos⁡t(i) is cost of the CH node of the i. The value of Nc(i) is obtained by the fuzzy inference algorithm which considers the residual energy, the minimum number of hops, and the traffic numbers of each node. Its range is [0,1]. The maximum cost of the node i is max_cos⁡⁡t(i).D
max
⁡ is the maximum distance from the base station in the network. The actual cost from the initial node (start node) to the next node i is g(i). The estimated cost of the optimal path from node i to the target node (destination node) is h(i), which depends on the heuristic information of the problem area [44]. In the above formula, w is a constant, 0<w<1, which is used to balance the energy cost of the node and distance parameters. Clearly, the node with a larger cost will be closer to the base station.


## 4.4. Implementation of CAF Algorithm

CAF algorithm is divided into two steps. Firstly, apply the Stable Election Protocol (SEP) algorithm to the wireless sensor network in order to cluster. The nodes are divided into advanced nodes and normal nodes. The advanced node’s energy is two times the normal node. It is proposed to let the candidate nodes run for the CH based on the residual energy within a certain range, to make the even distribution of the CH. Secondly, among the CH nodes, the combined algorithms of the fuzzy inference and A-star method are used, taking into account the residual energy, minimum hops count, and traffic loads of each CH and looking for the best path from the source node to the destination node. Figures10 and 11 present the results using the CAF routing method to find the optimal route. The pseudocode of the proposed CAF routing method is described as Algorithm 1.Algorithm 1:Proposed CAF method.
Input:
N: a network
p: optimal election probability of a node to become a
CH
n: number of nodes in the field
m: percentage of nodes that are advanced
a: multiple of the advanced node is α times greater
than the normal node
r: the number of rounds
output:
NA(r): the number of alive nodes in each round
RP(r): the remaining power of each node in
each round
R_FND: the round of first node are dead
R_HNA: the round in which half of the nodes are alive
Function:
FuzzyLogic(Remain_Power, Traffic_Number);
Insert_Open(xval, yval, parent_xval, parent_yval,
hn, cost, xn)
Expand_Array(node_x, node_y, hn, xTarget,
yTarget, (LOSED, MAX_X, MAX_Y, exp_neibor)
Max_Fn(OPEN, OPEN_COUNT,xTarget, yTarget)
Seek_Node_Id(C, xval,yval)
Node_Index(OPEN,xval, yval)
Arrow(Pstart, Pend);
Initialization:
(1)r←0;
(2)K←n*p;
(3)  RP←(S(C(i)·id)·E)*10;
(4)  TN← rand(1) * 10;
(5)  Pro(i) ← FuzzyLogic(RP, TN);
(6)W_cost2dis ← 0.7
Main:
(7)  Fori=1 : 1 : n
(8)   If (temp_rnd >=m*n+1)
(9)S(i).type ←Nnor;
(10)  elseS(i).type ←Nadv;
(11)   end if
(12) end for
(13)/* for every clustering round */
(14) Fori=1 : 1 : n
(15)  if((S(i).type==Nnor && (temp_rand <= (pnrm/
(1 –pnrm * mod(r, round(1/pnrm)))))))
(16)S(i).type ←Nch; //Election CHs from normal nodes
(17)  end if
(18)  if((S(i).type == Nadv && (temp_rand <= (padv/
(1-padv*mod(r, round(1/padv)))))))
(19)S(i).type ←Ach; //Election CHs from advanced nodes
(20)  end if
(21) end for
(22) Voronoi(X,Y);
(23)[v, c]← voronoin([X;Y]′);
(24) Fork=1 : 1 : cluster -1
(25)/*Find the optimal route using the A-star method*/
(26)  MH(i)← sqrt((S(C(i)·id)·xd-(S(n+1)·xd))∧2+(S(C(i)·id))·yd
-(S(n+1).yd))∧2);
(27)  NC(i) ←W_cost2dis*(Pro(i)/Max_cost) + (1 − W_cost2dis)
* ((Max_distance-MH(i))/Max_distance);
(28)C(i).ver ←[v(c{i}, 1), v(c{i}, 2)];
(29)  if the polygoni and j have two same vertexes or more
(30)C(i).neighbor(nNei) ←j; // Find the neighbor of each CH
(31)   end if
(32)  while((xNode ~= xTarget ||y Node ~= yTarget) &&
NoPath == 1)
(33)   if nodei is in Exp_Array table and not in OPEN table
(34)     OPEN(OPEN_COUNT,:)← Insert_Open(
Exp_Array(i, 1), Exp_Array(i, 2), xNode,
yNode, Exp_Array(i, 3), Exp_Array(i, 4), Exp_Array(i, 5));
(35)   end if
(36)   index_max_node← Max_Fn(OPEN, OPEN_COUNT,
xTarget, yTarget);
(37)   if (index_max_node ~= −1)
(38)     CLOSED(CLOSED_COUNT,1)←xNode;
(39)     CLOSED(CLOSED_COUNT,2)←yNode;
(40)   else NoPath← 0;
(41)   end if
(42)  end while
(43)  while(parent_x ~= xStart || parent_y ~= yStart)
(44)   parent_x← OPEN(Node_Index(OPEN, xval, yval),4);
(45)   parent_y← OPEN(node_index(OPEN, xval, yval),5);
(46)inode ← node_index(OPEN, parent_x,parent_y);
(47)pStart ←[parent_x, parent_y];
(48)pEnd ←[xval, yval];
(49)   Arrow(pStart,pEnd);
(50)  end while
(51) end forFigure 10
The CAF routing method result with all nodes being alive.Figure 11
The CAF routing method result with some nodes being dead.


## 5. Performance Evaluations

The simulation environment, parameters, and metrics are presented in this section, followed by the simulation results. This paper adopts the combined methods of the SEP method, the A-star algorithm, and the fuzzy approach, and experimental simulation results are given to evaluate the merits of the algorithm. This paper selects the SEP, AF, and A-star algorithms as a comparison of the CAF method. Simulation results show that the CAF algorithm performs better than others.


### 5.1. Simulation Environment

Construct a simulation environment of the algorithm test using the Matlab2010a. In order to verify the adaptive capacity of the CAF algorithm under different network topologies, this paper sets two topological regions, A and B. The region size of A is100m×100m, while the region size of B is 200m×50m. According to the actual situation, coordinates of the base station are fixed and are far from the sensor nodes in the network, so this paper sets the base station coordinates as follows: A is (50,300) and B is (100,150). In the two different topological regions, A and B, 100 nodes are placed randomly as a test network.For nonclustering routing algorithms, such as AF and A-star, each node has the same initial energy of 0.55 J. For clustering routing algorithms, such as SEP and CAF, the initial energy of the advanced node is 1 J, and normal node’s initial energy is 0.5 J. The size of the message that nodes send to their CHs as well as the size of the (aggregate) message that a CH send to the sink is 2000 bits. The packet size is 2000 bit, and the initial ratio of CH is 0.1.Simulations are done using the values 50 nJ/bit and 100 pJ/bit/m2 for Eelec and Eamp, respectively. Table 2 presents the systems parameters in detail.Table 2
Simulation parameters.
Parameter
Value
Topographical area (meter)
A
100 m × 100 m
B
200 m × 50 m
Sink location
A
(50, 300)
B
(100, 150)
Initial energy of node
AF, A-star
0.55 J
SEP, CF, CA, CAF
Normal nodes
0.5 J
Advanced nodes
1 J
Radio model
EDA
5 nJ/bit
EelecTx or EelecRx
50 nJ/bit
εfs
10 pJ/bit/m2
εmp
0.0013 pJ/bit/m4
Number of nodes
100
Limit of transmission distance (meters)
30 m
Packet data size
2 k bit
P
opt
0.1
m
0.1
α
1


### 5.2. Energy Model

Once the node is placed, it is no longer moved and the node died when the energy is zero. The experiment utilized a first-order radio model [45] which is commonly used in the WSNs. The radio energy consumption model is shown in Figure 12.Figure 12
Radio energy dissipation model.The energy consumed by the sensor nodes in this paper is divided into two categories. First is the energy consumed by the normal or advanced node (non-CH and nonparent node). According to Figure12, when the distance is d and transmit L-bit message, the energy required by common sensor nodes while transmitting electronics can be defined as
(10)ENTx(L,d)={L·Eelec+L·εfs·d2ifd≤d0L·Eelec+L·εmp·d4ifd>d0,
where L is the packet size of transmitted data, d is the distance between the sender and the receiver, Eelec is power circuits for sending or receiving, determined by the digital coding, modulation, filtering, and spread signal and other factors, and d0 is the distance threshold. When the transmission distance is less than the threshold, the free space channel model is used. On the contrary, when the transmission distance is more than the threshold, the multipath fading channel model is used [46]. Amplifier power εfs and εmp is determined by transmission distance and the accepting error rate. When d=d0, let d0=εfs/εmp.The received electronics energy consumption when the normal node receives theL-bit message is shown as
(11)ENRx=L·Eelec.The next is the energy consumed by the CH or parent node (PN). As a CH or PN, except that the sending and receiving messages consume energy, the data processing also consumes the energy. The energy consumed by the CH or PN while transferringL-bit data can be obtained via
(12)ECHPTx(L,d)={L·Eelec+L·EDA+L·εfsd2ifd≤d0L·Eelec+L·EDA+L·εmpd4ifd>d0,
where EDA 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 they receive L-bit message can be defined as
(13)ECHPRx=L·(Eelec+EDA).The values used in the first-order radio model are described in Table2.


### 5.3. Simulation Results

Handy et al. [47] proposed the metric first node dies (FND) and half of the nodes alive (HNA). FND metric is useful in these scenarios where it is necessary that all nodes stay alive as long as possible, since network quality decreases considerably as soon as one node dies, such as intrusion or fire detection. In these cases, it is important to know when the first node dies. 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 loss of a single or few nodes does not automatically diminish the quality of service of the network. Hence, HNA metric is useful in densely deployed sensor networks.The rounds of FND and HNA are simulated using A-star, AF, CF, CA, SEP, and CAF, the six different approaches, for both areas A and B. The results are shown in Figures13 and 14, respectively. Clearly, the CAF method outperforms the A-star, AF, CF, CA, and SEP algorithms in both areas, A and B. In Figure 13, the FND improvements 3240%, 1216%, 121%, 30%, and 104% are accomplished by comparing the algorithms of A-star, AF, CF, CA, and SEP, respectively. HNA improves by 282%, 270%, 51%, 39%, and 57%, while, in Figure 14, the FND improvements 3660%, 766%, 151%, 37%, and 42% are accomplished by comparing the algorithms of A-star, AF, CF, CA, and SEP, respectively. HNA improves by 275%, 264%, 41%, 43%, and 33%. It can be seen that the times for the FND and HNA in the proposed method are much longer than the times for the FND and HNA for all the three methods in both areas A and B.Figure 13
Simulation results of FND and HNA in sample network in Area A.Figure 14
Simulation results of FND and HNA in sample network in Area B.Moreover, Figures15 and 16 show the simulation results for this configuration. It can be seen that the number of nodes alive in the proposed method is always higher than that of all A-star, AF, CF, CA, and SEP algorithms. The two figures can also show that the performance of the SEP and CF algorithm is obviously affected by the topographic regions. The SEP and CF algorithm performance varies greatly in different topographic regions. In Figure 15 with the position of the sink node (50,300), the survival rate of nodes for SEP and CF algorithm is lower than those in Figure 16 with the position of the sink node (200,50), while the CAF algorithm this paper proposed has achieved good performance both in areas A and B. The CAF algorithm has a strong adaptive capacity under different network topologies.Figure 15
Distribution of the nodes being alive according to the number of rounds in Area A.Figure 16
Distribution of the nodes being alive according to the number of rounds in Area B.Figures17 and 18 show the total remaining energy of a WSN with the round number increasing for the six approaches in areas, A and B, respectively. This validates that the proposed CAF method actually consumes less energy than the A-star, AF, CF, CA, and SEP algorithms. A better energy balance in a WSN is achieved by the proposed method in both areas A and B. The simulation results indicate that the proposed CAF is superior to the other mechanisms in terms of FND, HNA, residual total energy, and the number of sensor nodes alive with different topographical areas.Figure 17
Distribution of the total remaining energy according to the number of rounds in Area A.Figure 18
Distribution of the total remaining energy according to the number of rounds in Area B.From the aforementioned simulation results, it is clear that the proposed CAF method outperforms the AF algorithm, CF approach, CA algorithm, SEP method, and A-star approach in terms of balancing energy consumption and maximization of network lifetime. This is because the CAF algorithm selects a CH first. The CH is selected randomly from the advanced nodes as well as normal nodes and it always selects the node with the highest residual energy as a CH. The sensor nodes are clustered in the zone using the Voronoi cell and the member nodes send messages directly to the CH instead of the base station, which reduces the message communication distance of the member nodes greatly. Meantime, the AF routing algorithm is used to find the optimal path among the CHs. The multiple factors including the residual energy, traffic load, and minimum hop are taken into consideration to propose a metric of finding the next hop in the optimal path. In this way, the energy cost of CHs can be controlled in minimum in message communication. The CAF algorithm guarantees that the discovered routing path can remain consistent.


## 5.1. Simulation Environment

Construct a simulation environment of the algorithm test using the Matlab2010a. In order to verify the adaptive capacity of the CAF algorithm under different network topologies, this paper sets two topological regions, A and B. The region size of A is100m×100m, while the region size of B is 200m×50m. According to the actual situation, coordinates of the base station are fixed and are far from the sensor nodes in the network, so this paper sets the base station coordinates as follows: A is (50,300) and B is (100,150). In the two different topological regions, A and B, 100 nodes are placed randomly as a test network.For nonclustering routing algorithms, such as AF and A-star, each node has the same initial energy of 0.55 J. For clustering routing algorithms, such as SEP and CAF, the initial energy of the advanced node is 1 J, and normal node’s initial energy is 0.5 J. The size of the message that nodes send to their CHs as well as the size of the (aggregate) message that a CH send to the sink is 2000 bits. The packet size is 2000 bit, and the initial ratio of CH is 0.1.Simulations are done using the values 50 nJ/bit and 100 pJ/bit/m2 for Eelec and Eamp, respectively. Table 2 presents the systems parameters in detail.Table 2
Simulation parameters.
Parameter
Value
Topographical area (meter)
A
100 m × 100 m
B
200 m × 50 m
Sink location
A
(50, 300)
B
(100, 150)
Initial energy of node
AF, A-star
0.55 J
SEP, CF, CA, CAF
Normal nodes
0.5 J
Advanced nodes
1 J
Radio model
EDA
5 nJ/bit
EelecTx or EelecRx
50 nJ/bit
εfs
10 pJ/bit/m2
εmp
0.0013 pJ/bit/m4
Number of nodes
100
Limit of transmission distance (meters)
30 m
Packet data size
2 k bit
P
opt
0.1
m
0.1
α
1


## 5.2. Energy Model

Once the node is placed, it is no longer moved and the node died when the energy is zero. The experiment utilized a first-order radio model [45] which is commonly used in the WSNs. The radio energy consumption model is shown in Figure 12.Figure 12
Radio energy dissipation model.The energy consumed by the sensor nodes in this paper is divided into two categories. First is the energy consumed by the normal or advanced node (non-CH and nonparent node). According to Figure12, when the distance is d and transmit L-bit message, the energy required by common sensor nodes while transmitting electronics can be defined as
(10)ENTx(L,d)={L·Eelec+L·εfs·d2ifd≤d0L·Eelec+L·εmp·d4ifd>d0,
where L is the packet size of transmitted data, d is the distance between the sender and the receiver, Eelec is power circuits for sending or receiving, determined by the digital coding, modulation, filtering, and spread signal and other factors, and d0 is the distance threshold. When the transmission distance is less than the threshold, the free space channel model is used. On the contrary, when the transmission distance is more than the threshold, the multipath fading channel model is used [46]. Amplifier power εfs and εmp is determined by transmission distance and the accepting error rate. When d=d0, let d0=εfs/εmp.The received electronics energy consumption when the normal node receives theL-bit message is shown as
(11)ENRx=L·Eelec.The next is the energy consumed by the CH or parent node (PN). As a CH or PN, except that the sending and receiving messages consume energy, the data processing also consumes the energy. The energy consumed by the CH or PN while transferringL-bit data can be obtained via
(12)ECHPTx(L,d)={L·Eelec+L·EDA+L·εfsd2ifd≤d0L·Eelec+L·EDA+L·εmpd4ifd>d0,
where EDA 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 they receive L-bit message can be defined as
(13)ECHPRx=L·(Eelec+EDA).The values used in the first-order radio model are described in Table2.


## 5.3. Simulation Results

Handy et al. [47] proposed the metric first node dies (FND) and half of the nodes alive (HNA). FND metric is useful in these scenarios where it is necessary that all nodes stay alive as long as possible, since network quality decreases considerably as soon as one node dies, such as intrusion or fire detection. In these cases, it is important to know when the first node dies. 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 loss of a single or few nodes does not automatically diminish the quality of service of the network. Hence, HNA metric is useful in densely deployed sensor networks.The rounds of FND and HNA are simulated using A-star, AF, CF, CA, SEP, and CAF, the six different approaches, for both areas A and B. The results are shown in Figures13 and 14, respectively. Clearly, the CAF method outperforms the A-star, AF, CF, CA, and SEP algorithms in both areas, A and B. In Figure 13, the FND improvements 3240%, 1216%, 121%, 30%, and 104% are accomplished by comparing the algorithms of A-star, AF, CF, CA, and SEP, respectively. HNA improves by 282%, 270%, 51%, 39%, and 57%, while, in Figure 14, the FND improvements 3660%, 766%, 151%, 37%, and 42% are accomplished by comparing the algorithms of A-star, AF, CF, CA, and SEP, respectively. HNA improves by 275%, 264%, 41%, 43%, and 33%. It can be seen that the times for the FND and HNA in the proposed method are much longer than the times for the FND and HNA for all the three methods in both areas A and B.Figure 13
Simulation results of FND and HNA in sample network in Area A.Figure 14
Simulation results of FND and HNA in sample network in Area B.Moreover, Figures15 and 16 show the simulation results for this configuration. It can be seen that the number of nodes alive in the proposed method is always higher than that of all A-star, AF, CF, CA, and SEP algorithms. The two figures can also show that the performance of the SEP and CF algorithm is obviously affected by the topographic regions. The SEP and CF algorithm performance varies greatly in different topographic regions. In Figure 15 with the position of the sink node (50,300), the survival rate of nodes for SEP and CF algorithm is lower than those in Figure 16 with the position of the sink node (200,50), while the CAF algorithm this paper proposed has achieved good performance both in areas A and B. The CAF algorithm has a strong adaptive capacity under different network topologies.Figure 15
Distribution of the nodes being alive according to the number of rounds in Area A.Figure 16
Distribution of the nodes being alive according to the number of rounds in Area B.Figures17 and 18 show the total remaining energy of a WSN with the round number increasing for the six approaches in areas, A and B, respectively. This validates that the proposed CAF method actually consumes less energy than the A-star, AF, CF, CA, and SEP algorithms. A better energy balance in a WSN is achieved by the proposed method in both areas A and B. The simulation results indicate that the proposed CAF is superior to the other mechanisms in terms of FND, HNA, residual total energy, and the number of sensor nodes alive with different topographical areas.Figure 17
Distribution of the total remaining energy according to the number of rounds in Area A.Figure 18
Distribution of the total remaining energy according to the number of rounds in Area B.From the aforementioned simulation results, it is clear that the proposed CAF method outperforms the AF algorithm, CF approach, CA algorithm, SEP method, and A-star approach in terms of balancing energy consumption and maximization of network lifetime. This is because the CAF algorithm selects a CH first. The CH is selected randomly from the advanced nodes as well as normal nodes and it always selects the node with the highest residual energy as a CH. The sensor nodes are clustered in the zone using the Voronoi cell and the member nodes send messages directly to the CH instead of the base station, which reduces the message communication distance of the member nodes greatly. Meantime, the AF routing algorithm is used to find the optimal path among the CHs. The multiple factors including the residual energy, traffic load, and minimum hop are taken into consideration to propose a metric of finding the next hop in the optimal path. In this way, the energy cost of CHs can be controlled in minimum in message communication. The CAF algorithm guarantees that the discovered routing path can remain consistent.


## 6. Conclusions

Energy is a major factor for designing WSNs in the real world. Unfortunately, the battery energy is inherently limited. Therefore, efficient utilization of the energy is most important. To improve the energy efficiency, many algorithms are proposed. One of the main characteristics of these algorithms shows that the network lifetime is highly related to the routing selection. This paper has proposed a cluster algorithm and the A-star with fuzzy method, called CAF, providing an energy-efficient routing in WSNs. The main goal of the CAF algorithm is to prolong the lifetime of the WSN by evenly distributing the workload, retaining the remaining energy, and reducing the number of the hops. To achieve this goal, this paper has mostly focused on selecting proper CHs from existent sensor nodes and the optimum next hop from the CHs. The SEP algorithm has been used to choose the best CHs, while the A-star method and fuzzy approach is used to select the proper next hop of the optimal path.Simulation results confirming the CAF method produce the following advantages. Firstly, this algorithm is stable and adaptable to different topologies; secondly, the algorithm has low energy consumption and effectively balances the energy consumption of each sensor node, and the algorithm significantly extends the survival time of the network.In conclusion, the proposed CAF achieves a better FND, HNA, residual total energy, and the number of sensor nodes alive than the original SEP, A-star, CF, CA, and AF techniques with different topographical areas. However, in the real world, there may be certain situations that one or even more of the sensors in the critical pathway becomes intermittent in the ability to function normally. Such behavior may add performance noise (fluctuations) into the WSNs. Ongoing research is investigating the practicality of using the CAF routing protocol for data gathering in WSNs.



---

*Source: 936376-2014-04-28.xml*