Theorem 3.3 The expected value of hQ is E[hQ] < 4m/3.
Proof. Clearly, there are a total of m2(m2??’1)/2 possible pairs of source and
querying nodes. Note that given any, the quorum-based protocol produces a
shortest path between them. Let f(m) be the sum of hop counts of the shortest
paths between all node pairs in an (m?—m)-grid. By solving a set of six linear
equations, we can obtain
f(m) = (2m5 ??’ 16m4 + 94m3 ??’ 620m2 + 1404m ??’ 864)/3.
Therefore, we have E[hQ] = 2f(m)/m2(m2 ??’ 1) < 4m/3.
248
The proof is then finished.
Now consider the case where the network graph is an (m?—m) hexagonal
grid (Figure 6). Using the same analysis method of Theorem 3, we can prove
the following theorem.
Theorem 3.4 The expected value of hQ is E[hQ] < 41m/45.
Proof. Clearly, there are a total of 3m(m??’1)(3m2 ??’3m+1)/2 possible pairs
of source and querying nodes. f(m) is defined as above. We then can obtain
f(m) = m(82m4 ??’ 205m3 + 200m2 ??’ 95m ??’ 18)/20.
Therefore we have E[hQ] < 41m/45.
The proof is then finished.
3.3 Other Quorum Methods
Aydin and Shen [37] proposed a match-making method in ad hoc and WSNs
for producers and consumers to forward their ADV/SUB without flooding
(SUB for data SUBscription, which is similar to REQ). The quorum system is
constructed in a di?®erent way. Each ADV and SUB spreads along four main
sections (east, west, north and south) as defined by a threshold angle. The size
of each quorum is related to the density of networks and the threshold angle.
Pages:
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406