## 4 Proposed Scheme
### Identity, Route, and Location Privacy (IRL)
\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \multirow{3}{*}{Neighbor nodeID (Integer)} & \multirow{3}{*}{Direction} & \multicolumn{3}{c|}{Past interactions based on time window} & \multirow{3}{*}{Trust value} \\ \cline{3-3} \cline{5-8}  & & \multicolumn{3}{c|}{Successful interactions} & & \multicolumn{1}{c|}{Unsuccessful interactions} & \\  & & (\(S_{x,y}\)) & & (\(U_{x,y}\)) & & \\ \hline
1 & \(F\) (00) & 10 &... & 5 & 4 &... & 1 & 90 \\ \hline
2 & \(B_{R}\) (01) & 2 &... & 4 & 8 &... & 2 & 25 \\ \hline � & � & � & � & � & � & � & � & � \\ \hline \(M\) & \(B_{L}\)(11) & 5 &... & 7 & 0 &.. & 3 & 70 \\ \hline \end{tabular}
\end{table} 
Table 2: Neighbor list table at sensor node. In the Phantom Flood Routing (PFR) [3] scheme, each sensor node needs to maintain the list of neighbor nodes and these neighbor nodes are divided into two sets. Here we assume that identity of a node is represented by two bytes, and set is distinguished by a single bit. So the total memory required by each node in the PFR scheme is (16+1)\(M\) bits. In the Phantom Single-path Routing (PSR) [4] scheme, each node maintain the list of neighbor nodes, hop count (2 bytes), and set identification (1 bit). Therefore, the total memory required by each node in the PSR scheme is (16+16+1)\(M\) bits. In the SAS scheme, each node needs \(K\)(4\(M\)+2\(N\))+16\(M\) bits of memory. Here \(M\) represents the neighborhood size, \(K\) represents pseudonym space and \(N\) is the total number of nodes in the network. For the CAS scheme, each node requires \(K\)(6+7\(M\))+16\(M\) bits of memory. (See [5] for more details about the SAS and CAS schemes.) Let us assume that the sensor node has ten neighbor nodes, then the total memory required by the sensor node by the PFR, PSR, IRL, CAS and SAS is 21.25, 41.25, 260.5, 628 and 1940 bytes respectively, as shown in Figure 5.

Additionally, cycle prevention strategy (Section 4.2) requires some short term memory to store signature of the packet for short period of time (\(\delta t\)). In our proposed schemes, signature of the packet comprises of six fields: 1) Sequence number (2 bytes), 2) previous hop identity (2 bytes), 3) next hop identity (2 bytes), 4) payload (variable size), 5) counter (2 bits), and 6) \(\delta t\) time (4 bytes). So, for each packet sensor node requires \(10.25+Size(\text{payload})\) bytes of memory. The packet signature will be \begin{table}
\begin{tabular}{|c|c|} \hline PFR [3] & (16+1)\(M\) bits \\ \hline PSR [4] & (16+16+1)\(M\) bits \\ \hline SAS [5] & \(K\)(4\(M\)+2\(N\))+16\(M\) bits \\ \hline CAS [5] & \(K\)(6+7\(M\))+16\(M\) bits \\ \hline IRL / r-IRL & \(M(26+32\Delta t)+k_{bs}^{+}+k_{x,bs}\)bits \\ \hline \end{tabular}
\end{table} 
Table 3: Memory requirement in bits. removed from the buffer after \(\delta t\) time. For example, sensor node \(x\) received 20 packets of equal size of payload (e.g., 10 bytes). Then, the total memory required by the sensor node is \(20\times(10.25+10)\) = 405 bytes. This additional overhead does not make sensor nodes overloaded because of following reasons:

1. Generally, wireless sensor networks are event driven [34; 35; 36] or sensor nodes generate packets in periodic intervals [37; 38]. Therefore, the amount of overall traffic usually remains low. 2. In our proposed schemes, packets always follow different routes. Therefore, the probability of a single node to be overloaded is very low. Let us assume that the amount of traffic is very high and single sensor node needs to store large amount of packets at a time. Then in order to reduce the size of memory, we can use the technique of signature generation code [39]. This technique allows us to represent single signature code in few bytes. However, this technique is based on Bloom filters [40] that require the computation of multiple hash values. This may increase the computational cost. Therefore, we need to trade off between memory and computation cost. ### Energy Consumption Analysis

In this section, we will show the efficiency of our routing strategies with existing schemes.