Proceedings of the 2014 IEEE/SICE International
Symposium on System Integration, Chuo University,
Tokyo, Japan, December 13-15, 2014

SaA1D.1

Connectivity of Swarm Robot Networks for Communication Range andthe Number of Robots Based on Percolation Theory
Yoshiaki Katada
achieve collective exploration. As soon as a robot detects
a target, the information is sent from the robot to the basestation via intermediate relay robots. Therefore, all robots
should be “connected” to the base station via WSN.
This paper investigates communication range and thenumber of robots required for a wireless sensor network
composed of swarm robots (which is called “SR network”
in the remainder of this paper) to achieve connectivity
base on the percolation theory[6]. The paper is organized
as follows. The next section shortly introduces percolation
theory. Section III conducts computer simulations. Section
IV investigates the validity of the results in a robotics control
task and discusses utilization of the results. Conclusions are
given in the last section.

Abstract— One approach in swarm robotics (SR) is homogeneous system which is embedded with sensing, computing,mobile and communication components. This is identified withmobile wireless sensor networks (WSNs). For some SR tasks,
robots need to collect information from the environment andshare their data with each other. Due to the multi-hop transmission of WSNs, robots in such networks can communicate
with each other via intermediate relay robots. Therefore, it isimportant to take connectivity of the network into account.
This study investigates communication range and the numberof robots required for a SR network to achieve connectivity
based on percolation theory.

I. INTRODUCTION
Swarm Robotics (SR) [1][2] have attracted much researchinterest in recent years. Generally, the tasks in SR are difficult
or inefficient for a single robot to cope with as those inmulti-robot systems. Sahin [3] enumerated several criteria1
for distinguishing swarm robotics:• autonomy: Each robot should be physically embodied
and situated.
• redundancy: Group sizes accepted as swarms is 10 to20.
• scalability: SR system should be able to operate undera wide range of group sizes.
• simplicity: Each robot should employ cheap design, thatis, the structure of a robot would be simpler and the costfor it would be cheap.
• homogeneity: SR system should be composed of homogeneous individuals. This enhances the above 2nd and3rd criterion.
Following the last criterion, homogeneous controllers forindividuals are desirable for SR systems. This approach does
not assume the existence of an explicit leader in the system
due to the above criteria. This results in that a collective
behavior emerges from the local interactions among robots
and between the robots and the environment. Therefore,
SR systems are required for that individuals show various
behaviors although the individuals are homogeneous.
In SR, the typically control tasks requiring distributed
collective strategies have been coped with, navigation, aggregation, formation and transport. This paper supposes wecopes with a navigation problem. In this control task, several
robots can communicate with each other via wireless sensor
networks (WSN)[4][5] due to the multi-hop transmission to
Y. Katada is with Faculty
Setsunan University, Neyagawa,

II. PERCOLATIONThis section shortly introduces percolation theory.
A site is randomly arranged with probability p on lattice
points of a square lattice. Sites become adjacent to each otherwhen p becomes large from 0. Above a critical value ofp, clusters of big size first form where any sites between
opposite boundaries are interconnected, that is, sites percolate. Such a process in that clusters form is called, “sitepercolation”. For another process, lines are randomly add
between neighbouring lattice sites until clusters form. Thisis called, “bond percolation”. In this way, percolation theory
discusses connection between elements composing a cluster
and characteristic emerged from a set of connected elements[6].
For an infinite set of sites, it has been reported that a
critical value at which an infinite large cluster forms dependon the shape of a lattice. In some cases of two- or threedimensional lattice whose shape is simple, a critical value
can be calculated explicitly. In the rest of cases, such a
critical value cannot be calculated exactly so that this value
is estimated by computer simulations. The above explanation
is based on a lattice, that is, discrete region.
As those studies in a lattice, several researchers investigated percolation in continuous space [7][8]. In continuous
space, the concept, “neighbouring lattice sites”, does notexist. Therefore, the bonding criterion must be defined. Fig.
1 shows the bonding criteria in two-dimensional continuous
space: Two sites are bonded if those are within each other’scircle of radius R, that is, d ≤ R, where d is the distance
between two sites. In the reference [8], the authors investigated percolation on the two-dimensional continuous space.
N points are uniformly distributed in a unit square in Fig.
2. About each point, a circle of radius R is drawn. Twoof Science and Engineering,Osaka, JAPAN katada @ele.setsunan.ac.jp
1 Sahin [3] claimed that these criteria should be used as a measure of thedegree of SR in a particular study.

978-1-4799-6943-2/14/$31.00 ©2014 IEEE93

(0,1)(1,1)

R: Communication
Range

R

Robots(0,0)

Fig. 1. Illustration of the bonding criteria for two-dimensional continuous
space

Fig. 4.

(1,0)

Experimental setup for two-dimensional continuous spaceRtFig. 5.
Fig. 2.

Snapshots of robots navigation

Two-dimensional continuous space

III. COMPUTER SIMULATIONS
points are considered to be connected when their distanceis less than R (Fig. 1). For this setting, you can imagine
the following situation: The value of R is increased with theconstant N or the value of N is increased with the constant R
until the clusters of big size are observable between opposite
boundaries. The phenomenon at these critical values is also
called, percolation.
Fig.3 illustrates percolation in continuum region2 . The
radius of a circle shows R. The center point in the green
circle is connected via other center points from the origin
while the point in the red circle is unconnected. The valueof N is increased while R is fixed at 0.1. When N = 50,
a few connections from the origin appear (Fig.3(a)). WhenN = 150, many connections appear although the connections
are not observable on the far side of the square (Fig.3(b)).
When N = 200, the connections are observable throughout
the square so that a cluster forms (Fig.3(c)).

A. Simulation Conditions
In this experiment, we considered the model in two
dimensional space in percolation theory as described in theprevious section. We uniformly distributed N points in aunit square in Fig. 4. About each point, a circle of radius
R is drawn. This corresponds to a SR network as follows;
A point i(i ∈ {1, · · · , N }) is an arbitrary robot, The point
density, N , is the number of robots in a unit square and R
is communication range for each robot, where R is set toconstant for all the robots because we assume the system ina SR to be homogeneous as described in Section I. The basestation locates at the origin, whose communication range is
R. Mobile robots are supposed to be used in this study.
However, the setting described above is static, that is, thepositions of the robots are fixed. This is because we consider
this setting to be a snapshot during robots’ navigation (Fig.
5). According to this setting, we investigated connectivity
among the robots and between the robots and the basestation. The values of R and N are increased until theconnections are observable between the most of those robots
and the base station, that is, percolation is detected. Above
this critical value, each robot can communicate with the basestation via intermediate relay robots. This is a different pointfrom the original model on the two-dimensional continuous
space. For this experiment, R = {0.1, 0.2, · · · , 0.9} andN = {2, · · · , 1400}. The robots were randomly distributed
in a unit square. We conducted 10000 independent runs
for each problem with the parameters (N , R). All results
were averaged over 10000 runs. These several runs with therandom distribution make possible to consider a series of2 This situation described here is not the same as the original one in [8]but is related to our setting of this study (the details are described later).

1

1

1

0.5

0.5

0.5

0

0
0

0.5

1

(a) N = 50
Fig. 3.

000.5(b) N = 150

1

0

0.5

1

(c) N = 200

Percolation in continuous space

978-1-4799-6943-2/14/$31.00 ©2014 IEEE94

although larger P needs more N for small R as mentioned
before. For large R, P becomes large when r is large in Fig.
7(d). Addition to this, we can find lower bounds of P foreach N when r = 0. We observed the same tendencies as
this for other values of R.
For each r, the critical values of N are shown in Table I3 .
When R is more than 0.5, connectivity were observable forless N by introducing the body of each robot which makes
robots distribute evenly.
3) Under uncertainty: In Section III-B.1 and III-B.2, we
employed the simplified communication range model (Fig.
1). In real environment, however, there are several uncertainty, such as noise and interference, scattering, diffraction,and reflection of other transmissions and obstacles [5]. Thus,
we consider a probabilistic communication model. However,no general communication model considering uncertainty has
not proposed. In this study, we employed the probabilistic
communication model in which the communication radius,′
R , is a random variable following probability distributionsin Fig.8.
Two types of distributions were used: uniform distribution′
and Gaussian distribution. A communication radius, Ru ,′distributes uniformly between 0 and R: Ru ∈ U (0, R)(Fig.8(a)) where R is the communication range of a transmitter employed in Section III-B.1 and III-B.2. Another′communication radius, Rg , follows N (µ, σ 2 ) where µ is
average and σ is standard deviation. We set µ at R2 and σ at
′
R
R 2
R
6 , respectively. Following N ( 2 , ( 6 ) ), Rg falls within thethree σ range, µ − 3σ ≤ X ≤ µ + 3σ, at a probabilityof 0.9999 (Fig.8(b)). A common features between theseprobabilistic communication radiuses are that the minimum
value is 0 and the maximum value is effectively R. This
corresponds to the simplified communication range in Fig.1.
′′
According to the above distributions, Ri and Rj are
generated for the i-th and j-th robot, where ∃ i, j ∈{1, . . . , N }, i 6= j. Two sites are bonded, that is, two robots′′
can communicate with each other when d ≤ min{Ri , Rj },where d is the distance between two robots. For this experiment, R = {0.1, 0.2, · · · , 1.0, · · · , 5.0, 10.0, 20.0}, wheresome R are larger than those in Section III-B.1 and III-B.2.
We conducted 100000 independent runs for each problem
with the parameters (N , R).

snapshots to be the behavior of the robots during navigation.
So far we have described the common setting in a series ofexperiments conducted in this study. Particular setting foreach experiment will be described in the following part.
B. Simulation Results
1) Without body: In the first experiment, we do notconsider the body of the robot and treat it as a point. In Fig. 6,
the ratio, P , of the number of the connected robots directly or
indirectly via intermediate relay robots from the base stationfor each N is shown on a semilogarithmic graph for each R.
P is sometimes called connectivity in the remainder of thispaper. P increases with the increase of N . P for the extreme
large value of R is more than 0.8 even when N = 2. We
can find the critical value of N at which P converges to 1.0
for each R. Table I shows the critical values obtained in thisexperiment (r = 0.0).
2) With body: So far we have not considered the bodyof the robot located at a point. That is, an infinite numberof robots can be located in the neighborhood of a robot.
In the second experiment, we considered the body of eachrobot by introducing a circle of radius, r [8], where r ∈{0.05, 0.075, 0.1} and r < R. The reason why the conditionr < R is introduced is that the radius which is larger thancommunication range (r > R) is not practical. Here, we
conducted the same experiment as the first one after the
robots were randomly distributed in a unit square avoiding
overlap between robots and the border of the environment.
Note that there are cases in which we can not distribute N
robots due to the body of the robot.
Fig. 7 show the effect of the body on P . The graphs
were plotted for each R in Figs 7(a)-7(d) in order to avoid
overplotting. Note that the scales of horizontal axis aredifferent for each graph, and that the results for r = 0.0 were
the same as those in the first experiment (without body). For
small values of R, there were the cases where the calculationof P was not able to be executed, e.g., r = 0.075, 0.05 in
Fig. 7(a) and r = 0.075, 0.1 in Fig. 7(b). This is because
we can not distribute N robots due to the body of them

1
0.8

3 ’x’ shows nonexecution of the calculation and *–* shows no setup in
Table I.

P

0.6
0.4

TABLE IC RITICAL VALUES OF N FOR EACH R AND r, ABOVE WHICH A
NETWORK IS FULLY CONNECTED .

0.2
0
10

1

10

2

N
R=0.9
R=0.8
R=0.7
Fig. 6.

R=0.6
R=0.5
R=0.4

R=0.3
R=0.2
R=0.1

r
0
0.050
0.075
0.100

Connectivity for each communication range

978-1-4799-6943-2/14/$31.00 ©2014 IEEE

95

0.1
1388
x
x
–

0.2
341
x
x
–

0.3
163
47
x
x

0.4
83
36
x
x

R
0.5
50
26
18
x

0.6
34
19
14
11

0.7
20
17
10
9

0.8
16
12
8
7

0.9
9
7
6
5

1
0.8

1

r=0.0
r=0.050
r=0.075

0.8

P

0.6

P

0.6

r=0.0
r=0.050
r=0.075
r=0.100

0.4

0.4

0.2

0.2

0

1

2

10

0

3

10

1

10

2

10

10

N

N

(a) R = 0.1(b) R = 0.2

0.8

0.8

0.6

0.6
P

1

P

1

0.4

0.4
r=0.0
r=0.050
r=0.075
r=0.100

0.2
0

1

0

2

10

r=0.0
r=0.050
r=0.075
r=0.100

0.2

1

10
N

10
N

(c) R = 0.3(d) R = 0.5

Fig. 7.

Effect of the size of the robot on connectivity P

Fig.9 show the effect of the noise on P . For each N , R oflarger than 1.0 is required for that P converges to 1.0. For
large N , P for uniform distribution is larger than the one for
Gaussian distribution with the same value of R. For small N ,P for Gaussian distribution becomes large at relatively small
R compared to those for uniform distribution (Fig.9(b)). Overthe range 10 ≤ N ≤ 20, R of larger than 20.0 is required in
the case of uniform distribution (the worse case) for that P
converges to 1.0. This means that the communication range,
R, must be 20 times as large as the environment. From theseresults, we can say that the effective communication range
under uncertainty is much less than the communication range
of a transmitter.

according to Table I. For another example, a two-dimensionalsquare with edges of length 250m corresponds to R = 0.8.
Thus, 16 robots are required for connectivity.
When R is large, we can decrease the number of robots
required for connectivity by considering the body of the robot
as mentioned in the previous section. In the above case where
the edge of length is 250m and R = 0.8, r = 250m × 0.05
= 12.5m. This results in a robot with a diameter of 25m. But
this body length is not practical. When we assume typicalcommunication range of a transmitter for WSN (100m to200m) and a robot with the radius of less than 1m, r becomesvery small compared with R. This means that the results for
r = 0 is sufficient for robots with practical volume.
Under uncertainty, R of larger than 1.0 is required forconnectivity (Section III-B.3). Over the range 10 ≤ N ≤ 20,
R must be 20 times as large as the environment. For thesecases, we suppose that the environment can be divided into
several regions. This results in that we distribute N required
for each smaller region. In the case of an unconvex region,
e.g., an L-shaped or U-shaped corridor, we can apply thisway.
For typical communication range, we have a problem thathow much two-dimensional square we consider corresponding R in Table I and the results obtained in Section III-B.3.
These are decided due to the number of robots preparable
by users and the control task to be solved by the SR.

IV. DISCUSSION
A. Utilization of the Results
In this subsection, we propose the way to utilize the results
obtained in the previous section. For the experimental setup
in the previous section, the robots with communication range
R were randomly deployed in a unit square. Therefore, thewidth and the height are considered as 1.0, respectively and
R as a relative value for them.
Let communication range 200m in line-of-sight communication. For example, for a two-dimensional square with edgesof length 400m, the communication range 200m corresponds
to R = 0.5. Thus, 50 robots are required for connectivity

978-1-4799-6943-2/14/$31.00 ©2014 IEEE96’

Probability density function f(R )’Probability density function f(R )

2.5

1

0

2

1.5

1

0.5

0
0

R

0

R/2

’

R
’

R

R

(a) Uniform distribution
Fig. 8.

(b) Gaussian distribution
Probabilistic communication model

1
0.8
P

0.6
0.4
0.2
0
101

102

103

N
R=20.0R=10.0
R=5.0
R=4.0
R=3.0

R=2.0
R=1.5
R=1.0
R=0.9
R=0.8

R=0.7
R=0.6
R=0.5
R=0.4
R=0.3

R=0.2
R=0.1

(a) Uniform distribution

1
0.8

P

0.6
0.4
0.2
0
101

102

103

N
R=5.0
R=4.0
R=3.0
R=2.5

R=2.0
R=1.5
R=1.0
R=0.8

R=0.7
R=0.6
R=0.5
R=0.4

R=0.3
R=0.2
R=0.1

(b) Gaussian distribution
Fig. 9.

Effect of the noise of the robot on connectivity P

B. Validity of Connectivity

environment of the robot was a rectangular arena surroundedby walls with a base station placed at the bottom left
corner (Fig. 10). The control task for a robot used in thisexperiment was navigating the environment where a robot
avoids other robots. The robot was provided with 6 infraredproximity sensors which have a limited detection range in the

In this subsection, we investigate the validity of the results
obtained in Section III. We conducted additional computer
simulations where robots with the body in SR perform
random walk with obstacle avoidance.
A two-wheeled robot was used in this experiment. The

978-1-4799-6943-2/14/$31.00 ©2014 IEEE

97

1

Connectivity

0.8
0.6
0.4
0.2
0

Fig. 10.

0Experimental setup for navigation problem

200

400
600
Time Step

800

1000

800

1000

800

1000

(a) R = 0.6, Ns = 20
1

environment. If other robots or wall intersects a proximity
sensor, the sensor outputs a value inversely proportional tothe distance between the other robot or wall and the sensor.
Employing a mathematical model of a mobile robot, thedisplacement of the robot was computed. At the beginningof each trial, robots were placed at random initial positions
avoiding overlap at random orientations. According to Table
I, the parameters were set as follows: The body of radius, r,
is set at 0.05 and (R, Ns ) = (0.6, 20), (0.2, 20), (0.3, 50).
One trial ends when 1000 time steps are performed. We
conducted 10 independent runs. All results were averaged
over 10 runs.
Figs. 11 show connectivity averaged in 10 runs for eachtime step. For R = 0.6, Ns = 20, connectivity wereobservable with relatively small number of robots over
the runs because the environment were covered with wide
communication range (Fig. 11(a)). When R is small withthe same Ns (R = 0.2, Ns = 20), on the other hand,connectivity were not observable most over the run. For
small R and large Ns (R = 0.3, Ns = 50), connectivity
were observable most over the run. In several runs whereconnectivity were not kept in the last several hundred steps,
about 10% robots came to a deadlock at the corners of theenvironment or among robots. This means that the robots
were not distributed appropriately all over the environment.

Connectivity

0.8
0.6
0.4
0.2
0
0

200

400

600

Time Step(b) R = 0.2, Ns = 20
1

Connectivity

0.8
0.6
0.4
0.2
0
0

200

400

600

Time Step(c) R = 0.3, Ns = 50
Fig. 11.

Connectivity for each time step

V. CONCLUSIONS AND FUTURE WORKSR EFERENCES

This paper investigated communication range and thenumber of robots required for swarm robot networks toachieve connectivity based on percolation theory. Criticalvalues for them were calculated under various conditions.
Based on these results, it was confirmed in computer simulations that most mobile robots can navigate the environment
keeping connectivity. Moreover, utilization of the results
obtained in a series of simulation was discussed.
In real environment, quality of wireless communication
maybe deteriorate due to several causes, e.g., obstacles inenvironment, interference of other transmissions or traffic
congestion in wireless networks. In this study, we introduced
the probabilistic communication model. In future works, wewill investigate the validity of this model in real environment.
Addition to this, we plan behavior design for real robots tokeep connectivity of the network in the control task.

[1] V. Trianni, Evolutionary Swarm Robotics, Springer-Verlag 2008.
[2] M. Brambilla, E. Ferrante, M. Birattari, M. Dorigo, “Swarm Robotics:
A Review from the Swarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp.1-41, 2013.
[3] E. Sahin, “Swarm Robotics: From Sources of Inspiration to Domains of Application,” Lecture Notes in Computer Science, Volume3342/2005, pp.10-20, 2005.
[4] J. Li, L.L.H. Andrew, C.H. Foh, M. Zukerman, C. Hsiao-Hwa,“Connectivity, Coverage and Placement in Wireless Sensor Networks,”
Sensors, Vol.9, No.10, pp.7664-7693, 2009.
[5] A. Ghosha and S.K. Das, “Coverage and connectivity issues in wirelesssensor networks: A survey,” Pervasive and Mobile Computing volume
4, issue 3, pp.303-334, 2008.
[6] D. Stauffer and A. Aharony, Introduction To Percolation Theory:
Revised Second Edition, CRC Press, 1994.
[7] E.N. Gilbert, “Random Plane Networks,” J. Soc. Indust. Appl. Math,Vol. 9, No. 4, pp.533543, 1961.
[8] G.E. Pike and C.H. Seager, “Percolation and Conductivity: A Computer Study. I,” Phys. Rev. B, volume 10, issue 4, pp.1421-1434, 1974.

978-1-4799-6943-2/14/$31.00 ©2014 IEEE

98