SYSTEMS AND METHODS FOR RESOURCE ALLOCATION SERVING COMMUNICATION REQUIREMENTS AND FAIRNESS

• US 20130182565A1
• Filed: 03/06/2013
• Published: 07/18/2013
• Est. Priority Date: 07/15/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: HUANG, Xiaolong, Das, Soumya
• Granted Patent: US 8,929,388 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04W 72/02 Selection of wireless resources by user or terminal
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02

Abstract

An allocation technique is operable to allocate communication resources in multi-hop networks under the joint consideration of communication requirements and fairness. Embodiments operate to provide allocation of time slot resources in TDMA based multi-hop wireless networks under the joint consideration of QoS and fairness. Embodiments operate with respect to information regarding maximal common slot set flow contention. An iterative process is applied with respect to the information regarding maximal common slot set flow contention to allocate communication resources providing a balance between meeting communication requirements and fairness. According to embodiments, an inter-graph process iteratively selects a maximal common slot set for which resource allocation with respect to various flows is to be performed and an intra-graph process assigns communication resources in the maximal common slot set providing a balancing between meeting communication requirements (e.g., QoS) and providing fairness. Other aspects, embodiments, and features are also claim and described.

Claims

1. A method comprising:

if a node is at least one of a source node and a destination node of a new network data flow, sending by the node information regarding the new data flow and information regarding contending data flows to neighboring nodes, the information regarding the new data flow including an available resource set for the new data flow; and

determining maximal common resource set based flow contention information for the new network data flows using the information regarding the new data flow and the information regarding contending data flows.

2. The method of claim 1, wherein the maximal common resource set based flow contention information comprises a maximal common slot set based flow contention graph (MCSS-FCG), wherein the MCSS-FCG comprises a flow contention graph with respect to a maximal common slot set which is available to all data flows in the MCSS-FCG.

3. The method of claim 1, further comprising decomposing the MCSS-FCG into maximal cliques of data flows.

4. The method of claim 1, wherein the network comprises a TDMA based communication network and the available resource set comprises TDMA time slots.

5. The method of claim 1, further comprising:

defining a structure for the TDMA network, the structure having a maximal common time slot set and its associated MCSS-FCG; and

decomposing all available time slots into several maximal common time slot sets, each being associated with a MCSS-FCG.

6. The method of claim 1, further comprising:

receiving the information regarding the data flow by a neighboring node; and

if the receiving neighboring node is a primary node and is a source node or a destination node of the data flow, notifying the sending node by the receiving neighboring node that the data flow belongs to the receiving neighboring node.

7. The method of claim 1, further comprising:

receiving the information regarding the contending data flows by a neighboring node; and

if the receiving neighboring node is at least one of a source node and a destination node of the data flow, notifying the sending node by the receiving neighboring node the flows that contend the data flows of the receiving neighboring node.

8. A communication device comprising a processor that is configured to implement the method of claim 1.