Method and system for proximity-based information retrieval and exchange in ad hoc networks

• US 20050188062A1
• Filed: 02/23/2004
• Published: 08/25/2005
• Est. Priority Date: 02/23/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Shehktman, Gene, Li, Michael B.
• Granted Patent: US 8,959,187 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/54 Presence management, e.g. monitoring or registration for receipt of user log-on information, or the connection status of the users
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A network has clients and a server. The clients can discover and be discovered by each other. Discovery includes emitting requests to and acquiring identifying information from clients within a certain geographical range. A discovering client sends all identifying information to the server. The server includes client information database and topological map, comprised of nodes representing clients and edges indicating the discovery of one client by another. When the server receives identifying information from the discovering client, the server updates the topological map and determines which neighboring clients of the discovering client matches the match criteria of the discovering client. The server may determine a discovery schedule detailing which client should discover next. The server may send the match information and discovery schedule to the discovering client, discovered clients, or a third party. The server may also store this information.

Claims

1. A network, wherein discovery consists of emitting a plurality of requests and acquiring identifying information, the network comprising:

a plurality of clients configured to send and receive information and configured to be either in a mode to discover other clients or in a mode to be discoverable by other clients, the plurality of clients including;

a plurality of secondary clients in the mode to be discoverable; and

at least one primary client in the mode to discover secondary clients; and

at least one server configured to send information to and receive information from the at least one primary client, the information received from the at least one primary client including identifying information of a plurality of discovered secondary clients, the at least one server including;

a client information database for storing client information associated with the plurality of clients, including identifying information, match information, and match criteria;

a matcher configured to identify matching secondary clients by determining neighboring secondary clients, and determining which neighboring secondary clients have client information that match the primary client'"'"'s match criteria; and

wherein when the at least one primary client sends to the at least one server the identifying information of the secondary clients acquired by the at least one primary client, and the matcher identifies matching secondary clients.

2. The network in claim 1, wherein the at least one server transmits match information.

3. The network in claim 2, wherein the at least one server transmits the match information of the matching secondary clients to the at least one primary client.

4. The network in claim 2, wherein the at least one server transmits the match information of the matching secondary clients to a third party.

5. The network in claim 1, wherein the at least one server further includes:

a topological map representing the plurality of clients, the topological map comprising nodes representing and associated with each client and edges between the nodes such that each node representing the at least one primary client is within one edge to the nodes representing the secondary clients that the at least one primary client has discovered; and

a topological mapper configured to update the topological map upon the at least one server'"'"'s receipt of information from the at least one primary client; and

wherein the matcher further uses the topological map updated by the topological mapper to identify the list of matching secondary clients.

6. The network in claim 2, wherein the at least one server transmits the match information of the primary client to the matching secondary clients.

7. The network of claim 2, wherein the match information includes a URL.

8. The network in claim 7, wherein at least one of the plurality of clients further includes a display.

9. The network of claim 8, wherein at least one of the plurality of clients that includes a display further includes:

a webpage creator creating a webpage that displays the URLs included in the match information received from the server as links;

an Internet connection; and

a web browser that displays the webpage created by the web page creator and the web pages indicated by the URLs displayed thereon.

10. The network of claim 9, wherein at least one of the plurality of clients that includes a display is configured to annotate the webpages indicated by the URLs displayed on the web browser.

11. The network of claim 1, wherein the matcher'"'"'s identification of matching secondary clients are limited by a boundary.

12. The network in claim 11, wherein the boundary is a predetermined number of clients from the primary client.

13. The network of claim 11, wherein the boundary is a predetermined number of matching secondary clients.

14. The network in claim 1, wherein each of the plurality of clients cycles between the active state (SA), during which a client discovers other clients, or the passive state (SP), during which a client is discoverable.

15. The network in claim 14, wherein either or both of the duration of the active state (SA) and the duration of the passive state (SP) are random.

16. The network in claim 14, wherein the at least one server is further configured to control the duration of the active state (SA) and the duration of the passive state (SP) for each of the plurality of clients.

17. The network in claim 16, wherein the client information stored on the client information database further includes a discovery timestamp associated with each client, designating the time at which each client was most recently in the active state (SA);

and

the at least one server further includes a scheduler configured to schedule the discovery activity of the plurality of clients.

18. The network of claim 17, wherein the scheduler schedules the discovery activity of the at least one primary client by selecting the neighboring secondary client with the most recent discovery timestamp, then setting a skip flag only if the current time is less than the timestamp plus a predetermined discovery threshold, the server sending the flag along with the match information of the matching secondary clients to the primary client;

and

the at least one primary client further configured to skip the active state (SA) and remain in the passive state (SP) for the duration of the active state (SA) portion of the cycle if the skip flag is set.

19. The network of claim 18, wherein the predetermined discovery threshold is tunable.

20. The network of claim 18, wherein the predetermined discovery threshold is greater than the average duration of the active state (SA) minus a predetermined allowance of variation in the active state (SA) duration (D_SA) minus twice a predetermined allowance of variation in the passive state (SP) duration (D_SP), but greater than the average duration of the active state (SA) plus the predetermined allowance of variation in the active state (SA) duration (D_SA) plus twice the predetermined allowance of variation in the passive state (SP) duration (D_SP).

21. The network in claim 18, wherein the scheduler schedules the discovery activity of a neighboring secondary client by selecting the neighboring secondary client with the least recent discovery timestamp, and sending an instruction to the neighboring secondary client to go into active state (SA);

and

the at least one primary client further configured to skip the active state (SA) and remain in the passive state (SP) for the duration of the active state (SA) portion of the cycle.

22. The network in claim 17, wherein the scheduler further identifies a locality group of the at least one primary client, the locality group consisting of the at least one primary client and the secondary clients that are within a predetermined distance from the at least one primary client;

and

the server further sends a message to each client in the locality group instructing each client to go into active state (SA) at different times but to remain in passive state (SP) at the same time interval, wherein the time interval at which the clients are instructed to remain in SP depends upon the number of clients in the locality group and a predetermined frequency at which a client in the locality group must go into SA.

23. The network of claim 1, further comprising:

a plurality of non-clients, configured to be discoverable;

wherein

the at least one primary client is further configured to discover non-clients; and

the information received from the at least one primary client further including identifying information from the discovered non-clients.

24. The network of claim 23, wherein the server further comprising:

a topological map representing the plurality of clients and the plurality of non-clients, the topological map further comprising nodes representing and associated with each client and non-client, and edges between the nodes such that each node representing the at least one primary client is within one edge to the nodes representing the secondary clients and the non-clients that the at least one primary client discovered.

25. A system for detecting clients that match a predetermined criteria, wherein discovery consists of emitting a plurality of requests and acquiring identifying information, the system comprising:

a plurality of client modules configured to send and receive information, the plurality of client module s including;

a plurality of secondary client modules configured to be discoverable; and

at least one primary client module configured to discover secondary client modules; and

at least one server module configured to send information to and receive information from the at least one primary client module, the information received from the at least one primary client module including identifying information of the discovered secondary client modules, the at least one server module including;

a client information database for storing client information associated with the plurality of client modules, including identifying information, match information, and match criteria;

a matcher configured to identify matching secondary client modules by determining neighboring secondary client modules, and determining which neighboring secondary client modules have client information that match the primary client module'"'"'s match criteria; and

wherein when the at least one primary client module sends to the at least one server module the identifying information of the secondary client modules acquired by the at least one primary client module, and the matcher identifies matching secondary client modules.

26. The system in claim 25, wherein the at least one server module transmits match information.

27. The system in claim 26, wherein the at least one server module transmits the match information of the matching secondary client modules to the at least one primary client module.

28. The system in claim 26, wherein the at least one server module transmits the match information of the secondary clients to a third party.

29. The system in claim 25, wherein the at least one server further includes:

a topological map representing the plurality of client modules, the topological map comprising nodes representing and associated with each client module and edges between the nodes such that each node representing the at least one primary client module is within one edge to the nodes representing the secondary client modules that the at least one primary client module has discovered; and

a topological mapper configured to update the topological map upon the at least one server'"'"'s receipt of information from the at least one primary client module; and

wherein the matcher further uses the topological map updated by the topological mapper to identify the list of matching secondary client modules.

30. The system in claim 26, wherein the at least one server module sends the match information of the primary client module to the matching secondary client modules.

31. The system of claim 26, wherein the match information includes a URL.

32. The system in claim 31, wherein at least one of the plurality of client modules further includes a display.

33. The system of claim 32, wherein the at least one of the plurality of client modules that includes a display further includes:

a webpage creator creating a webpage that displays the URLs included in the match information received from the server as links;

an Internet connection; and

a web browser that displays the webpage created by the web page creator and the web pages indicated by the URLs displayed thereon.

34. The system of claim 33, wherein the at least one of the plurality of client modules that includes a display is configured to annotate the webpages indicated by the URLs displayed on the web browser.

35. The system of claim 25, wherein the matcher'"'"'s identification of matching secondary client modules are limited by a boundary.

36. The system in claim 35, wherein the boundary is a predetermined number of client modules from the primary client module.

37. The system of claim 35, wherein the boundary is a predetermined number of matching secondary client modules.

38. The system in claim 25, wherein each of the plurality of client modules cycles between the active state (SA), during which a client module discovers other client modules, or the passive state (SP), during which a client module is discoverable.

39. The system in claim 38, wherein either or both of the duration of the active state (SA) and the duration of the passive state (SP) are random.

40. The system in claim 38, wherein the at least one server module is further configured to control the duration of the active state (SA) and the duration of the passive state (SP) for each of the plurality of client modules.

41. The system in claim 40, wherein the client module information stored on the client module information database further includes a discovery timestamp associated with each client module, designating the time at which each client module was most recently in the active state (SA);

and

the at least one server further includes a scheduler configured to schedule the discovery activity of the plurality of client modules.

42. The system in claim 41, wherein the scheduler schedules the discovery activity of the at least one primary client module by selecting the neighboring secondary client module with the most recent discovery timestamp, then setting a skip flag only if the current time is less than the timestamp plus a predetermined discovery threshold, the server module sending the flag along with the match information of the matching secondary client modules to the primary client module;

and

the at least one primary client module further configured to skip the active state (SA) and remain in the passive state (SP) for the duration of the active state (SA) portion of the cycle if the skip flag is set.

43. The system of claim 42, wherein the predetermined discovery threshold is tunable.

44. The system of claim 42, wherein the predetermined discovery threshold is greater than the average duration of the active state (SA) minus a predetermined allowance of variation in the active state (SA) duration (D_SA) minus twice a predetermined allowance of variation in the passive state (SP) duration (D_SP), but greater than the average duration of the active state (SA) plus the predetermined allowance of variation in the active state (SA) duration (D_SA) plus twice the predetermined allowance of variation in the passive state (SP) duration (D_SP).

45. The system in claim 42, wherein the client module information stored on the client module information database further including a discovery timestamp associated with each client module, designating the time at which the client module was most recently in the active state (SA);

and

the at least one server further including a scheduler configured to schedule the discovery activity of the at least one primary client module by selecting the neighboring secondary client module with the least recent discovery timestamp, and sending an instruction to the neighboring secondary client module to go into active state (SA); and

the at least one primary client module further configured to skip the active state (SA) and remain in the passive state (SP) for the duration of the active state (SA) portion of the cycle.

46. The system of claim 41, wherein the scheduler further identifies a locality group of the at least one primary client, the locality group consisting of the at least one primary client and the secondary clients that are within a predetermined distance from the at least one primary client;

and

the server module further sends a message to each client in the locality group instructing each client to go into active state (SA) at different times but to remain in passive state (SP) at the same time interval, wherein the time interval at which the clients are instructed to remain in SP depends upon the number of clients in the locality group and a predetermined frequency at which a client in the locality group must go into SA.

47. The system of claim 25, further comprising:

a plurality of non-client modules, configured to be discoverable;

wherein

the at least one primary client module is further configured to discover non-client modules; and

the information received from the at least one primary client module further including identifying information from the discovered non-client modules.

48. The system of claim 47, wherein the server further comprising:

a topological map representing the plurality of client modules and the plurality of non-client modules, the topological map further comprising nodes representing and associated with each client module and non-client module, and edges between the nodes such that each node representing the at least one primary client module is within one edge to the nodes representing the secondary client modules and the non-client modules that the at least one primary client module discovered.

49. A method of operating a network, wherein discovery consists of emitting a plurality of requests and acquiring identifying information, the network comprising at least one server and a plurality of clients configured to send and receive information, the plurality of clients including a plurality of secondary clients configured to be discoverable and at least one primary client configured to discover secondary clients, the method comprising the steps of:

at the at least one primary client;

discovering secondary clients; and

sending information, including the identifying information, to the server;

at the at least one server;

receiving information from the at least one primary client;

updating a client information database with the information from the at least one primary client;

determining neighboring secondary clients; and

searching the client information database that stores client information associated with the plurality of clients, including identifying information, match information, and match criteria, for client information of neighboring secondary clients that match the at least one primary client'"'"'s match criteria to identify matching secondary clients.

50. The method of claim 49, further comprising the step of:

at the at least one server;

transmitting match information.

51. The method of claim 50, wherein at the at least one server, the transmitted match information is the match information of the matching secondary clients and the transmitted match information is transmitted to the at least one primary client.

52. The method of claim 50, wherein at the at least one server, the transmitted match information is the match information of the matching secondary clients and the transmitted match information is transmitted to a third party.

53. The method of claim 49, further comprising the steps of:

at the at least one server;

after the step of updating the client information database, updating a topological map representing the plurality of clients, the topological map comprising nodes representing and associated with each client and edges between the nodes such that each node representing the at least one primary client is within one edge to the nodes representing the secondary clients that the at least one primary client has discovered; and

the searching step further includes using the updated topological map.

54. The method of claim 50, wherein at the at least one server, the transmitted match information is the match information of the at least one primary client and the transmitted match information is transmitted to the matching secondary clients.

55. The method of claim 50, wherein the match information includes a URL.

56. The method of claim 55, wherein at least one of the plurality of clients further includes a display.

57. The method of claim 56, further comprising the steps of:

at the at least one of the plurality of clients that includes a display;

creating a webpage that displays the URLs included in the match information received from the server as links;

displaying the webpage in a web browser; and

further displaying the webpages indicated by the URLs.

58. The method of claim 57, further comprising the step of:

at the at least one of the plurality of clients that includes a display;

annotating the webpages indicated by the URLs.

59. The method of claim 49, wherein the step of determining further includes limiting the neighboring secondary clients by a boundary.

60. The method of claim 59, wherein the boundary is a predetermined number of clients from the primary client.

61. The method of claim 59, wherein the boundary is a predetermined number of matching secondary clients.

62. The method of claim 49, wherein each of the plurality of clients cycles between the active state (SA), during which a client discovers other clients, or the passive state (SP), during which a client is discoverable.

63. The method of claim 62, wherein either or both of the duration of the active state (SA) and the duration of the passive state (SP) are random.

64. The method of claim 62, wherein the at least one server is further configured to control the duration of the active state (SA) and the duration of the passive state (SP) for each of the plurality of clients.

65. The method of claim 64, wherein the client information stored on the client information database further includes a discovery timestamp associated with each client, designating the time at which each client was most recently in the active state (SA), the method further including the step of:

at the at least one server;

scheduling the discovery activity of the plurality of clients.

66. The method of claim 65, further including the steps of:

at the at least one server;

updating the client information stored for the primary client with the current time as the discovery timestamp for the at least one primary client;

selecting the neighboring secondary client with the most recent discovery timestamp;

setting a skip flag only if the current time is less than the timestamp plus a predetermined discovery threshold; and

transmitting the match information of the matching secondary clients and the flag to the primary client; and

at the at least one primary client;

skipping the active state (SA); and

remaining in the passive state (SP) for the duration of the active state (SA) portion of the cycle if the skip flag is set.

67. The method of claim 66, wherein the predetermined discovery threshold is tunable.

68. The method of claim 66, wherein the predetermined discovery threshold is greater than the average duration of the active state (SA) minus a predetermined allowance of variation in the active state (SA) duration (D_SA) minus twice a predetermined allowance of variation in the passive state (SP) duration (D_SP), but greater than the average duration of the active state (SA) plus the predetermined allowance of variation in the active state (SA) duration (D_SA) plus twice the predetermined allowance of variation in the passive state (SP) duration (D_SP).

69. The method of claim 65, further comprising the steps of:

at the at least one server;

the updating step further includes associating a discovery timestamp with each client, designating the time at which the client was most recently in the active state (SA);

the scheduling step further includes selecting the neighboring secondary client with the least recent discovery timestamp; and

sending an instruction to the neighboring secondary client to go into active state (SA); and

at the at least one primary client;

skipping the active state (SA); and

remaining in the passive state (SP) for the duration of the active state (SA) portion of the cycle.

70. The method of claim 65, further comprising the steps of:

at the at least one server;

identifying a locality group of the at least one primary client, the locality group consisting of the at least one primary client and the secondary clients that are within a predetermined distance from the at least one primary client; and

sending a message to each client in the locality group instructing each client to go into active state (SA) at different times but to remain in passive state (SP) at the same time interval, wherein the time interval at which the clients are instructed to remain in SP depends upon the number of clients in the locality group and a predetermined frequency at which a client in the locality group must go into SA.

71. The method of claim 49, wherein the network further comprises a plurality of non-clients, configured to be discoverable, said method further comprising the steps of:

at the at least one primary client;

the discovering step further comprising discovering non-clients;

the receiving step further comprising receiving identifying information from the discovered non-clients; and

the sending step further comprising including identifying information from the discovered non-clients in the information sent; and

at the server;

the updating step further including updating the client information database with information from the discovered non-clients.

72. The method of claim 71, further comprising:

at the server;

updating a topological map representing the plurality of clients and non-clients, the topological map further comprising nodes representing and associated with each client and non-client, and edges between the nodes such that each node representing the at least one primary client is within one edge to the nodes representing the secondary clients and the non-clients that the at least one primary client has discovered; and

the searching step further includes searching the topological map.

73. A computer media, wherein discovery consists of emitting a plurality of requests and acquiring identifying information, the computer media comprising:

a data structure including characteristic information about a plurality of clients and an access flag for each client represented, the access flag being in one of two states consisting of active and passive, the plurality of clients including at least one primary client that discovers and a plurality of secondary clients that are discoverable;

instructions for receiving an indication that the primary client represented in the data structure is within a predetermined distance of the secondary clients represented in the data structure;

wherein

the access flag for the primary client is set to the active state;

the access flags for the plurality of secondary clients is set to the passive state; and

instructions for finding secondary clients represented in the data structure with characteristic information matching the primary client'"'"'s characteristic information.

74. The computer media in claim 73, further comprising instructions for transmitting characteristic information.

75. The computer media in claim 73, further comprising instructions for creating a topological map of the plurality of clients.

76. The computer media in claim 75, further comprising instructions for including a plurality of non-clients in the topological map.

77. The computer media in claim 73, further comprising instructions for scheduling the change of access flags for each of the clients.

78. The computer media in claim 73, wherein the instructions for finding secondary clients further include setting a boundary for the secondary clients that may be considered as having characteristic information that matches the primary client'"'"'s characteristic information.

79. The computer media in claim 73, wherein the characteristic information includes URLs.