## 4 Secure Path Algorithm
### Feedback-Based Secure Path Construction  
Here we propose a feedback-based secure path construction (FSPC) algorithm to support secure data collection. We try to use a _tracing/feedback mechanism_ for this purpose. The algorithm is illustrated as follows:  
1. A source node \(S\) sends a data packet according to the ADC algorithm. To each share of data packet, \(S\) attaches an identity list \(L_{R}\) to it. Initially, \(L_{R}\) is empty.
2. When a sensor node \(S_{k}\) receives a share, if it is a normal node, it adds its identity \(d_{k}\) to \(L_{R}\) (it is possible that compromised nodes also do so in order to disguise themselves).
3. On the arrival of the share, the sink extracts \(L_{R}\)= {\(d_{1}\), \(d_{2}\),..., \(d_{n}\)} (\(d_{i}\) refers to the identity of the node \(S_{i}\)) from the share and stores it in its local database. Here \(L_{R}\) is called a _secure path_ in this case.
4. The sink adds \(L_{R}\) to a notification packet (see figure 3) and sends the packet to \(S\) according to \(L_{R}\). The notification packet contains the secure path for data collection.
5. When a sensor node \(S_{j}\) receives the packet, if its identity \(d_{j}\) is within \(L_{R}\), it extracts a sub-path \(P_{j}\)= {\(d_{j+1}\), \(d_{j+2}\),..., \(d_{n}\)} from  
In this algorithm, each normal sensor node in a routing path adds its unique identity to the data packet. When the data packet reaches the sink, it involves a routing path that consists of a list of the identities of normal sensor nodes. It means that the path is potentially safe for data collection and can be used again by the source node in the future. A complete secure path is always terminated and collected by the sink. Here we use a _feedback mechanism_ to notify the source node that requires the path for future data collection. The sink sends back a notification packet that contains a secure path to the source node. The task of notification is at intervals rather than immediately in order to reduce the overhead of the WSN. We can formally represent a secure path as a triple \(<\)_S_, \(L_{R}\), \(C\)\(>\), where \(S\) is the source node for the path, \(L_{R}\) is the identity list and \(C\) is a counter with an initial value \(\lambda\) (\(\lambda>0\)). The value of \(C\) denotes the trust value for a secure path and a path with larger counter value is safer.  
The secure path \(L_{R}\) from the source node \(S\) to the sink is a complete path for data collection. Therefore, it is called a _global secure path_. The secure path \(P_{j}\) from an intermediate node to the sink is a part of the global secure path, so it is called _local secure path_. Local secure paths can be extracted from a global path. With FSPC, we can get one global secure path as well as a collection of local secure paths. For example, a source node \(a\) wants to send data to the destination node \(g\) (see figure 5). Assume node \(e\) is a compromised node. Then the path {_b_, \(c\), \(d\), \(f\), _g_} is a complete secure path. Paths like {_d_,\(f\), _g_} are local secure paths.  
Figure 4: An illustration of the FSPC algorithm for secure data collection.  
Figure 5: A simple example for secure path in WSN.  
Here the notion of secure path does not mean that the path is safe for data collection. A secure path may include compromised nodes. This is mainly because that a compromised node drops a data packet with a probability. If a compromised node does not drop any data packet during the process of secure path construction, it will be considered potentially safe and be included in the path. In the worst case, each compromised node does not drop the data packet on the stage of secure path construction, in order to be involved in a secure path. Then each compromised node will appear on a secure path, which leads to a very low success ratio of data transmission. Therefore, when we say a path is a secure path, it only means that the path is currently safe for data collection.