We consider the problem of serving a set of sensors/end-users at multi-level quality of service. Consider for example the problem, which arises in augmented reality applications, of single-hop radio broadcasting a common content from a provider. Each end-user requires a minimal quality level of the common content. The provider must satisfy all end-users at their required minimal quality level with a point-to-point encrypted transmission. Since the number of different quality level versions of the common content cannot be as large as the number of end-users, the provider has to partition the end-users into groups. The provider adopts for each group a quality level which is the maximum among the levels required by the end-users of that group. In doing so, the provider incurs into an encryption and transmission cost which is proportional to the product between the end-user group size and the adopted quality level. Such a problem consists in finding a partition of the end-users that satisfies their requests and minimizes the overall provider cost. These quality of service problems are optimally solved in polynomial time by dynamic programming techniques for an arbitrary number of end-users. A faster greedy heuristic is also proposed which quickly finds a solution very close to the optimum one.

Algorithms for Services with Multiple Levels of Quality

Mostarda, Leonardo
2016

Abstract

We consider the problem of serving a set of sensors/end-users at multi-level quality of service. Consider for example the problem, which arises in augmented reality applications, of single-hop radio broadcasting a common content from a provider. Each end-user requires a minimal quality level of the common content. The provider must satisfy all end-users at their required minimal quality level with a point-to-point encrypted transmission. Since the number of different quality level versions of the common content cannot be as large as the number of end-users, the provider has to partition the end-users into groups. The provider adopts for each group a quality level which is the maximum among the levels required by the end-users of that group. In doing so, the provider incurs into an encryption and transmission cost which is proportional to the product between the end-user group size and the adopted quality level. Such a problem consists in finding a partition of the end-users that satisfies their requests and minimizes the overall provider cost. These quality of service problems are optimally solved in polynomial time by dynamic programming techniques for an arbitrary number of end-users. A faster greedy heuristic is also proposed which quickly finds a solution very close to the optimum one.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11581/405160
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact