Experimental Evaluation of Synchronous and Asynchronous Algorithms for Wireless Sensor Networks: The Case of Graph Matching


Innovations in Intelligent Systems and Applications Conference (ASYU), İzmir, Turkey, 31 October - 02 November 2019, pp.607-612 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/asyu48272.2019.8946414
  • City: İzmir
  • Country: Turkey
  • Page Numbers: pp.607-612
  • Keywords: Distributed Computing, Wireless Sensor Networks, Asynchronous Algorithm, Synchronous Algorithm, Graph Matching, Performance Evaluation


Wireless sensor networks (WSNs) consist of tiny nodes that are capable of sensing the environment and transmitting the sensed data through wireless transceivers. Synchronous and asynchronous operations are two communication paradigms, which have different advantages and purposes. A WSN can be modeled as a graph that leads to use graph-theoretic structures such as graph matching, for various applications. A matching in a graph is a set of edges that do not have any common endpoint (node). Backup assignment and clustering are the most well-known applications of graph matching, where nodes incident to edges in a matching are backups of each other. In this paper, a detailed performance evaluation of synchronous and asynchronous operations in terms graph matching is provided. A synchronous and an asynchronous design of the Hoepman's algorithm, whose original was asynchronous, were considered. Extensive transmitted bit, energy and wall clock time measurements of these algorithms are given by comparing them in detail. The tests, which are carried out via TOSSIM simulations, showed that asynchronous operation is considerably faster, on the other side the synchronous algorithm is significantly more energy efficient.