\subsection{Comparison Between the Approaches in Detecting Hole Boundary}
As we mentioned above in section~\ref{Scheme_Overview}, we now compare by simulation experiments between the two HBD mentioned approaches, i.e. the Boundhole approach from~\cite{FGG04} and the BCP approach from~\cite{KYX13} to find out which suits better to our main goal: we need our HBD algorithm to be as fast as possible and to consume energy as less as possible (to help with monitoring expanding holes). In this evaluation, we run the experiments with $2$ network models: $1800$ nodes and $2500$ nodes.
Table~\ref{tab:simu_param_base} summarizes the parameters which are suggested by~\cite{SHCWW04}:

\begin{table}[h]
  \begin{center}
  \begin{tabular}{l r} \hline
    \textit{Variables} & \textit{Values} \\ \hline
    Communication range & 40m \\
    Voltage & 3V \\
    Receiving current & 15mA \\
    Transmitting current & 29.5mA \\
		Idle current & 3.2mA \\
		Number of nodes & 29.5mA  \\
		Period of HELLO packet & 30s  \\
		Simulation time & 1050s  \\ \hline
  \end{tabular}
  \end{center}
  \caption{Simulation parameters for comparing BOUNDHOLE and BCP algorithm}
	\label{tab:simu_param_base}
\end{table}

The results of experiments are evaluated by these metrics: average consumed energy and running time (the lower is better). Result can be seen in figure~\ref{fig:boundhole_bcp}.

\begin{figure*}[t]
\centering
\subfigure[Comparison of consumed energy]{
\epsfig{width=0.46\textwidth,file=boundhole_bcp_energy.eps}
\label{fig:boundhole_bcp_energy}}
\hfill
\subfigure[Comparison of running time]{
\includegraphics[width=0.46\textwidth]{boundhole_bcp_runtime.eps}
\label{fig:boundhole_bcp_runtime}}
\caption{Comparison between the Boundhole and the BCP approaches}\label{fig:boundhole_bcp}
\end{figure*}

We can see in Fig~\ref{fig:boundhole_bcp}, the Boundhole approach gives better result with slightly less consumed energy and running time.
It appears that the Boundhole uses simpler operations while the BCP uses a bit too many floating-point operations (especially, when computing circle-circle intersections). 

\subsection{Experiment Deployment and Settings}

\begin{figure*}[bth]
	\centering
	\minipage{0.45\textwidth}\label{tabu:DREonDNT}
	\centering
		\input{table_deadnode_false_positive}
    \endminipage
	\hfill
	\minipage{0.45\textwidth}
        \epsfig{file=deadnode_false.eps, width=1\columnwidth} % figure2.eps is a standalone file in EPS format
        \label{diag:DREonDNT}
    \endminipage
	\caption{\label{fig:DREonDNT}
    Effect of DNT on the Death Report Error}
\end{figure*}

\begin{figure*}[bth]
	\centering
	\minipage{0.45\textwidth}
	\centering
	\input{table_deadnode_approximate_ratio}
	\endminipage
	\hfill
	\minipage{0.45\textwidth}
	\epsfig{width=1\columnwidth,file=deadnode_area.eps}
	%\caption{}
	%\label{fig:deadnode1}
	\endminipage
	\caption{\label{fig:ARonDNT}Effect of DNT on Approximation Ratio}
\end{figure*}

\begin{table*}[bth]
	\centering
	\minipage{0.45\textwidth}
	\centering
	\input{table_deadnode_false_positive_slow}
	\caption{Effect of DNT on DRE with the Slow Expansion script}
	\label{tab:DREonDNTwithSE}
	\endminipage
	\hfill
	\minipage{0.45\textwidth}
	\centering
	\input{table_deadnode_approximate_ratio_slow}
	\caption{Effect of DNT on AR with the Slow Expansion script}
	\label{tab:ARonDNTwithSE}
	\endminipage
\end{table*}

We have proposed our very first algorithmic solution to deal with a possibly new and challenging problem of hole expansion in WSN. Bellow we show our initial results in evaluating our algorithm through experiments by simulation. Here we propose to use the following metrics to evaluate our algorithm performance:

\begin{itemize}
	\item The \emph{Approximation Ratio} (AR) is the ratio between the area that our algorithm approximately describes of a hole and the true area of this hole.
	\item The \emph{Death Report Error} (DRE) reflects how well we monitor the dead nodes, which is calculated as $\frac{|RN-TN|}{TN}$ where $RN$  is the number of nodes reported as dead by our algorithm and $TN$ is the true number of the dead nodes.
	\item The \emph{Consumed Energy} (CE) of network which is computed as the average energy consumed by the nodes in the network.
\end{itemize}

More specifically, we study the effect of choosing the following parameters, crucial in our algorithm, in achieving good performance by the above mentioned metrics.

\begin{itemize}
	\item \textit{Dead Node Threshold} (DNT): All the alive nodes periodically sends the HELLO packets to their neighbor nodes, hence in our algorithm after waiting for a time period called DNT if a node does not receive the next HELLO from a certain neighbor, this node can decide that this neighbor is dead.
	\item \textit{Notification Threshold} (NTT): As described in section~\ref{sec:proposed_scheme}, the pivot of a black/gray square decides to send a NOTIFY packet to each of its $4$ neighbor squares (to notify about the hole expansion) when the ratio of the number of dead nodes (per the total) in its square exceeds a NTT.
	\item \textit{Report Threshold} (RPT): The pivot of a black square decides to send a REPORT packet to the nearest sink when the ratio of the number of dead nodes in this square exceeds a RPT.
\end{itemize}

We run the experiments on the ns-2 simulator (802.11 as MAC protocol). Table~\ref{tab:simu_param} summarizes the parameters which are suggested by~\cite{SHCWW04}. In our simulation, about $2500$ sensor nodes are deployed randomly in an area of $1400m \times 1400m$.

We conduct three different simulation settings to evaluate the effect of these parameters on three metrics described above.
Also in our simulation settings, we deploy two different scripts of a large hole expanding: one is called Fast Expansion (EF), where we focus on, and the other Slow Expansion (SE). In each script we program so that the hole gradually expands from a chosen center point toward a fixed given shape, which is a random set of points with distances to the center varying randomly from a minimum value ($300$ m) to a maximum value ($450$ m). The hole reaches its maximum, final shape in $1000$ seconds in our FE script, and $2500$ seconds in our SE script. We believe that these scripts would reflect reasonably to the expansion of a typical forest fire.
\subsection{Simulation results}

\setlist[enumerate]{itemindent=\dimexpr\labelwidth+\labelsep\relax,leftmargin=0pt}

\begin{enumerate}
	\item \textit{Effect of Dead Node Threshold:} We conducted the simulation with four values of the Dead Node Threshold (DNT): $1$x, $1.3$x~\footnote{A HELLO packet may be sent a bit later than expected due to some random delay in processing; thus, we take this into account by using DNT$=1.3$x.}, $2$x, $3$x, where $n$x means the DNT equals $n$ times of the HELLO period (at which the HELLO packets being periodically sent from a node to a neighbor).

\begin{table}[h]
  \begin{center}
  \begin{tabular}{l r} \hline
    \textit{Variables} & \textit{Values} \\ \hline
    Communication range & 40m \\
    Voltage & 3V \\
    Receiving current & 15mA \\
    Transmitting current & 29.5mA \\
		Idle current & 3.2mA \\
		Network size & $1400m \times 1400m$ \\
		Number of nodes & 2500  \\
		Period of HELLO packet & 30s  \\
		Simulation time & 1050s for SE, 2500s for FE  \\ \hline
  \end{tabular}
  \end{center}
  \caption{Simulation parameters}
	\label{tab:simu_param}
\end{table}

\begin{figure*}[bth]
\centering
\subfigure[Effect of NTT on Consumed Energy\protect\linebreak(with 3 different cell size-settings)]{%
\epsfig{width=0.45\textwidth,file=notify_energy.eps}%
\label{fig:notify1}%
}
\hfill
\subfigure[Effect of NTT on Approximation Ratio\protect\linebreak(with 3 different cell size-settings)]{
\includegraphics[width=0.45\textwidth]{notify_area.eps}
\label{fig:notify2}}
\caption{Effect of Notification Threshold (NTT) with FE script}\label{fig:notify}
\end{figure*}
\begin{figure*}[bth]
\subfigure[Effect of NTT on Consumed Energy\protect\linebreak (with 2 different cell size-settings)]{
\epsfig{width=0.45\textwidth,file=notify_energy_slow.eps}
\label{fig:notify1_SE}}
\hfill
\subfigure[Effect of NTT on Approximation Ratio\protect\linebreak (with 2 different cell size-settings)]{
\includegraphics[width=0.45\textwidth]{notify_area_slow.eps}
\label{fig:notify2_SE}}
\caption{Effect of Notification Threshold(NTT) with the SE script}\label{fig:notify_SE}
\end{figure*}

Fig.~\ref{fig:DREonDNT} and~\ref{fig:ARonDNT} show the simulation results of our first simulation settings (with the Fast Expansion script) on the effect of DNT on the Death Report Error (DRE) and the Approximation Ratio (AR), respectively. It can be seen that the DRE tends to decrease with the increasing of the time values during the simulation. That is, for all the different DNT values, the trend is that the performance keeps improving (DRE gets close to $0\%$ and AR gets close to $1$) along the the simulation process (better performance for captures at later simulation moments - larger timestamps).

With the case of $1$x, the DRE is very large at first: it can be explained as because the HELLO packets and responses may get delayed or stuck (and dropped) at some nodes; therefore, when the threshold is too short, the nodes whose HELLO packets are delayed or dropped are wrongly judged as dead nodes (so DRE very large, initially). However later the HELLO packets (and its responses) can be retransmitted and thus, the nodes which have been judged as dead can be reconsidered as alive and so the DRE decreases.

The simulation results also shown that $FN-TN$, the difference between the number of reported dead nodes and the true number of dead nodes, tends to decrease when the DNT increases. Especially, with the DNT $=2$x or larger $FN-TN$ is even negative, i.e. the number of the dead nodes determined by our algorithm is less than the true number of real dead nodes. This is because, when the DNT increases, the pivots tend to become dead too early to send alerts about its cell situation to the neighbor cells, thus many dead nodes may not be recognized. It can be seen that, the DRE in case of $1.3$x is closest to $0$ and thus, parameter DNT $=1.3$x can be considered (near) the best for maintaining low DRE.

Fig.~\ref{fig:ARonDNT} represents the relation between the approximation ratio (AR) and the DNT. Similarly as with the DRE, the AR decreases with the increasing of the DNT. The AR with the DNT $=1$x is quite greater than $1$ and the AR with the DNT as $2$x/$3$x is often/always (much) smaller than $1$. It can be seen that the hole area determined by our algorithm is always much larger than the real hole with the DNT as $1$x and always much smaller than the real hole with the DNT $=3$x (or quite smaller with $2$x). For the later phase of hole expansion, both $1.3$x and $2$x seem competing for the best AR (but in both sides of $1$).
Overall, it can be seen that a small enough DNT value may lead to a high DRE because of many alive nodes being wrongly judged as dead while a large enough DNT value may make unreasonably small AR because of many dead nodes being unrecognized. For our experiment setting with the FE script, the DNT$=1.3$x seems (near) the optimum option.

So far we have just analyzed the simulation with the FE script, where the considered hole expands to the maximum distance $450m$ (from the center) in only $1000sec$, we now take a quick look at the results with the SE script (reaching maximum distance in $2500s$). As can be seen in Table.~\ref{tab:ARonDNTwithSE} and table.~\ref{tab:DREonDNTwithSE}, the choice of DNT$=2$x results in poor AR while still quite good at keeping low DRE. For keeping AR close to $1$, the ideal DNT value should be between $4$x and $5$x, however with this range the DRE is rather high (compared to that of DNT$=2$x). This is because for a larger DNT the network acts slower with the hole expansion and hence, a number of new dead nodes cannot get reported fast enough. Thus, in fact for the SE script we face a complexity in choosing good DNT (further work needed in future work).

\item \textit{Effect of Notification Threshold:} The effect of the NTT on the Consumed Energy (CE) and Approximation Ratio (AR) is shown in Fig.~\ref{fig:notify}. In this simulation setting with the FE script we fix DNT$=1.3$x (as seen best from simulation results above). Another parameter needs taken into account is the size of the unit grid square which we choose within $80m-120m$ (ranges in small multiples of the sensor transmission range, $40m$).

It is clear that, the consumed energy becomes lesser for larger NTT as well as for smaller grid square (cell) sizes. That is for a larger NTT, the pivots of the black cells need to wait longer to notify its neighbor squares, i.e. the squares become gray later rather than sooner, lessening the monitoring work and hence, reducing the CE incurred due to our monitor mechanism. Also, for smaller cell sizes, obviously the total area being monitored is also smaller and thus, reducing the consumed energy as well.

The effect of the NTT on the AR is reported in Fig.~\ref{fig:notify}(b). It can be seen that the AR decreases with the increasing of the NTT. It can be explained as below. For smaller NTT values, the notification of the expanding hole is done earlier and hence, the gray area tends to get large earlier, i.e. the AR tends to increase.  For AR greater than $1$, the approximate area of the hole is larger than the real hole area. When the NTT is larger enough (from about $15$\%) the AR can be smaller than $1$ (for grid size $100$m or less). This is because the times to send NOTIFY packets may come too late (with a speed slower than the expansion speed of the hole) and thus, many black pivots may get dead before the time to notify their neighbor cells. Consequently, some should-be-black squares get unrecognized and the approximate hole area becomes smaller than the real hole area.

It can be remarked that the NTT should be selected in accordance with the speed of the expansion of the hole. When the hole expands fast, we should choose a small NTT. Particularly, in this simulation setting with the FE script, the best NTT is about $15\%$.

For our simulation with the SE script (see Fig.\ref{fig:notify_SE}), the AR becomes close to $1$ for NTT about $25-30\%$, larger than the setting with the FE script, which is an advantage for keeping the gray squares in smaller number. However, the CE looks quite higher to that in the setting with the FE script. This is because the gray/black squares live longer in this SE setting and hence more monitor traffic would get incurred. Of course, one would consider to use a smaller grid size but this would result in need of low NTT which is a disadvantage. Thus, again we face some complexity in choosing proper parameter values that needs further consideration in our future work.

Fig.~\ref{fig:demo} illustrates the growth of the real hole area (represented by the orange line) and the approximate hole area determined by our algorithm (represented by green line) with images captured at $4$ different time values.
\begin{figure*}[t]
\centering
\subfigure[Captured at 120s]{
\includegraphics[width=0.2\textwidth]{demo_120.eps}
\label{fig:demo_120}}
\hfill
\subfigure[Captured at 360s]{
\includegraphics[width=0.2\textwidth]{demo_360.eps}
\label{fig:demo_360}}
\hfill
\subfigure[Captured at 600s]{
\includegraphics[width=0.2\textwidth]{demo_600.eps}
\label{fig:demo_600}}
\hfill
\subfigure[Captured at 840s]{
\includegraphics[width=0.2\textwidth]{demo_840.eps}
\label{fig:demo_840}}
\hfill
\caption{The growth of the approx. and the real hole areas\\(DNT$=1.3$x; NTT$=15\%$; RPT$=15\%$)}
\label{fig:demo}
\end{figure*}

\item \textit{Effect of Report Threshold:} The simulation result in this aspect is shown in Fig.~\ref{fig:report} where we also fix DNT $=1.3$x and we evaluate only the AR because the energy consumption is not affected much by the RPT. It can be seen that the AR tends to decrease when the RPT increases; especially if the RPT $\le 30\%$, the AR becomes $\ge 1$, i.e. the approximate hole area is larger than the real hole area. However if the RPT is $\ge35\%$, the AR becomes less than $1$.

    This is because, for RPT small enough the pivots report to the sink about the approximate hole soon enough (after discovering a small enough fraction of the dead node in the their squares), thus the approximate hole area, which is the area defined by the black squares (called the black area), tends to contain the real hole area and hence, the AR is greater than $1$. The smaller is the RPT, the larger is the difference between the black area and the real hole are and thus, the larger is the AR. However, for RPT large enough (e.g. $\ge 35\%$), some pivots may get dead before the time to send a REPORT packet to the sink and thus, their black squares are not reported to the sink, i.e. the AR becomes less than $1$.

Similarly as with the NTT evaluation, it can be concluded that the RPT should be selected in accordance with the speed of expansion of the hole. For example, in this simulation setting, the best RPT is about $30\%$.

\begin{figure}[t]
\centering
\epsfig{width=0.4\textwidth,file=report_area.eps}
\caption{Effect of RPT on the Approx. Ratio}
\label{fig:report}
\end{figure}
\end{enumerate}
