Ultra-low-power media access control protocol based on clock drift characteristics in wireless sensor networks

Abstract

Many researchers have analyzed sources of uncertainty in synchronization protocols for wireless sensor networks. However, very few researchers perform this work in depth, and failed to discover comprehensive characteristics since they worked with only one or two measurement intervals. To overcome this problem, extensive measurements were conducted and analyzed to find the characteristics of the sources according to various measurement intervals. Using the characteristics, a new media access control protocol, WideMAC, was designed to support a wide range of duty cycles for various applications. The transmission node in WideMAC calculates the wakeup time of the reception node before transmitting a packet and adaptively estimates the synchronization error size according to the synchronization interval from seconds to hours. To track the reception node’s wakeup time for synchronization, WideMAC uses two estimation algorithms that estimate the wakeup time and the upper bound of the total timing error. Accurate estimation of the wakeup time results in a significant amount of energy saving at the transmission node. Finally, through extensive performance evaluations in a testbed, WideMAC confirmed that it can significantly outperform existing state-of-the-art protocols.

Keywords

Wireless sensor network ultra low power clock drift ultra-low duty cycle long network lifetime

Introduction

Wireless sensor networks (WSNs) have an attractive emerging technology that can support a myriad of services involving environmental monitoring, sensing, and data collection. In particular, WSNs are playing an increasingly important role in monitoring applications such as automatic metering reading or advanced metering infrastructure.¹

Since it is prohibitively expensive or even infeasible to replace batteries of WSN nodes in many environments, it is important that the network remains operational for a long period (i.e. have a long “lifetime”). Given the unique traits of monitoring applications, a wireless sensor media access control (MAC) protocol should be designed differently from other ad hoc or wireless MAC protocols, explicitly considering its particular characteristics.

One of the most effective ways to increase the lifetime of a WSN node is to put it into sleep mode periodically but this causes an additional problem, that is, how to find the wakeup time of the reception (RX) node. To solve this problem, there exist two approaches that are classified into synchronous and asynchronous types.

Synchronous MAC protocols such as S-MAC² and T-MAC³ are computationally expensive and consume a significant amount of energy in exchanging control packets between neighbor nodes to ensure synchronization of nodes according to a sleep-wake timetable. In this way, the transmission (TX) node wastes very little energy during its transmission period because it knows the exact wakeup schedule of each neighboring node. Nonetheless, synchronous MAC protocols waste energy due to the large synchronization overhead, especially for low-traffic applications. These problems get exacerbated when individual clocks have random amounts of drift depending on various environmental factors.

In contrast, asynchronous MAC protocols such as X-MAC⁴ and RI-MAC⁵ do not waste energy on periodic synchronization. However, their main drawback lies at the other end of the spectrum. The TX node spends considerable energy to find the wakeup time of each neighbor when it has a packet to transmit. Hence, they could waste a significant amount of energy, especially in low duty-cycle environments. To mitigate this problem, hybrid approaches such as SCP-MAC⁶ and WiseMAC⁷ have been introduced. However, they do not fully exploit the characteristics of sources for uncertainty, thus their improvements are limited.

As understanding the exact characteristics of sources of uncertainty is essential to finding the fundamental solution to these problems, there have been many related research efforts. These mainly analyzed the characteristics with only a few fixed measurement intervals because their targets are periodic synchronization protocols. With limited previous work, it is difficult to discover the comprehensive characteristics of uncertainty sources.

In this research, the characteristics of sources for uncertainty were extensively measured according to various measurement intervals. Through analyzing the relation between the clock drift size and the measurement interval, it was found that the ratio of the synchronization error to the synchronization interval can be modeled by a linear function without serious errors. Using this result, a new WSN MAC protocol named WideMAC was designed to use two estimation algorithms that estimate the wakeup time and the upper bound of the total timing error.

When WideMAC has a packet to send, it estimates the upper bound of the error size based on the history of the synchronization interval and error size. With the obtained tight upper bound, the TX node can transmit a data packet within a short wakeup period, thus saving a significant amount of transmission energy. By adopting the recursive estimation algorithm in So et al.,⁸ the memory requirement of WideMAC is very low. Therefore, WideMAC can run on most WSN node platforms due to its low memory requirement.

It supports aperiodic transmission as well as periodic transmission. Against most existing protocols that suffer from significant energy consumption in the ultra-low duty-cycled environments, WideMAC shows extremely low energy consumption even in the very low duty-cycled environments. Thanks to these features, it can support various applications such as infrequent event detection or monitoring with very long transmission intervals from seconds to hours.

The remainder of this article is organized as follows. In section “Related work,” related work is briefly described, and the measurement results for the relative clock drift variation are shown in section “Relative clock drift analysis.” In section “WideMAC protocol,” the proposed protocol is described in detail. Evaluation results are presented in section “Performance evaluation” by comparing the performance of the proposed MAC protocol with those of existing state-of-the-art protocols. In section “Conclusion,” the main results of the article are summarized and the conclusion is presented.

Related work

Clock drift

Oscillators or crystals that run individual clocks have different clock speeds within a margin of error that depends on the cost of each oscillator. Furthermore, the clock speed of each node can change due to clock drift that may depend on various environmental factors. This results in a serious problem for sensor communications since the TX node does not exactly know when the RX node wakes up.

A simple solution to this is to use a global positioning system (GPS) module or a very accurate clock (e.g. an atomic clock). However, these solutions are too expensive or energy inefficient. For example, a GPS device is not only expensive but also consumes about 30 to 360 times more power than a radio chip.⁹ Currently, a more practical approach is to use a synchronization protocol to predict and adjust each clock experiencing drift.

As clock accuracy and characteristics are important for a wide variety of applications, there have been many researches in this area. These studies have found that clock drift can be caused by various environmental factors such as temperature and humidity, as well as software and hardware architectures.^10,11 They also found that the distribution of the clock drift rate follows Gaussian.^12,13

However, most previous research focused on the clock drift at a fixed measurement interval because the goal was to develop periodic synchronization protocols. Thus, these results cannot show the relation between the clock drift and the measurement intervals, which is important in the context of event monitoring applications.

Wakeup time estimation algorithm

The wakeup time estimation algorithm determines the total energy consumption of WSN MAC protocols, thus, it should be carefully designed according to the requirements of upper layers such as node lifetime and a sleep period. According to the way to obtain the wakeup time, MAC protocols can be classified into three types: asynchronous, synchronous, and hybrid.

In asynchronous MAC protocols, a TX node should find an RX node’s wakeup time before packet transmission by hearing or sending beacon packets repeatedly over one sleep period.¹⁴ X-MAC⁴ and RI-MAC⁵ are famous protocols that belong to this category.

Generally, the amount of energy consumption is proportional to the packet transmission rate and the wakeup interval. Since an asynchronous MAC protocol does not use a synchronization algorithm, its implementation is very simple, but it consumes a higher energy for transmission than a synchronous MAC protocol. Hence, it is effective only for applications with infrequent packet generation and a high duty cycle.

Synchronous MAC protocols require many control packets and consume a large portion of the wakeup period for synchronization.^2,15 Each node can send packets to destinations without worrying about clock drift and thus easily support control plane functions of the upper layer such as route recovery.

Wakeup time estimation algorithms in synchronization protocols can be broadly classified into three types, that is, linear regression, phase-locked loop, and bounded drift model–based approach.¹⁶ Linear regression finds the clock speed ratio $s$ and the time offset $d$ to minimize the difference between the fitted value and the sampled one as follows¹⁷

τ_{i} = s \cdot t_{i} + d

where $t_{i}$ and $τ_{i}$ are times represented by TX and RX nodes, respectively. Least squares or generalized least squares are usually used for linear regression. More samples help more exact estimation but require a larger amount of memory.

Phase-locked loop (PLL) is originally designed to maintain the local oscillator in the same phase and frequency as the reference signal by applying a correction signal to the oscillator. The input of PLL is the difference between the actual sample and the fitted value. It detects its slope and offset by using the proportional–integral (PI) controller. PLL needs less memory than linear regression, but requires a longer time for convergence.¹⁸

The bounded drift model–based estimation algorithm is one of the simplest algorithms, but very practical in terms of implementation. In this model, the clock drift rate is assumed to be bounded by the maximum clock drift rate (MCDR) denoted as $θ$ . The upper bound of the synchronization error can be given as the product of the MCDR and the synchronization (or packet transmission) interval. Therefore, the margin size $m (\cdot)$ for the error is usually set to

m (Δ t) = 2 θ Δ t

(1)

where the interval is $Δ t$ . For instance, it is 60 clocks/s or 1.83 ms/s when $θ$ is 30 ppm (parts per million).^19,20 The reason for using $2 θ Δ t$ is that the worst case occurs when the TX and RX nodes have the clock drift rates of $θ$ and $- θ$ , respectively. However, $2 θ Δ t$ is only for the positive side margin, so the total margin is 4 $θ Δ t$ when the positive and negative margins are counted.¹⁶

The well-known protocols to use this algorithm are SCP-MAC and WiseMAC.^6,7 They operate in an asynchronous manner at first and then synchronously uses the estimation of the wakeup time of the RX node based on the last successful transmission and the MCDR. Hence, they are called hybrid protocols. Since this algorithm requires only two values of the last wakeup time and the sleep period, and uses a very simple algorithm to calculate the margin size, it can be used for most off-the-shelf WSN node platforms.

However, the linear regression and PLL require long-precision floating point numbers and a large memory size, which can be a burden in low-cost WSN nodes. Moreover, the bounded-drift model can be used for both aperiodic and periodic synchronous protocols, while linear regression and PLL are usually used for periodic synchronization protocols.

The energy consumption of the TX node in the bounded-drift model is determined by the MCDR and not by the sleep period. As the amount of the total energy consumption is inversely proportional to the sleep period, the network lifetime can be prolonged by lowering the duty cycle.

Periodicity of synchronization

Most synchronization protocols use a fixed synchronization interval, thus they are called periodic synchronization protocols. There are a few protocols that do not require any fixed synchronization intervals, which are classified as aperiodic synchronization protocols. A well-known aperiodic synchronization protocol is post-facto synchronization developed by Elson et al.²¹ It requires some nodes to broadcast synchronization pulses that help other nodes synchronize with each other.

Relative clock drift analysis

The most important process of a WSN MAC protocol for an ultra-low duty-cycle environment is to estimate when the RX node wakes up without consuming much energy. However, as mentioned earlier, in practice, this is difficult to accomplish because the clock drift of a node changes according to various factors.^11,12

In this section, experimental scenarios are presented and the measurement results are analyzed for the relative clock drift based on various measurement intervals. The packet reception and transmission times at MAC layers of the TX and RX nodes are measured, respectively, and the relative clock drift from these measurements is calculated.

Most existing research calculates the absolute clock drift from the difference between each node’s clock and GPS time.¹² These experiments are useful to obtain the characteristics of the clock drift incurred by the oscillator or crystal.

However, the relative clock drift, which occurred between the RX and TX nodes, is our focus. The experiments were performed to observe the relative clock drift characteristics of nodes located in the outdoor environment. In the experiments, three node types such as TelosB,²² MICAz,²³ and HMote²⁴ were used. For every node type, 11 nodes were used.

For easy description, some terminologies similar to those in Sundararaman et al.²⁵ are defined, where $t_{k}$ is the $k$ th measurement time and $k$ th measurement interval. We assume that $t_{k + 1} - t_{k}$ is fixed at $Δ t$ for $\forall k \in N_{0}$ .

Relative time

The time represented by a node’s clock when the reference node time is given. If the current reference node time is $t_{k}$ , the relative time of node A is denoted by $C_{A} (t_{k})$ .

Relative clock drift

The difference of the estimated relative time, that is, ${\tilde{C}}_{A} (t_{k + 1})$ , and the real relative time, that is, $C_{A} (t_{k + 1})$ is given by $ω_{A} (t_{k + 1}) = {\tilde{C}}_{A} (t_{k + 1}) - C_{A} (t_{k + 1})$ .

Relative clock drift rate

The ratio of the relative clock drift to the interval, that is, $Ω_{A} (t_{k + 1}) = \frac{ω_{A} (t_{k + 1})}{Δ t}$ .

Relative clock drift measurements

In the experiments, all the nodes are static and the TX node periodically sends a time-stamp message containing its clock counter to 10 RX nodes within its transmission range as shown in Figure 1. Whenever each RX node receives the message, it calculates the relative clock drift rate between the TX and RX nodes, and updates the statistics stored in the memory.

Figure 1.

Topology for the relative clock drift measurement: (a) time-stamp message broadcasting and (b) data gathering.

After all transmissions are completed, each RX node sends its collected data to the TX node and the TX node forwards the gathered data to the PC via USB cable. Eight message intervals were used for experiments, and each interval is denoted by $T_{k}$ where $k = 0, 1, \dots, 7$ . The smallest interval $T_{0}$ and the largest interval $T_{7}$ were set to 0.25 s and 64 min, respectively. For each interval of $T_{k}$ , the relative clock drift at the $i$ th measurement between the TX node and the $j$ th RX node is simply denoted by $ω_{j}^{(k)} (i)$ instead of $ω_{j} (T_{k} \cdot i + t_{0})$ , where $t_{0}$ is the measurement start time. Maximum relative clock drift and rate are measured, which are defined as follows, respectively

\begin{matrix} ω^{(k)} = \max {| ω_{j}^{(k)} (i) |, \forall i, j} \\ Ω^{(k)} = \frac{ω^{(k)}}{T_{k}} \end{matrix}

(2)

where |·| is the absolute value operator. The maximum relative clock drift determines the margin size, that is, the upper bound for the synchronization error. For example, if the margin size is set to a larger value than the maximum relative clock drift, the TX node can synchronize with the RX node without failure.

In addition, the MCDR is a very important factor as it mainly affects the energy consumption of the synchronization protocols. If the synchronization energy consumption is defined as the energy wasted to learn the wakeup time of the RX node, the estimation error in the clock drift rate directly affects the energy consumption for synchronization. Intuitively, synchronization energy consumption is proportional to the maximum relative clock drift rate (energy consumed by actual data transmission can be ignored because the traffic generation rate is low in WSN). Then, the total synchronization energy consumption for a given duration $t$ (in J/s) can be expressed as

E (t, T_{k}) \approx ϕ \cdot \frac{T_{k}}{t} \cdot Ω^{(k)} \cdot t = ϕ \cdot T_{k} \cdot Ω^{(k)}

(3)

where $ϕ$ is a proportional constant linked with the communication energy consumed in 1 s. Therefore, it can be concluded that the maximum relative clock drift rate determines the average energy consumption of synchronization protocols.

The experiments were performed for 14 days in an outdoor environment. Experimental results only for TelosB are presented because those for MICAz and HMote show similar qualitative results.

Relative clock drift measurement results

The measurement results for the relative clock drift are given in Figure 2 with respect to some selected time-stamp message intervals. Figure 2 shows that Gaussian distribution works only for large intervals against the previous study results that claim Gaussian distribution of the relative clock drift size.¹² If the interval is smaller than or equal to 1 min, the distribution of the relative clock drifts exhibits a very different form.

Figure 2.

Maximum relative clock drift distribution according to the time-stamp message interval: (a) 0.25 s, (b) 1 s, (c) 1 min, (d) 4 min, and (e) 1 h.

Most WSN nodes adopt a clock source such as a 32 KHz-oscillator. Thus, clock errors due to the coarse granularity always exist and the size is small but fixed regardless of the interval size. Moreover, a packet is generally handled by a specific task for transmission in a WSN node. If the interval size decreases, the more frequent packet transmission causes higher processor load resulting in increased scheduling delay and variations.¹¹ Thus, these errors caused by coarse granularity or scheduling overhead dominate the overall relative clock drift when the interval is small.

For further investigation, Figure 3 shows the measured maximum relative clock drift and rate according to the message interval. The line marked with empty circles represents the MCDR ( $θ$ ) × 2 and shows the margin for the relative clock drift rate used in bounded drift model–based protocols.

Figure 3.

Maximum relative clock drift and rate of experimental results, where $θ$ = 30 ppm: (a) relative clock drift and (b) relative clock drift rate.

In Figure 3(a), the size of the maximum relative clock drift increases with the interval. It is obvious that it has more chances of the environmental change such as temperature and humidity occurs if the interval is larger. However, it is almost fixed for intervals less than 1 min due to the errors caused by clock granularity and scheduling delay.

On the contrary, the maximum relative clock drift rate decreases rapidly with the interval in Figure 3(b). equation (3) and Figure 3(b) imply that periodic synchronization may not be optimal in terms of energy consumption. It is advantageous to perform synchronization when the TX node has a packet for saving energy.

WideMAC protocol

In this section, WideMAC is proposed to achieve a very low energy consumption and support a wide range of duty cycles. WideMAC uses simple estimation algorithms and requires a very small size of memory. Due to these features, it can be implementable on most existing node platforms. It efficiently supports very long traffic intervals, that is, seconds to hours, and the overall energy consumption decreases with the interval.

It adopts a hybrid approach similar to WiseMAC to remove the periodic synchronization overhead. It uses an adaptive estimation algorithm to find an exact error margin to improve the energy efficiency. The estimation algorithm exploits the relation between error size and synchronization interval from Figures 3(a) and 4.

Figure 4.

Maximum relative clock drift in linear scale for Figure 3(a).

When WideMAC initializes or loses synchronization, it operates similar to X-MAC⁴ that uses a small-sized packet called preamble to find the wakeup time of the RX node. The RX node replies with a preamble acknowledgment (ack) and waits for a data packet. If the TX node receives the ack, it sends a data packet to the RX node. Otherwise, the preamble will be retransmitted.

After the TX node discovers the wakeup time of the RX node, WideMAC does not send preambles when a packet transmission request arrives. Instead, it estimates the wakeup time and the timing error size for the RX node. After the estimation, it sends preambles only within the estimated range of the wakeup time for the RX node. Therefore, it can significantly decrease the energy consumption.

Motivation

According to Figures 3(a) and 4, the maximum relative clock drift can be modeled by

ω (Δ t) = \max {ω_{\min}, σ Δ t + δ}

(4)

where $Δ t$ is the inter-packet transmission time.

If $σ$ and $δ$ are successfully obtained, the optimal margin size can be calculated using $ω (\cdot)$ . For simple explanation, some notations are defined assuming a pair of RX and TX nodes (this assumption can be generalized easily).

t_n: The earliest wakeup time of RX node to receive a packet from TX node in terms of TX node’s clock when TX node has the $n$ th packet to be transmitted to RX node.

$t_{n}^{*}$ : Estimated $t_{n}$ in terms of TX node’s clock.

$Δ t_{n} : t_{n} - t_{n} - 1$ .

$τ_{n}$ : $t_{n}$ in terms of RX node’s clock.

$τ_{n}^{*}$ : $t_{n}^{*}$ in terms of RX node’s clock.

$Δ τ_{n} : τ_{n} - τ_{n - 1} .$

m_n: Margin size.

e_n: Error size of the estimated wakeup time, that is, $t_{n}^{*} - t_{n}$

T: The wakeup interval time of RX node in terms of RX node’s clock.

Wakeup time estimation

The TX node can find the exact wakeup time of the RX node, that is, $τ_{i}$ whenever it receives a preamble ack. To estimate the relative clock speed from the history of $(t_{i}, e_{i})$ pairs, the recursive estimation algorithm is used.⁸ Since it requires only five variables and single-floating point operations, it can be implemented easily in any sensor node platforms

\begin{matrix} < s_{n}, d_{n} > = \underset{< {\hat{s}}_{n}, {\hat{d}}_{n} >}{\arg \min} {\sum_{i = 1}^{n} γ^{n - i} {(τ_{i} - {\hat{τ}}_{i})}^{2}} \\ = \underset{< {\hat{s}}_{n}, {\hat{d}}_{n} >}{\arg \min} {\sum_{i = 1}^{n} γ^{n - i} {(τ_{i} - {\hat{s}}_{n} t_{i} - {\hat{d}}_{n})}^{2}} \end{matrix}

(5)

where ${\hat{τ}}_{i} = {\hat{s}}_{n} t_{i} + {\hat{d}}_{n}$ . The optimal $s_{n}$ and $d_{n}$ can be determined as follows, respectively

s_{n} = \frac{Γ_{n}^{t} Γ_{n}^{t τ} - Γ_{n}^{1} Γ_{n}^{t τ}}{{(Γ_{n}^{t})}^{2} - Γ_{n}^{t^{2}} Γ_{n}^{1}}, d_{n} = \frac{Γ_{n}^{t} Γ_{n}^{t τ} - Γ_{n}^{t^{2}} Γ_{n}^{τ}}{{(Γ_{n}^{t})}^{2} - Γ_{n}^{t^{2}} Γ_{n}^{1}}

(6)

where

\begin{matrix} Γ_{n}^{t} = γ Γ_{n - 1}^{t} + t_{n} \\ Γ_{n}^{τ} = γ Γ_{n - 1}^{τ} + τ_{n} \\ Γ_{n}^{1} = γ Γ_{n - 1}^{1} + 1 \\ Γ_{n}^{t^{2}} = γ Γ_{n - 1}^{t^{2}} + t_{n}^{2} \\ Γ_{n}^{t τ} = γ Γ_{n - 1}^{t τ} + t_{n} τ_{n} \end{matrix}

(7)

Since each term in equation (7) is expressed in a recursive form, the computational cost is very small. The overall procedures for the relative clock speed estimation is presented as follows (Figure 5).

Figure 5.

Clock speed ratio and the time offset estimation.

Error margin estimation

The purpose of margin estimation is to find the minimum margin size for synchronization for successfully transmitting a packet. For synchronization with a fixed interval, the margin size can be easily estimated. In contrast, for synchronization with varying intervals, the margin size estimation is very complicated.

As mentioned earlier, the maximum error size, that is, maximum relative clock drift, increases linearly proportional to the interval size, thus expressed as equation (4). If a sensor node has no information about $σ$ and $δ$ initially, it requires a long history of $(Δ t_{i}, e_{i})$ pairs to find the exact values of $σ$ and $δ$ , which is a significant burden to a low-cost WSN node with a limited memory size (Figure 6). To solve this problem, WideMAC adopts recursive estimation for linear margin estimation again in finding the relation between maximum error sizes and intervals⁸

\begin{matrix} \begin{matrix} < σ_{n}, δ_{n} > = \underset{\hat{σ}, \hat{δ}}{\arg \min} {\sum_{i = 1}^{n} λ^{n - i} {(Δ t_{i} - Δ {\hat{t}}_{i})}^{2}} \\ = \underset{\hat{σ}, \hat{δ}}{\arg \min} {\sum_{i = 1}^{n} λ^{n - i} {(Δ t_{i} - \hat{σ} Δ t_{i} - \hat{δ})}^{2}} \end{matrix} \end{matrix}

(8)

where

\begin{matrix} Λ_{n}^{Δ t} = λ Λ_{n - 1}^{Δ t} + Δ t_{n} \\ Λ_{n}^{Δ τ} = λ Λ_{n - 1}^{Δ τ} + Δ τ_{n} \\ Λ_{n}^{1} = λ Λ_{n - 1}^{1} + 1 \\ Λ_{n}^{Δ t^{2}} = λ Λ_{n - 1}^{Δ t^{2}} + Δ t_{n}^{2} \\ Λ_{n}^{Δ t Δ τ} = λ Λ_{n - 1}^{Δ t Δ τ} + Δ t_{n} Δ τ_{n} \end{matrix}

Figure 6.

Maximum relative clock drift estimation.

only if $e_{n} > ω (Δ t_{n}) = σ_{n} Δ t_{n} + δ_{n}$

The estimator has a new input only when the obtained new error size $e_{n}$ is larger than the estimated error size, $ω (Δ t_{n})$ . As the time elapses, the result of the estimator shows the linear relation between maximum error sizes and intervals. Then, the margin size, $m (n)$ , is given as $α ω (Δ t_{n})$ , where $α (> 1)$ is a safety factor. The overall procedures for error margin estimation are presented in Algorithm 2.

Algorithm 1 Wakeup time estimation
1: $s_{1} = 1$ , $n = 1$ 2: Find $d_{1}$ from the initial packet transmission. 3: loop 4: Find minimum $k$ s.t. $τ_{n} + kT > τ_{n + 1}$ . 5: $τ_{n + 1}^{} = τ_{n} + kT$ 6: Find $t_{n + 1}^{}$ corresponding to $τ_{n + 1}^{}$ . 7: Send a packet at $t_{n + 1}^{}$ . 8: if success then 9: Find $t_{n + 1}$ and $τ_{n + 1}$ . 10: Calculate $s_{n + 1}$ and $d_{n + 1}$ using equation (6). 11: $n \leftarrow n + 1$ 12: end if 13: end loop

Algorithm 1 Wakeup time estimation

s_{1} = 1

n = 1

2: Find

d_{1}

from the initial packet transmission.
3: loop
4: Find minimum

k

s.t.

τ_{n} + kT > τ_{n + 1}

.
5:

τ_{n + 1}^{*} = τ_{n} + kT

6: Find

t_{n + 1}^{*}

corresponding to

τ_{n + 1}^{*}

.
7: Send a packet at

t_{n + 1}^{*}

.
8: if success then
9: Find

t_{n + 1}

and

τ_{n + 1}

.
10: Calculate

s_{n + 1}

and

d_{n + 1}

using equation (6).
11:

n \leftarrow n + 1

12: end if
13: end loop

Algorithm 2 Error margin estimation
1: $α = α_{init}$ , $n = 1$ 2: loop 3: if $Δ t_{n} < Δ t_{\min}$ then 4: $Δ t_{n} \leftarrow Δ t_{\min}$ 5: end if 6: if $m_{n} = α \cdot ω (Δ t_{n}) = α (σ Δ t_{n} + δ) < e_{n}$ then 7: /* Estimation failed. / 8: $α \leftarrow α (1 + δ_{α}^{+})$ 9: else 10: if $ω (Δ t_{n}) < e_{n}$ then 11: if $(Λ_{n}^{Δ t})^{2} - Λ_{n}^{Δ t^{2}} Λ_{n}^{1} = 0$ then 12: / Fixed $Δ t$ */ 13: $σ \leftarrow \frac{Λ_{n}^{Δ t Δ τ}}{Λ_{n}^{Δ t}}$ 14: $δ \leftarrow 0$ 15: else 16: Find $σ$ and $δ$ using equation (8). 17: end if 18: else 19: $α \leftarrow \max {α (1 - δ_{α}^{-}), α_{\min}}$ 20: end if 21: end if 22: $n \leftarrow n + 1$ 23: end loop

Algorithm 2 Error margin estimation

α = α_{init}

n = 1

2: loop
3: if

Δ t_{n} < Δ t_{\min}

then
4:

Δ t_{n} \leftarrow Δ t_{\min}

5: end if
6: if

m_{n} = α \cdot ω (Δ t_{n}) = α (σ Δ t_{n} + δ) < e_{n}

then
7: /* Estimation failed. */
8:

α \leftarrow α (1 + δ_{α}^{+})

9: else
10: if

ω (Δ t_{n}) < e_{n}

then
11: if

(Λ_{n}^{Δ t})^{2} - Λ_{n}^{Δ t^{2}} Λ_{n}^{1} = 0

then
12: /* Fixed

Δ t

*/
13:

σ \leftarrow \frac{Λ_{n}^{Δ t Δ τ}}{Λ_{n}^{Δ t}}

14:

δ \leftarrow 0

15: else
16: Find

σ

and

δ

using equation (8).
17: end if
18: else
19:

α \leftarrow \max {α (1 - δ_{α}^{-}), α_{\min}}

20: end if
21: end if
22:

n \leftarrow n + 1

23: end loop

Performance evaluation

In this section, experimental results for the proposed MAC protocol are presented. To evaluate the performance, four types of MAC protocols including WideMAC were implemented using TelosB²² and TinyOS²⁶ as follows.

Maximum clock drift based MAC protocol: It estimates the margin size with the MCDR, which is exactly the same with WiseMAC. The margin size, $m (Δ t)$ is non-adaptive and given as $2 θ Δ t$ as shown in (1). To compare the performance for different drift rates, a smaller drift rate size, $0.1 θ$ is also applied in addition to $θ$ .

Multiple fixed interval (MFI)-based MAC protocol: Since the margin estimation for a fixed interval is simple, it uses multiple fixed margin sizes to support aperiodic margin estimation. Thus, the total range of intervals is divided into $k$ sub-ranges and the fixed interval estimation algorithm is used for each sub-range. The $i$ th sub-range is given by $(Δ t_{0} ρ^{i}, Δ t_{0} ρ^{i + 1})$ where $ρ > 1$ . For sub-range $i$ , the margin size is $α e_{\max}^{i}$ where the experienced maximum error size is $e_{\max}^{i}$ , and $α (> 1)$ is a safety factor. For small $ρ$ and a sufficient number of $(Δ t_{i}, e_{i})$ pairs, the estimation becomes very accurate.

Rate adaptive synchronization (RATS) protocol: It calculates the sampling window size and estimates the average error size so that the synchronization error remains bounded within the pre-defined maximum error size, $E_{\max}$ ²⁷ The margin size is obtained by multiplication of the estimated average error size and scaling factor, $Δ$ . If the margin size is smaller than the maximum error threshold, the sampling window size increases, or if it is larger than the minimum error threshold, the window size decreases.

Each configuration of the considered protocols is shown in Table 1. The field of “stored variables” indicates the total number of variables maintained at each RX node to estimate the margin size. Since the other protocols except for the MFI-based protocol require very small sizes of memory, they have no difficulty in supporting any WSN node platforms.

Table 1.

Algorithms and configurations in experiments.

Name	Label	Stored variables	Configuration parameters
WideMAC	WideMAC	6	$λ = γ = 0.9$		$δ_{α}^{+} = 1$
Multiple fixed interval based	MFI(1.2)	$46 \cdot 3 = 138$	$ρ = 1.2$	$Δ t_{0} =$ 2 s	$δ_{α}^{-} = 0.2$ ,
	MFI(2)	$13 \cdot 3 = 39$	$ρ = 2$		$α_{\min} = 2$ for 95%
Maximum clock drift based	MCDR	1	$θ$ = 30 ppm
	MCDR(0.1)	1	$θ$ = 3 ppm
RATS	RATS	$25 \cdot 2 = 50$	$Δ = 4.12$ , $E_{\max} = 20$ ms

The energy consumption of the RX node is mainly defined by the wakeup time interval. However, the energy consumption of the TX node is affected by many factors such as duty cycle and traffic rate. Therefore, the total energy consumption of the TX node is measured every 10 h for performance evaluation. Experiments were performed with six pairs of RX and TX nodes in the same outdoor environment for 100 h, where TX nodes send packets to RX nodes according to the four inter-packet time distributions, respectively, for each experiment shown in Table 2.

Table 2.

Inter-packet time distribution.

Name	Interval distribution	Average interval
Fixed small interval	Fixed	1 min
Fixed medium interval		30 min
Fixed large interval		1 h
Variable small interval	Exponential	1 min
Variable medium interval		30 min
Variable large interval		1 h

In each experiment, the preamble packet size is 8 bytes and its transmission interval is 0.26 ms.⁴ Since the packet retransmission is disabled, the packet is dropped if wakeup time estimation is failed. All the algorithms except for the MCDR-based MAC protocol use the recursive estimation algorithm to find the wakeup time of the RX node.

Fixed inter-packet time case

For a fixed inter-packet time, the MCDR-based MAC protocol has almost the same energy regardless of elapsed time since its margin size is determined by the inter-packet time. As shown in Figure 7, when the interval is 1 min, MCDR(0.1) consumes 86% less energy compared with MCDR. When the interval is 1 h, MCDR(0.1) consumes almost 90% lower energy than MCDR as expected since MCDR(0.1) has a margin size 10 times smaller than that of MCDR.

Figure 7.

Average ratio of the energy consumption for TX node of each protocol to that of MCDR when the fixed inter-packet time is used: (a) inter-packet time = 1 min, (b) inter-packet time = 30 min, and (c) inter-packet time = 1 h.

When the interval is fixed, the MFI-based MAC protocols, that is, MFI(2) and MFI(1.2), show almost the same performance regardless of $ρ$ . Only one sub-range of the interval is used in this case so the energy consumption is independent of the number of sub-ranges. When the packet interval is 1 min, WideMAC consumes 84% less energy than MCDR and almost the same energy compared to the other adaptive algorithms with the same safety factor. When the interval is 1 h, it consumes 5% less energy compared to MFI. For the fixed intervals, the margin size of WideMAC is set to $\frac{α Λ_{n}^{Δ t Δ τ}}{Λ_{n}^{Δ t}}$ where $\frac{Λ_{n}^{Δ t Δ τ}}{Λ_{n}^{Δ t}}$ is an exponentially weighted average of given input estimation errors. This helps the estimation based on history of $(Δ t_{n}, e_{n})$ pairs to be reasonably accurate.

RATS protocol requires explicit synchronization which consumes additional energy. As the inter-packet time increases, the overall energy consumption of RATS decreases. However, due to the overhead of explicit synchronization, the performance of RATS can be degraded in terms of the high estimation failure and low packet delivery ratio even if it consumes the same energy compared to competitors.

For the small interval, all the adaptive algorithms need almost 60–70 h to obtain stable margin values as shown in Figure 7(a). It implies that infrequent but abrupt changes in timing information occur. For medium and large intervals, that is, for 30 min and 1 h, they require 50 and 40 h until margins converge, respectively. It is obvious that the larger interval generates the larger margin size. Since the increased margin is less affected by the abrupt change in clock drifts, the convergence time can be reduced.

All the protocols experience similar failure rates regardless of interval size. Thus, failure rates only occur when the inter-packet time is 1 min as shown in Figure 8(a). As shown in the figure, only MCDR always estimated correctly without any failure during evaluation. Other protocols except for RATS failed to estimate the wakeup time only one time but no estimation failure happened after they obtained converged margin sizes. MFI(1.2) and MFI(2) use only one sub-range if the inter-packet time is fixed so they should provide the same performance.

Figure 8.

Estimation failure rate when the fixed inter-packet time is used: (a) inter-packet time = 1 min, (b) inter-packet time = 30 min, and (c) inter-packet time = 1 h.

When the inter-packet time is 1 min, RATS shows a 5% failure rate which is the highest compared to other protocols. Although RATS adaptively calculates the window size and synchronization interval, it also relies on pre-defined configuration values such as $Δ$ and $E_{\max}$ . These values are dependent with the environment which sensor nodes are installed in. Thus, they cannot provide an optimal performance in the different environment.

Table 3 shows the total packet delivery ratio for each protocol. Since packet delivery ratio is proportional to packet transmission delay and energy consumption, it is a very important factor. As shown in the table, WideMAC achieves a very high delivery ratio. Although it does not aim at periodic data transmission, it shows that WideMAC can support a low energy consumption and high delivery ratio simultaneously.

Table 3.

Total packet delivery ratio when the fixed inter-packet time is used.

Inter-packet time (min)	WideMAC	MCDR	MCDR (0.1)	MFI (1.2)	MFI (2)	RATS
1	0.9998	1	0.9998	0.9998	0.9998	0.9537
30	1	1	1	1	1	0.9754
60	0.9882	1	1	0.9882	0.9882	0.9595

Exponentially distributed inter-packet time case

In this experiment, the TX node issues packet transmission requests according to the exponential distribution. Since the packet transmission interval is not fixed, it is possible to investigate the performance of protocols in more realistic environments. Two exponential distributions were used and their average intervals are 1 min and 1 h, respectively. As shown in Figure 9, the results are quite different from the fixed interval cases.

Figure 9.

Average ratio of the energy consumption for TX node of each protocol to that of MCDR when an exponentially distributed inter-packet time is used: (a) inter-packet time = 1 min, (b) inter-packet time = 30 min, and (c) inter-packet time = 1 h.

When the average interval is 1 min, MCDR(0.1) consumes the smallest energy as shown in Figure 9. However, it cannot deal with abrupt changes in clock drift. This leads to high estimation failure as shown in Figure 10(a) that shows the estimation failure rate of each algorithm. The average failure rate in MCDR(0.1) is 1.7% which is much higher than 0.4%, 0.1%, and 0% for MFI(1.2), MFI(2), and WideMAC, respectively. The failure rates of all the algorithms except for MCDR(0.1) and RATS converge to 0%, but only WideMAC achieves 0% estimation failure rate for all experiment time. When the average packet interval is 1 h, MCDR(0.1) significantly consumes energy more than other adaptive algorithms. This shows a limitation in using a constant margin regardless of traffic intervals and clock drifts.

Figure 10.

Estimation failure rate when an exponentially distributed inter-packet time is used: (a) inter-packet time = 1 min, (b) inter-packet time = 30 min, and (c) inter-packet time = 1 h.

When the average packet interval is 1 min, MFI(1.2) uses a very small amount of energy, but its estimation failure rate fluctuates and becomes higher compared to other adaptive algorithms. Although a smaller size of each sub-range leads to a more exact margin estimation, it requires a lot of $(Δ t_{i}, e_{i})$ pairs. Therefore, this leads to a longer convergence time in terms of the margin size. On the contrary, MFI(2) shows a very low estimation failure rate but consumes 30% more energy than MFI(1.2).

In Figure 10, for the small interval, 1 min, WideMAC shows the second best performance except for MCDR(0.1) which has a very high estimation failure rate, and for the large average interval, 1 h, it outperforms all the other protocols except RATS which shows the worst estimation failure rate.

RATS shows the worst performance for the small interval due to non-optimal parameters and explicit synchronization. For medium and large intervals, it tends to generate very small margins. Therefore, it shows a poor packet delivery ratio although it consumes less energy compared to other protocols as shown in Table 4.

Table 4.

Total packet delivery ratio when the exponentially distributed inter-packet time is used.

Average inter-packet time (min)	WideMAC	MCDR	MCDR (0.1)	MFI (1.2)	MFI (2)	RATS
1	0.9998	1	0.9828	0.9956	0.9989	0.8182
30	0.9961	1	1	0.9961	0.9846	0.9724
60	0.9643	1	0.9911	0.9911	0.9643	0.9621

Table 4 shows that WideMAC obtains the low delivery ratio for large interval. However, packets were lost only before the margin size converged, while other adaptive protocols suffered from packet drop after converged. When the average interval is 1 h, the margin size of WideMAC fluctuates as in the early stage of the experiment until the elapsed time is 30 h. This happens because WideMAC requires a large number of $(Δ t_{i}, e_{i})$ pairs in estimating the margin. If it does not have enough information for estimation, it uses a pre-defined margin size that leads to high energy consumption. However, after having a sufficient number of $(Δ t_{i}, e_{i})$ pairs, it consumes a very small amount of energy. Therefore, the initial overhead can be ignored in the overall performance. Thus, only WideMAC can show 0% estimation failure rate after the margin size is converged for all intervals as shown in Figures 9 and 10.

Conclusion

Wireless monitoring is a very important application for WSNs. However, existing WSN MAC protocols do not meet the energy needs of such an application. In this article, various clock drift characteristics were extensively analyzed through experiments and an on-demand synchronous MAC, called WideMAC, was designed to carefully exploit the real clock drift characteristics. This scheme adopts two estimation algorithms to keep track of the wakeup time of the RX node. These algorithms provide a precise estimation of both the relative clock drift and the total timing error bound, which results in significant transmission energy savings at the TX node.

The empirical results show that WideMAC reduces the energy consumption by 90%, when compared to maximum clock drift based protocols, and provides a stable and fast margin estimation, when compared to other adaptive protocols. They also confirm that WideMAC supports a wide range of duty cycles without performance degradation. Therefore, the proposed scheme is widely applicable and suitable for any application that requires very low energy consumption.

Footnotes

Academic Editor: Poh Kit Chong

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF-2014R1A1A103 8306).

References

Hatler

Chi

. Wireless sensor networks: growing markets, accelerating demand. On World, July 2005.

Heidemann

Estrin

. Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE ACM T Network 2004; 12(3): 493–506.

Van Dam

Langendoen

. An adaptive energy-efficient MAC protocol for wireless sensor networks. In: Proceedings of the ACM conference on embedded network sensor systems (Sensys), Los Angeles, CA, 5–7 November 2003, pp.171–180. New York: ACM.

Buettner

Yee

Anderson

. X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks. In: Proceedings of the ACM conference on embedded network sensor systems (Sensys), Boulder, CO, 31 October–3 November 2006, pp.307–320. New York: ACM.

Sun

Gurewitz

Johnson

. RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks. In: Proceedings of the ACM conference on embedded network sensor systems (Sensys), Raleigh, NC, 5–7 November 2008, pp.1–14. New York: ACM.

Silva

Heidemann

. Ultra-low duty cycle MAC with scheduled channel polling. In: Proceedings of the ACM conference on embedded network sensor systems (Sensys), Boulder, CO, 31 October–3 November 2006, pp.323–331. New York: ACM.

El-Hoiydi

Decotignie

. WiseMAC: an ultra low power MAC protocol for multi-hop wireless sensor networks. In: Proceedings of the ACM conference on embedded network sensor systems (Sensys), 5–7 November 2003, pp.675–690. New York: ACM.

HSW

Nguyen

Walrand

. Practical synchronization techniques for multi-channel MAC. In: Proceedings of the 12th annual international conference on Mobile computing and networking, Los Angeles, CA, 24–29 September 2006, pp.134–145. New York: ACM.

Power consumption by GPS receivers, http://mygeologypage.ucdavis.edu/gps/MISC/power.html

10.

Huang

Yun

Zhong

. PSR: practical synchronous rendezvous in low-duty-cycle wireless networks. In: Proceedings of the INFOCOM, Turin, 14–19 April 2013, pp.2661–2669. New York: IEEE.

11.

Maróti

Kusy

Simon

. The flooding time synchronization protocol. In: Proceedings of the ACM conference on embedded network sensor systems (Sensys), Baltimore, MD, 3–5 November 2004, pp.39–49. New York: ACM.

12.

Dai

Han

. TSync: a lightweight bidirectional time synchronization service for wireless sensor networks. ACM SIGMOBILE Mob Comput Commun Rev 2004; 8(1): 125–139.

13.

Chaudhari

Serpedin

. Clock offset and skew estimation in wireless sensor networks with known deterministic delays and exponential nondeterministic delays. In: Proceedings of the third international conference on digital telecommunications(ICDT ’08), Bucharest, 29 June–5 July 2008, pp.37–40. New York: IEEE.

14.

Tang

Sun

Gurewitz

. PW-MAC: an energy-efficient predictive-wakeup MAC protocol for wireless sensor networks. In: Proceedings of the INFOCOM, Shanghai, China, 10–15 April 2011, pp.1305–1313. New York: IEEE.

15.

Liu

Fan

Sinha

. CMAC: an energy efficient MAC layer protocol using convergent packet forwarding for wireless sensor networks. ACM T Sens Netw 2009; 5(4): 1–34.

16.

omer

Blum

Meier

. Time synchronization and calibration in wireless sensor networks. In: Stojmenovic

(ed.) Handbook of sensor networks: algorithms and architectures. Hoboken, NJ: John Wiley & Sons, 2005, pp.199–237.

17.

Press

Teukolsky

Vetterling

. Numerical recipes in C. 2nd ed.Cambridge: Cambridge University Press, 1992.

18.

Mills

. Improved algorithms for synchronizing computer network clocks. IEEE ACM T Network 1995; 3(3): 245–254.

19.

C-MAC microTechnology.HC49/4H SMX crystals datasheet, 2004, http://uk.rs-online.com/web/p/crystal-units/4789662/

20.

ECS, Inc. International. ECS-3x8/2x6/1x5 tunig fork crystals datasheet, http://www.ecsxtal.com/store/pdf/ECS-3x8.pdf

21.

Elson

Girod

Estrin

. Fine-grained network time synchronization using reference broadcasts. SIGOPS Oper Syst Rev 2002; 36(SI): 147–163.

22.

TelosB, http://www.memsic.com/userfiles/files/Datasheets/WSN/telosb_datasheet.pdf

23.

MICAz, http://www.memsic.com/userfiles/files/Datasheets/WSN/micaz_datasheet-t.pdf

24.

HMote, http://www.hybus.net

25.

Sundararaman

Buy

Kshemkalyani

. Clock synchronization for wireless sensor networks: a survey. Elsevier Ad-Hoc Netw 2005; 3(3): 281–323.

26.

TinyOS Forum, http://www.tinyos.net

27.

Ganeriwal

Tsigkogiannis

Shim

. Estimating clock uncertainty for efficient duty-cycling in sensor networks. IEEE ACM T Network 2009; 17(3): 843–856.