1. Introduction
Mobile ad hoc networks (MANETs) have been proposed as a communication mechanism for disaster situations [1] . When a disaster occurs, people need to obtain information regarding what is happening, what they must do, and what is announced by the anti-disaster headquarters. Currently, people tend to use smartphones to communicate with each other. Messaging services (such as Twitter, Facebook, and Instagram) available on smartphones sometimes work effectively as communication methods in disaster situations. However, these cellular-based communication services are dependent on carrier infrastructures. This has the result that one might not be able to communicate with one’s friends after a disaster, because of possible damage to the carrier’s infrastructure. MANETs are useful in such situations, because a MANET requires no infrastructure other than wireless communication devices such as smartphones.
It has been suggested that the headquarters take three steps to lead a safe evacuation: first, collect information; second, decide on an evacuation plan based on risk estimation; and third, decide on an evacuation route for each evacuee [2] . Some studies have been conducted to determine how information is exchanged between evacuees and the headquarters [3] [4] [5] . The latter can build an ad hoc network using unmanned aerial vehicles, drones, or rescue teams carrying wireless devices, if needed [6] .
In this study, we focus on the first evacuation after the occurrence of a disaster. People need to plan their own evacuation by themselves until a headquarters and rescue teams are organized. Using a MANET, they can exchange information with other people. The Emergency Urgent Communication-Evacuation Support (EUC-ES) system [7] gathers information on how evacuees have moved on roads, estimates broken roads, and proposes an evacuation plan. It uses MANETs as a communication method to avoid problems of infrastructure failure. A map information sharing system [8] takes the same approach; it gathers routes passed by evacuees using MANETs and constructs a map. An extension based on ant colony optimization (ACO) [9] has been proposed to respond to a situation that is changing from moment to moment in disaster areas. We have also considered a method to create an evacuation plan based on ACO and MANETs [10] .
These MANET-based approaches are based on the premise that evacuees can share newly discovered information with each other. There is a question: Does a MANET have sufficient power to share information for evacuation? This is not obvious. MANETs have several problems regarding information sharing, as described in the next section, and there is a probability that they influence evacuation efficiency. In this paper, we use a multi-agent evacuation simulator to examine whether the power of information sharing through MANETs is sufficient for evacuation. Our simulator showed the power of MANETs is sufficient for evacuation without using a complex communication protocol. Section 2 details problems of MANETs. Section 3 describes evacuation simulation scenarios, the information sharing method, and the evacuation planning method on our simulator. Section 4 shows the simulation results, and Section 5 draws conclusions.
2. Manet
The following is a typical explanation of MANET. Nodes require no central server or infrastructure to communicate with each other. From the viewpoint of the network, each node is both a host and a router. Nodes communicate with each other using a wireless communication method such as Wi-Fi. Multihop communication is provided by nodes working as routers, but we must consider that nodes can move when they want to. When a router node moves out of another router’s communication range, a multihop communication using the router is broken. Figure 1 shows an example of a multihop communication. Node D can communicate with A via B and C, but E cannot communicate with other nodes because there is no other node on the communication range of E. In a disaster situation, a node is a wireless communication device such as a smartphone owned by an evacuee. Therefore, to maintain multihop communication is difficult, because nodes move frequently for evacuation.
There are two categories of routing protocols, proactive and reactive [11] . In proactive protocols, nodes exchange routing tables and network topology information periodically. In reactive protocols, routes are created when they are requested and are maintained while they are being used by multihop communications. Some studies [12] [13] [14] have evaluated several popular routing protocols in disaster scenarios and concluded that the reactive routing protocol ad hoc On-Demand Distance Vector (AODV) [15] is suitable. Proactive protocols such as the Optimized Link State Routing Protocol (OLSR) [16] have the disadvantage that the updating cost of the network topology tends to increase, because the topology is changed frequently, as described previously.
Broadcasting is another communication approach on MANETs. Basically, a node can share the same information with all one-hop neighboring nodes at the same time. If one wants to share information with multihop neighbors, flooding is a solution. For example, AODV sends a route request message in the flooding manner when creating a route. It is known that the simple flooding causes broadcast storm problems [17] , but these can be controlled as with AODV.
Broadcasting is not to be used frequently from the viewpoint of the network bandwidth capacity. However, sometimes broadcasting is useful. For example, when one must send an alert to all evacuees immediately, broadcasting is the best solution. It is also effective when a node needs to share the same information with several one-hop neighboring nodes. In this case, receiver nodes that does
![]()
Figure 1. Multihop communication on a MANET.
not need information can drop packets in the same manner as when receiving a wireless packet that has a different destination. It must be noted that sharing with two- or more-hop neighbors does not always call for broadcasting. In this case, all one-hop neighbors cannot drop packets, because they must try to relay a packet to two-hop neighbors.
3. Evacuation Simulation
To evaluate the benefits of using MANETs, we simulated evacuees’ movements and communication. Figure 2 shows our map-based simulation.
This map shows the Shinjuku District of Tokyo, consisting of the following elements:
・ Black solid line: road. Evacuees can move on these lines.
・ Green area: safe area. Evacuees attempt to move to these areas.
・ Red circle: danger area. These areas grow over time. Evacuees must avoid these areas. An evacuee who enters these areas is considered to be dead.
Evacuees are drawn as follows (see Figure 5 for details):
・ Blue point: an evacuee is evacuating but does not know where the safe areas are.
・ Light blue point: an evacuee is evacuating and knows one or more safe areas.
・ Red point: an evacuee cannot move anywhere because he/she is dead or has no available paths without entering danger areas.
・ Green point: an evacuee has already evacuated successfully.
Evacuees are placed at random locations on roads at the start of the simulation. They attempt to move to any of the safe areas via roads. They have no initial knowledge regarding maps. They can use knowledge of their own or that received from other evacuees. For this purpose, they attempt to exchange knowledge with one another, and they can communicate with other evacuees who are in the communication range drawn as a light yellow circle.
Simulation proceeds by repetition of the following steps until the states of all evacuees are changed to red or green:
1) Evacuees exchange knowledge with each other.
2) Each evacuee decides on a destination and a route based on knowledge.
3) Each evacuee moves on the route at his or her moving speed. If an evacuee’s
![]()
(a) ![]()
(b)
Figure 2. Simulation maps. The disaster situation changes from (a) to (b) in one hour.
state is not red or green (meaning that the evacuee is alive but still continuing evacuation), then when he or she arrives at the destination, he/she decides on a new destination and begins to move.
4) Danger areas expand.
Danger areas grow over time. This represents the dynamic changing of the disaster situation. If this dynamic changing is omitted, the evacuation problem changes more easily. The principal problem will be sharing the static map information, and the route detection will be similar to the simple shortest path search problem. These assumptions appear to be overly optimistic. It is natural to suppose that the situation will worsen substantially after the occurrence of a disaster. For example, a fire will expand over time. We implemented this as the simple dynamic changing.
3.1. Evacuee Behavior
In this simulation, evacuees have no initial knowledge of the map or the situation, but they can recognize these during the evacuation. An evacuee moves from one intersection to another intersection through the road and upon arrival at an intersection obtains information as follows:
・ Coordinates of the intersection (obtained, e.g., from the Global Positioning system (GPS)).
・ Length of the road.
・ Roads that begin with the intersection, the number of roads, and their directions.
・ Situation of the intersection: whether it is inside or outside a safe area or a danger area.
When the intersection arrived at is inside a safe area, an evacuee stops, because evacuation is completed. In the case of danger areas, the evacuee attempts to return to the intersection he or she came from. When both end points of a road are inside a danger area, the evacuee stops, because he or she cannot evacuate further.
3.2. Knowledge Exchange
Evacuees exchange knowledge with each other via a MANET periodically. During an exchange, they can communicate only with other evacuees who are within the communication range, but they can also use multihop communication methods, as described in Section 2.
In this simulation, they share map information, as follows:
・ Roads: the length and coordinates of end points (intersections).
・ Safe/danger areas: coordinates of intersections included in these areas.
Evacuees use area information to determine the location they must go to and road information to determine the route from the current to a safe area. Sharing road information is more difficult than sharing area information, because the volume of the information is larger in many cases.
There are several ways to share information. For example, every node can send and receive information to or from any specific node using multihop communication. This works in the same manner of the client-server model. This model has serious problems in that many nodes will be unable to communicate with the server node because of the nonexistence of a possible communication route, and the server node might disappear from the network, creating serious problems for the data exchange; this is known as the churn problem [18] . These complex methods must be planned carefully, but since planning is not the objective of this simulation, we selected simple communication methods, as follows:
・ No sharing: an evacuee communicates with no one.
・ One-hop broadcasting: an evacuee sends information to one hop neighbors using broadcasting.
・ Two-hop broadcasting: an evacuee sends information to two hop neighbors using broadcasting.
・ Share with all: an evacuee sends information to all other evacuees.
No sharing and share with all are baselines for evaluating broadcasting approaches. In the no sharing case, an evacuee can use only his or her own knowledge; this is the worst case from the viewpoint of the communication. In the share with all case, an evacuee can use whatever knowledge is acquired by any other evacuee; this is the best case.
In broadcasting approaches, evacuees cannot send knowledge that they received during the same period. They can send this knowledge in the next sharing period. One-hop broadcasting is suitable for a MANET, as described in Section 2, but information will spread only locally. Two-hop broadcasting is not the best for a MANET, but it will improve the spreading range somewhat. We can evaluate the effect of the number of hops by comparing two broadcasting approaches. For the scalability of the network, knowledge sharing of roads is limited. Evacuees can send only road information that is within a specified range around them. This prevents the sending of data becoming overwhelming, when the network and the map become large.
3.3. Evacuation Planning
The principal objective of the simulation is to evaluate whether information sharing improves evacuation efficiency. However, the efficiency depends on the intelligence of the evacuees. The evacuee agent on the simulator must be sufficiently intelligent to utilize knowledge, but it must not be cleverer than human beings.
We implemented agents to decide on evacuation plan based on their knowledge using an algorithm resembling the A* search algorithm. An agent decides on an evacuation plan as follows:
1) The agent selects the shortest path to safe areas for the plan when it can create the paths from its knowledge.
2) The agent stops the evacuation when it knows all end points of roads that start from all known intersections. This means that the agent knows all possible accessible areas but that there is no safe area to evacuate to.
3) The agent regards known end points of all known roads that have unknown end points as candidate points for the destination, because there is a possibility that an unknown end point leads to a safe area. An end point that has no known route from the point of the agent is not a candidate destination, because the agent cannot create a plan to move to the point.
4) The agent calculates the evaluation values of the candidate points and selects the best one as the destination.
5) The agent selects the road that has the best direction to move to the closest known safe area, when the destination point has several unknown roads.
Each agent builds an evacuation plan aimed at moving to a known safe area or the end point of an unknown road.
Calculating of the evaluation value of a candidate point is based on the A* algorithm. An evacuee is at point s. A candidate destination point is u. The point of a known intersection included in a safe area and the closest to u is g. The agent can calculate d(s, u) the shortest known route path length from s to u, from knowledge of the length of roads. h(u,g) is the estimation of the shortest route path length from u to g. We implemented this as the Euclidean distance from u to g.
Using these definitions, the estimation function f(u) is defined as follows:
. (1)
where f(u) is the estimation of the length of the route that leads from s to any safe area via u. The agent selects u that has the minimum f(u) as the destination. Figure 3 shows an example of estimation. Since
but
, the evacuee selects
as the destination. It is based on the simple evacuation approach in which an evacuee attempts to move to a known safe area that appears to be the nearest in his or her knowledge.
4. Results and Discussion
Table 1 shows the parameters of the our evacuation simulation in the Shinjuku
![]()
Figure 3. Example of the evacuation planning.
District. In addition, the map width is 3.6 km, and an agent can move from the east to the west within 45 minutes.
In Figure 4, the black dotted line (6) shows that the evacuee algorithm has little power without knowledge exchange. In contrast, the red solid line (1) shows the power of knowledge exchange, with a majority of people finishing evacuation within 20 minutes.
![]()
Table 1. Parameters of the simulation.
![]()
Figure 4. Number of agents which have completed evacuation.
Our simulation distinguishes between information regarding areas (safe/ danger) and that regarding roads because their contributions to evacuation are different and their required traffic is also different. An agent needs knowledge of at least one safe area to evaluate candidate points when creating an evacuation plan. An agent selects the nearest candidate point as the destination when it has no knowledge of safe areas, because it cannot estimate h(u, g) in formula (1).In other words, the agent uses the Dijkstra algorithm instead of A* when no areas information has become available. On the other hand, road information improves the calculation of d(s, u).
In the Figure 4, solid lines ((1), (2), (5)) represent the case of communicating information on safe/danger areas using share with all. The figure shows that sharing knowledge of safe areas greatly impacts the efficiency of evacuation. Comparing the red solid line (1) with the black solid line (5) shows that the sharing of road knowledge has also has a substantial impact. However, it is not realistic to share road information with all agents; because there are too many roads compared to areas, we must limit sharing at least regarding roads information. The blue solid line (2) uses one-hop broadcasting to share road knowledge. Although the communication between agents is limited, it shows the result closest to the best case shown by the red solid line (1).
The blue (4) and green (3) dashed lines are the results of one- or two-hop broadcasting. Comparing with the solid lines, these cases do not use the share with all method. The two-hop method is better than the one-hop method, but the advantage of increasing the number of hops from one to two is less significant than that of increasing the number from zero to one.
It is a noteworthy that one-hop broadcasting method (4) is more efficient than the black-line case (5) using share with all for safe/danger areas. In broadcasting, knowledge of safe area is not spread across all of the agents. Figure 5 shows the
![]()
Figure 5. Example of one-hop broadcasting after 20 minutes have elapsed.
typical situation of one-hop broadcasting. An agent shown as the light blue point has knowledge of safe areas, but a blue point agent has no knowledge of safe areas. In Figure 5, many agents are still in the blue state. Clusters of blue agents and light blue agents tend to separate out. Knowledge of a safe area spreads from a safe area to the outside, but every agent that is to relay knowledge to the outside attempts to move in the direction of the safe area after receiving knowledge. Therefore, the possibility that blue agents communicate with light blue agents decreases over time.
Despite the lack of information regarding safe areas, agents seem to be able to build effective evacuation plans using information on roads. A possible reason is that road sharing with neighbors works efficiently. This sharing completes map knowledge around the agent efficiently, and then the agent recognizes that there is no safe area around it. This stimulates the agent to move to a distant location.
5. Conclusions
In this paper, we showed the difference in efficiency brought about by data sharing in the first evacuation after the occurrence of a disaster. It is efficient from the viewpoint of MANET that an evacuee broadcasts to one-hop neighbors. This not only reduces traffic but also avoids several complex problems inherent in MANET.
Despite communication range limitations, this one-hop broadcasting showed substantial benefits for evacuation efficiency. Evacuees need knowledge regarding where and how to evacuate from a disaster and, in particular, information regarding safe areas and roads. When evacuees have already shared safe area information sufficiently, they can obtain results close to the best regarding sharing road information using one-hop broadcasting. Even if evacuees must share all knowledge via a MANET, sharing by one-hop broadcasting provides sufficient efficiency for evacuation.
Acknowledgements
This work is supported in part by Japan Society for Promotion of Science (JSPS), with the basic research program (C) (No. 17K01342), Grant-in-Aid for Scientific Research.