Search

Graph embedding is a powerful method in parallel computing that maps a guest network G into a host network H. The performance of an embedding can be evaluated by certain parameters, such as the dilation, the edge congestion, and the wirelength. In this manuscript, we obtain the wirelength (exact and minimum) of embedding complete multi-partite graphs into Cartesian product of paths and/or cycles, which include n-cube, n-dimensional mesh (grid), n-dimensional cylinder, and n-dimensional torus, etc., as the subfamilies.

Wireless sensor networks (WSNs) integrate sensor technology, communication technology and information processing technology; it is a synthetic discipline. WSNs have been applied into almost all walks of life. However, in many special fields, network security is a basic and important factor which we must concern for. This paper introduces the key management scheme after analyzing the security threats of LEACH protocol. At the same time, we adopt several related mechanisms to protect the communication among the sensor nodes and the confidentiality of the data transmission. Also, we use the mixed multipath mechanism among the clusters to improve the security of the network and strengthen the intrusion tolerance.

Deployment is a fundamental issue in wireless sensor networks (WSNs), which affects the performance and lifetime of the networks. Usually the sensor locations are precomputed based on “perfect” sensor detection model, whereas sensors may not always provide reliable information, either due to operational tolerance levels or environmental factors. Therefore, it is very important to take into account this uncertainty in the deployment process. In this paper, we address the problem of sensor deployment in a mixed sensor network where the mobile and static nodes work collaboratively to perform deployment optimization task. We consider the Gaussian white noise in the environment and present a centralized algorithm (FABGM for short) which discoveres vacancies by using detection model based on false alarm and moves the mobile nodes according to the method based on bipartite graph matching in this study. In this algorithm, the management node of the WSNs collects the geographical information of all of the static and mobile sensors. Then, the management node executes the algorithm to get the best matches between mobile sensors and coverage holes. Simulation results are presented to demonstrate the effectiveness of the proposed approach.

Navigation with wireless sensor networks (WSNs) is the key to provide an effective path for the mobile node. Without any location information, the path planning algorithm generates a big challenge. Many algorithms provided efficient paths based on tracking sensor nodes which forms a competitive method. However, most previous works have overlooked the distance cost of the path. In this paper, the problem is how to obtain a path with minimum distance cost and effectively organize the network to ensure the availability of this path. We first present a distributed algorithm to construct a path planning infrastructure by uniting the neighbors’ information of each sensor node into an improved connected dominating set. Then, a path planning algorithm is proposed which could produce a path with its length at most c times the shortest Euclidean length from initial position to destination. We prove that the distributed algorithm has low time and message complexity and c is no more than a constant. Under different deployed environments, extensive simulations evaluate the effectiveness of our work. The results show that factor c is within the upper bound proved in this paper and our distributed algorithm achieves a smaller infrastructure size.

In wireless sensor networks, it is of great importance for fault diagnosis to ensure the gathering information accuracy and reduce energy additionally consumed by faulty nodes, for the deployment of a large number of sensor nodes in hostile environment. In this paper, we propose an energy-efficient data collection protocol which consists of clustering and multipath routing. Clustering based on fault diagnosis eliminates the possibility of cluster heads (CHs) acting by faulty nodes which reduce energy consumption and fault information transmission. Multipath routing provided by directed acyclic graph (DAG) increases system fault tolerance. Furthermore, clustering and multihop routing consider residual energy and routing cost, respectively; thus balanced energy consumption is achieved. Performance analysis shows that the message complexity disseminated in clustering and fault diagnosis is acceptable. Simulations demonstrate that the protocol has better energy efficiency compared with other related protocols.

Processing the gathered information efficiently is a key functionality for wireless sensor networks. In generally, the sensor networks often use in-network data aggregation and clustering to optimize network communication. The set of aggregating nodes forms a dominating set of the network graph. Finding the weakly connected dominating set (WCDS) is a promising approach for clustering the WSN. However, finding a minimum WCDS is NP-hard problem for most graphs, and a host of approximation algorithm has been proposed. The aim of the paper is to construct a minimum WCDS as a clustering scheme for WSN. Our clustering schemes construction algorithm includes two phases. First of all, we construct a maximal data aggregation tree (DAT) of the network. The second phase of the algorithm is to choose the nodes (called connectors) to make the WCDS connected. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations.

Mobile agent (MA) systems provide new capabilities for energy-efficient data processing by flexibly planning its itinerary for facilitating agent-based data collection and aggregation. In this paper, we present a cooperative data processing algorithm based on mobile agent (MA-CDP), and considers MA in multihop environments and can autonomously clone and migrate themselves in response to environmental changes. MA accounts for performing data processing and making data aggregation decisions at nodes rather than bringing data back to a central processor, and redundant sensory data will be eliminated. The results of our simulation show that MA-based cooperative data processing provides better performance than directed diffusion in terms of end-to-end delivery latency, packet delivery ratio, and energy consumption.

The problem of constructing independent spanning trees (ISTs) dates back to as early as the late 1980s. Given a network G of a certain topology, the question is whether we can, as well as how to, construct a set of ISTs in G. ISTs have proven to be of great importance in many network tasks. The past decade has seen a particularly remarkable increase in the literature on ISTs, manifesting a significant growth of interest. ISTs can be classified into edge-independent spanning trees (edge-ISTs), node-independent spanning trees (node-ISTs), and completely independent spanning trees (CISTs). For a network G, node-ISTs (edge-ISTs) rooted at u are a set of spanning trees rooted at u in G such that there are no common internal nodes (edges) between u and any other node among the paths in these spanning trees. If every node in a set of node-ISTs can act as a root node, the set of trees is called CISTs. This survey aims at bringing together important works on ISTs that have been reported in the literature. It provides a historical perspective of how the field has evolved, and can serve as an integrated useful resource of references for future research on ISTs. [ABSTRACT FROM AUTHOR]

Network representation learning (NRL) advances the conventional graph mining of social networks, knowledge graphs, and complex biomedical and physics information networks. Dozens of NRL algorithms have been reported in the literature. Most of them focus on learning node embeddings for homogeneous networks, but they differ in the specific encoding schemes and specific types of node semantics captured and used for learning node embedding. This article reviews the design principles and the different node embedding techniques for NRL over homogeneous networks. To facilitate the comparison of different node embedding algorithms, we introduce a unified reference framework to divide and generalize the node embedding learning process on a given network into preprocessing steps, node feature extraction steps, and node embedding model training for an NRL task such as link prediction and node clustering. With this unifying reference framework, we highlight the representative methods, models, and techniques used at different stages of the node embedding model learning process. This survey not only helps researchers and practitioners gain an in-depth understanding of different NRL techniques but also provides practical guidelines for designing and developing the next generation of NRL algorithms and systems. [ABSTRACT FROM AUTHOR]

The optimal embeddings of paths of all possible lengths between two arbitrary distinct nodes in twisted cubes are analyzed. The special cases for the nonexistence and existence of embeddings of paths between nodes u and v with length dist(T[Q.sub.n],u,v) + 1 are also discussed.

The crossed cube is an important variant of the hypercube. It is shown that a stronger connectivity for crossed cubes not only by a Hamilton path but also by many other paths of consecutive lengths in interconnection networks.

Graph embedding is a powerful method in parallel computing that maps a guest network G into a host network H. The performance of an embedding can be evaluated by certain parameters, such as the dilation, the edge congestion and the wirelength. In this manuscript, we obtain the wirelength (exact and minimum) of embedding complete multi-partite graphs into Cartesian product of paths and/or cycles, which include n-cube, n-dimensional mesh (grid), n-dimensional cylinder and ndimensional torus, etc., as the subfamilies. [ABSTRACT FROM AUTHOR]

The k-ary n-cube is one of the most attractive interconnection networks for parallel and distributed computing systems. In this paper, we investigate hamiltonian cycle and path embeddings in k-ary n-cubes Qnk based on structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph. Let H be a connected graph with H ∈{K1, K1,1, K1,2, K1,3}. We show that for two arbitrary distinct healthy nodes of a faulty Qnk, there exists a fault-free hamiltonian path connecting these two nodes if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. We also show that there exists a fault-free hamiltonian cycle if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. These results mean that the k-ary n-cube Qnk can tolerate up to 4(n-2) faulty nodes such that Qnk - V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qnk. . [ABSTRACT FROM AUTHOR]

Recent research shows that huge energy saving can be achieved in wireless sensor networks by introducing mobile collector (MC) that visits sensor nodes and collects data from them via short-range communications. One bottleneck of such approach is the large data collection latency incurred by the slow-moving MC. It is observed that the latency can be effectively shortened by performing local data aggregation. In this paper, we formulate this problem as rendezvous-based mobile data collection (MDC-RN), and prove that it is NP-hard. In MDC-RN, the locally aggregated data is first relayed to rendezvous nodes (RNs) under the constraint of relay hop d, and then the data cached by RNs is uploaded to MC when it arrives. In order to minimize the MC tour and optimize the routes in aggregation trees, we propose two efficient rendezvous-based algorithms. The centralized algorithm selects RNs according to the load priority, while the distributed scheme determines RNs based on underlying aggregation trees. The effectiveness of our algorithms is validated through both theoretical analysis and extensive simulations. [ABSTRACT FROM AUTHOR]

DCell has been proposed for data centers as a server-centric interconnection network structure. DCell can support millions of servers with high network capacity by only using commodity switches. With one exception, we prove that a k level DCell built with n port switches is Hamiltonian-connected for k ≥ 0 and n ≥ 2. Our proof extends to all Generalized DCell connection rules for n ≥ 3. Then, we propose an O(tk) algorithm for finding a Hamiltonian path in DCellk, where tk is the number of servers in DCellk. Furthermore, we prove that DCellk is (n + k - 4)-fault Hamiltonian-connected and (n + k -- 3)-fault Hamiltonian. In addition, we show that a partial DCell is Hamiltonian-connected if it conforms to a few practical restrictions. [ABSTRACT FROM AUTHOR]

The Vertex Cover (VC) problem is a classical optimization problem that can be applied in topology design in Wireless Sensor Networks (WSNs). In this paper, we first propose two polynomial time approximation schemes (PTASs) for the Minimum Vertex Cover (MVC) problem and the Minimum Weighted Vertex Cover (MWVC) problem in growth-bounded graphs. We then propose an approximation algorithm, with a performance guarantee of (1 + 2ε/(1 - ε)) for sufficiently small ε>0, for the Minimum Connected Vertex Cover (MCVC) problem. In contrast to previously proposed schemes for VC problems, our approach does not assume geometric representation of vertices in growth-bounded graphs. We also prove that the running times of the proposed algorithms are bounded by a polynomial in terms of the graph size and the input ε. We evaluate the performance of our algorithms through simulation. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, it is of great importance for fault diagnosis to ensure the gathering information accuracy and reduce energy additionally consumed by faulty nodes, for the deployment of a large number of sensor nodes in hostile environment. In this paper, we propose an energy-efficient data collection protocol which consists of clustering and multipath routing. Clustering based on fault diagnosis eliminates the possibility of cluster heads (CHs) acting by faulty nodes which reduce energy consumption and fault information transmission. Multipath routing provided by directed acyclic graph (DAG) increases system fault tolerance. Furthermore, clustering and multihop routing consider residual energy and routing cost, respectively; thus balanced energy consumption is achieved. Performance analysis shows that the message complexity disseminated in clustering and fault diagnosis is acceptable. Simulations demonstrate that the protocol has better energy efficiency compared with other related protocols. [ABSTRACT FROM AUTHOR]

Examines the diagnosability of a multiprocessor system. Properties of the crossed cube; Comparison of power between crossed cube and hypercube; Use of polynomial algorithm to diagnose the n-dimensional crossed cube.