Energy-aware and load-balancing cluster routing protocol for wireless sensor networks in long-narrow region

Abstract

Wireless sensor networks (WSNs) are envisioned for a number of application scenarios. However, the few focus on the features of a specific system, and rarely report about the characteristics of the target environment. This article presents an unequal clustering and cross-layer routing protocol for environmental monitoring based on WSNs under coal mine laneway. Considering the long and narrow structure of the road tunnels, a chain-type topology is developed to achieve an application-aware system. In order to improve the performance and prolong the lifetime of the network, an energy balancing strategy is deployed in the cluster head nodes. The mechanism of unbalanced energy exhaustion among cluster heads in the whole network is theoretically analyzed, and the effective density function (ρ (x)) is calculated, which is used for cluster head election in order to make the distribution density of cluster heads correspond to. In addition, a cross-layer routing algorithm is presented, which considers routing and MAC layers information to reduce the congestion, increase the packet delivery ratio, and minimize the energy usage. Simulations show that the proposed scheme outperforms other algorithms in terms of energy balance of average node, prolonging the network lifetime and better network throughput.

Keywords

Energy balancing unequal clustering distribution density of cluster heads cross-layer routing

1 Introduction

WSN (Wireless Sensor Network) has been applied to environmental monitoring of underground coal mine (monitor temperature, humidity, gas density, wind speed, smog and other related data in roadway, driving face and gob area). With the advantages of lower price, easy and fast deployment and self-organizing network, WSN is more suitable for rescue disaster relief and large-scale deployment in underground coal mines. However, underground coal mines suffer complex topographical and geological conditions. For example, underground coal mine structures are restricted by narrow roadway and related geological features of coal rocks on roadway walls are very complicated. In this view, it is of notable significance for intelligent mine constructions to study how to optimize network performance and data transmission and create stable and reliable WSN. In reference [1], the study has been launched towards node deployment according to topological relations in undereground coal mines, whereas the node deployment encounters a great challenge with increasing number of node and precision of data sampling. In reference [2], WSN on coal faces is utilized so as to position movable targets and extend network life based on the analysis of relay node and node energy consumption. In reference [3], the clustering technology is applied to divide the network into hierarchical topology for networking control in response to specific applications of WSN in mine roadway monitoring systems. Due to the spatial structure of narrow on both sides and long distance for underground coal mine roadway, WSN nodes will be deployed into a belt accordingly. In consideration of selective frequency attenuations due to reflection, diffraction and dispersion of electromagnetic waves by coal rocks on roadway walls and also due to multi-path transmission, the single-hop link is unable to adapt to the complex environment in underground coal mine roadway. Under such a circumstance, the clustering multi-hop network can better meet needs for underground network transmission in comparison with planar network [4 –6].

In multi-hop networks, the cluster head (CH) acts as the network routing node, and undertakes the function to forward the data from the other clusters. Therefore, it constitutes the upper backbone network of WSN. Considering the Sink node as the data collection center, the data flow follows the many-to-one model which results in premature death of the cluster heads nearby Sink for their heavy communication loads, and the fracture phenomenon of the network topology structure can further reduce the network stability and lifespan. In [7], the authors proposed Unequal Clustering Size (UCS) model to solve the problem of unbalanced energy consumption, but they considered heterogeneous network, where cluster head is a super node, which is not a general understanding of the topology. Considering that some cluster heads near or far from the Sink take a heavier energy burden, schemes in Energy Efficient Clustering Scheme (EECS) [8] and Energy-Efficient Unequal Clustering (EEUC) [9], are proposed to form clusters with different sizes in which energy consumption load of CHs is heavier. In EEUC scheme, CHs are elected by localized competition, the distance between node and Sink, and residual energy of node are calculated as a weighting parameter which is defined for CH election. However, the path in the routing CHs also depends on distance cost and residual energy, without any consideration of buffer queue backlog and packet loss, which may trigger significant amount of data retransmission thus causing the wastage of resources.

Considering the imbalance of energy consumption among CHs that is caused by the difference in the data transmission loads between the CHs in different regions around the Sink node, an an Energy-Balance Unequal Clustering Routing Scheme (EBUCR) be designed. Compared to the existing studies, the major contribution of this paper work is:

The energy consumption equilibrium model is constructed by analyzing of the asymmetry of the data transmission, and the effective CH distribution density is proposed as an important metric for cluster head election.

Cross-layer design is applied to inter-cluster routing after taking into account the node load balancing to prevent accumulated data causing network congestion during data transmission and avoid unexpected resource waste and network delay.

2 System model and problem description

2.1 Network model

Wireless sensor network node distribution can be divided into random distribution and even distribution with a certain density. Sensor nodes are evenly distributed according to a specific density in order to promote the precision, accuracy and integrity of sampling data in monitored laneways. In the network considered in this paper, there are N sensor nodes which are evenly distributed with random in the monitoring area. While the network should obey the following rules:

Wireless sensor node will be fixed after the even deployment;

All sensor nodes in network are the same, having a unique ID, the same status and role and the limited initial energy E₀;

Single-hop communication mode of sensor node can be adopted in the inner clusters, while multi-hop communication mode with cluster head as the routing node is employed between the clusters. Data fusion with the fusion rate θ will be considered in the inner cluster for data transmission, while the data fusion between the clusters is not;

The transmission power of the node with same type in the network can be adjusted according to the requirement. Node has sensing radius R_s and the data transmission radius R_t, (R_t > R_s);

There is only one base station in the network, which is fixed at the entrance or exit of a coal mine laneway and connected with the underground Ethernet.

Figure 1(a) shows various sensors placed in the 3-D real environment in tunnel. Figure 1(b) shows nodes in the vertical plane projection. To facilitate analysis, the two walls of the tunnel are unfolded and a 2-D representation of the 3-D deployment is constructed on the inner surface of the tunnel, as depicted in Fig. 1(c). In practice, the relationship between neighboring nodes in the 3-D real environment is the same as in the 2-D representation, the network model will be developed and the analysis will be performed in 2-D coordinates.

2.2 Wireless communication model

The wireless communication energy consumption model used in this paper is similar to the LEACH [10]. Assuming a node transmitting k-bit packet over distance d, the energy consumption can be described as Equation (1). $E_{Tx} (k, d) = {\begin{matrix} {ke}_{elec} + k ɛ_{fs} d^{2}, & d < d_{0} \\ {ke}_{elec} + k ɛ_{mp} d^{4}, & d \geq d_{0} \end{matrix}$ (1)

In this equation, e_elec stands for the energy consumption of the radiating circuit. If the transmitting distance of the radiating circuit is less than threshold (d₀), the power amplification loss will use a free space model. When the distance is more than (or equal to) the threshold d₀, multi-path attenuation model will be adopted. The parameters ɛ_fs and ɛ_mp are the energy required in these two models for power amplification. The energy consumption of the nodes for receiving k-bit data is $E_{Rx} (k, d) = E_{Rx - elec} (k) = {ke}_{elec}$ (2)

2.3 Imbalanced energy consumption of inter-cluster

The existing studies demonstrate that the hierarchical topology structure can achieve a better network performance than the plane structure, while in the hierarchical network structure, the clustering technology has the strong adaptability to environment changes. Aiming at the problem of maximizing the network life, many aspects have been discussed in the recent studies, including the clustering algorithm complexity, cluster formation mechanism and the optimal number of cluster head generation. Uneven clustering is considered as a better way to balance the network energy consumption, but it is difficult to achieve the perfect condition for all these methods. Available uneven clustering is not only embodied on the simplification of uneven cluster rules, but also can be used for changes in the network environment. This paper, from the perspective of the data transmission quantity, analyzes the problem of imbalance data transmission in multi-hop transmission. Because the communication distance of inter-nodes is the straight-line distance, this paper only takes the simplified model from the perspective of one-dimensional coordinates. As shown in Fig. 2, sensor nodes were deployed in a region A, and A is further divided into n sub-regions, A = [A₁, A₂, ⋯ A_n] where, the greater numerical value of n means the shortest distance from the Sink nodes. As the network is based on multi-hop transmission, in region A_n, the CHs not only sent the data collected from its own region, but also forward the data from region A_n-1. The data quantity sent in region A_n is $D_{A_{n}} = \sum_{i = 1}^{n - 1} D_{A_{i}} + B_{A_{n}}$ , where B_{A
_i} means the data which is collected from region A_n-1, and should be sent to the CHs. It must be noted that D_{A
_i} > D_{A
_i-1}, from Section 3.2, the energy consumption of CHs is calculated as E_total (k, d) = k (E_Tx + E_Rx), E_{A
_i} (D_{A
_i}, d) = D_{A
_i} (E_Tx + E_Rx), E_{A
_i} > E_{A
_i-1}, so it shows that in different regions, the energy consumption of CH will be different. The wireless sensor network cluster head in cluster network architecture consumes maximum energy and exhausts earliest. This problem can be solved by equalizing the amount of data transmission in different regions, thus it can prevent the early exhaustion of the nodes closer to Sink nodes. In order to maximize the network life, the problem can be summarized as the following mathematical model Equation (3).

$\begin{matrix} \max & {T_{net}} \\ s . t . & T_{net} = min [T_{A_{n}}, T_{A_{n - 1}}, \dots, T_{A_{1}}] \\ T_{A_{n}} = Arg (E_{A_{n}} (t) = {Qch}_{A_{n}} E_{0}) \\ \frac{E_{A_{n}}}{{Qch}_{A_{n}}} = \frac{E_{A_{n - 1}}}{{Qch}_{A_{n - 1}}} = . . . = \frac{E_{A_{1}}}{{Qch}_{A_{1}}} \end{matrix}$ (3)

Where Qch_{A
_n} is the generation number of the cluster heads in region A_n, which is related to the cluster head formation density, regional distance, the distance between Sink node and the regional area. The problem of cluster head nodes formation density will be introduced in Section 2.4.

2.4 Imbalanced energy consumption of inter-cluster

Through constructing a mathematical model, this paper analyzes the problem of imbalance in the energy consumption of cluster head nodes. Assuming that the cluster head nodes generated in the systemic network model is ℂℍ, and the routing node distribution is as shown in Fig. 2. The base station or Sink node is at the origin of coordinates, it can be noticed that the network topology is a chain-type. It is supposed that the number of cluster head generated in the network is M, M = Np₀, p₀ is the cluster head formation rate. Generally to describe the data arrival rate, there are three cases used in related studies: Poisson arrival, deterministic arrival, and even distribution arrival. This paper adopts the deterministic arrival pattern, i.e., assuming the data rate generated in the slot time of routing node is λ bit. The energy consumption of sensor nodes mainly focuses on data transmission. Assuming the energy consumption to send 1 bit data is e_Tx (1, d), to receive 1 bit data is e_Rx (1, d), the communication distance for cluster head achieved to the next hop is l/2, L/2 is the length of the total network deployment area, S is the distance between cluster head nodes that are closer to the Sink node, ρ (x) stands for the density function of cluster head node whose distance to Sink is x, and ρ (x) determines the number of cluster head distribution or cluster head formation density in different areas, the number of cluster heads in region A is ${Qch}_{A_{n}} = \int_{s - l / 2}^{s + l / 2} ρ (x) dx$ (4)

It can be learned from Fig. 2 that, in the t time slot, when the nodes in the regions to the right side of A_n send data, they should forward the data through the nodes in region A, so the energy consumption in region A_n is $\begin{matrix} E_{A_{n}} (t) \\ = (\int_{s + l / 2}^{L / 2} λ ρ (x) dx (e_{Tx} + e_{Rx}) + \int_{s - l / 2}^{s + l / 2} e_{Tx} λ ρ (x) dx) E_{0} \end{matrix}$ (5)

The energy consumption in regions on the right side of region A is $\begin{matrix} E_{rAn} (t) \\ = (\int_{s + l / 2}^{L / 2} λ ρ (x) dx (e_{Tx} + e_{Rx}) - \int_{s - l / 2}^{s + l / 2} e_{Rx} λ ρ (x) dx) E_{0} \end{matrix}$ (6)

The number of cluster heads generated to the right side of region A is ${Qch}_{{rA}_{n}} = \int_{s + l / 2}^{L / 2} ρ (x) dx$ drags the energy consumption of nodes in the systemic network tends to the equilibrium, and average energy consumption of each node in region A is approximately equal to the cluster head node to its right regions; which is mathematically given by $\frac{E_{A_{n}}}{{Qch}_{A_{n}}} = \frac{E_{{rA}_{n}}}{{Qch}_{{rA}_{n}}}$ (7)

Due to the even distribution of the nodes in regions, there is a negligible difference in density. In the wide areas, when s >> l, there is s + l/2 = s - l/2 = s. $\int_{s - l / 2}^{s + l / 2} ρ (x) dx = \int_{s - l / 2}^{s + l / 2} ρ (s) ds$ (8)

By substitute Equation (8) into Equation (7), ${\begin{matrix} \frac{\int_{s + l / 2}^{L / 2} λ ρ (x) dx (e_{Tx} + e_{Rx}) + \int_{s - l / 2}^{s + l / 2} e_{Tx} λ ρ (x) dx}{\int_{s - l / 2}^{s + l / 2} ρ (x) dx} \\ = \frac{\int_{s + l / 2}^{L / 2} λ ρ (x) dx (e_{Tx} + e_{Rx}) - \int_{s - l / 2}^{s + l / 2} e_{Rx} λ ρ (x) dx}{\int_{s + l / 2}^{L / 2} ρ (x) dx} \\ \int_{s - l / 2}^{s + l / 2} ρ (x) dx = \int_{s - l / 2}^{s + l / 2} ρ (s) dx \\ e_{Tx} (1, x) = {\begin{matrix} e_{elec} + ɛ_{fs} x^{2}, & x < d_{0} \\ e_{elec} + ɛ_{mp} x^{4}, & x \geq d_{0} \end{matrix} \\ e_{Rx} (1, x) = e_{Rx - elec} (1) = e_{elec} \end{matrix}$ (9) $\begin{matrix} ρ (x) \\ = Arg (\begin{matrix} \frac{\int_{s + l / 2}^{L / 2} λ ρ (x) dx (e_{Tx} + e_{Rx}) + \int_{s - l / 2}^{s + l / 2} e_{Tx} λ ρ (x) dx}{\int_{s - l / 2}^{s + l / 2} ρ (x) dx} \\ = \frac{\int_{s + l / 2}^{L / 2} λ ρ (x) dx (e_{Tx} + e_{Rx}) - \int_{s - l / 2}^{s + l / 2} e_{Rx} λ ρ (x) dx}{\int_{s + l / 2}^{L / 2} ρ (x) dx} \end{matrix}) \end{matrix}$ (10)

The result can be simplified as Equation (11) $ρ (x) = (L - 2 x) \frac{λ (e_{Tx} + e_{Rx})}{2 {lE}_{0}}$ (11)

It can be found that, the cluster head density has a decreasing relationship with the distance to the Sink node in order to reach the average energy consumption of the cluster heads within the area. It is summarized that, if the energy consumption of each node in a network needs to be balanced, the distribution of cluster head nodes should follow the uneven distribution rule based on the distribution density ρ (x) to achieve the balanced energy of inter-cluster routing nodes. In [11], the authors proved that it is impossible to achieve absolute balance of the network energy consumption based on the uneven distribution, but if cluster head nodes are unevenly distributed with the distribution density ρ (x), they can achieve suboptimal energy consumption balanced. This density is called the effective density, it will be referred to as a key reference parameter for the selection of cluster head then and as the basis of cross-layer routing.

3 Cross-layer routing under unequal clustering

The spatial feature of being narrow and long in underground coal mine laneway makes WSN topology different from traditional round regional model, the distribution of whose nodes resemble the belt model much more. Due to the relative long distance and with rising number of hop during inter-cluster multi-hop transmission, the data to be transmitted in the region are also continually increasing. Consequently, data transmission congestion occurs. This paper adopts the cluster head uneven distribution scheme, and considers the effective generation density as an important parameter of cluster head election to generate uneven distribution of cluster head nodes in the upper layer backbone network; as a result, it provides more routing nodes as the basic platform for data accumulation near the Sink node in multi-hop transmission. However, effective routing mechanism of inter-cluster can be implemented for the data equilibrium transmission, and then achieve the fairness of data transmission and efficiency of end-to-end throughput.

In order to achieve the fair selection of different routing nodes in the service transmission, and effectively prevent the congestion caused by the data backlog, the current state of each node needs to be detected at real-time and will be considered in the process of route elections. Traditional design of a layered network protocol, influenced by variable characteristics of wireless network, is not an effective design method [12, 13]. This is mainly because the traditional OSI layered model cannot carry out the overall management on wireless network resources, leading to poor balance of network traffic load, as well as the unfair resource allocation. A cross-layer design, from the overall situation [14, 15], considers a compromised performance of all aspects, and further improves the network performance. The cross-layer approach is adopted in this paper, as shown in Fig. 3(a), where a cross-layer management module is added in the network layer, logical link layer and MAC, in which the available bandwidth information of MAC and residual local capacity can be fed back to the network layer routing agents. Afterwards, through information sharing, the residual energy information of node in physical layer can be provided to network layer and data link layer. All of these set up the criterion for the selection of route in network.

3.1 Cluster formation strategy

In the primary stage of the network, Sink node broadcasts a message to every node in the network at the highest power to make sure every node can receive messages and work out the distance from a node to Sink according to the location algorithm. By using the cluster head “rotation” approach, the time-space of cluster head rotation can be set in advance according to specific situation of the number of cluster. All nodes select a threshold to judge whether they can serve as cluster head. A random number a (a ∈ [0, 1]) generated by node is compared with a threshold value. If a is less than the threshold, then the node can be elected as cluster head, otherwise it cannot serve as cluster head. Threshold value T_i is given as Equation (12). $T_{i} (r) = P [α (E_{0} - E_{i} (r)) / E_{0} + (1 - α) ρ_{i} (d) / ρ_{max}]$ (12)

In which P, the initial probability as the nodes becoming cluster head, is set as the cluster head election threshold. The optimum value of α in range [0, 1], is set to 0.3 after many experiments; the simulations discussed in the later part of paper will provide further explanation. E_i (r) is the residual energy of the r around the current node, E₀ is the initial energy, ρ_i (d) is the density value of uneven distribution of nodes in the ideal state and ρ_max is the largest density value of cluster head generation. The value of ρ_max can be obtained by setting the value of parameter s into Equation (11). The introduction of weight (E_i (r)/E₀) can avoid the probability of cluster head node being a low energy node, and increase the probability of cluster head node being a higher energy node. On contrary, the increase of weight (ρ_i (d)/ρ_max) can raise the possibility of the transformation of the nodes near Sink to cluster head; therefore, to make more CHs close to Sink node, the value must be higher. Thus, it forms the uneven distribution of the nodes in upper backbone network which is constituted by CHs based on distribution density ρ_i (d). After cluster head is elected, it broadcasts message (be elected as CH) to the neighboring nodes. All the nodes without being elected as the cluster heads can join the cluster selectively according to the received radio signal strength, thus forming the clusters of Graph Voronoi structure in network. The network enters into stable stage after the completion of clustering, data transmissions are realized between clusters through CSMA protocol based on channel contention. Specific cluster formation process is described in Fig. 3(b).

3.2 Cross-layer parameters selection

The data that is collected by cluster head from the inner member nodes will be sent to the Sink node via the inter-cluster communication after data fusion. The choice of path in routing mechanism also plays an important role in balancing the energy consumption. When the shortest path is taken or minimum hop is selected as the choice, the energy consumed by the cluster heads will be significantly high, resulting in the emergence of “energy hole” in network.

Definition 1. During the process of establishing routing between clusters, the set of next hop candidate routes (i.e. candidate CHs) is CH_i . R_candidate.

$\begin{matrix} {CH}_{i} . R_{candidate} \\ = {\begin{matrix} {CH}_{i} | d ({CH}_{i}, BS) < d ({CH}_{j}, BS) \\ \begin{matrix} \begin{matrix} AND & d ({CH}_{i}, {CH}_{j}) \leq {bCH}_{i} . R_{c}) \end{matrix} \end{matrix} \end{matrix}} \end{matrix}$ (13)

CH_i . R_candidate is the smallest non-null set for b. Without b, CH_i . R_candidate = φ, CH_i will directly communicate with Sink or BS in a single-hop mode. Because of the asymmetry transmission among CHs, it is easy to emerge congestion and uneven resource distribution in the network. For example, the congestion and energy “hot spot” can appear in one of the shortest paths. So, CH_i should consider the node status information of the MAC layer in the candidate routing nodes CH_i . R_candidate.

Through the cross-layer design, EBUCR considers two factors in route selection: 1) Available Link Bandwidth (ALB:CH_i _ BW); 2) Available Queue Buffer Length (AQBL:CH_i _ Expect _ load). The larger values of CH_i _ BW and CH_i _ Expect _ load means the node transmission ability is strongest. During the transmission stage, the node’s status can change with an increase in load and the extension of time. The communication tasks taken by each CH are not the same. Using the two parameters introduced in the design, the routing nodes can reflect the real-time status of nodes in the network transmission through the underlying information of the protocol.

The busy or idle status of the node transmission channel can be detected using the virtual carrier sensing in MAC layer to calculate the available bandwidth. By means of IAB (Improved Available Bandwidth estimation) algorithm proposed by Haitao [16], the busy status caused by transmission of node itself or nodes around can be detected. In order to accurately calculate the CH_i _ BW, ALB is defined as ${CH}_{i}_BW = (1 - \frac{DIFS + B}{T_{total}}) (\frac{T_{total} - T_{busy} - T_{sen s e}}{T_{total}})$ , where T_total is the total sampling period of the information channel, T_busy is the time of “busy” status, T_sense is the time of “sensing” status, DIFS (DCF Interframe Space) is the inter-frame space of DCF (Distributed Coordination Function), and B is back-off time.

In order to accurately assess the communication load by nodes in the network, the forecast evaluation can be carried based on the information of the node CH_i at the past time t - 1 and the current time t.“Payload capacity” of the node queue can be obtained by the weighted moving average of the current available queue length and the previous available residual value of the queue length. Weighted moving average algorithm can be used to smooth for avoiding the effect of obvious deviation caused by sudden jitter of desired value.

CH_i _ Available _ load = Total _ Q_i - Cur _ Q_i, where Total _ Q_i is the total queue length, Cur _ Q_i is the current queue length.

Definition 2. Available Queue Buffer Length: CH_i _ Available _ load (t).

$\begin{matrix} {CH}_{i}_Available_load (t) \\ = β {CH}_{i}_Available_load (t - 1) \\ + (1 - β) {CH}_{i}_Available_l {oad}_{sample} \end{matrix}$ (14) where CH_i _ Available _ load_sample is the currentremaining length of node interface queue and CH_i _ Available _ load (t - 1) is the effective value ofthe previous interface queue length. CH_i _ Available _ load_sample is given a greater priority for the better reflection of the current state of the node. β is the weight of adjusting expected load capacity; β = 0.7, and β ∈ [0, 1] according to reference [17].

Definition 3. Degree of congestion control: Congest _ value_i

$\begin{matrix} Congest_v {alue}_{i} \\ = max (χ \times {CH}_{i}_BW \\ + (1 - χ) {CH}_{i}_Available_load) \end{matrix}$ (15) where χ ∈ [0, 1]. χ can be obtained from simulation, it is the weighting coefficient to balance the ALB and the AQBL. Congest _ value_i can be changed by adjusting the value of χ. If the AQBL becomes small, χ will be decreased to increase the weight of the load capacity on the congestion control, whereas χ will be increased to enlarge the weight of ALB, which then controls the degree of congestion.

3.3 Cross-layer route discovery and maintenance

In the definition as above, link available bandwidth, node load capacity and node dump energy can be obtained by the network layer through the cross-layer mechanism. Three extension fields are added in control message packet of the network layer. As indicated by the Fig. 4, E_j (r), CH_j _ BW and Congest _ valve_j are three pieces of cross-layer transfer information in the extension fields. During routing discovery, the node transfers cross-layer information in RREQ extension field through control message packets (such as RREQ, RREP and RERR) and realizes the route selection based on computations according to specific rules.

The sensor node power can be adjusted for dynamic maintenance of the node transmission power in the routing stage. The discovery process of next hop routing node works as follow:

Step 1: The source node cluster head CH_i broadcasts one message control packet RREQ CH _ MSG (ID, E_i (r) , CH_i _ BW, CH_i _ Available _ load) at the highest level of emission power.

Step 2: The adjacent cluster head CH_j reads the receiving power P_rec according to RSSI value and then calculates the lowest level of emission power P_mintra according to the reference [18] and check whether it has the same ID with the target node. R_threshold is the minimum RSSI value for receiving a packet. If it is, RREP message will be sent to the source code. Otherwise, its own ID will be added into routing records till target nodes are achieved. $P_{min tra} = \frac{P_{max} \times R_{threshold}}{P_{rec}}$ (16) $Congest_v {alve}_{path} = max_{R} [\sum_{j \in R} Congest_v {alve}_{j}]$ (17)

Step 3: The target node will receive multiple RREQ packets from different routing nodes and then choose the best path in Equation (17). Then the target node creates one RREP packet and gives a reply to the source node through single broadcast along the chosen path. When the RREP is sent back to the source node, all intermediate routing nodes on the best path will detect RREP messages and update their routing list. If the target node has received the same Congest _ valve_i value, the path with the most energy but the fewest hops will be chosen.

4 Message complexity of EBUCR

The message complexity of EBUCR is O (N).

Proof. Since cluster head generation rate is p₀, there are Np₀ cluster heads that deliver Np₀ messages to nodes around them, and N (1 - p₀) non-cluster heads broadcast apply to join in cluster set message. In the selection of route, CH broadcast Np₀ message (CH _ MSG (ID, E_i (r))), and each CH reply Np₀ message, the total volume of message expenses is Np₀ + N (1 - p₀) + Np₀ + Np₀ = (1 + 2p₀) N.

Thus, the message complex of EBUCR is O (N).

5 Message complexity of EBUCR

In order to verify that EBUCR protocol is more applicable to network deployments in narrow and long space of roadways, all nodes in this paper are distributed in three regions. In detail, A1 is a simulated belt region of laneways with length of 200 and width of 8 and base station coordinates of [220, 4]. A2 is a 200×200 rectangular region with base station coordinates of [100, 220]. A3 is a square region with the size of 200×200 and base station coordinates of [100, 100]. Both test and verification are implemented on the NS2 simulation platform. Meanwhile, the simulation and comparison with three algorithms, including LEACH, HEED [19] and EEUC, are carried out. Initial energy of the network node is 0.6J. E_elec is 50nJ/bit. ɛ_fs = 50pJ/(bit · m²), ɛ_mp = 0.0013pJ/(bit · m⁴) and E_DA = 5nJ/(bit · sin gnal). The data packet size is 4,000 bits and the control data packet is 100 bits. The data transmission rate is 12 packets per second and the node quantity is 100, 200 and 400.

5.1 Distribution of cluster head

Distribution of nodes is shown in Fig. 5.

CH and Ordinary Nodes (ON) seem to be overlapped, but actually separated by a very short distance. The result demonstrates that, in LEACH, CHs are irregularly distributed that often result in overlapping of various areas; thus, severely affecting the communication. Cluster heads distribution in HEED is different from that in LEACH. In LEACH, remained energy and communication cost is considered; however, the number of cluster heads generated is not so ideal than that in EEUC and EBUCR. In EEUC and EBUCR, CH distribution has a inverse relation with the distance to Sink, i.e., the farther separated from the Sink, the less number of the cluster heads.

5.2 Selection of parameter α

α is an important parameter on unequal clustering mechanism, which decides the scale of the cluster. The relationship between α and the network lifetime is observed by varying α between 0 and 1. Figure 6 shows that the lifetime decreases when α is very large; it can be concluded that the distribution of CH can affect the network lifetime. Therefore, there an optimal value for α must be selected, which is 0.3 in this experiment, as shown in Fig. 6. In addition, when N = 400, the lifetime of first node is much longer than that when N = 100 or N = 200, which has proved that the scenario designated in this paper is better suited to dense distribution for WSN.

5.3 Average energy consumption of cluster heads

In the experiment, ten rounds are selected at random to calculate the statistical information on all the energy consumed by the cluster heads in each round; the results from the experiment are shown in Fig. 7. It is found that the cluster heads of HEED consume less energy, while EBUCR and EEUC consume least of all. The possible reasons are the use of multi-hop in EBUCR, EEUC and HEED; the remaining energy is also considered for electing CHs. In addition, EEUC and EBUCR are using unequal clustering for CH electing. The case that CHs in LEACH consume most energy can be due to use of single hop for transmission; additionally, it is caused by unstable CH number and irregular distribution.

5.4 Data transmission contrast

Figure 8 shows a comparison of the number of message received in Sink over time using LEACH, HEED, EEUC and EBUCR schemes. In LEACH, all CHs directly transmit data to Sink due to restricted communication distance; thus, the messages received in Sink are less compared to other schemes. Multi-hop is used in HEED scheme; however, the number of cluster head is limited that caused the instability in the message transmission rate. The EEUC scheme also considers the minimum energy consumption path in routing without considering the link congestion. In addition, the factors such as cross-layer design, ALB and AQBL are generally considered. Therefore, the transmission is more fluent than the other schemes; thus, the number of messages is increased in the network. It is quite clear that EBUCR can transmit more data in the same period, and keep a better stability than the other schemes.

Figure 9 describes average packet delivery under various χ, it also reflects the congestion control of routing protocol. It is found that when the χ value is 0.5, packet delivery is best in EBUCR mechanism; this shows that ALB is as important as AQBL. In Fig. 10, it can be observed that there is very small difference in packet delivery ratio among HEED, EEUC and EBUCR, when one hop approach is used. However, with increase in number of hops, the packet delivery ratio noticeably drops. The drop is due to the many-to-one traffic pattern in multi-hop WSN that cases uneven data transmission of CHs. EEUC and EBUCR adopt unequal clustering strategy to relieve uneven traffic of CHs, and the packet delivery ratio is better than that in HEED. The EBUCR scheme considers the link congestion when choosing routes among CHs by cross-layer routing, the packet delivery ratio is better than that in EEUC.

In order to analyze the role of link available bandwidth and node load capacity in the cross-layer routing, end-to-end data delays are analyzed when transmissions are increased. As indicated by the Fig. 11, EBUCR protocol is better than other three types of protocol in terms of average data delay. Unequal clustering strategy is applied by this paper to EBUCR (No-CL) in the simulation. But the link available bandwidth and the node load capacity are not taken as reference factors. Only the protocol with node dump energy and the shortest path is taken into account. With increasing number of source node for data transmission, EBUCR the cross-layer routing selection strategy helps effectively avoid those routing nodes that may lead to network congestions because it has fully considered two factors as above. When there is a large number of transmission hop as indicated by Fig. 10, EBUCR is also superior according to the data transmission rate. With increasing hops, regions, where routing nodes are located in, are closer to base stations. Those routing nodes will bear more and more data for transmission. EBUCR protocol has fully considered the network topology and MAC status information of network routing nodes to balance loads on both network layer and link connection.

5.5 Network lifetime

The network lifetime comparison is shown in Fig. 12(a); it can be observed that the network lifetime in EBUCR and EEUC is longer than that of LEACH and HEED, especially in system stability (i.e. the first node dead time in the network) that is resulting from the use of unequal clustering strategy in EBUCR and EEUC. It is found that EBUCR is slightly better than EEUC. The simulation results can be concluded as the following: in LEACH scheme, the remaining energy of the node is neglected for the selection of cluster heads; while in HEED, the energy consumption is considered but the effective distribution of the cluster heads is neglected; in EEUC, the competition radius is considered as the main factor of clustering, while it ignores the size of distribution area.

The network stability of EBUCR is 13%, 120% and 160% higher than that of EEUC, HEED and LEACH respectively. The network is deemed unavailable when it has only 30% of nodes available. According to Fig. 12(a), EBUCR is better than other three types of protocol. EBUCR’s lifetime has been prolonged by more than 45% in comparison with LEACH and by about 19% in comparison with HEED. Data on Fig. 12(b) indicate that EBUCR protocol better adapts to narrow and long structure of roadways. According to results of analysis, cluster heads in LEACH protocol are selected at random according to a specific probability and the node dump energy is not taken as the reference of selecting cluster heads. Regardless of the fact that HEED protocol has considered node energy consumption, HEED protocol neglects the effective distribution of cluster head nodes in network regions. With respect to routing node selection, EEUC protocol has taken into account the dump energy as a parameter but ignored the impact brought by MAC layers to data transmission. By taking narrow and long belt regions for node deployment, EBUCR has considered the effective distribution density of cluster head nodes and asymmetric transmission of data. Furthermore, EBUCR protocol has referred to factors on the link layer during the routing node selection and can effectively guarantee balanced data transmission and data arrival rate in roadways with large-scale node deployment.

6 Conclusions

An effective distribution density of CH is introduced in this paper to balance the network energy consumption, and a cross-layer routing scenario is designed for the selection of cluster routes using unequal clustering strategy. From the experiment, it is proved that EBUCR has better stability and it can balance the cluster head energy consumption. In addition, it can select the best among various routing nodes to improve network throughput, and enlarge the life span to a certain extent. EBUCR is very suitable for the chain-type topology in tunnel monitoring. Wireless sensor network, as one of the favorite research topic, it is expected to further study various aspects including hardware development, node distribution, and dynamic topology controlling. The heterogeneous network deployment and distributed transmission control based on multiple base stations will be further studied in this paper in future.

Footnotes

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant No. 51204176), Innovation Fund Project on the Integration of Industry, Education and Research of Jiangsu Province (Grant No. BY2012081), Natural Science Foundation of Jiangsu Province (No. BK20140202). We would also like to thank the editor and the referees for their valuable comments.

References

Wang

, Research on Key Technologies of Mine Wireless Sensor Networks Node Deployment, Ph. D. Dissertation, China University of Mining and Technology, 2011.

Q.S.

, Wu

L.X.

, Zhang

and Ding

, Placement of positioning WSN in coal face and energy consumption analysis, Journal of China University of Mining & Technology43(2) (2014), 351–355.

Yang

and Wang

, Realization of hiberarchy wireless sensor network for mine laneway monitoring, Journal of China Coal Society33(1) (2008), 94–98.

Zhou

G.B.

, Zhu

Z.C.

Chen

G.Z.

, et al., Hiberarchy topology control of wireless sensor networks in coal mine laneway, Journal of China Coal Society35(2) (2010), 333–337.

Yuan

K.L.

, Qiao

and Han

H.L.

, Level and cluster based routing for wireless sensor network, Applied Mechanics & Materials321 (2013), 515–522.

Haneef

and Deng

, Design challenges and comparative analysis of cluster based routing protocols used in wireless sensor networks for improving network life time, Advances in Information Sciences & Service Sciences4(1) (2012), 450–459.

Soro

and Heinzelman

, Prolonging the lifetime of wireless sensor networks via unequal clustering, International Workshop on Alogrithms for Wireless, Mobile, Ad Hoc and Sensor Networks, Denver, 2005, PP. 417–456.

, Li

C.F.

, Chen

G.H.

and Wu

, An energy efficient clustering scheme in wireless sensor networks, International Journal of Ad Hoc & Sensor Wireless Networks3(2) (2007), 99–119.

C.F.

, Ye

, Chen

and Wu

, An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks, IEEE International Conf Mobile Adhoc and Sensor Systems, Washington, 2005, pp. 604.

10.

Heinzelman

, Chandrakasan

and Balakrishnan

, An application-specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications1(4) (2002), 660–670.

11.

X.B.

and Chen

G.H.

, The energy hole problem of nonuniformnode distribution in wireless sensor networks, Chinese Journal of Computers31(2) (2008), 253–261.

12.

Goldsmith

A.J.

and Wicker

S.B.

, Design challenges for energy-constrained ad hoc wireless networks, IEEE Wireless Communications9(4) (2002), 8–27.

13.

Munera

D.A.

and Gaviria

, A framework for simulation and evaluation of cross-layer techniques in wireless sensor networks, 2011 2nd National Conference on Telecommunications (CONATEL), Catolica San Pablo, Arequipa, 2011, pp. 1–7.

14.

Hakala

and Tikkakoski

, From vertical to horizontal architecture: A cross-layer implementation in a sensor network node, International Conference in Integrated Internet Ad Hoc and Sensor Networks, Nice, France, 2006, pp. 1–6.

15.

Paris

, Nita-Rotaru

, Martignon

and Capone

, Cross-layer metrics for reliable routing in wireless mesh networks, IEEE/ACM Transactions on Networking21(3) (2013), 1003–1016.

16.

Zhao

H.T.

, Garcia-Palacios

, Wei

J.B.

, et al., Accurate Available Bandwidth estimation in IEEE 802.11-based ad hoc networks, Computer Communications32(6) (2009), 1050–1057.

17.

Song

and Fang

X.M.

, Design and simulation of fairness-aware routing algorithm in wireless mesh networks, Journal of System Simulation19(18) (2007), 4320–4325.

18.

Rhee

, Jin

, Kim

, et al., Challenge-response based RFID authentication protocol for distributed database environment,, The KIPS Transactions PartC3450(3) (2005), 309–316.

19.

Younis

and Fahmy

, HEED: A hybrid, energy-efficient, distributed clustering approach for Ad hoc sensor networks, IEEE Transactions on Mobile Computing3(4) (2004), 366–379.