# Battery-Free Sensor Array for
Wireless Multi-Depth In-Situ Sensing
††thanks: This work was supported in part by NSF under grant no. CNS-2341846
and CNS-2310856.

Hongzhi Guo and Adam Kamrath  School of Computing, University of Nebraska-
Lincoln, Lincoln, NE, USA
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Underground in-situ sensing plays a vital role in precision agriculture and
infrastructure monitoring. While existing sensing systems utilize wires to
connect an array of sensors at various depths for spatial-temporal data
collection, wireless underground sensor networks offer a cable-free
alternative. However, these wireless sensors are typically battery-powered,
necessitating periodic recharging or replacement. This paper proposes a
battery-free sensor array which can be used for wireless multi-depth in-situ
sensing. Utilizing Near Field Communication (NFC)—which can penetrate soil
with negligible signal power loss—this sensor array can form a virtual
magnetic waveguide, achieving long communication ranges. An analytical model
has been developed to offer insights and determine optimal design parameters.
Moreover, a prototype, constructed using off-the-shelf NFC sensors, was tested
to validate the proposed concept. While this system is primarily designed for
underground applications, it holds potential for other multi-depth in-situ
sensing scenarios, including underwater environments.

###### Index Terms:

Battery-free sensors, in-situ sensing, magnetic induction, near field
communication.

##  I Introduction

Multi-depth in-situ sensing systems are extensively used in agriculture and
water management [1, 2]. In precision agriculture, soil sensors are placed at
various depths to comprehensively monitor attributes like salinity, moisture,
and nitrogen density and distribution. This sensing data aids in the
intelligent management of irrigation and nitrogen usage. Unlike single
sensors, multi-depth sensory arrays gather rich information, providing a
deeper understanding of a crop’s root nutrition.

Current multi-depth sensors are typically connected by cables, as shown in
Fig. 1(a). For easier deployment, these sensors can be housed in tubes. Often,
a solar panel is positioned on the ground as the primary energy source.
Additionally, the sensing system includes a wireless module on the surface
that employs cellular communication or long-range Internet of Things (IoT)
technologies to transmit the collected data. However, this system presents
several drawbacks that have driven the search for alternative solutions.
First, this type of sensing system is intrusive, which can alter the original
distribution of the sensing parameters, leading to biased measurements.
Second, the system’s cost, often exceeding $1,000, restricts widespread
deployment. The system also necessitates specialized protection for the
sensors, cables, and above-ground equipment, especially in extreme weather
conditions. Last, the current systems often experience data loss due to
unreliable solar power sources or wireless channels.

In-situ wireless sensors eliminate the need for cable connections, as shown in
Fig. 1(b). They are notably smaller and less intrusive compared to their wired
counterparts. Rather than relying on solar panels for power, these sensors
utilize batteries. While battery-powered wireless sensors have notably
simplified deployment and reduced maintenance costs, they also present both
environmental and technical challenges. First, to prolong battery life, the
sensing system often operates in a low-power mode. This might entail reducing
transmission power, increasing the time between sensing periods, and adopting
energy-efficient cross-layer protocols. However, such measures can adversely
affect both communication and sensing performance. Second, replacing batteries
becomes a significant challenge, especially when sensors are positioned in
inaccessible or unseen environments. Although wireless charging presents a
possible solution, its efficiency diminishes considerably when sensors are
buried deeply. Last, when the sensors reach the end of their operational life,
they must be retrieved to ensure their batteries are disposed of responsibly.
Such challenges are non-existent in terrestrial environments where locating
and replacing or recharging batteries can be accomplished with relative ease.

Battery-Free Wireless (BFW) sensors can harvest energy from electromagnetic
fields. Once powered up, they can perform sensing tasks and transmit data by
modulating signals over existing electromagnetic fields. Depending on the
source of the electromagnetic fields, BFW sensors can either utilize ambient
wireless signals or rely on dedicated signal generators. Due to their
diminutive size, BFW sensors are non-intrusive; their presence in the soil
does not significantly alter soil nutrition and water distribution. Ambient
backscatter communication leverages legacy wireless sources such as LTE, Wi-
Fi, and LoRa. While ambient backscatter communication is prevalent in
terrestrial environments, legacy wireless signals struggle to penetrate soil
or water, rendering them unsuitable for BFW sensors. Therefore, employing a
dedicated wireless signal generator (often referred to as a ”reader”) becomes
preferable, as it can provide robust transmission power. Current BFW sensors
paired with a dedicated reader typically operate based on UHF (300 MHz to 3
GHz) RFID or HF (3 MHz to 30 MHz) RFID/NFC[3]. Given that soil possesses a
certain water content and electrical conductivity, UHF signals face challenges
penetrating deep soil — for instance, the skin depth of soil at UHF
frequencies is approximately 20 cm [4]. For deeper in-situ BFW sensing, HF
RFID/NFC can be used due to their long wavelength.

In this paper, we use HF NFC-based BFW sensors for wireless multi-depth in-
situ sensing. An array of these sensors is evenly spaced and embedded within
the soil, as shown in Fig. 1(c). Above ground, a mobile reader initiates
communication with the buried BFW sensors. These sensors harvest energy from
the magnetic fields generated by the reader, then proceed to sense and respond
in accordance with NFC anti-collision protocols.

Deploying BFW sensors presents unique challenges, distinguishing them from
their wired counterparts. First, many NFC modules possess a limited
communication range, often less than 10 cm. Unlike battery-powered sensors
that are inherently powered, battery-free sensors rely on downlink signals
(from reader to sensor) for activation. Once powered, they can then remodulate
these signals, transmitting them through uplink channels (from sensor to
reader) [5]. However, multi-depth in-situ sensing requires considerably longer
communication ranges, spanning from 0.5 m to several meters, depending on the
specific application. Thus, it’s imperative to extend the communication range
of NFC BFW sensors to align with these demands. Second, the HF band signals
have a long wavelength and the coupling between sensor antennas must be
carefully considered to avoid negative impacts on communication performance.
Last, a near-far issue arises: sensors located closer to the reader receive
significantly higher voltages than those situated further away. This poses a
risk, as BFW sensors are low-power devices and excessive voltages could cause
damage.

(a) Wired sensor array using cables.

(b) Battery-powered wireless sensor array.

(c) Battery-free wireless sensor array.

Figure 1: Multi-depth in-situ sensory array.

To address theses challenges, this paper adopt the concept of magnetic
induction waveguide [6, 7]. In this approach, sensor coil antennas are spaced
at regular intervals, forming a virtual link via magnetic coupling. While
previous research has indicated that the magnetic induction waveguide can
notably enhance communication range [6, 7], these studies predominantly focus
on battery-powered sensors, leaving battery-free sensors unexplored. To our
knowledge, this is the the first paper using magnetic induction waveguide
concept for BFW sensors. The main contribution of this paper is two-fold.

  * •

We introduce an analytical communication and networking model for BFW sensors.
Drawing from this, we offer insights into the optimal configurations and
strategic placements of BFW sensors aimed at achieving a long communication
range.

  * •

We construct a testbed using readily available BFW sensors, testing our
proposed approach both empirically and numerically. A comprehensive analysis
of the empirical results, rooted in our analytical model, is also provided.

The rest of this paper is organized as follows. In Section II, we provide
analytical communication models for a single BFW sensor and multiple BFW
sensors and show the major difference. Then, we optimize the analytical model
and obtain the optimal interval between sensors. The development testbed and
numerical analysis are presented in Section III. Finally, this paper is
concluded in Section IV.

##  II Communication System Modeling and Optimization

NFC operates using coils that are coupled by near-field magnetic fields. While
the coil antenna does produce electromagnetic waves, in the near field (where
the distance from the antenna is much smaller than one wavelength) the
electric and magnetic fields are weakly coupled. Unlike electromagnetic waves,
near-field magnetic fields can penetrate non-magnetic materials with minimal
scattering, reflection, and absorption losses. Consequently, NFC offers a
reliable wireless channel, finding applications in diverse non-terrestrial
environments [8, 3, 9]. Communication and networking of battery-powered
sensors using magnetic induction have been a subject of extensive research [6,
10]. These can achieve extended communication ranges, exceeding 10 m, through
specialized coil designs and circuit resonance. In contrast, BFW sensors have
predominantly been employed for point-to-point communications rather than
networked setups, owing to their inherently shorter communication ranges.

NFC-based BFW sensors predominantly employ the ISO/IEC 14443 and ISO/IEC 15693
protocols [3]. Due to their reduced data rate, the ISO/IEC 15693 sensors can
achieve a longer range compared to the ISO/IEC 14443 sensors. Ideally, with
sufficiently large coil antennas, the ISO/IEC 15693 can support a
communication range of up to 1.5 m. In this study, our BFW sensor array
utilizes the ISO/IEC 15693 protocol. An illustration of the communication
signal is provided in Fig. 2. By positioning a USRP N210 equipped with an NFC
antenna near a sensor, we captured the communication signals exchanged between
the reader and the sensor. Following the reader’s request transmission, it
continues to emit continuous waves. Upon receipt of this request, the sensor
selects an appropriate time slot for its response. As evident from the data,
the signal from the sensor is considerably weaker than that from the reader.

Figure 2: Illustration of ISO/IEC 15693 reader and sensor signals.

###  II-A Joint Antenna and Channel Model

Magnetic coupling between sensor coils can profoundly influence both the
communication range and achievable data rates. Consequently, there’s a need to
develop a joint model for the antenna and channel. As depicted in Fig. 3, we
utilize an equivalent parallel circuit model for both the reader and the
sensors. This parallel circuit design is particularly effective at amplifying
the induced voltage in the sensor circuits, ensuring it meets the cold start
voltage requirements. This makes it a popular choice in NFC circuit design. In
this paper, the reader’s circuit elements and parameters are denoted using
subscript 1, while the sensors’ are denoted using subscript 2 to $n$ based on
sensors’ depth. The $n$th sensor has the largest depth. The self-inductance of
coil $p$ is $L_{p}=\mu\pi a_{p}n_{p}^{2}/2$, where $\mu$ is the permittivity,
$a_{p}$ is the $p$th sensor’s coil radius, and $n_{p}$ is the $p$th sensor’s
coil number of turns [6]. The capacitor $C_{p}$ is used to tune the circuit to
resonant, and $C_{p}=1/(\omega^{2}L_{p})$, where $\omega=2\pi f_{c}$ and
$f_{c}$ is the signal carrier frequency, i.e., 13.56 MHz. The resistor $R_{p}$
is used to control the coil’s quality factor and bandwidth. If the quality
factor $Q_{p}$, then $R_{p}=\omega L_{p}Q_{p}$.

NFC coils use magnetic coupling to transmit signals and the wireless channel
is determined by the mutual inductance. The mutual inductance between the
$i$th and $j$th sensor coils is [6]

$\displaystyle M_{ij}=\frac{\mu\pi n_{i}n_{j}a_{i}^{2}a_{j}^{2}}{2d^{3}},$ (1)

where $d$ is the distance between the coils. We can neglect the dynamics of
soil conductivity and permittivity provided that $d$ is much smaller than the
wavelength. The above equation can not provide accurate approximation when $d$
is extremely small. In this paper, we use the following mutual inductance
equation when $d$ is small [11],

$\displaystyle\begin{array}[]{r}M_{ij}=\mu_{0}\pi
n_{i}n_{j}a_{i}a_{j}\int_{0}^{\infty}J_{0}(sp)J_{1}\left(sa_{i}\right)J_{1}\left(sa_{j}\right)\\\
\exp\left(-s\left|z_{2}-z_{1}\right|\right)ds.\end{array}$ (4)

where $p$ is the perpendicular distance separating the coil axes,
$|z_{2}-z_{1}|$ is the vertical distance separating the coil planes,
$J_{n}(\cdot)$ is the Bessel Function of the $n^{th}$ order, and $s$ is the
variable of integration. This model can also capture the horizontal deviation
of sensors. Note that, although Equ. (4) is accurate and generic, it is
challenging to obtain insightful results using it. In the following, we will
develop analytical models using Equ. (1) and verify the results in Section III
using Equ. (4).

(a) Single sensor.

(b) Multiple sensors.

Figure 3: Illustration of the equivalent circuit for single sensor and
multiple sensors.

###  II-B Single Sensor

In existing NFC-based battery-free sensing systems, the reader communicates
with each individual sensor. When there is one sensor, the communication range
is determined by both the uplink and downlink channel. First, the downlink
channel must induce sufficient voltage in the sensor’s coil to power up the
sensor. Second, the uplink channel must provide sufficient signal strength for
the reader to demodulate the load modulated signals.

Given the transmission power $P_{t}$, the voltage across the reader’s coil is
$v_{1}=\sqrt{2\omega P_{t}L_{1}Q_{1}}$. The induced voltage across the sensor
load is

$\displaystyle v_{2}=v_{R_{2}||C_{2}}=\frac{-j\omega L_{2}R_{2}}{R_{2}-j\omega
L_{2}}\cdot i_{2}$ (5)

where $i_{2}$ is the current in the sensor coil. The current $i_{2}$ can be
written as

$\displaystyle i_{2}=\frac{-j\omega M_{12}i_{1}}{-\frac{j\omega
L_{2}Q_{2}}{Q_{2}-j}+j\omega L_{2}}=\frac{M_{12}(Q_{2}-j)i_{1}}{jL_{2}}.$ (6)

According to Kirchhoff’s Voltage Law, the current in reader’s coil satisfy the
following condition

$\displaystyle j\omega L_{1}i_{1}+j\omega M_{12}i_{2}=v_{1}.$ (7)

By substituting $i_{2}$ in Equ. (7), we can obtain $i_{1}$, which is then used
to obtain $i_{2}$ and $v_{2}$. Since the sensor can only be power up when
$v_{2}$ is larger than a threshold voltage, we pay attention to the amplitude
of $v_{2}$, which is

$\displaystyle|v_{2}|=\left|\frac{M_{12}Q_{2}L_{2}v_{1}}{jL_{1}L_{2}+M_{12}^{2}(Q_{2}-j)}\right|$
(8)

By expanding the expressions of $L_{i}$ and $M_{12}$, we can obtain

$\displaystyle|v_{2}|=\left|\frac{n_{2}a_{1}a_{2}^{2}Q_{2}\sqrt{\omega\mu\pi
a_{1}P_{t}Q_{1}}}{jd^{3}+\frac{a_{1}^{3}a_{2}^{3}(Q_{2}-j)}{d^{3}}}\right|$
(9)

As we can see from the above equation, when $d$ is small increasing coil radii
cannot effectively increase $|v_{2}|$ due to the second term in the
denominator, while when $d$ is large, we can increase reader and sensor’s coil
radii, transmission power, quality factors, and sensor coil’s number of turns
to meet the threshold voltage. Since we are interested in the maximum range,
the second term in the denominator can be neglected. As a result, the maximum
downlink range is

$\displaystyle
d_{max}^{dl}=\left(\frac{n_{2}a_{1}a_{2}^{2}Q_{2}\sqrt{\omega\mu\pi
a_{1}P_{t}Q_{1}}}{v_{th}}\right)^{\frac{1}{3}},$ (10)

where $v_{th}$ is the threshold voltage.

The reader detects load-modulated signals through the reflected impedance from
the sensor coil. As shown in Equ. (7), the impact of the sensor coil can be
written as

$\displaystyle\alpha_{s}=\left|\frac{\omega M_{12}i_{2}}{\omega
L_{1}i_{1}}\right|=\frac{a_{1}^{3}a_{2}^{3}\sqrt{Q_{2}^{2}+1}}{d^{6}}.$ (11)

Note that, there is a self-interference issue in the reader’s coil. In Equ.
(7), the first term on the left-hand side is for transmitting continuous waves
to power sensors, while the second term reflects the signal modulated by the
sensor. Both are in the same reader’s coil. Use a strong transmission power
can reduce the impact of noise and increase $d_{max}^{dl}$, but it cannot
change $\alpha_{s}$. Given a threshold ratio $\alpha_{t}$, the maximum uplink
range is

$\displaystyle
d_{max}^{ul}=\left(\frac{a_{1}^{3}a_{2}^{3}\sqrt{Q_{2}^{2}+1}}{\alpha_{t}}\right)^{1/6}$
(12)

As a result, the maximum signal sensor communication range is

$\displaystyle d_{max}=\min(d_{max}^{dl},d_{max}^{ul}).$ (13)

We will evaluate $d_{max}$ and compare it with the multi-sensor solution in
Section III.

###  II-C Multiple Sensors

When there are multiple sensors, they can mutually affect each other. The
impact can be positive or negative depending on sensor locations. Next, we
develop a generic analytical model to characterize the multi-sensor
interaction and obtain the optimal deployment policy. Considering the impact
of all sensor coils, the reader’s coil circuit satisfies,

$\displaystyle j\omega L_{1}i_{1}+\sum_{k=2}^{n}j\omega M_{1k}i_{k}=v_{1}.$
(14)

Similarly, the voltage and current in a coil $p$ ($p\in[2,n]$) can be written
as

$\displaystyle\sum_{k=1}^{p-1}j\omega
M_{kp}i_{k}+Z_{p}i_{p}+\sum_{k=p+1}^{n}j\omega M_{kp}i_{k}=0,$ (15)

where $Z_{p}$ is the impedance of the coil $p$.

####  II-C1 Approximated Analytical Model

To obtain the induced voltage in each sensor coil, we can rewrite the above
equations in matrix format, as used in [10]. However, the challenge is not to
obtain the voltage in sensor coils, but to optimize sensors’ location to
maximize the communication range. In this paper, we decompose this complex
problem using the following two steps.

First, the mutual inductance between nonadjacent coils is small. In the
sensory array, only the top and the bottom (if any) sensor coils can strongly
affect the sensor coil in the middle. As a result, Equ. (15) can be rewritten
as

$\displaystyle j\omega M_{1p}i_{1}+j\omega
M_{(p-1)p}i_{p-1}+Z_{p}i_{p}+j\omega M_{p(p+1)}i_{p+1}\approx 0.$ (16)

In Equ. (16), we keep the induced voltage by the reader coil. This is because
in NFC systems, the reader coil usually has a larger size than sensor coils
and $M_{1p}$ can be relatively large.

Second, the sensors form a chain to relay signals and sensor coil currents on
this chain should decrease at a constant rate, i.e, $i_{p-1}\beta=i_{p}$ for
$p\in[2,n-1]$, where $|\beta|\leq 1$. Then, we search for a sensor deployment
solution that can maximize $\beta$ given a minimum interval. Since the
considered environment is homogeneous and sensors are placed with a constant
interval, the optimal mutual inductance between two sensor coils should be
similar. As a result, Equ. (16) can be rewritten as

$\displaystyle\gamma j\omega Mi_{p-1}+j\omega
Mi_{p-1}+Z_{p}i_{p-1}\beta+j\omega Mi_{p-1}\beta^{2}=0,$ (17)

where we consider $j\omega M_{1p}i_{1}=\gamma j\omega Mi_{p-1}$. Then, we can
find $\beta$, which is

$\displaystyle\beta=\frac{-Z_{p}+\sqrt{Z_{p}^{2}+4\omega^{2}M^{2}(1+\gamma)}}{2j\omega
M}.$ (18)

Since the sensor coil coupling $\omega M$ is usually much smaller than
$Z_{p}$, we can obtain the following approximation using Taylor Series,

$\displaystyle\beta\approx\frac{\frac{1}{2}\frac{4\omega^{2}M^{2}(1+\gamma)}{Z_{p}^{2}}}{\frac{2j\omega
M}{Z_{p}}}=\frac{\omega M(1+\gamma)}{jZ_{p}}.$ (19)

Since $Z_{p}$ can be expressed as $-j\omega L_{p}Q_{p}/(Q_{p}-j)+j\omega
L_{p}$, $\beta$ can be simplified to

$\displaystyle|\beta|\approx\frac{a_{p}^{3}}{d^{3}}(1+\gamma)\sqrt{Q_{p}^{2}+1}.$
(20)

Here, we implicitly assume that all the sensor coils have the same number of
turns and the same coil radius.

Next, we consider the reader’s impact can be neglected, i.e., $\gamma=0$, and
the coil’s quality factor is much larger than 1, i.e., $Q_{p}>>1$. Given
$\beta$, the distance between two sensors is

$\displaystyle d=\sqrt[3]{\frac{Q_{p}}{|\beta|}}a_{p}.$ (21)

As we can see from the above equation, we can increase sensor coil’s quality
factor and size to extend the range. Also, using a small $\beta$ can also
increase the range between two sensors, however, that decreases the power
delivered to the deeper sensor which can result in a short overall
communication range.

Since the sensor currents are proportional, we can find $i_{2}$ then based on
$\beta$, we can obtain the rest of the currents. In Equ. (14), the summation
can only include sensor 2 and neglect other sensor coils due to their weak
currents and small mutual inductance. Then, by using Equ. (14) and Equ. (15)
(only consider adjacent mutual inductance), we can obtain

$\displaystyle i_{2}=\frac{-M_{12}(Q_{2}-j)v_{1}}{-j\omega
M_{12}^{2}(Q_{2}-j)+\omega L_{1}L_{2}+j\omega M_{23}L_{1}\beta(Q_{2}-j)}.$
(22)

We can approximately obtain the current in each sensor coil which is
$i_{p}\approx\beta^{p-2}i_{2}$. The voltage in each sensor is $|v_{p}|=|\omega
M_{(p-1)p}i_{p-1}Q_{p}|$. Note that, we cannot get a simple equation for
$d_{max}^{dl}$ when there are multiple sensors. The system can operate only if
the sensor voltage is higher than $v_{th}$.

From Equ. (22) we can see that if sensor 2 and sensor 3 are extremely close,
i.e., $M_{23}$ is large, $i_{2}$ can be small. As a result, sensor 2 cannot
receive enough voltage to power up. This shows that when there are multiple
sensors, their distance need to be carefully planned to avoid negative
effects.

The uplink for sensor $k$ in multi-sensor scenario can be evaluated using the
$j\omega M_{1k}i_{k}$, which is

$\displaystyle\alpha_{m}^{p}=\left|\frac{\omega M_{1k}i_{k}}{\omega
L_{1}i_{1}+\sum_{p,p\neq k}^{n}\omega M_{1p}i_{p}}\right|.$ (23)

The reader can demodulate sensor data only if $\alpha_{m}^{p}>\alpha_{t}$.

####  II-C2 Optimal Multi-Depth Sensor Deployment

In the previous part, we present the relation between distance and current
decay rate. In multi-depth in-situ sensing, we are interested in several
depths with the same mutual interval, e.g., the depth of sensor $p$ is
$l_{p}=(p-1)l_{0}$, where $p\in[2,n]$ is the index of the sensor and $l_{0}$
is the interval. Given the required depths, we need to find the optimal or
feasible combinations of sensor coil radius $a_{p}$, quality factor $Q_{p}$,
and reader transmission power $P_{t}$ to achieve the range.

As we can see from Equ. (20) to Equ. (22), the coil radius and quality factor
can be considered jointly and it is challenging to separate them. We use a
search-based solution. We consider $a_{p}=a_{0}$ and $Q_{p}=Q_{0}$ which are
standard values used by NFC sensors, e.g., $a_{0}=2.5$ cm and $Q_{p}=8$. The
transmission power is $P_{t}=0.01$ W. We solve equations (14) and (15) and
check if the voltages can meet the threshold voltage requirement. If not, we
update $Q_{p}=Q_{p}+\Delta Q$, $P_{t}=P_{t}+\Delta P_{t}$, and
$a_{p}=a_{p}+\Delta a$ in sequence, and then check the voltages iteratively.
This process will continue until we obtain the feasible $a_{p}$, $Q_{p}$, and
$P_{t}$. Also, we set the maximum radius $a_{p}^{max}$, maximum quality factor
$Q_{p}^{max}$, and maximum transmission power $P_{t}^{max}$. When all of them
reach the maximum values but we cannot obtain a feasible solution, the
requirement is beyond the capability of the system.

##  III Implementation and Simulation

In this section, we show an implementation using off-the-shelf NFC sensors and
understand the results using the developed analytical models. Also, we provide
more simulations to show the achievable communication range of the proposed
system.

###  III-A Implementation using Off-The-Shelf Sensors

In our implementation, we consider the following off-the-shelf reader and
sensors.

  * •

NFC battery-free sensor. We use the MAX66242EVKIT sensor board from Analog
Devices. The sensor board has a temperature sensor and supports ISO/IEC 15693
protocol.

  * •

Long-range reader. We use the FEIG ID MR102 reader with ANT340/240 pad antenna
which supports ISO/IEC 15693 protocol. The reading range is around 35 cm.

We measured the response signals from two sensors, as shown in Fig. 4. In
order to obtain a clear signal, we place the two sensors close to the reader’s
antenna. As we can see, the sensors respond in different time slots to avoid
collisions. We test the multi-depth sensor array in air and soil to understand
the impact of soil. The measure setup is shown in Fig. 5. We measure the
maximum communication range (where the reader can read a sensor’s ID) in the
air for one sensor and two sensors. Figure 5(a) shows the two-sensor setup.
Then, we place a sensor in a soil box with soil depth of around 15 cm and vary
the height of the reader’s antenna, as shown in Fig. 5(b).

Figure 4: Signals with two sensors’ responses.

(a) Two sensors in the air.

(b) One sensor in a soil box.

Figure 5: Measurement setup.

Figure 6: Induced voltages in a two-sensor case.

Figure 7: Downlink communication range between a reader and a sensor.

Figure 8: Impact of quality factor on optimal interval between two sensors.

As shown in Table I, for one sensor, the communication ranges in the air and
in the soil are similar which shows that the soil does not have significant
impact on the sensor coil and signal propagation. In the air, we use two
sensors and form an array and the overall range can be extended. However, it
only works when sensor 1 and sensor 2 are placed at specific locations. This
is mainly due to the low quality factor of sensor coils and their small sizes.
Note that, when sensor 1 is close to the reader, the simulation results show
that the sensor 2 can be powered up. However, in experiment, we cannot observe
this phenomenon. The sensor 1 cannot support high voltages (e.g., higher than
20 V). It is impractical to use this region. On the contrary, when sensor 1 is
close to sensor 2 and the induced voltage in sensor 2 is slightly higher than
the threshold voltage. Meanwhile, sensor 1’s voltage is not high. As sensor 1
moves further closer, the coupling between two sensor coils becomes so strong
that neither of them can communicate. In Fig. 8, we choose parameters to
approximate the experiment measures and show this phenomenon using the
analytical model. As we can see in the figure, theoretically, there are two
regions that sensor 2 can be powered up. However, the region that is close to
the reader induces strong voltages in sensor 1. Sensor 1’s circuit has
protection mechanism which does not allow such strong voltages. Therefore,
only the region close to sensor 2 can be measured in practice.

As a result, there is a “near-far” problem here. When we try to power up a far
sensor using high transmission power or high-quality-factor transmission
coils, the near sensors will be exposed to high voltages which can destroy
their circuits. However, the near sensors have to be alive to relay signals
for far sensors. This issue can be addressed by using a transformer to
separate the sensor coil and sensor circuits. The transformer needs to be
specifically designed for each sensor with different depths. Due to the
limitation of space, we do not consider transformer design in this paper.

TABLE I: Range Measurement. | Air (1 sensor) | Air ( 2 sensors) | Soil (1 sensor)
---|---|---|---
Sensor 1 | 29.5 cm | 24 cm | 27.5 cm
Sensor 2 | — | 31.5 cm | —

###  III-B Numerical Simulation

In the following, we evaluate the impact of various sensor coil configurations
on the communication range. First, we consider standard NFC reader and sensor
coils. The reader coil radius is 4 cm and sensor coil radius is 2.5 cm. Both
the reader and sensor coil have 5 turns. The reader coil quality factor is 8
and the sensor coil quality factor is varied from 8 to 32. The transmission
power is 0.01 W.

As shown in Fig. 8, the downlink communication range is determined by the
power-up threshold voltage $v_{th}$. As the sensor coil quality factor
increases from 8 to 32, the range is increased from 6 cm to around 11 cm. Due
to the short communication range, we used Equ. (4) to simulate (sim in Fig. 8)
the induced voltage, and the analytical model (ana in Fig. 8) uses Equ. (9).
The results are consistent with existing NFC sensors. For example, the
measured maximum communication range between MAX66300-24XEVKIT and
MAX66242EVKIT is 7 cm. Although increasing the quality factor can extend the
range, using existing NFC sensors cannot meet most long-range multi-depth in-
situ sensing requirements.

In Equ. (21), we find that the optimal interval is proportional to
$a_{p}\sqrt[3]{Q_{p}}$. In Fig. 8, we show the induced voltage in the deepest
sensor of a 10-sensor array. Their interval is scaled by
$a_{p}\sqrt[3]{Q_{p}}$ and shown in the x-axis. We consider four sensor coil
quality factors. Since the interval is scaled by $a_{p}\sqrt[3]{Q_{p}}$, the
induced voltage in sensor coils should be similar. As we can see in Fig. 8, as
the interval increases sensor voltages converges to the same value. When the
interval is small, the reader has stronger impact on each sensor coil. As a
result, the assumption of neglecting reader impact to derive Equ. (21) is not
valid when the distance from the reader is short.

Figure 9: Required transmission power to achieve 0.6 m range using sensor
arrays with various sensor coil quality factor.

In Fig. 9, we set the required range as 0.8 m and set the interval as
$0.8a_{p}\sqrt[3]{Q_{p}}$. The interval and the overall range will determine
the number of required sensors in the sensor array. The transmission power is
varied from 0.01 W to 1 W. As we can see in Fig. 9, the high quality factor
can effectively reduce the use transmission power by achieving the threshold
voltage using a lower transmission power.

We also evaluated the optimal multi-depth sensor deployment. Given a
requirement sensing depth of 1.2 m with 0.15 m interval, we use 8 sensors. By
iterating the quality factor, transmission power, and sensor coil radius as
discussed in Section II-C2, we find that we can successfully power up all the
sensors using $Q_{p}=32$, $P_{t}=1$ W, and $a_{p}=$0.05 m. To evaluate the
uplink channel, we use the derived optimal multi-depth sensor array and obtain
the $\alpha_{s}$ for each sensor. The results are compared with a single
sensor at various depths as the sensor array. As shown in Fig. 10, the single
sensor can only receive enough voltage at the first three locations, while the
multi-depth sensor array can receive enough voltage at 1.2 m away.
$\alpha_{s}$ is decreasing as the distance increases.

Figure 10: $\alpha_{s}$ of signal sensor at 8 different locations and
$\alpha_{s}$ for 8 sensors in a multi-depth sensor array.

##  IV Conclusion

In this paper, we propose a battery-free multi-depth sensing system, where
sensors use NFC modules for data communication. The sensor coils form a
virtual magnetic induction waveguide to achieve a longer communication range
than each individual sensor. We develop an analytical model to identify key
parameters and design the optimal sensor coil parameters. A proof-of-concept
testbed is developed and numerical simulations are used to comprehensively
evaluate the performance.

## References

  * [1] S. F. Pichorim, N. J. Gomes, and J. C. Batchelor, “Two solutions of soil moisture sensing with rfid for landslide monitoring,” _Sensors_ , vol. 18, no. 2, p. 452, 2018.
  * [2] M. Boada, A. Lazaro, R. Villarino, and D. Girbau, “Battery-less soil moisture measurement system based on a nfc device with energy harvesting capability,” _IEEE Sensors Journal_ , vol. 18, no. 13, pp. 5541–5549, 2018.
  * [3] H. Guo and A. A. Ofori, “The internet of things in extreme environments using low-power long-range near field communication,” _IEEE Internet of Things Magazine_ , vol. 4, no. 1, pp. 34–38, 2021.
  * [4] D. A. Ellerbruch, “Electromagnetic attenuation properties of clay and gravel soils,” _NTIS, US Department of Commerce_ , pp. 74–381, 1974.
  * [5] A. A. Ofori and H. Guo, “Magnetic blind beamforming for battery-free wireless sensor networks,” _IEEE Transactions on Green Communications and Networking_ , vol. 6, no. 3, pp. 1819–1832, 2022.
  * [6] Z. Sun and I. F. Akyildiz, “Magnetic induction communications for wireless underground sensor networks,” _IEEE transactions on antennas and propagation_ , vol. 58, no. 7, pp. 2426–2435, 2010.
  * [7] H. Guo, Z. Sun, J. Sun, and N. M. Litchinitser, “M2I: Channel Modeling for Metamaterial-Enhanced Magnetic Induction Communications,” _IEEE Transactions on Antennas and Propagation_ , vol. 63, no. 11, pp. 5072–5087, 2015\.
  * [8] R. Zhao, P. Wang, Y. Ma, P. Zhang, H. H. Liu, X. Lin, X. Zhang, C. Xu, and M. Zhang, “Nfc+ breaking nfc networking limits through resonance engineering,” in _Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication_ , 2020, pp. 694–707.
  * [9] H. Guo, Z. Sun, and P. Wang, “Joint design of communication, wireless energy transfer, and control for swarm autonomous underwater vehicles,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 2, pp. 1821–1835, 2021.
  * [10] S. Kisseleff, I. F. Akyildiz, and W. H. Gerstacker, “Magnetic induction-based simultaneous wireless information and power transfer for single information and multiple power receivers,” _IEEE Transactions on Communications_ , vol. 65, no. 3, pp. 1396–1410, 2016.
  * [11] J. T. Conway, “Inductance calculations for noncoaxial coils using bessel functions,” _IEEE Transactions on Magnetics_ , vol. 43, no. 3, pp. 1023–1034, 2007.


# A min-max regret approach for the Steiner Tree Problem with Interval Costs

###### Abstract

Let $G=(V,E)$ be a connected graph, where $V$ and $E$ represent, respectively,
the node-set and the edge-set. Besides, let $Q\subseteq V$ be a set of
terminal nodes, and $r\in Q$ be the root node of the graph. Given a weight
$c_{ij}\in\mathbb{N}$ associated to each edge $(i,j)\in E$, the Steiner Tree
Problem in graphs (STP) consists in finding a minimum-weight subgraph of $G$
that spans all nodes in $Q$. In this paper, we consider the Min-max Regret
Steiner Tree Problem with Interval Costs (MMR-STP), a robust variant of STP.
In this variant, the weight of the edges are not known in advance, but are
assumed to vary in the interval $[l_{ij},u_{ij}]$. We develop an ILP
formulation, an exact algorithm, and three heuristics for this problem.
Computational experiments, performed on generalizations of the classical STP
instances, evaluate the efficiency and the limits of the proposed methods.

Iago A. Carvalho
Instituto de Computação, Universidade Estadual de Campinas
Av. Albert Einstein 1251, Campinas, SP, 13083-852, Brazil
<EMAIL_ADDRESS>

Amadeu A. Coco
Departamento de Computação, Centro Federal de Educação Tecnológica de Minas
Gerais
Av. Amazonas 7675, Belo Horizonte, MG, 30510-000, Brazil
<EMAIL_ADDRESS>

Thiago F. Noronha
Departamento de Ciências da Computação, Universidade Federal de Minas Gerais
Av. Antônio Carlos 6627, Belo Horizonte, MG, 31270-901, Brazil
<EMAIL_ADDRESS>

Christophe Duhamel
LITIS, Université Le Havre Normandie
25 Rue Philippe Lebon, 76600 Le Havre, France
<EMAIL_ADDRESS>

KEYWORDS. Steiner tree problem. Min-max regret. Interval uncertainty.

Combinatorial optimization, Mathematical programming

##  1 Introduction

Let $G=(V,E)$ be a connected graph, where $V$ is the set of nodes and $E$ is
the set of edges, where each edge $(i,j)\in E$ is associated with a cost
$c_{ij}\in\mathbb{N}_{+}$. Given a set $Q\subset V$ of terminal nodes, a
Steiner tree is defined as a tree in $G$ that spans all nodes in $Q$ and may
contain additional nodes from $V\setminus Q$. The Steiner Tree Problem in
graphs (STP) [Dreyfus e Wagner, 1971] consists in finding a minimum cost
Steiner tree of $G$.

STP is a well known NP-Hard problem [Karp, 1972]. This problem finds practical
applications in areas such as telecommunication networks design, computational
biology, VLSI design, among others [Prömel e Steger, 2012]. In most of these
applications, the cost associated with each edge is not precisely known. In
this paper, we investigate how Robust Optimization (RO) [Kouvelis e Yu, 1997]
can be applied to this context.

RO is an approach to deal with uncertain parameters in decision making, where
the data variability is represented by deterministic values [Kasperski e
Zieliński, 2016; Kouvelis e Yu, 1997]. We focus on RO models where the
uncertain data is modelled by an interval of possible values. We refer to the
book by Kouvelis e Yu [1997] for other robust optimization models. In this
approach, any realization of a single value for each parameter is considered
as a scenario that can happen. The objective is to find a solution that is
efficient for all scenarios, usually referred to as a robust solution. The RO
criterion used in this work to classify a solution as robust or not is the
min-max regret. It was proposed by Wald [1939] in the context of game theory
and was adapted to RO by Kouvelis e Yu [1997].

In this paper, we introduce a variant of STP where the value of $c_{i}$ is
uncertain. However, it is assumed that this value is in the range
$[l_{ij},u_{ij}]$. This problem is refereed to as the Min-max Regret Steiner
Tree Problem with with Interval Costs (MMR-STP) and is defined as follows.

######  Definition 1.

A _scenario_ $S$ is an assignment of a single value
$c_{ij}^{S}\in[l_{ij},u_{ij}]$ for each edge $(i,j)\in E$.

It is worth noting that there are infinitely many scenarios, as $c_{ij}^{S}$
can assume any real value in $[l_{ij},u_{ij}]$. Let $\Gamma$ be the set of all
scenarios and $\Phi$ be the set of all Steiner trees in $G$.

######  Definition 2.

The _cost_ of a solution $x\in\Phi$ in a scenario $S\in\Gamma$ is given by

$F(x,S)=\sum_{(i,j)\in E}c_{ij}^{S}x_{ij}.$

######  Definition 3.

The cost of the optimal SPT solution $z^{S}$ in the scenario $S$ is denoted by

$F(z^{S},S)=\min\limits_{z\in\Phi}F(z,S)=\min\limits_{z\in\Phi}\sum_{(i,j)\in
E}c_{ij}^{S}z_{ij}.$

######  Definition 4 (Kouvelis e Yu [1997]).

The _regret_ of a solution $x\in\Phi$ in a scenario $S\in\Gamma$ is the
difference between the cost of $x$ in the scenario $S$ and the cost of $z^{S}$
in $S$.

######  Definition 5.

The _worst-case_ scenario scenario of $x$, i.e., the one where the regret of
$x$ is the maximum is denoted by

$S^{x}=\arg\max\limits_{S\in\Gamma}\left\\{F(x,S)-F(z^{S},S)\right\\}.$

######  Lemma 1 (Averbakh [2001]).

Although $|\Gamma|=\infty$, for any min-max regret optimization problem,
$S^{x}$ is such that $c^{S^{x}}_{ij}=u_{ij}$ if $x_{ij}=1$, and
$c^{S^{x}}_{ij}=l_{ij}$ otherwise. That is,
$c_{i}^{S^{x}}=l_{ij}+(u_{ij}-l_{ij})x_{ij}$, for all $x\in\Phi$ and $(i,j)\in
E$.

######  Definition 6.

The robust cost of a solution $x\in\Phi$ is defined as

$Z(x)=F(x,S^{x})-F(z^{S^{x}},S^{x}),$

i.e. $Z(x)$ is the maximum regret of $x$. It is worth noting that one has to
solve an STP in $S^{x}$ in order to compute $z^{S^{x}}$. That is, it is NP-
Hard to compute the robust cost of a single solution for MMR-STP.

######  Definition 7.

MMR-STP consists in finding the Steiner tree $x^{*}\in\Phi$ with the smallest
robust cost $Z(x^{*})$.

MMR-STP is clearly NP-Hard, as for $l_{ij}=u_{ij}=c_{ij}$ it reduces to SPT.
Therefore, in this paper we propose heuristics and exact algorithms for this
problem. We evaluate how good are the solutions provided by the state of the
art exact and heuristic algorithms designed for min-max regret optimization
problems these problems for the case of MMR-SPT.

The remainder of this work is organized as follows. Related works are
presented in Section 2. Section 3 shows the proposed ILP formulation for MMR-
STP. Then, an exact algorithm for MMR-STP are described in Section 4, while
three heuristics are proposed for this same problem in Section 5. Computation
experiments, which evaluates the proposed exact and heuristic algorithms, are
reported in Section 6. Finally, concluding remarks are drawn in the last
section.

##  2 Related work

The Steiner Tree Problem in graphs was proposed in Dreyfus e Wagner [1971],
and was proven NP-Hard in Karp [1972]. Several mathematical formulations
[Chopra e Rao, 1994; Goemans e Myung, 1993; Polzin e Daneshmand, 2001], as
well as exact algorithms [Lucena e Beasley, 1998], and heuristics [Duin e Voß,
1994, 1999], were proposed and evaluated for this problem. A comparison among
several mathematical formulations for STP was shown in Polzin e Daneshmand
[2001]. A compendium of STP formulations can be found in Goemans e Myung
[1993]. Furthermore, the state-of-the-art algorithms and other recent advances
regarding this problem can be found in Du et al. [2013]; Prömel e Steger
[2012].

Many robust counterparts of classical optimization problems have been studied
in the literature, such as the Robust Shortest Path Problem [Karaşan et al.,
2001; Catanzaro et al., 2011; Pérez-Galarce et al., 2018] and the Robust
Minimum Spanning Tree Problem [Montemanni, 2006; Godinho e Paquete, 2019], and
the Robust Shortest Path Tree Problem [Catanzaro et al., 2011; Carvalho et
al., 2016b, a, 2018]. These problems are NP-hard [Aissi et al., 2009], despite
the fact that their deterministic counterparts can be solved in polynomial
time. RO problems whose deterministic counterparts are already NP-hard have
also been studied, such as the Robust Restricted Shortest Path Problem
[Assunção et al., 2017], the Robust Traveling Salesman Problem [Montemanni et
al., 2007], and the Robust Set Covering Problem [Pereira e Averbakh, 2013;
Coco et al., 2015, 2016], and the Robust Knapsack Problem [Deineko e
Woeginger, 2010; Furini et al., 2015]. As is the case of MMR-STP, these
problems are particularly harder to solve than other NP-Hard problems, because
the complexity of computing the cost of a single solution is at least that of
solving the deterministic counterpart, which is itself NP-Hard.

Some works in the literature also consider robust variations of STP. A Robust
Prize-Collecting Steiner Tree Problem in which both edge weights and node
prizes are subject to uncertainty was proposed in Álvarez-Miranda et al.
[2013]. Moreover, a Two-stage Robust Steiner tree was presented in Khandekar
et al. [2008]. In the initial stage, a small subset of terminal nodes is
given. In the second stage, the edge weights are increased by a factor
$\lambda$ and several scenarios can occur, each one with a new set of terminal
nodes. The objective is to minimize the maximum overall cost over all
scenarios.

Other variations of Steiner problems with data uncertainty were handled by
means of stochastic programming. The most studied of these problems is the
Two-stage Stochastic Steiner Tree in graphs with recourse [Bomze et al., 2010;
Fleischer et al., 2006; Gupta e Pál, 2005]. In the initial stage, a known
probability distribution $\pi$ is set on subsets of nodes and a cost is
assigned to each edge of the graph. In the second stage, a subset of nodes
materializes, given their prior known distribution, and the cost of each edge
is increased by a factor $\lambda$. Then, an additional set of edges can be
bought to build a tree that spans all materialized nodes. The objective is to
minimize the expected cost of the two-stage solution. A mathematical
formulation and an exact algorithm for this problem were presented in Bomze et
al. [2010]. Approximation algorithms were presented in Fleischer et al.
[2006]; Gupta e Pál [2005].

To the best our knowledge, the min-max regret Robust Steiner Tree Problem in
graphs has not been studied in the literature. Therefore, we propose an
Integer Linear Programming (ILP) formulation for MMR-SPT, based on STP’s bi-
directed multi-commodity flow formulation presented in Chopra e Rao [1994]. As
this formulation has an exponentially large number of constraints, we extend
the Benders-like Decomposition framework of Montemanni e Gambardella [2005]
for MMR-SPT. Furthermore, we propose three heuristics based on the framework
of Kasperski e Zieliński [2006]: $(i)$ the Algorithm Mean (AM); $(ii)$ the
Algorithm Upper (AU); and $(iii)$ the Algorithm Mean Upper.

##  3 An ILP formulation for MMR-STP

Our ILP formulation for MMR-STP is based on the multi-commodity flow
formulation for STP proposed in Chopra e Rao [1994]. Let $G^{\prime}=(V,A)$ be
a directed graph, obtained by bi-directing the edges in $E$. Furthermore, let
$r\in Q$ be an arbitrary terminal node, which is referred to as the _root_
node. From this data, STP is formulated by means of binary variables
$x\in\\{0,1\\}^{|A|}$, such that $x_{ij}=1$ if arc $(i,j)\in A$ belongs to the
Steiner tree, and $x_{ij}=0$ otherwise. Besides, we make use of auxiliary
binary variables $y\in\\{0,1\\}^{|A\times Q|}$, such that $y_{ij}^{k}=1$ if
arc $(i,j)\in A$ is used to send an unit of flow from the root $r$ to the
terminal $k\in Q$, and $y_{ij}^{k}=0$ otherwise. The resulting formulation
consists of the objective function (1) and the constraints in (5)–(8).

$\displaystyle\min\sum_{(i,j)\in A}c_{ij}x_{ij}$ (1) $\displaystyle s.t.$
$\displaystyle\sum_{(j,i)\in A}y_{ji}^{k}-\sum_{(i,j)\in
A}y_{ij}^{k}=\left\\{\begin{tabular}[]{l}1, if $j=r$\\\ -1, if $j=k$\\\ 0,
otherwise\end{tabular}\right.,\forall j\in N,\ k\in Q$ (5) $\displaystyle
y_{ij}^{k}+y_{ij}^{k}\leq x_{ij},\quad\forall\,(i,j)\in A,k\in Q$ (6)
$\displaystyle x_{ij}\in\\{0,1\\},\quad\forall\,(i,j)\in A$ (7) $\displaystyle
y_{ij}^{k}\in\\{0,1\\},\quad\forall\,(i,j)\in A,k\in Q$ (8)

The objective function (1) minimizes the cost of the arcs in the Steiner tree.
The constraints in (5) are the classic flow conservation constraints that
enforce a path from the root $r$ to every other terminal $k\in Q$. The
inequalities in (6) project the variables $y$ into the variables $x$. Besides,
together with (5), they enforce that $x$ induce a spanning tree of the
terminals in $Q$. The domain of the variables $x$ and $y$ are defined by (7)
and (8), respectively.

From the STP formulation described above, we have that the polytope that
describes the set $\Phi$ of Steiner trees of $G$ can be formulated by (5)–(8).
We have that MMR-STP can be written as

$\min_{x\in\Phi}Z(x)=\min_{x\in\Phi}F(x,S^{x})-F(z^{S^{x}},S^{x}).$

Besides, from definition 1.2, we have that

$F(x,S^{x})=\sum_{(i,j)\in e}u_{ij}x_{ij},$

and from definition 1.3 and lemma 1.6, we have that

$F(z^{S^{x}},S^{x})=\min_{z\in\Phi}\sum_{(i,j)\in
A}c^{S^{x}}_{ij}z_{ij}=\min_{z\in\Phi}\sum_{(i,j)\in
A}\big{(}l_{ij}+(u_{ij}-l_{ij})x_{ij}\big{)}z_{ij}.$

Therefore, MMR-SPT can be formulated by the 0-1 Bilevel Integer Linear Program
defined by the objective function (9) and the constraints (5)–(8). We note
that (9) is indeed linear as $x$ is constant in the inner optimization
problem.

$\min_{x\in\Phi}\left\\{\sum_{(i,j)\in
A}u_{ij}x_{ij}-\min_{z\in\Phi}\sum_{(i,j)\in
A}\big{(}l_{ij}+(u_{ij}-l_{ij}\big{)}x_{ij})z_{ij}\right\\}$ (9)

We can then obtain a MIP formulation by linearizing $F(y^{S^{x}},S^{x})$, as
explained in Aissi et al. [2009]. Let $y_{ij}^{k}$ and $x_{ij}$ be the binary
variables defined in the STP formulation (1)–(7). Besides, let variable
$\theta\in\mathbb{R}$ be the cost of the Steiner tree in the worst-case
scenario defined by variables $z_{ij}$. The resulting formulation is defined
by the objective function (10) and constraints (11)–(19).

$\displaystyle\min\sum_{(i,j)\in A}u_{ij}x_{ij}-\theta$ (10) $\displaystyle
s.t.$ $\displaystyle\theta\leqslant\sum_{(i,j)\in
A}\big{(}l_{ij}+(u_{ij}-l_{ij}\big{)}x_{ij})z_{ij},\quad\forall\,z\in\Gamma$
(11) $\displaystyle\sum_{(j,i)\in A}y_{ji}^{k}-\sum_{(i,j)\in
A}y_{ij}^{k}=\left\\{\begin{tabular}[]{l}1, if $j=r$\\\ -1, if $j=k$\\\ 0,
otherwise\end{tabular}\right.,\leavevmode\nobreak\ \forall\,j\in N,\ k\in Q$
(15) $\displaystyle y_{ij}^{k}+y_{ij}^{k}\leqslant
x_{ij},\quad\forall\,(i,j)\in A,k\in Q$ (16) $\displaystyle
x_{ij}\in\\{0,1\\},\quad\forall\,(i,j)\in A$ (17) $\displaystyle
y_{ij}^{k}\in\\{0,1\\},\quad\forall\,(i,j)\in A,k\in Q$ (18)
$\displaystyle\theta\in\mathbb{R}$ (19)

The objective function (10) aims at minimizing the maximum regret. The
constraints in (15)–(18) are as previously defined for the STP. The
inequalities in (11) computes the cost of each solution $z\in\Gamma$ in the
worst-case scenario. One can see that we have an inequality (11) for each
possible solution. Therefore, the number of these inequalities is exponential.
In order to satisfy these inequalities, the value of $\theta$ should not be
greater than the cost of any solution $z\in\Gamma$. Finally, the constraint in
(19) defines the domain of variable $\theta$.

##  4 A Benders-like Decomposition for MMR-STP

The Benders-like Decomposition (Benders) for MMR-STP is inspired by the
Benders Decomposition and based on the approaches used to solve other interval
data min-max robust optimization problems, as the Robust Set Covering Problem
Pereira e Averbakh [2013] and the Robust Minimal Spanning Tree Problem
Montemanni [2006]. Benders is based on formulation (10)–(19). As the number of
constraints (11) grows exponentially with the number of nodes, they are
relaxed in the master problem. At each iteration, one of these constraints is
separated and added to the master problem. Benders stops when the lower bound
obtained by solving the master problem is equal to the cost of the best (in
this case optimal) solution.

Let $\Gamma^{h}\subseteq\Gamma$ be the subset of constraints (11) that are
known in the master problem at iteration $h$ of Benders, and $X^{h}$ be the
optimal solution of this problem. The value of $\theta$ may not be equal to
the cost of the optimal solution $Y^{h}\in\Gamma$ of scenario $s(X^{h})$, as
constraints (11) are relaxed. Therefore, a new constraint (11), generated from
$Y^{h}$, must be added to $\Gamma^{h+1}$ in order to update the value of
$\theta$ for $X^{h}$. $Y^{h}$ can be obtained by solving a STP subproblem in
$s(X^{h})$.

In the first iteration, in order to avoid an unbounded master problem,
$\Gamma^{1}$ is initialized with two solutions obtained by the Algorithm Mean
and Algorithm Upper heuristics proposed in Section 5, as suggested in Pereira
e Averbakh [2013]. At each iteration, the master problem and the corresponding
STP subproblem (Equations (1)–(8)) are solved. Given the lower bound $z^{h}$
obtained by solving the master problem at iteration $h$, if
$z^{h}<min_{l\in\\{1,\dots,h\\}}\rho^{s(X^{h})}(X^{h})$,
$\Gamma^{h+1}=\Gamma^{h}\cup\\{Y^{h}\\}$ and a new iteration starts.
Otherwise, Benders stops since an optimal solution was found.

##  5 Heuristics for MMR-STP

A framework for building heuristics that can be applied to any interval data
min-max robust optimization problem was introduced in Kasperski e Zieliński
[2006]. The complexity of the algorithms developed through this framework are
the same of solving the classical counterpart of the robust optimization
problem studied. In this work, we applied this framework to develop three
heuristics for MMR-STP.

The first heuristic, called Algorithm Mean (AM), uses a branch-and-bound
algorithm based on the flow formulation presented in Polzin e Daneshmand
[2001] to solve a STP at the midpoint scenario $s^{=}$. In $s^{=}$, the weight
of each edge is set to its mean value, i.e.
$c_{ij}^{s^{=}}=(u_{ij}+l_{ij})/2$, for all edges $(i,j)\in E$. Next, the
_maximum regret_ of the computed solution is evaluated and returned. The cost
of the solution obtained through AM is bounded by a factor of $2$ from the
optimal solution, as proved in Kasperski e Zieliński [2006].

The second heuristic, called Algorithm Upper (AU), is similar to AM. However,
instead of solving a STP for scenario $s^{=}$, AU solves the STP for the upper
scenario $s^{+}$, where the weight of each edge is set to its upper value,
i.e. $c_{ij}^{s^{+}}=u_{ij}$, for all edges $(i,j)\in E$. Unlike AM, the cost
of the solution obtained by AU is not bounded.

The last heuristic, called Algorithm Mean Upper (AMU), combines AM and AU.
Next, it returns the smallest computed _maximum regret_. As AMU runs AM, it is
also a $2$-approximation algorithm for any interval data min-max robust
optimization problem.

##  6 Computational experiments

Computational experiments have been performed on an Intel Xeon CPU E5645 with
$2.4$ GHz clock and $32$ GB of RAM memory, running under Linux operating
system. The _branch-and-bound_ implementation of the ILOG CPLEX version $12.6$
with default parameter settings was used to solve the mixed integer linear
programs. The algorithms were implemented in C++ using the ILOG Concert
Technology and compiled with GNU g++ 5.4.0. The running time of all algorithms
has been limited to 10800 seconds (3 hours).

The instances used in the experiments are generalizations of classical STP
instances. The 5 first instances (WRP3-11 to WRP3-15) from the SteinLib
111http://elib.zib.de/steinlib WRP3 set were used. Their sizes range from 128
nodes, 227 edges, and 11 terminal nodes (WRP3-11) to 138 nodes, 257 edges, and
15 terminal nodes (WRP3-15). Next, three different methods, namely Beasley
(BE), Montemanni (MO) and Kasperski-Zielinski (KZ), are used to generate the
edge weights interval as in Pereira e Averbakh [2013]. A parameter
$\beta=\\{0.1,0.3,0.5\\}$ is used in BE, while $M=\\{750,1000,1250\\}$ is used
as parameter in MO and KZ. For each method, the higher the parameter value,
the larger the edge weight interval. These methods are applied to the selected
WRP3 instances. Therefore, nine sets of 5 instances were generated by using
different interval sizes. They are used in the experiment described below.

The performance of Benders, AM, AU, and AMU for these sets is displayed in
Table 1. The name of each instance set is shown in Column 1. The average
relative optimality gap of Benders, as well as the average computation time of
these runs are reported in columns 2 and 3, respectively. Then, columns 4 and
5 present respectively $(i)$ the average percent relative deviation to the
Bender’s upper bound and $(ii)$ the average computational time of AM for each
set. The same information is given for AU and for AMU.

| Benders | AM | AU | AMU
---|---|---|---|---
Instance set | gap% | t(s) | %dev | t(s) | %dev | t(s) | %dev | t(s)
WRP3-BE-0.1 | 15.48 | 5948.72 | 3.70 | 1.91 | 1.83 | 1.94 | 1.46 | 3.85
WRP3-BE-0.3 | 14.80 | 4763.78 | 3.12 | 2.03 | 1.03 | 2.74 | 0.91 | 3.77
WRP3-BE-0.5 | 6.25 | 4825.14 | 0.85 | 1.76 | 1.65 | 0.97 | 0.14 | 3.26
WRP3-MO-750 | 6.32 | 6059.24 | 4.33 | 238.80 | 2.29 | 240.00 | 1.21 | 478.80
WRP3-MO-1000 | 12.60 | 7434.67 | 4.22 | 467.28 | 2.80 | 637.26 | 1.96 | 1104.54
WRP3-MO-1250 | 23.64 | 8583.08 | 5.93 | 1231.83 | 2.79 | 1658.32 | 2.79 | 2890.15
WRP3-KZ-750 | 28.37 | 10800.00 | 3.94 | 2916.45 | 3.78 | 2508.25 | 2.02 | 5424.70
WRP3-KZ-1000 | 27.88 | 10800.00 | 1.25 | 2247.66 | 4.10 | 2894.98 | 0.91 | 5142.64
WRP3-KZ-1250 | 27.92 | 8926.96 | 1.83 | 1510.39 | 3.12 | 1486.42 | 0.93 | 2996.81
Table 1: Evaluation of Benders, AM, AU, and AMU

One can see from Table 1 that Benders achieves a smaller relative optimality
gap and running times in BE and MO instances than in KZ. It indicates that the
KZ instances are the most difficult ones among the three proposed sets.
Regarding the interval sizes, we obtained different results for each instance
set. For the BE instances, the smaller is the interval size, the greater is
the average optimality gap. On the other hand, for the MO instances, the
greater is the interval size, the smaller is the average optimality gap.
However, the Benders’s algorithm average optimality gap was almost the same
for all of the KZ instances.

Regarding the heuristics, one can see from this same table that, for BE
instances, AM, AU and AMU average running times never exceeds 4 seconds, but
grow quickly for MO and KZ instances. The maximum average relative deviations
for AM, AU, and AMU are respectively 5.93%, 4.10%, and 2.79%. These results
indicate that the Bender’s algorithm did not greatly improved its initial
solution (which is given by AMU, as explained in Section 4).

##  7 Conclusions

This paper considers a new combinatorial optimization problem that arises from
the uncertain nature of Steiner tree problem applications. We propose a
mathematical formulation based on the robust optimization framework presented
in Kouvelis e Yu [1997] and an exact and three heuristic algorithms to solve
it. Computational experiments show that Benders-like decomposition did not
solve all proposed instances to optimality. However, the heuristics achieve
good results in a small running time. Future works should focus on the
development of new exact and heuristic methods for the studied problem.
Moreover, other mathematical formulations for the Steiner tree problem in
graphs presented in Polzin e Daneshmand [2001] can be extended to handle the
uncertain data for this problem.

## Aknowledgments

This study was financed in part by the _Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior - Brasil_ (CAPES) - Finance Code 001, the _Conselho
Nacional de Desenvolvimento Científico e Tecnológico - Brasil_ (CNPq), the
_Fundação de Amparo à Pesquisa do Estado de Minas Gerais - Brasil_ (FAPEMIG),
and the _Fundação de Amparo à Pesquisa do Estado de São Paulo - Brasil_
(FAPESP).

## References

  * Aissi et al. [2009] Aissi, H., Bazgan, C., e Vanderpooten, D. (2009).  Min-max and min-max regret versions of combinatorial optimization problems: A survey.  European Journal of Operational Research, 197(2):427–438.
  * Álvarez-Miranda et al. [2013] Álvarez-Miranda, E., Ljubić, I., e Toth, P. (2013).  Exact approaches for solving robust prize-collecting steiner tree problems.  European Journal of Operational Research, 229(3):599–612.
  * Assunção et al. [2017] Assunção, L., Noronha, T. F., Santos, A. C., e Andrade, R. (2017).  A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs.  Computers & Operations Research, 81:51–66.
  * Averbakh [2001] Averbakh, I. (2001).  On the complexity of a class of combinatorial optimization problems with uncertainty.  Mathematical Programming, 90(2):263–272.
  * Bomze et al. [2010] Bomze, I., Chimani, M., Jünger, M., Ljubić, I., Mutzel, P., e Zey, B. (2010).  Solving two-stage stochastic steiner tree problems by two-stage branch-and-cut.  In International Symposium on Algorithms and Computation, p. 427–439. Springer.
  * Carvalho et al. [2018] Carvalho, I. A., Noronha, T. F., Duhamel, C., e Vieira, L. F. (2018).  A milp-based vnd for the min-max regret shortest path tree problem with interval costs.  Electronic Notes in Discrete Mathematics, 66:39–46.
  * Carvalho et al. [2016a] Carvalho, I. A., Santos, V. F., e Noronha, T. F. (2016a).  Sobre a complexidade do problema da árvore de caminhos mais curtos robusta.  XLVIII Simpósio Brasileiro de Pesquisa Operacional, p. 12.
  * Carvalho et al. [2016b] Carvalho, I. A., Noronha, T. F., Duhamel, C., e Vieira, L. F. M. (2016b).  A scenario based heuristic for the robust shortest path tree problem.  In VIII Conference on Manufacturing, Modelling, Management & Control, p. 443–448.
  * Catanzaro et al. [2011] Catanzaro, D., Labbé, M., e Salazar-Neumann, M. (2011).  Reduction approaches for robust shortest path problems.  Computers & operations research, 38(11):1610–1619.
  * Chopra e Rao [1994] Chopra, S. e Rao, M. R. (1994).  The steiner tree problem i: Formulations, compositions and extension of facets.  Mathematical Programming, 64(1-3):209–229.
  * Coco et al. [2015] Coco, A. A., Santos, A. C., e Noronha, T. F. (2015).  Senario-based heuristics with path-relinking for the robust set covering problem.  In Proceedings of the XI Metaheuristics International Conference (MIC).
  * Coco et al. [2016] Coco, A. A., Santos, A. C., e Noronha, T. F. (2016).  Coupling scenario-based heuristics to exact methods for the robust weighted set covering problem with interval data.  IFAC-PapersOnLine, 49(12):455–460.
  * Deineko e Woeginger [2010] Deineko, V. G. e Woeginger, G. J. (2010).  Pinpointing the complexity of the interval min–max regret knapsack problem.  Discrete Optimization, 7(4):191–196.
  * Dreyfus e Wagner [1971] Dreyfus, S. E. e Wagner, R. A. (1971).  The steiner problem in graphs.  Networks, 1(3):195–207.
  * Du et al. [2013] Du, D. Z., Smith, J., e Rubinstein, J. H. (2013).  Advances in Steiner trees, volume 6 of Combinatorial optimization.  Springer Science & Business Media.
  * Duin e Voß [1994] Duin, C. e Voß, S. (1994).  Steiner tree heuristics - a survey.  In Operations Research Proceedings 1993, p. 485–496. Springer.
  * Duin e Voß [1999] Duin, C. e Voß, S. (1999).  The pilot method: A strategy for heuristic repetition with application to the steiner problem in graphs.  Networks: An International Journal, 34(3):181–191.
  * Fleischer et al. [2006] Fleischer, L., Könemann, J., Leonardi, S., e Schäfer, G. (2006).  Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, p. 663–670. ACM.
  * Furini et al. [2015] Furini, F., Iori, M., Martello, S., e Yagiura, M. (2015).  Heuristic and exact algorithms for the interval min–max regret knapsack problem.  INFORMS Journal on Computing, 27(2):392–405.
  * Godinho e Paquete [2019] Godinho, N. e Paquete, L. (2019).  A combinatorial branch and bound for the min-max regret spanning tree problem.  In International Symposium on Experimental Algorithms, p. 69–81. Springer.
  * Goemans e Myung [1993] Goemans, M. X. e Myung, Y.-S. (1993).  A catalog of steiner tree formulations.  Networks, 23(1):19–28.
  * Gupta e Pál [2005] Gupta, A. e Pál, M. (2005).  Stochastic steiner trees without a root.  In International Colloquium on Automata, Languages, and Programming, p. 1051–1063. Springer.
  * Karaşan et al. [2001] Karaşan, O., Pinar, M., e Yaman, H. (2001).  The robust shortest path problem with interval data.  Technical report, Bilkent University, Ankara, Turkey.
  * Karp [1972] Karp, R. M. (1972).  Reducibility among combinatorial problems.  In Complexity of computer computations, p. 85–103. Springer.
  * Kasperski e Zieliński [2006] Kasperski, A. e Zieliński, P. (2006).  An approximation algorithm for interval data minmax regret combinatorial optimization problems.  Information Processing Letters, 97(5):177–180.
  * Kasperski e Zieliński [2016] Kasperski, A. e Zieliński, P. (2016).  Robust discrete optimization under discrete and interval uncertainty: A survey.  In Robustness Analysis in Decision Aiding, Optimization, and Analytics, p. 113–143. Springer.
  * Khandekar et al. [2008] Khandekar, R., Kortsarz, G., Mirrokni, V., e Salavatipour, M. R. (2008).  Two-stage robust network design with exponential scenarios.  In European Symposium on Algorithms, p. 589–600. Springer.
  * Kouvelis e Yu [1997] Kouvelis, P. e Yu, G. (1997).  Robust discrete optimization and its applications, volume 14 of Nonconvex optimization and its applications.  Springer.
  * Lucena e Beasley [1998] Lucena, A. e Beasley, J. (1998).  A branch and cut algorithm for the steiner problem in graphs.  Networks: An International Journal, 31(1):39–59.
  * Montemanni [2006] Montemanni, R. (2006).  A benders decomposition approach for the robust spanning tree problem with interval data.  European Journal of Operational Research, 174(3):1479–1490.
  * Montemanni et al. [2007] Montemanni, R., Barta, J., Mastrolilli, M., e Gambardella, L. M. (2007).  The robust traveling salesman problem with interval data.  Transportation Science, 41(3):366–381.
  * Montemanni e Gambardella [2005] Montemanni, R. e Gambardella, L. M. (2005).  The robust shortest path problem with interval data via benders decomposition.  4or, 3(4):315–328.
  * Pereira e Averbakh [2013] Pereira, J. e Averbakh, I. (2013).  The robust set covering problem with interval data.  Annals of Operations Research, p. 1–19.
  * Pérez-Galarce et al. [2018] Pérez-Galarce, F., Candia-Véjar, A., Astudillo, C., e Bardeen, M. (2018).  Algorithms for the minmax regret path problem with interval data.  Information Sciences, 462:218–241.
  * Polzin e Daneshmand [2001] Polzin, T. e Daneshmand, S. V. (2001).  A comparison of steiner tree relaxations.  Discrete Applied Mathematics, 112(1):241–261.
  * Prömel e Steger [2012] Prömel, H. J. e Steger, A. (2012).  The Steiner tree problem: a tour through graphs, algorithms, and complexity.  Springer Science & Business Media.
  * Wald [1939] Wald, A. (1939).  Contributions to the theory of statistical estimation and testing hypotheses.  Annals of Mathematics, 10:299–326.


# SIMDRAM: A Framework for Bit-Serial SIMD Processing Using DRAM
_Extended Abstract_

Nastaran Hajinazar ⋄⋆ 11footnotemark: 1 Geraldo F. Oliveira ⋄ Sven Gregorio ⋄
João Dinis Ferreira ⋄ Nika Mansouri Ghiasi ⋄

Minesh Patel ⋄ Mohammed Alser ⋄ Saugata Ghose ⊙ Juan Gómez-Luna ⋄ Onur Mutlu ⋄
⋄ETH Zürich ⋆Simon Fraser University ⊙University of Illinois at
Urbana–Champaign  Nastaran Hajinazar and Geraldo F. Oliveira are co-primary
authors.

##  1 Motivation & Limitations of State-of-the-Art

The increasing prevalence and growing size of data in modern applications has
led to high costs for computation in traditional computer architectures.
Moving large volumes of data between memory devices (e.g., DRAM) and the CPU
across bandwidth-limited memory channels can consume more than 60% of the
total energy in modern systems[48, 10]. To mitigate these costs, researchers
have proposed a new computing paradigm, known as _processing-in-memory_ (PIM).
The key idea of PIM is to move computation closer to where the data resides,
reducing (and in some cases eliminating) the need to move data between memory
and the processor.

There are two main approaches to PIM [27, 49]: (1) processing-near-memory,
where PIM logic is added to the same die as memory or to the logic layer of
3D-stacked memory [40, 2, 51, 10, 11, 69, 25, 35, 18, 55, 52, 3, 26, 34, 30,
39, 33, 12, 31, 13, 70, 54, 20, 46, 53, 4, 32, 8, 41, 17]; and (2) processing-
using-memory, which makes use of the operational principles of the memory
cells themselves to perform computation by enabling interactions between cells
[15, 61, 58, 60, 43, 57, 59, 16, 68, 65, 64, 24, 19, 1, 22]. Since processing-
using-memory operates directly in the memory cells, it benefits from the large
internal bandwidth and parallelism available inside the memory arrays, which
are significantly higher than those for processing-near-memory solutions.

A common approach for processing-using-memory architectures is to make use of
bulk bitwise computation. Many widely-used data-intensive applications (e.g.,
databases, neural networks, graph analytics) heavily rely on a broad set of
simple (e.g., AND, OR, XOR) and complex (e.g., equality check, multiplication,
addition) bitwise operations. Ambit [58, 56], an in-DRAM processing-using-
memory accelerator, was the first work to propose exploiting DRAM’s analog
operation to perform bulk bitwise AND, OR, and NOT logic operations. Inspired
by Ambit, many prior works have explored DRAM (as well as NVM) designs that
are capable of performing in-memory bitwise operations [6, 7, 5, 44, 24, 68].
However, a major shortcoming prevents these proposals from becoming widely
applicable: they support only basic operations (e.g., Boolean operations,
addition) and fall short on flexibly supporting new and more complex
operations. Some prior works propose processing-using-DRAM designs that
support more complex operations [43, 16]. However, such designs (1) require
significant changes to the DRAM subarray, and (2) support only a limited and
specific set of operations, lacking the flexibility to support new operations
and cater to the wide variety of applications that can potentially benefit
from in-memory computation. Our goal in this paper is to design a framework
that aids the adoption of processing-using-DRAM by efficiently implementing
complex operations and providing the flexibility to support new desired
operations.

##  2 The Proposal

We propose SIMDRAM, an end-to-end processing-using-DRAM framework that
provides the programming interface, the ISA and the hardware support for (1)
efficiently computing _complex_ operations, and (2) providing the ability to
implement _arbitrary_ operations as required, all in an in-DRAM massively-
parallel SIMD substrate. At its core, we build the SIMDRAM framework around a
DRAM substrate that enables two previously-proposed techniques: (1) vertical
data layout in DRAM, and (2) majority-based logic for computation.

Vertical Data Layout. Supporting bit-shift operations is essential for
implementing complex computations, such as addition or multiplication. Prior
works show that employing a vertical layout [9, 62, 24, 5, 19, 22] for the
data in DRAM, such that all bits of an operand are placed in a single DRAM
column (i.e., in a single bitline), eliminates the need for adding extra logic
in DRAM to implement shifting [16, 43]. Accordingly, SIMDRAM supports
efficient bit-shift operations by storing operands in a vertical fashion in
DRAM. This provides SIMDRAM with two key benefits. First, a bit-shift
operation can be performed by simply copying a DRAM row into another row
(using RowClone [57], LISA [14] or FIGARO [67]). For example, SIMDRAM can
perform a left-shift-by-one operation by copying the data in DRAM row $j$ to
DRAM row $j+1$. (Note that while SIMDRAM supports bit shifting, we can
optimize many applications to avoid the need for explicit shift operations, by
simply changing the row indices of the SIMDRAM commands that read the shifted
data). Second, SIMDRAM enables massive parallelism, wherein each DRAM column
operates as a SIMD lane by placing the source and destination operands of an
operation on top of each other in the same DRAM column.

Majority-Based Computation. Prior works use majority operations to implement
basic logical operations [58, 24, 56, 43] (e.g., AND, OR) or addition [6, 5,
23, 43, 16, 24]. These basic operations are then used as basic building blocks
to implement the target in-DRAM computation. SIMDRAM extends the use of the
majority operation by directly using the logically complete set of majority
(MAJ) and NOT operations to implement in-DRAM computation. Doing so enables
SIMDRAM to achieve higher performance, throughput, and reduced energy
consumption compared to using basic logical operations as building blocks for
in-DRAM computation. We find that a computation typically requires fewer DRAM
commands using MAJ and NOT than using basic logical operations such as AND,
OR, and NOT.

##  3 SIMDRAM Framework

SIMDRAM is the first end-to-end framework for processing-using-DRAM. SIMDRAM
consists of three key steps to enable a desired operation in DRAM: (1)
building an efficient MAJ/NOT-based representation of the desired operation,
(2) mapping the operation input and output operands to DRAM rows and to the
required DRAM commands that produce the desired operation, and (3) executing
the operation. These three steps ensure efficient computation of a wide range
of arbitrary and complex operation in DRAM. The first two steps give users the
flexibility to efficiently implement and compute any desired operation in
DRAM. The third step controls the execution flow of the in-DRAM computation,
transparently from the user. We briefly describe these steps.

The goal of the first step is to use logic optimization to minimize the number
of DRAM row activations, and therefore the compute latency required to perform
a specific operation. Accordingly, for a desired computation, the first step
is to derive its _optimized_ MAJ/NOT-based implementation from its AND/OR/NOT-
based implementation.

The second step translates the MAJ/NOT-based implementation into DRAM row
activations. This step includes (1) mapping the operands to the designated
rows in DRAM, and (2) defining the sequence of DRAM row activations that are
required to perform the computation. SIMDRAM chooses the operand-to-row
mapping and the sequence of DRAM row activations to minimize the number of
DRAM row activations required for a specific operation.

The third step is to program the memory controller to issue the sequence of
DRAM row activations to the appropriate rows in DRAM to perform the
computation of the operation from start to end. To this end, SIMDRAM uses a
_control unit_ in the memory controller that transparently executes the
sequence of DRAM row activations for each specific operation.

##  4 System Integration

To incorporate SIMDRAM into a real system, we address three integration
challenges as part of our work: (1) managing memory with both vertical and
horizontal layouts in a system, (2) exposing SIMDRAM functionality to
programmers and compilers, and (3) dealing with potential RowHammer-based
security exploits [37, 50, 36, 21, 47]. As part of the support for system
integration, we introduce two components.

First, SIMDRAM adds a _transposition unit_ in the memory controller that
transforms the data layout from the conventional horizontal layout to vertical
layout (and vice versa), as required, thereby allowing both layouts to
coexist. Using the transposition unit, SIMDRAM provides the ability to store
only the data that is required for in-DRAM computation in the vertical layout.
As a result, SIMDRAM maintains the horizontal layout for the rest of the data
and allows the CPU to read/write its operands from/to DRAM in a horizontal
layout and at full bandwidth.

Second, SIMDRAM extends the ISA to enable the user/compiler to communicate
with the SIMDRAM control unit. These extensions include instructions for (1)
transposing data and (2) indicating specific operations to be issued by the
control unit during in-DRAM execution.

##  5 Key Results and Contributions

The end-to-end support enables SIMDRAM as a holistic approach that facilitates
the adoption of processing-using-DRAM. The SIMDRAM framework efficiently
supports a wide range of operations of different types. In this work, we
demonstrate the functionality of the SIMDRAM framework using an example set of
operations including (1)  _N_ -input logic operations (e.g., AND/OR/XOR of
more than 2 input bits); (2) relational operations (e.g., equality/inequality
check, greater than, maximum, minimum); (3) arithmetic operations (e.g.,
addition, subtraction, multiplication, division); (4) predication (e.g., if-
then-else); and (5) other complex operations such as bitcount and ReLU [29].
The SIMDRAM framework is not limited to these operations, and can enable
processing-using-DRAM for other existing and future operations.

We compare the benefits of SIMDRAM to different state-of-the-art computing
platforms (CPU, GPU, and the Ambit [58] in-DRAM computing mechanism). We
comprehensively evaluate SIMDRAM’s reliability, area overhead, throughput, and
energy efficiency. Our evaluation shows that SIMDRAM provides up to
$5.1\times$ higher throughput and $2.5\times$ higher energy efficiency
compared to Ambit [58] for 16 different operations, while incurring less than
1% DRAM area overhead.

We leverage the SIMDRAM framework to accelerate seven application kernels from
machine learning, databases, and image processing (VGG-13 [63], VGG-16 [63],
LeNET [38], kNN [42], TPC-H [66], BitWeaving [45], Brightness [28]). SIMDRAM
provides up to $2.5\times$ speedup for the kernels compared to Ambit [58].
Compared to a CPU and a high-end GPU, SIMDRAM is $257\times$ and $31\times$
more energy efficient, while providing $93\times$ and $6\times$ higher
throughput, respectively. We also evaluate the reliability of SIMDRAM under
different degrees of manufacturing process variation, and observe that it
guarantees correct operation as the DRAM process technology node scales down
to smaller sizes.

We make the following key contributions:

  * •

To our knowledge, this is the first work to propose a framework to enable
efficient computation of a flexible and wide range of operations in a
massively parallel SIMD substrate built via processing-using-DRAM.

  * •

SIMDRAM provides a three-step framework to develop efficient and reliable
MAJ/NOT-based implementations of a wide range of operations. We design this
framework, and add hardware and ISA support, to (1) address key system
integration challenges and (2) allow programmers to employ new SIMDRAM
operations without hardware changes.

  * •

We provide a detailed reference implementation of SIMDRAM, including required
changes to the user applications, ISA, and hardware.

  * •

We evaluate the reliability of SIMDRAM under different degrees of process
variation and observe that it guarantees correct operation as the DRAM
technology scales to smaller node sizes.

IEEEexample:BSTcontrol

## References

  * [1] S. Aga _et al._ , “Compute Caches,” in _HPCA_ , 2017.
  * [2] J. Ahn _et al._ , “A Scalable Processing-in-Memory Accelerator for Parallel Graph Processing,” in _ISCA_ , 2015.
  * [3] J. Ahn _et al._ , “PIM-Enabled Instructions: A Low-Overhead, Locality-Aware Processing-in-Memory Architecture,” in _ISCA_ , 2015.
  * [4] B. Akin _et al._ , “Data Reorganization in Memory Using 3D-Stacked DRAM,” in _ISCA_ , 2016.
  * [5] M. F. Ali _et al._ , “In-Memory Low-Cost Bit-Serial Addition Using Commodity DRAM Technology,” in _TCAS-I_ , 2019.
  * [6] S. Angizi and D. Fan, “GraphiDe: A Graph Processing Accelerator Leveraging in-DRAM-Computing,” in _GLSVLSI_ , 2019.
  * [7] S. Angizi _et al._ , “IMCE: Energy-Efficient Bitwise In-Memory Convolution Engine for Deep Neural Network,” in _ASP-DAC_ , 2018.
  * [8] O. O. Babarinsa and S. Idreos, “JAFAR: Near-Data Processing for Databases,” in _SIGMOD_ , 2015.
  * [9] K. E. Batcher, “Bit-Serial Parallel Processing Systems,” in _IEEE Trans. Comput._ , 1982.
  * [10] A. Boroumand _et al._ , “Google Workloads for Consumer Devices: Mitigating Data Movement Bottlenecks,” in _ASPLOS_ , 2018.
  * [11] A. Boroumand _et al._ , “LazyPIM: An Efficient Cache Coherence Mechanism for Processing-in-Memory,” _IEEE CAL_ , 2017.
  * [12] A. Boroumand _et al._ , “CoNDA: Efficient Cache Coherence Support for Near-Data Accelerators,” in _ISCA_ , 2019.
  * [13] D. S. Cali _et al._ , “GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis,” in _MICRO_ , 2020.
  * [14] K. K. Chang _et al._ , “Low-Cost Inter-Linked Subarrays (LISA): Enabling Fast Inter-Subarray Data Movement in DRAM,” in _HPCA_ , 2016.
  * [15] P. Chi _et al._ , “PRIME: A Novel Processing-in-Memory Architecture for Neural Network Computation in ReRAM-Based Main Memory,” in _ISCA_ , 2016\.
  * [16] Q. Deng _et al._ , “DrAcc: a DRAM based Accelerator for Accurate CNN Inference,” in _DAC_ , 2018.
  * [17] F. Devaux, “The True Processing in Memory Accelerator,” in _HCS_ , 2019\.
  * [18] M. Drumond _et al._ , “The Mondrian Data Engine,” in _ISCA_ , 2017.
  * [19] C. Eckert _et al._ , “Neural Cache: Bit-serial in-Cache Acceleration of Deep Neural Networks,” in _ISCA_ , 2018.
  * [20] A. Farmahini-Farahani _et al._ , “NDA: Near-DRAM Acceleration Architecture Leveraging Commodity DRAM Devices and Standard Memory Modules,” in _HPCA_ , 2015.
  * [21] P. Frigo _et al._ , “TRRespass: Exploiting the Many Sides of Target Row Refresh,” in _IEEE S &P_, 2020.
  * [22] D. Fujiki _et al._ , “Duality Cache for Data Parallel Acceleration,” in _ISCA_ , 2019.
  * [23] P.-E. Gaillardon _et al._ , “The Programmable Logic-in-Memory (PLiM) Computer,” in _DATE_ , 2016.
  * [24] F. Gao _et al._ , “ComputeDRAM: In-Memory Compute Using Off-the-Shelf DRAMs,” in _MICRO_ , 2019.
  * [25] M. Gao and C. Kozyrakis, “HRL: Efficient and Flexible Reconfigurable Logic for Near-Data Processing,” in _HPCA_ , 2016.
  * [26] M. Gao _et al._ , “TETRIS: Scalable and Efficient Neural Network Acceleration with 3D Memory,” in _ASPLOS_ , 2017.
  * [27] S. Ghose _et al._ , “Processing-in-Memory: A Workload-Driven Perspective,” _IBM JRD_ , 2019.
  * [28] R. C. Gonzalez and R. E. Woods, _Digital Image Processing_ , 2nd ed. Addison-Wesley, 2002.
  * [29] I. Goodfellow _et al._ , _Deep Learning_. MIT Press, 2016.
  * [30] P. Gu _et al._ , “Leveraging 3D Technologies for Hardware Security: Opportunities and Challenges,” in _GLSVLSI_ , 2016.
  * [31] K. Hsieh _et al._ , “Transparent Offloading and Mapping (TOM) Enabling Programmer-Transparent Near-Data Processing in GPU Systems,” in _ISCA_ , 2016.
  * [32] K. Hsieh _et al._ , “Accelerating Pointer Chasing in 3D-Stacked Memory: Challenges, Mechanisms, Evaluation,” in _ICCD_ , 2016.
  * [33] Hybrid Memory Cube Consortium, “Hybrid Memory Cube Specification Rev. 2.0,” http://www.hybridmemorycube.org/.
  * [34] D. Kim _et al._ , “Neurocube: A Programmable Digital Neuromorphic Architecture with High-Density 3D Memory,” in _ISCA_ , 2016.
  * [35] J. S. Kim _et al._ , “GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping using Processing-in-Memory Technologies,” in _APBC_ , 2018\.
  * [36] J. S. Kim _et al._ , “Revisiting RowHammer: An Experimental Analysis of Modern DRAM Devices and Mitigation Techniques,” in _ISCA_ , 2020.
  * [37] Y. Kim _et al._ , “Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors,” in _ISCA_ , 2014.
  * [38] Y. LeCun _et al._ , “LeNet-5, Convolutional Neural Networks,” http://yann.lecun.com/exdb/lenet, 2015.
  * [39] D. U. Lee _et al._ , “25.2 A 1.2V 8Gb 8-Channel 128GB/s High-Bandwidth Memory (HBM) Stacked DRAM with Effective Microbump I/O Test Methods Using 29nm Process and TSV,” in _ISSCC_ , 2014.
  * [40] D. Lee _et al._ , “Simultaneous Multi-Layer Access: Improving 3D-Stacked Memory Bandwidth at Low Cost,” _ACM TACO_ , 2016.
  * [41] J. H. Lee _et al._ , “BSSync: Processing Near Memory for Machine Learning Workloads with Bounded Staleness Consistency Models,” in _PACT_ , 2015.
  * [42] Y. Lee, “Handwritten Digit Recognition Using k-Nearest-Neighbor, Radial-Basis Function, and Backpropagation Neural Networks,” _Neural Computation_ , 1991\.
  * [43] S. Li _et al._ , “DRISA: A DRAM-Based Reconfigurable In-Situ Accelerator,” in _MICRO_ , 2017.
  * [44] S. Li _et al._ , “Pinatubo: A Processing-in-Memory Architecture for Bulk Bitwise Operations in Emerging Non-Volatile Memories,” in _DAC_ , 2016.
  * [45] Y. Li and J. M. Patel, “BitWeaving: Fast Scans for Main Memory Data Processing,” in _SIGMOD_ , 2013.
  * [46] G. H. Loh _et al._ , “A Processing in Memory Taxonomy and a Case for Studying Fixed-Function PIM,” in _WoNDP_ , 2013.
  * [47] O. Mutlu, “The RowHammer Problem and Other Issues We May Face as Memory Becomes Denser,” in _DATE_ , 2017.
  * [48] O. Mutlu _et al._ , “Processing Data Where It Makes Sense: Enabling In-Memory Computation,” _MICPRO_ , 2019.
  * [49] O. Mutlu _et al._ , “A Modern Primer on Processing in Memory,” _Emerging Computing: From Devices to Systems - Looking Beyond Moore and Von Neumann_ , 2021.
  * [50] O. Mutlu and J. S. Kim, “RowHammer: A Retrospective,” in _TCAD_ , 2019.
  * [51] L. Nai _et al._ , “GraphPIM: Enabling Instruction-Level PIM Offloading in Graph Computing Frameworks,” in _HPCA_ , 2017.
  * [52] G. F. Oliveira _et al._ , “NIM: An HMC-Based Machine for Neuron Computation,” in _ARC_ , 2017.
  * [53] A. Pattnaik _et al._ , “Scheduling Techniques for GPU Architectures with Processing-in-Memory Capabilities,” in _PACT_ , 2016.
  * [54] S. H. Pugsley _et al._ , “NDC: Analyzing the Impact of 3D-Stacked Memory+Logic Devices on MapReduce Workloads,” in _ISPASS_ , 2014.
  * [55] P. C. Santos _et al._ , “Operand Size Reconfiguration for Big Data Processing in Memory,” in _DATE_ , 2017.
  * [56] V. Seshadri _et al._ , “Fast Bulk Bitwise AND and OR in DRAM,” in _IEEE CAL_ , 2015.
  * [57] V. Seshadri _et al._ , “RowClone: Fast and Energy-Efficient in-DRAM Bulk Data Copy and Initialization,” in _MICRO_ , 2013.
  * [58] V. Seshadri _et al._ , “Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology,” in _MICRO_ , 2017.
  * [59] V. Seshadri and O. Mutlu, “The Processing Using Memory Paradigm: In-DRAM Bulk Copy, Initialization, Bitwise AND and OR,” arXiv:1610.09603 [cs.AR], 2016.
  * [60] V. Seshadri and O. Mutlu, “In-DRAM Bulk Bitwise Execution Engine,” arXiv:1905.09822 [cs.AR], 2019.
  * [61] A. Shafiee _et al._ , “ISAAC: A Convolutional Neural Network Accelerator with In-Situ Analog Arithmetic in Crossbars,” in _ISCA_ , 2016.
  * [62] W. Shooman, “Parallel Computing with Vertical Data,” in _EJCC_ , 1960.
  * [63] K. Simonyan and A. Zisserman, “Very Deep Convolutional Networks for Large-Scale Image Recognition,” arXiv:1409.1556 [cs.CV], 2014.
  * [64] L. Song _et al._ , “PipeLayer: A Pipelined ReRAM-based Accelerator for Deep Learning,” in _HPCA_ , 2017.
  * [65] L. Song _et al._ , “GraphR: Accelerating Graph Processing Using ReRAM,” in _HPCA_ , 2018.
  * [66] Transaction Processing Performance Council, “TPC-H,” http://www.tpc.org/tpch/.
  * [67] Y. Wang _et al._ , “FIGARO: Improving System Performance via Fine-Grained In-DRAM Data Relocation and Caching,” in _MICRO_ , 2020.
  * [68] X. Xin _et al._ , “ELP2IM: Efficient and Low Power Bitwise Operation Processing in DRAM,” in _HPCA_ , 2020.
  * [69] D. Zhang _et al._ , “TOP-PIM: Throughput-Oriented Programmable Processing in Memory,” in _HPDC_ , 2014.
  * [70] Q. Zhu _et al._ , “Accelerating Sparse Matrix-Matrix Multiplication with 3D-Stacked Logic-in-Memory Hardware,” in _HPEC_ , 2013.