A Caltech Library Service

Index-based sampling policies for tracking dynamic networks under sampling constraints

He, Ting and Anandkumar, Animashree and Agrawal, Dakshi (2011) Index-based sampling policies for tracking dynamic networks under sampling constraints. In: 2011 Proceedings IEEE INFOCOM. IEEE , Piscataway, NJ, pp. 1233-1241. ISBN 978-1-4244-9919-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We consider the problem of tracking the topology of a large-scale dynamic network with limited monitoring resources. By modeling the dynamics of links as independent ON-OFF Markov chains, we formulate the problem as that of maximizing the overall accuracy of tracking link states when only a limited number of network elements can be monitored at each time step. We consider two forms of sampling policies: link sampling, where we directly observe the selected links, and node sampling, where we observe states of the links adjacent to the selected nodes. We reduce the link sampling problem to a Restless Multi-armed Bandit (RMB) and prove its indexability under certain conditions. By applying the Whittle's index policy, we develop an efficient link sampling policy with methods to compute the Whittle's index explicitly. Under node sampling, we use a linear programming (LP) formulation to derive an extended policy that can be reduced to determining the nodes with maximum coverage of the Whittle's indices. We also derive performance upper bounds in both sampling scenarios. Simulations show the efficacy of the proposed policies. Compared with the myopic policy, our solution achieves significantly better tracking performance for heterogeneous links.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. The first and the third authors are supported in part by the U.S. National Institute of Standards and Technology under Agreement Number 60NANB10D003. The second author is supported in part by a MURI funded through ARO Grant W911NF-06-1-0076.
Funding AgencyGrant Number
National Institute of Standards and Technology (NIST)60NANB10D003
Army Research Office (ARO)W911NF-06-1-0076
Subject Keywords:Network sampling, network topology tracking, restless multi-armed bandits, Whittle’s index policy
Record Number:CaltechAUTHORS:20170925-091212425
Persistent URL:
Official Citation:T. He, A. Anandkumar and D. Agrawal, "Index-based sampling policies for tracking dynamic networks under sampling constraints," 2011 Proceedings IEEE INFOCOM, Shanghai, 2011, pp. 1233-1241. doi: 10.1109/INFCOM.2011.5934904 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81799
Deposited By: Tony Diaz
Deposited On:25 Sep 2017 17:00
Last Modified:03 Oct 2019 18:47

Repository Staff Only: item control page