D-LPCN: A Distributed Least Polar-angle Connected Node Algorithm for Finding the Boundary of a Wireless Sensor Network

Autor: Ahcène Bounceur, Marc Sevaux, Abdelkader Laouid, Reinhardt Euler, Farid Lalem, M-Tahar Kechadi, Madani Bezoui, Massinissa Saoudi
Přispěvatelé: Complex & Adaptive Systems Laboratory - University College Dublin (CASL), University College Dublin [Dublin] (UCD), Lab-STICC_UBO_CACS_MOCS, Université de Brest (UBO)-Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Lab-STICC_UBO_CID_DECIDE, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), LIMED Laboratory, University A-Mira of Bejaia (LIMED), Université M'Hamed Bougara Boumerdes (UMBB), Lab-STICC_UBS_CID_DECIDE, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (UMR 3192) (Lab-STICC), Université européenne de Bretagne - European University of Brittany (UEB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université européenne de Bretagne - European University of Brittany (UEB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Centre National de la Recherche Scientifique (CNRS), ANR-14-CE24-0017,PERSEPTEUR,PlateformE viRtuelle 3D pour la Simulation des rEseaux de caPTEURs(2014), Université M'Hamed Bougara Boumerdes, Université européenne de Bretagne - European University of Brittany (UEB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Télécom Bretagne-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université européenne de Bretagne - European University of Brittany (UEB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Télécom Bretagne-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC)
Jazyk: angličtina
Rok vydání: 2017
Předmět:
Star network
Brooks–Iyengar algorithm
Computer Networks and Communications
Computer science
02 engineering and technology
0202 electrical engineering
electronic engineering
information engineering
[INFO]Computer Science [cs]
AhceneBounceur@univ-brestfr (Ahcène Bounceur)
[MATH]Mathematics [math]
FaridLalem@univ-brestfr (Farid Lalem)
020206 networking & telecommunications
Energy consumption
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Graph
Polygon hull * Corresponding author Email addresses: MassinissaSaoudi@univ-brestfr (Massinissa Saoudi)
Key distribution in wireless sensor networks
Hardware and Architecture
Distributed algorithm
ReinhardtEuler@univ-brestfr (Reinhardt Euler)
Polygon hull
Graph (abstract data type)
Distributed algorithms
020201 artificial intelligence & image processing
Boundary detection
Polar coordinate system
Wireless Sensor Networks
Wireless sensor network
Algorithm
Software
Zdroj: Ad Hoc Networks
Ad Hoc Networks, Elsevier, 2017, 56, pp.56-71. ⟨10.1016/j.adhoc.2016.11.010⟩
ISSN: 1570-8705
DOI: 10.1016/j.adhoc.2016.11.010⟩
Popis: International audience; A boundary of wireless sensor networks (WSNs) can be used in many fields, for example, to monitor a frontier or a secure place of strategic sensitive sites like oil fields or frontiers of a country. This situation is modeled as the problem of finding a polygon hull in a connected Euclidean graph, which represents a minimal set of connected boundary nodes. In this paper we propose a new algorithm called D-LPCN (Distributed Least Polar-angle Connected Node) which represents the distributed version of the LPCN algorithm introduced in [1]. In each iteration, any boundary node, except the first one, chooses its nearest polar angle node among its neighbors with respect to the node found in the previous iteration. The first starting node can be automatically determined using the Minimum Finding algorithm, which has two main advantages. The first one is that the algorithm works with any type of a connected network, given as planar or not. Furthermore, it takes into account any blocking situation and contains the necessary elements to avoid them. The second advantage is that the algorithm can determine all the boundaries of the different connected parts of the network. The proposed algorithm is validated using the CupCarbon, Tossim and Contiki simulators. It has also been implemented using real sensor nodes based on the TelosB and Arduino/XBee platforms. We have estimated the energy consumption of each node and we have found that the consumption of the network depends on the number of the boundary nodes and their neighbors. The simulation results show that the proposed algorithm is less energy consuming than the existing algorithms and its distributed version is less energy consuming than the centralized version.
Databáze: OpenAIRE
Externí odkaz: