Studies of quantum metrology have shown that the use of many-body entangled states can lead to an enhancement in sensitivity when compared with unentangled states. In this paper, we quantify the metrological advantage of entanglement in a setting where the measured quantity is a linear function of parameters individually coupled to each qubit. We first generalize the Heisenberg limit to the measurement of nonlocal observables in a quantum network, deriving a bound based on the multiparameter quantum Fisher information. We then propose measurement protocols that can make use of Greenberger-Horne-Zeilinger (GHZ) states or spin-squeezed states and show that in the case of GHZ states the protocol is optimal, i.e., it saturates our bound. We also identify nanoscale magnetic resonance imaging as a promising setting for this technology.