In this article, we address the problem of delayed query processing raised by tree-based index structures in wireless broadcast environments, which increases the access time of mobile clients. We propose a novel distributed index structure and a clustering strategy for streaming XML data that enables energy and latency-efficient broadcasting of XML data. We first define the DIX node structure to implement a fully distributed index structure which contains the tag name, attributes, and text content of an element, as well as its corresponding indices. By exploiting the index information in the DIX node stream, a mobile client can access the stream with shorter latency. We also suggest a method of clustering DIX nodes in the stream, which can further enhance the performance of query processing in the mobile clients. Through extensive experiments, we demonstrate that our approach is effective for wireless broadcasting of XML data and outperforms the previous methods.
TopIntroduction
As wireless communication technologies are rapidly gaining in popularity, the mobile computing paradigm has been realized in the industry, where mobile clients communicate by using hand-held devices such as laptops, PDAs, and cellular phones while they are moving (Acharya, Alonso, Franklin, & Zdonik, 1995; Imielinski, Viswanathan, & Badrinath, 1997). In wireless and mobile environments, data broadcasting is an effective method for data dissemination because it provides the benefits of bandwidth efficiency, scalability, and energy-efficiency. Meanwhile, mobile clients use battery-powered mobile devices in wireless broadcast environments, and thus, selective access of broadcast data is necessary for energy conservation in the devices. The overall query processing time must be also minimized in order to provide fast response to the users. The former is related to energy-efficiency and the latter is related to latency-efficiency (Imielinski, Viswanathan, & Badrinath, 1994). When a mobile device tunes in to and receives data from the broadcast stream in the active mode, it consumes much more energy than when it is in the doze mode. The tuning time is the sum of the elapsed times when the mobile client is in the active mode, and thus serves as a criterion for measuring the energy-efficiency. Meanwhile, the access time is the time elapsed from when a query is issued by a mobile client to when the target data is completely retrieved from the stream, and thus serves as a measure of the latency-efficiency.
In this article, we consider efficient streaming and access of XML data in a wireless mobile environment. With the successful development and proliferation of various related technologies, XML (eXtensible Markup Language) (W3C Recommendation-XML, 2006) has been popularly used as a standard means to facilitate the representation and sharing of structured data across different information systems not only in the wired Internet environment but also in the wireless broadcast environment (Fong & Wong, 2004). Figure 1 shows an example of an XML document (a) and its tree representation (b). This XML document will be used as a running example throughout the article.
Figure 1. An example of XML document and its tree representation
Currently, wireless broadcasting of XML data is used in emerging applications such as the Electric Program Guide (EPG) of Digital Audio/Video Broadcasting services (DVB, 2004), and the Traffic and Travel information (TTI) over a wireless broadcast channel in T-DMB (Terrestrial Digital Multimedia Broadcasting) services (TPEG, 2006). Especially, data is not static but continuously updated in such applications. Thus, there should be support for a query processing algorithm that allows mobile clients to start evaluation of a given query as soon as they tune in to the broadcast channel in order to satisfy the users’ information needs quickly and efficiently.
Park, Kim, and Chung (2005) and Park, Choi, and Lee (2006) proposed methods to stream XML data in the wireless broadcast environment in an energy-efficient manner. However, their approaches are based on a tree-structured index inserted in the stream, and query processing in a mobile client is performed by following the location paths from the XML document root to the desired data. And the mobile client cannot seek backward in the stream unless the streamed data is buffered at the client. Therefore, if the mobile client tunes in to the broadcast channel after the XML root has been passed over, it should wait until the next broadcast cycle begins, and this waiting time results in a long access time. We refer to this as the Delayed Query Processing Problem, which is described in the following example.