A new single channel, time division multiple access (TDMA)scheduling protocol, termed "Evolutionary-TDMA", is presented for mobilead hoc networks. The protocol allows nodes in an ad hoc network toreserve conflict-free TDMA slots for transmission to their neighbors.Two topology-dependent schedules are generated and maintained by theprotocol: a broadcast schedule suitable for network control traffic anda mixed schedule which combines unicast, multicast and broadcasttransmissions for user data traffic. The schedules are frequentlyupdated in an evolutionary manner to maintain conflict-freetransmissions. The protocol executes across the entire networksimultaneously in a fully-distributed and parallel fashion. Trafficprioritization and Quality of Service (QoS) can be supported.Simulations have shown that the performance of the E-TDMA protocol isclose to that of centralized algorithms, while being insensitive tonetwork size in terms of scheduling quality and scheduling overhead. Itis a scalable protocol suitable for very large networks, and networks ofvarying size.