## 1 Introduction  
Emergency evacuation is unfortunately an essential component of built environments such as sports arenas, concert halls, buildings in general, and even ships. The technical issues it raises are related to search techniques [1] to guide people or vehicles in dangerous areas [1,2]. As a consequence, there has been many work related to evacuation techniques that use distributed computation and wireless sensor networks (WSN) [3]. Although WSNs can be used both for sensing the hazards, identifying evacuees and communicating with them, and possibly for finding safe paths, such networks also require a minimal fixed infrastructure which remains viable during an emergency. Since many catastrophic events can also impair or destroy the fixed sensor nodes, this paper considers the use of a simpler technology based on commonly available wearable opportunistic network nodes that can be implemented with smart phones or personal digital assistants, as a supplementary system or an alternative for helping evacuees. Research papers in the field [4] fall mainly into two categories. The first group is comprised of solutions that rely on the existence of a sensor network for emergency navigation. The work by [PERSON] _et al._[5] who propose a distributed navigation algorithm with implementation and evaluation on a physical sensor network. Their approach is based on the flooding model in which every sensor exchanges information with every other sensor, therefore, this solution does not scale well, due to a very high communication cost. In [6] a distributed navigation algorithm based on the temporally ordered routing algorithm (TORA) is introduced in order to guide civilians in a building with a 2D layout during an emergency. This protocol is extended to 3D environments in [7]. In addition, others [8,9] have taken congestion into account, and in [8] an algorithm where rescue force flexibility is also examined is proposed. An indoor navigation system is presented in [10] based on mobile phones that use a pre-existing WSN for monitoring the building and receiving updates regarding a dynamic hazard, together with a centralized emergency guidance system. Some prior work [11,12] provides a distributed decision support system (DDSS) for building evacuation, where static decision nodes (DNs) with communication and processing capabilities are installed in the building and provide directions to civilians in their vicinity, either via dynamic signs or wireless communications. DNs form a network and disseminate information regarding the hazard and evacuation paths in a distributed manner based only on local information, and a distributed update algorithm is executed periodically by the DNs, where each DN communicates with its neighbors to send its current hazard and path metrics. Other work has considered the specific computational structure that is needed to simulate and control emergency navigation with the use of sensor networks [13]. The second group of solutions is significantly different from the first, since hazard information is disseminated over an opportunistic network of communication nodes (CNs) that operate as part of the Emergency Support System (ESS) and disseminate Emergency Messages (EM). Most data forwarding and routing protocols for opportunistic networks (oppnets) [14] seek a balance between message delivery ratio and resource consumption [15, 16, 17]. For the dissemination of EMs, which are very short in nature, a high delivery ratio and low message latencies are crucial. A fine example of opportunistic communication protocols is the epidemic routing protocol [18], which disseminates multiple copies of a message over the network similar to the spread of an infectious disease and has been used in [19]. However, the ESS we describe uses a fixed infrastructure of sensor nodes (SNs) to monitor the environment, but each civilian is guided by his/her own individual CN, which locally calculates the best evacuation path based on the currently obtained information.