Distributed Broadcast with Minimum Latency in Asynchronous Wireless Sensor Networks under SINR-Based Interference

Abstract

Data broadcast is a fundamental operation in wireless sensor networks (WSNs). The existence of wireless interference makes it nontrivial to design a minimum-latency broadcast scheme, which is known to be NP-hard. Existing works all assume strict time synchronization and provide centralized TDMA scheduling algorithms. However, WSNs in practice are more likely to be distributed asynchronous systems. In this paper, we investigate the problem of data broadcast with minimum latency for distributed asynchronous WSNs. To this end, we propose a Distributed Asynchronous Broadcast (DAB) algorithm which crucially leverages an elaborately optimized carrier-sensing range together with collision-backoff schemes to coordinate the transmissions among the nodes on a predetermined broadcast backbone. Theoretical analysis shows that DAB is order-optimal and achieves constant factor approximation to the optimal delay. We then conduct extensive simulations to evaluate the practical capability of DAB in asynchronous WSNs and the results corroborate our theoretical analysis.

1. Introduction

Data broadcasting is probably one of the most fundamental operations in wireless sensor networks (WSNs) in which a message needs to be disseminated from its source to all the other nodes in the network. Broadcast plays an important role in implementing many networking protocols such as routing, information distribution, and resource discovery. In many applications of WSNs, for instance, military surveillance, industrial control, and object tracking, the time of utilizing the data is critical and a broadcast task often comes with a stringent delay constraint, which leads to the demand for low-latency broadcast scheme. Generally, a major challenge in achieving fast broadcast is how to deal with the interference in wireless networks effectively [1]. Due to the broadcast nature of wireless channel, two or more nodes transmitting data at the same time may interfere with each other, resulting in potential transmitting or receiving failures. To avoid wireless interference, the transmission requests within the network should be carefully scheduled, and such a requirement brings out the extensive research of Minimum-Latency Broadcast Scheduling (MLBS) in the literature [1–8]. MLBS aims to find an interference-free transmission schedule for data broadcast subject to interference constraints, while minimizing the total latency.

Ever since the NP-hardness of MLBS was established by Gandhi et al. in [1], a large amount of research has been conducted towards designing efficient broadcast algorithms with favorable approximation performance. Based on the assumption that interference exists among transmitters within a certain distance from each other (termed protocol or graph-based interference model [9]), numerous polynomial-time scheduling algorithms are proposed to generate collision-free transmission schedules for broadcasting and meanwhile achieve broadcast latencies whose upper bounds are approximate to the optimum [2–8]. Nevertheless, to the best of our knowledge, most of the existing works study MLBS under an ideal condition where the time is slotted and the entire network is strictly synchronized. In such a case, the transmissions in the network can be elaborately arranged to be scheduled during different time-slots and moreover nice bounds of broadcast latency can be calculated, which offers convenience for evaluating and comparing the theoretical performance of different broadcast schemes. However, in practice, it is rather difficult and not realistic to achieve strict time synchronization in wireless networks due to clock drift, unstable deployment environment and other technical limits, especially WSNs comprising large numbers of nodes [10, 11]. For the more practical asynchronous WSNs, unfortunately, little research on MLBS has been carried out.

In this paper, we are desired to fill this gap in order to better understand the performance of data broadcast algorithms in practical asynchronous WSNs. Such work is nontrivial yet rather challenging for that in asynchronous WSNs, it is impractical to acquire the overall information of all the nodes in the network and thus optimal schedule of data transmissions cannot be easily computed. Furthermore, in asynchronous WSNs, each node starts data transmission based on its own time clock and local information, which inevitably results in many data collisions and retransmissions, incurring latency performance degradation. To address the above challenges, we propose an interference-free and low-latency broadcast algorithm named DAB with favourable performance guaranteed by theoretical analysis and experimental evaluation for MLBS in asynchronous WSNs. DAB bases its design idea on CSMA/CA in the IEEE 802.11 standard and crucially uses the physical carrier sensing as a key ingredient. By carefully setting the carrier-sensing range and backoff timer, we make sure that each node can successfully broadcasts a message to its neighbours without suffering from any interference. Through propagating the broadcast message among the nodes on a preconstructed Connected Dominating Set- (CDS-) based broadcast backbone, all the nodes in the network are ensured to receive the message within a duration whose length is shown to achieve constant factor approximation to the theoretical minimum time. In other words, DAB achieves constant factor approximation on the optimal broadcast latency. Additionally, DAB focuses on the physical interference model [9] which is known to capture wireless interference more accurately and realistically than the widely used graph-based models. In the physical model, a signal is received successfully if and only if the Signal-to-Interference-plus-Noise-Ratio (SINR)—the ratio of the received signal strength to the sum of the interference caused by nodes transmitting simultaneously, plus noise—is above a hardware-defined threshold. The adoption of the physical model brings about another challenge as the interference among simultaneous transmissions is no longer a localized relationship and all the potential interference from the other (even very far-away) nodes should be taken into account. In all, we make the contributions summarized as below.

• (1)

We derive the minimum interference-free carrier-sensing range, named minICR, for the nodes involved in the broadcast task under the physical interference model. The value of minICR is elaborately designed to make sure that (a) each node can conduct a successful broadcast to the nodes within distance of $\delta r$ from it, provided that there is no ongoing transmission within its carrier-sensing range, and (b) the largest degree of spatial reuse can be achieved. Here r is the maximum transmission range of each node and δ ( $\mathrm{0}<\delta <\mathrm{1}$ ) is a small constant chosen properly to ensure the network with links of length at most $\delta r$ to be connected.

(2)

Based on the obtained minICR, we propose a distributed CSMA-like algorithm DAB for data broadcasting in asynchronous WSNs. Taking an existing CDS-based routing tree as the broadcast backbone, DAB propagates the broadcast message among the nodes on the backbone using carrier-sensing and collision backoff. Through coordinating the transmissions effectively, we make sure that the broadcast task is accomplished within $O(R)$ time in the worst case, where R is the radius of the graph with link length at most $\delta r$ (which we refer to as reduced graph). Since R is a trivial lower bound for any broadcast algorithms, DAB achieves constant factor approximation with regard to the theoretical optimum.

(3)

We conduct extensive simulations to evaluate the practical capability of DAB in asynchronous WSNs. The results reveal that DAB does have comparable performance as the latest centralized and synchronized data broadcast algorithms in terms of latency under various network configurations.

The rest of the paper is organized as follows: Section 2 reviews the related work. Section 3 presents the network model and problem definition. Section 4 introduces the derivation of the minimum interference-free carrier-sensing range under the physical interference model. Section 5 serves as one of the main parts of this paper which presents the detail of DAB and its performance analysis as well. Section 6 provides the simulation results. Finally, Section 7 concludes the paper.

2. Related Works

2.1. Minimum Latency Broadcast Scheduling

MLBS in arbitrary undirected graphs has been extensively studied in the literature. Chlamtac and Kutten [14] established the NP-hardness of MLBS in general graphs. For the same problem, Elkin and Kortsarz investigated the hardness of approximation algorithms in [15, 16]. They proved a logarithmic multiplicative inapproximability (unless $\text{NP}\subseteq \text{BPTIME}(n^{O(\log \hspace{0.17em}\log n)})$ , $\Omega (\log n)$ —approximation of the broadcast problem is impossible [15]), and a polylogarithmic additive inapproximability (unless $\text{NP}\subseteq \text{BPTIME}(n^{O(\log \hspace{0.17em}\log n)})$ ; there exists no polynomial-time algorithm that produces a schedule with length less than $\text{opt}(G)+{\log }^{\mathrm{2}}n$ , where $\text{opt}(G)$ is the optimal broadcast latency and n is the number of nodes [16]). Afterwards, Kowalski and Pelc [12] constructed a broadcast schedule with length $O(R\log n+{\log }^{\mathrm{2}}n)$ , the approximation ratio of which is $O({\log }^{\mathrm{2}}(n/R))$ for $R=\Omega (\log n)$ . Gaber and Mansour [17] presented a method consisting of partitioning the underlying graph into clusters and by applying broadcast schemes in each cluster separately; they proposed a schedule with length $O(R+{\log }^{\mathrm{5}}n)$ , which was further reduced to $O(R+{\log }^{\mathrm{2}}n)$ by Gasieniec et al. in [13].

For MLBS under the Disk-graph model, in which the transmission and interference range of a node equipped with an omnidirectional antenna is thought of a disk centered at this node with some radius, large amount of research has emerged in recent years. Gandhi et al. [1] showed that the MLBS problem restricted to unit-disk graphs in wireless networks is NP-hard and presented an approximation algorithm whose approximation ratio is as great as 600. Under the same model, Huang et al. [4] presented three progressively improved approximation algorithms with latencies at most $\mathrm{24}R-\mathrm{23}$ , $\mathrm{16}R-\mathrm{15}$ , and $R\hspace{0.17em}+\hspace{0.17em}\log (R)$ , respectively, where R is the radius of the network. In [3], Chen et al. studied MLBS in a more realistic model in which the interference range of a node is ρ ( $\rho >\mathrm{1}$ ) times the transmission range. They proposed an $O({\rho }^{\mathrm{2}})$ approximation algorithm and the approximation factor is proved to be smaller than $\mathrm{2}\pi {\rho }^{\mathrm{2}}$ . For the case where nodes have different transmission ranges, Tiwari et al. [8] proposed two constant approximation algorithms for centralized scheduling and localized scheduling, respectively. For the practical duty-cycled scenarios where nodes switch between active states and sleep states to save energy, Jiao et al. [18] proposed an algorithm with approximation factor of $\mathrm{17}|T|$ , where $|T|$ is the number of time slots in a scheduling period. Note that all the above works adopt the graph-based models to represent wireless interference. As for the more realistic and accurate physical interference model, few work has been carried out. Huang et al. [5] introduced a tessellation/coloring technique, by which they proposed an approximation algorithm for the 2-Disk model with ratio $\mathrm{6}{\lceil (\mathrm{3}/\mathrm{2})((r_I/r_T)+\mathrm{2})\rceil }^{\mathrm{2}}$ , where $r_I$ and $r_T$ are the interference range and transmission range, respectively. Further, by carefully setting the values of $r_I$ and $r_T$ , they extended the centralized algorithm to the general physical model with the same approximation ratio. Later, Wan et al. [6] presented another constant approximation algorithm whose schedules are built upon a general technique which enables a unified graph-theoretical treatment of the communication scheduling subject to the physical interference model. In addition to deterministic centralized/distributed algorithms, randomized algorithms were also proposed to solve the MLBS problem in the probabilistic model [19, 20], where an explicit relationship between the tolerated transmission-failure probability and the latency of the corresponding broadcast schedule was established and delay efficient scheduling algorithms were presented to ensure that broadcast be finished in low latency with high probability. Unfortunately, for all we know, all the existing works on MLBS made their schedules under an ideal assumption that the network is synchronized and time is divided into slots explicitly or implicitly. Besides, most of the algorithms are centralized. In practice, WSNs are more likely to be distributed asynchronous systems. It is rather challenging yet very essential to investigate distributed broadcast algorithms for asynchronous WSNs, which serves as the target of this paper. We summarize the comparison of different algorithms designed for the MLBS problem that are most related to ours in Table 1.

Table 1

The comparison of different algorithms on the minimum-latency broadcast scheduling problem.

Reference	Interference model	Network model	Implementation	Approximability
Kowalski and Pelc [12]	General graph	Synchronous	Centralized	$O\left(R\log n+{\log }^{2}n\right)$
Gasieniec et al. [13]	General graph	Synchronous	Centralized	$O\left(R+{\log }^{2}n\right)$
Gandhi et al. [1]	Unit-disk graph	Synchronous	Centralized	$O\left(R\right)$ with ratio >600
Huang et al. [4]	Unit-disk graph	Synchronous	Centralized	$O\left(R\right)$ with ratio 16
Chen et al. [3]	Unit-disk graph	Synchronous	Centralized	$O\left({\mathrm{\rho }}^{\mathrm{2}}·R\right)$
Tiwari et al. [8]	Disk graph, $\mathrm{\rho }>\mathrm{1}$	Synchronous	Centralized, distributed	$O\left(R\right)$
Huang et al. [5]	Disk graph, physical	Synchronous	Centralized	$O\left(R\right)$
Wan et al. [6]	Physical	Synchronous	Centralized	$O\left(R\right)$
This paper	Physical	Asynchronous	Distributed	$O\left(R\right)$

2.2. Asynchronous WSNs

Due to the difficulty of strict time synchronization in WSNs, more and more research has been carried out towards designing efficient communication protocols for nodes in asynchronous WSNs. Borbash et al. [21] proposed a probabilistic and asynchronous neighbor discovery algorithm that permits each node in the network to develop a list of its neighbors. Jang et al. [22] presented an energy efficient MAC protocol for WSNs that avoids overhearing and reduces contention and delay through asynchronously scheduling the wakeup time of neighboring nodes. In [23], a dynamic traffic-aware MAC protocol for energy conserving in asynchronous duty-cycled WSNs was proposed which can provide better data transmission rate when nodes are with high traffic loading and save energy when nodes are with low traffic loading.

2.3. Physical Interference Model

In recent years, physical algorithm, that is, algorithm for the physical interference model, has attracted a lot of attention both in the algorithm community and in the communication community. Much efforts have been paid in developing efficient physical algorithms for a wide range of topics in wireless network, including capacity [24], link scheduling [25], data collection, and aggregation [26–28], topology control [29], and so on. For recent results and references we refer the readers to the survey [30].

3. Network Model and Problem Definition

3.1. Network Model

We consider a set V of n nodes deployed in a 2D plane where $v_s\in V$ is the source node. Each node can transmit (receive) data to (from) all directions and all nodes share a common wireless channel. Under the physical interference model [9], we assume all nodes have uniform and fixed transmission power P and define the strength of the received signal at node v transmitted by node u as $P_v(u)=P/d^{\alpha }(u,v)$ . Here α ( $\mathrm{2}<\alpha <\mathrm{6}$ ) is the path-loss exponent and $d(u,v)$ is the Euclidean distance between nodes u and v. A receiver v can successfully receive a message transmitted by the sender u if and only if the Signal-to-Interference-plus-Noise-Ratio (SINR) at v is above a certain threshold β ( $\beta \ge \mathrm{1}$ ):

$$\begin{array}{cc}& \text{SINR}\left(v,u,{𝒮}_u\right)=\frac{P_v\left(u\right)}{\xi +{\Sigma }_{w\in {𝒮}_u}{P}_v\left(w\right)}\ge \beta .\end{array}$$

(1)

Here $\xi >\mathrm{0}$ is the background noise and ${𝒮}_u$ is the set of senders transmitting simultaneously with node u.

Under the physical model, we can compute the maximum transmission range r of each node as $r=(P/\xi \beta {)}^{\mathrm{1}/\alpha }$ . Note that r is achieved by assuming that only one sender is transmitting in the network. In the communication graph of the network, a link exists between nodes u and v ( $u,v\in V$ ) if $d(u,u)\le r$ . Observe that a link with length close to r is in practice not a good candidate for transmission since (a) the SINR value of the receiver will be rather small and (b) many possible concurrent transmissions will be prohibited. Therefore, we will only consider a reduced graph with link length at most $\delta r$ ( $\mathrm{0}<\delta <\mathrm{1}$ ). Generally, the larger the value of δ, the higher the probability that the reduced graph is connected will be. However, if δ is too large (close to 1), the network will be strongly connected with a lot of links, which holds back simultaneous transmissions and increases broadcast latency, potentially. As a result, we will prefer relatively smaller δ. From now on, we assume that the constant δ has been chosen appropriately to ensure the reduced graph is connected. In a reduced graph, the neighbors of node u is the set of nodes that are within distance $\delta r$ from u, and the graph radius R is the maximum graph distance from the source $v_s$ to all other nodes, where the graph distance from u to v is the minimum number of hops between them.

3.2. Problem Definition

Considering a network containing a set V of nodes, and a source $v_s\in V$ having a message m to be disseminated. We do not make any assumption about time synchronization among the nodes in the network. For the broadcast message m, we assume that it takes $t_{\mathrm{0}}$ time for a sender to transmit it to the corresponding receiver when no collision or interference happens. The goal of MLBS is to generate an interference-free transmission schedule for distributing m from $v_s$ to all the other nodes in V. Specifically, the produced schedule should satisfy the following constraints.

• (1)

Each node can only be scheduled to transmit after it has received m from some other nodes.

(2)

At any time instant, the scheduled transmissions must be interference-free, which means that at each of the intended receivers, the SINR value should satisfy the SINR Inequality (1).

(3)

All the nodes within the network must have received m at least once.

(4)

The total time needed to accomplish the broadcast task should be minimized.

4. Interference-Free Carrier-Sensing Range

Since we study data broadcasting in distributed asynchronous WSNs, each node in the network will sense the activities of the other nodes within its carrier-sensing range (CR) before it transmits some data. Only when there is no ongoing transmission within its CR can a node carry out a new data transmission. Intuitively, the value of CR is of great importance on the performance of a distributed broadcast scheme. Specifically, CR should be chosen properly to make sure that when only one node is transmitting within its CR, the transmission will certainly be successful no matter how many nodes beyond its CR are transmitting simultaneously. In such a case, we say that the sensing range is an interference-free CR (ICR), the formal definition of which is presented below.

Definition 1.

The carrier-sensing range CR of a WSN is an interference-free carrier-sensing range (ICR) if each node in the network can conduct a successful transmission to its neighbours in the reduced graph when the node is the only transmitter within its CR.

Under the physical interference model, we have the following theorem which shows the condition that guarantees a carrier-sensing range CR of a WSN be an interference-free carrier-sensing range (ICR).

Theorem 2.

With the physical interference model, a carrier-sensing range CR is ensured to be an ICR if $CR\ge \delta r+(c\beta P/(P(\delta r{)}^{-\alpha }-\beta \xi ){)}^{\mathrm{1}/\alpha }$ , where $c=\mathrm{6}+\mathrm{6}(\sqrt{\mathrm{3}}/\mathrm{2}{)}^{-\alpha }·\zeta (\alpha -\mathrm{1})+\mathrm{3}(\sqrt{\mathrm{3}}/\mathrm{2}{)}^{-\alpha -\mathrm{1}}·\zeta (\alpha )$ and $\zeta (·)$ is the Riemann zeta function.

Proof.

Assuming that node u is a transmitter and node v is one of its neighbours in the reduced graph, we have $d(u,v)\le \delta r$ . To ensure that v can receive the message from u successfully, the following condition should hold:

$$\begin{array}{cc}& \frac{P{\left(\delta r\right)}^{-\alpha }}{\xi +ℐ}\ge \beta .\end{array}$$

(2)

Here ℐ is the total interference from all other concurrent transmitters experienced by v. We now try to bound the amount of ℐ. Let ${𝒮}_u$ be the set of nodes transmitting simultaneously with node u, then the minimum distance between any two nodes in ${𝒮}_u$ is no smaller than CR. It has been proven in [31] that the densest packing of nodes with the minimum distance requirement is the hexagon packing, as shown in Figure 1.

Subsequently, all the nodes $w\in {𝒮}_u$ can be divided into layers according to their distance from u. If node w is at the first layer around u, we have $d(w,u)\ge \text{CR}$ . Using this fact and the triangular inequality, we have $d(w,v)\ge d(w,u)-d(u,v)\ge \text{CR}-\delta r$ . If node w is at the kth ( $k\ge \mathrm{2}$ ) layer around u, we have $d(w,u)\ge (\sqrt{\mathrm{3}}/\mathrm{2})k\text{CR}$ . Similarly, we have $d(w,v)\ge (\sqrt{\mathrm{3}}/\mathrm{2})k\text{CR}-\delta r$ . Since there are at most $\mathrm{6}k$ nodes at the kth ( $k\ge \mathrm{1}$ ) layer, we can bound the total interference experienced by node v from all potential transmitters at all layers as follows (in the derivation, we denote CR by ℛ for conciseness):

$$\begin{array}{l}ℐ\le P{\left(ℛ-\delta r\right)}^{-\alpha }·\mathrm{6}\\ \hspace{1em}\hspace{1em}+\sum _{k=\mathrm{2}}^{\infty }P{\left(\frac{\sqrt{\mathrm{3}}}{\mathrm{2}}kℛ-\delta r\right)}^{-\alpha }·\mathrm{6}k\\ \hspace{1em}=\mathrm{6}P{\left(ℛ-\delta r\right)}^{-\alpha }+\mathrm{6}P{\left(\frac{\sqrt{\mathrm{3}}ℛ}{\mathrm{2}}\right)}^{-\alpha }\\ \hspace{1em}\hspace{1em}\times \sum _{k=\mathrm{2}}^{\infty }k{\left(k-\frac{\mathrm{2}\delta r}{\sqrt{\mathrm{3}}ℛ}\right)}^{-\alpha }\\ \hspace{1em}=\mathrm{6}P{\left(ℛ-\delta r\right)}^{-\alpha }+\mathrm{6}P{\left(\frac{\sqrt{\mathrm{3}}ℛ}{\mathrm{2}}\right)}^{-\alpha }\\ \hspace{1em}\hspace{1em}\times (\sum _{k=\mathrm{2}}^{\infty }{\left(k-\frac{\mathrm{2}\delta r}{\sqrt{\mathrm{3}}ℛ}\right)}^{-\alpha +\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sum _{k=\mathrm{2}}^{\infty }{\left(k-\frac{\mathrm{2}\delta r}{\sqrt{\mathrm{3}}ℛ}\right)}^{-\alpha }·\frac{\mathrm{2}\delta r}{\sqrt{\mathrm{3}}ℛ})\\ \hspace{1em}\le \mathrm{6}P{\left(ℛ-\delta r\right)}^{-\alpha }+\mathrm{6}P{\left(\frac{\sqrt{\mathrm{3}}ℛ}{\mathrm{2}}\right)}^{-\alpha }\\ \hspace{1em}\hspace{1em}\times \left(\sum _{k=\mathrm{2}}^{\infty }{\left(k-\mathrm{1}\right)}^{-\alpha +\mathrm{1}}+\frac{\mathrm{2}\delta r}{\sqrt{\mathrm{3}}ℛ}·\sum _{k=\mathrm{2}}^{\infty }{\left(k-\mathrm{1}\right)}^{-\alpha }\right)\\ \hspace{1em}=\mathrm{6}P{\left(ℛ-\delta r\right)}^{-\alpha }+\mathrm{6}P{\left(\frac{\sqrt{\mathrm{3}}ℛ}{\mathrm{2}}\right)}^{-\alpha }\\ \hspace{1em}\hspace{1em}\times \left(\zeta \left(\alpha -\mathrm{1}\right)+\frac{\mathrm{2}\delta r}{\sqrt{\mathrm{3}}ℛ}\zeta \left(\alpha \right)\right)\\ \hspace{1em}\le P{\left(ℛ-\delta r\right)}^{-\alpha }(\mathrm{6}+\mathrm{6}{\left(\frac{\sqrt{\mathrm{3}}}{\mathrm{2}}\right)}^{-\alpha }·\zeta \left(\alpha -\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\mathrm{3}{\left(\frac{\sqrt{\mathrm{3}}}{\mathrm{2}}\right)}^{-\alpha -\mathrm{1}}·\zeta \left(\alpha \right))\\ \hspace{1em}=cP{\left(ℛ-\delta r\right)}^{-\alpha }.\end{array}$$

(3)

Here $c=\mathrm{6}+\mathrm{6}(\sqrt{\mathrm{3}}/\mathrm{2}{)}^{-\alpha }·\zeta (\alpha -\mathrm{1})+\mathrm{3}(\sqrt{\mathrm{3}}/\mathrm{2}{)}^{-\alpha -\mathrm{1}}·\zeta (\alpha )$ is a constant since $\zeta (\alpha )$ ( $\alpha >\mathrm{3}$ ) can be bound by a positive constant. In the derivation, we have used the fact that $\text{CR}-\delta r>\delta r$ ; that is, $\text{CR}>\mathrm{2}\delta r$ . Then the SINR value at node v can be obtained as

$$\begin{array}{l}\text{SINR}\left(v,u,{𝒮}_u\right)\\ \hspace{1em}\ge \frac{P{\left(\delta r\right)}^{-\alpha }}{\xi +cP{\left(\text{CR}-\delta r\right)}^{-\alpha }}\\ \hspace{1em}\ge \frac{P{\left(\delta r\right)}^{-\alpha }}{\xi +cP{\left(\delta r+{\left(c\beta P/\left(P{\left(\delta r\right)}^{-\alpha }-\beta \xi \right)\right)}^{\mathrm{1}/\alpha }-\delta r\right)}^{-\alpha }}\\ \hspace{1em}=\beta .\end{array}$$

(4)

Thus, node v can successfully receive the message from node u and the carrier-sensing range CR is surely an interference-free carrier-sensing range (ICR). This finishes the proof.

Figure 1

The hexagon packing of nodes.

Intuitively, the smaller the CR, the higher the degree of spatial reuse will be. Therefore, we set CR as $\delta r+(c\beta P/(P(\delta r{)}^{-\alpha }-\beta \xi ){)}^{\mathrm{1}/\alpha }$ and denote it by minICR, which not only guarantees the data transmissions be interference-free but also ensures the largest spatial reuse. Furthermore, with regard to α, β, and δ, we numerically analyze the relationship between these parameters and the degree of spatial reuse, which is expressed in the form of $(\text{minICR}/\delta r)$ , that is, the ratio of the carrier-sensing range to the transmission (broadcast) range. Obviously, the larger the value of $(\text{minICR}/\delta r)$ , the lower the spatial reuse degree will be. Figure 2 shows the variation of $(\text{minICR}/\delta r)$ with different α, β, and δ. We can figure out that relatively larger α and smaller δ induce more spatial reuse, which can be explained by the fact that larger α means more severe degradation of interference and smaller δ implies shorter transmission range and hence larger received power. In both cases, more simultaneous transmissions can be conducted. On the other hand, the SINR threshold δ does not have much impact on spatial reuse, which is not surprising since β is just a ratio.

Figure 2

The impact of α, β, and δ on the degree of spatial reuse.

5. Algorithm Design

In this section, we present the algorithm design for data broadcasting, which takes advantage of the derived minICR in Section 4 as a core ingredient. In our algorithm, we first construct a broadcast backbone which will serve as the routing of message propagation using an existing method and then present our broadcast scheduling algorithm which coordinates the node activities on the backbone in order to accomplish the broadcast task efficiently.

5.1. Broadcast Backbone

For a WSN represented by a reduced graph $G(V,E)$ where E consists of edges of length at most $\delta r$ , we will construct a Connected Dominator Set- (CDS-) based broadcast backbone by employing a similar method with those in [4, 32]. The employed method comprises the following three steps.

• (1)

Perform a breadth-first search (BFS) on G, beginning at the sink $v_s$ and obtaining a BFS tree named $T_{\text{BFS}}$ of the reduced graph. As expected, the i-layer of $T_{\text{BFS}}$ consists of nodes that are i hops from $v_s$ . We give an example of the graph G and the produced $T_{\text{BFS}}$ as shown in Figures 3(a) and 3(b), respectively.

(2)

Select a Maximum Independent Set (MIS) 𝒟 from the nodes in V. Specifically, we first add $v_s$ into 𝒟. Next, we check each of the remaining nodes in the BFS order and add it into 𝒟 provided this node is not adjacent to any of the nodes in 𝒟. Note that the MIS 𝒟 is also a dominator set (DS) and the nodes in 𝒟 are called dominators. The RED nodes in Figure 3(b) show an example of an MIS.

(3)

Select some connectors to interconnect the dominators in 𝒟 and hence form as a CDS-based broadcast tree. In specific, for each dominator in 𝒟, we pick its parent in $T_{\text{BFS}}$ as a connector and the selected connectors make up a connector set 𝒞. The nodes in $𝒟\cup 𝒞$ form a CDS. The nodes not in $𝒟\cup 𝒞$ are called dominatees. Furthermore, we connect each dominator with its corresponding connector and each connector with one of the dominators in the same or upper layers, resulting in a connected broadcast tree. Figure 3(c) shows an example of a CDS-based broadcast tree of the reduced graph G.

Figure 3

An example of the construction of broadcast backbone (a) the graph G, (b) the selection of MIS; (c) the constructed CDS-based backbone.

Apparently, to accomplish the broadcast task, it is unnecessary for every node in G to participate in the message propagation. Instead, we only need to deliver the broadcast message among the nodes on the backbone. In particular, after each node in $𝒟\cup 𝒞$ has transmitted at least once, all the nodes in the network will have heard the broadcast message. Base on the constructed backbone (denoted by $T_B$ ), we now present the detail of our distributed asynchronous algorithm for broadcasting.

5.2. Distributed Asynchronous Broadcast

Our Distributed Asynchronous Broadcast (DAB) algorithm works in a CSMA fashion, except for the RTS/CTS working mode and the necessity to reply an ACK packet after receiving a data packet. Such elegance is owing to the fact that we have carefully set the carrier-sensing range for each sender which guarantees the data transmission be certainly interference-free under the physical interference model.

We present the pseudo-code of DAB in Algorithm 1. At the beginning, the sink broadcasts a message and then turns to asleep. For each dominatee in the network, it will turn to asleep after receiving the broadcast message at the first time. For each dominator or connector, it will try to relay the broadcast message immediately after receiving it. Before transmitting, the node (say u) randomly sets a backoff timer $t_u$ , where $t_u\in (\mathrm{0},t_w]$ and $t_w$ is the backoff contention window. We assume that the length of $t_w$ is negligible compared with the data transmission time $t_{\mathrm{0}}$ , that is, $t_w\ll t_{\mathrm{0}}$ . Afterwards, node u begins the countdown process and keeps sensing the channel with minICR. If the channel is busy sensed by u, the countdown process at u will be frozen. At such circumstances, if a data transmission is ongoing, all the other nodes having data to transmit within minICR of the transmitter will stop their cutdown processes. If the channel is sensed free by u, the backoff time $t_u$ will be cut by one time unit. Node u will transmit the message as soon as $t_u$ expires. Here we make an assumption that by randomization, no two transmitters within the CR of each other have their backoff timers expired at the same time instant. For the case of simultaneous countdown-to-zero, we can tackle it by an exponential backoff mechanism in which the transmission probability of each node is adjusted in a dynamic way based on the network busyness as in [31]. With such an assumption, we ensure that the transmission of each node to be carried out successfully without suffering from any interference.

Algorithm 1: Distributed asynchronous broadcast (DAB).

1 Initially, each node sets its carrier-sensing range as $\underset{}{\min }\text{ICR}$ . Then the sink ${\upsilon }_s$ broadcasts a message

and turns to be asleep;

2 if node u  receives the broadcast message then

3   if u is a dominatee node then

4     u turns to be asleep;

5   else

6     u randomly sets a backoff timer $t_u$ , where $t_u$ ∈ (0, $t_w$ ] and $t_w$ is the backoff contention

    window;

7    while $t_u$ > 0 do

8      u senses the channel with $\underset{}{\min }\text{ICR}$ ;

9      if the channel is busy sensed by u then

10       u freezes the backoff timer and stops the countdown process until the channel

       becomes free again;

11     else

12        $t_u\leftarrow t_u-1$ ;

13      end

14    end

15    if $t_u$ == 0 then

16       $s_u$ broadcasts the received message to its neighbors within the range of $\delta r$ , and then

     turns to be asleep;

17    end

18   end

19 end

It is essential to clarify that in CSMA/CA of the IEEE 802.11 standard, each node has a limited carrier-sensing range and a node knows that the wireless channel is busy when another node in this range is transmitting by the way of a power-threshold carrier-sensing mechanism [33]. However, as we could see, the value of minICR is usually larger than the original carrier-sensing range. That means minICR is inherently not compatible with the conventional power-threshold carrier-sensing mechanism as used in IEEE 802.11. Specifically, the absolute power sensed by a node in the conventional mechanism does not contain enough information for it to derive its distances from other concurrent transmitter nodes. Fortunately, for the case where a lager carrier-sensing range is needed, a new carrier-sensing mechanism called Incremental-Power Carrier-Sensing (IPCS) proposed by Fu et al. in [31] can realize it in a simple way. To be more specific, instead of monitoring the absolute detected power, the IPCS mechanism monitors every increment in the detected power. This means that IPCS can separate the detected power of every concurrent transmitter and map the power profile to the required distance information [31]. Using such a method, a node will be able to determine whether it is within minICR of a transmitter in the distributed asynchronous broadcast algorithm DAB.

5.3. Latency Analysis

We now analyze the latency performance of DAB, which is of great importance on the efficiency of our algorithm. To begin with, we introduce a classic geometric result on disk packing.

Lemma 3 (Groemer inequality [34]).

Suppose that C is a compact convex set and U is a set of points with mutual distances at least one. Then

$$\begin{array}{cc}& \left|U\cap C\right|\le \frac{area\left(C\right)}{\sqrt{\mathrm{3}}/\mathrm{2}}+\frac{peri\left(C\right)}{\mathrm{2}}+\mathrm{1},\end{array}$$

(5)

where area(C) and peri(C) are the area and perimeter of C respectively.

Based on Lemma 3, we are able to bound the number of dominators and connectors within the CR of each node.

Lemma 4.

Let $N_{𝒟}$ (resp., $N_{𝒞}$ ) denote the number of dominators (resp., connectors) located in the CR of each node, then we have $N_{𝒟}\le \beta (CR/\delta r)$ (resp., $N_{𝒞}\le \beta (CR/\delta r+\mathrm{1}))$ , where $\beta (x)=(\mathrm{2}\pi x^{\mathrm{2}}/\sqrt{\mathrm{3}})+\pi x+\mathrm{1}$ .

Proof.

For node u, its carrier-sensing range is a disk of radius CR centered at u. Moreover, the mutual distances of the dominators in 𝒟 are not longer than $\delta r$ . By applying Lemma 3, we can directly bound $N_{𝒟}$ as $N_{𝒟}\le \beta (\text{CR}/\delta r)$ , where $\beta (x)=(\mathrm{2}\pi x^{\mathrm{2}}/\sqrt{\mathrm{3}})+\pi x+\mathrm{1}$ .

According to the construction of the broadcast backbone, for each dominator, we add a corresponding connector to interconnect it with some other dominator. Then consider a disk of radius $\text{CR}+\delta r$ centered at u, the number of dominators in this disk does not exceed $\beta (\text{CR}/\delta r+\mathrm{1})$ based on Lemma 3. For the corresponding connectors that are located within a disk of radius CR centered at u, the number is at most $\beta (\text{CR}/\delta r+\mathrm{1})$ . On the other hand, for the dominators in a disk of radius larger than $\text{CR}+\delta r$ , the corresponding connectors are surely not located in the disk of radius CR centered at u. As a result, we can bound the number of connectors within a disk of radius CR as $N_C\le \beta (\text{CR}/\delta r+\mathrm{1})$ . This finishes the proof.

Now we are able to acquire the latency bound of DAB, for which we have the following lemma.

Lemma 5.

Algorithm DAB accomplishes broadcast in $O(R)$ time, where R is the radius of the reduced graph.

Proof.

For each node (dominator or connector) on the backbone, there are at most $N_{𝒞}+N_{𝒟}$ nodes contending for data transmission within its CR. Since each transmission takes $t_{\mathrm{0}}$ time, in the worst case, each node can conduct a data transmission within $(N_{𝒞}+N_{𝒟})·t_{\mathrm{0}}$ time. Therefore, for all the nodes on the backbone that are i hops from $v_s$ , they are able to finish broadcast in $(N_{𝒞}+N_{𝒟})·t_{\mathrm{0}}$ time. Moreover, after such time, all the nodes on the backbone that are $i+\mathrm{1}$ hops from $v_s$ will have heard the broadcast message at least once. This implies that the farthest nodes from $v_s$ , that is, nodes that are R hops from $v_s$ , will have received the broadcast message within $(N_{𝒞}+N_{𝒟})t_{\mathrm{0}}·R$ time in the worst case. Note that to ensure interference-free transmission, CR is set as minICR, which is a constant. Thus, $N_{𝒞}$ and $N_{𝒟}$ are both constants as well. Hence, the upper bound of the time consumed by DAB is $(N_{𝒞}+N_{𝒟})t_{\mathrm{0}}·R=O(R)$ . This finishes the proof.

Observe that it takes at least $R*t_{\mathrm{0}}$ time for the farthest node to receive the broadcast message initially transmitted by $v_s$ for any algorithm. This implies that R is a lower bound for the broadcast problem. As the latency of DAB is bounded by $O(R)$ , we can achieve the following theorem immediately.

Theorem 6.

DAB is a constant approximation algorithm for data broadcasting, when we only consider a reduced graph of the original network.

6. Simulation

6.1. Setup

In this section, we evaluate the practical performance of DAB using simulations. In all simulations, we consider the WSNs consisting of one source node and n sensor nodes that are uniformly and randomly deployed in a square region with side length l. All the nodes in the network have fixed and equal transmission power P and share a common wireless channel with limited bandwidth. The compared algorithm for DAB is the Centralized Broadcast Scheduling (CBS) algorithm proposed by Wan et al. in [6], which is the most recently published data broadcast algorithm under the more practical physical interference model. Unlike DAB, CBS is a highly centralized algorithm and works in a TDMA fashion. Specifically, the broadcast schedule is made at a control center with the assumption that the information at individual nodes are known prior and during each time slot, as many transmitters are scheduled as possible without violating the SINR requirements at all the corresponding receivers. Since our primary concern is the total latency of broadcast, we assume that the transmission duration of a single data packet is normalized to 1 time unit. Specifically, we set the transmission time of the broadcast message (i.e., $t_{\mathrm{0}}$ ) and the length of a time slot both as 1 for DAB and CBS, respectively. Additionally, we set the backoff contention window $t_w=\mathrm{0.1}$ for DAB. In all the simulations, we set the transmission power $P=\mathrm{15}$ and the background noise $\xi =\mathrm{0.1}$ . For the other parameters, such as the path-loss exponent α and the SINR threshold β, we specify them later in each group of simulations.

Based on the parameters P, ξ, α, and β, we can obtain the maximum transmission range r of each node. For both algorithms, we consider a reduced graph consisting of edges with length at most $\delta r$ . Intuitively, the value of δ determines the topology of the network to a certain degree and further influences the performance of broadcast algorithms. Generally, the larger the value of δ, the higher the possibility that the reduced network is connected will be. However, if δ is too large (close to 1), the network will be strongly connected with a large number of links, which prevents simultaneous transmissions and increases broadcast latency, potentially. From this perspective, a relatively smaller δ is preferred for broadcast. In later simulations, we will first set δ as some default values and then try to find an optimal choice of δ to minimize the broadcast delay under certain network conditions.

6.2. Impact of Network Radius

Firstly, we evaluate the effect of network radius R on broadcast latency. We set $l=\mathrm{200}$  m, $\alpha =\mathrm{3.0}$ , and $\beta =\mathrm{1.0}$ . By increasing the network size n from 200 to 2000 with step size 200, we obtain the average latencies of broadcast algorithms with different $\delta =0.2$ , 0.5, and 0.8 as shown in Figure 4. The Upper Bound curve in Figure 4 is drawn as theoretical bound of the latency of DAB as described in Section 5.3, which serves as another benchmark for performance comparison. We can observe that as the number of nodes increases, the latency of CBS, DAB, and Upper Bound all increase monotonously. Moreover, CBS always achieves the best performance under various network size, which is not surprising since it is a nearly optimal algorithm that makes transmission schedules based on global information. Nevertheless, we can see that our distributed asynchronous algorithm DAB has comparable performance with CBS, and the gap between both algorithms does not exceed 15% in the worst case under various values of n and δ. Additionally, we find that the latency of DAB is much shorter—from 1.9 to 2.5 times less than the theoretical upper bound. In all, the simulation results reveal that DAB does have good performance in terms of broadcast latency in various network configurations.

Figure 4

Broadcast latency of different algorithms in terms of the number of nodes when (a) $\delta =\mathrm{0.2}$ , (b) $\delta =\mathrm{0.5}$ , and (c) $\delta =\mathrm{0.8}$ .

6.3. Impact of α, β

We evaluate the effect of SINR parameters α and β. We set $l=\mathrm{200}$  m and $\delta =\mathrm{0.5}$ and consider a moderate network density of 1000 nodes. Figures 5(a) and 5(b) show the impact of α and β on broadcast latency, respectively. We observe that as α increases, the latency of all algorithms decrease monotonously. This is due to the fact that when α becomes larger, the attenuation of signal will be more severe. Therefore, the interference of one transmission on others will be alleviated, which further implies that more transmissions can be conducted concurrently. We can also observe that unlike α, the value of β does not influence the performance of all algorithms much, which is expected, given that β is just a ratio. As before, DAB has similar performance with CBS and much better performance with the theoretical bound, which further demonstrates the suitability of DAB in practical asynchronous WSNs.

Figure 5

The impact of SINR parameters α and β on broadcast latency.

6.4. The Best Choice of δ

Finally, we conduct simulations to see the impact of δ in different scenarios. We set $l=\mathrm{200}$  m, $\alpha =\mathrm{3.0}$ , and $\beta =\mathrm{1.0}$ . By fixing the network size as 1000, Figure 6(a) shows the latency of DAB with different values of δ. Furthermore, by varying the network size n from $\mathrm{200}$ to $\mathrm{2000}$ with step size $\mathrm{200}$ , Figure 6(b) shows the best choices of δ in a fixed deployment area. Here a best choice means that the latency of DAB reaches minimum when δ is set to this value. For practical application of DAB, we can choose the most suitable δ to minimize the broadcast latency as well as maintain the connectivity of the network.

Figure 6

The impact of δ on broadcast latency of DAB.

7. Conclusion and Future Work

We study the minimum latency data broadcast problem in distributed asynchronous WSNs, which is more practical yet rather challenging compared with centralized and synchronized sceneries. To avoid transmission interference, we derive the minimum interference-free carrier-sensing range (termed minICR) under the physical interference model to make sure that by taking minICR as its carrier-sensing range, each node can conduct a successful broadcast to its neighbors. Meanwhile, the largest degree of spatial reuse can be achieved. Based on the obtained minICR, we propose a distributed algorithm DAB for data broadcasting in asynchronous WSNs. DAB takes a CDS-based routing tree as the broadcast backbone and propagates the messages among the nodes on the backbone using carrier-sensing and collision backoff. Theoretical analysis shows that DAB is order-optimal and achieves constant factor approximation to the optimal delay. We also conduct extensive simulations to evaluate the practical performance of DAB and the results reveal that DAB has similar performance to the latest centralized data broadcast algorithm. Several interesting questions are left for further research. The first one is to improve the approximation ratio of DAB. The second one is to design efficient broadcast algorithms with favourable performance for the original communication graph instead of the reduced one. The third one is to extend DAB for the more general Gaussian channel model [35].