# Pido: Predictive Delay Optimization for Intertidal Wireless Sensor Networks
## 4 Design of Pido
### Overview of Pido  
Pido utilizes delays as metric to select routing paths. There are three types of delays in IT-WSNs as explained in Section 3: (1) queuing delay caused by intermittent connections, (2) queuing delay caused by buffer occupancy and (3) transmission delay caused by poor link quality in Section 3. We further summarize delays into node delay (\(nd\)) and link delay (\(ld\)) in Pido. Node delay (\(nd_{j}\)) is the additional delay introduced by node \(j\) individually, and is related to the process capability, buffer condition and future status of node \(j\). The link delay (\(ld_{ij}\)) is related to the link quality from node \(i\) to node \(j\), which reveals the delay cost of transmitting a packet from node \(i\) to node \(j\). We will describe the detail of calculating link delay (\(ld\)) and node delay (\(nd\)) in Section 4.2.  
Figure 3: The expected transmission times distribution in an indoor WSN and an IT-WSN in Zhoushan.  
Pido selects the routing path with the least end-to-end delay and Figure 4 is an example of routing selection in Pido. Figure 4a is a typical network with four nodes and a sink node, and each node attempts to select a routing path to the sink node with the least end-to-end delay. The numbers in circles represent the node delays and the numbers on dash lines are link delays. Figure 4b,c reveal the routing paths for _Node C_ and _Node D_. Both _Node C_ and _Node D_ have three candidate parents, and they select _Node B_ and _Node A_ as parents individually, which have the least end-to-end delay.  
Pido helps nodes to select parents with least end-to-end delays and Figure 5 reveals the mechanism of Pido. We take _Node C_ in Figure 4 as an example.  
* **Step 1:** The node generates a packet at each cycle, and receives packets from children. Packets are stored in a sending queue and sent based on the FIFO (first in first out) rule.
* **Step 2:** When the sending queue is not empty, the node checks the routing table and searches for the best candidate to forward packets.
* **Step 3:** The node then maintains a routing table and updates it with beacons from neighbors.
* **Step 4:** The node activates self-check to calculate the process capability and buffer status, and broadcasts beacons periodically to announce the delay from itself to the sink (\(Min\{C->sink\}+nd_{C}(t)\)) to neighbors.  
Broadcasting beacons can help neighbors to update their routing tables, and the detail of this mechanism is similar with CTP, which can be searched in [16]. Notably, when the buffer is nearly full, _Node C_ then alarms neighbors not to send packets to it by sending beacons with infinite delay. In this way, a node can solve the problem of packet drop caused by overflow effectively in a lightweight method.  
Figure 4: (**a**) the numbers in circles represent the node delays and the numbers on dash lines are link delays; (**b**) the routing path for _Node C_ is: _Node C_->_Node B_->_Sink node_, and the overall delay is 52 cycles; (**c**) the routing path for _Node D_ is: _Node D_ -> _Node A_-> _Sink node_, and the overall delay is 28 cycles.  
Figure 5: The routing selection procedure of _Node C_.