Discovery of objects in wireless environments

• US 9,467,842 B2
• Filed: 12/12/2013
• Issued: 10/11/2016
• Est. Priority Date: 12/12/2013
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Acer, Utku G., Pianese, Fabio
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): NG, CHRISTINE Y
• Application Number:
  US14/104,037
• Publication Number:
  US 20150172900A1
• Time in Patent Office: 1,034 Days
• Field of Search: 370/252, 370/328, 370/338, 370/401
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals

Abstract

An object discovery capability is provided to enable discovery of objects in a wireless environment, which may include discovering objects available from a set of wireless nodes in a wireless environment. The discovery of objects available from a set of wireless nodes may include a determination as to whether a particular object is available from the set of wireless nodes, identification of the wireless node or nodes from which a particular object is available, or the like. The object discovery capability may leverage physical features of the wireless medium (namely the additive nature of wireless signals in a Hertzian broadcast channel) in combination with set reconciliation techniques (e.g., using data encoding structures, such as Bloom filters, with information at the physical layer or one or more other layers) in order to enable discovery of objects available from a set of wireless nodes in a wireless environment.

Claims

1. An apparatus for discovering objects available from a set of wireless nodes, the apparatus comprising:

a processor and a memory communicatively connected to the processor, the processor configured to;

receive a sequence of combined wireless signals, the combined wireless signals being respective wireless combinations of wireless signals of respective wireless signal sequences transmitted by the wireless nodes, the wireless signal sequences of the wireless nodes being representative of respective local object data structures of the wireless nodes, the local object data structures of the wireless nodes being indicative of respective sets of objects available from the wireless nodes; and

generate a combined object data structure based on the sequence of combined wireless signals, the combined object data structure being indicative of objects available from the set of wireless nodes.

2. The apparatus of claim 1, wherein the wireless signal sequences transmitted by the wireless nodes correspond to respective sequences of values of the local object data structures of the wireless nodes, wherein the sequences of values of the local object data structures of the wireless nodes are indicative of the respective sets of objects available from the wireless nodes.

3. The apparatus of claim 2, wherein, to generate the combined object data structure, the processor is configured to:

analyze one of the combined wireless signals to determine whether the one of the combined wireless signals is a global signal for FALSE that is used by each of the wireless nodes to represent FALSE values within the respective object data structures of the wireless nodes.

4. The apparatus of claim 3, wherein, to analyze one of the combined wireless signals to determine whether the one of the combined wireless signals is a global signal for FALSE, the processor is configured to:

calculate a projection of the combined wireless signal on the global signal for FALSE.

5. The apparatus of claim 3, wherein, to generate the combined object data structure, the processor is configured to:

based on a determination that the one of the combined wireless signals is a wireless combination of global signals for FALSE, set a corresponding value position of the combined object data structure to a value for FALSE.

6. The apparatus of claim 3, wherein, to generate the combined object data structure, the processor is configured to:

based on a determination that the one of the combined wireless signals is not a wireless combination of global signals for FALSE, set a corresponding value position of the combined object data structure to a value for TRUE.

7. The apparatus of claim 1, wherein the processor is configured to:

determine the sequence of combined wireless signals based on;

8. The apparatus of claim 1, wherein the processor is configured to:

determine, based on the combined object data structure, whether a particular object is available from at least one of the wireless nodes in the set of wireless nodes.

9. The apparatus of claim 8, wherein, to determine whether a particular object is available from at least one of the wireless nodes in the set of wireless nodes, the processor is configured to:

determine a set of value positions of the combined object data structure corresponding to the particular object; and

determine whether the particular object is available from at least one of the wireless nodes in the set of wireless nodes based on a set of values from the set of value positions of the combined object data structure corresponding to the particular object.

10. The apparatus of claim 1, wherein the processor is configured to:

identify, based on the sequence of combined wireless signals, one of the wireless nodes from which a particular object is available.

11. The apparatus of claim 10, wherein, to identify one of the wireless nodes from which a particular object is available, the processor is configured to:

identify, from the sequence of combined wireless signals, one of the combined wireless signals corresponding to a value position of the combined object data structure which, when set to TRUE, indicates availability of the particular object; and

determine one of the wireless signals of one of the wireless nodes which contributed to the identified one of the combined wireless signals.

12. The apparatus of claim 11, wherein, to determine one of the wireless signals of one of the wireless nodes which contributed to the identified one of the combined wireless signals, the processor is configured to:

determine a set of signals, the set of signals including a global signal for FALSE that is used by each of the wireless nodes to represent FALSE values within respective local object data structures of the wireless nodes, the set of signals including respective signals for TRUE that are unique to the wireless nodes and used by the wireless nodes in order to represent TRUE values within the respective local object data structures of the wireless nodes; and

determine the one of the wireless signals of one of the wireless nodes which contributed to the identified one of the combined wireless signals based on projection of the identified one of the combined wireless signals onto each signal in the set of signals S.

13. The apparatus of claim 12, wherein, to determine the set of signals, the processor is configured to:

initialize the set of signals to include the global signal for FALSE;

initialize a sequence of temporary signals r[n] having respective temporary signals equal to the combined wireless signals in the sequence of combined wireless signals;

iterate as follows until respective values of the temporary signals r[n] are below a threshold;

iterate as follows on each of the combined wireless signals;

compute a value of the temporary signal r[n] by subtracting projections of the combined wireless signal y[n] on the set of signals S;

determine, from among the temporary signals r[n], a wireless signal q having a lowest energy value that is greater than a threshold; and

add the determined signal q to the set of signals S.

14. The apparatus of claim 12, wherein, to determine the one of the wireless signals of one of the wireless nodes which contributed to the identified one of the combined wireless signals based on projection of the identified one of the combined wireless signals onto each signal in the set of signals S, the processor is configured to:

for each signal (s) in the set of signals;

calculate a temporary signal r[n,s] by projecting the identified one of the combined wireless signals on the signal s from the set of signals; and

determine whether the signal s contributed to the identified one of the combined wireless signals y[n] by measuring an energy value of the temporary signal r[n,s] and comparing the energy value of the temporary signal r[n,s] against a threshold.

15. The apparatus of claim 1, wherein the objects comprise at least one of node identifiers of the wireless nodes, information available from the wireless nodes, content items available from the wireless nodes, or services available from the wireless nodes.

16. The apparatus of claim 1, wherein the local object data structures are Bloom filters and the combined object data structure is a Bloom filter.

17. The apparatus of claim 1, wherein the processor is configured to:

wirelessly transmit a request for objects message, the sequence of combined wireless signals being received responsive to processing of the request for objects message by the wireless nodes.

18. The apparatus of claim 1, wherein the memory is configured to store a local object data structure indicative of objects available from the apparatus, wherein the processor is configured to:

represent the local object data structure as a sequence of signals by providing, for each value in a sequence of values of the local object data structure, a respective signal representing the value in the sequence of values, wherein each FALSE value in the sequence of values is represented using a global signal for FALSE that is used by each of the wireless nodes to represent FALSE values within the respective local object data structures of the wireless nodes, wherein each TRUE value in the sequence of values is represented using a local signal for TRUE that is unique to the wireless node for use by the wireless node to represent TRUE values of the respective local object data structure of the wireless node; and

transmit the sequence of signals wirelessly.

19. The apparatus of claim 1, wherein the local object data structures of the respective wireless nodes comprise respective sets of values, wherein each FALSE value in each of the sets of values of the respective wireless nodes is represented using a global signal for FALSE that is used by each of the wireless nodes in the set of wireless nodes to represent FALSE values of the respective object data structures of the wireless nodes, wherein, for each of the wireless nodes in the set of wireless nodes, each TRUE value in the respective set of values of the respective wireless node is represented using a local signal for TRUE that is unique within the set of wireless nodes for use only by the respective wireless node to represent TRUE values of the object data structure of the respective wireless node.

20. The apparatus of claim 19, wherein, to generate the combined object data structure, the processor is configured to:

determine whether one of the combined wireless signals is a global signal for FALSE; and

set a value position of the combined object data structure, associated with the one of the combined wireless signals, to a value for FALSE based on a determination that the one of the combined wireless signals is a global signal for FALSE or to a value for TRUE based on a determination that the one of the combined wireless signals is not a global signal for FALSE.

21. A method for discovering objects available from a set of wireless nodes, the method comprising:

using a processor and a memory for;

receiving a sequence of combined wireless signals, the combined wireless signals being respective wireless combinations of wireless signals of respective wireless signal sequences transmitted by the wireless nodes, the wireless signal sequences of the wireless nodes being representative of respective local object data structures of the wireless nodes, the local object data structures of the wireless nodes being indicative of respective sets of objects available from the wireless nodes; and

generating a combined object data structure based on the sequence of combined wireless signals, the combined object data structure being indicative of objects available from the set of wireless nodes.

22. A wireless node of a set of wireless nodes, the set of wireless nodes comprising the wireless node and at least one other wireless node, the wireless node comprising:

a memory configured to store an object data structure indicative of objects available at the wireless node, the object data structure comprising a set of values; and

a processor communicatively connected to the memory, the processor configured to;

represent the object data structure as a sequence of signals by providing, for each value in the set of values, a respective signal representing the value in the set of values, wherein each FALSE value in the set of values is represented using a global signal for FALSE that is used by each of the wireless nodes in the set of wireless nodes to represent FALSE values within respective object data structures of the wireless nodes, wherein each TRUE value in the set of values is represented using a local signal for TRUE that is unique within the set of wireless nodes for use only by the wireless node to represent TRUE values of the object data structure of the wireless node; and

control transmission of the sequence of signals from the wireless node wirelessly.

23. A method for use by a wireless node of a set of wireless nodes, the set of wireless nodes comprising the wireless node and at least one other wireless node, the method comprising:

using a processor and a memory for;

storing an object data structure indicative of objects available at the wireless node, the object data structure comprising a set of values;

representing the object data structure as a sequence of signals by providing, for each value in the set of values, a respective signal representing the value in the set of values, wherein each FALSE value in the set of values is represented using a global signal for FALSE that is used by each of the wireless nodes in the set of wireless nodes to represent FALSE values within respective object data structures of the wireless nodes, wherein each TRUE value in the set of values is represented using a local signal for TRUE that is unique within the set of wireless nodes for use only by the wireless node to represent TRUE values of the object data structure of the wireless node; and

controlling transmission of the sequence of signals from the wireless node wirelessly.