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