On the topology of wireless sensor networks

Abstract—In this paper, we explore methods to generate optimal network topologies for wireless sensor networks (WSNs) with and without obstacles. Specifically, we investigate a dense network with n sensor nodes and m = nb (0 < b < 1) helping nodes, and assess the impact of topology on its throughput capacity. For networks without obstacles, we find that uniformly distributed sensor nodes and regularly distributed helping nodes have some advantages in improving the throughput capacity. We also explore properties of networks composed of some isomorphic sub-networks. For networks with obstacles, we assume there are M = (nv) (0 < v 1) arbitrarily or randomly distributed obstacles, which block cells they are located in, i.e., sensor nodes cannot be placed in these cells and nodes ’ communication cannot cross them directly. We find that the overall throughput capacity is bounded by the transmission burden in areas around these blocked cells and introduce a novel algorithm of complexity O(M) to generate optimal sensor nodes ’ topologies for any given obstacles ’ distributions. We further analyze its performance for regularly distributed obstacles, which can be taken to estimate the lower bound of the algorithm’s performance. I