论文部分内容阅读
1.INTRODUCTION
Ensuring transportation network security is one Of the most daunting challenges confronting homeland security agencies today. Significant research has been dedicated. To model and analyze the vulnerability of transportation systems，while notably fewer studies propose specific strategies for deploying defensive technologies to safeguard these systems. The ultimate goal of situational awareness for prevention and rapid response remains largely unaddressed. Wireless sensors and ad hoc networks are widely regarded as a promising approach to monitor systems and enhance their security.Furthermore，the growth in smart phone usage can contribute additional relay nodes to the network connecting the deployed sensors and command center. Such sensor networks offer the potential to detect a terrorist plot before it can be executed， support effective response to emergency events，and dynamically monitor traffic flows to facilitate efficient travel within a city.
This paper proposes an algorithm to deploy wireless sensor nodes for monitoring a transportation system in order to provide highly reliable data delivery to a homeland security command center within a city.It is assumed that the vulnerability analysis stage has already been carried out and can therefore guide deployment according to the relative importance for monitoring portions of the city.
The deployed sensor nodes form a network and leverage the additional bandwidth available from smart phones in the city to deliver information to a command center in order to coordinate response services. The existing 3G network is also employed in order to ensure the delivery of data. Certain key properties are required， including sensing coverage， network connectivity， and low end to end delay.
The deployment is formulated as a multi-objective optimization problem to place sensors at a subset of candidate positions to maximize coverage， guarantee connectivity， and provide fault-tolerance， which will ensure low end to end delay . Information from vulnerability analysis， Geographic Information System data， and additional details such as the sensing range of sensor nodes and the mobility patterns of smart phones are incorporated into the utility function of the optimization problem to guide node placement.
We illustrate the approach through a series of simulations with applications to detection， traffic monitoring，and travel guidance based on real GIS data and realistic scenarios. Our results demonstrate the approach cost effectively achieves high coverage， guarantees connectivity，and delivers fault-tolerant end to end delay. 2.DESCRIPTION
This section formulates sensor deployment
as an optimization problem and then solving this formulation to achieve the key performance metrics of the applications. We also Introduce our cell phone assisted routing scheme here.
2.1 Deployment problem formulation
（1）Definition： To capture real-world restrictions on the deployment of sensors in a city such as various forms of private property， our model considers regions where sensors are prohibited. Thus， we first identify a set of candidate deployment locations beforehand in light of these restrictions.This planning step determines candidate positions，represented by matrix Lmn，which indicates the locations of these possible deployment sites throughout the entire transportation system under consideration. Here m is the number of roads，and n the number of points along the mth road.
In3G or even 4G network，some equipments can serve as access points，providing gate ways to connect to existing networks， including the internet. They may also serve as
Each road possesses a quantitative measure of vulnerability， which is based on the importance or criticality of that road. Our previous research [1] offers a game Theoretic approach to assess the vulnerability of the links comprising a network.Other risk based methodologies are also possible.Intuitively，a highly vulnerable road should receive priority for coverage by the monitoring network so that problems occurring on this road can be quickly detected and remediated. The present work assumes that each road possess a constant vulnerability given by Vm.Future research will explore the possibility of time-varying vulnerability.
Because timely response is needed to prevent a problematic situation from worsening，the latency experienced with the network during data delivery is of paramount
importance.Many operations incur delays in a single hop of a wireless network，including transmission delay，propagation delay，and reception delay，as well as encoding and decoding delay.The sum of these operations is represented by the constantτ.Furthermore，tolerant end to end delay from event detection to command center awareness is denoted byτT.A primary objective is to minimize the overall average end to end delay overhead through 3G network.
To concretize this formulation，we de?ne Y
where Vki denotes the vulnerability of the point Lki.Although the vulnerability of each road is given， some candidate points may be situated at intersections.In these situations，the point vulnerability is computed as the sum of the vulnerabilities of all road crossing a point，capturing the criticality of such crossroads. （3）Constraints： are formulated to ensure coverage is achieved.In total，four sets of constraints are considered，including a budget limit for sensors，connectivity requirements，guarantees of tolerant end to end delayτT.
·Budget limit：the budget limit constrainsthe number of available sensors. Weassume the budget is predefined and doesnot change.Thus，it is not possible to addmore sensors during the optimization procedure，hence we have：
·Tolerant end to end delay：Tolerant end toend delay guarantees that all events aredetected can be delivered to the commandcenter within time no greater thanτT， sothat the response can be initiated toprevent the undesirable outcomes that canlead to loss of life and assets. Because thisend to end delay is the sum of the delaysfrom the points where the event happens tothe access point，and from access point tothe command center coverage mustbemore thantheminimumneededto ensureconnectivity.Since wired networks areorders of magnitude faster， the delayfrom access point to the command centertreated as a fixed constant Pa. Thus， thedelay depends primarily on the delay fromlocation of the event’s occurrence to anaccess point. For this reason，each cluster should be able to reach one or more accesspoint，and the overall delay should be lessthanτT.Assuming the delay betweeneach pairs of sensor nodes isηij，wehave：
In above formulation，although the binaryvariable Yki=0can always make theequation hold，however，when the positionshould be selected，Yki should be“1”.Thanks to the maximization in equationEq.（4），Yki tend to be “1”.
By solving the optimization problem with branch-and-cut which is introduced in Section II in linear time， the position where the sensors should be deployed can be figured out. Deploy sensors according to the guideline of
the algorithm， the weighted coverage can be maximized.
2.2Cell phone assisted routing
In this sub-section， we utilize a VBF like[2]routing scheme for mobile smart phones to add additional band-width to the system.
Nowadays， people operate smart phones to talk or text with each other through 3G networks as they travel through the city； They also obtained access to internet through a 3G or 4G network. Thus， smart phones also possess the ability to form an ad hoc network by changing their configurations for the WIFI. In this mode， smart phones can serve as mobile sensor nodes to aid the monitoring system， by helping to deliver some delay tolerant information. Here， we assume that an advertising campaign has successfully recruited a large number of smart phones users to register for the service. and that existing an ad hoc network which enables them to connect to access points throughout the majority of the city. A flooding based routing scheme for the mobile smart phones is then employed todeliver information from sensor nodesnear events to an access points. Sensor nodes and smart phones know their positions as well as the location of access points. Each packet carries the positions of the sender and the target access points for delivery through thead hoc network according to a forwarding path specified by the routing vector from the sender to each target access point. For example， when a smart phone receives a packet， it computes its position relative to the sender andtarget access point. If the smart phone is close enough to the routing vector（e.g.，less than a predefined distance threshold， denoted asW）， it will continue to forward the packet； otherwise， it simply discards the packet. This way，all the smart phones forwarding packets in the ad hoc network form a “routing pipe”. Smart phones in this pipe are eligible for packet forwarding. Those which are notclose to the routing vector（i.e.， the axis of the pipe） do not forward.
Fig.1 Smart phone routing strategy
Fig. 1 illustrates the concept of a routing pipe. Sensor node S0 is the source， and Ap is the target access point，and the routing vector is determined from their locations.Data packets are forwarded from S0 to Ap. Forwarders along the routing vector form a routing pipe with a pre-controlled radius （i.e.， the distance threshold）. The radius of the routing pipe may be increased to ensure the delivery of critical events.
3.PERFORMANCE EVALUATION
3.1 Simulation Settings
The simulations were developed in CPLEX， which provides an implementation of branch-and-cut to solve the optimization problem. There are 100 candidates position， and the topology of the candidates position is a 10 by 10 grid of horizontal and vertical roads intersecting at right angles. The intersections（nodes） are labeled 1 to 100， from the left upper node to the node in the lower right. The vulnerabilities of each horizontal roads is randomly set to 0 to 1 with probability 0.5.
Furthermore， the are a total of 10 access points throughout the city， which can be accessed by both wireless sensor nodes and smart phones. These access points are randomly located in the cityAfter the location of the access points are determined， the shortest path to each candidate position is known. Thus， it becomes possible to apply static routing to route information within the wireless sensor network. There are also 200 registered smart phones randomly distributed in the city， which can help to deliver information. The end to end delay between each pair of smart phones is set to one second， denoted as Ps and events occur randomly throughout the city every one hour. 3.2 Results and Analysis
（1）Coverage：Fig.2 shows the normalized coverage achieved with different numbers of sensors. Clearly， there is a direct relationship between the number of sensors and the attainable coverage. This agrees with intuition because more sensors can cover more area in the city， ensuring that coverage increases. The figure also reveals that increasing the number of sensors does not achieve a linear improvement in the coverage. This sublinear improvement occurs because the optimization scheme covers the most vulnerable portions of the network with greater redundancy to ensure that the command center is notified of events occurring in critical regions. Less vulnerable roads therefore receive less attention.
Fig.2 Normalized coverage vs. number of sensors
（2）Average end to end delay：Fig.3 shows the impact of the number of deployed sensors on the average end to end delay. The average end to end delay is always under 5 seconds，which is the acceptable delay for the detected information to reach the command center. It may also been seen that increasing the number of sensors deployed decreases the average delay. This increase occurs because additional sensor nodes provide more alternative paths to route detected information to access points. Since routing within the wireless sensor network occurs along the shortest paths， these additional paths lower the average end to end delay.
Fig.3 Average delay vs. number of sensors
4.CONCLUSION AND FUTURE WORK
This paper proposes an algorithm to deploy wireless sensor nodes to monitor a transportation system in order to ensure highly reliable data delivery to a homeland security command center within a city.We formulated sensor deployment as an optimization problem to quickly detect events occurring at the most vulnerable portions of the network.We also demonstrated that an ad hoc network formed with smart phones can be harnessed to deliver information to a command center in order to facilitate response.
Future research will apply our scheme with real GIS data to evaluate its performance and identify additional constraints to make the approach more practical for adoption in real-world applications.
【References】
[1]N.Lownes，Q.Wang，S.Ibrahim，R.Ammar，S.Rajasekaran，and D. Sharma， “A many-to-many game theoretic approachtomeasuring transportation network vulnerability，”Transportation ResearchRecord，vol.2263：1-8，mar，2011.
[2]P.Xie，L.Lao，andJ.-H.Cui，“VBF：vector-based forwarding protocol for underwater sensor networks，”in To appear in Proceedings of IFIP Networking，May，2006.
Ensuring transportation network security is one Of the most daunting challenges confronting homeland security agencies today. Significant research has been dedicated. To model and analyze the vulnerability of transportation systems，while notably fewer studies propose specific strategies for deploying defensive technologies to safeguard these systems. The ultimate goal of situational awareness for prevention and rapid response remains largely unaddressed. Wireless sensors and ad hoc networks are widely regarded as a promising approach to monitor systems and enhance their security.Furthermore，the growth in smart phone usage can contribute additional relay nodes to the network connecting the deployed sensors and command center. Such sensor networks offer the potential to detect a terrorist plot before it can be executed， support effective response to emergency events，and dynamically monitor traffic flows to facilitate efficient travel within a city.
This paper proposes an algorithm to deploy wireless sensor nodes for monitoring a transportation system in order to provide highly reliable data delivery to a homeland security command center within a city.It is assumed that the vulnerability analysis stage has already been carried out and can therefore guide deployment according to the relative importance for monitoring portions of the city.
The deployed sensor nodes form a network and leverage the additional bandwidth available from smart phones in the city to deliver information to a command center in order to coordinate response services. The existing 3G network is also employed in order to ensure the delivery of data. Certain key properties are required， including sensing coverage， network connectivity， and low end to end delay.
The deployment is formulated as a multi-objective optimization problem to place sensors at a subset of candidate positions to maximize coverage， guarantee connectivity， and provide fault-tolerance， which will ensure low end to end delay . Information from vulnerability analysis， Geographic Information System data， and additional details such as the sensing range of sensor nodes and the mobility patterns of smart phones are incorporated into the utility function of the optimization problem to guide node placement.
We illustrate the approach through a series of simulations with applications to detection， traffic monitoring，and travel guidance based on real GIS data and realistic scenarios. Our results demonstrate the approach cost effectively achieves high coverage， guarantees connectivity，and delivers fault-tolerant end to end delay. 2.DESCRIPTION
This section formulates sensor deployment
as an optimization problem and then solving this formulation to achieve the key performance metrics of the applications. We also Introduce our cell phone assisted routing scheme here.
2.1 Deployment problem formulation
（1）Definition： To capture real-world restrictions on the deployment of sensors in a city such as various forms of private property， our model considers regions where sensors are prohibited. Thus， we first identify a set of candidate deployment locations beforehand in light of these restrictions.This planning step determines candidate positions，represented by matrix Lmn，which indicates the locations of these possible deployment sites throughout the entire transportation system under consideration. Here m is the number of roads，and n the number of points along the mth road.
In3G or even 4G network，some equipments can serve as access points，providing gate ways to connect to existing networks， including the internet. They may also serve as
Each road possesses a quantitative measure of vulnerability， which is based on the importance or criticality of that road. Our previous research [1] offers a game Theoretic approach to assess the vulnerability of the links comprising a network.Other risk based methodologies are also possible.Intuitively，a highly vulnerable road should receive priority for coverage by the monitoring network so that problems occurring on this road can be quickly detected and remediated. The present work assumes that each road possess a constant vulnerability given by Vm.Future research will explore the possibility of time-varying vulnerability.
Because timely response is needed to prevent a problematic situation from worsening，the latency experienced with the network during data delivery is of paramount
importance.Many operations incur delays in a single hop of a wireless network，including transmission delay，propagation delay，and reception delay，as well as encoding and decoding delay.The sum of these operations is represented by the constantτ.Furthermore，tolerant end to end delay from event detection to command center awareness is denoted byτT.A primary objective is to minimize the overall average end to end delay overhead through 3G network.
To concretize this formulation，we de?ne Y
where Vki denotes the vulnerability of the point Lki.Although the vulnerability of each road is given， some candidate points may be situated at intersections.In these situations，the point vulnerability is computed as the sum of the vulnerabilities of all road crossing a point，capturing the criticality of such crossroads. （3）Constraints： are formulated to ensure coverage is achieved.In total，four sets of constraints are considered，including a budget limit for sensors，connectivity requirements，guarantees of tolerant end to end delayτT.
·Budget limit：the budget limit constrainsthe number of available sensors. Weassume the budget is predefined and doesnot change.Thus，it is not possible to addmore sensors during the optimization procedure，hence we have：
·Tolerant end to end delay：Tolerant end toend delay guarantees that all events aredetected can be delivered to the commandcenter within time no greater thanτT， sothat the response can be initiated toprevent the undesirable outcomes that canlead to loss of life and assets. Because thisend to end delay is the sum of the delaysfrom the points where the event happens tothe access point，and from access point tothe command center coverage mustbemore thantheminimumneededto ensureconnectivity.Since wired networks areorders of magnitude faster， the delayfrom access point to the command centertreated as a fixed constant Pa. Thus， thedelay depends primarily on the delay fromlocation of the event’s occurrence to anaccess point. For this reason，each cluster should be able to reach one or more accesspoint，and the overall delay should be lessthanτT.Assuming the delay betweeneach pairs of sensor nodes isηij，wehave：
In above formulation，although the binaryvariable Yki=0can always make theequation hold，however，when the positionshould be selected，Yki should be“1”.Thanks to the maximization in equationEq.（4），Yki tend to be “1”.
By solving the optimization problem with branch-and-cut which is introduced in Section II in linear time， the position where the sensors should be deployed can be figured out. Deploy sensors according to the guideline of
the algorithm， the weighted coverage can be maximized.
2.2Cell phone assisted routing
In this sub-section， we utilize a VBF like[2]routing scheme for mobile smart phones to add additional band-width to the system.
Nowadays， people operate smart phones to talk or text with each other through 3G networks as they travel through the city； They also obtained access to internet through a 3G or 4G network. Thus， smart phones also possess the ability to form an ad hoc network by changing their configurations for the WIFI. In this mode， smart phones can serve as mobile sensor nodes to aid the monitoring system， by helping to deliver some delay tolerant information. Here， we assume that an advertising campaign has successfully recruited a large number of smart phones users to register for the service. and that existing an ad hoc network which enables them to connect to access points throughout the majority of the city. A flooding based routing scheme for the mobile smart phones is then employed todeliver information from sensor nodesnear events to an access points. Sensor nodes and smart phones know their positions as well as the location of access points. Each packet carries the positions of the sender and the target access points for delivery through thead hoc network according to a forwarding path specified by the routing vector from the sender to each target access point. For example， when a smart phone receives a packet， it computes its position relative to the sender andtarget access point. If the smart phone is close enough to the routing vector（e.g.，less than a predefined distance threshold， denoted asW）， it will continue to forward the packet； otherwise， it simply discards the packet. This way，all the smart phones forwarding packets in the ad hoc network form a “routing pipe”. Smart phones in this pipe are eligible for packet forwarding. Those which are notclose to the routing vector（i.e.， the axis of the pipe） do not forward.
Fig.1 Smart phone routing strategy
Fig. 1 illustrates the concept of a routing pipe. Sensor node S0 is the source， and Ap is the target access point，and the routing vector is determined from their locations.Data packets are forwarded from S0 to Ap. Forwarders along the routing vector form a routing pipe with a pre-controlled radius （i.e.， the distance threshold）. The radius of the routing pipe may be increased to ensure the delivery of critical events.
3.PERFORMANCE EVALUATION
3.1 Simulation Settings
The simulations were developed in CPLEX， which provides an implementation of branch-and-cut to solve the optimization problem. There are 100 candidates position， and the topology of the candidates position is a 10 by 10 grid of horizontal and vertical roads intersecting at right angles. The intersections（nodes） are labeled 1 to 100， from the left upper node to the node in the lower right. The vulnerabilities of each horizontal roads is randomly set to 0 to 1 with probability 0.5.
Furthermore， the are a total of 10 access points throughout the city， which can be accessed by both wireless sensor nodes and smart phones. These access points are randomly located in the cityAfter the location of the access points are determined， the shortest path to each candidate position is known. Thus， it becomes possible to apply static routing to route information within the wireless sensor network. There are also 200 registered smart phones randomly distributed in the city， which can help to deliver information. The end to end delay between each pair of smart phones is set to one second， denoted as Ps and events occur randomly throughout the city every one hour. 3.2 Results and Analysis
（1）Coverage：Fig.2 shows the normalized coverage achieved with different numbers of sensors. Clearly， there is a direct relationship between the number of sensors and the attainable coverage. This agrees with intuition because more sensors can cover more area in the city， ensuring that coverage increases. The figure also reveals that increasing the number of sensors does not achieve a linear improvement in the coverage. This sublinear improvement occurs because the optimization scheme covers the most vulnerable portions of the network with greater redundancy to ensure that the command center is notified of events occurring in critical regions. Less vulnerable roads therefore receive less attention.
Fig.2 Normalized coverage vs. number of sensors
（2）Average end to end delay：Fig.3 shows the impact of the number of deployed sensors on the average end to end delay. The average end to end delay is always under 5 seconds，which is the acceptable delay for the detected information to reach the command center. It may also been seen that increasing the number of sensors deployed decreases the average delay. This increase occurs because additional sensor nodes provide more alternative paths to route detected information to access points. Since routing within the wireless sensor network occurs along the shortest paths， these additional paths lower the average end to end delay.
Fig.3 Average delay vs. number of sensors
4.CONCLUSION AND FUTURE WORK
This paper proposes an algorithm to deploy wireless sensor nodes to monitor a transportation system in order to ensure highly reliable data delivery to a homeland security command center within a city.We formulated sensor deployment as an optimization problem to quickly detect events occurring at the most vulnerable portions of the network.We also demonstrated that an ad hoc network formed with smart phones can be harnessed to deliver information to a command center in order to facilitate response.
Future research will apply our scheme with real GIS data to evaluate its performance and identify additional constraints to make the approach more practical for adoption in real-world applications.
【References】
[1]N.Lownes，Q.Wang，S.Ibrahim，R.Ammar，S.Rajasekaran，and D. Sharma， “A many-to-many game theoretic approachtomeasuring transportation network vulnerability，”Transportation ResearchRecord，vol.2263：1-8，mar，2011.
[2]P.Xie，L.Lao，andJ.-H.Cui，“VBF：vector-based forwarding protocol for underwater sensor networks，”in To appear in Proceedings of IFIP Networking，May，2006.