Reading Material:

General:

**[Estrin99]**D. Estrin, R. Govindan, J. S. Heidemann, and S. Kumar.**Next century challenges: Scalable coordination in sensor networks**, In Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99).**[Culler04]**D. Culler, D. Estrin, M.Srivastava.**Overview of Sensor Networks**, IEEE Computer, Aug. 2004**[Hill04]**J. Hill, M. Horton, R. Kling, and L. Krishnamurthy.**The Platforms Enabling Wireless Sensor Networks**, Communications of the ACM, Volume 47, Issue 6, pp. 41-46, June 2004.**[TinyOS] http://www.tinyos.net/**.

__Localization:__

**[Savvides01]**A. Savvides, C.-C. Han, and M. B. Strivastava.**Dynamic****fine-grained localization in ad-hoc networks of sensors**. In MobiCom 01: Proceedings of the 7th ACM Annual International Conference on Mobile Computing and Networking, pages 166-179, 2001.*The basic trilateration scheme: compute the location of a node by using the distances to at least three anchor nodes.***[Graver93]**J. Graver, B. Servatius, and H. Servatius, Combinatorial Rigidity, Chapter 1, volume 2, Graduate Studies in Mathematics, Amer. Math. Soc., 1993.*Introduction to rigidity theory (graph rigidity, generic rigidity, infinitesimal rigidity, etc).***[Jacobs97]**D. J. Jacobs and B. Hendrickson,**An****Algorithm for two dimensional rigidity percolation: The pebble game.**J. Comput. Phys., 137:346-365, 1997.*Pebble game algorithm: O(nm) algorithm to test whether a graph is rigid or not.***[Eren04]**Tolga Eren, David Goldenberg, Walter Whitley, Yang Richard Yang, A. Stephen Morse, Brian D.O. Anderson and Peter N. Belhumeur,**Rigidity, Computation, and Randomization of Network Localization**. In Proceedings of IEEE INFOCOM, Hong Kong, China, April 2004.*The first time that rigidity theory is used for sensor network localization. A greedy algorithm to localize trilateration graphs.***[Moore04]**D. Moore, J. Leonard, D. Rus, S. Teller,**Robust distributed network localization with noisy range measurements**, Proc. ACM SenSys 2004.*Anchor-free algorithm by patching up robust quadrilaterals --- the quadrilaterals that are unlikely to have a local flip.***[Shang03]**Yi Shang, Wheeler Ruml, Ying Zhang, Markus P.J. Fromherz,**Localization from Mere Connectivity**, MobiHoc'03.*Multi-dimensional scaling and its application in network localization.***[Lederer08]**Sol Lederer, Yue Wang, Jie Gao,**Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape**, INFOCOM’08.*Use combinatorial Delaunay complex for anchor-free localization. The intuition is that two adjacent Delaunay triangles must be embedded side-by-side.***[Lee08]**HyungJune Lee, Martin Wicke, Branislav Kusy, Leonidas Guibas,**Localization of Mobile Users Using Trajectory Matching**, ACM International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments, MELT 2008.*Fingerprinting approach but uses a short history of the signals from infrastructure nodes.***[Zhong07]**Ziguo Zhong, Tian He,**MSP: Multi-Sequence Positioning of Wireless Sensor Nodes**, Sensys07.*Use simply distance**comparisons for localization.*

__Location-based
routing:__

**[Bose01]**P. Bose, P. Morin, I. Stojmenovic and J. Urrutia,**Routing with guaranteed delivery in ad hoc wireless networks**, Wireless Networks, 7(6), 609-616, 2001.*One of the first papers on greedy forwarding + face routing to guarantee delivery in ad hoc networks.***[Karp00]**Karp, B. and Kung, H.T.,**Greedy Perimeter Stateless Routing for Wireless Networks**, in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254.*GPSR: one of the first on geographical routing.***[Kuhn03]**F. Kuhn, R. Wattenhofer, Y. Zhang, A. Zollinger,**Geometric****Ad-hoc routing: of theory and practice**, in PODC'03.*How to find a short path with geographical routing?***[Gao01]**J. Gao, L. Guibas, J. Hershberger, L. Zhang, A. Zhu,**Geometric Spanner for Ad hoc Mobile Networks**, in MobiHoc'01.*Develop a planar subgraph from a unit disk graph that is also a planner spanner, i.e., having paths that are at most a constant factor longer than the shortest path in the original graph.***[Kim05]**Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S.,**On the Pitfalls of Geographic Face Routing**, The third International workshop on foundations of mobile computing (DIAL-M-POMC'05), 2005.*Geographical routing in practice fails, because the planar subgraph extraction is not perfect.***[Frey06]***Hannes**Frey, Ivan Stojmenovic,***On****delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks***, Mobicom’06. An in-depth study of the local rules used in variations of face routing. Conclusion: it is subtle! Please pay attention during implementation.***[Popa07]**Lucian Popa, Afshin Rostamizadeh, Richard Karp, Christos Papadimitriou, Ion Stoica,**Balancing Traffic Load in Wireless Networks with Curveball Routing****,**Mobihoc’07.*How to route messages such that the traffic load is balanced for all pairs traffic.***[Mei08]**Alessandro Mei, Julinda Stefa,**Routing in Outer Space: Fair Traffic Load in Multi-Hop Wireless Networks****,**Mobihoc’08.*Geographical routing such that the load of the nodes is balanced.*

__Routing with virtual
coordinates:__

**[Rao03]**Ananth Rao, Christos Papadimitriou, Scott Shenker, and Ion Stoica,**Geographical routing without location information**, Proc. MobiCom'03, pages 96 - 108, 2003.*Generate with rubberband representation virtual coordinates and apply greedy forwarding.***[Papadimitriou04]**David Ratajczak, Christos Papadimitriou,**On****a conjecture related to geometric routing**, ALGOSENSOR, 2004.*Can one find a embedding of a given graph such that greedy forwarding always works?***[Leighton08]**T. Leighton and A. Moitra.**Some results on greedy embeddings in metric spaces.**FOCS08.*The Ratajczak-Papadimitriou conjecture is proved.***[Newsome03]**James Newsome, Dawn Song,**GEM: Graph EMbedding for Routing and Data-Centric Storage in Sensor Networks Without Geographic Information**, Proc. Sensys'03.*Virtual coordinates constructed by using a spanning tree.***[Caesar06]**M. Caesar, M. Castro, E. B. Nightingale, G. O'Shea, A. Rowstron,**Virtual Ring Routing: Network Routing Inspired by DHTs**, Sigcomm’06.*Routing with 1D coordinates.***[Bruck05b]**J. Bruck, J. Gao, A. Jiang,**MAP: Medial Axis Based Geometric Routing in Sensor Networks**, to appear in the 11th Annual International Conference on Mobile Computing and Networking (MobiCom05), August, 2005.*Extract a skeleton from the sensor network and use it to guide routing around holes.*

__Landmark-based
routing:__

**[Kleinberg04]**J. Kleinberg, A. Slivkins, T. Wexler.**Triangulation and Embedding using Small Sets of Beacons.**Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.*Using the distances to landmarks and triangle inequality, one can approximate the distance for most of pairs.***[Fang05a]**Qing Fang, Jie Gao, Leonidas Guibas, Vin de Silva, Li Zhang,**GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks**, Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM'05), March, 2005.*Route around holes. Use combinatorial Delaunay graph to capture the global topology.***[Fonseca05]**Rodrigo Fonseca, Sylvia Ratnasamy, Jerry Zhao, Cheng Tien Ee and David Culler, Scott Shenker, Ion Stoica,**Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets**, NSDI'05.*Landmark-based routing scheme.***[Mao07]**Yun Mao, Feng Wang, Lili Qiu, Simon S. Lam, Jonathan M. Smith,**S4: Small State and Small Stretch Routing Protocol for Large Wireless Sensor Networks**, NSDI’07.*Landmark-based routing with constant stretch, and \sqrt{n} routing table size.***[Thorup01]**Mikkel Thorup, Uri Zwick,**Compact Routing Schemes**, SPAA'01.*The scheme in S4.***[Nguyen07]**An Nguyen, Nikola Milosavljevic, Qing Fang, Jie Gao, Leonidas Guibas,**Landmark selection and Greedy Landmark-descent Routing for Sensor Networks**, INFOCOM’07.*Landmark-selection and a coupled landmark-based routing scheme with bounded stretch.***[Tsuchiya88]**P. F. Tsuchiya.**The landmark hierarchy: a new hierarchy for routing in very large networks**. In Sigcomm88.*Landmark hierarchy for routing.***[Funke05a]**S. Funke, L. Guibas, A. Nguyen, Y. Wang,**Distance Sensitive Routing and Information Brokerage in Sensor Networks**, DCOSS’06.*Improved landmark hierarchy for routing with worse-case guarantee.*

__Data-centric
query:__

**[Intanagonwiwat00]**Chalermek Intanagonwiwat, Ramesh Govindan and Deborah Estrin,**Directed diffusion: A scalable and robust communication paradigm for sensor networks**, In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM '00), August 2000, Boston, Massachussetts.*The first paper on data-centric routing in sensor networks. Data discovery relies on flooding the network.***[Ratnasamy02]**Sylvia Ratnasamy, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, Brad Karp, Scott Shenker,**GHT: A Geographic Hash Table for Data-Centric Storage**, In First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA) 2002.*Hash data to geographical locations, for storage and retrieval.***[Braginsky02]**David Braginsky, Deborah Estrin,**Rumor routing algorithm for sensor networks**, 1^{st}ACM workshop on Wireless Sensor Networks, 2002.*The data source sends agents that walk randomly in the network and leave traces. Sink will send queries along some other random walk and hope to encounter the data traces.***[Sarkar06]**Rik Sarkar, Xianjin Zhu, Jie Gao,**Double Rulings for Information Brokerage in Sensor Networks**, MobiCom06.*Hash data to circles.***[Fang06]**Qing Fang, Jie Gao, Leonidas Guibas,**Landmark-based Information Storage and Retrieval in Sensor Networks,**INFOCOM'06.*Landmark-based data-centric routing with GLIDER: use GHT on top level, use double rulings at bottom level.***[Awerbuch91]**Baruch Awerbuch, David Peleg.**Concurrent online tracking of mobile users,**SIGCOMM'91.*Track mobile users. Use hierarchies.***[Li00]**Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger and Robert Morris,**A scalable location service for geographic ad hoc routing,**MobiCom'00.*Hierarchical structure with universal hashing. Application in location service.***[Abraham04]**I. Abraham, D. Dolev, D. Malkhi ,**LLS : a Locality Aware Location Service for Mobile Ad Hoc Networks**, DIALM-POMC 2004.*Improve the above algorithm in terms of worst-case bound.***[Vieira08]**Luiz F. M. Vieira, Uichin Lee, Mario Gerla,**Phero-Trail: a Bio-inspired Location Service for Mobile Underwater Sensors**, WUWNet'08,*Location service for mobile underwater 3D networks.*

**[Greenstein03]**B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker, DIFS: A distributed index for features in sensor networks. In Proc. of the 1st IEEE workshop on sensor networks protocols and applications, 2003. Hashing scheme that exploits data correlation.**[Madden02]**Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong.**TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks**, OSDI, December 2002.*Aggregation with a tree.***[Hellerstein03]**Joseph Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek.**Beyond Average: Towards Sophisticated Sensing with Queries**. In Proceedings of IPSN, 2003.**[Nath04] Suman Nath, Phillip B. Gibbons, Zachary Anderson, and Srinivasan Seshan,**__Synopsis Diffusion for Robust Aggregation in Sensor Networks__. In proceedings of ACM SenSys'04.*Use multipath routing to improve routing robustness. Order and duplicate insensitive synopsis needs to be used to prevent one data value to be aggregated multiple times.***[Considine04] Jeffrey Considine, Feifei Li, George Kollios and John Byers, Approximate Aggregation Techniques for Sensor Databases, Proc. ICDE 2004.***Independent development of the same idea as above.***[Broder02] A. Broder and M. Mitzenmacher,****Network Applications of Bloom Filters: A Survey**,*Bloom filters: a classical data structure for the representation of sets.***[Shrivastava04] Nisheeth Shrivastava, Chiranjeeb Buragohain, Divy Agrawal, Subhash Suri,**__Medians and Beyond: New Aggregation Techniques for Sensor Networks__, ACM SenSys '04, Nov. 3-5, Baltimore, MD.*Approximate answer to medians, reduce storage and message size.***[Kamra07] Abhinav Kamra, Vishal Misra, Dan Rubenstein,**__CountTorrent: Ubiquitous Access to Query Aggregates in Dynamic and Mobile Sensor Networks__, Sensys’07.*Use multipath routing and record what value has been aggregated.***[Manjhi05] Amit Manjhi, Suman Nath, and Phillip B. Gibbons,**__Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams__, ACM SIGMOD 2005.*Combine synopsis diffusion with tree-based aggregation.***[Przydatek03] Bartosz Przydatek, Dawn Song, Adrian Perrig,**__SIA: Secure Information Aggregation in Sensor Networks__, Sensys’03.*Secure computation of median and average.*

__Multi-dimensional range
queries:__

**[Berg99] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf,**__Computational Geometry, Algorithms and Applications, Chapter 5, Orthogonal Range Searching,__Springer, Second edition, 1999.**[Matousek94] Jirka Matousek,**__Geometric range searching__. Computing Surveys, volume 26, number 4, page. 422-461, 1994.**[Li03a] X. Li, Y. J. Kim, R. Govindan, W. Hong,**__Multi-dimensional Range Queries in Sensor Networks__, Proc. ACM SenSys 2003.**[Gao04] J. Gao, L. Guibas, J. Hershberger, L. Zhang,**__Fractional Cascaded Information in a Sensor Network__, IPSN'04.**[Ganesan02] Deepak Ganesan, Deborah Estrin and John Heidemann,**__DIMENSIONS: why do we need a new data handling architecture for sensor networks__. In Proc. ACM SIGCOMM workshop on hot topics in networks, 2002.

__Boundary
detection:__

**[Funke05] Stefan Funke, Topological Hole Detection in Wireless Sensor Networks and its Applications, The 3rd ACM/SIGMOBILE International Workshop on foundations of Mobile Computing (DIAL-M-POMC) 2005.***Detect broken contours caused by network holes.***[Wang06] Yue Wang, Jie Gao, Joseph S.B. Mitchell, Boundary Recognition in Sensor Networks by Topological Methods, Mobicom06.****[Kroller06] A. Kröller, S. P. Fekete, D. Pfisterer, S. Fischer, Deterministic boundary recognition and topology extraction for large sensor networks, SODA06.**

__Coding and applications in wireless
communication and storage:__

**[Fragouli06]**C. Fragouli, J. Le Boudec, Jorg Widmer,**Network coding: an instant primer**. A (very) short survey of network coding and applications.**[Katti06]**S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft,**XORs in The Air: Practical Wireless Network Coding**, Sigcomm’06. Use network coding in wireless networks.- [Katti07] Sachin Katti, Shyamnath Gollakota, Dina Katabi, Embracing Wireless Interference: Analog Network Coding, SIGCOMM 2007. Wireless interference is in fact network coding with the analog signals. The paper uses wireless interference intentionally to improve system throughput.
- [Katti08] Sachin Katti, Dina Katabi, Hari Balakrishnan, Muriel Medard, Symbol-level Network Coding for Wireless Mesh Networks, SIGCOMM 2008. The scheme in this paper patches up uncorrupted portions of packets delivered by lossy wireless channels.
- [Gollakota08] Shyamnath Gollakota, Dina Katabi, ZigZag Decoding: Combating Hidden Terminals in Wireless Networks, SIGCOMM 2008. Combat hidden terminal problem in wireless networks. When there are collisions.
**[Dubois05]**Henri Dubois-Ferriere, Deborah Estrin and Martin Vetterli,**Packet Combining in Sensor Networks**, Sensys'05.**[Dimakis05] A. G. Dimakis, V. Prabhakaran and K. Ramchandran, Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes, IPSN'05.***Use erasure code to improve data robustness.***[Kamra06] Abhinav Kamra, Vishal Misra, Jon Feldman, Dan Rubenstein,**__Growth Codes: Maximizing Sensor Network Data Persistence__, SIGCOMM06.*There is a sink in the network. However, instead of sending the data directly to the sink, the nodes in the network propagate coded packets (whose code degree --- the number of source data blocks --- grows over time). The sink is able to decode all the data eventually when it receives enough coded packets.***[Lin07]**Yunfeng Lin, Ben Liang, Baochun Li, Data Persistence in Large-scale Sensor Networks with Decentralized Fountain Codes, INFOCOM07.*This paper uses random walk and Metropolis algorithm to construct Fountain Codes.***[Nath09] Suman Nath, Energy Efficient Sensor Data Logging with Amnesic Flash Storage, IPSN’09.***Compression schemes with data aging.*

__Sensor
selection:__

**[Krause06] Andreas Krause, Carlos Guestrin, Anupam Gupta, Jon Kleinberg, Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost, IPSN’06.***Place sensors for the optimal sensing results.***[Das08] A. Das and D. Kempe. Sensor selection for minimizing worst-case prediction error, IPSN’08.***Select a minimum subset of sensors for aggregation that achieves some error given bound.***[Gandhi07] Sorabh Gandhi, Subhash Suri, Emo Welzl,**__Catching Elephants with Mice: Sparse Sampling for Monitoring Sensor Networks__, Sensys 2007.*Use random samples to catch significant events.***[Shrivastava05] Nisheeth Shrivastava, Subhash Suri, Csaba, Toth, Detecting Cuts in Sensor Networks, IPSN'05.***Use a small subset of sensor nodes to*d*etect whether the network is partitioned.***[Singh07]**Jaspreet Singh, Rajesh Kumar, Upamanyu Madhow, Subhash Suri, Richard Cagley, Tracking Multiple Targets Using Binary Proximity Sensors, IPSN'07.

** **