A distributed And asynchronous approach for optimizing weighted graph matchings in wireless network services

Can Umut Ileri, Orhan Dagdeviren*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Weighted graph matching is one of the most fundamental graph theoretical problems used in network design, especially in wireless network services such as radio resource allocation, physical layer security, energy-efficient partner selection and optimizing storage capacity. In this paper we present a distributed heuristic which provides nearly-optimal weighted matchings in polynomial time. We also propose an algorithm to decrease the number of transmitted messages to provide energy-efficient operation. Our approaches assume the asynchronous communication model and small messages having O(log (n)) bits. These assumptions directly fit the battery powered wireless networks such as wireless ad hoc and sensor networks. To the best of our knowledge, we propose the first distributed weighted matching algorithm which benefits from augmentation of augmenting paths having size larger than 3 for these networks. We also provide results of our simulations on synthetic geometric graphs to model wireless networks. Extensive simulations reveal that our algorithm improves the approximation performances of the other weighted matching algorithms and closes the gap between the approximation ratio and the optimum up to 32%.

Original languageEnglish
Pages (from-to)73-89
Number of pages17
JournalExpert Systems with Applications
Volume119
DOIs
Publication statusPublished - 1 Apr 2019
Externally publishedYes

Keywords

  • Distributed algorithms
  • Graph matching
  • Graph theory
  • Wireless networks

Fingerprint

Dive into the research topics of 'A distributed And asynchronous approach for optimizing weighted graph matchings in wireless network services'. Together they form a unique fingerprint.

Cite this