Patent ID: 7885240

Claim:
In a multi-hop ad hoc network comprising a plurality of nodes, a method for allocating a plurality of time slots of a frame, wherein the frame comprises: a first number of the time slots for a Time Division Multiple Access (TDMA) portion of the frame comprising at least one or more Hello time slots; and a Carrier Sense Multiple Access (CSMA) portion of the frame comprising a second number of virtual time slots, the method comprising: operating each node of the plurality of nodes to: determine a self-highest slot number based on a particular time slot allocation, wherein the self-highest slot number is determined based on the time slots on which the node is transmitting or receiving, and based on the time slots on which one or more neighbor nodes are transmitting or receiving, wherein the self-highest slot number indicates the highest slot number in the TDMA portion of the frame that is being used by the node or that is being used by a neighbor node of the node; transmit a Hello message when time slots in the TDMA portion of the frame are allocated for a stream, wherein each Hello message comprises (a) time slots being used by the node to receive and transmit; (b) time slots being used by neighbor nodes of the node to receive and transmit; and (c) the self-highest slot number determined by the node; receive at least one Hello message from one or more neighbor nodes; calculate a neighborhood-highest slot number by finding the maximum of all the self-highest slot number values received in the Hello messages from the neighbor nodes and the node's self-highest slot number value; and use the neighborhood-highest slot number to determine the first number of the time slots and the second number of virtual time slots.