Keywords

1 Introduction

In this paper, we propose an evacuation support system that provides evacuation routes in the case of a disaster, and verify the usefulness of the system. In recent years, with the development of communication and portable device technologies, people can collect and spread information using the Internet regardless of time and place. Current popular wireless communication infrastructure is supported by a series of base stations and one communication equipment in such a base station handles a lot of communication. Therefore, when problems occur at an equipment in such a communication base station, it may be difficult, even if possible, for the smartphones to use the Internet. In fact, in the 2011 off the Pacific coast of Tohoku Earthquake in Japan, we have observed a large-scale communication failure due to corruption of the communication equipment and traffic congestion. Paralyzed communication infrastructure made it difficult for people to collect information about the conditions of transportation and safety information about family and friends using smartphones.

Our proposed system addresses this problem of communication infrastructure by constructing mobile ad hoc network (MANET) by wireless communication between users’ smartphones. Then users can share information in such a network. Since MANET is a network constructed with only portable devices, it is possible to avoid problems due to failure of communication infrastructure. However, the ever changing topology of MANET makes stable communication extremely difficult. Therefore, we propose an information sharing method using mobile software agents. A mobile agent is a program with mobility, it has a feature of perceiving environment and deciding behavior. Our proposed system constructs optimal evacuation routes by using such mobile agents to share and collect information necessary for evacuation.

In previous studies, we proposed basic configuration of the evacuation support system and verified its feasibility by simulators [1, 2]. In this study, we have expanded the features of the system and verify its usefulness with a simulator namely NS-3. In the previous paper, we have only employed mobile agents for diffusing information about the circumstances. The evacuation users, therefore, have received information not related to their potential evacuation routes, while having not receiving crucial information for their evacuation (i.e. potential dangers on their evacuation routes). In order to ameliorate the system, in this paper, we introduce yet another kind of mobile agents that actively collect information closely related to the users’ potential evacuation routes.

NS-3 is a discrete-event network simulator which targeted primarily for research and educational use [3]. The previous simulators were crude and cannot reflect the real MANET situation. On the other hand, NS-3 models the communication environments and processes in a form close to the real world, and makes it possible to perform various verification experiments. Using NS-3 makes the simulation results of ad hoc network feasible.

The structure of the balance of this paper is as follows: the second section describes related works. The third section describes the details the proposed system. The fourth section describes the numerical experiments and discusses the results, and the fifth section discusses the future works and concludes the discussion.

2 Related Works

Avilés et al. proposed an evacuation support system using MANET and Ant Colony Optimization (ACO) for in-door environments [4]. In the study, they implemented ACO by using mobile agents so that the ACO algorithm can take the movement trajectory and speed of evacuees in consideration. Then the evacuation support system constructs an optimal evacuation route for each user.

Likewise, Ohta et al. studied on evacuation support methods using ACO and MANET [5]. In the study, they pointed out a problem such as a conventional ACO may include dangerous locations when it constructs evacuation routes. This problem is caused by the dynamic nature of the disaster environments such as conflagration or tsunami. In order to mitigate this problem, they proposed an improved ACO-based evacuation support system that equips deodorant pheromone which erases ACO pheromone traces when dangerous locations are found. Goto et al. applied this proposed method to real data of tsunami damage [6]. They showed practical results by using the data of Rikuzentakata city which suffered great damage due to the 2011 off the Pacific coast of Tohoku Earthquake. They verified the method of Ohta et al. is feasible based on the real data.

Kambayashi et al. proposed and implemented a system that collects safety information of evacuees using mobile agents and MANET [7]. In the study, they proposed a method to reduce load on transmission by combining multiple mobile agents into one. Nishiyama et al. proposed communication system using portable devices that switch between MANET and Delay Tolerant Networking (DTN) according to the communication situation [8]. DTN is a method for coping with a network environment where maintaining stable communication connection is hard to achieve. When communication is disconnected, portable devices accumulate data, and then transmitted when communication is resumed. Their proposed system apply MANET when there are many portable devices in the surroundings, and apply DTN when there are not much. With such a method, they achieved to cope with various network environments.

3 Agent Base Evacuation Support System

In this section, we describe our proposed system in detail. The proposed system aims to provide an optimal evacuation route for each user (hereafter we call the evacuation user). Since the proposed system maintains the map information of the evacuation area, it is possible to calculate the shortest route to the destination (i.e. safe place). However, at the time of a disaster, there is a possibility of occurrence of a point unsuitable for evacuation (hereafter we call dangerous point) due to fire, building collapse, or inundation. Since nobody knows these points before the occurrence of a disaster, it is necessary to collect the information during evacuation. When an evacuation user finds a dangerous point, he or she inputs the position information to the system. Then the proposed system constructs a new evacuation route avoiding this dangerous point, and provides it to the user. At the same time, the system diffuses the information about the dangerous point and new route to other users’ smartphones. As a result, evacuation users other than the discoverer can know the dangerous point and avoid it in advance. In order to realize this function, we use multiple mobile agents.

A multi-agent system is a system that consists of multiple agents and achieves tasks by their cooperative operations. The agents can be categorized into two types: mobile agents and static agents. A mobile agent is generated when it is needed and executes a task through migrating among communication sites including smartphones. Every mobile agent has a unique identifier. A static agent resides on communication site including, of course, a smartphone. Unlike mobile agents, static agent has no unique identifier. We describe the details of each agent we use in the proposed system below.

3.1 Static Agents

Information Agent.

Information Agent is a static agent residing on a smartphone that interacts with mobile agents and constructs evacuation routes. When requested from the system, it creates mobile agents.

The information agent processes the request in the following order. (i) It generates the requested mobile agent. (ii) It acquires the information necessary for the generated mobile agent from the node management agent and passes it to the mobile agent. (iii) It stores the mobile agent in a queue. It periodically checks the queue, and dispatches the mobile agents to the neighboring smartphones. When a mobile agent comes from another smartphone, the information agent receives information held by the mobile agent. Then it passes the requested information to the arrived mobile agent and store it in the queue in the same way as the above step (iii). The information agent records the unique identifier of the mobile agent that visited the smartphone as well as it created in a list called visitor list. The information agent requests the visitor list of other smartphones when it communicates with them. It then passes the received visitor list to the mobile agent that needs it in the queue. The mobile agent decides the next destination from this visitor list.

The information agent constructs evacuation routes based on the information it initially has, and the information collected from the visited mobile agents. The evacuation route is the shortest route to the destination avoiding dangerous points that are currently known by the information agent. The evacuation route is determined based on the Dijkstra’s algorithm. The Dijkstra’s algorithm is an algorithm for solving the shortest path problem between two nodes in a graph, and was proposed by Edgar Dijkstra in 1959 [9]. In the proposed system, the graph consists of intersection as the nodes, and the distances between intersections as the edge weights. The information agent constructs an initial evacuation route at the system startup time. After that, when a mobile agent arrives and let the information agent know a dangerous point exists on the current evacuation route, the information agent reconstructs the evacuation route.

Node Management Agent.

Node Management Agent is another static agent residing on a smartphone for managing the information on the smartphone. The node management agent stores the dangerous point information collected from the visited mobile agents in the information table. At this time, if the same information already exists in the information table, the node management agent delete older information. Also, if the information agent requests information about dangerous points, the node management agent passes the requested information.

3.2 Mobile Agents

Information Diffusion Agent.

Information Diffusion Agent is a mobile agent that diffuses the information of the dangerous point found by the evacuation user to neighboring smartphones.

When an evacuation user finds a dangerous point and input its information into the system, the information agent generate the information diffusion agent. The information agent passes the coordinates of the discovered point to the generated information diffusion agent. And then, the information diffusion agent waits until a link with another smartphone is established. After that the information diffusion agent act as follows: (i) When communication links with other smartphones are established, the information diffusion agent copies itself by the number of linked smartphones and moves to each smartphone. However, if the information diffusion agent finds that it has already visited the smartphone (i.e. the smartphone’s visitor list has its identifier), it does not move but commit suicide. (ii) After the movement, it passes its own information to the information agent on the destination, and be into standby state until the next communication link being established. It repeats this process a constant number of hops. When the information diffusion agent copies itself, it copies not only its own information but also its own unique identifier. Therefore, it does not move to the smartphone that its own copy has visited. This mechanism prevents a smartphone from receiving the same information multiple times.

Information Collecting Agent.

Information Collecting Agent is another mobile agent that collects information about the events on the evacuation route and returns to the original smartphone. The information diffusion agent diffuses the information discovered by the evacuation user around the discovery point, but there is no guarantee that this information can be conveyed to all evacuation users who need it. In order to solve this problem, we propose the information collecting agent that actively collects information diffused by the information diffusion agent as shown in Fig. 1.

Fig. 1.
figure 1

Information diffusing and information collecting.

Full size image

The information collecting agent returns to the original smartphone after the information collecting process, but there is a problem with the return method. In the situation of the proposed system being used, it is difficult to return through the movement history of the agent in reverse order due to the disappearance of the smartphones it has visited. They may move out of wireless communication range or their batteries may be exhausted. For this reason, the proposed system predicts the current location of the original smartphone based on the evacuation route, moving speed and elapsed time of the original smartphone.

The information agent generates the information collecting agent at regular time intervals. Then, the information agent passes the current evacuation route information, the moving speed of the user, and the life time of the information collecting agent, to the generated information collecting agent. And this information collecting agent waits until a communication link with another smartphone is established. The information collecting agent has two states, the collecting state and the return state, and the behavior changes depending on the state. Initially it is in the collecting state. The collecting state is a state of collecting information and acts as follows. (i) The information collecting agent moves to the smartphone located close to the current evacuation route of the user and furthest from the user. Though, of course, it excludes the smartphone that it has already visited. (ii) It acquires information from the destination smartphone. The information collecting agent repeats this process during the collecting state. If the information collecting agent acquires information that tells there is a dangerous points on the evacuation route, or exceeded half of the its own life time, or cannot find the next migration candidate, the information collecting agent becomes in the return state. The return state is a state of returning to the original smartphone and acts as follows. (i) The information collecting agent calculates the predicted current position of the original smartphone based on the information it has; i.e. evacuation route information of the original smartphone and the moving speed of the evacuation user of the smartphone, and the elapsed time since it was generated as shown in Fig. 2. (ii) It moves to the smartphone closest to the calculated expected current position.

Fig. 2.
figure 2

Predict the position of original smartphone.

Full size image

Unlike the collecting state, in the return state, it is not excludes the smartphone it has visited. It repeats this process until returning to the original smartphone. When the information collecting agent return to the original smartphone, it passes the collected information to the information agent on the smartphone and disappears. If the information collecting agent cannot returns even exceed the own life time, or if it cannot find the original smartphone in the vicinity of the calculated predicted current position, it commits suicide.

One of the disadvantages of the information collecting agent is that, since it is generated from each smartphone, the network load tends to increase. In order to mitigate this problem, the proposed system controls the generation of the information collecting agents by broadcasting messages to the neighboring smartphones that request to stop generating the information collecting agent for certain period. This message contains the address and the evacuation route of the sender, and the life time of the information collecting agent. The smartphones that receive this message stop generating information collecting agents if its own evacuation route is the same as described one in the message. If the own evacuation route is different from what described in the message, it ignores and discards the message. When the information collecting agent returns to the sender smartphone of the message, this smartphone broadcasts messages that permit generating information collecting agents and the collected information to the neighboring smartphones. The smartphones that have stopped generating information collecting agent resume generating of the agents when they receive this message. The smartphones also resume generating information collecting agents when the stopping period in the message elapses.

4 Numerical Experiment

This section describes the numerical experiment of the proposed system. We verified by simulation in situations that people use the proposed system at the disaster area. We used NS-3 for simulation. NS-3 is a discrete-event network simulator which is open for research and educational use [3]. The model of the communication environments and processes in a form close to the real world, and the simulator makes it possible to perform various verification experiments. In this experiment, we verified how far evacuees can avoid dangerous points and how many agents are transmitted when using the proposed system.

4.1 Experimental Conditions

We created the simulation map that represents the evacuation area (Fig. 3). This simulation map is a model of the real map which about 1 km2. Evacuation users are randomly placed and move toward assigned destination (safe area). There are four destinations (depicted as green zones), and randomly assigned to each evacuation user. The moving speed of the evacuation user is set to 1 m/s. The evacuation user knows the map and the destination of the evacuation area and moves through the route constructed by the Dijkstra’s algorithm. However, the evacuation user does not know dangerous points in advance, and they will know for the first time by actually touching to the dangerous points or notified by other evacuation users through mobile agents. When an evacuation user knows the new dangerous point, the information agent in his or her smartphone reconstructs the evacuation route avoiding this dangerous point. Ten dangerous points are randomly allocated from all intersections. The communication distance of the smartphone is 50 m. The evacuation user who arrives at the destination terminates the communication. The simulation finishes when all the evacuation users arrive at the designated destinations.

Fig. 3.
figure 3

Simulation map (Color figure online)

Full size image

In this verification experiment, we measured (1) the number of the touches to the dangerous points of all evacuees and (2) the number of agent transmissions of all the smartphones. In (1), we divided the experiment into two cases. One is the case that people use the proposed system. In this case, the information diffusion agent diffuse discovered information, and the information collecting agent collects information on evacuation route. The number of hops of an information diffusion agent is 2, and the life time and the generation interval of an information collecting agent is set to 50 s. The other case is that people do not use the proposed system. In this case, people spreads the discovered information by simple flooding. The number of hops is not limited, and if the link with another smartphone is established at the time of transmission, it is diffused any number of times. However, as with the proposed system, the same information is never transmitted to the same smartphone. In both cases, we further divided the cases that the number of evacuees 100, 200, 300, 400, 500. We have carried out all the cases 50 times each, and the average value was taken as the results.

4.2 Result and Discussion

Figure 4 shows the results of the number of the touches to the dangerous points. In this figure, “proposed system” is the case of using the proposed system and “flooding” is the case of not using it. In all the results, we found that the case of using proposed system suppressed the number of touches to the dangerous points than the case of not using it.

Fig. 4.
figure 4

The number of the touches to the dangerous points.

Full size image

The result of the number of agent transmissions was as shown in Fig. 5. We found that as the number of evacuation users increases, the number of transmissions also increases. Also, the average number of transmissions per evacuation user increased according to the number of people. We have considered that this is due to as the number of the agent generation source smartphones increases, the number of transmission of the relay smartphones increases. In this experiment, the maximum number of evacuation users was set at 500 people and the number of agent transmissions is tolerable, but in a real situation, the number of people may increase further. In such a case, the load of the relay smartphone may increases to an extent that cannot be ignored. We must construct yet another mechanism to suppress the number of generating mobile agents.

Fig. 5.
figure 5

The number of agent transmissions

Full size image

5 Conclusion

In this paper, we proposed an evacuation support system that enables information sharing under environments where people cannot use the Internet communication due to the disaster, and verified this system.

As a future work, it is necessary to address the increase in the load of relay smartphones. Since the information collecting agent moves along the evacuation route of the evacuation user, they frequently move in a busy street such as main streets and in front of evacuation centers. As a result, the network load increases locally. Therefore, it is necessary to develop a mechanism for controlling the flow amount of the agent in such a place. In addition, we also need to extend the simulation. Although we used a two-dimensional map in the simulation, a three-dimensional map is needed to consider tsunami damage.