Method for dynamically allocating time slots of a common TDMA broadcast channel to a network of transceiver nodes

• US 7,082,111 B2
• Filed: 05/15/2001
• Issued: 07/25/2006
• Est. Priority Date: 05/15/2000
• Status: Expired due to Fees

• Current Assignee: Quarterhill Inc. (f/k/a Wi-LAN Inc.)
• Original Assignee: Quarterhill Inc. (f/k/a Wi-LAN Inc.)
• Inventors: Amouris, Konstantinos
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Davis, Cynthia L.
• Application Number:
  US09/855,297
• Publication Number:
  US 20020001294A1
• Time in Patent Office: 1,897 Days
• Field of Search: 370/321, 370/337, 370/347, 370/442
• US Class Current: 370/321
• CPC Class Codes: H04B 7/2656 for structure of frame, burst
• CPC Class Codes: H04Q 11/0421 Circuit arrangements therefor
• CPC Class Codes: H04Q 2213/13098 Mobile subscriber
• CPC Class Codes: H04Q 2213/13216 Code signals, frame structure
• CPC Class Codes: H04Q 2213/13292 Time division multiplexing, TDM
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/1334 Configuration within the switch
• CPC Class Codes: H04Q 2213/13367 Hierarchical multiplexing, add-drop multiplexing
• CPC Class Codes: H04Q 2213/13392 Channels assigned according to rules

Abstract

A method for allocating a set of time slots belonging to a common time division multiple access (TDMA) channel to a network of transceiver nodes is provided. The method includes the steps of dividing the set of time slots into a plurality of time slot sub-sets; defining for each transceiver node a common function that assigns one time slot sub-set of the plurality of time slot sub-sets to each point in space, where each point in space is identified by a unique set of space coordinates; and performing the following steps for each one of the transceiver nodes: periodically identifying a set of space coordinates; and allocating to each transceiver node time slots belonging to the time slot sub-set assigned by the common function to the point in space identified by the periodically identified set of space coordinates. The method further includes the step of resolving time slot allocation conflicts occurring when at least two transceiver nodes are allocated time slots belonging to an identical time slot sub-set and the distance between the at least two transceiver nodes is less than a predetermined distance threshold. This step includes allocating to each one of the at least two transceiver nodes time slots belonging to a different time slot sub-set of the identical time slot sub-set. The periodically identified set of space coordinates corresponds to the current set of space coordinates for each one of the transceiver nodes.

Claims

1. A method for allocating a set of time slots belonging to a common time division multiple access (TDMA) channel to a network of transceiver nodes, the method comprising the steps of:

dividing said set of time slots into a plurality of time slot sub-sets;

defining for each transceiver node a common function that assigns one time slot sub-set of said plurality of time slot sub-sets to each point in space, wherein said each point in space is identified by a unique set of space coordinates; and

performing the following steps for each one of said transceiver nodes;

periodically identifying a set of space coordinates; and

allocating to said each one of said transceiver nodes time slots belonging to the time slot sub-set assigned by said common function to the point in space identified by the periodically identified set of space coordinates; and

resolving time slot allocation conflicts occurring when at least two transceiver nodes of said network of transceiver nodes are allocated time slots belonging to an identical time slot sub-set and the distance between said at least two transceiver nodes is less than a predetermined distance threshold, wherein said resolving step comprises the step of allocating to each one of said at least two transceiver nodes time slots belonging to a different time slot sub-set of said identical time slot sub-set.

2. The method of claim 1, wherein the periodically identified set of space coordinates corresponds to said each one of said transceiver nodes current set of space coordinates.

3. The method of claim 1, further comprising the step of using said set of time slots belonging to said common TDMA channel for managing communication channel resources between a plurality of nodes of said network of transceiver nodes.

4. The method of claim 3, wherein each node of said plurality of nodes communicates on multiple channels on a time multiplex basis.

5. The method of claim 4, further comprising the steps of:

dividing each time slot of said set of time slots belonging to said common TDMA channel into a plurality of time sub-slots; and

designating one time sub-slot of said plurality of time sub-slots as a query time sub-slot;

wherein each source node of said plurality of nodes desiring to send data to a destination sub-set of said each source node'"'"'s respective set of neighboring nodes transmits a query packet including the identifier of each node of said destination sub-set of said respective set of neighboring nodes during the query time sub-slot of an allocated time slot of said set of time slots belonging to said common TDMA channel.

6. The method of claim 5, further comprising the steps of:

storing for each communicating node of said plurality of nodes;

a transmit set of time slot and channel pairs which can be used by said each communicating node to transmit data to said each communicating node'"'"'s said respective set of neighboring nodes; and

a receive set of time slot and channel pairs which can be used by said each communicating node to receive data from each communicating node'"'"'s said respective set of neighboring nodes; and

communicating a portion of the stored time slot and channel pair data between said each source node and said destination sub-set during the subsequent time sub-slots of said allocated time slot.

7. The method of claim 6, wherein said query packet further includes a selected sub-set of said transmit set of time slot and channel pairs stored for said each source node.

8. The method of claim 7, wherein said step of communicating said portion of the stored time slot and channel pair data is performed by sequentially repeating for each destination node of said destination sub-set of said each source node'"'"'s said respective set of neighboring nodes the following steps:

identifying by said each destination node an assignment set of time slot and channel pairs belonging to both the selected sub-set of said transmit set of time slot and channel pairs included in said query control packet and the receive set of time slot and channel pairs stored for said each destination node;

sending by said each destination node a response packet including said assignment set of time slot and channel pairs on which said each destination node desires to receive data from said each source node;

receiving by said each source node said response packet including said assignment set of dine slot and channel pairs; and

sending by said each source node a confirmation packet including said assignment set of time slot and channel pairs which said each source node uses to transmit data to said each destination node.

9. The method of claim 8, wherein:

each neighboring node of said each destination node receiving said response packet identifies in the transmit set of time slot and channel pairs stored for said each neighboring node of said each destination node the time slot and channel pairs belonging to said assignment set of time slot and channel pairs; and

each neighboring node of said each source node receiving said confirmation packet identifies in the receive set of time slot and channel pairs stored for said each neighboring node of said each source node the time slot and channel pairs belonging to said assignment set of time slot and channel pairs.

10. A system for allocating a set of time slots belonging to a common time division multiple access (TDMA) channel to a network of transceiver nodes, said system comprising:

means for dividing said set of time slots into a plurality of time slot sub-sets;

means for defining for each transceiver node a common function that assigns one time slot sub-set of said plurality of time slot sub-sets to each point in space, wherein said each point to space is identified by a unique set of space coordinates;

means for performing the following steps for each one of said transceiver nodes;

periodically identifying a set of space coordinates; and

allocating to said each one of said transceiver nodes time slots belonging to the time slot sub-set assigned by said common function to the point in space identified by the periodically identified set of space coordinates; and

means for resolving time slot allocation conflicts occurring when at least two transceiver nodes are allocated time slots belonging to an identical time slot sub-set and the distance between said at least two transceiver nodes is less than a predetermined distance threshold, wherein said resolving means comprises means for allocating to each one of said at least two transceiver nodes time slots belonging to a different time slot sub-set of said identical time slot sub-set.

11. The system of claim 10, wherein the periodically identified set of space coordinates corresponds to said each one of said transceiver nodes current set of space coordinates.