Dynamic time-spectrum block allocation for cognitive radio networks

• US 7,876,786 B2
• Filed: 04/02/2008
• Issued: 01/25/2011
• Est. Priority Date: 12/01/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bahl, Paramvir, Moscibroda, Thomas, Wu, Yunnan, Chandra, Ranveer, Narlanka, Gopala Sri Hari, Yuan, Yuan
• Primary Examiner(s): Vu; Huy D
• Assistant Examiner(s): Duffy; James P
• Application Number:
  US12/061,577
• Publication Number:
  US 20090196180A1
• Time in Patent Office: 1,028 Days
• Field of Search: None
• US Class Current: 370/478
• CPC Class Codes: H04L 5/0023 Time-frequency-space
• CPC Class Codes: H04L 5/0032 Distributed allocation, i.e. involving a plurality of allocating devices, each making partial allocation
• CPC Class Codes: H04L 5/0039 Frequency-contiguous, i.e. with no allocation of frequencies for one user or terminal between the frequencies allocated to another
• CPC Class Codes: H04L 5/0066 Requirements on out-of-channel emissions
• CPC Class Codes: H04L 5/0094 Indication of how sub-channels of the path are allocated
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames

Abstract

Dynamic time-spectrum block allocation for cognitive radio networks is described. In one implementation, without need for a central controller, peer wireless nodes collaboratively sense local utilization of a communication spectrum and collaboratively share white spaces for communication links between the nodes. Sharing local views of the spectrum utilization with each other allows the nodes to dynamically allocate non-overlapping time-frequency blocks to the communication links between the nodes for efficiently utilizing the white spaces. The blocks are sized to optimally pack the available white spaces. The nodes regularly readjust the bandwidth and other parameters of all reserved blocks in response to demand, so that packing of the blocks in available white spaces maintains a fair distribution of the overall bandwidth of the white spaces among active communication links, minimizes finishing time of all communications, reduces contention overhead among the nodes contending for the white spaces, and maintains non-overlapping blocks.

Claims

1. A method, comprising:

sensing communication spectrum utilization among peer nodes capable of using the communication spectrum;

sharing white spaces in the communication spectrum for information transfer between sender-receiver pairs of the peer nodes;

wherein sharing the white spaces includes optimizing utilization of the white spaces, including for each sender-receiver pair of the nodes, negotiating blocks of the white spaces for the information transfer, each block defined by negotiating an available frequency in the communication spectrum, a bandwidth in relation to the frequency, a starting time, and a duration to exchange the information using the frequency and the bandwidth, wherein the bandwidth negotiated for each block is represented by B/N, where B comprises the overall bandwidth of the white spaces and N comprises a measure of congestion in a neighborhood of the sender and the receiver; and

reallocating the blocks at intervals according to changes in the spectrum utilization.

2. The method as recited in claim 1, wherein the peer nodes collaboratively sense the communication spectrum utilization, collaboratively optimize utilization of the white spaces, and collaboratively reallocate the blocks at intervals according to the spectrum utilization, without participation of a centralized node.

3. The method as recited in claim 1, further comprising reallocating the blocks to minimize a finishing time for communications between nodes.

4. The method as recited in claim 1, further comprising reallocating the blocks to reduce contention overhead among the nodes for the white spaces.

5. The method as recited in claim 1, further comprising reallocating the blocks to create blocks of communication spectrum usage that do not overlap within an interference range with respect to each other and with respect to existing allocations of the communication spectrum.

6. The method as recited in claim 1, further comprising optimizing placement of a representation of the blocks in a local spectrum allocation table of each node.

7. The method as recited in claim 6, wherein a sending node negotiates the block by evaluating an overall bandwidth N of the white spaces, the local spectrum allocation table, and a queue size of information to be transferred.

8. The method as recited in claim 1, wherein the negotiating includes sending a request-to-send (RTS) packet, wherein the RTS packet structure contains a view of the spectrum utilization at a node sending the RTS packet.

9. The method as recited in claim 1, wherein the congestion measure N is approximated from a number of blocks stored in a local allocation table of one of the nodes.

10. The method as recited in claim 1, further comprising evaluating bandwidth options for each block in decreasing order of bandwidth, starting at a bandwidth greater than B/N;

for each bandwidth being evaluated, estimating a corresponding duration of the block for transmitting the information based on a current queue size of the information to be transferred; and

when the estimated duration exceeds a selected maximum block duration, then setting the duration of the block to the value of the maximum block duration.

11. The method as recited in claim 1, wherein when additional pairs of the nodes negotiate for blocks of the white spaces, then all pairs negotiating for blocks reduce their share of the bandwidth to increase parallelism.

12. The method as recited in claim 1, wherein negotiating the duration of the block is based on a balance between shortening each block to reduce delay and improve connectivity versus lengthening each block to manage an amount of contention for the white spaces;

wherein a maximum block duration is selected to amortize overhead associated with the contention for the white spaces;

wherein a sending node queues the information in order to transfer the information for the entire maximum block duration.

13. The method as recited in claim 12, wherein the maximum block duration is selected to ensure that a rate at which handshakes between nodes for negotiating the white spaces is greater than or equal to a rate at which the nodes return to a control channel for contending for the white spaces.

14. The method as recited in claim 12, further comprising aggregating packets of the information in order to transfer the information for the entire maximum block duration.

15. A system, comprising:

wireless nodes, each capable of self-tuning a variable frequency parameter and an associated variable bandwidth parameter for transferring information via a communication spectrum;

a network engine in each wireless node to sense communication spectrum utilization among peer nodes and share white spaces in the communication spectrum for transferring information;

a local allocation table in each node to store a view of local spectrum allocation with respect to time; and

a spectrum allocation engine in each wireless node to negotiate time-frequency blocks of the communication spectrum for the information transfer, each block defined by an available frequency in the communication spectrum, a bandwidth in relation to the frequency, a starting time, and a duration to exchange the information using the frequency and the bandwidth,

wherein the spectrum allocation engine evaluates bandwidth options for each block in decreasing order of bandwidth, starting at a bandwidth greater than B/N, where B comprises an overall bandwidth of the white spaces and N comprises a measure of congestion in a neighborhood of a sender and a receiver.

16. The system as recited in claim 15, wherein the spectrum allocation engine negotiates the block by evaluating an overall bandwidth of the white spaces, the local spectrum allocation table, and a queue size with respect to the information to be transferred.

17. The system as recited in claim 15, wherein the spectrum allocation engine adapts the frequency, bandwidth, start time, and duration of a block at regular intervals according to the overall bandwidth of white spaces in the communication spectrum and a congestion in a neighborhood of a sender and a receiver.

18. The system as recited in claim 15, wherein the spectrum allocation engine;

estimates, for each bandwidth being evaluated, a corresponding duration of the block for transmitting the information based on a current queue size of the information to be transferred; and

when the estimated duration exceeds a selected maximum block duration, sets the duration of the block to the value of the maximum block duration.

19. The system as recited in claim 15, wherein the spectrum allocation engine selects a maximum block duration to amortize overhead associated with contention among the nodes for the white spaces;

wherein a sending node queues the information in order to transfer the information for the entire maximum block duration.

20. A method, comprising:

sensing communication spectrum utilization among peer nodes capable of using the communication spectrum;

sharing white spaces in the communication spectrum for information transfer between sender-receiver pairs of the peer nodes;

wherein sharing the white spaces includes optimizing utilization of the white spaces, including for each sender-receiver pair of the nodes, negotiating blocks of the white spaces for the information transfer, each block defined by negotiating an available frequency in the communication spectrum, a bandwidth in relation to the frequency, a starting time, and a duration to exchange the information using the frequency and the bandwidth,

wherein when additional pairs of the nodes negotiate for blocks of the white spaces, then all pairs negotiating for blocks reduce their share of the bandwidth to increase parallelism; and

reallocating the blocks at intervals according to changes in the spectrum utilization.