# Opportunistic Network Algorithms for Internet Traffic Offloading in Music Festival Scenarios
## 4 An Opportunistic Routing Protocol for a Festival Scenario  
In this section, we propose and present two opportunistic routing protocols especially designed for music festivals. Our aim is to determine a routing protocol which will best suit the communication patterns at a music festival. We formulate the following qualities of such an algorithm:  
* Ideally, it should consume a small amount of resources;
* The delivery delay should be less than 5-10 min for an acceptable quality of service;
* The delivered messages ratio should be above 90%. Figure 4: Crowd distribution in FMM (nodes with the same color belong to the same community). In Section 3, we pointed out that a festival crowd mimics a social structure. The natural behavior of attendees is to share these collective experiences with a group of friends. Thus, we argue that a routing algorithm could benefit from taking into consideration the social dimension when deciding the next hop for a message. To make our approach more resource-efficient, we have decided to use the idea proposed by the Spray-and-Wait algorithm [4], which bounds the number of copies a message can have at any given time. By limiting the number of copies, a flood-based forwarding scheme is avoided. Moreover, we base the forwarding decision on two social factors, namely node centrality and the number of common friends. Node centrality was first proposed by the algorithm Bubble Rap [21] as a metric to quantify node popularity. Bubble Rap embraces the fact that because a smartphone is carried by a person, the mobility pattern exhibited by such ad hoc networks closely follows people's mobility patterns. Consequently, the forwarding decision relies on two social metrics: centrality and community structure. Detecting the community structure is performed using the K-clique algorithm [22]. Although the MobEmu simulator has this mechanism for community detection already implemented, it is a time-consuming process. Our algorithm measures the centrality of nodes similarly to the Degree forwarding scheme [21] proposed by Bubble Rap. Thus, centrality is defined as the number of unique encounters a node has over a period of time. Besides being an indicator of node popularity, centrality can also be used to depict the mobility degree of a node. During a concert, most people remain static, while some may go to the food court and drinks area or briefly join another group of friends. In the case of movement, such a person will make contact with other nodes and become a better candidate to carry a message from one place to another. The number of common friends is another valuable social metric we have chosen as a substitute for community detection. Given the fact that the number of common friends is public information on Facebook, with the appropriate permissions from the owning company and the festival attendees, it could be easily collected. For this to work, each device should store an offline list of Facebook (or other social network) friends that can be securely exchanged with an encountered node at the beginning of a contact. This way, a node would not depend on global information when encountering a node, only what it has stored locally and what the encountered node advertises. We favor the number of common friends over K-clique community detection due to the complexity of the two processes. Retrieving the number of common friends has a complexity of \(O(1)\), whilst detecting the community structure can have a worst-case complexity of \(O(n^{2})\) if we use a global approach, or \(O(n)\) if we use a local approach when computing the familiarity set of a node. The familiarity set is the set of nodes which have been in contact with a node for a period which exceeds a certain threshold. In terms of graph theory, there is an undirected edge between the nodes which have fulfilled that criteria. In the worst case scenario, a node keeps track of the familiarity sets of all encountered nodes.