An algorithmic approach for locating holes in WSN has been firstly introduced in~\cite{FGG04} where Fang \emph{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. The basic idea is to have a packet traveling around the hole, learning the position of the nodes on its side. Other follow-up works~\cite{KFPF06, WGM06, LWG09} study a generalized problem in computing the exact shape of the network as collection of boundaries, i.e. the outer perimeter of the whole network area and boundaries of inside holes. %These papers all are connectivity-based that they try to avoid using GPS devices.
In \cite{LQHV11}, we introduce an efficient and flexible approach and techniques to approximate the shape of a hole.

However, this approach is based on the possibility of having a 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. Our main solution is actually to distribute this task of capturing the hole perimeter: several HBA packets (sent by the stuck nodes) and later, the cell pivots are responsible to pick up a collection of segments of the hole perimeter.

There are many HDD algorithms have been proposed which can be classified into three categories: geometric methods, statistical methods and topo-logical methods. Geometrical approach uses the coordinates of the nodes and standard geometric tools (such as the Delaunay or Voronoi diagrams) to detect coverage holes and their boundaries. Several simple distributed algorithms have been proposed in \cite{MS11,ZYW11,Watfa06} to detect the boundary nodes (i.e. \emph{non-covered sensor} in our definitions) and build the routes around holes. In the topological approach, there are neither coordinates nor localization of nodes are required. Instead, this approach use topological properties such as the information of connectivity to identify the boundary nodes; e.g. Ghrist \emph{et al.}~\cite{GM05} proposed a purely connectivity-based coverage hole detection method.

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~\cite{KK00}), in the later of which the data packets are forwarded along the hole boundary~\cite{KK00}\cite{BMSU08}\cite{KWZ02}\cite{KWZ03}\cite{Kal03}. These proposals require a specific embedding of a planar graph (e.g. Gabriel Graph).

There are quite a few papers in geographic routing which propose to learn about the hole shape then disseminate this hole info to the surrounding area for supporting routing tasks performed later.  This approach as we call learn-and-disseminate strategy has been used in e.g.~\cite{TBK09}\cite{ZFSW08}\cite{WSW11}, however, the main aim there is to achieve a bounded route stretch in their routing algorithms. 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~\cite{WSW11}, 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.

We briefly review the two mentioned (in section~\ref{Scheme_Overview}) approaches in detecting a hole boundary, i.e. the work in~\cite{FGG04} for supporting geographic routing in WSNs and the work in~\cite{KYX13} for  solving the problem of wireless hole coverage. The BOUNDHOLE algorithm~\cite{FGG04} can be shortly described as follows. Each stuck node \emph{p} initiates a HBD message (denoted for Hole Boundary Detection) which includes its location and sends it to \emph{p}'s leftmost node with respect to the stuck angle. The leftmost node can be defined as follows: \emph{p} faces the area formed by the two rays of this angle, and uses the angle's bisector line to conduct counter-clockwise sweeping. The leftmost node is the first one that is met by the sweeping line. Upon receiving the HBD message, \emph{p}'s leftmost neighbor node writes its location into the message and passes it to the next-hop determined by the minimal sweeping angle from previous hop. The HBD message will finally come back to node \emph{p} from \emph{p}'s rightmost neighbor with respect to the initial investigated angle, where the right most neighbor is defined in the similar way as the leftmost node. Basically the HBD message creates a closed cycle that goes back to \emph{p}.

The coverage hole detection algorithm in~\cite{KYX13} is based on the concept of Boundary Critical Points (BCPs). A boundary critical point is defined as the intersection point of two sensing circles that cannot be covered by any other sensing circles. Each sensor node first computes its BCPs. Note that the sensors that are not along the boundary of any coverage holes cannot have any boundary critical point. Then each consecutive boundary critical points is connected by constructing an boundary line along the border of the nodes having those boundary critical points. The construction of boundary line is continued until the starting boundary critical point is revisited or border of the monitoring region is touched.
