# On Constructingt-Spanner in IoT under SINR

Authors: Xiujuan Zhang; Yongcai Wang; Wenping Chen; Yuqing Zhu; Deying Li; Guangshun Li
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Following the recent advances in the Internet of Things (IoT), it is drawing lots of attention to design distributed algorithms for various network optimization problems under the SINR (Signal-to-Interference-and-Noise-Ratio) interference model, such as spanner construction. Since a spanner can maintain a linear number of links while still preserving efficient routes for any pair of nodes in wireless networks, it is important to design distributed algorithms for spanners. Given a constantt>1 as the required stretch factor, the problem of our concern is to design an efficient distributed algorithm to construct a t-spanner of the communication graph under SINR such that the delay for the task completion is minimized, where the delay is the time interval between the time slot that the first node commences its operation to the time slot that all the nodes finish their task of constructing the t-spanner. Our main contributions include four aspects. First, we propose a proximity range and proximity independent set (PISet) to increase the number of nodes transmitting successfully at the same time in order to reduce the delay. Second, we develop a distributed randomized algorithm SINR-Spanner to construct a required t-spanner with high probability. Third, the approximation ratio of SINR-Spanner is proven to be a constant. Finally, extensive simulations are carried out to verify the effectiveness and efficiency of our proposed algorithm.


---

## Body

## 1. Introduction

The Internet of Things (IoT) has attracted great attention in recent years, owing to its potential military and civilian applications [1, 2]. Such a network generally consists of a large number of autonomous network nodes, in which algorithms are usually distributed since these algorithms have to work without global information and coordinated central control. Hence, there is an imperative need to design efficient distributed algorithms for various network optimization problems in the IoT.Constructing at-spanner with a minimum number of edges is one of the fundamental network optimization problems since the spanner property is a critical requirement of topology control in the IoT [3]. The IoT is commonly modeled as a graph GV,E, in which V is the set of wireless nodes and E represents the set of communication links (edges) connecting the nodes in V. A spanning subgraph H of G is called a t-spanner, for t≥1 if for all pairs of nodes u,v∈V, the length of the shortest path from u to v in H is at most t times of that in G. Here, t is called the stretch factor. A spanner can not only decrease the number of links and maintain connectivity but also ensure that the length of a path between any pair of communication nodes is within some constant factor from the shortest possible one. Therefore, constructing a spanner of the communication graph is enormously helpful for topology control, geographic routing, and compact routing in the IoT [3].Spanners have been extensively studied in computational geometry [4], in which GV,E is generally the complete Euclidean graph of the node set V in the Euclidean plane. However, even in the field of computational geometry, computing a minimum stretch factor spanner using not more than a given number of edges is NP-hard [5]. In the IoT, current spanner construction algorithms either do not consider interference, such as [6], or only handle it under the protocol interference model [7].However, when multiple nodes send messages at the same time, a node may be unable to receive the message from its given sender owing to the interference caused by simultaneous transmissions. Theprotocol interference model and the SINR (Signal-to-Interference-and-Noise-Ratio) interference model are the commonly used interference models. SINR can take into account cumulative interference of wireless communications and is more realistic [8], thus has been widely adopted now. However, designing and analyzing algorithms are challenging under the SINR model since each given receiver should compute accumulated interference generated by all other senders at the same time.


### 1.1. Outline of the Problem

In this paper, we consider a general case of constructing at-spanner under SINR, namely t-spanner-SINR. That is, given a constant t as the required stretch factor, our objective is to design an efficient distributed algorithm for constructing a t-spanner of the communication graph to minimize the delay of constructing the t-spanner. The delay of constructing a t-spanner is defined as the time interval from the start time-slot that nodes start to work to the last time-slot that all the nodes finish their task of constructing the t-spanner.A large scale IoT discussed in this work consists ofn sensor nodes, with uniform transmission powers, deployed randomly and uniformly in the two-dimensional Euclidean space. Nodes act in synchronous rounds; in every communication round, a node can transmit a message and attempt to receive a message. Each node initially knows only its own unique ID and its own coordinates. Since we adopt the SINR interference model when nodes communicate, the predesigned receivers can successfully decode the messages if and only if SINR constraints are satisfied. Owing to the accumulation and uncertainty of the SINR model, it is challenging to design a t-spanner distributed algorithm based on SINR in wireless networks. How to make more nodes transmit simultaneously and meanwhile make their given neighbor nodes successfully decode the messages is crucial to the performance of the algorithm under SINR.The authors in [9] proposed a distributed algorithm SINR-Undirected-YG under SINR and proved that the resultant graph is a t-spanner. Zhang et al. [9] claim to be able to construct a spanner at Ologn time-slots, but the running time of its algorithm is very large during the simulation. In this paper, we study a general case of constructing a t-spaner under SINR and try to reduce the delay.


### 1.2. Summary of Contributions

The summary of contributions of this paper is as follows:(1)
We identify the general case of constructing at-spanner under SINR (t-spanner-SINR problem), and we design an efficient distributed algorithm SINR-Spanner to construct a required t-spanner under SINR with high probability, i.e., with a probability of at least 1−e−n/4, where n is the total number of nodes in the network. Moreover, the resultant t-spanner has On edges(2)
Our distributed algorithm SINR-Spanner is also a local algorithm, in which the topology can be locally and self-adaptively maintained based on the information from the neighbor nodes without affecting the whole network. We reasonably utilize one kind of proximity graph—Yao graph (YG)—to construct spanner under SINR. YGs divide the surrounding area of each node intok sectors of equal angles and add edges only to the nearest neighbor within each sector [10]. If there are two or more nearest neighbors in a sector, one can choose the first neighbor receiving the message. In our design, each node is capable of independently performing successful local broadcasts to collect its neighborhood information within a certain range, such that it can get the nearest neighbor in each sector and the resultant t-spanner is a special YG(3)
We introduce the definition of proximity range and proximity-independent set (PISet) to increase the number of nodes transmitting successfully at the same time and to reduce the delay in the SINR-Spanner algorithm. The approximation ratio of SINR-Spanner is proven to be a constant(4)
Extensive simulations are carried out to verify the effectiveness and efficiency of our proposed distributed and randomized algorithmThe rest of this paper is organized as follows. Section2 reports the most related work. Section 3 precisely defines the formulation of the problem and introduces relevant models and notations. The spanner construction algorithm SINR-Spanner is presented in Section 4. Section 5 gives a theoretical analysis of the algorithm. In Section 6, we evaluate the performance of the algorithm via simulation. Section 7 concludes the paper with suggestions for future work.


## 1.1. Outline of the Problem

In this paper, we consider a general case of constructing at-spanner under SINR, namely t-spanner-SINR. That is, given a constant t as the required stretch factor, our objective is to design an efficient distributed algorithm for constructing a t-spanner of the communication graph to minimize the delay of constructing the t-spanner. The delay of constructing a t-spanner is defined as the time interval from the start time-slot that nodes start to work to the last time-slot that all the nodes finish their task of constructing the t-spanner.A large scale IoT discussed in this work consists ofn sensor nodes, with uniform transmission powers, deployed randomly and uniformly in the two-dimensional Euclidean space. Nodes act in synchronous rounds; in every communication round, a node can transmit a message and attempt to receive a message. Each node initially knows only its own unique ID and its own coordinates. Since we adopt the SINR interference model when nodes communicate, the predesigned receivers can successfully decode the messages if and only if SINR constraints are satisfied. Owing to the accumulation and uncertainty of the SINR model, it is challenging to design a t-spanner distributed algorithm based on SINR in wireless networks. How to make more nodes transmit simultaneously and meanwhile make their given neighbor nodes successfully decode the messages is crucial to the performance of the algorithm under SINR.The authors in [9] proposed a distributed algorithm SINR-Undirected-YG under SINR and proved that the resultant graph is a t-spanner. Zhang et al. [9] claim to be able to construct a spanner at Ologn time-slots, but the running time of its algorithm is very large during the simulation. In this paper, we study a general case of constructing a t-spaner under SINR and try to reduce the delay.


## 1.2. Summary of Contributions

The summary of contributions of this paper is as follows:(1)
We identify the general case of constructing at-spanner under SINR (t-spanner-SINR problem), and we design an efficient distributed algorithm SINR-Spanner to construct a required t-spanner under SINR with high probability, i.e., with a probability of at least 1−e−n/4, where n is the total number of nodes in the network. Moreover, the resultant t-spanner has On edges(2)
Our distributed algorithm SINR-Spanner is also a local algorithm, in which the topology can be locally and self-adaptively maintained based on the information from the neighbor nodes without affecting the whole network. We reasonably utilize one kind of proximity graph—Yao graph (YG)—to construct spanner under SINR. YGs divide the surrounding area of each node intok sectors of equal angles and add edges only to the nearest neighbor within each sector [10]. If there are two or more nearest neighbors in a sector, one can choose the first neighbor receiving the message. In our design, each node is capable of independently performing successful local broadcasts to collect its neighborhood information within a certain range, such that it can get the nearest neighbor in each sector and the resultant t-spanner is a special YG(3)
We introduce the definition of proximity range and proximity-independent set (PISet) to increase the number of nodes transmitting successfully at the same time and to reduce the delay in the SINR-Spanner algorithm. The approximation ratio of SINR-Spanner is proven to be a constant(4)
Extensive simulations are carried out to verify the effectiveness and efficiency of our proposed distributed and randomized algorithmThe rest of this paper is organized as follows. Section2 reports the most related work. Section 3 precisely defines the formulation of the problem and introduces relevant models and notations. The spanner construction algorithm SINR-Spanner is presented in Section 4. Section 5 gives a theoretical analysis of the algorithm. In Section 6, we evaluate the performance of the algorithm via simulation. Section 7 concludes the paper with suggestions for future work.


## 2. Related Work

In this section, we first investigate the spanner algorithms in computational geometry and in the IoT, then discuss the method of applying randomized and distributed solutions under SINR.


### 2.1.t-Spanner

The book [4] by Narasimhan and Smid is a comprehensive overview of geometric spanners. For geometric spanners, several structures and methods have been proposed, such as the Greedy method [11], Well-Separated Pair Decomposition method, Delaunay triangulation, θ-graphs, and YGs. Constructing YGs is one of the simplest ways of constructing t-spanners. Yao [10] used YGs to simplify the computation of the Euclidean minimum spanning tree. Althöfer et al. [11] firstly proved that YGs are the t-spanners for the corresponding complete graph. For the corresponding complete graph, YGs are 1/1−2sinπ/k-spanners with k>6 [12].In wireless networks, the spanner property was first discussed by Li et al. in [6]. They modeled the network as a unit disk graph (UDG) and analyzed the energy stretch factor of several common subgraphs of a UDG: n−1 for the relative neighborhood graph (RNG), 1 for the Gabriel graph (GG), and O1 for YG. And these proximity graphs have been widely used in spanner construction as subgraphs of a UDG. There also exist spanner construction mechanisms for quasi-unit disk graphs, disk graphs, and unit ball graphs [13]. In [14], Kothapalli et al. proposed a local-control protocol for establishing a constant density spanner among a set of mobile stations. The LISE (low interference spanner establisher) algorithm was presented to establish a spanner in [7], where the interference definition is based on how many nodes are affected by the communication over a certain link. However, since the above spanner algorithms for wireless networks are all studied without considering interference or handling interference under the protocol interference model, they cannot deal with interference effectively under the SINR interference model. Zhang et al. [9] first consider spanner construction under SINR, and this work improves it.Constructing spanners under a computational geometry field greatly promotes the study under the wireless network setting. Meanwhile, wireless network requirements, which generally need to efficiently satisfy various topological characteristics, encourage the development of geometric spanner construction. Recent results on sparse geometric spanners focused on satisfying one or multiple topological characteristics such as lightness, small degree [15], fault tolerance, no central agent [16], and multiple characteristics [17].


### 2.2. SINR Model

In wireless networks, the SINR model received increasing attention [8]. Despite the vast amount of researches in the design and analysis of centralized algorithms under SINR [18], few results are known about distributed solutions in this model, especially for global communication tasks, owing to the accumulation and uncertainty of interference.There is a growing interest in developing randomized distributed solutions to local broadcast [19], which is defined as successfully transmitting a message to all neighbors in the corresponding reachable proximity of a node. Randomized distributed solutions to local broadcast are often used as a building block for global communication tasks, such as multiple-message broadcast [20], synchronization [21], and multiple channels broadcast [22]. In [20], selected leader nodes adopt local broadcast to collect the messages that arrive at their dominated nonleader nodes and then disseminate the received messages to the whole network. The algorithm in [21] starts from very low probabilities and increases them gradually until nodes can hear a reasonable number of messages and implement all nodes’ clock synchronization. In [22], the selected leader in different channel collects locally the messages of its dominated nonleader nodes in the same channel to speedup multiple channel broadcast. Note that most of the existing distributed and randomized works under SINR are still in the theoretical stage except [19] and Fuchs’s coloring study, such as [23]. Using local broadcasting as a basic unit, we propose an algorithm of spanner construction in this paper and perform simulations to verify the performance of the algorithm.


## 2.1.t-Spanner

The book [4] by Narasimhan and Smid is a comprehensive overview of geometric spanners. For geometric spanners, several structures and methods have been proposed, such as the Greedy method [11], Well-Separated Pair Decomposition method, Delaunay triangulation, θ-graphs, and YGs. Constructing YGs is one of the simplest ways of constructing t-spanners. Yao [10] used YGs to simplify the computation of the Euclidean minimum spanning tree. Althöfer et al. [11] firstly proved that YGs are the t-spanners for the corresponding complete graph. For the corresponding complete graph, YGs are 1/1−2sinπ/k-spanners with k>6 [12].In wireless networks, the spanner property was first discussed by Li et al. in [6]. They modeled the network as a unit disk graph (UDG) and analyzed the energy stretch factor of several common subgraphs of a UDG: n−1 for the relative neighborhood graph (RNG), 1 for the Gabriel graph (GG), and O1 for YG. And these proximity graphs have been widely used in spanner construction as subgraphs of a UDG. There also exist spanner construction mechanisms for quasi-unit disk graphs, disk graphs, and unit ball graphs [13]. In [14], Kothapalli et al. proposed a local-control protocol for establishing a constant density spanner among a set of mobile stations. The LISE (low interference spanner establisher) algorithm was presented to establish a spanner in [7], where the interference definition is based on how many nodes are affected by the communication over a certain link. However, since the above spanner algorithms for wireless networks are all studied without considering interference or handling interference under the protocol interference model, they cannot deal with interference effectively under the SINR interference model. Zhang et al. [9] first consider spanner construction under SINR, and this work improves it.Constructing spanners under a computational geometry field greatly promotes the study under the wireless network setting. Meanwhile, wireless network requirements, which generally need to efficiently satisfy various topological characteristics, encourage the development of geometric spanner construction. Recent results on sparse geometric spanners focused on satisfying one or multiple topological characteristics such as lightness, small degree [15], fault tolerance, no central agent [16], and multiple characteristics [17].


## 2.2. SINR Model

In wireless networks, the SINR model received increasing attention [8]. Despite the vast amount of researches in the design and analysis of centralized algorithms under SINR [18], few results are known about distributed solutions in this model, especially for global communication tasks, owing to the accumulation and uncertainty of interference.There is a growing interest in developing randomized distributed solutions to local broadcast [19], which is defined as successfully transmitting a message to all neighbors in the corresponding reachable proximity of a node. Randomized distributed solutions to local broadcast are often used as a building block for global communication tasks, such as multiple-message broadcast [20], synchronization [21], and multiple channels broadcast [22]. In [20], selected leader nodes adopt local broadcast to collect the messages that arrive at their dominated nonleader nodes and then disseminate the received messages to the whole network. The algorithm in [21] starts from very low probabilities and increases them gradually until nodes can hear a reasonable number of messages and implement all nodes’ clock synchronization. In [22], the selected leader in different channel collects locally the messages of its dominated nonleader nodes in the same channel to speedup multiple channel broadcast. Note that most of the existing distributed and randomized works under SINR are still in the theoretical stage except [19] and Fuchs’s coloring study, such as [23]. Using local broadcasting as a basic unit, we propose an algorithm of spanner construction in this paper and perform simulations to verify the performance of the algorithm.


## 3. Model and Problem Formulations

Assume that a setV of n wireless network nodes, modeled as a graph G, is deployed randomly and uniformly in a 2-dimensional geographic plane. Nodes act in synchronous rounds. Each node is conscious of its ID and coordinates and has the same transmission power P (P>0). Let the Euclidean distance for the two endpoints u and v, denoted by duv, be the length of an edge in G. And let duvG be the length of the shortest path between u and v in G which is defined as the sum of the lengths of its edges.A commonly assumed model for the propagation effect of wireless nodes is deterministic path loss, i.e.,Pr=P/duvα, where u transmits a message to v, Pr is the received power at a receiver v, and α is the path loss exponent (typically, 2<α≤6). A deterministic path loss model is applied to the following interference model.


### 3.1. SINR (Signal-to-Interference-and-Noise-Ratio) Interference Model

In the SINR model, a transmission from nodeu to node v is successful iff the SINR condition holds:
(1)P/duvαN+∑w∈T\uP/dwvα≥β,where T⊆V is the set of transmitting nodes, α∈2,6 is the path loss exponent depending on the network environment, β>1 is a hardware-defined threshold, and N is the environmental noise.The transmission rangeRmax of a node u is the maximum distance at which a node v can receive a clear transmission from u while no other node is transmitting at the same time, i.e., ∑w∈T\uP/dwvα=0. The SINR condition (1) tells us that
(2)Rmax=P/Nβ1/α,for the given power level P. Note that Rmax is for only one node u transmitting in the whole network at the time slot.


### 3.2. Local Broadcasting Range (Rb)

We set the local broadcasting range(3)Rb=1−εRmax,where 0≤ε<1 is a fixed model parameter.We say a node transmitsRb successfully in a time slot if it transmits a message, and this message is received by all its neighbors in a distance smaller or equal to Rb in the time slot. In Section 4, we define the proximity range Rp such that the nodes which are in a distance greater or equal to Rp can transmit Rb successfully at the same time slot.We denote the region withinRb of node u as a local broadcasting region Bu and the number of nodes in it as Δub. Furthermore, let Δb=maxu∈VΔub.


### 3.3. Communication Graph

The communication graphGRbV,ERb of a given network consists of all network nodes and edges u,v such that duv≤Rb. Since Rmax is for only one transmission in the whole network at the same time, we adopt a slightly smaller range Rb as [22] which suffice for practical communication. In the communication graph GRbV,ERb, which is simply denoted by GRbV, a node v is a neighbor of node u if duv≤Rb.


### 3.4. Yao Graph (YG)

The directed Yao graphYG→kV with a fixed integer parameter k>0 is defined as follows. Any k equally separated rays starting at the origin node define k sectors. The orientation of the cut is identical for all nodes. Translate the sectors to each node u∈V. In each sector with a node u, pick the shortest directed edge u,v, if there is one, to YG→kV. Ties are broken arbitrarily.This implies thatYG→kV preserves the shortest outcoming edge in each sector. Accordingly, YG←kV preserves the shortest incoming edge in each sector.An undirected Yao graph, in which the edge directions are ignored, is denoted byYGkV. YGkRbV is the Yao graph in which only the edges whose lengths are no more than Rb are preserved from YGkV. In other words, YGkV is the spanning subgraph of a complete Euclidean graph KnV on node set V and YGkRbV is the spanning subgraph of GRbV.


### 3.5.t-Spanner

Lett>1 be a real number. A spanning subgraph HV,EH of GV,E is said to be a t-spanner of G, if for any two nodes u and v in V, the shortest path between u and v in H, whose length is at most t times that of the shortest path in G, i.e.,
(4)duvH≤t·duvG.The constantt is called the stretch factor of H (w.r.t. G). Note that G can be KnV or a communication graph that is a spanning subgraph of KnV.


### 3.6. Delay of Constructing at-Spanner

The delay of constructing at-spanner is defined as the time interval from the start time slot that the first node starts to work to the last time slot that all the nodes finish their task of constructing the t-spanner.Next, we present the definition of the problem, thet-spanner under the SINR problem, which is our focus in this paper.


### 3.7.t-Spanner under the SINR Problem (t-Spanner-SINR)

Assume that a setV of n wireless network nodes deployed randomly and uniformly in a 2-dimensional geographic plane, in which each node is aware of its ID and coordinates, has the same transmission power P (P>0) and a local broadcasting range Rb; given a constant t>1, the goal is to design a distributed algorithm to find a t-spanner of the corresponding communication graph GRbV,ERb under SINR, such that the delay of constructing a t-spanner is minimized.


## 3.1. SINR (Signal-to-Interference-and-Noise-Ratio) Interference Model

In the SINR model, a transmission from nodeu to node v is successful iff the SINR condition holds:
(1)P/duvαN+∑w∈T\uP/dwvα≥β,where T⊆V is the set of transmitting nodes, α∈2,6 is the path loss exponent depending on the network environment, β>1 is a hardware-defined threshold, and N is the environmental noise.The transmission rangeRmax of a node u is the maximum distance at which a node v can receive a clear transmission from u while no other node is transmitting at the same time, i.e., ∑w∈T\uP/dwvα=0. The SINR condition (1) tells us that
(2)Rmax=P/Nβ1/α,for the given power level P. Note that Rmax is for only one node u transmitting in the whole network at the time slot.


## 3.2. Local Broadcasting Range (Rb)

We set the local broadcasting range(3)Rb=1−εRmax,where 0≤ε<1 is a fixed model parameter.We say a node transmitsRb successfully in a time slot if it transmits a message, and this message is received by all its neighbors in a distance smaller or equal to Rb in the time slot. In Section 4, we define the proximity range Rp such that the nodes which are in a distance greater or equal to Rp can transmit Rb successfully at the same time slot.We denote the region withinRb of node u as a local broadcasting region Bu and the number of nodes in it as Δub. Furthermore, let Δb=maxu∈VΔub.


## 3.3. Communication Graph

The communication graphGRbV,ERb of a given network consists of all network nodes and edges u,v such that duv≤Rb. Since Rmax is for only one transmission in the whole network at the same time, we adopt a slightly smaller range Rb as [22] which suffice for practical communication. In the communication graph GRbV,ERb, which is simply denoted by GRbV, a node v is a neighbor of node u if duv≤Rb.


## 3.4. Yao Graph (YG)

The directed Yao graphYG→kV with a fixed integer parameter k>0 is defined as follows. Any k equally separated rays starting at the origin node define k sectors. The orientation of the cut is identical for all nodes. Translate the sectors to each node u∈V. In each sector with a node u, pick the shortest directed edge u,v, if there is one, to YG→kV. Ties are broken arbitrarily.This implies thatYG→kV preserves the shortest outcoming edge in each sector. Accordingly, YG←kV preserves the shortest incoming edge in each sector.An undirected Yao graph, in which the edge directions are ignored, is denoted byYGkV. YGkRbV is the Yao graph in which only the edges whose lengths are no more than Rb are preserved from YGkV. In other words, YGkV is the spanning subgraph of a complete Euclidean graph KnV on node set V and YGkRbV is the spanning subgraph of GRbV.


## 3.5.t-Spanner

Lett>1 be a real number. A spanning subgraph HV,EH of GV,E is said to be a t-spanner of G, if for any two nodes u and v in V, the shortest path between u and v in H, whose length is at most t times that of the shortest path in G, i.e.,
(4)duvH≤t·duvG.The constantt is called the stretch factor of H (w.r.t. G). Note that G can be KnV or a communication graph that is a spanning subgraph of KnV.


## 3.6. Delay of Constructing at-Spanner

The delay of constructing at-spanner is defined as the time interval from the start time slot that the first node starts to work to the last time slot that all the nodes finish their task of constructing the t-spanner.Next, we present the definition of the problem, thet-spanner under the SINR problem, which is our focus in this paper.


## 3.7.t-Spanner under the SINR Problem (t-Spanner-SINR)

Assume that a setV of n wireless network nodes deployed randomly and uniformly in a 2-dimensional geographic plane, in which each node is aware of its ID and coordinates, has the same transmission power P (P>0) and a local broadcasting range Rb; given a constant t>1, the goal is to design a distributed algorithm to find a t-spanner of the corresponding communication graph GRbV,ERb under SINR, such that the delay of constructing a t-spanner is minimized.


## 4. Algorithm

### 4.1. Algorithm Outline

The main idea of our algorithm is to constructYGkV for the t-spanner-SINR problem. The reason is that the YGkV graph is a t=1/1−2sinπ/k-spanner [9]. Consequently, given a constant t>1, we compute a k and construct YGkV under SINR in our distributed algorithm to get the required t-spanner.To constructYGkV, each node u needs the node v’s information which is the closest to u in the sector v belongs. Accordingly, each node should locally broadcast its ID and coordinates to its neighbors. However, if all the nodes transmit together under SINR, no node will receive any message owing to the interference. To avoid collision, each node could locally broadcast one by one. However, in a distributed algorithm, there is not a centralized coordination for arranging nodes to transmit in sequence. Accordingly, each node can only transmit with the probability 1/n. Furthermore, in order to reduce the delay, it has an obligation to have as many nodes as possible to transmit simultaneously. Therefore, each node will make a range as the radius of its neighborhood circle region and next take the inverse of the number of nodes in its neighborhood circle region as the sending probability.First, we will compute the range and give the node set in which all nodes can transmit simultaneously.


### 4.2. Proximity Range and Proximity Independent Set (PISet)

How to make more nodes transmit simultaneously and meanwhile make their neighbor nodes successfully decode the messages is crucial for the performance of the algorithms under SINR. Thus, we define the proximity rangeRp such that any nodes u and v can transmit simultaneously if duv≥Rp. Intuitively, a tiny Rp implies a high degree of channel utilization. We examine how to set a proper Rp to guarantee SINR threshold and meanwhile the highest channel utilization degree. For clarity, we define the proximity range and proximity independent set as follows.


#### 4.2.1. Proximity RangeRp and the Corresponding Proximity Independent Set PISetp

Proximity rangeRp is a length, and a PISetp is a subset of V that satisfies duv≥Rp for ∀u,v∈PISetpu≠v. A PISetp is maximal if and only if duw<Rp for ∀u∈PISetp and ∀w∉PISetp. How to design Rp? The basic idea underlying the design is to ensure the nodes in the same PISetp transmit simultaneously and all their neighbors receive the message successfully.We refer to the region withinRp of node u as proximity region Xu and the number of nodes in it as Δup. Besides, let Δp=maxu∈VΔup.Before designingRp, we first give an example for Rp and PISetp. Rp and PISetp are illustrated in Figure 1 where 19 nodes represented by solid circles are in the same PISetp. Note that this PISetp is maximal. The distance between the given receiver v with the sender u and the nearest of other senders, which is w in Figure 1, is at least Rp−Rb. In other words, dwv≥Rp−Rb in Figure 1.Figure 1
Proximity rangeRp and a corresponding PISetp.By observing the above example, we give the specific relationship betweenRp and Rb in the following theorem.Theorem 1.
Suppose thatRp=c2·β·c1/c1−11/α·Rb+Rb where c1=1/1−εα>1 and c2=6+π2−63/2−α, the nodes in the same PISetp can transmit Rb successfully at the same time slot.Proof.
LetI=Rp−Rb. We begin by estimating the smallest value of I when u transmits to v successfully and u transmits simultaneously with other nodes in the same PISetp. Further, we prove that the nodes in the same PISetp can transmit Rb successfully at the same time slot with the above I. We say a node transmits Rb successfully in a time slot if it transmits a message and this message is received by all its neighbors in a distance smaller or equal to Rb in the time slot.
In order forv to be able to receive the message from u, we require SINRuv≥β.
Thus,(5)P/duvαN+∑w∈PISetp\uP/dwvα≥β.
Since the equations (2) and (3), N=P/c1βRbα where c1=1/1−εα is a fixed parameter.
Now(6)P/duvαN+∑w∈PISetp\uP/dwvα=P/duvαP/c1βRbα+∑w∈PISetp\uP/dwvα=duv−αRb−α/c1β+∑w∈PISetp\udwv−α.
We derive the lower bound of the above formula. First,duv−α≥Rb−α since Rb is the maximum local broadcasting range of a node. Furthermore, if a node w transmit together with u as shown in Figure 1, w produces the largest interference when w and the given receiver v have the closest distance I. If we represent a link as a node as shown in Figure 2(a), for the nodes in the PISetp, the densest packing of interfering links is the hexagon packing [24] with edge length I as shown in Figure 2(b). There are at most six nodes in the first layer, and the distance is I with respect to the abstracting node uv. Furthermore, the distance between uv and any node in the lth l≥2 layer is no less than 3/2lI with the lth layer having at most 6l nodes.
(7)∑w∈PISetp\udwv−α≤6·I−α+∑l≥26l·32lI−α=6·I−α+6·32I−α·∑l≥2l−α+1.
Since∑l≥2l−α+1=ζα−1−1, where ζ· is the Riemann zeta function, considering that α≥3, then ζα−1≤ζ2=π2/6. Thus, we have
(8)∑w∈PISetp\udwv−α≤6·I−α+6·32I−α·π26−1=6+π2−632−α·I−α=c2·I−α,where c2=6+π2−63/2−α.
Therefore, to makeduv−α/Rb−α/c1β+∑w∈PISetp\udwv−α≥β valid, it is sufficient to have
(9)Rb−αRb−α/c1β+c2I−α≥β.
Therefore,I≥c2·β·c1/c1−11/α·Rb.
Hence,Rp=c2·β·c1/c1−11/α·Rb+Rb, where c1=1/1−εα>1 and c2=6+π2−63/2−α.Figure 2
Link abstraction and the densest packing of interfering links.
(a)(b)Conversely, ifRp have the value as shown in the above, the nodes in the same PISetp, which is maximal as shown in Figure 1 or not maximal, can transmit Rb successfully at the same time slot since the receiver power is no less than P·Rb−α in (9) and the cumulative interference is less than P·c2I−α.Figure3 depicts visually the relation between proximity range Rp and local broadcasting range Rb with different α, β, and ε, which is helpful to pick these values during subsequent algorithm simulation. These parameters are reasonably set as follows: the path loss exponent α∈3,4,5,6, the threshold β∈1,10, and ε∈0.4,0.95. From Figure 3, one can see that Rp increases when α decreases, β increases, and ε decreases. So we can get that Rp is as about 2.57 times at a minimum as Rb when α=6, β=1, and ε=0.95, while Rp is as about 6.34 times at a maximum as Rb when α=3, β=10, and ε=0.4.Figure 3
Rp vs. α, β, and ε.
(a)(b)(c)


### 4.3. Algorithm

From the above Theorem1, the nodes in the same PISetp can transmit Rb successfully at the same time slot while each node takes the value of Rp as Theorem 1, so the sending probability for each node u is set to the inverse of the number of nodes in its proximity region Δup. Thus, we guess all its neighbors can receive the message successfully with high probability, and we will give the proof in the next section. The pseudo-code for node u is given in Algorithm 1, which implies that each node runs it independently.Algorithm 1: SINR-Spanner(u).
1: Initialize the stretch factort;2: Initializek=π/arcsint−1/2t;3: Compute the number of nodes in its proximity region, i.e.,Δup;4: Initializepu=1/Δup;5: InitializeIui=−1 for i=1,2,⋯,k;6:forj=1 to Δp time-slots do7: Send a message containing its IDu and coordinates with probability pu, and remains listening with probability 1−pu;8:while receiving a message from some node vdo9:i= the index of the sector to which v belongs;10:ifIui==−1 or the distance dIuiu>dvuthen11:Iui=v12end if13:end while14:end for15:←Eu=∅;16:fori=1 to kdo17:ifIui≠−1then18:Eu←=Eu←∪Iui,u;19:end if20:end for21:Eu=u,v∣v,u∈Eu←;22:fori=1 to Δp time-slots do23: Broadcast the incoming neighbor set with probabilitypu;24:while receiving a message from some node vdo25:ifu is the incoming neighbor of v and u,v∉Euthen26:Eu=Eu∪u,v;27:end if28:end while29:end forNow, we describe the full operation of our distributed algorithm SINR-Spanner. Each nodeu carries out the same operations and has its local memory. The algorithm consists of three parts. In part 1 (line 1-line 5), each node performs initialization work. Each node u first computes the required number of sectors depending on the given stretch factor t. Then, each node u takes the inverse of Δup as the sending probability. Thus how to obtain Δupa priori is critical to our algorithm design. Some existing works, such as [19, 23], assume the availability of Δup to facilitate the algorithm design and analysis. Such requirements are common under SINR in order to enable initial communication. Therefore, in our algorithm, we also assume that Δup is available to simplify the presentation. In part 2 (line 6-line 20), each node obtains the incoming neighbor in each sector by receiving the neighbors’ messages, and thus, a directed Yao graph forms. Figure 4 shows an intermediate result after part 2 in which there are 6 nodes; the edge length is at most Rb and k=7. Here, Ev1→=v3,v1v2,v1, Ev2→=v1,v2v3,v2v4,v2, Ev3→=v2,v3, and so on. In part 3 (line 21-line 29), each node sends an acknowledgement message back to its incoming neighbor, and thus, an undirected Yao graph is constructed which is a t-spanner we require. An example of YGkRbV is presented in Figure 5, in which edge directions are ignored from the graph shown in Figure 4. Here, Ev1=v1,v2,v1,v3, Ev2=v2,v1,v2,v3,v2,v4, Ev3=v3,v1,v3,v2, and so on. Ev1 has local data v1,v3, and Ev3 has local data v3,v1; thus, the undirected edge v1,v3 is known by two endpoints.Figure 4
YG←kRbV after part 2, where k=7.Figure 5
YGkRbV after part 3, where k=7.Our distributed and randomized algorithm SINR-Spanner, which is different from the algorithms in [9], can solve the t-spanner-SINR problem. In part 1, the algorithm first initializes the stretch factor t to attain a t-spanner. The sending probability for each node u is set to the inverse of Δup to reduce the delay; then, u repeats randomized transmission for 8Δp time slots, respectively, in part 2 and part 3.


## 4.1. Algorithm Outline

The main idea of our algorithm is to constructYGkV for the t-spanner-SINR problem. The reason is that the YGkV graph is a t=1/1−2sinπ/k-spanner [9]. Consequently, given a constant t>1, we compute a k and construct YGkV under SINR in our distributed algorithm to get the required t-spanner.To constructYGkV, each node u needs the node v’s information which is the closest to u in the sector v belongs. Accordingly, each node should locally broadcast its ID and coordinates to its neighbors. However, if all the nodes transmit together under SINR, no node will receive any message owing to the interference. To avoid collision, each node could locally broadcast one by one. However, in a distributed algorithm, there is not a centralized coordination for arranging nodes to transmit in sequence. Accordingly, each node can only transmit with the probability 1/n. Furthermore, in order to reduce the delay, it has an obligation to have as many nodes as possible to transmit simultaneously. Therefore, each node will make a range as the radius of its neighborhood circle region and next take the inverse of the number of nodes in its neighborhood circle region as the sending probability.First, we will compute the range and give the node set in which all nodes can transmit simultaneously.


## 4.2. Proximity Range and Proximity Independent Set (PISet)

How to make more nodes transmit simultaneously and meanwhile make their neighbor nodes successfully decode the messages is crucial for the performance of the algorithms under SINR. Thus, we define the proximity rangeRp such that any nodes u and v can transmit simultaneously if duv≥Rp. Intuitively, a tiny Rp implies a high degree of channel utilization. We examine how to set a proper Rp to guarantee SINR threshold and meanwhile the highest channel utilization degree. For clarity, we define the proximity range and proximity independent set as follows.


### 4.2.1. Proximity RangeRp and the Corresponding Proximity Independent Set PISetp

Proximity rangeRp is a length, and a PISetp is a subset of V that satisfies duv≥Rp for ∀u,v∈PISetpu≠v. A PISetp is maximal if and only if duw<Rp for ∀u∈PISetp and ∀w∉PISetp. How to design Rp? The basic idea underlying the design is to ensure the nodes in the same PISetp transmit simultaneously and all their neighbors receive the message successfully.We refer to the region withinRp of node u as proximity region Xu and the number of nodes in it as Δup. Besides, let Δp=maxu∈VΔup.Before designingRp, we first give an example for Rp and PISetp. Rp and PISetp are illustrated in Figure 1 where 19 nodes represented by solid circles are in the same PISetp. Note that this PISetp is maximal. The distance between the given receiver v with the sender u and the nearest of other senders, which is w in Figure 1, is at least Rp−Rb. In other words, dwv≥Rp−Rb in Figure 1.Figure 1
Proximity rangeRp and a corresponding PISetp.By observing the above example, we give the specific relationship betweenRp and Rb in the following theorem.Theorem 1.
Suppose thatRp=c2·β·c1/c1−11/α·Rb+Rb where c1=1/1−εα>1 and c2=6+π2−63/2−α, the nodes in the same PISetp can transmit Rb successfully at the same time slot.Proof.
LetI=Rp−Rb. We begin by estimating the smallest value of I when u transmits to v successfully and u transmits simultaneously with other nodes in the same PISetp. Further, we prove that the nodes in the same PISetp can transmit Rb successfully at the same time slot with the above I. We say a node transmits Rb successfully in a time slot if it transmits a message and this message is received by all its neighbors in a distance smaller or equal to Rb in the time slot.
In order forv to be able to receive the message from u, we require SINRuv≥β.
Thus,(5)P/duvαN+∑w∈PISetp\uP/dwvα≥β.
Since the equations (2) and (3), N=P/c1βRbα where c1=1/1−εα is a fixed parameter.
Now(6)P/duvαN+∑w∈PISetp\uP/dwvα=P/duvαP/c1βRbα+∑w∈PISetp\uP/dwvα=duv−αRb−α/c1β+∑w∈PISetp\udwv−α.
We derive the lower bound of the above formula. First,duv−α≥Rb−α since Rb is the maximum local broadcasting range of a node. Furthermore, if a node w transmit together with u as shown in Figure 1, w produces the largest interference when w and the given receiver v have the closest distance I. If we represent a link as a node as shown in Figure 2(a), for the nodes in the PISetp, the densest packing of interfering links is the hexagon packing [24] with edge length I as shown in Figure 2(b). There are at most six nodes in the first layer, and the distance is I with respect to the abstracting node uv. Furthermore, the distance between uv and any node in the lth l≥2 layer is no less than 3/2lI with the lth layer having at most 6l nodes.
(7)∑w∈PISetp\udwv−α≤6·I−α+∑l≥26l·32lI−α=6·I−α+6·32I−α·∑l≥2l−α+1.
Since∑l≥2l−α+1=ζα−1−1, where ζ· is the Riemann zeta function, considering that α≥3, then ζα−1≤ζ2=π2/6. Thus, we have
(8)∑w∈PISetp\udwv−α≤6·I−α+6·32I−α·π26−1=6+π2−632−α·I−α=c2·I−α,where c2=6+π2−63/2−α.
Therefore, to makeduv−α/Rb−α/c1β+∑w∈PISetp\udwv−α≥β valid, it is sufficient to have
(9)Rb−αRb−α/c1β+c2I−α≥β.
Therefore,I≥c2·β·c1/c1−11/α·Rb.
Hence,Rp=c2·β·c1/c1−11/α·Rb+Rb, where c1=1/1−εα>1 and c2=6+π2−63/2−α.Figure 2
Link abstraction and the densest packing of interfering links.
(a)(b)Conversely, ifRp have the value as shown in the above, the nodes in the same PISetp, which is maximal as shown in Figure 1 or not maximal, can transmit Rb successfully at the same time slot since the receiver power is no less than P·Rb−α in (9) and the cumulative interference is less than P·c2I−α.Figure3 depicts visually the relation between proximity range Rp and local broadcasting range Rb with different α, β, and ε, which is helpful to pick these values during subsequent algorithm simulation. These parameters are reasonably set as follows: the path loss exponent α∈3,4,5,6, the threshold β∈1,10, and ε∈0.4,0.95. From Figure 3, one can see that Rp increases when α decreases, β increases, and ε decreases. So we can get that Rp is as about 2.57 times at a minimum as Rb when α=6, β=1, and ε=0.95, while Rp is as about 6.34 times at a maximum as Rb when α=3, β=10, and ε=0.4.Figure 3
Rp vs. α, β, and ε.
(a)(b)(c)


## 4.2.1. Proximity RangeRp and the Corresponding Proximity Independent Set PISetp

Proximity rangeRp is a length, and a PISetp is a subset of V that satisfies duv≥Rp for ∀u,v∈PISetpu≠v. A PISetp is maximal if and only if duw<Rp for ∀u∈PISetp and ∀w∉PISetp. How to design Rp? The basic idea underlying the design is to ensure the nodes in the same PISetp transmit simultaneously and all their neighbors receive the message successfully.We refer to the region withinRp of node u as proximity region Xu and the number of nodes in it as Δup. Besides, let Δp=maxu∈VΔup.Before designingRp, we first give an example for Rp and PISetp. Rp and PISetp are illustrated in Figure 1 where 19 nodes represented by solid circles are in the same PISetp. Note that this PISetp is maximal. The distance between the given receiver v with the sender u and the nearest of other senders, which is w in Figure 1, is at least Rp−Rb. In other words, dwv≥Rp−Rb in Figure 1.Figure 1
Proximity rangeRp and a corresponding PISetp.By observing the above example, we give the specific relationship betweenRp and Rb in the following theorem.Theorem 1.
Suppose thatRp=c2·β·c1/c1−11/α·Rb+Rb where c1=1/1−εα>1 and c2=6+π2−63/2−α, the nodes in the same PISetp can transmit Rb successfully at the same time slot.Proof.
LetI=Rp−Rb. We begin by estimating the smallest value of I when u transmits to v successfully and u transmits simultaneously with other nodes in the same PISetp. Further, we prove that the nodes in the same PISetp can transmit Rb successfully at the same time slot with the above I. We say a node transmits Rb successfully in a time slot if it transmits a message and this message is received by all its neighbors in a distance smaller or equal to Rb in the time slot.
In order forv to be able to receive the message from u, we require SINRuv≥β.
Thus,(5)P/duvαN+∑w∈PISetp\uP/dwvα≥β.
Since the equations (2) and (3), N=P/c1βRbα where c1=1/1−εα is a fixed parameter.
Now(6)P/duvαN+∑w∈PISetp\uP/dwvα=P/duvαP/c1βRbα+∑w∈PISetp\uP/dwvα=duv−αRb−α/c1β+∑w∈PISetp\udwv−α.
We derive the lower bound of the above formula. First,duv−α≥Rb−α since Rb is the maximum local broadcasting range of a node. Furthermore, if a node w transmit together with u as shown in Figure 1, w produces the largest interference when w and the given receiver v have the closest distance I. If we represent a link as a node as shown in Figure 2(a), for the nodes in the PISetp, the densest packing of interfering links is the hexagon packing [24] with edge length I as shown in Figure 2(b). There are at most six nodes in the first layer, and the distance is I with respect to the abstracting node uv. Furthermore, the distance between uv and any node in the lth l≥2 layer is no less than 3/2lI with the lth layer having at most 6l nodes.
(7)∑w∈PISetp\udwv−α≤6·I−α+∑l≥26l·32lI−α=6·I−α+6·32I−α·∑l≥2l−α+1.
Since∑l≥2l−α+1=ζα−1−1, where ζ· is the Riemann zeta function, considering that α≥3, then ζα−1≤ζ2=π2/6. Thus, we have
(8)∑w∈PISetp\udwv−α≤6·I−α+6·32I−α·π26−1=6+π2−632−α·I−α=c2·I−α,where c2=6+π2−63/2−α.
Therefore, to makeduv−α/Rb−α/c1β+∑w∈PISetp\udwv−α≥β valid, it is sufficient to have
(9)Rb−αRb−α/c1β+c2I−α≥β.
Therefore,I≥c2·β·c1/c1−11/α·Rb.
Hence,Rp=c2·β·c1/c1−11/α·Rb+Rb, where c1=1/1−εα>1 and c2=6+π2−63/2−α.Figure 2
Link abstraction and the densest packing of interfering links.
(a)(b)Conversely, ifRp have the value as shown in the above, the nodes in the same PISetp, which is maximal as shown in Figure 1 or not maximal, can transmit Rb successfully at the same time slot since the receiver power is no less than P·Rb−α in (9) and the cumulative interference is less than P·c2I−α.Figure3 depicts visually the relation between proximity range Rp and local broadcasting range Rb with different α, β, and ε, which is helpful to pick these values during subsequent algorithm simulation. These parameters are reasonably set as follows: the path loss exponent α∈3,4,5,6, the threshold β∈1,10, and ε∈0.4,0.95. From Figure 3, one can see that Rp increases when α decreases, β increases, and ε decreases. So we can get that Rp is as about 2.57 times at a minimum as Rb when α=6, β=1, and ε=0.95, while Rp is as about 6.34 times at a maximum as Rb when α=3, β=10, and ε=0.4.Figure 3
Rp vs. α, β, and ε.
(a)(b)(c)


## 4.3. Algorithm

From the above Theorem1, the nodes in the same PISetp can transmit Rb successfully at the same time slot while each node takes the value of Rp as Theorem 1, so the sending probability for each node u is set to the inverse of the number of nodes in its proximity region Δup. Thus, we guess all its neighbors can receive the message successfully with high probability, and we will give the proof in the next section. The pseudo-code for node u is given in Algorithm 1, which implies that each node runs it independently.Algorithm 1: SINR-Spanner(u).
1: Initialize the stretch factort;2: Initializek=π/arcsint−1/2t;3: Compute the number of nodes in its proximity region, i.e.,Δup;4: Initializepu=1/Δup;5: InitializeIui=−1 for i=1,2,⋯,k;6:forj=1 to Δp time-slots do7: Send a message containing its IDu and coordinates with probability pu, and remains listening with probability 1−pu;8:while receiving a message from some node vdo9:i= the index of the sector to which v belongs;10:ifIui==−1 or the distance dIuiu>dvuthen11:Iui=v12end if13:end while14:end for15:←Eu=∅;16:fori=1 to kdo17:ifIui≠−1then18:Eu←=Eu←∪Iui,u;19:end if20:end for21:Eu=u,v∣v,u∈Eu←;22:fori=1 to Δp time-slots do23: Broadcast the incoming neighbor set with probabilitypu;24:while receiving a message from some node vdo25:ifu is the incoming neighbor of v and u,v∉Euthen26:Eu=Eu∪u,v;27:end if28:end while29:end forNow, we describe the full operation of our distributed algorithm SINR-Spanner. Each nodeu carries out the same operations and has its local memory. The algorithm consists of three parts. In part 1 (line 1-line 5), each node performs initialization work. Each node u first computes the required number of sectors depending on the given stretch factor t. Then, each node u takes the inverse of Δup as the sending probability. Thus how to obtain Δupa priori is critical to our algorithm design. Some existing works, such as [19, 23], assume the availability of Δup to facilitate the algorithm design and analysis. Such requirements are common under SINR in order to enable initial communication. Therefore, in our algorithm, we also assume that Δup is available to simplify the presentation. In part 2 (line 6-line 20), each node obtains the incoming neighbor in each sector by receiving the neighbors’ messages, and thus, a directed Yao graph forms. Figure 4 shows an intermediate result after part 2 in which there are 6 nodes; the edge length is at most Rb and k=7. Here, Ev1→=v3,v1v2,v1, Ev2→=v1,v2v3,v2v4,v2, Ev3→=v2,v3, and so on. In part 3 (line 21-line 29), each node sends an acknowledgement message back to its incoming neighbor, and thus, an undirected Yao graph is constructed which is a t-spanner we require. An example of YGkRbV is presented in Figure 5, in which edge directions are ignored from the graph shown in Figure 4. Here, Ev1=v1,v2,v1,v3, Ev2=v2,v1,v2,v3,v2,v4, Ev3=v3,v1,v3,v2, and so on. Ev1 has local data v1,v3, and Ev3 has local data v3,v1; thus, the undirected edge v1,v3 is known by two endpoints.Figure 4
YG←kRbV after part 2, where k=7.Figure 5
YGkRbV after part 3, where k=7.Our distributed and randomized algorithm SINR-Spanner, which is different from the algorithms in [9], can solve the t-spanner-SINR problem. In part 1, the algorithm first initializes the stretch factor t to attain a t-spanner. The sending probability for each node u is set to the inverse of Δup to reduce the delay; then, u repeats randomized transmission for 8Δp time slots, respectively, in part 2 and part 3.


## 5. Performance Analysis of Algorithm SINR-Spanner

### 5.1. The Delay of SINR-Spanner

In order to obtain the main result of this section in Theorem8, we first prove that a graph YGkRbV is constructed with high probability after the algorithm SINR-Spanner terminates in 16Δp+c time slots in Theorem 3; next, analyze why the resultant YGkRbV is the required t-spanner of the communication graph GRbV in Theorem 3.Now, we give a form of Chernoff bounds which can be found in [22] and some advanced textbooks, such as [25], for the proof of Theorem 3.Lemma 2 [22, 25] (Chernoff bounds).
Let0<δ≤1 and X1,X2,⋯,Xn be independent Bernoulli random variables, and let X≔Σi=1nXi and μ=EX. Then, for any δ>0, it holds that
(10)ProbX<1−δμ<e−δ1+δ1+δμ<e−δ2μ/2.
And forδ=1/2,
(11)ProbX<12μ<e−μ/8.Theorem 3.
A graphYGkRbV is constructed with high probability after the algorithm SINR-Spanner terminates in 16Δp+c time-slots, where Δp is the maximum of the node number in one proximity region and c is a constant for the number of time slots for the initialization work.Proof.
SinceRp is as about 2.57 times to 6.34 times as Rb from Theorem 1 and the resultant graph is connected, Δup>2 for any node u. The probability that u transmits as the only transmitting node in its proximity region is
(12)CΔup1·1Δup·1−1ΔupΔup−1=1−1ΔupΔup−1>1−1ΔupΔup>14.
The last inequality holds, since1−1/ΔupΔup increases when Δup increases, and it obtains the minimum value 1/4 when Δup is 2.
Since the nodes can transmitRb successfully if they belong to the same PISetp owing to Theorem 1, there are at least n/Δp nodes transmitting together in one time slot. Consequently, there are at least n/Δp·1/4 nodes transmitting Rb successfully together in one time slot.
Therefore, after8Δp time slots, there are at least 2n nodes transmitting Rb successfully in expectation. By Chernoff bound (Lemma 2), after 8Δp time slots, the probability
(13)ProbX<n=ProbX<1−12·2n<e−n/4.
Therefore, the probability for alln nodes transmitting Rb successfully is
(14)ProbX=n=1−ProbX<n≥1−e−n/4.
Thus, after8Δp time slots in part 2 of the algorithm SINR-Spanner, all the node transmit its ID and coordinates Rb successfully with high probability, i.e., each node obtains the “nearest” incoming neighbor in its proper sectors. Then, after a further 8Δp time slots in part 3, all the node transmit acknowledgement messages Rb successfully with high probability. As a result, a graph YGkRbV is constructed with high probability.
In addition, the number of time slots for the initialization work in part 1 is a constant, which is denoted byc. So the algorithm SINR-Spanner terminates in 16Δp+c time slots.
Obviously, the number of nodes in the proximity region is upper bound byn. If Δp=n, a graph YGkRbV is constructed with high probability in 16n+c time slots.
Next, in order to prove that the resultantYGkRbV of the algorithm is a t-spanner of the communication graph GRbV, we apply some conclusions about YGkV where YGkV is constructed from KnV.Lemma 4 ([11]).
IfV is a set of n points in the plane, and the integer k≥2, then the graph YGkV contains at most kn=On edges.Lemma 5 ([12]).
Lett=1/1−2sinπ/k for the integer k>6, YGkV is a t-spanner of KnV, where n is the number of nodes in V.
In the next, we show thatYGkRbV is the required t-spanner of the communication graph GRbV if GRbV is connected in the following lemma of our previous work [9]. Zhang et al. [9] first give the condition that GRbV is connected if and only if the longest edge in Euclidean minimum spanning tree of the node set V is at most Rb. Note that if the nearest neighbor of each node in every sector is within the local broadcast region, the graph YGkRbV is a YGkV and it is also a 1/1−2sinπ/k-spanner of KnV.Lemma 6 ([9]).
Lett=1/1−2sinπ/k. If GRbV is connected and the integer k>6, YGkRbV is a t-spanner of GRbV.
Now, we show that the resultantYGkRbV of the algorithm is a t-spanner of the communication graph GRbV.Theorem 7.
Given a constantt>1, setting k=π/arcsint−1/2t, the resultant graph YGkRbV is the required t-spanner with at most kn edges after the algorithm SINR-Spanner terminates.Proof.
Ask>6, the sector angle is not larger than π/6. Hence, sinπ/k is a monotone decreasing function of k, and its value is less than 1/2. As a result, t=1/1−2sinπ/k increases as k increases when k>6 and approaches 1 as k⟶∞, i.e., t is an injective and increasing function of k. Hence, its inverse function k=π/arcsint−1/2t is a decreasing function of t. Therefore, given a constant t>1, we will find a k such that the Yao graph with the number of sectors of no less than k is the required t-spanner.
Since the number of sectors is an integer, and the number of edges becomes larger as the number of sectors increases from Lemma4, k is assigned to π/arcsint−1/2t. Therefore, the resultant graph YGkRbV is the required t-spanner. Furthermore, YGkRbV have kn edges by Lemma 4.Based on Theorems3 and 7, we can state the main conclusion of this section in Theorem 8.Theorem 8.
The distributed algorithm SINR-Spanner constructs the requiredt-spanner with high probability, and the delay is 16Δp+c time slots, where Δp is the maximum of the node number in one proximity region and c is a constant for the number of time slots for the initialization work.Lastly, Table1 illustrates the relation between the stretch factor t and the number of sectors k in theory. In SINR-Spanner, k is the value in the second row given the corresponding t in the first row. Note that t=1/1−2sinπ/k is the upper theory bound of the stretch factor for YGkRbV with respect to GRbV so far, maybe a smaller k is sufficient in practical.Table 1
The stretch factort and the number of sectors k in theory.
t7.64.33.22.72.32.121.91.81.71.61.51.41.31.21.1k78910111213141516171922283870


### 5.2. The Approximation Ratio of SINR-Spanner Algorithm

The goal oft-spanner-SINR problem is to find a suitable t-spanner under SINR and to minimize the delay in the construction. Now, we try to give the approximation ratio of the SINR-Spanner algorithm. The basic idea of our algorithm is that each node should locally broadcast its ID and coordinates to its neighbors Rb successfully under SINR. In order to reduce the delay, there should be as many nodes as possible to transmit simultaneously. As we see, in the SINR-Spanner algorithm, the nodes in different proximity region can transmit simultaneously. Now, we consider whether the nodes in a different local broadcasting region can transmit simultaneously, then discuss the approximation ratio of SINR-Spanner.Theorem 9.
The approximation ratio of the algorithm SINR-Spanner is bounded bye/2·Rp2/Rb2.Proof.
The probability that any nodeu transmits as the only transmitting node in its local broad region is
(15)CΔub1·1Δub·1−1ΔubΔub−1=1−1ΔubΔub−1.
LetS be the total area of wireless nodes distribution. Assume that a node as the only transmitting node in its local broadcasting region can transmit Rb successfully, the number of nodes transmitting Rb successfully in one time slot is
(16)SπRb2·1−1ΔubΔub−1.
In fact, the assumption cannot be guaranteed by theory and the following simulation, i.e., even though a node is the only transmitting node in its local broadcasting region, the node may not transmitRb successfully owing to cumulative interference producing by other simultaneously transmitting nodes. So the solution adopted the above assumption is the low bound for t-spanner-SINR problem.
From the analysis of SINR-Spanner algorithm, the delay of constructing at-spanner under SINR is mainly and inversely proportional to the number of nodes transmitting Rb successfully in one time slot. Hence, the approximation ratio of the algorithm SINR-Spanner is
(17)SπRb2·1−1ΔubΔub−1/SπRp2·1−1ΔupΔup−1=Rp2Rb21−1ΔubΔub−1/1−1ΔupΔup−1≤Rp2Rb2·12/1e=e2·Rp2Rb2.
The inequality holds owing to the following:Δup>Δub≥2 for connectivity and 1−1/xx−1 decreases with x increases when x≥2. When x is large enough, replacing x−1 by x does not cause much error and 1−1/xx≅1/e.
SinceRp is at about 2.57 to 6.34 times as Rb from Theorem 1 and Figure 3, the approximation ratio of SINR-Spanner is a constant.


## 5.1. The Delay of SINR-Spanner

In order to obtain the main result of this section in Theorem8, we first prove that a graph YGkRbV is constructed with high probability after the algorithm SINR-Spanner terminates in 16Δp+c time slots in Theorem 3; next, analyze why the resultant YGkRbV is the required t-spanner of the communication graph GRbV in Theorem 3.Now, we give a form of Chernoff bounds which can be found in [22] and some advanced textbooks, such as [25], for the proof of Theorem 3.Lemma 2 [22, 25] (Chernoff bounds).
Let0<δ≤1 and X1,X2,⋯,Xn be independent Bernoulli random variables, and let X≔Σi=1nXi and μ=EX. Then, for any δ>0, it holds that
(10)ProbX<1−δμ<e−δ1+δ1+δμ<e−δ2μ/2.
And forδ=1/2,
(11)ProbX<12μ<e−μ/8.Theorem 3.
A graphYGkRbV is constructed with high probability after the algorithm SINR-Spanner terminates in 16Δp+c time-slots, where Δp is the maximum of the node number in one proximity region and c is a constant for the number of time slots for the initialization work.Proof.
SinceRp is as about 2.57 times to 6.34 times as Rb from Theorem 1 and the resultant graph is connected, Δup>2 for any node u. The probability that u transmits as the only transmitting node in its proximity region is
(12)CΔup1·1Δup·1−1ΔupΔup−1=1−1ΔupΔup−1>1−1ΔupΔup>14.
The last inequality holds, since1−1/ΔupΔup increases when Δup increases, and it obtains the minimum value 1/4 when Δup is 2.
Since the nodes can transmitRb successfully if they belong to the same PISetp owing to Theorem 1, there are at least n/Δp nodes transmitting together in one time slot. Consequently, there are at least n/Δp·1/4 nodes transmitting Rb successfully together in one time slot.
Therefore, after8Δp time slots, there are at least 2n nodes transmitting Rb successfully in expectation. By Chernoff bound (Lemma 2), after 8Δp time slots, the probability
(13)ProbX<n=ProbX<1−12·2n<e−n/4.
Therefore, the probability for alln nodes transmitting Rb successfully is
(14)ProbX=n=1−ProbX<n≥1−e−n/4.
Thus, after8Δp time slots in part 2 of the algorithm SINR-Spanner, all the node transmit its ID and coordinates Rb successfully with high probability, i.e., each node obtains the “nearest” incoming neighbor in its proper sectors. Then, after a further 8Δp time slots in part 3, all the node transmit acknowledgement messages Rb successfully with high probability. As a result, a graph YGkRbV is constructed with high probability.
In addition, the number of time slots for the initialization work in part 1 is a constant, which is denoted byc. So the algorithm SINR-Spanner terminates in 16Δp+c time slots.
Obviously, the number of nodes in the proximity region is upper bound byn. If Δp=n, a graph YGkRbV is constructed with high probability in 16n+c time slots.
Next, in order to prove that the resultantYGkRbV of the algorithm is a t-spanner of the communication graph GRbV, we apply some conclusions about YGkV where YGkV is constructed from KnV.Lemma 4 ([11]).
IfV is a set of n points in the plane, and the integer k≥2, then the graph YGkV contains at most kn=On edges.Lemma 5 ([12]).
Lett=1/1−2sinπ/k for the integer k>6, YGkV is a t-spanner of KnV, where n is the number of nodes in V.
In the next, we show thatYGkRbV is the required t-spanner of the communication graph GRbV if GRbV is connected in the following lemma of our previous work [9]. Zhang et al. [9] first give the condition that GRbV is connected if and only if the longest edge in Euclidean minimum spanning tree of the node set V is at most Rb. Note that if the nearest neighbor of each node in every sector is within the local broadcast region, the graph YGkRbV is a YGkV and it is also a 1/1−2sinπ/k-spanner of KnV.Lemma 6 ([9]).
Lett=1/1−2sinπ/k. If GRbV is connected and the integer k>6, YGkRbV is a t-spanner of GRbV.
Now, we show that the resultantYGkRbV of the algorithm is a t-spanner of the communication graph GRbV.Theorem 7.
Given a constantt>1, setting k=π/arcsint−1/2t, the resultant graph YGkRbV is the required t-spanner with at most kn edges after the algorithm SINR-Spanner terminates.Proof.
Ask>6, the sector angle is not larger than π/6. Hence, sinπ/k is a monotone decreasing function of k, and its value is less than 1/2. As a result, t=1/1−2sinπ/k increases as k increases when k>6 and approaches 1 as k⟶∞, i.e., t is an injective and increasing function of k. Hence, its inverse function k=π/arcsint−1/2t is a decreasing function of t. Therefore, given a constant t>1, we will find a k such that the Yao graph with the number of sectors of no less than k is the required t-spanner.
Since the number of sectors is an integer, and the number of edges becomes larger as the number of sectors increases from Lemma4, k is assigned to π/arcsint−1/2t. Therefore, the resultant graph YGkRbV is the required t-spanner. Furthermore, YGkRbV have kn edges by Lemma 4.Based on Theorems3 and 7, we can state the main conclusion of this section in Theorem 8.Theorem 8.
The distributed algorithm SINR-Spanner constructs the requiredt-spanner with high probability, and the delay is 16Δp+c time slots, where Δp is the maximum of the node number in one proximity region and c is a constant for the number of time slots for the initialization work.Lastly, Table1 illustrates the relation between the stretch factor t and the number of sectors k in theory. In SINR-Spanner, k is the value in the second row given the corresponding t in the first row. Note that t=1/1−2sinπ/k is the upper theory bound of the stretch factor for YGkRbV with respect to GRbV so far, maybe a smaller k is sufficient in practical.Table 1
The stretch factort and the number of sectors k in theory.
t7.64.33.22.72.32.121.91.81.71.61.51.41.31.21.1k78910111213141516171922283870


## 5.2. The Approximation Ratio of SINR-Spanner Algorithm

The goal oft-spanner-SINR problem is to find a suitable t-spanner under SINR and to minimize the delay in the construction. Now, we try to give the approximation ratio of the SINR-Spanner algorithm. The basic idea of our algorithm is that each node should locally broadcast its ID and coordinates to its neighbors Rb successfully under SINR. In order to reduce the delay, there should be as many nodes as possible to transmit simultaneously. As we see, in the SINR-Spanner algorithm, the nodes in different proximity region can transmit simultaneously. Now, we consider whether the nodes in a different local broadcasting region can transmit simultaneously, then discuss the approximation ratio of SINR-Spanner.Theorem 9.
The approximation ratio of the algorithm SINR-Spanner is bounded bye/2·Rp2/Rb2.Proof.
The probability that any nodeu transmits as the only transmitting node in its local broad region is
(15)CΔub1·1Δub·1−1ΔubΔub−1=1−1ΔubΔub−1.
LetS be the total area of wireless nodes distribution. Assume that a node as the only transmitting node in its local broadcasting region can transmit Rb successfully, the number of nodes transmitting Rb successfully in one time slot is
(16)SπRb2·1−1ΔubΔub−1.
In fact, the assumption cannot be guaranteed by theory and the following simulation, i.e., even though a node is the only transmitting node in its local broadcasting region, the node may not transmitRb successfully owing to cumulative interference producing by other simultaneously transmitting nodes. So the solution adopted the above assumption is the low bound for t-spanner-SINR problem.
From the analysis of SINR-Spanner algorithm, the delay of constructing at-spanner under SINR is mainly and inversely proportional to the number of nodes transmitting Rb successfully in one time slot. Hence, the approximation ratio of the algorithm SINR-Spanner is
(17)SπRb2·1−1ΔubΔub−1/SπRp2·1−1ΔupΔup−1=Rp2Rb21−1ΔubΔub−1/1−1ΔupΔup−1≤Rp2Rb2·12/1e=e2·Rp2Rb2.
The inequality holds owing to the following:Δup>Δub≥2 for connectivity and 1−1/xx−1 decreases with x increases when x≥2. When x is large enough, replacing x−1 by x does not cause much error and 1−1/xx≅1/e.
SinceRp is at about 2.57 to 6.34 times as Rb from Theorem 1 and Figure 3, the approximation ratio of SINR-Spanner is a constant.


## 6. Simulation

In the previous section, we theoretically prove that the algorithm SINR-Spanner performs well in the worst cases and the resultant graph is the required spanner. In this section, we conduct simulations to investigate the average performance of our algorithm.Our simulations are coded in the Sinalgo simulation framework [26], which is for testing and validating network algorithms and abstracts from the underlying layers. We consider a square area of 1000 by 1000 and deploy n nodes within this network region randomly and uniformly, where n∈3000,3500,4000,4500,5000. The local broadcasting range Rb varies in 10,12,14,16,18. The ambient noise N=5×10−8mW. Figure 3 has given the ranges of the path loss exponent α, the threshold β, and ε, and the relation between them and the proximity range Rp. Rp mainly affects the sending probability, which affects the delay of our algorithm. After testing various values, no matter what values α, β, and ε have in the ranges, the variety of the performance and the delay in our algorithm is similar. Therefore, we adopted α=5, β=4, and ε=0.8 in our following reported result. Accordingly, the transmission power P=Nβ·Rb/1−εα owing to the equation (2) and (3). The setting of simulation parameters refers to [9, 19]. With the proof of Theorem 8, we know that each node runs 16Δp+c rounds and the algorithm could get the required spanner with high probability. However, the way we adopted was that the algorithm terminates when the resultant graph does not change in 50 continuous timeslots in the simulation, i.e., in 50 continuous time slots no node can find a nearer neighbor within each sector. Over 100 runs of the simulations have been made for each reported average result.Now, we first explore the stretch factor of the resultant graph (real stretch factor) in Figure6. In (a), we analyze the influence of the number of nodes. The local broadcasting range was set to Rb=12, and the number of sectors was set to k=8. The maximum and average real stretch factor slightly reduced with the number of nodes increasing. In (b), we investigate the impact of Rb with the number of nodes n=3500 and the number of sectors k=8. The real stretch hardly changes with Rb. In (c), we analyze the influence of the number of sectors k with n=3500 and Rb=12. The maximum and average real stretch factor decrease with k increases. When k→∞, the stretch factor approaches one. From all figures in Figure 6, it can be seen that both the maximum and average real stretch factor is much smaller than the theory value in Table 1 with the same k. Hence, given the required t, we can choose a smaller k according to practical experience. In summary, the stretch performance of the algorithm SINR-Spanner is better than expected.Figure 6
Influences ofn, Rb, and k on the number of missing edges.
(a)(b)(c)Due to randomization of SINR-Spanner, the constructed graphs may not be perfectYGkRb; for example, the connection link to the nearest neighbor in a sector might be missing. But the algorithm performance is guaranteed with high probability, i.e., the probability for all n nodes transmitting Rb successfully and all edges in YGkRb being reserved is bounded by 1−e−n/4. To verify this, we evaluate the number of missing edges in the resultant graph from the corresponding perfect YGkRb in Figure 7. With a different number of nodes, different values of Rb, and different number of sectors, we compare the number of missing edges in three sending probability cases including 1/n, 1/Δup (SINR-Spanner), and 1/ΔuI (the algorithm SINR-Undirected-YG in previous work [9]). When the sending probability is 1/Δup, the number of missing edges is a little bit more than the other two cases; the reason is that the nodes transmitting at the same time are more and mutual interference is a little bigger. However, the number of missing edges in all three cases is no more than three in total 100 runs, though each run has no less than 3000 nodes and Okn edges. Simulations indicate that the similarity between the resultant graph and the corresponding YGkRb with no-missing edges is close to 100% in all three cases.Figure 7
Influences ofn, Rb, and k on the number of missing edges.
(a)(b)(c)We then consider the average delay needed by SINR-Spanner in Figure8 from the influences of n in (a), Rb in (b), and k in (c), respectively. We still compare the results with three sending probability cases including 1/n, 1/Δup (SINR-Spanner), and 1/ΔuI (the algorithm SINR-Undirected-YG in previous work [9]). Whether the sending probability is 1/n, 1/Δup, or 1/ΔuI in (a), the delay grows with the number of nodes increasing. In (b), the delay increases with Rb increasing when the sending probability is 1/Δup and 1/ΔuI. However, when the sending probability is 1/n, the delay does not change in (b) since it is only related to the number of nodes. In (c), the delay does not vary with k increasing. In summary, from Figure 8, the delay mainly changes with the change of the sending probability, while the sending probability of 1/Δup or 1/ΔuI mainly varies with n and Rb. Moreover, the average delay needed by the algorithm in [9] is close to the case where each node transmits with the probability 1/n, and the average delay needed by SINR-Spanner is much smaller than that of previous work [9]. Finally, in theory, 16Δp+c is the delay upper bound of the algorithm SINR-Spanner from Theorem 8 and Δp is the upper bound by n, while in the simulation, the delay is much smaller than 16n+c and the algorithm can achieve reliable performance when the algorithm terminates when the resultant graph does not change in 50 continuous time slots.Figure 8
Influences ofn, Rb, and k on the delay.
(a)(b)(c)


## 7. Summary

In this paper, we present a randomized and distributed algorithm SINR-Spanner to solve thet-spanner-SINR problem using small delay in the IoT, which has the following characteristics: (1) being a distributed algorithm, (2) considering the SINR interference model, (3) applying the YG idea, and (4) theory and simulation guaranteed. In future research, the delay performance of the spanner construction algorithm under SINR may be able to be improved by adopting a smaller proximity region. Other methods for spanner construction except YG are also worthy of investigating.



---

*Source: 6643810-2021-02-02.xml*