Abstract
We present a novel control policy, called Predictive Network Control (PNC) to control wireless communication networks on packet level, based on paradigms of Model Predictive Control (MPC). In contrast to common myopic policies, who use one step ahead prediction, PNC predicts the future behavior of the system for an extended horizon, thus facilitating performance gains. We define an advanced system model in which we use a Markov chain in combination with a Bernoulli trial to model the stochastic components of the network. Furthermore, we introduce the algorithm and present two detailed simulation examples, which show general improved performance and a gain in stability region compared to the standard MaxWeight policy.
I. INTRODUCTION AND MOTIVATION
Modern wireless networks, such as 5G, have an increasing amount of options to route packets to multiple nodes, making information flow control essential for throughput performance, e.g. to avoid bottlenecks due to cell overload, or to exploit diversity of wireless links for low latency communication [1] . Seminal work on wireless network control was published in [2] in 1992 and introduced the so called MaxWeight policy (MW). This policy still stands as a benchmark and was improved upon many times, e.g. in [3] and [4] . However, MW and all its deviations are of the myopic type [5] . This means, they only make decisions based on immediate next step system changes (while using a time discrete network description which is the most convenient model due to clocked devices in reality). Although not without its flaws (e.g. large delays of single packets under low workload [6] ), this approach used to be reasonable due to limited amount of computational resources and high pace requirements. Espiecally in simple network topologies (e.g. boradcasting), these policies are well studied [7] . Nowadays though, with advancements in computational power, we have the option of using more mathematically ambitious algorithms to devise policies that can improve on the network behavior. Initial attempts in this direction were made in [8] , where in each time slot a draining problem is solved to minimize delay for an OFDM broadcast channel.
In this paper, we introduce a new network control policy, that we call Predictive Network Control (PNC). Herein we use paradigms from the field of Model Predictive Control (MPC) [9] , to devise a policy that predicts the system behavior for multiple steps into the future. While we gain improvements in performance, this approach additionally produces a schedule of predicted communications which seems very intriguing for implementation into Cyber Physical Systems, where control and communication merge together.
This work is dedicated to present the new policy together with the utilized system model. We omit analytical results for later publications but provide numerical results which indicate inferiority of MW, in terms of performance and overall stability.
In the next sections, we will use upper case letters for matrices (M ) and cost functions (J), bold ones for sets (S) or probability operators (P[·]) and lower case for everything else.
II. SYSTEM MODEL
We concentrate on the fairly common case of a discretetime, packet-level communication network, where we have an arbitrary number of entities sending information to one another [5] . Additionally, information may enter or leave the whole system. If an entity receives more information than it can send, it has to store it in a buffer. The amount of information in that buffer we call the queue length q
Considering all entities at once, we get the queue-vector q t ∈ N n , n being the number of all buffers. It is possible that one entity keeps multiple buffers, e.g. if the received information is of different type. This will simply result in n being larger than the number of entities. Between the entities there exist so called communication links as column vectors. E.g. the vector −1 1 0 . . . 0 T would send information from the first buffer (decreasing its size by 1) to the second buffer (increasing its size by 1). These m vectors collected side by side form the system-matrix B t . We can influence the network by deciding, which links are to be activated at the current time. For that, we use the binary inputor control-vector u t ∈ {0, 1} m . The system evolution can then be expressed as
where B t ∈ Z n×m is discrete valued. Information leaves the system, when columns are activated, that possess more negative than positive entries. This represents the information reaching its intended destination, which is the goal of any controller. In contrast, the arrival-vector a t ∈ N n represents 9781538614785/18/$31.00 © 2018 IEEE an information influx by simply increasing q t (usually in a stochastic way). Its time averageā = E [a] ∈ R n + we call the arrival-rate, which is pivotal for system stability.
If every possible communication link (column of B t ) could be activated at the same time, there would be no need to steer the system. However, in reality some of these links might not be available at the same time, because they share the same communication channels (which have a limited capacity). These disjunct links can be encoded in the constituency-matrix C which limits the control decisions through Cu t ≤ 1 (with 1 being the vector of ones, with appropriate dimension). This means, that the controller is usually left with the decision of which information to route first. While this system model is mostly in alignment to the usual one [2] , we now introduce some novel features, that aim to model especially wireless communication more accurately.
(F1) we allow our links (columns of B t ) to have discrete values (in contrast to the usual binary ones). This allows information of different type to have different size or different importance since high entries in a communication link will mean faster transportation.
(F2) we allow each column of B t to have multiple positive and negative entries and define that we can not activate a link, when (due to the system evolution) at least one entry of q t would become negative. The second part is equal to the control restriction
where both inequalities are meant element wise. This makes it possible to couple the processing of information, or model a demand [5, p.273 ] by forcing certain buffers to only be depletable together. Especially the last inequality in (2) deviates from the standard models used in [2] and [5] , and is responsible for many results that are presented here.
(F3) as already done in [2] , we capture the short term wireless characteristics (e.g. channel fading), by introducing a diagonal weight matrix M ∈ [0, 1] m×m which encodes the success probability of an activated communication link. Hence a controller might activate some link in time slot t, which in the end will not influence the system due to the communication being unsuccessful. More specifically, we define that the controller has knowledge of all communication links (now encoded as columns of the matrix B) and their success probabilities (encoded in M ). For the real system evolution however, we evaluate M by performing Bernoulli trials (coin tosses) on its individual entries. Specifically, B[ξ] = 1 w.p. ξ and 0 otherwise for any ξ ∈ [0, 1]. Using this operator on matrices means using it separately on its individual entries. We then obtain B t from (1) through multiplication as
. As a result, some columns of B t are set to 0, whereas others are as in B, independent of the decisions made by the controller.
(F4) we capture long term wireless characteristics (e.g. entities leaving the entire system), by having a whole set of probability matrices {M i } , i = 1 . . . p and choosing one of these through an underlying discrete time Markov chain (DTMC) σ t = M({1 . . . p}, P, σ 0 ) on its index set {1 . . . p} with left side transition matrix P and initial state σ 0 . In each time slot this DTMC will dictate, which M i to use for the description in (F3). We can therefore write
This setup is tightly related to Discrete-Time Markov Jump Linear Systems [10] .
III. PREDICTIVE NETWORK CONTROL (PNC)
We now introduce our new control policy, called Predictive Network Control (PNC). Like for any policy, the purpose of PNC is to let the system process as much information per time as possible, i.e. to escort it out of the system.
As mentioned, PNC is inspired by the paradigms of Model Predictive Control (MPC) [9] . Therefore we first define a cost function J(·), which assigns a cost to a whole trajectory of
We call the length of the trajectory the prediction horizon H. Going on, we calculate the minimizing trajectory of input-vectors u * t and intuitively apply its first vector u * t to our system to advance to the next time slot t+1. However once there, we do not apply the second vector of the optimal trajectory, which would be u * t+1 , since it is outdated. We instead repeat the whole process (minimizing, applying the first input-vector of the optimal trajectory) and thus obtain an implicit feedback control law.
In what follows, we will assume that the current time slot is t = 0. We choose the cost J(·) to be of quadratic form
with Q and R being symmetric, positive definite matrices. Naturally, we do not have a choice but to work with the expectation E [·] of future queue-vectors due to the stochastic system evolution. For this cost function, we can find the optimal, minimizing controlũ * 0 by transforming the problem into a standard quadratic program. The rest of this section shows how this can be accomplished (despite of the stochastics in the system evolution).
To handle the DTMC, it helps to define the expanded versions of σ t , P , and B as
where e σt is the flag-vector, corresponding to σ t (which is 1 at the (σ t )-th element and 0 everywhere else). With this we can express the expected future system-matrix given an initial Markov-state as
It follows that the expected queue-vector becomes
Substituting this into the cost function yields three cost terms, which are constant, linear and quadratic with respect to our control:
The first term is independent of u t and therefore without concern to us. The linear term can be expressed with (5) as
For the quadratic cost term, we need an expression for the expected square of the system-matrices. It is easy to verify that for k ≥ l
It follows that
Furthermore, we need to handle the following 3 constraints (i) the binarity ofũ 0
(ii) the constituency ofũ 0
(iii) the constraint of q t ∈ N n . Here, the discreteness is provided by the system model (1) . However, there are several ways to translate the positiveness into the optimization. Simply forcing q t ≥ 0 for t = 1 . . . H, resulting in H so called hard constraints, is most conservative and neglects any information on the arrival rate (setting it to the worst case, which is 0). Indeed, it would suffice to only force positiveness for the first evolution, q 1 ≥ 0, since this alone would already guarantee overall positiveness due to the repeated application of the optimization. The rest of the constraints could then be reformulated as soft constraints E [q t ] ≥ 0 for t = 2 . . . H. We suggest an adjustable approach, depending on the variance of the arrival. The more evenly the arrival, the more soft constraints should be used. This should improve performance due to a better prediction of the future states of the network. Using only one hard constraint for the first two steps yields the following constraint ⎛
Multiple hard constraints up to time slot τ can be implemented by replacing any expected system-matrices matrices with B on the lhs and removing anyā term on the rhs of the constraint up until row τ . Note that the last matrix in each row is denoted with (·) − . This operator transforms the matrix by setting every positive entry of it to 0. Let A be any real valued matrix and a ij its entries, then a − ij := min{a ij , 0}. This is necessary to forbid the system to route a single packet of information through multiple queues in a single time slot.
Finally, we can define the PNC as the policy that in each time slot solves the binary quadratic program
and initializes the first optimal control u * t from its solution. We implicitly assume, that the Markov-state σ t is known together with all other used parameters.
IV. SIMULATIONS
In what follows, we showcase the behavior of two exemplary networks, when controlled by the PNC policy. We compare it directly with the MW policy, which as mentioned is often used as a benchmark. Note however, that especially feature (F2) makes MW deviate from its usual throughput optimal behavior. Also, since the arrival has stochastic character, each simulation yields slightly different results. The here presented graphs are therefore only representatives which, to the best of our knowledge, do showcase the usual behavior of the quantity in question.
Note, that PNC, as defined in section III, uses a binary quadratic optimization over a control variable of potentially high dimension (depending on horizon H). Whereas MW uses binary linear optimization. Thus any gain in performance has to be set into relation to the additional computational cost. Having this in mind, we developed a modified version of PNC, called linear PNC (L-PNC), which does neglect the quadratic term in the optimization (setting J q (σ t ) = 0 in (13)). To separate both versions, we will from now on call the standard PNC (as introduced in section III) quadratic PNC (Q-PNC). Indeed, all simulations show little to no change in performance when using L-PNC instead of Q-PNC, though this is still subject to research. Finally, since MW does not Fig. 1 . Sketch with Arrivals (red) and Links (blue) of generic Example consider any direct cost contributed to the control-vector, we choose Q = I n and R = 0 to be able to compare the policies.
A. Generic Example
We first consider an example, specifically constructed to showcase the mechanism through which PNC dominates MW. This example does not need any probability weights, as introduced in (F3) and (F4), but only makes use of (F1) and (F2). Specifically we look at two queues, q (1) t and q (2) t , who are subject to arrival ratesā (1) and 0, respectively. As shown in Figure 1 , the controller is in every time slot presented with the same three mutually exclusive options (links), decoded as columns in the constant system-matrix
The first column directly decreases q (1) t while not changing q (2) t . This can be interpreted as the data of q (1) t being processed and afterwards leaving the system. The second column also decreases q (1) t for the price of increasing q (2) t which models a transmission from q (1) t to q (2) t . The third column allows the controller to heavily decrease q (1) t ; however according to (F2) it can only take this action if q (2) t is nonempty. An interpretation could be, that the parallel processing of the information is extremely beneficial (e.g. due to a lack of storage).
For this specific case, we designed link 1 in such a way that MW will almost always prefer it compared to link 2. We say that link 1 dominates link 2 under the MW policy. As a consequence, MW will never be able to use link 3 (since there will not be any information in q (2) t ). Hence the maximal arrival rate that MW can handle isā (1) 
A superior strategy would be to switch periodically between link 2 and 3, enabling the system to be stable under a maximal arrival rate ofā (1) 
. PNC, with a horizon of at least H = 2 indeed follows this strategy when possible (the stochastical character of a t may prevent it from time to time). Through this behavior, PNC does stabilize the Network for a wider set of arrival rates. Figure 2 compares the queue states over the first 100 time slots for the mentioned policies. In this case, we choseā (1) = 2.4 where we simulated a t as a Bernoulli trial (coin toss) with probability of 0.8 and The whole stability region for MW is shown in Figure 3 as the red area. PNC, implemented with full hard constraints, does expand onto this with the blue area (but also still stabilizes the red one). For this specific example, we do not increase the stability region if we chose H > 2. However, there do exist such networks where the stability region increases with increasing horizon. E.g. changing the −5 −1 column in the B t matrix to −5 −2 would be such a network.
B. Natural Example
The second example, that is showcased in the following, is obtained by modeling a rather real world scenario. We consider two users, interacting through a mobile game. Additionally a game master is also needed to provide neutral information to both parties as shown in Figure 4 . The game consists of many turns, each one progressing according to the following scheme: The game master sends information to both users; the game waits until both users interact with this information; their inputs are communicated between each other and evaluated; the turn ends. This network can be modeled with the help of three queues: q (1) holds the information, the game master sends in the beginning of each turn; q (2) holds the information that was successfully send to both users but is not yet processed due to missing interactions by the users; q (3) symbolizes the inputs of the users and is increased, only when both users did interact with the information from q (2) . Hence, information can only exit the system, when both q (2) and q (3) are non empty, i.e. only when the game master did successfully send information and both users interacted with it. We further define two communication channels: one between the users and one from game master to both users. We assume that both channels are mutually exclusive, so that in each time step, a policy has to decide for one of them to be inactive. Figure 5 shows the model of the network with arrivals (red) and communication links (blue). Note that q (2) acts as a buffer, which, when filled, allows for q (3) to be decreased. The superiority of PNC over MW is based on the utilization of that buffer. Through prediction of the Markov chain, PNC usually keeps this buffer at a higher level. MW on the other hand tends to use this buffer to decrease q (3) every time it gets the chance to do so, which is not the optimal strategy.
In this simulation example, we model the wireless characteristics according to (F3) and (F4) by introducing a good network state, in which both communication channels are guaranteed to work, and a bad network state, in which only Figure 6 shows q (1) over time, which is an indicator for the speed of the game. It therefore can be interpreted as a performance measure. We can see, that Q-PNC outperforms MW already for H = 2. For H = 1, both policies exhibit the same behavior (which as mentioned is an indication that the quadratic part of the optimization does not influence the result significantly). It should be noted, that both policies cannot stabilize the system for the specified arrival rate and that we used soft constraint for all but the first evolution of the system in the PNC algorithm.
For a stabilizable arrival rates, Figure 7 shows the performance gains that Q-PNC with H = 3 yields compared to MW. The average queue states are roughly about 10% smaller for Q-PNC. We omit q (2) which is usually higher for PNC, since it is meant to act like a storage and thus does not give any additional indication on the performance. For these graphs, we switch between periods of high and low arrivals. Specifically we usedā (1) = 0.375±0.3 andā (3) = 0.38±0.38 for intervals Δt (1) = 100 and Δt (3) = 250 respectively; the arrivals were initialized as Bernoulli trials.
V. CONCLUSION
Our new control policy seems to outperform the standard MW policy when the network is based on our more general system model. Especially the gain in stability region is a huge and surprising advantage. Another conclusion, that might be overlooked when reading this paper, is the following negative indication: for rather simple networks (e.g. broadcasting scenarios), our policy does not lead to any significant gains. After the initial results presented here, our immediate research 

{'paper_id': '52130537', 'title': 'Predictive Network Control and Throughput Sub-Optimality of Max Weight', 's2_url': 'https://api.semanticscholar.org/CorpusID:52130537', 'source': 'S2ORC'}