QuadScatter for Simultaneous Transmissions in a
Large-Scale Backscatter Network
Ousmane Zeba, Shunsuke Saruwatari and Takashi Watanabe
Graduate School of Information Science and Technology
Osaka University, Japan

Abstract—Backscatter communication is attracting attention
for its ultra-low-power consumption ability. The said capability
will enhance IoT which aims to enable a large number ofnovel applications for object-to-object communication. In sucha network, where numerous tags may transmit simultaneously,
it is important to make sure that the number of simultaneoustransmissions allows reliable decoding operations on a large
scale. Here we introduce QuadScatter, a series of algorithms thatmake proﬁt of the maximum number of simultaneous backscattertransmissions to enable a network of a signiﬁcant numberof transmitters, tags, and readers. The maximum number ofsimultaneous transmissions is veriﬁed by simulations and theoverall capacity of the network allows successful communications
above 3 dB of signal-to-noise ratio (SNR). QuadScatter shows
agreeable results compared to the exhaustive search algorithm.
The simulation results highlight computational time and simultaneous transmission improvements of 250x and 2x. Furthermore,while the exhaustive search is limited to a few nodes(< 20), ourproposal uses a larger number of nodes.

Keywords— Simultaneous backscatter transmissions,quadtree, quadtree quadrant, nearest neighbor search,exhaustive search, IoT
I. I NTRODUCTION
The backscatter device is attracting attention because of
its ultra-low-power wireless communication capabilities. The
ability of power consumption below the milliwatt is signiﬁcant
for the upcoming IoT technology. IoT aims to enable a large
number of novel applications, where objects will be capableof responding to the presence of people and other objects.
In a typical bistatic backscatter system design [1], thebackscatter tag receives an excitation signal from the transmitter and reﬂects it to the receiver or reader, without generating
or amplifying any signal. Numerous studies such as [2] and[3], showing signiﬁcant results, have been conducted in thecase of concurrent transmissions from several backscatter tags
to the same reader.
The impending IoT technology will need to make to beneﬁt
from the case of simultaneous backscatter transmissions where
several backscatter devices transmit their data to different
readers at the same time in the same environment. The reason
behind that is if a large number of tags are deployed in thepresence of an equivalent number of transmitters and receivers,simultaneous transmissions will occur inevitably. In addition,
selecting the best threesome source-tag-reader can agreeably
improve the capacity of the network.
In [4] the detection problem of multiple passive and semipassive RFID tags with impulsive backscattered signals isaddressed in an ultrawideband (UWB) technology. The goal
was to improve the reader capability and enable robust tag
detection, even in the presence of multi-tag interference andclock drift effects.
Choir is presented in [2] to overcome the challenges related
to density and transmission range in urban Low-Power WideArea Networks (LP-WANs). Choir allows a maximum of 10
concurrent transmissions and is capable of retrieving data fromdevices located as far as 2.65km. This performance is achieved
by applying chirp spread spectrum modulation [5].
In a recent work [3], a large scale backscatter network
named NetScatter is presented. NetScatter is a wireless protocol that enables a network of 256 backscatters for concurrent
transmissions on 500kHz channel bandwidth. The number ofconcurrent transmissions increases according to the bandwidth,
reaching a thousand of concurrent transmissions for only
2MHz of bandwidth. All this is achieved by using a distributed
chirp spread spectrum coding based on chirp spread spectrum
modulation and ON-OFF keying. Furthermore, NetScatter iscapable of operating with weak backscatter signals aroundnoise ﬂoor. However, time synchronization is compulsory for
NetScatter. The backscatter devices must be synchronizedwhen sending to the access point. Besides, hardware delays
such as clock frequency variations, inherent to backscatterdevices, and propagation delay need to be corrected. The
above-mentioned timing mismatch is difﬁcult to avoid witha growing number of backscatter devices.
The above-cited publications analyze the multi-tag to one
reader scenario. In other words, they are dealing with a
network of many backscatter tags and only one receiver towhich all the backscatter signals are directed. In contrast,
we are investigating in this study the case of a network ofnumerous backscatter devices and an equivalent number oftransmitters and receivers. The main constraint of multi-tag toreader transmissions is to increase the number of concurrent
transmissions and communication range while keeping reliable
decoding operations on the reader side. As for our case,dealing with numerous backscatters and numerous APs ischallenging for two reasons.
1) Computational complexity. Finding the best AP foreach tag among numerous devices can entail extremely
high computational cost. To solve this issue we apply
quadtree, a 2-D nearest neighbor search algorithm that
reduces signiﬁcantly the computational cost.

2) Simultaneous communications. In the current scenario
we do not have concurrent transmissions like in [2]and [3]. However, multiple backscatter tag-AP pairs
may transmit simultaneously. In that case, knowing theupper bound of the number of simultaneous communications helps in increasing the overall capacity of thewhole network by allowing the maximum simultaneoustransmissions. To this end, and for this ﬁrst study, we
numerically determined the upper limit of simultaneoustransmissions for a given signal-to-noise-ratio thresholdof 3dB.
3) Supported number of network nodes. As for now, only
the exhaustive search algorithm can be used in suchsituation. However, it has a serious handicap regarding
the network size. The exhaustive search algorithm deals
only with a network of very few number of nodes.
The main contribution of this work is a series of algorithms that enable simultaneous transmissions in a large scale
backscatter network resulting in a reduced computational timeand cost, and an increased network size compared to theexhaustive search algorithm. Simulation results that verify
our conclusions are also presented. The paper is organized
as follows: Section II states the problem of simultaneoustransmissions in a large scale backscatter network; Section III
describes the algorithms designed for this study; Section IV focuses on the numerical analysis of simultaneous transmissions.
Section V presents simulation results while the conclusion
follows in Section VI.
II. P ROBLEM S TATEMENT
Imagine a scenario where n backscatter tags and m APs are
deployed in a given area. Backscatter tags are passive devices
that only reﬂect [1] incident signals from their surrounding
environment. APs can generate and transmit their signals andreceive them from other transmitting devices. In our case,the tags will use the received signal from APs to transmit
their own collected data. Backscatter tags have only one task:
receive signals from sources and reﬂect them to the desired
destinations. The task of APs is different when we have a big
number of tags deployed with a limited number of APs. In
addition to generating, transmitting and receiving signals, eachAP has to handle many tags. It may alternately be transmitterand receiver for many tags or receiver for many tags. Thereis also the possibility of being a transmitter for many tags.
However, that case does not demand too much to the AP, asbeing a transmitter for one or many makes no difference interms of power.
One of the most important parameters in a network is its
transmission capacity. A major factor of the capacity according
to Shannon’s law is the signal-to-interference-plus-noise ratio(SINR) [6] [7], which is equivalently replaced in this paper by
the signal-to-interference ratio (SIR), neglecting the ambient
noise for the sake of simplicity. The better the SIR is, thebetter the capacity will be. Unfortunately, the SIR is subject
to the distance between the transmitter and receiver and theinterference occurring at the receiver. Obtaining a high SIR,

which gives, in turn, an interesting and reliable transmission
capacity, requires to avoid or mitigate the interfering signals
and reduce the distance between transceivers.
In a network formed by backscatter tags and APs, only
the APs are capable of receiving signals. In reality, thoseAPs receive more signals than the signal intended to them.
An AP in such a case, in addition to the inbound signal,
receives interfering signals from other tags in its immediateneighborhood and the transmitter AP as illustrated. Assumingthat the signal reﬂected by the backscatter has a slightly
different frequency due to the impedance of the backscatterdevice, we can consider the signals from other backscatters as
the only interference in addition to the ambient noise. Figure
1 gives an illustration of the devices and the different signals.
According to [8], considering only the signal from the tag
to the reader we can writeτ Pr d−β(z,y)
SIRy|n = ∑n,−βi τ Pṙ d(z˙i ,y)(1)

where Pr is the received power at the backscatter tag andτ is the factor introduced by the backscatter tag (0 < τ < 1)and β = 2 to 4 is a propagation constant. Pṙ and d(z˙i ,y) are
related to other tags that are source of interference. PE being
the transmit power from the source transmitter and d(x,z) the
distance between source and tag, we havePr =PEdβ(x,z).

(2)

Hence eq. 1 becomes−βτ PE d−β(x,z) d(z,y)
SIRy|n = ∑n.
−β−βi τ PĖi d(x˙i ,z˙i ) d(z˙i ,y)(3)

Assuming that all the sources are equal in power leads towriting eq. 3 as−βd−β(x,z) d(z,y)
SIRy|n = ∑n −β,−βi d(x˙i ,z˙i ) d(z˙i ,y)(4)which shows that the SIR depends only on the distances
between the nodes involved in the transmission and interfering
signal.
With the above-mentioned issues and the given parameters,
how can we maximize the SIR of the receiver to improve
the transmission capacity of the network? Some works havealready addressed the issue of interference mitigation such as[9]–[11]. We opted to treat that issue in a simple but different
manner as follows:
1) First, we built an assignment or selection algorithm
to optimize the received power on the reader’s side.
The received power depends on the distance between
the sender and receiver, assuming that all the carrier
signals are emitted with the same power. Thus, if thenearest transmitter and the nearest in the vicinity ofthe tag can be selected it would be easier to obtain aEĞƚǁŽƌŬŽŶƚƌŽůůĞƌ
Rx2

Tag2
Incident signal
Tag’s signal
Interference signal

Tx

Tag1

Rx1

Fig. 1. Simultaneous backscatter transmissions: Signals and interferences.

maximized received power. One has to bear in mind thatthe backscatter tag is not able to select a carrier signal
nor to decide which reader should receive the reﬂectedsignal. For that reason, there is a controller that controls
all the Network components.
2) Second, we tried to ﬁnd the maximum number of simultaneous backscatter transmissions that can be tolerated
by the reader. By simultaneous transmissions, we mean
many tags reﬂecting signals to different readers at thesame time. The signal from other tags will create interference to the inbound signal to each tag. According to
the SIR threshold for successful decoding of the signal,
there will be a limit to the acceptable interference.
Which corresponds to a certain number of interfering
signals and backscatter devices.
III. P ROPOSED A LGORITHM
This section describes our proposed algorithm to maximize
the transmission capacity in a backscatter network. Two cases
have been distinguished in tackling this issue: before thedeployment of the network and after the network is deployed.
In this work, we only focus on an already deployed network.
In an already deployed network, it is hard to change thetopology to a suitable one without redeploying the wholenetwork, which would cost much effort and time. To avoid
redeployment while trying to improve the transmission capacity of the network, we just apply the AP selection techniqueand limit the number of simultaneous communications to the
maximum allowed number.
The AP selection algorithm looks for APs (transmitter andreceiver) that suit the most to each tag in terms of distance.
It just picks the two closest APs to the tag. For a huge
number of tags and APs, ﬁnding the nearest neighbor canbecome NP-hard due to the computational complexity. Forn number of tags and m, ﬁnding two nearest neighbors ofeach tag gives the complexity of O(2n ) by making a naive
comparison with the exhaustive search algorithm. The highcomputational cost is attributable to the process of ﬁnding
the most appropriate AP. Therefore, a nearest neighbor searchalgorithm will considerably reduce the computing cost.
1) Nearest Neighbor Search: There exist many algorithms
for nearest neighbor search. Among them are Locality Sensitive Hashing (LSH) and quadtree.
LSH is an algorithmic technique that creates a bucketof input items with a high probability of similarity usinghash functions [12]. Since it separates similar items from
dissimilar ones, LSH can be used for the nearest neighborFig. 2. Backscatter controlled network.
Ƌϭͮ,ϭ

YϮͮ,Ϯ

Yϯͮ,ϯ

Yϰͮ,ϭ

Fig. 3. Backscatter network and quad tree quadrants: Each quadrant Qn is
assigned a channel CHk orthogonal to its immediate neighbors’ channels.

search. However, LSH is more convenient in high dimensional
spaces, which is different from our two-dimensional space. For
example, the Python implementation of LSH in [13] is only
suitable for data samples with high dimensionality.
Quadtree is an algorithmic technique used to partition a
two-dimensional space by recursively subdividing it into four
quadrants or regions [14]. The subdivided regions may havearbitrary shapes. Quadtree decomposes the space into buckets.
Each bucket has a maximum capacity. When the maximum
capacity is reached, the bucket divides into four quadrants. The
quadtree algorithm is interesting for our situation in the sensethat it is conceived for two-dimensional space. For that reason,
quadtree drove our attention and convinced us to combine itwith our assignment algorithm. Furthermore, it has a worse
case complexity of O(n), which is signiﬁcantly lower thanthe complexity of exhaustive search algorithm.
A. QuadScatter
QuadScatter is the algorithm we deﬁne for assigning APs
to backscatter tags. Mainly four phases compose the QuadScatter algorithm: Apply quadtree to create quadrants, nearest
neighbor selection phase, common transmitter search phase,and transmitter-receiver assignment phase.
1) Deﬁne and create an adequate number of quadrants:
This phase is a crucial step in the whole process as it
subdivides the target area into quadrants allowing an easierlocalization of nodes. An implementation of a quadtree allows
deciding the maximum number of nodes in each quadrant after
receiving the coordinates of the targeted area. It is also possible
to limit the number of divisions by giving the maximum
range of divisions. This phase of QuadScatter receives thearea size and the coordinates of nodes deployed on it as
an input, Algorithm 1 line 2. As an output, it gives theresulting quadrants and the points associated with each ofthem, Algorithm 1 line 3.
Algorithm 1: C REATE Q UADRANT creates quadrants
in area A
Input: A two-dimensional area A and the coordinatesof its network nodes
Output: A ﬁnite set Q = {q1 , q2 , . . . , qn } of quadrants
1 Q←∅
2 Quadtree(A)3 Q ← {q1 , q2 , . . . , qn }4 return Q
2) Nearest neighbor selection: Instead of randomly selecting the transmitters and readers, a thorough search of nearest
APs would give a better result as the SIR and capacity dependon the distances separating the two nodes.
As already mentioned above in section III-1, we apply
quadtree to the area to lower the computational complexityof our proposed algorithm. The quadrants or regions resulting
from quadtree will contain a certain number of devices that
we address with very little complexity. For a given quadrant,
containing m tags and n APs, algorithm 2 compares the
distances separating tags and APs, in lines 3 to 6. After that,it returns an array of the nearest APs to each tag, algorithm
2 line 7. In that array, each line corresponds to a tag in thequadrant. The same line is a sorted list of APs where the ﬁrst
AP is the nearest one.
Algorithm 2: F IND N EAREST ﬁnds the nearest APs in
the quadrant
Input: A quadrant q of a given area and its points
Output: An array A of nearest APs to each tag
1 A←∅
2 list ← ∅3 for i ← 1 to m do4
for j ← 1 to n do
5compute distance dij
6list ← dij
7
8
9

sort list
A ← list
return A

3) Common transmitter search and assignment: The main
objective of this stage is to avoid the usage of many transmitters while only one sufﬁces for many backscatter tags.
This phase named 3 works as described in the following lines.

Algorithm 3 picks the ﬁrst element of the array returned byalgorithm 2 and compares it to the elements of the following
line, lines 7 to 8 in algorithm 3. In case it matches any elementin that line it jumps to the next line, line 9 of algorithm 3. Incase no element of the current line matches, algorithm 3 goesback to the following element in the ﬁrst line of the array,as described in lines 11 and 12. After any line is ﬁnished,algorithm 3 makes sure to always start with the ﬁrst elementof the next line as shown in line 14. After running throughall the lines of the array, algorithm 3 stops looking for thecommon element, lines 15 and 16.
Algorithm 3: F IND C OMMON ﬁnds the common element to the lines of an array
Input: An array of n columns and m lines
Output: The common element to all the lines
1 i←0
2 j ←03 line ← 0
4 common ← ∅5 for k ← 1 to n − 1 do
6
while i ≤ n and j ≤ m do
7
common ← A0,k8
if common ̸= Ai,j then9j ←j+1
10
else
11
i←i+1
12
j←0
13
line ← i
14
15
16
17

j←0
if line = m thenbreak
return common

4) Transmitter and receiver assignment: At this stage, theappropriate tags and APs are assigned to each other by the
network controller. This process completes the backscatter
network and enables communications between network nodes
as described in algorithm 4. Algorithm 4 takes a set of APs
and tags associated with one quadrant as an input. First of all,it makes sure that a common AP is already found or not. If a
common AP exists, that AP will be set as the transmitter for
all the tags in the quadrant. Once the common transmitter isdesignated, the nearest AP to each tag other than the common
AP is set as receiver for the appropriate tag, as illustrated inlines 1 to 8 of Algorithm 4. In the case of no common AP, thenearest AP to each tag is taken as a receiver and the second
one as a transmitter. The latter case is described in lines 9 to
14 of algorithm 4.
IV. M ATHEMATICAL A NALYSIS
Equation 4 gives the SIR in the theoretical analysis of
the capacity of backscatter communication as presented in[8]. Even though this formulation is the appropriate one forSIRy|4 =SIRy|4 =Fig. 4. Simultaneous transmissions and formulation of the distances: The
distance is evaluated following the path of the signal from the transmitter tothe receiverthe current situation, it might become arduous to manipulate
when dealing with a large number of devices, due to the
product of powered distances dβ(x,z) et dβ(z,y) and the sum∑ ββi d(x˙i ,z˙i ) d(z˙i ,y) . For the sake of simplicity and to reduce theheaver of mathematical manipulations, we consider a slightly
different formulation. That is, as shown in Eq. 4, the factor τ
induced by the backscatter disappeared as if the backscatter
itself was no more involved in the transmission. Thus, we take
into account the distance from the source x to the reader y as
if it was a straight line instead of distances from the source
to tag and from tag to the reader. As a result, we obtain asimpler and mathematically convenient to manipulate versionof the SIR.

(5)

Algorithm 4: A SSIGN assigns APs to tags
Input: A ﬁnite set A of n APs and m backscatter tags
Output: Selected and assigned APs and tags
1 if common ̸= ∅ then2common ← transmitter3
for i ← 1 to m do4
for j ← 1 to n do
5
if Ai,j ̸= transmitter then6
Ai,j ← receiver
7
Ai,j ← tagi
8
break
else
for i ← 1 to m do
11
Ai,0 ← receiver
12
Ai,1 ← transmitter
13
Ai,0 ← tagi
14
Ai,1 ← tagi
9

10

15

d−β
1 + ρ2 )−β + (2ρd + d)−β.

(6)Since the propagation constant β = 2, obtain the following
simpliﬁed version of Eq. 6

݀

]−β
[
d(x,z) + d(z,y)
SIRy|n = ∑ []−β .
i d(x˙i ,z˙i ) + d(z˙i ,y)2(ρd + d√return 01) Simultaneous communications: According to Eq. 5 theSIR of 4 simultaneous backscatter communications as illustrated in Fig. 4 is given as follows, considering one source astransmitter and following the distances derived in Fig. 4.

1

.
1
√ 2
(1+2ρ)2 + ( 1+ρ2 +ρ)2

(7)

Then while looking for the upper bound of SIRy|4 we found
the following. The details are given in the appendix section ofthis paper.
√8ρ(3 + 2 2)
√ ,SIRy|4 <(8)16ρ + (3 + 2 2)√

√ 2 ≈ 0.7945.
with ρy|4 > 83+2
2−3
For ﬁve simultaneous communications, in the similar conditions as explained above, the SIR appears to be:

SIRy|5 =

(

2
√

√

1−ρ

1
)2 + (√5−1+ρ2 +ρ
2

1+ρ

2
√

√
10−2 5+ρ2 +ρ
2

)2

.

(9)
For a better understanding of SIRy|5 in Eq.5 we computeits upper bound:√√(ρ + 2)2 (4 + 2 3)√
√ .
SIRy|5 <(10)
8 + 2 2 + 2(ρ + 2)2
√
√
√
6+8 3
It yields ρy|5 >− 2 ≈ 1.158 for a minimum
3
SIR of 3dB. Which clearly suggests the limit of simultaneousbackscatter communication.
One must keep in mind that we are using an upper boundestimation ρ. Normally the real values are supposed to beinferior to the given values. Even though ρ|5 appears to begreater than 1, at least ﬁve simultaneous communications canbe considered possible, which is veriﬁed by the simulations
results of QuadScatter in section V.
2) Quadrant channel assignment: One issue that might beencountered with QuadScatter is the inter-quadrant interferences. In fact, a node located in a given quadrant might sufferfrom the interferences from nodes located in its neighboring
quadrants. To solve that issue we propose to alternately
assign different channels to the quadrants as shown in Fig. 3.
Considering the 2.4GHz band and its 3 orthogonal channels,
the channels will be assigned so that a quadrant and its two
immediate neighbors use the three orthogonal channels.
V. E VALUATIONThis section gives the evaluation results of our proposed
method. We compare the number of simultaneous transmissions and the computational time of our algorithm named
QuadScatter to those of the exhaustive search or brute force
algorithm. We simulated a network of randomly deployed tags

3.0

Exhaustive search
Quadscatter# of simultaneous transmissions# of simultaneous transmissions

2.5
2.0
1.5
1.0
0.5
0.0

0

5

10

15
20
Number of tags

25

Fig. 5. Average number of simultaneous transmissions in random 30x30 areawith 6 APs.

100
10−1
10−2
10−3
10−4
5

10
15
20
Number of tag nodes

25

1.5
1.0
0.5
0

5

10

15
20
Number of tags

101

E haustive search
Quadscatter

0

2.0

30

25

30

Fig. 7. Average number of simultaneous transmissions in random 30x30 areawith 12 APs.

Computational time [sec]Computational time [sec]

101

2.5

0.0

30

Exhaustive search
Quadscatter

E haustive search
Quadscatter

100
10−1
10−2
10−3
10−4

0

5

10

15
20
Number of tags

25

30

Fig. 6. Computational time of exhaustive search and QuadScatter in random
30x30 area with 6 APs.

Fig. 8. Computational time of exhaustive search and QuadScatter in random
30x30 area with 12 APs.

and AP nodes on a 30x30 area. The data collected are theaverage values from one hundred different random topologies.
Meaning that the program is executed one hundred times andat each time a different random topology of APs and tags
is created. While the number of APs is kept unchanged, thenumber of tags is incremented by one after one hundred trials
until the desired number of tags is reached. We conducted thesimulations in three cases. Case 1 with only 6 APs, case 2
with 12 APs and case 3 with growing number of APs. 6 is
the minimum number of APs that could give 5 simultaneoustransmissions following our numerical study in section IV.
The simulation parameters are set as follows: Transmit
power = 20dBm equivalent to 100mW, sensitivity = −94dB,
noise ﬂoor = −97dB, SNR threshold = 3dB, path loss
exponent β = 2.
As for the results, we found that Exhaustive search reaches
a maximum of 3 simultaneous transmissions whereas QuadScatter outputs a maximum of 7 simultaneous transmissions,in some occurrences, outperforming exhaustive search andconﬁrming our theoretical analysis. Hence, if the suitable

topology is found QuadScatter will deliver at least the doubleof the performance of exhaustive search. Note again that, thevalues shown by Fig.5, Fig.7 and Fig.9 are average values of
100 trials, which is more realistic for a random deployment
scenario. Figure 5 shows a better performance of exhaustive
search over QuadScatter. However, that performance is limited
to a network of few nodes (< 20). As illustrated in Fig.6, thecomputational cost of exhaustive search does not comply witha large scale network. When the network size grows, Fig. 7,
QuadScatter renders agreeable performance in terms of simultaneous transmission while keeping an ultra-low computationalcost, Fig.8. In Fig. 9 and Fig.10 QuadScatter shows its abilityof handling a network of a hundred of nodes, delivering around5 simultaneous transmissions with a computational time lower
than 0.01 sec. QuadScatter suitable to a network of numerous
nodes while exhaustive search deals only with a network of a
restrained number of nodes without time constraint. Naturally,
exhaustive search does not go beyond 10 backscatter tags andits computational time extends considerably with an increased
number of APs. For that reason, when the number of APs

0 < ρ < 1 gives 1 + 4ρ < (1 + 2ρ)2 <√ 8ρ which gives# of simultaneous transmissions

5

1
1
<
1 + ρ2 + ρ)2 <2 . 0 < ρ < 1 also gives 1 < (8ρ
√ (1+2ρ)2( 2 + ρ)2 , which gives (√2+ρ)< √ 22 2 and 3+22√2 <2( 1+ρ +ρ)
2√
1
√ 2
we
get the lower bound of.
By
addingto8ρ
( 2+ρ)2
3+2 2
1
1
2
√
ρy|4 = (1+2ρ)2 + ( 1+ρ2 +ρ)2 . Then by taking the inverse of√8ρ(3+2 2)√that sum, we obtain the upper bound 16ρ+(3+2of ρy|4 . The
2)upper bound of ρy|5 is computed in the same way.

Quadscatter

4
3
2

R EFERENCES

1
0

0

10

20

30
40
Number of APs

50

60

Fig. 9. Average number of simultaneous transmissions in random 30x30 areawith 30 tags.

Computational time[sec]10−2

Quadscatter

10−3

10

20

30
40
Number of APs

50

60

Fig. 10. Computational time of QuadScatter in random 30x30 area with 30
tags.

increased, case 2 and case 3, we deliberately restrained thenumber of tag nodes for exhaustive search to avoid runningthe experiment during many days.
In conclusion, 3 major improvement points are broughtby QuadScatter compared to exhaustive search. An increased number of simultaneous backscatter transmissions andbackscatter nodes in a controlled network, and signiﬁcantly
faster computational time, QuadScatter is at least 250 times
faster than exhaustive search.
VI. C ONCLUSION
In this work, we analyzed computational cost and simultaneous transmissions in a large backscatter network. An algorithm
was developed to improve the performance of the wholenetwork. Our results show signiﬁcant improvements comparedto the exhaustive search algorithm. Future work will focus on
increasing the number of simultaneous transmissions.
A PPENDIX
Upper bound proof of ρy|4 and ρy|5 in section IV.

[1] C. Xu, L. Yang, and P. Zhang, “Practical Backscatter Communication
Systems for Battery-Free Internet of Things: A tutorial and survey ofrecent research,” IEEE Signal Processing Magazine, vol. 35, no. 5, pp.
16–27, 2018.
[2] R. Eletreby, D. Zhang, S. Kumar, and O. Yağan, “Empowering LowPower Wide Area Networks in Urban Settings,” in Proceedings of theConference of the ACM Special Interest Group on Data Communication.
ACM, 2017, pp. 309–321.
[3] M. Hessar, A. Najaﬁ, and S. Gollakota, “NetScatter: Enabling LargeScale Backscatter Networks.” in NSDI, 2019, pp. 271–284.
[4] F. Guidi, N. Decarli, S. Bartoletti, A. Conti, and D. Dardari, “Detectionof Multiple Tags Based on Impulsive Backscattered Signals,” IEEE
Transactions on Communications, vol. 62, no. 11, pp. 3918–3930, 2014.
[5] B. Reynders and S. Pollin, “Chirp Spread Spectrum as a Modulation
Technique for Long Range Communication,” in 2016 Symposium on
Communications and Vehicular Technologies (SCVT). IEEE, 2016, pp.
1–5.
[6] C. E. Shannon, “A mathematical theory of communication,” Bell systemtechnical journal, vol. 27, no. 3, pp. 379–423, 1948.
[7] T. M. Cover and J. A. Thomas, Elements of information theory. John
Wiley & Sons, 2012.
[8] A. V. Padaki and M. J. Zawodniok, “Theoretical Capacity Analysis forMulti-hop Backscatter Communication Networks,” in 2011 Proceedingsof 20th International Conference on Computer Communications andNetworks (ICCCN). IEEE, 2011, pp. 1–6.
[9] W. Liu, K. Huang, X. Zhou, and S. Durrani, “Full-duplex Backscatter
Interference Networks Based on Time-hopping Spread Spectrum,” IEEE
Transactions on Wireless Communications, vol. 16, no. 7, pp. 4361–
4377, 2017.
[10] M. R. Souryal, D. R. Novotny, D. G. Kuester, J. R. Guerrieri, and K. A.
Remley, “Impact of RF Interference between a Passive RFID System
and a Frequency Hopping Communications System in the 900 MHz ISM
Band,” IEEE Electromagnetic Compatibility Magazine, vol. 1, no. 3, pp.
97–102, 2012.
[11] A. Varshney, O. Harms, C. Pérez-Penichet, C. Rohner, F. Hermans, andT. Voigt, “LoRea: A Backscatter Architecture that Achieves a Long
Communication Range,” in Proceedings of the 15th ACM Conferenceon Embedded Network Sensor Systems. ACM, 2017, p. 18.
[12] Wikipedia contributors, “Locality-sensitive hashing — Wikipedia,
The Free Encyclopedia,” https://en.wikipedia.org/w/index.php?title=
Locality-sensitive hashing&oldid=905340247, 2019, [Online; accessed
16-August-2019].
[13] Avinash Kak, “LocalitySensitiveHashing — LocalitySensitiveHashing.py version: 1.0.1,” https://engineering.purdue.edu/kak/distLSH/
LocalitySensitiveHashing-1.0.1.html, 2017-May-25, [Online; accessed
8-October-2019].
[14] Wikipedia contributors, “Quadtree — Wikipedia, The Free Encyclopedia,” https://en.wikipedia.org/w/index.php?title=Quadtree&oldid=
910044683, 2019, [Online; accessed 16-August-2019].