Deterministic Digital Clustering of Wireless Ad Hoc Networks

∗

Tomasz Jurdziński1 , Dariusz R. Kowalski2 , Michal Różański1 , and Grzegorz Stachowiak1
1

arXiv:1708.08647v4 [cs.DS] 12 Jan 2018

2

Institute of Computer Science, University of Wroclaw, Poland
Department of Computer Science, University of Liverpool, United Kingdom

Abstract
We consider deterministic distributed communication in wireless ad hoc networks of identical
weak devices under the SINR model without predefined infrastructure. Most algorithmic results
in this model rely on various additional features or capabilities, e.g., randomization, access to
geographic coordinates, power control, carrier sensing with various precision of measurements,
and/or interference cancellation. We study a pure scenario, when no such properties are available.
The key difficulty in the considered pure scenario stems from the fact that it is not possible to
distinguish successful delivery of message sent by close neighbors from those sent by nodes located
on transmission boundaries. This problem has been avoided by appropriate model assumptions
in many results, which simplified algorithmic solutions.
As a general tool, we develop a deterministic distributed clustering algorithm, which splits
nodes of a multi-hop network into clusters such that: (i) each cluster is included in a ball of
constant diameter; (ii) each ball of diameter 1 contains nodes from O(1) clusters. Our solution
relies on a new type of combinatorial structures (selectors), which might be of independent interest.
Using the clustering, we develop a deterministic distributed local broadcast algorithm accomplishing this task in O(∆ log∗ N log N ) rounds, where ∆ is the density of the network. To the best
of our knowledge, this is the first solution in pure scenario which is only polylog(n) away from
the universal lower bound Ω(∆), valid also for scenarios with randomization and other features.
Therefore, none of these features substantially helps in performing the local broadcast task.
Using clustering, we also build a deterministic global broadcast algorithm that terminates
within O(D(∆ + log∗ N ) log N ) rounds, where D is the diameter of the network. This result
is complemented by a lower bound Ω(D∆1−1/α ), where α > 2 is the path-loss parameter of the
environment. This lower bound, in view of previous work, shows that randomization or knowledge
of own location substantially help (by a factor polynomial in ∆) in the global broadcast. Therefore,
unlike in the case of local broadcast, some additional model features may help in global broadcast.

1

Introduction

We study distributed algorithms in ad hoc wireless networks in the SINR (Signal-to-Interferenceand-Noise Ratio) model with uniform transmission power. We consider the ad hoc setting where
both capability and knowledge of nodes are limited – nodes know only the basic parameters of the
SINR model (i.e., α, β, ε, N ) and upper bounds ∆, n on the degree and the size of the network, such
that the actual maximal degree is O(∆) and the size is nO(1) . Such a setting appears in networks
without infrastructure of base nodes, access points, etc., reflecting e.g. scenarios where large sets
of sensors are distributed in an area of rescue operation, environment monitoring, or in prospective
internet of things applications. Among others, we study basic communication problems as global and
∗

This work was supported by the Polish National Science Centre grant DEC-2012/07/B/ST6/01534.

1

local broadcast, as well as primitives used as tools to coordinate computation and communication
in the networks (e.g., leader election and wake-up). Most of these problems were studied in the
model of graph-based radio networks over the years. Algorithmic study of the closer to reality
SINR model has started much later. This might be caused by specific dynamics of interferences and
signal attenuation, which seems to be more difficult for modeling and analysis than graph properties
appearing in the radio network model (see e.g. [28]).
As for the problems studied in this paper, several distributed algorithms have been presented in
recent years. However, all these solutions were either randomized or relied on the assumption that
nodes of a network know their own coordinates in a given metric space. In contrast, the aim of this
paper is to check how efficient could be solutions without randomization, availability of locations,
power control, carrier sensing, interference cancellation or other additional model features, in the
context of local and global communication problems. Our research objective is motivated twofolds.
Firstly, examination of necessity of randomization is a natural research topic in algorithmic community for classic models of sequential computation as well as for models of parallel and distributed
computing (see e.g. [3] for an example in a related radio networks model). Moreover, as wireless ad
hoc networks are usually built from computationally limited devices run on batteries, it is desirable
to use simple and energy efficient algorithms which do not need access to several sensing capabilities
or true randomness.

1.1

The Network Model.

We consider a wireless network consisting of nodes located on the 2-dimensional Euclidean space1 .
We model transmissions in the network with the SINR constraints. The model is determined by
fixed parameters: path loss α > 2, threshold β > 1, ambient noise N > 0 and transmission power
P. The value of SIN R(v, u, T ) for given nodes u, v and a set of concurrently transmitting nodes T
is defined as
P/d(v, u)α
P
SIN R(v, u, T ) =
,
(1)
N + w∈T \{v} P/d(w, u)α
where d(u, v) denotes the distance between u and v. A node u successfully receives a message from
v iff v ∈ T and SIN R(v, u, T ) ≥ β, where T is the set of nodes transmitting at the same time.
Transmission range is the maximal distance at which a node can be heard provided there are no
other transmitters in the network. Without loss of generality we assume that the transmission range
is all equal to 1. This assumption implies that the relationship P = N β holds. However, it does not
affect generality and asymptotic complexity of presented results.
Communication graph In order to describe the topology of a network as a graph, we set a
connectivity parameter ε ∈ (0, 1). The communication graph G = (V, E) of a given network consists
of all nodes and edges {v, u} connecting nodes that are in distance at most 1 − ε, i.e., d(u, v) ≤ 1 − ε.
Observe that a node can receive a message from a node that is not its neighbor in the graph, provided
interference from other nodes is small enough. The communication graph, defined as above, is a
standard notion in the analysis of ad hoc multi-hop communication in the SINR model, cf., [10, 25].
Synchronization and content of messages We assume that algorithms work synchronously in
rounds. In a single round, a node can transmit or receive a message from some node in the network
and perform local computation. The size of a single message is limited to O(log N ).
Knowledge of nodes Each node has a unique identifier from the set [N ] = {1, . . . , N }, where
N = nO(1) is the upper bound on the size n of the network. Moreover, nodes know N , the SINR
parameters – P, α, β, ε, N , the linear upper bounds on the diameter D and the degree ∆ of the
communication graph.
1
Results of this paper can be generalized to so-called bounded-growth metric spaces with the same asymptotic
complexity bounds.

2

Communication problems The global broadcast problem is to deliver a message from the designated source node s to all the nodes in the network, perhaps through relay nodes as not all nodes
are within transmission range of the source in multi-hop networks. At the beginning of an execution
of a global broadcast algorithm, only the source node s is active (i.e., only s can participate in the
algorithm’s execution). A node v 6= s starts participating in an execution of the algorithm only
after receiving the first message from another node. (This is so-called non-spontaneous wake-up
model, popular in the literature.) In the local broadcast problem, the goal is to make each node to
successfully transmit its own message to its neighbors in the communication graph. Here, all nodes
start participating in an algorithm’s execution at the same round.

1.2

Related Work

In the last years the SINR model was extensively studied, both from the perspective of its structural
properties [2, 20, 28] and algorithm design [16, 4, 10, 18, 22, 35, 29, 21].
The first work on local broadcast in SINR model by Goussevskaia et al. [16] presented an
O(∆ log n) randomized algorithm under assumption that density ∆ is known to nodes. After that,
the problem was studied in various settings. Halldorsson and Mitra presented an O(∆ + log2 n)
algorithm in a model with feedback [19]. Recently, for the same setting Barenboim and Peleg
presented solution working in time O(∆ + log n log log n) [4]. For the scenario when the degree ∆
is not known Yu et al. in [35] improved on the O(∆ log3 n) solution of Goussevskaia et al. to
O(∆ log n + log2 n).
In [22] a O(∆ log3 n)-round deterministic local broadcast algorithm was presented under the
assumption that nodes have access to location information (their coordinates). However, no deterministic algorithm for local broadcast was known in the scenario that nodes do not know their
coordinates.
Previous results on local broadcast are collected and compared with our result in Table 1. There
are also a few algorithms which require carrier sensing or power control (e.g., [15]). As the model and
techniques in this line of work are far from the topic of our paper, those solutions are not presented
in the table.
Paper
[16]
[16]
[35]
[19]
[4]
[22]
This

Model
Knowledge
Time
Randomized algorithms
∆, n
O(∆ log n)
n
O(∆ log3 n)
n
O(∆ log n + log2 n)
feedback
∆, n
O(∆ + log2 n)
feedback
∆, n
O(∆ + log n log log n)
Deterministic algorithms (for N = poly(n))
location
∆, N
O(∆ log3 n)
work
∆, N
O(∆ log∗ n log n)

Table 1: Algorithms for the local broadcast problem. The column Model enumerates features which
do not appear in the model of this paper, while they are needed to implement particular algorithms.
For the global broadcast problem a few deterministic solutions are known. If the information
about location of nodes is available, the global broadcast can be accomplished deterministically
in time O(D log2 n) [26]. In contrast, if connectivity of a network might rely on so-called weak
links and the model does not allow for any channel sensing nor access to geographic coordinates,

3

deterministic global broadcast requires Θ(n log N ) rounds [27], which gives logarithmic improvement
over O(n log2 n)-time algorithm from [10] for this model.
The main randomized results on global broadcast in ad hoc settings include papers of Daum et
al. [10] and Jurdzinski et al. [25]. Solutions with complexity, respectively O((D log n) logα+1 g) and
O(D log2 n) are presented, where g is a parameter depending on the geometry of the network, at
most exponential with respect to n. (Results on global broadcast are collected and compared with
our result in Table 2.)
Recently Halldorsson et al. [18] proposed an algorithm which can be faster assuming that nodes
are equipped with some extra capabilities (e.g., detection whether a received message is sent from a
close neighbor) and the interference function on the local (one-hop) level is defined as in the classic
radio network model. Given additional model features as channel/carrier sensing, total interference estimation by signal measurements and others, efficient algorithms for various communication
problems have been designed in recent years, e.g., [17, 33, 31].
Paper

[10]
[10]
[24]
[25]
[26]
[27]
This work
This work

Model:
extra features

Model:
Knowledge
Time
weaknesses
Randomized algorithms
n
O((D log n) logα+1 g)
weak links
n
O(n log2 n)
location
n
O(D log n + log2 n)
n
O(D log2 n)
Deterministic algorithms (for N = poly(n))
location
N
O(D log2 n)
weak links
N
Θ(n log n)
∆, N
Ω(D∆1−1/α )
∆, N
O(D(∆ + log∗ n) log n)

Table 2: Algorithms for the global broadcast problem.
In the related multi-hop radio network model the global broadcast problem is well examined. The
complexity of randomized broadcast is of order of Θ((D+log n) log(n/D)) [3, 9, 30]. A series of papers
on deterministic global broadcast give the upper bound of O(n min{log n, log D log log(D∆/n)} [5,
9, 11] with the lower bound of Ω(n log n/ log(n/D)) [30]. In terms of ∆ and D, the best bounds are
O(D∆ log(N/∆) log1+α N ) and Ω(D∆ log(N/∆) [7]. For the closest to our model geometric unitdisk-graph radio networks, the complexity of broadcast is Θ(D∆) [12, 13], even when nodes know
their coordinates.
Recently, communication algorithms have been also designed in a very weak beeping networks
[8, 14], where a node can only distinguish between 0 or at least one of its neighbors transmitting on
the communication channel.

1.3

Our Contribution

As a general tool, we develop a clustering algorithm which splits nodes of a multi-hop network into
clusters such that: (i) each cluster is included in a ball of constant diameter; (ii) each ball of diameter
1 contains nodes from O(1) clusters. Using the clustering algorithm, we develop a local broadcast
algorithm for ad hoc wireless networks, which accomplishes the task in O((∆ + log∗ n) log n) rounds,
where ∆ is the density of the network. Up to our knowledge, this is the first solution in the considered
pure ad hoc scenario which is only polylog(n) away from the trivial universal lower bound Ω(∆),
valid also for scenarios with randomization and other features.
4

Using clustering, we also build a deterministic global broadcasting algorithm that terminates
within O(D(∆ + log∗ n) log n) rounds, where D is the diameter of the network graph. This result is
complemented by a lower bound Ω(D∆1−1/α ) in the network of degree ∆, where α > 2 is the path-loss
parameter of the environment. This lower bound, in view of previous work, shows that randomization
or knowledge of own location substantially help (by a factor polynomial in ∆) in the global broadcast.
Previous results on global broadcast in related models achieved time O(D polylogN ), thus they were
independent of the networks density ∆. They relied, however, on either randomization, or access to
coordinates of nodes in the Euclidean space, or carrier sensing (a form of measurement of strength
of received signal). Without these capabilities, as we show, the polynomial dependence of ∆ is
unavoidable.
Therefore, our results prove that additional model features may help in global communication
problems, but not much in local problems such as local broadcast, in which advanced algorithms
are (almost) equivalent to the presence of additional model features. Using designed algorithmic
techniques we also provide efficient solutions to the wake-up problem and the global leader election
problem.

1.4

High Level Description of Our Technique

The key challenge in designing efficient algorithm in the ad hoc wireless scenario is the interference
from dense areas of a network. Note that if randomization was available, nodes could adjust their
transmission probabilities and/or signal strength such that the expected interference from each ball
of radius 1 is bounded by a constant.
Another problem stems from the fact that it is impossible to distinguish received messages which
are sent by close neighbors from those sent by nodes on boundaries of the transmission range. This
issue could be managed if nodes had access to their geographic coordinates or were equipped with
carrier sensing capabilities (thanks to them, the distance of a neighbor can be estimated based on a
measurement of the strength of received signal). In the pure ad hoc model considered in this paper,
all those tools are not available.
Our algorithmic solutions rely on the notion of r-clustering, i.e., a partition of a set of nodes
into clusters such that: (i) each cluster is included in a ball of radius r; (ii) each ball of radius 1
contains nodes from O(1) clusters and (iii) each node knows its cluster ID. First, we develop tools
for (partially) clustered networks. We start with a sparsification algorithm, which, given a set of
clustered nodes W , gradually decreases the largest number of nodes in a cluster and eventually ends
with a set W 0 ⊂ W such that O(1) (and at least one!) nodes from each cluster of W belongs to W 0 .
Using sparsification algorithm, we develop a tool for imperfect labeling of clusters, which results in
assigning temporary IDs (tempID) in range O(∆) to nodes such that O(1) nodes in each cluster have
the same tempID. Moreover, an efficient radius reduction algorithm is presented, which transforms
r-clustering for r > 1 into 1-clustering.
Two communication primitives are essential for efficient implementation of our tools, namely,
Sparse Network Schedule (SNS) and Close Neighbors Schedule (CNS). Sparse Network Schedule is a
communication protocol of length O(log N ) which guarantees that, given an arbitrary set of nodes
X with constant density, each element v of X performs local broadcast (i.e., there is a round in
which the message transmitted by v is received in distance 1 − ε). Close Neighbors Schedule is a
communication protocol of length O(log N ) which guarantees that, given an arbitrary set of nodes
X of density Γ with r-clustering of X for r = O(1), each close enough pair of elements of X from
each sufficiently dense cluster can hear each other during the schedule.
Given the above described tools for clustered set of nodes, we build a global broadcasting algorithm, which works in phases. In the ith phase we assure that all nodes awaken2 in the (i − 1)-st
2

A node is awaken in the phase j if it receives the broadcast message for the first time in that phase.

5

phase perform local broadcast. In this way, the set of nodes awaken in the first i phases contains
all nodes in communication graph of distance i from the source. Moreover, we assure that all nodes
awaken in a phase are 1-clustered. (We start with the cluster formed by nodes in distance ≤ 1 from
the source s, awaken in a round in which s is the unique transmitter.) A phase consists of three
stages. In Stage 1, an imperfect labeling of each cluster is done. In Stage 2, Sparse Network Schedule
is executed ∆ times3 . A node with label j participates in the jth execution of SNS only. In this
way, all nodes transmit successfully on distance 1 − ε. All nodes awaken in Stage 2 inherit cluster
ID from nodes which awaken them. In this way, we have 2-clustering of all nodes awaken in Stage 2.
In Stage 3, a 1-clustering of awaken nodes is formed by using an efficient algorithm that reduces the
radius of clustering. Figure 1 provides an example describing a phase.

(a) Black, red and blue nodes were awaken in
phase i−1, they are 1-clustered (colors correspond
to clusters). Gray nodes are asleep neighbors of
awaken nodes.

(b) Stage 2: in the jth execution of Sparse Network Schedule, only nodes with label j from each
cluster participate (black, red and blue nodes).

(c) During Stage 2 asleep nodes (gray in Figure (a); black, red and blue in Figure (c)) receive messages from their awaken neighbors. After Stage 2, newly awaken nodes inherit cluster
IDs (colors) of neighbors which awaken them.

(d) In Stage 3, newly awaken nodes build a new
1-clustering, using the algorithm which “reduces”
a 2-clustering to a 1-clustering.

Figure 1: An illustration of phase i > 1 of the global broadcast algorithm. Squares denote centres
of clusters (corresponding to nodes from these clusters).
Our algorithm for local broadcast builds a 1-clustering of the whole network, assigns tempIDs
to nodes in clusters with use of the imperfect labeling algorithm, and eventually performs local
broadcast by applying Sparse Network Schedule for each prospective tempID separately. (Recall
3

Here, we assume that ∆ is the maximal number of nodes in a ball of radius 1. This number differs from the degree
of the communication graph by a constant multiplicative factor.

6

that, in the local broadcast problem, all nodes are awaken simultaneously, just at the beginning of
a protocol.) Thus, the key challenge here is to build a 1-clustering starting from an unclustered
network. First, we use our sparsification technique to build a sparse set of leaders and a schedule S
such that each node of the network is in distance of O(log N ) hops from some leader with respect
to the schedule S. Then, starting from clusters containing neighbors of leaders, we gradually build
clustering of the whole network.
For efficient implementation of our solutions, we build a new type of selectors, called witnessed
(cluster aware) strong selectors. These selectors implement algorithmically an implicit collision detection, which filters out most connections on large distance in an execution of Close Neighbors
Schedule. Therefore, properties of the new selectors might be applicable for designing efficient (deterministic) solutions for other communication problems.

1.5

Organization of the paper

Section 2 contains basic notions and definitions. Combinatorial tools are introduced and applied to
build SINR communication primitives in Section 3. Section 4 describes the sparsification technique
which leads to the clustering algorithm. In Section 5, we describe solutions of global/local broadcast
as well as other communication problems. Finally, a lower bound for global broadcast is provided.

2

Preliminaries

Geometric definitions Let B(x, r) denote the ball of radius r around point x on the plane. That
is, B(x, r) = {y | d(x, y) ≤ r}. We identify B(x, r) with the set of nodes of the network that are
located inside B(x, r). A unit ball is a ball with radius 1. Let χ(r1 , r2 ) denote the maximal size
of a set of points S located in a ball of radius r1 such that d(u, v) ≥ r2 for each u, v ∈ S such that
u 6= v.
Clustered and unclustered sets of nodes Assume that each node from a given set is associated
with a pair of numbers (v, φ), where v ∈ [N ] is its unique ID and φ ∈ [N ] is the cluster of v,
φ = cluster(v). A set X of pairs (v, φ) associated to nodes is called a clustered set of nodes. The set
X is partitioned into clusters, where cluster φ denotes the set {(v, φ0 ) ∈ X | φ0 = φ}.
An unclustered set X of nodes is just a subset of [N ], which might be also considered as a clustered
set, where each node’s cluster ID is equal to 1, i.e., cluster(v) = 1 for each v ∈ X.
Geometric clusters Consider a clustered set of nodes X such that each node is located in the
Euclidean plane (i.e, it has assigned coordinates determining its location). The clustering of X is an
r-clustering for r ≥ 1 if the following conditions are satisfied:
• For each cluster φ, all of nodes from the cluster φ are located in the ball B(x, r), where x is an
element of φ called the center of φ.
• For each clusters φ1 , φ2 , the centers x1 , x2 of φ1 , φ2 are located in distance at least 1 − ε, i.e.,
d(x1 , x2 ) ≥ 1 − ε.
The density Γ of an unclustered network/set denotes the largest number of nodes in a unit ball.
For a clustered network/set G, the density is equal to the largest number of elements of a cluster.
Below, we characterize dependencies between the degree of the communication graph and the density
of the network.
Fact 1. Let ∆V be equal to the largest degree in the communication graph G. Then,
1. There exist constants 0 < c1 < c2 such that the density of each unclustered network V is in the
range [c1 ∆V , c2 ∆V ].
7

2. There exist constants 0 < c1 < c2 such that the density of each r-clustered network V for r ∈ [1, 2]
is in the range [c1 ∆V , c2 ∆V ].
As the density of a network and the degree of its communication graph are linearly dependent,
we will use ∆/Γ to denote both the density and the degree of the communication graph.4 For a
clustered set of density Γ, a cluster is dense when it contains at least Γ/2 elements. Similarly, for an
unclustered set of density Γ, a unit ball B is dense when it contains at least Γ/2 elements.
In the following, we define the notion of a close pair, essential for our network sparsification
technique.
Let dΓ,r be the smallest number satisfying the inequality χ(r, dΓ,r ) ≥ Γ/2. Thus,
according to the definition of the function χ and the definition of a dense cluster/ball, the smallest
distance between nodes of a dense cluster (unit ball, resp.) in an r-clustered (unclustered, resp.)
network is at most dΓ,r (dΓ,1 , resp.).
Definition 1. Nodes u, w form a close pair in an r-clustered network of density Γ if the following
conditions hold for some ζ ∈ (0, 1] and cluster φ:
a) cluster(u) = cluster(w) = φ,
b) d(u, w) = ζdΓ,r ≤ 1 − ε,
c) d(u, x) ≥ d(u, w) and d(w, x) ≥ d(u, w) for each x 6∈ {u, w} from the cluster φ = cluster(u) =
cluster(w);
d) d(u0 , w0 ) ≥ d(u, w)/2 for any u0 6= w0 such that u0 , w0 ∈ B(u, ζ) ∪ B(w, ζ) and cluster(u0 ) =
cluster(w0 ) = φ.
The nodes u, w form a close pair in an unclustered network of density Γ iff the above conditions
(a)–(d) hold provided cluster(x) = 1 for each node x of a network and r = 1.
A node v is a close neighbor of a node u iff (u, v) is a close pair.
An intuition behind the requirements of the definition of a close pair is as follows. In the clustered
case, only the pairs inside the same cluster are considered to be a close pair, by (a). The requirement
of (b) states that u and w can form a close pair only in the case that d(u, w) is at most the upper
bound on the smallest distance between closest nodes of a dense cluster/ball. The item (c) assures
that u is the closest node to w and w is the closest node u. Finally, (d) states that u and w can
be a close pair only in the case that the distances between nodes in their close neighbourhood are
not much smaller than d(u, w). This requirement’s goal is to count u, w as a close pair only in the
case that d(u, w) is of the order of the smallest distance between nodes in some neighbourhood.
Polynomial attenuation of strength of signals with the power α > 2 in the SINR model will assure
that, for a close pair u, w, a successful reception of a message from u to w will depend on behaviour
of some constant number of the nodes which are closest to u and w. We formalize this intuition in
further part of this work (Lemmas 5 and 6). In the following lemma we observe presence of close
pairs in dense areas of a network.
Lemma 1. Assume that the density of a set of nodes X is Γ. Then,
1. If X is unclustered, then there is a close pair in each ball B(x, 5) such that B(x, 1) is dense.
2. If X is clustered, then there is a close pair in each dense cluster.
4

This overuse of notations has no impact on asymptotic upper bounds on complexity of algorithms designed in this
paper, since dependence on density/degree will be at most linear.

8

Imperfect labeling Assume that a clustering of a set X of nodes with density Γ is given. Then,
c-imperfect labeling of X is a labeling of all elements of X such that label(x) ≤ Γ for each x ∈ X
and, for each cluster φ ∈ [N ] and each label l ∈ [N ], the number of nodes from the cluster φ with
label l is at most c, where c is a fixed constant. That is, the labeling is “imperfect” in the sense that,
instead of unique labels, we guarantee that each label is assigned to at most c nodes in a cluster.

3

Combinatorial Tools for SINR communication

In this section, we introduce combinatorial structures applied in our algorithms and basic communication primitives using these structures.

3.1

Combinatorial tools

In this section we will apply the idea (known e.g. from deterministic distributed algorithms in radio
networks) to use families of sets with specific combinatorial properties as communication protocols in
such a way that the nodes from the ith set of the family are transmitters in the ith round. Below, we
give necessary definitions to apply this approach, recall some results and build our new combinatorial
structures.
A transmission schedule for unclustered (clustered, resp.) sets is defined by (and identified with)
a sequence S = (S1 , ..., St ) of subsets of [N ] ([N ] × [N ], resp.), where the ith set determines nodes
transmitting in the ith round of the schedule. That is, a node with ID v ∈ [N ] (and cluster(v) = φ,
resp.) transmits in round i if and only if v ∈ Si ((v, cluster(v)) ∈ Si , resp.).
A set S ⊆ [N ] selects x ∈ X from X ⊆ [N ] when S ∩ X = {x}. The family S of sets over [N ]
is called (N, k)-strongly selective family (or (N, k)-ssf) if for each subset X ⊆ [N ] such that |X| ≤ k
and each x ∈ X there is a set S ∈ S that selects x from X. It is well known that there exist (N, k)-ssf
of size O(k 2 log(N/k)) for each k ≤ N , [6].
We introduce a combinatorial structure generalizing ssf in two ways. Firstly, it will take clustering
into account, assuming that some clusters might be “in conflict”. Secondly, selections of elements
from a given set X will be “witnessed” by all nodes outside of X. As we show later, this structure
helps to build a sparse graph in a SINR network, such that each close pair is connected by an edge.
We start from a basic variant called witnessed strong selector (wss), which does not take clustering
into account. (A restricted variant of wss has been recently presented in [27].) Then, we generalize
the structure to clustered sets. We call this variant witnessed cluster aware strong selector (wcss).
Witnessed strong selector. Below, we introduce the witnessed strong selector which extends the
notion of ssf by requiring that, for each element x of a given set X of size k and each y 6∈ X, x is
selected from X by such a set S from the selector that y ∈ S as well.
A sequence S = (S1 , . . . , Sm ) of sets over [N ] satisfies witnessed strong selection property for a
set X ⊆ [N ], if for each x ∈ X and y 6∈ X there is a set Si ∈ S such that X ∩ Si = {x} and y ∈ Si .
One may think that y is a “witness” of a selection of x in such a case. A sequence S = (S1 , . . . , Sm )
is a (N, k)-witnessed strong selector (or (N, k)-wss) of size m if, for every subset X ⊆ [N ] of size k,
the family S satisfies the witnessed strong selection property for X.
Note that any (N, k)-wss is also, by definition, an (N, k)-ssf. Additionally, (N, k)-wss guarantees
that each element outside of a given set X of size k has to be a “witness” of selection of every element
from X.
Below we state an upper bound on the optimal size of (N, k)-wss. It is presented without a proof,
since its generalization is given in Lemma 3 and accompanied by a proof which implies Lemma 2
(Lemma 2 is an instance of Lemma 3 for the number of clusters l = 1).
Lemma 2. For each positive integers N and k ≤ N , there exists an (N, k)-wss of size O(k 3 log N ).
9

Now, we generalize the notion of (N, k)-wss to the situation that witnessed strong selection
property is analyzed for each cluster separately, assuming that each cluster might be in conflict with
l other clusters. The conflict between the clusters φ1 and φ2 means that a selection of an element
from φ1 by a set S from the selector is possible only in the case that the considered set S does not
contain any element from the cluster φ2 .
(N, k, l)-witnessed cluster aware strong selector. We say that a set S ⊆ [N ]2 is free of cluster
φ if for all (x, φ0 ) ∈ S we have φ0 6= φ. A set S is free of the set of clusters C if it is free of each
cluster φ ∈ C. Let X ⊆ [N ] × {φ} be a set of nodes from the cluster φ and C ⊆ [N ] \ {φ} be a set of
clusters in conflict with the cluster φ. Then, a sequence S = (S1 , ..., Sm ) of subsets of [N ]2 satisfies
witnessed cluster aware selection property (wcss property) for X with respect to C if for each x ∈ X
and each y 6∈ X from cluster φ (i.e., y ∈ [N ] × {φ}) there is a set Si such that Si ∩ X = {x}, y ∈ Si
and Si ∩ ([N ] × C) = ∅ (i.e., Si is free of clusters from C). In other words, wcss property requires
that for each x ∈ X and each y 6∈ X from φ = cluster(x), x is selected by some Si , y is a witness of
a selection of X by Si (i.e., y ∈ Si ), and Si is free of the clusters from C.
A sequence S = (S1 , ..., Sm ) of subsets of [N ]2 is a (N, k, l)-witnessed clusters aware strong
selector (or (N, k, l)-wcss) if for any set of clusters C ⊆ [N ] of size l, any cluster φ 6∈ C and any set
X ⊆ [N ] × {φ} of size k, S satisfies wcss property for X with respect to C.
Lemma 3. For each natural N , and k, l ≤ N , there exists a (N, k, l)-wcss of size O((k +l)lk 2 log N ).
Proof. We use the probabilistic method [1]. Let S = (S1 , ..., Sm ), when the length m of the sequence
will be specified later, be a sequence of sets build in the following way. The set Si is chosen independently at random as follows. First, the set Ci of “allowed” clusters is determined by adding each
cluster ID from [N ] to Ci with probability 1/l. Then, the set Si is determined by adding independently (x, φ) to Si for each x ∈ [N ] and φ ∈ Ci to the set Si , with probability 1/k. Let T be the set
of tuples (X, C, φ, x, y) such that X, C ⊂ [N ], |X| = k, |C| = l, φ, x, y ∈ [N ], φ 6∈ C, x ∈ X, y 6∈ X.
The size of T is
  
N
N
|T | =
(N − l)k(N − k) < N k+l+3 .
k
l
For a fixed tuple (X, C, φ, x, y) ∈ T , let E i be the conjunction of three independent events:
• E i,0 : φ ∈ Ci and C ∩ Ci = ∅.
• E i,1 : (X × {φ}) ∩ Si = {(x, φ)},
• E i,2 : (y, φ) ∈ Si ,
Then, E i occurs with probability
1
p = Prob(E i ) = Prob(E i,0 ) · Prob(E i,1 ) · Prob(E i,2 ) =
l



1
1−
l

l

1
·
k



1
1−
k

k−1

1
· =Ω
k



1
lk 2


.

The sequence S1 , S2 , . . . , Sm is a (N, k)-wcss when the event E i occurs for each element of T for
some index i ∈ [m]. The probability that, for all indices i ∈ [m], E i does not occur for the tuple
(φ, X, C, x, y) is equal to
(1 − Prob(Ei ))m = (1 − p)m ≤ e−mp .
Thus, by the union bound, the probability that there exists a tuple (X, C, φ, x, y) for which Ei does
not occur for all i is smaller or equal to
|T |(1 − p)m ≤ N k+l+3 e−mp = eO((k+l) log N )−mp .
By choosing m = Θ((k + l)lk 2 log N ) large enough, the above expression gets strictly smaller than 1
and therefore the probability of obtaining (N, k, l)-wcss is positive. Hence, by using the probabilistic
method, such an object exists.
10

3.2

Basic communication under SINR interference model

Using introduced selectors, we provide some basic communication primitives on which we build our
sparsification and clustering algorithms. As the proofs of stated properties are fairly standard, we
present them in Appendix.
Firstly, consider networks with constant density. Below, we state that a fast efficient communication is possible in such a case.
Lemma 4. (Sparse Network Lemma) Let γ ∈ N be a fixed constant and ε ∈ (0, 1) be the parameter
defining the communication graph. There exists a schedule Lγ of length O(log N ) such that each
node u transmits a message which can be received (at each point) in distance ≤ 1 − ε from u in an
execution of Lγ , provided there are at most γ nodes in each unit ball.
The schedule Lγ defined in Lemma 4 will be informally called Sparse Network Schedule or shortly
SNS. The following lemmas imply that, for a successful transmission of a message on a link connecting
a close pair, it is sufficient that some set of constant size of close neighbors is not transmitting at
the same time (provided a round is free of some set of conflicting clusters of constant size). This fact
will allow to apply wss (and wcss) for efficient communication in the SINR model.
Lemma 5. There exists a constant κ (which depends merely on the SINR parameters and ε) which
satisfies the following property. Let u, v be a close pair of nodes in an unclustered set A. Then,
there exists a set A0 ⊆ A such that u, v ∈ A0 , |A0 | ≤ κ and v receives a message transmitted from u
provided u is sending a message and no other element from A0 is sending a message.
Lemma 6. Let A be an r-clustered set for a fixed r = O(1). Then, there exists constants κ, ρ
(depending only on r, ε and SINR parameters) satisfying the following condition. For each cluster φ
and each close pair of nodes u, v from φ, there exists A0 ⊆ A of size ≤ κ and a set of clusters C of
size ≤ ρ such that u receives a message transmitted by v in a round satisfying the conditions:
• no node from A0 (except of v) transmits a message in the round,
• the round is free of clusters from C.

3.3

Proximity graphs

The idea behind sparsification algorithm extensively applied in our solutions is to repeat several
times the following procedure: identify a graph including as edges all close pairs and “sparsify this”
graph (switch off some nodes) appropriately. To this aim, we introduce the notion of proximity graph.
For a given (clustered) set of nodes X, a proximity graph H(X) of X is any graph on this set such
that:
(i) vertices of each close pair u, v are connected by an edge,
(ii) the degree of each node of the graph is bounded by a fixed constant,
(iii) cluster(u) = cluster(v) for each edge (u, v) of H(X).
Using well-known strongly selective families (ssf) and Lemma 5, one can build a schedule S of length
O(log N ) such that each close pair of an unclustered network exchange messages during an execution
of S. However, this property is not sufficient for fast construction of a proximity graph, since nodes
may also receive messages from distant neighbors during an execution of S which migh result in
large degrees. Moreover, each node v knows only received messages after an execution of S, but
it is not aware of the fact which of its messages were received by other nodes. Finally, a direct
11

application of ssf for clustered network/set requires additional increase of time complexity. In order
to build proximity graphs efficiently, we use the algorithm ProximityGraphConstruction (Alg. 1).
This algorithm relies on properties of witnessed (cluster aware) strong selectors.
Our construction (Alg. 1) builds on the following observations. Firstly, if u can hear v in a round
in which w is transmitting as well, then u, w is for sure not a close pair (otherwise, w generates
interferences which prevents reception of the message from v by u). Secondly, given a close pair
(u, v), u can hear v in a round in which v transmits, provided:
• unclustered case: none of the other κ closest to u nodes transmits (see Lemma 5),
• clustered case: none of the other κ closest to u nodes from cluster(u) transmits, and no node
from ρ “conflicting” clusters transmit (see Lemma 6),
where κ, ρ are the constants from Lemma 5 and Lemma 6.
Given an (N, κ)-wss/(N, κ, ρ)-wcss S for constants κ, ρ from Lemmas 5 and 6, one can build
a proximity graph in O(log N ) rounds using the following distributed algorithm at a node v (see
pseudocode in Alg. 1 and an illustration on Fig. 2):
• Exchange Phase: Execute S.
• Filtering Phase:
– Determine the set Cv of all nodes u such that v has received a message from u during S
and v has not received any other message in rounds in which u is transmitting (according
to S). Remark: ignore messages from other clusters in the clustered case.
– If |Cv | > κ, then remove all elements from Cv .
• Confirmation Phase
– Send information about the content of Cv to other nodes in consecutive |Cv | repetitions
of S.
– Choose Ev = {w ∈ Cv | v ∈ Cw } as the set of neighbours of v in the final graph. (That is,
v exchange messages with its neighbours during an execution S.)
Algorithm 1 ProximityGraphConstruction(v)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

Ev ← ∅
S ← (N, κ)-wss or (N, κ, ρ)-wcss, common to all nodes.
. κ, ρ – constants from L. 5 or 6
Execute S with message containing ID of v and cluster(v).
. Exchange Phase.
Let Uv be the set nodes which successfully delivered a message to v during Exchange Phase.
C v ← Uv
. Filtering Phase.
for each u, w ∈ Uv do
if in some round u and w transmitted and v heard u then
. lookup in the schedule S
Cv ← Cv \ {w}
if |Cv | > κ then
Cv ← ∅
for each u ∈ Cv do
. Confirmation Phase
Execute S with hv, ui as the message.
for each message hw, vi received during the confirmation phase do
if w ∈ Cv then
Ev ← Ev ∪ {w}

12

Lemma 7. (Close Neighbors Lemma) ProximityGraphConstruction executed on a (clustered) set X
builds a proximity graph H(X) of constant degree in O(log N ) rounds. Moreover, ProximityGraphConstruction builds a schedule S of size O(log N ) such that u and v exchange messages during S for
each edge (u, v) of H(X).
Proof. First, we show that each close pair in X is connected by an edge in H, i.e., u ∈ Ew and
w ∈ Eu after an execution of ProximityGraphConstruction on X.
By Lemma 5 we know that, if u is the only transmitter among κ nodes closest to w (including
w), then w receives the message. By the fact that the schedule S is a (N, κ, ρ)-wcss, we know that
there is a round satisfying this condition during an execution of S. More precisely, we choose κ and
ρ from Lemma 6. Thus, u ∈ Uw and w ∈ Uu after Exchange phase (see Fig. 2(a)).
Since u, w is a close pair, it is impossible that u receives a message from x 6= w in a round in
which w transmits a message (since β > 1 and d(u, x) > d(u, w)). Thus, w (u, resp.) belongs to Cu
(Cw , resp.) after Filtering Phase.
A node can also purge the candidate set Cv during Filtering Phase, if the set of candidates
contains more than κ nodes. However, as S is (N, κ, ρ)-wcss, if u, w ∈ X is a close pair then the
sizes of Cu and Cw ar at most κ. Indeed, let U denote the set of κ nodes closest to u (including u).
Then, for any node ufar 6∈ U which is not among κ closest nodes to u, there is a round in S in which
w transmits uniquely in U and also ufar 6∈ U transmits by the witnessed strong selection property of
S. Thus, ufar is eliminated from Cu in Filtering Phase, as well as any other node not in U . So, the
set of candidates Cu for u is a subset of U , thus its size is at most κ (see Fig. 2(b)).
It is clear that the degree of resulting graph is at most κ = O(1). The round complexity of the
procedure is at most (κ + 1)|S| = O(log N ).

w

u

(a) Exchange Phase: edges connect
u with elements of Uu . Some of
them can be “removed” in Filtering Phase.

w

u

(b) Filtering Phase: If u hears
some node w, it can “remove” all
other nodes that transmitted in
that round. The dashed edges denote nodes removed for sure.

w

u

(c) A possible result of the proximity graph construction. Only close
pairs are guaranteed to be connected by an edge.

Figure 2: An illustration of the proximity graph construction (Algorithm 1). The blue circle contains
κ closest nodes to u.

4

Network sparsification and its applications

In this section we describe a sparsification algorithm which decreases density of a network by removing some nodes from dense areas and assigning them to their “parents” which are not removed.
Simultaneously, the algorithm builds a schedule in which removed nodes exchange messages with
their parents. Using sparsification as a tool, we develop other tools for (non)sparsified networks.
13

Finally, a clustering algorithm is given which partitions a network (of awaken nodes) into clusters in
time independent of the diameter of a network.

4.1

Sparsification

A c-sparsification algorithm for a constant c ≤ 1 is a distributed ad hoc algorithm S which, executed
on a set of nodes X of density ∆ ≤ N , determines a set Y ⊆ X such that:
a) density of Y is at most c∆,
b) each v ∈ X knows whether v ∈ Y and each v ∈ X \ Y has assigned parent(v) ∈ Y such that v
and parent(v) exchange messages during an execution of S on X.
Moreover, if X is a clustered set, cluster(v)=cluster(parent(v)) for each v ∈ X \ Y .
Alg. 2 contains a pseudocode of our sparsification algorithm. The algorithm builds a proximity
graph of a network several times. Each time a proximity graph H is determined, an independent set
Y of H is computed such that:
• for each dense cluster φ, at least one element of φ is in Y (clustered case) or
• for each dense unit-ball B, there is an element in Y located close to the center of B (unclustered
case).
Then, some elements of Y are linked with their neighbours in Y by parent/child relation and removed
from the set of nodes attending consecutive executions of ProximityGraphConstruction.

(a) Clustered case. Child-parent relations is possible only between nodes of the same cluster.

(b) Unclustered case. An example demonstrates
that the number of nodes in a dense unit ball (in
gray) is not necessarily reduced, due to the fact
that all nodes from the ball become parents of
nodes outside of the ball.

Figure 3: An example of sparsification of a network. Each edge corresponds to child-parent relation
(the direction of an edge is from a child to its parent). The elements of the returned set of nodes are
denoted by dots, the remaining nodes are denoted by squares.
In this way, the density of the set of nodes attending the algorithm gradually decreases. Details
of implementation of the algorithm, including differences between clustered and unclustered variant,
and analysis of its efficiency are presented below (see also Fig. 3).
For a clustered network, IndependentSet(G) is chosen as the set of local minima in a proximity
graph, that is, Y ← {v | ID(v) < min({ID(u) | u ∈ NvH })}.
Lemma 8. Alg. 2 is a 34 -sparsificaton algorithm for clustered networks, it works in time O(Γ log N ).

14

Algorithm 2 Sparsification(Γ, X)
1: For each v ∈ X: parent(v) = ⊥, children(v) = ∅
2: Active ← X, Prnts ← ∅, GlobChl ← ∅
3: for i = 1, 2, . . . , Γ do
4:
H ← ProximityGraphConstruction(Active)
5:
Y ← IndependentSet(H)
. Implementions different for clustered/unclustered X
6:
NewChl ← {v ∈ Active | v ∈
6 Y and NvH ∩ Y 6= ∅}
. NvH denotes the set of neighbors of v in H
7:
for each v ∈ NewChl do
8:
parent(v) ← min(NvH ∩ Y )
9:
children(parent(v)) ← children(parent(v)) ∪ {v}

Prnts ← Prnts ∪ {v ∈ Active | children(v) 6= ∅}
GlobChl ← GlobChl ∪ NewChl
Active ← Active \ (Prnts ∪ GlobChl)
13: return Active ∪ Prnts
10:
11:
12:

Proof. First, let us discuss an implementation of the algorithm in a distributed ad hoc network. A
proximity graph H is built by Alg. 1 in O(log N ) rounds. Moreover, after an execution of Alg. 1, all
nodes know their transmission patterns in the schedule S of length O(log N ) such that each pair of
neighbors u, v in G exchange messages during S. Therefore, each node v knows its neighbors NvH in
H as well. In order to execute the remaining steps in the for-loop, nodes determine locally whether
they belong to NewChl. Then elements of NewChl choose their parents and send messages to them
using the schedule S. Simultaneously, each node updates the local children(v) variable if it receives
messages from its new child(ren). (Note that a directed graph connecting children with their parents
is acyclic.
Lemma 7 implies that the graph H built by ProximityGraphConstruction connects by an edge
each close pair. Thus, by Lemma 1.2, H contains at least one edge connecting elements of φ, for
each dense cluster φ. Thus, Y contains at least one element of φ and, since edges connect only nodes
of the same cluster, at least one element of φ determines its parent inside φ. As the result, at least
two elements of φ are removed from Active in each execution of ProximityGraphConstruction.
These properties guarantee that each repetition of the main for-loop decreases the number of
elements of Active in each dense cluster. Therefore, each cluster contains at most Γ/2 elements of
Active after O(Γ) repetitions of the loop.
Let Active0 , Prnts0 , GlobChl0 be the intersections of Active, Prnts and GlobChl with a cluster
φ. Above, we have shown that |Active0 | ≤ Γ/2, while the algorithm returns Active0 ∪ Prnts0 . Thus,
in order to prove the lemma, it is sufficient to show that |Prnts0 | ≤ Γ/4. For each cluster φ, each
element of Prnts0 from this cluster has assigned nonempty subset of the cluster as children of v and
the sets of children of nodes are disjoint. Thus, the number of elements of Prnts0 in the cluster is at
most as large as the number of elements of GlobChl0 in that cluster: |Prnts0 | ≤ |GlobChl0 |. Summing
up, |Active0 ∪ Prnts0 ∪ GlobChl0 | ≤ Γ, |Active0 | ≤ Γ/2, |Prnts0 | ≤ |GlobChl0 |. As Active0 , Prnts0 , and
GlobChl0 are disjoint, the finally returned set Active0 ∪ Prnts0 contains at most 34 Γ elements from the
considered cluster φ.
For unclustered networks IndependentSet(G) is determined by a simulation of the distributed
Maximal Independent Set (MIS) algorithm for the LOCAL model [34] which, for graphs of constant
degree, works in time O(log∗ n) and sends O(log n)-size messages. As ProximityGraphConstruction
builds an O(log N ) time schedule in which each pair of neighbors u, v (of a built proximity graph)
exchange messages, we can simulate each step of the algorithm from [34] in O(log N ) rounds. In contrast to the clustered networks, we are unable to guarantee that a single execution of Sparsification
reduces the density in an unclustered network. This is due to the fact that a node from dense unit

15

ball might become a parent of a node outside of this ball (see Fig. 3(b)); as a result the number of elements in the considered unit ball is not reduced during an execution of Sparsification. Therefore, we
have to deal with unclustered case more carefully. Let l ← χ(5, 1 − ε) and let SparsificationU(Γ, X)
be an algorithm which executes Sparsification(Γ, Xi ) for i = 0, . . . , l − 1, where X0 = X, Xi is the
set returned by Sparsification(Γ, Xi−1 ) and Xl is the set returned as the final result.
Algorithm 3 SparsificationU(Γ, X)
1: X0 ← X
2: l ← χ(5, 1 − ε)
3: for i = 0, . . . , l − 1 do
4:
Xi+1 ← Sparsification(Γ, Xi )
5:
Si : the schedule of Sparsification(Γ, Xi )
6: return (X1 , . . . , Xl ), (S0 , . . . , Sl−1 )

Lemma 9. An execution of SparsificationU(Γ, U ) on an unclustered set U of density Γ returns a
sequence of set X0 ⊇ X1 ⊇ · · · ⊇ Xl and schedules S0 , . . . , Sl−1 such that the density of Xl is at
most 43 Γ, each node x ∈ Xi \ Xi+1 exchange messages with parent(x) ∈ Xi+1 during Si . Morover,
SparsificationU(Γ, U ) works in time O(Γ log N log∗ N ).
Proof. The analysis of the sparsification algorithm for clustered networks relies on the fact that there
is a close pair in each dense cluster φ and therefore the number of active elements in φ is reduced
after each iteration of the for-loop in Alg. 2. In the unclustered network, it might be the case that
there is no close pair in a dense unit-ball. That is why the reasoning from Lemma 8 does not apply
here.
We define an auxiliary notion of saturation. For a unit ball B = B(x, 1), the saturation of B with
respect to the set of nodes X is the number of elements of X in B(x, 5). As long as B contains at
least Γ/2 nodes in an execution of ProximityGraphConstruction, there is a close pair u, v in B(x, 5)
(Lemma 1) and therefore u, v are connected by an edge in H. Thus, u or v is not in the computed
MIS (line 5); wlog assume that u is not in MIS. Thus, u is dominated by a node from MIS and
therefore it becomes a member of GlobChl and it is switched off. This in turn decreases saturation of
B(x, 5). Thus, an execution of Sparsification results either in decreasing the number of nodes in B to
≤ Γ/2 or in reducing saturation of B by at least Γ. As B(x, 5) might be covered by l = χ(5, 1) unit
balls, there are at most lΓ nodes in B(x, 5) and saturation can be reduced at most lΓ times. Hence,
l repetitions of Sparsification eventually leads to the reduction of the number of active elements
located in B to ≤ Γ/2.

4.2

Full Sparsification

A full sparsification algorithm is a distributed ad hoc algorithm/schedule S = S1 S2 . . . Sk which,
executed on an r-clustered set of nodes A of density Γ determines sets A0 , A1 , . . . , Ak such that
k = log4/3 Γ, Ai+1 ⊆ Ai (each node v ∈ A knows whether v ∈ Ai ), A0 = A and, for each i ∈ [k]:
a) the density of Ai is at most max{Γ(3/4)i , χ(r, 1 − ε)},
b) each v ∈ Ai \ Ai+1 has assigned parent(v) ∈ Ai+1 such that v and parent(v) exchange messages
during Si and cluster(v)=cluster(parent(v)).
Alg. 4 contains a pseudocode of our full sparsification algorithm (see also Fig. 4). In Lemma 10,
the properties of this algorithm (following directly from Lemma 8) are summarized.

16

Algorithm 4 FullSparsification(Γ, A)
1: A0 ← A,
2: X ← A, Λ ← Γ, k ← log 3 Γ
4
3: for i = 1, 2, . . . , k do
4:
Y ← Sparsification(Λ, X)
5:
Si ← the schedule of Sparsification(Λ, X)
6:
Ai ← X \ Y
7:
X←Y
8:
Λ ← 34 Λ
9: return (A0 , . . . , Ak ), (S1 , . . . , Sk )

(a) The clustered set A, where colors correspond
to clusters.

(b) The result of the first execution of Sparsification. Nodes from A1 are denoted by squares.

(c) The set on which Sparsification is executed for
the second time (dots from Figure (b)).

(d) The result of the second execution of Sparsification. Nodes from A2 are denoted by squares.

Figure 4: An illustration of full sparsification. Each edge correspond to child-parent relation (the
direction of an edge is from a child to its parent).

Lemma 10. Algorithm 4 is a full sparsificaton algorithm for clustered networks which works in time
O(Γ log N ).

4.3

Imperfect labelings of clusters

Using r-clustering of a set X with density Γ, it is possible to build efficiently an imperfect c-labeling
of X, where c is a constant which depends merely on r and SINR parameters.
Lemma 11. Assume that an r-clustering of a set X of density Γ is given. Then, it is possible to build
c-imperfect labeling of X in O(Γ log N ) rounds, where c depends merely on r and SINR parameters.
Proof. Let S = S1 , . . . , Sk and A1 , . . . , Ak be the schedules and the sets obtained as the result of
an execution of FullSparsification(Γ, X). FullSparsification(Γ, X) splits each cluster in O(1) trees,
defined by the child-parent relation build during an execution of FullSparsification. (Indeed, the
17

elements of Ak are the roots of the trees.) The schedule S (and its reverse S R ) of length O(Γ log N )
allows for bottom-up (top-down) communication inside these trees. Using S and S R one can implement tree-labeling algorithm as follows. First, each node learns the size of its subtree in a bottom-up
communication. Then, the root starts top-down phase, where each node assigns the smallest label
in a given range to itself and assigns appropriate subranges to its children. More precisely, the root
starts from the range [1, m], where m is the size of the tree. Given the interval [a, b], each node
assigns a as its own ID and splits [a + 1, b] into its subtrees.

4.4

Reduction of radius of clusters

In this section we show how to reduce the radius of a clustering. Given an r-clustering of a set X
of density Γ, our goal is to build an 1-clustering of X. The idea is to repeat the following steps
several times. First, X is fully sparsified, i.e., O(1) nodes remain from each non-empty cluster.
Then, a minimum independent set (MIS) of this sparse set is determined on the graph with edges
(u, v) connecting u, v which exchange messages during an execution of Sparse Network Schedule (see
Lemma 4). The elements of MIS become the centers of new clusters in the new 1-clustering and they
execute Sparse Network Schedule. A node v (not in MIS) which receives a message from w during
this execution of SNS, becomes an element of cluster(w) and it is removed from further consideration.
As we show below, a 1-clustering of X can be obtained in this way efficiently by Alg. 5.
Algorithm 5 RadiusReduction(Γ, X, r)
1: For each v ∈ X: newcluster(v) ← ⊥
. ⊥ means “undetermined”
2: for i = 1, 2, . . . , χ(r + 1, 1 − ε) do
3:
(X0 , . . . , Xk ), (S0 , . . . , Sk ) ← FullSparsification(Γ, X)
4:
Execute Sparse Network Schedule Lγ from Lemma 4 on Xk
5:
Let G(Y, E), where E = {(u, v) | u, v exchange messages during Lγ } and Y = {v | ∃u (u, v) ∈ E}
6:
D ← MIS(G)
. simulation of maximal independent set alg. from [34]
7:
Execute Sparse Network Schedule Lγ from Lemma 4 on D
. Local Broadcast from D, using L. 4
8:
for each v ∈ X \ D do
9:
if v received a message from u ∈ D during execution of Lγ in line 7 then
10:
newcluster(v) ← u
. Choose arbitrary u if v received many messages
11:

X ← X \ (D ∪ {v | newcluster(v) 6= ⊥})

Lemma 12. Assume that a r-clustering of a set X of density Γ is given for a fixed constant r ≥ 1.
Then, Algorithm 5 builds 1-clustering of X in O((Γ + log∗ N ) log N ) rounds.
Proof. By Lemma 8, the set Xk has density c0 = O(1) and it contains at least one element from each
nonempty cluster of X. Each pair of nodes from Xk in distance ≤ 1 − ε exchange messages during
step 4, therefore the graph G contains the communication graph of Xk . As D computed in step 6
is a MIS of Xk in the graph G and Xk contains at least one element from each nonempty cluster,
there is an element of D in close neighborhood of each cluster. More precisely, for a dense cluster
φ with nodes located inside B(x, r), there is an element of the computed maximal independent set
(MIS) in B(x, r + 1). Indeed, by Lemma 10, there is y from φ in Y . Thus, y ∈ B(x, r), where x is
the center of the cluster φ. Either y is in the computed MIS or y is in distance ≤ 1 from an element
z from the MIS. In the latter case, z ∈ B(x, r + 1). Then, steps 7–10 assign all nodes in distance
≤ 1 − ε (and some in distance ≤ 1) from elements of D (including the above defined y or z) to new
clusters included in unit balls with centers at the elements of D. Thus, the nodes from each “old”
cluster are assigned to new clusters after χ(r + 1, 1 − ε) repetitions of the main for-loop.

18

4.5

Clustering algorithm

In this section we provide an algorithm which, given an unclustered set A, builds a 1-clustering of A.
The algorithm consists of two main parts. In the former part, the sequence of sets A0 ⊇ · · · ⊇ Akl
is built using SparsificationU, for k = log4/3 Γ and l = χ(5, 1 − ε). By Lemma 9, the density of Ail
is at most Γ( 43 )i . Moreover, a sequence of schedules S0 , . . . , Skl is built such that each v ∈ Ai \ Ai+1
exchange messages with parent(v) ∈ Ai+1 . In the latter part, we start from 1-clustering of Akl ,
which is obtained by assigning each node v ∈ Akl to a separate cluster. Then, given an 1-clustering
of Ai for i > 0, we get 2-clustering of Ai−1 by executing Si−1 with messages equal to cluster IDs of
transmitting nodes. The elements of Ai−1 choose clusters of their parents. Using RadiusReduction
(Lemma 12), the obtained 2-clustering is transformed into an 1-clustering. A pseudocode is presented
in Alg. 6.
Algorithm 6 Clustering(Γ, A)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

k ← log4/3 Γ
X ← A, A0 ← A
Λ ← Γ, k ← log 34 Γ, l ← χ(5, 1 − ε)
for i = 1, 2, . . . , k do
(A(i−1)l+1 , . . . , Ail ), (S(i−1)l+1 , . . . , Sil ) ← SparsificationU(Λ, X)
X ← Ail
Λ ← 43 Λ
For each v ∈ Akl : cluster(v) ← ID(v)
X ← Akl
Λ←1
for i = 0, 1, 2, . . . , kl do
Execute Skl−i , on Akl−i , each v ∈ Akl−i sends cluster(v) during the execution
For each v ∈ Akl−i−1 : cluster(v) ← cluster(parent(v))
X ← X ∪ Akl−i−1
RadiusReduction(Λ, X, 2)
if i mod l = 0 then Λ ← 34 · Λ

Theorem 1. The algorithm Clustering builds 1-clustering of an unclustered set A of density Γ in
time O(Γ log N log? N ).
Proof. Correctness of the algorithm follows from the properties of SparsificationU and RadiusReduction (Lemmas 9 and 12). The time of executions of SparsificationU is
 i
k
X
3
log N log∗ N ) = O(Γ log N log∗ N ).
O(
Γ
4
i=1

The time of executions of RadiusReduction is
 i
k
X
3
O( (Γ
+ log∗ N ) · log N ) = O(Γ log N + log∗ N log N ).
4
i=1

Altogether, time complexity is O(Γ log N log? N ).

5

Communication problems

In this section, we apply sparsification and clustering in distributed algorithms for broadly studied
communication problems, especially the local and global broadcast.
19

5.1

Local broadcast

Now, we can solve the local broadcast problem for a set V of density ∆ by the following LocalBroadcast algorithm.
Algorithm 7 LocalBroadcast(V, ∆)
1: Clustering(∆, V )
2: Imperfect labeling of V
3: for l = 1, . . . , ∆ do
4:
Run SNS on nodes with label equal to l

. Theorem 1
. Lemma 11
. Lemma 4

First, the clustering algorithm is applied which builds a 1-clustering of V in time O(∆ log N log? N )
(Theorem 1). Then, an imperfect labeling of clusters can be formed in time O(∆ log N ) (Lemma 11).
Finally, an algorithm which executes ∆ times Sparse Network Schedule (see Lemma 4), the lth execution of SNS is performed by the nodes with label l. As each label appears O(1) times in each
cluster, the density of the set of nodes with label l (for each l) is O(1) for each l ∈ [N ]. Thus,
consecutive executions of SNS accomplish the local broadcast task (see Lemma 4).
Theorem 2. The algorithm LocalBroadcast performs local broadcast from a set V of density ∆ in
time O(∆ log N log? N ).

5.2

Sparse multiple-source broadcast

In this section we consider sparse multiple source broadcast (SMSB) problem, a generalization of
the global broadcast problem. This generalization is introduced for further applications for other
communication problems as leader election and wake-up.
The sparse multiple source broadcast problem (SMSB problem) is defined as follows. At the
beginning, the unique broadcast message is known to a set of distinguished nodes S ⊂ V such that
d(u, v) > 1 − ε for each u, v ∈ S, u 6= v. The problem is solved when
(a) the broadcast message is delivered to all nodes of the network, AND
(b) each node v ∈ V transmitted a message in some round which was received by all its neighbors
in the communication graph.
The algorithm for SMSB problem. Let Vi denote the set of nodes in the graph-distance i from S,
i.e., v ∈ Vi if a shortest path from an element of S to v has length i. The algorithm works in phases.
In Phase 1, Sparse Networks Schedule (Lemma 4) is applied on the set of distinguished nodes S. In
this way all elements of S transmit messages received by V1 , their neighbors in the communication
graph (and possibly some other nodes in geometric distance at most 1). After receiving the first
message from s ∈ S, a node v ∈ V \ S assigns itself to the cluster s. Hence, the set of awaken nodes
L1 contains V1 and we have 1-clustering of L1 .
In Phase i > 1, local broadcast is executed on Li , the set of nodes awaken5 in Phase i − 1 . In
this way,
S the setSof nodes awaken in the first i phases contains all nodes in graph distance i from S,
i.e., j∈[i] Vj ⊆ j∈[i] Lj . Moreover, we assure that all nodes awaken in a phase are 1-clustered at
the end of the phase. (Thus, each node knows its cluster ID in such clustering).
A phase consists of three stages. In Stage 1 of phase i, an imperfect labeling of each cluster of Li
is built. This means that each node v is assigned a label lv such that, for each cluster, the number
of nodes with the same label in the cluster is O(1)(see Lemma 11). In Stage 2, Sparse Network
5

A node is awaken in the phase j if it receives the broadcast message for the first time in that phase.

20

Schedule (Lemma 4) is executed ∆ times. A node with label l participates in the lth execution of
SNS only. In this way, all nodes from Li transmit on distance 1 − ε. All nodes awaken in Stage 2
inherit cluster numbers from nodes which awaken them. In this way, we obtain a 2-clustering of
Li+1 , the set of nodes awaken in Stage 2. The goal of Stage 3 is (given the obtained 2-clustering) to
build an 1-clustering of awaken nodes. (See Fig. 1 in Section 1 for an example.)
Algorithm 8 SMSBroadcast(V, S)
1: SNS(S)
2: L1 ← nodes awaken by elements of S, clustered by IDs of their neighbors from S
3: for i = 1, 2, . . . do
4:
Stage 1: imperfect labeling of Li
5:
Stage 2: local broadcast from Li , using assigned labels

. Lemma 11
. Lemma 4
. Awaken nodes form Li+1 and inherit cluster IDs from nodes which awaken them.
Stage 3: RadiusReduction(∆, Li+1 , 2) using 2-clustering given by inherited cluster numbers
. Lemma 12.

6:

Using Lemmas 11, 4 and 12, we obtain the following result.
Theorem 3. Algorithm SMSBroadcast solves sparse multiple source broadcast problem in O(D(∆ +
log∗ N ) log N ) rounds. For S of size 1, the algorithm solves the global broadcast problem.

5.3

Other problems

By applying the clustering algorithm and SMSBroadcast, solutions for other widely studied problems
can be obtained, e.g., leader election or wake-up.
Wake-up problem In the wake-up problem [23], some nodes become spontaneously active at various rounds and the goal is to activate the whole network. Nodes which do not become active
spontaneously can be activated by a message successfully delivered to them. Spontaneous wake-ups
are controlled by an adversary, thus an algorithm solving the problem should work for each pattern
of spontaneous activations. A node can not participate in an execution of an algorithm as long as
it is not active. Time of an execution of a wake-up algorithm is the number of rounds between the
spontaneous activation of the first node and the moment when all nodes are activated. We assume
the model with global clock, i.e., there is a central counter of rounds and each node knows the current
value of that counter.
For a while, assume that all spontaneous wake-ups appear at the same round r. Then, starting at
round r, we call Clustering (Alg. 6) on the set of spontaneously awaken nodes S (see Lemma 9). As
a result, we get a nonempty set S 0 ⊂ S of constant density in O(∆ log N log∗ N ) rounds. Then,
SMSBroadcast(V, S 0 ) activates all nodes on a network in O(D(∆ + log∗ N ) log N ) rounds. Let
T (N, ∆) = O(D(∆ + log∗ N ) log N ) be the exact number of rounds of this algorithm. In order
to adjust the above algorithm to arbitrary times of spontaneous wake-ups, we start a separate execution of this algorithm at each round r whose number is divisible by T (N, ∆). In an execution
starting at round r, only nodes awaken before r are considered to be activated spontaneously. Thus,
we have the following result.
Theorem 4. The wake-up problem in networks with global clock can be solved in O(D(∆+log∗ N ) log N )
rounds.
Leader election The leader election problem is to choose (exactly) one node in the whole network
as the leader, assuming that nodes are awaken in various rounds. First, assume that all nodes
start a leader election algorithm at the same round. In order to elect the leader, we first execute
Clustering (Alg. 6) on all nodes of a network which takes O(∆ log∗ N log N ) rounds and determines
21

the non-empty set S of constant density. Then, a unique member of S is chosen as the leader, in
the following (standard) way. Observe that one can verify whether S contains nodes with IDs in the
range [l, r] by executing SMSBroadcast(V, S 0 ), where S 0 are nodes from S with IDs in [l, r]. Thus,
it is possible to choose the leader from S by binary search which starts from the range [1, N ] and
requires O(log N ) executions of SMSBroadcast. In order to adjust the above algorithm to arbitrary
times of spontaneous wake-ups of nodes, we start a separate execution of the algorithm at each round
r whose number is divisible by T (N, ∆), where T (N, ∆) = O(D(∆ + log∗ N ) log2 N ) is the upper
bound on the time of the algorithm. In an execution starting at round r, only nodes awaken before
r are considered to be activated spontaneously. Finally, we have the following result.
Theorem 5. The leader election problem in networks with global clock can be solved in O(D(∆ +
log∗ N ) log2 N ) rounds.

6

Lower Bound

In this section we prove a lower bound on the number of rounds needed to perform global broadcast.
Theorem 6. A deterministic algorithm for the global broadcast in the SINR network works in time
Ω(D∆1−1/α + ∆), provided N = Ω(D∆) and the connectivity parameter ε > 0 is small enough.
In order to prove the above theorem, we build a family of networks called gadgets. Each network
from the family consists of ∆ + 4 nodes s, v0 , . . . , v∆+1 , t located on the line – see Fig. 5 (in Section 6)
for locations and distances between nodes. Thus, in particular, s is connected by an edge in the
communication graph with v0 , . . . , v∆+1 , t is connected merely with v∆+1 and only messages from
v∆+1 can be received by t. One can show that, for each deterministic algorithm, one can assign IDs
to the nodes s, v0 , . . . , v∆+1 such that the broadcast message originating at s will be delivered to t
after Ω(∆) rounds. For the purpose of the lower bound, the main property of the locations of nodes
in the gadget are:
(a) The node vi does not receive any message, provided at least two nodes from the set {vj | j < i}
transmit at the same time.
(b) The node t can receive a message from v∆+1 (v∆+1 is the only node from the gadget in distance
≤ 1 from t) only in the case that no other node from the gadget transmits at the same time.
Using (a), we assign IDs to consecutive nodes v1 , v2 , . . . such that, after i rounds, the nodes vk for
k > 2i do not have any information about their location inside the set {vl | l > 2i}. Thus, the only
available information differentiating them are their IDs. As a result, we prevent a transmission of
v∆+1 in a round in which other nodes from the gadget do not transmit for Ω(∆) rounds.
A natural idea to generalize such a result to Ω(D∆) is to connect sequentially consecutive gadgets
such that the target (t) of the ith gadget is identified with the source s of the (i + 1)st gadget.
Such approach usually works in the radio networks model, where no distant interferences appear.
However, under the SINR constraints, the interference from distant nodes might potentially help,
since it differentiate history of communication for nodes in various locations (even the close ones).
Therefore, the applicability of this idea under the SINR constraints is limited. Instead of identifying
the target t of the ith gadget with the source of the (i+1)st gadget s, we separate each two consecutive
gadgets by a long “sparse” path of nodes such that consecutive nodes are in distance 1 − ε (Fig. 7).
In this way, we limit the impact of nodes located outside of a gadget on communication inside the
gadget. Finally, our result is only Ω(D∆1−1/α ). Below, we give a full formal proof following the
above ideas.

22

6.1

Proof of Theorem 6

First, we build a gadget (sub)network consisting of ∆ + 4 nodes s, v0 , . . . , v∆+1 , t located on the line
– see Figure 5 and Figure 6 for locations of nodes of a gadget. The notion gadget denotes actually
a family of (sub)networks with location of nodes described on Figure 5 and Figure 6 and aribtrary
IDs in the range [N ]. Observe that the diameter D of the gadget network is equal to 2 (indeed, s
is connected to v0 , . . . , v∆+1 , (vi , vj ) is and edge for each i 6= j and t is connected with v∆+1 ). In
Lemma 13 we show that any deterministic algorithm needs Ω(∆) rounds to deliver a message to t (the
target), which originally is known only to s (the source). More precisely, we show that there exists
an assignment of IDs for the nodes of the gadget such that delivery of a message from s to t takes
Ω(∆) rounds. As our ultimate goal is to analyse networks which contain gadgets as subnetworks, we
make an additional assumption that a limited interference from outside of the gadget might appear.

v0

s

v∆+1

t
1−ε

ε
the core of the gadget

Figure 5: The gadget. The nodes s and t are called the source and the target of a given gadget.
Importantly, d(x, t) > 1 for each x from the gadget except of v∆+1 .

v0
b

v1
b

ε/2∆

v∆−1
...

v∆+1

v∆
b

b

ε/2

b

2ε

Figure 6: The core of the gadget, d(vi , vi+1 ) = ε/2∆−i for i < ∆. Observe, that 2ε < d(v0 , v∆+1 ) < 3ε.

Lemma 13. For any deterministic algorithm A there exists a choice of identifiers
for the nodes in
P/(4ε)α
the gadget such that the following holds. Let ν be the number satisfying N +ν = β and let I ⊆ [N ]
be a set of allowed IDs such that |I| ≥ ∆ + 4. Assume that the interference coming from the outside
of the core of the gadget G in any node of the core is smaller than ν in every round. Moreover,
assume that s is the only awake node of the gadget at a given starting round. Then, it takes Ω(∆)
rounds until the broadcast message is delivered to t using algorithm A.
Proof. The fact that the sequence of distances d(v0 , v1 ), d(v1 , v2 ), . . . forms a geometric sequence
implies the following property, provided ε > 0 is a small enough constant.
Fact 2.
1. If the nodes vi and vj , for i < j are transmitting in a round then the nodes vj+1 , ..., v∆+1
do not receives a message in that round.
2. If v∆+1 is not the only transmitter from the set {v0 , . . . , v∆+1 } in a round, then t does not
receive a message in that round.
As {v0 , . . . , v∆+1 } are asleep at the beginning, they are all awaken in a round in which s sends
its first message, thanks to the fact that interference from outside of the gadget’s core is bounded by
ν. In order to simplify notations, assume that the number of the round in which v0 , . . . , v∆+1 receive
the first message from s is equal to 0. Recall that v∆+1 is the only node from the gadget that can
pass a message to the target t (c.f. Figure 5 and Figure 6). Our goal is to gradually assign IDs to
v0 , v1 , v2 , . . . such that, in each round j ∈ [i/2],
23

• either no node from the set {v0 , . . . , v∆+1 } transmits,
• or at least two nodes from {v0 , . . . , vi } transmit.
In this way the assignment of IDs prevents v∆+1 from being the unique transmitter from {v0 , . . . , v∆+1 }
for Ω(∆) rounds. This fact in turn guarantees that t does not receive any message in Ω(∆) rounds.
Now, we describe the process of assigning IDs to v0 , . . . , v∆+1 . Let I0 = I of size ≥ ∆ + 4 be the
set of allowed IDs at the beginning.
Let r0i > 0 be the smallest round number in which the node with ID equal to i transmits, provided
s is the only node from the gadget (possibly) sending messages before. Let r0 be the smallest round
number r > 0 such that {i | r0i = r} 6= ∅. If |{i ∈ I0 | r0i = r0 }| = 1, we assign the IDs j, k to v0 , v1 ,
where j is the only element of {i ∈ I0 | r0i = r0 } and k is an arbitrary element of I0 different from
j. If |{i ∈ I0 | r0i = r0 }| > 1, we assign the IDs j, k to v0 , v1 , where j 6= k are arbitrary elements of
{i ∈ I0 | r0i = r0 }. Then, we set I1 = I0 \ {j, k}. Let u be a node with ID in I1 located on a position of
one of nodes from {v2 , . . . , v∆+1 }. Then: (i) u does not transmit in rounds r ≤ r0 in which less than
two nodes from {v0 , v1 } transmit; (ii) the feedback which u gets from the communication channel
until the round r0 does not depend on the actual location of u (by (i) and Fact 2.1).
Now, inductively, assume that the IDs of v0 , v1 , . . . , v2a−1 , the round number ra ≥ a and Ia ⊂ I
of size ≥ ∆ + 4 − 2a are fixed for a > 0 such that, for each u with ID in Ia located in a position of one
of nodes v2a , . . . , v∆+1 , the following holds: (i) u does not transmit in rounds r ≤ ra in which less
than two nodes from {v0 , . . . , v2a−1 } transmit; (ii) the feedback which u gets from the communication
channel until the round ra does not depend on the actual location of u.
i
Now, we assign IDs to v2a and v2a+1 , set ra+1 > ra , and Ia+1 . Let ra+1
> ra for i ∈ Ia be the
smallest round number larger than ra in which the node with ID equal to i transmits, provided the
above assumption (i) and (ii) are satisfied and the only transmitters in rounds r > ra belong to
i
{s, v0 , . . . , v2a−1 }. Let ra+1 be the smallest round number r > ra such that {i | ra+1
= r} =
6 ∅. If
i
|{i ∈ Ia | ra+1 = ra+1 }| = 1, we assign the IDs j, k to v2a , v2a+1 , where j is the only element of {i ∈
i
i
Ia | ra+1
= ra+1 } and k is an arbitrary element of Ia different from j. If |{i ∈ Ia | ra+1
= ra+1 }| > 1,
i
we assign the IDs j, k to v2a , v2a+1 , where j 6= k are arbitrary elements of {i ∈ Ia | ra+1
= ra+1 }.
Then, we set Ia+1 = Ia \ {j, k}.
As one can see, the choice of IDs for v2a and v2a+1 , the value of ra+1 > ra , and Ia+1 of size
≥ ∆ + 4 − 2(a + 1) guarantee that, for each u with ID in Ia+1 located in a position of one of the nodes
v2a+2 , . . . , v∆+1 , the following holds: (i) u does not transmit in rounds r ≤ ra+1 in which less than
two nodes from {v0 , . . . , v2a+1 } transmit; (ii) the feedback which u gets from the communication
channel until the round ra+1 does not depend on the actual location of u.
By assigning IDs in the above way we assure that v∆+1 is not the unique transmitter in the
gadget core in Ω(∆) rounds after the first message from s, thus a message is delivered to t after
Ω(∆) rounds.
Lemma 13 gives the lower bound Ω(∆) for the global broadcast. In order to extend the lower
bound to take the network diameter into account, we build a network by joining gadgets sequentially.
However, the following problem appears in such approach. It is vital for our argument that, in each
round, either all nodes from the core of a gadget receive a fixed message or none of them receives
any message. If the network consists of more than one gadget, then the interference from other parts
of the network might cause that only a subset of the nodes from the core receive a message. This in
turn might help to break symmetry and resolve contention in the core in o(∆) rounds.
To overcome the presented problem, we place “a buffer zone” between two consecutive gadgets.
The “buffer zone” is a long path of nodes mitigating the interference between two consecutive gadgets
(see Fig. 7). In this way we can bound the maximal interference coming from the outside of the
24

gadget to ν (where ν is the constant from Lemma 13). Given that, we are able to use Lemma 13 in
networks containing many gadgets.
More precisely, we put a path of κ = ∆1/α /(1 − ε) nodes between two consecutive gadgets to
compensate for the interference on a gadget’s core caused by potential transmitters from previous
gadgets (see Figure 7 for exact composition of gadgets).

w1
b

gadget 1
b

w2

b

1−ε

b

1−ε

...

wκ
b
b

1−ε

gadget 2

Figure 7: Network of diameter Θ(D) formed by D/κ gadgets, where κ =

b

...

∆1/α
1−ε .

The choice of the value of κ follows from the fact that each gadget consists of about ∆ nodes,
while we want to limit the interference from neighbouring gadgets to O(1). The interference from
∆ nodes in distance d from the receiver is equal to ∆P/dα . This value is O(1) provided d ≥ ∆1/α .
Since the path separating two gadgets “wastes” about ∆1/α of the diameter, one can see that we
can put as much as ∆D
1/α of such “separators” on a line, each followed by a gadget. This leads to the
D
lower bound Ω( ∆1/α ∆) = Ω(D∆1−1/α ). Theorem 6 follows from Lemma 14, which formalizes the
above described idea.
Lemma 14. Consider a network of diameter D and density Θ(∆) formed by D/κ gadgets of size ∆+4
located on the line such that consecutive gadgets are “separated” by the path of κ nodes w1 , ..., wκ ,
where d(wi , wi+1 ) = 1 − ε (see Fig. 7). For any deterministic global broadcast algorithm A, there
exists a choice of IDs for the nodes in this network such that A works in time Ω(D∆1−1/α ).
Proof. First, we prove an auxiliary fact which gives an opportunity to use Lemma 13 in multi-gadget
networks from Fig. 7.
Fact 3. For any gadget G in the network, the interference caused by the nodes outside of the gadget
is at most ν at any point v0 , v1 , ..., v∆+1 from the core of the gadget.
Proof. All nodes that may interfere are located on the left side of G (i.e., are closer to the source
than G), we split them in two groups. (Note, that we do not consider the node s from the gadget G
as the interferer nor as the core node (c.f. Fig. 5)). The first group T1 consists of a path of κ nodes
that are closest to G, the rest of nodes located to the left of the gadget (i.e., the nodes closer to
the source than the gadget
to the second group T2 . The maximal interference caused by
PG) belong
P
nodes from T1 is at most κi=1 (1−ε)
α iα .
Now, we bound the interference from T2 . First, we estimate the interference from the kth gadget
to the left of G and from the path separating the kth gadget and the (k − 1)st gadget to the left of
G. There are ∆ + ∆1/α ≤ 2∆ nodes in this part of the network, in distance at least k∆1/α from the
2∆P
α
core of the gadget G. This gives the interference smaller than (k∆
1/α )α = 2P/k . Thus, as there are
PD/κ
at most D/κ gadgets, the interference from T2 is at most k=1 2P/k α . The total interference I at
G is at most
D/κ
κ
X
X
P
I≤
+
2P/k α
(1 − ε)α iα
i=1
k=1

which is O(1) with respect to the parameters ε, D and ∆. On the other hand, ν = Ω ε1α . Thus, for
sufficiently small values of ε we have I ≤ ν.
There are D/κ gadgets, each of size ∆ and, by Lemma 13, it takes Ω(∆) to push a message
through each gadget. Thus, we have a lower bound of Ω(D∆/κ) = Ω(D∆1−1/α ).
25

7

Conclusions

We have shown that it is possible to build efficiently a clustering of an ad hoc network without use
of randomization in a very harsh model of wireless SINR networks. Using the clustering algorithm,
we developed a very efficient local broadcast algorithm. On the other hand, by an appropriate lower
bound, we exhibited importance of randomization or availability of coordinates for complexity of the
global broadcast problem. The exact complexity of global broadcast remains open as well as the
impact of other features, e.g., carrier sensing or power control.
We developed a combinatorial structure called witnessed (cluster aware) strong selector along
with several communication primitives, which might be of independent interest.

References
[1] N. Alon and J. H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016.
[2] B. Aronov and M. J. Katz. Batched point location in SINR diagrams via algebraic tools. In
Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto,
Japan, July 6-10, 2015, Proceedings, Part I, pages 65–77, 2015.
[3] R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time-complexity of broadcast in multi-hop
radio networks: An exponential gap between determinism and randomization. J. Comput. Syst.
Sci., 45(1):104–126, 1992.
[4] L. Barenboim and D. Peleg. Nearly optimal local broadcasting in the SINR model with feedback.
In Structural Information and Communication Complexity - 22nd International Colloquium,
SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, pages 164–178, 2015.
[5] B. S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, and W. Rytter. Deterministic broadcasting
in unknown radio networks. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on
Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA., pages 861–870, 2000.
[6] A. E. F. Clementi, A. Monti, and R. Silvestri. Selective families, superimposed codes, and
broadcasting on unknown radio networks. In S. R. Kosaraju, editor, SODA, pages 709–718.
ACM/SIAM, 2001.
[7] A. E. F. Clementi, A. Monti, and R. Silvestri. Distributed broadcast in radio networks of
unknown topology. Theor. Comput. Sci., 302(1-3):337–364, 2003.
[8] A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In Distributed Computing,
24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010.
Proceedings, pages 148–162, 2010.
[9] A. Czumaj and W. Rytter. Broadcasting algorithms in radio networks with unknown topology.
In FOCS, pages 492–501. IEEE Computer Society, 2003.
[10] S. Daum, S. Gilbert, F. Kuhn, and C. C. Newport. Broadcast in the ad hoc SINR model. In
Y. Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem,
Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science,
pages 358–372. Springer, 2013.
[11] G. DeMarco. Distributed broadcast in unknown radio networks. SIAM J. Comput., 39(6):2162–
2175, 2010.
26

[12] Y. Emek, L. Gasieniec, E. Kantor, A. Pelc, D. Peleg, and C. Su. Broadcasting in udg radio
networks with unknown topology. Distributed Computing, 21(5):331–351, 2009.
[13] Y. Emek, E. Kantor, and D. Peleg. On the effect of the deployment setting on broadcasting in
euclidean radio networks. Distributed Computing, 29(6):409–434, 2016.
[14] K. Förster, J. Seidel, and R. Wattenhofer. Deterministic leader election in multi-hop beeping
networks - (extended abstract). In Distributed Computing - 28th International Symposium,
DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, pages 212–226, 2014.
[15] F. Fuchs and D. Wagner. On local broadcasting schedules and CONGEST algorithms in the
SINR model. In Algorithms for Sensor Systems - 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers, pages
170–184, 2013.
[16] O. Goussevskaia, T. Moscibroda, and R. Wattenhofer. Local broadcasting in the physical interference model. In M. Segal and A. Kesselman, editors, DIALM-POMC, pages 35–44. ACM,
2008.
[17] H. Gudmundsdottir, E. I. Ásgeirsson, M. H. L. Bodlaender, J. T. Foley, M. M. Halldórsson,
and Y. Vigfusson. Extending wireless algorithm design to arbitrary environments via metricity.
In 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and
Mobile Systems, MSWiM’14, Montreal, QC, Canada, September 21-26, 2014, pages 275–284,
2014.
[18] M. M. Halldórsson, S. Holzer, and N. A. Lynch. A local broadcast layer for the SINR network
model. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing,
PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 129–138, 2015.
[19] M. M. Halldórsson and P. Mitra. Towards tight bounds for local broadcasting. In F. Kuhn and
C. C. Newport, editors, FOMC, page 2. ACM, 2012.
[20] M. M. Halldórsson and T. Tonoyan. How well can graphs represent wireless interference? In
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC
2015, Portland, OR, USA, June 14-17, 2015, pages 635–644, 2015.
[21] N. Hobbs, Y. Wang, Q.-S. Hua, D. Yu, and F. C. Lau. Deterministic distributed data aggregation
under the sinr model. In Theory and Applications of Models of Computation, pages 385–399.
Springer Berlin Heidelberg, 2012.
[22] T. Jurdzinski and D. R. Kowalski. Distributed backbone structure for algorithms in the sinr
model of wireless networks. In M. K. Aguilera, editor, DISC, volume 7611 of Lecture Notes in
Computer Science, pages 106–120. Springer, 2012.
[23] T. Jurdzinski and D. R. Kowalski. Wake-up problem in multi-hop radio networks. In Encyclopedia of Algorithms, pages 2352–2354. Springer, 2016.
[24] T. Jurdzinski, D. R. Kowalski, M. Rozanski, and G. Stachowiak. Distributed randomized broadcasting in wireless networks under the sinr model. In DISC, pages 373–387, 2013.
[25] T. Jurdzinski, D. R. Kowalski, M. Rozanski, and G. Stachowiak. On the impact of geometry
on ad hoc communication in wireless networks. In M. M. Halldórsson and S. Dolev, editors,
ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18,
2014, pages 357–366. ACM, 2014.
27

[26] T. Jurdzinski, D. R. Kowalski, and G. Stachowiak. Distributed deterministic broadcasting in
uniform-power ad hoc wireless networks. In L. Gasieniec and F. Wolter, editors, FCT, volume
8070 of Lecture Notes in Computer Science, pages 195–209. Springer, 2013.
[27] T. Jurdzinski, M. Rozanski, and G. Stachowiak. Token traversal in ad hoc wireless networks
via implicit carrier sensing. SIROCCO 2017, 2017.
[28] E. Kantor, Z. Lotker, M. Parter, and D. Peleg. The minimum principle of SINR: A useful
discretization tool for wireless communication. In IEEE 56th Annual Symposium on Foundations
of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 330–349,
2015.
[29] T. Kesselheim. A constant-factor approximation for wireless capacity maximization with power
control in the sinr model. In D. Randall, editor, SODA, pages 1549–1559. SIAM, 2011.
[30] D. R. Kowalski and A. Pelc. Broadcasting in undirected ad hoc radio networks. In Proceedings
of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC ’03,
pages 73–82, New York, NY, USA, 2003. ACM.
[31] A. Ogierman, A. W. Richa, C. Scheideler, S. Schmid, and J. Zhang. Competitive MAC under
adversarial SINR. In 2014 IEEE Conference on Computer Communications, INFOCOM 2014,
Toronto, Canada, April 27 - May 2, 2014, pages 2751–2759, 2014.
[32] E. Porat and A. Rothschild. Explicit nonadaptive combinatorial group testing schemes. IEEE
Transactions on Information Theory, 57(12):7982–7989, 2011.
[33] A. W. Richa and C. Scheideler. Jamming-resistant MAC protocols for wireless networks. In
Encyclopedia of Algorithms, pages 999–1002. Springer, 2016.
[34] J. Schneider and R. Wattenhofer. A log-star distributed maximal independent set algorithm
for growth-bounded graphs. In Proceedings of the Twenty-Seventh Annual ACM Symposium on
Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages
35–44, 2008.
[35] D. Yu, Q. Hua, Y. Wang, and F. C. M. Lau. An o(log n) distributed approximation algorithm for
local broadcasting in unstructured wireless networks. In IEEE 8th International Conference on
Distributed Computing in Sensor Systems, DCOSS 2012, Hangzhou, China, 16-18 May, 2012,
pages 132–139, 2012.

28

8

Appendix

8.1

Proofs for Section 2

Lemma 1. Assume that the density of a set of nodes X is Γ. Then,
1. If X is unclustered, then there is a close pair in each ball B(x, 5) such that B(x, 1) is dense.
2. If X is clustered, then there is a close pair in each dense cluster.
Proof. The item 2. follows directly from the definitions of a dense cluster, the function χ and dΓ,r .
For item 1., assume that B = B(x, 1) is dense. Then, there are at least Γ/2 nodes in B and
therefore the smallest distance between nodes located in B is at most dΓ,1 . Let u0 , v0 ∈ B be a pair
of nodes in the smallest distance in B, d = d(u0 , v0 ) = ζdΓ,1 for 0 ≤ ζ ≤ 1. If d(u0 , v 0 ) ≥ d/2 for each
u0 , v 0 ∈ B(u0 , ζ) ∪ B(v0 , ζ) ⊂ B(u, ζ + d) then u0 , v0 is a close pair. Otherwise, let u1 , v1 be a pair
of nodes in B(u0 , ζ + d) in distance ≤ d/2. In this way, we can build a sequence of different pairs
(ui , vi ) for i ≥ 0 such that d(ui , vi ) ≤ d/2i ,
X
ui , vi ∈ B(x, 1 + (ζ + d) ·
1/2i ) ⊂ B(x, 1 + 2(ζ + d)) ⊂ B(x, 5).
i≥0

Eventually, a close pair uj , vj will appear in the sequence, as the number of nodes in X is finite.
And, uj , vj ∈ B(x, 5).

8.2

Proofs for Section 3

The proofs of technical lemmas given in this section rely on the polynomial attenuation of signals
with the power α > 2.
First, we give an estimation of the interference coming from a set of “distant nodes” with limited
density.
Proposition 1. Let T be a set of transmitting nodes, let v be a point on the plane and let x be a
positive natural number such that any ball of radius r contains at most
of T and B(v, xr)
P δ elements −α
does not contain elements of T . Then, the
overall
strength
I(v)
=
Pd(u,
v)
of signals from
u∈T

the set T received at v is O

Pr−α x−α+2 δ
α−2

.

Proof. We can estimate I(v) as

I(v) =

X
u∈T

Pd(u, v)−α ≤

X

|T ∩ (B(v, (i + 1)r) \ B(v, ir)) | · P · (ir)−α = O Pδr−α

i≥x


X

i−α+1  .

i≥x

The last equality above stems from the fact that (B(v, (i + 1)r) \ B(v, ir) is included in O(i) balls
of radius r, each such ball
and all those nodes are in distance ≥ ir from v.
R∞
P contains at most δ nodes
−α+2
By bounding the sum i≥x i−α+1 by the integral x t−α+1 dt = xα−2 we get
 −α −α+2 
Pr x
δ
I(v) = O
.
α−2

Lemma 4. (Sparse Network Lemma) Let γ ∈ N be a fixed constant and ε ∈ (0, 1) be the parameter
defining the communication graph. There exists a schedule Lγ of length O(log N ) such that each
node u transmits a message which can be received (at each point) in distance ≤ 1 − ε from u in an
execution of Lγ , provided there are at most γ nodes in each unit ball.
29

Proof. For each point v, we prove that each node in distance at most 1 − ε from v transmits a
message received at v if we set Lγ to be a (N, k)-ssf for some k which depends on: γ, ε and the SINR
parameters α > 2, β, N . Let vi denote the i-th closest node to v (where v1 = v). According to our
assumptions, only the nodes v1 , . . . , vγ can be in distance ≤ 1 − ε from v. Thus, let γ 0 ≤ γ be the
largest i such that d(v, vi ) ≤ 1 − ε. The inequality
β≤

Pd(v, vi )−α
,
I(v) + N

guarantees that v receives a message transmitted by vi for i ≤ γ 0 in some round, where
X
Pd(u, v)−α ,
I(v) =
u∈T \{vi }

T ⊂ X is the set of nodes transmitting in that round, and vi ∈ T . Thus, as d(v, vi ) ≤ 1 − ε, v
receives the message from vi if
I(v) ≤ P(1 − ε)−α /β − N = N β(1 − ε)−α /β − N = N ((1 − ε)−α ) = O(1).
We can bound I(v) as needed using Prop. 1 (with r = 1), by choosing constant x large enough
(depending on ε and SINR parameters) and assuring that there is no transmitter (except of vi ) in
B(v, x). Let kγ be the maximal number of nodes in a ball of radius x. Observe that kγ = O(x2 · γ) =
O(1) since x is a constant. Let Lγ be a (N, kγ )−ssf. Then, for each i ∈ [γ 0 ], there is a round in Lγ
in which vi is the only transmitter in B(v, x). Thus, each neighbor of v transmits in a round where
it is the unique transmitter in B(v, x) and v can hear it.
Thus, the length of the schedule Lγ is O(γ 2 log N ) = O(log N ), [32].
Lemma 5. There exists a constant κ (which depends merely on the SINR parameters and ε) which
satisfies the following property. Let u, v be a close pair of nodes in an unclustered set A. Then, there
exists a set A0 ⊆ A such that u, v ∈ A0 , |A0 | ≤ κ and v receives a message transmitted from u provided
u is sending a message and no other element from A0 is sending a message.
Proof. Let v, u be a close pair and let d(u,Pv) = d = ζdΓ,1 for ζ ∈ (0, 1]. Moreover, let T be the set
of transmitters in a round and let I(u) = w∈T \{v} P/d(w, u)−α be the interference at u caused by
other nodes. The following condition
P/d−α
β≤
,
I(u) + N
guarantees that u receives the message transmitted by v. In order to satisfy the above inequality, it
is sufficient that I(u) ≤ Pd−α /(2β) and N ≤ Pd−α /(2β).
The latter inequality is equivalent to

d≤

2N β
P

−1/α

= 2−1/α ≤ Γ−1/α ,

(2)

where the equality follows from the assumption P = N β. Thus, the latter condition can be guaranteed if dΓ,r ≤ 2−1/α , which holds for each sufficiently large Γ (recall that d ≤ dΓ,1 .)
In order to estimate I(u), we choose x ∈ N such that xd ≤ ζ and split T into T0 = T ∩ B(u, xd),
T1 = P
T ∩ (B(u, ζ) − B(u, xd)) and T2 = T − (T0 ∪ T1 ). Analogously, I(u) is split into I0 , I1 , I2 , where
Ij = w∈Tj Pd(w, u)−α for j ∈ [0, 2]. The exact value of x will be determined later.

30

Let A0 be the set of all nodes from A located inside B(u, xd). The assumption that u, v is a close
pair guarantees that each pair of nodes inside B(u, ζ) is in distance ≥ d/2. Thus the number of
nodes in A0 is at most χ(dx, d/2) = Θ(x2 ), since nodes are located on the plane.
In the following, we will analyse the scenario that v is the only transmitter from A0 . Then I0 = 0,
since T0 ⊆ A0 . In order to prove the lemma, it is sufficient to prove that I1 ≤ Pd−α /(4β) and
I2 ≤ Pd−α /(4β).
In order to estimate I1 , we apply Prop. 1 with r = d, δ = χ(d, d/2) = O(1) and T = T1 , obtaining
 −α −α+2 
Pd x
I1 = O
.
(3)
α−2
In order to estimate I2 , we make use of the assumption that each ball of radius 1 contains at most
Γ nodes and apply Prop. 1 with r = ζ ≤ 1, x = 1, δ = Γ and T = T2 , which gives

 −α
ζ PΓ
.
(4)
I2 = O
α−2
The value of I1 can be made smaller than P(2d)−α /(4β) by taking big enough but constant (i.e.,
depending only on the model parameters) x. (Recall that constant x would give |A0 | = κ = O(x2 ) =
O(1).)
The value of I2 is
 −α

ζ PΓ
I2 = O
α−2
−α

while the bound P (2d)
4β

satisfies

(2d)−α
P
=Ω
4β



−α 
P 
1/2
· 2 · ζ(1/Γ)
= Ω(ζ −α · Γα/2 ),
4β
−α

since d ≤ dΓ,1 = Θ(Γ1/2 ). Thus, I2 ≤ P (2d)
if Γ is big enough.
4β
Finally, if Γ is smaller than the values needed to satisfy (3), or (4), or (2), we can use the
construction from Lemma 4.
Lemma 6.
Let A be an r-clustered set for a fixed r = O(1). Then, there exists constants κ, ρ
(depending only on r, ε and SINR parameters) satisfying the following condition. For each cluster φ
and each close pair of nodes u, v from φ, there exists A0 ⊆ A of size ≤ κ and a set of clusters C of
size ≤ ρ such that u receives a message transmitted by v in a round satisfying the conditions:
• no node from A0 (except of v) transmits a message in the round,
• the round is free of clusters from C.
Proof. If φ is the only nonempty cluster, the result can be obtained by the same reasoning as in the
proof of Lemma 5.
In order to take other clusters into account recall that nodes from γ = O(1) clusters might appear
in each unit ball, by the definition of r-clustering (since the centers of clusters are in distance ≥ 1−ε).
Thus, the number of nodes from all clusters in a unit ball is limited by γΓ = O(Γ). For a cluster φ
included in B(x, r), let the set C of clusters “in conflict” with φ consists of all clusters (excluding φ)
whose nodes (at least one of them) are located in B(x, 2r). There are ρ = O(1) such clusters. Then,
the interference from other clusters (excluding those from C) on the nodes of a close pair in φ can
be limited similarly as in Lemma 5, thanks to the fact that the number of nodes in a unit ball is
O(Γ), the distance between nodes of a close pair is O(1/Γ1/2 ) and α > 2.

31

