# An IoT-Based COVID-19 Prevention and Control System for Enclosed Spaces
## 3 Materials and Methods
### Path-Planning Algorithm with Congestion Control
Edges between two vertices (e.g., three edges between A and C with weight 5, 6, and 7, respectively) are divided into two categories: \"congestion edges\" and \"ordinary edges\". Congestion edges with probability of \(p\) and ordinary edges with probability of \(1-p\), \((p<1-p)\) are selected. If the congestion edges are selected, they are stored in \(list_{1}\). Then, let \(D_{1}=[d_{1},\ d_{2},\ d_{3}\dots\ d_{n}]^{T}\), and \(d_{i}\) denotes the distance of the \(i\)-st edge in \(list_{1}\). Let \(L_{1}=[l_{1},\ l_{2},\ l_{3}\dots\ l_{n}]^{T}\), and \(l_{i}\) represents the number limit of the \(i\)-st edge. The probability of selecting \(D_{i}\) follows Equations (19) and (20). \[\rho_{i}=\frac{l_{i}}{d_{i}} \tag{19}\]  
\[p_{i}=\frac{e^{p_{i}}}{\sum_{m=1}^{n}e^{\rho_{m}}} \tag{20}\]  
Figure 4: A graph about number limits. Figure 3: An example multi-graph. The probability of finally selecting \(D_{i}\) follows Equation (21). \[p_{f\_i}=p*p_{i} \tag{21}\]  
Indicator \(\rho\) is the \"capacity density\". An edge with greater capacity and shorter distance has a larger capacity density. Edges with a higher capacity density are more likely to be selected. The strategy for selecting ordinary edges is similar. After this process, a simple graph \(G_{s}\) is generated. The navigation for a user is based on \(G_{s}\). Each person's real-time location is marked on a multi-graph \(G_{m}\), and the number of people on each edge is monitored in real time. If a user is moving and the server finds that the number of people on the next planned edge \(e_{p}\) has reached the limit, it will open any adjacent edge near \(e_{p}\). The next vertex \(v_{p}\) is selected as the start vertex to find the shortest path to the destination. If all edges have reached the number limit, the booking algorithm in this paper is applied to wait for an edge. As shown in Figure 5, a person plans to go to A from D, and the path is D \(\geq\) C \(\geq\) A (\(e_{1}\) is selected among \(e_{1}\), \(e_{2}\), and \(e_{3}\)). The number inside parentheses indicates the current number of people on this edge. When the person is on the edge between C and D and about to reach C, the number of people on \(e_{1}\) and \(e_{2}\) exceeds the limit, and C is chosen as the start vertex to find the shortest path from C to A. Rollback is not allowed, and the person will go through \(e_{3}\). In the case where the number of people on \(e_{1}\), \(e_{2}\), and \(e_{3}\) has all reached the limit, the booking algorithm will work. Though the parallel algorithm is fast, we introduce a cache strategy which can greatly reduce the computation pressure on the server. An unordered map is a hash-based data structure which stores key-value pairs. On the premise of a proper hash algorithm implementation, the value can be accessed in constant time complexity via the key. The key of the unordered map is a combination of information (the differences between the original multi-graph and simple graph, and the start vertex with the destination vertex). For example, a key-value pair is (Key: (Delete \(e_{1}\), \(e_{2}\), and ed  
Figure 5: Dynamic congestion control. from D to A), Value: (A path)). Every time the parallel algorithm finds the shortest path, the path is stored in the unordered map if it is never added to the cache. Additionally, we can even adopt a more aggressive cache strategy: it is feasible to generate and store most of the possible paths as early as possible. In this paper, our purpose is not to build a high-performance computing center, and the hardware budget is also limited. Because of the cache strategy, the computing pressure on the server is reduced. When the cache has not been established or there are many changes to the multi-graph, the real-time path-planning algorithm will work, which often takes much more time than loading a path from the cache. In general, there is no need to invoke the parallel algorithm. The test of cache is relatively simple. The time consumption of loading a path from the cache should be within a reasonable time.