Stuff Yaron Finds Interesting

Technology, Politics, Food, Finance, etc.

A quick and dirty way to calculate endpoints needed for forming a mesh with radios

I needed to figure out how many Wifi endpoints which had a range of around 300 feet would be needed to form a mesh that covers a square mile. I do a bunch of 1/2 baked math below to estimate that 138 endpoints would be needed for complete coverage.
For some work I’m doing I needed to know how many Wifi endpoints I needed to cover an area. But since I’m trying to mesh these endpoints to form a network I have to make sure that all the circles overlap so they can “see” each other.
Right off these kind of calculations are nonsense. In the real world, even assuming we are talking about external endpoints (e.g. not in buildings) we have to deal with issues of elevation, building interference, even weather effects on radio propagation. So I wasn’t overly worried about accuracy since the whole approach is silly. I’m just looking for an order of magnitude idea of how many Wifi endpoints would be needed.
This problem translates to figuring out how many circles of a uniform diameter are needed to completely cover a square and overlap each other (I decided to measure things in square miles or square kilometers). This turns out to be a very difficult problem to find the optimal answer to.
So instead one can cheat and translate this to the problem of how many hexagons whose diagonal equals the diameter of the circle are needed to cover the square. The reason this works is because the circles that are inscribed on the outside of the hexagon will overlap each other and thus be able to form a mesh. The result is obviously not optimal but it’s a reasonable approximation given all the other nonsense going on here.
The next challenge is that I’m trying to measure coverage over a square but Hexagonal tessellations do not form straight edges. But again, we can cheat and be less accurate.
When measuring the vertical axis things are a bit easier. Hexagons do stack rather nicely. So we can measure the vertical distance as being exactly H*Nv where H is the horizontal size of the Hexagon and Nv is the number of Hexagons on the vertical. This means that the hexagons in the next interior vertical row will cover extra area (equal to the size of 1/2 a hexagon on the top and bottom) but such is life with Hexagons (or circles, at least if you don’t use fancier packing techniques).
Measuring the horizontal axis is trickier. This is because if you stack your hexagons vertically then they won’t stack nicely horizontally. Also the math for the vertical calculation explicitly assumes that if the left most vertical column will, if there is a second column, be followed by a column with Nv + 1 members. This means that each vertical row alternates. The first contains Nv and the second Nv + 1 and the third back to Nv and so on.
If we require an even number of vertical rows and we ignore the edge rows for the moment then we can measure horizontal distance covered in units of two. The first hexagon can be said to cover, horizontally, D for the diagonal of the hexagon plus S for the side (of the second Hexagon). There is still some length left over in the remaining triangle but in order not to double count we will ignore it and allocate that space to the next column. So for every two hexagon rows we cover a horizontal area equal to D+S.
We now have to compensate for the fact that both the farthest left hexagon and the farther right hexagon will be outside of the square. Because of how we measure horizontal distance covered we can ignore the farthest right hexagon because we anyway don’t count for the triangle that sticks out in our normal calculations. So we only need to worry about the farthest left hexagon. There we have to remove the length I call R. This is the height of the triangle that sticks out beyond the square area. We can calculate this length as R2 + ((H)/(2))2 = S2 where R is the height of the triangle we are trying to solve for. So this then gives us R = (S2 − ((H)/(2))2). So we have to subtract R from the length we covered.
If there are an odd number of rows then we treat the width of the last odd row as covering S.
So to summarize:
Vertical CoverageH*NV
Horizontal Coverage (if even number of vertical rows)(D + S)*(NH)/(2) − R
Total number of hexagons in the grid (if even number of vertical rows)(NH*(2NV + 1))/(2)
Horizontal Coverage (if odd number of vertical rows)(D + S)*((NH − 1))/(2) − R + S
Total number of hexagons in the grid (if odd number of vertical rows)((NH − 1)*(2NV + 1))/(2) + NV
Where:
H Height of the hexagon
NH Number of hexagons on the horizontal
D Diagonal length of the hexagon
S Length of a side of the hexagon
R Length of the base of the triangle formed in a hexagon, equal to (S2 − ((H)/(2))2)
NV Number of hexagons along the vertical axis
I find this website useful for visualizing and calculating the measurements of a Hexagon.
Now to solve my problem. Let’s say that a Wifi endpoint outside gets about 300 feet of range which gives us a circle with a diameter of 600 feet. Mapping the circle to a hexagon means that the diagonal D of the hexagon equals 600 feet. Which using the previous website tells me that the height H is 519.6 feet. So 519.6*NV = 5280 so therefore NV = (5280)/(519.6) = 10.16 and since I can’t have 0.16 of a Wifi endpoint I’ll round up and say 11 Wifi endpoints on the vertical.
For the horizontal I need to calculate R which is (3002 − ((519.6)/(2))2) = 150. So assuming an even number of horizontal rows then the length we will cover is (600 + 300)*(NH)/(2) − 150 = 5280 so NH = 12.06. We can also test what would happen if we used an odd number of rows. (600 + 300)*(NH − 1)/(2) − 150 + 300 = 5280 so NH = 12.4 which since we know NH in this case is supposed to be odd we know we have to actually round up to 13. So we should use an even number of rows, in this case, 12.
So the total number of Wifi endpoints we would need to cover a square mile is (12*(2*11 + 1))/(2) = 138.

One Response to A quick and dirty way to calculate endpoints needed for forming a mesh with radios

  1. Pingback: Building local Internet infrastructure for disadvantaged communities |

Leave a Reply

Your email address will not be published. Required fields are marked *