Devices and methods for communication in ad-hoc networks

• US 9,553,769 B2
• Filed: 03/07/2013
• Issued: 01/24/2017
• Est. Priority Date: 04/06/2012
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Abraham, Santosh Paul, Cherian, George, Merlin, Simone, Sampath, Hemanth
• Primary Examiner(s): Khan, Aftab N.
• Application Number:
  US13/789,495
• Publication Number:
  US 20130268654A1
• Time in Patent Office: 1,419 Days
• Field of Search: 709/230
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In a particular embodiment, a method includes determining, by a first device, a number of discovery messages received during at least one discovery interval. Based on the number of discovery messages, an estimated number of devices in an ad-hoc network is determined. The method further includes transmitting, during a second discovery interval that is subsequent to the at least one discovery interval, a discovery message. The discovery message indicates the estimated number of devices in the ad-hoc network.

Claims

1. A method comprising:

determining, by a first device, a number of discovery messages received during at least one discovery interval;

synchronizing a subsequent communication according to one of the number of discovery messages received during the at least one discovery interval;

halting discovery message transmission attempts by the first device during the at least one discovery interval;

based on the number of discovery messages, determining an estimated number of devices in an ad-hoc network;

determining an estimated duration of a second discovery interval based on the estimated number of devices in the ad-hoc network wherein the determining the estimated duration comprises multiplying the estimated number of devices by a per device transmit time of each device within the ad-hoc network;

during the second discovery interval that is subsequent to the at least one discovery interval, transmitting a discovery message indicating the estimated number of devices in the ad-hoc network, the discovery message transmitted during the second discovery interval, wherein the second discovery interval based on the estimated duration, and

setting a duration of the second discovery interval to match the estimated duration.

2. The method of claim 1, wherein determining the number of discovery messages includes determining multiple numbers of discovery messages received over multiple discovery intervals, the multiple discovery intervals including the at least one discovery interval, and wherein determining the estimated number of devices includes selecting a highest number of the multiple numbers as the estimated number of devices.

3. The method of claim 1, wherein a duration of the second discovery interval matches the estimated duration, and wherein the discovery message further indicates an end of the second discovery interval.

4. The method of claim 1, further comprising in response to transmitting the discovery message, halting additional discovery message transmission attempts by the first device during the second discovery interval.

5. The method of claim 1, wherein the subsequent communication is synchronized according to a timestamp included in one of the discovery messages received during the at least one discovery interval.

6. The method of claim 1, wherein each of the discovery messages includes a beacon frame.

7. The method of claim 1, wherein the estimated number of devices in the ad-hoc network is different than a total number of device in the ad-hoc network.

8. The method of claim 1, wherein determining the estimated duration comprises multiplying the estimated number of devices by a scaling factor.

9. A method comprising:

determining, by a first device, a first value associated with an ad-hoc network, the first value based on a plurality of discovery messages observed during at least one discovery interval;

receiving a discovery message from a second device, the discovery message indicating a second value determined by the second device, the second value associated with the ad-hoc network;

determining whether to participate in the ad-hoc network based on a first comparison of the first value and the second value to determine an estimated number of hidden devices in the ad-hoc network and based on a second comparison of the estimated number of hidden devices to a threshold wherein determining whether to participate in the ad-hoc network includes;

performing the first comparison of the first value and the second value to determine the estimated number of hidden devices in the ad-hoc network; and

performing the second comparison of the estimated number of hidden devices to a threshold;

in response to the estimated number of hidden devices satisfying the threshold, forming a new ad-hoc network and;

in response to the estimated number of hidden devices failing to satisfy the threshold, joining the ad-hoc network.

10. The method of claim 9, wherein each of the plurality of discovery messages includes a beacon frame.

11. The method of claim 9, wherein the first value associated with the ad-hoc network comprises a number of devices associated with the ad-hoc network.

12. The method of claim 9, wherein the first value associated with the ad-hoc network comprises aggregate position information, the aggregate position information including location information associated with each device of the ad-hoc network.

13. An apparatus comprising:

a processor; and

a memory storing instructions that are executable by the processor to cause the processor to;

determine a number of discovery messages received during at least one discovery interval;

synchronizing a subsequent communication according to one of the number of discovery messages received during the at least one discovery interval;

halting discovery message transmission attempts by the first device during the at least one discovery interval;

based on the number of discovery messages, determine an estimated number of devices in an ad-hoc network;

determine an estimated duration of a second discovery interval based on the estimated number of devices in the ad-hoc network; and

during the second discovery interval that is subsequent to the at least one discovery interval wherein the estimated duration comprises multiplying the estimated number of devices by a per device transmit time of each device within the ad-hoc network and;

transmit a discovery message indicating the estimated number of devices in the ad-hoc network, the discovery message transmitted during the second discovery interval, the second discovery interval based on the estimated duration wherein the second discovery interval is based on the estimated duration and setting a duration of the second discovery interval to match the estimated duration.

14. The apparatus of claim 13, wherein the instructions are further executable by the processor to determine multiple numbers of discovery messages received over multiple discovery intervals, the multiple discovery intervals including the at least one discovery interval, and further to determine the estimated number of devices by selecting a highest number of the multiple numbers as the estimated number of devices.

15. The apparatus of claim 13, wherein the discovery message further indicates an estimated end of the second discovery interval based on the estimated duration of the second discovery interval.

16. An apparatus comprising:

a processor; and

a memory storing instructions that are executable by the processor to cause the processor to;

determine a first value associated with an ad-hoc network, the first value based on a plurality of discovery messages observed by a first device during at least one discovery interval;

receive a discovery message from a second device, the discovery message indicating a second value determined by the second device; and

determine whether to participate in the ad-hoc network based on a first comparison of the first value and the second value to determine an estimated number of hidden devices in the ad-hoc network and based on a second comparison of the estimated number of hidden devices to a threshold,

wherein performing the first comparison of the first value and the second value to determine the estimated number of hidden devices in the ad-hoc network; and

performing the second comparison of the estimated number of hidden devices to a threshold;

in response to a determination that the estimated number of hidden devices satisfies the threshold, initiate formation of a new ad-hoc network and in response to the estimated number of hidden devices failing to satisfy the threshold, joining the ad-hoc network.

17. The apparatus of claim 16, wherein the first value associated with the ad-hoc network comprises a number of devices associated with the ad-hoc network.

18. The apparatus of claim 16, wherein the first value associated with the ad-hoc network comprises aggregate position information, the aggregate position information including location information associated with each device of the ad-hoc network.

19. An apparatus comprising:

means for determining a number of discovery messages received during at least one discovery interval and for determining, based on the number of discovery messages, an estimated number of devices in an ad-hoc network;

means for synchronizing a subsequent communication according to one of the number of discovery messages received during the at least one discovery interval;

means for halting discovery message transmission attempts by the first device during the at least one discovery interval;

means for determining an estimated duration of a second discovery interval based on the estimated number of devices in the ad-hoc network; and

means for transmitting a discovery message during the second discovery interval that is subsequent to the at least one discovery interval, the discovery message indicating the estimated number of devices in the ad-hoc network, the discovery message transmitted during the second discovery interval, the second discovery interval based on the estimated duration and setting a duration of the second discovery interval to match the estimated duration.

20. The apparatus of claim 19, wherein the means for determining the number of discovery messages includes a processor, and wherein the means for transmitting the discovery message includes a radio frequency (RF) interface.

21. The apparatus of claim 19, integrated within a mobile device.

22. An apparatus comprising:

means for determining a first value associated with an ad-hoc network, the first value based on a plurality of discovery messages observed by a first device during at least one discovery interval; and

means for receiving a discovery message from a second device, the discovery message indicating a second value determined by the second device,

wherein a determination whether to participate in the ad-hoc network is based on a comparison of the first value and the second value to determine an estimated number of hidden devices and based on a comparison of the estimated number of hidden devices to a threshold wherein determining whether to participate in the ad-hoc network includes;

performing the first comparison of the first value and the second value to determine the estimated number of hidden devices in the ad-hoc network; and

performing the second comparison of the estimated number of hidden devices to a threshold;

means for forming a new ad-hoc network in response to a determination that the estimated number of hidden devices satisfies the threshold; and

means for joining the ad-hoc network in response to the estimated number of hidden devices failing to satisfy the threshold.

23. The apparatus of claim 22, wherein the first value associated with the ad-hoc network comprises a number of devices associated with the ad-hoc network.

24. The apparatus of claim 22, wherein the means for determining the first value includes a processor, and wherein the means for receiving the discovery message includes a radio frequency (RF) interface.

25. The apparatus of claim 22, integrated into a mobile device.

26. A non-transitory computer-readable medium storing instructions that are executable by a processor to cause the processor to:

determine a number of discovery messages received during at least one discovery interval;

synchronize a subsequent communication according to one of the number of discovery messages received during the at least one discovery interval;

halt discovery message transmission attempts by the first device during the at least one discovery interval;

based on the number of discovery messages, determine an estimated number of devices in an ad-hoc network;

determine an estimated duration of a second discovery interval based on the estimated number of devices in the ad-hoc network wherein the determining the estimated duration comprises multiplying the estimated number of devices by a per device transmit time of each device within the ad-hoc network; and

during the second discovery interval that is subsequent to the at least one discovery interval, transmit a discovery message indicating the estimated number of devices in the ad-hoc network, the discovery message transmitted during the second discovery interval, wherein the second discovery interval based on the estimated duration and setting a duration of the second discovery interval to match the estimated duration.

27. The non-transitory computer-readable medium of claim 26, wherein the instructions are further executable by the processor to determine multiple numbers of discovery messages received over multiple discovery intervals, the multiple discovery intervals including the at least one discovery interval, and wherein the instructions are further executable by the processor to determine the estimated number of devices by selecting a highest number of the multiple numbers as the estimated number of devices.

28. The non-transitory computer-readable medium of claim 26, wherein the discovery message further indicates an estimated end of the second discovery interval based on the estimated duration of the second discovery interval.

29. A non-transitory computer-readable medium storing instructions that are executable by a processor to cause the processor to:

determine a first value associated with an ad-hoc network, the first value based on a plurality of discovery messages observed by a first device during at least one discovery interval;

receive a discovery message from a second device, the discovery message indicating a second value determined by the second device, the second value associated with the ad-hoc network;

determine whether to participate in the ad-hoc network based on comparing the first

value and the second value to determine an estimated number of hidden devices in

the ad-hoc network and based on comparing the estimated number of hidden devices to a threshold wherein determining whether to participate in the ad-hoc network includes;

performing the first comparison of the first value and the second value to determine the estimated number of hidden devices in the ad-hoc network;

performing the second comparison of the estimated number of hidden devices to a threshold;

in response to a determination that the estimated number of hidden devices satisfies the threshold, form a new ad-hoc network; and

in response to the estimated number of hidden devices failing to satisfy the threshold, joining the ad-hoc network.

30. The non-transitory computer-readable medium of claim 29, wherein the first value associated with the ad-hoc network comprises a number of devices associated with the ad-hoc network.

31. The non-transitory computer-readable medium of claim 29, wherein the first value associated with the ad-hoc network comprises aggregate position information, the aggregate position information including location information associated with each device of the ad-hoc network.