This paper presents the proposition of a new optimization method calledEnhanced Network Search, which is an extension of the method Modified Network Search to calculate the empirical parameters of the Rakhmatov and Vrudhula model to predict the mobile devices battery lifetime. The new method was evaluated according to the following methodology, at first empirical parameters were computed considering the optimization methods of Improved Network Search, Modified Network Search 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 fone. In a second moment, the Vrudhula andRakhmatov model was validated for each set of parameters obtained, and the simulated data from the model were compared with a set of experimental data. From simulations results was performed a comparative analysis and was found that with the application of the method Enhanced Search Network in the estimation of parameters of the Rakhmatov and Vrudhula model was possible to obtain an easy and intuitive implementation, improving the results obtained in the model accuracy, as well as preserves the runtime.