On dual power assignment optimization for biconnectivity | Journal of Combinatorial Optimization Skip to main content

Advertisement

Log in

On dual power assignment optimization for biconnectivity

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

Topology control is an important technology of wireless ad hoc networks to achieve energy efficiency and fault tolerance. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model which is a combinatorial optimization problem from topology control technology.

The problem is arisen from the following origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerantly connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity.

We addressed these optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model in (Wang et al. in Theor. Comput. Sci., 2008). In this paper, we propose a novel approximation algorithm, called Candidate Set Filtering algorithm, to compute nearly-optimal solutions. Specifically, our algorithm can achieve 3.67-approximation ratio for both 2-edge connectivity and 2-vertex connectivity, which improves the existing 4-approximation algorithms for these two cases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Calinescu G, Wan P-J (2006) Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks. Mob Netw Appl 11:121–128

    Article  Google Scholar 

  • Chen J-J, Lu H-I, Kuo T-W, Yang C-Y, Pang A-C (2005) Dual power assignment for network connectivity in wireless sensor networks. In: Proceedings of the IEEE GLOBECOM

  • Clementi AEF, Penna P, Silvestri R (1999) Hardness results for the power range assignment problem in packet radio networks. In: Proceedings of the 2nd international workshop on approximation algorithms for combinatorial optimization problems (APPROX), pp 197–208

  • Diestel R (2000) Graph theory, 2nd edn. Springer, Berlin

    Google Scholar 

  • Hajiaghayi M, Immorlica N, Mirrokni VS (2003) Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. In: Proceedings of the 9th annual international conference on mobile computing and networking

  • Kirousis LM, Kranakis E, Krizanc D, Pelc A (2000) Power consumption in packet radio networks. Theor Comput Sci 243:289–305

    Article  MATH  MathSciNet  Google Scholar 

  • Lloyd EL, Liu R (2006) Approximating the minimum number of maximum power users in ad hoc networks. Mob Netw Appl 11:129–142

    Article  Google Scholar 

  • Lloyd E, Liu R, Marathe M, Ramanathan R, Ravi SS (2002) Algorithmic aspects of topology control problems for ad hoc networks. In: Proc. third ACM international symposium on mobile ad hoc networking and computing (mobiHoc), pp 123–134

  • Park M-A, Wang C, Willson III JKV, Wu W, Farago A (2006) Fault-tolerant dual-power assignment in wireless sensor networks, Technical Report, UTDCS-52-06

  • Poojary N, Krishnamurthy SV, Dao S (2001) Medium access control in a network of ad hoc mobile nodes with heterogenous power capabilities. In: IEEE ICC’01, pp. 872–877

  • Rong Y, Choi H, Choi H-A (2004) Dual power management for network connectivity in wireless sensor networks. In: Proceedings of the 18th international parallel and distributed processing symposium

  • Shah V, Krishnamurthy SV, Poojary N (2004) Improving the MAC layer performance in ad hoc networks of nodes with heterogeneous transmit power capabilities. In: IEEE ICC’04

  • Wang C, Park M-A, Willson III JKV, Wu W, Farago A (2008) On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity. Theor Comput Sci 396:180–189

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Chen Wang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, C., Willson, J., Park, MA. et al. On dual power assignment optimization for biconnectivity. J Comb Optim 19, 174–183 (2010). https://doi.org/10.1007/s10878-008-9173-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-008-9173-x

Keywords

Navigation