{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T08:33:36Z","timestamp":1672562016045},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,5,6]],"date-time":"2014-05-06T00:00:00Z","timestamp":1399334400000},"content-version":"vor","delay-in-days":35,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Science and Technology 863 Key Project No. 2011AA010500"},{"name":"Fundamental Research Funds for the Central Universities","award":["2012QN078"]},{"name":"Youth Innovation Promotion Association, Chinese Academy of Sciences"},{"name":"National Natural Science Foundation of Hubei Province","award":["2011CDB044"]},{"name":"Fok Ying Tung Education Foundation","award":["132036"]},{"name":"Hong Kong Scholars Program","award":["XJ2012019"]},{"name":"Microsoft Research Asia","award":["60933012"]},{"name":"Program for New Century Excellent Talents in University","award":["NCET-10-408 (State Education Ministry)"]},{"name":"NSFC","award":["61103243"]},{"name":"Scientific Research Foundation for the Returned Overseas Chinese Scholars (State Education Ministry)"},{"name":"National Natural Science Foundation of China","award":["61073147, 61173120, 61103243, 61202460, 61271226, and 61272410"]},{"name":"Shenzhen Overseas High-level Talents Innovation and Entrepreneurship Funds KQC201109050097A"},{"name":"CHUTIAN scholar Project of Hubei Province"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2014,4]]},"abstract":"\n When a sensor network grows large, or when its topology becomes complex (e.g., containing many holes), network algorithms designed with a smaller or simpler setting in mind may be rendered rather inefficient. We propose to address this problem using a divide and conquer approach: the network is divided into convex pieces by a distributed\n convex partitioning<\/jats:italic>\n protocol, using connectivity information only. A convex network partition exhibits some desirable properties that allow traditional algorithms to work to their full advantage. Based on this, we can achieve relatively high performance for an algorithm by combining algorithmic actions within individual partitions. We consider two important applications: virtual-coordinate-based geographic routing and connectivity-based localization. The former benefits from convex partition's friendliness to network embedding, which is crucial to generating accurate virtual coordinates for the nodes, while the latter leverages the fact that shortest paths are largely straight for node pairs within a convex partition. Experimental results show that the convex partition approach can significantly improve the performance of both applications in comparison with state-of-the-art solutions.\n <\/jats:p>","DOI":"10.1145\/2594772","type":"journal-article","created":{"date-parts":[[2014,5,13]],"date-time":"2014-05-13T12:18:28Z","timestamp":1399983508000},"page":"1-23","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Convex Partitioning of Large-Scale Sensor Networks in Complex Fields"],"prefix":"10.1145","volume":"10","author":[{"given":"Guang","family":"Tan","sequence":"first","affiliation":[{"name":"SIAT, Chinese Academy of Sciences, China"}]},{"given":"Hongbo","family":"Jiang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"given":"Jun","family":"Liu","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}]},{"given":"Anne-Marie","family":"Kermarrec","sequence":"additional","affiliation":[{"name":"INRIA\/IRISA, Rennes France"}]}],"member":"320","published-online":{"date-parts":[[2014,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132908"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11502593_33"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080829.1080839"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.8"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of IEEE INFOCOM.","author":"Caruso A.","unstructured":"A. Caruso , A. Urpi , S. Chessa , and S. De . 2005. GPS free coordinate assignment and routing in wireless sensor networks . In Proceedings of IEEE INFOCOM. A. Caruso, A. Urpi, S. Chessa, and S. De. 2005. GPS free coordinate assignment and routing in wireless sensor networks. In Proceedings of IEEE INFOCOM."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015471"},{"key":"e_1_2_1_7_1","volume-title":"GLIDER: Gradient landmark-based distributed routing for sensor networks","author":"Fang Q.","year":"2005","unstructured":"Q. Fang , J. Gao , L. Guibas , V. de Silva , and L. Zhang . 2005 . GLIDER: Gradient landmark-based distributed routing for sensor networks . In Proceedings of IEEE INFOCOM. Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. 2005. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proceedings of IEEE INFOCOM."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of Algorithmic Aspects of Wireless Sensor Networks: First International Workshop (ALGOSENSOR).","author":"Fekete S. P.","unstructured":"S. P. Fekete , A. Kroeller , D. Pfisterer , S. Fischer , and C. Buschmann . 2004. Neighborhood-based topology recognition in sensor networks . In Proceedings of Algorithmic Aspects of Wireless Sensor Networks: First International Workshop (ALGOSENSOR). S. P. Fekete, A. Kroeller, D. Pfisterer, S. Fischer, and C. Buschmann. 2004. Neighborhood-based topology recognition in sensor networks. In Proceedings of Algorithmic Aspects of Wireless Sensor Networks: First International Workshop (ALGOSENSOR)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of USENIX NSDI.","author":"Fonseca R.","unstructured":"R. Fonseca , S. Ratnasamy , J. Zhao , C. T. Ee , D. Culler , S. Shenker , and I. Stoica . 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets . In Proceedings of USENIX NSDI. R. Fonseca, S. Ratnasamy, J. Zhao, C. T. Ee, D. Culler, S. Shenker, and I. Stoica. 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of USENIX NSDI."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080810.1080819"},{"key":"e_1_2_1_11_1","volume-title":"CONSEL: Connectivity-based segmentation in large-scale 2D\/3D sensor networks","author":"Jiang H.","year":"2012","unstructured":"H. Jiang , T. Yu , C. Tian , G. Tan , and C. Wang . 2012 . CONSEL: Connectivity-based segmentation in large-scale 2D\/3D sensor networks . In Proceedings of IEEE INFOCOM. H. Jiang, T. Yu, C. Tian, G. Tan, and C. Wang. 2012. CONSEL: Connectivity-based segmentation in large-scale 2D\/3D sensor networks. In Proceedings of IEEE INFOCOM."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345953"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of ACM-SIAM SODA.","author":"Kroller A.","unstructured":"A. Kroller , S. Fekete , D. Pfisterer , and S. Fischer . 2006. Deterministic boundary recognition and topology extraction for large sensor networks . In Proceedings of ACM-SIAM SODA. A. Kroller, S. Fekete, D. Pfisterer, and S. Fischer. 2006. Deterministic boundary recognition and topology extraction for large sensor networks. In Proceedings of ACM-SIAM SODA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872044"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/570810.570814"},{"key":"e_1_2_1_16_1","volume":"200","author":"Lederer S.","unstructured":"S. Lederer , Y. Wang , and J. Gao. 200 8. Connectivity-based localization of large scale sensor networks with complex shape. In Proceedings of IEEE INFOCOM. S. Lederer, Y. Wang, and J. Gao. 2008. Connectivity-based localization of large scale sensor networks with complex shape. In Proceedings of IEEE INFOCOM.","journal-title":"J. Gao."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of IEEE ICNP.","author":"Leong B.","unstructured":"B. Leong , B. Liskov , and R. Morris . 2007. Greedy virtual coordinates for geographic routing . In Proceedings of IEEE ICNP. B. Leong, B. Liskov, and R. Morris. 2007. Greedy virtual coordinates for geographic routing. In Proceedings of IEEE ICNP."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287853.1287861"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997823"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646236.682869"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of IEEE INFOCOM.","author":"Liu W.","unstructured":"W. Liu , D. Wang , H. Jiang , W. Liu , and C. Wang . 2012. Approximate convex decomposition based localization in wireless sensor networks . In Proceedings of IEEE INFOCOM. W. Liu, D. Wang, H. Jiang, W. Liu, and C. Wang. 2012. Approximate convex decomposition based localization in wireless sensor networks. In Proceedings of IEEE INFOCOM."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of Shape Modeling International.","author":"Lu Y.","unstructured":"Y. Lu , J.-M. Lien , M. Ghosh , and N. Amato . 2012. Alpha-decomposition of polygons . In Proceedings of Shape Modeling International. Y. Lu, J.-M. Lien, M. Ghosh, and N. Amato. 2012. Alpha-decomposition of polygons. In Proceedings of Shape Modeling International."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958501"},{"key":"e_1_2_1_24_1","volume":"200","author":"Nguyeny A.","unstructured":"A. Nguyeny , N. Milosavljevic , Q Fang , J. Gao , and L. J. Guibas. 200 8. Landmark selection and greedy landmark-descent routing for sensor networks. In Proceedings of IEEE INFOCOM. A. Nguyeny, N. Milosavljevic, Q Fang, J. Gao, and L. J. Guibas. 2008. Landmark selection and greedy landmark-descent routing for sensor networks. In Proceedings of IEEE INFOCOM.","journal-title":"J. Guibas."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/938985.938996"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126256"},{"key":"e_1_2_1_27_1","volume":"200","author":"Sack J.-R.","unstructured":"J.-R. Sack and J. Urrutia. 200 0. Handbook of Computational Geometry. Elsevier Science Publishers, B. V. North-Holland, Amsterdam. J.-R. Sack and J. Urrutia. 2000. Handbook of Computational Geometry. Elsevier Science Publishers, B. V. North-Holland, Amsterdam.","journal-title":"J. Urrutia."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of IEEE INFOCOM.","author":"Shang Y.","unstructured":"Y. Shang and W. Ruml . 2004. Improved MDS-based localization . In Proceedings of IEEE INFOCOM. Y. Shang and W. Ruml. 2004. Improved MDS-based localization. In Proceedings of IEEE INFOCOM."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/778415.778439"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of IEEE INFOCOM.","author":"Tsai M.","unstructured":"M. Tsai , H. Yang , and W. Huang . 2008. Axis-based virtual coordinate assignment protocol and delivery-guaranteed routing protocol in wireless sensor networks . In Proceedings of IEEE INFOCOM. M. Tsai, H. Yang, and W. Huang. 2008. Axis-based virtual coordinate assignment protocol and delivery-guaranteed routing protocol in wireless sensor networks. In Proceedings of IEEE INFOCOM."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1161089.1161104"},{"key":"e_1_2_1_32_1","volume":"200","author":"Wang Y.","unstructured":"Y. Wang , S. Lederer , and J. Gao. 200 9. Connectivity-based sensor network localization with incremental delaunay refinement method. In Proceedings of IEEE INFOCOM. Y. Wang, S. Lederer, and J. Gao. 2009. Connectivity-based sensor network localization with incremental delaunay refinement method. In Proceedings of IEEE INFOCOM.","journal-title":"J. Gao."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2005.13"},{"key":"e_1_2_1_34_1","volume":"200","author":"Zhu X.","unstructured":"X. Zhu , R. Sarkar , and J. Gao. 200 8. Shape segmentation and applications in sensor networks. In Proceedings of IEEE INFOCOM. X. Zhu, R. Sarkar, and J. Gao. 2008. Shape segmentation and applications in sensor networks. In Proceedings of IEEE INFOCOM.","journal-title":"J. Gao."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2594772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T21:03:50Z","timestamp":1672434230000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594772"}},"subtitle":["Algorithms and Applications"],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["10.1145\/2594772"],"URL":"https:\/\/doi.org\/10.1145\/2594772","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
