Milan Bradonjić
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Milan Bradonjić has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Allon G. Percus
Claremont Graduate University Institute of Mathematical Sciences Claremont CA USA
3 shared publications - Aric Hagberg
Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, USA
2 shared publications - Eddie Kohler
Harvard University
1 shared publication - Loukas Lazos
Department of Electrical, Computer Engineering, University of Arizona, Tucson, AZ, USA
1 shared publication - Nicolas Hengartner
Theoretical Biology and Biophysics Group, Los Alamos National Laboratory, Los Alamos, NM 87545
1 shared publication - Rafail Ostrovsky
UCLA
1 shared publication
Latest Publications
- Open Access
Near-Optimal Radio Use For Wireless Network Synchronization
We consider the model of communication where wireless devices can either switch their radios off to save energy, or switch their radios on and engage in communication. We distill a clean theoretical formulation of this problem of minimizing radio use and present near-optimal solutions. Our base model ignores issues of communication interference, although we also extend the model to handle this requirement. We assume that nodes intend to communicate periodically, or according to some time-based schedule. Clearly, perfectly synchronized devices could switch their radios on for exactly the minimum periods required by their joint schedules. The main challenge in the deployment of wireless networks is to synchronize the devices' schedules, given that their initial schedules may be offset relative to one another (even if their clocks run at the same speed). We significantly improve previous results, and show optimal use of the radio for two processors and near-optimal use of the radio for synchronization of an arbitrary number of processors. In particular, for two processors we prove deterministically matching $\Theta(\sqrt{n})$ upper and lower bounds on the number of times the radio has to be on, where $n$ is the discretized uncertainty period of the clock shift between the two processors. (In contrast, all previous results for two processors are randomized.) For $m=n^\beta$ processors (for any $\beta < 1$) we prove $\Omega(n^{(1-\beta)/2})$ is the lower bound on the number of times the radio has to be switched on (per processor), and show a nearly matching (in terms of the radio use) $\~{O}(n^{(1-\beta)/2})$ randomized upper bound per processor, with failure probability exponentially close to 0. For $\beta \geq 1$ our algorithm runs with at most $poly-log(n)$ radio invocations per processor. Our bounds also hold in a radio-broadcast model where interference must be taken into account.Open AccessNear-Optimal Radio Use For Wireless Network Synchronization
We consider the model of communication where wireless devices can either switch their radios off to save energy, or switch their radios on and engage in communication. We distill a clean theoretical formulation of this problem of minimizing radio use and present near-optimal solutions. Our base model ignores issues of communication interference, although we also extend the model to handle this requirement. We assume that nodes intend to communicate periodically, or according to some time-based schedule. Clearly, perfectly synchronized devices could switch their radios on for exactly the minimum periods required by their joint schedules. The main challenge in the deployment of wireless networks is to synchronize the devices' schedules, given that their initial schedules may be offset relative to one another (even if their clocks run at the same speed). We significantly improve previous results, and show optimal use of the radio for two processors and near-optimal use of the radio for synchronization of an arbitrary number of processors. In particular, for two processors we prove deterministically matching $\Theta(\sqrt{n})$ upper and lower bounds on the number of times the radio has to be on, where $n$ is the discretized uncertainty period of the clock shift between the two processors. (In contrast, all previous results for two processors are randomized.) For $m=n^\beta$ processors (for any $\beta < 1$) we prove $\Omega(n^{(1-\beta)/2})$ is the lower bound on the number of times the radio has to be switched on (per processor), and show a nearly matching (in terms of the radio use) $\~{O}(n^{(1-\beta)/2})$ randomized upper bound per processor, with failure probability exponentially close to 0. For $\beta \geq 1$ our algorithm runs with at most $poly-log(n)$ radio invocations per processor. Our bounds also hold in a radio-broadcast model where interference must be taken into account. - 20 June 2011
- Published by Elsevier in Ad Hoc Networks
- Vol. 10 (1) , 75-94
Graph-based criteria for spectrum-aware clustering in cognitive radio networks
- 20 June 2011
- Published by Elsevier in Ad Hoc Networks
- Vol. 10 (1) , 75-94
Graph-based criteria for spectrum-aware clustering in cognitive radio networks
- Open Access
Component Evolution in General Random Intersection Graphs
Random intersection graphs (RIGs) are an important random structure with applications in social networks, epidemic networks, blog readership, and wireless sensor networks. RIGs can be interpreted as a model for large randomly formed non-metric data sets. We analyze the component evolution in general RIGs, and give conditions on existence and uniqueness of the giant component. Our techniques generalize existing methods for analysis of component evolution: we analyze survival and extinction properties of a dependent, inhomogeneous Galton-Watson branching process on general RIGs. Our analysis relies on bounding the branching processes and inherits the fundamental concepts of the study of component evolution in Erd\H{o}s-R\'enyi graphs. The major challenge comes from the underlying structure of RIGs, which involves its both the set of nodes and the set of attributes, as well as the set of different probabilities among the nodes and attributes.
Open AccessComponent Evolution in General Random Intersection Graphs
Random intersection graphs (RIGs) are an important random structure with applications in social networks, epidemic networks, blog readership, and wireless sensor networks. RIGs can be interpreted as a model for large randomly formed non-metric data sets. We analyze the component evolution in general RIGs, and give conditions on existence and uniqueness of the giant component. Our techniques generalize existing methods for analysis of component evolution: we analyze survival and extinction properties of a dependent, inhomogeneous Galton-Watson branching process on general RIGs. Our analysis relies on bounding the branching processes and inherits the fundamental concepts of the study of component evolution in Erd\H{o}s-R\'enyi graphs. The major challenge comes from the underlying structure of RIGs, which involves its both the set of nodes and the set of attributes, as well as the set of different probabilities among the nodes and attributes.
- 3 January 2009
- Published by Society for Industrial & Applied Mathematics (SIAM)
- p. 11-16
Coloring Geographical Threshold Graphs
- 3 January 2009
- Published by Society for Industrial & Applied Mathematics (SIAM)
- p. 11-16
Coloring Geographical Threshold Graphs
- 1 January 2008
- Published by Internet Mathematics in Internet Mathematics
- Vol. 5 (1) , 113-139
The Structure of Geographical Threshold Graphs
By Allon G. Percus, Milan Bradonjić & 1 more. We analyze the structure of random graphs generated by the geographical threshold model. The model is a generalization of random geometric...
- 1 January 2008
- Published by Internet Mathematics in Internet Mathematics
- Vol. 5 (1) , 113-139
The Structure of Geographical Threshold Graphs
By Allon G. Percus, Milan Bradonjić & 1 more. We analyze the structure of random graphs generated by the geographical threshold model. The model is a generalization of random geometric...