Radio environment maps (REMs) and geolocation database represent an important source of information for the operation of cognitive radio networks, replacing or complementing spectrum sensing information. This paper provides a survey of methods for constructing the radio frequency layer of radio environment map (RFREM) using distributed measurements of the signal levels at a given frequency in space and time. The signal level measurements can be obtained from fixed or mobile devices capable of sensing radio environment and sending this information to the REM. The signal measurements are complemented with information already stored in different REM content layers. The combined information is applied for estimation of the RFREM layer. The RFREM construction methods are compared, and their advantages and disadvantages with respect to the spatial distribution of signal measurements and computational complexity is given. This survey also indicates possible directions of further research in indirect RFREM construction methods. It emphasizes that accurate RFREM construction methods should in the best case support operation with random and clustered signal measurements, their operation should not be affected by measurements outliers, and it must estimate signal levels comparably on all RFREM locations with moderate computational effort.
1. Introduction
T
he runtime awareness of the operating environment conditions is becoming increasingly important complementary information for smart and efficient usage of resources in different types of dynamic systems. The awareness about the radio environment in a wireless system is not an exception given that the radio spectrum is a limited natural resource which has to be used as efficiently as possible. Current spectrum allocation where chunks of spectrum are exclusively licensed to traditional users of radio communications, e.g., military, radio and TV broadcasters and mobile operators, leads to inefficient use of this natural resource. The measurement campaigns also revealed that some licenced frequency bands are often underutilized in space and time
[1]
, while the unlicensed bands and frequency bands licensed to mobile operators are saturated. In order to overcome this imbalance, the concept of dynamic spectrum sharing (DSS) has been introduced for the use in cognitive radio (CR). This exploits the awareness of radio environment to dynamically allocate unused but allocated chunk of spectrum to the user with no prime rights, i.e. a secondary user. However, the protection of a primary user is introduced in this concept. It is forcing the secondary user to free the spectrum and find the new unused part of it, when the primary user starts using the spectrum.
The basic approach to obtain the awareness of the local radio environment is spectrum sensing. This, with the current state of technology, cannot satisfy the sensitivity levels required by FCC
[2]
and ECC
[3]
within reasonable costs, to be included in each terminal. An alternative approach is the use of geolocation database on available radio resources. Geolocation database is proposed for the introduction of unlicensed (secondary) devices in the recently vacant parts of the VHF and UHF TV frequency bands, so called TV White Spaces (TVWS). This database stores locations and various parameters of primary and secondary spectrum users, such as their antenna heights, transmit powers, technology, operation channel(s), etc. Based on this information it constructs a real time view of the spectrum occupancy at the TV bands at each location of interest. CRs can thus consult geolocation database before accessing the spectrum and retrieve the information on available channels, including the time constraints and the maximum allowed transmission powers
[1]
. However, geolocation database shows some limitation in highly dynamic radio environments. In such case, CRs can consult an enhanced concept which combines the spectrum sensing with the geolocation and database approach, known as radio environment map (REM)
[4]
. Its most important content is the interference information, which can be estimated from maps representing the coverage of an area with the radio signal, named radio frequency (RF) REM layers or RFREMs. The estimation of RFREM for transmitters, which parameters are known and are not varying in time, is straightforward. It can be based on the approaches for radio network planning including empirical, semiempirical and deterministic channel models and their calibration applying field measurement results. On the other hand, when the transmitter parameters are unknown, the construction of the RFREM layer is performed with the methods relying on distributed sensing of the radio environment. It can apply interpolation of the signal measurements, utilize transmitter location and propagation modelling, or combine both approaches. While the interpolation based methods are most often considered in practice, the results from
[1]
show that methods utilizing transmitter location and propagation modelling can construct more accurate RFREMs. However, there are many different RFREM construction methods with their own advantages, disadvantages and computationaltime complexity, which should be carefully analysed before selecting the most suitable for a given application.
In this paper we are surveying the contemporary methods for estimating the RFREM layer, which are following different construction approaches and considering the measurements distributed in space and time. The rest of this article is organized as follows. We introduce REM and its content incorporating the RFREM layers in Section 2. The RFREM construction methods are briefly surveyed in Section 3, while their advantages, disadvantages and further research possibilities are discussed in Section 4. Finally, Section 5 concludes the paper.
2. Radio environment map
REM has been envisioned to include comprehensive multidomain information for CR
[5]
to allow sharing of geographically unused spectrum primarily allocated to the television broadcast services
[6]
. In the current state of the art, REM can be a centralized or distributed integrated information structure
[7]
, which involves various types of information, algorithms and methods developed to support the decision making by a cognitive engine
[8]
. Besides being used for processing and reasoning, it is also a data storage
[9]
with modular and extendible structure for collecting and managing comprehensive multidomain information
[10
,
11]
from heterogeneous sources. Furthermore, it is considered as an extension to the available resource map (ARM)
[12]
as a knowledge base for storing dynamic information related to the radio environment of the wireless systems
[13]
and a network entity capable of reconfiguring measurement capable devices (MCDs)
[4]
. As such, REM supports various CR applications dealing with (i) hierarchical spectrum access in licenced bands, (ii) spectrum sharing in unlicensed bands, (iii) intra operator radio resource management, and (iv) dedicated spectrum monitoring
[14]
. For example, in (i), REM can enable CRs’ coordinated or noncoordinated spectrum access, operation of spectrum leaser, broker or seller, out of band cognitive femto cells operation, IEEE 802.11af standard networks, interference mitigation, smart metering, long term evolution (LTE) network operation in TV white spaces, etc. In (ii), REM can enable hierarchical or nonhierarchical spectrum access of coordinated, noncoordinated or adhoc CRs. Moreover, it can be used for minimizing signalling, interference management (IM), optimization of radio resources allocation, dealing with jammer issues, etc. In (iii) it can be used for radio resource management, dynamic spectrum allocation, networks planning, maintenance and optimization of radio resources. In LTE networks it can be used to identify badsignal areas and automatic neighbour relation (ANR), minimize drive tests, support power management and depict coverage with radio signals. Additionally, REM can support soft frequency reuse (SFR), handovers optimization, coexistence of various CR technologies, spectrum refarming, automatic femto cells configuration, etc. With (iv), REM can support various military applications, intelligent transport systems, selforganizing networks, distributed computing optimization, etc.
To support such wide range of applications REM stores data in REMSA. The data in REMSA is classified into static, volatile and derived
[1]
, or in simplified terms we can talk about (i) long term information and (ii) short term information. The long term information is changing slowly, but it may be also static or quasi static. It is related to TV broadcast and receiver stations, mobile operator base stations (BSs) and similar static transmitters with predominantly fixed operating parameters. On the contrary, the period of updating short term information, such as information about wireless microphones and other portable transmitters, should be much shorter and can be obtained directly via observing the radio environment in the area of interest. If the REM contains only static information, it is classified as static REM (SREM), while both, slow and fast changing information is included in dynamic REM (DREM)
[4]
. Furthermore, REM can be classified as local (LREM) or global (GREM)
[12
,
14]
with respect to CR network architecture and amount of the stored details. Mostly referring to the work done on REM within the European FP7 project FARAMIR
[4]
, REM is generally depicted to consist of the REM data storage and acquisition unit (REMSA), the REM manager, MCDs and a set of connection interfaces and a graphical user interface (GUI). REMSA interchanges instructions with MCDs and collects their scheduled, requested or contributed (in participatory manner) measurement reports, and stores both, raw data and results of various REM layers’ construction or modelling processes. The REM manager is the intelligent part of REM where all the processing and exchange of requests with other REM entities is performed. MCDs can be diverse spectrum sensing sources, ranging from highfidelity spectrum analysers to dedicated lowcost embedded solutions
[9]
, such as mobile terminals, smart phones, tablet computers, and various sensor nodes. The connection interfaces and GUI are in charge of interaction with the REM. This general REM structure is depicted in
Fig. 1
.
The REM structure [4].
The REM content in REMSA is used to depict past, current, as well as expected conditions in the area of interest and can be classified into three main categories or layers related to: (i) radio elements, (ii) radio scene, and (iii) radio environment
[4]
. The content of REM layers is more detailed in
Fig. 2
. The layer of radio elements consists of several sublayers describing the type of devices, their communication and sensing capabilities, etc. The sublayers of radio scene layer depict radio element communication patterns, their communication priorities, etc. Finally, the sublayers of radio environment layer include information which characterizes environment and radio conditions in a particular operating environment. This includes various types of data such as terrain elevation, clutter and other environment characteristics, signal level measurements obtained by MCDs, communication channel conditions, propagation modelling parameters, etc.
The main content categories of the REM storage divided into layers and sublayers.
Each individual RFREM layer is a sublayer of the radio environment layer and in a most basic form presents coverage of an area with the radio signal at a specified frequency. In literature it is also referred to as RF environment map (RFEM), radio electric exposure level map (REELM), power spectral density map (PSD), and most often simplified as radio environment map (REM), although the latter is broadly used for the entire REM. Consequently, RFREM construction surveyed in this paper is in the literature found under different terms, most often as the REM construction.
3. RFREM construction
The construction of an additional REM content is a process of obtaining the relevant information from REMSA, its processing, and preparing new derived information to be stored back in REMSA. The RFREM construction process, which serves as a basic example of the REM construction, is schematically depicted in
Fig. 3
. It primarily exploits MCD signal measurements and deals with estimating the signal levels at geographical locations i.e. RFREM elements where signal measurements are not available. Additionally, it can rely on other relevant information such as properties of the transmitters and the operating environment. The quality of constructed RFREM depends on its resolution, the characteristics of the construction method and quality of its input data. The input data mostly depends on its own source, while the RFREM construction methods are classified into three basic categories. There are (i) direct methods applying interpolation, (ii) indirect methods utilizing transmitter location and propagation modelling, and (iii) hybrid methods which combine both approaches. Prior the RFREM construction, the available signal measurements obtained as received signal strength (RSS), received signal code power (RSCP), reference signal received power (RSRP) or other specific signal strength values are filtered and preprocessed. If multiple measurements exist for a particular RFREM location, the median or mean value of measurements is estimated. Since the average value can be significantly influenced by the outlined measurements, making it not very representative of the signal value at the location, the median gives better representation of central signal tendency than the mean value.
The RFREM construction based on direct, indirect and hybrid construction methods.
 3.1. Direct construction methods
The direct RFREM construction is based on the interpolation approach which is used to estimate the signal levels at locations of interest as schematically depicted in
Fig. 4
. The RFREM is most often constructed by interpolating available signal measurements using local neighbourhood, geostatistical and variational interpolation methods
[15]
. The most widely applied interpolation methods for RFREM construction found in the literature are: inverse distance weighted (IDW)
[16]
, nearest neighbours (NN), splines
[17]
, natural neighbours (NNI)
[15]
, and modification and derivation of mentioned methods, such as Modified Shepard’s (MSM) method
[18]
, Gradient plus Inverse Distance Squared method (GIDS)
[4]
, and Kriging
[19]
. Among these, Kriging is the most commonly used, since it is a geostatistical best linear unbiased estimator that yields a zero mean residual error and minimizes the error variance.
Direct RFREM construction.
 3.1.1. Inverse distance weighted interpolation method (IDW)
The IDWinterpolation considered for RFREM construction in
[15
,
17
,
20

23]
is also referred to as a Shepard’s method. It assumes that signal spatial samples which are close to each another, are more alike than those which are farther apart. To calculate the interpolated signal value
P_{rx}
at the individual RFREM location (
x,y
) it uses a weighted average of the
P_{i}
,
i
= 1,…,
N
measured signal values at locations (
x_{i}
,
y_{i}
) in the surrounding of the location (
x,y
). Each measurement
P_{i}
is weighted with the weight
w_{i}
calculated as the inverse of the distance
d_{i}
between the locations (
x,y
) and (
x_{i}
,
y_{i}
) and raised to the power
p
, which can be any real number. The value
p
controls the decrease rates of weight with a distance. If
p
is equal to 0, the weights’ values are one and no decrease with distance is used. When
p
is equal to 1, the interpolation is called inverse distance weighted, while
p
equal to 2 yields the inverse distance squared weighted (IDW2) interpolation.
 3.1.2. Nearest neighbour method (NN)
The NN interpolation considered in
[20
,
23

26]
is also referred to as proximal interpolation and point sampling. This is one of the computationally most efficient, but also the least accurate interpolation method for constructing RFREM. The interpolated signal value
P_{rx}
at the individual RFREM location (
x,y
) always adopts the value of the closest signal measurement
P_{i}
at location (
x_{i}
,
y_{i}
),
i
=1,…,
N
. A straightforward option to find which signal value is to be adopted at which RFREM location is to calculate Euclidean distances between the interpolating location and locations of the measurements, and select the measurement with the minimum Euclidean distance. One of alternatives is to use methods for constructing Voronoi diagrams
[27]
, also known as Dirichlet tessellations, which define the regions in which all locations adopt the same signal level
P_{i}
as can be seen in
Fig. 5
.
An example of Voronoi diagrams created from spatially distributed signal measurements for the nearest neighbour interpolation.
 3.1.3. Spline method
The Spline method considered in
[15
,
17
,
20
,
28]
is also known as Radial Basis Function (RBF) and “rubber sheeting”. It estimates the signal value
P_{rx}
at the individual RFREM location (
x,y
) by using piecewise defined polynomials called splines, whose coefficients are calculated so as to guarantee a global smoothness between the measurements in all possible pairs formed from the
N
available signal measurements. The most common splines are linear, quadratic and cubic polynomials. The linear splines simply involve forming the consecutive signal values through straight lines between the signal measurements. The quadratic splines go through consecutive measurements whose first derivatives of two splines are continuous at interior points, while the cubic splines produce interpolated signal values that are continuous through to the second derivative.
 3.1.4. Natural neighbour method (NNI)
The NNI method considered in
[15
,
24]
estimates the signal value
P_{rx}
at the individual RFREM location (
x,y
) as a weighted average of
K
from
N
available measurements
P_{i}
at locations (
x_{i}
,
y_{i}
),
i
=1,…,
N
, which fall within the natural neighbourhood of the location (
x,y
). The natural neighbourhood as well as interpolation weights can also be calculated from the Voronoi diagrams, which are applied also in the nearest neighbour interpolation. If we assume the same spatial distribution of signal measurements as in
Fig. 5
and add a new polygon
V_{Prx}
of the interpolating location (
x,y
), the overlapping of polygons for the natural neighbour interpolation method is depicted in
Fig. 6
. In particular, polygons
V_{i}
,
i
=1,…,
K
,
K
=5 represent the natural neighbourhood of the interpolating location (
x,y
) and signal measurements
P_{i}
,
i
=1,…
K
, are the corresponding natural neighbours. The overlapping areas
W_{i}
of the new polygon
V_{Prx}
with polygons
V_{i}
are called local coordinates of the natural neighbourhood. The size of overlapping areas
W_{i}
normalized by the size of
V_{Prx}
represents the interpolation weight for the measurement
i
.
An example of using Voronoi diagrams created from spatially distributed signal measurements for the natural neighbour interpolation.
 3.1.5. Modified Shepard’s method (MSM)
The MSM method considered in
[15
,
21]
is an enhanced inverse distance weighted interpolation based on the mathematical functions for local RFREM approximation. These functions are known as nodal functions. The most common nodal functions are of a quadratic form
[18]
, while the linear form has proved to be more appropriate in the case of RFREM construction
[15]
. The estimated signal value
P_{rx}
at the individual RFREM location (
x,y
) is estimated as a weighted average of nodal functions’ values
Q_{i}
(
x,y
),
i
=1,…,
K
, defined for locations of
K
measurements within the influence area limited by the radius
r_{w}
. For instance, in scenario depicted in
Fig. 7
only two measurements are considered,
P
_{1}
and
P
_{2}
. The coefficients of nodal functions
Q_{i}
are estimated from the measurements within their influence areas limited with the radius
r_{ω}
by fitting individual nodal functions of the same type to all measurements within the individual influence areas in the least squares sense. For example, in the case of measurement
P
_{1}
the nodal function is fitted to measurements
P
_{1}
, and
P
_{4}
, while in the case of measurement
P
_{2}
it is fitted to measurements
P
_{2}
,
P
_{3}
, and
P
_{4}
. The behaviour of the interpolation is controlled by the radii
r_{w}
and
r_{ω}
which can be fixed or variable. The fixed radii are selected according to the desired interpolation smoothness while the variable radii are usually defined by equations, which take into account the number of all available measurements, the maximum Euclidean distance in the measurement set and the expected number of measurements in both influence area types
[29]
.
An example of spatially distributed signal measurements for the representation of the modified Shepard's method.
 3.1.6. Gradient plus inverse distance squared method (GIDS)
The GIDS method considered in
[21
,
30
,
31]
combines the multiple linear regression and inverse distance square weighted interpolation and incorporates elevation as a covariate. The method first fits the linear regression model to
N
closest signal measurements in the least square sense and estimates
x, y
and elevation gradients of the radio signal to estimate the signal value
P_{rx}
at the individual RFREM location (
x,y
). Then, the values of the fitted model at the locations of the measurements are averaged using the inverse distance squared weights to calculate the predicted signal value at the location (
x,y
).
 3.1.7. Kriging method
The Kriging method considered in
[4
,
17
,
20

23
,
32]
is a weighted average interpolation technique. It takes into account both, the distances and the degree of influence between the signal measurements when estimating the signal level
P_{rx}
(
x,y
) at a given RFREM location (
x,y
). The Kriging method determines the weights by minimizing the error variance of the general Kriging linear estimator
[19
,
33]
.
There are various Kriging implementations, largely used in geostatistics
[33]
. The most often considered implementations for the RFREM construction are the ordinary Kriging and the simple Kriging method. Before the Kriging method defines the interpolation weights, a degree of relationship between the signal levels on all RFREM locations is estimated from the
N
available measurements by using a variogram analysis
[19]
. For example, if there are
N
available measurements,
M
=
N
(
N
−1)/2 measurement pairs can be formed and for each the separation or
lag
distance
h
and a semivariance
γ
can be calculated. The scatter plot of
γ
with respect to
h
is called the empirical semivariogram and expresses the spatial autocorrelation between the signal measurements. As it is schematically depicted in
Fig. 8
, the selected mathematical function
f
(
h
) can be fitted to the empirical semivariogram to extract the values of
sill
,
Nugget
and the
Range
. The
sill
is the
γ
at which the semivariogram levels off, the
Range
is the distance at which the semivariogram reaches the
sill
, while the
Nugget
represents variability at distance values smaller than the typical sample spacing, including the measurement error. Next, by using
f
(
h
) the value of
γ
can be estimated at an arbitrary distance between RFREM locations. For example, if
h_{A}
is the distance between the measurement at the location (
x_{A},y_{A}
) and the interpolating location (
x,y
), then
γ_{A}
=
f
(
h_{A}
). If
h_{B}
is the distance between the measurement at the location (
x_{B},y_{B}
) and the interpolating location (
x,y
), then
γ_{B}
=
f
(
h_{B}
). Similarly the
γ
is estimated for any distances between the locations of the measurements e.g. for measurement at the location (
x_{A},y_{A}
) and measurement at the location (
x_{B},y_{B}
),
γ_{AB}
=
f
(
h_{AB}
).
The empirical semivariogram with the fitted mathematical function.
To estimate the signal level
P_{rx}
(
x,y
) at a given RFREM location (
x,y
), the simple Kriging considers all available measurements, while in ordinary Kriging the domain of stationarity of the unknown constant mean is limited to the local neighbourhood window cantered at the location (
x,y
). The local neighbourhood is determined by the
range
of the semivariogram. The
K
closest measurements surrounding the location (
x,y
) with separating distances up to the
range
are retained for the interpolation, while those with distances larger than the
range
are discarded. Finally, the interpolation weights are calculated from all
γ
values obtained from the
f
(
h
) based on the separating distances between the considered measurements and the distances between the considered measurements and the interpolating location.
 3.2. Indirect construction methods
The indirect RFREM construction methods are making use of estimated or known parameters of the transmitter and radio propagation modelling. The procedure is schematically depicted in
Fig. 9
. These methods can be computationally more complex and they are not as common as the direct methods. Nevertheless, they can be efficiently used to describe the RF coverage more realistically, especially in long term information REM scenarios where the RFREM construction time is not of such great importance as in the short term information REM scenarios.
Indirect RFREM construction.
Indirect methods distinguish between scenarios where all, some or none of the parameters of the transmitter are known. In the first case, the RFREM construction is straightforward and performed by calculating the RF signal coverage with a propagation model using known transmitter parameters. This approach is also used for planning wireless networks, but introduces unnecessary errors in coverage prediction if inappropriate propagation model is selected and/or the propagation model is not calibrated by actual signal measurements. In the second case, an efficient estimation of the transmitter location is performed if other parameters of the transmitter such as transmit power, antenna characteristics, etc. are known. After this the approach outlined for the first case can be applied. However, if only the transmitter location is known, other parameters must be estimated before using the selected propagation model. In the last case, the estimation of the transmitter location, its other parameters and, if considered, also calibration of the propagation model are performed before proceeding to RFREM construction with the propagation modelling. The recent research in indirect methods
[1]
follows this idea by proposing the transmitter location estimation based REM construction method (LIvE). Since LIvE can construct more accurate RFREM than the direct Kriging method, it shows further research possibilities in the direction of indirect construction methods.
 3.2.1. LIvE method
The indirect method LIvE
[1]
first estimates the location and the transmit power of transmitter taking into account the propagation channel properties and subsequently uses the estimated values for the RFREM construction. It considers the logdistance path loss propagation model and assumes that propagation channel parameters of the operating area i.e. path loss exponent factor
α
and the path loss correction factor
P
_{L0}
, are known. The received power at
N
available measurement locations (
x_{i},y_{i}
),
i
=1,…,
N
, from unknown transmitter location is written as the optimization problem
A
Θ=
b
, which is solved in the least squares sense to obtain the location and estimated transmit power of the transmitter. Then this information is used to estimate signal levels on individual RFREM locations (
x,y
) using the considered propagation model.
 3.2.2. SNRaided method
Similar method as LIvE called the SNRaided method is proposed in
[34]
. It is a lowcost, highprecision localization method for the RFREM construction, operating without any prior knowledge of the interference source other than the transmitter power. In the first step it estimates the angles of arrival at the locations of the measurements and combines them by the received signal powers. Next, the SNRaided fusion is performed with different algorithms. By having both, location of the transmitter and its transmit power, finally any suitable propagation model can be used to construct the RFREM.
 3.2.3. Indirect RFREM construction in indoor environments
An example of indirect RFREM construction assuming known transmitter location and transmit power is studied in
[35]
. The considered method was tested by the help of real testbed that allowed studying the characterization and modelling of the radio indoor environment based on spectrum measurements from heterogeneous spectrum sensors. By considering modified logdistance propagation model, the observed phenomena strongly indicated that development of general radio environment map solutions for indoor use are extremely challenging, unless heterogeneity of spectrum sensors and nonlinearity of propagation conditions is considered.
 3.3. Hybrid construction methods
The hybrid methods for constructing RFREM combine the approaches of direct and indirect construction methods, trying to strike the best tradeoff between their advantages and disadvantages. As such, they can construct very accurate RFREM at the expense of combined complexity. For example, the hybrid method proposed in
[24]
first uses NN method, two dimensional linear (LIN) interpolation method or NNI method to interpolate measurements into an image, which in the case of direct methods already forms the RFREM layer. This image is further processed by selected image processing techniques, in order to identify propagation and transmitter features. These are eventually used with propagation modelling to construct the final RFREMlayer. The method can extract the transmitter position, the antenna pattern and propagation model features, but introduces errors in case of shadowed operating environment.
A different method is proposed in
[36]
, where at first a preliminary RFREM is constructed by a simple numerical propagation modelling, which is in the next step corrected according to the available measurements with the Kriging interpolation with an external drift (KED)
[33]
. This method only operates with preknown parameters of the transmitter. It can be further enhanced by filtering smallscale variations in measurements, but it has problems with measurement outliers.
4. Discussion and further research possibilities
As shown in Section 3 there are many existing methods for constructing the RFREM layer to estimate the coverage of an area with the radio signal. Each has its own characteristics which, besides the quality of the input data, affect the accuracy and suitability of constructed RFREM. Before identifying further research possibilities and challenges for construction of RFREM we will thus group and compare the existing direct and indirect methods as per increasing asymptotical computationaltime complexity. For the latter we assume there are
N
measurements available in a given time moment and
M
locations in RFREM at which we need to estimate signal levels. Furthermore, we assume both values being very large, i.e.
M,N
→∞, but generally having more RFREM locations than available measurements, i.e.
M
>
N
. Following the discussion, the advantages, disadvantages and computationaltime complexity will be summarized in
Table 1
for direct and indirect methods, giving also indications for combined complexity and achievable benefits by combinations in different hybrid methods.
Characteristics of the surveyed construction methods
^{*} M, N→∞,M>N M  no. of estimating RFREM locations P  order of the spline function N  no. of measurements p – no. of unknowns in linear system of equations
One of computationally low complex methods is NN. Its complexity is
0
((
M
+
N
)log
N
), which can be reduced to
0
(
M
log
N
)
[4]
. The NN method operates well with uniformly distributed measurements and it is most effective in filling the small number of missing signal values. It poorly extrapolates signal values outside the limits found in the measurement set and assumes uniform properties for large RFREM areas. This results in sharp transitions between the individual signal level zones. The constructed RFREM is thus not smooth and tends to increase noise at boundaries.
The MSM and GIDS methods have the same complexity as NN, i.e.
0
(
M
log
N
) , since their highest complexity source is the nearest neighbour search
[4]
. The MSM method can eliminate or reduce the “bull’seye” effect of signal levels being estimated well only in the surroundings of the measurement locations. Unlike the NN method it can perform extrapolation of signal values beyond the limits found in the measurement set, but introduces degradation in the performance if measurements lie in a lowdimensional subspace. The GIDS method can take into account signal level gradients and elevation of the terrain at the interpolated location and at locations of the measurements. The method is very sensitive to the size of a manually selected local neighbourhood of the interpolated location. If it is too small, it can leave out significant measurements, whereas if it is too large, it can introduce noise.
The NNI method relies on automatic definition of a local neighbourhood. It has complexity proportional to
0
(
M
(
N
+
k
) log
N
)
[37]
, where
k
is the number of natural neighbours of the interpolated location. This method performs well also with nonhomogeneous distribution of measurements. Its drawback is that it cannot extrapolate signal values outside the convex hull, defined by the locations of measurements.
The IDW method has complexity proportional to
0
(
MN
)
[4]
. It is most efficient with uniformly distributed measurements and can be used as a smoothing interpolator. Its main disadvantages are the production of the “bull’seyes” effect, sensitivity to the measurement outliers and introduction of errors in case of spatially nonuniform distribution of measurements. Similar as the NN method, the IDW method cannot extrapolate signal values beyond the limits found in the measurement set. There is also no way of finding in advance which weighting power factor will construct the most accurate RFREM.
The spline method has complexity
0
(
MNP
^{2}
)
[38]
, where
P
is the spline order. It is particularly suitable for constructing relatively smooth RFREM from several signal measurements in case of faintly varying signal levels. The method can capture trends in signal variations and perform extrapolation, similar as the MSM method. It is sensitive to measurement outliers as the IDW method and fails when measurements are closely clustered and have extreme differences in values.
Relatively high computationally complex among presented direct methods is the ordinary Kriging method with complexity
0
(
MN
^{2}
)
[4]
. This is an exact interpolation method unless the semivariogram has a nugget effect, i.e. a discontinuity at the origin. In such case Kriging poorly reproduces the shortscale signal variability by underestimating signal extremes. The main drawbacks of Kriging are the requirement for high number of measurements for achieving high precision and the need for interaction with a user to achieve best fit of the selected function to the semivariogram.
Indirect construction methods are in general similar or more complex than the direct methods. The SNRaided method and the Indirect indoor method have complexity proportional to
0
(
Np
^{2}
)
[4]
due to least squares regression algorithm applied in those methods. The SNRaided method can improve the localization accuracy of the transmitter if individual MCDs sense signal levels below the required accuracy. However, its drawback is that MCDs have to be equipped with two antennas. The Indirect indoor method applies semiempirical propagation model tuning to the measurements as it assumes operation with preknown transmitter parameters. Due to the selection of considered propagation model it is adapted only for indoor operation.
LIvE method has complexity
0
(
MN
^{2.376}
), if it is optimized with the CoppersmithWinograd algorithm
[23]
. It was showed to outperform IDW, IDW2 and the Kriging methods in a lognormal shadowing and Rayleigh fading environment
[1]
. However, the method assumes empirical propagation model, which represents the general statistical radio channel behaviour. This model is not completely valid for an arbitrary environment, where an obstacle can cause significant disagreement between measured and estimated signal levels. For that reason deterministic and semiempirical propagation models are more often considered in practical calculation of the signal coverage
[39]
. The main drawbacks of the LIvE method are inability to model the impact of antenna pattern and the assumption that the exact information is available for the adaptation of empirical propagation model to the operating environment. The latter is very rare or hard to obtain in practical scenarios and for the best performing propagation models demands finetuning to the particular operating environment.
From the characteristics of the surveyed methods it can be seen that they are largely dependent on spatial distribution of considered signal measurements. This can theoretically be uniform, gridbased, adaptive, random and clustered
[40]
. In practice, uniform and gridbased distribution cannot be easily achieved due to physical limitations of the operating environment. Adaptive distribution of measurements assumes more measurements at locations with more variability in the signal levels, which requires prior knowledge of the distribution of signal levels. However, if such prior knowledge is readily available, there is no need to construct the RFREM. Consequently, a good method for constructing an accurate RFREM must support operation with (pseudo) random and clusterbased distribution of measurements. Furthermore, its operation should not be affected by the measurement outliers and it must be able to estimate signal levels comparably at all RFREM locations with moderate computational effort. Direct methods hardly encompass multiple of these features. Also, as shown for the LIvE method, some indirect methods can already outperform some of the direct methods. In the light of increasingly computationally capable devices this opens further research opportunities in the direction of indirect and hybrid RFREM construction methods. To this end, the investigation of indirect methods considering characteristics of the operating environment and of the transmitter along with an appropriate nonempirical propagation model appears particularly promising. With respect to the latter, one can choose between deterministic and semiempirical propagation models. The deterministic models require detailed knowledge of the operating environment geometry and are computationally very demanding. In contrary, semiempirical models are characterised by moderate complexity
[39]
and can be readily considered for indirect RFREM construction.
The majority of research in the fields of REM and cognitive radio networking has been focused on efficient usage of radio spectrum in TVWS. However, as pointed out in the introduction, the potential application of REM goes far beyond this. They are opening opportunities for using REM also at other frequency bands, especially in ISM bands, frequency bands allocated to mobile operators, radars, aviation, army, earth observation, etc. These new application areas are also putting forward some new requirements and research issues for building the RFREM layer, including:

• The analysis of how different number, quality and distribution of measurements influence the RFREM construction.

• The selection of the most appropriate propagation model for particular indirect or hybrid RFREM estimation.

• Discovering the effect of antenna pattern, elevation angle and azimuth on the RFREM.

• RFREM calculation for single frequency radio networks consisting of a large number of transmitters operating at the same frequency.

• RFREM construction for highly dynamic radio environment.

• Efficient parallel implementation for RFREM construction on platforms such as multicore central processing units (CPUs), digital signal processors (DSPs), fieldprogrammable gate arrays (FPGAs) or graphics processing units (GPUs).

• RFREM construction based on spectrum sensing using heterogeneous MCDs.
5. Conclusion
Initially, REM has been incepted and promoted mainly as a support to early adoption of the cognitive radio concept until end user terminals are capable of autonomous spectrum sensing in accordance with the regulatory requirements. Now it is being increasingly positioned as a comprehensive structure used for planning and managing wireless networks, promising to support the provision of runtime context awareness. The latter is becoming an imperative for the operation of smart devices and applications. In this paper we presented the concept and structure of REM, we outlined its main content layers and highlighted the RFREM layer. We focused on the REM construction which can be in the most basic form represented as the RFREM construction. RFREM can be constructed with different methods which are generally classified as direct, indirect and hybrid methods. Regardless of the particular type, these methods are concerned with estimating the signal levels on geographical locations where distributed signal measurements are not available. We surveyed the most commonly used or referred existing RFREM construction methods of each category, we briefly outlined their operation and directed an interested reader to the relevant literature on REM and its construction. We also analysed the relative advantages and disadvantages of the presented methods, focusing on their suitability for the use in real operating environment with specific distribution of signal measurements and on their computational complexity. We concluded with the recommendation that for obtaining an accurate RFREM the selected construction method must in the best case support operation with spatially (pseudo)random and clustered signal measurements, its operation should not be notably affected by the outliers of the signal measurements, and it must estimate the signal level comparably at any location. For runtime operation such method should have moderate computational complexity, but this is very relative requirement considering the increasing computational capabilities of contemporary end user devices. Consequently, we expect the main further improvements related to the REM construction in the direction of new and enhanced indirect construction methods supporting the abovementioned features. In particular, indirect RFREM construction method with semiempirical propagation modelling and consideration of the operating environment and transmitter characteristics appears as computationally manageable solution that could significantly enhance the accuracy of the constructed RFREMs.
Acknowledgements
This work has been in part funded by the European Union from Social Fund and the FP7 project ABSOLUTE (FP7ICT318632).
BIO
Marko Pesko received B.Sc. degree in Electrical Engineering from the Faculty of Electrical Engineering, University of Ljubljana, Slovenija in 2009. He is employed at Telekom Slovenije and a Ph.D. student at the Jozef Stefan International Postgraduate School. His main research interests cover the area of wireless sensor networks, their integration with mobile networks and Radio Environment Maps (REM) construction. His research is carried out in collaboration with the Department of Communication Systems at the Jozef Stefan Institute.
Tomaž Javornik received B.Sc., M.Sc., and Ph.D. degrees in Electrical Engineering from the University of Ljubljana, Slovenia, in 1987, 1990 and 1993, respectively. He spent six months at the University of Westminster, London, UK, as a visiting scientist. He is currently a senior researcher in the Communication Systems department at the Jozef Stefan Institute, and an assistant professor in the Jozef Stefan International Postgraduate School. His research interests include radio signal propagation channel modeling in terrestrial and satellite communication systems, adaptive coding and modulation, adaptive antenna and MIMO systems, wireless optical communication, cooperative communication, adaptive coding and modulation, relay communication, and selforganizing networks.
Andrej Košir, Ph.D., B.Sc. math is an associate professor at the Faculty of Electrical Engineering, University of Ljubljana. He is active in a broad research fields including: user modeling and personalization, user interfaces and optimization. He has participated to several industrial and European projects. He is a reviewer for projects submitted to SPIRIT technological agency and article submission reviewer in scientific journals.
Mitja Štular graduated from the Faculty of Electrical Engineering and Computer Science of the University of Ljubljana, Slovenia in 1994. He successfully defended his master thesis in 1997 and Ph.D. thesis in 2000. In 2001 he began a career at Mobitel as a consultant to the CEO and also as the UMTS project director and been involved in a variety of research and development projects. In 2006 he took on the position of CTO responsible for networks, services and IT, and in 2009 a position of a Senior Strategy Adviser to the CEO, CSO.
Mihael Mohorčič received B.Sc. (1994), M.Sc. (1998) and Dr.Sc. (2002) degrees in Electrical Engineering from the University of Ljubljana, Slovenia and M.Phil. (1998) degree in Electrical Engineering from the University of Bradford, UK. He has been with the Department of Communication Systems at the Jozef Stefan Institute since 1994, since 2010 holding the position of senior research fellow and head of the department. Since 2006 he has been assistant professor at the Jozef Stefan International Postgraduate School. His main research interests are in wireless access, resource management, crosslayer protocol design and optimization, cognitive radio networks, and wireless sensor networks with smart application scenarios. He is a Senior Member of IEEE.
Yilmaz H. B.
,
Tugcu T.
2013
“Location estimationbased radio environment map construction in fading channels,”
Wireless communications and mobile computing
Haykin S.
2012
Cognitive Dynamic Systems Perceptionaction Cycle, Radar and Radio
Cambridge University Press
New York
ECC
2010
“Technical and operational requirements for the possible operation of cognitive radio systems in the 'white spaces' of the frequency band 470790 MHz,”
ECC Report 159
2012
European FP7 project FARAMIR reports, “Flexible and Spectrum Aware Radio Access through Measurements and Modelling in Cognitive Radio Systems,”
Available:
Zhao Y.
,
Reed J. H.
,
Mao S.
,
Bae K. K.
“Overhead Analysis for Radio Environment Map enabled Cognitive Radio Networks,”
in Proc. of 1st IEEE Workshop on Networking Technologies for Software Defined Radio Networks (SDR '06)
September 2525, 2006
18 
25
2011
IEEE Standard 802.222011, “IEEE Standard for Information technology Local and metropolitan area networks Specific requirements Part 22: Cognitive Wireless RAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Policies and procedures for operation in the TV Bands,”
Sayrac B.
,
Jemaa S. Ben
,
Cordier P.
“Radio Environmental Maps (REMs): A Cognitive Tool for Environmental Awareness,”
Centre Tecnològic de Telecomunicacions de Catalunya (CTTC)
2011
Zhao Y.
,
Reed J. H.
“Radio Environment Map (REM)Enabled Cognitive Radios,”
in Proc. of 16th Annual Wireless Symposium and 2nd Annual Wireless Summer School
June 79, 2006
Atanasovski V.
,
van de Beek J.
,
Dejonghe A.
,
Denkovski D.
,
Gavrilovska L.
,
Grimoud S.
,
Mahonen P.
,
Pavloski M.
,
Rakovic V.
,
Riihijarvi J.
,
Sayrac B.
“Constructing radio environment maps with heterogeneous spectrum sensors,”
in Proc. of 2011 IEEE Int. Symposium on Dynamic Spectrum Access Networks (DYSPAN 2011)
May 36, 2011
660 
661
Zhang L.
,
Zheng G.
2010
“Reliable Information Transmission: A Chaotic SequenceBased Authentication Scheme for Radio Environment Maps Enabled Cognitive Radio Networks,”
Int. Journal of Digital Content Technology and its Applications
4
48 
57
Vizziello A.
,
PerezRomero J.
“System architecture in cognitive radio networks using a radio environment map,”
in Proc. of 4th Int. Conference on Cognitive Radio and Advanced Spectrum Management (CogART ’11)
October 2629, 2011
Zhao Y.
,
Morales L.
,
Gaeddert J.
,
Bae K. K.
,
JungSun U.
,
Reed J. H.
“Applying radio environment maps to cognitive wireless regional area networks,”
in Proc. of 2nd IEEE Int. Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN 2007)
April 1720, 2007
115 
118
van de Beek J.
,
Tao C.
,
Grimoud S.
,
Sayrac B.
,
Mahonen P.
,
Nasreddine J.
,
Riihijarvi J.
2012
“How a layered rem architecture brings cognition to today’s mobile networks,”
IEEE Wireless Communications
19
(4)
17 
24
DOI : 10.1109/MWC.2012.6272419
Subramani S.
,
Riihijarvi J.
,
Sayrac B.
,
Gavrilovska L.
,
Sooriyabandara M.
,
Farnham T.
,
Mahonen P.
“Towards Practical REMbased Radio Resource Management,”
in Proc. of Future Network & Mobile Summit
June 1518, 2011
Denkovski D.
,
Atanasovski V.
,
Gavrilovska L.
,
Riihijärvi J.
,
Mähönen P.
“Reliability of a Radio Environment Map: Case of Spatial Interpolation Techniques,”
in Proc. of 7th Int. Conference on Cognitive Radio Oriented Wireless Networks (CROWNCOM)
June 1820, 2012
248 
253
Shepard D.
“A twodimensional interpolation function for irregularlyspaced data,”
in Proc. of 23rd ACM National conference
August 2729, 1968
517 
524
Azpurua M. A.
,
Ramos K. D.
2010
“A comparison of spatial interpolation methods for estimation of average electromagnetic field magnitude,”
Progress In Electromagnetics Research M (PIER M)
14
135 
145
DOI : 10.2528/PIERM10083103
Renka R. J.
1988
“Multivariate interpolation of large sets of scattered data,”
ACM Transactions on Mathematical Software (TOMS)
14
(2)
139 
148
DOI : 10.1145/45054.45055
Isaaks E. H.
,
Srivastava R. M.
1989
An Introduction to Applied Geostatistics
Oxford University Press
New York
AlayaFeki A. B. H.
,
Jemaa S. Ben
,
Sayrac B.
,
Houze P.
,
Moulines E.
“Informed spectrum usage in cognitive radio networks: interference cartography,”
in Proc. of 2008 IEEE 19th Int. Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2008)
September 1518, 2008
Angjelicinoski M.
,
Atanasovski V.
,
Gavrilovska L.
“Comparative analysis of spatial interpolation methods for creating radio environment maps,”
in Proc. of 19th Telecommunications Forum (TELFOR)
November 2224, 2011
334 
337
Phillips C.
,
Ton M.
,
Sicker D.
,
Grunwald D.
“Practical Radio Environment Mapping with Geostatistics,”
in Proc. of 2012 IEEE Int. Symposium on Dynamic Spectrum Access Networks (DYSPAN 2012)
October 1619, 2012
422 
433
Yılmaz H. B.
,
PhD thesis
2012
“Cooperative spectrum sensing and radio environment map construction in cognitive radio networks,”
Institute for Graduate Studies in Science and Engineering, Bogazici University
PhD thesis
Bolea L.
,
PerezRomero J.
,
Agusti R.
“Received signal interpolation for context discovery in Cognitive Radio,”
in Proc. of 14th Int. Symposium on Wireless Personal Multimedia Communications (WPMC)
October 37, 2011
Bolea L.
,
PerezRomero J.
,
Agusti R.
,
Sallent O.
“Image Processing Techniques as a Support to Transmitter Positioning Determination in Cognitive Radio Networks,”
Sixth Advanced Int. Conference on Telecommunications (AICT 2010)
May 915, 2010
112 
117
Bolea L.
,
PerezRomero J.
,
Agusti R.
,
Sallent O.
“Context Discovery Mechanisms for Cognitive Radio,”
in Proc. of IEEE 73rd Vehicular Technology Conference (VTC2011 Spring)
May 1518, 2011
Riihijarvi J.
,
Mahonen P.
“Exploiting spatial statistics of primary and secondary users towards improved cognitive radio networks,”
in Proc. of 3rd Int. Conference on Cognitive Radio Oriented Wireless Networks and Communications (CrownCom 2008)
May 1517, 2008
Mateos G.
,
Bazerque J. A.
,
Giannakis G. B.
“Splinebased spectrum cartography for cognitive radios”
in Proc. of 2009 IEEE Conference Record of the FortyThird Asilomar Conference on Signals, Systems and Computers
November 14, 2009
1025 
1029
Franke R.
,
Nielson G.
1980
“Smooth interpolation of large sets of scattered data,”
Int. Journal for Numerical Methods in Engineering
15
(11)
1691 
1704
DOI : 10.1002/nme.1620151110
Dagres I.
,
Polydoros A.
,
Riihijärvi J.
,
Nasreddine J.
,
Mähönen P.
,
Gavrilovska L.
,
Atanasovski V.
,
van de Beek J.
,
Sayrac B.
,
Grimoud S.
,
Lopez Benitez M.
,
Perez Romero J.
,
Agusti R.
,
Casadevall F.
2012
“FARAMIR project final report: Flexible and Spectrum Aware Radio Access through Measurements and Modelling in Cognitive Radio Systems,”
Nalder I. A.
,
Wein R. W.
1998
“Spatial interpolation of climatic Normals: test of a new method in the Canadian boreal forest,”
Agricultural and Forest Meteorology
92
(4)
211 
225
DOI : 10.1016/S01681923(98)001026
Mahapatra R.
,
Strinati E. C.
“Interferenceaware dynamic spectrum access in cognitive radio network,”
in Proc. of 2011 IEEE 22nd Int. Symposium on Personal Indoor and Mobile Radio Communications (PIMRC)
September 1114, 2011
396 
400
Goovaerts P.
1997
Geostatistics for Natural Resources Evaluation
Oxford University Press
New York
Sun G.
,
Beek J. v. d.
“Simple distributed interference source localization for radio environment mapping”
2010 IFIP Wireless Days (WD)
October 2022, 2010
Meshkova E.
,
Ansari J.
,
Denkovski D.
,
Riihijarvi J.
,
Nasreddine J.
,
Pavloski M.
,
Gavrilovska L.
,
Mahonen P.
“Experimental Spectrum Sensor Testbed for Constructing Indoor Radio Environmental Maps,”
in Proc. of 2011 IEEE Int. Symposium on Dynamic Spectrum Access Networks (DYSPAN 2011)
May 36, 2011
603 
607
Ould Isselmou Y.
,
Wackernagel H.
,
Tabbara W.
,
Wiart J.
“Geostatistical interpolation for mapping radioelectric exposure levels,”
in Proc. of First European Conference on Antennas and Propagation Conference (EuCAP 2006)
November 610, 2006
Fan Q.
,
Efrat A.
,
Koltun V.
,
Krishnan S.
,
Venkatasubramanian S.
“HardwareAssisted Natural Neighbor Interpolation,”
in Proc. of 7th Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO)
January 22, 2005
111 
120
Kazuo T.
,
Kazuki K.
,
Iwao S.
,
Ryoichi M.
1987
“Computational complexity of spline interpolation,”
Int. Journal of Systems Science
18
(5)
945 
954
DOI : 10.1080/00207728708964021
Fleury B. H.
,
Leuthold P. E.
1996
“Radiowave propagation in mobile communications: an overview of European research,”
IEEE Communications Magazine
34
(2)
70 
81
DOI : 10.1109/35.481300
Gumus K.
,
Sen A.
2013
“Comparison of spatial interpolation methods and multilayer neural networks for different point distributions on a digital elevation model,”
Geodetski vestnik
57
(3)
523 
543
DOI : 10.15292/geodetskivestnik.2013.03.523543