Congestion Control to Reduce Latency in Sensor Networks for Real-Time ApplicationsOutlineSensor Networks for Real-Time SurveillanceSample Surveillance ScenarioStudy focused on design of network congestion controlPerformance Metric: EstimatorBackground on Congestion Control [1] [2]Various User Utility FunctionsPrimal Algorithm and ControllerDual Algorithm and ControllerPrimal-Dual Algorithms and other variantsExamples of Congestion Control AnalysisApplying TCP/IP congestion control to wireless sensor networksProperties of Utility and Pricing FunctionsIncorporating Latency into UtilityIncorporating Latency into Utility (2)Flow Rate vs. Delay and Packet Drop RateHope? Congestion control policies as an optimization solver with a black boxDesign Guidelines for Packet Drop PolicyDesign Guidelines for Congestion Feedback PolicyDesign Guidelines for Rate Adaptation PolicyFuture WorkExtra SlidesSlide 24What pursuers really seeSensor net increases visibility5/4/2006 EE228A – Communication Networks 1Congestion Control to Reduce Latency in Sensor Networks for Real-Time ApplicationsPresented byPhoebus ChenEE228A – Communication Networks 25/4/2006OutlineMotivation: Sensor Network SurveillanceBackground: Congestion ControlDifficulties with Addressing LatencyDesign Guidelines for Latency Congestion Control PoliciesEE228A – Communication Networks 35/4/2006Sensor Networks for Real-Time SurveillanceEvent Detectionbursty trafficvarying importance of data for estimationcan operate with incomplete dataLow Latencyroutingselective packet deliverycongestion controlEE228A – Communication Networks 45/4/2006Sample Surveillance ScenarioMultiple targets on linear trajectoriesOne centralized estimator per cellUltimate scenario:Pursuit-Evasion Games with mobile robotsEE228A – Communication Networks 55/4/2006Study focused on design of network congestion controlWireless, multi-hop channelFixed routingMultiple sources, one sinkEstimationSensing and Data AggregationSensing and Data Aggregation(sink)(source)(source)(network)EE228A – Communication Networks 65/4/2006Performance Metric: EstimatorLinear System Dynamicsdriven by a white noise processSimple linear measurement modelEstimation via Kalman FilterCheck performance under different traffic patternsEE228A – Communication Networks 75/4/2006Background on Congestion Control [1] [2]Flow modelNetwork Optimization Problem[1] R. Srikant, The Mathematics of Internet Congestion Control, ser. Systems & Control: Foundations & Applications. Birkhauser Boston, 2004.[2] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability,” Journal of the Operational Research Society, vol. 49, no. 3, pp. 237–252, March 1998.EE228A – Communication Networks 85/4/2006Various User Utility FunctionsWeighted Proportional FairnessMinimum Potential DelayMax-Min FairGeneral Utility Function [3]For max-min fairness[3] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–567, Oct 2000.EE228A – Communication Networks 95/4/2006Primal Algorithm and ControllerPrimal Algorithm (Lyapunov Function)Flow Controllerkr(xr) > 0 is a non-decreasing, continuous functionAssume prices react instantaneouslyEE228A – Communication Networks 105/4/2006Dual Algorithm and ControllerDual AlgorithmPrice Controllerhl(pl) > 0 is a non-decreasing continuous functionAssume flows react instantaneouslyEE228A – Communication Networks 115/4/2006Primal-Dual Algorithms and other variantsCan combine primal and dual controllers, and prove via a Lyapunov function that the algorithm is globally, asymptotically stable Other variants existCalculate prices using a weighted average of the flow at a link over timeSetting prices based on fullness of a virtual queue (Adaptive Virtual Queue, or AVQ)Prices are marking probabilities of packetsEE228A – Communication Networks 125/4/2006Examples of Congestion Control AnalysisConvergence RateLinearize about equilibriumLook at smallest eigenvalue of dynamics matrixTime-delay Stability AnalysisLinearize about equilibriumLook at transfer function in the frequency domain and apply Nyquist stability criterionStochastic StabilityLinearize about equilibriumLook at Brownian motion perturbations, check induced covariance of fluctuationsEE228A – Communication Networks 135/4/2006Applying TCP/IP congestion control to wireless sensor networksDoes not account for wireless networks with: interference from neighboring pathsphysical channel errorsHard to address both, first pass is to treat as constant error disturbance like [4] [5][4] M. Chen, A. Abate, and S. Sastry, “New congestion control schemes overwireless networks: stability analysis,” in Proceedings of the 16th IFACWorld Congress, 2005.[5] A. Abate, M. Chen, and S. Sastry, “New congestion control schemesover wireless networks: delay sensitivity analysis and simulations,” inProceedings of the 16th IFAC World Congress, 2005.EE228A – Communication Networks 145/4/2006Properties of Utility and Pricing FunctionsAssumptions on Ur(xr), ris a non-decreasing, continuously differentiable, strictly concave functionUr(xr) - as xr 0Assumptions on prices pl() lis a non-decreasing, continuous function such thatEE228A – Communication Networks 155/4/2006Incorporating Latency into UtilityAssign a utility to each packetSigmoidal function for differentiabilityEE228A – Communication Networks 165/4/2006Incorporating Latency into Utility (2)Integrate delay utility of each packet with flownon-decreasing, continuously differentiable, strictly concave (assuming additional flow only come with greater delay)May not be able to meet constraint Ur(xr) - as xr 0EE228A – Communication Networks 175/4/2006Flow Rate vs. Delay and Packet Drop RateDelay is a function ofqueuing delayCongestionErrors from wireless channelCSMA contentiontransmission delay (number of hops)Do not have a good/simple model of CSMA contention at the MAC layerWithout knowing we have a hard time knowing for our optimization problemCongestion at merge points In routing treeEE228A – Communication Networks 185/4/2006Hope? Congestion control policies as
View Full Document
Unlocking...