Patent ID: 8320321

Claim:
A method for optimizing bandwidth utilization in a multi-hop ad hoc network comprising a plurality of nodes which communicate using a frame comprising a plurality of time slots, 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: determining a virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame based on one or more boundary variables, wherein the one or more boundary variables are computed based on information contained in a hello message received in a hello time slot of the one or more hello time slots, wherein the information contained in the hello message comprises: one or more time slots currently being used by a node and its neighbor nodes, and a Highest Slot Number (HSN) field which indicates a highest slot number being used by the node or its neighbor nodes; determining whether the TDMA portion of the frame comprises free time slots which are no longer being used by the nodes; and updating the virtual boundary by decreasing the first number if the frame includes free time slots by relocating currently used time slots in the TDMA portion of the frame to the free time slots in the TDMA portion of the frame.