Practical 19: Sensor Network Deployment and Coverage Analysis
Chapter Twenty-Two
Syllabus topic Module 2, "Wireless Sensor Network Deployment and Coverage Analysis: Simulate random and grid deployment of sensor nodes and evaluate network coverage and connectivity."
Pages 202 to 207 of 232
Aim
To simulate grid and random deployments of sensor nodes in a field, and to evaluate how much of the field each covers with its sensing range and how many sensors each can connect to the sink over radio links.
What you need to know before you start
Two ranges. A sensor has a sensing range, how far away it can detect an event, and a radio range, how far its packets reach. They are different: a temperature sensor senses the air a few metres around it but its radio reaches hundreds of metres. This practical uses a sensing radius of 100 m and NS-2's radio range of 250 m.
Coverage is the fraction of the field within sensing range of at least one sensor. An event in an uncovered spot is never seen. Connectivity is whether each sensor has a chain of radio links, each within radio range, to the sink that collects the readings. A sensor that is not connected sees events and cannot report them.
Grid deployment places sensors in a regular square pattern, as a planned installation would. The weakest spot of a square grid is the centre of each square, equally far from its four corners: half the square's diagonal, the spacing divided by the square root of 2, 1.414. So a grid covers everything if its spacing is at most 1.414 × the sensing radius: 141.4 m for a 100 m radius.
Random deployment scatters sensors, as dropping them from the air would. Some spots end up covered many times over and others not at all. For sensors scattered at random with density λ per square metre, the fraction of a large field left uncovered is about e^(-λπR²), so the coverage is about 1 - e^(-λπR²), for sensing radius R.
Step 1: the simulation
coverage.py works on a 1000 m square field with the sink at its centre. It measures coverage on 40,000 points 5 m apart, and connectivity by following radio links outwards from the sink. For random deployment it averages ten seeded deployments.
# coverage.py: grid against random deployment of sensors: how much of the field they sense, and
# how many of them can reach the sink at the centre over radio links
import math
import random
SIDE = 1000.0 # a 1000 m by 1000 m field
SENSE = 100.0 # sensing radius, m
STEP = 5.0 # coverage is measured on points 5 m apart
SINK = (500.0, 500.0)
POINTS = [(x * STEP + STEP / 2, y * STEP + STEP / 2)
for x in range(int(SIDE / STEP)) for y in range(int(SIDE / STEP))]
def grid(k):
s = SIDE / k
return [(s / 2 + i * s, s / 2 + j * s) for i in range(k) for j in range(k)]
def scattered(n, seed):
r = random.Random(seed)
return [(r.uniform(0, SIDE), r.uniform(0, SIDE)) for _ in range(n)]
def uncovered(nodes):
"""How many of the 40000 measuring points no sensor is within sensing range of."""
return sum(1 for p in POINTS if not any(math.dist(p, s) <= SENSE for s in nodes))
def covered(nodes):
return 1 - uncovered(nodes) / len(POINTS)
def reach_sink(nodes, radio):
"""How many sensors have a chain of radio links, each at most `radio` long, to the sink."""
everyone = [SINK] + nodes
seen, todo = {0}, [0]
while todo:
a = todo.pop()
for b in range(len(everyone)):
if b not in seen and math.dist(everyone[a], everyone[b]) <= radio:
seen.add(b)
todo.append(b)
return len(seen) - 1
for k in (8, 7, 6):
u = uncovered(grid(k))
print('grid %d x %d = %d sensors, %.1f m apart: %5d of %d points uncovered, covered %.2f %%'
% (k, k, k * k, SIDE / k, u, len(POINTS), 100 * (1 - u / len(POINTS))))
print(' a grid covers everything if its spacing is at most sqrt(2) x %.0f m = %.1f m' % (SENSE, math.sqrt(2) * SENSE))
for n in (64, 147):
cov = [covered(scattered(n, seed)) for seed in range(1, 11)]
print('random, %d sensors, ten deployments: covered %.1f %% on average (%.1f to %.1f)'
% (n, 100 * sum(cov) / 10, 100 * min(cov), 100 * max(cov)))
density = n / SIDE ** 2
print(' formula 1 - e^(-density x pi x R^2): %.1f %%' % (100 * (1 - math.exp(-density * math.pi * SENSE ** 2))))
for radio in (250, 130):
reach = [reach_sink(scattered(64, seed), radio) for seed in range(1, 11)]
print('radio range %d m: grid sensors reaching the sink %d of 64; random %.1f of 64 on average (fewest %d)'
% (radio, reach_sink(grid(8), radio), sum(reach) / 10, min(reach)))
print('random deployment 1, positions in m:')
r1 = scattered(64, 1)
for i in range(0, 64, 8):
print(' ' + ' '.join('%3.0f,%3.0f' % p for p in r1[i:i + 8]))Practical 19: Sensor Network Deployment and Coverage Analysis
$ python3 coverage.py
grid 8 x 8 = 64 sensors, 125.0 m apart: 0 of 40000 points uncovered, covered 100.00 %
grid 7 x 7 = 49 sensors, 142.9 m apart: 12 of 40000 points uncovered, covered 99.97 %
grid 6 x 6 = 36 sensors, 166.7 m apart: 1984 of 40000 points uncovered, covered 95.04 %
a grid covers everything if its spacing is at most sqrt(2) x 100 m = 141.4 m
random, 64 sensors, ten deployments: covered 83.8 % on average (79.8 to 88.3)
formula 1 - e^(-density x pi x R^2): 86.6 %
random, 147 sensors, ten deployments: covered 98.3 % on average (97.1 to 99.1)
formula 1 - e^(-density x pi x R^2): 99.0 %
radio range 250 m: grid sensors reaching the sink 64 of 64; random 63.8 of 64 on average (fewest 62)
radio range 130 m: grid sensors reaching the sink 64 of 64; random 23.0 of 64 on average (fewest 6)
random deployment 1, positions in m:
134,847 764,255 495,449 652,789 94, 28 836,433 762, 2 445,722
229,945 901, 31 25,541 939,381 217,422 29,222 438,496 233,231
219,460 290, 21 838,556 642,186 993,860 121,333 721,711 936,422
830,670 303,588 882,846 505,589 35,243 797,414 173,549 703,674
375,439 508,778 521,393 490, 30 43,703 983,593 394,170 502,982
771,540 860,232 514,952 578,459 269,548 957, 6 784,820 886,741
809,519 561,426 56,870 570,200 505,485 357,346 538,623 612,458
28,230 177,584 861,798 797,816 255,842 673, 83 17, 15 756,250Practical 19: Sensor Network Deployment and Coverage Analysis
Figure 22.1 The same 64 sensors, in a grid and scattered at random
The grid rule holds exactly at its threshold. At 125 m spacing, below the 141.4 m limit, not one of the 40,000 points is uncovered. At 142.9 m, just above it, 12 points are: the centre of each square of four sensors is half a diagonal from all four, 142.9 m divided by the square root of 2, which is 101.0 m to one decimal place, just beyond the 100 m radius, and leaves a hole a few metres across. At one decimal place those holes would have read as 100.0 per cent, which is why the program counts points. At 166.7 m the holes are large: 1984 points, nearly 5 per cent of the field.
Random deployment wastes sensors. The same 64 sensors covered only 83.8 per cent of the field on average, and as little as 79.8 per cent: where sensors fall close together they sense the same ground twice, and elsewhere they leave gaps. To reach about 99 per cent at random takes 147 sensors, more than twice the grid's 64 for complete coverage.
The formula is close, and a little high. For 64 sensors it predicts 86.6 per cent against 83.8 measured, and for 147, 99.0 against 98.3. The formula assumes a field without edges; in a real one, a sensor near the edge senses partly outside the field, where coverage counts for nothing, so the measured coverage is lower. The figure shows it: the white gaps gather at the edges.
Connectivity follows the same pattern, more sharply. With NS-2's 250 m radio range, almost every sensor could reach the sink either way: all 64 in the grid, 63.8 on average when scattered. With a 130 m radio range, just over the grid's 125 m spacing, the grid still connected all 64, because every sensor has neighbours exactly 125 m away in four directions; the scattered sensors connected only 23.0 on average, and in the worst deployment 6. A random field needs radio ranges well above its average spacing to stay connected; a grid needs only its spacing.
Practical 19: Sensor Network Deployment and Coverage Analysis
Procedure
- Write
coverage.py: a 1000 m field, sensing radius 100 m, the sink at the centre, coverage measured on 40,000 points, connectivity by following radio links from the sink. - Measure the coverage of 8 by 8, 7 by 7 and 6 by 6 grids, and compare their spacings with 1.414 × the sensing radius.
- Measure the coverage of 64 and of 147 randomly placed sensors over ten deployments each, and compare it with the formula 1 - e^(-λπR²).
- Count the sensors that can reach the sink, for the grid and the random deployments, with radio ranges of 250 m and 130 m.
- Draw the grid and one random deployment with their sensing disks.
Observations
| Deployment | Sensors | Coverage | Sensors reaching the sink, 250 m radio | Same, 130 m radio |
|---|---|---|---|---|
| grid, 125.0 m apart | 64 | 100.00 % | 64 | 64 |
| grid, 142.9 m apart | 49 | 99.97 % (12 of 40,000 points uncovered) | ||
| grid, 166.7 m apart | 36 | 95.04 % | ||
| random, ten deployments | 64 | 83.8 % (79.8 to 88.3); formula 86.6 % | 63.8 on average, fewest 62 | 23.0 on average, fewest 6 |
| random, ten deployments | 147 | 98.3 % (97.1 to 99.1); formula 99.0 % |
Result
Grid and random deployments of sensors were simulated in a 1000 m field with a 100 m sensing radius and a 250 m radio range. A square grid covered the whole field whenever its spacing was at most 1.414 × the sensing radius, 141.4 m: at 125 m nothing was uncovered, at 142.9 m small holes appeared at the centres of the squares, and at 166.7 m 5 per cent of the field was uncovered. The same 64 sensors placed at random covered 83.8 per cent on average, a little below the formula 1 - e^(-λπR²)'s 86.6 per cent because the formula ignores the field's edges; random placement needed 147 sensors for about 99 per cent. Connectivity differed even more at a short radio range: at 130 m the grid still connected all 64 sensors to the sink and random deployments only 23 on average.
Where marks are lost
Confusing the two ranges. Coverage depends on the sensing range, connectivity on the radio range. State both.
Rounding away the holes. A grid just over the 1.414 × R spacing leaves holes too small to change a one-decimal percentage. Count uncovered points, or give more decimals.
Trusting the formula at the edges. 1 - e^(-λπR²) is for a field without edges; in a finite field it predicts more coverage than there is.
Judging random deployment by one throw. Coverage ranged from 79.8 to 88.3 per cent across ten deployments of the same number of sensors. Average several, and give the range.
Practical 19: Sensor Network Deployment and Coverage Analysis
Assuming coverage implies connectivity. A field can be well covered and badly connected: at a 130 m radio range the scattered sensors covered as much as before but most could not reach the sink.
For the journal
Write: aim; sensing range and radio range; coverage and connectivity; grid and random deployment; the grid rule, spacing at most 1.414 × R, with the reason; the random-coverage formula; coverage.py and its output; the figure; the grid rule checked on both sides of its threshold; the formula against measurement, and the edge effect; connectivity at two radio ranges; observations; result.
Quick revision
- Sensing range: how far a sensor detects events. Radio range: how far its packets reach.
- Coverage: the share of the field within sensing range of some sensor. Connectivity: whether each sensor has a chain of links to the sink.
- A square grid covers everything if its spacing is at most 1.414 × R: the square's centre is spacing ÷ 1.414 from its corners.
- Random coverage is about 1 - e^(-λπR²); lower in a real field, because of its edges.
- Here: grid 64 sensors, 100 %; random 64, 83.8 %; random needs 147 for about 99 %.
- Connectivity at 130 m radio: grid 64 of 64; random 23.0 of 64.
- Count uncovered points, and average several random deployments.
Questions you must be able to answer
1. What is the difference between coverage and connectivity? Coverage is whether every part of the field is within sensing range of some sensor, so that events there are detected. Connectivity is whether every sensor has a chain of radio links to the sink, so that what it detects is reported.
2. Why must a square grid's spacing be at most 1.414 × the sensing radius to cover everything? The point furthest from any sensor is the centre of each square of four sensors, at half the square's diagonal, spacing ÷ 1.414, from all four. It is covered only if that distance is at most the sensing radius.
3. The 7 by 7 grid, 142.9 m apart, covered 99.97 per cent. Where were the holes, and why so small? The centre of each square is half a diagonal from its four sensors, 101.0 m to one decimal place, just over the 100 m radius. Only the few metres around each centre are beyond every sensor's reach.
4. Why did 64 randomly placed sensors cover less than 64 in a grid? Scattered at random, some sensors fall close together and sense the same ground twice, and some parts of the field are left with none. A grid spreads them so that overlaps are small and every point is reached.
Practical 19: Sensor Network Deployment and Coverage Analysis
5. What does the formula 1 - e^(-λπR²) predict for 64 sensors, and why was the measurement lower? 86.6 per cent. The formula assumes a field without edges; in a real field, sensors near the edge sense partly outside it, so less of the field is covered: 83.8 per cent on average.
6. How many randomly placed sensors does the formula say are needed for 99 per cent coverage, and how many does a grid need for 100? 147 at random, against 64 in a grid 125 m apart.
7. Why did the grid stay connected at a 130 m radio range when the random deployments did not? Every grid sensor has neighbours exactly 125 m away, within 130 m, in four directions, so a chain of links reaches every sensor. Scattered sensors have neighbours at all distances, and many had none within 130 m, which cut them, and everyone beyond them, off from the sink.
8. Why average ten random deployments? Because one deployment can be unusually good or bad: coverage ranged from 79.8 to 88.3 per cent across the ten. The average and the range describe random deployment; a single throw does not.
9. When would you still deploy sensors at random? When the field cannot be reached to place them by hand, for instance dropped from the air over a forest or a disaster zone. Then more sensors must be deployed, as the formula shows, to reach the coverage a grid would give.
10. Can a field be well covered and poorly connected? Yes. With a 130 m radio range the scattered sensors covered the field as before, but on average only 23 of the 64 could report to the sink.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.