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

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*N_v where H is the horizontal size of the Hexagon and N_v 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 N_v + 1 members. This means that each vertical row alternates. The first contains N_v and the second N_v + 1 and the third back to N_v 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 R² + ((H)/(2))² = S² where R is the height of the triangle we are trying to solve for. So this then gives us R = √(S² − ((H)/(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:

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*N_V = 5280 so therefore N_V = (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 √(300² − ((519.6)/(2))²) = 150. So assuming an even number of horizontal rows then the length we will cover is (600 + 300)*(N_H)/(2) − 150 = 5280 so N_H = 12.06. We can also test what would happen if we used an odd number of rows. (600 + 300)*(N_H − 1)/(2) − 150 + 300 = 5280 so N_H = 12.4 which since we know N_H 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.