The problem of software aging widely exists in long-running software system, and the solution is software rejuvenation. Traditional software rejuvenation strategy has some deficiencies in solving the software aging problems of web services, for example, the higher failure rate and the poorer stability. Therefore, considering web services may have the correlation, at first we classified web service relationship and analyzed the relationship of web services by using the association mining algorithm; secondly we established and continuously fixed the aging model of web services by using the error back-propagation network to calculate the aging weights of web services. On this basis, based on the analysis of web services’ priority, call frequency and aging states, we calculated the rejuvenation cost, constructed the rejuvenation queue, and proposed an adaptive rejuvenation strategy of related web services. The experiment result showed that, compared with traditional regeneration strategy, this strategy improved the stability and dependability of web services.