System and method for transmission scheduling using network membership information and neighborhood information

• US 20020167960A1
• Filed: 02/28/2002
• Published: 11/14/2002
• Est. Priority Date: 02/28/2001
• Status: Active Grant

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Garcia-Luna-Aceves, Jose J.
• Granted Patent: US 7,142,527 B2
• Time in Patent Office: Days
• US Class Current: 370/442
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 12/43 with synchronous transmission, e.g. time division multiplex [TDM], slotted rings

Abstract

A system and method is directed at providing collision-free transmission of packets into a channel, such that: an upper bound can be enforced for the time elapsed between two consecutive time slots assigned to the same node; no collision-avoidance handshake is required for each packet transmission, and no pre-assignment of transmission times (slots), channels, or codes are required. Time is divided into frames consisting of a known number of time slots, and frames can be further organized into epochs.

Claims

1. A system for scheduling transmissions without collisions for nodes in an ad hoc network, wherein the nodes include a new node and admitted nodes, comprising:

the admitted nodes, wherein each of the admitted nodes include;

a network interface unit arranged to communicate with the nodes within the ad hoc network; and

a transmission scheduling unit operative to perform actions, including;

using a quasi-static method for time slot allocation within a frame to enforce an upper bound on a time elapsed between two time slots allocated to the same node;

determining when the new node has entered the network, and when;

propagating the information that the new node has entered the network to the other admitted nodes within the network within a finite time; and

once the new node is admitted to the network and known by a majority of the admitted nodes known neighbors and thereby, the new node becoming one of the admitted nodes, start using the time slots reserved for quasi-static scheduling;

assigning the time slots for quasi-static scheduling using a network membership date obtained from a routing protocol used in the network;

a storage unit configured to store information relating to the nodes on the network; and

the new node, wherein the new node includes;

a network interface unit arranged to communicate with the nodes within the network; and

a transmission scheduling unit that is arranged to to perform actions, including;

using a dynamic slot allocation method to transmit packets before the new node is admitted to the network;

notifying the nodes on the network that the new node has entered the network;

using a quasi-static method to transmit packets when the new node is admitted to the network; and

determine when the new node has been admitted to the network; and

when, using the quasi-static method after receiving a first update from a neighbor that the neighbor knows the existence of the new node.

2. The system of claim 1, wherein the transmission scheduling unit comprises a frame including separate time slots for dynamic scheduling and time slots for quasi-static scheduling, wherein the separate slots determine an upper bound for time elapsed between the occurrences of time slots.

3. The system of claim 1, wherein propagating the information that the new node has entered the network to the other admitted nodes within the network within the finite time, further comprises each one of the admitted nodes notifying each one of its neighbors that the new node has entered the network.

4. The system of claim 1, wherein using the quasi-static method for time slot allocation within a frame to enforce the upper bound on the time elapsed between the two time slots allocated to the same node, further comprises using a distributed election algorithm to assign the time slots for quasi-static scheduling using a network membership date obtained from a routing protocol used in the network.

5. The system of claim 3, wherein each of the nodes maintains an admitted-node table that specifies all of the nodes in the network that have been admitted for inclusion in the assignment of the time slots reserved for quasi-static scheduling.

6. The system of claim 5, wherein each of the nodes maintains a new-node table that specifies for each one of the nodes in the network a unique identifier and a network time indicating when the new nodes is assumed to have first announced an entry into the network.

7. The system of claim 6, wherein the new nodes delays notifying its entry into the network for a predetermined period of time.

8. The system of claim 7, wherein for quasi-static scheduling the time slots are assigned to the admitted nodes using a deterministic algorithm based on identifiers of all the nodes in the network.

9. The system of claim 8, further comprising, when the new node enters the network, the new node is arranged to notify its neighbors about a network time when it becomes operational.

10. The system of claim 3, wherein the admitted nodes notifies its two closest neighbors.

11. The system of claim 4, further comprising, the admitted nodes including a storage unit that is arranged to maintain an admitted-node table and a new-node table.

12. The system of claim 4, wherein the transmission scheduling unit is further arranged to reconfigure a ratio of the number of the time slots available for quasi-static assignment.

13. The system of claim 11, further comprising moving the new node to the admitted-node table after a predetermined time.

14. The system of claim 11, further comprising synchronizing with the other admitted nodes a time when the new node is added to the admitted-node table.

15. The system of claim 11, wherein the new node uses the quasi-static method after receiving a first update from an admitted node neighbor indicating that it knows about the existence of the new node.

16. The system of claim 11, wherein the new node may start to use a quasi-static scheduling after when all the admitted node neighbors of the new node indicate through update messages that the new node exists.

17. The system of claim 12, further comprising assigning a priority to nodes, wherein the priority is related to how many time slots are allocated to the node.

20. The method of claim 19, further comprising adding a padding time to the hold-down time such that regardless of the network time when the new node became operational, all the nodes in the network start including the new node for the allocation of time slots reserved for a quasi-static scheduling method at a same schedule starting point.

21. The method of claim 19, wherein the new node notifies the network that it is operational after at least one epoch has passed.

22. The method of claim 21, wherein the time slots allocated for quasi-static scheduling may be used to transmit short control packets that are used primarily to maintain time synchronization in the network.

18. A method for admitting a new node into a network without collisions, comprising:

specifying a network time when the new node enters the network;

applying a hold-down time from the network time; and

adding the node to the admitted-node list at the network time plus the hold-down time.

19. The method of 18, wherein the hold-down time is set such that all of the nodes within the network have learned about the existence of the new node by the expiration of the hold-down time.