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

Saoudi Massinissa 1, 2 Farid Lalem 2 Ahcène Bounceur 2 Reinhardt Euler 2 M. Tahar Kechadi 1 Laouid Abdelkader 3 Bezoui Madani 4 Marc Sevaux 5
2 Lab-STICC_UBO_CACS_MOCS
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance, UBO - Université de Brest
5 Lab-STICC_UBS_CID_DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (UMR 3192), Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : 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.
Type de document :
Article dans une revue
Ad Hoc Networks, Elsevier, 2017, 56, pp.56-71. 〈10.1016/j.adhoc.2016.11.010〉
Liste complète des métadonnées

http://hal.univ-brest.fr/hal-01402480
Contributeur : Ahcène Bounceur <>
Soumis le : jeudi 24 novembre 2016 - 16:55:03
Dernière modification le : mardi 16 janvier 2018 - 15:54:25

Identifiants

Citation

Saoudi Massinissa, Farid Lalem, Ahcène Bounceur, Reinhardt Euler, M. Tahar Kechadi, et al.. D-LPCN: A Distributed Least Polar-angle Connected Node Algorithm for Finding the Boundary of a Wireless Sensor Network. Ad Hoc Networks, Elsevier, 2017, 56, pp.56-71. 〈10.1016/j.adhoc.2016.11.010〉. 〈hal-01402480〉

Partager

Métriques

Consultations de la notice

353