A Fast and Reliable Hybrid Data Delivery Protocol for Large-Scale Heterogeneous Sensor Networks

Abstract

We propose a hybrid data delivery method for the large-scale heterogeneous sensor networks, which is a fast and reliable delivery protocol for the aggregated data from the sinks to the GW. We develop a new multicriteria-ranking algorithm which determines multiple forwarders for each hop by ranking neighbor nodes. To rank the nodes, we compute the fitness value using features for each node such as the received signal strength, nodal delay, and hop distance. We determine the time of sending among forwarders using the waiting time assignment algorithm. In the experimental section, we show that our method outperforms conventional data delivery protocols in terms of data delivery ratio and end-to-end delay.

1. Introduction

Wireless sensor networks (WSNs) are multihop wireless networks which main purpose is to deliver sensed data collected from multiple sensors to one or more data-collecting devices (or sinks). Its inherent power limitation [1], wireless connectivity and vast number of applications have been attracting much attention from a good number of researchers in the recent years [2, 3]. WSNs are used in acquiring information from inaccessible or perilous areas. Sensed data collected at a sensor are delivered to a remote monitoring center through an intermediate system.

Large-scale heterogeneous sensor network, one type of WSN, has a number of heterogeneous wireless nodes deployed over a wide geographical region. The WSN is commonly made up of two subnetworks: a sensor network and a distribution network. Sensors in the sensor network collect or sense data and deliver them to the nearest sink. In general, sensors are static and densely deployed so they can be easily connected to a sink. The distribution network on the other hand is responsible for delivering data gathered from sinks to the remote monitoring center through a gateway (GW). The GW in turn is connected to an external network like the Internet where the remote monitoring center gets the data. Issues on the deployment of nodes and data collection in the sensor network have already been well addressed in a number of literatures [4– 7]. In general, data delivery from sensors to the nearest sink is assumed to be loss tolerant due to the sheer amount of correlated data [8]. However, the aggregated data in the distribution network are not. Furthermore, the significant distance between the monitoring center and the GW is also a challenge. But since they are connected through a high-speed wired network, we focus on the data delivery between the sinks and the GW. In addition, it is desirable for the protocol to be relatively fast because a remote monitoring center may need to take appropriate actions based on the information provided by the distribution network.

Hence in this paper, we develop a fast and reliable delivery protocol for the aggregated data from the sinks to the GW. We obtain good data delivery ratio and end-to-end delay by solving the drawbacks of conventional protocols. We also present a new multicriteria ranking paradigm and present a waiting time assignment algorithm. In the experimental section, we show that our protocol outperforms conventional flooding and relaying techniques.

This paper is organized as follows. Section 2 presents the drawbacks of related works. In Section 3, we describe in detail our proposed protocol followed by the analysis of experimental results in Section 4. We conclude in Section 5.

2. Related Works

In general, wireless data delivery protocols can be divided into two major categories, (1) relaying and (2) flooding approaches [9]. Relay methods send messages once to a single forwarder. Usually, these methods make use of a multi-criteria fitness function to determine the link cost of its neighbors [10, 11]. Such criteria are usually extracted through a network discovery process commonly done by sending control messages. The more the number of control messages sent, the better the decision process of choosing the next forwarder reflects the state of the network. However, too many of these messages might cause data delivery ratio to fall due to increase in the probability of collision. And since packets are sent only once to a single forwarder, the probability of packet lost is also high. Moreover, the delivery time may suffer from the overhead of the network discovery process.

Flooding techniques on the other hand, in their purest sense, broadcast messages epidemically by forwarding the data to all of its neighbors [12]. In flooding techniques, data is delivered relatively fast because there is minimal or no overhead [13]. However, flooding protocols are notorious for causing broadcast storms which lowers deliver ratio due to high chance of collision between messages. Usual attempts to solve the problem like RBVT [13, 14], MHVB [12, 15] and RSB [16] assign neighboring nodes a waiting time before sending. It has a value commonly dependent on the forward progress given by $d_{S D} - d_{N_{i} D}$ , where $d_{S D}$ is the distance between the sink S and the destination D and $d_{N_{i} D}$ is the distance between the receiving neighbor $N_{i}$ and D [12– 16]. The best neighbor, through computation of its own waiting time, should in principle have the least value. By this, the best node broadcasts first. The other neighbors cancel their timers and suppress rebroadcasting or reset their timer to a random value [16], after receiving the duplicate broadcast from the winning node. Such technique can be generally referred to as the election approach [14]. The approach has also an advantage of implicitly having multiple backup forwarders.

The following section explains how to solve the drawbacks of both relay and flooding approaches for the WSN's distribution network.

3. Multicriteria Sender-Side Election Protocol

To explain our proposed protocol named multi-criteria sender-side election (MCSS) protocol, we discuss how we model the local network using neighbor information then present how it is used to rank the neighboring nodes. We present how we assign justifiable waiting time to the best k ranking sinks. Lastly, we discuss how the idea fits into the whole delivery protocol.

3.1. Neighbor Table

Instead of building a path from the sink to the GW, our protocol selects its next forwarder on each hop in order to improve data delivery ratio and end-to-end delay. For each hop, the forwarding node ranks its one-hop neighbors with respect to how much they are able to receive the message. We call it the fitness value of a neighboring node. The fitness value reflects the communication environment of the node. To do this, the Neighbor Table (NT) contains three fields: received signal strength (RSS), nodal delay of messages received from the neighbor, and hop distance from the GW.

The RSS of a message measures the signal strength between the sink and the neighbor. The higher the RSS, the better the chance that broadcasts are successful. The nodal delay describes the amount of time it takes for a message to be delivered from the sink to the neighbor. It includes the processing delay, the queuing delay, the transmission delay, and the propagation delay. The less is the nodal delay of messages received, the less is the end-to-end delay. Since packet loss probability in a wireless multi-hop communication environment increases with the number of hops [17], we choose the hop distance between the neighbor and the GW as one of the criteria. To infer the hop distance of each node, we periodically flood a PROBE message in the distribution network.

The sinks update their own NTs for every message received. The three fields of the received messages are averaged using the Exponential Moving Average (EMA). We think of the NT as an ordered set of the ith neighbor vector $\vec{v_{i}} = 〈 c_{i, j} 〉, i = 1,2, \dots, n$ and $j = 1,2, 3$ with $c_{i, 1}$ as the RSS, $c_{i, 2}$ as the nodal delay, and $c_{i, 3}$ as the hop distance of neighbor i from the GW. Each value is updated as follows:

\begin{matrix} {\overset{̅}{c}}_{i, j} (t) = α {\overset{̅}{c}}_{i, j} (t - 1) + (1 - α) c_{i, j} (t), \end{matrix}

(1)

where

{\overset{̅}{c}}_{i, j} (t)

and

{\overset{̅}{c}}_{i, j} (t - 1)

are the new and old average values at time t, respectively.

c_{i, j} (t)

is measured value at time t and the constant α is a smoothing factor.

3.2. Selection of Forwarders

The conventional schemes selecting a single forwarder can increase the chance of data delivery failure because the forwarder can miss the message in dynamic communication environment. Thus, we choose more than one forwarder by ranking neighbor nodes. To rank the nodes, we compute the fitness value using the three fields in NT for each neighbor. Note that the number of forwarders depends on the degrees of connection. In our experiments, we set it the half of the number of sink's neighbors.

In general, the larger is the value of RSS and the smaller are the nodal delay and hop distance, the better is the performance. For the consideration, we inverse the nodal delay and hop distance using

c_{i, j} = {\begin{cases} \frac{1}{(c_{i, j} + λ)}, & j = 2,3 \\ c_{i, j}, & j = 1, \end{cases}

(2)

where λ is a very small positive number used to avoid division by zero. The fitness value

F_{i}

of node i is given as

F_{i} = \sum_{j = 1}^{3} Γ_{j} (c_{i, j}) \cdot w_{i, j},

(3)

where

Γ_{j} (c_{i, j})

is the min-max normalization function of

c_{i, j}

. The weight

w_{i, j}

can be thought of as the importance of field j to the overall evaluation and it is calculated as

w_{i, j} = \frac{\max_{i \in n} c_{i, j}}{\sum_{i \in n} c_{i, j}} .

(4)

The top k ranked neighbors are chosen as forwarders. To illustrate our method, we use the node setup in Figure 1 and NT in Tables 1– 3. Here, the sink S sends a data to the GW and ranks its neighbors A and B. The final ranking makes B the overall best neighbor with a fitness value equal to 0.95. If

k = 1

, then only B is considered as a forwarder.

Table 1

Neighbor table of S in Figure 1.

Neighbor	RSS (dBmV/m)	Nodal delay (microseconds)	Hop distance (hops)
A	3	4.5	2
B	2.5	4	1
C	2	4.3	1

Table 2

Inverse values for Table 1 with $λ = 1 \times 1 0^{- 9}$ .

Neighbor	RSS*	Nodal delay	Hop distance
A	3	0.22	0.5
B	2.5	0.25	1
C	2	0.23	1

Table 3

Scores and fitness values of the neighbors of S based on Table 2 with $w_{1} = 0.4$ , $w_{2} = 0.35$ , and $w_{3} = 0.4$ .

Neighbor	RSS Score	Nodal delay Score	Hop distance Score	Fitness value
A	1	0	0	0.4
B	0.5	1	1	0.95
C	0	0.37	1	0.52

Figure 1

Sink S sends a message to the GW through one of its neighbors A, B or C.

The responsibility of computing the waiting time is moved from the receiving neighbors to the sink. After choosing the forwarders, the sink assigns each forwarder with a waiting time [18]. We assign the best ranked forwarder with zero waiting time. For the waiting time gaps between adjacently ranked forwarders, we use the nodal delays between each of them.

The waiting time assigned to a forwarder with rank $r = 1, 2, \dots, k$ is given as

(r - 1) \frac{\sum_{i = 1}^{k - 1} c_{i, 2}}{k - 1} + β,

(5)

where β is a small random number. The waiting time table as shown in Table 4 is appended to and sent together with the data.

Table 4

Waiting time table with $n = 2 (β = 0)$ .

Neighbor	Waiting Time
B	0
C	4.15

3.3. The Delivery Protocol

This section discusses the overall data delivery protocol from a sink to the GW. When a sink collects and aggregates sensed data from the sensors in its service area, it sends the aggregated data to the GW. We refer to the aggregated data as the message. We use the hybrid sender-side election approach discussed above. Additionally, each sink node keeps a record of the messages and sends and forwards in a message table (MT). An entry in the MT contains a message ID and the last known time-to-live (L_TTL). An ACK field is also included to serve as a crossing-out mechanism for successfully acknowledged one-hop broadcasts and is initially set to NO_ACK.

The sink node computes its waiting time and attaches it to the message. The message is broadcasted to its neighbors. The sink enters waiting mode for the message by starting a timer initially set to the mean of its forwarders' nodal delay. And the sink creates an entry in the MT with L_TTL equals to the maximum TTL. If a duplicate message is received during the time and the TTL is less than L_TTL, the sink stops its timer and exits waiting mode. The message is acknowledged by setting ACK to YES_ACK and ignores future duplicates. In other words, the received message is already a rebroadcast from one of its forwarders and has already progressed by one hop. We refer to the condition as the suppression condition. Otherwise, if the timer expires, the message is rebroadcasted. Figure 2 illustrates the data delivery process.

Figure 2

Sequence diagram for an example data delivery scenario for Figure 1.

4. Experimental Results and Analysis

In this section, we present our experiments done using the NS-2 simulator [19]. We used the shadowing propagation model [20] with path loss exponent $β = 3.0$ and shadowing deviation $σ_{dB} = 5.0$ to model a noisy outdoor environment. Sinks are placed in a 2000 m by 2000 m area and a transmission range of each node is 250 m. A sink sends a message to the GW every second at constant bit rate (CBR) for 100 seconds. Additionally, we use IEEE 802.11 [21] as the MAC layer.

We first experimented on both conventional flooding and relay approaches to serve as basis for comparison with our protocol. For the relay approach, we investigated four combinations of criteria setups. In all setups, nodes send a control message every 100 milliseconds. For the flooding approach, we experimented on two weight combinations of the RBVT protocol [13]. This protocol uses forward progress, RSS and optimal transmission area given by

f_{trans} (x) = {\begin{cases} x + d_{trans}, & x \leq d_{opt}, \\ - x + d_{\max}, & x > d_{opt}, \end{cases}

(6)

where

d_{opt} = 100 m

and

d_{\max} = 250 m

are the optimal and the estimated maximum transmission ranges, respectively, and

d_{trans} = 150 m

is the translation distance.

We evaluated the performance of the protocols through the following performance factors. (1)

Data delivery ratio—the value computed by dividing the number of data packet successfully received at the GW by the total number of data packets sent by sinks.

(2)

End-to-end delay—the time needed to forward data from a sink to the GW.

In Figure 3, we can see that the relay approach using only RSS performs best in terms of delivery ratio compared to other conventional setups. Its performance falls with the increase of neighbor density. This is due to collisions from the intense number of control messages. On the other hand, though RBVT does not send control messages, its delivery ratio might have suffered from huge waiting time values being directly equal to the sum of the three criteria.

Figure 3

Data delivery ratio of conventional protocols.

In Figure 4, relay approach using only RSS is still the best performing protocol in terms of end-to-end delay. Though RBVT does not have a discovery process, the distance-dependent waiting time makes it perform worst. Additionally, it is also important to note that considering RSS more makes the overall performance of the relay approach better and somewhat less spiky. This gives us an idea on how important the assignment of weights is.

Figure 4

End-to-end delay of conventional protocols.

Using the best setups for both conventional approaches, we compared the performance of our MCSS protocol using two weight combinations. In Figure 5, we can see that our protocol achieves an increase of about 20% in data delivery ratio. It is caused by the reduction of control messages. Additionally, the assignment of zero waiting time value for the best forwarders avoids unnecessary pending for message. Moreover, the improved performance can also be attributed to having the $k - 1$ ranking forwarders as backup resenders.

Figure 5

Data delivery ratio of MCSS and conventional protocols.

In Figure 6, we can see that MCSS decreases the end-to-end delay of relay approach and RBVT protocol by about 100% and 500%, respectively. It is due to the waiting time values being well gapped, that is, nodal delay dependent and sender-side assigned. Additionally, note that varying the weights in our protocol has minor effect on its overall performance. Hence MCSS is resilient to poor weight assignments with respect to the protocols experimented upon.

Figure 6

End-to-end delay of MCSS and conventional protocols.

We therefore conclude from the above experimental results that our MCSS protocol improves the quality of data delivery between the sinks and the GW in terms of end-to-end delivery ratio and delay.

5. Conclusion

We developed a fast and reliable data delivery protocol for large-scale heterogeneous sensor networks. The summary and contributions of this paper are as follows. (1)

We identified the data delivery problem in the distribution network of large-scale heterogeneous WSNs.

(2)

We analyzed conventional wireless data delivery protocols and enumerated their weaknesses.

(3)

We developed a selection algorithm of forwarders.

(4)

We developed a sender-side waiting time assignment algorithm for forwarders.

(5)

We developed a general hybrid multi-criteria sender-side election protocol which utilizes the two developed ideas.

(6)

We applied our approach to the data delivery process between the sinks and the GW in the distribution network.

(7)

We showed that our protocol outperforms conventional data delivery protocols in terms of data delivery ratio and end-to-end delay.

In our approach, we used three criteria to model WSN. As a future work, we will do research on more possible criteria and on ways to assign weights dynamically to correspond to a better performance.

Footnotes

Acknowledgment

This work was supported by the GRRC program of Gyeonggi province ([(GRRC SUWON2011-B4), Research on Precision Location Tracking System for Real-Time Situation).

References

Chen

Tse

C. K.

Feng

Minimizing effective energy consumption in multi-cluster sensor networks for source extraction

IEEE Transactions on Wireless Communications 2009 8 3 1480 1489

2-s2.0-62949228349

10.1109/TWC.2008.080319

4801500

Culler

Estrin

Srivastava

Overview of sensor networks

IEEE Computer 2004 37 8 41 49

2-s2.0-4344668573

10.1109/MC.2004.93

Romer

Mattern

The design space of wireless sensor networks

IEEE Wireless Communications 2004 11 6 54 61

2-s2.0-11144332044

10.1109/MWC.2004.1368897

Niculescu

Communication paradigms for sensor networks

IEEE Communications Magazine 2005 43 3 116 122

2-s2.0-17744388372

10.1109/MCOM.2005.1404605

Al-Karaki

J. N.

Kamal

A. E.

Routing techniques in wireless sensor networks: a survey

IEEE Wireless Communications 2004 11 6 6 28

2-s2.0-11144277843

10.1109/MWC.2004.1368893

Luo

Cheng

Zhang

A two-tier data dissemination model for large-scale wireless sensor networks

Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MobiCom '02)

September 2002

Atlanta, Ga, USA

148 159

2-s2.0-0036949025

De Couto

Aguayo

Bicket

Morris

A high-throughput path metric for multi-hop wireless routing

Wireless Networks 2005 11 4 419 434

2-s2.0-23044444929

10.1007/s11276-005-1766-z

Sankarasubramaniam

Akan

O.B.

Akyildiz

I.F.

ESRT: event-to-sink reliable transport in wireless sensor networks

Proceedings of the Annual ACM International Conference on Mobile Computing and Networking (MobiCom '03)

June 2003

Annapolis, Md, USA

177 188

Cataldi

Tomatis

Grilli

Gerla

A novel data dissemination method for vehicular networks with rateless codes

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '09)

April 2009

1 6

2-s2.0-70349172158

10.1109/WCNC.2009.4917521

10.

Szymanski

B. K.

Chen

G. G.

Computing with time: from neural networks to sensor networks

Computer Journal 2008 51 4 511 522

2-s2.0-46749112746

10.1093/comjnl/bxm109

11.

Zhao

Liu

Jiang

Distributed neural network routing algorithm based on global information of wireless sensor network

Proceedings of the WRI International Conference on Communications and Mobile Computing (CMC '09)

January 2009

Yunnan, China

552 555

2-s2.0-64549093367

10.1109/CMC.2009.103

12.

Osafune

Lin

Lenardi

Multi-hop vehicular broadcast (MHVB)

Proceedings of the 6th International Conference on ITS Telecommunications (ITST '06)

June 2006

Chengdu, China

757 760

2-s2.0-44449143634

10.1109/ITST.2006.289011

13.

Nzouonta

Rajgure

Wang

Borcea

VANET routing on city roads using real-time vehicular traffic information

IEEE Transactions on Vehicular Technology 2009 58 7 3609 3626

2-s2.0-69549116414

10.1109/TVT.2009.2014455

14.

Egoh

De Swades

A multi-criteria receiver-side relay election approach in wireless ad hoc networks

Proceedings of the ITST 2006 Military Communications Conference (MILCOM '06)

October 2006

Washington, DC, USA

2-s2.0-35148861618

10.1109/MILCOM.2006.302362

15.

Cherif

M. O.

Secouci

S. M.

Ducourthial

How to disseminate vehicular data efficiently in both highway and urban environments?

Proceedings of the 6th Annual IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob '10)

October 2010

Niagara Falls, Canada

165 171

2-s2.0-78650748813

10.1109/WIMOB.2010.5644988

16.

Lee

Chen

Reliably suppressed broadcasting for Vehicle-to-Vehicle communications

Proceedings of the 71st IEEE Vehicular Technology Conference, VTC 2010-Spring

May 2010

Taipei, Taiwan

1 7

2-s2.0-77954949041

10.1109/VETECS.2010.5493961

17.

Toumpis

Goldsmith

A. J.

Capacity regions for wireless ad hoc networks

IEEE Transactions on Wireless Communications 2003 2 4 736 748

2-s2.0-3042796475

18.

Wang

Xie

Chatterjee

Small-scale and large-scale routing in vehicular ad hoc networks

IEEE Transactions on Vehicular Technology 2009 58 9 5200 5213

2-s2.0-70450185449

10.1109/TVT.2009.2025652

5089413

19.

The network simulator, ns-2

http://www.isi.edu/nsnam/ns/

20.

Rappaport

T. S.

Wireless Communications, Principles and Practice 1996

New York, NY, USA

Prentice Hall

21.

IEEE Std. 802.11

Wireless LAN medium access control (MAC) and physical layer (PHY) specification: higher speed physical layer (PHY) extension in the 2.4 GHz Band

1999