Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate...Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.展开更多
Routing, modulation and spectrum allocation in elastic optical networks is a problem aiming at increasing the capacity of the network. Many algorithms such as shortest path algorithm can be used as the routing section...Routing, modulation and spectrum allocation in elastic optical networks is a problem aiming at increasing the capacity of the network. Many algorithms such as shortest path algorithm can be used as the routing section of this problem. The efficiency of these algorithms is partly based on how the cost of each link is defined. In this study, we considered several basic metrics in cost of network links and compared their effects on the network capacity. In particular, the static costs and the dynamic costs were evaluated and compared. For dynamic scenarios, compared to static scenarios, at least one additional factor, the usage of the links, was added. We further considered a new factor that is based on probability of accommodating the signal at a given time in any given link. The results show that, among them, the shortest path algorithm provides the least blocking probability when the cost is a combination of link length and the abovementioned possibility/usage of the link.展开更多
The wireless sensor networks (WSN) are formed by a large number of sensor nodes working together to provide a specific duty. However, the low energy capacity assigned to each node prompts users to look at an important...The wireless sensor networks (WSN) are formed by a large number of sensor nodes working together to provide a specific duty. However, the low energy capacity assigned to each node prompts users to look at an important design challenge such as lifetime maximization. Therefore, designing effective routing techniques that conserve scarce energy resources is a critical issue in WSN. Though, the chain-based routing is one of significant routing mechanisms but several common flaws, such as data propagation delay and redundant transmission, are associated with it. In this paper, we will be proposing an energy efficient technique based on graph theory that can be used to find out minimum path based on some defined conditions from a source node to the destination node. Initially, a sensor area is divided into number of levels by a base station based on signal strength. It is important to note that this technique will always found out minimum path and even alternate path are also saved in case of node failure.展开更多
This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building...This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.展开更多
基金This work was supported by the UK Engineering and Physical Sciences Research Council(grant no.EP/N029496/1,EP/N029496/2,EP/N029356/1,EP/N029577/1,and EP/N029577/2)the joint scholarship of the China Scholarship Council and Queen Mary,University of London(grant no.202006830015).
文摘Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.
文摘Routing, modulation and spectrum allocation in elastic optical networks is a problem aiming at increasing the capacity of the network. Many algorithms such as shortest path algorithm can be used as the routing section of this problem. The efficiency of these algorithms is partly based on how the cost of each link is defined. In this study, we considered several basic metrics in cost of network links and compared their effects on the network capacity. In particular, the static costs and the dynamic costs were evaluated and compared. For dynamic scenarios, compared to static scenarios, at least one additional factor, the usage of the links, was added. We further considered a new factor that is based on probability of accommodating the signal at a given time in any given link. The results show that, among them, the shortest path algorithm provides the least blocking probability when the cost is a combination of link length and the abovementioned possibility/usage of the link.
文摘The wireless sensor networks (WSN) are formed by a large number of sensor nodes working together to provide a specific duty. However, the low energy capacity assigned to each node prompts users to look at an important design challenge such as lifetime maximization. Therefore, designing effective routing techniques that conserve scarce energy resources is a critical issue in WSN. Though, the chain-based routing is one of significant routing mechanisms but several common flaws, such as data propagation delay and redundant transmission, are associated with it. In this paper, we will be proposing an energy efficient technique based on graph theory that can be used to find out minimum path based on some defined conditions from a source node to the destination node. Initially, a sensor area is divided into number of levels by a base station based on signal strength. It is important to note that this technique will always found out minimum path and even alternate path are also saved in case of node failure.
文摘This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.
