Let start by considering an example scenario of a forest wherein fire rather frequently occurs in summer. Since it is very large and difficult to access and monitor by human, one thinks of using helicopters to disseminate thousands of wireless sensor nodes through out this forest area for deploying a fire monitor system. Due to the cost limitation, these pieces are equipped with just a temperature and humidity sensing device, a very simple processing unit and a small radio communication module that allows them to communicate with the others in their communication range. The mission of these sensor nodes is to monitor the environment, detect the fire and report to a central host via some special sink nodes (with more powerful resource). Paradoxically possibly when the fire occurs, the sensor nodes in the area of an on-going fire can be destroyed and thus cannot perform their monitor task and fail to report about the fire. To solve this problem, a common approach is letting the alive nodes surrounding the fire areas detect the boundary of the fire area fast enough and report to the central host. This scenario belongs to a well-known problem in sensor network which is called \emph{hole detection and determination}.

The hole detection-determination (HDD) problem is not only used to detect the events that are being monitored as described above but also is, and in fact known more as, an important technical issue in geographic routing. Geographic routing~\cite{KV98}\cite{KK00} which exploits the local geographical information at the sensors is popular for its simplicity and efficiency. The traditional geographic routing strategy works well and can achieve the near-optimal routing path length in networks without holes, however with the occurrence of network holes, the path length can grow as much as $\theta (c^2)$ where $c$ is the optimal path length~\cite{KWZZ03}. In order to solve the problem of path enlargement, a common approach is to determine the hole boundary, describe it by a simpler shape whose information is disseminated to the surrounding area. This information will help to establish a hole awareness and mechanism to find short detour routes~\cite{WSW11}\cite{ZFSW08}\cite{Tal08}\cite{Yal08}\cite{CC11}.

There are many HDD algorithms proposed however, these just consider the problem of detecting a typically static hole (hole whose boundary never changes). Moreover, almost of these algorithms are conducted in the centralization manner and is time ineffective.
A very common approach is based on the possibility of \emph{having a monitor packet to travel a full route around the hole, which could be unlikely possible in our problem scenario -- the network hole can be expanding fast enough that could destroy any attempt to send a packet around in one simple loop}.

In this paper, we propose a novel approach to detect and regularly report about the hole boundary, that to the best of our knowledge is \emph{the first one that targets expanding holes} (whose boundary change continually). Especially, we aim at scenarios where holes can occur and grow rapidly; i.e.,  we aim to design fast algorithms for detecting and monitoring hole boundaries. Our main idea is actually to distribute this task of capturing the dynamic hole perimeter into the hands of several boundary nodes and network cells that are carefully selected to take this joint responsibility.

In our protocol, the network is divided into small grid squares by a given grid. The squares (cells) are to be divided into three groups: black, gray and white. A black square is one which already belongs to or is heavily affected by a hole, a gray square is not yet touched by any hole but is detected being close enough and getting soon affected by an expanding hole, and a white is a currently safe one. A white square can later get turned into a gray and then a black square when facing an expanding hole, which can be seen as a set of the black squares. Each square in the black and the gray group is monitored by a local node, called a pivot, which is elected from the sensors in that square. These pivots monitor the status of the sensors and the squares and help to manage the square status changes.

The contribution of this paper are threefold:

\begin{itemize}
  \item We propose a distributed hole detection algorithm which can determine a hole boundary efficiently with respect to time and energy saving.
  \item We propose a distributed hole updating algorithm which monitors the expansion of the hole boundary and reports regularly to the central host.
  \item We conduct initial experiments by simulation to analyze our protocol and evaluate its feasibility and advantages.
\end{itemize}

The remainder of the paper is organized as follows. Our hole detecting and updating protocols are proposed in section~\ref{sec:proposed_scheme}. Section~\ref{sec:evaluation} evaluates the performance of our protocol using simulation experiments. We also discuss further on related work in section~\ref{sec:related_work} and finally conclude the paper in section~\ref{sec:conclusion} with further concerns about open issues.

A preliminary version of this paper appears in~\cite{TLHV15}. Besides a significant revision effort for improving the clarity, formality and preciseness we also add new substantial elements to this full version.  That is we reshape and adjust some important parts in our proposed algorithm and thus make it more efficient; as a result, we redo the evaluation task but in a larger scale for obtaining a more insightful about the performance of our algorithm. Below we briefly mention the most important adjustments. In section 2.1, for the task of detecting a hole boundary we justify our decision to choose the approach used in~\cite{FGG04} over the one in~\cite{KYX13}. In section 2.2 we optimize the way we define and use Bitmap Presentation for reducing incurred communication overhead and delay. In 2.3 we tune the process of forwarding the hole boundary info towards the sink(s): the pivots fully involve in this process that increases the efficiency of the whole mechanism.

Compared to the previous version, moreover, we also extend our evaluation work to a significant deeper level where we redesign a new, significant larger set of simulation scenarios, inspired by new observations and thus obtain new findings.  Most notably, our 3 main simulation settings (for studying the effects of 3 system parameters: Dead Node Threshold, Notification Threshold \& Report Threshold) are all extended by our new deployment where we use two separate scripts to simulate an expanding hole: the Fast Expansion  and the Slow Expansion scripts. We focus more on the Fast Expansion scenario (a hole expands fast for simulating a forest fire) and we identify some value region of the Dead Node Threshold that could optimize our algorithm. We also extend our study on these main parameters with some initial consideration of the relationship with another variable that is the grid cell size. In spite of this rather extensive evaluation analysis there still remain many unknowns that can be challenging enough for good results in future work.
