Implementation and verification of MORN to RoboCup Rescue Simulation NAITO-Rescue 2014(Japan)

Yoshiki Fukushige, Takuma Kawakami, Dai Obashi, Shunki Takami, Yusuke Kitagawa, Nobuhiro Ito, Kazunori Iwata

Department of Information Science, Aichi Institute of Technology, Aichi, Japan; Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Aichi, Japan; Department of Business Administration, Aichi University, Aichi, Japan

Abstract Voice and radio communication are a means of sharing information between agents in RoboCup Rescue Simulation. However, this is limited to voice communication in some scenarios. It is necessary to establish a communication system for environments in which voice communication is disrupted and delayed. The architecture to overcome this situation is called a delay-tolerant network (DTN). In this paper, we implement moving target oriented opportunistic routing algorithm in vehicular networks (MORN) for the agents, and compare it with epidemic routing. Extending epidemic routing with MORN is a technique typical of DTN.

1 Introduction

Cooperation in RoboCup Rescue Simulation (RCRS) is achieved by using radio communication and voice communication. While radio communication can be used without distance restrictions, voice communication can only transmit information in an area around the agent. However, in some scenarios where radio communication is not available or the bandwidth is limited, the sharing of information between agents is restricted to voice communication. Voice communication has several problems owing to the changing positional relationships between agents. For example, it may not be possible to construct a communication path between end nodes in a divided intermittent network, and there are delays in information transmission. Therefore, it is necessary to establish a communication system for environments in which voice communication is disrupted and delayed. In this paper, we apply moving target oriented opportunistic routing algorithm in vehicular networks (MORN)[3] as an information sharing system for agents, reducing information sharing problems in environments that allow only voice communication.

2 Moving target oriented opportunistic routing algorithm in vehicular networks (MORN)

[Subsections follow]

2.1 Delay-tolerant network

In recent years, delay-tolerant networks (DTN)[1] have become an important communication architecture for overcoming delays and division in a network. DTN was proposed as an architecture for networks having propagation delays associated with interplanetary communication. However, it is expected to be an effective architecture for networks that divide frequently, and so might also be applicable in environments with poor communication. Epidemic routing[2] is a representative DTN routing method. Epidemic routing continually generates a copy of a message, which is finally delivered to a destination. This method makes it possible to reliably deliver a message to the node. However, it has the problem of pressuring the communication band with several copies of each message.

2.2 About MORN

To reduce communication problems, MORN [3] has been proposed as a routing method that targets vehicle networks. MORN is able to select the best transmission destination based on global positioning system information obtained from other nodes within a communication range. Contrary to epidemic routing, a message is sent only to the best communication node, and thus does not compress the communication bandwidth. Each vehicle in a MORN broadcasts its tracking information, and message carriers transfer the message to the vehicle determined to be closest to the target vehicle based on tracking information. For this reason, message delivery is achieved with a small average number of hops.

2.3 Node model of MORN

The node model of MORN has the following features.

• Each node has a unique identification, and can be differentiated from other nodes.
• Nodes move in real time.
• Each node can obtain auditory information and visibility information.
• There is a limit to the visibility range of the node.
• Visibility information can give location information for surrounding nodes.
• Nodes can communicate through a radio communication device.
• The radio communication devices have a limited range of communication.
• There is a limit to the communication bandwidth.
• Multiple nodes also perform communication at the same time, it is capable of receiving data correctly.
• Movement speed will vary with situation (e.g., traffic jams).

Design of MORN

[Subsections follow]

Sending message

In MORN, $v_{tar}$ is the vehicle that requires a message, IS is the source of the requested message, $v_i$ is the vehicle that has a response message (message carrier), and $v_i$ is the vehicle that could be the message carrier. The message contains tracking information about $v_{tar}$ and the TTL (time to live) that represents the effective time of the message. When $v_i$ receives the request from $v_{tar}$, $v_i$ determines whether $v_{tar}$ is within the communication range. If $v_{tar}$ exists, $v_i$ terminates the process and sends a reply message to the $v_{tar}$. If $v_{tar}$ is not within the communication range, $v_i$ uses the tracking information about $v_{tar}$ included in the message sent from $v_{tar}$ to determine the minimum distance $d_{min}(v_i, v_{tar})$ between $v_{tar}$ and $v_i$ from formulas 1 and 2. Defining $t_{min}(v_i, v_{tar})$ as the time corresponding to $d_{min}(v_i, v_{tar})$ as in formula 3, the ratio of proximity to time $t^(v_i)$ and the ratio of proximity to a distance $d^(v_i)$ are calculated from formulas

$$d_{v_i,v_{tar}}(t) = dist(v_i(t), v_{tar}(t)) = \sqrt{(x_{v_i}(t) - x_{v_{tar}}(t))^2 + (y_{v_i}(t) - y_{v_{tar}}(t))}$$

$$d_{min}(v_i, v_{tar}) = min_{0 \le t \le TTL} d_{v_i, v_{tar}}(t)$$

$$t_{min}(v_i, v_{tar}) = t_{d_{min}(v_i, v_{tar})}$$

$$d^{\star}(v_i) = \frac{d_{min}(v_i, v_{tar})}{d_{IS, v_{tar}}(0)}$$

$$t^{\star}(v_i) = \frac{t_{min}(v_i, v_{tar})}{TTL}$$

All vehicles in the coverage area of $v_i$ then use the tracking information about $v_i$ and $v_{tar}$ to obtain values for $d^(v_i)$ and $t^(v_i)$. Formula 6 is then used to determine a value $\sigma(v_i, v_i)$ by combining the time and distances between $v_i$ and $v_i$ in the ratio of $1 - \lambda : \lambda$.

$$\sigma(v_i, v_j) = \lambda * (d^(v_i) - d^(v_j)) + (1 - \lambda) * (t^(v_i) - t^(v_j)) \qquad 0 \le \lambda \le 1$$

Choose $v_j$ so that $\sigma(v_i, v_j)$ is greater than a threshold c and $v_j$ is closest to $v_{tar}$. $v_i$ then sends a response message to the selected $v_j$. After a successful transmission, the response message $v_i$ holds is removed and the process ends. Further, if $\sigma(v_i, v_j) < c$ for all $v_i$, then $v_i$ terminates the process without sending a response message. Figure 1 shows the process flow.

Monitoring of the effectiveness of the message

To monitor whether the message is always valid, the message carrier $v_i$ must be discarded if the message has been disabled. We use effectiveness of time $M_t(v_i)$ and distance $M_d(v_i)$ for this. $M_d(v_i)$ and $M_t(v_i)$ can be obtained from formulas 7 and 8. These two values are used to calculate the validity $M^{\star}(v_i)$ in formula 9. The message is discarded if the value of $M^*(v_i)$ is less than or equal to zero.

$$M_d(v_i) = \frac{d_{min}(v_i, v_{tar})}{d_{IS, v_{tar}}(t_{now})}$$

$$M_t(v_i) = \begin{cases} \frac{t_{now}}{TTL} & \text{if } 0 \le t_{now} \le TTL\ 1 & \text{if } t_{now} \ge TTL \end{cases}$$

$$M^{\star}(v_i) = (1 - M_d(v_i)) * (1 - M_t(v_i))$$

3 Verification

[Subsections follow]

3.1 Method

We apply both epidemic routing and MORN to a simulation experiment, and compare the results. Initial experiments are used to determine the number of attempts. In Berlin and Kobe, figure 2 and figure 3 are the standard deviations of the number of hops in each attempt. From the results, it can be seen that sufficient results are achieved for 20 or more attempts, so the number of attempts we use is 30.

3.2 Simulation setting

[Subsections follow]

Maps

In this paper, we study traffic in Berlin and Kobe. Because the shape of the roads and the size of the map affects the results, we use two maps with contrasting features. Berlin is currently the largest map used in RoboCup competition, and it is a complicated map. Kobe is smaller than Berlin, and the road shape is simpler.

Scenarios

We prepared 30 scenarios with no road blockages and 60, 80, or 100 fire agents placed randomly on the roads. Information sharing may be affected by the death of the agent in a fire or by an agent 's movement being interrupted by a road blockage. The number of agents is a third factor that may affect the results.

Agent behavior

The behavior of the agent comprises only voice communication and movement. Rescue activities influence information sharing in an investigation in terms of both the average delivery time and the message delivery rate. The speed of the agents is 30 km/h. In addition, agents are placed randomly and take the shortest path to a destination. The communication range for voice communication has a radius of 30 m, and each agent has at most one message request at a time.

MORN setting

We set the TTL, the effective time of the message, as 10 steps.

3.3 Results

The following table shows the results of the simulations.

Table 1. result

3.4 Comparison of MORN and epidemic routing

[Subsections follow]

Average delivery rate

In all simulations, the average delivery rate is within 0.5% of the maximum. It is seen that there is no significant difference in delivery rate for epidemic routing and MORN.

Average delivery time

For both maps, MORN has a shorter average delivery time for 80 and 100 agents. This is considered to be because the message is delivered effectively by MORN. However, the average delivery time for MORN is longer than for epidemic routing for both maps in the case of 60 agents. Because the number of agents is not sufficient for the size of the map, message delivery cannot be achieved efficiently

Average hops

The average number of hops was fewer for MORN in all simulations, indicating that agents implementing MORN performed the routing and delivery of messages more efficiently. Therefore, we consider MORN to be effective in RCRS.

Comparison of the map

There are significant differences between the simulations for Berlin and Kobe for average delivery time and average delivery rate. In Kobe, the average delivery rate is close to 100% regardless of the number of agents. In contrast, the highest delivery rate for Berlin is 12.1% in the case of 100 agents. The average delivery time is around 60 steps for Kobe while it is around 140 steps for Berlin, became a lower close half of simulation time of 300step. We consider this to be influenced by the communication range and the size of the map. In a large map, the agent can only move a short distance relative to the entire map, so the probability that the agent is in contact with other agents is low and communication is thus reduced. This demonstrates that it is not possible to share information sufficiently using MORN on large maps.

4 Conclusion

In this paper, we focus on using MORN to reduce information sharing problems for voice communication in RCRS. Implementing MORN for agents in RCRS verified the effectiveness of this approach in an environment where there is division and delays in a network using direct communication as the main information sharing mechanism. The results of our simulation show that, compared with epidemic routing, MORN reduces hops and performs message delivery efficiently. Sufficient information sharing occurs in simulations on Kobe 's smaller map, but not on the larger map of Berlin. Consequently, MORN is not valid when the RCRS map is large.

5 Future

[Subsections follow]

Influence of the movement of the agent

In this paper, agents are assumed to follow random movement patterns. However, in actual RCRS rescue operations there will be some pattern in the movement of the agents. Thus, we need to investigate whether movement patterns have an impact on information sharing.

The effectiveness of a wide map

IThe experiments in this paper were conducted on maps with different features, namely those of Berlin and Kobe. However, the results of MORN to the larger map of Berlin were insufficient. Therefore, it is necessary to investigate whether agents that actively share information can help efficiently transport messages.

References

1. Fall, Kevin. "A delay-tolerant network architecture for challenged internets." Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications. ACM, 2003.
2. Vahdat. A, and Becker. D. Epidemic Routing for Partially-Connected Ad Hoc Networks. Technical report, Duke University (2000)
3. Yu Ding, Wendong Wang, Yong Cui, Xiangyang Gong, and Bai Wang, " Moving Target Oriented Opportunistic Routing Algorithm in Vehicular Networks, "International Journal of Distributed Sensor Networks, vol. 2013, Article ID 692146, 10 pages, 2013. doi:10.1155/2013/692146