A dominating and absorbent set in a wireless ad-hoc network with different transmission ranges

ABSTRACT

Unlike a cellular or wired network, there is no base station or network infrastructure in a wireless ad-hoc network, in which nodes communicate with each other via peer communications. In order to make routing and flooding efficient in such an infrastructureless network, Connected Dominating Set (CDS) as a virtual backbone has been extensively studied. Most of the existing studies on the CDS problem have focused on unit disk graphs, where every node in a network has the same transmission range. However, nodes may have different powers due to difference in functionalities, power control, topology control, and so on. In this case, it is desirable to model such a network as a disk graph where each node has different transmission range. In this paper, we define Minimum Strongly Connected Dominating and Absorbent Set (MSCDAS) in a disk graph, which is the counterpart of minimum CDS in unit disk graph. We propose a constant approximation algorithm when the ratio of the maximum to the minimum in transmission range is bounded. We also present two heuristics and compare the performances of the proposed schemes through simulation.

REFERENCES

• 1: Fei Dai , Jie Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.908-920, October 2004 [doi>10.1109/TPDS.2004.48]
• 2: Stefan Funke , Alexander Kesselman , Ulrich Meyer , Michael Segal, A simple improved distributed algorithm for minimum CDS in unit disk graphs, ACM Transactions on Sensor Networks (TOSN), v.2 n.3, p.444-453, August 2006 [doi>10.1145/1167935.1167941]
• 3: Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754 ]
• 4: Yingshu Li , My T. Thai , Feng Wang , Chih-Wei Yi , Peng-Jun Wan , Ding-Zhu Du, On greedy construction of connected dominating sets in wireless networks: Research Articles, Wireless Communications & Mobile Computing, v.5 n.8, p.927-932, December 2005 [doi>10.1002/wcm.v5:8]
• 5: My T. Thai , Feng Wang , Dan Liu , Shiwei Zhu , Ding-Zhu Du, Connected Dominating Sets in Wireless Networks with Different Transmission Ranges, IEEE Transactions on Mobile Computing, v.6 n.7, p.721-730, July 2007 [doi>10.1109/TMC.2007.1034]
• 6: Peng-Jun Wan , Khaled M. Alzoubi , Ophir Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.141-149, April 2004 [doi>10.1023/B:MONE.0000013625.87793.13]
• 7: Jie Wu, Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.866-881, September 2002 [doi>10.1109/TPDS.2002.1036062 ]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Performance

Keywords:
absorbent set, disk graph, dominating set, wireless ad-hoc network