Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infectio...Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks.The channel assignment problem is equivalent to the generalized graph-coloring problem which is a NP-complete problem.We further present a meta-heuristic Wireless Sensor Network Parallel Tabu Search(WSN-PTS) algorithm,which can optimize global networks with small numbers of iterations.The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.展开更多
We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are give...We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter--radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.展开更多
Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered ...Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.展开更多
Schlieren imaging is a widely used technique to visualize the structure of supersonic flow field,which is usually dominated by shock waves.Precise identification of shock waves in schlieren image provides critical ins...Schlieren imaging is a widely used technique to visualize the structure of supersonic flow field,which is usually dominated by shock waves.Precise identification of shock waves in schlieren image provides critical insights for flow diagnostics,especially for supersonic inlet whose performance is highly associated with that of the whole flight.However,conventional shock wave identification methods have limited accuracy in segmenting the shock wave.To overcome the limitation,we proposed an automated shock wave identification method(SW-Segment)that can attain high resolution and automatic shock wave segmentation by integrating correlation-based feature extraction with graph search.We demonstrated the efficacy of SW-Segment via the identification of shock waves in simulatively and experimentally obtained schlieren image.The results proved that SW-Segment showed a shock wave identification accuracy of 95.24%in the numerical schlieren image and an accuracy of 88.33%in the experimental image,clearly demonstrating its reliability.SW-Segment holds broad applicability for shock wave detection in diverse schlieren imaging scenarios,offering robust data support for flow field analysis and supersonic flight design.展开更多
基金supported by National Key Basic Research Program of China(973 program) under Grant No. 2007CB307101National Natural Science Foundation of China under Grant No.60833002,No.60802016,No.60972010+1 种基金Next Generation Internet of China under Grant No.CNGI-0903-05the Fundamental Research Funds for the Central Universities under Grant No.2009YJS011
文摘Wireless sensor networks are suffering from serious frequency interference.In this paper,we propose a channel assignment algorithm based on graph theory in wireless sensor networks.We first model the conflict infection graph for channel assignment with the goal of global optimization minimizing the total interferences in wireless sensor networks.The channel assignment problem is equivalent to the generalized graph-coloring problem which is a NP-complete problem.We further present a meta-heuristic Wireless Sensor Network Parallel Tabu Search(WSN-PTS) algorithm,which can optimize global networks with small numbers of iterations.The results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.
文摘We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter--radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.
基金supported by the National Natural Science Foundation of China(Grant Nos.61502101 and 61170321)the Natural Science Foundation of Jiangsu Province,China(Grant No.BK20140651)the Research Fund for the Doctoral Program of Higher Education of China(Grant No.20110092110024)
文摘Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.
基金supported by the National Natural Science Foundation of China(Grant Nos.12402336,U20A2070,12025202)the Natural Science Foundation of Jiangsu Province(Grant No.BK20230876)+2 种基金the National High-Level Talent Project(Grant No.YQR23069)the Key Laboratory of Intake and Exhaust Technology,Ministry of Education(Grant No.CEPE2024015)the Key Laboratory of Mechanics and Control for Aerospace Structures(Nanjing University of Aeronautics and Astronautics)(Grant No.MCAS-I-0325K01)。
文摘Schlieren imaging is a widely used technique to visualize the structure of supersonic flow field,which is usually dominated by shock waves.Precise identification of shock waves in schlieren image provides critical insights for flow diagnostics,especially for supersonic inlet whose performance is highly associated with that of the whole flight.However,conventional shock wave identification methods have limited accuracy in segmenting the shock wave.To overcome the limitation,we proposed an automated shock wave identification method(SW-Segment)that can attain high resolution and automatic shock wave segmentation by integrating correlation-based feature extraction with graph search.We demonstrated the efficacy of SW-Segment via the identification of shock waves in simulatively and experimentally obtained schlieren image.The results proved that SW-Segment showed a shock wave identification accuracy of 95.24%in the numerical schlieren image and an accuracy of 88.33%in the experimental image,clearly demonstrating its reliability.SW-Segment holds broad applicability for shock wave detection in diverse schlieren imaging scenarios,offering robust data support for flow field analysis and supersonic flight design.
