Offering traffic safety information to drivers and passengers is one of essential services towards the smart city. Recent research utilizes AI models to analyze the collection of IoT-driven data in transportation environments. Exploring unveiled characteristics of traffic information to improve traffic control and accident prevention on roads, this way becomes plausible. Prior studies exploited various sorts of spatio-temporal traffic data to achieve the traffic prediction using deep learning models. Without understanding the complexity of spatio-temporal data, however, their efforts have not fully shown the effectiveness of deep learning-based traffic prediction and risk presentation. In this paper, our study first applies the Pearson correlation coefficient to clarify that traffic accidents appear in high correlation with time and space patterns. We identify multiple features from traffic domains, and employ CNN first and then LSTM learning techniques on several volumes of spatio-temporal traffic data, including weather, time, traffic flow, and historical traffic accidents and locations, etc. Our study shows that the combination of CNN and LSTM learning on spatio-temporal traffic data is applicable and useful for traffic risk prediction. Under experiments and demonstrations with actual traffic datasets, our proposed traffic risk prediction scheme, called CLwST, can exhibit more accurate results, faster convergence and lower loss in comparison with the two prior studies based on LSTM and ConvLSTM schemes.

This research studies the problem of enabling users to verify that the results of analytical queries such as top k they receive from a potentially untrustworthy cloud are indeed correct. Existing work shows that it is possible for a data owner to create an authentication data structure (ADS) by which a cloud can build a verification object (VO) to prove the correctness of a query result. The current technique, however, has largely ignored the computation cost in VO construction and query result verification. In this paper, we extend and integrate Intersection tree (I-tree) and Merkle hash-tree (MH-tree) to develop a new ADS called Intersection Function Merkle Hash-tree (IFMH-tree). We propose two versions of the IFMH-tree, one-signature and multi-signature, and study their performance in supporting three representative types of analytic queries, including top-k, range, and KNN queries. Our results show that the new technique outperforms the existing solution to a large extent.

Data outsourcing is a cost-effective solution for data owners to tackle issues such as large volumes of data, huge number of users, and intensive computation needed for data analysis. They can simply upload their databases to a cloud and let it perform all management works, including query processing. One problem with this service model is how query issuers can verify the query results they receive are indeed correct. This concern is legitimate because, as a third party, clouds may not be fully trustworthy, and as a large data center, clouds are ideal targets for hackers. There has been significant work on query result verification, but most consider only simple queries where query results can be attained by checking the raw data against the query conditions directly. In this paper, we consider the problem of enabling users to verify the correctness of the results of analytic queries. Unlike simple queries, analytic queries involve ranking functions to score a database, which makes it difficult to build data structures for verification purposes. We propose two approaches, namelyone-signatureandmulti-signature, and show that they work well on three representative types of analytic queries, includingtop-k,range, andKNNqueries, through both analysis and experiments.

Deep Neural Networks (DNNs) have demonstrated remarkable performance in a diverse range of applications. Along with the prevalence of deep learning, it has been revealed that DNNs are vulnerable to attacks. By deliberately crafting adversarial examples, an adversary can manipulate a DNN to generate incorrect outputs, which may lead catastrophic consequences in applications such as disease diagnosis and self-driving cars. In this paper, we propose an effective method to detect adversarial examples in image classification. Our key insight is that adversarial examples are usually sensitive to certain image transformation operations such as rotation and shifting. In contrast, a normal image is generally immune to such operations. We implement this idea of image transformation and evaluate its performance in oblivious attacks. Our experiments with two datasets show that our technique can detect nearly 99% of adversarial examples generated by the state-of-the-art algorithm. In addition to oblivious attacks, we consider the case of white-box attacks. We propose to introduce randomness in the process of image transformation, which can achieve a detection ratio of around 70%.

We introduce a new problem, namely, check-in time prediction where the goal is to predict the time when a given user will check-in to a location of interest. We design a novel Recurrent Spatio-Temporal Point Process (RSTPP) model for check-in time prediction. RSTPP addresses two key challenges: 1) Data scarcity due to uneven distribution of check-ins among users/locations. 2) User trajectories contain valuable information that is ignored by standard temporal point process which only considers historical event times. RSTPP is designed to learn the latent dependencies of event times over both historical events and spatio-temporal information about locations a user visited before check-in to the location of interest. We evaluate RSTPP on several real-world datasets, and it significantly outperforms state-of-the-art event time predicting techniques. Our work derives a set of practical implications that can benefit a wide spectrum of applications.

We introduce a novel check-in time prediction problem. The goal is to predict the time a user will check-in to a given location. We formulate check-in prediction as a survival analysis problem and propose a Recurrent-Censored Regression (RCR) model. We address the key challenge of check-in data scarcity, which is due to the uneven distribution of check-ins among users/locations. Our idea is to enrich the check-in data with potential visitors, i.e., users who have not visited the location before but are likely to do so. RCR uses recurrent neural network to learn latent representations from historical check-ins of both actual and potential visitors, which is then incorporated with censored regression to make predictions. Experiments show RCR outperforms state-of-the-art event time prediction techniques on real-world datasets.

We introduce a new query primitive called Function Query (FQ). An FQ operates on a set of math functions and retrieves the functions whose output with a given input satisfies a query condition (e.g., being among top k, within a given range). While FQ finds its natural uses in querying a database of math functions, it can also be applied on a database of discrete values. We show that by interpreting the database as a set of user-defined functions, FQ can achieve the same functionality as existing analytic queries such as top-k query and scalar product query. We address the challenge of efficient execution of FQ. The core of our solution is a novel data structure called Intersection-tree. Our research takes advantage of the fact that 1) the intersections of a set of continuous functions partition their domain into a number of subdomains, and 2) in each of these subdomains, the functions can be sorted based on their output. We evaluate the performance of the proposed techniques through analysis, prototyping, and experiments using both synthetic and real-world data. When querying a database of functions, our techniques scale well. When applied on a database of discrete values, our techniques are more versatile and outperform existing techniques in terms of various performance metrics.

An effective way to visualize the prediction of deep neural networks on an image is to decompose the prediction into the contribution of units (pixels or patches). In the existing works, these units are largely considered independently, thus limiting the performance of visualization. In this paper, we propose a new predication visualization method that uses super-pixel as a contribution unit. Moreover, our method takes into consideration of the interaction of adjacent super-pixels. We implement our technique and evaluate its performance with various images. Our results show its excellent performance.

We propose a Parity-based Data Outsourcing(PDO) model in this paper. This model outsources a set of raw data by associating it with a set of parity data and then distributing both sets of data among a number of cloud servers that are managed independently by different service providers. Users query the servers for the data of their interest and are allowed to perform both authentication and correction. The former refers to the capability of verifying if the query result they receive is correct (i.e., all data items that satisfy the query condition are received, and every data item received is original from the data owner), whereas the latter, the capability of correcting the corrupted data, if any. A data item may be corrupted unintentionally (e.g, because of errors in systems and/or networking) or intentionally (e.g., by malicious service providers or because of systems being compromised by hackers). Existing techniques support only query authentication, but not error correction. Moreover, they all rely on complex cryptographic techniques and require the cloud server to build verification objects. In contrast, our approach achieves both without using any encryption. It does not require to install any additional software on a cloud server and thus can take advantage of the many cloud data management services available on the market today. We address the challenges of PDO implementation, including parity coding, database encoding, data retrieval, and database insertion and deletion, and evaluate the performance potential of PDO through analysis, simulation, and prototyping. Our results indicate its excellent performance in terms of storage, communication, and computation overhead.

Consider a database where each record represents a math function. A third party is in charge of processing queries over this database and we want to provide a mechanism for users to verify the correctness of their query results. Here each query, referred to as a Function Query (FQ), retrieves the functions whose computation results with user-supplied arguments satisfy certain conditions (e.g., within a certain range). We present authentication solutions that work on a variety of functions, including univariate linear function, multivariate linear function, and multivariate high degree function. Our solutions are based on the fact that the functions can be sorted in the subdomains defined by their intersections and thus can be chained to produce a signature mesh for query result verification. We study the performance of the proposed techniques through theoretical analysis, simulation and empirical study, and include the results in this paper.

In mobile object database systems, both query issuers and queried objects are subject to location privacy intrusion. One solution to this problem is to have users reduce their location resolution when making location update. Such location cloaking allows mobile objects to achieve a desired level of protection, but may not produce accurate query results. Alternatively, one can apply cryptography techniques such as secure multiparty computation to compute the spatial relationship among mobile objects without having mobile objects to disclose their location at all. This strategy produces high quality query results, but in general are computation-intensive, especially when a large number of mobile objects are involved. In this paper, we present a hybrid approach that mitigates the above dilemma. Our idea is to compute approximate query results based on cloaked location information and then refine query results by applying homomorphic encryption. We demonstrate that this approach can be used for efficient and privacy-preserving processing of KNN queries and evaluate its performance through simulation.

When requesting location-based services, users can associate their queries with a purposely blurred location such as a circular or rectangular geographic region instead of their exact position. This strategy makes it possible for privacy protection, but presents problems in query processing. Since the server does not know a user's exact position, it has to retrieve query results for each position inside the user's cloaking region. While the server workload dramatically increases, a client downloading all query results will waste its battery power, because most of the data may be irrelevant to its query interest. This paper considers the problems of efficient processing of location-cloaked queries (LCQs). Our key observation is that queries may overlap in their cloaking regions and thus share some query results. In light of this, we propose to process queries as a batch instead of one by one independently. The technical contributions of this paper are threefold. 1) We propose to decompose queries into subqueries based on their interested region. Since the subqueries with a common region need to be processed only once, the server workload is minimized. 2) We propose a novel scheduling technique that addresses the dilemma between minimizing server latency and ensuring good fairness in query processing. 3) We present a personalized air indexing technique by which a client can filter out and download only the needed query results, thus avoiding the waste of energy in downloading irrelevant data.

This paper presents a subscription-based overlay network that supports efficient any-source multicast. The system lets users register to a central server and allows the server to incrementally build a topology graph that contains the network connections among the subscribers. With this topology graph in place, we address the challenges of minimizing network traffic and the delay incurred in broadcasting a data packet to all active subscribers. The active subscribers are organized in a directional ring, and for each of them, we find a number of predecessors and successors, the number of which depends on the subscriber's network capacity. When a node sends a packet, the packet is routed along the ring and to its successors simultaneously. To minimize the delay in data forwarding, we take network proximity into consideration when constructing ring and selecting a subscriber's successors and predecessors. In addition to being topology-aware, the proposed system also features leveraging idling nodes for data forwarding. More specifically, the subscribers who are online but not participating in application services (e.g., gaming) are recruited to reduce network traffic and further reduce data latency.

Our physical environment is a natural storage where we can store and share information. For instance, a stop sign is a piece of information implanted in a particular location. In this paper, we propose a storage underlay platform called “ELIAS” (Every Location Is A Storage) for a mobile peer-to-peer system. ELIAS enables user applications to transparently save/retrieve data items to/from a location without concerning with low-level detailed implementation. The underlying platform chooses appropriate mobile nodes to store/retrieve data items. We discuss an efficient implementation of ELIAS, and present a detailed analytical model that is validated by simulation. Finally, we show results of sensitivity analysis on a variety of factors that impact the performance of ELIAS.

For safety and privacy protection, nodes participating in ad hoc networks must keep their precise location in secret. When having to report its location (for routing purposes, etc.), a node can report only a cloaking region, a spatial region that contains its current position. Reducing location resolution has a significant impact on the applications that rely on nodes' location information. These applications can become less efficient. Some may not even function. Moreover, operations such as packet forwarding may allow an adversary to refine a node's location resolution, thus reversing the effect of location cloaking in safety and privacy protection. In this paper, we investigate these problems in the context of geographic ad hoc routing and propose a novel concept called safe link. A network link is considered safe if sending and receiving of a data packet do not allow an adversary to refine the sender and receiver's location. With this concept in place, we develop a new secure routing protocol that can work with inaccurate location and construct a routing path using only safe links. We evaluate the performance of the proposed technique under various network conditions using simulation. Detailed results are presented to provide the insight of the impact of safety and privacy protection on packet delivery.

A spatial monitoring query (SMQ) retrieves the set of mobile nodes that satisfy some spatial constraints, and provides real-time updates whenever this set of nodes changes. Efficient processing of such queries is essential to moving objects database management. Existing techniques rely on one or more central servers for query management and assume each mobile node can communicate with some server directly. These limitations prevent them from being used in application scenarios where no such server exists. This paper assumes a mobile peer-to-peer system where mobile nodes are the only computing devices, and investigates the challenges of allowing mobile nodes to collaborate in query processing. We present a cost-effective technique to process a primitive type of SMQs and then show that other types of queries can be converted into the primitive type of queries. As such, different types of queries can now be supported within a common platform and without relying on any stationary server. We also evaluate, through both mathematical analysis and simulation, the performance of the proposed platform in terms of mobile communication costs incurred in query processing.

Anonymous location information may be correlated with restricted spaces such as home and office for subject re-identification. This makes it a great challenge to provide location privacy protection for users of location-based services. Existing work adopts traditional K-anonymity model and ensures that each location disclosed in service requests is a spatial region that has been visited by at least K users. This strategy requires a user to specify an appropriate value of K in order to achieve a desired level of privacy protection. This is problematic because privacy is about feeling, and it is awkward for one to scale her feeling using a number. In this paper, we propose a feeling-based privacy model. The model allows a user to express her privacy requirement by specifying a public region, which the user would feel comfortable if the region is reported as her location. The popularity of the public region, measured using entropy based on its visitors' footprints inside it, is then used as the user's desired level of privacy protection. With this model in place, we present a novel technique that allows a user's location information to be reported as accurate as possible while providing her sufficient location privacy protection. The new technique supports trajectory cloaking and can be used in application scenarios where a user needs to make frequent location updates along a trajectory that cannot be predicted. In addition to evaluating the effectiveness of the proposed technique under various conditions through simulation, we have also implemented an experimental system for location privacy-aware uses of location-based services.

Location information is crucial to design efficient and scalable ad hoc networks, yet the exposure of such information presents them significant safety threats. This paper investigates the problem of preventing an adversary from locating (and thus destroying) nodes based on their location information revealed explicitly in communications. Our idea is to reduce location resolution to achieve a desired level of safety protection. We define the safety level of a geographic region to be the ratio of its area and the number of nodes inside it. The higher safety level a region has, the less attractive for an adversary to search over it for the nodes. Thus, when a node has to disclose its location, it can compute a cloaking box that meets a desired level of safety requirement and report that as its current location information. Although the basic idea is simple, there are several challenges to implement it. First, each cloaking box must be as small as possible in order to minimize the impact of reduced location resolution on the efficiency of network operating and applications. Second, nodes must be able to compute their cloaking boxes without having to reveal their accurate position. Finally, given a sequence of cloaking boxes, they must not be correlated to refine an area whose safety level is less than the required. This paper addresses these challenges with cost-effective solutions in the context of both stationary and mobile ad hoc networks. Our extensive performance evaluation indicates that our proposed technique is efficient in node safety protection, and does not have a significant impact on the performance of networks and applications.

Most existing cloaking techniques only focus on achieving location k-anonymity. However, maintaining location k-anonymity alone is not enough to counter query homogeneity attacks. In this paper, we first define the query l-diversity concept in location-based services, and then propose a technique to achieve query l-diversity. The proposed technique is compared with the improved Interval Cloak technique using simulation; and the extensive results indicate that our technique is better in protecting user privacy.

The advances in wireless communication and positioning technology have made it possible to collect large volumes of personal location data. While such data are useful to many organizations, making them public accessible is generally prohibited, because location data may imply sensitive private information. This paper investigates the challenges of publishing location data while preserving the location privacy of data subjects. Since location data itself may lead to subject reidentification, simply removing user identity of location data is not sufficient for anonymity preservation. To address this problem, this paper presents a novel technique that reduces location resolution to achieve a desired level of anonymity protection. The new scheme ensures K-anonymity protection and allows location data to be published as accurate as possible. More importantly, it is designed to support efficient publishing of large volumes of location data.

We present a new approach for if-anonymity protection in Location-Based Services (LBSs). Specifically, we depersonalize location information by ensuring that each location reported for LBSs is a cloaking area that contains K different footprints-historical locations of different mobile nodes. Therefore, the exact identity and location of the service requestor remain anonymous from LBS service providers. Existing techniques, on the other hand, compute the cloaking area using current locations of K neighboring hosts of the service requestor. Because of this difference, our approach significantly reduces the cloaking area, which in turn decreases query processing and communication overhead for returning query results to the requesting host. In addition, existing techniques also require frequent location updates from all nodes, regardless of whether or not these nodes are requesting LBSs. Most importantly, our approach is the first practical solution that provides K-anonymity trajectory protection needed to ensure anonymity when a mobile host requests LBSs continuously as it moves. Our solution depersonalizes a user's trajectory (a time-series of the user's locations) based on the historical trajectories of other users. We evaluate our techniques under various conditions using location data synthetically generated based on real road maps. The results show that our techniques can provide K-anonymity trajectory protection using a minimized cloaking area.

A continuous k nearest neighbor (cKNN) query is a query that continuously returns a set of k nearest moving objects (mobile hosts) to a given query point. For example, report three nearest moving sensors to a given location continuously. Most existing research efforts focus on centralized solutions. In a mobile peer-to-peer network (M-P2P), a centralized approach incurs expensive communication cost. In this paper, we propose Safe-Time - a distributed solution for cKNN given a stationary query point for M-P2P. The two key features are as follows. 1) Actual execution of a cKNN query is not needed during a safe-time period since the query result is guaranteed to remain the same during this period. 2) Once the safe-time expires, execution of a cKNN query involves only objects in a circular band of width equal to the estimated distance between the kthand the k + 1thnearest neighbors. To further reduce communication cost for dense queries, we introduce Unite-Safe-Time that executes one virtual query derived from nearby queries instead of executing each of them separately. Our simulation result shows that the proposed distributed solutions outperform a centralized solution under a range of conditions. Safe-Time incurs up to 2/3 less communication cost compared to a centralized solution. Unite-Safe-Time shows up to 1/3 less communication cost than Safe-Time in our study.

Today's Internet is incapable of handling information like a stop sign. Such information stays in a geographic region, consistently beams to the people who move into from certain direction. This paper presents a system aimed at bridging the Internet with the physical world. The hardware platform of the system consists of a central server and a set of position-aware mobile clients that communicate with the server through means of wireless networks. Each client has a capable zone, a circular region centered on its current position with a user-defined radius. Each piece of information managed by the server is a geopage, an HTML page associated with a geographic region. As clients move, they load with the geopages implanted in their surroundings. This paper identifies the technical challenges of managing a large number of geopages that spans over a large terrain with a large number of mobile clients, and proposes a cost-effective solution that minimizes mobile communication and server processing costs. We evaluate the scalability of the proposed technique with a detailed mathematical model. The accuracy of the model is verified using simulation. We have also implemented a prototype and field tested the system in several cities.

A major concern for large-scale deployment of location-based services (LBSs) is the potential abuse of their client location data, which may imply sensitive personal information. Location privacy protection is challenging because a location itself may reveal a subject's identity. To support location anonymity, existing research reduces location resolution by ensuring each location reported to a service provider is a cloaking area that contains at least K mobile nodes. This strategy is effective when each location update can be considered as an independent event. In this paper, we investigate location anonymity in the context of continuous LBSs, which require frequent location updates from service users. Knowing that a user is inside a cloaking area constrains its position in the next cloaking area. Thus, simply ensuring each cloaking area contains at least K users does not give a user K-anonymity protection. We propose to measure the anonymity degree of a cloaking area using entropy, which takes into account not only the number of the entities inside, but also their anonymity probability distribution. To find a cloaking area that can provide a given level of anonymity protection and is also as small as possible, we present a novel technique with a polynomial time complexity. The effectiveness of our techniques is studied under various conditions using location data synthetically generated using real road maps and traffic volume data. The results show that our techniques can indeed protect user anonymity at a desired level, and at the same time, minimize the size of each cloaking area, allowing users to receive high quality services.

Our physical environment is a natural storage where we are used to store and share information. A stop sign, for instance, is such a piece of information that is stored on a particular location. In this paper, we assume a fully distributed mobile networking system and investigate the challenges of enabling the system to treat its underlying geographic environment as a virtual storage disk. Specifically, our research aims at developing a platform that allows one to conceptually save/retrieve a data item to/from a location. Since this capability can be used in a broad range of applications, the proposed platform can serve as a common underlay for developing and running these applications. We propose a cost-effective implementation of this platform. For the purpose of performance evaluation, we develop a detailed analytical model and verify its accuracy using simulation.

Peer-to-peer (P2P) video systems provide a cost-effective way for a large number of hosts to collaborate for video sharing. Two features characterize such a system: 1) a video is usually available on many participating hosts, and 2) different hosts typically have different sets of videos, though some may partially overlap. From a client's perspective, it can be served by any host having the video it requests. From a server's perspective, it be used to serve any client requesting the videos it has. Thus, an important question is, which servers should be used to serve which clients in the system? In this paper, we refer to this problem as service scheduling and show that different matches between clients and servers can result in significantly different system performance. Finding a right server for each client is challenging not only because a client can choose only the servers that are within its limited search scope, but also because clients arrive at different times, which are not known a priori. In this paper, we address these challenges with a novel technique called Shaking. While the proposed technique makes it possible for a client to be served by a server that is beyond the client's own search scope, it is able to dynamically adjust the match between the servers and their pending requests as new requests arrive. Our performance study shows that our new technique can dynamically balance the system workload and significantly improve the overall system performance

Overlay multicast streaming is built out of loosely coupled end-hosts (peers) that contribute resources to stream media to other peers. Peers, however, can be malicious. They may intentionally wish to disrupt the multicast service or cause confusions to other peers. We propose two new schemes to detect malicious peers in overlay multicast streaming. These schemes compute a level of trust for each peer in the network. Peers with a trust value below a threshold are considered to be malicious. Results from our simulations indicate that the proposed schemes can detect malicious peers with medium to high accuracy, depending on cheating patterns and malicious peer percentages

This paper investigates a new problem of sharing location dependent experiences among mobile hosts in mobile adhoc networks. An experience is location and observer dependent. In other words, experiences of different people witnessing the same event may be quite different. The ability to retrieve prior experiences observed in a given area in advance is very useful for newcomers wishing to enter the same vicinity. Solving this problem is vital for important applications such as hurricane rescue missions, combat missions, and deep space or deep sea exploration. In this paper, we propose a distributed solution that lets mobile hosts share their experiences efficiently. Our simulation results show that our approach significantly outperforms a centralized approach.

We propose a framework, called overlay subscription network (OSN), for live Internet TV broadcast, where a subscriber can choose to watch at any time. This framework allows the source server to incrementally build a topology graph that contains the network connections not only from the server to each subscriber, but also among the subscribers themselves. With such a topology graph in place, we consider efficient overlay multicast for scalable OSN services. We first show that idling nodes, which do not receive video data for their own playback, can actually be used for data forwarding to significantly reduce the cost of overlay multicast. In light of this observation, we then propose a novel overlay multicast technique that distinguishes itself from existing schemes with these three aspects. First, the proposed technique is centered on the topology graph and can take advantage of the actual network connections among the subscribing nodes. Second, the new scheme is able to find and incorporate appropriate idling nodes in multicast to reduce network traffic. Third, with our approach, a node can be used in multiple multicast trees for data forwarding to improve the overall system performance. We evaluate the performance of the proposed technique through simulation. Our extensive studies show that the proposed framework has the potential to enable the Internet, a vehicle up to date mainly for transferring text and image data, for large-scale and cost-effective TV broadcast

Unlike conventional range queries, a range-monitoring query is a continuous query. It requires retrieving mobile objects inside a user-defined region and providing continuous updates as the objects move into and out of the region. In this paper, we present an efficient technique for real-time processing of such queries. In our approach, each mobile object is associated with a resident domain, and when an object moves, it monitors its spatial relationship with its resident domain and the monitoring areas inside it. An object reports its location to the server when it crosses over some query boundary or moves out of its resident domain. In the first case, the server updates the affected query results accordingly, while in the second case, the server determines a new resident domain for the object. This distributive approach achieves an accurate and real-time monitoring effect with minimal mobile communication and server processing costs. Our approach also allows a mobile object to negotiate a resident domain based on its computing capability. By having a larger resident domain, a more capable object has less of a chance of moving out of it and having to request a new one. As a result, both communication and server processing costs are reduced. Our comprehensive performance study shows that the proposed technique can be highly scalable in supporting location-based services in a wireless environment that consists of a large number of mobile devices.

Peer-to-peer (P2P) video system is characterized by two features: 1) a video is usually available on many participating hosts, and 2) different hosts typically have different sets of videos, though some may partially overlap. From a client's perspective, it can be served by any host having the video it requests. From a server's perspective, it will be used to serve any client requesting the videos it has. In this paper, we refer to the problem of who-serves-whom as service scheduling and show that different matches between clients and servers can result in significantly different system performance. Finding a right server for each client is challenging not only because a client can choose only the servers that are within its limited search scope, but also because clients arrive at different times, which are not known a priori. To address these challenges, we propose a novel technique called shaking and our performance study shows that it can effectively boost the overall system performance.

A subscription overlay network (SON) consists of a stream source server and a number of subscribing nodes that pay monthly fee to watch the program. While the video program is continuous and endless, a subscriber typically watches the program only in some time interval. Thus, a SON may have a large number of subscribing nodes, but at any one time, only a small percentage of them may be playing (i.e., receiving some program) while many others are just idling. In this paper, we consider how these idling nodes can be leveraged for constructing highly efficient overlay multicast, where clients can join and leave dynamically. Unlike regular playing nodes, an idling node should be included in a multicast tree only when doing so can improve the system performance (e.g., reducing network traffic). We address this challenge and propose a novel overlay multicast technique that is able to find and incorporate appropriate idling nodes for data forwarding. We evaluate the performance of the proposed technique through simulation, and the results confirm its performance advantages.

In this paper, we propose a new technique, called priority forwarding, for efficient and fast flooding operations in wireless ad hoc networks. The new scheme is featured by dynamic delay and priority checking. The former feature allows a host to wait as long as possible to refrain from retransmission, minimizing retransmission overhead. The priority checking feature, on the other hand, allows a flooding packet to be propagated as quickly as possible, keeping flooding latency low. Unlike many location-aided flooding techniques, priority forwarding requires each host to know only the distance of its 1-hop neighbors, instead of their exact locations. Therefore, it has low implementation cost. For performance evaluation, we compare priority forwarding with some existing techniques using simulation. Our results show that under most scenarios, the new technique performs many times better in reducing packet retransmissions and flooding latency.

Flooding is a fundamental and frequently invoked operation in wireless ad hoc networks. Existing flooding techniques either are unreliable, generate overwhelming unnecessary retransmission, or incur excessive network control overhead. In this paper, we address these crucial problems and propose a new flooding technique called edge forwarding. The new scheme minimizes the flooding traffic by leveraging location information to limit broadcast retransmission to only hosts near the perimeter of each broadcast coverage. Unlike most existing techniques, edge forwarding requires each host to track only neighboring nodes within its one-hop distance. Therefore, it is more adaptive to host mobility and incurs less network control overhead. In particular, it can be easily incorporated into many existing routing protocols without any additional control overhead. Our performance studies indicate that with our strategy, a substantial portion of the unnecessary broadcast retransmission can be eliminated.

Providing scalable video services in a peer-to-peer (P2P) environment is challenging. Since videos are typically large and require high communication bandwidth for delivery, many peers may be unwilling to cache them in whole to serve others. In this paper, the authors addressed two fundamental research problems in providing scalable P2P video services, namely (1) how a host can find enough video pieces, which may scatter among the whole system, to assemble a complete video, and (2) given a limited buffer size, what part of a video a host should cache. A new distributed video management technique was proposed. This scheme organizes hosts into a number of cells, each of which is a distinct set of hosts which together can supply a video in its entirety. A client looking for a video can stop its search as soon as it finds a host that caches any part of the video. Caching operations can be coordinated within each cell to balance data redundancy in the system. The extensive study on a Gnutella-like simulation network shows convincingly the performance advantage of the new scheme.

We consider applying the FEC-based multiple description coding method for multicasting a source to a set of clients with heterogeneous access bandwidths. In the scenario where different clients access the server via separate links, we propose a procedure which refines the already computed optimal solutions for other bandwidths, using different packet lengths. Compared to the scheme that computes an optimal solution individually for each bandwidth, this procedure is quite faster and has comparable performance. In another scenario where many clients share a bottleneck link, we extend our embedded packetization framework to be available in more than two bandwidths, and propose a fast heuristic algorithm which can achieve very good performance tradeoff among all clients.

To provide scalable video-on-demand services, precious system bandwidth must be shared among video requests. Although many efficient bandwidth-sharing techniques have been proposed, they are all designed for homogeneous receivers, i.e., the clients are assumed to have the same receiving bandwidth. For networks with client heterogeneity, these techniques either cannot work or have to compromise their performance. We address this problem and propose an efficient solution allowing each client to use its whole receiving bandwidth to download data. To serve a client, the server first selects a set of serving channels for the client according to its actual receiving bandwidth. The video data needed for this client are then scheduled and dynamically adjusted for delivery over these channels. We evaluate the performance of the new technique using simulation and compare it with an existing scheme. Our study shows that by effectively leveraging client heterogeneity, the new technique achieves significantly smaller service latency.

Periodic broadcast is a cost-effective solution for disseminating popular videos. This strategy has the potential to serve a very large community with minimal broadcast bandwidth: regardless of the number of video requests, the worst service latency to all clients is constant. Although many efficient schemes have been proposed, most of them impose some rigid requirement on client receiving bandwidth. They either demand clients to have the same bandwidth as the video server, or limit them to receive no more than two video streams at any one time. In our previous work, we addressed this problem by proposing a client-centric approach (CCA). Unlike any other technique, CCA takes both server broadcast bandwidth and client receiving bandwidth into design consideration. More specifically, CCA allows clients to use all their receiving capability for prefetching broadcast data. Therefore, given a fixed broadcast bandwidth, CCA can achieve shorter broadcast period with an improved client communication capability. In this paper, we present a novel technique to further leverage client bandwidth for more efficient video broadcast. We prove the correctness of this new technique and provide analytical evaluations to show that with the same client bandwidth, it achieves significantly better performance than CCA.

We consider in this paper how to leverage heterogeneous mobile computing capability for efficient processing of real-time range-monitoring queries. In our environment, each mobile object is associated with a resident domain and when an object moves, it monitors its spatial relationship with its resident domain and the monitoring areas inside it. An object reports its location to server whenever its movement affects any query results (i.e., crossing any query boundaries) or it moves out of its resident domain. In the first case, the server updates the affected query results accordingly while in the second case, the server determines a new resident domain for the object. This distributive approach is able to provide accurate query results and real-time monitoring updates with minimal location update and server processing costs. In addition, the new scheme allows a mobile object to negotiate a resident domain based on its computing capability. Thus, a more capable object can have a larger resident domain reducing its chance of having to request a new resident domain because of moving out of it. This feature makes the new approach highly adaptive to the heterogeneity of mobile objects. In our performance study, we compare it with an existing approach using simulation. The study shows that the new technique is many times better in reducing mobile communication and server processing costs.

Patching is a cost efficient channel-sharing technique for video-on-demand systems. However, its performance is limited due to the fact that a video stream cannot be shared unless it delivers the video in its entirety. As a result, larger and larger patches are required to serve new requests as the temporal distance increases. To avoid the overwhelming accumulation of patching cost, the entire video must be delivered frequently. In this paper, we address this problem by introducing a new technique called Transition Patching. Our performance study shows that the new scheme outperforms the existing approach under all scenarios. In particular, the performance gain is more significant when the request rate is higher. We note that such improvement is achieved without extra download bandwidth required at the client site. The implementation cost, therefore, is the same as the original Patching scheme.

Several periodic broadcasting schemes have been shown to be very effective in addressing the bandwidth limitation in multimedia servers. Since this approach allows many users to share a server stream, its bandwidth requirement is independent of the number of users the system is designed to support. Existing broadcasting schemes use two or less download channels at the client end to receive data. We discuss the drawbacks of this approach, and propose a new technique which allows a video session to download data through several client channels. The number of channels which can be used simultaneously is limited only by the communication capability of the client system. We prove the correctness of this client-centric approach, and provide analytical evaluations to show that it has significantly better performance than skyscraper broadcasting technique which has been shown to offer the best performance to date.

Until now, true video-on-demand can only be achieved using a dedicated data flow for each sen-ice request. This brute- force approach is prohibitively expensive. Using multicast can significantly reduce the system cost. This solution, however, must delay services in order to serve many requests as a batch. In this paper, we consider a third alternative called Patching. In our technique, an existing multicast can expand dynamically to serve new clients. Allowing new clients to join an existing multicast improves the efficiency of the multicast. Furthermore, since all requests can be served im-mediately, the clients experience no service delay and true video-on-demand can be achieved. A significant contribution of this work, is making multicast work for true video- on-demand services. In feet, we are able to eliminate the service latency and improve the efficiency of multicast at the same time. To assess the benefit of this scheme, we perform simulations to compare its performance with that of standard multicast. Our simulation results indicate convincingly that- Patching offers substantially better performance. © 1998 ACM.