Adaptive search in mobile peer-to-peer databases

• US 7,849,139 B2
• Filed: 05/02/2008
• Issued: 12/07/2010
• Est. Priority Date: 05/02/2007
• Status: Expired due to Fees

• Current Assignee: Pirouette Software Consulting Co.
• Original Assignee: Pirouette Software Consulting Co.
• Inventors: Xu, Bo, Wolfson, Ouri
• Primary Examiner(s): Patel; Haresh N
• Application Number:
  US12/114,150
• Publication Number:
  US 20090210495A1
• Time in Patent Office: 949 Days
• Field of Search: 709/205, 709217-224, 370/252, 370/310
• US Class Current: 709/205
• CPC Class Codes: G06F 16/256 in federated or virtual databases
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1061 using node-based peer discovery mechanisms static access to replicated servers H04L67/1006; service discovery H04L67/51
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/1078 Resource delivery mechanisms
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Information is stored in a plurality of mobile peers. The peers communicate in a peer to peer fashion, using a short-range wireless network. Occasionally, a peer initiates a search for information in the peer to peer network by issuing a query. Queries and pieces of information, called reports, are transmitted among peers that are within a transmission range. For each search additional peers are utilized, wherein these additional peers search and relay information on behalf of the originator of the search.

Claims

1. A method of searching information located within a plurality of peer-devices wherein said plurality of peer-devices store information in the form of reports and communicate by a short-range wireless network, comprising the steps of:

(a) initiating a multihop search, represented by a query, by an originator in said plurality of peer-devices wherein said originator does not need to know the locations of searched reports;

(b) transmitting said query by said originator to at least one neighbor of said originator, wherein a neighbor is an additional peer-device in said plurality of peer-devices that is within transmission range of a transmitter;

(c) selecting queries and reports from local storage by set X of peer-devices from said plurality of peer-devices that receive queries or reports, and transmitting selected queries and reports to neighbors of said set X;

(d) repeating step 1 (c) recursively; and

(e) ranking reports by a peer-device P1, wherein the rank of a report R1 is a function of the demand for R1 which is the number of peer-devices in said short-range wireless network requesting R1 or the total degree to which R1 matches the requests of said peer-devices, or of the size of R1, or of the reliability of R1, or of the supply of R1 in said short-range wireless network wherein said supply is the fraction of peer-devices having R1;

wherein the rank of said report R1 computed by said peer-device P1 at time t, denoted rank(R1, t), is proportional to demand(R1,t), or proportional to (1-supply(R1,t)), or proportional to reliability(R1, t) where reliability(R1,t) is a function that returns the reliability of R1 at time t, or inversely proportional to size (R1).

2. The method of claim 1, wherein the rank of said report R1 computed by said peer-device P1 at time t, denoted rank(R1,t), is approximately

3. The method of claim 2 wherein said peer-device P1 selects reports to transmit or save using an algorithm whose objective is to maximize rank(R1,t)×

size(R1).

4. The method of claim 1 wherein said peer-device P1 selects reports to transmit or save using an algorithm whose objective is to maximize rank(R1,t)×

size(R1).

5. The method of claim 1, wherein said peer-device P1 stores a database of queries that represents a demand for reports in said short-range wireless network.

6. The method of claim 5, wherein said peer-device P1 saves in said database of queries the queries of latest peer devices encountered.

7. The method of claim 5, wherein said peer-device P1 sets the size of database of queries such that the accuracy of an estimated demand is higher than a pre-specified level of confidence.

8. The method of claim 1, further comprising the steps of:

estimating by said peer-device P1 the fraction of peer-devices in said short-range wireless network that have said report R1 at a particular time, denoted supply(R1), wherein;

(a) said peer device P1 uses a number of indicator variables, including the age of R1 or the number of times P1 received R1, to determine whether or not R1 is new R1'"'"'s recipient peer-devices;

(b) said peer-device P1 puts either a pair (indicator-variables'"'"' values, “

new”

) or a pair (indicator-variables'"'"' values, “

not new”

) in P1'"'"'s examples database, based on the determination in 10(a); and

(c) when R1 is ranked by P1, it invokes a machine learning algorithm that uses said P1'"'"'s examples database to determine the probability that if transmitted, R1 will be new to a recipient peer-devices, and this is taken to be supply(R1).

9. The method of claim 8, wherein a MALENA algorithm is an instance of the implementation.

10. The method of claim 8, further comprising the steps of:

(a) improving a “

new”

or “

not new”

labeling, by said peer-device P1, by maintaining a tracking set, wherein said tracking set stores a plurality of identifications of the reports that have been received by P1; and

(b) labeling a report “

not new”

by said peer-device P1, if its identification is in said tracking set.

11. The method of claim 1, wherein a peer-device P2 dynamically adjusts a transmission size or an inter-transmission period of time, to optimize utilization of bandwidth or transmission energy, comprising the steps of:

(a) computing the capacity of said short-range wireless network, by said peer-device P2, as a function of the inter-transmission period of time and of the transmission-size; and

(b) either

(b.1) selecting said transmission size, by said peer-device P2, that optimizes the capacity of said short-range wireless network for a given inter-transmission period of time;

or

(b.2) selecting said inter-transmission period of time, by said peer-device P2, that optimizes the capacity of said short-range wireless network for a given transmission size

12. The method of claim 1, further comprising a multi-mode communication protocol, executed by said plurality of peer-devices, wherein a transmission by a peer-device P3 is initiated when encountering another peer-device;

if such an encounter does not occur within a pre-specified period of time, then reports received by P3 since the last transmission are broadcast to peer-devices in transmission range.

13. The method of claim 1, further comprising the step of:

using access to the Internet or a cellular network in order to enhance search, wherein if a peer-device P4 receives a report R2 that matches a query originating in another peer-device P5, then P4 may send said report R2 to P5 via the Internet or said cellular network.

14. The method of claim 1, wherein a user of a peer-device P6 is allowed to limit total energy E of P6 allocated to search for a specified life-time T, wherein:

(a) said peer-device P6 divides said specified life-time T into cycles;

(b) said peer-device P6 assigns to a cycle an energy quota Q when said cycle starts, wherein said energy quota Q is based on the remaining available energy and the remaining life-time of said peer-device P6; and

(c) said peer-device P6 stops transmission, receiving, and listening on behalf of search when energy consumed by search at P6 at said cycle, including transmission, receiving, and listening, exceeds said energy quota Q.

15. The method of claim 1, further comprising synchronization of peer-devices in said short-range wireless network, wherein:

(a) each peer-device divides time into listen-transmit-receive cycles;

(b) in each cycle, each peer-device performs listening, transmitting, and receiving in some order; and

(c) cycles of all the peers-devices are synchronized using a Global Positioning System time, or the time of a cellular service provider, or any other time service.

16. A non-transitory computer readable medium having stored therein instructions for causing a processor to execute the method of claim 1.

17. A method of searching information in a group of peer-devices, in a peer to peer system communicating by short-range wireless network, comprising the steps of:

(a) storing information by a plurality of peer-devices, wherein said plurality of peer-devices are in communication with each other;

(b) transmitting queries or reports by said plurality of peer-devices, wherein a report represents a piece of information and transmitting and receiving peer-devices are within a transmission range;

(c) utilizing for a search additional peer-devices, by an originator, wherein said additional peer-devices search and relay information on behalf of said originator;

(d) estimating by a peer-device the fraction of peer-devices in said short-range wireless network that have a report at a particular time using the MALENA algorithm; and

(e) dynamically adjusting a transmission size or an inter-transmission period of time, by a peer-device, to optimize utilization of bandwidth and transmission energy, comprising the steps of;

(e.1) computing the capacity of said short-range wireless network, by said peer-device, as a function of inter-transmission period of time and transmission-size; and

(e.2) either

(e.2.1) selecting said transmission size, by said peer-device, that optimizes the capacity of said short-range wireless network for a given inter-transmission period of time;

or

(e.2.2) selecting said inter-transmission period of time, by said peer-device, that optimizes the capacity of said short-range wireless network for a given transmission size.