research-article

Reconstruction of event sequences based on asynchronous observations in sensor networks

Authors:

Jiaxiang Yan,

Lingxi Li,

Dongsoo S. KimAuthors Info & Claims

ICUIMC '13: Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication

Article No.: 37, Pages 1 - 7

https://doi.org/10.1145/2448556.2448593

Published: 17 January 2013 Publication History

Get Access

Abstract

This paper proposes an event sequence reconstruction algorithm for a given sensor network based on asynchronous observations of its state changes. We assume that the sensor network is modeled as a Petri net and the asynchronous observations are in the form of state (token) changes at different places in the Petri net. More specifically, the observed sequences of state changes are provided by local sensors and are asynchronous, i.e., they only contain partial information about the ordering of the state changes that occur. We propose an approach that is able to partition the given net into several subnets and reconstruct the event sequence for each subnet. Then we develop an algorithm that is able to reconstruct the event sequences for the entire net that are consistent with: 1) the asynchronous observations of state changes; 2) the event sequences of each subnet; and 3) the structure of the given Petri net. We also discuss the algorithmic complexity and present an example to illustrate our approach.

References

[1]

Y. Luo and J. Tsai, "A graphical simulation system for modeling and analysis of sensor networks," in Proc. of the 7th IEEE International Symposium on Multimedia, pp. 474--482, December 2005.

Digital Library

Google Scholar

[2]

R. V. AdiMallikarjuna, A. Kumar, and D Janakiram, "E-Petri net model for programming integrated network of wireless sensor networks and grids," in Proc. of 7th International Conference on Computer and Information Technology, pp. 1038--1043, October 2007.

Digital Library

Google Scholar

[3]

V. Devarashetty, J. Tsai, L. Ma, and D. Zhang, "Modeling a secure sensor network system using an extended elementary object system," in Proc. of 7th IEEE International Conference on Cognitive Informatics, pp. 67--74, August 2008.

Google Scholar

[4]

C. Kuo and J. Siao, "Petri net based reconfigurable wireless sensor networks for intelligent monitoring systems," in Proc. of International Conference on Computational Science and Engineering, pp. 897--902, August 2009.

Digital Library

Google Scholar

[5]

D. He, L. Cui, H. Huang, and M. Ma, "Design and verification of enhanced secure localization scheme in wireless sensor networks," IEEE Trans. on Parallel and Distributed Systems, vol. 20, no. 7, pp. 1050--1058, July 2009.

Digital Library

Google Scholar

[6]

A. Shareef and Y. Zhu, "Energy modeling of wireless sensor nodes based on Petri nets," in Proc. of 39th International Conference on Parallel Processing, pp. 101--110, Septermber 2010.

Digital Library

Google Scholar

[7]

J. Lee, "A Petri net design of command filters for semiautonomous mobile sensor networks," IEEE Trans. on Industrial Electronics, vol. 55, no. 4, pp. 1835--1841, April 2008.

Crossref

Google Scholar

[8]

L. Li, C. N. Hadjicostis, and R. S. Sreenivas, "Reconstruction of transition firing sequences based on asynchronous observations of place token changes," in Proc. 46th IEEE Intl. Conf. Decision and Control, pp. 1898--1903, December 2007.

Google Scholar

[9]

T. Murata, "Petri nets: Properties, analysis and applications," Proc. of the IEEE, vol. 77, no. 4, pp. 541--580, April 1989.

Crossref

Google Scholar

[10]

C. G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, Springer, 1999.

Digital Library

Google Scholar

[11]

S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Second Edition, Pearson Education, Inc., 2003.

Digital Library

Google Scholar

Cited By

View all

Keyu Ruan Weimin Wu Li L(2016)Reconstruction of unknown Petri net structures from asynchronous observations of token change sequences2016 IEEE International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2016.7743519(1049-1054)Online publication date: Aug-2016
https://doi.org/10.1109/COASE.2016.7743519
Shen FLiu CQi BJi YCaban D(2014)Building Effective Scheduling Algorithms for Sensor Networks2014 11th International Conference on Information Technology: New Generations10.1109/ITNG.2014.111(403-406)Online publication date: Apr-2014
https://doi.org/10.1109/ITNG.2014.111

Index Terms

Reconstruction of event sequences based on asynchronous observations in sensor networks
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Software system models
        Petri nets

Recommendations

Some observations on supervisory policies that enforce liveness in partially controlled Free-Choice Petri nets

Every arc from a place to a transition in a Free-Choice Petri net (FCPN) is either the unique output arc of the place, or, the unique input arc to the transition [M.H.T. Hack, Analysis of production schemata by Petri nets, Master's thesis, Massachusetts ...
Diagnosis of Asynchronous Discrete Event Systems: A Net Unfolding Approach
WODES '02: Proceedings of the Sixth International Workshop on Discrete Event Systems (WODES'02)

This paper studies diagnosis of asynchronous discrete event systems. We follow a so-called true concurrency approach, in which neither global state nor global time are available. Instead, we use only local states in combination with a partial order ...
Least-cost path estimation in wireless ad hoc sensor networks using Petri nets
ICUIMC '11: Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication

This paper develops an iterative algorithm for estimating the least-cost paths that can lead from a given initial state to a given final state in a wireless ad hoc sensor network (WASN) that is modeled by a Petri net. In particular, a WASN can be assumed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICUIMC '13: Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication

January 2013

772 pages

ISBN:9781450319584

DOI:10.1145/2448556

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICUIMC '13

Sponsor:

SIGAPP
SKKU

ICUIMC '13: The 7th International Conference on Ubiquitous Information Management and Communication

January 17 - 19, 2013

Kota Kinabalu, Malaysia

Acceptance Rates

Overall Acceptance Rate 251 of 941 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
59
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Keyu Ruan Weimin Wu Li L(2016)Reconstruction of unknown Petri net structures from asynchronous observations of token change sequences2016 IEEE International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2016.7743519(1049-1054)Online publication date: Aug-2016
https://doi.org/10.1109/COASE.2016.7743519
Shen FLiu CQi BJi YCaban D(2014)Building Effective Scheduling Algorithms for Sensor Networks2014 11th International Conference on Information Technology: New Generations10.1109/ITNG.2014.111(403-406)Online publication date: Apr-2014
https://doi.org/10.1109/ITNG.2014.111

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Some observations on supervisory policies that enforce liveness in partially controlled Free-Choice Petri nets

Diagnosis of Asynchronous Discrete Event Systems: A Net Unfolding Approach

Least-cost path estimation in wireless ad hoc sensor networks using Petri nets