Sarkar, Saswati
Email Address
ORCID
Disciplines
relationships.isProjectOf
relationships.isOrgUnitOf
Position
Introduction
Research Interests
Collection
50 results
Search Results
Now showing 1 - 10 of 50
Publication A Framework for Optimal Battery Management for Wireless Nodes(2003-02-01) Sarkar, Saswati; Adamou, MariaThe focus of this paper is to extend the lifetime of a battery powered node in wireless context. The lifetime of a battery depends on both the manner of discharge and the transmission power requirements. We present a framework for computing the optimal discharge strategy which maximizes the lifetime of a node by exploiting the battery characteristics and adapting to the varying power requirements for wireless operations. The complexity of the optimal computation is linear in the number of system states. However, since the number of states can be large, the optimal strategy can only be computed offline and executed via a table lookup. We present a simple discharge strategy which can be executed online without any table lookup and attains near maximum lifetime.Publication Economy of Spectrum Access in Timy Varying Multichannel Networks(2010-10-01) Khouzani, M.H.R.; Sarkar, SaswatiWe consider a wireless network consisting of two classes of potentially mobile users: primary users and secondary users. Primary users license frequency channels and transmit in their respective bands as required. Secondary users resort to unlicensed access of channels that are not used by their primary users. Primaries impose access fees on the secondaries which depend on access durations and may be different for different primary channels and different available communication rates in the channels. The available rates to the secondaries change with time depending on the usage status of the primaries and the random access quality of channels. Secondary users seek to minimize their total access cost subject to stabilizing their queues whenever possible. Our first contribution is to present a dynamic link scheduling policy that attains this objective. The computation time of this policy, however, increases exponentially with the size of the network. We next present an approximate scheduling scheme based on graph partitioning that is distributed and attains arbitrary trade-offs between aggregate access cost and computation times of the schedules, irrespective of the size of the network. Our performance guarantees hold for general arrival and primary usage statistics and multihop networks. Each secondary user is, however, primarily interested in minimizing the cost it incurs, rather than in minimizing the aggregate cost. Thus, it will schedule its transmissions so as to minimize the aggregate cost only if it perceives that the aggregate cost is shared among the users as per a fair cost sharing scheme. Using concepts from cooperative game theory, we develop a rational basis for sharing the aggregate cost among secondary sessions and present a cost sharing mechanism that conforms to the above basis.Publication Admission Control Framework to Provide Guaranteed Delay in Error-Prone Wireless Channel(2007-01-01) Sarkar, Saswati; Chaporkar, PrasannaThis paper considers a wireless system in which different sessions may use different channels with different transmission characteristics. A general framework for admission control and scheduling that provides stochastic delay and packet drop guarantees in this error-prone wireless system is proposed. By "general," the authors mean that the scheduling policies from a large class can be plugged in this framework and that admission control conditions can be obtained for different arrival processes. This enables the use of many scheduling policies that have not been considered so far for error-prone wireless systems. Using large deviation bounds and renewal theory, the authors prove that once a session i is admitted, irrespective of the scheduling policy and the channel errors experienced by other sessions, i obtains its desired quality of service. The admission control algorithm uses only individual channel statistics of sessions and not joint statistics, and the scheduling does not require any knowledge of instantaneous channel states.Publication Fairness in Cellular Mobile Networks(2002-08-01) Sarkar, Saswati; Sivarajan, Kumar N.Channel allocation algorithms for channelized cellular systems are discussed from a new perspective, viz., fairness of allocation. The concepts of relative and absolute fairness are introduced and discussed. It will be shown that under certain reasonable assumptions, there exists an absolute (max-min) fair carried traffic intensity vector (a vector describing the traffic carried in the cells of the system). We also show that this vector is unique. We describe some properties of the max-min fair carried traffic intensity vector in an asymptotic limit where the traffic and the number of channels are scaled together. For each traffic pattern, we determine a fixed channel allocation which attains this max-min fair carried traffic intensity vector independent of the value of the offered traffic, in the same asymptotic limit. Finally, we discuss a tradeoff between being max-min fair and trying to maximize revenue. We conclude this correspondence by discussing some possible extensions of our work.Publication Jointly optimal transmission and probing strategies for multichannel wireless systems(2006-03-22) Guha, Sudipto; Sarkar, Saswati; Munagala, KameshWe consider a wireless system with multiple channels when each channel has several different transmission states. Different states are associated with different probabilities of successful transmissions. In such networks, we are faced with making transmission decisions in the presence of partial information about channel states. This (typically probabilistic) information about any channel can be refined by sending control packets in the channels. In presence of multiple alternative channels, this process of probing every channel to find the best one is onerous and resource consuming. There is a natural tradeoff between the resource consumed in probing and the estimate of channel state we can obtain. The desired tradeoff can be attained by judiciously determining which and how many channels to probe and also which channel to transmit. We present adaptive algorithms for provably approximating the desired tradeoffs within constant factors.Publication Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks(2008-02-01) Chaporkar, Prasanna; Kar, Koushik; Luo, Xiang; Sarkar, SaswatiThe question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the "interference degree" of the network, which is the maximum number of transmitter–receiver pairs that interfere with any given transmitter–receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.Publication MAC Layer Wireless Multicast: Theory and Approaches(2003-06-29) Chaporkar, Prasanna; Sarkar, SaswatiWe develop the theory behind wireless MAC layer multicast and obtain throughput optimal transmission policies that provide desired loss and power characteristics. Key idea is to exploit the broadcast nature of wireless channel, i.e, a sender can reach all the receivers in a MAC layer multicast group with a single transmission. Through the broadcast nature of wireless transmissions provides a possible approach to improve the efficiency of the multicast communication, it also imposes critical challenges. A multicast specific challenge is that some but not all the receivers may be ready to receive on account of the interference caused by the transmissions in their neighborhood. The readiness state of a receiver depends on the network load. A transmission policy, which does not transmit until all the receivers are ready may have to wait long and hence it may provide low system throughput. On the other hand, if the sender transmits when only a few receivers are ready, then the transmitted packet will be lost at the receivers that were not ready. This packet loss may not be acceptable. Hence, the policy decision in this case is when should a sender transmit. Further, a sender may achieve required loss characteristics by transmitting a packet several times till sufficient number of receivers receive the packet. But additional power consumption in this case at the sender imposes a limit on the number of such transmissions. We consider a single multicast session in isolation. The impact of the network on the multicast session is modeled by considering random receiver readiness states. In each slot, we assume that a receiver is ready with probability (w.p.) p. Further, the number of arrivals in each slot is assumed to be iid with expectation denoted by λ.Publication Optimum Scheduling and Memory Management in Input Queued Switches With Finite Buffer Space(2004-12-01) Sarkar, SaswatiThe goal of this paper is to design optimal scheduling and memory management so as to minimize packet loss in input queued switches with finite input buffers. The contribution is to obtain closed-form optimal strategies that minimize packet loss in 2 x 2 switches with equal arrival rates for all streams. For arbitrary arrival rates, the contribution is to identify certain characteristics of the optimal strategy, and use these characteristics to design a near-optimal heuristic. A lower bound for the cost associated with packet loss for N x N switches is obtained. This lower bound is used to design a heuristic which attains near-minimum packet loss in N x N switches with arbitrary N. These policies reduce packet loss by about 25% as compared to the optimal strategy for the infinite buffer case. The framework and the policies proposed here apply to buffer-constrained wireless networks as well.Publication A Framework for Misuse Detection in Ad Hoc Networks—Part I(2006-02-01) Subhadrabandhu, Dhanant; Sarkar, Saswati; Anjum, FarooqWe consider ad hoc networks with multiple, mobile intruders. We investigate the placement of the intrusion detection modules for misuse-based detection strategy. Our goal is to maximize the detection rate subject to limited availability of communication and computational resources. We mathematically formulate this problem, and show that computing the optimal solution is NP-hard. Thereafter, we propose two approximation algorithms that approximate the optimal solution within a constant factor, and prove that they attain the best possible approximation ratios. The approximation algorithms though require recomputation every time the topology changes. Thereafter, we modify these algorithms to adapt seamlessly to topological changes. We obtain analytical expressions to quantify the resource consumption versus detection rate tradeoffs for different algorithms. Using analysis and simulation, we evaluate these algorithms, and identify the appropriate algorithms for different detection rate and resource consumption tradeoffs.Publication A Jointly Optimum Scheduling and Memory Management for Matching Based Service(2002-12-10) Sarkar, SaswatiWe consider resource allocation in a system which must process and subsequently deliver jobs from N input terminals to N output terminals as per matching constraints. Jobs are stored in a common memory before processing and transfer. The resource allocation objective is to minimize the job loss due to memory overflow. We present optimal scheduling and memory management policies for attaining this objectives for N = 2 and symmetric traffic. We identify certain characteristics of the optimal strategy for N = 2 and asymmetric traffic, and present a near optimal heuristic for this case. We obtain a heavy traffic lower bound for the optimal discounted cost function for the general case of arbitrary N and arbitrary traffic. We use this lower bound to propose a heuristic strategy whose performance is close to the optimal strategy in this case. The policies proposed in this paper substantially outperform the existing strategy for the system, which was designed and proved to be optimal under the assumption of infinite storage.