# Information-Aware Secure Routing in Wireless Sensor Networks
## 4 Algorithm  
First, we distinguish two types of shortest paths in a WSN \(G\): (1) The single-source shortest path is the shortest path with a designated source node, and (2) the single-destination shortest path is the shortest path with a designated destination node. The original problem to be solved in this paper is to find the single-destination shortest path. If we invert the direction of all edges in such a path, we turn it into a single-source shortest path. Therefore, the problem can actually be regarded as the computation of all the shortest paths with a designated sink node in a weighted directed graph, which can be solved by the Dijkstra algorithm [43; 44]. In addition, after the problem is converted, the weight is calculated according to the original direction, in order to ensure correctness; that is, the direction of each edge in the graph is not inverted in the actual calculation. In the Dijkstra algorithm, the cost (weight) of the edge is generally represented by the distance between two nodes. The cost of the path between any two nodes is the sum of the cost of all edges in the path. In contrast, the weight \(c_{n}\) in Equation (9) is a hybrid value of the secure cost and the status of the nodes in the path. Therefore, the shortest path in the Dijkstra algorithm is replaced by the minimum cost path in our model. Algorithm 1 depicts the idea for computing the path with the minimum cost. We first illustrate the notations used in Algorithm 1:  
* The sink node is designated as source node \(v_{i}\). * \(V\) denotes the set of all vertices (\(V=N\cup\{sink\}\)). \(S\) denotes the set of destination nodes that have found the minimum cost path. \(V-S\) denotes the set of nodes that have not found the minimum cost path. \(C_{l(j)}\) denotes the cost of the minimum cost path from node \(v_{j}\) to source node \(v_{i}\). \(tempC_{l(j)}\) denotes the cost of the reconstructed minimum cost path from node \(v_{j}\) to source node \(v_{i}\). * \(pre_{ij}\) denotes the intermediate nodes in the minimum cost path from node \(v_{j}\) to source node \(v_{i}\). * \(A_{l(j)}\) represents the total attack probability of the nodes in the entire path from node \(v_{j}\) to source node \(v_{i}\), \(E_{l(j)}\) represents the total status value of the nodes in the entire path from node \(v_{j}\) to the source node \(v_{i}\), and \(C_{l(j)}=A_{l(j)}+E_{l(j)}\). Initially, \(S\) only has source node \(v_{i}\), i.e., \(C_{l(i)}=0\). If source node \(v_{i}\) is adjacent to node \(v_{j}\), then we set \(pre_{ij}=0\) and calculate \(C_{l(j)}\). If it is not adjacent to node \(v_{i}\), then \(C_{l(j)}\) is set to infinity. Then, we add node \(v_{k}\) with the least cost in all nodes adjacent to set \(S\) into set \(S\), and the minimum cost path from node \(v_{k}\) to source node \(v_{i}\) is thereby found. Because node \(v_{k}\) joins set \(S\), it is necessary to recalculate the cost of the path from each node in set \(V-S\) to source node \(v_{i}\). We repeat the above steps (by repeatedly selecting the node with the minimum cost path to join set \(S\)) until set \(S\) contains all nodes in graph \(G\). ```
Input: Node information Output: The minimum cost path from \(v_{i}\) to \(v_{j}\), \(j\in\{1,2,\ldots,n\}\) and \(j\
eq i\)
1 Initialize \(S=\{v_{i}\}\) for\(v_{j}\in V-S\)do
2 ifnode \(v_{j}\) can be directly connected to \(v_{i}\)then
3\(pre_{ij}=0\), calculate \(C_{l(j)}=A_{l(j)}+E_{l(j)}\), \(j=1,\ldots,i-1,i+1,\ldots,n\)
4 else
5\(C_{l(j)}\) is set to infinity
6
7 repeat
8 Select \(v_{k}\) so that \(C_{l(k)}=min\{C_{l(j)}=A_{l(j)}+E_{l(j)}|v_{j}\in V-S\}\) and \(S=S\cup\{v_{k}\}\)
9 Recalculate the cost of the path from each node in set \(V-S\) to \(v_{i}\)
10 if\(tempC_{l(p)}<C_{l(p)}\)then
11\(C_{l(p)}=tempC_{l(p)}\), \(pre_{ip}=k\), where \(C_{l(p)}=A_{l(p)}+E_{l(p)}\), \(p=1,\ldots,i-1,i+1,\ldots,n\)
12 until set \(S\) contains all nodes in graph \(G\)
```  
**Algorithm 1**Minimum Cost Path. Table 1 compares the improved Dijkstra algorithm and the traditional Dijkstra algorithm.