Deterministic Oblivious Local Broadcast in the SINR Model

Abstract

Local Broadcast is one of the most fundamental communication problems in wireless networks. The task is to allow each node to deliver a message to all its neighbors. In this paper we consider an oblivious and semi-oblivious variants of the problem. The oblivious algorithm is a fixed deterministic schedule of transmissions that tells each station in which rounds it has to transmit. In semi-oblivious variant of the problem we allow a station to quit the execution of the schedule at some point. We present algorithms with complexity of $O(\varDelta ^{2+2/(\alpha -2)}\log N)$ for the oblivious variant and $O(\varDelta \log N)$ for the semi-oblivious case, where $\alpha >2$ is a path loss parameter, [1, N] is the range of IDs of stations and $\varDelta$ is the maximal degree in a network. In the latter case we make use of the acknowledgements, which inform a station, after it sent a message, if all its neighbors had received it.

This work was supported by the Polish National Science Centre grants DEC-2012/07/B/ST6/01534 and 2014/13/N/ST6/01850.

1 Introduction

1.1 The Network Model

We consider a wireless network consisting of nodes located on the 2-dimensional Euclidean plane. We model transmissions in the network with the SINR (Signal-to-Interference-and-Noise Ratio) constraints. The model is determined by fixed parameters: path loss $\alpha >2$, threshold $\beta >1$, ambient noise $\mathcal {N}>0$ and uniform transmission power $\mathcal {P}$. The communication graph $G=(V,E)$ of a given network consists of all nodes and edges $\{v,u\}$ between nodes that are within distance of at most $1-\varepsilon$, where $\varepsilon \in (0,1)$ is a fixed constant (the connectivity parameter). The communication graph, defined as above, is a standard notion in the analysis of ad hoc communication in the SINR model, cf., [4, 18]. The value of $SINR(v,u,\mathcal {T})$, for given stations u, v and a set of concurrently transmitting stations $\mathcal {T}$ is defined as follows.

$$\begin{aligned} SINR(v,u,\mathcal {T}) = \frac{\mathcal {P}/d(v,u)^{\alpha }}{\mathcal {N}+\sum _{w\in \mathcal {T}\setminus \{v\}}\mathcal {P}/d(w,u)^{\alpha }} \end{aligned}$$

(1)

A node u receives a message from w iff $w\in \mathcal {T}$ and $SINR(w,u,\mathcal {T})\ge \beta$, where $\mathcal {T}$ is the set of stations transmitting at the same time. Transmission range is the maximal distance at which a station can be heard provided there are no other transmitters in the network. Without loss of generality we assume that the transmission range are all equal to 1.

We assume that algorithms work synchronously in rounds. In a single round, a station transmits a message according to the predefined schedule (the algorithm). In the semi-oblivious variant of the problem, a station can quit the execution of the algorithm at some point. This means that nodes do not perform any calculations, nor react to the content of the messages they receive; the only thing a node can do is to transmit its message in rounds defined by the schedule, or – in the semi-oblivious variant – quit the execution of the algorithm after receiving specific feedback.

The degree of the network $\varDelta$ is the maximal number of stations in any ball of radius 1. Observe, that the maximum node degree of the communication graph is $\varTheta (\varDelta )$.

Each station has a unique identifier from the set [N], where $N=n^{O(1)}$ is the upper bound on the size n of the network. Moreover, the stations know: N, the SINR parameters – $\mathcal {P},\alpha ,\beta ,\varepsilon ,\mathcal {N}$, and the degree of the network $\varDelta$. In the section presenting semi-oblivious algorithm we allow the stations to use the feedback mechanism, which tells the station if its message had been received by all neighbors in given round. It has been widely used in the randomized algorithms for local broadcast problem [3, 13].

1.2 Problem Definition and Related Work

The problem of local broadcast is one of the most fundamental communication tasks. We say that an algorithm solves local broadcast problem if, during its execution, each node sends a message that is received by all its neighbors.

In the last years the SINR model was extensively studied. It regards structural properties of so-called SINR-diagrams and reception areas [2, 14, 20, 21] as well as algorithm design for local and global broadcast [3, 4, 10, 11, 16, 17, 19, 24, 26], link scheduling [12], and other problems [15, 22]. The first work on local broadcast in SINR model by Goussevskaia et al. [10] presented an $O(\varDelta \log n)$ randomized algorithm. After that, the problem was studied in various settings. Halldorsson and Mitra presented an $O(\varDelta +\log ^2n)$ algorithm in a model with feedback [13]. Recently, for the same setting Barenboim and Peleg presented solution working in time $O(\varDelta + \log n\log \log n)$ [3]. For the scenario when degree $\varDelta$ is not known Yu et al. in [26] improved on the $O(\varDelta \log ^3 n)$ solution of Goussevskaia et al. to $O(\varDelta \log n+ \log ^2n)$. However, no deterministic (oblivious) algorithm for local broadcast was known in the scenario considered here, i.e., when stations do not know their coordinates.

The local broadcast problem is a generalization of the extensively studied contention resolution problem in multiple-access channels, in which nodes have to send their messages to a shared channel (that corresponds to a neighborhood in our context) [1, 5,6,7,8,9, 23].

1.3 Our Contribution and Open Problems

To the best knowledge of the authors this paper is the first to investigate non-adaptive (i.e., oblivious or semi-oblivious) deterministic algorithms in the SINR model.

In Sect. 3.1 we present the application of strongly selective families as local broadcast schedules. The complexity of this result is worse than the one of schedules constructed from balanced strongly selective families in Sect. 3.3, but the advantage of this result is that the strongly selective families are constructive (i.e., can be locally computed in polynomial time, c.f., [25]). Also, this result serves as a part of the semi-oblivious schedule in Sect. 4.2.

In Sect. 3.2 we show existence of balanced strongly selective families (bssf) with certain parameters through the probabilistic method. Then, in Sect. 3.3, we prove that bssf can serve as a local broadcast schedule. The length of the schedule is $O(\varDelta ^{2+2/(\alpha -2)}\log N)$.

In the last section we show existence of fractional balanced selectors through the probabilistic method. The analysis is not standard for such constructions and might be interesting on its own. Then, we apply the result to show existence of the semi-oblivious schedule of length $O(\varDelta \log N)$.

Our results indicate that although non-adaptive deterministic local broadcast is a time consuming task, little adaptivity polynomially improves the performance. The issue of efficient construction of balanced strongly selective families and (fractional) balanced selectors remains open.

2 Preliminaries

In this section we present basic definitions and facts to be used in further sections. We use [n] to denote the set of natural numbers $\{1,...,n\}$. The central object in this paper are families of sets over [N]. Any family of subsets over [N] can be regarded as a transmission schedule, assuming that the sets are ordered within a family. We formalize this notion as follows.

A transmission schedule of length t is defined by a sequence $\mathcal {S}=(S_1,...,S_t)$ of subsets of [N], where the ith set determines nodes transmitting in the ith round of the schedule. That is, a node with ID $v\in [N]$ transmits in round i of an execution of $\mathcal {S}$ if and only if $v\in S_i$.

Most of the results in our paper are of probabilistic nature, hence we introduce a suitable notion of random sequences of subsets. We denote by $\mathcal {Q}_{m,p}=(Q_1,\dots ,Q_m)$ a random sequence subsets of [N] where each $x\in [N]$ is independently put into each $Q_i$ with probability p for each $1 \le i\le m$.

A set $S\subseteq [N]$ selects $x\in A$ from $A\subseteq [N]$ when $S\cap A=\{x\}$.

A sequence $\mathcal {S}=(S_1,\ldots ,S_t)$ of sets over [N] is called (N, k)-strongly selective family (or (N, k)-ssf) if for any subset $A\subseteq [N]$ such that $|A|\le k$, and each $x\in A$ there is $i\in [t]$ such that $S_i$ selects x from A.

A sequence $\mathcal {S}=(S_1,\ldots ,S_t)$ of sets over [N] is called $(N,k,\gamma ,\varvec{b})$-balanced strongly selective family (or $(N,k,\gamma ,\varvec{b})$-bssf), where $\varvec{b}=(b_1,...,b_l)$, if for each subset $A\subseteq [N]$ such that $|A|\le k$, and any $B_1,...,B_l\subseteq [N]$ such that $|B_i|=b_i$, for any $x\in A$ there is $S\in \mathcal {S}$ such that: (i) $S\cap A=\{x\}$, (ii) $|S\cap B_i|\le \gamma \cdot b_i$ for all i. The sets $B_i$ are called bounding sets.

The definition of fractional balanced selector (fbs) is analogous to the definition of bssf, where we require that at least half of the elements of A are selected instead of all of them. We give full definition of fbs in Subsect. 4.1. Note, that we give the probabilistic argument for existence of fbs with specific parameters suited for local broadcast problem in SINR model, however more general statement is possible.

We say that a schedule $\mathcal {S}$ is a local broadcast schedule if for any network of degree $\varDelta$, for any node $v\in G$ there is a round, when v transmits and is heard by all its neighbors, where G is the communication graph of that network. Formally, for any $v\in G$ there exists $S\in \mathcal {S}$ such that: (i) $v\in S$, (ii) $w\not \in S$ for any $w\in N(v)$, (iii) SINR$(v,w,S)\ge \beta$ for all $w\in N(v)$.

Let $\mathcal {I}_d$ be the maximal value of interference at node v that guarantees that v can receive a message from any station at distance d.

Below we present some basic mathematical facts.

Fact 1

For all $x\in \mathbb {R}$ we have

$$e^x\ge 1+x.$$

Fact 2

For any natural $k\le n$ we have

$${n \atopwithdelims ()k} \le e^{k\ln (n/k)+k}.$$

Fact 3

(Chernoff Bound) Let $X\sim Bin(n,p)$, where $p\le 1/2$. Then for any $\delta >0$ we have

$$\mathbb {P}(X\ge (1+\delta )\mathbb {E}[X]) \le \exp (-\delta ^2\mathbb {E}[X]/(2+\delta )).$$

Fact 4

For $p\in (0,1/2)$ we have

$$1/4 \le (1-p)^{1/p}\le 1/e.$$

Fact 5

One can cover a disc of radius $r>1$ using $8r^2$ discs of radius 1.

Fact 6

Let $a>1, b>0$, then for all $x\ge 2\log _a(2b/\ln a)$ we have

$$\frac{a^x}{x}\ge b.$$

3 Non-adaptive Algorithms

3.1 Application of Strongly Selective Families

In this subsection we present a preliminary result on application of combinatorial structures to solve local broadcast in SINR networks. We explore the parameters of strongly selective families so that the schedules resulting from them are local broadcast schedules.

Proposition 1

Let $\mathcal {T}$ be a set of transmitting stations and let v be a point on the plane. Assume that any ball of radius r contains at most $\varDelta$ elements of $\mathcal {T}$ and B(v, xr) does not contain elements of $\mathcal {T}$ for a natural positive number x. Then, the overall strength $I(v)=\sum _{u\in \mathcal {T}}\mathcal {P}/d(u,v)^{\alpha }$ of signals from the set $\mathcal {T}$ at v is $O\left( r^{-\alpha }x^{-\alpha +2}\varDelta \right)$.

Thanks to the above proposition, in the following corollary we estimate the distance at which there should be no transmitters in order to limit the total power of the signal to a given value.

Corollary 1

There exists a constant $\tau >0$ dependent on $\alpha ,\ \mathcal {P}$ such that if there are no stations transmitting in $B(v,\tau \left( \varDelta /y\right) ^{1/(\alpha -2)})$ then $I(v)\le y$, provided that there are at most $\varDelta$ stations per disc of radius 1.

The following is a direct consequence of Corollary 1.

Corollary 2

Let v be the only one transmitting station in B(v, x), assuming that at most $\varDelta$ stations are transmitting per each unit ball outside of B(v, x). Let $x_\varDelta = \tau (\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}+1$. If $x\ge x_\varDelta$ then every station within distance at most $1-\varepsilon$ from v can hear the transmission of v.

The following construction is a natural consequence of the above observations: If a station is a unique transmitter in the set of all stations within distance $x_\varDelta$ then it is heard by all its neighbors. A ssf-schedule, guaranteeing that each station has a round in which it transmits in such way, would be a local broadcast schedule. In the following Theorem we present such schedules.

Theorem 1

Let $x_\varDelta$ be the value defined in Corollary 2, and $\mathbf {S}$ be a $(N,8\varDelta x_\varDelta ^2)$-ssf schedule. Then $\mathbf {S}$ is a local broadcast schedule for any network of density $\varDelta$, and the length of the schedule is $O(\varDelta ^{2+4/(\alpha -2)}\log (N/(\varDelta ^{1+2/(\alpha -2)}))$.

Proof

Let v be any station. By Fact 5, there are at most $8\varDelta x_\varDelta ^2$ stations in $B(v,x_\varDelta )$, and by the definition of the schedule $\mathbf {S}$, there is a round in $\mathbf {S}$ when v is the unique transmitter in $B(v,x_\varDelta )$. Then, by Corollary 2, the interference in any point of $B(v,1-\varepsilon )$ allows to receive the message from v, which concludes the proof.

3.2 Balanced Strongly Selective Families

We say that a sequence $\mathcal {Q}$ of subsets of [N] is a $(N,k,\gamma ,\varvec{b})-$balanced ssf, if for any central set $A\subseteq [N]$ of size k, any bounding sets $B_1,...,B_l\subseteq [N]$ such that $|B_i|=b_i$, and limit coefficient $\gamma$, all elements $x\in A$ are selected – an element $x\in A$ is said to be selected if there exists a round $Q\in \mathcal {Q}$ such that

• (a) $Q\cap A = \{x\}$,

• (b) $|Q\cap B_i| \le \gamma \cdot b_i$.

Note, that the value of l is not defined here. It is not influencing any calculations, however it is important to state that the construction works for a fixed value of l.

Our goal is to show the existence of balanced strongly selective families of minimal size.

Given the bounding sets $B_1,...,B_l$ we say that the round Q is quiet if it satisfies the condition b). In the next proposition we show that, with appropriate choice of p, for fixed bounding sets $B_1,...,B_l$ the probability that a single round is good is at least 1/2.

Proposition 2

Let $B_1,...,B_l$ be fixed sets such that $|B_1|<|B_2|<...<|B_l|$, and $\gamma \le 1$. Then for $Q\in \mathcal {Q}_{m,p}$ we have

$$\mathbb {P}\left( \bigcap _{i\le l} |Q\cap B_i|\le \gamma \cdot b_i\right) \ge 1/2,$$

provided that the value of p satisfies $p\le \gamma /2$, and $p\cdot b_i\ge 6+i$.

A configuration is a tuple of form $(A,B_1,...,B_l)$, representing a possible arrangement of elements into central set and bounding sets. Let us define a set of all possible configurations by $\mathcal {F}$, formally

$$\begin{aligned}\mathcal {F}=\{(A,B_1,...,B_l):&A,B_1,...,B_l\subseteq [N],\ |A|=k,\ \forall _{i\ne j}\ |B_i|=b_i, \\&A\cap B_i=\varnothing ,\ B_j\cap B_i=\varnothing \}.\end{aligned}$$

We have the following bound on the size of $\mathcal {F}$.

Proposition 3

Let $\mathcal {F}$ be the set of all possible configurations. Then

$$|\mathcal {F}|\le N^{k+s},$$

where $s=b_1+...+b_l$.

Observe, that $\mathcal {Q}$ is not a $(N,k,\gamma ,\varvec{b})$-bssf if for some configuration $(A,B_1,...,B_l)$ there is an element of A that is not selected. In the next propositions we bound the probability that for a fixed choice of $A,B_1,...,B_l$ a random sequence $\mathcal {Q}_{m,p}$ does not select some element of A.

Proposition 4

Let $A, B_1,...,B_l$ be a fixed configuration, and $v\in A$. The probability that v is selected in a single round $Q\in \mathcal {Q}_{m,p}$ is at least $p/4^{pk+1}$, provided that the value of p satisfies $p\le \gamma /2$, and $p\cdot b_i\ge i+6$.

Now we bound the probability that $Q_{m,p}$ selects all elements of A in quiet rounds for a fixed configuration $A,B_1,...,B_l$. We say that a family S over [N] is good for a configuration $(A,B_1,...,B_l)\in \mathcal {F}$ if it selects all elements of A.

Proposition 5

Let $A, B_1,...,B_l$ be a fixed configuration. Let $p\le \gamma /2$, and $p\cdot b_i\ge i+6$. Then we have

Lemma 1

Let $p\le \gamma /2$, and $p\cdot b_i\ge i+6$. Then we have

$$\mathbb {P}(\mathcal {Q}_{m,p}{} \textit{ is }(N,k,\gamma ,\varvec{b})\text {-bssf} )>0,$$

provided that $m > 4^{pk+1}\cdot \frac{2k+s}{ p}\ln N,$ where $s=b_1+...+b_l$.

Proof

The sequence $\mathcal {Q}_{m,p}$ is a $(N,k,\gamma ,\varvec{b})$-balanced selector if it is good for all $(\tilde{A},\tilde{B_1},...,\tilde{B_l})\in \mathcal {F}$. Thus,

$$\begin{aligned} \mathbb {P}(\mathcal {Q}_{m,p}\text { is not } (N,k,\gamma ,\varvec{b}\text {-bssf}))&\le \sum _{\mathbf {c}\in \mathcal {F}} \mathbb {P}(\mathcal {Q}_{m,p}\text { is not good for }\mathbf {c}) \\&\le |\mathcal {F}|\cdot k\exp (-m\cdot p/4^{pk+1}) \\&\le {N^{k+s}}{}\cdot {k}\exp (-m\cdot p/4^{pk}) \\&\le \exp ((2k+s)\ln N -m\cdot p/4^{pk}) \end{aligned}$$

Thus, in order to guarantee $\mathbb {P}(\mathcal {Q}_{m,p}\text { is not }(N,k,\gamma ,\varvec{b}\text {-bssf)})<1$ it is sufficient that m satisfies the following inequality

$$(2k+s)\ln N -m\cdot p/4^{pk} < 0,$$

which is true given the assumptions regarding the value of m.

3.3 Oblivious Local Broadcast with BSSFs

In this section we provide an application of the balanced selective families to Local Broadcast in the SINR model. We proceed analogously to the result in Theorem 1 – we show that for any network of density $\varDelta$ each node transmits in some round when it is possible for all its neighbors to receive the message. The main difference with the previous result is that we do not demand that a station will be a unique transmitter among its very broad neighborhood, instead we analyze the interference carefully and exploit its nature by applying balanced selective families.

First, we show for a certain choice of $k, b_i, \gamma$ there exists a bssf of size guaranteed by the Lemma 1 for such parameters. Then, we prove that a schedule constructed from such bssf is feasible local broadcast schedule.

Let $c_1$ be a constant, whose value will be defined later. We allow for $c_1$ to depend on the model constants, that is $\alpha , \beta , \mathcal {P}$.

Let $k=c_1\varDelta ,\ b_i=c_1\varDelta \cdot 2^{2i}$, and $\gamma =1/\varDelta$. Since the length of the bssf from Lemma 1 depends highly on $s=b_1+...+b_l$ we have an incentive to choose the value of l to be as small as possible. On the other hand it is important to capture the behavior of the interference in the network through the bounding sets, which implies that the cardinality of all bounding sets needs to be high. We set the value of l to $\lambda = \lceil \log (2+\tau (2\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}) + 5 \rceil$. We give more details for this value later.

Definition 1

A geometric configuration for a point x on a plane is a partition of the network into $l+1$ sets $A^{(x)}, B^{(x)}_1,..., B^{(x)}_l$ in the following way. The k stations that are closest to x constitute the set A. The next $b_i$ stations that are closest to x go to $B^{(x)}_1$, and so on. We call the point x the perspective.

Note that the above definition is ambiguous, because it is not clear which elements to choose if there is more than one possibility. However, this will not be a problem in the following analysis, since the definition is used only to connect a configuration $A,B_1,...,B_l$ of sets with its location on a plane through the perspective point.

We identify rounds of communication with the subset of transmitting stations $Q\subseteq [N]$. For a fixed geometric configuration we say that the round Q is quiet if for all i we have $|Q\cap B_i^{(x)}|\le \gamma |B_i^{(x)}|$, which corresponds to the condition present in the definition of balanced strongly selective families.

Proposition 6

For any geometric configuration $A^{(x)},B_1^{(x)},...,B_l^{(x)}$ and $w\in B^{(x)}_i$, we have $d(x,w)\ge \sqrt{c_1}\cdot 2^{i-5}$.

Consider some point x on a plane. Our idea of handling the interference in the network is to divide it into three groups. The first group consists of first k stations closest to x, namely $A^{(x)}$. The second group consists of $B_1^{(x)}\cup ...\cup B_\lambda ^{(x)}$ (recall that $\lambda = \lceil \log (2+\tau (2\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}) + 5 \rceil$), and the last group consists of all other stations. We denote the groups by $H_1^{(x)}, H_2^{(x)}$, and $H_3^{(x)}$. The partition of the network into three groups here is crucial to the complexity of the algorithm. The interference from stations within small distance is far more influential than the interference from distant stations, thus we capture the $H_2^{(x)}$ in the bounding sets, and analyze interference coming from there carefully. On the other hand, we bound the interference from $H_3^{(x)}$ less precisely, using Corollary 1. Note, that it would be possible to fit all the stations into bounding sets (that is $H_2$), but then the total cardinality of bounding sets, that is $s=b_1+...+ b_l$, would be $\varOmega (N)$ and the length of the bssf would be $\varOmega (N\log N)$ (see Lemma 1).

Let us recall that $\mathcal {I}_d$ denotes the maximal value of interference in a fixed point v that guarantees that v can receive a message from any station at distance d, and $\mathcal {I}(X,x)=\sum _{v\in X}\mathcal {P}/d(v,x)^\alpha$. In the following two propositions we bound the interference from $H_2^{(x)}$ and $H_3^{(x)}$ for any configuration $(A^{(x)},B_1^{(x)},...,B_\lambda ^{(x)}).$

Proposition 7

Let $\varvec{c}=(A^{(x)}, B^{(x)}_1,..., B^{(x)}_\lambda )\in \mathcal {F}$ be a fixed geometric configuration. Then in each quiet round $Q\subseteq [N]$, the maximal interference coming from $H_2^{(x)}$ in B(x, 2) is bounded as follows,

$$\mathcal {I}(Q\cap H_2^{(x)}, v)\le \mathcal {I}_{1-\varepsilon }/2 \quad \textit{ for each }v\in B(x,2),$$

provided that $c_1\ge \max \{ 2^{14}, (\frac{2^{6\alpha +1}\mathcal {P}}{\mathcal {I}_{1-\varepsilon }(2^{\alpha -2}-1)})^{2/(\alpha -2)}\}$.

Proof

The good round for x means that at most $\gamma b_i$ nodes are transmitting from $B_i^{(x)}$ for each i. Let $d_i$ denote the minimal distance from the nodes in $B_i^{(x)}$ to B(x, 2). Thanks to Proposition 6 we have $d_i \ge \sqrt{c_1}\cdot 2^{i-5}-2\ge \sqrt{c_1}\cdot 2^{i-6}$ (provided that $c_1\ge 2^{14}$). Denote by $\mathcal {I}$ the maximal interference in B(x, 2) coming from the stations in $\bigcup _{i\le \lambda } B_i^{(x)}$ in a good round for $\varvec{c}$. We have

$$\begin{aligned} \mathcal {I}&\le \sum _{1\le i\le \lambda } \gamma |B_i| \cdot \frac{\mathcal {P}}{d_i^\alpha } \\&\le \sum _{1\le i\le \lambda } c_1^{1-\alpha /2}\cdot 2^{i(2-\alpha )}\cdot 2^{6\alpha } \cdot \mathcal {P}\\&\le \frac{2^{6\alpha }\mathcal {P}}{c_1^{\alpha /2 -1}}\sum _{i\ge 1} \left( \frac{1}{2^{\alpha -2}}\right) ^i = \frac{2^{6\alpha }\mathcal {P}}{c_1^{\alpha /2 -1}(2^{\alpha -2}-1)}. \end{aligned}$$

Thus, for $c_1\ge (\frac{2^{6\alpha +1}\mathcal {P}}{\mathcal {I}_{1-\varepsilon }(2^{\alpha -2}-1)})^{2/(\alpha -2)}$ we have $\mathcal {I}\le \mathcal {I}_{1-\varepsilon }/2$.

Proposition 8

In every round the maximal interference coming from $H_3^{(x)}$ to any station $v\in B(x,2)$ is at most $\mathcal {I}_{1-\varepsilon }/2$.

Proof

Let us recall $\lambda = \lceil \log (2+\tau (2\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}) + 5 \rceil$. Thanks to Proposition 6 we know that for each station $v\in H_3^{(x)}$ we have

$$\begin{aligned} d(v,x)&\ge \sqrt{c_1}\cdot 2^{\lambda -5} \ge 2+\tau (2\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}, \end{aligned}$$

since all stations in $H_3^{(x)}$ lay farther than stations from $B_\lambda ^{(x)}$. Thus, for each $u\in B(x,2)$, and $v\in H_3^{(x)}$ we have $d(u,v)\ge \tau (2\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}$ which by Corollary 1 assures that $\mathcal {I}(H_3^{(x)}, u) \le \mathcal {I}_{1-\varepsilon }/2$ for each $u\in B(x,2)$.

We have shown a way to capture interference in a network by partitioning it into groups and analyzing the interference in them separately. We crafted the analysis so it fits the construction of balanced strongly selective family. Now, we put all the pieces together in the following theorem.

Theorem 2

There exists a local broadcast schedule $\mathbf {S}$ feasible for networks of density $\varDelta$ of length $O(\varDelta ^{2+2/(\alpha -2)}\log N)$.

Proof

We show that a schedule constructed from $(N,k,\gamma ,\varvec{b})$-bssf with $\varvec{b}=(b_1,...,b_\lambda )$, where $b_i=c_1\varDelta \cdot 2^{2i}$, $\lambda = \lceil \log (2+\tau (2\varDelta /\mathcal {I}_{1-\varepsilon })^{1/(\alpha -2)}) + 5 \rceil$, $k=c_1\varDelta$, $c_1=\max \{2^{14}, (\frac{2^{6\alpha +1}\mathcal {P}}{\mathcal {I}_{1-\varepsilon }(2^{\alpha -2}-1)})^{2/(\alpha -2)} \}$ is feasible local broadcast schedule for any network of density $\varDelta$.

Let $\mathbf {S}$ be the smallest $(N,k,\gamma ,\varvec{b})$-bssf. We need to show that during the execution of $\mathbf {S}$ each station is heard by all its neighbors. Let us fix a station v and a point x on a plane such that $v\in B(x,1)$. The definition of $\mathbf {S}$ guarantees that there exists a round $Q\in \mathbf {S}$ such that $Q\cap A^{(x)} = \{v\}$, and Q is quiet for $B_1^{(x)},...,B_\lambda ^{(x)}$. Let us denote $\tilde{Q}=Q\smallsetminus \{v\}$. The total interference on any neighbor w of v is equal to

$$\begin{aligned} \mathcal {I}(\tilde{Q}\cap V, w)&= \mathcal {I}(\tilde{Q}\cap H_1^{(x)}, w)+\mathcal {I}(\tilde{Q}\cap H_2^{(x)}, w)+\mathcal {I}(\tilde{Q}\cap H_3^{(x)}, w) \le \mathcal {I}_{1-\varepsilon }, \end{aligned}$$

thanks to Propositions 7 and 8, and the fact that $\mathcal {I}(\tilde{Q}\cap H_1^{(x)}, w)=0$ (recall that $H_1^{(x)}=A^{(x)}$, and $\tilde{Q}\cap A^{(x)}=\varnothing$). This shows that in this round v transmits and interference in all its neighbors is at most $\mathcal {I}_{1-\varepsilon }$ which allows them to receive the message.

It remains to show that the length of $\mathbf {S}$ is $O(\varDelta ^{2+2/(\alpha -2)}\log N)$. Now, we use Lemma 1 to show the existence of small bssf with parameters defined at the beginning of this proof.

Let $p=\gamma /2$ and $m=\lceil 2^{c_1+1}\varDelta (2\varDelta c_1+ s)\ln N \rceil$. In order to use Lemma 1 we need to meet its assumptions, that is to guarantee that $p\cdot b_i \ge i+6$. It is easy to check, that this true for all $c_1\ge 3$. By Lemma 1 we know that $\mathcal {Q}_{m,p}$ is a $(N,k,\gamma ,\varvec{b})$-bssf with non-zero probability, thus there exists bssf of given parameters of size at most m. In order to estimate the value of m let us bound the sum of sizes of all bounding sets,

$$\begin{aligned} s&=b_1+...+b_\lambda =\sum _{1\le i\le \lambda }c_1\varDelta \cdot 2^{2i} =c_1\varDelta \frac{4^{\lambda +1}-1}{3}\\&\le 2^8 c_1\varDelta \left( 2+\tau (\frac{2\varDelta }{\mathcal {I}_{1-\varepsilon }})^{1/(\alpha -2)}\right) ^2=O(\varDelta ^{\alpha /(\alpha -2)}). \end{aligned}$$

Thus the size of $\mathbf {S}$ is at most $m = O(\varDelta (\varDelta +\varDelta ^{\alpha /(\alpha -2)})\log N) = O(\varDelta ^{2+2/(\alpha -2)}\log N)$, which concludes the proof.

4 Local Broadcast with Feedback

In this section we provide another structure enabling to accomplish partial local broadcast – meaning that only a fraction of nodes will be heard by all its neighbors. This allows us to substantially reduce the size of the schedule to $O(\varDelta \log N)$ in networks of diameter $\varDelta$. Such approach also gives us an efficient solution to local broadcast in a scenario of semi-oblivious networks, with acknowledgments. In such networks, the only action of a node, apart from executing a given schedule, is to quit the protocol at the point when the node was heard by all its neighbors.

We construct a combinatorial structure similar to the one used in previous section. However, there are some major changes both in application of the structure to the SINR networks, and in the analysis of the structure itself. The analysis from the previous section does not allow to reduce the size of the family to $O(\varDelta \log N)$. To enable this, we introduce changes in the definition of bounding sets, allowing for more stations to be selected in quiet rounds. However, this enforces a more careful analysis of the interference in the network later.

4.1 Fractional Balanced Selectors

In this section we give the definition of fractional balanced selectors (FBS), which is suited for the use in the local broadcast algorithm. That definition may be generalized, allowing for another parameters, and perhaps be used in other algorithms. However, in this section whenever we speak of fractional balanced selector, we mean an FBS with specific parameters, that are defined in the next paragraph. We treat the selectors as if they are transmission schedules already. Particularly, if some element $v\in [N]$ is present in $Q\subseteq [N]$ we say that v transmits in round Q.

Our goal here is to show a fractional balanced selector, that is $\mathcal {Q}$ such that, for any C, A, such that $C\subseteq A \subseteq [N]$, where $|C|=\varDelta$ and $|A|=k$ there are rounds $Q\in \mathcal {Q}$ for at least half of all elements $v\in C$ such that: (i) $Q\cap A=\{v\}$, (ii) $|Q\cap B_i |\le |B_i|\delta ^{i+k}/k$ for all i, where $|B_i|=b_i, b_i= k 2^{2i}, k=c_1\varDelta , c_1=(\delta ^c)^{(2+\alpha )/(2\alpha )}$, and $\alpha$ is the SINR Model constant, and values of $\delta$, and c are to be determined later.

Wherever we say that $C,A,B_1,...,B_l$ are fixed configuration, we mean that they are disjunct, fixed subsets of [N], such that $|C|=\varDelta , |A|=k,$ and $|B_i|=k2^{2i}$.

The general idea in this section is to prove that the family $\mathcal {Q}_{m,p}$ for certain values of m and p is FBS with non-zero probability. We do it in two steps. First, we show that with probability greater than 1/2 it satisfies the following property: for all configurations $(C,A,B_1,...,B_l)$ there are at least $\sigma$ rounds Q such that $|Q\cap B_i|\le |B_i|\delta ^{i+k}/k$ for all i (see the second condition in the above definition). Then, we show that with probability greater than 1/2 any subset of $\sigma$ rounds satisfies the first condition, that is it selects at least half of elements in C. Hence, with non-zero probability there is a subset of $\sigma$ rounds in which the number of transmitters from $B_i$’s is bounded and elements of C are being selected.

A sequence of sets $\mathcal {Q}$ is i-bounding if $\sum _{Q\in \mathcal {Q}} |Q\cap B|\le mb_i/k$ for all $B\subseteq [N]$ of size $b_i$. We say that $\mathcal {Q}$ is bounding if it is i-bounding for all $i\le l$. In the following two propositions we show that with probability greater than 1/2 the family $\mathcal {Q}_{m,p}$ is bounding.

Proposition 9

Let $C,A,B_1,...,B_l$ be a fixed configuration, and $p= 1/(2k)$. For $\mathcal {Q}_{m,p}$ we define $X_i=\sum _{Q\in \mathcal {Q}_{m,p}} |Q\cap B_i|$, that is the total number of “transmissions” from the set $B_i$. We have

$$\mathbb {P}(X_i \ge m|B_i|/k) \le \exp (-m|B_i|/6k).$$

Proposition 10

Let $p=1/(2k)$, then we have

$$\mathbb {P}(\mathcal {Q}_{m,p}{} \textit{ is bounding}) > \frac{1}{2},$$

provided that $m>6k\left( \ln (2l)+\ln N+1\right)$.

The following lemma is purely deterministic. We show there that if a family of sets $\mathcal {Q}$ is bounding, then it cannot have too many spoiled rounds.

Lemma 2

If a family $\mathcal {Q}$ of size m is bounding then for any configuration $A,B_1,...,B_l$ the number of spoiled rounds in $\mathcal {Q}$ is at most $m/\kappa$, where $\kappa =(\delta ^{c}(\delta -1))$.

This concludes the first step of the analysis. Now, we know that with probability at least 1/2 there at most $m/\kappa$ rounds are spoiled by too many transmitters from bounding sets. It remains to show that for any subset of $m-m/\kappa$ quiet rounds there are at least $\varDelta /2$ distinct selections from the set C.

We say that a family of sets $\mathcal {Q}$ is (N, a, b)-inner-selective if for any sets $\hat{A}\subseteq \hat{B}$ such that $|\hat{A}|=a,|\hat{B}|=b$ for at least half elements $x\in \hat{A}$ of $\hat{A}$ there exists an $Q\in \mathcal {Q}$ such that $Q\cap B=\{x\}$. We say that a family $\mathcal {Q}$ of subsets of [N] is $(N,\varDelta ,k,\sigma )$-good if any subset $\mathcal {Q}'\subseteq \mathcal {Q}$ of size $\sigma$ is $(N,\varDelta ,k)$-inner-selective.

Now, we are ready to make the second step in the proof. We show, that for certain parameters $\mathcal {Q}_{m,p}$ is $(N,\varDelta ,k,\sigma )$-good with probability at least 1/2.

Lemma 3

Let $p=1/(2k)$, $\kappa = \delta ^c(\delta -1)$, and $\sigma =m(1-\frac{1}{\kappa })$.

$$\mathbb {P}\left( \mathcal {Q}_{m,p}{} \textit{ is }(N,\varDelta ,k,\sigma )-\textit{good}\right) \ge \frac{1}{2},$$

Provided that $m\ge \frac{16k}{\varDelta (1-1/ \kappa )}(k\ln (N/k)+3k+\ln 2)$, and $c\ge 2\log _a(2b/\ln a)$, where $a=\delta ^{(\alpha -2)/(2\alpha )}$, $b=\max \{\frac{32(\ln \delta +\ln (\delta -1)+1)}{\delta -1},1\}$.

Theorem 3

Let $p=1/(2k)$, $\kappa =\delta ^c(\delta -1)$, $\sigma =m(1-1/\kappa )$

$$\mathbb {P}(\mathcal {Q}_{m,p}{} \textit{ is a fractional balanced selector})>0,$$

provided that $m\ge \max \{ 6k\left( \ln (2l)+\ln N+1\right) +1, \frac{16k}{\varDelta (1-1/\kappa )}(k\ln (N/k)+3k+\ln 2)\}$, and $c\ge 2\log _a(2b/\ln a)$, where $a=\delta ^{(\alpha -2)/(2\alpha )}$, $b=\max \{\frac{32(\ln \delta +\ln (\delta -1)+1)}{\delta -1},1\}.$

Because of the complicated formulas in the theorem above, we state its main consequence more clearly in the following corollary.

Corollary 3

There exists a fractional balanced selector of size $O(\varDelta \log (N))$.

4.2 Semi-oblivious Algorithm with Acknowledgements

Observe, that if we allow for a node to get an acknowledgement when all its neighbors receive its message, then it can quit from further execution of the protocol. Then, after first execution of FBS for networks of density $\varDelta$, the density of the network drops to $\varDelta /2$, since all the nodes that transmitted successfully during the first FBS quit the protocol. Then, we run an FBS for networks of density $\varDelta /2$, and so on. When the density of the network drops below $\varDelta ^{1/(2+4/(\alpha -2))}$ we use the result of Theorem 1 to make sure that all nodes transmitted successfully.

Theorem 4

There exists a semi-oblivious algorithm for local broadcast in networks of density $\varDelta$ that runs in $O(\varDelta \log N)$ rounds, assuming that nodes are capable of using acknowledgements of successful transmissions.