A key challenge in classical federated learning (FL) is statistical heterogeneity, which may lead to slow convergence and low accuracy. To tackle this, personalized FL (PFL) accounts for the individual data distribution of each client. This article proposes a new PFL method that relies on two principles: 1) shared knowledge and personalized knowledge can be reflected in different layers of the network and 2) clients with more data can contribute more to shared knowledge, while knowledge transfer from similar clients can boost personalization. We propose a novel method that applies aggregation based on the local data sizes for the shared knowledge layers and uses a deep reinforcement learning (DRL) agent for aggregating the layers pertaining to personalized knowledge. To ascertain efficiency and scalability, we train a single DRL agent (for all users) that operates on the server side, taking as input the subset of models corresponding to participants in the previous round. To reduce the dimensionality of its state space, we design a multihead autoencoder (MHAE). Extensive experiments on benchmark datasets for variable data heterogeneity levels reveal benefits over leading baselines in terms of both higher accuracy (up to +3.71%) and faster convergence (a reduction of global rounds by up to 30.6%). Our code is accessible at:https://github.com/fdksd/pFedRLLA.

The effectiveness of WiFi-based localization systems heavily relies on the spatial accuracy of WiFi AP. In real-world scenarios, factors such as AP rotation and irregular antenna tilt contribute significantly to inaccuracies, surpassing the impact of imprecise AP location and antenna separation. In this paper, we proposeAnteumbler, a non-invasive, accurate, and efficient system for measuring the orientation of each antenna in physical space. By leveraging the fact that maximum received power occurs when a Tx-Rx antenna pair is perfectly aligned, we build a spatial angle model capable of determining antennas’ orientations without prior knowledge. However, achieving comprehensive coverage across the spatial angle necessitates extensive sampling points. To enhance efficiency, we exploit the orthogonality of antenna directivity and polarization, and adopt an iterative algorithm, thereby reducing the number of sampling points by several orders of magnitude. Additionally, to attain the required antenna orientation accuracy, we mitigate the influence of propagation distance using a dual plane intersection model while filtering out ambient noise. Our real-world experiments, covering six antenna types, two antenna layouts, two antenna separations ($\lambda /2$and$\lambda$), and three AP heights, demonstrate thatAnteumblerachieves median errors below$\text{6}^\circ$for both elevation and azimuth angles, and exhibits robustness in NLoS and dynamic environments. Moreover, when integrated into the reverse localization system,Anteumblerdeployed over LocAP reduces antenna separation error by$10 \,\mathrm{mm}$, while for user localization system, its integration over SpotFi reduces user localization error by more than$1 \,\mathrm{m}$.

The Vision Transformer (ViT) has emerged as a powerful architecture for various computer vision tasks. Nonetheless, this comes with substantially heavier computational costs than Convolutional Neural Networks (CNNs). The attention mechanism in ViTs, which integrates information from different image patches to the class token ([CLS]), renders traditional structured pruning methods used in CNNs unsuitable. To overcome this issue, we propose SynergisTic pAtch pRuning (STAR) that unifies intra-layer and inter-layer patch importance scoring. Specifically, our approach combines a) online evaluation of intra-layer importance for the [CLS] and b) offline evaluation of the inter-layer importance of each patch. The two importance scores are fused by minimizing a weighted average of Kullback-Leibler (KL) Divergences and patches are successively pruned at each layer by maintaining only the top-k most important ones. Unlike prior art that relies on manual selection of the pruning rates at each layer, we propose an automated method for selecting them based on offline-derived metrics. We also propose a variant that uses these rates as weighted percentile parameters (for the layer-wise normalized scores), thus leading to an alternate adaptive rate selection technique that is input-based. Extensive experiments demonstrate the significant acceleration of the inference with minimal performance degradation. For instance, on the ImageNet dataset, the pruned DeiT-Small reaches a throughput of 4,256 images/s, which is over 66\% higher than the much smaller (unpruned) DeiT-Tiny model, while having a substantially higher accuracy (+6.8\% Top-1 and +3.1\% Top-5).

The passive compliance of soft robotic arms renders the development of accurate kinematic models and model-based controllers challenging. The most widely used model in soft robotic kinematics assumes Piecewise Constant Curvature (PCC). However, PCC introduces errors when the robot is subject to external forces or even gravity. In this paper, we establish a three-dimensional (3D) kinematic representation of a soft robotic arm with pseudo universal and prismatic joints that are capable of capturing non-constant curvature deformations of the soft segments. We theoretically demonstrate that this constitutes a more general methodology than PCC. Simulations and experiments on the real robot attest to the superior modeling accuracy of our approach in 3D motions with unknown loads. The maximum position/rotation error of the proposed model is verified 6.7×/4.6× lower than the PCC model considering gravity and external forces. Furthermore, we devise an inverse kinematic controller that is capable of positioning the tip, tracking trajectories, as well as performing interactive tasks in the 3D space.

The performance of WiFi-based localization systems is affected by the spatial accuracy of WiFi AP. Compared with the imprecision of AP location and antenna separation, the imprecision of AP’s or antenna’s orientation is more important in real scenarios, including AP rotation and antenna irregular tilt. In this paper, we propose Anteumbler that non-invasively, accurately and efficiently measures the orientation of each antenna in physical space. Based on the fact that the received power is maximized when a Tx-Rx antenna pair is perfectly aligned, we construct a spatial angle model that can obtain the antennas’ orientations without prior knowledge. However, the sampling points of traversing the spatial angle need to cover the entire space. We use the orthogonality of antenna directivity and polarization and adopt an iterative algorithm to reduce the sampling points by hundreds of times, which greatly improves the efficiency. To achieve the required antenna orientation accuracy, we eliminate the influence of propagation distance using a dual plane intersection model and filter out ambient noise. Our real-world experiments with six antenna types, two antenna layouts and two antenna separations show that Anteumbler achieves median errors below 6 ° for both elevation and azimuth angles, and is robust to NLoS and dynamic environments. Last but not least, for the reverse localization system, we deploy Anteumbler over LocAP and reduce the antenna separation error by 10 mm, while for the user localization system, we deploy Anteumbler over SpotFi and reduce the user localization error by more than 1 m.

-norm is not scaling-invariant (i.e., the regularization penalty depends on weight values) and 2) there is no rule for selecting the penalty coefficient to trade off high pruning ratio for low accuracy drop. To address these issues, we propose a lightweight pruning method termed adaptive sensitivity-based pruning (ASTER) which: 1) achieves scaling-invariance by refraining from modifying unpruned filter weights and 2) dynamically adjusts the pruning threshold concurrently with the training process. ASTER computes the sensitivity of the loss to the threshold on the fly (without retraining); this is carried efficiently by an application of L-BFGS solely on the batch normalization (BN) layers. It then proceeds to adapt the threshold so as to maintain a fine balance between pruning ratio and model capacity. We have conducted extensive experiments on a number of state-of-the-art CNN models on benchmark datasets to illustrate the merits of our approach in terms of both FLOPs reduction and accuracy. For example, on ILSVRC-2012 our method reduces more than 76% FLOPs for ResNet-50 with only 2.0% Top-1 accuracy degradation, while for the MobileNet v2 model it achieves 46.6% FLOPs Drop with a Top-1 Acc. Drop of only 2.77%. Even for a very lightweight classification model like MobileNet v3-small, ASTER saves 16.1% FLOPs with a negligible Top-1 accuracy drop of 0.03%.

Traditional embedding methodologies, also known as dimensionality reduction techniques, assume the availability of exact pairwise distances between the high-dimensional objects that will be embedded in a lower dimensionality. In this article, we propose an embedding that overcomes this limitation and can operate on pairwise distances that are represented as a range of lower and upper bounds. Such bounds are typically estimated when objects are compressed in a lossy manner, so our approach is highly applicable in the case of big compressed datasets. Our methodology can preserve multiple aspects of the original data relationships: distances, correlations, and object scores/ranks, whereas existing techniques typically preserve only distances. Comparative experiments with prevalent embedding methodologies (ISOMAP, t-SNE, MDS, UMAP) illustrate that our approach can provide fidelitous preservation of multiple object relationships, even in the presence of inexact distance information. Our visualization method is also easily interpretable.

Accurate ambient perception via multi-object detection and tracking is instrumental for autonomous vehicles. This article addresses two main challenges when operating solely on 3-D light laser detection and ranging (LiDAR) point clouds: the classification of objects with similar geometric structures and tracking under the commonplace setting of low-frequency sensing. First, we design a semantically enhanced feature aggregation module that fuses features learned from two branches with different resolutions and depths. Subsequently, the extracted semantic information combined with our proposed Margin Loss allows the re-identification module to extract time-invariant geometric features. These features are fused with the positional information provided by the detector by a cluster-based Earth's mover distance algorithm along with conflation to improve the tracking stability. Extensive experiments on nuScenes demonstrate that our proposed model outperforms the state-of-the-art methods for both LiDAR-based 3-D object detection and tracking. In particular, we report an increase of 1.1% in average multi-object tracking accuracy, as well higher mean average precision for detection by 6.2% and 7.5% on motorcycle and bicycle, respectively.

We propose a communication efficient quasi-Newton method for large-scale multi-agent convex composite optimization. We assume the setting of a network of agents that cooperatively solve a global minimization problem with strongly convex local cost functions augmented with a non-smooth convex regularizer. By introducing consensus variables, we obtain a block-diagonal Hessian and thus eliminate the need for additional communication when approximating the objective curvature information. Moreover, we reduce computational costs of existing primal-dual quasi-Newton methods from $\mathcal{O}\left( {{d^3}} \right)$ to $\mathcal{O}\left( {cd} \right)$ by storing c pairs of vectors of dimension d. An asynchronous implementation is presented that removes the need for coordination. Global linear convergence rate in expectation is established, and we demonstrate the merit of our algorithm numerically with real datasets.

Federated Learning (FL) is an emerging framework for distributed processing of large data volumes by edge devices subject to limited communication bandwidths, heterogeneity in data distributions and computational resources, as well as privacy considerations. In this paper, we introduce a new FL protocol termed FedADMM based on primal-dual optimization. The proposed method leverages dual variables to tackle sta-tistical heterogeneity, and accommodates system heterogeneity by tolerating variable amount of work performed by clients. FedADMM maintains identical communication costs per round as FedAvg/Prox, and generalizes them via the augmented Lagrangian. A convergence proof is established for nonconvex objectives, under no restrictions in terms of data dissimilarity or number of participants per round of the algorithm. We demon-strate the merits through extensive experiments on real datasets, under both IID and non-IID data distributions across clients. FedADMM consistently outperforms all baseline methods in terms of communication efficiency, with the number of rounds needed to reach a prescribed accuracy reduced by up to 87%. The algorithm effectively adapts to heterogeneous data distributions through the use of dual variables, without the need for hyperparameter tuning, and its advantages are more pronounced in large-scale systems.

3D Multi-Object Tracking (MOT) plays a crucial role in efficient and safe operation of automatic driving, especially in scenarios of occlusion or poor visibility. Most 3D MOT methods leverage only positional distance, which is insufficient for scenes with high density of objects or drastic changes in the motion state. In order to address this, we propose a new 3D MOT model which fuses information pertaining to positional distance and geometric similarity. Our proposed solution comprises of four parts: a) a feature extraction mechanism integrated into a commonly used detector to extract individual features for each detection, b) computation of two distance matrices based on Euclidean distance and feature similarity, c) conversion of the distance matrices to probability matrices by a cluster based Earth-Mover Distance (EMD) algorithm, and d) a data association method that fuses both sources to boost the tracking accuracy. Our proposed model demonstrates state-of-the-art performance on the nuScenes tracking dataset, with extensive experiments attesting to an improved tracking accuracy over baselines that operate solely on positional distance.

Navigation paths and corresponding travel times play a key role in location-based services (LBS) of which large-scale navigation path caching constitutes a fundamental component. In view of the highly dynamic real-time traffic changes in road networks, the main challenge amounts to updating paths in the cache in a fashion that incurs minimal costs due to querying external map service providers and cache maintenance. In this paper, we propose a hybrid graph approach in which an LBS provider maintains a dynamic graph with edge weights representing travel times, and queries the external map server so as to ascertain high fidelity of the cached paths subject to stringent limitations on query costs. We further deploy our method in one of the biggest on-demand food delivery platforms and evaluate the performance against state-of-the-art methods. Our experimental results demonstrate the efficacy of our approach in terms of both substantial savings in the number of required queries and superior fidelity of the cached paths.

Guaranteed delivery (GD) and real-time bidding (RTB) constitute two parallel profit streams for the publisher. The diverse advertiser demands (brand or instant effect) result in different selling (in bulk or via auction) and pricing (fixed unit price or various bids) patterns, which naturally raises the fusion allocation issue of breaking the two markets' barrier and selling out at the global highest price boosting the total revenue. The fusion process complicates the competition between GD and RTB, and GD contracts with overlapping targeting. The non-stationary user traffic and bid landscape further worsen the situation, making the assignment unsupervised and hard to evaluate. Thus, a static policy or coarse-grained modeling from existing work is inferior to facing the above challenges.

In this article, we study a multiplayer Stackelberg-Nash game (SNG) pertaining to a nonlinear dynamical system, including one leader and multiple followers. At the higher level, the leader makes its decision preferentially with consideration of the reaction functions of all followers, while, at the lower level, each of the followers reacts optimally to the leader's strategy simultaneously by playing a Nash game. First, the optimal strategies for the leader and the followers are derived from down to the top, and these strategies are further shown to constitute the Stackelberg-Nash equilibrium points. Subsequently, to overcome the difficulty in calculating the equilibrium points analytically, we develop a novel two-level value iteration-based integral reinforcement learning (VI-IRL) algorithm that relies only upon partial information of system dynamics. We establish that the proposed method converges asymptotically to the equilibrium strategies under the weak coupling conditions. Moreover, we introduce effective termination criteria to guarantee the admissibility of the policy (strategy) profile obtained from a finite number of iterations of the proposed algorithm. In the implementation of our scheme, we employ neural networks (NNs) to approximate the value functions and invoke the least-squares methods to update the involved weights. Finally, the effectiveness of the developed algorithm is verified by two simulation examples.

Federated learning (FL) enables large amounts of participants to construct a global learning model, while storing training data privately at each client device. A fundamental issue in this framework is the susceptibility to the erroneous training data. This problem is especially challenging due to the invisibility of clients' local training data and training process, as well as the resource constraints of a large number of mobile and edge devices. In this paper, we try to tackle this challenging issue by introducing the first FL debugging framework, FLDebugger, for mitigating test error caused by erroneous training data. The pro-posed solution traces the global model's bugs (test errors), jointly through the training log and the underlying learning algorithm, back to first identify the clients and subsequently their training samples that are most responsible for the errors. In addition, we devise an influence-based participant selection strategy to fix bugs as well as to accelerate the convergence of model retraining. The performance of the identification algorithm is evaluated via extensive experiments on a real AIoT system (50 clients, including 20 edge computers, 20 laptops and 10 desktops) and in larger-scale simulated environments. The evaluation results attest to that our framework achieves accurate and efficient identification of negatively influential clients and samples, and significantly improves the model performance by fixing bugs.

A wide range of optimization problems arising in machine learning can be solved by gradient descent algorithms, and a central question in this area is how to efficiently compress a large-scale dataset so as to reduce the computational complexity. Coreset is a popular data compression technique that has been extensively studied before. However, most of existing coreset methods are problem-dependent and cannot be used as a general tool for a broader range of applications. A key obstacle is that they often rely on the pseudo-dimension and total sensitivity bound that can be very high or hard to obtain. In this paper, based on the “locality” property of gradient descent algorithms, we propose a new framework, termed “sequential coreset”, which effectively avoids these obstacles. Moreover, our method is particularly suitable for sparse optimization whence the coreset size can be further reduced to be only poly-logarithmically dependent on the dimension. In practice, the experimental results suggest that our method can save a large amount of running time compared with the baseline algorithms.

Fine-grained energy consumption analysis has great potential value in applications of Smart Grids, renewable energy, and Artificial Intelligence of Things. Non-Intrusive Load Monitoring (NILM) is a single-sensor alternative to the conventional one-sensor-for-one-appliance solution due to its ability to deduce individual appliances states from mixed measurements from the main power interface. Despite its advantages of low cost and easy maintenance, a few drawbacks hinders its widespread adoption. To enhance the Quality of Service (QoS) of NILM, four objectives should be achieved by careful designing: high accuracy, user transparency, low response delay, and low data redundancy.Inspired by observations of discriminative yet redundant current waveform and model sparsity, we propose LCL, a lightweight, contactless, plug-and-play solution for real-time load monitoring. The filtering module skips over unchanged input and compresses the measurements of interest using Compressed Sensing. The reconstruction-free inference module runs an attentional multi-label classification and returns all functioning appliance states directly from the compressed input. The compression module leverages model sparsity for real-time processing on edge devices. Evaluations based on our prototype deployed in real-life scenarios attest to the high QoS of LCL with a subset accuracy of 94.2% and a delay reduction of 52.2%. Our solution further filters out 96.8% of the redundant input and attains a Measurement Rate of 0.1 without noticeable impact on the performance.

The rapid proliferation of Smart Grids calls for a more in-depth understanding of user energy consumption behaviors, based on large data volumes collected by various sources of sensors such as voltmeter and ammeter. Non-Intrusive Load Monitoring (NILM) is a single sensor solution, which can effectively disaggregate individual appliance states from measurements only at the interface to the power source, albeit at the cost of requiring circuit modifications thus introducing suspension of services and potential safety hazards. To overcome the undesirable attribute of NILM and achieve a safe yet highly accurate solution, we devise a contactless sensing system based on inductive current measurements that can conduct load disaggregation without tampering with the power system. Despite using single modality, i.e., the inductive current, our scheme attains state-of-the-art accuracy in existing multi-modality datasets by leveraging modality distillation technique to handle arbitrary input structure. Our main contributions enlist: (1) devising and deploying the first, to the best of our knowledge, purely contactless non-intrusive load disaggregation system; (2) the design of an oracle-apprentice network structure to leverage multi-modality input for training, while operating with single modality; (3) a high estimation accuracy of 95.44% and 96.21%, respectively, is attested on two public datasets, which proves the efficiency of our method.

A common assumption in embedding methodologies is the availability of exact pairwise distances. In this paper, we propose a 2D embedding that overcomes this limitation. It can operate on distances that are represented as a range of lower and upper bounds. Such bounds are typically available when objects are compressed, whence our approach is highly applicable in the case of big compressed datasets. We establish linear convergence (i.e., exponential decay of distance to optimality) for the proposed scheme, with a rate characterized by the topology of the data graph. We compare with prevalent embedding methodologies (ISOMAP, t-SNE, MDS) and illustrate that our approach can provide fidelitous preservation of distances, correlations, and object ranks, even in the presence of inexact distance information.

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous works in edge computing mainly focused on either one kind of utility function (e.g., linear, sigmoid, or the hard deadline) or different kinds of utilities separately. In this paper, we investigate online job dispatching and scheduling strategies under the setting of coexistence of heterogeneous utilities, i.e., various coexisting jobs can employ different non-increasing utility functions. The goal is to maximize the total utility over all jobs in an edge system. Besides heterogeneous utilities, we here adopt a practical online model where the unrelated machine model and the upload and download delay are considered. We proceed to propose an online algorithm, O4A, to dispatch and schedule jobs with heterogeneous utilities. Our theoretical analysis shows that O4A is O(1/ɛ2)-competitive under the (1 + ɛ)-speed augmentation model, where ɛ is a small positive constant. We implement O4A on an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate that O4A can increase the total utility by up to 39.42% compared with state-of-the-art utility-agnostic methods. Moreover, O4A is robust to estimation errors in job processing time and transmission delay.

Protection of one's intellectual property is a topic with important technological and legal facets. We provide mechanisms for establishing the ownership of a dataset consisting of multiple objects. The algorithms also preserve important properties of the dataset, which are important for mining operations, and so guarantee both right protection and utility preservation. We consider a right-protection scheme based on watermarking. Watermarking may distort the original distance graph. Our watermarking methodology preserves important distance relationships, such as: the Nearest Neighbors (NN) of each object and the Minimum Spanning Tree (MST) of the original dataset. This leads to preservation of any mining operation that depends on the ordering of distances between objects, such as NN-search and classification, as well as many visualization techniques. We prove fundamental lower and upper bounds on the distance between objects post-watermarking. In particular, we establish a restricted isometry property, i.e., tight bounds on the contraction/expansion of the original distances. We use this analysis to design fast algorithms for NN-preserving and MST-preserving watermarking that drastically prune the vast search space. We observe two orders of magnitude speedup over the exhaustive schemes, without any sacrifice in NN or MST preservation.

Mobile health is gaining increasing importance for society and the quest for new power efficient devices sampling biosignals is becoming critical. We discuss a new scheme called Variable Pulse Width Finite Rate of Innovation (VPW-FRI) to model and compress ECG signals. This technique generalizes classical FRI estimation to enable the use of a sum of asymmetric Cauchy-based pulses for modeling electrocardiogram (ECG) signals. We experimentally show that VPW-FRI indeed models ECG signals with increased accuracy compared to current standards. In addition, we study the compression efficiency of the method: compared with various widely used compression schemes, we showcase improvements in terms of compression efficiency as well as sampling rate.

We consider the problem of scalable video streaming from a server to multinetwork clients over heterogeneous access networks, with the goal of minimizing the distortion of the received videos. This problem has numerous applications including: 1) mobile devices connecting to multiple licensed and ISM bands, and 2) cognitive multiradio devices employing spectrum bonding. In this paper, we ascertain how to optimally determine which video packets to transmit over each access network. We present models to capture the network conditions and video characteristics and develop an integer program for deterministic packet scheduling. Solving the integer program exactly is typically not computationally tractable, so we develop heuristic algorithms for deterministic packet scheduling, as well as convex optimization problems for randomized packet scheduling. We carry out a thorough study of the tradeoff between performance and computational complexity and propose a convex programming-based algorithm that yields good performance while being suitable for real-time applications. We conduct extensive trace-driven simulations to evaluate the proposed algorithms using real network conditions and scalable video streams. The simulation results show that the proposed convex programming-based algorithm: 1) outperforms the rate control algorithms defined in the Datagram Congestion Control Protocol (DCCP) by about 10–15 dB higher video quality; 2) reduces average delivery delay by over 90% compared to DCCP; 3) results in higher average video quality of 4.47 and 1.92 dB than the two developed heuristics; 4) runs efficiently, up to six times faster than the best-performing heuristic; and 5) does indeed provide service differentiation among users.

Most real-world data contain repeated or periodic patterns.This suggests that they can be effectively represented and compressed using only a few coefficients of an appropriate complete orthogonal basis (e.g., Fourier, Wavelets, Karhunen-Loève expansion or Principal Components).In the face of ever increasing data repositories and given that most mining operations are distance-based, it is vital to perform accurate distance estimation directly on the compressed data.However, distance estimation when the data are represented using different sets of coefficients is still a largely unexplored area.This work studies the optimization problems related to obtaining the tightest lower/upper bound on the distance based on the available information.In particular, we consider the problem where a distinct set of coefficients is maintained for each sequence, and the L2norm of the compression error is recorded.We establish the properties of optimal solutions, and leverage the theoretical analysis to develop a fast algorithm to obtain an exact solution to the problem.The suggested solution provides the tightest provable estimation of the L2-norm or the correlation, and executes at least two order of magnitudes faster than a numerical solution based on convex optimization.The contributions of this work extend beyond the purview of periodic data, as our methods are applicable to any sequential or high-dimensional data as well as to any orthogonal data transformation used for the underlying data compression scheme.

This work rigorously explores the design of cluster-preserving compression schemes for high-dimensional data. We focus on the K-means algorithm and identify conditions under which running the algorithm on the compressed data yields the same clustering outcome as on the original. The compression is performed using single and multi-bit minimum mean square error quantization schemes as well as a given clustering assignment of the original data. We provide theoretical guarantees on post-quantization cluster preservation under certain conditions on the cluster structure, and propose an additional data transformation that can ensure cluster preservation unconditionally; this transformation is invertible and thus induces virtually no distortion on the compressed data. In addition, we provide an efficient scheme for multi-bit allocation, per cluster and data dimension, which enables a trade-off between high compression efficiency and low data distortion. Our experimental studies highlight that the suggested scheme accurately preserved the clusters formed in all cases, while incurring minimal distortion on the data shapes. Our results can find many applications, e.g., in a) clustering, analysis and distribution of massive datasets, where the proposed data compression can boost performance while providing provable guarantees on the clustering result, as well as, in b) cloud computing services, as the optional transformation provides a data-hiding functionality in addition to preserving the K-means clustering outcome.

We consider multihomed scalable video streaming, where videos are transmitted by a single server to multiple clients over heterogeneous access networks. The specific problem that we address is to determine which video packets to transmit over each network, in order to minimize a cost function of the expected video distortion at the clients. We present a network model and a video model that capture the network conditions and video characteristics, respectively. We develop an integer program for deterministic packet scheduling. We propose different cost functions in order to provide service differentiation and address fairness among users. We propose several suboptimal convex problems for randomized packet scheduling, and study their performance and complexity. We propose an algorithm that yields a good performance and is suitable for real-time applications. We conduct extensive trace-driven simulations to evaluate the proposed algorithms using real network conditions and scalable video streams. The simulation results show that the proposed algorithm: (i) outperforms the rate control algorithms defined in the Datagram Congestion Control Protocol (DCCP) by about 10 dB, (ii) results in video quality, of 4.33 dB and 1.84 dB higher than the two heuristics developed in [1], (iii) runs efficiently, up to six times faster than one of the heuristics, and (iv) indeed can provide service differentiation among users.

Sensor networks potentially feature large numbers of nodes. The nodes can monitor and sense their environment over time, communicate with each other over a wireless network, and process information that they exchange with each other. They differ from data networks in that the network as a whole may be designed for a specific application. We study the theoretical foundations of such large-scale sensor networks. We address four fundamental organizational and operational issues related to large sensor networks: connectivity, capacity, clocks, and function computation. To begin with, a sensor network must be connected so that information can indeed be exchanged between nodes. The connectivity graph of an ad hoc network is modeled as a random graph and the critical range for asymptotic connectivity is determined, as well as the critical number of neighbors that a node needs to connect to. Next, given connectivity, we address the issue of how much data can be transported over the sensor network. We present fundamental bounds on capacity under several models, as well as architectural implications for how wireless communication should be organized. Temporal information is important both for the applications of sensor networks as well as their operation. We present fundamental bounds on the synchronizability of clocks in networks, and also present and analyze algorithms for clock synchronization. Finally, we turn to the issue of gathering relevant information, which sensor networks are designed to do. One needs to study optimal strategies for in-network aggregation of data, in order to reliably compute a composite function of sensor measurements, as well as the complexity of doing so. We address the issue of how such computation can be performed efficiently in a sensor network and the algorithms for doing so, for some classes of functions.