Subscribe Now Subscribe Today
Abstract
Fulltext PDF
References

Research Article
The Research of Traffic Flow Assignment Model based on the Network Calculus of Computer Network

Yali Peng, Wei Fan, Jiayao Liu and Fan Zhang
 
ABSTRACT
The existing dynamic traffic assignment researches mostly based on ideal hypothesis conditions which can analyze the affection of all kinds of traffic parameters on traffic flow and find out characteristics of various types of traffic distribution, but there is rarely have accurate calculation of flow distribution model. The study will first apply the network equilibrium theory into dynamic traffic flow assignment. Using Leaky Bucket Controller and Network Calculus, complicated traffic elements will incorporate into unified mathematical model called T-S Constrained Model, we can deduce flow assignment rate which is in a delay-limited constraints. The simulation results manifest that the model can not only solves congestion, but also reduce average delay of every path, it can extremely improve the traffic capacity of road network. The accurate assignment solutions will have significant impact on traffic engineering implementation.
Services
E-mail This Article
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Yali Peng, Wei Fan, Jiayao Liu and Fan Zhang, 2012. The Research of Traffic Flow Assignment Model based on the Network Calculus of Computer Network. Information Technology Journal, 11: 307-312.

DOI: 10.3923/itj.2012.307.312

URL: http://scialert.net/abstract/?doi=itj.2012.307.312
 
Received: October 18, 2011; Accepted: November 15, 2011; Published: January 18, 2012

INTRODUCTION

Urban Dynamic Traffic Assignment model and algorithm according to the dynamic traffic demanding which are the core of the intelligent transportation theory. Because of the complexity of the road traffic system and the dynamic assignment of real-time property, they make traffic assignment a series of problems. In 1956, Beckman puts forward the calculation traffic equilibrium state of integral transform which form the important foundation of urban traffic balance theory and then appear a series of related research, but most are static traffic distribution model (Lian and Gao, 2005). In dynamic traffic assignment, Barthelemy M based on the number of referral traffic in order to determine the distribution network, discussed the characteristics of scale-free network flow distribution and the scaling relation between node degree and flow (Barthelemy, 2004). Dobson et al. (2003) was put forward Cascade model which was based on probability flow and has analyzed the Cascade mode which effect on failure scale which existed the critical point. Then according to the efficiency of the edge the changes of thought during the process of node failure also the characteristics of dynamic distribution flow in complex network (Crucitti et al., 2004). Lee et al. (2011) analyzed the traffic spread rules in complex network and the congested influence which was caused by network topological structure and proposed the control strategy about how to eliminate the traffic congestion.

Overall, at present the existing dynamic traffic assignment researches mostly based on ideal hypothesis conditions which can analyze the effect of all kinds of traffic parameters on traffic flow and find out characteristics of various types of traffic distribution, but there is rarely have accurate calculation of flow distribution model. But in the actual traffic control engineering, the traffic flow assignment needs a precise quantitative index so as to offer specific flow rate or signal lights control. Therefore, it is very beneficial for us to study precise model of dynamic traffic flow assignment model to realize the traffic control engineering.

The study will first apply the network equilibrium theory (Chen et al., 2011) into dynamic traffic flow assignment which Using Leaky Bucket Controller and Network Calculus. The traffic flow rate distribution and path delay is exchanged to be a series of mathematical operations, finally use simple greedy algorithm to balance traffic delay and get traffic assignment. The model aims at a short time dynamic analyzing, propose a traffic flow calculation model called T-S Constrained Model to solve congestion. The simulation results show that the model effectively solves the heavy traffic, has a better convergence property in balancing the traffic flow and can advance traffic capacity of road network.

TRAFFIC FLOW ASSIGNMENT PROBLEM

Description of the simulated problem: The dynamic traffic flow control system within a city’s road network is built to ensure an efficient traffic flow, because in the event that the traffic is not managed properly, congestion could occur which affects the traffic seriously. This article focuses on how to dynamically manage a heavily congested road way, to dissipate the traffic within the congested region in a short period of time. At the same time to solve the current state of congestion and balance traffic delay and assure the assigned cars can reach in the core area in an effective time.

The transmission process of road traffic network is similar with computer network’s. In recent years, the theory of complex networks for urban transportation research provides a new perspective. Domestic and overseas scholars using complex network theory achieve many Research results in the traffic network dynamics behavior analysis, traffic network cascade failure, traffic jams communication and transportation network evolution modeling, etc. But the main achievements are analysis of urban traffic network structure on the network traffic, expenses and the influence of the obstruction and there is rarely have accurate calculation model which can utilize to practice traffic engineering.

Using wireless network multimedia application transmission theory and combining with traffic network transmission characteristics, we apply the network equilibrium theory into dynamic traffic flow assignment. Using network calculus we analyze the route service ability of roadways, incorporate the complexity of the road elements into unified mathematical model called D-R Constrained Model and deduce the path of assigned path in a bounded delay. It will get to meet the max allowable rate in effective delay-limited constraints and provide delay-rate constraint dynamic traffic flow assignment model so as to offer accurate mathematical flow assignment solutions.

THE PROBLEM THEORY

Leaky bucket controller: Network nodes' traffic control of communication flows makes the network node cache space does not overflow and the transmission of data is guaranteed. In Fig. 1, node traffic control as the leaky bucket, a bucket which the capacity is σ, discharge rate is ρ, we must control the traffic flows so that communication storage x(t) won't be overflow from the bucket in any time. If the reaching of the traffic won't cause an overflow, called traffic R (t) satisfy the control of leaky bucket which the parameters is (σ, ρ).

Theorem 1: If the communication stream R(t) is controlled by the leaky bucket which parameter is (σ, ρ), then R(t) will constraint by the reach curve α(t) = σ+ρt.

Network calculus is a set of theory of analyzing packet switching network queuing system. Different from traditional queuing theory, Network calculus theory mainly studies packet switching network performance to secure border rather than stable state of the average performance.

Fig. 1: Leaky bucket controller

The central theme of the theory is to utilize minimum plus algebra and maximum plus algebra to transform a complex, non-linear network system into a linear system which is easier to analyze. This theory has been widely utilized by various network performance benchmark tools and resource distribution solutions, as well as many others. To ensure that network calculation is used primarily to analyze the guaranteed availability of services under the worst case scenario. When ensuring service guarantee which are all of the data flow from the source node group to destination node(host, routers etc.) forward can satisfy the demanding performance index such as bandwidth, time delay and traffic, etc. Reaching curve and service curve is to determine core model which is in the network calculation theory and to describe streams of data flow characteristics and server service capacity characteristics. Based on this, ensuring network calculation may analyze the delay in the network group, the output of the flow characteristics server and network elements of the buffer size and performance indicators. Network data delay definition: Given a stream which will be restrained by arrival curve when enter the system, when through the system ,the system provides service curve β(t) so that the communication stream delay d(t) at any time satisfies formula (1),which h(α, β) also known as standard deviation between α and β curves:

PATH ANALYSIS OF SERVICE CAPABILITIES

We think congestion happens when the sections share is larger than a certain value and we will take the real-time dynamic route guidance strategy. In order to make the traffic flow of current congestion section S meet the Leaky Bucket Controller which parameter is (σ, ρ),then R (t)<σ-x (t0)+ρt.σ. is the vehicle's maximum capacity of the sections, x (t0)is the number of vehicles in initial time during the time t. ρ is the rate of the section which the vehicle out of. In this project, the sections shares in each period are obtained by sensor. In order to simplify the formula, we reduce the formula σ-x (t0) to the capacity of vehicle φ (t0)in current section that means the arrived cars meet the curve r (t)<φ (t0)+ρt and we call:

(1)

Fig. 2: Traffic flow distribution

Current road S divides traffic stream R(t) into m of small streams R1(t), R2(t),..., Rm(t) through route guidance, show in Fig. 2.

Every traffic flow’s speed is ρi, there are:

(2)

For any path i, assuming the path has n sections, each section provides some service capabilities for traffic flow. Shown in Fig. 4, the service curves which are provided by every road section are: . According to the network calculus theorem, the series service curve in path i which is provided by the n middle sections is

For any passage of the section, we can assumed that section provides rate-delay service curve for traffic flow no matter use which signal control algorithm and the curve can be used as a service guarantees for traffic flow (Mao et al., 2006). Thus, the service curve formula (3) which is provided by each sub-section is:

(3)

Among them, Vij is the designed speed of road section, Vij the time which the vehicle delayed in this road.

The series service curve βi (t) of path i can be calculated according to the characteristics of rate-delay function. Show in Formula (4):

(4)

The delay of vehicle which passes every road section j in path i are divided into two part: the one is the vehicle's travel time: Ri, the other one is the vehicle's waiting time: Wi. Every path i runs n sections, the time of vehicles in each section is:

Lij is the length of section j, Vij is the designed speed of current section. So the time of vehicles in path i is:

(5)

For a stable queuing system, the upper bound of queuing delay is the maximum heavy interval (Chang, 1994; Si et al., 2009). So, the queuing time delay of data stream which constrained by the curve can be represented as: α (t) = φ (t0)+ρt

So, the mutable time delay of path i meet the formula:

(6)

Overview the formula (5) and (6), we can get the time delay upper bound of path I:

(7)

DELAY-RATE CONSTRAINED DTFA MODEL

We take the dynamic real-time assignment model in congested section. If the congestion occurs when you in the way of the peak destination, we take the D-R Constrained Model for the congested section. To make sure every divided section has the same traffic capacity and guarantee the through efficiency of each section, the key to the induced algorithm is to balance the time delay of each traffic flow in divided section and assuming the longest time delay Δ of each divided traffic flow in a reasonable time, then:

(8)

So we can get:

(9)

Among them, ρi is the constrained average speed of arrival stream and it is the maximum allowable flow rate of the path at the same time. We can see from the formula that when the service rate of the path is larger, the speed of the data which satisfy the required delay is greater.

So, we can analyze the total data stream in current congested section:

(10)

The constrained speed of total data stream which get into the current congested section can not exceed a certain threshold value, otherwise that will result in a back of vehicles on the road, adding the path time delay exceeds the limited value Δ. That is, using the red light to control the traffic w in order to control the speed of traffic in current congested section.

To ensure the path induced diversion keep the same traffic capacity, to meet the requirements of the delay in premise, we should reduce the difference between each path as much as possible and we attribute the path capacity allocation problem to the following planed optimization problem:

s.t.:

Because of the above problem is NP-hard problem, we propose greedy algorithm to solve it. Described as follows in detail:

Input: Section length L, designed speed of section V, the upper delay of path Δ, the signal cycle C, the split λ, the acquisition probability K
Output: The entry speed of each path after the traffic distribution ρi
Step 1: Calculate the upper bound of constrained speed ρi in each section:


Step 2: In order to stream out the congestion vehicles and maintain the vehicles forward by the designed speed in a cycle time, then L (1-K) +VC<ρC, then calculate the discharge rate ρ
Step 3: Set the constrained speed of each path proportionally according to the upper limit value:


Step 4: For the allocation plan (ρ1, ρ2,…, ρm), we calculate the time delay upper bound of each path according to the formula 7:


Step 5: For these two paths which have the maximum and minimum time delay upper bound, adjusting each constrained speed ρi, reduce , increase , but can not exceed each limited value so that the delay inequality:

can be reduced between paths

Step 6: Repeat the step (5) until the:

can not be reduced

THE SIMULATION EXPERIMENT

We take the traffic network which was forward with 21 sections to simulate, the experimental data is from the reference (Wang et al., 2010), setting up the congested roads in all directions of the heart land, because the multiple loops of the road network, we selected 3, 5, 8 diffluent path and three different congested situations to have a test, compare the before and after adjustment delay changes. From the simulation results, we can see the average time delay was generally lower after assignment, in the aspect of balancing traffic flow and resolve congestion, we enhance the capacity of road, shown in Fig. 3.

Fig. 3: Comparison of average delay in 3 road situation of different path

The more path involve in the assignment, the better the convergence of the algorithm is and the lower the average time delay of diversion is and the time delay will converge towards the balanced direction, shown in Fig. 4. But for multiple diffluent paths, if the driving range differs so much, the time delay of each road is difficult to converge to a specified value, it will stay in a value.

When we take 8 diffluent paths, the different congested status values before and after adjustment, we can see in Fig. 5 severe congestion delays can converge to a better delay value which can improve that it can disperse congestion, but that will also sacrifice some sections’ delay value in mild congestion, in order to balance the traffic flow, we should to adjust different sections to achieve better level in whole.

Fig. 4: The value comparison of 3/5/8 diffluent paths after adjusting

Fig. 5: The comparison of 8 paths’ congested situation

CONCLUSION

This project aimed at dynamic traffic flow assignment in congestion section of traffic network, in a period of time to complete the assignment of high-load flow in congested section and balance the delay in each diffluent path so that the vehicles which are participate in shunting can reach in central area in a limited time. It’s the first time to come up with applying network equilibrium theory in wireless network, combined with the transmission characteristics of the transport network, applying the network equilibrium theory into dynamic traffic flow assignment. Using the network calculus theory to analyze the section service capacity of the road, combining the complex road elements into unified mathematical model, deducing the delay upper value of diversion path and getting the biggest flow rate which is in a delay-limited constraints, come up with Delay-Rate Constraint dynamic traffic flow assignment model, giving the accurate flow distribution program. Simulation test is in different number of diversion paths, different delay situation of different road network, the average time delay was generally lower after adjusting , congestion delays of each path can converge to a better delay value in the condition of our model, the congested section can reach a better shutting effect when there are many diversion paths and the each path can reach in central area in a limited time.

ACKNOWLEDGMENT

This study was supported by Projects of International Cooperation and Exchanges NSFC No. 2010DFB90460, Science and Technology Planning Project of Jiangxi Province No. 20111BDH80030.

REFERENCES
Barthelemy, M., 2004. Betweenness centrality in large complex networks. Eur. Phys. J. B Condensed Matter Complex Syst., 38: 163-168.
CrossRef  |  

Chang, C.S., 1994. Stability, queue length and delay of deterministic and stochastic queuing networks. IEEE Trans. Automatic Control, 39: 913-931.
CrossRef  |  

Chen, X., X.D. Xiang, L. Zhang and T. Xu, 2011. Network calculus and ins application in packet switching networks. J. Beijing Inform. Technol. Univ. (Natl. Sci.).

Crucitti, P., V. Latora and M. Marchiori, 2004. Model for cascading failures in complex networks. Phys. Rev. E, Vol. 69. 10.1103/PhysRevE.69.045104

Dobson, I., B.A. Carreras and D.E. Newman, 2003. A probabilistic loading-dependent model of cascading failure and possible implications for blackouts. Proceedings of the 35th Hawaii International Conference on System Sciences, January 6-9, 2003, Hawaii, pp: 1-10.

Lee, S.B., J.J. Wu, Z.Y. Gao, Y. Lin and B.B. Fu, 2011. Based on the traffic congestion of complex network and the analysis of transmission dynamics. J. Acta Physica Sinica.

Lian, A.P. and Z.Y. Gao, 2005. Research on combined dynamic traffic assignment and signal control. Acta Automatica Sin., 31: 727-736.
Direct Link  |  

Mao, S., S.S. Panwar and Y.T. Hou, 2006. On minimizing end-to-end delay with optimal traffic partitioning. IEEE Trans. Vehicular Technol., 55: 681-690.
CrossRef  |  

Si, B., H. Zhang and Z. Gao, 2009. Improved Dia's algorithm for logit-based stochastic traffic network assignment problem. China J. Hignway Trans.

Wang, T., S. Gao, L. Zhang, Y. Wu and X. He et al., 2010. Overlap domain decomposition method for bioluminescence tomography (BLT). Int. J. Numerical Methods Biomed. Eng., 26: 511-523.
CrossRef  |  Direct Link  |  

©  2014 Science Alert. All Rights Reserved
Fulltext PDF References Abstract