Music Information Retrieval in P2P Networks - Intelligent Music Information Systems: Tools and Methodologies - page 212

by R educed representation with T Transcoding) and
is illustrated in Figure 5.

changed their location, others have switched
off, and some new ones have become reachable.
The MHs that are greyed are the ones that were
included in the forward path too, whereas the
rest are new ones that were involved only in the
backward phase.
With the global-counter (GC) policy, when
selecting the MHs to route back the answer-set,
GC tries to follow the MHs included in the forward
path. However, to overcome problems from the
alteration of the MANET (like the disappear-
ance of P 4 in this example), it allows an amount
of discrepancy by resorting to broadcasting. To
control the discrepancy, and thus the backward
traffic, it uses the value of e . Notice that with a
very large e , GC resorts to broadcasting for a very
large number of times, thus becoming equivalent
to the simplistic policy used by the ML searching
algorithm. In contrast, with a very small e , the
querier may not become reachable, especially
when the MANET changes very fast.
A variation of GC works as follows. After a
discrepancy, when a MH from the path has been
reached again, h is reset to its initial value. In
the previous example, when P 3 is reached again,
available hop is reset to 6 (initial value). Thus, h
acts as a decreasing local counter, because it is
reset independently at several MHs. For this reason
this policy is denoted as local-counter (LC). Its
objective is to increase the probability of reaching
the querier, by rewarding the identification of the
forward path. Nevertheless, this can increase the
backward traffic.

routing policies for the Backward
phase

Accordingly, Karydis et al. (2006) describe
three policies for routing the answer-sets in the
backward phase. The first two policies (global
and local counter) are based on existing methods
(Castaneda, Das, & Marina, 2002). As mentioned,
all policies try to select nodes that were included
in the path during the forward phase. Neverthe-
less, the backward phase cannot be based only on
such nodes. Due to the mobility of MHs, it may
be impossible to reach the querier unless other
MHs (not included in the path) are additionally
involved. The objective of all policies is to control
the number of involved MHs so as to reduce back-
ward traffic. These policies constitute a hybrid
approach between probabilistic broadcasting,
where the broadcasting decision is completely
local to each mobile host and the deterministic
broadcasting which relies on the discovery of
some form of connected dominating set (Lou &
Wu, 2004).

Global and Local Counter Policies

To clarify the description of the first two policies,
consider the example of Figure 6a, which depicts
the path from MH P 1 to MH P 6 , which was fol-
lowed in the forward phase. Figure 6b depicts
the routing of the answer-set from P 6 back to P 1 .
Comparing the two phases, several MHs have

Critical Mass Policy

With the critical-mass (CM) policy, if at least a
number, denoted as critical-mass factor ( CMF ),
of the current neighbors was in the forward path,
they are selected as the only ones to propagate the
answer-set. If their number is less than CMF , then
some of the current neighbors (not in the path) are
additionally randomly selected in order to have
at least CMF MHs to propagate the answer-set.

Figure 6. Propagation in a MANET: (a) forward
phase, (b) backward phase.