Matching queries in a network

• US 8,271,522 B2
• Filed: 12/03/2004
• Issued: 09/18/2012
• Est. Priority Date: 12/03/2004
• Status: Active Grant

• Current Assignee: National University of Singapore
• Original Assignee: National University of Singapore
• Inventors: Mehul, Motani, Vikram, Srinivasan
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US11/720,808
• Publication Number:
  US 20090319503A1
• Time in Patent Office: 2,846 Days
• Field of Search: 709/201, 709/238, 709/218, 707/999.005, 707/999.007, 707/770, 707/771, 707/E17.032, 707/959
• US Class Current: 707/770
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/022 with dynamic range variability
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method of matching queries in a hybrid infrastructure/infrastructure-less network, the network comprising pluralities of first and second type communication devices respectively, the method comprising placing a first query by a user on one of the first type devices and forwarding the query via infrastructure based communication to one of the second type devices; forwarding, depending on a category of the first query, the first query from the one second type device to one or more first type devices via infrastructure based communication; and relaying the first query from each of one or more first type devices to one or more neighboring first type devices via infrastructure-less communication.

Claims

1. A method, comprising:

receiving a query, based on a category of the query and a geographic area assigned to the category, from a first communication device of a first type by a communication device of a second type communicatively coupled to the first communication device via a network infrastructure, wherein the communication device of the second type is located within the geographic area assigned to the category;

selecting, by the communication device of the second type, at least one second communication device of the first type from a plurality of communication devices of the first type that is at least temporarily located within the geographic area; and

forwarding, by the communication device of the second type, the query to the selected at least one second communication device via the network infrastructure,

wherein the query is respectively forwarded to the selected at least one second communication device to relay the query to at least one third communication device of the first type that is at least temporarily neighboring and communicatively coupled with the selected at least one second communication device.

2. The method as claimed in claim 1, wherein said receiving comprises receiving the query, by the communication device of the second type, via cellular services.

3. The method as claimed in claim 1, further comprising forwarding the query to one or more additional communication devices of the second type, based at least in part on the category of the query, by the communication device of the second type.

4. The method as claimed in claim 1, wherein said selecting is based at least in part on a statistical analysis of a matching time for queries and probability of a match.

5. The method as claimed in claim 1, wherein the communication device of the second type is a base station or an access point of the network infrastructure.

6. The method of claim 1, wherein said selecting further comprises randomly selecting the at least one second communication device of the first type from the plurality of communication devices of the first type.

7. The method of claim 1, wherein the first communication device, the at least second communication device, and the at least one third communication device of the first type include mobile communication devices, and wherein the communication device of the second type includes a stationary communication device.

8. The method of claim 1, wherein the first communication device, the at least one second communication device, and the at least one third communication device include communication devices configured to originate queries, and wherein the communication device of the second type includes a communication device configured to forward queries.

9. The method of claim 1, wherein the geographic area assigned to the category associated with the query is arbitrarily assigned.

10. The method of claim 1, wherein the geographic area assigned to the category associated with the query is based on characteristics of the geographic area.

11. The method of claim 1, wherein the geographic area assigned to the category associated with the query is dynamically defined.

12. The method of claim 1, wherein the query is respectively forwarded to the selected at least one third communication device to relay the query to at least one fourth communication device of the first type via one or more peer-to-peer connections separate and distinct from the network infrastructure.

13. A method, comprising:

receiving a first query associated with a category having a geographic area assigned to the category, by a first communication device of a first type, from a communication device of a second type communicatively coupled to the first communication device via a network infrastructure,

wherein the first query is originated from a second communication device of the first type located outside the geographic area, and the first query is forwarded from the second communication device of the first type to the communication device of the second type based on the category of the query and the geographic area assigned to the category,

wherein the communication device of the second type is located within the geographic area assigned to the category, and

wherein the first communication device is at least temporarily located within the geographic area;

determining, by the first communication device, whether a second query that complements the first query has been received at the first communication device; and

based on said determining, relaying, via one or more peer-to-peer connections separate and distinct from the network infrastructure, the first query from the first communication device to at least one third communication device of the first type that is at least temporarily neighboring the first communication device.

14. The method as claimed in claim 13, further comprising generating, by the first communication device, a notification message in response to a determination that the second query that complements the first query has been received.

15. The method as claimed in claim 14, further comprising transmitting, via the network infrastructure, by the first communication device, the notification message to the second communication device of the first type from which the first query or the matching second query originated.

16. The method as claimed in claim 14, wherein the notification message includes a Small Message Service (SMS) message or an Email.

17. The method as claimed in claim 13, further comprising storing, by the first communication device, the first query.

18. The method as claimed in claim 17, further comprising determining, by the first communication device, whether one or more previously stored queries are to be deleted from the first communication device, based at least in part on relative priorities of the one or more previously stored queries.

19. The method as claimed in claim 13, wherein the first communication device is a mobile station of the network infrastructure.

20. The method as claimed in claim 13, wherein the at least one third communication device that is at least temporarily neighboring the first communication device is capable of infrastructure-less communication, and incapable of infrastructure-based communication.

21. The method of claim 13, wherein said relaying further comprises relaying the first query to the at least one third communication device while the first communication device is moving about in the geographic area.

22. A non-transitory computer-readable storage medium comprising a plurality of instructions stored thereon that are configured to cause an apparatus, in response to execution of the instructions by the apparatus, to perform operations including:

receiving a query, based on a category of the query and a geographic area assigned to the category, from a first communication device of a first type communicatively coupled to the apparatus via a network infrastructure, wherein the apparatus is located within the geographic area assigned to the category;

selecting at least one second communication device of the first type from a plurality of communication devices of the first type that is at least temporarily located within the geographic area; and

forwarding the query to the selected at least one second communication device, via the network infrastructure, wherein the query is respectively forwarded to the selected at least one second communication device to relay the query to at least one third communication device of the first type that is at least temporarily neighboring and communicatively coupled with the selected at least one second communication device, and

wherein the apparatus is a communication device of a second type.

23. The non-transitory computer-readable storage medium of claim 22, wherein the query is respectively forwarded to the selected at least one third communication device to relay the query to at least one fourth communication device of the first type via one or more peer-to-peer connections separate and distinct from the network infrastructure.

24. A non-transitory computer-readable storage medium, comprising a plurality of instructions stored thereon that are configured to cause a first communication device of a first type, in response to execution of the instruction by the first communication device of the first type, to perform operations including:

receiving a first query associated with a category having a geographic area assigned to the category, via a network infrastructure, from a communication device of a second type communicatively coupled to the first communication device via the network infrastructure,

wherein the first query is originated from a second communication device of the first type located outside the geographic area, and the first query is forwarded from the second communication device of the first type to the communication device of the second type based on the category of the query and the geographic area assigned to the category,

wherein the communication device of the second type is located within the geographic area assigned to the category, and

wherein the first communication device is at least temporarily located within the geographic area;

determining whether a second query that complements the first query has been received by the first communication device; and

based on said determining, relaying the first query, via one or more peer-to-peer communications separate and distinct from the network infrastructure, to at least one third communication device of the first type that is at least temporarily neighboring the first communication device.