# An IoT-Based COVID-19 Prevention and Control System for Enclosed Spaces
## 3 Materials and Methods
### Path-Planning Algorithm with Congestion Control  
The main function of the path-planning algorithm is to guide users to destinations as soon as possible, which reduces the infection risk. For a COVID-19-positive individual, fewer contaminants will be unconsciously emitted; and for a healthy person, the exposure time to contaminants will be reduced. The path-finding algorithm is introduced to solve the Single-Source Shortest Path problem with efficiency. The Dijkstra algorithm is a ubiquitous and typical solution to find the shortest path between two given vertices. In the statement of Dijkstra, \(V\) is a set saving all nodes in the graph, and \(S\) is initialized to store nodes whose shortest paths from the start vertex are found. Every time, we select a node \(u\) with the shortest distance from start vertex \(s\) in \(V-S\) (difference set between \(V\) set and \(S\) set). After that, the vertex \(u\) can be considered as the intermediary point, and then the shortest distance between the start  
Figure 2: The establishment of RSSI fingerprint database. vertex \(s\) and any vertex \(v\) that can be reached from \(u\) is optimized [55]. The pseudo code of the sequential Dijkstra algorithm is presented in Algorithm 1. ```
Input: vertex s, graph G Output: None
1. set collected;
2. double_array d[];
3. \(\textbf{while}(1)[\)
4. node v = get_min_node();
5. if(v is null)break;
6. collected.insert(v);
7. for(w in vadjacent_vertices())
8. if(w not in collected)
9. if(d[v] + G[v][w] < d[w])
10. d[w] = d[v] + G[v][w];
11. ] ```  
**Algorithm 1**Sequential Dijkstra Algorithm  
However, for a public area in which many people stay, a single-thread Dijkstra algorithm implementation is of low efficiency for handling a great many simultaneous requests. An increase in the use of the General-Purpose Graphics Processing Unit (GPGPU) offers massive-scale parallel computing capabilities. The GPGPU is based on a single-intruction, multiple-thread (SIMT) execution model, i.e., each thread executes the same code. CUDA (Compute Unified Device Architecture) is a parallel computing framework enabling programmers to develop GPU-accelerated applications on major architectures including x86, Arm and POWER. It dispatches GPU parallelism for general-purpose computing and retains performance. It is developed based on industry-standard C++. CUDA consists of a small set of extensions to enable heterogeneous programming [56]. ```
Input: vertex s, graph G Output: None
1. generate subgroups;
2. while (there are vertices not in collected){
3. for (vertices in the subgroup but outside collected){
4. select the locally closest vertex;
5. } 6. find the globally closest vertex;
7. } ```  
**Algorithm 2**Parallel Dijkstra Algorithm  
In the sequential algorithm, the outer loop must be executed in order. Subgroups for every \(V/P\) vertices are partitioned. \(P\) is the number of computation units, which is set by programmers according to the need, and \(V\) is the number of vertices. Each core finds its closest vertex to the source vertex, selects the globally closest one, and broadcasts the result to all cores. In Algorithm 2, at each loop, the value for \(O(V)\) cores is updated separately, and the gross execution time is \(O\) (\(V2+V/log(P)\)) [57,58]. After surveying and mapping, the original graph of an enclosed space is generated, and then it is converted to an adjacency table or adjacency matrix. The graph is sometimes a multi-graph (e.g., Figure 3). The edges represent roads, and the numbers indicate the distance between two vertices. The vertices are marked by the manager of the enclosed space as needed. It is required to make statistics and record the roads (edges in the multi-graph) most prone to congestion (or manually analyze which roads have higher probabilities for congestion), and these roads are stored in a set \(E_{s}\). Every time a user sends a request for navigation, the multi-graph needs to be converted to a simple graph.