Multi-hop time reservation using adaptive control for energy efficiency

• US 20040184473A1
• Filed: 03/17/2003
• Published: 09/23/2004
• Est. Priority Date: 03/17/2003
• Status: Active Grant

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: Heinzelman, Wendi, Tavli, Bulent
• Granted Patent: US 7,411,919 B2
• Time in Patent Office: Days
• US Class Current: 370/445
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 72/23 in the downlink direction of a wireless link, i.e. towards a terminal
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The present invention extends the TRACE (Time Reservation Using Adaptive Control for Energy Efficiency) protocol to allow multi-hop communication in dispersed radio networks. The nodes in the network are dynamically clustered based on proximity and interference level. Time is divided into superframes, each cluster choosing a frame within the superframe for data transmission to reduce the likelihood of interference.

Claims

1. A method for assigning a node to a cluster of a plurality of nodes in a network, the network comprising at least one clusterhead which owns a cluster, information being transmitted over the network in frames, each frame comprising (i) a beacon slot for sending a beacon, (ii) a plurality of contention slots for sending requests for data slots, (iii) a header slot for sending a header which comprises a transmission schedule for the frame, (iv) a plurality of information summarization slots for sending summaries of the information, and (v) a plurality of data slots, each for data transmission by one of the nodes, the method comprising:

(a) listening over the network for a beacon sent by a clusterhead in the beacon slot;

(b) if one beacon is heard, assigning the node to a cluster belonging to the clusterhead;

(c) if a plurality of beacons are heard, selecting one of the beacons and joining a cluster belonging to a clusterhead which sent said selected one of the beacons;

(d) if no beacon is heard, determining whether a new cluster can be created; and

(e) if the new cluster can be created, creating the new cluster and operating as the clusterhead of the new cluster.

2. The method of claim 1, wherein step (d) comprises:

(i) determining a level of interference on the network;

(ii) if the level of interference is lower than a predetermined level, proceeding to step (e); and

(iii) if the level of interference is not lower than the predetermined level, waiting for a predetermined time and returning to step (a).

3. The method of claim 2, wherein step (e) comprises:

(i) sending a beacon;

(ii) if a beacon or header is heard from another node, joining a corresponding cluster; and

(iii) if no beacon or header is heard, sending a header and creating a cluster.

4. The method of claim 1, wherein step (c) comprises selecting a strongest one of the beacons.

5. The method of claim 1, wherein step (c) comprises selecting one of the beacons which identifies a clusterhead having a greatest number of available data slots.

6. The method of claim 1, wherein step (c) comprises one of the beacons which identifies a closest clusterhead having an available data slot.

7. The method of claim 1, further comprising:

(f) transmitting information through the network through multiple hops, wherein the information is passed from one clusterhead to another by way of at least one node.

8. The method of claim 7, wherein each of the nodes in the network is assigned a priority from among a plurality of priorities, and wherein, when the network does not have sufficient capacity to permit all of the nodes to transmit the information, packets from the nodes having a highest priority are given preference.

9. The method of claim 1, wherein the information is transmitted over the network in superframes, each superframe comprising a predetermined number of the frames, and wherein each cluster selects one of the predetermined number of the frames for broadcasting information.

10. The method of claim 9, wherein, once the node is assigned to a cluster, the clusterhead of the cluster communicates over a frame in a steady-state mode until:

(A) interference within the frame reaches a predetermined value, in which case the clusterhead switches to a less noisy frame;

(B) interference within all of the frames reaches the predetermined value, in which case the clusterhead resigns and goes back to step (a);

or

(C) the clusterhead hears a beacon from another clusterhead, in which case the clusterhead resigns and joins the cluster belonging to the other clusterhead.

11. The method of claim 10, wherein the clusterhead switches to the less noisy frame with a first predetermined probability and resigns with a second predetermined probability.

12. A method for transmitting information in a network having a plurality of nodes which are grouped into clusters, the method comprising:

(a) dividing time into superframes, each superframe comprising a predetermined number of frames, each frame comprising (i) a beacon slot for sending a beacon, (ii) a plurality of contention slots for sending requests for data slots, (iii) a header slot for sending a header which comprises a transmission schedule for the frame, (iv) a plurality of information summarization slots for sending summaries of the information, and (v) a plurality of data slots, each for data transmission by one of the nodes;

(b) permitting each of the clusters within the network to choose one of the predetermined number of frames;

(c) transmitting information within each of the clusters during said one of the predetermined number of frames in each superframe; and

(d) transmitting information between at least two of the clusters by way of one or more nodes.

13. The method of claim 12, wherein step (c) comprises:

(i) in each of the frames, permitting each of the plurality of nodes to reserve one of the plurality of data slots by sending the requests in the contention slots; and

(ii) maintaining a reservation of each of the plurality of data slots which is reserved by one of the plurality of nodes until said one of the plurality of nodes indicates that it has stopped transmitting.

14. The method of claim 13, wherein, in step (c)(i):

the nodes transmit the requests to reserve data slots;

in an absence of collision, the clusterhead assigns the data slots to the nodes and broadcasts the transmission schedule indicating assignments of the data slots to the nodes; and

if a node which has requested a data slot is not listed in the transmission schedule, the node retransmits its request.

15. The method of claim 13, wherein:

each node sends an information summarization packet during a corresponding one of the information summarization slots; and

each node indicates that it has stopped transmitting by sending an end-of-transmission bit in its information summarization packet.

16. The method of claim 15, wherein:

each node records a power level of the information summarization packet sent by each of a plurality of other nodes to determine a listening cluster of nodes based at least partially on proximity; and

said each node listens to the nodes in the listening cluster.

17. The method of claim 16, wherein:

each node receives the information summarization packets sent by the nodes in its listening cluster, determines in accordance with the information summarization packets which information it wishes to receive, and listens only to the nodes sending the information that it wishes to receive.

18. The method of claim 12, wherein step (d) comprises transmitting the information between said at least two of the clusters by way of at least one node which is in communication with said at least two of the clusters.

19. The method of claim 12, wherein step (d) comprises transmitting the information between said at least two of the clusters by way of at least two nodes, said at least two nodes comprising a first node in communication with a first one of the clusters and a second node in communication with a second one of the clusters, wherein said at least two nodes are in communication with one another.

20. A device for communication within a network, the network comprising a cluster of nodes, at least one of the nodes operating as a clusterhead which owns the cluster, information being transmitted over the network in frames, each frame comprising (i) a beacon slot for sending a beacon, (ii) a plurality of contention slots for sending requests for data slots, (iii) a header slot for sending a header which comprises a transmission schedule for the frame, (iv) a plurality of information summarization slots for sending summaries of the information, and (v) a plurality of data slots, each for data transmission by one of the nodes, the device comprising:

a communication component for communicating with a plurality of other devices within the network; and

a processor, operatively connected to the communication component, for controlling an operation of the communication component such that the device performs the following operational steps;

(a) listening over the network for a beacon sent by a clusterhead in the beacon slot;

(b) if one beacon is heard, assigning the device to a cluster belonging to the clusterhead;

(c) if a plurality of beacons are heard, selecting one of the beacons and joining a cluster belonging to a clusterhead which sent said selected one of the beacons;

(d) if no beacon is heard, determining whether a new cluster can be created; and

(e) if the new cluster can be created, creating the new cluster and operating as the clusterhead of the new cluster.

21. The device of claim 20, wherein, when the device operates as the clusterhead, the processor further performs the following operational steps:

(f) receiving the requests from the nodes for the data slots;

(g) assigning the data slots to the nodes;

(h) sending the header to indicate, in the transmission schedule, assignments of the data slots to the nodes; and

(i) maintaining the assignments of the data slots to the nodes until a node indicates that it has ended transmission.