The vertex k-center problem is a classical NP-Hard optimization problem with application to Facility Location and Clustering among others. This problem consists in finding a subset C ⊆ V of an input graph G = (V, E), such that the distance from the farthest vertex in V to its nearest center in C is minimized, where ıCı <; k, with k ε Z± as part of the input. Many heuristics, metaheuristics, approximation algorithms, and exact algorithms have been developed for this problem. This paper presents an analytical study and experimental evaluation of the most representative approximation algorithms for the vertex k-center problem. For each of the algorithms under consideration and using a common notation, we present proofs of their corresponding approximation guarantees as well as examples of tight instances of such approximation bounds, including a novel tight example for a 3-approximation algorithm. Lastly, we present the results of extensive experiments performed over de facto benchmark data sets for the problem which includes instances of up to 71009 vertices.

Vehicular networks is a key technology for efficiently communicating both user’s devices and cars for timely information regarding safe driving conditions and entertaining applications like social media, video streaming, and gaming services, among others. In view of this, mobile communications making use of cellular resources may not be an efficient and cost-effective alternative. In this context, the implementation of light-fidelity (LiFi) in vehicular communications could be a low-cost, high-data-rate, and efficient-bandwidth usage solution. In this work, we propose a mathematical analysis to study the average throughput in a road intersection equipped with a traffic light that operates as a server, which is assumed to have LiFi communication links with the front lights of the vehicles waiting for the green light. We further assume that the front vehicle (the car next to the traffic light) is able to communicate to the car immediately behind it by using its own tail lights and the front lights of such vehicle, and so on and so forth. The behavior of the road junction is modeled by a Markov chain, applying the Queueing theory with an M/M/1 system in order to obtain the average queue length. Then, Little’s theorem is applied to calculate the average waiting delay when the red light is present in the traffic light. Finally, the mathematical expression of the data throughput is derived.

Linear topologies arise naturally in the context of Internet-of-Things (IoT) applications for smart cities, where the infrastructure itself commonly has a linear or semi-linear structure. This is the case of buildings, public transportation systems, road infrastructure, and utility distribution networks. Given the prevalence of this type of topologies, several Medium Access Control (MAC) protocols have been designed to take advantage of their particular properties. Unfortunately, most of them do not scale well as the node density and the distance in hops to the sink increases. The result is that packets generated many hops away from the sink tend to experience unacceptable high end-to-end delay and low delivery probabilities. This paper introduces HP-MAC, a synchronized duty-cycled MAC protocol for Linear Sensor Networks (LSNs) that assigns transmission priorities to nodes to avoid collisions, through the implementation of distributed elections based on hash functions. HP-MAC also implements a packet queuing scheme that acts as a mechanism to control the amount of network resources allocated to data flows generated at different distances to the sink. This way, packets can reach their destination with loss probability and end-to-end delay that do not depend on their distance to the sink. We use a Discrete-Time Markov Chain (DTMC) to model the performance of the proposed protocol. Numerical solutions of this model show that HP-MAC outperforms state-of-the-art representatives in terms of throughput, end-to-end delay, power consumption, and packet loss probability. These results are validated through extensive discrete-event simulations.

A framework for integrated multicast and unicast routing in mobile ad hoc networks (MANETs) is introduced. It is based on interest-defined mesh enclaves that are connected components of a MANET spanning the sources and receivers of unicast or multicast flows. The Protocol for Routing in Interest-defined Mesh Enclaves (PRIME) is presented to implement the proposed framework for integrated routing in MANETs. PRIME establishes meshes that are activated and deactivated by the presence or absence of interest in individual destination nodes and groups and confines most of the signaling overhead within regions of interest (enclaves) in such meshes. The routes established in PRIME are shown to be free of permanent loops. Experimental results based on extensive simulations show that PRIME attains similar or better data delivery and end-to-end delays than traditional unicast and multicast routing schemes for MANETs (AODV, OLSR, ODMRP). The experiments also show that signaling in PRIME is far more scalable than the one used by traditional multicast and unicast routing protocols such as AODV, OLSR, or ODMRP.