  We consider multi-hop wireless networks serving multiple flows in which only
packets that meet hard end-to-end deadline constraints are useful, i.e., if a
packet is not delivered to its destination node by its deadline, it is dropped
from the network. We design decentralized scheduling policies for such
multi-hop networks that attain the maximum throughput of useful packets. The
resulting policy is decentralized in the sense that in order to make a
transmission decision, a node only needs to know the "time-till-deadline" of
the packets that are currently present at that node, and not the state of the
entire network. The key to obtaining an easy-to-implement and highly
decentralized policy is to replace the hard constraint on the number of
simultaneous packet transmissions that can take place on the outgoing links of
a node, by a time-average constraint on the number of transmissions. The policy
thus obtained is guaranteed to provide maximum throughput. Analysis can be
extended to the case of time-varying channel conditions in a straightforward
manner.
  Simulations showing significant improvement over existing policies for
deadline based scheduling, such as Earliest Deadline First, and supporting the
theory, are presented.
