Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas
Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional ante...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69948 |
| _version_ | 1811092447111938048 |
|---|---|
| author | Dutta, Partha Mhatre, Vivek Rastogi, Rajeev Panigrahi, Debmalya |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Dutta, Partha Mhatre, Vivek Rastogi, Rajeev Panigrahi, Debmalya |
| author_sort | Dutta, Partha |
| collection | MIT |
| description | Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5). |
| first_indexed | 2024-09-23T15:18:19Z |
| format | Article |
| id | mit-1721.1/69948 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:18:19Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/699482022-09-29T14:03:14Z Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas Dutta, Partha Mhatre, Vivek Rastogi, Rajeev Panigrahi, Debmalya Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Panigrahi, Debmalya Panigrahi, Debmalya Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5). 2012-04-05T15:59:44Z 2012-04-05T15:59:44Z 2010-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-3512-8 0743-166X INSPEC Accession Number: 11291475 http://hdl.handle.net/1721.1/69948 Dutta, Partha et al. “Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas.” IEEE, 2010. 1–5. Web. 5 Apr. 2012. en_US http://dx.doi.org/10.1109/INFCOM.2010.5462186 IEEE INFOCOM Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Dutta, Partha Mhatre, Vivek Rastogi, Rajeev Panigrahi, Debmalya Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas |
| title | Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas |
| title_full | Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas |
| title_fullStr | Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas |
| title_full_unstemmed | Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas |
| title_short | Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas |
| title_sort | joint routing and scheduling in multi hop wireless networks with directional antennas |
| url | http://hdl.handle.net/1721.1/69948 |
| work_keys_str_mv | AT duttapartha jointroutingandschedulinginmultihopwirelessnetworkswithdirectionalantennas AT mhatrevivek jointroutingandschedulinginmultihopwirelessnetworkswithdirectionalantennas AT rastogirajeev jointroutingandschedulinginmultihopwirelessnetworkswithdirectionalantennas AT panigrahidebmalya jointroutingandschedulinginmultihopwirelessnetworkswithdirectionalantennas |