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