Medium-Contention Based Energy-Efficient Distributed Clustering (MEDIC) for Wireless Sensor Networks

Abstract

In this paper, we utilize clustering to organize wireless sensors into an energy-efficient hierarchy. We propose a Medium-contention based Energy-efficient DIstributed Clustering (MEDIC) scheme, through which sensors self-organize themselves into energy-efficient clusters by bidding for cluster headship. This scheme is based on a new criterion that can be used by each sensor node to make a distributed decision on whether electing to be a cluster head or a non-head member, which is a fully distributed approach. Although MEDIC uses only local information, it achieves better performance in terms of effective lifetime and its Data/Energy Ratio is 25% higher than native LEACH (Low-Energy Adaptive Clustering Hierarchy), which relies on other routing algorithms to access global information. A complementary exponential data correlation model is also introduced to simulate different data aggregation effect.

1. Introduction

A wireless sensor network (WSN) can be thought of as an ad hoc network consisting of sensors linked by a wireless medium to perform distributed sensing tasks. Thanks to recent advances in semiconductor technology, the sensors nodes can be made small in size and cheap for mass production. Due to their low-power antenna and limited energy reserves in the form of chemical battery, the sensor nodes can communicate with each other in a short range and work for a relatively short duration.

WSNs share many communication technologies with ad hoc networks, but there are some vital differences such as dense deployment and energy constraint [1], thus the protocols developed for traditional wireless ad hoc networks are not necessarily well-suited to the unique features of WSNs. When a wireless sensor may have to operate for a relatively long duration on a tiny battery, energy efficiency becomes a major concern.

A variety of “power-aware” routing protocols have been proposed to address this problem. In one school of thought [2–4], the traditional Shortest Path First strategy is replaced by the Least Energy First routing, i.e., a multihop route is preferred to a single-hop one if only the multiple short-distance relays cost less energy than a single long-distance transmission. For example, “Minimum Transmission Energy” (MTE) routing [3], [4] was proposed in place of traditional “minimum hops routing”. Another school of thought is that nodes are clustered so that a hierarchy is formed [5–7]. Based on the observations on cellular networks [8], it would be advisable to partition the nodes into clusters for reasons such as spatial reuse, less update cost, less routing information, and less data transmission.

Another dispute in clustering research is whether a cluster head can be elected within each cluster. Some researchers [6], [7], [9] argue that it is unreasonable to have a cluster head because every node has a similar energy constraint and the cluster head will consume energy much faster. Their methodology breaks the information exchange is achieved by demand-based operations. This approach does have some advantage when the traffic is mostly within the cluster; however, when the major traffic in WSN is directed from the sensor nodes to the base station, i.e., of the intercluster type, the headless structure suffers from cumbersome intercluster information exchange.

On the other hand, the extra burden of the cluster head can be mitigated by rotating the headship among the members. The rotation can also take advantage of the relaxation effect [10], which indicates frequently reducing the current drawn from the battery enables the battery to recover a portion of its lost capacity and hence lengthens the battery lifetime. In addition, the cluster head can perform data fusion and reduce the data sent back to the base station. LEACH (Low-Energy Adaptive Clustering Hierarchy) [11], an example of the latter, school, can extend network lifetime by an order of magnitude compared with general-purpose multihop approaches. In conclusion, the characteristics of WSN prefer a hierarchical structure with cluster heads.

This paper builds on the work described in [12] by giving a detailed description and analysis of Medium-contention based Energy-efficient Distributed Clustering (MEDIC). The rest of this paper is organized as follows. Section II reviews LEACH and wireless medium access. Section IV-A introduces the data correlation model that our research is based on. In Section IV, we make data-centric analysis of energy consumption in WSN and propose a new criterion that MEDIC bases the self-electing decision on. MEDIC is described in Section V and the simulations are given in Section VI. Section VII concludes this paper.

2. Related Work

In this section, we provide some preliminaries needed for further discussion.

2.1. Leach

LEACH uses the CDMA-TDMA hybrid communication scheme. Each cluster has its own Spread Spectrum code so that the interference between clusters is minimized. For intracluster communications, TDMA slots are assigned for each member to minimize media contention. The operation of LEACH is divided into rounds. At the beginning of each round, cluster heads are elected and other nodes join them as members so that N nodes are partitioned into c clusters. When a cluster is formed, the cluster head creates and broadcasts a time schedule to its members. As shown in Fig. 1, each member is assigned a time slot per frame to send its data to its cluster head, and then the cluster head performs data aggregation and sends the resulting data back to the base station. Compared with multihop routing schemes, LEACH shows an outstanding energy efficiency, which is referred to as clustering energy gain in the following.

Figure 1

A generic MAC.

However, the cluster formation in LEACH is based on global information. To access such information, other routing schemes are required. In this sense, LEACH is only a semi-distributed protocol for WSN. Another problem with LEACH is the random head election that cannot guarantee that the desired number of cluster heads be elected or the elected heads be evenly positioned. In this paper, we are concerned about optimizing the cluster formation using only local information. The intuition behind the proposed Medium-contention based Energy-efficient Distributed Clustering (MEDIC) is using medium contention to keep the cluster size within an ideal range. By exploiting medium contention to simulate an auction for the cluster headship, we also eliminate the need for location information.

The problems of LEACH are also addressed by other researchers. HEED [13] corrects the problem that none or not enough cluster heads are elected by doubling the probability of electing to be a cluster head for those nodes that are not covered by any cluster heads. In [14], Qin and Zimmermann proposed a voting-based clustering algorithm (VCA) for energy-efficient data dissemination in quasi-stationary sensor networks. Their approach lets sensors vote for their neighbors to elect suitable cluster heads. Connectivity based k-hop clustering [15] proposed to combine two known approaches into a single clustering algorithm which considers connectivity as a primary criterion and lower ID as a secondary criterion for selecting cluster heads. Their clustering goal is to minimize the number of clusters, which results in dominating sets of smaller sizes (this is important for applications in broadcasting and Bluetooth formation). Bandyopadhyay and Coyle in [16] extend clustering to multiple levels, generating a hierarchy of clusterheads and observed that the energy savings increase with the number of levels in the hierarchy. They also used stochastic geometry to derive solutions for the values of parameters of our algorithm that minimize the total energy spent in the network when all sensors report data through the cluster heads to the processing center. Weighted Clustering Algorithm (WCA) [17] took into consideration the ideal degree, the transmission power, the mobility, and the battery power of a mobile node and tried to keep the number of nodes in a cluster around a pre-defined threshould to facilitate the optimal operation of the medium access control (MAC) protocol, The on-demand execution of WCA aimed to maintain the stability of the network, thus lowering the computation and communication costs associated with it. In [18], Two-Phase Clustering (TPC) partitions the network into clusters in phase I, each with a cluster head, forming a direct link between the cluster member and the cluster head. In phase II, each cluster member searches for a neighbor closer than the cluster head within the cluster to set up an energy-saving data relay link. The sensors use either the direct link or the data relay link for their sensed data forwarding depending on the requirements specified by the users or applications. Other work on clustering also tries to distribute the clustering formation [19], [20]. Our approach is independent and orthogonal to these advances in clustering and thus may be used to further improve the energy efficiency.

2.2. Review of Wireless Medium Access

In this paper, we consider a generic MAC that is compatible with the basic access mechanism described in 802.11 DCF [21]. As illustrated in Fig. 1, after the channel is sensed idle for greater than or equal to a DIFS (Distributed InterFrame Spacing) period, the transmitting node generates a random backoff timer chosen uniformly from the range [0, w-1], where w is the size of the contention window. In a binary exponential backoff scheme, the value of w is reset to CW _min after each successful transmission, and doubled after each unsuccessful transmission, up to CW _max (maximum contention window). The backoff timer is decremented as long as the channel is sensed idle, stopped when a transmission is detected, and reactivated when the channel is sensed idled again for a DIFS period. After the backoff timer reaches zero, the node starts transmission.

The collisions of packets in the contention-based MAC generally degrade channel utilization and increase energy consumption, which motivates establishing transmission schedules to allow nodes to communicate without collisions. In NAMA (Node Activation Multiple Access) [22] and TRAMA (Traffic-Adaptive Medium Access protocol) [23], a distributed election scheme is used to determine which node can transmit at a particular time slot. From this point of view, LEACH is also a schedule-based scheme, in which cluster formation is a random-access period to establish a scheduled-access period collision-free (Fig. 3).

2.3. Auction Theory

Auctions are heavily studied as a market clearing mechanism to equate demand and supply [24]. In WSN, the cluster headship is a scarce resource, and hence, it would help to view the process of electing a cluster head among nodes in WSNs as an auction for the headship. Auctions can be classified according to several distinct criteria. For example, they can be classified into open and sealed-bid auctions, based on whether all bids are publicly observable. Open auctions can be further classified into ascending and descending price auction. The ascending auction, also called English auction, starts at a low price and bids have to be increasing. The ascending stops when no bidder is willing to increase his bid above the highest standing bid. The bidder with the highest bid wins the auction and pays the highest bid. The English auction is the best-known format of auctions, its drawback is that a bidder can take a dominating strategy to win the bid, that is as long as his bid is higher than the second highest bid, this bidder can win the bid, even when the highest bid is still much lower than the true value of the auctioned object. In comparison, the descending price auction, also known as Dutch auctions, starts at a high price that continuously decreases on an automated clock. The auction ends when one of the bidders stops the clock. This bidder wins the object and pays the price at which the clock stopped. The aforementioned dominating strategy cannot be used in Dutch auctions, therefore, the highest bid in the Dutch auction tends to reflect the true value of the resource. However, our interest in the Dutch auction is for another advantage—its time efficiency. Note that in the Dutch auction, the highest bidder always speaks first, and the auction ends right after its bid. On the other hand, the English auction could start with a lower bid, and when this does happen, it might take several rounds before a bidder dominates. Therefore, we design MEDIC based on the Dutch auction.

2.4. Radio Energy Consumption

The following model is adopted from [11] where perfect power control is assumed. To transmit l bits over distance d, the sender's radio expends

$$E_{TX}(l,d)=\{\begin{array}{ll}l{E}_{elec}+l{\epsilon }_{f_s}{d}^2& d<d_0\\ l{E}_{elec}+l{\epsilon }_{mp}{d}^4& d\ge d_0\end{array}$$

(1)

and the receiver's radio expends

$$E_{RX}(l,d)=l{E}_{elec}.$$

(2)

E _elec is the unit energy consumed by the electronics to process one bit of message, ε _fs and ε _mp are the amplifier factor for free-space and multi-path models, respectively, and d₀ is the reference distance to determine which model to use. The values of these communication energy parameters are set as in Table 1.

Table 1

Communication Energy Parameters

Name	Value
d 0	86.2m
E elec	50nJ/bit
E DA	5nJ/bit
ε fs	10pJ/bit/m2
C mp	0.0013pJ/bit/m4

3. Problems and Motivations

Random election has been widely used in algorithms for wireless sensor networks for its simplicity and convenience [11]. However, there are two fundamental drawbacks in random election:

Dependence on Global Information In LEACH, each node i elects itself to be a cluster head at the beginning of round r + 1 (which starts at time t) with probability P _i (t). Two ways were used to determine the self-electing probability P_i(t) in [11]. If all nodes are assumed to start with an equal amount of energy, P_i(t) is given by

$$P_i(t)=\{\begin{array}{ll}\frac{c}{N-c^{\ast }(rmod\frac{N}{c})}& :C_i(t)=1\\ 0& :C_i(t)=0\end{array},$$

(3)

where c is the desired number of clusters and C_i(t) is the indicator function determining whether or not node i has been a cluster head in the most recent (r mod (N/c)) rounds. The more general estimate of P_i(t) is given by

$$P_i(t)=min\{\frac{E_i(t)}{E_{total}(t)}c,1\},$$

(4)

where E_i(t) is the current energy (i.e. remaining battery capacity) of node i and

$$E_{total}(t)=\sum _{i=1}^N{E}_i(t).$$

(5)

Essentially, N in (3) and E_total in (4) are global information, which is only accessible via other routing schemes.

High Variation Although random decision generally strengthens the robustness by avoiding sticking to a single choice, a high variation in the decision may shift the decision too far away from the optimal range. For example, suppose (4) is used and all nodes have an equal amount of energy, if N nodes want to elect c heads among them, then the self-electing probability for each node is

$$p-\frac{c}{N}$$

(6)

Then the probability of “n heads are elected” is

$$Pr(n\text{\hspace{0.5em}elected heads})=(\begin{array}{c}N\\ n\end{array})p^n(1-p{)}^{N-n}$$

(7)

The distribution of the number of elected heads is listed in Table 2. Obviously, too few (Fig. 2(c)) and too many (Fig. 2(d)) elected heads would damage the energy efficiency.

Figure 2

100 nodes elect 5 heads (Heads marked by pentagrams). (a) Five heads are elected and evenly distributed. (b) Five heads are elected and clump in the right semicircle. (c) Only one head is elected. (d) Nine heads are elected.

Figure 3

Time line showing LEACH's frame structure.

Table 2

Outcome of 100 Nodes Electing 5 Heads

n: number of elected heads	Pr (n elected heads)
0	0.0059
1	0.0312
2	0.0812
3	0.1396
4	0.1781
5	0.1800
6	0.1500
7	0.1060
8	0.0649
9	0.0349
≥10	0.0341

Moreover, in the case of “no elected head” whose probability is listed in row 1, all the nodes have to communicate directly with the base station, in which case all the clustering energy gain is lost. When the number of elected heads is too few, for example, only one head is elected, the head may be exhausted by the tremendous data sent to it. In such cases, the energy efficiency is tremendously compromised.

Another problem introduced by the random head selection is that the sensor locations are not taken into consideration. Obviously, the even layout of heads would favor energy efficiency (Fig. 2(a)). When heads are randomly selected as in LEACH, elected heads sometimes clump together as shown in Fig. 2(b), which leads to unnecessary energy waste.

4. Optimal Clustering

In this section, we first introduce a data correlation model, and then based on this model, make data-centric analysis of energy consumption in WSN. A new criterion is proposed for clustering, which is the theoretical basis of Medium-contention based Energy-efficient Distributed Clustering (MEDIC). For easy reference, the variables used in the following discussion are listed in Table 3.

4.1. Data Correlation Model

The data collected by neighboring sensors have a lot of redundancy, thus, [11] assumes a perfect data correlation that all individual signals from members of the same cluster can be combined into a single representative signal. Nevertheless, this assumption cannot hold when the cluster size increases to some extent. Therefore, we develop a complementary exponential data correlation model based on the observations in distributed data compression [25], [26].

Considering the phenomenon of interest as a random process, the correlation between data collected by two sensors is generally a decreasing function of the distance r between them. After the data aggregation removes most of the redundancy, the residue can be assumed to be an increasing function of r. Based on the above observation, the data aggregation effect is modeled as below.

Table 3

Table of Variables

Name	Definition
N	the total of nodes
c	the desired number of clusters
k	the actual number of clusters
R c	cluster radius
α	data correlation exponent
J CH	energy cost of a cluster head
J CM	energy cost of a cluster member
J total	energy cost of the whole network
E(i)	the energy level of the ith neighbor
B(i)	the number of neighbors of the ith neighbor

Suppose there are M _k non-head members in cluster k(k = 1,2,3, …, c), the ith member (i = 1,2,3, …, M _k ) collects l bits and sends them back to its head k at distance r _ki , the head expends 2lE _DA Joules on the data aggregation of the 2l bits (l bits collected by itself and another l bits by its ith member), where E _DA is set as 5nJ/bit as in [11] and listed in Table 1. The resulting data is assumed of l(1 + η _ki ) bits, where η _ki is data aggregation residue ratio and assumed to be complementary exponential, specifically,

$${\eta }_{ki}=1-e^{-\alpha r_{ki}},0<\alpha <1.$$

(8)

where α is a small positive real number whose magnitude depends on specific phenomenon of interest. For example, the light, acoustic, seismic, and thermal signals often show a strong correlation at short distance, and thus, α will have smaller values for such data. Since η is a monotonically decreasing function of α and r, η approaches zero for smaller α and r. This model can approach the perfect-data-correlation assumpion in [3], [4] by increasing α, thus, different scenarios can easily be set up by varying α.

4.2. Problem Formulation

Clustering has been widely used in pattern recognition, and we use it to obtain the energy-efficient organization for WSN. From the data-centric view, the data collected by a node can be sent back directly to the base station or relayed by a cluster head. The first case occurs if this node is a cluster head; the data collected by head k is data-aggregated (with the data collected by its members) and sent back to the base station. Thus, the energy cost for each bit of data collected by head k is

$$J_{CH(k)}=E_{DA}+E_{elec}+{\epsilon }_{mp}{d}_k^4,$$

(9)

where d _k is the distance between head k and the base station.

For the second case, consider non-head member ki, the ith sensor in cluster k, with distance r _ki to its cluster head, member ki sends its data to head k, and then head k performs data aggregation on the data and sends the resulting data to the base station. Thus, the energy cost for each bit of data collected by non-head member ki is

$$J_{CM(ki)}=E_{elec}+{\epsilon }_{f_s}{r}_{ki}^2+E_{elec}+E_{DA}+\eta (r_{ki})(E_{elec}+{\epsilon }_{mp}{d}_k^4),$$

(10)

where η(r _ki ) is the data aggregation residue ratio introduced in Section IV-A.

Considering all c clusters, the overall cost is

$$J_{total}=\sum _{k=1}^c\{J_{CH}(k)+\sum _{i=1}^{Mk}{J}_{CM}(ki)\},$$

(11)

where M _k is the number of non-head members in cluster k.

Taking E[J _total ] the expected value of the overall energy cost as the objective function, the original problem is translated into an objective function clustering. If a central control scheme is possible, an iterative algorithm can be run at the base station to minimized E[J _total ]. For example, Fuzzy c-Means is utilized in [27] to minimize a Euclidean-distance-based functional representing the energy cost in Wireless Personal Area Networks. However, since WSNs are working in ad hoc mode, the clustering decision must be distributed to each sensor node. Thus, our goal is using only local information to achieve energy-efficient clustering.

4.3. Influence Range

When a node finds no cluster head around, it should naturally elect to be a cluster head. However, if a node is close to a cluster head, there could be some energy gain or loss if it joins that cluster. In the following, we will discuss how a node decided to be a cluster head when it finds a cluster head in its communication range. The energy gain diminishes when the distance between the non-head member and the head increases. Consequently, the energy gain approaches zero at some critical distance, termed as influence range. To determine the influence range, consider a node i with a head k at distance r. The node could choose to be a non-head member or a head, which would consequently cost J _CM or J _CH as in (10) and (9). Naturally, the decision should be based on the comparison of J _CM and J _CH as

$$J_{CM}\underset{\underset{{\displaystyle CM}}{{\displaystyle >}}}{\overset{\stackrel{{\displaystyle CH}}{{\displaystyle <}}}{\hspace{0.17em}}}{J}_{CH},$$

(12)

i.e., the decision rule for each sensor is:

$$\text{Node\hspace{0.5em}}i\text{\hspace{0.5em}elects to be}\{\begin{array}{ll}\text{a non-head member if}& J_{CM}<J_{CH}\\ \text{a cluster head if}& J_{CM}>J_{CH}\end{array}$$

(13)

We call this criterion as the local energy efficiency criterion, because it is based on only the local information. Substituting (9) and (10) into (12), we obtain

$$\begin{array}{rl}{E}_{elec}+{\epsilon }_{f_s}{r}_{ik}^2+E_{elec}+E_{DA}& +\eta (r_{ik})(E_{elec}+{\epsilon }_{mp}{d}_k^4)\\ & \underset{CM}{\overset{CH}{\gtrless }}{E}_{DA}+E_{elec}+C_{mp}{d}_i^4.\end{array}$$

(14)

The influence range can be obtained by equating two sides though a closed form may be unavailable. Obviously, the cluster radius R _c has to be much smaller than the influence range because the energy gain is so low at the outer ring that a new cluster can be formed. Although this criterion is too complex to be used in real applications, it promotes using R _c instead of c as the clustering objective parameter to guide the election. Denote the areas occupied by the whole WSN and the cluster by S _N and S _c respectively,

$$c\approx \frac{S_N}{S_c}.$$

(15)

Assume S _N and S _c are both circular, R _c is related to c by

$$c-\frac{\pi R^2}{\pi R_c^2}={\left(\frac{R}{R_c}\right)}^2.$$

(16)

where R is the radius of S _N . Although it is mathematically equivalent to partition nodes into c clusters or to organize nodes into clusters with radius R _c , the former is definitely a global approach, which leads to dependence on the global information. Thus, the latter is more suitable for a distributed algorithm.

4.4. Optimal Cluster Size

As indicated in (16), it is equivalent to determine c or R _c . Here, we try to analytically determine the optimal value of c using the introduced models. LEACH can only determine a rough range C _opt ε [1, 6] for a similar 100-node network [11], while our analysis predicts the optimal value of R _c in simulation with satisfying accuracy.

The typical scenario is that N nodes are distributed uniformly in a circular region with radius R. There are c clusters with one cluster head and n-1 non-head members within each cluster. n is the average number of cluster members and related to c by

$$n\approx \cdot N/c.$$

(17)

Based on (11), the average total energy cost can be approximated by

$$\begin{array}{rl}{\dot{J}}_{total}& =c({\bar{J}}_{CH}+(n-1){\bar{J}}_{CM})\\ & =c{\bar{J}}_{CH}+(N-c){\bar{J}}_{CH}\end{array}$$

(18)

where ${\bar{J}}_{CH}$ and ${\bar{J}}_{CM}$ are the average energy cost for the cluster head and non-head member respectively.

Following (9) and (10),

$${\bar{J}}_{CH}=E_{DA}+E_{elec}+{\epsilon }_{mp}E[d^4],$$

(19)

$${\bar{J}}_{CM}=E_{elec}+{\epsilon }_{f_s}E[r^2]+E_{elec}+E_{DA}+E[\eta (r)(E_{elec}+{\epsilon }_{mp}{d}^4)].$$

(20)

Since all nodes are independently deployed, r and d are independent, thus, (20) can be written as

$${\bar{J}}_{CM}=E_{elec}+{\epsilon }_{f_s}E[r^2]+E_{elec}+E_{DA}+E[\eta (r)](E_{elec}+{\epsilon }_{mp}E[d^4]).$$

(21)

We estimate the expected values in (19) and (21) as follows. Assuming the cluster head is at the center of mass of the cluster,

$$\begin{array}{rl}E[r^2]& =\int {\int }_{S_c}{r}^2{\rho }_c(r,\theta )rdrd\theta \\ & ={\int }_0^{2\pi }{\int }_0^{R_c}{r}^2{\rho }_c(r,\theta )rdrd\theta \end{array}$$

(22)

Where ρ _c (r,θ) is the node distribution density. Since the nodes are assumed to be uniformly distributed, ρ _c (r,ρ) is a constant given by

$${\rho }_c=1/\pi R_c^2=c/(\pi R^2).$$

(23)

Substituting (23) and (16) into (22),

$$\begin{array}{rl}E[r^2]& -\frac{\pi {\rho }_c{R}_c^4}{2}\\ & -\frac{R^2}{2c}\end{array}$$

(24)

Similarly,

$$\begin{array}{rl}e[\eta (r)]=& \int {\int }_{Sc}(1-e^{\alpha r}){\rho }_c(r,\theta )rdr\theta \\ =& \frac{c}{\pi R^2}{\int }_0^{2\pi }{\int }_0^{R_c}(1-e^{-\alpha r})rdrd\theta \\ =& \frac{2c}{R^2}{\int }_0^{R_c}(1-e^{-\alpha r})rdr\end{array}$$

(25)

$$=1+\frac{2c}{{\alpha }^2{R}^2}(e^{-\frac{\alpha R}{\sqrt{c}}}(\frac{\alpha R}{\sqrt{c}}+1)-1)$$

(26)

$$\begin{array}{rl}E[d^4]& =\int {\int }_{S_N}|r-r_{BS}{|}^4{\rho }_N(r,\theta )rdrd\theta \\ & =\frac{1}{\pi R^2}{\int }_0^{2\pi }{\int }_0^R(r^2+r_{BS}^2-2r{r}_{BS}cos(0-{\theta }_{BS}){)}^{2}rdrd\theta \end{array}$$

(27)

Since E[d⁴] is a function of R and irrelevant to c, we keep it in the further derivation.

The optimal value of c can be obtained by setting $\frac{\mathrm{\partial }{\bar{J}}_{total}}{\mathrm{\partial }c}$ to zero.

$$\begin{array}{rl}\frac{\mathrm{\partial }{\bar{J}}_{total}}{\mathrm{\partial }c}& ={\bar{J}}_{CH}-{\bar{J}}_{CM}+(N-c)\frac{\mathrm{\partial }{\bar{J}}_{CM}}{\mathrm{\partial }c}\\ & ={\epsilon }_{mp}E[d^4]-E_{elec}-{\epsilon }_{f_s}\frac{R^2}{2_c}-E[\eta (r)](E_{elec}|{\epsilon }_{mp}E[d^4])\\ & +(N-c)(-\frac{{\epsilon }_{f_s}{R}^2}{2c^2}+\frac{\mathrm{\partial }E[\eta (r)]}{\mathrm{\partial }c}(E_{elec}+{\epsilon }_{mp}E[d^4]))\end{array}$$

(28)

$$\begin{array}{rl}\frac{{\mathrm{\partial }}^2{\bar{J}}_{total}}{\mathrm{\partial }{c}^2}=& \frac{\epsilon f_s{R}^2}{2c^2}-\frac{\mathrm{\partial }E[\eta (r)]}{\mathrm{\partial }c}(E_{elec}+{\epsilon }_{mp}E[d^4])\\ & -(-\frac{\epsilon f_s{R}^2}{2c^2}+\frac{\mathrm{\partial }E[\eta (r)]}{\mathrm{\partial }c}(E_{elec}+{\epsilon }_{mp}E[d^4]))\\ & +(N-c)(\frac{\epsilon f_s{R}^2}{c^3}+\frac{{\mathrm{\partial }}^{2}E[\eta (r)]}{\mathrm{\partial }{c}^2}(E_{elec}+{\epsilon }_{mp}E[d^4]))\\ =& \frac{\epsilon f_s{R}^2}{c^2}+(N-c)\frac{\epsilon f_s{R}^2}{c^3}\\ & -2\frac{\mathrm{\partial }E[\eta (r)]}{\mathrm{\partial }c}(E_{elec}+{\epsilon }_{mp}E[d^4])\\ & +(N-c)\frac{{\mathrm{\partial }}^{2}E[\eta (r)]}{\mathrm{\partial }{c}^2}(E_{elec}+{\epsilon }_{mp}E[d^4])\end{array}$$

(29)

where $\frac{\mathrm{\partial }E[\eta (r)]}{\mathrm{\partial }c};\frac{{\mathrm{\partial }}^{2}E[\eta (r)]}{\mathrm{\partial }{c}^2}$ can be computed based on (26).

$$\frac{\mathrm{\partial }E[\eta (r)]}{\mathrm{\partial }c}=\frac{2}{{\alpha }^2{R}^2}(e^{-\frac{\alpha R}{\sqrt{c}}}(\frac{\alpha R}{\sqrt{c}}+1)-1)+\frac{e^{-\frac{\alpha R}{\sqrt{c}}}}{c}$$

(30)

$$\frac{{\mathrm{\partial }}^{2}E[\eta (r)]}{\mathrm{\partial }{c}^2}=\frac{\alpha R{e}^{-\frac{\alpha R}{\sqrt{c}}}}{2c^{5/2}}$$

(31)

Since it is impossible to solve (28) algebraically, we turn to the numerical solution. For example, the base station is located at (r _BS , θ _BS ) = (125, 0) and N − 100, R = 50m in our experiments, we can evaluate (27) as

$$E\left[d^4\right]=5.8997c+008.$$

(32)

In Fig. 4(a)(b), we plot $\frac{\mathrm{\partial }{\dot{J}}_{total}}{\mathrm{\partial }c}$ over c for α − 0.001 and α − 0.05 respectively. The corresponding C _opt can be easily obtained by setting $\frac{\mathrm{\partial }{\bar{J}}_{total}}{\mathrm{\partial }c}0$ .

$$c_{opt}=\{\begin{array}{cc}1.6569,& \text{for\hspace{0.5em}}\alpha -0.001\\ 20.2600& \text{for\hspace{0.5em}}\alpha -0.05\end{array}$$

(33)

Figure 4

Plot of $\frac{\mathrm{\partial }{\bar{J}}_{total}}{\mathrm{\partial }c}$ for N = 100, R = 50m and (r _BS , θ _BS ) = (125,0). (a) α = 0.001. (b) α = 0.05.

Note that $\frac{{\mathrm{\partial }}^2{\bar{J}}_{total}}{\mathrm{\partial }{c}^2}{|}_{c_{opt=1.6569}}=2.98E-7>0$ and $\frac{{\mathrm{\partial }}^2{\bar{J}}_{total}}{\mathrm{\partial }{c}^2}{|}_{c_{opt=20.26}}=2.51E-9>0$ , which indicates ${\bar{J}}_{total}$ is minimized at these C _opt 's. According to (16), the corresponding R _c is

$$R_c=\{\begin{array}{cc}38m& \text{for\hspace{0.5em}}\alpha -0.001\\ 11m& \text{for\hspace{0.5em}}\alpha =0.05\end{array}$$

(34)

We are also interested in the relation of N to C _opt . In Fig. 5(a)(b), we plot c _opt over N for α = 0.001 and α = 0.05 respectively. These figures show that C _opt is an increasing function of N, which indicates that the clustering objective parameter (c or R _c ) should be adjusted adaptively if N varies.

Figure 5

Plot of c _opt vs. N for R = 50m and (r _BS , θ _BS ) = (125,0). (a) α = 0.001. (b) α = 0.05.

5. Medium-contention based Energy-efficient Distributed Clustering

Medium-contention based Energy-efficient Distributed Clustering (MEDIC) is designed to replace the cluster formation occurring at the beginning of each round in LEACH. We design MEDIC based on the Dutch auction for its time efficiency. Note that in the Dutch auction, the highest bidder always speaks first, and the auction ends right after its bid. On the other hand, the English auction could start with a lower bid, and when this does happen, it might take several rounds before a bidder dominates.

In MEDIC, there is no global broadcast. As shown in Fig. 6, each node first broadcasts its vital information at the maximum radio power level so that the knowledge is spread as widely as possible. Such “maximum-power” broadcasts are not frequent in MEDIC, which helps saving energy. The vital information may include nodes' energy, location, etc., though only the energy information is needed by MEDIC. Then, each node counts its neighbors and broadcasts the number of its neighbors at an adjusted power level corresponding to the cluster radius R _c . The cluster radius R _c is an important system parameter for energy efficiency. As shown in Section IV-D, given a specific type of application, R _c is mainly determined by the node density. In MEDIC, each node should choose an appropriate R _c according to the neighbor count in its transmission range, which is a good estimator of the local density.

Figure 6

Flow chart of a node in MEDIC.

If a node's headship potential qualifies as a head compared to its neighbors', it will try to claim the headship by broadcasting locally, which can be viewed as placing a bid for the headship. A node's “neighbors” are defined as the nearby nodes within distance R _c from that node. Due to the possible contention for the headship, such bids could fail, which is indicated by the collision of “headship claims.” Using the modified MAC described below, the bidders will contend with each other until a node with satisfactory potential wins. By doing so, the head-to-be expels other possible heads in its neighborhood, and in consequence, the clusters with desired size are formed.

The headship potential is an important parameter, which replaces the self-electing probability used in native LEACH. As discussed in [11], the node's energy is important to determine its potential because the headship can be rotated among nodes by assigning more potential to the nodes with higher energy. In addition, we propose taking the number of neighbors into consideration, because the energy gain is prominent only in the neighborhood of the head as shown in Section IV-C and thus it is energy-efficient to let the node with more neighbors win the headship.

Based on these considerations, the qualification conditions are set as below. For any node, let N denote the set of its neighbors, E(i) and B(i) be the energy and the number of neighbors of the ith neighbor respectively, i ε N. The thresholds are set as the linear combination of the maximum and mean value of corresponding parameters as in (35) and (36) so that the thresholds are adapted to the current distribution of parameters and take values between the maximum and mean.

$$E_{th}\triangleq {\gamma }_{1_{i\epsilon }\mathcal{N}}^{max}E(i)+(1-{\gamma }_1{)}_{i\epsilon \mathcal{N}}^{\text{mean}}E(i)$$

(35)

$$B_{th}\triangleq {\gamma }_{2_{i\epsilon }\mathcal{N}}^{max}B(i)+(1-{\gamma }_2{)}_{i\epsilon \mathcal{N}}^{\text{mean}}B(i)$$

(36)

The conditions can be relaxed by decreasing γ₁, γ₂, where γ₁, γ₂ ε [0, 1]. Since there is no closed-form objective function, it is difficult to determine optimal γ₁, γ₂ analytically. Fortunately, our experiments show that the performance is not sensitive to the setting of γ₁, γ₂. Thus, we simply choose a smaller value for γ₁ and a larger value for γ₂ as γ₁ = 0, γ₂ = 0.8, because we want to emphasize the position condition in order to achieve energy efficiency and relax the energy condition in order to accept more nodes into the headship auction.

Depending on their conditions, the nodes classify themselves into three categories shown in Fig. 7. Each node can classify itself into one of the three categories by comparing itself to its neighbors. The nodes meeting both conditions consider themselves in Category-A, meeting one of the conditions indicates Category-B, and Category-C for the rest which fail both conditions. Note that DIFS _B = DIFS _A + CW _min in Fig. 8, Category-B bidders have to wait CW _min longer than Category-A to ascertain there are no Category-A bidders in their neighborhoods. That is, no matter which slot Category-A nodes randomly choose to send out the claim, there is no chance for a Category-B node to access the channel if there is one Category-A node in its neighborhood. The extreme case that no heads are elected is avoided by permitting Category-B bidders into the headship auction because it is impossible that there are only Category-C nodes in the neighborhood.

Figure 7

Categories of bidders.

Figure 8

The Medium Access Control used in MEDIC.

Once a node successfully sends out the “headship claim,” its neighbors must join it by sending “Request to join.” Since these requests can be eavesdropped by their neighbors, their neighbors can correspondingly correct their numbers of unclustered neighbors. If a node finds all its neighbors are clustered, it can elect to be a cluster head by sending out a “headship claim.” Those nodes outside the neighborhood of existing cluster heads cannot join any clusters. When the public channel is idle again, which indicates there is no node in its neighborhood trying to join existing clusters, another round of auction will begin until all nodes are clustered.

6. Simulations

In this section, we compare the performance of MEDIC and LEACH using Matlab simulations. 100 nodes, each with 2J initial energy, were evenly distributed in a circular region with diameter 100m, and the base station was located at (125m, 0). Because currently available sensor nodes have no problem covering such an area, we assume every node can communicate directly to one another and the base station. This is because we want to find the optimal cluster size without constraint on the communication range. We ran LEACH and MEDIC over 1000 random network topologies for each c or R _c and took the average of the collected data. In each simulation, nodes were redeployed uniform randomly in the area and ran until more than 95% nodes were dead. Since the steady state is much longer than the cluster formation phase, the time and energy used in the cluster formation is generally two orders of magnitude less than in the steady state, whose effect is safe to neglect.

6.1. MEDIC vs. LEACH

In this case, MEDIC is compared to native LEACH for nearly perfect data correlation (α = 0.001). For such small α, the amount of residue data is negligible, therefore, this setting is equivalent to the perfect data compression assumption used in [11]. Fig 9(a) and (b) plot the received data in the base station over time and the energy dissipated, respectively, while (o) and (d) plot the number of survival nodes whose batteries are not completely exhausted over time and per given amount of received data in the base station, respectively. To find the best c for LEACH, we compared the maximum transportation, the total data delivered back to the base station during a simulation, for different c. The simulations show that the maximum transportation is maximized at c ≈ 7 for LEACH in this case. Similarly, we found the performance of MEDIC is best at R _c ≈ 40m (See Fig. 12 and Fig. 13).

Figure 9

MEDIC vs. LEACH. (a) Amount of data received at the base station over time. (b) Amount of data received at the base station per given amount of energy. (c) Number of survival nodes over time. (d) Number of survival nodes per amount of data received in the base station.

At first glance, LEACH seems to have a longer lifetime than MEDIC as shown in Fig. 9(a). However, a further study of Fig. 10 reveals that LEACH cannot guarantee the data delivery during the later phase. Figure 10 clearly shows that the throughput of LEACH starts to degrade shortly and continues to decrease to virtually zero. The reason is that the ill result of random election (e.g. too few heads are elected) often puts a tremendous burden on the heads whose energy is already low during the later phase. After the heads are exhausted quickly, the cluster members remain idle during the rest of that round, which seems to extend the lifetime. Therefore, we define the effective lifetime as when the data loss remains below 10 percent. Figure 10 shows that MEDIC extends the effective lifetime by about 3200s.

Figure 10

MEDIC vs. LEACH. Node-to-basestation throughput over time.

Another good measurement of energy efficiency is the ratio of data transporation over energy consumption, termed as Data/Energy Ratio (DER), which is indicated by the slope in Fig. 9(b). A higher slope implies that the corresponding scheme can transport more data with the given amount of energy dissipation. Figure 9(b) shows MEDIC increased DER by about 25%. The energy efficiency improvement is achieved by successfully electing the required number of cluster heads and evenly distributing them among the whole sensor networks. In MEDIC, once a node successfully wins the bid for cluster headship, it also eliminates its neighbor's possibility to be a cluster head. And the nodes outside its influence range still have a chance to be a cluster head. In this way, MEDIC avoids electing too many or too few cluster heads in the simulation, and the elected cluster heads are evenly laid out. The mean and std of cluster heads are plotted in Fig. 11. The higher variation in the head election of LEACH indicates the clustering in the LEACH led to a worse result, which is the main reason for its damaged energy efficency.

Figure 11

The elected number of heads (Average and std).

Figure 12

Data of LEACH.

Figure 13

Data of MEDIC at α = 0.001.

The analysis in section IV-D indicates that R _c should be adapted to the decreasing node density. Since the death of nodes decreases the node density, we expect the optimal R _c to decrease accordingly. However, since MEDIC remarkably extends the effective lifetime, the number of survival nodes does not decrease visibly during most of the network lifetime. Therefore, we need not adapt R _c to keep energy efficiency.

6.2. Optimal R_c for Varying Data Aggregation Effect

In this case, MEDIC is evaluated for different α. We ran 1000 simulations at different R _c with α = 0.05 to determine optimal R _c . Figure 14 shows that the performance of MEDIC is optimal at around R _c − 10m, which is far from R _c = 40m when α = 0.001. The reason that the smaller clusters are formed is that the influence range shrinks when the data correlation decreases. These values of R _c agree well with the analysis in section IV-D for both values of α. This shows the advantage of MEDIC over the original LEACH; the inherent distributed nature of MEDIC makes it more adaptive to the different applications. This also shows the advantage of our data correlation model; we can easily fit the simulation scenarios for the phenomena of interest by varying α.

Figure 14

Data of MEDIC at α = 0.05.

7. Conclusion

The previous clustering researches often take a global approach, which is appropriate for global optimization. However, when a distributed clustering is desired, the already-answered questions such as “How many clusters should the nodes be partitioned into?” have to be translated into a distributed version, that is, “What's the appropriate cluster size?”, because it is easier for a node to know its cluster size than the number of clusters in the whole network. In this paper, we take a fully distributed approach to energy efficiency for WSN. Motivated by the local energy efficiency criterion, we propose using the cluster size instead of the number of clusters as the clustering objective parameter in clustering. Furthermore, we utilize the medium contention to implement the headship auction to keep the cluster size within an ideal range. As shown by the simulations, although the proposed MEDIC uses only local information, it achieves better energy efficiency than native LEACH in terms of Data/Energy Ratio and an effective lifetime. The simulations also show that the optimal cluster radius obtained from the experiments agrees well with the analysis of optimal clustering, which indicates that the performance of our distributed clustering is close to that of the global optimal one.