DOCTORAL THESIS

MULTIMEDIA DATA DISSEMINATION IN
OPPORTUNISTIC SYSTEMS

A Scalable Video Dissemination Scheme

Submitted to:

UNIVERSITÉ DE LYON, INSA, Ecole Doctorale InfoMaths N°512,
Lyon, France

UNIVERSITÄT PASSAU, Fakultät der Informatik & Mathematik,
Passau, Germany

in fulfillment of the requirements for

DOCTORAL DEGREE
in Computer Science

Defended on 01.12.2016, by:

MERZA KLAGHSTAN

EXAMINATION COMMITTEE

Prof. Jaime Delgado, Universitat Politècnica de Catalunya, Spain Reviewer

Assoc.-Prof. Ahmed Mostefaoui, Université de Franche-Comté, France Reviewer

Assoc.-Prof. Klaus Schöffmann, Universität Klagenfurt, Austria Examiner

Prof. Michael Granitzer, Universität Passau, Germany Examiner

Assoc.-Prof. Faiza Najjar, Ecole nationale des sciences de
l'Informatique, Tunisia Examiner

Prof. Harald Kosch, Universität Passau, Germany Doctoral Advisor

Prof. Lionel Brunie, INSA de Lyon, France Doctoral Advisor

Assoc.-Prof. Nadia Bennani, INSA de Lyon, France Co-Advisor

Dr. David Coquil, European Patent Office, EU Guest
Technology is meant to serve for the good of the humankind. Abusing technology to censor people, pursue them and revoke their freedom of expression is a double crime.

To the victims of technology abuses, I dedicate this work ...
<figure><img src="image_1.png" /></figure>
ABSTRACT

Opportunistic networks (OppNets) are human-centric mobile ad-hoc networks, in which neither the topology nor the participating nodes are known in advance. Routing is dynamically planned following the store-carry-and-forward paradigm, which takes advantage of people mobility. This widens the range of communication and supports indirect end-to-end data delivery. But due to individuals' mobility, OppNets are characterized by frequent communication disruptions and uncertain data delivery. Hence, these networks are mostly used for exchanging small messages like disaster alarms or traffic notifications. Other scenarios that require the exchange of larger data (e.g. video) are still challenging due to the characteristics of this kind of networks. However, there are still multimedia sharing scenarios where a user might need switching from infrastructural communications to an ad-hoc alternative. Examples are the cases of 1) absence of infrastructural networks in far rural areas, 2) high costs due to roaming or limited data volumes or 3) undesirable censorship by third parties while exchanging sensitive content. Consequently, we target in this thesis a video dissemination scheme in OppNets.

For the video delivery problem in the sparse opportunistic networks, we propose
a solution with the objective of reducing the video playout delay, so that enabling
the recipient to play the video content as soon as possible even if at a low quality.
Furthermore, the received video reaches later a higher quality level, ensuring a better
viewing experience.

The proposed solution encloses three contributions. The first one is given by gran-
ulating the videos at the source node into smaller parts, and associating them with
unequal redundancy degrees. This is technically based on using the Scalable Video
Coding (SVC), which encodes a video into several layers of unequal importance for
viewing the content at different quality levels. Layers are routed using the Spray-
and-Wait routing protocol, with different redundancy factors for the different layers
depending on their importance degree. In this context as well, a video viewing QoE
metric is proposed, which takes the values of the perceived video quality, delivery
delay and network overhead into consideration, and on a scalable basis.
Second, we take advantage of the small units of the Network Abstraction Layer
(NAL), which compose SVC layers. NAL units are packetized together under spe-
cific size constraints to optimize granularity. Packets sizes are tuned in an adaptive
way, with regard to the dynamic network conditions. Each node is enabled to record
a history of environmental information regarding the contacts and forwarding oppor-
tunities, and use this history to predict future opportunities and optimize the sizes
accordingly.

Lastly, the receiver (destination) node is pushed into action by reacting to missing
data parts in a composite “backward” loss concealment mechanism. So, the receiver
asks first for the missing data from other nodes in the network in the form of request-
response. Then, since the transmission is concerned with video content, video frame
loss error concealment techniques are also exploited at the receiver side. Conse-
quently, we propose to combine the two techniques in the loss concealment mech-
anism, which is enabled then to react to missing data parts.

To study the feasibility and the applicability of the proposed solutions, simulation-
driven experiments are performed, and statistical results are collected and analyzed.
Consequently, we have got promising results that show the applicability of video dis-
semination in opportunistic delay tolerant networks, and open the door for a range
of possible future works.

* * *
ZUSAMMENFASSUNG

Die opportunistische Netzwerke sind Mensch-zentrierte Mobile Ad-hoc Netzwerke, die weder die Topologie noch die teilnehmendem Knoten im Voraus kennen. Dank des Paradigmas von Store-Carry-and-Forward (speichern, mitnehmen, dann weiterleiten) kann das Routing dynamisch geplant werden. Das hat den Vorteil von einer größeren Kommunikationsreichweite, sowie von der Unterstützung einer indirekten Datenlieferung, wo ein vollständiger Weg von der Quelle zum Ziel nicht erforderlich ist. Allerdings, wegen der Mobilität der Knoten kann die Verbindung in OppNets häufig getrennt werden, und also ist eine erfolgreiche Datenlieferung unsicher. Deswegen sind OppNets hauptsächlich eingesetzt, um kleine Nachrichten auszutauschen, wie zum Beispiel Notfallübertragungen in Krisenfällen, wohingegen ist der Austausch von großen Daten (z.B. Videos) in OppNets ungewöhnlich. Trotzdem haben die OppNets noch Einsatzmöglichkeiten in Multimediaaustausch-Szenarien. Beispiele sind wenn: 1) kein Infrastruktur-gebundenes Netzwerk zur Verfügung steht, 2) extra Kosten oder begrenzte Datenvolumen in Frage kommen, oder 3) eine Zensur von Dritten unerwünscht ist. Insgesamt betrachtet zielt diese Arbeit auf eine Lösung zur Videodatenübertragung in OppNets ab.

In Bezug auf das Problem von Videodatenlieferung in opportunistischen Netzwerke schlagen wir eine Lösung vor mit dem Ziel, die Playout-Verzögerung zu reduzieren, womit der Zielknoten in der Lage wäre, das Video so schnell wie möglich anzuschauen auch wenn mit einer geringeren Qualität. Darüber hinaus, die lieferte Videoqualität könnte später noch aufsteigen, was eine bessere Anschauungsqualität versichern könnte.

Die vorgeschlagene Lösung hat drei Beiträge. Der Erste geht darum, die Videos beim Quellknoten mithilfe des Scalable Video Coding (SVC) in kleinere Teile zu spalten. SVC kodiert ein Video so, dass es aus verschiedenen Layers besteht, die ungleichmäßig wichtig sind. Die Layers werden dann unter Einsatz vom Spray-and-Wait Routing-Protokoll übertragen, mit einem Redundanzgrad, der davon abhängt, wie wichtig das jeweilige Layer ist. Noch dazu kommt eine Messung der Videoanschauungszufriedenheit, die nicht nur die gelieferte Videoqualität berücksichtigt, sondern auch die Verzögerung und die Netzwerkbelastung.

Zweitens, zum Einsatz kommen die kleinen Einheiten von Network Abstraction Layer (NAL), woraus die SVC layers bestehen. Die sogenannte NALUs werden berücksichtigt
gend Umwelt-gebundenen Informationen dynamisch zusammen eingepackt.
Letztens, der Zielknoten wird zum Einsatz gebracht, um auf den Verlust von Daten-
teilen zu reagieren. Dieser Knote fragt zuerst um die vermissten Daten von anderen
Knoten im Netzwerk. Dann, da es sich um einen Videoinhalt handelt, können auch
Video-gebundene Verlustverscleierungstechniken verwendet werden. Insgesamt be-
trachtet möchten wir die zwei Techniken zusammen kombinieren in einem rückwär-
tigen Verlustverscleierungsmechanismus.

Um die Anwendbarkeit der vorgeschlagenen Lösung testen zu können, werden Ex-
perimente durch Simulationen ausgeführt und Statistiken gesammelt. Schließlich
haben wir gute Ergebnisse gehabt, die die Übertragbarkeit der Videodaten in Opp-
Nets vorstellt, und die Tür für weitere Forschungen in diesem Bereich öffnet.

* * *
# RÉSUMÉ

Les réseaux opportunistes (oppnets) sont des réseaux mobiles qui se forment spon-
tanément et de manière dynamique grâce à un ensemble d'utilisateurs itinérants
dont le nombre et le déplacement ne sont pas prévisibles. En conséquence, la topolo-
gie et la densité de tels réseaux évoluent sans cesse. La diffusion de bout-en-bout
d'informations, dans ce contexte, est incertaine du fait de la forte instabilité des liens
réseaux point à point entre les utilisateurs. Les travaux qui en ont envisagé l'usage
visent pour la plupart des applications impliquant l'envoi de message de petite taille.
Cependant, la transmission de données volumineuses telles que les vidéos représente
une alternative très pertinente aux réseaux d'infrastructure, en cas d'absence de
réseau (zones rurales peu ou pas équipées), de coût important (cas des usagers en sit-
uation d'itinérance) ou pour éviter la censure d'un contenu (envoi de vidéos témoins
d'exactions par exemple).

La diffusion des informations de grande taille en général et de vidéos en particulier dans des réseaux oppnets constitue un challenge important. En effet, permettre, dans un contexte réseau très incertain et instable, au destinataire d'une vidéo de prendre connaissance au plus vite du contenu de celle-ci, avec la meilleure qualité de lecture possible et en encombrant le moins possible le réseau reste un problème encore très largement ouvert.

Dans cette thèse, nous proposons un nouveau mécanisme de diffusion de vidéos dans un réseau opportuniste de faible densité, visant à améliorer le temps d'acheminement de la vidéo tout en réduisant le délai de lecture à destination. La solution proposée se base sur le choix d'encoder la vidéo en utilisant l'encodage SVC, grâce auquel la vidéo se décline en un ensemble de couches interdépendantes (layers), chacune améliorant la précédente soit en terme de résolution, soit en terme de densité, soit en terme de perception visuelle.

Notre solution se décline en trois contributions. La première consiste à proposer une
adaptation du mécanisme de diffusion Spray-and-Wait, avec comme unités de diffu-
sion, les couches (layers) produites par SVC. Les couches sont ainsi diffusées avec un
niveau de redondance propre à chacune, adapté à leur degré d'importance dans la
diffusion de la vidéo.
Notre seconde contribution consiste à améliorer le mécanisme précédent en prenant en compte une granularité plus fine et adaptative en fonction de l'évolution de la topologie du réseau. Cette amélioration a la particularité de ne pas engendrer de coût de partitionnement, les couches vidéos dans l'encodage SVC étant naturellement déclinées en petites unités (NALU) à base desquelles l'unité de transfert sera calculée.

Enfin, la troisième contribution de cette thèse consiste à proposer un mécanisme hybride de complétion des couches vidéos arrivées incomplètes à destination. Cette méthode se caractérise par le fait d'être initiée par le destinataire. Elle combine un protocole de demande des parties manquantes aux usagers proches dans le réseau et des techniques de complétion de vidéo à base d'opérations sur les frames constituant la vidéo.

Pour valider la faisabilité de nos contributions, et afin d'analyser la variation des différentes caractéristiques, nous avons implémenté nos algorithmes de diffusion en utilisant un environnement de simulation des réseaux opportunistes (ONE). Les résultats obtenus sont prometteurs et ouvrent de nouvelles perspectives de recherche dans le domaine.

* * *
PUBLICATIONS

Publications that are directly related to the course of this thesis:

2016 Merza Klaghstan, David Coquil, Nadia Bennani, Harald Kosch and Lionel Brunie. "BALCON: BAckward Loss Concealment Mechanism for Scalable Videos in Opportunistic Networks." In 2016 IEEE 27th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pp. 1789-1795. Valencia, 2016. (SJR-Scimago H-Index: 40).

2014 Merza Klaghstan, Nadia Bennani, David Coquil, Harald Kosch and Lionel Brunie. "Contact-Based Adaptive Granularity for Scalable Video Transmission in Opportunistic Networks." In 2014 International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 773-778. Nicosia, 2014.

2013 Merza Klaghstan, David Coquil, Nadia Bennani, Harald Kosch and Lionel Brunie. "Enhancing Video Viewing-Experience in Opportunistic Networks Based on SVC, an Experimental Study." In 2013 IEEE 24th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pp. 3563-3567. London, 2013. (SJR-Scimago H-Index: 40).

Other publications:

2012 Merza Klaghstan, Ronny Haensch, David Coquil, and Olaf Hellwich. "Impact of hierarchical structures in image categorization systems." In 2012 IEEE 3rd International Conference on Image Processing Theory, Tools and Applications (IPTA), pp. 367-370.
<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>
# CONTENTS

<table><tr><td>List of Figures</td><td>5</td></tr><tr><td>List of Tables</td><td>6</td></tr><tr><td>Listings</td><td>7</td></tr></table>

<table><tr><td>i RESEARCH POSITIONING</td><td>11</td></tr></table>

<table><tr><td>1 INTRODUCTION</td><td>13</td></tr></table>

<table><tr><td>1.1 Motivation</td><td>13</td></tr></table>

<table><tr><td>1.1.1 The Emergence of Mobile Ad-hoc and Opportunistic Networks</td><td>13</td></tr></table>

<table><tr><td>1.1.2 Target Applications</td><td>15</td></tr></table>

<table><tr><td>1.2 Research Problems</td><td>17</td></tr></table>

<table><tr><td>1.3 Objectives & Hypothesis</td><td>18</td></tr></table>

<table><tr><td>1.3.1 Assumptions</td><td>19</td></tr></table>

<table><tr><td>1.4 Thesis Contributions</td><td>19</td></tr></table>

<table><tr><td>1.5 Thesis Organization</td><td>21</td></tr></table>

<table><tr><td>2 THEMATIC BACKGROUND</td><td>23</td></tr></table>

<table><tr><td>2.1 Opportunistic Networks</td><td>23</td></tr></table>

<table><tr><td>2.1.1 Multihop Networks: Terminology & Taxonomy</td><td>23</td></tr></table>

<table><tr><td>2.1.2 Data Delivery</td><td>28</td></tr></table>

<table><tr><td>2.2 Simulation Modeling</td><td>30</td></tr></table>

<table><tr><td>2.2.1 Overview</td><td>30</td></tr></table>

<table><tr><td>2.2.2 The ONE Simulator</td><td>31</td></tr></table>

<table><tr><td>2.2.3 Mobility Models</td><td>33</td></tr></table>

<table><tr><td>2.2.4 Discussion</td><td>34</td></tr></table>

<table><tr><td>2.3 Video Coding</td><td>34</td></tr></table>

<table><tr><td>2.3.1 Overview</td><td>35</td></tr></table>

<table><tr><td>2.3.2 Scalable Video Coding</td><td>37</td></tr></table>

<table><tr><td>2.3.3 Video Quality Measurement</td><td>42</td></tr></table>

<table><tr><td>2.3.4 Discussion</td><td>44</td></tr></table>

<table><tr><td>3 RELATED LITERATURE</td><td>45</td></tr></table>

<table><tr><td>3.1 Video Communication Schemes in Multihop Networks</td><td>45</td></tr></table>

<table><tr><td>3.1.1 Target Multihop Network</td><td>46</td></tr></table>

<table><tr><td>3.1.2 Solving Approach</td><td>47</td></tr></table>

<table><tr><td>3.1.3 Evaluation Metric</td><td>49</td></tr></table>

<table><tr><td>3.1.4 Summary</td><td>50</td></tr></table>

<table><tr><td>3.2 Granulation and Corresponding Routing</td><td>53</td></tr></table>
<table><tr><td>3.2.1</td><td>Granulation and Data Partitioning</td><td>53</td></tr><tr><td>3.2.2</td><td>Routing of The Data Parts</td><td>54</td></tr><tr><td>3.2.3</td><td>Conclusion</td><td>55</td></tr><tr><td>3.3</td><td>Adaptive Size Tuning of The Video Chunks</td><td>55</td></tr><tr><td>3.3.1</td><td>Message Adaptation</td><td>56</td></tr><tr><td>3.3.2</td><td>Routing Adaptation</td><td>56</td></tr><tr><td>3.3.3</td><td>Conclusion</td><td>57</td></tr><tr><td>3.4</td><td>Loss Recovery</td><td>58</td></tr><tr><td>3.4.1</td><td>Video Frame Loss Concealment</td><td>58</td></tr><tr><td>3.4.2</td><td>Network Packet Loss Recovery</td><td>59</td></tr><tr><td>3.4.3</td><td>Conclusion</td><td>60</td></tr><tr><td>ii</td><td>CONTRIBUTION</td><td>61</td></tr><tr><td>4</td><td>TOWARD VIDEO DELIVERY WITH A BETTER VIEWING EXPERIENCE USING SVC: AN EXPERIMENTAL STUDY</td><td>63</td></tr><tr><td>4.1</td><td>Overview</td><td>63</td></tr><tr><td>4.2</td><td>Objectives and Contributions</td><td>63</td></tr><tr><td>4.2.1</td><td>Recall: Granulation and Data Partitioning</td><td>63</td></tr><tr><td>4.2.2</td><td>Viewing Experience</td><td>64</td></tr><tr><td>4.2.3</td><td>Prioritized Routing</td><td>67</td></tr><tr><td>4.3</td><td>Experimental Setup</td><td>70</td></tr><tr><td>4.3.1</td><td>Scalable Video Coding</td><td>70</td></tr><tr><td>4.3.2</td><td>Simulation Environment</td><td>77</td></tr><tr><td>4.4</td><td>Map-Based Experiments</td><td>79</td></tr><tr><td>4.4.1</td><td>Delivery Ratio and Delay</td><td>79</td></tr><tr><td>4.4.2</td><td>Quality Distribution</td><td>82</td></tr><tr><td>4.4.3</td><td>Viewing Quality-of-Experience (QoE)</td><td>83</td></tr><tr><td>4.5</td><td>Open-Area Experiments</td><td>85</td></tr><tr><td>4.5.1</td><td>Delivery Ratio and Delay</td><td>85</td></tr><tr><td>4.5.2</td><td>Quality Distribution</td><td>85</td></tr><tr><td>4.5.3</td><td>Viewing QoE</td><td>86</td></tr><tr><td>4.6</td><td>Validation and Comparison</td><td>88</td></tr><tr><td>4.7</td><td>Summary</td><td>90</td></tr><tr><td>5</td><td>ADAPTING GRANULARITY FOR A BETTER CONTACT-OPPORTUNITY EXPLOITATION</td><td>93</td></tr><tr><td>5.1</td><td>Problem Statement</td><td>93</td></tr><tr><td>5.2</td><td>Objectives and Contributions</td><td>94</td></tr><tr><td>5.2.1</td><td>More Efficient Granulation</td><td>94</td></tr><tr><td>5.2.2</td><td>Adaptivity</td><td>97</td></tr><tr><td>5.3</td><td>Contact-Based Adaptive Packetization</td><td>98</td></tr></table>
<table><tr><td>5.3.1</td><td>Contact Time Prediction</td><td>98</td></tr><tr><td>5.3.2</td><td>The Process of Packetization</td><td>99</td></tr><tr><td>5.4</td><td>Experiments</td><td>100</td></tr><tr><td>5.4.1</td><td>Transmission Using NALUs</td><td>101</td></tr><tr><td>5.4.2</td><td>Oracle-Based Experiments</td><td>102</td></tr><tr><td>5.4.3</td><td>Adaptive Packetization</td><td>104</td></tr><tr><td>5.4.4</td><td>Viewing QoE</td><td>106</td></tr><tr><td>5.4.5</td><td>Validation and Comparison</td><td>107</td></tr><tr><td>5.5</td><td>Summary</td><td>108</td></tr></table>

# 6 THE INTEGRATION OF BALCON: A BACKWARD LOSS CONCEALMENT MECHANISM

<table><tr><td>6.1</td><td>Problem Statement</td><td>111</td></tr><tr><td>6.2</td><td>Objectives and Contributions</td><td>112</td></tr><tr><td>6.2.1</td><td>Backward Loss Concealment</td><td>112</td></tr><tr><td>6.2.2</td><td>Launching Criteria of The Concealment Process</td><td>113</td></tr><tr><td>6.3</td><td>Network Demands: Requests & Responses</td><td>114</td></tr><tr><td>6.3.1</td><td>Requests: Initiating Demands</td><td>114</td></tr><tr><td>6.3.2</td><td>Responses: Serving Demands</td><td>115</td></tr><tr><td>6.4</td><td>The Functionality of BALCON</td><td>116</td></tr><tr><td>6.5</td><td>Experiments</td><td>119</td></tr><tr><td>6.5.1</td><td>Capability Estimation of The Network Demands</td><td>119</td></tr><tr><td>6.5.2</td><td>Concealment Capability of BALCON</td><td>121</td></tr><tr><td>6.5.3</td><td>The Complete Functionality of BALCON</td><td>122</td></tr><tr><td>6.6</td><td>Summary</td><td>125</td></tr></table>

# iii CONCLUSION 127

# 7 CONCLUSION AND FUTURE WORK 129

<table><tr><td>7.1</td><td>Overview</td><td>129</td></tr><tr><td>7.2</td><td>Contributions</td><td>130</td></tr><tr><td>7.3</td><td>Future Work</td><td>131</td></tr><tr><td>7.3.1</td><td>Further Improvements</td><td>131</td></tr><tr><td>7.3.2</td><td>New Domains of Research</td><td>132</td></tr></table>

# iv APPENDIX 133

# A TECHNICAL DETAILS 135

<table><tr><td>A.1</td><td>SVC Encoder/Decoder</td><td>135</td></tr><tr><td>A.1.1</td><td>Encoder</td><td>135</td></tr><tr><td>A.1.2</td><td>Decoder and Player</td><td>138</td></tr><tr><td>A.2</td><td>PSNR Calculation for SVC Videos</td><td>140</td></tr><tr><td>A.2.1</td><td>Problem Statement</td><td>140</td></tr><tr><td>A.2.2</td><td>The Limitation of PSNR Computation in JSVM</td><td>141</td></tr></table>
<table><tr><td>A.2.3</td><td>Implementing the Proposed Solutions</td><td>143</td></tr><tr><td>A.3</td><td>Functionality Adaptation of The O.N.E. Simulator</td><td>144</td></tr><tr><td>A.3.1</td><td>Analysis of Adaptation Necessity</td><td>144</td></tr><tr><td>A.3.2</td><td>Message Prioritizing</td><td>145</td></tr><tr><td>A.3.3</td><td>Adaptive Packetization & Size Tunning</td><td>146</td></tr><tr><td>BIBLIOGRAPHY</td><td></td><td>149</td></tr></table>
LIST OF FIGURES

<table><tr><td>Figure 1.1</td><td>Mobile Networking Pattern: Infrastructural Vs. Ad-hoc</td><td>14</td></tr><tr><td>Figure 1.2</td><td>Multihop Mobile Ad-hoc Network (MANET)</td><td>14</td></tr><tr><td>Figure 1.3</td><td>Functionality of The Store-Carry-Forward Paradigm</td><td>15</td></tr><tr><td>Figure 2.1</td><td>Density Patterns of Wireless Networks</td><td>24</td></tr><tr><td>Figure 2.2</td><td>Multihop Data Delivery in MANET</td><td>25</td></tr><tr><td>Figure 2.3</td><td>Functionality of Store-Carry-Forward</td><td>26</td></tr><tr><td>Figure 2.4</td><td>Opportunistic Network Environment (ONE) Simulator's Functional Modules [1]</td><td>32</td></tr><tr><td>Figure 2.5</td><td>ONE Simulator's GUI</td><td>32</td></tr><tr><td>Figure 2.6</td><td>I-, B- and P-frames in a Group-of-Pictures (GoP)</td><td>35</td></tr><tr><td>Figure 2.7</td><td>Example of Temporal Scalability</td><td>38</td></tr><tr><td>Figure 2.8</td><td>Example of Spatial Scalability</td><td>38</td></tr><tr><td>Figure 2.9</td><td>Example of Signal-to-Noise Ratio (SNR) Scalability</td><td>38</td></tr><tr><td>Figure 2.10</td><td>Example of Scalable Video Coding (SVC) Layers</td><td>39</td></tr><tr><td>Figure 2.11</td><td>Operating Points</td><td>40</td></tr><tr><td>Figure 2.12</td><td>NAL Units (NALUs) in a GoP</td><td>42</td></tr><tr><td>Figure 3.1</td><td>Classified Related Works: Network Types</td><td>47</td></tr><tr><td>Figure 3.2</td><td>Classified Related Works: Solution Method</td><td>49</td></tr><tr><td>Figure 3.3</td><td>Classified Related Works: Evaluation Metrics</td><td>50</td></tr><tr><td>Figure 4.1</td><td>Trade-off Dimensions for Generic and Video Data Delivery</td><td>65</td></tr><tr><td>Figure 4.2</td><td>Magnitude</td><td>65</td></tr><tr><td>Figure 4.3</td><td>Two Result Points</td><td>67</td></tr><tr><td>Figure 4.4</td><td>An Example Run of Prioritized Layered Routing</td><td>68</td></tr><tr><td>Figure 4.5</td><td>Video Sequences</td><td>70</td></tr><tr><td>Figure 4.6</td><td>File Size Distribution Among Scalability Layers, Video: Bus</td><td>71</td></tr><tr><td>Figure 4.7</td><td>File Size Distribution Among Scalability Layers, Video: Highway</td><td>72</td></tr><tr><td>Figure 4.8</td><td>SVC File Size Comparison</td><td>72</td></tr><tr><td>Figure 4.9</td><td>SVC Layers</td><td>73</td></tr><tr><td>Figure 4.10</td><td>Operating Points (OPs) Size Distribution</td><td>75</td></tr><tr><td>Figure 4.11</td><td>SVC Operating Points</td><td>76</td></tr><tr><td>Figure 4.12</td><td>Helsinki Map</td><td>77</td></tr><tr><td>Figure 4.13</td><td>Density Patterns of Wireless Networks</td><td>78</td></tr><tr><td>Figure 4.14</td><td>Map-Based Experiments</td><td>80</td></tr><tr><td>Figure 4.15</td><td>Quality Distribution</td><td>82</td></tr></table>
<table><tr><td>Figure 4.16</td><td>Open-Area Experiments</td><td>86</td></tr><tr><td>Figure 4.17</td><td>Overhead Comparison</td><td>88</td></tr><tr><td>Figure 5.1</td><td>NALUs in One GoP of an SVC Video</td><td>95</td></tr><tr><td>Figure 5.2</td><td>The 3-Sigma Rule</td><td>99</td></tr><tr><td>Figure 5.3</td><td>Transmission of NAL-Units</td><td>102</td></tr><tr><td>Figure 5.4</td><td>Distribution of Contact Times</td><td>103</td></tr><tr><td>Figure 5.5</td><td>Oracle-Based Packetization</td><td>103</td></tr><tr><td>Figure 5.6</td><td>Adaptive Packetization</td><td>104</td></tr><tr><td>Figure 5.7</td><td>Combined Solution: Conditioned Packetization</td><td>106</td></tr><tr><td>Figure 6.1</td><td>Network Demands: One Potential</td><td>120</td></tr><tr><td>Figure 6.2</td><td>Network Demands: Multiple Potentials</td><td>121</td></tr><tr><td>Figure 6.3</td><td>Transmission of NAL-Units</td><td>123</td></tr><tr><td>Figure 6.4</td><td>Delivery Progression of an Undelivered BL and an Undelivered EL</td><td>123</td></tr><tr><td>Figure 6.5</td><td>Transmission of NAL-Units + Applying BALCON</td><td>124</td></tr><tr><td>Figure A.1</td><td>Snapshot of PSNR Values using JSVM [2]</td><td>141</td></tr><tr><td>Figure A.2</td><td>The Limitation of JSVM's PSNR Computation Due to Different Temporal Resolutions</td><td>141</td></tr><tr><td>Figure A.3</td><td>Solution to Temporal Resolution Difference</td><td>142</td></tr><tr><td>Figure A.4</td><td>The Limitation of JSVM's PSNR Computation Due to Different Spatial Resolutions: Problem & Solution</td><td>142</td></tr><tr><td>Figure A.5</td><td>ONE's Basic Classes</td><td>145</td></tr></table>

LIST OF TABLES

<table><tr><td>Table 2.1</td><td>Multihop Networks</td><td>27</td></tr><tr><td>Table 2.2</td><td>Peak Signal-to-Noise Ratio (PSNR) to Mean Opinion Score (MOS)</td><td>43</td></tr><tr><td>Table 3.1</td><td>Literature Summary</td><td>51</td></tr><tr><td>Table 3.2</td><td>Literature Summary, Simulation Setup</td><td>52</td></tr><tr><td>Table 3.3</td><td>Granularity Techniques</td><td>55</td></tr><tr><td>Table 3.4</td><td>Related Works Summary: Adaptivity</td><td>57</td></tr><tr><td>Table 3.5</td><td>Related Works Summary: Loss Recovery</td><td>60</td></tr><tr><td>Table 4.1</td><td>Sizes and Quality Values of the Operating Points</td><td>76</td></tr><tr><td>Table 4.2</td><td>Simulation Configuration</td><td>79</td></tr><tr><td>Table 4.3</td><td>Average Quality Levels</td><td>82</td></tr><tr><td>Table 4.4</td><td>Normalized Average Quality Levels</td><td>83</td></tr></table>
<table><tr><td>Table 4.5</td><td>Viewing Experience Evaluation</td><td>84</td></tr><tr><td>Table 4.6</td><td>Average Quality Levels (Open-Area)</td><td>86</td></tr><tr><td>Table 4.7</td><td>Average Quality Levels (Open-Area)</td><td>87</td></tr><tr><td>Table 4.8</td><td>Viewing Experience Evaluation (Open-Area)</td><td>87</td></tr><tr><td>Table 5.1</td><td>The Distribution of NALUs in The Sample Videos</td><td>95</td></tr><tr><td>Table 5.2</td><td>Average and Normalized Quality Level</td><td>106</td></tr><tr><td>Table 5.3</td><td>Viewing Experience Evaluation</td><td>107</td></tr></table>

LISTINGS

<table><tr><td>Listing 4.1</td><td>Prioritized Layered Routing</td><td>69</td></tr><tr><td>Listing 4.2</td><td>The Selection of Operating Points Path</td><td>74</td></tr><tr><td>Listing 4.3</td><td>The Selection of Operating Points Path</td><td>75</td></tr><tr><td>Listing 5.1</td><td>Adaptive Packetization at Node X: Reception &amp; Transmission</td><td>101</td></tr><tr><td>Listing 5.2</td><td>Adaptive Packetization at Node X: The Combined Solution</td><td>105</td></tr><tr><td>Listing 6.1</td><td>BALCON Functionality - 1</td><td>117</td></tr><tr><td>Listing 6.2</td><td>BALCON Functionality - 2: Utility Functions</td><td>118</td></tr><tr><td>Listing A.1</td><td>SVC Encoding Instruction</td><td>135</td></tr><tr><td>Listing A.2</td><td>SVC Encoding: JSVM Main Configuration File</td><td>136</td></tr><tr><td>Listing A.3</td><td>SVC Encoding: JSVM Configuration File layero.cfg (basic)</td><td>136</td></tr><tr><td>Listing A.4</td><td>SVC Encoding: JSVM Configuration File layer2.cfg (basic)</td><td>137</td></tr><tr><td>Listing A.5</td><td>SVC Encoding: JSVM Configuration File layero.cfg</td><td>137</td></tr><tr><td>Listing A.6</td><td>SVC Encoding: JSVM Configuration File layer1.cfg</td><td>137</td></tr><tr><td>Listing A.7</td><td>SVC Encoding: JSVM Configuration File layer2.cfg</td><td>138</td></tr><tr><td>Listing A.8</td><td>SVC Encoding: JSVM Configuration File layer3.cfg</td><td>138</td></tr><tr><td>Listing A.9</td><td>Message Creation in Spray-and-Wait (SnW)</td><td>145</td></tr><tr><td>Listing A.10</td><td>Prioritized Message Creation in SnW</td><td>146</td></tr><tr><td>Listing A.11</td><td>Update Contact Times on Hosts Disconnections</td><td>147</td></tr><tr><td>Listing A.12</td><td>De-Packetize at Sender</td><td>147</td></tr><tr><td>Listing A.13</td><td>De-Packetize at Receiver</td><td>148</td></tr></table>
ACRONYMS

AP Access Point

ARQ Automatic Retransmission Request

AU Access Unit

AVC Advanced Video Coding

BALCON Backward Loss Concealment

BL Base Layer

CIF Common Intermediate Format

DTN Delay Tolerant Network

EL Enhancement Layer

FEC Forward Error Correction

FLC Frame Loss error-Concealment

fps frame per second

GoP Group-of-Pictures

GPS Global Positioning System

GUI Graphical User Interface

HEVC High Efficiency Video Coding

ISO/IEC International Organization for Standardization / International Electrotechnical Commission

ITU-T International Telecommunication Union - Telecommunication Standardization Sector

JSVM Joint Scalable Video Model

MANET Mobile Ad-hoc Network

MBM Map-based Movement

MDC Multiple Description Coding

MMS Multimedia Messaging Service
**MOS** Mean Opinion Score

**MPEG** Moving Pictures Experts Group

**MPQM** Moving Pictures Quality Metric

**MSE** Mean Square Error

**NAL** Network Abstraction Layer

**NALU** NAL Unit

**OppNet** Opportunistic Network

**ONE** Opportunistic Network Environment

**OP** Operating Point

**OSD** OpenSvc Decoder

**POI** Point-of-Interest

**P2P** Peer-to-peer

**PSNR** Peak Signal-to-Noise Ratio

**QCIF** Quarter CIF

**QoE** Quality-of-Experience

**QoS** Quality-of-Service

**RW** Random Walk

**RWP** Random Way-Point

**SCF** Store-Carry-Forward

**SHM** SHVC Test Model

**SHVC** Scalable HEVC

**SNR** Signal-to-Noise Ratio

**SPMBM** Shortest Path Map-Based Movement

**SSIM** Structural Similarity Index

**SVC** Scalable Video Coding

**SnW** Spray-and-Wait

**TTL** Time-to-Live
UGC User-Generated Content

VCEP Video Coding Expert Group

VCL Video Coding Layer

VQM Video Quality Metric

WDM Working Day Movement
# Part I

## RESEARCH POSITIONING

Chapter 1: Introduction.

Chapter 2: Thematic Background.

Chapter 3: Related Literature.

> The most profound technologies are those that disappear.
> They weave themselves into the fabric of everyday life,
> until they are indistinguishable from it

> — Mark Weiser
<figure><img src="image_4.png" /></figure>
# INTRODUCTION

## 1.1 MOTIVATION

### 1.1.1 *The Emergence of Mobile Ad-hoc and Opportunistic Networks*

Over twenty years ago, computing paradigms with higher flexibility and accessibility than moving a portable computer elsewhere, were still an outlook for the future. The ubiquitous presence of computing and computing elements was envisioned by Weiser in 1991 [3]. He claimed that in order to implement a real ubiquitous computing paradigm, “computers have to be better integrated until they disappear in the background, and become indistinguishable from any other element of everyday life.” Following the continuously expanding communication evolution, people nowadays can touch the essence of ubiquitous computing through the massive growth of handheld devices, both quantitatively and qualitatively. Devices like smartphones, tablets, MP3-players and many others, have become equipped with different functionalities and present in almost every environment. Hence, users now are offered high capabilities of computation power, battery lifetime, storage capacity, content generation tools (e.g. camera, voice recorder, etc.) and communication technologies (e.g. 3G/4G, WiFi, bluetooth, etc.).

This wide range of extra capabilities has permitted a natural evolution of the networking patterns, by which multiple devices may communicate, interact and share content. Alongside the standard infrastructural communication models (e.g. 3G/4G), devices are enabled to communicate using their built-in short range technologies. Bluetooth and IEEE 802.11 WiFi are the most common examples for establishing such an ad-hoc short range communication. Consequently, this has opened the door for a new era of mobile ad-hoc networks, shortly known as MANETs [4]. The general idea behind mobile ad-hoc networking is to offer a decentralized connection, which decouples the communicating nodes<fnref n="1" /> from access points and base stations. That is, when two nodes are physically close enough to be in the communication range of each other,

<footnote n="1">¹ Users with communication-enabled handheld devices.</footnote>
they can substitute the data exchange through a centralized infrastructural entity (Figure 1.1a), with the ad-hoc short-range alternative (Figure 1.1b). This way, the two nodes can overcome possible problems associated with infrastructural networks, e.g. weak coverage, congestions, censorship, etc.

<figure><img src="image_5.png" /><figcaption>Figure 1.1: Mobile Networking Pattern: Infrastructural Vs. Ad-hoc</figcaption></figure>

Moreover, MANETs are not limited to simple direct communications, which go through one hop from source to destination. A MANET communication might have a longer path, and hop through multiple intermediary nodes to reach the destination. The communication distance is measured then by the number of hops, that was required to bridge the source and distance nodes. This is why this kind of networks and all its underlying categories are referred to as *Multihop* networks [5]. Figure 1.2 depicts a simple MANET example, where nodes’ intersecting communication ranges allow to establish a communication from source to destination, with a distance being equal to three.

<figure><img src="image_6.png" /><figcaption>Figure 1.2: Multihop MANET</figcaption></figure>

A continuous and unbroken path from source to destination, as the one shown in Figure 1.2, is not only an option for MANETs but a functioning condition. An end-to-end path, regardless the number of hops, must be available for a message to be successfully delivered. Any disconnection on the path, due to nodes’ mobility and topology changes, will result in a transmission failure.
To tolerate such disconnections and resulting delays, Delay Tolerant Networks (DTNs) and Opportunistic Networks (OppNets) emerged. When the occurrence and location of disconnections are predictable, DTNs can push more tolerance into the network functionality by allowing specific intermediary nodes to carry received messages until having the opportunity to forward them again. This behavior is known as the Store-Carry-Forward (SCF) paradigm. It lays the end-to-end connectivity condition aside, and introduces a new form of ad-hoc networks based on delay tolerance and opportunistic message forwarding [6, 5]. The corresponding functionality is expressed in Figure 1.3 through timely separated snapshots. It shows how an intermediary node may deliver a message from source to destination without having to be connected with both at the same time. Mobility makes it possible to bridge nodes temporally, even if they are spatially disconnected.

<figure><img src="image_7.png" /><figcaption>Figure 1.3: Functionality of The Store-Carry-Forward Paradigm</figcaption></figure>

Otherwise, when the occurrence and location of disconnections are unpredictable, Opportunistic Networks (OppNets) allow the network to function in a fully dynamic fashion. OppNets are regarded as multihop networks with a valid Store-Carry-Forward (SCF) paradigm for any arbitrary number of intermediary nodes before reaching the destination. Consequences of the offered dynamicity and flexibility include advantages and disadvantages. On the first hand, OppNets support indirect end-to-end data delivery and possess a wider communication range, that is given by the dynamic network topology. Nevertheless, on the other hand, because forwarding opportunities depend on nodes’ mobility, communication disruptions and uncertain data delivery are dominant. These characteristics make the usual use case scenarios of OppNets limited to the exchange of small messages, in relation for example to traffic notifications or disaster alarms [5].

### 1.1.2 Target Applications

Beside the networking pattern, the availability of highly capable handheld devices has also revolutionized the content generation prospects through the simplification of producing, storing and sharing audio/visual content.
Sharing multimedia User-Generated Content (UGC) can take place either on social networks like YouTube and Facebook, or using messaging services and applications like MMS, WhatsApp and Google Hangouts, which all go through infrastructural communications. Nevertheless, special scenarios or situations for multimedia dissemination do exist, where users need to lay infrastructural means aside and switch to a multihop ad-hoc alternative. Examples are when infrastructural communications are subject to undesired censorship, are not available, or apply extra costs.

#### 1.1.2.1 Censorship

Infrastructural communications can be easily subject to undesired censorship by third parties, including but not limited to dictator governments. Any data exchange must go through central service providers, which can analyze the data and identify the concerned users.

Consequences of detecting sensitive data may range from a simple denial of service to prevent data delivery, to extremely pursue and detain people. Therefore, OppNets can provide an ad-hoc alternative that lays central service providers aside.

*Example scenario: Scattered fleeing anti-government demonstrators, sharing sensitive content that must be kept out of censors' reach.*

#### 1.1.2.2 Connection Absence

Despite the massive deployment of cellular infrastructures, a network connection like 3G/4G might fail in far rural areas due to coverage problems, or in over-crowded urban areas due to network congestions.

*Example scenario: Participants in a nature excursion in a rural geographical area, sharing image/video shots. The area is not covered by an infrastructural communication, and an ad-hoc connection has to be established.*

Furthermore, another possibility is the collapse of infrastructural network in emergency situations due to direct damages.

*Example scenario: Network providers or power supplies crash in a war zone, a terrorist attack or a natural disaster hit.*

In both cases, OppNets provide an ad-hoc alternative that can still function with the aid of the mobile users moving in, to and out of the concerned area.

#### 1.1.2.3 Over-Costs

Data usage is usually size- or time-limited by mobile providers or public access points, which does not fit for exchanging large multimedia content. A worse case is when a user is roaming, where extra fees apply.

*Example scenario: Foreign tourists (on roaming), sharing image/video shots.*
So, even if the area is covered by an infrastructural communication, *OppNets* provide
a free access to an ad-hoc network that can be established anytime and anywhere.

1.1.2.4 Summary

Motivated by those example scenarios, this dissertation focuses on designing a video dissemination scheme in Opportunistic Networks within the scope of the defined research problems in Section 1.2.

1.2 RESEARCH PROBLEMS

OppNets are human-centric, that is, data forwarding opportunities tightly depend on how humans move and come in contact with each other. OppNets do not impose strict preconditions as a continuous end-to-end connectivity to ensure data delivery, assuming that the Store-Carry-Forward (SCF) paradigm will overcome the disconnections on the multihop delivery path. Consequently, challenging specificities must be taken into account when designing any communication scheme in the context of OppNets. These include unanticipated delivery delays, high loss ratios and an unstable connectivity due to the continuously changing network conditions, which affect the contact patterns among nodes, and hence the forwarding opportunities. Moreover, implementing a video dissemination scheme in OppNets also involves new design and evaluation requirements. First, OppNets would expose large-sized video data to partial losses, which can result in whole failures because of the continuity of the video medium. Second, the video viewing QoE can not be easily implemented by the means of the perceived video quality because of the presence of other important criteria, as the varying resources (e.g. bandwidth and storage) and the varying delivery conditions (e.g. delivery ratio and delay).

Therefore, the broad research problem at the core of this thesis is:

(P) *How to design and evaluate a video dissemination scheme for infrastructure-less Opportunistic Networks?*

Where the term "dissemination" in this context refers to the category of routing tech-
niques for *OppNets*, which is defined by Pelusi et al. [5] as a form of "controlled
flooding." On the contrary to the classical meaning, this does not necessarily involve
broadcasting to multiple recipients, but a single recipient is acceptable according to
this definition.

The challenging specificities of OppNets, along with the videos' large volumes, present the fragmentation<fnref n="2" /> as a natural candidate for the solution. It allows to reduce the transmission units' volumes, to split large video content into smaller chunks and then to reach the destination through different paths and at different timestamps.

<footnote n="2">² or partitioning, or granulation.</footnote>
Furthermore, depending on the coding algorithm, multimedia files can tolerate a cer-
tain amount of loss at the expense of quality, offering to view the content at multiple
quality levels. Consequently, our first specific research problem can be formulated as:

(P₁) How to granulate a video and route the resulting chunks, to improve the viewing QoE and resist partial losses?

(P₁.₁) A corresponding sub-problem is then: *How to define and measure the viewing QoE?*

The importance of the adaptivity to the changing OppNet conditions arises from the fact that in more stable systems like MANETS, the setup of the fragmentation (e.g. the size and number of the smaller chunks) can be predetermined. On the contrary for OppNets, this is not possible due to the unstable connectivity and dynamically changing network conditions, like node density and mobility. Thus, the second research problem to be addressed is:

(P2) How to adaptively tune the size of the data chunks, with respect to OppNet's changing conditions?

Lastly, the usual case in *OppNet* communication schemes is that the destination node plays a passive and inactive role, while data is pushed by the source. According to the degree of dependency between the different data chunks, small fractions of partial losses may put the destination (receiving node) into a long or endless suspension. Hence, we formulate our last research problem as:

(P3) *How to design a loss concealment mechanism at the destination node, to enable reacting to small amounts of loss?*

1.3 OBJECTIVES & HYPOTHESIS

Concluding from the last section, our objectives regarding a video dissemination
scheme in Opportunistic Networks are:

EFFECTIVENESS manifests itself by two parameters, delivery ratio and delay, both objectively affecting the viewing experience of the video upon reception.

1. Delivery ratio: is the percentage of the delivered data, to the intended amount of data to be delivered.

2. Delivery delay: is the waiting time between the start of sending a video by the source, and when it can be viewed by the destination.
EFFICIENCY manifests itself by the overhead, which is measured differently according to the transmission model and the routing technique. In dissemination-based routing, as defined above, the overhead is given by the Equation 1.1.

$$overhead = \frac{I_{data}}{D_{data}} \qquad (1.1)$$

where

$D_{data}$ : The amount of successfully delivered data

$I_{data}$ : The initiated amount of data, including the redundancy of the "controlled-flooding" routing

Toward these objectives, the thesis argues that applying a scalable layering video coding, which fragments videos into parts (called layers) representing overlaid levels of quality, is the first clue of the solution.

### 1.3.1 Assumptions

The research area of Opportunistic Networks is too broad, and therefore it must be narrowed by drawing constraints and assumptions on some aspects, which can not be addressed in this thesis.

* Energy resources: optimizing the energy consumption in ad-hoc network is an independent research area, and hence not considered in our contribution.

* Cooperation: participating nodes are assumed to be cooperative by nature, without a need to implement a framework for incentives or consider message drops at "malicious" nodes.

* Security: Disseminated content is assumed to be safe from dropping, eavesdropping, intrusion and forgery.

* Social network: no overlaid social network is assumed to be present beside the ad-hoc network of the participating nodes.

## 1.4 THESIS CONTRIBUTIONS

Conforming with the presented research problems in Section 1.2, this thesis contributes to the field of Opportunistic Networks by designing and evaluating a communication scheme for video dissemination in a fully infrastructure-less and delay-tolerant context. This scheme covers the following contributions:
(C₁) The scheme applies a scalable video coding technique, which granulates videos into scalable layers of smaller volumes, holding different levels of quality. The dependency among layers marks them with multiple unequal importance degrees. This property is exploited to prioritize the video layers and route them with unequal degrees of redundancy proportionally to their importance. As a consequence, a reasonable trade-off between the delay and quality parameters of the viewing experience is obtained. The playout delay is reduced by stressing on faster and more reliable delivery of layers with lower quality (but higher importance). Moreover, the quality parameter is not laid aside, thanks to the space for later arriving quality-enhancing layers.

In order to evaluate (and compare) the different measurement parameters on a single basis, a definition of the viewing QoE is proposed. With the aid of this definition, delivering an objectively better video viewing experience is argued, in comparison with the dissemination of non-scalable video within the same context.

*Relevant publication: Klaghstan et al. [7].*

(C₂) The scheme takes the fragmentation into a deeper level, by not being limited to the scalable layers (that have predetermined sizes) as the granules<fnref n="3" />. The network's varying conditions cause fixed-size layers to fall into one of two problems regarding the durations of data forwarding opportunities:

* either a layer is too big to be sent during the given forwarding opportunity, so a transmission failure will occur.

* or it is too small, so it is successfully sent during the given forwarding opportunity, which is still open but is not sufficiently long to send a complete second layer. Hence the opportunity is not optimally exploited.

Therefore, the scheme we propose enables each node to record a history of environmental information regarding the contacts and forwarding opportunities, and use this history to predict future opportunities and optimize the units' sizes accordingly. Consequently, by complementing the solution of (C₁) with the new proposal of (C₂), the video viewing QoE is enhanced in terms of both data delivery and delay.

*Relevant publication: Klaghstan et al. [8].*

(C₃) The scheme involves the destination node by implementing a loss concealment mechanism at its side, with the capability to react to an amount of loss. The implemented concealment mechanism functions in a composite manner with a twofold profit: 1) a content-based video frame loss concealment, and 2) a network-demands-based loss concealment, where demands are initiated and

<footnote n="3">³ or fragments, i.e. the individual composing units.</footnote>
cast to other nodes in the network in search for the missing data parts.
This part of the solution joins the prior two ones as a second step that comes
afterwards. The receiver node starts receiving data parts that were prepared
by the source node using (C₁) and (C₂). Then, it applies (C₃) to recover the
few and small (however critical) data parts that failed to arrive in the first step.
Implementing this mechanism at the receiver side helped to enhance the video
viewing QoE through a better data delivery.

*Relevant publication: Klaghstan et al. [9].*

1.5 THESIS ORGANIZATION

The next chapters of the thesis are organized as the following:

CHAPTER 2: highlights the theoretical background of the addressed themes in this thesis, including:

* The target domain of ad-hoc networks.

• The simulation modeling for this type of networks.

* The fundamentals of video coding and its available techniques.

CHAPTER 3: discusses works in the literature related to our research. It starts with a general overview of state-of-the-art video communication schemes in multihop networks. Then it focuses more on the works that are directly related to the identified research problems.

CHAPTER 4: presents the first contribution (C₁), which focuses on video granulation to shift the transmission units from entire videos to smaller parts. It also defines the viewing-experience evaluation metric.

CHAPTER 5: presents the second contribution (C₂), which aims to vary and tune the sizes of the video data chunks in a dynamic and adaptive way according to the *OppNets* changing conditions.

CHAPTER 6: presents the third contribution (C₃), which aims to induct a conceal-
ment mechanism at the destination node.

CHAPTER 7: concludes this work by giving a short summary of the addressed issues,
and suggesting possible directions of future research.

APPENDIX A: overviews the essential technical material that enables delivering the scientific contribution of this thesis. It includes instructions, implementations and techniques from different addressed aspects.
* * *
# THEMATIC BACKGROUND

This chapter highlights the theoretical background of the topics addressed in this thesis: Section 2.1 discusses the target domain of ad-hoc networks, and Section 2.2 presents the simulation modeling for this type of networks. Lastly, Section 2.3 tackles the fundamentals of video coding and its available techniques.

## 2.1 OPPORTUNISTIC NETWORKS

This section aims first to precisely define Opportunistic Networks (OppNets) against other types of multihop networks, and derive key differences among them. Then, it discusses available data delivery mechanisms in OppNets and their corresponding applications and requirements.

### 2.1.1 Multihop Networks: Terminology & Taxonomy

As presented in Chapter 1, the massive growth of mobile devices and their built-in technologies has allowed the emergence of autonomous multihop ad-hoc networks beside their infrastructural counterparts. The advancement of applications from early military scenarios to more diverse civil ones [10], introduced new adaptation requirements and forked the multihop networking paradigm into Mobile Ad-hoc Networks (MANETs) and Delay Tolerant Networks (DTNs), and the latter differentiated then between DTNs and Opportunistic Networks (OppNets) [5].

However, these three subclasses of multihop networks are not always precisely separated in the literature, and sometimes interchangeably misused because of some similarities and common characteristics. For example, all the three types support mobility; MANETs and DTNs may include sub-communities; and DTNs and OppNets rely on the Store-Carry-Forward (SCF) paradigm. Nevertheless, we argue in this thesis that the three subclasses of multihop networks have different properties in terms of connectivity, data delivery and network topology. Pelusi et al. [5] trace all these differences back to a single factor: the density, which by ranging its value higher or lower
may alter between the different forms of multihop networks. Krishnamachari et al. [11] represent wireless networks as random graphs, with vertices referring to mobile nodes and edges to established connections. The density of the network, given by the density of the graph edges, is classified into three levels: dense, medium and sparse, which are visually illustrated<fnref n="1" /> in Figure 2.1.

<figure><img src="image_8.png" /><figcaption>Figure 2.1: Density Patterns of Wireless Networks</figcaption></figure>

This classification is also compatible with the network partitioning patterns proposed by Spyropoulos et al. [13]. These latter claim that according to the mobility and transmission ranges, a wireless network may fall into one of the following categories:

1. Well-connected: The network is very dense, and shape an almost complete graph. A continuous path between any two nodes is most likely to exist, which fulfills the end-to-end connectivity requirement of MANETs.

2. Connectivity islands: The network is composed of diverse connected partitions, with no spatial direct interconnections between them. The possibility for a node to move from one partition to another interconnects them temporally, and shapes the core of DTNs.

3. Sparse: The network is composed of individual nodes, who meet only opportunistically. Therefore, at any instant of time, there is only a small number of active connections. OppNets fall in this category.

### 2.1.1.1 Mobile Ad-hoc Networks (MANETs)

MANETs are defined as autonomous self-organizing networks, composed by mobile nodes with short range ad-hoc communications [10]. Data delivery in MANETs can go through a number of hops from source to destination, on a continuous path that has to be planned prior to launching the delivery process, and is able to end-to-end connect the source and the destination together. Any member node in the network

<footnote n="1">¹ Illustrations generated on GraphTea [12]</footnote>
may be employed as a relay for the good of messages delivery. An example of this is illustrated in Figure 2.2, with a source, a destination and two relay nodes, all within the corresponding communication ranges.

<figure><img src="image_9.png" /><figcaption>Figure 2.2: Multihop Data Delivery in MANET</figcaption></figure>

However, nodes' mobility is unlimited, so that nodes can freely move in the environment and consequently change connection pairs in the communication range. MANETs regard such network topology changes and resulting disconnections as disruptions that eliminate the already planned end-to-end paths, and necessitate planning new ones [14].

**TOPOLOGY** Although MANET's topology may rapidly and frequently change, new distributions and nodes have to be recognized in order to be able to establish new end-to-end paths [15]. Since MANETs assume a regular presence of end-to-end paths and an immediate update of these paths upon topology changes, the network in general has to be dense and fully connected [4], as shown in Figure 2.1a.

**ROUTING** The necessary presence of end-to-end paths in MANETs affects the design of routing protocols. According to the way paths are established, MANET routing protocols can be classified into proactive and reactive [4, 16]. Proactive (table-driven) protocols provide each node with an updated routing information to other nodes in the network. Reactive (on-demand) protocols, on the other hand, establish the path only when a transmission has to take place. However, the common characteristic among both types of routing protocols is the TCP/IP-like design [17], which fails in the case of a sudden path break.

### 2.1.1.2 Delay Tolerant Networks (DTNs)

Delay Tolerant Networks (DTNs) differ from MANETs in their reaction behavior toward connectivity interruptions. DTNs do not assume the presence of an end-to-end connectivity, and do not regard disconnections due to mobility as disruptions. On the contrary, DTNs take advantage of users' mobility to widen the topology of the network and reach possibly far located nodes. DTNs were introduced in 2003 by Fall [6] to address applications of the so-called "challenged networks," which violate the traditional assumptions of the TCP/IP model, like stable connectivity, reliability and
constrained delays. In a DTN, the destination is not supposed to be reachable by the
source on a preplanned end-to-end path. This is overcome by applying the Store-
Carry-Forward (SCF) paradigm, which yields that any node receiving a message is
able to store and carry it, until an opportunity of forwarding it to another node exists.
This functionality is illustrated in Figure 2.3, which depicts a source, a destination
and an intermediary node that comes in contact with them at different time instants.

<figure><img src="image_10.png" /><figcaption>Figure 2.3: Functionality of Store-Carry-Forward</figcaption></figure>

TOPOLOGY DTN's overall topology is split into subnetworks, that are called "islands" as in [13], "regions" as in [6], or "communities" when they refer to social relationships. Each of these subcomponents has an ongoing intra-connectivity within [5, 6, 13], but inter-connections between them can take place only indirectly through the SCF paradigm. DTNs assume that each island can predict and localize disconnections [15]. This property affects the design of routing and data delivery protocols.

ROUTING The purpose of DTNs is to provide interoperability between the diverse disconnected subnetworks, regardless of the intra-connection within each subnet-work [6]. Since the network is assumed to be able to predict the locations of possible disconnections, it setups specific nodes as "gateways" at those points, in order to connect the separated regions through their mobility [15, 6, 13]. Once the assumption of disconnections predictability is no longer valid, the domain of the target multihop ad-hoc network moves to OppNets.

2.1.1.3 Opportunistic Networks (OppNets)

Opportunistic Networks (OppNets) share their basic characteristics with DTNs, so that earlier in the literature both terms were often used to refer to the same concept of networks [14, 18]. However, Pelusi et al. [5] introduce OppNets as being derived from DTNs, but representing a more flexible form of it. Similarly to DTNs, OppNets do not assume an end-to-end connectivity as a precondition for data delivery. They con-
sider users' mobility as an advantage, and tolerate resulted disconnections via SCF paradigm. Nevertheless, unlike DTN's subcomponents and their predicable disconnections, OppNets assume zero-knowledge about the network topology, which makes each relay node responsible for deciding on the next hop for routing based on local information only (e.g. previous and currently available contacts) [5, 19]. While the objective in DTN is to interconnect heterogeneous connectivity islands, nodes in OppNet are standalone. Consequently, OppNets can be defined based on individual-nodes, on the contrary to the network- and subnetwork-based definition of DTNs [20].

**TOPOLOGY** OppNet's architecture is based on the interoperability between standalone nodes, each relying only on local information with regard to previous and currently available contacts. Hence, according to Figure 2.1, OppNets belong to the third category of sparse networks [21, 22], where no end-to-end paths exist, and the individually moving nodes are the building elements. If a snapshot of the network is taken at any instant of time, it will show scattered nodes with only a few number of active connections.

**ROUTING** Contrarily to DTN, relaying messages in OppNet is not limited to specific gateway nodes. Because path breaks and disconnections may unpredictably take place anywhere in the network, any node in OppNet can play the role of a relay [5, 18]. However, once a message leaves a DTN connectivity island on a gateway node, the routing between intermediary nodes will be identical to how it works in OppNet. Therefore, both DTNs and OppNets share the same literature on routing strategies (as will be presented next).

### 2.1.1.4 Summary & Discussion

The outlined differences and characteristics of the multihop networks subclasses are summarized in Table 2.1.

<table><caption>Table 2.1: Multihop Networks</caption><thead><tr><th></th><th>MANET</th><th>DTN</th><th>OppNet</th></tr></thead><tbody><tr><th>Topology</th><td>Dense</td><td>Connectivity islands or partitions</td><td>Sparse with standalone nodes</td></tr><tr><th>Connectivity</th><td>end-to-end</td><td>Store-Carry-Forward</td><td>Store-Carry-Forward</td></tr><tr><th>Routing</th><td>Full knowledge</td><td>Basic graph-based knowledge</td><td>Zero previous-knowledge, Opportunistic contacts</td></tr><tr><th>Relay</th><td>Any node on a continuous path</td><td>Definite nodes on definite locations</td><td>Any node</td></tr></tbody></table>

This thesis is based on sparse OppNets with standalone nodes, that meet only oppor-
tunistically and deliver data on top of the SCF paradigm. This allows to study the delivery application under extreme conditions, which are not unlikely to happen.

### 2.1.2 Data Delivery

A large amount of works in the literature regarding data delivery and routing protocols for OppNets is available. Furthermore, a large part of this literature is shared with DTN because both types of networks function under the same philosophy of SCF and indirect end-to-end connectivity. Accordingly, a number of surveys have been published to summarize and categorize these works [13, 5, 18, 23, 24, 25, 26, 27]. Classifications in [5, 18, 24, 27] base on two criteria: replication and knowledge, to split data delivery approaches in OppNets into dissemination (flooding)-based and forward-based.

#### 2.1.2.1 Dissemination-based Routing

This type of routing is also called replication-based [13, 23] or flooding-based [18, 24] routing, and it aims to spread messages to nodes in the network using replication [5]. Redundancy is meant to compensate the absence of advanced knowledge about the network. Two extreme cases of this approach are implemented by tuning the number of message copies to be distributed in the network, and the number of hops, over which a message is allowed to move. The two implementations are the direct delivery and epidemic routing protocols.

* Direct delivery: as a lower bound, this protocol involves a single copy of source messages, that are forced to be kept at the source node until meeting the destination, to be directly delivered in a single hop. This ensures the best overhead and resources utilization, but the worst delivery probability and delay [28].

* Epidemic: implements the upper bound by an unlimited flooding [29]. In epidemic routing, a node carrying a message, replicates it to any other encountered node limitlessly, unless that node already has a copy of the message (avoid cycles) or the Time-to-Live (TTL) parameter of the message expired. Consequently, the message will spread as a disease, whose infection is a new replica of the message. This obviously enables the best possible delivery ratio and delay, but it is very resource-hungry and causes maximum overhead.

All other routing protocols lay in between these two extremes, trying to control flooding in order to trade-off delay and delivery ratio on the first hand, with resources consumption (bandwidth, storage and energy) on the other hand. To achieve that, two strategies are possible: replication control and estimation functions [13, 18].

**REPLICATION CONTROL** As with epidemic routing, messages are copied when nodes come in contact with each other. The difference is that the number of replicas
of a given message that may exist at a given time is bounded by a maximum value. Spyropoulos et al. [30] propose the Spray-and-Wait (SnW) protocol, which consists (as the name suggests) of two phases: spray and wait. During the first phase, k replicas of a message are “sprayed” to k nodes in the network. Then, these nodes “wait” until they come in contact with the destination to deliver the message. The spray phase has two variations: Vanilla and Binary. Vanilla spray replicates the message to the first k met nodes, with one copy to each. Whereas Binary spray suggests to hand over half of the copies upon each contact. Each node repeats the same until it has only one copy left, where it enters in the waiting phase.

Another possibility to control replication is to bound the number of hops, that a message is allowed to go through. This is like the already mentioned direct delivery routing protocol.

**ESTIMATION FUNCTION** In this strategy, the replication decision is not limited by a maximum number of replicas, but by an estimation function, which determines whether to exploit the contact opportunity or not. This function is evaluated based on narrow simple knowledge regarding the nature of replicated messages or the fitness of encountered nodes. Ramanathan et al. [31] and Wang et al. [32] propose prioritized epidemic routing protocols, which prioritize messages based on local information like messages' TTL or inter-node exchanged simple information to reflect messages' delivery costs. On the other hand, the PRoPHET routing protocol [33] states that when two nodes meet, they exchange summary vectors of encounters history, which indicates to each other their delivery predictability to a given destination.

### 2.1.2.2 Forward-based Routing

The forward-based routing protocols need more information about the network topology. Furthermore, for a given message, no replicas are generated in the network but the message itself is handed over along the possibly best determined path. When nodes meet, a forwarding decision has to be taken, which is conceptually similar to the estimation function of dissemination-based routing. The difference is that a forwarding decision is not concerned with whether to replicate a message or not, but with entirely handing the message over. Therefore, the decision is more sensitive, and must be based on available contextual knowledge. The simplest form of such knowledge is based on location, where forwarding takes place to a node only if is closer to the destination in a given coordination system [27]. The coordination system here can have a physical perspective, as for instance if GPS is enabled, or a conceptual perspective as proposed by Leguay et al. [34], where the distance of two nodes represent their likelihood to meet.

A higher level of knowledge encloses more specific contextual and environmental
parameters, as in the context-aware routing protocol [35], which enables the nodes to evaluate and exchange delivery probabilities toward possible and known destinations in the network. Consequently, the current carrier of a message may decide for the best next relay based on contextual information like mobility, connectivity changes and energy level.

Forward-based routing achieves a better resources consumption, because of the limitation to a single copy of the routed messages. However, this is accompanied by increased delays and computational costs [5].

### 2.1.2.3 Discussion

Dissemination based data delivery is more common in OppNets, not only because of the direct disadvantages of forward-based routing, like delay and computational complexity, but because of the unaffordable amount of necessary contextual knowledge for forward-based strategies. This family of routing protocols was originally adopted from more stable networks, e.g. wired networks or MANETs. Therefore, they are proven to perform poorly on DTNs and OppNets [27, 5, 18].

* * *

## 2.2 SIMULATION MODELING

This section introduces the need for simulation modeling as an evaluation method. A number of state-of-the-art available simulators are reviewed, with a deeper look on the Opportunistic Network Environment (ONE) simulator, which was used for all the experiments in this work. Lastly, mobility models, which are an important part for the simulation modeling, are discussed.

### 2.2.1 Overview

The performance evaluation of a proposed solution in the domain of wired or wireless network can be done by three methods of evaluation [36]:

1. Complexity analysis

2. Experiments based on real-world testbeds

3. Simulations

As Lindeberg et al. [36] argue, although performing a mathematical complexity analysis to reflect the system's performance might be the cheapest variation (in terms of applicability and usability), its complexity dramatically grows with the complexity of
the system itself. Therefore, this evaluation method is incapable of modeling whole
complex systems with a big number of interoperating components and parameters.
Real-world experiments, on the second hand, deliver reliable and actual results but
they are expensive and difficult to deploy and run. Consequently, computer-based
simulations become the most used evaluation method, as they are utilized in 75-86%
of the evaluation experiments, according to analysis surveys [37, 36].

A simulator is a software, which enables virtually implementing and evaluating a net-
work on a computer [38]. It has the advantage of making it easy to rerun experiments
at large scales, under different conditions or setup parameters. Furthermore, within
the constrained environment of a simulator, the comparability and repeatability of
experiments are better offered [22].

2.2.1.1 State-of-the-Art Simulators

There are basically four simulators, that are usually used for DTN and OppNet appli-
cations [39, 40] :

* NS-2 [41] (and NS-3 [42]) : A general network simulator, and the most used simulator for MANETs in the literature [36]. However, it has only a superficial applicability for DTNs and OppNets.

* OMNeT++ [43] : Similarly to NS-2, it is a general network simulator, based on a component and modular architecture. It also lacks good support for DTN.

* DTNSim [15] : It is developed exclusively for DTNs. It simulates message routing using SCF, but needs input data of connectivity traces to determine availability and unavailability of links between nodes.

* ONE [1] : A recent simulator for DTNs and OppNets. It supports the simulation of mobility and routing, in addition to events visualization. Since its launch in 2009, it has obtained a significant interest and a wide usage in the literature [21].

2.2.2 The ONE Simulator

2.2.2.1 *Architecture*

Opportunistic Network Environment (ONE) is an open-source Java-based simulator,
designed to implement and evaluate applications in DTN and OppNet [1, 44]. ONE is
a discrete event simulator, that is, simulation's functional modules are updated at
discontinuous simulation steps. As shown in Figure 2.4, ONE has four interoperating
functional modules:

1. Movement models
2. Routing

3. Output visualization/reports

4. Event generators

<figure><img src="image_11.png" /><figcaption>Figure 2.4: ONE Simulator’s Functional Modules [1]</figcaption></figure>

The movement model is responsible for controlling nodes’ positions in the simulated environment, and hence determining whether they are in the communication range of each other to exchange data. This information is fed into the routing module to know how to hand over messages, that were created in the event generator module. Lastly, ongoing actions can be followed graphically on the simulator’s GUI (as in Figure 2.5), or they can be written onto output textual reports for further processing.

<figure><img src="image_12.png" /><figcaption>Figure 2.5: ONE Simulator’s GUI</figcaption></figure>
### 2.2.2.2 Advantages of ONE

ONE decouples the simulations from the low-level implementation details of the wireless communication, which results in a simpler communication model between nodes that is based on only being in the reach of each other. This, according to Keränen et al. [1], “allows focusing on the evaluation of the DTN protocols, instead of fully modeling the lower layers.” Furthermore, the focus on the usage scenarios of DTNs and OppNets, frees the simulator from the complications associated with general networks support. Lastly, the open-source and modular architecture of the simulator supports extensibility and customizability of its functions to a large extent.

### 2.2.3 Mobility Models

The functionality of the movement module is based on the mobility models, which defines how the nodes move in the simulation environment. According to their generation, there are two types of mobility models: synthetic and based on real-world traces [45].

#### 2.2.3.1 Synthetic Mobility Models

These are theoretical models, and as in [40, 1] they are further classified into:

1. **Random:** Mobility is generated using mathematical random functions. Examples are the Random Walk (RW) and Random Way-Point (RWP) models [46], where initial starting points, drawn destinations and movement speed are all randomly assigned. Despite its unreality and limited performance, RWP is the most used model<fnref n="2" /> in the simulations due to its simplicity [36]. Consequently, it has become a common comparison reference in the literature.

2. **Real Mobility-Driven:** To reduce randomness and shift the model to the real-world case, mobility models can be based on real maps or real human behaviors. Map-based models derive movement paths from data on real maps. The most common examples are the Map-based Movement (MBM) and Shortest Path Map-Based Movement (SPMBM) [1]. Human behavior models are a further step, which include daily human actions, like the Working Day Movement (WDM) model [47].

MBM is similar in its core to RWP, except that the movement must follow the paths on the defined map. SPMBM is a bit more realistic, in the sense that nodes select a point on the map either randomly or from a list of interesting points, then take the shortest path on the map to that point. On the other hand, WDM

<footnote n="2">² This is to be shown later in Table 3.2</footnote>
tries to better mimic reality by modeling human activities like sleeping, working and going out, each with a different corresponding location.

### 2.2.3.2 Real-World Traces-Based Mobility Models

Mobility models, that are based on this kind of traces, do not involve any mathematical estimation, but instead they use real world measurements. Experiments are performed to track real users and collect data, that reflect different aspects of nodes' mobility and contact [40].

Although the trace-based mobility models obviously yield the most realistic setup, their main drawback is that they are collected from very specific scenarios with limited populations, and therefore they can not be reliably generalized. Furthermore, real world traces are characterized by low temporal or spatial resolutions [44, 40]. That is, frequency of scans for other devices is kept low to save battery, which results in inaccurate contacts measurements as well as missing contacts. Otherwise, locations are detected by widely separated fixed Access Points (APs).

### 2.2.4 Discussion

Against the less appropriate alternatives, simulation modeling is chosen to evaluate the proposals of this work. Furthermore, the ONE simulator is used, most importantly because of its open-source structure, which allows a flexible adaptation of its functionality in order to implement the proposed solutions of the thesis. Adaptation examples include:

* Assigning variable redundancy parameters

* Packetize small messages in one big message (and depacketize later)

* Request/response of additional messages at runtime

Regarding the mobility model, two models were utilized in the simulations. RWP, to ensure a comparison reference, and to obtain a more realistic results, simulations also included SPMBM.

* * *

## 2.3 VIDEO CODING

This section discusses video coding from the perspectives of its purposes, types and fundamentals. Then, Scalable Video Coding (SVC), which was chosen to fulfill the need for a multistream coding, is addressed in details. Lastly, an overview of video quality measurements is given.
### 2.3.1 Overview

#### 2.3.1.1 Video Coding Evolution and Fundamentals

Video coding is a critical procedure to be performed at the video source for two purposes: first, to reduce the stream bitrate for both storage and transmission purposes, and second, to enhance the reliability against possible losses or errors. The basic idea is to exploit the redundancy within a frame or between consecutive frames, in order to compress the data through redundancy reduction, and enhance the stream with error detection and recovery capabilities.

The evolution of standards for video coding was mainly defined by two organizations: the International Telecommunication Union - Telecommunication Standardization Sector (ITU-T), and the International Organization for Standardization / International Electrotechnical Commission (ISO/IEC) and its underlying Moving Pictures Experts Group (MPEG). Both organizations developed many coding standards, one of the last of which is the H.264/AVC (also called MPEG-4 Part-10), which was jointly developed to achieve high video quality at low video bitrates [48]. To control redundancy reduction and data compression, Advanced Video Coding (AVC), as an MPEG and H.26X standard, divides the sequence of frames of a video stream into a set of Group-of-Pictures (GoP). Hence, the redundancy between consecutive frames is studied within the same GoP. Frames in a GoP can be in one of three types according to their coding/decoding dependability:

* **I-frame:** Intra-frames are intra-coded independently from other frames, so that data compression only considers spatial information withing the same frame.

* **P-frame:** Predictive-frames are coded based on the previous reference frame, which is the last appearing I- or P-frame.

* **B-frame:** Bidirectional-frames are also dependently coded, but based on both previous and following reference frames, which are the last appeared and next appearing I- or P-frames respectively.

<figure><img src="image_13.png" /><figcaption>Figure 2.6: I-, B- and P-frames in a GoP</figcaption></figure>
Because of this dependency, the order of frames within a GoP affects the coding complexity and the output stream size and quality, since only the difference from the reference frame has to be coded. For instance, less I-frames would result in a smaller size, but also in a lower quality and a more complex coding process. An example of a GoP with dependencies between frames is depicted in Figure 2.6.

### 2.3.1.2 Multisream Video Coding

Contrarily to ordinary coding standards, whose output is a compressed single stream, in multistream coding a video is encoded into several scalable substreams. These substreams can then build on top of each other, to deliver all together the video's overall quality. The removal of one or more substreams would result in only degrading the video quality, instead of a whole failures as with single stream coding. Consequently, parts of the main stream can be easily removed, in order to adapt to changing conditions like heterogeneous recipient devices or varying bandwidth availability. This property is referred to as "encode once, decode many." That is, when facing new demands due to conditions changes, the same encoded video can be differently decoded as many times as needed, to cope with the corresponding demands. Re-encoding or the initiation of different representations of the same content are not necessary. Moreover, the choice of scalable multistream coding has also the advantage of fulfilling the requirement of granulation. But unlike generic granulation techniques, which split the data into meaningless parts and condition reconstructing the original data by receiving them all, scalable multirestream coding offers multi-level reconstruction. The overlaid parts can reconstruct the video body on levels with ascending quality, depending on the amount of data received.

For the purpose of scalable multirestream coding, two approaches exist: Layered Coding and Multiple Description Coding (MDC).

#### LAYERED CODING
Using this approach, the video content is coded into a number of stacked layers, each of which refers to a quality level. These layers reflect a back dependency property, which tightly links the decodability of a given layer with the reception of its precedent layers. Hence, the layers reflect different importance degrees, where the first layer (called "Base Layer") will possess the highest importance among other layers. The Scalable Video Coding (SVC), an extension of the H.264/AVC, is a state-of-the-art implemented example in this domain, and will be presented in details next.

#### MULTIPLE DESCRIPTION CODING
Contrary to layered coding, MDC splits a video stream into equally important substreams, called descriptions [49]. A base quality is obtained by decoding any description, then, the more descriptions are successfully received, the higher the video quality is.
A number of comparisons are performed between the two coding approaches [50, 51, 52, 53]. Although conclusions outline close performance regarding many metrics, like delivered quality and output source size [50], other metrics reflect remarkable differences. With regard to delivery ratio and perceived video quality, MDC has an advantage unless the layered coding powerfully protects the base layer [51, 52], in addition to a higher coding complexity of MDC [51]. Furthermore, SVC (as a layered coding technique) introduces additional advantages by the means of a further partitioning of the scalability layers into content-dependent very small units. This property will be fully utilized (as will be presented later) for adaptive routing and error concealment solutions.

### 2.3.2 Scalable Video Coding

#### 2.3.2.1 History

Scalable Video Coding (SVC) is one of the recent stable video coding standards, proposed as an extension to H.264/AVC [54]. It was developed by the Joint Video Team, which embraces both ITU-T's Video Coding Expert Group (VCEP) and ISO/IEC's MPEG [55]. An official reference implementation was also provided, under the name of Joint Scalable Video Model (JSVM) software [2].

A more recent successor to H.264/AVC is the High Efficiency Video Coding (HEVC) standard, which was completed in early 2013 [56]. A set of extensions, including the Scalable HEVC (SHVC), were standardized later in 2013 [57]. However, the SHVC Test Model (SHM) reference software was until very recently under development. The first conformance test draft appeared in late 2014 with the last stable version of SHM [58]. This very recent emergence of the standard prevented an accordant consideration in this work.

#### 2.3.2.2 Fundamentals and Objectives

The objective of SVC is to compress and encode a raw video file with a single bit-stream into another compressed form containing many sub bit-streams. Thus, an SVC-encoded video consists of one Base Layer (BL), $L_0$, and one or more Enhancement Layers (ELs), $L_1, ..., L_n$. The successful reception and decoding of the BL provides a low-quality playable version of the video. Then, further ELs would enhance the quality in one of the scalability features. SVC supports three features (or dimensions) of scalability:

* **Temporal Scalability:** A temporally scalable video can be viewed on different frame rates. Hence, a higher frame per second (fps) value is obtained with every further received temporal EL. The number of temporal layers for a given video is tightly dependent on the defined GoP size. BL delivers only one frame per GoP,
and each further temporal EL doubles the frame rate. Hence, the total number
of temporal layers is equal to log(GoP).

For example, if GoP=4 frames, there will be three temporal layers: Lt,0 (with 1
frame per GoP), Lt,1 (2 frames per GoP) and Lt,2 (4 frames per GoP).

Consequently, any SVC-encoded video with GoP>1 is temporally scalable by de-
fault, with no extra encoding complexity.

<figure><img src="image_14.png" /><figcaption>Figure 2.7: Example of Temporal Scalability</figcaption></figure>

*   **Spatial Scalability:** A spatially scalable video can be viewed on different spatial resolution. Spatial ELs increase the video resolution, most commonly in a 2:1 ratio between neighbor layers [59], although SVC can handle other arbitrary power-of-2 ratios [2]. That is, the spatial resolution will double with further ELs. Hence, the total number of spatial layers is determined with respect to two conditions: first, the already mentioned power-of-2 increment ratio, and second, that the resolution can not go under 96 × 80 [2].

<figure><img src="image_15.png" /><figcaption>Figure 2.8: Example of Spatial Scalability</figcaption></figure>

*   **Quality Scalability:** This is also called fidelity scalability. It refers to the value of the Signal-to-Noise Ratio (SNR) at given temporal and spatial resolutions. A substream with a lower SNR value supports viewing a video at the given temporal and spatial resolutions but with less sharp quality, as illustrated in Figure 2.9. SVC can support up to 15 refinement layers, however this is costly with regard to coding efficiency [60].

<figure><img src="image_16.png" /><figcaption>Figure 2.9: Example of SNR Scalability</figcaption></figure>
The total number of layers, n, is determined by the defined scalability levels in each of the scalability dimensions. Any layer $L_{i>0}$ is dependent on the precedent layers $L_0 \to L_{i-1}$. Consequently, layers $L_0 \to L_n$ reflect an ascending importance degree.

**EXAMPLE** Figure 2.10 depicts the layers' structure of an SVC-coded video, holding:

* Three frame rates: 7.5, 15 and 30 fps

* Two spatial resolutions: Common Intermediate Format (CIF) 352 x 288 and Quarter CIF (QCIF) 176 x 144

* Two SNR quality levels

<figure><img src="image_17.png" /><figcaption>Figure 2.10: Example of SVC Layers</figcaption></figure>

**OPERATING POINTS** SVC scalability levels allow to transform the quality for one step in one direction of the scalability dimensions. But beside this forward step in some direction, the transformation might cause backward steps in other directions. For example, in Figure 2.10, the transformation from EL-5 to EL-6 moves the quality forward in the spatial direction, but also backward in both temporal and SNR directions. To overcome this mismatch, the concept of Operating Points (OPs) is formulated to define virtual quality levels, which contain subsets of the scalability levels, and ensure an overall forward transformation in each enhancement step [60].

The number and the distribution of the OPs have many possibilities. Let us assume m, n and l are the number of the scalability levels of the temporal, spatial and SNR dimensions respectively. If m = n = l = 1, then the number of scalability layers: N = 1, and the number of the OPs: $N_{op} = 1$. Otherwise, N > 1 and the number of the OPs in the resulting space will be in the range:

$$2 \le N_{op} \le 1 + d_{\text{Manhattan}}(L_0, L_N) \qquad (2.1)$$
Where $d_{Manhattan}(L_0, L_N)$ is the Manhattan distance between the first and the last layers, and is calculated with the Equation 2.2.

$$ 
\begin{aligned}
d_{\text{Manhattan}}(L_0, L_N) &= d_{\text{Manhattan}}((1, 1, 1), (m, n, l)) \\
&= (m - 1) + (n - 1) + (l - 1)
\end{aligned} 
\qquad (2.2) $$

For example in Figure 2.10, $m = 3$, $n = 2$, $l = 2$, then the maximum possible number of OPs is equal to $1 + (3 - 1) + (2 - 1) + (2 - 1) = 5$.

Moreover, the distribution of the OPs can also vary, as different paths can be drawn from $L_0$ to $L_N$ in the taxicab geometry [61]. For example, derived from Figure 2.10, two (out of many other) possible sets of OPs are depicted in Figure 2.11.

<figure><img src="image_18.png" /><figcaption>Figure 2.11: Operating Points</figcaption></figure>

SET 1: depicted in red in Figure 2.11. It consists of four levels or OPs:

Point 1: at BL

Point 2: moves two steps in the temporal direction. Hence, it includes two enhancement layers (EL-1 and EL-2)

Point 3: moves one step in the SNR direction, without temporal setbacks. Hence, it includes three enhancement layers (EL-3 to EL-5)

Point 4: moves one step in the spatial direction, without temporal or SNR setbacks. Hence, it includes six enhancement layers (EL-6 to EL-11)

SET 2: depicted in blue in Figure 2.11. It consists of five levels or OPs:

Point 1: at BL

Point 2: moves one step in the spatial direction. Hence, it includes one enhancement layer (EL-6)

Point 3: moves one step in the temporal direction. Hence, it includes two enhancement layers (EL-1 and EL-7)
Point 4: moves one step in the temporal direction. Hence, it includes two enhancement layers (EL-2 and EL-8)

Point 5: moves one step in the SNR direction, without temporal or spatial setbacks. Hence, it includes six enhancement layers (EL-3 to EL-5 and EL-9 to EL-11)

The choice of a specific path among other variations for a given number of OPs is critical when the sizes of the OPs are not homogeneous, i.e. there is one or more OPs on the path, whose size is extremely bigger than the others, which makes the corresponding path not preferable. Otherwise, the issue is subject to trade-offing the order of the scalability dimensions.

### 2.3.2.3 Internal Structure

The internal structure of SVC is based on a Video Coding Layer (VCL) and a Network Abstraction Layer (NAL) [54, 55]. The coded content of SVC is represented by the VCL, which is formatted then by the NAL in a network- and storage-friendly way, by organizing the data into NAL Units (NALUs) and pushing additional information to their headers. A NALU header serves to easily extract and customize VCL content for the different possible requirements, since it contains information specifying to which scalable level the unit belongs. This is done using the following fields of the header: temporal_id, dependency_id and quality_id, which refer to the corresponding temporal, spatial and SNR layers respectively. SVC NALU header is four bytes long, one for the old AVC standard, and three additional bytes for SVC [60].

Partitioning the SVC content into NALUs is done in a content-wise way. That is, each unit represents one frame belonging to one of the scalability layers. Consequently, the units are different in size, depending on the content they carry [62]. NALUs of one frame among all layers are packed into a so-called Access Unit (AU).

**EXAMPLE** With regard to the example in Figure 2.10, the distribution of NALUs among all scalability layers, in a GoP=4 frames, would look like as in Figure 2.12.

1. The video at its BL has one frame per GoP (the lowest temporal scalability), and hence one NALU. The first and second ELs enhance the temporal resolution by adding one then two more NALUs (frames) per GoP.

2. NALUs from EL-3 to EL-5 enhance the SNR quality for the corresponding NALUs from the first step (BL, EL-1 and EL-2).

3. NALUs from EL-6 to EL-8 deliver a higher spatial resolution for the corresponding NALUs from the first step (BL, EL-1 and EL-2).

4. NALUs from EL-9 to EL-11 enhance the SNR quality for the corresponding NALUs from the last step (EL-6, EL-7 and EL-8).
<figure><img src="image_19.png" /><figcaption>Figure 2.12: NALUs in a GoP</figcaption></figure>

This architecture helps to count the number of NALUs per GoP, and hence for the
whole video.

2.3.3 *Video Quality Measurement*

In network applications, the term Quality-of-Service (QoS) covers many technical per-
formance metrics as packet-loss (the ratio of undelivered messages), overhead (the
cost of delivering a message with regard to its redundancy) and delay (waiting time
between initiation of message and delivery). In multimedia applications, on the other
hand, Quality-of-Experience (QoE) extends QoS to measure the satisfaction of end
users' experience with the perceived content quality [63, 64].

This kind of video quality measurement can be classified based on its methodology
as either subjective or objective [65]. Subjective metrics reflect the quality of video
perception by human viewers. They can only be measured by tests that require the
participation of real human testers, which makes it expensive and time consuming
[64]. On the other hand, objective metrics utilize technical parameters and mathemat-
ical models in an attempt to predict the human perception.

A commonly used subjective method is the Mean Opinion Score (MOS), which is
calculated as the average subjective judgment, out of values assigned by a set of
testers. MOS comes out on a scale from 1 (bad) to 5 (excellent) [66]. Objective alterna-
tives include many methods like for example the Video Quality Metric (VQM), which
measures the perceptual video deteriorations [67], the Moving Pictures Quality Met-
ric (MPQM), which manages to ignore error pixels if they are not perceived by the
human visual system [68], the Structural Similarity Index (SSIM), which tries to cap-
ture the structural distortions for a better correlation with the subjective techniques [69], and the well known Peak Signal-to-Noise Ratio (PSNR) function, which is calculated for each frame of the video with regard to the Mean Square Error (MSE) [70]:

$$MSE_{frame(i)} = \frac{1}{W \cdot H} \sum_{x}^{W} \sum_{y}^{H} [Y_{r}(x, y) - Y_{p}(x, y)]^2 \quad (2.3)$$

$$PSNR_{frame(i)} = 10 \times \log_{10} \frac{I^2}{MSE} \quad (2.4)$$

$$PSNR_{total} = \frac{1}{N} \sum_{i=1}^{N} PSNR \quad (2.5)$$

where

W, H : Frame's width and height

Y<sub>r</sub> : Luminance value of the reference frame in pixel (x, y)

Y<sub>p</sub> : Luminance value of the processed frame in pixel (x, y)

I : Maximum luminance value

N : Number of frames in the video

Compared to the other objective metrics<fnref n="3" /> and the expensive subjective ones, PSNR has achieved a high popularity due to its fast and simple computation and understanding [70]. Consequently, PSNR has become the most commonly used quality measurement in the literature [36]. Moreover, a conversion between PSNR and MOS is proposed by Klaue et al. [65] based on the range of the PSNR value. The conversion values are shown in Table 2.2.

<table><caption>Table 2.2: PSNR to MOS</caption><thead><tr><td>PSNR</td><td>MOS</td></tr></thead><tbody><tr><td>&gt;37</td><td>5: Excellent</td></tr><tr><td>[31, 37[</td><td>4: Good</td></tr><tr><td>[25, 31[</td><td>3: Fair</td></tr><tr><td>[20, 25[</td><td>2: Poor</td></tr><tr><td>&lt; 20</td><td>1: Bad</td></tr></tbody></table>

For multistream videos, PSNR is calculated for each of the substreams separately<fnref n="4" />. The overall PSNR is obtained then by considering the video with all its substreams present.

<footnote n="3">³ Available objective metrics in the literature are much more than the above mentioned [71].</footnote>

<footnote n="4">⁴ More details in Appendix A.2.</footnote>
### 2.3.4 Discussion

This work is based on the choice of scalable multistream coding, which offers two advantages:

* FIRST, the built-in fragmentation into smaller parts, which eases the delivery of larger data.

* SECOND, the split of quality into levels, which allows defining some metrics like delivery ratio and delay on each quality level independently. The set of all metrics among the different levels contribute to define an overall viewing experience value (more on Chapter 4).

To this end we propose to use the Scalable Video Coding (SVC), a state-of-the-art coding technique with an available official reference implementation (JSVM [2]). Lastly, the quality of the received videos is measured using the Peak Signal-to-Noise Ratio (PSNR) metric.

* * *
RELATED LITERATURE

This chapter discusses works in the literature related to our research. It starts in Section 3.1 with a general overview of state-of-the-art video communication schemes in multihop networks. Then Sections 3.2, 3.3 and 3.4 focus more on the works that are directly related to the research problems identified in Chapter 1, namely:

P₁ Video granulation and specific viewing QoE improvements,

P₂ Adaptive size tuning of the video chunks, and

P₃ Loss concealment.

Moreover, these later sections also discuss the pros and cons of the presented works with regard to their suitability for the given problems.

3.1 VIDEO COMMUNICATION SCHEMES IN MULTIHOP NETWORKS

Video applications found their way to both Delay Tolerant Networks (DTNs) and Opportunistic Networks (OppNets) through the less strict Mobile Ad-hoc Networks (MANETs). Hence, this section reviews video communication schemes in each of the given multihop domains (MANETs, DTNs and OppNets), and analyzes them based on three criteria:

1. Target multihop network.

2. Solving approach.

3. Evaluation metrics.

Each of the following subsections addresses the corresponding works from the per-
spective of one criteria at a time. All together then they serve to reflect the contribu-
tion, challenges and objectives of the addressed works, and analyze their visions in
the context of our research.
### 3.1.1 Target Multihop Network

This subsection addresses the state-of-the-art works (that are summarized later in Table 3.1) from the perspective of their target multihop network.

MANET is the most favorable multihop network for video communication, since the presence of an end-to-end connectivity enables supporting streaming applications with strict time constraints. A number of works examine many streaming scenarios of different communication models with regard to source and destination, i.e. 1:1, 1:n, n:1 and n:n. Whereas Yu et al. [72] study a routing protocol for 1:n tree multicasting, Schierl et al. [73, 74, 75] aim to merge multiple streams of the same video from different sources by implementing a multi-source (n:1) streaming scheme<fnref n="1" />. Seferoglu and Markopoulou [76, 77] extend this by merging multiple streams on paths to different recipients, so that to support n:n streaming. One the other hand, Qin and Zimmermann [78] and Mao et al. [79] also want to support multiple streams on multiple paths, but on the basis of a 1:1 streaming problem.

A MANET is established by definition considering a source, a destination and a set of intermediary relay nodes, without further external entities. However, many works deviate from the standard definition, shifting their multihop network into a new dimension. For example, Seferoglu and Markopoulou [76, 77] further add an Access Point (AP) to Internet, to shift the wireless environment to a mesh network with both infrastructure and infrastructureless alternatives. Another shift of MANET by Cabrero et al. [80] consider video streaming in sparse network configurations. The network can switch between MANET and DTN depending on path availability. The authors introduce session nodes, which act as ordinary relays in the normal case of MANETs, where an end-to-end path exist. If a disconnection happens, MANETs would usually fail. However, session nodes are used then as message ferries, to deliver data between network's partitions on top of the Store-Carry-Forward (SCF) paradigm. Similarly, Raffelsberger and Hellwagner [81] assume that in emergency situations the established MANETs might suffer link breaks, leading to partition the network. Hence, they aim for the delivery of audiovisual content at switching between MANET and DTN.

In all of the works in DTNs and OppNets, streaming applications can not be supported due to the coarse conditions. Instead, data forwarding schemes are introduced, where delivery delays are unpredictable compared to the streaming counterparts. For instance, in an OppNet with indirect end-to-end delivery between individual nodes instead of network partitions, Chen et al. [82, 83] and Wu and Ma [84] discuss video data delivery over disconnections and intermittent contacts. Besides, similar to the shift of MANET to mesh networks in [76, 77], Yoon et al. [85], Yoon and Kim [86] also modify the standard definition of an OppNet for their streaming protocol. They propose the MOVi protocol for on-demand video streaming in a mobile OppNets, which

<footnote n="1">¹ The solving approaches of all the listed works are discussed in details next in Section 3.1.2</footnote>
is built on a Peer-to-peer (P2P) network with distributed Access Points and a central scheduler. Mobile peers always address their video requests to the central server, and a list of potential mobile providers is returned.

**CONCLUSION** The majority of the works in the MANET domain are neither comparable nor directly derivable in the case of very sparse networks with missing end-to-end paths and high disruptions. To the best of our knowledge, beside the deviated definition by Yoon et al. [85], the only video schemes in a correctly defined OppNet are the two by Chen et al. [82, 83] and Wu and Ma [84], in addition to the scheme under DTN by Cabrero et al. [80] and Raffelsberger and Hellwagner [81]. A classification of the reviewed schemes according to the network type, is given in Figure 3.1.

<figure><img src="image_20.png" /><figcaption>Figure 3.1: Classified Related Works: Network Types</figcaption></figure>

### 3.1.2 Solving Approach

This subsection addresses the corresponding works (that are summarized later in Table 3.1) from the perspective of the proposed solving approach.

#### 3.1.2.1 Coding Techniques

The most common approach for video delivery in multihop networks is to leverage the coding theory, under one of its types; network, channel or video (aka source) coding. The basic idea behind network and channel coding is to combine the original data parts into another form of packet including redundancy, to enhance throughput or help in loss recovery. Source coding, on the other hand, aims basically at data compression as introduced in Section 2.3.

**NETWORK CODING** It is applied in [72, 76, 77], where different network packets are combined together to enhance the communication efficiency. Yu et al. [72] use network coding to encode multicast packets of on-demand videos before being delivered. Seferoglu and Markopoulou [76, 77] enable intermediary nodes to combine
streams from multiple sources using XOR-based network codes, in order to form a
single output with an increased amount of information per transmission.

**CHANNEL CODING** aka Forward Error Correction (FEC). It helps to detect and possibly recover errors and losses. Schierl et al. [73, 74, 75] combine both channel and video coding techniques to present a multi-source streaming approach, that overcomes video failures caused by route losses. The video, which resides at different sources (acting as servers) at the same time, is divided into layers using Scalable Video Coding (SVC). Then a FEC technique is applied to generate different correction codes per source node and SVC layer. These independent representations of the same video are routed then on demand, over different paths through the moving intermediary nodes to the requesting (or subscribed) destination(s). The different sources do not use for this any central coordinator or direct connection between each other. To decode a layer, a destination needs a subset of the originally generated codes of that layer. Chen et al. [82, 83] assume that a video is completely available at one source. Then, similarly to before, it is divided using channel and video coding into quality layers and coded blocks. Using a controlled flooding routing with a prefixed coding replication factor, the authors ensure a fixed amount of overhead. Again using SVC, Qin and Zimmermann [78] encode videos into two layers, and predict link-breaks based on a mathematical model in relation with movement patterns and directions. Using these predictions, and by monitoring the receiver's buffer, transmission bit-rate is adaptively reduced and streaming can be limited to the (so-considered) more important parts.

As seen in Section 2.3.1, Multiple Description Coding (MDC) is another used multi-stream video coding. To overcome frequent loss because of the multihop data delivery in MANETs, Mao et al. [79] propose multistream video coding with path diversity. A number of paths is established between the source and the destination, and each path is evaluated with Quality-of-Service (QoS) parameters like delay and loss probabilities. Videos are coded into multisystems using both layered coding and MDC. The layered coding's unequally important base- and enhancement layers are sent on different paths. Combined with a feedback channel and a retransmission-request technique, the Base Layer (BL) can be retransmitted on a path that was originally used to transmit a less important enhancement layer. On the other hand, MDC depends on prediction from previously coded frames, with no need for feedback. Raffelsberger and Hellwagner [81] manually encode videos at different specifications in order to achieve multistream videos. They divide the content into temporal segments with short durations. Furthermore, each segment is separately encoded into different representations at a variety of bitrates. Segments are prioritized based on time and representation, and a transmission order is prepared in accordance.
However, the main drawback of the coding techniques is that the source node has to
spend more time distributing the code blocks to a larger set of relays. Furthermore, when channel coding is combined with video coding, changes in the video encoder body are needed.

### 3.1.2.2 Other Techniques

Beside coding techniques, Wu and Ma [84] aim at an improved video delivery quality using a buffer management strategy, based on video properties. Video frames are split bit-wise into several messages prior to transmission. Messages are differentiated according to the type of frame, to which they belong in their GoP, that is I-, B- or P-frame message. This property is utilized to trade-off messages when deciding on which should be kept in the buffer. Another bit-wise fragmentation is applied by Yoon et al. [85] based on their P2P scheme. Before distribution, video content is fragmented like in Bittorrent into segments with identical sizes and in a certain order. And upon reception, missing parts are complemented by the central server in order to meet the strict delay constraints.

**CONCLUSION** Data partitioning is implicitly expressed in network and channel coding, since data composition is applied on network packets. However, both network and channel coding suffer from prolonged delays, content encapsulation and obligations of video encoder changes. On the other hand, video coding techniques help not only to overcome the bad QoS conditions, but also provide a new perspective to enhance the Quality-of-Experience (QoE) through the adaptivity and scalability options. A classification of the reviewed schemes according to the solution key, is given in Figure 3.2.

<figure><img src="image_21.png" /><figcaption>Figure 3.2: Classified Related Works: Solution Method</figcaption></figure>

### 3.1.3 Evaluation Metric

It is obvious for the quality to be the dominant metric in evaluating video communication schemes. In all the works of [76, 77, 73, 74, 75, 79, 82, 83, 84], Peak Signal-to-Noise Ratio (PSNR) is used as the quality metric. Differently, Yu et al. [72] measure video playback quality by the number of successfully decoded video packets compared to their total number.
Beside quality, the delivery or loss ratios are also common metrics, since they directly affect the quality level. Loss is measured in [76, 77, 79], and delivery in [78, 80, 81]. However, this can be implemented in a different way in the context of videos. An example is the concept of playout availability by Schierl et al. [73], which considers the cases where delivery is enough to play any degraded version of the video. Despite the importance of the delivery delay metric, it is rarely evaluated in streaming application, because it is considered as a knockout factor, that is either met or not. However, Raffelsberger and Hellwagner [81] and Yu et al. [72] measure the delay as it is, whereas Cabrero et al. [80] and Chen et al. [82, 83] take it as a function for the increasing delivery ratio and quality level respectively. A special case of the delay can be derived out of this, namely the playout delay, which accepts different reception instances at different qualities and delays. Playout delay is also used by Schierl et al. [75] and Chen et al. [82].

Otherwise, other specific evaluation metrics are introduced like the throughput and power consumption [76, 77, 85]. However, these are important metrics, and have their own research domains outside the video context.

### CONCLUSION
The majority of the works consider the received video quality as the main evaluation metric. Many works also use the delivery and loss ratios as well. Furthermore, although streaming applications in MANET require strict delay constraints, and thus consider delay as a knockout factor, in more constrained multihop networks network, the varying delay value is an important metric. Besides, few video schemes concentrate on other specific metrics like the throughput (network utilization) and energy consumption. A classification of the reviewed schemes according to the evaluation metrics, is given in Figure 3.3.

<figure><img src="image_22.png" /><figcaption>Figure 3.3: Classified Related Works: Evaluation Metrics</figcaption></figure>

### 3.1.4 Summary

Summaries of all video communication schemes are given, along their characteristics in Table 3.1, and simulation setup in Table 3.2.
<table><caption>Table 3.1: Literature Summary</caption><thead><tr><td>Work Ref.</td><td>Network</td><td>Com. Model</td><td>Solution Key</td><td>Routing</td><td>Evaluation Metric</td></tr></thead><tbody><tr><td>Yu et al. [72]</td><td>MANET</td><td>Multicast</td><td>Network coding</td><td>On-demand tree-based multicasting</td><td>Multicast video playback quality, Playout delay</td></tr><tr><td>Seferoglu and Markopoulou [76, 77]</td><td>Mesh Network with Internet APIs</td><td>Multi-source streaming</td><td>Network coding</td><td>1-hop direct delivery</td><td>Quality (PSNR) to loss, Throughput to loss</td></tr><tr><td>Schierl et al. [73, 74, 75]</td><td>MANET</td><td>Multi-source streaming</td><td>SVC + Raptor-codes FEC</td><td>Reactive on demand</td><td>Playout availability, Quality, Startup delay (in [75]) (PSNR)</td></tr><tr><td>Qin and Zimmermann [78]</td><td>MANET</td><td>Unicast streaming</td><td>SVC</td><td>Flooding with link breaks prediction</td><td>Delivery ratio</td></tr><tr><td>Mao et al. [79]</td><td>MANET</td><td>Unicast streaming</td><td>Layered coding, Multiple Description Coding</td><td>On demand source-based routing, over multiple paths</td><td>Quality (PSNR), Loss ratio</td></tr><tr><td>Cabrero et al. [80]</td><td>Sparse MANET (DTN)</td><td>Unicast streaming</td><td>Overlay DTN using Store-Carry-Forward</td><td>Optimized Link State Routing</td><td>Delivery ratio over Time</td></tr><tr><td>Raffelsberger and Hellwagner [81]</td><td>DTN</td><td>Unicast forward</td><td>Temporal segments + MPEG-2 different representations</td><td>Epidemic, PRoPHET and SnW</td><td>Video delivery ratio and delay of two quality levels</td></tr><tr><td>Chen et al. [82, 83]</td><td>OppNet</td><td>Unicast forward</td><td>Multiple Description Coding + Layered coding</td><td>Controlled-flooding</td><td>Quality (PSNR) to delay</td></tr><tr><td>Wu and Ma [84]</td><td>OppNet</td><td>Unicast forwarding</td><td>Bit-wise frame split, priority based on GoP frame type</td><td>Epidemic</td><td>Quality (PSNR) to buffer tunning parameters</td></tr><tr><td>Yoon et al. [85]</td><td>OppNet with APIs and a central server</td><td>Peer-to-peer (P2P) streaming</td><td>Bittorrent-like fragmentation</td><td>P2P with central-scheduler</td><td>Playout delay and continuity, Throughput, Power consumption</td></tr></tbody></table>
<table><caption>Table 3.2: Literature Summary, Simulation Setup</caption><thead><tr><th>Work Ref.</th><th>Simulator</th><th>Mobility</th><th>Environment</th><th>Num. of Nodes</th></tr></thead><tbody><tr><td>Yu et al. [72]</td><td>Self implemented</td><td>RWP</td><td>Open area: 1000 × 1000m</td><td>60</td></tr><tr><td>Seferoglu and Markopoulou [76, 77]</td><td>NA</td><td>None</td><td>NA</td><td>NA</td></tr><tr><td>Schierl et al. [73, 74, 75]</td><td>NS-2</td><td>RWP</td><td>Open area: 1000 × 600m</td><td>40</td></tr><tr><td>Qin and Zimmermann [78]</td><td>NS-2</td><td>RWP, RW</td><td>NA</td><td>NA</td></tr><tr><td>Mao et al. [79]</td><td>OPNET</td><td>RWP</td><td>Open area: 600 × 600m</td><td>16</td></tr><tr><td>Cabrero et al. [80]</td><td>Emulator (compatible with NS-2)</td><td>RWP</td><td>Open area: 1000 × 600m → 3000 × 1000m</td><td>2–20 → 30–50</td></tr><tr><td>Raffelsberger and Hellwagner [81]</td><td>ONE</td><td>Real Mobility-Driven: Disaster area</td><td>Real map-based: 400 × 300m</td><td>25</td></tr><tr><td>Chen et al. [82, 83]</td><td>DTNSim</td><td>Real-world traces</td><td>NA</td><td>273, 5148</td></tr><tr><td>Wu and Ma [84]</td><td>NS-2</td><td>RWP, Real-world traces</td><td>Open area: 1000 × 1000m, Traces-based area: 10 × 10km</td><td>60, 92</td></tr><tr><td>Yoon et al. [85]</td><td>NS-2</td><td>Real-world traces</td><td>Traces-based area: 1000 × 1000m</td><td>500</td></tr></tbody></table>
## 3.2 GRANULATION AND CORRESPONDING ROUTING

This section discusses related works with regard to the first research problem, as defined in Chapter 1:

(P<sub>1</sub>) How to granulate a video and route the resulting chunks, to improve the viewing QoE and resist partial losses?

### 3.2.1 Granulation and Data Partitioning

It has been seen in Section 3.1 that when dealing with large volumes of data in multihop networks, granulation exists as a part of the solution in the majority of the works. This manifests itself in one or a combination of the following forms:

1. File-level partitioning

2. Network coding

3. Channel coding

4. Video coding

This step is fundamental to prevent limited contacts times, which are the common case in *OppNet*, from frustrating large data delivery [87, 88].

**FILE-LEVEL PARTITIONING** This is interpreted as dividing the data into parts<fnref n="2" /> at the physical file level. Pitkanen et al. [88] study how to partition the data payload, where some fixed information of the original header (e.g. source, destination) have to be copied as it is into each of the parts, and other headers (e.g. size, partitioning offset and routing information) have to be updated accordingly to enable routing and recovering the original data. Recovery can succeed only if all the composing parts are received.

In the context of videos, Wu and Ma [84] divide each video frame into several parts, and differentiate between them according to their originating frame. They rely on the dependency between I-, B- and P-frames within a GoP to prioritize data parts. Yoon et al. [85] build a bittorrent-like P2P sharing protocol, and assume hence that data is divided into segments, as this kind of protocols require. For a different purpose, Renuka and Thangaraj [89] and Vinod and Madhusudan [90] divide data into smaller parts to enhance transmission confidentiality. Each part is encrypted separately, and then using multipath routing, an attacker has a lower probability to reconstruct the original data.

Despite simplicity, this kind of partitioning may suffer bad worst-case delays if one

<footnote n="2">² Can also be named chunks, fragments, granules or partitions.</footnote>
(or more) of the composing parts arrive late. Furthermore, without further protection
(e.g. redundancy), any loss can cause a delivery failure.

**NETWORK/CHANNEL CODING** The basic idea behind network and channel coding is to take the original data parts, combine them into another form of packets that are called code blocks, and include extra blocks to help in loss recovery. At the receiver side, only a subset of the total blocks is needed in order to reconstruct the original data. Network coding is used by Wang et al. [91] and Tsapeli and Tsaoussidis [92] to further enhance routing in OppNets. Moreover, as seen in Section 3.1, network coding is also used for multicasting [72, 76, 77] and channel coding for streaming [73, 74, 75] in MANETs.

The main drawback of these techniques is that the source node has to spend more
time generating and distributing the code blocks to a larger set of relays. Furthermore,
when channel coding is combined with video coding, changes in the video encoder
body are needed.

**VIDEO CODING** An overview of video coding is already given in Section 2.3, and its common usage in Section 3.1. The scalable granularity implemented in this approach can also be combined with channel or erasure coding to support more error resilience [73, 74, 75].

3.2.2 Routing of The Data Parts

Based on the selection of Scalable Video Coding (SVC) as given in Section 2.3.2, we
have to consider that the resulting data parts are unequally important due to their
dependency. Consequently, the communication scheme to transmit these parts must
respect the different importance levels, in order to meet the viewing experience re-
quirements. This philosophy of inequality can be applied in two forms: prior to rout-
ing, and on routing.

PRIOR TO ROUTING Techniques of this type apply unequal error protection func-
tions, based on network or channel coding. Different parts are protected differ-
ently by tuning the redundancy variable of the coding algorithm, according to
their importance [93, 94, 73].

ON ROUTING Techniques that function on routing can also be classified into two
types:

*   **Drop-based**: An intelligent selection/drop procedure is performed at in-
intermediary nodes along the path, to best enhance the quality gain [76] or
manage the buffer occupation [32, 84].
* Path diversity: When the sender has a diversity of paths, they can be evaluated according to some parameters, and the best or more stable path is assigned for the important data [79]. Another possibility to compare paths, is to send the important data redundant on more than one path [95].

### 3.2.3 Conclusion

This section discussed the popularity of data partitioning approaches for large data delivery in multihop networks. A summary of the corresponding works is given in Table 3.3.

<table><caption>Table 3.3: Granularity Techniques</caption><thead><tr><td>Technique</td><td>Used in</td><td>Pros</td><td>Cons</td></tr></thead><tbody><tr><td>File-level</td><td>[84, 85, 89, 90]</td><td>Simplicity, Parts can take any size</td><td>Bad worst-case delay, High loss probability</td></tr><tr><td>Network/Channel Coding</td><td>[91, 92, 72, 76, 77, 73, 74, 75]</td><td>Error resilience, Loss tolerance</td><td>Prolonged delay, Changes in the video encoder</td></tr><tr><td>Video Coding</td><td>[73, 74, 75, 78, 79, 82, 83]</td><td>Scalability, Content-based representation of sub parts, Loss tolerance</td><td>Configuration complexity</td></tr></tbody></table>

Then, based on the arguments in Section 2.3.2 for choosing SVC, the applied routing protocol has to respect the fact the resulting data parts are not similarly important. Hence, unequal routing protocols are presented.

Our contribution in this context, and our positioning with regard to the presented works, are discussed later in Chapter 4.

* * *

## 3.3 ADAPTIVE SIZE TUNING OF THE VIDEO CHUNKS

This section discusses related works with regard to the second research problem, as defined in Chapter 1:

(P2) *How to adaptively tune the size of the data chunks, with respect to OppNet's changing conditions?*

Adaptivity corresponds to the ability of nodes to react to their changing conditions in an OppNet: density, mobility pattern and network connectivity status. According to Moreira and Mendes [96], these critical condition changes can be basically captured by three parameters:
* Contact time: represents how long a contact between two nodes lasts.

* Inter-contact time: is the duration between two successive contacts

* Contact volume: reflects the quality of the contact that allows to transfer a set of information.

The density of the network, and how the nodes move, directly affect the contact and inter-contact times. How the nodes react then, belongs to one of two forms at two levels of the routing protocol: adapt the message(s) to be sent, or adapt the routing decision (to send or not, and to whom to send).

### 3.3.1 Message Adaptation

This form of adaptation answers the question: what to send? It consists most commonly in reducing the data rate according to the connectivity status. By using network or channel coding, the replication factor to generate the coding blocks can be adapted according to how good the connectivity is, in order to enhance delivery or reduce overhead [97, 75, 74].

Another way of adapting what to send, is how Tournoux et al. [98] optimize the number of copies omitted by Spray-and-Wait routing protocol to enhance delivery under delay constraints and keep the overhead as low as possible. They used in this context the node degree parameter, which was defined by them as the average number of contacts that a node encounters in a given period of time.

### 3.3.2 Routing Adaptation

A wider space of adaptation possibilities, is to adapt how routing protocols function, which answers the two questions: If and How to send? One of the first examples in this context are the PRoPHET [33] and MaxProp [99] routing protocols. Based on the contact history, MaxProp prioritizes the messages to be sent or dropped, whereas PRoPHET forwards a message only to those nodes that have a higher delivery probability.

Similarly, Hu and Hsieh [100] provide each node with a limited list to record the history inter-contact times. This list helps to measure the current local density and estimate the future one. Consequently, nodes can take density-aware decisions to forward messages only to encountered nodes that are moving toward a dense area.

Wang et al. [32] modify the epidemic routing protocol to make message forwarding when encountering a node subject to variable weighting and probabilistic functions. The forwarding probability function is evaluated through the message's level of pervasiveness among neighbor nodes, which is defined as "the proportion of nodes encountered that have the specific message over a predefine time period [32]". Moreover,
which messages to be forwarded is determined by the messages' weights, pervasiveness as well as an inter-contact time measure.

The routing decision is not limited to whether to send a message or not, but can also serve to choose routing protocol itself. For instance Lakkakorpi et al. [101] enable the sending node to adaptively switch the routing protocol between MANET-based and DTN-based<fnref n="3" />. This decision is taken depending on a set of parameters: node density, which inferred from tracked contact pattern, and velocity and file size, which both can be directly read as local information.

Miao et al. [102] rely on two parameters to estimate the delay and cost of data delivery: centrality and regularity, and hence switch between two corresponding routing algorithms in accordance. The former parameter is the node's relative importance to other nodes (measured by the number of times that node was on the path of a message that was delivered to them), and the latter is the likelihood for two nodes to come into contact based on their encounter history.

### 3.3.3 Conclusion

A summary of all mentioned works is given in Table 3.4.

<table><caption>Table 3.4: Related Works Summary: Adaptivity</caption><thead><tr><th>Adaptation</th><th>Work Ref.</th><th>Measurement</th><th>Reaction</th></tr></thead><tbody><tr><td rowspan="2">Message</td><td>[97, 75, 74]</td><td>Connectivity status</td><td>Change messages' redundancy factor</td></tr><tr><td>[98]</td><td>Average number of contacts</td><td>Optimize SnW's number of copies</td></tr><tr><td rowspan="7">Routing decision</td><td>[33]</td><td>Contact (encounter) history</td><td>Forward or not</td></tr><tr><td>[99]</td><td>Contact (encounter) history</td><td>Prioritize messages</td></tr><tr><td>[100]</td><td>Inter-contact time</td><td>Forward or not</td></tr><tr><td>[32]</td><td>Message pervasiveness &amp; Inter-contact time</td><td>Forward or not</td></tr><tr><td>[101]</td><td>Number of contacts &amp; Nodes' velocity</td><td>Switch routing protocol</td></tr><tr><td>[102]</td><td>Contact (encounter) history</td><td>Switch routing protocol</td></tr></tbody></table>

<footnote n="3">³ Differences are presented in Section 2.1.1</footnote>
3.4 LOSS RECOVERY

This section discusses related works from the perspective of the third research problem, as defined in Chapter 1 :

(P₃) *How to design a loss concealment mechanism at the destination node, to enable reacting to small amounts of loss?*

There are different terms that refer to overcoming loss, namely *resilience, concealment* and *recovery*. These terms are differentiated depending on how missing data are compensated.

RESILIENCE reconstructs lost (or faulty) packets using redundant codes that are ex-
tracted from the original data and added by the transmitter [103]. This is similar
to how network and channel coding work, as presented in Section 3.2.

CONCEALMENT tries to reconstruct lost data using the already received parts of the original data [103]. For example, a missing video frame can be reconstructed using the adjacent frames if they were received.

RECOVERY is a general term, which includes the last two ones. Moreover, it proposes
to implement other generic techniques like packet-retransmission [104].

In the context of this dissertation, loss recovery is approached through two perspec-
tives: video frame loss concealment, and network packet loss recovery.

3.4.1 *Video Frame Loss Concealment*

Videos are characterized by high dependency among the underlying components, e.g. consecutive frames, or blocks within the same frame. This property helps to overcome an amount of loss, using the successfully received parts. However, there is no direct contribution in this work to this kind of concealment. Therefore, we will only give a quick review of existing techniques and corresponding surveys, in order to enlighten our selection of applied techniques.

Concerns of video loss concealment in SVC go back to its predecessor H.264/Advanced Video Coding (AVC) [105]. Although the new capabilities and characteristics of SVC increase the encoding complexity, SVC still has a plenty of concealment techniques, most of which are inherited from the error concealment literature of the AVC. Guo et al. [103] describe the transition from AVC to SVC, and outline the key differences between the concealment techniques of each of the coding techniques. Based on the layered structure of SVC, they classify the techniques into Intra-layer, where the con- concealment information are taken from the same scalability layer, and Inter-layer, where the concealment information is exchanged among layers. The SVC Joint Scalable Video
Model (JSVM)<fnref n="4" /> reference software implementation includes four built-in basic tech-
niques:

1. Frame Copy: the last received reference frame is entirely copied into the location of the missing frame.

2. Temporal Direct: only the motion vectors of the last reference frame are copied, and then scaled to fit the place of loss.

3. BLSkip: upsamples the motion vector and residual information from the (correctly received) BL to fit the lost spatial layer.

4. Reconstruction BL Upsampling: decodes the BL directly and upsamples the tex-
tural elements.

Where the techniques (1-2) function in an intra-layer manner, and (3-4) in an inter-
layer one. Two surveys and extended evaluations of the above mentioned conceal-
ment techniques are given in [106, 107].

3.4.2 Network Packet Loss Recovery

To the best of our knowledge, loss recovery in *OppNets* is mainly addressed through
the resilience perspective, which usually follows network and channel coding algo-
rithms [91, 92]. The basic idea, as seen in Section 3.2, is to include extra code blocks to
the original data body, and these will be transmitted through a big number of relays
[108], usually bigger than the required number of relays for ordinary replication-
based routing protocols. At the receiver side, only a subset of the blocks is needed in
order to reconstruct the original data. The main drawback of these techniques is that
the source node has to spend more time distributing the code blocks to a larger set
of relays, and consequently a prolonged delay is observed. Multisourcing was sug-
gested as a solution to overcome this problem [109], where code blocks are initiated
by more than one source node. Nevertheless, the multisourcing technique is tightly
dependent on the coordination possibility between the sources for the generation of
data and their code blocks, and such a coordination is not always possible according
to the network settings.

Network and channel coding are also specifically applied for SVC applications, using Raptor erasure coding [73, 110] or Reed-Solomon coding [111]. In addition to the above mentioned drawbacks, using these coding techniques for SVC requires changes in the encoder and/or byte-wise partitioning to build the code blocks, which contradicts the advantages of Network Abstraction Layer (NAL) units partitioning.

<footnote n="4">4 Version: 9.19.14 - Last update: 14.06.2011</footnote>
### 3.4.3 Conclusion

A summary of all mentioned works is given in Table 3.5.

<table><caption>Table 3.5: Related Works Summary: Loss Recovery</caption><thead><tr><th>Technique</th><th>Work Ref.</th><th>Pros</th><th>Cons</th></tr></thead><tbody><tr><td>Video loss concealment</td><td>[105, 103, 106, 107]</td><td>Rely on existing data</td><td>High impact on quality, Advanced techniques are concerned with high computation complexity</td></tr><tr><td rowspan="2">Recovery</td><td>General com. schemes</td><td>[91, 92, 108, 109]</td><td>Reliability, Computationally simple</td><td>Prolonged delay OR Coordination necessity</td></tr><tr><td>Video com. schemes</td><td>[73, 110, 111]</td><td>Reliability, Computationally simple</td><td>Encoder changes</td></tr></tbody></table>

* * *
# Part II

## CONTRIBUTION

* Chapter 4: Toward Video Delivery With a Better Viewing Experience Using SVC: An Experimental Study.

* Chapter 5: Adapting Granularity for A Better Contact-Opportunity Exploitation.

* Chapter 6: The Integration of BALCON: A Backward Loss Concealment Mechanism.

*Delay is preferable to error.*

— Thomas Jefferson
<figure><img src="image_23.png" /></figure>
# TOWARD VIDEO DELIVERY WITH A BETTER VIEWING EXPERIENCE USING SVC: AN EXPERIMENTAL STUDY

## 4.1 OVERVIEW

This chapter addresses the first research problem, which focuses on video granulation to shift the transmission units from entire videos to smaller parts. It also addresses the viewing-experience measurement, which is defined then as a compromise between Quality-of-Service (QoS) and Quality-of-Experience (QoE). Consequently, the communication scheme will aim at optimizing the delivery results considering delivery delay, overhead and video quality.

Toward these objectives, this chapter proposes an experimental study that covers the selection of the granulation mechanism and the routing of the resulting data parts. The configuration parameters for both video encoding and network simulation are studied, and experimental results are derived and discussed.

## 4.2 OBJECTIVES AND CONTRIBUTIONS

This section highlights the objectives and contributions of this chapter. First, the need for granulation and the importance of choosing Scalable Video Coding (SVC) is addressed. Then, we define the notion of viewing experience and how it is measured in our context benefiting from the characteristics of SVC. Lastly, with respect to this definition, a prioritized redundancy-based routing is formulated.

### 4.2.1 Recall: Granulation and Data Partitioning

In Chapter 2, Opportunistic Networks (OppNets) were presented as human-centric mobile ad-hoc networks, with no constraints on mobility, stable connectivity nor topology changes. Nodes' free mobility widens the network topology, and provides
indirect end-to-end data delivery on top of the Store-Carry-Forward (SCF) paradigm. However, that limits data links to be operational only during opportunistic contacts, which might not last for long durations. Consequently, typical applications in this context usually consider only small messages, which can easily fit with the short contact times, as for instance disaster alarms and traffic notifications.

To enable applications of large data volumes, granulation emerges as a necessary step to break large messages into smaller sub-messages, which can exploit short opportunistic contacts. At the receiver side, recovery of original data succeeds only if all sub-messages are successfully received. This reflects a high sensitivity toward loss, so that any partial loss can cause a high delivery delay or a whole failure. A temporary loss until the late arriving one or more sub-messages causes a high delivery delay, that is associated with the last arriving sub-message. If loss turns permanent, with regard to a time constraint, then delivery is failed. Delivery is usually enhanced by applying different forms of redundancy to avoid partial losses. However, redundancy is associated with extra overhead in the network, which actually identifies the problem as a trade-off between the QoS parameters of delay, overhead and delivery probability.

Unlike generic content delivery, videos can alleviate the sensitivity to loss by tolerating an amount of loss at the cost of a lower quality. In this context, SVC does not only comprise the core idea of granulation by dividing the video main stream into smaller sub-streams, but it also introduces the advantages of quality scalability. As described in Section 2.3.2, SVC encodes a video into one Base Layer (BL) and several Enhancement Layers (ELs). The first layer represents the video at its lowest quality specifications, and each further layer then enhances the quality in one of the scalability dimensions. This property is exploited below to formulate an evaluation metric of the viewing experience.

### 4.2.2 Viewing Experience

As outlined before, the QoS covers technical network performance indicators, whereas the QoE goes further in video applications and measures the satisfaction of end users with the perceived video quality [63, 64].

Thanks to using SVC, quality is divided into levels, and can be regarded as a further trade-off dimension in addition to delay, overhead and delivery probability. This allows to extend the QoS model to represent QoE as well. The quality level is tightly dependent on the delivery ratio on a multi-level scale. That is, independent delivery ratio measurements must be taken for each corresponding quality level. Consequently, in video applications, the metric of quality level can substitute its delivery ratio counterpart, and hence both will be interpreted as a single parameter. An overview of the trade-off parameters for generic and video data delivery is depicted in Figure 4.1.
<figure><img src="image_24.png" /><figcaption>Figure 4.1: Trade-off Dimensions for Generic and Video Data Delivery</figcaption></figure>

The objective of the communication scheme in our work is therefore to optimize results in the depicted 3D space, with respect to the parameters: quality, delay and overhead.

**WHERE IS THE OPTIMAL POINT IN THIS SPACE?** Both delay and overhead reflect a bad performance when their values increase. Hence, their optimal values are at zero. The quality is contrarily better with higher values. Therefore, to subject a direct proportion between the three parameters, the optimal point in the trade-off space can be moved to the (0,0,0) center by inverting the quality metric as shown in Figure 4.2.

<figure><img src="image_25.png" /><figcaption>Figure 4.2: Magnitude</figcaption></figure>

An experiment of sending a video under specific settings is concluded by the means of three measurement values: quality, delay and overhead. Observing these measurements as three features in a 3D feature space allows us to represent the experiment by a feature vector that is given by a point p in the 3D space in Figure 4.2. Consequently, the given experiment can be assigned a single value by simply using the Euclidean distance (magnitude) of its feature vector, which is calculated as the following:

$$val(p) = |\vec{0p}| = \sqrt{w_1.q^2 + w_2.t^2 + w_3.o^2} \quad (4.1)$$

where
q : Projection of p on the inversed quality axis

t : Projection of p on the delay axis

o : Projection of p on the overhead axis

w₁,₂,₃ : Weights of the corresponding parameters

**NORMALIZATION** However, since the values of the three features belong to different data ranges, the calculated Euclidean distance will be dominated by the feature of the broadest data range. Therefore, each feature value has to be independently normalized to the [0, 1] range. This is done using the technique of linear scaling to unit range [112], which is calculated for a given feature value (measurement) as the following:

$$ \tilde{x} = \frac{x - l}{u - l} \qquad (4.2) $$

where

x̃ : The normalized value of x, where $\tilde{x} \in [0, 1]$

l : The lower bound of the corresponding feature's data range.

u : The upper bound of the corresponding feature's data range.

By applying this normalization to all the q, t and o components of Equation 4.1, the given formula will enable comparing different experiments using their corresponding projected points in the trade-off space. A smaller Euclidean distance refers to a better experiment, because the feature vector will be closer to the (0,0,0) center, where the optimal point lies.

**WEIGHTING** The weighting factors are assigned depending on the target application, if any of parameters is more critical than the others. For example, in video telephony, the delay is very critical to ensure real-time conversations, then $w_2$ gets a higher value than $w_1$ and $w_3$ to express this. On the other hand, in movies streaming, some users are interested in a very good quality, then $w_1$ must get a higher value. However, when not comparing experiments from different applications the weighting can be ignored by assigning $w_1 = w_2 = w_3 = 1$.

**THE INFLUENCE OF MULTI-LEVEL QUALITY** In the multi-level quality context of SVC, we follow the argumentation by Schierl et al. [75] and Chen et al. [82], which states that a lower playout delay at the cost of a lower quality would ensure a better viewing experience. Therefore, in our further experiments, we propose to extend the single result point in Figure 4.2 to two points that can represent the result of an experiment:
p₁: represents the result associated with the lower playout delay at the SVC's BL quality.

p₂: represents the result associated with the maximum delivered layer. At the worst case, if no further ELs beyond the BL could be delivered, p₂ would be identical to p₁.

An example of two result points in a 2D space of inverted quality and delay (referred to the axes as Q and T respectively) is depicted in Figure 4.3.

<figure><img src="image_26.png" /><figcaption>Figure 4.3: Two Result Points</figcaption></figure>

To represent an experiment with a single value that takes both p₁ and p₂ into consideration, an average feature vector between p₁ and p₂ is calculated. Consequently, the viewing experience is implicitly represented by the means of the playout delay (taken from p₁), the maximum delivered level of quality (taken from p₂) and the overhead (homogeneously calculated for the experiment).

### 4.2.3 Prioritized Routing

SVC output layers, L₀, ..., Lₙ, refer to different importance degrees because of two reasons, one is related to the technical characteristics of SVC and the other one is derived from our viewing experience requirements.

FIRST, the layers of a scalable bit stream form a hierarchical dependency [54, 113]. That is, a given layer is not decodable unless all of the lower layers, on which it depends, are already successfully received. Consequently, given n scalable layers, the base layer L₀ is essential for all upper layer, and hence the most important layer. On the other hand, the last layer Lₙ-₁ is the least important one.

SECOND, based on the interest of delivering a degraded version of the video with the shortest possible delay for a better viewing experience, more importance must also be assigned to lower layers, which represent a video at its lower specifications. Consequently, same as before, the base layer L₀ is associated with the highest priority.
This prioritizing affects the selection and configuration of the routing protocol. As presented in Section 3.2, the choice of a routing protocol that is based on controlled flooding and multi-path redundancy encloses many advantages. First, it allows to simply reflect the priorities of messages by tuning the corresponding redundancy factor up and down. That is, one can send more copies of the more important messages (i.e. layers), and vice versa. Second, it offers a full control over the applied network overhead. The Redundancy factor, or the allowed number of copies, define an upper bound of the overhead. Lastly, when it comes to *OppNets*, where no prior knowledge on the network or the nodes exists, this family of routing techniques (e.g. Spray-and-Wait (*SnW*)) report good experimental results with regard to delivery ratio, delay and limited overhead [114].

Hence, the workflow of our proposal is based on the *SVC* encoding of an input video into a given number (n) of layers, over which m Operating Points (OPs) are defined as described in Section 2.3.2.2. Then, the *BL* is sent first with the highest redundancy factor, followed by the second important *OP* with less redundancy, and so on until $OP_{m-1}$. Upon each contact on the way to destination, messages are copied based on the algorithm of the *SnW* routing protocol, as described in Section 2.1.2. The workflow is summarized in Listing 4.1, and an example run of the proposition is depicted in Figure 4.4.

<figure><img src="image_27.png" /><figcaption>Figure 4.4: An Example Run of Prioritized Layered Routing</figcaption></figure>
Input: raw single-stream video

% Granulating and preparing messages @source
svcVid = JSVM-SVC-encode.video) % where svcVid has n layers: L[0 .. n-1]
Define m < n operating points: OP[0 .. m-1]
For (j = 0 → m-1) {
    OP[j].setRedundancyFactor()
    % where OP[j].redundancyFactor >= OP[j+1].redundancyFactor, because lower
    layers and OPs are more important as already given in Section 4.2.3
}

% Routing of a message msg=OP[j] when the node X meets Y
if (Y.hasMessage(msg) == false) {
    if (X.msg.redundancyFactor > 1) {
        X.send(to=Y, message(msg)
        X.msg.redundancyFactor /= 2
        Y.msg.redundancyFactor /= 2
    }
    else { % when redundancyFactor=1, the message can only be sent to its target
        if (Y == X.msg.target) {
            X.send(to=Y, message(msg)
            X.delete(msg)
        }
    }
}

% Measurements @target
t1: Delay to deliver OP[0] = BL
q1: BL quality level

t2: Delay to reach OP[j];
    where 0 < j ≤ m-1 and all OP[0 .. j-1] are already delivered
q2: Quality level associated with OP[j]

o: Σ(m-1) j=0 OP[j].redundancyFactor x OP[j].size

% Evaluation
p1: The result point that corresponds to the lower playout delay at BL quality (
    t1 and q1)
p2: The result point that corresponds to maximum delivered quality at any delay
    (t2 and q2)

Evaluate the whole experiment with a single value = mean(p1,p2)

<caption>Listing 4.1: Prioritized Layered Routing</caption>
## 4.3 EXPERIMENTAL SETUP

### 4.3.1 Scalable Video Coding

This section describes the choice of parameters that are needed in the SVC encoder for the determination of the scalability dimensions and the corresponding scalability layers and operating points.

#### 4.3.1.1 Video Sequences

Video streams are selected for the experiments from the video trace library [115]. Videos are downloaded in a raw and uncompressed file formats with (.YUV) extension. Basically, four video streams (which are commonly used standard video test sequences can be found) were selected for different experiments in the work. They all possess the same resolution of CIF: 352 × 288, the same frame rate of 30fps, but different number of frames and hence different file sizes.

These sequences are:

* $V_0$: *Bus*, consists of 150 frames

* $V_1$: *Crew*, consists of 600 frames

* $V_2$: *Highway*, consists of 2000 frames

* $V_3$: A repetition of *Highway*, consists of 4000 frames

<figure><img src="image_28.png" /><figcaption>Figure 4.5: Video Sequences</figcaption></figure>

The first sequence (*Bus*) is used only for pre-configuration experiments, whereas the other three sequences are used later for the proposed delivery scheme. Lengths of these sequences range between 20 seconds to about 2 minutes to coincide the given example scenarios in Chapter 1 (e.g. disaster recognition, touristic shooting or demonstration documenting videos), where no longer video samples are required to correspond to those examples.
### 4.3.1.2 Scalability Dimensions

As shown before, SVC supports three dimensions or features of scalability, and a given video can be encoded using SVC with any combination of the three dimensions. To set the scalability dimensions that our encoded sample videos will have, different combinations are experimented and compared with regard to 1) the size distribution among the layers and 2) the output file size. To the best of our knowledge, no other work in the literature has proposed such a study. Thus, we had to perform the experiments ourselves.

For the experiments, *Bus* and *Highway* video sequences were selected, as they are significantly different with regard to length (Bus: 150 frames, Highway: 2000 frames) and in term of dynamicity of the video content (Bus: very changing, Highway: less changing). Each sequence was encoded several times with a single isolated scalability dimension each time, and then all dimensions were combined together for the last experiment. When tested individually, temporal, spatial and SNR scalabilities included three scalability levels for each, to show the distribution of size among the layers. The last experiment combined all the scalability dimensions together, holding three temporal-, two spatial- and two SNR-levels, which results in 12 layers. This configuration is based on the recommendations provided in [59] and [116] for a better performance with regard to encoding time and output size.

Figures 4.6 and 4.7 show for the 2 videos the percentage of size distribution among the three composing layers of the individually tested scalability dimensions, as well as the 12 layers of the combined dimensions.

<figure><img src="image_29.png" /><figcaption>Figure 4.6: File Size Distribution Among Scalability Layers, Video: Bus</figcaption></figure>

It is noticed above in the cases of the individually tested scalability dimensions, that the major part of the total size is concentrated in one layer ($L_0$ for the temporal and Signal-to-Noise Ratio (SNR) scalabilities, and $L_2$ for the spatial scalability). This contradicts the objective of fragmentation because a large sub-part is not different from the original data. On the contrary, combining all scalability options together will have the advantage of spreading the same (or only slightly larger) size over a bigger number of layers (as shown on the right of the figure).
<figure><img src="image_30.png" /><figcaption>Figure 4.7: File Size Distribution Among Scalability Layers, Video: Highway</figcaption></figure>

Furthermore, Figure 4.8 compares the sizes of the output files (taken for both videos), considering the encoded video with temporal scalability only as a reference, because as given in Section 2.3.2.2, any SVC-encoded video (with Group-of-Pictures (GoP)>1) is temporally scalable by default, with no extra volume or encoding complexity.

<figure><img src="image_31.png" /><figcaption>Figure 4.8: SVC File Size Comparison</figcaption></figure>

This shows that encoding a video using the three scalability options yields only about 5-15% more size for the output file.

Therefore, this configuration of combined scalability dimensions will be adopted for all next experiments.

### 4.3.1.3 Scalability Layers

This section details the parameters, which define the number of layers in each scalability dimension.

**TEMPORAL LAYERS** As outlined in Section 2.3.2, the essential parameter to be set is the size of the GoP, which influences the coding efficiency, output file size, output quality, and more importantly the temporal scalability levels. Unanue et al. [59] listed recommended configurations for different scenarios. For a better performance with regard to encoding complexity and storage requirements, smaller GoP values are recommended. Namely, GoP is set to 4, which results in 3 temporal levels.
**SPATIAL LAYERS** The common resolution of video samples is the CIF (352 × 288), which allows only one step down on a 2:1 ratio due to technical limitations of the Joint Scalable Video Model (JSVM) software [2]. Two spatial resolutions is also the common recommendation by Wang et al. [116].

**SNR LAYERS** In relation to the recommendations by Unanue et al. [59] regarding performance oriented scenarios, they also limited the encoding to two SNR levels. The reason is that the SNR scalability is the most computationally expensive variation compared to the temporal and spatial scalabilities, and this complexity increases with more SNR layers [54].

Using these recommendations together will result in 12 scalability layers in total among the three scalability dimensions. This is illustrated in Figure 4.9.

<figure><img src="image_32.png" /><figcaption>Figure 4.9: SVC Layers</figcaption></figure>

#### 4.3.1.4 Operating Points

The path of the OPs from the first till the last layer must be selected with respect to the following criteria:

* The path must have the maximum possible length, as given in Equation 2.2 in Section 2.3.2.

* The path must leave the SNR enhancement to the last step, because it delivers the least significant quality gain [59], and leaves the biggest peak of size to the last enhancement step.

* The path must ensure that each step starting from the first layer (BL) brings the most possible quality-gain (with regard to Peak Signal-to-Noise Ratio (PSNR) metric).

The whole selection process is summarized in Algorithm 4.2.
```
Input:
    layers: array of n layers
    paths: array of all possible OPs paths from layers[0] → layers[n-1]

% Calculate max length according to Equation 2.2
maxLength = distanceManhattan();

% (1) filter out paths that are shorter than maxSize, and paths that enhance
on SNR dimension before the last step.
paths = filter paths, maxSize);

% (2) remove all paths that have very varying sizes, i.e. some OPs are too big,
others are too small.
candidatePaths = paths
for (p in candidatePaths) {
    p.pop(lastStep); % exclude the last SNR step
    sd = stddev(sizes of operating points in p);
    if (sd > size of any operating point in p) {
        candidatePaths.pop(p);
    }
}

% if only one path is remaining after filtering, return it
if (candidatePaths.length == 1) {
    return candidatePaths[0];
}

% if more than one path is remaining, trade-off them
% if no path is remaining, trade-off remained paths after applying the filter
if (candidatePaths.length == 0) {
    candidatePaths = paths;
}

% (3) now trade-off each step from the remaining candidate paths
bestPath = [];
currentLayer = layers[0];
bestPath.push(currentLayer);
while(bestPath.length < maxSize) {
    steps = nextPossibleSteps(from(currentLayer, on=candidatePaths);
    currentLayer = chooseBestLayer(steps)
    bestPath.push(currentLayer);
}
```

<caption>Listing 4.2: The Selection of Operating Points Path</caption>

Where the trade-off between the next possible steps is done by analyzing how much quality-gain (PSNR) would the next step bring, as shown in Algorithm 4.3. The result usually depends on the video content type. That is, if the video content is very dynamic (changes a lot), the temporal enhancement brings more quality gain because it brings new different frames from previous ones. On the other hand, if the video content is stable, the spatial enhancement brings more quality gain.
```matlab
function chooseBestLayer.stepLayers) {
    bestLayer = null;
    for (l in stepLayers) {
        if (videoPsnr(with layer l) > videoPsnr(with layer bestLayer)) {
            bestLayer = l;
        }
    }
    return bestLayer;
}
```

<caption>Listing 4.3: The Selection of Operating Points Path</caption>

Consequently, five OPs are fixed on top of the SVC layers in a way to ensure a quality advancement with each further level and achieve a good distribution of the total size among the maximum possible number of levels. Fixing the least significant SNR scalability to the last enhancement level, leaves 3 possible taxicab paths from $L_0 \to L_{11}$:

$$1. L_0 \to L_6 \to L_7 \to L_8 \to L_{11}$$

$$2. L_0 \to L_1 \to L_7 \to L_8 \to L_{11}$$

$$3. L_0 \to L_1 \to L_2 \to L_8 \to L_{11}$$

The distribution of size among the 5 OPs for the 3 path variations is depicted in Figure 4.10.

<figure><img src="image_33.png" /><figcaption>Figure 4.10: OPs Size Distribution</figcaption></figure>

It is noticed that the 3 paths have the same characteristics, and there is no preferred path with regard to the size distribution. Therefore, based on the steps trade-off, we select the first path ($L_0 \to L_6 \to L_7 \to L_8 \to L_{11}$), which goes in the direction of the spatial resolution first. The spatial resolution is more important for the given example scenarios (e.g. disaster recognition, touristic shooting or demonstration documenting videos) as it critically influences the picture-quality and the needed details inside. The chosen path of OPs is shown in Figure 4.11.
<figure><img src="image_34.png" /><figcaption>Figure 4.11: SVC Operating Points</figcaption></figure>

### 4.3.1.5 Video Encoding & Layers Extraction

Videos are SVC-encoded using the JSVM official reference software implementation [2]. JSVM outputs a file or stream of NAL Units (NALUs), which are combined in subsets to form individual SVC layers [54]. To prepare data for the dissemination scheme, the different layers have to be extracted out of the stream. For this, JSVM provides a bit-stream extractor function that extracts a specific layer. But undesirably, the returned stream does not include the specified layer only, but also all of the dependent successive layers. Hence, in order to extract physically independent layers with no redundancy with each other, a modification to JSVM's implementation of the extraction function has to be applied to ignore dependencies and extract a single layer at once. This change is presented by Chen et al. [117]. Consequently, any layer (shown in Figure 4.9) or subset of layers (OPs shown in Figure 4.11) are extractable as a separate file, which can be individually sent.

By applying the aforementioned SVC configurations on the sample video sequences: $V_0$, $V_1$ and $V_2$, the resulting sizes and PSNR quality values of the given OPs are as listed in Table 4.1.

<table><caption>Table 4.1: Sizes and Quality Values of the Operating Points</caption><thead><tr><th rowspan="2">OP</th><th colspan="3">PSNR (db)</th><th colspan="3">Size (KB)</th></tr><tr><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th></tr></thead><tbody><tr><td>1 (Base)</td><td>25.3</td><td>28.7</td><td>28.7</td><td>86</td><td>118</td><td>236</td></tr><tr><td>2</td><td>26</td><td>30.2</td><td>30.2</td><td>263</td><td>685</td><td>1370</td></tr><tr><td>3</td><td>29</td><td>32.3</td><td>32.3</td><td>44</td><td>110</td><td>220</td></tr><tr><td>4</td><td>33</td><td>34.9</td><td>34.9</td><td>91</td><td>186</td><td>372</td></tr><tr><td>5</td><td>36</td><td>37.3</td><td>37.3</td><td>735</td><td>2321</td><td>4642</td></tr></tbody></table>

The PSNR values are not calculated for SVC in a straight forward way compared to unscalable videos as given in Section 2.3.3. For multistream videos, PSNR has to be calculated for each of the substreams (layers) separately. The problem is that each
substream has a specific value for the $Width_{frame}$, $Height_{frame}$ and $N_{frames}$ pa- rameters, depending on its spatial and temporal resolution. The reference video has the upper bound values for those parameters. A substream of a lower spatial layer will have smaller W and H values, whereas a substream of a lower temporal layer will have a smaller N value. Consequently, lower layers have to be upsampled temporally and/or spatially to match the reference video and hence be applicable in Equation 2.3 [118]. This technique is described in details in Appendix A.2.

### 4.3.2 Simulation Environment

#### 4.3.2.1 Mobility

As presented in Section 2.2.3, to avoid the drawbacks of using real-world traces, we use the Shortest Path Map-Based Movement (SPMBM) model in a map-based area. The map is taken from Helsinki city, which is the default built-in map for the Opportunistic Network Environment (ONE) simulator with predefined streets and POIs. The size of the map is 4300 × 3400 meters including the free space that occupies most of the map as shown in Figure 4.12.

<figure><img src="image_35.png" /><figcaption>Figure 4.12: Helsinki Map</figcaption></figure>

Furthermore, to keep the common comparison reference, we also run our experi- ments using the Random Way-Point (RWP) mobility model in an open area of the size 1000 × 1000 meters.

Besides, the simulation run (and mobility) lasts for 360 minutes. Although it is more realistic to be limited to 180 or 240 minutes, we implement this long run in order to examine the quality impact of the late arriving ELs.

#### 4.3.2.2 Population

As introduced in Section 2.1.1, the density of wireless networks is classified into three levels: dense, medium and sparse, which are visually illustrated in Figure 2.1.

OppNets fall in the third category of sparse networks, where nodes are scattered with
<figure><img src="image_36.png" /><figcaption>Figure 4.13: Density Patterns of Wireless Networks</figcaption></figure>

only a few number of active connections at any instant of time. However, in the simulated experiments in the literature, the used number of nodes varies from 50 to 1000 or more nodes [119, 22]. High populations are criticized by Grasic and Lindgren [21] due to the unrealistic usage of big number of nodes. Consequently, to keep the sparse settings of *OppNets*, we set our population to 50 pedestrian nodes.

### 4.3.2.3 Routing

As presented earlier in Section 4.2.3, the SnW routing protocol (in its both variations: Vanilla and Binary) is chosen because it is considered as a reference routing schema and it can easily implement the intended unequal dissemination.

Furthermore, to keep a baseline and a reference for comparisons, the epidemic and PRoPHET protocols<fnref n="1" /> are also tested. Epidemic, as an uncontrolled flooding protocol, delivers the best results in a given scenario with regard to delay and delivery ratio when the messages buffer is big enough. PRoPHET, on the other hand, is an estimation-based protocol, and hence gives the chance to test another family of routing protocols.

All the SnW, Epidemic and PRoPHET routing protocols are built-in delivered with the ONE simulator, and can be directly used with no extra costs of further implementations. However, the basic implementation of SnW allows to set only one redundancy factor for all the generated messages. Therefore, in order to set different redundancy factors according to the importance degree of each message, the open-source simulator had to be adapted as described in Appendix A.3.2.

### 4.3.2.4 Other Configuration Parameters

The transmission interface is set to Bluetooth with a 250kBps transmission rate, which represents a lower-bound that can be ensured to exist on any mobile device.

<footnote n="1">¹ Section 2.1.2.</footnote>
Messages' Time-to-Live (TTL) is set unlimited (or in other words, limited to the simulation lifetime), because we are interested in examining late arriving messages, and because messages in our scenarios have no validation deadline.

Lastly, the buffer size on each node is set to 100 MB, so that it is big enough to carry all forwarded messages.

### 4.3.2.5 Summary

All experiments are performed on the Opportunistic Network Environment (ONE) simulator [1]. A summary of the configuration parameters is given in Table 4.2.

<table><caption>Table 4.2: Simulation Configuration</caption><thead><tr><th>Parameter</th><th>Value</th><th>Remarks</th></tr></thead><tbody><tr><td rowspan="2">Mobility</td><td>Random Way-Point (RWP)</td><td>Open area: 1000 × 1000m</td></tr><tr><td>Shortest Path Map-Based Movement (SPMBM)</td><td>Helsinki map with predefined streets and POIs</td></tr><tr><td>Run duration</td><td>360 min</td><td>-</td></tr><tr><td>Population</td><td>50 pedestrian nodes</td><td>Ensure a sparse setup</td></tr><tr><td rowspan="3">Routing</td><td>Spray-and-Wait (SnW)</td><td>Vanilla and Binary</td></tr><tr><td>Epidemic</td><td>Baseline for comparisons</td></tr><tr><td>PRoPHET</td><td>Further comparisons</td></tr><tr><td>Transmission interface</td><td>Bluetooth</td><td>Rate: 250kBps, Range: 10m</td></tr><tr><td>TTL</td><td>= Run duration = 360 min</td><td>-</td></tr><tr><td>Buffer</td><td>100 MB</td><td>-</td></tr></tbody></table>

Lastly, to reduce variability, every experiment is repeated in $N_r = 400$ complete simulation runs (rounds), each time with different randomly selected source and destination nodes. $N_r$ is statistically set, so that the standard deviations of the delivery times are not significantly affected by a higher value of $N_r$.

## 4.4 MAP-BASED EXPERIMENTS

This section presents and analyzes the results of the map-based experiments. The selected video sequences are disseminated first as one unlayered part, and then SVC-encoded using the proposed scheme.

### 4.4.1 Delivery Ratio and Delay

Results for the three video sequences are depicted in Figure 4.14. Box-plots that refer to the 25th, 50th and 75th percentiles are used, along with bars referring to the percentage number of rounds where no delivery was reported.
In all Figures, the different routing protocols are represented by different color sets.
The depicted boxes are denoted as follows:

* e1, e2, E: SVC's base layer, highest delivered enhancement layer and the non-SVC video, in respective order, using Epidemic routing

* p1, p2, P: same as before using PRoPHET routing

* s1, s2, S: same as before using vanilla SnW routing

* b1, b2, B: same as before using binary SnW routing

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /><figcaption>Figure 4.14: Map-Based Experiments</figcaption></figure>

The consequence of the proposal can be concluded out of the box-plots for the larger
videos V2 and V3, by comparing the $x_1$ and $x_2$ SVC segments to non-SVC X segment,
where a triplet {$x_1, x_2, X$} corresponds to one routing algorithm (e.g. e1, e2, E). For example, using *binary SnW*, $b_1$ represents the time that the destination node has to wait before it can start watching a video at its lowest quality:

* $\text{Avg}_{v_2}(b1) \approx 70$ min, on Figure 4.14b

* $\text{Avg}_{v_3}(b1) \approx 80$ min, on Figure 4.14c

Video quality keeps getting better until $b_2$, the delivery time of the last successfully delivered enhancement layer.

* $\text{Avg}_{v_2}(b2) \approx 190$ min, on Figure 4.14b

* $\text{Avg}_{v_3}(b2) \approx 210$ min, on Figure 4.14c

On the other hand, B is the delay for delivering the non-SVC version.

* $\text{Avg}_{v_2}(B) \approx 280$ min, on Figure 4.14b

* $\text{Avg}_{v_3}(B) \approx 260$ min, on Figure 4.14c

It is noticed that in general $x_1 \ll X$ and $x_2 < X$. Moreover, the no-delivery ratio, represented below each figure, is much higher for non-SVC transmission.

Comparing the different routing algorithms, we can note that results of *binary SnW* (following our approach) are equal to or slightly less good than the results of *Epidemic*, although the network overhead for the *binary SnW* case is much lower than *Epidemic's* overhead. The PRoPHET protocol, on the other hand, is the worst among others with regard to both delay and delivery. This shows that redundancy-based routing protocols suits better for sparse environments, because PRoPHET needs more contacts in order to enhance its estimation function.

The percentile margins of the box plots around the corresponding averages are noticed to be generally wide referring to dispersed data. This common problem is due to characteristics of *OppNets*, where the delivery probability and delay vary a lot. Increasing the number of simulation rounds does not completely help to overcome this phenomena.

Besides, the playout availability, which reflects the availability of any playable version of the video at any quality, is equal to 100% in both cases (0% no delivery rounds). This is achieved in our scheme with the aid of the focus on delivering the *BL*, which ensures playing the video at the lower quality.

The main advantages of our proposal with regard to the given example scenarios are:

1. Less playout delay: so that an informing video (e.g. about a demonstration or a disaster) can be delivered at a lower quality but with the least possible delay.

2. High playout availability: so that the probability to receive the informing video at least is high.
3. QoE taken into consideration: by the means of video reception on 2 levels (lower quality at lower delay and higher quality at higher delay).

### 4.4.2 Quality Distribution

One drawback when using SVC is that the best successfully delivered quality is not necessarily always the maximum quality that is achieved when delivering all of the enhancement layers. In some simulation rounds, only the base layer could be delivered, so the quality stops at the base level. Other rounds reached the quality level associated with further OPs. For instance, Figure 4.15 presents the quality distribution for the three video sequences when using Epidemic and binary SnW routing algorithms.

<figure><img src="image_40.png" /><figcaption>Figure 4.15: Quality Distribution</figcaption></figure>

The video V3 could reach the maximum quality (the 5th OP) in 55% of the simulation rounds using Epidemic, where 30% stopped at the quality level of the 4th OP and less than 10% at the BL quality. On the other hand, using binary SnW, only 12% of the simulation rounds reached the 5th OP, where over 50% stopped at the quality level of the 4th OP, less than 10% at each of the 3rd and 2nd OPs, and about 18% at the BL quality.

The same analysis above applies for each of the other videos V1 and V2. Consequently, average quality levels are calculated and listed in Table 4.3 with regard to the reached OPs and the corresponding PSNR values.

<table><caption>Table 4.3: Average Quality Levels</caption><thead><tr><th rowspan="2">Metric</th><th colspan="3">Epidemic</th><th colspan="3">Binary SnW</th></tr><tr><th>V1</th><th>V2</th><th>V3</th><th>V1</th><th>V2</th><th>V3</th></tr></thead><tbody><tr><td>OPs</td><td>5</td><td>4.5</td><td>4.2</td><td>4.3</td><td>3.7</td><td>3.4</td></tr><tr><td>PSNR</td><td>36</td><td>36.1</td><td>35.4</td><td>34.2</td><td>34.3</td><td>33.5</td></tr></tbody></table>
### 4.4.3 Viewing QoE

#### 4.4.3.1 Results Normalization

The viewing experience is evaluated using the Equation 4.1 from Section 4.2.2, after the measurement values are normalized using the Equation 4.2.

**QUALITY** The achieved average PSNR values from Table 4.3 are normalized on the basis of the videos' full PSNR values in Table 4.1 as the range upper bound (lower bound = 0). To invert the quality values, so that the optimal value lies at zero (as described in Section 4.2.2), the Equation 4.3 is applied.

$$ \tilde{q} = -1 \times \text{PSNR} + \text{bound}_{\text{upper}} = -1 \times \text{PSNR} + 1 \quad (4.3) $$

Consequently, the values of the normalized PSNR and the normalized inverted quality are given in Table 4.4.

<table><caption>Table 4.4: Normalized Average Quality Levels</caption><thead><tr><th rowspan="2">Metric</th><th colspan="3">Epidemic</th><th colspan="3">Binary SnW</th></tr><tr><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th></tr></thead><tbody><tr><td>PSNR</td><td>1</td><td>0.97</td><td>0.95</td><td>0.95</td><td>0.92</td><td>0.90</td></tr><tr><td>q̃</td><td>0</td><td>0.03</td><td>0.05</td><td>0.05</td><td>0.08</td><td>0.1</td></tr></tbody></table>

**DELAY** The delay values are normalized on the basis of the messages' set TTL as the upper bound. The lower bound is set to 0.

**OVERHEAD** The overhead of an experiment is calculated as the following:

$$ \text{overhead} = \frac{I_{\text{data}}}{D_{\text{data}}} \times \frac{1}{\text{overhead}_e} $$

where,

* $D_{\text{data}}$: The amount of successfully delivered data

* $I_{\text{data}}$: The initiated amount of data, including the redundancy of the "controlled-flooding" routing

* $\text{overhead}_e$: The overhead of the Epidemic routing protocol

Then, all overhead values are normalized on the basis of the overhead of the Epidemic routing protocol, which represents the upper bound of the possible overhead in the network. Similarly, the lower bound is set to 0.
### 4.4.3.2 Calculation Of The Viewing QoE

As proposed, two measurement points ($p_1, p_2$) are taken, referring to 1) the result associated with the lowest playout delay at the lowest quality, and 2) the result associated with the maximum delivered quality at any delay. Consequently, an analytical summary of the viewing QoE values is given in Table 4.5.

<table><caption>Table 4.5: Viewing Experience Evaluation</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="3">Epidemic</th><th colspan="3">Binary SnW</th></tr><tr><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th></tr></thead><tbody><tr><td rowspan="6">p<sub>1</sub></td><td>PSNR</td><td>25.3</td><td>28.7</td><td>28.7</td><td>25.3</td><td>28.7</td><td>28.7</td></tr><tr><td>PSNR</td><td>0.70</td><td>0.77</td><td>0.77</td><td>0.70</td><td>0.77</td><td>0.77</td></tr><tr><td>q̃</td><td>0.3</td><td>0.23</td><td>0.23</td><td>0.3</td><td>0.23</td><td>0.23</td></tr><tr><td>t (min)</td><td>55</td><td>80</td><td>80</td><td>74</td><td>80</td><td>80</td></tr><tr><td>t̃</td><td>0.153</td><td>0.222</td><td>0.222</td><td>0.206</td><td>0.222</td><td>0.222</td></tr><tr><td>õ</td><td>1</td><td>1</td><td>1</td><td>0.15</td><td>0.15</td><td>0.15</td></tr><tr><td colspan="2">val(p<sub>1</sub>)</td><td>1.055</td><td>1.049</td><td>1.049</td><td>0.393</td><td>0.353</td><td>0.353</td></tr><tr><td rowspan="6">p<sub>2</sub></td><td>PSNR</td><td>36</td><td>36.1</td><td>35.4</td><td>34.2</td><td>34.3</td><td>33.5</td></tr><tr><td>PSNR</td><td>1</td><td>0.97</td><td>0.95</td><td>0.95</td><td>0.92</td><td>0.90</td></tr><tr><td>q̃</td><td>0</td><td>0.03</td><td>0.05</td><td>0.05</td><td>0.08</td><td>0.1</td></tr><tr><td>t (min)</td><td>55</td><td>115</td><td>130</td><td>145</td><td>190</td><td>210</td></tr><tr><td>t̃</td><td>0.153</td><td>0.319</td><td>0.361</td><td>0.403</td><td>0.528</td><td>0.583</td></tr><tr><td>õ</td><td>1</td><td>1</td><td>1</td><td>0.15</td><td>0.15</td><td>0.15</td></tr><tr><td colspan="2">val(p<sub>2</sub>)</td><td>1.012</td><td>1.050</td><td>1.064</td><td>0.433</td><td>0.554</td><td>0.611</td></tr><tr><td colspan="2">QoE(p)</td><td>1.033</td><td>1.050</td><td>1.057</td><td>0.413</td><td>0.454</td><td>0.482</td></tr></tbody></table>

As Figure 4.2 shows, the lower the value of the viewing QoE, the better it is. It is noticed using this metric how each of the parameters (quality, delay and overhead) contribute to the QoE. Consequently, using the Binary SnW routing protocol along with our proposal that is summarized in Listing 4.1, the results in Table 4.5 are significantly better than those of Epidemic, although this latter has slightly lower delays and better qualities, but a high overhead.

Beside the metric of the viewing QoE, our approach of using a layered video coding and prioritizing the more important parts enables the scheme to deliver a quality level that is very close to the quality level of Epidemic, which represents the performance upper bound since the message buffer is assumed to be big enough. This is noticed in Table 4.5 for $p_2$ under the results of direct and normalized PSNR. Furthermore, to overcome the high delay to reach high levels of quality (for instance 210 min for $V_3$ using SnW compared to 130 min using Epidemic), the layered video encoding enables the scheme to deliver a degraded and smaller version (that is represented by $p_1$) at significantly lower delays, which positively contributes to the viewing QoE.
## 4.5 OPEN-AREA EXPERIMENTS

This section presents and analyzes the results of the open-area experiments. The selected video sequences are disseminated first as one unlayered part, and then SVC-encoded using the proposed scheme.

### 4.5.1 *Delivery Ratio and Delay*

Results for the three video sequences using the RWP mobility are depicted in Figure 4.16. Box-plots that refer to the 25th, 50th and 75th percentiles are used, along with bars referring to the percentage number of rounds where no delivery is reported. The interpretation of the figures is the same as given in Section 4.4.1.

The results for the applied open-area settings are worse than those for the map-based settings in the previous section. The reason behind this is the low number of contacts because of the (completely) random movement. The most remarkable setback is the delivery ratio, which leads to imprecise comparisons of the delay results since they are only calculated for the successfully delivered data. For instance, for the $V_3$ video, the delay of $e_2$ (max quality using Epidemic) is higher than the delay of $s_2$ (max quality using binary SnW). This is not realistic, but it is because that the results for Epidemic are calculated among 96% of the simulation rounds (4% no-delivery rounds), whereas the results for the binary SnW are only calculated among 80% of the simulation rounds.

However, similar conclusions to those in Section 4.4.1 can be drawn, with regard to:

* Comparing the $x_1$ and $x_2$ SVC segments to the non-SVC X segment.

* The superiority of the binary SnW routing protocol among other protocols, contributing to:

- Less playout delay.

- Higher playout availability.

### 4.5.2 *Quality Distribution*

The average quality levels are calculated and listed in Table 4.6 with regard to the OPs and the corresponding PSNR values.
<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /><figcaption>Figure 4.16: Open-Area Experiments</figcaption></figure>

<table><caption>Table 4.6: Average Quality Levels (Open-Area)</caption><thead><tr><th rowspan="2">Metric</th><th colspan="3">Epidemic</th><th colspan="3">Binary SnW</th></tr><tr><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th></tr></thead><tbody><tr><td>OPs</td><td>5</td><td>4.1</td><td>3.6</td><td>4</td><td>3.1</td><td>2.8</td></tr><tr><td>PSNR</td><td>36</td><td>35.1</td><td>33.7</td><td>33</td><td>32.5</td><td>31.8</td></tr></tbody></table>

### 4.5.3 Viewing QoE

#### 4.5.3.1 Results Normalization

The viewing experience is evaluated using the Equation 4.1 from Section 4.2.2. The measurement values for quality, delay and overhead are normalized in same way as
in Section 4.4.3.1. The values of the normalized PSNR and the normalized inverted quality are given in Table 4.7.

<table><caption>Table 4.7: Average Quality Levels (Open-Area)</caption><thead><tr><th rowspan="2">Metric</th><th colspan="3">Epidemic</th><th colspan="3">Binary SnW</th></tr><tr><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th></tr></thead><tbody><tr><td>PSNR</td><td>1</td><td>0.94</td><td>0.90</td><td>0.92</td><td>0.87</td><td>0.85</td></tr><tr><td>q̃</td><td>0</td><td>0.06</td><td>0.1</td><td>0.08</td><td>0.13</td><td>0.15</td></tr></tbody></table>

### 4.5.3.2 Calculation Of The Viewing QoE

As proposed, two measurement points ($p_1, p_2$) are taken, referring to 1) the result associated with the lowest playout delay ( corresponding to the lowest quality), and 2) the result associated with the maximum delivered quality. An analytical summary of the viewing QoE values is given in Table 4.8.

<table><caption>Table 4.8: Viewing Experience Evaluation (Open-Area)</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="3">Epidemic</th><th colspan="3">Binary SnW</th></tr><tr><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>V<sub>3</sub></th></tr></thead><tbody><tr><td rowspan="6">p<sub>1</sub></td><td>PSNR</td><td>25.3</td><td>28.7</td><td>28.7</td><td>25.3</td><td>28.7</td><td>28.7</td></tr><tr><td>PSNR</td><td>0.70</td><td>0.77</td><td>0.77</td><td>0.70</td><td>0.77</td><td>0.77</td></tr><tr><td>q̃</td><td>0.3</td><td>0.23</td><td>0.23</td><td>0.3</td><td>0.23</td><td>0.23</td></tr><tr><td>t (min)</td><td>145</td><td>155</td><td>170</td><td>160</td><td>160</td><td>170</td></tr><tr><td>t̃</td><td>0.403</td><td>0.431</td><td>0.472</td><td>0.444</td><td>0.444</td><td>0.472</td></tr><tr><td>q̃</td><td>1</td><td>1</td><td>1</td><td>0.15</td><td>0.15</td><td>0.15</td></tr><tr><td></td><td>val(p<sub>1</sub>)</td><td>1.119</td><td>1.113</td><td>1.129</td><td>0.557</td><td>0.522</td><td>0.546</td></tr><tr><td rowspan="6">p<sub>2</sub></td><td>PSNR</td><td>36</td><td>35.1</td><td>33.7</td><td>33</td><td>32.5</td><td>31.8</td></tr><tr><td>PSNR</td><td>1</td><td>0.94</td><td>0.90</td><td>0.92</td><td>0.87</td><td>0.85</td></tr><tr><td>q̃</td><td>0</td><td>0.06</td><td>0.1</td><td>0.08</td><td>0.13</td><td>0.15</td></tr><tr><td>t (min)</td><td>155</td><td>255</td><td>240</td><td>190</td><td>220</td><td>215</td></tr><tr><td>t̃</td><td>0.431</td><td>0.708</td><td>0.667</td><td>0.528</td><td>0.611</td><td>0.597</td></tr><tr><td>q̃</td><td>1</td><td>1</td><td>1</td><td>0.15</td><td>0.15</td><td>0.15</td></tr><tr><td></td><td>val(p<sub>2</sub>)</td><td>1.088</td><td>1.227</td><td>1.206</td><td>0.554</td><td>0.642</td><td>0.634</td></tr><tr><td></td><td>QoE(p)</td><td>1.104</td><td>1.169</td><td>1.167</td><td>0.555</td><td>0.582</td><td>0.590</td></tr></tbody></table>

Conclusions from Figure 4.16 and Table 4.8 do not differ from those from Figure 4.14 and Table 4.5. Most importantly is how using our proposed metric allows each of the quality, delay and overhead parameters to contribute to the QoE. Moreover, how the layered video encoding enables the scheme to deliver a degraded and smaller version at lower delays, which positively contributes to the viewing QoE.
4.6 VALIDATION AND COMPARISON

This section aims to validate our results by comparing them to some of the corre-
sponding works from Section 3.2. The target works are those that are implemented
in DTNs or OppNets. Nevertheless, no direct numerical comparisons can be drawn be-
cause of the many different setting parameters. Instead, we try to estimate the results
of the presented works as if they were performed in our settings.

On the other side, for all other delivery schemes in MANETs it is not possible to draw
a comparison or a conclusion analysis because of the different settings that are meant
for the stable connectivity of MANETs.

Raffelsberger and Hellwagner [81] use a very expensive encoding technique (MPEG-based<fnref n="2" />) that must be repeated for each desired quality level. They limit the quality levels to only 2, where the second level is playable by itself independently of the first one. This flexibility comes at the expense of a large size for the higher level compared to SVC. For instance, if a video is encoded using SVC into 2 layers with the sizes s₁, s₂ respectively, the whole video will have the total size of s₁ + s₂, whereas using the technique in [81] the video will have the size of s₁ + (s₁ + s₂) because of the redundancy in the second level. Hence, the overhead can grow dramatically with the increasing number of layers (e.g. 5 in our experiments). This is depicted in Figure 4.17, which estimates the sizes of the 5 OPs of the video V₁ if the technique in [81] was applied, compared to the sizes of our OPs from Table 4.1.

<figure><img src="image_44.png" /><figcaption>Figure 4.17: Overhead Comparison</figcaption></figure>

It is easily noticed how using SVC leads to a lower overhead. Besides, to compare the
influence of the authors' work on the quality and delay to our work, we build the
comparison with regard to the two result points in Figure 4.3.

p₁: The time to deliver the first layer and the resulting quality will not differ from our experimental results that are associated with the delivery of the BL.

<footnote n="2">2 Not particularly specified.</footnote>
p₂: For the sake of fragmentation, the authors divide each level temporally into short chunks that can be encoded, decoded and played independently. Hence, the viewing QoE metric for the second result point p₂ can not be successfully applied because both delay and quality are unpredictable. The former because of the jitter between the randomly received playable parts, which makes the play-out delay unclearly defined, i.e. there is no particular moment to start watching the whole video. And the latter because of the incapability of PSNR under the absence of a lot of frames as Equation 2.3 shows, that PSNR is calculated among each frame of the video.

Another possibility is to consider that a quality level is successfully delivered only if all of its parts are delivered (while no error concealment is applied). Consequently, the authors' second quality level will have a bad delivery ratio compared to our higher levels because of the larger size due to the encoding technique. Hence, p₂ (and the total viewing experience) is worse than its counterpart in our experiments.

Wu and Ma [84] split single-stream videos in a frame-wise fashion into a number of sub-messages for each frame. They offer a single level of quality, which makes p₁ and p₂ from our viewing QoE metric absolutely identical. In their work, the authors are only interested in the delivery ratio, and no result with regard to delay are reported. However, the offered single level of quality refers to the video's full-quality, which will shift the playout delay to a larger value, which corresponds to the delay of p₂ in our experiments.

The delivered quality is either zero, if a delivery failure occurs, or it is equal to the input encoded quality, if the delivery succeeds. The absence of lower levels of quality is not suitable for environments like OppNets, where loss is common. This is also not suitable for our example scenarios, where delivering a video with a degraded quality would serve for a better viewing QoE.

Lastly, the authors route the sub-messages using the Epidemic protocol, and they control flooding by limiting the buffer size and applying a buffer management technique. Therefore, the network overhead because of further copying the messages can grow dramatically (depending on the used buffer size) up to the overhead levels of using Epidemic in our experiments.

All in all, following the authors' technique in our context will result in a viewing QoE that has:

* a worse *delay*, to deliver a single high-quality level,

* a better *quality* that refers to the full video quality, but however with a worse delivery probability,

* and varying *overhead*, depending on the chosen buffer size.
Chen et al. [82, 83] use Multiple Description Coding (MDC) to encode videos into any number of quality levels. As described in Section 2.3, MDC can achieve a better maximum quality (corresponding to $p_2$) and a better associated delay since each delivered message can help for the reconstruction. However, MDC makes no differentiation between layers, and hence no special support can be applied for the basic quality. Therefore, by exceptionally protecting the SVC's BL as Chiang et al. [51] recommend, we could achieve a better playout delay (corresponding to $p_1$), beside a close quality to MDC's basic quality. Besides, the overhead is hard to estimate in comparison to ours, because of combining channel coding with MDC in a controlled-flooding routing protocol.

Consequently, it is not possible to derive a numerical viewing QoE comparison between the authors' and our results. However, looking at the viewing QoE's two result points $p_1$ and $p_2$, our approach achieves a better result with regard to $p_1$, whereas the MDC approach is better with regard to $p_2$.

## 4.7 SUMMARY

This chapter addressed the problem of granulation and proposed the Scalable Video Coding (SVC) to encode a video into a number of unequally important layers. These layers are routed then with redundancy factors corresponding to their importance. An evaluation metric for the viewing experience was defined in a 3D feature space that consists of delivery delay, video quality and network overhead. It was calculated as an average between two feature vectors: the first one refers to the delivery of the BL quality level at the lowest delay, and the second one refers to the delivery of a higher quality level at a higher delay.

Furthermore, the experimental setup parameters were fixed, including: SVC's configurations set of scalability dimensions and levels in each dimension, and the simulator configurations set (population, mobility, routing, transmission, etc.).

Lastly, experiments were performed and evaluated using three different video sequences and two mobility patterns: RWP and SPMBM. Promising results were delivered with regard to the viewing QoE metric. With a very low overhead compared to *Epidemic*'s overhead, our proposed approach using *Binary SnW* could reach a very good playout delay (Figure 4.14). Although the delay for the maximum quality is high, the overall evaluated viewing QoE shows the applicability of the proposed scheme in *OppNets* under the given specificities (Table 4.5).

Nevertheless, there is still a space for improving the results to overcome two recognizable drawbacks. First, as shown in Figure 4.14, the high delay to deliver the BL as well as the higher quality layers. Second, as shown in Figure 4.15, the limited quality, so that not all the OPs could have always been successfully delivered.
* * *
<figure><img src="image_45.png" /></figure>
ADAPTING GRANULARITY FOR A
BETTER CONTACT-OPPORTUNITY
EXPLOITATION

5.1 PROBLEM STATEMENT

This chapter addresses the second research problem, which aims to vary and tune
the sizes of the video data chunks in a dynamic and adaptive way according to the
Opportunistic Networks (OppNets) changing conditions. Using Scalable Video Cod-
ing (SVC), as presented in Chapter 4, results in splitting videos into smaller layers, and
hence in better delivery results. However, these layers (and the overlaid Operating
Points (OPs)) possess predetermined arbitrary sizes according to the encoding con-
figurations. On the other hand, contacts in OppNets are opportunistic, and their du-
rations vary a lot. Therefore, a video layer might be exposed to one of two possible
deficiencies with regard its size and the available forwarding opportunities:

* The layer is either too big to be completely sent during a contact between two nodes, then a delivery failure is reported.

* Or it is too small compared to the contact duration, then the opportunity of data transfer is poorly exploited if no further parts are pushed in an aggressive data forwarding way [97]. However, pushing a further layer aggressively, puts this layer again against the same two possible deficiencies.

In this context, we argue that a further granulation of video layers into smaller parts can partially resolve the problem in both cases. First, smaller data parts can better fit into short contact durations and hence avoid the first deficiency with a high probability. Second, aggressive data forwarding can be supported more easily, since a number of small data parts can most likely be pushed before a disconnection occurs. However, applying a high degree of granulation introduces a new drawback of subjecting the whole video to a higher partial loss probability, which can result in delivery failures and worst-case delays.
Hence, the size of the data chunk serving as a transmission unit should be determined adaptively, depending on the changing network conditions of the *OppNet*. However, the determination of the network conditions in such a fully decentralized environment is quite difficult, since there is no central controller and nodes interact only with their changing neighbors. Consequently, this chapter introduces an adaptive solution, which enables each node in the network to predict and prepare the next optimal chunk size as precisely as possible, based on a dynamic monitoring of environmental parameters.

## 5.2 OBJECTIVES AND CONTRIBUTIONS

This section highlights the objectives and contributions of this chapter. First, it discusses an alternative approach for granulation, which goes beyond scalability layers. Then, the need for adaptivity is introduced, and propositions are discussed.

### 5.2.1 More Efficient Granulation

Experiments of Chapter 4 were concluded with two main drawbacks: a limited quality level and a high delay. One open issue is how to determine the granularity of data transmission. Indeed, while SVC layers (and the overlaying OPs) provide a good abstraction of the data related to different levels of video quality, some OPs can still be relatively large in size (up to 40-50% of the whole video, as shown in Table 4.1). Hence, due to the unreliability of the opportunistic networks, trying to transmit such an OP at once has a higher probability of failure, which limits the performance of our approach. Whereas smaller transmission units would be more appropriate to overcome the problem of short contact times.

Consequently, we propose to reduce the granularity of transmission units (on the application-layer) down to NAL Units (NALUs) that compose the SVC layers. The advantage of choosing NALUs in this context is that there is no more cost for the partitioning process, because NALUs are the atomic elements of the SVC stream by default [54]. Moreover, the concepts of unequally important parts and prioritized routing can still be applied for NALUs in the same way as before in Chapter 4 for SVC layers. Each NALU represents one frame at one specific layer, and hence can inherit the corresponding importance degree, which will affect later the redundancy factor of the routing protocol.

#### 5.2.1.1 The Number and Distribution of NALUs in a Video Stream

The number of NALUs in an SVC stream is determined by the stream's number of frames and the given scalability options (dimensions and levels). In general, there
will be a big number of NALUs, over which the total video size will be distributed. For example, using the fixed configurations in Chapter 4, Figure 5.1 depicts the distribution of NALUs in one Group-of-Pictures (GoP) of 4 frames.

<figure><img src="image_46.png" /><figcaption>Figure 5.1: NALUs in One GoP of an SVC Video</figcaption></figure>

It can be noticed that for 4 frames within one GoP, there are 16 NALUs among the 12 SVC layers. That is, the Base Layer (BL) has 1 NALU (and hence 1 frame) per GoP. To enhance the temporal resolution, the Enhancement Layers EL-1 and EL-2 double the number of frames in the GoP by adding one then two NALUs respectively. EL-3, -4 and -5 enhance their previous counterpart NALUs on the Signal-to-Noise Ratio (SNR) scalability dimension. Similarly, the ELs -6 to -11 build on the same structure to finally result in 16 NALUs representing 1 GoP of 4 frames. The same applies for all next GoPs of the video. Thus, for the whole video there would be NALUs equal to 4 times the number of frames.

Example 5.1. A video with 100 frames, 12 SVC layers and GoP=4, will have 25 GoPs, each with 16 NALUs. Hence, the BL will have one NALU per GoP = 25 × 1 = 25 NALUs, and the whole video will have 25 × 16 = 400 NALUs, over which the size of the video will be divided.

Consequently, our used sample videos will have the given distribution of NALUs in Table 5.1.

<table><caption>Table 5.1: The Distribution of NALUs in The Sample Videos</caption><thead><tr><td>Video</td><td># Frames</td><td># Layers</td><td>GoP</td><td># NALUs in BL</td><td># NALUs in Vid.</td></tr></thead><tbody><tr><td>V<sub>1</sub></td><td>600</td><td>12</td><td>4</td><td>150</td><td>2400</td></tr><tr><td>V<sub>2</sub></td><td>2000</td><td>12</td><td>4</td><td>500</td><td>8000</td></tr><tr><td>V<sub>3</sub></td><td>4000</td><td>12</td><td>4</td><td>1000</td><td>16000</td></tr></tbody></table>
5.2.1.2 The Transmission of NALUs

The size of a single NALU varies a little bit from one to another, but they are all of
very small sizes compared to the sizes of SVC layers. Example 5.1 shows how the size
of the video can be distributed over 400 NALUs instead of only 12 layers.

Consequently, an aggressive data forwarding becomes easy to implement: when com-
ing in contact with another node, say x, send one messages (a copy of an NALU). If the
contact with x is still ongoing, send a further message. This loop continues until the
contact is broken. The small sizes of NALUs will allow to better exploit the contacts
and send more units before disconnection, without an extra partitioning overhead to
generate the already existing NALUs. Nevertheless, the big number of NALUs, each of
which serving as a single transmission unit, results in a discouraging high degree of
granulation for the use-cases where a partial loss would dramatically affect the total
delivery [88, 120]. For instance, when sending an SVC layer, if any NALU of this layer
is lost (while no loss concealment is assumed to be applied<fnref n="1" />), other received units are
useless.

To express the problem of a high degree of granulation mathematically, let be:

$P(\text{Layer}_i) = q$ : the probability of delivering a layer (i) as one part

$P(\text{NALU}_{(i,j)}) = p_j$ : the probability of delivering a NALU (j) of the layer (i)

$P(\text{NALU}_i) = \prod_{j=1}^{n} p_j = p$ : the probability of delivering all the NALUs of a layer (i)

where n is the layer's total number of NALUs, so that for any SVC video: n ≫ 1, as shown in Table 5.1 and Example 5.1.

Due to the characteristics of OppNets, the delivery probability can not in general reach
its upper bound, i.e. $p_j < 1$ and $q < 1$. Furthermore, because of the difference in
size between a NALU and an SVC layer: $p_j > q$. Although p refers to delivering the
composing NALUs of the layer whose delivery probability is q, we can not assume
that p = q, because the NALUs can take different paths and thus have independent
delivery probabilities. Moreover, for a big enough n ≫ 1 then p ≪ 1 and p < q.

Therefore, an SVC layer has to be divided into a number of chunks, m, less than the
number of NALUs composing this layer: $1 < m < n$. Let $P(chunk_k) = r_k$ be the prob-
ability of delivering a newly resulting chunk (k), then we have to find the optimal
number of chunks (m) that yields:

$$
\prod_{1}^{m} r_{k} > q > p
$$

<footnote n="1">¹ Later in Chapter 6, a concealment mechanism will be studied as a further contribution of this work to overcome partial losses.</footnote>
### 5.2.2 Adaptivity

Concluded from the last section, the transmission units must lie with respect to their number and size in the range between the few but big SVC layers and the lots of but small NALUs. In other words, if the number of layers composing a scalable video is l, and the number of NALUs is n, we have to find the optimal number of chunks, m, which yields a higher delivery probability than the other cases when sending layers or NALUs, so that $l < m < n$. Tuning the optimal number of chunks takes place by determining the optimal chunk size depending on the network conditions. The advantage of having the NALUs in this context is that the number and size of the transmission units can then be dynamically adjusted by packetizing the very small units into larger chunks. Furthermore, each node in the network can perform the packetization process adaptively according to the environmental parameters on its side, which would reflect the node's knowledge about network conditions like density and mobility.

To develop an adaptive solution, there is a variety of environmental parameters that can play a role in the dynamic characterization in the OppNets. As presented in Section 3.3, these parameters include the contact time (or duration), inter-contact time and contact volume. The inter-contact time can serve for analyzing the frequency of contacts and estimating the occurrence of the next contact. The contact volume studies the stability of contacts. On the other hand, the contact time represents how long a contact between two nodes lasts. By estimating future contact times, the optimal granularity level with regard to the chunks number and size can also be estimated. Since the transmission interface and its transfer rate are fixed, then the sought chunk size can be calculated as in Equation 5.1.

$$ size = contactTime \times transferRate \qquad (5.1) $$

Besides, the calculation of the environmental parameters can use different settings regarding 1) *dynamicity*:

* Semi-dynamic setting: for relatively stable environments, the environment parameters are not set in advance, but they are calculated over a short time then they are fixed and considered to be valid for the future. Big changes in network conditions are not expected.

* Dynamic setting: for continuously changing environments, parameters are regularly updated all over the time.

and 2) *the calculation domain*:

* Local: for sparse environments, each node calculates and keeps its own environments parameters. Exchanging these information with other nodes is excluded.