Given the explosive growth of mobile subscribers, network operators have to densely deploy base stations to serve the exponentially increasing access demands. Nevertheless, recent researches have pointed out that base station operation has been identified as a significant portion of total system energy consumption and 90% of the traffic is carried by only 40% of base stations even under peak traffic demand. Therefore, switching off underutilized base stations for saving power is an important issue with the increasing awareness of environmental responsibility and economical concerns of network operators. This paper targets the problem of dynamic base station operation, with an objective to minimize total power consumption of all base stations. We prove this problem is \(\mathcal{NP}\)-hard and cannot be approximated in polynomial time with a ratio better than \(\frac{3}{2}\). Then, we propose a distributed algorithm to tackle it. The simulation results show that our proposed algorithm can significantly reduce the network power consumption.