# Properties of 3D HI Filaments in the Smith High Velocity Cloud

Colin Holm-Hansen,1 M. E. Putman,2 D. A. Kim2
1Department of Physics, Columbia University, New York, NY 10027, USA
2Department of Astronomy, Columbia University, New York, NY 10027, USA

(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

We present findings of 3D filamentary structures in the Smith Cloud, a high-
velocity cloud (HVC) located at $l=38^{\circ}$, $b=-13^{\circ}$. We use data
from the Galactic Arecibo L-Band Feed Array H i (GALFA-H i) along with our new
filament detection algorithm, fil3d, to characterize these structures. In this
paper, we also discuss how different input parameters affect the output of
fil3d. We study filaments in the local ISM and compare them to those found in
the Smith Cloud. Based on thermal linewidth estimations we find supporting
evidence that the Smith Cloud filaments are part of its warm neutral medium.
We also find a relationship between thermal linewidth and the $v_{LSR}$ of the
filaments. We study the plane-of-sky magnetic field as traced by Planck 353
GHz polarized dust emission along the line of sight and find the HI filaments
in this region are not aligned with the magnetic field. This is likely related
to their location close to dynamic processes in the Galactic Plane and/or the
low column density of the filaments relative to emission in the Plane. The
results show the HI filaments are found in a wide range of Galactic
environments and form through multiple processes.

###### keywords:

ISM:clouds – ISM:kinematics and dynamics – ISM:structure

††pubyear: 2023††pagerange: Properties of 3D HI Filaments in the Smith High
Velocity Cloud–A

##  1 Introduction

The interstellar medium (ISM) is flush with complex morphology. It has been
shown that there exists an intricate network of molecular filaments that may
be linked to star formation (e.g., André et al., 2014). Recently, H i
filaments have also been found at varying Galactic scales (McClure-Griffiths
et al., 2006; Clark et al., 2014; HI4PI Collaboration et al., 2016; Kalberla
et al., 2016; Soler et al., 2020, 2022). Unlike molecular clouds, these
objects are not self-gravitating, meaning they must form due to factors in
their environment. Given that they have been detected in several environments
at varying scales and densities, multiple formation mechanisms may exist. In
order to understand their formation, a plethora of work has been underway
studying their physical properties. It has been shown that these filaments
tend to align with the ambient magnetic field traced by polarized dust
emission (McClure-Griffiths et al., 2006; Clark et al., 2014; Kim et al.,
2023). Around the Galactic plane, alignment is mostly parallel to the plane,
but due to several factors smaller regions with perpendicular planar alignment
are also present (Soler et al., 2020, 2022).

Characterization of filaments in regions beyond the local ISM is beginning to
take shape as well. Ma et al. (2023) studied filamentary structure in regions
of the Small Magellanic Cloud and found possible evidence of alignment with
its magnetic field. Jung et al. (2023) has shown in MHD simulations that high-
velocity clouds (HVCs) draped in a magnetic field should have filaments along
their direction of motion. However, up until now, the quantification of
observed H i filaments in a HVC has not been done.

The Smith Cloud (Smith, 1963) is one of the most thoroughly studied HVCs with
a known distance of 12.4 kpc (Putman et al., 2003; Lockman et al., 2008;
Wakker et al., 2008). Like other HVCs it has a comet-like morphology with a
compact head and more diffuse tail. Its head is located at approximately
$l=38^{\circ},b=-13^{\circ}$, and the whole structure extends approximately 1
x 3 kpc across the sky. Mass estimates place it having around $10^{6}M_{\sun}$
in both neutral H i and H ii (Lockman et al., 2008; Hill et al., 2009). Its
magnetic field strength has been mapped using Faraday Rotation (Hill et al.,
2013; Betti et al., 2019). Lockman et al. (2008) computes a z-height for the
Smith Cloud of -2.9 $\pm~{}0.3$ kpc, which we adopt for this paper. Kinematic
analysis done by Lockman et al. (2008) has shown that it is on a trajectory
toward the Galactic plane and will reach it in about 30 Myr.

The origin of the Smith Cloud is still unknown. It has been proposed as having
an extragalactic origin (Bland-Hawthorn et al., 1998) or a local origin as a
conglomerate ejected from the disc of the Milky Way (Sofue et al., 2004;
Marasco & Fraternali, 2017). If it is a failed dwarf galaxy it likely already
passed through the disc approximately 70 Myr ago and in order for it to have
survived this encounter it must have a dark matter halo (Nichols & Bland-
Hawthorn, 2009). If it has a local origin, Alig et al. (2018) has shown that
this encounter with the disc may trigger a burst in star formation in the disc
gas.

In this paper, we investigate the structure and properties of 3D H i filaments
in the Smith Cloud. We compare their properties to filaments at lower
velocities along the same line of sight. Section 2 introduces the data and
reviews the procedures for both extracting and analyzing 3D H i filaments
using our 3D Filament finding algorithm, fil3d. Section 3 discusses the
effects of fil3d parameters on the final filament populations and goes over
the selections made for this study. Section 4 shows the results when applied
to the data and investigates filament properties such as physical
characteristics and magnetic field orientation. We discuss these results and
present our conclusions in Section 5.

##  2 Data & Methods

We extract filaments with data from the Galactic Arecibo L-Band Feed Array H i
(GALFA-H i) survey (Peek et al., 2018). GALFA-H i is highly effective at
locating filaments due to its sensitivity and spatial resolution of 4′. The
data are gridded to 1′x 1′pixels. We downloaded a custom cube from the GALFA-H
i website, using the 0.739 km s-1channel spacing for spectral resolution over
a total velocity range of -68 < $~{}v_{LSR}~{}$ < 188 km s-1. The upper-
velocity range for the cube was selected to ensure that the entire extent of
the Smith Cloud would be captured. The RMS noise is 150 mK per 1 km
s-1velocity channel. The total region of sky sampled is 292°< $\alpha$ <
312°and -1°< $\delta$ < 6°. The trade-off with using the high spatial
resolution GALFA-H i data over other survey data is that we are located at the
minimum declination of GALFA-H i’s observation region (-1°17′), whereas the
main component of Smith Cloud extends as far as -2°(see Lockman et al., 2008).
Figures 1 and 2 show the entire Smith Cloud as shown in the GBT (Lockman et
al., 2008) and the GALFA-H i region respectively. For magnetic field
information, we employ the Planck 353 GHz Stokes linear polarization maps
(Planck Collaboration et al., 2020). We smooth the resolution of the Planck
maps to a full width at half-maximum (FWHM) of 1° from their original
resolution of 4.9′in order to improve the maps’ signal-to-noise ratio.

Figure 1: The Smith Cloud as shown in Lockman et al. (2008) integrated from
70-130 km s-1with the column density from the moment 0 map shown with the
right scale bar. The GALFA-H i region is shown in a rectangle outlined in red.

We use the fil3d algorithm to identify filaments in GALFA-H i as discussed in
Kim et al. (2023) and Putman et al. (in prep.). In an attempt to capture the
entirety of the Smith Cloud, we also tried running fil3D on data from the
Robert C. Byrd Green Bank Telescope (GBT) from Lockman et al. (2008) as well
as from the H i 4$\pi$ survey (HI4PI Collaboration et al., 2016) using a wide
range of settings, but found with the larger beamwidths (10′and 16′,
respectively), filaments are not resolved enough to be captured by fil3d
(although see Figure 3 for the 2D filament map using the GBT data). We follow
the same procedure for extracting filaments laid out in Kim et al. (2023) and
Putman et al. (in prep), which can be consulted for more details. We begin by
applying an unsharp mask (USM) with a 30′Gaussian beam to each channel in the
spectral cube, which acts as a high-pass filter, removing diffuse emission.
Following this we run FilFinder (Koch & Rosolowsky, 2015) to identify 2D
filamentary structures in each channel. Each 2D filament is referred to as a
node. If any two nodes in adjacent channels share 85% of pixels in common,
they are considered to be part of one composite 3D object, known as a tree.
Once a tree is formed, it is finalized by repeating this process until
adjacent channels have no significant overlap. The final mask for a tree is
the aggregated mask of each of its nodes, called the merged mask.

After generating trees, we validate them based on several criteria. First,
only trees with an aspect ratio of 1:6 or greater are accepted to ensure
filament-like morphology. Since FilFinder tends to pick up more noise at the
edges, any trees with a merged mask along the edge of the data are also
discarded. If filaments pass these first two criteria we inspect their median
intensity within the merged masked area as a function of their velocity (see
Kim et al. (2023), figure 4). This is done since most fil3D trees only span
2-3 channels. As such, we consider the entire Gaussian profile to be a more
physical line width for the filaments as opposed to only the fil3D detected
channels. To ensure the validity of this assumption, we require that the
median velocity channel detected by fil3D falls within one standard deviation
of the best fit Gaussian profile. Finally, we visually inspect the merged mask
contours overlaid on a moment zero map of the USM data integrated over the
FWHM of their Gaussian profile. Since we are interpreting this range as the
true linewidth of a filament, we require that the moment zero map integrated
over this range be consistent with the original fil3d merged mask. Therefore,
only filaments whose merged masks match the data over their FWHM range are
accepted. Filaments that pass all of these criteria are then saved in the
final set. Applying this to our dataset we find an initial return of 135,
which becomes 72 after the filtering process. The final batch covers a
velocity range (taken to be the velocity of the median channel of the filament
found by fil3d) of -6 < vLSR < 107 km s-1.

For the plane of sky magnetic field data, we follow the same procedure as Kim
et al. (2023), using the supplied Stokes data to obtain the dust polarization
$\psi$ in the Galactic IAU convention. Since polarized dust grains align
perpendicularly with the ambient magnetic field, we define the plane of sky
magnetic field orientation $\phi$ at a given location to be:

$\phi=\frac{1}{2}\arctan(U,-Q)$ (1)

which is a 90°rotation from $\psi$. From this, we compute the the average
B-field value $\overline{\phi}$ in the area of each filament:

$\overline{\phi}=\frac{\sum_{j}\sum_{i}\phi(x_{i},y_{j})}{A}$ (2)

where A is the area of the merged mask, and $\phi(x_{i},y_{j})$ is the
magnetic field orientation at location $(x_{i},y_{j})$ within the area of the
merged mask. The orientations of the filaments themselves, denoted as
$\theta$, are computed using the Rolling Hough Transform (RHT) as described in
Clark et al. (2014). We define the difference between these two values,
$|\theta-\overline{\phi}|$, to be the mean magnetic alignment of a filament.
We also compute the polarization fraction $p$ for each filament:

$p=\frac{\sqrt{U^{2}+Q^{2}}}{I}$ (3)

which we use to help discuss our findings in Section 5.

Figure 2: Top: Average velocity moment 1 map of the GALFA-H i region of the
Smith Cloud over the same velocity range as Figure 1 with Galactic coordinates
overlaid. Bottom: Filament masks overlaid on N${}_{\text{H\,{i}}}$ map of the
Smith Cloud integrated from 70-130 km s-1. The vertical lines present in the
background are artefacts from the basketweave scanning method used for GALFA-H
i.

##  3 fil3D Dependencies

The output generated from fil3D is sensitive to its multiple input parameters,
including inputs made to Filfinder, the overlap percentage, the aspect ratio
filter, and the width of the USM Gaussian kernel. Different inputs should be
expected to work better for different data sets as well as in different
regions. Overall, we find that tweaking these parameters often changes the
total number of filaments, but the overall trends and findings discussed in
Section 4 stay the same. Here we discuss the selections made for this study.
For these selections, we find the multiple steps of validation criteria to
serve as a means to minimize artefacts in the final population. For example,
lowering the size threshold or the minimum aspect ratio requirement inherently
leads to more junk being included in the initial return sample. However, we
find that when these changes are made, the percentage of filaments removed by
the velocity filter increases significantly. As such, the multiple criteria
help ensure the validity of the final population.

###  3.1 FilFinder Parameters

The nodes drawn from each channel are partially dependent on the parameters
used for Filfinder. For these, we start by defining a characteristic
scale_width and defining the rest of our variables with respect to it. For
this value, we found 0.1 pc to work the best. 0.15 pc and 0.05 pc were also
tried, but with the former, the number of filaments drops drastically and the
latter picks up too many artefacts. Other inputs to Filfinder include
smooth_size which was set to $0.5*$scale_width, and adaptive_threshold which
was set to $2*$scale_width. smooth_size determines the magnitude of the beam
applied to the image to remove small noise variations, and adaptive_threshold
is a parameter related to the expected filament size. border_masking, which
excludes the edges from the search region, was set to false. More details on
these parameters can be found in the Filfinder documentation.

The Filfinder parameter that was given the most consideration was
size_threshold, which is the minimum size required for an individual node to
be considered real. We experimented with using both very large and very small
values for this parameter. We started with $8*$(scale_width*2)2 (used in Kim
et al. (2023) and Putman et al.), but found that this left out visibly
filamentary structure in the Smith Cloud. We then tried dropping it down to 5
pix2 with the thought that any junk picked up would be filtered out through
our other validation criteria. However, we found that under this setting many
filaments ended up with nodes only a few pixels in size, and some filaments
recovered at higher size thresholds had additional nodes at the beginning or
end of their channels that were squares 5-10 pixels in size. We eventually
settled on $3*$(scale_width*2)2 as a compromise between the two extremes. The
smallest nodes were inspected visually at this threshold and none appeared to
be artefacts.

###  3.2 Aspect Ratio

Figure 3: Filfinder results ran on the moment 0 map in Figure 1 with a 1:2
aspect ratio cut, minimum area of twice the beam size, and edge filtering
applied. The prominent structure centered at (l,b) $\approx$ (40°,-15°) is
outside of the GALFA-H i data. Figure 4: Filfinder results ran on the moment 0
map of the GALFA-H i region for comparison with Figure 3. The beam size is
drawn as a black circle in the upper left corner.

We tested several different aspect ratio filters: 1:6, 1:5, 1:4, and even 1:2
was considered to better understand the overall effect on the final filament
count. As expected, as the aspect ratio filter drops, the total number of
filaments increases. For these data, 1:6 usually returned just under one
hundred filaments (For this subsection, the totals referred to do not include
any other sort of filtering as discussed in Section 2 other than the aspect
ratio filter). 1:5 and 1:4 returned several hundred filaments each, and 1:2
returned over one thousand filaments. As with other parameters, these aspect
ratio outputs were inspected visually to determine which produced the most
filaments without producing too many artefacts. We selected 1:6 for this
study, consistent with what was used in Kim et al. (2023) and Putman et. al
(in prep).

###  3.3 Overlap Threshold

We find the ability to vary the overlap threshold is somewhat limited.
Somewhat counter-intuitively, the total number of filaments found decreases if
the overlap threshold is lowered too far below 85%. This occurs because as the
overlap threshold is lowered, more and more nodes are accumulated into the
merged mask structure. This causes filaments to span across more channels on
average, but it also causes them to become wider, or to pick up adjacent
material that is not associated with them. As such their aspect ratios
decrease, causing more filaments to be rejected by the aspect ratio filter.
For this region we found this to start occurring at an overlap threshold of
65%.

###  3.4 Resolution

To illustrate the dependency of spatial resolution in this section we compare
the Filfinder output on moment 0 maps integrated from 70-130 km s-1for both
the GBT and GALFA-H i data. For each output, we apply a rough filter of a
minimum aspect ratio of 1:2, a minimum size of twice the beam size, and remove
any filaments that touch the edge of the data. We apply a smaller aspect ratio
filter here since the Filfinder output of a single channel is more comparable
to a node which is smaller on average than a tree, meaning the corresponding
node aspect ratio is smaller. The outputs are shown in Figures 3 and 4
respectively. The GBT data only returns one object satisfying these criteria
along the lower ridge of the body of the Smith Cloud, which is located in a
region outside of the GALFA-H i data. This motivates why we were unable to
find filaments in the GBT data. By contrast, the GALFA-H i data returns 70
structures (although artefacts are definitely still present), and there are
cohesive filament structures at the locations of fil3d trees.

The different spatial resolutions also correspond to different width scales.
For GALFA-H i structures that Filfinder can compute the width of, i.e.
excluding artefacts and other structures with obscure geometries, the average
width is 32.9 pc at a distance of 12.4 kpc. By contrast, the computed width of
the GBT structure in the lower ridge of the Smith Cloud body is 107.9 pc.

##  4 Results

Figure 5: Histogram of the final sample of 3D filaments as a function of their
median fil3d $v_{LSR}$.

Figure 6: Top: Catalog of all filaments detected. Color indicates $v_{LSR}$ of
the median channel of the filament as found by fil3d. Bottom: Magnetic field
orientation of all filaments. The background shows magnetic field orientation
drawn with line integral convolution. Local filaments appear anti-aligned in
this region.

We find a total of 72 filaments passing all criteria outlined in Section 2.
Looking at the distribution of median velocities for each filament as shown in
Figure 5, we categorize the filaments into three distinct groups. The bulk of
filaments with median velocities less than 20 km s-1are considered to be
relatively local structures in the Galactic disc. The second group is a
smaller population between 20 and 70 km s-1, which are largely thought to
represent structures in intermediate velocity clouds (IVCs). The remaining
group, all with velocities of 70 km s-1or greater, are the filaments located
in the Smith Cloud. This range of velocities for the Smith Cloud is based on
Figure 3 of Lockman et al. (2008), which suggests that prominent Smith Cloud
flux ranges from 70-130 km s-1. The HVC filaments are plotted in Figure 2. The
entire group of filaments are plotted in Figure 6.

The magnetic field alignment of filaments is shown in Figures 6 and 9. The
color indicates $|\theta-\overline{\phi}|$ for each filament in degrees. The
local filaments appear preferentially anti-aligned, with a median alignment of
59.7°and a mean of 56.3°. The anti-alignment falls off going to higher
velocities, and for the IVC and HVC population, the filaments seem to be more
randomly oriented with respect to the Planck data. The median B-field
alignment, as well as a summary of overall attributes for each group, are
shown in Table 1. The mean computed polarization fraction within the merged
mask area of the local filaments is .0725.

We make a temperature estimate for each filament by the following relation
between gas line width and temperature:

$\text{T}=21.9~{}\text{K}\left(\frac{\Delta\text{v}}{\text{~{}km~{}s}^{-1}}\right)^{2}$
(4)

Figure 7: FWHM as a function of median velocity. Points located in the tail of
the Smith Cloud are in orange while points in the tip are in green. Filaments
not in the Smith Cloud are blue.

where $\Delta\text{v}$ is the FWHM as discussed in Section 2. FWHM as a
function of median filament velocity is plotted in Figure 7. The median
temperature of the local filaments is 203 K, indicating they are part of the
cold neutral medium (CNM). The median HVC population temperature is $\sim$7400
K and the mean is $\sim$9300 K. This is expected since the Smith Cloud is
known to have a warm neutral medium (WNM) and has been shown to have a H ii
mass comparable to its H i mass (Putman et al., 2003; Hill et al., 2009). In
particular, Hill et al. (2009) placed a lower bound temperature estimate of
$7000\pm 2000$ K, which these results are consistent with. Apparent from the
graph is a correlation between velocity and temperature of the H i gas along
this line of sight.

Figure 8: Median column density as a function of velocity for each filament
generated from the raw (left) and USM (right) data. These distributions show
the effect of the unsharp mask removing diffuse emission as well as the drop
off in gas density with increasing distance from the disc along the line of
sight.

We also examine the column density of each filament. We evaluate the column
densities by integrating over the FWHM of the line width fitted to each
filament as discussed in 2. Figure 8 shows the median column density within
the merged mask area of each filament as a function of that filament’s
velocity for both the raw and USM data. The raw data shows a maximum density
at v${}_{LSR}\approx$ 0 km s-1followed by an exponentially decreasing
relationship out to higher velocities. We interpret this as a result of the
fact that along this line of sight increasing vLSR corresponds to increased
distance from the Galactic disc. More details on filament column densities, as
well as filament spatial widths, are discussed in Putman et. al. (in prep.).

The majority of filaments detected in the Smith Cloud itself are located away
from the head, closer to the tail and midsection. Looking at Figure 3, it
seems probable there are more filaments in the midsection that are not being
detected due to them being partially or completely cut off from the GALFA-H i
region. Moreover, such filaments would be at the edge of the region where
fil3D tends to pick up noise. The filaments that are detected are aligned with
the morphology of the Smith Cloud itself. There are initially 9 detected after
filtering in this region; however, there was a significant overlap in the
filament contours for two filaments in the tail and two in the body. We
inspected the nodes for these trees and found that in each case the last node
of the first tree and the first node of the second tree were in adjacent
channels with an overlap fraction of 80% and 75% respectively, just below our
threshold of 85%. Given that their contours along the long axis of the
filaments were nearly identical, combined with the greater thermal broadening
in this region, we merged these tree groups into one filament each, leaving 7
trees in the region in total.

Figure 9: Histogram of filament alignment with the plane of sky magnetic field. Table 1: Properties for each filament group. The median value is reported for the B-field alignment, FWHM, and temperature. Group | N | Velocity Range | $|\theta-\overline{\phi}|$ | FWHM | Temp.
---|---|---|---|---|---
|  | ( km s-1) | (°) | ( km s-1) | (K)
Local | 52 | –8-20 | 59.7 | 3.05 | 203
IVC | 13 | 20-65 | 47.2 | 10.1 | 2240
HVC | 7 | 75-110 | 77.3 | 17.8 | 6900

We attempted to investigate the dust content of the Smith Cloud with the
Planck 857 GHz data. We created a map of the dust emission expected in this
region from the Galactic emission alone by creating a column density map
integrated from -60 km s-1< $v_{LSR}$ < 60 km s-1and multiplying by the
$I_{857}/\text{N}_{\text{H\,{i}}}$ ratio from Planck Collaboration et al.
(2014). We then subtracted the expected map from the Planck 857 GHz map to
create a residual map. Figure 10 shows these maps and that there appears to be
a visual excess in the region of the Smith Cloud in the residual map. The
excess in this map at the level of 0.5 MJy/sr was confirmed by randomly
sampling 1000 on and off points and using a 2-sample T-test, however, there
are too many caveats to claim this excess is directly from the Smith Cloud.
Tests of additional regions are needed and the residual map is positive over
the majority of the map indicating the scaling ratio from Planck Collaboration
et al. (2014) was not a good fit in this region. This makes sense given the
low Galactic latitude of this sight-line and shows that caution is needed when
producing expected FIR maps with this ratio.

##  5 Discussion

We present the first findings of velocity-resolved 3D H i filaments in an HVC.
We also identify local filaments with a preferential orientation perpendicular
to the plane-of-sky magnetic field. Here we discuss both findings.

###  5.1 Local 3D Filaments

Overall the local filaments are consistent with the 3D filaments detected by
Kim et al. (2023) at high Galactic latitude. The distinct exception is the
filaments in this low Galactic latitude region are mostly anti-aligned with
the plane-of-sky magnetic field. To further confirm this result, we compared
our findings to the H i orientations in the Clark & Hensley maps (Clark &
Hensley, 2019). Using the same procedure that was done to compare alignment
with the Planck 353-GHz polarization map, we compute a median alignment
between our 3D local filaments and the C&H map of 15.7°, indicating a strong
alignment. We also checked our magnetic field results from Planck by comparing
it with the magnetic field derivation in Soler et al. (2016) and found our
model matches their findings.

Filaments that are perpendicular to the Galactic magnetic field near the plane
have previously been detected in Soler et al. (2020) and Soler et al. (2022),
which looked for H i filaments at |b| < 1.25°and |b| < 10°, respectively. They
associate regions of perpendicular alignment with H ii regions and supernovae
feedback from the Galactic fountain (Shapiro & Field, 1976; Putman et al.,
2012). In particular, Soler et al. (2022) finds more perpendicular filaments
toward the inner galaxy, which also makes sense if caused by the Galactic
fountain since there is a greater concentration of supernovae remnants in the
inner galaxy (e.g., Green, 2015). This is consistent with our findings, since
the region studied here points toward the inner galaxy in the direction of the
Sagittarius Arm. The local filaments in our sample are also preferentially
oriented perpendicular to the Galactic plane.

Our local filament properties can be compared to Kim et al. (2023), which
observed a H i filament population at high Galactic latitude. While we find a
different behavior with respect to the magnetic field, we find a mean
linewidth of 3.72 km s-1and median column density of $10^{19.9}$ cm-2,
compared to their findings of 3.1 km s-1and $10^{19.6}$ cm-2, respectively.
Our somewhat greater line-width may be influenced by the fact that we employ a
velocity resolution of .739 km s-1in the GALFA-H i data whereas Kim et al.
(2023) uses the narrower channels with a .184 km s-1resolution. Our slightly
greater column density value makes sense as well in the context of our
filaments being located closer to the Galactic plane. That being said, the
column density of all of our filaments (Figure 8) is still low compared to the
general Galactic HI (above $10^{21}$ cm-2). Since the dust along this line of
sight is likely associated with the densest HI, the HI filaments detected here
may not be tracing exactly the same material as the Planck data. This could
then also explain the lack of alignment with the Galactic magnetic field.

###  5.2 HVC Filaments

We find 7 filaments in the HVC known as the Smith Cloud, and they are oriented
along its long axis. There is no consensus reason for how filaments form,
given their presence at varying scales and environments (Hacar et al., 2023).
As the Smith Cloud approaches the Galactic disc, it encounters greater and
greater pressure from the surrounding medium. At the same time, ram pressure
stripping of the cloud ablates material, creating fragments that are
potentially condensed by the surrounding medium (Heitsch & Putman, 2009). It
is already known that the head-tail structures of HVCs have more elongated
lower-density structures in the tail (Quilis & Moore, 2001; Heitsch & Putman,
2009). Such conditions are more conducive to filament formation and may be
consistent with warmer filaments towards the trailing tail of the HVC.

The HVC magnetic field may also play a role in the filament formation.
Previous work has shown local H i filaments at higher Galactic latitudes align
with the plane of sky magnetic field as traced by dust polarization (Clark et
al., 2014; Clark et al., 2015; Kim et al., 2023), but to what effect the
magnetic field plays in the formation of the filaments is less certain. While
we find the IVC and HVC filament alignment to be randomly oriented in regard
to the magnetic field traced by 353 GHz dust polarization along the line of
sight, the local ISM dominates the dust column with respect to the IVC dust
(Panopoulou et al., 2019). Given the non-detection or limited detection of
dust in HVCs (e.g., Peek et al., 2009; Lenz et al., 2017), it is reasonable to
assume that the Planck data does not capture IVC and HVC magnetic field
information. Recent estimates of the field strength for the Smith Cloud’s
magnetic field place it at 5 $\mu G$ (Betti et al., 2019), making its
influence on its local environment substantial. Furthermore, Betti et al.
(2019) created a model magnetic field for the Smith Cloud that would give a
magnetic field orientation along the long axis of the Smith Cloud. Since this
is the same orientation as our detected Smith Cloud filaments, they are
potentially aligned with its local magnetic field.

The line widths of the Smith Cloud filaments are consistent with them being
part of a warm neutral medium within the cloud. It will be interesting to
explore the distribution of filaments and filament temperatures further with
future high resolution HI observations. Comparing Figures 2 and 3, we see that
the GBT moment 0 map identifies material in the lower midsection, as well as
the lower extending ridge. With higher-resolution data in the region not
covered by GALFA-H i, fil3d would likely return filaments in these areas as
well.

Figure 10: Top Left: The original Planck 857 GHz map in the region around the
Smith Cloud. Top Right: The expected map created using column density map and
the $I_{857}/\text{N}_{\text{H\,{i}}}$ ratio from Planck Collaboration et al.
(2014). Bottom Right: Residual map, showing the expected map subtracted from
the Planck map with the outline of the Smith Cloud included for reference.

###  5.3 Overall Properties

The trends in velocity FWHM and column density in Figures 7 and 8 can be
understood from the perspective that the farther out we look along this line
of sight (represented at some level by the filament velocity) the greater the
$|z|$ value from the plane becomes. With the FWHMs (and thereby temperatures
from Equation 4), we see the local region has line widths consistent with the
CNM but then scales to the WNM as $|z|$ increases as we reach the Smith Cloud,
which sits 3 kpc below the disc. For column densities, we see the emission in
the raw data peak around 0 km s-1and drop off as we go further from the plane,
which is consistent with the overall observed H i distribution of the Galactic
ISM (Kalberla & Kerp, 2009).

The separate filament groups also correspond to different physical scales.
Assuming a distance of 200 pc, with the given GALFA-H i spatial resolution the
local filaments have an average width (defined as twice the radial profile of
the root node computed in Filfinder) of 0.66 pc, whereas at a distance of 12.4
kpc the HVC filaments have a mean width of 38 pc. These filaments are
significantly larger than the sub-pc local ISM filaments and have not been
studied as extensively in the literature. As such, their formation mechanism
may vary from the smaller scale filaments and there may be multiple filaments
embedded in the large linear structures.

Future work entails searching for filaments in other HVC complexes to see if
properties are shared across different objects. For the Smith Cloud, in
particular, a full high-resolution map is needed to study the filamentary
structure of the entire cloud. An increased knowledge of the magnetic field of
the Smith Cloud, as well as halo clouds in general, is also required to
confirm the filaments align with the cloud’s magnetic field. It is also
possible that filaments may exist in ionized hydrogen as well. The Smith Cloud
has already been mapped in H-$\alpha$ (Hill et al., 2009) at a low resolution,
but doing so at higher resolution may reveal a network of H-$\alpha$ filaments
as seen in Galactic ISM H-$\alpha$ surveys (e.g. Homa et al., 2023).

## Acknowledgements

The authors thank Susan Clark for many helpful discussions and Jay Lockman for
sharing the GBT data of the Smith Cloud. This project makes use of NumPy
(Harris et al., 2020), AstroPy (Astropy Collaboration et al., 2013, 2018),
Matplotlib (Hunter, 2007), Filfinder Koch & Rosolowsky (2015), and Healpy
(Zonca et al., 2019)

## Data Availability

This paper makes use of data from the Galactic Arecibo L Band Feed Array
(GALFA) H i Data Release 2 which are publicly available to download at
https://purcell.ssl.berkeley.edu/, the H i 4$\pi$ Survey, available at
http://cade.irap.omp.eu/dokuwiki/doku.php?id=hi4pi, as well as observations
from the Planck Collaboration, which are publicly accessible at
http://www.esa.int/Planck. In addition, this paper made use of Smith Cloud
data from the Robert C. Byrd Green Bank Telescope, Green Bank, WVA, which is
available upon reasonable request to the authors. Data and code corresponding
to the plots in this paper are also available upon reasonable request to the
authors.

## References

  * Alig et al. (2018) Alig C., Hammer S., Borodatchenkova N., Dobbs C. L., Burkert A., 2018, ApJ, 869, L2
  * André et al. (2014) André P., Di Francesco J., Ward-Thompson D., Inutsuka S. I., Pudritz R. E., Pineda J. E., 2014, in Beuther H., Klessen R. S., Dullemond C. P., Henning T., eds, Protostars and Planets VI. pp 27–51 (arXiv:1312.6232), doi:10.2458/azu_uapress_9780816531240-ch002
  * Astropy Collaboration et al. (2013) Astropy Collaboration et al., 2013, A&A, 558, A33
  * Astropy Collaboration et al. (2018) Astropy Collaboration et al., 2018, AJ, 156, 123
  * Betti et al. (2019) Betti S. K., Hill A. S., Mao S. A., Gaensler B. M., Lockman F. J., McClure-Griffiths N. M., Benjamin R. A., 2019, ApJ, 871, 215
  * Bland-Hawthorn et al. (1998) Bland-Hawthorn J., Veilleux S., Cecil G. N., Putman M. E., Gibson B. K., Maloney P. R., 1998, MNRAS, 299, 611
  * Clark & Hensley (2019) Clark S. E., Hensley B. S., 2019, ApJ, 887, 136
  * Clark et al. (2014) Clark S. E., Peek J. E. G., Putman M. E., 2014, ApJ, 789, 82
  * Clark et al. (2015) Clark S. E., Hill J. C., Peek J. E. G., Putman M. E., Babler B. L., 2015, Phys. Rev. Lett., 115, 241302
  * Green (2015) Green D. A., 2015, MNRAS, 454, 1517
  * HI4PI Collaboration et al. (2016) HI4PI Collaboration et al., 2016, A&A, 594, A116
  * Hacar et al. (2023) Hacar A., Clark S. E., Heitsch F., Kainulainen J., Panopoulou G. V., Seifried D., Smith R., 2023, in Inutsuka S., Aikawa Y., Muto T., Tomida K., Tamura M., eds, Astronomical Society of the Pacific Conference Series Vol. 534, Protostars and Planets VII. p. 153 (arXiv:2203.09562), doi:10.48550/arXiv.2203.09562
  * Harris et al. (2020) Harris C. R., et al., 2020, Nature, 585, 357
  * Heitsch & Putman (2009) Heitsch F., Putman M. E., 2009, ApJ, 698, 1485
  * Hill et al. (2009) Hill A. S., Haffner L. M., Reynolds R. J., 2009, ApJ, 703, 1832
  * Hill et al. (2013) Hill A. S., Mao S. A., Benjamin R. A., Lockman F. J., McClure-Griffiths N. M., 2013, ApJ, 777, 55
  * Homa et al. (2023) Homa J., Schiminovich D., Putman M., diCicco D., Walker S., Mittelman D., 2023, in American Astronomical Society Meeting Abstracts. p. 223.04
  * Hunter (2007) Hunter J. D., 2007, Computing in Science and Engineering, 9, 90
  * Jung et al. (2023) Jung S. L., Grønnow A., McClure-Griffiths N. M., 2023, MNRAS, 522, 4161
  * Kalberla & Kerp (2009) Kalberla P. M. W., Kerp J., 2009, ARA&A, 47, 27
  * Kalberla et al. (2016) Kalberla P. M. W., Kerp J., Haud U., Winkel B., Ben Bekhti N., Flöer L., Lenz D., 2016, ApJ, 821, 117
  * Kim et al. (2023) Kim D. A., Clark S. E., Putman M. E., Li L., 2023, MNRAS,
  * Koch & Rosolowsky (2015) Koch E. W., Rosolowsky E. W., 2015, MNRAS, 452, 3435
  * Lenz et al. (2017) Lenz D., Hensley B. S., Doré O., 2017, ApJ, 846, 38
  * Lockman et al. (2008) Lockman F. J., Benjamin R. A., Heroux A. J., Langston G. I., 2008, ApJ, 679, L21
  * Ma et al. (2023) Ma Y. K., et al., 2023, MNRAS, 521, 60
  * Marasco & Fraternali (2017) Marasco A., Fraternali F., 2017, MNRAS, 464, L100
  * McClure-Griffiths et al. (2006) McClure-Griffiths N. M., Dickey J. M., Gaensler B. M., Green A. J., Haverkorn M., 2006, ApJ, 652, 1339
  * Nichols & Bland-Hawthorn (2009) Nichols M., Bland-Hawthorn J., 2009, ApJ, 707, 1642
  * Panopoulou et al. (2019) Panopoulou G. V., et al., 2019, ApJ, 872, 56
  * Peek et al. (2009) Peek J. E. G., Heiles C., Putman M. E., Douglas K., 2009, ApJ, 692, 827
  * Peek et al. (2018) Peek J. E. G., et al., 2018, ApJS, 234, 2
  * Planck Collaboration et al. (2014) Planck Collaboration et al., 2014, A&A, 571, A11
  * Planck Collaboration et al. (2020) Planck Collaboration et al., 2020, A&A, 641, A3
  * Putman et al. (2003) Putman M. E., Bland-Hawthorn J., Veilleux S., Gibson B. K., Freeman K. C., Maloney P. R., 2003, ApJ, 597, 948
  * Putman et al. (2012) Putman M. E., Peek J. E. G., Joung M. R., 2012, ARA&A, 50, 491
  * Quilis & Moore (2001) Quilis V., Moore B., 2001, ApJ, 555, L95
  * Shapiro & Field (1976) Shapiro P. R., Field G. B., 1976, ApJ, 205, 762
  * Smith (1963) Smith G. P., 1963, Bull. Astron. Inst. Netherlands, 17, 203
  * Sofue et al. (2004) Sofue Y., Kudoh T., Kawamura A., Shibata K., Fujimoto M., 2004, PASJ, 56, 633
  * Soler et al. (2016) Soler J. D., et al., 2016, A&A, 596, A93
  * Soler et al. (2020) Soler J. D., et al., 2020, A&A, 642, A163
  * Soler et al. (2022) Soler J. D., et al., 2022, A&A, 662, A96
  * Wakker et al. (2008) Wakker B. P., York D. G., Wilhelm R., Barentine J. C., Richter P., Beers T. C., Ivezić Ž., Howk J. C., 2008, ApJ, 672, 298
  * Zonca et al. (2019) Zonca A., Singer L., Lenz D., Reinecke M., Rosset C., Hivon E., Gorski K., 2019, The Journal of Open Source Software, 4, 1298

##  Appendix A Additional Smith Cloud Plots

Here we show the ellipse used to represent the on/off boundary regions in the
discussion of dust with respect to the Smith Cloud itself. The region was
chosen to roughly correspond to N${}_{\text{H\,{i}}}$ > $1*10^{20}$ cm-2

Figure 11: Ellipse used for sampling the potential presence of dust overlaid
on the GALFA-H i column density map.


2021 0001

# Energy-Efficient Naming in Beeping Networks

Ny Aina Andriambolamalala
Université Paris Cité  IRIF  CNRS  F-75013 Paris  France
<EMAIL_ADDRESS>Vlady Ravelomanana
Université Paris Cité  IRIF  CNRS  F-75013 Paris  France
<EMAIL_ADDRESS>
###### Abstract

A single-hop beeping network is a distributed communication model in which all
stations can communicate with one another by transmitting only $1-bit$
messages, called beeps. This paper focuses on resolving the distributed
computing area’s two fundamental problems: naming and counting problems. We
are particularly interested in optimizing the energy complexity and the
running time of algorithms to resolve these problems. Our contribution is to
design randomized algorithms with an optimal running time of $O(n\log n)$ and
an energy complexity of $O(\log^{2}n)$ for both the naming and counting
problems on single-hop beeping networks of $n$ stations.

††volume: 178††issue: 1

Energy-efficient Naming in Beeping Networks

##  1 Introduction

Introduced by Cornejo and Kuhn in 2010 [1], the beeping model makes minor
demands on the network devices, which only need to be capable of performing
carrier-sensing to differentiate between silence and the presence of a jamming
signal (considered to be a $1-bit$ message or one beep) on the network. Such
devices have an unbounded local power computation [2]. The authors of [1]
noted that carrier-sensing can typically be performed much more reliably and
requires significantly less energy and resources than the message-sending
model’s devices. The minimization of such energy consumption per node arises,
as the nodes are battery-powered most of the time. Since sending or receiving
messages costs more energy than performing internal computations, a
distributed algorithm’s energy consumption is measured by the maximal over the
waking time slot’s number of all nodes [2, 3, 4, 5, 6, 7] (a node is awake
when it beeps or listens to the network). It is more realistic to consider the
nodes with no prior information regarding the network’s topology and no
identifiers (all nodes are initially indistinguishable). Symmetry breaking
protocols are important tools that allow the design of more elaborate
algorithms. Thus, researchers designed various symmetry breaking protocols,
such as leader election [2, 8, 9, 10, 11, 4, 12, 13, 6], maximal independent
set [14, 15], and naming protocols [16, 17, 3, 18, 19]. In this paper, we
consider the naming problem of the single-hop111The underlying graph of the
network is complete. beeping networks of unknown size $n$, which assigns a
unique label $\operatorname{l}(s)\in\\{1,\,2,\cdots,\,n\\}$ to each node $s.$
We design an energy-efficient randomized naming algorithm succeeding in
$O(n\log n)$ time slots with high probability 222An event $\varepsilon_{n}$
occurs with high probability if $\mathbb{P}[\varepsilon_{n}]\geq
1-\frac{1}{n^{c}}$ for some constant $c>0$, i.e., the probability of error is
inversely proportional to a polynomial in $n.$ (w.h.p. for short) on such a
model, with $O(\log^{2}n)$ energy complexity. First, in Section 2, we present
a deterministic algorithm, naming some $M$ nodes (with $M\leq n$) in $O(M\log
n)$ time slots with $O(M\log n)$ energy complexity. Then, in Section 3, we
address the naming problem for $n$ nodes when the number of nodes, $n$, is
unknown. The algorithm developed to solve the naming problem is then adapted
to address the counting problem, which involves allowing each node to learn
the total number of the nodes. In Section 4, we conjecture a lower bound of
$\Omega(\log n)$ on the beeping network’s naming algorithm’s energy
complexity. Finally, in Section 5, we present some Maple Simulation results
that illustrate our work.

###  1.1 Considered models and complexities measure

####  1.1.1 Beeping network model

In single-hop beeping networks, the nodes communicate with one another during
discrete time slots via a shared beeping channel. Each node has access to a
global clock. As presented in Figure 1, single-hop beeping networks can be
used for modelling an ad-hoc network, in which all nodes are in one another’s
communication range. The nodes can send $1-bit$ messages and perform carrier
sensing to detect any transmission.

Figure 1:

At each time slot, a node independently determines whether to transmit a beep,
listen to the network, or remain idle (asleep). Only the listening nodes can
receive the common channel’s state : namely, Beep if at least one node is
transmitting or Null if no node transmits. This model is also called the BL or
the beep listen model.

####  1.1.2 Complexities measure

######  Definition 1.1 (Time complexity)

The time complexity of an algorithm is defined as the maximum number of time
slots required for all nodes in the network to complete the algorithm.

There are several definitions of energy complexity for a distributed
algorithm, depending on the specific model of transmission and reception
energy cost considered. In this paper, we provide a formal definition of
energy complexity as follows [19, 20, 21].

######  Definition 1.2 (Energy complexity)

A node is considered active if it is transmitting or listening to the network.
In this paper, the energy complexity of a distributed algorithm is defined as
the maximum number of active time slots per node, over all nodes participating
in the algorithm.

###### Remark 1

Some papers consider only transmissions due to the negligible cost of message
receptions to measure a distributed algorithm’s energy complexity [22]. In
this paper, we consider both the transmission and the message reception.

###  1.2 Related works and new results

As the naming problem is a fundamental distributed computing problem [16],
many results exist for this problem. Let us first consider the simplest model,
namely the single-hop network, in which the network’s underlying graph is
complete. In [17], Hayashi, Nakano and Olariu presented a randomized naming
protocol with $O(n)$ running time for radio networks with collision detection
(or RNCD for short), in which the nodes transmit messages of size $O(\log n).$
Note that on RNCD, the nodes can only transmit or listen to the network during
each time slot, and the listening nodes receive only single transmissions. If
more than one node transmits simultaneously, a collision is detected by all
the listening nodes. Later, Bordim, Cui, Hayashi, Nakano and Olariu [18]
presented a naming algorithm for RNCD, terminating w.h.p. in $O(n)$ time slots
with $O(\log n)$ energy complexity. In [23], for radio networks with no
collision detection (RNnoCD for short), Nakano and Olariu designed a naming
protocol, terminating in $O(n)$ time slots w.h.p. with $O(\log\log n)$ energy
complexity. On RNnoCD, all nodes can transmit messages of size $O(\log n)$
during each time slot. Meanwhile, for RNCD, only the messages transmitted
alone are received, but the devices can detect no collision. As the naming and
counting problems are closely related to the network’s size approximation
problem, Jurdziński, Kutyłowski and Zatopiański presented an energy-efficient
algorithm to address this problem with $o(\log\log n)$ energy complexity [5].

Results on the beeping model appeared recently when Chlebus, De Marco and Talo
[19] presented their naming algorithm terminating in $O(n\log n)$ time slots
w.h.p. for the BL model. Moreover, they also provided a $\Omega(n\log n)$
lower bound on such an algorithm’s time complexity. Meanwhile, Casteigts,
Métivier, Robson and Zemmari [24] presented a counting algorithm for the
BcdL333The transmitters can detect collisions on the BcdL model or Beep with
Collision Detection Listen [14, 15].  model terminating in $O(n)$ time slots
w.h.p. They noticed that adapting their algorithm to work on the BL model
would result in a logarithmic slowdown regarding its time complexity. The
following Table 1 compares our results to the existing results of the single-
hop network model. In Table 1, as $n$ is unknown, $N$ represents a polynomial
upper bound on $n$ ($N=\operatorname{Poly}(n)$444In this paper, we define
$\operatorname{Poly}(n)=n^{\alpha}$ for some constant $\alpha>1.$), which is
computed by the nodes using the approximate counting algorithm described in
[25].

Table 1: Comparison between some existing results and ours. Problem | Time | Energy | Probability of
---|---|---|---
and model | complexity | complexity | success
Existing results
Randomized naming |  |  |
on single-hop RNnoCD [23] | $O(n)$ | $O(\log\log n)$ | $1-O\left(\frac{1}{n}\right)$
$n$ known |  |  |
Randomized naming |  |  |
on single-hop beeping networks [19] | $O(n\log n)$ | Not applicable | $1-O\left(\frac{1}{n}\right)$
(BL), $n$ known |  |  |
Randomized counting |  |  |
on single-hop beeping networks [24] | $O(n)$ | Not applicable | $1-O\left(\frac{1}{n}\right)$
(BcdL) |  |  |
Our results
Randomized naming |  |  |
on single-hop BL | $O(n\log n)$ | $O(\log^{2}n)$ | $1-O\left(n^{-c}\right)$
Indistinguishable nodes, |  |  | for some $c>0$
$n$ unknown, Theorem 2 |  |  |
Randomized |  |  |
counting on single-hop BL | $O(n\log n)$ | $O(\log^{2}n)$ | $1-O\left(n^{-c}\right)$
Indistinguishable nodes, |  |  |
$n$ unknown, Theorem 3 |  |  | for some $c>0$

The more realistic model, in which the network’s underlying graph is an
arbitrary connected graph (called the multi-hop network model), gained
importance as a research subject [26]. Czumaj and Davies [27] designed a
deterministic depth-first search (DFS for short) algorithm that initialized
such a network in $O(n\log n)$ time slots. [28] analyses the naming protocol
on such a multi-hop case, but it is restricted to a set of nodes randomly
located in a square area.

##  2 New approach: naming $M$ nodes in a deterministic manner

###  2.1 A first energy-inefficient naming algorithm

For the sake of simplicity without loss of generality, for the remainder of
this section, let us suppose that each node $s$ knows a common upper bound $N$
on $n$ such that $N=\operatorname{Poly}(n)$ and has a unique identifier
denoted $\operatorname{ID}_{s}\in\\{1,\,2,\,\cdots,\,N\\}.$ We note that this
assumption does not limit the generality of our results.

Our new approach employs a known method representing the $\operatorname{ID}$s
by their binary encoding and transmitting the obtained bits one at a time in
reverse order [29].

######  Definition 2.1 ($\textsc{Cid}_{s}$)

$\textsc{Cid}_{s}$ is the binary representation of a given
$\operatorname{ID}_{s}.$ We have
$\textsc{Cid}_{s}=\left[\textsc{Cid}_{s}[0]\textsc{Cid}_{s}[1]\cdots\textsc{Cid}_{s}[\lceil\log_{2}N\rceil]\right]$
such that $\textsc{Cid}_{s}[i]\in\\{0,1\\}.$

Let $M$ ($M\leq n$) represent the number of nodes participating in a specific
stage or phase of the naming algorithm. Each of the $M$ nodes first computes
its $\textsc{Cid}_{s}$ and sends it, bit by bit, over $\lceil
2\log_{2}N+2\rceil=O(\log n)$ time slots to check whether it has the largest
$\operatorname{ID}$ of all nodes. The node with the largest
$\operatorname{ID}$ will take the next available label. During each time slot,
a node $s$ that detects that another node $v$ has a higher
$\operatorname{ID}_{v}$ than $\operatorname{ID}_{s}$ is eliminated (i.e., it
is no longer a candidate to take the next label). Thus, after $\lceil
2\log_{2}N+2\rceil$ time slots, the unique remaining candidate node holding
the largest $\operatorname{ID}$ gets labelled.

######  Definition 2.2 (Season)

A season consists of $\lceil 2\log_{2}N+2\rceil$ time slots.

In what follows, we consider our naming algorithm as successive seasons
denoted $S_{1},\,S_{2},\,\cdots,\,S_{j},\,\cdots,\,S_{M}$ (note that the nodes
do not necessarily know $M$). During season $S_{j}$, each node $s$ sends its
$\textsc{Cid}_{s}$ bit by bit over $\lceil 2\log_{2}N+2\rceil$ time slots
$t_{0},\,t_{1},\,\cdots,\,t_{2\lceil\log_{2}N\rceil+1}.$ To do so, for
$i=0,\,1,\,\cdots,\,\lceil\log_{2}N+1\rceil$, during each couple of time slots
$\\{t_{2i},\ t_{2i+1}=t_{2i}+1\\}$, each node executes the following defined
Test($2i$) protocol. Test($2i$) accepts an even time slot number $2i$ as a
parameter and outputs a status $\in\\{\textsc{Eliminated},$
$\textsc{Active},\textsc{Eliminator}\\}$ at the end of $t_{2i+1}.$ By
executing Test($2i$), a node $s$ can take one status according to the
following rules:

  * •

If $s$ has $\textsc{Cid}_{s}[i]=0$ and detects that at least one node $v$
($v\neq s$) has $\textsc{Cid}_{v}[i]=1$, it becomes Eliminated at the end of
$\\{t_{2i},\,t_{2i+1}\\}.$

  * •

This latter node $v$ becomes an Eliminator.

  * •

If $s$ neither is eliminated nor has eliminated some other node during
$t_{2i},\,t_{2i+1}$, it stays Active.

Let us now define this Test($2i$) protocol.

Algorithm 1. Test$(2i)$ at any node $s.$
Input : The node $s$ has a unique code-word denoted $\textsc{Cid}_{s}$ and
receives the time slot’s number $2i$ as a parameter.  Output :
$\textsc{Status}(s)\in\\{\textsc{Active},\,\textsc{Eliminated},\,\textsc{Eliminator}\\}$
1 if  _$\textsc{Cid}_{s}[i]=0$_ then 2 $s$ beeps at $t_{2i}$ and listens to
the network at $t_{2i+1}=t_{2i}+1$ 3 if  _$s$ hears a beep at $t_{2i+1}$_ then
4 $s$ sets $\textsc{Status}(s)\leftarrow$ Eliminated.  5 else 6 $s$ sets
$\textsc{Status}(s)\leftarrow$ Active.  7 end if  8 9else 10 $s$ listens to
the network at $t_{2i}$ and beeps at $t_{2i+1}$ 11 if  _$s$ hears a beep at
$t_{2i}$_ then 12 $s$ sets $\textsc{Status}(s)\leftarrow$ Eliminator.  13 else
14 $s$ sets $\textsc{Status}(s)\leftarrow$ Active.  15 end if  16 17 end if
18

##### Our deterministic naming algorithm’s description for $M$ nodes.

Consider a set of $M$ participating nodes during the following protocol. At
each even time slot $t_{2i}$, where $i=0,\,1,\,2,\cdots,\,\log_{2}N$, in each
season $S_{j}$, where $j\in\\{1,\,2,\,\cdots,\,M\\}$, each node $s$ executes
the Test($2i$) function. If at least one node $v$ has $\textsc{Cid}_{v}[i]=1$,
then each node $s$ with $\textsc{Cid}_{s}[i]=0$ is eliminated until the
beginning of the next season $S_{j+1}$. At the end of season $S_{j}$, the last
remaining node is assigned the label $j$. By running this process for each
$j\in\\{1,\,2,\,\cdots,M\\}$, we obtain the following.

###### Lemma 2.3

The naming algorithm described above terminates terminates in $O(M\log n)$
time slots and assigns a unique label in $\\{1,\,\cdots,\,M\\}$ to each of the
$M$ nodes.

###  2.2 Energy optimization principle

The previously presented algorithm is not energy-efficient as all nodes wake
up (to beep or listen to the network) during the $O(M\log n)$ time slots. To
improve this energy consumption, we will subdivide the set of participants
into small groups and pass the last identifier of a group to the next group to
keep an order in the successive numberings. To do this, we need a
deterministic algorithm capable of numbering the members of a group without
knowing the exact cardinality of this group. To do this, we need to define
several sub-procedures and definitions.

######  Definition 2.4 (Time To Listen or $\operatorname{ttl}(s)$ for short)

$\operatorname{ttl}(s)$ is an even time slot $t_{2i},\,\mbox{ for
}i=0,\,1,\,\cdots,\,\lceil\log_{2}N\rceil,$ of any even season
$S_{2j-1},\,\mbox{for }j=1,\,2,\,\cdots,\,M,$ such that the node $s$ has been
eliminated during the couple of time slots $(t_{2i},\,t_{2i}+1)$, that is, the
node $s$ has $\textsc{Cid}_{s}[i]=0$, and some unlabeled node $v$ has
$\textsc{Cid}_{v}[i]=1$, so $s$ sets $t_{2i}$ as its $\operatorname{ttl}(s).$

$\operatorname{ttl}(s)=\max_{i=0,\,1,\,\cdots}\\{t_{2i}\mbox{ such that
}\textsc{Cid}_{s}[i]=0\mbox{ and }\exists\mbox{ an unlabeled node }v(v\neq
s)\mbox{ such that }\textsc{Cid}_{v}[i]=1\\}.$

For $i=0,\,1,\,\cdots,\,\lceil\log_{2}N\rceil$ and $j=1,\,2,\,\cdots,\,M$, a
node $s$ must wake up and execute Test$(2i)$ at $t_{2i}=\operatorname{ttl}(s)$
during the even seasons $S_{2},\,S_{4},\,\cdots,\,S_{2k}$ where $S_{2k}$ is
the even season during which $s$ is no longer eliminated.

######  Definition 2.5 (Time To Notify or $\operatorname{TTN}(s)$)

$\operatorname{TTN}(s)$ is a set of even time slots $\\{t_{2i}\\},\,\mbox{for
}i=0,\,1,\,\cdots,\,\lceil\log_{2}N\rceil,$ of any odd season
$S_{2j-1},\,\mbox{for }j=1,\,2,\,\cdots,\,M,$ such that the node $s$ has
eliminated some other nodes during the couple of time slots
$(t_{2i},\,t_{2i}+1).$ More precisely, if during any season
$S_{j},\,j=1,\,2,\,\cdots,\,M,$ the node $s$ has $\textsc{Cid}_{s}[i]=1$ and
some remaining unlabeled node $w$ has $\textsc{Cid}_{w}[i]=0$, then $s$ stores
$t_{2i}$ in $\operatorname{TTN}(s).$

$\operatorname{TTN}(s)=\\{t_{2i}\\}_{i=0,\,1,\,\cdots}\mbox{ such that
}\textsc{Cid}_{s}[i]=1\mbox{ and }\exists\mbox{ an unlabeled node }w(w\neq
s)\mbox{ such that }\textsc{Cid}_{w}[i]=0.$

Let $S_{l}$ be the season during which the node $s$ gets labelled. For
$i=0,\,1,\,\cdots,\,\lceil\log_{2}N\rceil,\,j=1,\,2,\,\cdots,\,M$, during the
seasons $S_{j+1},\,S_{j+2},\,\cdots,\,S_{l}$, the node $s$ must execute
Test$(2i)$ at each time slot $t_{2i}$, saved until season $S_{j}$ in its
$\operatorname{TTN}(s)$, to notify the other nodes still eliminated during
these seasons.

###### Remark 2

For $i=0,\,1,\,\cdots,\,\lceil\log_{2}N\rceil,\,$ when a node $s$ adds
$t_{2i}$ into its $\operatorname{TTN}(s)$, it no longer has an active neighbor
$w$ that holds $\textsc{Cid}_{w}[k]=1,k>i.$ Thus, $s$ sets its
$\operatorname{ttl}(s)$ to a specific value (say $-2$ as a sentinel value)
which corresponds to none of the even time slots
$t_{2i}(i\in\\{0,\,\cdots,\,\lceil\log_{2}N\rceil\\})$.

In what follows, we use these two new definitions to design our deterministic
naming algorithm.

###  2.3 Description of our deterministic naming algorithm

##### Initial states of the nodes:

Before executing the following defined algorithm, each node is sleeping (its
radio is switched off). Each node $s$ initializes its local variables
$\operatorname{ttl}(s)$ $\textsc{Status}(s)$ to Null and
$\operatorname{TTN}(s)$ to the empty set $\\{\\}.$

Each node can wake up at any couple of time slots
$(t_{2i},\,t_{2i+1}),\,i=0,\,1,\,\cdots,\,\lceil\log_{2}N\rceil,$ of any
season $S_{j},\,j=1,\,2,\,\cdots,\,M,$ by calling the Test$(2i)$ protocol. The
node returns to the sleeping state after each call of Test$(2i).$ Each node
$s$ with the Eliminated status sleeps (its radio is switched off and it cannot
execute Test$(2i)$) until the next season, when it resets its status.

##### High-level description of the algorithm :

First, at time slot $t_{0}$ of season $S_{1}$, each node $s$ sets
$\textsc{Status}(s)\leftarrow$Test$(0)$ (line $6$ of Algorithm 2). The
Eliminated nodes at $t_{0}$ record $0$ as their $\operatorname{ttl}(s)$ (line
$13$ of Algorithm 2). Meanwhile, each node $v$ with the Eliminator status adds
$0$ into its $\operatorname{TTN}(v)$ and sets its $\textsc{Status}(v)$ to
Active (line $16$ of Algorithm 2). Afterwards, for each time slot
$t_{2i},\,i=0,\,\cdots,\,\lceil\log_{2}N\rceil$ of each season
$S_{j},\,j=1,\,\cdots,\,M$, each node $s$ executes Test$(2i)$ only if one of
the following is satisfied (lines $5-7$ of Algorithm 2) :

  * •

$\textsc{Status}(s)=\textsc{Null}$ ($s$ starts a new season), and
$t_{2i}\in\\{\operatorname{TTN}(s)\bigcup\\{\operatorname{ttl}(s)\\}\\}$,

  * •

$\textsc{Status}(s)=\textsc{Active}$ i.e., at the time slot $t_{2i-2}$, the
node $s$ executed Test$(2i-2)$, which returned Active or Eliminator. Note that
at line $16$ of Algorithm 2, all Eliminator nodes become Active.

Each such execution of Test$(2i)$ works as described in the time slot $t_{0}$
: If Test$(2i)$ returns Eliminated, the node $s$ records $t_{2i}$ as its
$\operatorname{ttl}(s)$ and sets its $\textsc{Status}(s)$ to Eliminated (line
$4$ of Algorithm 1 and line $13$ of Algorithm 2). Otherwise, if Test$(2i)$
returns Eliminator, $s$ adds $t_{2i}$ into its $\operatorname{TTN}(s)$ and
sets its $\textsc{Status}(s)$ to Active (line $11$ of Algorithm 1 and line
$16$ of Algorithm 2). Finally, if Test$(2i)$ returns Active, the node $s$ sets
it as its $\textsc{Status}(s)$ (lines $6$ and $13$ of Algorithm 1 and line
$10$ of Algorithm 2). At the end of each season, the remaining unique Active
node takes the next available label, and before proceeding to the next season,
each node $s$ resets its $\textsc{Status}(s).$

For better comprehension, in what follows, we illustrate one example of the
DeterministicNaming($N$) algorithm’s execution using a binary tree, as done in
[30]. By doing so, we count the waking time slot’s number of a given node (red
or black node in the following figures).

###  2.4 Representing the DeterministicNaming($N$) algorithm’s execution with
a binary tree

##### Legends for the following figures:

  * Shapes

The hexagonal shapes above each node of the tree represent
$\operatorname{ttl}(s)$, the squares represent $\operatorname{TTN}(s)$, and
the circles represent the other waking time slots.

  * Numbers

The number inside these shapes defines the season during which the node $s$
wakes up at a time slot. Meanwhile, the numbers outside the shapes represent
the sleeping time slots (when the node does not execute Test$(2i)$). Finally,
the numbers inside the tree’s nodes represent each even time slot of the
algorithm’s execution.

Figure 2: One path of the tree represents the $\textsc{Cid}_{s}$ of a node
$s$, and one edge represents one bit of this $\textsc{Cid}_{s}$ : Left edges
correspond to bit $1$, and right edges correspond to bit $0.$ For example, the
considered red or black node $s$ has $\textsc{Cid}_{s}=1010.$ Each such tree’s
node depicts each even time slot $t_{2i}$ of the algorithm’s seasons, while
the leaves represent the stations executing an algorithm.

During season $S_{1}$, the node $s$ wakes up once at time slot $t_{0}$, adds
$0$ into its $\operatorname{TTN}(s)$, and wakes up and gets eliminated at
$t_{2}.$ It sets $t_{2}$ as its $\operatorname{ttl}(s)$ and sleeps until the
beginning of season $S_{2}.$ Node $1$ gets labelled at the end of season
$S_{1}.$

During $S_{2}$, $s$ wakes up at $t_{0}\in\operatorname{TTN}(s)$, sleeps, and
wakes up at $t_{2}\in\operatorname{ttl}(s).$ Then, it gets eliminated at
$t_{2}$, and sleeps until $S_{3}$ begins. Node $2$ gets labelled at the end of
$S_{2}.$

Seasons $S_{3}$ and $S_{4}$ work exactly as season $S_{2}.$

Then, during $S_{5}$, $s$ wakes up at $t_{0}\in\operatorname{TTN}(s)$, sleeps,
and wakes up at $t_{2}\in\operatorname{ttl}(s).$ Since no more unlabeled node
can eliminate $s$ at $t_{2}$, it wakes up at each time slot until $t_{6}$,
when it gets eliminated. It adds $t_{4}$ into its $\operatorname{TTN}(s)$,
sets its $\operatorname{ttl}(s)$ to $t_{6}$, and sleeps until $S_{6}$ begins.
Node $5$ gets labelled at the end of $S_{5}.$

During $S_{6}$, $s$ wakes up at $t_{0}\in\operatorname{TTN}(s)$, sleeps, and
wakes up at $t_{4}\in\operatorname{TTN}(s).$ It then sleeps and wakes up at
$t_{6}\in\operatorname{ttl}(s).$ Since no more unlabeled node can eliminate
it, $s$ wakes up at $t_{8}$ and gets labelled.

Algorithm 2. DeterministicNaming($N$) at any node $s$
Input : An upper bound $N$ on $n$ and a unique
$\operatorname{ID}_{s}\in\\{1,\,2,\,\cdots,\,N\\}.$ Output : A unique label
$\operatorname{l}(s)\in\\{1,\,2,\,\cdots,\,M\\}.$ 1 2$s$ encodes its
$\operatorname{ID}_{s}$ into a binary code-word
$\textsc{Cid}_{s}\leftarrow\\{0,1\\}^{\lceil\log_{2}N+1\rceil}.$ 3 $s$ sets
$\operatorname{l}(s)\leftarrow 0$,
$\operatorname{ttl}(s)\leftarrow\textsc{Null}$,
$\operatorname{TTN}(s)\leftarrow\\{\\}$, $j\leftarrow
1,\textsc{Status}(s)\leftarrow\textsc{Null}.$ 4 while
_$\operatorname{l}(s)=0$_ do 5 for  _$i\leftarrow 0$ to
$\lceil\log_{2}N\rceil$_ do 6 if  _$(\textsc{Status}(s)=\textsc{Null}$ and
$(\operatorname{ttl}(s)=t_{2i}$ or $t_{2i}\in\operatorname{TTN}(s)$ or $j=1))$
or $(\textsc{Status}(s)=\textsc{Active})$ _ then 7 $s$ sets
$\textsc{Status}(s)\leftarrow\textsc{Test}(2i)$ and sleeps.  8 end if  9 10
switch  _$\textsc{Status}(s)$_ do 11 case  _Active_ do 12 $s$ removes $t_{2i}$
from its $\operatorname{TTN}(s).$ 13 if  _$\textsc{Cid}_{s}[i]=0$_ then 14
resets $\operatorname{ttl}(s).$ 15 end if  16 17 end case  18 case
_Eliminated_ do 19 $s$ sets $t_{2i}$ as its $\operatorname{ttl}(s).$ 20 end
case  21 case  _Eliminator_ do 22 $s$ adds $t_{2i}$ into its
$\operatorname{TTN}(s)$ and sets
$\textsc{Status}(s)\leftarrow\textsc{Active}.$ 23 end case  24 25 end switch
26 27 end for  28 29 if  _$\textsc{Status}(s)=\textsc{Active}$_ then 30 $s$
sets $\operatorname{l}(s)\leftarrow j.$ 31 end if  32 $s$ sets $j\leftarrow
j+1.$ 33 end while

###### Lemma 2.6

In single-hop beeping networks of size $n$, there exists a deterministic
algorithm that names $M$ distinct ($M\leq n$) nodes in $O(M\log n)$ time
slots, with all nodes being awake the whole execution of the algorithm.

In what follows, let $W(s)$ be the total number of waking time slots of any
node $s$ during Algorithm 2’s execution; let $W_{\operatorname{TTN}}(s)$,
$W_{\operatorname{ttl}}(s)$ and $W_{o}(s)$ correspond to the
$\operatorname{TTN}(s)$ total waking time slots, the $\operatorname{ttl}(s)$,
and the other total waking time slots, respectively. Moreover, let $w,\,y,\,z$
be the nodes with the largest number of
$\operatorname{ttl},\,\operatorname{TTN}$, and other waking time slots,
respectively. Thus, we have

$W(s)=W_{\operatorname{TTN}}(s)+W_{\operatorname{ttl}}(s)+W_{o}(s)\leq
W_{\operatorname{ttl}}(w)+W_{\operatorname{TTN}}(y)+W_{o}(z)\,.$ (1)

Here, it is straightforward to observe that $w$ is the last node to get
labelled on the network (for example, the red or black node in Figure 3).

Figure 3: The worst case for $\operatorname{ttl}.$

######  Definition 2.7 ($M_{i}$)

For $i=1,\,2,\,\cdots,\lceil\log_{2}N\rceil,$ let $M_{i}(w)$ be the number of
nodes $s_{1},\,s_{2},\,\cdots,$ having
$\textsc{Cid}_{s_{1}}[i]=\textsc{Cid}_{s_{2}}[i]=\cdots=1$ when the last node
$w$ to get labelled on the network has $\textsc{Cid}_{w}[i]=0.$

Let us consider the set
$\mathcal{M}(w)=\\{M_{0}(w),\,M_{1}(w),\,\cdots,\,M_{\lceil\log_{2}N\rceil}(w)\\}.$
First, according to the definition of the DeterministicNaming$(N)$ algorithm,
one node gets labelled at the end of each season, so $M_{i}(w)$ nodes are
labelled after each $M_{i}(w)$ seasons. As the considered node $w$ receives
its label when each of the $M-1$ other nodes receives its label, we have

$\sum_{i}M_{i}(w)=M,$ (2)

Second, according to the definition of $\operatorname{ttl}(w)$, the node $w$
wakes up $M_{i}(w)+1$ times at any time slot
$t_{2i}\in\operatorname{ttl}(s),\,i=1,\,2,\,\cdots,\,\lceil\log_{2}N\rceil,$
until no other node $v$ has $\textsc{Cid}_{v}[i]=1$ ($w$ wakes up during
$M_{i}(w)+1$ seasons, once for the first check and $M_{i}(w)$ times until no
other node $v$ has $\textsc{Cid}_{v}[i]=1$). Thus,

$W_{\operatorname{ttl}}(w)\leq\sum_{i}^{O(\log N)}M_{i}(w)+1\leq O(M+\log N).$
(3)

Let us now consider an arbitrary node $y.$ By definition,
$\operatorname{TTN}(y)$ is a set of even time slots during which $y$ must wake
up until getting labelled to notify all nodes with a lesser
$\operatorname{ID}$ that they are eliminated.

######  Definition 2.8 ($L_{i}$)

For $i=1,\,2,\,\cdots,\,\lceil\log_{2}N\rceil,$ for an arbitrary unlabelled
node $y$, let $L_{i}(y)$ be the number of unlabeled nodes with higher
$\operatorname{ID}$s than $\operatorname{ID}_{y}$ and with $\textsc{Cid}[i]=1$
when $y$ has $\textsc{Cid}_{y}[i]=1.$

For $\operatorname{ttl}$, let us consider
$\mathcal{L}(y)=\\{L_{0}(y),\,L_{1}(y),\,\cdots,\,L_{O(\log N)}(y)\\}.$ If $y$
has $\textsc{Cid}_{y}[i]=1$, it wakes up at $t_{2i}\in\operatorname{TTN}(y)$
during $L_{i}(y)$ seasons. As $L_{i}(y)$ nodes are labelled after each
$L_{i}(y)$ seasons, we have

$\sum_{i}L_{i}(y)<M,$ (4)

As a consequence,

$W_{\operatorname{TTN}}(y)\leq O(M).$ (5)

Let us consider a node $z$: $z$ wakes up at only one season at any time slot
$t_{i}\notin\\{\operatorname{TTN}(z)\bigcup\\{\operatorname{ttl}(z)\\}\\}.$
Hence, we have

$W_{o}(z)\leq\sum_{i=1}^{\log N}O(1)\leq O(\log N)\leq O(\log n)\,.$ (6)

Finally, by applying (3), (5), and (6) to (1), we achieve the desired result.

$\square$

A Maple simulation illustrates these results in Section 5.

###### Theorem 1

In single-hop beeping networks of size $n$, suppose that no node knows $n$,
but a polynomial upper bound $N$ on $n$ is given in advance to all nodes and
the nodes, have a unique $\operatorname{ID}\in\\{1,\,2,\,\cdots,\,N\\}.$ A
deterministic naming algorithm assigns a unique label to each node in $O(n\log
n)$ time slots, with no node being awake for more than $O(n\log n)$ time
slots.

Proof. By applying $M=n$ to Lemma 2.6, we achieve the desired result.
$\square$

##  3 Our energy-efficient randomized algorithms

###  3.1 The naming algorithm

This section employs Algorithm 2 as a subroutine protocol to design a
randomized naming algorithm with $O(\log n)$ energy complexity.

######  Definition 3.1 (Period)

A period is the time complexity of one execution of Algorithm 2 by $O(\log n)$
nodes and consists of $O(\log^{2}n)$ time slots.

######  Definition 3.2 (Group)

A group $G_{k}$ is a set of nodes that will execute Algorithm 2 during any
period $k$,
$\left(k=1,\,2,\,\cdots,\,\Theta\left(\frac{n}{\log n}\right)\right).$

In what follows, we distribute the nodes into $\Theta\left(\frac{n}{\log
n}\right)$ groups to obtain $\Theta(\log n)$ nodes in each group with high
probability. The primary idea behind this is to make each of the
$\Theta\left(\frac{n}{\log n}\right)$ groups run the DeterministicNaming($N$)
protocol, one group after another during $\Theta\left(\frac{n}{\log n}\right)$
periods, instead of making all $n$ nodes execute it once. As each group counts
at most $O(\log n)$ nodes, we have $O(\log^{2}n)$ waking time per node by
applying $M=O(\log n)$ to Lemma 2.6 for each period.

Recall that we assume the total number of nodes to be unknown and the nodes to
be initially indistinguishable in this section. In addition, all nodes must
know a linear approximation $u$ on $n.$ This network’s size approximation
problem has been well studied in the distributed computing area; in
particular, Brandes, Kardas, Klonowski, Pająk and Wattenhofer [25] designed a
randomized linear size approximation algorithm, that terminated w.h.p. in
$O(\log n)$ time slots.

  1. 1.

Our first idea is to make all nodes compute $u$ in $O(\log n)$ time slots
using the algorithm designed by [25]. This algorithm can be parameterized to
make $u\in[\frac{1}{2}n,\,2n]$ (i.e., $2u\in[n,4n]$ will be locally known by
each node). Each node then sets $N=(2u)^{2}$
$\left(N=O\left(n^{2}\right)\right)$ and selects uniformly at random to be
entered into one of the
$\lceil\frac{2u}{\log{2u}}\rceil=\Theta\left(\frac{n}{\log n}\right)$ groups
$G_{1},\,G_{2},\,\cdots,\,G_{\lceil\frac{2u}{\log{2u}}\rceil}.$

###### Lemma 3.3

When $n$ nodes randomly and independently choose to enter $\left(\frac{n}{\log
n}\right)$ groups, there are $\Theta(\log n)$ nodes in each group with
probability $1-O(n^{-1})$.

  2. 2.

Each node $s$ then randomly selects a unique $\operatorname{ID}_{s}$ from
$\\{1,\,2,\,\cdots,\,N\\}.$

  3. 3.

Afterwards, all groups sequentially run the DeterministicNaming$(N)$ protocol,
one group after another:

     * •

First, group $G_{1}$ nodes execute DeterministicNaming$(N)$ to name
themselves, while all the other nodes sleep during $\lceil
4\log^{2}N\rceil=\Theta(\log^{2}n)$555Using the Chernoff Bounds, each group
counts at most $2\log N$ nodes. time slots. At the end of these first
$\Theta(\log^{2}n)$ time slots, each node $s$ of group $G_{1}$ has a unique
label $\operatorname{l}(s)\in\\{1,\,2,\,\cdots,\,|G_{1}|\\}.$

     * •

During some extra $\lceil\log_{2}N+1\rceil$ time slots, the last labelled node
in $G_{1}$ sends its label bit by bit to all nodes of the next group, $G_{2}.$
In parallel, each node $v$ of $G_{2}$ wakes up, listens to the network, and
saves the received value into a variable denoted
$\operatorname{l}_{\textsc{Prev}}(v).$

     * •

Second, by running the DeterministicNaming($N$) protocol, each node $v$ of
$G_{2}$ receives a label
$\operatorname{l}(v)\in\\{1,\,2,\,\cdots,\,|G_{2}|\\}.$ Each node must update
$\operatorname{l}(v)\leftarrow\operatorname{l}(v)+\operatorname{l}_{\textsc{Prev}}(v)$
for its label $\operatorname{l}(v)$ to belong to
$\\{|G_{1}|+1,\,|G_{1}|+2,\,\cdots,\,|G_{1}|+|G_{2}|\\}.$

     * •

We finally make each subsequent couple of groups
$\\{\\{G_{2},\,G_{3}\\},\,\\{G_{3},\,G_{4}\\},\,\cdots,\,\\{G_{\Theta\left(\frac{2u}{\log
u}\right)-1},\,G_{\Theta\left(\frac{2u}{\log u}\right)}\\}\\}$ sequentially
execute these previously described computations, one couple after another.

To make any node $s$ know whether it has the last label of its group, we
modify the DeterministicNaming$(N)$ protocol by making a node $s$ that was
labelled during a season $S_{j}$ wake up during the entire season $S_{j+1}$ to
listen to the network. By doing so, if $s$ hears a beep during this season, it
knows that some other node will take the next label. Each node consequently
wakes up during one entire season, but these waking time slots are additive to
the node’s energy complexity; thus, these extra $O(\log n)$ waking time slots
do not affect our $O(\log n)$ energy complexity.

###### Theorem 2

In single-hop beeping networks of size $n$, if $n$ is unknown by all nodes and
the nodes are initially indistinguishable, there exists a randomized naming
algorithm that assigns a unique label to each node in $O(n\log n)$ time slots
w.h.p. No node is awake for more than $O(\log^{2}n)$ time slots during its
execution.

Proof. On the one hand, the RandomizedNaming($u$) algorithm uses the
DeterministicNaming($N$) protocol as a subroutine. Let us denote the time
complexity of the DeterministicNaming($N$) algorithm as $T_{D}.$ Per [25],
$u=\Theta(n)$, and with $\Theta\left(\frac{2u}{\log{2u}}\right)$ calls of
DeterministicNaming($N$), our RandomizedNaming($u$) algorithm has

$\Theta\left(\frac{2u}{\log{2u}}\right)\times
T_{D}=\Theta\left(\frac{n}{\log{n}}\right)\times T_{D}\mbox{ time
complexity.}$

By Lemma 3.3, the number of nodes participating in each call of
DeterministicNaming($N$) is at most $O(\log n)$ w.h.p. Thus, by applying
$M=O(\log n)$ to Lemma 2.6, we obtain $T_{D}=O(\log^{2}n)$, implying $O(n\log
n)$ time complexity of Algorithm 3.

On the other hand, each node $s$ may be awake

  * •

during one execution of the DeterministicNaming($N$) protocol,

  * •

during $O(\log n)$ extra times to check whether it has the last label.

  * •

Moreover, during $O(\log n)$ time slots when it sends its label to the next
group.

Therefore, by applying $M=O(\log n)$ to Lemma 2.6, the energy complexity of
DeterministicNaming($N$) is $O(\log^{2}n).$ $\square$

Algorithm 3. RandomizedNaming($u$) at any node $s$
Input : A linear approximation $u$ on $n$ computed in $O(\log n)$ time slots
by executing the presented algorithm by [25].  Output : The node $s$ has a
unique label $\operatorname{l}(s)\in\\{1,\,2,\,\cdots,\,n\\}.$ 1 $s$ sets
$N\leftarrow(2u)^{2}$ and randomly chooses one $\operatorname{ID}_{s}$ from
$\\{1,\,2,\,\cdots,\,N\\}.$ 2 $s$ randomly chooses to enter one group $G(s)$
from $G_{1},\,G_{2},\,\cdots,\,G_{\lceil\frac{2u}{\log{2u}}\rceil}$ and sets
$\operatorname{l}_{\textsc{Prev}}(s)\leftarrow 0.$ 3 for  _$j$ from
$1\rightarrow\lceil\frac{2u}{\log{2u}}\rceil-1$_ do 4 5 if  _$G(s)=G_{j+1}$_
then 6 $s$ sleeps during $\Theta(\log^{2}N)$ time slots corresponding to the
time complexity of the modified DeterministicNaming($N$) protocol executed by
one group.  7 After these $\Theta(\log^{2}N)$ time slots, $s$ wakes up,
listens to the network during $O(\log N)$ time slots to get the last assigned
label and saves this value into its $\operatorname{l}_{\textsc{Prev}}(s).$ 8 9
end if  10 if  _$G(s)=G_{j}$_ then 11 $s$ sets
$\operatorname{l}(s)\leftarrow$DeterministicNaming($N$).  12 $s$ updates
$\operatorname{l}(s)\leftarrow\operatorname{l}(s)+\operatorname{l}_{\textsc{Prev}}(s).$
13 if  _$s$ is the last labeled node_ then 14 $s$ sends its label
$\operatorname{l}(s)$ bit by bit and sleeps.  15 16 end if  17 18 end if  19
20 end for  21

###  3.2 Adapting our naming algorithm to have a randomized counting algorithm

Using Algorithm 3, we can design a counting algorithm with $O(n\log n)$ time
complexity and $O(\log^{2}n)$ energy complexity on the single-hop BL network.
To do so, we add the following computations after running Algorithm 3 :

  1. 1.

As Algorithm 3 terminates after, at most,
$\lceil\frac{2u}{\log{2u}}\rceil\times\lceil 4\log^{2}N\rceil\leq\lceil 8n\log
N\rceil$ time slots, all nodes wake up after $\lceil 8n\log N\rceil$ time
slots (counted from the first time slot of season $S_{1}$) to listen to the
network.

  2. 2.

The last labelled node (in the last group) sends its label bit by bit.

This adaptation yields the following result:

###### Theorem 3

In single-hop beeping networks of size $n$, if $n$ is unknown by all nodes and
the nodes are initially indistinguishable, there exists a randomized counting
algorithm that allows all nodes to know the exact value of $n$, in $O(n\log
n)$ time slots w.h.p, with no node being awake for more than $O(\log^{2}n)$
time slots.

Proof. First, according to the definition of the naming problem, if, at the
end of the last group’s call of DeterministicNaming$(N)$, all nodes wake up to
listen to the network, and the last labelled node sends its label bit by bit,
this transmitted value corresponds w.h.p. to the exact number of the network’s
nodes.

On the other hand, as the adaptation consists of having each node wake up
during extra $O(\log^{2}n)$ time slots, by Lemma 2.6, the time complexity of
our counting algorithm is $O(n\log n)$ while its energy complexity remains
$O(\log^{2}n).$ $\square$

##  4 Lower bound on the energy complexity of the single-hop beeping networks
naming algorithms

In [19], the authors presented $\Omega(n\log n)$ lower bound for the running
time of any randomized naming algorithm. Note that in [2], Chang et al.
studied the energy complexity of leader election, approximate counting, and
census in several models of wireless radio networks with messages of unbounded
size. In this paragraph, we conjecture a lower bound on the energy complexity
of any randomized naming algorithm on radio and beeping networks.

###### Conjecture 1

The energy complexity of any randomized algorithm that solves the naming
problem with constant probability is $\Omega(\log n).$

The intuition of proof for Conjecture 1 lies from the proof of the lower bound
on time complexity given in [19]. We tried to use the Yao’s minimax principle
[31] but all our attempts in this direction failed as nodes can namely use
non-uniform probabilities.

##  5 Maple simulation

In this section, we present a sequential Maple simulation result of Algorithm
2’s execution. This Maple simulation works as follows :

  * •

We first represent $n$ nodes by a matrix $\mathbb{M}$ with $n$ lines and
$O(\log n)$ columns. Each line corresponds to the Cid of a node.

  * •

We then sort the matrix $\mathbb{M}$ by lines.

  * •

Afterwards, we simulate the nodes, executing Algorithm 2 in parallel, by
browsing $n$ times through $\mathbb{M}$, one column after another. Browsing
once through the columns of $\mathbb{M}$ allows us to label one node and count
its waking time slots number.

  * •

We finally retain the maximal value of the whole nodes waking time slots
number as the algorithm’s empirical energy complexity.

Figure 4 compares the algorithm’s empirical energy complexity (the green or
grey graph) with our theoretical result (the red or black graph) for a varying
number of nodes.

Figure 4: The Algorithm 2’s energy complexity for a set of
$\lceil\log_{2}N\rceil$ nodes where $N=n^{2}$ and $n$ varies from $100$ to
$10^{10}$.

The Maple codes are available at
https://www.irif.fr/~nixiton/initLoop.mw or
https://www.irif.fr/~nixiton/initLoop.pdf

## Conclusion

In this paper, we focus on the naming problem of single-hop beeping networks
of size $n$. When the nodes have no information about $n$ and are initially
indistinguishable, we design a randomized algorithm terminating w.h.p. in
optimal $O(n\log n)$ time slots, with a $O(\log^{2}n)$ energy complexity. Our
algorithm can be used to solve the counting problem, returning the exact
number of network nodes in $O(n\log n)$ time slots with $O(\log^{2}n)$ energy
complexity. It will be interesting to consider adapting our protocols for the
multi-hop beeping network model, which is much more realistic than the single-
hop model. We conjecture that $\Omega(\log n)$ is the energy complexity of any
randomized naming algorithm in Beeping Networks.

## References

  * [1] Cornejo A, Kuhn F.  Deploying wireless networks with beeps.  In: International Symposium on Distributed Computing, volume 6343. Springer, 2010 pp. 148–162.
  * [2] Chang YJ, Kopelowitz T, Pettie S, Wang R, Zhan W.  Exponential separations in the energy complexity of leader election.  In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, volume 15. ACM, Association for Computing Machinery, 2017 pp. 771–783.
  * [3] Nakano K, Olariu S.  Energy-efficient initialization protocols for radio networks with no collision detection.  In: International Conference on Parallel Processing. 2000 pp. 263–270.
  * [4] Lavault C, Marckert JF, Ravelomanana V.  Quasi-optimal energy-efficient leader election algorithms in radio networks.  _Journal of Information and Computation_ , 2007.  205(5):679–693.
  * [5] Jurdziński T, Kutyłowski M, Zatopiański J.  Energy-efficient size approximation of radio networks with no collision detection.  In: International Computing and Combinatorics Conference. Springer, 2002 pp. 279–289.
  * [6] Kardas M, Klonowski M, Pajak D.  Energy-efficient leader election protocols for single-hop radio networks.  In: Parallel Processing (ICPP), 2013 42nd International Conference on. IEEE, 2013 pp. 399–408.
  * [7] Ravelomanana V.  Time-Optimal and Energy-Efficient Size Approximation of Radio Networks.  In: Distributed Computing in Sensor Systems (DCOSS), 2016 International Conference on. IEEE, 2016 pp. 233–237.
  * [8] Kutten S, Pandurangan G, Peleg D, Robinson P, Trehan A.  Sublinear bounds for randomized leader election.  In: International Conference on Distributed Computing and Networking, volume 561. Springer, 2013 pp. 348–362.
  * [9] Jurdziński T, Kutyłowski M, Zatopiański J.  Efficient algorithms for leader election in radio networks.  In: Proceedings of the twenty-first annual symposium on Principles of distributed computing. ACM, 2002 pp. 51–57.
  * [10] Ghaffari M, Haeupler B.  Near optimal leader election in multi-hop radio networks.  In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 2013 pp. 748–766.
  * [11] Ghaffari M, Lynch N, Sastry S.  Leader election using loneliness detection.  _Distributed Computing_ , 2012.  25(6):427–450.
  * [12] Ramanathan MK, Ferreira RA, Jagannathan S, Grama A, Szpankowski W.  Randomized leader election.  _Distributed Computing_ , 2007.  19(5-6):403–418.
  * [13] Nakano K, Olariu S.  Uniform leader election protocols for radio networks.  _IEEE Trans. on Parallel Distrib. Syst._ , 2002.  13(5):516 – 526.
  * [14] Afek Y, Alon N, Bar-Joseph Z, Cornejo A, Haeupler B, Kuhn F.  Beeping a maximal independent set.  _Distributed computing_ , 2013.  26(4):195–208.
  * [15] Scott A, Jeavons P, Xu L.  Feedback from nature: an optimal distributed algorithm for maximal independent set selection.  In: Proceedings of the 2013 ACM symposium on Principles of distributed computing. ACM, Association for Computing Machinery, 2013 pp. 147–156.
  * [16] Nakano K.  Optimal initializing algorithms for a reconfigurable mesh.  _Journal of Parallel and Distributed Computing_ , 1995.  24(2):218–223.
  * [17] Hayashi T, Nakano K, Olariu S.  Randomized initialization protocols for packet radio networks.  In: IPPS. IEEE, 1999 p. 544.
  * [18] Bordim JL, Cui J, Hayashi T, Nakano K, Olariu S.  Energy-efficient initialization protocols for ad-hoc radio networks.  In: International Symposium on Algorithms and Computation. Springer, 1999 pp. 215–224.
  * [19] Chlebus BS, De Marco G, Talo M.  Naming a channel with beeps.  _Fundamenta Informaticae_ , 2017.  153(3):199–219.
  * [20] Chang YJ, Dani V, Hayes TP, He Q, Li W, Pettie S.  The energy complexity of broadcast.  In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. 2018 pp. 95–104.
  * [21] Chang YJ, Kopelowitz T, Pettie S, Wang R, Zhan W.  Exponential separations in the energy complexity of leader election.  _ACM Transactions on Algorithms (TALG)_ , 2019.  15(4):1–31.
  * [22] Sivalingam KM, Srivastava MB, Agrawal P.  Low power link and access protocols for wireless multimedia networks.  In: 1997 IEEE 47th Vehicular Technology Conference. Technology in Motion, volume 3. IEEE, 1997 pp. 1331–1335.
  * [23] Nakano K, Olariu S.  Energy-efficient initialization protocols for single-hop radio networks with no collision detection.  _IEEE Transactions on Parallel and Distributed Systems_ , 2000.  11(8):851–863.
  * [24] Casteigts A, Métivier Y, Robson JM, Zemmari A.  Counting in one-hop beeping networks.  _Theoretical Computer Science_ , 2019.  780:20–28.
  * [25] Brandes P, Kardas M, Klonowski M, Pająk D, Wattenhofer R.  Approximating the size of a radio network in beeping model.  In: International Colloquium on Structural Information and Communication Complexity. Springer, 2016 pp. 358–373.
  * [26] Perkins CE, et al.  Ad hoc networking, volume 1.  Addison-wesley Reading, 2001.
  * [27] Czumaj A, Davies P.  Communicating with beeps.  _Journal of Parallel and Distributed Computing_ , 2019.  130:98–109.
  * [28] Ravelomanana V.  Randomized initialization of a wireless multihop network.  In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences. IEEE, 2005 pp. 324b–324b.
  * [29] Jacquet P, Milioris D, Mühlethaler P.  A novel energy-efficient broadcast leader election.  In: 2013 IEEE 21st International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems. IEEE, 2013 pp. 495–504.
  * [30] Fuchs M, Hwang HK.  Dependence between path-length and size in random digital trees.  _Journal of Applied Probability_ , 2017.  54(4):1125–1143.
  * [31] Yao AC.  Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract).  In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977. 1977 pp. 222–227.