System and method for collision-free transmission scheduling using neighborhood information and advertised transmission times
First Claim
1. A system for distributed packet scheduling, comprising:
- a physical neighborhood list, wherein the physical neighborhood list is a data structure that is associated with a node in an ad hoc network and includes a transmit time parameter; and
a control packet that is transmitted in response to the transmit time parameter.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention provides a medium access control (MAC) protocol for the collision-free transmission of packets into a channel, such that nodes are assigned time slots for collision-free transmission based on the knowledge they acquire regarding the constituency of their local neighborhoods and the advertisements of the time slots when nodes in local neighborhoods will attempt to transmit again.
The scheduling procedure may utilize an age of the network together with the unique identifiers of nodes. The candidate transmission times for each node are determined using a list of the subsequent transmission times advertised by other nodes. The node discards the advertised transmission times from the list of potential transmission times, and computes its candidate transmission times using a function that provides a varying (pseudorandom) distribution of outputs for a varying sample of inputs. This function may be a hash function, an encryption function, or a table-lookup function. The computation of candidate transmission times uses the identifiers of those nodes for which no advertised transmission time has been obtained.
-
Citations
26 Claims
-
1. A system for distributed packet scheduling, comprising:
-
a physical neighborhood list, wherein the physical neighborhood list is a data structure that is associated with a node in an ad hoc network and includes a transmit time parameter; and
a control packet that is transmitted in response to the transmit time parameter. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for distributed packet scheduling, comprising:
-
determining physical neighborhood information associated with a node in an ad hoc network, wherein the physical neighborhood information includes a node identifier and a transmit time parameter;
creating a control packet in accordance with the physical neighborhood information; and
transmitting the control packet in accordance with the transmit time parameter. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A method for compressing a plurality of neighbor entries in a neighborhood list contained in a network configuration packet, comprising:
-
excluding a neighbor entry when;
the neighbor entry was reported in a round robin list;
when operating in a two-hop-scheduling mode, if the neighbor entry is a three-hop neighbor entry; and
a reported flag associated with the neighbor entry is set; and
including the neighbor entry in a compressed neighborhood list if it has not been excluded. - View Dependent Claims (19, 20)
-
-
21. A method for transmitting a network configuration packet associated with a node in an ad hoc network, comprising:
-
determining a next transmit time associated with the node;
determining a next holdoff time associated with the node;
evaluating a skip transmit flag, and if the skip transmit flag is set;
creating a network configuration packet;
setting a reported flag associated with a neighbor entry in accordance with whether the neighbor entry has been reported; and
transmitting the network configuration flag.
-
-
22. A method for transmission scheduling in an ad hoc network comprising:
-
ordering neighbor entries in a physical neighbor list in accordance with next transmit times associated with neighbor entries;
calculating an earliest subsequent transmit time for each neighbor entry;
setting a temporary transmit time associated with a neighbor node equal to a value representing the addition of an advertised transmit holdoff time associated with the neighbor node to a current transmit time associated with the neighbor node;
holding a neighborhood election; and
scheduling a next transmit time based on the neighborhood election. - View Dependent Claims (23, 24, 25, 26)
-
Specification