TY - CONF
T1 - Cross-layer latency minimization in wireless networks with SINR constraints
T2 - Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing
Y1 - 2007
A1 - Chafekar,Deepti
A1 - Kumar,V. S. Anil
A1 - Marathe,Madhav V.
A1 - Parthasarathy,Srinivasan
A1 - Srinivasan, Aravind
KW - cross-layer design
KW - end-to-end scheduling
KW - Interference
KW - SINR model
KW - Wireless networks
AB - 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.
JA - Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing
T3 - MobiHoc '07
PB - ACM
CY - New York, NY, USA
SN - 978-1-59593-684-4
UR - http://doi.acm.org/10.1145/1288107.1288123
M3 - 10.1145/1288107.1288123
ER -