@conference {17582,
	title = {Cross-layer latency minimization in wireless networks with SINR constraints},
	booktitle = {Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing},
	series = {MobiHoc {\textquoteright}07},
	year = {2007},
	month = {2007///},
	pages = {110 - 119},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	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.},
	keywords = {cross-layer design, end-to-end scheduling, Interference, SINR model, Wireless networks},
	isbn = {978-1-59593-684-4},
	doi = {10.1145/1288107.1288123},
	url = {http://doi.acm.org/10.1145/1288107.1288123},
	author = {Chafekar,Deepti and Kumar,V. S. Anil and Marathe,Madhav V. and Parthasarathy,Srinivasan and Srinivasan, Aravind}
}
@conference {17550,
	title = {Algorithmic aspects of capacity in wireless networks},
	booktitle = {Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems},
	series = {SIGMETRICS {\textquoteright}05},
	year = {2005},
	month = {2005///},
	pages = {133 - 144},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.},
	keywords = {capacity modeling, end-to-end scheduling, Linear programming, Wireless networks},
	isbn = {1-59593-022-1},
	doi = {10.1145/1064212.1064228},
	url = {http://doi.acm.org/10.1145/1064212.1064228},
	author = {Kumar,V. S. Anil and Marathe,Madhav V. and Parthasarathy,Srinivasan and Srinivasan, Aravind}
}
