Distributed Construction of Weakly Connected Dominating Sets for Clustering Mobile Ad hoc Networks

Mtenzi, Fredrick Japhet
December 2005
Journal of Digital Information Management;Dec2005, Vol. 3 Issue 4, p241
Academic Journal
Weakly connected dominating set (WCDS) has been proposed to cluster mobile ad hoc networks and be used as a virtual backbone. There have been some distributed approximation algorithms proposed in the literature for minimum WCDS. But none of them have constant approximation factors. Thus these algorithms can not guarantee to generate a WCDS of small size. Their message complexities may also be as large as O(n²). In this paper, we design a new distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 5 and linear message complexity. Our algorithm requires only single-hop neighborhood knowledge and a message length of O(1). So it is practical.


Related Articles

  • A Mobile Ticket System Based on Personal Trusted Device. Yu-Yi Chen; Chin-Ling Chen; Jinn-Ke Jan // Wireless Personal Communications;Mar2007, Vol. 40 Issue 4, p569 

    Abstract??Advances in wireless network technology and the continuously increasing users of Personal Trusted Device (PTD) make the latter an ideal channel for offering personalized services to mobile users. In this paper, we apply some cryptology (such as public key infrastructure, hashing chain...

  • A Energy-efficient Scheduling Algorithm in mWSN. Xinlian Zhou; Bin Xiao // Proceedings of the International Symposium on Networking & Netwo;Jun2010, p149 

    We research the topological control of the combination of the clustering hierarchical structure and sleep scheduling mechanism. Firstly, present a inner-cluster node scheduling algorithm solution of inner-cluster connectivity coverage problem, which can meet user's expected coverage, avoiding...

  • A novel convex hull-based flooding scheme using 1-hop neighbor information for mobile ad hoc networks. Yang, Shun-Ren; Chiu, Chun-Wei; Yen, Wei-Torng // Wireless Networks (10220038);Oct2011, Vol. 17 Issue 7, p1715 

    Flooding is one of the most essential and commonly used operations in mobile ad hoc networks. Different sender-based and receiver-based flooding algorithms have been presented separately in the literature. To integrate the advantages of sender-based and receiver-based flooding algorithms, this...

  • NETZYME ENTERPRISE WIRELESS SPEEDS MOBILE FUNCTIONS BY 80%.  // Tele-Service News;Sep2004, Vol. 16 Issue 9, p2 

    Focuses on NetZyme Enterprise Wireless, a middleware for mobile computing from Creative Science Systems. Features and capabilities of NetZyme; Challenges of mobile computing addressed by NetZyme; Platforms supported by NetZyme.

  • A seat at the table. Ford, Tracy // RCR Wireless News;7/31/2006, Vol. 25 Issue 31, p10 

    This article comments on how the value of indirect subscribers is evolving as some operators begin to depend more heavily on these customers and other operators find them less lucrative. Indirect subscribers use carriers' networks, but are contracted with an mobile virtual network operator or...

  • AODV-HM: A Hybrid Mesh Ad-hoc On-demand Distance Vector Routing Protocol. Pirzada, Asad Amir; Portmann, Marius; Indulska, Jadwiga // Journal of Research & Practice in Information Technology;2009, Vol. 41 Issue 1, p65 

    Wireless Mesh Networks (WMNs) have recently gained increasing attention and have emerged as a technology with great potential for a wide range of applications. WMNs can be considered as a superset of traditional mobile ad-hoc networks (MANETs), where the network is comprised of mobile client...

  • Making it simple. Fitchard, Kevin // Telephony;5/21/2007, Vol. 248 Issue 9, p20 

    The article assesses the data plans of mobile carriers to gain access to applications and content in the U.S. According to the author, mobile carriers are shifting from an ordinary attitude of charging customers for content to simpler plans of offering packages. He asserts that this shift is...

  • Power saving with p-persistent sleep decision for wireless communications. Wha Jeon; Dong Jeong; Ji Lee // Wireless Networks (10220038);May2010, Vol. 16 Issue 4, p1199 

    In wireless and mobile communications systems, battery power is an essential and limited resource of portable devices. Sleep mode operation is widely used to save battery power. However, by using the sleep mode, the delay in packet transmission increases. In this paper, we propose an adaptive...

  • Mobile and Wireless Computing. Skratt, Alison // IEEE Internet Computing;Mar/Apr2005, Vol. 9 Issue 2, p10 

    This section reviews two articles on mobile and wireless computing published in the January 2005 issue of Network Magazine.

  • IS TRUE MOBILITY AT HAND? Knorr, Eric // InfoWorld;5/10/2004, Vol. 26 Issue 19, p32 

    This article examines technological advances that may allegedly indicate mobility. High-speed 3G bandwidth would allegedly hover in the air everywhere, enabling one to whip out a wireless personal digital assistant (PDA) and turn the backseat of a taxicab into a rolling office with seamless...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics