Health & Environmental Research Online (HERO)


Print Feedback Export to File
6107296 
Journal Article 
On optimal spectrum-efficient routing in TDMA and FDMA multihop wireless networks 
Saad, M 
2012 
Yes 
Computer Communications
ISSN: 0140-3664 
35 
5 
628-636 
WOS:000301819100010 
This paper addresses the problem of finding the route with maximum end-to-end spectral efficiency, under the constraint of equal bandwidth sharing, in multihop wireless networks that use time division multiple access (TDMA) or frequency division multiple access (FDMA). The conceptual difficulty of this problem arises from the fact that the associated routing metric is neither isotonic nor monotone, and, thus, it cannot be solved directly using shortest path algorithms. The author has recently presented the first polynomial-time algorithm that solves the problem to exact optimality for TDMA networks. The contribution of this paper is twofold. For TDMA networks, we present a new algorithm that achieves a significant improvement in the computational complexity as compared to the algorithms previously known. For FDMA networks, we introduce the first polynomial-time algorithm that provides provably optimal routes. The proposed algorithms rely on the divide-and-conquer principle and a modified Bellman–Ford algorithm for widest path computation. Our computational results further illustrate the efficiency of the proposed approach. 
Multihop wireless networks; Spectrum-efficient routing; TDMA; FDMA; Polynomial-time algorithms