Distributed adaptive scheduling of communications among nodes in a mobile ad hoc network

A method of scheduling communications among nodes in a mobile ad hoc network, comprising:

• defining successive reservation frames in the network each containing a number of time slots for allowing nodes of the network to transmit traffic including messages to one another within certain slots reserved by the nodes while avoiding or reducing potential interference;
• maintaining, at a given node, one or more maps of time slots contained in the reservation frames and identifying the slots as being either free or reserved based on (a) slot reservations made by the given node, and (b) information received by the given node representing slot reservations made by other nodes of the network;
• determining, at the given node, a number of time slots required for containing a certain traffic load desired to be transmitted by the given node;
• selecting, at the given node, a first set of the required number of time slots for containing the traffic load from among those slots identified as free in the maps maintained by the given node;
• confirming that time slots selected at the given node for containing the desired traffic load are free, by transmitting a reservation initiation message (RIM) from the given node, including identifying the first set of time slots in the RIM;
• receiving the RIM at one or more of the other nodes of the network;
• determining, at each node receiving the RIM, which, if any, of the first set of time slots identified in the RIM is reserved according to the maps maintained by the RIM receiving node;
• transmitting a counter reservation initiation message (CRIM) from one or more nodes receiving the RIM only if a RIM receiving node determines that one or more of the time slots identified in the RIM are reserved, and including, in the CRIM transmitted by each RIM receiving node, a Free Bit Illustrated Map (FBIM) containing a map of the slots known by the RIM receiving node as being available;
• receiving at the given node one or more CRIMs if transmitted from the RIM receiving nodes, selecting a revised set of time slots for containing the traffic load from among slots identified as being free in the FBIMs included in the received CRIMs, and transmitting a corresponding new RIM from the given node;
• repeating at the given node the steps of transmitting a RIM, receiving the CRIMs, and selecting a revised set of time slots for containing the traffic load from among slots identified as free in the FBIMs included in the received CRIMs, and transmitting a corresponding new RIM from the given node until no CRIMs are received are after a determined time, thereby confirming that either the first or a last revised set of time slots selected at the given node are free;
• transmitting the desired traffic load from the given node in the set of time slots that are confirmed as being free;
• determining, at the given node, if a current number of slot reservations is sufficient for handling a pending traffic load awaiting transmission in a scheduling queue at the node;
• and
• if it is determined that an excess number of slot reservations are available for the pending traffic load, refraining from transmitting additional RIM messages from the given node until the current reservations expire thus leaving slots associated with the current reservations open for future slot reservations.