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.

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 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.