# Optimal Multicommodity Spectrum-Efficient Routing in Multihop Wireless Networks

Authors: Mohamed Saad
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Finding the route with maximum end-to-end spectral efficiency in multihop wireless networks has been subject to interest in the recent literature. All previous studies, however, focused on findingone route from a given source to a given destination under the constraint of equal bandwidth sharing. To the best of our knowledge, for the first time, this paper provides extensions to the multicommodity flow case, i.e., the case of multiple simultaneous source-destination (s-d) pairs. In particular, given an arbitrary number of s-d pairs, we address the problem of finding a route for every s-d pair such that the minimum spectral efficiency across all routes is maximized. We provide two alternative approaches, where one is based on fixed-sized time slots and the other is based on variable-sized time slots. For each approach, we derive theprovably optimal routing algorithm. We also shed the light on the arising tradeoff between the complexity of network-layer route computation and the complexity of medium access control (MAC) layer scheduling of time slots, as well as the amenability to distributed implementation of our proposed algorithms. Our numerical results further illustrate the efficiency of the proposed approaches and their tradeoffs.


---

## Body

## 1. Introduction

Multihop wireless networks consist of a set of wireless devices that communicate with each other over multiple wireless hops, with participating nodes collaboratively relaying ongoing traffic. Wireless multihop relaying/routing is the foundation for the development and deployment of emerging technologies such as(i)
client mesh networks: a set of client devices (tablets, phones, and/or laptops) form a multihop network withpeer-to-peer relaying;(ii)
infrastructure wireless mesh networks: wireless routers/access points are interconnected to provide an infrastructure/backbone for clients;(iii)
millimeter-wave-based 5G networks: future 5G networks are envisioned to depend (among others) on ultradense small-cell base stations and the use of millimeter- (mm-) wave spectrum for transmission [1]. The large bandwidth of mm-wave is also accompanied by a high path loss, which necessities the use of multihop relaying across the small-cell base stations [2]. Intelligent routing methods will also be needed for the underlying applications of 5G, e.g., the Internet of Things (IoT) [3].The end-to-endspectral efficiency (in bps/Hz) of a communication route is defined as the rate at which data can be transmitted over the route per unit bandwidth. Therefore, it is an indication of how efficient the channel bandwidth is utilized. Since the bandwidth is a scarce resource in wireless systems, this paper focuses on finding communication routes with maximum spectral efficiencies. In particular, given a multihop wireless network consisting of set of wireless devices and interconnecting wireless links and a set of source-destination (s-d) pairs of nodes, this paper addresses the problem of finding a path for each s-d pair such that the minimum spectral efficiency of all paths is maximized.


### 1.1. Related Work

To the best of our knowledge, this is the first systematic, comprehensive study to address wireless spectrum-efficient routing in the case of multiples-d pairs. Related work is presented in two categories:(1)
wireless spectrum-efficient routing,(2)
routing for multiple simultaneouss-d pairs.In what follows we summarize the relevant previous work belonging to both groups.Spectrum-efficient routing: the recent study in [4] has introduced the following spectrum-efficient routing problem. Given a multihop wireless network that employs time division multiple access (TDMA) andone  s-d pair, it finds the route withmaximum spectral efficiency under the constraint of equal bandwidth sharing. On the one hand, the authors of [4] noted that simple shortest path algorithms cannot be used to solve the problem because the resulting routing metric is not isotonic [5]. On the other hand, exhaustive search has an exponential computational complexity because it involves precomputingall paths joining a given node pair. Therefore, the study in [4] proposed two efficient, yetsuboptimal spectrum-efficient routing heuristics. In [6], we have closed the algorithmic gap by introducing thefirst polynomial-time algorithm that solves the spectrum-efficient routing problem (originally introduced in [4]) to exact optimality. In particular, the algorithm presented in [6] has a worst-case computational complexity of O(N4), where N is the number of nodes. Moreover, we have introduced in [7, 8] an improved algorithm for the same problem that runs in O(N3)-time. Furthermore, we have addressed in [9] the problem of joint routing and power allocation such that a desired spectral efficiency is achieved.All the studies above focused on finding a route from a given source to a given destination and did not address the interaction between multiples-d pairs; i.e., they did not address the multicommodity flow case. The study in [9] pointed very briefly to the extension to multiple s-d pairs for joint routing and power allocation. In contrast, this current paper takes a systematic and comprehensive approach to introduce the multicommodity spectrum-efficient routing problem, which is far from being fully explored.Multicommodity flow: finding routes for multiple s-d pairs simultaneously, such that a network-wide objective is optimized and the link capacities are not exceeded, is known in the computing literature as the multicommodity flow problem. In particular, given a network with capacities on the links, and a set of s-d pairs of nodes with associated traffic demands, the problem is to route the demand of each s-d pair alongexactly one route from s to d without violating/exceeding the link capacities. This problem is known as the integer multicommodity flow problem, or theunsplittable flow problem, and is known to be NP-hard. Readers can refer to [10, 11] for more information. If the limitation of routing each demand along exactly one route is relaxed (i.e., each demand can be split across arbitrarily many routes), the resultingsplittable flow problem can be solved in polynomial-time using linear programming. Readers can refer to [12] for more information. The problem addressed in this paper falls in the category of unsplittable flow, which is in general NP-hard to solve. It is worth noting that the above-mentioned unsplittable/multicommodity flow literature is devised for generic network settings, mostly applicable to wired networks. In this paper, we do not borrow any general-purpose multicommodity flow algorithm from the computing literature. However, we devise new polynomial-time algorithms that harness the special structure of the spectrum-efficient routing problem and provideprovably optimal solutions.


### 1.2. Contribution and Paper Outline

In light of the above, the contribution of this paper can be summarized as follows.(i)
To the best of our knowledge, for the first time, we address the problem of spectrum-efficient routing in the case of multiples-d pairs. In particular, given a multihop wireless network and an arbitrary set of s-d pairs, we address the problem of finding a route for every s-d pair such that the minimum spectral efficiency across all routes is maximized.(ii)
For the problem above, we provide two alternative approaches, where one is based on fixed-sized time slots and the other is based on variable-sized time slots. For each approach, we derive theprovably optimal routing algorithm. En route, our study sheds the light on the arising tradeoff between the complexity of network-layer route computation versus the complexity of medium access control (MAC) layer scheduling of time slots. Our numerical results further illustrate the efficiency of the proposed approaches, and their tradeoffs.The remainder of this paper is organized as follows. Section2 discusses the basics and preliminaries. Section 3 presents the problem formulation and provably optimal algorithm for the fixed time slots approach. The variable-time-slots-based approach, its problem formulation, and provably optimal algorithm are presented in Section 4. Section 5 discusses the tradeoff between the two approaches. Numerical examples and results are presented in Section 6. Section 7 concludes the paper.


## 1.1. Related Work

To the best of our knowledge, this is the first systematic, comprehensive study to address wireless spectrum-efficient routing in the case of multiples-d pairs. Related work is presented in two categories:(1)
wireless spectrum-efficient routing,(2)
routing for multiple simultaneouss-d pairs.In what follows we summarize the relevant previous work belonging to both groups.Spectrum-efficient routing: the recent study in [4] has introduced the following spectrum-efficient routing problem. Given a multihop wireless network that employs time division multiple access (TDMA) andone  s-d pair, it finds the route withmaximum spectral efficiency under the constraint of equal bandwidth sharing. On the one hand, the authors of [4] noted that simple shortest path algorithms cannot be used to solve the problem because the resulting routing metric is not isotonic [5]. On the other hand, exhaustive search has an exponential computational complexity because it involves precomputingall paths joining a given node pair. Therefore, the study in [4] proposed two efficient, yetsuboptimal spectrum-efficient routing heuristics. In [6], we have closed the algorithmic gap by introducing thefirst polynomial-time algorithm that solves the spectrum-efficient routing problem (originally introduced in [4]) to exact optimality. In particular, the algorithm presented in [6] has a worst-case computational complexity of O(N4), where N is the number of nodes. Moreover, we have introduced in [7, 8] an improved algorithm for the same problem that runs in O(N3)-time. Furthermore, we have addressed in [9] the problem of joint routing and power allocation such that a desired spectral efficiency is achieved.All the studies above focused on finding a route from a given source to a given destination and did not address the interaction between multiples-d pairs; i.e., they did not address the multicommodity flow case. The study in [9] pointed very briefly to the extension to multiple s-d pairs for joint routing and power allocation. In contrast, this current paper takes a systematic and comprehensive approach to introduce the multicommodity spectrum-efficient routing problem, which is far from being fully explored.Multicommodity flow: finding routes for multiple s-d pairs simultaneously, such that a network-wide objective is optimized and the link capacities are not exceeded, is known in the computing literature as the multicommodity flow problem. In particular, given a network with capacities on the links, and a set of s-d pairs of nodes with associated traffic demands, the problem is to route the demand of each s-d pair alongexactly one route from s to d without violating/exceeding the link capacities. This problem is known as the integer multicommodity flow problem, or theunsplittable flow problem, and is known to be NP-hard. Readers can refer to [10, 11] for more information. If the limitation of routing each demand along exactly one route is relaxed (i.e., each demand can be split across arbitrarily many routes), the resultingsplittable flow problem can be solved in polynomial-time using linear programming. Readers can refer to [12] for more information. The problem addressed in this paper falls in the category of unsplittable flow, which is in general NP-hard to solve. It is worth noting that the above-mentioned unsplittable/multicommodity flow literature is devised for generic network settings, mostly applicable to wired networks. In this paper, we do not borrow any general-purpose multicommodity flow algorithm from the computing literature. However, we devise new polynomial-time algorithms that harness the special structure of the spectrum-efficient routing problem and provideprovably optimal solutions.


## 1.2. Contribution and Paper Outline

In light of the above, the contribution of this paper can be summarized as follows.(i)
To the best of our knowledge, for the first time, we address the problem of spectrum-efficient routing in the case of multiples-d pairs. In particular, given a multihop wireless network and an arbitrary set of s-d pairs, we address the problem of finding a route for every s-d pair such that the minimum spectral efficiency across all routes is maximized.(ii)
For the problem above, we provide two alternative approaches, where one is based on fixed-sized time slots and the other is based on variable-sized time slots. For each approach, we derive theprovably optimal routing algorithm. En route, our study sheds the light on the arising tradeoff between the complexity of network-layer route computation versus the complexity of medium access control (MAC) layer scheduling of time slots. Our numerical results further illustrate the efficiency of the proposed approaches, and their tradeoffs.The remainder of this paper is organized as follows. Section2 discusses the basics and preliminaries. Section 3 presents the problem formulation and provably optimal algorithm for the fixed time slots approach. The variable-time-slots-based approach, its problem formulation, and provably optimal algorithm are presented in Section 4. Section 5 discusses the tradeoff between the two approaches. Numerical examples and results are presented in Section 6. Section 7 concludes the paper.


## 2. Preliminaries

To avoid the computational intractability of joint optimal routing and medium access control (MAC) layer scheduling, and following [4, 6–9], it is assumed that a common channel is shared among all nodes using TDMA without spatial reuse, i.e., each node transmits in its own unique time slot. It is demonstrated in [4] that, even though a path is selected assuming no spatial reuse/interference, applying a scheduling technique (separately) that allows some spatial reuse to the selected path can further improve the spectral efficiency. In other words, our framework can still benefit from spatial reuse. It is worth noticing that the MAC layer of the IEEE 802.16 mesh protocol, for example, is based on TDMA (see, e.g., [13]).A multihop wireless network is modeled as a graphG=(V,E), where V represents the set of nodes (vertices) and E represents the set of links (edges). We let l∈E signify a link in the network. We also let N=|V| and M=|E| denote the number of nodes and links, respectively.Following [4, 6, 8], we consider the setting in which all transmit devices are constrained by the same symbol-wise average transmit power P and assume that all devices transmit with power P when transmitting. A possible justification for this assumption is that nodes ininfrastructure wireless mesh networks are mostly immobile and connected with abundant power supplies. Therefore, for a link l∈E, the signal-to-noise ratio (SNR) is given by(1)SNRl=PGlN0B,where Gl is the path gain from the sender of link l to the receiver of link l, N0 is the normalized one-sided power spectral density of the additive white Gaussian noise (at any receiver in the network), and B is the finite bandwidth of the wireless channel.Now, assumeK simultaneous s-d pairs are using the network. Each s-d pair i=1,2,…,K has a source node si∈V and a destination node di∈V. We also let Li denote the set of all routes from si to di. Moreover, we let Li∈Li signify a route from si to di.Finally, the spectral efficiency of an arbitrary pathL in the network is defined as the bandwidth-normalized end-to-end data rate [4]. In other words,(2)RL=CLB,where R(L) is the spectral efficiency (in bps/Hz) of path L, C(L) is the end-to-end achievable rate (in bps) for path L, and B is the channel bandwidth (in Hz).


## 3. Fixed-Sized Time Slots

The studies in [4, 6–9] focused on asingles-d route and assumed the bandwidth is shared equally among its links via TDMA. In other words, each link transmits in its own unique time slot, where the time slots are of fixed size. One way to extend this equal bandwidth sharing to the multicommodity case is to maintain the assumption that the time frame is divided equally among all links of the different s-d routes. In particular, if s-d pairs i=1,2,…,K are served by routes L1,L2,…,LK, respectively, then any link on any of the K routes will transmit for a fraction of 1/∑i=1KLi of the time, where |Li| is the number of hops/links in route Li. In other words, the time frame will be divided into ∑i=1KLifixed-sized slots, where each slot has a length 1/∑i=1KLi of the frame length.


### 3.1. Problem Formulation

In light of the above discussion, the TDMA end-to-end achievable data rate on pathLi can be expressed using the well-known Shannon capacity formula as(3)CLi=B∑i=1KLiminl∈Li⁡log⁡1+PGlN0B.Note that the factor 1/∑i=1K|Li| comes from the sharing of the bandwidth equally among all links (of all routes), i.e., each link on any route is allocated a time fraction of 1/∑i=1KLi for transmission. Note also that the minimum function in (3) results from the fact that the end-to-end data rate of any path Li is equal to the data rate achieved by its bottleneck link. Using (2), the spectral efficiency of path Li can, thus, be expressed as follows:(4)RLi=1∑i=1KLiminl∈Li⁡log⁡1+PGlN0B.Consequently, the minimum spectral efficiency, Rmin, across all active routes (L1,L2,…,LK) can be expressed as(5)RminL1,L2,…,LK=1∑i=1KLiminl∈Li:i=1,2,…,K⁡log⁡1+PGlN0BNote thatlog⁡(1+PGl/N0B) can be viewed as the width of any link l. Consequently, minl∈{Li:i=1,2,…,K}log⁡(1+PGl/N0B) is the smallest link width used by the set of routes L1,L2,…,LK. In other words, the latter represents the width of the narrowest route among L1,L2,…,LK. To simplify our notation and algorithm development, we use the following substitution:(6)wL1,L2,…,LK=minl∈Li:i=1,2,…,K⁡log⁡1+PGlN0B.In other words, w(L1,L2,…,LK) is the smallest link width used by the set of routes L1,L2,…,LK; i.e., it represents the width of the narrowest route among L1,L2,…,LK using log⁡(1+PGl/N0B) as link widths. Consequently, the minimum spectral efficiency, Rmin, across all active routes (L1,L2,…,LK) can be rewritten as(7)RminL1,L2,…,LK=wL1,L2,…,LK∑i=1KLi.Therefore, the problem of jointly finding routes fors-d pairs 1,2,…,K such that the minimum spectral efficiency across all routes is maximized can be cast as the following optimization problem:(8)maxLi∈Li∀1≤i≤K⁡wL1,L2,…,LK∑i=1KLi.It is worth noting that problem (8) cannot be solved using standard shortest path methods as the resulting routing metric is not isotonic [5]. In particular, even with one s-d pair, the routing metric of (8) is not isotonic. See, e.g., [4, 6]. In what follows, we develop a polynomial-time algorithm that provides provably optimal solutions to (8).


### 3.2. Algorithm

The main idea of the proposed algorithm is an extension of the singles-d pair case [6]. In fact, even for multiple paths L1,L2,…,LK, the value of w(L1,L2,…,LK) takes one of finite possible values. It is readily seen from (6) that w(L1,L2,…,LK)∈W, where W is the set of all link widths in the network; i.e.,(9)W=log⁡1+PGlN0B:l∈E.Recall that E is the set of links in the network. Since W=M=O(N2), w(L1,L2,…,LK) can take at most M=O(N2) values.The main result follows.Theorem 1.
Let the set of routes(L1∗,L2∗,…,LK∗) denote the optimal solution to the original multicommodity spectrum-efficient routing problem (8). Let also the set of routes (L1a,L2a,…,LKa) denote the optimal solution to the following modified problem:(10)maxLi∈Li∀1≤i≤KwL1,L2,…,LK≥a⁡a∑i=1KLi.Then(11)RminL1∗,L2∗,…,LK∗=maxa∈W⁡RminL1a,L2a,…,LKa.Proof.
First, let the set of routes(L^1a,L^2a,…,L^Ka) be an optimal solution to the following subproblem:(12)maxLi∈Li∀1≤i≤KwL1,L2,…,LK=a⁡wL1,L2,…,LK∑i=1KLi.Note that (12) is the same as (8) with the additional constraint that w(L1,L2,…,LK)=a. By the divide-and-conquer principle [14], and since the union of the sets {Li∈Li:1≤i≤K,w(L1,L2,…,LK)=a}, over all possible values of a∈W, covers the route set {Li∈Li:1≤i≤K}, the following is true:(13)RminL1∗,L2∗,…,LK∗=maxa∈W⁡RminL^1a,L^2a,…,L^Ka.Note that Rmin(L1∗,L2∗,…,LK∗) and Rmin(L^1a,L^2a,…,L^Ka) represent the optimal objective function values of (8) and (12), respectively.
Moreover, by substituting the equality constraintw(L1,L2,…,LK)=a in its objective function, (12) is equivalent to(14)maxLi∈Li∀1≤i≤KwL1,L2,…,LK=a⁡a∑i=1KLi.Now, it is readily seen that (10) is a relaxation of (14). Therefore, if (L1a,L2a,…,LKa) and (L^1a,L^2a,…,L^Ka) are the optimal solutions to (10) and (14), respectively, then a/∑i=1KLia≥a/∑i=1KL^ia. The latter implies that(15)∑i=1KLia≤∑i=1KL^ia.
Now, the following is true:(16)RminL1∗,…,LK∗=maxa∈W⁡wL^1a,L^2a,…,L^Ka∑i=1KL^ia=maxa∈W⁡a∑i=1KL^ia≤maxa∈W⁡wL1a,L2a,…,LKa∑i=1KLiaNote that the first equality comes directly from (13). The second equality comes from the fact that the route set (L^1a,L^2a,…,L^Ka) is feasible for (12). The inequality comes from (15) and from the fact that the route set (L1a,L2a,…,LKa) is feasible for (10). Consequently, (16) implies that(17)RminL1∗,L2∗,…,LK∗≤maxa∈W⁡RminL1a,L2a,…,LKa.Since, among all route sets {Li∈Li:1≤i≤K}, (L1∗,L2∗,…,LK∗) is the route set which maximizes the minimum spectral efficiency, (17) must hold with strict equality. This completes the proof.In light of Theorem1, the multicommodity spectrum-efficient routing problem (8) can be solved using the following procedure:(i)
For everya∈W, find the route set(L1a,L2a,…,LKa)by solving (10).(ii)
Return the route set(L1∗,L2∗,…,LK∗)=argmaxa∈WRmin(L1a,L2a,…,LKa).Recall that, in the above procedure,W is the set of link widths given by (9), and Rmin is given by (7). The only remaining issue to show is how to solve (10). Note that, for a given a∈W, maximizing a/∑i=1KLi is equivalent to minimizing ∑i=1K|Li|. Moreover, the latter is minimized if every s-d pair i minimizes |Li|. Consequently, problem (10) is equivalent to finding the minimum-hop path for every s-d pair 1≤i≤K, such that the minimum link width across all paths is not less than a. Therefore, for a given value of a, (10) can be solved as follows:(i)
Remove all linksl∈E for which log⁡(1+PGl/N0B)<a. In the remaining graph, obtain the minimum-hop path for every s-d pair 1≤i≤K.In light of the above discussion, problem (8) can be solved by the following algorithm.Algorithm Equal-Time-Slots (1)
Let W = { log ⁡ ( 1 + P G l / N 0 B ) : l ∈ E }.For everya∈W,do:
(a)
For every s - d pair i = 1,2 , … , K,do:
(i)
Remove all links l ∈ E for which log ⁡ ( 1 + P G l / N 0 B ) < a. (ii)
In the remaining graph, find L i a, the minimum-hop path from sourcesito destinationdi. (b)
Let R m i n ( L 1 a , L 2 a , … , L K a ) = w ( L 1 a , L 2 a , … , L K a ) / ∑ i = 1 K L i a. (2)
Return the path set with largest R m i n ( L 1 a , L 2 a , … , L K a ).


### 3.3. Observations

The following observations are in order regarding algorithmEqual-Time-Slots.(i)
Step (1a) of algorithmEqual-Time-Slots can be implemented by each s-d pair independently, and without any coordination with the other s-d pairs. In particular, s-d pair i (or more precisely source node si) obtains its path Lia independently.(ii)
Step (1b), however, requires knowledge about alls-d pairs. Therefore, it can be implemented by a centralized entity which knows the hop-count |Lia| of every path Lia. Alternatively, it requires that all s-d pairs (or source nodes) exchange their information about |Lia| with all other nodes using flooding, or any other means of all-to-all communication.(iii)
At the MAC layer, the resulting set of paths will require dividing the time frame into∑i=1KLi∗equal-sized time slots. This simplicity of MAC layer scheduling comes at the expense of the necessity of coordination between s-d pairs during network-layer path computation.(iv)
The computational complexity of algorithmEqual-Time-Slots is dominated by the complexity of invoking a shortest path procedure |W|=M times, as in step (1a). Note that step (1a) can be implemented by the different s-d pairs in parallel. Since the number of links M is of O(N2), where N is the number of nodes, and if the Dijkstra shortest path algorithm is used in every iteration, the overall complexity of algorithmEqual-Time-Slots is O(N2·N2)=O(N4).


## 3.1. Problem Formulation

In light of the above discussion, the TDMA end-to-end achievable data rate on pathLi can be expressed using the well-known Shannon capacity formula as(3)CLi=B∑i=1KLiminl∈Li⁡log⁡1+PGlN0B.Note that the factor 1/∑i=1K|Li| comes from the sharing of the bandwidth equally among all links (of all routes), i.e., each link on any route is allocated a time fraction of 1/∑i=1KLi for transmission. Note also that the minimum function in (3) results from the fact that the end-to-end data rate of any path Li is equal to the data rate achieved by its bottleneck link. Using (2), the spectral efficiency of path Li can, thus, be expressed as follows:(4)RLi=1∑i=1KLiminl∈Li⁡log⁡1+PGlN0B.Consequently, the minimum spectral efficiency, Rmin, across all active routes (L1,L2,…,LK) can be expressed as(5)RminL1,L2,…,LK=1∑i=1KLiminl∈Li:i=1,2,…,K⁡log⁡1+PGlN0BNote thatlog⁡(1+PGl/N0B) can be viewed as the width of any link l. Consequently, minl∈{Li:i=1,2,…,K}log⁡(1+PGl/N0B) is the smallest link width used by the set of routes L1,L2,…,LK. In other words, the latter represents the width of the narrowest route among L1,L2,…,LK. To simplify our notation and algorithm development, we use the following substitution:(6)wL1,L2,…,LK=minl∈Li:i=1,2,…,K⁡log⁡1+PGlN0B.In other words, w(L1,L2,…,LK) is the smallest link width used by the set of routes L1,L2,…,LK; i.e., it represents the width of the narrowest route among L1,L2,…,LK using log⁡(1+PGl/N0B) as link widths. Consequently, the minimum spectral efficiency, Rmin, across all active routes (L1,L2,…,LK) can be rewritten as(7)RminL1,L2,…,LK=wL1,L2,…,LK∑i=1KLi.Therefore, the problem of jointly finding routes fors-d pairs 1,2,…,K such that the minimum spectral efficiency across all routes is maximized can be cast as the following optimization problem:(8)maxLi∈Li∀1≤i≤K⁡wL1,L2,…,LK∑i=1KLi.It is worth noting that problem (8) cannot be solved using standard shortest path methods as the resulting routing metric is not isotonic [5]. In particular, even with one s-d pair, the routing metric of (8) is not isotonic. See, e.g., [4, 6]. In what follows, we develop a polynomial-time algorithm that provides provably optimal solutions to (8).


## 3.2. Algorithm

The main idea of the proposed algorithm is an extension of the singles-d pair case [6]. In fact, even for multiple paths L1,L2,…,LK, the value of w(L1,L2,…,LK) takes one of finite possible values. It is readily seen from (6) that w(L1,L2,…,LK)∈W, where W is the set of all link widths in the network; i.e.,(9)W=log⁡1+PGlN0B:l∈E.Recall that E is the set of links in the network. Since W=M=O(N2), w(L1,L2,…,LK) can take at most M=O(N2) values.The main result follows.Theorem 1.
Let the set of routes(L1∗,L2∗,…,LK∗) denote the optimal solution to the original multicommodity spectrum-efficient routing problem (8). Let also the set of routes (L1a,L2a,…,LKa) denote the optimal solution to the following modified problem:(10)maxLi∈Li∀1≤i≤KwL1,L2,…,LK≥a⁡a∑i=1KLi.Then(11)RminL1∗,L2∗,…,LK∗=maxa∈W⁡RminL1a,L2a,…,LKa.Proof.
First, let the set of routes(L^1a,L^2a,…,L^Ka) be an optimal solution to the following subproblem:(12)maxLi∈Li∀1≤i≤KwL1,L2,…,LK=a⁡wL1,L2,…,LK∑i=1KLi.Note that (12) is the same as (8) with the additional constraint that w(L1,L2,…,LK)=a. By the divide-and-conquer principle [14], and since the union of the sets {Li∈Li:1≤i≤K,w(L1,L2,…,LK)=a}, over all possible values of a∈W, covers the route set {Li∈Li:1≤i≤K}, the following is true:(13)RminL1∗,L2∗,…,LK∗=maxa∈W⁡RminL^1a,L^2a,…,L^Ka.Note that Rmin(L1∗,L2∗,…,LK∗) and Rmin(L^1a,L^2a,…,L^Ka) represent the optimal objective function values of (8) and (12), respectively.
Moreover, by substituting the equality constraintw(L1,L2,…,LK)=a in its objective function, (12) is equivalent to(14)maxLi∈Li∀1≤i≤KwL1,L2,…,LK=a⁡a∑i=1KLi.Now, it is readily seen that (10) is a relaxation of (14). Therefore, if (L1a,L2a,…,LKa) and (L^1a,L^2a,…,L^Ka) are the optimal solutions to (10) and (14), respectively, then a/∑i=1KLia≥a/∑i=1KL^ia. The latter implies that(15)∑i=1KLia≤∑i=1KL^ia.
Now, the following is true:(16)RminL1∗,…,LK∗=maxa∈W⁡wL^1a,L^2a,…,L^Ka∑i=1KL^ia=maxa∈W⁡a∑i=1KL^ia≤maxa∈W⁡wL1a,L2a,…,LKa∑i=1KLiaNote that the first equality comes directly from (13). The second equality comes from the fact that the route set (L^1a,L^2a,…,L^Ka) is feasible for (12). The inequality comes from (15) and from the fact that the route set (L1a,L2a,…,LKa) is feasible for (10). Consequently, (16) implies that(17)RminL1∗,L2∗,…,LK∗≤maxa∈W⁡RminL1a,L2a,…,LKa.Since, among all route sets {Li∈Li:1≤i≤K}, (L1∗,L2∗,…,LK∗) is the route set which maximizes the minimum spectral efficiency, (17) must hold with strict equality. This completes the proof.In light of Theorem1, the multicommodity spectrum-efficient routing problem (8) can be solved using the following procedure:(i)
For everya∈W, find the route set(L1a,L2a,…,LKa)by solving (10).(ii)
Return the route set(L1∗,L2∗,…,LK∗)=argmaxa∈WRmin(L1a,L2a,…,LKa).Recall that, in the above procedure,W is the set of link widths given by (9), and Rmin is given by (7). The only remaining issue to show is how to solve (10). Note that, for a given a∈W, maximizing a/∑i=1KLi is equivalent to minimizing ∑i=1K|Li|. Moreover, the latter is minimized if every s-d pair i minimizes |Li|. Consequently, problem (10) is equivalent to finding the minimum-hop path for every s-d pair 1≤i≤K, such that the minimum link width across all paths is not less than a. Therefore, for a given value of a, (10) can be solved as follows:(i)
Remove all linksl∈E for which log⁡(1+PGl/N0B)<a. In the remaining graph, obtain the minimum-hop path for every s-d pair 1≤i≤K.In light of the above discussion, problem (8) can be solved by the following algorithm.Algorithm Equal-Time-Slots (1)
Let W = { log ⁡ ( 1 + P G l / N 0 B ) : l ∈ E }.For everya∈W,do:
(a)
For every s - d pair i = 1,2 , … , K,do:
(i)
Remove all links l ∈ E for which log ⁡ ( 1 + P G l / N 0 B ) < a. (ii)
In the remaining graph, find L i a, the minimum-hop path from sourcesito destinationdi. (b)
Let R m i n ( L 1 a , L 2 a , … , L K a ) = w ( L 1 a , L 2 a , … , L K a ) / ∑ i = 1 K L i a. (2)
Return the path set with largest R m i n ( L 1 a , L 2 a , … , L K a ).


## 3.3. Observations

The following observations are in order regarding algorithmEqual-Time-Slots.(i)
Step (1a) of algorithmEqual-Time-Slots can be implemented by each s-d pair independently, and without any coordination with the other s-d pairs. In particular, s-d pair i (or more precisely source node si) obtains its path Lia independently.(ii)
Step (1b), however, requires knowledge about alls-d pairs. Therefore, it can be implemented by a centralized entity which knows the hop-count |Lia| of every path Lia. Alternatively, it requires that all s-d pairs (or source nodes) exchange their information about |Lia| with all other nodes using flooding, or any other means of all-to-all communication.(iii)
At the MAC layer, the resulting set of paths will require dividing the time frame into∑i=1KLi∗equal-sized time slots. This simplicity of MAC layer scheduling comes at the expense of the necessity of coordination between s-d pairs during network-layer path computation.(iv)
The computational complexity of algorithmEqual-Time-Slots is dominated by the complexity of invoking a shortest path procedure |W|=M times, as in step (1a). Note that step (1a) can be implemented by the different s-d pairs in parallel. Since the number of links M is of O(N2), where N is the number of nodes, and if the Dijkstra shortest path algorithm is used in every iteration, the overall complexity of algorithmEqual-Time-Slots is O(N2·N2)=O(N4).


## 4. Variable-Sized Time Slots

An alternative approach to accommodating multiples-d pairs under the condition of equal bandwidth sharing is to divide the time frame equally among s-dpairs (as opposed to dividing the time equally among thelinks). In other words, every s-d pair/path will transmit for a fraction of 1/K of the time (assuming Ks-d pairs). Consequently, if s-d pair i uses path Li, then every link along this path will transmit for a fraction of 1/K|Li| of the time. Since different s-d pairs may use paths with different hop-counts, their respective links may use time slots of different sizes.In this case, the end-to-end spectral efficiency of routeLi serving s-d pair i can be expressed as(18)RLi=1KLiminl∈Li⁡log⁡1+PGlN0B.Note that the factor 1/K|Li| comes from the fact that every link l∈Li transmits for a fraction of 1/K|Li| of the time. Note also that the minimum function in (18) results from the fact that the end-to-end data rate of any path Li is equal to the data rate achieved by its bottleneck link. It is worth noting that the spectral efficiency for s-d pair i depends on the hop-count |Li| of its own path Li only. This is in contrast to the case of equal time slots, where the spectral efficiency for any s-d pair i depends on the hop-counts of all s-d paths L1,L2,…,ŁK.The problem of maximizing the minimum spectral efficiency across alls-d pairs can, thus, be expressed as(19)maxLi∈Li∀1≤i≤K⁡min1≤i≤K⁡RLi,where R(Li) is given by (18). It is not hard to see that the minimum spectrum efficiency will be maximized if every s-d pair i maximizes its individual spectral efficiency R(Li). In other words, every s-d pair i solves the following optimization problem:(20)maxLi∈Li⁡1KLiminl∈Li⁡log⁡1+PGlN0B.Moreover, since, for any number of s-d pairs, K is a constant, solving (20) is equivalent to solving the single s-d pair problem. The best known algorithm for solving (20) has been introduced in [8], and can be summarized as follows.Algorithm Variable-Time-SlotsFor every s-dpairi=1,2,…,K,do:(1)
Forh=1,2,…,N-1,do:
(a)
FindLih, the widest path with at mosthhops connectingsitodi, usinglog⁡(1+PGl/N0B)as link labels.(b)
LetR(Lih)=1/KLihminl∈Lihlog⁡(1+PGl/N0B).(2)
Return the path with largestR(Lih).The following observations are in order regarding algorithmVariable-Time-Slots.(i)
The algorithm can be implemented by eachs-d pair in a completely independent manner. In other words, s-d pairs are completely isolated and there is no need for coordination and/or a centralized component.(ii)
The number ofs-d pairs K does not affect the computation of the optimal paths. In particular, for any number of s-d pairs, K is a constant, and thus(21)argmaxLi∈Li⁡1KLiminl∈Li⁡log⁡1+PGlN0B=argmaxLi∈Li⁡1Liminl∈Li⁡log⁡1+PGlN0B.In other words, everys-d pair computes its optimal path regardless of how many other s-d pairs exist, and the optimal paths do not change with the change of the number of s-d pairs.(iii)
The number ofs-d pairs K, however, is needed for MAC layer scheduling. In particular, every s-d pair transmits for 1/K of the time, and every link l∈Li used by s-d pair i transmits for a fraction of 1/K|Li| of the time.(iv)
Since the paths used by differents-d pairs may have different hop-counts, the resulting time slots may be of different durations.(v)
The algorithm can be implemented by the differents-d pairs in parallel. Note also that shortest path algorithms can be modified to compute the widest path. See, e.g., [15]. Moreover, it is worth noticing that the Bellman-Ford shortest path algorithm, in its hth iteration, computes the shortest (or widest) path with at most h hops. Consequently, algorithmVariable-Time-Slots can be implemented by invoking the Bellman-Ford procedure onlyonce. The overall complexity of algorithmVariable-Time-Slots is, thus, O(N3).Note thatdynamically partitioning the TDMA frame into a set ofvariable-length transmission slots is possible. See, e.g., [9, 16]. As an example of the resulting MAC strategy, let the number of s-d pairs be 3. Assume also that applying algorithmVariable-Time-Slots results in paths L1, L2, and L3 for the 3 s-d pairs, where L1=3, L2=2, and L3=4, respectively. The time frame will, thus, be divided into 3+2+4=9 slots. The normalized slot size is 1/(3×3)=1/9 for the first 3 slots (used by path L1), 1/(3×2)=1/6 for the following 2 slots (used by path L2), and 1/(3×4)=1/12 for the last 4 slots (used by path L3). In other words, the normalized sizes of the 9 slots are 1/9, 1/9, 1/9, 1/6, 1/6, 1/12, 1/12, 1/12, and 1/12, respectively.In contrast, however, assume that algorithmEqual-Time-Slots results in paths L1, L2, and L3 for the 3 s-d pairs, where L1=3, L2=2, and L3=4, respectively. In this case, the time frame will be divided into 3+2+4=9 slots, where the normalized size of each slot is precisely 1/9.


## 5. Tradeoffs

In this section we summarize the main differences and tradeoffs between algorithmsEqual-Time-Slots andVariable-Time-Slots.(i)
Distributed implementation: algorithmEqual-Time-Slots has a component that requires centralized knowledge of the paths computed byalls-d pairs (in every iteration of the algorithm). Alternatively, coordination and exchange of information is required among s-d pairs. AlgorithmVariable-Time-Slots, however, can be implemented in a fully distributed fashion among s-d pairs. No coordination is required among s-d pairs in their path computation.(ii)
Synchronization: as described above, algorithmEqual-Time-Slots is based on the centralized (or coordinated) knowledge of the paths Lia for all s-d pairs i=1,2,…,K. This implicitly implies that all existing s-d pairs must make their path computation decisions (i.e., invoke their algorithms) in a synchronized way; any s-d pair cannot obtain its optimal path without the results of the other s-d pairs. AlgorithmVariable-Time-Slots, however, does not require this synchronization. Any s-d pair can compute its optimal path regardless of the other s-d pairs. In fact, optimal path computation does not even require the knowledge of the number of existing s-d pairs K. The optimal path in case of onlyones-d pair would remain optimal in the presence ofany number of s-d pairs K. Knowing K is necessary in the transmission (MAC) scheduling phase only.(iii)
MAC scheduling: algorithmEqual-Time-Slots results in TDMA transmission frames with equal time slots, while algorithmVariable-Time-Slots results in TDMA transmission frames with variable time slots.(iv)
Complexity: the complexity ofEqual-Time-Slots is O(N4), while the complexity ofVariable-Time-Slots is O(N3).It is worth noting that both algorithms (Equal-Time-Slots andVariable-Time-Slots) require the value of the link SNRs (PGl/N0B) to be known at the source nodes computing their respective paths. In practice, the link SNR can be directly measured by received signal strength indicators available on most devices [4], and fed back to the transmitters. Nodes can then exchange their knowledge about the values of PGl/N0B for their outgoing links using adistributed link-state protocol. Please refer to [9] for further elaboration.In the following section we provide a numerical study on the performance of both proposed approaches and their tradeoffs.


## 6. Numerical Results

We consider multihop wireless networks, in which the nodes are located at random positions in a 100× 100 two-dimensional area. Without loss of generality, it is assumed that any two nodes can directly communicate; i.e., the network is fully connected. Note that, from an information theoretic point of view, two nodes can always communicate at a sufficiently low rate [4, 17]. The path gain Gl of each link l is assumed to be given by (22)Gl=c·Al·max⁡dl,d0-4,where dl is the length of link l, d0 is the reference distance for the far-field, Al is a log-normally distributed random variable (with 0-dB mean and 8-dB log-variance) that reflects shadowing, and c is a constant. Without loss of generality, we set d0=0.1 and c=0.01. We test our proposed algorithms onrandom andindependent network realizations, where in each realization the horizontal and vertical coordinates of each node are chosen randomly (and independently) according to a uniform distribution between 0 and 100, and the path gains are generated randomly (and independently) according to (22). Among the randomly generated nodes, a set of s-d pairs is chosen at random. Furthermore, for each tested scenario, we average our results over 104 random network realizations. In other words,every point in each of the following result figures is averaged over104random network realizations.The simulation parameters are summarized in Table1 (note that E(·) and V(·) denote the expected value and variance of a random variable, respectively).Table 1
Simulation parameters.
Parameter Value Path gain (Gl) Equation (22) Path gain constant (c) 0.01 Far-field reference distance (d0) 0.1 Shadowing (Al) log-normal distribution E(10log⁡Al) 0 dB V(10log⁡Al) 8 dB Node positions random in 100× 100 area Number of nodes (N) 5 to 30 Number ofs-d pairs (K) 5 to 20 Network SNR (P/N0B) -20 dB to 80 dB Simulation software MATLAB R2017a


### 6.1. Effect of the Network Size

First, we vary the number of nodes in the network (N) from 5 to 30. For every value of N, we let the number of s-d pairs (K) be 5, and we set the network SNR (P/N0B) to 80 dB. Figure 1 depicts theminimum spectral efficiency among all s-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively. It is clearly seen that algorithmEqual-Time-Slots results in higher worst-case spectral efficiencies. In particular, the minimum source-destination (s-d) spectral efficiency resulting from algorithmEqual-Time-Slots is from 29.23% to 39.2% higher than that of algorithmVariable-Time-Slots. Averaged over all experiments for different values of N, the minimum s-d spectral efficiency resulting from algorithmEqual-Time-Slots is 36% higher than that of algorithmVariable-Time-Slots.Figure 1
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of network nodes.Moreover, Figure2 depicts theaverage spectral efficiency across all s-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively. It is straightforward to see that algorithmVariable-Time-Slots results in higher average spectral efficiencies. In particular, the average s-d spectral efficiency resulting from algorithmVariable-Time-Slots is from 29.88% to 64.2% higher than that of algorithmEqual-Time-Slots. Averaged over all experiments for different values of N, the average s-d spectral efficiency resulting from algorithmVariable-Time-Slots is 57.27% higher than that of algorithmEqual-Time-Slots. In short, although algorithmEqual-Time-Slots has a better worst-case performance (as seen in Figure 1), algorithmVariable-Time-Slots has a significantly better average performance (as seen in Figure 2).Figure 2
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of network nodes.Finally, we provide a comparison between the running times of algorithmsEqual-Time-Slots andVariable-Time-Slots per s-d pair. For fairness of comparison, we compare the overall running time of algorithmVariable-Time-Slots with the running time of the distributed component of algorithmEqual-Time-Slots (i.e., Step (1a), which can be implemented by each s-d pair in isolation). In other words, the running time of the centralized component of algorithmEqual-Time-Slots is excluded from the comparison. The running times of both algorithms are depicted in Figure 3. In fact, the (per s-d pair) average running time of algorithmVariable-Time-Slots is 0.44 milliseconds, while that of algorithmEqual-Time-Slots is 0.13 seconds. In other words, although the centralized component of algorithmEqual-Time-Slots was not considered in this comparison, the running time of algorithmVariable-Time-Slots is on average 99.23% lower than that of algorithmEqual-Time-Slots.Figure 3
Running times of algorithmsEqual-Time-Slots andVariable-Time-Slots.


### 6.2. Effect of Number ofs-d Pairs

Now, we vary the number ofs-d pairs (K) from 5 to 20, while the number of nodes is fixed at N=20 and the network SNR is fixed at 80 dB. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 4 and 5, respectively. Again, it can be easily seen that algorithmEqual-Time-Slots has a better worst-case performance (as seen in Figure 4), while algorithmVariable-Time-Slots has a significantly better average performance (as seen in Figure 5). In particular, the minimum spectral efficiency across all s-d routes obtained by algorithmEqual-Time-Slots is from 38.17% to 59.66% higher than that obtained by algorithmVariable-Time-Slots. Averaged over all experiments, the minimum spectral efficiency resulting from algorithmEqual-Time-Slots is 50.62% higher than that resulting from algorithmVariable-Time-Slots. On the other hand, the average spectral efficiency across all s-d routes resulting from algorithmVariable-Time-Slots is from 62.29% to 78.19% higher than that resulting from algorithmVariable-Time-Slots. Averaged over all experiments, algorithmVariable-Time-Slots results in 73.50% higher average spectral efficiencies than algorithmEqual-Time-Slots.Figure 4
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of s-d pairs.Figure 5
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of s-d pairs.


### 6.3. Effect of the Network SNR

Now, we vary the network SNR from -20 dB to 80 dB, while the number of nodes is fixed atN=20 and the number of s-d pairs is fixed at K=5. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 6 and 7, respectively. In consistency with all other results, algorithmEqual-Time-Slots consistently shows a better worst-case performance (as seen in Figure 6), while algorithmVariable-Time-Slots shows a consistently and significantly better average performance (as seen in Figure 7). In particular, the improvement inworst-case spectral efficiencies due to algorithmEqual-Time-Slots is between 37.96% and 38.24% (with an average improvement of 37.93% across all experiments). However, the improvement inaverage spectral efficiencies due to algorithmVariable-Time-Slots is between 65.18% and 136.37% (with an average improvement of 129.20% across all experiments).Figure 6
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the network SNR.Figure 7
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the network SNR.


### 6.4. Comparison against Benchmarks

Finally, we assess the performance of our proposed algorithms in comparison to existing techniques. To this end, we use the following two benchmarks.(i)
We compare our algorithms against the spectral efficiency resulting from routing everys-d pair along the direct link from s to d. Since all resulting routes are one hop long, dividing the time frame equally between s-d pairs or between transmission links is equivalent. Therefore, direct link routing is compared against both proposed algorithmsEqual-Time-Slots andVariable-Time-Slots.(ii)
We also compare our algorithms against the spectral efficiency resulting from routing everys-d pairindependently using the distributed spectrum-efficient routing (DSER) algorithm introduced in [4]. DSER [4] operates by simply finding a shortest path from the source to the destination using (1+2γ/SNRl) as the link metric, where γ is the path-loss exponent. Here, γ=4. It is assumed that the time frame is divided equally among s-d pairs, resulting in variable-length time slots for individual link transmissions. Therefore, DSER is compared against our proposed algorithmVariable-Time-Slots.To compare them against direct link routing, we vary the number ofs-d pairs K from 5 to 20, while the number of nodes is fixed at N=20 and the network SNR is fixed at 80 dB. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 8 and 9, respectively. Following the same trend, algorithmEqual-Time-Slots shows a better worst-case performance, while algorithmVariable-Time-Slots shows a better average performance. In particular, the worst-case spectral efficiency resulting from algorithmEqual-Time-Slots is 820% to 2500% higher than that resulting from direct routing (with an average improvement of 1724% across all experiments). Moreover, the average spectral efficiency resulting from algorithmVariable-Time-Slots is about 30% higher than that resulting from direct routing in all experiments.Figure 8
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots compared against direct link routing.Figure 9
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots compared against direct link routing.To compare against DSER from [4], we vary the number of nodes in the network (N) from 5 to 30, while the number of s-d pairs (K) is set to 5 and the network SNR is set to 80 dB. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 10 and 11, respectively. The superior performance of our proposed algorithmVariable-Time-Slots is clearly seen. In particular, our algorithm results in 93% to 743% higher worst-case spectral efficiencies as compared to direct link routing (with an average improvement of 446% across all experiments) and results in 16% to 68% higher worst-case spectral efficiencies as compared to DSER (with an average improvement of 45% across all experiments). Moreover, our algorithm results in 6.5% to 39% higher average spectral efficiencies as compared to direct link routing (with an average improvement of 24% across all experiments) and results in 2.9% to 27% higher average spectral efficiencies as compared to DSER (with an average improvement of 15% across all experiments).Figure 10
Minimum spectral efficiency among alls-d routes obtained using algorithmVariable-Time-Slots compared against DSER from [4] and direct link routing.Figure 11
Average spectral efficiency among alls-d routes obtained using algorithmVariable-Time-Slots compared against DSER from [4] and direct link routing.In summary, all our experiments (of varying the network size, number ofs-d pairs, and network SNR) indicate a similar trend of a better worst-case performance for algorithmEqual-Time-Slots versus a better average/typical performance for algorithmVariable-Time-Slots. It is worth noting, however, that the improvement in average results due to algorithmVariable-Time-Slots is always more significant. Moreover, algorithmVariable-Time-Slots enjoys a significantly (more than 99%) lower running time. Moreover, our proposed algorithmVariable-Time-Slots has shown a significantly superior worst-case and average performance as compared to DSER from [4], and as compared to direct link routing.


## 6.1. Effect of the Network Size

First, we vary the number of nodes in the network (N) from 5 to 30. For every value of N, we let the number of s-d pairs (K) be 5, and we set the network SNR (P/N0B) to 80 dB. Figure 1 depicts theminimum spectral efficiency among all s-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively. It is clearly seen that algorithmEqual-Time-Slots results in higher worst-case spectral efficiencies. In particular, the minimum source-destination (s-d) spectral efficiency resulting from algorithmEqual-Time-Slots is from 29.23% to 39.2% higher than that of algorithmVariable-Time-Slots. Averaged over all experiments for different values of N, the minimum s-d spectral efficiency resulting from algorithmEqual-Time-Slots is 36% higher than that of algorithmVariable-Time-Slots.Figure 1
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of network nodes.Moreover, Figure2 depicts theaverage spectral efficiency across all s-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively. It is straightforward to see that algorithmVariable-Time-Slots results in higher average spectral efficiencies. In particular, the average s-d spectral efficiency resulting from algorithmVariable-Time-Slots is from 29.88% to 64.2% higher than that of algorithmEqual-Time-Slots. Averaged over all experiments for different values of N, the average s-d spectral efficiency resulting from algorithmVariable-Time-Slots is 57.27% higher than that of algorithmEqual-Time-Slots. In short, although algorithmEqual-Time-Slots has a better worst-case performance (as seen in Figure 1), algorithmVariable-Time-Slots has a significantly better average performance (as seen in Figure 2).Figure 2
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of network nodes.Finally, we provide a comparison between the running times of algorithmsEqual-Time-Slots andVariable-Time-Slots per s-d pair. For fairness of comparison, we compare the overall running time of algorithmVariable-Time-Slots with the running time of the distributed component of algorithmEqual-Time-Slots (i.e., Step (1a), which can be implemented by each s-d pair in isolation). In other words, the running time of the centralized component of algorithmEqual-Time-Slots is excluded from the comparison. The running times of both algorithms are depicted in Figure 3. In fact, the (per s-d pair) average running time of algorithmVariable-Time-Slots is 0.44 milliseconds, while that of algorithmEqual-Time-Slots is 0.13 seconds. In other words, although the centralized component of algorithmEqual-Time-Slots was not considered in this comparison, the running time of algorithmVariable-Time-Slots is on average 99.23% lower than that of algorithmEqual-Time-Slots.Figure 3
Running times of algorithmsEqual-Time-Slots andVariable-Time-Slots.


## 6.2. Effect of Number ofs-d Pairs

Now, we vary the number ofs-d pairs (K) from 5 to 20, while the number of nodes is fixed at N=20 and the network SNR is fixed at 80 dB. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 4 and 5, respectively. Again, it can be easily seen that algorithmEqual-Time-Slots has a better worst-case performance (as seen in Figure 4), while algorithmVariable-Time-Slots has a significantly better average performance (as seen in Figure 5). In particular, the minimum spectral efficiency across all s-d routes obtained by algorithmEqual-Time-Slots is from 38.17% to 59.66% higher than that obtained by algorithmVariable-Time-Slots. Averaged over all experiments, the minimum spectral efficiency resulting from algorithmEqual-Time-Slots is 50.62% higher than that resulting from algorithmVariable-Time-Slots. On the other hand, the average spectral efficiency across all s-d routes resulting from algorithmVariable-Time-Slots is from 62.29% to 78.19% higher than that resulting from algorithmVariable-Time-Slots. Averaged over all experiments, algorithmVariable-Time-Slots results in 73.50% higher average spectral efficiencies than algorithmEqual-Time-Slots.Figure 4
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of s-d pairs.Figure 5
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the number of s-d pairs.


## 6.3. Effect of the Network SNR

Now, we vary the network SNR from -20 dB to 80 dB, while the number of nodes is fixed atN=20 and the number of s-d pairs is fixed at K=5. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 6 and 7, respectively. In consistency with all other results, algorithmEqual-Time-Slots consistently shows a better worst-case performance (as seen in Figure 6), while algorithmVariable-Time-Slots shows a consistently and significantly better average performance (as seen in Figure 7). In particular, the improvement inworst-case spectral efficiencies due to algorithmEqual-Time-Slots is between 37.96% and 38.24% (with an average improvement of 37.93% across all experiments). However, the improvement inaverage spectral efficiencies due to algorithmVariable-Time-Slots is between 65.18% and 136.37% (with an average improvement of 129.20% across all experiments).Figure 6
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the network SNR.Figure 7
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots, respectively, versus the network SNR.


## 6.4. Comparison against Benchmarks

Finally, we assess the performance of our proposed algorithms in comparison to existing techniques. To this end, we use the following two benchmarks.(i)
We compare our algorithms against the spectral efficiency resulting from routing everys-d pair along the direct link from s to d. Since all resulting routes are one hop long, dividing the time frame equally between s-d pairs or between transmission links is equivalent. Therefore, direct link routing is compared against both proposed algorithmsEqual-Time-Slots andVariable-Time-Slots.(ii)
We also compare our algorithms against the spectral efficiency resulting from routing everys-d pairindependently using the distributed spectrum-efficient routing (DSER) algorithm introduced in [4]. DSER [4] operates by simply finding a shortest path from the source to the destination using (1+2γ/SNRl) as the link metric, where γ is the path-loss exponent. Here, γ=4. It is assumed that the time frame is divided equally among s-d pairs, resulting in variable-length time slots for individual link transmissions. Therefore, DSER is compared against our proposed algorithmVariable-Time-Slots.To compare them against direct link routing, we vary the number ofs-d pairs K from 5 to 20, while the number of nodes is fixed at N=20 and the network SNR is fixed at 80 dB. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 8 and 9, respectively. Following the same trend, algorithmEqual-Time-Slots shows a better worst-case performance, while algorithmVariable-Time-Slots shows a better average performance. In particular, the worst-case spectral efficiency resulting from algorithmEqual-Time-Slots is 820% to 2500% higher than that resulting from direct routing (with an average improvement of 1724% across all experiments). Moreover, the average spectral efficiency resulting from algorithmVariable-Time-Slots is about 30% higher than that resulting from direct routing in all experiments.Figure 8
Minimum spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots compared against direct link routing.Figure 9
Average spectral efficiency among alls-d routes obtained using algorithmsEqual-Time-Slots andVariable-Time-Slots compared against direct link routing.To compare against DSER from [4], we vary the number of nodes in the network (N) from 5 to 30, while the number of s-d pairs (K) is set to 5 and the network SNR is set to 80 dB. The results for minimum and average spectral efficiencies across all s-d routes are depicted in Figures 10 and 11, respectively. The superior performance of our proposed algorithmVariable-Time-Slots is clearly seen. In particular, our algorithm results in 93% to 743% higher worst-case spectral efficiencies as compared to direct link routing (with an average improvement of 446% across all experiments) and results in 16% to 68% higher worst-case spectral efficiencies as compared to DSER (with an average improvement of 45% across all experiments). Moreover, our algorithm results in 6.5% to 39% higher average spectral efficiencies as compared to direct link routing (with an average improvement of 24% across all experiments) and results in 2.9% to 27% higher average spectral efficiencies as compared to DSER (with an average improvement of 15% across all experiments).Figure 10
Minimum spectral efficiency among alls-d routes obtained using algorithmVariable-Time-Slots compared against DSER from [4] and direct link routing.Figure 11
Average spectral efficiency among alls-d routes obtained using algorithmVariable-Time-Slots compared against DSER from [4] and direct link routing.In summary, all our experiments (of varying the network size, number ofs-d pairs, and network SNR) indicate a similar trend of a better worst-case performance for algorithmEqual-Time-Slots versus a better average/typical performance for algorithmVariable-Time-Slots. It is worth noting, however, that the improvement in average results due to algorithmVariable-Time-Slots is always more significant. Moreover, algorithmVariable-Time-Slots enjoys a significantly (more than 99%) lower running time. Moreover, our proposed algorithmVariable-Time-Slots has shown a significantly superior worst-case and average performance as compared to DSER from [4], and as compared to direct link routing.


## 7. Conclusion

To the best of our knowledge, previous work on finding the path with maximum end-to-end spectrum efficiency was restricted to a singles-d pair. This paper proposed two alternative approaches for the spectrum-efficient routing problem in the multicommodity flow regime, i.e., in the case of multiple active s-d pairs. The routing objective was to maximize the minimum spectrum efficiency achieved across all active s-d pairs. The first approach was based on dividing the time frame into equal-sized slots, while the second approach allows dividing the time frame into variable-sized slots. For each approach, we derived theprovably optimal routing algorithm. We also shed the light on the arising tradeoff between the resulting routing algorithms. In summary, the routing algorithm induced by equal time slots enjoys a better worst-case performance (i.e., higher worst-case spectrum efficiencies), at the price of a higher computational complexity and the existence of a centralized component requiring coordination and synchronization among all s-d pairs in the route computation phase. However, the routing algorithm induced by variable time slots has the advantages of (1) a significantly lower computational complexity (more than 99% reduction in running time), (2) a significantly better average/typical performance (i.e., higher average achieved spectral efficiencies), (3) a significantly better worst-case and average spectral efficiency performance as compared to existing methods, and (4) being entirely distributed with no need for coordination or synchronization among s-d pairs. In fact the routing algorithm induced by variable time slots does not even require the knowledge of the number of active s-d pairs; the optimal path in case of the existence of a single s-d pair remains optimal in case of any number of s-d pairs. Knowledge of the number s-d pairs is required only in the phase of MAC layer scheduling of time slots. This concludes that algorithmVariable-Time-Slots might be preferred for practical implementation.



---

*Source: 7985756-2018-07-09.xml*