Adaptive search in mobile peer-to-peer databases
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
17 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). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
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.
-
Specification