hal-02303242
https://hal-ensta-bretagne.archives-ouvertes.fr/hal-02303242
https://hal-ensta-bretagne.archives-ouvertes.fr/hal-02303242/document
https://hal-ensta-bretagne.archives-ouvertes.fr/hal-02303242/file/rr_lpcn_bb.pdf
doi:10.1002/ett.3696
[ENSTA-BRETAGNE] ENSTA Bretagne
[ENSTA-BRETAGNE-STIC] Département STIC
[INSTITUTS-TELECOM] composantes instituts telecom
[IBNM] Institut Brestois du Numérique et des Mathématiques
[LAB-STICC_UBO] Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance, site de l'UBO
[INSTITUT-TELECOM] Institut Télécom
[CNRS] CNRS - Centre national de la recherche scientifique
[LAB-STICC] Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
[ENIB] Ecole Nationale d'Ingénieurs de Brest
[UNIV-UBS] Université de Bretagne Sud
[UNIV-BREST] Université de Bretagne occidentale - Brest (UBO)
[LAB-STICC_ENIB] Laboratoire des Sciences et Techniques de l'Information, de la Communication et de la Connaissance, site ENIB Brest
[LAB-STICC_UBS] lab-STICC-UBS
[UBS] Université de Bretagne Sud
Finding the polygon hull of a network without conditions on the starting vertex
Bounceur, Ahcène
Bezoui, Madani
Hammoudeh, Mohammad
Lagadec, Loïc
Euler, Reinhardt
[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]
ART
Polar angle
Wireless Sensor Network
Boundary Node Detection
Polygon Hull
Many real‐life problems arising within the fields of wireless communication, image processing, combinatorial optimization, etc, can be modeled by means of Euclidean graphs. In the case of wireless sensor networks, the overall topology of the graph is not known because sensor nodes are often randomly deployed. One of the significant problems in this field is the search for boundary nodes. This problem is important in cases such as the surveillance of an area of interest, image contour reconstruction, graph matching problems, routing or clustering data, etc. In the literature, many algorithms are proposed to solve this problem, a recent one of which is the least polar‐angle connected node (LPCN) algorithm and its distributed version D‐LPCN, which are both based on the concept of a polar angle visit. An inconvenience of these algorithms is the determination of the starting vertex. In effect, the point with the minimum x‐coordinate is a possible starting point, but it has to be known at the beginning, which considerably increases the algorithms' complexity. In this article, we propose a new method called RRLPCN (reset and restart with least polar‐angle connected node), which is based on the LPCN algorithm to find the boundary vertices of a Euclidean graph. The main idea is to start the LPCN algorithm from an arbitrary vertex, and whenever it finds a vertex with an x‐coordinate smaller than that of the starting one, LPCN is reset and restarted from this new vertex. The algorithm stops as soon as it visits the same edge for the second time in the same direction. In addition to finding the boundary vertices, RRLPCN also finds the vertex with minimum x‐coordinate, which is the last starting point of our algorithm. The distributed version of the proposed algorithm, called D‐RRLPCN, is then applied to boundary node detection in the wireless sensor network. It has been implemented using real sensor nodes (Arduino/XBee and TelosB). The simulation results have shown our algorithm to be very effective in comparison to other algorithms.
2019
2020-01-13
en
Transactions on emerging telecommunications technologies
Wiley-Blackwell