Sage Journals: Discover world-class research

Abstract

Broadcast is widely used in applications in wireless sensor networks (WSNs). In the last decade, the broadcast problem in WSNs has been well studied. However, few of existing broadcasting strategies have considered the scenarios with sleeping schedules, which have been emerging as a prevalent energy-saving method for WSNs. In WSNs with sleeping schedule, each node switches on and off periodically, rendering the broadcast problem more difficult. To handle the periodical sleep issue, we focus on designing effective sleeping schedule-aware broadcast algorithms. We practically propose SALB, a sleeping schedule-aware local broadcast algorithm. In SALB, a typical local algorithm for constructing connected dominating set is employed to form the broadcast backbone. To guarantee proper transmission of broadcast messages, a sleep-aware forwarding mechanism is implemented. Moreover, heuristic strategies are used to decrease the number of transmissions and the broadcast latency. Theoretical analysis shows that the number of transmissions for SALB is within 4(min(Δ, $| T |) + c$ ) (c is constant) is constant) times of the optimal value. And the broadcast latency of SALB is within 4 $| T | + 1$ times of the optimal value (Δ is the maximum degree in the network, $| T |$ is the scheduling period length). The performance of SALB is evaluated via simulations.

1. Introduction

Energy is regarded as scarce resource in wireless sensor networks (WSNs). It is shown that most energy is wasted in sensor node's idle listening. To handle this issue, sleeping schedule has been proposed to preserve energy in WSNs. With sleeping schedule, each node is switched on and off periodically. Nodes turn on to detect object and receive and forward data and then turn to sleep to save energy. As a simple yet efficient method, sleeping scheduling has been widely used in WSN applications like environment monitoring and object tracking applications [1].

Broadcast is a fundamental operation in WSNs for routing discovery, information dissemination, and so on [2]. Naive broadcast methods such as flooding always lead to massive redundancy and intolerable latency, wasting the energy dramatically [2]. In order to design energy-efficient broadcast algorithms, a lot of effort has been devoted to reduce data transmission and broadcast latency. For instance, many MCDS-based approaches are proposed to minimize transmission redundancy [3–7]. And lots of coloring-based collision-avoiding approaches are used to reduce latency [8–10].

In this paper, we focus on the sleeping schedule-ware broadcast problem in WSNs, which is quite different from that in traditional WSNs. In traditional WSNs, each node is assumed to be nonsleeping. Based on the broadcast nature of wireless medium, a node can deliver one broadcast message to all its neighbors by one transmission. While in the WSNs with sleeping schedule, each node can only receive messages when it is active, so not all neighbors of a senor node can receive the broadcast message by one transmission. This difference renders the broadcast problem more difficult in such situations. Existing broadcast algorithms did not consider the sleeping schedule issues and thus are not suitable.

To solve the sleeping schedule-aware broadcast problem, we practically propose a local algorithm in this paper, namely, the sleeping schedule-aware local broadcast (SALB) algorithm. In SALB, we first use a typical local MCDS construction algorithm to form a virtual broadcast backbone. With this virtual backbone, we design an active slot-based forwarding mechanism for each node, which guarantees the success of broadcast and can help reduce transmission redundancy and latency. The numbers of transmissions for SALB are within $4 (\min (Δ, | T |) + c)$ (c is constant) times of the optimal value. And the broadcast latency of SALB is within $4 | T | + 1$ times of the minimum value. (Δ is the maximum degree in the network; $| T |$ is the scheduling period length).

The rest of this paper is organized as follows. We review the related work in Section 2 and present the models and assumption in Section 3. SALB is proposed in Section 4. We evaluate its performance in Section 5 and discuss the tradeoff between the number of transmissions and the broadcast latency in Section 6. In Section 7, we conclude this paper.

2. Related Work

Data-transmission issues in duty-cycled WANETs have recently attracted much of researchers' attention. Dousse et al. [11] established a bound on the transmission latency of sensor networks with uncoordinated schedule. Lu et al. proved the NP-hardness of minimizing end-to-end communication delay in low-duty-cycle sensor networks in [12]. Cao et al. proposed the pipeline forwarding pattern for sensor networks with a sleeping schedule to decrease the delay [13]. Keshavarzian et al. analyzed the delay of several known wake-up patterns and proposed a new multiparent scheduling pattern for sensor networks in [14]. Gu and He proposed a dynamic data forwarding scheme for extremely low-duty-cycle sensor networks based on the expected latency and reliability model [15]. However, these works mainly focus on the latency issue caused by the sleep schedule, and none of them refer to the broadcast problem.

Since broadcast plays an important role in WSNs, a lot of research work has been done on this area. The simplest approach for broadcast is blind flooding, where each node is obligated to forward a packet upon receiving it for the first time. However, it has been shown that blind flooding can lead to serious redundancy and collisions, a situation known as broadcast storm [2]. Therefore, great effort has been made by improving the flooding approach to reduce broadcast redundancy and collisions, as well as broadcast latency. For example, [2, 16] proposed probabilistic forwarding methods to avoid massive redundant transmissions. Based on the construction of virtual broadcast backbone and broadcasting along the backbone, [3–7] proposed different technologies to reduce broadcast redundancy. Specifically, much recent research has been done to minimize the broadcast transmissions and minimize the broadcast latency based on different network models. Generally, both the minimum transmission broadcast problem and the minimum latency broadcast problem are NP-hard, and a lot of efficient algorithms have been proposed [3–10].

Recently, some researches focusing on the sleeping schedule-aware broadcast problem have emerged. Wang et al. discussed the broadcast problem in duty-cycle sensor networks in [17]. Hong et al. proposed a series of work on the minimum-redundancy broadcast problem for duty-cycle wireless ad hoc networks [18, 19]. The other topic of minimum-latency broadcast problem has been investigated in [20, 21]. However, none of them proposes a local algorithm for sensor network considering both transmission and latency issues of broadcast.

3. Model and Assumption

We assume that n sensors node are deployed in a two-dimensional plane with equal maximum transmitting range of one unit. The network can be modeled as a connected UDG $G (V, E)$ , where V is the set of nodes and E is the edge set. An edge ${u, v} \in E$ if and only if the distance between nodes u and v is within each other's communication range. Unlike the literature focusing on tuning sleeping schedule [12–14], we follow the assumption in [11], where each node determines its sleeping schedule completely and uncoordinatedly. We assume that the scheduling period T is divided into $| T |$ time-slots with fixed and equal length, denoted by $1, 2, \dots, | T |$ accordingly. We also assume that each node v randomly chooses an active time-slot ${SL}_{a} (v) \in T$ independently. Each time-slot is assumed to be long enough for sending or receiving a data packet [12]. The contention and collision issues of wireless channel are assumed to process by the MAC protocols, for example, S-MAC [22]. Therefore we will not need to consider the impact of factors like channel conflict. Following the models in [12, 15], we assume that a node can wake up to transmit at any time, but can receive only in its active time-slot. The set of sending time-slots of node v is ${SL}_{s} (v)$ . The global time synchronization is guaranteed by protocols like flooding time synchronization protocol (FTSP) [23].

The notations used in this paper are listed in Table 1.

Table 1

Notations.

n	The number of nodes in the network
T	The period of sleeping schedule
Δ	The maximum degree of nodes in the network
$N (v)$	The set of neighbors of node v
$D (v)$	The set of 1-hop neighbor dominators of node v
$D_{2} (v)$	The set of 2-hop neighbor dominators of node v
${SL}_{a} (v)$	The active time-slot of node v

3.1. Problem Formulation

We consider the multisource broadcast in this paper, in which each node in the network is possible to broadcast the data packets to all the other nodes. In the general WSN, with the benefit of broadcasting nature of wireless media, each node can broadcast the data packets to all neighbor nodes with only one transmission. As a result, the objective of traditional broadcasting algorithm is to determine the forwarding nodes in broadcasting. Each forwarding node retransmits the data packets once after receiving them to complete the broadcasting process. However, considering the effect of sleeping schedule, the active time-slots of nodes are always different. A node cannot guarantee that all its neighbors are able to receive the data package successfully with one transmission. As a result, the broadcasting problem becomes different from the traditional WSN and thus is needed to be redefined. We define a broadcast backbone $B (G)$ on $G (V, E)$ as a subset of V, where the broadcast backbone is the set of forwarding nodes. The data package will be forwarded in the network on the broadcasting backbone. Also we define a broadcast schedule BS(B) as the set of ${SL}_{s} (v)$ in which v is the node in broadcasting backbone B. We also define ${Cov}_{i} (v)$ as the set of neighbor nodes in which node v covers at time-slot i. The sleeping schedule-aware broadcast problem can be described as follows.

Definition 1 (the sleeping schedule-aware broadcast (SA-broadcast)).

Given a WSN with sleeping schedule which is modeled as a $UDG G (V, E)$ , find a connected backbone $B (G)$ for broadcast and a corresponding broadcast schedule $BS (B)$ so that $⋃_{v \in B}^{} (⋃_{i \in S L_{s} (v)}^{} CO V_{i} (v)) = V$ .

Different broadcasting algorithms have different broadcast backbones and broadcast schedules, which determine the number of transmissions and the broadcast latency. Finally we present a useful definition.

Definition 2 (inversion).

Given a data transmitting node sequence $v_{0}, v_{1}, \dots, v_{k}, v_{k + 1}, \dots$ , for two adjacent transmitting and receiving nodes $v_{k}$ and $v_{k + 1}$ , if ${SL}_{a} (v_{k}) \leq {SL}_{a} (v_{k + 1})$ holds, we define it as an inversion.

When node a receives a data package at time-slot ${SL}_{a} (a)$ and sends data to node c through node b, if there is no inversion, node c can receive the data package within the minimum latency: ${SL}_{a} (c) - S L_{a} (a)$ time-slots. If an inversion exists, for example, ${SL}_{a} (a) \geq S L_{a} (b)$ , the latency of node c receiving the data package will be increased by $| T |$ time-slots. If the inversion appears k times, the time-slots will be increased by $k | T |$ . Therefore, to decrease the latency, we usually try to avoid the appearance of inversions in the sequence of forwarding nodes from the source node to the destination node.

4. Local Algorithm for SA-Broadcast Problem

In this section, we introduce the details of the proposed SALB algorithm. The design of SALB algorithm consists of two parts: construction of a broadcast backbone and the active time-slot-oriented forwarding mechanism.

4.1. Construction of Broadcast Backbone

Among existing broadcast backbone constructing algorithms, the MCDS is proved to have the minimum forwarding nodes, performing well in reducing both transmission and latency [24]. Therefore, we would like to use a MCDS as the broadcast backbone. Many MCDS constructing algorithms have been proposed so far, like [25–28]. Among them, a widely used local algorithm for mobile ad hoc networks proposed by Alzoubi et al. in [25] has constant message complexity and constant approximation ratio. Therefore, we employ this algorithm with some modification here to construct the broadcast backbone of SALB.

As described in [7, 25], the construction of broadcast backbone can consist of two phases: dominator election and dominator connection. The elected dominators and connectors form a connected dominating set (CDS), acting as the broadcast backbone. In the construction phase of the broadcast backbone, we assume that all nodes are in the active state. After the construction, each node will become a dominator, a dominate, or a connector. According to [25], there must be a dominator within three hop distance of any dominator. During the broadcast, each dominator delivers message to its neighbors, and connectors relay messages among dominators. Each node maintains a forwarding node list FWD_LIST, containing the IDs of destination nodes and their active time-slots. The FWD_LIST will be used in designing the forwarding mechanism.

4.1.1. Electing Dominators

We assume that each node in the network obtains all its 1-hop neighbors' ID and active time-slot by exchanging beacon messages. To reduce inversions in the broadcast process, we would like to make the active time-slot of each dominator smaller than its neighbors'. Let $N (v)$ be the set of node v's 1-hop neighbors. We define a metric η to represent the possibility of no inversion happening while a node u transmits to its neighbors:

\begin{matrix} η = \frac{| {u | u \in N (v), S L_{a} (v) < S L_{a} (u)} |}{| N (v) |} . \end{matrix}

(1)

In electing the dominators, nodes with larger value of η will be more likely to win. Initially, all nodes are in the “Blank” state. Then the modified election procedure based on that in [25] with metric η is as follows.

(i)

A Blank node becomes a dominator if it has the largest η among all its Blank 1-hop neighbors and then broadcast a message IamDominator (ID, i) with its ID and active time-lot i (ID is used to break the tie).

(ii)

A Blank node becomes a dominator if there are no Blank nodes nor dominators in its 1-hop neighbors (knowledge from the received IamDominatee message) and then broadcast the IamDominator(ID, i) message.

(iii)

A Blank node becomes a dominatee if it receives a IamDominator message and then broadcast message IamDominatee(ID, i).

After election, if a dominator u has the largest ID among all its dominatee v's neighbor dominators, it stores the ID and the schedule of active time-slots of v in its FWD_LIST. Each dominatee then records all of its dominator's IDs and active time-slots in its FWD_LIST.

4.1.2. Connecting Dominators

Here we present the modified dominator connecting phase based on the algorithm from [25]. For each dominator, we call the connecting nodes adjacent to its 2-hop dominators the 1-hop connectors and the connecting nodes 2-hop away from its 3-hop dominators the 2-hop connectors.

First we connect dominators with its 2-hop neighbor dominators. After the election phase, each dominatee v broadcasts an ANNOUNCE message containing the IDs of nodes in $D (v)$ . Hence, each dominator u is able to obtain the set of all its 2-hop dominators $D_{2} (u)$ , and the dominatees through which the nodes in $D_{2} (u)$ can be reached. Dominator u keeps this information in a list HOP1_LIST ${v, D (v) \cup D_{2} (u)}$ and uses a working set $T e m p = D_{2} (u)$ for the 1-hop connector selection. Dominator u then broadcasts an ANNOUNCE message containing the IDs of all nodes in $D_{2} (u)$ , so that all dominatees in $N (u)$ can obtain the information of u's 2-hop neighbor dominators. If dominator u does not have the largest ID among its dominatee v's 1-hop dominators, v will not be chosen as u's 1-hop connectors. And the item of v will be removed from u's HOP1_LIST, and all v's 1-hop dominators will be removed from $T e m p$ . After the removal, dominator u chooses 1-hop connectors for its 2-hop dominators using the procedure shown in Algorithm 1.

Algorithm 1

// Choosing 1-hop connectors for dominator

(1) If $T e m p = = \emptyset$ then stop, else execute the following steps;

(2) For each dominatee in HOP1_LIST, compute the number n of dominators in $T e m p$ ;

(3) Choose the dominatee with largest n as 1-hop connector;

(4) Remove the item of v from the HOP1_LIST, and remove all dominators connected by

v from $T e m p$ , go to Step 1.

After choosing its 1-hop connector, each dominator puts the ID of its 1-hop connectors and the connected dominators in $T e m p$ in a HOP1_CONN message and then broadcast. If a dominatee receives a HOP1_CONN message and finds its ID included, it marks itself as a connector and adds the ID and active time-slots of nodes attached in the HOP1_CONN message into its FWD_LIST.

Next we connect the dominator and its 3-hop neighbor dominators. After a dominator u broadcasts the IDs of all nodes in $D_{2} (u)$ with the ANNOUNCE message, its dominatee v is able to gather the information of 2-hop neighbor dominators of u. Then v puts its 1-hop and 2-hop dominators' information in an ANNOUNCE message and broadcast. When dominator u receives all the ANNOUNCE messages broadcasted by its dominatees, it is able to know the 2-hop neighbor dominators $D_{2} (w)$ for each dominator w in $D_{2} (u)$ , which will then be stored in a list. When a dominatee v receives the ANNOUNCE message from other dominatees, it checks their dominators. If there is some dominatee x which does not share 1-hop dominators with v, v will mark x as a special dominatee and mark its corresponding dominators as special dominators. Dominatee v maintains a list SPCON_LIST to store the special dominators for each special dominatees and then broadcast them with an ANNOUNCE message.

When dominator u receives the ANNOUNCE from dominatee v, it checks the special dominators inside the message. If there are nodes in the message which are neither 2-hop neighbor dominators of u nor the special dominators for the 2-hop neighbor dominators of any node in $D_{2} (u)$ , u will mark them as isolated dominators. If a dominatee v satisfies the following conditions: (1) there are isolated dominators marked by u in v's dominators and (2) u owns the largest ID among all isolated dominators and v's dominators [25], u will choose v as a 2-hop connector and notify v with the isolated dominators it needs to connect to. Receiving the message from u, dominatee v fetches the isolated dominators it needs to connect to and store them in $T e m p$ . After that, it finds the corresponding 1-hop connectors using the procedure shown in Algorithm 2.

Algorithm 2

// Choosing 1-hop connectors for dominatee

(1) Find $v^{'}$ from the SPCON_LIST which connects to most isolated dominators in $T e m p$ ;

(2) Mark $v^{'}$ as an 1-hop connector, and removes all nodes it connects to from $T e m p$ ;

(3) Store $v^{'}$ 's ID and active time-slot in FWD_LIST;

(4) Go to Step 1. until $T e m p = = \emptyset$ .

After that, each 2-hop connector stores the information of its isolated dominators in HOP1_CONN message and delivers the message to its 1-hop connectors. When these 1-hop connectors receive the message, they store the ID, as well as the active time-slots of the source 2-hop connectors and the isolated dominators they needs to connect to in FWD_LIST.

4.2. Active Time-Slot-Oriented Forwarding Mechanism

In a conventional WSN, broadcast can be finished if each node in the broadcast backbone forwards the packet to all its neighbor nodes only once receiving a packet. However, in a network with sleeping schedule, nodes have to forward the packet according to the schedule of active time-slots of all its receivers. Therefore, to execute the broadcast operation correctly, we have to design the forwarding mechanism for nodes in the broadcast backbone, that is, broadcast schedule. To distinguish the packets from the same source node or different source nodes, each broadcast packet includes the ID of its source node, as well as an increasing sequence number SEQ which is maintained by the source node. Based on the FWD_LIST list kept by each node, the forwarding mechanism for a node when receiving a broadcast packet is shown in Algorithm 3.

Algorithm 3

// The forwarding mechanism for node v when receiving a broadcast packet

(1) If the packet is not received for the first time, then it is just dropped and the following steps

are skipped. // According to the ID and SEQ of the packet.

(2) Let $T e m p$ be the set of nodes in the FWD_LIST excluding the one where the packet was just

from;

(3) $t = {(SL}_{a} (v) + 1) m o d | T |$ ;

(4) If $\exists u \in T e m p$ and ${SL}_{a} (u) = = t$ , then broadcast the packet at time slot t;

(5) For each node $u \in T e m p$ , if ${SL}_{a} (u) = = t$ , then delete u from $T e m p$ ;

(6) If $T e m p = = \emptyset$ , then stop forwarding; otherwise, let $t = (t + 1) m o d | T |$ and go to Step 4.

When a connector or dominator node s starts a broadcast operation, it keeps $T e m p$ as the set of all nodes in the FWD_LIST and starts the forwarding process as in step (3). If s is a dominatee, it forwards the packet to some adjacent dominator directly. From the above forwarding mechanism, we can see that nodes do not send the packet to the nodes in the FWD_LIST one by one, but forward according to their active time-slots. Therefore, the numbers of transmissions are greatly reduced because an effective transmission can cover all active neighbors in the corresponding time-slot. Meanwhile, a node starts the forwarding process once it receives a packet such that following up active neighbor nodes can receive the packet as soon as possible, reducing the broadcast latency.

5. Performance Evaluation

In this section, we first present theoretical analysis of the transmission number, broadcast latency, and the complexity of SALB. Then, we conduct simulations to evaluate the performance of SALB.

5.1. Theoretical Analysis

Since the broadcast virtual backbone of SALB is a CDS, if each node in the virtual backbone succeeds in delivering broadcast messages to its neighbor nodes, all nodes in the network are guaranteed to receive the broadcast message. Based on this fact, with the active slot-based forwarding mechanism, SALB obviously provides correct broadcasting operation. Next we give two theorems on broadcast transmission and latency of SALB.

Assuming the minimum number of transmission to complete a broadcast in the network is $R_{\min}$ , we have the following.

Theorem 3.

The numbers of transmissions of SALB are bounded by $(\min (Δ, | T | + c)) (4 R_{\min} + 1)$ , where c is constant.

Proof.

Assume that the WSN is modeled as a UDG $G (V, E)$ . According Lemma 1 in [7], the dominating set S elected in the virtual backbone's constructing phase of SALB is a maximal independent set of G. During the broadcasting of SALB, each dominator in S will transmit the message to nodes in its FWD_LIST. For each dominator u, the nodes in FWD_LIST are a subset of $N (u)$ . Since the transmission of node u is only according to the schedule of the active slots of nodes in $N (u)$ , the number of necessary transmissions is at most $\min (Δ, | T |)$ . To cover its 2-hop neighbor dominators, the 1-hop connectors of node u need at most $l_{2}$ transmission totally, where $l_{2}$ is the number of node u's 2-hop neighbor dominators. Also, the 2-hop connector of node u will need to transmit message to node u's 3-hop neighbor dominators through their 1-hop connectors, respectively. Denoting the number of node u's 3-hop neighbor dominators as $l_{3}$ , the numbers of transmissions to cover all 3-hop neighbor dominators of node u are at most $2 l_{3}$ because each 3-hop dominator connects to only one 1-hop connector in the worst case. Therefore, the numbers of transmissions M to finish the broadcast equal $| S | (\min (Δ, | T | + l_{2} + 2 l_{3}))$ .

Let the size of MCDS of G be $# MCDS$ , according to Lemma 2 in [25]; we have $| S | \leq 4 # MCDS + 1$ . And, according to Lemma 2 in [28], both $l_{2}$ and $l_{3}$ are bounded by constants in a UDG. Hence we use a constant c to denote the upper bound of $l_{2} + 2 l_{3}$ . On the other hand, in any WSN which can be modeled as a UDG, the minimum transmission $R_{\min}$ of broadcast is obviously has lower bound $# MCDS$ . Summarizing all above, we have

\begin{array}{l} M = | S | (\min (Δ, | T |) + l_{2} + 2 l_{3}) \\ \leq (\min (Δ, | T |) + c) (4 # MCDS + 1) \\ \leq (\min (Δ, | T |) + c) (4 R_{\min} + 1) . \end{array}

(2)

The theorem holds.

Theorem 3 shows that in situations with sparse node density or short sleeping scheduling period, the broadcast transmission of SALB will be closer to the optimal value.

Next we analyze the broadcast latency of SALB. Denoting the minimum broadcast latency in a WSN with sleeping schedule by $L_{\min}$ , we have the following.

Theorem 4.

The broadcast latency of SALB is bounded by $(4 | T | + 1) L_{\min}$ .

Proof.

Denote the virtual broadcast backbone constructed in SALB by B. B is a connected dominating set of the UDG G corresponding to the WSN. By adding edges connecting each dominator and its dominatees in B, we obtain a new graph $B ’$ . According to Lemma 5 in [28], the hop-distance between any two nodes u and v in $B ’$ is less or equal to three times of the minimum distance between them in G. As shown in Figure 1, assume that the path with minimum distance in G between nodes u and v is $p_{G} (u_{0}, u_{n}) = u_{0} u_{1} \cdot \cdot \cdot u_{n}$ , where $u = u_{0}, v = u_{n}$ . If $u_{i}$ is a dominator, let $d_{i}$ be its dominatee. If $u_{i}$ is a dominatee, let $d_{i} = u_{i}$ . It is obvious that there exists a path $d_{i} u_{i} u_{i + 1} d_{i + 1}$ in G. According to the connecting phase in SALB, at most two nodes are needed to connect two nodes $d_{i}$ and $d_{i + 1}$ . Therefore, nodes $u_{0}$ and $u_{n}$ can be connected with a path $p_{B^{'}} (u_{0}, u_{n}) = u_{0} d_{0} a_{0} a_{1} d_{1} a_{2} a_{3} d_{2} \cdot \cdot \cdot d_{n} u_{n}$ in graph $B^{'}$ , where $a_{0}, a_{1}, \dots$ are connecting nodes in B. If the minimum hop-distance between u and v is n in graph G, then the maximum distance between them in graph $B'$ is bounded by $3 n + 2$ .

Figure 1

Latency analysis of SALB.

Based on the above conclusion, we further analyze the broadcast latency of SALB. Assume Figure 1 describing a network with sleeping schedule, and let $p_{G} (u_{0}, u_{n})$ be the path between u and v ${(u}_{0} = u and u_{n} = v)$ with minimum latency. We also assume ${SL}_{a} (u_{0}) < S L_{a} (u_{1}) < S L_{a} (u_{2}) < \dots < S L_{a} (u_{n})$ . When $v_{0}$ receives the broadcast message at ${SL}_{a} (u_{0})$ , if each node in $p_{G} (u_{0}, u_{n})$ retransmits the broadcast message to its following neighbor along the path as long as receiving it, node $u_{n}$ is able to receive the broadcast message with the minimum latency ${SL}_{a} (u_{n}) - S L_{a} (u_{0})$ . If the broadcast message is forwarded using the mechanism in SALB along the path $p_{B^{'}} (u_{0}, u_{n})$ within the broadcast backbone B, at most $3 n + 1$ inversions will be encountered; for example, ${SL}_{a} (d_{0}) \geq S L_{a} (a_{0}) \geq S L_{a} (a_{1}) \geq S L_{a} (d_{1}) \geq \dots \geq S L_{a} (d_{n}) \geq S L_{a} (u_{n})$ . It is worth noting that $S L_{a} (u_{0}) < S L_{a} (d_{0})$ holds; otherwise, $S L_{a} (u_{0}) \geq S L_{a} (u_{n})$ , which contradicts the assumption. In this case, the transmission latency is $S L_{a} (u_{n}) - S L_{a} (u_{0}) + (3 n + 1) | T |$ . Let $L_{P_{B^{'}} (u_{0}, u_{n})}$ be the transmission latency along path $p_{B^{'}} (u_{0}, u_{n})$ using the forwarding mechanism of SALB, and let $L_{p_{G} (u_{0}, u_{n})}$ be the minimum transmission latency along path $p_{G} (u_{0}, u_{n})$ . $L_{p_{G} (u_{0}, u_{n})}$ has the minimum value of n when $S L_{a} (u_{i + 1}) = S L_{a} (u_{i}) + 1$ . Hence we have

\begin{array}{l} \frac{L_{P_{B^{'}} (u_{0}, u_{n})}}{L_{p_{G} (u_{0}, u_{n})}} \\ \leq \frac{S L_{a} (u_{n}) - S L_{a} (u_{0}) + (3 n + 1) | T |}{S L_{a} (u_{n}) - S L_{a} (u_{0})} \\ = 1 + \frac{(3 n + 1) | T |}{S L_{a} (u_{n}) - {SL}_{a} (u_{0})} \\ \leq 1 + \frac{(3 n + 1) | T |}{n} \leq 1 + 4 | T | . \end{array}

(3)

The equation holds when

n = 1

The minimum broadcast latency $L_{\min}$ in the network is actually the maximum-minimum transmission latency from the broadcast source s to each node in the network along the paths in graph G. Assume that the path in G with the latency $L_{\min}$ is $p_{G} (s, u^{'})$ . While using SALB, according to (3), the transmission latency of forwarding the broadcast message along the path $p_{B^{'}} (s, u^{'})$ in graph $B^{'}$ is less or equal to $(4 | T | + 1) L_{\min}$ . This theorem holds.

The construction of virtual broadcast backbone dominates the time and message complexities of SALB algorithm. According to [7, 25], the time and message complexities of the CDS constructing algorithm we used in forming the virtual backbone of SALB are both $O (n)$ . Therefore, the time and message complexities of SALB are both $O (n)$ , where n is the size of the WSN.

5.2. Simulation Results

We conduct simulations to evaluate the performance of SALB on a costumed simulator developed using PARSEC [29], which is a C-based distributed discrete-event simulation language. In simulations, the network is randomly deployed in a 200 m * 200 m dimension area. To maintain reasonable network connectivity, the radio radius of each node is set to 35 m, resulting in at least 0.5 nodes/100 m² and a node degree of at least 19 in the following experiments. Each node randomly chooses an active time-slot from T. All results are average of ten runs. In each run, the broadcast source node is chosen randomly.

We first observe the broadcast transmission of SALB. In this simulation, we compared SALB with the modified classical tree-based broadcast scheme [30], namely the Tree-algorithm. The Tree-algorithm can be stated as follows: generate a spanning tree of the network G rooted in the source node s and the broadcast finishes when each node on this tree sends message to all its children according to their active time-slots. Obviously total transmission of Tree-algorithm is exactly $n - 1$ . We let $| T | = 20$ to observe the impact of network size on the broadcast transmission. As the network size is scaling up, the transmission of both Tree-algorithm and SALB increases (Figure 2). When the network size is relatively small (e.g., $n < 300$ ), the transmission of SALB is a bit more than that of Tree-algorithm. That is because when $| T |$ is fixed and the network size is small, each node will choose a different active time-slot with a high probability. In this case, each dominator had to transmit to its dominatees one by one, which is similar to the unicast scenario. On the other hand, there exist redundant paths between two dominators in the virtual backbone of SALB, which also causes the result. However, when the network size is large enough, for example, $n > 300$ , more nodes will have identical active time-slots, and thus the active time-slot-oriented forwarding mechanism of SALB can save mode transmission. When $n > 900$ , the transmission of SALB is only 50% of the Tree-algorithm. Then we fix the network size to 500 nodes to observe the impact of $| T |$ on the transmission. For the Tree-algorithm, the transmission remains unchanged since it is determined by the network size. For SALB, the transmission increases as $| T |$ becomes larger (Figure 3). When $| T |$ is small, nodes share identical active time-slots with a high probability, and thus SALB can save more transmission (e.g., $| T | < 60$ in Figure 3). As $| T |$ increases, nodes have different active time-slots gradually, together with the redundant paths among dominators, leading to a bit more transmission than the Tree-algorithm.

Figure 2

Impact of network size on transmission.

Figure 3

Impact of |T| on transmission.

We then evaluate the broadcast latency of SALB. Without considering the collision of wireless channel, if each node retransmits the broadcast message as long as receiving it, the broadcast will finish within the minimum latency, namely, OPT. We compare the broadcast latency of SALB with OPT in the following simulations. First we fix $| T | = 100$ to observe the impact of network size on latency. As the network is scaling up, both the latency of SALB and OPT decrease (Figure 4). The reason behind is when $| T |$ is fixed, the increase of node will make more of them share identical active time-slots. As a result, in SALB, one transmission of a dominator at some time-slot can cover mode neighbor nodes, accelerating the broadcast process. We also find that the broadcast latency of SALB never exceeds 3.5 times of the OPT (Figure 5). Then we fix network size to 500 nodes to see the impact of $| T |$ . In accordance with theoretical analysis, both the latency of SALB and OPT increase linearly (Figure 6). That is because in the cases with fixed network size and increasing $| T |$ , few of nodes share identical active time-slots. Broadcast process had to borrow the unicast method, leading to the increase of latency. We also find that as $| T |$ is increasing, the latency of SALB remains within 3 times of OPT (Figure 7).

Figure 4

Impact of network size on latency.

Figure 5

Impact of network size on ratio to OPT.

Figure 6

Impact of |T| on latency.

Figure 7

Impact of |T| on latency ratio to OPT.

6. Discussion

In the design of SALB algorithm, we apply a heuristic strategy to decrease the number of transmissions and the broadcast latency. However, the two objectives always conflict with each other. Next we will illustrate an example. We consider a network shown as in Figures 8 and 9. The period of sleeping schedule $T = {1,2, 3,4, 5}$ . Node a is the source node of broadcasting. The number in the circle of a node means the active time-slot of the node and the underlined number means the time of package arrives. To minimize the broadcast latency, the broadcasting schedule will be $a \to c, a \to b, c \to f$ , and $b \to {d, e}$ (Figure 8). The latency is 8 time-slots and the numbers of transmissions are 4. To minimize the numbers of transmissions, the broadcasting schedule will be $a \to b, b \to {c, d, e}$ and $c \to f$ (Figure 9). The numbers of transmissions are 3, and the broadcast latency is the time of node f receiving the data package, 11 time-slots. We can observe from this example that minimizing the broadcast latency may cause the number of transmission to be increasing and vice versa. Therefore, in the real scenarios, a tradeoff between two objectives is required.

Figure 8

Relationship of latency and transmission (a).

Figure 9

Relationship of latency and transmission (b).

7. Conclusion

In this paper, we studied the broadcasting problem while considering sleeping schedule in WSN. First we formulated the sleeping schedule-aware broadcast algorithm. Then we proposed a local broadcast algorithm SALB. In SALB, we modified a classical local algorithm for constructing connected dominating set to form the broadcast backbone and designed a forwarding mechanism to handle the periodically sleeping issue of nodes. We proved that the number of transmission of SALB is within $4 (\min (Δ, | T |) + c)$ (c is constant) times of the optimal value, and the latency is within $4 | T | + 1$ times of the optimal value. Moreover, simulations results showed that the performance of SALB is better than the tree-based broadcast algorithm. In the best case, the SLAB saved 50% transmission of the Tree algorithm. As the network is scaling up and the period of sleeping schedule is increasing, the latency of SALB remains within the constant times of the optimal value.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is partly supported by the National Natural Science Foundation of China (Grant nos. 61202417, 61073028, and 61021062), the General Program of Science and Technology Development Project of Beijing Municipal Education Commission (Grant no. KM201411232013), and the Project of Shandong Province Higher Educational Science and Technology Program under Grant no. J13LN13.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 105

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

S. Y.

Tseng

Y. C.

Chen

Y. S.

Sheu

J. P.

The broadcast storm problem in a mobile Ad Hoc network

Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99)

1999

151 162

Lou

A cluster-based backbone infrastructure for broadcasting in manets

Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS '03)

April 2003

1530 2075

Wei

Forward-node-set-based broadcast in clustered mobile Ad Hoc networks

Wireless Communications and Mobile Computing 2003 3 2 155 173

2-s2.0-0038223173

10.1002/wcm.109

Lou

On reducing broadcast redundancy in Ad Hoc wireless networks

IEEE Transactions on Mobile Computing 2002 1 2 111 122

2-s2.0-0037547762

10.1109/TMC.2002.1038347

Stojmenovic

Seddigh

Zunic

Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks

IEEE Transactions on Parallel and Distributed Systems 2002 13 1 14 25

2-s2.0-0036377260

10.1109/71.980024

Liang

Ahmet Şekercioǧlu

Mani

A low-cost flooding algorithm for wireless sensor networks

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

March 2007

3498 3503

2-s2.0-36349022156

10.1109/WCNC.2007.641

Chlamtac

Kutten

Tree-based broadcasting in multihop radio networks

IEEE Transactions on Computers 1987 36 10 1209 1223

Huang

S. C.-H.

Wan

P.-J.

Jia

Shang

Minimum-latency broadcast scheduling in wireless Ad Hoc networks

Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM '07)

May 2007

733 739

2-s2.0-34548322734

10.1109/INFCOM.2007.91

10.

Mahjourian

Thai

Chen

Zhai

Tiwari

Fang

An approximation algorithm for conflict-aware broadcast scheduling in wireless Ad Hoc networks

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '08)

May 2008

331 340

2-s2.0-57349125628

10.1145/1374618.1374663

11.

Dousse

Mannersalo

Thiran

Latency of wireless sensor networks with uncoordinated power saving mechanisms

Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MoBiHoc '04)

May 2004

109 120

2-s2.0-4444247342

12.

Sadagopan

Krishnamachari

Goel

Delay efficient sleep scheduling in wireless sensor networks

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05)

March 2005

2470 2481

2-s2.0-25644435716

13.

Cao

Abdelzaher

Stankovic

Towards optimal sleep scheduling in sensor networks for rare-event detection

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05)

April 2005

20 27

2-s2.0-33744944530

14.

Keshavarzian

Lee

Venkatraman

Chitalapudi

Lal

Srinivasan

Wakeup scheduling in wireless sensor networks

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '06)

May 2006

322 333

2-s2.0-33748034055

15.

Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links

Proceedings of the 5th ACM International Conference on Embedded Networked Sensor Systems (SenSys '07)

November 2007

321 334

2-s2.0-77954257263

10.1145/1322263.1322294

16.

Kyasanur

Choudhury

R. R.

Gupta

Smart gossip: an adaptive gossip-based broadcasting service for sensor networks

Proceedings of the IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems (MASS '06)

October 2006

91 100

2-s2.0-39049156023

10.1109/MOBHOC.2006.278671

17.

Wang

Liu

Duty-cycle-aware broadcast in wireless sensor networks

Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM '09)

April 2009

468 476

2-s2.0-70349661806

10.1109/INFCOM.2009.5061952

18.

Hong

Cao

Chen

Minimum-transmission broadcast in uncoordinated duty-cycled wireless Ad Hoc networks

IEEE Transactions on Vehicular Technology 2010 59 1 307 318

2-s2.0-76849104635

10.1109/TVT.2009.2030203

19.

Tang

Hong

You

Distributed low redundancy broadcast for uncoordinated duty-cycled WANETs

Proceedings of the 54th Annual IEEE Global Telecommunications Conference (GLOBECOM '11)

December 2011

2-s2.0-84857220243

10.1109/GLOCOM.2011.6133526

20.

Hong

Cao

Chen

Sleeping schedule-aware minimum latency broadcast in wireless Ad Hoc networks

Proceedings of the IEEE International Conference on Communications (ICC '09)

June 2009

1 5

2-s2.0-70449479008

10.1109/ICC.2009.5199463

21.

Jiao

Lou

Cao

Wang

Zhou

Duty-cycle-aware minimum latency broadcast scheduling in multi-hop wireless networks

Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS '10)

June 2010

754 763

2-s2.0-77955889142

10.1109/ICDCS.2010.20

22.

Heidemann

Estrin

An energy-efficient MAC protocol for wireless sensor networks

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '02)

June 2002

1567 1576

2-s2.0-0036343658

10.1109/INFCOM.2002.1019408

23.

Maróti

Kusy

Simon

Lédeczi

Á.

The flooding time synchronization protocol

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys '04)

November 2004

39 49

2-s2.0-27644533289

24.

Lou

Dai

Extended multipoint relays to determine connected dominating sets in MANETs

IEEE Transactions on Computers 2006 55 3 334 347

2-s2.0-32044465204

10.1109/TC.2006.40

25.

Alzoubi

K. M.

Wan

P.-J.

Frieder

Message-optimal connected dominating sets in mobile Ad Hoc networks

Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '02)

June 2002

157 164

2-s2.0-0242527347

26.

Guha

Khuller

Approximation algorithms for connected dominating sets

Algorithmica 1998 20 4 374 387

2-s2.0-19644369843

27.

Wan

P.-J.

Alzoubi

K. M.

Frieder

Distributed construction of connected dominating set in wireless Ad Hoc networks

Mobile Networks and Applications 2004 9 2 141 149

2-s2.0-1642408650

10.1023/B:MONE.0000013625.87793.13

28.

Wang

X.-Y.

Geometric spanners for wireless Ad Hoc networks

Proceedings of the 22nd International Conference on Distributed Systems (ICDCS '02)

July 2002

171 178

2-s2.0-0036373267

29.

Bagrodia

Meyer

Takai

Chen

Y.-A.

Zeng

Martin

Song

H. Y.

Parsec: a parallel simulation environment for complex systems

Computer 1998 31 10 77 85

2-s2.0-0032186636

10.1109/2.722293

30.

Jüttner

Magi

Á.

Tree based broadcast in Ad Hoc networks

Mobile Networks and Applications 2005 10 5 753 762

2-s2.0-24344503680

10.1007/s11036-005-3368-5

Sleeping Schedule-Aware Local Broadcast in Wireless Sensor Networks

Abstract

1. Introduction

2. Related Work

3. Model and Assumption

3.1. Problem Formulation

Definition 1 (the sleeping schedule-aware broadcast (SA-broadcast)).

Definition 2 (inversion).

4. Local Algorithm for SA-Broadcast Problem

4.1. Construction of Broadcast Backbone

4.1.1. Electing Dominators

4.1.2. Connecting Dominators

Algorithm 1

Algorithm 2

4.2. Active Time-Slot-Oriented Forwarding Mechanism

Algorithm 3

5. Performance Evaluation

5.1. Theoretical Analysis

Theorem 3.

Proof.

Theorem 4.

Proof.

5.2. Simulation Results

6. Discussion

7. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References