This work addresses the mini-slot scheduling problem in IEEE 802.16d wireless mesh networks (WMNs).Apractical mini-slot scheduling needs to take into account following issues: the transmission overhead, the scheduling complexity, and the signaling overhead to notify the scheduling results to subscriber stations. We focus in a grid-based WMN, which is the most recommended topology due to its high capacity and connectivity. In this paper, we propose scheduling schemes featured by low complexity and low signaling overhead. The proposed schemes help find periodical and regular schedules, which can balance between transmission overhead and pipeline efficiency. They can achieve near-optimal transmission latencies. Simulation results show that our schemes outperform other schemes, especially when the network size is larger.