TECHNICAL FIELD The invention relates generally to communication systems and, more specifically but not exclusively, to scheduling data transfers in communication systems.
BACKGROUND Wireless networks continue to experience rapid growth in data traffic. The increase in use of data-intensive services, such as video download and streaming, is straining the capacity of wireless networks. Furthermore, the use of such data-intensive services on smartphones is projected to grow rapidly over the next few years. This is putting pressure on network operators to perform extensive network capacity upgrades. The network operators are seeking ways to keep network upgrade costs in check while meeting capacity challenges.
SUMMARY
Various deficiencies in the prior art are addressed by embodiments for scheduling data transfers of a wireless device.
In one embodiment, an apparatus includes a processor and a memory communicatively connected to the processor, where the processor is configured to group a plurality of wireless access points into a plurality of wireless access point groups based on a plurality of costs of usage of the respective wireless access points, prioritize the wireless access point groups based on the costs of usage of the respective wireless access points, and determine assignment of the data transfers of the wireless device to ones of the wireless access points based on the prioritization of the wireless access point groups.
In one embodiment, a computer-readable storage medium stores instructions which, when executed by a computer, cause the computer to perform a method for scheduling a plurality of data transfers for a wireless
device. The method includes grouping a plurality of wireless access points into a plurality of wireless access point groups based on a plurality of costs of usage of the respective wireless access points, prioritizing the wireless access point groups based on the costs of usage of the respective wireless access points, and determining assignment of the data transfers of the wireless device to ones of the wireless access points based on the prioritization of the wireless access point groups.
In one embodiment, a method includes a computer-readable storage medium stores instructions which, when executed by a computer, cause the computer to perform a method for scheduling a plurality of data transfers for a wireless device. The method includes grouping a plurality of wireless access points into a plurality of wireless access point groups based on a plurality of costs of usage of the respective wireless access points, prioritizing the wireless access point groups based on the costs of usage of the respective wireless access points, and determining assignment of the data transfers of the wireless device to ones of the wireless access points based on the prioritization of the wireless access point groups.
BRIEF DESCRIPTION OF THE DRAWINGS
The teachings herein can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:
FIG. 1 depicts a high-level block diagram of an exemplary communication system;
FIG. 2 depicts one embodiment of a method for scheduling data transfers for a wireless device using wireless access points;
FIG. 3 depicts an exemplary bipartite graph configured for use in determining assignment of data transfers to uncongested time intervals of wireless access points;
FIG. 4 an exemplary partitioning of a geometric graph for use in determining assignment of data transfers of a wireless device to timeslots of wireless access points;
FIG. 5 depicts one embodiment of a method for using a geometric graph to assign data transfers of a wireless device to timeslots of wireless access points; and
FIG. 6 depicts a high-level block diagram of a computer suitable for use in performing functions described herein.
To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.
DETAILED DESCRIPTION
In general, a data transfer scheduling capability is provided for scheduling data transfers (e.g., data downloads or data uploads) for a wireless device or for a group of wireless devices.
In at least some embodiments, the data transfer scheduling capability is configured to utilize available relatively low cost wireless access points (e.g., Wireless Fidelity (WiFi) access points, femtocells, or the like) and excess capacity of available relatively high cost wireless access points (e.g., access points of macro cellular wireless networks, such as Third Generation (3G) cellular networks, access points of Fourth Generation (4G) access points, or the like) to perform data transfers for wireless devices. In this manner, the network operator is able to increase available capacity without incurring additional network expansion costs.
FIG. 1 depicts a high-level block diagram of an exemplary communication system.
As depicted in FIG. 1, exemplary communication system 100 includes a wireless device 110, a plurality of wireless access points 1201 - 120N (collectively, wireless access points 120), a communication network 130, a
plurality of data nodes 1401 - 140M (collectively, data nodes 140), and a data transfer scheduler 150.
The wireless device 110 is configured to access one or more data networks for utilizing or providing various functions and services (e.g., one or more of voice communications, data communications, consuming content, providing content, or the like, as well as various combinations thereof).
The wireless device 110 is configured to access multiple types of wireless access points 120. For example, the wireless device 110 may be configured to access one or more cellular wireless access networks (e.g., 3G cellular networks, 4G cellular networks, femtocells, or the like) and one or more non-cellular wireless access networks (e.g., WiFi or the like). It will be appreciated that wireless device 110 may be configured to access a set of wireless access points 120 (which may include different types of wireless access points 120) available to the wireless device 110 at any given time. It will be further appreciated that the set of wireless access points 120 available to the wireless device 110 may vary over time (e.g., for a fixed wireless device 110 or a mobile wireless device 110 where new wireless access points 120 are activated, for a mobile wireless device 110 where the mobile wireless device 110 moves geographically, or the like, as well as various combinations thereof). In these cases, availability of wireless access points 120 to wireless device 110 may depend on factors such as one or more capabilities of the wireless device 110 (e.g., types of wireless access supported), one or more capabilities of wireless access points 120 (e.g., signal strength, security features, or the like), or the like, as well as various combinations thereof.
The wireless device 110 may be an end user device or any other suitable type of wireless device (e.g., a laptop computer, tablet computer, smartphone, cell phone, or the like).
The wireless device 110 may include one or more clients (e.g., a web browsing client, a streaming video client, or the like, which are omitted for purposes of clarity) which may be configured to submit requests for data transfers, specify data transfer priorities, specify data transfer deadlines, or
the like (e.g., a web browsing client, a streaming video client, or the like). The wireless device 110 may include one or more clients configured to obtain network status information and to provide the obtained network status information to data transfer scheduler 150 for use by data transfer scheduler 150 in scheduling data transfers for wireless device 110 (e.g., by monitoring and reporting one or more of network accessibility information, network performance information, or the like, as well as various combinations thereof). The wireless device 110 may include any other suitable types of clients.
The wireless device 110 may include various other elements (e.g., processor, memory, network interface modules, and the like), which are omitted for purposes of clarity.
The wireless access points 120 are configured to provide wireless network access to wireless devices (illustratively, to wireless device 110). The wireless access points 120 may include any types of wireless access points which may be available to wireless device 110. For example, the wireless access points may include macro cellular wireless access points (e.g., 3G cellular-based wireless access points, 4G cellular-based wireless access points, or the like), femtocells, Wireless Fidelity (WiFi) access points, or the like, as well as various combinations thereof.
In general, many macro cellular wireless networks are traditionally designed to handle peak usage (e.g., sufficient capacity is provisioned to handle peaks in the traffic load). As a result, however, many such macro cellular wireless networks include macro cells that have unused surplus capacity during off-peak times. Additionally, the load of a macro cell often changes dynamically with time (e.g., minute to minute, hour to hour, day to day, and so forth) and, similarly, the load of macro cells typically varies across the macro cells. In at least some embodiments, the data transfer scheduling capability is configured to utilize such surplus capacity of such wireless access points, at various times when the surplus capacity is expected to be available for use, for enabling service providers to handle imminent traffic growth while deferring the cost of network upgrades.
In general, the proliferation of various types of smaller-range (e.g., smaller range than macro cellular access points) access points has ensured that, at many geographic locations, multiple types of wireless access are available to end users (e.g., to a user of wireless device 110). It is understood that such smaller-range access points may serve to provide redundant coverage for macro cellular access points or to fill in gaps in coverage between macro cellular access points. In any event, the numbers and types of relatively low cost wireless access points available to wireless device 110 at any given time may depend on various factors (e.g., deployment of relatively low cost wireless access points, security settings of relatively low cost wireless access points, terminal capabilities of wireless device 110, movements of wireless device 110, or the like, as well as various combinations thereof). In at least some embodiments, the data transfer scheduling capability is configured to utilize such wireless access points, at various times when such wireless access points are expected to be available for use, for enabling service providers to handle imminent traffic growth while deferring the cost of network upgrades.
It is noted that, although primarily depicted and described herein with respect to specific numbers, types, and arrangements of wireless access points 120, any suitable numbers, types, or arrangements of wireless access points 120 may be available to wireless device 110 at any given time (i.e., the depictions of the wireless access points 120 in FIG. 1 merely indicate the availability of multiple wireless access points to wireless device 110, and does not reflect the typical geographic arrangement of wireless access points). The typical arrangements of different types of wireless access points in any particular geographic region will be understood by one skilled in the art. It is noted that the cellular-based wireless access points also may be referred to as cells (e.g., macro cells, femtocells, or the like). It is noted that the wireless access points 120 also may be referred to herein as networks or network access points (e.g., use of a particular wireless access point 120 is indicative of use of the network with which that wireless access point 120 is associated).
The communication network 130 generally represents communication paths between the various types of wireless access points 120, which may belong to various types of wireless networks, and the data nodes 140. For example, for a macro cellular wireless access point, communication network 130 may represent the associated Radio Access Network (RAN) to which the macro cellular wireless access point belongs and the associated wireless core network with which the RAN is associated. For example, for a WiFi access point, the communication network 130 may represent the communication path from the WiFi access point to the Internet. It is noted that the communication paths between such types of wireless access points 120 and data nodes 140 will be understood by one skilled in the art.
The data nodes 140 may be sources of data for wireless user device 110 (e.g., for data downloads in which data is downloaded from the data nodes 140 to the wireless user device 110 for use at the wireless user device 110) or destinations of data for wireless user device 110 (e.g., for data uploads in which data is uploaded by wireless user device 110 for storage on one or more of the data nodes 140). For example, data nodes 140 may include content servers (e.g., Hypertext Transfer Protocol (HTTP) servers, video-on-demand servers, or the like), application servers, cloud-based storage nodes, or the like. The data that is transferred may include any suitable type of data (e.g., files, streaming content, or the like).
The data transfer scheduler 150 is configured to schedule data transfers for wireless device 110. In general, the assignment of a data transfer for wireless device 110 includes assignment of the data transfer (as a whole or in portions) to one or more of the wireless access points 120. The assignment of a data transfer for wireless device 110 may specify the time(s) at which the data transfer is to be performed, one or more parameters related to the data transfer (e.g., minimum bandwidth to be used, type of transcoding to be used, or the like). It is noted that the assignment of data transfers of the wireless device 110 to wireless access points 120 may be specified as a data
transfer schedule including the details of assignment of the data transfers of the wireless device 110 to wireless access points.
The data transfer scheduler 150 may be configured to receive indications of data transfers to be performed for wireless device 110. For example, data transfer scheduler 150 may receive indications of data transfers from wireless device 110 (e.g., when wireless device 110 requests access to data stored in the network, when wireless device 110 indicates an intention to transfer data from the wireless device 110, or the like). For example, data transfer scheduler 150 may receive indications of data transfers from one or more network devices (e.g., one or more of the data nodes 140, one or more network elements configured to make recommendations on behalf of the user(s) of wireless device 110, or the like). The indications of data transfers may be provided to data transfer scheduler 150 in any suitable manner (e.g., using any suitable numbers and/or types of messages, at any suitable times, or the like).
The data transfer scheduler 150 may be configured to obtain various types of information which may be used as a basis for opportunistically scheduling data transfers for wireless device 110 using the wireless access points 120. The information may include network state information associated with wireless access points 120, network interaction information associated with interaction by wireless device 110 with wireless access points 120, one or more additional constraints, or the like, as well as various combinations thereof.
The data transfer scheduler 150 may receive network state information (e.g., at least one of historical state information of the network or current state information of the network). The network state information may include historical network status information, current network status information, or the like. The network state information may include information indicative of the congestion history of the network (e.g., congestion of each of the wireless access points 120 or the like). The network state information may include one or more of per wireless access point statistics (e.g., traffic load on each
wireless access point, variations in traffic load on each wireless access point, per user throughput on each wireless access point, or the like, as well as various combinations thereof). The data transfer scheduler 150 may receive one or more of network state information that is measured and collected by the wireless devices (including the wireless device 110), network state information that is measured and collected by wireless access points 120, network state information that is available from one or more management systems, or the like, as well as various combinations thereof. The network state information may include network availability information, network accessibility information, network congestion information, or the like, as well as various combinations thereof. In this manner, data transfer scheduler 150 may maintain a global state of the network availability, accessibility, and congestion for the set of wireless access points 120 via which data transfers may be scheduled. It is noted that such information may be provided to data transfer scheduler 150 as reported or after preprocessing (which may include combining of data, user data anonymization, or the like).
The data transfer scheduler 150 may receive information indicative of past interaction by the wireless device 110 with the wireless access points 120. The information indicative of past interaction by the wireless device 110 with the wireless access points 120 may include network access patterns for the wireless device 110. The information indicative of past interaction by the wireless device 110 with the wireless access points 120 may include historic or current data on times and durations during which the wireless device 110 is connected to or in the vicinity of the wireless access points 120. The information indicative of past interaction by the wireless device 110 with the wireless access points 120 may include indications of which wireless access points 120 were accessed, when the wireless access points 120 were accessed (e.g., time of day, day or the week, or the like), lengths of time for which the wireless device 110 accessed the wireless access points 120, or the like). The data transfer scheduler 150 also may receive information indicative of current interaction by the wireless device 110 with the wireless
access points 120 (e.g., a current wireless access point(s) 120 with which the wireless device 110 is or could communicate, signal strength information associated with one or more wireless access points 120 in the vicinity of the wireless device 110, or the like). It is noted that wireless device 110 may be considered to be in the vicinity of a wireless access point 120 when the wireless device 110 is capable of communicating with the wireless access point 120 (or of communicating with the wireless access point 120 while satisfying a certain level of quality of communication). The data transfer scheduler 150 may receive one or more of interaction information that is measured and collected by the wireless devices (including the wireless device 110), interaction information that is measured and collected by wireless access devices 120, interaction information that is available from one or more management systems, or the like, as well as various combinations thereof.
The data transfer scheduler 150 may receive information indicative of one or more additional constraints to be considered during scheduling of data transfers for wireless device 110 (e.g., data transfer deadlines associated with data transfers, data transfer priorities of data transfers, one or more user preferences associated with one or more users of wireless device 110, one or more or preferences associated with a network operator, or the like, as well as various combinations thereof).
The data transfer scheduler 150 may be configured to opportunistically schedule data transfers for wireless device 110 using wireless access points 120.
The data transfer scheduler 150 may be configured to opportunistically schedule data transfers by determining costs of usage for wireless access points 120, grouping wireless access points 120 into groups of wireless access points 120 based on costs of usage of the wireless access points 120, and assigning data transfers to one or more wireless access points 120 in one or more of the groups of wireless access points 120.
The cost of usage of a particular wireless access point 120 at a particular time may be based on one or more of a monetary amount paid by
the user for access to and use of the wireless access point 120 of a network associated with the wireless access point 120 (e.g., where macros cellular networks are expected to have a higher cost than WiFi access with Digital Subscriber Line (DSL) backhaul, an amount of congestion associated with the wireless access point 120 or a network associated with the wireless access point 120 (e.g., peak versus off-peak in macro cellular networks, number of connections active on the wireless access point 120, or the like), an energy cost per bit for the wireless access point 120 (e.g., lower cost for a wireless user device with relatively good signal strength and signal-to-noise (SNR), one or more operational costs assigned to the wireless access point by the service provider (e.g., based on one or more factors such as average usage of the wireless access point 120, congestion conditions associated with the wireless access point 120, or the like), one or more temporal conditions (e.g., time of day, day of week, or the like), an indication as to whether or not the wireless access point is managed by the service provider (e.g., a WiFi access point that is not managed by the service provider may have a lower cost than a WiFi access point that is managed by the service provider, both of which may have lower costs that a cellular access point), or the like, as well as various combinations thereof. Accordingly, the costs of usage of the wireless access points 120 may change under various conditions and, thus, the membership of the groups of wireless access points 120 may vary over various conditions. In this manner, various types of cost metrics may be used to prioritize the wireless access points 120 in a manner for maximizing use of lower-cost wireless access points 120 for data transfers and minimizing use of higher-cost wireless access points 120 for data transfers.
The cost of usage of a particular wireless access point 120 at a particular time may be determined using various types of information. For example, cost of usage of a particular wireless access point 120 at a particular time may be determined using one or more of network state information associated with wireless access points 120, network interaction information associated with interaction by wireless device 110 with wireless
access points 120, or the like, as well as various combinations thereof. It is noted that such information may be used directly to determine the cost of usage of a particular wireless access point 120 or indirectly to determine the cost of usage of a particular wireless access point 120 (e.g., where such information is used to determine information which is then used to compute the cost of usage of the wireless access point 120, such as portions of the information described above as being used as a basis for cost of usage of a wireless access point 120).
The wireless access points 120 may be grouped in the groups of wireless access points 120 such that, within each group of wireless access points 120, the costs of usage of the wireless access points 120 included in the group is similar. It is noted that each group of wireless access points 120 may include one or more wireless access points 120. In one embodiment, each wireless access point 120 may be considered individually (i.e., each group of wireless access points 120 includes only a single wireless access point 120). The wireless access points 120 may be groups into groups of wireless access points 120 in any other suitable manner.
The data transfers may be assigned to the one or more of the groups of wireless access points 120 by ordering the groups of wireless access points 120 relative to each other based on the costs of usage of the wireless access points 120 included in the groups of wireless access points 120 and assigning the data transfers to one or more of the groups of wireless access points 120 based on the ordering of the groups of wireless access points 120. The groups of wireless access points 120 may be ordered such that the group of wireless access points having the lowest relative cost of usage is the highest priority group of wireless access points 120 and the group of wireless access points having the highest relative cost of usage is the lowest priority group of wireless access points 120 (with each of any other group of wireless access points 120 being ordered accordingly in an order based on the relative cost of usage of the group of wireless access points 120).
The data transfers may be assigned to the one or more of the groups of wireless access points 120 in a manner for maximizing a number of data transfers assigned to wireless access points 120 in higher priority groups of wireless access points 120. In this manner, the total cost of supporting the data transfers for wireless device 110 may be reduced or even minimized.
The data transfers may be assigned to the one or more of the groups of wireless access points 120 in one or more phases by proceeding through the groups of wireless access points 120 based on the ordering of the groups of wireless access points 120. In a given phase, an attempt is made to assign any unassigned data transfers to wireless access points 120 of one or more groups of wireless access points 120 in a set of wireless access point groups considered during the given phase.
In a given phase, the unassigned data transfers include any data transfers not assigned to wireless access points 120 in any previous phase(s). In other words, in each phase the set of data transfers to be assigned using the wireless access point group(s) of the set of wireless access point groups of the phase may be different (e.g., as portions of the data transfers are assigned to ones of the wireless access points 120 in each phase, the set of remaining data transfers that still need to be assigned is reduced).
In a given phase, the set of wireless access point groups includes any previously selected group(s) of wireless access points 120 added to the set of wireless access point groups in any previous phase(s) as well as the group of wireless access points 120 selected for inclusion in the set of wireless access point groups during the given phase. For example, in a first phase the set of wireless access point groups includes a highest priority group of wireless access points 120, in a second phase the set of wireless access point groups includes the first and second highest priority groups of wireless access points 120, and so forth. In other words, in each phase, the set of wireless access point groups may be, updated to include a next group of wireless access points 120 (e.g., the next highest priority group of wireless access points 120). The wireless access points 120 included in the wireless access point group(s)
of the set of wireless access point groups may be referred to herein as a set of wireless access points 120.
The process may proceed through one or more such phases, using one or more of the groups of wireless access points 120, until all of the data transfers for the wireless device 110 have been assigned to associated ones of the wireless access points 120 (or until all groups of wireless access points 120 have been exhausted).
The data transfers to be assigned may be assigned to the wireless access points 120 of a given set of wireless access points 120 (i.e.., during a current phase of the process) in any suitable manner.
The data transfers to be assigned may be assigned to the wireless access points 120 of a given set of wireless access points 120 by assigning data transfers to ones of the wireless access points in an order based on the costs of usage of the wireless access points in the set of wireless access points 120, respectively.
The data transfers to be assigned may be assigned to the wireless access points 120 of a given set of wireless access points 120 (i.e., during a current phase of the process) by assigning data transfers to a given one of the wireless access points 120 during one or more time intervals in which the wireless access point 120 is expected to be available to the wireless device 110 and is expected to be satisfying a threshold level of congestion. The time interval(s) during which a wireless access point 120 is expected to be available to the wireless device 110 may be determined in any suitable manner (e.g., using information indicative of past interaction by the wireless device 110 with the wireless access points 120, information indicative of current interaction by the wireless device 110 with the wireless access points 120, or the like, as well as various combinations thereof). The time interval(s) during which a wireless access point 120 is expected to be satisfying a threshold level of congestion may be determined in any suitable manner (e.g., using past network state information, current network state information, or the like, as well as various combinations thereof). It is noted that the time
interval(s) of a wireless access point 120 during which data transfers may be assigned to the wireless access point 120 may be determined using any other suitable types of information (e.g., user preferences, operator preferences, or the like, as well as various combinations thereof).
The data transfers to be assigned may be assigned to the wireless access points 120 of a given set of wireless access points 120 (i.e., during a current phase of the process) by solving a matching problem defined based on the set of data transfers to be assigned and the wireless access points 120 included in the set of wireless access points 120. In one embodiment, the matching problem is a maximum matching problem. In one embodiment, the maximum matching problem defined for a given set of wireless access points 120 is defined based on a graph. In one embodiment, the graph is a geometric graph. In one embodiment, the geometric graph is a bipartite graph including a set of first nodes representing the data transfers to be assigned (e.g., representing data transfers directly, representing respective portions of data transfers, or the like) and a set of second nodes representing temporal availability on the wireless access points 120 in the set of wireless access points 120. The temporal availability of a wireless access point 120 may include any time intervals during which the wireless access point 120 is expected to be available to the wireless device 110 and expected to be satisfying a threshold level of congestion, portions of time intervals during which the wireless access point 120 is expected to be available to the wireless device 110 and expected to be satisfying a threshold level of congestion, or the like. The use of a geometric graph to solve a maximum matching problem for assigning a set of data transfers to a set of wireless access points 120 may be better understood by way of reference to FIGs. 3 and 4.
It is noted that, although primarily depicted and described with respect to an embodiment in which the groups of wireless access points 120 are considered serially during assignment of data transfers to wireless access points 120 (e.g., selected for inclusion in the set of wireless access point
groups serially), in one embodiment some or all of the groups of wireless access points 120 may be considered in a different manner during assignment of data transfers to wireless access points 120 (e.g., only a portion of a group of wireless access points 120 may be added to the set of wireless access point groups during a single phase, multiple groups of wireless access points 120 may be added to the set of wireless access point groups during a single phase, or the like, as well as various combinations thereof). The assignment of data transfers to wireless access points 120 in a set of wireless access points (i.e., in one or more groups of wireless access points 120 included in a set of wireless access point groups) may be better understood by way of reference to FIG. 2.
The data transfer scheduler 150 may be configured to send data transfer schedule information to one or more elements for use by the elements in performing the data transfers. For example, in the case of a data transfer to wireless device 110, data transfer scheduler 150 may inform a source of the data transfer of a time when the data transfer is to be initiated and which of the wireless access points 120 to use for the data transfer. For example, in the case of a data transfer from wireless device 110, data transfer scheduler 150 may inform wireless device 110 of a time when the data transfer is to be initiated and which of the wireless access points 120 to use for the data transfer. The data transfer scheduling information may be provided from data transfer scheduler 150 in any suitable manner (e.g., using any suitable numbers and/or types of messages, at any suitable times, or the like).
The data transfer scheduler 150 may be configured to dynamically modify an existing data transfer schedule or compute a new data transfer schedule in response to one or more conditions. The one or more conditions may result in changes to the cost of usage of one or more of the wireless access points 120 which may, in turn, result in changes to membership of one or more of the groups of wireless access points 120. The one or more conditions may include one or more of a determination that the existing data
transfer schedule is not feasible, a change in the state of the network (e.g., congestion status of one or more wireless access points, arrival/departure of wireless devices), a change in the state of the wireless device 110, addition of data transfers, changes in (which may include additions/removals of) data transfer deadlines, changes in (which may include additions/removals of) data transfer priorities, changes in operator preferences, changes in user preferences, or the like as well as various combinations thereof.
The data transfer scheduler 150 may be configured to provide various other functions in support of the data transfer scheduling capability.
The data transfer scheduler 150 may be implemented in any suitable manner. In one embodiment, the data transfer scheduler 150 may be implemented as a new management system(s) or as part of one or more existing management systems. In one embodiment, the data transfer scheduler 150 may be implemented as a server in a client server model where one or more clients of the wireless device 110 cooperate with the data transfer scheduler 150 to provide functions of the data transfer scheduling capability. The data transfer scheduler 150 may be implemented in any other suitable manner.
FIG. 2 depicts one embodiment of a method for scheduling data transfers for a wireless device using wireless access points. It is noted that, although primarily depicted and described as being performed serially, at least a portion of the steps of method 200 may be performed contemporaneously or in a different order than presented in FIG. 2.
At step 205, method 200 begins.
At step 210, costs of usage associated with the wireless access points are determined. The costs of usage for the wireless access points may be retrieved (e.g., locally or remotely) or computed in real time.
At step 215, the wireless access points are grouped into wireless access point groups based on the costs of usage of the wireless access points.
At step 220, the wireless access point groups are prioritized based on the costs of usage of the wireless access points of the wireless access point groups.
At step 225, a set of wireless access point groups is selected for performing assignment of data transfers to the wireless access point group. The selection of the set of wireless access point groups is based on the prioritization of the wireless access point groups (e.g., where wireless access point groups are selected for inclusion in the set of wireless access point groups in an order from highest priority toward lowest priority). In one embodiment, the set of wireless access point groups is selected by adding an additional wireless access point group to the set of wireless access point groups for each of the iterations of steps 225 - 250 of the method 200. For example, in a first iteration of steps 225 - 250 the set of wireless access point groups includes the highest priority wireless access point group, in a second iteration of steps 225 - 250 the set of wireless access point groups includes the first and second highest priority wireless access point groups, and so forth.
At step 230, a set of data transfers to be assigned to wireless access points of the wireless access point group(s) of the set of wireless access point groups is determined. It is noted that the set of data transfers to be assigned to wireless access points changes over time as data transfers are assigned to wireless access points (e.g., following each iteration of steps 225 - 250, the set of data transfers to be assigned to wireless access is expected to be smaller).
At step 235, at least a portion of the data transfers are assigned to ones of the wireless access points in the wireless access point group(s) of the set of wireless access point groups. The data transfers may be assigned to the wireless access points by solving a matching problem using a graph. The matching problem may be a maximum matching problem (i.e., matching may be a generalized matching of largest size). The graph may be a geometric graph and, optionally, one or more geometric graph partitioning techniques
may be used to manage complexity of computations associated with solving the matching problem (e.g., to localize matching computations) in the geometric graph. The graph may be generated by (1) for each data transfer, dividing the data transfer into a plurality of data transfer chunks where each data transfer chunk represents a piece of data which can be delivered without interruption, (2) for each wireless access point in the wireless access point group(s) of the set of wireless access point groups, determine each time interval during which the wireless access point is expected to be available to the wireless device and expected to be satisfying a threshold level of congestion and divide each of the time intervals into a plurality of timeslots (i.e., a timeslot on a wireless access point represents a portion of a time interval when the wireless access point is expected to be available to the wireless device and expected not to be overloaded such that one or more data transfer chunks may be delivered to the wireless device via the associated wireless access point. As described herein, solving a maximum matching problem in a geometric graph to determine assignment of data transfers to wireless access points may be better understood by way of reference to FIG. 3 and FIG. 4.
At step 240, a determination is made as to whether there are any remaining unassigned data transfers. If there are any remaining unassigned data transfers, method 200 proceeds to step 245. If there are no remaining unassigned data transfers, method 200 proceeds to step 255.
At step 245, a determination is made as to whether any wireless access point groups remain (i.e., whether there are any wireless access point groups that have not yet been added to the set of wireless access point groups for consideration during assignment of data transfers). If at least one wireless access point group remains for inclusion in the set of wireless access point groups, method 200 returns to step 225, at which point a next wireless access point group (e.g., a next highest priority wireless access point group, based on prioritization of the wireless access point groups) is selected for inclusion in the set of wireless access point groups that is used as a basis for
performing assignment of data transfers. If no wireless access point groups remain for inclusion in the set of wireless access point groups, method 200 proceeds to step 250.
At step 250, a determination is made that the data transfer schedule is not feasible. The data transfer schedule is deemed infeasible, because the execution of the method 200 did not result in assignment of all of the data transfers to wireless access points such that all of the data transfer can be completed. In one embodiment, one or more actions may be taken based on a determination that the data transfer schedule is infeasible. For example, the data transfer schedule may be used to perform, data transfers despite the fact that it was deemed to be infeasible (e.g., where the unassigned data transfers will be handled separately, where the unassigned data transfers each have data transfer priorities below a particular data transfer priority threshold, or the like). For example, all or part of the method 200 may be re-executed, with or without making one or more changes (e.g., to information used to determine usage costs of wireless access points, to previously determined usage costs of wireless access points, to definitions which control grouping of wireless access points into wireless access point groups, to the manner in which the wireless access point groups are considered, or the like), in order to compute a new data transfer schedule. For example, one or more adjustments (e.g., of one or more data transfers, one or more constraints, or the like) may be made in a manner for maximizing the number of data transfers accommodated while also accounting for any data transfer priorities of the data transfers (e.g., to accommodate the maximum number of high priority data transfers within the bounds of any other constraint(s)). It is noted that various other actions may be taken to adjust the existing data transfer schedule, compute a new data transfer schedule, accommodate the unassigned data transfers, or the like, as well as various combinations thereof. From step 250, method 200 proceeds to step 255.
At step 255, method 200 ends.
It is noted that, although primarily depicted and described with respect to an embodiment in which feasibility of a data transfer schedule depends on assignment of every data transfer to one of the wireless access points, in at least one embodiment feasibility of a data transfer schedule may be defined or determined in any other suitable manner. For example, a data transfer schedule may be considered to be feasible based on a determination that a threshold number of data transfers are assigned to wireless access points, a determination that each data transfer satisfying a data transfer priority threshold (e.g., all data transfers having data transfer priorities above the data transfer priority threshold) are assigned to wireless access points, or the like, as well as various combinations thereof.
FIG. 3 depicts an exemplary bipartite graph configured for use in determining assignment of data transfers to uncongested time intervals of wireless access points.
The bipartite graph 300 includes a set of first nodes 3101 - 310M (collectively, first nodes 310) representing uncongested timeslots of one or more wireless access points 120 and a set of second nodes 3201 - 320N (collectively, second nodes 320) representing data transfer chunks to be exchanged for wireless device 110 (e.g., chunks of data to be delivered to wireless device 110 or transmitted from wireless device 110 as part of the associated data transfer). The uncongested timeslots of the wireless access points 120 represented by the first nodes 310 may be weighted (e.g., using static weights or time-dependent weights) to represent the number of contemporaneous or simultaneous data transfers that may be assigned to the associated wireless access points 120. The data transfer chunks represented by the second nodes 320 may be data transfer chunks that are ready for transfer (e.g., available from the content source, due to be delivered in order to meet a delivery deadline, expected to be sent based on user preferences, or the like). The data transfer chunks may be included in the bipartite graph 300 (via addition of respective second nodes 320) when the data transfer chunks are unable to be assigned to any wireless access points 120 of any
higher priority groups of wireless access points 120 (i.e., unable to be assigned to wireless access points 120 during any previous phases for which processing has already been performed).
The bipartite graph 300 includes a plurality of edges 330 which connect first nodes 310 representing uncongested timeslots of wireless access points 120 and second nodes 320 representing data transfer chunks. In bipartite graph 300, the inclusion of an edge 330 between a first node 310 and a second node 320 indicates that the corresponding data transfer chunk can be delivered using the corresponding timeslot of the wireless access points 120. In other words, an edge 330 of bipartite graph 300 may represent that the wireless device 110 for which the associated data transfer is to be performed will be connected to the associated wireless access points 120 during the associated timeslot and that the associated timeslot will be uncongested at the time at which the wireless device 110 is connected. The edges 330 also may be used to model one or more constraints which may be considered during scheduling of data transfers for wireless device 110 (e.g., data transfer deadlines, operator preferences, user preferences, or the like).
The data transfer schedule may be determined by executing a process to solve a generalized matching problem on the bipartite graph 300 in which the goal is to "match" each second node 320 corresponding to a data transfer chunk to a first node 310 corresponding to an uncongested timeslot of a wireless access point 120 (i.e., to match data transfer chunks to timeslots during which the data transfer chunks may be delivered). It is noted that, at most, n data transfer chunks may be assigned to a given timeslot, where the value of n may vary across the timeslots. The process may be configured to solve the matching problem by exploiting the geometric property of the bipartite graph 300 (which may result in an efficient approximation even when the bipartite graph 300 includes a relatively large number of nodes) when performing the matching computation.
It is noted that, although primarily depicted and described herein with respect to embodiments in which assignment of data transfers to uncongested
time intervals of wireless access points is determined by using a specific type of geometric graph (namely, a bipartite graph), assignment of data transfers to uncongested time intervals of wireless access points may be determined by using any other suitable type of geometric graph. As noted herein, assignment of data transfers to uncongested time intervals of wireless access points may be determined by executing a process configured to perform a matching computation to solve a generalized matching problem on such a geometric graph. The matching computation can be computationally expensive (e.g., where the matching computation is performed for each new data transfer, where the underlying graph is large, or the like, as well as various combinations thereof). In one embodiment, one or more geometric graph partitioning techniques may be used to increase the speed of the matching computation and to localize the handling of updates when new data transfers are added). It may be observed that, for many users, the daily mobility of the user is generally restricted to a relatively small area that is centered around the current location of the user and, thus, that the data transfer jobs of the user are likely to be assigned to wireless access points which are in relatively close proximity to the user. An implication of this observation is that the graph that is used for determining assignment of data transfers to uncongested time intervals of wireless access points has a geometric property (most of the edges of the graph are relatively short). In such geometric graphs, a close to optimal match can be found by partitioning the geometric graph into a plurality of smaller partitions and independently solving the matching problem in each partition. In one embodiment, an additional matching may be performed to assign any leftover unassigned data transfers to any leftover timeslots. It is noted that there exists a way of geometrically partitioning the geographic graph such that the solution that is obtained by solving the generalized matching problem separately in each of the partitions is close to the optimal solution of solving the generalized matching problem in the entire geometric graph (e.g., a 1+£ approximation). In one embodiment, within a given partition the data transfers of a wireless
device are assigned only to wireless access points (in the same partition) that fall within the mobility range of the wireless device, and any data transfers not assigned in this manner then may be assigned via a full matching during which data transfers of the wireless device also may be assigned to one or more wireless access points in one or more other partitions). In one embodiment, any changes or updates may be handled by re-computing the matching problem in the partition or partitions to which the change or update is localized. In one embodiment, in which a change or update cannot be localized to any of the partitions, the matching may be fully re-computed. It is noted that performance bounds may be traded off with computation cost, where a larger partition results in better optimality guarantees, but at the cost of additional computation. An exemplary partitioning of a geometric graph for use in determining assignment of data transfers to timeslots of wireless access points is depicted and described with respect to FIG. 4.
FIG. 4 an exemplary partitioning of a geometric graph for use in determining assignment of data transfers of a wireless device to timeslots of wireless access points.
As depicted in FIG. 4, a geometric graph 410 including a plurality of data transfer chunks 4111 - 4116 (collectively, data transfer chunks 411) and a plurality of wireless access points 4121 - 41213 (collectively, wireless access points 412) is partitioned into a plurality of partitions 4201 - 4209 (collectively, partitions 420). The partitions 420 have respective partition sizes associated therewith. It is noted that the circles around the data transfer chunks 411 are intended to represent the mobility range of the wireless device.
In one embodiment, assignment of the data transfer chunks 411 to the wireless access points 412 includes: (1) within a partition 420, assigning the data transfer chunks 411 only to wireless access points 412 that fall within the mobility range of the wireless device, and (2) for any data transfer chunk 411 that is not assigned to one of the wireless access points 412 in this manner, assigning the data transfer chunk 411 via a full matching in which the data transfer chunk 411 may be assigned to one of the wireless access points 412
within its partition 420 or to one of the wireless access points 412 within a different one of the partitions 420.
In one embodiment, assignment of the data transfer chunks 411 to the wireless access points 412 includes (1) for each partition 420, assigning data transfer chunks 411 only to wireless access points 412 within the partition 420, and (2) for any data transfer chunk 411 that is not assigned to one of the wireless access points 412 using the partitions 420, assigning the remaining data transfer chunks 411 via a full matching in which all of the wireless access points 412 are available for assignment of the remaining data transfer chunks (i.e., all of the wireless access points 412 are considered together as a single partition 420).
In one embodiment, assignment of the data transfer chunks 411 to the wireless access points 412 includes performing one or more iterations of attempting to assign the data transfer chunks 411 to wireless access points 412 that fall within the partitions 420. In a current iteration, the partitions 420 have respective partition sizes associated therewith and an attempt is made to assign the data transfer chunks 411 to wireless access points 412 that fall within the partitions 420. If any of the data transfer chunks 411 remain unassigned after execution of the current iteration, the process proceeds to a next iteration in which the partition sizes of the partitions 420 are increased and a new attempt is made to assign any unassigned data transfer chunks 411 to wireless access points 412 that fall within the partitions 420. The process proceeds through iterations until all of the data transfer chunks 411 are assigned or until the partition size has increased to a point in which there is only a single partition 420 including all of the wireless access points 412. It is noted that use of partitioning to assign data transfer chunks 411 to the wireless access points 412 may be used in combination with the phases for considering wireless access point groups (e.g., the phases depicted and described with respect to FIG. 1 and FIG. 2) in various different ways. In one embodiment, within each phase for considering wireless access point groups, the partitioning of FIG. 4 may be used for assigning the data transfer chunks
411 to the wireless access points 412 considered during the phase (i.e., the partitioning techniques of FIG. 4 are repeated within each phase). In one embodiment, the phases for considering wireless access point groups are executed within each iteration of the partitioning techniques of FIG. 4 (e.g., within each iteration of the partitioning, the various phases for considering wireless access point groups are used in order to attempt to assign data transfer chunks 411 to the wireless access points 412, where the iterations may include growing of the partition sizes or use of full matching for assigning remaining data transfer chunks 411). It is noted that various combinations of such embodiments also may be supported during assignment of a given set of data transfers to a given set of wireless access points.lt is noted that, although FIG. 4 is depicted and described with respect to an embodiment including specific numbers, types, and arrangements of data transfer chunks 411, wireless access points 412, and partitions 420, a geometric graph may partitioned in various other ways (e.g., using various other numbers, types, or arrangements of data transfer chunks 411, wireless access points 412, and partitions 420).
FIG. 5 depicts one embodiment of a method for using a geometric graph to assign data transfers of a wireless device to timeslots of wireless access points. It is noted that, although primarily depicted and described as being performed serially, at least a portion of the steps of method 500 may be performed contemporaneously or in a different order than presented in FIG. 5.
At step 510, method 500 begins.
At step 520, the original graph (i.e., the geometric graph) is partitioned into a plurality of partitions, where each partition includes zero or more wireless access points and has a partition size associated therewith.
At step 530, for each partition, data transfer chunks are assigned to one or more wireless access points in the partition.
At step 540, a determination is made as to whether any unassigned data transfer chunks remain. If no unassigned data transfer chunks remain (i.e., all of the data transfers to be assigned have been assigned to the
wireless access points), method 500 proceeds to step 570, where method 500 ends. If any unassigned data transfer chunks remain, method 500 proceeds to step 550.
At step 550, a determination is made as to whether the original graph has been reached. It is noted that as method 500 iterates through steps 530 - 560, the partition sizes of the partitions are increased such that, eventually, the original graph (i.e., a single partition) will be reached. If the original graph has been reached, method 500 proceeds to step 570, where method 500 ends. If the original graph has not been reached, method 500 proceeds to step 560 (i.e., the partition sizes may be further increased and at least one additional iteration may be executed in order to try to assign all of the data transfer chunks to the wireless access points).
At step 560, the original graph is repartitioned using increased partition sizes (i.e., an increase over the partitions sizes used in the previous iteration). It is noted that this may result in a decrease in the number of partitions until, eventually, the original graph (i.e., a single partition) will be reached. From step 560, method 500 returns to step 530, at which point another attempt is made to assign the remaining unassigned data transfer chunks to wireless access points.
At step 570, as noted above, method 500 ends.
As described hereinabove with respect to FIG. 4, the use of phases to consider sets of wireless access point groups and the use of iterations of increasing partition size may be combined in a number of ways. It is noted that, in such embodiments, steps from method 200 and method 500 may be combined. For example, steps from method 500 may be inserted into method 200 such that the use of iterations of increasing partition size may be used within one or more of the phases (i.e., during which a set of wireless access points is considered) of method 200. For example, steps from method 200 may be inserted into method 500 such that the use of phases to consider sets of wireless access point groups may be used within one or more of the iterations (i.e., of increasing partition size) of method 500. It will be
appreciated that steps from method 200 and method 500 may be combined in other ways.
It is noted that, although primarily depicted and described herein with respect to embodiments in which the wireless access points 120 are uncongested (or expected to be uncongested) at the time of data transfers, in at least some embodiments the wireless access points 120 may simply satisfy a threshold level of congestion at the time of data transfers. It is noted that the threshold level of congestion may be defined in any suitable manner (e.g., equal to or less than 80% load on the wireless access point, equal to or less than 60% load on the wireless access point, per user throughput greater than certain value, or the like, as well as various combinations thereof. It is noted that the threshold level of congestion may be defined differently (e.g., using different measures for congestion, using different values of similar measures for congestion, or the like) for different ones of the wireless access points 120. In other words, the condition of a wireless access point 120 being uncongested may be defined in any suitable manner (which may include at least some level of loading).
It is noted that, although primarily depicted and described with respect to embodiments of the data transfer scheduling capability in which a time interval of a wireless access point is considered for use in performing a data transfer if the wireless access point is expected to be available to the wireless device and is expected to satisfy a threshold level of congestion, in at least some embodiments a time interval of a wireless access point may be considered for use in performing a data transfer if the wireless access point is expected to be available to the wireless device (e.g., in the case of private wireless access points not available to other wireless devices (e.g., private WiFi access points) or other types of access points which are not expected to be congested).
It is noted that, although primarily depicted and described with respect to embodiments of the data transfer scheduling capability in which assignment of data transfers to wireless access points is performed by solving a maximum
matching problem for each group of wireless access points, in at least some embodiments other types of matching may be used for one of more of the groups of wireless access points in order to assign data transfers to wireless access points in the one or more groups of wireless access points. For example, one or more simpler scheduling mechanisms may be employed for one of more of the groups of wireless access points.
It is noted that, although primarily depicted and described with respect to use of embodiments of the data transfer scheduling capability to schedule data transfers for a single wireless device, embodiments of the data transfer scheduling capability may be used to schedule data transfers for multiple wireless devices as a group. In at least some such embodiments, the data transfer scheduling may be based on one or more additional constraints (e.g., comparisons of data transfer deadlines across wireless devices, comparisons of data transfer priorities across wireless devices, comparisons of subscription levels associated with the wireless devices, or the like, as well as various combinations thereof).
It is noted that, although primarily depicted and described with respect to embodiments of the data transfer scheduling capability in which only wireless access points are considered and analyzed during scheduling of data transfers, in at least some embodiments one or more wired access points may be considered and analyzed during scheduling of data transfers.
In at least some embodiments, the data transfer scheduling capability is configured to augment the capacity of the mobile network using unused capacity of the mobile network and alternative access networks (e.g., WiFi, femtocell, or the like). Utilization of such additional capacity may result in a five-fold (or more) increase in available capacity with no additional capital expenditure costs. Leveraging of such additional capacity for delivering multimedia content to the end user can result in substantial revenues for the network operator, service provider, and content provider while providing the end user with access to large multimedia files at discounted prices. The data transfer scheduling capability may tap into surplus capacity and enables the
amount of content delivered using such surplus capacity to be maximized. The data transfer scheduling capability may ensure that delivery of content happens in a timely manner and under the constraints and preferences set up by the operator and end user. The data transfer scheduling capability may check for the feasibility of finding a schedule for delivering content and, thus, also can be used for applying admission control to user requests for content delivery. The data transfer scheduling capability may dynamically adjust the data transfer schedule to handle changes in one or more of network state, user state, or content state. The data transfer scheduling capability may be implemented in a scalable and practical manner without requiring excessive computational or storage resources. The data transfer scheduling capability may provide various other types of benefits to one or more network operators, content providers, or end users.
In at least some embodiments, the data transfer scheduling capability is configured to optimize content delivery using spare capacity in mobile networks and spare capacity in alternate access networks (e.g., WiFi networks, femtocell networks, or the like). In at least some embodiments, the data transfer scheduling capability is configured to maximize the amount of content delivered while accounting for various user, network operator, or service provider constraints on the delivery process.
In at least some embodiments, the data transfer scheduling capability is configured to determine if the given set of content can be delivered using the estimated available capacity without violating any constraints. In one embodiment, when such a delivery is not possible, the data transfer scheduling capability is configured may be configured to identify a subset of the content that can be delivered. In one embodiment, the data transfer scheduling capability is configured to perform admission control of requests by users for content delivery.
FIG. 6 depicts a high-level block diagram of a computer suitable for use in performing functions described herein.
The computer 600 includes a processor 602 (e.g., a central processing unit (CPU) and/or other suitable processor(s)) and a memory 604 (e.g., random access memory (RAM), read only memory (ROM), and the like).
The computer 600 also may include a cooperating module/process 605. The cooperating process 605 can be loaded into memory 604 and executed by the processor 602 to implement functions as discussed herein and, thus, cooperating process 605 (including associated data structures) can be stored on a computer readable storage medium, e.g., RAM memory, magnetic or optical drive or diskette, and the like.
The computer 600 also may include one or more input/output devices 606 (e.g., a user input device (such as a keyboard, a keypad, a mouse, and the like), a user output device (such as a display, a speaker, and the like), an input port, an output port, a receiver, a transmitter, one or more storage devices (e.g., a tape drive, a floppy drive, a hard disk drive, a compact disk drive, and the like), or the like, as well as various combinations thereof).
It will be appreciated that computer 600 depicted in FIG. 6 provides a general architecture and functionality suitable for implementing functional elements described herein and/or portions of functional elements described herein. For example, the computer 600 provides a general architecture and functionality suitable for implementing one or more of a portion of wireless device 110, wireless device 110, a portion of a wireless access point 120, a wireless access point 120, a portion of a data node 140, a data node 140, a portion of data transfer scheduler 150, data transfer scheduler 150, or the like.
It will be appreciated that the functions depicted and described herein may be implemented in software (e.g., via implementation of software on one or more processors, for executing on a general purpose computer (e.g., via execution by one or more processors) so as to implement a special purpose computer, and the like) and/or may be implemented in hardware (e.g., using a general purpose computer, one or more application specific integrated circuits (ASIC), and/or any other hardware equivalents).
It is contemplated that some of the steps discussed herein as software methods may be implemented within hardware, for example, as circuitry that cooperates with the processor to perform various method steps. Portions of the functions/elements described herein may be implemented as a computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer such that the methods and/or techniques described herein are invoked or otherwise provided. Instructions for invoking the inventive methods may be stored in fixed or removable media, transmitted via a data stream in a broadcast or other signal bearing medium, and/or stored within a memory within a computing device operating according to the instructions.
It is noted that the term "or" as used herein refers to a non-exclusive "or," unless otherwise indicated (e.g., "or else" or "or in the alternative").
It is noted that, although various embodiments which incorporate the teachings of the present invention have been shown and described in detail herein, those skilled in the art can readily devise many other varied embodiments that still incorporate these teachings.

I/We claim:
1. An apparatus for scheduling a plurality of data transfers for a wireless
device, comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
group a plurality of wireless access points into a plurality of wireless access point groups based on a plurality of costs of usage of the respective wireless access points;
prioritize the wireless access point groups based on the costs of usage of the respective wireless access points; and
determine assignment of the data transfers of the wireless device to ones of the wireless access points based on the prioritization of the wireless access point groups.
2. The apparatus of claim 1, wherein, for at least one of the wireless access points, the cost of usage of the wireless access point is based on at least one of a monetary amount paid for access to and use of the wireless access point or a network associated with the wireless access point, an amount of congestion associated with the wireless access point or a network associated with the wireless access point, an energy cost per bit for the wireless access point, one or more operational costs assigned to the wireless access point by a service provider, one or more temporal conditions, or an indication as to whether or not the wireless access point is managed by the service provider.
3. The apparatus of claim 1, wherein, to determine assignment of the data transfers to ones of the wireless access points based on the prioritization of the wireless access point groups, the processor is configured to:
select a first one of the wireless access point groups based on the prioritization of the wireless access point groups; and
assign at least a portion of the data transfers to one or more wireless access points of the first one of the wireless access point groups.
4. The apparatus of claim 3, wherein the first one of the wireless access
point groups has a first priority level associated therewith, wherein the
processor is configured to:
select a second one of the wireless access point groups based on the prioritization of the wireless access point groups, wherein the second one of the wireless access point groups has a second priority level associated therewith, wherein the first priority level is greater than the second priority level; and
assign at least a portion of the data transfers to one or more wireless access points of at least one of the first one of the wireless access point groups or the second one of the wireless access point groups.
5. The apparatus of claim 4, wherein the second one of the wireless access point groups is selected based on a determination that at least one of the data transfers remains unassigned after assignment of at least a portion of the data transfers to one or more wireless access points of the first one of the wireless access point groups.
6. The apparatus of claim 1, wherein, to determine assignment of the data transfers to ones of the wireless access points based on the prioritization of the wireless access point groups, the processor is configured to:
determine a set of wireless access point groups comprising two or more of the wireless access point groups; and
assign at least a portion of the data transfers to one or more wireless access points of the two or more wireless access point groups of the set of wireless access point groups.
7. The apparatus of claim 1, wherein the processor is configured to determine assignment of the data transfers to ones of the wireless access based on one or more of a data transfer priority associated with one of the data transfers, a data transfer deadline associated with one of the data transfers, a preference of a user of the wireless device, or a preference of a service provider or network operator.
8. The apparatus of claim 1, wherein the processor is configured to determine assignment of the data transfers to ones of the wireless access points based on the prioritization of the wireless access point groups by:
generating a graph for one of the wireless access point groups; and solving a matching problem using the graph generated for the one of the wireless access point groups.
9. The apparatus of claim 8, wherein the processor is configured to
generate the graph by:
dividing one of the data transfers into a plurality of data transfer chunks; and
generating a plurality of nodes representing the respective data transfer chunks.
10. The apparatus of claim 8, wherein the processor is configured to
generate the graph by:
determining a time interval when one of the wireless access points in the wireless access point group is expected to be satisfying a threshold level of congestion;
dividing the time interval into a plurality of timeslots; and generating a plurality of nodes representing the respective timeslots of the one of the wireless access points.
11. The apparatus of claim 8, wherein the processor is configured to
generate the graph by:
generating a plurality of first nodes associated with ones of the data transfers; and
generating a plurality of second nodes associated with the wireless access points in the one of the wireless access point groups.
12. The apparatus of claim 8, wherein the processor is configured to
generate the graph by:
generating a plurality of first nodes representing respective data transfer chunks of one of more of the data transfers; and
generating a plurality of second nodes representing respective timeslots during which one of the wireless access points in the one of the wireless access point groups is expected to be satisfying a threshold level of congestion.
13. The apparatus of claim 12, wherein at least one of the second nodes comprises a weight indicative of a number of data transfer chunks capable of being assigned to the associated one of the wireless access points during the associated timeslot.
14. The apparatus of claim 12, wherein the graph includes an edge from one of the first nodes to one of second nodes based on a determination that the data chunk associated with the one of the first nodes is capable of being assigned to the timeslot of the one of the second nodes.
15. The apparatus of claim 12, wherein the graph includes a plurality of edges between ones of the first nodes and ones of the second nodes, wherein at least one of the edges is configured to represent at least one of a data delivery deadline, a preference of a user of the wireless device, or a preference of a network operator.
16. The apparatus of claim 1, wherein the processor is configured to
determine assignment of the data transfers to ones of the wireless access
points based on the prioritization of the wireless access point groups by:
generating a geometric graph for one of the wireless access point
groups;
partitioning the geometric graph into a plurality of graph partitions; and solving a plurality of matching problems in the respective plurality of
graph partitions.
17. The apparatus of claim 1, wherein the processor is configured to
determine assignment of the data transfers to ones of the wireless access
points based on the prioritization of the wireless access point groups by:
partitioning a geometric graph into a plurality of graph partitions; and within each of the graph partitions, assigning a portion of the data transfers to wireless access points within the graph partition.
18. The apparatus of claim 17, wherein the graph partitions have
respective graph partition sizes associated therewith, wherein the processor is
configured to assign any remaining data transfers to wireless access points
by:
re-partitioning the graph while increasing the partition sizes of the graph partitions; and
assigning at least a portion of the remaining data transfers to the wireless access points within the graph partitions.
19. A computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method for scheduling a plurality of data transfers for a wireless device, the method comprising:
grouping a plurality of wireless access points into a plurality of wireless access point groups based on a plurality of costs of usage of the respective wireless access points;
prioritizing the wireless access point groups based on the costs of usage of the respective wireless access points; and
determining assignment of the data transfers of the wireless device to ones of the wireless access points based on the prioritization of the wireless access point groups.
20. A method for scheduling a plurality of data transfers for a wireless device, comprising:
grouping a plurality of wireless access points into a plurality of wireless access point groups based on a plurality of costs of usage of the respective wireless access points;
prioritizing the wireless access point groups based on the costs of usage of the respective wireless access points; and
determining assignment of the data transfers of the wireless device to ones of the wireless access points based on the prioritization of the wireless access point groups.