Disjoint path protection in multi-hop wireless networks with interference constraints
We consider the problem of providing protection against failures in wireless networks by using disjoint paths. Disjoint path routing is commonly used in wired networks for protection, but due to the interference between transmitting nodes in a wireless setting, this approach has not been previously...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116508 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826213501566189568 |
|---|---|
| author | Kuperman, Gregory Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Kuperman, Gregory Modiano, Eytan H |
| author_sort | Kuperman, Gregory |
| collection | MIT |
| description | We consider the problem of providing protection against failures in wireless networks by using disjoint paths. Disjoint path routing is commonly used in wired networks for protection, but due to the interference between transmitting nodes in a wireless setting, this approach has not been previously examined for wireless networks. In this paper, we develop a non-disruptive and resource-efficient disjoint path scheme that guarantees protection in wireless networks by utilizing capacity "recapturing" after a failure. Using our scheme, protection can oftentimes be provided for all demands using no additional resources beyond what was required without any protection. We show that the problem of disjoint path protection in wireless networks is not only NP-hard, but in fact remains NP-hard to approximate. We provide an ILP formulation to find an optimal solution, and develop corresponding time-efficient algorithms. Our approach utilizes 87% less protection resources on average than the traditional disjoint path routing scheme. For the case of 2-hop interference, which corresponds to the IEEE 802.11 standard, our protection scheme requires only 8% more resources on average than providing no protection whatsoever. |
| first_indexed | 2024-09-23T15:50:15Z |
| format | Article |
| id | mit-1721.1/116508 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:50:15Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1165082019-05-17T08:51:27Z Disjoint path protection in multi-hop wireless networks with interference constraints Kuperman, Gregory Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Kuperman, Gregory Modiano, Eytan H We consider the problem of providing protection against failures in wireless networks by using disjoint paths. Disjoint path routing is commonly used in wired networks for protection, but due to the interference between transmitting nodes in a wireless setting, this approach has not been previously examined for wireless networks. In this paper, we develop a non-disruptive and resource-efficient disjoint path scheme that guarantees protection in wireless networks by utilizing capacity "recapturing" after a failure. Using our scheme, protection can oftentimes be provided for all demands using no additional resources beyond what was required without any protection. We show that the problem of disjoint path protection in wireless networks is not only NP-hard, but in fact remains NP-hard to approximate. We provide an ILP formulation to find an optimal solution, and develop corresponding time-efficient algorithms. Our approach utilizes 87% less protection resources on average than the traditional disjoint path routing scheme. For the case of 2-hop interference, which corresponds to the IEEE 802.11 standard, our protection scheme requires only 8% more resources on average than providing no protection whatsoever. National Science Foundation (U.S.) (CNS-1116209) National Science Foundation (U.S.) (CNS-1017800) United States. Defense Threat Reduction Agency (HDTRA-09-1-005) 2018-06-21T18:56:12Z 2018-06-21T18:56:12Z 2015-02 2014-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-3512-3 1930-529X http://hdl.handle.net/1721.1/116508 Kuperman, Greg, and Eytan Modiano. “Disjoint Path Protection in Multi-Hop Wireless Networks with Interference Constraints.” 2014 IEEE Global Communications Conference (December 2014), Austin, TX, USA, Institute of Electrical and Electronics Engineers (IEEE), 2014. OPEN_ACCESS_POLICY https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/GLOCOM.2014.7037512 2014 IEEE Global Communications Conference Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Prof. Modiano |
| spellingShingle | Kuperman, Gregory Modiano, Eytan H Disjoint path protection in multi-hop wireless networks with interference constraints |
| title | Disjoint path protection in multi-hop wireless networks with interference constraints |
| title_full | Disjoint path protection in multi-hop wireless networks with interference constraints |
| title_fullStr | Disjoint path protection in multi-hop wireless networks with interference constraints |
| title_full_unstemmed | Disjoint path protection in multi-hop wireless networks with interference constraints |
| title_short | Disjoint path protection in multi-hop wireless networks with interference constraints |
| title_sort | disjoint path protection in multi hop wireless networks with interference constraints |
| url | http://hdl.handle.net/1721.1/116508 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT kupermangregory disjointpathprotectioninmultihopwirelessnetworkswithinterferenceconstraints AT modianoeytanh disjointpathprotectioninmultihopwirelessnetworkswithinterferenceconstraints |