Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Finding the polygon hull of a network without conditions on the starting vertex

Ahcène Bounceur 1 Madani Bezoui 2 Mohammad Hammoudeh 3 Loïc Lagadec 4 Reinhardt Euler 5
1 Lab-STICC_UBS_CACS_MOCS
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
4 Lab-STICC_ENSTAB_ CACS_MOCS
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
5 Lab-STICC_UBO_CID_DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : 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.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [61 références]  Voir  Masquer  Télécharger

https://hal-ensta-bretagne.archives-ouvertes.fr/hal-02303242
Contributeur : Marie Briec <>
Soumis le : lundi 13 janvier 2020 - 23:10:21
Dernière modification le : mercredi 24 juin 2020 - 16:19:56
Document(s) archivé(s) le : mardi 14 avril 2020 - 19:29:54

Fichier

rr_lpcn_bb.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Ahcène Bounceur, Madani Bezoui, Mohammad Hammoudeh, Loïc Lagadec, Reinhardt Euler. Finding the polygon hull of a network without conditions on the starting vertex. Transactions on emerging telecommunications technologies, Wiley-Blackwell, In press, pp.e3696. ⟨10.1002/ett.3696⟩. ⟨hal-02303242⟩

Partager

Métriques

Consultations de la notice

149

Téléchargements de fichiers

193