Range extension cooperative MAC to attack energy hole in duty-cycled multi-hop WSNs

Abstract

Effective techniques for extending lifetime in multi-hop wireless sensor networks include duty cycling and, more recently introduced, cooperative transmission (CT) range extension. However, a scalable MAC protocol has not been presented that combines both. An On-demand Scheduling Cooperative MAC protocol (OSC-MAC) is proposed to address the energy hole problem in multi-hop wireless sensor networks (WSNs). By combining an on-demand strategy and sensor cooperation intended to extend range, OSC-MAC tackles the spatio-temporal challenges for performing CT in multi-hop WSNs: cooperating nodes are neither on the same duty cycle nor are they necessarily in the same collision domain. We use orthogonal and pipelined duty-cycle scheduling, in part to reduce traffic contention, and devise a reservation-based wake-up scheme to bring cooperating nodes into temporary synchrony to support CT range extension. The efficacy of OSC-MAC is demonstrated using extensive NS-2 simulations for different network scenarios without and with mobility. Compared with existing MAC protocols, simulation results show that while we explicitly account for the overhead of CT and practical failures of control packets in dense traffic, OSC-MAC still gives 80–200 % lifetime improvement.

1 Introduction

Wireless sensor networks (WSNs) usually consist of a vast number of integrated system-on-chip devices (nodes) that are powered by batteries and equipped with less capable micro-controllers and limited memory. These nodes make local measurements and send the data through multiple hops to the remote gateway, i.e., the sink node. It is desirable that the energy constrained network operates unattended for a long period of time, especially when those networks are deployed in human-prohibited areas where replacing nodes is infeasible or too costly. Therefore, the network lifetime is among the paramount considerations when designing medium access control (MAC) protocols. Various delay-tolerant data gathering applications favor long lifetime including, among others, environmental monitoring, structural health monitoring, and animal habitat tracking [1]. While effective techniques for extending lifetime in multi-hop wireless sensor networks include duty-cycling [49] and, more recently introduced, range extension supported by cooperative transmission (CT) [18, 19, 28], only the conference version of this paper [27] provides a scalable and efficient MAC protocol that combines both. Harvesting the combined benefits of duty cycling and CT range extension is not a trivial design, because three or more nodes participate in each CT link and the cooperating nodes are neither on the same duty cycle nor are they necessarily in the same collision domain as a result of the extended transmission range. This also means more MAC overhead must be occurring in terms of cooperating nodes selection and wakeup rendezvous scheduling, both of which are dynamic processes. Therefore, the motivation for the work reported here is to present a MAC design and to determine if the extra overhead outweights the range extension benefit. While [27] shows the preliminary results on the lifetime benefit from combining the two strategies, this paper extends it with more implementation details, more scenarios and more types of results.

The network lifetime is often defined as the number of packets delivered to the sink when the first node depletes its energy [18, 19, 21]. The energy-hole is a known problem that limits the lifetime of multi-hop WSNs, in which an intermediate node that is carrying heavier traffic has to spend more energy and consequently exhausts earlier [23]. If this node is the only node connecting two parts of a network, then a network partition or energy hole occurs when the node dies (such as Node P in Fig. 1). Generally, the nodes near the sink are heavily burdened and are prone to creating energy holes. Consequently, energies outside of the holes are trapped and unused because the packet-forwarding nodes surrounding the sink are dead. While duty cycling is an efficient method to save nodes’ energy, it cannot solve the energy hole problem due to its inability to balance energy in a multi-hop network. The cooperative transmission when used for range extension purpose has been analytically shown to solve the energy hole [19, 28].

On the other hand, from energy consumption perspective, besides data transmission and reception, the major sources of energy consumption inherent to MACs include idle listening, overhearing, and collision [49]. Idle listening means that nodes keep listening to the channel while there are no incoming packets at all. Notably, idle listening is disastrous in WSNs because nodes in this mode consume the same magnitude of power as in receiving [49]. Overhearing means that nodes decode packets that are destined to others. Collisions result in corrupted packets and the following MAC layer retransmissions consume extra energy. From the network perspective, while these factors reduce an individual node’s lifetime, the network lifetime is more critically limited by the energy holes formed around the sink leaving unused energy outside of the holes [23].

Fig. 1

A small network illustrating the energy hole and a VMISO link. Conventionally, Node P must forward Node C’s packets. With VMISO, Nodes S and C can bypass the bottleneck node P and transmit directly to the sink

In general, network longevity can be achieved from two strategies: energy conservation and energy balancing, which are individual node oriented and network oriented, respectively. Duty-cycling MAC, e.g., [49], is a popular energy conserving mechanism that alternates each node between active and sleep modes by turning the radio on and off periodically. Nodes are allowed to transmit and receive data in the active period, and are mandated to turn off the radio in the sleep period to save energy substantially. These protocols dramatically reduce the periods of idle listening and overhearing. In particular, DW-MAC[44] has been shown to have superior delivery ratio, delay, and energy consumption. Unfortunately, DW-MAC and the others do not solve the energy hole problem.

Among methods of attacking the energy-hole, a particularly promising energy-balancing method is cooperative transmission (CT) range extension. CT is a mixture of physical layer combining techniques and communication protocols that allows spatially separated single-antenna nodes to collaborate to form a virtual multiple-input-single-output (VMISO) array [22, 28], as shown in Fig. 1. The source node first multi-casts a packet to the neighboring cooperators, which then send the packet in orthogonal diversity channels [2, 9] or concurrently in concert with coding [46]. Ranked by the synchronization requirements at the cooperative node, there are three types of CT schemes: coherent beamforming (CB), time division CT (TDCT), and concurrent CT (CCT), a detailed discussion was presented in [28]. In this paper, we assume time-division CT [22, 29], in which the cooperators forward the multi-casted packet to the destination in orthogonal time slots. Compared with CB, TDCT has less synchronization and channel state information requirement; compared with CCT, TDCT has shorter interference range because cooperating nodes do not fire at the same time, and it saves the CT initiator from transmitting for the second time, at the cost of longer time to complete CT transmission. The VMISO array provides array gain (simple summing of transmit powers) and spatial diversity gain in fading channels (the improved likelihood that at least one of the fading channels to the destination has a high gain). Consequently, the destination receiver obtains a significant signal-to-noise ratio (SNR) advantage through physical layer combining. The SNR advantage can be used to increase transmission rate, reduce transmission power or achieve a longer transmission range. The range extension property of CT has been shown, in concert with routing, to correct the energy imbalance by using the long-range VMISO transmission to bypass the bottleneck nodes and allow those nodes to sleep. This CT energy-balancing approach has been shown to extend network lifetime by factors of two or more, as in [18, 19]. In particular, in the Residual-Energy-Activated Cooperative Transmission (REACT) protocol introduced in [18], a node on the primary route, instead of forwarding the packet to the next-hop node that has lower residual energy, can transmit to the sink directly by recruiting cooperators, and therefore the bottleneck nodes in the network are protected. However, the increased control overhead from CT was not considered in [18, 19]. Also, [18, 19] did not consider how CT could be merged with duty cycling, which is a popular way to conserve energy and extend the life of a WSN. From the MAC perspective, conducting CT in a multi-hop asynchronous duty-cycling network is extremely challenging, because the source, the cooperators and the destination need to reach consensus about a wake-up period, during which CT can be performed.

We note that the incremental redundancy (IR) form of CT, in which cooperation is requested only when the conventional transmission fails, does not apply to the range extension scenario. By definition, the receiver in our CT link is out of single-input-single-output (SISO) decoding range. We also note that physical layer CT requires the receiver to store samples of the payload waveform and coherently combine with samples of payload from other packet copies. This requires preamble and synchronization algorithm designed to work at extremely low SNR [29, 30], which is feasible in today’s commercially available and small form factor software defined radios (SDRs), e.g., the Ettus USRP B200mini [4]. Such an SDR is feasible as a sink node; fortunately, a sizeable CT lifetime benefit is obtainable when the sink is the only CT destination [18, 19]. However, in this paper, we scale to the large multi-hop networks, so we allow sensor nodes to also be CT receivers. The necessary extra memory and processing capability may become reasonable as the cost of integrated circuits continues to decrease.

Fig. 2

The architecture of the system design

Motivated by the analysis in [18, 19], the objective of this paper is to present a novel Medium Access Control (MAC) protocol that supports both CT range extension and duty cycling, and properly accounts for the control packet overhead. The architecture of the entire system design is depicted in Fig. 2. The proposed protocol solves the energy hole problem with design features that both conserve and balance energy. We summarize the main contributions of this paper, as follows:

• A novel and scalable solution to enable CT in a duty-cycled multi-hop WSN. Unlike most papers on MAC that focus on either an energy-conserving or an energy-balancing strategy, we propose an On-demand Scheduling Cooperative MAC (OSC-MAC) that incorporates both heuristics in the MAC design, and is not based on an existing commercial protocol (e.g., 802.11 nor 802.15.x).

• A simple and effective duty cycle scheduling algorithm, embedded in the MAC, which enables on-demand CT and provides the wake-up rendezvous for the cooperators.

• A seamless contention and transmission scheduling scheme, at the frame level, to support both direct transmission and CT range extension. The CT range extension scheduling and on-demand wakeup scheme have relaxed the spatial-tempo assumptions made in existing CT protocols.

• An implementation of the protocol in NS2 and extensive simulations that show significantly longer lifetime compared with other efficient MAC protocols, under different network scenarios.

The rest of this paper is structured as follows. Section 2 describes related works. Section 3 describes the network model and the duty cycle scheduling. Section 4 presents different aspects of the proposed OSC-MAC. In Sect. 5, the system performance is evaluated and compared with other MAC protocols using NS-2 simulation, for different network scenarios. The concluding remark is given in Sect. 6.

2 Related work

In this section, we describe related works towards lifetime enhancement in the areas of duty-cycling protocols, cooperative protocols, and existing energy hole attacks, and highlight the relevant challenges and considerations in designing a very efficient MAC.

Duty-cycling Protocols Duty cycling has been widely investigated as an essential component in MAC protocols to save energy [7, 37, 44, 45, 49]. By cycling between active and dormant modes, nodes reduce idle-listening and thus conserve energy substantially in sleep periods. Duty cycle MAC protocols fall mainly into two categories: synchronous and asynchronous protocols. Synchronous protocols such as S-MAC [49] and DW-MAC [44] align all nodes to wake up and sleep at the same time. However, network-wide synchronization requires extra energy to maintain and introduces more packet collisions. Asynchronized approaches including B-MAC [37] and X-MAC [7] allow nodes to maintain active-sleep schedules independently; these protocols rely on low power listening (LPL) that requires appending a long preamble before each data transmission, which is energy inefficient. Moreover, the channel utilization efficiency is low, because the channel is excessively occupied by the preamble preventing neighboring nodes to transmit. RI-MAC [45] switches the burden of the sender to the the receiver, which transmits a packet upon waking up, to poll the senders. However, senders still need to stay awake to listen for the polling packet. Except for DW-MAC, none of these works explore reservation-based data transmission to reduce idle listening. Furthermore, although duty-cycling techniques save energy for individual nodes, none of the the reported studies solves the “energy hole” problem due to their inability to balance energy in MHWSNs.

Cooperative Protocols Cooperative transmission (CT) has been deeply explored in the physical layer [22, 34, 38, 42]. In addition to the physical layer, there is also increasing interest in Layers 2 and 3 supporting CT [5, 18, 19, 36, 41, 53, 54], and some cross-layer design [13]. Nevertheless, four limitations exist in the literature. (1) Though many authors have considered how the SNR gains may benefit a wireless network by increasing link reliability [36] and reducing transmit power [41], relatively less attention has been given to the energy-balancing benefits of CT range extension, and thus none of them alleviates the energy hole. (2) While the improvements in single-hop networks have been studied through diverse examples [36, 54], the studies on cooperative multi-hop networks that provide explicit MAC signaling procedure are limited. (3) None of these considers duty cycling, and thus the lifetime issue is not addressed. Although some work such as LC-MAC [53] demonstrates energy efficiency of CT, without duty-cycling, no noticeable lifetime benefits were shown. (4) All these protocols make the spatial assumption that the source, cooperators and the destination are located in one collision domain (i.e. within single-input-single-output (SISO) transmission range of each other), and the temporal assumption that all nodes stay active when CT is performed [22]. The spatial assumption is not generally true for multi-hop networks, and the temporal assumption is not necessary because an efficient scheduling scheme can be designed. In this paper, we have addressed these four limitations.

SCT-MAC [26], CDC-MAC [16] and ACT-MAC [14] were our efforts to design a MAC bringing CT into the duty cycle context. In SCT-MAC, to protect the one-hop parent, a node transmits directly to its two-hop parent by incorporating one cooperator. The disadvantage of SCT-MAC is that it requires some nodes to maintain many schedules, producing more than necessary wakeup periods to support CT. CDC-MAC and ACT-MAC addresses only a two-hop network and lacks scalability to the multi-hop network. In [27], we have given the basic description of our protocol and some first simulation results to show the efficacy of the protocol in random network. In this paper, we present more implementation related details and extended simulation experiments that clearly show the significantly improved lifetime in random networks, and grid networks, in static, as well as in mobile sink scenarios.

Solutions attacking energy-hole Existing solutions for the energy-hole focus mainly on the network-layer protocols, such as (1) the non-uniform node deployment [25, 32, 51] and (2) the mobile relay/sink strategy [24, 35, 48]. In the non-uniform deployment scheme, additional nodes are placed in the area close to the sink, and routes are selected so that nodes can evenly consume the energy. The downside of this strategy is that it can drastically increase the cost of deployment because of the required additional nodes [51]. On the other hand, when the number of available nodes in the network is fixed, the non-uniform strategy decreases the sensing/coverage area of the network because the extra nodes deployed near the sink node could have been used to cover other areas. The mobile-relay strategy determines the movement of mobile nodes and routes (to send packets via mobile node) to mitigate the energy-hole problem. The moving sink can distribute the role of the bottleneck nodes and even out the load over time, especially in many-to-one data collection applications. Theoretical analyses in [33, 47] have shown in routing layer with simplified system model that the sink mobility can improve the lifetime of a WSN. There are two mobility regimes, fast mobility regime and slow mobility regime, depending on the relationship between the sink’s moving speed and the tolerable delay of the data delivery. In the fast mobility regime, such as in [8, 20], with mechanical movement of the sink the speed produces tolerable data delivery delay trading for reduced nodes’ energy consumption. In the slow mobility regime, the trace of the moving sink takes a discrete form and it consists of anchor points between which the sink moves and at which the sink pauses. It is known that routing protocols that support mobile sink to collect data in WSNs incur higher protocol overhead. In [35], a practical routing protocol is proposed that assumes controllable and predictable mobility, longer pausing time at anchor points than actual moving time, to limit the protocol overhead, and it shows the improved lifetime through sink mobility. In [39], the lifetime benefit is shown through a mobile sink strategy in IPv6-based WSNs, especially in the context of the IETF RPL protocol [50]. However, as noted in [48], mobile relays/sink may be hard to operate in certain environments such as under a bridge, on water, and in an unpaved area. To show the lifetime benefits of our proposed protocol on top of sink mobility, we also show the network performance when the sink is mobile in Sect. 6.3 assuming the slow mobility regime. Last, a common issue is that these routing strategies look at only transceiving, while overlooking the energy consumption in idle listening and overhearing whose magnitude is comparable to transceiving [49].

3 Network model and duty cycle design

In this section, following Fig. 2 we present the network model and duty cycle design under which the range extension cooperative MAC will operate. This serves as the basis for the detailed MAC signaling design in Sect. 5.

Fig. 3

Examples of the scheduling instance of random and grid topologies ($N_s = 12$). a Random topology, b grid topology. The asterisk represents the sink node

A data gathering tree is formed by routing protocols. Such protocols include the emerging IPv6 Routing Protocol for Low Power and Lossy Networks (RPL) [50], which is currently under development by the Internet Engineering Task Force (IETF) for low power and lossy networks. In such a converge-cast tree, it is customary to call nodes that have no children the leaf nodes, and nodes that have at least one child the parent nodes. Ideally, a cross-layer design that incorporates routing, MAC, CT, and duty cycle might have better yields, as we mathematically analyzed in [31]. While such a cross-layer optimization is theoretically possible, it trades off practicality with certain high-level assumptions that fail to capture low-level MAC operations. In this paper, with the mind of driving a readily implementable MAC protocol for sensor nodes equipped with a single antenna, we consider explicitly packet-level MAC signaling procedure (Sect. 5.4), scheduling conflict detection (Sect. 5.5), and practical CT handshake failures (Sect. 6.1.4), and hence a joint optimization in concert with routing is beyond the scope of this paper. Instead, same as in DW-MAC [44], we opt to build our design on top of a primary route¹. Although routes may change during network operation, we assume a primary route that is durable for a time that is long compared with a frame or several frames, with a tree-based routing structure. In Sect. 6.2, we show the benefits of our design observed in different routing structures.

In order to achieve CT range extension, the radio of the source node, cooperators and the destination must be on at the time when the source firstly multi-casts the packet to the cooperators that are within one SISO-hop of the source. Note that the destination, which may be two SISO-hops from the source, needs to be on during each transmission so that it can sample and store the signal received from the source, to combine later with copies received from the cooperators. To satisfy this extremely challenging wakeup condition in an asynchronous network, we present an explicit requesting/signaling procedure to bring the cooperating nodes into temporary synchrony in an on-demand fashion. To support this signaling procedure, specifically, each node shall maintain a regular schedule (RS) of its own to receive incoming packets, and wake up only on demand to support CT, which we call temporary schedules (TS). More details about this part of MAC signaling are described in Sect. 5.

One duty-cycle is composed of the scheduling period, the data period, and the sleep period. The duty-cycle repeats in time. Within a duty cycle, we define the concatenation of the scheduling period and the data period as a superframe. Further, we define the length of a duty-cycle to be $N_s$ superframes, i.e., the length of the sleep period is $N_s-1$ superframes. A pictorial representation of super frame is shown in Fig. 6(b), (c). Within a superframe, the scheduling period is used for cooperation wakeup request and transmission reservation. The non-CT data transmissions and CT data transmissions are performed in the data period according to the scheduling information obtained in the preceding scheduling period. Depending on the traffic demand, not every portion of the data period will be scheduled for data transmission. How the data transmission is scheduled will be described in Sect. 5.4. Nodes sleep during the entire sleep period, and also sleep in the “unused” portion of the data period. The regular schedules are achieved using the same greedy algorithm and broadcast procedure at network initialization phase as SCT-MAC, as in “Algorithm 1”.

The network initialization is triggered at the sink. Each node around the sink first retrieves the time slots that have already been occupied by interfering parent nodes, and then selects a free slot based on the collected information. After that, a beacon is transmitted for the scheduling procedure to propagate over the rest of the network. Note that before the network initialization phase, nodes have not yet learned their schedules and thus are all active, so a primary route can be established using any conventional routing protocol with the MAC layer enabling carrier sense multiple access (CSMA). CSMA has already been used in the scheduling handshake during the scheduling period in our protocol, see Sect. 5.4. After the network initialization, nodes have learned their schedules and will act according to our proposed protocol. The resulting schedules in a path from a low-level node towards the sink are sorted in a cyclic increasing (because the duty-cycle repeats) order within $[1, \, N_s]$. Figure 3 shows an instance of the scheduling algorithm for a random topology of 50 nodes and a deterministic $7 \times 7$ grid topology with $N_s = 12$. The number on reach node represents its regular schedule (see Sect. 5.1 for more description). Note that a leaf node follows its parent’s schedule. The pipelined feature is similar to P-MAC [11]. Unlike [11], the schedules of interfering nodes appear orthogonal in time (i.e., the superframe of a node lies in the sleep period of its interfering nodes, so interfering nodes do not regularly wake up in the same time slot). Here we assume the interference range is twice of SISO transmission range, which has been validated by measurements [3]. The introduced orthogonality guarantees that different traffic flows in the network are collision-free. Same as DW-MAC [44], a separate network time synchronization protocol is assumed to achieve the “coarse” synchronization. Note that a node does not need to wake up at the exact time of a schedule, instead, it needs only wake up a little earlier with a small margin time.

4 VMISO physical layer combining model

For the physical layer in Fig. 2, we adopt the physical-layer model of [17]. In Rayleigh fading (i.e., non-line-of-sight environment), when spatially separated cooperators transmit encoded symbols across space and time, the receiver that executes diversity combining can decode the symbols with much lower bit error rate (BER) than conventional single-input-single-output (SISO) transmission. This diversity gain leads to a smaller average SNR requirement, i.e., the average $E_b/N_o$ requirement, where $E_b$ refers to the average bit energy and $N_o$ is the power spectral density of white noise. For instance, for a target average BER of $10^{-3}$, the average $E_b/N_o$ required in a Rayleigh fading for uncoded BPSK modulation is 25 dB [2, 15], whereas with a $2 \times 1$ virtual MISO link, the required average $E_b/N_o$ is only 10 dB. In this example, the array gain, which is the increase in average received SNR, is $10{\text{log}}_{10}(2) = 3$ dB; and the diversity gain, which is the reduction in the extra transmit power (i.e., fade margin) allocated to overcome the worst case fades, is 12 dB ($25\,\text {dB}-10\,\text {dB}-3\,\text {dB}$). For a given target BER, the reduced SNR requirement can be translated into a longer transmission range. According to the standard power law model for path loss [17, 38], the range extension factor can be obtained as $f_{ext}(N_c) =10^{(10{\text{log}}_{10}(N_c)+D)/10\gamma }$, where $N_c$ is the number of diversity channels or cooperators in VMISO, D is the diversity gain, and $\gamma$ is the path loss exponent. Also, as in [17], we assume the diversity gain depends only on the number of cooperating nodes and not on the physical location of these nodes (as long as they are all within the SISO range of each other). In our NS-2 simulations, we employ the widely used Two-ray ground reflection model [38] for all studied protocols, with $\gamma = 4$. The cooperating nodes use the same maximum power as in SISO, and we do not exploit power control. We use a lower diversity gain $D=10$ dB to leave some margin for other channel effects. With one cooperator ($N_c = 2$), $\gamma = 4$ and $D=10$ dB, the range extension factor is over two. In other words, a 2-node VMISO transmitter can reach a destination two SISO-lengths away, as in Fig. 1. Although more cooperators lead to longer range extension, in our protocol design we consider only two SISO-hops range extension; three-hop or more will incur much more complexity in the protocol design. An analytical study of cooperating node selection, which does not limit to 2-hop range extension and which performs in the routing layer analysis, can be found in [19].

5 On-demand scheduling cooperative (OSC) MAC

In this section, with the foundation in Sect. 3 and following Fig. 2, we present various aspects of OSC-MAC that supports CT in duty cycle context. In particular, we first discuss the different types of schedules, the physical layer combining model for CT, and cooperator selection, in Sects. 5.1, 4, and 5.2, respectively. Then we present the detailed MAC signaling procedure in Sects. 5.3, 5.4 and 5.5.

5.1 Overview

In OSC-MAC, each node maintains one regular schedule (RS) and decides temporary schedules (TSs) on the fly. The TSs are activated on demand to support CT and deactivated afterwards. It is assumed that each node is aware of the RS of its one-hop neighbors and the RS of its two-hop parent. Because every node can be a receiver, it always keeps awake during its own RS to receive either CT data or non-CT data. When a node decides to transmit a non-CT data packet directly to its parent, it wakes up in its parent’s RS and proceeds to transmit using the procedure in Sect. 5.4. On the other hand, when the source node decides to do CT, as shown in Fig. 4, it tries to filter the candidate cooperators applying the criteria in Sect. 5.2 . Here we use the same simple criterion for CT decision as in REACT, which compares the source node’s residual energy $E_i$ and its parent’s energy $E_p$. If $E_p > E_i$, a non-CT transmission will be performed. Otherwise, a CT decision will be made to protect the parent. Then the cooperating nodes will decide TSs on the fly, during which they will wake up. A distributed algorithm is provided in Sect. 5.3 to achieve this. To support the scheduling in OSC-MAC, three classes of active schedule are defined, and the responsibility of the corresponding nodes are listed as follows:

• RS (Class 1): Set by each node to listen for incoming packets.

• TS-2 (Class 2): Set by source node that initializes CT, to perform wakeup request to cooperators.

• TS-3 (Class 3): Set by cooperating nodes as wakeup rendezvous, to perform CT.

Fig. 4

CT decision/wake-up scheduling at the source node

5.2 Cooperator selection

In our previous work, SCT-MAC, a cooperator must be the sibling of the source node or the sibling of the parent due to the scheduling design. One disadvantage of such selection constraint is that in some form of grid topologies, such as non-diagonal grid as will be discussed later, there lack the available cooperators and thus CT will not be applicable. In contrast, OSC-MAC allows each node to choose the cooperator from its one-hop neighborhood, which may have a distinct schedule. In this study, we consider selecting the helper that has: (1) the maximum residual energy, and (2) energy that is higher than the source node. Energy information of neighbors can be obtained by inserting a common information-sharing broadcast slot periodically and by overhearing control packets in the scheduling period. Energy information of the parent node can also be obtained by letting the parent transmit a beacon during the first slot in the parent’s RS. Packets transmitted during the broadcast period can also be used to readjust regular schedules and update neighbor information, to accommodate possible topology variations.

5.3 On-demand wakeup for CT

In the case of CT, we present the on-demand wakeup scheme to bring cooperating nodes into temporary synchrony, by managing temporary schedules (TSs) on the fly. Specifically, we require that CT should be performed during the two-hop parent’s regular schedule (RS), which would be the schedule had a two-hop non-CT been performed. Thus, the objective is to have all the cooperating nodes locked onto this CT rendezvous.

Fig. 5

On-demand wakeup scheme. (The CT TX Phase is zoomed in Fig. 6(b))

Because nodes may have distinct RSs, an explicit wakeup request procedure is proposed to set up the wakeup rendezvous for the cooperating nodes. As in Fig. 5, the source Node i sets $Class \, 2$ TSs (TS-2) to temporarily wake up in each of the cooperator’s and the one-hop parent’s RS $s_j$. Note that each $s_j$ is a concatenation of a scheduling period and a data period. The source node will send a wakeup request packet to the cooperating nodes to indicate the expected slot of CT rendezvous $\beta$, and wait for the wakeup replies. Depending on Slot $\alpha$ when the packet is generated and the schedule of the cooperating nodes, a method is provided for the cooperating nodes to self-decide when to wake up to perform CT. Basically, the source node that initiates CT when receiving a packet from the upper layer calculates the start time of future slot that CT can be formed in $T_{max}$ by considering the cooperative nodes’ individual RSs, and embeds this information in the wakeup request packet; then, the cooperating node j when receiving the wakeup request calculates the wakeup time on the fly, by first calculating an intermediate variable according to

$$\begin{aligned} T_{Wake, j} = T_{StartS,j} + d * T_{SF}, \end{aligned}$$

(1)

where $d = (\beta - s_j) \bmod Ns$, $T_{SF}$ is the superframe length, and $T_{StartS,j}$ is the start time of the current slot. And then $T_{Wake, j}$ is compared with $T_{max}$. This is necessary because a cooperative node’s RS may appear before or after the two-hop parent’s RS.

This coordination process falls in the non-CT case of the MAC procedure, as will be described in Sect. 5.4, i.e., with the scheduling period used for exchanging wakeup request/reply. More details of the on-demand wakeup scheme are provided in "Algorithm 2".

Fig. 6

MAC Signaling: seamless scheduling and transmission for non-CT and CT packets. a Part of a large network, b one-to-one mapping for Non-CT transmission, c cooperative range extension case (CT TX Phase)

5.4 Seamless scheduling and transmission for CT and non-CT

In this subsection, we provide the details for the seamless scheduling and transmission for non-CT during the parent’s schedule, and for CT during the CT rendezvous as in Fig. 6. There is one-to-one mapping between the scheduling handshake and the scheduled data transmission in the data period. Wakeup time slots in the data period are scheduled in sequence and are compact, see Eq. (2). The CT case, in Fig. 6(b), is the zoomed-in process in “CT TX Phase” of Fig. 5. Same as SCT-MAC, the scheduling period is used for control handshakes to reserve the data transmission in the following data period. Nodes also sleep during the unreserved portion of the data period. A receiver will keep track of the numbers of non-CT and CT transmissions that have already been granted by itself and thus been reserved in its own data period.

Next we will discuss the seamless scheduling and transmission process, using Fig. 6(a) as an example, wherein Node S is the source, C is the cooperator, P is the parent, and D is the two-hop parent. The process applies to any large network.

1. Non-CT case During the scheduling period, after random backoff such as CSMA, the source node S transmits a scheduling frame (SF) to the destination P (one-hop parent), which will reply with a SF, as in Fig. 6(b). The replying SF includes the numbers of non-CTs ($N_{non{\text {-}}CT}$) and CTs ($N_{CT}$) that have already been reserved in the data period. Both Node S and Node P determine the corresponding wakeup time instance $T_{Wakeup}$ from the beginning of the subsequent data period, according to

$$\begin{aligned} T_{Wakeup} = T_{non{\text {-}}CT} \times N_{non{\text {-}}CT} + T_{CT} \times N_{CT}, \end{aligned}$$

(2)

where $T_{non{\text {-}}CT}$ and $T_{CT}$ represent channel occupancy time of non-CT packet and CT packet, and thus $T_{non{\text {-}}CT} = T_{Pkt} + T_{Ack} + SIFS$ and $T_{CT} = 2T_{Pkt} + 2T_{Ack} + 3SIFS$. It is easy to see that for a particular receiver, no schedule conflicts will occur during the subsequent data period, and thus data collision from different contending transmitters is avoided. After waking up at the scheduled time $T_{Wakeup}$ in the data period, Node S transmits the data to Node P, which after decoding the packets, replies an ACK. Then both Node S and Node P sleep to avoid idle listening. Note that $N_{non{\text {-}}CT}$ or $N_{CT}$ increments according to whether the scheduled transmission is a non-CT packet or a CT packet.

2. CT case The CT transmission is performed in the RS of the two-hop parent. This CT TX phase is agreed upon by the on-demand wakeup scheme discussed in Sect. 5.3.

The source S As shown in Fig. 6(c), when Node S decides to hop over its one-hop parent using cooperative transmission, it initializes CT by firstly sending a cooperative schedule frame (CSF) destined to the two-hop parent D. The CSF also specifies the ID of the selected helper (such as C). Many measures can be applied to select the best helper such as best link quality, minimum distance, minimum load, etc, or a combination of those metrics. Inspired by REACT [18], we use a simple helper selection criterion by considering residual energy.

The cooperator C If Node C receives the CSF from Node D, it enlists itself as the potential helper, if it is available, and sends a CSF the same as the incoming CSF to S to indicate its availability to help. Note that the CSF frames from S and C are transmitted in two orthogonal time slots, and can not be decoded separately by D, which is the two-hop parent; however, they can be decoded jointly at D using Maximum Ratio Combining (MRC) [38]; D then replies a SF (including $N_{CT}$ and $N_{non{\text {-}}CT}$) to S and C in a two-hop manner, through the intermediate node P. Also, D schedules a wakeup time instance $T_{Wakeup}$ in the Data period according to Eq. (2), to receive the cooperative data transmission from Nodes S and C. If S and C receive the SF (D’s reply) forwarded by P, then they schedule the same wakeup time, to proceed to the data transmission in the data period. As shown in Fig. 6(c), at time $T_{Wakeup}$, Node S sends the data packet in the first time slot, which is decoded and forwarded by Node C in the next time slot. The two-hop parent D, upon receiving the two independent copies of packets, decodes the original packet using MRC. Then it sends an ACK back to S in two hops through P. Note that S should sleep immediately after sending its packet, to avoid overhearing the retransmission from the cooperator, and wake up again right before the expected ACK which is forwarded by P on behalf of D. Also, the cooperator should also sleep after relaying the packet, and it does not need to wakeup to receive the ACK.

The one-hop parent P (to be protected) As stated above, the role of Node P is to forward the control packets sent from Node D, such as SF and ACK. The SF is a grant for the CT request initiated by Node S. The ACK is an acknowledgement of the correct reception of the cooperative data transmission from Nodes S and C. Both of the CSF frames from S and C can be overheard by their one-hop parent P; if C decodes either of the CSF frames it then anticipates to receive the SF replied from Node D. If SF is received, P forwards it to S and C. Also, P schedules a wakeup time at $T_P = T_{Wakeup}+2T_{Pkt}+SIFS$ to receive a possible ACK from D which is destined to Node S. Note that the goal of REACT is to hop-over the energy constrained node (e.g., Node P), however, completely avoiding the usage of Node P requires either higher transmit power or cooperative transmission at D’s side, which adds extra energy cost (near the sink) with an increasing complexity of the protocol. Therefore, we let Node P forward only two control packets that are much shorter than the data packet, and allow P to sleep otherwise.

OSC-MAC does not require stringent synchronization, as nodes can wake up a little earlier (in ms) than their expected wakeup time to accommodate the clock drift. In the NS-2 implementation, we explicitly left a 2 ms margin. Also, although we have shown the non-CT and CT contention and scheduling only for one source node, OSC-MAC allows multiple data transmissions from different senders in the data period. According to Eq. (2), multiple contending nodes contend to execute a control handshake in the scheduling period with their intended (common) receiver and to schedule their data transmissions in the subsequent data periods. Retransmissions for CT and non-CT include the retries of SF handshake and DATA transmission. The former case occurs in the scheduling period, which can hold several retries until reaching the boundary of the period. However, if the SF handshake succeeds but the scheduled data transmission fails in the data period, the node has to wait until the next cycle.

5.5 Schedule conflict detection and avoidance

As stated above, a receiver does not have a schedule conflict in its data period because it schedules the data transmissions. However, under some conditions the sender may incur a conflict in the scheduled transmission, especially when the sender is both a data source and a cooperator, in the same schedule shared by different receivers. We illustrate this in Fig. 6(a), where Node D is the two-hop parent of Node S, and Node A is the two-hop parent of Node C. Assume D and A (separated over twice the SISO range) happen to have the same RS. In the first control handshake, C acts as the CT initializer to A and receives ($N_{CT}=1$, $N_{non{\text {-}}CT}=0$), from A. In the second control handshake (later), S initializes CT to D and enlists C as the cooperator, which then receives ($N_{CT}=1$, $N_{non{\text {-}}CT}=0$), from D. Then at the same wakeup time $T_{Wakeup}$, C must listen to S to receive and transmit its own CT packet, resulting a schedule conflict. To preclude this situation, after a new control handshake, a node checks whether new scheduled wakeup (start time and duration) conflicts with the existing ones; if a conflict is detected, then it sends a ConFlict SF to notify the partners to cancel their scheduled wakeup in the data period to avoid unsuccessful data transmission.

6 Simulation evaluation

In this section, we present detailed performance results for the proposed OSC-MAC protocol, which has been implemented (with 10K+ lines of C++ codes) in NS-2.29. We consider random networks, grid networks, and networks with a mobile sink. We compare with DW-MAC, which has proven scalability using NS2 simulation tool and the same assumptions as in our design. Same as SCT-MAC and DW-MAC, OSC-MAC is analyzed using the Random Correlated Event (RCE) traffic model to simulate burst traffic triggered by spatially correlated events, which are commonly observed in detection, monitoring and tracking applications. The event location (x, y) is randomly selected every 200 s. Each node within the circle of radius R centered at the event location (x, y) generates a packet to the sink. The radius R is gradually increased to input more traffic into the network. The main simulation parameters are listed in Table 1. The SISO transmission range is 250 m and the carrier sensing range is 550 m, same as used in previous works, e.g., [44, 49] and the reference therein. Although different devices would have different transmission range and carrier sensing range, the similar ratio between them is observed by measurements [3]. The energy consumption parameters are typical values for Mica2 radios [52] and are used in [44, 49] (one can choose different energy consumption parameters for other sensor chips of interest with our protocol). The transition time of Mica2 radio between active and dormant modes is about 2.47ms, however the transition energy is unavailable from the data sheet. As OSC-MAC requires more state transitions of the radio, to not favor OSC-MAC, we give transition energy the same value as in transmission, although the former normally consumes much lower energy than transmission and reception. The initial energy of node is set to 50J and the sink has no energy constraint. We compare different metrics in grid topologies. The performance of OSC-MAC is compared with the cooperative protocol SCT-MAC [26] and the non-cooperative duty-cycle protocol DW-MAC [44].

Table 1 Simulation parameters

6.1 Random networks

We consider 100 random topologies, where 50 nodes are randomly distributed in an area of 1000 m * 1000 m. The sink is located in the center. For example, Fig. 3(a) shows one random network. For each simulation run, the topology is constructed with shortest path (Dijkstra’s) algorithm, however one can use other algorithms as well such as those discussed in Sect. 6.2.

Fig. 7

Cumulative distribution function (CDF) of the performance of random networks ($R=300$ m): network lifetime, delivery ratio, energy consumption per packet, and end-to-end delay. a Network lifetime, b delivery ratio, c energy consumption per packet, d end-to-end delay

6.1.1 Network lifetime evaluation

Figure 7 depicts the cumulative distribution functions (CDF) (across all simulations) of the network performance of OSC-MAC, SCT-MAC and DW-MAC when the event sensing range R is 300 m, in terms of network lifetime, delivery ratio, energy consumption per packet, and end-to-end delay, respectively. Figure 7(a) shows that OSC-MAC significantly outperforms the others in the network lifetime. The improvements attribute to the duty cycle design for reducing contention and congestion, and to the scheduled transmissions for avoiding overhearing and idle listening, as well as to CT range extension for protecting bottleneck nodes. Figure 7(b) indicates that while all the protocols exhibit high delivery ratio for most random topologies, DW-MAC has relatively lower one (from the long tail) in occasional cases due to its network-wide synchronization. Figure 7(c) shows the energy efficiency in terms of energy consumption per packet. While DW-MAC has much less energy efficiency than OSC-MAC, SCT-MAC is only slightly worse, although the difference in lifetime is noticeable. Figure 7(d) indicates that the end-to-end delay of OSC-MAC and SCT-MAC is worse than DW-MAC, this is because nodes under DW-MAC have synchronized schedules (i.e., they wakeup and sleep at the same time) while the schedules in OSC-MAC and SCT-MAC are pipelined and orthogonal. The latter does not only reduce collision when traffic demand arises, but also aid in scheduling cooperative transmission. As a result, the wakeup time of a cooperating node is reduced because it is scheduled. We also note that OSC-MAC’s delay performance is similar to SCT-MAC, even though SCT-MAC’s CT TX rendezvous is fixed and OSC-MAC’s CT TX rendezvous is determined on the fly. This demonstrated the effectiveness of the on-demand wakeup scheme for CT as described in Sect. 5.3.

To have a quantitative sense, Fig. 8 shows average performance. Figure 8(a) presents the growth trend of the average lifetime as the event sensing range R increases, with 95% confidence intervals (they are very small). When the first node dies, some fraction of total energy consumed by the network can be attributed to transmission and another fraction can be attributed to idle listening. We note that the fraction attributed to packet transmission increases with event sensing radius (because the packet transmission rate increases) and the fraction due to idle listening will decrease. This explains why the total packets sent at first node death increases with increasing event radius. In Fig. 8(a), we see OSC-MAC is superior, e.g., it increases the mean network lifetime by 77.8% compared with SCT-MAC when $R = 400$ m. This is because OSC-MAC, in spite of CT, spends less time in idle listening. And when traffic increases, the staggered duty-cycles reduce the collisions when many nodes contend for the medium. Figure 8(b) shows in very small scale the average delivery ratio of the three protocols, with 95% confidence intervals. In Fig. 8(b), only DW-MAC has large intervals, and OSC-MAC has very small confidence intervals. This actually supports that OSC-MAC has very small deviation in the performance. Together with Fig. 8(a), (c) suggests that energy efficiency is only an indirect indicator of network lifetime, because the magnitude of lifetime difference between protocols cannot be projected from the difference in their energy efficiency. Figure 8(d) shows the end-to-end delay of the three protocols, with 95% confidence intervals. For the same reasoning explained for Fig. 7(d), OSC-MAC has larger delay compared with DW-MAC, but even with its on-demand wakeup, still manages to maintain a delay level that is comparable with SCT-MAC.

Fig. 8

Average performance of random networks (varied R): network lifetime, delivery ratio, energy consumption per packet, and end-to-end delay. a Network lifetime, b delivery ratio, c energy consumption per packet, d end-to-end delay

6.1.2 Residual energy profile

In this subsection, we show the residual energy profile of all the nodes in the network when the first node exhausts, for event sensing ranges of 100 and 300 m. Lower ID indicates shortest distance to the sink. Figure 9(a) suggests that SCT-MAC leaves more energy around the sink unused. This is because the scheduling in SCT-MAC requires a node to wakeup in the parent’s and two-hop parent’s schedule to support CT, and thus nodes farther away from the sink maintain up to three wakeup schedules consuming more energy than necessary in idle listening. From Fig. 9(a), DW-MAC obtains a balanced residual energy profile, however, much of the energy is consumed in idle listening in the scheduling period and channel contention because of the synchronized schedules of all the nodes. The reason that the energy-hole is not apparent in DW-MAC is because for bottleneck nodes the energy consumption in idle listening dominates the energy consumption in the extra wakeup (to forward packets) in the data period. OSC-MAC achieves more balanced energy than SCT-MAC because nodes are required to maintain one regular schedule and manage temporary schedules on the fly, and therefore the periods spent in idle listening for possible CT traffic are reduced. However, the energy in OSC-MAC is less balanced than DW-MAC at the nodes near the sink. Also OSC-MAC still leaves a significant amount of average residual energy at first node death, suggesting more efficient protocols may be possible. The imbalance is due to the limitation of the two-hop range extension in our scheme, and also the practical failures of CT handshake as will be discussed later. With longer range extension, the energy could be more balanced as shown in REACT [18]. However, longer range extension imposes more challenges in control packets exchange in a duty cycled network.

Fig. 9

Other observations of random networks (varied R): residual energy profile, saturation lifetime, and CT cancellation frequency. a Residual energy versus node ID, b saturation lifetime, c CT cancellation frequency

6.1.3 Saturation lifetime

To quantify the influence of CT in the OSC-MAC protocol, we increase the sensing range from 100 to 1200 m and compare the lifetime (with 95% confidence intervals) obtained in OSC-MAC with CT enabled and CT disabled cases, in Fig. 9(b). “CT disabled” means that the duty cycle assignment as in Section II is held, however every packet is forced to follow non-CT transmission. With sensing range of 1200 m almost every node would transmit periodically, and hence there are 50 flows converging to the sink making the network heavily loaded. As in Fig. 9(b), after an increasing trend before the sensing range reaches 600 m, the lifetime gradually decreases until arriving at a plateau. A similar trend of throughput as traffic increases is also observed by Bianchi [6] in the WIFI network. Similarly, we define the plateau as the saturation network lifetime. Figure 9(b) shows that CT increases the saturation lifetime about 30% compared with non-CT even when both cases are under carefully designed duty cycle schedules and when the communication overhead of CT is considered. We observe that the 30% improvement from CT is much less than was observed in [19], because as we will discuss, idle listening consumes a large part of the energy budget, but the model in [19] did not include idle listening.

6.1.4 Practical behavior due to CT handshake

Ideally, CT should be conducted whenever a CT decision is made (according to some criterion). However, this is not always possible due to contention and collisions. We observe that CT is not always being performed as desired. Figure 9(c) plots the CT cancellation frequency, for every source node with event sensing ranges of 200 and 600 m. Note that the first-hop nodes to the sink have no need to initialize CT. We observe that when the traffic load in the network is heavy, CT cancellations occur much more frequently. This takes place for two reasons: (1) the SF handshake during CT rendezvous for scheduling CT data transmission suffers more collisions when the network is heavily loaded. The collisions come from the contention with both non-CT an CT handshakes; (2) as we implement an explicit wakeup request/reply procedure to reach CT rendezvous, this wakeup procedure could fail more frequently due to contentions. Consequently, the CT attempt must be canceled and subsequently the non-CT is pursued.

Fig. 10

Non-diagonal Case: Routes constructed by different routing algorithms for a $7 \times 7$ grid topology. a SP (Dijkstra’s), b breadth-first search, c load balancing, d balance factor

6.2 Grid networks

Grid networks have also been seen in several monitoring applications [1, 12], and several other authors have studied WSNs with grid topologies [40, 43, 44]. A realistic deployment of a WSN is not necessarily completely random, and the sensors can be deployed along parallel paths and at periodic intervals, by (un)manned aerial and terrestrial vehicles [43]. Also, the grid network allows us to investigate the lifetime under more controlled conditions. With such a deployment control, we consider two types of grid networks. The first type is the non-diagonal grid network, wherein if using SISO transmission nodes can only communicate directly with nodes that are adjacent to them vertically or horizontally. The second type is the diagonal grid network, wherein nodes can also communicate directly with nodes that are in the diagonal. These two types of topologies have been considered in the literature and in real applications. Moreover, we remark that SCT-MAC cannot be applied to the non-diagonal networks, because due to its schedules SCT-MAC must select a one-hop neighbor that is also a sibling as the cooperator, which is infeasible in the non-diagonal networks. In contrast, the proposed on-demand protocol OSC-MAC can be applied to both the non-diagonal networks and the diagonal networks, because the on-demand feature allows it to select cooperators from one-hop neighbors that are not necessarily sibling nodes.

Fig. 11

Non-diagonal grid network (if using SISO transmission nodes can only communicate directly with nodes that are adjacent to them vertically or horizontally). a Network lifetime, b delivery ratio, c energy consumption per packet, d residual energy profile

In this subsection, we evaluate the performance of our proposed MAC protocol under different routing schemes. In particular, different routing protocols cause different loads for the bottleneck nodes, and load balancing schemes, from the routing perspective, have been studied by other authors as a method to balance energy consumption. This motivates us to evaluate the robustness and performance of OSC-MAC operating under different routing schemes, and to gain some insights of difference when the MAC layer energy consumptions are also captured, beneath the routing layer that typically captures only transmission and receiving. In the non-diagonal grid topology, because the source’s cooperator is not in the transmission range of the source’s one-hop parent, we slightly adjust the transmission of control packet as follows. After receiving the replying SF from the parent, the source node forwards it to the cooperator.

Three routing schemes differing in the load balance factor are considered: the shortest path (SP), breadth-first search (BFS), and node-centric (NC) load balancing routing [10]. The balance factor, $\theta$, is defined as the fairness index among loads in the top subtrees $\theta = \frac{\left( \sum ^n_{k=1}W_{k}\right) ^2}{n\sum ^n_{k=1}W^2_{k}}$ [10], where $W_k$ is the aggregate load of each branch, and n is the number of branches. When the weights in each branch converge to the same value, $\theta$ tends to be 1 indicating more balanced load. When the imbalance is large, the balance factor approaches 1 / n.

Figure 10 shows the primary routes constructed from SP, BFS and NC load-balancing algorithms for a $7 \times 7$ grid network, and the load balance factors of non-CT networks with different scales. Illustration for the routes in the diagonal is omitted due to space limit. For example, for the former network, the balancing factor of SP, BFS and NC are 0.81, 0.78, and 1, respectively. Note that for diagonal network, the SP and the BFS produce the same routes. We evaluate $7 \times 7$ grid networks in the simulations, while similar trends are observed for networks of other scales. As in the random networks, RCE traffic is generated in the deployment area of the grid networks.

Fig. 12

Diagonal grid network (nodes can also communicate directly with nodes that are in the diagonal). a Network lifetime, b delivery ratio, c energy consumption per packet, d residual energy profile

6.2.1 Network lifetime evaluation

Figure 11 shows the network performance of OSC-MAC, compared with DW-MAC, for the $7 \times 7$ non-diagonal network, with 95% confidence intervals in Fig. 11(a)–(c). SCT-MAC is not shown in the figure, because SCT-MAC cannot be applied to non-diagonal networks due to its limitation in the cooperator selection. For the same reasons as discussed above, OSC-MAC offers better performance with same trends observed as in the random networks. Figure 11(a) shows that OSC-MAC outperforms DW-MAC significantly in lifetime, e.g., providing 8–9 times of lifetime of DW-MAC when $R=400$ m. OSC-MAC provides higher average delivery ratio (nearly 100%) with much smaller confidence intervals, as in Fig. 11(b). Figure 11(c) demonstrates the high energy efficiency of OSC-MAC, i.e., large gaps with DW-MAC in terms of energy consumption per packet. The gaps in energy efficiency reduce as event sensing range increases, but still render large absolute value. Additionally, we observe that node-centric (NC) load balancing routing favors the lifetime of OSC-MAC. Also, for DW-MAC, although the energy efficiency of BFS and NC routing are slightly higher than shortest path, the lifetime of DW-MAC does not benefit noticeably from NC or BFS.

Figure 12 shows, for the $7 \times 7$ diagonal network, the network performance of OSC-MAC, compared with both SCT-MAC and DW-MAC, with 95% confidence intervals in Fig. 12(a)–(c). SCT-MAC can be applied because the diagonal network can satisfy its cooperator selection criterion. For all the three MAC protocols, the delivery ratios are higher than their counterparts in the non-diagonal network as in Fig. 12(b), because routes in the non-diagonal network are more restricted as nodes cannot communicate with a diagonal node. SCT-MAC provides a slightly better delivery ratio than OSC-MAC, at the cost of much less lifetime than OSC-MAC (e.g., OSC-MAC offers over 150% lifetime of SCT-MAC at $R=400$ m), as we can see in Fig. 12(a).

Another observation from Fig. 12(a) is that while NC routing benefits the lifetime of OSC-MAC compared with shortest path, DW-MAC gains the greatest lifetime from the shortest path among other routing schemes. This observation suggests that a seemingly “advantageous” routing algorithm does not necessarily lead to better lifetime, mainly because the MAC layer captures all complex aspects of energy consumption including collision, overhearing and idle listening besides tranceiving, while a routing scheme assessment typically examines only transmission and reception energy. Figure 12(c) shows, for each MAC protocol, indistinguishable energy efficiency when different routing protocols are used, although the lifetimes are indeed different, as in Fig. 12(a). This fact suggests that energy efficiency and lifetime should be jointly considered to quantitatively evaluate a WSN.

6.2.2 Residual energy

The residual energy profiles when the first node dies are shown in Figs. 11(d) and 12(d), for non-diagonal and for diagonal networks, respectively. Lower ID indicates shorter distance to the sink. In Fig. 11(d), both OSC-MAC and DW-MAC have balanced residual energy, for both $R=100$ m and $R=400$ m. We also observe that OSC-MAC has lower residual energy than DW-MAC, indicating better energy utilization towards increasing lifetime. In Fig. 12(d), SCT-MAC is also considered for the diagonal network. While OSC-MAC and DW-MAC show relatively balanced residual energy, SCT-MAC leaves significant amount of energy near the sink, for the same reason for random network that nodes farther from the sink maintain more schedules than necessary. A common observation from Figs. 11(d) and 12(d) is that the curve for OSC-MAC has some fluctuation around the sink, indicating certain nodes around the sink are not perfectly protected. The reason coincides with our previous observation that, first, CT may be canceled due to collisions and retries; and second, only two-hop CT is conducted due to practical considerations.

6.3 The influence of mobile sink

It is uncommon for the nodes in a wireless sensor network to be mobile, however, it is possible that the sink node(s) can be mobile [35]. Among others, one purpose for the sink to be mobile could be towards balancing traffic load among nodes. Thus, it is important to evaluate how different MAC protocols benefits in the context of mobile sink. If and how the MAC adapts to the mobility of the sink is out of scope of this paper, and in one sense the follow results represent the worse case wherein the MAC is not adaptive. In the mobile scenarios, the sink node can visit the deployment area following a certain geographical pattern. In this subsection, again we consider the $7 \times 7$ diagonal grid network, where a sink node travels clock-wisely along the borders of the network, in such a way that only the nearest node can directly communicate with it at a time. Therefore, the traffic is more congested than the cases in last section where sink locates in the middle. There are 24 positions on the border of the network that the sink can visit, and we determine the level of mobility in terms of the move period of the sink (traveling time between two positions). Between the times that the sink moves, nodes follow the schedules as discussed before; when sink moves to a new position, the same network process as in the network initialization phase is performed to establish new schedules. The shortest path routing algorithm is used. Along with mobile scenarios, we also compare with the static case that the sink resides still in the “corner” of the network.

Fig. 13

Mobile Sink Scenario. a Network life versus event sensing range, b delivery ratio versus event sensing range, c network lifetime versus mobility level

Figure 13(a) presents the lifetimes of OSC-MAC, SCT-MAC and DW-MAC when the sink node is static or mobile, with 95% confidence intervals. In the mobile scenario, the sink traveling period is 600 s. Again, the lifetime increases as the event sensing range increases. In the static case, at event sensing range of 400 m, OSC-MAC achieves 182.3% longer lifetime over SCT-MAC, which achieves 71.6% longer lifetime over DW-MAC. As expected, the mobility of sink releases the burden of the bottle-neck node in the static case, and thus increase the lifetime; however, the increasing rates are different for the three protocols. For example, at event sensing range of 400 m, with mobility the lifetime of OSC-MAC increases (over the static case) by 73.6%, SCT-MAC by 44.3%, and DW-MAC by 25.1%. Another observation that confirms the higher energy efficiency of OSC-MAC and SCT-MAC is that while OSC-MAC and SCT-MAC benefit from the mobility also in the case of smaller (than 400 m) event sensing ranges, DW-MAC improves by the minimum amount.

Figure 13(b) shows the packet delivery ratios versus event sensing ranges. For example, at event sensing range of 400 m, OSC-MAC achieves the highest delivery ratio (between 92.4 and 95%) among the three protocols, even in the mobile scenario. The delivery ratio of DW-MAC reduces quickly as event sensing range increases, and drops to around 80% at $R=400$ m, due to its requirement of network-wide schedule synchronization and its lower ability to handle congested traffic.

In our last experiment, we examine the reaction of the proposed OSC-MAC protocol when the sink has different levels of mobility. We run the previous $7 \times 7$ diagonal grid scenario with event sensing range of 200 m. The network lifetime versus the mobility level (sink move period) is depicted in Fig. 13(c), where larger horizontal axis indicates higher mobility level. We observe that the lifetime reaches the peak value of about 5600 packets when the mobility level is around 400 s. As the mobility level decreases, the lifetime reduces towards converging to the static network case. On the other hand, when the mobility level is higher, the network reacts to network schedule changes more frequently and incurs more packet retransmissions. Thus, as we can see from the figure, as the mobility level increases away from the peak point, the lifetime starts to degrade and reaches about 5000 packets when the mobility level is 100 s. However, the reduced lifetime due to high mobility still stay almost 90% of its peak value.

7 Conclusions

In this work, we propose a scalable and efficient on-demand duty cycling MAC (OSC-MAC) that reduces idle listening and supports cooperative transmission range extension to solve the energy hole problem in multi-hop WSNs. By combining an on-demand schedule and CT range extension, we have addressed the spatio-temporal challenges for performing CT in multi-hop duty cycled WSNs, to offer significantly longer lifetime. Even with control packet energy accounted for, OSC-MAC still produces about 80–200% longer lifetime in various network environments with a static, as well as mobile sink. OSC-MAC results in an energy-conserving and energy-balancing integrated scheme that can be implemented with sensor nodes equipped with a single antenna.