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.

With the advent of the era of big data,the demand of large-scale computing makes the requirements on the performance of chips constantly increasing.Network-on-Chip(NoC),as a network-communication-centered interconnection structure on chips,has achieved a good tradeoff in all aspects of communication.The physical layout and interconnection mode of NoC components have a significant impact on the overall performance of the chip(such as signal delay,circuit cost).Due to the limited area of the chip,minimizing the total length of wires connecting components,in other words,minimizing wirelength,is considered as the key of chip design.The hierarchical cubic network is an excellent interconnection network which has less communication delay,better reliability and greater scalability while the linear array is one of the common topologies of NoC.When the hierarchical cubic network is ported to the linear array,the structure and algorithm of hierarchical cubic network can be simulated on the linear array.Graph embedding is a key technology to realize network porting.In graph embedding,the goal of minimizing the total wire length can be achieved by finding the optimal embedding with minimum wirelength.This paper mainly studies the optimal embedding problem of hierarchical cubic networks into linear arrays with minimum wirelength.Firstly,by studying the optimal set of the hierarchical cubic network,an embedding scheme hel of hierarchical cubic networks into linear arrays is proposed,and it is proved that the wirelength under hel is minimum compared with other embedding schemes,that is, hel is an optimal embedding.Then,the exact value of the wirelength under hel and an embedding algorithm with O(N) time complexity are given,where N=22n is the number of vertices of the n-dimensional hierarchical cube network.Furthermore,an algorithm of physical linear layout in NoC for hierarchical cubic networks is proposed.Finally,comparison experiments are conducted to evaluate the performance of embed-ding hel.