PCFG Based Synthetic Mobility Trace Generation
PCFG Based Synthetic Mobility Trace Generation
复制标题
基于 PCFG 的合成移动轨迹生成
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Szymański
中科院分区：
文献类型：
--
作者：
S. Geyik;E. Bulut;B. Szymański
提出了一种基于概率上下文无关文法（PCFG）的移动轨迹生成方法。PCFG是上下文无关语法的推广，其中每个产生式规则都增加了在句子生成期间应用该产生式的概率。一个简洁的PCFG可以从给定的真实的世界的轨迹从实际的移动的节点的行为来推断。产生的语法可用于生成模仿移动的节点行为的任意长度的序列。当通过仿真测试用于移动的网络的新协议设计时，这是重要的。在本文中，我们描述了开发的方法来构建这样的语法从训练数据移动历史）。我们还讨论了如何生成合成数据与一个已经构造的语法。我们提出了两个真实的数据集上的实验结果，测量与合成的实际痕迹的相似性。我们比较我们的语法为基础的方法，2级马尔可夫模型为基础的跟踪生成方法。结果表明，基于语法的方法工程作为一个很好的压缩方法的实际数据。在许多指标上，从PCFG生成的合成数据比马尔可夫模型生成的数据更好地匹配训练数据。
This paper introduces a novel method of generating mobility traces based on Probabilistic Context Free Grammars (PCFGs). A PCFG is a generalization of a context free grammar in which each production rule is augmented with a probability with which this production is applied during sentence generation. A concise PCFG can be inferred from the given real world trace collected from the actual mobile node behaviors. The resulting grammar can be used to generate sequences of arbitrary length mimicking the mobile node behavior. This is important when new protocol designs for mobile networks are tested by simulation. In the paper, we describe the methods developed to construct such grammars from training data mobility history). We also discuss how to generate the synthetic data with an already constructed grammar. We present the experimental results on two real data sets, measuring similarity of the actual traces with the synthetic ones. We compare our grammar based method to a 2-level Markov Model based trace generation method. The results demonstrate that the grammar based approach works as an excellent compression method for the actual data. On many metrics, the synthetic data generated from the PCFG match the training data much better than the one generated by the Markov Model.