{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:42Z","timestamp":1759638222275,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>\n            We study routing and scheduling in\n            <jats:italic>multihop wireless networks<\/jats:italic>\n            . When data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. The data transmission is\n            <jats:italic>node constrained<\/jats:italic>\n            , that is, every node can transmit data to at most one neighboring node per time step. The transmission rates are\n            <jats:italic>time varying<\/jats:italic>\n            as a result of changing wireless channel conditions.\n          <\/jats:p>\n          <jats:p>\n            In this article, we assume that data arrivals and transmission rates are governed by an\n            <jats:italic>adversary<\/jats:italic>\n            . The power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. The node-constrained transmission and time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks.\n          <\/jats:p>\n          <jats:p>\n            For the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. These algorithms try to give priority to the data that is closest to its source node. However, at each time step only a subset of the data queued at a node is eligible for scheduling. One of our algorithms is fully\n            <jats:italic>distributed<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>For the case in which the adversary does not dictate the data paths, we show how to route data so that the admissibility condition is satisfied. We can then schedule data along the chosen paths using our stable scheduling algorithms.<\/jats:p>","DOI":"10.1145\/1273340.1273349","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Routing and scheduling in multihop wireless networks with time-varying channels"],"prefix":"10.1145","volume":"3","author":[{"given":"Matthew","family":"Andrews","sequence":"first","affiliation":[{"name":"Bell Laboratories, Murray Hill, NJ"}]},{"given":"Lisa","family":"Zhang","sequence":"additional","affiliation":[{"name":"Bell Laboratories, Murray Hill, NJ"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082040"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964804182041"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/35.900644"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089028"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509968"},{"volume-title":"Proceedings of the 42nd Annual Symposium on Foundations of Computer Science","author":"Awerbuch B.","key":"e_1_2_1_6_1","unstructured":"Awerbuch , B. , Berenbrink , P. , Brinkmann , A. , and Scheideler , C . 2001. Simple routing strategies for adversarial systems . In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science ( Las Vegas, NV, Oct.). 158--167. Awerbuch, B., Berenbrink, P., Brinkmann, A., and Scheideler, C. 2001. Simple routing strategies for adversarial systems. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (Las Vegas, NV, Oct.). 158--167."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363659"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021926590400099X"},{"volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"Garg N.","key":"e_1_2_1_9_1","unstructured":"Garg , N. , and Konemann , J . 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems . In Proceedings of the 39th Annual Symposium on Foundations of Computer Science ( Palo Alto, CA, Nov.) 300--309. Garg, N., and Konemann, J. 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, Nov.) 300--309."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.801403"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"volume-title":"Proceedings of the IEEE Semiannual Vehicular Technology Conference (VTC Spring)","author":"Jalali A.","key":"e_1_2_1_12_1","unstructured":"Jalali , A. , Padovani , R. , and Pankaj , R . 2000. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system . In Proceedings of the IEEE Semiannual Vehicular Technology Conference (VTC Spring) ( Tokyo, Japan, May). Jalali, A., Padovani, R., and Pankaj, R. 2000. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system. In Proceedings of the IEEE Semiannual Vehicular Technology Conference (VTC Spring) (Tokyo, Japan, May)."},{"volume-title":"the 40th Annual Allerton Conference on Communication, Control, and Computing.","author":"Kushner H.","key":"e_1_2_1_13_1","unstructured":"Kushner , H. , and Whiting , P . 2002. Asymptotic properties of proportional fair sharing algorithms . In the 40th Annual Allerton Conference on Communication, Control, and Computing. Kushner, H., and Whiting, P. 2002. Asymptotic properties of proportional fair sharing algorithms. In the 40th Annual Allerton Conference on Communication, Control, and Computing."},{"volume-title":"Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies","author":"Neely M.","key":"e_1_2_1_14_1","unstructured":"Neely , M. , Modiano , E. , and Rohrs , C . 2003. Dynamic power allocation and routing for time varying wireless networks . In Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies ( San Francisco, CA, Apr.). Neely, M., Modiano, E., and Rohrs, C. 2003. Dynamic power allocation and routing for time varying wireless networks. In Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies (San Francisco, CA, Apr.)."},{"volume-title":"Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies","author":"Neely M.","key":"e_1_2_1_15_1","unstructured":"Neely , M. , Modiano , E. , and Rohrs , C . 2002. Power and server allocation in a multi-beam satellite with time varying channels . In Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies ( New York, Jun.). Neely, M., Modiano, E., and Rohrs, C. 2002. Power and server allocation in a multi-beam satellite with time varying channels. In Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies (New York, Jun.)."},{"key":"e_1_2_1_16_1","first-page":"185","article-title":"Scheduling for multiple flows sharing a time-varying channel: The exponential rule","volume":"207","author":"Shakkottai S.","year":"2002","unstructured":"Shakkottai , S. , and Stolyar , A. 2002 . Scheduling for multiple flows sharing a time-varying channel: The exponential rule . Anal. Meth. Appl. Probab. 207 , 185 -- 202 . Shakkottai, S., and Stolyar, A. 2002. Scheduling for multiple flows sharing a time-varying channel: The exponential rule. Anal. Meth. Appl. Probab. 207, 185--202.","journal-title":"Anal. Meth. Appl. Probab."},{"volume-title":"Proceedings of 17th International Teletraffic Congress (Salvador da Bahia, Brazil). 793--804","author":"Shakkottai S.","key":"e_1_2_1_17_1","unstructured":"Shakkottai , S. , and Stolyar , A . 2001. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR . In Proceedings of 17th International Teletraffic Congress (Salvador da Bahia, Brazil). 793--804 . Shakkottai, S., and Stolyar, A. 2001. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR. In Proceedings of 17th International Teletraffic Congress (Salvador da Bahia, Brazil). 793--804."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0156"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.182479"},{"volume-title":"Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies","author":"Tassiulas L.","key":"e_1_2_1_20_1","unstructured":"Tassiulas , L. , and Sarkar , S . 2002. Maxmin fair scheduling in wireless networks . In Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies ( New York, Jun.). Tassiulas, L., and Sarkar, S. 2002. Maxmin fair scheduling in wireless networks. In Proceedings of the Annual Joint INFOCOM Conference of the IEEE Computer and Communications Societies (New York, Jun.)."},{"key":"e_1_2_1_21_1","volume-title":"Multiuser diversity in wireless networks","author":"Tse D.","year":"2001","unstructured":"Tse , D. Multiuser diversity in wireless networks . 2001 . http:\/\/degas.eecs.berkeley.edu\/~dtse\/pub.html. Tse, D. Multiuser diversity in wireless networks. 2001. http:\/\/degas.eecs.berkeley.edu\/~dtse\/pub.html."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1273340.1273349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:55Z","timestamp":1750258675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1273340.1273349"],"URL":"https:\/\/doi.org\/10.1145\/1273340.1273349","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}