# A Survey of Algorithms and Systems for Evacuating People in Confined Spaces
## 3 Evacuation Wayfinding Algorithms
### On-Line Evacuation Wayfinding Algorithms
#### 3.2.6 Routing Protocol-Based Algorithms  
Since many of the current emergency response systems are based on wireless sensor networks, routing protocols that were initially used for packet networks have been borrowed or adapted to direct evacuees and improve communication quality in hazardous environments. For instance, the research in [97] presented an emergency support system built on top of a WSN to guide evacuees out of a confined space in a real-time fashion; the embedded evacuation wayfinding algorithm was inspired by the cognitive packet network routing protocol [145; 146], which was initially designed for large-scale packet networks; different from the original CPN that contains three types of packets: smart packets (SPs), dumb packets (DPs) and acknowledgements (ACKs), this variant only consists of SPs and ACKs; SPs are sent from each sensor node in the WSN to search for egress paths and collect hazard information in a distribute manner with their predefined goals; when an SP reached an exit, which means an egress path has been discovered, an ACK would be generated and bring back the ID and the hazard information of each sensor node along the path to the source node that emitted the SP; when the ACK reached the source node, it would update the QoS level of the discovered path by using a rolling average mechanism, which summed the newly-discovered QoS and previously-stored value in a weighted manner; in attempting to efficiently find the route with the best quality of service (QoS), when an SP arrived at a sensor node, it would decide its next hop by the m-sensible routing algorithm [147]; a QoS metric was defined as sensitive if its value was affected by the traffic through the path, such as congestion level; on the other hand, a QoS metric was insensitive if its value was independent of the traffic assigned to the path, such as path length or number of hops on a path; m-sensible routing algorithm calculated the probabilistic choices of all the neighbour nodes based on the QoS information brought back by the previous SPs; hence, future SPs decided their next hop by yielding the probabilistic choices of the neighbour nodes obtained by the m-sensible policy; it is proven in [147] that the QoS increased with the increase of term \(m\); hence, an \(m+1\)-sensible routing policy provided better QoS on the average than the m-sensible policy; to enhance the stabilisation of network, a predefined \"measurement discard threshold\" was set to discard the reported QoS (effective length) that was smaller than the threshold. Since communications that are essential in an evacuation process can easily malfunction due to the hazard, the research in [23] proposed a resilient emergency support system (ESS) to disseminate emergency messages among evacuees and direct evacuees out of a confined space with the aid of opportunistic communications (Oppcomms) [22]. The proposed system was composed of pre-deployed sensor nodes (SNs) to collect environmental information and mobile communication nodes (CNs), which were portable devices carried by evacuees; to locate evacuees, each SN contained a location tag and could periodically send a location message (LM) to CNs in proximity; when an SN detected a hazard, an emergency message (EM) would be generated and broadcast to CNs carried by evacuees in the vicinity by using the epidemic routing [148]; the EM would be stored in these CNs and forwardedto other CNs in contact by the \"store-carry-forward\" paradigm [25] during the movement of the evacuees; to guide evacuees, each CN stored the building graph in its local storage and updated the edge costs when receiving an EM. [PERSON]'s shortest path algorithm was triggered to calculate the shortest safest path when the graph was updated; experimental results indicated that the proposed system was robust to network failures during an emergency.