## 5 Module I: Anonymity
### Communication Phase
#### 5.3.3 Acknowledgement  
As expected in data networks, message could be lost or could be corrupted. In either case, retransmission is required. Because SNs change PIDs after each transmission, synchronizing PIDs is crucial. Updating the pseudonyms depends on successful message delivery. Ideally, the source should update the pseudonyms only after making sure the BS receives the data. However, the lack of direct connection between the source and the BS makes it a bit complicated process. The BS cannot send direct acknowledgement to the source if it is multiple hops away. We have to depend on multiple acknowledgements along the path between the source and the BS. SN needs to calculate the Acknowledgement pseudonym ID (APIDi) according to Equation (13):  
\[\text{APIDi}=\text{H1}(\text{APIDi}\oplus\text{b}_{\text{i}}) \tag{13}\]  
The message will be sent out to the neighbor with the current value for \(\text{APIDi}\). Thus, we will rewrite \(\text{M}_{\text{i}\rightarrow\text{j}}\) as it appears in Equation (14):  
\[\text{M}_{\text{i}\rightarrow\text{j}}=\text{Padding}\parallel\text{OHPIDi} \mapsto\text{j}\parallel\text{E}_{\text{ki}\rightarrow\text{j}}\left(\text{APIDi }\parallel\text{PIDi}\parallel\text{E}_{\text{ki}\leftrightarrow\text{bs}} \left(\text{D}_{\text{i}}\right)\right) \tag{14}\]  
Padding is added to make sure all the one-hop messages have the same size to prevent _size correlation_ attacks. When SNj receives the message, it will reformat the message as in expression Equation (15) and then send it to SNr:  
\[\text{M}_{\text{j}\rightarrow\text{r}}=\text{APIDi}\parallel\text{OHPIDi} \mapsto\text{j}\parallel\text{E}_{\text{j}\rightarrow\text{r}}\left(\text{ APIDj}\parallel\text{PIDi}\parallel\text{E}_{\text{ki}\leftrightarrow\text{bs}} \left(\text{D}_{\text{i}}\right)\right) \tag{15}\]  
The transmission of \(\text{M}_{\text{j}\rightarrow\text{r}}\) should be heard by all the neighbors including both SNi and SNr. If SNi hears the message and reads (APIDi), the SNi knows that \(\text{M}_{\text{i}\rightarrow\text{j}}\) was received correctly by SNj. Only at this time, SNi updates the value of \(\text{OHPIDi}\mapsto\text{j}\). PIDi will get updated, as well, since SNi is the source of the message. This is exhibited in Figure 4. Here are two scenarios:  
_Scenario 1:_ The packet sent by SNi is lost or got corrupted. In this case, SNj considers nothing happened, so it will not forward any message onward. Meanwhile, SNi will wait for (\(\zeta\)) time to expire. It will send the message again with updated \(\text{APIDi}\). Once the message is acknowledged according to the procedure explained earlier, then PIDi, OHPIDi and \(\text{APIDi}\) will be updated. If it is intermediary SN, only \(\text{OHPIDi}\) and \(\text{APIDi}\) is updated as exhibited in Figure 5.  
_Scenario 2:_ SNj receives the packet correctly; the new packet \(\text{M}_{\text{j}\rightarrow\text{r}}\) is sent out which contains the acknowledgement (APIDi), and SNj updated the value of \(\text{OHPIDi}\mapsto\text{j}\). However, SNi does not hear the forwarded message \(\text{M}_{\text{j}\rightarrow\text{r}}\) within time (\(\zeta\)). At this moment SNi does not know for sure if the message was delivered (_resembles scenario 1_), or the acknowledgement is lost. It has to account for the worst case. A copy of the message will be retransmitted to SNj with the current OHPIDi and updated \(\text{APIDi}\). SNj can recognize the message because of the value of old \(\text{OHPIDi}\). After receiving the _retransmitted_ message, it now sends a direct acknowledgement to SNi as in Equation (16). \[\text{ACKi}_{\text{i}\leftarrow\text{j}}=\text{APIDi}\parallel\text{Padding} \tag{16}\]Figure 6 shows the process. BS is treated similar to a normal SN, so it has to acknowledge every message it receives. After the message is delivered to the BS, and after the message is acknowledged, the PIDi (of the source) will be updated on the BS tables while it has been already updated in the sensor itself after the first acknowledgement.