A low energy adaptive clustering multi-hop routing protocol based on fuzzy decision
Abstract
In large-scale wireless sensor networks, a low energy consumption requirement in data communication has become more prominent, but the currently existing solutions are unsatisfactory. Based on the complexity and uncertainty in the node energy consumption and communication path in wireless sensor networks, this paper proposes a low energy adaptive clustering multi-hop routing protocol based on fuzzy decision (FD-LEACH). In order to constitute a dynamic network routing structure, the protocol introduces the concept of fuzzy set and uses the theory of fuzzy decision to select excellent communication relay nodes. Analysis and simulation results demonstrate that the proposed protocol is more effectively adapted to large-scale wireless networks, which can provide a better balance in energy consumption and significantly prolong network lifetime.
1Introduction
As the field continues to develop, wireless sensor network technology is being widely used in intrusion detection, weather monitoring, tactical reconnaissance, detecting environmental conditions, etc [8]. Furthermore, a core technology in the field is a wireless sensor network routing protocol, and it is also a hot issue in theoretical research. The existing research focuses on energy saving, security, network QOS, and so on [18], and a series of techniques have been developed, including energy-efficient routing protocols, data aggregation techniques, energy harvesting approaches, and security routing [10, 15, 17]. With the constraint of limited node energy, determining how to prolong the life cycle of the whole network in the routing protocol is the key for designing a routing protocol.
Microelectronics technology has progressed and improved significantly; thus, wireless sensor equipment smaller and more integrated, and it enables the practical application of a greater number of sensor nodes. Therefore, large-scale wireless sensor network routing protocol research has attracted a great attention. Due to an expansion of application scope, most research content [3] is not appropriate to a certain extent. The primary reason is that the number of nodes and the network size in the simulation are too small. At the same time, the scale is larger, which causes a greater energy consumption of the network communication overhead and a greatly reduced network life cycle. As a result, it causes a noticeable decline in the availability of the network.
At present, there is little large-scale WSN routing protocol research. The existing extension of the network scale method can be divided into two categories. One category is the clustering structure, which reduces the energy consumption of communication through path structural optimization so as to complete the energy balance of the whole network and to reach the purpose that the network can still work normally at a large-scale, such as DECROP [7]. The other category is done through GPRS positioning and mobile base stations to collect the entire network information, which avoids the premature death of sensor nodes caused by a large number of communications and prolongs the network life cycle; an example of this category is DGMA [11]. However, these works have a common problem, which is attempting to use a certain algorithm to cope with the uncertainty in the actual work.
In an actual WSN, the energy consumption of the nodes and communication paths is changing. On one hand, as a result of the randomness of clustering and cluster head selection, each node energy consumption changes, which could not be determined in advance. On the other hand, the network is self-organizing, and the communication path is constantly changing. Therefore, by introducing the fuzzy algorithm, we use this kind of soft computing to process the uncertainty and to improve the flexibility and adaptability of the routing protocol. In order to reduce the energy consumption of network communication and to enhance the lifecycle of the entire network, we get a better dynamic selection path through a fuzzy algorithm. In this paper, we put forward a low energy adaptive clustering multi-hop routing protocol based on fuzzy decision (FD-LEACH). The protocol chooses good relay nodes in combination with a fuzzy set and fuzzy decision method and finally builds a routing path as the transmission channel between clusters in order to achieve the purpose of energy balance.
The remainder of the paper is organized as follows. In the next section, we review the related work and research motive. Then, in Section 3, we put forward a low energy adaptive clustering multi-hop routing protocol based on fuzzy decision. In Section 4, we provide experimental simulation and analysis. Finally, Section 5 summarizes the research results and discusses further work.
2Related works
In recent years, there are numerous works about saving energy in wireless sensor networks, which are mainly concentrated in the clustering protocol.Heinzelman et al. [20] proposed LEACH-C, which requires that only energy higher than the average residual energy of the network nodes may become a cluster head. Muhammad, et al. [14] proposed a multiple hops low energy adaptive clustering hierarchy routingalgorithm (MR-LEACH). The motivation of this work is to increase the adaptive clustering hierarchy in order to reduce the energy consumption of sensor nodes. Liu, et al. [1] considered energy as a metric in the setup path phase and introduced two new energy-aware cost functions, which are the Exponential and Sine Cost Function. Li, et al. [6] mainly studied how to optimize the composition of the cluster in order to prolong a network’s life cycle.
Because the range of wireless sensor networks (WSN) has been expanded, there has been a sharp rise in the energy consumption of communication. Now, commonly used measures are dynamic event clustering, multi-hop communication, cooperative communication, and so on [3]. Quang, et al. [19] proposed an Adaptive Routing Protocol with Energy efficiency and Event clustering for wireless sensor networks (ARPEES). Moreover, they introduced an event trigger mechanism in the study and let most nodes be dormant until events have occurred. Huang, et al. proposed a routing protocol named the Dynamic Minimal Spanning Tree Routing Protocol (DMSTRP) in [4]. They used a minimum spanning tree to form clusters in order to obtain a more reasonable node distance and to achieve a goal of reducing energy consumption in the communication. Ge, et al. [21] proposed a novel idea by introducing a cooperative communication from a mobile ad hoc network (MANET) to a WSN for energy reduction. They aimed to find the optimal coalition size to minimize the total transmission cost. Jung, et al. [9] investigated how a cooperative transmission can be used to extend the communication range and thus balance the duty cycling of nodes as normal relay sensors can be replaced by other cooperative nodes. Stefanos, et al. [13] modeled the network as a linear system and, using the Gaussian elimination algorithm, calculated the combinations of nodes that can be chosen as cluster heads in order to extend the network lifetime.
In recent years, soft computing based on an uncertain, imprecise, and incomplete truth value of fault tolerance in order to obtain low cost solutions and robustness has been used in many fields. This kind of method simulates intelligent biochemical processes (people’s perception, brain structure, evolution, immunity, etc.) to effectively deal with daily work. The method related to soft computing has a certain application in wireless sensor networks. Literature [20] used the simulated annealing algorithm to improve the selection of cluster heads. Song, et al. [23] and Ataul, et al. [2] incorporated an ant colony algorithm and genetic algorithm in cluster head election. Azim, et al. [12] utilized the fuzzy inference system (FIS) that optimizes the routing path (depending on the metrics: distance, remaining battery power, and link usage).
As far as we are aware, there is no relevant research of the application of soft computing to a large-scale WSN routing protocol. Therefore, we introduce a fuzzy mathematics method into the routing process to improve the LEACH [22] protocol, which is a single jump model and is not suitable for a large-scale environment. Thus, we put forward a low energy adaptive clustering multi-hop routing protocol based on fuzzy decision (FD-LEACH). The protocol is based on LEACH, adopts the idea of clustering, and utilizes fuzzy sets and fuzzy decision theory in the process of building a cluster routing for path optimization. Reference [12] studied the small-scale network (100 nodes); however, we extend our simulate network to 2500 nodes. Compared to literature [12], we not only adopted the membership function to set the classification of the node, but we also used the fuzzy decision to achieve the aim of selected relay nodes through the evaluation of the current situation.
The main contributions of this paper are as follows:
– We analyze the cause of the existing protocols inability to adapt to the large-scale network and give a method of energy saving improvement.
– We utilize soft computing with fuzzy set and fuzzy decision method of fuzzy mathematics to optimize a routing path choice between clusters in the routing protocol so that the protocol can apply to large-scale networks and improve the energy efficiency and scalability of the protocol.
– We increase the size of WSN in the simulation experiments by using a matlab simulation experiment to make comparisons to LEACH [22], SEP [5], and MR-LEACH [14] in many aspects.
3A low energy adaptive clustering multi-hop routing protocol based on fuzzy decision
3.1Protocol thought
The protocol operation is divided into rounds similar to the LEACH protocol. Each round has a setting up phase and a steady-state phase. In the setting up phase, cluster heads are elected, and clusters are organized. Then, in the stable phase, the cluster heads are responsible for collecting data from the cluster nodes and then transferring data to the base station through a routing path. A detailed protocol process will be presented in the following paragraphs.
3.2Definitions
Definition 1: Radius of Sense
In WSN, the power radius size of a sensor node that can sense the neighbor node with lower power consumption is called the radius of sense (shorthand of Rs). In combination with the first order radio model, we set the Rs = d 0.
Definition 2: Radius of Arrive
In WSN, the receiving node uses a certain amount of power to detect the area of the sending node. When it first arrives at the designated area, the power radius is called the radius of arrive (shorthand of Rarr). We set that the first time arriving at the area covers the longest boundary for d0, namely Rarr = (MaxDist2Sink –Ms+ d0). MaxDist2Sink is the longest distance from a base station to the network area. Ms is the side length of the square network area.
Definition 3: The Node Hierarchy Level
In the process of the wireless sensor network transmitting information, the send Node is called the source node SN (Source Node), and the default of the receiving Node is called the destination node DN (Destination Node).
As shown in Fig. 1, the nodes in the area of the square wireless sensor network are the source nodes, and the five-pointed star sign is the destination node. The level of the nodes, which are the first ones that receive the signal in the network area, is 1. Then, these nodes will send the radio message to the neighbor nodes by jumping with the radius of sense. The level of the nodes that have received the message is the same, and the level of the nodes that have not received the message is the original level plus 1. This operation is repeated until all nodes in the network receive broadcast information. The level of the nodes within the dashed lines in the picture is Level 1, and those within the dot-dash line are in Level 2.
3.3Protocol architecture
3.3.1Establishment stage
– Cluster Head Selection
In the protocol, we use a random selection of the cluster head strategy like the LEACH protocol. In the initialization, each sensor node N has a random number between 0 and 1. If the random number is lower than the threshold T (N), then the node is elected to be the cluster head. The threshold T (N) is calculated by the following equation:
(1)
In Equation (1), p is the expecting probability of the node to become a cluster head in each round: namely, the ratio of the pre-set number of cluster nodes and the total number of all the nodes. Furthermore, r is the current round number, and G is the collection of nodes that have not been a cluster head informer 1/p rounds.
– Clustering
The nodes that are selected as the cluster head nodes broadcast a message to the surrounding nodes. According to the received signal strength, each non-cluster head node chooses the nearest cluster to join. If there are no cluster heads, the node then communicates directly with the base station.
– Routing between clusters
After clustering and cluster head selection, a communication path from each cluster head to the base station is established using fuzzy sets and a fuzzy decision algorithm. The basic idea is:
* All nodes can be divided into three sets with different membership functions in order to measure the membership degree of these nodes.
* The nodes with a membership degree of zero will be directly removed, and we take the intersections of the three sets to reduce the scope of the candidate nodes.
* By using the fuzzy decision theory, we choose the nodes that have the highest number of points in the remaining nodes as the next-hop relay nodes.
The protocol process is given in great detail below.
First, set a is used to describe the relation of the distance between the next-hop node and the source node, and the membership function is:
(2)
Set b is used to describe the next-hop node energy, and the membership function is:
(3)
Set c is used to describe the relation of the distance from the next-hop node to the destination node, and the membership function is:
(4)
where z means the distance between the node and the BS node, which is shown in Fig. 2 nodes with the BS node double arrow dotted lines. Ds max represents the maximum distance from the base station to the sensor area. The greater the membership degree is, the nearer the node is to the base station, which is the bestlocation.
After removing the nodes with a degree of 0 in the above three sets, we obtain the intersection of the three sets and regard the rest of the nodes as the first relay node set of the candidate. Then, we use the fuzzy decision to make the decision through the wave number. The formula is as follows:
(5)
The coefficient of determination is selected artificially and is combined with the experimental results adjustment in order to obtain a better rate. The wave number of each node in the intersection is calculated, and then the largest one is chosen as the relay node. For a convenient calculation for each set, the wave number is not according to the rankings, and we use the membership degree values as a score of each node and then multiply by a certain factor as a weightedaverage.
Using the above method for each cluster head node, we form the path by a continual circulation until the selected relay node’s level is 1 (the next-hop about the level 1 node is the base station; there is no need to choose). When forming the path, the requirements are as follows:
– The selected node level should be smaller than the former one, which prevents unnecessary jumps between relay nodes.
– When there is an empty set in the intersection of relay nodes, the cycle ends, and the next-hop is set to the base station.
3.3.2Transmission stable stage
Firstly, the information is collected by the nodes in each cluster, and then, the nodes transmit the information to the cluster head nodes. Secondly, the cluster head node is responsible for integrating the information and then transmitting the information to the base station. Cluster heads go along with the routing path that is made by the protocol. They send the information to the relay node until reaching the base station.
4Experiment and analysis
4.1Experimental parameters
In this section, the experiment is in Matlab. According to literature [23], the optimal number of cluster heads ratio p opt is related to the network area size and the number of nodes. Thus, it is only related to the number of nodes under the same working area. In this paper, we add the following parameters according to the LEACH simulation experiment, which are shown in Table 1. In the experiment, we deploy 2500 nodes, which are randomly and uniformly distributed in an area of 500 m×500 m. The initial energy of each node is 2 J.
4.2Experimental results and analysis
– The simulation results of the network life cycle are shown in Fig. 3, under the deployment of 2500 nodes. The results are compared to the LEACH, SEP, MR-LEACH, and FD-LEACH protocols. From the graph, it can be observed that FD-LEACH can maintain a longer life cycle, and the number of nodes that survive over a period of time can achieve an ideal state, thereby providing a more reliable environment for collecting information for the entire network.
– Figure 4 compares the network residual energy of LEACH, SEP, MR-LEACH, and FD-LEACH 4 protocols. The figure reveals that the SEP protocol is slightly better than the LEACH protocol. Additionally, MR-LEACH is improved substantially, and the FD-LEACH protocol is the best protocol with the slowest energy attenuation curve.
– Figure 5 compares the number of cluster heads in each round of the LEACH, SEP, MR-LEACH, and FD-LEACH4 protocols. The figure demonstrates that the FD-LEACH protocol is better than the other protocols. The number of cluster heads is dominant because the number of survival nodes is a more reasonable value, and there is a greater number of randomly selected cluster heads, which lays the foundation for energy saving in the entire network.
– Concrete numerical values are presented in Tables 2–4 in order to compare the four protocols and supplement the above figure. The tables include the following statistics: the number of surviving nodes, the residual energy, and the cluster head number for every 50 rounds in each protocol. As shown in the tables, LEACH and SEP can only continue for around 200 rounds, MR-LEACH can continue for 350 rounds, and FD-LEACH can continue for 400 rounds. From the data provided, the number of nodes that did not survive can be computed for every 50 rounds. From this information, it can be found that the node death rate of the former two protocols slowly becomes smaller. In contrast, the node death rate of MR-LEACH is slow at the beginning and end, but it is fast in the middle of the network death rate. The node death rate of FD-LEACH slowly speeds up. As is shown in Table 3, the network residual energy is directly proportional to the number of surviving nodes. As evident from the data given in Table 4, when the numbers of surviving nodes are similar, there may be more cluster heads for MR-LEACH than for FD-LEACH. It verified that the capita clusters are randomly selected, but from the overall, it is still proportional to the number of nodes that survived. As shown in the three tables, the results indicate that the FD-LEACH protocol is more ideal.
5Conclusion
In this paper, we analyzed multiple protocols developed for large-scale sensor networks, and the related research work was classified. Then, we utilized fuzzy sets and fuzzy decision theory in the process of building a cluster routing for path optimization based upon LEACH. Then, a low energy adaptive clustering multi-hop routing protocol based on fuzzy decision (FD-LEACH) was put forward. At last, we compared the LEACH, SEP, MR-LEACH, and FD-LEACH protocols through an experiment. The results show that the FD-LEACH protocol has better energy efficiency and can prolong the network lifetime in a large-scale condition.
In the future, we can further optimize our protocol. We will introduce an intelligent algorithm in soft computing in order to make the selection of cluster heads more reasonable. In addition, we will set other parameters to optimize the path choice through necessary in-depth study. Finally, we will explore the trade-off security and energy consumption in routingprotocols.
Acknowledgments
This work is supported by the China Aviation Science Foundation (NO. 20101952021) and the Fundamental Research Funds for the Central Universities (NO. NZ2013306).
References
1 | Liu A, Ren J, Li X, Chen Z, Shen XS (2012) Design principles and improvement of cost function based energy aware routing algorithms for wireless sensor networks Comput Netw 56: 7 1951 1967 |
2 | Ataul B, Shamsul W, Arunita J (2009) A genetic algorithm based approach for energy efficient routing in two-tiered sensor networks Ad Hoc Networks 7: 665 676 |
3 | Li C, Zhang H, Hao B (2011) A survey on routing protocols for large-scale wireless sensor networks Sensors 11: 4 3498 3526 |
4 | Huang G, Li X, He J (2006) Dynamic minimal spanning tree routing protocol for large wireless sensor networks Proceedings of 2006 1st IEEE Conference on Industrial Electronics and Applications 1531 1535 Singapore |
5 | Smaragdakis G, Matta I, Bestavros A (2004) SEP: A stable election protocol for clustered heterogeneous wireless sensor networks Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA2004) 1 11 Boston, MA |
6 | Li H, Liu Y, Chen W, Jia W, Li B, Xiong J (2013) COCA: Constructing optimal clustering architecture to maximize sensor network lifetime Comput Commun 36: 3 256 268 |
7 | Chen J, Yin Z, Li D, Sun T (2008) A distributed and effective cluster routing protocol of sensor networks Proceedings of 1st International Conference on Intelligent Networks and Intelligent Systems 271 275 Wuhan, China |
8 | Al-Karaki JN, Kamal AE (2004) Routing techniques in wireless sensor networks: A survey IEEE Wirel Commun 11: 6 28 |
9 | Jung JW, Wang W, Ingram MA (2011) Cooperative transmission range extension for duty cycle-limited wireless sensor networks Int Conf on Wireless Communication, Vehicular Technology, Information Theory and Aerospace and Electronic Systems Technology 1 5 Chennai |
10 | Akkaya K, Younis M (2005) A survey on routing protocols for wireless sensor networks Ad Hoc Netw 3: 3 325 349 |
11 | Yuan L, Wang X, Gan J, Zhao Y (2010) A data gathering algorithm based on mobile agent and emergent event-driven in cluster-based WSN Networks 5: 1160 1168 |
12 | Azim MA, Jamalipour A (2006) Optimized forwarding for wireless sensor networks by fuzzy inference system In Proceedings of the IEEE International Conference on Wireless Broadband and Ultra Wideband Communications 13 16 Sydney, Australia |
13 | Nikolidakis SA (2013) Energy efficient routing in wireless sensor networks through balanced clustering Algorithms 6: 1 29 42 |
14 | Muhammad OF, Abdul BD, Ghalib AS (2010) MR-LEACH: Multi-hop routing with low energy adaptive clustering hierarchy 2010 Fourth International Conference on Sensor Technologies and Applications (ENSORCOMM), IEEE Communications Society 262 268 New York |
15 | Rajagopalan R, Varshney PK (2006) Data-aggregation techniques insensor networks: A survey IEEE Commun Surv Tutorials 8: 4 48 63 |
16 | Sharma S, Jena SK (2011) A survey on secure hierarchical routing protocols in wireless sensor networks Proceedings of the 2011 International Conference on Communication, Computing & Security 146 151 ACM |
17 | Sudevalayam S, Kulkarni P (2011) Energy harvesting sensor nodes: Survey and implications IEEE Commun Surv Tutorials 13: 3 443 461 |
18 | Rault T, Bouabdallah A, Challal Y (2014) Energy efficiency in wireless sensor networks: A top-down survey Computer Networks 67: 104 122 |
19 | Quang V, Miyoshi T (2008) Adaptive routing protocol with energy efficiency and event clustering for wireless sensor network IEICE Trans Commun E91-B: 2795 2805 |
20 | Heinzelman WB, Chandrakasan AP, Balakrishnan H (2002) An application-specific protocol architecture for wireless micro sensor networks IEEE Transactions on Wireless Communications 1: 4 660 670 |
21 | Ge W, Zhang J, Xue G (2008) Joint clustering and optimal cooperative routing in wireless sensor networks Proceedings of 2008 International Conference on Communication 2216 2220 Beijing, China |
22 | Heinzelman W, Chandrakasan A, Balakrishnan H (2000) Energy-efficient communication protocol for wireless micro sensor networks, Maui: IEEE Computer Soeiety Proc of the 33rd Annual Hawaii Int’ 1 Conf on System Sciences 3005 3014 |
23 | Songzhu X, Su W, Jun N (2009) A new energy-efficient routing algorithm based on ant colony system for wireless sensor networks, Washington USA, IEEE Communications Society 2009 Fourth International Conference on Internet Computing for Science and Engineering 176 180 |
Figures and Tables
Fig.1
The node hierarchy level.
Fig.2
The elements schematic diagram.
Fig.3
The network life cycle of LEACH, SEP, MR-LEACH, and FD-LEACH.
Fig.4
The network residual energy of LEACH, SEP, MR-LEACH, and FD-LEACH.
Fig.5
The number of cluster heads of LEACH, SEP, MR-LEACH, and FD-LEACH.
Table 1
The added simulation parameters
| The parameter name | Value |
| The number of nodes; Num | 2500 |
| Network area; Ms×Ms | 500 m×500 m |
| Initial energy of nodes; E0 | 2 J |
| Cluster heads ratio (expect); popt | 0.05/ |
Table 2
The number of surviving nodes for every fifty rounds
| Round | LEACH | SEP | MR-LEACH | FD-LEACH |
| 50 | 1143 | 1209 | 2356 | 2500 |
| 100 | 495 | 578 | 2111 | 2500 |
| 150 | 175 | 235 | 1725 | 2422 |
| 200 | 19 | 58 | 1250 | 2251 |
| 250 | 0 | 0 | 756 | 1940 |
| 300 | 0 | 0 | 348 | 1569 |
| 350 | 0 | 0 | 77 | 1047 |
| 400 | 0 | 0 | 0 | 310 |
| 423 | 0 | 0 | 0 | 0 |
Table 3
The residual energy for every fifty rounds
| Round | LEACH (J) | SEP (J) | MR-LEACH (J) | FD-LEACH (J) |
| 50 | 984.6747 | 1.2040e+03 | 3.5639e+03 | 4.1945e+03 |
| 100 | 249.9316 | 354.9692 | 2.3441e+03 | 3.3786e+03 |
| 150 | 49.2996 | 90.0910 | 1.3774e+03 | 2.5797e+03 |
| 200 | 1.0257 | 9.4892 | 696.9256 | 1.8272e+03 |
| 250 | 0 | 0 | 294.9766 | 1.1915e+03 |
| 300 | 0 | 0 | 85.0580 | 630.5214 |
| 350 | 0 | 0 | 14.0726 | 221.1004 |
| 400 | 0 | 0 | 0 | 16.1715 |
| 423 | 0 | 0 | 0 | 0 |
Table 4
The cluster head number for every fifty rounds
| Round | LEACH | SEP | MR-LEACH | FD-LEACH |
| 50 | 69 | 65 | 123 | 108 |
| 100 | 14 | 30 | 107 | 124 |
| 150 | 9 | 8 | 75 | 114 |
| 200 | 2 | 3 | 62 | 114 |
| 250 | 0 | 0 | 41 | 104 |
| 300 | 0 | 0 | 17 | 94 |
| 350 | 0 | 0 | 7 | 57 |
| 400 | 0 | 0 | 0 | 14 |
| 423 | 0 | 0 | 0 | 0 |
