# US 9,521,044 B2 · Systems and methods for discovering devices in a neighborhood aware network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,521,044 B2
- Document ID: US9521044B2
- Status: Granted
- Kind: B2
- Application number: 14/195,677
- Filed: 2014-03-03
- Published: 2014-09-11
- Granted: 2016-12-13
- Earliest claimed: 2013-03-08
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Santosh Paul Abraham; George Cherian; Alireza Raissinia; Guido Robert Frederiks
- Web page: https://patentgrep.com/patent/US9521044B2

## CPC

- H04W 8/005: {Discovery of network devices, e.g. terminals}
- H04W 4/38: for collecting sensor information
- H04W 4/70: Services for machine-to-machine communication [M2M] or machine type communication [MTC]
- H04W 48/16: Discovering, processing access restriction or access information
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

Methods, devices, and computer program products communicating discovery information in a wireless neighborhood aware network (NAN). One method includes receiving a message from a neighboring wireless device. The message includes an identifier associated with the neighboring wireless device. The method further includes adding the identifier to a data structure indicative of discovered device identifiers. The method further includes transmitting a message including the data structure indicative of discovered device identifiers.

## Claims

### Claim 1

A method of communicating discovery information in a wireless neighborhood aware network (NAN), comprising:
receiving a message from a neighboring wireless device, the message comprising an identifier associated with the neighboring wireless device;
adding the identifier to a data structure indicative of discovered device identifiers; and
transmitting a message comprising the data structure indicative of discovered device identifiers,
wherein:
the data structure comprises a Bloom filter,
the Bloom filter is a bit array of m bits with k different hash functions associated with the bit array, wherein each hash function maps an input string to one of the m array positions with a uniform random distribution, and
at least one of the k hash functions H(j,X,m) is defined as: (CRC32(j∥X) & 0xFFFF) mod m, wherein j is a modification string, X is the input string, and CRC32 is a 32 bit cyclic redundancy code.

### Claim 2 (depends on 1)

The method of claim 1, wherein the received message comprises a discovery response message.

### Claim 3 (depends on 1)

The method of claim 1, wherein the transmitted message comprises a discovery query message.

### Claim 4 (depends on 1)

The method of claim 1, wherein the data structure comprises a list of at least partial identifiers.

### Claim 5 (depends on 4)

The method of claim 4, wherein the at least partial identifiers comprise a subset of bytes of the identifier.

### Claim 6 (depends on 1)

The method of claim 1, wherein the message further comprises a Bloom filter index indicating a specific set of hash functions associated with the bit array.

### Claim 7 (depends on 6)

The method of claim 6, wherein the Bloom filter index is updated in subsequent transmissions.

### Claim 8 (depends on 1)

The method of claim 1, wherein said adding the identifier comprises:
feeding the identifier to each of the k hash functions to get k array positions; and
setting the bits at all the k array positions to 1.

### Claim 9 (depends on 1)

The method of claim 1, wherein the parameter k of the Bloom filter has a value of 4, and the parameter m of the Bloom filter has a value being larger than 5 times a number of devices to indicate in the bloom filter.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
generating a second Bloom filter using a different set of hash functions; and
transmitting a second message comprising the second Bloom filter.

### Claim 11 (depends on 1)

The method of claim 1, wherein the transmitted message comprises a length field, a discovery control field, and a discovered addresses information field.

### Claim 12 (depends on 11)

The method of claim 11, wherein the discovery control field comprises a type flag indicative of a presence of a Bloom filter, an include flag indicative of a desired station response, and a Bloom filter index identifying a specific set of hash functions associated with an associated Bloom filter.

### Claim 13 (depends on 12)

The method of claim 12, wherein the length field is one octet, the discovery control field is one octet, the type flag is one bit, the include flag is one bit, the Bloom filter index is two bits, and the discovered addresses information field is a variable length.

### Claim 14 (depends on 12)

The method of claim 12, wherein the include flag, when not set, indicates that devices indicated in the Bloom filter should not respond, and when set, indicates that only devices indicated in the Bloom filter should transmit.

### Claim 15 (depends on 12)

The method of claim 12, wherein the discovery control field further comprises a query index.

### Claim 16 (depends on 1)

The method of claim 1, wherein the identifier comprises a media access control (MAC) address.

### Claim 17

A wireless device configured to communicate discovery information in a wireless neighborhood aware network (NAN), comprising:
a receiver configured to receive a message from a neighboring wireless device, the message comprising an identifier associated with the neighboring wireless device;
a memory configured to store a data structure indicative of discovered device identifiers;
a processor configured to add the identifier to the data structure stored in the memory; and
a transmitter configured to transmit a message comprising the data structure indicative of discovered device identifiers,
wherein:
the data structure comprises a Bloom filter,
the Bloom filter is a bit array of m bits with k different hash functions associated with the bit array, wherein each hash function mass an input string to one of the m array positions with a uniform random distribution, and
at least one of the k hash functions H(j,X,m) is defined as: (CRC32(j∥X) & 0xFFFF) mod m, wherein j is a modification string, X is the input string, and CRC32 is a 32 bit cyclic redundancy code.

### Claim 18 (depends on 17)

The wireless device of claim 17, wherein the received message comprises a discovery response message.

### Claim 19 (depends on 17)

The wireless device of claim 17, wherein the transmitted message comprises a discovery query message.

### Claim 20 (depends on 17)

The wireless device of claim 17, wherein the data structure comprises a list of at least partial identifiers.

### Claim 21 (depends on 20)

The wireless device of claim 20 wherein the at least partial identifiers comprise a subset of bytes of the identifier.

### Claim 22 (depends on 17)

The wireless device of claim 17, wherein the message further comprises a Bloom filter index indicating a specific set of hash functions associated with the bit array.

### Claim 23 (depends on 22)

The wireless device of claim 22, wherein the Bloom filter index is updated in subsequent transmissions.

### Claim 24 (depends on 17)

The wireless device of claim 17, wherein said adding the identifier comprises:
feeding the identifier to each of the k hash functions to get k array positions; and
setting the bits at all the k array positions to 1.

### Claim 25 (depends on 17)

The wireless device of claim 17, wherein the parameter k of the Bloom filter has a value of 4, and the parameter m of the Bloom filter has a value being larger than 5times a number of devices to indicate in the bloom filter.

### Claim 26 (depends on 17)

The wireless device of claim 17, wherein:
the processor is further configured to generate a second Bloom filter using a different set of hash functions; and
the transmitter is further configured to transmit a second message comprising the second Bloom filter.

### Claim 27 (depends on 17)

The wireless device of claim 17, wherein the transmitted message comprises a length field, a discovery control field, and a discovered addresses information field.

### Claim 28 (depends on 27)

The wireless device of claim 27, wherein the discovery control field comprises a type flag indicative of a presence of a Bloom filter, an include flag indicative of a desired station response, and a Bloom filter index identifying a specific set of hash functions associated with an associated Bloom filter.

### Claim 29 (depends on 28)

The wireless device of claim 28, wherein the length field is one octet, the discovery control field is one octet, the type flag is one bit, the include flag is one bit, the Bloom filter index is two bits, and the discovered addresses information field is a variable length.

### Claim 30 (depends on 28)

The wireless device of claim 28, wherein the include flag, when not set, indicates that devices indicated in the Bloom filter should not respond, and when set, indicates that only devices indicated in the Bloom filter should transmit.

### Claim 31 (depends on 28)

The wireless device of claim 28, wherein the discovery control field further comprises a query index.

### Claim 32 (depends on 17)

The wireless device of claim 17, wherein the identifier comprises a media access control (MAC) address.

### Claim 33

An apparatus for communicating discovery information in a wireless neighborhood aware network (NAN), comprising:
means for receiving a message from a neighboring wireless device, the message comprising an identifier associated with the neighboring wireless device;
means for adding the identifier to a data structure indicative of discovered device identifiers; and
means for transmitting a message comprising the data structure indicative of discovered device identifiers,
wherein:
the data structure comprises a Bloom filter,
the Bloom filter is a bit array of m bits with k different hash functions associated with the bit array, wherein each hash function maps an input string to one of the m array positions with a uniform random distribution, and
at least one of the k hash functions H(j,X,m) is defined as: (CRC32(j∥X) & 0xFFFF mod m wherein is a modification string, X is the input string, and CRC32 is a 32 bit cyclic redundancy code.

### Claim 34 (depends on 33)

The apparatus of claim 33, further comprising:
means for feeding the identifier to each of k different hash functions, each associated with a Bloom filter bit array of m bits, to get k array positions; and
means for setting the bits of the bit array at all the k array positions to 1.

### Claim 35 (depends on 34)

The apparatus of claim 34, further comprising:
means for generating a second Bloom filter using a different set of hash functions; and
means for transmitting a second message comprising the second Bloom filter.

### Claim 36

A non-transitory computer-readable medium comprising code that, when executed, cause an apparatus to:
receive a message from a neighboring wireless device, the message comprising an identifier associated with the neighboring wireless device;
add the identifier to a data structure indicative of discovered device identifiers; and
transmit a message comprising the data structure indicative of discovered device identifiers
wherein:
the data structure comprises a Bloom filter,
the Bloom filter is a bit array of m bits with k different hash functions associated with the bit array, wherein each hash function maps an input string to one of the m array positions with a uniform random distribution, and
at least one of the k hash functions H(j,X,m) is defined as: (CRC32(j∥X) & 0xFFFF) mod m, wherein j is a modification string, X is the input string, and CRC32 is a 32 bit cyclic redundancy code.

### Claim 37 (depends on 36)

The medium of claim 36, further comprising code that, when executed, causes the apparatus to add the identifier to the data structure by:
feeding the identifier to each of k different hash functions, each associated with a Bloom filter bit array of m bits, to get k array positions; and
setting the bits of the bit array at all the k array positions to 1.

### Claim 38 (depends on 37)

The apparatus of claim 37, further comprising code that, when executed, causes the apparatus to:
generate a second Bloom filter using a different set of hash functions; and
transmit a second message comprising the second Bloom filter.