\subsection{Simulation Scenario}

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$. Below is the detail of the used metrics:

\begin{itemize}
	\item The \emph{Approximation Ratio} (AR) is the ratio between the area that our algorithm approximately describe of a hole and the area of the real hole.
	\item The \emph{False Positive Ratio} (FPR) in reporting the number of the dead nodes, which is calculated as $\frac{FN-TN}{TN}$ where $FN$  is the number of dead nodes determined by our algorithm and $TN$ is the number of real dead nodes.
	\item The \emph{Energy Consumption} (ECN) of network which is computed as the average energy consumed by the nodes in the network.
\end{itemize}

Note that, these metrics are effected by the following parameters:

\begin{itemize}
	\item \textit{Dead Node Threshold} (DNT): All the alive nodes periodically sends the HELLO packet 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 conduct three simulations to evaluate the effect of these parameters on three metrics described above.

\begin{figure*}[bth]
	\centering
	\minipage{0.45\textwidth}\label{tabu:FPRonDNT}
	\centering
		\begin{tabular}{|c|l|l|l|l|}
		\hline
		\multicolumn{1}{|l|}{}                                         & \multicolumn{4}{c|}{False positive ratio}                                                                \\ \hline
		\begin{tabular}[c]{@{}c@{}}Simulation \\ time (s)\end{tabular} & \multicolumn{1}{c|}{1x} & \multicolumn{1}{c|}{2x} & \multicolumn{1}{c|}{3x} & \multicolumn{1}{c|}{4x} \\ \hline
		140                                                            & 25                & 1.9810                & 0                       & 0                         \\ \hline
		260                                                            & 27.6344                & 2.3028                & 0                       & 0                         \\ \hline
		380                                                            & 20.1743                & 3.1702                & 0.5764                 & 0                         \\ \hline
		500                                                            & 13.5384                & 3.0945                & 0.3868                & 0                         \\ \hline
		620                                                            & 10.4300                & 3.2780                & 0.7450                & 0                         \\ \hline
		740                                                            & 7.62610                & 2.7236                & 0.5447                & 0                         \\ \hline
		860                                                            & 6.08135                & 2.5194                & 0.8687                & 0.0868                  \\ \hline
		980                                                            & 5.0261                 & 2.2258                & 1.2206                & 0.0718                  \\ \hline
		420                                                            & 4.29526                & 1.9021                & 1.2885                & 0.0613                  \\ \hline
		460                                                            & 3.90191                & 1.7279                & 1.5607                & 0.2787                  \\ \hline
	\end{tabular}
    \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:FPRonDNT}		
    \endminipage
	\caption{\label{fig:FPRonDNT}
    Effect of DNT on the False Positive Ratio}
\end{figure*}

\begin{figure*}[]
	\centering
	\minipage{0.45\textwidth}
	\centering
	\begin{tabular}{|c|l|l|l|l|}
		\hline
		\multicolumn{1}{|l|}{}                                         & \multicolumn{4}{c|}{Approximation error}                                                                \\ \hline
		\begin{tabular}[c]{@{}c@{}}Simulation \\ time (s)\end{tabular} & \multicolumn{1}{c|}{1x} & \multicolumn{1}{c|}{2x} & \multicolumn{1}{c|}{3x} & \multicolumn{1}{c|}{4x} \\ \hline
		100                                                            & 39.6216                & 1.9810                & 0                       & 0                         \\ \hline
		140                                                            & 27.6344                & 2.3028                & 0                       & 0                         \\ \hline
		180                                                            & 20.1743                & 3.1702                & 0.5764                 & 0                         \\ \hline
		220                                                            & 13.5384                & 3.0945                & 0.3868                & 0                         \\ \hline
		260                                                            & 10.4300                & 3.2780                & 0.7450                & 0                         \\ \hline
		300                                                            & 7.62610                & 2.7236                & 0.5447                & 0                         \\ \hline
		340                                                            & 6.08135                & 2.5194                & 0.8687                & 0.0868                  \\ \hline
		380                                                            & 5.0261                 & 2.2258                & 1.2206                & 0.0718                  \\ \hline
		420                                                            & 4.29526                & 1.9021                & 1.2885                & 0.0613                  \\ \hline
		460                                                            & 3.90191                & 1.7279                & 1.5607                & 0.2787                  \\ \hline
	\end{tabular}
	\endminipage
	\hfill
	\minipage{0.45\textwidth}
	\epsfig{width=1\columnwidth,file=deadnode_area.eps}
	%\caption{}
	%\label{fig:deadnode1}
	\endminipage
	\caption{\label{fig:deadnode2}Effect of dead node threshold on approximation error}
\end{figure*}

\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): $1x$, $1.3x$, $2x$, $3x$, where $nx$ means the DNT values is $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 & $1300m \times 1300m$ \\
		Number of nodes & 29.5mA  \\
		Period of HELLO packet & 30s  \\
		Simulation time & 1050s  \\ \hline
  \end{tabular}
  \end{center}
  \caption{Simulation parameters}
	\label{tab:simu_param}
\end{table}

Figure~\ref{fig:FPRonDNT} shows the simulation result of false positive ratio. I can be seen that, for all of the dead node thresholds which are greater than 1x, the false positive ratio tends to decrease with the increasing of the simulation time while the false positive ratio with the threshold of 1x is opposite. With the dead node threshold of 1x, the false positive ratio is very large at first but then decreases. The reason is because the HELLO packet and its respond may be stuck and dropped at some nodes. Therefore, when the threshold is too short, the nodes whose packets are dropped are wrongly judged as dead nodes, thus the ratio is very large at first. After that, the HELLO packet (and its respond) are resent and the nodes which are judged as dead node before may be turned to alive nodes after, thus the false positive ratio decreases.
The simulation result also shown that, the false positive ratio decreases when the dead node threshold increases. Especially, with the threshold equals to 2x, 3x, 4x, the false positive ratio is negative. It means that, the number of dead nodes discovered by our algorithm is less than the number of real dead nodes. This is because, when the dead node threshold increases, the pivot may be dead before updating the status of the neighbors, thus many dead nodes may not be recognized. It can be seen that, the false positive ratio in case of 2x is approximate to 1 and this is the best one.

Figure 5(b) represents the relation between the approximation error and the dead node threshold. Similar with the false positive ratio, the approximation error increases with the increasing of the dead node threshold. The approximation error with the threshold of 1x is always much greater than 1 and the approximate error with the threshold of 4x is always much smaller than 1. This means that, the hole discovered by our algorithm always much larger than the real hole with the threshold of 1x and always much smaller than the real hole with the threshold of 4x. The dead node threshold of 2x and 3x shows the best performance.
From the simulation result, it can be concluded that, the small dead node threshold may lead to a high false positive ratio where many alive nodes are judged as dead node and thus the approximate hole become much larger than the real hole. Meanwhile, the large dead node threshold may cause many dead nodes to be unrecognized and thus the approximate hole become smaller than the real hole. The dead node threshold of 2x or 3x can be seen as the best options.

\item \textit{Effect of notification threshold:} We conduct the simulation with the dead node threshold of 2x and 3x.
The effect of the notification threshold on the false positive ratio is shown in figure 6(a). It is clear that, the greater is the notification threshold, the smaller is the consumed energy. The reason is because, when the notification threshold increases the pivot of the black squares need to wait more time to notify its neighbor squares. Therefore, the number of the gray squares tends to decrease and thus the number of the pivot decreases too. As the most energy is consumed by the activity of the pivots, the energy consumption decreases consequently. It can be seen that, the consumed energy with the notification threshold of 50\% and 60\% are almost the same. This is because, when the notification threshold is large, the number of the pivots is very small compared to the total number of nodes in the network. Therefore, the decrease of the number of the pivots does not effect much on the average consumed energy of the network.

Compare the consumed energy with the dead node thresh-old of 2x and 3x, we can see that the smaller dead node thresh-old consumed more energy. This can be explained that, when the dead node threshold decreases, the pivots can discover the dead node fast and thus the speed of sending notification to the neighboring squares as well as report to the sink also increases. Therefore, more notifications and reports are sent and thus more energy is consumed. Furthermore, the increase of the speed of sending notification causes more gray squares to be created and thus more pivots are created too and thus consumes more energy.

The effect of the notification threshold on the approximation error is represented in figure 6(b). It can be seen that, the approximation error decreases with the increase of the notification threshold. It can be explained as below. When the notification threshold is small, the pivots of the black square always notify the neighboring squares soon. Therefore, more nodes are monitored by the pivots. Consequently, more squares are become black square very soon and makes the approximate hole be larger than the real hole.

The approximation error is larger than 1 when the notifi-cation threshold is less than or equal to 50\%. It means that, the approximate hole is larger than the real hole with this values of the notification threshold. When the notification threshold is larger than or equals to 60\%, the approximation error becomes smaller than 1. This is because, the notification speed becomes slower than the enlargement speed of the hole and thus many pivots may dead before sending notify to the neighboring squares. Consequently, some black squares are unrecognized and the approximate hole becomes smaller than the real hole.

It can be concluded that, the notification threshold should be selected in accordance with the speed of enlargement of the hole. When the hole enlarges fast, we should choose a small notification threshold as it makes the pivots send the notification to the neighboring squares fast. Particularly, in this simulation, the best notification threshold is 50\%.

\begin{figure*}[t]
\centering
\subfigure[Evaluation of consumed energy]{
\epsfig{width=0.45\textwidth,file=notify_energy.eps}
\label{fig:notify1}}
\hfill
\subfigure[Evaluation of approximation error of hole area]{
\includegraphics[width=0.45\textwidth]{notify_area.eps}
\label{fig:notify2}}
\caption{Effect of notification threshold}\label{fig:notify}
\end{figure*}

Figure \ref{fig:demo} shows the captures of the real hole (i.e. represented by orange line) and the approximate hole determined by our algorithm (i.e. represented by green line).
In this captures, the dead node threshold and the notification threshold are \emph{2x} and $50\%$.
\begin{figure*}[t]
\centering
\subfigure[Capture at 120s]{
\includegraphics[width=0.2\textwidth]{demo_120.eps}
\label{fig:demo_120}}
\hfill
\subfigure[Capture at 360s]{
\includegraphics[width=0.2\textwidth]{demo_360.eps}
\label{fig:demo_360}}
\hfill
\subfigure[Capture at 600s]{
\includegraphics[width=0.2\textwidth]{demo_600.eps}
\label{fig:demo_600}}
\hfill
\subfigure[Capture at 840s]{
\includegraphics[width=0.2\textwidth]{demo_840.eps}
\label{fig:demo_840}}
\hfill
\caption{Captures of the approximate hole and the real hole}\label{fig:demo}
\end{figure*}

\item \textit{Effect of report threshold:} The simulation result is shown in figure 7. In this simulation, we evaluate only the approximation error because the energy consumption does not affected much by the report threshold. It can be seen that, when the report threshold is smaller than or equals to 60\%, the approximation error is larger than 1, means that the approximate hole is larger than the real hole. The increase of the notification threshold makes the approximation error decrease and when the report threshold is larger than or equals to 70\%, the approximation error becomes less than 1. This is because, when the notification threshold is small, the pivots report to the sink about the approximate hole soon after discovering a small amount of the dead node in the their square. As the area of the black square always greater than the area covering the dead nodes in that black square, the approximate hole is larger than the real hole. The smaller is the notification threshold, the larger is the error between the area of black square and the area covering its dead nodes and thus the larger is the approximation error. When the notification threshold is very larger (i.e. larger than or equals to 70\%), some pivots may dead before sending report to the sink and thus, theirs black holes are not reported to the sink. Consequently, the approximate hole determined at the sink and the central becomes smaller than the real hole.

Similar to the simulation of the notification threshold, it can be concluded that, the report threshold could be selected in accordance with the speed of enlargement of the hole. When the hole enlarges fast, we should choose a small notification threshold as it makes the pivots send the report to the neigh-boring squares fast. For example, inn this simulation, the best report threshold is 60\%.

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