Change search
ReferencesLink to record
Permanent link

Direct link
A distributed approximation for multi-hop clustering problem in wireless sensor networks
Shanghai Key Laboratory of Scalable Computing and Systems, Department of Computer Science and Engineering, Shanghai Jiao Tong University.
Shanghai Key Laboratory of Scalable Computing and Systems, Department of Computer Science and Engineering, Shanghai Jiao Tong University.
Shanghai Key Laboratory of Scalable Computing and Systems, Department of Computer Science and Engineering, Shanghai Jiao Tong University.
Shanghai Key Laboratory of Scalable Computing and Systems, Department of Computer Science and Engineering, Shanghai Jiao Tong University.
Show others and affiliations
Number of Authors: 6
2016 (English)In: 2015 IEEE Global Communications Conference (GLOBECOM): San Diego, CA, 6-10 Dec 2015, Piscataway, NJ: IEEE Communications Society, 2016, 7416941Conference paper (Refereed)
Abstract [en]

In wireless sensor networks (WSNs), there is no predefined infrastructure. Nodes need to frequently flood messages to discover routes, which badly decreases the network performance. To overcome such drawbacks, WSNs are often grouped into several disjointed clusters, each with a representative cluster head (CH) in charge of the routing process. In order to further improve the efficiency of WSNs, it is crucial to find a cluster partition with minimum number of clusters and the distance between each node to its corresponding CH can be bounded by a constant number of hops. Finding such a partition is defined as minimum d-hop cluster head set (d-MCHS) problem, which is proved to be NP-hard. In this paper, we propose a distributed approximation algorithm, named d^2-Cluster, to address d-MCHS problem and prove that the approximation ratio of d^2-Cluster under unit disk graph (UDG) is a constant factor \lambda which is related to d. To the best of our knowledge, it is the first constant approximation ratio for d-MDS problem in UDG

Place, publisher, year, edition, pages
Piscataway, NJ: IEEE Communications Society, 2016. 7416941
National Category
Media and Communication Technology
Research subject
Mobile and Pervasive Computing
Identifiers
URN: urn:nbn:se:ltu:diva-37677DOI: 10.1109/GLOCOM.2014.7416941ISI: 000382389300002Local ID: bc5420a5-887b-4746-adf0-54b19d06f0f0ISBN: 9781479959525 (PDF)OAI: oai:DiVA.org:ltu-37677DiVA: diva2:1011175
Conference
IEEE GLOBECOM : 06/12/2015 - 10/12/2015
Note

Validerad; 2016; Nivå 1; 2016-11-25 (andbra)

Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2016-11-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Vasilakos, Athanasios
By organisation
Computer Science
Media and Communication Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link