A tale of two graph models: a case study in wireless sensor networks
A tale of two graph models: a case study in wireless sensor networks
复制标题
两种图模型的故事：无线传感器网络的案例研究
DOI：
10.1007/s00165-021-00558-z
复制
发表时间：
2021
影响因子：
1
通讯作者：
Archibald B
中科院分区：
文献类型：
--
作者：
Archibald B
由于高度动态的环境，设计和推理无线传感器网络等复杂系统非常困难：传感器是异构的、电池供电的和移动的。虽然形式化建模可以提供严格的设计/推理机制，但它们通常被认为难以使用。基于图形重写的建模技术通过提供直观、灵活和图解的建模形式来提高可用性，其中图形结构表达实体之间的关系，而重写机制允许模型演化。两种主要的基于图的形式是图转换系统（GTS）和双向反应系统（BRS）。虽然两者都使用相似的底层结构，但它们在建模中的使用方式却截然不同。为了更深入地了解 GTS 和 BRS，并指导未来的建模、理论和工具开发，在本经验报告中，我们比较了 GTS 和 BRS 在应用于 WSN 拓扑控制时的实际建模能力和风格。为了展示模型的价值，我们描述了如何以两种形式进行分析。这些方法的比较表明，尽管这两种形式不同，但从理论和实践建模的角度来看，它们在无线传感器网络中的拓扑控制建模方面都取得了成功。我们发现，GTS 虽然具有一小组实体和转换规则，但依赖于实体属性、基于属性/变量附加条件的规则应用以及命令式控制流单元。另一方面，BRS 需要大量实体，以便直接在模型中对属性进行编码（通过嵌套）并提供标记功能，该功能在与规则优先级结合时实现控制流。形式主义之间仍然存在有前途的研究映射技术，以进一步实现灵活和富有表现力的建模。
Designing and reasoning about complex systems such as wireless sensor networks is hard due to highly dynamic environments: sensors are heterogeneous, battery-powered, and mobile. While formal modelling can provide rigorous mechanisms for design/reasoning, they are often viewed as difficult to use. Graph rewrite-based modelling techniques increase usability by providing an intuitive, flexible, anddiagrammaticform of modelling in which graph-like structures express relationships between entities while rewriting mechanisms allow model evolution. Two major graph-based formalisms are Graph Transformation Systems (GTS) and Bigraphical Reactive Systems (BRS). While both use similar underlying structures, how they are employed in modelling is quite different. To gain a deeper understanding of GTS and BRS, and to guide future modelling, theory, and tool development, in this experience report we compare thepracticalmodelling abilities and style of GTS and BRS when applied to topology control in WSNs. To show the value of the models, we describe how analysis may be performed in both formalisms. A comparison of the approaches shows that although the two formalisms are different, from both a theoretical and practical modelling standpoint, they are each successful in modelling topology control in WSNs. We found that GTS, while featuring a small set of entities and transformation rules, relied on entity attributes, rule application based on attribute/variable side-conditions, and imperative control flow units. BRS on the other hand, required a larger number of entities in order to both encode attributes directly in the model (via nesting) and provide tagging functionality that, when coupled with rule priorities, implements control flow. There remains promising research mapping techniques between the formalisms to further enable flexible and expressive modelling.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
Graph Transformation, Specifications, and Nets
影响因子：
--
作者：
B. König;Dennis Nolte;J. Padberg;A. Rensink
通讯作者：
A. Rensink
图重写 Petri 网
DOI：
--
发表时间：
2018
期刊：
International Conference on Graph Transformation
影响因子：
--
作者：
Géza Kulcsár;Malte Lochau;Andy Schürr
通讯作者：
Andy Schürr
关键物联网系统同步、八卦和环境影响的正式验证
DOI：
--
发表时间：
2018
期刊：
EasyChair Preprints
影响因子：
--
作者：
M. Webster;Michael J. Breza;C. Dixon;Michael Fisher;J. Mccann
通讯作者：
J. Mccann
一种通过图变换设计动态拓扑控制算法的方法
DOI：
--
发表时间：
2015
期刊：
International Conference on Model Transformation
影响因子：
--
作者：
R. Kluge;Gergely Varró;Andy Schürr
通讯作者：
Andy Schürr
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
V. Sassone;P. Sobocinski
通讯作者：
P. Sobocinski