1328 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.22,NO.8,AUGUST 2011 Algorithm 2 Using progressive filling method to achieve overall allocated time fraction of each user j that commu- max-min fairness nicates with all APs cannot be more than 1.Constraint(16) 1:t=0 shows that the time fraction is between 0 and 1. 2:while t<T do 3: For each snapshot t,sort the users according to Algorithm 3 Calculate optimized allocations iteratively oecreasing order of Denote there while maximizing the throughput of the saturated users ordered users as 1,2,...j,..n. 1:U={1,2,J}-S. 4: Initialize pi;(t)=0 for all i,j pairs,initialize the 2:while U'≠0do saturated user set S=0. 3: Conduct the linear programming LP(U)to figure 5: J=1 out the optimal parameters for p(t). 6: while J≤ndo 4 Update the following parameters 公 Call Algorithm 3 to progressively allocate addi- i∈A,j∈Upi,(t)=pi(t)+p,(t) tional fractional resource pii(t)to each nonsat- urated user j(j<J),update the saturated user vjeU, bs(d)dt=b,(t)dt+∑r)p(因△t 0 Jo set S. iEA 8: J=J+1 for each user j do 9: end while ⊙ if∑sAP=1 or ViE A,∑eU Pij=1then 10: Calculate the integral solution by using rounding Add j into S. algorithm. 8 end if 11: Updateb(t)dt and Ti(t)for each user j. end for 10 U=U-S 12: t=t+△t 13:end while 11:end while Algorithm 3 is the optimized allocation algorithm for each In each iteration of Algorithm 3,we attempt to determine progressive filling round.During each round we utilize the the optimal allocations for the users which are still non- linear program LP(U)to iteratively determine the saturated saturated,and check current users if they are already users while trying to maximize the throughput of these saturated according to the definition.Then we remove the saturated users,as shown in the following formulation: saturated users from the target set U.In this way we achieve the"max-min fair"allocation in an approximate approach by maximize y, (11) using the progressive filling method. In the supplementary material,which can be found on subject to the Computer Society Digital Library at http://doi. ieeecomputersociety.org/10.1109/TPDS.2011.17,we further j∈U”5= t)dt+∑eAr因)·，)·△t introduce the group-based methodology to reduce associa- ·(T(t)+△t) tion control complexity,and discuss the practical utilization 5eU5≥， (12) in realistic settings. 5∈U'≤ bs(t)dt (13) e·(T(t)+△t) 5 PERFORMANCE EVALUATIONS ∀i∈A >(p(t)+)≤1， (14) We have implemented a simulator to simulate the Drive- U thru Internet scenario.In order to simulate the realistic 0∈U ∑p)+P()≤1， 15) settings about the road topologies and the vehicles'moving i traces,we use the realistic traffic generator Simulation of i∈A,j∈U'0≤p(t)+p(t)≤1 16 Urban MObility (SUMO)[18]to construct the large road network and generate vehicle traffic.In the simulation,we In the linear programming LP(U),U'denotes the non- build the road topologies based on the road networks in a saturated user set,we,respectively,use p(t)and pij(t)to rectangular region(3,500 m x 3,000 m)in Washington DC., denote the new allocated time fraction and the already which is imported from the TIGER database [19].We build allocated time fraction.The objective is to maximize y, the roads with lanes,and the number of lanes of each road which is the minimum value of yj for each user j inside the ranges from 1 to 6.Hence,the major roads take the majority nonsaturated user set U'.Constraint(12)depicts that y is the of traffic flow as there are more lanes on the major roads than minimum value of yj.Constraint(13)depicts that y;should the other roads.Traffic lights are deployed at the cross of not be allocated more than the value of roads.We generate vehicle traffics over the road networks according to the parameters illustrated in Table 1,where bs(t)dt accel and decel,respectively,denote the acceleration and 四·(T(t)+△t) deceleration ability of vehicles,sigma denotes the driver imperfection (between 0 and 1),length and speed,respec- since we are considering the progressive filling approach tively,denote the vehicle length and average speed,density for users in 1,2,..../for each round.Constraint (14)means denotes the average density of vehicles on the roads.The that the overall allocated time fraction of each AP i to all average speed speed=15 m/s and we observe that the users cannot be more than 1.Constraint(15)states that the 95 percent confidence interval for vehicles'speed isAlgorithm 3 is the optimized allocation algorithm for each progressive filling round. During each round we utilize the linear program LP(U0 ) to iteratively determine the saturated users while trying to maximize the throughput of these saturated users, as shown in the following formulation: maximize y; ð11Þ subject to 8j 2 U0 yj ¼ R t 0 bjðtÞdt þ P i2A ri;jðtÞ  p0 i;jðtÞ  t wj  ðTjðtÞ þ tÞ 8j 2 U0 yj  y; ð12Þ 8j 2 U0 yj  R t 0 bJ ðtÞdt wj  ðTJ ðtÞ þ tÞ ; ð13Þ 8i 2 A X j2U ðpi;jðtÞ þ p0 i;jðtÞÞ  1; ð14Þ 8j 2 U0 X i2A ðpi;jðtÞ þ p0 i;jðtÞÞ  1; ð15Þ 8i 2 A; j 2 U0 0  pi;jðtÞ þ p0 i;jðtÞ  1: ð16Þ In the linear programming LP(U0 ), U0 denotes the non￾saturated user set, we, respectively, use p0 i;jðtÞ and pi;jðtÞ to denote the new allocated time fraction and the already allocated time fraction. The objective is to maximize y, which is the minimum value of yj for each user j inside the nonsaturated user set U0 . Constraint (12) depicts that y is the minimum value of yj. Constraint (13) depicts that yj should not be allocated more than the value of R t 0 bJ ðtÞdt wj  ðTJ ðtÞ þ tÞ ; since we are considering the progressive filling approach for users in 1; 2; ... ; J for each round. Constraint (14) means that the overall allocated time fraction of each AP i to all users cannot be more than 1. Constraint (15) states that the overall allocated time fraction of each user j that commu￾nicates with all APs cannot be more than 1. Constraint (16) shows that the time fraction is between 0 and 1. In each iteration of Algorithm 3, we attempt to determine the optimal allocations for the users which are still non￾saturated, and check current users if they are already saturated according to the definition. Then we remove the saturated users from the target set U0 . In this way we achieve the “max-min fair” allocation in an approximate approach by using the progressive filling method. In the supplementary material, which can be found on the Computer Society Digital Library at http://doi. ieeecomputersociety.org/10.1109/TPDS.2011.17, we further introduce the group-based methodology to reduce associa￾tion control complexity, and discuss the practical utilization in realistic settings. 5 PERFORMANCE EVALUATIONS We have implemented a simulator to simulate the Drive￾thru Internet scenario. In order to simulate the realistic settings about the road topologies and the vehicles’ moving traces, we use the realistic traffic generator Simulation of Urban MObility (SUMO) [18] to construct the large road network and generate vehicle traffic. In the simulation, we build the road topologies based on the road networks in a rectangular region (3,500 m  3,000 m) in Washington DC., which is imported from the TIGER database [19]. We build the roads with lanes, and the number of lanes of each road ranges from 1 to 6. Hence, the major roads take the majority of traffic flow as there are more lanes on the major roads than the other roads. Traffic lights are deployed at the cross of roads. We generate vehicle traffics over the road networks according to the parameters illustrated in Table 1, where accel and decel, respectively, denote the acceleration and deceleration ability of vehicles, sigma denotes the driver imperfection (between 0 and 1), length and speed, respec￾tively, denote the vehicle length and average speed, density denotes the average density of vehicles on the roads. The average speed speed ¼ 15 m=s and we observe that the 95 percent confidence interval for vehicles’ speed is 1328 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 22, NO. 8, AUGUST 2011