An improved clustering routing mechanism for wireless Ad hoc network

Abstract

In Wireless Ad hoc Networks (WANET), to organize sensor nodes for data collection is an important research issue. Clustering is an effective technique for prolonging the network lifetime. However, the Cluster Header (CH) in a cluster always involves a lot of data forwarding tasks, rather than its Cluster Members (CMs). This energy consumption overloading inevitably leads to the “hot spot” problem. With these in mind, an Energy-Balanced and Unequally-Layered Routing Protocol (EBULRP) is proposed in this article. The main emphasis is on balancing the energy consumption among CHs. In our design, the network is decoupled into multiple layers with different width, where the radius of clusters is differentiated at each layer. The core is to organize those CHs closer to the sink node, with more energy for inter-cluster data forwarding. Simulation results show that the proposed EBULRP effectively balances the energy consumption among CHs, and further prolongs the network lifetime.

Keywords

Wireless sensor networks communication protocol routing energy efficiency

1 Introduction

Wireless Ad hoc Network (WANET) is a decentralized type of wireless network. Over the last decade, the research on Wireless Sensor Networks (WSNs) or WANETs has been receiving great attention from academic and industrial communities. WSNs generally include a number of sensor nodes and given sink node deployed in an area, mainly for event monitoring and detection, data collection and transmission [1 –4]. However, sensor nodes are inherently battery-powered, and it is also difficult to recharge their energy once being used. In light of this, how to prolong the network lifetime by efficiently utilizing the limited energy of sensor nodes is a primary objective for protocol design in WSNs [5 –8].

In literature, the energy consumption module in WSNs generally includes sensing module, processing module, and wireless communication module. Among them, the wireless communication module concerning data transmission consumes most of the energy. Compared with flat routing schemes [9 –11], those schemes based on clustering [12 –15] can effectively improve the network scalability. While in clustering routing, sensor nodes are generally divided into two parts, which are Cluster Header (CH) and Cluster Member (CM). Here, the CH is responsible for establishing cluster structure and gathering data from its CMs. Since applying a single-hop data transmission between CHs and sink node is not beneficial to energy conservation, instead, existing studies have shown that a multi-hop communication between CHs and sink node can effectively reduce the energy consumption [16]. However, this method inevitably brings uneven distribution of energy consumption among CHs [17]. In this “many-to-one” data transfer mode, the CH closer to sink node needs to bear more data forwarding tasks from other clusters. It is also stated that this situation may exhaust their energy faster, meaning the network lifetime is reduced. Such situation is also referred as the “hot spot” problem in previous works [15 –17]. With this in mind, an Energy-Balanced and Unequally-Layered Routing Protocol (EBULRP) is proposed in this article. Compared with previous works, our main contributions are as follows:

The radius of clusters at each layer is differently assigned, while the width of each layer is determined by the distance between the sink node and those CHs at certain layer. Such design aims to alleviate the hot spot problem.

A multi-hop communication is applied between clusters across different layers, to overcome the problem if sensor nodes at certain layer are energy exhausted. The rest of this paper is organized as follows. The related work is described in Section II, followed by Section III in which we introduce the network model. The proposed EBULRP is detailed in Section 4 and evaluated in Section 5. Finally, we conclude our work in Section 6.

2 Related works

In recent years, researchers have proposed numerous clustering routing algorithms for WSNs to alleviate the hot spot problem. As the first proposed based on data fusion adaptive clustering topology protocol, Low-Energy Adaptive 3 Clustering Hierarchy (LEACH) [18] plays an important role in the development of clustering topologies routing protocols. The survival time of the whole algorithm is expressed in rounds in LEACH, though cluster establishment and data communication periodically. Through the random election of cluster heads and the application of data fusion method to reduce the communication load, LEACH can extend the network’s survival time greatly. However, due to the random cluster head selection scheme, the problem of cluster head uneven distribution or the number of cluster members appears frequently, which is shown as Fig. 1. LEACH-Centralized (LEACH-C) [19] is proposed to solve the problem of uneven cluster head distribution, which select the cluster head by global information. However, the global optimal selection is an NP problem, which is difficult to draw the exact solution. LEACH-Energy (LEACH-E) [20] considers node residual energy to solve the hot spot problem in LEACH.

Fig.1

LEACH cluster protocol.

In the Power-Efficient GAthering in Sensor Information Systems (PEGASIS) [21], sensor nodes are constructed in a chain, with each node serving as the header of chain. Then, the data is transmitted along the chain to CHs and finally to the sink node.

A Hybrid Energy-Efficient Distributed (HEED) clustering protocol [22] considers the residual energy of the node in its clustered threshold. Here, the candidate node is firstly generated, and then, formal CHs are selected according to the maximum residual energy and minimum reachable energy. However, the overhead for network clustering is inevitable due to the iterative manner in CH election.

Besides, other model [23] alleviates the hot spot problem via an unequal clustering manner. This algorithm assumes that two concentric circles are constructed with the sink node as their center. The cluster formed by the nodes in the inner circle is small, for which more energy is reserved for outer circle data forwarding. However, this model requires CHs are with powerful processing ability, and the locations of sensor nodes have to be obtained in advance. Another unequal clustering routing protocol, EnergyEfficient Uneven Clustering (EEUC) [24] divides the network into non-uniform clusters. However, the problem of cross-iteration and the node residual energy factors are not considered during the computation of radius.

3 Network model

In this section, the network model is introduced. Table 1 summarizes the key notations used in the paper.

Table 1
List of notations

W The width of monitoring area

L The side length of monitoring area

N Number of sensor nodes within the monitoring area

layer _i The ith layer from the BS

E _Tx Consumed energy for sending k bits to the destination node over distance d

E _Rx Energy for receiving k bits data

E _elec Energy consumed on sending/receiving per bit data

ɛ _fs Free-space-order radio antenna loss factor

ɛ _mp Radio antenna fading channel loss coefficient

fd _i the vertical distance between the cluster head i and the network middle line in the first layer

r _i Radius of the clusters in the layer_i

3.1 Assumption

Wireless sensor network consists of target, sensing nodes, observation node and sensing field. In addition, the external network, the user and the remote task management unit make the system description complete. The entire network scenario is shown in Fig. 2, the underlying application is for data collection. We consider a W × L rectangular monitoring area, within which there are N sensor nodes and one sink node. The set of all nodes is given by S = {s₁, s₂, …, s_N-1, s_N}, where |S| = N. Our design is based on following assumptions:

All sensor nodes are randomly deployed in a two-dimensional plane within the monitoring area. A base station (referred to sink node) is located outside the area, while the locations of base station and sensor nodes are fixed.

Each sensor node is identified by a unique ID. We assume all sensor nodes are initialized with the same amount of energy.

Each sensor node can be either Cluster Header (CH) or Cluster Member (CM), depending on the design of routing protocol.

The network time is decoupled into each round, within which sensor nodes will send their collected data to the base station.

Each sensor node can calculate its coordinate away from the emission source, according to the intensity and angle of its receivedsignal.

Fig.2

Network scenario.

3.2 Energy consumption mode

The wireless communication energy consumption model is presented in [19] and is shown in Fig. 3. the energy consumption E_Tx (k, d) for data transmission per k bits, with a distance d between pairwise nodes, is calculated according to Equation (1): $E_{TX} (k, d) = {\begin{matrix} k \times E_{elec} + k \times ɛ_{fs} \times d^{2} if (d < d_{0}) \\ k \times E_{elec} + k \times ɛ_{mp} \times d^{4} else \end{matrix}$ (1)

Fig.3

Energy consumption model.

Where the threshold value d₀ can be calculated according to Equation (2): $d_{0} = \sqrt{\frac{ɛ_{fs}}{ɛ_{mp}}}$ (2)

Here, Eelec represents the energy consumption of transmission circuit. Besides, ɛ_fs and ɛ_mp represent the amount of energy required by power amplification in that two models.

On the one hand, if the transmission distance d is smaller than the threshold d₀, the energy amplification consumption is based on free-space model. On the other hand, when the transmission distance is larger than or equal to threshold d₀, the multi-path fading model is applied. It can be observed that, applying single hop transmission for long range data transmission is energy costly. Therefore, applying multi-hop communication is alternatively more energy efficient.

4 Energy-balanced and unequally-layered routing protocol

Design of EBULRP consists of three phases, which are: Cluster Formation Phase, Data Transmission Phase, and Cluster Maintenance Phase. The main idea of EBULRP is shown in Fig. 4. Here, the entire network topology is decoupled into n layers, where each layer is assigned with a given width. At each layer, the closer to the base station, the smaller that the radius of cluster is. In order to alleviate the hot spot problem, EBULRP balances the energy consumption among CHs, based on the design detailed in this section.

Fig.4

Overview of cluster formation in EBULRP.

We assumed that the whole sensor network is divided into n layers with unequal width based on the distance to the base station, and the following properties can be obtained:

The closer to the base station, the smaller the width of the layer (WL), and the smaller the cluster radius r;

The cluster size in the same layer is equal, and the cluster radius is half width of the corresponding layer;

The data transmission adopts the multi-hop communication mode from the upper layer to the next layer until the base station.

4.1 Cluster formation phase

(1) Radius of Cluster Calculation: Given that r_n is the radius of cluster at the nth layer, the set for that at all layers is then given by R = {r₁, r₂, … r_n-1, r_n}. By referring to Fig. 4, the corresponding width of a given layer is calculated by 2 × r_n, while the transmission range of CH at each layer is given by (r_n + r_n-1).

The energy consumption of each sensor node module is shown in Fig. 5. The energy consumption mainly concentrates on the wireless communication module. Send data state cost most energy, and the idle state consumption is almost the same to the receive state.

Fig.5

The situation of sensor node energy consumption.

Given that a sensor node is with k bits data for transmission, the energy consumption E_n of CH at the nth layer for data transmission, is calculated as:

$\begin{matrix} E_{n} & = & (π \times r_{n}^{2} \times ρ) \\ \times [k \times E_{elec} + ɛ_{fs} \times k \times {(r_{n}^{2} + r_{n - 1})}^{2}] \end{matrix}$ (3) where ρ is the deployment density of sensor nodes. Regarding the CH at the (n - 1) ^th layer, its energy consumption E_n-1 is not only due to the data transmission within its local cluster, but also due to relaying the data from those CHs at the nth layer. Here, we have:

$\begin{matrix} E_{n - 1} \\ = {π \times r_{n - 1}^{2} \times ρ \\ + [π \times r_{n}^{2} \times ρ \times (\frac{L}{2 \times r_{n}}) \times (\frac{2 \times r_{n - 1}}{L})]} \\ \times [k \times E_{elec} + ɛ_{fs} \times k \times {(r_{n - 1} + r_{n - 2})}^{2}] \end{matrix}$ (4) where $(\frac{L}{2 \times r_{n}})$ indicates the number of clusters at the nth layer. While $(\frac{2 \times r_{n - 1}}{L})$ is the reciprocal of the number of clusters at the (n - 1) th layer. Note that L is the length of monitoring region shown in Fig. 4. Likewise, at the (n - 2) th layer, the energy consumption of CH, as for E_n-2, is given by:

$\begin{matrix} E_{n - 2} = {π \times r_{n - 2}^{2} \times ρ \\ + [\sum_{i = n - 1}^{n} π \times r_{i}^{2} \times ρ \times (\frac{L}{2 \times r_{i}})] \\ \times (\frac{2 \times r_{n - 2}}{L})} \\ \times [E_{elec} \times k + ɛ_{fs} \times k \times {(r_{n - 2} + r_{n - 3})}^{2}] \end{matrix}$ (5) $\begin{matrix} E_{n} \\ = (π \times r_{n}^{2} \times ρ) \\ \times [k \times E_{elec} + ɛ_{fs} \times k \times {(r_{n}^{2} + r_{n - 1})}^{2}] \\ E_{n - 1} \\ = {π \times r_{n - 1}^{2} \times ρ \\ + [π \times r_{n}^{2} \times ρ \times (\frac{L}{2 \times r_{n}}) \\ \times (\frac{2 \times r_{n - 1}}{L})]} \\ \times [k \times E_{elec} + ɛ_{fs} \times k \times {(r_{n - 1} + r_{n - 2})}^{2}] \end{matrix}$ (6) $\begin{matrix} \dots \dots \\ E_{1} \\ = {(π \times r_{1}^{2} \times ρ) \\ + \sum_{i = 2}^{n} [π \times r_{i}^{2} \times ρ \times (\frac{L}{2 \times r_{i}})] \\ \times (\frac{2 \times r_{1}}{L})} \\ \times [k \times E_{elec} + ɛ_{fs} \times k \times {\bar{R_{1}}}^{2}] \end{matrix}$

Based on above derivation, we can obtain Equation (6), where $\bar{R_{1}}$ as an approximate distance between the base station and the CH at the 1st layer, is calculated as: $\bar{R_{1}} = \sqrt{{(\frac{L}{4})}^{2} + d_{min}^{2}}$ (7)

Here, d_min is the shortest distance from the monitoring area to the base station. In particular, aiming to balance the energy consumption of CHs, we have: $E_{k} ≅ E_{k - 1} ≅ \dots ≅ E_{2} ≅ E_{1}$ (8)

In addition, according to the characteristics of network structure,we can get: $r_{1} + r_{2} + \dots + r_{n - 1} + r_{n} = \frac{W}{2}$ (9)

Where, W is the width of the monitor area. Then, from Equations (6) to (9), r₁, r₂, …, r_n can be calculated, and the width of each layer can be established. For example, we suppose a network structure consisting by only three layers, n = 3. Then, r₁, r₂, …, r₃ can be calculated as (10). ${\begin{matrix} E_{3} = (π \times r_{3}^{2} \times ρ) \\ \times [E_{elec} \times k + ɛ_{fs} \times k \times {(r_{2} + r_{3})}^{2}] \\ E_{2} = {π \times r_{2}^{2} \times ρ + \\ [π \times r_{3}^{2} \times ρ \times (\frac{L}{2 \times r_{3}}) \times (\frac{2 \times r_{2}}{L})]} \\ \times [E_{elec} \times k + ɛ_{fs} \times k \times {(r_{1} + r_{2})}^{2}] \\ E_{1} = {π \times r_{1}^{2} \times ρ \\ + [\sum_{i = 2}^{3} π \times r_{i}^{2} \times ρ \times (\frac{L}{2 \times r_{i}})] \times (\frac{2 \times r_{1}}{L})} \\ \times [E_{elec} \times k + ɛ_{fs} \times k \times {\bar{R_{1}^{'}}}^{2}] \\ E_{1} ≅ E_{2} ≅ E_{3} \\ \frac{W}{2} = r_{1} + r_{2} + r_{3} \end{matrix}$ (10)

In calculating the radius of the cluster, the data transmission distance of each cluster head in other layers, except the first layer, can be approximated as the sum of the cluster radius between adjacent layers. However, As shown in Fig. 6 (a) and (b), the base station is the next-hop data transfer for the cluster head in the first layer. the data transmission distance is not only the sum of the cluster radius between adjacent layers, and the distances between the respective base stations are also different. Assume that N is the total number of cluster heads in the first layer. It can be an odd number or even number. fd_i is the vertical distance between the cluster head i and the network middle line in the first layer.

Fig.6

The communication distance between each cluster head and the base station in Layer₁.

For the first situation: N is an odd number. ${fd}_{i} = {\begin{matrix} [N - (2 i - 1)] \times r_{1}, i = 1 \sim ⌊ \frac{N}{2} + 1 ⌋ \\ 2 [i - ⌊ \frac{N}{2} ⌋] \times r_{1}, i = ⌊ \frac{N}{2} + 2 ⌋ \sim N \end{matrix}$ (11)

For the second situation: N is an even number. ${fd}_{i} = {\begin{matrix} [N - (2 i - 1)] \times r_{1}, i = 1 \sim \frac{N}{2} \\ [2 (i - \frac{N}{2}) - 1] \times r_{1}, i = \frac{N}{2} + 1 \sim N \end{matrix}$ (12)

Then, the mathematical expectation or mean of fd_i, E [fd_i], is as follow: $E [{fd}_{i}] = \frac{1}{N} ({fd}_{1} + {fd}_{2} + \dots + {fd}_{N - 1} + {fd}_{N})$ (13)

Then, in Equations (6), The data transmission distance between the cluster head and the base station in the first layer, ${\bar{R}}_{1}$ , can be expressed as: $\bar{R_{1}} = \sqrt{(r_{1} + d_{min})^{2} + (E [{fd}_{i}])^{2}}$ (14)

(2) Cluster Formation: The base station broadcasts a signal to the entire monitoring region, based on a given transmission power. Sensor nodes receiving this signal, then calculate their relative coordinates according to the intensity and the angle of signal [25]. Furthermore, based on the previous discussion on the radius of cluster, the base station can calculate all locations of Ideal CHs (namely ICHs) at each layer, based on a n layers’ topology configuration. Note that the locations of CHs finally determined in the network, may have a certain variation from that of ICHs calculated by the base station.

With a flowchart shown in Fig. 4, the detailed procedure for cluster formation is listed as follows:

1) The base station broadcasts a message namely “CH INFORM MSG” including information about all ICHs at all layers, to sensor nodes in the entire network. Particularly, for each layer, it includes:

The layer ID.

The locations of all ICHs at certain layer.

The IDs of all ICHs at certain layer.

The radius of clusters at certain layer.

2) After receiving the “CH INFORM MSG”, a sensor node s_i, with the closest distance to a given ICH, initially elects itself as the CH for competition. Besides, s_i further broadcasts a “CH COMPETE MSG” to its neighbors, including the layer ID, ID of ICH it elects for competition and its distance to that ICH.

3) Any other sensor node s_j receiving this “CH COMPETE MSG”, will compare the information in relation to the ICH it elects for competition, with that of in this received message. If the same ICH is under competition, all details included in “CH COMPETE MSG”, will be inserted into a set SCH.

4) After a given competition time interval, each sensor node will compare the distance to the ICH it competes, with those values in S_CH. Here, the sensor node making comparison is elected as the CH, only if it is with the smallest value regarding such distance metric. Followed by this successful election, that given sensor node then broadcasts a “CH ELECT MSG”.

5) Other sensor node receiving “CH ELECT MSG”, will join the closest cluster by sending a “CH JOIN MSG”. Here, the estimation regarding the closest cluster is based on the intensity of signal. In special case, the sensor node without “CH ELECT MSG” received, will alternatively broadcast “CH FIND MSG” to find the closest CH and join that cluster.

6) The network clustering is finished until all CHs are elected, around which other sensor nodes are their CMs.

4.2 Data transmission phase

In EBULRP, the data transmission is decoupled into two stages:

In the first stage, the data transmission happens between the CH and its CMs.

The data transmission in the second stage is between CHs and base station. Here, two communication modes are applied. The single-hop communication is for directly delivering data from the CH to the base station. The multi-hop communication is for intermediate data transmission to the base station, through a number of CHs. Note that we already discussed that using multi-hop communication is more energy efficient in Section 3.

As shown in Fig. 7, the network time is decoupled into several rounds, where each round consists of several time slots. The time slots in EBULRP is shown in Fig. 8. Based on different characteristics, these time slots are classified into:

CM-Slot: The time slot assigned for CM, to report its request and transmit data to the CH.

Control-Slot: The time slot to manage the cluster.

CH-Slot: The time slot assigned for CH, to deliver data to the base station.

Special-Slot: The time slot assigned to directly receive the information broadcasted from the base station.

Fig.7

Flowchart of cluster formation in EBULRP.

Fig.8

Time slots in EBULRP.

1) First Stage: For the first stage, EBULRP modifies the fixed time slot based communication as adopted by LEACH, into a dynamic time slot based communication. It is highlighted that such modification can meet the requirement of different CMs with certain time slot for data transmission.

Starting from the first CM-Slot, each CM sends request in relation to its number of required time slots for data transmission. Upon receiving requests from all CMs within the local cluster, the CH then randomly allocates the remaining CM-Slots, such that each node with pending request is allocated with at least one CM-Slot.

Before the expiration of first CM-Slot, the CH will inform other CMs regarding their specific assigned CM-Slots. Each CM will only return to awake mode upon an arrival of its own CM-Slots, and then starts to transmit data to the CH. In other time slots, CMs will remain in sleep mode for energy saving purpose.

2) Second Stage: Upon the collection of data, the CH will then deliver data to the based station, via multi-hop communication mode, only within the CH-Slot. Given that the network clustering has already been established, the neighbor information is exchanged between adjacent CHs, and stored locally for selecting the next hop. Overall, the data is relayed from the CH at an upper layer to that at a lower layer, and finally from the CH at the lowest layer to the base station. If there are more than one CHs available for next hop, the one with a closer distance and more energy is selected as the next hop. This aims to balance the energy consumption among CHs, as such the hop spot problem can be alleviated. In special case, a direct data transmission is established with the base station, if there is no available next hop.

With further concerning, the Direct Sequence Spread Spectrum (DSSS) can be integrated into this multi-hop communication. By doing so, each cluster is coded with different SS in order to avoid crosstalk. The signal from other clusters will not be filtered by CMs in their local cluster. This can effectively alleviate the interference across CMs in adjacent clusters. Furthermore, the Carrier Sense Multiple Access (CSMA)mechanism can be applied for communication between CHs, and that between CHs and the base station. Here, CHs should listen to the channel before data transmission, to prevent collision, as shown in Fig. 9.

Fig.9

The inter-layer multi-hop communication mode.

4.3 Cluster maintenance phase

Basically, CHs are responsible to manage their CMs within the cluster, along with data forwarding for intra-cluster and inter-cluster data forwarding. In the worst case, CHs may run out of energy.

Indeed, clustering based routing protocols such as LEACH and EEUC, rely on periodical re-clustering mechanism to balance the energy consumption of CHs. However, such re-clustering mechanism requires huge information exchange and complicated computation, which limits the system scalability.

Our design in EBULRP is not with such periodical re-clustering mechanism. Instead, each CM within a cluster will be elected as the CH alternately. Once a CM becomes the CH, it will collect the information in relation to an average energy E_avg of other CMs in the cluster. Whenever the CH detects that its energy is smaller than $\frac{E_{avg}}{2}$ or a threshold E_min, it considers itself not to be the CH anymore. Upon this decision, within the Control-Slot, the CH collects the information in relation to the energy of other CMs in the cluster, and elects the one with the highest energy as the CH in next round.

As previously mentioned, EBULRP is layered with different width, where the width and clusters at certain layer are decreased, from the layer that is with the fastest distance to the base station. In case that sensor nodes are uniformly distributed in the network, the cluster with a smaller radius thereby consists of less number CMs. In the worst case, all nodes including CHs and CMs at a given layer may run out of energy, however those at other layers still work.

In EBULRP, a cross-layer communication is applied to prolong the network lifetime. Here, the base station will inform those CHs at an upper layer to directly communicate with itself, if all nodes at a lower layer run out of their energy. For example, if all nodes at the 1st layer are energy exhausted, all nodes at the 2nd layer then performs direct communication with the base station, as shown in Fig. 10(a) and (b).

Fig.10

The cross-layer communication in EBULRP.

5 Performance evaluation

The scenario comprises a 150 m by 120 m monitoring area. The performance is evaluated using Matlab, with the configuration listed in Table 1. In order to show the advantage of our proposal, we also implement the LEACH [18], EEUC [24] for comparison. Three evaluation metrics of the network performance have been studied as follows:

Network Lifetime: There is no universally agreed definition for the network lifetime. The importance of WSNs is to be operational and able to perform tasks. In WSNs, it is important to maximize the network lifetime, which means to increase the network survivability or to prolong the battery lifetime of sensor nodes. Here, the total number of alive nodes is applied in our evaluation to measure the network lifetime.

Network Energy Balance: This metric calculates the variance of the CHs’ energy consumption in each round, to evaluate the energy balance in the network.

Average Energy Consumption: This metric shows the average dissipation of energy per node over time in the network as it performs various functions such as transmitting, receiving, sensing and aggregation of data.

The parameters used in the simulation experiments are shown in Table 2. To begin with, the influence of network layers is evaluated. Table 3 shows the radius of cluster with layers of 1-layer, 2-layers, 3-layers for the design of EBULRP, respectively. Note that more or less hops will lead to additional communication overhead, so the number of network layers has a significant impact on the overall network performance.

Table 2
Simulation configuration

Parameter Value

Network Coverage Area 180 m×120 m

Location of Base Station (–50, 60)

Number of Sensor nodes 180

Initial Energy 0.5 J

Eelec 50 nJ/bit

ɛ _fs 10 pJ/bit/m2

ɛ _mp 0.0013 pJ/bit/m4

Network Layer 2

r ₁ 30.62 m

r ₂ 44.38 m

Data size 3000 bits

Parameter	Value
Network Coverage Area	180 m×120 m
Location of Base Station	(–50, 60)
Number of Sensor nodes	180
Initial Energy	0.5 J
Eelec	50 nJ/bit
ɛ _fs	10 pJ/bit/m2
ɛ _mp	0.0013 pJ/bit/m4
Network Layer	2
r ₁	30.62 m
r ₂	44.38 m
Data size	3000 bits

Table 3

Configuration based on different layers

Number of Layers	r ₁	r ₂	r ₃	r ₄
n = 1	31.67 m	43.33 m
n = 2	13.75 m	25.11 m	34.13 m
n = 3	9.74 m	16.52 m	19.90 m	28.84 m

Figure 11 shows the network lifetime of EBULRP with 1-layer, 2-layers and 3-layers configuration respec-tively, where the radius of cluster at each layer follows calculation in Table 2. In case of 2-layers,nodes can survive longer and show better performance than other two cases. Therefore, it is essential for the base station to determine an appropriate layer when designing the cluster structure.

Fig.11

Influence of layers.

Figure 12 shows the average energy consumed by all nodes, at the first 100 rounds. The node energy consumption of LEACH is significantly higher than that of EEUC and EBULRP. The reason is that LEACH makes use of single-hop data transmission for inter-cluster communication, which results in more energy consumption at CHs which are far from the base station. While EEUC builds the topology through unequal clustering method, along with a multi-hop communication to reduce the communication cost during the routing selection. However, due to the random distribution of clusters, there still exists uneven distribution which may cause abundant hops during inter-cluster data transmission. In contrast, EBULRP lets the base station to proceed main computation for network clustering, and only leaves a littledata exchange and calculation at sensor nodes. Furthermore, it achieves an even distribution on clusters where the number of hops for inter-cluster data forwarding is relatively fixed. Such a way better organizes the network clustering for energy saving purpose.

Fig.12

Average energy consumption of nodes.

Since the core idea is to alleviate the hot spot problem, the accuracy of computation on networkclustering plays an important role in energy balance. In Fig. 13, we arbitrarily select 20 rounds of data to calculate the variance of the CHs’ energy consumption. Here, EBULRP achieves the smallest variation,followed by EEUC and LEACH. This is because that the design of EBULRP considers the properties of different CHs, and well organizes the network topology to address the energy unbalance among CHs.

Fig.13

Variations of CHs’ energy consumption.

The purpose of Fig. 14 is to examine the network lifetime. It shows the number of the alive nodes along with the number of rounds. If considering that 50% of sensor nodes are dead, EBULRP, EEUC and LEACH end at 467, 338 and 250 rounds respectively. Here, the performance of EBULRP is 38% higher than EEUC and 87% higher than LEACH. If considering 80% of sensor nodes are dead, EBULRP, EEUC, and LEACH end at 562, 441, and 398 rounds respectively. Here, the performance of EBULRP is 27% higher than EEUC and 41% higher than LEACH. This is due to that EBULRP adopts a well clustering and multi-hop communication for inter-cluster data transmission.

Fig.14

Number of alive nodes.

6 Conclusion

We have proposed EBULRP in this article to solve the hot spot problem. The design of EBULRP alleviates the computation complexity at CH side, via a less numbers of controlling information exchange. We firstly analyzed the energy consumption of CHs, then established a multi-layered network structure to balance the energy consumption among CHs. Compared with the previous works LEACH and EEUC, results show EBULRP significantly prolongs the network lifetime and balances the energy consumption in the network.

Footnotes

Acknowledgments

This paper is supported by the National Natural Science Foundation (61102105), the Postdoctoral start foundation of Heilongjiang Provence (LBH-Q12117); the Foundation for Innovative Research of Harbin (2015RAQXJ008); and the Fundamental Research Funds for the Central Universities (GK2080260138). We Also would like to acknowledge the support of the University of Surrey 5GIC () members for this work.

References

Yao

, Feng

, Zhou

and Liu

, Secure routing in multihop wireless Ad-hoc networks with decode-and-forward relaying, IEEE Transactions on Communications64(2) (2015), 753–764.

Cao

, Sun

, Wang

, Riaz

, Cruickshank

and Liu

, Geographic-based spray-and-relay (GSaR): An efficient routing scheme for DTNs, IEEE Transactions on Vehicular Technology64(4) (2015), 1548–1564.

Zanella

, Bazzi

, Pasolini

and Masini

B.M.

, On the impact of routing strategies on the interference of ad hoc wireless networks, IEEE Transactions on Communications61(10) (2013), 4322–4333.

Wang

, Zhao

, Xu

and Qi

, An intelligent processing model on heterogeneous information from the internet of things, Journal of Computational Information Systems7(2) (2011), 578–584.

Kurt

, Yildiz

H.U.

, Yigit

, Tavli

and Gungor

V.C.

, Packet size optimization in wireless sensor networks for smart grid applications, IEEE Transactions on Industrial Electronics64(3) (2016), 2392–2401.

Rahat

A.A.

, Everson

R.M.

and Fieldsend

J.E.

, Evolutionary multi-path routing for network lifetime and robustness in wireless sensor networks, Ad Hoc Networks52 (2016), 130–145.

Kim

H.Y.

, An energy-efficient load balancing scheme to extend lifetime in wireless sensor networks, Cluster Computing19(1) (2016), 279–283.

Wang

, Zhang

, Cui

and Zhou

, A novel protocol of energy-constrained sensor network for emergency monitoring, Interational Journal of Sensor Networks15(3) (2014), 171–182.

Echoukairi

, Bourgba

and Ouzzif

, A Survey on Flat Routing Protocols in Wireless Sensor Networks, Advances in Ubiquitous Networking, SpringerSingapore, 2016, pp. 270–277.

10.

Kulik

, Heinzelman

and Balakrishnan

, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks8(2) (2002), 169–185.

11.

Intanagonwiwat

, Govindan

and Estrin

, Directed diffusion for wireless sensor networking, IEEE/ACM Transaction on Networking11(1) (2003), 2–16.

12.

Wang

, Wu

, Xu

, Zhu

and Charles

, A cross unequal clustering routing algorithm for sensor network, Measurement Science Review13(4) (2013), 200–205.

13.

Kavitha

, Ramakrishnan

and Das

, A novel routing scheme to avoid link error and packet dropping in wireless sensor networks, International Journal of Computer Networks and Applications (IJCNA)3(4) (2016).

14.

Yan

, Zhou

and Ding

, Recent advances in energy-efficient routing protocols for wireless sensor networks: A review, IEEE ACCESS4 (2016), 5673–5686.

15.

, Yang

and Zhang

, Design of an intrusion detection system for wireless sensor networks, Sensor Letters9(5) (2011), 2082–2086.

16.

Zhu

, Efficient fault-tolerant event query algorithm in distributed wireless sensor networks, International Journal of Distributed Sensor Networks5(4) (2010), 1–7.

17.

Zou

, Wang

and Wang

, A routing algorithm on delay-tolerant of wireless sensor network based on the node selfishness, EURASIP Journal on Wireless Communications and Networking1 (2013), 1–9.

18.

Heinzelman

, Chandrakasan

and Balakrishnan

, Energy-Efficient Communication Protocols for Wireless Microsensor Networks, IEEE Hawaii International Conference on Systems Sciences (HICSS), 18, 2000, p. 8020.

19.

Heinzelman

, Application-Specific Protocol Architectures for Wireless Networks, Massachusetts Institute of Technology, 2000.

20.

Peng

and Zhang

, An energy efficient cluster-routing protocol for wireless sensor networks, IEEE International Conference on Computer Design and Applications (ICCDA)2 (2010), 530–533.

21.

Lindsey

, Raghavendra

and Sivalingam

, Data gathering algorithms in sensor networks using energy metrics, IEEE Transactions on Parallel and Distributed Systems13(9) (2002), 924–935.

22.

Younis

and Fahmy

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

23.

Soro

and Heinzelman

, Prolonging the lifetime of wireless sensor networks via unequal clustering, IEEE Computer Society Press (2005), p. 556.

24.

, Ye

, Chen

and Wu

, An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks, IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), 2005, p. 604.

25.

Parameswaran

, Husain

M.I.

and Upadhyaya

, Is RSSI a Reliable Parameter in Sensor Localization Algorithms, An Experimental Study, Field Failure Data Analysis Workshop (F2DA2009). 2009, p. 5.

W	The width of monitoring area
L	The side length of monitoring area
N	Number of sensor nodes within the monitoring area
layer _i	The ith layer from the BS
E _Tx	Consumed energy for sending k bits to the destination node over distance d
E _Rx	Energy for receiving k bits data
E _elec	Energy consumed on sending/receiving per bit data
ɛ _fs	Free-space-order radio antenna loss factor
ɛ _mp	Radio antenna fading channel loss coefficient
fd _i	the vertical distance between the cluster head i and the network middle line in the first layer
r _i	Radius of the clusters in the layer_i

An improved clustering routing mechanism for wireless Ad hoc network

Abstract

Keywords

1 Introduction

2 Related works

Table 2 Simulation configuration Parameter Value Network Coverage Area 180 m×120 m Location of Base Station (–50, 60) Number of Sensor nodes 180 Initial Energy 0.5 J Eelec 50 nJ/bit ɛ fs 10 pJ/bit/m2 ɛ mp 0.0013 pJ/bit/m4 Network Layer 2 r 1 30.62 m r 2 44.38 m Data size 3000 bits

Footnotes

Acknowledgments

References