Synchronizing Finite State Machine Controllers for Distribution Systems | Consortium for Embedded Systems | SIU

Abstract: We consider a distribution system in which a set of suppliers (or “generators”) are connected to a set of consumers (or “loads”) through a network of switches. Each of the generators and switches is controlled by a Finite State Machine (FSM) that specifies the allowed states and the transitions among them. For fault tolerance and/or load balancing purposes, the network has to be occasionally reconfigured so that the supply to the consumers continues uninterrupted. The trivial approach is to view the local FSMs as one global FSM that responds accordingly to the event requiring the reconfiguration. The problem with this centralized approach is that the complexity becomes unmanageable as the size of the system scales up. In this project we propose a decentralized scheme where the individual FSMs are synchronized through message passing in a distributed manner in order to arrive at a consensus on how to respond safely to each reconfiguration triggering event. The scheme is based on Bipartite Graph Matching and Knapsack heuristics.

Problem: We consider an abstract model of a distribution system in which a set of suppliers (or “generators”) are connected to a set of consumers (or “loads”) through a network of switches. Each of the generators and switches is controlled by a Finite State Machine (FSM) that specifies the allowed states and the transitions among them. Such a system needs to be reconfigured for a variety of reasons such as load balancing (generators should normally drive approximately the same number of loads), or fault tolerance (if a generator fails, the loads it supplied must be supplied from other generators). We want to be able to do such reconfigurations dynamically in a distributed/decentralized/asynchronous manner.

Rationale / Approach: The local FSM controllers must be able to respond to each reconfiguration triggering event in a decentralized/asynchronous manner through message passing. The complexity of a centralized global FSM is impractical even for moderately large (30 nodes) distribution systems. The proposed work aims to provide such a decentralized solution using as a case study a power supply system for avionics. We will develop synchronization, consensus, and reconfiguration procedures based on Bipartite Graph Matching and Knapsack heuristics.

Novelty: Existing results remain at the theoretical/generic level and may not even be directly applicable as -within our knowledge- no experimental verification has been given in the literature for specific systems. The proposed work will develop a practical methodology for a real-world industrial problem, namely the control/reconfiguration of the power supply system of an aircraft.

Potential Member Company Benefits: The studied model of a distribution system with a set of suppliers (or “generators”) connected to a set of consumers (or “loads”) through a network of switches is general enough that it can be useful in many situations. Also the reconfiguration triggering events considered are general enough to model different requirements such as reconfiguration due to a failure or reconfiguration due to load balancing.

Deliverables for the proposed year: (1).Comprehensive report on the DS modelling and synchronization, consensus, and reconfiguration procedures for the avionics power supply system. (2) Software prototype tool of the developed model.

Milestones for the proposed year: (1) Development of the Distribution System (DS) and the FSM for each controller and the consensus and reconfiguration order strategies. (2) Implementation of Bipartite Graph Matching and Knapsack heuristics. (3)Simulation of different scenarios and efficiency evaluation. (4) Refinement of the DS formulation and simulation package and writing of the comprehensive project report.