@article{lee_eun_2016, title={Exploiting Heterogeneity for Improving Forwarding Performance in Mobile Opportunistic Networks: An Analytic Approach}, volume={15}, ISSN={["1558-0660"]}, DOI={10.1109/tmc.2015.2407406}, abstractNote={Heterogeneity arises in a wide range of scenarios in mobile opportunistic networks and is one of the key factors that govern the performance of forwarding algorithms. While the heterogeneity has been empirically investigated and exploited in the design of new forwarding algorithms, it has been typically ignored or marginalized when it comes to rigorous performance analysis of such algorithms. In this paper, we develop an analytical framework to quantify the performance gain achievable by exploiting the heterogeneity in mobile nodes' contact dynamics. In particular, we derive a delay upper bound of a heterogeneity-aware static forwarding policy per each given number of message copies and obtain its closed-form expression, which enables our quantitative study on the benefit of leveraging underlying heterogeneity structure in the design of forwarding algorithms. In addition, we develop a dynamic forwarding policy that performs as an extension of the static forwarding policy while proven to improve the delay performance. We then demonstrate that only a small fraction of total (unlimited) message copies, via both static and dynamic forwarding policies, are enough under various heterogeneous network settings to achieve the same delay as that obtained using the unlimited message copies when the networks become homogeneous. We also show that, given the same number of message copies, our dynamic forwarding policy significantly outperforms the `homogeneous-optimal' forwarding policy (up to about 50 percent improvement in the delay performance), especially when the number of message copies allowed in the networks is small.}, number={1}, journal={IEEE TRANSACTIONS ON MOBILE COMPUTING}, author={Lee, Chul-Ho and Eun, Do Young}, year={2016}, month={Jan}, pages={150–162} }
 @article{lee_kwak_eun_2016, title={Towards Distributed Optimal Movement Strategy for Data Gathering in Wireless Sensor Networks}, volume={27}, ISSN={["1558-2183"]}, DOI={10.1109/tpds.2015.2407893}, abstractNote={In this paper, we address how to design a distributed movement strategy for mobile collectors, which can be either physical mobile agents or query/collector packets periodically launched by the sink, to achieve successful data gathering in wireless sensor networks. Formulating the problem as general random walks on a graph composed of sensor nodes, we analyze how much data can be successfully gathered in time under any Markovian random-walk movement strategies for mobile collectors moving over a graph (or network), while each sensor node is equipped with limited buffer space and data arrival rates are heterogeneous over different sensor nodes. In particular, from the analysis, we obtain the optimal movement strategy among a class of Markovian strategies so as to minimize the data loss rate over all sensor nodes, and explain how such an optimal movement strategy can be made to work in a distributed fashion. We demonstrate that our distributed optimal movement strategy can lead to about two times smaller loss rate than a standard random walk strategy under diverse scenarios. In particular, our strategy results in up to 70 percent cost savings for the deployment of multiple collectors to achieve the target data loss rate than the standard random walk strategy.}, number={2}, journal={IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS}, author={Lee, Chul-Ho and Kwak, Jaewook and Eun, Do Young}, year={2016}, month={Feb}, pages={574–584} }
 @article{lee_eun_2015, title={Characterizing link connectivity in opportunistic networks}, journal={Opportunistic Mobile Social Networks}, author={Lee, C. H. and Eun, D. Y.}, year={2015}, pages={71–97} }
 @inproceedings{xu_lee_eun_2014, title={A general framework of hybrid graph sampling for complex network analysis}, DOI={10.1109/infocom.2014.6848229}, abstractNote={Being able to capture the properties of massive real graphs and also greatly reduce data scale and processing complexity, graph sampling techniques provide an efficient tool for complex network analysis. Random walk-based sampling has become popular to obtain asymptotically uniform samples in the recent literature. However, it produces highly correlated samples and often leads to poor estimation accuracy in sampling large networks. Another widely-used approach is to launch random jump by querying randomly generated user/node ID, but also has the drawback of unexpected cost when the ID space is sparsely populated. In this paper, we develop a hybrid graph sampling framework that inherits the benefit of returning immediate samples from random walk-based crawling, while incorporating the advantage of reducing the correlation in the obtained samples from random jump. We aim to strike the right balance between random jump and crawling by analyzing the resulting asymptotic variance of an estimator of any graph nodal property, in order to give guidelines on the design of better graph sampling methods. We also provide simulation results on real network (graph) to confirm our theoretical findings.}, booktitle={2014 proceedings ieee infocom}, author={Xu, X. and Lee, C. H. and Eun, D. Y.}, year={2014}, pages={2795–2803} }
 @inproceedings{kwak_lee_eun_2014, title={A high-order Markov chain based scheduling algorithm for low delay in CSMA networks}, DOI={10.1109/infocom.2014.6848103}, abstractNote={Recently, several CSMA algorithms based on the Glauber dynamics model have been proposed for multihop wireless scheduling, as viable solutions to achieve the throughput optimality, yet simple to implement. However, their delay performance still remains unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show in theory and simulation that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively `de-correlating' the link state process (and thus resolves link starvation). Our extensive simulations demonstrate that the delay under our algorithm can be often reduced by a factor of 20 over a wide range of scenarios, compared to the standard Glauber-dynamics-based CSMA algorithm.}, booktitle={2014 proceedings ieee infocom}, author={Kwak, J. and Lee, C. H. and Eun, D. Y.}, year={2014}, pages={1662–1670} }
 @inproceedings{lee_kwak_eun_2013, title={Characterizing link connectivity for opportunistic mobile networking: Does mobility suffice?}, DOI={10.1109/infcom.2013.6567009}, abstractNote={With recent drastic growth in the number of users carrying smart mobile devices, it is not hard to envision opportunistic ad-hoc communications taking place with such devices carried by humans. This leads to, however, a new challenge to the conventional link-level metrics, solely defined based on user mobility, such as inter-contact time, since there are many constraints including limited battery power that prevent the wireless interface of each user from being always `on' for communication. By taking into account the process of each user's availability jointly with mobility-induced contact/inter-contact process, we investigate how each of them affects the link-level connectivity depending on their relative operating time scales. We then identify three distinct regimes in each of which (1) the so-called impact of mobility on network performance prevails; (2) such impact of mobility disappears or its extent is not that significant; (3) the user availability process becomes dominant. Our findings not only caution that mobility alone is not sufficient to characterize the link-level dynamics, which in turn can lead to highly misleading results, but also suggest the presence of many uncharted research territories for further exploration.}, booktitle={2013 proceedings ieee infocom}, author={Lee, C. H. and Kwak, J. and Eun, D. Y.}, year={2013}, pages={2076–2084} }
 @article{lee_eun_2013, title={On the Forwarding Performance under Heterogeneous Contact Dynamics in Mobile Opportunistic Networks}, volume={12}, ISSN={["1558-0660"]}, DOI={10.1109/tmc.2012.84}, abstractNote={In this paper, we focus on how the heterogeneous contact dynamics of mobile nodes impact the performance of forwarding algorithms in mobile opportunistic networks (MONs). To this end, we consider two representative heterogeneous network models, each of which captures heterogeneity among node pairs (individual) and heterogeneity in underlying environment (spatial), respectively, and examine the full extent of difference in delay performance they cause on forwarding algorithms through formal stochastic comparisons. We first show that these heterogeneous models correctly capture non-Poisson contact dynamics observed in real traces. We then rigorously establish stochastic/convex ordering relationships on the delay performance of direct forwarding and multicopy two-hop relay protocol under these heterogeneous models and the corresponding homogeneous model, all of which have the same average intercontact time of a random pair of nodes. In particular, we demonstrate that the heterogeneous models predict an entirely opposite ordering relationship in delay performance depending on which of the two heterogeneity structures is captured. We also provide simulation results including the delay performance of epidemic routing protocol to support the analytical findings. Our results thus suggest that the heterogeneity in mobile nodes' contact dynamics should be properly taken into account for the performance evaluation of forwarding algorithms. Our results will also be useful for better design of forwarding algorithms correctly exploiting the heterogeneity structure.}, number={6}, journal={IEEE TRANSACTIONS ON MOBILE COMPUTING}, author={Lee, Chul-Ho and Eun, Do Young}, year={2013}, month={Jun}, pages={1107–1119} }
 @inproceedings{lee_eun_2011, title={Smart sleep: sleep more to reduce delay in duty-cycled wireless sensor networks}, DOI={10.1109/infcom.2011.5935237}, abstractNote={A simple random walk (SRW) has been considered as an effective forwarding method for many applications in wireless sensor networks (WSNs) due to its desirable properties. However, a critical downside of SRW - slow diffusion or exploration over the space, typically leads to longer packet delay and undermines its own benefits. Such slow-mixing problem becomes even worse under random duty cycling adopted for energy conservation. In this paper, we study how to overcome this problem without any sacrifice or tradeoff, and propose a simple modification of random duty cycling, named Smart Sleep, which achieves more power-saving as well as faster packet diffusion (or smaller delay) while retaining the benefits of SRW. We also introduce a class of p-backtracking random walks and establish its properties to analytically explain the fast packet diffusion induced by Smart Sleep. We further obtain a necessary condition to achieve an optimal performance under our Smart Sleep, and finally demonstrate remarkable performance improvement via independent simulation results over various network topologies.}, booktitle={2011 proceedings ieee infocom}, author={Lee, C. H. and Eun, D. Y.}, year={2011}, pages={611–615} }
 @inproceedings{lee_eun_2010, title={A Distributed Wake-up Scheduling for Opportunistic Forwarding in Wireless Sensor Networks}, DOI={10.1109/glocom.2010.5683254}, abstractNote={In wireless sensor networks (WSNs), sensor nodes are typically subjected to energy constraints and often prone to topology changes. While \emph{duty cycling} has been widely used for energy conservation in WSNs, \emph{random walks} have been popular for many delay-tolerant applications in WSNs due to their many inherent desirable properties. In this paper, we consider an opportunistic forwarding under an asynchronous and heterogeneous duty cycling. We first show that its resulting packet trajectory can be interpreted as a continuous-time random walk, and then provide an analytical formula for its end-to-end delay. Since the extremely large end-to-end delay is still undesirable even for most delay-tolerant applications, we develop a \emph{distributed} wake-up scheduling algorithm in which each node autonomously adjusts its (heterogeneous) wake-up rate based \emph{only} on its own degree information so as to improve the worst-case end-to-end delay. In particular, we prove that our algorithm outperforms pure homogeneous duty cycling, where every node uses the same wake-up rate, in its guaranteed asymptotic upper bound of the worst-case delay for \emph{any} graph. In addition, we show that our proposed algorithm brings out more than $35\%$ performance improvement on average when compared with pure homogeneous duty cycling, under various settings of random geometric graphs via numerical evaluations and independent simulation results.}, booktitle={2010 ieee global telecommunications conference globecom 2010}, author={Lee, C. H. and Eun, D. Y.}, year={2010} }
 @article{kim_lee_eun_2010, title={Superdiffusive Behavior of Mobile Nodes and Its Impact on Routing Protocol Performance}, volume={9}, ISSN={["1558-0660"]}, DOI={10.1109/TMC.2009.124}, abstractNote={Mobility is the most important component in mobile ad hoc networks (MANETs) and delay-tolerant networks (DTNs). In this paper, we first investigate numerous GPS mobility traces of human mobile nodes and observe superdiffusive behavior in all GPS traces, which is characterized by a ¿faster-than-linear¿ growth rate of the mean square displacement (MSD) of a mobile node. We then investigate a large amount of access point (AP) based traces, and develop a theoretical framework built upon continuous time random walk (CTRW) formalism, in which one can identify the degree of diffusive behavior of mobile nodes even under possibly heavy-tailed pause time distribution, as in the case of reality. We study existing synthetic models and trace-based models in terms of the capability of producing various degrees of diffusive behavior, and use a set of Levy walk models due to its simplicity and flexibility. In addition, we show that diffusive properties make a huge impact on contact-based metrics and the performance of routing protocols in various scenarios, and that existing models such as random waypoint, random direction model, or Brownian motion lead to overly optimistic or pessimistic results when diffusive properties are not properly captured. Our work in this paper, thus, suggests that the diffusive behavior of mobile nodes should be correctly captured and taken into account for the design and comparison study of network protocols.}, number={2}, journal={IEEE TRANSACTIONS ON MOBILE COMPUTING}, author={Kim, Sungwon and Lee, Chul-Ho and Eun, Do Young}, year={2010}, month={Feb}, pages={288–304} }
 @inproceedings{lee_eun_2009, title={Heterogeneity in contact dynamics: Helpful or harmful to forwarding algorithms in DTNs?}, booktitle={2009 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless}, author={Lee, C. H. and Eun, D. Y.}, year={2009}, pages={72–81} }