Scaling laws for data-centric storage and querying in wireless sensor networks

ABSTRACT

We use a constrained optimization framework to derive scaling laws for data-centric storage and querying in wireless sensor networks. We consider both unstructured sensor networks, which use blind sequential search for querying, and structured sensor networks, which use efficient hash-based querying. We find that the scalability of a sensor network's performance depends upon whether the increase in energy and storage resources with more nodes is outweighed by the concomitant application-specific increase in event and query loads. We derive conditions that determine: 1) whether the energy requirement per node grows without bound with the network size for a fixed-duration deployment, 2) whether there exists a maximum network size that can be operated for a specified duration on a fixed energy budget, and 3) whether the network lifetime increases or decreases with the size of the network for a fixed energy budget. An interesting finding of this work is that three-dimensional (3D) uniform deployments are inherently more scalable than two-dimensional (2D) uniform deployments, which in turn are more scalable than one-dimensional (1D) uniform deployments.

REFERENCES

• 1: Ramesh Govindan, Data-centric routing and storage in sensor networks, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
• 2: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 3: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, Mar. 2000.
• 4: P. Gupta and P. R. Kumar, "Internets in the sky: Capacity of 3D wireless networks," in Proc. 39th IEEE Conf. Decision and Control, 2000, vol. 3, pp. 2290-2295.
• 5: L.-L. Xie and P. R. Kumar, "A network information theory for wireless communication: Scaling laws and optimal operation," IEEE Trans. Inf. Theory, vol. 50, no. 5, pp. 748-767, May 2004.
• 6: O. Leveque and I. E. Telatar, "Information-theoretic upper bounds on the capacity of large extended ad hoc wireless networks," IEEE Trans. Inf. Theory, vol. 51, no. 3, pp. 858-865, Mar. 2005.
• 7: O. Leveque and E. Preissmann, "Scaling laws for one-dimensional ad hoc wireless networks," IEEE Trans. Inf. Theory, vol. 51, no. 11, pp. 3987-3991, Nov. 2005.
• 8: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 9: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 10: W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application- specific protocol architecture for wireless microsensor networks," Wireless Commun., vol. 1, no. 4, pp. 660-670, Oct. 2002.
• 11: O. Younis and S. Fahmy, "Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach," in Proc. 23rd IEEE INFOCOM , Mar. 7-11, 2004, vol. 1, pp. 640-640.
• 12: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023746]
• 13: Z. Hu and B. Li, "Fundamental performance limits of wireless sensor networks," in Ad Hoc and Sensor Networks, Y. Xiao and Y. Pan, Eds. Commack, NY: Nova, 2004.
• 14: M. Bhardwaj and A. P. Chandrakasan, "Bounding the lifetime of sensor networks via optimal role assignments," in Proc. IEEE INFOCOM, New York, Jun. 2002, online.
• 15: Jae-Hwan Chang , Leandros Tassiulas, Maximum lifetime routing in wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.609-619, August 2004 [doi>10.1109/TNET.2004.833122]
• 16: Konstantinos Kalpakis , Koustuv Dasgupta , Parag Namjoshi, Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.6, p.697-716, 21 August 2003 [doi>10.1016/S1389-1286(03)00212-3]
• 17: Scott Shenker , Sylvia Ratnasamy , Brad Karp , Ramesh Govindan , Deborah Estrin, Data-centric storage in sensornets, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.137-142, January 2003 [doi>10.1145/774763.774785]
• 18: N. Trigoni, Y. Yao, A. Demers, J. Gehrke, and R. Rajaraman, "Hybrid push-pull query processing for sensor networks," in Proc. GI-Conf. Informatik, Workshop on Sensor Netw., Berlin, Germany, Sep. 2004, pp. 370-374.
• 19: S. Shakkottai, "Asymptotics of query strategies over a sensor network," in IEEE INFOCOM, Mar. 2004, online.
• 20: Xin Liu , Qingfeng Huang , Ying Zhang, Combs, needles, haystacks: balancing push and pull for discovery in large-scale sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031510]
• 21: M. D. Penrose, "The longest edge or the random minimal spanning tree," Ann. Appl. Probability, vol. 7, pp. 340-361, 1997.
• 22: M. D. Penrose, "A strong law for the longest edge of the minimal spanning tree," Ann. Probability, vol. 27, pp. 246-260, 1999.
• 23: P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," in Stochastic Analysis, Control, Optimization and Applications, W. H. Fleming, W. M. McEneany, G. Yin, and Q. Zhang, Eds. Boston, MA: Birkhauser, 1998, p. 547.566.
• 24: Nicholas Chang , Mingyan Liu, Revisiting the TTL-based controlled flooding search: optimality and randomization, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023730]
• 25: M. Chu, H. Haussecker, and F. Zhao, "Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks," Int. J. High Perform. Comput. Appl., vol. 16, no. 3, pp. 293-313, Aug. 2002.
• 26: B. Krishnamachari and J. Ahn, "Optimizing data replication for expanding ring-based queries in wireless sensor networks," in Proc. WIOPT, Boston, MA, Apr. 2006, pp. 1-10.
• 27: S. Kapadia and B. Krishnamachari, "Comparative analysis of push-pull query strategies for wireless sensor networks," in Proc. DCOSS, Jun. 2006, pp. 185-201.
• 28: H. Robbins, "Remark of Stirling's formula," Amer. Math., Monthly 62, pp. 26-29, 1955.
• 29: J. Ahn and B. Krishnamachari, "Modeling search costs in wireless sensor networks," [Online]. Available: http://ceng.usc.edu/~bkrishna Workshop paper, to be published.
• 30: M. Imase and B. M. Waxman, "Dynamic Steiner tree problem," SIAM J. Discrete Math., vol. 4, pp. 369-369, 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Management, Performance

Keywords:
energy efficiency, modeling, performance analysis, querying, scalability, wireless sensor networks