# Research

## Contents

- 1 Research Projects
- 2 Game Theoretic Approaches for Distributed Resource Management Strategies in Multi-user Systems and Multi-user Wireless/Wired/Peer-to-Peer (P2P) Networks
- 3 Efficient and Robust Multimedia Streaming Strategies using Network Coding
- 4 P2P Multimedia Data Transmission and Resource Reciprocation Strategy
- 5 Fairness Paradigms for Resource Management using Game Theory
- 6 Cross-layer Optimization for Wireless Networks

## Research Projects

### Active Projects

- Research on Virtually Always-on Connectification and Adaptively Self-evolving Functional Flat Network in Massive Connectivity, National Research Foundation of Korea (NRF), Ministry of Science and ICT, 2017-2020 (PI)
- Development of Flipped Learning Model and Support System based on Big Data and Smart Device: In a Middle School Math Curricula Context, National Research Foundation of Korea (NRF), Ministry of Education, 2015-2018.

### Completed Projects

- [Completed] Network Coding based Self-organizing Smart Networks for Intelligent Internet of Things, National Research Foundation of Korea (NRF), Ministry of Science, ICT and Future Planning, 2014-2017 (PI)
- [Completed] u-Office Service Research Based on High-speed Wireless Networks, Ministry of Knowledge Economy (ITRC - Information Technology Research Center), 2012-2015 (co-PI).
- [Completed] Core-Technology Development of Next-generation Digital TV Broadcasting System (Realistic/Mobile/Interactive), Ministry of Knowledge Economy (ITRC - Information Technology Research Center), 2012-2015.
- [Completed] Low-complexity network coding and decoding study for Internet of Things based on message passing algorithm, Korea Foundation for the Advancement of Science and Creativity (KOFAC), Ministry of Education, 2015 (PI)
- [Completed] Robust Real-time Multimedia Transmission Strategies over Various Network Environment, National Research Foundation of Korea (NRF), Ministry of Education, Science, and Technology, 2010-2015 (PI).
- [Completed] Study of Network Topologies for Maximum Capacity Gain based on Network Coding based Data Transmission, Center for Women in Science, Engineering and Technology (WISET), Ministry of Science, ICT and Future Planning, 2014 (Advisor)
- [Completed] Study and Implementation of Multimedia Streaming Systems based on Network Coding, Korea Foundation for the Advancement of Science and Creativity (KOFAC), Ministry of Education, 2014 (PI)
- [Completed] Context based Biometric Data Collection using Wearable Devices and Methodology for Efficient Data Collection, LG Electronics, 2014 (PI)
- [Completed] An Algorithm for Efficient Cooperation among Multi-Cleanup Robots based on Machine Learning and Cooperative Game Theory, Korea Foundation for the Advancement of Science and Creativity (KOFAC), Ministry of Education, 2013-2014 (PI)
- [Completed] Bloom Filter based Realtime Algorithms for Data Collected by Wearable Devices, LG Electronics, 2013 (PI)
- [Completed] Development of Seasonal Forecast System of Sea Ice Concentration, Korea Meteorological Administration, 2012-2013
- [Completed] On Duality between Approximate Decoding for Network Coding and Compressive Sensing, National Research Foundation of Korea (NRF) and Swiss State Secretariat for Education and Research (SER) (Korean-Swiss cooperative research project in collaboration with LTS4, EPFL), 2010-2011 (PI).
- [Completed] Game Theoretic Distributed Resource Management Strategies for Multimedia Stream Mining Systems, Ewha Womans University, 2010-2011(PI).

## Game Theoretic Approaches for Distributed Resource Management Strategies in Multi-user Systems and Multi-user Wireless/Wired/Peer-to-Peer (P2P) Networks

**Multi-user Networks: Cognitive Radio Networks for Multimedia**

Designing efficient and fair solutions for dividing the network resources in a distributed manner among self-interested multimedia users is recently becoming an important research topic because heterogeneous and high bandwidth multimedia applications (users), having different quality of service requirements, are sharing the same network. Suitable resource negotiation solutions need to explicitly consider the amount of information exchanged among the users and the computational complexity incurred by the users. In this research, we propose decentralized solutions for resource negotiation, where multiple autonomous users self-organize into a coalition which shares the same network resources and negotiate the division of these resources by exchanging information about their requirements. We then discuss various resource sharing strategies that the users can deploy based on their exchanged information.

Several of these strategies are designed to explicitly consider the utility (i.e., video quality) impact of multimedia applications. In order to quantify the utility benefit derived by exchanging different information, we define a new metric, which we refer to as the value of information. We quantify through simulations the improvements that can be achieved when various information is exchanged between users, and discuss the required complexity at the user side involved in implementing the various resource negotiation strategies.

**Multi-user Systems: Distributed Systems for Stream Mining**

We consider the problem of optimizing stream mining applications, constructed as tree topologies of classifiers, deployed on a set of resource constrained and distributed processing resources. The optimization involves selecting appropriate false-alarm detection tradeoffs (operating points) for each classifier to minimize an end-to-end misclassification penalty, while satisfying resource constraints.

We design distributed solutions, by defining tree configuration games, where individual classifiers configure themselves to maximize an appropriate local utility. We define the local utility functions and determine the information that needs to be exchanged across classifiers, in order to design the distributed solutions. We analytically show that there is a unique pure strategy Nash equilibrium in operating points, which guarantees convergence of the proposed approach. We develop both myopic strategy, where the utility is purely local to the current classifier, and foresighted strategy, where the utility includes impact of classifier actions on successive classifiers. We analytically show that actions determined based on foresighted strategies improve the end-to-end performance of the classifier tree, by deriving an associated probability bound. We also investigate the impact of resource constraints on the classifier action selections for each strategy, and the corresponding application performance. We propose a learning-based approach, which enables each classifier to effectively adapt to the dynamic changes of resource constraints.

We evaluate the performance of our solutions on an application for sports scene classification, and compare against centralized solutions. We show that foresighted strategies result in better performance than myopic strategies in both resource unconstrained and resource constrained scenarios, and also asymptotically approach the centralized optimal solution. We also show that the proposed distributed solutions outperform the centralized Sequential Quadratic Programming based solution on average in resource unconstrained scenarios.

## Efficient and Robust Multimedia Streaming Strategies using Network Coding

In this research, we consider the problem of distributed delivery of correlated data from sensors in ad hoc network topologies. We propose to use network coding in order to exploit the path diversity in the network for efficient delivery of the sensor information. Specifically, we deploy random linear network coding (RLNC), where encoding process consists of 1) randomly selecting coefficients from finite field (i.e., Galois field, GF) for received data and 2) combining the received data with the selected coefficient. The encoded data are forwarded to each node’s neighboring nodes. We further show that the correlation between the data sources can be exploited at receivers for efficient approximate decoding when the number of received data packets is not sufficient for perfect decoding. We analyze how the decoding performance is influenced by the choice of the network coding parameters and in particular by the size of finite fields. We determine the optimal field size that maximizes the expected decoding performance, which actually represents a trade-off between information loss incurred by quantizing the source data and the error probability in the reconstructed data. Moreover, we show that the decoding performance improves when the accuracy of the correlation estimation increases. We have illustrated our network coding based algorithms with approximate decoding in sensor networks and video coding applications. In both cases, the experimental results confirm the validity of our analysis and demonstrate the benefits of our solution for distributed delivery of correlated information in ad hoc networks.

## P2P Multimedia Data Transmission and Resource Reciprocation Strategy

We consider the problem of resource reciprocation in P2P networks, where the resources are the peer's available content and its available upload bandwidth. Hence, a peer can increase its utility by associating itself with other peers (i.e., form a coalition), which are interested in exchanging resources with it. In this case, each peer needs to determine how to reciprocate its limited resources by determining the amount of its resource allocations to dedicate to its associated peers, such that each peer can maximize its own utility.

To capture the repeated and dynamic interactions among the self-interested and heterogeneous peers, we model resource reciprocation among peers as a stochastic game and show how the peers can determine optimal strategies for resource reciprocation using a Markov Decision Process (MDP) framework.

The optimal strategies determined based on MDP enable the peers to make foresighted decisions about resource reciprocation, such that they can explicitly consider both their immediate as well as future expected utilities.

For this approach, several issues should be considered:

- How to capture the probabilistic behaviors of associated peers, and
- What is the impact of peer’s bounded rationality on its performance.

1: Unlike conventional stochastic game modeling, where the probabilistic behaviors of associate peers are known and stationary, we propose a novel algorithm that identifies the state transition probabilities using representative resource reciprocation models of peers. These models capture different attitudes that the peers may have toward resource reciprocation, such as optimistic, pessimistic, and neutral attitudes.

We analytically investigate how the error between the true and estimated state transition probability impacts each peer's decisions for selecting its actions as well as the resulting utilities.

2: Unlike in conventional MDP formulations, where users assume that the states (of the resource reciprocation) are known (i.e. users can exactly recognize the amount of resources received from their associated users), we consider heterogeneous peers that have different and limited ability to characterize their resource reciprocation with other peers (i.e. they can distinguish their received resources using only a limited number of states). This is due to the large complexity requirements associated with their decision-making processes.

## Fairness Paradigms for Resource Management using Game Theory

If available resources are limited and users are competing for the resources, then the participating users need to agree on a particular resource division.

The resource negotiations among the participating users are modeled as bargaining problems in utility domain.

A solution to the bargaining problems enables the users to fairly and optimally determine their resource division, based on utilities. We consider several bargaining solutions such as the Nash bargaining solution (NBS), the Kalai-Smorodinsky bargaining solution (KSBS), the proportional bargaining solution (PBS), and the egalitarian bargaining solution (EBS) which is a special case of the PBS. Each of bargaining solution has its own axioms, which define the properties of resource allocation. Illustrative examples for the NBS and the KSBS are shown below.

In multi-user multimedia applications, we show that

- NBS: maximize the system utility (i.e., sum of users’ utilities),
- KSBS: incur the same utility penalty relative to each user’s maximum achievable utility, and
- PBS (EBS): achieve the proportional (same) utility.

These interpretations are deployed to fairly and efficiently solve resource division problems in various networks scenarios such as wireless, wired, and P2P networks, while explicitly considering their own characteristics. We extend and generalize the existing bargaining solutions by successfully deploying bargaining powers of each user, which are determined based on each users multimedia characteristics, channel conditions, delay constraints, etc.

## Cross-layer Optimization for Wireless Networks

Recent research in wireless multimedia streaming has focused on optimizing the multimedia quality in isolation, at each station. However, the cross-layer transmission strategy deployed at one station impacts and is impacted by the other stations, as the wireless network resource is shared among all competing users. Hence, efficient and fair resource management for autonomous wireless multimedia users becomes very important. The resource allocation is coordinated in polling-based wireless schemes by a network moderator (e.g., access point), which needs to fairly determine the amount of transmission time (resource) to be allocated among multiple autonomous wireless stations. Traditional fairness approaches such as proportional fairness, air-time fairness, and generalized processor scheduling solutions cannot guarantee that desired relationships among the resulting qualities of autonomous multimedia users are satisfied. Hence, we also consider quality-based fairness schemes based on axiomatic bargaining theory, which can ensure that the autonomous multimedia stations incur the same drop in multimedia quality as compared to a maximum achievable quality for each wireless station.

Implementing this quality based fairness solution in time-varying channel condition requires high computational complexity and communication overheads since the wireless stations need to transmit their channel state information and cross-layer strategies during every service interval. Hence, we develop suboptimal solutions that significantly reduce the computational complexity and communication overheads. Our simulations show that the proposed game-theoretic resource management can indeed guarantee desired utility-fair allocations when wireless stations deploy different cross-layer strategies.