# Sensor Networks Hierarchical Optimization Model for Security Monitoring in High-Speed Railway Transport Hub

Authors: Zhengyu Xie; Yong Qin
Journal: Journal of Sensors
 (2015)

---

## Abstract

We consider the sensor networks hierarchical optimization problem in high-speed railway transport hub (HRTH). The sensor networks are optimized from three hierarchies which are key area sensors optimization, passenger line sensors optimization, and whole area sensors optimization. Case study on a specific HRTH in China showed that the hierarchical optimization method is effective to optimize the sensor networks for security monitoring in HRTH.


---

## Body

## 1. Introduction

With the rapid development of high-speed railway in China, many modern HRTHs have been built to match the developing demands. HRTHs become the crossing and interface of multitransportation which include high-speed railway, civil aviation, highway, waterway, urban rail transit, public transport, motor vehicle, and taxi. As a vital node of passenger transport net, HRTH is an important distribution place of massive passenger flow. With the increase of high-speed railway operation mileage, the distribution quantity of passengers will be sustained to increase sharply, which leads HRTHs to confront severe challenges in passenger flow security monitoring.At present, the video surveillance system is the main security monitoring approach used in HRTH. The managers can detect the congestion of passenger flow, abnormal behaviors of passengers, abandoned objects, and so forth by using surveillance systems. The basic workflow of system includes the following: (i) data acquisition: distribute surveillance sensors and develop a sensor network; (ii) data transmission: choose suitable approaches to transmit data acquired from the sensor networks; (iii) data processing: utilize efficient image processing method to process the data acquired from the sensor networks and obtain processing result based on the demands of security monitoring; (iv) data dissemination: select various channels to disseminate the security monitoring information. Currently, the studies related to video surveillance system in HRTH mainly focused on (ii) and (iii) to improve detection accuracy and speed; specific study on (i) is scarce. As a foundation of other parts, the sensor networks have important influences on other parts. So it is necessary for HRTH security monitoring to optimize the sensor networks.The rest of this paper is organized as follows: The relevant literature is reviewed in the next section. The sensor networks hierarchical optimization problem is described in Section3 and Section 4 proposes a sensor networks hierarchical optimization model. A case study is reported in Section 5 and finally Section 6 covers the conclusion.


## 2. Literature Review

The sensor networks optimization problem for security monitoring in HRTH belongs to the art gallery problem (AGP) which was first proposed in 1973 in a conversation between Klee and Chvatal [1]. Based on the conversation, Chvatal proofed [n/3] cameras are always sufficient and sometimes necessary. This conclusion is called the Art Gallery Theorem, or Watchman Theorem [2]. Fisk used triangulation techniques and staining methods and got the conclusion “any simple polygon after triangulation, the corresponding diagram can 3-stain,” and the same type of colored dots can cover the entire simple polygon [3]. Avis, Toussaint, and Chazelle gave different algorithms for the simple polygon triangulation. For any simple polygon with given point, we can determine the location of monitors in a simple polygon within time, making any point in this simple polygon able to see at least one monitor [4, 5]. Lee and Lin proved that the algorithm of solving any simple polygon which required minimum number of guards is NP-hard [6].After Art Gallery Theorem is proved, more and more questions of AGP are proposed, including the following: the monitor can be moved at the edge, the monitor can be moved at the diagonal, at least two monitors are required that can be guarded by each other, one guard is removed while the other guards could know, and the walls of the gallery should be vertical [7, 8].In computational geometry, the gallery can be abstract simple polygon; put a monitor abstraction for a point in simple polygon, and then the problem can be abstracted as an art gallery plane geometry problem; gallery guards problem can be abstracted as how many points can cover the entire simple polygon. Variant problem can be abstracted as joint guards, side cover, diagonal coverage, coguards, orthogonal gallery guards, moving guard, limited perspective guards, moving guard with limited perspective, orthogonal polygons mobile guards, and other issues [9, 10].For unrealistic assumptions of monitor in the solving of AGP and its variant problem, such as magnifying the monitoring range of single monitor, expanding the depth of field, and not limiting the recognition accuracy and speed, lead to research in art galleries and related issues are hard to be good application in the actual layout of video surveillance capture point.Applied researches of monitor sensors layout mainly put video monitor sensors layout problem into set covering problem. Chakrabarty and Bulusu used the method of linear programming to obtain the minimum activity to maintain coverage node set [11, 12]. Meguerdichian et al. made more complex coverage model which, from the perspective of minimizing the uncovered area of the start, considers the problem of network coverage uniformity runtime based on the degree of coverage [13]. Erdem and Sclaroff proposed an efficient algorithm to calculate the radial scans of each collection point in the visual range of the camera, so that the total layout costs are optimized while the collection point layout constraints can be met [14].


## 3. Problem Description

In this section, the sensor networks hierarchical optimization problem is described in three aspects. Firstly, the data acquisition demands of security monitoring in HRTH are analyzed. Secondly, the hierarchical organization of sensor networks is described. Based on the previous two parts, the basic process of security monitoring based on multilayer sensor networks is designed in the last part.


### 3.1. Data Acquisition Demands of Security Monitoring in HRTH

According to the different safety forewarning focuses, the security monitoring can be divided into three levels, and each level has its specific data acquisition demands. The data acquisition demands of security monitoring in HRTH are shown in Table1.Table 1
Data acquisition demands of security monitoring in HRTH.
Level
Description
Concern
Data acquisition demands
First level
Key area monitoring
Focus on the security of key, important, and sensitive areas
The data of key areas in HRTH must be continuously acquired and can meet the anomaly detection of key areas
Second level
Passenger line monitoring
Focus on the security of passenger input and output lines
The data of entire passenger line in HRTH must be continuously acquired and can meet the forecast demands of post node in passenger line
Third level
Complete coverage monitoring
Focus on the security of whole HRTH
The data of whole HRTH can be inconsecutively and optionally acquired and must ensure all function areas are completely coveredThe demands relationship among three levels is shown in Figure1. The demands covered areas are gradually increasing from the first level to the third level, and the timeliness and precision of data acquisition are gradually increasing from the opposite direction.Figure 1
Demands relationship among three levels.


### 3.2. Hierarchical Organization of Sensor Networks

Based on the data acquisition demands analysis above, the sensor networks for security monitoring in HRTH are classified into three hierarchies, which are one-to-one correspondence to the data acquisition demands levels. The hierarchical organization of sensor networks is shown in Table2.Table 2
Hierarchical organization of sensor networks.
Sensor network
First hierarchy
Key area monitoring sensors
(i) Sensors in different key areas are independent and do not have any relevance(ii) Sensors do not need adjustment after setting(iii) Sensors have front-end event detecting software
Second hierarchy
Passenger line monitoring sensors
(i) Sensors should be set following the passenger line(ii) Sensors in same passenger line have association(iii) Sensors do not need adjustment after setting(iv) The data acquired by sensors should be continuously transferred to the control center to process
Third hierarchy
Complete coverage monitoring sensors
(i) Sensors should cover all the function areas in HRTH(ii) The monitoring areas of sensors should reduce overlaps as much as possible(iii) Sensors can adjust monitoring areas after setting(iv) The data acquired by sensors should be continuously transferred to the control center to be stored


### 3.3. Basic Structure of Security Monitoring Based on Multilayer Sensor Networks

According to the above analysis in this section, a basic process of security monitoring is designed based on multilayer sensor networks. The structure is shown in Figure2.Figure 2
Basic structure of security monitoring.As observed in Figure2, in the first hierarchy, anomalies in key areas are detected by monitoring sensors, and then the anomaly detection data are transmitted to control center and inform monitoring personnel to respond. In the second hierarchy, passenger flow data are acquired by monitoring sensors and transmitted to control center. According to the incidence relation among sensors, the passenger flow data can be processed to obtain real-time passenger flow status, search the post node in passenger line, and forecast the variation trend of passenger flow. The monitoring personnel can forewarn passenger flow congestion and make emergency response based on the processing results. The third hierarchy mainly focuses on the overall safe state of HRTH. The monitoring personnel need to use the monitoring sensors to observe function areas in HRTH when the first or second hierarchy has safety forewarning. This hierarchy is a supplement for the previous two hierarchies.


## 3.1. Data Acquisition Demands of Security Monitoring in HRTH

According to the different safety forewarning focuses, the security monitoring can be divided into three levels, and each level has its specific data acquisition demands. The data acquisition demands of security monitoring in HRTH are shown in Table1.Table 1
Data acquisition demands of security monitoring in HRTH.
Level
Description
Concern
Data acquisition demands
First level
Key area monitoring
Focus on the security of key, important, and sensitive areas
The data of key areas in HRTH must be continuously acquired and can meet the anomaly detection of key areas
Second level
Passenger line monitoring
Focus on the security of passenger input and output lines
The data of entire passenger line in HRTH must be continuously acquired and can meet the forecast demands of post node in passenger line
Third level
Complete coverage monitoring
Focus on the security of whole HRTH
The data of whole HRTH can be inconsecutively and optionally acquired and must ensure all function areas are completely coveredThe demands relationship among three levels is shown in Figure1. The demands covered areas are gradually increasing from the first level to the third level, and the timeliness and precision of data acquisition are gradually increasing from the opposite direction.Figure 1
Demands relationship among three levels.


## 3.2. Hierarchical Organization of Sensor Networks

Based on the data acquisition demands analysis above, the sensor networks for security monitoring in HRTH are classified into three hierarchies, which are one-to-one correspondence to the data acquisition demands levels. The hierarchical organization of sensor networks is shown in Table2.Table 2
Hierarchical organization of sensor networks.
Sensor network
First hierarchy
Key area monitoring sensors
(i) Sensors in different key areas are independent and do not have any relevance(ii) Sensors do not need adjustment after setting(iii) Sensors have front-end event detecting software
Second hierarchy
Passenger line monitoring sensors
(i) Sensors should be set following the passenger line(ii) Sensors in same passenger line have association(iii) Sensors do not need adjustment after setting(iv) The data acquired by sensors should be continuously transferred to the control center to process
Third hierarchy
Complete coverage monitoring sensors
(i) Sensors should cover all the function areas in HRTH(ii) The monitoring areas of sensors should reduce overlaps as much as possible(iii) Sensors can adjust monitoring areas after setting(iv) The data acquired by sensors should be continuously transferred to the control center to be stored


## 3.3. Basic Structure of Security Monitoring Based on Multilayer Sensor Networks

According to the above analysis in this section, a basic process of security monitoring is designed based on multilayer sensor networks. The structure is shown in Figure2.Figure 2
Basic structure of security monitoring.As observed in Figure2, in the first hierarchy, anomalies in key areas are detected by monitoring sensors, and then the anomaly detection data are transmitted to control center and inform monitoring personnel to respond. In the second hierarchy, passenger flow data are acquired by monitoring sensors and transmitted to control center. According to the incidence relation among sensors, the passenger flow data can be processed to obtain real-time passenger flow status, search the post node in passenger line, and forecast the variation trend of passenger flow. The monitoring personnel can forewarn passenger flow congestion and make emergency response based on the processing results. The third hierarchy mainly focuses on the overall safe state of HRTH. The monitoring personnel need to use the monitoring sensors to observe function areas in HRTH when the first or second hierarchy has safety forewarning. This hierarchy is a supplement for the previous two hierarchies.


## 4. Sensor Networks Hierarchical Optimization Model

According to the problem description in Section3, a sensor networks hierarchical optimization model is proposed in this section. Sensor networks for security monitoring in HRTH are optimized from three hierarchies based on the hierarchical organization mentioned above. The hierarchical optimization framework is shown in Figure 3.Figure 3
Hierarchical optimization framework.


### 4.1. Key Area Sensors Optimization

The core concern of key area sensors optimization is to determine the key areas in HRTH. According to the different area characteristic, the key areas can be mainly divided into congestion areas and sensitive areas. Each area has its specific determination method.


#### 4.1.1. Congestion Areas Determination Method

The congestion areas are mainly determined by the computation result. There are three main methods to calculate the relation between passenger flow and facilities capacity, which are described as follows.(1) Capacity Method. Capacity method is used to determine facilities congestion. This method divides the passenger line into several units and calculates the capacity balance of units. When the facility design capacity is less than practical capacity, this facility is considered a key area. The facility design capacity is calculated by (1)C=W·q·φ.W is the width of the facility. q is the predicted passenger flow volume. φ is the peak period coefficient.(2) Delay Method. Delay is an important judging parameter for the congestion of passenger line. The passenger delay in HRTH mainly results from queuing, congesting, and waiting behaviors. The calculation of three behaviors is shown in Table 3.Table 3
Calculation of three behaviors.
Delay behaviors
Generation mechanism
Calculation
Range of application
Queuing delay
The facility service capability is less than passenger arrival rate
λ
μ
-
λ
2
Ticket entrance, wicket, baggage check entrance, and so forth
Congesting delay
The facility cannot be used when the passengers arrive
∫
t
0
t
n
q
t
d
t
-
n
∫
n
T
+
(
n
-
1
)
q
(
t
)
n
T
+
(
n
-
1
)
(
k
1
+
k
2
)
q
(
t
)
q
t
d
t
Ticket entrances delay check caused by train late
Waiting delay
The facility capacity is insufficient, which leads to high density and low speed of passenger flow
L
k
j
k
u
f
The service capability of interface channel between service nodes is insufficient(3) Density Method. Passenger flow density is an effective indicator to measure congestion level. The higher density passenger flow has, the more congestion in passenger line arises. This density is named congestion density and calculated by(2)ρijt=nijtMij.ρij(t) is congestion density of the jth segment in the ith passenger line. Mij is the facility available area of the jth segment in the ith passenger line. nij(t) is passenger amount of the jth segment in the ith passenger line.


#### 4.1.2. Sensitive Areas Determination Method

Sensitive areas determination, compared with congestion areas determination, is relatively simple and does not have specific calculating method. Most of sensitive areas are determined based on the actual demand of security monitoring in HRTH. The common sensitive areas include distribution facility areas, fireproofing facility areas, office areas, and security check areas.


### 4.2. Passenger Line Sensors Optimization

The core concerns of passenger line sensors optimization are to determine the passenger line type and generate the passenger line under established facility layout.


#### 4.2.1. Passenger Line Type Determination

The passenger line in HRTH can be mainly divided into passenger output line, passenger input line, and passenger transfer line. These three types of passenger lines are described as follows.(1) Passenger Input Line. The passenger input line begins at passenger arriving at HRTH and finishes after passenger gets in trains. In the period between passenger arriving and leaving, there are several events happening, such as purchasing tickets, shopping, dining, and waiting in trains. The passenger input line and procedure are shown in Figure 4.Figure 4
Passenger input line and procedure.(2) Passenger Output Line. The passenger output line begins at train arriving at HRTH and finishes after passenger leaves HRTH. Compared with passenger input line, passenger output line has few events and is relatively simple. The output passengers flow has characteristics of being concentrated, high density, and short stay time. The passenger output line and procedure are shown in Figure 5.Figure 5
Passenger output line and procedure.(3) Passenger Transfer Line. Passenger transfer line is similar to passenger input line and relatively simple, so we do not introduce it in detail.


#### 4.2.2. Passenger Line Generation

After determining the passenger line type, passenger line is generated based on the established facility layout of HRTH. Generation steps are shown as follows.Step 1.
Mark the geometric center of facilities in HRTH function areas and use these geometric centers as the origin-destination points.Step 2.
Use directed line segments to link geometric centers based on passenger moving tracks in different type passenger lines.Step 3.
Classify the directed line segments, use different color to denote different type passenger lines, and use different thicknesses lines to denote the amount of passenger flow.


### 4.3. Whole Area Sensors Optimization

In order to ensure that all function areas in HRTH are covered by sensors, a whole area sensors optimization framework is proposed in this section. After space two-dimension, space partition and visibility analysis, we change the whole area sensors optimization problem into set covering problem and develop a set covering model. The whole area sensors optimization framework is shown in Figure6.Figure 6
Whole area sensors optimization framework.Step 1 (HRTH space two-dimension).
HRTH space two-dimension is to make the three-dimensional space into a two-dimension ichnography and scale down the layout of facilities and instruments. After HRTH space two-dimension, we can obtain a schematic representation of whole HRTH.Step 2 (HRTH space partition).
After obtaining the schematic representation, we abstract the facilities and instruments into square or rectangle and lengthen the sides of square and rectangle. A space partition sample is shown in Figure7.Figure 7
A space partition sample.
(a)
(b)Step 3 (visibility analysis).
Based on HRTH space partition, we analyze the visibility of each region in schematic representation. The visibility analysis includes two parts.
The first part is to analyze the geometric visibility. Assume the region center is the laying position. If the link line between two regions is not interrupted by facilities or instruments, the two regions are considered geometric visibility. Figure8(a) is a geometric visibility analysis sample. The geometric visibility set of R12 is R3,R4,R5,R7,R8,R9,R10,R11,R13,R14,R15,R16,R17.
The second part is visual range analysis. We set the coverage of one sensor as a circle whose radius is the visual range of sensor. The regions which are covered by the circle are the visual regions. Figure8(b) is a visual range analysis sample. The visual visibility set of R12 is V12=R7,R8,R10,R11,R13,R14,R17.Figure 8
Visibility analysis samples.
(a)
(b)Step 4 (a set covering model for whole area sensors optimization).
In this step, we develop a set covering model to describe the whole area sensors optimization problem.(1) Notations and Variables. Consider the following:i,j: region index,m: total amount of regions,R: visual range of sensor,dis(i,j): the distance between region i and region j,Wi: weighted values,xi: 0-1 variable; if sensor is set in region i, xi=1; otherwise, xi=0,covi,j: 0-1 variable; if the visual range of region i can cover region j, covi,j=1; otherwise, covi,j=0.(2) Objective Function. The objective function of whole area sensors optimization model is written as follows: (3)Minimize⁡Z=∑i=0mWixi.The objective function minimizes the amount of sensors to cover whole function areas in HRTH.(3) Constraints. The constraints of whole area sensors optimization model are introduced as follows to ensure the practical feasibility of the solution:(4)∑i1=0mcovi,jxi1≥1,0≤j≤m,(5)covi,j·R-disi,j≥0,0≤i≤m,0≤j≤m,(6)1-covi,j·disi,j-R≥0,0≤i≤m,0≤j≤m,(7)xi∈0,1,(8)covi,j∈0,1.Constraint (4) represents that each region in HRTH should at least be covered by one sensor. Constraint (5) ensures that the distance between sensor and covered region cannot be larger than the visual range of sensor. Constraint (6) represents that the region whose distance is larger than the visual range of sensor cannot be covered by this sensor. Constraint (7) and Constraint (8) are 0-1 variable constraints.Step 5 (solution algorithm).
In order to solve the optimization model developed above, a heuristic algorithm is proposed in this section.X is the area set of two-dimension division. m is the elements amount in X. C is the area set of sensors layout. q is the elements amount in C. The algorithm implement process is shown in Figure 9.Figure 9
Algorithm implement process.


## 4.1. Key Area Sensors Optimization

The core concern of key area sensors optimization is to determine the key areas in HRTH. According to the different area characteristic, the key areas can be mainly divided into congestion areas and sensitive areas. Each area has its specific determination method.


### 4.1.1. Congestion Areas Determination Method

The congestion areas are mainly determined by the computation result. There are three main methods to calculate the relation between passenger flow and facilities capacity, which are described as follows.(1) Capacity Method. Capacity method is used to determine facilities congestion. This method divides the passenger line into several units and calculates the capacity balance of units. When the facility design capacity is less than practical capacity, this facility is considered a key area. The facility design capacity is calculated by (1)C=W·q·φ.W is the width of the facility. q is the predicted passenger flow volume. φ is the peak period coefficient.(2) Delay Method. Delay is an important judging parameter for the congestion of passenger line. The passenger delay in HRTH mainly results from queuing, congesting, and waiting behaviors. The calculation of three behaviors is shown in Table 3.Table 3
Calculation of three behaviors.
Delay behaviors
Generation mechanism
Calculation
Range of application
Queuing delay
The facility service capability is less than passenger arrival rate
λ
μ
-
λ
2
Ticket entrance, wicket, baggage check entrance, and so forth
Congesting delay
The facility cannot be used when the passengers arrive
∫
t
0
t
n
q
t
d
t
-
n
∫
n
T
+
(
n
-
1
)
q
(
t
)
n
T
+
(
n
-
1
)
(
k
1
+
k
2
)
q
(
t
)
q
t
d
t
Ticket entrances delay check caused by train late
Waiting delay
The facility capacity is insufficient, which leads to high density and low speed of passenger flow
L
k
j
k
u
f
The service capability of interface channel between service nodes is insufficient(3) Density Method. Passenger flow density is an effective indicator to measure congestion level. The higher density passenger flow has, the more congestion in passenger line arises. This density is named congestion density and calculated by(2)ρijt=nijtMij.ρij(t) is congestion density of the jth segment in the ith passenger line. Mij is the facility available area of the jth segment in the ith passenger line. nij(t) is passenger amount of the jth segment in the ith passenger line.


### 4.1.2. Sensitive Areas Determination Method

Sensitive areas determination, compared with congestion areas determination, is relatively simple and does not have specific calculating method. Most of sensitive areas are determined based on the actual demand of security monitoring in HRTH. The common sensitive areas include distribution facility areas, fireproofing facility areas, office areas, and security check areas.


## 4.1.1. Congestion Areas Determination Method

The congestion areas are mainly determined by the computation result. There are three main methods to calculate the relation between passenger flow and facilities capacity, which are described as follows.(1) Capacity Method. Capacity method is used to determine facilities congestion. This method divides the passenger line into several units and calculates the capacity balance of units. When the facility design capacity is less than practical capacity, this facility is considered a key area. The facility design capacity is calculated by (1)C=W·q·φ.W is the width of the facility. q is the predicted passenger flow volume. φ is the peak period coefficient.(2) Delay Method. Delay is an important judging parameter for the congestion of passenger line. The passenger delay in HRTH mainly results from queuing, congesting, and waiting behaviors. The calculation of three behaviors is shown in Table 3.Table 3
Calculation of three behaviors.
Delay behaviors
Generation mechanism
Calculation
Range of application
Queuing delay
The facility service capability is less than passenger arrival rate
λ
μ
-
λ
2
Ticket entrance, wicket, baggage check entrance, and so forth
Congesting delay
The facility cannot be used when the passengers arrive
∫
t
0
t
n
q
t
d
t
-
n
∫
n
T
+
(
n
-
1
)
q
(
t
)
n
T
+
(
n
-
1
)
(
k
1
+
k
2
)
q
(
t
)
q
t
d
t
Ticket entrances delay check caused by train late
Waiting delay
The facility capacity is insufficient, which leads to high density and low speed of passenger flow
L
k
j
k
u
f
The service capability of interface channel between service nodes is insufficient(3) Density Method. Passenger flow density is an effective indicator to measure congestion level. The higher density passenger flow has, the more congestion in passenger line arises. This density is named congestion density and calculated by(2)ρijt=nijtMij.ρij(t) is congestion density of the jth segment in the ith passenger line. Mij is the facility available area of the jth segment in the ith passenger line. nij(t) is passenger amount of the jth segment in the ith passenger line.


## 4.1.2. Sensitive Areas Determination Method

Sensitive areas determination, compared with congestion areas determination, is relatively simple and does not have specific calculating method. Most of sensitive areas are determined based on the actual demand of security monitoring in HRTH. The common sensitive areas include distribution facility areas, fireproofing facility areas, office areas, and security check areas.


## 4.2. Passenger Line Sensors Optimization

The core concerns of passenger line sensors optimization are to determine the passenger line type and generate the passenger line under established facility layout.


### 4.2.1. Passenger Line Type Determination

The passenger line in HRTH can be mainly divided into passenger output line, passenger input line, and passenger transfer line. These three types of passenger lines are described as follows.(1) Passenger Input Line. The passenger input line begins at passenger arriving at HRTH and finishes after passenger gets in trains. In the period between passenger arriving and leaving, there are several events happening, such as purchasing tickets, shopping, dining, and waiting in trains. The passenger input line and procedure are shown in Figure 4.Figure 4
Passenger input line and procedure.(2) Passenger Output Line. The passenger output line begins at train arriving at HRTH and finishes after passenger leaves HRTH. Compared with passenger input line, passenger output line has few events and is relatively simple. The output passengers flow has characteristics of being concentrated, high density, and short stay time. The passenger output line and procedure are shown in Figure 5.Figure 5
Passenger output line and procedure.(3) Passenger Transfer Line. Passenger transfer line is similar to passenger input line and relatively simple, so we do not introduce it in detail.


### 4.2.2. Passenger Line Generation

After determining the passenger line type, passenger line is generated based on the established facility layout of HRTH. Generation steps are shown as follows.Step 1.
Mark the geometric center of facilities in HRTH function areas and use these geometric centers as the origin-destination points.Step 2.
Use directed line segments to link geometric centers based on passenger moving tracks in different type passenger lines.Step 3.
Classify the directed line segments, use different color to denote different type passenger lines, and use different thicknesses lines to denote the amount of passenger flow.


## 4.2.1. Passenger Line Type Determination

The passenger line in HRTH can be mainly divided into passenger output line, passenger input line, and passenger transfer line. These three types of passenger lines are described as follows.(1) Passenger Input Line. The passenger input line begins at passenger arriving at HRTH and finishes after passenger gets in trains. In the period between passenger arriving and leaving, there are several events happening, such as purchasing tickets, shopping, dining, and waiting in trains. The passenger input line and procedure are shown in Figure 4.Figure 4
Passenger input line and procedure.(2) Passenger Output Line. The passenger output line begins at train arriving at HRTH and finishes after passenger leaves HRTH. Compared with passenger input line, passenger output line has few events and is relatively simple. The output passengers flow has characteristics of being concentrated, high density, and short stay time. The passenger output line and procedure are shown in Figure 5.Figure 5
Passenger output line and procedure.(3) Passenger Transfer Line. Passenger transfer line is similar to passenger input line and relatively simple, so we do not introduce it in detail.


## 4.2.2. Passenger Line Generation

After determining the passenger line type, passenger line is generated based on the established facility layout of HRTH. Generation steps are shown as follows.Step 1.
Mark the geometric center of facilities in HRTH function areas and use these geometric centers as the origin-destination points.Step 2.
Use directed line segments to link geometric centers based on passenger moving tracks in different type passenger lines.Step 3.
Classify the directed line segments, use different color to denote different type passenger lines, and use different thicknesses lines to denote the amount of passenger flow.


## 4.3. Whole Area Sensors Optimization

In order to ensure that all function areas in HRTH are covered by sensors, a whole area sensors optimization framework is proposed in this section. After space two-dimension, space partition and visibility analysis, we change the whole area sensors optimization problem into set covering problem and develop a set covering model. The whole area sensors optimization framework is shown in Figure6.Figure 6
Whole area sensors optimization framework.Step 1 (HRTH space two-dimension).
HRTH space two-dimension is to make the three-dimensional space into a two-dimension ichnography and scale down the layout of facilities and instruments. After HRTH space two-dimension, we can obtain a schematic representation of whole HRTH.Step 2 (HRTH space partition).
After obtaining the schematic representation, we abstract the facilities and instruments into square or rectangle and lengthen the sides of square and rectangle. A space partition sample is shown in Figure7.Figure 7
A space partition sample.
(a)
(b)Step 3 (visibility analysis).
Based on HRTH space partition, we analyze the visibility of each region in schematic representation. The visibility analysis includes two parts.
The first part is to analyze the geometric visibility. Assume the region center is the laying position. If the link line between two regions is not interrupted by facilities or instruments, the two regions are considered geometric visibility. Figure8(a) is a geometric visibility analysis sample. The geometric visibility set of R12 is R3,R4,R5,R7,R8,R9,R10,R11,R13,R14,R15,R16,R17.
The second part is visual range analysis. We set the coverage of one sensor as a circle whose radius is the visual range of sensor. The regions which are covered by the circle are the visual regions. Figure8(b) is a visual range analysis sample. The visual visibility set of R12 is V12=R7,R8,R10,R11,R13,R14,R17.Figure 8
Visibility analysis samples.
(a)
(b)Step 4 (a set covering model for whole area sensors optimization).
In this step, we develop a set covering model to describe the whole area sensors optimization problem.(1) Notations and Variables. Consider the following:i,j: region index,m: total amount of regions,R: visual range of sensor,dis(i,j): the distance between region i and region j,Wi: weighted values,xi: 0-1 variable; if sensor is set in region i, xi=1; otherwise, xi=0,covi,j: 0-1 variable; if the visual range of region i can cover region j, covi,j=1; otherwise, covi,j=0.(2) Objective Function. The objective function of whole area sensors optimization model is written as follows: (3)Minimize⁡Z=∑i=0mWixi.The objective function minimizes the amount of sensors to cover whole function areas in HRTH.(3) Constraints. The constraints of whole area sensors optimization model are introduced as follows to ensure the practical feasibility of the solution:(4)∑i1=0mcovi,jxi1≥1,0≤j≤m,(5)covi,j·R-disi,j≥0,0≤i≤m,0≤j≤m,(6)1-covi,j·disi,j-R≥0,0≤i≤m,0≤j≤m,(7)xi∈0,1,(8)covi,j∈0,1.Constraint (4) represents that each region in HRTH should at least be covered by one sensor. Constraint (5) ensures that the distance between sensor and covered region cannot be larger than the visual range of sensor. Constraint (6) represents that the region whose distance is larger than the visual range of sensor cannot be covered by this sensor. Constraint (7) and Constraint (8) are 0-1 variable constraints.Step 5 (solution algorithm).
In order to solve the optimization model developed above, a heuristic algorithm is proposed in this section.X is the area set of two-dimension division. m is the elements amount in X. C is the area set of sensors layout. q is the elements amount in C. The algorithm implement process is shown in Figure 9.Figure 9
Algorithm implement process.


## 5. A Case Study

To illustrate the proposed model and algorithm for sensor networks hierarchical optimization problem, a case study is performed by using the actual data from a specific HRTH in China. We choose comprehensive transfer layer of the HRTH as optimization object.This layer is composed by transfer hall, parking area, passenger output system, and passenger input system. There are six entrances, six exits, and four ticket offices in this layer. The transfer hall connects with metro, taxi, and bus. The whole layer has various kinds of passenger lines and crossover among passenger lines.We use the hierarchical optimization method mentioned in Section4 to optimize the sensor networks in this layer. The hierarchical optimization is shown as follows.


### 5.1. Key Area Sensors Optimization

According to the actual passenger flow data in this layer, we use the key area determination method mentioned in Section4.1 to determine key areas. The distribution of key areas in this layer is shown in Figure 10.Figure 10
Distribution of key areas.


### 5.2. Passenger Line Sensors Optimization

Through analysis of origin-destination points and passenger moving tracks, we generate the passenger lines in this layer. The passenger lines are shown in Figure11.Figure 11
Passenger lines in the layer.


### 5.3. Whole Area Sensors Optimization

Follow the whole area sensors optimization framework mentioned in Figure6; the space is partitioned which is shown in Figure 12 and the space partition result is shown in Figure 13.Figure 12
Space partition process.Figure 13
Space partition result.After space partition, the layer is divided into 58 regions. Through the visibility analysis, we can obtain the visual visibility sets of 58 regions and use the heuristic algorithm to find a solution for the whole area sensors optimization model. The final sensors layout region set is{R2,R5,R6,R9,R12,R14,R21,R22,R29,R30,R34,R36,R41,R49,R50,R57}. The solution obtained by the heuristic algorithm is shown in Figure 14.Figure 14
Solution obtained by the heuristic algorithm.According to the hierarchical optimization, the final sensor networks for security monitoring in HRTH are shown in Figure15.Figure 15
Final sensor networks for security monitoring in HRTH.


## 5.1. Key Area Sensors Optimization

According to the actual passenger flow data in this layer, we use the key area determination method mentioned in Section4.1 to determine key areas. The distribution of key areas in this layer is shown in Figure 10.Figure 10
Distribution of key areas.


## 5.2. Passenger Line Sensors Optimization

Through analysis of origin-destination points and passenger moving tracks, we generate the passenger lines in this layer. The passenger lines are shown in Figure11.Figure 11
Passenger lines in the layer.


## 5.3. Whole Area Sensors Optimization

Follow the whole area sensors optimization framework mentioned in Figure6; the space is partitioned which is shown in Figure 12 and the space partition result is shown in Figure 13.Figure 12
Space partition process.Figure 13
Space partition result.After space partition, the layer is divided into 58 regions. Through the visibility analysis, we can obtain the visual visibility sets of 58 regions and use the heuristic algorithm to find a solution for the whole area sensors optimization model. The final sensors layout region set is{R2,R5,R6,R9,R12,R14,R21,R22,R29,R30,R34,R36,R41,R49,R50,R57}. The solution obtained by the heuristic algorithm is shown in Figure 14.Figure 14
Solution obtained by the heuristic algorithm.According to the hierarchical optimization, the final sensor networks for security monitoring in HRTH are shown in Figure15.Figure 15
Final sensor networks for security monitoring in HRTH.


## 6. Conclusion

In this paper, we considered the sensor networks hierarchical optimization problem in HRTH. A hierarchical optimization framework is proposed, and the problem is solved from three hierarchies which are key area sensors optimization, passenger line sensors optimization, and whole area sensors optimization. In the third hierarchy, a whole area sensors optimization model is developed and a heuristic algorithm is designed. Case study on a specific HRTH in China showed that the hierarchical optimization method is effective to optimize the sensor networks for security monitoring in HRTH. In the future, considering the layout costing in optimization method is a possibility for further research.



---

*Source: 951242-2015-08-02.xml*