A Flexible Stochastic Automaton-Based Algorithm for Network Self-Partitioning. (2008)

• Record Type: Journal Article
• Authors: Wan Wan, Yan Yan; Roy Roy, Sandip Sandip; Saberi Saberi, Ali Ali; Lesieutre Lesieutre, Bernard Bernard
• Is Part Of: International journal of distributed sensor networks. Volume 4:Number 3(2008)
• Page Start: 223
• Page End: 246
• Publication Date: 2008
• Subjects: Partitioning; Distributed Partitioning; Islanding; Stochastic Automata; Sensor networks -- Periodicals; Intelligent agents (Computer software) -- Periodicals; Multisensor data fusion -- Periodicals; 681.2
• DOI: 10.1080/15501320701260063
• Languages: English
• ISSNs: 1550-1329

Abstract

Abstract : This article proposes a flexible and distributed stochastic automaton-based network partitioning algorithm that is capable of finding the optimal k-way partition with respect to a broad range of cost functions, and given various constraints, in directed and weighted graphs. Specifically, we motivate the distributed partitioning (self-partitioning) problem, introduce the stochastic automaton-based partitioning algorithm, and show that the algorithm finds the optimal partition with probability 1 for a large class of partitioning tasks. Also, a discussion of why the algorithm can be expected to find good partitions quickly is included, and its performance is further illustrated through examples. Finally, applications to mobile/sensor classification in ad hoc networks, fault-isolation in electric power systems, and control of autonomous vehicle teams are pursued in detail.