Combinatorial Optimization Problems in Multimedia Delivery

Combinatorial Optimization Problems in Multimedia Delivery

Tibor Szkaliczki (Institute for Computer Science and Control, Hungarian Academy of Sciences, Hungary)
DOI: 10.4018/978-1-5225-2990-3.ch004
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The amount of multimedia data (video, audio, images, animation, etc.) delivered through the Internet is continuously increasing. There is a wide range of application possibilities of optimization methods in the multimedia systems such as adapting multimedia objects, replication of multimedia elements, resource assignment, etc. This chapter introduces selected combinatorial optimization problems arising during the operation of multimedia delivery systems. The efficient solution of the problems considered can enhance significantly the performance of the servers and improve the quality of the provided services. This chapter provides an overview of the algorithms that can be used in multimedia delivery. Both heuristics and adaptation of well-known combinatorial optimization algorithms can be applied to solve the problems concerned. The approaches are related to typical problems and solutions in discrete mathematics such as facility location problem, knapsack problem, monotonic optimization, linear programming, evolutionary algorithms, etc.
Chapter Preview
Top

Introduction

Multimedia combines different content formats such as text, images, audio, animation, video etc. in order to present the content in an attractive and expressive way. Multimedia services over computer networks are becoming widespread and the amount of multimedia data delivered through the Internet is continuously increasing. Multimedia based services such as multimedia sharing and streaming, video phoning and conferencing, internet TVs, surveillance, etc. are spreading fast. Video data exceeded two-thirds of global consumer Internet traffic and it will increase to 82% by 2020 according to a recent forecast (Cisco Visual Networking Index, 2016). Considering the mobile systems, more than half of all mobile data traffic is in the form of video.

Meanwhile, an intensive diversification can be experienced among the video recording and playing devices (Higgins et al., 2010). There is an increasing need for receiving the same content not only on PCs but on smart phones, tablets, digital TVs and VR glasses as well. Continuous improvement in the quality of the multimedia items can be experienced while new multimedia formats and types appear due to the development of the display devices and delivery infrastructure. Due to sharp increase in the number of video recording devices, the digital multimedia can be produced at many sources and can be injected at most different places into a fully distributed and multimodal environment. The large amount of multimedia data is produced and consumed in most different quality, with most different aims and requirements. Heterogeneity can be experienced also among the networks connecting the devices.

Despite the diversification in devices, network and contents, the users require to receive the same multimedia items on different devices anytime and anywhere (see Figure 1).

Figure 1.

Multimedia content delivery

The multimedia delivery through computer networks plays a key role in various application domains including entertainment, health, transportation, education, telecommunication, environment etc. For example, a company, operating public motorways equipped with plenty of sensors and cameras is actually producing more broadcast material than a number of TV channels together. Another example is a live event with large public interest. Typically, number of professional and amateurish multimedia data producers participates on it and a huge amount and diversity of multimedia data are generated. The information shared in social networks is preferably also in the form of multimedia. A growing number of industrial applications incorporate multimedia information processing such as machine vision, automated inspection, vehicle guidance, etc. In health-care a large number of videos are produced which is an inherent part of the treatment in certain operation techniques.

The multimedia delivery systems offer a wide range of application possibilities of optimization methods. For example, multimedia objects (e.g., pictures and videos) cannot be often delivered in their original form because of the resource limitations. In this case, the multimedia objects have to be adapted to a lower-quality version that can be delivered under the given resource constraints while providing the maximal utility to the user. Another example is the video replication. The startup delay can be significantly decreased if the videos are located near the requesting user. For this reason, several samples of the same video are distributed in the network. The optimization problem is where to place the video samples in order to minimize the startup delays.

The chapter introduces selected combinatorial optimization problems arising during the operation of multimedia delivery systems. Common requirement for all solution methods is that they should be performed fast in order to provide short startup delay and continuous streaming. The efficient solution of the problems can enhance significantly the performance of the delivery systems and improve the quality of the provided services.

Complete Chapter List

Search this Book:
Reset