## 3 Routing algorithms based on sensor position
### Grid-based routing
Each cell is an \(\alpha\)*\(\alpha\) square. A source itself is at one crossing point of the grid and propagates the parameters (\(\alpha\)) in the whole field. The other dissemination points can be calculated based on the simple equation: \(\{x_{i}\)=\(x\)+\(i\)*\(\alpha\); \(y\)=\(y\)+\(j\)*\(\alpha\); \(i\),\(j\)=\(\ldots\),-3, -2, -1, 0, 1, 2, 3,...\(\}\). The source sends a data-announcement message to its four dissemination points (\(L_{p}\)) and the neighbor node continues forwarding the data announcement message in a similar way till the message stops at a node that is closer to \(L_{p}\) than all its neighbors. If this node's distance to \(L_{p}\) is less than a threshold \(\alpha\)/2, it becomes a dissemination node serving \(L_{p}\) for the source. The data announcement message is recursively propagated through the whole sensor field so that each dissemination point on the grid is served by a dissemination node. Figure.19 shows a grid constructed by a source \(B\). It should be pointed out that the crossing points of two blue lines are virtual and the black nodes around crossing points are the dissemination nodes. Another key problem is how to maintain the grid structure. TTDD uses the _Grid Lifetime_ to control the maintaining time. The data announcement message includes Grid Lifetime. So, _Grid Lifetime_ is known by the dissemination nodes when the grid is built. If the lifetime elapses and the dissemination nodes do not receive any further data announcements to update the lifetime, they clear their states and the grid no longer exists. Proper _grid lifetime_ values depend on the data availability period and the mission of the sensor network. After the grid is constructed, the whole data forwarding process can be described as follows. The sink floods its query within a cell and only sensors located at grid points need to acquire the forwarding information. When the nearest dissemination node for the requested data receives the query, it forwards the query to its upstream dissemination node toward the source, which in turns further forwards the query, until it reaches either the source or a dissemination node that is already receiving data from the source. This query forwarding process lays information of the path to the sink, to enable data from the source to traverse the same two tiers as the query but in the reverse order. Combining the grid structure and curve-based routing idea, [PERSON] _et al._ proposed the grid-based routing algorithms (GBRA) [50; 51]. The algorithm is used to the static WSN, where the source and sink are fixed. The algorithms can be divided into several stages: the local topology built stage (LTBS), grid built stage (GBS), path constructed stage (PCS), density controlled stage (DCS) and data forwarded stage (DFS). In LTBS, the main purpose of this stage is to build a neighbor table (NT) through finding the direct neighbors of each node. Once node is scattered, the node will send topology finding packets (TFP) three times during a certain period. In GBS, the aim is to divide the network into grid with suitable size similar to TTDD and let each node know which grid it belongs to, shown as Figure.21. Meanwhile,relational information (location and data type needed) about sink is distributed. In Figure.21, \((x,y)\) is a theoretic point and the service node (\(SN\)) of \((x,y)\) is selected. For each vertex, two \(SN\) are selected. \(SN\) only deals with those packets coming from the same grid and ignores those coming from neighbor grid. In PCS, the aim of this stage is to construct a path across one single grid from one SN to another SN based on curve routing algorithm, which is described in [45]. Based on CBGR, two theoretic vertexes and a randomly node are selected as control points in PCS. Because two vertexes are neighbor, one vertex can induce the other vertex. In DCS, the aim is to make redundant nodes sleep, shown as Figure.22. In Figure.22, the black nodes are working and the gray nodes are sleeping. The node on the path (named Initiating Node, \(IN\)) is working node.