{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:29Z","timestamp":1750307729746,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-064387"],"award-info":[{"award-number":["CNS-064387"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>The diversity of the deployment settings of sensor networks is naturally inherited from the diversity of geographical features of the embedded environment, and greatly influences network design. Many sensor network protocols in the literature implicitly assume that sensor nodes are deployed inside a simple geometric region, without considering possible obstacles and holes in the deployment environment. When the real deployment setting deviates from that, we often observe degraded performance. Thus, it is highly desirable to have a generic approach to handle sensor fields with complex shapes. In this article, we propose a segmentation algorithm that partitions an irregular sensor field into nicely shaped pieces such that algorithms and protocols that assume a nice sensor field can be applied inside each piece. Across the segments, problem dependent structures specify how the segments and data collected in these segments are integrated. Our segmentation algorithm does not require any extra knowledge (e.g., sensor locations) and only uses network connectivity information. This unified spatial-partitioning approach makes the protocol design become flexible and independent of deployment specifics. Existing protocols are still reusable with segmentation, and the development of new topology-adaptive protocols becomes much easier. We verified the correctness of the algorithm on various topologies and evaluated the performance improvements by integrating shape segmentation with several fundamental problems in network design.<\/jats:p>","DOI":"10.1145\/1498915.1498918","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Segmenting a sensor field"],"prefix":"10.1145","volume":"5","author":[{"given":"Xianjin","family":"Zhu","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rik","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Gao","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2004.1368893"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052199.1052206"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012319418150"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080829.1080839"},{"volume-title":"Proceedings of the International Conference on Network Protocols (ICNP). 271--282","author":"Chandra R.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1997.181.57"},{"volume-title":"Proceedings of Workshop on Algorithms and Data Structures (WADS). 25--36","author":"Dey T. K.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). 111--117","author":"Dimakis A. G.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127791"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Elson J. 2003. Time synchronization in wireless sensor networks. Ph.D. thesis University of California Los Angeles.   Elson J. 2003. Time synchronization in wireless sensor networks. Ph.D. thesis University of California Los Angeles.","DOI":"10.1145\/774763.774787"},{"volume":"1","volume-title":"Proceedings of the 24th Conference of the IEEE Communication Society (INFOCOM).","author":"Fang Q.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the 25th Conference of the IEEE Communication Society (INFOCOM). 1--12","author":"Fang Q.","key":"e_1_2_1_12_1"},{"volume":"3121","volume-title":"ALGOSENSORS. Lecture Notes in Computer Science","author":"Fekete S. P.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080810.1080819"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137911"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 958--967","author":"Funke S.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958508"},{"volume-title":"Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications. 163--173","author":"Greenstein B.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383282"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345953"},{"volume-title":"Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 1000--1009","author":"Kr\u00f6ller A.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872044"},{"volume-title":"Proceedings of the 4th International Workshop Visual Form. 216--228","author":"Leymarie F. F.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958500"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/781606.781620"},{"volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281--297","year":"1967","author":"MacQueen J. B.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570750"},{"volume-title":"Proceedings of the International Conference on Computer Vision (ICCV). 755--762","author":"Sebastian T.","key":"e_1_2_1_28_1"},{"volume-title":"Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON). 512--519","author":"Shi Y.","key":"e_1_2_1_29_1"},{"volume-title":"Proceedings of the International Conference on Computer Vision (ICCV). 222--229","author":"Siddiqi K.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127802"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1161089.1161104"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498915.1498918","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498915.1498918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:39Z","timestamp":1750253919000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498915.1498918"}},"subtitle":["Algorithms and applications in network design"],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1498915.1498918"],"URL":"https:\/\/doi.org\/10.1145\/1498915.1498918","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}