research-article

SCPS: A Social-Aware Distributed Cyber-Physical Human-Centric Search Engine

Authors:

Stanley MoyerAuthors Info & Claims

IEEE Transactions on Computers, Volume 64, Issue 2

Pages 518 - 532

https://doi.org/10.1109/TC.2013.211

Published: 01 February 2015 Publication History

Abstract

Advances in ubiquitous sensing, computing and wireless communication technologies are leading to the development of cyber-physical systems (CPS), which promise to revolutionize the way we interact with the physical world. CPS applications, such as healthcare monitoring, may involve many users and objects scattered over a wide area. One critical function of CPS is object search in the physical world through the cyber sphere that enables interaction between the cyber and physical spheres. Some of the previously proposed physical object search engines use RFID tracking, and others collect the information of object locations into a hierarchical centralized server. The difficulty of widely deploying RFID devices, the centralized search, and the need for periodical location information collection prevent CPS from achieving higher scalability and efficiency. To deal with this problem, we propose a Social-aware distributed Cyber-Physical human-centric Search engine (SCPS) that leverages the social network formed by wireless device users for object search. Without requiring periodical location information collection, SCPS locates objects held by users based on the routine user movement pattern. Moreover, using a social-aware Bayesian network, it can accurately predict the users' locations even at the occurrence of exceptional (i.e., non-routine) events (e.g., raining) that break user movement pattern. Thus, SCPS is more advantageous than all previous social network based works which assume that user behaviors always follow a certain pattern. Further, SCPS conducts the search in a fully distributed manner by relying on a distributed hash table (DHT) structure. As a result, SCPS achieves high scalability, efficiency and location accuracy. Extensive real-trace driven simulation results show the superior performance of SCPS compared to other representative search methods including a hierarchical centralized method, a decentralized method, and two social network based methods. The results also show the effectiveness of different components of SCPS.

References

[1]

E. A. Lee, “Cyber physical systems: Design challenges,” in Proc. 11th IEEE Int. Symp. Object Oriented Real-Time Distributed Computing (SORC), 2008, pp. 363–369.

[2]

E. A. Fry and L. A. Lenert, “MASCAL: RFID tracking of patients, staff, and equipment to enhance hospital response to mass casualty events,” in Proc. AMIA Annu. Symp., 2005, pp. 261–265.

[3]

K. K. Yap, V. Srinivasan, and M. Motani, “MAX: Human-centric search of the physical world,” in Proc. 3rd Int. Conf. Embedd Netw. Sensor Syst. (SenSys), 2005, pp. 166–179.

[4]

H. Wang, C. C. Tan, and Q. Li, “Snoogle: A search engine for the physical world,” in Proc. IEEE Conf. Comput. Commun. (INFOCOM), 2008, pp. 1382–1390.

[5]

C. Tan, B. Sheng, H. Wang, and Q. Li Microsearch: When search engines meet small devices Proc. Perv., New York, NY: Springer-verlag, 2008, pp. 93–110.

[6]

Wall Street Cheers iPhone Sales Data, [Online]. Available: http://weblogs.baltimoresun.com/business/appleaday/blog/2007/09/wall_street_cheers_iphone_sale.html.

[7]

M. C. Gonzalez, C. A. Hidalgo, and A. Barabasi, “Understanding individual human mobility patterns”, in Nature, vol. 453, no. 7196, pp. 779–782, 2008.

[8]

M. Mcpherson, “Birds of a feather: Homophily in social networks”, in Annu. Rev. Sociol., vol. 27, no. 1, pp. 415–444, 2001.

[9]

A. Lindgren, A. Doria, and O. Schelén, “Probabilistic routing in intermittently connected networks”, in Service Assur. Partial Intermittent Resour., vol. 3126, pp. 239–254, 2004.

[10]

J. Ghosh, S. J. Philip, and C. Qiao, “Sociological orbit aware location approximation and routing (SOLAR) in MANET”, in Ad Hoc Netw., vol. 5, no. 2, pp. 189–209, 2007.

Digital Library

[11]

E. M. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant manets,” in Proc. 6th Annu. Int. Conf. Mobile Comput. Netw. (MobiHoc), 2007, pp. 32–40.

[12]

F. Li and J. Wu, “MOPS: Providing content-based service in disruption-tolerant networks,” in Proc. 29th IEEE Int. Conf. Distrib. Comput. Syst. (ICDCS), 2009, pp. 526–533.

[13]

P. Hui, J. Crowcroft, and E. Yoneki, “Bubble rap: Social-based forwarding in delay tolerant networks,” in Proc. IEEE Trans. Mob. Comput. (MobiHoc), 2008, pp. 241–250.

[14]

A. Mtibaa, M. May, C. Diot, and M. Ammar, “Peoplerank: Social opportunistic forwarding,” in Proc. IEEE Conf. Comput. Commun. (INFOCOM), 2010, pp. 111–115.

[15]

B. Guo and M. Imai, “Home-explorer: Search, localize, and manage the physical artifacts indoors,” in Proc. 21st Int. Conf. Adv. Inform. Netw. Appl. (AINA), 2007, pp. 378–385.

[16]

G. Mao, B. Fidan, and B. Anderson, “Wireless sensor network localization techniques”, in Comput. Netw., vol. 51, no. 10, pp. 2529–2553, 2007.

Digital Library

[17]

R. Peng and M. L. Sichitiu, “Probabilistic localization for outdoor wireless sensor networks”, in Mobile Comp. Commun. Rev., vol. 11, no. 1, pp. 53–64, 2007.

Digital Library

[18]

H. C. Chu and R. H. Jan, “A GPS-less, outdoor, self-positioning method for wireless sensor networks”, in Ad Hoc Netw., vol. 5, no. 5, pp. 547–557, 2007.

Digital Library

[19]

J. Bruck, J. Gao, and A. Jiang, “Localization and routing in sensor networks by local angle information”, in ACM Trans. Sensor Netw., vol. 5, no. 1, 2009.

[20]

Y. M. Kwon, K. Mechitov, S. Sundresh, W. Kim, and G. Agha, “Resilient localization for sensor networks in outdoor environments”, in ACM Trans. Sensor Netw., vol. 7, no. 1, 2010.

[21]

S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker, “A scalable content-addressable network,” in Proc. Conf. Appl. Technol. Archit. protocols Comput. Commun. (SIGCOMM), 2001, pp. 161–172.

[22]

I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for internet applications,” in Proc. Conf. Appl. Technol. Archit. protocols Comput. Commun. (SIGCOMM), 2001, pp. 149–160.

[23]

A. Rowstron and P. Druschel, “Pastry: Scalable, distributed object location, and routing for large-scale peer-to-peer systems,” in Proc. 18th IFIP/ACM Int. Conf. Distrib. Syst. Platforms (Middleware), 2001, pp. 329–350.

[24]

B. Y. Zhao, J. Kubiatowicz, and A. D. Joseph, Tapestry: An infrastructure for fault-tolerant wide-area location, and routing, Comput. Sci. Div., Univ. California, 2001, Tech. Rep.

[25]

D. Guo, J. Wu, H. Chen, and X. Luo, “Moore: An extendable peer-to-peer network based on incomplete kautz digraph with constant degree,” in Proc. INFOCOM, 2007, pp. 821–829.

[26]

B. Karp and H. T. Kung, “GPSR: Greedy perimeter stateless routing for wireless networks,” in Proc. IMobiCom, 2000, pp. 243–254.

[27]

F. V. Jensen, An Introduction to Bayesian Networks, London: UCL Press, 1996.

Digital Library

[28]

A. P. Dawid, “Applications of a general propagation algorithm for probabilistic expert systems”, in Stat. Comput., vol. 2, pp. 25–36, 1992.

[29]

F. V. Jensen, S. L. Lauritzen, and K. G. Olesen, “Bayesian updating in recursive graphical models by local computations”, in Comput. Stat. Quart., pp. 1–23, 1990.

[30]

L. Le Cam Maximum likelihood an introduction Lecture Notes in Statistics, College Park, MD: Univ. Maryland, 1990.

[31]

H. W. Sorenson, Parameter Estimation: Principles and Problems, New York: Marcel Dekker, 1980, vol. 382.

[32]

S. L. Lauritzen, “The EM algorithm for graphical association models with missing data”, in Comp. Stat. Data Anal., pp. 191–201, 1995.

[33]

G. Cooper and C. Yoo, “Causal discovery from a mixture of experimental, and observational data,” in Proc. 15th Conf. Uncertainty Artif. Intell. (UAI), 1999, pp. 116–125.

[34]

N. Wermuth and S. L. Lauritzen, “Graphical and recursive models for contingency tables”, in Biometrika, vol. 72, pp. 537–552, 1983.

[35]

T. Verma and J. Pearl, “An algorithm for deciding if a set of observed independencies has a causal explanation,” in Proc. 8th Conf. Uncertainty Artif. Intell. (UAI), 1992, pp. 323–330.

[36]

C. Taylor, A. Rahimi, J. Bachrach, H. Shrobe, and A. Grue, “Simultaneous localization, calibration, and tracking in an ad hoc sensor network,” in Proc. 5th Int. Conf. Inform. Process. Sensor Netw. (IPSN), 2006, pp. 27–33.

[37]

T. N. Chung, O. Camp, and S. Loiseau, “A Bayesian network based trust model for improving collaboration in mobile ad hoc networks,” in Proc. IEEE Int. Conf. Res. Innov. Vis. Fut. (RIVF), 2007, pp. 144–151.

[38]

Y. Wang and J. Vassileva, “Trust, and reputation model in peer-to-peer networks,” in Proc. 3rd Int. Conf. Peer-to-Peer Comput. (P2P), 2003, pp. 150–157.

[39]

Y. Wang and J. Vassileva, “Bayesian network-based trust model,” in Proc. IEEE/WIC Int. Conf. Web Intell. (WI), 2003, pp. 372–378.

[40]

R. Arroyo-Valles, A. G. Marques, J. J. Vinagre-Diaz, and J. Cid-Sueiro, “A bayesian decision model for intelligent routing in sensor networks,” in Proc. 3rd Int. Symp. Wireless Commun. Syst. (SWCS), 2006, pp. 103–107.

[41]

K. S. Hwang and S. B. Cho, “Modular bayesian network learning for mobile life understanding,” in Proc. Intell. Data Eng. Automated Learning (IDEAL), 2008, pp. 225–232.

[42]

T. Bruland, A. Aamodt, and H. Langseth, “Architectures integrating case-based reasoning, and bayesian networks for clinical decision support,” in Proc. Intell. Inform. Process., 2010, pp. 82–91.

[43]

A. Rowe, M. Berges, G. Bhatia, E. Goldman, R. Rajkumar, L. Soibelman, J. Garrett, and J. M. F. Moura, Sensor andrew: Large-scale campus-wide sensing and actuation, 2008, CMU Tech. Rep.

[44]

Y. Li, L. Shou, and K. L. Tan, “CYBER: A community-based search engine,” in Proc. 8th Int. Conf. Peer-to-Peer Comput. (P2P), 2008, pp. 215–224.

[45]

N. Eagle, A. Pentland, and D. Lazer, “Inferring social network structure using mobile phone data”, in Proc. Nat. Acad. Sci., vol. 106, pp. 15274–15278, 2009.

[46]

The Network Simulator ns-2, [Online]. Available: http://www.isi.edu/nsnam/ns/.

[47]

PlanetSim, [Online]. Available: http://projects-deim.urv.cat/trac/planetsim/.

[48]

BNT Bayes Net Toolbox for Matlab, [Online]. Available: http://code.google.com/p/bnt/.

[49]

J. L. Hammond and P. J. P. O’Reilly, Performance Analysis of Local Computer Networks, Reading, MA: Addison-Wesley Publishing Company, 1988.

[50]

S. Chahramant, Fundamentals of Probability with Stochastic Process, Springfield, MA: Western New England College, 1986.

Cited By

Zhao KZhang ZRaymond Choo KZhang ZZhang T(2023)A Combinatorial Optimization Analysis Method for Detecting Malicious Industrial Internet Attack BehaviorsACM Transactions on Cyber-Physical Systems10.1145/36375548:1(1-20)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1145/3637554
Liu JShen HNarman HChung WLin Z(2018)A Survey of Mobile Crowdsensing TechniquesACM Transactions on Cyber-Physical Systems10.1145/31855042:3(1-26)Online publication date: 13-Jun-2018
https://dl.acm.org/doi/10.1145/3185504

Index Terms

SCPS: A Social-Aware Distributed Cyber-Physical Human-Centric Search Engine

Index terms have been assigned to the content through auto-classification.

Recommendations

Cyber Physical Socio Ecology

Exploring the laws of the nature and the rules of human society is the grand challenge of sciences. The Internet, Web, various communication networks and digital devices are connecting each other to form an enormous cyber space. The cyber space ...
Cyber-Physical Systems: Integrated Computing and Engineering Design
Cyber Physical Society
SKG '10: Proceedings of the 2010 Sixth International Conference on Semantics, Knowledge and Grids

Natural physical space provides material basis for the birth and evolution of human beings and civilization. The progress of human society has created the cyber space. With the rapid development of information technology, the cyber space is connecting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 64, Issue 2

Feb. 2015

297 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2013.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 February 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao KZhang ZRaymond Choo KZhang ZZhang T(2023)A Combinatorial Optimization Analysis Method for Detecting Malicious Industrial Internet Attack BehaviorsACM Transactions on Cyber-Physical Systems10.1145/36375548:1(1-20)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1145/3637554
Liu JShen HNarman HChung WLin Z(2018)A Survey of Mobile Crowdsensing TechniquesACM Transactions on Cyber-Physical Systems10.1145/31855042:3(1-26)Online publication date: 13-Jun-2018
https://dl.acm.org/doi/10.1145/3185504

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents