Cache Placement in Sensor Networks Under Update Cost Constraint

  • Bin Tang
  • Samir Das
  • Himanshu Gupta
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)


In this paper, we address an optimization problem that arises in context of cache placement in sensor networks. In particular, we consider the cache placement problem where the goal is to determine a set of nodes in the network to cache/store the given data item, such that the overall communication cost incurred in accessing the item is minimized, under the constraint that the total communication cost in updating the selected caches is less than a given constant. In our network model, there is a single server (containing the original copy of the data item) and multiple client nodes (that wish to access the data item). For various settings of the problem, we design optimal, near-optimal, heuristic-based, and distributed algorithms, and evaluate their performance through simulations on randomly generated sensor networks.


Sensor Network Sensor Node Greedy Algorithm Data Item Steiner Tree 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Badrinath, B., Srivastava, M., Mills, K., Scholtz, J., Sollins, K. (eds.): Special Issue on Smart Spaces and Environments. IEEE Personal Communications (2000)Google Scholar
  2. 2.
    Bahl, P., Padmanabhan, V.N.: Radar: An in-building RF-based user-location and tracking system. In: INFOCOM 2000 (2000)Google Scholar
  3. 3.
    Berman, P., Ramaiyer, V.: Improved approximation algorithms for the steiner tree problem. J. Algorithms (1994)Google Scholar
  4. 4.
    Bhattacharya, S., Kim, H., Prabh, S., Abdelzaher, T.: Energy-conserving data placement and asynchronous multicast in wireless sensor networks. In: MobiSys 2003 (2003)Google Scholar
  5. 5.
    Bulusu, N., Heidemann, J., Estrin, D.: GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7(5) (2000)Google Scholar
  6. 6.
    Estrin, D., Intanagonwiwat, C., Govindan, R., Heidemann, J.: Directed diffusion for wireless sensor networks. IEEE/ACM TON 11(1), 2–16 (2003)Google Scholar
  7. 7.
    Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: IEEE FOCS 1999, pp. 378–388 (1999)Google Scholar
  8. 8.
    Chu, M., Haussecker, H., Zhao, F.: Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks. IEEE Journal of High Performance Computing Applications (2002)Google Scholar
  9. 9.
    Estrin, D., Govindan, R., Heidemann, J. (eds.): Special Issue on Embedding the Internet. Communications of the ACM 43 (2000)Google Scholar
  10. 10.
    Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math 16, 1–29 (1968)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Gupta, H.: Selection and Maintenance of Views in a Data Warehouse. PhD thesis, Computer Science Department, Stanford University (1999)Google Scholar
  12. 12.
    Hofmann-Wellenhof, B., Lichtenegger, H., Collins, J.: Global Positioning System: Theory and Practice. Springer, Heidelberg (1997)Google Scholar
  13. 13.
    Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: a scalable and robust communication paradigm for sensor networks. In: MOBICOM 2000 (2000)Google Scholar
  14. 14.
    Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2) (2001)Google Scholar
  15. 15.
    Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM 48(2), 274–296 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Kalpakis, K., Dasgupta, K., Wolfson, O.: Steiner-optimal data replication in tree networks with storage costs. In: Proceedings of IDEAS, pp. 285–293 (2001)Google Scholar
  17. 17.
    Karp, B., Kung, H.T.: GPSR: Greedy perimeter stateless routing for wireless networks. In: MOBICOM 2000 (2000)Google Scholar
  18. 18.
    Krishnan, P., Raz, D., Shavitt, Y.: The cache location problem. IEEE/ACM TON 8, 568–582 (2000)CrossRefGoogle Scholar
  19. 19.
    Li, B., Golin, M.J., Italiano, G.F., Deng, X.: On the optimal placement of web proxies in the internet. In: INFOCOM 1999 (1999)Google Scholar
  20. 20.
    Perkins, C.E., Bhagwat, P.: Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. In: SIGCOMM 1994 (1994)Google Scholar
  21. 21.
    Wattenhofer, R., Li, L., Bahl, P., Wang, Y.-M.: Distributed topology control for wireless muitihop ad-hoc networks. In: INFOCOM 2001 (2001)Google Scholar
  22. 22.
    Xu, J., Li, B., Lee, D.L.: Placement problems for transparent data replication proxy services. IEEE JSAC 20(7), 1383–1397 (2002)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Bin Tang
    • 1
  • Samir Das
    • 1
  • Himanshu Gupta
    • 1
  1. 1.Computer Science DepartmentStony Brook UniversityStony BrookUSA

Personalised recommendations