Sage Journals: Discover world-class research

Abstract

Sensed data can be forwarded only in one direction to the base station in one-dimensional queue wireless sensor networks different from mesh structure, so the network lifetime will be shortened if some continuous neighboring nodes have run out of their energy. So designing routing protocols for balancing energy consumption is a challenging problem. However, traditional and existing opportunistic routing protocols for one-dimensional queue wireless sensor network proposed so far have not yet addressed this problem to prolong the network lifetime by introducing sleep mode. In this article, we propose a distributed energy-efficient opportunistic routing algorithm accompanied by timeslot allocation by using specific network topology of one-dimensional queue wireless sensor network. In our new algorithm, clustering and routing tree construction is performed while introducing the optimal relay transmission distance achieved by using opportunistic routing principle, and at the same time, interference-free wake up time is scheduled, which may optimize energy consumption and decrease the number of various control messages as possible to prolong the network lifetime. Furthermore, this improves energy efficiency by introducing the operation mode giving up cluster head role. Simulation results show that the proposed protocol can significantly improve the network performance such as energy consumption and network connectivity, when compared with other existing protocols.

Keywords

One-dimensional queue wireless sensor network opportunistic routing routing tree construction timeslot allocation energy efficiency wireless sensor networks

Introduction

Routing is one of the key techniques in wireless sensor network (WSN). Any application such as ecological environment monitoring, health care, target tracking, and agriculture surveillance needs routing technique for forwarding sensed data by sensor nodes through several relay nodes to the base station (BS) or monitoring center. So far, many routing protocols have been proposed according to the requirement of different applications in WSN.^1–5

This article is focused on one-dimensional queue WSN, a linear network of regular network topology. In topology such as tree or mesh structure used in many applications, sensor nodes are distributed randomly in areas that are beyond people’s reach. However, in one-dimensional queue WSN, nodes are uniformly and densely deployed on a line and this type of network offers many applications such as ecological environment monitoring system along a river, fire monitoring and controlling system along a corridor, smart traffic monitoring system along a road, and tunnel or bridge and petroleum pipeline remote monitoring system. In such one-dimensional queue WSN, the geographical location of each node is fixed, and the distance between two neighboring nodes is always uniform and sensed data can only be forwarded in one direction to the BS. So the network becomes more unreliable and has high probability that network may be partitioned if some continuous nodes have run out of their energy.⁶ Therefore, it should be key metrics of designing routing protocol in one-dimensional WSNs to ensure energy efficiency and sensed data relay latency by balancing and optimizing energy consumption. Furthermore, including sleep mode in routing design through timeslot allocation could prolong the network lifetime by ensuring energy efficiency and also satisfy the requirement of sensed data relay latency considering interference between nodes in some degrees.

But existing routing protocols^7–13 in WSNs including one-dimensional queue WSN attempt to find the path of minimum energy consumption from the source node to the BS to achieve optimal energy consumption, considering that transmitting data consumes much more energy than collecting data. Besides, some other routing protocols^6,14–18 are proposed to ensure energy efficiency and to improve sensed data report latency. So far, several routing protocols for one-dimensional queue WSNs have been proposed but many of them don’t address the problem to improve the network lifetime by introducing sleep mode when opportunistic routing algorithms gathering constant data are adopted in one-dimensional queue WSNs having the fixed sink.

Our objective in this work is to solve the problem of energy efficiency raised when data gathering opportunistic routing algorithms are used in one-dimensional queue WSNs in the case of fixed sink. For this, we propose the distributed opportunistic routing algorithm accompanied by timeslot allocation in one-dimensional queue WSNs. The main idea of this algorithm is to achieve better energy efficiency by reducing overhead consumption of unnecessary control messages through opportunistic routing accompanied by timeslot allocation. This work should meet the goal to improve the network lifetime. For this goal, we optimize energy consumption by performing routing tree construction using predefined optimal relay distance based on opportunistic routing (OR) and interference-free timeslot allocation simultaneously and reduce various control messages used through this process by using characteristics of network topology so as to reducing energy consumption. In one-dimensional queue WSNs, the network topology is linear so identification of each node is unique and continuous and the geographical position is certain. Using such characteristic, as small number of messages as possible could be needed through clustering and constructing the routing tree accompanied by timeslot allocation. To prolong the network lifetime further by improving energy efficiency, it is crucial to reduce overhead consumption of various control messages used in constructing the routing tree by clustering and timeslot allocation on it as much as possible.

The contributions of our work are as follows:

We define construction of the routing sub-tree and timeslot allocation problem to reach the main objective of our work.

We present a distributed energy-efficient OR algorithm that routing tree construction and timeslot allocation are performed at the same time by using specific network topology of one-dimensional queue WSN.

Operation mode giving up CH role in clustering is introduced to improve the energy efficiency of the proposed algorithm more and more.

We analyze several properties of the proposed algorithm.

Extension simulations are conducted to demonstrate that the proposed protocol supports better energy efficiency than the other existing similar protocols.

The remainder of the work is organized as follows: section “Related works” gives a brief introduction of prior works in one-dimensional queue WSN. Section “System model and problem description” describes the network model and system model for the proposed protocol. A distributed energy-efficient opportunistic routing accompanied by timeslot allocation (DEEOR-TA) is detailed in section “The proposed algorithm”. Section “Protocol analysis” considers characteristics of the proposed protocol analytically. Section “Performance evaluation” analyzes the performances of DEEOR-TA and simulation results in detail and this work is concluded by the conclusions in section “Conclusion.”

Related works

Traditional routing protocols for WSNs have been proposed as the best path way by preselecting one or more fixed optimal routes before starting transmission and relaying packets through the fixed neighbors to a relay node. However, this way is not applicable to dynamic wireless environment which would trigger excessive link-level retransmission.

Therefore, OR is proposed. The main principle of OR is to overcome the drawback of unreliable wireless transmission by employing advantage of broadcast nature of the wireless medium that one transmission can be overheard by multiple neighbors.¹⁹ Out of this, it is known that forwarding can be continued as long as at least one neighbor along a route receives packets. It can improve the performance of traditional routing. The key issues in design of OR include forwarder set selection, prioritization, and duplicate transmission avoidance. We categorize the previously proposed OR protocols by different standards.¹⁹ By forwarder set selection method, it is classified in end-to-end forwarder set selection and hop-to-hop forwarder set selection.

End-to-end forwarder set selection such as ExOR (Extreme Opportunistic Routing),²⁰ MORE (MAC-independent Opportunistic Routing and Encoding),²¹ and Opportunistic routing in dynamic Ad Hoc networks (OPRAN)²² prioritizes the forwarder candidates by using predicted transmission count. ExOR integrates routing and MAC protocols. It improves routing performance by using long wireless link with high loss rate. Here, nodes closer to the destination node than a source node are included in forwarder set. MORE integrates OR and intra-flow network and is proposed for improving ExOR. Different from ExOR that uses duplicated packets, MORE uses the concept of innovative packets for judging whether received packets bring new information or not. OPRAN forms braid multipath set between source and destination through demand routing to support opportunistic forwarding. For this purpose, this protocol makes intermediate nodes record more sub-paths back to the source node and downstream to the destination station. With hop-to-hop forwarder set selection such as CORE,²³ OAPF,²⁴ and ENS_OR,⁷ each packet holder independently decides its own forwarder set along the path to the expected destination. Coding-aware opportunistic routing mechanism (CORE) makes a packet holder forward a packet to the next hop that leads to the best coding changes in its forwarder set by integrating localized network coding and OR. Such hop-to-hop forwarder set selection operation can significantly improve the end-to-end coding gain in packet delivery with little extra overhead consumption. OAPF (Opportunistic Any-Path Forwarding) introduces an any-path count (EAX) expected by possible forwarders and recursively calculates the near-optimal forwarder set at each possible forwarder to reach the destination. So extra high calculation overhead should be paid and more network state information should be gathered. Energy saving via opportunistic routing (ENS_OR) adopted the concept of an energy equivalent node for forwarder set selection based on OR principle in one-dimensional opportunistic network and derived the optimal transmission distance for energy saving and maximizing the network lifetime using it. ENS_OR with sleep mode algorithm⁸ is developed to decrease energy wastage due to the idle listening of nodes in ENS_OR, which is the main drawback of ENS_OR. It derives the optimum sleep interval using the current flow rate to increase the substantial amount of energy saving and prolong the lifetime of the network. This algorithm is event triggering scheme, that is, when an event is triggered, the node awakes instantly, receives data and the received data is transmitted to the sink node via the highest priority nodes. This is not adequate in the case of data gathering like our proposed method that all nodes sense and transmit data. Routing can also be classified into event triggering scheme, which drives routing algorithms when an event occurs, and data gathering scheme that constantly collects indices such as temperature and humidity in whole surveillance region. In data gathering scheme, ways of moving the sink to enhance the energy efficiency are studied.^25,26 These studies introduce the mobile sink for data gathering to handle the problem of unbalanced energy consumption. Our work aims to solve the problem of energy efficiency raised when data gathering OR algorithms are adopted in one-dimensional queue WSNs in the case of fixed sink.

Also, OR can be classified into location-based selection and topology-based selection according to the location of node and topology of network. Topology-based selections such as ExOR, MORE, CORE, and OAPF enable efficient OR by using local or global state information. Location-based selections such as GeRaF,²⁷ EQGOR,¹⁶ ENS_OR,⁷ and TE-OR⁶ determine a forwarder and its priority based on very little topology-based and no global topology-based network state information. GeRaF (Geographic Random Forwarding) is based on geographical location of each node and random forwarder selection via competition. In GeRaF, each packet carries the location information of the source and destination and only neighboring nodes closer to the destination than the source can be forwarder candidates. EQGOR (Efficient QoS-aware Geographic Opportunistic Routing) suggests multipurpose-multi-criteria optimal problem that satisfies various criteria together with energy efficiency, report latency and time complexity, and select forwarder candidates set and prioritize them using effective solving method. Time-aware and energy-efficient opportunistic routing (TE-OR) gathers residual energy of forward neighbors, pre-calculates, and prioritizes the forwarder set. It achieves energy efficiency and sensed data report latency goals by adopting different parameters to various types of packets.

System model and problem description

Network model

We consider the network model of one-dimensional queue WSNs with linear topology. In this model, nodes are uniformly deployed in a line and each node is provided with a unique and successive identification from 1 to M. All nodes except BS are powered by limited unchargeable battery.

It is assumed that transmission range, one of the key parameters, is set in $[D_{min}, D_{max}]$ and is changed according to the transmission of control messages and sensed data packet, where $D_{min}$ is the distance between two neighboring nodes.

Let the number of nodes in the maximum transmission range be j, then $D_{max} = j D_{min}$ . Interference range $R_{I} (v_{i})$ of node $v_{i}$ represents the range that the transmission of node $v_{i}$ interferes with the reception of node $v_{k}$ $‖ v_{k} - v_{i} ‖ \leq R_{I} (v_{i})$ when node $v_{i}$ transmits in fixed power. $R_{I} (v_{i})$ is assumed to be always $R_{I} (v_{i}) \geq (1 + β) R_{T} (v_{i})$ , where $R_{T} (v_{i})$ is transmission range and constant $β > 0$ ( $β \approx 1$ in actual).²⁸

The one-dimensional queue network can be modeled by a connected graph $G = (V, E)$ , where V is a set of all sensor nodes aligned on a line and E is a set of directed links between nodes. Let the specific node in V be the BS and $R \subseteq V$ is the set of data collection nodes defined by a monitor. Each directed link has a non-negative weight w, which denotes the total energy consumption in transmission and reception when node $v_{i}$ sends a packet to its neighboring node $v_{j}$ .

Energy model

In this article, we refer to transmitting and receiving energy consumption model of wireless communications as it is used by Bhardwaj et al.²⁹ and Min et al.³⁰ The energy consumption of transmitting and receiving l-bit packet, $E_{tx}$ and $E_{rx}$ , in this model can be expressed as follows

$E_{tx} = (E_{elec} + ε_{amp} d^{τ}) \times l$ (1)

$E_{rx} = E_{elec} \times l$ (2)

where E_elec is the basic energy consumption of running transmitter and receiver circuit and $ε_{amp}$ is the power coefficient of transmitting amplifier circuit. d is the distance from source to destination node, and $τ$ is wireless channel path-loss factor on the transmission path, which depends on the condition of wireless channel and satisfies $2 \leq τ \leq 4$ . In our work, we set $τ = 2$ . From above two equations, it is known that the energy consumption of transmitting l-bit packet is always much greater than packet receiving energy. In our model, it is assumed that the noise and environmental factors are constant, so only the transmitter can adjust its transmission power in the range of $[D_{min}, D_{max}]$ to make $E_{tx}$ to reach the minimum value.

Problem description

Construction of the routing tree is the precondition for collecting sensed data in WSNs. In Luo et al.,⁷ the optimal transmission distance to prolong the network lifetime by maximizing energy efficiency is derived as a constant (approximately 32 m). Therefore, in our work, we will achieve energy efficiency in forwarding by adopting this optimal transmission distance in one-dimensional queue WSN as the one for communication between two neighboring cluster heads (CHs). From now on, this distance will be called the optimal relay transmission distance. The optimal relay transmission distance is changed according to actual condition such as the distance to an energy equivalent node from each node and residual energy of each node in forwarder set. In general, routing based on clustering includes clustering (deciding a cluster head and cluster members joined to it) and then constructing the routing tree for relaying. However, since the network topology is linear and the relay distance between clusters are confirmed, clustering and constructing the routing tree are performed simultaneously. Clustering and constructing the routing tree are accompanied by exchanging control messages. So simultaneous performance of these two stages enables the number of control messages to be reduced.

Besides, in timeslot allocation phase, which introduces sleep mode, a timeslot is allocated to each node in the routing sub-tree that is included in data collection set following the demand of a monitor without interference based on the routing tree that includes all nodes in entire network. In general, construction of routing sub-tree consisting of the above data collection set and timeslot allocation are not performed simultaneously. First, the routing sub-tree is constructed and then control messages are used for timeslot allocation. However, special topology of one-dimensional queue WSN provides the possibility that even timeslot allocation could be simultaneously performed and enables the number of control messages to be reduced.

From above consideration, we define construction of the routing sub-tree and timeslot allocation problem to reach the main goal of our work as follows.

Definition 1

Given one-dimensional queue network $G = (V, E)$ , data collection set R and k available timeslots, constructing the routing sub-tree and timeslot allocation problem is construction of the routing tree by dividing the sensor network into clusters based on the optimal relay transmission distance and simultaneously timeslot allocation to each node without interference between nodes to reduce the overhead of the overall control messages.

Such problem is realized by following algorithm.

The proposed algorithm

Distributed Energy Efficient Opportunistic Routing accompanied by Timeslot Allocation (DEEOR-TA) is summarized as follows. DEEOR-TA algorithm is run in several rounds and each round involves two phases of clustering-based routing tree construction accompanied by timeslot allocation and data transmission.

Clustering-based routing tree construction phase accompanied by timeslot allocation contains two stages of routing tree construction and timeslot allocation. In a stage of the routing tree construction, the whole one-dimensional WSN is divided into clusters by selecting cluster heads (CHs) and cluster member (CM) nodes based on the optimal relay transmission distance. During this, the routing tree for collecting and relaying sensed data is also constructed. In timeslot allocation stage, energy consumption is minimized by allocating timeslots to CH nodes and their CM nodes based on the routing tree construction (BS is located at the root, a CH at each edge and CM nodes in leaves). Considering interference between nodes, timeslot allocation and constructing the routing tree are performed at the same time so that another control messages for timeslot allocation would not be used. This enables total sensed data report latency to be minimized. So the total energy consumption could be reduced further. To balance the energy consumption and prolong the network lifetime further, CH role giving up operation mode is adopted that makes a node plays only the role of CM node if its residual energy reaches its lower threshold. In data transmission phase, each sensor node aggregates its sensing data to its CH in an interference-free timeslot allocated to itself in the whole network and each CH conducts the aggregated sensing data to BS via the constructed routing tree.

The description of control messages that are used in the proposed algorithm is illustrated in Table 1.

Table 1.

Description of control messages.

Message	Description
BS_Msg	Tuple(token, R, (k−1))where token is initiation token and R is data collection set. (k−1) means that the number of available timeslots is k and that (k−1)th timeslot is allocated to BS for receiving data from the first-level CH.
Hello_Msg	Tuple(node_ID, node_priority, node_energy, R_membership)where node_priority is priority of a node that could be selected as CH, node_energy is residual energy of a node, and R_membership represents whether it is included in R.
CH_Msg	Tuple(node_ID, R, k′, (k′−1)_idlesub-timeslots)where R is data collection set. (k′−1)_idlesub-timeslots is sub-timeslots of (k′−1)th timeslot which is not used yet. k′ is a timeslot allocated to the next upper level CH.
Join_Msg	Tuple(node_ID, CH_ID, (k′−1)_assigned_sub-timeslot)where (k′−1)_allocated_sub-timeslot is a sub-timeslot allocated to itself in (k′−1)th timeslot.

As shown in Table 1, distance to BS or number of relay nodes is not represented in fields of all control messages. In one-dimensional network node-ID can represent its geographical location, so it can be calculated when the identification of each node, node_ID, is received correctly.

More details are provided in the following sections.

Cluster-based routing tree construction and timeslot allocation

Clustering-based routing tree construction

At this stage, CHs are selected among sensor nodes and the routing tree is constructed via them. For this purpose, we define the wireless transmission range r_inter and r_intra, respectively, for inter-cluster and intra-cluster communications. Let the optimal relay transmission distance for selecting relay nodes in a linear network verified in Luo et al.⁷ be D_optimum. The energy consumption for relaying can be optimized by using this distance in inter-cluster communication. The inter-cluster communication distance is defined as r_inter = D_optimum, and the intra-cluster communication distance is defined as r_intra = 1/2D_optimum.

First-level cluster

At the beginning, BS initializes new data collecting task and broadcasts BS_Msg message in r_inter for routing and timeslot allocation. Each node that receives BS_Msg and that its distance to BS is lower than r_inter calculates its priority by the following formula (3)

$\begin{matrix} P (i) = α \cdot \frac{D_{optimum}}{1 + | h \times D_{optimum} - d (i) |} \\ + (1 - α) \frac{(E_{i} - E_{threshold})}{E_{max}} \end{matrix}$ (3)

where $P (i)$ represents the priority of node i. h is the level number of cluster and belongs to $[1, L]$ (L is the number of levels). D_optimum is the optimal relay transmission distance calculated in Luo et al.,⁷ $d (i)$ is the distance from node i to BS, $E_{max}$ denotes the initial energy of nodes, and $E_{i}$ denotes the residual energy of node i. $E_{threshold}$ denotes the threshold energy. $α$ is a weighted coefficient to coordinate distance and energy. When $α$ is greater, the nearer to D_optimum the node is, the higher priority it has. When $α$ is smaller, the more the residual energy is, the higher priority it has. We shall set the $α$ value in experiment suitable for environment and application of this work. For calculation of priority, relative concepts are used since it is impossible to directly compare the distance and the energy.

Then, each node that receives BS_Msg massage within r_inter exchanges Hello_Msg massages with its neighboring nodes within r_inter to get their local information. To avoid collision of packets, each node sets the timer based on its $P (i)$ and if the timer expires, broadcasts its Hello_Msg massage. Hello_Msg includes its node identification, residual energy, membership in R, and priority information expressed by formula (3).

After exchanging Hello_Msg messages, the first-level cluster is formed. Each node gets neighboring nodes’ local information via exchanging Hello_Msg messages and compares its priority with the others. From formula (3), it is known that the node that is closer to D_optimum and has more residual energy, that is, the node with highest priority is selected as $C H_{1}$ .

Afterward, $C H_{1}$ broadcasts CH_Msg in r_inter. $⌊ D_{optimum} / D_{min} ⌋$ nodes (to simplify the consideration, if the number of nodes including CH in a cluster is odd, respectively $⌊ D_{optimum} / 2 D_{min} ⌋ = n / 2$ on the right and left. And if the number of nodes in a cluster is even, $⌊ D_{optimum} / 2 D_{min} ⌋ = n / 2$ on the right and $⌊ D_{optimum} / 2 D_{min} ⌋ - 1$ on the left respectively), which receive CH_Msg and its distance to $C H_{1}$ is smaller than $D_{optimum} / 2$ , inform $C H_{1}$ that it is a member node of the first-level cluster by replying Join_Msg if it is contained in R. CH and CM nodes formed in first-level cluster are denoted as $C H_{1}$ and ${CM}_{1}^{i}$ that means it is the cluster head and member node of the first-level cluster, respectively ( ${CM}_{1}^{i}$ : 1st member node of 1st cluster).

Since the first-level cluster plays the role of relaying more than sensing, different ways may be used to balance the energy consumption: increasing density of node in a cluster, forming two-dimensional cluster in the first-level cluster, making nodes in the first-level cluster be only responsible for relaying and so on. Each member node ${CM}_{1}^{i}$ transmits its sensing data to $C H_{1}$ . $C H_{1}$ aggregates sensed data and then transmits it to BS. If a parent node of each CH is denoted as parent(CH), parent of $C H_{1}$ is $parent (CH) = BS$ . Each node which is not joined to the first-level cluster, in so-called 0-level cluster, directly transmits sensed data to BS.

Lower level cluster

Each node in lower levels, which receives CH_Msg from the higher cluster and was not joined to the higher cluster, calculates its priority by formula (3). It represents the possibility that may be selected as a cluster head. Next, each node gets local information of neighboring nodes via exchanging Hello_Msg and $C H_{h}$ is selected based on that. Through broadcasting CH_Msg of the selected $C H_{h}$ and replying Join_Msg of nodes following that, the lower level cluster is formed. CH and CM nodes formed in lower level cluster are denoted as $C H_{h}$ and ${CM}_{h}^{i}$ that represents the number of level. Note that even though no node is involved in R in constructing a cluster, one node should be selected as CH for relaying data when each level cluster is formed. At the same time as the $h th$ level cluster is formed, the routing tree is constructed for relaying aggregated data from $h th$ level cluster to $(h - 1) th$ level cluster. When a cluster is formed and its CH is selected, we make the relay distance from $C H_{h}$ to $C H_{h - 1}$ satisfies the optimal relay transmission distance D_optimum of Luo et al.⁷ So a parent of $C H_{h}$ is $parent (C H_{h}) = C H_{h - 1}$ and relaying distance is the optimal relay transmission distance D_optimum. In such way, the routing tree T is constructed in $G = (V, E)$ where BS is located at the root, CH at the edge and CM nodes in leaves. Figure 1 shows formed clusters through this process and the routing tree.

Figure 1.

Clustering-based routing tree construction in one-dimensional queue WSN.

CH role giving up operation mode

To balance the energy consumption and to prolong the network lifetime, CH role giving up operation mode is introduced. In this mode, a node with residual energy that reaches the predefined energy threshold gives up CH role and plays only the role of CM. In more detail, in the successive data collection process, if all nodes in $h th$ level cluster have smaller residual energy than $E_{threshold}$ in formula (3), the lower threshold of residual energy $E_{lower - threshold}$ is used to form cluster. The lower threshold value is set to the half of $E_{threshold}$ in equation (3) according to Darabkh et al.⁵

Then, formula (3) will be changed as follows

$P (i) = {\begin{matrix} α \cdot \frac{D_{optimum}}{1 + | h \times D_{optimum} - d (i) |} + (1 - α) \frac{(E_{i} - E_{lower - threshold})}{E_{max}}, \\ E_{threshold} \geq E_{i} > E_{lower - threshold} \\ 0, E_{i} \leq E_{lower - threshold} \end{matrix}$ (4)

All nodes in a cluster recognize whose residual energy reaches the lower threshold through taking local information by exchanging Hello_Msg. In other words, a node with residual energy that reaches the lower threshold value sets its priority to 0 as shown in formula (4) and exchanges its priority. A node with priority 0 is excluded in selection of CH and senses data playing only the role as CM. If all nodes have lower residual energy than the lower threshold $E_{lower - threshold}$ , we will set the energy threshold to lower energy threshold and continue collecting data.

Timeslot allocation

At this stage, timeslots are allocated to each node in routing sub-tree at the same time as the routing sub-tree including all nodes in R is constructed based on the routing tree T where all nodes in the entire network are connected. Timeslot allocation must be performed in such way that nodes can be interference-free and total sensed data report latency can be minimized.³¹ We accept a time-division model that time is divided into fixed length timeslots in timeslot allocation. k consecutive timeslots are grouped together into a frame. In each frame, a timeslot $t s_{i} \in {0, 1, 2, \dots, k - 1}$ is allocated to each cluster head $C H_{i}$ in routing tree T, where k denotes the number of timeslots allocated to the whole network, $t s_{i}$ is a timeslot allocated to $C H_{i}$ . During timeslot $t s_{i}$ , $C H_{i}$ announces a beacon to synchronize with its children and wakes them up. Then it collects sensed data from them. During other timeslots excluding $t s_{i}$ , $C H_{i}$ goes to sleep mode. The value of k should be large enough to ensure that each node can find a timeslot.³² Because we define communication distances as r_inter = D_optimum and r_intra = 1/2D_optimum, interference range of inter-cluster communication and communication between CM and CH are 2D_optimum and D_optimum, size of a cluster, respectively. Since the network we consider is one dimensional, if $t s_{i} \in {0, 1, 2}$ among $k = 3$ timeslots in total is allocated to $C H_{i}$ , we may perform data collecting task without interference. When the number of nodes CM in a cluster is n, $t s_{i}$ of $C H_{i}$ contains all timeslots allocated to $C M_{i}$ to ensure interference-free communication of n CMs toward CH. And a timeslot allocated according to whether $C H_{i}$ is included in R or not, and another one for relaying data that receives from the lower level CH are contained in ts_i. Therefore, timeslots allocated to $C H_{i}$ and $C M_{i}$ are considered sub-timeslots of timeslot $t s_{i} \in {0, 1, 2}$ . Timeslot allocation is detailed in each level as follows.

Timeslot allocation to the first-level cluster

First of all, $C H_{1}$ of the first-level cluster recognizes which node is involved in data collection set R among its CMs through receiving BS_Msg. Also, it notices that $k - 1 = 2 nd$ timeslot among $k = 3$ timeslots is allocated to itself for relaying data to BS. Each timeslot, which would be allocated to CH, consists of sub-timeslots illustrated as Figure 2. Each node, which is not joined to the first-level cluster and so-called 0-level cluster, directly transmits the sensed data to BS by using sub-timeslots allocated to BS.

Figure 2.

Configuration of sub-timeslots among a timeslot.

All nodes in the first-level cluster would be recognized whether the others are included in R exchanging Hello_Msg each other or not.

Once $C H_{1}$ is selected through exchanging Hello_Msg, $C H_{1}$ broadcasts CH_Msg including $(k - 2) th$ timeslot with $⌊ D_{optimum} / D_{min} ⌋ + 2 = n + 2$ sub-timeslots, where one sub-timeslot is for relaying data that receives from the lower level CH and other $(n + 1)$ slots are for all nodes including CH in the current level. Then, the first sub-timeslot is used for relaying data that receives from the lower level $C H_{2}$ to BS, $s (C H_{1}) = (k - 2 : 1) mod (n + 2)$ , where $k - 2 : 1$ denotes the first sub-timeslot of $(k - 2) th$ timeslot.

Once the selected $C H_{1}$ is included in R, it should get the second sub-timeslot for its own sensed data, that is, $s (C H_{1}) = (k - 2 : 1, 2) mod (n + 2)$ , where s is a sub-timeslot allocated to $C H_{i}$ . In this case, $C H_{1}$ would make CH_Msg and broadcast, including the information that the first and second sub-timeslots of $(k - 2) th$ timeslot are allocated to itself. Each node ${CM}_{1}^{i}$ , which is included in R and in the first-level cluster by replying Join_Msg including the number of a sub-timeslot allocates to it once it receives CH_Msg, declares sub-timeslot allocation. At that time, sub-timeslots are allocated to member nodes of $C H_{1}$ from the farthest forward neighboring node away $C H_{1}$ in the sequence of 3^rd, 4^th, … If $C H_{1}$ is not the member of R, sub-timeslots are occupied from the second.

As mentioned above, in our work, a parent node just sets out sub-timeslots which are not occupied yet and a child node occupies them for itself different from prior works where a parent node allocates sub-timeslots to its child nodes. The precondition for using this method is that the network topology is one dimensional and linear. So each node has the unique and consecutive identification and certain geographical position.

Timeslot allocation to the lower level cluster

In the lower level (ex. h level) cluster, timeslots are also allocated following the above allocating principle. First, a timeslot is allocated to $C H_{h}$ as follows

$ts (C H_{h}) = {\begin{matrix} (k - (h mod 3)) mod k, h \neq 3 j \\ 0, h = 3 j \end{matrix}$ (5)

where $j = 1, 2, 3, \dots$ . Sub-timeslots of $ts (C H_{h})$ in h level of $C H_{h}$ are occupied in the same way as $C H_{1}$ . Sub-timeslot allocation to ${CM}_{h}^{i}$ can be generalized as follows. The first sub-timeslot of $ts (C H_{h})$ is allocated for relaying data from $C H_{h - 1}$ . If $C H_{h}$ is a node in R, the second sub-timeslot is occupied for its own sensing data.

Then, the remaining is allocated to the neighboring nodes from the forward neighboring nodes ${CM}_{h}^{i}$ of $C H_{h}$ , where i of ${CM}_{h}^{i}$ denotes the sequence number of member nodes included in h level cluster. They are numbered from the farthest forward neighboring node away $C H_{h}$ to the farthest backward neighboring node away $C H_{h}$ .

Then, $s ({CM}_{h}^{i})$ is denoted as follows

$s ({CM}_{h}^{i}) = {\begin{matrix} (k ″ : 2 + i) mod (n + 2), C H_{h} \in R \\ (k ″ : 1 + i) mod (n + 1), C H_{h} \notin R \end{matrix}$ (6)

where $k ″$ is a sub-timeslot allocated to $C H_{h}$ . It represents the case when all ${CM}_{h}^{i}$ nodes in h level cluster are included in R. In other case, that is, when some nodes are not included in R, sub-timeslots are allocated to member nodes in turn from the second or third sub-timeslot (it is determined whether $C H_{h}$ is contained in R or not), and inform $C H_{h}$ using Join_Msg. In the last L level, the first sub-timeslot is not allocated for relaying data and if $C H_{L}$ is involved in R, but it is allocated for sensing its own data. Figure 3 shows timeslots and sub-timeslots allocated to the nodes which are involved in R in the routing tree T. A number in circle denotes the number of timeslot allocated to CHs and a number denoted as $x : y$ means $y th$ sub-timeslot of $x th$ timeslot. Algorithm 1 shows h level cluster formation algorithm accompanied by routing tree construction and timeslot allocation.

Figure 3.

Timeslot allocation in one-dimensional queue WSN.

Algorithm 1. h Level cluster formation algorithm accompanied with routing tree construction and timeslot allocation.
Event: CH_h _-1 broadcasts CH_Msg(CH_h-1_ID, R, k′, (k′-1)_idlesub-timeslots) within r_inter.Input:E_i, E_threshold, E_{lower-threshold}; d(i);αOutput: CH_Msg(CH_h_ID, R, k′-1, (k′-2)_idlesub-timeslots)(1) for calculate priority operator P(i) for each node in set {node_i \|d(CH_h_-1) + 1/2D_optimum < d(i) ≤ d(CH_h_-1) + 3/2D_optimum} do(2) // node_i denotes the i^th node in the network;(3) ifE_i > E_threshold then(4) $P (i) = α \cdot \frac{D_{optimum}}{1 + \| h \times D_{optimum} - d (i) \|} + (1 - α) \cdot \frac{(E_{i} - E_{threshold})}{E_{max}}$ ;(5) else then(6) P(i) = 0;(7) end if(8) end for(9) //CH role giving up operation(10) if all priorities are 0 then(11) E_threshold←E_{lower-threshold};(12) go to 1;(13) end if(14) for each node in set {node_i \|d(CH_h_-1) + 1/2D_optimum < d(i) ≤ d(CH_h_-1) + 3/2D_optimum }do(15) Set and start the priority timer based on its priority P(i);(16) if the priority timer expires then(17) Broadcast a Hello_Msg within r_intra to exchange its local information.(18) end if(19) end for(20) Compare the priority operators and find the Maximum value.(21) About the node of the highest priority, do(22) State ←CH(23) Level_ID ←h(24) Parent ←CH_h-1(25) if the selected cluster head CH_h∈R then(26) CH_h occupies the first and second sub-timeslots {1,2}of timeslot ‘k′-2’;(27) (k′-2)_idlesub-timeslots ← {3, 4, …, n + 2};(28) else(29) CH₁ occupies the first sub-timeslots {1}of timeslot ‘k′-2’;(30) (k′-2)_idlesub-timeslots ← {2, 3, …, n + 1};(31) end if(32) Broadcasts CH_Msg(CH₁_ID, R, (k′-1), (k′-2)_idlesub -timeslots) within r_inter;(33) for each node in set {node_i \|CH_h_ID + D_optimum / (2D_min) ≥ i ≥ CH_h_ID–D_optimum/(2D_min), i∈Z } do(34) ifstate≠ && node_i∈R then(35) State ←CM(36) Level_ID ←h(37) Parent ←CH_h(38) Sub-timeslot ← the first sub-timeslot of (k′-2)_ idlesub-timeslots;(39) (k′-2)_idlesub-timeslots ← (k′-2)_idlesub-timeslots - {Sub-timeslot};(40) Send Join_Msg(i, CH_h_ID, Sub-timeslot) to CHh;(41) else if state = CH then(42) Receive Join_Msg from its member nodes;(43) end if(44) end for

Algorithm 1. h Level cluster formation algorithm accompanied with routing tree construction and timeslot allocation.

Event: CH_h _-1 broadcasts CH_Msg(CH_h-1_ID, R, k′, (k′-1)_idlesub-timeslots) within r_inter.Input:E_i, E_threshold, E_{lower-threshold}; d(i);αOutput: CH_Msg(CH_h_ID, R, k′-1, (k′-2)_idlesub-timeslots)(1) for calculate priority operator P(i) for each node in set {node_i |d(CH_h_-1) + 1/2D_optimum < d(i) ≤ d(CH_h_-1) + 3/2D_optimum} do(2) // node_i denotes the i^th node in the network;(3) ifE_i > E_threshold then(4)

P (i) = α \cdot \frac{D_{optimum}}{1 + | h \times D_{optimum} - d (i) |} + (1 - α) \cdot \frac{(E_{i} - E_{threshold})}{E_{max}}

;(5) else then(6) P(i) = 0;(7) end if(8) end for(9) //CH role giving up operation(10) if all priorities are 0 then(11) E_threshold←E_{lower-threshold};(12) go to 1;(13) end if(14) for each node in set {node_i |d(CH_h_-1) + 1/2D_optimum < d(i) ≤ d(CH_h_-1) + 3/2D_optimum }do(15) Set and start the priority timer based on its priority P(i);(16) if the priority timer expires then(17) Broadcast a Hello_Msg within r_intra to exchange its local information.(18) end if(19) end for(20) Compare the priority operators and find the Maximum value.(21) About the node of the highest priority, do(22) State ←CH(23) Level_ID ←h(24) Parent ←CH_h-1(25) if the selected cluster head CH_h∈R then(26) CH_h occupies the first and second sub-timeslots {1,2}of timeslot ‘k′-2’;(27) (k′-2)_idlesub-timeslots ← {3, 4, …, n + 2};(28) else(29) CH₁ occupies the first sub-timeslots {1}of timeslot ‘k′-2’;(30) (k′-2)_idlesub-timeslots ← {2, 3, …, n + 1};(31) end if(32) Broadcasts CH_Msg(CH₁_ID, R, (k′-1), (k′-2)_idlesub -timeslots) within r_inter;(33) for each node in set {node_i |CH_h_ID + D_optimum / (2D_min) ≥ i ≥ CH_h_ID–D_optimum/(2D_min), i∈Z } do(34) ifstate≠ && node_i∈R then(35) State ←CM(36) Level_ID ←h(37) Parent ←CH_h(38) Sub-timeslot ← the first sub-timeslot of (k′-2)_ idlesub-timeslots;(39) (k′-2)_idlesub-timeslots ← (k′-2)_idlesub-timeslots - {Sub-timeslot};(40) Send Join_Msg(i, CH_h_ID, Sub-timeslot) to CHh;(41) else if state = CH then(42) Receive Join_Msg from its member nodes;(43) end if(44) end for

Data transmission

In this case, a CM node, which occupies a timeslot, would wake up so as to transmit its sensed data to its CH during its timeslot.

Then, it would go to sleep. Note that a CH needs to wake up to aggregate data relayed from the lower level CH and sensed data by CMs in the current level, and that relays data to the upper level CH along the routing tree T. This process is repeated until sensed data finally reach BS.

Protocol analysis

Theorem 1

The overhead complexity of control messages, when DEEOR-TA is run, becomes 2M in each round.

Proof

For a new collecting task, each node within r_inter exchanges Hello_Msg by initial broadcasting of BS_Msg message, and then CH₁ is selected. After CH₁ broadcasts CH_Msg, each node in lower level exchanges Hello_Msg. At this time, backward neighboring nodes of CH that were attached to CH don’t exchange Hello_Msg. Thus, at most M, the number of whole nodes in the network, Hello_Msg messages are exchanged. The number of CH_Msg is equal to L if the number of levels is the same as the one of clusters. Meanwhile, in each round the number of Join_Msg messages is equal to M—L and are as many as the number of CMs in the whole network. Therefore, the total number of control messages in the whole network is expressed as formula (7)

$M (Hello_Msg) + L (CH_Msg) + (ML) (Join_Msg) = 2 M$ (7)

where x(y) means that the number of y control message is x.

Theorem 2

If the number of relay nodes interfering with each other is m, timeslot allocation without interference is possible when the number of available timeslots k satisfies $k \geq m + 1$ . And the relayed data report latency is at most (L−1).

Proof

Let each node have one or two direct neighboring nodes and interfere with each node in m relay nodes in one-dimensional queue network, where m satisfies $m \geq 2$ . So the maximum neighboring limit of the interference set can be set 2 m. The interference set is considered dividing into two sets of CHs and of CMs. Each node in set S_CH ={CH_i|i∈[1,L]} of CHs has the transmission range of R_T(CH_i) = 3/2D_optimum and R_I(CH_i) = 2×R_T(CH_i) = 3D_optimum if the interference range is set twice of the transmission range. Thus, each CH interferes with $m (= 2)$ CHs within interference range and $k = m + 1 = 3$ , where CHs are included in the range. And each CM node has the transmission range R_T(CM_i) = 3/4D_optimum so the interference range is R_I(CM_i) = 2×R_T(CM_i) = 3/2D_optimum. The distance between two neighboring CMs is $D_{min} = ⌊ D_{optimum} / n ⌋$ (where n denotes the number of CMs in a cluster) and the range of a cluster is D_optimum. But each CM in set S_CM occupies a sub-timeslot of a timeslot allocated to its CH. So interference between CM nodes is restricted within range of a cluster unless a timeslot of CH is duplicated. Thus, m =n +1 (where n denotes the number of CM nodes in a cluster) CM nodes interfere with each other and (n + 1) sub-timeslots must be allocated to each CM in each cluster.

Eventually, the number of timeslots and sub-timeslots for interference-free timeslot allocation must be set k =m + 1 = 3 and k =m +1 =n + 2, respectively, in the case of S_CH and S_CM. Sensed data report latency from node i to node j is defined as the number of timeslots (or sub-timeslots) that node i should wait for transmitting to node j. Thus, the number of sub-timeslots that each node in a cluster should wait is $n + 2 = ⌊ D_{optimum} / D_{min} ⌋ + 2$ if whole CM nodes in a cluster are involved in R. Namely, sensed data report latency of CM is at most $n + 2 = ⌊ D_{optimum} / D_{min} ⌋ + 2$ . Relayed data report latency means the number of timeslots that each CH should wait for relaying aggregated sensed data to BS.

There are L CHs, and one of them doesn’t play the relaying role, so relayed data report latency is at most $(L - 1)$ .

Theorem 3

Energy consumed for timeslot allocation of DEEOR-TA never reaches by twice of optimal value.

Proof

In timeslot allocation that is interference-free timeslot allocation to each node in the data collection set R accompanied by constructing the routing tree T, time slots for transmitting and receiving are fixed. Therefore, the difference between energy consumption in different timeslot allocation is the one between cost paid for timeslot allocation and synchronizing.

Each node switches its mode (from sleep mode to active mode) at least twice in the proposed timeslot allocation. In more detail, as shown in Figure 4, CM must wake up for transmitting its own sensed data to its CH.

Figure 4.

Data aggregating and relaying based on the routing tree in one-dimensional queue WSN.

Besides, CH must wake up for aggregating sensed data from every CM node including itself while receiving aggregated data from the lower level cluster and for transmitting aggregated data to the upper level cluster according to its reception requirement.

As there are L CHs in the network, Lth level CH has no lower level, so the number of CHs that must wake up twice is equal to (L−1). Thus, the total number of nodes that must switch its mode is at least M + (L−1) and energy consumption for switching mode is [M + (L−1)] times as much as that of one node. For any scheduling, each node needs to switch its mode at least once and energy consumption at this time can be considered the optimal energy consumption. If the optimal energy consumption for switching mode is denoted as $E_{state_switch}^{optimum}$ , then $E_{state_switch}^{optimum} \geq M \times E_{state_switch}$ , where E_{state_switch} denotes the energy of a node consumed for switching mode.

The total energy consumption of the proposed protocol is expressed as formula (8)

$\begin{matrix} E = E_{active}^{total} + E_{state_switch}^{total} = E_{active}^{total} \\ + [M + (L - 1)] E_{state_switch} < \\ < E_{active}^{optimal_total} + 2 M E_{state_switch} \\ < 2 E_{active}^{optimal_total} + 2 E_{state_switch}^{total} \\ = 2 E^{optimal} \end{matrix}$ (8)

where $E_{active}^{total}$ denotes energy consumed when all nodes are in active mode and $E_{state_switch}^{total}$ denotes total energy for switching mode. Thus, we conclude that energy consumed for timeslot allocation of DEEOR-TA never reaches by twice of the optimal value.

Performance evaluation

In this section, we evaluate the performance of our protocol in various aspects and then compare with ENS_OR and TE_OR, OR algorithms in one-dimensional queue WSN.

Simulation environment

We conduct experiment by MATLAB with 200 nodes uniformly distributed over a line. The uniform distance between neighboring nodes(D_min) is 5–25 m and inter-cluster and intra-cluster communication distances are, respectively, set r_inter =D_optimum≈32 m, r_intra = D_optimum/2≈16 m.

Other simulation parameters are listed in Table 2.

Table 2.

Simulation parameters.

Parameters	Value
Deployment area	50 m × 2500 m
Number of nodes	200
Distance between two neighboring nodes	5–25 m
E_elec	50 nJ/bit
ε_amp	100 pJ/bit/m²
E _max	1 J
E_threshold	0.6 J
E_{lower-threshold}	0.3 J
Active energy	0.9e–6 J
Sleep energy	9e–9 J
Packet size	1024 bit
Control message size	80 bit
Sending rate	1 packet/s
Data rate	1 Mbit/s

In this article, we assume that all nodes in entire Next, network are included in data collecting set R, that is, each node in entire network generates packets periodically and relays sensed data to BS. A duty cycle of each node is 0.1%. For instance, this is the duty cycle of a sensor that wakes up once every 1 s for 10 ms.

Performance metrics

We define four measurable metrics to evaluate the performance of DEEOR-TA in one-dimensional queue WSN.

Average of residual energy: More average residual energy indicates better energy efficiency of routing algorithm and it would help to prolong the network lifetime.

Variation of residual energy: It is used as a metric to evaluate the energy balancing characteristic and deviation. The smaller it is, the better the balancing characteristic and deviation are. It is calculated as standard deviation of residual energy.

Number of dead node: It is the number of nodes that run out of energy. This metric reflects connectivity of one-dimensional WSN. If dead time of a node is long, the number of dead nodes doesn’t decrease and good network connectivity can be hold.

Network lifetime: the network lifetime is defined as the time when the BS is unable to receive packet sent from the source node. It is closely related to the energy consumption and network connectivity.

Simulation results and analysis

Performance of DEEOR-TA

We assume that each node in the network periodically senses data and reports. Under this assumption, we consider the energy efficiency of DEEOR-TA.

First, we evaluate how parameter $α$ affects to selection of CH. In this experiment, we use min-max normalization in Jain and Bhandare³³ for the purpose to get values of distance factor and energy factor in the range [0,1] because the contribution degree of distance and energy factors to calculation of priority P(i) of node i in formula (4)

$\begin{matrix} P (i) = α \cdot (1 - \frac{| h \times D_{optimum} - d (i) |}{\frac{1}{2} D_{optimum}}) \\ + (1 - α) \frac{(E_{i} - E_{threshold})}{E_{max}} \end{matrix}$ (9)

We use priorities calculated by formula (9) for selection of CH. It is known that the suitable range of the value of $α$ is $α = 0.4 - 0.6$ . So we set $α = 0.5$ in the following experiments.

Next, Figure 5 shows the simulation results when data is aggregated to BS using the routing tree with timeslot allocation and without timeslot allocation. DEEOR denotes the routing algorithm without timeslot allocation and DEEOR-TA denotes the routing algorithm with timeslot allocation. In addition, DEEOR-TA uses CH role giving up operation mode.

Figure 5.

Various performance of the proposed protocol: (a) average of residual energy, (b) number of dead nodes, (c) variation of residual energy, (d) network lifetime, (e) variation of residual energy, and (f) number of dead nodes.

From the simulation results, if we introduce sleep mode we can prolong the network lifetime about three times compared with the case without sleep mode, where the distance between two neighboring nodes is 5 m. In the cases of extra distance between two neighboring nodes, the network lifetime can be prolonged more than twice.

Especially, Figure 5(e) and (f) illustrates that the variation of residual energy and the number of dead nodes decrease if CH role giving up operation mode is introduced so that we can balance energy consumption to prolong the network lifetime more.

Comparison with other protocols

We analyze our protocol compared with ENS_OR,⁷ ENS_OR with sleep mode⁸ and TE_OR.⁶ We conduct following experiment considering that ENS_OR or TE-OR is an OR algorithm only for relaying data but sleep mode is not introduced and interference is not considered.

Both ENS_OR with idle mode and ENS_OR with sleep mode are event triggering schemes. ENS_OR with sleep mode is also run as the same way with ENS_OR with idle mode in data gathering scheme that all nodes sense data in cycle during a timeslot allocated to itself like our proposed algorithm. So we expand ENS_OR (ENS_OR with sleep mode) and TE-OR into the cases with timeslot allocation and compare with our protocol. We set the interference-free communication range k = 3 under the consumption that nodes within the range D_optimum (approximately 32 m) and R (50 m) form a so-called cluster. Experiment results are illustrated in Figure 6. Figure 6(a) shows average residual energy of our protocol is much greater than that of ENS_OR and TE-OR and TE-OR has the worst. Figure 6(b) illustrates that variation of residual energy of the proposed protocol is greater than others in certain time (about 160 min) but as time goes, it gets much smaller so that energy consumption balance is ensured.

Figure 6.

Comparison of performance of various routing protocols: (a) average of residual energy, (b) variation of residual energy, (c) number of dead nodes, and (d) network lifetime.

This is because the number of CH nodes that consume much energy is small in the beginning of operation compared with the total number of nodes but after certain time, all nodes play the role of CH so variation of residual energy gets small. Especially, using CH role giving up operation mode makes this parameter smaller. And in ENS_OR and TE-OR, data are not aggregated and directly relayed by finding opportunistic relay distance. Thus, the energy consumption is balanced in certain time but it increases rapidly when nodes run out of energy. Figure 6(c) shows that ENS_OR and TE-OR are pure relay node selection algorithm without clustering and they can prolong the network lifetime before the certain time. After the certain time, the number of dead nodes increases rapidly. Especially, in TE-OR relay distance of each node is longer than of others so it has shorter latency but greater energy consumption. Thus, nodes are dead faster than ENS_OR. And in preceding two algorithms, nodes are dead at the same time since all nodes transmit data in opportunistic relay distance.

In total, Figure 6(d) shows that our protocol can significantly prolong the network lifetime compared with ENS_OR and TE-OR with rough timeslot allocation. In more detail, simulation results show that our protocol can help to prolong the network lifetime more than twice when the distance between two neighboring nodes is 5–20 m. And when the distance is 25 m, the network lifetime of our protocol is similar to that of ENS_OR because one node is just one cluster and only plays the role of relaying.

Conclusion

Optimization of energy consumption is one of the key problems in routing design in one-dimensional queue WSN. In this work, we have proposed a distributed energy-efficient opportunistic routing algorithm that routing tree construction and timeslot allocation are performed at the same time by using specific network topology of one-dimensional queue WSN. Existing opportunistic routing algorithms in one-dimensional queue WSN have been proposed as OR for ensuring energy efficiency and time limit regardless of introduction of timeslot allocation and interference between sensor nodes. Our main goal is to minimize the energy consumption derived from overhead of control messages as possible by performing timeslot allocation and routing tree construction simultaneously with the characteristic of linear network topology. For this purpose, we have given the definition of the routing tree construction and timeslot allocation problem using optimal relay transmission distance of OR in one-dimensional queue WSN and explained the detailed algorithm. We have optimized not only its energy consumption by introducing sleep mode that ensures data aggregation to BS without interference but also have improved its energy efficiency by adopting operation mode giving up CH role in clustering. Extension simulation results show that the proposed protocol supports better energy efficiency than the other existing protocols, so it can help to prolong the network lifetime.

Footnotes

Handling Editor: Lyudmila Mihaylova

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) received no financial support for the research,authorship,and/or publication of this article.

ORCID iD

Man Gun Ri

Data availability

The data used to support the findings of this study are available from the corresponding author upon request.

References

Heinzelman

Chandrakasan

Balakrishnan

. An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–700.

Jothiprakasam

Muthial

. A method to enhance lifetime in data aggregation for multi-hop wireless sensor networks. AEU: Int J Electron C 2018; 72(2): 183–191.

Sabet

Naji

. A decentralized energy efficient hierarchical cluster-based routing algorithm for wireless sensor networks. AEU: Int J Electron C 2015; 69(5): 790–797.

Darabkh

Al-Maaitah

Jafar

, et al. EA-CRP: a novel energy-aware clustering and routing protocol in wireless sensor networks. Comput Electr Eng 2018; 72(11): 702–718.

Darabkh

El-Yabroudi

El-Mousa

. BPA-CRP: a balanced power-aware clustering and routing protocol for wireless sensor networks. Ad Hoc Netw 2019; 82(1): 155–171.

Luo

Ruan

. Time-aware and energy-efficient opportunistic routing with residual energy collection in wireless sensor networks. Int J Commun Syst 2017; 30(10): 1–12.

Luo

, et al. Opportunistic routing algorithm for relay node selection in wireless sensor networks. IEEE T Ind Inform 2015; 11(1): 112–121.

Mhatre

Khot

. Energy efficient opportunistic routing with sleep scheduling in wireless sensor networks. Wireless Pers Commun 2020; 112(2): 1243–1263.

Mao

Tang

, et al. Energy efficient opportunistic routing in wireless sensor networks. IEEE T Parall Distr 2011; 22(11): 1934–1942.

10.

Zhang

Zheng

, et al. An energy-balanced routing method based on forward-aware factor for wireless sensor networks. IEEE T Ind Inform 2014; 10(1): 766–773.

11.

Liang

Zheng

, et al. Relay node placement in wireless sensor networks with respect to delay and reliability requirements. IEEE Syst J 2019; 13(3): 2570–2581.

12.

Huang

. Energy-aware geographic routing in wireless sensor networks with anchor nodes. Int J Commun Syst 2013; 26(1): 100–113.

13.

Jiang

. Relay node placement based on optimal transmission distance in two-tiered sensor network. IEEE Access 2020; 8(6): 110438–110445.

14.

Felemban

Lee

C-G

Ekici

. MMSPEED: multipath multi-speed protocol for QoS guarantee of reliability and timeliness in wireless sensor networks. IEEE T Mobile Comput 2006; 5(6): 738–754.

15.

Behnad

Nader-Esfahani

. On the statistics of MFR routing in one-dimensional ad hoc networks. IEEE T Veh Technol 2011; 60(7): 3276–3289.

16.

Cheng

Niu

Cao

, et al. QoS aware geographic opportunistic routing in wireless sensor networks. IEEE T Parall Distr 2014; 25(7): 1864–1875.

17.

Yahya

Ben-othman

. An energy efficient and QoS aware multipath routing protocol for wireless sensor networks. In: Proceedings of the 34th IEEE conference on local computer networks, Zurich, 20–23 October 2009, pp.93–100. New York: IEEE.

18.

Razzaque

Alam

Or-Rashid

, et al. Multi-constrained QoS geographic routing for heterogeneous traffic in sensor networks. In: Proceedings of IEEE consumer communications and network conference, Las Vegas, NV, 10–12 January 2008, pp.157–162. New York: IEEE.

19.

Liu

Zhang

Mouftah

, et al. Opportunistic routing for wireless Ad Hoc and sensor networks: present and future directions. IEEE Commun Mag 2009; 47(12): 103–109.

20.

Biswas

Morris

. Opportunistic routing in multi-hop wireless networks. In: Proceedings of ACM SIGCOMM, Philadelphia, PA, 22–26 August 2005, pp.133–144. New York: ACM.

21.

Chachulski

Jennings

Katti

, et al. Trading structure for randomness in wireless opportunistic routing. In: Proceedings of ACM SIGCOMM, Kyoto, Japan, 27–31 August 2007, pp.169–180. New York: ACM.

22.

Westphal

. Opportunistic routing in dynamic Ad Hoc networks: the OPRAH protocol. In: Proceedings of IEEE MASS, Vancouver, BC, Canada, 9–12 October 2006, pp.570–573. New York: IEEE.

23.

Yan

Zhang

Mouftah

, et al. Practical coding-aware opportunistic routing mechanism for wireless mesh networks. In: Proceedings of IEEE international conference on communications, Beijing, China, 19–23 May 2008, pp.2871–2876. New York: IEEE.

24.

Zhong

Wang

Nelakuditi

, et al. On selection of candidates for opportunistic any path forwarding. ACM SIGMOBILE Mobile Comp Commun Rev 2006; 10(4): 1–2.

25.

Wang

Gao

, et al. An asynchronous clustering and mobile data gathering schema based on timer mechanism in wireless sensor networks. CMC 2019; 58(2): 711–725.

26.

Wang

Gao

Liu

, et al. An intelligent data gathering schema with data fusion supported for mobile sink in wireless sensor networks. Int J Distrib Sens N 2019; 15(3): 1–9.

27.

Zorzi

Rao

. Geographic random forwarding (GeRaF) for Ad Hoc and sensor networks: multihop performance. IEEE T Mobile Comput 2003; 2(4): 337–348.

28.

X-Y

Liu

, et al. Energy-efficient timeslot allocation for data collection and aggregation. IEEE T Parall Distr 2010; 21(2): 275–286.

29.

Bhardwaj

Garnett

Chandrakasan

. Upper bounds on the lifetime of sensor networks. In: Proceedings of IEEE international conference of communication, Helsinki, 11–14 June 2001, pp.785–790. New York: IEEE.

30.

Min

Bhardwaj

Ickes

, et al. The hardware and the network: total-system strategies for power aware wireless microsensors. In: Proceedings of IEEE CAS workshop wireless communication network, Pasadena, CA, 5–6 September 2002, pp.36–42. New York: IEEE.

31.

Cohen

Kapchits

. An optimal timeslot allocation algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor network. IEEE T Netw 2009; 17(2): 570–581.

32.

F-J

Tseng

Y-C

. Distributed timeslot allocation for data collection in tree-based wireless sensor networks. IEEE Commun Lett 2009; 13(11): 850–852.

33.

Jain

Bhandare

. Min max normalization based data perturbation method for privacy protection. Int J Comput Commun Technol 2011; 2(8): 45–50.

A distributed energy-efficient opportunistic routing accompanied by timeslot allocation in wireless sensor networks

Abstract

Keywords

Introduction

Related works

System model and problem description

Network model

Energy model

Problem description

Definition 1

The proposed algorithm

Cluster-based routing tree construction and timeslot allocation

Clustering-based routing tree construction

First-level cluster

Lower level cluster

CH role giving up operation mode

Timeslot allocation

Timeslot allocation to the first-level cluster

Timeslot allocation to the lower level cluster

Data transmission

Protocol analysis

Theorem 1

Proof

Theorem 2

Proof

Theorem 3

Proof

Performance evaluation

Simulation environment

Performance metrics

Simulation results and analysis

Performance of DEEOR-TA

Comparison with other protocols

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

Data availability

References