Guglielmo Marconi
research :: wireless networking

Prabal Dutta
410 Soda Hall #1776
Computer Science Division
Berkeley, California 94720

prabal   cs . berkeley . edu
(510) 643-3327 (Office)



Overview Wireless networking.
Select Projects

Disco. An asynchronous neighbor discovery and rendezvous protocol that allows two or more nodes to operate their radios at low duty cycles (e.g. 1%) and yet still discover and communicate with one another during infrequent, opportunistic encounters without requiring any prior synchronization information. Disco nodes pick a pair of prime numbers such that the sum of their reciprocals is equal to the desired radio duty cycle. Each node increments a local counter with a globally-fixed period. If a node's local counter value is divisible by either of its primes, then the node turns on its radio for one period. This protocol ensures that two nodes will have some overlapping radio on-time within a bounded number of periods, even if nodes independently set their own duty cycle.


Backcast. A backcast is a link-layer frame exchange in which a single radio frame transmission triggers zero or more acknowledgment frames that interfere non-destructively at the initiator. The above figure illustrates a backcast exchange involving three nodes. The two responders have their radios configured to automatically acknowledge any received frames. The backcast exchange begins with the initiator transmitting a probe frame to the hardware broadcast address. Both responders receive the probe and they both transmit identical acknowledgments. Although these two acknowledgments collide at the initiator, as long as certain conditions are met, this collision is non-destructive, allowing the initiator to correctly decode the acknowledgment frame and conclude that at least one of its neighbors responded. A number of useful services can be built using Backcast's "acknowledged anycast"-like semantics, including low-power asynchronous network wakeup, low-power unicast communications, and a constant-time logical OR over the neighborhood.


Flush. Flush is a reliable, high goodput bulk data transport protocol for wireless sensor networks. Flush provides end-to-end reliability, reduces transfer time, and adapts to time-varying network conditions. It achieves these properties using end-to-end acknowledgments, implicit snooping of control information, and a rate-control algorithm that operates at each hop along a flow. Using several real network topologies, we show that Flush closely tracks or exceeds the maximum goodput achievable by a hand-tuned but fixed rate for each hop over a wide range of path lengths and varying network conditions. Flush is scalable; its effective bandwidth over a 48-hop wireless network (shown above) is approximately one-third of the rate achievable over one hop! We collected all of the performance data for the study using Flush itself.


Secure Deluge. A system for secure and efficient network programming in resource-constrained wireless sensor networks. Secure Deluge demonstrates the feasibility and low overhead of adding public-key-based program source authentication, strong integrity verification, and freshness checks to existing network programming services. The above left figure illustrates the program to packet transformation used to secure network programming. The shaded boxes represent information added for security. The above right figure illustrates Secure Deluge in action. The top part shows packet reception (red arrow) and verification (green arrow) for one page of data (note: verification times have been delayed by 10 ms for clarity). The bottom part shows the CDF of programming completion time for 28 nodes using standard Deluge with 23-byte payloads (dotted red line), standard Deluge with 64-byte payloads (dashed green line) and Secure Deluge with 56-byte payload with an 8-byte hash (solid blue line).


Publications
  1. "Mobility Changes Everything in Low-Power Wireless Sensornets",
    Prabal Dutta and David Culler,
    In Proceedings of the 12th Workshop on Hot Topics in Operating Systems (HotOS-XII), Monte Verita, Switzerland, May 18-20, 2009.

  2. "Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications",
    Prabal Dutta and David Culler,
    In Proceedings of the Sixth ACM Conference on Embedded Networked Sensor Systems (SenSys'08), Nov. 5-7, 2008. © ACM, 2008

  3. "Wireless ACK Collisions Not Considered Harmful",
    Prabal Dutta, Razvan Musaloiu-E., Ion Stoica, and Andreas Terzis,
    In Proceedings of the Seventh Workshop on Hot Topics in Networks (HotNets-VII), Calgary, Alberta, Canada, Oct. 6-7, 2008.

  4. "Flush: A Reliable Bulk Transport Protocol for Multihop Wireless Networks",
    Sukun Kim, Rodrigo Fonseca, Prabal Dutta, Arsalan Tavakoli, David Culler, Philip Levis, Scott Shenker, and Ion Stoica,
    In Proceedings of the Fifth ACM Conference on Embedded Networked Sensor Systems (SenSys'07), Nov. 6-9, 2007.

  5. "Procrastination Might Lead to a Longer and More Useful Life",
    Prabal Dutta, David Culler, and Scott Shenker,
    In Proceeding of the Sixth Workshop on Hot Topics in Networks (HotNets-VI), Atlanta, GA, Nov. 14-15, 2007.

  6. "A Modular Sensornet Architecture: Past, Present, and Future Directions",
    Arsalan Tavakoli, Prabal Dutta, Jaein Jeong, Sukun Kim, Jorge Ortiz, Phil Levis, and Scott Shenker,
    In Proceedings of the International Workshop on Wireless Sensor Network Architecture (WSNA'07), Apr. 2007.

  7. "Some Implications of Low Power Wireless to IP Networking",
    Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip Levis,
    In Proceedings of the Fifth Workshop on Hot Topics in Networks (HotNets-V), Irvine, CA, Nov. 29-30, 2006.

  8. "Securing the Deluge Network Programming System",
    Prabal K. Dutta, Jonathan W. Hui, David C. Chu, and David E. Culler
    In Proceedings of the Fifth International Conference on Information Processing in Sensor Networks (IPSN'06), pp. 326-333, 2006.

  9. "On the Scalability of Routing Integrated Time Synchronization",
    Janos Sallai, Branislav Kusy, Akos Ledeczi, and Prabal Dutta
    In Proceedings of the 3rd European Workshop on Wireless Sensor Networks (EWSN'06), pp. 115-131, 2006.

  10. "Elapsed Time on Arrival: A Simple and Versatile Primitive for Time Synchronization Services",
    Branislav Kusy, Prabal Dutta, Philip Levis, Miklos Maroti, Akos Ledeczi, and David Culler,
    International Journal of Ad hoc and Ubiquitous Computing, Vol. 2, No. 1, 2006.

  11. "Towards a Sensor Network Architecture: Lowering the Waistline",
    David Culler, Prabal Dutta, Cheng Tien Ee, Rodrigo Fonseca, Jonathan Hui, Philip Levis, Joseph Polastre, Scott Shenker, Ion Stoica, Gilman Tolle, Jerry Zhao,
    In Proceedings of the Tenth Workshop on Hot Topics in Operating Systems (HotOS X), 2005.

  12. "ExScal: Elements of an Extreme Scale Wireless Sensor Network",
    Anish Arora, Rajiv Ramnath, Emre Ertin, Prasun Sinha, Sandip Bapat, Vinayak Naik, Vinod Kulathumani, Hongwei Zhang, Hui Cao, Mukundan Sridharan, Santosh Kumar, Nick Seddon, Chris Anderson, Ted Herman, Nishank Trivedi, Chen Zhang, Mikhail Nesterenko, Romil Shah, Sandeep Kulkarni, Mahesh Aramugam, Limin Wang, Mohamed Gouda, Young-ri Choi, David Culler, Prabal Dutta, Cory Sharp, Gilman Tolle, Mike Grimmer, Bill Ferriera, Ken Parker
    In Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005), 2005.

Tech Reports
  1. "An Empirical Study of Low Power Wireless",
    Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip Levis, SING Tech Report, SING-08-03, Stanford University, 2008.

  2. "Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks",
    Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip Levis, SING Tech Report, SING-06-00, Stanford University, 2006.

Patents / Applications
  1. "System and Method for Distributed Control of Unrelated Devices and Programs",
    Prabal Dutta and Charles McManis, 2002 (filed).

  2. "System and Method for On-Demand Communications with Legacy Networked Devices",
    Prabal Dutta, 2001 (filed).



Prabal K. Dutta
Computer Science Division
Department of Electrical Engineering and Computer Sciences
The University of California, Berkeley
Soda Hall #1776, Berkeley, California 94720