A METHODOLOGY FOR DESIGN SPACE EXPLORATION OF REAL-TIME
LOCATION SYSTEMS

Kirov Dmitry Alexandrovich, Passerone Roberto , Ozhiganov Aleхander A.

doi:10.17586/2226-1494-2015-15-4-551-567

2015 , VOLUME 15, NUMBER 4 ( July–August )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

doi: 10.17586/2226-1494-2015-15-4-551-567

A METHODOLOGY FOR DESIGN SPACE EXPLORATION OF REAL-TIME LOCATION SYSTEMS

D. A. Kirov, R. Passerone, A. A. Ozhiganov

Read the full article

Article in English

For citation: Kirov D.A., Passerone R., Ozhiganov A.A. A methodology for design space exploration of real-time location systems. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2015, vol. 15, no. 4. pp. 551–567 (in English)

Abstract

Scope of Research. This paper deals with the problem of design space exploration for a particular class of networked embedded systems called Real-Time Location Systems (RTLS). Methods. The paper contains a clear and detailed plan of anongoing research and could be considered as a review, a vision and a statement of objectives. Analytical and formal methods, simulation and automated verification will be involved in the research. Main Results. Analysis of the state of the art (current design flow, existing simulation tools and verification techniques) has revealed several limitations for performing efficientdesign space exploration of RTLS, especially for safety-critical applications. The review part of the paper also contains a clear problem statement. The main outcome of this research is the proposed vision of a novel methodology for determining the best-suited technology and its configuration from the space of potential solutions. In particular, it is planned to extend an existing simulation framework and apply automated verification techniques. The latter will be used for checking simulation results and also for exploring different system configuration alternatives, that is, to optimize the design, which is a novel approach. A case study for validating the methodology is also proposed. Practical Significance. The proposed methodology will highly increase the breadth of design space exploration of RTLS as well as the confidence on taken design decisions. It will also contribute to optimizing the design.

Keywords: design space exploration, localization, positioning, real-time location systems, RTLS, simulation, automated verification, statistical model checking, networked embedded systems, embedded systems, cyber-physical systems, CPS.

References

1. Lee E.A., Seshia S.A. Introduction to Embedded Systems: a Cyber-Physical Systems Approach. Lulu.com, 2011, 516 p.

2. Lee E.A., Kubiatowicz J.D., Rabaey J.M., Seshia S.A. et al. The Terraswarm Research Center (TSRC) (A White Paper). Technical Report no. UCB/EECS-2012-207. EECS Department, University of California, Berkeley, 2012, 14 p.

3. Lee J.H., Buehrer R.M. Fundamentals of received signal strength-based position location. In Handbook of Position Location: Theory, Practice, and Advances. John Wiley and Sons, 2012, pp. 359–394. doi: 10.1002/9781118104750.ch11

4. Buehrer R.M., Venkatesh S. Fundamentals of time-of-arrival-based position location. In Handbook of Position Location: Theory, Practice, and Advances. John Wiley and Sons, 2012, pp. 175–212. doi:10.1002/9781118104750.ch6

5. Peng R., Sichitiu M.L. Angle of arrival localization for wireless sensor networks. Proc. 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston, USA, 2006, vol. 1, pp. 374–382. doi: 10.1109/SAHCN.2006.288442

6. Zekavat S.A., Kansal S., Levesque A.H. Wireless positioning systems: operation, application and comparison. In Handbook of Position Location: Theory, Practice and Advances. John Wiley and Sons, 2012, pp. 3–23. doi: 10.1002/9781118104750.ch1

7. El Madani B., Yao A.P., Lyhyaoui A. Combining Kalman filtering with ZigBee protocol to improve localization in wireless sensor network. ISRN Sensor Networks, 2013, art. 252056. doi: 10.1155/2013/252056

8. Liu H., Darabi H., Banerjee P., Liu J. Survey of wireless indoor positioning techniques and systems. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 2007, vol. 37, no. 6, pp. 1067–1080. doi: 10.1109/TSMCC.2007.905750

9. Aravecchia M., Messelodi S. Gaussian process for RSS-based localization. Proc. 10th IEEE Int. Conf. on Wireless and Mobile Computing, Networking and Communications. Larnaca, Cyprus, 2014, pp. 654–659. doi: 10.1109/WiMOB.2014.6962240

10. Bouet M., dos Santos A.L. RFID tags: positioning principles and localization techniques. Proc. 1st IFIP Wireless Days. Dubai, United Arab Emirates, 2008, art. 4812905. doi: 10.1109/WD.2008.4812905

11. Raza U., Murphy A.L., Picco G.P. Embracing localization inaccuracy: a case study. Proc. IEEE 8th Int. Conf. on Intelligent Sensors, Sensor Networks and Information Processing. Melbourn, Australia, 2013, vol. 1, pp. 207–212. doi: 10.1109/ISSNIP.2013.6529790

12. Nissanka B.P. The Cricket Indoor Location System. PhD thesis. Massachusetts Institute of Technology, 2005.

13. Real-Time Location Systems (RTLS). Technical Report. Nanotron Technologies GmbH, 2006, 20 p.

14. Want R. An introduction to RFID technology. IEEE Pervasive Computing, 2006, vol. 5, no. 1, pp. 25–33. doi: 10.1109/MPRV.2006.2

15. Mitrokotsa A., Douligeris C. Integrated RFID and sensor networks: architectures and applications. In RFID and Sensor Networks: Architectures, Protocols, Security and Integrations. CRC Press, 2009, pp. 511–536.

16. Enriquez G., Park S., Hashimoto S. Wireless sensor network and RFID fusion approach for mobile robot navigation. ISRN Sensor Networks, 2013, art. 157409. doi: 10.1155/2013/157409

17. Liu H., Bolic M., Nayak A., Stojmenovic I. Taxonomy and challenges of the integration of RFID and wireless sensor networks. IEEE Network, 2008, vol. 22, no. 6, pp. 26–32. doi: 10.1109/MNET.2008.4694171

18. Lei Z., Zhi W. Integration of RFID into wireless sensor networks: architectures, opportunities and challenging problems. Proc. 5th Int. Conf. on Grid and Cooperative Computing. Hunan, China, 2006, pp. 463–469. doi: 10.1109/GCCW.2006.58

19. Yang L., Xu H. Wireless localization using ultra-wideband signals. In Handbook of Position Location: Theory, Practice, and Advances. John Wiley and Sons, 2012, pp. 245–277. doi: 10.1002/9781118104750.ch8

20. Chakeres I.D., Belding-Royer E.M. AODV routing protocol implementation design. Proc. 24th Int. Conf. on Distributed Computing Systems Workshops. Hachioji, Japan, 2004, vol. 24, pp. 698–703.

21. Gnawali O., Fonseca R., Jamieson K., Kazandjieva M., Moss D., Levis P. CTP: an efficient, robust and reliable collection tree protocol for wireless sensor networks. ACM Transactions on Sensor Networks, 2013, vol. 10, no. 1, art. 16. doi: 10.1145/2529988

22. Lee E.A. Cyber-physical systems: design challenges. Proc. 11th IEEE Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC). Orlando, USA, 2008, pp. 363–369. doi: 10.1109/ISORC.2008.25

23. Sangiovanni-Vincentelli A. Quo vadis, SLD? Reasoning about the trends and challenges of system level design. Proceedings of the IEEE, 2007, vol. 95, no. 3, pp. 467–506. doi: 10.1109/JPROC.2006.890107

24. Davare A., Densmore D., Guo L., Passerone R., Sangiovanni-Vincentelli A., Simalatsar A., Zhu Q. MetroII: a design environment for cyber-physical systems. Transactions on Embedded Computing Systems, 2013, vol. 12, art. 49. doi: 10.1145/2435227.2435245

25. Sangiovanni-Vincentelli A., Damm W., Passerone R. Taming Dr. Frankenstein: contract-based design for cyber-physical systems. European Journal of Control, 2012, vol. 18, no. 3, pp. 217–238. doi: 10.3166/EJC.18.217-238

26. Lee E.A., Neuendorffer S., Wirthlin M.J. Actor-oriented design of embedded hardware and software systems. Journal of Circuits, Systems and Computers, 2003, vol. 12, no. 3, pp. 231–260. doi: 10.1142/S0218126603000751

27. Kirov D.A., Ozhiganov A.A. Analysis of wireless sensor and actuator networks design methods. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2013, no. 1 (83), pp. 129–135. (in Russian)

28. Zekavat S.A. Channel modeling and its impact on localization. In Handbook of Position Location: Theory, Practice, and Advances. John Wiley and Sons, 2012, pp. 105–135. doi: 10.1002/9781118104750.ch4

29. Boulis A. Castalia: revealing pitfalls in designing distributed algorithms in WSN. Proc. 5th ACM Conference on Embedded Networked Sensor Systems. Sydney, Australia, 2007, pp. 407–408. doi: 10.1145/1322263.1322318

30. Koepke A., Swigulski M., Wessel K., Willkomm D., Klein Haneveld P.T., Parker T.E.V., Visser O.W., Lichte H.S., Valentin S. Simulating wireless and mobile networks in OMNET++: the MiXiM vision. Proc. 1st Int. Conf. on Simulation Tools and Techniques for Communications, Networks and Systems, SIMUTOOLS’08.

Marseille, France, 2008, pp. 263–284.

31. System Design, Modeling and Simulation using Ptolemy II. Ed. C. Ptolemaeus. Ptolemy.org Publ., 2013, 685 p.

32. Baldwin P., Kohli S., Lee E.A., Liu X., Zhao Y. VisualSense: visual modeling for wireless and sensor network systems. Technical Memorandum UCB/ERL M05/25. University of California, Berkeley, 2005, 68 p.

33. Minakov I., Passerone R. PASES: an energy-aware design space exploration framework for wireless sensor networks. Journal on Systems Architecture, 2013, vol. 59, no. 8, pp. 626–642. doi: 10.1016/j.sysarc.2013.05.020

34. Transaction-Level Modeling with SystemC. Ed. F. Genassia. Springer, 2005, 272 p. doi: 10.1007/b137175

35. Fummi F., Quaglia D., Stefanni F. A systemC-based framework for modeling and simulation of networked embedded systems. Proc. Forum on Specification, Verification and Design Languages, FDL'08. Stuttgart, Germany, 2008, pp. 49–54. doi: 10.1109/FDL.2008.4641420

36. Eriksson J., Osterlind F., Finne N., Tsiftes N, Dunkels A., Voigt T., Sauter R., Marron P.J. COOJA/MSPSim: interoperability testing for wireless sensor networks. Proc. 2nd Int. Conf. on Simulation Tools and Techniques. Rome, Italy, 2009. doi: 10.4108/ICST.SIMUTOOLS2009.5637

37. Du W., Mieyeville F., Navarro D., O'Connor I. IDEA1: a validated SystemC-based system-level design and simulation environment for wireless sensor networks. EURASIP Journal on Wireless Communications and Networking, 2011, pp. 143. doi: 10.1186/1687-1499-2011-143

38. Lizarraga A., Ding L., Hiner J., Lysecky R., Lysecky S., Gordon-Ross A. ATLeS-SN: a modular simulator for wireless sensor networks. Design Automation for Embedded Systems, 2013, vol. 16, no. 4, pp. 265–291. doi: 10.1007/s10617-013-9109-2

39. Bayer C., Katoen J.-P. Principles of Model Checking. Cambridge, MIT Press, 2008, 984 p.

40. Sebastiani R. Lazy satisfiability modulo theories. Journal on Satisfiability, Boolean Modeling and Computation, 2007, vol. 3, pp. 141–224.

41. Biere A. Bounded model checking. Frontiers in Artificial Intelligence and Applications, 2009, vol. 185, no. 1, pp. 457–481. doi: 10.3233/978-1-58603-929-5-457

42. Basu A., Bensalem S., Bozga M., Caillaud B., Delahaye B., Legay A. Statistical abstraction and model checking of large heterogeneous systems. Lecture Notes in Computer Science, 2010, vol. 6117 LNCS, pp. 32–46. doi: 10.1007/978-3-642-13464-7_4

43. Kwiatkowska M., Norman G., Parker D. PRISM 4.0: verification of probabilistic real-time systems. Lecture Notes in Computer Science, 2011, vol. 6806 LNCS, pp. 585–591. doi: 10.1007/978-3-642-22110-1_47

44. Boyer B., Corre K., Legay A., Sedwards S. PLASMA-lab: a flexible, distributable statistical model checking library. Lecture Notes in Computer Science, 2013, vol. 8054 LNCS, pp. 160–164. doi: 10.1007/978-3-642-40196-1_12

45. Bertinato M., Ortolan G., Maran F., Marcon R., Marcassa A., Zanella F., Zambotto M., Schenato L., Cenedese A. RF localization and tracking of mobile nodes in wireless sensor networks: architectures, algorithms and experiments. University of Padua, Italy, 2007.

46. Guerrero-Ibanez J., Flores-Cortes C., Zeadally S. Vehicular ad-hoc networks (VANETs): architecture, protocols and applications. In Next-Generation Wireless Technologies. Springer, 2013, pp. 49–70.

47. Boukerche A., Oliveira H.A., Nakamura E.F., Loureiro A.A. Vehicular ad-hoc networks: a new challenge for localization-based systems. Computer Communications, 2008, vol. 31, no. 12, pp. 2838–2849. doi: 10.1016/j.comcom.2007.12.004

48. Drenjanac D., Tomic S., Aguera J., Perez-Ruiz M. Wi-fi and satellite-based location techniques for intelligent agricultural machinery controlled by a human operator. Sensors (Switzerland), 2014, vol. 14, no. 10, pp. 19767–19784. doi: 10.3390/s141019767

49. Rappaport T.S. Wireless Communications: Principles and Practice. 2nd ed. Prentice Hall, 2002, 736 p.

50. Cimatti A., Palopoli L., Ramadian Y. Symbolic computation of schedulability regions using parametric timed automata. Proc. Real-Time Systems Symposium. Barcelona, Spain, 2008, pp. 80–89. doi: 10.1109/RTSS.2008.36

51. Simalatsar A., Ramadian Y., Passerone R., Lampka K., Perathoner S., Thiele L. Enabling parametric feasibility analysis in real-time calculus driven performance evaluation. Proc. 14th Int. Conf. on Compilers, Architectures and Synthesis for Embedded Systems. Teipei, Taiwan, 2011, pp. 155–164. doi: 10.1145/2038698.2038723

52. Brunelli D., Minakov I., Passerone R., Rossi M. POVOMON: an ad-hoc wireless sensor network for indoor environmental monitoring. Proc. 6th IEEE Workshop on Environmental, Energy and Structural Monitoring Systems. Naples, Italy, 2014, pp. 175–180. doi: 10.1109/EESMS.2014.6923287

53. Kleissl J., Agarwal Y. Cyber-physical energy systems: focus on smart buildings. Proc. 47th Design Automation Conference. Anaheim, USA, 2010, pp. 749–754. doi: 10.1145/1837274.1837464

54. Ye W., Heidemann J., Estrin D. An energy-efficient MAC protocol for wireless sensor networks. Proc. 21st IEEE INFOCOM. NY, 2002, vol. 3, pp. 1567–1576. doi: 10.1109/INFCOM.2002.1019408

55. Lu C., Xing G., Chipara O., Fok C.-L., Bhattacharya S. A spatiotemporal query service for mobile users in sensor networks. Proc. 25th IEEE Int. Conf. on Distributed Computing Systems, ICDCS. Columbus, USA, 2005, pp. 381–390.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License