{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:44:22Z","timestamp":1750308262877,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T00:00:00Z","timestamp":1122854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2005,8]]},"abstract":"<jats:p>\n            In this article, we define the\n            <jats:italic>time-indexing<\/jats:italic>\n            problem as the in-network storage and querying of sensor network data based solely on the time attribute. We argue qualitatively why existing storage schemes may be insufficient as solutions. We then present, analyze, and evaluate novel and lightweight solutions to both the storage and the querying subproblems for time indexing. First, the time-indexed storage problem is formally defined and two formulations are presented seeking to optimize generic utility functions that are derived from concerns about energy, bandwidth usage, and storage balancing. We present and analyze decentralized protocols to solve these formulations and prove the optimality of some of our solutions. Secondly, maintenance and use of simple overlays among rendezvous point nodes in order to enable fault-tolerant and efficient time-indexed queries are discussed. Finally, simulation results are presented to quantify performance characteristics of the protocols, and we find that our proposed scheme has low query overhead that scales with system size and density while exhibiting very good load-balancing and fault-tolerance properties. The use of time-indexed structure is shown to achieve more than double the lifetime of sensor networks compared to existing approaches in some scenarios.\n          <\/jats:p>","DOI":"10.1145\/1077391.1077396","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"101-133","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["A framework for time indexing in sensor networks"],"prefix":"10.1145","volume":"1","author":[{"given":"Guanghui","family":"He","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of Houston, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Indranil","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lui","family":"Sha","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,8]]},"reference":[{"volume-title":"Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN'04)","author":"Abrams Z.","unstructured":"Abrams , Z. , Goe , A. , and Plotkin , S . 2004. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks . In Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN'04) . 10.1145\/984622.984684 Abrams, Z., Goe, A., and Plotkin, S. 2004. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN'04). 10.1145\/984622.984684","key":"e_1_2_1_1_1"},{"unstructured":"Alon N. and Spencer J. H. 1992. The probablistic method. J. Wiley & Sons.  Alon N. and Spencer J. H. 1992. The probablistic method. J. Wiley & Sons.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/JCN.2002.6596929","article-title":"Distributed heuristics for connected dominating set in wireless ad hoc networks","volume":"4","author":"Alzoubi K.","year":"2002","unstructured":"Alzoubi , K. , Wan , P. , and Frieder , O. 2002 . Distributed heuristics for connected dominating set in wireless ad hoc networks . J. Comm. Netw. 4 , 1 (Mar.). Alzoubi, K., Wan, P., and Frieder, O. 2002. Distributed heuristics for connected dominating set in wireless ad hoc networks. J. Comm. Netw. 4, 1 (Mar.).","journal-title":"J. Comm. Netw."},{"doi-asserted-by":"crossref","unstructured":"Athuraliya S. and Low S. H. 2000. Optimization flow control with newton-like algorithm. Telecomm. Syst. 15 3\/4 345--358.  Athuraliya S. and Low S. H. 2000. Optimization flow control with newton-like algorithm. Telecomm. Syst. 15 3\/4 345--358.","key":"e_1_2_1_4_1","DOI":"10.1023\/A:1019155231293"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set covering problem","volume":"4","author":"Chvatal V.","year":"1979","unstructured":"Chvatal , V. 1979 . A greedy heuristic for the set covering problem . Math. Operat. Res. 4 , 3, 233 -- 235 . Chvatal, V. 1979. A greedy heuristic for the set covering problem. Math. Operat. Res. 4, 3, 233--235.","journal-title":"Math. Operat. Res."},{"volume-title":"IEEE International Conference on Communication (ICC'97)","author":"Das B.","unstructured":"Das , B. and Bharghavan , V . 1997. Routing in ad-hoc networks using minimum connected dominating sets . In IEEE International Conference on Communication (ICC'97) , 376--380. Das, B. and Bharghavan, V. 1997. Routing in ad-hoc networks using minimum connected dominating sets. In IEEE International Conference on Communication (ICC'97), 376--380.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of Operating Systems Design and Implementation (OSDI'02)","author":"Elson J.","unstructured":"Elson , J. , Girod , L. , and Estrin , D . 2002. Fine-grained network time synchronization using reference broadcasts . In Proceedings of Operating Systems Design and Implementation (OSDI'02) . 10.1145\/1060289.1060304 Elson, J., Girod, L., and Estrin, D. 2002. Fine-grained network time synchronization using reference broadcasts. In Proceedings of Operating Systems Design and Implementation (OSDI'02). 10.1145\/1060289.1060304","key":"e_1_2_1_8_1"},{"unstructured":"Handy M. J. Haase M. and Timmermann D. 2002. Low energy adaptive clustering hierarchy. Available at http:\/\/www-mtl.mit.edu\/ wendi\/leach\/leach.html.  Handy M. J. Haase M. and Timmermann D. 2002. Low energy adaptive clustering hierarchy. Available at http:\/\/www-mtl.mit.edu\/ wendi\/leach\/leach.html.","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM Press, 89--102","author":"Ganesan D.","unstructured":"Ganesan , D. , Greenstein , B. , Perelyubskiy , D. , Estrin , D. , and Heidemann , J . 2003. An evaluation of multi-resolution storage for sensor networks . In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM Press, 89--102 . 10.1145\/958491.958502 Ganesan, D., Greenstein, B., Perelyubskiy, D., Estrin, D., and Heidemann, J. 2003. An evaluation of multi-resolution storage for sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM Press, 89--102. 10.1145\/958491.958502","key":"e_1_2_1_10_1"},{"doi-asserted-by":"crossref","unstructured":"Ghose A. Grossklags J. and Chuang J. 2003. Resilient data-centric storage in wireless ad-hoc sensor networks. In Mobile Data Management (MDM'03). 45--62.   Ghose A. Grossklags J. and Chuang J. 2003. Resilient data-centric storage in wireless ad-hoc sensor networks. In Mobile Data Management (MDM'03). 45--62.","key":"e_1_2_1_11_1","DOI":"10.1007\/3-540-36389-0_4"},{"volume-title":"IEEE Proceedings of the 1st International Workshop on Sensor Network Protocols and Applications (SNPA'03)","author":"Greenstein B.","unstructured":"Greenstein , B. , Estrin , D. , Govindan , R. , Ratanasamy , S. , and Shenker , S . 2003. Difs: A distributed index for features in sensor networks . In IEEE Proceedings of the 1st International Workshop on Sensor Network Protocols and Applications (SNPA'03) . Greenstein, B., Estrin, D., Govindan, R., Ratanasamy, S., and Shenker, S. 2003. Difs: A distributed index for features in sensor networks. In IEEE Proceedings of the 1st International Workshop on Sensor Network Protocols and Applications (SNPA'03).","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX). 10","author":"Hill J.","unstructured":"Hill , J. , Szewczyk , R. , Woo , A. , Hollar , S. , Culler , D. E. , and Pister , K. S. J. 2000. System architecture directions for networked sensors . In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX). 10 .1145\/378993.379006 Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D. E., and Pister, K. S. J. 2000. System architecture directions for networked sensors. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX). 10.1145\/378993.379006","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of MOBICOM'00","author":"Intanagonwiwat C.","unstructured":"Intanagonwiwat , C. , Govindan , R. , and Estrin , D . 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks . In Proceedings of MOBICOM'00 . 10.1145\/345910.345920 Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of MOBICOM'00. 10.1145\/345910.345920","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the 6th International ACM\/IEEE Conference on Mobile Computing and Networking. 10","author":"Karp B.","unstructured":"Karp , B. and Kung , H. T . 2000. Greedy perimeter stateless routing for wireless networks . In Proceedings of the 6th International ACM\/IEEE Conference on Mobile Computing and Networking. 10 .1145\/345910.345953 Karp, B. and Kung, H. T. 2000. Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th International ACM\/IEEE Conference on Mobile Computing and Networking. 10.1145\/345910.345953","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 22nd ACM International Symposium on the Principles of Distributed Computing (PODC'03)","author":"Kuhn F.","year":"2035","unstructured":"Kuhn , F. , Wattenhofer , R. , Zhang , Y. , and Zollinger , A . 2003. Constant-time distributed dominating set approximation . In Proceedings of the 22nd ACM International Symposium on the Principles of Distributed Computing (PODC'03) . 10.1145\/87 2035 .872040 Kuhn, F., Wattenhofer, R., Zhang, Y., and Zollinger, A. 2003. Constant-time distributed dominating set approximation. In Proceedings of the 22nd ACM International Symposium on the Principles of Distributed Computing (PODC'03). 10.1145\/872035.872040"},{"volume-title":"Proceedings of ACM SenSys'03","author":"Li X.","unstructured":"Li , X. , Kim , Y. J. , Govindan , R. , and Hong , W . 2003. Multi-dimensional range queries in sensor networks . In Proceedings of ACM SenSys'03 . 10.1145\/958491.958500 Li, X., Kim, Y. J., Govindan, R., and Hong, W. 2003. Multi-dimensional range queries in sensor networks. In Proceedings of ACM SenSys'03. 10.1145\/958491.958500","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1109\/90.811451"},{"volume-title":"Proceedings of Operating Systems Design and Implementation (OSDI'02)","author":"Madden S.","unstructured":"Madden , S. , Franklin , M. J. , Hellerstein , J. M. , and Hong , W . 2002. Tag: A tiny aggregation service for ad-hoc sensor networks . In Proceedings of Operating Systems Design and Implementation (OSDI'02) . 10.1145\/1060289.1060303 Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2002. Tag: A tiny aggregation service for ad-hoc sensor networks. In Proceedings of Operating Systems Design and Implementation (OSDI'02). 10.1145\/1060289.1060303","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of IEEE INFOCOM'99","author":"Massoulie L.","unstructured":"Massoulie , L. and Roberts , J . 1999. Bandwidth sharing: objectives and algorithms . In Proceedings of IEEE INFOCOM'99 . Massoulie, L. and Roberts, J. 1999. Bandwidth sharing: objectives and algorithms. In Proceedings of IEEE INFOCOM'99.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of ACM SenSys'03","author":"Newsome J.","unstructured":"Newsome , J. and Song , D . 2003. Gem: Graph embedding for routing and data-centric storage in sensor networks without geographic information . In Proceedings of ACM SenSys'03 . 10.1145\/958491.958501 Newsome, J. and Song, D. 2003. Gem: Graph embedding for routing and data-centric storage in sensor networks without geographic information. In Proceedings of ACM SenSys'03. 10.1145\/958491.958501","key":"e_1_2_1_21_1"},{"volume-title":"Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis","author":"Polastre J.","unstructured":"Polastre , J. 2003. Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis , University of California at Berkeley . Polastre, J. 2003. Design and implementation of wireless sensor networks for habitat monitoring. Master's Thesis, University of California at Berkeley.","key":"e_1_2_1_22_1"},{"volume-title":"the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02)","author":"Ratnasamy S.","unstructured":"Ratnasamy , S. , Karp , B. , Yin , L. , Yu , F. , Estrin , D. , Govindan , R. , and Shenker , S . 2002. GHT: A geographic hash table for data-centric storage in sensornets . In the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02) (Sept.). Atlanta, GA. 10.1145\/570738.570750 Ratnasamy, S., Karp, B., Yin, L., Yu, F., Estrin, D., Govindan, R., and Shenker, S. 2002. GHT: A geographic hash table for data-centric storage in sensornets. In the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02) (Sept.). Atlanta, GA. 10.1145\/570738.570750","key":"e_1_2_1_23_1"},{"unstructured":"Ratnasamy S. Karp B. Yin L. Yu F. Estrin D. Govindan R. and Shenker S. 2003. Data-centric storage in sensornets with ght a geographic hash table. In Mobile Networks and Applications (MONET'03) Special Issue on Wireless Sensor Networks. 10.1023\/A:1024591915518   Ratnasamy S. Karp B. Yin L. Yu F. Estrin D. Govindan R. and Shenker S. 2003. Data-centric storage in sensornets with ght a geographic hash table. In Mobile Networks and Applications (MONET'03) Special Issue on Wireless Sensor Networks. 10.1023\/A:1024591915518","key":"e_1_2_1_24_1"},{"volume-title":"the 1st ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets'02)","author":"Shenker S.","unstructured":"Shenker , S. , Ratnasamy , S. , Karp , R. G. B. , and Estrin , D . 2002. Data-centric storage in sensornets . In the 1st ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets'02) (Oct). Shenker, S., Ratnasamy, S., Karp, R. G. B., and Estrin, D. 2002. Data-centric storage in sensornets. In the 1st ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets'02) (Oct).","key":"e_1_2_1_25_1"},{"volume-title":"INFOCOM'99","author":"Sinha P.","unstructured":"Sinha , P. , Sivakumar , R. , and Bharghavan , V . 1999. CEDAR: a core-extraction distributed ad hoc routing algorithm . In INFOCOM'99 . 202--209. Sinha, P., Sivakumar, R., and Bharghavan, V. 1999. CEDAR: a core-extraction distributed ad hoc routing algorithm. In INFOCOM'99. 202--209.","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'03)","author":"Zheng R.","unstructured":"Zheng , R. , Hou , J. C. , and Sha , L . 2003. Asynchronous wakeup for ad hoc networks . In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'03) . 10.1145\/778415.778420 Zheng, R., Hou, J. C., and Sha, L. 2003. Asynchronous wakeup for ad hoc networks. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'03). 10.1145\/778415.778420","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03)","author":"Zheng R.","unstructured":"Zheng , R. and Kravets , R . 2003. On-demand power management for ad hoc network . In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03) . Zheng, R. and Kravets, R. 2003. On-demand power management for ad hoc network. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03).","key":"e_1_2_1_28_1"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077391.1077396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1077391.1077396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:51Z","timestamp":1750267431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077391.1077396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1145\/1077391.1077396"],"URL":"https:\/\/doi.org\/10.1145\/1077391.1077396","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2005,8]]},"assertion":[{"value":"2005-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}