A system and method for wireless communication over multi-rate channels are disclosed. One embodiment of the system operates on wake-up schedules for power saving. The system includes a first multi-band wireless station that is capable of using a first frequency band and a second frequency band for wireless communication; and a second multi-band wireless station that is capable of using the first frequency band and the second frequency band for wireless communication. One or more of the first and second stations is configured to maintain therein one or more wake-up schedules on the second frequency band of one or more of the first station, the second station, and an access point. The first and second stations are configured to share the one or more wake-up schedules with each other via the first frequency band. The system allows the stations to effectively associate with each other, thereby saving power.