Existing methods for readability assessment usually construct inductive classification models to assess the readability of singular text documents based on extracted features, which have been demonstrated to be effective. However, they rarely make use of the interrelationship among documents on readability, which can help increase the accuracy of readability assessment. In this article, we adopt a graph‐based classification method to model and utilize the relationship among documents using the coupled bag‐of‐words model. We propose a word coupling method to build the coupled bag‐of‐words model by estimating the correlation between words on reading difficulty. In addition, we propose a two‐view graph propagation method to make use of both the coupled bag‐of‐words model and the linguistic features. Our method employs a graph merging operation to combine graphs built according to different views, and improves the label propagation by incorporating the ordinal relation among reading levels. Experiments were conducted on both English and Chinese data sets, and the results demonstrate both effectiveness and potential of the method.

In this paper, we present a method which learns the word embedding for readability assessment. For the existing word embedding models, they typically focus on the syntactic or semantic relations of words, while ignoring the reading difficulty, thus they may not be suitable for readability assessment. Hence, we provide the knowledge-enriched word embedding (KEWE), which encodes the knowledge on reading difficulty into the representation of words. Specifically, we extract the knowledge on word-level difficulty from three perspectives to construct a knowledge graph, and develop two word embedding models to incorporate the difficulty context derived from the knowledge graph to define the loss functions. Experiments are designed to apply KEWE for readability assessment on both English and Chinese datasets, and the results demonstrate both effectiveness and potential of KEWE.

Cross project defect prediction (CPDP) is a challenging task since the predictor built on the source projects can hardly generalize well to the target project. Previous studies have shown that both feature mapping and feature selection can alleviate the differences between the source and target projects. In this paper, we propose a novel method FeSCH (Feature Selection using Clusters of Hybrid-data). In particular it includes two phases. The first is the feature clustering phase, which uses a density-based clustering method DPC to group highly co-related features into clusters. The second is the feature selection phase, which selects beneficial features from each cluster. We design three ranking strategies to choose appropriate features. During the empirical studies, we design experiments based on real-world software projects, and evaluate the prediction performance of FeSCH by analyzing the influence of ranking strategies. The experimental results show that FeSCH can outperform three baseline methods (i.e., WPDP, ALL, and TCA+) in most cases, and its performance is independent of the used classifiers.

Software fault prediction is a valuable exercise in software quality assurance to best allocate limited testing resources. Classification is one of the effective methods for software fault prediction. The classification models are trained based on the datasets obtained by mining software historical repositories. However, the performance of the models depends on the quality of datasets. In this paper, we propose a novel two-stage data preprocessing approach which incorporates both feature selection and instance reduction. Specifically, in the feature selection stage, we first perform relevance analysis, and then propose a threshold-based clustering method, called novel threshold-based clustering algorithm, to conduct redundancy control. In the instance reduction stage, we apply random under-sampling to keep the balance between the faulty and non-faulty instances. In empirical studies, we chose datasets from real-world software projects, such as Eclipse and NASA. Then we compared our approach with some classical baseline methods, and further investigated the influencing factors in our approach. The final results demonstrate the effectiveness of our approach, and provide a guideline for achieving cost-effective data preprocessing when using our two-stage approach.

Noises are inevitable when mining software archives for software fault prediction. Although some researchers have investigated the noise tolerance of existing feature selection methods, few studies focus on proposing new feature selection methods with a certain noise tolerance. To solve this issue, we propose a novel method FECS (FEature Clustering with Selection strategies). This method includes two phases: a feature clustering phase and a feature selection phase with three different heuristic search strategies. During empirical studies, we choose real-world software projects, such as Eclipse and NASA and inject class level and feature level noises simultaneously to imitate noisy datasets. After using classical feature selection methods as the baseline, we confirm the effectiveness of FECS and provide a guideline of using FECS after analyzing the effects of varying either the percentage of selected features or the noise rate.

This paper proposes a graph-based readability assessment method using word coupling.Compared to the state-of-theart methods such as the readability formulae, the word-based and feature-based methods, our method develops a coupled bag-of-words model which combines the merits of word frequencies and text features.Unlike the general bag-of-words model which assumes words are independent, our model correlates the words based on their similarities on readability.By applying TF-IDF (Term Frequency and Inverse Document Frequency), the coupled TF-IDF matrix is built, and used in the graph-based classification framework, which involves graph building, merging and label propagation.Experiments are conducted on both English and Chinese datasets.The results demonstrate both effectiveness and potential of the method.

With the increasing number of location-dependent applications, positioning and tracking a mobile device becomes more and more important to enable pervasive and context-aware service. While extensive research has been performed in physical localization and logical localization for satellite, GSM and WiFi communication networks where fixed reference points are densely-deployed, positioning and tracking techniques in a sparse disruption tolerant network (DTN) have not been well addressed. In this paper, we propose a decentralized cooperative method called PulseCounting for DTN localization and a probabilistic tracking method called ProbTracking to confront this challenge. PulseCounting evaluates the user walking steps and movement orientations using accelerometer and electronic compass equipped in cellphones. It estimates user location by accumulating the walking segments, and improves the estimation accuracy by exploiting the encounters of mobile nodes. Several methods to refine the location estimation are discussed, which include the adjustment of trajectory based on reference points and the mutual refinement of location estimation for encountering nodes based on maximum-likelihood. To track user movement, the proposed ProbTracking method uses Markov chain to describe movement patterns and determines the most possible user walking trajectories without full record of user locations. We implemented the positioning and tracking system in Android phones and deployed a testbed in the campus of Nanjing University. Extensive experiments are conducted to evaluate the effectiveness and accuracy of the proposed methods, which show an average deviation of 9m in our system compared to GPS.

Software defect prediction can classify new software entities into either buggy or clean. However the effectiveness of existing methods is influenced by irrelevant and redundant features. In this paper, we propose a new feature selection framework FECAR using Feature Clustering And feature Ranking. This framework firstly partitions original features into k clusters based on FF-Correlation measure. Then it selects relevant features from each cluster based on FC-Relevance measure. In empirical study, we choose Symmetric Uncertainty as FF-Correlation measure, and choose Information Gain, Chi-Square, and Relief as three different FC-Relevance measures. Based on some real projects Eclipse and NASA, we implemented our framework and performed empirical studies to investigate the redundancy rate and the performance of the trained defect predictors. Final results verify the effectiveness of our proposed framework and further provide a guideline for achieving cost-effective feature selection when using our framework.

Location privacy preservation has become an important issue in providing location based services (LBSs). When the mobile users report their locations to the LBS server or the third-party servers, they risk the leak of their location information if such servers are compromised. To address this issue, we propose a Location Privacy Preservation Scheme (LPPS) based on distributed cache pushing which is based on Markov Chain. The LPPS deploys distributed cache proxies in the most frequently visited areas to store the most popular location-related data and pushes them to mobile users passing by. In the way that the mobile users receive the popular location-related data from the cache proxies without reporting their real locations, the users' location privacy is well preserved, which is shown to achieve k-anonymity. Extensive experiments illustrate that the proposed LPPS achieve decent service coverage ratio and cache hit ratio with low communication overhead.

With the rapid proliferation of Wi-Fi technologies in recent years, it has become possible to utilize the vehicular wireless network to assist the route guidance for drivers in a cooperative approach, aiming to mitigating heavy traffic congestion. In this paper, we investigate into the route guidance problem in vehicular wireless network, and then propose two efficient routing algorithms, i.e., centralized route guidance and distributed route guidance, according to different situations. A hybrid framework is then proposed to provide optimized routing decisions in a uniform way. Simulation results in Simulation of Urban MObility (SUMO) indicate that, our route guidance schemes achieve much better performance than traditional GPS-based navigation and randomized routing.

In wireless sensor networks, the connectivity-based localization protocols are widely studied due to low cost and no requirement for special hardware. Many connectivity-based algorithms rely on distance estimation between nodes according to their hop count, which often yields large errors in anisotropic sensor network. In this paper, we propose a virtual potential field algorithm, in which the estimated positions of unknown nodes are iteratively adjusted by eliminating the inconsistency to the connectivity constraint. Unlike current connectivity-based algorithms, VPF effectively exploits the connectivity constraint information, regardless of distance estimation between nodes, thus achieving high localization accuracy in both isotropic and anisotropic sensor networks. Simulation results show that VPF improves the localization accuracy by an average of 47% compared with MDS in isotropic network, and 42% compared with PDM in anisotropic network. As a refinement procedure, the average improvement factor of VPF is 56% and 50%, based on MDS and PDM respectively.

With the rapid proliferation of RFID technologies, RFID has been introduced to the applications like safety inspection and warehouse management. Conventionally a number of deployment rules are specified for these applications. This paper studies a practically important problem of rule checking over a large set of RFID tags, i.e., checking whether the specified rules are satisfied according to the RFID tags within the monitoring area. This rule checking function may need to be executed frequently over a large number of tags and therefore should be made efficient in terms of execution time. Aiming to achieve time efficiency, we propose two efficient protocols based on the collision detection and the logical features of rules, respectively. Simulation results indicate that our protocols achieve much better performance than other solutions in terms of time efficiency.

Classification based software fault prediction methods aim to classify the modules into either fault-prone or non-fault-prone. Feature selection is a preprocess step used to improve the data quality. However most of previous research mainly focus on feature relevance analysis, there is little work focusing on feature redundancy analysis. Therefore we propose a two-stage framework for feature selection to solve this issue. In particular, during the feature relevance phase, we adopt three different relevance measures to obtain the relevant feature subset. Then during the feature redundancy analysis phase, we use a cluster-based method to eliminate redundant features. To verify the effectiveness of our proposed framework, we choose typical real-world software projects, including Eclipse projects and NASA software project KC1. Final empirical result shows the effectiveness of our proposed framework.

In this paper, we show the first comprehensive experimental study on mobile RFID reading performance based on a relatively large number of tags. By making a number of observations regarding the tag reading performance, we build a model to depict how various parameters affect the reading performance. Through our model, we have designed very efficient algorithms to maximize the time-efficiency and energy-efficiency by adjusting the reader's power and moving speed. Our experiments show that our algorithms can reduce the total scanning time by 50\% and the total energy consumption by 83\% compared to the prior solutions.

In recent years, there has been an increasing interest in the adoption of wireless sensor networks (WSNs) for structural health monitoring (SHM). However, considering the large amount of sampled data, limited power supply and wireless bandwidth of WSNs, it is generally not possible for sensor nodes to monitor structural condition continuously especially for long-term SHM. From SHM perspective, it is highly desirable to collect data during the occurrence of some certain kinds of events such as earthquakes, large wind, etc, since data collected during these periods are more informative for damage detection purpose. However, these events in SHM occur infrequently and if happen, only last for a very short period of time. To effectively capture these short events using energy-limited wireless sensor nodes is a challenging task that has not been addressed in literature. In this paper, we propose a fast and reliable scheme to capture these short-term events. In terms of hardware, the radio-triggered unit and the vibration-triggered unit are designed in our motes. From software perspective, we develop the event capture scheme to realize fast, reliable and energy-efficient event detection under noisy environment. We mainly study the very first problem of the scheme: sentry selection. The optimization problem is formulated and we show that the problem is a general case of the classical k-center problem. Then we propose a greedy algorithm to solve this problem, and conduct simulation to test the effectiveness of the proposed algorithm.

Vehicular Ad Hoc Networks (VANETs) enable car-to-car communication without the support of network infrastructure, which introduce diverse application possibilities and have drawn much attention from academy and industry in the past years. Unlike other ad hoc networks, nodes in VANETs are restricted to move in streets and have limited communication ranges. Intuitively, vehicle-to-vehicle communication somehow has similarity to human-to-human interaction, which lead to an interesting question of exploring the social properties of VANET nodes. To address the question, we consider encounters of vehicles as their social relationships and model VANETs as social graphs. Based on the social graph model, we use two traces of mobile vehicles from San Francisco and Shanghai to explore their social properties. Our analysis show that several universal laws of social network are hold for VANETs. The social graphs forming by vehicles are scale-free networks with power-law like distribution of node degrees. Small world phenomenon is also observed in our experiments: the nodes in VANETs have high cluster coefficient and there exist short paths between node pairs less than 3 hops on average. The implication of our analytical results is of benefit to develop large scale software system for mobile applications such as VANETs, as well as helps to facilitate inter-device wireless communications in pervasive environment.

It is a tedious task to search and locate a specific book from massive number of books arbitrarily placed in a bookshelf. In this paper, we demonstrate iBookshelf, a system which allows users to quickly search and accurately locate books in the bookshelf, by leveraging a passive RFID system. By deploying a number of reference tags on the bookshelf, we are able to perform localization based on the similarities in received signal strength, and effectively offset the impact from the ambient noises and interferences. We deploy and evaluate our system in a real 3m x 2.5m bookshelf, and show that users are able to locate the book from our Android-based application with 85% accuracy.

In recent years, researchers have paid more attention to influence maximization problem. This problem is firstly defined by Domingos and Richardson as follows: finding a small set of individuals in a social network that could maximize the spread of influence under certain influence cascade model. To solve this issue, researchers proposed different algorithms. However, in all of these algorithms, the size of the chosen individuals -k, is assigned in advance. In this paper, we conduct a preliminary exploration on the relationship between the size of the chosen set and the corresponding influence spread. We propose two metrics to analyze the factor k. Then we further consider the performance metric of the chosen set, which can be described by the stability of the chosen set. Experimental results on two real social networks show the efficiency and necessity of our proposed metrics.

Femtocell network is an efficient configuration to improve coverage and quality of service (QoS) in cellular networks. However, due to dense deployment, users in a femtocell may be interfered by the base stations nearby, resulting in a deteriorated throughput of the femtocell. In this paper, we investigate the resource allocation problem targeting at max-min throughput of the femtocells. Under the assumption that a number of discrete power levels are available for each device, a joint optimization problem over power control and channel allocation is formulated. We show its hardness and propose a particle swarm optimization based algorithm PCASO. We demonstrate the efficiency of PCASO by thorough numerical experiments.

Peer-to-peer (P2P) overlay-based streaming services have became more and more attractive. However, it is still challenging to provide scalable streaming services over large-scale Internet environment beacause of the stringent quality of service requirements as well as the dynamic nature of P2P overlay network. In this study, the authors focus on the optimisation of streaming data scheduling in P2P video-on-demand (VoD) system, with the objective of minimising the server stress and maximising the playback continuity. The authors first model the data scheduling problem to the maximum network flow problem where the schedule scheme is transformed to find an optimal supplier-consumer relationship assigment among peers with minimal server strees, and then present two max-flow-based streaming data scheduling algorithms by combining the upload capacity of peers as well as the path capacity between peers. The authors prove that the computing complexing of the proposed scheduling algorithms is polynomial. The practicability of the proposal is evaluated via simulations. Simulation results indicate that the proposed scheduling scheme could distribute bandwidth load among peers well while keeping the node degree low. Simulation results also show that the novel proposal has better performance than previous work in term of the server stress and the playback continuity.

Sensor networks nowadays are widely used for structural health monitoring; for example, the sensor monitoring system deployed on the Guangzhou New TV Tower, China. While wired systems still dominate, it is commonly believed that wireless sensors will play a key role in the near future. One key difficulty for such systems is the data transmission from the sensor nodes to the base station. Given the long span of the civil structures, neither a strategy of long-range one-hop data transmission nor short-range hop-by-hop communication is cost-efficient. In this paper, we propose a novel scheme of using the elevators to assist data collection. A base station is attached to an elevator. A representative node on each floor collects and transmits the data to the base station using short range communication when the elevator stops at or passes by this floor. As such, communication distance can be minimized. To validate the feasibility of the idea, we first conduct an experiment in an elevator of the Guangzhou New TV Tower. We observe steady transmission when elevator is in movement. To maximize the gain, we formulate the problem as an optimization problem where the data traffic should be transmitted on time and the lifetime of the sensors should be maximized. We show that if we know the movement pattern of the elevator in advance, this problem can be solved optimally. We then study the online version of the problem and show that no online algorithm has a constant competitive ratio against the offline algorithm. We show that knowledge of the future elevator movement will intrinsically improve the data collection performance. We discuss how the information could be collected and develop online algorithms based on different level of knowledge of the elevator movement patterns. Theoretically, given that the links capacity assumptions we made, we can prove that our online algorithm can guarantee data delivery on time. In practice, we may set a buffer zone to minimize the possible data delivery violation. A comprehensive set of simulations and MicaZ testbed experiments have demonstrated that our algorithm substantially outperforms conventional multihop routing and naive waiting for elevator scheme. The performance of our online algorithm is close to the optimal offline solution.

Service composition is a useful technology to achieve dynamic requests. But in cloud, the cloud provider should guarantee the QoS of the user request as well. Previous work investigated how to select proper available replicas (the similar functional services located on different physical nodes) to effectively achieve the composite services. However, as the requirements for some service grow, even the optimal selection strategy could not satisfy all the QoS requests, if it is only based on the existed replicas. In this case, cloud provider should deploy more replicas to meet the growing requests. Some existing literatures have addressed the service redeployment problem, aiming to optimize the overall or average performance; however, few of them can guarantee QoS of each request. This paper investigates QoS-aware service redeployment problem (SRP), with objective to minimize the redeployment cost. We show that, it is NP-hard to decide whether there exists a feasible solution of SRP. Thus we propose a novel heuristic algorithm SRA, which can find a solution such that most of the requests can be satisfied, while the deployment cost is minimized. Experimental results show that our approach is effective and efficient.

Deploying road-side WiFi access points has made possible internet access in a vehicle, nevertheless it is challenging to maintain client performance at vehicular speed especially when multiple mobile users exist. This paper considers the association control problem for vehicular WiFi access in the Drive-thru Internet scenario. In particular, we aim to improve the efficiency and fairness for all users. We design efficient algorithms to achieve these objectives through several techniques including approximation. Our simulation results demonstrate that our algorithms can achieve significantly better performance than conventional approaches.

Combinatorial testing (also called interaction testing) is an effective specification-based test input generation technique. By now most of research work in combinatorial testing aims to propose novel approaches trying to generate test suites with minimum size that still cover all the pairwise, triple, or n-way combinations of factors. Since the difficulty of solving this problem is demonstrated to be NP-hard, existing approaches have been designed to generate optimal or near optimal combinatorial test suites in polynomial time. In this paper, we try to apply particle swarm optimization (PSO), a kind of meta-heuristic search technique, to pairwise testing (i.e. a special case of combinatorial testing aiming to cover all the pairwise combinations). To systematically build pairwise test suites, we propose two different PSO based algorithms. One algorithm is based on one-test-at-a-time strategy and the other is based on IPO-like strategy. In these two different algorithms, we use PSO to complete the construction of a single test. To successfully apply PSO to cover more uncovered pairwise combinations in this construction process, we provide a detailed description on how to formulate the search space, define the fitness function and set some heuristic settings. To verify the effectiveness of our approach, we implement these algorithms and choose some typical inputs. In our empirical study, we analyze the impact factors of our approach and compare our approach to other well-known approaches. Final empirical results show the effectiveness and efficiency of our approach.

Replication is a widely used technique in unstructured overlays to improve the content availability or the system performance. Among the prior work on replication, a fundamental question is often addressed: how many replicas should be kept for each data item if given the fixed request rates and the limited storage capability? The Square-Root Replication, in which the replica number of an item is proportional to the square root of its global request rate and proportional to its item size, is usually considered to be optimal as far as the minimization of the search size is concerned. However, our work shows that this viewpoint is not always true, especially in the realistic environments. Firstly, we hold that the replica number should be inversely proportional to the square root of the item size in the optimal replication under the theoretical settings. Secondly, the Square-Root Replication is not optimal when TTL (Time to Live) is small or replica density is low in the practical applications. In this paper, we firstly formulate the questions and present the formal proofs, and finally provide some simulations to validate our conclusions.

Media streaming services have been much more popular nowadays, and these services consume lots of network bandwidth. Peer-to-Peer(P2P) technology has been employed in the streaming systems to save the server bandwidth consumption and enhance the system scalability. In a P2P streaming system, the quality of the data scheduling scheme will largely affect the server stress that being saved. In this paper, we present our optimal data scheduling scheme to achieve both server stress minimization and fairness among users when the playback continuities of the users are guaranteed. The data scheduling scheme we proposed is based on the maximum network flow problem, and it is proved to be polynomial. Simulations also show that the time consumption for the computation of the optimal scheduling is acceptable, and the result of the scheduling also achieves small node degree bound which makes it practical.

Finding effective approaches to detect vulnerabilities is important to guarantee the security of Web applications. Web application security issues are mostly related to malicious input data and Web forms are the main interface to input these data. According to the above observation, we propose a novel approach to detect Web application vulnerabilities. In our approach, given a URL, we get a target Web form. After analyzing characteristics of this Web form, we assign a set of test values to each field in this form. Then we propose a method to generate test suites taking the weight of each test value into account. Finally, we execute these test suites and analyze corresponding result based on HTTP response code and response HTML. We implement our approach into a tool called D-WAV and choose several Web applications as benchmarks to conduct empirical studies. Final results show that our approach can automatically and effectively discover Web application vulnerabilities such as cross-site scripting and SQL injection.

In this paper we consider how to efficiently identify tags on the moving conveyor. Considering conditions like the path loss and multi-path effect in realistic settings, we first propose a probabilistic model for RFID tag identification. Based on this model, we propose efficient solutions to identify moving RFID tags, according to the fixed-path mobility on the conveyor. A dynamic program based solution and an adaptive solution are proposed to select optimized frame sizes during the query cycles. Simulation results indicate that by leveraging the probabilistic model our solutions can achieve much better performance than using parameters for the ideal propagation situations.

A lot of network services and applications are being designed to support quality-of-service (QoS) routing. One of the key problems is to find a feasible path that satisfies multiple QoS requirements, i.e., Multi-Constrained Path (MCP) problem which is known to be NP-complete. Many heuristic and approximation algorithms have been proposed to solve this problem. However, most of them converted it into the classic shortest path problem by transforming multiple QoS weights into single weight. In this paper, we propose a binary graph reduction (BGR) algorithm to convert network graph into a simplified graph by removing redundant edges before constructing a routing path. BGR improves system performance from two aspects: i) BGR decreases the decision-making time, which then decreases the delay of end users; ii) BGR removes some abnormal anti-heuristic redundant edges from network graph, so that the actual routing algorithm could get a better result. We use a multimedia delivery system to illustrate these advantages in this paper. Simulation results also approve the efficiency of the proposed BGR algorithm.

Test suite reduction can greatly save the test effort during regression testing. For software development with frequent minor updates, a good policy is to managing selective form regression testing, where the total set of test requirements is divided into two subsets: one is the set of concerned test requirements which ought to be covered by selected regression test cases; the other is the set of irrelevant test requirements which should be avoided to save the test case execution and analysis effort, enable missing parts and stubs, or avoid failure protecting codes. We define the multi-objective test suite reduction to model the selective coverage test suite reduction problem, and put forward the HATS algorithm to solve it. Within the HATS, the weighting factor α is defined to balance the two selecting criteria for each test case: maximizing the number of concerned requirements covered, or minimizing the number of irrelevant requirements involved. Experimental results show that compared with the total-coverage test suite reduction techniques, with proper settings of α, the HATS can further decrease the size of the regression test bucket, and cut down the coverage of irrelevant test requirements, while only slightly compromise the fault detection capability against the set of concerned test requirements.

Interactive wireless applications, like VoIP over wireless networks, desire high-quality links and smooth connectivity during user movement. In order to support seamless roaming in wireless networks, handoff optimization has attracted a lot of attention recently. Most existing approaches aim at reducing handoff latency in communication protocols. While these methods provide significant savings in handoff latency, frequent handoffs could still be crucial and problematic for interactive applications. In this paper, we propose a new perspective for handoff optimization by introducing navigation guidance to minimize the handoff frequency. We first formulate the navigation-driven handoff minimization problem, then propose an optimal algorithm and a localized algorithm to solve it. The optimal algorithm assumes global knowledge of AP locations and uses a navigation graph to find a minimal handoff frequency path. The localized algorithm, however, only uses neighbor AP locations for route selection, which is more practical in real applications. Implementation issues of the proposed algorithms are discussed and simulations based on real world AP deployment are used to evaluate their performance. Experiment results show that our algorithms reduce handoff frequency by at most 42% compared to existing strategies.

Existing localization algorithms for mobile sensor networks are usually based on the Sequential Monte Carlo (SMC) method. They either suffer from low sampling efficiency or require high beacon density to achieve high localization accuracy. Although papers can be found for solving the above problems separately, there is no solution which addresses both issues. In this paper, we propose an energy efficient algorithm, called WMCL, which can achieve both high sampling efficiency and high localization accuracy in various scenarios. In existing algorithms, a technique called bounding-box is used to improve the sampling efficiency by reducing the scope from which the candidate samples are selected. WMCL can further reduce the size of a sensor node's bounding-box by a factor of up to 87 percent and, consequently, improve the sampling efficiency by a factor of up to 95 percent. The improvement in sampling efficiency dramatically reduces the computational cost. Our algorithm uses the estimated position information of sensor nodes to improve localization accuracy. Compared with algorithms adopting similar methods, WMCL can achieve similar localization accuracy with less communication cost and computational cost. Our work has additional advantages. First, most existing SMC-based localization algorithms cannot be used in static sensor networks but WMCL can work well, even without the need of experimentally tuning parameters as required in existing algorithms like MSL*. Second, existing algorithms have low localization accuracy when nodes move very fast. We propose a new algorithm in which WMCL is iteratively executed with different assumptions on nodes' speed. The new algorithm dramatically improves localization accuracy when nodes move very fast. We have evaluated the performance of our algorithm both theoretically and through extensive simulations. We have also validated the performance results of our algorithm by implementing it in real deployed static sensor networks. To the best of our knowledge, we are the first to implement SMC-based localization algorithms for wireless sensor networks in real environment.

Interaction testing (also called combinatorial testing) is an cost-effective test generation technique in software testing. Most research work focuses on finding effective approaches to build optimal t-way interaction test suites. However, the strength of different factor sets may not be consistent due to the practical test requirements. To solve this problem, a variable strength combinatorial object and several approaches based on it have been proposed. These approaches include simulated annealing (SA) and greedy algorithms. SA starts with a large randomly generated test suite and then uses a binary search process to find the optimal solution. Although this approach often generates the minimal test suites, it is time consuming. Greedy algorithms avoid this shortcoming but the size of generated test suites is usually not as small as SA. In this paper, we propose a novel approach to generate variable strength interaction test suites (VSITs). In our approach, we adopt a one-test-at-a-time strategy to build final test suites. To generate a single test, we adopt ant colony system (ACS) strategy, an effective variant of ant colony optimization (ACO). In order to successfully adopt ACS, we formulize the solution space, the cost function and several heuristic settings in this framework. We also apply our approach to some typical inputs. Experimental results show the effectiveness of our approach especially compared to greedy algorithms and several existing tools.

Since automated fault localization can improve the efficiency of both the testing and debugging process, it is an important technique for the development of reliable software. This paper proposes a novel fault localization approach based on multi-level similarity of execution traces, which is suitable for object-oriented software. It selects useful test cases at class level and computes code suspiciousness at block level. We develop a tool that implements the approach, and conduct empirical studies to evaluate its effectiveness. The experimental results show that our approach has the potential to be effective in localizing faults for object-oriented software.

Broadcast is a fundamental operation of wireless ad hoc networks (WANET) and has been widely studied in the last decade. However, very few existing broadcasting strategies has considered the scenarios with sleeping schedule, which is a prevalent power-saving method in wireless networks. In this paper we study the sleeping schedule-aware minimum latency broadcast (MLB-SA) problem in WANETs and prove its NP-hardness. By constructing a shortest path tree (SPT) defined with the latency function on the network, we derive a lower bound on the broadcast latency theoretically. Following the top-down layered approach and using the D2-coloring solution, we proposed two progressively improved algorithms: the simple layered coloring algorithm (SLAC) and the enhanced layered coloring algorithm (ELAC) for the MLB-SA problem. The SLAC has an approximation ratio of O(Delta2+ 1) where Delta is maximum degree of the network, while the ELAC has constant approximation ratio of 24|T| + 1 where |T| is the number of timeslots in a scheduling period. The two algorithms have O(n2) and O(n3) time complexities respectively. The performance of the proposed algorithms are evaluated by simulations.

Maintaining cache consistency in mobile environment is an important issue which is extensively studied in the last decade. In mobile ad hoc networks (MANETs), a large number of nonstationary mobile terminals connect with each other through multi-hop unreliable communication channels, coupling with the fact that disconnections from the network are very frequent. Most existing cache consistency strategies assume reliable communication between mobile terminals, which cannot handle frequently offline devices adequately. In this paper, we introduce the probabilistic cache consistency model for applications not requiring strong consistency. Based on this model, a probability consistency strategy (ProP) for frequently offline devices in MANETs is studied. ProP is a randomized pull-based Strategy. It is demostrated to guarantee cache consistency with a high probability. A theoretical model is developed to investigate the performance of the proposed cache consistency strategies, and design guidelines are provided for ProP to choose proper system parameters to achieve probabilistic cache consistency.

Sleep scheduling protocols are widely used in wireless sensor networks for saving energy in sensor nodes. However, without considering the special requirements of object tracking, conventional sleep scheduling protocols may lead to intolerable degradation of tracking qualities when they are used in object tracking applications. To handle this problem, sleep scheduling protocols tailed for object tracking have been proposed recently. For saving energy while maintaining satisfactory tracking qualities, these protocols pro-actively awaken sensors according to the prediction of objects' movement. Such sleep scheduling protocols are called the prediction-based sleep scheduling protocols. Most existing prediction-based sleep scheduling protocols require sensor nodes to know the locations of themselves, which may not always be available. In this paper we propose a Location-free Prediction-based Sleep Scheduling protocol (LPSS) for object tracking in sensor networks. LPSS guarantees the coverage level, an important tracking quality in most applications, which is defined as the number of sensors simultaneously detecting the object. In LPSS, when a sensor detects the object, it will emit a signal, namely the sensing stimulus. Sensors decide to wake up or not based on only the received sensing stimulus, the prediction models and the required coverage level, without the requirement of location information. We implement LPSS with two most popular prediction models: the Circle-based and the Probability-based prediction models. Experiment results show that LPSS not only provides qualified coverage levels, but also saves about 40% to 70% energy compared with existing location-free protocols. Moreover, the energy cost of LPSS is close to the ideal approach using accurate location information in terms of the number of awakened nodes.

Deploying city-wide 802.11 access points has made possible internet access in a vehicle, nevertheless it is challenging to maintain client performance at vehicular speed especially when multiple mobile users exist. This paper considers the association control problem for vehicular networks in drive-thru Internet scenarios. In particular, we aim to improve the overall throughput and fairness for all users. We design efficient algorithms to achieve the objectives through several techniques including approximation. Our simulation results confirm the performance of our algorithms.

This paper presents the design of a decentralized storage scheme to support multi-dimensional range queries over sensor networks. We build a distributed k-d tree based index structure over sensor network, so as to efficiently map high dimensional event data to a two-dimensional space of sensors while preserving the proximity of events. We propose a dynamic programming based methodology to control the granularity of the index tree in an optimized approach, and an optimized routing scheme for range query processing to achieve best energy efficiency. The simulation results demonstrate the efficiency of the design.

Providing continuous on-demand streaming services with VCR functionality over ubiquitous environments is challenging due to the stringent QoS requirements of streaming service as well as the dynamic characteristics of both underlying network and user behavior. In this paper, we propose SkipStream, a skip graph based peer-to-peer (P2P) on-demand streaming scheme with VCR support to address the above challenges. In the design of SkipStream, we first group users into a set of disjoint clusters in accordance with their playback offset and further organize the resulted clusters into a skip graph based overlay network. In addition, we present a distributed on-demand streaming scheduling mechanism to minimize the impact of VCR operations and balance system load among nodes adaptively. The average search latency of SkipStream is O(log(N)) where N is the number of disjoint clusters. We also evaluate the performance of SkipStream via extensive simulations. Experimental results show that SkipStream outperforms early skip list based scheme DSL by reducing the search latency 20%-60% in average case and over 50% in worst case.

Media streaming service over Internet has become more and more popular in recent years, with the emerging applications like Internet TV and VOD (Video on Demand) systems. In the context of pervasive computing, media streaming service is supposed to be available anytime and anywhere. In order to achieve pervasive media service, one of the most important issue is application migration, that is, migrating live streaming from one device to another without interruption. For example, people can watch football games in a moving car, and migrate the video to a pocket PC when leaving the car, and then continue enjoying the game in a TV screen after coming home. In this paper, we will address the technical issues for seamless media streaming migration in pervasive environment.

Service composition is a useful technique to assemble light, independent services to meet the complicated and dynamic requirements. Previous research has addressed the quality-of-service (QoS) aware composition path selection problem. However, as the requests growing, the selected service composition path may violate the QoS requirements. In this case, more service replicas should be deployed on suitable nodes to improve the QoS. But which service component should be selected and where these service replicas should be deployed is a challenge. In this paper, we make a deep study on this service replication problem. We give a detailed description of service replication triggering time. And then, we propose LDCS (Longest Delay Service Component Selection) to select the bottle-neck service component by evaluating the real-time performance of all these components. Finally, we employ MACP (Maximum Available Capacity Path) algorithm to select a suitable node to deploy this service replica. Simulation results approve that our approach is effective and efficient.

Localization is an essential problem in Wireless Sensor Networks (WSNs). Many localization algorithms have been proposed, but few efforts have been paid on theoretical analysis on the accuracy of these algorithms. Because it is naturally to formalize range-based localization problems as deterministic parameter estimation problems, for range-based localization algorithms Cramér-Rao Lower Bound (CRLB) has been used to lower bound the variance on the estimation of sensor's positions. However, few similar works have been done for range-free localization algorithms. In this paper, based on geometry properties, we theoretically analyze bounds on accuracy for Region-Based Localization (RBL) algorithms which can be classified as one type of range-free localization algorithms. We prove that if in a RBL algorithm, the deployment region R with the area size s is partitioned into k regions (they can be with any shape and any area size), the localization accuracy is bounded below by no matter how the algorithm partitions R. Although the lower bound is not theoretically tight, our simulation results show that the gap between this bound and achievable accuracy is very small. We conjecture a tighter lower bound when k is large enough. We also observe that in order to achieve high localization accuracy, partitioned regions should have nearly the same size. We give three examples with simulation results to show how the results can be used to set the values of the parameters, like k and the corresponding anchor/event number, in a RBL algorithm in order to achieve desired localization accuracy.

Most of the proposed communication protocols for wireless sensor networks focus on the energy efficiency. However, it often brings poor latency performance. In this paper, we develop a novel cross-layer designed asynchronous protocol EEFF (Energy Efficient and Fast Forwarding) for wireless sensor networks regarding low latency and energy efficiency. EEFF improves low power listening approach and introduces dynamical routing selection to reduce the latency. We evaluate the performance of the EEFF protocol in a testbed of 16 MICAZ motes and perform larger scale experiments with NS-2. These experiments demonstrate that EEFF significantly improves the latency and energy performance compared with state-of-art asynchronous protocols, and it's especially suitable for large scale dense wireless sensor networks.

Self-organization is the key to implement self-calibration, autonomously coordination and P2P communication in sensor networks. Current researches mainly solve this problem in an inappropriate pre-planned manner. The swarm intelligence of the ant colony algorithm (ACA) provides a novel and efficient method for self-organization. For the similarity of sensor network and ant colony, we argue that the sensor networks will benefit from the bio-inspired self-organization by applying the ACA in optimization, structure formation and task/resource allocation. In this paper we outline the current researches on the ACA in sensor network first, then propose the potential applications and research issues. General design of the ACA in sensor network and some challenges are presented as well.

Data-centric storage is an effective and important technique in sensor networks, however, most data-centric storage schemes may not be energy efficient and load balanced due to non-uniform event and query distributions. This paper proposes EEBASS, it utilizes an approximation algorithm to solve the optimal storage placement problem according to the variance of event and query distributions, aiming to minimize the total energy consumption for data-centric storage scheme. And it further leverages a ring based replication structure to achieve the load balance goal. Simulation results show that EEBASS is more energy efficient and balanced than traditional data-centric storage mechanisms in sensor network.

As a fundamental operation of wireless ad hoc networks (WANET), broadcast has been widely studied in the past ten years. However, most existing broadcasting strategies assumed non-sleeping wireless devices. Little attention has been paid to broadcast in WANETs with sleeping schedule, which is a promising power-saving method in wireless networks. In this paper we study the sleeping schedule aware minimum transmission broadcast problem in WANETs (MTB-SA problem) and prove its NP-hardness. Both centralized and distributed approximation algorithms are presented to solve the problem. The centralized algorithm SchmM-Cent has an approximation ratio of 3(ln¿+1) and time complexity of O(n^3). The distributed algorithm SchmM-Dist has a constant approximation ratio of at most 20, while time and message complexity are both O(n). In addition, we provide theoretical analysis and simulations to evaluate the performance of the approximation algorithms.

Localization in mobile sensor networks is more challenging than in static sensor networks because mobility increases the uncertainty of nodes' positions. Most existing localization algorithms in mobile sensor networks use Sequential Monte Carlo (SMC) methods due to their simplicity in implementation. However, SMC methods are very time-consuming because they need to keep sampling and filtering until enough samples are obtained for representing the posterior distribution of a moving node's position. In this paper, we propose a localization algorithm that can reduce the computation cost of obtaining the samples and improve the location accuracy. A simple bounding-box method is used to reduce the scope of searching the candidate samples. Inaccurate position estimations of the common neighbor nodes is used to reduce the scope of finding the valid samples and thus improve the accuracy of the obtained location information. Our simulation results show that, comparing with existing algorithms, our algorithm can reduce the total computation cost and increase the location accuracy. In addition, our algorithm shows several other benefits: (1) it enables each determined node to know its maximum location error, (2) it achieves higher location accuracy under higher density of common nodes, and (3) even when there are only a few anchor nodes, most nodes can still get position estimations.

Power control plays an important role in wireless communications. However, most existing power control protocols are not efficient enough to be applied in real ad hoc network systems. In this paper, we propose PIPC (Proportion-Integral Power Control), a novel closed-loop power control algorithm that can be used in conjunction with any routing protocol as long as the routing table of a node provides enough knowledge of local network topology. PIPC adaptively adjusts the transmission power for each node through an improved version of the classical PID (Proportion-Integral-Differential) control. The topology derived under PIPC is also fed back to the routing table that is used as its input. Both theoretical analysis and simulation study show that PIPC has a good performance.

Multimedia applications are becoming more and more popular on today's Internet. Given the enormous development costs and less flexibility, traditional monolithic based approaches are not suitable for building large-scale multimedia systems. By composing of distributed, autonomous services dynamically to provide more complex tasks, service composition provides an attractive way for building large-scale Internet applications. So, multimedia service composition provides a viable solution to large-scale complex multimedia systems. One of the challenging issues of multimedia service composition is how to find service paths to route the data flows through while meeting the applications' resource requirements and specific QoS constraints. However, QoS-aware service routing problem is typically NP-hard. In this paper, we propose a heuristic algorithm named greedy-EF to solve this problem more effectively. More specially, greedy-EF uses an aggregate function to evaluate the QoS conditions for each service instance, and a hop-by-hop service selection approach to explore the proper service path. Simulations show that greedy-EF algorithm can achieve desired QoS assurances as well as load balancing in multimedia service overlay networks.

Cache invalidation is an important issue in mobile caching and has received much attention by researchers. However most existing studies on cache invalidation strategies are limited to cellular wireless networks in which the mobile terminals can communicate with the base stations directly. In this paper, we address the seldom studied issue of cache invalidation in mobile ad hoc networks (MANETs), where the use of multi-hop communications poses serious challenges. We propose three cache invalidation strategies for MANETs. The three methods, namely pull on demand (POD), modified amnesic terminals (MAT) and pull-based amnesic terminals (PAT) are adapted from Barbara and Imielinski's classic cache invalidation schemes to handle the special requirements of MANETs. Both analytical results as well as simulation experiments are used to examine the performance of these three schemes, and it is shown that PAT provides the best overall performance.

The unstructured peer-to-peer (P2P) systems usually use a "blind search" method to find the requested data object by propagating a query to a number of peers randomly. In order to increase the success rate of blind search, replication techniques are widely used in these systems. Most P2P systems replicate the most frequently accessed data objects to improve system performance. However, existing replication strategies cannot answer the question that how many replicas of an object should be kept in the P2P system. If an object is replicated excessively, it inevitably will affect the average efficiency of a replica, which will decrease the whole search performance. This paper addresses the issue of finding the proper number of replicas for an object according to its query rate. In this paper, we firstly investigate the precise relation among success rate, the allocation of replicas and query rate. Then we propose an approach of the allocation of copies to optimize the success rate. As a benchmark, our result offers a new understanding of replication.

Topology control for fault tolerant communication is one of the important issues in wireless sensor networks. This paper presents a simple mechanism of fault tolerant topology control for generating undirected scale-free networks, where the network evolution is determined by the rules of growth and preferential attachment. The authors prove that this mechanism produces scale-free networks with degree exponent gamma = 1. The dynamic analysis found that this evolution model can maintain the character of scale-free networks and can improve the uniformity of the degree distribution of the networks as compared with Barabasi and Albert model.

Data caching on mobile clients is widely seen as an effective solution to improve system performance. In particular, cooperative caching, based on the idea of sharing and coordination of cache data among multiple users, can be particularly effective for information access in mobile ad hoc networks where mobile clients moving frequently and network topology changing dynamically. Most existing cache strategies perform replacement independently, and they seldom consider coordinated replacement and energy saving issues in the context of a mobile ad hoc network. This paper analysed the impact of energy on designing a cache replacement policy and formulate the energy-efficient coordinated cache replacement problem (ECORP) as a 0-1 knapsack problem. A heuristic algorithm called ECORP-greedy and an optimal solution called ECORP-OPT are presented to solve the problem. Simulations show that the proposed policies can significantly reduce energy consumption and access latency when compared to other replacement policies.

Summary form only given. Many algorithms for achieving mutual exclusion in distributed computing systems have been proposed. The three most often used performance measures are the number of messages exchanged between the nodes per critical section (CS) execution, the response time, and the synchronization delay. We present a new fully distributed mutual exclusion algorithm. A node requesting the CS sends out the request message which will roam in the network. The message are forwarded among the nodes until the requesting node obtains enough permissions to decide its order to enter the CS. The decision is made by using relative consensus voting (RCV), which is a variation of the well-known majority consensus voting (MCV) scheme. Unlike existing algorithms which determine the node to enter the CS one by one, in our algorithm, several nodes can be decided and ordered for executing the CS. The synchronization delay is minimal. Although the message complexity can be up to O(N) in the worst case in a system with N nodes, our simulation results show that, on average, the algorithm needs less number of messages and has less response time than most of those existing algorithms which do not require a logical topology imposed on the nodes. This is especially true when the system is under heavy demand. Another feature of the proposed algorithm is that it does not require the FIFO property of the underlying message passing mechanism.

FDDI networks have been widely deployed to support real-time traffic such as voice and video communications. However its medium access control (MAC) protocol can transmit synchronous messages up to at most one half of the total bandwidth of the FDDI network. Shin and Zheng has proposed a modification to the FDDI MAC protocol, called FDDI-M, which can double a ring's ability in supporting synchronous traffic (see IEEE Trans. Parallel and Distributed Systems, no.6, p.1125-31, 1995). However, it is widely known that the ability of timed token protocols such as FDDI to guarantee synchronous message deadlines is very dependent on the synchronous bandwidth allocation (SBA) schemes used. We first propose a classification of SBA schemes proposed in the literature which facilitates our comparison of FDDI-M with FDDI. Next, we present an analytical study of the timing properties of the FDDI-M protocol, using the worst case achievable utilization (WCAU) as the performance metric, for a class of SBA schemes. Our results show that FDDI-M improves the WCAU values for those SBA schemes which are non-zero to start with, but those whose WCAU values are zero remain unchanged.

The FDDI Standard specifies a 100 Mbits/s fibre-optic token ring network that has been implemented and widely installed. The FDDI medium access control (MAC) protocol, however, has the inherent deficiency that, at most, one half of the bandwidth of a FDDI ring can be used to transmit synchronous messages. In a recent paper, a modification to the FDDI MAC protocol, called FDDI-M, was proposed to overcome this deficiency. It has been shown using simulation that FDDI-M doubles a ring's ability of supporting synchronous traffic while at the same time it achieves a higher throughput for asynchronous traffic than standard FDDI. In this paper we present an analytical study of the timing properties of the FDDI-M protocol. The results presented in this paper complement those of the original paper. Using the worst-case achievable utilization (WCAU) as the performance metric, we evaluate the performance of various synchronous bandwidth allocation (SBA) schemes in guaranteeing synchronous message deadlines. It is found that, in comparison with FDDI, the FDDI-M protocol results in a higher WCAU for the normalized proportional SBA scheme. However, for the local SBA schemes studied, the WCAU values remain at zero.