Dynamic speed adaptive classified (D-SAC) data dissemination protocol for improving autonomous robot performance in VANETs

ABSTRACT In robotics, mechanized and computer simulation for accurate and fast crash detection between general geometric models is a fundamental problem. The explanation of this problem will gravely improve driver safety and traffic efficiency, vehicular ad hoc networks (VANETs) have been employed in many scenarios to provide road safety and for convenient travel of the people. They offer self-organizing decentralized environments to disseminate traffic data, vehicle information and hazardous events. In order to avoid accidents during roadway travels, which are a major burden to the society, the data, such as traffic data, vehicle data and the road condition, play a critical role. VANET is employed for disseminating the data. Still the scalability issues occur when the communication happens under high-traffic regime where the vehicle density is high. The data redundancy and packet collisions may be high which cause broadcast storm problems. Here the traffic regime in the current state is obtained from the speed of the vehicle. Thus the data reduction is obtained. In order to suppress the redundant broadcast D-SAC data, dissemination protocol is presented in this paper. Here the data are classified according to its criticality and the probability is determined. The performance of the D-SAC protocol is verified through conventional methods with simulation.

Introduction
In recent years, vehicular ad hoc networks (VANETs) are considered by many researchers since they show wider applications in many areas like intelligent transport system (ITS), passenger safety, infotainment and emergency scenarios. VANETs are a kind of mobile ad hoc networks (MANETs), but the difference is that the nodes move over the limited places. These networks have the nodes with high mobility and the nodes of network move in the same or opposite directions. Because of the high mobility of the nodes, the network topology becomes dynamic. In VANETs, the vehicles moving on road can establish two different communications, vehicle-to-vehicle (V2V) or vehicle-to-infrastructure (V2I) [1]. In V2V communication, the nodes (vehicles) send and receive message between them in peer-topeer (P2P) manner, while in V2I communication the nodes communicate with the surrounding communication units which are the nearest road side unit (RSUs). RSUs also work as the routers to send various information to the moving vehicles. Though VANETs yield many benefits to the drivers and others, there are certain issues to be met by the VANETs. The nodes moving on different roads cannot sometimes establish communication between them if there are blockades. Many VANETs employ a broadcast communication scheme to transmit the information to all nodes that come within the communication. This is known as a data dissemination process. In this scheme, the data are not preserved; the details of a certain vehicle, such as position and travel route, are publicly accessible by other vehicles. In a crash avoidance system and a traffic information system, the message must be transmitted to the vehicles travelling near to the source vehicle. However, if there are more vehicles in a region, the information from all the vehicles are shared and hence redundant data are communicated which exploits the channel radio bandwidth which is a limited constraint. Data collision also occurs when many vehicles retransmit the same data. This is referred as broadcast storm [2]. Moreover, the generated data must reach the all destination nodes within the specific time without any delay. Since the VANETs are dynamic network and the traffic patterns change frequently, the information also may vary. When the vehicle is reaching another area, the traffic pattern may vary. The information regarding accidents or obstacles should be communicated and reached to the vehicle in time critical fashion [3]. These reasons make the broadcast in VANETs as a great concern. Since the density of nodes (vehicles) varies for different times and on different roads, the broadcast scheme should function well in different scenarios. In a dense network, packet collisions and low packet delivery ratio problems occur. Many protocols are invented to reduce the broadcast storm concern in the traditional MANETs. However, there are only few for VANET and they are not much reliable and efficient.
The general solution to overcome these concerns is reducing the amount of redundant data. This process is accomplished by allowing only few vehicles to transmit data. However, in this process the high delivery ratio must be maintained [4]. In the existing method, the vehicles need beacons to retrieve information from the neighbouring vehicle. Conversely, beaconing has some disadvantages like bandwidth exploitation, delayed data packet and higher network congestion [5]. Even beaconing process also produce large load in the network. If it produce large load in the network, this process is referred as background traffic [6]. Hence, when using the beaconing process for VANETs, it is necessary to employ suitable data dissemination methods to keep the beacons size at a particular range, so that the bandwidth exploitation can be decreased. In VANETs, broadcasting the flooding process is the basic broadcasting approach in which the source vehicle transmits the data to all of its neighbouring vehicles. In multihop transmission, all the nodes receiving data from the source node will reroute the same to their one-hop neighbouring nodes. In the simple broadcast scheme, when all the vehicles in an area transmit the data simultaneously, many data are transferred and collisions may occur. This problem is more for high-density networks. Because of the transmission of many data, the utilization of bandwidth increases. In Figure 1, the broadcast storm problem is depicted where node A starts first to transmit the data and the data are received at nodes B and C. Afterward, these nodes retransmit the data if the data were not transmitted by them previously. Similarly, node D retransmits the data if no collision occurs. This process increases the cost of the communication system and the following issues will happen. Many protocols are proposed for solving broadcast storm problems in MANETs and they give efficient results. However, they do not provide better results for VANETs since they have the mobility features. In Section 2, the existing protocols for mitigating broadcast storm issues are described. The aim of this work is to mitigate the broadcast storm problem in multihop VANETs. We presented the dynamic speed adaptive classified (D-SAC) data dissemination protocol. In this work, the traffic flow theory presented in [8,9] is employed to determine the traffic details. This theory states that the negative correlation exists between the speed and the traffic density. In employing vehicle density to determine the traffic condition in an area, the details of nearby vehicles are required, whereas the employment of speed in determining the traffic does not require the details of other vehicles. Based on this concept, the probability of data transmission in VANET is determined by considering four different factors, namely, the speed of the vehicle, source vehicle distance, label of message or type of message and time of occurrence of an event. The proposed work and the advantages of the proposed method compared with the existing works are described in Section 3. Section 4 explains the results obtained from the proposed work.
The contribution of proposed work is as follows.
• Since a vehicle obtains the current traffic scenario from its speed, the transmitted bytes are reduced. • Broadcast overhead (BO) is reduced through broadcast suppression, which is achieved by fixing probability for forwarding data according to the message type, message occurrence time, vehicle and distance. Thus the unnecessary data broadcast occurring even after the event are vanished or can be reduced. • The packet collisions are avoided through timebased dissemination since the time-based method allots a different time for each vehicle to relay the received data. Moreover, the data are discarded if it is forwarded previously. Thus the performance of the network is improved.
The work is organized as follows. Section 2 describes the previous works related to the mitigation of broadcast storm problem. The proposed protocol and the relevant computations are explained in Section 3. Section 4 describes the simulation process and the results obtained from simulation.

Related works
Many protocols were presented in literatures to reduce the broadcast storm problem in a high-density network. These protocols can be typified into senderoriented protocols and receiver-oriented protocols. In sender-oriented protocols, a sender node detects the relay nodes for broadcasting packets, whereas in receiver-based protocols, the receiver node takes decision whether to transmit the packets or not. In works [10][11][12][13], receiver-based broadcast protocols have been explained. In these types of protocols, all of the redundant broadcasts are not eliminated. In addition, as these protocols employ a probabilistic method, the reliability of the network is not ensured, particularly in the case of sparse network. Hence the receiver-based broadcast protocols do not suit well for VANET applications where reliability is momentous. In [14], a multipoint relay (MPR) broadcast protocol was presented. In [15], connected dominating set-based broadcast protocol is presented. In both of these works, the authors did not consider the node mobility while selecting the relay node. Therefore, the relay node selection process becomes sub-optimal and packet loss will occur due to the moving nodes. In work [16], the authors presented enhanced MPR broadcast protocol that allows only several relay nodes to rebroadcast a message. This protocol employs an acknowledgement method to note whether the message is received by all the selected receivers and retransmitted on the occurrence of packet loss. The strength of received signal is not taken into account in selecting the relay nodes. The performance of this protocol is reduced when fading happens. In addition, the receiving node should transmit acknowledgement signal to the source node. This problem leads to increased overhead in the high-density network. Sahoo et al. [17] presented a protocol in which the node located far away in the selected direction is chosen to rebroadcast the message. But in a fading channel, packet loss happens when this method is used. Hence many factors, such as inter-vehicle distance, mobility and signal strength, must be taken into account for selecting relay node. In a VANET broadcast, retransmission process is necessary due to some factors such as the moving vehicles, data collisions and random loss occurring in fading channel. In enhanced MPR broadcast protocol, a source node retransmits a message if a receiver node did not receive the message in a fixed time period. This state can be checked by the protocol with the help of explicit ACK messages. Hence, the overhead problem increases particularly in the case of high-density network. Hence, the MAC layer contention time at every node increases. Thus, more delay occurs and a message becomes useless though it is received after some time. Hence, a lightweight retransmission method is considered.
The protocols presented for obtaining lightweight solutions in VANETs are classified into types, probabilistic approach and the Delay-based approach. In the probabilistic approach, rebroadcast probability set to the different receiving vehicle is different. Hence, in this only some vehicles broadcast data and so data redundancy, overhead and data collisions are reduced. The major challenge of the probabilistic approaches is to find out an optimal probability assignment function to keep the delivery ratio high. Simple probabilistic broadcasting approaches assign a fixed probability to the vehicles, whereas complex probabilistic approaches assign dynamic probability values. In [10], weighted p-persistence probabilistic broadcast protocol is presented in which distance of the node from the source node is selected as a factor to compute probability of packet broadcast. In this method, the vehicles located far away are given higher probability. However, in this work, the traffic density details are not taken into account and hence the data redundancy issue happens when network density is high. In paper [18], another probabilistic broadcast protocol is presented in which traffic density is considered. In this method, the traffic density is determined by counting the number of onehop and two-hop neighbouring vehicles. Mylonas et al. [13] first presented speed adaptive probabilistic flooding (SAPF) technique of utilizing the speed of vehicles in the network for probabilistic broadcast approach. Linear approximation of data is used to map the speed of the vehicle to the broadcasting probability. The authors compared the probability function with typical flooding method and a valid comparative analysis was not performed. Besides this, the broadcasting overhead was not considered. Conversely, in delay-based broadcast, various waiting delays were set to the receiving vehicles in the VANET. In this method, the vehicles with less delay would rebroadcast first. Delay-based broadcast protocol is also known as broadcast suppression approaches. In this method, when a vehicle received a duplicate copy of message, it stopped rebroadcasting the same message since it indicates that the other vehicle was involved in the job. Therefore, redundant rebroadcasts are reduced. In [18], slotted 1-persistence is presented where the vehicles are allotted to different time slots according to the distance to the source vehicle. Here the farther vehicles are assigned to the slot having less delay for broadcasting. In this method also, the traffic density is not taken into account. Hence scalability issue will happen when the network density is high because of redundant data. In some works, the probabilistic and delay-based approaches are combined and assign the farthest vehicles with shortest delay with a fixed probability to rebroadcast. In [10], slotted p-persistence approach is given, where messages are rebroadcasted based on a pre-computed probability and a waiting delay. This method also did not consider the traffic density. Distributed optimized time (DOT) [19] is delay-based rebroadcasting approach in which timeslot density control is involved. But this work did not consider the actual traffic in the network. The density of timeslots assigns the number of vehicles in each slot. DOT needs beacons to collect the information regarding the nearest vehicles. The increase in beacon size yields high bandwidth exploitation. In [20], an efficient data dissemination protocol is presented without beaconing overhead. In this scheme, a sweet spot is defined in an area of interest (AoI) and the vehicle in the sweet spot started to disseminate the message. The transmission region is considered as a circle shape area and it is partitioned into four quadrants. For every quadrant, one sub-region is assigned which is termed as sweet spot. If no vehicle presents in the sweet spot, the next vehicle located away from the sweet spot will broadcast the data. This method can give high delivery ratio, but the high communication overhead still exists. Maia et al. [21] presented HyDiAck protocol for dense and sparse networks. This method cannot reduce the redundant data, but it gives high delivery ratio. Another disadvantage is the requirement of one-hop neighbour data. In [22], Adaptive Forwarding message and Cooperative Safe driving (AFCS) approach are presented in which traffic density is considered. The traffic details are found through exchanging information among the vehicles through beacons or through RSUs. In [23], autonomic dissemination method (ADM) is proposed where the vehicles are allowed to dynamically change its broadcasting according to the network density and based on the priority level of packet to be sent. The advantages of this method are that the latency and radio interferences are reduced. However, the shortcoming is that the method did not reduce the redundant data. In [24], advanced diffusion of classified data (ADCD) protocol is presented to manage data dissemination in VANETs. In this method, the received message as the input message and compute the time of reception in receiver end. The authors used Markov chain to obtain the optimal number of broadcasting nodes. The advantage of this method is that the overhead is maintained as constant even the vehicle density varies. The conventional schemes for data dissemination in VANETs produce communication overhead, scalability issues when the vehicle density is more. Though the methods presented in [10,20,21] yield high data delivery ratio, they cause high dissemination overhead. In literatures [19,21,22,23,25], though redundant data are reduced through beacons some problems, such as bandwidth exploitation and increased congestion, may occur. When beacons are used, the congestion will occur in high density since the beacons broadcast the message many times. Thus beaconing produces high load on the VANET.

Proposed method
In the proposed method, when an incident occurs and it is required to be transmitted to the participating vehicles in the network, the source vehicle sends the event occurrence along with some other information. On receiving the information from the source vehicle, the subsequent vehicle will assign a probability for rebroadcasting the message according to the four factors, which are described later. Since in this work speed adaptive broadcast technique is utilized as in [7], the traffic regime can be retrieved using the speed of the source vehicle only and hence the vehicle no need to gather message from more vehicles to determine the traffic regime.

Materials and methods
Autonomous robots like a VANET consider three different models: road layout, mobility and communication. Linear road topology of multiple lanes is assumed as the road layout in this model, which contains highways and straightway roads. For mobility modelling, a simple macroscopic model is taken for mathematical analysis. In this model, the activities of one parameter of traffic flow alter according to the activities of another. The Green shields model presented in [9] explains the traffic flow using the speed-density relationship as road traffic as the traffic in a region always depends on certain features like flow rate, the traffic density and the average speed. For analysing the performance of the proposed method using simulation, the traffic scenarios are generated using SUMO [26]. In establishing vehicular communication, an on board unit (OBU) is interfaced with each vehicle. Each OBU contains physical layer, MAC layer, networking layer and application unit. The vehicle can establish communication through its OBU with vehicles in its communication range. In this work, V2V communication is considered and the communication with RSUs does not occur in this work. The global positioning system (GPS) is employed to obtain the information regarding vehicle location. In vehicular networks, the disseminated data are the type of WAVE short messages (WSM) [26] containing the information like position, speed and acceleration of vehicle. The message has eight fields and the total size of the message is computed by adding the bytes consumed by each field. The information reported along with the message are listed as follows.
• The position of the place where the event has occurred.

Data dissemination model
Consider a highway road lane shown in Figure 2, where the vehicles detect a hazardous incident and transmits the message to alert the following vehicles through multi-hop ad hoc communications. This is to alert all of the following vehicles travelling in the area near to the locationA. The number of vehicles in the dissemination area is taken as v. Whenever a vehicle in the area collects a message, a probability is determined by the vehicle to decide whether the message is to be forwarded or not. The probability is determined based on four factors. They are speed of the vehicle, source vehicle distance, label of message or type of message and time of occurrence of an event.
In this section, the average number of informed nodes is determined by using the analysis made in [27] for single a broadcast cycle. The probability that a node rebroadcasts a message is denoted using α which is less than one always. The vehicle density is represented as γ which denotes the average number of vehicles in an area. The distance between two neighbouring vehicles is exponentially distributed with γ . The probability that the number of informed nodes in an area is denoted by S(n). Similarly, the probability that the number of connected forwarding nodes equal to n is denoted as P r (n). The length of the area is denoted as D and the transmission range of all vehicles in the area is equal and denoted by R. In this analysis, the number of nodes in an area is denoted as n * which is equal to γ D. P r (n) is expressed as The average number of informed nodes S(n) is obtained by using the following equation: The probability that a vehicle is informed irrespective of the position can be obtained as shown in (3), whereSdenotes the average number of informed nodes and γ D denotes the average number of nodes in the area:

Traffic regime detection
Since the data dissemination overhead happens when all the nodes forward the received data, only some selected nodes must forward the data. In this work to select the nodes, the probability is assigned to every node based on the several factors. In a high-density area where there are more number of vehicles, the dissemination overhead is high. Hence it is essential to allow very few vehicles to relay the message. To achieve this the probability is assigned by considering the speed such that the probability for a vehicle to forward the message is computed as a fraction of the vehicle density. As provided in [7], the traffic density is obtained from the own speed of a vehicle. Thus using this model the traffic in an area can be determined without the knowledge of the number of nearby travelling vehicle. In highdensity roads, the vehicles must be driven in low speeds whereas in the low-density roads the converse will happen. Taking this notion, the speed-density relationship is presented in [9]. Thus using this model, since the speed of the own vehicle can provide the traffic information, the message retrieval from the neighbouring vehicle to get the traffic regime is avoided which in turn reduces the dissemination overhead. In addition, the probability for a vehicle to forward the message is computed. The fundamental traffic flow equation is given as where Q is the traffic flow, V is the average speed and TD is the traffic density. The traffic condition of a road can be found by analysing the speed ratio given in the following equation: where V r is the speed ratio, V is the current average speed on the road and V f is the free flow speed (maximum allowable speed).
In [9], the speed and density relationship is given as where d denotes the current traffic density and d j denotes the density when traffic jam occurs. Thus it is inferred that when V r reaches zero, the traffic jam occurs, while on reaching value 1, the traffic density is low and the vehicles move with the free flow speed. The traffic organization as shown in Figure 3.

D-SAC data dissemination protocol
The proposed D-SAC data dissemination method assigned a probability at the receiving node based on the four factors as described above. The speed of the sender vehicle is received along with the message. From the speed, the current traffic density on the road is determined using the relationship shown in (6). In determining, whether the received data to be forwarded by the receiving vehicle, the first and foremost factor must be considered is the message type. Based on the type of received message the dissemination is divided into three kinds, namely critical data dissemination, semi-critical data dissemination and non-critical data dissemination. After classifying the messages, the probability is assigned based on the class.

Critical data dissemination method
For critical data dissemination, the forwarding probability is determined similar to the dynamic speed adaptive broadcast (D-SAB) method. The critical data are the events that are lasting for long time, such as damage on the road, road extension works, and landslides. The probability of a receiving vehicle i to forward data at time tis given by the speed ratio as shown in the following equation: where V(i, t) is the current speed of receiving vehicle i at time t. Based on the speed, the probability is determined for the critical data dissemination. Equation (8) implies that the probability to forward the data is low when the road is congested while the probability is high on the free road. Thus the redundant communication occurred by many vehicles where the forwarding message is reduced. The critical data should necessarily reach to the subsequent vehicles to avoid the hazardous events. Upon receiving the message, the received vehicle forwards the data after some delay. In this dissemination method, each vehicle is assigned to a timeslot which is computed at each hop based on the speed ratio. Timeslot is the time period for which a vehicle must wait before deciding to forward the received message or discard the message. From the speed of the neighbouring vehicles, the received vehicle set the total number of slots. Each time slot is assigned with certain waiting delay. In addition, the delay is assigned by considering the type of the road area. In rural area roads, less delay is given since they are less congested, whereas in city roads, more delay is given to each timeslot to avoid transmission overhead since the traffic is more in city roads. Since the forwarded message transmits the message along with its current speed, the receiving vehicle can able to detect the current traffic state of the road. When a message is received by a vehicle, it checks whether it receives the message before, using the message ID. If the message is already scheduled in the slot to be forwarded by this vehicle, it suppresses the broadcast. Adding to this the received vehicle computes the total number of timeslots and detects its suitable timeslot based on its location. Then it fixes delay according to the road area to schedule the retransmission. In this D-SAC, the nearest vehicle is assigned with less delay and given high priority to forward the message. Hence, since the other vehicles have more delay, they will suppress (cancel) the broadcast on receiving duplicate message. Thus the redundant transmissions are reduced. The timeslots are allocated with enough time to the timeslots for obtaining efficient broadcast suppression and hence it can have enough time to decide either to forward the message or to discard the message. The total number of timeslots is obtained by using the following equation: where m = R/w and denotes the maximum number of timeslots. R and w denote the transmission radio range and the minimum size of a single timeslot which is set by summing the length of vehicle with the safety distance between two vehicles. Thus under hightraffic regime, more number of slots are obtained from Equation (9) and hence only few vehicles forward message. Conversely, the number of slots is less in low traffic regime. In this method, it is assumed that the speed of the vehicles in the single hop transmission is the same whereas it changed in next-hop transmission. The current speed of the vehicles is obtained from the data received from the sender vehicle (i.e. speed of the source vehicle in the first hop and relaying vehicle in the subsequent hop). The width of timeslots is allocated to be equal over the transmission range for all vehicles and the corresponding timeslot of a receiving vehicle is detected based on the location information of the vehicle. The time delay at each time slot is computed using (10) such that the nearest vehicles are allocated to less delay: where d k is the delay at a timeslot k, S k is the slot number, τ is the minimum one-hop delay that depends on the propagation delay, β is 0.5 for rural roads and 0.8 for city roads: where range denotes the distance covered by the forwarding vehicle and dist denotes distance between two vehicles. Thus in computing delay to allocate for each timeslot, the parameter β is given with two different values according to the type of road. Figure 4 shows the D-SAC-based critical data dissemination, where the source node transmits the message on the occurrence of an event to its one-hop neighbours. Then, based on D-SAC protocol, the vehicles determine whether to forward the message or suppress the message. Each vehicle in a zone is allotted to the corresponding time slot with delay according to the traffic regime. The nearest vehicle to the source vehicle in zone 1 forwards the message to its next-hop vehicles. The other vehicles check whether the data are scheduled to be forwarded and discard the message because of the broadcast by forwarding vehicle. In zone 2, the nearest vehicle to the forwarding vehicle forwards the message to its next-hop vehicles. Thus the message reaches all the vehicles travelling in the area. Algorithm 1 shows the D-SAC data dissemination protocol.

Semi-critical data dissemination method
For semi-critical data dissemination, the time of occurrence of event is considered in computing the probability. The events classified under semi-critical case are the events that may disappear or cleared off within some time period. Example for semi-critical data is the accidents, vehicle collision, traffic due to breakdown vehicle, traffic light failure. The probability of a receiving vehicle i to forward data at time t is given by the followingequation: Equation (12) denotes that the probability to forward the data is more if the difference between the times is less. The more difference between message received time and message occurred time denotes that the message is occurred long time ago. This in turn implies that the event may be vanished. Hence the probability is less. Thus the vehicle discards the message if the event is vanished and suppresses the broadcast. After computing the probability, as in the case of critical data dissemination, D-SAB technique is employed. The timeslots are allocated based on the speed of the sender vehicle and the delay time for each slot is computed dynamically at each hop using Equation (10). Thus the vehicle  suppress the broadcast of semi-critical data if the data occurred long time ago. If the occurred event lasts for the time duration equal to two-hop propagation delay, then two relaying vehicles forward the message and the next vehicle suppresses the message, which is shown in Figure 5. Figure 5 shows the D-SAC-based semi-critical data dissemination where the source node transmits the message on the occurrence of an event to its onehop neighbours. Then, based on D-SAC protocol, the vehicles determine whether to forward the message or suppress the message. Each vehicle in a zone is allotted to the corresponding time slot with delay according to the traffic regime. The nearest vehicle to the source vehicle in zone 1 forwards the message to its nexthop vehicles. The other vehicles check whether the data are scheduled to be forwarded and discard the message because of the broadcast by forwarding vehicle. In zone 2, the nearest vehicle to the forwarding vehicle forwards the message to its next-hop vehicles. Thus the message reaches all the vehicles travelling in the area. On each broadcast, the forwarding vehicle checks whether the event exists or vanished. Based on this, the probability is assigned to each vehicle as in (12). If the event is vanished, the forwarding vehicle suppresses the broadcast.

Non-critical data dissemination method
In non-critical data dissemination method, the probability of a receiving vehicle i to forward data at time t is given by the following equation: where h represents the current hop number. Thus, the forwarding probability of farthest vehicle from the source vehicle reduces. After computing the probability, as in the case of critical data dissemination, D-SAB technique is employed. The timeslots are allocated based on the speed of the sender vehicle and the delay time for each slot is computed dynamically at each hop using Equation (10). Thus the vehicle suppresses the broadcast of semi-critical data if the data are forwarded by other vehicles. Since the message is not critically to be forwarded, it does necessarily not to be reached to a long distance. Hence, only the vehicles near to the location of the event forward the data. Thus, the probability decreases when the number of communication hops increases. In addition, if the one-hop propagation delay is more the probability is less. Thus, the message is forwarded in at least two to three hops of communication.

Result and discussion
In this section, the proposed approach is implemented and validated by simulating autonomous robot system in VANETs environment with NS2. The simulation parameters are given in Table 1 (14) M expected is computed from total number of messages sent: BO is measured as the ratio of the total number of duplicate messages to the number of received messages: Average dissemination delay is computed by measuring delay at every vehicle and then averaging it over the network. The simulation results give the performance of the proposed method over the existing methods such as P-SAB, slotted 1-persistence, G-SAB weighted-p persistence method [7]. Figures 6-9 show the comparative analysis of the performance parameters such as data delivery ratio, average dissemination delay, BO and number of hops. In Figure 6 data delivery ratio in various traffic scenarios us plotted for different methods. It is observed that all the methods almost provide the maximum delivery ratio. It is also inferred that the delivery ratio is less in congested scenarios while it is high in low traffic scenarios. Here in the weighted-p persistence method, the delivery ratio is less. Figure 7 shows the comparative analysis of average number of hops propagated. The number of propagation hops should be minimum for the improved performance. In the weighted-p persistence method, the average number of hops is more. In the proposed scheme, the data are delivered to less number of hops. On an average, the data are delivered for 2-4 hops, from the sender side to the receiver side in the proposed scheme. In addition, it is found from the graph that the number of hops is reduced when the vehicle density increases, which implies that the data are transmitted for only two hops in high-traffic scenarios. Figure 8 depicts BO. When compared with the P-SAB, weighted p-persistence, slotted 1-persistence, G-SAB reduces BO. In the proposed scheme, since high level of broadcast suppression is obtained, the BO is reduced significantly. The impact of the classification of message in BO reduction in shown in Figure 10. From Figure 10, it is observed that the BO is more in critical data dissemination compared with the other two types, since the critical data must be forwarded with higher probability. For lower traffic regime, overhead is low since the number of vehicles is less. In contrast, overhead is large in medium traffic. All at once, it should be observed that the overhead is constant in semi-critical type and non-critical type, irrespective of the traffic regime.    Figure 9 compares the average delay over the entire network, for different methods. In the weighted ppersistence method, the delay is more. Though considerable reduction is achieved in the exiting methods like slotted 1-persistence, G-SAB and S-SAB, in the proposed method, the performance is still improved by achieving very small delay of 50-100 ms on average.   Average of number of hops for the proposed scheme is analysed and compared for various classes of message. The graph in Figure 11 shows the comparison, where the number of hops is more in critical data dissemination. With respect to the traffic regime, the number of hops for critical data dissemination is more for medium traffic regime and less for higher traffic regime. The number of hops is slightly reduced in semi-critical data dissemination since it depends on the time occurrence of the event. Similar to the case of critical data, the number of hops is more for medium traffic regime and less for higher traffic regime. For non-critical data dissemination, the average number of hops is 3 for lowtraffic regime and it nearly approaches 2 for high-traffic conditions. Thus in the proposed scheme, the BO, average delay and average number of hops are reduced considerably compared with the previous methods.

Conclusion
Autonomous robot in VANETs the broadcast storm is considered as a significant concern which disrupts the performance of the network. Concerning VANETs, it is essential that the BO issue should be minimum along with the assurance of improved data delivery ratio. It is hard to attain high delivery ratio along with the maintenance of small delay. To achieve the objectives we presented D-SAC data dissemination protocol, which forwards the data according to different factors. The proposed protocol is implemented and the simulation results verified that the proposed technique decreases the end-end dissemination delay and BO. It is also proved that the delivery ratio is high. In addition, by classifying the data based on their criticality, the data redundancy is still reduced. In semi-critical data, the probability for rebroadcast is computed based on the time of event occurred. Thus, the data are discarded after certain hops. Therefore, the number of hops also reduced. From the results, it is observed that the BO does not increase under high-density scenarios, which proves that the broadcast suppression is improved. The impact of data classification is analysed through the number of hops. For critical message it should be forwarded to more vehicles hence it is propagated over more number of hops. In semi-critical data, the number of hops is proportional to the time of event occurrence and the propagation delay.

Compliance with ethical standards
Disclosure of potential conflicts of interest: Author 1 & 2 declares that they have no conflict of interest. Research involving human participants and/or animals: All procedures followed were in accordance with the ethical standards of the responsible committee on human experimentation (institutional and national) and with the Helsinki Declaration of 1975, as revised in 2008. Informed consent: Informed consent was obtained from all patients for being included in the study


REVIEW ON SHORTEST ROUTE PROBLEM IN URBAN NETWORK SYSTEM

The shortest path problem has been studied for over 40 years in diverse fields and transportation. It is one of the fundamental rules that is being used to find a minimum distance to reach the destination, with minimum time consumption in a cost effective manner. In the modern world, it is very useful in planning the efficient shortest routes that is essential for transportation, telephone network, electricity power supply network, gas pipeline network, water supply, drainage network system etc. The complexity of network, cost and time required for networking is increasing in different kinds of network systems and identification of shortest paths plays pivotal role. In graph theory, the number of algorithms can be applied for finding shortest paths in a graph based network system. It reduces complexity of network routes, cost and time to build and maintain network based systems. In this review of literature, some of the gateways in finding out the shortest path that have been developed in the past in different networks are highlighted. The goal of this study is to select a cross-section of approaches in identifying the shortest path in different fields of research usingGeographical Information System (GIS) and (Global Positioning Systems) GPS. Keywords—Shortest path, Algorithms, GIS

INTRODUCTION
Shortest path problem is very significant in the study of transportation and communication network. Travelling is important part of daily life. Therefore, the optimal shortest path (SP) to the particular destination becomes inevitable to reduce costs, losses in productivity, pollutions, and risks etc. An appropriate algorithm is used to find the shortest path between two known vertices is Dijkstra's algorithm, which waspresented by the famous Dutch computer scientist Edsger W. Dijkstra.This was recognized as the optimal algorithm that can be applied to obtain the shortest path from a vertex (node) to any other vertex.
In this paper, an improved Dijkstra algorithm will beused to constraint function and develop this algorithm by using priority queue and determine the source by GIS & GPS .This Application helps to find out the shortest path to road network system from user location along with time, distance and all roads related information. It is helpful in terms of reducing travel time, effort, and cost. GIS and GPS based route network system is considered as a guide for users from the origin to a destination in the Bengaluru city. There has been a surge of systematic investigation in shortestpath algorithms due to the problem's numerous and diverse applications. These applications include network routing protocols, route planning, traffic control, path finding in social networks, computer games, and transportation systems, to count a few. In recent years there has been an increasing interest in the shortest path problem for use in various transportation engineering applications. Generally, in order to represent the shortest route problem graphs are used. There are a number of transportation applications which require the use of a shortest path algorithm rather than one of the standard and most favourable optimal algorithms. The objective of this survey is to present a breakdown of the shortest-path with GIS and GPS through an appropriate classification. This classification aims to help researchers, practitioners, and application developers to understand how each shortest-path works and to help them decide, which type or category of shortest-path algorithms to use given a specific scenario or application domain.

II. GIS APPLICATION IN TRANSPORTATION:
GIS are becoming more widely used in transportation planning agencies, especially among metropolitan transportation organizations. In many developed countries, highway maintenance management and urban planning is becoming a critical issue. Many more authorities are now able to use GIS for Highways and transport management, due to falling price of GIS software and friendliness. A popular methodology of modelling road networks is in the form of a Geographical Information System (GIS). GIS is framework for gathering, managing, and analyzing data. A lot of transportation related applications are developed using Arc-GIS.Arc-GIS is the industry leader in modelling of complex road networks. However, lack of appropriate data for GIS remains a chronic problem. In our approach, we develop the road network system on GIS platform that can provide multiple route options given a start and end location. The key idea is to find a cost optimal solution for two locations using Dijkstra's algorithm and rerun the algorithm by increasing the travel cost of one segment or the whole path, forcing the search algorithm to an alternative solutions.

III. RELATED WORK
Here an attempt has been made to review the literatures related to finding shortest path in various applications. There are number of works carried out. An effort has been made to bring the advanced and up to date review articles / papers published in the journals and books. Several methods have been developed in transportation engineering applications to find an optimal path. These methods could be mathematical model computations or classical algorithms (Bellman, 1958;Dijkstra, 1959). Dijkstra algorithm (1959) is one of the most famous methods to find the shortest path for a deterministic network. Many research works considered the road network as a deterministic network where the travel time is a constant value. Typically, there are two types of short path problems: the single shortest path problem which aims to find the shortest path from a given source to all other vertex in the graph, and all-pairs shortest path to find out the shortest path from every source in a network to every other destination in the graph (Baras and Theodorakopoulos, 2010). A conceptual architecture of a traveller information system for a metropolitan city in India was proposed by Pal, Sarvjeet (2011). This web GIS based system, namely Computerized Traveller Information and Decision Support System (CTIDSS) will not only assist travellers in route butalso provide prevailing roadway and traffic condition and schedule of operation of public transportation in real time. A path finding algorithm for transit network is proposed to handle the special characteristics of transit networks, e.g., time-dependent services, common bus lines on the same street, and no symmetric routing with respect to an origin/destination pair. The resulted path is a schedule coordinated fastest path for given constraints including origin and destination with a planned departure time or an expected arrival time. A GIS based information analyses and system was created by Amrapali C (2014) tosolve the traffic problem so that patients can find out the information about necessary treatment in a hospital based on a specialist service provided. The main objective of this paper was to integrate information on the actual position of health centres in Aurangabad city with the service and facilities provided. Further, the author demonstrated the function of the shortest path in a network analysis for finding out the nearest health facilities from patient's location. The base map of the study area is collected while the coordinates of the health care centres obtained in the field using Global Positioning System (GPS). These data incorporated into GIS environment and analyzed using Arc-GIS 10.0 software. Kumar (2014) discussed the network analysis tool to measure the efficiency of services in terms of time and distance. In his study, the optimal service area such as hospitals, schools and fire stations were defined based on the time and distance and analyzed the gap that exists in the allocation of these services in city area. So, this study had used GIS tools which are more relevant for different type of network analysis especially for transport planning for different purposes like shortest path, closest facility, service area and also for the best recourses allocation and for the creating of emergency route services, so this type of analysis is very crucial for the transport based planning.  (2015). This is particularly relevant for active commuting, where actual routes travelled may show high levels of agreement with modelled shortest routes. However, the predictability of the commute route clearly depends on the mode of travel used. Demirel (2016) demonstrated the opportunities of spatio-temporal analyses within dynamic urban road network management, where the concepts are supported with a case study from Istanbul Metropolitan Area. In the proposed methodology, the speed information retrieved from detectors was associated with the Open Street Map and quickest paths were simulated within determined time intervals. Different shortest routes are proposed to users in various time spans via incorporated speed information and network analyses. For the same origin and destination, 2.5 minutes difference is observed within the study area. The results were promising, where the added value of this study is presenting an approach for integrating various spatio-temporal data to aid dynamic urban road network management. In a study Idhoko K.E (2016) appliedGIS tool is applied to answer basic generic questions on how accessible one location is to another. The geospatial datasets were geo-referenced and link with attribute database using the Arc-GIS software. Analysis such as; spatial search for a particular road; the shortest route between two locations by applying concept of road network analysis was employed for effective emergency response services as well as solving travel salesman problem and improving the standard of life within the study area. Shortest path from the user location to the University to minimize the travelling distance was analysed by Saeed (2017)analyzed the. The author implemented Arc-GIS and Dijkstra's algorithm that find the shortest path between two points depend on the route length. The useof GIS Cloud Publisher for Arc-Map extension enables to publish the maps from Arc-Map to GIS Cloud. Amoako (2017) dealt with the problem of finding shortest paths in traversing some locations within the Kumasi Metropolis in the Ashanti Region of Ghana using Dijkstra's algorithm. The updated route was sent via a dynamic routing system for all vehicles in urban road communication system to vehicle driver to change his network has some special considerations which are the route. School bus routing and scheduling could be treated as a multiobjective Vehicle Routing Problem (VRP) that helps to transport the students in the safest, most economical and convenient way was proposed by Hashi(2017). The result of this research helps the Transport Management to design a dynamic shortest and fastest route for the vehicles. The GIS helps to identify the real-world pickup stops according to the concentration of the students in a particular area as well as to visualize the current optimum route and pickup points. Zhu (2017) proposed a mathematical model for mini-bus stop spacing based on Voronoi Diagrams to minimize the passengers' total travel time. In the optimization model, the Cartesian coordinate system was defined to calculate the travel time from origins or destinations to mini-bus stops. The model was a non-linear and constrained programming problem, which is modified WilsonHan-Powell Sequential Quadratic Programming (SQP) technique with properties of global convergence and stability used to solve this problem. However, the optimal mini-bus spacing calculated by the model was relatively ideal. The results have shown that there was an optimal minibus stop spacing of 330 m, which was used to locate minibus stops with the proposed modification methods, proving simple and practical. Babiker (2017) illustrated that GIS based network analysis was more helpful tool for solving transportation problems, road congestion and terrific jam. It was being dominant in most planning and transportation sector, and provides effective cost for agencies even small ones. Further, the study showed that the high resolution IKONOS image provided an cost effective and less time consuming as data source to find out the best and short route between locations, determine the closest facility depended on arrival time and the car speed, determine the area serviced by certain facility which helped in the future planning and support decision makers to determine the area needed for new facilities to build and compare alternatives. Ride-Sharing is an efficient way to improve the traffic situation by lowering the number of necessary vehicles when people travel together was proposed by Paul Czioska (2017). However, in a real city environment, it is necessary to consider the local situation to determine convenient meeting points, enabling a secure parking and boarding and making the waiting time as comfortable as possible. The evaluation shows that the user satisfaction as well as the amount of matched participants is dependent on the amount and spatial distribution of meeting points. However, a saturation effect can be observed, showing that a limited amount of labelled meeting points in a city is sufficient to meet the demand. Locations with facilities like light, shelter and seating can further improve the overall satisfaction of the user. An assessment of characteristics, spatial arrangements, and impedance of the roads through digital road map and database was discussed by Chigbu(2017). Data analysis included layers and database creation, link impedances that indicate area with low, moderate and high efficiency route and proximity analysis that indicate areas with difficulty accessibility due to poor planning of infrastructures. The use of geo-database, digital road map for the evaluation of road transportation and infrastructure planning such as electricity was recommended which will help to solve long lasting problem of light within the area. Fitro(2018)presented the problem-solving technique in the shortest path search based on Geographic Information Systems using combination of methods that are node combination algorithm and Dijkstra's algorithm. Based on the results of tests that have been carried out the technique succeeded in finding the optimal route in the case study route in Taman Sub district, Sidoarjo Regency, East Java, Indonesia. The results presented can be the distance traveled and travel time from the starting point to the end point. The neutrosophic shortest path (NSP), where edge weights were represented by IVNS was described by Broumi1 (2019). The advantage of using IVNSs in NSP has been discussed in this paper. The classical Bellman's algorithm has been modified by incorporating the uncertainty using IVNSs for NPP between source and destination nodes. The main goal of this work was to describe an algorithm for NSP in the neutrosophic environment using IVNS as edge weight. The algorithm proposed in the study is very effective for real-life problem.

IV. CONCLUSION AND SUMMARY
This literature review has shown that GIS is a broad field which covers many applications of scientific knowledge for practical purposes and it they plays a significant role in the technology era. The large growth of technology and GIS applications help people in daily life in various domains. Theshortest path solution will be considered as an excellent guide for users to benefit from its services by decrease time, cost, and effort in finding out the shortest path to the various transportation services from user locations, most appropriate roads, time and distance. The improved Dijkstra algorithm is better than traditional algorithm because it reduces nodes number and consuming time. Apart from this, the application of GIS will have the possibility to offer the following benefits: improved safety, efficiency, mobility, accessibility and intermodal connections. The beneficiaries' areas are optimal path, emergency service, data collection, environmental issues and traveller information. This paper has presented a wide range of GIS technique where in research journals in this field were collected, classified and interpreted result. Further, this review addresses the use of GIS in Sustainable Urban Transport performance, particularly on traffic and road network studies. In addition, this review enables researchers to understand the overview of application of GIS in finding all shortest route and also provides researchers with information on GIS areas in which further detailed investigation may be needed.

V. RECOMMENDATIONS
There is an urgent need for transportation planning and management in urban network by the application of Geographic Information System, because the number of vehicles on roads at certain peak periods of the day leads to lot of traffic congestion. The time periods between 7.30 am to 10.30 am and 3.30pm to 8.30pm in the major cities of India e.g. Bengaluru, Chennai, Hyderabad, Delhi etc., require alternative routes to overcome traffic jams. This problem can be resolved by the application of GIS, which help the users to decide the best possible routes from his own place. Government should ensure free flowingtraffic for people's safety and easy mobility.

VI. ACKNOWLEDGEMENT
The support from Dr.A.M. Ramesh, Chief Executive Officer from Karnataka Science and Technology is gratefully acknowledged.


A High-Quality Multilingual Dataset for Structured Documentation Translation

This paper presents a high-quality multilingual dataset for the documentation domain to advance research on localization of structured text. Unlike widely-used datasets for translation of plain text, we collect XML-structured parallel text segments from the online documentation for an enterprise software platform. These Web pages have been professionally translated from English into 16 languages and maintained by domain experts, and around 100,000 text segments are available for each language pair. We build and evaluate translation models for seven target languages from English, with several different copy mechanisms and an XML-constrained beam search. We also experiment with a non-English pair to show that our dataset has the potential to explicitly enable 17 × 16 translation settings. Our experiments show that learning to translate with the XML tags improves translation accuracy, and the beam search accurately generates XML structures. We also discuss trade-offs of using the copy mechanisms by focusing on translation of numerical words and named entities. We further provide a detailed human analysis of gaps between the model output and human translations for real-world applications, including suitability for post-editing.

Introduction
Machine translation is a fundamental research area in the field of natural language processing (NLP). To build a machine learning-based translation system, we usually need a large amount of bilingually-aligned text segments.
Examples of widely-used datasets are those included in WMT (Bojar et al., 2018) and LDC 1 , while new evaluation datasets are being actively created (Michel and Neubig, 2018;Bawden et al.,  2018; Müller et al., 2018). These existing datasets have mainly focused on translating plain text.
On the other hand, text data, especially on the Web, is not always stored as plain text, but often wrapped with markup languages to incorporate document structure and metadata such as formatting information. Many companies and software platforms provide online help as Web documents, often translated into different languages to deliver useful information to people in different countries. Translating such Web-structured text is a major component of the process by which companies localize their software or services for new markets, and human professionals typically perform the translation with the help of a translation memory (Silvestre Baquero and Mitkov, 2017) to increase efficiency and maintain consistent termi-nology. Explicitly handling such structured text can help bring the benefits of state-of-the-art machine translation models to additional real-world applications. For example, structure-sensitive machine translation models may help human translators accelerate the localization process.
To encourage and advance research on translation of structured text, we collect parallel text segments from the public online documentation of a major enterprise software platform, while preserving the original XML structures.
In experiments, we provide baseline results for seven translation pairs from English, and one non-English pair. We use standard neural machine translation (NMT) models, and additionally propose an XML-constrained beam search and several discrete copy mechanisms to provide solid baselines for our new dataset. The constrained beam search contributes to accurately generating source-conditioned XML structures. Besides the widely-used BLEU (Papineni et al., 2002) scores, we also investigate more focused evaluation metrics to measure the effectiveness of our proposed methods. In particular, we discuss trade-offs of using the copy mechanisms by focusing on translation of named entities and numerical words. We further report detailed human evaluation and analysis to understand what is already achieved and what needs to be improved for the purpose of helping the human translators (a post-editing context). As our dataset represents a single, well-defined domain, it can also serve as a corpus for domain adaptation research (either as a source or target domain). We will release our dataset publicly, and discuss potential for future expansion in Section 6.

Collecting Data from Online Help
This section describes how we constructed our new dataset for XML-structured text translation.
Why high quality? We start from the publiclyavailable online help of a major international enterprise software-as-a-service (SaaS) platform. The software is provided in many different languages, and its multilingual online documentation has been localized and maintained for 15 years by the same localization service provider and inhouse localization program managers. Since the beginning they have been storing translations in a translation memory (i.e. computer-assisted translation tool) to increase quality and terminology consistency. The documentation makes frequent use of structured formatting (using XML) to convey information to readers, so the translators have aimed to ensure consistency of formatting and markup structure, not just text content, between languages.
How many languages? The web documentation currently covers 16 non-English languages translated from English. These 16 languages are Brazilian Portuguese, Danish, Dutch, Finnish, French, German, Italian, Japanese, Korean, Mexican Spanish, Norwegian, Russian, Simplified Chinese, Spanish, Swedish, and Traditional Chinese. In practice, the human translation has been done from English to the other languages, but all the languages could be potentially considered as both source and target because they contain the same tagging structure.

Bilingual Web Page Alignments
In this paper, we focus on each language pair separately, as an initial construction of our dataset. Each page of the online documentation in the different languages is already aligned in the following two ways: first, the same page has the same file name between languages; for example, if we have a page about "WMT", there would be /English/wmt.xml and /Japanese/wmt.xml, and second, most of the high-level XML elements are already aligned, because the original English files have been translated by preserving the same XML structures as much as possible in the localization process, to show the same content with the same formatting. Figure 2 shows a typical pair of files and the alignment of their high-level XML elements.
Our dataset contains about 7,000 pairs of XML files for each language pair; for example, there are 7,336 aligned files for English-{French, German, Japanese}, 7,160 for English-{Finnish, Russian}, and 7,927 for Finnish-Japanese. 2 2.2 Extracting Parallel Text Segments XML parsing and alignment For each language pair, we extract parallel text segments from XML structures. We use the etree module in a Python library called lxml 3 to process XML strings in the XML files. Since the XML elements are well formed and translators keep the same tagging structure as much as their languages allow it, as described in Section 2.1, we first linearize an XML-parsed file into a sequence of XML elements. We then use a pairwise sequence alignment algorithm for each bilingually-aligned file, based on XML tag matching. As a result, we have a set of aligned XML elements for the language pair.
Tag categorization Next, we manually define which XML elements should be translated, based on the following three categories: -Translatable: A translatable tag (e.g. p, xref, note) requires us to translate text inside the tag, and we extract translation pairs from this category. In general, the translatable tags correspond to standalone text, and are thus easy to align in the sequence alignment step.
-Transparent: By contrast, a transparent tag (e.g. b, ph) is a formatting directive embedded as a child element in a translatable tag, and is not always well aligned due to grammatical differences among languages. We keep the transparent tags embedded in the translatable tags.
-Untranslatable: In the case of untranslatable tags (e.g. sup), we remove the elements. The complete list of tag categorizations can be found in the supplementary material. Figure 3 shows how to extract parallel text segments based on the tag categorization. There are three aligned translatable tags, and they result in three separate translation pairs. The note tag is translatable, so the entire element is This is an <xref>international conference</xref> called WMT. これは WMT という<xref>国際会議</xref>です。 international conference 国際会議 It is held for machine translation. 機械翻訳のために開催されます。
This is an <xref>international conference</xref> called WMT. <note>It is held for machine translation.</note>

これは WMT という<xref>国際会議 </xref>です。<note>機械翻訳のために開催されま す。</note>
 En Ja Figure 3: Extracting parallel text segments from aligned XML elements. removed when extracting the translation pair of the p tag. However, we do not remove nested translatable tags (like the xref tag in this figure) when their tail 4 has text, to avoid missing phrases within sentences. Next, we remove the root tag from each translation pair, because the correspondence is obvious. We also remove fine-grained information such as attributes in the XML tags for the dataset; from the viewpoint of real-world usage, we can recover (or copy) the missing information as a post-processing step. As a result of this process, a translation pair can consist of multiple sentences as shown in Example (c) of Figure 1. We do not split them into single sentences, considering a recent trend of context-sensitive machine translation (Bawden et al., 2018;Müller et al., 2018;Zhang et al., 2018;Miculicich et al., 2018). One can use split sentences for training a model, but an important note is that there is no guarantee that all the internal sentences are perfectly aligned. We note that this structure-based alignment process means we do not rely on statistical alignment models to construct our parallel datasets.  Filtering We only keep translation pairs whose XML tag sets are consistent in both language sides, but we do not constrain the order of the tags to allow grammatical differences that result in tag reordering. We remove duplicate translation pairs based on exact matching, and separate two sets of 2,000 examples each for development and test sets. There are many possible experimental settings, and in this paper we report experimental results for seven English-based pairs, English-to-{Dutch, Finnish, French, German, Japanese, Russian, Simplified Chinese}, and one non-English pair, Finnish-to-Japanese. The dataset thus provides opportunities to focus on arbitrary pairs of the 17 languages. For each of the possible pairs, the number of training examples (aligned segments) is around 100,000.

Detailed Dataset Statistics
Table 1 and Figure 4, 5, 6 show more details about the dataset statistics. We take our English-French dataset to show some detailed statistics, but the others also have the consistent statistics because all the pairs are grounded in the same English files.
Text lengths Due to the XML tag-based extraction, our dataset includes word-and phrase-level translations as well as sentence-and paragraphlevel translations, and we can see in Figure 4 that there are many short text segments. This is, for example, different from the statistics of the widelyused News Commentary dataset. The text length is defined based on the number of subword tokens, following our experimental setting described below.
Sentence counts Another characteristic of our dataset is that the translation pairs can consist of multiple sentences, and Figure 5 shows the statistics of the number of English sentences in the English-French translation pairs. The number of sentences is determined with the sentence splitter from the Stanford CoreNLP toolkit (Manning et al., 2014).
XML-tag counts As we remove the root tags from the XML elements in our dataset construction process, not all the text segments have XML tags inside them. More concretely, about 25.5% of the translation pairs have at least one internal XML tag, and Figure 6 shows the statistics. For example, Example (a) in Figure 1 has four XML tags, and Example (b) has three.

Evaluation Metrics
We consider multiple evaluation metrics for the new dataset. For evaluation, we use the true-cased and detokenized text, because our dataset is designed for an end-user, raw-document setting.
BLEU without XML We include the most widely-used metric, BLEU, without XML tags.
That is, we remove all the XML tags covered by our dataset and then evaluate BLEU. The metric is compatible with the case where we use the dataset for plain text translation without XML. To compute the BLEU scores, we use language-specific tokenizers; for example, we use Kytea (Neubig et al., 2011) for Simplified Chinese and Japanese, and the Moses (Koehn et al., 2007) tokenizer for English, Dutch, Finnish, French, German, and Russian.
Named entities and numbers The online help frequently mentions named entities such as product names and numbers, and accurate translations of them are crucial for users. Frequently, they are not translated but simply copied as English forms. We evaluate corpus-level precision and recall for translation of the named entities and numerical tokens. To extract the named entities and numerical words, we use a rule-based regex script, based on our manual analysis on our dataset. The numerical words are extracted by "[0-9.,\'/:]*[0-9]+[0-9.,\'/:]*".
The named entities are defined as appearing in a non-alphabetic language, Japanese, because in our dataset we observe that the alphabetic words in such non-alphabetic languages correspond to product names, country names, function names, etc.
XML accuracy, matching, and BLEU For each output text segment, we use the etree module to check if it is a valid XML structure by wrapping it with a dummy root node. Then the XML accuracy score is the number of the valid outputs, divided by the number of the total evaluation examples. We further evaluate how many translation outputs have exactly the same XML structures as their corresponding reference text (an XML matching score). If a translation output matches its reference XML structure, both the translation and reference are split by the XML tags. We then evaluate corpus-level BLEU by comparing each split segment one by one. If an output does not match its reference XML structure, the output is treated as empty to penalize the irrelevant outputs.

Machine Translation with XML Tags
We use NMT models to provide competitive baselines for our dataset. This section first describes how to handle our dataset with a sequential NMT model. We then propose a simple constrained beam search for accurately generating XML structures conditioned by source information. We further incorporate multiple copy mechanisms to strengthen the baselines.

Sequence-to-Sequence NMT
The task in our dataset is to translate text with structured information, and therefore we consider using syntax-based NMT models. A possible approach is incorporating parse trees or parsing algorithms into NMT models (Eriguchi et al., 2016(Eriguchi et al., , 2017, and another is using sequential models on linearized structures (Aharoni and Goldberg, 2017). We employ the latter approach to incorporate source-side and target-side XML structures, and note that this allows using standard sequenceto-sequence models without modification.
We have a set of parallel text segments for a language pair (X , Y), and the task is translating a text segment x ∈ X to another y ∈ Y. Each x in the dataset is represented with a sequence of tokens including some XML tags: where N is the length of the sequence. Its corresponding reference y is also represented with a sequence of tokens: y = [y 1 , y 2 , . . . , y M ], where M is the sequence length. Any tokenization method can be used, except that the XML tags should be individual tokens.
To learn translation from x to y, we use a transformer model (Vaswani et al., 2017). In our Klayer transformer model, each source token x i in the k-th (k ∈ [1, K]) layer is represented with where i is the position information, d is the dimensionality of the model, and h x where v(x i ) ∈ R d is a token embedding, and e(i) ∈ R d is a positional embedding.
Each target-side token y j is also represented in a similar way: where only [h y k−1 (y 1 ), h y k−1 (y 2 ), . . . , h y k−1 (y j )] is used from h y k−1 . In the same way as the sourceside embeddings, h y 0 (y j ) is computed as h y 0 (y j ) = √ d · v(y j ) + e(j). For more details about the parameterized functions f and g, and the positional embeddings, please refer to Vaswani et al. (2017).
Then h y K (y j ) is used to predict the next token w by a softmax layer: p g (w|x, y ≤j ) = softmax(W h y K (y j ) + b), where W ∈ R |V|×d is a weight matrix, b ∈ R |V| is a bias vector, and V is the vocabulary. The loss function is defined as follows: where we assume that y 1 is a special token BOS to indicate the beginning of the sequence, and y M is an end-of-sequence token EOS. Following Inan et al. (2017) and Press and Wolf (2017), we use W as an embedding matrix, and we share the single vocabulary V for both X and Y. That is, each of v(x i ) or v(y j ) is equivalent to a row vector in W .

XML-Constrained Beam Search
At test time, standard sequence-to-sequence generation methods do not always output valid XML structures, and even if an output is a valid XML structure, it does not always match the tag set of its source-side XML structure. To generate source-conditioned XML structures as accurately as possible, we propose a simple constrained beam search method. We add three constrains to a standard beam search method. First, we keep track of possible tags based on the source input, and allow the model to open only a tag that is present in the input and has not yet been covered. Second, we keep track of the most recently opened tag, and allow the model to close the tag. Third, we do not allow the model to output EOS before opening and closing all the tags used in the source sentence. Algorithm 1 in the supplementary material shows a comprehensive pseudo code.

Reformulating a Pointer Mechanism
We consider how to further improve our NMT system, by using multiple discrete copy mechanisms. Since our dataset is based on XML-structured technical documents, we want our NMT system to copy (A) relevant text segments in the target language if there are very similar segments in the training data, and (B) named entities (e.g. product names), XML tags, and numbers directly from the source. For the copy mechanisms, we follow the general idea of the pointer used in See et al. (2017).
For the sake of discrete decisions, we reformulate the pointer method. Following the previous work, we have a sequence of tokens which are targets of our pointer method: c = [c(z 1 ), c(z 2 ), . . . , c(z U )], where c(z i ) ∈ R d is a vector representation of the i-th token z i , and U is the sequence length. As in Section 3.1, we have h y K (y j ) to predict the (j + 1)-th token. Before defining an attention mechanism between h y K (y j ) and c, we append a parameterized vector c(z 0 ) = c to c. We expect c to be responsible for decisions of "not copying" tokens, and the idea is inspired by adding a "null" token in natural language inference (Parikh et al., 2016).
We then define attention scores between h y K (y j ) and the expanded c: a(j, i) = score(h y K (y j ), c i , c), where the normalized scoring function score is implemented as a singlehead attention model proposed in Vaswani et al. (2017). If the next reference token y j+1 is not included in the copy target sequence, the loss function is defined as follows: and otherwise the loss function is as follows: and then the total loss function is L(x, y) + M −1 j=1 L(x, y ≤j , c). The loss function solely relies on the cross-entropy loss for single probability distributions, whereas the pointer mechanism in See et al. (2017) defines the cross-entropy loss for weighted summation of multiple distributions.
At test time, we employ a discrete decision strategy for copying tokens or not. More concretely, the output distribution is computed as where p c (w|x, y ≤j ) is computed by aggregating [a(j, 1), . . . , a(j, U )]. δ is 1 if a(j, 0) is the largest among [a(j, 0), . . . , a(j, U )], and otherwise δ is 0. Gu et al. (2018) presented a retrieval-based NMT model, based on the idea of translation memory (Silvestre Baquero and Mitkov, 2017). Following Gu et al. (2018), we retrieve the most relevant translation pair (x , y ) for each source text x in the dataset. In this case, we set [z 1 , . . . , z U ] = [y 2 , . . . , y M ] and c = [h y K (y 1 ), . . . , h y K (y M −1 )], where M is the length of y , and each vector in c is computed by the same transformer model in Section 3.1. For this retrieval copy mechanism, we denote p c and δ as p r and δ r , respectively.

Copy from Retrieved Translation Pairs
Copy from Source Text To allow our NMT model to directly copy certain tokens from the source text x when necessary, we follow See et al. (2017). We set [z 1 , . . . , , and we denote p c and δ as p s and δ s , respectively.
We have the single vocabulary V to handle all the tokens in both languages X and Y, and we can combine the three output distributions at each time step in the text generation process: (1 − δ s )p s + δ s (δ r p g + (1 − δ r )p r ).
The copy mechanism is similar to the multipointer-generator method in McCann et al. (2018), but our method employs rule-based discrete decisions. Equation (7) first decides whether the NMT model copies a source token. If not, our method then decides whether the model copies a retrieved token.

Experimental Settings
This section describes our experimental settings. We will release the preprocessing scripts and the training code (implemented with PyTorch) upon publication. More details are described in the supplementary material.

Tokenization and Detokenization
We used the SentencePiece toolkit (Kudo and Richardson, 2018) for sub-word tokenization and detokenization for the NMT outputs.
Without XML tags If we remove all the XML tags from our dataset, the task becomes a plain MT task. We carried out our baseline experiments for the plain text translation task, and for each language pair we trained a joint SentencePiece model to obtain its shared sub-word vocabulary. For training each NMT model, we used training examples whose maximum token length is 100.
With XML tags For our XML-based experiments, we also trained a joint SentencePiece model for each language pair, where one important note is that all the XML tags are treated as user-defined special tokens in the toolkit. This allows us to easily implement the XML-constrained beam search. We also set the three tokens &, <, and > as special tokens.

Model Configurations
We implemented the transformer model with K = 6 and d = 256 as a competitive baseline model. We trained three models for each language pair: "OT" (trained only with text without XML), "X" (trained with XML), and "X rs " (XML and the copy mechanisms).
For each setting, we tuned the model on the development set and selected the best-performing model in terms of BLEU scores without XML, to make the tuning process consistent across all the settings. rs ) on our test set to show our baseline scores for future comparisons. Simplified Chinese is written as "Chinese" in this section.

Evaluation without XML
We first focus on the two evaluation metrics: BLEU without XML, and named entities and numbers (NE&NUM). In Table 2, a general observation from the comparison of OT and X is that including segment-internal XML tags tends to improve the BLEU scores. This is not surprising because the XML tags provide information about explicit or implicit alignments of phrases. However, the BLEU score of the English-to-Finnish task significantly drops, which indicates that for some languages it is not easy to handle tags within the text.
Another observation is that X rs achieves the best BLEU scores, except for English-to-French. In our experiments, we have found that the improvement of BLEU comes from the retrieval method, but it degrades the NE&NUM scores, especially the precision. Then copying from the source tends to recover the NE&NUM scores, especially for the recall. We have also observed that using beam search, which improves BLEU scores, degrades the NE&NUM scores. A lesson learned from these results is that work to improve BLEU scores can sometimes lead to degradation of other important metrics.   Compatibility with other domains Our dataset is limited to the domain of online help, but we can use it as a seed corpus for domain adaptation if our dataset contains enough information to learn basic grammar translation. We conducted a simple domain adaptation experiment in English-to-French by adding 10,000 or 20,000 training examples of the widely-used News Commentary corpus. We used the newstest2014 dataset for evaluation in the news domain. From Table 3, we can see that a small amount of the news-domain data significantly improves the target-domain score, and we expect that our dataset plays a good role in domain adaptation for all the covered 17 languages. Table 4 shows the evaluation results with XML. Again, we can see that X rs performs the best in terms of the XML-based BLEU scores, but the absolute values are lower than those in Table 2 due to the more rigid segment-by-segment comparisons. This table also shows that the XML accuracy and matching scores are higher than 99% in most of the cases. Ideally, the scores could be 100%, but in reality, we set the maximum length of the translations; as a result, sometimes the model cannot find a good path within the length limitation. Table 5 shows how effective our method is, based on the English-to-Japanese result, and we observed the consistent trend across the different languages.

Evaluation with XML
These results show that our method can accurately generate the relevant XML structures.
How to recover XML attributes? As described in Section 2.2, we removed all the attributes from the original XML elements for simplicity. However, we need to recover the attributes when we use our NMT model in the real-world application. We consider recovering the XML attributes by the copy mechanism from the source; that is, we can copy the attributes from the XML elements in the original source text, if the XML tags are copied from the source. Table 6 summarizes how our model generates the XML tags on the English-Japanese development set. We can see in the table that most of the XML tags are actually copied from the source. Figure 7 shows an example of the output of the X rs model. For this visualization, we merged all the subword tokens to form the standard words. The tokens in blue are explicitly copied from the source, and we can see that the time expression "12:57 AM" and the XML tags are copied as expected. The output also copies some relevant text segments (in red) from the retrieved translation. Like this, we can explicitly know which words are copied from which parts, by using our multiple discrete copy mechanisms. One surprising observation is that the underlined phrase "for example" is missing in the translation result, even though the BLEU scores are higher than those on other standard public datasets. This is a typical error called under translation. Therefore, no matter how large the BLEU scores are, we definitely need human corrections (or post editing) before providing the translation results to customers.

Human Evaluation by Professionals
One important application of our NMT models is to help human translators; translating online help has to be precise, and thus any incomplete translations need post-editing. We asked professional translators at a vendor to evaluate our test set results (with XML) for the English-to-{Finnish, French, German, Japanese} tasks. For each language pair, we randomly selected 500 test examples, and every example is given an integer score in [1,4]. A translation result is rated as "4" if it can be used without any modifications, "3" if it needs simple post-edits, "2" if it needs more post-edits but is better than nothing, and "1" if using it is not better than translating from scratch. Figure 8 shows the summary of the evaluation to see the ratio of each score, and the average scores are also shown. A positive observation for all the four languages is that more than 50% of the translation results are evaluated as complete or useful in post-editing. However, there are still many low-quality translation results; for example, around 30% of the Finnish and German results are evaluated as useless. Moreover, the German results have fewer scores of "4", and it took 12 hours for the translators to evaluate the German results, whereas it took 10 hours for the other three languages. To further make our NMT models useful for post-editing, we have to improve the translations scored as "1".
Detailed error analysis We also asked the translators to note what kinds of errors exist for each of the evaluated examples. All the errors are classified into the six types shown in Table 7, and each example can have multiple errors. The "Formatting" type is our task-specific one to evaluate whether the XML tags are correctly inserted. We can see that the Finnish results have significantly more XML-formatting errors, and this result agrees with our finding that handling the XML tags in Finnish is harder than in other languages, as discussed in Section 5.1. It is worth further investigating such language-specific problems.
The "Accuracy" type covers major issues of NMT, such as adding irrelevant words, skipping important words, and mistranslating phrases. As discussed in previous work (Malaviya et al., 2018), reducing the typical errors covered by the "Accuracy" type is crucial. We have also noticed  Figure 8: Human evaluation results for the X rs model. "4" is the best score, and "1" is the worst.  that the NMT-specific errors would slow down the human evaluation process, because the NMT errors are different from translation errors made by humans. The other types of errors would be reduced by improving language models, if we have access to in-domain monolingual corpora.
Can MT help the localization process? In general, it is encouraging to observe many "4" scores in Figure 8. However, one important note is that it takes significant amount of time for the translators to verify the NMT outputs are good enough. That is, having better scored NMT outputs does not necessarily lead to improving the productivity of the translators; in other words, we need to take into account the time for the quality verification when we consider using our NMT system for that purpose. Previous work has investigated the effectiveness of NMT models for post-editing (Skadina and Pinnis, 2017), but it has not yet been investigated whether using NMT models can improve the translators' productivity alongside the use of a well-constructed translation memory (Silvestre Baquero and Mitkov, 2017). Therefore, our future work is investigating the effectiveness of using the NMT models in the real-world localization process where a translation memory is available.

Related Work and Discussions
Automatic extraction of parallel sentences has a long history (Varga et al., 2005), and usually statistical methods and dictionaries are used. By contrast, our data collection solely relies on the XML structure, because the original data have been well structured and aligned. Recently, collecting training corpora is the most important in training NLP models, and thus it is recommended to maintain well-aligned documents and structures when building multilingual online services. That will significantly contribute to the research of language technologies. We followed the syntax-based NMT models (Eriguchi et al., 2016(Eriguchi et al., , 2017Aharoni and Goldberg, 2017) to handle the XML structures. One significant difference between the syntax-based NMT and our task is that we need to output sourceconditioned structures that are able to be parsed as XML, whereas the syntax-based NMT models do not always need to follow formal rules for their output structures. In that sense, it would be interesting to relate our task to source code generation (Oda et al., 2015) in future work.
Our dataset has significant potential to be further expanded. Following the context-sensitive translation (Bawden et al., 2018;Müller et al., 2018;Zhang et al., 2018;Miculicich et al., 2018), our dataset includes translations of multiple sentences. However, the translatable XML tags are separated, so the page-level global information is missing. One promising direction is thus to create page-level translation examples. Finally, considering the recent focus on multilingual NMT models (Johnson et al., 2017), multilingually aligning the text will enrich our dataset.

Conclusion
We have presented our new dataset for XMLstructured text translation. Our dataset covers 17 languages each of which can be either source or target of machine translation. The dataset is of high quality because it consists of professional translations for an online help domain. Our experiments provide baseline results for the new task by using NMT models with an XML-constrained beam search and discrete copy mechanisms. We further show detailed human analysis to encourage future research focusing on how to apply machine translation to help human translators in practice.