Weighted Combinatorial Laplacian and its Application to Coverage Repair in Sensor Networks

Graphs have been used extensively to model networks of robot or sensor networks [1, 2]. One of the fundamental algebraic tools relevant to graphs is the graph Laplacian matrix, the spectrum of which encodes the connectivity of the graph [3]. In weighted graphs, one assigns non-negative, real-valued weights or importance to each edge of the graph, with a zero weight on an edge being equivalent to the edge being non-existent, thus allowing a continuum between different graph topologies. Furthermore, for robot or mobile sensor networks, the real-valued weights naturally correspond to the separation or distance between pairs of agents (with the weights being inversely related to the distances so that agents that are closer to each other are strongly connected, while agents that are farther from each other are weakly connected). A weighted graph Laplacian can be constructed accordingly, and real-valued optimization objectives can be formulated to control the connectivity of a network [4, 5].