Figure 5 shows how several queries for the same event originating
from di?®erent locations are resolved at di?®erent replicas of that event.
Fig. 5. Illustration of Search with Replication.
We aim to minimize the total expected cost of search and replication for
each event. While there is an energy cost to be paid for moving each replica
of the information to its location, having more replicas reduces the expected
search energy cost. The search energy cost is measured in terms of the total
number of transmissions needed for the query to locate the nearest replica.
We could also account for the number of transmissions needed to return the
response back to the querier by doubling this number, assuming that the
response is returned along the reverse path.
Let us first consider the cost of replication. The expected number of transmissions
required to place each replica at a randomly selected location is the
expected Manhattan distance (i.e., the L1 distance, measured as the sum of
396
R1
R2
R3
Q2
Q1
Q3
R4
Chapter 16 Modeling Data Gathering in Wireless Sensor Networks
the absolute distance in the x-coordinate and the absolute distance in the
y-coordinate) between any pair of nodes in the n ?— n grid. The expected xdistance
is n/3 and the expected y-distance is n/3, hence 2n/3 transmissions
are required on average to place each replica. To place k??’1 replicas, this cost
is then:
Creplication =
2
3
n(k ??’ 1).
Pages:
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628