Multi-Hop Deterministic Cluster Routing in Wireless Sensor Networks

Ⅰ. Introduction

Wireless sensor networks (WSN) require sophisticated energy-efficient routing protocols to prolong the network lifespan. Renowned LEACH^[1] and most of its descendant algorithms^[2] adopt conventional stochastic cluster routing. Instead of stochastic cluster routing, there has been recent research work on deterministic cluster routing^[3,4] with longer network lifespan by eliminating the stochastic nature and/or control messages.

In the research by Choi,^[5] they have proposed a stochastic cluster routing with a multi-hop forwarding among cluster head nodes, based on a local optimization of the energy expense. However, we can hardly find work on multi-hop routing for deterministic cluster routing. In this letter, we investigate the effects of applying multi-hop routing to a deterministic cluster routing^[4] on energy efficiency. Our main contribution is providing a dynamic programming by considering the whole-path energy expense for multi- hop routing to achieve maximum energy efficiency based on global optimization.

Ⅱ. Deterministic Cluster Routing

In this section, we redescribe the existing deterministic cluster routing (DCR)^[4] by the notations used in this letter. There are N battery-powered sensor nodes which are elements of the sensor node set [TeX:] $$M=\left\{n_1,\right.\left.n_2, \cdots, n_N\right\}.$$ Considering the base station (BS) as a special node, let us denote it by [TeX:] $$n_0.$$ We define the extended set of nodes, [TeX:] $$\tilde{M},$$ by adding the BS node to the sensor node set M, as [TeX:] $$\tilde{M}=\left\{n_0, n_1, n_2, \cdots, n_N\right\}.$$ Sensor nodes are randomly deployed on a circular- shaped sensor field with radius L[m].

By exchanging initial greeting messages, each node in [TeX:] $$\tilde{M}$$ has acquired the distance between itself and all other nodes. Let [TeX:] $$d_{i j}$$ denote the distance between nodes [TeX:] $$n_i \text { and } n_j$$ in [TeX:] $$\tilde{M}$$. The distance information [TeX:] $$\left\{d_{i j} \mid n_i, n_j\right. \in \tilde{M}\}$$ among the sensor nodes is reported to the BS. Note that the distance between the BS and each sensor node, [TeX:] $$\left\{d_{0, i} \mid n_i \in M\right\},$$ can also be measured by the BS itself. Gathering all distance information from the sensor nodes, the BS constructs routing paths by performing the functions of deterministic clustering with node re-indexing and deterministic TDMA-scheduling. The resulting deterministic routing information is broadcast to all of the sensor nodes.

N sensor nodes are divided into K equal-size clusters. We have the cluster set [TeX:] $$C=\left\{c_1, c_2, \cdots , c_K\right\}.$$ Each cluster, [TeX:] $$c_k,$$ is a set of G = N/K sensor nodes. For the sake of simplicity, we assume that G is an integer. By the BS, sensor nodes close to each other are assigned into the same cluster. Sensor nodes [TeX:] $$n_i$$ are re-indexed with new node-indices i, such that [TeX:] $$c_1=\left\{n_1, n_2 \cdots, n_G\right\} ; c_2=\left\{n_{G+1}, n_{G+2} \cdots, n_{2 G}\right\} ;$$ and so on. Consequently, cluster [TeX:] $$c_k,(k=1,2, \cdots K),$$ is the set of sensor nodes with new indices, such as

From now on, we refer to nodes [TeX:] $$n_i$$ by the newly assigned node indices i, [TeX:] $$(i=1,2, \cdots, N).$$

On the other hand, the time line of cluster routing consist of rounds, [TeX:] $$r_m,(m=1,2, \cdots).$$ According to DCR,^[4] for round [TeX:] $$r_m,$$ the cluster head (CH) node of cluster [TeX:] $$c_k$$ is determined to be node [TeX:] $$n_{h_m(k)},$$ in which the node-index [TeX:] $$h_m(k)$$ is

where % is the modulo operation. During a round, a CH node receives sensor data from all of its member nodes, aggregates the data, and forwards it to the BS node directly in single-hop transmission.

Ⅲ. Multi-Hop Deterministic Cluster Routing

In this section, we describe our proposed method for applying multi-hop forwarding among the CH nodes to deliver aggregated sensor data to the BS node. Transmitting an [TeX:] $$l_d$$-bit data to the receiver at a distance d[m], a sensor node consumes energy [TeX:] $$E_T\left(l_d, d\right)[\mathrm{J}]$$ by^[1]

where [TeX:] $$E_e$$[J/bit] is the energy factor in the circuitry: [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]$$ are the energy dissipation factors in the transmission amplifier by free space model and the multi-path model, respectively; and [TeX:] $$\delta=\sqrt{\varepsilon_f / \varepsilon_m}[\mathrm{m}]$$. Energy consumption in a sensor node receiving [TeX:] $$l_d$$-bit data is [TeX:] $$E_R\left(I_d\right)[\mathrm{J}]$$ as

In conventional LEACH-based single-hop cluster routing, a CH node transmits the aggregated sensor data to the BS directly. This approach causes the nodes far from the BS to suffer greater energy depletion, which results in a short network lifespan. A multi-hop routing scheme allows a CH node to take other CH nodes as relay nodes in transferring data to the BS in order to reduce energy consumption.

We consider sensor- node energy consumption as follows. When [TeX:] $$l_d$$-bit data is transmitted from sensor node [TeX:] $$n_i$$ to other sensor node [TeX:] $$n_j, \left(n_i, n_j \in M\right),$$ the energy expense [TeX:] $$e\left(n_i, n_j\right)$$ is the Tx energy consumed in [TeX:] $$n_i$$ plus the Rx energy consumed in [TeX:] $$n_j.$$ For transmitting data from a sensor node to the BS, we only consider the Tx energy consumption. We consider Rx energy for transferring data from the BS to as sensor node. Consequently, we have the following for the sensor- node energy expenses as follows.

From eqs. (3) and (4), we have [TeX:] $$e\left(n_i, n_j\right)=e\left(n_j, n_i\right)$$ for [TeX:] $$\left(n_i, n_j \in M\right).$$ We also use the following notation for short.

In a recent investigation into multi-hop cluster routing by Choi,^[5] they have proposed a stochastic cluster routing with a multi-hop forwarding scheme based on a least cost tree by local optimization of the route, as shown in Fig. 1(a), where the next-hop node of node [TeX:] $$n_t$$ is determined by comparing energy expenses between direct forwarding to the BS, [TeX:] $$e_{t0}$$, and indirect forwarding via other CH nodes [TeX:] $$n_p, e_{t p}+e_{p 0}$$, in which the next-hop node [TeX:] $$n_p$$ is assumed to perform direct forwarding to the BS with [TeX:] $$e_{p 0}.$$ This may results in a local optimization scheme.

However, the concept of our approach is shown in Fig. 1(b), where the energy comparison is carried out by comparing the energy expense of the direct transmission [TeX:] $$e_{t 0}$$ with [TeX:] $$e_{t p}+\tilde{e}_p$$ in which [TeX:] $$\tilde{e}_p$$ is the total energy expenses along the whole-path of the optimum multi-hop route from the next-hop node [TeX:] $$n_p$$ to the BS. From this, we expect to achieve global optimization.

We explain our proposed deterministic multi-hop scheme in detail. In the location phase of the deterministic cluster routing, the BS node performs a newly added function called deterministic multi-hop path setting as explained in the following.

Fig. 1.

Multi-hop path selection

For each of the first G rounds [TeX:] $$r_m, (m=1,2, \cdots G),$$ the BS constructs the CH-node list [TeX:] $$H_m$$ with K elements,

in which the node-indices [TeX:] $$H_m(k)$$ for [TeX:] $$(k=1,2, \cdots, K)$$ is determined by eq. (2). The BS constructs the optimal- path energy cost list with K elements, each of which is the total energy expenses along the whole-path of the optimum multi-hop route from each CH node in [TeX:] $$H_m$$ to the BS,

The list [TeX:] $$\tilde{E}_m$$ is initialized to be the energy expenses for direct forwarding to the BS, i.e., [TeX:] $$\tilde{e}_{h_m(k)}=e\left(n_{h_m(k)}, n_0\right)$$ in the beginning. We have another K-element list called the next-hop list [TeX:] $$F_m,$$ in which each element [TeX:] $$F_m[k]$$ is the next-hop CH node for each CH node [TeX:] $$H_m[k].$$ We denote [TeX:] $$F_m$$ as

Each element of [TeX:] $$F_m$$ is initialized to be the BS node, as [TeX:] $$n_{f_m(k)}=n_0,(k=1,2, \cdots, K),$$ in the beginning.

After above initialization, the lists [TeX:] $$\tilde{E}_m \text { and } F_m$$ are updated iterating the following process. For the first element of [TeX:] $$H_{m,} H_m[1]=n_{h_m(1)},$$ which is the CH node of cluster [TeX:] $$c_1,$$ the energy expense for the direct-forwarding to the BS, [TeX:] $$e\left(H_m[1], n_0\right),$$ is compared with the energy expenses through other CH nodes in [TeX:] $$H_m$$ by taking the optimal-path energy [TeX:] $$\tilde{E}_m$$ for the relay nodes. The first element of [TeX:] $$\tilde{E}_m$$, which is for node [TeX:] $$n_{h_m(1)}$$ is updated as

At the same time, the next-hop CH node [TeX:] $$F_m[1]=n_{f_m(1)} \text { for } n_{h_m(1)},$$ whose index [TeX:] $$f_m(k)$$ is updated as well, such that

With this, updating [TeX:] $$\tilde{E}_m[1] \text { and } F_m[1] \text { for } H_m[1]$$ are done. The same procedure is then carried out for CH node [TeX:] $$H_m[2]=n_{h_m(2)}$$ to update [TeX:] $$\tilde{E}_m[2] \text { and } F_m[2],$$ and so on.

In the following, we have a pseudo code for the above explained dynamic programming represented as ‘Updating Loop’. Once the updating processes for all elements of [TeX:] $$\tilde{E}_m \text { and } F_m$$ are done by the first iteration of the updating loop in the pseudo code, we are given the next-hop tree as a local optimization as in Fig. 1(a), because the initial value of the elements in [TeX:] $$\tilde{E}_m$$ was the energy for direct forwarding to the BS. If the BS keeps iterating the updating procedure several times until the list [TeX:] $$\tilde{E}_m$$ converges to its optimum value, it is given by the global optimization as in Fig. 1(b). The global optimization requires several loops to converge, it has more complexity than the local optimization with a single loop in the algorithm, which may affect the real-time routing in stochastic cluster routing with varying CHs round by round. However, since we consider deterministic cluster routing, this multi-hop path selection can be carried out in advance before the network operation starts, without compromising the real-time performance.

The next-hop determination process explained so far is carried out for rounds [TeX:] $$r_m, \text{ or } r_1$$ through [TeX:] $$r_G.$$ We note that all deterministic routing processes from round [TeX:] $$r_1$$ through [TeX:] $$r_G$$ are the same as form round [TeX:] $$r_{G+1}$$ through [TeX:] $$r_{2G},$$ and as in every G rounds. In other words, the constructed routing tree for [TeX:] $$r_m(m=1,2, \cdots \cdot G)$$ is the same as in rounds from then on [TeX:] $$r_s(s=G+1, G+2, \cdots)$$ with s%G =m. We have a pseudo-code of next-hop determination among CH nodes for the first G rounds, [TeX:] $$r_m(m=1,2, \cdots \cdot G)$$ in the following.

Once the BS constructs the multi-hop tree by determining the next-hop nodes of all CH nodes, it broadcasts the information to the sensor nodes. In single- hop cluster routing, once a CH node forwards data generated within its cluster to the BS, then it can go to sleep. However, in multi-hop routing, it cannot go to sleep until the BS, after receiving all required sensor data, allows the CH nodes to go to sleep.

From simulations, it is observed that our proposed dynamic programming scheme converges to the same routing path as Dijkstra’s routing algorithm^[6] which also yields global optimization.

Ⅳ. Performance Evaluation

We evaluate our proposed multi-hop deterministic cluster routing (MH-DCR) by comparing it to the deterministic cluster routing (DCR)^[4]. Simulations are carried out on NS-2 in the scenario of {N = 240, L = 87[m]} with K = 12 clusters. Simulation parameters are as follows^[1,4]. We set [TeX:] $$l_d=500[\mathrm{bits}]$$ and [TeX:] $$E_e=0.2[\mathrm{nJ/bits}]$$ Data is transmitted at 1Mbps on 2.4GHz signal, which gives [TeX:] $$\varepsilon_f=60\left[\mathrm{pJ} / \mathrm{bit} / \mathrm{m}^2\right] \text { and } \varepsilon_m=0.0013\left[\mathrm{pJ} / \mathrm{bit} / \mathrm{m}^4\right].$$ Every node has initial energy of 0.2[J].

We show the number of nodes alive versus rounds in Fig. 2. For reference, we have shown the result of the conventional LEACH^[1]. Both the deterministic cluster routing (DCR)^[4] and our proposed multi-hop deterministic cluster routing (MH-DCR) run more rounds compared with LEACH. We look at running rounds until 200 nodes are alive as shown by the dashed horizontal line. In the MH-DCR multi-hop setting algorithm, the updating procedure for [TeX:] $$\tilde{E}_m \text { and } F_m$$ converges after 4 iterations as global optimization. In the figure, MH-DCR with local optimization with 1 iteration is observed to have run about 475 rounds by the 200-node criterion. The result of global optimization for MH-DCR yields about 515 rounds, which is 8.4% improvement over the local optimization in our simulation scenario of {N = 240, L = 87[m], K = 12}. DCR shows about 340 rounds by the 200-node criterion. MH-DCR schemes, running at least 475 rounds, yield more than 38% improvement over DCR. From simulations, our proposed method shows efficiency with energy expenses of 16.4[mJ] per round as in MH-DCR(global), and outperforms DCR with 21.9[mJ] which is a single-hop scheme. If we look at the lifetime as the time until the last-node’s death, DCR shows the longest result, which is often observed when comparing single-hop algorithms with multi-hop algorithms. This can be expected from the fact that the nodes near the BS have short lifespan by relaying the data with multi-hop schemes, whereas the the nodes near the BS has much longer lifespan with single- hop schemes.

Fig. 2.

Network lifespans in terms of the number of nodes alive (N = 240)

Ⅴ. Conclusion

We have investigated into the effects of applying multi-hop to the deterministic cluster routing on energy efficiency. We consider the whole-path energy expense for multi-hop routing to achieve energy efficiency based on global optimization. The global optimization is achieved by iteration of updating the list of total energy expenses along the whole-path of the optimum multi-hop route from each CH node to the BS. Our multi-hop relaying improves existing deterministic cluster routing in terms of network lifespan, which is shown by simulations.