Cross-layer latency minimization in wireless networks with SINR constraints

ABSTRACT

Recently, there has been substantial interest in the design of cross-layer protocols for wireless networks. These protocols optimize certain performance metric(s) of interest (e.g. latency, energy, rate) by jointly optimizing the performance of multiple layers of the protocol stack. Algorithm designers often use geometric-graph-theoretic models for radio interference to design such cross-layer protocols. In this paper we study the problem of designing cross-layer protocols for multi-hop wireless networks using a more realistic Signal to Interference plus Noise Ratio (SINR) model for radio interference. The following cross-layer latency minimization problem is studied: Given a set V of transceivers, and a set of source-destination pairs, (i) choose power levels for all the transceivers, (ii) choose routes for all connections, and (iii) construct an end-to-end schedule such that the SINR constraints are satisfied at each time step so as to minimize the make-span of the schedule (the time by which all packets have reached their respective destinations). We present a polynomial-time algorithm with provable worst-case performance guarantee for this cross-layer latency minimization problem. As corollaries of the algorithmic technique we show that a number of variants of the cross-layer latency minimization problem can also be approximated efficiently in polynomial time. Our work extends the results of Kumar et al. (Proc. SODA, 2004) and Moscibroda et al. (Proc. MOBIHOC, 2006). Although our algorithm considers multiple layers of the protocol stack, it can naturally be viewed as compositions of tasks specific to each layer --- this allows us to improve the overall performance while preserving the modularity of the layered structure.

REFERENCES

• 1: P. Bjorklund, P. Varbrand, and D. Yuan, A Column Generation Method for Spatial TDMA Scheduling in Ad Hoc Networks, Ad Hoc Networks, vol. 2, Issue 4, pp. 405--418, 2004.
• 2: R. Bhatia, and M. Kodialam, On Power Efficient Communication over Multi--hop Wireless Networks: Joint Routing, Scheduling and Power Control, IEEE INFOCOM, vol. 2, pp. 1457--1466, March 2004.
• 3: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 4: L. Chen, S. Low, M. Chiang, and J. Doyle, Cross-layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks, IEEE INFOCOM , pp. 1--13, April 2006.
• 5: L. Chen, S. Low, M. Chiang, and J. Doyle, Jointly Optimal Congestion Control, Routing, and Scheduling for Wireless Ad Hoc Networks, IEEE INFOCOM April 2006.
• 6: M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures, To appear Proceedings of IEEE, vol. 95, Issue 1, pp. 255--312, January 2007.
• 7: H. Chernoff. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations. Annals of Mathematical Statistics, vol. 23, Number 4, pp. 493--509, 1952.
• 8: R. L. Cruz, and A. V. Santhanam, Optimal Routing, Link Scheduling and Power Control in Multi-hop Wireless Networks, IEEE INFOCOM, pp. 702--711, March 2003.
• 9: T. ElBatt, and A. Ephremides, Joint Scheduling and Power Control for Wireless Ad-hoc Networks, IEEE INFOCOM, vol. 2, pp. 976--985, June 2002.
• 10: P. Gupta, and P. Kumar, The Capacity of Wireless Networks, IEEE Transactions on Information Theory, vol. 46, Issue 2, pp. 388--404, March 2000.
• 11: D. Knuth, The Art of Computer Programming, Vol. 3 -- Sorting and Searching, Addison-Wesley (1973).
• 12: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 13: G. Kulkarni, V. Raghunathan, and M Srivastava, Joint End-to-End Scheduling, Power Control and Rate Control in Multi-hop Wireless Networks, IEEE GLOBECOM, pp. 3357--3362, December 2004.
• 14: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 15: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Unit disk graph approximation, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022634]
• 16: T. Leighton, B. Maggs, and S.Rao, Packet Routing and Job Shop Scheduling in O(Congestion+Dilation) steps, Combinatorica, vol. 14, Issue 2, pp. 167--180, 1994.
• 17: X. Lin, and N. Shroff, Joint Rate Control and Scheduling in Multihop Wireless Networks, 43rd IEEE Conference on Decision and Control, Paradise Island, vol. 2, pp. 1484--1489, December 2004.
• 18: X. Lin, and N. Shroff, The Impact of Imperfect Scheduling on Cross-layer Rate Control in Multihop Wireless Networks, In IEEE INFOCOM, vol. 3, pp. 1804--1814, March 2005.
• 19: X. Lin, N. Shroff, and R. Srikant, A Tutorial on Cross-Layer Optimization in Wireless Networks, IEEE Journal on Selected Areas in Communications on Non-Linear Optimization of Communication Systems, vol. 24, Issue 8, pp. 1452--1463, June 2006.
• 20: T. Moscibroda, R. Wattenhofer and Y. Weber, Protocol Design Beyond Graph-Based Models, 5th Workshop on Hot Topics in Networks (HotNets), November 2006.
• 21: T. Moscibroda, and R. Wattenhofer, The Complexity of Connectivity in Wireless Networks, IEEE INFOCOM , pp. 1--13, April 2006.
• 22: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 23: M. Neely, Optimal Energy and Delay Tradeoffs for Multi-User Wireless Downlinks, IEEE INFOCOM, pp. 1--13, April 2006.
• 24: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 25: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 26: S. Ramanathan, A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.900, April 09-11, 1997
• 27: Subramanian Ramanathan , Errol L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking (TON), v.1 n.2, p.166-177, April 1993 [doi>10.1109/90.222924]
• 28: Aravind Srinivasan , Chung-Piaw Teo, A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria, SIAM Journal on Computing, v.30 n.6, p.2051-2068, 2001 [doi>10.1137/S0097539798335596]
• 29: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 30: L. Xiao, M. Johansson, and S. Boyd. Simultaneous Routing and Resource Allocation via Dual Decomposition. IEEE Transactions on Communications, vol. 52, Issue 7, pp. 1136--1144, July 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Theory

Keywords:
SINR model, cross-layer design, end-to-end scheduling, interference, wireless networks