Abstract:

The transmission scheduling of wireless mesh networks (WMNs) is modeled as a problem of conflict graph coloring. a new distributed time division multiple access（TDMA） medium access control（MAC） algorithm based on parallel graph coloring is proposed. The algorithm utilizes the advantages of mesh routers and backbone networks, and only depends on local topology and traffic load information. Simulation demonstrates that the proposed scheme achieves significant throughput enhancement approaching optimal scheduling in WMNs, and enjoys very low communication overhead.

Key words: wireless mesh networks, medium access control, parallel graph coloring, distributed scheduling algorithm