Method and apparatus for radio filtering in a multi-radio device

• US 8,351,456 B2
• Filed: 01/07/2010
• Issued: 01/08/2013
• Est. Priority Date: 06/29/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Kadous, Tamer A., Mantravadi, Ashok
• Primary Examiner(s): Nguyen, Hahn
• Application Number:
  US12/683,879
• Publication Number:
  US 20100329162A1
• Time in Patent Office: 1,097 Days
• Field of Search: 370/328, 370/329, 370/320, 370/321, 370/335, 370/337, 370/343, 370/346, 370/338, 370/443, 370/445, 455/419, 455/509, 455/500, 455/67.11, 455/446, 455/453, 455/524, 455/525
• US Class Current: 370/445
• 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 for radio filtering, comprising:

identifying a set of transceivers to be resolved on a multi-radio wireless device;

obtaining information relating to potential pairwise collisions between respective transceivers in the set of transceivers on the multi-radio wireless device; 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective 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 at a given time interval by the set of transceivers to be resolved; and

identifying one or more events in the set of events to evaluate in the given time interval based on the received information relating to the set of events.

3. The method of claim 2, wherein the given time interval comprises a current decision unit (DU) and the set of events comprises one or more of an immediate event that starts at a next DU, an ongoing event that started in a past DU and executes through the current DU, or a future event that starts subsequent to the next DU and potentially conflicts with one or more of the immediate event or the ongoing event.

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

generating a graph comprising nodes corresponding to respective transceivers in the set of transceivers and edges connecting respective nodes and corresponding to potential pairwise collisions between the respective transceivers corresponding to the respective nodes connected with the edges; and

generating the respective non-overlapping clusters based at least in part on 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 transmit components and nodes corresponding to one or more receive components of one or more of the respective transceivers in the set of transceivers; and

the dividing comprises dividing the set of transceivers into respective non-overlapping resolution clusters that distinguish between the one or more transmit components and the one or more receive components of the one or more respective transceivers.

6. The method of claim 4, wherein:

the generating a graph comprises constructing nodes corresponding to one or more transmit components and one or more receive components of the one or more of the respective transceivers in the set of transceivers that are operating in one or more of an active mode or a sleep mode; and

the dividing comprises dividing the set of transceivers into respective non-overlapping sleep clusters that regard the one or more transmit components and the one or more receive components of the one or more respective transceivers as a single entity.

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

constructing a combination node corresponding to a plurality of aggressor transceivers that can jointly collide with one or more victim transceivers;

constructing a plurality of constituent nodes respectively corresponding to the plurality of aggressor transceivers that can jointly collide with the one or more victim transceivers; and

constructing edges connecting the combination node to the plurality of constituent nodes.

8. The method of claim 1, further comprising building one or more resolution tables based at least in part on the respective non-overlapping clusters dividing the set of transceivers.

9. The method of claim 8, wherein the building comprises:

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

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

10. The method of claim 9, wherein:

the obtaining information comprises generating a graph comprising nodes that represent transmit or receive components of respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the transmit or receive components of the respective transceivers that correspond to the respective nodes and finding respective connected subgraphs in the graph; and

the generating the one or more resolution tables comprises creating the one or more resolution tables for the respective connected subgraphs found in the graph.

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

12. A method for radio filtering, comprising:

identifying a set of transceivers to be resolved on a multi-radio wireless device;

obtaining information relating to potential pairwise collisions between respective transceivers in the set of transceivers on the multi-radio wireless device; 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster, wherein the dividing comprises;

generating a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges; and

generating the respective non-overlapping clusters based at least in part on one or more maximal connected subgraphs of the graph, wherein the generating respective non-overlapping clusters comprises;

initializing a primary transceiver set to initially contain substantially no transceivers and a secondary transceiver set to initially contain 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 in the graph that are connected to the selected node in the graph;

moving respective transceivers corresponding to the selected node and the respective nodes that are 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 respective transceivers with respect to additional nodes corresponding to one or more of 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.

13. The method of claim 12, wherein the generating respective non-overlapping 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 respective transceivers, the iterating, and the generating a cluster in an iterative manner until substantially all transceivers are removed from the secondary transceiver set.

14. A method for radio filtering, comprising:

identifying a set of transceivers to be resolved on a multi-radio wireless device;

obtaining information relating to potential pairwise collisions between respective transceivers in the set of transceivers on the multi-radio wireless device;

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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster; and

building one or more resolution tables that correspond to one or more respective subsets of potentially conflicting transceivers in the set of transceivers based at least in part on the respective non-overlapping clusters dividing the set of transceivers, wherein building the one or more resolution tables comprises;

generating a graph to obtain information relating to the one or more respective subsets of potentially conflicting transceivers, wherein the generated graph comprises nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges;

finding respective connected subgraphs in the graph, wherein finding the respective connected subgraphs comprises;

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

determining additional nodes in the graph that are connected to the respective pairs of nodes via one or more of the edges that represent previously identified collisions between the respective transceivers represented in the graph;

identifying respective collisions represented in the graph corresponding to respective connected subgraphs in the graph that include the previously identified collisions and the determined additional connected nodes; and

iterating the determining additional nodes and the identifying respective collisions until substantially no further collisions between the respective transceivers represented in the graph are identified; and

creating the one or more resolution tables for the respective connected subgraphs found in the graph based on the respective collisions identified from the graph.

15. A wireless communications apparatus, comprising:

a memory that stores data relating to a set of transceivers to be resolved on a multi-radio wireless device; 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective 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 at a given time interval by the set of transceivers to be resolved; and

the processor is further configured to identify one or more events in the set of events to evaluate in the given time interval based on the data relating to the set of events stored in the memory to identify the set of transceivers to be resolved on the multi-radio wireless device.

17. The wireless communications apparatus of claim 16, wherein the given time interval comprises a current decision unit (DU) and the set of events comprises one or more of an immediate event that starts at a next DU, an ongoing event that started in a past DU and executes through the current DU, or a future event that starts subsequent to the next DU and potentially conflicts with one or more of the immediate event or the ongoing event.

18. The wireless communications apparatus of claim 15, wherein the processor is further configured to generate a graph comprising nodes corresponding to respective transceivers in the set of transceivers and edges connecting respective nodes and corresponding to potential pairwise collisions between the respective transceivers corresponding to the respective nodes connected with the edges and to generate the respective non-overlapping clusters based at least in part one 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 transmit components and nodes corresponding to one or more receive components of one or more of the respective transceivers in the set of transceivers and to divide the set of transceivers into respective non-overlapping resolution clusters that distinguish between the one or more transmit components and the one or more receive components of the one or more respective transceivers.

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

21. The wireless communications apparatus of claim 18, wherein the processor is further configured to construct a combination node in the graph corresponding to a plurality of aggressor transceivers that can jointly conflict with one or more victim transceivers, to construct a plurality of constituent nodes in the graph respectively corresponding to the plurality of aggressor transceivers that can jointly collide with the one or more victim transceivers, and to construct edges in the graph connecting the combination node to the plurality of constituent nodes.

22. 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 the respective non-overlapping clusters dividing the set of transceivers.

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

24. The wireless communications apparatus of claim 23, wherein the processor is further configured to generate a graph nodes comprising nodes that represent transmit or receive components of respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the transmit or receive components of the respective transceivers that correspond to the respective nodes, to find respective connected subgraphs in the graph, and to create the one or more resolution tables for the respective connected subgraphs found in the graph.

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

26. A wireless communications apparatus, comprising:

a memory that stores data relating to a set of transceivers to be resolved on a multi-radio wireless device; and

a processor further 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster, wherein to divide the set of transceivers into the respective non-overlapping clusters, the processor is further configured to generate a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges, initialize a primary transceiver set to initially contain substantially no transceivers and a secondary transceiver set to initially contains substantially all transceivers represented in the graph, select a node in the graph corresponding to a transceiver in the secondary transceiver set, identify respective nodes in the graph that are connected to the selected node in the graph, move respective transceivers corresponding to the selected node and the respective nodes that are connected to the selected node from the secondary transceiver set to the primary transceiver set, iteratively select a node, identify respective nodes that are connected to the selected node, and move respective transceivers with respect to additional nodes corresponding to one or more transceivers or combinations of transceivers in the primary transceiver set until substantially no further nodes are identified, and generate a cluster among the respective non-overlapping clusters based at least in part on one or more maximal connected subgraphs of the graph determined from respective transceivers in the primary transceiver set upon completion of the iterating.

27. The wireless communications apparatus of claim 26, wherein the processor is further configured to empty the primary transceiver set upon generating the cluster and to iteratively select respective nodes, identify nodes that are connected to the respective selected nodes, move respective 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.

28. A wireless communications apparatus comprising:

a memory that stores data relating to a set of transceivers to be resolved on a multi-radio wireless device; and

a processor further configured to obtain information relating to potential pairwise collisions between respective transceivers in the set of transceivers, 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster, to generate a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges, to identify second order collisions between respective transceivers in the set of transceivers based at least in part on respective pairs of nodes in the graph that are connected via the edges, to determine additional nodes in the graph that are connected to the respective pairs of nodes via one or more of the edges that represent previously identified collisions between the respective transceivers represented in the graph, to identify respective collisions represented in the graph corresponding to respective connected subgraphs in the graph that include the previously identified collisions and the determined additional connected nodes, to iteratively determine the additional nodes and identify the respective collisions until substantially no further collisions between the respective transceivers represented in the graph are identified, and to build one or more resolution tables that correspond to one or more respective subsets of potentially conflicting transceivers in the set of transceivers based at least in part on the respective connected subgraphs and the respective collisions identified from the graph.

29. An apparatus for radio filtering, comprising:

means for identifying a set of transceivers to be resolved on a multi-radio wireless device;

means for obtaining information relating to potential pairwise collisions between respective transceivers in the set of transceivers on the multi-radio wireless device; and

means for 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster.

30. A computer-readable storage medium comprising instructions that, when executed on a processor, cause the processor to:

identify a set of transceivers to be resolved on a multi-radio wireless device;

obtain information relating to potential pairwise collisions between respective transceivers in the set of transceivers on the multi-radio wireless device; and

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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster.

31. An apparatus for radio filtering, comprising:

means for identifying a set of transceivers to be resolved on a multi-radio wireless device;

means for obtaining information relating to potential pairwise collisions between respective transceivers in the set of transceivers on the multi-radio wireless device; and

means for 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster, wherein the means for dividing comprises;

means for generating a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges; and

means for generating the respective non-overlapping clusters based at least in part on one or more maximal connected subgraphs of the graph, wherein the means for generating respective non-overlapping clusters comprises;

means for initializing a primary transceiver set to initially contain substantially no transceivers and a secondary transceiver set to initially contain substantially all 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 in the graph that are connected to the selected node in the graph;

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

means for iteratively invoking the means for selecting a node, the means for identifying respective nodes, and the means for moving respective transceivers with respect to additional nodes corresponding to one or more of 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 transceivers in the primary transceiver set upon completion of the iterating.

32. A computer-readable storage medium comprising instructions that, when executed on a processor, cause the processor to:

identify a set of transceivers to be resolved on a multi-radio wireless device;

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

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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster, wherein the instructions that cause the processor to divide the set of transceivers into the respective non-overlapping clusters further cause the processor to;

generate a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges;

initialize a primary transceiver set to initially contain substantially no transceivers and a secondary transceiver set to initially contains substantially all transceivers represented in the graph;

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

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

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

iteratively select a node, identify respective nodes that are connected to the selected node, and move respective transceivers with respect to additional nodes corresponding to one or more transceivers or combinations of transceivers in the primary transceiver set until substantially no further nodes are identified; and

generate a cluster among the respective non-overlapping clusters based at least in part on one or more maximal connected subgraphs of the graph determined from respective transceivers in the primary transceiver set upon completion of the iterating.

33. An apparatus for radio filtering, comprising:

means for identifying a set of transceivers to be resolved on a multi-radio wireless device;

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

means for 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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster;

means for generating a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges;

means for identifying second order collisions between respective transceivers in the set of transceivers based at least in part on respective pairs of nodes in the graph that are connected via the edges;

means for determining additional nodes in the graph that are connected to the respective pairs of nodes via one or more of the edges that represent previously identified collisions between the respective transceivers represented in the graph;

means for identifying respective collisions represented in the graph corresponding to respective connected subgraphs in the graph that include the previously identified collisions and the determined additional connected nodes;

means for iteratively invoking the means for determining the additional nodes and the means for identifying the respective collisions until substantially no further collisions between the respective transceivers represented in the graph are identified; and

means for building one or more resolution tables that correspond to one or more respective subsets of potentially conflicting transceivers in the set of transceivers based at least in part on the respective connected subgraphs and collisions identified from the graph.

34. A computer-readable storage medium comprising instructions that, when executed on a processor, cause the processor to:

identify a set of transceivers to be resolved on a multi-radio wireless device;

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

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 among the respective non-overlapping clusters and respective transceivers that are associated with a given cluster among the respective non-overlapping clusters do not exhibit potential pairwise collisions with respective transceivers not associated with the given cluster;

generate a graph comprising nodes that represent respective transceivers in the set of transceivers and edges that connect respective nodes and represent potential pairwise collisions between the respective transceivers that correspond to the respective nodes connected with the edges;

identify second order collisions between respective transceivers in the set of transceivers based at least in part on respective pairs of nodes in the graph that are connected via the edges;

determine additional nodes in the graph that are connected to the respective pairs of nodes via one or more of the edges that represent previously identified collisions between the respective transceivers represented in the graph;

identify respective collisions represented in the graph corresponding to respective connected subgraphs in the graph that include the previously identified collisions and the determined additional connected nodes;

iteratively determine the additional nodes and identify the respective collisions until substantially no further collisions between the respective transceivers represented in the graph are identified; and

build one or more resolution tables that correspond to one or more respective subsets of potentially conflicting transceivers in the set of transceivers based at least in part on the respective connected subgraphs and collisions identified from the graph.