| 2. |
- Zou, Zhenhua, et al.
(författare)
-
Online shortest path routing: The value of information
- 2014
-
Konferensbidrag (refereegranskat)abstract
- This paper studies online shortest path routing over dynamic multi-hop networks. Link costs or delays are time-varying and modelled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative delay difference) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decision. For each scenario, we derive the tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. These bounds help us to understand the performance improvements we can expect when (i) taking routing decisions at each hop rather than at the source only, and (ii) observing per-link costs rather than aggregate path costs. In particular, we show that (i) is of no use while (ii) can have a spectacular impact. Efficient algorithms are proposed and evaluated against the state-of-the a
|
|
| 3. |
- Zou, Zhenhua, 1984-
(författare)
-
Real-time communication in wireless lossy networks
- 2014
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The last decades’ tremendous advances in wireless communications havebeen driven mainly by personal communications. Radio resource allocationmechanisms for optimizing key metrics, such as average throughput and delay,are by now rather well-developed. However, with the increased interest inwireless machine-to-machine communication, new challenges emerge, such asmulti-hop connectivity, lossy and bursty links, battery-powered nodes, andchanging/unknown link parameters, among others. With these challenges inmind, this thesis studies real-time communication in wireless lossy networks,and how the resulting networking primitive can be used to design networkedcontrol systems with optimal closed-loop performance.First, we study optimal forwarding of deadline-constrained traffic overmulti-hop networks with losses on links described by finite-state Markovchains. We consider two problems: maximizing the probability that packetsare delivered within specified deadlines; and minimizing the expected energycost with a guaranteed probability of on-time delivery. Both problems fallinto the category of Markov Decision Processes and can be studied in a generaldynamic programming framework. Particular instances with Bernoulliand Gilbert-Elliot loss models, which admit insight and efficient computations,are discussed. Moreover, a number of extensions and variations ofthe deadline-constrained forwarding problem are investigated. These extensionsinclude systems with unknown channel states and unknown link lossmodels, scenarios with multiple concurrent flows, and solutions adapted toopportunistic routing and the recent WirelessHART standard.Second, we show how the solution for the deadline-constrained forwardingproblem can be used in the optimal co-design of networked control systems.Specifically, we consider the joint design of packet forwarding policies andcontrollers for wireless control loops where sensor data are sent to the controllerover an unreliable and energy-constrained multi-hop wireless network.For fixed sampling rate of the sensor, the co-design problem separates into twowell-defined and independent subproblems: transmission scheduling for maximizingthe deadline-constrained reliability and optimal control under packetloss. We develop optimal and implementable solutions for these subproblemsand show that the optimally co-designed system can be efficiently found.Finally, we study online shortest-path routing problems in which link delaysare time-varying and modeled by random processes with initially unknownparameters. The optimal path can only be estimated by routing packetsthrough the network and observing the realized delays. The aim is to finda routing policy that minimizes the regret (the cumulative delay difference)between the path chosen by the policy and the unknown optimal path. Weformulate the problem as a combinatorial bandit optimization problem andconsider several scenarios. For each scenario, we derive the tight asymptoticlower bound on the regret that has to be satisfied by any online routing policy.These bounds help us to understand the performance improvements wecan expect when (i) taking routing decisions at each hop rather than at thesource only, and (ii) observing per-link costs rather than aggregate path costs.Efficient algorithms are proposed and evaluated against the state-of-the-art.
|
|
