A general methodology for direction-based irregular routing algorithms

This paper presents a general methodology for generating deadlock-free routing algorithms for irregular networks. Constructing a spanning tree on the given network, assigning directions to the network channels, creating deadlock-free zones, and specifying a logical sequence of the produced deadlock-free zones are the four fundamental steps that the proposed methodology takes to generate deadlock-free and connected routing algorithms. By applying the proposed methodology with two known labeling methods we have generated six irregular routing algorithms: three of them are novel routing algorithms and three of them (the Up/Down, Left/Right, and L-turn routing algorithms) have already been proposed in the literature. Extensive simulation experiments have been performed considering various network topologies, different network sizes (considering different network nodes and network channels), various message lengths, a variety of spanning tree roots, and a wide range of message (traffic) generation rates. Simulation results show that the six routing algorithms can be divided into three pairs. Routing members of each pair show similar behavior in terms of message latencies and saturation generation rates. However, it is worth noting that for a given topology the performance of the six routing algorithms may be totally different and it mainly depends on the network topology.     

Efficient allocation of resources in multiple heterogeneous Wireless Sensor Networks

Wireless Sensor Networks (WSNs) are useful for a wide range of applications, from different domains. Recently, new features and design trends have emerged in the WSN field, making those networks appealing not only to the scientific community but also to the industry. One such trend is the running different applications on heterogeneous sensor nodes deployed in multiple WSNs in order to better exploit the expensive physical network infrastructure. Another trend deals with the capability of accessing sensor generated data from the Web, fitting WSNs in novel paradigms of Internet of Things (IoT) and Web of Things (WoT). Using well-known and broadly accepted Web standards and protocols enables the interoperation of heterogeneous WSNs and the integration of their data with other Web resources, in order to provide the final user with value-added information and applications. Such emergent scenarios where multiple networks and applications interoperate to meet high level requirements of the user will pose several changes in the design and execution of WSN systems. One of these challenges regards the fact that applications will probably compete for the resources offered by the underlying sensor nodes through the Web. Thus, it is crucial to design mechanisms that effectively and dynamically coordinate the sharing of the available resources to optimize resource utilization while meeting application requirements. However, it is likely that Quality of Service (QoS) requirements of different applications cannot be simultaneously met, while efficiently sharing the scarce networks resources, thus bringing the need of managing an inherent tradeoff. In this paper, we argue that a middleware platform is required to manage heterogeneous WSNs and efficiently share their resources while satisfying user needs in the emergent scenarios of WoT. Such middleware should provide several services to control running application as well as to distribute and coordinate nodes in the execution of submitted sensing tasks in an energy-efficient and QoS-enabled way. As part of the middleware provided services we present the Resource Allocation in Heterogeneous WSNs (SACHSEN) algorithm. SACHSEN is a new resource allocation heuristic for systems composed of heterogeneous WSNs that effectively deals with the tradeoff between possibly conflicting QoS requirements and exploits heterogeneity of multiple WSNs.     

Capturing an intruder in product networks

In this paper, we propose a solution to the problem of capturing an intruder in a product network. This solution is derived based on the assumption of existing algorithms for basic member graphs of a graph product. In this problem, a team of cleaner agents are responsible for capturing a hostile intruder in the network. While the agents can move in the network one hop at a time, the intruder is assumed to be arbitrarily fast in a way that it can traverse any number of nodes contiguously as far as no agents reside in those nodes. Here, we consider a version of the problem where each agent can replicate new agents. Thus, the algorithm starts with a single agent and new agents are created on demand. We propose a novel method for deriving intrusion capturing algorithms based on the abstract idea of spanning search trees. Later, we utilize this method for deriving capturing algorithms for Cartesian product graphs.     

An energy-efficient permutation routing protocol for single-hop radio networks

A radio network (RN) is a distributed system where each station or node is a small hand-held commodity device called a station. Typically, each station has access to a few channels for transmitting and receiving messages. By RN(p, k), we denote a radio network with p stations, where each station has access to k channels. In a single-hop RN, every station is within the transmission range of every other station. Each station consumes power while transmitting or receiving a message, even when it receives a message that is not destined for it. It is extremely important that the stations consume power only when it is necessary since it is not possible to recharge batteries when the stations are on a mission. We are interested in designing an energy-efficient protocol for permutation routing, which is one of the most fundamental problems in any distributed system. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination address which is the identity of the destination station to which the item should be sent. The goal is to route all the items to their destinations while consuming as little energy as possible. We show that the permutation routing problem of n packets on an RN(p, k) can be solved in 2n/k+(p/k)/sup 2/+p+2k/sup 2/ slots and each station needs to be awake for at most 6n/p+2p/k+8k slots. When k/spl Lt/p/spl Lt/n, our protocol is more efficient, both in terms of total number of slots and the number of slots each station is awake compared to a previously published protocol by Nakano et al. (2001).     

A framework for reinforcement-based scheduling in parallelprocessor systems

Task scheduling is important for the proper functioning of parallel processor systems. The static scheduling of tasks onto networks of parallel processors is well-defined and documented in the literature. However, in many practical situations a priori information about the tasks that need to be scheduled is not available. In such situations, tasks usually arrive dynamically and the scheduling should be performed on-line or “on the fly”. In this paper, we present a framework based on stochastic reinforcement learning, which is usually used to solve optimization problems in a simple and efficient way. The use of reinforcement learning reduces the dynamic scheduling problem to that of learning a stochastic approximation of an unknown average error surface. The main advantage of the proposed approach is that no prior information is required about the parallel processor system under consideration. The learning system develops an association between the best action (schedule) and the current state of the environment (parallel system). The performance of reinforcement learning is demonstrated by solving several dynamic scheduling problems. The conditions under which reinforcement learning can used to efficiently solve the dynamic scheduling problem are highlighted