Ⅰ. Introduction
Many applications of wireless sensor networks (WSN) to the Internet of Things (IoT) find themselves with limited lifespans due to their battery-powered sensor nodes. A WSN needs a sophisticated energy-efficient routing protocol. As an introduction to hierarchical routing scheme, Low Energy Adaptive Clustering Hierarchy (LEACH)[1] is renowned for its simplicity and energy efficiency. Most of LEACH-based hierarchical routing schemes adopt stochastic clustering approaches.[2] Recently, instead of stochastic clustering, there has been research on deterministic clustering which provides far higher energy efficiency with longer network lifespan.[3,4]
In both stochastic and deterministic clustering schemes, the energy saving performance depends on the number of clusters and the cluster formations. In stochastic clustering, the number of clusters is a stochastic variable which varies over rounds. For stochastic clustering routings, the optimum value of expectation of the number of clusters is determined through an approximate energy analysis in the research by Heinzelman.[1] A more thorough energy analysis has been carried out by Kang[5] for the joint optimization of both the number of clusters and the transmission radius of control messages. However, we can hardly find optimization methods for deterministic clustering in the literature.
On the other hand, technologies have continued to advance since the early days of hierarchical routing concept for WSN. The advancement of IC technologies has allowed sensor nodes to operate on low-power consumption in RX/TX circuitry and high-frequency signals as compared with the early days of WSN. This advancement should be taken into account in the optimization of WSN parameters.
In this paper, we investigate the optimization of the number of clusters in load-balanced deterministic cluster routing without control messages,[4] by analyzing the amount of energy dissipation in the sensor nodes. We assume sensor nodes with low-power consumption circuitry and high-frequency microwave signals for long transmission distance. Given the optimum number of clusters, we also investigate the effect of cluster formations on energy optimization by relating the formation to the problem of densest packing of congruent circles in a circle. The verification of our proposed optimization is carried out by computer simulations using the NS2 simulation tool.
Ⅱ. Cluster-based Routing in WSN
We assume there are N sensor nodes which are randomly deployed with uniform density on a circular-shaped sensor field with radius of L[m]. The base station (BS) node is located on the border of the sensor field. All sensor nodes are assumed to be powered by batteries with a limited amount of energy.
If a transmitter node has already known the distance to the receiver node, it uses power control to set the amount of transmit power based on the distance. Transmitting an l-bit message to the receiver at a distance of d[m], a sensor node consumes energy [TeX:] $$E_7(1, d)[\mathrm{J}]$$ by [1]
where [TeX:] $$E_e[\mathrm{J} / \mathrm{bit}]$$ is the energy factor in the circuitry per bit; [TeX:] $$\varepsilon_f\left[\mathrm{J} / \mathrm{bit} / \mathrm{m}^2\right] \text { and } \varepsilon_m\left[\mathrm{J} / \mathrm{bit} / \mathrm{m}^4\right]$$ denote the energy dissipation factors in the transmission amplifier by Friis’ free space model and the multi-path model (2-ray), respectively; and [TeX:] $$\delta=\sqrt{\varepsilon_f / \varepsilon_m}[\mathrm{m}].$$
In the literature from year 2000 or thereabouts, the circuitry energy factor is considered to be [TeX:] $$E_e=50[\mathrm{nJ} / \mathrm{bit}].$$[1] Since then, however, IC fabrication technology has continued advance from MOSFET with 150nm process to modern FinFET with 5nm process, which provides over 240 times the power efficiency.[6] Taking this advancement into account, in this paper, we set [TeX:] $$E_e=0.2[\mathrm{nJ} / \mathrm{bit}]$$ for circuitry energy consumption. On the other hand, considering modern sensor networks,[7] we assume sensor communications on 2.4GHz-frequency signal, which gives us updated factors [TeX:] $$\varepsilon_f=60\left[\mathrm{pJ} / \mathrm{bit} / \mathrm{m}^2\right], \varepsilon_m=0.0013\left[\mathrm{pJ} / \mathrm{bit} / \mathrm{m}^4\right]$$, and [TeX:] $$\delta=\sqrt{\varepsilon_f / \varepsilon_m} \approx 226.2[\mathrm{m}]$$, compared with the parameters in LEACH. [1]
In this paper, we assume the sensor field with radius [TeX:] $$L\lt 100[\mathrm{m}]$$, which is still large-area sensor field compared to typical [TeX:] $$L\lt 50[\mathrm{m}]$$ in most of the WSN literature.[1,2] With [TeX:] $$L\lt 100[\mathrm{m}]$$, we have the maximum transmission distance such that [TeX:] $$2L\lt \delta$$, and thus, we only have to consider the free space model in the energy consumption analysis for the optimization of network parameters.
In cluster-based routing, the time line is divided into rounds. In each round, the sensor nodes sense data which is finally forwarded to the BS node. In a round, N sensor nodes are grouped into clusters. One sensor node in a cluster is elected to be the cluster head (CH) node. Each non-CH node sense data and sends it to its CH node once during a round. The CH node aggregates the data from its non-CH nodes and forwards it to the BS node.
In conventional stochastic clustering, the number of clusters, as a stochastic variable, varies from round to round, and the CH node in a cluster is elected in a stochastic manner, too. Stochastic clustering schemes require a bunch of control message transmissions. In deterministic clustering, however, the number of clusters and the member nodes in each cluster are fixed or predetermined for each round. Naturally, the transmission order among member nodes in a cluster can be pre-scheduled. Consequently, control messages can be eliminated in a deterministic clustering, which results in energy saving.[4]
Ⅲ. Energy Consumption Analysis
In this section, we analyze the energy consumption function for the load-balanced deterministic cluster routing by Kang,[4] in which control messages for cluster formations are eliminated. Since we assume that the sensor field has a circular shape with radius [TeX:] $$2L\lt 100[\mathrm{m}]$$ and the BS node is on the border of the field, the maximum distance, 2L, between any two nodes is given by [TeX:] $$2L\lt \delta$$, with [TeX:] $$\delta \approx 226.2[\mathrm{m}]$$. Thus, the energy consumption in any transmission of [TeX:] $$I_d$$-bit message over a distance d[m] can be modeled as
Energy dissipated in receiving an
[TeX:] $$I_d$$-bit message is
N sensor nodes are evenly divided and grouped into k clusters. For the sake of simplicity we assume that N is an integer multiple of k, so that the number of member nodes in each cluster is N/k. Out of N/k sensor nodes in a cluster, one node is a CH node and the remaining [TeX:] $$\left(\frac{N}{k}-1\right)$$ nodes are non-CH nodes during a round. The area occupied by each cluster is approximately [TeX:] $$\pi L^2 / k$$ Modeling each cluster as a small circle with radius [TeX:] $$R_c[\mathrm{m}]$$, we have [TeX:] $$k \pi R_c^2=\pi L^2$$, and thus
The energy consumption in a non-CH node during a round, [TeX:] $$E_{n o n-C H} \text {, }$$ is for transmitting an [TeX:] $$I_d$$-bit sensor data to its CH node as follows.
where random variable [TeX:] $$d_{t o C H}$$ denotes the distance between the non-CH node and its CH node. Consider a cluster modeled as a circle of radius [TeX:] $$R_c$$ with the center at the origin of the polar coordinate system [TeX:] $$(r, \theta),\left(0 \leq r \leq R_c, 0 \leq \theta \leq 2 \pi\right).$$ We denote the random locations of a non-CH node and its CH node by [TeX:] $$\left(r_n, \theta_n\right) \text { and }\left(r_c, \theta_c\right),$$ respectively. Then, the expected squared distance between a non-CH node and its CH node, [TeX:] $$\overline{d_{t o C H}^2} \text {, }$$ is calculated as
Therefore, the amount of energy consumption in a nonCH node during a round is as follows.
We next analyze energy consumption in a CH node during a round. Each CH node dissipates energy receiving [TeX:] $$I_d$$-bit sensor data from its [TeX:] $$\left(\frac{N}{k}-1\right)$$ non-CH member nodes, i.e., the amount of energy consumption is
Receiving all sensor data, the CH node aggregates the data by consuming the energy
where [TeX:] $$E_{D A}[\mathrm{~J} / \mathrm{bit} / \text { node }]$$ is an aggregation energy factor. Finally, the CH node sends the aggregated data to the BS node dissipating the following amount of energy.
where [TeX:] $$d_{t o B S}$$ is the distance between the CH node and the BS node. Since we assume the BS node resides on the border of the circular-shaped sensor field, the expected squared distance from sensor nodes to the BS node is calculated by
Therefore, from equations (8) through (11), the amount of energy consumption in a CH node during a round is calculated as follows.
With k clusters, there are k CH nodes and (N−k) non-CH nodes in the entire sensor field. Consequently, from equations (7) and (12), we are given by the total energy consumption per round as a function of k in the following
With given N and L, we can find the optimum number of clusters, [TeX:] $$k_{o p t}$$, by solving
respect to k to obtain
Ⅳ. Verification of the Optimization
The analytical results on energy consumption for the optimization are verified using simulations. We consider {N = 240, L = 87[m]} and {N = 120, L = 43[m]} networks varying the number of clusters k between 3 and 20. On NS2 simulation tool, we use the cluster routing simulation program written by the originator of LEACH,[1] except for applying higher transmission signal frequency, 2.4GHz, and lower circuity energy consumption factor, [TeX:] $$E_e=0.2[\mathrm{nJ} / \mathrm{bit}] .$$
Fig. 1 shows the energy consumption per round as a function of the number of clusters, [TeX:] $$E_r(k),$$ derived in eq. (13) in comparison with the corresponding simulation results. Overall, it is shown that the energy curves from analysis Er (k) have a convex-down shape and agree well with the simulations, enough to provide the optimum number of clusters for deterministic cluster routing schemes, which maximizes the network lifespan.
Energy consumption function [TeX:] $$E_r(k),$$ vs. k
We next compare the network lifespan between LEACH and the deterministic cluster routing, with sensor field {N = 240, L = 87[m]}. Initial node energy is set to 0.2[J]. Each routing scheme has been run with its own optimized number of clusters. Given a circular-shaped field {N, L} with the BS node on the border and with
[TeX:] $$2 L\lt \delta,$$ the energy consumption analysis by Heinzelman
[1] yields the optimum number of clusters for LEACH represented as
which gives [TeX:] $$k_{o p t, \text { LEACH }}=9.7$$ for {N = 240, L = 87[m]}. Thus we set k = 10 for LEACH as an optimum value in the following performance comparison. On the other hand, our optimization for the deterministic cluster routing (DCR) gives [TeX:] $$k_{o p t}=12.6$$. Thus we set k = 12 in the simulation for the deterministic cluster routing (DCR).
On the cluster formation with k = 12, we conjecture that it is required to make the shape of each equal-area cluster to have as small perimeter as possible to minimize energy consumption. This is related to two-dimensional packing problem of the densest packing of congruent circles in a circle.
[8,9] In Fig. 2 we show the densest packing of 12 congruent circles in a circle and the 12-cluster formation used in our simulation.
Clustering with k = 12 by densest circle-packing
Fig. 3 shows network lifespan in terms of the number of nodes alive over rounds. Against LEACH, the deterministic cluster routing (DCR) shows the time elapsed until first-node-death of 285 rounds, which is 50% improvement over LEACH which has shown 190 rounds. On the time until last-node-death, DCR shows 720 rounds compared to 380 rounds by LEACH, which is about 90% improvement. The average energy consumption is observed to be 21.9[mJ] per round by DCR compared to 40.9[mJ] per round by LEACH. It is noted that the deterministic cluster routing saves energy consumption by high level of load balancing and by eliminating control messages in the set-up phase in each round. Our optimization maximize the performance of the deterministic cluster routing.
Network lifespans in terms of the number of nodes alive (N = 240)
Finally, we investigate the effect of cluster formations on the energy consumption. With k = 12, we have shown various possible cluster formations in Fig. 4, where each formation has 12 equal-area clusters. Formation 1 corresponds to the densest circle packing as in Fig. 2
Various equal-area cluster formations with k = 12
In Table 1, we show the effect of cluster formations on energy consumption per round, where we have the corresponding packing density calculated for each formation. Given the optimized number of clusters [TeX:] $$k_{o p t}=12$$ for {N = 240, L = 87[m]}, Formation 1 with the densest packing is considered to be the optimum formation yielding the best energy saving performance compared to other formations. We can expect better energy saving performance in formations with higher packing density. It is noted that the energy consumption in LEACH is 40.9[mJ] per round with [TeX:] $$k_{o p t, \text { LEACH }}=10$$ as in Fig. 1. Thus, compared to LEACH, the deterministic cluster routing is more energy efficient even with pseudo-optimum formations, e.g., formations 2, 3, and 4.
Effect of cluster formations on energy consumption
Ⅴ. Conclusion
We have analyzed energy consumption for deterministic cluster routing in order to calculate the optimum number of clusters which maximize network lifespan. We have assumed sensor nodes with high-frequency transmission signals and low-power consumption circuitry reflecting technology advancement. Considering the CH nodes and non-CH nodes in clusters, we investigate energy dissipated in a round. The analysis result shows well agreement with simulations. For the optimum cluster formation with given numbers of clusters, we have adopted the solutions to densest circle-packing in a circle. In performance evaluation, it is shown that the deterministic cluster routing with our proposed optimization outperforms the LEACH in terms of network lifespan.