Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

2.2 GRID PARTITIONING-BASED BACKBONES

A grid partitioning algorithm for backbone construction, called geographical adaptive fidelity (GAF), was proposed by Xu et al. (2001). It assumes that location information is available via GPS, and each node knows its current location relative to other nodes. The algorithm divides the whole area of the network into virtual grids. The virtual grid is defined such that, for any two adjacent grids, any node in one grid can directly communicate with any node in the other grid. That is, all nodes in the same grid are “equivalent” from the routing or broadcasting point of view. Therefore, one representative node from each grid is sufficient to construct a connected backbone.

Suppose r is the size (edge length) of the virtual grid and R is the transmission range. In order to guarantee that any two nodes in adjacent grids can communicate with each other, the following relationship is required: r² + (2r)² ≤ R². Thus, we have .

Geographical adaptive fidelity was further studied by Basagni et al. (2004). This study shows that the backbone constructed by GAF may disconnect the graph. The reason is that nodes are not evenly distributed in the grids. It is very likely for a grid with one or more nodes to be adjacent to one or more empty grids. Two nonadjacent nonempty grids may be connected when all the nodes within them are active. However, particular leaders ...