On the Complexity of Routing in Wireless Multihop Network
Wireless backbone networks represent an attractive alternative to wired networks in situations where cost, speed of deployment, and flexibility in network design are important. In typical configurations, users connect to wireless routers of the backbone network, which then redirect the traffic to one of the existing network gateways. To improve the network performance, wireless backbone routers redirect their traffic to the network gateways so as to maximize amount of traffic that can be supported by the network. In this paper, the authors prove that this problem is NP-hard as a result of the wireless interference that is created between geographically close transmission links.