On Local Broadcasting Schedules and CONGEST Algorithms in the SINR Model

Abstract

We consider the distributed construction of a deterministic local broadcasting schedule in the SINR model of interference. During the execution of such a schedule each node should be able to transmit one message to its neighbors. Our construction requires only $\mathcal {O}(\varDelta \log n)$ time slots, where $\varDelta$ is the maximum node degree in the network and $n$ the number of nodes. We prove that the length of the constructed schedule is asymptotically optimal, i.e. of length $\mathcal {O}(\varDelta )$. Considering the simulation of $\mathcal {CONGEST}$ algorithms in the SINR model, our deterministic schedule achieves a runtime of $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$ time slots, where $\tau$ is the original runtime in the $\mathcal {CONGEST}$ model. We show that there is a lower bound of $\varOmega (\varDelta ^2)$ for the simulation of each one of the $\tau$ rounds, hence our simulation is optimal apart from the logarithmic factor. If we restrict the knowledge of the nodes and let the maximum node degree $\varDelta$ be unknown, we can prove that at least $\varOmega (\mathrm{D }+ \tau \varDelta ^2)$ time slots are required to simulate synchronized $\mathcal {CONGEST}$ algorithms in the SINR model of interference, where $\mathrm{D }$ is the diameter of the network. For our algorithms we assume location information to be given. Regarding the case without location information we argue that a deterministic algorithm to compute local broadcasting schedules by Derbel and Talbi [ICDCS’10], which requires transmission power adaption, needs messages of size $\mathcal {O}(\log n)$ to simulate $\mathcal {CONGEST}$ algorithms. This is a logarithmic factor less than stated by the authors.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Local broadcasting is one of the most fundamental task in wireless networks. In contrast to global broadcasting, where one message must be spread over the whole network, in the problem of local broadcasting each node must send one message only to all direct neighbors. In wireless networks usually only a fraction of all nodes can broadcast simultaneously due to the signal interference of multiple transmissions. Hence local broadcasts must be coordinated in order to avoid too high interference. Since interference is modeled relatively realistic in the SINR model (Signal-to-Interference-and-Noise-Ratio model, cf. Sect. 2), the problem of finding a local broadcasting schedule must be tackled by algorithms designed for this model, whereas for many other models such as the message-passing based $\mathcal {CONGEST}$ or $\mathcal {LOCAL}$ models [1] the broadcasting problem does not occur as interference-free communication is assumed (cf. Sect. 2). Thus, in these models message reception is guaranteed regardless of other transmissions.

However, wireless technology is becoming more and more ubiquitous and hence distributed computing in a wireless context—along with the SINR model—received increasing attention in recent research. Local broadcasting is a fundamental problem in the SINR model that can be used as a building block to solve higher-level problems. Hence it is quite well studied and can be solved in $\mathcal {O}(\varDelta \log n)$ time slots [2] (where $\varDelta$ is the maximum number of nodes in any transmission region of the network) if $\varDelta$ is known. Further results will be discussed in Sect. 1.1. Due to the vast amount of algorithms designed for message-passing models, one particularly interesting application of local broadcasting is to simulate algorithms designed for message-passing models in the SINR model.

For complex algorithms it may be more effective to invest some time in a preprocessing step in order to achieve faster local broadcasting. In fact, this can be beneficial and both Derbel and Talbi [3] and Jurdzinski and Kowalski [4] achieve—using different methods and assumptions—local broadcasting in $\mathcal {O}(\varDelta )$, which is optimal due to a trivial lower bound¹ For Derbel’s and Talbi’s approach such a preprocessing requires $\mathcal {O}(\varDelta \log n)$ time slots while Jurdzinski’s and Kowalski’s approach requires $\mathcal {O}(\varDelta \log ^3 n)$ slots. Inspired by both approaches we describe how to construct a deterministic local broadcasting schedule with optimal length $\mathcal {O}(\varDelta )$ and preprocessing time of $\mathcal {O}(\varDelta \log n)$ time slots. We use distributed node coloring proposed by Derbel and Talbi [3] to construct an infeasible local broadcasting schedule and combine it with the concept of dilution by Jurdzinski and Kowalski [4], which enables us to achieve feasibility of the schedule while increasing the length of the schedule only by a constant factor. We require the nodes to know an upper bound on the number of nodes $n$, the maximum node degree $\varDelta$ in the network, their own ID, and location information. We do not require carrier sensing and restrict ourselves to uniform and non-adjustable transmission powers.

Our deterministic local broadcasting algorithm differs from the previously mentioned algorithms in various ways. In contrast to the distributed node coloring by Derbel and Talbi [3] we do not require the nodes to tune their transmission power, while they require the nodes to tune the transmission power by a constant factor. With regard to the backbone structure constructed by Jurdzinski and Kowalski [4] the method described in this work is faster by a polylogarithmic factor.

Using the local broadcasting schedule to simulate algorithms (with original runtime $\tau$) designed for the $\mathcal {CONGEST}$ model, we achieve a runtime of $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$ time slots in the SINR model. Regarding the case that nodes do not know the global maximum degree, we show a lower bound of $\varOmega (\tau \varDelta ^2 + \mathrm{D })$ (with diameter $\mathrm{D }$) on the runtime in the SINR model for the simulation of synchronized $\mathcal {CONGEST}$ algorithms.

Finally, we argue that the local broadcasting based on a coloring described in [3] is capable of simulating message-passing algorithms with messages that are by a factor of $\log n$ smaller than stated. This results in an approach that is capable of simulating $\mathcal {CONGEST}$ algorithms in $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$ using messages of size $\mathcal {O}(\log n)$. This is as fast as the deterministic local broadcasting schedule described in this work, however, note that they assume the nodes to tune their transmission power by a constant factor, while we require location information to be given.

1.1 Related Work

A few years ago, the SINR model has only been considered for basic communication problems in wireless networks such as connectivity [5, 6], link scheduling [7], or local broadcasting [2]. However, it recently attracted considerable attention even in the distributed computing community. There are now initial works considering distributed computing problems in the SINR model, for example distributed node coloring [3, 8], independent sets [8] or dominating sets [9].

However, due to the complexity of analyses in the SINR model, it is reasonable to use local broadcasting as a building block in order to run more evolved distributed computing algorithms on wireless networks. By simulating a round-based message-passing environment through local broadcasting even complex distributed algorithms such as for example all-pairs shortest paths [10] or graph partition [11] designed for the message-passing-based $\mathcal {CONGEST}$ model can be made available in the SINR model.

The simulation of message-passing algorithms in radio networks (in which a message is successfully received if the receiver is silent and only one of its neighbors is transmitting) has first been studied by Alon et al. in [12]. They propose a separate simulation of each round of the message-passing algorithm. Among other results they proved a bound of $\varTheta (\varDelta ^2)$ for the case that each node transmits a different message to each of its neighbors. The lower bound translates to the SINR model with a slightly modified proof (see Sect. 4.1), while the upper bound has not yet been reached. Kuhn et al. [13] proposed an abstract interface—an abstract MAC layer—that enables easier models (i.e., message-passing based models) to be executed in more realistic models for wireless communication. However, they did only describe an implementation of the abstract MAC layer by local broadcasting in the radio network model, which does not account for global interference.

Local broadcasting in the SINR model has first been studied by Goussevskaia et al. in [2]. They considered local broadcasting with known and unknown competition (which is the number of nodes within a certain region around the node) in asynchronous networks and propose two randomized algorithms for the asynchronous SINR model with runtimes of $\mathcal {O}(\varDelta \log n)$ and $\mathcal {O}(\varDelta \log ^3 n)$ for known and unknown competition. Yu et al. [14] improve the approximation ratio for the unknown competition by a logarithmic factor to $\mathcal {O}(\varDelta \log ^2 n)$ and propose two algorithms for the synchronized model (with synchronous and asynchronous wake-up) that make use of carrier sensing and thereby achieve local broadcasting in $\mathcal {O}(\varDelta \log n)$ time slots. In [15] Yu et al. improve the algorithm for asynchronous time slots and unknown competition further to $\mathcal {O}(\varDelta \log n + \log ^2 n)$ and provide a lower bound of $\varOmega (\varDelta + \log n)$ for randomized algorithms in this model. Halldórsson and Mitra [16] provide an algorithm with the same running time of $\mathcal {O}(\varDelta \log n + \log ^2 n)$ in the same model, that is slightly simpler and more robust. They also provide an algorithm that achieves a running time of $\mathcal {O}(\varDelta + \log ^2 n)$ per round of local broadcasting with the assumption that acknowledgments are received freely.

The first result that achieves local broadcasting in the synchronized SINR model in $\mathcal {O}(\varDelta )$ after a preprocessing stage of $\mathcal {O}(\varDelta \log n)$ time slots is from Derbel and Talbi [3]. They transfer a distributed node coloring algorithm proposed by Moscibroda and Wattenhofer [17] to the SINR model and, by tuning the transmission power during the coloring step, achieve a deterministic local broadcasting schedule of length $\mathcal {O}(\varDelta )$ that is feasible in the SINR model. A second result by Jurdzinski and Kowalski [4], which assumes the location to be known to the nodes, achieves the optimal runtime of $\mathcal {O}(\varDelta )$ for local broadcasting without requiring the capability of nodes to tune their transmission power. However, the preprocessing stage requires $\mathcal {O}(\varDelta \log ^3 n)$ time slots. The authors introduce the concept of dilution (cf. Sect. 2.2) and build a deterministic backbone structure that enables communication to the backbone in $\mathcal {O}(\varDelta )$ and local broadcasts from within the backbone in constant time. This backbone structure also enables local broadcasting in $\mathcal {O}(\varDelta )$. For an overview of related results, see Table 1.

Table 1. Local broadcasting results for the SINR model. Ordered chronologically by appearance with separation in algorithms with and without preprocessing.

1.2 Structure

The rest of this paper is structured as follows. In the next section, we describe required models and state some basic definitions. In Sect. 3, the construction of the deterministic local broadcasting schedule is described and we show its feasibility in the SINR model. Afterwards we consider the simulation of $\mathcal {CONGEST}$ algorithms in the SINR model in Sect. 4. We conclude this work with some final remarks in Sect. 5.

2 Model and Definitions

We consider a wireless network consisting of $n$ nodes, that are placed arbitrarily on the Euclidean plane. The global maximum number of nodes within a transmission region is called the maximum degree of any node in the network and denoted by $\varDelta$. We usually assume that all nodes in the network know their ID and an upper bound $\tilde{n}$ on $n$, with $\tilde{n} \le n^c$ for some constant $c \ge 1$. As the upper bound influences our results only by a constant factor we usually write $n$ even though only $\tilde{n}$ may be known by the nodes.

In the geometric SINR model a transmission from node $v$ to node $w$ is successful iff the SINR condition holds:

$$\begin{aligned} \frac{\frac{\mathrm{P }_v}{\mathrm{dist }(v,w)^\alpha }}{\sum _{u\in \mathcal {I}} \frac{\mathrm{P }_u}{\mathrm{dist }(u,w)^\alpha } + N} \ge \beta \end{aligned}$$

(1)

where $\mathrm{P }_v$ ($\mathrm{P }_u$) denotes the transmission power of node $v$ ($u$), $\alpha$ is the attenuation coefficient² depending on the network environment, the SINR-threshold $\beta \ge 1$ is a hardware-defined constant, $N$ is the environmental noise and $\mathcal {I}$ is the set of nodes sending simultaneously with $v$. We assume uniform transmission powers, hence $\mathrm{P }_v = \mathrm{P }$ for each node $v$.

Based on the SINR condition the maximum transmission range of each node is $(\frac{\mathrm{P }}{N\beta })^{1/\alpha }$. However, as soon as only one other node in the network transmits simultaneously, this transmission range cannot be achieved anymore. Having only one transmission in the whole network is clearly not desired, hence we define the maximum transmission range $R_T$ such that twice the amount of noise can be tolerated: $R_T= (\frac{\mathrm{P }}{2N\beta })^{1/\alpha }$. Note that this is a usual assumption and consistent with [3]. We do not exactly require twice the amount of noise, any constant factor $b > 1$ would also be sufficient. The area that is within the transmission range of a node $v$ is denoted by $D_T^v$.

2.1 Simulating $\mathcal {CONGEST}$ Algorithms in the SINR Model

Let us first introduce the $\mathcal {CONGEST}$ model of distributed computation [1] briefly. This model focuses on the effects of congestion in distributed networks. Algorithms in the $\mathcal {CONGEST}$ model enforce a $\mathcal {O}(\log n)$ limitation on the maximum message size, while messages can only be sent to neighboring nodes. Note that with one message only a constant number of node IDs in the range $[0,\dots ,n]$ can be transmitted in this model. Hence, unlike in the $\mathcal {LOCAL}$ model which allows messages of unlimited sizes but restricts the runtime to a constant number of rounds [1] only a small fraction of the possibly obtained information can be made known to neighbors in reasonable time.

For a simulation of algorithms designed for the $\mathcal {CONGEST}$ model of distributed computation in the geometric SINR model we require the following properties to hold:

• Locality: The neighbors of each node $v$ must be reachable in our model, i.e., in the nodes transmission area $D_T^v$.

• Disambiguity: Each message is intended to one receiver, which is specified in the message by the receivers ID.

• Synchronization: Two neighbors are not allowed to be in different rounds of the $\mathcal {CONGEST}$ algorithm.

For the simulation to be successful we require that one or more transmission per sender-receiver-pair must be feasible in the SINR model of interference with high probability (w.h.p.—at least probability $1-\frac{1}{n^c}$ for a constant $c > 0$) in each round of the $\mathcal {CONGEST}$ algorithm. Note that by disambiguity messages that are overheard by a node but not intended for it are discarded upon reception. This is not required in any part of our algorithms but increases clarity of the required properties. We usually assume the network to be connected, hence synchronization in combination with connectivity implies that all nodes must be in the same round of the $\mathcal {CONGEST}$ algorithm.

2.2 Dilution and Backbone Structure

In accordance with [4] we call a partition of the 2-dimensional plane in boxes of size $\gamma \times \gamma$, where $\gamma = R_T{ /} \sqrt{2}$, the pivotal grid $G_{\gamma }$. Note that the dimensions of the box are such that all nodes within the same box are within each others transmission radius. Formally each box includes its bottom and left side but does not include its top and right side. We assume box $C(i,j)$ to be the box with lower left coordinates $(i,j) \in {\mathbb {R}}^{2}$. A node with position $(x,y)$ is in box $C(i,j)$ iff $\lfloor \frac{x}{\gamma } \rfloor = i$ and $\lfloor \frac{y}{\gamma } \rfloor = j$.

A local broadcast schedule can be seen as an assignment of 0/1-bitstrings to nodes indicating in which time slots the node is allowed to broadcast. In the deterministic schedule constructed in this work, however, each node sends only once throughout an execution of the schedule. Hence we can simply store the number of the time slot instead of a 0/1 bitstring.

In order to combine geometric information with local broadcast schedules, we use the concept of dilution as introduced in [4]. For a constant $\delta$, which determines the distance between two active transmissions and will be defined later, we assign each node $v$ local coordinates $(l_x^v, l_y^v) = (\lfloor \frac{x}{\gamma } \rfloor \mod \delta , \lfloor \frac{y}{\gamma } \rfloor \mod \delta ) = (i \mod \delta , j \mod \delta )$. This ensures that nodes in the same box of $G_{\gamma }$ share the same local coordinates. Now, we can dilute a local broadcast schedule by a factor of $\delta ^2$ by allowing each node $v$ with local coordinates $(l_x^v,l_y^v)$ to send in time slot $t \delta ^2 + l_x^v \delta + l_y^v$ iff $v$ was allowed to send in time slot $t$ in the original schedule.

3 Deterministic Local Broadcasting Schedule

One main approach for wireless transmission scheduling problems is to find a graph coloring and then use this coloring to decide when and for how long each node is allowed to transmit a message. This can be done by simply associating each color with a time slot. Let us first consider the simpler protocol model, in which a transmission is successful iff in the interference range (which often equals the transmission range) of the receiver only one node is transmitting at a given time. Even in this simpler model a node coloring which ensures that two nodes are assigned different colors if they are within each others transmission range is not sufficient to directly build a feasible transmission schedule as depicted in Fig. 1. However, for the protocol models this can be overcome by using a distance-2-coloring (i.e., a coloring which ensures unique colors within each transmission region $D_T$).

Due to the global nature of interference in the SINR model, finding some sort of agreement about transmission schedules (i.e., medium access) is required for deterministic local broadcasting schedules. In the case of coloring in the SINR model, even the more refined coloring that achieves unique colors within each transmission region is not sufficient as shown in Fig. 1(b). However, schedules can be made feasible if the node coloring ensures unique colors in an area larger than the transmission region. Unfortunately finding such a coloring is not possible if we cannot reach nodes outside the transmission region. Finding a coloring can be made possible by tuning the nodes transmission power to reach a larger transmission region, cf. [3], investing time in $\varOmega (\mathrm{D })$ (given the network is connected), or having additional knowledge such as location information or knowledge about the topology. As computation of the diameter requires $\varOmega (n)$ time slots [18], we restrict ourselves to some additional knowledge. In this work we consider location information to be known by each node. In the following theorem we show that we can distributedly construct a feasible local broadcasting schedule based on the location information and a given node coloring, even if the coloring does not ensure unique colors within each transmission region $D_T$. Note that such a coloring is easy to compute within $\mathcal {O}(\varDelta \log n)$ time slots even in the SINR model [3]. If not noted otherwise we assume such a coloring.

Fig. 1.

Using a coloring as depicted on the left does not yield a feasible local broadcasting schedule in the protocol model as the transmission from $v$ to $w$ is not feasible as according to the coloring $u$ and $v$ transmit simultaneously. However, the coloring on the right corresponds to a local broadcasting schedule that is feasible in the protocol model. Still it is not feasible in the SINR model as the SINR constraint is violated (at least for $\alpha \le 6$).

Theorem 1

Given a network of nodes in which each node knows its location, the color assigned by a coloring using at most $c_{\text {max}} = \mathcal {O}(\varDelta )$ colors, and $c_{\text {max}}$ itself. Then we can distributedly compute a local broadcasting schedule that is feasible under the SINR model of interference with length in $\mathcal {O}(\varDelta )$.

In order to prove the theorem we first show that such a coloring is a local broadcasting schedule in which at most one node sends in each box of the pivotal grid $G_{\gamma }$ (Lemma 1), and then prove that we can achieve a feasible schedule by applying dilution to this schedule (Lemma 2).

Lemma 1

Given a network in which each node has a unique color within distance $R_T$. This implies a local broadcast schedule in which in each slot at most one node is transmitting in each box of the pivotal grid $G_{\gamma }$.

Proof

As each node knows the number $c$ of its color and a shared upper bound $c_\text {max}$ on the number of colors assigned to the nodes in the network we can assign each color to one of $c_\text {max}$ time slot. Consider a node $v$ within box $C(i,j)$ and color $c$. Since the diameter of each box is exactly $R_T$, the coloring ensures that there is no other node within box $C(i,j)$ that has color $c$.

We extend Proposition 1 in [4] by explicitly giving a formula to compute the constant $\delta$ (depending only on $\alpha$) that enables us to prove feasibility of a $\delta$-diluted schedule in the SINR model of interference for $\alpha > 2$. For $\alpha =2$ we can also achieve feasibility, however for $\delta \in \mathcal {O}(\log n)$, which is now additionally dependent on $n$. This leads to an increase in the schedule length of a multiplicative factor of $\delta ^2\in \mathcal {O}(\log ^2 n)$.

Lemma 2

Let $\alpha > 2$ and $\delta = \left( \frac{8 \mathrm{P }\sum _{k=1}^\infty \frac{1}{k^{\alpha -1}}}{\mathrm{N }\gamma ^\alpha }\right) ^{1/\alpha }+3$. Then a local broadcasting schedule $\mathcal {S}$ in which at most one node in each box of the pivotal grid $G_{\gamma }$ transmits in each time slot can be made feasible in the SINR model of interference with a constant increase in the schedule length.

The case $\alpha = 2$ is considered after the proof.

Proof

Let $\mathrm{length }(\mathcal {S})$ be the length of the local broadcasting schedule $\mathcal {S}$. In order to achieve a feasible schedule, we dilute the schedule $\mathcal {S}$ by a constant $\delta ^2$ and obtain a feasible schedule $\mathcal {S'}$ with $\mathrm{length }(\mathcal {S'}) = \mathcal {O}(\mathrm{length }(\mathcal {S}) \cdot \delta ^2) = \mathcal {O}(\mathrm{length }(\mathcal {S}))$. In this schedule $\mathcal {S'}$ a node $v$ with local coordinates $(l_x^v,l_y^v)$ sends in time slot $t \delta ^2 + l_x^v \delta + l_y^v$ if and only if the node would have sent in time slot $t$ of schedule $\mathcal {S}$.

Let us now consider an arbitrary time slot of schedule $\mathcal {S'}$, a node $v$ that transmits a message in this time slot, and another node $w$ that is within the transmission region of $v$. Let $C(i,j)$ be the box in which $v$ is located and accordingly $(l_x^v, l_y^v) = (i \mod \delta , j \mod \delta )$ the local coordinates of $v$. We claim that $w$ can successfully receive the message sent by $v$ and hence—as we considered an arbitrary sender, receiver and time slot—this schedule is feasible in the SINR model. To show this claim we bound the interference received by $w$ from simultaneously transmitting nodes by first upper bounding the number of simultaneously transmitting nodes within certain distances and then computing an upper bound on the interference of all those nodes on $w$.

The application of $\delta$-dilution ensures that only nodes $u$ with local coordinates $(l_x^u, l_y^u) = (i \mod \delta , j \mod \delta ) = (l_x^v, l_y^v)$ transmit simultaneously with $v$. Note that local coordinates are shared by all nodes in the same box. Hence we call boxes that have nodes with the same local coordinates as $v$, i.e. boxes that are also allowed to send in the considered time slot, active. Due to the cyclicity of the modulo operator, $\delta$-dilution results in a grid of active boxes with distance $\xi := (\delta -1) \gamma$ between each two active boxes, as depicted in Fig. 2. Note that according to Lemma 1 at most one node in each active box transmits in each time slot.

Fig. 2.

Grid cells of $G_{\gamma }$ that are active simultaneously to a transmission originating from box $C(i,j)$. Note that in order to increase readability $\xi := (\delta -1) \gamma$.

Let us now examine how many active boxes there are at specified distances. We consider the boxes in so-called rings, which actually are the border layer of active boxes of a square centered at the box $C(i,j)$. In the situation of Fig. 2 all depicted nodes in columns $j-\delta$ , $j$ and $j+\delta$ except for $C(i,j)$ itself are in boxes of ring level 1 from $C(i,j)$. It can be observed that in each ring of level $k \ge 1$, exactly $8k$ active boxes can be accommodated. Also, each node in level $k$ has distance at least $k ((\delta -3) \gamma )$ from $w$ ($\delta -3$ since $w$ can be at most 2 boxes away from $v$).

Using this relation we can now upper bound the interference received by $w$ from all nodes sending simultaneously with $v$, which are at most $8k$ nodes from each ring level $k$. Hence the interference at w is at most

$$\begin{aligned} {\sum _{\begin{array}{c} u \in V\backslash \{v\},\\ u \text { sending simultaneously with } v \end{array}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \frac{\mathrm{P }}{\mathrm{dist }(u,w)^\alpha } \;\;\; \le \;\;&\sum _{k=1}^\infty (8k) \frac{\mathrm{P }}{(k(\delta -3) \gamma )^\alpha } \end{aligned}$$

(2)

$$\begin{aligned} \le \;\; \sum _{k=1}^\infty \frac{8 \mathrm{P }k}{k^\alpha (\delta -3)^\alpha \gamma ^\alpha } \le \;\;&\frac{8\mathrm{P }}{(\delta -3)^\alpha \gamma ^\alpha } \left( \sum _{k=1}^\infty \frac{1}{k^{\alpha -1}} \right) \le \;\; N \end{aligned}$$

(3)

where the first equation follows from applying the considerations about the ring levels and the last equation follows by insertion of $\delta$. Note that the sum, which is the generalized harmonic number of order $(\alpha -1)$, evaluates to a value lower than 6 for $\alpha >2.2$ and is in $\mathcal {O}(1)$ for any $\alpha >2$ [19].

Evaluating the SINR at node $w$ yields

where the first inequality follows from $\mathrm{dist }(v,w) \le R_T$ and Eq. 3 and the last inequality follows from the definition of the transmission range $R_T= (\frac{\mathrm{P }}{2N\beta })^{1/\alpha }$. This concludes the proof for $\alpha > 2$.

We will now briefly consider the case of $\alpha =2$.

Corollary 1

Let $\alpha = 2$ and $\delta = \left( \frac{8 \mathrm{P }\sum _{k=1}^n \frac{1}{k^{\alpha -1}}}{\mathrm{N }\gamma ^\alpha }\right) ^{1/\alpha }+3$. Then a local broadcasting schedule $\mathcal {S}$ in which at most one node in each box of the pivotal grid $G_{\gamma }$ transmits in each time slot can be made feasible in the SINR model of interference with a factor $\delta ^2\in \mathcal {O}(\log ^2 n)$ increase in the schedule length.

Proof

Note that we changed the sum introduced in Eq. 2 from $\sum _{k=1}^\infty$ to $\sum _{k=1}^n$. This is possible as at most $n$ non-empty ring levels exist. Since the distance of the levels increases it holds that

$$\begin{aligned} \sum _{\text {non-empty ring levels k}} \!\!\!\!\!\!\!\!\!\!\!\!\! \frac{1}{k^{\alpha -1}} \le \sum _{k=1}^n \frac{1}{k^{\alpha -1}} \end{aligned}$$

(4)

and hence the resulting sum $\sum _{k=1}^n \frac{1}{k}$ can be evaluated to $\mathcal {O}(\log n)$[19]. This implies $\delta \in \mathcal {O}(\log n)$ and finally $\mathrm{length }(\mathcal {S'}) = \mathcal {O}(\mathrm{length }(\mathcal {S}) \cdot \delta ^2) = \mathcal {O}(\mathrm{length }(\mathcal {S}) \cdot \log ^2 n)$ as claimed in the corollary.

A pseudo code of the procedure described above is given in Algorithm 1. First an initial schedule is computed by distributed node coloring, then this schedule is diluted in order to obtain a schedule that is feasible in the SINR model. We can see that the algorithm itself is very simple. For a definition of the parameters cf. Sect. 2. Note that regarding $\delta$ neither the ceiling nor limiting the sum at $n$ affects our theoretic results.

4 Simulating $\mathcal {CONGEST}$ Algorithms in SINR

Using the deterministic local broadcasting schedule constructed in Sect. 3, $\mathcal {CONGEST}$ algorithms with a runtime in $\mathcal {O}(\tau )$ can be simulated in $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$ for $\alpha > 2$. This can be done by first computing the local broadcasting schedule in $\mathcal {O}(\varDelta \log n)$ and then simulating the algorithm using so-called single-round-simulation as introduced by Alon et al. [12]. This requires $\varDelta$ executions of the local broadcasting schedule for each round of the message-passing algorithm.

We restrict ourselves to the simulation of general $\mathcal {CONGEST}$ algorithms in most parts of our work. In this model a node can send a different message of size $\mathcal {O}(\log n)$ to each neighbor in each round (cf. Sect. 2.1). However the methods transfer to the simulation of algorithms designed for similar models, for example if the same message is sent to all neighbors or if differently-sized messages are used. In particular for messages of arbitrary size $s$ in a message-passing algorithm, the message size during simulation in the SINR model is $O(s + \log n)$. If unlike in the $\mathcal {CONGEST}$ model the same message is sent to each neighbor the runtime of the simulation decreases to $\mathcal {O}(\tau \varDelta + \varDelta \log n)$.

4.1 The Maximum Node Degree and the Simulation of (Synchronized) $\mathcal {CONGEST}$ Algorithms

Regardless of which local broadcasting strategy we use to simulate the rounds of the message-passing algorithm, all nodes must know the maximum number of time slots required to simulate one round of the message-passing algorithm. This number is needed so that each node can determine the time slot in which all nodes should finish with a certain round of the $\mathcal {CONGEST}$ algorithm. In the case of our local broadcasting schedule the number of slots required per round is $r = \varDelta (\delta ^2 \cdot c_\text {max})\in \mathcal {O}(\varDelta ^2)$, where $c_\text {max}$ is the number of colors used by the node coloring.

So far we assumed the global maximum node degree $\varDelta$ to be known to all nodes. In this section we will show that without an upper bound on the maximum node degree we cannot simulate a synchronized message-passing algorithm in less than $\varOmega (D+\tau \varDelta ^2)$ time slots, where $D$ is the diameter of the network. In order to show this results, let us briefly consider a lower bound on the number of time slots required to simulate one round of a general message-passing algorithm. Such a lower bound has already been stated by Alon et al. in [12] for the radio network model. However, it does not directly transfer to the SINR model. Note that we show the lower bound for message-passing models that allow to send a different message to each neighbor in each round (which is consistent with the assumptions of Alon et al.). This includes the general $\mathcal {CONGEST}$ model.

Lemma 3

One round of a message-passing algorithm cannot be simulated in less than $\varOmega (\varDelta ^2)$ time slots, where $\varDelta$ is the maximum node degree of all nodes in the network.

Proof

Assume a graph with all nodes within one transmission radius $R_T$ and let this graph consist of two clusters $S_l, S_r$ of the same (geometric) diameter $d$. Let those clusters be at least $\eta$ times the diameter apart from each other and $\eta > 1$ be chosen such that $\frac{\mathrm{P }}{(\eta d)^\alpha } - \frac{\mathrm{P }}{((\eta +2)d)^\alpha } < N$ (note that the left part tends towards 0 for increasing values of $\eta$). Such clusters are shown in Fig. 3.

Fig. 3.

Two clusters of same diameter within one transmission region. The distance between the clusters is more than $\eta$ times the diameter of the cluster.

Fig. 4.

The network is constructed such that $a$ nodes are in the cluster on the right. For $a>2$ the maximum node degree $\varDelta$ occurs in the cluster on the right and must be communicated through the network. The transmission range is such that on the left part at most two nodes are within each others transmission range.

Let us only consider the transmission from the left cluster to the right cluster. Each node in the left cluster must transmit one different message to each node in the right cluster. This yields $\frac{\varDelta }{2} \times \frac{\varDelta }{2}\in \varOmega (\varDelta ^2)$ inter-cluster-transmissions.

We will now show that at most one inter-cluster transmission can occur in one time slot. Let $v\in S_l$ be in the left cluster and $w\in S_r$ be in the right cluster. Assume $v$ transmits to $w$ in time slot $t$ and assume another node $u$ transmits to any other node in the same time slot. There are 2 cases: $u$ can either be in $S_l$ or $S_r$. In both cases $u$ transmits simultaneously to $v$ and we show that $w$ cannot successfully receive $v$’s message due to a SINR of less than 1. Let $u\in S_l$, then the SINR constraint (cf. Sect. 2) evaluates to

$$\begin{aligned} \frac{\frac{\mathrm{P }}{\mathrm{dist }(v,w)^\alpha }}{\frac{\mathrm{P }}{\mathrm{dist }(u,w)^\alpha } + N}&\le \frac{\frac{\mathrm{P }}{(\eta d)^\alpha }}{\frac{\mathrm{P }}{((\eta +2)d)^\alpha } + N} < \frac{\frac{\mathrm{P }}{(\eta d)^\alpha }}{\frac{\mathrm{P }}{((\eta +2)d)^\alpha } + \frac{\mathrm{P }}{(\eta d)^\alpha } - \frac{\mathrm{P }}{((\eta +2)d)^\alpha }} = \frac{\frac{\mathrm{P }}{(\eta d)^\alpha }}{\frac{\mathrm{P }}{(\eta d)^\alpha }} = 1 \le \beta \end{aligned}$$

where the first inequality holds since $\mathrm{dist }(v,w) \ge \eta d$ and $\mathrm{dist }(u,w) \le (\eta +2)d$ and the strict inequality follows from the selection of $\eta$. Hence $w$ cannot receive $v$’s message. Otherwise, if $u$ in $S_r$ the SINR is

$$\begin{aligned} \frac{\frac{\mathrm{P }}{\mathrm{dist }(v,w)^\alpha }}{\frac{\mathrm{P }}{\mathrm{dist }(u,w)^\alpha } + N}&\le \frac{\frac{\mathrm{P }}{(\eta d)^\alpha }}{\frac{\mathrm{P }}{(d)^\alpha } + N} < \frac{1}{\eta ^\alpha } < 1 \le \beta \end{aligned}$$

where the first inequality again holds since $\mathrm{dist }(v,w) \ge \eta d$ and $\mathrm{dist }(u,w) \le d$, the second inequality follows from $0 < N$ and cancelation of $\frac{\mathrm{P }}{d^\alpha }$ and the third inequality holds since $\eta ^\alpha > 1$. Hence at most one transmission from the left to the right cluster can happen in one time slot. This shows that $\frac{\varDelta }{2} \times \frac{\varDelta }{2}\in \varOmega (\varDelta ^2)$ time slots are needed to simulate one round of a message-passing algorithm.

We can now prove the main result of this section, which provides a lower bound on the simulation runtime if the global maximum degree is not known to the nodes in the network.

Proposition 1

Let $n$ be the only knowledge available to the nodes. Then the simulation of a synchronized message-passing algorithm (e.g., $\mathcal {CONGEST}$) that requires $\tau$ rounds in the message-passing model cannot be executed in less than $\varOmega (\mathrm{D }+\tau \varDelta ^2)$ time slots in the SINR model.

Proof

According to Lemma 3, $\varOmega (\tau \varDelta ^2)$ is a lower bound for simulating a message-passing algorithm with runtime $\tau$. To show the $\varOmega (\mathrm{D })$ lower bound, note that networks with $\varDelta = \sqrt{\mathrm{D }}$ exist, and hence in those networks at least $\varOmega (\mathrm{D })$ time slots are required for each round of the simulation. However, there exist also networks in which $\tau \varDelta ^2 \not \in \varOmega (\mathrm{D })$ and still $\varOmega (\mathrm{D })$ time slots are required for the simulation. Hence $\varOmega (\mathrm{D }+ \tau \varDelta ^2)$ is effectively a stronger bound than $\varOmega (\tau \varDelta ^2)$.

Consider two networks. The first is the network depicted in Fig. 4 with $a=\sqrt{n}$, and the second a line network (which is equal to the depicted network without the high-density part on the right, i.e. with $a = 0$). Clearly the line network is a network in which $\tau \varDelta ^2 \not \in \varOmega (\mathrm{D })$. For nodes on the left end of both networks the view is exactly the same until at least $\varOmega (\mathrm{D })$ time slots have passed and information from the high-density part can reach the left end of the network. Assume for contradiction that there is an algorithm that finishes the simulation on both networks in less than $\varOmega (\mathrm{D })$ time slots. This algorithm must compute the number of time slots required for each round of the simulation in order to synchronize the message-passing algorithm. Since the information about the high-density part is not available to nodes on the left end of both networks the algorithm computes the same number of required time slots in the leftmost nodes of both networks. Regardless of the result the algorithm fails to simulate the message-passing algorithm in one of the networks. If the result (i.e., the required number of time slots per simulated round) is in $o(\sqrt{n})$, the algorithm fails in the network depicted in Fig. 4 with $a=\sqrt{n}$, as the network cannot be synchronized. If the result is in $\varOmega (\sqrt{n})$ this results in $\varOmega (n) = \varOmega (\mathrm{D })$ time slots for the simulation, which contradicts the assumption that the algorithm runs in less than $\varOmega (\mathrm{D })$ time slots on both graphs. Hence any algorithm that simulates a synchronized message-passing algorithm in the SINR model without the knowledge of $\varDelta$ requires at least $\varOmega (\mathrm{D })$ time slots.

Note that the proof relies on restrictions on simultaneous transmissions and the synchronization of the $\mathcal {CONGEST}$ algorithm. Hence letting the node know the diameter $\mathrm{D }$ or even its position does not circumvent the bound.

4.2 Notes on Location Information

After considering the case that the global maximum degree $\varDelta$ is unknown, we will now focus on the knowledge of location information. Local broadcasting in $\mathcal {O}(\varDelta )$ time slots (after a preprocessing stage of $\mathcal {O}(\varDelta \log n)$ time slots) is also possible by allowing nodes to tune their transmission power. Derbel and Talbi describe an algorithm that is based on distributed node coloring with tuned transmission radius in [3] and they achieve a runtime of $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$. However, they state a message size of $\mathcal {O}(s \cdot \log n)$, where $s$ is the original message size. For the simulation of $\mathcal {CONGEST}$ algorithms this results in messages of size $\mathcal {O}(\log ^2 n)$ instead of $\mathcal {O}(\log n)$. We claim that messages of size $\mathcal {O}(\log n)$ are possible and hence this additional logarithmic factor is not necessary. The algorithm consists of two parts. In the first part a distributed node coloring is computed. For this only the node ID and the number of the color must be transmitted. Hence messages of size $\mathcal {O}(\log n)$ are sufficient. In the second part the actual simulation takes place. Therefore the original message of size $s$ along with a node ID (in order to identify the receiver) must be transmitted. This requires messages of size $\mathcal {O}(s + \log n)$. For $\mathcal {CONGEST}$ algorithms this results in messages of size $\mathcal {O}(\log n)$, since $s\in \mathcal {O}(\log n)$.

Hence for both cases, using either tuned transmission powers or location information the same runtime of $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$ and messages of size $\mathcal {O}(\log n)$ are sufficient to simulate a $\mathcal {CONGEST}$ algorithm with original runtime $\tau$ in the SINR model.

5 Conclusion

In this work we introduced a new algorithm to compute a deterministic local broadcasting schedule of optimal length $\mathcal {O}(\varDelta )$ that is feasible in the SINR model of interference. The construction of the schedule requires $\mathcal {O}(\varDelta \log n)$ time slots, which is optimal up to the logarithmic factor. The algorithm enables the simulation of algorithms designed for message-passing models in more realistic models of interference such as the SINR model: An algorithm with original runtime of $\tau$ rounds in the $\mathcal {CONGEST}$ model can be simulated in $\mathcal {O}(\tau \varDelta ^2 + \varDelta \log n)$ time slots in the SINR model. This is optimal apart from the logarithmic factor. Our algorithm assumes that nodes know their position and the global maximum node degree $\varDelta$. We showed a lower bound of $\varOmega (\mathrm{D }+ \tau \varDelta ^2)$, thus the knowledge of $\varDelta$ is required in order to achieve an efficient simulation.