Virtual Backbone Construction Algorithms Based on Protocol Interference Model

Autor:	Congcong Chen, Jiguo Yu, Guomin Yan, Lili Jia
Rok vydání:	2014
Předmět:	Correctness Matching (graph theory) Computer science Dominating set ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS Interference (wave propagation) Wireless sensor network Algorithm Time complexity Energy (signal processing) Connected dominating set
Zdroj:	Communications in Computer and Information Science ISBN: 9783642545214 CWSN
DOI:	10.1007/978-3-642-54522-1_4
Popis:	Interference is one of the main challenges in designing energy efficient protocols for wireless sensor networks. Decreasing interference can reduce energy consumptions of nodes and prolong the lifetime of the network. Combining graph matching and the protocol interference model, in this paper, we propose a Matching Based Interference-Aware Dominating Set Construction Algorithm (MBIDSC), in which we consider a connected dominating set as a virtual backbone. The upper bounds of message complexity of the algorithm is \(O(nr{\varDelta} )\) and the time complexity is \(O(r{\varDelta} )\). Where n is the total number of nodes, \({\varDelta}\) is the maximum degree of the network, r is the round of the algorithm, and d is the diameter of the network. We show the correctness of the algorithms and complexity of time and message by theoretical analysis. To the best of our knowledge, the proposed algorithm is the first results for the protocol interference model based on graph matching.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::54c493b20e654f44b22126a9ee5d01ff https://doi.org/10.1007/978-3-642-54522-1_4 Zobrazit plný text záznamu