Communication-Efficient Support for Spatial Filtering of State Updates in Distributed Virtual Environments

ABSTRACT

Spatial filtering is an interest management mechanism that eliminates unnecessary state updates transmitted in distributed virtual environments. This paper proposes a new protocol to reduce the communication overhead for supporting spatial filtering. The protocol maintains potential interest regions (PIRs) to assist in observing entities entering the areas-of-interest (AOIs) of other entities. PIRs enable the protocol to take advantage of the relative positions between entities and AOIs to save communication cost. We elaborate the design of the protocol. A number of concurrency issues that arise from the delay of message transmission are identified and resolved. We also propose an algorithm for computing PIRs to maximize the saving in communication cost. Experimental results show that the proposed protocol maintains highly accurate entity-in-AOI knowledge with substantially lower communication overhead compared to existing strategies.

REFERENCES

• 1: R. Waters and J. Barrus, "The Rise of Shared Virtual Environments", IEEE Spectrum, 34(3):20-25, Mar. 1997.
• 2: John C. S. Lui , M. F. Chan, An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.193-211, March 2002 [doi>10.1109/71.993202]
• 3: Michele Garetto , Emilio Leonardi, Analysis of Random Mobility Models with Partial Differential Equations, IEEE Transactions on Mobile Computing, v.6 n.11, p.1204-1217, November 2007 [doi>10.1109/TMC.2007.1023]
• 4: Mark Claypool , Kajal Claypool, Latency and player actions in online games, Communications of the ACM, v.49 n.11, November 2006 [doi>10.1145/1167838.1167860]
• 5: Wentong Cai , Stephen J. Turner , Bu-Sung Lee , Junlan Zhou, An alternative time management mechanism for distributed simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.2, p.109-137, April 2005 [doi>10.1145/1060576.1060577]
• 6: Katherine L. Morse , Lubomir Bic , Michael Dillencourt, Interest Management in Large-Scale Virtual Environments, Presence: Teleoperators and Virtual Environments, v.9 n.1, p.52-68, February 2000 [doi>10.1162/105474600566619]
• 7: M. Bassiouni, M.-H. Chiu, M. Loper, and M. Garnsey, "Relevance Filtering for Distributed Interactive Simulation", Computer Systems Science & Engineering, 13(1):39-47, Jan. 1998.
• 8: John C. S. Lui, Constructing Communication Subgraphs and Deriving an Optimal Synchronization Interval for Distributed Virtual Environment Systems, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.778-792, September 2001 [doi>10.1109/69.956100]
• 9: Rassul Ayani , Farshad Moradi , Gary Tan, Optimizing cell-size in grid-based DDM, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.93-100, May 28-31, 2000, Bologna, Italy
• 10: IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA) - Framework and Rules, IEEE Standard 1516, 2000.
• 11: D. Wood, "Implementation of DDM in the MAK High Performance RTI", Proc. 2002 Spring Simulation Interoperability Workshop (SIW), paper 02S-SIW-056, Mar. 2002.
• 12: Haibo Hu , Jianliang Xu , Dik Lun Lee, A generic framework for monitoring continuous spatial queries over moving objects, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066212]
• 13: Bugra Gedik , Ling Liu, MobiEyes: A Distributed Location Monitoring Service Using Moving Location Queries, IEEE Transactions on Mobile Computing, v.5 n.10, p.1384-1402, October 2006 [doi>10.1109/TMC.2006.153]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: User profiles and alert services

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems
      H.3.5 On-line Information Services
          Subjects: Web-based services

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Design, Management

Keywords:
distributed virtual environment, state update, interest management, consistency