@article{kwak_lee_eun_2016, title={A High-Order Markov-Chain-Based Scheduling Algorithm for Low Delay in CSMA Networks}, volume={24}, ISSN={["1558-2566"]}, DOI={10.1109/tnet.2015.2458703}, abstractNote={Recently, several CSMA algorithms based on the Glauber dynamics model have been proposed for wireless link 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 that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively “decorrelating” the link state process (and thus resolves link starvation). Our simulation results demonstrate that the delay under our algorithm can be reduced by a factor of 20 in some cases, compared to the standard Glauber-dynamics-based CSMA algorithm.}, number={4}, journal={IEEE-ACM TRANSACTIONS ON NETWORKING}, author={Kwak, Jaewook and Lee, Chul-Ho and Eun, Do Young}, year={2016}, month={Aug}, pages={2278–2290} }
 @inproceedings{kwak_eun_2016, title={An antithetic coupling approach to multi-chain based CSMA scheduling algorithms}, DOI={10.1109/infocom.2016.7524595}, abstractNote={In recent years, a suite of Glauber dynamics-based CSMA algorithms have attracted great attention due to their simple, distributed implementations with guaranteed throughput-optimality. However, these algorithms often suffer from poor delay performance and the starvation problem. Among several attempts to improve the delay performance, a remarkable improvement has recently been made in a class of CSMA algorithms that utilize multiple instances of the algorithm (or Markov chains). In this paper, we develop a new approach via an antithetic coupling (AC) method, which can further improve the delay performance of those that virtually emulate multiple chains. The key enabler of utilizing AC method lies in our skilful choice of manipulating the driving sequences of random variables that govern the evolution of schedule instances, in such a way that those multiple instances of chains become negatively correlated as oppose to having them run independently. This contributes faster change of the link state, rendering it more like a periodic process and thus leading to better queueing performance. We rigorously establish an ordering relationship for the effective bandwidth of each net-input process to the queue, between our proposed algorithm (AC-CSMA) and other state-of-the-art existing algorithms in the literature, under a mild set of assumptions. The proposed algorithm involves very simple modification onto existing CSMA-based algorithms, and can be implemented in a fully distributed manner without any additional message overhead. Our extensive simulation results also confirm that AC-CSMA always delivers better queueing performance over a variety of network scenarios.}, booktitle={IEEE INFOCOM 2016 - the 35th annual IEEE international Conference on Computer Communications}, author={Kwak, J. and Eun, D. Y.}, year={2016} }
 @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} }
 @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} }