Abstract: In this study, Petri net is used to model and analyze cross-organization task coordination patterns of Urban Emergency Response Systems (UERS). A kind of Petri net extended with time, resource and message factors is firstly proposed to model tasks and emergency response process within a single organization. Based on this the proposed model, four kinds of cross-organization task coordination patterns within a UERS are summarized, including the sequential task pattern, the task synchronization pattern, the resource sharing pattern and the message exchanged pattern. A UERS can be modeled according to the task and emergency response process modeling methods of a single organization and the cross-organization task coordination patterns.
INTRODUCTION
Urban Emergency Response System (UERS) is a modernization symbol of a city (Zhong et al., 2010), integrating the emergency directions and the scheduling, which deals with unexpected incidents into a management system through the integrated information network and the communications system. The unexpected incidents include the public security, the fire prevention, the hygienic first aid, the transportation, the public utility, the natural disaster and so on. A UERS realizes the unification to answer alarm, the unified command, the combined action, the rapid reaction by sharing the platform and the foundation information, providing a more convenient emergency rescue service and the related services for the resident and technical assistances for government to exactly deal with all kinds of disasters and technical supports for the public security of cities (Wei et al., 2006). Based on the Markov Chain (MC) of the model, Zhong et al. (2010) analyzed the performance of typical UERS. Xia et al. (2008) constructed the framework of urban emergency response system based on Multi-Agent System and analyzed these agent groups of the system. Li and Wei (2008) presented a new model and framework of UERS based on decision-system. Tang and Li (2010) used UML to design a complete UERS model, including case diagram, class diagram, timing diagram, state diagram, component diagram and deployment diagram of the UERS. Zhong et al. (2003) analyzed the performance of the UERS by the Petri net. In the research on modeling and performance of the UERS, there is a little work on the coordination problem between organizations, although an emergency response process usually includes several organizations. To deal with the coordination problem between organizations is important to improve the efficiency of a complex system. There are many research results on the coordination problem between organizations in workflow systems or business process. For example, Kappel et al. (1998) believed that the so-called coordination is the joint effects of each independent component, so they insisted on the importance of coordination between the components. Van der Aalst (1998) modeled inter organizational workflows in terms of Petri nets and focus on techniques to verify the correctness of these workflows. In this study, we use Petri net as formal model to analyze cross-organization task coordination patterns of Urban Emergency Response Systems (UERS). A kind of Petri net extended with time, resource and message factors is firstly proposed to model tasks and emergency response process within a single organization. Based on the proposed model, four kinds of cross-organization task coordination patterns within a UERS are summarized and modeled. A UERS can be modeled according to the task and emergency response process modeling methods of a single organization and the cross-organization task coordination patterns.
TASK MODEL OF A SINGLE ORGANIZATION
Here, we first present the formal definition of an emergency task and the modeling approach for a task using Petri net.
Definition 1: An emergency task is a 7-tuple:
where:
| • | Name is the ID of a task and points out the content of a task |
| • | Duration represents implementation time of a task |
| • | Organization represents the organization to complete this task |
| • | MessagesReq represents the message set required before the implementation of a task. In this study, if MessagesReq = φ, it means that the implementation of a task requires no messages |
| • | MessageSent represents the message set sent after the implementation of a task. If MessageSent = φ, it means that the implementation of a task does not send any messages |
| • | Resources represent the resource set required during the implementation of a task. If Resources = φ, it means that the implementation of a task requires no resources |
| • | PostTasks represent the post task set. For any task in PostTasks of a task t, it should not be implemented until t is completed. If the post task set of t is empty, i.e., PostTasks ⊂φ, it means that t is an end task |
In definition 1, we assume that the resources are exclusively used. If a resource is occupied or locked by one task, then the other tasks requiring this resource have to wait until the resource becomes available.
For example, a task <Ti,Di,Oi,{Mi1}, {Mi2},{Ri1, Ri2},φ> can be represented in XML language which is shown in Fig. 1.
Petri net is a useful tool for system modeling and analysis (Zeng, 2008; Zeng and Duan, 2007; Zeng et al., 2008; Wang and Zeng, 2008; Liu and Yang, 2010). In this study, Petri net is used to model tasks of a UERS. A task Ti is represented by a transition and two places of the transition respectively represent the start and the end of Ti. In order to distinguish the logic places in a Petri net, we use a double-line circle to represent a resource place or a message place. Before the implementation of a task, each resource place should contain a token, which means the resources are well prepared and available for the task. However, no message places hold a single token because the message tokens are produced during the implementation of the emergency response process. For example, Fig. 2 presents the Petri net model for the task shown in Fig. 1.
| Fig. 1: | A task represented in XML |
| Fig. 2: | Task model of a single organization |
In Fig. 2, Ti represents the task which is corresponding to the element <name>, Pi1 and Pi2 represent the start and the end of the task, respectively. Ri1 and Ri2 represent the required resources which are corresponding to the element <resources>. Mi1, which is corresponding to the element <messagesReq>, represents the message received. On the other hand, Mi2, which is corresponding to the element <messagesSent>, represents the message sent. In Fig. 2, we can see that there are no input arcs to Mi1, which means Mi1 is a message received from other tasks. And, there are no output arcs from Mi2, which means Mi2 is a message sent to other tasks.
An emergency response process within an organization is composed of a set of emergency tasks, which can be formalized in an extended Petri net.
Definition 2: An emergency response process is an extended Petri net
| Table 1: | Description of symbols in Fig. 6 |
| Fig. 3: | Two tasks of a single organization |
| • | P = PL∪PR∪PI, such that PL represents the logic places between tasks, PR represents the resource set and PI represents the message set |
| • | The transition set T represents the task set of an emergency response process |
| • | F⊆PxT∪TxP |
| • | τ: T→D, which represents the duration of each task, where D is a time set |
| • | λ: T→O, which represents the organization of each task, where, O is the organization |
| • | M0: ∀p∈P, |
In this study, we assume that the tasks within a single organization are executed in sequence and there are no resource conflicts and message exchange among tasks. If two tasks <T1, D1, O1, MessagesReq1, MessagesSent1, Resource1, PostTask1> and <T2, D2, O2, MessagesReq2, MessagesSent2, Resource2, PostTask2> satisfy (1) O1 = O2 and (2) T2∈PostTask1, it means task T2 is one of the post tasks of T1. In other words, we can say that T1 and T2 are sequential tasks within a single organization. For example, Fig. 3 shows two sequential tasks within a single organization.
To model two sequential tasks within a single organization, T1 and T2, we can use the model shown in Fig. 4, where the end place of T1 and the start place T2 are merged as one place.
If a task is not the post of any task, then it is the start of the whole emergency response process. Likewise, if a task is not followed by any post tasks, then it is the end of the whole emergency response process.
| Fig. 4: | Tasks model of a single organization |
The start place of a start task should contain tokens representing the start of the process and the end place of an end task is the end place of the whole process. For example, if we assume the T1 and T2 in Fig. 4 as the start and the end tasks of an emergency response process respectively, then the corresponding Petri net model can be shown in Fig. 4.
For example, the tasks set of a local police station in an emergency response process are shown in Fig. 5.
According to the modeling method, Fig. 6 shows the Petri net model for the emergency response process shown in Fig. 5. The meanings of symbols in Fig. 6 are shown in Table 1.
CROSS-ORGANIZATION TASK COORDINATION PATTERNS
In a UERS, there are requirements for organizations to collaborate with each other to complete a complex emergency response process. By analyzing a large number of practical cases, four kinds of basic cross-organization task coordination patterns are given here, which are the sequential task pattern, the task synchronization pattern, the resource sharing pattern, the message transmission pattern.
| Fig. 5: | Tasks set of a local police station |
| Fig. 6: | The Petri net model of the local police station |
The formal definitions and models of the four coordination patterns are presented here. For simplicity, the four coordination patterns are illustrated with only two organizations, as the patterns with more organizations are similar with it.
Sequential task pattern: If two tasks
and
satisfy, (1) O1≠O2 and (2) T2∈PostTask1, then two organizations O1 and O2 are collaborated with sequential tasks T1 and T2.
For example, two tasks shown in Fig. 7 illustrate T1 differs from T2 in <organization> and T2 belongs to the element<postTasks> of T1. So, they are two sequential tasks between O1 and O2.
| Fig. 7: | Two sequential tasks |
| Fig. 8: | Petri net model of sequential task pattern |
| Fig. 9: | Two synchronous tasks |
To model two organizations O1 and O2 collaborated with sequential tasks T1 and T2 (T2 is the post task of T1), a new output place of the corresponding transition of T1 is added and it is added as one input place of T2 at the same time. The model of the sequential task pattern is shown in Fig. 8.
Task synchronization pattern: If two tasks:
and
satisfy (1) T1 = T2; (2) D1 = D2 and (3) O1 ≠ O2, then two organizations O1 and O2 are collaborated with synchronous tasks T1 and T2.
For example, the two tasks shown in Fig. 9 illustrate T1 differs from T2 in <organization> and have the same <name> and <duration>, so they are two synchronous tasks between O1 and O2.
To model two organizations O1 and O2 collaborated with synchronous tasks T1 and T2, the two tasks are merged into one task in the Petri net model and are represented by one transition T12, but the start places and the end places of T1 and T2 are connected to T12. The model of the task synchronization pattern is shown in Fig. 10.
| Fig. 10: | Petri net model of task synchronization pattern |
| Fig. 11: | Two tasks sharing resource |
Resource sharing pattern: If two tasks:
and
satisfy (1) O1≠O2 and (2) Resources1∩Resources2≠φ, then two organizations O1 and O2 are collaborated with sharing resources between T1 and T2.
For example, the two tasks shown in Fig. 11 illustrate T1 differs from T2 in <organization> and theirs <resource> have the same resource R1, so they are two tasks with sharing resources between O1 and O2.
To model two organizations O1 and O2 collaborated with sharing resources between tasks T1 and T2, the same resource used by T1 and T2 is represented by a resource place. The model of the resource sharing pattern is shown in Fig. 12.
Message exchanged pattern: If two tasks:
and
| Fig. 12: | Petri net model of resource sharing pattern |
satisfy, (1) O1≠O2 and (2) MessagesReq1∩MessagesSent2 ≠ φ or MessagesReq2∩MessagesSent1 ≠ φ, then two organizations O1 and O2 are collaborated with message exchanged between tasks T1 and T2. For example, the two tasks shown in Fig. 13, the <messageSent> of T1 and the <messageReq> of T2 have the same message M1, so there is a message exchanged between O1 and O2.
To model two organizations O1 and O2 collaborated with message exchanged between tasks T1 and T2, the message place exchanged is represented by one message place and the transitions of T1 and T2 connect to this message place.
| Fig. 13: | Two tasks with message exchanged |
| Fig. 14: | Petri net model of message exchanged pattern |
| Table 2: | A serial tasks of the bomb attack in a city |
The model of the message exchanged pattern is shown in Fig. 14.
Application case: According to the emergency response process modeling method of a single organization given in here and the task coordination patterns between organizations given in here, a serial of cross-organization tasks within UERS can be modeled. In this section, an example is given for illustration. For example, a set of tasks in an emergency response process are shown in Table 2, which includes 14 tasks completed by five organizations. During the implementation of the emergency response process, there are nine kinds of resources required and eleven kinds of messages exchanged. The meanings of symbols in Table 2 are shown in Table 3.
According to the emergency response process modeling method and the task coordination patterns between organizations, the Petri net model for the tasks presented in Table 2 is shown in Fig. 15.
According to Fig. 15, the emergency response process for each organization is very clear. The task coordination patterns between these five organizations are observed and presented in Table 4. From the table, we can see that O1 only cooperates with O2, but O2, O3, O4 and O5 are working in a very close collaboration with each other.
| Table 3: | Description of symbols in Table 2 |
| Fig. 15: | Petri net model of tasks in Table 2 |
| Table 4: | Coordination patterns between organizations |
Form Table 4, it can also be found that message exchanged pattern is the most common patterns between organizations.
In Table 4, STP represents Sequential task pattern, TSP represents Task synchronization pattern, RSP represents Resource sharing pattern and MEP represents Message exchanged pattern.
CONCLUSION
The coordination problem is important within a complex UERS. In this study, we use Petri net as formal tool to model the task of a single organization and propose four task coordination patterns between organizations in UERS, which include the sequential task pattern, the task synchronization pattern, the resource sharing pattern and the message exchanged pattern based on Petri net. Finally, an example is used as application case to illustrate the proposed modeling approach. The coordination problem is a very complex research topic. In this study, we only propose the modeling method and coordination patterns of tasks between organizations. Based on the modeling method and the coordination patterns, there are many problems to be continued, for example, the resource conflict analysis between organizations, the performance analysis for a complex UERS cross organization and so on.
ACKNOWLEDGMENT
This study is supported partly by the NSFC under Grant No. 60603090, 90718011 and 50875158; Science and Technology Development Fund of Shandong Province of China (2010GSF10811); the Excellent Young Scientist Foundation of Shandong Province of China under Grant No. BS2009DX004; the Special Fund for Fast Sharing of Science Paper in Net Era by CSTD (20093718110008); the Open Project of Computer Architecture Lab of ICT, CAS, (No. ICT-ARCH200807); the Research Foundation of Shandong Educational Committee under Grant No. J08LJ77 and the Taishan Scholar Program of Shandong Province.