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.
International Journal of Sensor Networks, 2015 Vol.19 No.2, pp.69 - 77
Received: 01 Oct 2012
Accepted: 24 Dec 2012
Published online: 04 Sep 2015 *