Therefore, we have
E[fQ] = (2k??’1)2
m2 (10k ??’ 2) + 8k
m2 (8k ??’ 1) < 5m.
The proof is then finished.
We now consider the case where the network graph is an (m?—m) hexagonal
grid.
Theorem 3.2 The expected value of fQ is E[fQ] < 68m/9.
247 Chapter 10 Location Service, Info. Dissemination and Object Tracking
Dan-Dan Liu and Xiao-Hua Jia
S
Fig. 6. Performances in a hexagonal grid.
Proof. Note that there are (2m??’1) rows. The total number of nodes in the
network is (Figure 6):
Pm
i=2(2m ??’ i) + (2m ??’ 1) = 3m2 ??’ 3m + 1.
It is easy to find that when the source node s is located inside the grid and
at the column having (2m ??’ i) nodes, the number of nodes that are required
to forward the message is
fQ = 6(m ??’ 1) + (2m ??’ i ??’ 1) = 8m ??’ i ??’ 7, for i =1, 2,. . ., m;
and when the source node s is located at the boundary of the grid, the
number required is fQ = 6m ??’ 7. Thus we have
E[fQ] = 1
3m2
??’3m+1[6(m ??’ 1)(6m ??’ 7)
+2Pm??’1
i=1 (2m ??’ i ??’ 2)(8m ??’ i ??’ 7) ??’ (2m ??’ 3)(8m ??’ 8)] < 68m/9.
The proof is then finished.
From the above theorems, we can see that the quorum-based protocol
needs only O(???n) nodes to forward messages in grids, where n is the total
number of nodes inside the network. They achieve significant energy savings
when compared with the classic flooding, which requires O(n) nodes.
ii. Hop Counts of Generated Paths
Similarly, let??™s first consider the case where the network graph is the
(m?—m)-grid (Figure 5), and for the easy presentation, let m=2k+1.
Pages:
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405