Tessellating Cell Shapes for Geographical Clustering

This paper investigates the energy-saving organization of sensor nodes in large wireless sensor networks. Due to a random deployment used in many application scenarios, much more nodes need to be deployed to achieve a complete sensor coverage than theoretically needed in case of an ideal deployment. Consequently, most of the deployed nodes are redundant and can be switched-off for a long time to save energy. A well-known principle to detect the redundancy of nodes is to divide sensor network into equally sized cells. Assuming a well chosen cell size, depending on transmission range and sensing range, it is possible to switch-off all nodes but one per cell. The idea was applied in the extended geographic adaptive fidelity algorithm (XGAF), which divides the network into virtual square cells. In the current work, we improve the idea of XGAF by using different tessellating cell shapes, namely triangles, pentagons and hexagons. Furthermore, we examine the cell shapes in terms of coverage, connectivity and average hop count.