Sage Journals: Discover world-class research

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 the Right 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.

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 by $l r c o d$ , can detect nearby objects and enumerate them by their cyclic order; neither distance nor the angular position of each object is provided. The $l r c o d$ sensor only measures the cyclic order, unlike bearing measurement systems, where the angle of each object is known. $l r c o d$ 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: Section 2 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 \in R^{2}$ . Figure 1 illustrates an example of the sequences of landmarks detected from two positions $lrcod (v_{4}) = [v_{5}, v_{3}, v_{1}, v_{6}]$ and $lrcod (v_{3}) = [v_{4}, v_{5}, v_{2}]$ .

Figure 1

Sequence of landmarks detected by the sensor. $lrcod (v_{4}) = [v_{5}, v_{3}, v_{1}, v_{6}]$ ; up to a cyclic permutation, landmark 2 cannot be detected because it is outside the reach of the sensor; analogously, $lrcod (v_{3}) = [v_{4}, v_{5}, v_{2}]$ . 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 in $R^{2}$ . Let $G = (V, E)$ be a connected graph where V is the set of landmark labels and $E = \{\{x, y\} | x, y \in V, ‖x, y‖ \leq λ\}$ with $(y \neq x)$ ; here $‖\cdot, \cdot‖$ denotes the Euclidean distance between two points. An edge between two landmarks $x, y \in V$ means that $l r c o d$ 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 $v_{i}$ and $v_{j}$ seen from $v_{x}$ , we define $Λ^{'} (v_{x}; v_{i}, v_{j})$ as the points within the counterclockwise circular sector $v_{i} v_{x} v_{j}$ . Let the output of the sensor be of the form $lrcod (v_{x}) = [A, v_{i}, B, v_{j}, C]$ , in which $A, B$ , and C are subsequences of $l r c o d (v_{x})$ separated by the labels corresponding to landmarks $v_{i}$ and $v_{j}$ ; then $Λ^{'} (v_{x}; v_{i}, v_{j}) = B$ and $Λ^{'} (v_{x}; v_{j}, v_{i}) = C + A$ , where + is the concatenation of two sequences.

The sensor $v_{x}$ shown in Figure 2 reads $lrcod (v_{x}) = [v_{3}, v_{4}, v_{5}, v_{1}, v_{2}]$ . Landmarks $v_{3}, v_{5}$ define two sectors $Λ^{'} (v_{x}; v_{3}, v_{5}) = \{v_{4}\}$ and $Λ^{'} (v_{x}; v_{5}, v_{3}) = \{v_{1}, v_{2}\}$ .

Figure 2

Orientation and circular sectors. Circular sectors detected from $l r c o d$ : $Λ^{'} (v_{x}; v_{3}, v_{5}) = \{v_{4}\}$ and $Λ^{'} (v_{x}; v_{5}, v_{3}) = \{v_{1}, v_{2}\}$ .

Walk. A walk in a graph G is a sequence $W ≔ v_{0} e_{0} v_{1} \dots v_{l - 1} e_{l - 1} v_{l}$ , whose components are alternately vertices and edges of G (not necessarily distinct), such that $v_{i}$ and $v_{i + 1}$ are the ends of edge $e_{i}$ , $0 \leq i \leq l - 1$ [7]. We say that W connects the initial point $v_{0}$ to the final point $v_{l}$ and refer to W as a $v_{0} v_{l}$ -walk or simply $v_{0} W v_{l}$ . 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 = v_{0} v_{1} \dots v_{l - 1} v_{l}$ to denote the walk $W = v_{0} e_{0} v_{1} \dots v_{l - 1} e_{l - 1} v_{l}$ . The vertices of a closed walk also define a polygon P.

Polygon. A polygon P is a finite sequence $P = v_{0} v_{1} \dots v_{p - 1}$ of points in the plane. The set of edges of a polygon is $E (P) = \{e_{i} | i = 0, \dots, p - 1\}$ , where $e_{i}$ is defined as an edge connecting $v_{i}$ and $v_{(i + 1 \mod p)}$ .

Simple Polygon. A simple polygon is a polygon composed of nonrepeating vertices where none of its edges $e_{i}$ and $e_{j}$ , for $i \neq 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 $d_{F} (P, Q) < ϵ$ , where $d_{F}$ 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 polygon P partitions $R^{2} ∖ P$ into two regions: interior and exterior.

λ-Polygon. A λ-polygon P is a weakly simple polygon where $‖e_{i}‖ \leq λ$ for all $e_{i} \in E (P)$ .

λ-Boundary. A λ-boundary or outer boundary P of a set of points V is a λ-polygon such that $V ∖ P$ lies in the interior of P.

Diagonal. A diagonal is a line that connects two nonconsecutive vertices of a polygon; an inner diagonal lies totally in the interior of the polygon.

Hole. A hole or inner boundary is an empty λ-polygon with vertices $H \subset 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 sensors V, located in a region $R \subset R^{2}$ ; each sensor $v \in V$ has a distinctive identity.

(ii)

Every sensor $v \in 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 in R 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 in ad 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 $l r c o d$ sensors, find the boundary polygon of V and its holes by using only the local information provided by the $l r c o d$ 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 the convex hull (CH) of the point set.

Unfortunately, following it by using the limited 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 $l r c o d$ 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 Section 4.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 $v_{j}$ for which $\exists v_{i}, v_{k} \in lrcod (v_{j})$ such that $Λ^{'} (v_{j}; v_{i}, v_{k}) = \{\}$ and $v_{i} \notin lrcod (v_{k})$ . Points $v_{i}, v_{k}$ are called adjacent boundary points of $v_{j}$ .

4.2. Detecting a Boundary from $λ$ -Points

This subsection addresses how to use λ-points as seeds to find the boundary sequence.

Let $h_{j}$ and $h_{j + 1}$ be two consecutive points on the convex hull and let $(h_{j}, h_{j + 1})$ be the line segment joining them. Since the graph G is connected, there exists at least one $h_{j} h_{j + 1}$ -walk. We are looking for the walk such that the area comprised by $W^{'} ≔ h_{j} W h_{j + 1} (h_{j + 1}, h_{j}) h_{j}$ does not contain any landmark $v \in V$ ; we refer to the walk that satisfies this condition as a pocket.

The right-hand rule (RH) is a heuristic rule that has been used extensively to deliver packages in ad 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 $v_{j - 1}, v_{j}$ then the next vertex is the first vertex that appears immediately by turning right from the edge $(v_{j - 1}, v_{j})$ . 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 the Right Hand Without Crossings (RHWoC)rule. Given a partial walk $W^{'} = [v_{0} \dots v_{j - 1} e_{j - 1} v_{j}]$ such that its last edge is $(v_{j - 1}, v_{j})$ , the RHWoC rule selects the first landmark $v_{k}$ in $lrcod (v_{j})$ that follows $v_{j - 1}$ in the permutation such that the edge $e_{j} ≔ (v_{j}, v_{k})$ 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 = v_{1} e_{12} v_{2} e_{24} v_{4} e_{46} v_{6}$ . When the point $v_{6}$ is analyzed, $v_{3}$ appears in the permutation immediately after point $v_{4}$ but it is not selected because the edge $(v_{6}, v_{3})$ intersects the boundary; then the correct point $v_{5}$ 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 walk W 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.

Let $e_{i j} = (v_{i}, v_{j})$ and $e_{k n} = (v_{k}, v_{n})$ be two edges, and let ${l r c o d}_{k, n} : = l r c o d (v_{k}) \cup l r c o d (v_{n})$ be the landmarks seen from $v_{k}$ or $v_{n}$ . If $(v_{i} \notin {l r c o d}_{k, n}) \land (v_{j} \notin {l r c o d}_{k, n})$ then $e_{i j}$ does not intersect $e_{k n}$ .

Proof.

When $e_{i j}$ and $e_{k n}$ intersect at a single point q, there exist two points $v_{a} \in \{v_{i}, v_{j}\}$ and $v_{b} \in \{v_{k}, v_{n}\}$ such that $‖v_{a} q‖ \leq λ / 2$ and $‖v_{b} q‖ \leq λ / 2$ . From the law of cosines it can be shown that $‖v_{a}, v_{b}‖ \leq λ$ ; in other words, $v_{b} \in lrcod (v_{a})$ .

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 as bridges and articulation points [11].

Lemma 2 states how to use the information provided by $l r c o d$ to detect that two edges in a walk intersect in a single point.

Lemma 2.

Let $v_{h} e_{h i} v_{i} e_{i j} v_{j} e_{j k} v_{k} \dots v_{m}$ be a border walk, and let $v_{n} \in l r c o d (v_{m})$ be a point seen from $v_{m}$ ; edge $e_{n} ≔ (v_{m}, v_{n})$ intersects edge $e_{i j}$ in a single point when $(v_{n} \in Λ_{j}^{'} (v_{k}, v_{i})) \land (v_{n} \in Λ_{i}^{'} (v_{j}, v_{h}))$ and $l r c o d (v_{n})$ is arranged as $[v_{i}, A, v_{k}, B, v_{j}, C]$ with $A, B$ , and C subsequences of $l r c o d (v_{n})$ .

Proof.

Figure 5(a) illustrates this lemma for $v_{m} = v_{k}$ . Every point satisfying $(v_{n} \in Λ_{j}^{'} (v_{k}, v_{i})) \land (v_{n} \in Λ_{i}^{'} (v_{j}, v_{h}))$ is in the red shadow. When $lrcod (v_{n}) = [v_{i}, A, v_{k}, B, v_{j}, C]$ , meaning that $v_{n}$ is in the circular sector (of a large circle) $v_{j} v_{k} v_{i}$ , then $e_{k n}$ intersects edge $e_{i j}$ .

Corollary 3.

Let $v_{j}$ be a λ-point with adjacent boundary points $v_{i}, v_{k}$ . If $v_{n} \notin Λ_{j}^{'} (v_{k}, v_{i})$ , $e_{k n} ≔ (v_{k}, v_{n})$ does not intersect $e_{i j}$ . In other words, a walk of four consecutive boundary points can be found from two consecutive λ-points.

Proof.

Corollary 3 follows directly from Lemma 2. In Figure 5(b), the edge $(v_{k}, v_{n})$ does not cross any edge when $v_{n} \notin Λ_{j} (v_{k}, v_{i})$ . Point $v_{k}$ is also a λ-point because $Λ_{j}^{'} (v_{i}, v_{k})$ is empty.

Observation 1.

It is always possible to define intersections for a walk with four or more vertices by using Lemma 2.

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}^{'} (v_{k}, v_{i})$ is empty, but $Λ_{j}^{'} (v_{k}, v_{i}) = \{v\}$ in Figure 3(b). Those undetectable cases never occur for points on the convex hull.

Figure 3

(a) Detectable $4$ -hole, the sensor $v_{j}$ reads an empty sector. (b) Nondetectable hole, all sensors on the hole read nonempty sectors.

Figure 4

Finding the boundary from a partial walk. The boundary is recovered from the walk $v_{1} v_{2} v_{4} v_{6}$ ; point $v_{5} \in lrcod (v_{6})$ is selected because $e_{65} ≔ (v_{6}, v_{5})$ 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.

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 $v_{n} \in Λ_{j} (v_{k}, v_{i})$ and $lrcod (v_{n})$ reads $[v_{i}, A, v_{k}, B, v_{j}, C]$ . Unfortunately, the limited range of the sensor prevents us from using this case for all situations because sometimes $v_{i} \notin lrcod (v_{n})$ . 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 points V 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 \subset R^{2}$ .

Result: A list $L$ of the boundary and detectable holes of V.

(1) Exchange sensor information between neighbors;

(2) $L \leftarrow {}$ ;

(3) foreach $v_{i} \in V$ do

(4) if $v_{i} i s a λ - p o i n t w i t h a d j a c e n t s p o i n t s v_{a}, v_{b}$

then

(5) $W^{'} \leftarrow v_{a} (v_{a}, v_{i}) v_{i} (v_{i}, v_{b}) v_{b}$ ;

(6) if $W^{'} i s n o t u s e d i n L a n d v_{b} i s a λ - p o i n t w i t h a d j a c e n t p o i n t s v_{i}, v_{c}$ then

(7) $W \leftarrow$ RHWoC $(v_{a}, v_{i}, v_{b}, v_{c})$ ;

(8) $L \leftarrow L \cup W$ ;

(9) end

(10) end

(11) end

(12) return $L$

Algorithm 2: Function RHWoC ( $v_{i - 3}, v_{i - 2}$ , $v_{i - 1}$ , $v_{i}$ ).

(1) $e_{j} \leftarrow (v_{i - 1}, v_{i})$ ;

(2) $v_{j - 1} \leftarrow v_{i - 1}$ ;

(3) $v_{j} \leftarrow v_{i}$ ;

(4) $W \leftarrow v_{i - 3} v_{i - 2} v_{i - 1} v_{i}$ ;

(5) repeat

(6) $L \leftarrow lrcod (v_{j})$ ;

(7) Circular-rotate L until $v_{j - 1}$ is the last element of L;

(8) foreach $v_{k} \in L$ do

(9) if $(k = j - 1) o r$ $(v_{j}, v_{k}) d o e s n o t i n t e r s e c t a n y e d g e o f W$ then

(10) $e_{j} \leftarrow (v_{j}, v_{k})$ ;

(11) $v_{j - 1} \leftarrow v_{j}$ ;

(12) $v_{j} \leftarrow v_{k}$ ;

(13) $W \leftarrow W e_{j} v_{j}$ ;

(14) break;

(15) end

(16) end

(17) until ( $e_{j} \notin W)$ ;

(18) return W

Correctness of Function RHWoC. Let $W$ be the outer area reachable with the $l r c o d$ from vertices of W. At each step, the next landmark $v_{k}$ in the walk is selected according to the RHWoC rule. The rule's precondition asserts that $v_{1}, \dots, v_{i - 1}$ are λ-convex hole points; then $W$ does not contain any landmark. For the following steps, RHWoC rule ensures that $S_{j} = Λ^{'} (v_{j}; v_{j - 1}, v_{k}) \cap W$ does not contain any landmark. As $⋃_{\forall v_{j} \in W} ‍ S_{j} = 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 of $30 \times 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 of N uniform distributed random points within a quadrangle of $30 \times 30$ .

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. The Right 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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Saukh

Sauter

Gauger

Marrón

P. J.

On Boundary recognition without location information in wireless sensor networks

ACM Transactions on Sensor Networks 2010 6 3, article 20

10.1145/1754414.1754416

2-s2.0-77953982155

Ferrat

Gimkiewicz

Neukom

Zha

Brenzikofer

Baechler

Ultra-miniature omni-directional camera for an autonomous flying micro-robot

7000

Conference on Optical and Digital Image Processing

2008

Proceedings of SPIE

Tavli

Bicakci

Zilan

Barceló-Ordinas

J. M.

A survey of visual sensor network platforms

Multimedia Tools and Applications 2012 60 3 689 726

10.1007/s11042-011-0840-z

2-s2.0-79959680213

Pugh

Raemy

Favre

Falconi

Martinoli

A fast onboard relative positioning module for multirobot systems

IEEE/ASME Transactions on Mechatronics 2009 14 2 151 162

10.1109/TMECH.2008.2011810

2-s2.0-67349187686

Roberts

J. F.

Stirling

Zufferey

J.-C.

Floreano

3-D relative positioning sensor for indoor flying robots

Autonomous Robots 2012 33 1-2 5 20

10.1007/s10514-012-9277-0

2-s2.0-84862143540

Tovar

Freda

Lavalle

S. M.

Learning combinatorial map information from permutations of landmarks

International Journal of Robotics Research 2011 30 9 1143 1156

10.1177/0278364910381416

2-s2.0-80052194737

Bondy

Murty

U. S. R.

Graph Theory 2008

Springer

Graduate Texts in Mathematics

MR2368647

Ribó Mor

Realization and counting problems for planar structures: trees and linkages, polytopes and polyominoes [Ph.D. thesis] 2006

Berlin, Germany

Freie Universität Berlin

Graham

R. L.

Yao

F. F.

Finding the convex hull of a simple polygon

Journal of Algorithms 1983 4 4 324 331

10.1016/0196-6774(83)90013-5

MR729228

2-s2.0-0001651336

10.

Muhammad

R. B.

A distributed graph algorithm for geometric routing in ad hoc wireless networks

Journal of Networks 2007 2 6 50 57

2-s2.0-84866889939

11.

Ausiello

Firmani

Laura

Real-time monitoring of undirected networks: articulation points, bridges, and connected and biconnected components

Networks 2012 59 3 275 288

10.1002/net.21450

MR2912898

2-s2.0-84859771212

12.

Edelsbrunner

Kirkpatrick

D. G.

Seidel

On the shape of a set of points in the plane

IEEE Transactions on Information Theory 1983 29 4 551 559

10.1109/tit.1983.1056714

MR713690

13.

Funke

Klein

Hole detection or: how much geometry hides in connectivity?”

Proceedings of the 22nd Annual Symposium on Computational Geometry (SCG ′06) 2006

New York, NY, USA

ACM

377 385

10.1145/1137856.1137911

MR2389347

14.

Kröller

Fekete

S. P.

Pfisterer

Fischer

Deterministic boundary recognition and topology extraction for large sensor networks

Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA ’06)

2006

New York, NY, USA

ACM

1000 1009

10.1145/1109557.1109668

MR2373827

15.

Wang

Gao

Mitchell

J. S. B.

Boundary recognition in sensor networks by topological methods

Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MOBICOM ′06)

September 2006

New York, NY, USA

ACm

122 133

2-s2.0-33751047930

Detecting the Boundary of Sensor Networks from Limited Cyclic Information

Abstract

1. Introduction

2. Basic Definitions

3. Network Model

4. Proposed Algorithm

4.1. Boundary Points

4.2. Detecting a Boundary from λ -Points

4.3. Discovering Intersections

Lemma 1.

Proof.

Lemma 2.

Proof.

Corollary 3.

Proof.

Observation 1.

Observation 2.

4.4. Algorithm Overview

Algorithm 1: Boundary (V).

Algorithm 2: Function RHWoC ( v i - 3 , v i - 2 , v i - 1 , v i ).

5. Simulations

6. Related Work

7. Conclusions

Footnotes

Conflict of Interests

References

4.2. Detecting a Boundary from $λ$ -Points

Algorithm 2: Function RHWoC ( $v_{i - 3}, v_{i - 2}$ , $v_{i - 1}$ , $v_{i}$ ).