Optimization of communication and coverage in classes of distributed systems.

摘要

This dissertation deals with two different types of optimization problems for networked systems. They are (1) minimization of communications in distributed discrete event systems and (2) maximization of coverage in wireless networked systems.; The problem of minimizing communications in distributed systems is considered in a discrete-event formalism where the system is modeled as a finite-state automaton. There is a set of n communicating agents observing the behavior of the system for purposes of control or diagnosis. A set of communication policies for the agents is said to be minimal if no communication can be removed without affecting the correctness of the solution. A more general formulation of the communication structure than prior works on this problem is considered. Under an assumption on the absence of cycles (other than self-loops) in the system model, an algorithm that computes a set of minimal communication policies in polynomial-time in the number of states of the system is presented. Moreover, the special case of a central station together with other local agents observing the behavior of the system is considered. The central station needs to know exactly the state of the system, whereas local agents need to disambiguate certain pre-specified pairs of states. Communication occurs only between the central station and local agents but not among local agents. For this case, an algorithm that computes a set of minimal communication policies in polynomial-time in all input variables is obtained.; For the purpose of verification of potential results in minimal communication problems, a polynomial algorithm is developed for tabulating indistinguishable states in finite state automata with partially observable transitions.; The problem of maximization of coverage in wireless networked systems is considered from the viewpoint of positioning circles, whose centers are mobile nodes, in a given region in order to maximize the covered area. A procedure to calculate the rate of change of total covered area in terms of' the movement direction of an individual node is presented. The optimum movement direction is achieved when a node moves in the direction corresponding to the maximum rate of change of total covered area. A method to calculate optimum movement direction of a node as a function of positions of nodes and boundary of the region is developed. A nonlinear programming algorithm for positioning nodes based on the calculation of optimum movement direction is presented.