Water quality sensor networks are promising tools for the exploration of oceans.Some key areas need to be monitored effectively.Water quality sensors are deployed randomly or uniformly,however,and understanding how to...Water quality sensor networks are promising tools for the exploration of oceans.Some key areas need to be monitored effectively.Water quality sensors are deployed randomly or uniformly,however,and understanding how to deploy sensor nodes reasonably and realize effective monitoring of key areas on the basis of monitoring the whole area is an urgent problem to be solved.Additionally,energy is limited in water quality sensor networks.When moving sensor nodes,we should extend the life cycle of the sensor networks as much as possible.In this study,sensor nodes in non-key monitored areas are moved to key areas.First,we used the concentric circle method to determine the mobile sensor nodes and the target locations.Then,we determined the relationship between the mobile sensor nodes and the target locations according to the energy matrix.Finally,we calculated the shortest moving path according to the Floyd algorithm,which realizes the redeployment of the key monitored area.The simulation results showed that,compared with the method of direct movement,the proposed method can effectively reduce the energy consumption and save the network adjustment time based on the effective coverage of key areas.展开更多
On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP ...On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.展开更多
Purpose-Isometric feature mapping(Isomap)is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization.The most time-consuming step in Isomap is to compute the shorte...Purpose-Isometric feature mapping(Isomap)is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization.The most time-consuming step in Isomap is to compute the shortest paths between all pairs of data points based on a neighbourhood graph.The classical Isomap(C-Isomap)is very slow,due to the use of Floyd’s algorithm to compute the shortest paths.The purpose of this paper is to speed up Isomap.Design/methodology/approach-Through theoretical analysis,it is found that the neighbourhood graph in Isomap is sparse.In this case,the Dijkstra’s algorithm with Fibonacci heap(Fib-Dij)is faster than Floyd’s algorithm.In this paper,an improved Isomap method based on Fib-Dij is proposed.By using Fib-Dij to replace Floyd’s algorithm,an improved Isomap method is presented in this paper.Findings-Using the S-curve,the Swiss-roll,the Frey face database,the mixed national institute of standards and technology database of handwritten digits and a face image database,the performance of the proposed method is compared with C-Isomap,showing the consistency with C-Isomap and marked improvements in terms of the high speed.Simulations also demonstrate that Fib-Dij reduces the computation time of the shortest paths from O(N3)to O(N2lgN).Research limitations/implications-Due to the limitations of the computer,the sizes of the data sets in this paper are all smaller than 3,000.Therefore,researchers are encouraged to test the proposed algorithm on larger data sets.Originality/value-The new method based on Fib-Dij can greatly improve the speed of Isomap.展开更多
基金This research was funded by the National Natural Science Foundation of China(Grant No.61802010)National Social Science Fund of China(Grant No.19BGL184)+1 种基金Beijing Excellent Talent Training Support Project for Young Top-Notch Team(Grant No.2018000026833TD01)and Hundred-Thousand-Ten Thousand Talents Project of Beijing(Grant No.2020A28).
文摘Water quality sensor networks are promising tools for the exploration of oceans.Some key areas need to be monitored effectively.Water quality sensors are deployed randomly or uniformly,however,and understanding how to deploy sensor nodes reasonably and realize effective monitoring of key areas on the basis of monitoring the whole area is an urgent problem to be solved.Additionally,energy is limited in water quality sensor networks.When moving sensor nodes,we should extend the life cycle of the sensor networks as much as possible.In this study,sensor nodes in non-key monitored areas are moved to key areas.First,we used the concentric circle method to determine the mobile sensor nodes and the target locations.Then,we determined the relationship between the mobile sensor nodes and the target locations according to the energy matrix.Finally,we calculated the shortest moving path according to the Floyd algorithm,which realizes the redeployment of the key monitored area.The simulation results showed that,compared with the method of direct movement,the proposed method can effectively reduce the energy consumption and save the network adjustment time based on the effective coverage of key areas.
基金the National Natural Science Foundation of China under Grant No. 60671033.
文摘On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.
基金supported by the National Natural Science Foundation of China under Grant Nos 91220301,61273314 and 61175064.
文摘Purpose-Isometric feature mapping(Isomap)is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization.The most time-consuming step in Isomap is to compute the shortest paths between all pairs of data points based on a neighbourhood graph.The classical Isomap(C-Isomap)is very slow,due to the use of Floyd’s algorithm to compute the shortest paths.The purpose of this paper is to speed up Isomap.Design/methodology/approach-Through theoretical analysis,it is found that the neighbourhood graph in Isomap is sparse.In this case,the Dijkstra’s algorithm with Fibonacci heap(Fib-Dij)is faster than Floyd’s algorithm.In this paper,an improved Isomap method based on Fib-Dij is proposed.By using Fib-Dij to replace Floyd’s algorithm,an improved Isomap method is presented in this paper.Findings-Using the S-curve,the Swiss-roll,the Frey face database,the mixed national institute of standards and technology database of handwritten digits and a face image database,the performance of the proposed method is compared with C-Isomap,showing the consistency with C-Isomap and marked improvements in terms of the high speed.Simulations also demonstrate that Fib-Dij reduces the computation time of the shortest paths from O(N3)to O(N2lgN).Research limitations/implications-Due to the limitations of the computer,the sizes of the data sets in this paper are all smaller than 3,000.Therefore,researchers are encouraged to test the proposed algorithm on larger data sets.Originality/value-The new method based on Fib-Dij can greatly improve the speed of Isomap.
