## 3 Routing algorithms based on sensor position
### Grid-based routing  
Grid-based routing algorithms use grid as the basic routing infrastructure. Considering different characteristics of networks, different grid construction methods have been proposed. In [48], grid location service (GLS) is proposed for Ad Hoc routing where the nodes are totally mobile. In [49], two-tier data dissemination (TTDD) grid is constructed for large-scale WSN where multiple sinks are mobile. In [50; 51], a virtual grid (VG) is constructed for routing in WSN where all sensors are static. In grid-based routing algorithms, how to construct and maintain the grid is the key problem. Figure 16: Applications of CBR [44]. GLS is based on the idea that a node maintains its current location information in some location servers distributed throughout the network [48]. GLS provides for distributed location lookups by replicating the knowledge of a node's current location at a small subset of the network's node, which is referred to as the node's location servers. In GLS, grid-based partition is arbitrary and any other balanced hierarchical partition of the space can be used. It is presumed that all nodes know the same global partitioning of the area into a hierarchy of grids with squares of increasing size, as shown in Figure.17. One smallest square is called an order-1 square. Generally, four order-1 squares make up an order-2 square, and so on. Sometimes, a particular order-n square is part of only one order-n+1 square in order to avoid overlap. This maintains an important invariant: a node is located in exactly one square of each size. If square size is increased, fewer location servers are selected for nodes at greater distances. The location servers are not specially designated and are acted by each node. The location servers for a node are relatively dense near the node but sparse farther from node to balance the efficiency and energy consumption. Each node recruits nodes with IDs \"close\" to its own ID to serve as its location  
Figure 17: Global partitioning of the area [48]. Figure 18: The location server of B in different order [48]. servers. The node closest to node, \(X\), in ID space is defined to be the node with the least ID greater than \(X\). A node selects location servers in each _sibling_ of a square that contains the node, as shown in Figure.18. In Figure.18, \(B\) recruits three servers in order-1 squares (28, 2 and 63), three servers in order-2 squares (26, 31 and 43), and three servers in order-3 squares (37, 19 and 20). Once all nodes have provided their coordinates to their location servers, the grid state is complete. If one node (\(S\)) sends the data to the destination (\(D\)), S sends the query to the least node greater than or equal to \(D\) for which \(S\) has location information. The query is forwarded in the same way. Eventually, the query will reach a location server of \(D\), which will forward the query to \(D\). Since the query contains \(S\)'s location, \(D\) can respond directly using geographic forwarding. Although GLS is effective to query and forward data in Ad Hoc, the construction and maintenance of grid is too complicated and not energy-aware to apply to WSN. Sink mobility also brings new challenges to large-scale WSN because the location information of mobile sink's should be continuously updated through the sensor field, such as Directed Diffusion [52] and GRAB [53]. It causes the excessive drain of sensor's limited energy and increases the collisions in wireless link. [PERSON] _et al._ proposed the two-tier data dissemination (TTDD) idea to resolve this problem [49]. There are two tiers: the lower tier is within the local grid square of the sink's current location (called cells), and the higher tier is made of the sensors closest to grid points (called dissemination nodes). Each data source proactively builds a grid structure which enables mobile sinks to continuously receive data on the move by flooding queries within a local cell. In TTDD, the grid is constructed by sources. A source divides the plane into a grid of cells.