This paper presents a proposition of a new optimization method called Search in Improved Network, which is an extension of the method Search in Modified Network, to calculate the empirical parameters of the Rakhmatov and Vrudhula model for predicting batteries lifetime used in mobile devices. The new method is evaluated according to the following methodology. At first empirical parameters are computed considering the optimization methods Search in Improved Network, Search in Modified Network, and Least Squares, as well as the experimental data obtained from a testbed, considering a Lhition-Ion battery, model BL5F, used in the Nokia N95 cell phone. In a second moment, the Rakhmatov and Vrudhula model is validated for each set of parameters obtained, and the simulated data from the model are compared with a set of experimental data. From simulations results a comparative analysis is performed and it is found that by the application of the method Search in Improved Network in the parameters estimation of the Rakhmatov and Vrudhula model it is possible to obtain an easy and intuitive implementation, improving the results obtained in the model accuracy, as well as preserving the runtime.