|
|
Saswati SarkarAssociate Professor Dept. of Electrical Eng |
My research interests are in the general area of communications networks withemphasis on resource allocation, routing and scheduling, optimization and control of stochastic systemss, distributed systems and algorithms, quality of service and pricing issues. A brief description of my research areas follow.
Our research has contributed towards providing a theoretical framework for overcoming the resource constraints in multihop wireless networks by exploiting the interdependence of the key resources and the network users. This interdependence arises from the fact that the temporary scarcity of one key resource can be compensated by leveraging the availability of another, and different users can share the same resource using temporally and spatially disjoint sharing schemes. We have focussed on an important paradigm in wireless networks, that of group communications. We have shown that the very nature of group communications leads to fundamental changes in relation between important quality of service metrics like throughput, stability and packet loss, e.g., a strategy that maximizes the throughput does not necessarily maximize the stability region or minimize the packet loss. Having demonstrated that group communications requires new design paradigms, we obtained computationally simple, closed form resource allocation strategies that provably maximize important performance metrics without using any information about network traffic statistics. We next considered joint optimization of allocation of multiple resources, and designed scheduling strategies that provably optimize the use of bandwidth, memory and energy. Finally, we considered equitable sharing of resources, and proposed computationally simple flow control and scheduling schemes that provably attain fair sharing of bandwidth and power. Many of our results generalize to arbitrary constrained queueing networks and should therefore be of independent interest in the stochastic control and optimization communities. This research has been funded by the NSF-Career grant.
The theoretical framework described above identifies the best possible performance of the network provided resource contentions can be resolved using centralized resolution mechanisms. But, given the current state of the art in wireless networks, only distributed control strategies that rely on only local information at each node can be implemented. Obtaining provable performance guarantees with distributed control strategies for access of radio-spectrum has however remained a long-standing open problem. We have recently taken a step towards solving this open problem. We have considered a simple distributed scheduling strategy, maximal scheduling, which is readily implementable in existing wireless networks, and completely characterized its performance in arbitrary wireless networks. The characterizations prove that maximal scheduling is guaranteed to attain a certain fraction of the maximum possible stability region of the network; this fraction is a constant in important special cases. This is one of the first few results that guarantees global performance bounds using local decisions in wireless networks. In another recent result, we have considered the dominating set problem, one of the oldest NP-hard problems in computer science and one that finds extensive applications in several different contexts including wireless networks, and have proved that a distributed pproximation algorithm not only attains the best possible approximation ratio but also emulates the performance of the best known centralized algorithm. Thus, in this case, globally optimum approximation ratio can be obtained using locally optimum decisions. We expect this result to be of independent interest in the algorithms community. Finally, we have developed distributed resource allocation strategies with provable performance guarantees in context of specific protocols like ALOHA and Bluetooth. This research has been funded by a collaborative NSF-CNS grant awarded to UPenn, Columbia and RPI and lead by our group at UPenn.
A major obstacle towards large scale deployment of wireless ad hoc networks is the lack of mechanisms for ensuring privacy and the integrity of the communications. An important tradeoff in context of wireless networks is that between security and performance - in many cases the network can be made arbitrarily secure by sacrificing performance and vice-versa, and neither extreme is clearly desirable. Our goal is to provide theoretical foundations for obtaining desired tradeoffs between security and performance, and quantify basic metrics such as the degree and cost of security. We have made progress towards this end for the limited problem of intrusion detection in multi-hop wireless networks. Our goal has been to maximize the detection rate using compromised defenders and limited communication and computation resources. We proved that the detection problems are NP-hard, and developed approximation algorithms that provably attain the desired approximation bounds.
The bulk of the multicast traffic in internet consists of multimedia applications, which consume huge network resources. Good resource allocation strategies can be used for congestion control. The constraint is that any practical resource allocation strategy must be comutationally simple, adaptive and local information based. We have investigated routing and scheduling policies which optimize the system performance and satisfies the above constraints. Multicast transmission allows several receivers to join the same applicaton. These receivers have diverse requirements and capabilities. For this purpose, the multimedia signals are coded in several levels of precisions, and receivers adapt to congeston by appropriately choosing the precision level of reception. This advanced multimedia coding technique calls for innovative distribution strategies. We have studied network resource allocation for multilevel coding, and have developed computing and scheduling strategies for ataining several resource allocation objectives.
Ph.D. in Electrical and Computer Engineering, University of Maryland, College Park, August 2000
Master of Engineering in Electrical Communication Engineering department in Indian Institute of Science, 1996
Bachelor of Engineering in Electronics and Telecommunications in Jadavpur University in 1994