arXiv:1608.08261v3  [cs.RO]  23 Nov 2016
Interference Power Bound Analysis of a Network of
Wireless Robots
Pradipta Ghosh
Ming Hsieh Department of Electrical Engineering
University of Southern California
Los Angeles, California 90089
Email: pradiptg@usc.edu
Bhaskar Krishnamachari
Ming Hsieh Department of Electrical Engineering
University of Southern California
Los Angeles, California 90089
Email: bkrishna@usc.edu
Abstract—We consider a fundamental problem concerning
the deployment of a wireless robotic network: to fulfill various
end-to-end performance requirements, a “sufficient” number of
robotic relays must be deployed to ensure that links are of
acceptable quality. Prior work has not addressed how to find
this number. We use the properties of Carrier Sense Multiple
Access (CSMA) based wireless communication to derive an upper
bound on the spacing between any transmitter-receiver pair,
which directly translates to a lower bound on the number
of robots to deploy. We focus on SINR-based performance
requirements due to their wide applicability. Next, we show
that the bound can be improved by exploiting the geometrical
structure of a network, such as linearity in the case of flow-based
robotic router networks. Furthermore, we also use the bound
on robot count to formulate a lower bound on the number of
orthogonal codes required for a high probability of interference
free communication. We demonstrate and validate our proposed
bounds through simulations.
I.
INTRODUCTION
In the field of Robotics and Automation, one of the
emerging area of research is focused on the applicability of
a wireless network of robots to create a temporary communi-
cation backbone between a set of communication endpoints
with no or limited connectivity [1]. In these contexts, the
robots act as relay nodes to form wireless communication
paths between the communication endpoints. The application
of this field of research ranges from fire fighting [2] and
underground mining [3] to supporting temporary increase in
the communication demands or creating a secure mesh network
for clandestine operations [4]. To the best of our knowledge,
one of the unexplored problem in this context is to determine
the number of robots to deploy such that all the links can
maintain certain acceptable link qualities, such as maximum
allowed bit error rate (BER) or minimum supported data rate,
in presence of fading and shadowing. Interestingly, most of
these link quality metrics are known to be directly related to
the Signal to Interference plus Noise ratio (SINR) of the links.
Now, the SINR value of a link depends on the spacing between
the transmitter and receiver of the link as well as the locations
of the interfering nodes. Thus, an offline characterization of
SINR values as a function of the maximum allowed inter-
node distance is required to properly select the number of
nodes to be deployed and to properly place the nodes across
a deployment region. Moreover, the presence of CSMA/CA
among the robots needs to be taken into account for more
practical estimation.
In our venture for a generic model to estimate the number
of robots to deploy (by estimating the maximum allowed inter-
node distance to maintain the target SINR), we explored the
existing literature in search for a proper model of interference
and Signal to Interference plus Noise Ratio (SINR) range
analysis in a CSMA/CA based wireless network. There exist
a large body of works that characterize the mean interference
power distribution in CSMA networks ([5], [6]) by employing
the concepts of point process such as Poisson Point process,
Mat’ern hard core process and Simple Sequential Inhibition[7].
The basic idea of this class of work is to represent the locations
of the interferers as spatial point processes, more specifically,
hard core point processes where the nodes fulfil a criterion of
being certain distance apart to take into account CSMA among
themselves. Through application of different point process
properties such as thinning and superpositions, researchers
([5], [8], [6], [9]) estimated the probability distributions of
the mean interference powers in the presence of CSMA/CA.
Interested readers are referred to [10] for a detailed survey
on this class of works. Among the other class of works, the
work of Hekmat and Van Mieghem [11] is the most relevant
to us. They demonstrated that the interference power in the
presence of CSMA is actually upper bounded and can be
best estimated by use of hexagonal lattice structure. However,
this work as well as most of the other works include some
assumptions such as the receiver being located at the center
of a contention region, which is only acceptable if the devices
follow the 802.11 RTS/CTS standards [12]. Interestingly, in
practice, very few commercially available products actually
employ the RTS/CTS mechanism. Furthermore, the Internet of
Things (IoT) and Wireless Sensor Network (WSN) standard
802.15.4, which is also a standard choice for robotic network
platforms, does not use RTS/CTS mechanism, in order to
avoid inefficiencies. Thus, it is actually the transmitter that
employs the CSMA and should be located at the center of the
contention region, whereas, the receiver is free to be anywhere
inside the transmitter’s communication range. In such cases,
the SINR and the interference mean values as well as the
bounds for a link are, in fact, functions of the separation
distance (d) between the endpoints of the link. However, none
of the existing works try to characterize the SINR or the
interference as a function of the separation distance (d),
which is crucial for the number of robot estimations. In
this paper, we modify the bounds proposed in [11] and flesh
out details of applying the modified bounds to estimate the
number of robots to be deployed to satisfy the communication
performance goals. Note that, in the rest of the paper, we focus
on interference limited networks and, thereby, ignore the effect
of noise and focus on Signal to Interference Ratio (SIR) instead
of SINR.
In this paper, we first explain the concepts presented
in [11] (for a general dense wireless network) as well as
the impracticality of the bounds, followed by our proposed
modified interference and SIR bounds as functions of the
distance between a transmitter and a receiver, for any network
that employs CSMA/CA. Through a set of simulation results
we show that, with fading introduced in the model, we can
form a stochastic bound as well, such that the probability of the
real interference being higher than the bound is very low. This
formulation helps any network designer to properly choose
a maximum separation between the nodes and to properly
place a set of nodes in any practical deployment. Secondly, we
extend this bound one step further to determine a bound on the
number of orthogonal codes to be used in order to guarantee a
high probability of interference free communication. We also
explore the bounds on interference power, if a fixed number
of orthogonal codes are employed. Thirdly, we consider our
application specific scenario of robotic router network to devise
a better bound by applying the structure of the network.
Through a set of simulation experiments we validate the
bounds and show that the improved application specific bound
significantly (10% −45%) decreases the required number of
costly, resource constraint robots.
II.
PROBLEM DESCRIPTION
In this section, we detail our problem formulations. For
compactness, we list the symbols used for base problem
formulation in Table I and symbols related to our goals in
Table II, respectively. Say, we have a transmitter node T and
a receiver node X that are placed at d distance apart, alongside
with a larger number of interfering wireless nodes. Each
node of this interference limited network (i.e., the interference
dominates over noise) employs Channel Sense Multiple Access
with Collision Avoidance (CSMA/CA) [13] for wireless media
access and has a transmission power of Pt. The radio range of
each node is subdivided into three regions, centered at the
node’s location: a circular connected/contention region of
radius D1, an annular transition region with inner radius
D1 and outer radius D2 (including the boundaries), and a
disconnected region which is the entire region outside the
circle with radius D2 > D1; where the values of D1 and
D2 depend on the actual RSSI thresholds of the devices
used [14]. Undoubtedly, in the presence of fading, the regions
are not so nicely structured, nonetheless, can be approximated
by proper choice of D1 and D2. Now, the CSMA restricts
the transmissions from the nodes in the contention region
of T , while the nodes in the transition region are aware of
T ’s transmission with very low probabilities and, therefore,
are the potential interferers. However, only a subset of the
nodes in the transition region can be active simultaneously,
due to CSMA among themselves, which requires any two
simultaneous interferers to be at least D1 distance apart. The
interference power from the nodes in the disconnected region
are considered insignificant.
Definition 1. A set of interfering nodes (IC) such that D2 ≥
dij ≥D1 and diT ≥D1 ∀i, j ∈IC, is referred to as an
Interference Set Cover.
Now, there are four main objectives of this work as follows.
Objective 1. Find a mapping between d and the minimum
achievable SIR at X, SIRX(d).
Objective 2. Find the range, 0 < d ≤dmax, such that the
outage probability i.e., P(SIRX(d) < SIRth) < γ where
0 ≤γ ≤0.5 is the choice of the designer.
Now, one can employ a set of orthogonal codes to further
restrict the interference in a CSMA network. In such cases,
the maximum value of interference power decreases, based on
the number of codes employed, possibly leading to near zero
interference. In this context, our goal is as follows.
Objective 3. Characterize SIRX(d) as a function of the
number of orthogonal codes (NO) employed for concurrent
transmissions, and find a bound N ′
O such that P(1I0 = 1) ≥κ
∀NO > N ′
O, where the indicator function
1I0 refers to
interference free communication and κ ≥0.5 is a designer
choice.
For our SIR and Interference bound analysis, we consider
two different scenarios in this paper. In the first scenario, the
node pair in focus is placed in a “dense” network, where a
countably many uncontrollable wireless nodes are co-located
in the area of interest. Secondly, we consider our target
application of robotic router placement, where the goal is
to place a set of robots such that they form multihop links
between a set of maximum M concurrent communication
end-point pairs. This application context restricts the possible
configuration of the interfering nodes within a class of network
formations, such as straight line formation, that voids the
earlier dense network assumption. At any time instance, we
associate a set of routers with each flow i ∈{1, 2, · · ·M}
that form a chain between the communication endpoints. Thus,
for a fixed set of communication endpoints of a flow i, the
minimum number of nodes (N R
i ) to be allocated to flow i
depends on dmax which in turn controls the minimum number
of nodes to be deployed, N R ≥PM
i=1 N R
i .
Objective 4. Find a better and tighter bound on interference
as well as SIR by exploiting the application specific restrictions
on the network configurations. Next, analyze the improvement
in the number of robots required, with this improved bound.
III.
OUTLINE OF THE PROPOSED SOLUTION
In this section, we summarize our methodologies for
achieving the target objectives while the details are discussed
later on.
A. Methodology for Mapping from d to SIRX
For a fixed value of the separation distance d between T
and X, we estimate the maximum feasible interference as well
as minimum feasible SIR, by exploiting the geometry of the
connectivity region and transition region. For received power
modelling, we opt for the standard log normal fading model
[13], where the received power is distributed log normally with
TABLE I: General Parameters
Symbol
Description
T
Transmitter
X
Receiver
dij
Distance between node i and j
d
Distance between T and X i.e., dT X
η
Path Loss Exponent
ψ ∼N (0, σ2)
Log normal Fading Noise with variance σ2
Pt
Transmitted Signal Power
Pr
Received Signal Power
PI
Received Interference Power
IC
Interference Set Cover
M
Number of Flows
TABLE II: System Parameters
Symbol
Description
SIRth
The Target Minimum SIR
SIRX(d)
Minimum Achievable SIR at X for d separation
D1
Contention Region Outer Radius
D2
Transition Region Outer Radius
Pt
Transmitter Power
γ
Required Probability of SIR ≥SIRth
κ
minimum probability of interference
free communication
dmax
maximum distance allowed between T and X
NO
Number of Orthogonal Codes
Nmax
I
Maximum Number of Interfering Nodes
mean power calculated using simple path loss model. Thus, the
received power can be represented as:
Pr(d) = Q.Ptd−η10
ψ
10
(1)
where Q is some constant. Next, we introduce the following
claim as our whole estimation process revolves around this
claim.
Claim 1. In presence of Independent and Identically Dis-
tributed (I.I.D) fading noise, the Interference Set Cover (see
Definition 1) with maximum mean power as well as maximum
number of interferers will give us better stochastic bound than
any other Interference Set Cover.
Justification:
This claim is justified by the fact that, if
the fading noises are I.I.D, the Interference Set Cover with
maximum number of nodes will give the highest variance.
Thus, the Interference Set Cover with highest mean as well
as highest number of nodes will be a better bound than any
other Interference Set Cover.
Now, the main steps for representing SIRX as a function
of d are as follows.
Step 1. We first identify the Interference Set Cover(s) (IC)
that will potentially give us the best estimate of the maximum
feasible mean interference power, for a fixed d, using greedy
algorithm.
Step 2. We estimate the maximum number of nodes in any
Interference Set Cover, N max
I
.
Step 3. To get the maximum interference power, we add up
the interference powers of the nodes of the Interference Set
Covers selected in Step 1, according to Eqn (1). Thus the total
interference power at X is a sum of log normal variables as
follows.
PIC (d) = Q.
X
j∈IC
Ptd−η
jX10
ψ
10
(2)
Step 4. We multiply the interference power estimate in Step 3
by a correction factor ζ = max{1, N max
I
|IC| }, where |.| denotes
the cardinality of a set, to account for the Interference Set
Covers with less than N max
I
number of nodes, i.e., |IC| <
N max
I
. Now, the modified interference power is:
PIC (d) = ζ.Q.
X
j∈IC
Ptd−η
jX10
ψ
10
(3)
Step 5. We calculate the SIR value for each of the Interference
Set Covers selected in Step 1 in dB, as follows.
SIRX(d) = 10 log10


Ptd−η10
ψ
10
ζ. P
j∈IC Ptd−η
jX10
ψ
10


(4)
B. Methodology for Selecting dmax
In order to properly select dmax, first of all, we need
to estimate the distribution of the SIRX(d) using Eqn (4),
which is not very straightforward as it involves division and
summation of a large set of log normal random variables. The
traditional log normal summation methods involve sampling
and filtering to fit the distribution into an approximated log
normal [15]. We opt for similar approach where we collect
a good number of samples, say 50000, from each of the con-
tributing log normal distributions, for a fixed d, to generate the
SIR samples (SIRX(d)) and use the SIR samples to determine
the mean, µSIRX(d), the variance of the SIR, σ2
SIRX(d) and
the empirical probability distribution function (PDF) of the
SIRX(d). A rigorous mathematical PDF formulation is one of
our future works. Note that in presence of fading, using simple
path loss model, we can easily get the mean powers received
from each interferer, which can be used to estimate E(Pr)
E(PI), but,
not the mean SIR, i.e., E(SIR) = E

Pr
PI

̸= E(Pr)
E(PI).
Step 6. To properly select dmax, we first choose an acceptable
value for SIRth and γ. Next, we use the samples of SIRX(d)
to estimate the outage probability Γ(d) = P(SIRX(d) <
SIRth), for a uniformly selected values of d ∈[0, D1]. The
highest value of d that satisfies Γ(d) < γ is the estimated
dmax.
C. Orthogonal Code Bound For Interference Free Network
First of all, say, NO number of orthogonal codes are used
and each node chooses a code randomly (all codes are equally
likely to be chosen) and independently. The new code specific
interference power bound for a randomly selected Interference
Set Cover (IC) will be:
PIC (d|OT ) =
|IC |
X
j=1
P j
IC ×
1{Oj=OT }
E(PIC (d)) =
1
(NO)
|IC|
X
j=1
E(P j
IC )
(5)
where OT is the code chosen by T , P j
IC denotes the inter-
ference power due to jth interferer in IC, and the indicator
function
1{Oj=OT } denotes whether the jth interferer have
chosen same code as the transmitter i.e., OT . Notice that, the
Interference Set Cover with maximum mean interference
power will still give us the maximum mean estimated
interference power in presence of orthogonal codes.
Step 7. We use the estimated Interference Set Cover from
Step 1 to determine the new SIR bounds as follows.
SIRIC (d|OT ) =
Ptd−η10
ψ
10
ζ. P
j∈IC

Ptd−η
jX10
ψ
10

. 1{Oj=OT }
(6)
Now, at any time instance, maximum N max = (N max
I
+
1) number of nodes can be active simultaneously. Given that
NO ≥N max, we deduce that (Proof in Appendix A):
P(1I0 = 1) ≥
Nmax
Y
i=1

1 −i −1
NO

(7)
From Eqn (7), we can see that for NO
≥
N max,
QN max
i=1

1 −i−1
NO

is a strictly increasing function of NO.
Step 8. To find the optimum value of NO, we estimate
QN max
i=1

1 −i−1
NO

for increasing value of NO (starting from
N max), and select the minimum value of NO such that
QN max
i=1

1 −i−1
NO

≥κ.
IV.
IDENTIFICATION OF MAXIMUM POWER
INTERFERENCE SET COVER
In the section, we identify the Interference Set Covers that
result in the highest total interference power at a given receiver
location, X, for both scenarios i.e., dense random network and
robotic router network.
A. Dense Random Network
In [11], Hekmat and Van Mieghem showed that the mean
interference power in CSMA Network is bounded by the
interferers located along the hexagonal rings centred at the
receiver’s location, where the ith ring with each side length
equal to i × D1 contains 6 ∗i nodes. While the assumption
of putting the receiver at the center is valid in the presence of
RTS/CTS mechanism in CSMA, in reality, RTS/CTS mech-
anism is NOT employed in most of the enterprise wireless
networks as well as Internet of Things (IoT) networks. In such
cases, the transmitter is the node to be located at the center of
the rings while the receiver is free to be located anywhere in
the connected region of T . With this modification, the maximum
feasible interference can actually be higher than the bound
estimated in [11] e.g., when X is located at the farthest point
of the connected region of T . Moreover, for determining the
number of nodes to deploy, we need to know the maximum
separation distance (dmax) that can support an acceptable
maximum interference level, in order to place a set of nodes
in any area of deployment. This requires us to modify the
bounds to have a separation distance (d) dependency. However,
hexagonal packing is known to be the densest packing in
circular spaces which leads us to believe that the distance
dependent interference are also bounded by the interference
power of the set of interferers located at hexagonal rings
(similar to [11] but in an annular ring) around the Transmitter’s
location. With this assumption, our focus becomes restricted to
all possible sets of locations that form such hexagonal packing.
We can easily prove that, with the separation distance d > 0,
we only need to consider two different angular orientations of
such hexagonal packing, as illustrated in Figures 1a and 1b.
(a) Configuration 1
(b) Configuration 2
Fig. 1: Illustration of the Interference Set Covers For Estima-
tion of Interference Upper Bound in a Dense Network
In the first type of configuration, which we refer to as Con-
figuration 1, the closest interferer is located at the intersection
of the inner boundary of the annulus and the line joining T and
X (Illustrated in Figure 1a). This configuration is generated
by taking a greedy iterative approximation approach, where
we start with an empty IC and, in each iteration, we select
a point on the annulus that is closest to the receiver X and
is not located in the connected regions of the nodes already
added to IC. In the second configuration, which we refer to
as Configuration 2 (illustrated in Figure 1b), the number of
closest interferers is two and they are exactly D1 distance
apart from each other as well as from the transmitter. With
this new initial condition, we can find the rest of the nodes,
again, using the greedy approach. Now, WLOG, we assume
that T is located at (0, 0) in a 2D domain, while X is located
at (d, 0). In this 2D domain, the positions of the interfering
nodes for both of these Interference Set Covers are listed in
Table III. It can be easily shown that these two configurations
form the bound of the interference power for any configuration
within same class i.e, with similar relative position between
nodes with hexagonal corner positioning. Next, we calculate
the interference and SIR for these two configurations according
to Eqn. (3) and (4). Then, we choose the maximum of these
two interference estimates as our interference estimate, and
minimum of these two SIR estimates as our SIR estimate.
We perform this using the sampling method discussed in
Section III-B, where we collect a large number of pairs of
samples from these two configurations and take the highest
interference power sample (or lowest SIR sample) from
each pair as a sample for our estimated bounds.
However, since this is an greedy solution, the resulting
Interference Set Cover combination may not include the max-
imum number of interferer and, therefore, does not guarantee
maximum possible interference power. Now say the greedy
logic includes n interferes. Then according to the greedy
logic, it is most likely that the top n interfering nodes of
TABLE III: Interference Set Cover Node Locations for a Dense Network
Line Number
Configuration 1
Configuration 2
(Illustrated in Figures1a and 1b)
l0
{(±jD1, 0)} ∀j ∈{1, 2, · · · , N0 + 1}
{(0, ±jD1)} ∀j ∈{1, 2, · · · , N0 + 1}
N0 = ⌊D2−D1
D1
⌋
lk where k is odd
{(± D1(1+2×j)
2
,
√
3
2 kD1)}
{(
√
3
2 kD1, ± D1(1+2×j)
2
)}
Nk = ⌊

D2
2−3
4 k2D2
1
 1
2
D1
⌋
∀k ∈{1, ⌊2D2
√
3D1 ⌋}
∀j ∈{0, 1, · · · , Nk}
∀j ∈{0, 1, · · · , Nk}
l′
k where k is odd
{(± D1(1+2×j)
2
, −
√
3
2 kD1)}
{(−
√
3
2 kD1, ± D1(1+2×j)
2
)}
Nk = ⌊

D2
2−3
4 k2D2
1
 1
2
D1
⌋
∀k ∈{1, ⌊2D2
√
3D1 ⌋}
∀j ∈{0, 1, · · · , Nk}
∀j ∈{0, 1, · · · , Nk}
lk where k is even
{(±jD1,
√
3
2 kD1)}
{(
√
3
2 kD1, ±jD1}
Nk = ⌊

D2
2−3
4 k2D2
1
 1
2
D1
⌋
∀k ∈{1, ⌊2D2
√
3D1 ⌋}
∀j ∈{0, 1, · · · , Nk}
∀j ∈{0, 1, · · · , Nk}
l′
k where k is even
{(±jD1, −
√
3
2 kD1)}
{(−
√
3
2 kD1, ±jD1}
Nk = ⌊

D2
2−3
4 k2D2
1
 1
2
D1
⌋
∀k ∈{1, ⌊2D2
√
3D1 ⌋}
∀j ∈{0, 1, · · · , Nk}
∀j ∈{0, 1, · · · , Nk}
the maximum power Interference Set Cover will have less
or equal interference power compared to the interference
power from the greedily found Interference Set Cover. To
guarantee that our estimated interference power is no less
than the maximum possible interference power, we multiply
our estimated interference power by a correction factors, ζ =
max{1, N max
I
|IC| }, where N max
I
denotes the maximum number
of simultaneous interferers and |.| denotes the cardinality of a
set. The correction factor (ζ) compensates for the cardinality
of the Interference Set Cover i.e., if |IC| < N max
I
. We
found that the number of interferers estimated from the
hexagonal packing is in fact also N max
I
for most of the
cases. Nonetheless, we can determine the maximum number
of concurrent interfering nodes (N max
I
) by formulating the
problem as a circle packing problem [16] as follows.
Definition 2. Pack Problem: Maximize the number of circles
with radius
 D1
2


that can be packed inside an annulus with
inner and outer radius:
 D1
2


and
D2 + D1
2


, respectively.
Lemma 1. The cardinality of the solution to the Pack Problem
is also the maximum cardinality of an Interference Set Cover.
(Proof in Appendix B)
Note that, there exists a range of approximation solution
to the circle packing problem [16], which can be directly
applied to solve this problem. In this paper, we do not present
any circle packing solution. Furthermore, since it is hard to
analytically prove the correctness of our estimated bounds,
we validate the bounds via a set of simulation experiments
in Section V.
B. Interference Estimation for Robotic Router Network
In this section, we focus on the interference estimation for
our application specific context of robotic wireless network
in a obstacle free environment. Before that, we make an
assumption, based on two related works [1], [17], as follows.
Assumption 1. For a flow based robotic network in a ob-
stacle free environment, if the goal is to optimize the flow
performance in terms of SIR, the best configuration of robots
allocated to that flow is to stay on the straight line joining the
static endpoints.
This assumption is justified by the work presented
in [1] which shows that the best configuration of robots in
order to optimize packet reception rate (which is directly
related to SIR) of a flow based network is to evenly place
them along the line segment joining the static endpoints.
The work of Yan and Mostofi[17] further justify the
linear arrangement of same flow nodes for Signal to Noise
Ratio (SNR) based optimization goal. In our analysis, we
employ Assumption 1 to restrict the feasible positions of the
interfering nodes, thereby, leading to better and tighter bounds
on interference. In this context, we divide the interference
into two components: Intra-flow interference and Inter flow
interference. These two components refer to the interference
power from the nodes in the same flow as the transmitter
T and interference power from the nodes of different flows,
respectively.
Fig. 2: Illustration of the Highest Power Intra-Flow Interfer-
ence Set Cover
1) Intra-Flow Interference: Our intra-flow interference es-
timation is based on the following lemma.
Lemma 2. The maximum expected Intra-flow interference
power for a link corresponds to the sum of interference powers
from nodes located at distances {D1, 2.D1, · · · k.D1} from the
transmitter node T along the line segment joining the flow
endpoints, where k.D1 ≤D2. (Proof in Appendix C)
Therefore, the maximum number of intra-flow interferers
is 2

⌊D2−D1
D1
⌋+ 1

, where the factor 2 accounts for both
sides. In Figure 2, we present an illustration of such scenario.
Thus, the set of nodes that will result in the highest intra-
flow interference power are located at {(±jD1, 0)}
∀j ∈
{1, · · · , ⌊D2−D1
D1
⌋+ 1} in the 2-dimensional area of interest.
Interestingly, these set of locations are same as the line l0 of
Configuration 1 discussed in Section IV-A.
2) Inter-Flow Interference: In realistic scenarios, there will
be more than one flows in the network where robots assigned
to different flows can interfere as well. We refer to such
interference as the Inter-flow interference. Now, the interferers
can be located in the annular transition region around the
transmitter, while the nodes allocated to same flow stay on
the straight line joining the endpoints of the respective flow
(according to Assumption 1). In this section, we start the bound
estimation with a two flow network, followed by a network
with M flows. In this context, we make a key assumption
about the maximum power Interference Set Cover for multi-
flow scenario, as follows.
(a) Two flow Case
(b) M Flow Case
Fig. 3: Illustration of the Multi Flow Interference Estimation
(Blue Nodes: Intra-Flow Interferer, Red Nodes: Inter-Flow
Interferer)
Assumption 2. For any transmitter-receiver node pair of a
flow, the intra-flow maximum power Interference Set Cover
estimated in section IV-B1 is always part of the maximum
power Interference Set Cover in presence of multiple flows.
The reason behind this assumption is mainly the fact that
in practical deployment, some node-pairs might not have
any inter-flow interference at all (e.g., single flow network).
Therefore, neglecting any of the intra-flow interfering nodes
will lead to a incorrect estimate of the interference in such
cases. Under the given assumption, our next step is to find
another line segment that will generate the maximum inter-flow
interference power, for two flow cases. In general case with
M flows, we need to find M −1 other line segments such that
carefully placed set of interferers on those segments result in
the highest inter-flow interference power. Now, following the
greedy approach mentioned in the Section IV-A, the second
flow should contain Y2 or Y3 or both, in Figure 3a, since they
are the next closest points to X after the Intra-flow interference
set cover nodes are accounted for.
Lemma 3. Among the possible line segments through Y2 or
Y3 or both, we just need to consider lZ and lW in Figure 3a
for estimating the bound on the interference power for two
flow case. (Proof in Appendix D)
The set of nodes on lW that will result in highest inter-
ference power should be located at ( D1
2 , ±(
√
3
2 D1 + jD1))}
TABLE IV: Interference Set Cover Node Locations for a Flow
Based Network
Line Number
(Illustrated in Figures 3b)
lW,k
{((2k + 1) D1
2 , ±(
√
3
2 D1 + jD1))}
∀k ∈{0, ⌊(D2−D1)
2D1
⌋}
∀j ∈{0, 1, · · · , NW,k}
l′
W,k
{(−(2k + 1) D1
2 , ±(
√
3
2 D1 + jD1))}
∀k ∈{0, ⌊(D2−D1)
2D1
⌋}
∀j ∈{0, 1, · · · , NW,k}
NW,k = ⌊
 
D2
2−{(2k+1)D1}2
4
! 1
2 −
√
3
2 D1
D1
⌋
∀j ∈{0, 1, · · · , ⌊

D2
2−
D2
1
4
 1
2 −
√
3
2 D1
D1
⌋}. On the other hand,
The maximum power interference set cover node locations
on lZ are same as the line l1 of Configuration 1, listed
in to Table III. Now, the inter flow interference power is
max{P lW
I (d), P lZ
I (d)}, where P lW
I
and P lZ
I
denotes the total
maximum interference power for nodes in line lW and lZ,
respectively.
Next, we extend this concept to M flow scenario i.e., maxi-
mum M−1 interfering flows. For a fixed pair of transmitter and
receiver node of a flow with M −1 interfering flows, we need
to consider two class of configurations. The mean inter-flow
interference power bound of the first class of configurations
is calculated by summing up the total interference power of
the first M ′ lines from the set {l1, l′
1, l2, l′
2, · · · , lK, l′
K} in
Figure 1a, where K = ⌊2D2
√
3D1 ⌋and M ′ = min{M −1, 2K}.
Now, for the bound estimation of second class of configura-
tions, we consider the line segment joining the closest pair
of nodes at any point of time. More precisely, we choose
M ′ pairs of nodes from the pairs illustrated in Figure 3b
as {(Z1, W1), (Z2, W2), (Z′
1, W ′
1), (Z3, W3), · · · , (Z′
K, W ′
K)}
where K =

⌊(D2−D1/2)
D1
⌋+ 1

, M ′ = min{M −1, 2K},
and the pairs are sorted in terms of the respective distances
to the receiver. Thus, the flows situated along lines lW,i
and l′
W,i , i ∈{1, 2, · · · , K} determine the second type of
interference bound in our estimation. The respective locations
of the interferers are illustrated in Table IV. Next, we compare
these two bounds and take the maximum of them as the
estimated interference power bound. We prove the validity
of this bound through a set of MATLAB based simulation
experiments, discussed in Section V.
V.
SIMULATION RESULTS
In this section, we verify our proposed d dependent bounds
on the interference and SIR, through a set of MATLAB 8.1
based experiments performed on a machine with 3.40 GHz
Intel i7 processor and 12GB RAM. For this set of experiments,
we fix the values of the transmitter powers and the path
loss exponent at Pt = 1 and η = 2.2, respectively. The
value of η = 2.2 is motivated by our experiences from real
outdoor experiments (from a different project). As a measure
of the annular transition region area, we choose the ratio of
D2
D1 = {3, 6} as the typical RSSI CCA thresholds are separated
by 10dB to 15dB [14]. The absolute value of D1 is randomly
selected to be 6m as the major factors that controls the
d
-10
-8
-6
-4
-2
0
2
Interference Power (dB)
D 2/D 1=3
Empirical Average
Empirical Max
Empirical Min
General Max Bound
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
6
Separation Distance (d)
-20
-15
-10
-5
0
5
10
SIR (dB)
Empirical Average
Empirical Min
Empirical Max
General Min Bound
(a)
1
2
3
4
5
Separation Distance (d)
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
P{SIR < SIRestimated}
D 2/D 1=3
E{Signal}
E{Interferece}
E{SIR}
E{SIR} −σ{SINR}
(b)
1
2
3
4
5
Separation Distance (d)
0
0.05
0.1
0.15
0.2
0.25
0.3
P{SIR < SIRestimated}
D 2/D 1=3
Theoretical E{SIR}
Empirical E{SIR}
Empirical E{SIR} −σ{SINR}
(c)
Fig. 4: (a) Validation of Estimated Interference Power (Top) and SIR (Bottom) Bounds in dB, for Dense Network with No fading
(b) Probability that Actual SIR is Lower than the estimated Minimum SIR with Log-Normal Fading with variance σ2 = 4 (c)
Probability that Actual SIR is Lower than the estimated Minimum SIR with NO Fading but in Presence of 10 Orthogonal Codes
Algorithm 1 Generate a random set of Interferer
1: procedure GENERATE( )
2:
Initialize a Dense Set of Nodes: ID
3:
Initialize IS as a empty set
4:
while ID is not Empty do
5:
Randomly select v ∈ID
6:
IS = IS ∪v
7:
Bv = {i|i ∈ID & div < D1}
8:
ID = ID \ Bv
9:
end while
10: end procedure
performance is the D2
D1 ratio, not the absolute values of D1 and
D2. With these initializations, we vary the separation distance
d from 1m to D1 −1m with granularity of 0.1m to plot the
separation distance dependent bounds.
First, we verify the bounds for a general dense network,
where the interfering nodes are uniformly distributed over the
annular transition region around T . To verify the bounds,
we randomly generate 1000 sets of interfering nodes, for
a fixed value of d, using Algorithm 1. In Figure 4a, we
compare our estimated interference power and estimated SIR,
with the interference powers and SIR of the generated IS
sets, for no fading scenario and D2
D1 = 3. Figure 4a clearly
validates our d dependent interference and SIR bounds for
a general dense network in absence of fading. Next, we
perform similar experiments but in the presence of log nor-
mal fading of variance σ2 = 4 and
D2
D1 = 3. In this set
of experiments, the estimated bounds for each value of d
are some probability distributions, rather than deterministic
values. In this context, we empirically collect a set of 50000
samples (SIR(d)) from the distributions estimated according
to Eqn (4) and estimate the mean, µSIRX(d) and the variance
of the SIR, σ2
SIRX(d). Next, we collect 50000 sample from
each generated IS and empirically compute the probabilities,
P(SIRIS < µSIRX(d)) , P(SIRIS < µSIRX(d) −σSIRX(d))
and P(SIRIS
<
E(Signal)
E(Interference). We plot the results in
Figure 4b which shows that the estimated SIR mean (from
Eqn (4)) is higher than the actual SIR for around 25% of the
cases, while µSIRX(d) −σSIRX(d) is higher than the actual
SIR for only 10% of the case. Thus, if we were to choose
a deterministic value for the bound rather than a distribution,
µSIRX(d) −σSIRX(d) is considered as a good estimate. Next,
we use similar sampling method to generate the orthogonal
code based SIR bounds when the number of codes used is
10, while the maximum number of simultaneously interfering
node is 38 (For D2/D1 = 3). In this set of experiments, each
node randomly selects a code from the code alphabet. But,
we only sum up the interference powers of the interferers
that select the same code as the transmitter. We apply the
same method for each of the IS set as well to validate our
bounds and plot the probabilities P(SIRIS < µSIRX(d)) and
P(SIRIS < µSIRX(d) −σSIRX(d)) in Figure 4c, for log
normal fading scenario. Figure 4c shows that our proposed
bound also works well in presence of orthogonal codes.
Similar to the generic dense wireless network, we perform a
set of bound tests for the robotic network scenario for D2
D1 = 3.
In this case, we randomly select two pairs of endpoints (i.e.,
we consider a 3 flow network) along the circumference of the
outer circle with radius D2, which are the flow endpoint for
two other flows. Next, we place a dense set of points along
each of the randomly selected flow segments as well as the
line segment joining the transmitter T and the receiver X to
include the intra-flow interference. Then, we use Algorithm 1
to generate 1000 sets of interfering nodes for each value of
d and for each of the 500 randomly generated sets of flow
endpoints. In all cases, the total interference power is bounded
by our proposed theoretical maximum interference power, for
no fading scenario, as illustrated in Figure 5a. This figure also
shows that our application specific bounds are much tighter
than the generic bound. In order to illustrate the impact of
this improvement, we also plot the difference in the number
of robots required to cover a distance of 100m for different
values of SIRth ∈[−5dB, 5dB] in Figure 5b for D2
D1 = {3}.
Figure 5b clearly illustrates that with our improved bound,
the required number of robots to guarantee some target SIR
requirements, is significantly lower than the generic bound
based number of robots estimations, ranging from a maximum
of ∼45% for single flow network to a minimum of ∼10%
for a three flow network. The improvement is significant for
Separation Distance (d)
-15
-10
-5
0
5
Interference Power (dB)
D2/D 1=3
Empirical Average
Empirical Max
Empirical Min
Application Specific Max Bound
General Max Bound
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
6
Separation Distance (d)
-20
-15
-10
-5
0
5
10
15
SIR (dB)
Empirical Average
Empirical Min
Empirical Max
Application Specific Min Bound
General Min Bound
(a)
-5
-4
-3
-2
-1
0
1
2
3
4
5
SIRth in dB
0
5
10
15
20
25
30
35
40
45
in %
Difference in the Number of Robots to be Deployed
1-Flow
2-Flow
3-Flow
(b)
1
2
3
4
5
Separation Distance (d)
0
0.05
0.1
0.15
0.2
0.25
0.3
P{SIR < SIRestimated}
D 2/D 1=3
E{Signal}
E{Interferece}
E{SIR}
E{SIR} −σ{SINR}
(c)
Fig. 5: For a 3 Flow Network: (a) Validation of Estimated Interference Bound (Top) and SIR Bound (bottom) with No Fading
(b) Illustration of Less Number of Robots to be Deployed with Our Application Specific Bound with No Fading (c) Probability
that Actual SIR is Lower than the estimated Minimum SIR with Log-Normal Fading with variance σ2 = 4
less number of flows, as for higher number of flows (∼6 −7
flows) the general dense network bound becomes dominant,
which is quite intuitive. Next, similar to the generic bound,
in Figure 5c we compare the bounds in presence of fading to
show that the estimated µSIRX(d) −σSIRX(d) is higher than
the actual SIR for only 10% of the case, for D2
D1 = 3.
VI.
CONCLUSION
In this paper, we proposed a method for estimation of
the maximum interference and minimum achievable SIR for
a link of length d in an unknown environment while CSMA-
CA or equivalent MAC layer protocols are employed. First,
we demonstrate a strong dependency of these bounds on the
transmitter-receiver separation distance d. Next, by considering
two different scenarios: generic dense network and robotic
router network; we demonstrate that we can formulate bet-
ter and tighter bounds by exploiting the network topology
structure which infact improves our main goal of estimating
the number of nodes to be deployed for our robotic router
network in order to guarantee some network performance.
We also perform a set of MATLAB based simulation results
that validate our findings. This work is a part of our bigger
project of development of a CSMA Aware Autonomous Re-
configurable Network of Wireless Robots, SWANBOT, than
can adapt its configuration over time to maintain link qualities
while performing some allocated task. As a part of our future
work on this specific topic, we plan to develop a more formal
algorithmic approach with polynomial time complexity as well
as flesh out analytical details about the correctness of the
bounds, if possible. Another direction of future work will be
to validate this bounds with real testbed experiments.
APPENDIX A
PROOF OF ORTHOGONAL CODE BOUND
Say, at any time instance, the number of active interferers
is NI ∈[0, N max
I
]. Given that NI number of nodes are
active and NO ≥NI, the probability of interference free
communication is as follows.
P(1I0 = 1|NI) =
NOCNI × NI!
(NO)NI
=
NI
Y
i=1

1 −i −1
NO

=⇒P(1I0 = 1|N1
I) ≥P(1I0 = 1|N2
I)
if N1
I ≤N2
I ≤NO
(8)
Thus, the probability of interference free transmission for
NO ≥N max, where N max = N max
I
+ 1, can be expressed as
follows.
P(1I0 = 1) =
Nmax
X
j=0
P(1I0 = 1|NI = j)P(NI = j)
=
Nmax
X
j=0
j
Y
i=1

1 −i −1
NO

P(NI = j)
≥
Nmax
Y
i=1

1 −i −1
NO
 Nmax
X
j=0
P(NI = j) Using (8)
≥
Nmax
Y
i=1

1 −i −1
NO

(9)
APPENDIX B
PROOF OF LEMMA 1
A valid Solution to the Pack Problem can be directly
mapped to a valid Interference Set Cover. To prove that, let
us consider the set of centres, SP , for the circles in the
Pack Problem solution. For any valid solution to the Pack
Problem, the distance between the centers of the circles are
at least R1 which satisfies the Interference Set Cover distance
condition. Now, the center of any circle to be packed must
lie in the annulus with radius R1 and R2 as the radius of
the circles are R1
2 . Thus SP is a valid Interference Set Cover.
Next, assume the solution to the pack problem, n, does not
contain maximum number of interferer. So there must exist an
Interference Set Cover with more than n interferer. However,
if we formulate a set of circles with the centers to be same
as the Interference Set Cover but with radius equal to R1
2 , it
is also a valid circle packing solution with higher cardinality.
This is a contradiction. Thus the earlier assumption is not true.
Conversely, say that the solution to the Pack problem have
higher cardinality than the max cardinality of Interference Set
Cover, we can always map the Pack problem solution to a new
Interference Set Cover with higher cardinality than the earlier
solution. This is also a contradiction, thus, proves the lemma.
APPENDIX C
PROOF OF LEMMA 2
According to Assumption 1 states that in the final config-
uration, the routers should be placed along the line segment
joining the sink and source, say Lineopt.. Now, assume that
the first interferer in the worst case interference combination
is located at D1 + δ distance from the source, along Lineopt,
instead of D1 where 0 < δ < (D2 −D1). Since, the
distance between two interferer have to be greater than D1
for concurrent transmission, the resulting set of interferers
are located at I1 = {D1 + δ, 2 ∗D1 + δ, · · · , k ∗D1 + δ}
where k ∗D1 + δ ≤D2. Now, the Interference Power is
inversely proportional to distance, more specifically d−η where
2 ≤η ≤6 is the path loss exponent. Now say, the receiver
is located at distance d from the transmitter on the same
side as the interferers. Therefore, the power of the interferer
located at D1 + δ is less the the power of interferer located
at D1 as
1
(D1−d)η ≥
1
(D1+δ−d)η . Similarly if the receiver
is located at distance d from the transmitter on the other
side i.e, the distance between the first interferer and the
receiver is D1 + δ + d, the power of the interferer located
at D1 + δ is less the the power of interferer located at D1 as
1
(D1+d)η ≥
1
(D1+δ+d)η Thus, if we exchange the first interferer
position with D1 i.e, I2 = {D1, 2 ∗D1 + δ, · · · , k ∗D1 + δ}
where k ∗D1 + δ ≤D2 then we get set of location with
total interference power higher than that of I1. This is a
contradiction. Thus the earlier assumption is wrong, thus,
proves the lemma.
APPENDIX D
PROOF OF LEMMA 3
To prove this, we first introduce another lemma as follows.
Lemma 4. The length of the chords of an annulus with inner
radius D1 and outer radius D2, located at dr < D1 distance
from the centre increases monotonically with dr. (Proof in
Appendix E)
WLOG, we assume that Y2 must be part of the interfering
set cover. Next, for proving this claim, we subdivide the
angular region around point Y2 into four regions, demonstrated
in Figure 3a. For region I and IV we can show that the
maximum interference power from any flow, placed along any
line in that region, is upper bounded by the interference power
from a flow located on lZ as shown in Figure 3a. For any
random line l in Zone I, the next interfering nodes on either
side of Y2 are, say, P1 and P2 while the same for lZ are Z1, Z3,
respectively. From triangular geometry, ||XP1|| ≥||XZ1|| as
||Y2P1|| = ||Y2Z1|| = D1 whereas ||XP2|| ≥||XZ3|| (Due
to the presence of node Y4). Thus the interference power from
Z1 is greater than or equal to P1, and the interference from Z3
is greater or equal to the interference from P2. This way we
can show that the maximum interference power from a flow
located along lZ is always ahead of the same for l with same
number of interferer on either side of Y2. Furthermore, using
the properties of an annulus along with Lemma 4, it can be
easily shown that the length of l is less than the length of
lZ and therefore can support less number of simultaneously
interfering nodes than lZ. Thus, the maximum interference
power from a flow on l is less than the maximum interference
power from a flow on lZ. Due to symmetry, we can similarly
prove that the interference power from a flow located along any
line l in Zone IV is always upper bounded by the maximum
interference power from a flow located along lZ.
Now, for region II and III, we claim that interference power
from a flow located along any random line segment l is always
upper bounded by the maximum interference power of a flow
located along lW. In such cases, the power from P2 is less than
the power from Y3, whereas the power from P1 is greater than
the power from W1, or vice versa. Thus, there is no straight
forward dominance of the power from either line segment.
Instead the sum of the power dominates for lW. To show this,
we perform a brute force simulation algorithm where we first
add up the total interference power from Y3 and W1, and P1
and P2, respectively, which verified that the former is always
higher than later. Similarly, we perform simulation to show
that the maximum interference power from a flow along l is
always upper bounded by the maximum interference power
from a flow along the line lW.
APPENDIX E
PROOF OF LEMMA 4
Lets take a random chord of the annulus, located at dr
distance from the center with dr < D1. Then the length of
the chord is equal to g(dr) =
p
D2
2 −d2r −
p
D2
1 −d2r. Now
taking derivative of g(.) as follows.
g′(dr) = −
dr
q
D2
2 −d2r
+
dr
q
D2
1 −d2r
= −
1
q
( D2
dr )2 −1
+
1
q
( D1
dr )2 −1
> 0 as D2 > D1 and dr < D1
(10)
This implies that g(.) is a strictly increasing function of dr,
which proves our lemma.
REFERENCES
[1]
Ryan Williams, Andrea Gasparri, and Bhaskar Krishnamachari. Route
swarm: Wireless network optimization through mobility. In Proceedings
of the IEEE/RSJ International Conference on Intelligent Robots and
Systems (IROS), 2014. IEEE.
[2]
Jacques Penders, Lyuba Alboul, Ulf Witkowski, Amir Naghsh, Joan
Saez-Pons, Stefan Herbrechtsmeier, and Mohamed El-Habbal. A robot
swarm assisting a human fire-fighter. Advanced Robotics, 25(1-2):93–
117, 2011.
[3]
Sebastian Thrun, Scott Thayer, William Whittaker, Christopher Baker,
Wolfram Burgard, David Ferguson, Dirk Hahnel, D Montemerlo, Aaron
Morris, Zachary Omohundro, et al.
Autonomous exploration and
mapping of abandoned mines. IEEE Robotics & Automation Magazine,
11(4):79–91, 2004.
[4]
Hoa G Nguyen, Narek Pezeshkian, Michelle Raymond, Anoop Gupta,
and Joseph M Spector. Autonomous communication relays for tactical
robots. Technical report, DTIC Document, 2003.
[5]
Martin Haenggi.
Mean interference in hard-core wireless networks.
IEEE Communications Letters, 15(8):792–794, 2011.
[6]
Radha Krishna Ganti and Martin Haenggi. Interference and outage in
clustered wireless ad hoc networks. IEEE Transactions on Information
Theory, 55(9):4067–4086, 2009.
[7]
Anthony Busson and Guillaume Chelius.
Capacity and interference
modeling of csma/ca networks using ssi point processes. Telecommu-
nication Systems, 57(1):25–39, 2014.
[8]
Hesham ElSawy and Ekram Hossain. Modeling random csma wireless
networks in general fading environments. In Proceedings of the IEEE
International Conference on Communications (ICC), 2012. IEEE.
[9]
Anthony Busson and Guillaume Chelius. Point processes for interfer-
ence modeling in csma/ca ad-hoc networks. In Proceedings of the 6th
ACM symposium on Performance evaluation of wireless ad hoc, sensor,
and ubiquitous networks, 2009. ACM.
[10]
Paulo Cardieri.
Modeling interference in wireless ad hoc networks.
IEEE Communications Surveys & Tutorials, 12(4):551–572, 2010.
[11]
Ramin Hekmat and Piet Van Mieghem. Interference in wireless multi-
hop ad-hoc networks and its effect on network capacity.
Wireless
Networks, 10(4):389–399, 2004.
[12]
Giuseppe Bianchi. Performance analysis of the ieee 802.11 distributed
coordination function. IEEE Journal on Selected Areas in Communi-
cations, 18(3):535–547, 2000.
[13]
Theodore S Rappaport et al. Wireless communications: principles and
practice, volume 2. Prentice Hall PTR New Jersey, 1996.
[14]
Yunze Zeng, Parth H Pathak, and Prasant Mohapatra. A first look at
802.11 ac in action: energy efficiency and interference characterization.
In Proceedings of IFIP Networking Conference, 2014. IEEE.
[15]
Aysel Safak. Statistical analysis of the power sum of multiple correlated
log-normal components. IEEE Transactions on Vehicular Technology,
42(1):58–61, 1993.
[16]
Mhand Hifiand Rym M’hallah. A literature review on circle and sphere
packing problems: models and methodologies. Advances in Operations
Research, 2009, 2009.
[17]
Yuan Yan and Yasamin Mostofi.
Robotic router formation in real-
istic communication environments.
IEEE Transactions on Robotics,
28(4):810–827, 2012.