Performance Analysis of Quorum System
Authors in [28] also studied the e?±ciency of the quorum method through
some mathematical analysis in two special network topologies, the (m?—m)-
grid and (m?—m)-hexagonal grid. Both topologies are very popular in wireless
communications, where many ad hoc networks or randomly deployed sensor
246
networks can be approximated by grid or hexagonal topologies. Two performance
metrics are evaluated: 1) The number of nodes that are required to
forward an ADV/REQ, denoted by fQ; 2) The hop counts of the route between
the source node and querying node, denoted by hQ. The hop counts
indicate the distance data would travel. Each node in the network is supposed
to have the same independent possibility to disseminate and inquire about
the information.
i. Numbers of Forwarding Nodes
We first consider the case where the network graph is an (m?—m)-grid, and
for easy presentation, let m=2k+1.
S
Fig. 5. Performances in a grid.
Theorem 3.1 The expected value of fQ is E[fQ] < 5m.
Proof. The message is transmitted to both north and south directions in parallel
and stops after traversing along the boundary under non-duplicated face
routing (Figure 5). It is easy to find that when the source node s is located
inside the grid, the number of nodes required to forward the message is
fQ = (2k ??’ 2) + 2(2k ??’ 1) + 2(2k + 1) = 10k ??’ 2.
When the source node s is located at the boundary of the grid, the number
required is
fQ = 2(2k ??’ 1) + 2(2k + 1) ??’ 1 = 8k ??’ 1.
Pages:
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404