This paper focuses on the procurement of load shifting service by optimally scheduling the charging and discharging of PEVs in a decentralized fashion. We assume that the energy flow between PEVs and the grid is bidirectional, i.e., PEVs can also release energy back into the grid as distributed generation, which is known as vehicle-to-grid (V2G). The optimal scheduling problem is then formulated as a mixed discrete programming (MDP) problem, which is NP-hard and extremely difficult to solve directly. To get over this difficulty, we propose a solvable approximation of the MDP problem by exploiting the shape feature of the base demand curve during the night, and develop a decentralized algorithm based on iterative water-filling. Our algorithm is decentralized in the sense that the PEVs compute locally and communicate with an aggregator. The advantages of our algorithm include reduction in computational burden and privacy preserving. Simulation results are given to show the performance of our algorithm.