Skip to search boxSkip to navigationSkip to main content

On the complexity of routing in wireless multihop network

  • Sonia Waharte
    ,
  • Alexander Golynski
    ,
  • Raouf Boutaba
Research Output: Chapter in Book/Report/Conference proceeding Conference contribution Peer-review

Open access

Abstract

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 sup- ported by the network. In this paper, we prove that this problem is NP-hard as a result of the wireless interference that is created between geographically close transmission links. We consequently design and investigate the performance of interference-aware algorithms suitable for multi-channel environments against more traditional routing approaches. We evaluate their performance in simulated environments based on data taken from existing networks, and show that interference-based heuristics exhibit advantageous performance in non-uniform deployment.

Publication Information

Output type

Research Output: Chapter in Book/Report/Conference proceeding Conference contribution Peer-review

Original language

English

Publication milestones

  • Published - 27/09/2012

Publication status

Published - 27/09/2012

Publisher

Institute of Electrical and Electronics Engineers Inc., United States

External Publication IDs

  • handle.net: 10547/288445
  • Scopus: 84869185600

Host publication title

2012 8th International Wireless Communications and Mobile Computing Conference (IWCMC)

Access to documents

Publication metrics

Metrics

Download statistics
Download count
6