Distributed coordination maximization over networks: A stochastic approximation approach

In various online/offline networked environments, it is very popular that the system can benefit from coordinating actions of two interacting nodes, but incur some cost due to such coordination. Examples include a wireless sensor networks with duty cycling, where a sensor node consumes a certain amount of energy when it is awake, but a coordinated operation of sensors enables some meaningful tasks, e.g., sensed data forwarding, collaborative sensing of a phenomenon, or efficient decision of further sensing actions. In this paper, we formulate an optimization problem that captures the amount of coordination gain at the cost of node activation over networks. This problem is challenging since the target utility is a function of the long-term time portion of the inter-coupled activations of two adjacent nodes, and thus a standard Lagrange duality theory is hard to apply to obtain a distributed decomposition as in the standard NUM (Network Utility Maximization). We propose a fully-distributed algorithm that requires only one-hop message passing. Our approach is inspired by a control of Ising model in statistical physics, and the proposed algorithm is motivated by a stochastic approximation method that runs a Markov chain incompletely over time, but provably guarantees its convergence to the optimal solution. We validate our theoretical findings on convergence and optimality through extensive simulations under various scenarios.