{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:00:02Z","timestamp":1753887602825,"version":"3.41.2"},"reference-count":26,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T00:00:00Z","timestamp":1612224000000},"content-version":"vor","delay-in-days":32,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["F060505","ZR2019ZD10","61972404","12071478"],"award-info":[{"award-number":["F060505","ZR2019ZD10","61972404","12071478"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Wireless Communications and Mobile Computing"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Following the recent advances in the Internet of Things (IoT), it is drawing lots of attention to design distributed algorithms for various network optimization problems under the SINR (Signal\u2010to\u2010Interference\u2010and\u2010Noise\u2010Ratio) interference model, such as spanner construction. Since a spanner can maintain a linear number of links while still preserving efficient routes for any pair of nodes in wireless networks, it is important to design distributed algorithms for spanners. Given a constant <jats:italic>t<\/jats:italic> &gt; 1 as the required stretch factor, the problem of our concern is to design an efficient distributed algorithm to construct a <jats:italic>t<\/jats:italic>\u2010spanner of the communication graph under SINR such that the delay for the task completion is minimized, where the delay is the time interval between the time slot that the first node commences its operation to the time slot that all the nodes finish their task of constructing the <jats:italic>t<\/jats:italic>\u2010spanner. Our main contributions include four aspects. First, we propose a proximity range and proximity independent set (PISet) to increase the number of nodes transmitting successfully at the same time in order to reduce the delay. Second, we develop a distributed randomized algorithm SINR\u2010Spanner to construct a required <jats:italic>t<\/jats:italic>\u2010spanner with high probability. Third, the approximation ratio of SINR\u2010Spanner is proven to be a constant. Finally, extensive simulations are carried out to verify the effectiveness and efficiency of our proposed algorithm.<\/jats:p>","DOI":"10.1155\/2021\/6643810","type":"journal-article","created":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T03:35:08Z","timestamp":1612323308000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Constructing <i>t<\/i>\u2010Spanner in IoT under SINR"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0609-8710","authenticated-orcid":false,"given":"Xiujuan","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4197-2258","authenticated-orcid":false,"given":"Yongcai","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenping","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuqing","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7748-5427","authenticated-orcid":false,"given":"Deying","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6147-0637","authenticated-orcid":false,"given":"Guangshun","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2021,2,2]]},"reference":[{"key":"e_1_2_11_1_2","doi-asserted-by":"crossref","unstructured":"CaiZ.andHeZ. Trading private range counting over big IoT data 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS) 2019 Dallas TX USA 144\u2013153 https:\/\/doi.org\/10.1109\/icdcs.2019.00023.","DOI":"10.1109\/ICDCS.2019.00023"},{"key":"e_1_2_11_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2019.102037"},{"key":"e_1_2_11_3_2","first-page":"904","article-title":"Spanner construction for topology control in wireless networks","volume":"26","author":"Zhang X.","year":"2015","journal-title":"Ruan Jian Xue Bao\/Journal of Software"},{"key":"e_1_2_11_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"e_1_2_11_5_2","series-title":"Lecture Notes in Computer Science","first-page":"196","volume-title":"Graph Drawing. GD 2006","author":"Klein R.","year":"2006"},{"key":"e_1_2_11_6_2","doi-asserted-by":"crossref","unstructured":"LiX. WanP. andWangY. Power efficient and sparse spanner for wireless ad hoc networks Proceedings Tenth International Conference on Computer Communications and Networks (Cat. No.01EX495) 2001 Scottsdale AZ USA 564\u2013567 https:\/\/doi.org\/10.1109\/icccn.2001.956322 2-s2.0-84950243763.","DOI":"10.1109\/ICCCN.2001.956322"},{"key":"e_1_2_11_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.926506"},{"key":"e_1_2_11_8_2","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rssonM. M.andTonoyanT. Plain SINR is enough Jul 2019 in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing 2019 Toronto Canada 127\u2013136 https:\/\/doi.org\/10.1145\/3293611.3331602 2-s2.0-85070981273.","DOI":"10.1145\/3293611.3331602"},{"key":"e_1_2_11_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2688484"},{"key":"e_1_2_11_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211059"},{"key":"e_1_2_11_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_11_12_2","series-title":"The IMA Volumes in Mathematics and its Applications","first-page":"237","volume-title":"Wireless Communications","author":"Scheideler C.","year":"2010"},{"key":"e_1_2_11_13_2","doi-asserted-by":"crossref","unstructured":"KanjI. Geometric spanners: recent results and open directions 82 2013 Third International Conference on Communications and Information Technology (ICCIT) 2013 Beirut Lebanon https:\/\/doi.org\/10.1109\/iccitechnology.2013.6579526 2-s2.0-84883896156.","DOI":"10.1109\/ICCITechnology.2013.6579526"},{"key":"e_1_2_11_14_2","doi-asserted-by":"crossref","unstructured":"KothapalliK. ScheidelerC. OnusM. andRichaA. W. Constant density spanners for wireless ad-hoc networks Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures - SPAA\u203205 2005 Las Vegas NV USA 116\u2013125 https:\/\/doi.org\/10.1145\/1073970.1073987 2-s2.0-32144443992.","DOI":"10.1145\/1073970.1073987"},{"key":"e_1_2_11_15_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a015"},{"key":"e_1_2_11_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.07.020"},{"key":"e_1_2_11_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0476-8"},{"key":"e_1_2_11_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2016.10.012"},{"key":"e_1_2_11_19_2","doi-asserted-by":"crossref","unstructured":"GoussevskaiaO. MoscibrodaT. andWattenhoferR. Local broadcasting in the physical interference model Proceedings of the 5th International Workshop on Foundations of Mobile Computing (DialM-POMC\u203208) 2008 Toronto Canada 35\u201344 https:\/\/doi.org\/10.1145\/1400863.1400873 2-s2.0-65249107706.","DOI":"10.1145\/1400863.1400873"},{"key":"e_1_2_11_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31104-8_10"},{"key":"e_1_2_11_21_2","doi-asserted-by":"crossref","unstructured":"JurdzinskiT. KowalskiD. R. RozanskiM. andStachowiakG. On setting-up asynchronous ad hoc wireless networks 2015 IEEE Conference on Computer Communications (INFOCOM) 2015 Kowloon Hong Kong 2191\u20132199 https:\/\/doi.org\/10.1109\/infocom.2015.7218605 2-s2.0-84954211878.","DOI":"10.1109\/INFOCOM.2015.7218605"},{"key":"e_1_2_11_22_2","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rssonM. M. WangY. andYuD. Leveraging multiple channels in ad hoc networks Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing 2015 Donostia-San Sebasti\u00e1n Spain 431\u2013440 https:\/\/doi.org\/10.1145\/2767386.2767437 2-s2.0-84957645899.","DOI":"10.1145\/2767386.2767437"},{"key":"e_1_2_11_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_11"},{"key":"e_1_2_11_24_2","doi-asserted-by":"crossref","unstructured":"FuL. LiewS. C. andHuangJ. Effective carrier sensing in CSMA networks under cumulative interference 2010 Proceedings IEEE INFOCOM 2010 San Diego CA USA 1\u20139 https:\/\/doi.org\/10.1109\/infcom.2010.5462088 2-s2.0-77953295008.","DOI":"10.1109\/INFCOM.2010.5462088"},{"key":"e_1_2_11_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108755528"},{"key":"e_1_2_11_26_2","unstructured":"Distributed Computing Group ETH Zurich Sinalgo - simulator for network algorithms version 0.75.3. 2008 http:\/\/sourceforge.net\/projects\/."}],"container-title":["Wireless Communications and Mobile Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/wcmc\/2021\/6643810.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/wcmc\/2021\/6643810.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2021\/6643810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T13:56:20Z","timestamp":1723038980000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2021\/6643810"}},"subtitle":[],"editor":[{"given":"Zhuojun","family":"Duan","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1155\/2021\/6643810"],"URL":"https:\/\/doi.org\/10.1155\/2021\/6643810","archive":["Portico"],"relation":{},"ISSN":["1530-8669","1530-8677"],"issn-type":[{"type":"print","value":"1530-8669"},{"type":"electronic","value":"1530-8677"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"2020-10-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"6643810"}}