Cross-layer latency minimization in wireless networks with SINR constraints

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