Electric vehicle (EV) fleets can provide ancillary services, such as frequency regulation, to the utility grid, if their charging/discharging schedules are coordinated appropriately. In this paper, a multi-level architecture for bidirectional vehicle-to-grid regulation service is proposed. In this architecture, aggregators coordinate the charging/discharging schedules of EVs in order to meet their shares of regulation demand requested by the grid operator. Based on this architecture, the scheduling problem of V2G regulation is then formulated as a convex optimization problem, which in turn degenerates to an online scheduling problem for charging/discharging of EVs. It requires only the current and past regulation profiles, and does not depend on the accurate forecast of regulation demand. A decentralized algorithm, which enables every EV to solve its local optimization problem and obtain its own schedule, is applied to solve the online scheduling problem. Based on the household driving pattern and regulation signal data from the PJM market, a simulation study of 1,000 EVs has been performed. The simulation results show that the proposed online scheduling algorithm is able to smooth out the power fluctuations of the grid by coordinating the EV schedules, demonstrating the potential of V2G in providing regulation service to the grid.