# Patent

## Title
Techniques for dynamic resource allocation

## Abstract

Techniques are disclosed that dynamically allocate communications resources in a wireless communications network, such as a wireless personal area network (WPAN). For instance, a wireless communications device may obtain a resource allocation. This resource allocation includes a time slot (e.g., a TDMA time slot) within a wireless communications medium. The device determines a first portion of the time slot in which it intends to transmit data. Also, the wireless communications device relinquishes a second portion of the time slot that occurs after the first portion of the time slot. Based on this relinquishment, a central controller device may reallocate the second portion of the time slot.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This patent application is a continuation of U.S. patent application Ser. No. 13/680,884, entitled “Techniques for Dynamic Resource Allocation,” filed Nov. 19, 2012, which claims the benefit of U.S. patent application Ser. No. 12/653,931, entitled “Techniques for Dynamic Resource Allocation,” filed Dec. 21, 2009, the contents of which are incorporated herein by reference.


BACKGROUND
Wireless communications capabilities are increasingly being integrated into portable devices, including laptop computers, handheld devices (such as personal digital assistants (PDAs)), and mobile phones. The integration of such capabilities can provide users with anywhere and anytime connectivity to information resources.
Many communications systems include a central controller device that manages available network bandwidth. For example, wireless personal area networks (WPANs) may include a piconet controller device (PNC) that allocates resources for multiple wireless communications devices (DEVs). Such WPANs may operate at various frequencies. For example, organizations such as the Wireless Gigabit Alliance (WiGig) promote the development of WPANs in which devices exchange millimeter wave signals at a 60 gigahertz (GHz) frequency range. Such signals may convey data at very high rates. Thus, these networks may support high data rate (HDR) applications, such as high definition television (HDTV).
Time division multiple access (TDMA) is a resource allocation technique for shared medium networks. TDMA allows multiple devices to share a frequency channel by dividing a time period (such as a superframe) into multiple time slots. For instance, multiple devices may be allocated corresponding (non-overlapping) time slots to transmit data. As a result, multiple devices may send transmissions that do not collide (interfere) with each other.
Devices may have time varying resource needs. For instance, certain applications (such as compressed video, telephony, and so forth) produce traffic having variable bit rates (VBRs). Conventional resource allocation techniques may allocate a resource to a device so that the device's maximum resource needs can always be met. Unfortunately, this approach is wasteful. This is because, for most of the time, the device's varying resource needs are well below its allocated amount.



BRIEF DESCRIPTION OF THE DRAWINGS
In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the reference number. The present invention will be described with reference to the accompanying drawings, wherein:
FIG. 1 is a diagram of an exemplary operational environment;
FIG. 2 is a diagram of an exemplary time allocation;
FIG. 3 is a diagram showing a technique of dynamic slot allocation with early announcement;
FIGS. 4A-4E are diagrams showing interactions among multiple devices;
FIG. 5 is a logic flow diagram; and
FIG. 6 is a diagram of an exemplary implementation.



DETAILED DESCRIPTION
Embodiments provide techniques for dynamic resource allocation in a wireless network. For instance, a wireless communications device may obtain a resource allocation. This resource allocation includes a time slot (e.g., a TDMA time slot) within a wireless communications medium. The device determines a first portion of the time slot in which it intends to transmit data. Also, the wireless communications device relinquishes a second portion of the time slot that occurs after the first portion of the time slot. Based on this relinquishment, a central controller device may reallocate the second portion of the time slot.
Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. Thus, appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.
FIG. 1 is a diagram of an exemplary operational environment 100 in which the techniques described herein may be employed. As shown in FIG. 1, this environment includes a central controller device 102 and multiple devices (DEVs) 104a-b. These elements may each be implemented in any combination of hardware and/or software.
Central controller device 102 provides a DEVs 104a-b with mobile communications capabilities. For example, central controller device 102 may operate as a hub through which DEVs 102a-b may communicate with each other. Also, central controller device 102 may provide DEVs 102a-b with access to a packet network (such as the Internet). Accordingly, FIG. 1 shows central controller device 102 coupled to such a packet network 110.
Moreover, central controller device 102 may control access to a wireless communications resource (such as one or more frequency channels or bands). For instance, central controller device 102 may control the allocation of time slots in accordance with a TDMA allocation scheme. This may involve central controller device 102 receiving resource requests from DEVs 104a-b, and granting corresponding time slots within a TDMA frame format.
DEVs 104a-b may each be implemented as various types of devices. Exemplary devices include mobile telephones, smartphones, wireless personal digital assistants (PDAs), mobile internet devices (MIDs), notebook computers, netbooks, nettops, and so forth. Embodiments are not limited to these examples.
DEVs 104a-b (as well as central controller device 102) may communicate wirelessly with each other. Such communications may be either through direct links or through central controller device 102. Thus, the devices of FIG. 1 may form a WPAN in which central controller device 102 operates as a PNC. Such communications involve the exchange of wireless signals that may be at various frequency ranges. For example, in embodiments, these signals are millimeter wave signals at a 60 GHz frequency range.
Each of devices 104a-b is associated with central controller device 102. Moreover, devices 104a-b and central controller device 102 may each have directional antenna (e.g., beamforming) capabilities. Thus, the devices of FIG. 1 may be trained to use directed signal transmissions and signal receptions with each other
When higher frequencies (such as 60 GHz) are employed, greater signal propagation losses occur. Thus, such directional antenna features may advantageously handle these losses and achieve substantial wireless communications ranges for the transmission of data at very high data rates (e.g., at rates greater than 1 gigabit per second). Thus, embodiments may exchange data corresponding to high data rate applications, such as uncompressed HDTV (as well as other applications).
In embodiments, transmissions by the devices in FIG. 1 are each based on a repeating pattern called a superframe. FIG. 2 is a diagram showing an exemplary superframe format. In particular, FIG. 2 shows a frame format that includes consecutive superframes 202n and 202n+1.
This superframe format provides for wireless transmission according to a TDMA resource allocation scheme that allocates time slots for devices to send their transmissions. These time slots may be allocated in response to individual device requests. For instance, FIG. 2 shows a time allocation request 204 being transmitted in superframe 202n. This request is transmitted from a device to a central controller device. For example, in the context of FIG. 1, request 204 may be sent from DEV 104a or DEV 104b to central controller device 102.
Upon receipt of this request, the central controller device may allocate a corresponding time slot to the requesting device. In particular, FIG. 2 shows an allocated time slot 206 in superframe 202n+1. During this time slot, the requesting device may send its transmissions. In embodiments, this allocation may be indicated in a beacon transmitted by the central controller device. Embodiments, however, may employ other indication techniques.
A drawback of TDMA is that it may be slow in allocating time slots. More particularly, a device requesting an allocation (or to change an existing allocation) may have to wait approximately one superframe. For example, FIG. 2 shows that a delay 208 occurs between request 206 and the corresponding allocation 208. Thus, TDMA allocation can be inefficient.
While conventional TDMA may be satisfactory for devices needing a constant bit-rate (CBR) data transfer, it is often inadequate for variable bit rate (VBR) applications. For instance, VBR applications, such ones employing compressed bit-streams, do not offer transmitting devices with a priori knowledge regarding how much data is available for each of its allocated time slots.
As discussed above, an approach to guaranteeing sufficient transmission capacity for a device involves a central controller device (e.g., a PNC) providing a maximal allocation. In particular, this maximal allocation provides the device with a time slot large enough for the device to transmit the maximum possible number of bits that it can. Unfortunately, devices would typically use only a fraction (e.g., one-half or one-tenth) of such a maximally allocated slot. Thus, this approach wastes bandwidth that could be used by other devices. Such other devices may include devices that do not have pre-allocated time slots, but need to transfer data from time to time.
Another approach to guaranteeing sufficient transmission capacity for a device involves dividing a maximally allocated slot into several smaller mini-slots. In this approach, a VBR device stops at the end of each mini-slot and asks the central controlling device to continue using the next mini-slot. This procedure may be performed until all of the device's available data (e.g., all of its buffered data) has been sent. However, with this approach, the involved devices (e.g., the PNC, the VBR device, and any other devices requesting allocations) would unfortunately be involved in a tedious handshake. Moreover, such a handshake would need to be resolved in a relatively short amount of time. Thus, this approach may be complicated, power consuming, and prohibitive for handheld devices.
Embodiments may provide sufficient transmission capacity through an approach that involves dynamic allocation with early announcement. FIG. 3 is a diagram showing an example of this approach. In particular, this diagram shows a time slot 302, which is allocated to a first wireless communications device (DEV1). This time slot was allocated by a central controller device (such as a PNC).
Various intervals (or portions) exist within time slot 302. For instance, FIG. 3 shows an announcement 304 that is sent by DEV1. Announcement 304 indicates a portion of time slot 302 that DEV1 intends to transmit, as well as a portion of time slot 302 that DEV1 has relinquished.
In embodiments, announcement 304 may include various information. For example, announcement 304 may include a duration of a time interval (which starts at the end of announcement 304) during which DEV1 intends to transmit data. In FIG. 3, a block 305 shows reception of announcement portion 304 by the central controller device.
As described herein, a wireless communications device may retain a portion of its time slot to transmit its available data. For instance, FIG. 3 shows a first transmission portion 306 that DEV1 utilizes to transmit data.
FIG. 3 shows that a grant 308 follows first transmission portion 306. Grant 308 (which is transmitted by the central controller device) indicates how the remainder of time slot 302 is to be allocated. For example, in FIG. 3, grant 308 indicates that a second wireless communications device (DEV2) has been allocated the remainder of time slot 302. Accordingly, FIG. 3 shows a second transmission portion 310 (e.g., the remainder of time slot 302) that DEV2 uses to transmit data.
Alternatively, grant 308 may be transmitted earlier. For example, when directed antenna patterns (e.g., beamforming patterns) are employed, the central controller device may send grant 308 to DEV2 while DEV1 is transmitting first transmission portion 306. This is because such beamforming patterns may allow grant 308 to not interfere with first transmission portion 306. This may advantageously cause power savings by the central controller device.
FIGS. 4A-4E are diagrams showing an exemplary sequence of interactions among multiple devices. These devices include a PNC and four other wireless communications device (shown as DEV1-DEV4). Also, these diagrams show exemplary directional antenna patterns.
FIG. 4A shows a steady state in which unengaged devices DEV1 and DEV2 are listening to the PNC. Also, FIG. 4A shows directional antenna patterns employed by these devices. For instance, DEV1 and DEV2 have receive antenna patterns 402 and 404, respectively. These patterns are directed towards the PNC. Also the PNC has a receive antenna pattern 406, which is pointed away from DEV1 and DEV2, and towards another device (not shown).
FIGS. 4B-E illustrate different interactions during a time slot that is allocated to DEV1. For instance, FIG. 4B shows DEV1 having a transmit/receive antenna pattern 408 that is directed to the PNC. Likewise, the PNC has a transmit/receive antenna pattern 410 that is directed towards DEV1. Through these patterns, DEV1 sends an announcement 450 to the PNC. As described herein, this announcement indicates a portion of the allocated time slot that DEV1 intends to utilize for data transmission. Also, FIG. 4B shows DEV2 having a receive antenna pattern 412 that is directed towards the PNC.
In FIG. 4C, DEV1 is shown sending a data transmission 452 to DEV2. Accordingly, FIG. 4C shows DEV1 having a transmit/receive antenna pattern 414 that is directed towards DEV2. Likewise, FIG. 4C shows DEV2 having a receive antenna pattern 416 that is directed towards DEV1.
Following this data transmission, FIG. 4D shows the PNC sending a grant message 454 to DEV3. This grant message allocates the remainder of DEV1's time slot to DEV3. Thus, FIG. 4D also shows the PNC having a transmit antenna pattern 418 directed towards DEV3, and DEV3 having a receive antenna pattern 420 that is directed to the PNC.
Based on grant message 454, FIG. 4E shows DEV3 sending a data transmission 456 to DEV 4. Furthermore, FIG. 4E shows DEV3 having a transmit antenna pattern 422 that is directed towards DEV4, and DEV4 having a receive antenna pattern 424 that is directed towards DEV3.
Operations for the embodiments may be further described with reference to the following figures and accompanying examples. Some of the figures may include a logic flow. Although such figures presented herein may include a particular logic flow, it can be appreciated that the logic flow merely provides an example of how the general functionality described herein can be implemented. Further, the given logic flow does not necessarily have to be executed in the order presented unless otherwise indicated. In addition, the given logic flow may be implemented by a hardware element, a software element executed by a processor, or any combination thereof. The embodiments are not limited to this context.
FIG. 5 illustrates an exemplary logic flow 500, which may be representative of the operations executed by one or more embodiments described herein. The logic flow of FIG. 5 is described in the context of a wireless communications device (e.g., a DEV) and a central controller device (e.g., a PNC). Thus, this flow may be employed in the contexts of FIGS. 1-4E. Embodiments, however, are not limited to these contexts. Also, although FIG. 5 shows particular sequences, other sequences may be employed. Moreover, the depicted operations may be performed in various parallel and/or sequential combinations.
At a block 502, the wireless communications device obtains a resource allocation from the central controller device. This resource allocation may include a time slot (e.g., a TDMA slot) within a wireless communications medium. In embodiments, block 502 may comprise the wireless communications device obtaining the resource allocation (e.g., DEV1) by sending a request message to the central controller device (PNC). In response, the central controller device sends a broadcast transmission that includes the resource allocation slots of all devices (like DEV1 & DEV2) that may be used by VBR traffic and therefore candidates for other devices (like DEV3 & DEV4) to use the remaining non-used portions. This transmission may be a beacon. However, embodiments may employ other forms of broadcast and/or point-to-point transmissions.
When such candidate allocated time slot (302) arrives, the directed antenna of each device (like DEV3 & DEV4) is directed to the PNC to be ready to get the grant that allows using remaining time of the slot or to reuse any part of the slot.
In block 504, at the start of the slot the directed antenna of the PNC is directed to the device (DEV1) which is owner of the slot (FIG. 4B). Then device (DEV1) directs it's antennas to the PNC and sends to the PNC an announcement that includes the duration that the device is going to utilize in the current slot. This may involve, for example, the wireless communications device determining the amount of data it has in a transmission buffer (e.g., an encoder output buffer).
At a block 508, the wireless communications device relinquishes a second portion (the remaining portion) of its resource allocation. This second portion of the time slot occurs after the first portion of the time slot.
Upon receipt of the relinquishment (e.g., the announcement message), the central controller device reallocates the second portion of the resource allocation at a block 510. This may involve granting the second portion to one or more other wireless communications devices (e.g., other DEV(s)). Alternatively, this may involve the central controller device retaining the second portion of the resource allocation for its own use (e.g., for its own data transmission).
The central controller device may employ various techniques for reallocating the second portion. For instance, in embodiments, the central controller device may employ a polling mechanism that requests whether other wireless communications device(s) have data to transmit. If so, then the central controller device sends a grant to such a device. Upon receipt of this grant, the wireless communications device may transmit its data within the second portion of the time slot.
FIG. 6 is a diagram of an implementation 600 that may be included in a wireless communications device, such as a DEV (e.g., DEVs 104a and 104b) and/or central controller devices (e.g., central controller device 102). Implementation 600 may include various elements. For example, FIG. 6 shows implementation 600 including multiple antennas 602a-c, a transceiver module 604, a host module 606, a control module 608, and a transmit buffer 611. These elements may be implemented in hardware, software, or any combination thereof.
Antennas 602a-c provide for the exchange of wireless signals with remote devices. Although three antennas are depicted, any number of antennas may be employed. Also, embodiments may employ one or more transmit antennas and one or more receive antennas. Such multiple antenna arrangements may be employed for beamforming and/or the employment of multiple spatial streams with a remote device.
Transceiver module 604 provides for the exchange of information with other devices. As shown in FIG. 6, transceiver module 604 includes a transmitter portion 610, and a receiver portion 612. During operation, transceiver module 604 provides an interface between antennas 602a-c and other elements, such as host module 606, control module 608, and transmit buffer 611. For instance, transmitter portion 610 receives symbols from such elements, and generates corresponding signals for wireless transmission by one or more of antennas 602a-c. This may involve operations, such as modulation, amplification, and/or filtering. However, other operations may be employed.
Conversely, receiver portion 612 obtains signals received by one or more of antennas 602a-c and generates corresponding symbols. In turn, these symbols may be provided to elements, such as host module 606 and control module 608. This generation of symbols may involve operations, including (but not limited to) demodulation, amplification, and/or filtering.
The signals generated and received by transceiver module 604 may be in various formats. For instance, these signals may be modulated in accordance with an orthogonal frequency division multiplexing (OFDM) scheme. However, other schemes and formats (e.g., QPSK, BPSK, FSK, etc.) may be employed.
To provide such features, transmitter portion 610 and receiver portion 612 may each include various components, such as modulators, demodulators, amplifiers, filters, upconverters, and/or downconveters. Such components may be implemented in hardware (e.g., electronics), software, or any combination thereof.
The symbols exchanged between transceiver module 604 and other elements may form messages or information associated with one or more protocols, and/or with one or more user applications. Thus, these elements may perform operations corresponding to such protocol(s) and/or user application(s). Exemplary protocols include (but are not limited to) various media access control and discovery protocols. Exemplary user applications include telephony, messaging, e-mail, web browsing, content (e.g., video and audio) distribution/reception, and so forth.
Moreover, in transmitting signals, transceiver module 604 may employ various access techniques. For example, transceiver module 604 may operate in accordance with a TDMA technique. Embodiments, however, are not limited to such techniques.
In embodiments, control module 608 may perform various operations described herein. For instance, control module 608 may generate, receive, and process various resource allocation messages, as described herein. Such messages may include resource allocation requests, allocation indications (e.g., conveyed in beacons), announcement messages, and grant messages. Moreover, control module 608 may determine the amount of available data in transmission buffer 611.
Transmission buffer 611 stores data that is ready for wireless transmission. Such data may be encoded and/or compressed data associated with one or more applications (e.g., VBR applications). In embodiments, transmission buffer 611 includes a storage medium (e.g., memory). Also, transmission buffer 611 may be arranged as a first-in, first-out (FIFO) buffer.
Host module 606 may exchange symbols with transceiver module 604 (e.g., through transmission buffer 611) that correspond to wireless signals exchanged with remote devices. These symbols may form messages or information associated with one or more protocols, and/or one or more user applications. Thus, host module 606 may perform operations corresponding to such protocol(s) and/or user application(s). Exemplary protocols include various media access, network, transport and/or session layer protocols. Exemplary user applications include telephony, messaging, e-mail, web browsing, content (e.g., video and audio) distribution/reception, and so forth.
As described herein, various embodiments may be implemented using hardware elements, software elements, or any combination thereof. Examples of hardware elements may include processors, microprocessors, circuits, circuit elements (e.g., transistors, resistors, capacitors, inductors, and so forth), integrated circuits, application specific integrated circuits (ASIC), programmable logic devices (PLD), digital signal processors (DSP), field programmable gate array (FPGA), logic gates, registers, semiconductor device, chips, microchips, chip sets, and so forth.
Examples of software may include software components, programs, applications, computer programs, application programs, system programs, machine programs, operating system software, middleware, firmware, software modules, routines, subroutines, functions, methods, procedures, software interfaces, application program interfaces (API), instruction sets, computing code, computer code, code segments, computer code segments, words, values, symbols, or any combination thereof.
Some embodiments may be implemented, for example, using a storage medium or article which is machine readable. The storage medium may store an instruction or a set of instructions that, if executed by a machine, may cause the machine to perform a method and/or operations in accordance with the embodiments. Such a machine may include, for example, any suitable processing platform, computing platform, computing device, processing device, computing system, processing system, computer, processor, or the like, and may be implemented using any suitable combination of hardware and/or software.
The storage medium or article may include, for example, any suitable type of memory unit, memory device, memory article, memory medium, storage device, storage article, storage medium and/or storage unit, for example, memory, removable or non-removable media, erasable or non-erasable media, writeable or re-writeable media, digital or analog media, hard disk, floppy disk, Compact Disk Read Only Memory (CD-ROM), Compact Disk Recordable (CD-R), Compact Disk Rewriteable (CD-RW), optical disk, magnetic media, magneto-optical media, removable memory cards or disks, various types of Digital Versatile Disk (DVD), a tape, a cassette, or the like. The instructions may include any suitable type of code, such as source code, compiled code, interpreted code, executable code, static code, dynamic code, encrypted code, and the like, implemented using any suitable high-level, low-level, object-oriented, visual, compiled and/or interpreted programming language.
While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not in limitation. For example, the techniques described herein are not limited to WPANs.
Accordingly, it will be apparent to persons skilled in the relevant art that various changes in form and detail can be made therein without departing from the spirit and scope of the invention. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

## Claims

1. An apparatus, comprising:
a transceiver to receive a transmission indicating a resource allocation, wherein the resource allocation comprises a time duration within a wireless communications medium; and
a control module to determine, based at least in part on the resource allocation and a usage portion of the time duration for data transmission or data reception, a relinquishment of a portion of the time duration;
wherein the transceiver is to send, to a remote device:
a transmission indicating the relinquishment, wherein the transceiver is to send the transmission indicating the relinquishment prior to the relinquished portion; and
a data transmission in a second time duration prior to the relinquished portion of the time duration, the data transmission comprising millimeter wave signals.

2. The apparatus of claim 1, wherein the remote device is a central controller device.

3. The apparatus of claim 1, wherein the transceiver is to refrain from transmitting data during the relinquished portion.

4. The apparatus of claim 1, further comprising one or more antennas to provide directional beamforming.

5. The apparatus of claim 1, further comprising a host module to perform operations of a user application.

6. The apparatus of claim 5, wherein the user application is a variable bit rate (VBR) application.

7. A method, comprising:
obtaining a resource allocation for a wireless communications device, the resource allocation comprising a time duration within a wireless communications medium;
relinquishing a portion of the time duration based at least in part on the resource allocation and a usage portion of the time duration for data transmission or data reception,
wherein relinquishing the portion of the time duration comprises sending a transmission indicating the relinquishment to a remote device, wherein the transmission indicating the relinquishment is sent prior to the relinquished portion; and
transmitting data in a second time duration prior to the relinquished portion of the time duration, the data transmission comprising millimeter wave signals.

8. The method of claim 7, wherein the relinquished portion of the time duration is a final portion of the time duration.

9. The method of claim 7, further comprising refraining from transmitting data during the relinquished portion.

10. The method of claim 7, wherein transmitting data in the time duration prior to the relinquished portion of the time duration comprises performing directional beamforming of the millimeter wave signals.

11. The method of claim 7, further comprising performing operations of a user application.

12. The method of claim 11, wherein the user application is a variable bit rate (VBR) application.

13. An article comprising a non-transitory machine-accessible medium having stored thereon instructions that, when executed by one or more machines, cause the one or more machines to:
obtain a resource allocation for a wireless communications device, the resource allocation comprising a time duration within a wireless communications medium;
relinquish a portion of the time duration based at least in part on the resource allocation and a usage portion of the time duration for data transmission or data reception,
wherein relinquishing the portion of the time duration comprises sending a message indicating the relinquishment to a remote device, wherein the message is sent prior to the relinquished portion; and
transmit data in a second time duration prior to the relinquished portion of the time duration, the data transmission comprising millimeter wave signals.

14. The article of claim 13, wherein the instructions, when executed by the one or more machines, cause the one or more machines to perform operations of a user application.

15. The article of claim 14, wherein the user application is a variable bit rate (VBR) application.

16. The article of claim 13, wherein the relinquished portion of the time duration is a final portion of the time duration.

17. The article of claim 13, wherein the non-transitory machine-accessible medium having stored thereon further instructions that, when executed by the one or more machines, cause the one or more machines to refrain from transmitting data during the relinquished portion.

18. The article of claim 13, wherein the non-transitory machine-accessible medium having stored thereon further instructions that, when executed by the one or more machines, cause the one or more machines to perform directional beamforming of the millimeter wave signals.