Information Technology Reference
In-Depth Information
Node Density vs Average Hop Count for Different Topologies
14
Dijkstra
Greedy algorithm (UDG)
Prob a l g orithm (sgma = 0)
P ro b algorithm (sgma = 6)
Prob algorithm (sgma = 8)
13
12
11
10
9
8
7
6
6
8
10
12
14
16
18
20
22
24
26
Node Density
Fig. 7.16 Average hop count against node density for Dijkstra's algorithm, the UDG-based greedy
routing and the probabilistic progress localized greedy routing on model employing a realistic
physical layer for different values of
σ , and with a correlation length of 150 m ( y = 2.45)
dB
The performance of the Dijkstra-based algorithm, and greedy algorithm applied
on the UDG and the partially physically “realistic” model with no shadow fading
can be seen to be comparable throughout.
For values of y significantly greater than 1, a narrow range of average local node
densities 10
0 dB
dB
σ≥ , we observe a statistically significant reduction
in the average hop length of approximately 30%. For values of y significantly less
than 1, we observe a slightly reduced advantage and only for
<< and
15
8dB
dB
σ≥ .
The most important observation though, is that for y = 1 and
8dB
dB
σ≥ , we
observe a consistent reduction in the average hop count of approximately 35-40%
for all values of average local node density in the simulated range of 9
8dB
dB
≤κ≤ .
Under these circumstances we can claim with some confidence that the probabi-
listic progress localized routing algorithm with a realistic propagation model
incorporating correlated shadow fading is capable of making next hop decisions
that offer substantial performance improvements.
This observation can be plausibly explained in the following terms: Large but
typical values of
26
σ≥ result in a ppr = 0.5 contour “amoeba” that has “long
legs.” Provided the typical width y and average local node density are such that
these pronounced “legs” are only just populated by neighboring nodes with a
sufficiently high probability, the probabilistic localized routing algorithm will
select such next hop neighbours consistently, resulting in significantly shorter end-
to-end path hop counts. To support, clarify, and quantify this statement, further
theoretical and simulation work is being pursued.
8dB
dB
Search WWH ::




Custom Search