METHOD AND APPARATUS FOR RADIO FILTERING IN A MULTI-RADIO DEVICE

• US 20100329162A1
• Filed: 01/07/2010
• Published: 12/30/2010
• Est. Priority Date: 06/29/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Kadous, Tamer A., Mantravadi, Ashok
• Granted Patent: US 8,351,456 B2
• Time in Patent Office: Days
• US Class Current: 370/310
• CPC Class Codes: H04W 72/1215 for collaboration of different radio technologies
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals

Abstract

Systems and methodologies are described herein that facilitate filtering or clustering of radios and/or other transceivers associated with a communication environment. As described herein, potentially conflicting transceivers supported by a communications device can be managed in an expedited fashion by filtering the transceivers into respective groups or clusters of transceivers that exhibit potential collisions. For example, clusters can be generated such that respective transceivers are associated with a single cluster and respective transceivers associated with a given cluster do not exhibit potential collisions with transceivers not associated with the given cluster. Clustering can be performed graphically as further described herein by generating and analyzing a graph that includes nodes corresponding to respective transceivers and edges representing potential conflicts therebetween. Additionally, resolution tables can be generated using substantially all combinations of conflicting transceivers within a set of transceivers, as determined based on an initial clustering and/or in any other suitable manner.

Claims

1. A method, comprising:

identifying a set of transceivers to be resolved at a given time interval;

obtaining information relating to potential pairwise collisions between respective transceivers in the set of transceivers; and

dividing the set of transceivers into respective non-overlapping clusters of one or more transceivers such that respective transceivers in the set of transceivers are associated with a single cluster and respective transceivers associated with a given cluster do not exhibit potential pairwise collisions with transceivers not associated with the given cluster.

2. The method of claim 1, wherein the identifying comprises:

receiving information relating to a set of events to be executed; and

identifying events relevant to selection of one or more events in a given decision unit (DU) in time based on the information relating to the set of events.

3. The method of claim 2, wherein the information relating to the set of events comprises one or more of a notification relating to an event to be executed in the given DU, information relating to an ongoing event that executes through the given DU, or a notification relating to an event to be executed in a subsequent DU in time that potentially overlaps in execution with an ongoing event or an event to be executed in the given DU.

4. The method of claim 1, wherein the dividing comprises:

generating a graph at least in part by constructing nodes corresponding to respective transceivers in the set of transceivers and constructing edges between respective nodes corresponding to potential pairwise collisions between the respective transceivers corresponding to the nodes; and

generating respective clusters at least in part by determining one or more maximal connected subgraphs of the graph.

5. The method of claim 4, wherein:

the generating a graph comprises constructing nodes corresponding to one or more of transmit components or receive components of respective transceivers; and

the dividing comprises dividing the set of transceivers into respective non-overlapping resolution clusters of one or more transceivers.

6. The method of claim 4, wherein:

the generating a graph comprises constructing nodes corresponding to transmit or receive components of respective transceivers in operation or respective transceivers operating in a sleep mode; and

the dividing comprises dividing the set of transceivers into respective non-overlapping sleep clusters of one or more transceivers.

7. The method of claim 4, wherein the generating a graph comprises:

constructing a composite node corresponding to a plurality of aggressor transceivers that can jointly collide with a victim transceiver; and

constructing edges connecting the composite node to respective nodes that correspond to constituent transceivers of the plurality of aggressor transceivers.

8. The method of claim 4, wherein the generating respective clusters comprises:

initializing a primary transceiver set and a secondary transceiver set such that the primary transceiver set initially contains substantially no transceivers and the secondary transceiver set initially contains substantially all transceivers represented in the graph;

selecting a node in the graph corresponding to a transceiver in the secondary transceiver set;

identifying respective nodes that are connected to the selected node in the graph;

moving respective transceivers corresponding to the selected node and respective nodes connected to the selected node from the secondary transceiver set to the primary transceiver set;

iterating the selecting a node, the identifying respective nodes, and the moving with respect to respective additional nodes corresponding to transceivers or combinations of transceivers in the primary transceiver set until substantially no further nodes are identified; and

generating a cluster based on respective transceivers in the primary transceiver set upon completion of the iterating.

9. The method of claim 8, wherein the generating respective clusters further comprises:

emptying the primary transceiver set upon completion of the generating a cluster; and

performing the selecting a node, the identifying respective nodes, the moving, the iterating, and the generating a cluster in an iterative manner until substantially all transceivers are removed from the secondary transceiver set.

10. The method of claim 1, further comprising building one or more resolution tables based at least in part on respective clusters generated from the set of transceivers.

11. The method of claim 10, wherein the building comprises:

obtaining information relating to respective subsets of potentially conflicting transceivers in the set of transceivers; and

generating resolution tables corresponding to one or more subsets of potentially conflicting transceivers for which information is obtained.

12. The method of claim 11, wherein:

the obtaining information comprises generating a graph at least in part by constructing nodes corresponding to transmit or receive components of respective transceivers in the set of transceivers and constructing edges between respective nodes corresponding to potential pairwise collisions between the components of the respective transceivers corresponding to the nodes and finding respective connected subgraphs in the graph; and

the generating resolution tables comprises creating resolution tables for the respective connected subgraphs.

13. The method of claim 12, wherein:

the finding respective connected subgraphs comprises;

identifying second order collisions between respective transceivers in the set of transceivers at least in part by identifying respective pairs of nodes in the graph that are connected by edges;

determining whether additional nodes in the graph corresponding to respective transceivers are connected via edges to one or more previously identified collisions between respective transceivers represented in the graph;

identifying respective collisions represented by the graph corresponding to respective subgraphs in the graph that include a previously identified collision and an additional connected node; and

repeating the determining and the identifying respective collisions in an iterative manner until further iteration yields identification of substantially no new collisions between transceivers identified in the graph; and

the generating resolution tables further comprises generating resolution tables based on respective collisions identified from the graph.

14. The method of claim 1, wherein the set of transceivers comprises at least one radio.

15. A wireless communications apparatus, comprising:

a memory that stores data relating to a set of transceivers to be resolved at a given time interval; and

a processor configured to obtain information relating to potential pairwise collisions between respective transceivers in the set of transceivers and to divide the set of transceivers into respective non-overlapping clusters of one or more transceivers such that respective transceivers in the set of transceivers are associated with a single cluster and respective transceivers associated with a given cluster do not exhibit potential pairwise collisions with transceivers not associated with the given cluster.

16. The wireless communications apparatus of claim 15, wherein:

the memory further stores data relating to a set of events to be executed; and

the processor is further configured to identify the set of transceivers to be resolved at a given time interval at least in part by identifying events relevant to selection of one or more events in a given decision unit (DU) in time based on the information relating to the set of events.

17. The wireless communications apparatus of claim 16, wherein the data relating to the set of events to be executed comprises one or more of a notification relating to an event to be executed in the given DU, information relating to an ongoing event that executes through the given DU, or a notification relating to an event to be executed in a subsequent DU in time that potentially overlaps in execution with an ongoing event or an event to be executed in the given DU.

18. The wireless communications apparatus of claim 15, wherein the processor is further configured to generate a graph at least in part by constructing nodes corresponding to respective transceivers in the set of transceivers and constructing edges between respective nodes corresponding to potential pairwise collisions between the respective transceivers corresponding to the nodes and to generate respective clusters at least in part by determining one or more maximal connected subgraphs of the graph.

19. The wireless communications apparatus of claim 18, wherein the processor is further configured to construct nodes in the graph corresponding to one or more of transmit components or receive components of respective transceivers and to divide the set of transceivers into respective non-overlapping resolution clusters of one or more transceivers.

20. The wireless communications apparatus of claim 18, wherein the processor is further configured to construct nodes in the graph corresponding to transmit or receive components of respective transceivers in operation or respective transceivers operating in a sleep mode and to divide the set of transceivers into respective non-overlapping sleep clusters of one or more transceivers.

21. The wireless communications apparatus of claim 18, wherein the processor is further configured to construct a composite node in the graph corresponding to a plurality of aggressor transceivers that can jointly conflict with a victim transceiver and to construct edges in the graph connecting the composite node to respective nodes that correspond to constituent transceivers of the plurality of aggressor transceivers.

22. The wireless communications apparatus of claim 18, wherein the processor is further configured to generate respective clusters at least in part by initializing a primary transceiver set and a secondary transceiver set such that the primary transceiver set initially contains substantially no transceivers and the secondary transceiver set initially contains substantially all transceivers represented in the graph;

selecting a node in the graph corresponding to a transceiver in the secondary transceiver set;

identifying respective nodes that are connected to the selected node in the graph;

moving respective transceivers corresponding to the selected node and respective nodes connected to the selected node from the secondary transceiver set to the primary transceiver set;

iterating the selecting a node, the identifying respective nodes, and the moving with respect to respective additional nodes corresponding to transceivers or combinations of transceivers in the primary transceiver set until substantially no further nodes are identified; and

generating a cluster based on respective transceivers in the primary transceiver set upon completion of the iterating.

23. The wireless communications apparatus of claim 22, wherein the processor is further configured to empty the primary transceiver set upon completion of the generating a cluster and to iteratively select respective nodes, identify nodes connected to the respective nodes, move transceivers between the primary transceiver set and the secondary transceiver set, and generate respective clusters until substantially all transceivers are removed from the secondary transceiver set.

24. The wireless communications apparatus of claim 15, wherein the processor is further configured to build one or more resolution tables based at least in part on respective clusters generated from the set of transceivers.

25. The wireless communications apparatus of claim 24, wherein the processor is further configured to obtain information relating to respective subsets of potentially conflicting transceivers in the set of transceivers and to generate resolution tables corresponding to one or more subsets of potentially conflicting transceivers for which information is obtained.

26. The wireless communications apparatus of claim 25, wherein the processor is further configured to generate a graph at least in part by constructing nodes corresponding to transmit or receive components of respective transceivers in the set of transceivers and constructing edges between respective nodes corresponding to potential pairwise collisions between the components of the respective transceivers corresponding to the nodes, to find respective connected subgraphs in the graph, and to create resolution tables for the respective connected subgraphs.

27. The wireless communications apparatus of claim 25, wherein the processor is further configured to find respective subgraphs in the graph at least in part by identifying second order collisions between respective transceivers in the set of transceivers at least in part by identifying respective pairs of nodes in the graph that are connected by edges, determining whether additional nodes in the graph corresponding to respective transceivers are connected via edges to one or more previously identified collisions between respective transceivers represented in the graph, identifying respective collisions represented by the graph corresponding to respective subgraphs in the graph that include a previously identified collision and an additional connected node, and repeating the determining and the identifying respective collisions in an iterative manner until further iteration yields identification of substantially no new collisions between transceivers identified in the graph.

28. The wireless communications apparatus of claim 15, wherein the set of transceivers comprises at least one radio.

29. An apparatus, comprising:

means for obtaining information relating to respective associated transceivers and potential pairwise conflicts between the respective associated transceivers; and

means for filtering the respective associated transceivers into one or more clusters such that respective transceivers are associated with only a single cluster and respective transceivers have potential pairwise collisions only with transceivers in a common cluster.

30. The apparatus of claim 29, wherein the means for obtaining information comprises:

means for obtaining information relating to a set of events to be executed; and

means for identifying events relevant to selection of one or more events in a given decision unit (DU) in time based on the information relating to the set of events to be executed.

31. The apparatus of claim 30, wherein the information relating to the set of events to be executed comprises one or more of a notification relating to an event to be executed in the given DU, information relating to an ongoing event that executes through the given DU, or a notification relating to an event to be executed in a subsequent DU in time that potentially overlaps in execution with an ongoing event or an event to be executed in the given DU.

32. The apparatus of claim 29, wherein the means for filtering comprises:

means for constructing a graph at least in part by generating nodes corresponding to respective associated transceivers and generating edges between respective nodes corresponding to potential pairwise collisions between the respective associated transceivers corresponding to the nodes; and

means for filtering the respective associated transceivers into respective clusters at least in part by determining one or more maximal connected subgraphs of the graph.

33. The apparatus of claim 32, wherein:

the means for constructing a graph comprises means for generating nodes corresponding to one or more of transmit components or receive components of respective associated transceivers; and

the means for filtering comprises means for filtering the respective associated transceivers into respective non-overlapping resolution clusters of one or more transceivers.

34. The apparatus of claim 32, wherein:

the means for constructing a graph comprises means for generating nodes corresponding to transmit or receive components of respective associated transceivers in operation or respective associated transceivers operating in a sleep mode; and

the means for filtering comprises means for filtering the respective associated transceivers into respective non-overlapping sleep clusters of one or more transceivers.

35. The apparatus of claim 32, wherein the means for constructing a graph comprises:

means for generating a composite node corresponding to a plurality of associated aggressor transceivers that can jointly collide with an associated victim transceiver; and

means for generating edges connecting the composite node to respective nodes that correspond to constituent transceivers of the plurality of associated aggressor transceivers.

36. The apparatus of claim 32, wherein the means for filtering further comprises:

means for initializing a primary transceiver set and a secondary transceiver set such that the primary transceiver set initially contains substantially no transceivers and the secondary transceiver set initially contains substantially all associated transceivers represented in the graph;

means for selecting a node in the graph corresponding to a transceiver in the secondary transceiver set;

means for identifying respective nodes that are connected to the selected node in the graph;

means for moving respective associated transceivers corresponding to the selected node and respective nodes connected to the selected node from the secondary transceiver set to the primary transceiver set;

means for iterating the selecting a node, the identifying respective nodes, and the moving with respect to respective additional nodes corresponding to associated transceivers or combinations of transceivers in the primary transceiver set until substantially no further nodes are identified; and

means for generating a cluster based on respective associated transceivers in the primary transceiver set upon completion of the means for iterating.

37. The apparatus of claim 36, wherein the means for filtering further comprises:

means for emptying the primary transceiver set upon execution of the means for generating a cluster; and

means for repeating the selecting a node, the identifying respective nodes, the moving, the iterating, and the generating a cluster in an iterative manner until substantially all associated transceivers are removed from the secondary transceiver set.

38. The apparatus of claim 29, further comprising means for building one or more resolution tables based at least in part on respective clusters into which the respective associated transceivers are filtered.

39. The apparatus of claim 38, wherein the means for building comprises:

means for obtaining information relating to respective subsets of potentially conflicting associated transceivers; and

means for generating resolution tables corresponding to one or more subsets of potentially conflicting associated transceivers for which information is obtained.

40. The apparatus of claim 39, wherein:

the means for obtaining information comprises means for constructing a graph at least in part by generating nodes corresponding to transmit or receive components of respective associated transceivers and generating edges between respective nodes corresponding to potential pairwise collisions between the components of the respective associated transceivers corresponding to the nodes and means for finding respective connected subgraphs in the graph; and

the means for generating resolution tables comprises means for creating resolution tables according to the respective connected subgraphs.

41. The apparatus of claim 40, wherein:

the means for obtaining information further comprises;

means for identifying second order collisions between respective associated transceivers at least in part by identifying respective pairs of nodes in the graph that are connected by edges;

means for determining whether additional nodes in the graph corresponding to respective associated transceivers are connected via edges to one or more previously identified collisions between respective associated transceivers represented in the graph;

means for identifying respective collisions represented by the graph that correspond to respective subgraphs in the graph comprising a previously identified collision and an additional connected node; and

means for repeating the determining and the identifying respective collisions in an iterative manner until further iteration yields identification of substantially no new collisions between transceivers identified in the graph; and

the means for generating resolution tables further comprises means for generating resolution tables based on respective collisions identified from the graph.

42. The apparatus of claim 29, wherein the set of transceivers comprises at least one radio.

43. A computer program product, comprising:

a computer-readable medium, comprising;

code for causing a computer to obtaining information relating to respective associated radios and potential pairwise conflicts between the respective associated radios; and

code for causing a computer to filter the associated radios into one or more clusters such that respective radios are associated with only a single cluster and respective radios have potential pairwise collisions only with radios in a common cluster.