The Internet of Things (IoT) has emerged as a promising paradigm which facilitates the seamless integration of physical devices and digital systems, thereby transforming multiple sectors such as healthcare, transportation, and urban planning. This paradigm is also known as ad-hoc networks. IoT is characterized by several pieces of equipment called objects. These objects have different and limited capacities such as battery, memory, and computing power. These limited capabilities make it difficult to design routing protocols for IoT networks because of the high number of objects in a network. In IoT, objects often have data which does not belong to them and which should be sent to other objects, then leading to a problem known as permutation routing problems. The solution to that problem is found when each object receives its items. In this paper, we propose a new approach to addressing the permutation routing problem in single-hop IoT networks. To this end, we start by representing an IoT network as an oriented graph, and then, based on a reservation channel protocol, we first define a permutation routing protocol for an IoT in a single channel. Secondly, we generalize the previous protocol to make it work in multiple channels. Routing is done using graph theory approaches. The obtained results show that the wake-up times and activities of IoT objects are greatly reduced, thus optimizing network lifetime. This is an effective solution for the permutation routing problem in IoT networks. The proposed approach considerably reduces energy consumption and computation time. It saves 5.2 to 32.04% residual energy depending on the number of items and channels used. Low energy and low computational cost demonstrate that the performance of circuit-based and oriented graph theory is better than the state-of-the-art protocol and therefore is a better candidate for the resolution of the permutation routing problem in single-hop environment.

Internet of Things (IoT) consists of a variety of heterogeneous interconnected devices called objects or things. These objects are generally equipped with sensing, processing and wireless communication capabilities. Unfortunately, these capabilities are not enough compared to those of devices in traditional networks. For example, objects have low battery power, limited memory storage, and less processing power. There are some cases where objects have to communicate with each other. In an Autonomous Vehicular Network for example, when a vehicle needs to change its direction, it has to alert other vehicles in the same network. This is known as the permutation routing problem. More precisely, the permutation routing problem in IoT occurs when some things of the network possess items that belong to others. The goal is to send items to their respective owners. A number of solutions to the problem have been proposed in literature which focus mainly on Wireless Sensor Networks (where the memory size of objects are the same). In this paper, we propose an efficient permutation routing scheme for a single-hop IoT network (the memory size differs from one object to another). The proposed NESEPRIN protocol consists of two phases: In the first phase, we solve the permutation routing problem in a single-hop environment with a single channel, and secondly we generalize the previous solution to a network with multiple channels. Our solution makes use of the wake and sleep technique to improve the energy conservation of objects. The simulation results show that our protocol outperforms the existing protocols designed to solve the permutation routing problem in terms of energy saving when the volume of data to route is large. NESEPRIN is the better candidate to solve the permutation routing problem in a single-hop multi-channels IoT environment where the volume of data to route is huge.

Summary This article presents a fast sequential algorithm for the matrix chain ordering problem. Our solution is based on Yao's sequential algorithm that solves this problem in time by reducing the total number of distinct subproblems to be performed. We solve them fastly by avoiding some unnecessary computations. Our strategy consists in organizing the evaluation of the subproblems according to their dependencies instead of their precedence order as in the previous solutions. In many cases, our solution runs in time. An experimental study is conducted to benchmark the performance of our algorithm by measuring the average of the results obtained on five random data sets. This shows that our algorithm is 18.93 faster than Yao's sequential algorithm and 5.07 faster than the previous best CGM‐based parallel solutions on 32 processors.

A mobile ad hoc network can be defined as a network that is spontaneously deployed and is independent of any static network. The network consists of mobile nodes with wireless interfaces and has an arbitrary dynamic topology. The networks suffers from frequent link formation and disruption due to the mobility of the nodes. A clustering method is used for obtaining a hierarchical organization for the ad hoc networks. In this paper we present a clustering token based algorithm for Group Mutual Exclusion in ad hoc mobile networks. The proposed algorithm is adapted from the RL algorithm in and utilizes the concept of weight throwing in. The proposed algorithm is sensitive to link forming and link breaking. The algorithm ensures the mutual exclusion, the bounded delay, and the concurrent entering properties.

Geocasting or Multi-Geocasting in wireless sensor network is the delivery of packets from a source (or sink) to all the nodes located in one or several geographic areas. The objectives of a geocasting (multi-geocasting) protocol are the guarantee of message delivery and low transmission cost. The existing protocols which guarantee delivery run on network in which each node has an ID beforehand. They are valid either only in dense networks or must derive a planar graph from the network topology. Hence the nodes may be adapted in order to carry out huge operations to make the network planar. In this paper we consider anonymous networks. To avoid this drawback, we adopt another strategy. Firstly each node acquires a unique identifier in random ranging from 1 to n3 with high probability. Next we partition the network in multi-stage distributed clusters using Gerla & Tsai method. And finally we derive geocast and multi-geocast algorithms that guarantee delivery and that need less overhead with respect to the existing protocols. They are also suitable for networks with irregular distributions with gaps or obstacles.

A mobile ad-hoc network is considered as a dynamic autonomous system composed of mobile devices interconnected by links without wire, without the use of a fixed infrastructure and without centralized administration. The absence of a centralized infrastructure forces each device to work in a peer to peer distributed environment, and to act as a router to relay communications, or to generate its own data. The management of the network thus is strongly distributed on all elements of the network. In this paper, we present a modelling of the Mobile Ad-hoc NETwork (MANET) problem in form of a Constraint Satisfaction/ Optimization Problem called CSPADhoc. Then, to minimize the consumption of batteries for devices, we describe an approach based on an adaptation of the A star algorithm to the MANET problem called (MANET-Astar). Finally, we present some experimental results using our approach.

In their recent work in 1999, Nakano, Olariu and Schwing showed that the permutation routing of n items pretitled on a radio network model of p processors and k channels (RN(p,k)) with k /spl les/ p/spl radic/(p/2) c as open problems. This paper shows how to handle efficiently these open problems. In order to get efficiency, we show that these open problems become those of concurrent broadcast on multiple channels. More precisely, in a concurrent broadcast environment, we show that the permutation routing problem on RN(p,k) with k/spl radic/(p/2) can be performed in 2 n/k + q - 1 broadcast rounds. Where z and q are such that p = zk + r(z) and p = q(2k) + r(q) respectively, with r(z) < k and r(q) < 2k.

Abstract We propose two randomized protocols by which n (n not known) initially identical stations of a Packet Radio Network (PRN) are assigned ID numbers from 1 to n to distinguish them. They run regardless of the number of stations per channel. The first one is a naive protocol and is derived from recursive probabilistic divide‐and‐conquer techniques. It requires n/lnk broadcast rounds, where k is the number of communication channels. The second solution needs the well‐known prefix sums algorithm and we show that in this scenario the described protocol terminates in O(n/k) broadcast rounds on the average case whenever k ≤ n/lnn. These results are obtained by means of the average case analysis of algorithms, using probabilistic generating functions and formal methods. Surprisingly, our last protocol performs as well as the efficiency‐oriented protocol of Hayashi et al. in 1 , 2 , which depends on the number of stations per channel. And moreover, it can handle the case where k∈[n/3lnn, n/lnn]. Copyright © 2003 John Wiley & Sons, Ltd.

This paper presents a work-optimal CGM algorithm that solves the Longest Increasing Subsequence Problem. It can be implemented in the CGM with P processors in O(N2 ÷P) time and O(P) communication steps. It is the first CGM algorithm for this problem and it is work-optimal since the sequential algorithm has a complexity of O(N2).

In this paper, we use a variant of the geometric method to derive efficient modular linear systolic algorithms for the transitive closure and shortest path problems. Furthermore, we show that partially-pipelined modular linear systolic algorithms with an output operation, for matrix multiplication, can be as fast as the fully-pipelined existing ones and, moreover, they need less cells.