ABSTRACT The moving firefighter problem (MFP) is a more realistic variant of the classic firefighter problem (FP), where firefighters require time for both travel and defense. Unfortunately, the only known exact solution for the MFP does not scale. In this paper, we establish that the MFP is NP‐complete on trees of maximum degree three and present four alternative methods to find exact solutions for the case of arbitrary trees with a single initial fire and one firefighter. The first method is a dynamic programming algorithm, while the other three methods are based on mathematical programming: an integer quadratically constrained program (IQCP), and two distinct integer linear programs (ILP and E‐ILP). Our mathematical programming formulations exploit the inherent properties of tree topologies to significantly improve scalability by reducing the number of decision variables and constraints relative to those for arbitrary graphs. We present a comprehensive experimental analysis of the performance and scalability of the proposed solutions.

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.

Prior solutions for routing to multi-instantiated destinations simply adapt existing routing algorithms designed for single-instance destinations, or rely on flooding techniques. In this paper, a new approach for routing to multi-instantiated destinations is introduced, and the Multiple Instance Destination Routing (MIDR) framework is presented as an example of the approach. MIDR uses only distance information to multi-instantiated destinations, without routers having to establish overlays, know the network topology, use complete paths to destination instances, or know about all the instances of destinations. MIDR can be used in name-based content routing, IP unicast routing, multicasting, and anycasting; even in scenarios where the network topology is highly dynamic such as in the case of MANETs. It is shown that MIDR provides multiple loop-free paths to destination instances. Extensive simulation-based experiments performed in the context of MANETs show that MIDR outperforms traditional approaches based on unicast protocols and that it scales to large networks.

The increasing adoption of mobile personal devices and Internet of Things devices is leveraging the emergence of a wide variety of opportunistic sensing applications. However, the designers of this type of applications face a set of technical challenges related to the limitations and heterogeneity of the hardware and software platforms and to the dynamics of the scenarios where they are deployed. In this paper, we introduce a Semantic‐Centric Fog‐based framework aimed at effectively and efficiently supporting this type of applications. The proposed framework is composed of local and distributed algorithms that support the establishment and coordination of sensing tasks in the Fog. First, it performs ontology‐driven in‐network processing to locate the most adequate devices to carry out a given sensing task and then, it establishes efficient multihop routes that are used to coordinate relevant devices and to transport the collected sensory data to Fog sinks. We present a set of theorems that prove that the proposed algorithms are correct and the results of a series of detailed simulation‐based experiments in NS3 that characterize the performance of the proposed platform. The results show that the proposed framework outperforms traditional sensing platforms that are based on centralized services.

We introduce the Selective-Awakening MAC (SA‐MAC) protocol which is a synchronized duty‐cycled protocol with pipelined scheduling for Linear Sensor Networks (LSNs). In the proposed protocol, nodes selectively awake depending on node density and traffic load conditions and on the state of the buffers of the receiving nodes. In order to characterize the performance of the proposed protocol, we present a Discrete‐Time Markov Chain‐based analysis that is validated through extensive discrete‐event simulations. Our results show that SA‐MAC significantly outperforms previous proposals in terms of energy consumption, throughput, and packet loss probability. This is particularly true under high node density and high traffic load conditions, which are expected to be common scenarios in the context of IoT applications. We also present an analysis by grade (i.e., the number of hops to the sink, which is located at one end of the LSN) that reveals that LSNs exhibit heterogeneous performance depending on the nodes’ grade. Such results can be used as a design guideline for future LSN implementations.

In this paper we present an experimental study of trilateration and probabilistic multilateration. Both methods are techniques aimed at estimating the location of a point, based on the position of three or more references and distances to them. To asses the effectiveness of the aforementioned methods, we present a characterization of the various error conditions, a sensitivity analysis of the trilateration and probabilistic multila-teration to measure the level of collinearity among references, and a simulation-based analysis describing the results of detailed simulation experiments used to study the performance of DV-Hop that use trilateration as method to estimate the position of their nodes, as well as the version of DV-Hop that use probabilistic multilateration for the same purpose. DV-Hop is the most representative range-free positioning algorithms in the context of mobile ad hoc networks (MANETs). Our experimental results show that the probabilistic multilateration method is superior to the traditional trilateration method.

In this paper, we present a new protocol for routing in intermittently connected mobile networks that, by periodically exchanging constant-size Counting Bloom filters, assigns to every node in the network probabilities of reaching any destination. The gradients defined by these probabilities are further used to forward data packets towards any node in the network. The proposed protocol is based on two novel operations defined over the Bloom filters, namely, the unary degradation operation that models the loss of topological information as it gets stale or as it is propagated away from the place where it was generated; and the binary addition operation that is used to acquire topological information from other nodes. These two operations are used to implement a probabilistic form of soft state that is defined in terms of the content of the Counting Bloom filters. We present a series of experimental results based on extensive detailed simulations that show that the proposed protocol outperforms the Epidemic routing protocol by delivering more data packets with less delay, while inducing less total overhead in both MANET and VANET scenarios.

A cross-layer framework is introduced for the effective dissemination of real-time and elastic traffic in multihop wireless networks called Scheduling and Traffic Management in Ordered Routing Meshes (STORM). Unicast and multicast routes are established in coordination with the scheduling of transmissions and bandwidth reservations in a way that bandwidth and delay guarantees can be enforced on a per-hop and end-to-end basis. The routes established in STORM are shown to be loop-free and real-time packets forwarded along these routes are shown to have bounded end-to-end delays. Results from detailed simulation experiments show that, compared to a protocol stack consisting of 802.11 DCF for channel access, AODV or OLSR for unicast routing, and ODMRP for multicast routing, STORM attains similar or better performance for elastic traffic, and up to two orders of magnitude improvement in end-to-end delays, with twice the amount of data delivery for real-time traffic while inducing considerably less communication overhead.

A Framework for Integrated Routing, Scheduling and Traffic Management (FIRST) in Ad Hoc Networks is introduced. Unicast and multicast routes are established in coordination with the scheduling of transmissions and bandwidth reservations in a way that bandwidth and delay guarantees can be enforced on a per-hop and end-to-end basis. Results from detailed simulation experiments show that, compared to a protocol stack consisting of 802.11 DCF for channel access, AODV or OLSR for unicast routing, and ODMRP for multicast routing, FIRST attains similar or better performance for elastic traffic, and up to two orders of magnitude improvement in end-to-end delays, with twice the amount of data delivery for real-time traffic.

We present the Ordered Proactive Enclave-based Routing for Ad-hoc networks (OPERA) protocol for unicast routing in mobile ad hoc networks (MANETs). OPERA uses source and destination labels to define elliptical interest-driven enclaves to reduce control overhead. A topological sort of destination labels is used for loop freedom. The use of label spacing allows effective local repairs. Simulation results comparing OPERA with traditional routing schemes such as AODV and OLSR show that it has a better delivery ratio and smaller delay in realistic load situations. The network load with OPERA is much smaller than with the traditional on-demand and proactive routing schemes.

To date, there are different ontologies for many domains and applications. Users can access them to share information, reuse knowledge, and integrate data sources for several purposes and applications such as semantic web, data warehousing, e-learning, e-commerce, knowledge representation, and so on. Ontology engineering is rapidly becoming a mature discipline, having produced tools and methodologies for building and managing ontologies. However, even with a clearly defined engineering methodology, building an ontology remains a challenging, time-consuming, and error-prone task, because it forces ontology builders to conceptualize their expert knowledge explicitly and to re-organize it in typical ontological categories such as concepts, properties, and axioms. In this article, an approach to conceptualizing the geographic domain is described. It is oriented toward formalizing a geographic domain conceptualization according to specifications from the Mexican Institute of Statistics, Geography and Informatics. The main goal is to provide semantic and ontological descriptions, which represent the properties and relationships that describe the behavior of geographic objects by means of concepts. GEONTO-MET is focused on developing geographic application ontologies for sharing and integrating geospatial information.

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.

A new context-aware routing framework for multicast and unicast routing in mobile ad hoc networks is introduced. This framework, which is called CAROM (Context-Aware Routing over Ordered Meshes), uses regions of interest to identify connected components of the network that span sources and destinations of interest to restrict signaling to occur mostly within these regions. Context information is used to compute routing meshes composed of shortest-paths located inside of regions of interest. Experimental results based on extensive simulations show that CAROM attains similar or better data delivery and end-to-end delays than traditional unicast and multicast routing schemes for MANETs (AODV, OLSR, ODMRP), and that CAROM incurs only a fraction of the signaling overhead of traditional routing schemes.

This paper introduces an integrated framework for multicast and unicast routing in mobile ad hoc networks (MANET) based on interest-defined mesh enclaves. Such meshes are connected components of a MANET that span the sources and receivers of unicast and multicast flows. We present the Protocol for Routing in Interest-defined Mesh Enclaves (PRIME), which establishes meshes that are activated and deactivated by the presence or absence of interest in destinations and groups, and which confines most of the signaling overhead within regions of interest (enclaves) in such meshes. Experimental results based on 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), and that PRIME incurs only a fraction of the signaling overhead of traditional routing schemes.

We present Hydra, the first multicast routing protocol for MANETs that establishes a multicast routing structure approximating the set of source-rooted shortest-path trees from multicast sources to receivers, without requiring the dissemination of control packets from each source of a multicast group. Hydra accomplishes this by dynamically electing a core for the mesh of a multicast group among the sources of the group, and aggregating multicast routing state in the nodes participating in multicast meshes, so that only control packets from the core are disseminated towards the receivers of a group. We prove that Hydra establishes correct routes from senders to receivers of a multicast group when multicast state information is aggregated. We also present simulations results illustrating that Hydra attains comparable or higher delivery ratios than ODMRP, but with considerably lower end-to-end delays and far less communication overhead. Results are shown for scenarios using 802.11 and TDMA as the MAC layer protocols.