Performance-guaranteed strongly connected dominating sets in heterogeneous wireless sensor networks

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

14 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications
PublisherIEEE
ISBN (Electronic)978-1-4673-9953-1
ISBN (Print)978-1-4673-9954-8
Publication statusPublished - 2016
Externally publishedYes

Conference

Title35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016
PlaceUnited States
CitySan Francisco
Period10 - 14 April 2016

Abstract

In wireless sensor networks, Virtual Backbone (VB) construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Transmission ranges of sensors are not always equivalent. A sensor networks is modeled as a directed graph while sensors have different transmission ranges. In this paper, we will try to find a special Strongly Connected Bidirectional Dominating Set (SCBDS) within minimum routing cost for each pair of nodes in directed graphs. The SCBDS forms a VB of the networks whose sensors have different transmission radius. For any pair of sensors, the length of the shortest path they communicate with each other through VB should be no more than a constant times the length of the shortest path without using VB. We propose a constant approximate scheme to construct the SCBDS with the bounded size 3*(8ρ+1)2(2ρ+1)2/2 opt. A centralized and a distributed algorithm with the same performance ratio are presented to show the details to construct the SCDS in directed graphs. Simulation results show that the average shortest path length through our algorithms is reduced greatly compared with other algorithms.

Research Area(s)

  • Approximation algorithm, Connected dominating set, Wireless sensor networks

Citation Format(s)

Performance-guaranteed strongly connected dominating sets in heterogeneous wireless sensor networks. / Liu, Chunyan; Huang, Hejiao; Du, Hongwei; Jia, Xiaohua.

IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications. IEEE, 2016. 7524455.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review