PUAR: Performance and Usage Aware Routing Algorithm for Long and Linear Wireless Sensor Networks

Abstract

Aiming at requirements of performance and usage in the monitoring of tunnels with the long and linear structure, this work demonstrates a low-energy and quality of service- (QoS-) supported uneven clustering routing algorithm based on the labor cost called PUAR. PUAR realizes uneven clusters by a designed cluster radius related to the distance and the labor cost, with consideration of the residual energy and spatial layout of sensor nodes in the cluster head selection. With QoS support, PUAR uses the quality of link to reduce the packet loss and shortens the total transmitting distance to reduce the average delivery delay in multihop transmission. For the usage requirements of tunnel monitoring, PUAR utilizes the labor cost of replacing batteries to realize local or global energy balance. According to the analysis and simulation results, PUAR is found to achieve low-power consumption and reliable QoS support, and it can also reduce the operating cost of tunnel monitoring.

1. Introduction

Over the past years, as with rapid development of the low-power sensor node (SN) and wireless network such as ZigBee, wireless sensor networks (WSNs) have been used in a wide range of indoor and outdoor applications, such as environment monitoring [1], health care, military warfare, traffic control, and structural health monitoring [2]. WSNs consist of compact-size, relatively inexpensive computational nodes, which measure local environmental conditions through a series of sensors and forward these data to the sink node. Most of SNs depend on battery power so that the power limitation is unavoidable. In addition, WSNs have the characteristics of large scale, self-organization, and distribution. The experiment in [3] shows that, for the same volume of data, the energy consumption of transmission with node radio module is over one hundred times larger than that for computation with node microprocessor. Thus energy is a major factor affecting the design of routing algorithms used in applications of WSN.

Most of the existing routing algorithms are aimed at prolonging the network lifetime through energy-efficient or energy-balanced mechanism. Clustering has been the most widespread technique used to save energy in WSNs [4], since some SNs in the clustered network can be used for cluster heads (CHs) which gather data from their respective cluster members (CMs) and forward data to the sink node. Many routing algorithms realize energy-efficient or energy-balanced mechanism by optimizing CH selection and multihop transmission, such as using residual energy of SNs [5], setting a cluster radius [6], optimizing the cluster number [7], and using relative neighborhood graphs [8]. Although energy is the main constraint which can be saved and balanced by the clustering technology, there are also some other factors that need to be considered in some detail, such as QoS concept and location information. With QoS support including delay and packet loss, some researchers designed delay-sensitive and fault-tolerant WSNs successfully [9] and realized the localized QoS controlling scheme which is useful in WSNs due to its flexibility and scalability [10]. Different from other routing algorithms getting the distance between two SNs through the received signal strength indicator (RSSI) [11], location-based routing algorithms not only can exactly calculate the distance with the location information of SNs but also can get the directivity. Thus these algorithms can shorten the transmission path and improve the geometry of the network, in applications of some special structures, in particular. The location information of SNs is a necessary condition for location-based routing algorithms to optimize the transmission path and node coverage.

In modern times, underground tunnels can be seen everywhere, so structural health monitoring of them is very important. Compared to regular artificial view, WSN is more useful in monitoring the infrastructure, offering accurate data acquisition, rapid data transmission, low-cost investment, and so forth. Thus we need to overcome the difficulties in deploying a WSN for structural health monitoring of tunnel (also called tunnel monitoring in this paper).

WSNs have been widely applied in many areas. For example, a WSN-based water management framework called aqua-net makes water management efficient and reliable [12]. However, the monitoring of tunnel with the long and linear structure cannot use most of these existing routing algorithms and is totally different from the other applications. Although a few researchers have presented some frameworks for the monitoring of scenarios with long and linear structure, such as oil, gas, and water pipeline monitoring [13], smart grid monitoring [14], and rail infrastructure monitoring [15], these lack corresponding routing algorithms based on performance and usage. These existing routing algorithms for linear WSNs mainly focus on improving the routing performance through optimization of transmission path. Tunnel monitoring has two obvious differences which are the long and linear structure and the difficulty in entering into tunnels. Many researchers randomly deployed SNs in a $M*M$ two-dimensional (2D) field when testing the performance of the routing algorithms, because they designed their routing algorithms without any consideration of the external structure of the network. Even some of them did consider this kind of shape in routing algorithms, which may be different from the long and linear structure of the tunnel. For many monitoring scenes with regular shape, selecting a square or similar plane to simulate or test algorithm is a commonly used method. However, the long and linear structure of tunnel will definitely affect the algorithm performance and lead to multihop transmissions. SNs near the sink node need to consume much more energy for relaying data and even influence the transmission performance when the volume of data depending on the number of SNs is big. Moreover, different from other scenarios where it is easy to deploy SNs and to replace batteries, the underground tunnel is so difficult to enter that the cost of battery replacement is high. Some researchers may have alleviated this kind of problems by making SNs die at almost the same time, which has been proved to be useful, and this paper thus uses a similar mechanism. Sometimes this mechanism is taken too extremely, because it is supposed to strictly realize the energy balance. We have found that the topology in the latter half of network life cycle is totally irrational when we use the mechanism of strict energy balance in the routing algorithm, because SNs near the sink node consume much more energy than the other SNs. Because of balancing energy strictly, there will be more CHs far away from the sink node in the latter half of network life cycle, which leads to the long-distance transmission. It is obvious that realizing energy balance strictly in underground tunnel with obvious energy imbalance will dramatically reduce energy efficiency and shorten the network lifetime. This work therefore allows the SNs which need consuming more energy to die early, but it is based on the labor cost of replacing batteries, which meant not only global energy balance but also local energy balance is considered in the routing algorithm presented in this work.

To address these critical issues, this paper presents a performance and usage aware routing (PUAR) algorithm of which the contributions are made up of two aspects, for the scenario with the long and linear structure, in particular. Firstly, aiming at performance requirements of tunnel monitoring, we focus on some factors based on the long and linear structure including energy efficiency, local or global energy balance, and QoS and then integrate them to design the implementation mechanism in PUAR. PUAR has a transformation mechanism of three-dimensional (3D) space which can calculate distance in 3D space by using the radius and 2D coordinate. After all, it is difficult to get a set of $XYZ$ values. Secondly, different from the previous routing algorithms based on the performance requirements only, PUAR is also sensitive to the usage requirement of tunnel monitoring, which is the labor cost of replacing batteries. According to this labor cost, PUAR realizes local or global energy balance instead of single global energy balance to improve the energy efficiency. This method makes PUAR reduce the cost of tunnel monitoring and achieve a good performance of network.

The rest of this paper is organized as follows. In Section 2, we review existing works on routing algorithms for many performance requirements and some applications. Section 3 lists problems of WSNs for tunnel monitoring, space model, energy model, and assumptions. PUAR is described in Section 4. Then we analyze its adaptability to the tunnel monitoring in Section 5. Section 6 shows performance and usage advantages of PUAR in tunnel monitoring. Finally, Section 7 concludes this paper.

2. Correlational Research

To drastically minimize energy consumption, various hierarchical protocols have been designed and used in WSNs. Clustering has been proved to be an energy-efficient method [16]. LEACH [17], which is the first energy-efficient hierarchical algorithm, introduces the concept of “wheel” including the initialization phase and stable transfer phase. CHs are selected randomly to balance the energy dissipation. CHs gather data from their CMs under data aggregation and communicate with the sink node directly. Tong and Tang [5] presented LEACH-B which adopts the same method as LEACH in the first CH selection. However, in the following rounds, it modifies the number of CHs in consideration of node's residual energy to balance the system energy consumption. Liu et al. [18] considered the combination of single-hop and multihop in multilayer clustering routing algorithm (MLCRA). SNs farthest from the sink node transmit data with multihop communication so as to balance the energy consumption. Balancing energy has been found useful to prolong the network lifetime. Younis and Fahmy [19] achieved it by using node density and residual energy as a metric for cluster selection in HEED. Different from LEACH, HEED increases the probability of SNs with higher energy selected as CHs. Unequal clustering size (UCS) [20], which is an uneven clustering algorithm presented in the first place, also can achieve balanced energy consumption by dividing the network into clusters of different sizes.

Recently, QoS support for WSN has increasingly caught the attention that delay and packet loss are main metrics. Energy-balanced routing algorithm based on mobile base station (EBRAMS) is focused on minimization of energy consumption and latency [21]. In data transmission phase, EBRAMS uses parallel communication to decrease the delay. Shan et al. [22] raised the need for time-sensitive data gathering to guarantee minimum delay with maximum network lifetime. They reduce delay by minimizing the routing path from each SN to the sink node. Both delay and packet loss are reduced in the mobile-sink routing for large grids (MRLG) algorithm [23]. MRLG picks one of the downhill and peer nodes with the fewest hops to reach the sink as the relay node after 3 unacknowledged transmission attempts.

Although there have been so many efficient methods available, some researchers realized that the position of SNs affects the performance of the routing algorithm, in scenarios with some special structure, in particular. To be adapted to location-unaware and location-aware WSNs, Yi et al. [24] have presented power-efficient and adaptive clustering hierarchy protocol (PEACH), which either uses location-aware version if the location information of SNs can be detected or uses location-unaware version. Trajectory based forwarding (TBF) [25] used a coordinate system for SNs to calculate distance to their neighbors in which SNs select the closest trajectory to transmit data under the location information.

Some of the routing algorithms mentioned above have been used in different applications, but most of them are suitable for generic WSNs. Environmental characteristics also affect the performance of the routing algorithm so that many researchers have designed environmental monitoring aware routing algorithms based on performance requirements of the application, such as energy efficiency, QoS, and reliable communications. For example, Joe-Air et al. [26] presented a QoS-guaranteed and energy-aware coverage precedence routing algorithm for mission-critical applications of WSNs involving extensive battlefield surveillance, medical healthcare, and so forth. Its root node selection mechanism is based on energy-balancing and coverage-preserving techniques. Saengudomlert et al. [27] designed a multiple access control protocol relying on downstream single-hop and upstream multihop transmissions which allows for contact between survivors and the base stations in disaster areas. However, the performance of these routing algorithms will be affected by the long and linear structure. Toma et al. proposed a bidirectional communication scheme based on the high-level data link control (HDLC) standard for large-scale linear WSNs [28]. Aiming at linear WSNs for freight railroad trains, Zimmerling et al. [29] introduced two routing schemes with good energy efficiency: minimum energy relay routing (MERR) and adaptive MERR (AMERR). Based on Poisson model for the distribution of nodes along a linear path, they set the characteristic distance as a constant. SNs select another node in their downstream neighbors of which the distance is closest to the characteristic distance, to relay data. This always leads to a hangover distance, because transmitting distance is an integral multiple of the characteristic distance in MERR. They also designed an adapted forwarding distance in AMERR. Both protocols save energy efficiently based on minimum energy paths. Jawhar et al. [30] presented a routing framework and corresponding addressing scheme for oil, gas, and water pipeline monitoring. Its multilayer addressing is based on three kinds of nodes. The multihop algorithm used is based on a multilayer addressing scheme. Recently, they proposed using unmanned aerial vehicles to transport the data that is collected by the relay nodes to the sink [31]. The SNs transmit their data to the nearest relay node in a multihop manner. For linear WSNs, the optimization of transmission path is a major means of improving the performance of routing algorithms, but other methods mentioned above in other scenarios may also be useful. Aiming at tunnel monitoring, we implement the performance aware mechanism based on the long and linear structure, which includes energy efficiency, energy balance, and QoS. What is more, the usage aware mechanism is needed in the routing algorithm for tunnel monitoring.

3. Model and Assumption

3.1. Problem Description

Two characteristics of tunnel monitoring introduced above, which are the long and linear structure and the difficulty in entering into tunnels, cause problems which should be addressed in PUAR.

3.1.1. Significantly Heterogeneous Energy Consumption

The phenomenon of heterogeneous energy is the hot spot problem in WSNs, and the long and linear structure makes it more obvious. Suppose that the sink node is located in the center of the monitoring area; we set it as the origin of coordinates. In the case of single-hop transmission, the distance between the SN and the sink node is proportional to the energy consumption of SN. In the case of multihop transmission, SNs near the sink node need consuming more energy to relay more data. Heterogeneous energy consumption is thus contrary to the former.

Due to the long and linear structure and transmitting range, it is not easy for tunnel monitoring to transfer data by single-hop way. To balance energy, PUAR uses residual energy in the CH selection and the multihop transmission and achieves uneven clusters by a designed cluster radius related to the distance from the SN to the sink node and the labor cost. Since heterogeneous energy consumption in tunnels is quite obvious, global energy balance adopted in most of the existing routing algorithms not only may make it convenient to uniformly replace batteries but also may reduce energy efficiency. To avoid that, PUAR adopts local or global energy balance based on the labor cost. Only when the labor is highest PUAR does adopt global energy balance to reduce the cost.

3.1.2. QoS Support Needed

WSNs for the tunnel monitoring require high data accuracy and low delay, while they depend on sensor collection and wireless transmission. QoS support for some special application fields has certain requirements and needs the support of routing algorithms.

Different from traditional QoS parameters mainly based on the concept of end-to-end, QoS support in WSN where a large number of SNs collect data and transmit them to the sink node needs non-end-to-end-based concepts. We thus offer QoS support after data aggregation, namely, in transmitting among clusters or between clusters and the sink node.

We have known that SNs near the sink node need relaying more data, in the long and linear structure particularly. It may also degrade transmission performance including delay and packet loss. Shortening the path of the multihop transmission adopted by PUAR, which is not difficult in the coordinates, can diminish delay. PUAR chooses the path with high link quality to reduce the packet loss.

3.1.3. Different Labor Cost

The labor cost for entering tunnels to replace batteries may be more expensive than the cost of batteries. Meanwhile, the labor cost has a big difference, because it depends on the difficulty of entering the tunnel, the distance between the tunnel and the maintenance site, the opening time for entering the tunnel and the location of the tunnel. However, the battery cost almost shows no change. We then consider the labor cost in PUAR, which has nothing to do with the number of batteries to be replaced but has things to do with the times of entering; balance energy is therefore needed. If the labor cost is 200 yuan each time while the battery cost is 10 yuan, the cost of a large number of batteries may be comparable to the labor cost. If the labor cost is 1000 yuan, routing algorithms must make a change in strategy for reducing the cost. We have also known that global energy balance can reduce the labor cost by reducing the frequency of battery replacement but raise the battery cost by reducing energy efficiency. To reduce the cost and improve energy efficiency, PUAR determines the extent of local energy balance under the labor cost.

3.2. Space Model

Different from some other ordinary structures, the long and linear structure affects the performance of routing algorithms significantly. In the tunnel monitoring, positions of SNs depend on monitoring tasks, which are arranged in the inner ring wall of long and linear tunnel. They directly affect the topology structure of WSN and make it long, linear, and distributed. The long and linear structure of WSNs of tunnel monitoring is as shown in Figure 1.

Figure 1

The long and linear structure.

PUAR is a location-based routing algorithm, but the space of tunnel is 3D. It is difficult to get the whole set of $XYZ$ values or angles. Even if adopting GPS or localization algorithms to get the 3D location, it may not be accurate and a waste of power. However, the distance in the direction of tunnel axes from the SN to the sink node and the length on inner ring wall of the SN are easy to get. We design the transformation mechanism of tunnel space which can calculate the distance in 3D by 2D data mentioned above and radius (R) of tunnel. Besides, 2D data can reduce complexity and the amount of information (see Figure 2).

Figure 2

Coordinate translation from 3D space to 2D plane.

In 2D coordinates, the coordinate-axis X denotes the distance in the direction of tunnel axes from the SN to the sink node, and the coordinate-axis Y denotes the length on inner ring wall from the tunnel bottom to the SN.

In long and linear model, with known nodes $n_i\hspace{0.17em}\hspace{0.17em}(x_i,y_i)$ and $n_j\hspace{0.17em}\hspace{0.17em}(x_i,y_i)$ , computation equation of the practical distance $d_{ij}$ between the nodes $n_i$ and $n_j$ is given by

$$\begin{array}{cc}& d_{ij}=\{\begin{array}{cc}\sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left[\mathrm{2}R\sin \left(\frac{\left|y_i-y_j\right|}{\mathrm{2}R}\right)\right]}^{\mathrm{2}}},\hfill & \hfill \\ \hspace{1em}\left|y_i-y_j\right|\le \pi R\hfill & \hfill \\ \sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left[\mathrm{2}R\sin \left(\pi -\frac{\left|y_i-y_j\right|}{\mathrm{2}R}\right)\right]}^{\mathrm{2}}},\hfill & \hfill \\ \hspace{1em}\left|y_i-y_j\right|>\pi R.\hfill & \hfill \end{array}\end{array}$$

(1)

3.3. Basic Model of Energy Consumption

The model of energy consumption is the same as that of LEACH [17]. Energy consumption of sending data is primarily related to the sending circuit and power amplifier circuit. With reasonable signal-to-noise ratio, energy consumption of sending k-bit data in a range of d meters is given by

$$\begin{array}{cc}& E_{Tx}(k,d)=\{\begin{array}{cc}k\times E_{\text{elec}}+k\times {\epsilon }_{fs}{d}^{\mathrm{2}}\hfill & d<d_{\mathrm{0}}\hfill \\ k\times E_{\text{elec}}+k\times {\epsilon }_{mp}{d}^{\mathrm{4}}\hfill & d\ge d_{\mathrm{0}}.\hfill \end{array}\end{array}$$

(2)

Energy consumption of receiving k-bit data is given by

$$\begin{array}{cc}& E_{Rx}\left(l\right)=k\times E_{\text{elec}}.\end{array}$$

(3)

3.4. Assumptions

WSNs consist of many SNs randomly deployed in different scenarios. The following assumptions are made for this scheme.

• (1)

All SNs are not mobile and aware of their location in the 2D coordinates designed for long and linear tunnels.

(2)

The immobile-sink node has no energy limitations.

(3)

SNs can adjust the transmitting power depending on the distance.

(4)

SNs are assigned a unique ID, respectively, to identify them.

4. Description of PUAR

4.1. Introduction of PUAR

PUAR is based on requirements of performance and usage in tunnel monitoring, which is implemented in different levels of uneven clusters based on the labor cost. Its main objectives include realization of energy-balanced and energy-efficient strategy, realization of effective QoS strategy, and reduction of maintenance cost.

As shown in Figure 3, PUAR algorithm also uses the round mechanism which is similar to that of LEACH and owns two stages in every round: the stage of establishing clusters (Time = $h_t$ ) and the stage of stable work (Time = $w_t$ ). Therefore, time of each round is given by $h_t+w_t$ . In the stage of stable work, SNs send data to the CH once per frame at most during their allocated transmission slot by using a time division multiple access (TDMA) schedule mechanism, and then the CH performs data aggregation, which is adopted in PUAR for its good performance in the tunnel monitoring, and is similar to that of LEACH. To meet requirements of performance and usage in the tunnel monitoring, PUAR achieves the following strategies in the stage of establishing clusters.

Figure 3

A round of network life cycle.

4.2. Clustering Formation

Since PUAR is designed for tunnel monitoring which needs a kind of static WSN, the network initialization is needed only once to save energy in the entire network life cycle. It can be realized as shown in line 1 of the pseudocode description of PUAR algorithm (also expressed as line number in this paper). The network topology is so long that the sink node cannot initialize all SNs in one time. PUAR finishes the phase of network initialization step by step under the relaying of SNs. Firstly, the sink node broadcasts “Init” message in the network, as shown in line 2. Secondly, these SNs, which have received this message, add their own coordinate values in this message and broadcast this processed “Init” message with a certain power in neighbor range (also called neighbor power) for once, as shown in lines 3–5. Thirdly, any SN, receiving the message with the coordinate values added, records these coordinate values in its table of neighbor nodes as its neighbor node. If this SN never broadcasted this processed “Init” message, it should do it with the neighbor power for once after replacing the previous coordinate values with its own coordinate values, as shown in lines 6-7. Finally, all SNs build their respective tables of neighbor nodes like Table 1, as shown in line 8.

Table 1

The table of neighbor nodes.

Node ID (n)	Residual energy	Neighbor node 1 ( $x_{\mathit{1}},y_{\mathit{1}},\mathit{0}$ or 1)	Neighbor node 2 ( $x_{\mathit{2}},y_{\mathit{2}},\mathit{0}$ or 1)	⋯
X	X	$\left(X,X,X\right)$	$\left(X,X,X\right)$	⋯

In this kind of initialization mechanism, SNs in the neighbor radius of a SN are neighbor nodes of this SN, because SNs broadcast “Init” message with the neighbor power which decides the neighbor radius. As shown in Table 1, the table of neighbor nodes saves the ID, residual energy, and the information of neighbor nodes. The information of neighbor nodes is a set of $1*3$ matrixes where the first two values are the coordinate values and the third one is the meaning of CH. If the third one is equal to 1, then this neighbor node is a CH; otherwise it is not a CH.

In the process of CH selection, to save energy and to operate with high efficiency, not all nodes need to participate in it. Therefore PUAR in the forming stage of clusters is divided into three parts, stage of candidate CHs, stage of CHs, and stage of clusters.

4.2.1. The Stage of Candidate CHs

PUAR algorithm sets up two variable scaling factors termed RB and CCH. RB means the percentage of SNs requiring battery replacement. CCH means the percentage of candidate CHs. SNs of which the percentage of residual energy is less than $P_{\text{RE}}$ require battery replacement. $P_{\text{RE}}$ depends on the labor cost, which is valued between 5% and 20%. $P_{\text{LC}}$ represents how expensive the real labor cost ( ${\text{LC}}_R$ ) is. LC_MIN and LC_MAX denote the minimum and maximum labor cost, respectively. The relationship of these variables is as follows:

$$\begin{array}{cc}& \frac{P_{\text{RE}}-\mathrm{5}\%}{\mathrm{15}\%}=P_{\text{LC}},\hspace{1em}{P}_{\text{LC}}=\frac{\text{L}{\text{C}}_R-\text{L}{\text{C}}_{\text{MIN}}}{\text{L}{\text{C}}_{\text{MAX}}-\text{L}{\text{C}}_{\text{MIN}}}.\end{array}$$

(4)

PUAR calculates $P_{\text{RE}}$ using (4), as shown in line 9. RB is always getting larger when PUAR is running, as shown in line 10. CCH, which depends on RB as shown in (5), is calculated in line 11:

$$\begin{array}{cc}& \text{CCH}=\mathrm{0.25}\left(\mathrm{2}-P_{\text{LC}}\right)\left(\mathrm{1}+\text{RB}\right).\end{array}$$

(5)

CH_prop is the percentage of the residual energy, which affects the possibility of becoming a candidate CH:

$$\begin{array}{cc}& \text{C}{\text{H}}_{\text{prop}}\left(n_i\right)=\frac{E_c\left(n_i\right)}{E_f\left(n_i\right)}.\end{array}$$

(6)

In (6), $E_c(n_i)$ and $E_f(n_i)$ are the residual energy and the initial total energy of node $n_i$ . According to $\text{C}{\text{H}}_{\text{prop}}(n_i)$ , PUAR selects CCH ×   $n$ nodes with bigger $\text{C}{\text{H}}_{\text{prop}}(n_i)$ as candidate CHs, as shown in lines 12–16.

We define a set of all candidate CHs termed $S_{\text{TCH}}$ . According to (6), nodes with higher residual energy are more likely to turn into the candidate CHs.

4.2.2. The Stage of CHs

Each candidate CH sets up a cluster radius R based on the distance and the labor cost, which is used to realize uneven distribution of CHs. The cluster radius is smaller than the neighbor radius. The cluster radius of each candidate CH should be proportional to the distance between the SN and the sink node and should be inversely proportional to the labor cost. Suppose that $R_0$ is the largest cluster radius; cluster radius $R_i$ of node $n_i$ is given by (7) and is calculated as shown in lines 17–19:

$$\begin{array}{cc}& R_i=\left[\mathrm{1}-\left(\mathrm{0.2}{P}_{\text{LC}}+\mathrm{0.6}\right){\left(\frac{d_{\max }-d_{iS}}{d_{\max }-d_{\min }}\right)}^{\mathrm{2}}\right]R_{\mathrm{0}},\end{array}$$

(7)

where $d_{\max }$ and $d_{\min }$ represent the maximum and minimum distance between any node and the sink node, respectively; $d_{iS}$ represents the distance between node $n_i$ and sink node; $P_{\text{LC}}$ is an indication of price levels which is a constant value approximately between 0 and 1. According to (7), cluster radius of candidate CHs varies between $(0.4-0.2P_{\text{LC}})R_{\mathrm{0}}$ and $R_{\mathrm{0}}$ .

There are four kinds of SNs: candidate CHs, CHs, ordinary SNs, and candidate CMs. Initial state of this stage includes candidate CHs and ordinary SNs only. CHs and candidate CMs originate from candidate CHs and ordinary SNs, respectively. PUAR circularly calculates $\text{D}{\text{T}}_i$ between candidate CH $n_i$ and SNs including candidate CHs and ordinary SNs within its cluster radius, where $\text{D}{\text{T}}_i$ is given by (8). Cycle: according to the cluster radius and the table of neighbor node, all candidate CHs compute $\text{D}{\text{T}}_i$ in the cluster radius, as shown in lines 21–23. PUAR marks the candidate CH with minimum $\text{D}{\text{T}}_i$ as a CH, marks ordinary SNs in the cluster radius of this CH as its candidate CMs, and then deletes them from their original sets, as shown in lines 24-25. The cycle will continue until none of candidate CHs exists or number of CHs reaches a setting number as shown in line 20, where all CHs have been marked:

$$\begin{array}{cc}& \text{D}{\text{T}}_i=\{\begin{array}{cc}\frac{\sum d_{ij}^{\mathrm{2}}}{\text{nu}{\text{m}}^{\mathrm{2}}},\hfill & \text{num}\ne \mathrm{0},\hfill \\ \infty ,\hfill & \text{num}=\mathrm{0}.\hfill \end{array}\end{array}$$

(8)

4.2.3. The Stage of Clusters

When CH selection is completed, all nodes quit sleep status. Every CH broadcasts an ADV type package with a certain power in its cluster radius as shown in lines 26–28, which inform the surplus nodes that it is a CH. SNs receive this package and record its ID number in sequence. After receiving all ADV packages, SNs select a CH with the minimum distance in their tables of neighbor nodes and send a JOIN_REQ type package containing their own IDs and this CH's ID to request joining in this CH, as shown in line 29. If some SNs cannot receive any ADV type package, PUAR will jump to the stage of CHs after these SNs join in the set of candidate CHs, as shown in lines 30-31. This mechanism can guarantee a high coverage rate, which may only be triggered once at most in every round. Here, CH information in the table of neighbor nodes is updated, as shown in line 32. Uneven clusters of long and linear WSNs have then been formed.

4.3. Multihop among Clusters

PUAR selects relay nodes depending on reduction of energy consumption and realization of QoS support. In this paper, a CH node $n_i$ uses greedy algorithm to select a relay node in the set of neighbor CHs, minimizing the cost function as follows:

$$\begin{array}{cc}& \text{cost}(i,j)=\{\begin{array}{cc}a\frac{E_n\left(n_i\right)}{E_C\left(n_j\right)}+b\frac{N_c\left(n_j\right)}{N_n\left(n_i\right)}+c\frac{d_{ij}^{\mathrm{2}}+d_{jS}^{\mathrm{2}}}{d_{iS}^{\mathrm{2}}}+d{L}_{ij},\hfill & \hfill \\ \hspace{1em}i\ne j\hfill & \hfill \\ +\infty ,\hfill & \hfill \\ \hspace{1em}i=j,\hspace{0.17em}\hspace{0.17em}{d}_{iS}>D_{\text{MAX}}\hfill & \hfill \\ \mathrm{0},\hfill & \hfill \\ \hspace{1em}i=j,\hspace{0.17em}\hspace{0.17em}{d}_{iS}<D_{\text{MIN}},\hfill & \hfill \end{array}\end{array}$$

(9)

where $E_n(n_i)$ denotes the average residual energy of neighboring CHs of CH $n_i$ ; $E_C(n_j)$ denotes the remaining energy of CH $n_j$ ; $N_c(n_j)$ denotes the number of members in the cluster of CH $n_j$ ; $N_n(n_i)$ denotes the average number of members in the neighboring clusters of CH $n_i$ ; $d_{ij}$ denotes the distance between $n_i$ and $n_j$ ; $d_{iS}$ denotes the distance between CH $n_i$ and sink node; $d_{jS}$ denotes the distance between CH $n_j$ and sink node; $L_{ij}$ indicates the bit error rate (BER) of link between CH $n_i$ and $n_j$ , which is significantly influenced by spatiotemporal factors [32]; a, b, c, and d are weight factors which are valued approximately between 0 and 1.

If node $n_i$ is a CH, PUAR will calculate $\text{cost}(i,j)$ ( $j=1,\dots ,n$ ) and then select the neighbor CH with minimum $\text{cost}(i,j)$ as its relay node, as shown in lines 33–38. CH $n_i$ adopts single-hop transmission if j equals i; otherwise it relays data to CH $n_j$ with multihop transmission.

4.4. The Triggering Mechanism of Replacing Batteries

PUAR triggers batteries replacement, based on the experience that more batteries should be replaced each time if the real labor cost is high. Consequently, PUAR models a linear relationship between RB_LC and $P_{\text{LC}}$ as (10) and calculates RB_LC as shown in line 39. If RB is greater than or equal to RB_LC at scenarios with different labor costs, PUAR resets all variables and requests for replacing batteries for SNs within RB; otherwise PUAR just resets all variables as shown in lines 40–43. All batteries need to be replaced uniformly when the labor cost is the highest, which means that global energy balance is adopted:

$$\begin{array}{cc}& \text{R}{\text{B}}_{\text{LC}}=\mathrm{0.7}{P}_{\text{LC}}+\mathrm{0.3}.\end{array}$$

(10)

Knowing that PUAR finishes establishing clusters, it can enter into the stage of stable work as shown in Figure 3. In the next round, PUAR starts establishing clusters again from line 1 of PUAR algorithm, whose pseudocode description is shown in Algorithm 1.

Algorithm 1: PUAR: performance and usage aware routing algorithm.

Input: The location of SNs and the sink node, residual energy of SNs,

labor cost, percentage of CHs, and maximum cluster radius.

Output: Cluster structure and connectivity

Initialization

(1) if it is the first time to initialize network then

(2)  The sink node broadcasts “Init” message

(3)  while (any SN has not broadcasted this message)

(4)   if SNs receive “Init” message from the sink node then

(5)    Broadcast “Init” message added their coordinate values with the neighbor power just once

(6)   else if SNs receive “Init” message from other SNs then

(7)    Record them as neighbor nodes, and then broadcast “Init” message in the same way

(8)  Build their respective tables of neighbor nodes as Table 1

The Stage of candidate CHs

(9) Calculate the proportion of residual energy ( $P_{\text{RE}}$ ) using (4) to decide which SN should be replaced

(10) The percentage of SNs to be replaced batteries(RB) changes over time based on $P_{\text{RE}}$

(11) Calculate the percentage of candidate CHs (CCH) using (5)

(12) for ( $i=\mathit{1}$ ; $i\le n$ ; i++)    //Here, i is the ID of SN.

(13)   Calculate CH_prop( $n_i$ ) using (6)

(14) for ( $i=\mathit{1}$ ; $i\le n$ ; i++)

(15)   if CH_prop( $n_i$ ) belong to the CCH × n biggest CH_prop  then

(16)     $n_i\in S_{\text{TCH}}$

The stage of CHs

(17) for ( $i=\mathit{1}$ ; $i\le n$ ; i++)

(18)   if   $n_i\in {\text{S}}_{\text{TCH}}$   then

(19)    Calculate $R_i$ using (7)

(20) while  (exist candidate CHs and number of CHs is less than a setting value)

(21)   for ( $i=\mathit{1}$ ; $i\le n$ ; i++)

(22)    if   $n_i\in S_{\text{TCH}}$   then

(23)     Caculate D ${\text{T}}_i$ in existing candidate CHs using (8)

(24)   if D ${\text{T}}_i$ is the smallest then

(25)       $n_i\in S_{\text{CH}}=\{\text{CHs}\}$ , $n_i\notin S_{\text{TCH}}$ , {ordinary SNs in its cluster radius}

       $\subset {\text{S}}_{\text{CCM}}=\{$ candidate CMs}, {ordinary SNs in its cluster radius $\}\not\subset S_{\text{OSN}}=\{$ ordinary SNs}

The stage of clusters

(26) for ( $i=\mathit{1}$ ; $i\le n$ ; i++)

(27)   if   $n_i\in S_{\text{CH}}$   then

(28)    CHs broadcast an ADV type package in the cluster radius

(29) SNs join in the CH with the minimum distance

(30) if still has SN which is not a CM of any CH then

(31)   this SN become a CH, and jump to the stage of clusters

(32) Update CH information in the table of neighbor nodes

Multihop among clusters

(33) for ( $i=\mathit{1}$ ; $i\le n$ ; i++)

(34)   if   $n_i\in S_{\text{CH}}$   then

(35)    for ( $j=\mathit{1}$ ; $j\le n$ ; j++)

(36)     if   $i=j$ or $n_j$ is a neighbor CH of $n_i$   then

(37)      Calculate cost( $i,j$ ) using (9)

(38)   Select the neighbor CHs with minimum cost( $i,j$ ) as its relay node

The triggering mechanism of replacing batteries

(39) Calculate $\text{R}{\text{B}}_{\text{LC}}$ using (10)

(40) if   $\text{RB}\ge \text{R}{\text{B}}_{\text{LC}}$   then

(41)   replace batteries and reset all information including sets and tables

(42) else

(43)   reset all sets

(44) end

5. Analysis of Adaptability to the Tunnel Monitoring

5.1. Local or Global Energy Balance

Different from the fact that LEACH generates clusters directly and randomly, PUAR joins the stage of candidate CHs. In this stage, every node calculates its own ratio of residual energy (CH_prop) and chooses nodes with bigger ratio as candidate CHs. It lets nodes with less residual energy avoid consuming more energy, so as to balance energy consumption.

CCH is inversely proportional to $P_{\text{LC}}$ as shown in (5). In CH selection, residual energy which is the key to realize energy balance is considered in CH_prop only, while energy efficiency is the main factor in later stages. Bigger CCH thus means that more SNs with less residual energy may be selected as CHs if energy efficiency is considered, and, since it is not easy to maintain global energy balance, local energy balance is needed. This is one part of local energy balance, and the other part can be seen in the content of uneven cluster. According to the relationship between CCH and $P_{\text{LC}}$ , the scenario with low labor cost which may be near or below the cost of batteries needs local energy balance rather than global energy balance, which consumes more total energy in tunnel. On the contrary, global energy balance may be used to reduce the cost by reducing the frequency of battery replacement in the scenario with high labor cost.

5.2. Uneven Cluster

PUAR has a designed cluster radius $R_i$ to realize the uneven cluster. As can be seen in (7), $R_i$ is proportional to $d_{iS}$ . The nearer the sink node is, the smaller the radius of cluster is, and the bigger the number of clusters is. Suppose that $d_{\max }=100$ , $d_{\min }=1$ , and $R_0=50$ ; the relationship between $R_i$ and $d_{iS}$ is as shown in Figure 4.

Figure 4

The relationship between $R_i$ and $d_{iS}$ .

The most obvious point of long and linear WSNs differing from other kinds of WSNs is that the CH near sink node needs more energy to transmit more data, which is an energy bottleneck. Through realizing uneven cluster, PUAR can bear greater pressure to transmit more data.

Considering the difference of the labor cost, the extent of uneven cluster can be regulated. As shown in Figure 4, the heterogeneity of the scenario with the high labor cost is more obvious than that with the low labor cost, and uneven cluster is necessary to balance energy in tunnel with heterogeneous energy, so global energy balance in the scenario with low labor cost will be damaged. The scenario with the low labor cost can thus properly increase the frequency of replacing batteries to improve energy efficiency so that fewer batteries may be replaced. Consequently, PUAR also realizes local energy balance to cut total expenses on batteries and labor by making different uneven cluster depending on different labor cost.

5.3. Centrality and Overlap of Cluster

If candidate CHs (A, B, C, and D) and ordinary SNs $(1\cdots 10)$ have node distribution as shown in Figure 5, PUAR can calculate their respective DT_i. DT_i is proportional to the sum of squares of distances between node $n_i$ and ordinary SNs in its cluster radius, so ${\text{DT}}_{\text{A}}<{\text{DT}}_{\text{B}}$ and the candidate CH A become a CH. This cluster structure has a good centrality so that it can significantly reduce the transmission path within cluster and prominently reduce the energy consumption.

Figure 5

Centrality and overlap of cluster.

In the next round of CH selection, SNs from number 1 and number 5 are deleted from the set of ordinary SNs, so the DT _i of the candidate CH C is larger. Although the candidate CH C has a good centrality, the candidate CH D will become a CH. This cluster structure has a small overlapping cluster distribution.

5.4. Single-Hop or Multihop among Clusters

As can be seen in the cost function (9), PUAR can embody its advantages in long and linear WSNs.

Firstly, PUAR reduces the possibility of a node with low energy selected as a relay node, because residual energy of CH and $\text{cost}(i,j)$ have an inverse relationship.

Secondly, PUAR balances network traffic. $N_c(n_j)$ is proportional to $\text{cost}(i,j)$ so that a neighboring CH with less members which owns more free memory and less network traffic is more likely to turn into a relay node.

Thirdly, PUAR embodies the linearity and directivity of multihop among clusters. Obviously, $d_{ij}$ is proportional to $\text{cost}(i,j)$ . Shortening the transmission path by choosing a nearer node as a relay node can decrease energy consumption and make multihop among clusters reflect linearity. On the other hand, we also find that $d_{jS}$ is proportional to $\text{cost}(i,j)$ , which means that relay node is mainly selected between node $n_i$ and sink node, so that it can reflect the directivity. The linearity and directivity will shorten the total transmission path of a packet so that PUAR can decrease the delay to improve the performance of QoS.

Further, to avoid the long-distance single-hop transmission which may cause high energy consumption and high packet loss rate and short-distance multihop transmission which is unnecessary, PUAR joins the distance limits $D_{\text{MIN}}$ and $D_{\text{MAX}}$ .

Finally, PUAR reduces the packet loss rate of transmission among clusters. $L_{ij}$ are proportional to that of $\text{cost}(i,j)$ . Multihop among clusters should choose the path with lower BER, to reduce packet loss rate of transmission.

5.5. Replacing Batteries Based on the Labor Cost

In (4) and (10), the labor cost is directly proportional to the residual energy and the number of batteries which need to be replaced. For example, 30% SNs with the remaining 5% power should be replaced when the real labor cost reaches the minimum. If the real labor cost reaches the maximum, 100% SNs with the remaining 20% power should be replaced. Obviously, in some tunnel monitoring with high labor cost, the workers should replace more batteries; even they still have energy, because it can reduce the cost when system is running well.

6. Simulation Analysis of PUAR

6.1. Simulation Platform

Before simulating algorithms on a simulation platform called NS2, we set some relevant simulation parameters as shown in Table 2. Physical layer and MAC layer are based on IEEE 802.15.4. The main parameters are set as shown in Table 2, and other parameters are set to their default values in the standard.

Table 2

Simulation parameters.

Simulation parameter	Setting	Acronym
(1) SN
Initial energy (J)	2 J
Number	100
Distribution	Randomly
(2) Network
Channel type	Wireless channel
Radio-propagation model	Two-ray ground
Network interface type	Wireless physical layer
MAC type	802.15.4
Frequency	2.4 GHz
Data rate	250 kb/s
Energy spent in transmitter/receiver electronics	50 nJ/b	$E_{\text{elec}}$
Constant for free space propagation	10 pJ/b/m2	${\epsilon }_{\text{fs}}$
Constant for multipath propagation	0.0013 pJ/b/m4	${\epsilon }_{\text{mp}}$
Data aggregation energy	5 nJ/b/signal
Maximum transmit distance	150 m
(3) Application
Data packet size	500 bytes
The percentage of CHs	10%
Radius of the tunnel	2.5 m	R
The largest radius of cluster	50 m	$R_{\mathit{0}}$
The minimum labor cost	100	$\text{L}{\text{C}}_{\text{MIN}}$
The maximum labor cost	1000	$\text{L}{\text{C}}_{\text{MAX}}$
The minmum distance of multihop transmission	10 m	DMIN
The maxmum distance of single-hop transmission	100 m	DMAX
(4) Simulation platform
Step time of simulation	10 s
All times of simulation	1800 s

To validate the adaptability of PUAR in the scenario with the long and linear structure, we set up the following simulation scenarios. As shown in the space model, we use a rectangle with 200 m × 16 m to express the wall of tunnel with 2.5-meter radius, of which the sink node is placed at 100 and 8. This is number 1 scenario. Number 2 is a square plane with 56.56 m × 56.56 m, of which the sink node at is placed at 28.28 and 28.28. PUAR then has some comparisons with four kinds of routing algorithms mentioned in the related research. MTE [17] is a lowest-energy consumption algorithm. LEACH [17] is a low-energy algorithm and can balance energy by randomly selecting CH. LEACH-B [5] makes use of residual energy to balance energy significantly. MLCRA [18] achieves the multihop transmission. These algorithms are not based on the system operation cost. To validate the adaptability of PUAR in the scenario with a high cost of battery replacement, we use the maximum labor cost as the default labor cost.

6.2. Distribution of CHs

As shown in Figure 6, PUAR prominently implements uneven clusters in number 1 scenario so that there are more CHs near sink node, and thus it can take more tasks of relaying data.

Figure 6

Distribution of CHs formed by PUAR.

6.3. Network Life Cycle

Evaluation indicators: time of first node's death is termed FNT; time of last node's death is termed LNT.

In number 2 scenario, FNT and LNT of PUAR are similar to those of LEACH, LEACH-B, and MLCRA, as shown in Figure 7. All of them are effective in the usual scenario. However, in number 1 scenario, PUAR is superior, because multihop of PUAR owns the linearity and directivity and neighboring information is different from that of MLCRA, as shown in Figure 8. Multihop is necessary so that MLCRA is better than others except PUAR.

Figure 7

Node survival situation in number 2 scenario.

Figure 8

Node survival situation in number 1 scenario.

When the labor cost is high, FNT value is very important because it can reduce the number of times of replacing batteries and reflects the effect of energy balance. PUAR balances energy by the residual energy, cluster radius, multihop, and labor cost, while LEACH-B is mainly based on the residual energy. In these two scenarios, it can be seen that LNT value of MTE is big, because it focuses on the total energy of consumption only and batteries need replacing frequently. LNT-FNT value represents the abnormal operation time of the monitoring system. A small number of this value is favored, because it is convenient to replay batteries in a uniform manner. In number 1 scenario, LNT-FNT value of PUAR is 80, which is smaller than that of others.

6.4. Energy Efficiency

In number 2 scenario, due to minimal energy consumption mechanism of MTE, it owns the highest energy efficiency, as shown in Figure 9. In number 1 scenario, LNT of PUAR is longer than that of others except MTE for its high energy efficiency, as shown in Figure 10. After 340 seconds, average remaining energy of MTE exceeds that of PUAR, because MTE sacrifices FNT to prolong LNT. According to the results of PUAR and MLCRA, multihop is useful and necessary to realize energy efficiency in the tunnel monitoring. LEACH-B is based on the residual energy apart from heterogeneous energy in the tunnel, of which CHs in the latter half of network life cycle will be on the side with more energy. Due to high energy efficiency of PUAR, in number 1 scenario, in particular, it is therefore a kind of low-energy consumption algorithm and suitable for long and linear WSNs particularly.

Figure 9

Residual energy situation in number 2 scenario.

Figure 10

Residual energy situation in number 1 scenario.

6.5. QoS Performance

PUAR obviously reduces the number of lost packets by choosing the path with lower BER, as shown in Figure 11. In LEACH, CHs immediately transmit data fused to the sink node, so packet loss mainly depends on the transmitting range and network throughput. Apart from these factors in LEACH, multihop of MLCRA may also increase the number of lost packets. Though PUAR also adopts multihop way, BER of link is considered in multihop among clusters.

Figure 11

Number of lost packets in number 1 scenario.

As shown in Figure 12, 100 SNs are randomly deployed in the tunnel and average delivery delay is proportional to the length of the tunnel. As a single-hop routing algorithm, LEACH has a low average delivery delay if network performs well. Multihop is necessary in the tunnel but may add to the total transimission distance. MLCRA is not based on the location of SNs and cannot ensure that total distance is short while next transmission distance is good. PUAR uses the location of SNs and keeps the linearity and directivity of multihop among clusters in the long and linear structure. Average delivery delay of PUAR is reduced significantly, even if it is still slightly bigger than LEACH because of its multihop way.

Figure 12

Average delivery delay in the tunnel with different lengths.

6.6. Labor Cost

PUAR has stipulated the triggering mechanism of replacing batteries. For LEACH and LEACH-B, battery replacement of SNs dying in one hour can be counted as one time. Figure 13 shows the number of times of replacing batteries for number 1 scenario in a year. Because LEACH is an energy-efficient rather than energy-balanced routing algorithm, SNs die in different times. It needs frequent battery replacement, which results in high cost. As a global energy balance, LEACH-B decreases the number of times of battery replacement prominently but cannot fit its cluster structure to the space with the long and linear structure. Its number of times of battery replacement is therefore bigger than that of PUAR which reduces its number by its adaptability in the long and linear structure and local energy balance with variable levels. PUAR (0) denotes PUAR with $P_{\text{LC}}=0$ , as mentioned above. In PUAR, the number of times of replacing batteries is inversely proportional to $P_{\text{LC}}$ . We have known that, with smaller $P_{\text{LC}}$ , the level of local energy balance is higher so that it will better improve energy efficiency. If $P_{\text{LC}}=1$ , PUAR adopts global energy balance to decrease the high labor cost by reducing frequency of battery replacement even through sacrificing a bit of energy efficiency.

Figure 13

The number of times replacing batteries for number 1 scenario in a year.

7. Conclusions

In this paper, PUAR presented focuses on the performance and usage requirements for the monitoring of tunnels with the long and linear structure. Using analysis and simulation techniques, it has been proved that PUAR can achieve low-energy consumption and reliable QoS support and also can decrease the cost of maintaining the tunnel monitoring system. In the long and linear structure, realizing uneven clusters by a designed cluster radius based on the distance and the labor cost and using residual energy in CH selection is necessary to achieve energy efficiency and energy balance. In the stage of CHs, PUAR also uses the spatial layout of SNs to determine the CH, which may be at the center of data and structure. With QoS support, PUAR uses the BER of link to reduce the packet loss and shortens the total transmitting distance to reduce the average delivery delay. Not only these performance requirements which can also be seen in other routing algorithms but may not be based on the long and linear structure, but also the usage requirements such as the labor cost of replacing batteries are considered in the design of PUAR, which makes the tunnel monitoring achieve high performance with lower cost.