The energy needed for reporting from a sensor to the sink in wireless sensor network is proportional to the average number of hops. In large scale networks, this may become a bottleneck. Mobile sinks reduce the number of hops and, therefore, energy consumption by collecting sensor measurements in their neighborhoods. Sensors route their periodic readings toward the current location of the mobile sink via other sensors in multi-hop fashion. As an example, a human could walk through a sensor network deployment with a mobile phone in hand and gather sensor data in its current vicinity. In another scenario, robots move while performing assigned tasks. Events are detected by sensors and routed toward a nearby robot for actuation. The objective is to enable each sensor to maintain a slow-varying routing next hop to the sink or robot, rather than the precise knowledge of quick-varying sink position.
In this paper, the authors propose a novel localized Integrated Location Service and Routing (ILSR) scheme, based on the geographic routing protocol GFG (greedy-face-greedy, see below), for data communications from sensors to a mobile sink in wireless sensor networks. GFG ensures successful communication as long as a sensor remains connected to the mobile sink. In ILSR, the sink updates location to neighboring sensors after or before a link breaks and whenever a link creation is observed. Location update relies on flooding, restricted within necessary area, where sensors experience (next hop) change in GFG routing to the sink. Dedicated location update message is additionally routed to selected nodes for prevention of routing failure.
Considering both unpredictable and predictable (controllable) sink mobility, the authors present two versions of their scheme and prove that both of them guarantee delivery in a connected network modeled as unit disk graph. ILSR is the first localized protocol that has this property. They further propose to reduce message cost, without jeopardizing this property, by dynamically controlling the level of location update. A few add-on techniques are also suggested to enhance the algorithm performance. They compare ILSR with an existing competing algorithm through simulation. It is observed that ILSR generates routes close to shortest paths at dramatically lower (90% lower) message cost.
On GFG: Bose, Morin, Stojmenovic and Urrutia describing the greedy-face-greedy (GFG) protocol in 1999, as practical routing algorithms that can guarantee delivery of packets in wireless sensor networks, where each node/sensor has the same transmission radius and has only local knowledge (position of immediate neighbors) and accurate position of destination, without memorizing at nodes. GFG was subsequently enhanced (e.g. it was simplified by Frey and Stojmenovic, and a beaconless variant which does not need prior neighbor's knowledge was described later by Ruehrup and Stojmenovic) and applied in many tasks.
GFG makes greedy forwarding decisions. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the face of the region. The recovery is based on the construction of a planar connected subgraph without any communication overhead, and on a routing algorithm that is always successful in planar connected graphs. GFG remains the only known framework for guaranteed delivery of localized memoryless path-based routing, and remains amongst the very few most fundamental protocols in the entire ad hoc and sensor network research domain. GFG has been widely implemented (under the name of its duplication GPSR) and added to most existing simulation tools.