Abstract:Graph has been widely used to model the applications in social network, semantic web, computational biology and software analysis. Reachability query is one kind of basic queries in graph data. Currently, in allusion to graph, several index algorithms have been proposed to answer reachability query, however, they can not scale to large graph flexibly. To address the issue, a new index method called RIAIL (reachability index augmented by interval labeling) is developed in this paper. RIAIL labels each node with four-tuple. The first two elements are interval labels that encode reachability information of the spanning tree, and the last two elements encode reachability information of non-tree edges. RIAIL only needs to index when querying and the cost of index construction is little. Finally, a wide range of experiments on real and synthetic datasets are conducted to demonstrate that RIAIL can efficiently handle reachability query and easily scale to large graph.

Abstract:In multi-hop wireless sensor networks that contain a high density of nodes, precise data gathering makes nodes that are close to the sink incur a heavier workload, which depletes their energy faster and can easily cause a “hot spot” that would shorten the network lifetime. The problem of constructing a tree that has a maximum lifespan is NP-complete. An algorithm called MAXLAT can be used to solve this problem without the need for the location of nodes. MAXLAT starts from a tree whose root has the largest number of children. The nodes in the tree are classified into three subsets that go accordingly to their respective loads: bottleneck nodes, sub-bottleneck nodes, and rich nodes. Next, the MAXLAT continues to transfer descendants of high-load nodes to sub-trees of low-load nodes by coloring. When MAXLAT is terminated, it constructs a tree in which “bottleneck nodes” carry a lighter load. Simulation results show that the tree achieved by MAXLAT has a longer lifetime than trees created by previous algorithms.

Abstract:In application layer multicast (ALM) tree, when a parent node quits or fails, all its descendent nodes must adjust their positions, which causes the interruptions of multicast connections. This problem is called stability problem of ALM trees, and it may affect the continuity of multicast data transmission and then degrade user experience seriously. This paper first analyzes the stability problem of ALM trees and proposes the instantaneous stability degree model (ISDM). An approach which takes advantage of the statistical properties of members’ join-leave behaviors is proposed to estimate the relative leave probability of member nodes in ISDM. Then, real-time transmission is one of the important aspects of ALM and one major objective of the ALM-based real-time transmissions is to determine multicast tree so as to guarantee the lower delay. This paper proposes the DDSD (the degree-and delay-bounded maximum instantaneous stability degree ALM tree) problem based on the ISDM. The DDSD problem is proved to be NP-Hard and an approximation algorithm (i.e. DDSD-H) is proposed to solve it. In addition, three heuristic policies are presented for the algorithm. Finally, the simulation results demonstrate the validity of the proposed algorithms and the comparison in the performance of the three heuristic policies is made.

Abstract:This paper proposes a distributed energy efficient clustering protocol for target surveillance in sensor networks (EECTS). The protocol selects cluster heads according to a hybrid of nodes residual energy and distribution of its neighbors. In addition, for the sake of reducing the energy dissipation of the cluster head, a minimum spanning tree with root of the base station is constructed among the cluster heads. Then it sends the gathered data to its upstream node along the spanning tree. The chief task of surveillance sensor networks is to sensing the moving target. So an intra-cluster node schedule method named EECTS-1 that can senses the most part of the network and its enhanced method EECTS-2 are introduced. The two methods can obtain the high continuous surveillance degree when the moving target enters into the network. EECTS produces a linear network lifetime in the number of nodes and keeps good continuous surveillance degree simultaneously. The simulation results show that with the same performance of surveillance the EECTS-1 achieves the same lifetime as that HEED obtains and outperforms DEEG with up to 35% improvement. The EECTS-2 outperforms HEED significantly with prolonging the network lifetime about 70%~80%. Therefore the EECTS is suitable for military target surveillance and has high reliability of the sensing information.

Abstract:With the successful development of frequent item set and frequent sequence mining,the technology of data mining is natural to extend its way to solve the problem of structural pattern mining—Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry,biology,computer networks,and World-Wide Web. This paper proposes a new algorithm GraphGen for mining frequent subgraphs. GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm available,the complexity is O(n3·2n),n is the number of frequent edges in a graph dataset. The complexity of GraphGen is O〔2n·n2.5／logn〕,which is improved O(√n·logn) times than the best one. Experimental results prove this theoretical analysis.

Abstract:Reducing power consumption to extend network lifetime is one of the most important challenges in designing wireless sensor networks. One promising approach to conserving system energy is to keep only a minimal number of sensors active and put others into low-powered sleep mode, while the active sensors can maintain the communication connectivity and cover the target region completely. The problem of computing such minimal active sensor set is NP-hard. In this paper, a centralized Voronoi tessellation (CVT) based approximate algorithm is proposed to construct a near optimal cover set of active sensors required to cover the target region completely. The communication graph induced by the cover set computed by CVT algorithm is connected if sensor’s communication radius is at least twice of its sensing radius. In case of sensor’s communication radius is smaller than twice of its sensing radius, a minimum spanning tree (MST) based connection algorithm is proposed to ensure the communication connectivity of the cover set. Finally, the performance of the proposed algorithm is evaluated through theoretical analysis and extensive numerical experiments. Experimental results show that the proposed algorithm outperforms the greedy algorithm in terms of the runtime and the size of the constructed connected cover set.

Abstract:The multi-criteria minimum spanning tree (mc-MST) problem is a typical NP-hard problem. An algorithm to enumerate the set of Pareto optimal spanning trees on some mc-MST instances was put forward by Zhou and Gen, but it does not guarantee returning all the Pareto optimal solutions. To settle this problem, an improved algorithm is developed and also proved to be able to find all the true Pareto optimal solutions in this paper. The new algorithm adds some conditions in the elimination of subtrees. Simulation results show that the new algorithm can find all the Pareto optimal solutions and also show that the new algorithm has potential usage in practice.

Abstract:A parallel machine batch process scheduling problem (PBPSP) integrating batching decision is investigated. The problem is converted into the fixed charge transportation problem (FCTP). A genetic local search algorithm (GLSA) with intensification strategy of local search and escape strategy from local optimal solution is developed. The sorted edges attained by root-first search of spanning tree are used to encode spanning tree in the genetic local search algorithm. Efficient single point crossover operator appending edges to sub-tree is proposed. Network simplex method based local search is used to be the mutation of individual. To enhance the capacity of searching the global optimal solution, this paper presents an intensification strategy of local search that applies continuous random node local search to the current optimal solution and an escape strategy from local optimal solution based on random pivot mutation and random node local search. The results of computations demonstrate that the genetic local search algorithm is better than the permutation encoding genetic algorithm and the matrix encoding genetic algorithm on solution quality, and can find the optimal solution of all Benchmark problems. Moreover, the genetic local search algorithm is robust. Compared with the tabu heuristic search procedure, this algorithm can obtain more frequently the optimal solutions of the test problem instances.

Abstract:Real time transmission, which is delay sensitive, is an important aspect of application-layer multicast. It is crucial to build an efficient multicast tree to guarantee the lower delay. This research is focused on the algorithms of the minimum-delay spanning tree for the application-layer multicast. Firstly, it is stated that the total delay is affected by communication delay, processing delay and the degree of nodes. Then the network is modeled into the node-and-edge-weighted directed graph with the limited degree of nodes. In this model the problem is shown to be NP-hard. Therefore, two kinds of heuristic algorithms are proposed, which are based on the maximum degree and the maximal length path respectively. Finally, the simulation demonstrates that the proposed algorithms are valid.

Abstract:This paper proposes a distributed energy-efficient data gathering and aggregation protocol, in which a node, according to its residual energy and the strength of the signal received from its neighboring nodes, independently makes its decision to compete for becoming a cluster head. In addition, assume that the inter-cluster communication data in a multi-hop manner is sent to the designated node, it then sends the gathered data by the whole network to the base station. DEEG also proposes a simple approach to solve the cluster coverage problem. With the increase in node density, this approach produces a linear sensor network lifetime in the number of nodes. Experimental results have shown that compared with another two data gathering and aggregation protocols--- leach and PEGASIS, the DEEG algorithm, in the best case, can lead to the increase of sensor network lifetime by 1800% and 300% respectively. Moreover, since all the nodes in the sensor network die in the last 40 rounds (the last node dies) in DEEG protocol, the reliability of the sensing information in DEEG is higher than that in LEACH and PEGASIS.