{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:39:44Z","timestamp":1757540384436,"version":"3.37.3"},"reference-count":33,"publisher":"Wiley","license":[{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772385","61572370"],"award-info":[{"award-number":["61772385","61572370"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mobile Information Systems"],"published-print":{"date-parts":[[2020,11,16]]},"abstract":"<jats:p>We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters <jats:inline-formula>\n                     <a:math xmlns:a=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M1\">\n                        <a:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <a:mrow>\n                              <a:mi>f<\/a:mi>\n                              <a:mo>,<\/a:mo>\n                              <a:mi>g<\/a:mi>\n                           <\/a:mrow>\n                        <\/a:mfenced>\n                     <\/a:math>\n                  <\/jats:inline-formula>. We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides. First, we propose four approximation algorithms for the weighted channel allocation problem: 1. a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side <jats:inline-formula>\n                     <f:math xmlns:f=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M2\">\n                        <f:mi>O<\/f:mi>\n                        <f:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <f:mrow>\n                              <f:mn>1<\/f:mn>\n                           <\/f:mrow>\n                        <\/f:mfenced>\n                     <\/f:math>\n                  <\/jats:inline-formula>-IS-approximation is obtained; 2. a greedy <jats:inline-formula>\n                     <k:math xmlns:k=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M3\">\n                        <k:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <k:mrow>\n                              <k:mi>O<\/k:mi>\n                              <k:mrow>\n                                 <k:mfenced open=\"(\" close=\")\" separators=\"|\">\n                                    <k:mrow>\n                                       <k:mn>1<\/k:mn>\n                                    <\/k:mrow>\n                                 <\/k:mfenced>\n                                 <k:mo>,<\/k:mo>\n                                 <k:mi>O<\/k:mi>\n                                 <k:mfenced open=\"(\" close=\")\" separators=\"|\">\n                                    <k:mrow>\n                                       <k:mn>1<\/k:mn>\n                                    <\/k:mrow>\n                                 <\/k:mfenced>\n                              <\/k:mrow>\n                           <\/k:mrow>\n                        <\/k:mfenced>\n                     <\/k:math>\n                  <\/jats:inline-formula>-approximation algorithm for single channel with fixed interference radius scheduling problem is presented; 3. we improve the existing algorithm for the multichannel scheduling and show an <jats:inline-formula>\n                     <v:math xmlns:v=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M4\">\n                        <v:mfenced open=\"|\" close=\"|\" separators=\"|\">\n                           <v:mrow>\n                              <v:mi>E<\/v:mi>\n                           <\/v:mrow>\n                        <\/v:mfenced>\n                        <v:msup>\n                           <v:mrow>\n                              <v:mi>O<\/v:mi>\n                           <\/v:mrow>\n                           <v:mrow>\n                              <v:mfenced open=\"(\" close=\")\" separators=\"|\">\n                                 <v:mrow>\n                                    <v:mi>d<\/v:mi>\n                                    <v:mo>\/<\/v:mo>\n                                    <v:mi>\u03b5<\/v:mi>\n                                 <\/v:mrow>\n                              <\/v:mfenced>\n                           <\/v:mrow>\n                        <\/v:msup>\n                     <\/v:math>\n                  <\/jats:inline-formula> time <jats:inline-formula>\n                     <db:math xmlns:db=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M5\">\n                        <db:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <db:mrow>\n                              <db:mn>1<\/db:mn>\n                              <db:mo>\u2212<\/db:mo>\n                              <db:mi>\u03f5<\/db:mi>\n                           <\/db:mrow>\n                        <\/db:mfenced>\n                     <\/db:math>\n                  <\/jats:inline-formula>-approximation algorithm; 4. we speed up the polynomial time approximation scheme for single-channel scheduling through merging two algorithms and show a <jats:inline-formula>\n                     <ib:math xmlns:ib=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M6\">\n                        <ib:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <ib:mrow>\n                              <ib:mn>1<\/ib:mn>\n                              <ib:mo>\u2212<\/ib:mo>\n                              <ib:mi>\u03f5<\/ib:mi>\n                              <ib:mo>,<\/ib:mo>\n                              <ib:mi>O<\/ib:mi>\n                              <ib:mrow>\n                                 <ib:mfenced open=\"(\" close=\")\" separators=\"|\">\n                                    <ib:mrow>\n                                       <ib:mn>1<\/ib:mn>\n                                    <\/ib:mrow>\n                                 <\/ib:mfenced>\n                              <\/ib:mrow>\n                           <\/ib:mrow>\n                        <\/ib:mfenced>\n                     <\/ib:math>\n                  <\/jats:inline-formula>-approximation algorithm. Next, we study two polynomial time constant factor greedy approximation algorithms for the unweighted channel allocation with variate interference radius. A greedy <jats:inline-formula>\n                     <qb:math xmlns:qb=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M7\">\n                        <qb:mi>O<\/qb:mi>\n                        <qb:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <qb:mrow>\n                              <qb:mn>1<\/qb:mn>\n                           <\/qb:mrow>\n                        <\/qb:mfenced>\n                     <\/qb:math>\n                  <\/jats:inline-formula>-approximation algorithm for the multichannel scheduling problem and an <jats:inline-formula>\n                     <vb:math xmlns:vb=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M8\">\n                        <vb:mfenced open=\"(\" close=\")\" separators=\"|\">\n                           <vb:mrow>\n                              <vb:mi>O<\/vb:mi>\n                              <vb:mrow>\n                                 <vb:mfenced open=\"(\" close=\")\" separators=\"|\">\n                                    <vb:mrow>\n                                       <vb:mn>1<\/vb:mn>\n                                    <\/vb:mrow>\n                                 <\/vb:mfenced>\n                                 <vb:mo>,<\/vb:mo>\n                                 <vb:mi>O<\/vb:mi>\n                                 <vb:mfenced open=\"(\" close=\")\" separators=\"|\">\n                                    <vb:mrow>\n                                       <vb:mn>1<\/vb:mn>\n                                    <\/vb:mrow>\n                                 <\/vb:mfenced>\n                              <\/vb:mrow>\n                           <\/vb:mrow>\n                        <\/vb:mfenced>\n                     <\/vb:math>\n                  <\/jats:inline-formula>-approximation algorithm for single-channel scheduling problem are developed. At last, we do some experiments to verify the effectiveness of our proposed methods.<\/jats:p>","DOI":"10.1155\/2020\/8836517","type":"journal-article","created":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T02:50:09Z","timestamp":1605581409000},"page":"1-13","source":"Crossref","is-referenced-by-count":1,"title":["Different Approximation Algorithms for Channel Scheduling in Wireless Networks"],"prefix":"10.1155","volume":"2020","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0462-9549","authenticated-orcid":true,"given":"Qiufen","family":"Ni","sequence":"first","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan 430072, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5554-4871","authenticated-orcid":true,"given":"Chuanhe","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan 430072, China"},{"name":"Collaborative Innovation Center of Geospatial Technology, Wuhan 430072, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos M.","family":"Pardalos","sequence":"additional","affiliation":[{"name":"Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA"},{"name":"LATNA, Higher School of Economics, Nizhni Novgorod, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia","family":"Ye","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan 430072, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas Rio Grande Valley, Edinburg, TX 78539, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","reference":[{"key":"1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90077-1"},{"first-page":"871","article-title":"A multi-channel timeslot scheduling algorithm for link recovery in wireless multi-hop sensor networks","author":"J. Lee","key":"2"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1007\/s12083-017-0619-8"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1109\/twc.2016.2629484"},{"first-page":"216","article-title":"Ssch: slotted seeded channel hopping for capacity improvement in ieee 802.11 ad-hoc wireless networks","author":"P. Bahl","key":"5"},{"key":"6","article-title":"Reduced power for avoidance of interference in wireless communications","volume":"15","author":"R. S. Reis","year":"2018","journal-title":"United States Patent Application"},{"key":"7","article-title":"Approaches for improved frequency reuse efficiency and interference avoidance for a multi-beam satellite communications network","volume":"15","author":"S. Kay","year":"2018","journal-title":"United States Patent Application"},{"first-page":"367","article-title":"Enhanced adaptive geographic opportunistic routing with interference avoidance assisted with mobile sinks for underwater wireless sensor network","author":"T. N. Qureshi","key":"8"},{"key":"9","first-page":"148","article-title":"Avoidance of interference in wireless communications","volume":"16","author":"R. S. Reis","year":"2019","journal-title":"United States Patent Application"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1109\/twc.2017.2762680"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1109\/access.2017.2778083"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2018.03.037"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1016\/j.pmcj.2018.03.003"},{"first-page":"359","article-title":"Bssa ch: a big slot scheduling algorithm with channel hopping for dynamic wireless sensor networks","author":"C. T. Ngo","key":"14"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1109\/tcomm.2018.2812731"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-016-1351-7"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1109\/access.2018.2817189"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1155\/2010\/418934"},{"key":"19","doi-asserted-by":"publisher","DOI":"10.1109\/JCN.2017.000027"},{"first-page":"137","article-title":"Multi-channel assignment and link scheduling for prioritized latency-sensitive applications","author":"S.-Y. Tsai","key":"20"},{"key":"21","article-title":"Multi-band resource scheduling for wireless device tethering","volume":"10","author":"G. Farhadi","year":"2019","journal-title":"United States Patent Application"},{"key":"22","article-title":"Enhancing monitoring of multiple physical downlink control channels in beam based system","volume":"16","author":"J. Kaikkonen","year":"2019","journal-title":"United States Patent Application"},{"key":"23","article-title":"System and method for multi-channel packet transmission","volume":"10","author":"M. Pasotti","year":"2019","journal-title":"United States Patent Application"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-018-1672-9"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00214"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1023\/a:1019128411323"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.014"},{"first-page":"1512","article-title":"The complexity of channel scheduling in multi-radio multi-channel wireless networks","author":"W. Cheng","key":"28"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1109\/lcomm.2020.2968902"},{"article-title":"A joint learning and communications framework for federated learning over wireless networks","year":"2019","author":"M. Chen","key":"30"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1109\/access.2018.2789423"},{"first-page":"5429","article-title":"A graph-coloring based resource allocation algorithm for D2D communication in cellular networks","author":"X. Cai","key":"33"}],"container-title":["Mobile Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/misy\/2020\/8836517.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/misy\/2020\/8836517.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/misy\/2020\/8836517.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T02:50:23Z","timestamp":1605581423000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/misy\/2020\/8836517\/"}},"subtitle":[],"editor":[{"given":"Alessandro","family":"Bazzi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,11,16]]},"references-count":33,"alternative-id":["8836517","8836517"],"URL":"https:\/\/doi.org\/10.1155\/2020\/8836517","relation":{},"ISSN":["1875-905X","1574-017X"],"issn-type":[{"type":"electronic","value":"1875-905X"},{"type":"print","value":"1574-017X"}],"subject":[],"published":{"date-parts":[[2020,11,16]]}}}