Sage Journals: Discover world-class research

Abstract

In this article, we propose two new routing protocols for wireless sensor networks. First one is AM-DisCNT (angular multi-hop distance–based clustering network transmission) protocol which uses circular deployment of sensors (nodes) for uniform energy consumption in the network. The protocol operates in such a way that nodes with maximum residual energy are selected as cluster heads for each round. Second one is iAM-DisCNT (improved AM-DisCNT) protocol which exploits both mobile and static base stations for throughput maximization. Besides the proposition of routing protocols, iAM-DisCNT is provided with three mathematical models: two linear-programming-based models for information flow maximization and packet drop rate minimization and one model for calculating energy consumption of nodes. Graphical analysis for linear-programming-based mathematical formulation is also part of this work. Simulation results show that AM-DisCNT has 32% and iAM-DisCNT has 48% improved stability period as compared to LEACH (low-energy adaptive clustering hierarchy) and DEEC (distributed energy-efficient clustering) routing protocols. Similarly, throughput of AM-DisCNT and iAM-DisCNT is improved by 16% and 80%, respectively, in comparison with the counterpart schemes.

Keywords

Wireless sensor networks logical clustering routing protocol energy efficiency linear programming

Introduction

Wireless sensor networks (WSNs) are composed of small, compact, and lightweight sensors called nodes. These nodes are deployed to monitor the environmental conditions (such as temperature, light, sound, and fire) and gather the information of interest. Then, following a specific routing strategy, the encoded information in the form of data messages is transmitted to base station (BS) where it is decoded. By encoded data we mean sensed data in the form of bits (information) and by decoded data we mean extracted information when the encoded data are successfully received at the sink. Figure 1 shows the WSN clustering technique, where communication between cluster head (CH) and cluster member nodes (MNs) is direct. Applications of WSNs include constant monitoring and detection of specific events such as battlefield surveillance, weather forecast, flood detection, and patient monitoring.^1–4

Figure 1.

WSN with clusters.

Methods of data delivery to BS depend on application and can be categorized into four types: continuous, query driven, event driven, and hybrid. The first method allows each node to transmit data periodically. In the second method, data are transmitted when a query is generated by BS. Similarly, event-driven transmission is triggered by occurrence(s) of specific event(s). A hybrid data delivery method utilizes two or more methods at the same time. Routing protocols are highly influenced by these data delivery methods in terms of energy consumption.^5,6 Therefore, selection of proper data delivery method is one of the major challenges faced by the sensor network routing protocols.

Each node is equipped with limited energy source, usually a battery. Therefore, proper route selection for data transmission is of extreme significance.^7–9 In Jin et al.,¹⁰ authors discussed the relation between hop count and energy consumption on theoretical as well as practical point of view. For example, Figure 2 shows the comparison of single-hop communication and multi-hop communication with respect to energy consumption when the distance between nodes and sink is subject to increase. As evident from the figure, direct communication penalizes nodes far away from sink, whereas multi-hop communication penalizes nodes nearer to the sink. Therefore, clustering is required to balance the energy consumption of farther as well as nearer nodes. Prior to routing, random deployment of nodes leave some regions un-monitored. So, the placement of BS should be such that it can conveniently get packets from every part of network.

Figure 2.

Comparison of energy consumption: direct communication (DC) versus minimum transmission energy (MTE).

Scalability is one of the major design considerations in sensor network applications. In a single-tier network, aggregator node is overloaded whenever the network density is increased. This overloading may cause latency along with high energy consumption. So, single-tier WSNs are not scalable because nodes are not capable of long-haul communication. In order to cover large network area, without degrading quality of service, clustering has been introduced as one of the very fruitful routing approaches.⁵

In this article, our focus is on the network lifetime maximization and minimization of packet drop ratio. For this purpose, two cluster-formation-based routing protocols for WSNs are presented: AM-DisCNT (angular multi-hop distance–based clustering network transmission) and iAM-DisCNT (improved AM-DisCNT). In AM-DisCNT, network area is divided into circular regions such that inner circle nodes directly communicate with BS, whereas outer circle nodes form clusters in their defined areas. CHs gather data from nodes associated with them and after aggregation, send these data to BS using multi-hop technique. CHs are more penalized as compared to the MNs of clusters because they have to relay data of the MNs, and they deplete their energies soon. To overcome this issue, another scheme iAM-DisCNT is proposed that is equipped with mobile BSs. Role of CH is shifted to mobile BS. We assume that these Mobile BSs have no constraint of energy. They move in the field and gather data directly from the nodes. Moreover, iAM-DisCNT is aided with linear-programming-based mathematical models for data flow maximization and packet drop minimization. Here, it is important to mention that section “The proposed protocol: AM-DisCNT” summarizes our previous work in Rao et al.¹¹ and section “Extending AM-DisCNT: iAM-DisCNT” includes the improvements made to our previous work.

Rest of the article is organized as follows. Section “Related work” contains a brief review of related work. Section “The proposed protocol: AM-DisCNT” describes the motivation for the proposed protocols. Section “Extending AM-DisCNT: iAM-DisCNT” presents the details of AM-DisCNT protocol and also contains explanation about the drawback of AM-DisCNT protocol and proposition of the second routing protocol “iAM-DisCNT” along with linear-programming-based mathematical models for data flow maximization and packet drop minimization. Section “Simulation results” provides the simulation results along with discussions. Finally, section “Conclusion and future work” concludes the article and states the future work.

Related work

In this section, a brief overview of related research work is presented. Here, the focal point is hierarchical routing protocols and cluster organization based in particular.

LEACH (low-energy adaptive clustering hierarchy)¹² is a hierarchical clustering algorithm which randomly selects nodes as CHs. Basically, LEACH works in two phases: set-up phase and steady-state phase. In set-up phase, nodes are randomly deployed in network field such that each node is initially equipped with equal energy. Deployment is followed by random selection of CHs where each node generates a random number and compares it with a threshold value. If the generated random number is less than the threshold value, then that node is selected as CH for the current round. Soon after the selection of CHs, remaining nodes associate themselves with the nearest CH. In steady-state phase, time division multiple access (TDMA)-based schedules are assigned to nodes and CHs for data transmission such that each node or CH associates within its allocated time slot only. Thus, we can say that LEACH uses two modes of communication, that is, between nodes and CHs, and between CHs and BS. In LEACH, CH selection is random and non-uniform. Due to this non-uniformity, density of clusters varies in different regions causing loss of data. LEACH-C (LEACH centralized)¹³ uses centralized clustering algorithm, where the information about the energy and location of nodes is sent to BS. The CH selection is random in LEACH-C. In LEACH-C, BS makes sure that node with lower energy than the network’s average energy does not become CH. However, nodes away from BS are unable to send their data to BS due to less energy, thus leading to network partition (improper coverage of the network). Moreover, selection of CHs is random like LEACH, thereby causing nodes to deplete their energy in an unbalanced manner which ultimately leads to decreased network lifetime and throughput. In multi-hop LEACH,¹⁴ data sent by nodes are received at BS through a chain of CHs. In case of multi-hop LEACH, nodes which are not in the vicinity of any CH, send a request to near-by nodes to become their temporary CH. However, CH selection is random which leads to problem similar to that in LEACH, LEACH-C, and multi-hop LEACH. This agreement does not guarantee monitoring of the entire network. A-LEACH (advanced LEACH)¹⁵ selects CHs on the basis of current state and random probability.

TEEN (threshold-sensitive energy-efficient sensor network protocol)¹⁶ is the first reactive protocol for homogeneous WSNs. This protocol defines two thresholds: hard and soft. The set-up phase of TEEN is similar to that of LEACH, where CHs are randomly selected from the set of eligible nodes. Whereas, data are not transmitted until the threshold is reached in steady-state phase. That is why TEEN is not a good option for applications that require periodic data monitoring. APTEEN (adaptive threshold-sensitive energy-efficient sensor network protocol)¹⁷ sends data periodically and also provides information on time-critical events. Main drawback of TEEN and APTEEN is the complexity of forming clusters in multiple levels implementing threshold-based functions and dealing with attribute-based naming of queries.

SEP (stable election protocol)¹⁸ is the first heterogeneity-aware WSN protocol which uses proactive data reporting. The authors consider two levels of energy in a hierarchical network such that each node independently elects itself as a CH based on probability value. Node with more residual energy hold strong chances to be selected as CH due to biased probability weight in proportion to residual energy level. Following the same technique as that of LEACH, data scheduling and transmissions occur in SEP as well. In Aderohunmu and Deng,¹⁹ authors propose E-SEP (enhanced-SEP) routing protocol for heterogeneous WSNs. The proposed proactive E-SEP protocol extends the concept of SEP from two-level heterogeneity to three levels.

DEEC²⁰ (distributed energy-efficient clustering) generalizes the concept of SEP to multi-energy levels in a homogeneous proactive environment. This protocol selects CHs on the basis of nodes’ residual energy and average energy of the network. Soon after the CHs selection, minimum distance–based association of nodes with CHs takes place. Finally, BS assigns TDMA-based schedules to nodes as well as CHs. In these schedules, data transmissions from nodes to their respective CHs and from CHs to BS occur. DEEC protocol also has variable number of clusters and their size vary indefinitely. SDEEC (stochastic distributed energy-efficient clustering)²¹ introduces a balanced method for CH election. This method is more efficient than previous techniques as it uses stochastic scheme detection. SDEEC outperforms SEP and DEEC in terms of network lifetime.

In Luo and Hubaux,²² authors investigate the joint sink mobility and routing problem. They first solve the problem by primal dual algorithm while considering single BS and then it is generalized with the consideration of multiple BSs. Behdani et al.²³ use mobile BS to maximize the lifetime of WSNs, where the BS moves with a finite speed to collect data from static nodes. In Haeyong et al.,²⁴ authors increase the network lifetime by deploying multiple BSs where mixed integer linear programming is used to determine the position as well as traffic flow from/toward the mobile BS.

To improve the efficiency of a WSN, energy consumption should be minimized that also improves the network lifetime. Rahim et al.²⁵ address the issue of communication efficiency and power consumption. As nodes have limited battery, the energy efficiency is a critical issue. They give the solution by distributing traffic uniformly across the network.

A hierarchical clustering scheme, called LESCA (location energy spectral cluster algorithm) is proposed in Jorio et al.²⁶ This scheme calculates the total number of clusters in a network. For finding optimal number of clusters, it takes into account residual energy as well as properties of nodes. It uses K-ways algorithm in order to determine the clusters and respective CHs. For this purpose, it uses average energy and distance to BS. The simulation results show that if the network does not form optimal number of clusters, the total consumed energy increases exponentially per round.

AUV-PN (autonomous underwater vehicle visits path nodes) is proposed in Khan and Cho.²⁷ To gather data, an AUV is deployed in the field. By taking constant depth of AUV, that is, $D_{avu} < D$ , the problem is simplified into two-dimensional field. The two-dimensional network field is divided into several sub-regions (clusters). When network starts, AUV logically divides the network into clusters and broadcast the cluster information. Nodes identify their respective cluster using the broadcast information. After nodes’ association phase, MNs selects a CH. These CHs further divides the clusters into several sub-clusters. A CH selects a PN which gathers data from MNs and relay it to the AUV. AUV collects the PN information from the clusters. In second phase, AUV takes data gathering tour in which it visits each PN and receives collected data. Data are sent to the BS in three hops: sub-cluster nodes send the sensed data to the PN in first hop; in second hop, PNs send the received data to AUV; and in final hop, an AUV forwards the received information to the sink. PNs gather data continuously except the interval in which they transfer their data to AUV. After each tour (round), AUV returns to the start point from where it sends data to the surface sink. PN assigns the time slots through TDMA to MNs for data transmission. Table 1 presents the in-depth comparative analysis of the selected protocols.

Table 1.

Comparative analysis of the selected routing protocols.

Protocol	Node deployment	Sensor batteries	Control mechanism	Sink mobility	Sinks	Route processing	Network lifetime	Throughput	Delay
LEACH	Random	Homogeneous	Centralized	Nil	1	Proactive	+	++	+
LEACH-C	Random	Homogeneous	Centralized	Nil	1	Proactive	+++	+++	++
Multi-hop LEACH	Random	Homogeneous	Centralized	Nil	1	Proactive	++	++	++
S-LEACH	Random	Homogeneous	Centralized	Nil	1	Proactive	++	++	+
A-LEACH	Hybrid	Homogeneous	Centralized	Nil	1	Proactive	++	++	+
TEEN	Random	Homogeneous	Centralized	Nil	1	Reactive	+++	+	++++
APTEEN	Random	Homogeneous	Centralized	Nil	1	Reactive	+++	+	++++
SEP	Random	Heterogeneous	Centralized	Nil	1	Proactive	++	++	+++
DEEC	Random	Heterogeneous	Distributed	Nil	1	Proactive	+++	+++	++++

LEACH: low-energy adaptive clustering hierarchy; LEACH-C: LEACH centralized; S-LEACH: secure LEACH; A-LEACH: advanced LEACH; TEEN: threshold-sensitive energy-efficient sensor network protocol; APTEEN: adaptive TEEN; SEP: stable election protocol; DEEC: distributed energy-efficient clustering.

The proposed protocol: AM-DisCNT

In order to cope with the problems stated in the introduction and motivation sections, we proposed a new proactive routing protocol, AM-DisCNT, for heterogeneous WSNs. The proposed protocol uses direct communication and static clustering to cope with the design constraints. Our work is based on the assumption that the network field is circular. Coverage means that sensed data from the entire network field is accessible at the BS. Rather than randomly deploying nodes in the entire network field, we randomly deploy uniform number of nodes in each sub-region to ensure full area coverage. Detailed description is provided in the upcoming subsections.

Field distribution and architecture

AM-DisCNT divides the network area into two concentric circles: inner circle with radius “ $r_{i}$ ” and outer circle with radius “ $r_{0}$ .” BS is placed at the center of the circle. Circular region is considered to get maximum output from every region of the network. Unlike rectangular networks, corner nodes do not consume extra energy during communication. Inner circle nodes directly send the sensed data to BS, whereas, outer circle nodes communicate with their respective CHs.

The schematic diagram of AM-DisCNT is summarized in Figure 3. N nodes are deployed randomly in two circular regions: inner circle and outer circle. The nodes are assumed to be static, that is, their position does not change after deployment. Inner circle nodes directly send sensed information to BS, whereas outer circle nodes are further organized into eight sub-regions. This logical divisioning is done for the purpose of clustering. Equal number of nodes are deployed in each region. In the outer eight regions, fixed number of nodes are randomly deployed to provide full area coverage. Outer region nodes send sensed data to their respective CHs, and the CHs then forward the data either directly to BS or through intermediate node of inner circle depending on its transmission range which is shown Figure 3.

Figure 3.

Schematic diagram of AM-DisCNT: (a) network topology, (b) inner circle: nodes to BS communication, and (c) outer region: communication of nodes with CH.

Nodes are often located far from the BS, and they always have data to transmit. Outer circle of AM-DisCNT is divided into eight equal regions. Thus, the network area consists of nine regions: a inner circular region “ $T_{1}$ ” and eight outer regions (from $R_{1}$ to $R_{8}$ ). Area divisioning decreases the communication distance between sender and receiver. $T_{1}$ of the network is formed to separate nearer nodes from farther nodes. $n_{T 1}$ nodes out of N are randomly deployed in $T_{1}$ . x and y coordinates of $n_{T 1}$ are calculated as

X_{n_{T 1}} = r_{i} \cos (θ)

(1)

Y_{n_{T 1}} = r_{i} \sin (θ)

(2)

where $0 \leq θ \leq 2 π$ and $0 < r_{i} \leq S$ . S can be any positive integer.

In order to deploy the nodes, we assume the ability to detect the empty areas and then deploy nodes in those empty areas. First, $n_{T 1}$ nodes are deployed in $T_{1}$ and then the nodes $n_{r 1}, \dots, n_{r 8}$ are deployed in $r_{1}, \dots, r_{8}$ , respectively. We also assume that the communication range of all the wireless nodes is within their own defined regions except CHs. The nodes are bounded to communicate within their own specified regions. In regions $r_{1}$ to $r_{8}$ , the x and y coordinates of nodes are given in the same way as for circular region “ $T_{1}$ ” in equations (1) and (2). Value of $θ$ is different in the following equation

X_{i} = R_{0} \cos (θ) Y_{i} = R_{0} \sin (θ)

here $θ$ is a variant of $n (π / 4)$ , given $n = 0 - 8$ and $R_{0} = r_{2} - r_{1}$ , where $i = 1, \dots, 8$ . $R_{0} = r_{j} = r_{(i + 1)} - r_{(i)}$ . To divide outer circle into regions, two limits of $θ$ are defined for each.

Selection of CHs

In each round, eight CHs are selected for outer circular region, one from each sub-region. These CHs are selected on the basis of nodes’ residual energies. CHs collect data from their own regions and after aggregation send these data to BS. CHs either transmit directly to BS or through inner circle nodes, depending on the residual energy. After the first round, energy of each node is calculated and highest energy nodes are selected as CHs. Such type of clustering ensures maximal area coverage.

AM-DisCNT considers first-order radio model for energy consumption of nodes.²⁰ We also consider a path loss of $(distance)^{2}$ in transmitting a k-bit packet. Equation for the transmission of k-bit packet through distance d, provided $d < d_{0}$ , is

E_{TX} = E_{elec} k + ϵ_{fs} k d^{2}

(3)

where $ϵ_{fs}$ is the radio parameter used to achieve an acceptable signal-to-noise (SNR) ratio. Equation for transmission of k-bit packets through distance d provided

E_{TX} = E_{elec} k + ϵ_{amp} k d^{4}

(4)

For the reception of k-bit packet

E_{RX} = E_{elec} k

(5)

Heterogeneity of the network

We consider a multi-level heterogeneous network in such a way that first we develop a two-level heterogeneous network model, followed by three levels, and finally, its generalization into a multi-level heterogeneous network model. Advanced nodes own $α$ times more energy than the normal ones. $E_{0}$ is the initial energy of normal nodes, and $(1 - m) N$ is the total number of advanced nodes. “m” is the fraction of advanced nodes. mN number of advanced nodes are equipped with total energy of $E_{0} (1 + α)$ . Thus, the total initial energy of two-level heterogeneous network is given by the following equation

E_{total} = N E_{0} (1 + m α)

(6)

Total energy of three-level heterogeneous networks is given by

E_{total} = N E_{0} (1 + m (α + m_{0} β))

(7)

where the fraction of super nodes is denoted by $m_{0}$ and the super nodes have $β$ times more energy than the normal ones.

AM-DisCNT considers a wireless multi-level heterogeneous network. Energy is randomly distributed among all the nodes of the network. The energy of nodes is given by the following equation

E_{node} = E_{0} (1 + t α)

(8)

where $E_{0}$ is the initial energy of nodes and the nodes may have $α$ times more energy than the initial energy $E_{0}$ . Thus, the total energy of multi-level heterogeneous wireless network is given by

E_{total} = \sum_{t = 1}^{N} E_{0} (1 + t α)

Extending AM-DisCNT: iAM-DisCNT

The proposed AM-DisCNT minimizes the communication distance between nodes and BS and uses fixed number of CHs to minimize energy consumption during each round. AM-DisCNT’s performance is far better than LEACH; however, when compared to DEEC, results are not satisfactory in terms of throughput. On average, DEEC outperforms AM-DisCNT, two times out of five. This behavior of DEEC is due to the CHs’ fluctuation in each round. Greater number of CHs implies larger throughput. This problem is catered in iAM-DisCNT.

This section contains four subsections: (1) iAM-DisCNT, (2) energy-consumption calculation, (3) information flow maximization model, and (4) packet drop minimization model. Details are given in the upcoming sections.

iAM-DisCNT

iAM-DisCNT inherits all features from AM-DisCNT except the deployment and operations of BS. Thus, we only discuss placement and working of BS. Three BSs, one static and two mobile, are deployed to maximize the throughput while providing full area coverage. In iAM-DisCNT, mobile BSs are introduced in the network which replace the role of CH. Mobile BS receives data from nodes at minimum distance, minimizes their energy consumption, and prolongs the network life and stability period. CHs drain more energy (relay the data of MNs) as compared to the MNs.

Static BS. Static BS is deployed in the inner circle of the network area. So, nodes lying in $r_{i}$ communicate directly with the static BS. Such type of BS deployment minimizes the energy consumption of nodes.

Mobile BSs. Mobile BSs provide energy-efficient data collection in WSNs.

Direct data collection. Mobile BSs collect data (during sojourn intervals) by staying at sojourn locations, directly from nodes as shown in Figure 4, where sojourn location is the location at which any of the two mobile stations stops for data receptions. The time duration for which mobile BS stays at any sojourn location within any of the sub-regions is called sojourn time. This technique reduces the communication distance between BS and nodes, thereby minimizing energy consumption.

Figure 4.

Schematic diagram of iAM-DisCNT.

The movement energy of mobile sink is much more than the communication energy. However, we assume that the sink has sufficient energy (it has no constraint of energy) and only the sensor nodes are energy constrained. Our focus is to minimize the energy consumption of nodes to enhance the network lifetime. As far as the scope of this article is considered, we have assumed smooth deployment. iAM-DisCNT considers two mobile BSs moving in outer circle of the network area. The mobile BSs move in a circular trajectory: one in clockwise direction, whereas the other in anticlockwise direction, meanwhile collecting data from the nodes. Circular trajectory is a path that is exactly at the middle of outer circle as shown in Figure 4. Two BSs move synchronously with constant velocity during their movement. Each BS broadcasts a message while moving. After that nodes share their current status with BS telling whether these are in communication range or not. If a node receives message from two BSs, it replies with a data packet to any one of them (randomly). Nodes, which are not in communication range of any BS, switch to sleep mode. Whereas, nodes which come to communication range of any BS switch to active mode and start transmissions.

Outer BSs $(S_{A})$ and $(S_{B})$ use basic equation of circle to follow their trajectory. For $S_{A}$ , the equations are

X_{A} = R_{A} \cos (θ)

Y_{A} = R_{A} \sin (θ)

(10)

For $S_{B}$ , the equations are

X_{B} = - R_{B} \cos (θ)

Y_{B} = - R_{B} \sin (θ)

(11)

where $θ$ varies from $0 \circ \leq θ \leq 360 \circ$ and $R_{A} = R_{B}$ .

From extensive simulations as well as literature review, we conclude that relatively better results are obtained when the outer circle is divided into eight sub-regions. This makes the total number of regions as nine, the inner region nodes communicating directly with the static sink. In literature,^1–3 different sink mobility patterns are explored. Based on their findings and the needs of our network architecture, we have selected anticlockwise and clockwise movement directions for the BSs.

Calculation of energy consumption

We develop the following set of mathematical equations to calculate the energy consumption of nodes in each segment.

Referring Figure 4, if $A_{i}$ is the area of inner region and $A_{0}$ is the area of outer region (consisting of eight sub-regions) then

A_{i} = π {r_{i}}^{2}

and

A_{0} = π ({r_{0}}^{2} - {r_{i}}^{2})

where $r_{i}$ and $r_{0}$ are the radii of inner and outer circles, respectively. Similarly, the number of nodes in inner region and outer region is calculated as follows

n_{i} = ρ_{i} π {r_{i}}^{2}

n_{0} = ρ_{0} π ({r_{0}}^{2} - {r_{i}}^{2})

where $ρ_{i}$ and $ρ_{0}$ are the node densities in inner and outer regions, respectively. So, the total number of nodes in the network area is calculated as follows

N = ρ_{0} π {r_{0}}^{2} - π {r_{i}}^{2} (ρ_{0} - ρ_{i})

(12)

Since the inner region nodes in both protocols, AM-DisCNT and iAM-DisCNT, consume same amount of transmit energy, we develop the following equations

E_{tx}^{i} = ρ_{i} π {r_{i}}^{2} (E_{elec} + ϵ_{fs} d^{2}) k

where $E_{elec}$ is the per bit electronic circuitry energy, $ϵ_{fs}$ is the amplifier type, d is the communication distance between sender and receiver, and k is the packet size in bits.

Using similar approach, we calculate energy consumption for the outer region non-CH nodes of AM-DisCNT as follows

E_{tx, non - CH}^{0, AM - DisCNT} = (π ρ_{0} ({r_{0}}^{2} - {r_{i}}^{2}) - 8) \times (E_{elec} + ϵ_{fs} d^{2}) k

Transmit energy of the CHs of AM-DisCNT is calculated as follows

E_{tx, CHs}^{0, AM - DisCNT} = 8 (E_{elec} + ϵ_{fs} d^{2}) k

Energy consumption of CHs in AM-DisCNT while gathering data is calculated as

E_{da, CHs}^{0, AM - DisCNT} = 8 (E_{elec} + E_{da} + ϵ_{fs} d^{2}) k

where $E_{da}$ is the per bit data aggregation energy.

In iAM-DisCNT, none of the nodes are selected as CHs from the outer region. So, these nodes only consume transmission energy which is calculated as follows

E_{tx}^{0, iAM - DisCNT} = (π ρ_{0} ({r_{0}}^{2} - {r_{i}}^{2})) \times (E_{elec} + ϵ_{fs} d^{2}) k

(13)

From these calculations, we conclude that the energy consumption of outer region nodes of iAM-DisCNT is less than that of AM-DisCNT. However, energy consumption is minimized at the cost of mobile BSs.

Information flow maximization model

Let us consider that the WSN is a graph $G = (N, L, S)$ , where $| N | = n$ nodes, $| L | = l$ links, and $| S | = k$ BSs such that $\exists (i, k) \in L$ if and only if the data of node i are intended for direct transmission toward BS. Hence, linear programming model for throughput maximization is as follows

Max \sum_{r} l . q_{i}^{k} (r) \forall r \in R

(14)

where

l = {\begin{matrix} 1 & if p_{l} \geq p_{s} \\ 0 & if p_{l} < p_{s} \end{matrix}

(15)

such that

C_{1} : q_{i}^{k} - R_{i}^{k} t_{k}^{m} \leq 0 \forall i \in N and k \in S

(14a)

C_{2} : λ_{i} t_{k}^{m} \leq F_{i}^{k} \forall i \in N and k \in S

(14b)

C_{3} : t_{k}^{m} \leq t_{\min} \forall k \in S

(14c)

C_{4} : E_{i} \leq E_{0} \forall i \in N

(14d)

The objective function in equation (16) is to maximize the information flow “q” from node “i” to BS “k” during the current round “r” belonging to the set of rounds “R” throughout the network lifetime. This objective function depends on the link flag “l” which depends on the probability of given link “ $p_{l}$ ” such that if its value is greater than or equal to the minimum required probability for successful transmission “ $p_{s}$ ,” the flag is raised, else not. Constraint in equation (14a) determines $R_{i}^{k}$ as the upper bound on transmission rate of link $(i, k) \in L$ during the sojourn time “t” of BS “k” at sojourn location “ $m \in M$ ” as shown in Figure 4. Similarly, constraint in equation (14b) determines that the information generation rate “ $λ$ ” should not exceed the outgoing flow “F” during sojourn time. Violation of $C_{1}$ and/or $C_{2}$ leads to loss of data which ultimately results in decreased data flow. Constraint in equation (14c) provides explanation about the sojourn time (stay time at location m) of the BS that this interval should be at least equal to the minimum required time for successful data transmission. Alternatively, equation (14c) indicates about the existence of trade-off between delay and network lifetime. Equation (14d) deals with energy constraint, that is, each node is equipped with an energy source “ $E_{i}$ ” upper bounded by $E_{0}$ . Nodes cease transmissions whenever their batteries are drained out; so, for data flow maximization, the energy of nodes needs to be saved. In this regard, iAM-DisCNT puts a stop on node-to-node communication ( $q_{i}^{j} = 0 and q_{j}^{i} = 0$ ) which is further facilitated by setting $q_{k}^{i} = 0$ . This means that each node can only transmit data packets to BS, thereby not concerned with data-packet reception from node(s) or BS(s), thus saving energy. Moreover, data flow is maximized with the introduction of two mobile sinks and one static sink.

Packet drop minimization model

In addition to the information flow maximization, our second objective is to minimize the packet drop rate such that throughput of the network is maximized. In subject to this, we develop a linear-programming-based mathematical formulation as follows

Min \sum_{r} P D (r) \forall r \in R

(16)

such that

C_{1} : n_{s} \to n_{s}^{opt}

(16a)

C_{2} : d_{i, k} \to d_{i, k}^{\min} \forall i \in N and k \in S

(16b)

C_{3} : Min I_{ch}

(16c)

C_{4} : q_{i}^{-} + λ_{i} t \leq q_{i}^{+} \forall i \in N

(16d)

The objective function, $\sum_{r} PD (r)$ , in equation (16) aims to minimize the total number of dropped packets. Constraint (16a) states that the number of sojourn locations “ $n_{s}$ ” should approach its optimal value $n_{s}^{opt}$ . Agreement with $C_{1}$ means proper cluster size which in turn means decreased contention for channel access at sojourn location(s), thus leading to decreased packet drop rate as rounds proceed. Similarly, constraint (16b) focuses on the minimization of communication distance “ $d_{i, k}$ ” to approach its minimum possible value $d_{i, k}^{\min}$ whenever node “i” is intended to communicate with BS “k” at particular sojourn location. Violation of $C_{2}$ means low SNR value at the receiver end which causes increased packet drop rate. In addition, constraint (16c) aims to minimize channel interference “ $I_{ch}$ ”; it includes both co-channel and adjacent channel interference. In case of high-channel interference, the packet drop rate would increase and vise versa. Finally, constraint (16d) does not allow the incoming data flow at a given node “ $q_{i}^{-}$ ” plus the data generated by that node “ $λ_{i}$ ” during time span “t” to exceed its outgoing data flow limit “ $q_{i}^{+}$ .” Violation of $C_{4}$ would lead to buffer overflow because arrival rate exceeds the packet-handling capacity. In other words, violation of $C_{4}$ would lead to increased packet drop rate.

Graphical analysis

Let $q_{i}^{+}$ is varied between $0 - 2000$ bits, such that $λ_{i} t_{k}$ is between $0 - 250$ bits and $q_{i}^{-}$ is between $0 - 1750$ bits. Considering these values, the bounds for constraint in equation (16d) can be re-written as follows

0 \leq q_{i}^{-} + λ_{i} t_{k} \leq 2000 \forall i \in N

(16d-i)

0 \leq q_{i}^{-} \leq 1750 \forall i \in N

(16d-ii)

0 \leq λ_{i} t_{k} \leq 250 \forall i \in N

(16d-iii)

In subject to the bounds provided by equations (16d-i to 16d-iii), Figure 5 shows the intersection of five lines ( $L_{1}$ , $L_{2}$ , $L_{3}$ , $L_{4}$ , and $L_{5}$ ). As can be seen in this figure, the intersection results in a bounded region (which is colored cyan) as the feasible region. In this region, the set of all possible solutions lie. Other than this region, all other solutions are invalid. In order to verify the validity of our statement, let us test each vertex of the feasible region for valid solution. At $p_{1}$ : (0, 250) = 0+250 = 250 bits, at $p_{2}$ : (0, 0) = 0+0 = 0 bits, at $p_{3}$ : (1750, 0) = 1750+0 = 1750 bits, and at $p_{4}$ : (1750, 250) = 1750+250 = 2000 bits. Hence, it is proved that the set of all possible solutions that lie within the premises of feasible region is valid.

Figure 5.

Feasible region.

Simulation results

In this section, we evaluate the performance of the proposed protocols using MATLAB for simulations. A total of 20 nodes are randomly deployed in the inner circle. Outer circle is further divided into eight regions. Each region contains 10 nodes. These nodes are randomly deployed within the defined regions. Radius of inner circle $(R_{1})$ is taken as 20 m and radius of outer circle $(R_{2})$ is 35 m. BS trajectory is considered at a distance of 27 m from the center, that is, $R_{A}$ . Simulation parameters are shown in Table 2, and average results with $90 %$ confidence interval are shown and discussed in the upcoming sections.

Table 2.

Simulation parameters.

Parameter	Value
N	100
$R_{1}$	$27 m$
$R_{2}$	$100 m$
$E_{0}$	$0.5 J$
$ϵ_{fs}$	$10 pJ / bit / m^{2}$
$E_{elec}$	$50 nJ / bit$

Figure 6 shows that the stability period and network lifetime of the proposed protocols are greater than the existing protocols. AM-DisCNT’s superior performance in comparison with LEACH and DEEC is due the minimization of communication distance and proper selection of CHs. iAM-DisCNT shows further improvement in stability period and network lifetime at the cost of multiple BSs (one static and two mobile). Furthermore, we can interpret that instead of variable number of CHs in LEACH and DEEC, the proposed protocols rather select fixed number of CHs per round: one CH per region in the outer circle. This type of CH selection ensures data delivery from every part of network to BS, thus ensuring full area coverage.

Figure 6.

Network lifetime.

The rate at which CHs are selected in the proposed as well as chosen existing routing protocols is shown in Figure 7. This figure depicts that the selected CHs in LEACH routing protocol vary from 5 to 15 (per round) during initial rounds and then this rate drops to zero. Similar is the case with DEEC protocol, where the selected CHs fluctuate between 3 and 36 during initial rounds. Both of these protocols do not guarantee optimum number of CHs throughout the network lifetime. Fluctuation in CH number is due to random selection criteria of these protocols. In response, this random number of selected CHs may lead to one of the two drawbacks: (1) the selected CHs are more than the required number of CHs and (2) the selected CHs are less than the required number of CHs. Alternatively, the first drawback means surplus energy consumption and the second drawback means large cluster size. Surplus energy consumption leads to decreased network lifetime, and large cluster size leads to more load on the selected CHs. AM-DisCNT routing protocol fixes both of these drawbacks by selecting one CH per round from each of the eight outer regions. iAM-DisCNT further extends the network lifetime by introducing mobile BSs. These results show that AM-DisCNT has approximately 32% and iAM-DisCNT has approximately 48% improved stability period as compared to LEACH and DEEC routing protocols, respectively.

Figure 7.

CH selection frequency.

From Figure 8, we see that LEACH sends the smallest number of packets to BS as compared to DEEC, AM-DisCNT, and iAM-DisCNT. This is due to LEACH in which all nodes are homogenous. Such assumption selects low-energy nodes as CHs instead of high-energy nodes, thereby increasing dead nodes in the network which causes the loss of useful data. DEEC performs better than LEACH because it selects CHs based on the ratio of residual energy of nodes and average energy of the network. This conserves energy and increases network lifetime, thus increasing the number of packets sent to BS. The performance of DEEC and LEACH is not satisfactory because of varying cluster sizes. Farther nodes use more energy to send the sensed data and die quickly leaving some area un-monitored. AM-DisCNT’s performance is far better than LEACH; however, when compared to DEEC, the results are not satisfactory in terms of the number of packets sent to BS. On average, DEEC outperforms AM-DisCNT, two times out of five. This behavior of DEEC is due to the fluctuation of CHs in each round. Greater number of CHs implies larger number of packets sent to BS. This problem is catered in iAM-DisCNT using one static and two mobile BSs. This approach increases the probability of direct communication between nodes and BS, and less distance between nodes and BS reduces the energy consumption of nodes leading to maximized number of packets sent to BS.

Figure 8.

Number of packets sent to BS.

Whenever packets are sent from source to destination through wireless channel, some transmitted packets may get dropped due to bad channel conditions. In order to calculate dropped packets, we use “Random Uniformed Model.”²⁸ We set the probability of channel to be in bad status as 0.3 (30%). Figure 9 shows the number of successfully received packets at BS for the newly as well as selected existing routing protocols. iAM-DisCNT shows greater number of successfully received packets at BS as compared to LEACH, DEEC, and AM-DisCNT routing protocols. The throughput of AM-DisCNT and iAM-DisCNT is improved by approximately 16% and 80%, respectively, as compared to the counterpart schemes.

Figure 9.

Number of packets received at BS.

Figure 10 shows the end-to-end delay comparison of iAM-DisCNT, AM-DisCNT, LEACH, and DEEC. Greater end-to-end delay, in case of DEEC and LEACH protocols, is due to greater queuing and processing delays. Due to distant communication between sender and receiver, LEACH and DEEC exhibit greater end-to-end delay. In AM-DisCNT, logical divisioning of the network area decreases the communication distance for the delivery of packets causing minimization of the propagation time, thereby showing least end-to-end delay among the selected routing protocols. Introduction of mobile and static BSs, in iAM-DisCNT, increases the chances of direct communication with BS which decreases the propagation delay from nodes to their respective BSs to some extent. However, data-packet delivery to final destination increases the overall propagation delay which alternatively increases the end-to-end delay.

Figure 10.

End-to-end delay.

Performance trade-offs

In order to achieve a(some) desired objective(s), routing protocols pay its(their) cost in terms of other performance metric(s): trade-off(s). In this section, we analyze the four simulated routing protocols (LEACH, DEEC, AM-DisCNT, and iAM-DisCNT) in terms of performance trade-offs. We thus refer Figures 6, 9, and 10 and Table 3; DEEC achieves higher energy efficiency as well as throughput as compared to LEACH, however, at the cost of high end-to-end delay. A major reason for this relatively higher end-to-end delay is distant communication. AM-DisCNT logically divides the network area to minimize the end-to-end delay that also leads to increased energy efficiency. This is obvious as the local clusters are more restricted, that is, minimization of the communication distance. However, this achievement is made at the cost of restricted freedom at the time of node deployment (uniform random deployment of nodes). iAM-DisCNT further improves the network lifetime and throughput at the cost of an additional mobile sink. Moreover, this protocol also pays the cost of somewhat increased end-to-end delay as compared to AM-DisCNT. All these trade-offs are summarized in Table 4.

Table 3.

Comparative analysis of the selected routing protocols.

Protocol	Node deployment	Sensor batteries	Control mechanism	Sink mobility	No. of sinks	Route processing	Network lifetime	Throughput	Delay
LEACH	Random	Homogeneous	Centralized	Nil	1	Proactive	+	++	++
DEEC	Random	Heterogeneous	Distributed	Nil	1	Proactive	+++	+++	++++
AM-DisCNT	Hybrid	Heterogeneous	Hybrid	Yes	1	Proactive	++++	+++	+
iAM-DisCNT	Hybrid	Heterogeneous	Hybrid	Yes	2	Proactive	+++++	++++	+++

LEACH: low-energy adaptive clustering hierarchy; DEEC: distributed energy-efficient clustering; AM-DisCNT: angular multi-hop distance–based clustering network transmission; iAM-DisCNT: improved AM-DisCNT.

Table 4.

Comparative analysis of the selected routing protocols.

Protocol	Achievement(s) made	Cost paid
LEACH	freedom in node deployment	network lifetime
DEEC	network lifetime and throughput	end-to-end delay
AM-DisCNT	end-to-end delay and network lifetime	freedom in node deployment
iAM-DisCNT	network lifetime and throughput	end-to-end delay and an additional mobile sink

Conclusion and future work

In this article, we have proposed two new energy-efficient routing protocols for WSNs: AM-DisCNT and iAM-DisCNT. The leading one uses static clustering and maximum residual energy–based CH selection. The beauty of this protocol is the formation of fixed number of CHs in the defined regions per round which reduces the communication distance within clusters. However, the throughput of AM-DisCNT is not satisfactory. The lagging one, iAM-DisCNT, uses two mobile BSs and direct contact data collection technique to associate nodes with BS. Mobile BSs follow a pre-defined trajectory, minimizing the communication distance. In addition to the two newly proposed protocols, graphical analysis of the proposed linear-programming-based mathematical models provides the bounds within which the set of all possible solutions lie. Simulation results show better performance of AM-DisCNT and iAM-DisCNT as compared to LEACH and DEEC routing protocols in terms of stability period, network lifetime, and throughput. Based on these results, we have also analyzed the four simulated routing protocols in terms performance trade-offs.

In future, we are interested to exploit the work in Sun et al.²⁹ for the selection of CHs along with quality routing link metrics in Javaid et al.³⁰ Moreover, real-time experimental test bed development is also under consideration.

Footnotes

Academic Editor: Seungmin Rho

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by the Deanship of Scientific Research at King Saud University through Research Group Project no. RG#1435-051.

References

Akyildiz

Sankarasubramaniam

. Wireless sensor networks: a survey. Comput Netw 2002; 38(4): 393–422.

Liu

Ruan

A dynamic and energy-efficient clustering algorithm in large-scale mobile sensor networks. Int J Distrib Sens N 2013; 2013: 8

Anisi

Abdullah

Coulibaly

. EDR: efficient data routing in wireless sensor networks. Int J Ad Hoc Ubiq Co 2013; 12(1): 46–55.

Hamid

Alam

Islam

. Fair data collection in wireless sensor networks: analysis and protocol. Ann Telecommun 2010; 65(7–8): 433–446.

Akkaya

Younis

A survey on routing protocols in wireless sensor networks. Ad Hoc Netw 2005; 3(3): 325–349.

Liang

Gao

Zhang

. Efficient event detecting protocol in event-driven wireless sensor networks. IEEE Sens J 2012; 12(6): 2328–2337

Ahmad

Javaid

Khan

. (ach)²: routing scheme to maximize lifetime and throughput of WSNs. IEEE Sens J 2014; 14(10): 3516–3532.

Zytoune

El-Aroussi

Aboutajdine

An energy efficient clustering protocol for routing in wireless sensor network. Int J Ad Hoc Ubiq Co 2011; 7(1): 54–59

Liao

Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks. IEEE Sens J 2013; 13(5): 1498–1506.

10.

Jin

Jinsung

Sungyoung

. Hop-based energy aware routing algorithm for wireless sensor networks. IEICE T Commun 2010; 93(2): 305–316.

11.

Rao

Akbar

Javaid

. AM-DisCNT: angular multi-hop distance based circular network transmission protocol for WSNs. In: Proceedings of the 8th international conference on broadband and wireless computing, communication and applications (BWCCA13), Compiegne, 28–30 October 2013.

12.

Heinzelman

Chandrakasan

Balakrishnan

. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd annual Hawaii international conference on system sciences, Maui, HI, 4–7 January 2000, p.10. New York: IEEE.

13.

Heinzelman

WB.

Application-specific protocol architectures for wireless networks. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, 2000.

14.

Israr

Awan

Multihop clustering algorithm for load balancing in wireless sensor networks. Int J Simulat Syst Sci Tech 2007; 8(1): 13–25.

15.

Ali

Dey

Biswas

. A-LEACH: advanced leach routing protocol for wireless microsensor networks. In: Proceedings of the international conference on electrical and computer engineering (ICECE 2008), Dhaka, Bangladesh, 20–22 December 2008, pp.909–914. New York: IEEE.

16.

Manjeshwar

Agrawal

. Teen: a routing protocol for enhanced efficiency in wireless sensor networks. In: Proceedings of the 1st international workshop on parallel and distributed computing issues in wireless networks and mobile computing, San Francisco, CA, April 2001.

17.

Manjeshwar

Agrawal

. APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks. In: Proceedings of the 16th international parallel and distributed processing symposium, Ft. Lauderdale, FL, 15–19 April 2002, p.48. New York: IEEE.

18.

Smaragdakis

Matta

Bestavros

SEP: a stable election protocol for clustered heterogeneous wireless sensor networks. Technical report, Computer Science Department, Boston University, Boston, MA, 2004.

19.

Aderohunmu

Deng

JD.

An enhanced stable election protocol (SEP) for clustered heterogeneous WSN. IEEE Commun Mag 2002; 9(2002): 3–79

20.

Qing

Zhu

Wang

Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks. Comput Commun 2006; 29(12): 2230–2237.

21.

Elbhiri

Saadane

Aboutajdine

Stochastic distributed energy-efficient clustering (SDEEC) for heterogeneous wireless sensor networks. ICGST-CNIR J 2009; 9(2): 11–17.

22.

Luo

Hubaux

JP.

Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility. IEEE/ACM T Network 2010; 18(3): 871–884.

23.

Behdani

Smith

Xia

The lifetime maximization problem in wireless sensor networks with a mobile sink: MIP formulations and algorithms. IIE Trans 2013; 45(10): 1094–1113.

24.

Haeyong

Taekyoung

Pyeongsoo

Multiple sink positioning and routing to maximize the lifetime of sensor networks. IEICE T Commun 2008; 91(11): 3499–3506.

25.

Rahim

Riadh

Andre-Luc

Load balancing techniques for lifetime maximizing in wireless sensor networks. Ad Hoc Netw 2013; 11: 2172–2186.

26.

Jorio

Fkihi

Elbhiri

. An energy-efficient clustering routing algorithm based on geographic position and residual energy for wireless sensor network. J Comput Netw Commun 2015; 2015: 170138 (11 pp.).

27.

Khan

Cho

HS.

A distributed data-gathering protocol using AUV in underwater sensor networks. Sensors 2015; 15(8): 19331–19350.

28.

Zhou

Cao

Chen

. A solution to error and loss in wireless network transfer. In: Proceedings of the international conference on wireless networks and information systems, Shanghai, China, 28–29 December 2009, pp.312–315. New York: IEEE.

29.

Sun

Cho

Lee

Node classification based on functionality in energy-efficient and reliable wireless sensor networks. Int J Distrib Sens N 2012; 2012: 12.

30.

Javaid

BiBi

Javaid

. Investigating quality routing link metrics in wireless multi-hop networks. Ann Telecommun 2014; 69: 209–217.

A multi-hop angular routing protocol for wireless sensor networks

Abstract

Keywords

Introduction

Related work

The proposed protocol: AM-DisCNT

Field distribution and architecture

Selection of CHs

Heterogeneity of the network

Extending AM-DisCNT: iAM-DisCNT

iAM-DisCNT

Calculation of energy consumption

Information flow maximization model

Packet drop minimization model

Graphical analysis

Simulation results

Performance trade-offs

Conclusion and future work

Footnotes

Declaration of conflicting interests

Funding

References