Adaptive search in mobile peer-to-peer databases
View Patent ↗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.
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 P 1 , wherein the rank of a report R 1 is a function of the demand for R 1 which is the number of peer-devices in said short-range wireless network requesting R 1 or the total degree to which R 1 matches the requests of said peer-devices, or of the size of R 1 , or of the reliability of R 1 , or of the supply of R 1 in said short-range wireless network wherein said supply is the fraction of peer-devices having R 1 ;
wherein the rank of said report R 1 computed by said peer-device P 1 at time t, denoted rank(R 1 , t), is proportional to demand(R 1 ,t), or proportional to (1-supply(R 1 ,t)), or proportional to reliability(R 1 , t) where reliability(R 1 ,t) is a function that returns the reliability of R 1 at time t, or inversely proportional to size (R 1 ).
2. The method of claim 1 , wherein the rank of said report R 1 computed by said peer-device P 1 at time t, denoted rank(R 1 ,t), is approximately
demand
(
R
1
,
t
)
·
(
1
-
supply
(
R
1
,
t
)
)
·
reliability
(
R
1
,
t
)
size
(
R
1
)
,
where reliability(R 1 ,t) is a function that returns the reliability of R 1 at time t.
3. The method of claim 2 wherein said peer-device P 1 selects reports to transmit or save using an algorithm whose objective is to maximize rank(R 1 ,t)×size(R 1 ).
4. The method of claim 1 wherein said peer-device P 1 selects reports to transmit or save using an algorithm whose objective is to maximize rank(R 1 ,t)×size(R 1 ).
5. The method of claim 1 , wherein said peer-device P 1 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 P 1 saves in said database of queries the queries of latest peer devices encountered.
7. The method of claim 5 , wherein said peer-device P 1 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 P 1 the fraction of peer-devices in said short-range wireless network that have said report R 1 at a particular time, denoted supply(R 1 ), wherein:
(a) said peer device P 1 uses a number of indicator variables, including the age of R 1 or the number of times P 1 received R 1 , to determine whether or not R 1 is new R 1 's recipient peer-devices;
(b) said peer-device P 1 puts either a pair (indicator-variables' values, “new”) or a pair (indicator-variables' values, “not new”) in P 1 's examples database, based on the determination in 10 ( a ); and
(c) when R 1 is ranked by P 1 , it invokes a machine learning algorithm that uses said P 1 's examples database to determine the probability that if transmitted, R 1 will be new to a recipient peer-devices, and this is taken to be supply(R 1 ).
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 P 1 , by maintaining a tracking set, wherein said tracking set stores a plurality of identifications of the reports that have been received by P 1 ; and
(b) labeling a report “not new” by said peer-device P 1 , if its identification is in said tracking set.
11. The method of claim 1 , wherein a peer-device P 2 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 P 2 , 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 P 2 , 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 P 2 , that optimizes the capacity of said short-range wireless network for a given transmission size
ThR
≈
2
·
π
·
λ
·
k
·
1
c
·
∫
0
r
δ
·
(
1
-
p
′
)
λ
·
r
·
(
2
·
q
(
δ
2
·
r
)
+
(
π
-
2
·
q
(
δ
2
·
r
)
)
·
(
2
T
+
1
)
)
-
1
ⅆ
δ
)
.
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 P 3 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 P 3 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 P 4 receives a report R 2 that matches a query originating in another peer-device P 5 , then P 4 may send said report R 2 to P 5 via the Internet or said cellular network.
14. The method of claim 1 , wherein a user of a peer-device P 6 is allowed to limit total energy E of P 6 allocated to search for a specified life-time T, wherein:
(a) said peer-device P 6 divides said specified life-time T into cycles;
(b) said peer-device P 6 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 P 6 ; and
(c) said peer-device P 6 stops transmission, receiving, and listening on behalf of search when energy consumed by search at P 6 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.