# Distributed Forest Fire Monitoring Using Wireless Sensor Networks

Authors: M. Ángeles Serna; Rafael Casado; Aurelio Bermúdez; Nuno Pereira; Stefano Tennina
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Disaster management is one of the most relevant application fields of wireless sensor networks. In this application, the role of the sensor network usually consists of obtaining a representation or a model of a physical phenomenon spreading through the affected area. In this work we focus on forest firefighting operations, proposing three fully distributed ways for approximating the actual shape of the fire. In the simplest approach, a circular burnt area is assumed around each node that has detected the fire and the union of these circles gives the overall fire’s shape. However, as this approach makes an intensive use of the wireless sensor network resources, we have proposed to incorporate two in-network aggregation techniques, which do not require considering the complete set of fire detections. The first technique models the fire by means of a complex shape composed of multiple convex hulls representing different burning areas, while the second technique uses a set of arbitrary polygons. Performance evaluation of realistic fire models on computer simulations reveals that the method based on arbitrary polygons obtains an improvement of 20% in terms of accuracy of the fire shape approximation, reducing the overhead in-network resources to 10% in the best case.


---

## Body

## 1. Introduction

Forest fires are a common occurrence in several countries all around the world because of the general increase of hot and dry climate conditions and the presence of large forests. In most European countries such as Cyprus, France, Greece, Italy, Portugal, Spain, and Turkey, as well as parts of Africa, Australia, and USA, every summer numerous fires destroy thousands of acres of forests and pose great risks to life and infrastructure during all times of the year. In the United States, there are typically between 60,000 and 80,000 wildfires that occur each year, burning 3 million to 10 million acres of land [1]. According to the Joint Research Centre (JRC), in just one year a total of 323,896 hectares of land has been destroyed in 52,795 fires in France, Greece, Italy, Portugal, and Spain [2].In general, forest fires have a lasting impact on social, environmental, and financial aspects. Socially, catastrophic fires can have an enormous impact with losses of human lives and destruction of properties, thus creating persisting effects on a collective and individual level [3, 4]. Forest fires, especially mega fires, can cause psychopathological disturbances to survivors [5] as well as to firefighters [6]. Environmentally, in [7] novel techniques in environmental pollution analysis clearly demonstrate how air quality can be affected in the short term, while in [8] it is argued that previously burned areas have an increased probability to be burnt again, thus intensifying the catastrophes. On a global scale, forest fires can potentially increase the total carbon footprint [9]. It is therefore imperative that society and local authorities are equipped with necessary systems to act proactively and reactively against forest fires. Strategies of fire prevention, detection, and suppression have varied over the years, and international experts encourage further development of technology and research [10].In this perspective, wireless sensor networks (WSNs) or geosensor networks (GSNs) are being frequently used in disaster management scenarios for promptly detecting and continuously monitoring environmental phenomena, such as toxic plumes, earthquakes, and oil spills [11, 12]. In the context of forest fire management, several recent works proposed the use of WSNs for firefighting [13, 14]. In particular, EIDOS (Equipment Destined for Orientation and Safety) [15, 16] is our novel WSN-based support system proposed for reducing hazardous situations for people working in forest firefighting operations, employing various sensors, aerial vehicles, and mobile devices to set up an information system and assist them when they are not aware of the evolution of the fire in the surroundings. In this case, the goal of the sensor network consists of obtaining a map of the fire that is displayed on the firefighters’ handheld devices.In EIDOS, each network node builds and maintains its own approximation of the forest fire shape, by using the information it gathers from the network, as the fire spreads. To do this, when a node detects the proximity of a fire, it broadcasts a fire detection notification into the network such that all nodes are able to update their local approximation of the fire shape. Therefore, the algorithm to update and maintain this approximation of the fire shape is a central piece of the EIDOS system. In this paper, we will compare innovative and efficient solutions, in the sense that they consume a small amount of resources (memory, computation, and communication) for approximating complex fire shapes.We have developed three different fire approximation models, with different characteristics. In the first model [17], nodes represent the shape of the fire by considering the full set of positions of burnt nodes (i.e., nodes reached by the fire so far and which have sent previously a fire notification event), assuming a circular burning area around each one of such positions. The resulting fire shape will be the union of all of those circular shapes. This approach obtains good approximations, but it has the drawback of requiring the storage and forwarding of every fire event received.To address the bottlenecks detected in the first model, in our second proposal the forest fire is approximated by means of a shape composed of several convex hulls (representing distinct burning areas) that eventually merge themselves as they grow and overlap over the time as the fire spread [18]. In this case, instead of relaying all the received fire events, each node forwards only the “new” events, that is, the events originating by the nodes whose position is not already included in any of the actual hulls. In [19], we proved that this approach greatly helps in saving network resources, since meaningless events coming from nodes that do not contribute in improving the current fire shape are discarded.Finally, along the lines of the latter solution and with the goal of further improving the accuracy of the approximation of the fire shape in realistic scenarios, in this paper we propose a third model, which removes the assumption of convex hull-based shapes and makes use of irregular polygons of arbitrary shape. As we will demonstrate through computer simulations, this method outperforms the classical ones based on convex shapes, while keeping low the impact on the network overhead.The rest of this paper is organized as follows. Next section provides some background on the related works in WSNs-based phenomena monitoring. Section3 describes the architecture and functionality of the EIDOS system. After that, Section 4 formally introduces the fire approximation techniques referred to in this work, along with the new proposed one, while Section 5 presents a detailed performance assessment of them. Finally, concluding remarks and future work directions are given in Section 6.


## 2. Related Work

Lots of proposals addressing the problem of mapping and tracking the contour or boundary of a physical phenomenon by using WSNs can be found in the literature. A comprehensive survey can be found in [20].In [21], one of the earliest works on contour mapping, each network node gathers the measurements sensed by its direct neighbors and uses this information to determine whether it is close to the edge of two inhomogeneous fields. The work proposes three approaches for edge detection. The first approach is a statistical approach, while the other two are based on a high pass filter and a classifier, respectively.The procedure proposed in [22] requires a hierarchical communication structure. Sensor nodes must be able to not only detect local physical properties, such as temperature, but rather measure the properties within a certain distance. This approach is based on the fact that sensor nodes can determine the distance and direction from the border of the observed phenomenon.In [23], the authors present an algorithm for boundary approximation in locally linked sensor networks that communicate with a remote monitoring station. They use Delaunay triangulations and Voronoi diagrams to generate a sensor communication network and to define boundary segments between sensors, respectively. The proposed algorithm identifies boundaries based on differences between neighboring sensor readings and not absolute sensor values.In [24] a cross layer approach for obtaining the contour of the phenomenon is proposed. It incorporates data fusion techniques which use the sensing noise (often negligible), the data quantification error, and the data communication noise. Furthermore, instead of making a hard binary decision, the probability for a sensor node being a contour node is calculated at the local fusion center.Authors of [25] describe a scheme for estimating the boundary of a large-scale phenomenon by aggregating readings along a predefined hierarchical structure within the network.The contour mapping engine (CME) was proposed in [26] in order to build a dynamic contour map by using in-network data processing techniques. In this approach, the network must be divided into clusters. Instead of sending to the sink all the sensor readings, the cluster head at each cluster builds some contour segments and reports them to the sink.The mechanism presented in [27] also relies on a root node for obtaining the phenomenon boundary. Nevertheless, it is particularly interesting, since it incorporates a strategy to minimize overall data communication. In this proposal, sensors exchange information only when the process under study does not proceed as expected. However, it involves programming network nodes with a model of the phenomenon behavior (referred to astiny model). Further proposals focused on reducing the amount of data to send to the sink node during the tracking of a continuous object can be found in [28–31].There are many proposals for representing in a compact way the spatial shape of a phenomenon starting from the set of localizations where its presence has been detected. In [32], authors analyze the use of lines and Bezier curves for approximating a set of data points provided by a WSN. In [33] a set of polygons are used for representing the contour of the phenomenon, being the number of vertices that are employed a user-specified parameter. Some complex analytical frameworks, such asVoronoi diagrams [23],kernel linear regression [34], andGaussian kernel estimation [35] have been also proposed for modeling sensor data.Recently, an algorithm for phenomena tracking has been proposed in [36]. This proposal relies on a complex deformable curve model [37] to maintain an updated representation of the phenomenon. The key idea is that each sensor node is able to detect incremental changes in the phenomenon boundary in its proximity, only by exchanging messages with its neighbors. These changes are then reported to a base station, in charge (again) of aggregating all the information.Although these mechanisms are partly distributed (most of them rely on some clustering technique [38]), to our knowledge, in all of them the participation of a base station is required at some point of the process. As the EIDOS system considers the existence of a base station optional, these proposals are not suitable for us.The work presented in [39] is an exception. In this case, authors propose a completely distributed contour tracking algorithm for the sensor network to maintain contours (or boundaries) of a binary object incrementally as they deform, while guaranteeing that the maintained contours capture the global topological features of the object boundary.


## 3. EIDOS: A System for Forest Fire Management

Disaster management systems face rapidly changing situations by relying on the capability of a (complex) distributed sensor network, deployed over a wide area, to capture and report real time data from a large number of heterogeneous information sources. The final goal of the full system is to provide support for decisions making [11]. Extensive examples of the use of WSNs in such scenarios can be found in [40–44].In this work, we focus on forest firefighting operations and in particular on the EIDOS system [15, 16], which was proposed as a disaster management system to help firefighters to increase their efficacy, while minimizing their risks. The system is based on a large and dense WSN, composed by nodes randomly dropped by aircraft in the surroundings of the area affected by a forest fire, and is able to provide the firefighters with critical information, contributing to enhancing their safety. More in detail, the data collected by the WSN is processed by the network nodes in a fully distributed and collaborative way, with the goal of tracking the position and shape of the active fire boundaries. Finally, this information is always made available to the firefighters, who are equipped with mobile handheld devices.


### 3.1. EIDOS Architecture

EIDOS considers three types of devices, as sketched in Figure1. First, the nodes of the WSN (commonly referred to as “motes”) are basically small computing and storage platforms with wireless radios. They are equipped with sensors able to monitor environmental parameters, such as temperature, pressure, and humidity. Optionally, (some of) these nodes are also equipped with GPS (Global Positioning System) receivers.Figure 1
EIDOS architecture.Besides the motes, the firefighters are directly involved in fire extinction activities and carry wireless handheld mobile devices, such as smartphones or tablets, which allow them to communicate with the WSN. The purpose of these devices is to process information in order, for example, to display the fire map by means of a graphical interface. Of course, the connection gateway between the Bluetooth or Wi-Fi technology commonly supported by generic handheld devices and the ZigBee/IEEE 802.15.4 technology usually employed by the WSN should be explicitly addressed. However, this issue is out of the scope of this paper, assuming that they are able to wirelessly interact. Finally, the system incorporates several (possibly unmanned) aerial vehicles, which perform the task of deploying the network over the area of interest.Unlike other similar systems proposing the use of a predeployed sensor network for forest fire detection and monitoring [13, 14, 45–54], we do not explicitly rely on a base station (usually called “sink,” or “gateway”) which gathers the environmental data from the sensor nodes. In other words, the EIDOS system is designed to work correctly, even if there is not connectivity with the sink. For this reason, the base station has not been considered in Figure 1.Next, we detail the behavior of network nodes after their deployment.


### 3.2. Node Deployment and Localization

As stated above, in the EIDOS system the WSN used to build the map of the fire is deployed by dropping motes from the air. This involves several issues, such as atmospheric conditions, aircraft speed and direction, and coverage strategy. As a consequence, the resulting network topology is highly irregular and unknowna priori. Therefore, the first key task of each node in the network consists of determining its own geographical position. This information can be either directly obtained from an on-board GPS receiver or estimated by running a distributed localization algorithm.A description of the existing localization techniques for WSNs is out of the scope of this work, and can be found in [55–57]. Most of them are based on the existence of some special nodes (calledbeacons oranchors) with known coordinates, which periodically broadcast their position in order to help other nodes (calledblinds) to localize themselves. Differently from the classicalrange-based solutions (e.g., [58]), in EIDOS we have opted for arange-free localization technique, in which blind nodes only use connectivity information to estimate their location [59].In particular, starting from the information each node receives, a fully distributed and iterative process is executed, in which the node’s location estimate is progressively refined as a rectangular area. More in detail, the localization process is started by the beacon nodes, which broadcast their position. Then, each time a node receives a localization estimate, it extends the received area by using a common radio coverage range. After that, it updates its current estimate by intersecting it with extended received area. Then, the new estimate is transmitted again, in order to help other nodes to refine their estimates. All details of this algorithm are in [59] and here we aim to recall that it has been demonstrated that with a very small percentage of anchors equipped with GPS receivers, that is, as low as 2% of the total number of nodes, the position error of the blind nodes falls below the radio range (e.g., <50 meters).


### 3.3. Fire Detection and Dissemination

During normal operation, each noden detecting an approaching fire front triggers a process for broadcasting its position p to the entire network. We assume that each node is able to periodically monitor the local temperature, detecting the arrival of the fire front when the sensed value overcomes a predefined threshold t
d
e
t
e
c
t. The strategy to establish the sampling rate is out of the scope of this work. Additionally, nodes burn at a certain temperature t
b
u
r
n, such that t
b
u
r
n
>
t
d
e
t
e
c
t. In our simulation experiments, we assume that, after reaching t
d
e
t
e
c
t, nodes are able to transmit their position before burning. Otherwise, from the point of view of the mechanisms described in the following section, these nodes simply do not exist.In order to minimize the consumption of network resources and prolong network lifetime, WSN nodes neither maintain any hierarchy nor have preliminary information about the network topology. With these restrictions, for disseminating fire detection events, EIDOS implements a variation of ABBA (Area-based Beaconless Algorithm) [60], an efficient broadcasting mechanism.In particular, our dissemination technique is detailed in [61]: it assumes circular coverage areas and is based on the perimeter covered by the copies of the same message. Basically, a node n cancels the forwarding of a message m
p when the successive copies of m
p
(
m
p
′
,
m
p
′
′
,
…
) completely cover the perimeter of n. Note that it is necessary that each node maintains a queue of messages waiting to be forwarded, along with the perimeter not yet covered by the copies of these messages. Furthermore, to enable the updating of the covered perimeter at the receiver node, messages have to explicitly include the transmitter’s position.Starting from the fire detection events it receives, each node builds and maintains a local approximation of the whole forest fire. The choice of the most appropriate fire representation model is of paramount importance since it will have a huge impact on both (i) the accuracy of the obtained approximations and (ii) the amount of resources required (including computing power, memory, and wireless bandwidth, for each node). Section3 introduces the formal models considered in this work.


## 3.1. EIDOS Architecture

EIDOS considers three types of devices, as sketched in Figure1. First, the nodes of the WSN (commonly referred to as “motes”) are basically small computing and storage platforms with wireless radios. They are equipped with sensors able to monitor environmental parameters, such as temperature, pressure, and humidity. Optionally, (some of) these nodes are also equipped with GPS (Global Positioning System) receivers.Figure 1
EIDOS architecture.Besides the motes, the firefighters are directly involved in fire extinction activities and carry wireless handheld mobile devices, such as smartphones or tablets, which allow them to communicate with the WSN. The purpose of these devices is to process information in order, for example, to display the fire map by means of a graphical interface. Of course, the connection gateway between the Bluetooth or Wi-Fi technology commonly supported by generic handheld devices and the ZigBee/IEEE 802.15.4 technology usually employed by the WSN should be explicitly addressed. However, this issue is out of the scope of this paper, assuming that they are able to wirelessly interact. Finally, the system incorporates several (possibly unmanned) aerial vehicles, which perform the task of deploying the network over the area of interest.Unlike other similar systems proposing the use of a predeployed sensor network for forest fire detection and monitoring [13, 14, 45–54], we do not explicitly rely on a base station (usually called “sink,” or “gateway”) which gathers the environmental data from the sensor nodes. In other words, the EIDOS system is designed to work correctly, even if there is not connectivity with the sink. For this reason, the base station has not been considered in Figure 1.Next, we detail the behavior of network nodes after their deployment.


## 3.2. Node Deployment and Localization

As stated above, in the EIDOS system the WSN used to build the map of the fire is deployed by dropping motes from the air. This involves several issues, such as atmospheric conditions, aircraft speed and direction, and coverage strategy. As a consequence, the resulting network topology is highly irregular and unknowna priori. Therefore, the first key task of each node in the network consists of determining its own geographical position. This information can be either directly obtained from an on-board GPS receiver or estimated by running a distributed localization algorithm.A description of the existing localization techniques for WSNs is out of the scope of this work, and can be found in [55–57]. Most of them are based on the existence of some special nodes (calledbeacons oranchors) with known coordinates, which periodically broadcast their position in order to help other nodes (calledblinds) to localize themselves. Differently from the classicalrange-based solutions (e.g., [58]), in EIDOS we have opted for arange-free localization technique, in which blind nodes only use connectivity information to estimate their location [59].In particular, starting from the information each node receives, a fully distributed and iterative process is executed, in which the node’s location estimate is progressively refined as a rectangular area. More in detail, the localization process is started by the beacon nodes, which broadcast their position. Then, each time a node receives a localization estimate, it extends the received area by using a common radio coverage range. After that, it updates its current estimate by intersecting it with extended received area. Then, the new estimate is transmitted again, in order to help other nodes to refine their estimates. All details of this algorithm are in [59] and here we aim to recall that it has been demonstrated that with a very small percentage of anchors equipped with GPS receivers, that is, as low as 2% of the total number of nodes, the position error of the blind nodes falls below the radio range (e.g., <50 meters).


## 3.3. Fire Detection and Dissemination

During normal operation, each noden detecting an approaching fire front triggers a process for broadcasting its position p to the entire network. We assume that each node is able to periodically monitor the local temperature, detecting the arrival of the fire front when the sensed value overcomes a predefined threshold t
d
e
t
e
c
t. The strategy to establish the sampling rate is out of the scope of this work. Additionally, nodes burn at a certain temperature t
b
u
r
n, such that t
b
u
r
n
>
t
d
e
t
e
c
t. In our simulation experiments, we assume that, after reaching t
d
e
t
e
c
t, nodes are able to transmit their position before burning. Otherwise, from the point of view of the mechanisms described in the following section, these nodes simply do not exist.In order to minimize the consumption of network resources and prolong network lifetime, WSN nodes neither maintain any hierarchy nor have preliminary information about the network topology. With these restrictions, for disseminating fire detection events, EIDOS implements a variation of ABBA (Area-based Beaconless Algorithm) [60], an efficient broadcasting mechanism.In particular, our dissemination technique is detailed in [61]: it assumes circular coverage areas and is based on the perimeter covered by the copies of the same message. Basically, a node n cancels the forwarding of a message m
p when the successive copies of m
p
(
m
p
′
,
m
p
′
′
,
…
) completely cover the perimeter of n. Note that it is necessary that each node maintains a queue of messages waiting to be forwarded, along with the perimeter not yet covered by the copies of these messages. Furthermore, to enable the updating of the covered perimeter at the receiver node, messages have to explicitly include the transmitter’s position.Starting from the fire detection events it receives, each node builds and maintains a local approximation of the whole forest fire. The choice of the most appropriate fire representation model is of paramount importance since it will have a huge impact on both (i) the accuracy of the obtained approximations and (ii) the amount of resources required (including computing power, memory, and wireless bandwidth, for each node). Section3 introduces the formal models considered in this work.


## 4. Forest Fire Approximations

This section details the different models for approximating forest fires with WSNs. For each fire approximation, we will present some definitions that formally describe it. They provide a theoretical framework for the implementation of the algorithm executed by every network node in order to obtain the fire model and update it as the fire spreads. Due to space constraints, implementation details are skipped.


### 4.1. Circle-Based Model

The first approach consists of representing the fire by means of a set of circles generated around the position of each node detecting the fire [17]. To achieve it, each network node stores all the fire positions received from its neighbors and forwards them (unless they are discarded by the dissemination process policy [61]). In this way, nodes approximate the forest fire assuming that it is flared up and currently burning in the surroundings of the collected positions. Next, we formally define the shape considered for the approximation.Definition 1 (point).
A pointp
∈
R
2 is a position of the 2D plane with coordinates (
p
x
,
p
y
).Definition 2 (distance between points).
Given two pointsa
,
b
∈
R
2, the Euclidean distance between them is provided by the function distance as follows: R
2
×
R
2
→
R, denoted by D
i
s
t
a
n
c
e
(
a
,
b
) and defined as(1)
Distance
a
,
b
=
a
x
-
b
x
2
+
a
y
-
b
y
2
.Definition 3 (circle).
Given a pointp
∈
R
2 and a value r
∈
R, then c
p
r
∈
R
2
×
R denotes the area delimited by a circle centered at p with radius r.Definition 4 (fire spread function).
LetF
=
(
℘
(
R
2
)
×
R
2
,
R
) be the set of functions from ℘
(
R
2
)
×
R
2 to R. Given a set of points P
∈
℘
(
R
2
) and a point p
∈
P, then a function FireSpread ℘
(
R
2
)
×
R
2
→
R, denoted by F
i
r
e
S
p
r
e
a
d
(
P
,
p
) or F
(
P
,
p
) (or simply F
∈
F), will provide a radius for a circle representing the fire spread at point p.Definition 5 (circle-based shape).
Given a set of pointsP
∈
℘
(
R
2
) and a fire spread function F
∈
F, then the function GetShape ℘
(
R
2
)
×
F
→
℘
(
R
2
×
R
), denoted by G
e
t
S
h
a
p
e
(
P
,
F
) or S
P
F, obtains a shape verifying that ∀
p
∈
P, c
p
F
(
P
,
p
)
∈
S
P
F.
Figure2 shows an example of a circle-based shape.Figure 2
A circle-based shapeS
{
a
,
b
,
c
}
F, represented by the shadowed area. Additional points may be analyzed to determine if they are inside the shape. In this example, I
n
s
i
d
e
(
S
{
a
,
b
,
c
}
F,d
)
=
f
a
l
s
e, while I
n
s
i
d
e
(
S
{
a
,
b
,
c
}
F
,
e
)
=
t
r
u
e (since D
i
s
t
a
n
c
e
(
b
,
e
)
≤
F
(
{
a
,
b
,
c
}
,
b)).Definition 6 (belonging function).
Given a circle-based shapeS
P
F and a point a
∈
R
2, the function Inside ℘
(
R
2
×
R
)
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
P
F
,
a
), is defined by(2)
Inside
S
P
F
,
a
=
true
,
if
∃
c
b
r
∈
S
P
F
∣
Distance
a
,
b
≤
r
false
,
in other case.Given a shape and an arbitrary location, this function provides a way for deciding whether that location is burning or not. Examples of application of this function are shown in Figure 2.


#### 4.1.1. Fire Spread Functions

Different criteria can be used for defining the fire spread function. The simplest criterion consists of considering a constant radiusr for every circle in the shape. The fire spread function is F
(
P
,
p
)
=
r, and the resulting shape may be denoted as S
P
r. Figure 3 shows an example. We refer to this model ashomogeneous shapes.Figure 3
A homogeneous shapeS
{
a
,
b
,
c
}
r. The fire spread function applied is F
(
{
a
,
b
,
c
}
,
p
)
=
r.Alternatively, each network node receiving a new fire pointp
∈
P can determine the radius r for a new circle c
p
r for the shape as function of the fire density in a particular neighboring area. This density is computed starting from the amount of fire points currently included in the shape and formally defined in the following.Definition 7 (neighborhood).
Given a set of pointsP
∈
℘
(
R
2
) and a circular area c
a
n
∈
R
2
×
R, the subset of those points that are located inside this area is defined by the function GetNeighborhood ℘
(
R
2
)
×
(
R
2
×
R
)
→
℘
(
R
2
), denoted by G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
), which verifies the following:(1)
GetNeighborhood(
P
,
c
a
n
)
⊆
P.
(2)
∀
p
∈
P
∣
D
i
s
t
a
n
c
e
(
p
,
a
)
≤
n, then p
∈
G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
).This is a noninjective function. Consequently, it is not possible to recover the original set P starting from G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
). Additionally, it is surjective, so that a randomly selected collection of points may represent a neighborhood.Definition 8 (area density).
Given a set of pointsP
∈
℘
(
R
2
) and a circular area c
a
n
∈
R
2
×
R, the function Density ℘
(
R
2
)
×
(
R
2
×
R
)
→
R, is defined as(3)
Density
P
,
c
a
n
=
GetNeighborhood
P
,
c
a
n
π
n
2
.Starting from the previous definitions, the fire spread function may provide big circles covering less dense areas and smaller circles as point density increases. Figure 4 shows some examples.Figure 4
Examples of heterogeneous shapes based on fire density (a) and node density (b). Shapes are represented by shadowed areas. Black points represent nodes detecting fire. White points represent the rest of network nodes. In (a), the biggest circle corresponds to pointc due to G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
c
n
)
=
{
c
}. One of the smallest circles corresponds to point d, due to G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
d
n
)
=
{
a
,
d
,
e
,
f
,
g
,
h
}.
(a)
(b)Theseheterogeneous shapes based on fire density may be computed by each destination node (or handheld device carried by a firefighter) as fire points are received. Given a prefixed radius n for the neighborhood, according to [17], two options for the fire spread function are an inverse linear behavior F
(
P
,
p
)
=
A
-
B
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
) and a logarithmic behavior F
(
P
,
p
)
=
A
+
B
l
n
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
).A straightforward improvement of this approach consists of computing the area density by considering all the deployed network nodes, even those nodes which have not reported fire, yet. In this way, the previous definitions applied to fire density can be directly translated to node density.We can see the benefits of this improvement by comparing Figures4(a) and 4(b). In the new approximation (Figure 4(b)), the size of the shaded circular area centered on point a has been considerably reduced, since G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
)
=
{
a
,
b
,
d
,
i
,
j
,
k
,
l
}. However, given that each network node does not store information about the entire topology (it is only able to know about its direct neighbors), this approach involves that density values are determined by the nodes detecting the fire, instead of being computed by the nodes receiving the corresponding notification (as before). As a consequence, the dissemination mechanism should support the propagation of this information through the network.


### 4.2. Hull-Based Model

In this subsection we describe a second proposal for modeling forest fires, based on a shape composed of a collection of convex hulls (from now on, only “hulls”) [18, 62]. The advantage of this approach is that each node only considers those fire positions received which would imply a variation in the local approximation, ignoring the rest of fire events. Consequently, the amount of data stored and disseminated through the network is significantly reduced.Definition 9 (relative position among points).
Given three pointsa, b, and c
∈
R
2, the relative position (clockwise,counter clockwise, orin line) among them is provided by the function Order R
2
×
R
2
×
R
2
→
{
C
W
,
C
C
W
,
L
I
N
E
}, denoted by O
r
d
e
r
(
a
,
b
,
c
) and defined by(4)
Order
a
,
b
,
c
=
CW
,
if
det
⁡
a
,
b
,
c
<
0
CCW
,
if
det
⁡
a
,
b
,
c
>
0
LINE
,
if
det
⁡
a
,
b
,
c
=
0
,
where det⁡
a
,
b
,
c
=
1
a
x
a
y
1
b
x
b
y
1
c
x
c
y
.An example of application of this function is shown in Figure 5.Figure 5
Relative position of three points. Given the spatial distribution of pointsa, b, c, and d, then O
r
d
e
r
(
a
,
b
,
c
)
=
C
W and O
r
d
e
r
(
a
,
b
,
d
)
=
C
C
W. In the same way, O
r
d
e
r
(
a
,
c
,
b
)
=
C
C
W, O
r
d
e
r
(
a
,
d
,
b
)
=
C
W, and O
r
d
e
r
(
c
,
d
,
a
)
=
C
C
W. Similarly, O
r
d
e
r
(
a
,
b
,
a
)
=
O
r
d
e
r
(
a
,
b
,
b
)
=
L
I
N
E.Definition 10 (hull function).
Given a set of pointsP
∈
(
R
2
), the function GetHull ℘
(
R
2
)
→
℘
(
R
2
), denoted by G
e
t
H
u
l
l
(
P
) or H
P, verifies the following: (1)
H
P
⊆
P.
(2)
∀
a
∈
H
P, ∃
b
∈
H
P
∣
∀
p
∈
P, O
r
d
e
r
(
a
,
b
,
p
)
∈
{
C
W
,
L
I
N
E
}.
(3)
∀
a
∈
H
P, ∃
b
∈
H
P
∣
∀
c
∈
H
P, O
r
d
e
r
(
a
,
b
,
c
)
=
C
W.An example of application of this function is shown in Figure 6(a).Figure 6
(a) Hull obtained from a set of points. GivenP
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
,
i
,
j
}, then H
P
=
{
a
,
b
,
d
,
e
,
g
,
h
,
i
} (black points). (b) Set of points enclosed by a hull. Given P
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
,
i
,
j
} and a hull H
=
{
a
,
c
,
f
,
g
,
h
,
i
}, then E
n
c
l
o
s
e
d
(
P
,
H
)
=
{
a
,
c
,
f
,
g
,
h
,
i
,
j
} (black points).
(a)
(b)GetHull is a noninjective function. Consequently, it is not possible to recover the original setP starting from G
e
t
H
u
l
l
(
P
). Additionally, it is nonsurjective, so that a randomly selected collection of points does not necessarily represent a hull. For this reason, we introduce the next definition.Definition 11 (hull).
A set of pointsH
∈
℘
(
R
2
) is a hull if it verifies that G
e
t
H
u
l
l
(
H
)
=
H.Definition 12 (enclosed set).
Given a set of pointsP
∈
℘
(
R
2
) and a hull H
∈
℘
(
R
2
), the function Enclosed ℘
(
R
2
)
×
℘
(
R
2
)
→
℘
(
R
2
), denoted by E
n
c
l
o
s
e
d
(
P
,
H
), verifies the following: (1)
E
n
c
l
o
s
e
d
(
P
,
H
)
⊆
P.
(2)
∀
p
∈
P
∣
∀
a
∈
H, ∃
b
∈
H
∣
O
r
d
e
r
(
a
,
b
,
p
)
=
C
W, then p
∈
E
n
c
l
o
s
e
d
(
P
,
H
).Enclosed is a noninjective function since although it is possible to recover the original set H starting from E
n
c
l
o
s
e
d
(
P
,
H
), it is not possible to recover the original set P. Additionally, it is a surjective function. Therefore, given any random set of points, there is a hull enclosing it. An example of application of this function is shown in Figure 6(b).Definition 13 (hull-based shape).
Given a set of pointsP
∈
℘
(
R
2
) and a value d
∈
R, the function G
e
t
S
h
a
p
e
℘
(
R
2
)
×
R
→
℘
(
℘
(
R
2
)
), denoted by G
e
t
S
h
a
p
e
(
P
,
d
) or S
P
d, verifies the following: (1)
∀
H
∈
S
P
d, H
⊆
P
∧
H is a hull.
(2)
∀
H
∈
S
P
d, ∀
Q
1, Q
2
∣
Q
1
∪
Q
2
=
E
n
c
l
o
s
e
d
(
P
,
H
)
∧
Q
1
∩
Q
2
=
⌀, ∃
a
∈
Q
1
∣
∃
b
∈
Q
2 that verifies D
i
s
t
a
n
c
e
(
a
,
b
)
<
d.
(3)
∀
H
1, H
2
∈
S
P
d, H
1
∩
H
2
=
E
n
c
l
o
s
e
d
(
P
,
H
1
)
∩
E
n
c
l
o
s
e
d
(
P
,
H
2
).
(4)
∀
H
1, H
2
∈
S
P
d, ∀
a
,
b
∈
P, a
∈
H
1
∧
a
∉
H
2
∧
b
∉
H
1
∧
b
∈
H
2
⇒
D
i
s
t
a
n
c
e
(
a
,
b
)
>
d
(5)
∀
p
∈
P, ∃
H
∈
S
P
d
∣
p
∈
E
n
c
l
o
s
e
d
(
P
,
H
).GetShape is a noninjective function. Consequently, it is not possible to recover the original set P starting from S
P
d. Additionally, it is nonsurjective, so that a randomly selected collection of points does not necessarily represent a shape. An example of application of this function is shown in Figure 7.Figure 7
Set of points enclosed by a hull-based shape. Given a spatial distribution forP, the amount of hulls provided by GetShape depends on the applied threshold distance. (a) and (b) show results for two different values, d
1 and d
2, assuming that d
1
<
d
2. Hulls are represented by linked black points. Points not belonging to any hull are represented by white points. Independently of the value of the threshold distance, all the points of P are enclosed into some hull.
(a)
G
e
t
S
h
a
p
e
(
P
,
d
1
)
=
{
H
1
,
H
2
,
H
3
,
H
4
}
(b)
G
e
t
S
h
a
p
e
(
P
,
d
2
)
=
{
H
1
,
H
5
,
H
6
}Given a hull-based shape representing a fire, the next function may be applied to determine whether an arbitrary location is burning or not.Definition 14 (belonging function).
Given a shapeS
P
d and a point p
∈
R
2, the function Inside ℘
(
℘
(
R
2
)
)
×
R
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
P
d
,
p
), verifies the following: (5)
Inside
S
P
d
,
p
=
true
,
if
S
P
d
=
S
P
∪
p
d
false
,
in other cases.


### 4.3. Polygon-Based Model

The main contribution of the current work is a fire representation model based on arbitrary polygons, which is described in this subsection.We first formally define the concept of a polygon-based shape, that is, a contour composed of several closed chains of vertices connected by segments. After that, we will introduce the criterion used to determine if a specified position of the plane is covered (or not) by a given shape.


#### 4.3.1. Polygon-Based Shapes

Definition 15 (vertex).
LetV be the set of vertices. Given a vertex p
∈
V, the function Position V
→
R
2, denoted by P
o
s
i
t
i
o
n
(
p
)
=
P, provides the 2D position of the vertex. This is a noninjective function since multiple overlapped vertices p
1
,
p
2
…
p
n may be located at the same point, that is, P
o
s
i
t
i
o
n
(
p
1
)
=
P
o
s
i
t
i
o
n
(
p
2
)
=
⋯
=
P
o
s
i
t
i
o
n
(
p
n
)
=
P. In this case, all vertices are referred to asclones.For the sake of clarity, we will use circles labeled with capital letters for representing points and we will represent vertices by means of misplaced boxes labeled with small letters with numerical subscripts used to distinguish among clones (see, e.g., Figure8).Figure 8
Example of a polygon-based shapeS
=
{
[
a
b
c
]
[
d
1
e
2
f
g
h
i
j
k
l
]
[
d
2
m
n
e
1
]
[
o
]
}. Boxes help us to distinguish among several cloned vertices (placed into the same location). For clarity, segment o
o (with null length) has been drawn as a curved vector starting and ending at the same point.Definition 16 (sequence functions).
LetF
=
(
℘
(
V
)
×
V
,
V
) be the set of functions from ℘
(
V
)
×
V to V. Given a set of vertices V
⊂
V and a vertex v
∈
V, the function next ℘
(
V
)
×
V
→
V, denoted by n
e
x
t
(
V
,
v
), or simply v
⇾, provides the next vertex to v in V, that is, ∀
a
∈
V, a
⇾
∈
V. Similarly, the inverse function prev ℘
(
V
)
×
V
→
V, denoted by p
r
e
v
(
V
,
v
) or v
⇽, provides the previous vertex to v in V, satisfying that ∀
a, b
∈
V
∣
a
⇾
=
b implies that b
⇽
=
a.Definition 17 (polygon-based shape).
Given a set of verticesV
∈
℘
(
V
) and a function n
e
x
t
(
V
,
v
)
∈
F, a shape S
∈
S
=
(
℘
(
V
)
×
F
), denoted by S
(
V
,
n
e
x
t
), or S, is a set of vertices maintaining a relationship of sequence among them.Definition 18 (segment).
Given two verticesa
,
b
∈
V
∣
P
o
s
i
t
i
o
n
(
a
)
=
A and P
o
s
i
t
i
o
n
(
b
)
=
B, the relation a
⇾
=
b will be denoted by a segment a
b and graphically represented by a vector from point A to point B. Consequently, a shape will be represented as a directed graph (as shown in the example of Figure 8).Definition 19 (chain).
Given a shapeS
(
V
,
n
e
x
t
)
∈
S, it may be partitioned in k disjoint ordered subsets C
1
,
C
2
,
…
C
k called chains, verifying the following:(1)
∀
v
∈
S, ∃
C
⊂
S
∣
v
∈
C.
(2)
∀
C
i, C
j
⊂
S, C
i
∩
C
j
=
⌀.
(3)
⋃
i
=
1
k
C
i
=
S.
(4)
∀
C
⊂
S composed of n vertices, denoted by [
v
0
v
1
⋯
v
n
-
1
], it verifies that ∀
i
,
0
≤
i
<
n, v
i
⇾
=
v
(
(
i
+
1
)
m
o
d
n
).Graphically, each chain of the shape is represented as a subgraph composed of a cyclic sequence of n consecutive segments. Note that a chain allows n different notations. Also, when appropriate, irrelevant subchains in a chain are abbreviated by “⋯.”


#### 4.3.2. Coverage Issues

Definition 20 (point of a segment).
Given a pointP
∈
R
2 and a segment a
b
∈
S, we say that P belongs to a
b or P
∈
a
b, if it is verified that(1)
(
P
y
-
A
y
)
(
P
y
-
B
y
)
≤
0,
(2)
A
x
+
(
B
x
-
A
x
/
B
y
-
A
y
)
(
P
y
-
A
y
)
=
P
x.Definition 21 (horizontal semiline).
Given a pointP
∈
R
2, a horizontal semiline y
=
P
y, or P
⟜, is defined ∀
x
>
P
x.Definition 22 (segment crossing a semiline).
Given a shapeS
∈
S, a point P
∈
R
2 defining the semiline P
⟜, and a segment a
b
∈
S, we say that a
b crosses P
⟜ or a
b
⌿
P
⟜, if the following conditions are satisfied:(1)
A
y
≠
B
y.
(2)
A
x
+
(
B
x
-
A
x
/
B
y
-
A
y
)
(
P
y
-
A
y
)
>
P
x.
(3)
(
P
y
-
A
y
)
(
P
y
-
B
y
)
≤
0.
(4)
P
y
≠
m
i
n
(
A
y
,
B
y
).Definition 23 (set of segments crossing a semiline).
Given a shapeS
∈
S and a point P
∈
R
2 defining the semiline P
⟜, the subset of segments of S crossing P
⟜, denoted by X
P
⊂
S, verifies that(1)
∀
a
b
∈
S
∣
a
b
⌿
P
⟜, a
b
∈
X
P,
(2)
∀
a
b
∈
X
P, a
b
⌿
P
⟜.Definition 24 (belonging function).
Given a shapeS
(
V
,
n
e
x
t
)
∈
S and a point P
∈
R
2, the function Inside S
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
,
P
), is defined by(6)
Inside
S
,
P
=
true,
if
∃
a
∈
S
∣
pos
a
=
P
∨
∃
a
b
∈
S
∣
P
∈
a
b
∨
X
P
is odd
false,
in other cases.
X
P indicates thecardinality of X
P, that is, the amount of segments crossing P
⟜. Figure 9 shows an example of the behavior of this function.Figure 9
For the shapeS of Figure 8, I
n
s
i
d
e
(
S
,
U
)
=
f
a
l
s
e, I
n
s
i
d
e
(
S
,
V
)
=
f
a
l
s
e, and I
n
s
i
d
e
(
S
,
W
)
=
t
r
u
e.A WSN deployed over a forest area with the purpose of monitoring the evolution of a wildfire will produce a set of 2D points indicating the presence of fire in the specific locations of certain network nodes. Although the information collected is discrete, the fire spreads continuously over the area. For this reason, the shapes should be “interpolated” starting from the collection of gathered points but by establishing a minimum distance threshold among these points to allow the space “in the middle” to be considered to be actually burning or not. This is formally stated in the next definition.Definition 25 (shape covering a set of points with a distance threshold).
Given a set of pointsQ
∈
℘
(
V
), a shape S
∈
S covers Q with a threshold d if it verifies that(1)
∀
a
∈
S, P
o
s
i
t
i
o
n
(
a
)
∈
Q,
(2)
∀
a
b
∈
S, Distance (
P
o
s
i
t
i
o
n
(
a
)
,
P
o
s
i
t
i
o
n
(
b
)
)
≤
d,
(3)
∀
A
∈
Q, I
n
s
i
d
e
(
S
,
A
)
=
t
r
u
e,
(4)
∀
A, B
∈
Q
∣
D
i
s
t
a
n
c
e
(
A
,
B
)
≤
d, then ∀
P
∈
R
2, I
n
s
i
d
e
(
{
[
a
,
b
]
}
,
P
)
⇒
I
n
s
i
d
e
(
S
,
P
),
(5)
∀
A, B, C
∈
Q
∣
D
i
s
t
a
n
c
e
(
A
,
B
)
≤
d, D
i
s
t
a
n
c
e
(
B
,
C
)
≤
d, and D
i
s
t
a
n
c
e
(
C
,
A
)
≤
d, then ∀
P
∈
R
2, I
n
s
i
d
e
(
{
[
a
,
b
,
c
]
}
,
P
)
⇒
I
n
s
i
d
e
(
S
,
P
).


## 4.1. Circle-Based Model

The first approach consists of representing the fire by means of a set of circles generated around the position of each node detecting the fire [17]. To achieve it, each network node stores all the fire positions received from its neighbors and forwards them (unless they are discarded by the dissemination process policy [61]). In this way, nodes approximate the forest fire assuming that it is flared up and currently burning in the surroundings of the collected positions. Next, we formally define the shape considered for the approximation.Definition 1 (point).
A pointp
∈
R
2 is a position of the 2D plane with coordinates (
p
x
,
p
y
).Definition 2 (distance between points).
Given two pointsa
,
b
∈
R
2, the Euclidean distance between them is provided by the function distance as follows: R
2
×
R
2
→
R, denoted by D
i
s
t
a
n
c
e
(
a
,
b
) and defined as(1)
Distance
a
,
b
=
a
x
-
b
x
2
+
a
y
-
b
y
2
.Definition 3 (circle).
Given a pointp
∈
R
2 and a value r
∈
R, then c
p
r
∈
R
2
×
R denotes the area delimited by a circle centered at p with radius r.Definition 4 (fire spread function).
LetF
=
(
℘
(
R
2
)
×
R
2
,
R
) be the set of functions from ℘
(
R
2
)
×
R
2 to R. Given a set of points P
∈
℘
(
R
2
) and a point p
∈
P, then a function FireSpread ℘
(
R
2
)
×
R
2
→
R, denoted by F
i
r
e
S
p
r
e
a
d
(
P
,
p
) or F
(
P
,
p
) (or simply F
∈
F), will provide a radius for a circle representing the fire spread at point p.Definition 5 (circle-based shape).
Given a set of pointsP
∈
℘
(
R
2
) and a fire spread function F
∈
F, then the function GetShape ℘
(
R
2
)
×
F
→
℘
(
R
2
×
R
), denoted by G
e
t
S
h
a
p
e
(
P
,
F
) or S
P
F, obtains a shape verifying that ∀
p
∈
P, c
p
F
(
P
,
p
)
∈
S
P
F.
Figure2 shows an example of a circle-based shape.Figure 2
A circle-based shapeS
{
a
,
b
,
c
}
F, represented by the shadowed area. Additional points may be analyzed to determine if they are inside the shape. In this example, I
n
s
i
d
e
(
S
{
a
,
b
,
c
}
F,d
)
=
f
a
l
s
e, while I
n
s
i
d
e
(
S
{
a
,
b
,
c
}
F
,
e
)
=
t
r
u
e (since D
i
s
t
a
n
c
e
(
b
,
e
)
≤
F
(
{
a
,
b
,
c
}
,
b)).Definition 6 (belonging function).
Given a circle-based shapeS
P
F and a point a
∈
R
2, the function Inside ℘
(
R
2
×
R
)
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
P
F
,
a
), is defined by(2)
Inside
S
P
F
,
a
=
true
,
if
∃
c
b
r
∈
S
P
F
∣
Distance
a
,
b
≤
r
false
,
in other case.Given a shape and an arbitrary location, this function provides a way for deciding whether that location is burning or not. Examples of application of this function are shown in Figure 2.


### 4.1.1. Fire Spread Functions

Different criteria can be used for defining the fire spread function. The simplest criterion consists of considering a constant radiusr for every circle in the shape. The fire spread function is F
(
P
,
p
)
=
r, and the resulting shape may be denoted as S
P
r. Figure 3 shows an example. We refer to this model ashomogeneous shapes.Figure 3
A homogeneous shapeS
{
a
,
b
,
c
}
r. The fire spread function applied is F
(
{
a
,
b
,
c
}
,
p
)
=
r.Alternatively, each network node receiving a new fire pointp
∈
P can determine the radius r for a new circle c
p
r for the shape as function of the fire density in a particular neighboring area. This density is computed starting from the amount of fire points currently included in the shape and formally defined in the following.Definition 7 (neighborhood).
Given a set of pointsP
∈
℘
(
R
2
) and a circular area c
a
n
∈
R
2
×
R, the subset of those points that are located inside this area is defined by the function GetNeighborhood ℘
(
R
2
)
×
(
R
2
×
R
)
→
℘
(
R
2
), denoted by G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
), which verifies the following:(1)
GetNeighborhood(
P
,
c
a
n
)
⊆
P.
(2)
∀
p
∈
P
∣
D
i
s
t
a
n
c
e
(
p
,
a
)
≤
n, then p
∈
G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
).This is a noninjective function. Consequently, it is not possible to recover the original set P starting from G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
). Additionally, it is surjective, so that a randomly selected collection of points may represent a neighborhood.Definition 8 (area density).
Given a set of pointsP
∈
℘
(
R
2
) and a circular area c
a
n
∈
R
2
×
R, the function Density ℘
(
R
2
)
×
(
R
2
×
R
)
→
R, is defined as(3)
Density
P
,
c
a
n
=
GetNeighborhood
P
,
c
a
n
π
n
2
.Starting from the previous definitions, the fire spread function may provide big circles covering less dense areas and smaller circles as point density increases. Figure 4 shows some examples.Figure 4
Examples of heterogeneous shapes based on fire density (a) and node density (b). Shapes are represented by shadowed areas. Black points represent nodes detecting fire. White points represent the rest of network nodes. In (a), the biggest circle corresponds to pointc due to G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
c
n
)
=
{
c
}. One of the smallest circles corresponds to point d, due to G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
d
n
)
=
{
a
,
d
,
e
,
f
,
g
,
h
}.
(a)
(b)Theseheterogeneous shapes based on fire density may be computed by each destination node (or handheld device carried by a firefighter) as fire points are received. Given a prefixed radius n for the neighborhood, according to [17], two options for the fire spread function are an inverse linear behavior F
(
P
,
p
)
=
A
-
B
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
) and a logarithmic behavior F
(
P
,
p
)
=
A
+
B
l
n
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
).A straightforward improvement of this approach consists of computing the area density by considering all the deployed network nodes, even those nodes which have not reported fire, yet. In this way, the previous definitions applied to fire density can be directly translated to node density.We can see the benefits of this improvement by comparing Figures4(a) and 4(b). In the new approximation (Figure 4(b)), the size of the shaded circular area centered on point a has been considerably reduced, since G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
)
=
{
a
,
b
,
d
,
i
,
j
,
k
,
l
}. However, given that each network node does not store information about the entire topology (it is only able to know about its direct neighbors), this approach involves that density values are determined by the nodes detecting the fire, instead of being computed by the nodes receiving the corresponding notification (as before). As a consequence, the dissemination mechanism should support the propagation of this information through the network.


## 4.1.1. Fire Spread Functions

Different criteria can be used for defining the fire spread function. The simplest criterion consists of considering a constant radiusr for every circle in the shape. The fire spread function is F
(
P
,
p
)
=
r, and the resulting shape may be denoted as S
P
r. Figure 3 shows an example. We refer to this model ashomogeneous shapes.Figure 3
A homogeneous shapeS
{
a
,
b
,
c
}
r. The fire spread function applied is F
(
{
a
,
b
,
c
}
,
p
)
=
r.Alternatively, each network node receiving a new fire pointp
∈
P can determine the radius r for a new circle c
p
r for the shape as function of the fire density in a particular neighboring area. This density is computed starting from the amount of fire points currently included in the shape and formally defined in the following.Definition 7 (neighborhood).
Given a set of pointsP
∈
℘
(
R
2
) and a circular area c
a
n
∈
R
2
×
R, the subset of those points that are located inside this area is defined by the function GetNeighborhood ℘
(
R
2
)
×
(
R
2
×
R
)
→
℘
(
R
2
), denoted by G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
), which verifies the following:(1)
GetNeighborhood(
P
,
c
a
n
)
⊆
P.
(2)
∀
p
∈
P
∣
D
i
s
t
a
n
c
e
(
p
,
a
)
≤
n, then p
∈
G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
).This is a noninjective function. Consequently, it is not possible to recover the original set P starting from G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
). Additionally, it is surjective, so that a randomly selected collection of points may represent a neighborhood.Definition 8 (area density).
Given a set of pointsP
∈
℘
(
R
2
) and a circular area c
a
n
∈
R
2
×
R, the function Density ℘
(
R
2
)
×
(
R
2
×
R
)
→
R, is defined as(3)
Density
P
,
c
a
n
=
GetNeighborhood
P
,
c
a
n
π
n
2
.Starting from the previous definitions, the fire spread function may provide big circles covering less dense areas and smaller circles as point density increases. Figure 4 shows some examples.Figure 4
Examples of heterogeneous shapes based on fire density (a) and node density (b). Shapes are represented by shadowed areas. Black points represent nodes detecting fire. White points represent the rest of network nodes. In (a), the biggest circle corresponds to pointc due to G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
c
n
)
=
{
c
}. One of the smallest circles corresponds to point d, due to G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
d
n
)
=
{
a
,
d
,
e
,
f
,
g
,
h
}.
(a)
(b)Theseheterogeneous shapes based on fire density may be computed by each destination node (or handheld device carried by a firefighter) as fire points are received. Given a prefixed radius n for the neighborhood, according to [17], two options for the fire spread function are an inverse linear behavior F
(
P
,
p
)
=
A
-
B
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
) and a logarithmic behavior F
(
P
,
p
)
=
A
+
B
l
n
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
).A straightforward improvement of this approach consists of computing the area density by considering all the deployed network nodes, even those nodes which have not reported fire, yet. In this way, the previous definitions applied to fire density can be directly translated to node density.We can see the benefits of this improvement by comparing Figures4(a) and 4(b). In the new approximation (Figure 4(b)), the size of the shaded circular area centered on point a has been considerably reduced, since G
e
t
N
e
i
g
h
b
o
r
h
o
o
d
(
P
,
c
a
n
)
=
{
a
,
b
,
d
,
i
,
j
,
k
,
l
}. However, given that each network node does not store information about the entire topology (it is only able to know about its direct neighbors), this approach involves that density values are determined by the nodes detecting the fire, instead of being computed by the nodes receiving the corresponding notification (as before). As a consequence, the dissemination mechanism should support the propagation of this information through the network.


## 4.2. Hull-Based Model

In this subsection we describe a second proposal for modeling forest fires, based on a shape composed of a collection of convex hulls (from now on, only “hulls”) [18, 62]. The advantage of this approach is that each node only considers those fire positions received which would imply a variation in the local approximation, ignoring the rest of fire events. Consequently, the amount of data stored and disseminated through the network is significantly reduced.Definition 9 (relative position among points).
Given three pointsa, b, and c
∈
R
2, the relative position (clockwise,counter clockwise, orin line) among them is provided by the function Order R
2
×
R
2
×
R
2
→
{
C
W
,
C
C
W
,
L
I
N
E
}, denoted by O
r
d
e
r
(
a
,
b
,
c
) and defined by(4)
Order
a
,
b
,
c
=
CW
,
if
det
⁡
a
,
b
,
c
<
0
CCW
,
if
det
⁡
a
,
b
,
c
>
0
LINE
,
if
det
⁡
a
,
b
,
c
=
0
,
where det⁡
a
,
b
,
c
=
1
a
x
a
y
1
b
x
b
y
1
c
x
c
y
.An example of application of this function is shown in Figure 5.Figure 5
Relative position of three points. Given the spatial distribution of pointsa, b, c, and d, then O
r
d
e
r
(
a
,
b
,
c
)
=
C
W and O
r
d
e
r
(
a
,
b
,
d
)
=
C
C
W. In the same way, O
r
d
e
r
(
a
,
c
,
b
)
=
C
C
W, O
r
d
e
r
(
a
,
d
,
b
)
=
C
W, and O
r
d
e
r
(
c
,
d
,
a
)
=
C
C
W. Similarly, O
r
d
e
r
(
a
,
b
,
a
)
=
O
r
d
e
r
(
a
,
b
,
b
)
=
L
I
N
E.Definition 10 (hull function).
Given a set of pointsP
∈
(
R
2
), the function GetHull ℘
(
R
2
)
→
℘
(
R
2
), denoted by G
e
t
H
u
l
l
(
P
) or H
P, verifies the following: (1)
H
P
⊆
P.
(2)
∀
a
∈
H
P, ∃
b
∈
H
P
∣
∀
p
∈
P, O
r
d
e
r
(
a
,
b
,
p
)
∈
{
C
W
,
L
I
N
E
}.
(3)
∀
a
∈
H
P, ∃
b
∈
H
P
∣
∀
c
∈
H
P, O
r
d
e
r
(
a
,
b
,
c
)
=
C
W.An example of application of this function is shown in Figure 6(a).Figure 6
(a) Hull obtained from a set of points. GivenP
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
,
i
,
j
}, then H
P
=
{
a
,
b
,
d
,
e
,
g
,
h
,
i
} (black points). (b) Set of points enclosed by a hull. Given P
=
{
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
,
i
,
j
} and a hull H
=
{
a
,
c
,
f
,
g
,
h
,
i
}, then E
n
c
l
o
s
e
d
(
P
,
H
)
=
{
a
,
c
,
f
,
g
,
h
,
i
,
j
} (black points).
(a)
(b)GetHull is a noninjective function. Consequently, it is not possible to recover the original setP starting from G
e
t
H
u
l
l
(
P
). Additionally, it is nonsurjective, so that a randomly selected collection of points does not necessarily represent a hull. For this reason, we introduce the next definition.Definition 11 (hull).
A set of pointsH
∈
℘
(
R
2
) is a hull if it verifies that G
e
t
H
u
l
l
(
H
)
=
H.Definition 12 (enclosed set).
Given a set of pointsP
∈
℘
(
R
2
) and a hull H
∈
℘
(
R
2
), the function Enclosed ℘
(
R
2
)
×
℘
(
R
2
)
→
℘
(
R
2
), denoted by E
n
c
l
o
s
e
d
(
P
,
H
), verifies the following: (1)
E
n
c
l
o
s
e
d
(
P
,
H
)
⊆
P.
(2)
∀
p
∈
P
∣
∀
a
∈
H, ∃
b
∈
H
∣
O
r
d
e
r
(
a
,
b
,
p
)
=
C
W, then p
∈
E
n
c
l
o
s
e
d
(
P
,
H
).Enclosed is a noninjective function since although it is possible to recover the original set H starting from E
n
c
l
o
s
e
d
(
P
,
H
), it is not possible to recover the original set P. Additionally, it is a surjective function. Therefore, given any random set of points, there is a hull enclosing it. An example of application of this function is shown in Figure 6(b).Definition 13 (hull-based shape).
Given a set of pointsP
∈
℘
(
R
2
) and a value d
∈
R, the function G
e
t
S
h
a
p
e
℘
(
R
2
)
×
R
→
℘
(
℘
(
R
2
)
), denoted by G
e
t
S
h
a
p
e
(
P
,
d
) or S
P
d, verifies the following: (1)
∀
H
∈
S
P
d, H
⊆
P
∧
H is a hull.
(2)
∀
H
∈
S
P
d, ∀
Q
1, Q
2
∣
Q
1
∪
Q
2
=
E
n
c
l
o
s
e
d
(
P
,
H
)
∧
Q
1
∩
Q
2
=
⌀, ∃
a
∈
Q
1
∣
∃
b
∈
Q
2 that verifies D
i
s
t
a
n
c
e
(
a
,
b
)
<
d.
(3)
∀
H
1, H
2
∈
S
P
d, H
1
∩
H
2
=
E
n
c
l
o
s
e
d
(
P
,
H
1
)
∩
E
n
c
l
o
s
e
d
(
P
,
H
2
).
(4)
∀
H
1, H
2
∈
S
P
d, ∀
a
,
b
∈
P, a
∈
H
1
∧
a
∉
H
2
∧
b
∉
H
1
∧
b
∈
H
2
⇒
D
i
s
t
a
n
c
e
(
a
,
b
)
>
d
(5)
∀
p
∈
P, ∃
H
∈
S
P
d
∣
p
∈
E
n
c
l
o
s
e
d
(
P
,
H
).GetShape is a noninjective function. Consequently, it is not possible to recover the original set P starting from S
P
d. Additionally, it is nonsurjective, so that a randomly selected collection of points does not necessarily represent a shape. An example of application of this function is shown in Figure 7.Figure 7
Set of points enclosed by a hull-based shape. Given a spatial distribution forP, the amount of hulls provided by GetShape depends on the applied threshold distance. (a) and (b) show results for two different values, d
1 and d
2, assuming that d
1
<
d
2. Hulls are represented by linked black points. Points not belonging to any hull are represented by white points. Independently of the value of the threshold distance, all the points of P are enclosed into some hull.
(a)
G
e
t
S
h
a
p
e
(
P
,
d
1
)
=
{
H
1
,
H
2
,
H
3
,
H
4
}
(b)
G
e
t
S
h
a
p
e
(
P
,
d
2
)
=
{
H
1
,
H
5
,
H
6
}Given a hull-based shape representing a fire, the next function may be applied to determine whether an arbitrary location is burning or not.Definition 14 (belonging function).
Given a shapeS
P
d and a point p
∈
R
2, the function Inside ℘
(
℘
(
R
2
)
)
×
R
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
P
d
,
p
), verifies the following: (5)
Inside
S
P
d
,
p
=
true
,
if
S
P
d
=
S
P
∪
p
d
false
,
in other cases.


## 4.3. Polygon-Based Model

The main contribution of the current work is a fire representation model based on arbitrary polygons, which is described in this subsection.We first formally define the concept of a polygon-based shape, that is, a contour composed of several closed chains of vertices connected by segments. After that, we will introduce the criterion used to determine if a specified position of the plane is covered (or not) by a given shape.


### 4.3.1. Polygon-Based Shapes

Definition 15 (vertex).
LetV be the set of vertices. Given a vertex p
∈
V, the function Position V
→
R
2, denoted by P
o
s
i
t
i
o
n
(
p
)
=
P, provides the 2D position of the vertex. This is a noninjective function since multiple overlapped vertices p
1
,
p
2
…
p
n may be located at the same point, that is, P
o
s
i
t
i
o
n
(
p
1
)
=
P
o
s
i
t
i
o
n
(
p
2
)
=
⋯
=
P
o
s
i
t
i
o
n
(
p
n
)
=
P. In this case, all vertices are referred to asclones.For the sake of clarity, we will use circles labeled with capital letters for representing points and we will represent vertices by means of misplaced boxes labeled with small letters with numerical subscripts used to distinguish among clones (see, e.g., Figure8).Figure 8
Example of a polygon-based shapeS
=
{
[
a
b
c
]
[
d
1
e
2
f
g
h
i
j
k
l
]
[
d
2
m
n
e
1
]
[
o
]
}. Boxes help us to distinguish among several cloned vertices (placed into the same location). For clarity, segment o
o (with null length) has been drawn as a curved vector starting and ending at the same point.Definition 16 (sequence functions).
LetF
=
(
℘
(
V
)
×
V
,
V
) be the set of functions from ℘
(
V
)
×
V to V. Given a set of vertices V
⊂
V and a vertex v
∈
V, the function next ℘
(
V
)
×
V
→
V, denoted by n
e
x
t
(
V
,
v
), or simply v
⇾, provides the next vertex to v in V, that is, ∀
a
∈
V, a
⇾
∈
V. Similarly, the inverse function prev ℘
(
V
)
×
V
→
V, denoted by p
r
e
v
(
V
,
v
) or v
⇽, provides the previous vertex to v in V, satisfying that ∀
a, b
∈
V
∣
a
⇾
=
b implies that b
⇽
=
a.Definition 17 (polygon-based shape).
Given a set of verticesV
∈
℘
(
V
) and a function n
e
x
t
(
V
,
v
)
∈
F, a shape S
∈
S
=
(
℘
(
V
)
×
F
), denoted by S
(
V
,
n
e
x
t
), or S, is a set of vertices maintaining a relationship of sequence among them.Definition 18 (segment).
Given two verticesa
,
b
∈
V
∣
P
o
s
i
t
i
o
n
(
a
)
=
A and P
o
s
i
t
i
o
n
(
b
)
=
B, the relation a
⇾
=
b will be denoted by a segment a
b and graphically represented by a vector from point A to point B. Consequently, a shape will be represented as a directed graph (as shown in the example of Figure 8).Definition 19 (chain).
Given a shapeS
(
V
,
n
e
x
t
)
∈
S, it may be partitioned in k disjoint ordered subsets C
1
,
C
2
,
…
C
k called chains, verifying the following:(1)
∀
v
∈
S, ∃
C
⊂
S
∣
v
∈
C.
(2)
∀
C
i, C
j
⊂
S, C
i
∩
C
j
=
⌀.
(3)
⋃
i
=
1
k
C
i
=
S.
(4)
∀
C
⊂
S composed of n vertices, denoted by [
v
0
v
1
⋯
v
n
-
1
], it verifies that ∀
i
,
0
≤
i
<
n, v
i
⇾
=
v
(
(
i
+
1
)
m
o
d
n
).Graphically, each chain of the shape is represented as a subgraph composed of a cyclic sequence of n consecutive segments. Note that a chain allows n different notations. Also, when appropriate, irrelevant subchains in a chain are abbreviated by “⋯.”


### 4.3.2. Coverage Issues

Definition 20 (point of a segment).
Given a pointP
∈
R
2 and a segment a
b
∈
S, we say that P belongs to a
b or P
∈
a
b, if it is verified that(1)
(
P
y
-
A
y
)
(
P
y
-
B
y
)
≤
0,
(2)
A
x
+
(
B
x
-
A
x
/
B
y
-
A
y
)
(
P
y
-
A
y
)
=
P
x.Definition 21 (horizontal semiline).
Given a pointP
∈
R
2, a horizontal semiline y
=
P
y, or P
⟜, is defined ∀
x
>
P
x.Definition 22 (segment crossing a semiline).
Given a shapeS
∈
S, a point P
∈
R
2 defining the semiline P
⟜, and a segment a
b
∈
S, we say that a
b crosses P
⟜ or a
b
⌿
P
⟜, if the following conditions are satisfied:(1)
A
y
≠
B
y.
(2)
A
x
+
(
B
x
-
A
x
/
B
y
-
A
y
)
(
P
y
-
A
y
)
>
P
x.
(3)
(
P
y
-
A
y
)
(
P
y
-
B
y
)
≤
0.
(4)
P
y
≠
m
i
n
(
A
y
,
B
y
).Definition 23 (set of segments crossing a semiline).
Given a shapeS
∈
S and a point P
∈
R
2 defining the semiline P
⟜, the subset of segments of S crossing P
⟜, denoted by X
P
⊂
S, verifies that(1)
∀
a
b
∈
S
∣
a
b
⌿
P
⟜, a
b
∈
X
P,
(2)
∀
a
b
∈
X
P, a
b
⌿
P
⟜.Definition 24 (belonging function).
Given a shapeS
(
V
,
n
e
x
t
)
∈
S and a point P
∈
R
2, the function Inside S
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
,
P
), is defined by(6)
Inside
S
,
P
=
true,
if
∃
a
∈
S
∣
pos
a
=
P
∨
∃
a
b
∈
S
∣
P
∈
a
b
∨
X
P
is odd
false,
in other cases.
X
P indicates thecardinality of X
P, that is, the amount of segments crossing P
⟜. Figure 9 shows an example of the behavior of this function.Figure 9
For the shapeS of Figure 8, I
n
s
i
d
e
(
S
,
U
)
=
f
a
l
s
e, I
n
s
i
d
e
(
S
,
V
)
=
f
a
l
s
e, and I
n
s
i
d
e
(
S
,
W
)
=
t
r
u
e.A WSN deployed over a forest area with the purpose of monitoring the evolution of a wildfire will produce a set of 2D points indicating the presence of fire in the specific locations of certain network nodes. Although the information collected is discrete, the fire spreads continuously over the area. For this reason, the shapes should be “interpolated” starting from the collection of gathered points but by establishing a minimum distance threshold among these points to allow the space “in the middle” to be considered to be actually burning or not. This is formally stated in the next definition.Definition 25 (shape covering a set of points with a distance threshold).
Given a set of pointsQ
∈
℘
(
V
), a shape S
∈
S covers Q with a threshold d if it verifies that(1)
∀
a
∈
S, P
o
s
i
t
i
o
n
(
a
)
∈
Q,
(2)
∀
a
b
∈
S, Distance (
P
o
s
i
t
i
o
n
(
a
)
,
P
o
s
i
t
i
o
n
(
b
)
)
≤
d,
(3)
∀
A
∈
Q, I
n
s
i
d
e
(
S
,
A
)
=
t
r
u
e,
(4)
∀
A, B
∈
Q
∣
D
i
s
t
a
n
c
e
(
A
,
B
)
≤
d, then ∀
P
∈
R
2, I
n
s
i
d
e
(
{
[
a
,
b
]
}
,
P
)
⇒
I
n
s
i
d
e
(
S
,
P
),
(5)
∀
A, B, C
∈
Q
∣
D
i
s
t
a
n
c
e
(
A
,
B
)
≤
d, D
i
s
t
a
n
c
e
(
B
,
C
)
≤
d, and D
i
s
t
a
n
c
e
(
C
,
A
)
≤
d, then ∀
P
∈
R
2, I
n
s
i
d
e
(
{
[
a
,
b
,
c
]
}
,
P
)
⇒
I
n
s
i
d
e
(
S
,
P
).


## 4.3.1. Polygon-Based Shapes

Definition 15 (vertex).
LetV be the set of vertices. Given a vertex p
∈
V, the function Position V
→
R
2, denoted by P
o
s
i
t
i
o
n
(
p
)
=
P, provides the 2D position of the vertex. This is a noninjective function since multiple overlapped vertices p
1
,
p
2
…
p
n may be located at the same point, that is, P
o
s
i
t
i
o
n
(
p
1
)
=
P
o
s
i
t
i
o
n
(
p
2
)
=
⋯
=
P
o
s
i
t
i
o
n
(
p
n
)
=
P. In this case, all vertices are referred to asclones.For the sake of clarity, we will use circles labeled with capital letters for representing points and we will represent vertices by means of misplaced boxes labeled with small letters with numerical subscripts used to distinguish among clones (see, e.g., Figure8).Figure 8
Example of a polygon-based shapeS
=
{
[
a
b
c
]
[
d
1
e
2
f
g
h
i
j
k
l
]
[
d
2
m
n
e
1
]
[
o
]
}. Boxes help us to distinguish among several cloned vertices (placed into the same location). For clarity, segment o
o (with null length) has been drawn as a curved vector starting and ending at the same point.Definition 16 (sequence functions).
LetF
=
(
℘
(
V
)
×
V
,
V
) be the set of functions from ℘
(
V
)
×
V to V. Given a set of vertices V
⊂
V and a vertex v
∈
V, the function next ℘
(
V
)
×
V
→
V, denoted by n
e
x
t
(
V
,
v
), or simply v
⇾, provides the next vertex to v in V, that is, ∀
a
∈
V, a
⇾
∈
V. Similarly, the inverse function prev ℘
(
V
)
×
V
→
V, denoted by p
r
e
v
(
V
,
v
) or v
⇽, provides the previous vertex to v in V, satisfying that ∀
a, b
∈
V
∣
a
⇾
=
b implies that b
⇽
=
a.Definition 17 (polygon-based shape).
Given a set of verticesV
∈
℘
(
V
) and a function n
e
x
t
(
V
,
v
)
∈
F, a shape S
∈
S
=
(
℘
(
V
)
×
F
), denoted by S
(
V
,
n
e
x
t
), or S, is a set of vertices maintaining a relationship of sequence among them.Definition 18 (segment).
Given two verticesa
,
b
∈
V
∣
P
o
s
i
t
i
o
n
(
a
)
=
A and P
o
s
i
t
i
o
n
(
b
)
=
B, the relation a
⇾
=
b will be denoted by a segment a
b and graphically represented by a vector from point A to point B. Consequently, a shape will be represented as a directed graph (as shown in the example of Figure 8).Definition 19 (chain).
Given a shapeS
(
V
,
n
e
x
t
)
∈
S, it may be partitioned in k disjoint ordered subsets C
1
,
C
2
,
…
C
k called chains, verifying the following:(1)
∀
v
∈
S, ∃
C
⊂
S
∣
v
∈
C.
(2)
∀
C
i, C
j
⊂
S, C
i
∩
C
j
=
⌀.
(3)
⋃
i
=
1
k
C
i
=
S.
(4)
∀
C
⊂
S composed of n vertices, denoted by [
v
0
v
1
⋯
v
n
-
1
], it verifies that ∀
i
,
0
≤
i
<
n, v
i
⇾
=
v
(
(
i
+
1
)
m
o
d
n
).Graphically, each chain of the shape is represented as a subgraph composed of a cyclic sequence of n consecutive segments. Note that a chain allows n different notations. Also, when appropriate, irrelevant subchains in a chain are abbreviated by “⋯.”


## 4.3.2. Coverage Issues

Definition 20 (point of a segment).
Given a pointP
∈
R
2 and a segment a
b
∈
S, we say that P belongs to a
b or P
∈
a
b, if it is verified that(1)
(
P
y
-
A
y
)
(
P
y
-
B
y
)
≤
0,
(2)
A
x
+
(
B
x
-
A
x
/
B
y
-
A
y
)
(
P
y
-
A
y
)
=
P
x.Definition 21 (horizontal semiline).
Given a pointP
∈
R
2, a horizontal semiline y
=
P
y, or P
⟜, is defined ∀
x
>
P
x.Definition 22 (segment crossing a semiline).
Given a shapeS
∈
S, a point P
∈
R
2 defining the semiline P
⟜, and a segment a
b
∈
S, we say that a
b crosses P
⟜ or a
b
⌿
P
⟜, if the following conditions are satisfied:(1)
A
y
≠
B
y.
(2)
A
x
+
(
B
x
-
A
x
/
B
y
-
A
y
)
(
P
y
-
A
y
)
>
P
x.
(3)
(
P
y
-
A
y
)
(
P
y
-
B
y
)
≤
0.
(4)
P
y
≠
m
i
n
(
A
y
,
B
y
).Definition 23 (set of segments crossing a semiline).
Given a shapeS
∈
S and a point P
∈
R
2 defining the semiline P
⟜, the subset of segments of S crossing P
⟜, denoted by X
P
⊂
S, verifies that(1)
∀
a
b
∈
S
∣
a
b
⌿
P
⟜, a
b
∈
X
P,
(2)
∀
a
b
∈
X
P, a
b
⌿
P
⟜.Definition 24 (belonging function).
Given a shapeS
(
V
,
n
e
x
t
)
∈
S and a point P
∈
R
2, the function Inside S
×
R
2
→
{
t
r
u
e
,
f
a
l
s
e
}, denoted by I
n
s
i
d
e
(
S
,
P
), is defined by(6)
Inside
S
,
P
=
true,
if
∃
a
∈
S
∣
pos
a
=
P
∨
∃
a
b
∈
S
∣
P
∈
a
b
∨
X
P
is odd
false,
in other cases.
X
P indicates thecardinality of X
P, that is, the amount of segments crossing P
⟜. Figure 9 shows an example of the behavior of this function.Figure 9
For the shapeS of Figure 8, I
n
s
i
d
e
(
S
,
U
)
=
f
a
l
s
e, I
n
s
i
d
e
(
S
,
V
)
=
f
a
l
s
e, and I
n
s
i
d
e
(
S
,
W
)
=
t
r
u
e.A WSN deployed over a forest area with the purpose of monitoring the evolution of a wildfire will produce a set of 2D points indicating the presence of fire in the specific locations of certain network nodes. Although the information collected is discrete, the fire spreads continuously over the area. For this reason, the shapes should be “interpolated” starting from the collection of gathered points but by establishing a minimum distance threshold among these points to allow the space “in the middle” to be considered to be actually burning or not. This is formally stated in the next definition.Definition 25 (shape covering a set of points with a distance threshold).
Given a set of pointsQ
∈
℘
(
V
), a shape S
∈
S covers Q with a threshold d if it verifies that(1)
∀
a
∈
S, P
o
s
i
t
i
o
n
(
a
)
∈
Q,
(2)
∀
a
b
∈
S, Distance (
P
o
s
i
t
i
o
n
(
a
)
,
P
o
s
i
t
i
o
n
(
b
)
)
≤
d,
(3)
∀
A
∈
Q, I
n
s
i
d
e
(
S
,
A
)
=
t
r
u
e,
(4)
∀
A, B
∈
Q
∣
D
i
s
t
a
n
c
e
(
A
,
B
)
≤
d, then ∀
P
∈
R
2, I
n
s
i
d
e
(
{
[
a
,
b
]
}
,
P
)
⇒
I
n
s
i
d
e
(
S
,
P
),
(5)
∀
A, B, C
∈
Q
∣
D
i
s
t
a
n
c
e
(
A
,
B
)
≤
d, D
i
s
t
a
n
c
e
(
B
,
C
)
≤
d, and D
i
s
t
a
n
c
e
(
C
,
A
)
≤
d, then ∀
P
∈
R
2, I
n
s
i
d
e
(
{
[
a
,
b
,
c
]
}
,
P
)
⇒
I
n
s
i
d
e
(
S
,
P
).


## 5. Performance Evaluation

In this section, we will analyze the quality of the approximation produced by the proposed fire models. After describing the simulation environment and the evaluation methodology used, we present a preliminary study aimed at choosing the optimal value for the parameters associated with each model. Finally, we provide the results corresponding to the comparative evaluation.


### 5.1. Simulation Environment

In the context of the EIDOS system, we have developed a simulation environment [16], in which we can deploy a WSN, spread a forest fire, place firefighters, and see the evolution of the fire fronts that they are faced with. As shown in Figure 10, this tool is composed of several independent and interconnected modules, which share information by means of a global MySQL database [63].Figure 10
Architecture of the EIDOS simulation environment.In short, first we use Farsite [64] to simulate a fire over a particular forest area, under realistic conditions, that is, by using real geographical, environmental, and vegetation data. Then, a WSN simulator (developed in Python/TOSSIM [65]) executes the EIDOS application in each network node, having as inputs the evolution of the temperatures generated by Farsite.Besides the WSN simulation, a graphical user interface (area display), developed with Adobe Flash [66], shows the evolution of the fire and allows the user to place and move firefighters across the scenario (Figure 12(a)). The evaluation environment also incorporates a handheld device simulator, developed with Adobe Air and interacting with the other components by means of Flash Remoting and Flash Media Server technology. This tool shows the fire approximation performed by the WSN in the surroundings of the position of the firefighter (Figure 12(b)).Regarding the radio propagation, we assume the use of omnidirectional antennas and the same transmission power for all network nodes. In order to reproduce a realistic scenario, the WSN simulator incorporates a noise and interference model and the well-knownFriis free-space signal propagation model [67]. We have modeled the radio of the Iris motes [68], applying a transmission power of 3 dBm and a minimum reception power of −90 dBm. Under these conditions, we obtain an approximate radio range of 50 meters. The simulated protocol for media access control is the basic CSMA [65].


### 5.2. Evaluation Methodology

At the beginning of each simulation run, the nodes are randomly distributed in a square area of 2500 × 2500 meters. We have considered network sizes varying from 2000 to 15000 nodes, corresponding to connectivity degrees (average number of direct neighbors per node) from 3.02 to 23.6. During the simulation, a forest fire with three separate ignition points and changing wind conditions spreads in the deployment area two hours after the beginning of the simulation, and four hours later it has reached approximately half of the simulation area (Figure11).Figure 11
Aspect of the original fire.Figure 12
User interfaces developed in the context of the EIDOS simulation environment.
(a)
Forest area display
(b)
Firefighter mobile applicationSensor nodes behave as detailed in Section3.3. For localization purposes, in this paper we assume that all nodes know their location with negligible error. However, this is not a limitation, since the objective is to make a fair comparison of the different solutions proposed, benchmarking them against the baseline “circular shape” model. Each time a node detects a fire in its proximity (by a sudden rise in the sensed temperature), it broadcasts its position. Our simulation model also takes into account that in a short period of time, the node affected by the fire is burnt, and consequently it becomes not operational any longer. Note that, although sensor nodes may cease to be operative as the fire spreads, network connectivity is supposed to be never lost. In realistic situations, this assumption holds true thanks to the redundancy level in the number of deployed nodes or, in extreme cases, to the addition of new nodes dropped by the aircraft. This means that any new fire detection event always reaches every (survivor) network nodes; thus, they are able to estimate the same fire shape, in a fully distributed way.In order to increase the representativeness of the obtained results, 10 independent simulation runs have been performed for each setup and the statistics have been averaged.The Farsite simulator has been assumed as provider of ground-truth fire spreading images over the time and the images obtained by each approximation method have been compared against those ones. In particular, Farsite outputs a set of raster files. Each raster is a 2D grid of cells representing the whole simulation area (for this work, we have set cells of 10 × 10 meters size each). The raster is a Time of Arrival (TOA) raster; that is, each cell has a timestamp valueT
O
A
(
c
e
l
l
) indicating the instant when the fire has reached that cell. This allows us to analyze how the fire spreads along time, since, for a given simulation time t, the fire has reached a cell if T
O
A
(
c
e
l
l
)
≤
t.In order to measure the accuracy of a given model, an unbiased criterion consists of comparing the TOA raster produced by Farsite with respect to the equivalent TOA raster obtained by each model. Thus, for a given timet, the amount of cells correctly estimated by each model is given by the sum of the recognized burning cells minus the amount of missed burning cells and minus the amount of cells wrongly estimated as burning. Sometimes, instead of using the absolute number of correct cells, we will use the correct cells rate, by normalizing that value over the total amount of burning cells (according to the Farsite output).


### 5.3. Tuning the Fire Approximation Models

In this section, we will evaluate the performance of the three distinct models to approximate the shape of the fire of Figure11, while Section 5.4 will focus on an overall comparison.


#### 5.3.1. Circle-Based Model

Figure13(a) shows the quality of the circle-based model, by considering the use of homogeneous shapes, with different radius values (i.e., the parameter r in the model), expressed in units of raster cells. We can see that (as intuitively expected) bigger circles are suitable for lower network degrees and vice versa. From these results we have selected the best radius to be applied in function of the network degree; and we have approximated them by a logarithmic fire spread function F
(
P
,
p
)
=
6.1419
-
1.283
l
n
⁡
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
)
⁡. More details about that may be found in [17].Figure 13
Quality of the circle-based approximation versus network degree (time = 5 hours).
(a)
Homogeneous shapes
(b)
Heterogeneous shapesFigure13(b) shows the quality of heterogeneous shapes composed of circles with radius obtained applying the previously computed fire spread function. In this case, numerical values in the legend represent the radius of this area (i.e., the parameter n in the model), expressed in meters. Each node only knows the amount of neighbours located under its radio coverage (because of alternative communication protocols that broadcast node positions are not considered); therefore, the “N 50” series in this plot is the only one that corresponds to the use of heterogeneous shapes based on node density. On the other hand, as each node stores and relays all the received fire positions, they are able to compute heterogeneous shapes based on fire density even on areas bigger than the coverage area. For this reason, we have considered fire density areas with radius equal to 50, 75, and 100 meters.Overall, we may conclude that the best results for heterogeneous shapes are obtained when they are based on node density, even if fire density was considered for bigger areas.


#### 5.3.2.  Hull-Based Model

Figure14(a) shows the accuracy of the approximation obtained by the hull-based model, in function of the distance of fusion considered (i.e., the parameter d in the model), expressed in meters. The “Farsite” series shows the real amount of burning cells (verifying that T
O
A
f
a
r
s
i
t
e
[
c
e
l
l
]
≤
t), representing an ideal upper bound for any fire approximation. The rest of series show the quality achieved by the multiple hull-based approximation. We can appreciate that the “d
=
∞” series (that implies a shape composed of only one hull) offers a poor approximation to the fire, representing the lower bound for this technique. Additionally, the “d
=
400” series performs similarly to the “d
=
∞” series, making this analysis for higher values of d unnecessary. On the other hand, as d decreases, the accuracy of the representation increases. Additionally, we observe that the “d
=
40” series exhibits a slightly worse behavior than the “d
=
50” series during the first part of the simulation. For this reason, we do not continue analyzing smaller values for d.Figure 14
Quality of the hull-based approximation.
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 4 hours)Figure14(b) shows the influence of network degree on the accuracy of the obtained approximation. The “d
=
∞” series shows that an approximation based on a single convex hull is not negatively affected by low network densities (on the contrary, it even slightly improves). The reason is that errors produced by not covered burning areas are implicitly corrected as the hull grows. However, this approach is able to correctly estimate only 32% of a forest fire. On the other hand, beyond a certain density threshold, approximations based on multiple hulls are very accurate, correctly estimating up to 72% of a forest fire. Also, they (especially the “d
=
50” series) are not significantly affected by low densities until the network is practically unconnected.In conclusion, from both charts of Figure14 we can state that a value for d
=
50 meters is fair, assuming that the network connectivity degree is not too low. A more detailed analysis including memory requirements may be found in [18].


#### 5.3.3. Polygon-Based Model

Figure15 presents the results for the polygon-based model, by considering different values for the distance parameter (d), expressed in meters. In Figure 15(a) we can observe that, for low distances (40, 60, and 80 meters), the quality of the obtained approximation is poor. The reason is that the polygons in the shape do not merge, leading to lots of burning regions missed by the approximation. However, highest threshold distances are not the best option, since the improvement in the accuracy tends to become marginal.Figure 15
Quality of the polygon-based approximation.
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 5 hours)In Figure15(b) we can see that, in general, higher distances are less affected by network density (they are more stable). For sparse networks, the quality of the approximation grows up with distance. The reason is that low values of the distance lead to poor quality levels since several burning cells are not identified. On the other hand, as network degree increases, lower distance thresholds perform better. This is due to the fact that greater distance values lead to loss of resolution in the fire shape approximation; that is, fire “holes” (still not burning cells) are considered to be already burning. Therefore, a reasonable election for the following comparative analysis may be a threshold distance d
=
200 meters, since it maintains a good quality for a wide range of densities.


### 5.4. Comparative Analysis

After tuning the optimal parameter values for each fire model, this subsection presents a comparative analysis. Before presenting the quantitative results obtained, Figure16 shows the fire evolution presented in Figure 11 and the corresponding outputs provided by the analyzed proposals. At the beginning, the circle-based model overestimates the burning areas (reporting fire where there is not), whereas the other models underestimate them. As time evolves, we can appreciate that convex hulls grow and their fusion produce significant overestimations.Figure 16
Aspect of the original fire (left column) and the corresponding approximations at different simulation times.Figure17 corroborates the previous appreciations by numerically showing the accuracy of the approximations provided by the analyzed fire models. In Figure 17(a) we can observe that the circle-based and polygon-based approximations provide the best results along the entire simulation run time, while, at the end of the simulation, when the fire has spread all over the area, the polygon-based approximation outperforms the circle-based one. In Figure 17(b) the influence of network degree on the quality of the approximation is shown. In this plot the same conclusion as before is confirmed. Circle-based and polygon-based approximations obtain accuracy levels close or above 90%, for all network densities, whereas the hull-based one only obtains about 70%. For sparser networks, the circle-based approximation underperforms the polygon-based one.Figure 17
Quality of the approximations
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 5 hours)Finally, Figure18 compares the amounts of node memory required by each model as the fire spreads. The plot shows that the circle-based approximation presents the highest memory requirements, since it needs all the information listened from the medium. On the other hand, the in-network aggregation proposals reduce these requirements to approximately 10%. Once the circle-based method has been discarded, we can see that hulls require less memory than polygons at the end of the simulation, when the shape representing the fire is composed of only a few large hulls.Figure 18
Instantaneous memory requirements (network size = 5000 nodes).


## 5.1. Simulation Environment

In the context of the EIDOS system, we have developed a simulation environment [16], in which we can deploy a WSN, spread a forest fire, place firefighters, and see the evolution of the fire fronts that they are faced with. As shown in Figure 10, this tool is composed of several independent and interconnected modules, which share information by means of a global MySQL database [63].Figure 10
Architecture of the EIDOS simulation environment.In short, first we use Farsite [64] to simulate a fire over a particular forest area, under realistic conditions, that is, by using real geographical, environmental, and vegetation data. Then, a WSN simulator (developed in Python/TOSSIM [65]) executes the EIDOS application in each network node, having as inputs the evolution of the temperatures generated by Farsite.Besides the WSN simulation, a graphical user interface (area display), developed with Adobe Flash [66], shows the evolution of the fire and allows the user to place and move firefighters across the scenario (Figure 12(a)). The evaluation environment also incorporates a handheld device simulator, developed with Adobe Air and interacting with the other components by means of Flash Remoting and Flash Media Server technology. This tool shows the fire approximation performed by the WSN in the surroundings of the position of the firefighter (Figure 12(b)).Regarding the radio propagation, we assume the use of omnidirectional antennas and the same transmission power for all network nodes. In order to reproduce a realistic scenario, the WSN simulator incorporates a noise and interference model and the well-knownFriis free-space signal propagation model [67]. We have modeled the radio of the Iris motes [68], applying a transmission power of 3 dBm and a minimum reception power of −90 dBm. Under these conditions, we obtain an approximate radio range of 50 meters. The simulated protocol for media access control is the basic CSMA [65].


## 5.2. Evaluation Methodology

At the beginning of each simulation run, the nodes are randomly distributed in a square area of 2500 × 2500 meters. We have considered network sizes varying from 2000 to 15000 nodes, corresponding to connectivity degrees (average number of direct neighbors per node) from 3.02 to 23.6. During the simulation, a forest fire with three separate ignition points and changing wind conditions spreads in the deployment area two hours after the beginning of the simulation, and four hours later it has reached approximately half of the simulation area (Figure11).Figure 11
Aspect of the original fire.Figure 12
User interfaces developed in the context of the EIDOS simulation environment.
(a)
Forest area display
(b)
Firefighter mobile applicationSensor nodes behave as detailed in Section3.3. For localization purposes, in this paper we assume that all nodes know their location with negligible error. However, this is not a limitation, since the objective is to make a fair comparison of the different solutions proposed, benchmarking them against the baseline “circular shape” model. Each time a node detects a fire in its proximity (by a sudden rise in the sensed temperature), it broadcasts its position. Our simulation model also takes into account that in a short period of time, the node affected by the fire is burnt, and consequently it becomes not operational any longer. Note that, although sensor nodes may cease to be operative as the fire spreads, network connectivity is supposed to be never lost. In realistic situations, this assumption holds true thanks to the redundancy level in the number of deployed nodes or, in extreme cases, to the addition of new nodes dropped by the aircraft. This means that any new fire detection event always reaches every (survivor) network nodes; thus, they are able to estimate the same fire shape, in a fully distributed way.In order to increase the representativeness of the obtained results, 10 independent simulation runs have been performed for each setup and the statistics have been averaged.The Farsite simulator has been assumed as provider of ground-truth fire spreading images over the time and the images obtained by each approximation method have been compared against those ones. In particular, Farsite outputs a set of raster files. Each raster is a 2D grid of cells representing the whole simulation area (for this work, we have set cells of 10 × 10 meters size each). The raster is a Time of Arrival (TOA) raster; that is, each cell has a timestamp valueT
O
A
(
c
e
l
l
) indicating the instant when the fire has reached that cell. This allows us to analyze how the fire spreads along time, since, for a given simulation time t, the fire has reached a cell if T
O
A
(
c
e
l
l
)
≤
t.In order to measure the accuracy of a given model, an unbiased criterion consists of comparing the TOA raster produced by Farsite with respect to the equivalent TOA raster obtained by each model. Thus, for a given timet, the amount of cells correctly estimated by each model is given by the sum of the recognized burning cells minus the amount of missed burning cells and minus the amount of cells wrongly estimated as burning. Sometimes, instead of using the absolute number of correct cells, we will use the correct cells rate, by normalizing that value over the total amount of burning cells (according to the Farsite output).


## 5.3. Tuning the Fire Approximation Models

In this section, we will evaluate the performance of the three distinct models to approximate the shape of the fire of Figure11, while Section 5.4 will focus on an overall comparison.


### 5.3.1. Circle-Based Model

Figure13(a) shows the quality of the circle-based model, by considering the use of homogeneous shapes, with different radius values (i.e., the parameter r in the model), expressed in units of raster cells. We can see that (as intuitively expected) bigger circles are suitable for lower network degrees and vice versa. From these results we have selected the best radius to be applied in function of the network degree; and we have approximated them by a logarithmic fire spread function F
(
P
,
p
)
=
6.1419
-
1.283
l
n
⁡
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
)
⁡. More details about that may be found in [17].Figure 13
Quality of the circle-based approximation versus network degree (time = 5 hours).
(a)
Homogeneous shapes
(b)
Heterogeneous shapesFigure13(b) shows the quality of heterogeneous shapes composed of circles with radius obtained applying the previously computed fire spread function. In this case, numerical values in the legend represent the radius of this area (i.e., the parameter n in the model), expressed in meters. Each node only knows the amount of neighbours located under its radio coverage (because of alternative communication protocols that broadcast node positions are not considered); therefore, the “N 50” series in this plot is the only one that corresponds to the use of heterogeneous shapes based on node density. On the other hand, as each node stores and relays all the received fire positions, they are able to compute heterogeneous shapes based on fire density even on areas bigger than the coverage area. For this reason, we have considered fire density areas with radius equal to 50, 75, and 100 meters.Overall, we may conclude that the best results for heterogeneous shapes are obtained when they are based on node density, even if fire density was considered for bigger areas.


### 5.3.2.  Hull-Based Model

Figure14(a) shows the accuracy of the approximation obtained by the hull-based model, in function of the distance of fusion considered (i.e., the parameter d in the model), expressed in meters. The “Farsite” series shows the real amount of burning cells (verifying that T
O
A
f
a
r
s
i
t
e
[
c
e
l
l
]
≤
t), representing an ideal upper bound for any fire approximation. The rest of series show the quality achieved by the multiple hull-based approximation. We can appreciate that the “d
=
∞” series (that implies a shape composed of only one hull) offers a poor approximation to the fire, representing the lower bound for this technique. Additionally, the “d
=
400” series performs similarly to the “d
=
∞” series, making this analysis for higher values of d unnecessary. On the other hand, as d decreases, the accuracy of the representation increases. Additionally, we observe that the “d
=
40” series exhibits a slightly worse behavior than the “d
=
50” series during the first part of the simulation. For this reason, we do not continue analyzing smaller values for d.Figure 14
Quality of the hull-based approximation.
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 4 hours)Figure14(b) shows the influence of network degree on the accuracy of the obtained approximation. The “d
=
∞” series shows that an approximation based on a single convex hull is not negatively affected by low network densities (on the contrary, it even slightly improves). The reason is that errors produced by not covered burning areas are implicitly corrected as the hull grows. However, this approach is able to correctly estimate only 32% of a forest fire. On the other hand, beyond a certain density threshold, approximations based on multiple hulls are very accurate, correctly estimating up to 72% of a forest fire. Also, they (especially the “d
=
50” series) are not significantly affected by low densities until the network is practically unconnected.In conclusion, from both charts of Figure14 we can state that a value for d
=
50 meters is fair, assuming that the network connectivity degree is not too low. A more detailed analysis including memory requirements may be found in [18].


### 5.3.3. Polygon-Based Model

Figure15 presents the results for the polygon-based model, by considering different values for the distance parameter (d), expressed in meters. In Figure 15(a) we can observe that, for low distances (40, 60, and 80 meters), the quality of the obtained approximation is poor. The reason is that the polygons in the shape do not merge, leading to lots of burning regions missed by the approximation. However, highest threshold distances are not the best option, since the improvement in the accuracy tends to become marginal.Figure 15
Quality of the polygon-based approximation.
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 5 hours)In Figure15(b) we can see that, in general, higher distances are less affected by network density (they are more stable). For sparse networks, the quality of the approximation grows up with distance. The reason is that low values of the distance lead to poor quality levels since several burning cells are not identified. On the other hand, as network degree increases, lower distance thresholds perform better. This is due to the fact that greater distance values lead to loss of resolution in the fire shape approximation; that is, fire “holes” (still not burning cells) are considered to be already burning. Therefore, a reasonable election for the following comparative analysis may be a threshold distance d
=
200 meters, since it maintains a good quality for a wide range of densities.


## 5.3.1. Circle-Based Model

Figure13(a) shows the quality of the circle-based model, by considering the use of homogeneous shapes, with different radius values (i.e., the parameter r in the model), expressed in units of raster cells. We can see that (as intuitively expected) bigger circles are suitable for lower network degrees and vice versa. From these results we have selected the best radius to be applied in function of the network degree; and we have approximated them by a logarithmic fire spread function F
(
P
,
p
)
=
6.1419
-
1.283
l
n
⁡
(
D
e
n
s
i
t
y
(
P
,
c
p
n
)
)
⁡. More details about that may be found in [17].Figure 13
Quality of the circle-based approximation versus network degree (time = 5 hours).
(a)
Homogeneous shapes
(b)
Heterogeneous shapesFigure13(b) shows the quality of heterogeneous shapes composed of circles with radius obtained applying the previously computed fire spread function. In this case, numerical values in the legend represent the radius of this area (i.e., the parameter n in the model), expressed in meters. Each node only knows the amount of neighbours located under its radio coverage (because of alternative communication protocols that broadcast node positions are not considered); therefore, the “N 50” series in this plot is the only one that corresponds to the use of heterogeneous shapes based on node density. On the other hand, as each node stores and relays all the received fire positions, they are able to compute heterogeneous shapes based on fire density even on areas bigger than the coverage area. For this reason, we have considered fire density areas with radius equal to 50, 75, and 100 meters.Overall, we may conclude that the best results for heterogeneous shapes are obtained when they are based on node density, even if fire density was considered for bigger areas.


## 5.3.2.  Hull-Based Model

Figure14(a) shows the accuracy of the approximation obtained by the hull-based model, in function of the distance of fusion considered (i.e., the parameter d in the model), expressed in meters. The “Farsite” series shows the real amount of burning cells (verifying that T
O
A
f
a
r
s
i
t
e
[
c
e
l
l
]
≤
t), representing an ideal upper bound for any fire approximation. The rest of series show the quality achieved by the multiple hull-based approximation. We can appreciate that the “d
=
∞” series (that implies a shape composed of only one hull) offers a poor approximation to the fire, representing the lower bound for this technique. Additionally, the “d
=
400” series performs similarly to the “d
=
∞” series, making this analysis for higher values of d unnecessary. On the other hand, as d decreases, the accuracy of the representation increases. Additionally, we observe that the “d
=
40” series exhibits a slightly worse behavior than the “d
=
50” series during the first part of the simulation. For this reason, we do not continue analyzing smaller values for d.Figure 14
Quality of the hull-based approximation.
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 4 hours)Figure14(b) shows the influence of network degree on the accuracy of the obtained approximation. The “d
=
∞” series shows that an approximation based on a single convex hull is not negatively affected by low network densities (on the contrary, it even slightly improves). The reason is that errors produced by not covered burning areas are implicitly corrected as the hull grows. However, this approach is able to correctly estimate only 32% of a forest fire. On the other hand, beyond a certain density threshold, approximations based on multiple hulls are very accurate, correctly estimating up to 72% of a forest fire. Also, they (especially the “d
=
50” series) are not significantly affected by low densities until the network is practically unconnected.In conclusion, from both charts of Figure14 we can state that a value for d
=
50 meters is fair, assuming that the network connectivity degree is not too low. A more detailed analysis including memory requirements may be found in [18].


## 5.3.3. Polygon-Based Model

Figure15 presents the results for the polygon-based model, by considering different values for the distance parameter (d), expressed in meters. In Figure 15(a) we can observe that, for low distances (40, 60, and 80 meters), the quality of the obtained approximation is poor. The reason is that the polygons in the shape do not merge, leading to lots of burning regions missed by the approximation. However, highest threshold distances are not the best option, since the improvement in the accuracy tends to become marginal.Figure 15
Quality of the polygon-based approximation.
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 5 hours)In Figure15(b) we can see that, in general, higher distances are less affected by network density (they are more stable). For sparse networks, the quality of the approximation grows up with distance. The reason is that low values of the distance lead to poor quality levels since several burning cells are not identified. On the other hand, as network degree increases, lower distance thresholds perform better. This is due to the fact that greater distance values lead to loss of resolution in the fire shape approximation; that is, fire “holes” (still not burning cells) are considered to be already burning. Therefore, a reasonable election for the following comparative analysis may be a threshold distance d
=
200 meters, since it maintains a good quality for a wide range of densities.


## 5.4. Comparative Analysis

After tuning the optimal parameter values for each fire model, this subsection presents a comparative analysis. Before presenting the quantitative results obtained, Figure16 shows the fire evolution presented in Figure 11 and the corresponding outputs provided by the analyzed proposals. At the beginning, the circle-based model overestimates the burning areas (reporting fire where there is not), whereas the other models underestimate them. As time evolves, we can appreciate that convex hulls grow and their fusion produce significant overestimations.Figure 16
Aspect of the original fire (left column) and the corresponding approximations at different simulation times.Figure17 corroborates the previous appreciations by numerically showing the accuracy of the approximations provided by the analyzed fire models. In Figure 17(a) we can observe that the circle-based and polygon-based approximations provide the best results along the entire simulation run time, while, at the end of the simulation, when the fire has spread all over the area, the polygon-based approximation outperforms the circle-based one. In Figure 17(b) the influence of network degree on the quality of the approximation is shown. In this plot the same conclusion as before is confirmed. Circle-based and polygon-based approximations obtain accuracy levels close or above 90%, for all network densities, whereas the hull-based one only obtains about 70%. For sparser networks, the circle-based approximation underperforms the polygon-based one.Figure 17
Quality of the approximations
(a)
Instantaneous results (network degree = 7.89 neighbors/node)
(b)
Versus network degree (time = 5 hours)Finally, Figure18 compares the amounts of node memory required by each model as the fire spreads. The plot shows that the circle-based approximation presents the highest memory requirements, since it needs all the information listened from the medium. On the other hand, the in-network aggregation proposals reduce these requirements to approximately 10%. Once the circle-based method has been discarded, we can see that hulls require less memory than polygons at the end of the simulation, when the shape representing the fire is composed of only a few large hulls.Figure 18
Instantaneous memory requirements (network size = 5000 nodes).


## 6. Conclusions and Future Works

In this work, we have focused on the EIDOS platform, aimed at reducing human risks in forest firefighting operations. This system is based on a large WSN deployed from the air in the surroundings of the area affected by the fire. A communication layer allows the dissemination of fire detection events to the whole network. Starting from the information it listens to, each WSN node maintains an updated approximation of the current fire’s shape. We have introduced three mathematical models for representing the fire, based on using circles, convex hulls, and arbitrary polygons. After tuning them, we have comparatively analyzed the quality of the outputs provided by these approaches. For this, we have compared them with the output provided by the Farsite fire simulation tool. Results clearly demonstrate that the proposed approach using the polygon-based method outperforms the other approaches. More in detail, while the circle-based and polygon-based models obtain accurate approximations of the fire and are close to each other, particularly for higher network densities, the circle-based model exhibits the highest memory storage and communications overhead requirements.As future works, we plan to extend the fire models in order to handle 3D shapes. We also are going to evaluate the impact of localization and communication errors on the accuracy of the final approximations.



---

*Source: 964564-2015-10-04.xml*