An advanced MAP transmission scheme for improving Media Access Control(MAC) overhead in the IEEE 802.16e systems is proposed. In the IEEE 802.16e system, when a Base Station(BS) broadcasts a MAP message, which is a control message about scheduling information, it applies a robust Modulation and Coding Scheme(MCS) level and allocates a large amount of radio resources, which induce a huge MAP overhead. Our proposed scheme utilizes piggybacked MAP IEs, in which control messages are concatenated with data packets and transmitted with the MCS level applied to data transmission. Due to the fact that the rate at which data is transmitted is generally higher than the rate at which broadcasting messages are transmitted, the proposed scheme can increase average data rate of a MAP transmission and consequently reduce the amount of resources allocated to the MAP transmission. Numerical analysis and simulations are presented to show that the MAP overhead is critical to system performance and can be improved by the proposed scheme.