{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:47Z","timestamp":1760243267785,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T00:00:00Z","timestamp":1400112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>With both computational complexity and storage space bounded by a small constant, greedy routing is recognized as an appealing approach to support scalable routing in wireless sensor networks. However, significant challenges have been encountered in extending greedy routing from 2D to 3D space. In this research, we develop decentralized solutions to achieve greedy routing in 3D sensor networks. Our proposed approach is based on a unit tetrahedron cell (UTC) mesh structure. We propose a distributed algorithm to realize volumetric harmonic mapping (VHM) of the UTC mesh under spherical boundary condition. It is a one-to-one map that yields virtual coordinates for each node in the network without or with one internal hole. Since a boundary has been mapped to a sphere, node-based greedy routing is always successful thereon. At the same time, we exploit the UTC mesh to develop a face-based greedy routing algorithm and prove its success at internal nodes. To deliver a data packet to its destination, face-based and node-based greedy routing algorithms are employed alternately at internal and boundary UTCs, respectively. For networks with multiple internal holes, a segmentation and tunnel-based routing strategy is proposed on top of VHM to support global end-to-end routing. As far as we know, this is the first work that realizes truly deterministic routing with constant-bounded storage and computation in general 3D wireless sensor networks.<\/jats:p>","DOI":"10.3390\/axioms3020177","type":"journal-article","created":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T11:05:15Z","timestamp":1400151915000},"page":"177-201","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Deterministic Greedy Routing with Guaranteed Delivery in 3D Wireless Sensor Networks"],"prefix":"10.3390","volume":"3","author":[{"given":"Su","family":"Xia","sequence":"first","affiliation":[{"name":"Cisco Systems, Milpitas, CA 95035, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaotian","family":"Yin","sequence":"additional","affiliation":[{"name":"Mathematics Department, Harvard University, Cambridge, MA 02138, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongyi","family":"Wu","sequence":"additional","affiliation":[{"name":"The Center for Advanced Computer Studies, University of Louisiana, Lafayette, LA 70504, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miao","family":"Jin","sequence":"additional","affiliation":[{"name":"The Center for Advanced Computer Studies, University of Louisiana, Lafayette, LA 70504, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianfeng","family":"Gu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stony Brook University, Stony Brook, NY 11790, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,5,15]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Bai, X., Zhang, C., Xuan, D., Teng, J., and Jia, W. (2009, January 18\u201321). Low-connectivity and full-coverage three dimensional networks. Proceedings of the MobiHOC, New Orleans, LA, USA.","key":"ref_1","DOI":"10.1145\/1530748.1530768"},{"doi-asserted-by":"crossref","unstructured":"Bai, X., Zhang, C., Xuan, D., and Jia, W. (2009, January 19\u201325). Full-coverage and K-connectivity (K = 14, 6) three dimensional networks. Proceedings of the INFOCOM, Rio de Janeiro, Brazil.","key":"ref_2","DOI":"10.1109\/INFCOM.2009.5061943"},{"doi-asserted-by":"crossref","unstructured":"Liu, C., and Wu, J. (2009, January 19\u201325). Efficient geometric routing in three dimensional ad hoc networks. Proceedings of INFOCOM, Rio de Janeiro, Brazil.","key":"ref_3","DOI":"10.1109\/INFCOM.2009.5062225"},{"unstructured":"Kao, T.F.G., and Opatmy, J. (2005, January 10\u201312). Position-based routing on 3D geometric graphs in mobile ad hoc networks. Proceedings of the 17th Canadian Conference on Computational Geometry, Windsor, ON, Canada.","key":"ref_4"},{"unstructured":"Opatrny, J., Abdallah, A., and Fevens, T. (, January July). Randomized 3D position-based routing algorithms for ad-hoc networks. Proceedings of the Third Annual International Conference on Mobile and Ubiquitous Systems: Networking & Services, San Jose, CA, USA.","key":"ref_5"},{"doi-asserted-by":"crossref","unstructured":"Flury, R., and Wattenhofer, R. (2008, January 13\u201318). Randomized 3D geographic routing. Proceedings of the INFOCOM, Phoenix, AZ, USA.","key":"ref_6","DOI":"10.1109\/INFOCOM.2008.135"},{"doi-asserted-by":"crossref","unstructured":"Li, F., Chen, S., Wang, Y., and Chen, J. (2008, January 19\u201323). Load balancing routing in three dimensional wireless networks. Proceedings of the ICC, Beijing, China.","key":"ref_7","DOI":"10.1109\/ICC.2008.578"},{"doi-asserted-by":"crossref","unstructured":"Zhou, J., Chen, Y., Leong, B., and Sundar, P. (2010, January 3\u20135). Practical 3D geographic routing for wireless sensor networks. Proceedings of the SenSys, Zurich, Switzerland.","key":"ref_8","DOI":"10.1145\/1869983.1870016"},{"doi-asserted-by":"crossref","unstructured":"Pompili, D., Melodia, T., and Akyildiz, I.F. (2006, January 23\u201329). Routing algorithms for delay-insensitive and delay-sensitive applications in underwater sensor networks. Proceedings of the MobiCom, Los Angeles, CA, USA.","key":"ref_9","DOI":"10.1145\/1161089.1161123"},{"doi-asserted-by":"crossref","unstructured":"Cheng, W., Teymorian, A.Y., Ma, L., Cheng, X., Lu, X., and Lu, Z. (2008, January 13\u201318). Underwater Localization in Sparse 3D Acoustic Sensor Networks. Proceedings of the INFOCOM, Phoenix, AZ, USA.","key":"ref_10","DOI":"10.1109\/INFOCOM.2008.56"},{"doi-asserted-by":"crossref","unstructured":"Allred, J., Hasan, A.B., Panichsakul, S., Pisano, W., Gray, P., Huang, J., Han, R., Lawrence, D., and Mohseni, K. (2007, January 6\u20139). SensorFlock: An airborne wireless sensor network of micro-air vehicles. Proceedings of the SenSys, Sydney, NSW, Australia.","key":"ref_11","DOI":"10.1145\/1322263.1322275"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/MNET.2006.1637927","article-title":"Challenges: Building scalable mobile underwater wireless sensor networks for aquatic applications","volume":"20","author":"Cui","year":"2006","journal-title":"IEEE Netw."},{"unstructured":"Bose, P., Morin, P., Stojmenovic, I., and Urrutia, J. (1999, January 20). Routing with guaranteed delivery in ad hoc wireless networks. Proceedings of the Third Workshop Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, WA, USA.","key":"ref_13"},{"doi-asserted-by":"crossref","unstructured":"Karp, B., and Kung, H. (2001, January 16\u201321). GPSR: Greedy perimeter stateless routing for wireless networks. Proceedings of the MobiCom, Rome, Italy.","key":"ref_14","DOI":"10.1145\/345910.345953"},{"unstructured":"Kranakis, E., Singh, H., and Urrutia, J. (1999, January 15\u201318). Compass routing on geometric networks. Proceedings of the Canadian Conference on Computational Geometry (CCCG), Vancouver, BC, Canada.","key":"ref_15"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zhang, Y., and Zollinger, A. (2003, January 13\u201316). Geometric ad-hoc routing: Theory and practice. Proceedings of the 22nd ACM Symposium on the Principles of Distributed Computing, Boston, MA, USA.","key":"ref_16","DOI":"10.1145\/872035.872044"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., and Zollinger, A. (2003, January 1\u20133). Worst-case optimal and average-case efficient geometric ad-hoc routing. Proceedings of the MobiHOC, Annapolis, MD, USA.","key":"ref_17","DOI":"10.1145\/778415.778447"},{"unstructured":"Mitra, B.L.S., and Liskov, B. (2005, January 6\u20139). Path vector face routing: Geographic routing with local face information. Proceedings of the ICNP, Boston, MA, USA.","key":"ref_18"},{"doi-asserted-by":"crossref","unstructured":"Frey, H., and Stojmenovic, I. (2006, January 23\u201329). On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks. Proceedings of the MobiCom, Los Angeles, CA, USA.","key":"ref_19","DOI":"10.1145\/1161089.1161133"},{"doi-asserted-by":"crossref","unstructured":"Tan, G., Bertier, M., and Kermarrec, A.M. (2009, January 19\u201325). Visibility-graph-based shortest-path geographic routing in sensor networks. Proceedings of the INFOCOM, Rio de Janeiro, Brazil.","key":"ref_20","DOI":"10.1109\/INFCOM.2009.5062091"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2005.06.022","article-title":"On a conjecture related to geometric routing","volume":"344","author":"Papadimitriou","year":"2005","journal-title":"Theor. Comput. Sci."},{"unstructured":"Angelini, P., Frati, F., and Grilli, L. (2008, January 21\u201324). An algorithm to construct greedy drawings of triangulations. Proceedings of the 16th International Symposium on Graph Drawing, Heraklion, Crete, Greece.","key":"ref_22"},{"unstructured":"Leighton, T., and Moitra, A. (2008, January 25\u201328). Some results on greedy embeddings in metric spaces. Proceedings of the 49th IEEE Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA.","key":"ref_23"},{"doi-asserted-by":"crossref","unstructured":"Kleinberg, R. (2007, January 6\u201312). Geographic routing using hyperbolic space. Proceedings of the INFOCOM, Anchorage, AK, USA.","key":"ref_24","DOI":"10.1109\/INFCOM.2007.221"},{"doi-asserted-by":"crossref","unstructured":"Cvetkovski, A., and Crovella, M. (2009, January 19\u201325). Hyperbolic embedding and routing for dynamic graphs. Proceedings of the INFOCOM, Rio de Janeiro, Brazil.","key":"ref_25","DOI":"10.1109\/INFCOM.2009.5062083"},{"unstructured":"Sarkar, R., Yin, X., Gao, J., Luo, F., and Gu, X.D. (2009, January 13\u201316). Greedy routing with guaranteed delivery using ricci flows. Proceedings of the IPSN, San Francisco, CA, USA.","key":"ref_26"},{"doi-asserted-by":"crossref","unstructured":"Flury, R., Pemmaraju, S., and Wattenhofer, R. (2009, January 19\u201325). Greedy routing with bounded stretch. Proceedings of the INFOCOM, Rio de Janeiro, Brazil.","key":"ref_27","DOI":"10.1109\/INFCOM.2009.5062093"},{"unstructured":"Durocher, S., Kirkpatrick, D., and Narayanan, L. (2008, January 5\u20138). On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Proceedings of the International Conference on Distributed Computing and Networking, Kolkata, India.","key":"ref_28"},{"doi-asserted-by":"crossref","unstructured":"Zhou, H., Xia, S., Jin, M., and Wu, H. (2010, January 21\u201325). Localized algorithm for precise boundary detection in 3D wireless networks. Proceedings of the ICDCS, Genoa, Italy.","key":"ref_29","DOI":"10.1109\/ICDCS.2010.40"},{"doi-asserted-by":"crossref","unstructured":"Zhong, Z., and He, T. (2007, January 6\u20139). MSP: Multi-sequence positioning of wireless sensor nodes. Proceedings of the SenSys, Sydney, NSW, Australia.","key":"ref_30","DOI":"10.1145\/1322263.1322266"},{"doi-asserted-by":"crossref","unstructured":"Giorgetti, G., Gupta, S., and Manes, G. (2007, January 25\u201327). Wireless localization using self-organizing maps. Proceedings of the IPSN, Cambridge, MA, USA.","key":"ref_31","DOI":"10.1145\/1236360.1236399"},{"doi-asserted-by":"crossref","unstructured":"Li, L., and Kunz, T. (2007, January 28\u201330). Localization applying an efficient neural network mapping. Proceedings of the Int\u2019l Conference on Autonomic Computing and Communication Systems, Rome, Italy.","key":"ref_32","DOI":"10.4108\/ICST.AUTONOMICS2007.2126"},{"doi-asserted-by":"crossref","unstructured":"Shang, Y., Ruml, W., Zhang, Y., and Fromherz, M.P.J. (2003, January 1\u20133). Localization from mere connectivity. Proceedings of the MobiHOC, Annapolis, MD, USA.","key":"ref_33","DOI":"10.1145\/778415.778439"},{"unstructured":"Shang, Y., and Ruml, W. (2004, January 7\u201311). Improved MDS-based localization. Proceedings of the INFOCOM, Hong Kong, China.","key":"ref_34"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"191","DOI":"10.4310\/CIS.2003.v3.n3.a4","article-title":"Volumetric harmonic map","volume":"3","author":"Gu","year":"2003","journal-title":"Commun. Inf. Syst."},{"doi-asserted-by":"crossref","unstructured":"Wan, S., Ye, T., Li, M., Zhang, H., and Li, X. (2012, January 8\u201310). Efficient spherical parametrization using progressive optimization. Proceedings of the First International Conference on Computational Visual Media, Beijing, China.","key":"ref_36","DOI":"10.1007\/978-3-642-34263-9_22"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1109\/TMI.2004.831226","article-title":"Genus zero surface conformal mapping and its application to brain surface mapping","volume":"23","author":"Gu","year":"2004","journal-title":"IEEE Tran. Med. Imaging"},{"doi-asserted-by":"crossref","unstructured":"Alt, H., and Schwarzkopf, O. (1995, January 5\u20137). The voronoi diagram of curved objects. Proceedings of the 11th Annual Symposium on Computational Geometry, Vancouver, BC, Canada.","key":"ref_38","DOI":"10.1145\/220279.220289"},{"doi-asserted-by":"crossref","unstructured":"Li, J., Jannotti, J., de Couto, D.S.J., Karger, D.R., and Morris, R. (2000, January 6\u201311). A scalable location service for geographic ad hoc routing. Proceedings of the MobiCom, Boston, MA, USA.","key":"ref_39","DOI":"10.1145\/345910.345931"},{"doi-asserted-by":"crossref","unstructured":"Li, X., Kim, Y.J., Govindan, R., and Hong, W. (2003, January 5\u20137). Multi-dimensional range queries in sensor networks. Proceedings of the SenSys, Los Angeles, CA, USA.","key":"ref_40","DOI":"10.1145\/958499.958500"},{"unstructured":"Yu-Chi, C., I-Fang, S., and Chiang, L. (2007, January 25\u201329). Supporting multi-dimensional range query for sensor networks. Proceedings of the ICDCS, Toronto, ON, Canada.","key":"ref_41"}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/3\/2\/177\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:11:27Z","timestamp":1760217087000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/3\/2\/177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,15]]},"references-count":41,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2014,6]]}},"alternative-id":["axioms3020177"],"URL":"https:\/\/doi.org\/10.3390\/axioms3020177","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2014,5,15]]}}}