## 2 The Novel Algorithms
### The Direction Based Path Finding Algorithm  
Our observations are depicted in Figure 1. This figure shows an example for a fire evacuation with two fire exits and one civilian. As it could be seen, there are two different evacuation path, one for each exit. In the Figure 1a subfigure the civilian will choose the path which is indicated by red, as it is shorter than the other one. However, the \"red\" path is shorter than the \"green\" one, but it leads the civilian towards the hazardous area which can be very dangerous. Thus, our idea was that the algorithm should lead the civilian through a safe path even if it is longer than the others. Hence in this case, the civilian should choose the \"green\" path instead of the \"red\" one. To predict the safety metric of a path, we can utilize directions, which is the main element of our novel path finding algorithm. A direction vector should be determined for each path, which describes its main direction (the direction points from the civilian position to the selected exit), and another vector should be calculated, which is the optimal evacuation direction from the hazardous area. These direction vectors are shown in Figure 1b. The proposed algorithm uses these directions to guide the civilian through a safe path to a fire exit. The first step in our algorithm is the calculation of these directions. The directions from the civilian's position to the exits (such as the dashed arrows in Figure 1b) are easy to calculate, since the graph for the given area is stored on the CN, therefore, the positions of the exits are available for every civilian, and each CN can obtain its location from the fixed sensor nodes (SNs). The fire direction (which points from the estimated fire location to the CN) is a bit more sophisticated, since a CN could have many emergency messages (EMs) and these could contain different locations. Thus, the resultant vector should take into account all the received packets. More recent messages (with a newer timestamp) are more relevant, therefore, the locations in the messages should be weighted by factoring in their creation time. Lets assume, that a civilian has received \(n\) different EMs (identified by (device ID, timestamp) pair), which are ordered chronologically (based on the creation time), and let \(v_{t_{i}}\) be a direction carried by the EM (from the affected location to the current civilian's position) generated at \(t_{i}\). Then the resultant vector could be calculated as follows:  
\[v_{sum}^{\ \ \ }=\sum_{i=t_{0}}^{tn}\frac{1}{2^{i}}\vec{v}_{i} \tag{1}\]  
It should be noted in Equation (1), that when \(n\rightarrow\infty\) then the newest message has the same weight as all the preceding weights aggregated. It is important to notice that the \(v_{t_{i}}\) vectors are direction vectors, therefore, the result does not depend on the distance between the civilian and the hazardous area. In the next step, our algorithm tries to find a path based on the previously calculated \"fire\" vector. Since a civilian has one \"fire\" vector and many \"exit\" vectors, the angle between a fire vector and an exit vector can be calculated simply. As it is depicted in Figure 1b the paths with smaller angle (meaning the  
Figure 1: An evacuation example. (**a**) Based on the shortest path the civilian will choose the “red” path; (**b**) By using directions, our algorithm can guide the civilian through the safer “green” path. angle between the selected exit and the fire vector) are more likely to be safer than the paths with higher ones. Hence, a novel cost function could be defined as follows:  
\[\hat{F}(\phi_{i},G)=\frac{-cos(\phi_{i})+1}{2}*D_{i} \tag{2}\]  
\(\phi_{i}\) denotes the angle between the fire vector and the \(i^{th}\) exit vector, \(D_{i}\) is the shortest path cost to the \(i^{th}\) exit and \(G\) is the graph of the area. Note, that If there is an exit right next to the civilian's position but its angle (\(\phi_{i}\)) is much bigger than the other's (which is actually far from the source), the algorithm will choose the further exit.