DARC: A Distributed and Adaptive Routing Protocol in Cluster-Based Wireless Sensor Networks

Abstract

Due to the limited energy of wireless sensor nodes, the energy efficiency of data collection is a key issue in wireless sensor network (WSN). Dynamic clustering is a scalable and energy efficient solution for data collection in WSN. However, it suffers from the imbalanced energy consumption in the intercluster communication. To solve this problem, in this paper, we propose a distributed and adaptive routing protocol for cluster-based wireless sensor networks (DARC). In DARC, an adaptive energy threshold is proposed for the cluster head to control its intercluster routing mode, and a tunable cost function is designed for relay selection. Simulation results prove that DARC effectively balances the energy consumption in the intercluster communication and hence improves the energy efficiency and prolongs the network lifetime.

1. Introduction

Due to the advantages of easy deployment and low cost, wireless sensor network (WSN) has been widely used for collecting data in many applications such as emergency response [1, 2], environment monitoring [3, 4], and industrial control [5, 6]. Most wireless sensors are powered by batteries with limited energy; thus the energy efficiency is an essential issue in the data collection of WSN [7].

Dynamic clustering provides a scalable and energy efficient solution for data collection in WSNs [8–10]. The operation of dynamic clustering is divided into rounds. At the beginning of every round, some nodes are selected as the cluster heads (CHs) to build up the backbone of network, while the others become cluster members (CMs) and select their own CHs. The CH collects data from CMs in its cluster and then forwards the data to the base station (BS). At the end of each round, the cluster-based topology breaks up, and new clusters will be formed in the next round. The CHs generally consume much more energy than the CMs; hence, the periodic cluster reorganization in dynamic clustering can balance the energy consumption among CHs and CMs.

However, the imbalanced energy consumption among CHs can hardly be solved by cluster reorganization. It is because the difference of node location has great impacts on the energy consumption of intercluster routing. Generally, the intercluster routing can be classified to single-hop routing (SHR) [8, 11] and multihops routing (MHR) [12, 13]. In SHR, all CHs communicate with BS directly. On the other hand, in MHR, CHs forward their data to the BS via several hops. However, the imbalance of energy consumption is inevitable in both SHR and MHR. In SHR, the node that is far away from BS suffers from long transmission range and consumes more energy. While in MHR, the node close to the BS dies faster due to the heavy relay burden.

To solve this problem, in this paper, we propose a distributed and adaptive routing protocol for cluster-based wireless sensor networks (DARC). The basic idea of DARC is to adaptively adjust the routing mode of CHs to balance the intercluster energy consumption. The major contributions of this paper are given as follows.

• (1)

Simulations are executed to study the distribution of energy consumption in both SHR and MHR. There are two important results derived from the simulations. At first, the energy consumption is imbalanced in both SHR and MHR due to the difference of node location, and this problem can not be solved by cluster reorganization. Secondly, SHR and MHR have opposite distribution of energy consumption. It motivates us to design a new protocol that can adaptively adjust the routing modes of CHs to balance the energy consumption.

(2)

We propose a distributed and adaptive routing protocol for cluster-based wireless sensor networks (DARC). In DARC, an adaptive energy threshold is designed for CHs to select intercluster routing modes. Moreover, a tunable cost function is proposed for CHs to select proper relays. All the algorithms are executed based on the distributed information exchanged during the process of dynamic clustering, which ensures that DARC has low overhead.

(3)

The guideline of setting the parameters in DARC is provided based on the simulations. Moreover, the analytical and numerical results prove that DARC effectively balances the energy consumption among CHs and thus has better energy efficiency and longer network lifetime.

The rest of this paper is organized as follows. The related works are summarized in Section 2. Section 3 presents the network models and states the problem addressed in this paper. Section 4 provides the details of DARC protocol, and the simulations are executed in Section 5 to evaluate the performance of DARC. Finally, Section 6 makes the conclusion of this paper.

2. Related Works

Clustering provides a scalable solution for data collection in WSN [9, 14]. Observing the fact that the energy consumption of CHs is much larger than that of CMs, dynamic clustering is proposed in LEACH [8] to balance the energy consumption among nodes. The basic idea of dynamic clustering is to periodically rotate the cluster heads (CHs) and reorganize the cluster-based topology based on the new set of CHs. In this case, the heavy energy burden of CHs can be dispersed all over the network. Due to the advantages of scalability and energy efficiency, dynamic clustering becomes a popular research topic that attracts considerable attentions from various research communities.

Many works focus on the algorithm of cluster head selection in dynamic clustering. HEED [12] is an iteration-based algorithm that considers both residual energy and communication cost in cluster head selection. It improves the CHs distribution in the network and hence has better efficiency than LEACH. However, HEED suffers from considerable overhead due to the iteration in the algorithm. To solve this problem, BSC [11] adopts the random backoff scheme to control the process of CH selection. The node with smaller backoff time has higher probability to be CH. BSC can generate well-distributed CHs with low overhead. In [15], the vice-cluster head is proposed to alleviate the traffic load of cluster head, such that the network lifetime is significantly improved. The authors in [16] consider the collaborative data processing between nodes and propose an efficient cluster head selection approach for collaborative data processing.

Cluster formation is another popular research topic in dynamic clustering. In EECS [17], a novel cost function is proposed for CMs to select proper CHs by considering the distance between CH and the BS. The energy consumption is balanced by intracluster communication in EECS and the network lifetime is significantly improved. In IDUC [18], a radius competition scheme is proposed to generate unequal clusters that can balance the energy consumption among CHs in the network with heterogeneous energy. On the other hand, some research works provide mathematical analysis on how to assign the range of clusters in various scenarios [13, 19]. In [19], the authors provide a mathematical framework to determine the optimal number of clusters by minimizing the energy consumption in both single-hop and multihops scenarios. EC [13] considers the multihop data collection scenario and formulates an optimization problem that determines suitable cluster ranges depending on the hop distance to the BS.

For the intercluster communication, many dynamic clustering protocols are developed based on the assumption that the CHs can communicate with the BS directly [8, 11, 17]. On the other hand, some research works have considered the multihops routing among CHs [12, 13, 18]. For example, HEED [12] uses the greedy routing algorithm for intercluster communication, and EC [13] uses a routing algorithm that considers the load balance among CHs. Nonetheless, due to the difference of node location, the imbalanced energy consumption among CHs can hardly be solved by these routing algorithms. Moreover, these algorithms are not tailored for dynamic clustering that may generate considerable overhead during cluster reorganization. It motivates us to study this problem in Section 3.3 and provide a distributed solution named DARC in Section 4.

3. Preliminaries

3.1. Network Model

In this paper, we consider a typical data collection scenario in WSN. A great number of sensor nodes are randomly deployed in a square area. The network is assumed to have the following properties.

• (1)

There is a base station (BS) located in the network area to collect sensing data from sensor nodes. Hence, the destination of every sensing data is the BS.

(2)

Sensor nodes have homogeneous hardware capabilities. They are powered by batteries which have limited energy. It motivates the requirement of improving energy efficiency and prolong the network lifetime.

(3)

Every node can use power control to adjust its transmission range, and it has sufficient power to transmit its data to the BS directly.

(4)

Links are symmetric, and every node can estimate its distance to another node based on the received signal strength indication (RSSI).

(5)

The network is organized into clusters which includes one cluster head (CH) and some cluster members (CMs). Each CH has the ability to aggregate intracluster data packets into one single packet, while the intercluster packets can not be aggregated.

3.2. Energy Consumption Model

The energy consumption model is adopted from LEACH [8]. The energy consumed for transmitting l-bit data over distance d is

$$\begin{array}{cc}& E_{\text{tx}}\left(l,d\right)=l\left(E_{\text{elec}}+{ϵ}_{\text{fs}}{d}^{\mathrm{2}}\right)\end{array}$$

(1)

and the energy consumed for receiving l-bit data is

$$\begin{array}{cc}& E_{\text{rx}}\left(l\right)=l{E}_{\text{elec}},\end{array}$$

(2)

where $E_{\text{elec}}$ is the electronics energy which depends on the radio electronics and ${ϵ}_{\text{fs}}{d}^{\mathrm{2}}$ is the amplifier energy which follows the free space channel model. The values of these parameters are given in Table 1.

Table 1

Simulation parameters.

Type	Parameter	Value
Application	Initial energy	1 J
	Data packet size (l)	125 bytes
	Node density	0.01 nodes/m2
	Round	20 TDMA frames
Radio model	$$E_{\text{elec}}$$	50 nJ/bit
	$${ϵ}_{\text{fs}}$$	10 pJ/bit/m2
	$$E_{\text{DA}}$$	5 nJ/bit/signal

3.3. Problem Statement

In dynamic clustering, periodical cluster reorganization can distribute the energy consumption of CHs among all nodes. However, the imbalance of energy consumption still exists due to the difference of node location. Every node has different distance to the BS that leads to different energy consumption in the intercluster communication.

To further study the imbalance of energy consumption caused by node location, simulations are executed to demonstrate the location distribution of the first dead node. The first dead node is defined as the node that runs out its energy first in the network. The backoff-based clustering scheme [11] is used to generate the cluster-based topology. Based on the selected CHs, two routing algorithms are used in the intercluster communication: the single-hop routing (SHR) and the multihops routing (MHR). In SHR, all CHs transmit data to the BS directly. On the other hand, in MHR, CHs forward their data to the BS via multihops relay. In this paper, a greedy routing algorithm is used in MHR [20]. The CH i selects the closest CH which is closer to BS than itself as its relay. The algorithm can be formulated as

$$\begin{array}{cc}& \mathcal{R}\left(i\right)=\min \left\{d\left(i,j\right)\mid d\left(i,\mathrm{0}\right)>d\left(j,\mathrm{0}\right),\hspace{0.17em}\hspace{0.17em}j\in \mathcal{H}\right\},\end{array}$$

(3)

where $d(i,j)$ is the distance between nodes i and j and $d(i,\mathrm{0})$ is the distance between node i and BS. $\mathcal{H}$ is the set of CHs and $\mathcal{R}(i)$ is the relay of CH i.

The network area is set as $\mathrm{200}\times \mathrm{200}\hspace{0.17em}{\mathrm{m}}^{\mathrm{2}}$ , and the BS locates at $(\mathrm{0,0})$ . The simulation runs 50 times to obtain the statistics about the distance from the first dead node to the BS. The results are given in Table 2.

Table 2

The distance from first dead node to BS.

Distance to BS	0–70 m	70–140 m	140–210 m	>210 m
SHR	0	0	21	29
MHR	41	5	3	1

In SHR, the distances from all first dead nodes to BS are over 140 m. On the other hand, in MHR, 82% first dead nodes are located within 70 m to the BS. It indicates that the locations of first dead nodes are different in SHR and MHR. In SHR, the node that is far away from the BS consumes more energy due to the long transmission range. While, in MHR, the node closer to the BS suffers from the heavy load for relaying and dies faster than other nodes.

The results demonstrate that the energy consumption is imbalanced due to the difference of node location, and this problem can not be solved by cluster reorganization. On the other hand, the results also depict that SHR and MHR have opposite distribution of energy consumption. It motivates us to design a new protocol that can adaptively adjust the routing modes of CHs to balance the energy consumption.

3.4. Design Goals

To solve the problem stated above, we propose a distributed and adaptive routing protocol in cluster-based wireless sensor networks (DARC). The basic idea of DARC is to adaptively adjust the intercluster routing modes of CHs based on distributed information exchanges among CHs. Specifically, the design goals of DARC are given as follows.

• (1)

The routing modes of CHs can be adaptively selected based on their residual energy, such that the energy consumption of intercluster communication can be balanced in different rounds.

(2)

The relays of CHs should be selected with joint consideration of the balance of energy consumption and energy efficiency, since both of them are critical to prolong the network lifetime.

(3)

The algorithm should be distributed with low overhead due to the limited hardware resources of sensor nodes.

4. DARC Protocol

DARC is designed based on the framework of dynamic clustering which uses periodical clusters reorganization to distribute the energy consumption among all nodes. Different from existing dynamic clustering protocols, in DARC, every node collects the information of neighbors during the process of cluster head selection and uses the information to make the clustering and routing decision distributively. Once a node decides to be a CH, it should determine the routing mode by comparing its residual energy with neighboring CHs. Moreover, it uses a cost function, which considers both the energy efficiency and the load balance, to select CH or BS as its next-hop nodes.

The details of DARC are described in the following sections. To clarify the statement, the variables using in DARC are summarized in Table 3.

Table 3

Variables list.

Symbol	Description
$$T(i)$$	The backoff timer of node i
$$T_{\text{chs}}$$	The duration of cluster head selection
$$T_r$$	The duration of adaptive routing
$$R_c$$	The clustering range
$$R_n$$	The range for relay selection
$$E_{\text{MAX}}$$	The initial energy of nodes
$$E_r(i)$$	The residual energy of node i
$$N_{\text{CH}}$$	The number of CHs
$$E_{\text{ave}}$$	The average energy of all CHs
$$d(i,j)$$	The distance between nodes i and j
$$d(i,\mathrm{0})$$	The distance between node i and base station

4.1. Cluster Head Selection

The random backoff strategy [11, 21] is used in DARC to select CHs with low overhead. The network operation is divided into rounds. At the beginning of every round, each node sets a backoff timer $T(i)$ according to its residual energy,

$$\begin{array}{cc}& T\left(i\right)=\frac{E_{\text{MAX}}-E_r\left(i\right)}{E_{\text{MAX}}}\times T_{\text{chs}},\end{array}$$

(4)

where $E_r(i)$ is the residual energy of the node i and $E_{\text{MAX}}$ is the initial energy of node. $T_{\text{chs}}$ is the duration of cluster head selection phase.

After setting the backoff timer $T(i)$ , the node should listen to the channel for incoming packets. There are two kinds of advertisement (ADV) packets that are distributively exchanged during the cluster head selection phase: the ADV packet for clustering (AC) and the ADV packet for routing (AR). Both of them are broadcast by the CHs. Considering the AC and AR packets broadcast by CH j, they should carry the following information: the ID j, the residual energy $E_r(j)$ , and the estimated distance to the BS $d(j,\mathrm{0})$ . Moreover, the AC and AR packets are broadcast in different ranges. The AC packets are broadcast in range $R_c$ to control the size of clusters, while the AR packets are broadcast in range $R_n$ to adjust the area for relay selection. Both $R_c$ and $R_n$ impact the efficiency of clustering and routing in DARC. The guideline of setting $R_c$ and $R_n$ will be discussed in Section 5.1.

Based on received packets, every node updates the following data lists:

• (i)

JOIN list: it records the CHs within range $R_c$ ;

(ii)

ENERGY list: it records the CHs within range $R_n$ .

When the node receives AC packet, it records the information of transmitter CH to the JOIN list. The JOIN list will be used for the node to select its CH when it decides to be CM. When the node receives AR packet, it records the information to the ENERGY list which will be used for the CH to make intercluster routing decision.

When the backoff timer $T(i)$ terminates, the node i checks its JOIN list. If the JOIN list is empty, it will set up its status as CH and broadcast AC and AR packets. On the other hand, if the JOIN list is not empty, it will quit the competition for becoming CH and assign itself as a CM. The condition for selecting CH is based on the setting of backoff timer. According to (4), a node with higher residual energy has smaller $T(i)$ and hence could broadcast its ADV packet before its neighbors. Therefore, if the JOIN list is empty, it means that node i has the maximum residual energy among all its neighbors in $R_c$ .

After determining its status, the node should continue listening to the channel until $T_{\text{chs}}$ expires, that is, the end of cluster head selection phase. For CMs, they should record all AC packets to the JOIN list, and the CHs have to record all AR packets to the ENERGY list. This information will be used to make the clustering and routing decision. The details are given in the following sections.

4.2. Cluster Formation

When $T_{\text{chs}}$ expires, each CM has to select a proper CH from the JOIN list. In DARC, we use a simple metric so that the CM chooses its CH with the maximum RSSI of AC packet. This metric can minimize the energy consumption of intracluster communication. When a CM has selected its CH, it has to transmit a Join Cluster (JC) packet to its CH. By receiving the JC packet, the CH records the transmitter to the MEM list as its member. The MEM list will be used by each CH to schedule the intracluster data collection in the data transmission phase. When every CM has transmitted JC packet to its CH, the cluster formation is completed.

4.3. Adaptive Routing

The basic idea of DARC is to adaptively switch the routing modes of CH to balance the energy consumption of intercluster communication. To realize this idea, we define two kinds of routing modes for every CH: CH-L and CH-H. The CH-L denotes the CH with relatively low energy that requires a closer relay to forward its data. While the CH-H denotes the CH with relatively high energy that can serve as a relay and transmit its data to the BS directly.

At the beginning, each CH has to determine its routing mode based on the ENERGY list. A CH i estimates the average residual energy $E_{\text{ave}}(i)$ of all CHs in its ENERGY list by

$$\begin{array}{cc}& E_{\text{ave}}\left(i\right)=\frac{{\sum }_{j=\mathrm{1}}^{N_{\text{CH}}\left(i\right)}{E}_r\left(j\right)}{N_{\text{CH}}\left(i\right)},\hspace{1em}j\in \text{ENERGY}\left(i\right),\end{array}$$

(5)

where $N_{\text{CH}}(i)$ is the number of CHs in the ENERGY list. Then, the CH compares its residual energy $E_r(i)$ with $E_{\text{ave}}(i)$ . If $E_r(i)<E_{\text{ave}}(i)$ , the CH will be classified as a CH-L. Otherwise, if $E_r⩾E_{\text{ave}}$ , the CH will be classified as a CH-H.

The CH-H selects the BS as its next-hop node since it has sufficient energy. Then it broadcasts AR packet in $R_n$ to announce that it can serve as a relay for nearby CH-L. On the other hand, the CH-L sets up a timer $T_r$ and then keeps listening to the channel. $T_r$ is a fixed timer that presents the duration of adaptive routing phase.

When it receives a AR packet from CH j, it should compare its distance to the BS, which is denoted by $d(i,\mathrm{0})$ , with $d(j,\mathrm{0})$ that is contained in the AR packet. If $d(i,\mathrm{0})>d(j,\mathrm{0})$ , the CH i will record the information of CH j to the RELAY list. Otherwise, it will discard the AR packet. This condition ensures that its next-hop node is closer to the BS.

When $T_r$ terminates, the CH-L checks its RELAY list. If RELAY list is empty, which means that there is no CH-H located closer to the BS in $R_n$ , it will select the BS as its next-hop node. Otherwise, the CH-L has to select a relay from its ENERGY list. The relay selection is a nontrivial issue that impacts both energy efficiency and load balance. Therefore, we firstly analyze the energy consumption of intercluster routing among CHs and then provide the algorithm for relay selection.

According to the energy model given in Section 3.2, the energy consumption for CH-L i to transmit l-bit data to its relay CH j can be estimated by

$$\begin{array}{cc}& E_{\text{chtx}}\left(i,j\right)=l{E}_{\text{elec}}+l{ϵ}_{\text{fs}}{d}^{\mathrm{2}}\left(i,j\right),\end{array}$$

(6)

where $d(i,j)$ is the distance between CH-L i and CH j. On the other hand, in order for a CH to forward l-bit data to BS, the energy consumption can be calculated by

$$\begin{array}{cc}& E_{\text{chtx}}\left(j,\mathrm{0}\right)=l{E}_{\text{elec}}+l{ϵ}_{\text{fs}}{d}^{\mathrm{2}}\left(j,\mathrm{0}\right),\end{array}$$

(7)

where $d(j,\mathrm{0})$ is the distance between CH j and BS.

Based on the analysis given above, the energy efficiency of intercluster communication can be achieved by minimizing the following cost function:

$$\begin{array}{cc}& \text{cost}\left(j,i\right)=d^{\mathrm{2}}\left(i,j\right)+d^{\mathrm{2}}\left(j,\mathrm{0}\right).\end{array}$$

(8)

However, the load balance can hardly be achieved simply by minimizing the cost given in (8). It is possible that the CH-H has considerable traffic load in a single round. On the other hand, the residual energy of CH-L may be so small that selecting a closer relay is urgent. Therefore, with jointed consideration of both CH-L and CH-H, we set a weighted factor α for the tradeoff between $d^{\mathrm{2}}(i,j)$ and $d^{\mathrm{2}}(j,\mathrm{0})$ . The improved cost function used in DARC is

$$\begin{array}{cc}& \text{cost}\left(j,i\right)=\alpha \times d^{\mathrm{2}}\left(i,j\right)+\left(\mathrm{1}-\alpha \right)\times d^{\mathrm{2}}\left(j,\mathrm{0}\right).\end{array}$$

(9)

The CH-H j with the lowest $\text{cost}(j,i)$ is the best relay for CH-L i, since the smaller $\text{cost}(j,i)$ represents not only the energy efficiency of transmission path, but also the reasonable load balance between CH-L and CH-H. The setting of α is critical to the network lifetime. How to obtain the optimal value of α will be discussed in Section 5.1.

4.4. Properties of DARC

In this section, we provide the basic properties of DARC protocol that prove its effectiveness.

Lemma 1.

After executing the cluster head selection algorithm of DARC, each node is either a CH or a CM.

Proof.

Assume that a node is neither a CH nor a CM after executing the cluster head selection algorithm. Since the node does not become CH, it implies that the JOIN list is not empty when its $T(i)$ terminates. In this case, the node will choose to be a CM according to line 15 given in Algorithm 1, which is a contradiction.

Algorithm 1: Clustering algorithm of DARC.

(1) Node i sets up random backoff timer $T(i)$ (Equation (4));

(2) repeat

(3)  if Receives AC packet from CH j  then

(4)   Records CH j to JOIN list;

(5)  end if

(6)  if Receives AR packet from CH j  then

(7)   Records CH j to ENERGY list;

(8)  end if

(9) until   $T(i)$ terminates

(10) if JOIN list is empty then

(11)    $\text{status}\leftarrow \text{CH}$ ;

(12)  Broadcasts AC packet in $R_c$

(13)  Broadcasts AR packet in $R_n$

(14) else

(15)   $\text{status}\leftarrow \text{CM}$ ;

(16) end if

(17) repeat

(18)  if  status = CM AND Receive AC packet from CH j  then

(19)   Records CH j to JOIN list;

(20) end if

(21)  if status = CH AND Receives AR packet from CH j  then

(22)   Records CH j to ENERGY list;

(23) end if

(24) until   $T_{\text{chs}}$ terminates

(25) if status = CM then

(26) Selects its CH with maximum RSSI from the JOIN list;

(27) Transmits a JC packet to its CH;

(28) end if

Lemma 2.

The distance between any pair of CHs is longer than $R_c$ .

Proof.

Assume that the distance between CH i and CH j is shorter than $R_c$ and the backoff timer of CH j, $T(j)$ is longer than $T(i)$ . In this case, in the cluster head selection algorithm, the node i broadcasts its AC packet in $R_c$ before $T(j)$ terminates. Therefore, node j receives the AC packet for CH i and records the information of CH i to its JOIN list. When $T(j)$ terminates, since the JOIN list of node j is not empty, the node j should select its status as CM. It is a contradiction to the assumption.

Lemma 3.

After executing the cluster formation algorithm of DARC, each CM has selected a CH and joined its cluster.

Proof.

In DARC, the CM selects its CH from the JOIN list. If the CM does not select a CH, it means that its JOIN list is empty. According to the algorithm of cluster head selection, the node will become a CH if its JOIN list is empty, which is a contradiction.

Lemma 4.

In DARC, the CH transmits its data to the BS in 1 or 2 hops.

Proof.

There are two kinds of CHs in DARC: CH-H and CH-L. The next-hop node of CH-H is destined to be the BS; thus, the hop count is 1. For the CH-L, if its RELAY list is empty, it will transmit data to the BS directly. Otherwise, it has to select its next-hop node from the RELAY list. According to lines 15 and 16 given in Algorithm 2, only the CH-H can be recorded in the RELAY list. Therefore, the hop count from CH-L to the BS is at most 2 hops.

Algorithm 2: Adaptive routing algorithm of DARC.

(1) Given a CH i after the cluster head selection algorithm;

(2) Calculates $E_{\text{ave}}(i)$ of CHs in ENERGY list (Equation (5));

(3) if   $E_r\left(i\right)⩾\mathrm{⩾}{E}_{\text{ave}}(i)$   then

(4)   $\text{status}\leftarrow \text{CH}$ -H

(5)  Select the BS as its next-hop node;

(6)  Broadcasts AR packet in $R_n$ ;

(7) else

(8)   $\text{status}\leftarrow \text{CH}$ -L

(9)  repeat

(10)  if  Receives AR packet from CH j  then

(11)   if   $d(j,\mathrm{0})<d(i,\mathrm{0})$   then

(12)    Records CH j to RELAY list;

(13)   end if

(14)  end if

(15)  until   $T_r$ terminates

(16)  if RELAY list is empty then

(17)   Select the BS as its next-hop node;

(18)  else

(19)   Selects the CH with minimum $C(i,j)$ (Equation (9)) in the RELAY list as its next-hop node;

(20)  end if

(21) end if

Theorem 5.

The DARC protocol generates a connected network topology.

Proof.

According to Lemma 1, each node is either a CH or a CM after running the cluster head selection algorithm. Combining Lemmas 3 and 4, every node can transmit its data to the BS with limited hops. Therefore, the network is connected.

Remark 6.

The DARC protocol is completely distributed.

Proof.

In DARC, every node determines its status (CM or CH) and selects its next-hop node based on its backoff timer $T(i)$ and the received packets. The backoff timer $T(i)$ is determined by its local information, and the received packets are broadcast by the CHs within the ranges $R_c$ and $R_n$ . Therefore, the DARC protocol is completely distributed.

Theorem 7.

Given the number of nodes N and the number of CHs $N_{CH}$ , the packet overhead of DARC is at most $N+\mathrm{2}\ast N_{CH}$ per round.

Proof.

In DARC, every CH broadcasts two packets (AC and AR) in the cluster head selection algorithm, and each CM transmits a JC packet to its CH in the cluster formation algorithm. According to Lemma 1, the number of CMs can be calculated by $N-N_{\text{CH}}$ . Thus, the packet overhead of the clustering algorithm can be calculated by $N-N_{\text{CH}}+\mathrm{2}\ast N_{\text{CH}}=N+N_{\text{CH}}$ . In the routing algorithm, the CH-H has to broadcast AR packet to inform neighbor CH-L. If the RELAY list of CH-L is not empty, the CH-L will transmit a packet to the selected CH-H for confirmation. Therefore, the packet overhead of the routing algorithm is at most $N_{\text{CH}}$ . To sum up, the packet overhead of DARC is at most $N+\mathrm{2}\ast N_{\text{CH}}$ .

For comparison, we analyze the complexity of SHR and MHR which have been described in Section 3.3.

Theorem 8.

Given the number of nodes N and the number of CHs $N_{CH}$ , the packet overhead of SHR is N per round.

Proof.

In SHR, every CH broadcasts AC packets in the cluster head selection algorithm, and each CM transmits a JC packet to its CH in the cluster formation algorithm. According to Lemma 1, the number of CMs can be calculated by $N-N_{\text{CH}}$ . Thus, the packet overhead of the clustering algorithm can be calculated by $N-N_{\text{CH}}+N_{\text{CH}}=N$ . In the routing algorithm, all CHs have to transmit data to the sink directly. Therefore, the packet overhead of the routing algorithm is 0. To sum up, the packet overhead of SHR is N.

Theorem 9.

Given the number of nodes N and the number of CHs $N_{CH}$ , the packet overhead of MHR is $N+\mathrm{2}\ast N_{CH}$ per round.

Proof.

In MHR, every CH broadcasts AC packets in the cluster head selection algorithm, and each CM transmits a JC packet to its CH in the cluster formation algorithm. According to Lemma 1, the number of CMs can be calculated by $N-N_{\text{CH}}$ . Thus, the packet overhead of the clustering algorithm can be calculated by $N-N_{\text{CH}}+N_{\text{CH}}=N$ . In the routing algorithm, each CH broadcasts small packets of distance and ID information in its transmission range to inform its neighbor CHs. Then, CH selects its relay according to (3) and transmits a packet to the selected relay for confirmation. Therefore, the packet overhead of the routing algorithm is $\mathrm{2}\ast N_{\text{CH}}$ . To sum up, the packet overhead of MHR is $N+\mathrm{2}\ast N_{\text{CH}}$ .

The properties given above prove that the DARC can generate reliable cluster-based network topology with low overhead. The efficiency of DARC will be further studied by simulations in the next section.

5. Simulation Results

In this section, the simulations are executed to study the performance of DARC. At first, we study how does the parameters setting in DARC impact the network performance. Then, the performance of DARC is compared with that of SHR and MHR to prove its efficiency. For fairness, both SHR and MHR adopt the backoff strategy [11] that is described in Section 4.1 for the cluster head selection. Network lifetime is the major metric for evaluating the energy efficiency of DARC. The network lifetime is defined as the rounds when the first node dies (FND), since a certain area may not be monitored once a sensor node exhausts its energy. The basic parameters used in simulations are summarized in Table 1. Each simulation runs 100 times with different node deployment to obtain the statistic results.

5.1. Parameters Setting

In DARC, there are three important parameters: the clustering range $R_c$ , the range for relay selection $R_n$ , and the weighted factor α in (9). The simulations are executed to study how does these parameters impact the network performance. The network is deployed in a $\mathrm{200}\hspace{0.17em}\mathrm{m}\times \mathrm{200}\hspace{0.17em}\mathrm{m}$ area with 400 nodes, and the base station (BS) is located at coordinates $(\mathrm{0,0})$ . $R_c$ is set as $\mathrm{20}\hspace{0.17em}\mathrm{m}$ , $\mathrm{40}\hspace{0.17em}\mathrm{m}$ , $\mathrm{60}\hspace{0.17em}\mathrm{m}$ , and $\mathrm{80}\hspace{0.17em}\mathrm{m}$ , respectively, while $R_n$ is set as $\mathrm{120}\hspace{0.17em}\mathrm{m}$ , $\mathrm{180}\hspace{0.17em}\mathrm{m}$ , and $\mathrm{240}\hspace{0.17em}\mathrm{m}$ . The weighted factor α varies in range $[\mathrm{0,1}]$ . The simulation results are given in Figure 1.

Figure 1

Impact of DARC parameters (α, $R_c$ , and $R_n$ ) on the network lifetime.

As shown in Figure 1, $R_c$ , $R_n$ , and α have significant impacts on network lifetime. The first important result is that the α has great impact on the network lifetime, and the optimal value of α is related to $R_c$ . When $R_c$ grows from $\mathrm{20}\hspace{0.17em}\mathrm{m}$ to $\mathrm{80}\hspace{0.17em}\mathrm{m}$ , the optimal value of α also grows from 0.6 to 1. It indicates that the transmitting range of CH-L is more important than that of CH-H in most scenarios. According to the cluster head selection algorithm of DARC, the clustering range $R_c$ not only impacts the number of clusters, but also determines the minimum distance between CHs. The growth of $R_c$ reduces the number of CHs and increases the distance between CHs. Therefore, as $R_c$ grows up, it is more difficult for the CH-L to select a reasonable CH-H as its relay. Therefore, a greater value of α, which makes the CH-L intends to select a closer CH-H as its next-hop node, is helpful to improve the network lifetime.

Then, we evaluate the impact of $R_n$ . The variance of network lifetime (with respect to α) increases with the growth of $R_n$ . Take $R_c=\mathrm{20}\hspace{0.17em}\mathrm{m}$ (Figure 1(a)); for example, when $R_n=\mathrm{120}\hspace{0.17em}\mathrm{m}$ , the network lifetime varies from 315 rounds to 358 rounds with different α. On the other hand, when $R_n=\mathrm{240}\hspace{0.17em}\mathrm{m}$ , the network lifetime varies from 194 rounds to 356 rounds with different α. It is because $R_n$ determines the area to select the relay. There are more CH-H that can be served as relay when $R_n$ grows. Nevertheless, as shown in Figure 1, $R_n$ has little impact on the optimal network lifetime which means that the optimal relay is generally not far away from the CH-L. Moreover, it indicates an important result that the distributed information exchanged in $R_n$ is sufficient for optimal relay selection.

For $R_c$ , its value determines the number of CHs and the energy consumption of intracluster communication. A reasonable setting of $R_c$ is able to reduce the energy consumption and prolong the network lifetime, which has been studied in [13, 22]. In this scenario, the network lifetime approaches the maximum at 396 rounds when $R_c=\mathrm{40}\hspace{0.17em}\mathrm{m}$ and $\alpha =\mathrm{0.9}$ .

According to the results given above, in the rest of simulations, $R_n$ is fixed at $\mathrm{120}\hspace{0.17em}\mathrm{m}$ . Meanwhile, for each given $R_c$ , α is set as the optimal value which could achieve maximum network lifetime.

5.2. Network Lifetime Analysis

To prove the efficiency of DARC, in this section, the simulations are executed to compare the network lifetime of DARC with that of SHR and MHR in different network scenario. We also compare the residual energy ratio, which is defined as the ratio of residual energy, to the initial energy when the first dead node appears.

At first, we compare the network lifetime and the residual energy ratio with different network area. The side length of the network area varies from $\mathrm{100}\hspace{0.17em}\mathrm{m}$ to $\mathrm{200}\hspace{0.17em}\mathrm{m}$ . The node density is fixed at $\mathrm{0.01}\hspace{0.17em}\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s}/{\mathrm{m}}^{\mathrm{2}}$ and the BS locates at coordinates $(\mathrm{0,0})$ . The simulation results are given in Figures 2 and 3.

Figure 2

Network lifetime with different network area.

Figure 3

Residual energy ratio with different network area.

As shown in Figure 2, the optimal network lifetime of DARC is longer than that of SHR and MHR in both small-scale and large-scale networks. In a small-scale network of 100 m × 100 m, the improvement of network lifetime in DARC is about $\mathrm{17.6}\%$ over SHR and $\mathrm{14.6}\%$ over MHR. Furthermore, in a large-scale network of 200 m × 200 m, the network lifetime of DARC is improved, $\mathrm{42.9}\%$ over SHR and $\mathrm{34.1}\%$ over MHR.

The advantages of DARC increase with the growth of network area. It is because as the area of network enlarges, the nodes in SHR suffer from the growth of transmission distance, while MHR generates greater amount of relay burden for the nodes close to the BS. It leads to severe energy imbalance and shortens the network lifetime. On the other hand, by adaptively controlling the routing modes of CHs, DARC successfully balances the energy consumption in intercluster routing and hence prolongs the network lifetime. Therefore, the DARC has longer network lifetime and better scalability than SHR and MHR.

The residual energy ratio also proves the energy efficiency of DARC. As shown in Figure 3, when the first dead node appears in DARC, only $\mathrm{2.48}\%$ energy is left in the $\mathrm{100}\hspace{0.17em}\mathrm{m}\times \mathrm{100}\hspace{0.17em}\mathrm{m}$ network and there is $\mathrm{6.91}\%$ energy left in the $\mathrm{200}\hspace{0.17em}\mathrm{m}\times \mathrm{200}\hspace{0.17em}\mathrm{m}$ network. On the other hand, the residual energy ratio of SHR and MHR is generally larger than $\mathrm{20}\%$ .

In DARC, the residual energy ratio monotonously increases with the growth of $R_c$ . It means that the energy utilization of DARC achieves the maximum when $R_c=\mathrm{20}\hspace{0.17em}\mathrm{m}$ . The reason can be found in the analysis given in Section 5.1. The smaller $R_c$ can reduce the distance between CHs and generate more CHs. Therefore, the relay selection is more efficient with a smaller $R_c$ . However, as shown in Figure 2, the network lifetime achieves the maximum when $R_c=\mathrm{30}\hspace{0.17em}\mathrm{m}$ in $\mathrm{150}\hspace{0.17em}\mathrm{m}\times \mathrm{150}\hspace{0.17em}\mathrm{m}$ network and $R_c=\mathrm{40}\hspace{0.17em}\mathrm{m}$ in $\mathrm{200}\hspace{0.17em}\mathrm{m}\times \mathrm{200}\hspace{0.17em}\mathrm{m}$ network. It is because the growth of $R_c$ can reduce the number of CHs and so as the intercluster traffic loads. This benefit is overwhelmed by the growth of intracluster energy consumption when $R_c$ grows larger than $\mathrm{50}\hspace{0.17em}\mathrm{m}$ . This reason can also explain the performance of SHR and MHR given in Figures 2 and 3.

Then we study the network performance with different node density. The network area is fixed at $\mathrm{200}\hspace{0.17em}\mathrm{m}\times \mathrm{200}\hspace{0.17em}\mathrm{m}$ , while the number of nodes N grows from 200 to 800. The simulation results are given in Figures 4 and 5.

Figure 4

Network lifetime with different node density.

Figure 5

Residual energy ratio with different node density.

Figures 4 and 5 show that DARC outperforms SHR and MHR with different node density. Specifically, in a sparse network with 200 nodes, the improvement of network lifetime in DARC is about $\mathrm{44.5}\%$ over SHR and $\mathrm{10.1}\%$ over MHR. In a dense network with 800 nodes, the network lifetime of DARC is improved, $\mathrm{43.1}\%$ over SHR and $\mathrm{14.2}\%$ over MHR. Moreover, the residual energy ratio of DARC is below $\mathrm{10}\%$ with the maximum network lifetime, while the residual energy ratio of SHR and MHR is generally larger than $\mathrm{20}\%$ . These results prove the efficiency of DARC in both sparse and dense networks.

As shown in Figure 4, the maximum network lifetime slightly increases with the growth of node density. Moreover, the optimal value of $R_c$ reduces when the node density increases. The reasons are given as follows. According to Lemma 2, the number of CHs is determined by $R_c$ rather than the node density, such that the dense node deployment can reduce the probability of being CH for each node. However, this benefit is limited by the growth of intracluster energy consumption in a dense network. In this case, reducing the value of $R_c$ is helpful to control the intracluster energy consumption and hence prolong the network lifetime.

5.3. Energy Consumption Analysis

In this section, we evaluate the energy consumption of DARC to exploit how does DARC prolong the network lifetime. The energy consumption is categorized into three groups: the energy of CH for transmitting data (CHTX), the energy of CH for receiving data (CHRX), and the energy of CM for transmitting data to its CH (CMTX). Simulations are implemented in a scenario where 400 nodes are deployed in a $\mathrm{200}\hspace{0.17em}\mathrm{m}\times \mathrm{200}\hspace{0.17em}\mathrm{m}$ area and the BS locates at coordinates $(\mathrm{0,0})$ . Based on the results given in Figure 3, $R_c$ is set as $\mathrm{40}\hspace{0.17em}\mathrm{m}$ to maximize the network lifetime in DARC. To clarify the comparison, $R_c$ is also set as $\mathrm{40}\hspace{0.17em}\mathrm{m}$ in SHR and MHR to generate similar distribution of CHs. Each simulation runs until the first dead node appears, and we study the energy consumption in two groups: the energy consumption of the first dead node and the average energy consumption of all nodes.

The simulation results are given in Tables 4 and 5. Since DARC provides longer network lifetime, the average energy consumption of DARC is larger than that of SHR and MHR. On the other hand, for the first dead node, its energy consumption in CHTX is significantly reduced in DARC due to the adaptive routing algorithm.

Table 4

Energy consumption comparison (average).

Average	CHRX (J)	CHTX (J)	CMTX (J)
DARC	0.3871	0.1129	0.4096
SHR	0.2416	0.0819	0.2633
MHR	0.3076	0.0611	0.3044

Table 5

Energy consumption comparison (first dead).

First dead	CHRX (J)	CHTX (J)	CMTX (J)
DARC	0.4282	0.1868	0.3889
SHR	0.2718	0.4929	0.2430
MHR	0.4684	0.2641	0.2750

To clarify the difference between the energy consumption of the first dead node and the average energy consumption of all nodes, we illustrate them with SHR, MHR, and DARC separately in Figure 6. In SHR, the CHTX dominates the energy consumption of the first dead node. The CHTX of the first dead node is over 6 times compared with the average CHTX. According to the results given in Table 2, the first dead node of SHR generally locates far away from the BS; hence, it suffers from the long transmitting distance when it becomes a CH. In MHR, the CHTX is smaller than that of SHR due to the multihops routing. However, both CHTX and CHRX of the first dead node are more than the average ones. It is because, in MHR, the CH that is close to the BS suffers from the burden for relaying intercluster packets.

Figure 6

Energy consumption comparison.

On the other hand, the CHTX of the first dead node is greatly reduced in DARC. In DARC, the CHTX of the first dead node is only $\mathrm{37.9}\%$ of that in SHR and $\mathrm{70.5}\%$ of that in MHR. Moreover, the difference of energy consumption between the first dead node and other nodes is greatly reduced in DARC. These results prove the effectiveness of DARC. The adaptive routing mechanism used in DARC successfully balances the energy consumption among the CHs that have different distance to the BS. It is the major reason that the DARC has longer network lifetime than SHR and MHR.

5.4. Hop Count Analysis

In this section, we compare the hop count from the CHs to the BS among SHR, MHR, and DARC. The hop count presents the transmission latency and the routing complexity of the protocol. Simulations are implemented in the scenario where 400 nodes are randomly deployed in a $\mathrm{200}\hspace{0.17em}\mathrm{m}\times \mathrm{200}\hspace{0.17em}\mathrm{m}$ area and the BS is located at coordinates $(\mathrm{0,0})$ . The clustering range grows from $\mathrm{20}\hspace{0.17em}\mathrm{m}$ to $\mathrm{80}\hspace{0.17em}\mathrm{m}$ . The simulation results are given in Figure 7.

Figure 7

Hop count of CHs.

As shown in Figure 7, the hop count of SHR is fixed at 1, and the hop count of MHR drops from 8.88 hops to 2.57 hops with the growth of $R_c$ . On the other hand, in DARC, the hop count slightly decreases from 1.47 to 1.29 as the $R_c$ grows. It proves that the DARC can prolong the network lifetime with reasonable growth of transmission latency and routing complexity.

Moreover, since the CH in DARC transmits its data to the BS in either one or two hops (Lemma 4), the hop count also presents the percentage of the CHs that have a relay. According to the results given in Figure 7, nearly $\mathrm{47}\%$ CHs select a relay to reduce its energy consumption when $R_c=\mathrm{20}\hspace{0.17em}\mathrm{m}$ , while, in $R_c=\mathrm{80}\hspace{0.17em}\mathrm{m}$ , only $\mathrm{29}\%$ CHs have selected a relay. It is because the growth of $R_c$ leads to the decreasing number of CHs, and it reduces the probability to find a reasonable relay. This result also explains why DARC does not perform well when $R_c$ has a large value.

6. Conclusion

In this paper, we analyze the energy consumption in dynamic clustering algorithms and find that the cluster reorganization can not balance the energy consumption in the intercluster communication. To solve this problem, we propose a distributed and adaptive routing protocol for cluster-based wireless sensor networks (DARC). The DARC protocol uses an adaptive energy threshold to select a suitable intercluster routing mode for CHs, and a tunable cost function is proposed for relay selection. Simulation results prove that DARC effectively balances the energy consumption among CHs in various network scenarios and hence has better energy efficiency and longer network lifetime.

In future works, we will study how to use the DARC protocol in a large-scale network where most nodes can not transmit their data to the BS directly. Moreover, the impact of α, $R_c$ , and $R_n$ on the DARC protocol will be studied with more theoretical analysis to provide the guideline of optimal parameters setting in more general network scenarios.