Approximation Algorithms for Maximum Link Scheduling under SINR-Based Interference Model

Abstract

A fundamental problem in wireless networks is the maximum link scheduling (MLS) problem. In this problem, interference is a key issue and past researchers have shown that determining reception using Signal-to-Interference plus Noise Ratio (SINR) is more realistic than graph-based interference models. Unfortunately, the MLS problem has been proven to be NP-hard for SINR interference models. To date, several approximation algorithms have been proposed to solve MLS under the SINR-based interference model. However, most of these works do not have either an approximation bound or a distributed version. To this end, we present a novel scheduling method with a constant approximation ratio which is much simpler and only 1/28 of it in past research. The improvement of constant ϕ also offers a better MLS set. In addition, based on our centralized method, we present a polynomial time, randomized, distributed algorithm, which only requires estimates of the number of links, and maximum and minimum link lengths. We prove its correctness and show that it can compute a MLS with time complexity of $O(\text{lo}{\text{g}}^{2}n)$ , where n is an estimate of the number of links.

1. Introduction

The capacity of a wireless network is directly proportional to the number of transmitting links in a certain time. This problem, called maximum link scheduling (MLS), can be succinctly described as follows: given a set of communication links L, derive a set S with maximum cardinality, where $S\subseteq L$ . The key constraint is that links in S can be activated simultaneously only if the respective receiver of each transmission is able to receive correctly or with high probability; MLS is also referred to as one-slot scheduling [1] or maximum independent link set problem [2]. Unfortunately, this problem is made difficult by interference, an inherent characteristic of wireless transmissions. Unlike wired networks, signal interference bounds the maximum number of concurrent transmissions. Like other well-known scheduling problems (e.g., maximum throughput scheduling), MLS becomes NP-hard to solve when considering wireless interference, while similar problems in wired networks are solvable in polynomial time.

Past research on MLS has used different interference models, most of which are graph-based, for example, protocol interference and RTS/CTS models [3]. In a graph-based model, interference-free communications can be achieved by applying a coloring method on a conflict graph [4]. This model has produced a number of interesting results; see [4–8], but they are limited due to the overly idealistic assumption. To this end, in recent years, a more realistic interference model based on Signal-to-Interference plus Noise Ratio (SINR) has gained a lot of interest. Here, a signal is received successfully if the SINR at a receiver is above a threshold, which is set according to hardware and coding method. For example, in IEEE 802.11b, the minimum SINR corresponding to 11 and 1 Mbps are 10 and 4 dB, respectively [9].

Recently, many models and protocols have been proposed to solve the link scheduling problem in wireless networks. They can be grouped into two types: scheduling the largest set of noninterfering links from a given set (maximum link scheduling) and scheduling a given set of links using the smallest time length (minimum length scheduling). These problems are well understood when a wireless network is represented as a graph, where, given an interference range for each node, concurrent transmitting links are required to be outside. Graph-based scheduling algorithms usually employ coloring on the resulting conflict graph [4]. However, their performance is not ideal when nodes’ reception is governed by a SINR model. This is well documented and has been shown theoretically as well as experimentally; see [10, 11].

The MLS problem over the SINR-based interference model is more challenging and has received a lot of interest recently. Goussevskaia et al. [12] proved that the MLS problem over the uniform power assignment is NP-hard and developed a $g(L)$ -approximation algorithm, where $g(L)$ is the link diversity; see Section 2.2. The first constant approximation algorithm for MLS problem is proposed in [1]. However, as observed by Xu and Tang [13], its approximation bound and corresponding proof (Lemma  4.5 in [1]) are only correct in the absence of background noise. This motivated them to propose a new algorithm using the method in [1] to select independent links from a subset of short links, as per Euclidean distance. Yet, as shown in [2], their algorithm is also inaccurate, as the selected links may not be independent. The approximation bound 272 was calculated based on the set ϕ to 0.5 subjectively without any derivation. The comparison between the approximation bound they got and the one in [1, 13] is not rigorous. To the best of our knowledge, Halldόrsson and Wattenhofer [14] proposed the first correct constant approximation algorithm for the MLS problem. In their algorithm, senders added into MLS are separated by at least a predefined interference range. The simple constant approximation algorithm proposed for the MLS problem in [14] assumes uniform power assignment, which only requires the interference received by a newly selected link to be lower-bounded by a constant. In [15], Halldόrsson and Mitra extend [14] to the length-monotone, sublinear power assignments. Kesselheim [16] presents the first constant-approximate Maximal Independent Set (MIS) algorithm with power control. The best previous results depend on further network parameters such as the ratio of the maximum and the minimum distance between a sender and its receiver.

All the works reviewed thus far are centralized, and the studies do not clearly show how to develop a distributed version. The MIS algorithm in [17] is the first randomized and distributed MIS algorithm for the SINR-based interference model. But the time complexity of $O(n^{\mathrm{2}}\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{3}}n)$ is unacceptable. Ásgeirsson and Mitra attempt to solve MLS under SINR model in a distributed setting in [18] after [17]. This algorithm computes the MIS in time $O(\mathrm{l}\mathrm{o}\mathrm{g}\Delta )$ where Δ is the ratio between the largest and the smallest link in the network. Though their $O(\mathrm{l}\mathrm{o}\mathrm{g}\Delta )$ is an exponential improvement of the approximation factor, their model needs additional capabilities or assumptions. That means if another algorithm uses constant size messages without any additional capabilities or assumptions would be better. Recently, Pei and Anil Kumar [19] propose a fully distributed algorithm based on the centralized method in [2] with a time complexity of $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{3}}n)$ . More recently, Pei and Vullikanti [20] develop the algorithm to the time complexity of $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)$ . However, we still could not verify the correctness of their algorithm because of gaps in Lemma $\mathrm{I}\mathrm{V}.\mathrm{3}$ ; that is, in [20], they do not give reasons why the number of active nodes in the vicinity of any active node decreases by half after each phase with a high probability.

The most closely related work to ours is the method in [14]. However, in [14], Halldόrsson and Wattenhofer apply the approach used in [1] to calculate the relative interference constant ϕ, their constant is much smaller than ours. For comparison, set α to $\mathrm{4}$ and β to $\mathrm{16}$ ; their constant ϕ is $\mathrm{1}/\mathrm{10952}$ which is only about $1/24$ of ours. That means that the size of their MLS set is much smaller than ours, both in terms of average and worst case. A bigger ϕ will permit more links to be added into the MLS set. This is one of the real crux of the MLS problems. Furthermore, the paper [14] does not give an approximation ratio and distributed implementation.

Henceforth, we design a centralized MLS schedule with a constant approximation ratio of $\mathrm{5}⌈{\left({\varphi }^{-\mathrm{1}/\alpha }+\mathrm{2}{\beta }^{-\mathrm{1}/\alpha }\right)}^{\alpha }⌉$ , where ϕ is a constant, α is the path-loss exponent, and β is the minimum SINR threshold required for a message to be decoded successfully. Both the calculation method of phi and approximation ratio are improved. As the assumption before, the approximation ratio obtained in [1] (in the absence of noise) and in [13] (restricted to short links) is at least 138135 and 137890, respectively, with the same α and β, both of which are more than 28 times the approximation ratio 4882 of our algorithm.

A randomized and distributed algorithm with polynomial execution time has also been designed. Our distributed algorithm only requires an estimate of the number of links and the maximum and minimum link lengths. We then prove its correctness and show it can compute a MLS with time $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)$ , where n is an estimate of the number of links. To the best of our knowledge, it is one of the algorithms which have the best time complexity.

The remainder of this paper is organized as follows. In Section 2, we introduce the network model, some definitions and theories, and the problem formulation. In Section 3, we introduce our approximation algorithm and its distributed implementation. Lastly, Section 4 concludes the paper and presents further works.

2. Preliminaries

2.1. Network Model

Define a set of links as $L=\left\{l_{\mathrm{1}},\dots ,l_n\right\}$ , where each link $l_v$ represents a communication channel from a sender $s_v$ to a receiver $r_v$ . Let $X(L)$ and $Y(L)$ be the set of senders and receivers of L, respectively; that is, $s_v\in X(L)$ and $r_v\in Y(L)$ . We assume senders and receivers are distributed in the Euclidean plane. Let $d(u,v)$ denote the Euclidean distance between node u and v. For link $l_v$ , let $d(l_v)=d(s_v,r_v)$ be its length. For link $l_v$ and $l_u$ , let $d(l_v,l_u)=d(s_v,r_u)$ denote the asymmetric length from link $l_v$ to $l_u$ . We will use $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ and $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ to denote the link with the smallest and the largest lengths, respectively. We assume the power level assignment is uniform whereby all senders transmit with power level P.

We adopt the SINR-based interference model, where a receiver $r_v$ successfully receives a message from a sender $s_v$ if and only if the following condition holds:

$$\begin{array}{l}\frac{Pd{\left(l_v\right)}^{-\alpha }}{{\sum }_{l_u\in S\setminus \left\{l_v\right\}}Pd{\left(l_u,l_v\right)}^{-\alpha }+N}\hfill \\ =\frac{\mathrm{1}}{{\sum }_{l_u\in S\setminus \left\{l_v\right\}}d{\left(l_u,l_v\right)}^{-\alpha }/d{\left(l_v\right)}^{-\alpha }+N/Pd{\left(l_v\right)}^{-\alpha }}\ge \beta ,\hfill \end{array}$$

(1)

where α is the path-loss exponent, which defines how the signal fades away from its source. Considering realistic wireless propagation environments such as the line-of-sight propagation environment in the building, urban cellular wireless environment with shadow, and the environment with obstacle in the closed space, our approximation results use the assumption that $\mathrm{1.6}<\alpha \le \mathrm{6}$ . $\beta >\mathrm{1}$ denotes the minimum SINR required for a message to be received successfully, N is the ambient noise, and $S\subseteq L$ is the set of links that are active at the same time as link $l_v$ .

We assume all communications are carried out in synchronized fixed length, time slots. In each time slot, a node can either listen or transmit. We assume nodes are able to measure the total received power from other nodes. Here, we define the received power $\mathrm{T}\mathrm{h}(v)$ as the signal power that node v receives from other nodes, excluding ambient noise; that is, given a node set U, the received power of node v is calculated as $\mathrm{T}\mathrm{h}(v)={\sum }_{u\in U}‍\left(P/d(u,v{)}^{\alpha }\right)$ .

2.2. Definitions and Theories

We define link diversity $g(L)$ as $⌈\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{1}+ϵ}\left(d_{\mathrm{m}\mathrm{a}\mathrm{x}}/d_{\mathrm{m}\mathrm{i}\mathrm{n}}\right)⌉$ , where ϵ is a positive constant that is usually set to 1. We can partition set L into nonoverlapping link subclasses $L_i$ , where $\mathrm{1}\le i\le g(L)$ . Each subset $L_i=\left\{l_v\hspace{0.17em}|\hspace{0.17em}(\mathrm{1}+ϵ{)}^{i-\mathrm{1}}{d}_{\mathrm{m}\mathrm{i}\mathrm{n}}<d(l_v)\le (\mathrm{1}+ϵ{)}^i{d}_{\mathrm{m}\mathrm{i}\mathrm{n}}\right\}$ denotes the set of links with similar length. Let $d_i$ denote the upper bound of link lengths in $L_i$ ; hence, $d_i=(\mathrm{1}+ϵ{)}^i{d}_{\mathrm{m}\mathrm{i}\mathrm{n}}$ . For example, assume $d_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{16}$ and $d_{\mathrm{m}\mathrm{i}\mathrm{n}}=\mathrm{2}$ , which yield $g(L)=\mathrm{3}$ when $ϵ=\mathrm{1}$ . As a result, we will have three sets of links, $L_{\mathrm{1}}$ to $L_{\mathrm{3}}$ , with length in the range $(\mathrm{2,4}]$ , $(\mathrm{4,8}]$ , and $(\mathrm{8,16}]$ respectively.

In a distributed environment, nodes use their shared estimates of minimum and maximum possible link length to replace $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ and $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ . As shown in [19], the minimum link length is constrained by a device's dimension, empirically at least 0.1 meter ( $d_{\mathrm{m}\mathrm{i}\mathrm{n}}$ ); the maximum link length depends on the network type and is usually bounded by 105 meters ( $d_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ). It implies that, in most cases, when $ϵ=\mathrm{1}$ , we have $g(L)\le \mathrm{10}$ . Furthermore, as discussed earlier, each link can compute which link subclass it belongs to using the estimates of minimum and maximum link length. The $g(L)$ is used for partitioning the links in L into disjoint link length classes. In practice, the exact number of links in a network may be unknown but can be approximated in advance. Here, we assume, in a distributed implementation, the approximate total number of links, $\widehat{n}$ , is an upper bound of a real number; that is, $\widehat{n}=n^c$ for some constant $c\ge \mathrm{1}$ .

A set I of nodes is said to be d-independent if the mutual distance of the nodes in I is greater than d [21]. A Maximal Independent Set (MIS) U is a d-independent set which is not a subset of any other d-independent sets.

Let R denote $(P/N\beta {)}^{\mathrm{1}/\alpha }$ . In the absence of interference, a link can communicate successfully if and only if $d(l_v)\le R$ . We thus refer to R as the maximum transmission radius.

Consider a link $l_v$ and a set S of concurrently scheduled links $l_v$ . By algebraic manipulation, inequality (1) holds if and only if

$$\begin{array}{cc}& \frac{{\sum }_{l_u\in S\setminus \left\{l_v\right\}}d{\left(l_u,l_v\right)}^{-\alpha }/d{\left(l_v\right)}^{-\alpha }}{\mathrm{1}/\beta -N/Pd{\left(l_v\right)}^{-\alpha }}\le \mathrm{1}.\end{array}$$

(2)

Motivated by inequality (2), we define relative interference $\mathrm{R}\mathrm{I}(l_u,l_v)$ as follows:

$$\begin{array}{cc}& \mathrm{R}\mathrm{I}\left(l_u,l_v\right)=c_v\frac{d{\left(l_u,l_v\right)}^{-\alpha }}{d{\left(l_v\right)}^{-\alpha }},\end{array}$$

(3)

where $c_v=\mathrm{1}/\left(\mathrm{1}/\beta -N/Pd(l_v{)}^{-\alpha }\right)=\beta /\left(\mathrm{1}-(d(l_v)/R{)}^{\alpha }\right)$ , since $R=(P/N\beta {)}^{\mathrm{1}/\alpha }$ . Note that we define $\mathrm{R}\mathrm{I}(l_v,l_v)=\mathrm{0}$ .

Then, with a slight abuse of notation, we define the relative interference of set S to link $l_v$ as the sum of the relative interferences of the links in S on $l_v$ . So, $\mathrm{R}\mathrm{I}(S,l_v)$ is

$$\begin{array}{cc}& \mathrm{R}\mathrm{I}\left(S,l_v\right)={\displaystyle \sum }_{l_u\in S\setminus \left\{l_v\right\}}{c}_v\frac{d{\left(l_u,l_v\right)}^{-\alpha }}{d{\left(l_v\right)}^{-\alpha }}={\displaystyle \sum }_{l_u\in S\setminus \left\{l_v\right\}}\mathrm{R}\mathrm{I}\left(l_u,l_v\right).\end{array}$$

(4)

According to the definitions of relative interference, inequality (2) can be transformed as

$$\begin{array}{l}\frac{{\sum }_{l_u\in S\setminus \left\{l_v\right\}}d{\left(l_u,l_v\right)}^{-\alpha }/d{\left(l_v\right)}^{-\alpha }}{\mathrm{1}/\beta -N/Pd{\left(l_v\right)}^{-\alpha }}={\displaystyle \sum }_{l_u\in S\setminus \left\{l_v\right\}}\mathrm{R}\mathrm{I}\left(l_u,l_v\right)\hfill \\ =\mathrm{R}\mathrm{I}\left(S,l_v\right)\le \mathrm{1}.\hfill \end{array}$$

(5)

As shown in inequality (5), the link $l_v$ succeeds if and only if the relative interference of S to the link $l_v$ is at most one; that is, $\mathrm{R}\mathrm{I}(S,l_v)\le \mathrm{1}$ .

A summary of notations used in this paper can be found in Notations section.

2.3. Problem Formulation

The MLS problem is a maximization problem whereby, given an input set of communication links L, we seek a subset of links $S\subseteq L$ whose cardinality is the largest and links can be scheduled simultaneously under the SINR-based interference model. As mentioned earlier, the MLS problem is NP-hard, and thus we focus on an approximation algorithm. We say an algorithm gives a C-approximation factor if it constructs a MLS set $S\subseteq L$ with $\left|S\right|\le \left|\mathrm{O}\mathrm{P}\mathrm{T}\left(L\right)\right|/C$ , where $\mathrm{O}\mathrm{P}\mathrm{T}(L)$ denotes an optimum solution for MLS.

3. Proposed Algorithm

We now present our constant approximation algorithm for MLS under the SINR-based interference model. We first introduce the centralized version and prove its correctness and approximation factor. After that, we present its distributed version.

3.1. The Centralized Algorithm

Our centralized algorithm for MLS is outlined in Algorithm 1. The algorithm is associated with a constant ϕ, whose value will be determined later on. Algorithm 1 greedily schedules links in nonincreasing order of link length; that is, shortest link is scheduled first. A link in L is selected into set S if and only if its relative interference from S is no larger than ϕ (line (8) of Algorithm 1). On the contrary, a link is discarded if its relative interference from set S is larger than ϕ (line (10) of Algorithm 1). This process repeats until all links in L are considered. Next, we prove the correctness of Algorithm 1 and derive its approximation factor.

Algorithm 1: Centralized algorithm for MLS.

(1) input: Set of links L

(2) output: Set S

(3) $L^{\prime }\leftarrow$ links in L in the non-decreasing order of length

(4) $S\leftarrow \mathrm{\varnothing }$

(5) while   $L^{\prime }\ne \mathrm{\varnothing }$   do

(6)   $l_v\leftarrow$ first link in set $L^{\prime }$

(7)  if RI $(S,l_v)\le \mathrm{\varphi }$   then

(8)    $S\leftarrow S\cup \left\{l_v\right\}$ and $L^{\prime }\leftarrow L^{\prime }\setminus \left\{l_v\right\}$

(9)  else

(10)    $L^{\prime }\leftarrow L^{\prime }\setminus \left\{l_v\right\}$

(11) return  S

3.1.1. Analysis

We begin our analysis by firstly presenting one key property for a pair of links; this property is captured by Lemmas 1 and 2. In particular, the property states that for a pair of links, for example, $l_v$ and $l_u$ , the distance between their respective sender is lower-bounded by a constant if their relative interference is upper-bounded by a constant ϕ. Then, following directly from Lemmas 1 and 2, we use Theorem 3 to prove our centralized algorithm is valid when ϕ is set to a proper value. Together with Lemma 4, Theorem 5 proves our centralized algorithm has a constant approximation factor.

Lemma 1.

Given a pair of links $l_v$ and $l_u$ , if the relative interference $RI(l_u,l_v)$ is upper-bounded by a constant $\mathrm{0}<\varphi <\mathrm{1}$ , that is, $RI(l_u,l_v)\le \varphi$ , the distance between two senders $d(s_v,s_u)$ is lower-bounded by $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ .

Proof.

Since $\mathrm{R}\mathrm{I}(l_u,l_v)=c_v{\left(d(l_u,l_v)/d(l_v)\right)}^{-\alpha }\le \varphi$ , it implies that $d(l_u,l_v)\ge \left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ . Recall that $c_v=\beta /\left(\mathrm{1}-(d(l_v)/R{)}^{\alpha }\right)>\mathrm{1}$ . Then, using the triangular inequality, we have the required lemma:

$$\begin{array}{l}d\left(s_u,s_v\right)>d\left(l_u,l_v\right)-d\left(l_v\right)>\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}{c}_v^{\mathrm{1}/\alpha }-\mathrm{1}\right)d\left(l_v\right)\hfill \\ >\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d\left(l_v\right).\hfill \end{array}$$

(6)

Lemma 2.

Given a pair of links $l_v$ and $l_u$ where $d(l_v)\le d(l_u)$ , if the relative interference $RI(l_v,l_u)$ is upper-bounded by a constant ϕ, the distance between two senders, namely, $d(s_v,s_u)$ , is lower-bounded by $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ .

Proof.

Since $\mathrm{R}\mathrm{I}(l_v,l_u)\le \varphi$ , as per Lemma 1, we have $d(s_u,s_v)>\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_u^{\mathrm{1}/\alpha }d(l_u)$ . Note that $d(s_u,s_v)=d(s_v,s_u)$ and $c_v\le c_u$ whenever $d(l_v)\le d(l_u)$ . Thus, we have

$$\begin{array}{l}d\left(s_v,s_u\right)>\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{1}\right)c_u^{\mathrm{1}/\alpha }d\left(l_u\right)\hfill \\ \ge \left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d\left(l_v\right).\hfill \end{array}$$

(7)

Theorem 3.

Algorithm 1 provides a valid solution when $\varphi \le \mathrm{1}/{\left(\mathrm{2}+(\rho +\mathrm{1}{)}^{\mathrm{1}/\alpha }\right)}^{\alpha }$ , where $\rho =\mathrm{8}(\mathrm{2}/\left(\alpha -\mathrm{2}\right)+\mathrm{1}/\left(\alpha -\mathrm{1}\right)+\mathrm{3})$ .

Proof.

Let $S_v^{-}$ denote the set of links shorter than link $l_v$ , that is, those added to the MLS set S before $l_v$ , and let $S_v^{+}$ be the set of links longer than $l_v$ , that is, those added to S after $l_v$ . When link $l_v$ is added to S, the relative interference $\mathrm{R}\mathrm{I}(S_v^{-},l_v)$ is no larger than ϕ (line (8) of Algorithm 1). Therefore, to make sure S is a valid set satisfying inequality (1), we need to show $\mathrm{R}\mathrm{I}(S_v^{+},l_v)$ is less than $\mathrm{1}-\varphi$ . In the following, we partition the nodes into different rings, then compute the relative interference from each ring, and sum them up to show $\mathrm{R}\mathrm{I}(S_v^{+},l_v)$ is upper-bounded by $\mathrm{1}-\varphi$ .

Using Lemmas 1 and 2 and the fact that the length of links in $S_v^{+}$ is larger than $d(l_v)$ and $c_v$ is an increasing function of $d(l_v)$ , the distance of any two senders of links in set $S_v^{+}\cup \left\{l_v\right\}$ is larger than $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ . We partition the senders in $S_v^{+}$ into concentric rings $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ with width $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ around sender $s_v$ . Rings $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ contain all senders $s_u$ of links in $S_v^{+}$ , for which $k\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)\le d(s_u,s_v)<(k+\mathrm{1})\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ . The first ring $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^{\mathrm{0}}$ does not contain any senders of links in $S_v^{+}$ . We now consider all senders $s_u\in \mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ for some integer $k>\mathrm{0}$ .

First, we consider the distance between any senders $s_u$ in $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ and $s_v$ . As per the construction of rings, we have $d(s_u,s_v)\ge k\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ for ring $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ . Note that $c_v>\mathrm{1}$ . Using the triangular inequality, we can lower bound $d(l_u,l_v)$ for $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ as follows:

$$\begin{array}{l}d\left(l_u,l_v\right)>d\left(s_u,s_v\right)-d\left(l_v\right)\hfill \\ >\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d\left(l_v\right)-d\left(l_v\right)\hfill \\ >\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)c_v^{\mathrm{1}/\alpha }d\left(l_v\right).\hfill \end{array}$$

(8)

Next, observing that, for any senders $s_u$ in $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ , the disk centered at $s_u$ with a radius of $\left(\mathrm{1}/\mathrm{2}\right)\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ is nonoverlapping with other senders in $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ , and such a disk is fully contained in an extended ring of $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ , with an extra width of $\left(\mathrm{1}/\mathrm{2}\right)\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_v^{\mathrm{1}/\alpha }d(l_v)$ at each side of $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ . Then, by referring to the ratio between the area of this extended ring and the disk, the number of senders contained in $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ is upper-bounded by $\mathrm{8}(\mathrm{2}k+\mathrm{1})$ .

The total relative interference coming from $\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k$ is then bounded by

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k,l_v\right)\le {\displaystyle \sum }_{s_u\in \mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k}\mathrm{R}\mathrm{I}\left(l_u,l_v\right)\hfill \\ <\mathrm{8}\left(\mathrm{2}k+\mathrm{1}\right)c_v{\left(k\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)c_v^{\mathrm{1}/\alpha }\frac{d\left(l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\hfill \\ =\mathrm{8}\left(\mathrm{2}k+\mathrm{1}\right)k^{-\alpha }{\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)}^{-\alpha }.\hfill \end{array}$$

(9)

Summing up the relative interferences over all rings yields

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(S_v^{+},l_v\right)\le {\displaystyle \sum }_{k=\mathrm{1}}^{\infty }\mathrm{R}\mathrm{I}\left(\mathrm{R}\mathrm{i}\mathrm{n}{\mathrm{g}}^k,l_v\right)\hfill \\ \le {\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)}^{-\alpha }{\displaystyle \sum }_{k=\mathrm{1}}^{\infty }\mathrm{8}\left(\mathrm{2}k+\mathrm{1}\right)k^{-\alpha }\hfill \\ <{\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)}^{-\alpha }\mathrm{8}\left(\frac{\mathrm{2}}{\alpha -\mathrm{2}}+\frac{\mathrm{1}}{\alpha -\mathrm{1}}+\mathrm{3}\right).\hfill \end{array}$$

(10)

Using $\mathrm{R}\mathrm{I}(S_v^{-},l_v)\le \varphi$ and inequality (10), if the following inequality holds, Algorithm 1 provides a valid solution:

$$\begin{array}{cc}& \mathrm{R}\mathrm{I}\left(S_v^{-},l_v\right)+\mathrm{R}\mathrm{I}\left(S_v^{+},l_v\right)\le {\left(\tau -\mathrm{2}\right)}^{-\alpha }\rho +{\tau }^{-\alpha }\le \mathrm{1},\end{array}$$

(11)

where $\varphi ={\tau }^{-\alpha }$ and $\rho =\mathrm{8}(\mathrm{2}/\left(\alpha -\mathrm{2}\right)+\mathrm{1}/\left(\alpha -\mathrm{1}\right)+\mathrm{3})$ . Since ${\left(\tau -\mathrm{2}\right)}^{-\alpha }\rho +{\tau }^{-\alpha }<{\left(\tau -\mathrm{2}\right)}^{-\alpha }\rho +(\tau -\mathrm{2}{)}^{-\alpha }$ , if the following inequality holds, inequality (11) must also hold:

$$\begin{array}{cc}& {\left(\tau -\mathrm{2}\right)}^{-\alpha }\rho +{\left(\tau -\mathrm{2}\right)}^{-\alpha }\le \mathrm{1}.\end{array}$$

(12)

Therefore, by inequality (12), we have the following bound:

$$\begin{array}{cc}& \tau \ge \mathrm{2}+{\left(\rho +\mathrm{1}\right)}^{\mathrm{1}/\alpha }.\end{array}$$

(13)

According to inequality (13), when $\varphi \le \mathrm{1}/{\left(\mathrm{2}+(\rho +\mathrm{1}{)}^{\mathrm{1}/\alpha }\right)}^{\alpha }$ , inequality (11) holds; that is, Algorithm 1 provides a correct solution.

Lemma 4.

Given links $l_v$ and $l_u$ and a set of links W whose senders lie in the disk centered at sender $s_v$ of $l_v$ with the radius of $d(s_v,s_u)$ , if $RI(W,l_v)\le \mathrm{1}$ and $\left|W\right|\ge ⌈{\left({\varphi }^{-\mathrm{1}/\alpha }+\mathrm{2}{\beta }^{-\mathrm{1}/\alpha }\right)}^{\alpha }⌉$ , one has $RI(l_u,l_v)\le \varphi RI(W,l_v)$ .

Proof.

Considering the fact that for any sender $s_w$ of link $l_w$ in W, $d(s_w,s_v)\le d(s_v,s_u)$ , and $\mathrm{R}\mathrm{I}(W,l_v)\le \mathrm{1}$ , we have $\left|W\right|\mathrm{R}\mathrm{I}(l_u,l_v)\le \mathrm{1}$ . Using the triangular inequality, we get

$$\begin{array}{l}\left|W\right|c_v{\left(\frac{d\left(s_u,s_v\right)+d\left(l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\le \left|W\right|\mathrm{R}\mathrm{I}\left(l_u,l_v\right)\hfill \\ =\left|W\right|c_v{\left(\frac{d\left(l_u,l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\le \mathrm{1}.\hfill \end{array}$$

(14)

Using inequality (14) and the fact that $c_v\ge \beta$ , we have

$$\begin{array}{l}{\left(\mathrm{1}+\frac{d\left(s_u,s_v\right)}{d\left(l_v\right)}\right)}^{\alpha }\ge \beta \left|W\right|\ge \beta ⌈{\left({\varphi }^{-\mathrm{1}/\alpha }+\mathrm{2}{\beta }^{-\mathrm{1}/\alpha }\right)}^{\alpha }⌉\hfill \\ \ge {\left(\mathrm{2}+{\left(\frac{\beta }{\varphi }\right)}^{\mathrm{1}/\alpha }\right)}^{\alpha }.\hfill \end{array}$$

(15)

Hence, we get $d(s_u,s_v)/d(l_v)\ge \mathrm{1}+(\beta /\varphi {)}^{\mathrm{1}/\alpha }$ . Let q denote $\mathrm{1}+(\beta /\varphi {)}^{\mathrm{1}/\alpha }$ . Next, using the triangular inequality, it follows that, for any $l_w\in W$ ,

$$\begin{array}{l}\frac{d\left(l_u,l_v\right)}{d\left(l_w,l_v\right)}\ge \frac{d\left(s_v,s_u\right)-d\left(l_v\right)}{d\left(s_v,s_w\right)+d\left(l_v\right)}\ge \frac{d\left(s_v,s_u\right)-d\left(l_v\right)}{d\left(s_v,s_u\right)+d\left(l_v\right)}\hfill \\ =\mathrm{1}-\frac{\mathrm{2}}{d\left(s_v,s_u\right)/d\left(l_v\right)+\mathrm{1}}\ge \frac{q-\mathrm{1}}{q+\mathrm{1}}.\hfill \end{array}$$

(16)

From inequality (16), we have

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(W,l_v\right)=c_v{\displaystyle \sum }_{l_w\in W}{\left(\frac{d\left(l_w,l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\hfill \\ \ge c_v{\displaystyle \sum }_{l_w\in W}{\left(\frac{q+\mathrm{1}}{q-\mathrm{1}}\frac{d\left(l_u,l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\hfill \\ =\left|W\right|{\left(\frac{q-\mathrm{1}}{q+\mathrm{1}}\right)}^{\alpha }\mathrm{R}\mathrm{I}\left(l_u,l_v\right).\hfill \end{array}$$

(17)

Then using the fact that $q=\mathrm{1}+(\beta /\varphi {)}^{\mathrm{1}/\alpha }$ and $\left|W\right|\ge ⌈{\left({\varphi }^{-\mathrm{1}/\alpha }+\mathrm{2}{\beta }^{-\mathrm{1}/\alpha }\right)}^{\alpha }⌉$ , we have

$$\begin{array}{cc}& \mathrm{R}\mathrm{I}\left(W,l_v\right)\ge \frac{\mathrm{1}}{\varphi }\mathrm{R}\mathrm{I}\left(l_u,l_v\right).\end{array}$$

(18)

Theorem 5.

Algorithm 1 is a $\mathrm{5}\mu$ -approximation algorithm, where μ is $⌈{\left({\varphi }^{-\mathrm{1}/\alpha }+\mathrm{2}{\beta }^{-\mathrm{1}/\alpha }\right)}^{\alpha }⌉$ .

Proof.

Before outlining our proof, we first introduce a method used by [2] to construct $\mu k$ disjoint subsets of links in the optimal MLS set $\mathrm{O}\mathrm{P}\mathrm{T}(L)$ , where k is the cardinality of the MLS set S outputted by Algorithm 1. Let W denote the set of links in $\mathrm{O}\mathrm{P}\mathrm{T}(L)$ . For each $\mathrm{1}\le i\le k$ and $\mathrm{1}\le j\le \mu$ , initialize $W^{\prime }$ to W and each $W_{ij}$ to be empty set. Then, repeat the following iterations for each i and j. For sender $s_i$ of link $l_i\in S$ , include into subset $W_{ij}$ a link $l_{w_{\mathrm{1}}}\in W^{\prime }$ with the closest sender $s_{w_{\mathrm{1}}}$ to $s_i$ , and draw six closed $\mathrm{6}{\mathrm{0}}^{°}$ -sectors originating at $s_i$ such that one of six boundary rays goes through node $s_{w_{\mathrm{1}}}$ , as shown in Figure 1. For each of the left four sectors not containing $s_{w_{\mathrm{1}}}$ , include into $W_{ij}$ a link in $W^{\prime }$ whose sender is closest to $s_i$ in this sector. After that, remove $W_{ij}$ from $W^{\prime }$ and repeat the above iterations. By construction, each $W_{ij}$ contains at most five links; that is, $\left|W_{ij}\right|\le \mathrm{5}$ . To sum up all links in $W_{ij}$ , we get ${\sum }_{i=\mathrm{1}}^k‍{\sum }_{j=\mathrm{1}}^{\mu }‍\left|W_{ij}\right|\le \mathrm{5}\mu k$ . Hence, to prove this theorem, we can prove $W={\bigcup }_{i=\mathrm{1}}^k‍{\bigcup }_{j=\mathrm{1}}^{\mu }‍W_{ij}$ .

By contradiction, assume $W\setminus {\bigcup }_{i=\mathrm{1}}^k‍{\bigcup }_{j=\mathrm{1}}^{\mu }‍W_{ij}$ is nonempty, and an arbitrary link $l_v$ is in this set. Hence, for any node $s_i\in X(S)$ , after μ iterations, node $l_v$ will not be selected into any $W_{ij}$ by assumption. That is, for each $\mathrm{1}\le i\le k$ and $\mathrm{1}\le j\le \mu$ , there must be a node $s_w\in X(W_{ij})$ such that $d(s_i,s_w)\le d(s_i,s_v)$ , and the angle $\angle s_w{s}_i{s}_v\le \mathrm{6}{\mathrm{0}}^{°}$ . Let $U_i$ denote the set of links whose sender lies in intersection of the two disks centered at $s_i$ and $s_v$ with radius $d(s_i,s_v)$ . Then $U_i$ contains at least μ links in W; else link $l_v$ must be chosen into some $W_{ij}$ .

According to Lemma 4, for any $\mathrm{1}\le i\le k$ , $\mathrm{R}\mathrm{I}(l_i,l_v)\le \varphi \mathrm{R}\mathrm{I}(U_i,l_v)$ . Recall that ${\bigcup }_{i=\mathrm{1}}^k‍U_i\subseteq W$ and $\mathrm{R}\mathrm{I}(W,l_v)\le \mathrm{1}$ by assumption, and thus we have

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(S,l_v\right)={\displaystyle \sum }_{i=\mathrm{1}}^k\mathrm{R}\mathrm{I}\left(l_i,l_v\right)\le {\displaystyle \sum }_{i=\mathrm{1}}^k\varphi \mathrm{R}\mathrm{I}\left(U_i,l_v\right)\le \varphi \mathrm{R}\mathrm{I}\left(W,l_v\right)\hfill \\ \le \varphi .\hfill \end{array}$$

(19)

Therefore, the relative interference of S to link $l_v$ is at most ϕ. This means that link $l_v$ should not have been removed which is a contradiction. So $W={\bigcup }_{i=\mathrm{1}}^k‍{\bigcup }_{j=\mathrm{1}}^{\mu }‍W_{ij}$ and $\left|W\right|\le \mathrm{5}\mu k$ .

Figure 1

An illustration of Theorem 5.

3.2. The Distributed Algorithm

In this section, we present a randomized, distributed implementation for Algorithm 1. We then prove its correctness and calculate its time complexity.

Our distributed algorithm is illustrated in Algorithm 2, in which we set $d_i=(\mathrm{1}+ϵ{)}^i{d}_{\mathrm{m}\mathrm{i}\mathrm{n}}$ and $c_i=\beta /\left(\mathrm{1}-(d_i/R{)}^{\alpha }\right)$ . Let $S_i$ be the set of links that are selected into the MLS set S in $L_i$ , and let $S_i^{-}$ (resp., $S_i^{+}$ ) be the set of links that are selected into the MLS set S before (resp., after) links in $S_i$ . Initially, we have $S=\varnothing$ , and $\sigma (v)=\mathrm{0}$ for any $v\in X(L)\cup Y(L)$ , where $\sigma (v)$ is used as an indicator to decide whether a link needs to be selected into S. Specifically, a link $l_v$ is added into S if and only if $\sigma (s_v)=\sigma (r_v)=\mathrm{1}$ .

Algorithm 2: Distributed algorithm for MLS.

(1) input: Set of links L

(2) output: MLS set S

(3) // $initialize\hspace{0.17em}\hspace{0.17em}(one\text{-}slot)$ //

(4) $S\leftarrow \mathrm{\varnothing }$

(5) $\mathrm{\sigma }(v)\leftarrow \mathrm{0}$ , $\forall v\in X(L)\cup Y(L)$

(6) for   $i\leftarrow \mathrm{1}$ to $g(L)$   do

(7)  // 1st   $step$ :   $RI\hspace{0.17em}\hspace{0.17em}Constraints\hspace{0.17em}\hspace{0.17em}(one\text{-}slot)$ //

(8)  Senders of links in S transmit in this slot

(9)  if   $v\in Y(L_i)$   then

(10)   v senses the channel

(11)   if   $Th(v)\le \mathrm{\varphi }P/c_i{d}_i^{\mathrm{\alpha }}$   then

(12)     $\mathrm{\sigma }(v)\leftarrow \mathrm{1}$

(13)  // 2nd   $step$ :   $Spatial\hspace{0.17em}\hspace{0.17em}Constraints\hspace{0.17em}\hspace{0.17em}(O({\log }^{\mathrm{2}}n)\text{-}slots)$ //

(14)  Perform the MIS algorithm of [22] with mutual distances larger than

     $\left({\mathrm{\varphi }}^{-\mathrm{1}/\mathrm{\alpha }}-\mathrm{1}\right)c_i^{\mathrm{1}/\mathrm{\alpha }}{d}_i$ , $\forall v\in X(L_i)$

(15)  if   $v\in X(L_i)\cap \text{MIS}$   then

(16)    $\mathrm{\sigma }(v)\leftarrow \mathrm{1}$

(17)  // 3rd   $step$ :   $Decision\hspace{0.17em}\hspace{0.17em}(two\text{-}slots)$ //

(18)  if   $v\in X(L_i)$ and $\mathrm{\sigma }(v)=\mathrm{1}$   then

(19)   v sends a REQUEST containing its ID and receiver's ID

(20)  else

(21)   v listens to the channel in this slot

(22)  if   $v\in Y(L_i)$ , $\mathrm{\sigma }(v)=\mathrm{1}$ and receives REQUEST from its sender  then

(23)   v transmits an ACK

(24)  if   $v\in X(L_i)$ , $\mathrm{\sigma }(v)=\mathrm{1}$ and receives ACK from its sender then

(25)   Add its link to S

(26) return  S

The algorithm then sweeps through the link classes in $g(L)$ rounds. The ith round, where $i\in [\mathrm{1},g(L)]$ , consists of three steps: (1) it checks the relative interference constraint for receivers $r_v$ in $Y(L_i)$ (line (9) to (12) in Algorithm 2); (2) it selects a set of $\left({\varphi }^{-\mathrm{1}/\alpha }-\mathrm{1}\right)c_i^{\mathrm{1}/\alpha }{d}_i$ -independent senders $s_v$ from $X(L_i)$ (line (14) to (16) in Algorithm 2); and (3) it selects into S link $l_v$ satisfying $\sigma (s_v)=\sigma (r_v)=\mathrm{1}$ (line (18) to (25) in Algorithm 2).

In the first step, only links $l_v$ in $L_i$ satisfying the relative interference constraint, that is, $\mathrm{R}\mathrm{I}(S_i^{-},l_v)\le \varphi$ , can be selected into S; that is, according to (3), the interference received by receiver $r_v$ must be no larger than $\varphi P/c_{v}d(l_v{)}^{\alpha }$ . Considering the fact that $d(l_v)\le d_i$ and $c_v\le c_i$ for set class $L_i$ , we can replace this interference bound with $\varphi P/c_i{d}_i^{\alpha }$ . All senders of links in S will send a message with power P in the first step and any receiver $r_v$ of links in $L_i$ senses the channel. Note that the value of $\mathrm{T}\mathrm{h}(r_v)$ is equal to the interference $r_v$ received. Hence, if $\mathrm{T}\mathrm{h}(r_v)\le \varphi P/c_i{d}_i^{\alpha }$ , we set $\sigma (r_v)$ to “1.”

The second step is used to select a MIS set from $X(L_i)$ with a mutual distance larger than $\left({\varphi }^{-\mathrm{1}/\alpha }-\mathrm{1}\right)c_i^{\mathrm{1}/\alpha }{d}_i$ . The intuition behind this step is to ensure that the relative interference received by $l_v\in S_i$ from other links in $S_i\cup S_i^{+}$ does not exceed $\mathrm{1}-\varphi$ ; that is, $\mathrm{R}\mathrm{I}(S_i\cup S_i^{+},l_v)\le \mathrm{1}-\varphi$ . In this step, all senders of links in $L_i$ need to compete to get into the MIS set using the MIS algorithm in [22]. The MIS algorithm in [22] randomized and distributed MIS algorithm for the SINR-based interference model. As shown in [22], it only requires an estimate of the number of nodes. In our case, the number of nodes in $X(L_i)$ is bounded by n. Observing that the MIS algorithm in [22] requires nodes to have adjustable power levels, we assume that, in Algorithm 2, the second step will use variable power levels, for example, ${\left({\varphi }^{-\mathrm{1}/\alpha }-\mathrm{1}\right)}^{\alpha }{c}_i{d}_i^{\alpha }N\beta$ , but the other steps use uniform power assignment P. Briefly, at any time during the execution, a node can be in one of four states. At first, a node joins the waiting state $\mathcal{W}$ in which it only listens for messages. If a node does not become covered by a MIS node, it will join the active state $\mathcal{A}$ . In state $\mathcal{A}$ , a node joins state $\mathcal{B}$ by sending a message with an increasing probability. If a node transmits this message successfully, it will join state $\mathcal{B}$ , whereas its neighbors in state $\mathcal{A}$ that receive the said message will restart the algorithm, returning to the initial waiting state $\mathcal{W}$ . After joining state $\mathcal{B}$ , nodes will compete to join state $\mathcal{M}$ to become a MIS member.

After finding the MIS set for nodes in $X(L_i)$ , all nodes v in the MIS will set $\sigma (v)$ to “1” (lines (15) to (16) in Algorithm 2).

For the third step, only links $l_v\in L_i$ with $\sigma (r_v)=\sigma (s_v)=\mathrm{1}$ are added into S. This decision step is conducted by a two-slot transmitting/receiving procedure. In the first slot, each sender $s_v$ in $X(L_i)$ with $\sigma (s_v)=\mathrm{1}$ transmits a REQUEST message containing its ID and its receiver's ID, and each receiver $r_v\in Y(L_i)$ listens to the channel (lines (18) to (21) in Algorithm 2). In the next slot, only the receivers $r_v\in Y(L_i)$ with $\sigma (r_v)=\mathrm{1}$ receiving the REQUEST message from the senders $s_v$ transmit an ACK message, and the senders add themselves into S after receiving the ACK (lines (22) to (25) in Algorithm 2). We will prove that all communications in this step are interference-free later on.

3.2.1. Analysis

Theorem 8 follows directly from Lemmas 6 and 7. Lemma 6 shows that the relative interference experienced by selected links in $L_i$ and those links selected after them is lower-bounded by $\mathrm{1}-\varphi$ . Lemma 7 proves that the communications in the third step of our distributed algorithm are interference-free. Together with Lemmas 6 and 7, we use Theorem 8 to prove that our distributed algorithm is correct. Additionally, Theorem 10 is used to determine the time complexity.

Lemma 6.

Given a link $l_v\in L_i$ , if $l_v$ is selected into S of Algorithm 2, the relative interference $RI(S_i\cup S_i^{+},l_v)$ does not exceed $\mathrm{1}-\varphi$ .

Proof.

According to the first step of Algorithm 2, for any links $l_v$ in $S_i$ , their relative interference $\mathrm{R}\mathrm{I}(S_i^{-},l_v)$ does not exceed ϕ. Assume that $l_u\in S_j$ and $j>i$ . Considering Lemma 1 and $l_v\in S_j^{-}$ , the distance between $s_u$ and $s_v$ must be larger than $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_u^{\mathrm{1}/\alpha }d(l_u)$ . Note that $d(l_u)>d_i$ and $c_u$ is an increasing function of $d(l_u)$ . Hence, we have that for any pair of links belonging to two different subclasses $S_i$ and $S_j$ , where $j>i$ , the mutual distance between their sender is larger than $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_i^{\mathrm{1}/\alpha }{d}_i$ .

Considering the fact that for any pair of links in the same subclass $S_j$ , the mutual distance between their sender is larger than $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_j^{\mathrm{1}/\alpha }{d}_j$ by the second step of Algorithm 2. Since $c_j$ and $d_j$ are increasing function of j, we have that for any pair of links in the same subclass $S_j$ , where $j\ge i$ , the mutual distance between their sender is no less than $\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_i^{\mathrm{1}/\alpha }{d}_i$ .

To summarize, we have that, for any pair of links $l_u$ and $l_v$ in $S_i\cup S_i^{+}$ , the mutual distance of their sender $s_u$ and $s_v$ is

$$\begin{array}{cc}& d\left(s_u,s_v\right)\ge \left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{1}\right)c_i^{\mathrm{1}/\alpha }{d}_i.\end{array}$$

(20)

Using the same method in Theorem 3, we can get the following upper bound for $\mathrm{R}\mathrm{I}(S_i\cup S_i^{+},l_v)$ based on inequalities (8), (9), and (10):

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(S_i\cup S_i^{+},l_v\right)\hfill \\ <{\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)}^{-\alpha }\mathrm{8}\left(\frac{\mathrm{2}}{\alpha -\mathrm{2}}+\frac{\mathrm{1}}{\alpha -\mathrm{1}}+\mathrm{3}\right).\hfill \end{array}$$

(21)

Recall that $\varphi \le \mathrm{1}/{\left(\mathrm{2}+(\rho +\mathrm{1}{)}^{\mathrm{1}/\alpha }\right)}^{\alpha }$ , where $\rho =\mathrm{8}(\mathrm{2}/\left(\alpha -\mathrm{2}\right)+\mathrm{1}/\left(\alpha -\mathrm{1}\right)+\mathrm{3})$ , and thus $\mathrm{R}\mathrm{I}(S_i\cup S_i^{+},l_v)<\mathrm{1}-\varphi$ .

Lemma 7.

The two-slot transmitting/receiving mechanism in the third step of Algorithm 2 is correct.

Proof.

To prove the correctness of this lemma, we only need to show that all communications can be executed successfully in two slots, that is, interference-free. We prove this lemma by considering two cases: communications in the first slot and communications in the second slot.

In the first case, only senders $s_v\in X(L_i)$ with $\sigma (s_v)=\mathrm{1}$ are allowed to send a REQUEST to their corresponding receivers $r_v$ . Recall that if $\sigma (s_v)=\mathrm{1}$ , sender $s_v$ must belong to the d-independent set by the second step of Algorithm 2, and the mutual distance between any pair of senders in the d-independent set is no less than d, where $d=\left(\mathrm{1}/{\varphi }^{\mathrm{1}/\alpha }-\mathrm{1}\right)c_i^{\mathrm{1}/\alpha }{d}_i$ . Denote by $D_i$ the set of links in $L_i$ whose senders belong to the d-independent set. Using inequalities (9) and (10) and triangular inequality, we have the relative interference received by $l_v$ from other links in $D_i$ :

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(D_i,l_v\right)=c_v{\displaystyle \sum }_{l_u\in D_i\setminus \left\{l_v\right\}}{\left(\frac{d\left(l_u,l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\hfill \\ \le c_v{\displaystyle \sum }_{l_u\in D_i\setminus \left\{l_v\right\}}{\left(\frac{d\left(s_u,s_v\right)-d\left(l_v\right)}{d\left(l_v\right)}\right)}^{-\alpha }\hfill \\ \le c_i{\displaystyle \sum }_{l_u\in D_i\setminus \left\{l_v\right\}}{\left(\frac{d\left(s_u,s_v\right)-d_i}{d_i}\right)}^{-\alpha }\hfill \\ <{\left(\frac{\mathrm{1}}{{\varphi }^{\mathrm{1}/\alpha }}-\mathrm{2}\right)}^{-\alpha }\mathrm{8}\left(\frac{\mathrm{2}}{\alpha -\mathrm{2}}+\frac{\mathrm{1}}{\alpha -\mathrm{1}}+\mathrm{3}\right)\hfill \\ <\mathrm{1}-\varphi <\mathrm{1}.\hfill \end{array}$$

(22)

That is, the transmissions in the first slot are interference-free.

For the second case, only receivers $r_v\in Y(L_i)$ with $\sigma (r_v)=\mathrm{1}$ that have received the REQUEST message from their corresponding senders $s_v$ are allowed to send the ACK to $s_v$ . As mentioned above, sender $s_v$ belongs to the d-independent set. That is, only receivers of links $l_v$ in $D_i$ are allowed to transmit in the second slot. Let $\overline{l_v}$ denote the link $l_v$ with transmission direction inverted, that is, from $r_v$ to $s_v$ . Likewise, let $\overline{D_i}$ denote the set of links in $D_i$ with transmission direction inverted. Note that, if $l_v\in D_i$ , we have $\overline{l_v}\in \overline{D_i}$ , $d(l_v)=d(\overline{l_v})$ , and $c_v=\beta /\left(\mathrm{1}-(d(l_v)/R{)}^{\alpha }\right)=\beta /\left(\mathrm{1}-(d(\overline{l_v})/R{)}^{\alpha }\right)$ . Then, using inequality (22) and triangular inequality, we get

$$\begin{array}{l}\mathrm{R}\mathrm{I}\left(\overline{D_i},\overline{l_v}\right)=c_v{\displaystyle \sum }_{\overline{l_u}\in \overline{D_i}\setminus \left\{\overline{l_v}\right\}}{\left(\frac{d\left(\overline{l_u},\overline{l_v}\right)}{d\left(\overline{l_v}\right)}\right)}^{-\alpha }\hfill \\ \le c_v{\displaystyle \sum }_{\overline{l_u}\in \overline{D_i}\setminus \left\{\overline{l_v}\right\}}{\left(\frac{d\left(s_u,s_v\right)-d\left(\overline{l_u}\right)}{d\left(\overline{l_v}\right)}\right)}^{-\alpha }\hfill \\ =c_v{\displaystyle \sum }_{l_u\in D_i\setminus \left\{l_v\right\}}{\left(\frac{d\left(s_u,s_v\right)-d\left(l_u\right)}{d\left(l_v\right)}\right)}^{-\alpha }\hfill \\ \le c_i{\displaystyle \sum }_{l_u\in D_i\setminus \left\{l_v\right\}}{\left(\frac{d\left(s_u,s_v\right)-d_i}{d_i}\right)}^{-\alpha }<\mathrm{1}.\hfill \end{array}$$

(23)

The transmissions in the second slot are also interference-free. Hence, the lemma is true.

Theorem 8.

Algorithm 2 provides a valid solution.

Proof.

For any links $l_v$ in $S_i$ , where $\mathrm{1}\le i\le g(L)$ , $\mathrm{R}\mathrm{I}(S_i^{-},l_v)\le \varphi$ by the first step of Algorithm 2. According to Lemma 6, we have $\mathrm{R}\mathrm{I}(S_i\cup S_i^{+},l_v)<\mathrm{1}-\varphi$ . Therefore, $\mathrm{R}\mathrm{I}(S,l_v)=\mathrm{R}\mathrm{I}(S_i^{-},l_v)+\mathrm{R}\mathrm{I}(S_i\cup S_i^{+},l_v)<\mathrm{1}$ .

Lemma 9.

The total time to compute a MIS at each stage is $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)$ .

Proof.

Please see [22].

Theorem 10.

The time complexity of Algorithm 2 is $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)$ .

Proof.

As shown in Algorithm 2, the initializing step only takes one slot for all links. For links in $L_i$ , lines (8) to (24) take $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)+\mathrm{3}$ slots to select valid links into S, and, in total, there are $g(L)$ subclasses. To sum up, Algorithm 2 takes $\mathrm{1}+(O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)+\mathrm{3})g(L)$ time slots.

3.3. Remarks on Distributed MIS Algorithm

The second step of Algorithm 2 is to compute a MIS set which has been extensively studied and many distributed algorithms have been proposed [23–25]. However, most of these methods compute the MIS set by modeling it as a graph, for example, the unit disk graph (UDG). A SINR-based interference model is fundamentally different because the cumulative interference may result in a node v failing to receive a message even when only one neighbor of v transmits. Due to this difference, it is impractical to adopt a graph-based, distributed MIS algorithm for our problem, which assumes the SINR-based interference model.

To the best of our knowledge, the first MIS algorithm designed for the SINR-based interference model is proposed by Yu et al. [22]. It is a randomized distributed method that can compute the MIS set in time $O(\mathrm{l}\mathrm{o}{\mathrm{g}}^{\mathrm{2}}n)$ . Another possible distributed MIS algorithm that we can use in the second step of Algorithm 2 is presented in [26]. Yu et al. [26] adapt the deterministic MIS algorithm of [24] by carefully choosing power levels. As proven in [26], their methods can compute the MIS set in time $O(\log n)$ , which will improve the time complexity of Algorithm 2 to $O(\log n)$ .

4. Conclusion

In this paper, we have studied the maximum link scheduling problem under the SINR interference model. The goal is to maximize the set of concurrent links. To address this problem, we design a constant approximation algorithm under the assumption of uniform transmission power. With the same assumption, the constant approximation ratio of our algorithm is $\mathrm{5}⌈{\left({\varphi }^{-\mathrm{1}/\alpha }+\mathrm{2}{\beta }^{-\mathrm{1}/\alpha }\right)}^{\alpha }⌉$ . Both the constant ϕ and ratio have improved by 24 times at least when comparing with excellent related algorithms. We also present its distributed implementation that is dependent only on the maximum and minimum link length.

There are still a number of open problems, such as power control, multihop traffic scheduling and routing, analog network coding, and models beyond SINR such as log-normal shadowing. As a future work, we are currently looking into a distributed algorithm with lower time complexity. The use of our solution in arbitrary power assignment and 3D space is also possible future works.