ADAPTIVE SEARCH IN MOBILE PEER-TO-PEER DATABASES

• US 20090210495A1
• Filed: 05/02/2008
• Published: 08/20/2009
• Est. Priority Date: 05/02/2007
• Status: Active Grant

• Current Assignee: Pirouette Software Consulting Co.
• Original Assignee: Pirouette Software Consulting Co.
• Inventors: Xu, Be, Wolfson, Ouri
• Granted Patent: US 7,849,139 B2
• Time in Patent Office: Days
• 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 in a group of peers, in a peer to peer system communicating by short-range wireless network, comprising the steps of:

(a) storing information in each of a plurality of peers, wherein the peers are in communication with each other;

(b) transmitting queries or pieces of information (called reports) among the plurality of peers, wherein the transmitting and receiving peers are within a transmission range; and

(c) utilizing for a search additional peers, wherein these additional peers search and relay information on behalf of the originator of the search.

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

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

ranking the reports, wherein the ranking is done in one of the plurality of peers, and wherein the rank of a report is a function of the number of the peers requesting the report in the wireless network, and/or the total degree to which the report matches the requests of these peers, and/or the supply of the report in the wireless network (i.e. the number of peers having the report), and/or the size of the report, and/or the reliability of the report.

4. The method of claim 3, wherein:

the rank of a report R at peer at time t is defined in formula 3.2 rank(R, t) is approximately

5. The method of claim 3, wherein rank (R,t) is approximately

6. The method of claim 3 wherein the reports transmitted or saved in one of the plurality of peers is selected by an algorithm whose objective is to maximize rank(R,t)×

size(R), given a limited bandwidth or storage size for the reports.

7. The method of claim 1, wherein each of the plurality of peers stores a database of queries, called the demand database, that represents the demand for reports in the peer-to-peer network.

8. The method of claim 7, wherein each of the plurality of peers saves in the demand database the queries of the latest peers encountered.

9. The method of claim 7, wherein the size of the demand database is set such that an accuracy of the estimated demand is higher than a pre-specified level of confidence (for example, using

Pr{|demand(R,t,M)−

demand(R,t)|≦

Δ

}>

1−

2e<sup>−

2</sup>nΔ

²). 

 

formula3.3

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

estimating the fraction of peers in the network that have a report R at a particular time, denoted supply(R), wherein;

(a) a peer O associates with each report R a number of indicators, such as the age of R and the number of times O received R;

(b) the peer O that interacts with neighbors determines whether the report is new or “

previously received”

at O, depending on whether or not O already has the report in its database, and puts the pair (indicators, {“

new”

/“

previously received”

}) in O'"'"'s examples database; and

(c) when a report R is ranked by O, it invokes a machine learning algorithm that uses the examples database to determine the probability that R will be new to a random peer, and this is taken to be supply(R).

11. The method of claim 10, wherein an MALENA algorithm is an instance of the implementation.

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

(a) improving a “

previously received”

/“

new”

labeling wherein a tracking set is maintained at one of the plurality of peers, wherein the tracking set stores a plurality of identifications of the reports that have been received by the peer; and

(b) labeling a report “

previously received”

if its identification is in the tracking set.

13. The method of claim 12, wherein the total number of identifications stored in the tracking set is bounded.

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

(a) computing the capacity of the wireless network as a function of the inter-transmission period of time and the transmission-size; and

(b) either

(b.1) selecting the transmission size that optimizes the capacity of the wireless network for the given inter-transmission period (for example, using the formula

15. The method of claim 1, further comprising a multi-mode communication protocol that allows effective search in both a static and a highly mobile environment, and a smooth transition between the two, wherein a transmission by a peer O is initiated when encountering another peer;

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

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

using access to the Internet or a cellular infrastructure in order to enhance search,

wherein if a peer B receives a report that matches a query originating in another peer Q,

then B may send the report to Q via the Internet or the cellular infrastructure.

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

(a) said period of time T is divided into cycles;

(b) a cycle is assigned an energy quota when it starts, wherein the energy quota is based on the remaining available energy and the remaining life-time of the peer; and

(c) the method ensures that the energy consumed by the peer-to-peer search at M at each cycle, including transmission, receiving, and listening, does not exceed the energy allocated to that cycle.

18. The method of claim 1, further comprising synchronization of the peers in the peer-to-peer network, wherein:

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

(b) in each cycle, each peer performs listening, transmitting, and receiving in an unspecified order; and

(c) cycles of all the peers are synchronized using, for example, the Global Positioning System time, or the time of the cellular service provider.