arXiv:1607.07848v1  [cs.RO]  26 Jul 2016
Towards Controllability of Wireless Network Quality using Mobile
Robotic Routers
Pradipta Ghosh∗, Raktim Pal† and Bhaskar Krishnamachari∗
∗Ming Hsieh Department of Electrical Engineering, University of Southern California {pradiptg, bkrishna}@usc.edu
†Department of Electrical and Computer Engineering, Georgia Institute of Technology {raktimnitt@gmail.com}
Abstract—We consider a problem of robotic router placement
and mobility control with the objective of formation and main-
tenance of an optimal communication network between a set of
transmitter-receiver pairs. In this scenario, the communication
path between any transmitter-receiver pair contains a prede-
termined set of mobile robotic routers nodes. The goal of this
work is to design an algorithm to optimize the positions of the
robotic nodes to improve the overall performance of the network.
We define the optimization metric to be the minimum of the
Signal to Interference plus Noise Ratios (SINR) over all the links.
In this manuscript, we propose two optimization algorithms to
solve this problem in a centralized and a decentralized manner,
respectively. We also demonstrate the performances of both
algorithms based on a set of simulation experiments.
I. INTRODUCTION
Distributed cooperation in mobile robotics is a very impor-
tant domain of research that mainly focuses on motion and
position configurations of a group of robots to perform a set
of tasks. To this end, researchers have proposed a range of
algorithms based on information exchanges between robots
such as swarming [1], flocking [2] and formation control [3].
The applications of cooperative robotics range across different
domains such as search and rescue operations, underground
mining, remote explorations, fire-fighting and military op-
erations. However, effective cooperation between robots in
any such application depends on the capacity and reliability
of the wireless communication infrastructure. Conversely, a
group of cooperative robots can be utilized to improve the
performance, capacity and reliability of a wireless communi-
cation infrastructure and even to build a controllable wireless
communication backbone. For example, a group of robots with
wireless communication and routing capabilities can form a
communication path between a sender and a receiver that are
unable to directly communicate with each other. In summary,
cooperative robotics and wireless networks are two symbiotic
fields of research.
Till last decade, there was no significant research on the
applications of cooperative robotics towards the advancement
and improvement of traditional communication infrastructures.
To this end, research on robotic routers and relay agents
in sensing and information routing is an emerging research
domain. An important and fundamental problem in this domain
is to guarantee an optimal, efficient and fair flow of informa-
tion in the network. Note that the definitions of optimality
and fairness themselves depend on the application scenarios.
For example, optimality can be defined in terms of signal to
interference and noise ratio (SINR), proper allocation of robots
between different flows, or bit error rates (BER). Another
challenge is to improve the overall performance and quality of
a network in a distributed manner instead of a centralized way.
All these problems are directly related to the proper placement
of robotic routers. Therefore, we primarily focus on optimizing
the robotic router placements in order to optimize the overall
network performance.
The goal of this work is to devise an algorithm for proper
placement and movement control of the robotic router nodes.
We follow three main steps towards achieving this goal. First,
we identify the advantages and disadvantages of different op-
timization metrics to achieve the goals. Some of the potential
choices are the expected transmission count metric (ETX), the
bit error rate (BER) and the signal-to-interference-plus-noise
ratio (SINR). However, we choose SINR as the optimization
metric because it is directly related to the communication
quality and because the rest of the metrics can be expressed as
a function of SINR. Second, we design a proper optimization
function that is directly related to the optimization goals. Third,
we propose two optimization techniques to efficiently solve
the optimization problem. The first technique is a centralized
algorithm which is based on a well known stochastic opti-
mization technique called Simulated Annealing ([4], [5]). The
second one is a distributed technique where each node makes
movement control decisions in a distributed manner in order
to improve the overall quality of the network. This technique
is subdivided into two major parts which we refer to as SINR
DaTa Accumulation Task (STAT) and Movement Direction
and GrAnularity ControL (MODAL), respectively. We also
present a simulation based performance and correctness anal-
ysis of our proposed methods.
II. PROBLEM FORMULATION
In this section, we discuss our problem formulation in de-
tails. First of all, for compactness, we summarize the symbols
used for this formulation in Table I. We assume that each
node of the network has a unique ID as well as proper lo-
calization techniques. The set of node locations is represented
as X = {(xi, yi) : i is the node ID}. We consider a network
with n transmitter-receiver pairs, which we also refer to as
the communication endpoints to avoid ambiguity, denoted by
T Xi = {Ti, Ri} where Ti and Ri are the IDs of ith sender and
receiver, respectively. For each transmitter-receiver pair, say
ith pair, we associate a set of robots, Mi. The total number
of robots in the system is m, i.e., Pn
i=1 |Mi| = m. We define
a ‘flow’ to be the set of links that form the communication
TABLE I: Symbol Table
Symbol
Description
X
Set of Node locations
XM
Set of Robots’ locations
Ti
Transmitter of Flow i
Ri
Receiver of Flow i
TXi
Communication Endpoints for flow i
i.e., {Ti, Ri}
Mi
Set of robots allocated to flow i
Lij
jth link of flow i, numbered from Ti
P (Lij)
Transmission Power for link Lij
d (Lij)
Length of link Lij
η
Path loss exponent
Pinter,k (Lij)
Transmission power of the link Lij’s
kth interference source
dinter,k (Lij)
Distance between the link Lij’s receiver end
and its kth interference source
ψdB, ψk
dB
Log normal fading effect ∼N (0, σ2)
PN (Lij)
Noise power for the link Lij
path between a transmitter and its corresponding receiver. For
example, Li = {Lij : j = 1, · · · , |Mi|+ 1} represents the ith
flow.
We select SINR as the optimizing quantity. The overall
performance of a network depends on the SINR quality of each
of the links. The link with the minimum SINR restricts the
overall performance of a network and acts as the bottleneck.
Therefore, an important step towards optimizing a network is
to try to improve the SINRs of each and every link. However,
SINRs of most of the links are not independent, thereby
making the optimization task complex. Ideally, we need an
optimization function that improves the overall performance
of a network while considering the link dependencies. In this
context, our optimization goal is to maximize the minimum
SINR of a network. We define the cost function for each flow,
say {i}, to be as follows.
Ci(XM) = min
j
SINR (Lij, XM)
(1)
where XM ⊂X is the set of all robots’ locations and
SINR (Lij, XM) denotes the SINR of link Lij for the
configuration XM. Therefore, the overall cost function for the
entire network is
C(XM) = min
i
Ci(XM)
(2)
Now, the optimization goal is as follows.
maximize
XM
{C(XM)}
(3)
Using simple path loss model and log-normal fading
model [6], the SINR of a link, Lij, can be mathematically
represented as follows.
P (Lij) d (Lij)−η 10
ψdB
10
P
k
Pinter,k (Lij) dinter,k (Lij)−η 10
ψk
dB
10
+ PN (Lij)
(4)
where the meaning of each symbol is illustrated in Table I. We
simplify this problem by assuming that all robot’s transmission
power are identical, say PM, all sender’s transmission power
are identical, say PT , and the noise powers are constant, say
PN. In this work, we are mainly interested in demonstrating
a proof of concept of robotic router placement with the goal
of SINR optimization. Thus, we further simplify the model
by ignoring the fading effect i.e. taking ψdB = 0, ψk
dB = 0
to deal with only the mean power value. Including the fading
effect will only delay the convergence of the process. Our
algorithms work for any value of η. However, all the experi-
ments presented in this paper are performed with η = 2. Note
that we do not assume the communication endpoints to be
static i.e., the endpoint can be mobile.
A. Sample Problem:
Let’s consider a very simple configuration with only two
pairs of transmitter-receiver. We deploy four robotic nodes,
which facilitate communication between them, with two robots
for each flow as in Figure 1. There are total 8 nodes with IDs: 1
to 8 respectively. In this example, T X1 = {T1, R1} = {1, 4},
T X2 = {T2, R2} = {5, 8}, M1 = {2, 3} and M2 = {6, 7}.
The transmitters and the receivers are assumed to be static with
coordinates {xi, yi} for i = 1, 4, 5, 8 and the robotic nodes are
mobile with coordinates {xi, yi} for i = 2, 3, 6, 7.
Fig. 1: A Simple Example Scenario
In Table II, we present a list of interfering nodes for each
link, which is essential to calculate the SINRs.
TABLE II: Interference Table
Link ID
Interfering
Link ID
Interfering
Node IDs
Node IDs
L12
3, 5, 6, 7
L56
1, 2, 3, 7
L23
1, 5, 6, 7
L67
1, 2, 3, 5
L34
1, 2, 5, 6, 7
L78
1, 2, 3, 5, 6
The SINRs at node 2, 3 and 4 are represented as:
SINR(L12), SINR(L23), SINR(L34), respectively.
SINR(L12) =
PT d−η
12
PT d−η
52 + PM

d−η
32 + d−η
62 + d−η
72

+ PN
(5)
SINR(L23) =
PM d−η
23
PT

d−η
13 + d−η
53

+ PM

d−η
63 + d−η
73

+ PN
(6)
SINR(L34) =
PMd−η
34
PT

d−η
14 + d−η
54

+ PM

d−η
24 + d−η
64
+ d−η
74

+ PN
(7)
where dij denotes the euclidean distance between node i and
node j. Similarly, we can write the SINR at nodes 6, 7 and
8 are represented as SINR(L56), SINR(L67), SINR(L78),
respectively. We assume that there exists no collision avoid-
ance mechanism[7] to avoid interference. While we acknowl-
edge that this assumption is unreasonable for real systems,
we argue that if our algorithm can handle the worst possible
case of interference (i.e., without any collision avoidance
mechanism), it will also be able to work well in CSMA based
systems or equivalent systems. Now, the optimization goal is
to maximize the minimum of these six SINR values.
B. Properties of the Optimization Function:
Similar to any optimization problem, it is important to
understand the behavior of our optimization function in order
to identify suitable optimization tools and techniques. To
analyze the optimization function proposed in (3), we take
a scenario with two flows, where only one mobile node is
allocated to each flow as in Figure 2. In this process, we move
the robotic routers along the straight line between the sender
and the receiver of the respective flow. We plot the minimum
SINR in the network as a function of the coordinates of these
two mobile nodes in Figure 3. From the figure, it is clear
that the optimization function is neither convex nor concave.
It has two peaks with different performance, corresponding
to two unique sets of robotic nodes’ positions.
From this
Fig. 2: Simplified Problem
Fig. 3: Plot of minimum SINR
observation, we conclude that the original generalized problem
is non-convex. Henceforth, we can not use traditional convex
optimization algorithms. Note that, the optimization problem
may be convex under some special circumstances.
III. A CENTRALIZED SOLUTION
In this section, we present a centralized method of solving
this problem. While centralized ways are much easier and
straightforward, they are less practical than decentralized ap-
proaches.
A. Simulated Annealing based approach
In this method, we assume that there exists either a central
server or a leader node that can communicate with all nodes
in the system. The central server has online knowledge of the
positions of all the nodes, X, and SINRs of all the links in
the network. The central server can either calculate the SINRs
of all links using proper signal strength model or directly
collect the SINR measurements from each individual nodes.
However, in this paper, we use simple path loss model [6]
for simplicity, while more realistic signal strength modeling
is left as a future work. For the optimization purpose, we
use a well-known stochastic global optimization algorithm
called Simulated Annealing ([4], [5]) which can be used to
find out the global optimum of complex problems with a
large search space. At each step of this algorithm, a new set
X′
M is generated. However, each new point (x′, y′) should
be in the neighborhood of the original point (x, y), i.e.,
(x′, y′) ∈N (x, y), where N(· , · ) refers to the neighborhood
of a location. If the set, X′
M, has a higher cost function than
XM, the new set X′
M is accepted unconditionally. In other
words, if C(X′
M) > C(XM), new XM = X′
M. However,
if C(X′
M) ≤C(XM), X′
M is accepted probabilistically using
the Metropolis criterion. According to the Metropolis criterion,
the probability of X′
M being selected is
p = min
 
1, exp
"
−C (XM) −C X′
M


T
#!
(8)
Initially, when T is high, there is a greater probability of
making downhill moves, which allows the algorithm to fully
explore the space. We choose the proper annealing schedule
and the number of iterations based on a number of simulations
and by taking into account the percentage of uphill moves
versus the temperature.
(a)
(b)
Fig. 4: Simulation plots for Simulated Annealing (a) Initial
Configuration (b) Configuration after 100 Iterations
B. Simulation
We performed a set of simulations on MATLAB 8.1, on
a machine with 3.40 GHz Intel i7 processor and 12GB
RAM to check the convergence of the algorithm for different
initial configurations. For this experiment, we considered the
topology introduced in Figure 1 with the transmitters fixed at
co-ordinates (−10, 0) and (0, 10) and the respective receivers
fixed at (10, 0) and (0, −10). We observed that the Simulated
Annealing algorithm converges to the same final configuration
irrespective of different initial configurations of the robots.
Table III illustrates the final SINR values of different links
of the network for different initial configurations and noise
values. The initial and final configurations of the robotic nodes
for one of the simulation instances is presented in Figure 4.
It is clear from the simulation results that the SINR values of
all the links are equal after the optimization process, which
is quite intuitive from the symmetry in the network structure.
The network cannot be further improved in terms of overall
performance.
IV. DISTRIBUTED OPTIMIZATION
In this section, we propose a new distributed approach for
solving the optimization problem. In this distributed approach,
each mobile node makes local decisions based on SINR
measurements and moves according to those decisions in order
to improve the overall quality of the network.
Step 1. Each node calculates the SINRs of its incoming links
and communicates these locally calculated SINR values with
all the other nodes that belongs to the same flow, whenever a
SINR is updated.
We assume that every node have the necessary hardware
and techniques to calculate the SINRs.
Step 2. Each node utilizes the gathered SINR information to
determine whether it is a part of the link that has the lowest
SINR (which we refer to as the bottleneck link) or the second
lowest SINR (which we refer to as the pseudo-bottleneck link)
for the respective flow.
We refer to the Steps 1 and 2 together as the SINR DaTa
Accumulation Task (STAT).
Step 3. If a robotic node v is a part of the bottleneck link
(or the pseudo-bottleneck link) of a flow i, it makes a local
control decision about its movement and moves accordingly, in
order to improve the link’s SINR, if an improvement is possible
without worsening the flow cost i.e., Ci(XM).
We consider the second lowest SINR link to add some
diversity in our algorithm so that it doesn’t get stuck when
no improvement is possible by just moving the bottleneck
link’s mobile endpoints. We refer to this step as the Movement
Direction and GrAnularity ControL (MODAL). In this step,
each node decides the movement direction and granularity as
follows.
We discretize the movements into steps of δ > 0, which
needs to be carefully chosen. The value of δ can be adapted
based on past movement history in order to increase the speed
of convergence. However, in this paper, we use a constant
value of δ for simplicity. Therefore, at each step, a robot {v}
can move to any point of the circumference of a circle with
radius δ centered at the robot’s current location. We denote
this circle as Bδ{xv}, where xv = (xv, yv) is the current
location of the robot {v}. To determine the best direction of
movement, each robot needs information about link qualities
at every possible future locations. Now, assume that each
robot have necessary SINR information about all potential
future locations. Then, a robot {v} simply employs a potential
based controller for the movements by setting the potential
of each future location, say x′v = (x′
v, y′
v), to be negative
of the cost of the flow for the new configuration, Ci(X′
M)
where X′
M = {XM \ xv} ∪x′v and i is the flow that
the robot is part of. Therefore, the gradient of the potential
will determine the best direction. To gather information about
SINR in future locations, we propose two different strategies.
First, we select a finite set of uniformly distributed points,
say xf
v, from the set of possible future locations. In our case,
the set of possible future locations is the circumference of
the circle Bδ{xv}. Thus we choose a set of points, say 36
points, over the circumference that are equidistant. Now, in
the first proposed strategy, a robot simply moves to each of
these points x ∈xf
v and calculates the SINR, assuming that
the rest of the network is unchanged. Although this method
is straightforward, the convergence time of this method is
very long as each iteration needs a significant amount of time
and it is not efficient in terms of energy consumption. In the
second method, each robot maintains a SINR belief model
of the network and updates it after every movement. Based
on that model, a robot estimates the SINRs for each of the
potential locations. However, this SINR belief model is part of
our ongoing work. Both parts of our algorithm i.e., STAT and
−10
−8
−6
−4
−2
0
2
4
6
8
10
−10
−8
−6
−4
−2
0
2
4
6
8
10
Iteration= 1 
(a)
−10
−8
−6
−4
−2
0
2
4
6
8
10
−10
−8
−6
−4
−2
0
2
4
6
8
10
Iteration= 100 
(b)
Fig. 5: Simulation plots (a) Initial Configuration (b) Configu-
ration after 100 Iterations
MODAL, are repeated until further improvement is possible
for neither the link with lowest SINR nor the link with second
lowest SINR. The process will restart if any robot senses a
change in the configuration.
A. Simulation
To check the performance and determine the properties
of this algorithm, we performed a set of simulation exper-
TABLE III: SINR values of the different links after Simulated Annealing
Initial Configuration of Robots
Final SINR on each link
(x2, y2)
(x3, y3)
(x6, y6)
(x7, y7)
Noise
Link 12
Link 23
Link 34
Link 56
Link 67
Link 78
(0, 0)
(0, 2)
(0, 0)
(0.5, 0)
0.6
0.0327
0.0327
0.0327
0.0327
0.0327
0.0327
(0, 0)
(2, 0)
(0, 0)
(0, 0)
1.0
0.0200
0.0200
0.0200
0.0200
0.0200
0.0200
(0, -1)
(0, 1 )
(0, 0)
(0, 0)
2.0
0.0108
0.0108
0.0108
0.0108
0.0108
0.0108
(0, 0)
(3, 0)
(0, 1)
(-1, 0)
3.0
0.0073
0.0073
0.0073
0.0073
0.0073
0.0073
(0, 2)
(0, 0)
(0, 0)
(-1, 0)
4.0
0.0055
0.0055
0.0055
0.0055
0.0055
0.0055
(0, 0)
(0, 0)
(0, 0)
(0, 0)
10.0
0.0022
0.0022
0.0022
0.0022
0.0022
0.0022
iments with the same initial configuration as described in
section III-B. One instance of such experiments is illustrated
in Figure 5. As the figure suggests, the result is strikingly
similar to the one obtained from the centralized approach.
Also, with the different initial configuration as in Table III,
the final SINRs are exactly same as in Table III.
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 1 
(a)
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 75 
(b)
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 150 
(c)
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 200 
(d)
Fig. 6: Simulation plots: Configuration after (a) 1 Iteration (b)
75 Iterations (c) 150 Iterations (d) 200 Iterations
So far, we have dealt with only two flow optimization prob-
lems with static endpoints, which are very simple compared to
problems with higher complexity and multiple flows. In order
to test the performance of our algorithm in a more complex
framework, we increased the complexity of the network by
adding two extra flows with two robots assigned to each
of the flow. The sender-receiver pair for flow 3 are initially
located at (10, 10) and (−10, −10), and for flow 4 are located
at (−10, 10) and (10, −10). We introduce random mobility
pattern to Flow 1’s transmitter, Flow 2’s receiver and Flow
3’s receiver. The results of a simulation instance with this
configuration is presented in Figure 6. The figure demonstrates
that our algorithm works well for a network with four flows
with total 16 node and mobile endpoints. Figure 7 illustrates
the convergences of the flow-wise minimum SINR values over
time. It is clear from Figure 7 that the minimum SINR of
similar flows, i.e., Flow 1 and Flow 2, or Flow 3 and Flow 4,
converges to the same values when the flow endpoints are
static. Once the mobility is introduced, the SINRs change
based on the new positions of the communication endpoints.
We have also tested our algorithm for networks that are
asymmetric and our algorithm performs equally well in those
cases. However, we do not present those results in this paper
to conform with the space limitation.
0
20
40
60
80
100
120
140
160
180
200
−101.33
−101.36
−101.39
−101.42
−101.45
−101.48
Min SINR
Iteration
SINR in dB
 
 
Flow 1
Flow 2
Flow 3
Flow 4
Fig. 7: Variation in the minimum SINR of each flow over time
V. RELATED WORK
In this section, we provide a brief overview of the existing
research works related to our field of interest. Most of the
significant research on robotic wireless router related topics
are very recent. Yan and Mostofi([8], [9]) are among the few
researchers to work on the robotic router related problems.
They focused on robotic router placement optimization in
order to maintain connectivity between an user and a base
station. This optimization problem is mainly focused on min-
imization of bit-error rate for two scenarios of multi-hop and
diversity. They also demonstrated that optimizations based on
the Fiedler eigenvalue, instead of bit-error rate, result in a
performance loss. In these works, they used an extension of
the channel modeling technique introduced in ([10], [11]).
However, they ignored the effect of interference in their model
and focused on a single flow between a single receiver-
transmitter pair. Unlike these works, our proposed method is
based on SINR, which is more generalized than bit-error rate
approach. Also, we optimize multiple flows simultaneously,
instead of focusing on a single flow. Tekdas et al.[12], also
focused on similar problem and proposed two motion planning
algorithms based on known user motion and unknown-random
adversarial user motion, respectively. Among other state-of-
the-arts, the decentralized algorithm based on super-gradient
and decentralized computation of Feidler eigenvector by De-
Gennaro and Jadbabaie[13] is mentionable. Stump, Jadbabaie
and Kumar [14] also developed a framework to control a
team of robots based on two metrics: the Fiedler value of
the weighted Laplacian matrix and the k-connectivity matrix.
However, Yan and Mostofi[8] showed that Fiedler eigenvalue
does not reflect the true reception quality, which is crucial in
wireless networks.
Among other works, the DARPA LANdroids program [15]
is mentionable. Tactical communication enhancement in urban
environments is the main goal of this program. Towards this
goal, they tried to develop pocket-sized intelligent autonomous
robotic radio relay nodes, LANdroids, that are inexpensive.
LANdroids are used to mitigate the communications problems
in urban settings, such as multipath effect, by acting like
relay node into shadows, using autonomous movement and
intelligent control algorithms. Dixon and Frew[16] proposed
a decentralized mobility controller based on maximizing the
capacity of a local 3-node network in order to maximize the
end to end capacity of the entire communication chain. They
used measurements of the local signal to noise ratio for this
purpose. A Disjunctive Programming Approach is presented
in [17]. Among other works, the work of Vieira, Govindan
and Sukhatme [18] is mentionable. In contrast, our proposed
method is based on signal to interference and noise ratios and
focuses on multiple flow optimization, which is more practical
and generalized.
In [19], Williams, Gasparri and Krishnamachari presented a
hybrid architecture called INSPIRE, with two separate planes
called Physical Control Plane (PCP) and Information Control
Plane (ICP). Their goal was to improve and optimize the
network between multiple pair of senders and receivers using
a group of robots and using ETX as a metric. They used ETX
to determine the allocation of nodes among different flows,
while the mobility framework is simply to place the robots
evenly along the line segments joining the flow endpoints.
Although our application contexts are the same, our mobility
formulation as well as problem formulation are completely
different. In our proposed model, the movement of the robots
are directly controlled by the link qualities (more specifically,
SINR) and, thus, is much practical.
VI. CONCLUSION
In this paper, we have considered a problem of proper
placement and control of mobile robotic nodes in order to
optimize the performance of a wireless network. We have
devised an optimization function and based on that function,
we have proposed a centralized and a distributed method
of robotic node placement and control that maximizes our
objective function. Through a set of simulation experiments,
we have demonstrated the performance and convergence of our
algorithms. However, due to space constraints, we have left
out detailed description of some key portions of our algorithm
such as the SINR modeling techniques as well as complexity
and optimality analysis of our algorithm. Therefore, our future
direction will be to flesh out the details of an adaptive SINR
model as well a thorough analysis of our algorithm. This
work is also a foundation of our future goal to develop an
algorithm for adaptive node allocation and placement among
different flows in order to handle various dynamic situation in
the network such as flow addition or deletion and increase or
decrease in flow demands. Another future direction would be
a practical implementation of our algorithms on a real robotic
network testbed.
REFERENCES
[1] V. Gazi, “Stability analysis of swarms,” Ph.D. dissertation, The Ohio
State University, 2002.
[2] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms
and theory,” IEEE Transactions on Automatic Control, vol. 51, no. 3,
pp. 401–420, 2006.
[3] J. A. Fax and R. M. Murray, “Information flow and cooperative
control of vehicle formations,” IEEE Transactions on Automatic Control,
vol. 49, no. 9, pp. 1465–1476, 2004.
[4] P. J. M. Van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory
and Applications.
Springer, 1987.
[5] E. Aarts and J. Korst, Simulated annealing and Boltzmann machines: a
stochastic approach to combinatorial optimization and neural comput-
ing.
Wiley, 1988.
[6] T. S. Rappaport, Wireless communications: principles and practice.
prentice hall PTR New Jersey, 1996, vol. 2.
[7] G. Bianchi, “Performance analysis of the ieee 802.11 distributed coor-
dination function,” IEEE Journal on Selected Areas in Communications,
vol. 18, no. 3, pp. 535–547, 2000.
[8] Y. Yan and Y. Mostofi, “Robotic router formation-a bit error rate
approach,” in Proceedings of the 2010 Military Communications Con-
ference (MILCOM).
[9] ——, “Robotic router formation in realistic communication environ-
ments,” IEEE Transactions on Robotics, vol. 28, no. 4, pp. 810–827,
2012.
[10] Y. Mostofi, M. Malmirchegini, and A. Ghaffarkhah, “Estimation of
communication signal strength in robotic networks,” in Proceedings of
the IEEE International Conference on Robotics and Automation (ICRA),
2010.
[11] M. Malmirchegini and Y. Mostofi, “On the spatial predictability of com-
munication channels,” IEEE Transactions on Wireless Communications,
vol. 11, no. 3, pp. 964–978, 2012.
[12] O. Tekdas, W. Yang, and V. Isler, “Robotic routers: Algorithms and im-
plementation,” The International Journal of Robotics Research, vol. 29,
no. 1, pp. 110–126, 2010.
[13] M. C. DeGennaro and A. Jadbabaie, “Decentralized control of connectiv-
ity for multi-agent systems,” in Proceedings of the 45th IEEE Conference
on Decision and Control, 2006.
[14] E. Stump, A. Jadbabaie, and V. Kumar, “Connectivity management
in mobile robot teams,” in Proceedings of the IEEE International
Conference on Robotics and Automation (ICRA), 2008.
[15] M. McClure, D. R. Corbett, and D. W. Gage, “The darpa landroids
program,” in Proceedings of the SPIE Defense, Security, and Sensing,
2009.
[16] C. Dixon and E. W. Frew, “Maintaining optimal communication chains
in robotic sensor networks using mobility control,” Mobile Networks
and Applications, vol. 14, no. 3, pp. 281–291, 2009.
[17] N. Bezzo, R. Fierro, A. Swingler, and S. Ferrari, “A disjunctive pro-
gramming approach for motion planning of mobile router networks,”
International Journal of Robotics and Automation, vol. 26, no. 1, pp.
13–25, 2011.
[18] M. A. M. Vieira, R. Govindan, and G. S. Sukhatme, “An autonomous
Wireless Networked Robotics System for backbone deployment in
highly-obstructed environments,” Ad Hoc Networks, vol. 11, no. 7, pp.
1963–1974, Sep. 2013.
[19] R. K. Williams, A. Gasparri, and B. Krishnamachari, “Route swarm:
Wireless network optimization through mobility,” in Proceedings of
the IEEE International Conference on Intelligent Robots and Systems
(IROS), 2014.
This figure "gmax.jpg" is available in "jpg"
 format from:
http://arxiv.org/ps/1607.07848v1
arXiv:1607.07848v1  [cs.RO]  26 Jul 2016
Towards Controllability of Wireless Network Quality using Mobile
Robotic Routers
Pradipta Ghosh∗, Raktim Pal† and Bhaskar Krishnamachari∗
∗Ming Hsieh Department of Electrical Engineering, University of Southern California {pradiptg, bkrishna}@usc.edu
†Department of Electrical and Computer Engineering, Georgia Institute of Technology {raktimnitt@gmail.com}
Abstract—We consider a problem of robotic router placement
and mobility control with the objective of formation and main-
tenance of an optimal communication network between a set of
transmitter-receiver pairs. In this scenario, the communication
path between any transmitter-receiver pair contains a prede-
termined set of mobile robotic routers nodes. The goal of this
work is to design an algorithm to optimize the positions of the
robotic nodes to improve the overall performance of the network.
We define the optimization metric to be the minimum of the
Signal to Interference plus Noise Ratios (SINR) over all the links.
In this manuscript, we propose two optimization algorithms to
solve this problem in a centralized and a decentralized manner,
respectively. We also demonstrate the performances of both
algorithms based on a set of simulation experiments.
I. INTRODUCTION
Distributed cooperation in mobile robotics is a very impor-
tant domain of research that mainly focuses on motion and
position configurations of a group of robots to perform a set
of tasks. To this end, researchers have proposed a range of
algorithms based on information exchanges between robots
such as swarming [1], flocking [2] and formation control [3].
The applications of cooperative robotics range across different
domains such as search and rescue operations, underground
mining, remote explorations, fire-fighting and military op-
erations. However, effective cooperation between robots in
any such application depends on the capacity and reliability
of the wireless communication infrastructure. Conversely, a
group of cooperative robots can be utilized to improve the
performance, capacity and reliability of a wireless communi-
cation infrastructure and even to build a controllable wireless
communication backbone. For example, a group of robots with
wireless communication and routing capabilities can form a
communication path between a sender and a receiver that are
unable to directly communicate with each other. In summary,
cooperative robotics and wireless networks are two symbiotic
fields of research.
Till last decade, there was no significant research on the
applications of cooperative robotics towards the advancement
and improvement of traditional communication infrastructures.
To this end, research on robotic routers and relay agents
in sensing and information routing is an emerging research
domain. An important and fundamental problem in this domain
is to guarantee an optimal, efficient and fair flow of informa-
tion in the network. Note that the definitions of optimality
and fairness themselves depend on the application scenarios.
For example, optimality can be defined in terms of signal to
interference and noise ratio (SINR), proper allocation of robots
between different flows, or bit error rates (BER). Another
challenge is to improve the overall performance and quality of
a network in a distributed manner instead of a centralized way.
All these problems are directly related to the proper placement
of robotic routers. Therefore, we primarily focus on optimizing
the robotic router placements in order to optimize the overall
network performance.
The goal of this work is to devise an algorithm for proper
placement and movement control of the robotic router nodes.
We follow three main steps towards achieving this goal. First,
we identify the advantages and disadvantages of different op-
timization metrics to achieve the goals. Some of the potential
choices are the expected transmission count metric (ETX), the
bit error rate (BER) and the signal-to-interference-plus-noise
ratio (SINR). However, we choose SINR as the optimization
metric because it is directly related to the communication
quality and because the rest of the metrics can be expressed as
a function of SINR. Second, we design a proper optimization
function that is directly related to the optimization goals. Third,
we propose two optimization techniques to efficiently solve
the optimization problem. The first technique is a centralized
algorithm which is based on a well known stochastic opti-
mization technique called Simulated Annealing ([4], [5]). The
second one is a distributed technique where each node makes
movement control decisions in a distributed manner in order
to improve the overall quality of the network. This technique
is subdivided into two major parts which we refer to as SINR
DaTa Accumulation Task (STAT) and Movement Direction
and GrAnularity ControL (MODAL), respectively. We also
present a simulation based performance and correctness anal-
ysis of our proposed methods.
II. PROBLEM FORMULATION
In this section, we discuss our problem formulation in de-
tails. First of all, for compactness, we summarize the symbols
used for this formulation in Table I. We assume that each
node of the network has a unique ID as well as proper lo-
calization techniques. The set of node locations is represented
as X = {(xi, yi) : i is the node ID}. We consider a network
with n transmitter-receiver pairs, which we also refer to as
the communication endpoints to avoid ambiguity, denoted by
T Xi = {Ti, Ri} where Ti and Ri are the IDs of ith sender and
receiver, respectively. For each transmitter-receiver pair, say
ith pair, we associate a set of robots, Mi. The total number
of robots in the system is m, i.e., Pn
i=1 |Mi| = m. We define
a ‘flow’ to be the set of links that form the communication
TABLE I: Symbol Table
Symbol
Description
X
Set of Node locations
XM
Set of Robots’ locations
Ti
Transmitter of Flow i
Ri
Receiver of Flow i
TXi
Communication Endpoints for flow i
i.e., {Ti, Ri}
Mi
Set of robots allocated to flow i
Lij
jth link of flow i, numbered from Ti
P (Lij)
Transmission Power for link Lij
d (Lij)
Length of link Lij
η
Path loss exponent
Pinter,k (Lij)
Transmission power of the link Lij’s
kth interference source
dinter,k (Lij)
Distance between the link Lij’s receiver end
and its kth interference source
ψdB, ψk
dB
Log normal fading effect ∼N (0, σ2)
PN (Lij)
Noise power for the link Lij
path between a transmitter and its corresponding receiver. For
example, Li = {Lij : j = 1, · · · , |Mi|+ 1} represents the ith
flow.
We select SINR as the optimizing quantity. The overall
performance of a network depends on the SINR quality of each
of the links. The link with the minimum SINR restricts the
overall performance of a network and acts as the bottleneck.
Therefore, an important step towards optimizing a network is
to try to improve the SINRs of each and every link. However,
SINRs of most of the links are not independent, thereby
making the optimization task complex. Ideally, we need an
optimization function that improves the overall performance
of a network while considering the link dependencies. In this
context, our optimization goal is to maximize the minimum
SINR of a network. We define the cost function for each flow,
say {i}, to be as follows.
Ci(XM) = min
j
SINR (Lij, XM)
(1)
where XM ⊂X is the set of all robots’ locations and
SINR (Lij, XM) denotes the SINR of link Lij for the
configuration XM. Therefore, the overall cost function for the
entire network is
C(XM) = min
i
Ci(XM)
(2)
Now, the optimization goal is as follows.
maximize
XM
{C(XM)}
(3)
Using simple path loss model and log-normal fading
model [6], the SINR of a link, Lij, can be mathematically
represented as follows.
P (Lij) d (Lij)−η 10
ψdB
10
P
k
Pinter,k (Lij) dinter,k (Lij)−η 10
ψk
dB
10
+ PN (Lij)
(4)
where the meaning of each symbol is illustrated in Table I. We
simplify this problem by assuming that all robot’s transmission
power are identical, say PM, all sender’s transmission power
are identical, say PT , and the noise powers are constant, say
PN. In this work, we are mainly interested in demonstrating
a proof of concept of robotic router placement with the goal
of SINR optimization. Thus, we further simplify the model
by ignoring the fading effect i.e. taking ψdB = 0, ψk
dB = 0
to deal with only the mean power value. Including the fading
effect will only delay the convergence of the process. Our
algorithms work for any value of η. However, all the experi-
ments presented in this paper are performed with η = 2. Note
that we do not assume the communication endpoints to be
static i.e., the endpoint can be mobile.
A. Sample Problem:
Let’s consider a very simple configuration with only two
pairs of transmitter-receiver. We deploy four robotic nodes,
which facilitate communication between them, with two robots
for each flow as in Figure 1. There are total 8 nodes with IDs: 1
to 8 respectively. In this example, T X1 = {T1, R1} = {1, 4},
T X2 = {T2, R2} = {5, 8}, M1 = {2, 3} and M2 = {6, 7}.
The transmitters and the receivers are assumed to be static with
coordinates {xi, yi} for i = 1, 4, 5, 8 and the robotic nodes are
mobile with coordinates {xi, yi} for i = 2, 3, 6, 7.
Fig. 1: A Simple Example Scenario
In Table II, we present a list of interfering nodes for each
link, which is essential to calculate the SINRs.
TABLE II: Interference Table
Link ID
Interfering
Link ID
Interfering
Node IDs
Node IDs
L12
3, 5, 6, 7
L56
1, 2, 3, 7
L23
1, 5, 6, 7
L67
1, 2, 3, 5
L34
1, 2, 5, 6, 7
L78
1, 2, 3, 5, 6
The SINRs at node 2, 3 and 4 are represented as:
SINR(L12), SINR(L23), SINR(L34), respectively.
SINR(L12) =
PT d−η
12
PT d−η
52 + PM

d−η
32 + d−η
62 + d−η
72

+ PN
(5)
SINR(L23) =
PM d−η
23
PT

d−η
13 + d−η
53

+ PM

d−η
63 + d−η
73

+ PN
(6)
SINR(L34) =
PMd−η
34
PT

d−η
14 + d−η
54

+ PM

d−η
24 + d−η
64
+ d−η
74

+ PN
(7)
where dij denotes the euclidean distance between node i and
node j. Similarly, we can write the SINR at nodes 6, 7 and
8 are represented as SINR(L56), SINR(L67), SINR(L78),
respectively. We assume that there exists no collision avoid-
ance mechanism[7] to avoid interference. While we acknowl-
edge that this assumption is unreasonable for real systems,
we argue that if our algorithm can handle the worst possible
case of interference (i.e., without any collision avoidance
mechanism), it will also be able to work well in CSMA based
systems or equivalent systems. Now, the optimization goal is
to maximize the minimum of these six SINR values.
B. Properties of the Optimization Function:
Similar to any optimization problem, it is important to
understand the behavior of our optimization function in order
to identify suitable optimization tools and techniques. To
analyze the optimization function proposed in (3), we take
a scenario with two flows, where only one mobile node is
allocated to each flow as in Figure 2. In this process, we move
the robotic routers along the straight line between the sender
and the receiver of the respective flow. We plot the minimum
SINR in the network as a function of the coordinates of these
two mobile nodes in Figure 3. From the figure, it is clear
that the optimization function is neither convex nor concave.
It has two peaks with different performance, corresponding
to two unique sets of robotic nodes’ positions.
From this
Fig. 2: Simplified Problem
Fig. 3: Plot of minimum SINR
observation, we conclude that the original generalized problem
is non-convex. Henceforth, we can not use traditional convex
optimization algorithms. Note that, the optimization problem
may be convex under some special circumstances.
III. A CENTRALIZED SOLUTION
In this section, we present a centralized method of solving
this problem. While centralized ways are much easier and
straightforward, they are less practical than decentralized ap-
proaches.
A. Simulated Annealing based approach
In this method, we assume that there exists either a central
server or a leader node that can communicate with all nodes
in the system. The central server has online knowledge of the
positions of all the nodes, X, and SINRs of all the links in
the network. The central server can either calculate the SINRs
of all links using proper signal strength model or directly
collect the SINR measurements from each individual nodes.
However, in this paper, we use simple path loss model [6]
for simplicity, while more realistic signal strength modeling
is left as a future work. For the optimization purpose, we
use a well-known stochastic global optimization algorithm
called Simulated Annealing ([4], [5]) which can be used to
find out the global optimum of complex problems with a
large search space. At each step of this algorithm, a new set
X′
M is generated. However, each new point (x′, y′) should
be in the neighborhood of the original point (x, y), i.e.,
(x′, y′) ∈N (x, y), where N(· , · ) refers to the neighborhood
of a location. If the set, X′
M, has a higher cost function than
XM, the new set X′
M is accepted unconditionally. In other
words, if C(X′
M) > C(XM), new XM = X′
M. However,
if C(X′
M) ≤C(XM), X′
M is accepted probabilistically using
the Metropolis criterion. According to the Metropolis criterion,
the probability of X′
M being selected is
p = min
 
1, exp
"
−C (XM) −C X′
M


T
#!
(8)
Initially, when T is high, there is a greater probability of
making downhill moves, which allows the algorithm to fully
explore the space. We choose the proper annealing schedule
and the number of iterations based on a number of simulations
and by taking into account the percentage of uphill moves
versus the temperature.
(a)
(b)
Fig. 4: Simulation plots for Simulated Annealing (a) Initial
Configuration (b) Configuration after 100 Iterations
B. Simulation
We performed a set of simulations on MATLAB 8.1, on
a machine with 3.40 GHz Intel i7 processor and 12GB
RAM to check the convergence of the algorithm for different
initial configurations. For this experiment, we considered the
topology introduced in Figure 1 with the transmitters fixed at
co-ordinates (−10, 0) and (0, 10) and the respective receivers
fixed at (10, 0) and (0, −10). We observed that the Simulated
Annealing algorithm converges to the same final configuration
irrespective of different initial configurations of the robots.
Table III illustrates the final SINR values of different links
of the network for different initial configurations and noise
values. The initial and final configurations of the robotic nodes
for one of the simulation instances is presented in Figure 4.
It is clear from the simulation results that the SINR values of
all the links are equal after the optimization process, which
is quite intuitive from the symmetry in the network structure.
The network cannot be further improved in terms of overall
performance.
IV. DISTRIBUTED OPTIMIZATION
In this section, we propose a new distributed approach for
solving the optimization problem. In this distributed approach,
each mobile node makes local decisions based on SINR
measurements and moves according to those decisions in order
to improve the overall quality of the network.
Step 1. Each node calculates the SINRs of its incoming links
and communicates these locally calculated SINR values with
all the other nodes that belongs to the same flow, whenever a
SINR is updated.
We assume that every node have the necessary hardware
and techniques to calculate the SINRs.
Step 2. Each node utilizes the gathered SINR information to
determine whether it is a part of the link that has the lowest
SINR (which we refer to as the bottleneck link) or the second
lowest SINR (which we refer to as the pseudo-bottleneck link)
for the respective flow.
We refer to the Steps 1 and 2 together as the SINR DaTa
Accumulation Task (STAT).
Step 3. If a robotic node v is a part of the bottleneck link
(or the pseudo-bottleneck link) of a flow i, it makes a local
control decision about its movement and moves accordingly, in
order to improve the link’s SINR, if an improvement is possible
without worsening the flow cost i.e., Ci(XM).
We consider the second lowest SINR link to add some
diversity in our algorithm so that it doesn’t get stuck when
no improvement is possible by just moving the bottleneck
link’s mobile endpoints. We refer to this step as the Movement
Direction and GrAnularity ControL (MODAL). In this step,
each node decides the movement direction and granularity as
follows.
We discretize the movements into steps of δ > 0, which
needs to be carefully chosen. The value of δ can be adapted
based on past movement history in order to increase the speed
of convergence. However, in this paper, we use a constant
value of δ for simplicity. Therefore, at each step, a robot {v}
can move to any point of the circumference of a circle with
radius δ centered at the robot’s current location. We denote
this circle as Bδ{xv}, where xv = (xv, yv) is the current
location of the robot {v}. To determine the best direction of
movement, each robot needs information about link qualities
at every possible future locations. Now, assume that each
robot have necessary SINR information about all potential
future locations. Then, a robot {v} simply employs a potential
based controller for the movements by setting the potential
of each future location, say x′v = (x′
v, y′
v), to be negative
of the cost of the flow for the new configuration, Ci(X′
M)
where X′
M = {XM \ xv} ∪x′v and i is the flow that
the robot is part of. Therefore, the gradient of the potential
will determine the best direction. To gather information about
SINR in future locations, we propose two different strategies.
First, we select a finite set of uniformly distributed points,
say xf
v, from the set of possible future locations. In our case,
the set of possible future locations is the circumference of
the circle Bδ{xv}. Thus we choose a set of points, say 36
points, over the circumference that are equidistant. Now, in
the first proposed strategy, a robot simply moves to each of
these points x ∈xf
v and calculates the SINR, assuming that
the rest of the network is unchanged. Although this method
is straightforward, the convergence time of this method is
very long as each iteration needs a significant amount of time
and it is not efficient in terms of energy consumption. In the
second method, each robot maintains a SINR belief model
of the network and updates it after every movement. Based
on that model, a robot estimates the SINRs for each of the
potential locations. However, this SINR belief model is part of
our ongoing work. Both parts of our algorithm i.e., STAT and
−10
−8
−6
−4
−2
0
2
4
6
8
10
−10
−8
−6
−4
−2
0
2
4
6
8
10
Iteration= 1 
(a)
−10
−8
−6
−4
−2
0
2
4
6
8
10
−10
−8
−6
−4
−2
0
2
4
6
8
10
Iteration= 100 
(b)
Fig. 5: Simulation plots (a) Initial Configuration (b) Configu-
ration after 100 Iterations
MODAL, are repeated until further improvement is possible
for neither the link with lowest SINR nor the link with second
lowest SINR. The process will restart if any robot senses a
change in the configuration.
A. Simulation
To check the performance and determine the properties
of this algorithm, we performed a set of simulation exper-
TABLE III: SINR values of the different links after Simulated Annealing
Initial Configuration of Robots
Final SINR on each link
(x2, y2)
(x3, y3)
(x6, y6)
(x7, y7)
Noise
Link 12
Link 23
Link 34
Link 56
Link 67
Link 78
(0, 0)
(0, 2)
(0, 0)
(0.5, 0)
0.6
0.0327
0.0327
0.0327
0.0327
0.0327
0.0327
(0, 0)
(2, 0)
(0, 0)
(0, 0)
1.0
0.0200
0.0200
0.0200
0.0200
0.0200
0.0200
(0, -1)
(0, 1 )
(0, 0)
(0, 0)
2.0
0.0108
0.0108
0.0108
0.0108
0.0108
0.0108
(0, 0)
(3, 0)
(0, 1)
(-1, 0)
3.0
0.0073
0.0073
0.0073
0.0073
0.0073
0.0073
(0, 2)
(0, 0)
(0, 0)
(-1, 0)
4.0
0.0055
0.0055
0.0055
0.0055
0.0055
0.0055
(0, 0)
(0, 0)
(0, 0)
(0, 0)
10.0
0.0022
0.0022
0.0022
0.0022
0.0022
0.0022
iments with the same initial configuration as described in
section III-B. One instance of such experiments is illustrated
in Figure 5. As the figure suggests, the result is strikingly
similar to the one obtained from the centralized approach.
Also, with the different initial configuration as in Table III,
the final SINRs are exactly same as in Table III.
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 1 
(a)
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 75 
(b)
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 150 
(c)
-20
-10
0
10
20
-20
-10
0
10
20
Iteration= 200 
(d)
Fig. 6: Simulation plots: Configuration after (a) 1 Iteration (b)
75 Iterations (c) 150 Iterations (d) 200 Iterations
So far, we have dealt with only two flow optimization prob-
lems with static endpoints, which are very simple compared to
problems with higher complexity and multiple flows. In order
to test the performance of our algorithm in a more complex
framework, we increased the complexity of the network by
adding two extra flows with two robots assigned to each
of the flow. The sender-receiver pair for flow 3 are initially
located at (10, 10) and (−10, −10), and for flow 4 are located
at (−10, 10) and (10, −10). We introduce random mobility
pattern to Flow 1’s transmitter, Flow 2’s receiver and Flow
3’s receiver. The results of a simulation instance with this
configuration is presented in Figure 6. The figure demonstrates
that our algorithm works well for a network with four flows
with total 16 node and mobile endpoints. Figure 7 illustrates
the convergences of the flow-wise minimum SINR values over
time. It is clear from Figure 7 that the minimum SINR of
similar flows, i.e., Flow 1 and Flow 2, or Flow 3 and Flow 4,
converges to the same values when the flow endpoints are
static. Once the mobility is introduced, the SINRs change
based on the new positions of the communication endpoints.
We have also tested our algorithm for networks that are
asymmetric and our algorithm performs equally well in those
cases. However, we do not present those results in this paper
to conform with the space limitation.
0
20
40
60
80
100
120
140
160
180
200
−101.33
−101.36
−101.39
−101.42
−101.45
−101.48
Min SINR
Iteration
SINR in dB
 
 
Flow 1
Flow 2
Flow 3
Flow 4
Fig. 7: Variation in the minimum SINR of each flow over time
V. RELATED WORK
In this section, we provide a brief overview of the existing
research works related to our field of interest. Most of the
significant research on robotic wireless router related topics
are very recent. Yan and Mostofi([8], [9]) are among the few
researchers to work on the robotic router related problems.
They focused on robotic router placement optimization in
order to maintain connectivity between an user and a base
station. This optimization problem is mainly focused on min-
imization of bit-error rate for two scenarios of multi-hop and
diversity. They also demonstrated that optimizations based on
the Fiedler eigenvalue, instead of bit-error rate, result in a
performance loss. In these works, they used an extension of
the channel modeling technique introduced in ([10], [11]).
However, they ignored the effect of interference in their model
and focused on a single flow between a single receiver-
transmitter pair. Unlike these works, our proposed method is
based on SINR, which is more generalized than bit-error rate
approach. Also, we optimize multiple flows simultaneously,
instead of focusing on a single flow. Tekdas et al.[12], also
focused on similar problem and proposed two motion planning
algorithms based on known user motion and unknown-random
adversarial user motion, respectively. Among other state-of-
the-arts, the decentralized algorithm based on super-gradient
and decentralized computation of Feidler eigenvector by De-
Gennaro and Jadbabaie[13] is mentionable. Stump, Jadbabaie
and Kumar [14] also developed a framework to control a
team of robots based on two metrics: the Fiedler value of
the weighted Laplacian matrix and the k-connectivity matrix.
However, Yan and Mostofi[8] showed that Fiedler eigenvalue
does not reflect the true reception quality, which is crucial in
wireless networks.
Among other works, the DARPA LANdroids program [15]
is mentionable. Tactical communication enhancement in urban
environments is the main goal of this program. Towards this
goal, they tried to develop pocket-sized intelligent autonomous
robotic radio relay nodes, LANdroids, that are inexpensive.
LANdroids are used to mitigate the communications problems
in urban settings, such as multipath effect, by acting like
relay node into shadows, using autonomous movement and
intelligent control algorithms. Dixon and Frew[16] proposed
a decentralized mobility controller based on maximizing the
capacity of a local 3-node network in order to maximize the
end to end capacity of the entire communication chain. They
used measurements of the local signal to noise ratio for this
purpose. A Disjunctive Programming Approach is presented
in [17]. Among other works, the work of Vieira, Govindan
and Sukhatme [18] is mentionable. In contrast, our proposed
method is based on signal to interference and noise ratios and
focuses on multiple flow optimization, which is more practical
and generalized.
In [19], Williams, Gasparri and Krishnamachari presented a
hybrid architecture called INSPIRE, with two separate planes
called Physical Control Plane (PCP) and Information Control
Plane (ICP). Their goal was to improve and optimize the
network between multiple pair of senders and receivers using
a group of robots and using ETX as a metric. They used ETX
to determine the allocation of nodes among different flows,
while the mobility framework is simply to place the robots
evenly along the line segments joining the flow endpoints.
Although our application contexts are the same, our mobility
formulation as well as problem formulation are completely
different. In our proposed model, the movement of the robots
are directly controlled by the link qualities (more specifically,
SINR) and, thus, is much practical.
VI. CONCLUSION
In this paper, we have considered a problem of proper
placement and control of mobile robotic nodes in order to
optimize the performance of a wireless network. We have
devised an optimization function and based on that function,
we have proposed a centralized and a distributed method
of robotic node placement and control that maximizes our
objective function. Through a set of simulation experiments,
we have demonstrated the performance and convergence of our
algorithms. However, due to space constraints, we have left
out detailed description of some key portions of our algorithm
such as the SINR modeling techniques as well as complexity
and optimality analysis of our algorithm. Therefore, our future
direction will be to flesh out the details of an adaptive SINR
model as well a thorough analysis of our algorithm. This
work is also a foundation of our future goal to develop an
algorithm for adaptive node allocation and placement among
different flows in order to handle various dynamic situation in
the network such as flow addition or deletion and increase or
decrease in flow demands. Another future direction would be
a practical implementation of our algorithms on a real robotic
network testbed.
REFERENCES
[1] V. Gazi, “Stability analysis of swarms,” Ph.D. dissertation, The Ohio
State University, 2002.
[2] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms
and theory,” IEEE Transactions on Automatic Control, vol. 51, no. 3,
pp. 401–420, 2006.
[3] J. A. Fax and R. M. Murray, “Information flow and cooperative
control of vehicle formations,” IEEE Transactions on Automatic Control,
vol. 49, no. 9, pp. 1465–1476, 2004.
[4] P. J. M. Van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory
and Applications.
Springer, 1987.
[5] E. Aarts and J. Korst, Simulated annealing and Boltzmann machines: a
stochastic approach to combinatorial optimization and neural comput-
ing.
Wiley, 1988.
[6] T. S. Rappaport, Wireless communications: principles and practice.
prentice hall PTR New Jersey, 1996, vol. 2.
[7] G. Bianchi, “Performance analysis of the ieee 802.11 distributed coor-
dination function,” IEEE Journal on Selected Areas in Communications,
vol. 18, no. 3, pp. 535–547, 2000.
[8] Y. Yan and Y. Mostofi, “Robotic router formation-a bit error rate
approach,” in Proceedings of the 2010 Military Communications Con-
ference (MILCOM).
[9] ——, “Robotic router formation in realistic communication environ-
ments,” IEEE Transactions on Robotics, vol. 28, no. 4, pp. 810–827,
2012.
[10] Y. Mostofi, M. Malmirchegini, and A. Ghaffarkhah, “Estimation of
communication signal strength in robotic networks,” in Proceedings of
the IEEE International Conference on Robotics and Automation (ICRA),
2010.
[11] M. Malmirchegini and Y. Mostofi, “On the spatial predictability of com-
munication channels,” IEEE Transactions on Wireless Communications,
vol. 11, no. 3, pp. 964–978, 2012.
[12] O. Tekdas, W. Yang, and V. Isler, “Robotic routers: Algorithms and im-
plementation,” The International Journal of Robotics Research, vol. 29,
no. 1, pp. 110–126, 2010.
[13] M. C. DeGennaro and A. Jadbabaie, “Decentralized control of connectiv-
ity for multi-agent systems,” in Proceedings of the 45th IEEE Conference
on Decision and Control, 2006.
[14] E. Stump, A. Jadbabaie, and V. Kumar, “Connectivity management
in mobile robot teams,” in Proceedings of the IEEE International
Conference on Robotics and Automation (ICRA), 2008.
[15] M. McClure, D. R. Corbett, and D. W. Gage, “The darpa landroids
program,” in Proceedings of the SPIE Defense, Security, and Sensing,
2009.
[16] C. Dixon and E. W. Frew, “Maintaining optimal communication chains
in robotic sensor networks using mobility control,” Mobile Networks
and Applications, vol. 14, no. 3, pp. 281–291, 2009.
[17] N. Bezzo, R. Fierro, A. Swingler, and S. Ferrari, “A disjunctive pro-
gramming approach for motion planning of mobile router networks,”
International Journal of Robotics and Automation, vol. 26, no. 1, pp.
13–25, 2011.
[18] M. A. M. Vieira, R. Govindan, and G. S. Sukhatme, “An autonomous
Wireless Networked Robotics System for backbone deployment in
highly-obstructed environments,” Ad Hoc Networks, vol. 11, no. 7, pp.
1963–1974, Sep. 2013.
[19] R. K. Williams, A. Gasparri, and B. Krishnamachari, “Route swarm:
Wireless network optimization through mobility,” in Proceedings of
the IEEE International Conference on Intelligent Robots and Systems
(IROS), 2014.
This figure "gmax.jpg" is available in "jpg"
 format from:
http://arxiv.org/ps/1607.07848v1