Kyoto University (京都大学) / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19125号 / 情博第571号 / 新制||情||100 / 32076 / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 杉江 俊治, 教授 石井 信, 教授 加納 学, 准教授 東 俊一 / 学位規則第4条第1項該当

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19125号 / 情博第571号 / 新制||情||100(附属図書館) / 32076 / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 杉江 俊治, 教授 石井 信, 教授 加納 学, 准教授 東 俊一 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Wireless technology has become an increasingly popular way to gain network access. Wireless networks are expected to provide efficient and reliable service and support a broad range of emerging applications, such as multimedia streaming and video conferencing. However, limited wireless spectrum together with interference and fading pose signi cant challenges for network designers. The novel technique of network coding has a significant potential for improving the throughput and reliability of wireless networks by taking advantage of the broadcast nature of wireless medium. Reverse carpooling is one of the main techniques used to realize the benefits of network coding in wireless networks. With reverse carpooling, two flows are traveling in opposite directions, sharing a common path. The network coding is performed in the intermediate (relay) nodes, which saves up to 50% of transmissions. In this thesis, we focus on the scheduling at the relay nodes in wireless networks with reverse carpooling. When two packets traveling in opposite directions are available at the relay node, the relay node combines them and broadcasts the resulting packet. This event is referred to as a coding opportunity. When only one packet is available, the relay node needs to decide whether to wait for future coding opportunities, or to transmit them without coding. Though the choice of holding packets exploits the positive aspects of network coding, without a proper policy in place that controls how long the packets should wait, it will have an adverse impact on delays and thus the overall network performance. Accordingly, our goal is to find an optimal control strategy that delicately balances the tradeoff between the number of transmissions and delays incurred by the packets. We also address the fundamental question of what local information we should keep track of and use in making the decision of of whether to transmit uncoded packet or wait for the next coding opportunity. The available information consists of queue length and time stamps indicating the arrival time of packets in the queue. We could also store history of all previous states and actions. However, using all this information makes the control very complex and so we try to find if the overhead in collecting waiting times and historical information is worth it. A major contribution of this thesis is a stochastic control framework that uses state information based on what can be observed and prescribes an optimal action. For that, we formulate and solve a stochastic dynamic program with the objective of minimizing the long run average cost per unit time incurred due to transmissions and delays. Subsequently, we show that a stationary policy based on queue lengths is optimal, and the optimal policy is of threshold-type. Then, we describe a non-linear optimization procedure to obtain the optimal thresholds. Further, we substantiate our analytical ndings by performing numerical experiments under varied settings. We compare systems that use only queue length with those where more information is available, and we show that optimal control that uses only the queue length is as good as any optimal control that relies on knowing the entire history.

Cette thése traite du contrôle de la formation et du confinement variant dans le temps pour les systèmes multi-agents linéaires invariants avec hétérogénéité en tenant compte des délais d’entrée / sortie constants / variables dans le temps et des perturbations adaptées / incompatibles sous topologie de communication dirigée et fixe. De nouveaux formats de formes de formation variables dans le temps pour des systèmes homogènes et hétérogènes sont proposés. Les contrôleurs, conçus sur la base de techniques prédictives et adaptatives avec une technique d’observation, sont entièrement distribués et peuvent être appliqués à des systèmes à grande échelle. L’application sur les systèmes robotisés multi hétérogènes linéarisés est vérifiée. / This thesis deals with the time-varying formation and containment control for linear time-invariant multi-agent systems with heterogeneity considering constant / time-varying input / output delays and matched / mismatched disturbances under directed and fixed communication topology. New formats of time-varying formation shapes for homogeneous and heterogeneous systems are proposed. The controllers, which are designed based on predictive and adaptive techniques with observer technique, are fully distributed and can be applied to large-scale systems. The application on linearized heterogeneous multi mobile robot systems is verified.