BZPEERReading, trust and collaboration for research
Menu

Discover

SearchFind papers, people, topics and opportunities from one place.GraphOpen maps around papers, topics and saved views.

Workspaces

HomeOpen the ranked research feed.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Source author record

Pradipta Mitra

Pradipta Mitra appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Networking and Internet ArchitectureData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingComputer Science and Game Theory

Catalog footprint

What is connected

11works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2014arXiv

Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model

We study the wireless scheduling problem in the SINR model. More specifically, given a set of $n$ links, each a sender-receiver pair, we wish to partition (or \emph{schedule}) the links into the minimum number of slots, each satisfying interference constraints allowing simultaneous transmission. In the basic problem, all senders transmit with the same uniform power. We give a distributed $O(\log n)$-approximation algorithm for the scheduling problem, matching the best ratio known for centralized algorithms. It holds in arbitrary metric space and for every length-monotone and sublinear power assignment. It is based on an algorithm of Kesselheim and Vöcking, whose analysis we improve by a logarithmic factor. We show that every distributed algorithm uses $Ω(\log n)$ slots to schedule certain instances that require only two slots, which implies that the best possible absolute performance guarantee is logarithmic.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Power of Non-Uniform Wireless Power

We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power --- when the power used by a transmitter only depends on the distance to the receiver --- as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves --- due to existing lower bounds --- capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Fully Distributed Algorithm for Throughput Performance in Wireless Networks

We study link scheduling in wireless networks under stochastic arrival processes of packets, and give an algorithm that achieves stability in the physical (SINR) interference model. The efficiency of such an algorithm is the fraction of the maximum feasible traffic that the algorithm can handle without queues growing indefinitely. Our algorithm achieves two important goals: (i) efficiency is independent of the size of the network, and (ii) the algorithm is fully distributed, i.e., individual nodes need no information about the overall network topology, not even local information.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributed Connectivity of Wireless Networks

We consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. Combinatorially, this means a) finding a set of links that form a strongly connected spanning graph on a set of $n$ points in the plane, and b) scheduling it efficiently in the SINR model of interference. The nodes must converge on a solution in a distributed manner, having no means of communication beyond the sole wireless channel. We give distributed connectivity algorithms that run in time $O(poly(\log Δ, \log n))$, where $Δ$ is the ratio between the longest and shortest distances among nodes. Given that algorithm without prior knowledge of the instance are essentially limited to using uniform power, this is close to best possible. Our primary aim, however, is to find efficient structures, measured in the number of slots used in the final schedule of the links. Our main result is algorithms that match the efficiency of centralized solutions. Specifically, the networks can be scheduled in $O(\log n)$ slots using (arbitrary) power control, and in $O(\log n (\log\log Δ+ \log n))$ slots using a simple oblivious power scheme. Additionally, the networks have the desirable properties that the latency of a converge-cast and of any node-to-node communication is optimal $O(\log n)$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Towards Tight Bounds for Local Broadcasting

We consider the local broadcasting problem in the SINR model, which is a basic primitive for gathering initial information among $n$ wireless nodes. Assuming that nodes can measure received power, we achieve an essentially optimal constant approximate algorithm (with a $\log^2 n$ additive term). This improves upon the previous best $O(\log n)$-approximate algorithm. Without power measurement, our algorithm achieves $O(\log n)$-approximation, matching the previous best result, but with a simpler approach that works under harsher conditions, such as arbitrary node failures. We give complementary lower bounds under reasonable assumptions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Wireless Capacity and Admission Control in Cognitive Radio

We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Wireless Network Stability in the SINR Model

We study the stability of wireless networks under stochastic arrival processes of packets, and design efficient, distributed algorithms that achieve stability in the SINR (Signal to Interference and Noise Ratio) interference model. Specifically, we make the following contributions. We give a distributed algorithm that achieves $Ω(\frac{1}{\log^2 n})$-efficiency on all networks (where $n$ is the number of links in the network), for all length monotone, sub-linear power assignments. For the power control version of the problem, we give a distributed algorithm with $Ω(\frac{1}{\log n(\log n + \log \log Δ)})$-efficiency (where $Δ$ is the length diversity of the link set).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Wireless Capacity With Arbitrary Gain Matrix

Given a set of wireless links, a fundamental problem is to find the largest subset that can transmit simultaneously, within the SINR model of interference. Significant progress on this problem has been made in recent years. In this note, we study the problem in the setting where we are given a fixed set of arbitrary powers each sender must use, and an arbitrary gain matrix defining how signals fade. This variation of the problem appears immune to most algorithmic approaches studied in the literature. Indeed it is very hard to approximate since it generalizes the max independent set problem. Here, we propose a simple semi-definite programming approach to the problem that yields constant factor approximation, if the optimal solution is strictly larger than half of the input size.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Wireless Connectivity and Capacity

Given $n$ wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in $O(\log n)$ slots, improving on the previous best bound of $O(\log^2 n)$ due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of $Ω(1/\log n)$ on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of $Ω(n)$ slots for connectivity. This rules out a recent claim of a $O(\log n)$ bound using oblivious power. On the other hand, using our result we show that $O(\min(\log Δ, \log n \cdot (\log n + \log \log Δ)))$ slots suffice, where $Δ$ is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with $O(\log n)$ latency is possible, improving upon the previous best known latency of $O(\log^3 n)$. We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and $k$-edge connected structures.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On a game theoretic approach to capacity maximization in wireless networks

We consider the capacity problem (or, the single slot scheduling problem) in wireless networks. Our goal is to maximize the number of successful connections in arbitrary wireless networks where a transmission is successful only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. We study a game theoretic approach towards capacity maximization introduced by Andrews and Dinitz (INFOCOM 2009) and Dinitz (INFOCOM 2010). We prove vastly improved bounds for the game theoretic algorithm. In doing so, we achieve the first distributed constant factor approximation algorithm for capacity maximization for the uniform power assignment. When compared to the optimum where links may use an arbitrary power assignment, we prove a $O(\log Δ)$ approximation, where $Δ$ is the ratio between the largest and the smallest link in the network. This is an exponential improvement of the approximation factor compared to existing results for distributed algorithms. All our results work for links located in any metric space. In addition, we provide simulation studies clarifying the picture on distributed algorithms for capacity maximization.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Wireless Capacity with Oblivious Power in General Metrics

The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight $θ(\log n)$-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal $O(\log n + \log \log Δ)$-approximation to the power control problem using mean power, where $Δ$ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.

0 citations0 reviewsNo code linkedOpen access