## 5 The MRLG Routing Protocol
### Formal MRLG Description  
Our routing protocol is optimized to operate under the following assumptions, which are commonly met in our target scenario: (a) the number of sensor nodes does not increase over time; (b) sensor nodes remain at static positions; and (c) the sink is able to move freely throughout the sensed area, without constraints.  
The MRLG protocol distinguishes between three types of neighbor nodes, from the perspective of a particular sensor node: (1) downhill: includes those nodes that are closer to the sink (lower hop count); (2) peers: nodes at the same distance from the sink (similar hop count) and, (3) uphill: nodes further away from the sink (higher hop count). Notice that creating and maintaining the list of downhill, peer and uphill nodes becomes straightforward by listening to the hop count advertised in the messages broadcasted by these nodes, and comparing against the node's own hop count.  
The sequence of actions taken by the MRLG routing algorithm when updating routes is the following:  
(1) Topology updates are triggered by the sink node. Since the sink can be mobile, it periodically sends Route Request (RREQ) messages to announce its presence at a rate that can be adjusted according to its degree of mobility (one second by default). These messages allow nearby sensor nodes to detect any changes in the sink's position, which may trigger a topology reconfiguration as explained below. The first message generated is fully propagated throughout the WSN, allowing the different sensor nodes to generate a vector field of routes pointing towards the sink node.  
(2) Upon listening to the sink's RREQ messages, every sensor node stores the hop count value and the sequence number of the last sink message received; from the set of nodes that share the same (minimal) hop count towards the sink (downhill nodes), it picks one of them as the next-hop for data forwarding. Sensor nodes also store information about other neighbors (both peers and uphill nodes), based on information collected from all overheard messages. In summary, the information stored by each sensor is: <RREQ sequence number, hop count, next_hop, downhill nodes [], peers [], uphill nodes []>.  
(3) After processing RREQ messages, sensor nodes will conditionally rebroadcast them taking into account the hop count and the sequence number, according to Algorithm (2). In this algorithm, RREQ is an object that refers to the Route Request Packet, and Node is an object that refers to the data stored by the sensor itself; both objects contain attributes such as hop_count, which refers to the number of hops towards the sink, and seq_number, which is the sequence number generated by the sink (increases every time). Additionally, RREQ contains the ttl attribute, which refers to the Time-to-Live property, and source, which refers to the address of the sensor that broadcasted the packet. Node objects contain methods such as IsUphill(), to determine if a certain node is stored as an the uphill node, and UpdateNeighborList(), which allows updating the information about neighbor nodes by assigning them to the appropriate list: downhill, peers, or uphill.  
Differently from the CTP protocol, the possibility of discarding RREQ messages most of the times will bring MRLG significant performance gains by avoiding to introduce routing packets in areas where route updates are unnecessary.