Narrow Results

Opportunistic Network (OppNet) IoT is a subsection of Mobile Adhoc Network (MANET) in which the connection between nodes is not regulated. In MANET, the message is transmitted to the destination with the known routing path, whereas OppNet can transmit data without having a predefined path for data transmission. Estimating the path between sources and destinations is complicated due to the lack of infrastructure and the frequently changing environment. In this research, efficient routing with the detection or classification of nodes is accomplished with a multi-hop routing-based deep learning model. The EPRoPHET routing algorithm is based on a deep learning strategy in which the energy-efficient routing decision is made based on node classification. The deep learning model optimized deep convolutional neural network (DCNN) is utilized to classify reliable and unreliable nodes based on their ability to deliver the message. The hyperparameters used in the DCNN are updated with the Bird Swarm bionic Model (BSBM). Information, such as node movement, location, distance between nodes, and energy status, is considered when estimating the delivery probability. The decision about the forwarder node is taken with the memory of individual nodes and the previous routing information. The performance of a proposed approach is evaluated and compared with the existing state-of-the-art approaches. For 150 nodes, the proposed model achieved a better delivery probability of 0.96, an overhead ratio of 15.6, a latency of 4,100ms and an energy consumption of 37.5J, respectively. The higher performance obtained with the EPRoPHET routing algorithm represents the efficiency of a proposed approach.

In Wireless Sensor Network (WSN), node localization is a crucial need for precise data gathering and effective communication. However, high energy requirements, long inter-node distances and unpredictable limitations create problems for traditional localization techniques. This study proposes an innovative two-stage approach to improve localization accuracy and maximize route selection in WSNs. In the first stage, the Self-Adaptive Binary Waterwheel Plant Optimization (SA-BWP) algorithm is used to evaluate a node’s trustworthiness to achieve accurate localization. In the second stage, the Gazelle-Enhanced Binary Waterwheel Plant Optimization (G-BWP) method is employed to determine the most effective data transfer path between sensor nodes and the sink. To create effective routes, the G-BWP algorithm takes into account variables like energy consumption, shortest distance, delay and trust. The goal of the proposed approach is to optimize WSN performance through precise localization and effective routing. MATLAB is used for both implementation and evaluation of the model, which shows improved performance over current methods in terms of throughput, delivery ratio, network lifetime, energy efficiency, delay reduction and localization accuracy in terms of various number of nodes and rounds. The proposed model achieves highest delivery ratio of 0.97, less delay of 5.39, less energy of 23.3 across various nodes and rounds.

The class of hypercubes is one of the most important and popular topologies for interconnection networks of multicomputer systems. This class includes the binary hypercube and generalized hypercube. Based on the observation that these two graphs can be constructed using a graph theoretic operation known as the product of graphs, we propose a new method for generating large symmetric graphs for networks of multicomputer systems. This method is essentially algebraic in nature, and makes use of the product of a class of graphs known as quasi-group graphs. We call the graphs we obtain PQG graphs. Because these graphs are constructed by an algebraic operation, it simplifies the analysis of their performance. Many of the well-known topologies can in fact be expressed as PQG graphs; this makes the method a very general one. We also investigate the problem of routing in a PQG graph, and propose a hardware implementation of the routing algorithm to reduce the delay in the routing of messages. We then apply our results to the Petersen graph and show that the product of such graphs has vastly superior topological properties than hypercubes of the same degree.

We propose a novel approach for shortest path routing in wireless mobile networks. The approach makes use of n mobile agents initially launched from n mobile nodes forming the network. The agents move randomly from node to node and update routing information as they go. The approach is presented in this paper with two protocols. Both of them exhibit good performance in terms of the network and computing resource consumptions. The first protocol relies on independent mobile agents and imposes a minimum bandwidth requirement on individual mobile agents. Each agent carries the link state of its creator and this information remains unchanged except when the mobile agent returns to the home node. The second protocol is a refinement of the first protocol, with some form of interaction between the mobile agents. Each agent maintains the routing table of its creator instead of link state. The randomly walking agents spread the update information and compute the shortest paths via exchanging network state information between the routing tables they carry and the routing tables at the nodes they traverse. The correctness of the protocols is proven. Our analysis shows that the agent cooperation improves the system performance when dealing with topology and link cost changes.

We consider the routing number of trees, denoted by rt(), with respect to the matching routing model. For an arbitrary n-node tree T, it is known that rt(T) < 3n/2 + O(log n). In this paper, by providing a recursive off-line permutation routing algorithm, we show that the routing number of an n-node complete d-ary tree of height h(T) > 1 is bounded from above by n + o(n). This is near optimal since, for an n-node complete d-ary tree T of height h(T) > 1 it holds that rt(T) ≥ n.

The last thirty years have seen tremendous growth in research in mobile telecommunications. However, interest in mobile computing, which includes mobile telephony and more, has increased over the last ten years. Nevertheless, most of the research on mobile computing addresses the "engineering" issues and the electronic componentary required for building mobile systems. On the other hand, algorithmics research in mobile computing is still in its infancy, and only dates back to few years. The elegance and terseness that exist today in algorithmics, especially parallel computing algorirthmics, can be brought to bear on research on "mobile computing algorithmics". However, mobility brings to the stage a whole gamut of new problems that needs to be addressed in order to develop new and efficient parallel algorithms that can be used to solve mobile computing problems.

New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the network topology are hard to be effectively captured in a classical graph model. In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristic of such networks, in order to propose and formally analyze least cost journey (the analog of paths in usual graphs) in a class of dynamic networks, where the changes in the topology can be predicted in advance. Cost measures investigated here are hop count (shortest journeys), arrival date (foremost journeys), and time span (fastest journeys).

Routing in the newer generation of network transmission methods may be performed at various levels of the IP stack such as datagram, TCP stream, and application levels. It is important in the use of these methods to compute the routes that minimize the end-to-end delays for the specific routing mechanism. We formulate an abstract network path computation problem, the dynamic quickest path problem, to encompass a number of message forwarding mechanisms including circuit switching, Internet Protocol, and their variations. This problem deals with the transmission of a message from a source to a destination with the minimum end-to-end delay over a network with propagation delays and dynamic bandwidth constraints on the links. The available bandwidth for each link is specified as a piecewise constant function. We present for each message forwarding mechanism or mode an algorithm to compute a path with the minimum end-to-end delay for a given message size. Our algorithms with suitable network restrictions have polynomial time complexity in the size of the network and total number of segments in the bandwidth list.

Ant Colony Optimization (ACO) techniques can be successfully implemented to solve many combinatorial optimization problems. After the traveling salesman problem was successfully solved using the ACO technique, other researchers have concentrated on solving other problems like the quadratic assignment and the job-shop scheduling problems using the same technique. In this paper we use the ACO technique to route messages through an N×N Optical Multistage Interconnection Network (OMIN) allowing upto 'C' limited crosstalk's (conflicts between messages within a switch) where 'C' is a technology driven parameter and is always less than log₂N. Messages with switch conflicts satisfying the crosstalk constraint are allowed to pass in the same group, but if there is any link conflict, then messages have to be routed in a different group. The focus is to minimize the number of passes required for routing allowing upto 'C' limited crosstalks in an N×N optical network. This routing problem is an NP-hard problem. In this paper we show how the ACO technique can be applied to the routing problem and compare the performance of the ACO technique to that of the degree-descending algorithm using simulation techniques. Finally the lower bound estimate on the minimum number of passes required is calculated and compared to the results obtained using the two algorithms discussed. The results obtained show that the ACO technique performs better than the degree-descending algorithm and is quite close to optimal algorithms to the problem.

In this paper, we present a fully distributed process to collect and distribute the minimal connected component (MCC) fault information so that the shortest-path between a source and its destination can always be found in the corresponding information-based routing via routing decisions made at each intermediate node. Considering the communication cost in the above information distribution, a more practical implementation is provided with a low number of nodes involved in the information propagation. The experimental results show substantial improvement of our approach in terms of the success rate in finding the shortest-path and the average path length.

We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalized to non periodic infinite words as well.

We consider the convergecast problem in wireless sensor networks where each sensor has a reading that must reach a designated sink. Since a sensor reading can usually be encoded in a few bytes, more than one reading can readily fit into a standard transmission packet. We assume that each packet hop consumes one unit of energy. Our objective is to minimize the total energy consumed to send all readings to the sink. We show that this problem is NP-hard even when all readings are of fixed size. We then study a class SPEP of distributed algorithms that is completely defined by two properties. Firstly, the packets hop along some shortest path to the sink. Secondly, the nodes use an elementary packing algorithm to pack readings into packets.

Our main technical contribution is a lower bound. We show that no algorithm for UCCP that either follows the shortest path or packs in an elementary manner is a (2 − ϵ)-approximation, for any fixed ϵ > 0. To complement this, we show that SPEP algorithms are -approximation for UCCP and 3-approximation for CCP, where k ≥ 2 is the number of readings that can fit within a packet. We conclude with some special cases and experimental observations.

The interconnetion network plays an important role in a parallel system. To avoid the edge number of the interconnect network scaling rapidly with the increase of dimension and achieve a good balance of hardware costs and properties, this paper presents a new interconnection network called exchanged $3$-ary $n$-cube ($E3C$). Compared with the $3$-ary $n$-cube structures, $E3C$ shows better performance in terms of many metrics such as small degree and fewer links. In this paper, we first introduce the structure of $E3C$ and present some properties of $E3C$; then, we propose a routing algorithm and obtain the diameter of $E3C$. Finally, we analyze the diagnosis of $E3C$ and give the diagnosibility under PMC model and MM* model.

We give a new routing algorithm for double loop networks with n nodes which requires O(log n) time for preprocessing and constant processing time at each node on the route. A simple modification of the algorithm works for the case of a single fault (either node or link). The routing is always through a shortest path and the only information needed by a node to process is the address of the destination.

We show that the edges of the modified Knödel graph can be grouped into dimensions which are similar to the dimensions of hypercubes. In particular, routing, broadcasting and gossiping, can be done easily in modified Knödel graphs using these dimensions.

The capability of fault tolerance is one of the advantages of multiprocessor systems. In this paper, we prove that the fault tolerance of an n-star graph is 2n-5 with restriction to the forbidden faulty set. And we propose an algorithm for examining the connectivity of an n-star graph when there exist at most 2n - 4 faults. The algorithm requires O(n²log n) time. Besides, we improve the fault-tolerant routing algorithm proposed by Bagherzadeh et al. by calculating the cycle structure of a permutation and the avoidance of routing message to a node without any nonfaulty neighbor. This calculation needs only constant time. And then, we propose an efficient fault-tolerant broadcasting algorithm. When there is no fault, our broadcasting algorithm remains optimal. The penalty is O(n) if there exists only one fault, and the penalty is O(n²) if there exist at most n - 2 faults.

Fast and efficient communication is one of the most important requirements in today's multicomputers. When reaching a larger scale of processors, the probability of faults in the network increases, hence communication must be robust and fault tolerant. The recently introduced family of folded Petersen networks, constructed by iteratively applying the cartesian product operation on the well-known Petersen graph, provides a regular, node– and edge-symmetric architecture with optimal connectivity (hence maximal fault-tolerance), and logarithmic diameter. Compared to the closest sized hypercube, the folded petersen network has a smaller diameter, lower node degree and higher packing density.

In this paper, we study fundamental communication primitives like single routing, permutation routing, one-to-all broadcasting, multinode-broadcasting (gossiping), personalized communications like scattering, and total exchange on the folded Petersen networks, considering two communication models, namely single link availability (SLA) and multiple link availability (MLA). We derive lower bounds for these problems and design optimal algorithms in terms of both time and the number of message transmissions. The results are based on the construction of minimal height spanning trees in the fault-free folded Petersen network. We further analyze these communication primitives in faulty networks, where processing nodes and transmission links cease working. This analysis is based on multiple arc-disjoint spanning trees, a construct also useful for analyzing other families of multicomputer networks.

We propose a constant node degree network topology, multitriangle, which is hierarchical, recursive, and expansive. First we introduce a corner cutting approach that generates a set of new network topologies (including multitriangles), followed by a formal definition of the multitriangle network and discussion of its properties. The salient features of this network are that it is a constant node degree network and it can be viewed as a hierarchical ring, a popular topology which has been adopted in several commercial systems. Algorithms for node-to-node routing, hierarchical ring routing, optimal ring routing, and broadcasting are presented. The multitriangle network is analyzed in terms of diameter, degree, average distance, and message density, and results are compared with other relevant networks.

Index-shuffle graphs are introduced as candidate interconnection networks for parallel computers. The comparative advantages of index-shuffle graphs over the standard bounded-degree "approximations" of the hypercube, namely butterfly-like and shuffle-like graphs, are demonstrated in the theoretical framework of graph embedding and network emulations.

An N-node index-shuffle graph emulates:

• an N-node shuffle-exchange graph with no slowdown, which the currently best emulations of shuffle-like graphs by hypercubes and butterflies incur a slowdown of Ω(log N).

• its like-sized butterfly graph with a slowdown O(log log log N), while the currently best emulations of butterfly-like graphs by shuffle-like graphs incur a slowdown of Ω(log log N).

• an N-node hypercube that executes an on-line leveled algorithm with a slowdown O(log log N), while the slowdown of currently best such emulations of the hypercube by its bounded-degree shuffle-like and butterfly-like derivatives remains Ω(log N). Our emulation is based on an embedding of an N-node hypercube into an N-node index-shuffle graph with dilation O(log log N), while the currently best embeddings of the hypercube into its bounded-degree shuffle-like and butterfly-like derivatives incur a dilation of Ω(log N).

We propose a new protocol for one-to-one communication in multiprocessor networks, which we call the Dynamic Scheduling Communication (or DSC) protocol. In the DSC protocol, the capacity of a link is partitioned into two channels: a data channel, used to transmit packets, and a control channel used to make reservations. We initially describe the DSC protocol and the data structures needed to implement it for a general network topology. We then analyze the steady-state throughput of the DSC protocol for random node-to-node communication in a hypercube topology. The analytical results obtained are in very close agreement with corresponding simulation results. For the hypercube topology, and under the same set of assumptions on the node architecture and the routing algorithm used, the DSC protocol is found to achieve higher throughput than packet switching, provided that the size of the network is sufficiently large. We also investigate the relationship between the achievable throughput and the fraction of network capacity dedicated to the control channel, and present a method to select this fraction so as to optimize throughput.