Systems and methods for discovering devices in a neighborhood aware network

A first 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 a data structure indicative of discovered device identifiers;
• a processor configured to determine whether the data structure indicates an identifier of the first wireless device;
• and
• a transmitter configured to transmit a message comprising the identifier of the first wireless device when the data structure does not indicate the identifier of the first wireless device,
• 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.

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 a data structure indicative of discovered device identifiers;
• means for determining whether the data structure indicates an identifier of the apparatus;
• and
• means for transmitting a message comprising the identifier of the apparatus when the data structure does not indicate the identifier of the apparatus,
• 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.

A non-transitory computer-readable medium comprising code that, when executed, causes an apparatus to:

• receive a message from a neighboring wireless device, the message comprising a data structure indicative of discovered device identifiers;
• determine whether the data structure indicates an identifier of the apparatus;
• and
• transmit a message comprising the identifier of the apparatus when the data structure does not indicate the identifier of the apparatus,
• 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.

A method of communicating discovery information in a wireless neighborhood aware network (NAN), comprising:

• receiving, at a first wireless device, a message from a neighboring wireless device, the message comprising a data structure indicative of discovered device identifiers;
• determining whether the data structure indicates an identifier of the first wireless device;
• transmitting a message comprising the identifier of the first wireless device when the data structure does not indicate the identifier of the first wireless device;
• receiving a second message comprising a second Bloom filter and a query index;
• determining whether the data structure indicates the identifier of the first wireless device using a different set of hash functions;
• and
• responding to the second message when the first wireless device has not responded to a query with the same query index and the data structure does not indicate the identifier of the first wireless device,
• wherein:
• the data structure comprises a Bloom filter, and
• 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.

A first 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 a data structure indicative of discovered device identifiers;
• a processor configured to determine whether the data structure indicates an identifier of the first wireless device;
• and
• a transmitter configured to transmit a message comprising the identifier of the first wireless device when the data structure does not indicate the identifier of the first wireless device,
• 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,
• the receiver is further configured to receive a second message comprising a second Bloom filter and a query index;
• and
• the processor is further configured to:
• determine whether the data structure indicates the identifier of the first wireless device using a different set of hash functions;
• and
• respond to the second message when the first wireless device has not responded to a query with the same query index and the data structure does not indicate the identifier of the first wireless device.

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 a data structure indicative of discovered device identifiers;
• means for determining whether the data structure indicates an identifier of the apparatus;
• means for transmitting a message comprising the identifier of the apparatus when the data structure does not indicate the identifier of the apparatus;
• means for receiving a second message comprising a second Bloom filter and a query index;
• means for determining whether the data structure indicates the identifier of the apparatus using a different set of hash functions;
• and
• means for responding to the second message when the apparatus has not responded to a query with the same query index and the data structure does not indicate the identifier of the apparatus,
• wherein:
• the data structure comprises a Bloom filter, and
• 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.

A non-transitory computer-readable medium comprising code that, when executed, causes an apparatus to:

• receive a message from a neighboring wireless device, the message comprising a data structure indicative of discovered device identifiers;
• determine whether the data structure indicates an identifier of the apparatus;
• and
• transmit a message comprising the identifier of the apparatus when the data structure does not indicate the identifier of the apparatus;
• receive a second message comprising a second Bloom filter and a query index;
• determine whether the data structure indicates the identifier of the apparatus using a different set of hash functions;
• and
• respond to the second message when the apparatus has not responded to a query with the same query index and the data structure does not indicate the identifier of the apparatus,
• wherein:
• the data structure comprises a Bloom filter, and
• 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.