\documentclass[11pt,twoside]{article}
\usepackage{informat}
\usepackage{epsfig}
\usepackage{epstopdf}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumitem}

\begin{document}
  \title{A Distributed Algorithm For Monitoring Hole Boundary in Wireless Sensor Network}
   \author{Nguyen Khanh Van \\
      Hanoi University of Science and Technology\\
      vannk@soict.hust.edu.vn\\
    \AndAuthor
      Phan Van Hau \\
      Hanoi University of Science and Technology\\
      pvhau93@gmail.com\\
    \AndAuthor
      Nguyen Phi Le \\
      Hanoi University of Science and Technology\\
      lenp@soict.hust.edu.vn\\
    \AndAuthor
      Nguyen Duc Trong \\
      Iowa State University\\
      trong@iastae.edu
   }
  \titleodd{Informatica}
  \authoreven{Nguyen Duc Trong et al.}
  \keywords{wireless sensor network, dynamic hole}
  \received{April 5, 2016}

  \abstract{Holes in sensor network are regions without operating nodes which may occur due to several reasons, including cases caused by natural obstacles or disaster suffered areas. Determining the location and shape of holes can help to monitor these disaster events (such as volcano, tsunami, etc.) or help to make smart, early routing decisions for circumventing a hole. There are many hole determination algorithms have been proposed in the literature. However, all of these algorithms only consider the networks with static holes. Moreover, most of these protocols are conducted in the centralized manner which is not suitable with the resource constraint of the sensor nodes. In this paper, we propose algorithms not only to determine the hole but also to quickly update the hole when it is enlarged. The algorithms are conducted in a distributed manner and the simulation results shown that our protocol is lightweight and feasible with the resource limitation of sensor network.}
  \abstractSi{
  % resume
  }

  \maketitle

\section{Introduction}
Consider the following scenario. There is a forest which frequently occurs fire in summer. As it is very large and difficult to access by human, an airplane is sent out to deploy thousands of wireless sensor nodes. Due to the cost limitation, these sensor nodes are equipped just with a temperature and humidity sensors, 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 via the sinks. Paradoxically, when the fire occurs, the sensor nodes in the areas of the on going fire may be destroyed and thus cannot perform their monitor task as well as report us about the fire. To solve this problem, a common approach is letting the alive nodes surrounding the fire areas detect the area of the fire. This is a well-known problem in sensor network which is called hole 1 detection and determination.

The hole detection and determination problem is not only used to detect the events that are being monitored as described above but also widely applied in geographic routing. Geo-graphic routing [1][2] which exploits the local geographical information at the GPS-equipped sensors is widely accepted for its simplicity and efficiency. Geographic routing works well and can achieve the near-optimal routing path length in networks without holes, however with the occurrence of the holes, the path length can grow as much as $\theta (c^2)$ when the holes present, where c is the optimal path length [3]. 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 hole detour routes [4][5][6][7][8].

There are many hole detection and determination algorithms have been proposed which can be classified into three categories: geometric methods, statistical methods and topo-logical methods [9]. However, these algorithms just considered the problem of detecting the static hole (hole whose boundary never changes). Moreover, almost of these algorithms are conducted in the centralization manner and is time ineffective. In this paper, we propose a novel approach to detect and update the hole boundary, that to the best of our knowledge is the first one that targets to dynamic holes (i.e. holes whose boundary change frequently). Our protocol not only help to detect but also to update the change of the hole boundary. Specially, we target to the networks whose holes occur and change very quickly, thus we need very fast hole detecting and updating algorithms.

In our protocol, the network is divided into small grid squares by a given grid. The squares are classified into three groups: black, gray and white. The black group contains the squares which already belonged to some holes, the gray group contains the squares which have not belonged to any hole but have high probability to stay inside some holes in the future, the white contains the remainder. Each square in the black and the gray group is monitored by a pivot which is elected from the sensors in that square. These pivots monitor the status of the sensors and help to classify the squares into white, gray and black groups. Hole is defined as a set of the black squares.

The contribution of this paper are threefold:

\begin{itemize}
  \item We propose a distributed hole detection algorithm which determines the hole very quickly.
  \item We propose a distributed hole updating algorithm which predicts the enlargement of the hole boundary and reports the prediction before the enlargement occurs.
  \item We conduct simulations to evaluate our protocol and confirm its feasibility and advantages for WSN.
\end{itemize}

The remainder of the paper is organized as follows. Our hole detecting and updating protocol is proposed in section II. Section III evaluate the performance of our protocol using simulation. We also discuss further on more related work in section IV and finally conclude the paper in section V.


\section{Our Hole Monitor Scheme}

\subsection{Scheme overview}
Our goal is to detect and update the hole as fast as possible so that our hole monitor scheme can beat the enlarging 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{}, and one from the research work on wireless hole coverage e.g. ~\cite{}. 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 $4$) 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{} [10]: 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 creates a hole-monitor packet, which contain a HBA message (denoted for Hole Boundary Approximation), and forwards it by the right hand rule [10] until arriving at the next stuck node. 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 a separate HBA node. 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}

Let m, n be the width and length of the network. We use a gird with the edge length of the unit square of a to divide the network into $ ([\frac{m}{a}]+1) \times ([\frac{n}{a}+1]) $ unit grid squares. We use a two dimension array $bmp[][]$ to represent the status of the unit grid squares, where $bmp[i][j]$ corresponds to the unit grid square with the coordinates of the center of $(1/2+i)a$; $(1/2+j)a$ and $bmp[i][j] = 1$ if the corresponded unit grid square belongs to a hole (i.e. intersects the hole boundary or stays inside the hole) and $bmp[i][j] = 0$, otherwise.

Definition 1 

For a line segment l on the plane, the bitmap representation of l is defined as a two dimension array bmpl[][], where bmpl[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$ intersects l and belongs to at least one hole; bmpl[i][j] = 0, otherwise.

Bitmap representation of the network is a two dimension array bmp[][], where bmp[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 belongs to at least one hole and bmp[i][j] = 0, otherwise.

\begin{figure}[htb]
  \begin{center}
    \epsfig{file=author1.eps,width=75mm} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{Illustration of bitmap representation}
\end{figure}

Figure 1 illustrates a network with a big hole. The unit grid squares which intersect the hole are colored black. The bitmap representation of node $N_1$ is
$\begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$
, of line segment $N_1N_2$ is
$\begin{bmatrix}
0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$
and bitmap representation of network is
$\begin{bmatrix}
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$
. In the hole boundary detection algorithm, the bitmap representation of the boundary segments form the source stuck nodes to the destination stuck nodes are determined by HBA messages and sent to the sink nodes by the destination stuck nodes. In the hole boundary update algorithm, when the number of the dead nodes exceeds the threshold, the pivot of the unit grid squares. which is predicted to belong to the hole soon, calculates their bitmap and sends to the nearest sink. The sinks combine the bitmaps received from all the destination stuck nodes by XOR operation before sending to the central node periodically. At the central node, the bitmaps received from all the sinks are XORed again to get the bitmap of the network. Note that, thanks to bitmap representation, the sinks and centrals just need to conduct XOR operation to combine the information received from the sensor nodes. The simplicity of the XOR operation make the protocol to be fast.

\subsection{Hole boundary detection algorithm}

All nodes find if they are the stuck nodes using TENT rule described in [10]. Each stuck node then creates the Hole Boundary Approximation (HBA) messages and sends to its left neighboring node. This HBA message then is forwarded along the hole’s boundary until arriving at the next stuck node to determine the hole boundary. The forwarding algorithm is the one described in [10] but the forwarding message is customized to contain the bitmap representation of the boundary segment between the two stuck nodes (i.e. the source stuck node and the destination stuck node). Denote this bitmap as $bmp_s$. The source stuck node sets the value of the item of $bmp_s$ corresponding to its unit grid square to 1 before forwarding the HBA message to its neighbor. When a node N on the hole boundary receives the HBA message, it determines the unit grid squares intersecting the line segment connecting it and the previous boundary node by the algorithm proposed in [11] and updates $bmp_s$ by XORing with the bitmap representation of this line segment. The details are described in algorithm 1. After HBA message arrived at the destination stuck node, the destination stuck node XORing the bitmap representation in the HBA message with the bitmap representation of the line segment connecting it and the previous node and before sending the bitmap to the nearest sink.
\begin{figure}[htb]
  \begin{center}
    \epsfig{file=author1.eps,width=75mm} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{Illustration of hole boundary detecting algorithm}
\end{figure}

\begin{algorithm}
\caption{Algorithm to update $bmp_s$}
\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_s$
    \STATE $tmp \leftarrow bmp_s from packet P$
		\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 $SendPivotElectionToU_i(x_i, y_i)()$
			\ENDIF	
		\ENDFOR
\end{algorithmic}
\end{algorithm}
To prepare for the hole boundary update phase, the boundary detection algorithm not only detects the hole boundary, but also determines the pivot for each unit grid square intersecting the hole boundary. The pivot is determined by the following algorithm. Each node receiving the HBA message sends a pivot election message to the centrals of unit grid squares which intersect the line segment connecting it and the previous boundary node and does not contain the previous boundary node. Note that, these messages will stop at the nodes where none of their neighbors is nearer to the central of the unit grid square than them self. These nodes are elected as the pivots. The pivots then broadcast a pivot announcement message to all the nodes in the same unit grid square.
Figure 2 illustrates the algorithm. In the figure, the yellow nodes $S_1$, $S_2$, ...$S_5$ found them as the stuck nodes using TENT rule. They initiate and forward the HBA message by the right hand rule until arriving at the next stuck node. So, the HBA
message initiated by Si  is forwarded until arriving at and this message contain the bitmap representation of the line segment of the boundary from $S_i$ to $S_{i+1}$. For example, the bitmap representation in the HBA message forwarded from $S_1$ and $S_2$ is
$\begin{bmatrix}
0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}$
. After the algorithm finished, the approximate shape of the hole as well as the pivot of the unit grid squares surrounding the hole are determined. In the figure, the approximate shape of the hole is colored black and the pivots are colored red.

\subsection{Hole boundary update algorithm}

We call an unit grid square belonging to a hole (i.e. intersects the hone boundary or stays inside the hole) the black unit grid square. After the hole boundary detection phase finished, each black unit grid square has the pivot. All nodes in these black unit grid squares notify their status (i.e. whether alive or not) to its unit grid square’s pivot periodically. When the ratio of the dead nodes in a black unit grid square exceeds a predefined threshold $T_1$, the pivot sends an alert to four neighbor unit grid squares which share an edge with it to notify that they have a high capability to become the black unit grid square. These four neighbor unit grid squares are called gray unit grid squares. Note that, some of these neighbors may already be the black unit grid square, and in this case the nodes in these unit grid square just simply ignore the alert. Note that, the destination of the alerts are set to be the central of the gray unit grid squares and thus the last nodes receiving these alerts are elected as the pivots of the gray unit grid squares. Similar to the pivot of the black unit grid square, the pivot of the gray unit grid square also monitors the status of the nodes in the same unit grid square. When the ratio of the dead nodes of a gray unit grid squares exceeds a predefined threshold $T_2$, it is predicted to belong to some holes soon, thus it is colored black and the bitmap representation of its pivot is sent to the nearest sink by the pivot. The details are described in algorithm 2.
Figure 3 illustrates an example. In this figure, the network is divided into $4 \times 3$ unit grid squares. The black nodes are dead nodes and the others are alive nodes. After conducting the hole boundary detection algorithm, the hole boundary has been detected and the unit grid squares that belong the hole are colored black as shown in figure 3(a). The red nodes $P_1$, $P_2$, ...$P_6$ represent the pivot of the black unit grid squares. Suppose that, the hole is extended to the right, then after a time, some nodes in square (6) die, when the number of the dead nodes exceed the threshold $T_1$, the pivot $P_6$ sends alert to the neighbor squares as shown in figures 3(b). Among these neighbors, (0) and (5) are already the black squares, thus they ignore the alert, the others (i.e. square (7) and (8)) are not black squares yet, thus they become gray squares. As alert is sent to the center of the squares, the nodes which are nearest to the centers will be the pivots and thus $P_7$, $P_8$ become the pivot of (7) and (8) (3(c)). $P_7$, $P_8$ monitor the status of the nodes in their squares. When the number of the dead nodes in (7) exceed the threshold $T_2$, it is considered as black square and $P_7$ updates its bitmap representation to the sink as shown in figure 3(d).
\begin{algorithm}
\caption{Algorithm at black node and gray node}
\label{alg2}
\begin{algorithmic}
    \REQUIRE $state$: State of the square node belonging to
		\ENSURE
		
    \WHILE{$true$}
			\IF{$IsPivot$}
				\STATE $deadNumber \leftarrow CheckDeadNode()$
				\IF{$state = BLACK$ and $deadNumber > notification\_threshold$}
					\STATE $SendAlertPacket()$
				\ELSE
					\IF{$state = GRAY$ and $deadNumber > report\_threshold$}
						\STATE $state \leftarrow BLACK$
						\STATE $SendBmpToSink()$
					\ENDIF	
				\ENDIF
			\ELSE
				\IF{$state = WHITE$}
					\STATE $SendHelloToNeighbor()$
				\ELSE
					\STATE $SendUpdateToPivot()$
				\ENDIF
			\ENDIF
		\ENDWHILE
\end{algorithmic}
\end{algorithm}

\subsection{Hole information combination}

At the central node, we get the bitmap representation of the network. Although this bitmap give us a view of location of the holes, in some applications (e.g. geographic routing) the polygonal expression of the holes are required. In this section, we describe an algorithm to determine the boundary of the hole approximate shape as a polygon which satisfy the following condition:
\begin{itemize}
	\item Its vertices are the vertices of the grid squares which intersect to the hole
	\item All the central of the unit grid squares belonging to the hole stay inside of it
\end{itemize}
For the simplicity, we call the boundary of the hole approximate shape as A-polygon. We start with the following fact. This fact is quite simple so we omit the proof.
Note that, the vertices of the I-squares with the lowest y-coordinate are the vertices of the A-polygon.
Fact 1 Assume $G_i$ and $G_{i+1}$ are two consecutive vertices of the unit grid square that stay on boundary of the A-polygon in the clockwise order. Denote (1), (2), (3), (4) as the unit squares which has $G_{i+1}$ as an vertex and let M,N,P be the adjacent vertices of $G_{i+1}$ as shown in figure 4. Let (xi; yi) be the coordinates of the center of (i) and a(i) be the value of bmp, then:
\begin{itemize}
\item	M is an vertex of the A-polygon if and only if a(2)=1 (figure 4(a)).
\item	N is an vertex of the A-polygon if and only if a(2)=0 and a(3)=1 (figure 4(b)).
\item	P is an vertex of the A-polygon if and only if a(2)=0 and a(3)=0 (figure 4(c)).
\end{itemize}
Using this fact, we have the algorithm to determine the holes’ polygonal boundary as described in algorithm 3.
\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
			\COMMENT{the following pseudo 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}

\section{Performance evaluation}

\subsection{Simulation Scenario}

We run the experiments on the NS-2 simulator (802.11 as MAC protocol). Table 1 summarizes the parameters which are suggested by [12]. In our simulation, about 2000 sensor nodes are deployed randomly in an area of $1300m \times 1300m$. Below is the detail of the used metrics:

\begin{itemize}
	\item The approximation error is the ratio between the area of the hole determined by our algorithm and the real hole.
	\item The false positive ratio of the dead nodes is calculated as $\frac{FN-TN}{TN}$ where $FN$  is the number of dead nodes discovered by our algorithm and $TN$ is the number of real dead nodes.
	\item The energy consumption of network is the average energy consumed by the nodes in the network.
\end{itemize}

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

\begin{itemize}
	\item \textit{Dead node threshold}. In our simulation, the pivot periodically sends the HELLO packet to other nodes and waits for a \textit{dead node threshold}. Until this threshold, the nodes which do not response to the pivot will be considered as dead nodes.
	\item \textit{Notification threshold}. As described in section II, the pivot of black square sends the NOTIFY packet to the neighbor squares to notify about the enlargement of the hole when the ratio of dead nodes in its square exceeds a threshold. This threshold is called \textit{notification threshold}.
	\item \textit{Report threshold}. The pivot of gray square sends the REPORT packet to the sink when the ratio of dead nodes in this square exceeds a threshold and this threshold is \textit{report threshold}.
\end{itemize}	
We conduct three simulations to evaluate the affect of these parameters on three metrics described above.

\begin{figure*}[h] % '*' for two columns
  \begin{center}
    \epsfig{file=author2.eps, width=160mm} % figure2.eps is a standalone file in EPS format
  \end{center}
  \caption{Algorithm to determine hole boundary from bitmap representation}
\end{figure*}

\subsection{Simulation results}

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

\begin{enumerate}
	\item \textit{Affect of dead node threshold:} We conducted the simulation with four values of dead node threshold: 1x, 2x, 3x, 4x, where nx means the threshold is n times of the HELLO packet’s period.

\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 & 40s  \\
		Simulation time & 500s  \\ \hline
  \end{tabular}
  \end{center}
  \caption{Simulation parameters}
\end{table}

\begin{figure}[htb]
  \begin{center}
    \epsfig{file=author1.eps,width=75mm} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{Affect of dead node threshold}
\end{figure}

Figure 5(a) 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. Especialy, 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{Affect of notification threshold:} We conduct the simulation with the dead node threshold of 2x and 3x.
The affect 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 affect 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 affect 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}[htb]
  \begin{center}
    \epsfig{file=author1.eps,width=75mm} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{Affect of notification threshold}
\end{figure}

\item \textit{Affect 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}[htb]
  \begin{center}
    \epsfig{file=author1.eps,width=75mm} % figure1.eps is a standalone file in EPS format
  \end{center}
  \caption{Affect of report threshold}
\end{figure}

\end{enumerate}


\section{Related work}

Routing hole is a critical issue in geographic routing where data packets are forwarded based on the positional information of the sensor nodes (assuming that they are equipped with GPS devices). Early approaches are based on greedy and perimeter routing where with the former a packet is forwarded to the 1-hop neighbor that is closest to the destination. However, greedy forwarding can lead into the local minimum phenomenon whenever the packet encounters a routing hole. To bypass such a hole, the traditional schemes appropriately switch between greedy and perimeter forwarding modes (initiated by the GPSR proposal in [2]), in the later of which the data packets are forwarded along the hole boundary [2][13][14][15][16]. These proposals require a specific embedding of a planar graph (e.g. Gabriel Graph). However, Subramanian et al. ([17]) show that this perimeter routing could cause the throughput capacity of the whole network to significantly drop due to the concentration of traffic on the face of the holes. On a planar network with no holes, Gupta and Kumar's seminal paper [18] shows that a uniform traffic demand of $\Theta (1/\sqrt{n\ log\ n})$ is achievable. However, from [17] a large hole occupying a constant fraction of the network area can cause the throughput capacity to drop from $\Theta (1/\sqrt{n})$ to just $O(1/n)$. Also in the paper, Subramanian et al. proposed a randomized routing scheme which can achieve a near-optimal throughput capacity, which however appears merely of theoretical interest (the overhead traffic can be extremely large in practice).

The arguable shortcomings in using costly GPS devices and complicated planarization process can be avoided by using virtual coordinates as in [19][20][21][22][23]. In such a proposal, the nodes are assigned with virtual coordinates in metric X and the algorithm forwards packets greedily in X. Although better than early greedy routing schemes, this greedy embedding approach still does not always guarantee successes and also has a serious shortcoming: the virtual coordinates would incur rather heavy re-computation upon any minor change in the physical WSN.
An algorithmic approach for locating holes in WSN has been formally introduced in [10] where Fang et al. propose a procedure to obtain the exact boundary of the hole as a polygon with vertices being adjacent nodes on the hole side. In [11], we introduce an efficient and flexible approach and techniques to approximate the shape of a hole.
There exists other proposals using a similar approach to our learn-and-disseminate strategy, e.g. [24][5][4], however, the main aim there is to achieve a bounded route stretch. As a result, although achieving a desired route stretch, these schemes can incur heavy extra communication in broadcast and significant load imbalance due to congestion on these major routes. For example, in [4], the holes are compactly described as a set of extreme points of the convex hull covering the boundary nodes and thus, the hole detour will be along these points, that may cause the traffic concentration around the boundary of the convex hull.

\section{Conclusion and Future work} % conclusion and discussion; just discussion etc.
% Conclusion text.

% bibliography style is not predefined; authors can apply their own,
% but it should be sent to matjaz.gams@ijs.si with the accepted paper
\begin{thebibliography}{99}

  \bibitem{} Y. Ko and N. H. Vaidya (1998) Location-Aided Routing (LAR) in Mobile ad hoc Networks, {\it Proc. of MOBICOM’98}.

	\bibitem{} B. Karp and H. T. Kung (2000) GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, {\it Proc. of MOBICOM’00}, pp. 243--254.
	
	\bibitem{} Fabian Kuhn, Roger Wattenhofer, Yan Zhang, and Aaron Zollinger (2003) Geometric ad-hoc routing: of theory and practice, {\it In PODC}, pp. 63-72.

	\bibitem{} Myounggyu Won, Radu Stoleru, and Haijie Wu (2011) Geographic routing with constant stretch in large scale sensor networks with holes, {\it Proc. of WiMob}, pp. 80-88.

	\bibitem{} Z. Zheng, K. W. Fan, P. Sinha, and Y. Wang (2008) Distributed roadmap aided routing in sensor networks, {\it 5th IEEE International Conference}, pp. 347–352.
	
	\bibitem{} Y. Tian et al (2008) Energy-Efficient Data Dissemination Protocol for Detouring Routing Holes in Wireless Sensor Networks, {\it Proc. of IEEE Intl. Conf. on Communications, ICC’08}, pp. 2322–2326.

	\bibitem{} F. Yu et al (2008) Efficient Hole Detour Scheme for Geographic Routing in Wireless Sensor Networks, {Proc. of the 67th IEEE Vehicular Technology Conference, VTC’08}, pp. 153-157.

	\bibitem{} M. Choi and H. Choo (2011) Bypassing Hole Scheme Using Observer Packets for Geographic Routing in WSNs, {\it Proc. of Intl. Conf. on Information Networking, ICOIN’11}, pp. 435-440.

	\bibitem{} Yue Wang, Jie Gao, and Joseph S.B. Mitchell (2006) Boundary recognition in sensor networks by topological methods, {\it 5MobiCom’06}.
	
	\bibitem{} Q. Fang, J. Gao, and L. J. Guibas (2004) Locating and Bypassing Routing Holes in Sensor Networks, {\it Proc. of INFOCOM’04}.
	
	\bibitem{} N. P. Le, B. T. Quan, N. T. Hieu, and N. K. Van (2011) Efficient approximation of routing holes in wireless sensor networks, {\it ACM Proc. of the Second Symposium on Information and Communication Technology}.
	
	\bibitem{} Victor Shnayder, Mark Hempstead, Bor rong Chen, Geoffrey Werner-Allen, and Matt Welsh (2004) Simulating the power consumption of large scale sensor network applications, {\it SenSys}, ACM, pp. 188-200.
	
	\bibitem{} P. Bose, P. Morin, I. Stojmenovir, and J. Urrutia (2008) Routing with guaran-teed delivery in ad hoc wireless networks, {\it 5th IEEE International Conference}, pp. 347-352.
	
	\bibitem{} F. Kung, R. Wattenhofer, and A. Zollinger (2002) Asymptotically Optimal Geometric Mobile Ad-hoc Routing, {\it Dial-M}.
	
	\bibitem{} F. Kung, R. Wattenhofer, and A. Zollinger (2003) Worst-Case Optimal and Average-Case Efficient Geometric Ad-hoc Routing, {\it Proc. of ACM MobiHoc}.
	
	\bibitem{} F. Kung et al (2003) Geometric Ad-hoc Routing: Of Theory and Practice, {\it Proc. of ACM PODC}.
	
	\bibitem{} S. Subramatian, S. Shakkottai, and P. Gupta (2007) On Optimal Geographical Routing in Wireless Networks with Holes and Non-Uniform Traffic, {\it Proc. of IEEE INFOCOM}.
	
	\bibitem{} Piyush Gupta and P. R. Kumar (2000) The capacity of wireless networks, {\it IEEE Transactions on Information Theory}, pp. 388–404.
	
	\bibitem{} A. Rao, C. H. P., S. Shenker, and I. Stoica (2003) Geographic Routing without Location Information, {\it Proc. of ACM MOBICOM 2003}, pp. 96-108.
	
	\bibitem{} Q. Fang, J. Gao, L.J. Guibas, V. de Silva, and L. Zhang (2005) Glider: Gradient Landmark-based Distributed Routing for Sensor Networks, {\it Proc. of IEEE INFOCOM}, pp. 339-350.
	
	\bibitem{} R. Fonseca, S. Ratnasamy, J.Zhao, C.T. Ee, D.E. Culler, S. Shenker, and I.Stoica (2007) Beacon Vector Routing: Scalable Point-to-point Routing in Wireless Sensornets.
	
	\bibitem{} A. Caruso et al (2007) GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks {\it INFOCOM}, pp. 150-160.
	
	\bibitem{} R. Kleinberg (2007) Geographic Routing Using Hyperbolic Space, {\it IEEE INFOCOM}, pp. 1902–1909.
	
	\bibitem{} G. Tan, M. Bertier, and A.-M. Kermarrec (2009) Visibility-graph-based shortest-path geographic routing in sensor networks, {\it Proc. of IEEE
INFOCOM}, pp. 1719–1727.

\end{thebibliography}

\end{document}
