Normally the protection relay tracks the power system frequency in real time. It shall provide precise frequency measurement and adjust its sampling frequency according to the system frequency to ensure the accuracy of protection functions. So the frequency estimation is a fundamental function for the protection relay. This paper analyzes the basic principle and the performance of the conventional frequency estimation solution, which is based on discrete phase locked loop technology. To improve the conventional frequency estimation, this paper proposes to execute DFT calculations on single cycle and multi-cycles timing windows simultaneously. The minimum angle offset derived from the single cycle DFT or multi-cycles DFT is selected to calculate the frequency deviation. Besides, different proportional factors can be applied for the calculations of the frequency measurement and the sampling frequency. These strategies can achieve both the stability and shorter settling time of the frequency response. The improved frequency estimation solution is verified with different test scenarios. The simulation results show the new frequency estimation solution with proper data length has better stability under voltage disturbance. Meanwhile the additional time delay due to the longer data length is limited and acceptable for practical application.