US 8,351,456 B2 · Method and apparatus for radio filtering in a multi-radio device

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.

Claims34

Dependent claims

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.

1 more element

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.

11 more elements

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.

11 more elements

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.

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.

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.

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.

11 more elements

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.

9 more elements

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.

7 more elements

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.

7 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims34