# Detecting the Boundary of Sensor Networks from Limited Cyclic Information

Authors: Carlos Lara-Alvarez; Juan J. Flores; Chieh-Chih Wang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

We address the problem of finding the boundaries of a set of points by using a limited range-cyclic order detector. This sensor, denoted by lrcod, is able to detect nearby objects and enumerate them by their cyclic order; neither distance nor the angular position of each object is provided. Boundaries are important in many applications such as detecting the breakdown of networks, insufficient coverage or connectivity, abnormal functioning sensors, and virtual coordinates for routing. We studied the information space of the lrcod sensors and established their capabilities to find inner and outer boundaries. Our proposed approach uses local information to recognize points on the boundary. To discover the complete boundary we define theRight Hand Without Crossings (RHWoC) rule. We also provide a correctness proof of this rule. The experimental evaluation confirms the effectiveness to find the boundary of large sensor networks.


---

## Body

## 1. Introduction

Sensor networks can be seen as a large collection of nodes that reason about the state of the world, that is, their environment. Distributed sensing improves the signal-to-noise ratio because sensors are closer to the phenomena. Obtaining the boundary of a sensor network is important in many engineering applications. Boundaries are useful to detect the breakdown of a network, insufficient coverage or connectivity, abnormal functioning sensors, virtual coordinates for routing, and so forth. Boundary recognition is a challenging issue in wireless sensor networks [1]. The distinction between inner and boundary nodes of the network can provide valuable knowledge to a broad spectrum of algorithms. In practice, sensors are deployed randomly in a given area. Even if the initial deployment is known, the topology may vary because of sensors failure. Furthermore, many applications require dynamic sensors.Ad hoc networks are often modeled as unit disk graphs (UDG), where each point can reach other points in a given radius λ. Accurately defining the boundary of a UDG without a general position system (GPS) is a challenge that should not be underestimated.The problem we address in this paper is to find the boundaries of a set of points by using a limited range-cyclic order detector. This sensor, denoted bylrcod, can detect nearby objects and enumerate them by their cyclic order; neither distance nor the angular position of each object is provided. The lrcod sensor only measures the cyclic order, unlike bearing measurement systems, where the angle of each object is known. lrcod network can be implemented from visual sensors with miniaturized omnidirectional systems [2, 3]. Another implementation could use infrared based relative positioning sensors specially designed to enable interrobot spatial coordination [4, 5].Although the model studied in this paper considers a sensor network as its main application, many ideas developed here could be applied to other areas such as mobile robots. For mobile robots, landmarks are like sensors in a network, and the robot provides the communication link between them. Tovar et al. [6] consider a robot that moves in the plane and that is able to sense only the cyclic order of landmarks with respect to its current position. In contrast to [6], which considers an infinite range sensor model, this paper studies a sensor that can only detect objects at a maximum range of λ. A limited sensing model is more convenient for real applications; for example, laser scans have a maximum range, walls in indoor environments can occlude some objects, and so forth.The rest of the paper is organized as follows: Section2 introduces some basic definitions used along this paper. Section 3 describes the assumed network model and defines the problem. Section 4 describes how to detect a single point on a boundary and using it to recover the complete boundary. Section 5 describes the simulations and results obtained from the proposed algorithm, showing that it works under different conditions. Section 6 describes the related work. Finally, Section 7 concludes this work.


## 2. Basic Definitions

l
r
c
o
d is a sensor that gives the counterclockwise cyclic permutations of other sensors or landmark labels. This sensor is able to see landmarks only within a given distance; for a given sensor the parameter λ is the maximum range at which the cyclic order detector can sense a landmark. Henceforth, lrcod(x) is a function that returns the readings of the sensor; those readings are permutations of the set of sensor identifiers as seen from the point x∈R2. Figure 1 illustrates an example of the sequences of landmarks detected from two positions lrcod(v4)=[v5,v3,v1,v6] and lrcod(v3)=[v4,v5,v2].Figure 1
Sequence of landmarks detected by the sensor.lrcod(v4)=[v5,v3,v1,v6]; up to a cyclic permutation, landmark 2 cannot be detected because it is outside the reach of the sensor; analogously, lrcod(v3)=[v4,v5,v2]. Only the cyclic order is preserved; the sensed angular position of each landmark may be quite different from the real one.A set of landmarks is inR2. Let G=(V,E) be a connected graph where V is the set of landmark labels and E=x,y∣x,y∈V,x,y≤λ with (y≠x); here ·,· denotes the Euclidean distance between two points. An edge between two landmarks x,y∈V means that lrcod can detect the landmark y from landmark x and vice versa. We assume that graph G is connected; therefore every landmark is detectable from at least one other landmark.Circular Sector. Given two landmarks vi and vj seen from vx, we define Λ′(vx;vi,vj) as the points within the counterclockwise circular sector vivxvj. Let the output of the sensor be of the form lrcod(vx)=[A,vi,B,vj,C], in which A,B, and C are subsequences of lrcod(vx) separated by the labels corresponding to landmarks vi and vj; then Λ′(vx;vi,vj)=B and Λ′(vx;vj,vi)=C+A, where + is the concatenation of two sequences.The sensorvx shown in Figure 2 reads lrcod(vx)=[v3,v4,v5,v1,v2]. Landmarks v3,v5 define two sectors Λ′(vx;v3,v5)=v4 and Λ′(vx;v5,v3)=v1,v2.Figure 2
Orientation and circular sectors. Circular sectors detected fromlrcod: Λ′(vx;v3,v5)=v4 and Λ′(vx;v5,v3)=v1,v2.Walk. A walk in a graph G is a sequence W≔v0e0v1⋯vl-1el-1vl, whose components are alternately vertices and edges of G (not necessarily distinct), such that vi and vi+1 are the ends of edge ei, 0≤i≤l-1 [7]. We say that W connects the initial point v0 to the final point vl and refer to W as a v0vl-walk or simply v0Wvl. A walk in a graph is closed if its initial and terminal vertices are identical. In case of no confusion we use the succession of vertices W=v0v1⋯vl-1vl to denote the walk W=v0e0v1⋯vl-1el-1vl. The vertices of a closed walk also define a polygon P.Polygon. ApolygonP is a finite sequence P=v0v1⋯vp-1 of points in the plane. The set of edges of a polygon is E(P)=ei∣i=0,…,p-1, where ei is defined as an edge connecting vi and v(i+1mod⁡p).Simple Polygon. Asimple polygon is a polygon composed of nonrepeating vertices where none of its edges ei and ej, for i≠j, intersect at points different from their extremes.The Jordan curve theorem states that every simple closed curve divides the plane into an interior region bounded by the curve and an unbounded region containing all exterior points.Weakly Simple Polygon. A polygon P is weakly simple if, for any ϵ>0, there is a simple closed curve Q such that dF(P,Q)<ϵ, where dF is the Fréchet distance [8] between two polygons P and Q.In other words, a polygon is weakly simple if it can be made simple by an arbitrarily small perturbation of the entire curve. Informally, a weakly simple polygon is a polygon in which sides can touch each other but cannot cross. Any weakly simple polygonP partitions R2∖P into two regions: interior and exterior.λ-Polygon. A λ-polygonP is a weakly simple polygon where ei≤λ for all ei∈E(P).λ-Boundary. A λ-boundary orouter boundaryP of a set of points V is a λ-polygon such that V∖P lies in the interior of P.Diagonal. Adiagonal is a line that connects two nonconsecutive vertices of a polygon; aninner diagonal lies totally in the interior of the polygon.Hole. Ahole orinner boundary is an empty λ-polygon with vertices H⊂V such that every inner diagonal is larger than λ. A hole with n=|H| vertices will be called n-hole.


## 3. Network Model

Throughout this paper, we consider sensor networks that satisfy the following assumptions.(i)
The system is composed of a set of sensorsV, located in a region R⊂R2; each sensor v∈V has a distinctive identity.(ii)
Every sensorv∈V is able to detect lrcod(v).(iii)
All wireless sensors have the same maximum transmission rangeλ.Assumptions (i) and (iii) involve that each sensor can gather information from other sensors within its transmission range. Therefore, we can build a network graph whose vertices correspond to the labeled nodes and whose edges correspond to communication links. Henceforth, we will indistinctly call them sensors, nodes, or landmarks.Assumption (i) admits that sensors can move arbitrarily inR but they are static for a period of time τ long enough to recover the boundaries. Furthermore, we assume that landmarks are in general position (i.e., no three landmarks are collinear). Assumption (iii) is usual inad hoc networks modeled as unit disk graphs (UDG), where each point can reach other points in a given radius λ.Problem Definition. Given a network V of lrcod sensors, find the boundary polygon of V and its holes by using only the local information provided by the lrcod sensors.The task we are solving is to find the perimeter of a set of points; this task can be done by simply following the sequence of extreme points on the convex hull. Classical algorithms such as the Graham Scan [9] can be used to find theconvex hull (CH) of the point set.Unfortunately, following it by using thelimited range-cyclic order detector is in certain cases impossible, because the distance between two consecutive extreme points could be greater than the maximum range of the sensor. Hence, when following the CH of the set of lrcod sensors, the algorithm can reach a position where the sensor cannot see the next point in the CH, so it has to share information through other points inside the CH (points at sight) until the next point on the CH (not at sight before) is reached. Once it has done so, it can continue finding points on the CH. This approach is time consuming and sometimes unnecessary.


## 4. Proposed Algorithm

The proposed approach finds points on the boundary following the procedure described in Section4.1. Those points can be used as seeds to find the complete sequence of points on the boundary, as described in Section 4.2.


### 4.1. Boundary Points

This subsection presents a series of definitions and lemmas that are the basis for discerning boundary from inner points. According to our definition of holes aλ-polygon P formed by less than four points cannot be a boundary; hence, three connected points on the vertices of a triangle cannot form a hole; therefore, a hole must have at least four landmarks.λ-Point. A λ-point is a point vj for which ∃vi,vk∈lrcod(vj) such that Λ′(vj;vi,vk)= and vi∉lrcod(vk). Points vi,vk are calledadjacent boundary points of vj.


### 4.2. Detecting a Boundary fromλ-Points

This subsection addresses how to useλ-points as seeds to find the boundary sequence.Lethj and hj+1 be two consecutive points on the convex hull and let (hj,hj+1) be the line segment joining them. Since the graph G is connected, there exists at least one hjhj+1-walk. We are looking for the walk such that the area comprised by W′≔hjWhj+1(hj+1,hj)hj does not contain any landmark v∈V; we refer to the walk that satisfies this condition as apocket.Theright-hand rule (RH) is a heuristic rule that has been used extensively to deliver packages inad hoc networks [10]. It has also been used to find the convex hull for an unlimited cyclic sensor [6]. The right-hand rule states that if the last two previously visited vertices of a walk are vj-1,vj then the next vertex is the first vertex that appears immediately by turning right from the edge (vj-1,vj). When the greedy multi-hop forwarding algorithm gets stuck, the right hand rule can be used to go around holes.To complete a boundary starting from a border walk, we define theRight Hand Without Crossings(RHWoC)rule. Given a partial walk W′=[v0⋯vj-1ej-1vj] such that its last edge is (vj-1,vj), the RHWoC rule selects the first landmark vk in lrcod(vj) that follows vj-1 in the permutation such that the edge ej≔(vj,vk) does not intersect at a single point to any previous edge in the walk. To illustrate the RHWoC rule, Figure 4 shows an example to find the next point of the walk W=v1e12v2e24v4e46v6. When the point v6 is analyzed, v3 appears in the permutation immediately after point v4 but it is not selected because the edge (v6,v3) intersects the boundary; then the correct point v5 is selected.


### 4.3. Discovering Intersections

The RHWoC rule selects an edge that does not cross any previous edge in the border walk, but the border walkW could be a long sequence of vertices and edges. The following lemma states that when two edges intersect at a single point, at least one vertex of an edge must see at least one vertex of the other edge.Lemma 1.
Leteij=(vi,vj) and ekn=(vk,vn) be two edges, and let lrcodk,n:=lrcod(vk)∪lrcod(vn) be the landmarks seen from vk or vn. If (vi∉lrcodk,n)∧(vj∉lrcodk,n) then eij does not intersect ekn.Proof.
Wheneij and ekn intersect at a single point q, there exist two points va∈vi,vj and vb∈vk,vn such that vaq≤λ/2 and vbq≤λ/2. From the law of cosines it can be shown that va,vb≤λ; in other words, vb∈lrcod(va).We are interested in determining if two different edges intersect in a single point. When discovering crossing edges, the endpoints of two edges could be the same; hence, there is only one rather than two distinct edges. This condition is easily detectable and can be used to discover connectivity issues of the network such asbridges andarticulation points [11].Lemma2 states how to use the information provided by lrcod to detect that two edges in a walk intersect in a single point.Lemma 2.
Letvhehivieijvjejkvk⋯vm be a border walk, and let vn∈lrcod(vm) be a point seen from vm; edge en≔(vm,vn) intersects edge eij in a single point when vn∈Λj′(vk,vi)∧vn∈Λi′(vj,vh) and  lrcod(vn) is arranged as [vi,A,vk,B,vj,C] with A,B, and C subsequences of  lrcod(vn).Proof.
Figure5(a) illustrates this lemma for vm=vk. Every point satisfying vn∈Λj′(vk,vi)∧vn∈Λi′(vj,vh) is in the red shadow. When lrcod(vn)=[vi,A,vk,B,vj,C], meaning that vn is in the circular sector (of a large circle) vjvkvi, then ekn intersects edge eij.Corollary 3.
Letvj be a λ-point with adjacent boundary points vi,vk. If vn∉Λj′(vk,vi), ekn≔(vk,vn) does not intersect eij. In other words, a walk of four consecutive boundary points can be found from two consecutive λ-points.Proof.
Corollary3 follows directly from Lemma 2. In Figure 5(b), the edge (vk,vn) does not cross any edge when vn∉Λj(vk,vi). Point vk is also a λ-point because Λj′(vi,vk) is empty.Observation 1.
It is always possible to define intersections for a walk with four or more vertices by using Lemma2.Although it is useful to find inner diagonals of a hole,λ-points are better to find points on the boundary when two consecutive points on the convex hull cannot see each other. Sometimes small holes do not have detectable λ-points; for instance, the 4-hole shown in Figure 3(a) can be detected because Λj′(vk,vi) is empty, but Λj′(vk,vi)=v in Figure 3(b). Those undetectable cases never occur for points on the convex hull.Figure 3
(a) Detectable4-hole, the sensor vj reads an empty sector. (b) Nondetectable hole, all sensors on the hole read nonempty sectors.
(a)
(b)Figure 4
Finding the boundary from a partial walk. The boundary is recovered from the walkv1v2v4v6; point v5∈lrcod(v6) is selected because e65≔(v6,v5) does not intersect any previous edge.Figure 5
Discovering intersections. Using sectors and landmark ordering, one can determine when two edges intersect at a single point.
(a)
(b)
(c)Observation 2.
If there is only a singleλ-point (a walk with three points instead of four) then Corollary 3 can be used. We can define some other cases such as that shown in Figure 5(c) where vn∈Λj(vk,vi) and lrcod(vn) reads [vi,A,vk,B,vj,C]. Unfortunately, the limited range of the sensor prevents us from using this case for all situations because sometimes vi∉lrcod(vn). We say that the intersection is undetermined for the cases where we cannot determine if an edge intersects or not with another edge of a walk. In such cases, the boundary could be completed by using other λ-points.


### 4.4. Algorithm Overview

To find the boundaries of a set of pointsV we propose Algorithms 1 and 2. In Algorithm 1 each sensor first obtains local information (line 1), then it applies the definition of Section 4.1 to recognize two consecutive λ-points (lines 4–6). If the λ-point and its corresponding adjacent points are not already used, then a boundary (or a hole) has been detected and the function RHWoC is called (line 7). Function alg:closed recovers the complete border until it finds an edge that already is on the boundary. When no more borders can be found then the list L is returned (line 12).Algorithm 1:Boundary (V).
Data: A finite set of connected points  V⊂R2.
Result: A list L of the boundary and detectable holes of  V.
(1) Exchange sensor information between neighbors;
(2)L←{};
(3)foreach  vi∈V  do
(4)if  viisaλ-pointwithadjacentspointsva,vb
then
(5) W′←va(va,vi)vi(vi,vb)vb;
(6) if  W′isnotusedinLandvbisaλ-pointwithadjacentpointsvi,vc  then
(7)W← RHWoC (va,vi,vb,vc);
(8)L←L∪W;
(9) end
(10)end
(11)end
(12)return  LAlgorithm 2:Function RHWoC (vi-3,vi-2, vi-1, vi).
(1)ej←(vi-1,vi);
(2)vj-1←vi-1;
(3)vj←vi;
(4)W←vi-3vi-2vi-1vi;
(5)repeat
(6)L←lrcod(vj);
(7)Circular-rotate L until vj-1 is the last element of L;
(8)foreach  vk∈L  do
(9)  if  (k=j-1)or  (vj,vk)doesnotintersectanyedgeofW  then
(10)ej←(vj,vk);
(11)vj-1←vj;
(12)vj←vk;
(13)W←Wejvj;
(14)    break;
(15)end
(16)end
(17)until  (ej∉W);
(18)return  WCorrectness of Function RHWoC. Let W be the outer area reachable with the lrcod from vertices of W. At each step, the next landmark vk in the walk is selected according to the RHWoC rule. The rule’s precondition asserts that v1,…,vi-1 are λ-convex hole points; then W does not contain any landmark. For the following steps, RHWoC rule ensures that Sj=Λ′(vj;vj-1,vk)∩W does not contain any landmark. As ⋃∀vj∈W‍Sj=W and the walk never crosses itself, the Jordan theorem asserts that W is a boundary and the set of landmarks V∖W are in the same side of W. Finally, based on our connectivity assumption, the walk reaches a previously detected edge and the cycle of lines 5–17 terminates correctly.


## 4.1. Boundary Points

This subsection presents a series of definitions and lemmas that are the basis for discerning boundary from inner points. According to our definition of holes aλ-polygon P formed by less than four points cannot be a boundary; hence, three connected points on the vertices of a triangle cannot form a hole; therefore, a hole must have at least four landmarks.λ-Point. A λ-point is a point vj for which ∃vi,vk∈lrcod(vj) such that Λ′(vj;vi,vk)= and vi∉lrcod(vk). Points vi,vk are calledadjacent boundary points of vj.


## 4.2. Detecting a Boundary fromλ-Points

This subsection addresses how to useλ-points as seeds to find the boundary sequence.Lethj and hj+1 be two consecutive points on the convex hull and let (hj,hj+1) be the line segment joining them. Since the graph G is connected, there exists at least one hjhj+1-walk. We are looking for the walk such that the area comprised by W′≔hjWhj+1(hj+1,hj)hj does not contain any landmark v∈V; we refer to the walk that satisfies this condition as apocket.Theright-hand rule (RH) is a heuristic rule that has been used extensively to deliver packages inad hoc networks [10]. It has also been used to find the convex hull for an unlimited cyclic sensor [6]. The right-hand rule states that if the last two previously visited vertices of a walk are vj-1,vj then the next vertex is the first vertex that appears immediately by turning right from the edge (vj-1,vj). When the greedy multi-hop forwarding algorithm gets stuck, the right hand rule can be used to go around holes.To complete a boundary starting from a border walk, we define theRight Hand Without Crossings(RHWoC)rule. Given a partial walk W′=[v0⋯vj-1ej-1vj] such that its last edge is (vj-1,vj), the RHWoC rule selects the first landmark vk in lrcod(vj) that follows vj-1 in the permutation such that the edge ej≔(vj,vk) does not intersect at a single point to any previous edge in the walk. To illustrate the RHWoC rule, Figure 4 shows an example to find the next point of the walk W=v1e12v2e24v4e46v6. When the point v6 is analyzed, v3 appears in the permutation immediately after point v4 but it is not selected because the edge (v6,v3) intersects the boundary; then the correct point v5 is selected.


## 4.3. Discovering Intersections

The RHWoC rule selects an edge that does not cross any previous edge in the border walk, but the border walkW could be a long sequence of vertices and edges. The following lemma states that when two edges intersect at a single point, at least one vertex of an edge must see at least one vertex of the other edge.Lemma 1.
Leteij=(vi,vj) and ekn=(vk,vn) be two edges, and let lrcodk,n:=lrcod(vk)∪lrcod(vn) be the landmarks seen from vk or vn. If (vi∉lrcodk,n)∧(vj∉lrcodk,n) then eij does not intersect ekn.Proof.
Wheneij and ekn intersect at a single point q, there exist two points va∈vi,vj and vb∈vk,vn such that vaq≤λ/2 and vbq≤λ/2. From the law of cosines it can be shown that va,vb≤λ; in other words, vb∈lrcod(va).We are interested in determining if two different edges intersect in a single point. When discovering crossing edges, the endpoints of two edges could be the same; hence, there is only one rather than two distinct edges. This condition is easily detectable and can be used to discover connectivity issues of the network such asbridges andarticulation points [11].Lemma2 states how to use the information provided by lrcod to detect that two edges in a walk intersect in a single point.Lemma 2.
Letvhehivieijvjejkvk⋯vm be a border walk, and let vn∈lrcod(vm) be a point seen from vm; edge en≔(vm,vn) intersects edge eij in a single point when vn∈Λj′(vk,vi)∧vn∈Λi′(vj,vh) and  lrcod(vn) is arranged as [vi,A,vk,B,vj,C] with A,B, and C subsequences of  lrcod(vn).Proof.
Figure5(a) illustrates this lemma for vm=vk. Every point satisfying vn∈Λj′(vk,vi)∧vn∈Λi′(vj,vh) is in the red shadow. When lrcod(vn)=[vi,A,vk,B,vj,C], meaning that vn is in the circular sector (of a large circle) vjvkvi, then ekn intersects edge eij.Corollary 3.
Letvj be a λ-point with adjacent boundary points vi,vk. If vn∉Λj′(vk,vi), ekn≔(vk,vn) does not intersect eij. In other words, a walk of four consecutive boundary points can be found from two consecutive λ-points.Proof.
Corollary3 follows directly from Lemma 2. In Figure 5(b), the edge (vk,vn) does not cross any edge when vn∉Λj(vk,vi). Point vk is also a λ-point because Λj′(vi,vk) is empty.Observation 1.
It is always possible to define intersections for a walk with four or more vertices by using Lemma2.Although it is useful to find inner diagonals of a hole,λ-points are better to find points on the boundary when two consecutive points on the convex hull cannot see each other. Sometimes small holes do not have detectable λ-points; for instance, the 4-hole shown in Figure 3(a) can be detected because Λj′(vk,vi) is empty, but Λj′(vk,vi)=v in Figure 3(b). Those undetectable cases never occur for points on the convex hull.Figure 3
(a) Detectable4-hole, the sensor vj reads an empty sector. (b) Nondetectable hole, all sensors on the hole read nonempty sectors.
(a)
(b)Figure 4
Finding the boundary from a partial walk. The boundary is recovered from the walkv1v2v4v6; point v5∈lrcod(v6) is selected because e65≔(v6,v5) does not intersect any previous edge.Figure 5
Discovering intersections. Using sectors and landmark ordering, one can determine when two edges intersect at a single point.
(a)
(b)
(c)Observation 2.
If there is only a singleλ-point (a walk with three points instead of four) then Corollary 3 can be used. We can define some other cases such as that shown in Figure 5(c) where vn∈Λj(vk,vi) and lrcod(vn) reads [vi,A,vk,B,vj,C]. Unfortunately, the limited range of the sensor prevents us from using this case for all situations because sometimes vi∉lrcod(vn). We say that the intersection is undetermined for the cases where we cannot determine if an edge intersects or not with another edge of a walk. In such cases, the boundary could be completed by using other λ-points.


## 4.4. Algorithm Overview

To find the boundaries of a set of pointsV we propose Algorithms 1 and 2. In Algorithm 1 each sensor first obtains local information (line 1), then it applies the definition of Section 4.1 to recognize two consecutive λ-points (lines 4–6). If the λ-point and its corresponding adjacent points are not already used, then a boundary (or a hole) has been detected and the function RHWoC is called (line 7). Function alg:closed recovers the complete border until it finds an edge that already is on the boundary. When no more borders can be found then the list L is returned (line 12).Algorithm 1:Boundary (V).
Data: A finite set of connected points  V⊂R2.
Result: A list L of the boundary and detectable holes of  V.
(1) Exchange sensor information between neighbors;
(2)L←{};
(3)foreach  vi∈V  do
(4)if  viisaλ-pointwithadjacentspointsva,vb
then
(5) W′←va(va,vi)vi(vi,vb)vb;
(6) if  W′isnotusedinLandvbisaλ-pointwithadjacentpointsvi,vc  then
(7)W← RHWoC (va,vi,vb,vc);
(8)L←L∪W;
(9) end
(10)end
(11)end
(12)return  LAlgorithm 2:Function RHWoC (vi-3,vi-2, vi-1, vi).
(1)ej←(vi-1,vi);
(2)vj-1←vi-1;
(3)vj←vi;
(4)W←vi-3vi-2vi-1vi;
(5)repeat
(6)L←lrcod(vj);
(7)Circular-rotate L until vj-1 is the last element of L;
(8)foreach  vk∈L  do
(9)  if  (k=j-1)or  (vj,vk)doesnotintersectanyedgeofW  then
(10)ej←(vj,vk);
(11)vj-1←vj;
(12)vj←vk;
(13)W←Wejvj;
(14)    break;
(15)end
(16)end
(17)until  (ej∉W);
(18)return  WCorrectness of Function RHWoC. Let W be the outer area reachable with the lrcod from vertices of W. At each step, the next landmark vk in the walk is selected according to the RHWoC rule. The rule’s precondition asserts that v1,…,vi-1 are λ-convex hole points; then W does not contain any landmark. For the following steps, RHWoC rule ensures that Sj=Λ′(vj;vj-1,vk)∩W does not contain any landmark. As ⋃∀vj∈W‍Sj=W and the walk never crosses itself, the Jordan theorem asserts that W is a boundary and the set of landmarks V∖W are in the same side of W. Finally, based on our connectivity assumption, the walk reaches a previously detected edge and the cycle of lines 5–17 terminates correctly.


## 5. Simulations

The proposed algorithm has been implemented for randomly generated sets in a quadrangle of30×30. The number of nodes and the value of λ are user-defined parameters. Examples of networks for different values of n are illustrated in Figure 6. The proposed algorithm finds correctly the outer boundaries of networks which are relatively sparse (Figures 6(a) and 6(b)) and dense (Figures 6(c) and 6(d)). Figures 6(a) and 6(b) also show the detectable inner boundaries.Figure 6
Boundaries obtained from a set ofN uniform distributed random points within a quadrangle of 30×30.
(a)
N
=
80, λ=15
(b)
N
=
120, λ=15
(c)
N
=
1000, λ=15
(d)
N
=
3000, λ=15


## 6. Related Work

A well-known technique to find the boundary of a set of points is theα-shape [12]. Alpha shapes are closely related to alpha complexes, subcomplexes of the Delaunay triangulation of the point set.Some approaches to detect boundaries in networks are (a) distribution of nodes in the nonhole regions [13], (b) length of the shortest path between two nodes to detect cycles [14, 15], and (c) patterns that the nodes produce [1].In robotics, landmarks are useful for navigation, place recognition, localization, and mapping. The proposed approach deals with a more challenging setting compared with [6], on which a robot that is only able to detect the cyclic angular order of landmarks in an unlimited range can accomplish simple tasks, such as navigation and patrolling. One of the advantages of this approach is that the memory of the robot does not save the complete state of the environment. To compensate, it considers an infinite range in the landmark order detector.


## 7. Conclusions

The problem we address in this paper is to find the boundaries of a sensor network by using a limited range-cyclic order detector. By using local information we show how to detectλ-points; these points are on the boundary or on a hole. TheRight Hand Without Crossings (RHWoC) rule can be used to discover other landmarks from an incomplete border walk. We provide a correctness proof of the RHWoC rule.Some holes could not be detected by using local information. We also show the configurations where the boundary is detectable; the most remarkable case is when there are two consecutiveλ-points. Therefore, the proposed technique is appropriate for large sensor networks. The experimental evaluation confirms the effectiveness to find the boundary of large sensor networks.



---

*Source: 401838-2015-07-07.xml*