\newtheorem{mydef}{Definition}
\newtheorem{myfact}{Fact}

\subsection{Scheme Overview}
\label{Scheme_Overview}
Our goal is to detect and update the hole as fast as possible so that our hole monitor scheme can beat the expanding speed of a hole. Therefore, we aim to determine the approximate shape of the hole boundary rather than its exact shape. The approximate shape of the hole boundary is determined via a set of the unit squares of a given grid (with certain predefined unit length) which are affected by the hole, i.e. ether intersecting the hole boundary or staying inside the hole.

Our hole monitor scheme consists of two protocols: the hole boundary detection protocol, denoted by the HBD protocol, and the hole boundary update protocol, denoted by the HBU protocol. Let us discuss the basics of the HBD protocol first. The main idea is to have some nodes on the hole boundary detect that they are on a hole's boundary. This initial awareness helps to start the process of learning about the whole hole shape by arranging a special monitor packet to travel around the hole: this packet is being forwarded from one boundary node to another as a neighbor. Technically, we know of two main approaches in detecting a hole boundary, one from the research works on geographic routing in WSNs e.g. in~\cite{FGG04}, and one from the research work on wireless hole coverage e.g.~\cite{KYX13}. We have done certain probing experiments and found out that the former approach appears more efficient (we show our experimental evaluation on this in section~\ref{sec:evaluation}) and thus, we choose to use this approach for designing our HBD protocol where we aim at approximating the hole shape in a distributed manner.
%%Our approximation scheme is based on using a square grid which divided the plane into unit grid squares (with certain predefined unit length).

Based on the above mentioned approach, our HBD protocol is conducted by using the \textit{stuck nodes} introduced in~\cite{FGG04}: by definition, a node $u$ is considered a stuck node if there exists a position $w$ outside $u$'s transmission range such that $u$ is closer to $w$ than all the neighbor nodes of $u$~\footnote{Thus, a task of forwarding to destination $w$ would gets `stuck' at node $u$ if greedy routing is being used}. Note that a stuck node always stays on a hole boundary but not all the boundary nodes are stuck node. Each stuck node can detect its status as being stuck (using the TENT rule~\cite{FGG04}) and then creates a hole-monitor packet, which contains a HBA message (denoted for Hole Boundary Approximation), and forwards it to the next neighbor, boundary node (determined by the right hand rule~\cite{FGG04}). The mission of this HBA message is to record the approximate shape of the path it has gone through: at each boundary node, the HBA gets updated about the new, just traveled edge.
Upon reaching the next stuck node, a HBA message has fulfilled its mission by capturing the approximate shape of the boundary segment between this pair of successive stuck nodes, which will be forwarded to the nearest sink node (via a cell pivot node that we will introduce later). Note that each boundary segment (a chunk between two successive stuck nodes) is determined and approximated by using a separate HBA message. The sink node combines information received from all these stuck nodes (via the pivot nodes) and sends the whole info to the central node.

We now discuss the HBU protocol. %
Because the holes can enlarge quickly we want to have each update action performed as fast as possible to reflect well with the changes. Therefore, instead of determining the changes after happening we predict and update the changes of the hole boundary based on the prediction. Specifically, we monitor the status of the nodes (i.e. of being alive or dead) in the unit grid squares (also called cells) around the hole boundary. When the amount of the dead nodes of a given cell exceeds a predefined threshold, this cell is predicted to belong the hole soon and thus the hole area gets updated by adding that cell. To make the mechanism distributed, the task of monitoring within each unit square is performed by a so-called pivot node of this cell. The cell pivot is a sensor node (by default, the one closest to the center of the square) that is elected from all the nodes locating inside the cell.

During the HBD protocol, when a HBA message is about to fulfill its mission (and then stop being forwarded), the receiving stuck node can initiate the election of the pivot node of its cell if not selected yet, then forward the HBA info to this pivot.

\subsection{Bitmap Representation}

The main idea of our approximation mechanism is to describe the status of the cells (unit grid squares) in the network area by a bitmap representation where each bit would reflect if a corresponding cell belongs to a hole or not. More specifically, let $m \& n$ denote the width and length of the network; we use a grid with the edge length (of the unit squares) $a$ that divides the network into $ ([\frac{m}{a}]+1) \times ([\frac{n}{a}+1]) $ cells. We use a two dimension array $bmp[.][.]$ to represent the status of the cells, where $bmp[i][j]$ corresponds to the unit grid square whose center has the coordinates $(1/2+i)a$; $(1/2+j)a$ and $bmp[i][j] = 1$ if the corresponding cell belongs to a hole (i.e. this cell stays inside this hole or intersects its boundary) or else, $bmp[i][j] = 0$.

During the execution of the HBD protocol, the chunks of a hole's boundary (boundary segments between two successive stuck nodes) are approximated and these approximation info pieces are recorded into the HBA messages, which then are later forwarded to the sink(s) for being combined. To facilitate this computing mechanism, below we formally define bitmap representations as data structures to keep data at the HBA messages as well as at the pivots and the sink(s).

\begin{mydef}[Bitmap representation]
%For each node N in thenetwork, the bitmap representation of N is defined as a two dimension array $bmp_N[][]$, where $bmp_N [i][j] = 1$ if and only if the unit grid square with the coordinates of the center of $(1/2 + i)a; (1/2 + j)a$ contains N and belongs to at least one hole; $bmp_N [i][j] = 0$, otherwise.
For a line segment $l$ on the plane, the bitmap representation of $l$ is defined as a two dimension array $bmp_l[.][.]$, where $bmp_l[i][j] = 1$ if and only if $l$ intersects the unit grid square whose center's coordinates are $((1/2 + i)a, (1/2 + j)a)$; $bmp_l[i][j] = 0$, otherwise.

We call the bitmap representation of the whole network a two dimension array $bmp$, where $bmp[i][j] = 1$ if and only if the unit grid square whose center's coordinates $((1/2+i)a, (1/2+j)a)$ belongs to a hole and $bmp[i][j] = 0$, otherwise.
\end{mydef}

\begin{figure}[htb]
  \begin{center}
    \epsfig{file=bitmap2.eps,width=0.6\columnwidth} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{\label{fig:bitmap}Illustration of bitmap representation}
\end{figure}

Fig. \ref{fig:bitmap} illustrates a network with a big hole. The unit grid squares which intersect the hole are colored black. The bitmap representation of line segment $N_1N_2$ is
$\begin{bmatrix}
0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$
and the bitmap representation of the network is
$\begin{bmatrix}
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$. %

In the HBD algorithm, the bitmap representations of the boundary segments are determined by using HBA messages and sent to the local cell pivots, which forward these info pieces to the sinks. During the HBU algorithm, the pivots of the newly alarmed cells (who have been alarmed about the expanding hole after the HBD's execution) keep monitoring the hole and reports its status to the sinks as a black cell (belonging to the hole) when the number of the dead nodes inside exceeds a predefined threshold. The sinks maintain their bitmap representations (as about the network from their viewpoints) and periodically report them to the central node, which can combine these pieces into the bitmap representation of the whole network  by simple bitmap XOR operations.

% TODO: add this section to describe Algorithm \ref{alg1}
\subsubsection{Forwarding Mechanism with Compact Hole Info}
The main goal of our scheme is to monitor the hole(s) and update the sink(s) with any new status of the network shape. Our algorithm scheme is fully distributed where several nodes independently and concurrently capture info about pieces of a hole's boundary and forward towards the sink(s) via the cell pivots -- the intermediate hubs. The bitmap presentations of the network are only formed at the sink(s), however ``pieces" of that being formed and forwarded at node- and pivot- levels, at which sending a hole bitmap would be too much a luxury to afford (by a piece we mean a chunk of adjacent nodes on the hole boundary). In fact, the bitmap presentation of a line segment, or even a full hole's boundary (a collection of segments) can be compactly described, i.e. specifically, stored into memory as follows. Starting with an end vertex of the line segment (or any of the hole boundary polygon) we store the full coordinates (indexes) of its cell and then continually check the adjacent vertices for newly separate cells, per each of which store just two bits for describing its relative position to the preceding cell~\footnote{It only needs two bits to describe $4$ possible directions that may involves left, right, up and down}. By this mechanism, even a complex full hole boundary can be compactly described (as for reflecting the bitmap presentation of the network)by just the coordinates of a cell plus a rather short binary string (just a few bytes) as illustrated in~\ref{fig:compact_form}.

% TODO: end

\begin{figure}[htb]
  \begin{center}
    \epsfig{file=compression_form.eps,width=0.7\columnwidth}
  \end{center}
  \caption{\label{fig:compact_form}Compact Hole Info}
  \footnotesize{This hole can be reflected by the coordinate of cell $S$ plus a string of $24$ bits to locate the remaining 12 cells at the hole boundary.}
\end{figure}

\subsection{Hole Boundary Detection Algorithm}
This section discusses further details of our HBD algorithm.

At the initial, all the network nodes detect if each is a stuck node by using the TENT rule described in~\cite{FGG04}. Each stuck node then creates its HBA message and sends it to the left boundary neighbor node (using the right hand rule~\cite{FGG04}) which then forwards it towards the next stuck node. Here we use the forwarding mechanism as suggested in~\cite{FGG04} but the HBA message is customized to reflect $bmp_s$ -- the bitmap representation of the boundary segment between the two successive stuck nodes. When a node $N$ on the hole boundary receives the HBA message, it determines the cells intersecting the line segment connecting $N$ and the previous boundary node by the algorithm suggested in~\cite{LQHV11} and updates $bmp_s$ and the HBA message accordingly. In deployment of HBD algorithm, to reduce size of data transfers between node, we make compress this bitmap representation and use this compression form instead of full bitmap representation form. The details are described in algorithm $1$.
\begin{figure}[htb]
  \begin{center}
    \epsfig{file=detect.eps,width=0.6\columnwidth} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{\label{fig:detect}Illustration of hole boundary detecting algorithm}
\end{figure}

\begin{algorithm}
\caption{Algorithm to update compression form of bitmap representation $bmp_{comp}$}
\label{alg1}
\begin{algorithmic}
    \REQUIRE P: HBA packet; $N_c(x_C, y_C)$: current node and its coordinate; $N_P(x_P, y_P)$: previous node and its coordinate
    \ENSURE updated $bmp_{comp}$

    \STATE $bmp_{comp} \leftarrow$ the compression form from packet $P$
    \STATE $tmp \leftarrow$ transfering $bmp_{comp}$ into bitmap
		\STATE $U \leftarrow$ set of the unit grid squares which intersect $N_CN_P$
		\FORALL{the unit grid square $U_i(x_i, y_i)$ in $U$}
			\STATE $tmp[\left \lfloor \frac{x_i}{a} \right \rfloor][\left \lfloor \frac{y_i}{a} \right \rfloor] \leftarrow 1$
			\IF{$\left ( \left \lfloor \frac{x_i}{a} \right \rfloor \neq \left \lfloor \frac{x_P}{a} \right \rfloor \right ) and \left ( \left \lfloor \frac{y_i}{a} \right \rfloor \neq \left \lfloor \frac{y_P}{a} \right \rfloor \right )$}
				\STATE Send a election packet to $U_i(x_i, y_i)$.
			\ENDIF
		\ENDFOR
    \STATE $bmp_{comp} \leftarrow$ transfer $tmp$ into compression form
    \STATE update $P$ with new $bmp_{comp}$
\end{algorithmic}
\end{algorithm}
To prepare for the hole boundary update (HBU) phase, the HBD algorithm not only detects the hole boundary but also determines the pivots of the cells intersecting the hole boundary. Such a pivot is determined by the following algorithm. Each node $u$ receiving a HBA message determines the cell(s) which intersect the line segment connecting $u$ and the previous boundary node $v$ but does not contain $v$; there may exist none, one, or more such cell; for each such a cell if exists, $u$ sends a pivot election message towards this cell's center. Note that, such a message then stops at the node $w$ where none of its neighbors is nearer to the cell center than $w$, i.e $w$ can see it as elected as the cell pivot. Each pivot then broadcasts a pivot announcement message to all the nodes in the cell.

Fig. \ref{fig:detect} illustrates the algorithm. In the figure, the yellow nodes $S_1$, $S_2,\ldots,S_5$ found themselves as stuck nodes using the TENT rule. They initiate and forward the HBA messages along the boundary (using the right hand rule to determine the next boundary neighbor) until each arriving at the next stuck node. So, the HBA message initiated by $S_i$  is forwarded until arriving at $S_{i+1}$ wherein this message captures the bitmap representation of the line segment of the boundary between $S_i$ and $S_{i+1}$. For example, the bitmap representation of the segment between $S_1$ and $S_2$ is
$\begin{bmatrix}
0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$. After the HBD algorithm finishes, the approximate shape of the hole as well as the pivots of the cells surrounding the hole are determined. In Fig. \ref{fig:detect}, the approximate shape of the hole is colored black and the pivots are colored red.

\subsection{Hole Boundary Update Algorithm}
We discuss further details on the HBU protocol.
As mentioned above, se call an unit grid square, i.e. a network cell,  belonging to a hole (i.e. staying inside the hole or intersecting its boundary) a \textit{black} one. After the HBD phase finishes, each black cell has a pivot elected. All nodes in these black cells notify their status (i.e. whether alive or not) to its cell's pivot periodically.

When the ratio of the number of the dead nodes (over the total) of this cell exceeds a predefined threshold, which we call \textit{Notification Threshold}(NTT), the situation with this expanding hole is seen serious. Thus, the cell's pivot sends an alert message to each of the four neighbor cells which share an edge with it to notify about the high possibility that they would soon get affected by the hole, i.e. these four are considered \textit{gray} (becoming black). Note that some of these neighbors may have already been black cells wherein this alert simply gets ignored. Also, the destination of such an alert is set to be the center of the targeted gray cell and thus, the last node receiving the alert is elected as the pivot of this gray cell.

When the ratio of the number of dead nodes in a black cell exceeds a predefined threshold, which we call \textit{Report Threshold} (RPT), the cell is considered severely damaged by the hole and thus, this dangerous state gets reported to the nearest sink by the cell pivot.

Similarly to the pivot of a black cell, the pivot of a gray cell also monitors the status of all the nodes within the cell. When the ratio of the number of the dead nodes of this cell exceeds the NTT, the cell situation gets serious and thus, it turns into a black one. At this same time the cell's pivot sends an alert to its four neighbor cells (notification) to make any white remainder of them to become \textit{gray}.
The details of the algorithm's operations executed at gray/black cells after the NBD time are described in algorithm~\ref{alg2}.

Fig.~\ref{fig:update} illustrates an example. In this figure, the network is divided into $4 \times 3$ unit grid squares. The black nodes are dead and others are alive. After conducting the HBD algorithm, the hole boundary has been detected and the cells that belong the hole are colored black as shown in Fig.~\ref{fig:updating1}. The red nodes $P_1,P_2,\ldots,P_6$ represent the pivots of the black cells. Suppose that, the hole is expanding to the right, then after sometime some nodes in square $(6)$ die, which is enough to make pivot $P_6$ send an alert to the neighbor squares as shown in Fig.~\ref{fig:updating2}. Among these neighbors, $(0)$ and $(5)$ are already black which ignore the alert; the others i.e. squares (7) or (8) are still white, so become gray. The cell center nodes $P_7$ and $P_8$ then become the pivots of (7) and (8), respectively -- Fig.~\ref{fig:updating1}. When the ratio of the number of dead nodes in $(7)$ exceeds NTT, it is considered black and $P_7$'s pivot sends alerts to the neighbor cells -- Fig.~\ref{fig:updating4}.
\begin{figure*}[tb]
	\centering
	\subfigure[]{
		\epsfig{width=0.2\textwidth,file=updating1.eps}
		\label{fig:updating1}}
	%\hspace{0.1cm}
	\subfigure[]{
		\epsfig{width=0.2\textwidth,file=updating2.eps}
		\label{fig:updating2}}
	\subfigure[]{
		\epsfig{width=0.2\textwidth,file=updating3.eps}
		\label{fig:updating3}}
	\subfigure[]{
		\epsfig{width=0.2\textwidth,file=updating4.eps}
		\label{fig:updating4}}
	\caption{\label{fig:update}An example of hole boundary updating process}
\end{figure*}
\begin{figure*}
	%	\minipage{0.8\textwidth}
	\centering
	\subfigure[a(2) = 1]{
		\epsfig{height=3.2cm,file=offline-m.eps}
		\label{fig:offline-m}}
	\hfill
	\subfigure[a(2) = 0 and a(3) =1]{
		\epsfig{height=3.2cm,file=offline-n.eps}
		\label{fig:offline-n}}
	\hfill
	\subfigure[a(2) = 0 and a(3) = 0]{
		\epsfig{height=3.2cm,file=offline-p.eps}
		\label{fig:offline-p}}
	\caption{Algorithm to determine hole boundary from bitmap representation}
	\label{fig:offline-approximation}
	%	\endminipage
\end{figure*}

\begin{algorithm}
\caption{HBU process at nodes in a white cell ($state = WHITE$) when receives a message}
\label{alg2}
\begin{algorithmic}
    \REQUIRE $P$: received message, $C$: the current node
		\ENSURE

		\IF{$P$ is an alert message}
			\STATE $state \leftarrow GRAY$
      \IF{$C$ is the closest node of center}
        \STATE $C$ takes responsibility of the cell pivot
        \STATE Broadcast a notification to all nodes in the cell
      \ELSE
        \IF{$C$ has not received a pivot notification}
          \STATE Forward $P$ to the center of cell (Vote the closest node of center as the pivot node)
        \ENDIF
      \ENDIF
    \ELSIF{$P$ is a notification message}
      \STATE  Be informed that the source of message as the elected pivot
    \ELSE
      \STATE Send HELLO packet
		\ENDIF
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{HBU work at nodes in a gray cell ($state = GRAY$)}
\label{alg3}
\begin{algorithmic}
  \REQUIRE $C$: current node
	\ENSURE
\STATE LOOP periodically
	\IF{$C$ is a pivot}
    \STATE $d \leftarrow$ the number of dead nodes in the cell
		\IF{$d > NTT$}
      \STATE $state \leftarrow BLACK$
      \STATE Send alert packet to $4$ neighbor cells
    \ENDIF
  \ELSE
    \STATE Send HELLO packet to update node's state
	\ENDIF
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{HBU work at nodes in a black cell ($state = BLACK$)}
\label{alg4}
\begin{algorithmic}
  \REQUIRE  $C$: current node
	\ENSURE
\STATE LOOP periodically
	\IF{$C$ is a pivot}
    \STATE $d \leftarrow$ the number of dead nodes in the cell
		\IF{$d > RPT$}
      \STATE Report to the nearest sink
    \ENDIF
  \ELSE
    \STATE Send HELLO packet to update node's state
	\ENDIF
\end{algorithmic}
\end{algorithm}

\subsection{Hole Information Combination}

At the central node, we obtain the bitmap representation of the whole network. Although this bitmap gives us a view of location of the holes, in some applications (e.g. in geographic routing) geometric expressions (i.e. polygonal shapes) of the holes are required. We now describe an algorithm to determine the boundary of a hole approximate shape as a polygon, called an A-polygon, which satisfies the following condition:
\begin{itemize}
	\item This A-polygon vertices are the vertices of the grid squares which intersect the hole
	\item All the centers of the unit grid squares belonging to the hole stay inside this A-polygon
\end{itemize}
We will compute the (coordinates of) the vertices of this A-polygon in the clockwise order.
The following fact helps to show the process during each step for obtaining the next vertex; this fact is quite simple so we omit the proof.

In fact~\ref{fact_squares}, we consider the scenario where we have just determined that $G_i$ and $G_{i+1}$ are two consecutive vertices of the A-polygon (in the clockwise order), and we need to determine the next vertex. Let (1), (2), (3), (4) denote the unit squares that has $G_{i+1}$ as a vertex and let $M, N$ and $P$ denote the adjacent vertices of $G_{i+1}$ in (2), (3) and (4), respectively as shown in Fig. \ref{fig:offline-approximation}. Let ($x_i$, $y_i$) be the coordinates of the center of square (i) and $\alpha(i)$ be the corresponding bit value of square (i) in the network bitmap, then:

\begin{myfact}
\label{fact_squares}
Having $G_i$ and $G_{i+1}$ just determined as the vertices of an A-polygon from the given network bitmap, the next vertex of this A-polygon (in the clockwise order) can be determined as follows:
\begin{itemize}
\item	$M$ if and only if $\alpha(2)=1$ (Fig. \ref{fig:offline-m}).
\item	$N$ if and only if $\alpha(2)=0$ and $\alpha(3)=1$ (Fig. \ref{fig:offline-n}).
\item	$P$ if and only if $\alpha(2)=0$ and $\alpha(3)=0$ (Fig. \ref{fig:offline-p}).
\end{itemize}
\end{myfact}

Using fact~\ref{fact_squares}, we come up with algorithm \ref{alg3} below to determine an A-polygon of a hole from the network bitmap. It is easy to observe that for a given hole the vertex of the unit square (intersecting it) with the lowest $y$-coordinate must be a vertex of the A-polygon.

\begin{algorithm}
\caption{Algorithm to determine A-polygon from array $bmp$}
\label{alg3}
\begin{algorithmic}
    \REQUIRE bitmap $bmp$; $(x_A, y_A)$: coordinates of boundary node A that has lowest $y-coordinate$
    \ENSURE $G$: the set of vertices of the A-polygon

		\STATE Denote $r$ as the edge length of the unit square
		\STATE $G \leftarrow G \bigcup \left (\left \lfloor \frac{x_A}{r} \right \rfloor r + r, \left \lfloor \frac{y_A}{r} \right \rfloor r \right)$
		\STATE $G \leftarrow G \bigcup \left (\left \lfloor \frac{x_A}{r} \right \rfloor r, \left \lfloor \frac{y_A}{r} \right \rfloor r +r\right)$
    \WHILE{the top element of $G \neq \left (\left \lfloor \frac{x_A}{r} \right \rfloor r + r, \left \lfloor \frac{y_A}{r} \right \rfloor r \right)$}
			\STATE $U \leftarrow$ the top element of $G$
			\STATE $(x_u,y_u)$ is the coordinate of U
			\STATE $V$ is the previous element of U
			\STATE $(x_v,y_v)$ is the coordinate of V
			\\{//\textit{the following code is for the case when $y_u=y_v$, the other case ($x_u=x_v$) is similar}}\\
			\STATE $i \leftarrow \lfloor \frac{x_v}{r} \rfloor; j \leftarrow \lfloor \frac{y_v}{r} \rfloor - 1$
			\IF{$bmp[i-1][j] = 1$}
				\STATE $G \leftarrow G \bigcup (x_v, y_v - r)$
			\ELSE
				\IF{$bmp[i-1][j+1] = 1$}
					\STATE $G \leftarrow G \bigcup (x_v - r,y_v)$
					\STATE $G \leftarrow G \setminus (x_v,y_v)$
				\ELSE
					\STATE $G \leftarrow G \bigcup (x_v, y_v + r)$
				\ENDIF
			\ENDIF
		\ENDWHILE
\end{algorithmic}
\end{algorithm}
