Note on the capacity and geometric realizability of combinatorial mobile sensor networks

Abstract

We develop the mathematical theory of a model, constructed by C. Gu, I. Downes, O. Gnawali, and L. Guibas, of networks that diffuse continuously acquired information from mobile sensor nodes. We improve estimates of the expectation and variance of capacity of their model of restricted combinatorial mobile sensor networks (RCMSN) and geometric mobile sensor networks (GMSN), and give the maximum capacity of a variant of GMSN. We also show that the problem of deciding when an RCMSN is generated from a GMSN is NP-Hard, while a simple variant is solvable in polynomial time.

arXiv comment10 pages, 5 figures. For additional results, see the previous version. Thm. 22 is incorrect in the previous version