Connectivity in sensor networks

Let’s assume that we have a square area of dimensions DxD, and that in it we randomly distribute nodes. Let’s for now assume that the nodes are uniformly distributed over this square area. Two nodes are assumed to be ‘connected’ to each other if the channel gain between them is above a certain threshold. If the channel gain falls off as d^-g, where d is the distance between the two nodes and g is the path loss exponent, then there is a radius r that defines a circle of connectivity around each node. So for our randomly placed nodes, some are connected and some are not, thus creating a graph. The question that we want to answer is the following: how many nodes should there be in our square area, so that there is the graph is fully connected, i.e. so that there is a path from any node to any other node (or at least mostly connected)? It turns out that the answer to this problem exists, depends on g and the required threshold and can be found via simulations.

The advanced problem that we are going to address is similar to the one described above, except that now the connectivity area around each node is no longer a regular shape (a circle), but rather an irregular shape due to the combined effect of pathloss AND shadowing. The question now becomes: in the existence of shadowing how many more nodes should there be in our square area to guarantee connectivity?

This problem relates to the more complicated mathematical problem of percolation. We pursue the topic theoretically as well as via simulations.

Although we are describing the topic at an abstract level, it is a real life issue in sensor networks.