Report

Optimization of Wireless Multi-hop Networks with Random Access Morteza Mardani, Seung-Jun Kim, and Georgios B. Giannakis ECE Department, University of Minnesota Acknowledgments: NSF grants no. CCF-0830480, 1016605 EECS-0824007, 1002180 June 29, 2011 1 Motivation Random access is a simple MAC with no central coordination Probabilistic model to design utility-optimal MAC [LCC’07] Better efficiency and fairness than the contention graph model Joint design of multi-path routing and random access for wireless multi-hop networks Path selection and traffic splitting Routing can avoid interference prone areas of the network Related work Joint random access and flow control [YG’08], [WK’06] Joint random access, routing and flow control, [SS’09], [CLCD’06] Our goal: Joint optimization of routing, random access and flow control in a distributed way 2 System model Wireless multi-hop network with directed graph : set of incoming links at node , : set of outgoing links at node Node generates the single commodity traffic at rate and forward it through its outgoing link with rate Interference model: simultaneous receptions at the receiver : set of nodes causing interfering to link , : set of links interfered by transmission of node 1 C 7 A 2 3 Example: E 6 4 B 5 8 D 3 Random access control Slotted Aloha with a single shared channel Node randomly decides to transmit w.p. Active node chooses one of its outgoing links w.p. An outgoing link is active w.p. s.t. s.t. The average achievable MAC layer rate over link Link capacity Prob. that the competing nodes are silent MAC layer rate constraint 4 Network and transport layers Flow conservation constraint for queue stability set of incoming links except those emanating from destinations Flow control to adjust the source rate collision statistics at node based on the Node is awarded a utility to deliver the traffic at rate Utility function: an increasing and concave function, e.g., : fairness controlling parameter =1: proportional fairness =2: harmonic-mean fairness 5 Problem statement Seek for the optimal random access parameters routing variables , and the source rates which , the maximize the total network utility satisfy the MAC and net. layer constraints Formulation Flow rates are bounded in practice (P1) is inherently nonconvex due to MAC layer rate constraint 6 Successive convex approximation Theorem [MW’78]: consider the nonconvex problem (P0) convex nonconvex Approximate the nonconvex functions to 1) 2) 3) s.t. : feasible set of kth convex problem : optimal solution of kth convex problem By successively updating the convex problem, the solution converges to a KKT point of (P0) 7 Single condensation method After rearranging routing constraint Based on arithmetic-geometric mean inequality Tight surrogates for routing constraints Optimal solution in previous iteration Approximation elements 8 Convex problem(P2) Logarithmic change of variables Solve (P2) at kth iteration (*) (**) Proposition 1: (P2) is convex provided that β ≥ 1 9 Distributed solution Solve (P2) at the network nodes using only limited message exchange with the local nodes Difficulty: coupling among the routing constraints at different nodes Solution: keep a local copy of the rate of the outgoing links at The outgoing links not connected each node to the destinations Introduce the auxiliary variables Add to (P2) the constraints Regularization term to ensure feasibility of the converged solution of dual method 10 Partial Lagrangian Relax the MAC layer rate constraints and the constraints on the local copies Separable over MAC and higher layers at different nodes Lagrangian associated with MAC layer The price paid for the rate constraint Lagrangian associated with higher layers The dual variable for constraints on local copies The outgoing links connected to the destinations 11 Dual problem Dual function (**) in which is replaced with Dual optimization problem 12 MAC-layer subproblem Optimization problem at node n (P4) Similar problem in [LCC’07] for single-hop networks Persistence probabilities for node n and its outgoing links Remarks Higher the price paid, higher is the channel access Higher prices to less interfering links Message exchange: If (P4) solved at TX(l), only need 13 Higher-layers subproblem The optimization problem at node n (P5) l.h.s of (***) 14 Solution Proposition 2: Denoting , and , the optimum of (P5) for β=1 is a) If Share the total outgoing flow in proportion to and b) If Closed-form solutions Suitable for wireless sensor networks 15 Cont’d If β>1 and a) If satisfies Remarks Flow conservation is enforced by finding numerically A simple root finding method e.g., the bisection method Remarks Lower rates for the links with higher MAC competition Message passing only with neighbors. Node n only needs to receive 16 Dual update Subgradient projection method Dual iterations Simple projection computable in closed-form Proposition 4: Dual method converges to the optimum of (P2) if and . Remarks Local update of the approximation elements A global timer to stop (P3) distributed algorithm 17 Numerical tests Network example: 15 nodes, 52 links dc = di =0.35, ε =1e-3, rmin=1e-5, rmax=10 cl=10 Monotonic increase of the utility Coincidence with the global optimum 80% of trials Existing [YG’07]: prespecified routes Routing avoids interference around the destination Net. Utility 0.32 vs -0.74 18 Concluding summary Cross-layer design of random access, routing and flow control for wireless ad hoc networks Successive convex approximation approach to find a KKT point Distributed algorithms derived based on the dual method Closed-form solutions reducing implementation complexity After few outer iterations the algorithm converges to a point, which often coincides with the global optimum Optimized collision-aware routing enhances the network utility by avoiding the interference prone areas of the network Future work: extension to the multi-commodity flows and the asynchronous implementation Thank You! 19 Key references [LCC’07] J.-W. Lee, M. Chiang, and A. R. Calderbank, “Utility optimal random-access control,” IEEE Trans. Wireless Commun., vol. 6, no. 7, pp. 2741–2751, Jul. 2007. [YG’08] Y. Yu and G. B. Giannakis, “Cross-layer congestion and contention control for wireless ad hoc networks,” IEEE Trans. Wireless Commun., vol. 7, no. 1, pp. 37–42, Jan. 2008. [WK’06] X. Wang and K. Kar, “Cross-layer rate optimization for proportional fairness in multihop wireless networks with random access,” IEEE J. Sel. Areas. Commun., pp. 1548–1559, Aug. 2006. [SS’09] S. Supittayapornpong and P. Saengudomlert, “Joint flow control, routing and medium access control in random access multi-hop wireless networks,” in Proc. of Intl. Conf. on Comm., Dresden, Germany, pp. 1–6, Jun. 2009. [CLCD’06] L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, “Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks,” in Proc. of the INFOCOM Conf., pp. 1–13, Apr. 2006. [MW’78] B. R. Marks, and Gordon P. Wright, “A General Inner Approximation Algorithm for Nonconvex Mathematical Programs”, Operations research, vol. 26, no. 4, Jul.—Aug. 1978. 20