Int. J. of Sensor Networks   »   2015 Vol.19, No.2

 

 

Title: Strongly connected dominating and absorbing set in directed disk graph

 

Authors: Zhao Zhang; Weili Wu; Lidong Wu; Yanjie Li; Zongqing Chen

 

Addresses:
College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang 321004, China
Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080, USA
Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080, USA
College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, China
College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, China

 

Abstract: A heterogeneous wireless network can be modelled as a directed disk graph, in which a sensor u can receive signals from sensor v if and only if u is within the transmission range of v. A virtual backbone of such a network is a strongly connected dominating and absorbing set (SCDAS). This paper presents a (2 + ε)-approximation algorithm for the minimum dominating and absorbing set problem (DAS), which, as far as we know, is the first one achieving a constant approximation ratio for DAS without requiring a bounded ratio of maximum transmission range over minimum transmission range. Based on such a DAS, a (4 + 3 ln(2 + ε)opt + ε)-approximation algorithm for SCDAS is presented, where opt is the size of an optimal SCDAS, which improves on the previous approximation ratio (3H(n − 1) − 1), where n is the number of nodes, and H(·) is the Harmonic function.

 

Keywords: dominating sets; absorbing sets; strongly connected sets; directed disk graphs; wireless sensor network; WSNs; wireless networks; approximation ratio; harmonic function.

 

DOI: 10.1504/IJSNET.2015.071629

 

Int. J. of Sensor Networks, 2015 Vol.19, No.2, pp.69 - 77

 

Available online: 04 Sep 2015

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article