Minimized Delay with Reliability Guaranteed by Using Variable Width Tiered Structure Routing in WSNs

Abstract

Data collection should take reliability and delay into consideration. To address these problems, a novel variable width tiered structure routing scheme named variable width tiered structure routing (VWTSR) is proposed. The proposed VWTSR scheme integrates two core phases, namely, circular tiers and cells partition, and distributed in-network aggregation. The key idea of VWTSR is to partition the network into circular tiers with different widths and each tier is further partitioned into cells. Those cells that do not interfere with each other could simultaneously finish data aggregation by broadcast and retransmission within each cell. Moreover, the tier width could meet the goal that when collecting nodes in outer layer finish transmission to parent collecting nodes in inner layer, the collecting nodes in inner layer just finish data aggregation, thus minimizing the latency while maintaining reliability for data collection. The problem is formulated as to minimize the delay under reliability constraint by controlling the system parameters. To demonstrate the effectiveness of the proposed scheme, extensive theoretical analysis and simulations are conducted to evaluate the performance of VWTSR. The analysis and simulations show that VWTSR leads to lower delay subject to reliability constraint than the existing scheme.

1. Introduction

Wireless sensor networks (WSNs) have been widely recognized as a ubiquitous and general approach for extensive applications in unattended environment, such as habitat monitoring, surveillance, and tracking for military. It consists of a large number of low-cost and low-power sensor nodes, which collaborate with each other to collect data and disseminate them to sink through an established routing path. Multihop communication is often used to relay the information from the source node to the sink. Distributed in-network aggregation can improve the communication efficiency of the system. It can result in significant performance improvements in energy consumption, memory usage, bandwidth, and delay [1].

Reliable communications are essential for most applications in wireless sensor networks (WSNs) [2–7]. Many applications require that each data packet is successfully delivered to sink with statistical probability $\delta <1$ , such as 60–95% [6, 8], which is sufficient for these applications such as environment (temperature, humidity) and agriculture (water tank, irrigation) [8]. In such cases, 100% reliable communications are costly and not necessary [5]. But some of the reports reveal that wireless link packet error rate may be as high as 30% in real WSNs which are far from being satisfactory [9].

In addition, delay is also an important metric in WSNs. It plays a vital role in the application to transport the detected information quickly to sink in order to make a rapid response to the event. Therefore, the delay is generally defined as the time required for sensor nodes to send the sensed data to sink, named transport delay [10]. In many safety-critical applications, the missing of urgent information may cause severe property loss and casualties, which are often not acceptable.

To address these issues, a novel routing scheme based on tiered structure routing is proposed in this paper. It integrates the consideration of data reliability and transport delay and is called VWTSR (variable width tiered structure routing). Compared with the previous study, we make the following contributions:

(1) A novel VWTSR scheme is proposed to achieve delay performance subject to reliability constraint. Since many applications have both reliability and delay constraints, the new network architecture is developed for in-network aggregation to improve the reliability and delay performance. The proposed scheme named VWTSR is targeting both optimization of reliability and network delay. The key idea of VWTSR is to partition the network into circular tiers with different widths and each tier is further partitioned into cells. Those cells that do not interfere with each other could simultaneously finish data aggregation by broadcast and retransmission within each cell. In each cell, noncollecting nodes transmit data packet to collecting nodes. When the packet is lost in the transmission, it will be retransmitted until the maximum number of retransmission. Moreover, the tier width could meet the goal that when collecting nodes in outer layer finish transmission to parent collecting nodes in inner layer, the collecting nodes in inner layer just finish data aggregation, thus minimizing the latency while maintaining reliability for data collection.

Compared with the existing data aggregation schemes, the proposed approach could maintain the network transmission success rate by broadcast and retransmission. Furthermore, it could reduce the delay of all nodes data aggregated to sink through distributed in-network data aggregation.

(2) It can effectively minimize aggregation latency in WSNs. It is very challenging to reduce delay in the precondition of ensuring reliability. In this paper, a routing approach named variable width tiered structure routing is proposed to obtain optimized network delay. In the approach, the careful design of tiers and cells partition of WSN is exploited to reduce network delay by using distributed in-network aggregation. In this way, the network delay could be optimized in the precondition of reliability guaranteed.

(3) The theoretical analysis on latency is offered. The theoretical analysis on transport delay is presented. Theoretical analysis is conducted by comparing the proposed VWTSR scheme with the existing tiered structure routing with identical width to show that VWTSR could effectively reduce network delay. In addition, comprehensive simulation experiments are conducted to verify the effectiveness of the VWTSR scheme. The results show that the proposed VWTSR could obtain the goal of optimization of transport delay subject to transmission reliability. The optimized parameters can be obtained to ensure the reduction of transport delay without reduction of the data reliability. In the simulation, the maximum transport delay could be decreased by 19.48% compared with identical width tiered structure routing approach, which presents the superiority of the strategy.

The rest of this paper is organized as follows. In Section 2, the related works are reviewed. The system model is described in Section 3. The novel VWTSR scheme is presented in Section 4 including performance analysis. Performance evaluations through simulations are presented in Section 5. We conclude in Section 6.

2. Related Work

Data collection is a key function for wireless sensor networks. Processing the gathered information efficiently is a key issue for wireless sensor networks. A great deal of work has been devoted to this field [11–14]. Reference [15] studies the time complexity, message complexity, and energy cost complexity of some data collection, data aggregation, and queries for a multihop wireless sensor network of n nodes. Network delay and reliable communication are important performance metrics and need to be considered in many WSNs studies.

Network delay has an important influence on WSNs applications. So there is a great deal of research in this field. Han and Lee conduct analysis on WSNs transport delay of NAK-based SR-ARQ [16]. There is also much research on SW E2E and SW H2H, for example, [17–21]. However, it is worth attention that most of the existing studies do research on simple linear network and analysis on network delay of the flat network which is widely applied in real environments is still relatively rare. And in most of the studies network life is hardly considered.

Moreover, recently, for flat network, Shanti and Sahoo [22] presented a new contention-free TDMA-based integrated MAC and routing protocol named DGRAM. Considering the unique phenomenon of data aggregation in WSNs, Huang et al. [23] proposed a centralized scheduling algorithm with the delay bound of $\mathrm{23}R+\Delta +18$ time slots, where R is the network radius and Δ is the maximum node degree. Yu et al. [24] proposed a distributed scheduling method generating collision-free schedules with delay at most $\mathrm{24}D+\mathrm{6}\Delta +16$ time slots, where D is the network diameter. Xu et al. [25] theoretically prove that the delay of the aggregation schedule generated by their algorithm is at most $\mathrm{16}R+\Delta -14$ time slots. Joo and Shroff develop a new network architecture for in-network computation for a class of generalized maximum functions [1]. It focuses on the delay performance of the function computation subject to reliability constraint in lossy wireless environments. It shows that aggregation with wireless broadcast can substantially reduce the delay while satisfying the reliability constraint.

A great deal of research efforts have been devoted in this field to providing a reliable transmission service in WSNs because of the unreliable links. Reference [4] points out that the existing works mainly fall into two categories: packet-loss avoidance and packet-loss recovery. Packet-loss avoidance (e.g., [8, 9]) attempted to reduce the occurrence of packet loss and packet-loss recovery (e.g., [26]) tried to recover the packet loss when it happened. Because packet-loss avoidance methods need to pay a high price and from the cost consideration the mechanism widely used in network is based on packet-loss recovery. While the reliable protocol based on packet-loss recovery can be divided into two categories. One way is the retransmission after packets loss scheme, whose representative protocol is Automatic Repeat reQuest (ARQ). Another way is the packets reproduction strategy.

Network lifetime is an important performance metric and needs to be considered in all WSNs studies. There is also a great deal of research in the field [27]. However, as far as we know, there is most of the research only on one performance metric of WSNs because of the network complexity and research difficulty, for example, reliability [6, 8] and network delay [20–25]. Some research integrates network delay and reliability, for example, [1, 4], or integrates network lifetime and delay, for example, [28]. The main focus of the paper is to consider delay performance of in-network aggregation under the reliability constraint.

3. The System Model and Problem Statement

3.1. The System Model

Consider a wireless sensor network consisting of sensor nodes that are uniformly and randomly scattered in a flat network with the radius of R, the area of W, and the node density of ρ. And nodes do not move after being deployed. On detecting an event, a sensor node will generate a message and forward to a special node, called the sink. The information generated at each sensor node is exact without error. The sensor nodes are divided into two types of collecting and noncollecting nodes. Each collecting sensor node not only generates its own data, but also aggregates and relays others' data to the sink via multihop wireless communications. And each noncollecting node only generates its own data and forwards it to the corresponding collecting nodes. Routing is fixed and time is slotted. All sensor nodes are assumed to be synchronized. Each node has an identical transmission range of r and multiple wireless channels. The wireless channel is assumed to be lossy with nonzero packet loss reliability p. A packet loss can be restored by retransmitting the lost packet, which, however, results in additional delay.

3.2. The Data Aggregation Model

For data aggregation, the lossless step-by-step multihop aggregation model is adopted. In such aggregation model, the aggregation of κ multiple inputs with node i is performed sequentially; that is, incoming data is aggregated with existing data in order of arrival. ${\wp }_i$ denotes the origin data packet of node i, and $\phi (i,j)$ denotes the intermediate aggregation result of node i and node j, or simply use ${\phi }_i$ to denote the current intermediate aggregation result of node i. ${\varphi }_i$ denotes the final aggregation result of node i to all incoming nodes' data and its own data.

When node i receives data ${\varphi }_j$ from node j, node i aggregates ${\varphi }_j$ with its own data (may be the origin data ${\wp }_i$ or the intermediate data ${\phi }_i$ ). If current data packet of node i is ${\wp }_i$ , and data from j is ${\varphi }_j={\wp }_j$ ; namely, the data to be aggregated is both origin data; then the aggregation formula is the following:

$$\begin{array}{cc}& \phi \left(i,j\right)=c\max \left({\wp }_i,{\wp }_j\right)+\left(\mathrm{1}-c\right)\min \left({\wp }_i,{\wp }_j\right).\end{array}$$

(1)

In formula (1), c is the correlation coefficient and it is between 0 and 1. If any part of data to be aggregated is not source data when being aggregated, the aggregation formula is the following:

$$\begin{array}{cc}& \phi \left({\phi }_i,{\varphi }_j\right)=\varsigma \max \left({\phi }_i,{\varphi }_j\right)+\left(\mathrm{1}-\varsigma \right)\min \left({\phi }_i,{\varphi }_j\right).\end{array}$$

(2)

In formula (2), ς is called an impact factor which is a decimal less than 1, for example, $\varsigma =0.8$ ; ${\phi }_i$ and ${\varphi }_j$ , respectively, refer to intermediate aggregation result and final result of child nodes; there is at least one nonorigin data packet in ${\phi }_i$ and ${\phi }_j$ .

3.3. Problem Statement

In this part, some definitions are given firstly to ensure clear statement. They are as follows.

Definition 1 (transport delay).

One defines the transport delay as the time from a packet's first transmission until its final transmission to the sink [10]. Let ${\Gamma }_i$ denote the transport delay from node i to sink.

Definition 2 (network reliability).

It represents the probability of packets successfully forwarded to sink from one node. Let ${\delta }_i$ denote the network reliability of packets transmitted from node i to sink.

Definition 3 (network delay).

One defines the network delay as the time required for each node in the network to finish its single transmission to the sink. Let D denote the network delay.

The information obtained by an individual sensor node called noncollecting node is collected by some special nodes called colleting nodes, and these collecting nodes are responsible for data aggregation and information delivery to the sink. Each collecting node at depth d or tier d has at least $x(n)$ collecting parents at depth or tier $d-1$ and transmits a packet through the wireless broadcast channel to all parents ( $1+{\mu }_t$ ) times, where ${\mu }_t$ denotes the retransmission times. We say that a node successfully transmits a packet if the broadcast packet is successfully received by one of the $x(n)$ parents. And in the meantime, we try to minimize network delay.

Following the network model in [17], assume that the transmission reliability of node i is $p_i$ and assume that there are h hops from the source node i to the sink. Let $P_i$ denote the routing path from node i to the sink, where $P_i=\{v_{\mathrm{0}}^i,v_{\mathrm{1}}^i,\dots ,v_h^i\}$ and $v_h^i$ denotes the node whose distance to the sink is h hops in the routing path of node i. The transmission reliability and the delay at each hop are denoted by $p_i^T=[p_0,p_1,\dots ,p_h]$ and ${\tau }_i^T=[{\tau }_0,{\tau }_1,\dots ,{\tau }_h]$ , respectively. Therefore, the network reliability and transport delay of packet transmitted to sink from node i are, respectively, ${\delta }_i=\left[{\prod }_{k=\mathrm{0}}^{h_{\mathrm{1}}}[\mathrm{1}-(\mathrm{1}-p_{k+\mathrm{1}}{)}^{x(n)(\mathrm{1}+{\mu }_t)}]·[\mathrm{1}-(\mathrm{1}-p_k{)}^{(\mathrm{1}+{\mu }_t)}]\right]$ and ${\Gamma }_i={\sum }_{k=\mathrm{0}}^h{\tau }_k$ . And for the distributed in-network aggregation we have the equation $D=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\Gamma }_i\right\}$ ( $i=\mathrm{1,2},\mathrm{3},\dots$ ). The focus of the paper is to improve the delay performance while achieving the same level of reliability. That is, ${\delta }_i\ge \delta$ , where δ represents the network transmission success rate constraint. To sum up the above, the network optimization goal can be expressed as the following; that is, as for any node i in the network it meets the following formula:

$$\begin{array}{cc}& \mathrm{m}\mathrm{i}\mathrm{n}\hspace{1em}\left(D\right)=\min \underset{\mathrm{0}<i\le n}{\max }\left({\Gamma }_i\right)\\ \text{<!--?brm?-->s.t.<!--?erm?-->}\hspace{1em}{\Gamma }_i={{\displaystyle \sum }}_{k=\mathrm{0}}^h{\tau }_k\\ \hspace{1em}{\delta }_i\ge \delta .\end{array}$$

(3)

Hence, the optimization goal is minimizing the maximum transport delay under the guarantee of transport service quality; for example, ${\delta }_i\ge \delta$ .

4. Design of the VWTSR Scheme

The proposed VWTSR scheme consists of two phases: (1) circular tiers and cells partition and (2) in-network aggregation and multiroute simultaneously. As an illustration of the methods, these phases will be presented in the following two sections. At the end of the section, a theoretical analysis on delay performance will be demonstrated.

4.1. The Overall Approach

In this section, the overall approach is described. An example is illustrated in Figure 1. It consists of two phases: (1) each noncollecting node transmits its packet to its parent collecting node in the same cell and (2) each collecting node receives the packet and does aggregation. And it transmits the aggregated packet to its parent collecting nodes in inner tier. The procedure is repeated tier by tier from the outermost tier.

Figure 1

The overall approach: the black nodes are collecting nodes and white nodes are noncollecting nodes. (a) Phase I, (b) Phase II.

4.2. VWTSR Scheme

In the scheme, the network is partitioned into circular tiers with different widths and each tier is further partitioned into cells. Those cells that do not interfere with each other could simultaneously finish data aggregation by broadcast and retransmission within each cell. In each cell, noncollecting nodes transmit data packet to collecting nodes. When the packet is lost in the transmission, it will be retransmitted until the maximum number of retransmissions. Moreover, the tier width could meet the goal that when collecting nodes in outer layer finish transmission to parent collecting nodes in inner layer, the collecting nodes in inner layer just finish data aggregation, thus minimizing the latency while maintaining reliability for data collection. All the data will be gradually aggregated to sink by the distributed in-network aggregation.

As the above description, the proposed VWTSR consists of two phases. In the part, more details will be given on the implementation.

( 1) Circular Tiers and Cells Partition. For a flat circle network as described in Section 3.1, assume that the sink is located at the center and nodes' interference radius is $2r$ . The circular tiers and cells partition are shown in Figure 2. The width of each tier is firstly computed according to the constraint that the collecting nodes in inner layer just finish data aggregation when collecting nodes in outer layer finish transmission to parent collecting nodes in the inner layer. Accordingly, the network is divided into circular tiers $\left\{T_k\right\}$ .

Figure 2

Illustration of tiers and cells partition.

Assume that the width of the outmost tier $T_k$ is $\delta r$ , where $\mathrm{0}<\delta <\mathrm{1}$ . It is partitioned into cells $\left\{C_k^m\right\}$ and each cell has a width of r at the boundary of the inner tier as shown in Figure 2. There are $\mathrm{n}\mathrm{u}{\mathrm{m}}_{\mathrm{s}\mathrm{e}\mathrm{t}}=\mathrm{2}\pi ·(R-\delta r)/r$ cells (actually, it is an integer no smaller than $\mathrm{n}\mathrm{u}{\mathrm{m}}_{\mathrm{s}\mathrm{e}\mathrm{t}}$ ).

For a cell in the outmost tier $T_k$ , the circular angle (in radian) is $\theta =r/(R-\delta r)$ . So we can get the area of each cell $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}=\theta ·R·R/\mathrm{2}-\theta ·\left(R-\delta r\right)·\left(R-\delta r\right)/\mathrm{2}=(\theta /\mathrm{2})(\mathrm{2}R\delta r-{\delta }^{\mathrm{2}}{r}^{\mathrm{2}})$ . Finally, a simplified formula $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}=\delta r^{\mathrm{2}}(\mathrm{2}R-\delta r)/\mathrm{2}(R-\delta r)$ can be obtained. Therefore, the number of nodes in each cell is ${\xi }_k=\rho ·s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}$ , where ρ denotes the node density. Accordingly, we can get the time required for collecting nodes in the outmost tier to finish data aggregation of the tier. It is ${\tau }_{k\_n}=\mathrm{3}{\xi }_k(\mathrm{1}+\mu )$ with the assumption that there is only one collecting node within each cell and the maximum retransmission times are μ. The collecting nodes need to deliver the aggregated information to the collecting nodes in inner layer and the time for forwarding is ${\tau }_{k\_g}=\mathrm{3}(\mathrm{1}+\mu )$ . So the total time required for all nodes in the outmost tier to finish transmission to inner layer is computed by the following formula:

$$\begin{array}{cc}& {\tau }_k={\tau }_{k\_n}+{\tau }_{k\_g}=\mathrm{3}{\xi }_k\left(\mathrm{1}+\mu \right)+\mathrm{3}\left(\mathrm{1}+\mu \right).\end{array}$$

(4)

For inner tier $T_{k-\mathrm{1}}$ , the similar calculations can be done. So the following results can be obtained. The number of cells partitioned in the tier $T_{k-\mathrm{1}}$ is

$$\begin{array}{cc}& \mathrm{n}\mathrm{u}{\mathrm{m}}_{k-\mathrm{1}}=\frac{\mathrm{2}\pi ·\left(R-{\delta }_{k}r-{\delta }_{k-\mathrm{1}}r\right)}{r}.\end{array}$$

(5)

The area of each cell is calculated by

$$\begin{array}{cc}& s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k-\mathrm{1}}=\frac{\theta ·\left(R-{\delta }_{k}r\right)·\left(R-{\delta }_{k}r\right)}{\mathrm{2}}-\frac{\theta ·\left(R-{\delta }_{k}r-{\delta }_{k-\mathrm{1}}r\right)·\left(R-{\delta }_{k}r-{\delta }_{k-\mathrm{1}}r\right)}{\mathrm{2}}=\frac{\theta }{\mathrm{2}}\left\{R^{\mathrm{2}}+{{\delta }^{\mathrm{2}}}_k{r}^{\mathrm{2}}-\mathrm{2}{\delta }_{k}r-\left[R^{\mathrm{2}}+{\left({\delta }_{k}r+{\delta }_{k-\mathrm{1}}r\right)}^{\mathrm{2}}-\mathrm{2}R\left({\delta }_{k}r+{\delta }_{k-\mathrm{1}}r\right)\right]\right\}=\frac{\theta }{\mathrm{2}}\left\{-\mathrm{2}{\delta }_{k}r-\left[\left(\mathrm{2}{\delta }_k{\delta }_{k-\mathrm{1}}{r}^{\mathrm{2}}+{{\delta }^{\mathrm{2}}}_{k-\mathrm{1}}{r}^{\mathrm{2}}\right)-\mathrm{2}R\left({\delta }_{k}r+{\delta }_{k-\mathrm{1}}r\right)\right]\right\}.\end{array}$$

(6)

So we can get that the number of nodes in each cell is ${\xi }_{k-\mathrm{1}}=\rho ·s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k-\mathrm{1}}$ and the time required for collecting nodes in the tier to finish data aggregation is ${\tau }_{k-\mathrm{1}\_n}=3{\xi }_{k-\mathrm{1}}(\mathrm{1}+\mu )$ . Considering the constraint that the tier width could meet the goal that when collecting nodes in outer layer finish transmission to parent collecting nodes in inner layer and the collecting nodes in inner layer just finish data aggregation, we have the equation ${\tau }_{k-\mathrm{1}\_n}={\tau }_k$ . It is ${\xi }_{k-\mathrm{1}}={\xi }_k+\mathrm{1}$ after simplification. Therefore, the tier width can be obtained. If the procedure is repeated, we can obtain the width of each tier.

( 2) Distributed In-Network Aggregation. The information obtained by an individual sensor node is collected by some special colleting nodes, and these collecting nodes are responsible for data aggregation and information delivery to the sink.

Let $H(k,m)$ be the subset of nodes in $T_k$ that are scheduled simultaneously, and $\left|·\right|$ denotes the cardinality of the set. Let $H(k,m)$ include a node from every three cells; that is, $H(k,m)$ has a node from cells $C_k^m,C_k^{m+\mathrm{3}},\dots$ Since any two nodes in $H(k,m)$ are separated more than $2r$ , their transmissions do not interfere with each other. Moreover, since all cells have the same number of nodes (possibly except one cell, which may have a smaller number of nodes), the number of nodes in each $H(k,m)$ is identical and would be about a third of the number of cells. Moreover, since all cells have the same number of nodes, the number of nodes in each $H(k,m)$ is identical and would be about a third of the number of $C_k^m$ :

$$\begin{array}{cc}& \left|H\left(k,m\right)\right|=⌊\frac{\mathrm{1}}{\mathrm{3}}⌈\frac{\mathrm{2}\pi \left(R-\delta r\right)}{r}⌉⌋.\end{array}$$

(7)

Since each node has multiple wireless channels as described in Section 3.1, the subset of nodes $H(k,m)$ in $T_k$ could transmit data simultaneously with subsets in other tiers. Thus we could ensure node transmission simultaneously as much as possible. When collecting nodes in outer layer finish transmission to parent collecting nodes in inner layer and the collecting nodes in inner layer just finish data aggregation, the colleting nodes in inner layer go on forwarding the aggregated information together to their parent collecting nodes in more inner layer until the destination of sink.

The VWTSR protocol is implemented as shown in Algorithm 1 in detail.

Algorithm 1: A variable width tiered structure routing algorithm for WSNs.

Input: A flat network with the radius of R, the node density of ρ, transmission range of r and nonzero packet loss reliability p,

   retransmission times ${\mathrm{\mu }}_t$ .

Output: Data aggregation route

 Stage 1: Circular tiers and cells partition

   (1) According to formula (3) the network is partitioned into tiers $\left\{T_k\right\}$ , ( $k=\mathrm{1,2},\mathrm{3},\dots ,d$ ) with different width;

   (2) for each tier $T_k$

     Tier $T_k$ is partitioned into cells $\left\{C_k^m\right\}$ according to width r at the boundary of the inner tier;

     Select a node from cells $C_k^m,C_k^{m+\mathrm{3}},\dots$ , so on to construct $H(k,m)$ , that is ${\bigcup }_{m=\mathrm{1}}^{{\mathrm{ħ}}_k}H(k,m)=T_k$ ;

     end

 Stage 2: Distributed in-network aggregation

   (3) for   $k=d$   to 1

      for   $m=1$ to ${\mathrm{ħ}}_k$

       each non-collecting node i in $H(k,m)$ broadcasts its original or aggregated information ( $1+{\mathrm{\mu }}_t$ ) times to

       its collecting node ƛ in the same cell.

       if collecting node ƛ receives all the packet from non-collecting nodes in the same cell, then

        node ${\mathrm{ƛ}}_i$ does aggregation and broadcasts the information ( $1+{\mathrm{\mu }}_t$ ) times to its parent collecting nodes in

        inner tier.

       end if

      end for

     end for

   (4) Output results;

4.3. Performance Analysis

In this section, the delay of the data aggregation based on the proposed scheme is theoretically proved.

Theorem 4.

Consider that the network depth is d, let ${ħ}_d$ denote the total number of subsets in tier $T_d$ , and assume that the maximum number of retransmissions is μ. The time required for all nodes to finish a single transmission is $D={ħ}_d(\mathrm{1}+\mu )+{\sum }_{i=\mathrm{1}}^{d-\mathrm{1}}(\mathrm{1}+\mu )$ .

Proof.

Consider that the network depth is d, which represents the number of tiers. From Section 4.2, we know that $H(k,m)$ is the subset of nodes in $T_k$ that can be scheduled simultaneously. Let ${ħ}_k$ denote the total number of subsets in each tier $T_k$ such that ${\bigcup }_{m=\mathrm{1}}^{{ħ}_k}H(k,m)=T_k$ . Clearly, all nodes in $T_k$ can finish a single transmission in ${ħ}_k$ time slots. Based on the assumption that nodes transmission in different tiers do not interfere with each other, the subset of nodes $H(k,m)$ in different tiers could transmit data simultaneously. That is, nodes in $T_k$ can start their transmissions simultaneously with nodes in $T_{k+\mathrm{1}}$ . But the number of nodes in $T_k$ is more than that in $T_{k+\mathrm{1}}$ . Assume that the maximum number of retransmission is μ. Therefore, we can obtain the time required for all nodes to finish a single transmission as follows:

$$\begin{array}{cc}& D={ħ}_d\left(\mathrm{1}+\mu \right)+{{\displaystyle \sum }}_{i=\mathrm{1}}^{d-\mathrm{1}}\left(\mathrm{1}+\mu \right).\end{array}$$

(8)

Theorem 5.

Let D and $D^{\prime }$ , respectively, represent the time required for all nodes to finish a single transmission under the cases of network partition with the VWTSR scheme and the identical width. That is, $D^{\prime }-D>0$ .

Proof.

It is needed to estimate ${ħ}_d$ to obtain D. Obviously, the circular angle of each cell in the outmost layer is $\theta =r/(R-\delta r)$ and the area is $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}=\theta ·R·R/\mathrm{2}-\theta ·\left(R-\delta r\right)·\left(R-\delta r\right)/\mathrm{2}=(\theta /\mathrm{2})(\mathrm{2}R\delta r-{\delta }^{\mathrm{2}}{r}^{\mathrm{2}})$ . We can obtain after simplification

$$\begin{array}{cc}& s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}=\frac{\delta r^{\mathrm{2}}\left(\mathrm{2}R-\delta r\right)}{\mathrm{2}\left(R-\delta r\right)}.\end{array}$$

(9)

So ${ħ}_d=3\rho ·s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}$ and the time required for collecting nodes to finish data aggregation within each cell is $\mathrm{3}\rho ·s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}(\mathrm{1}+\mu )$ . The collecting nodes go on forwarding the aggregated data packets and the required time is ${\tau }_{k\_g}=3(\mathrm{1}+\mu )$ . So we get $D=\mathrm{3}\rho ·s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}(\mathrm{1}+\mu )+{\sum }_{i=\mathrm{1}}^{d-\mathrm{1}}(\mathrm{1}+\mu )$ . $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}$ is substituted by formula (9). Then the following formula can be obtained:

$$\begin{array}{cc}& D=\mathrm{3}\rho ·\frac{r\left(\mathrm{2}R\delta r-{\delta }^{\mathrm{2}}{r}^{\mathrm{2}}\right)}{\mathrm{2}\left(R-\delta r\right)}\left(\mathrm{1}+\mu \right)+{{\displaystyle \sum }}_{i=\mathrm{1}}^{d-\mathrm{1}}\left(\mathrm{1}+\mu \right).\end{array}$$

(10)

If the network depth is d and the partitioned tiers have the identical width of γ, that is, $R=\gamma d$ , so we have $\gamma =R/d$ . Let $D^{\prime }$ denote the time required for all nodes to finish a single transmission. Similarly, $D^{\prime }$ is calculated by the following formula:

$$\begin{array}{cc}& D^{\prime }={ħ}_d^{\prime }\left(\mathrm{1}+\mu \right)+{{\displaystyle \sum }}_{i=\mathrm{1}}^{d-\mathrm{1}}\left(\mathrm{1}+\mu \right).\end{array}$$

(11)

For the case of identical width circular partition, according to the previous calculation method, the area of each cell can be computed by $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}^{\prime }={\theta }^{\prime }·R·R/\mathrm{2}-\theta ·\left(R-\gamma \right)·\left(R-\gamma \right)/\mathrm{2}=({\theta }^{\prime }/\mathrm{2})(\mathrm{2}R\gamma -{\gamma }^{\mathrm{2}})$ . Substitute the circular angle ${\theta }^{\prime }=r/(R-\gamma )$ into $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}^{\prime }$ and $s_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}\_k}^{\prime }=r(\mathrm{2}R\gamma -{\gamma }^{\mathrm{2}})/\mathrm{2}(R-\gamma )$ can be obtained. Consequently, $D^{\prime }$ has

$$\begin{array}{cc}& D^{\prime }=\mathrm{3}\rho \frac{r\left(\mathrm{2}R\gamma -{\gamma }^{\mathrm{2}}\right)}{\mathrm{2}\left(R-\gamma \right)}\left(\mathrm{1}+\mu \right)+{{\displaystyle \sum }}_{i=\mathrm{1}}^{d-\mathrm{1}}\left(\mathrm{1}+\mu \right).\end{array}$$

(12)

Since $\gamma >\delta r$ , $D^{\prime }$ is compared with D and it has the following result:

$$\begin{array}{cc}& D^{\prime }-D=\mathrm{3}\rho r\left[\frac{\left(\mathrm{2}R\gamma -{\gamma }^{\mathrm{2}}\right)}{\mathrm{2}\left(R-\gamma \right)}-\frac{\left(\mathrm{2}R\delta r-{\delta }^{\mathrm{2}}{r}^{\mathrm{2}}\right)}{\mathrm{2}\left(R-\delta r\right)}\right]=\frac{\left(R-\delta r\right)\left[\mathrm{2}R\gamma -{\gamma }^{\mathrm{2}}\right]-\left(R-\gamma \right)\left[\mathrm{2}R\delta r-{\delta }^{\mathrm{2}}{r}^{\mathrm{2}}\right]}{\mathrm{2}\left(R-\gamma \right)\left(R-\delta r\right)}.\end{array}$$

(13)

It can be obtained after further simplification:

$$\begin{array}{cc}& D^{\prime }-D=\frac{\left(\gamma -\delta r\right)\left[\mathrm{2}{R}^{\mathrm{2}}+\gamma \delta r-R\left(\gamma +\delta r\right)\right]}{\mathrm{2}\left(R-\gamma \right)\left(R-\delta r\right)}\ge \frac{\left(\gamma -\delta r\right)\left[\mathrm{2}{R}^{\mathrm{2}}+\gamma \delta r-R^{\mathrm{2}}\right]}{\mathrm{2}\left(R-\gamma \right)\left(R-\delta r\right)}=\frac{\left(\gamma -\delta r\right)\left[R^{\mathrm{2}}+\gamma \delta r\right]}{\mathrm{2}\left(R-\gamma \right)\left(R-\delta r\right)}.\end{array}$$

(14)

Since $(\gamma -\delta r)\left[R^{\mathrm{2}}+\gamma \delta r\right]/\mathrm{2}(R-\gamma )(R-\delta r)>0$ , we get $D^{\prime }-D>0$ . This proves that there is lower delay for circular partition with different widths than that with identical width.

5. Simulation

In this section, the simulation results are presented to evaluate the VWTSR scheme. The simulation environment is firstly introduced, focusing more on the network model applied in simulation experiments. Then we present the evaluation results for the proposed routing scheme. Finally, some comparisons with existing routing mechanism are presented.

5.1. Simulation Parameter Setting

The test beds are, respectively, two wireless sensor networks with 600 nodes and 900 nodes randomly placed in a disk of radius $R=1$ . The transmission range of each node r is set to 0.5. The retransmission number μ is changed from 1 to 4. All links are assumed to fail transmission with the same probability p. Changing p, the number of time units required for the sink to receive the information value is counted and the rate of packet lost is measured. Each simulation is run 1000 times and the results are averaged.

5.2. Evaluation on the Proposed Scheme

The proposed scheme is evaluated firstly. Here, the performance evaluation mainly focuses on two metrics: the reliability and network delay. We investigate the performance of VWTSR through simulations. When $\delta =0.5$ , according to Algorithm 1, the network is divided into three circular tiers, whose widths are, respectively, 0.25, 0.2749, and 0.4751 from outer tier to inner tier. The network circular partitions for network with 600 nodes and 900 nodes are as shown in Figures 3 and 4, respectively. Tables 1 and 2, respectively, show the number of packets lost and network delay under different p and μ for networks with 600 nodes and with 900 nodes.

Table 1

The number of packets lost and network delay under different p and μ for network with 600 nodes.

Number of packets lost/delay	p
μ	$$p=\mathrm{0.4}$$	$$p=\mathrm{0.5}$$	$$p=\mathrm{0.6}$$	$$p=\mathrm{0.7}$$	$$p=\mathrm{0.8}$$
$$\mu =\mathrm{1}$$	190/258	143/240	92/219	42/201	17/180
$$\mu =\mathrm{2}$$	112/324	68/276	29/240	11/210	2/186
$$\mu =\mathrm{4}$$	38/327	14/321	5/252	0/219	0/183

Table 2

The number of packets lost and network delay under different p and μ for network with 900 nodes.

Number of packets lost/delay	p
μ	$$p=\mathrm{0.4}$$	$$p=\mathrm{0.5}$$	$$p=\mathrm{0.6}$$	$$p=\mathrm{0.7}$$	$$p=\mathrm{0.8}$$
$$\mu =1$$	295/303	217/288	134/273	71/249	28/234
$$\mu =2$$	162/378	111/348	56/312	17/267	7/240
$$\mu =4$$	76/456	20/381	11/330	5/273	4/234

Figure 3

Network circular partition with 600 nodes.

Figure 4

Network circular partition with 900 nodes.

Figures 5(a) and 5(b), respectively, show the reliability and delay under different p and μ for the network with 600 nodes. As shown in Figure 5, there is more number of packets lost when p is smaller and otherwise there are less packets lost. Since the packet will be retransmitted if it is lost in the journey, there is higher delay when μ is bigger, which means that the number of packets lost is reduced under the same p (as can be seen from Figure 5(a)).

Figure 5

Comparisons under different p and μ for the network with 600 nodes: (a) the number of packets lost, (b) network delay.

Figures 6(a) and 6(b), respectively, illustrate the relations of the reliability and delay with parameters of p and μ for the network with 900 nodes. As can be seen from Figure 6, there are more packets lost when p is smaller and there are less packets lost when p is bigger. Under the same p, the packet loss is reduced and the network delay is higher when μ is bigger.

Figure 6

Comparisons under different p and μ for the network with 600 nodes: (a) the number of packets lost, (b) network delay.

5.3. Comparisons with Existing Scheme

In this part, we compare the proposed VWTSR routing with existing scheme through the above-mentioned networks, focusing on delay and reliability performance. In order to prove the effectiveness of the scheme, it is compared with the tiered structure routing with the identical tier width named IWTSR in [1] and that with general varied width named GVWTSR. In GVWTSR, the width and network partition are not carefully designed, and it is a general form based on IWTSR. For the case of network circular partition with identical width, the circular width is 0.3333 in order to ensure that there is the same number of circular rings with VWTSR described in Section 5.2. Accordingly, for the GVWTSR, the circular widths are randomly set and they are 0.20, 0.35, and 0.45 from outer layer to inner layer. The network partitions of IWTSR and GVWTSR are, respectively, shown in Figures 7(a) and 7(b).

Figure 7

Network partition (a) with identical circular width of 0.3333 and (b) with circular width of 0.20, 0.35, and 0.45.

The comparisons of the number of packet lost and network delay under different p and μ for the network with 600 nodes are shown in Table 3. Figures 8 and 9, respectively, show the corresponding comparisons on the metrics of the number of packets lost and network delay by exploiting the different schemes of VWTSR, IWTSR, and GVWTSR. As shown in Figure 8, when $\mu =2$ , the proposed VWTSR is superior both in reliability and in delay. In the case, when $p=0.8$ the network delay is reduced by 19.48% and the number of packets lost is reduced by 5 compared with IWTSR. And when $\mu =4$ , the proposed VWTSR has significant advantage over IWTSR and GVWTSR in the network delay, which can be seen from Figure 9(a). And the transmission success rate is maintained as shown in Figure 9(b).

Table 3

Comparisons of the number of packets lost and network delay under different p and μ for the network with 600 nodes exploiting schemes of VWTSR, IWTSR, and GVWTSR.

Number of packets lost/delay	$$\mu =2$$			$$\mu =4$$
Schemes	$$p=\mathrm{0.4}$$	$$p=\mathrm{0.6}$$	$$p=\mathrm{0.8}$$	$$p=\mathrm{0.4}$$	$$p=\mathrm{0.6}$$	$$p=\mathrm{0.8}$$
VWTSR	112/324	29/240	2/186	38/327	5/252	0/183
IWTSR	116/420	39/315	7/231	32/456	9/297	3/246
GVWTSR	112/333	39/261	4/204	40/381	7/264	3/207

Figure 8

Comparisons of VWTSR, GVWTSR, and IWTSR for network with 600 nodes and $\mu =2$ . (a) Network delay, (b) success rate.

Figure 9

Comparisons of VWTSR, GVWTSR, and IWTSR for network with 600 nodes and $\mu =4$ . (a) Network delay, (b) success rate.

Figure 10 illustrates the network partition in the two cases of the identical circular width of 0.3333 and different circular width of 0.20, 0.35, and 0.45 for the network with 900 nodes. The comparisons of the number of packet lost and network delay under different p and μ are shown in Table 4. Figures 11 and 12, respectively, show the corresponding comparisons on the metrics of the number of packet lost and network delay by exploiting the different schemes of VWTSR, IWTSR, and GVWTSR. As shown in Figure 11, when $\mu =2$ , the proposed VWTSR is superior both in reliability and in delay than the other two schemes. For instance, when $p=0.8$ , the network delay is reduced by 19.19% compared with IWTSR. And, when $\mu =4$ , the proposed VWTSR has obvious advantage over IWTSR and GVWTSR in the network delay, which can be seen from Figure 12(a). And the transmission success rate is satisfied as shown in Figures 11(b) and 12(b).

Table 4

Comparisons of the number of packet lost under different p and μ for the network with 900 nodes.

Number of packets lost/delay	$$\mu =2$$			$$\mu =4$$
Schemes	$$p=\mathrm{0.4}$$	$$p=\mathrm{0.6}$$	$$p=\mathrm{0.8}$$	$$p=\mathrm{0.4}$$	$$p=\mathrm{0.6}$$	$$p=\mathrm{0.8}$$
VWTSR	162/378	56/312	7/240	76/456	11/330	4/234
IWTSR	175/480	54/357	11/297	64/573	15/366	2/282
GVWTSR	169/462	62/396	5/294	59/630	9/435	1/309

Figure 10

Network partition (a) with identical circular width of 0.3333 and (b) with circular width of 0.20, 0.35, and 0.45.

Figure 11

Comparisons of VWTSR, GVWTSR, and IWTSR for network with 900 nodes and $\mu =2$ . (a) Network delay, (b) success rate.

Figure 12

Comparisons of VWTSR, GVWTSR, and IWTSR for network with 900 nodes and $\mu =4$ . (a) Network delay, (b) success rate.

6. Conclusion

In this paper, the problem of distributed in-network aggregation to reduce delay in WSNs is studied. Data aggregation should take reliability as well as delay into consideration. To address these problems, a novel routing scheme named VWTSR is proposed. The improved VWTSR consists of two phases. The theoretical analysis and simulation results show that the method outperforms the existing methods. Carefully designed system parameters grant VWTSR lower transport delay under given reliability. In our simulation, it can be seen that the network delay could be reduced by 19.48% under the guarantee of reliability.

There are many interesting open questions to consider. Although we focus on the delay performance, other performance metrics such as time complexity and the communication overhead of the routing protocol are also of importance. It would be interesting to study the relationship between these metrics with data aggregation and network topologies.