A Load-Balanced Clustering Algorithm Using Fuzzy Logic for Maximizing Lifetime of Wireless Sensor Networks

A Load-Balanced Clustering Algorithm Using Fuzzy Logic for Maximizing Lifetime of Wireless Sensor Networks

Dibya Ranjan Das Adhikary1,*and Dheeresh K Mallick2

1 Department of Computer Science and Engineering, BIT Mesra, Ranchi,India.
2 Department of Computer Science and Engineering, BIT Mesra, Ranchi,India.

(Received 2 September 2015; Accepted 10 November 2015; Published on line 1 September 2016)
*Corresponding author: dibya@bitmesra.ac.in
DOI: 10.5875/ausmt.v6i3.1016

Abstract: In wireless sensor networks (WSN), clustering has been shown to effectively prolong network lifetime, and unequal clustering, which is an extension to traditional clustering, has demonstrated even better results. In unequal clustering, each individual cluster has a different cluster range. To date, clustering range calculations has been performed based on node positions in the network. However, node fitness is an important parameter. If assigned to a larger cluster range, nodes with low fitness can create inconsistencies within the network. Moreover, these methods fail to incorporate uncertainties in parametric quantities encountered during cluster head (CH) selection and cluster range assignment. Therefore, we propose a fuzzy logic based chance calculation that handles uncertainties in parametric quantities. The calculated chance value is applied for the selection of CHs and the chance value, is used along with node position to assign a proper cluster range. Compared with some well known approaches shows that the proposed approach creates more balanced clusters, consequently extending network lifetime.

Keywords: wireless sensor networks, fuzzy inference system; node density, unequal clustering, relay, network lifetime.

Introduction

The advancement in micro-electro-mechanical- system technologies has reduced the cost and size of sensors, thus significantly extending their range of possible applications [1]. A typical sensor is a device with built in sensing and communication capabilities. A single sensor has a limited sensing area so monitoring an extended area requires combining multiple sensors. The combined effort of sensors to sense the environment and report to a base station (or sink) creates a wireless sensor network (WSN)[2]. WSNs were initially developed for defense purposes [3] but their tiny size, low price and robustness in inhospitable conditions make them suitable for a plethora of applications, such as body area networks [3], traffic control [4], environmental monitoring [5], etc. [2, 6].

WSNs are primarily used to monitor and report on an area of interest. Each sensor senses its region, processes the sensed data and sends the processed data to the sink, usually through intermediate sensors. This process is energy intensive. Sensor nodes rely on battery power, and in most cases these batteries cannot be recharged [7,8]. Consequently, energy-efficiency is a vital concern in WSN design. Moreover, sensors are usually deployed randomly, so two sensors may be closely adjacent, sensing the same data, raising the need for data aggregation [9].

Clustering is an effective way to achieve energy efficiency and data aggregation in WSNs [8]. In clustering, the whole network is divided into multiple clusters, each with a cluster head (CH). Nodes belonging to a cluster send data to the CH, which then aggregates, compresses and send the data to the sink [10]. The CH can send the data directly to the sink or through intermediate CHs (multi-hop), which depend on the architecture of the WSN. According to the authors in [11] the multi-hop approach is more energy efficient than the direct approach. Unfortunately, the transmission load on the CHs is significantly increased in multi-hop approach because in addition to serving as a local sink, they need to serve as a router. As a result, the CHs nearer to the sink bear intense relay traffic, which drains their energy faster [12].

Initial clustering algorithms proposals divided the network into fixed size partitions. The problem with such algorithms was that they tried to maximize the network lifetime at the cost of non-uniform energy drainage in the network. Few algorithms solve the issue using unequal clustering [13-17], where clusters have a different cluster range depending on their position in the network. Clusters close to the sink are smaller in size in order to preserve energy for inter-cluster communication. To date, the clustering range calculation has been done based on node position in the network. But nodes fitness is also an important parameter. If assigned a bigger cluster range, nodes with low fitness can create inconsistency within the network. Moreover, these methods fail to account for uncertainty in parametric quantities encountered during cluster head (CH) selection and cluster range assignment.

Fuzzy-logic has been used to mimic human decision-making behavior. In WSNs, fuzzy-logic has been used in many scenarios such as the selection of CHs [18,19] and assigning the clustering range to the CHs [20-22]. The significance of fuzzy-logic in WSNs and to overcome the unequal energy drainage problem, a new fuzzy-logic based CH selection along with unequal clustering is proposed. The notable features of the proposed methodology are as follows:

  • Distributed election of CHs, i.e., CH election is based on local information.
  • CHs are selected non-probabilistically; nodes wait for a certain amount of time before declaring itself as a CH. The wait time is inversely proportional to its fitness.
  • The fitness or chance is calculated using fuzzy-logic, giving more importance to node density.
  • The CHs have different clustering ranges; the clustering range of a CH is a function of its distance from the sink and its chance value.
  • Dynamic cluster ranges for CHs; the cluster range of CH varies from one round to the next.
  • A comparison of application-specific relay selection.

The remainder of the paper is organized as follows. The related work section briefly summarizes some well known clustering approaches. The following section briefly illustrates the system model of our proposed method. Next, the proposed method is described followed by a detailed simulation and analysis of the proposed work. Conclusion is given in the final section.

Related Work

Over the last decade, many clustering algorithms have been proposed. A good clustering algorithm can be classified by the way it selects CHs, the CH sensing range and the way it delivers its data to the sink [23]. We have reviewed some of the most relevant papers related to clustering, unequal clustering, and fuzzy-logic based clustering.

LEACH [24] was one of the first algorithms to improve energy efficiency through clustering. In LEACH, the clustering cycle is divided into cluster formation and data transmission phase. It randomly rotates CHs to distribute energy consumption all over the network. In the data transmission phase, each CH transmits the aggregated data packet directly to the sink.

In the cluster formation phase, the randomly selected CHs will inform other nodes about its selection. The remaining nodes can choose which cluster to join, depending on the received signal strength. In general, the selection of CH is dependent on a threshold value T(n). T(n) is given as follows.

\[T\left( n \right)=\left\{ \begin{matrix} \frac{p}{1-p\text{*}\left[ rmod\left( \frac{1}{p} \right) \right]},~~~~~~~ifn\in G \\ ~~~~0~~~~~~~,~~~~~~otherwise \\ \end{matrix} \right\}\tag{1}\]

where $p$ is the preferred percentage of CHs, $r$ is the current round, and $G$ is the set of nodes that have not been CH in the last I/p rounds. In each round, the threshold T(n) gets increased for nodes that have not been CH. Thus, this procedure can guarantee that every node has an equal chance of being a CH.

The same authors in [25] proposed LEACH-C or LEACH-Centralized, a centralized version of LEACH in which the sink chooses the CH node. In LEACH-C, every node sends its position and status of remaining energy to the sink. The sink then selects the CHs using the simulated annealing approach from a set of nodes whose remaining energy exceeds the average node energy of the network. Apart from the cluster formation phase, the algorithm is identical to LEACH.

Many follow-up algorithms [26-29] further improvised on LEACH. Multihop-LEACH [27] tries to eradicate the direct communication between CHs and the sink by selecting an optimal path that adapts to multiple hops. Energy-LEACH [28] considers the remaining energy of the node while choosing the CHs, thus eliminating the randomized selection of CH of LEACH.

The authors of the Hybrid Energy Efficient Distributed (HEED) protocol [30, 31] use remaining energy as a parameter while selecting a $CH$. A node calculates its probability, of becoming a $CH$, ${{CH}_{prob}}$ as follows.

\[\text{C}{{\text{H}}_{\text{prob}}}=\text{max}\left( {{\text{C}}_{\text{prob}}}+\frac{{{\text{E}}_{\text{residual}}}}{{{\text{E}}_{\text{max}}}},{{\text{P}}_{\text{min}}} \right)\tag{2}\]

where ${{C}_{prob}}$ is optimal percentage $CHs$, $\frac{{{\text{E}}_{\text{residual}}}}{{{\text{E}}_{\text{max}}}}$ is the ratio of nodes remaining energy and initial energy and ${{P}_{min}}$ is a threshold value chosen to impose a restriction on the ${{CH}_{prob}}$ value. It uses a different communication range for inter-cluster broadcast and intra-cluster broadcast. HEED terminates within a constant number of iterations and achieves a fair distribution of $CHs$ across the network compared to LEACH.

Unequal clustering has been proposed as an effective way of balancing energy consumption. The principle of un-equality in clustering was first discussed by Soro and Heinzelman [13]. They proposed a scheme called unequal clustering size (UCS). The main idea of UCS was to form adaptive clusters based on their distance to the sink. UCS is based on the assumption that the CHs are placed at the center of the clusters and the CHs have more energy. This approach provides a significant improvement over the use of equal sized clusters, but this approach depends on assumptions which are impractical for real world applications

The authors in [14] proposed another unequal clustering mechanism called Energy-efficient unequal clustering (EEUC) which, unlike UCS, selects CHs based on a competition. It probabilistically selects some tentative CHs, and then the final set of CHs is selected on the basis of their remaining energy. In EEUC, cluster size is proportional to the distance from the sink with clusters closer to the sink being smaller. EEUC introduced an energy-aware multi-hop routing protocol to efficiently handle the energy usage in inter-cluster communication.

Unequal cluster-based Routing (UCR) [15] is an extension to the EEUC. Like EEUC, in this approach, cluster sizes gradually decrease as one approaches the sink, thus saving energy for inter-cluster communication. Apart from the unequal clustering, a greedy geographic and energy-aware routing protocol is also designed specifically for inter-cluster communication.

Some clustering algorithms use fuzzy-logic to resolve uncertainties in WSN. Low energy adaptive unequal clustering protocol using Fuzzy c-means (LAUCF)[17] is an unequal cluster based approach. In LAUCF the authors use the Fuzzy c-mean algorithm to form disjointed clusters of different sizes. After cluster formation, $CHs$ are selected probabilistically for each cluster.

Gupta et al., [18] proposed an algorithm for CH selection using fuzzy logic. In this approach, in each round all nodes send their clustering information to the sink. The sink then calculates the CHs and broadcasts back to the network.

Similar to Gupta et al., the cluster head election mechanism using fuzzy logic (CHEF) [19] uses a distributed approach with fuzzy logic for CH selection. It uses two fuzzy descriptors: energy and local distance. Energy means the remaining energy of that node and local distance is the sum of the distance between the node and all nodes within a given range.

The fuzzy energy-aware unequal clustering algorithm (EAUCF) [20,21] addresses the hot spot problem with unequal clustering using fuzzy logic. It assumes the same probabilistic approach as LEACH for tentative CH selection. The cluster range of the tentative CH is obtained by the fuzzy inference system (FIS). The FIS takes two inputs, remaining energy and distance to the sink, to calculate the clustering range. The multi-objective fuzzy clustering algorithm (MOFCA)[22] is a fuzzy logic-based unequal clustering algorithm similar to EAUCF. Unlike EAUCF, MOFCA uses node density along with remaining energy and the distance to the sink to calculate the clustering range.

The advantages of the proposed algorithm over the existing ones are summarized as follows.

  • The proposed approach uses local information to select the CHs, as opposed to the probabilistic approach of [14,15,17,20-22,24,27], the centralized approach of [18,25] and the strategic deployment of [13].
  • The proposed approach selects CHs on the basis of remaining energy, centrality and node density, whereas only energy was considered in [17,25,28,30,31] and energy and centrality was considered in [19].
  • In the proposed approach, the Cluster range is proportional to the CH distance from the sink and fitness. But in [14,15,25] the cluster range was only a function of the distance to the sink; in [20,21] the clustering range was calculated using remaining energy and distance to the sink; and in [22] the clustering range was calculated using remaining energy, distance to sink and node density.

System model

In this paper, we consider a WSN with N nodes deployed over an area of interest. Each sensor continuously senses its vicinity and sends information to the sink periodically through its CH. Each sensor can have different functionality according to its position. If it works as a cluster member, its job is to sense the vicinity and send the information to its CH. If it works as a CH, in addition to sensing its vicinity, it needs to collect data from its cluster members, compress it and send it towards the sink. Apart from this functionality, a CH can work as a relay node. In addition, the following assumptions are made:

  • All the sensors along with the sink are stationary after deployment.
  • All the sensors are homogeneous and possess the same amount of initial energy.
  • Sensors are left unattended and thus their batteries cannot be recharged.
  • Each sensor has a unique identifier (ID).
  • Sensors can vary the amount in terms of transmission power, according to the distance of the receiving node.
  • The distance between any pair of sensors can be calculated based on the received signal strength (RSS), if the transmitted power is known.
  • The radio links are symmetric. Thus, the communication between any two nodes requires the same transmission power.

But in a real world scenario, some of the assumptions made about the system model do not hold. For example, we consider that the distance between any pair of sensors can be calculated on the basis of RSS. However, because of multi-path fading and the shadowing effect, the measured distance is subject to error. But RSS can give a good approximation of the distance with a low energy overhead [32].

We use the first-order radio model as stated in [25] to model the energy dissipation. The free space model (${{d}^{2}}$ power loss) has been used when the distance between the receiver and the transmitter is lower than a threshold value ${{d}_{0}}$. For other cases multipath fading channel model (${{d}^{4}}$ power loss) has been used. The energy required to transmit an l-bit packet over a distance d is given as follows:

\[{{\text{E}}_{\text{Tx}}}\left( \text{l},\text{d} \right)=\text{l}{{\text{E}}_{\text{elec }\!\!~\!\!\text{ }}}+\text{l}\epsilon {{\text{d}}^{\text{ }\!\!\alpha\!\!\text{ }\!\!~\!\!\text{ }}}=\left\{ \begin{matrix} l{{\text{E}}_{\text{elec}}}+l{{\epsilon }_{\text{fs}}}{{\text{d}}^{2}},d<{{\text{d}}_{0}} \\ l{{\text{E}}_{\text{elec}}}+l{{\epsilon }_{\text{mp}}}{{\text{d}}^{4}},d\ge ~{{\text{d}}_{0}} \\ \end{matrix} \right.\tag{3}\]

where ${{E}_{elec}}$ energy is required to run the transceiver, depending on factors like digital coding and modulation. ${{\epsilon }_{\text{fs}}}{{\text{d}}^{2}}$ or ${{\epsilon }_{\text{mp}}}{{\text{d}}^{4}}$ is the amplifier energy that depends on the transmission distance and an acceptable bit error rate. The threshold value ${{d}_{0}}$ is obtained from the equation given below:

\[{{\text{d}}_{0}}=\text{ }\!\!~\!\!\text{ }\sqrt{{{\epsilon }_{\text{fs}}}/{{\epsilon }_{\text{mp}}}}\tag{4}\]

The energy required to receive a packet is given as:

\[{{\text{E}}_{\text{Rx}}}\left( \text{l} \right)=\text{ }\!\!~\!\!\text{ l}{{\text{E}}_{\text{elec }\!\!~\!\!\text{ }}}\tag{5}\]

We assume that the sensed information is highly co-related, therefore the CH always aggregates the data gathered from the member nodes and compresses it into a single packet. In some previous approaches [33], the relay node can also handle data aggregation. This is not feasible in our proposed approach because the co-relation factor is quite negligible for data from different clusters. So, in our proposed approach, the relay node doesn’t aggregate the relay packets. Instead, we assume that an ${{\text{E}}_{\text{DA}}}(\text{nJ}/\text{bit}/\text{signal})$ amount of energy is consumed by the $CH$ for data aggregation.

Proposed Methodology

In most WSN applications, nodes are deployed randomly. Thus, the underlying clustering approach must consider the distribution of nodes in the cluster or it can result in an unbalanced energy consumption structure, where some nodes die rapidly, causing partitioning in the network. Some algorithms [24,29,30] divide the network into nearly equal sized clusters and the CH communicates with the sink directly. Some algorithms [27,28,31] use multi-hop communication. In the former case, the more distant nodes die rapidly, while in the latter nodes closer to the sink die quickly [14,15]. Some algorithms [13-15,20-22] have use inequality in clusters to balance energy consumption, which proved to be more efficient than in equal distributions.

The proposed algorithm features a more balanced clustering scheme by considering the remaining energy, node concentration/density and centrality. The $CHs$ are selected based on local information. A node waits a certain amount of time before declaring itself as $CH$, where the wait time is inversely proportional to the node’s chance value. The chance value is the output of FIS used to balance between different input parameters. After that, each of the selected CHs calculates its cluster range. The cluster range is calculated using the node’s distance from the sink and its chance value; it is proportional to the node’s distance from the sink and its fitness. The greater the node’s distance from the sink and the greater its chance, the greater the cluster range, and vice-versa. An overview of the proposed unequal clustering scheme is given in Fig. 1.

The clustering range of the $CHs$ in the proposed approach varies from round to round because the cluster range is dependent on chance and the chance value is dependent on dynamic parameters (remaining energy, node density and centrality). Finally a comparison of relay selection based on chance and distance to sink is given with a detailed analysis of both approaches.

The proposed approach is carried out in rounds, and each round is divided into three stages: $CH$ selection phase, cluster set-up phase and steady-state phase. A neighborhood discovery phase is executed only once before the start of the first round.

Neighborhood discovery phase

The algorithm starts with the neighborhood discovery phase, in which the sink broadcasts a Hello message. On receiving the Hello message, a node can calculate its distance from the sink. The receiving node broadcasts a ${{Hello}_{Reply}}$ message consisting of sender id, within a range ${{R}_{max}}$ which is the maximum cluster range. Nodes receiving the ${{Hello}_{Reply}}$ message add the sender as its neighbor and record information like sender id and distance to neighbor. Whenever a node’s remaining energy is below a given threshold, it will announce itself as inactive by sending a Dead message. Nodes receiving the Dead message update their neighborhood information. The neighborhood discovery phase should be made only once at the time of network deployment.

Cluster Head Selection Phase

Following the neighborhood discovery phase, each node waits for a ${{Wait}_{Time}}$ before it broadcasts the ${{Candidate}_{CH}}$ message. The ${{Wait}_{Time}}$ is calculated as follows:

\[Wai{{t}_{Time}}=\frac{1}{Chance}\tag{6}\]

where chance is the output of the FIS. The value of variable chance ranges between 0 and 1, thus higher values are associated with lower waiting times.

The input variables of the FIS are Remaining Energy, Centrality and Node Density. The variables are defined as follows.

  • Remaining Energy – Energy level remaining in the node.
  • Centrality – A value which classifies the nodes based on the distance from the center of the cluster.
  • Node Density – Number of nodes present in the clustering range ${{R}_{max}}$.

We use fuzzy inference systems (FIS) to handle ambiguity. A FIS is a system that uses fuzzy set theory to map an input space to an output space [34]. In our proposed approach, we use the Mamdani method of fuzzy inference [35]. The Mamdani method is known for its simplicity, as it requires fewer computations. Fig. 2 gives a detailed outline of the FIS used in the proposed work. At first the inputs are transferred into linguistic terms, a process called fuzzification. This process is accomplished with the help of membership functions. The fuzzy inference unit then uses the fuzzy “if-then” rules to map the fuzzy inputs to fuzzy outputs. Finally the fuzzy outputs are defuzzified to crisp values, a process called defuzzification.

The first input fuzzy set is the remaining energy; Fig. 3 illustrates membership functions of the input variable remaining energy. The fuzzy sets in the form of linguistic variables include low, mid and high. The linguistic variable mid is represented using a triangular membership function, whereas the linguistic variables low and high are represented using a trapezoidal membership. The second input fuzzy set is node centrality; Fig. 4 illustrates the membership functions of input variable centrality. The fuzzy sets in the form of linguistic variables include close, not so far and far. The linguistic variable not so far is represented using a triangular membership function, whereas the linguistic variables close and far are represented using a trapezoidal membership. The third input fuzzy set is node density; Fig. 5 illustrates membership functions of the input variable node density. The fuzzy sets in the form of linguistic variables include low, mid and high. The linguistic variable mid is represented using a triangular membership function, whereas the linguistic variables low and high are represented using a trapezoidal membership.

The only fuzzy output variable of the FIS is chance; Fig. 6 illustrates the membership functions of the output variable chance. There are nine linguistic variables for the output fuzzy set chance: very low (VL), low, rather low (RL), med low (ML), medium (Med), med high (MH), rather high (RH), high and very high (VH). The linguistic variables VL and VH are represented using a trapezoidal membership function whereas the remaining seven linguistic variables are represented by triangular membership functions. This work mostly depends on triangular membership functions because this function type is quite simple and requires fewer computations.

As stated earlier, the fuzzy inference unit uses the fuzzy “if-then” rules to calculate chance. Table 1 defines twenty-seven fuzzy mapping rules based on the three fuzzy inputs: Remaining Energy, Centrality and Node Density. By applying these fuzzy “if-then” mapping rules to the inputs, the fuzzy output chance is generated. The output fuzzy variable can only be used if it is defuzzified to a single crisp value. In this paper, the center of gravity (COG) method [36] is used for defuzzyfication. The method is given as follows.

\[{{Z}^{\text{*}}}\,=\,\,\frac{\mathop{\int }^{}{{U}_{i}}(Z)ZdZ}{\mathop{\int }^{}{{U}_{i}}(Z)dZ}\tag{7}\]

where ${{\text Z}^{*}}$ is the defuzzified output, ${{\text U}_{\text i}(\text Z)}$ is the aggregated membership function and $\text Z$ is the output variable.

Fuzzy rules are usually generated either from experimental results, or based on heuristics. This work uses the heuristic based fuzzy rule generation method. For example, if a particular candidate CH’s battery is full, it has a handful of neighbors and the node’s location is quite central to the cluster, thus it has the highest chance value. On the other hand, if a particular candidate CH’s battery is closer to the threshold, it has either a very high or very low numbers of neighbors and it is located far from the center of the cluster, then it has the lowest chance value.

When the Wait Time is over, the candidate CH broadcasts a Candidate CH message in its cluster range. The clustering range has been calculated as follows.

\[\text{ }\!\!~\!\!\text{ }{{R}_{i\_max}}=\left( \left( 1-\text{c}\frac{{{\text{d}}_{\text{max}}}-\text{d}({{\text{s}}_{\text{i}}},\text{SI})}{{{\text{d}}_{\text{max}}}-{{\text{d}}_{\text{min}}}} \right)\times \text{ }\!\!~\!\!\text{ }{{R}_{max}} \right)\times \left( \frac{Chanc{{e}_{i}}}{Chanc{{e}_{max}}} \right)\tag{8}\]

where ${{d}_{max}}$ denotes the sensor having maximum distance from the sink, ${{d}_{min}}$ denotes the sensor having minimum distance from the sink, and $d$(${{s}_{i}}$,${SI}$) denotes the distance between the sensor ${{s}_{i}}$ and the sink. C is a constant coefficient between 0 and 1 and ${{R}_{max}}$ is the maximum competition range. ${{chance}_{iis}}$ the Chance value of candidate CH $i$ and ${{chance}_{max}}$ is the maximum possible chance value.

Towards the end of the network lifetime, the chance value shrinks, as does the clustering range. This drives the network to form a large set of small clusters, which in turn drains the energy more quickly. To overcome this situation, we set a threshold for the lower limit of the clustering range. Thus, when the ${{R}_{i{{\_}_{max}}}}$ values fall below the threshold value, we set the clustering range as the threshold value. The optimal clustering range ${{R}_{i{{\_}_{opt}}}}$ is given as follows.

\[{{R}_{i{{\_}_{opt}}}}=\text{max}\left( {{R}_{i{{\_}_{max}}}},{{R}_{min\text{ }\!\!~\!\!\text{ }}} \right)\tag{9}\]

where ${{R}_{min}}$ is the given threshold.

The candidate CHs are the set of nodes which have sent the ${{Candidate}_{CH}}$ message, after which they have either not received a further ${{Candidate}_{CH}}$ message or their chance value is higher than their neighbors. A node with a smaller chance value will terminate its timer and become a cluster member. It may also be possible that a node with a smaller chance value sends a ${{Candidate}_{CH}}$ message, in which case the node will send a ${{Quit}_{Election}}$ message and become a cluster member. This competition guarantees that only nodes with the best chance value will be the CH and there will be no other CH in its cluster range.

Cluster set-up phase

In this phase, the remaining candidate CHs send a Final_CH message to a distance twice its clustering range (i.e. $2*{{R}_{i{{\_}_{opt}}}}$) to inform the neighboring CH of its election as CH. The Final_CH message consists of node id, Chance and distance to sink. On receiving a Final_CH message, the CHs maintain a table of its neighbor CHs containing the neighbor node id, Chance and distance to sink. If every non-CH node receives multiple final CH messages, it will join the closest CH by sending a Membership message. Now, each CH prepares a TDMA schedule telling each member node when to transmit to nodes for which it received Membership messages. This TDMA schedule is broadcast back to the member nodes in the cluster.

Steady-state phase

In this phase, the data transmission begins after the CHs are selected and TDMA schedule is fixed. Every member node sends its data according to the predefined TDMA schedule and enters sleep state. The CH node must keep its receiver on to receive data from the member nodes in its cluster. After receiving all the data from member nodes, the CH compresses the data and passes it to the next CH or to the sink directly ($if~~distance~to~sink\le {{R}_{max~}}$).

The selection of relay CH depends on the underlying application of the sensor networks. For applications in which network lifetime is an important factor, the selection of relay is as follows.

\[C{{H}_{Relay\text{ }\!\!~\!\!\text{ }}}=\{C{{H}_{i}}/C{{H}_{i}}.chance\text{ }\!\!~\!\!\text{ }is\text{ }\!\!~\!\!\text{ }maximum\text{ }\!\!~\!\!\text{ }\}\tag{10}\]

where ${{CH}_{i}}$ is the neighboring CH whose distance to the sink is less than that of the CH itself and ${{CH}_{i}}.chance$ is the fuzzy output chance of ${{CH}_{i}}$.

For applications which require latency minimization, relay selection proceeds as follows.

\[C{{H}_{Relay\text{ }\!\!~\!\!\text{ }}}==\left\{ C{{H}_{i}}/C{{H}_{i}}.distance\_to\_sink~is~minimum\text{ }\!\!~\!\!\text{ } \right\}\tag{11}\]

where ${{CH}_{i}}$ is the neighboring CH and ${{CH}_{i}}.distance_to_sink$ is the distance between the sink and ${{CH}_{i}}$.

Simulation and Result Discussion

This section presents the results of the simulation experiments to illustrate the effectiveness of the proposed method. First, we describe the parameter settings of the proposed method, followed by an analysis of relay selections and lastly, a detailed comparison with some of the existing algorithms. For simplicity, in this work we used an ideal Mac layer and error free communication link and the energy is consumed whenever a sensor sends or receives data or performs data aggregation. We compare the proposed algorithm with LEACH, Multihop-LEACH and UCR.

The metrics used for comparing these algorithms are the network lifetime, average number of clusters, and the metrics used in [37], i.e., first node dies (FND), half of nodes alive (HNA) and last node dies (LND). FND represents an estimated value for the round in which the first node dies. HNA represents the estimated value for the round in which half of all nodes are alive. Likewise LND denotes estimated value for the round in which the last node dies. The FND and HNA metrics are considerably more powerful than LND because after half of the nodes are dead the network is almost useless.

The simulations were performed using MATLAB on two scenarios with 100 randomly deployed nodes.

  • cenario-I: The sensor nodes are randomly deployed over a 200 m x 200 m area, with just one sink located at position 100 m, 210 m).
  • Scenario-II: The sensor nodes are randomly deployed over a 200 m x 200 m area, with just one sink located at position (100 m, 100 m).

While simulating the parameter settings, we use scenario-I and then conduct a comparison using both scenarios. The remaining parameters are same for the both the scenarios (see Table 2). The radio model used in this simulation is the first-order radio model as stated in [25] to model the energy dissipation. In each round of the simulation the CHs are elected before the cluster is formed. Then every non-CH node sends data to the CH which aggregates the data and forwards it to the next CH or to the sink. The aggregation ratio for the simulation is set at 10% and we use the mechanism from [21]. Parameters values are set according to the given network dimension, network parameters and location of the sink. So the values and range need to vary with network dimensions or parameters, or for different sink locations.

Parameter Setting

There are three main parameters in the proposed method which influence the clustering mechanism, namely ${{R}_{min}}$, ${{R}_{max}}$ and $C$. The value of $C$ is set to 0.3 as given by [15]. In this section, we focus on parameter value selection to maximize network lifetime. First, we examine the effect of ${{R}_{max}}$ on network lifetime. Figure. 7 shows the impact of ${{R}_{max}}$ on network lifetime for different values of ${{R}_{max}}$ value and the result is shown on in.

We set the value of ${{R}_{min}}$ to 30 m and vary the value of ${{R}_{max}}$ from 30 m, 50 m, 60 m, 70 m and 80 m. The best result was reached when the value of ${{R}_{max}}$ is 70 m. For ${{R}_{max}}$= 30 m, the proposed method works as equal clustering (${{R}_{max}}$=${{R}_{min}}$) and as we increase the value of ${{R}_{max}}$, network lifetime increases significantly. When ${{R}_{max}}$ is greater than 70 m, lifetime decreases because the number of clusters decreases, which implies an increased intra-cluster communication load on the CH, thus resulting in increased energy dissipation which reduces overall network lifetime.

Next, we study the impact of ${{R}_{min}}$ on network lifetime. ${{R}_{min}}$ is the minimum threshold value imposed on the cluster range. When the cluster range is too small, it produces a large number of clusters, increasing the number of packet transmissions in the network and energy consumption, thus reducing network lifetime. Fig. 8 shows the impact of different values of ${{R}_{min}}$ on network lifetime. We set ${{R}_{max}}$ to 70 m and change the value of ${{R}_{min}}$ from 30 m, 40 m,50 m and 60 m. Network lifetime is seen to vary with ${{R}_{min}}$ and the optimum value lies in between 40 m and 50 m.

Selection of relay

In this section, we evaluate the selection of relay CH and its impact on network lifetime. As stated earlier, relay selection is application-specific. Maximizing network lifetime requires a relay with the maximum chance value. To minimize network latency we must choose the relay with the shortest distance from the sink. Figure 9 shows simulation results for both approaches, and clearly shows that selecting the relay with the maximum chance value significantly increases the network lifetime because the increased hop count increases the number of packets received and transmitted. But, it results in a fair load distribution as the load is distributed through the most efficient path. So, if we want the network to be delay-sensitive then we must choose the relay with the shortest distance from the sink. The problem with this approach is that the CHs with the shortest distance to sink are heavily loaded. As seen in Fig. 9, under such conditions, the nodes die faster compared to the chance-based approach.

Comparison: Network Scenario-I

The reference scenario consists of 100 randomly deployed nodes spread over a network measuring 200m × 200m. The sink is positioned at a location (100 m, 210 m) and the rest of the network parameters are set as specified in Table-II. We compare the proposed method with the LEACH, Multihop-LEACH and UCR. The maximum and minimum clustering ranges are respectively set to 70 m and 40 m respectively for our proposed method.

The maximum clustering range is set to 65 m for UCR, as we found it to be the most promising configuration and, except for LEACH, the remaining three approaches can send their data packets to the sink using multi-hop routing. First, we compare the network lifetimes of all four approaches. Figure 10 shows the distribution of live nodes with respect to the number of rounds until LND. The proposed method is more stable than the others because sensor node death begins later and continues linearly.

The second comparison is based on the metrics FND, HNA and LDA. Figure 11 shows a detailed comparison of the three metrics for all four approaches. As stated earlier, FND and HNA are the two most important factors if network lifetime is taken into account. As shown in Fig. 11, the proposed method outperforms the three other methods in terms of FND and HNA. LEACH performs most poorly due to the probabilistic approach in clustering. The Multihop-LEACH approach shows little improvement over LEACH as it uses multi-hop routing to forward data packets.

The figure clearly shows that the unequal clustering approach outperforms equal clustering because the unequal approach mitigates the excess loading on those nodes that are near the sink and it distributes the load evenly across the network. However, the proposed method shows quite an improvement over UCR, because it considers the nodes’ remaining energy, the number of neighbors and the average distance to the neighbors to calculate the chance value during the selection of CH, whereas CH selection is energy based probabilistic affair for UCR. Furthermore the dynamic clustering approach creates more stable clusters and chance-based relay selection distributes the relay load more precisely.

The third comparison is based on the average number of clusters per round for each method (see Fig. 12). LEACH, Multihop-LEACH and UCR generate a constant number of clusters until the first node dies. But the number of clusters in our proposed approach increases up to the point at which the clustering range equals ${{R}_{min}}$. It then generates a nearly constant number of clusters until the first node dies. UCR and the proposed method have a large number of clusters per round compared to LEACH and Multihop-LEACH because the unequal clustering approach creates smaller clusters around the sink to distribute the network’s relay load. Moreover, the proposed approach creates more clusters per round because it assigns a lower cluster range to nodes with low chance values, whereas the cluster range is only a factor of distance in UCR.

The fourth comparison is based on average energy consumption by a node in clustering and data transmission (see Fig. 13). The clustering process is similar in the case of LEACH and Multihop-LEACH, so they consume nearly equal amounts of energy in the clustering process. The energy-based probabilistic approach of UCR results in lower energy consumption for clustering. But the fuzzy-based CH selection of the proposed approach consumes the minimum amount of energy in the clustering process. Similarly, LEACH consumes more energy for data transmission because of its direct communication model. The multi-hop communication of the other three approaches is more energy efficient for data transmission, but are still less efficient than the chance-based relay selection of the proposed approach.

Comparison: Network Scenario-II

Network scenario-II uses the same number of nodes randomly deployed over the same network dimension in scenario–I. The only change is that the sink is located at the center of the network, i.e. at (100 m, 100 m). The remaining network parameters are identical to scenario-I. By changing the location of the sink, the values of ${{R}_{min}}$ and ${{R}_{max}}$ must be adjusted, and ${{R}_{min}}$ and ${{R}_{max}}$ are respectively changed to 20m and 50m accordingly.

The simulation results for this scenario are as follows. First, we compared the network lifetime until the half of the node remain alive. Figure 14 shows the distribution of live nodes with respect to the number of rounds until LND. The figure shows a significant improvement in network lifetime compared to scenario-I. By positioning the sink at the center of the network, less energy to is required to communicate with the sink and there are many CHs which can communicate to the sink directly. Again, the proposed method significantly outperforms the other three methods.

The second comparison is based on the metrics FND, HNA and LDA. Figure 15 shows a detailed comparison of the three metrics for all four approaches. The proposed method provides the best performance for the FND and HNA metrics. Compared to scenario-I, the value of metrics FND, HNA and LDA increases due to the location of the sink. LEACH provides the poorest performance in this scenario as well due to its use of a probabilistic approach for clustering. The Multihop-LEACH approach shows little improvement over LEACH as it uses multi-hop routing to forward the data packet. But the unequal clustering approach clearly outperforms LEACH and Multihop-LEACH, which strongly supports the use of unequal clustering in WSNs. However, the proposed method shows quite an improvement over UCR. In scenario-II, the differences between the results obtained with the four approaches are less significant than in scenario-I because more CHs can directly transmit their data to the centrally-located sink, thus diminishing the advantage of multi-hop communication over direct communication.

The third comparison is based on the average number of clusters per round (see Fig. 16). Compared to scenario-I, LEACH and Multihop-LEACH have a smaller average number of clusters because these approaches prolong network lifetime from the point at which the first node dies. Also, these approaches generate a constant number of clusters until the first node dies, after which cluster numbers are reduced as nodes continue to die. However, in the proposed approach, the number of clusters remains relatively stable, which shows the method’s adaptability to change.

The fourth comparison is based on average node energy consumption in clustering and data transmission. Figure 17 displays the average energy dissipated in cluster setup and data transmission for scenario-II. But again, the fuzzy based CH selection of the proposed approach consumes the minimum amount of energy in the clustering process. Compared to scenario –I, all four approaches consume less energy in data transmission because the central location of the sink diminishes the advantage of multi-hop communication over direct communication. But again, the chance-based relay selection of the proposed approach consumes the minimum amount of energy in data transmission.

Comparing scenario-I with scenario-II, we see that moving the sink further from the center of the network significantly increases the difference in results between the proposed approach and the other three compared algorithms.

Conclusion

We propose a load-balanced clustering algorithm using fuzzy logic with distributed self-organization for the non-uniform distribution of WSNs. The method seeks to maximize sensor life by evenly distributing the workload through selecting the most efficient node as CH. The range adjustment of the proposed method creates an optimal configuration of clusters and the relay selection creates a stable transmission route. Simulation results show the proposed method outperforms traditional clustering approaches, is realistic, and significantly improves network lifetime.

This study relies on several assumptions which provide scope for further studies. Specifically, we assume that the distance between any pair of sensors is calculated on the basis of received signal strength. However, because of the multi-path fading effect one cannot guarantee such a relationship exists between distance and received signal strength. Future work will extend/modify the proposed approach to deal with these limitations.

References

  1. Glaser, Steven D., et al. "Sensor technology innovation for the advancement of structural health monitoring: a strategic program of US-China research for the next decade." Smart Structures and Systems 3.2 (2007): 221-244.
    doi: 10.12989/sss.2007.3.2.221
  2. Akyildiz, Ian F., et al. "Wireless sensor networks: a survey." Computer networks 38.4 (2002): 393-422.
    doi: 10.1016/S1389-1286(01)00302-4
  3. Patel, M., & Wang, J. (2010). "Applications, challenges, and prospective in emerging body area networking technologies." Wireless Communications, IEEE, 17(1), 80-88.
    doi: 10.1109/MWC.2010.5416354
  4. Wenjie, C., Lifeng, C., Zhanglong, C., & Shiliang, T. (2005, June). "A realtime dynamic traffic control system based on wireless sensor network." In Parallel Processing, 2005. ICPP 2005 Workshops. International Conference Workshops on (pp. 258-264). IEEE.
    doi: 10.1109/ICPPW.2005.16
  5. Oliveira, L. M., & Rodrigues, J. J. (2011). "Wireless sensor networks: a survey on environmental monitoring." Journal of communications, 6(2), 143-151.
    doi: 10.4304/jcm.6.2.143-151
  6. Chong, C. Y., & Kumar, S. P. (2003). "Sensor networks: evolution, opportunities, and challenges." Proceedings of the IEEE, 91(8), 1247-1256.
    doi: 10.1109/JPROC.2003.814918
  7. A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, (). "Wireless sensor networks for habitat monitoring," In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pp. 88-97, September 2002.
    doi: 10.1145/570738.570751
  8. Younis, Ossama, Marwan Krunz, and Srinivasan Ramasubramanian. "Node clustering in wireless sensor networks: Recent developments and deployment challenges." Network, IEEE 20.3 (2006): 20-25.
    doi: 10.1109/MNET.2006.1637928
  9. Abdellaoui, Said El, et al. "Increasing network lifetime in an energy–constrained wireless sensor network." International Journal of Sensor Networks 13.1 (2013): 44-56.
    doi: 10.1504/IJSNET.2013.052730
  10. Krishnamachari, Bhaskar, Deborah Estrin, and Stephen Wicker. "The impact of data aggregation in wireless sensor networks." Distributed Computing Systems Workshops, 2002. Proceedings. 22nd International Conference on. IEEE, 2002.
    doi: 10.1109/ICDCSW.2002.1030829
  11. Tripathy, Asis Kumar, and Suchismita Chinara. "Comparison of residual energy-based clustering algorithms for wireless sensor network." ISRN Sensor Networks 2012 (2012).
    doi: 10.5402/2012/375026
  12. Pal, V., Singh, G., & Yadav, R. P. (2012). "SCHS: Smart cluster head selection scheme for clustering algorithms in wireless sensor networks." Wireless Sensor Network, 2012, 4, 273-280.
    doi: 10.4236/wsn.2012.411039
  13. Soro, Stanislava, and Wendi B. Heinzelman. "Prolonging the lifetime of wireless sensor networks via unequal clustering." Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International. IEEE, 2005.
    doi: 10.1109/IPDPS.2005.365
  14. Li, C.F.; Ye, M.; Chen, G.H.; Wu, J. "An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks. "Proceedings of the 2nd IEEE International Conference on Mobile Ad-hoc and Sensor Systems Conference (MASS), Washington, DC, 7– 10 November 2005; pp. 596–604.
    doi: 10.1109/MAHSS.2005.1542849
  15. Chen, Guihai, et al. "An unequal cluster-based routing protocol in wireless sensor networks." Wireless Networks 15.2 (2009): 193-207.
    doi: 10.1007/s11276-007-0035-8
  16. Mao, Song, et al. "An improved fuzzy unequal clustering algorithm for wireless sensor network." Communications and Networking in China (CHINACOM), 2011 6th International ICST Conference on. IEEE, 2011.
    doi: 10.1109/ChinaCom.2011.6158157
  17. Dutta, R., Gupta, S., & Das, M. K. (2014). "Low-Energy Adaptive Unequal Clustering Protocol Using Fuzzy c-Means in Wireless Sensor Networks." Wireless Personal Communications, 79(2), 1187-1209.
    doi: 10.1007/s11277-014-1924-7
  18. Gupta, Indranil, Denis Riordan, and Srinivas Sampalli. "Cluster-head election using fuzzy logic for wireless sensor networks." Communication Networks and Services Research Conference, 2005. Proceedings of the 3rd Annual. IEEE, 2005.
    doi: 10.1109/CNSR.2005.27
  19. Kim, Jong-Myoung, et al. "CHEF: cluster head election mechanism using fuzzy logic in wireless sensor networks." Advanced communication technology, 2008. ICACT 2008. 10th international conference on. Vol. 1. IEEE, 2008.
    doi: 10.1109/ICACT.2008.4493846
  20. Bagci, H., & Yazici, A. (2010, July). "An energy aware fuzzy unequal clustering algorithm for wireless sensor networks." In Fuzzy Systems (FUZZ), 2010 IEEE International Conference on (pp. 1-8). IEEE.
    doi: 10.1109/FUZZY.2010.5584580
  21. Bagci, Hakan, and Adnan Yazici. "An energy aware fuzzy approach to unequal clustering in wireless sensor networks." Applied Soft Computing 13.4 (2013): 1741-1749.
    doi: 10.1109/FUZZY.2010.5584580
  22. Sert, S. A., Bagci, H., & Yazici, A. (2015). "MOFCA: Multi-objective fuzzy clustering algorithm for wireless sensor networks." Applied Soft Computing, 30, 151-165.
    doi: 10.1109/FUZZY.2010.5584580
  23. Liu, X. (2012). "A survey on clustering routing protocols in wireless sensor networks." Sensors, 12(8), 11113-11153.
    doi: 10.3390/s120811113
  24. Heinzelman, Wendi Rabiner, Anantha Chandrakasan, and Hari Balakrishnan. "Energy-efficient communication protocol for wireless microsensor networks." System Sciences, 2000. Proceedings of the 33rd Annual Hawaii International Conference on. IEEE, 2000.
    doi: 10.1109/HICSS.2000.926982
  25. Heinzelman, Wendi B., Anantha P. Chandrakasan, and Hari Balakrishnan. "An application-specific protocol architecture for wireless microsensor networks." Wireless Communications, IEEE Transactions on 1.4 (2002): 660-670.
    doi: 10.1109/TWC.2002.804190
  26. Voigt, T., Dunkels, A., Alonso, J., Ritter, H., & Schiller, J. (2004, June). "Solar-aware clustering in wireless sensor networks." In Computers and Communications, 2004. Proceedings. ISCC 2004. Ninth International Symposium on (Vol. 1, pp. 238-243). IEEE.
    doi: 10.1109/ISCC.2004.1358411
  27. Biradar, R. V., Sawant, S. R., Mudholkar, R. R., & Patil, V. C. (2011). "Multihop routing in self-organizing wireless sensor networks." IJCSI International Journal of Computer Science Issues, 8(1), 155-164.
  28. Xiangning, Fan, and Song Yulin. "Improvement on LEACH protocol of wireless sensor network." Sensor Technologies and Applications, 2007. SensorComm 2007. International Conference on. IEEE, 2007.
    doi: 10.1109/SENSORCOMM.2007.4394931
  29. Ran, G., Zhang, H., & Gong, S. (2010). "Improving on LEACH protocol of wireless sensor networks using fuzzy logic." Journal of Information & Computational Science, 7(3), 767-775.
  30. Younis, O., & Fahmy, S. (2004). "HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks." Mobile Computing, IEEE Transactions on, 3(4), 366-379.
    doi: 10.1109/TMC.2004.41
  31. Younis, O., & Fahmy, S. (2004, March). "Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach." In INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies (Vol. 1). IEEE.
    doi: 10.1109/INFCOM.2004.1354534
  32. Patwari, Neal, Joshua N. Ash, Spyros Kyperountas, Alfred O. Hero III, Randolph L. Moses, and Neiyer S. Correal. "Locating the nodes: cooperative localization in wireless sensor networks." Signal Processing Magazine, IEEE 22, no. 4 (2005): 54-69.
    doi: 10.1109/MSP.2005.1458287
  33. C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: a scalable and robust communication paradigm for sensor networks, " Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking,Boston, MA, pp. 56-67, August 2000.
    doi: 10.1145/345910.345920
  34. Guillaume, S. (2001). "Designing fuzzy inference systems from data: an interpretability-oriented review." Fuzzy Systems, IEEE Transactions on, 9(3), 426-443.
    doi: 10.1109/91.928739
  35. Wang, Li-Xin. A course in fuzzy systems. Prentice-Hall press, USA, 1999.
  36. Runkler, Thomas A. "Selection of appropriate defuzzification methods using application specific properties." Fuzzy Systems, IEEE Transactions on 5.1 (1997): 72-79.
    doi: 10.1109/91.554449
  37. Handy, M. J., Marc Haase, and Dirk Timmermann. "Low energy adaptive clustering hierarchy with deterministic cluster-head selection." Mobile and Wireless Communications Network, 2002. 4th International Workshop on. IEEE, 2002.
    doi: 10.1109/MWCN.2002.1045790

Refbacks

  • There are currently no refbacks.


Copyright © 2011-2017  AUSMT   ISSN: 2223-9766