3y ago

49 Views

2 Downloads

701.43 KB

26 Pages

Transcription

Simulating a Multi-Stage ScreeningNetwork: A Queueing Theory and GameTheory ApplicationXiaowen Wang, Cen Song and Jun ZhuangAbstract Simulation is widely used to study model for balancing congestion andsecurity of a screening system. Security network is realistic and used in practice, butit is complex to analyze, especially when facing strategic applicants. To our bestknowledge, no previous work has been done on a multi-stage security screeningnetwork using game theory and queueing theory. This research ﬁlls this gap byusing simulation. For multi-stage screening, the method to determine the optimalscreening probabilities in each stage is critical. Potential applicants may have accessto information such as screening policy and other applicants’ behaviors to adjusttheir application strategies. We use queueing theory and game theory to study thewaiting time and the strategic interactions between the approver and the applicants.Arena simulation software is used to build the screening system with three majorcomponents: arrival process, screening process, and departure process. We useMatlab Graphic User Interface (GUI) to collect user inputs, then export datathrough Excel for Arena simulation, and ﬁnally export simulation from the resultsof the Arena to Matlab for analysis and visualization. This research provides somenew insights to security screening problems.This research was partially supported by the United States National Science Foundation (NSF)under award numbers 1200899 and 1334930. This research was also partially supported by theUnited States Department of Homeland Security (DHS) through the National Center for Riskand Economic Analysis of Terrorism Events (CREATE) under award number 2010-ST061-RE0001. However, any opinions, ﬁndings, and conclusions or recommendations in thisdocument are those of the authors and do not necessarily reflect views of the NSF, DHS, orCREATE. Cen Song and Jun Zhuang are the corresponding authors.X. Wang ! C. Song (&) ! J. ZhuangDepartment of Industrial and System Engineering, University at Buffalo, Buffalo, USAe-mail: censong@buffalo.edu; songcen22@gmail.comX. Wange-mail: xwang54@buffalo.eduJ. Zhuange-mail: jzhuang@buffalo.edu Springer International Publishing Switzerland 2015K. Hausken and J. Zhuang (eds.), Game Theoretic Analysis of Congestion,Safety and Security, Springer Series in Reliability Engineering,DOI 10.1007/978-3-319-13009-5 355

56X. Wang et al.!Keywords Security screening policy Two-stage queueing networktime Game theory Imperfect screening!!! Waiting1 Introduction1.1 BackgroundNowadays, security screening are very important in many ﬁelds, including airportsecurity screening [14], visa application [7], and customs inspection [15]. Screeningprocess can not be perfect, and there exist type I and type II errors [5]. Type I error isthe incorrect rejection of a true null hypothesis. In a screening system, if a goodapplicant is rejected, the approver is said to have a type I error. By contrast, Type IIerror is the failure to reject a false null hypothesis. In a screening system [21], if abad applicant is approved, the approver is said to have a type II error. Because ofthese errors, it adds costs to the approver. Moreover, these errors could pose seriousthreats to the public, such as security and safety issues. Therefore, multi-stagescreening process is introduced to reduce errors.After the 9/11/2001 attack, the U.S. government requires 100 % scanning of allU.S. bound containers by radiation detection and nonintrusive inspection equipmentat a foreign port before getting them loaded on vessels [3]. The TransportationSecurity Administration developed the Certiﬁed Cargo Screening Program forexplosives on a passenger aircraft to get 100 % screening [25]. It results in a longerwaiting time for the passengers to pass the security system. Moreover, reducing theprobability of screening, although it would lead to less waiting time, may fail tocatch some bad applicants. For each stage, low screening probability causes moreerrors while high screening probability causes congestion. In a visa application for aparticular tourism destination, if a good applicant knew before he applied, that thewaiting time is long, he would not apply. It is a loss for the destination country,because of the potential loss of economic contribution. In order to deter badapplicants and to attract good applicants to the most, a balance between congestionand intensity of screening should be achieved. In an airport security screeningprocess, such a long security check time may result in passengers missing the flight.The flight schedule for those who missed will be rescheduled. It will result in seatsunoccupied in the missed flight, which is such a waste. Meanwhile, the flight towhich passengers are rescheduled to might not have enough seats for them, becausecompany usually over sell tickets to maximize their beneﬁts [6]. The passengerswho got their itinerary changed are causing unbalance flows among the airlineschedules. Due to butterfly effect [28], it will lead to many more problems in thefuture. According to the data of 1980–2012 annual passenger number for NewarkLiberty International Airport [18], there are huge amount of people arriving at theairport. To avoid heavy congestion as well as to deter adversaries, a properscreening probability is required to the security screening.

Simulating a Multi-Stage Screening Network 57Since 1970s, researchers have studied security screening with queueing models[9]. We study the multiple stages of screening system and ﬁnd out how to predictapplicants’ behavior by applying queueing models and game theory. Based on thesimulation results, we ﬁnd the optimal strategy for the approvers.Game theory is a study of strategic decision-making [17]. Strategic interdependence is present in a social situation when what is best for someone depends onothers’ choices. The best strategies for attackers and defenders are analyzed bybalancing protection from terrorism and natural disasters and by consideringresource allocation [31]. The optimal inspection policies for security agency balance the inspection probability and average delay time and consider the adversarystrategic gaming behavior [8]. The optimal proportional inspection using gametheory is analyzed to achieve the most cost-effective combination of deterrence anddetection [2]. In the model, we assume that the decision makers are rational. Eachplayer maximizes his payoff, given his beliefs about the strategies used by otherplayers [24]. In this screening system, game players include applicants (good andbad) and approvers, whose actions impact each other. Knowing other players’potential best responses, players make their optimal decision. We apply gametheory to construct the dynamic system of screening system in this paper.Queueing theory is the mathematical study of waiting lines [23]. In queueingtheory, a model is constructed so that queue lengths and waiting time can bepredicted [23]. Single M/M/1, multiple M/M/c, single channel and multiple stages,and multiple channels and multiple stages models are used to estimate the truckdelay in the seaport [29]. The M/M/N queuing models are developed to quantifytruck congestion at primary scanning, and Monte-Carlo simulation is used toanalyze the risk of containers missing vessels at secondary inspections [1]. An M/M/m queuing model is designed and applied into an airport security system toanalyze the optimal number of security gates [20]. A queuing network and discreteevent simulation are used to test the effects of baggage volume and alarm rate at thesecurity screening checkpoint [4].In general, there are three ways to study the phenomena (fact or occurrence):analytic modeling [22], simulation [12] and experiment [11]. As phenomenabecomes more and more complex, analytic models may prove to be overly simpliﬁed, and some complex models cannot have analytical solutions. Meanwhile,sometimes experiments are not able to be performed or are too expensive to conduct. Simulation provides a way to meet our needs for cheaper, faster, and morepractical data [16]. Compared to various simulation methods, computer simulationmight be the most widely used one. Computer simulation is numerical evaluationusing software designed to imitate the systems operation characteristics [10]. Different softwares can be chosen according to the different characteristics of thesystem. Pendergraft et al. [19] simulate an airport passenger and luggage screeningsecurity screening system in a discrete event way. We need to simulate screeningsystem, which consists of queues and decision tree. It can be simulated by entityflows such as items or passengers constrained by conditions. In simulation,queueing models are often used for rough cut and condition setting [30]. We usequeueing models to set conditions, making the screening system more accurate.

58X. Wang et al.GUI in Matlab [13] provides point-and-click control of software application.Applied with user-deﬁned functions, Matlab GUI can fulﬁll the following taskswithout users knowing any command lines: data import/output, data analysis andplotting. In this paper, we apply GUI in Matlab for data analysis.The rest of this paper is structured as follows: A description of the model ispresented in Sect. 2. Designing Arena to simulate this screening system is discussedin Sect. 3. Matlab GUI design is discussed in Sect. 4. A numerical experiment anddata analysis are provided in Sect. 5. The conclusion and discussion on somepossible future work and application are provided in Sect. 6.2 The ModelFigure 1 shows the flowchart of the screening system. Potential applicants classiﬁedas good and bad applicants decide whether to enter this system or not. Once theyenter, they may go through several imperfect screening stages based on the screeningprobabilities at each stage. If they are screened, they would enter an M/M/1 servicequeue, which follows a ﬁrst-in ﬁrst-out rule. Based on the imperfect screeningresults, the suspected bad applicants are denied, while others are further to bedetermined to be screened or passed the system. Some applicants who are notscreened at all are deﬁned as good and they can pass the system.2.1 NotationTable 1 lists the notation that is used throughout this paper. We deﬁne the candidates as those who have the intention to enter the system but not certain enough tobe classiﬁed as potential applicants. Those who exactly enter the system are deﬁnedas applicants. Applicants are divided into two groups: good applicants and badapplicants. There is probability P that the potential applicants are good. Thepotential applicants enter the system with a Poisson arrival rate of K, includingFig. 1 Flowchart of screening system

Simulating a Multi-Stage Screening Network Table 1 The notation used in this chapterKPotential applicants’ total arrival ratePli ¼ 1; 2; 3; . . .; stbPercentage of good potential applicants in potential applicantsService rate in screening pointStage numberProbability of screening in the ﬁrst stageAfter passing the ði 1Þth stage, probability of screening in ith stageAfter failed the ði 1Þth stage, probability of screening in ith stageProbability of reject good applicantsProbability of approving bad applicantsReward of passing for good applicantsWaiting cost of good applicantsTotal waiting time of good applicantsWaiting time in ith stageReward of passing for bad applicantsCost of getting caught for bad applicantsReward for approving good applicants for approverReward for denying bad applicants for approverCost for denying good applicants for approverCost for approving bad applicants for approverSimulation data: number of good deniedSimulation data: number of bad approvedSimulation data: number of good approvedSimulation data: number of bad deniedApprover’s utilityExpected utility for good applicants before deciding enteringExpected utility for bad applicants before deciding enteringCalculated probability of passing for good applicantsCalculated probability of passing for bad applicantsCalculated probability of getting caught for bad applicantsRepresents U1 in simulationRepresents U2b in simulationRepresents U2g in simulationRepresents P in simulationRepresents a in simulationRepresents b in simulationRepresents l in simulationRepresents K in simulationRepresents rg in simulationRepresents cw in simulationRepresents rb in simulationRepresents cb in simulation59

60X. Wang et al.good potential applicants’ arrival rate of Kg and bad potential applicants’ arrivalrate of Kb . The one who takes charge of the system is deﬁned as approver. Theapprover screens the selected applicants with a service rate of l.To simplify the model, we assume service rates at each stage are equal. The M/M/1 queueing model is applied to study screening process at each stage. Theprobabilities of screening at each stage are deﬁned as Ui ; Uig ; Uib fori ¼ 1; 2; . . .; N. From the second stage, suspected good applicants and suspectedbad applicants would have different screening probabilities. For suspected goodapplicants we use Uig , while Uib is for suspected bad applicants. When the applicants enter the system, the approver screens them according to the probability Uig orUib . At stage 1, those who are not screened will pass immediately. At stageið1 & i & NÞ, those who are not screened will be approved or denied immediatelyaccording to the last stage screening results. Those who are screened are facingthree consequences after one of the three stages of screening: approved, denied orenter to next stage i 1. At stage N, those who are not screened will be approved ordenied immediately according to the last stage result. Those who are screened at thelast stage will pass or fail according to their own attributes (good or bad).We assume that type I and type II errors are the same at each stage. We deﬁnetype I error probability as a, and type II error probability as b. While there is aprobability a that good applicants would be screened as suspected bad applicants ateach stage, there is a probability b of vice versa.We deﬁne the good applicants as those who receive reward rg when gettingapproved, and pay a cost cw per unit waiting time. Similarly, we deﬁne the badapplicants as those who receive reward rb when getting approved, and pay a penaltycb while getting caught. As we assume that rb ' cw , waiting cost is neglected at thiscase. On the other hand, we deﬁne the approvers as those who receive reward Rgwhen approving good applicants and reward Rb when denying bad applicants. Theapprover pays cost Cg when denying good applicants and cost Cb when approvingbad applicants. We collect data after simulating for the number of good approved Nrg ,the number of good denied Nfb , the number of bad approved Nfg and the number ofbad denied Nrb . The approver’s utility is deﬁned as U. We deﬁne the calculatedprobability of passing for good applicants as Pag and the waiting time in queue as w.2.2 Payoffs of Applicants and ApproverApprover’s expected utility is shown in Eq. (1), where he maximizes his utilitypayoff.U ¼ Nrg Rg þ Nrb Rb Nfg Cg Nfb Cbð1ÞFor applicants, we also use their utilities to scale their payoffs. Good applicants’utility is deﬁned as ug in Eq. (2), where he maximizes his utility payoff.

Simulating a Multi-Stage Screening Network 61ug ¼ Pag rg wcwPag ¼1 nXU1j¼2a j ð1 aÞn jþ U1 ð1 aÞn 1 aþ U1j 1nXXj¼3j 2þð1 aÞi¼2anYnYUigi¼2!j 1Yk¼2Uigp¼2i¼2Upg!!!þ U1 að1 U2b Þj i 1 ið1 aÞjYUpbaj 1YUkgk¼2!Ukg ð1 Ujb Þ!ð2ÞiYUpbp¼2Upg!!ð1 Ujb Þ!!ð3ÞTo represent this series of problems, we use an M/M/1 queue as the queueingmodel, where there is a single server, unlimited waiting space, Poison arrival andexponential service time. Based on M/M/1 queue theory, at each screening point,we have waiting time W is shown in Eq. (4):W¼1l kð4ÞFor an N-stage screening, the total waiting time of good applicants is thesummation of the screening waiting time at each stage, which are shown in Eq. (5).1l U1 K1 aaw2 ¼þl U1 U2g K l U1 U2b Kw1 ¼w3 ¼.wn ¼ð1 aÞ2ð1 aÞað1 aÞaa2þþþl U1 U2g U3g K l U1 U2g U3b K l U1 U2b U3g K l U1 U2b U3b Kð1 aÞn 1ð1 aÞn 2 aþl U1 U2g U3g U4g . . .Ung K l U1 U2b U3g U4g . . .Ung Kþð1 aÞn 2 að1 aÞn 2 aþ !!! þl U1 U2g U3b U4g . . .Ung Kl U1 U2g U3g U4g . . .Unb Kð1 aÞn 3 a2an 1þ !!! þl U1 U2b U3b U4g . . .Ung Kl U1 U2b U3b U4b . . .Unb KnXwiw¼þi¼1ð5Þ

62X. Wang et al.Change Input ParametersMatlab GUISimulationCollect Output for Data AnalysisFig. 2 Relationship between simulation and matlab GUIBad applicant’s utility is deﬁned as ub is shown in Eq. (6), where he maximizeshis utility payoff.ub ¼ Pab rb Pdb cbð6ÞWe deﬁne the expected probability of passing for bad applicants as Pab inEq. (7), the expected probability of getting bad applicants caught as Pdb in Eq. (8).Pab ¼ 1 U1nXj¼2n 1þ U1 bþ U1þbj 2ð1 bÞ bð1 bÞj 1nXXj¼3nYbj 1Yk¼2Uigi¼2j i 1i¼2ð1 bÞnYj n j!p¼2i¼2Upg!!!þ U1 ð1 bÞð1 U2b Þð1 bÞ!UigjYUpbij 1YUkgk¼2Ukg ð1 Ujb Þ!Pdb ¼ 1 PabiYUpbUp¼2 pg!!!!ð1 Ujb Þð7Þð8ÞBy combining simulation and Matlab GUI, Fig. 2 shows the relationshipbetween the tools we used.3 SimulationArena is used to simulate the screening system. After each run, we get the numbersof applicants that are good but denied, bad but approved, good and approved andbad and denied. We deﬁne them as fake bad Nfb , fake good Nfg , real bad Nrb andreal good Nrg . Figure 3 shows the whole structure of two-stage imperfect securityscreening process.

Simulating a Multi-Stage Screening Network 63(c)A1Potential ostwReadRewardbReadCostbAssignC00type devide(a)0TrueFalse0waive outgoodA2True00good decide to enterFalseFalse000Truebad decide to enterbadTruefirst stageDispose 1True00A3FalseFalse0screen00Pass00Trueerror adjustment gFalseTrueFalse00error adjustment b00second stage for good0True0screen 2gpass 2g0False0False0Trueerror adjustment ggFalseTrueTrueFalse0(b)0error adjustment bgFalse00second stage for bad0FalseTrue0screen 2bpass 2b00FalseTrueTrue0defergoodFalse00error adjustment gbTrue0False0deferbad0error adjustment bb0True0TrueFalseTrueFalseFig. 3 Simulating two-stage imperfect security screening process3.1 Simulating a Perfect One-Stage Screening SystemFigure 3 part A excluding A2 shows the simulation of a one-stage imperfectscreening process. First of all, we need to put a “Create” module named “PotentialArrival” to simulate potential applicants’ arrival. It is Poison arrival as we describedwith the arrival rate of K, and “inﬁnite” as max arrival. We deﬁne a variable “ar”

64X. Wang et al.Fig. 4 Using “Create” module to simulate all applicants’ arrivalsrepresent K, as Greek letters cannot be typed in Arena. “ar” has no value, and weassign a value to it in Sect. 5. Variable K ¼ “ar” per day holds the information thatthere is an average of “ar” persons arriving everyday. Figure 4 shows how to use“Create” module to simulate all applicants’ arrivals. To set “Time BetweenArrivals,” there are several types to choose from: random[Expo], Schedule, Constant, and Expression. If you choose Expression, there are more Arena functionslike WEIB and POIS you can choose from. In this case, we simulate a Poissonarrival process, then choose the “Type” of “Expression.” The “Value Expression”box should be ﬁlled in with time value but not with rate value, “POIS(0.001).” Thevalue of 0.001 is an approximate value, we may adjust it later in Sect. 5. Unitsshould be deﬁned correctly, so we put in “Days” here. In the last row, we deﬁne oneentity at each arrival. “Max Arrival” is “Inﬁnite” and ﬁrst “Creation” is zero. Theabove simulates that every potential applicant follows a Poisson process, in anaverage of every 0.001 day to arrive.Then, we divide potential applicants into two categories: g

theory to construct the dynamic system of screening system in this paper. Queueing theory is the mathematical study of waiting lines [23]. In queueing theory, a model is constructed so that queue length

Related Documents: