A Location-Based Deterministic Load Balancing for Cluster Routing Protocol in Wireless Sensor Networks

Ⅰ. Introduction

In the Internet of Things (IoT) environments, ad-hoc wireless sensor networks (WSN) have larger area with increased number of sensor nodes compared with conventional application specific sensor networks. WSN is a core technology of IoT with a wide range of applications including smart home networking and Industrial Internet of Things (IIoT).^[1,2]

Low Energy Adaptive Clustering Hierarchy (LEACH)^[3,4] is a most widely adopted cluster-based routing protocol for WSN, by virtue of its simplicity and energy efficiency. LEACH and most of its descendant algorithms^[5,6] use several control messages for cluster head (CH) advertisement, join request, and/or message transmission scheduling, etc. These control messages need to be sent with maximum power, in order to be delivered to all nodes over the sensor field.

Referring to a survey paper over a hundred of LEACH-based cluster routing algorithms,^[7] most algorithms use stochastic cluster formation schemes.

Cluster-based routing protocols divide the sensor nodes into an average of K clusters in a stochastic manner, in which the number of clusters may vary from round to round. Moreover, in a round, clusters have different number of nodes. This stochastic nature compromises load balancing and impairs energy performance and the expected lifespan of WSNs.

In the research by Abad,^[8] a network field division method is proposed, in which a self-elected cluster head (CH) node in a sector broadcasts its status to the entire network; then, another node which is self-elected later as a CH in other sector will resign if it finds that it is close to the previous CH node. This approach has a problem of reduced number of CHs in successive rounds. This defect is compensated in the research by Abdul,^[9] in which the number of resigned CH candidate is taken into account to the selection stochastic model.

Recent location-based clustering schemes take advantage of the locations of sensor nodes in order to come up with more energy-efficient routing algorithms. Some location-based schemes feature load balancing among sensor nodes via deterministic clustering. Most existing location-based clustering protocols are with the pre-notification assumption, i.e., each sensor node is assumed to be informed its location in advance before deployment; and/or sensors are assumed to be equipped with GPS, which may not be cost effective. These assumptions have been eliminated in the research by Yoo,^[10] in which a decentralized self-locating scheme is proposed, in which, however, control messages are used. The scheme by Liu^[11] only consider the distance of sensor nodes from the BS node and not the distances among sensor nodes, and thus depends on a stochastic process in electing CH nodes, which may cause less energy-efficiency.

In this paper, we propose a more energy-efficient load-balancing by location-based cluster routing without pre-notification assumptions nor GPS equipments on sensor nodes. In our proposed self-locating scheme, sensor nodes and the BS node collaborate together to find out relative locations of the sensor nodes in the initial phase of sensor network construction. We investigate deterministic cluster formation where control messages are completely eliminated to prolong network lifespan.

Ⅱ. Related Work and Problem Statement

2.1 Notations

In the following table, we have a list of notations used in this paper.

2.2 Energy consumption model

Each sensor node is assumed to perform power control depending on the distance between the transmitter and receiver. We adopt the energy consumption model stated in LEACH algorithm.^[3] Transmitting an l-bit message over a distance d[m], a sensor node dissipates energy [TeX:] $$E_T(l, d)[\mathrm{J}]$$ by

and receiving this l-bit message consumes only energy on the circuitry by

where [TeX:] $$E_e=50$$ [nJ/bit] is the energy in the circuitry per bit; [TeX:] $$\varepsilon_f=10\left[\mathrm{pJ} / \mathrm{bit} / \mathrm{m}^2\right] \text { and } \varepsilon_m=0.0013\left[\mathrm{pJ} / \mathrm{bit} / \mathrm{m}^4\right]$$ denote the energy dissipation in the transmission amplifier needed to achieve an acceptable signal-to-noise ratio according to the free space model by Friis and the multi-path model, respectively; and [TeX:] $$\delta=\sqrt{\varepsilon_f / \varepsilon_m} \approx 87.7[\mathrm{~m}].$$ Given two nodes communicating with each other, we also assume symmetry of the forward and reverse path power dissipation i.e., the same amount of energy is consumed in the forward and reverse paths.

2.3 Conventional Cluster-based routing

There are sensor nodes deployed in a sensor field. All nodes are assumed to have the same sensing ability and the same initial amount of energy. The distribution of the sensor nodes is uniformly random within this area, and the deployment is independent for different nodes. According to the employed routing protocol, the sensing data is forwarded to the base station (BS) node which is the sink node.

In conventional LEACH-based cluster routing protocols, time line is divided into rounds as in Fig. 1(a). Every round starts with the stochastic set-up phase which is composed of cluster head (CH) selection and control message communications. The number of CH nodes in a round is a stochastic variable with the expectation of K. CH selection is followed by three sequential steps of transmitting control messages: (i) CHs for this round broadcast advertisement (ADV) messages; (ii) non-CH nodes transmit join-request (JOIN) messages; and (iii) CHs send TDMA scheduling messages to their members. This ends the set-up phase of a round as in Fig. 1(a).

The set-up phase is followed by the steady-state phase represented as ‘Send DATA’ in Fig. 1, in which each member node of a cluster transmits sensor DATA to its CH. Receiving sensor data from all nodes in its cluster, a CH gathers and aggregates the data, and forwards the aggregated data to the BS node. If a non-CH node has failed to join any cluster in a round, it transmits its DATA to the BS node directly for that round.

Fig. 1.

Time line showing the structure of rounds

2.4 Research Motivation and Problem Statement

The location information of nodes is not taken into account in most conventional LEACH-based routing algorithms. Each round has stochastic set-up phase which is composed of a bunch of control message communications. The control messages usually require large transmission ranges to cover entire sensor field, and, in result, cause a quite amount of energy consumption. Some location-based approaches improve performance with the aid of GPS equipment, which, however, is not cost effective for tiny sensor nodes. The motivation of our work is to make the CH selection and the transmission scheduling in a cluster to be a deterministic process instead of conventional stochastic process. Deterministic schemes can allow us to eliminate control messages. Also, a deterministic CH selection is expected to provide a better load balancing in WSN. These features of deterministic schemes will provide longer network lifespan.

We now have the problem statement as follows. Given sensor nodes without GPS equipments, our goal is to develop a decentralized self-locating method to find out relative locations between sensor nodes by exchanging initial probing packets among all nodes including the BS node. Our proposed scheme is expected to prolong network lifespan by means of eliminating control messages, in set-up phase, as in Fig. 1(b). Specifically, we want to put a new phase called ‘location phase’ before the first round starts in the beginning. We note that the location phase is executed for once in the beginning. A deterministic clustering will allow the network to have a fixed number, K, of clusters with evenly divided number of sensor nodes. The transmission scheduling within a cluster can be also done according to a deterministic process.

Ⅲ. New Location-based Cluster Routing

We assume a circular shaped sensor field in which N sensor nodes are deployed randomly. The radius of the network field is L[m]. The base station (BS) node resides on the border of the sensor field. Each sensor node is assumed to be powered by a battery with a limited amount of energy. The BS node is assumed to have plenty of energy and enough computing capability compared to the sensor nodes.

3.1 Location Phase

We adopt a new stage called ‘location phase’ which is right after the initial deployment of the sensor nodes. First, all nodes including the BS node introduce to each other by broadcasting probing packets called ‘greeting messages’. The greeting messages have a fixed level of power [TeX:] $$P_g$$ which is large enough to cover the entire network field, i.e., power level corresponding to maximum transmission distance of 2L[m]. We have the BS node denoted by [TeX:] $$n_0$$ and N sensor nodes denoted by [TeX:] $$n_i(i=1,2, \cdots N)$$ If all nodes including the BS, [TeX:] $$n_i(i=0,2, \cdots N),$$ receives a greeting message from node [TeX:] $$n_j(j \neq i)$$ with RSS (received signal strength) of [TeX:] $$P_r,$$ then node [TeX:] $$n_i,$$ can calculate the distance, [TeX:] $$d_{i, j},$$ from [TeX:] $$n_j$$ according to the energy model in equation (1) as follows:

Measuring distances to all other nodes through greeting messages, sensor node ni sends the distance information, [TeX:] $$\left\{d_{i, j} ; j=1,2, \cdots, N\right\},$$ to the BS node. Since all sensor nodes also have measured distance to the BS node, they can utilize transmission power control to save energy in this distance-information message transmission.

We consider a circular-shaped sensor field centered at (L, L) of a Cartesian coordinate system as in Fig. 2. The BS node is marked as the star at coordinate (L, 2L). Collecting all distance information [TeX:] $$d_{i, j}, (i, j=0,1, \cdots, N)$$ from the sensor node, the BS node calculates the coordinate of each and every sensor node. If we assume a symmetry channel between a sender and a receiver nodes, we have the same distance [TeX:] $$d_{i, j}$$ measured by node [TeX:] $$n_i$$ as the distance [TeX:] $$d_{j, i}$$ measured by node [TeX:] $$n_j,$$ for the sake of simplicity. However, asymmetry channels in practical situations may produce [TeX:] $$d_{i, j} \neq d_{j, i} .$$ In this case, the BS node may take the maximum of [TeX:] $$d_{i, j} \text{ and } d_{j, i}$$ as the distance between node [TeX:] $$n_i \text { and } n_j.$$

Fig. 2.

Coordinate system for sensor field

The BS node calculates the coordinates of all sensor nodes by triangulation with three reference nodes, [TeX:] $$\left\{n_0, n_f, n_v\right\},$$ explained as follows. The first reference node, [TeX:] $$n_0,$$ is simply taken as the BS node itself at coordinate (L, 2L). For the second reference node [TeX:] $$n_f,$$ consider the sensor node with

which is, in other words, the farthest sensor node from the BS node. The node [TeX:] $$n_f$$ is approximately considered to be on the border of the sensor field across the BS node. The BS node selects [TeX:] $$n_f$$ as the second reference node, and assigns the coordinate (L, 0) to [TeX:] $$n_f,$$ as in Fig. 2. Finally, the third reference node, [TeX:] $$n_v,$$ is selected as the node nearest to the border of the sensor field, which can be obtained as

where the maximum value is expected to be close to [TeX:] $$d_{0, v}^2+d_{f, v}^2 \approx L^2.$$ It is noted that [TeX:] $$n_v$$ is expected to be uniquely determined due to randomness of the location of the sensor nodes in practical situations. The coordinate [TeX:] $$\left(x_v, y_v\right)$$ of the third reference node [TeX:] $$n_v$$ is calculated as follows. Since node [TeX:] $$n_v$$ is taken to be at the boundary of the circle, it is given by

On the other hand, the BS node has already acquired the distance, [TeX:] $$d_{0, v},$$ from itself to node [TeX:] $$n_v$$ through initial greeting messages. It is given that

Solving simultaneous equations (6) and (7), the BS node calculates the coordinate [TeX:] $$\left(x_v, y_v\right)$$ of node [TeX:] $$n_v$$ as

In equation (8), we are given by a plus-minus sign. If we take the plus sign, we assume node [TeX:] $$n_v$$ is in the right half area of the sensor field as in Fig. 2. The minus sign means that node [TeX:] $$n_v$$ is in the left half area. If we take the correct half area for [TeX:] $$n_v$$ by chance, we can calculate exact coordinates of the sensor nodes. If we take the wrong half area for [TeX:] $$n_v$$, then the resulting coordinates are left-right reversed. Since our proposed deterministic protocol is based on the relative distances among nodes but not on the geo-location of sensor nodes, the expected performance is obviously the same no matter if the protocol works with the right coordinates or leftright reversed coordinates. It is noteworthy that if we have at least one out of N sensor to be equipped with GPS, then our proposed algorithm can allow us to implement a geo-location based WSN at the minimum cost.

Therefore, the BS node has all relative distance information among the sensor nodes as well as the three reference nodes, [TeX:] $$n_0, n_f, n_v,$$ whose coordinates are as follows:

For arbitrary sensor node [TeX:] $$n_i,$$ the distances from the reference nodes [TeX:] $$n_0, n_f, \text { and } n_v \text { are } d_{0, i}, d_{f, i} \text {, and } d_{v,i},$$ respectively. By triangulation, the coordinate [TeX:] $$\left(x_i, y_i)\right.$$ of node [TeX:] $$n_i$$ is calculated as follows. With reference nodes [TeX:] $$n_0 \text { and } n_f,$$ we have the following simultaneous equations:

which have two solutions corresponding to the two points of intersection of the circles centered at nodes [TeX:] $$n_0 \text { and } n_f,$$ as in Fig. 3. The coordinates of the two intersection points are

which correspond to the same [TeX:] $$y_i$$ value but different [TeX:] $$x_i$$ values. The distance, [TeX:] $$d^* \text {, from } n_v$$ to the midpoint [TeX:] $$\left(L, y_i\right)$$ of these two intersection points is given by

Finally, in equation (15), the [TeX:] $$x_i$$ values of the coordinate of node [TeX:] $$n_i$$ is determined as

which allows the BS node to find out all the the coordinates [TeX:] $$\left(x_i, y_i\right)$$ of all sensor nodes [TeX:] $$n_i(i=1,2 \cdots, N)$$. For example, in Fig. 3 node ni corresponds to the condition [TeX:] $$d^* \lt d_{v, i}$$ in equation (18).

Fig. 3.

Locating sensor nodes by triangulation

3.2 Deterministic Clustering

The number of clusters in conventional cluster-based routings is a stochastic variable with the expected value of [TeX:] $$\bar{K}$$. In LEACH,^[3] a pseudo-optimization of [TeX:] $$\bar{K}$$ is proposed by energy consumption analysis. For example, [TeX:] $$\bar{K}=5$$ given that N = 100 nodes are in a sensor field with an area of 10,000[m²].

However, in our proposed deterministic clustering, the number of clusters are fixed to be K in every round. With given K, the BS node divides N sensor nodes into K clusters, each of which has the equal number, G = N/K, of nodes. Since we assume uniform random deployment of sensor nodes, it is expected that each cluster has equal area, approximately.

The BS node performs reordering the nodes [TeX:] $$n_i$$ and reassigning the node index i to nodes [TeX:] $$n_i$$, such that nodes in Cluster 1 are denoted as [TeX:] $$\{n_1, n_2, \quad \cdots, n_G\}$$ nodes in Cluster 2, as [TeX:] $$\left\{n_{G+1}, n_{G+2}, \cdots, n_{2 G}\right\};$$ and so on. Consequently, cluster [TeX:] $$k(k=1,2, \cdots, K)$$ has nodes represented with new indices as

This new clustering scheme provides a high level of load-balancing among clusters and/or sensor nodes. The BS node broadcasts the clustering information with newly assigned indices to the entire sensor nodes. We have an example of clustering with N = 100, K = 5 in Fig. 4, where each cluster has G = 20 sensor nodes.

Fig. 4.

Examples of clustering with N = 100, K = 5

In the following, we refer notation [TeX:] $$n_i$$ to nodes with newly assigned indices. In round 1, we have CH node [TeX:] $$n_1$$ for Cluster 1; CH node [TeX:] $$n_{G+1},$$ for Cluster 2, and CH node [TeX:] $$n_{(k-1) G+1},$$ for Cluster [TeX:] $$k,(k=1,2, \cdots, K).$$ In round 2, we have CH node [TeX:] $$n_2$$ for Cluster 1; CH node [TeX:] $$n_{G+2},$$ for Cluster 2, and so on. In round G, CH node [TeX:] $$n_G$$ serves as the CH node for Cluster 1; CH node [TeX:] $$n_{2G},$$ for Cluster 2, and so on. In round G + 1, node [TeX:] $$n_1$$ again serves as the CH of Cluster 1 in a round robin manner. Consequently, in round [TeX:] $$r(r=1,2, \cdots),$$ the CH node of Cluster [TeX:] $$k (k=1,2, \cdots, K)$$ is given by node [TeX:] $$n_i$$ whose index i is determined as

where % is the modulo operation.

3.3 Energy-efficient Routing

Our proposed deterministic clustering does not need ADV and JOIN messages, which are essential to the conventional stochastic cluster formation. The TDMA scheduling messages can be removed as well, by letting the sensor nodes to send data to their CH node in the order of their node index, i, as in [TeX:] $$n_i$$. We have a reduced set-up phase with no control messages as in Fig. 1(b). Thus we can save the energy consumption caused by control messages in conventional schemes. Consequently, in each round, non-CH sensor nodes have only to send their data to their CH node. CH nodes then send the aggregated data to the BS node.

A sensor node running out of battery becomes a dead node which can no longer serve as a CH node of its cluster when its turn comes around. Then sensor nodes in that cluster fail to forward sensing data to the BS in the round. The BS node detects if a node is dead or not by observing received data for several rounds. If the BS node has concluded that a node is dead, then it broadcasts this information to all nodes in the corresponding cluster, in order for other alive sensor nodes to send data directly to the BS in upcoming rounds for which the dead node would have serve as the CH.

Ⅳ. Performance Evaluation

In this section, we evaluate our proposed locationbased deterministic routing scheme by comparing its performance against LEACH algorithm^[3] as well as other location-based routing algorithms in the literature.^[10,11]

We relay on the pseudo-optimization in the literature to determine the number of clusters K. On the NS-2 simulator, our simulations are based on the cluster routing simulation code written by the originator of LEACH,^[4] in which the sensor nodes transmit data at 1Mbps using the 915MHz band. We have 16-bit ADV messages and 16-bit JOIN messages and (16 × (G −1))-bit TDMA messages for other schemes in comparison^[3,10,11] which use control messages. The initial energy of a sensor node is set to be 1[J]. For simulations, consider a circular-shaped sensor field with a radius of L = 56.4[m] corresponding to the area of 10,000[m²], as typical area for performance evaluations in the literature.

With N = 100 and K = 5, we observe the number of nodes alive as round goes by, as in Fig. 5, where each curve is generated from a hundred times of simulations with different seed numbers. Let us we look at the rounds elapsed until 70% of N nodes are alive. Against the conventional LEACH^[3] yielding around 142-round lifespan on everage, our proposed scheme runs over 290 rounds on average, which is an improvement of lifespan by over 100%. On the other hand, the existing location-based deterministic scheme by Yoo^[10] runs 190 rounds which is 33.8% improvement over LEACH, where it is noted that Yoo’s scheme uses control messages every round. Remind that our proposed scheme saves energy consumption by eliminating control messages in the set-up phase in each round. This is why it outperforms over the scheme by Yoo.^[10] Improvement by another location-based scheme in the research by Liu^[11] is minor with 148-round lifespan on average. The scheme by Liu^[11] only considers the distance of sensor nodes from the BS node and not the distances among sensor nodes; and thus depends on a stochastic process in electing CH nodes, which may cause less energy-efficiency than other deterministic schemes. Consequently, we have shown that performance improvement has achieved from both high level of load balancing and reduced control message transmissions.

Fig. 5.

Network lifespan in terms of the number of nodes alive (N = 100, L = 56.4[m], K = 5)

Ⅴ. Conclusion

We have proposed a deterministic clustering scheme taking the location information into account in order to achieve load balancing among sensor nodes. Information on distances among nodes are acquired by letting all nodes including the BS node to exchange greeting messages in the location phase; and the BS node calculates the coordinates of each and every sensor node. Our proposed scheme works in a decentralized manner without any support from external systems such as GPS. Control message transmission energy is saved during the set-up phase in a round by virtue of the deterministic feature in the CH selection and transmission scheduling within clusters.

In performance evaluation, we have carried out extensive simulations. We have shown our proposed scheme provides a dramatic improvement on network lifetime compared with the conventional LEACH algorithm, and also outperforms other existing locationbased routing schemes. Our research can be further extended to investigation on the efficient topology of geometrical clustering as well as on the optimization of the number of clusters.