Minimum power assignment in wireless ad hoc networks with spanner property

ISSN： 1382-6905

Source： Journal of Combinatorial Optimization, Vol.11, Iss.1, 2006-02, pp. : 99-112

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Power assignment for wireless ad hoc networks is to assign a power for each wireless node such that the induced communication graph has some required properties. Recently research efforts have focused on finding the minimum power assignment to guarantee the connectivity or fault-tolerance of the network. In this paper, we study a new problem of finding the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Here, a spanner means that the length of the shortest path in the induced communication graph is at most a constant times of the length of the shortest path in the original communication graph. Polynomial time algorithm is given to minimize the maximum assigned power with spanner property. The algorithm also works for any other property that can be tested in polynomial time and is monotone. We then give a polynomial time approximation method to minimize the total transmission radius of all nodes. Finally, we propose two heuristics and conduct extensive simulations to study their performance when we aim to minimize the total assigned power of all nodes.

Related content

Power Assignment for k-Connectivity in Wireless Ad Hoc Networks

By Jia Xiaohua Kim Dongsoo Makki Sam Wan Peng-Jun Yi Chih-Wei

Journal of Combinatorial Optimization, Vol. 9, Iss. 2, 2005-03 ,pp. : 213-222 (10)

Springer Publishing Company

Access to resources Recommend Favorite

Optimal solutions to minimum total energy broadcasting problem in wireless ad hoc networks

By Min Manki Prokopyev Oleg Pardalos Panos

Journal of Combinatorial Optimization, Vol. 11, Iss. 1, 2006-02 ,pp. : 59-69 (11)

Springer Publishing Company

Access to resources Recommend Favorite

Computation of minimum transmit power for network connectivity in vehicular ad hoc networks formed by vehicles with random communication range

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS (ELECTRONIC), Vol. 27, Iss. 6, 2014-06 ,pp. : 931-955 (25)

John Wiley & Sons Inc

Access to resources Recommend Favorite

Approximation algorithms for multicast routing in ad hoc wireless networks

By Li Deying

Journal of Combinatorial Optimization, Vol. 21, Iss. 3, 2011-04 ,pp. : 293-305 (13)

Springer Publishing Company

Access to resources Recommend Favorite

Total energy optimal multicasting in wireless ad hoc networks

By Min Manki Pardalos Panos

Journal of Combinatorial Optimization, Vol. 13, Iss. 4, 2007-05 ,pp. : 365-378 (14)

Springer Publishing Company

Access to resources Recommend Favorite