Distributed wireless link scheduling in the SINR model

Abstract

We present an approximation algorithm for wireless link scheduling under the physical SINR interference model. In the link scheduling problem, it is given a set of $n$ links in a metric space, each of which is a sender–receiver pair, and the objective is to schedule the links using the minimum amount of time. We focus on a variant of this fundamental problem where the power is fixed, i.e., the power assignment of links is given as part of the input. Specifically, we consider an important category of power assignments called length-monotone sublinear power assignment, which includes the widely studied uniform, mean and linear power assignments. We present a distributed algorithm that can schedule all links in $O(\log \varDelta (I_{max}+\log ^3n))$ rounds with high probability, where $\varDelta$ is the ratio between the longest link and the shortest link and $I_{max}$ is the maximum nearly-equilength class affectance of the link set. It is shown that the proposed algorithm is $O(\log \varDelta )$ approximate to the optimal schedule in dense networks with $I_{max}\in \varOmega (\log ^3n)$. To the best of our knowledge, our algorithm is the first distributed one whose approximation ratio is independent of the network size $n$. Our result also shows that the $\varOmega (\log n)$ lower bound (Halldórsson and Mitra in: ICALP, 2011) on the approximation ratio does not hold for link sets with $\log \varDelta \in o(\log n)$.

1 Introduction

In wireless networks, concurrent transmissions may easily collide when they are within one another’s interference range. An efficient MAC protocol that can coordinate wireless transmissions in the face of interference is critically needed. Theoretically, designing an efficient MAC protocol boils down to finding a solution to the wireless link scheduling problem. Specifically, given a set $L$ of $n$ links in a wireless network, where a link represents a transmission request from one node (sender) to another (receiver), the link scheduling problem is to schedule the links using the minimum amount of time.

The complexity of link scheduling is dependent on the adopted interference model. In this paper, we study the link scheduling problem under the physical SINR interference model. The SINR model captures the fading feature and the cumulative effects of actual radio signals. Compared with oversimplified graph-based models, the SINR model represents the physical reality in wireless networks more precisely.

Wireless link scheduling under the SINR model has been extensively studied in centralized settings (Andrews and Dinitz 2009; Fanghänel et al. 2009, 2011; Goussevskaia et al. 2007; Halldórsson 2012; Halldórsson and Mitra 2011; Kesselheim 2011). But a distributed solution is more desirable, since in many real networks, e.g., wireless ad hoc and sensor networks, it is hard or impossible to provide a centralized controller or make individual nodes be aware of the overall network situation. Because of the ‘global-ness’ of the SINR model, practical distributed algorithms are difficult to derive, and so far only a few works (Kesselheim and Vöcking 2010; Halldórsson and Mitra 2011; Halldórsson et al. 2013) have existed offering distributed solutions. Under different settings, these works presented $O(\log n)$-like approximation algorithms for length-monotone sublinear power assignments or more restricted power assignments. For our work presented here, instead of the network size $n$, we use the special parameter $\varDelta$, which is the length ratio between the longest link and the shortest link, to express the efficiency of our algorithm. $\varDelta$ is widely adopted in link scheduling studies in centralized settings (e.g., Andrews and Dinitz 2009; Fanghänel et al. 2011; Goussevskaia et al. 2007; Halldórsson 2012). In fact, approximation algorithms with a ratio dependent on $\varDelta$ and not on the network size $n$ may be more attractive, since large link sets often have only a constant $\varDelta$ (Goussevskaia et al. 2007).

We consider the wireless link scheduling in networks whose nodes are limited in their functionalities. These nodes do not know their geometry coordinates, and cannot perform collision detection or physical carrier sensing. Furthermore, we assume the so called ack-only model (Halldórsson and Mitra 2011), which requires the receivers to send back the acknowledgements over the same channel as the message and there are no side-channels for control messages. Under such a harsh model, we focus on the link scheduling with fixed power assignment, i.e., the transmission power of each link is given as input, and present a randomized algorithm whose performance is guaranteed with high probability (with probability $1-n^{-c}$ for some constant $c$). In our algorithm, the receiver transmits the acknowledgement using the same assigned power as its sender. In contrast, in previous work, the receiver of a link transmits with dual power (Kesselheim and Vöcking 2010; Halldórsson and Mitra 2011). The dual power of a link $l_v$ is defined as $P^{*}(l_v)=\frac{P(l_{max})^{2}}{l_{max}^{\alpha }}\cdot \frac{l_v^{\alpha }}{P(l_v)}$, where $l_{max}$ is the length of the longest link, $P$ is the given power assignment and $\alpha$ is the constant path-loss exponent defined in the SINR model (refer to Sect. 3). Not only the dual power needs the information of the longest link (including the length and the assigned power of the longest link) to be defined, but also it can be very large in some power assignments, which is a great waste or even unaffordable for short links. For example, in a linear power assignment, where $P(l_v)=\gamma l_v^{\alpha }$ for some constant $\gamma >0$, the dual power of link $l_v$ can be as large as the maximum power assigned to links, which may be $\varDelta ^{\alpha }$ times of the assigned power $P(l_v)$. Clearly, an algorithm in which the sender and the receiver transmit with the same power is more desirable and is more suitable for implementing in a distributed environment, since links may not have exact knowledge on the link set.

Our result We focus on a category of power assignments that are called length-monotone sublinear power assignment. The length-monotone sublinear power assignment is a natural and important one, which covers the extensively studied uniform (Goussevskaia et al. 2007), mean (Fanghänel et al. 2009) and linear (Fanghänel et al. 2011) power assignments. All previous work on distributed link scheduling tried to work with this important category of power assignments. We present a distributed algorithm that generates a schedule longer than the optimal one by at most an $O(\log \varDelta )$ factor in dense networks. The performance of the proposed algorithm is guaranteed with high probability. Our understanding is that this is the first distributed algorithm whose approximation ratio is dependent on $\varDelta$, rather than $n$. The proposed algorithm also demonstrates that the general lower bound $\varOmega (\log n)$ (Halldórsson and Mitra 2011) for the approximation ratio of distributed link scheduling algorithms does not hold for link sets with $\log \varDelta \in o(\log n)$.

2 Related work

The scheduling complexity of arbitrary links in centralized settings has been extensively studied. The wireless scheduling problem is closely related to the capacity problem, also known as single slot scheduling problem, which is to find the maximum number of links that can communicate simultaneously. The capacity problem has been well studied in Andrews and Dinitz (2009), Asgeirsson and Mitra (2011), Chafekar et al. (2007), Dinitz (2010), Goussevskaia et al. (2009), Goussevskaia et al. (2007), Halldórsson and Mitra (2011), Kesselheim (2011). Approximation algorithms for the capacity problem can be adapted to solving the scheduling problem with an extra $O(\log n)$ factor in approximation ratio. Recently, there are many results in the literature that achieve $O(\log \varDelta )$-like approximation. Goussevskaia et al. (2007) gave an $O(\log \varDelta )$-approximation algorithm for both the scheduling and the capacity problem assuming the uniform power assignment. But the approximation ratio is obtained under the uniform power setting. Using an extra small step to relate the algorithm (Goussevskaia et al. 2007) to the optimal solution with power control, an $O(\log \varDelta )$-approximation algorithm can be obtained for the capacity problem, as given in Andrews and Dinitz (2009). Fanghänel et al. (2011) proposed the maximum affectance $I$ as a measure of interference, and proposed a randomized algorithm with linear power assignment that schedules an arbitrary set of links in $O(OPT\log \varDelta +\log ^2n)$ rounds. Thus, their results achieve an $O(\log \varDelta )$ approximation ratio for dense networks. Fanghänel et al. (2009) showed that any schedule based on oblivious power assignment can be a factor of $\varOmega (n)$ from the optimal. The lower bound comes from the asymmetry of the communication links. They introduced a bi-directional version of the wireless link scheduling problem, where the endpoints of each link are both sender and receiver. Under this symmetric model and using the mean power assignment, they gave an algorithm with approximation ratio $O(\log ^{3.5+\alpha } n)$ in general metrics. This result was improved to an $O(\log n)$-factor for doubling metrics in Halldórsson (2012). In terms of $\varDelta$, the lower bound is shown to be $O(\log \log \varDelta )$ in Halldórsson (2012) for any oblivious power assignment. Using the mean power assignment, Halldórsson (2012) also gave an $O(\log \log \varDelta \cdot \log n)$-approximation scheduling algorithm without the bi-directional setting in doubling metrics.

For the fixed given power case, Goussevskaia et al. (2009) gave an $O(\log n)$-approximation algorithm based on a constant approximation algorithm for the capacity problem when uniform power and Euclidean space are assumed. Both problems have been shown to be NP-complete in Goussevskaia et al. (2007). In terms of linear power assignment, a constant approximation algorithm was given in Fanghänel et al. (2011) for dense networks. For length-monotone sublinear power assignments, in a recent work, Halldórsson and Mitra (2011) gave an $O(\log n)$-approximation algorithm in general metrics.

There are only a few works considering distributed solutions for scheduling an arbitrary set of links in wireless networks. In Kesselheim and Vöcking (2010), assuming length-monotone sublinear power assignments, Kesselheim and Vöking gave the first known distributed wireless link scheduling algorithm with approximation ratio $O(\log ^2n)$. Under the same category of power assignments, the result was improved to $O(\log n)$ in Halldórsson and Mitra (2011), Halldórsson et al. (2013). In Halldórsson and Mitra (2011), it was also shown that $\varOmega (\log n)$ is a lower bound in general.

3 Network model and preliminaries

Given a set of links $L=\{l_1,\ldots ,l_n\}$ in a metric space $(X,d)$ where each link $l_v=(s_v,r_v)$ represents a communication request from a sender $s_v$ to a receiver $r_v$, the link scheduling problem is to find a partition of L of minimum size such that links of each subset in the partition can be scheduled together. The size of the partition is equal to the minimum number of slots required to schedule all links. A subset $S\subseteq L$ is called a feasible set if all links in $S$ can be scheduled together. Without confusion, we also use $l_v$ to denote the length of link $l_v$. For the link set $L$, let $\varDelta (L)$ be the ratio between the longest link and the shortest link in $L$. A nearly-equilength class is a set $R$ of links with $\varDelta (R)\le 2$. Any set $L$ of links can be divided into $\lceil \log \varDelta (L)\rceil$ nearly-equilength classes. To ease the algorithm description and the analysis, without loss of generality, we set the minimum length of links to 1. Then $\varDelta$ is simply the length of the longest link in $L$. For two links $l_v$ and $l_w$, we use $d(v,w)$ or simply $d_{vw}$ to denote the distance $d(s_v,r_w)$ from the sender $s_v$ of $l_v$ to the receiver $r_w$ of $l_w$.

We model the interference using the physical SINR (Signal-to-Interference-plus-Noise-Ratio) model. Let $P_v$ denote the power assigned to link $l_v$, or, in other words, $s_v$ transmits with power $P_v$. A node $r_v$ successfully receives a message from a sender $s_v$ if and only if the following condition holds:

$$\begin{aligned} \frac{P_v/l_v^\alpha }{N+\sum _{l_w\in V\setminus \{l_v\}}P_w/d(w,v)^\alpha }\ge \beta , \end{aligned}$$

(1)

where $\alpha >0$ is the path-loss exponent, $N$ is the constant ambient noise, S is the set of concurrently scheduled links in the same slot and $\beta$ is a constant threshold set by the hardware. Here we assume that $\beta >2^{\alpha }$.

We focus on an important power assignment that is called length-monotone sublinear power assignment (Kesselheim and Vöcking 2010). A power assignment $P$ is length-monotone if for any two links $l_u\le l_v$, $P_u\le P_v$, and $P$ is sub-linear if $\frac{P_u}{l_u^{\alpha }}\ge \frac{P_v}{l_v^{\alpha }}$ for any two links $l_u\le l_v$. Two widely used power assignments in this class are the uniform power assignment, where every link transmits with the same power; and the linear power assignment, where $P_v$ is proportional to $l_v^{\alpha }$.

All communications occur on a shared channel. Algorithms operate in synchronous rounds with the senders either transmitting or listening in each round. When the transmission is successful, the sender stops transmitting. This necessitates an acknowledgment from the receiver, so that the sender knows when his message has been heard. These acknowledgments are sent over the same channel as the message; thus, there are no side-channels for control messages. Furthermore, we restrict that the sender and the receiver of a link use the same transmission power assigned to the link.

Initially, nodes (senders and receivers) do not know their geometric coordinates, and know nothing about other links in their close proximity. The only initial knowledge to nodes are estimates of $\varDelta (L)$ and $n$. As shown in the analysis, polynomial estimates are enough, which will only affect the final result by a constant factor.

We will use the notion of affectance, introduced in Goussevskaia et al. (2009), Halldórsson and Wattenhofer (2009) and refined in Kesselheim and Vöcking (2010) as the thresholded form here. The affectance on a link $l_v$ caused by link $l_w$ under a power assignment $P$ is defined as

$$\begin{aligned} a_w(v)=\min \left\{ 1,c_v\frac{P_w/d_{wv}^{\alpha }}{P_v/l_v^\alpha }\right\} =\min \left\{ 1, c_v\frac{P_w}{P_v}\cdot \left( \frac{l_v}{d_{wv}}\right) ^{\alpha }\right\} , \end{aligned}$$

(2)

where $c_v=\beta /(1-\beta Nl_v^\alpha /P_v)$. The affectance on link $l_v$ caused by a set of links $S$ is denoted by $a_S(v)=\sum _{l_w\in S}a_w(v)$. For a set $R\subseteq L$, the maximum affectance of $R$ is defined as $I_R=\max _{l_v\in R}a_R(v)$. Denote by $\mathbb {R}$ the set of the $\lceil \log \varDelta \rceil$ nearly-equilength link classes of $L$, where links in the $i$-th nearly-equilength class have length in the range $[2^{i-1},2^i)$. Then we define the maximum nearly-equilength class affectance $I_{max}=\max _{R\in \mathbb {R}}I_R$.

With the definition of affectance, note that the SINR model prescribes that a link $l_v$ can be successfully scheduled if $a_R(v)\le 1$, where $R$ is the set of links simultaneously scheduled.

At the end of this section, we present two Chernoff bounds, as in the following Lemma 1 and Lemma 2. The Chernoff bound in Lemma 1 can be found in Dubhashi and Ranjan (1998), and the weighted Chernoff bound in Lemma 2 is proved in Fanghänel et al. (2011).

Lemma 1

For a parameter $a > 0$, let $X_1,\ldots ,X_n$ be independent or negatively associated non-negative random variables with $X_i\le a$. Further, let $X=X_1+\cdots +X_n$ and $\mu =E[X]$. For $0<\epsilon <1$, it holds that

$$\begin{aligned} Pr[X\le (1-\epsilon )\mu ]\le e^{-\epsilon ^2\mu /2a}. \end{aligned}$$

(3)

Lemma 2

Let $X_1,\ldots ,X_n$ be 0/1 random variables for which there is a $p\in [0,1]$ such that for all $k\in [n]$ and all $a_1,\ldots ,a_{k-1}\in \{0, 1\}$, $Pr[X_k = 1 | X_1 = a_1,\ldots ,X_{k-1}=a_{k-1}]\le p$. Let furthermore $w_1,\ldots , w_n$ be reals in $(0, 1]$ and $\mu \ge p\sum w_i$. Then for $\epsilon >0$,

$$\begin{aligned} Pr\left[ \sum _{i=1}^{n}w_iX_i\ge (1+\delta )\mu \right] \le \left( \frac{e^{\epsilon }}{(1+\epsilon )^{1+\epsilon }}\right) ^{\mu }. \end{aligned}$$

(4)

4 Link scheduling algorithm

In this section, we present a distributed link scheduling algorithm in which each link executes the algorithm only based on its own length. The detailed algorithm is given in Algorithm 1. We divide the links into $\lceil \log \varDelta \rceil$ nearly-equilength classes $\{L_i\}$, where $L_i$ denotes the set of links whose lengths are in the range $[2^{i-1},2^i)$. A link $l_v$ is called unsuccessful if the sender still does not receive the ack message from the receiver $r_v$. In Algorithm 1, we denote by $[\lceil \delta A\rceil ]$ the positive integers $\{1,2,\ldots ,\lceil \delta A\rceil \}$.

The algorithm execution is divided into stages (line 2–29) and each stage is further divided into $\lceil \log \varDelta \rceil$ phases (line 3–27). In each stage, links in $L_i$ execute the algorithm in the $i$-th phase. So links in the same nearly-equilength class execute the algorithm together. In each subphase (line 6–18) of phase $i$, each unsuccessful link in $L_i$ selects a random delay in a range determined by an estimate of the maximum nearly-equilength class affectance. Links with the same delay execute the algorithm together in the round after the delay. The round consists of two slots. In the first slot, the sender $s_v$ transmits. And in the second slot, the receiver $r_v$ transmits with a constant probability $\hat{p}$ if $r_v$ received the transmission of $s_v$. Senders that receive the acknowledgement from their receivers stop transmitting from then on. The adjustment of the affectance estimate uses a back on/back off manner: After each stage, the estimate is doubled and after each subphase, the estimate is decreased by a constant factor. Furthermore, there is a clean-up subphase (line 20–26) at the end of each phase for dealing with the case that the affectance on unscheduled links is small.

4.1 Algorithm analysis

In this section, we analyze the correctness and the time complexity of Algorithm 1. In particular, we will show that after $O(\log \varDelta (I_{max}+\log ^3n))$ rounds, all links will be scheduled with high probability.

For a link $l_v=(s_v,r_v)$, define the dual link $l_v^{*}$ of $l_v$ as $l_v^{*}=(r_v,s_v)$. The dual link is introduced in Kesselheim and Vöcking (2010). For a link set $S$, its dual link set is denoted as $S^{*}=\{l_v^{*}|l_v\in S\}$. We use $a_{u^{*}}(v^{*})$ to denote the affectance on $l_v^{*}$ caused by $l_u^{*}$ under the given power assignment. We first present an observation on dual link sets.

Observation 1

For a feasible link set $S$ which is nearly-equilength, $I_{S^{*}}\le \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }$.

Proof

The proof is based on the following key claim. $\square$

Claim 3

For two link $l_u,l_v\in S$, $a_{u^{*}}(v^{*})\le \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }a_u(v)$.

Proof

By the given power assignment, $\frac{1}{2^\alpha }P_v\le P_u\le 2^\alpha P_v$. Because $l_u$ and $l_v$ can be scheduled together, by the SINR condition, we have $d(s_u,r_u)\le \frac{2}{\beta ^{1/\alpha }}d(s_v,r_u)$ and $d(s_v,r_v)\le \frac{2}{\beta ^{1/\alpha }}d(s_u,r_v)$. We then can get that

$$\begin{aligned} d(s_u,r_v)\le & {} d(s_u,r_u)+d(r_u,s_v)+d(s_v, r_v)\nonumber \\\le & {} \frac{2}{\beta ^{1/\alpha }}d(s_v,r_u)+d(s_v,r_u)+\frac{2}{\beta ^{1/\alpha }}d(s_u,r_v). \end{aligned}$$

(5)

With the above inequality, $d(s_v,r_u)\ge \frac{\beta ^{1/\alpha }-2}{\beta ^{1/\alpha }+2}d(s_u,r_v)$. Then

$$\begin{aligned} \begin{aligned} a_{u^{*}}(v^{*})&=c_v\frac{P_u}{P_v}\cdot \left( \frac{d(r_v,s_v)}{d(r_u,s_v)}\right) ^{\alpha }\\&\le \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }\cdot c_v\frac{P_u}{P_v}\cdot \left( \frac{d(s_v,r_v)}{d(s_u,r_v)}\right) ^{\alpha }\\&=\left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }a_{u}(v). \end{aligned} \end{aligned}$$

(6)

$\square$

By the feasibility of $S$, $I_S=\max _{l_v}a_S(v)\le 1$. By Claim 3, we can get that

$$\begin{aligned} I_{S^{*}}=\max _{l_v}\sum _{l_u\in S}a_{u^{*}}(v^{*})\le \max _{l_v}\sum _{l_u\in S}(\frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2})^{\alpha }a_{u}(v)\le \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }. \end{aligned}$$

(7)

The above observation shows that the dual link set of a nearly-equilength feasible set is nearly feasible (with constant maximum affectance).

Now we start analyzing the algorithm’s performance. Consider phase $i$ of a stage. By the algorithm, links in $L_i$ execute the algorithm in this phase. We next show the reduction of the maximum affectance of $L_i$ after each subphase of phase $i$. Consider a subphase in phase $i$. If it is clear in the context, we use $L_i$ to denote the set of unsuccessful links in $L_i$ at the beginning of the subphase, and use $L_i^{'}$ to denote the set of unsuccessful links in $L_i$ after the subphase.

Lemma 4

Consider a subphase in the $i$-th phase of a stage. If $A\ge I_{L_i}$ and $I_{L_i}>\sigma \log n$, where $\sigma$ is a constant defined in Algorithm 1, then after the subphase, $I_{L^{'}_i}\le (1-\hat{p}/8)I_{L_i}$ with probability $1-O(n^{-3})$.

Proof

A link $l_v=(s_v,r_v)\in L_{i}$ does not stop the execution of the algorithm during a subphase for two reasons: First, the affectance on $l_v$ is larger than 1 such that $r_v$ does not receive the transmission; second though $s_v$ successfully transmits its message to $r_v$, $s_v$ does not receive an ack message from $r_v$. We next bound the affectance on a link $l_w$ after the subphase caused by links that are unsuccessful for these two reasons, respectively. Clearly, we only need to consider links $l_w$ with $a_{L_i}(w)> (1-\hat{p}/8)I_{L_i}$. Divide $L_i$ into two sets $R_1$ and $R_2$, where $R_1$ is the set of links that are unsuccessful for the first reason and $R_2=L_i{\setminus }R_1$. $\square$

We first consider the affectance on $l_w$ caused by links in $R_1$. Denote by ${\mathcal {E}}_1$ the random variable whose value is $\sum _{l_v\in R_1}a_v(w)$.

Claim 5

$Pr[{\mathcal {E}}_1\ge \frac{\hat{p}}{8}I_{L_i}]\le O(n^{-4})$.

Proof

We use the Chernoff bound of Lemma 2 to prove the result. We first give an arbitrary order on all links in $L_i$ and denote $L_i=\{l_1,l_2,\ldots , l_t\}$. Consider an arbitrary link $l_k=(s_k,r_k)\in L_i$. Let $S$ be the set of links that are scheduled together with $l_k$. Denote by $S_k^{-}$ and $S_k^{+}$ be the sets of links $l_j$ in $S$ with $j<k$ and $j>k$ respectively. If $s_k$ does not send the message to $r_k$, it means that $\sum _{l_j\in S_k^{-}}a_{j}(k)>\frac{1}{2}$ or $\sum _{l_j\in S_k^{+}}a_{j}(k)>\frac{1}{2}$. In the first case let the indicator $X_k^{-}=1$ and in the second case let the indicator $X_k^{+}=1$.

We next show that the random variables $\{X_k^{-}\}$ fulfill the condition of the Chernoff bound of Lemma 2. It is easy to see that the values of $X_1^{-},\ldots ,X_k^{-}$ are determined by the delays $d_1,\ldots ,d_{k}$, where $d_j$ is the delay selected by link $l_j$ for $1\le j\le k$. Fix $a_1,\ldots , a_{k-1}\in \{0,1\}$. Let $[\lceil \delta A\rceil ]^{k-1}$ be the set of vectors $(v_1,\ldots ,v_{k-1})$ with $1\le v_i\le \lceil \delta A\rceil$ for $1\le i\le k-1$. Then there exists a subset $H\subseteq [\lceil \delta A\rceil ]^{k-1}$ such that $X_1^{-}=a_1,\ldots ,X_{k-1}^{-}=a_{k-1}$ iff $(d_1,\ldots ,d_{k-1})\in H$.

For $1\le j\le k$, let $Y_j$ be the random variable with value 1 if $d_j=d_k$ and 0 otherwise, where $d_k$ is the delay selected by link $l_k$. Define $Z_k^{-}=\sum _{j=1}^{k-1}a_{j}(k)Y_j$. Because each link selects the delay independently and uniformly at random from $[\lceil \delta A\rceil ]$, we can get that for all $(b_1,\ldots ,b_{k-1})\in [\lceil \delta A\rceil ]^{k-1}$,

$$\begin{aligned} E[Y_j|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}]=\frac{1}{\lceil \delta A\rceil }. \end{aligned}$$

(8)

Then we can get that

$$\begin{aligned} \begin{aligned} E[Z_k^{-}|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}]&=\sum _{j=1}^{k-1}a_j(k)E[Y_j|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}]\\&= \frac{1}{\lceil \delta A\rceil }\sum _{j=1}^{k-1}a_j(k)\\&\le \frac{1}{\delta } \end{aligned} \end{aligned}$$

(9)

Based on the above, we obtain that

$$\begin{aligned} \begin{aligned}&Pr[X_k^{-}=1|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}] =Pr\\&\quad \left[ \sum _{l_j\in S_k^{-}}a_{j}(k)>\frac{1}{2}|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}\right] \\&\le 2E[Z_k^{-}|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}]\\&\le 2\delta ^{-1}. \end{aligned} \end{aligned}$$

(10)

Now we can compute $Pr[X_k^{-}=1|X_1^{-}=a_1,\ldots ,X_{k-1}^{-}=a_{k-1}]$ as follows.

$$\begin{aligned} \begin{aligned}&\ \ \ \ Pr\left[ X_k^{-}=1|X_1^{-}=a_1,\ldots ,X_{k-1}^{-}=a_{k-1}\right] \\&=\sum _{(b_1,\ldots ,b_{k-1})\in H}Pr\left[ X_k^{-}=1|d_1=b_1,\ldots ,d_{k-1}=b_{k-1}\right] \\&\ \ \ \ \cdot Pr\left[ d_1=b_1,\ldots ,d_{k-1}=b_{k-1}|X_1^{-}=a_1,\ldots ,X_{k-1}^{-}=a_{k-1}\right] \\&\le \frac{2}{\delta }. \end{aligned} \end{aligned}$$

(11)

Define the random variable $A_w^{-}=\sum _{j=1}^{t}X_j^{-}a_j(w)$. Set $p=\frac{2}{\delta }$ and $\mu =\frac{2a_{L_i}(w)}{\delta }$. By the Chernoff bound in Lemma 2, we can get that

$$\begin{aligned} Pr\left[ A_w^{-}\ge \frac{\hat{p}}{16}a_{L_{i}}(w)\right] \le 2^{-\frac{\hat{p}}{16}a_{L_{i}}(w)}\le 2^{-\frac{\hat{p}}{16}(1-\frac{\hat{p}}{8})I_{L_{i}}}\le n^{-4}. \end{aligned}$$

(12)

By using a similar argument, we can get the bound for $A_w^{+}=\sum _{j=1}^{t}X_j^{+}a_j(w)$ which is $Pr[A_w^{+}\ge \frac{\hat{p}}{16}a_{L_{i}}(w)]\le n^{-4}$. Clearly, ${\mathcal {E}}_1\le A_w^{+}+A_w^{-}$. Thus,

$$\begin{aligned} Pr\left[ {\mathcal {E}}_1\ge \frac{\hat{p}}{8}a_{L_{i}}(w)\right] \le Pr\left[ A_w^{+}\ge \frac{\hat{p}}{16}a_{L_{i}}(w)\right] +Pr[A_w^{-}\ge \frac{\hat{p}}{16}a_{L_{i}}(w)]\le O(n^{-4}). \end{aligned}$$

(13)

$\square$

We next consider the affectance on $l_w$ caused by unsuccessful links in $R_2$. For each link $l_v\in R_2$, define a random variable $Z_v$ with value $a_v(w)$ if $r_v$ successfully transmits the ack message and 0 otherwise. Let $Z=\sum _{l_v\in R_2}Z_v$ and ${\mathcal {E}}_2=I_{L_i}-Z$. Clearly, ${\mathcal {E}}_2$ is an upper bound for the affectance on $l_w$ caused by unsuccessful links in $R_2$.

Claim 6

$Pr[{\mathcal {E}}_2\ge (1-\frac{\hat{p}}{4})I_{L_i}]\le O(n^{-4})$.

Proof

Let $l_v$ be an arbitrary link in $R_2$, and denote by $M\subseteq R_2$ the set of links that select the same delay with $l_v$. For each other link $l_u\in M$, by Claim 3, $a_{u^{*}}(v^{*})\le \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }a_u(v)$, which concludes that

$$\begin{aligned} E\left[ \sum _{l_u\in M}a_{u^{*}}(v^{*})\right] \le \hat{p}\cdot \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }\sum _{l_u\in M}a_u(v)\le \hat{p}\cdot \left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }\le \frac{1}{2}. \end{aligned}$$

(14)

By Markov inequality, with probability $\frac{1}{2}$, $\sum _{l_u\in M}a_{u^{*}}(v^{*})\le 1$. In other words, with probability $1/2$, if the receiver $r_v$ of $l_v$ transmits, $s_v$ will receive the ack message. Then we can get that

$$\begin{aligned} E[Z_v]\ge \frac{\hat{p}}{2}\cdot a_v(w). \end{aligned}$$

(15)

by which it can be obtained that $E[Z]\ge \frac{\hat{p}}{2}\sum _{l_v\in R_2}a_v(w)$. By Inequality (13), with probability $1-O(n^{-4})$, $\sum _{l_v\in R_2}a_v(w)\ge (1-\frac{\hat{p}}{8})a_{L_{i}}(w)\ge (1-\frac{\hat{p}}{8})^2I_{L_i}$. Thus,

$$\begin{aligned} E[Z]\ge \frac{\hat{p}}{2}\left( 1-\frac{\hat{p}}{8}\right) ^2I_{L_i}\ge \frac{3\hat{p}}{8}\cdot I_{L_i}. \end{aligned}$$

(16)

Because $\{Z_v\}$ are negatively associated, we can apply the Chernoff bound of Lemma 1 with $a=1$ to get that

$$\begin{aligned} Pr\left[ Z\le \frac{\hat{p}}{4}I_{L_i}|E[Z]\ge \frac{3\hat{p}}{8}\cdot I_{L_i}\right] \le e^{-\frac{(1/3)^2\cdot (3\hat{p} I_{L_i}/8)}{2}}\le n^{-4}. \end{aligned}$$

(17)

Then we can get that $Pr[{\mathcal {E}}_2< (1-\frac{\hat{p}}{4})I_{L_i}]=Pr[Z> \frac{\hat{p}}{4}I_{L_i}]\ge 1-O(n^{-4})$. $\square$

Now we are ready to prove the lemma. Clearly, $a_{L^{'}_i}(w)\le {\mathcal {E}}_1+{\mathcal {E}}_2$. By Claim 5 and Claim 6,

$$\begin{aligned} \begin{aligned} Pr\left[ a_{L^{'}_i}(w)\ge (1-\frac{\hat{p}}{8})I_{L_i}\right]&\le Pr\left[ {\mathcal {E}}_1\ge \frac{\hat{p}}{8}I_{L_i}\right] +Pr\left[ {\mathcal {E}}_2\ge (1-\frac{\hat{p}}{4})I_{L_i}\right] \\&\le O(n^{-4}). \end{aligned} \end{aligned}$$

(18)

The above bound is true for all links in $L_i$ with probability $1-O(n^{-3})$. So $I_{L_{i}^{'}}\le (1-\frac{\hat{p}}{8})I_{L_{i}}$ holds with probability $1-O(n^{-3})$.

We next show that if the maximum affectance of a nearly-equilength class is small, all links will be successfully scheduled in the clean-up subphase.

Lemma 7

For the link set $L_i$, if $I_{L_i}\le \sigma \log n$, where $\sigma$ is a constant defined in Algorithm 1, then all links in $L_i$ will be successfully scheduled in the the clean-up subphase with probability $1-n^{-2}$.

Proof

Consider a round $r$ in the clean-up subphase. Let $R$ be the set of unsuccessful links in $L_i$ at the beginning of $r$. $\square$

Claim 8

In the first slot of round $r$, at least $\frac{p_c|R|}{2}$ links can successfully transmit their messages in expectation.

Proof

For each link $l_v\in R$, let $Z_v$ be the indicator with value 1 if $s_v$ transmits in the considered slot. Let $Z^{'}_v$ be the random variable with value 1 if $s_v$ sends the message to $r_v$ and 0 otherwise. By the algorithm, $Pr[Z_v=1]=p_c$ and $E[a_{R}(v)]=\sum _{l_w\in R}a_w(v)p_c\le p_c\cdot I_{L_i}\le \frac{1}{2}$. By the Markov inequality,

$$\begin{aligned} Pr[a_{R}(v)\le 1]\ge \frac{1}{2}. \end{aligned}$$

(19)

In other words, $s_v$ can send its message to $r_v$ with probability at least $\frac{1}{2}$ if it transmits. Then,

$$\begin{aligned} Pr[Z^{'}_v=1]=Pr[Z^{'}_v=1|Z_v=1]Pr[Z_v=1]\ge \frac{p_c}{2}. \end{aligned}$$

(20)

The number of successful transmissions is

$$\begin{aligned} E\left[ \sum _{l_w\in R}Z^{'}_w\right] =\sum _{l_w\in R}E\left[ Z^{'}_w\right] =\sum _{l_w\in L_i} Pr\left[ Z^{'}_w=1\right] \ge \frac{p_c|R|}{2}. \end{aligned}$$

(21)

$\square$

Let $R^{'}\subseteq R$ be the set of links that successfully transmit in the first slot of the considered round. By Observation 1, the maximum affectance on $R^{'}$ is $\left( \frac{\beta ^{1/\alpha }+2}{\beta ^{1/\alpha }-2}\right) ^{\alpha }$. Then using a similar argument to that for proving Claim 8, we can get the following result.

Claim 9

In the second slot of round $r$, at least $\frac{\hat{p}|R^{'}|}{2}$ links in expectation whose receivers can send ack messages to their senders.

Let $R_t$ be the set of unsuccessful links in $L_i$ after round $t$. By the above two claims, after round $r$, $\frac{p_c\cdot \hat{p}|R_t|}{4}$ links can be successfully scheduled in expectation. Thus,

$$\begin{aligned} E[R_{t+1}]= & {} \sum _{k=1}^{\infty }Pr[R_t=k]\cdot (1-\frac{p_c\cdot \hat{p}}{4})k=(1-\frac{p_c\cdot \hat{p}}{4})\sum _{k=1}^{\infty }Pr[R_t=k]\cdot \\ k= & {} (1-\frac{p_c\cdot \hat{p}}{4})E[R_t]. \end{aligned}$$

After $24\hat{p}^{-1}\sigma \log ^2n$ rounds, $E[R_{24\hat{p}^{-1}\sigma \log ^2n}]\le (1-\frac{p_c\cdot \hat{p}}{4})^{24\hat{p}^{-1}\sigma \log ^2n}\cdot n\le n^{-2}$, and

$$\begin{aligned} Pr[R_{24\hat{p}^{-1}\sigma \log ^2n}>0]=Pr[R_{24\hat{p}^{-1}\sigma \log ^2n}\ge 1]\le E[R_{24\hat{p}^{-1}\sigma \log ^2n}]\le n^{-2}, \end{aligned}$$

which completes the proof.$\square$

Theorem 2

Algorithm 1 schedules all links in $O(\log \varDelta (I_{max}+\log ^3n))$ rounds with probability $1-O(n^{-1})$, where $I_{max}$ is the maximum nearly-equilength class affectance.

Proof

If $I_{max}\le \sigma \log n$, by the algorithm and Lemma 7, with probability $1-n^{-1}$, all links will be scheduled in $O(\log \varDelta \log ^2n)$ rounds noting that there are at most $n$ non-empty nearly-equilength classes. In the following, we assume that $I_{max}> \sigma \log n$.

Consider the stage $T$ with $I_e\in [I_{max}, 2I_{max})$. For each nearly-equilength class $L_i$, using Lemma 4, it is easy to inductively prove that after $O(\log (I_{max}/\log n))$ subphases, with probability $1-O(n^{-2})$, the maximum affectance of unsuccessful links in $L_i$ will be reduced to be less than $\sigma \log n$. Then by Lemma 7, all remaining links in $L_i$ will be scheduled in the subsequent clean-up phases with probability $1-n^{-2}$. Thus, all links in $L_i$ will be scheduled by the end of phase $i$ of stage $T$ with probability $1-O(n^{-2})$. Note that there are at most $n$ non-empty nearly-equilength classes. By the union bound, all links will be scheduled by the end of stage $T$ with probability $1-O(n^{-1})$.

Now we bound the running time by stage $T$. In a stage $j\le T$ with estimate $I_j$, the running time of this stage is upper bounded by

$$\begin{aligned} \lceil \log \varDelta \rceil \left( \sum _{i=0}^{O\left( \log \left( I_j/\log n\right) \right) }\left( 1-\frac{\hat{p}}{8}\right) ^{i}I_j+O\left( \log ^2n\right) \right) =O\left( \log \varDelta \left( I_j+\log ^2n\right) \right) . \end{aligned}$$

Then the running time by stage $T$ is at most

$$\begin{aligned}&\displaystyle \sum \limits _{i=0}^{O\left( \log \left( I_{max}/\log n\right) \right) }O\left( \log \varDelta \left( \left( \frac{1}{2}\right) ^{i}\cdot 2\delta I_{max}+\log ^2n\right) \right) \\&\quad =O\left( \log \varDelta \left( I_{max}+\log I_{max}\log ^2n\right) \right) . \end{aligned}$$

By the definitions of $I_{max}$ and the affectance, $I_{max}\le n$, which help complete the proof. $\square$

4.2 Comparison to the optimal schedule

In the following, we give a lower bound for scheduling all links in a nearly-equilength class.

Lemma 10

Let $R$ be a nearly-equilength class of links. Given a length-monotone sublinear power assignment on $R$, any scheduling algorithm needs $\varOmega (I_R)$rounds to schedule all links in $R$, where $I_R$ is the maximum affectance of $R$.

Proof

Let $S=\{S_1,\ldots ,S_T\}$ be a scheduling of $R$. The following Claim is proved in Ásgeirsson et al. (2012). $\square$

Claim 11

Consider a feasible set $R^{'}\subseteq R$ and a link $l_v$ (not necessarily a member of $R^{'}$). Then

$$\begin{aligned} a_{R^{'}}(v)=\sum _{l_w\in R^{'}}a_w(v)\le \kappa , \end{aligned}$$

(22)

for some constant $\kappa$.

For each link $l_v\in R$, $a_R(v)=\sum _{i=1}^{T}a_{S_i}(v)$. By the above Claim, $a_R(v)\le \kappa T$. It follows that $I_R=\max _{l_v\in R}a_{R}(v)\le \kappa T$, which completes the proof.

Lemma 10 shows that given a link set $L$ and a length-monotone sublinear power assignment, any scheduling algorithm needs $\varOmega (I_{max})$ rounds to schedule all links in $L$. By Theorem 2, we have the following result.

Theorem 3

For any given link set and length-monotone sublinear power assignment, Algorithm 1 achieves an approximation ratio of $O(\log \varDelta )$ in dense networks with $I_{max}\in \varOmega (\log ^3n)$.

5 Conclusion

Assuming the physical SINR model and for the length-monotone sublinear power assignment, we gave an efficient distributed algorithm for wireless link scheduling whose approximation ratio is independent of the network size. Our work shows that it is possible to design algorithms with approximation ratio better than $O(\log n)$ in many cases in spite of the $\varOmega (\log n)$ lower bound in general. One interesting question is whether $O(\log \varDelta )$ approximation is the best possible, or we can get faster algorithms. It is also meaningful to adapt the link scheduling algorithm given in this work to solve more sophisticated problems in wireless networks, such as broadcast (Min et al. 2006), gossiping (Shi and Srimani 2006), information dissemination (Wang et al. 2014; Yan et al. 2014) and data aggregation (Li et al. 2013).