The world of wireless sensor networks has seen tremendous interest in the recent past from researchers and industry. Inexpensive battery-powered sensors with limited computing and wireless networking capabilities, such as the Motes, have been deployed for various applications, such as border patrol and environmental monitoring. Many of the interesting and important problems result from the special conditions, and has led to algorithms with geometric considerations. Sensors should be placed according to the details of the areas they need to cover (e.g. terrains, buildings, etc.). Transmitters are battery powered, hence their wireless communication range is short, or if they can control their range, would prefer to transmit information over multiple hops to conserve energy. The objective of a sensor network is to maximize the operational time by considering sensing, computing, and communication costs together.
Special protocols are necessary if the nodes are moving, for example, communication between cars. The protocols need to take into account the high probability that messages are dropped due to communication channel impairments. In addition, the nodes are unlikely to keep an up-to-date copy of their neighbors due to frequent movement of the neighbors. Therefore, the algorithms and protocols designed for such mobile ad hoc sensor networks lie in the intersection of ad-hoc networks, computational geometry, databases, and graph theory.
Alon Efrat, Department of Computer Science
Class Hours
Office Hours
Mondays and Wednesdays 9AM - 10:15 PM in Gould-Simpson 906
TueThu 2:00 PM - 3:30 PM Gould-Simpson 742 Or by appointment. - - -
The topics discussed in the seminar would include, but not limited to:
Algorithms for sensors and basement locations
Here we need to locate sensors in a way that a building or terrain would sensor a large enough area for surveillance. We also discuss other relevant location problems. (4; 3, 4, Appendix A): approximating functions asymptotically, some common recurrence formulas.
Protocols for maintaining connectivity between moving points
We will study routing algorithms and message forwarding mechanisms that are resilient to mobility in the network.
Indexing moving nodes, and location bases services
Here we study ways to efficiently maintain data-bases that can answer queries on a large number of objects which are moving in the plane. For example, to find cellular user which are currently within a certain region.
To be announced.
The final grade is determined by 90% quality of presentation and 10% participations in class.
Thanks to Prof. Subhash Suri, UCSB for allowing us to use his material.
Communication in Vehicular Network
Case Study
Dozer: Ultra-Low Power Data Gathering in Sensor Networks[PDF]. Nicolas Burri, Pascal von Rickenbach and Roger Wattenhofer
Localization and Network Discovery
Robust distributed network localization with noisy range measurements [ PDF ]
D. Moore, J. Leonard, D. Rus, S. Teller. Proc. ACM SenSys 2004.
Mobile-Assisted Localization in Wireless Sensor Networks [ PDF ]
N. B. Priyantha, H. Balakrishnan, E. Demaine, S. Teller. IEEE INFOCOM, Miami, FL, March 2005.
A theory of network localization [ PDF ]
J. Aspnes et al. IEEE Transactions on Mobile Computing.
Distributed Localization Using Noisy Distance and Angle Information [ PDF ]
Amitabh Basu, Jie Gao, Joseph S. B. Mitchell, and Girishkumar Sabhnani. MobiHoc 2005.
Force-Directed Approaches to Sensor Localization [ PDF ]
C. Erten, D. Forrester, A. Iyer, and S. G. Kobourov. 8th Workshop on Algorithm Engineering and Experiments (ALENEX) 2006.
Localization for Anchoritic Sensor Networks [ PDF ]
Baryshnikov and Jian Tan, Distributed Computing in Sensor Systems (DCOSS), 2007.
Clock Synchronization
Clock Synchronization: Open Problems in Theory and Practice Christoph Lenzen, Thomas Locher, Philipp Sommer, and Roger Wattenhofer [PDF]
Key Distribution and Security
Topics in security in Wireless Networks (survey) [PDF ]
Random keys Distribution Scheme for Sensor Networks [PDF]
A canonical Seed Assignment Model for Key Predistribution in Wireless Sensor Networks [PDF]
Geographical Routing
Geographic Routing Made Practical [ PDF ]
Y.-J. Kim, R. Govindan, B. Karp, S. Shenker, Proc. of USENIX NSDI 2005.
GPSR: Greedy perimeter stateless routing for wireless networks [ PDF ]
B. Karp and H. T. Kung. Proc. Mobicom 2000.
Geographic Routing With Limited Information in Sensor Networks [ PDF ]
S. Subramanian and S. Shakkottai Proc. IPSN 2005.
Geometric and Topological Methods in Routing
Locating and Bypassing Routing Holes in Sensor Networks [ PDF ]
Q. Fang, J. Gao and L. J. Guibas. Proc. INFOCOM 2004.
GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks [ PDF ]
Q. Fang, J. Gao, L. J. Guibas, V, de Silva, L. Zhang. Proc. INFOCOM 2005.
Geometric Spanner for Routing in Mobile Networks [ PDF ]
J. Gao, L. J. Guibas, J. Hershburger, L. Zhang, and A. Zhu. Proc. MobiHoc 2001.
Range Queries in Sensor Networks
Multi-dimensional Range Queries in Sensor Networks [ PDF ]
X. Li, Y. J. Kim, R. Govindan, W. Hong. Proc. ACM SenSys 2003.
Fractionally cascaded information in a sensor network [ PDF ]
J. Gao, L. J. Guibas, J. Hershberger, L. Zhang. Proc. IPSN 2004.
Data-Centric Storage in Sensornets with GHT [ PDF ]
S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin and F. Yu. Mobile Networks and Applications, 2003.
Data Aggregation: Various Aspects
Resilient Aggregation in Sensor Networks [ PDF ]
David Wagner. Proc. SASN 2004.
Medians and Beyond: New Aggregation Techniques for Sensor Networks [ PDF ]
N. Shrivastava, C. Buragohain, D. Agrawal, S. Suri. Proc. ACM SenSys '04.
Robust Aggregation in Sensor Networks [ PDF ]
G. Kollios, J. Byers, J. Considine, M. Hadjieleftheriou, and F. Li. Proc. ICDE 2004.
Approximate Isocontours and Spatial Summaries for Sensor Networks [ PDF ]
Sorabh Gandhi, John Hershberger, and Subhash Suri. (Best Paper Award.) IPSN '07
Tracking and Geometric Reasoning
Efficient Location Tracking Using Sensor Networks [ PDF ]
H. T. Kung and D. Vlah. Proc. IEEE Wireless Communications and Networking Conference, 2003.
Spatiotemporal Multicast in Sensor Networks [ PDF ]
Q. Huang, C. Lu and G.-C. Roman. Proc. SenSys 2003.
On Target Tracking with Binary Proximity Sensors [ PDF ]
W. Kim, K. Mechitov, J. Choi and S. Ham. Proc. IPSN 2005.
Construction of Connected Dominating Sets
On Greedy Construction of Connected Dominating Sets in Wireless Sensor Networks [ PDF ]
Y. Li, M. T. Thai, F. Wang, C. Yi, P.-J. Wan, D.-Z Du, WCMC 2005.
An Extended Localized Algorithm for Connected Dominating Set Formation in Wireless Ad Hoc Networks [ PDF ]
F. Dai and J. Wu, IEEE Transactions on Parallel and Distributed Systems, October 2004.
Constant time distributed dominating set approximation [ PDF ]
F. Kuhn and R. Watternhofer.
Boundary Detection
Deterministic boundary recognition and topology extraction for large sensor networks [ PDF ]
A.Kroller, S.P. Fekete, D.Pfisterer, S.Fischer. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 1000-1009.
Boundary Recognition in Sensor Networks by Topological Methods [ PDF ]
Yue Wang, Jie Gao, Joseph S. B. Mitchell. Proc. 12th Annual ACM Conference on Mobile Computing and Networking (MobiCom 2006).
J. Arango, A. Efrat, S. Ramasubramanian, S. Pink, and M. Krunz, "Retransmission and Backoff Strategies for Wireless Broadcasting," Elsevier Ad Hoc Networks Journal, vol. 8, no. 1, January 2010, pp. 77-95. [ PDF]
Book