氏学位名杨 斌名博士（システム情報科学）

学 位 記 番 号

第２９号

学位授与年月日

平成２７年９月１７日

学位論文題目

Performance Studies for Mobile Ad Hoc Networks with Erasure Codingand f-cast Relay

論文審査委員

主査 姜 暁鴻副査 高橋 修副査 藤野 雄一
副査 髙橋 信行
副査 佐藤 仁樹論

文 要 旨

The mobile ad hoc networks (MANETs) are a class of infrastructure-lessself-organizing networks consisting of mobile devices communicating with each otherover peer-to-peer wireless links. Due to their distinctive feature of robustness,
self-organization, quick deployment and reconfiguration, MANETs hold great promisesformany

importantapplication

scenarios,

likedisasterrelief,battlefield

communications, and wide area sensing, and are thus increasingly becoming anindispensable component for the next generation (5G) networks. To efficiently support
these critical applications with stringent performance requirements, it is of great
importance to thoroughly understand the fundamental performance of such networks,
like the delivery delay and throughput capacity.
This work focuses on the performance studies of an important class of MANETs
with erasure coding and packet redundancy (f-cast), i.e., each coded packet at source
node is transmitted to at most f distinct relay nodes. The erasure coding and packet redundancy
are two promising techniques that have been extensively studied in the literature for improving thepacket delivery performance in MANETs. On one hand, previous studies showed that erasure coding
technique can considerably reduce the delay variance in MANETs, while it may lead to a relatively
large packet delivery delay, since the early arrived coded packets in destination node have to wait along time for the arrivals of other coded packets from distinct relay nodes. On the other hand, packet

redundancy technique can efficiently reduce the packet delivery delay due to the fact that multiple
relays will carry redundant copies of a packet, increasing the chance of the packet being received byits destination; however, it usually incurs high variance of packet delivery delay. Thus, we consider acombination of erasure coding and packet redundancy in MANETs to have a flexible trade-off
between packet delivery delay and delay variance.
We combine these two techniques together and study the packet delivery delay and throughput
capacity in MANETs, under a general two-hop relay routing algorithm with unicast traffic pattern,i.e., a source node has only a destination node, which covers available routing algorithms with pureerasure coding or pure packet redundancy as special cases. To analyze the packet delivery delay, wepropose a Markov chain model to depict the packet delivery process under this routing algorithm,
with which we derive the analytical expressions for the mean value and variance of packet delivery
delay. To analyze the throughput capacity, we propose two Markov chain models to depict the fastestpacket distributing process and fastest packet receiving process at source and destination nodes,
respectively, with which we derive the analytical expression for the throughput capacity. Extensive
simulation and theoretical results are provided to validate the accuracy of our theoretical
performance analysis as well as our findings.
Then, we study packet delivery delay of MANETs adopting a two-hop relay routing algorithmwith packet redundancy, and multicast traffic pattern, where a source node has multiple destination
nodes. To this end, we propose a Markov chain model to capture the packet delivery process under
the routing algorithm, with which we derive the analytical expressions for the mean value andvariance of packet delivery delay. Extensive simulations demonstrate the efficiency of our theoreticaldelay results.

審査結果の要旨
This thesis studied the fundamental packet delivery performance of an important class ofmobile ad hoc networks (MANETs) with erasure coding and packet redundancy in terms of theirdelivery delay and throughput capacity. For MANETs with a generalized two-hop relay routing
algorithm combining the erasure coding and f-cast packet redundancy techniques, the thesis first
proposed a powerful Markov chain-based theoretical framework to analytically study their unicast
delivery delay/throughput capacity and to explore the inherent tradeoff between these performance
metrics. The thesis further extended packet delivery performance study to MANETs with multicast
traffic pattern and f-cast relay, and employed the Markov chain-based theoretical analysis to derive
the analytical expressions for multicast delivery delay there. All theoretical results were carefully
validated with extensive simulation results. It is expected that the results developed in this thesis canprovide instruction guidelines for the design and optimization of future MANETs and can be helpful
for packet delivery performance study in other MANET scenarios as well.

・論文の構成Chapter 1 Introduction
Chapter 2 Related Work
Chapter 3 Preliminaries
Chapter 4 Unicast Delivery Delay Study for MANETs with Erasure Coding and f -cast Relay
Chapter 5 Throughput Capacity Study for MANETs with Erasure Coding and f-cast Relay
Chapter 6 Multicast Delivery Delay Study for MANETs with f-cast Relay
Chapter 7 Conclusion
・研究目的の妥当性，従来の手法との比較においての有意性，および理論・実験手法の新規性
This thesis studied the fundamental performance of an important class of MANETs witherasure coding and f-cast packet redundancy in terms of their delivery delay and throughput capacity,
both of which are critical performance metrics and serve as the instruction guideline for the designand optimization of future MANETs.
Available studies on unicast delivery delay/throughput capacity performances in MANETs
mainly adopted erasure coding and packet redundancy techniques separately, so they might not beable to take the full advantages of these two techniques to provide a more flexible tradeoff between
these performances. Different from these works, this thesis combines these two techniques together
and establishes a complete theoretical framework based on the Markov chain theory to study theunicast delivery delay/throughput capacity in such a MANET and to demonstrate the flexible
performance tradeoff there. It is expected such a study will significantly enhance the ability of future
MANETs to support various applications with different performance requirements.
Available works on multicast delivery delay analysis in MANETs mainly explored theasymptotic bounds on the multicast delivery delay as network size scales, which tell us little about
the real multicast delivery delay performance. Different from these works, this thesis conducts study
on the exact multicast delivery delay of MANETs based on the Markov chain theory to explore thereal achievable multicast delivery delay in MANETs.
・得られた知見のシステム情報科学の分野における意義
The results of this thesis provide the following insights.
1. The promising method of combining erasure coding and packet redundancy will provide aflexible and strong performance guarantee for various unicast-intensive applications in futureMANETs.
2. The exact multicast delivery delay study in this thesis will be helpful for supporting multicast
applications in future MANETs with one-to-many communication pattern, like the informationexchanges among a group of soldiers in battlefield communication, emergency communications
among the rescuers in disaster relief, real-time monitoring, etc.
3. The novel theoretical frameworks developed in this thesis could provide precious insights forthe study of delivery delay/throughput capacity performances in other MAENT scenarios aswell.