360-degree videos have gained considerable popularity by offering immersive experiences to viewers. However, they consume a significant amount of bandwidth and demand specialized caching schemes at the edge network. Previous caching schemes have certain limitations due to either complete historical data or neglect the viewer-varying characteristics in 360-degree videos. In this paper, we address these limitations by proposing online caching schemes for two scenarios: (1) single-video and (2) multi-video. In the single-video scenario, we propose the online Single-Video caching scheme (SV-caching scheme). The SV-caching scheme predicts tile popularity using the PopPred algorithm, and optimizes caching decisions to enhance viewers’ Quality of Experience (QoE) using the CacheOpt algorithm. In the multi-video scenario, we propose the online Multi-Video caching scheme (MV-caching scheme). The MV-caching scheme dynamically allocates cache space for each video using the MVCacheAlloc algorithm according to the video popularity, and optimizes caching decisions using the MVCacheOpt algorithm. We prove that all algorithms achieve sublinear regret, i.e.,O(√K), whereKis the number of viewers. This guarantees that our schemes’ performance approaches the optimal as more viewers are served. Experiments on real-world data demonstrate that our caching schemes outperform existing algorithms in regret, QoE, and hit ratio for both scenarios.

Coded caching has emerged as an effective technique to alleviate network congestion. While the individual impact of user cache sizes or file popularity has been investigated independently, their joint impact on coded caching remains unclear. In this paper, we first characterize two information-theoretic lower bounds on the expected transmission rate. The first bound introduces a novel cut-set method that allows users to repeatedly request files at different frequencies, accounting for the heterogeneity of user cache sizes and file popularity. The second bound is derived from the traditional cut-set bound, assuming each file is requested at most once. Then a group-based multi-round decentralized coded caching scheme is introduced. We show that the expected transmission rate for this scheme is at most anO(logK) factor away from the second lower bound, applicable to any cache and popularity distributions, whereKis the number of users. Additionally, by combining with the first lower bound, a tighterO(logKmK/m1) gap between the upper and lower bounds is derived for power function and Zipf cache distributions, wherem1andmKrepresent the minimum and maximum cache sizes, respectively. Simulation results show the superior performance of our proposed scheme.

End-to-end (E2E) semantic communication (SemCom) powered by semantic knowledge base (SKB) is an efficient SemCom framework. However, in practical scenarios, SKB discrepancy among multiple SemCom pairs arises due to dynamic environmental changes (e.g., varying source data or tasks) or system-level alterations (e.g., integration of new SemCom pairs with divergent SKBs). Such discrepancy leads to performance disparity in semantic transmission, where underperforming pairs fail to maintain efficient task execution. To address this challenge, this paper introduces a cooperative SKB update policy, which enables collaborative evolution of SKBs to mitigate SKB discrepancy and improve performance of underperforming pairs. For each SemCom pair endowed with SKB-enabled SemCom, partial local SKB is selected out and uploaded to a mobile edge computing (MEC) server for establishing a global SKB. The global SKB aggregates the advantages of each local SKB, and is broadcasted to all SemCom pairs. Then, each SemCom pair updates their local SKB with the assistance of the global SKB. This process makes the local SKBs more sensible and less ambiguous, thereby enhancing the semantic transmission performance. Furthermore, in order to maximize the cooperative gains under limited uplink budgets of SemCom pairs, a knowledge selection optimization problem is formulated for the selection of the uploaded knowledge. Numerical results show that the proposed cooperative SKB update policy obtains significant performance gains, especially for the initially poor-performing pairs, and provide comprehensive performance comparison of the knowledge selection scheme.

The entanglement distribution problem over quantum networks has been widely studied, with the objective of maximizing network throughput, that is, the number of entanglements distributed for all user pairs. However, most of the existing works only focus on throughput maximization while neglecting fairness considerations. In this paper, we first characterize the fairness of an entanglement distribution scheme by introducing a fairness factor based on Element-Wise Inequalities, referred to as EWI-fairness. The EWI-fairness requires that the entanglement distribution rate of each user pair exceeds a certain threshold, ensuring the fair distribution. Second, we enforce fairness guarantees into two existing distribution methods, Temporal Multiplexing Distribution (TMD) and Flow Multiplexing Distribution (FMD). Our theoretical analysis reveals that FMD-based scheme outperforms TMD-based scheme. Therefore, we focus on optimizing FMD-based scheme. Third, we formulate the fair entanglement distribution problem as a linear programming problem, where fairness requirements serve as constraints, aiming to identify the optimal FMD-based scheme with the highest throughput. Simulation results demonstrate that the optimized FMD-based scheme achieves a higher throughput compared to existing schemes under identical fairness requirements.

Coded caching provides an opportunity to reduce data traffic load in peak hours via coded multicast transmissions. This paper studies the coded caching problem for video contents in heterogeneous packet erasure channels. The video contents are encoded in a scalable manner, where each user's decoding quality depends on the number of layers it receives. Two main challenges lie in this problem. (1) In heterogeneous erasure broadcast channels, users may receive varying numbers of packets. Thus, the performance of the system will be limited by the worst channel condition of users, which is referred to as the “worst-user effect” in existing works. (2) In a scenario where users require different video qualities, different numbers of layers may be transmitted to the users, which indicates a reduction in the multicast opportunities. In this paper, we propose a novel coded caching scheme that enables video quality adaptation, addressing these two challenges at once. The insight is to align the number of layers each user requests with its channel condition, ensuring that the amount of data each user attempts to receive is the same, thus maximizing the multicast opportunities. Analyses show that the transmission rate is determined by the average erasure probability among users, thus alleviating the worst-user effect. Simulation results illustrate the superior performance of the proposed scheme compared to state-of-the-art methods.

Coded caching has emerged as a promising technique to alleviate traffic congestion by strategically creating coded multicasting opportunities, even for caches with different demands. For a two-layer cache-aided hierarchical network consisting of a central server, multiple helpers, and multiple users, prior works have characterized the fundamental performance limits of coded caching for this system with the constraint of a uniform user distribution (i.e., each helper serves an equal number of users). However, when the heterogeneity of user distribution is taken into account, there remain open questions. In this article, we consider a two-layer cache-aided hierarchical network with arbitrary user distributions, where a central server is connected via an error-free link to multiple helpers and each user can randomly access one helper. We introduce a new decentralized coded caching scheme and employ the cut-set technique to characterize lower bounds. Our results show that the gap between the upper and lower bound of the achievable rate from server to helpers is within a constant multiplicative (i.e., [1/32]) and additive (i.e., 2) factor, outperforming prior works under uniform user distribution. Moreover, we also show that the transmission rate from each helper to its attached users is at most a constant factor away from the corresponding lower bound. To our knowledge, this is the first work in hierarchical networks to eliminate the additive gap of the second layer. Finally, simulation results demonstrate the superiority of the proposed caching scheme compared with the state of the art.

Semantic communication has drawn substantial attention as a promising paradigm to achieve effective and intelligent communications. However, efficient image semantic communication encounters challenges with a lower testing compression ratio (CR) and signal-to-noise ratio (SNR) compared to the training phase. To tackle this issue, we propose an innovative semantic knowledge base (SKB)-enabled generative semantic communication system for image classification task and image generation task. Specifically, a lightweight SKB, comprising class-level information, is exploited to guide the semantic communication process, which enables us to transmit only the relevant indices. This approach promotes the completion of the image classification task at the transmitter and significantly reduces the transmission load. Meanwhile, the class-level knowledge in the SKB facilitates the image generation task by allowing controllable generation, making it possible to generate class-consistent images in resource-constrained and low SNR scenarios. Furthermore, an adaptive CR and mode selection mechanism is designed to automatically adjust the CR and task mode, which allows the proposed system accommodate various CR and SNR conditions. Evaluation results indicate that the proposed method outperforms the benchmarks and achieves superior performance with minimal CR and SNR.

This paper proposes a replacement algorithm for file caching in mobile edge computing (MEC) networks. While there are numerous schemes for file replacement, it remains a challenge to achieve good, robust, and predictable performance simultaneously. To address this challenge, we introduce a general scheme called Incremental Least-Recently-Used (iLRU), which builds on the classic Least-Recently-Used (LRU) algorithm. iLRU initially caches only a “portion” of the file upon the first request and incrementally caches more when there are more requests for the file. In this regard, the request frequency can be inferred from the cached size without incurring additional overhead, where a larger cached size represents a higher request frequency. We derive the theoretical hit ratio of iLRU based on the Time-to-Live (TTL) analysis. With the Time-to-Live (TTL) analysis, we can theoretically derive the hit ratio and properties of iLRU and notably show that iLRU allocates more cache space to popular files, resulting in a higher hit ratio than LRU. Simulation results demonstrate the superior performance of iLRU and validate the accuracy of the theoretical hit ratio. Furthermore, we conduct simulations over various real-world traces to show that iLRU outperforms existing schemes across various real-world traces, defenestrating the robustness of iLRU.

Entanglement distribution via probabilistic entanglement swapping across a quantum repeater chain connecting two quantum nodes is a challenging problem. The difficulty lies in the exponential number of possible swapping structures within the repeater chain, necessitating efficient search algorithms, especially as the chain length increases. In this paper, we first explore the algorithmic design to facilitate the search for the optimal swapping structure along a repeater chain, aiming to maximize the entanglement distribution rate. Second, we examine the computational complexities of various algorithms and find that prior approaches exhibit excessively high complexities. Thus, we propose an efficient dynamic programming-based algorithm, FastHED, that leverages heuristics to expedite the search for the optimal swapping structure. Our theoretical analysis reveals that the upper bound of the proposed algorithm’s computational complexity is$O(n(\log n)^{3})$(more precisely,$O(n(\log n)^{2} \log \log n)$when$n\le 2^{29}$), a significant improvement over the existing algorithm with a complexity of$O(n^{2} \log n)$, where n denotes the repeater chain’s length. Additionally, we design a best-first framework to evaluate the performance of different algorithms. Numerical results show that our algorithm achieves a higher average entanglement distribution rate than existing algorithms.

We study the stochastic combinatorial semi-bandit problem with unrestricted feedback delays under merit-based fairness constraints. This is motivated by applications such as crowdsourcing, and online advertising, where immediate feedback is not immediately available and fairness among different choices (or arms) is crucial. We consider two types of unrestricted feedback delays: reward-independent delays where the feedback delays are independent of the rewards, and reward-dependent delays where the feedback delays are correlated with the rewards. Furthermore, we introduce merit-based fairness constraints to ensure a fair selection of the arms. We define the reward regret and the fairness regret and present new bandit algorithms to select arms under unrestricted feedback delays based on their merits. We prove that our algorithms all achieve sublinear expected reward regret and expected fairness regret, with a dependence on the quantiles of the delay distribution. We also conduct extensive experiments using synthetic and real-world data and show that our algorithms can fairly select arms with different feedback delays.

Semantic communication has emerged as a promising communication paradigm and there have been extensive research focusing on its applications in the increasingly prevalent multi-user scenarios. However, the knowledge discrepancy among multiple users may lead to considerable disparities in their performance. To address this challenge, this paper proposes a novel multi-pair cooperative semantic knowledge base (SKB) update policy. Specifically, for each pair endowed with SKB-enabled semantic communication, its well-understood knowledge in the local SKB is selected out and uploaded to the server to establish a global SKB, via a score-based knowledge selection scheme. The knowledge selection scheme achieves a balance between the uplink transmission overhead and the completeness of the global SKB. Then, with the assistance of the global SKB, each pair’s local SKB is refined and their performance is improved. Numerical results show that the proposed cooperative SKB update policy obtains significant performance gains with minimal transmission overhead, especially for the initially poor-performing pairs.

Large-scale quantum networks with thousands of nodes require topology-oblivious routing protocols to realize. Most existing quantum network routing protocols only consider the intra-domain scenario, where all nodes belong to a single party with complete topology knowledge. However, like the classical Internet, quantum Internet will likely be provided by multiple quantum Internet Service Providers (qISPs). In this paper, we consider the inter-domain scenario, where the network consists of multiple subnetworks owned by mutually untrusted parties without centralized control. Under this setting, previously proposed quantum entanglement routing policies, which rely on the network topology knowledge, are no longer applicable. We propose a Quantum Border Gateway Protocol (QBGP) for efficiently routing entanglement across qISP boundaries. To guarantee high-quality information transmission, we propose an algorithm named online top-K path selection. This algorithm utilizes the information gain introduced in this paper to adaptively decide on measurement parameters, allowing for the selection of high-fidelity paths and accurate fidelity estimates, while minimizing costs. Additionally, we implement a quantum network simulator and evaluate our protocol and algorithm. Our evaluation shows that QBGP effectively distributes entanglement across different qISPs, and our path selection algorithm increases the network performance by selecting high-fidelity paths with much lower resource consumption than other methods.

Coded caching was introduced in partially cooperative D2D networks where some selfish users keep silent during delivery process. In existing works, unselfish users were randomly selected as delivery proxies for selfish users, resulting in asymmetric utilization of unselfish users. We observe that averaging the transmission load uniformly over unselfish users may achieve better performance. With this motivation, we propose scheme A, which symmetrically employs all unselfish users in delivery, and its transmission rate outperforms the schemes in existing works. Moreover, existing schemes applied the same symmetric cache placement and file splitting strategy as in the fully cooperative D2D networks, which ignored the asymmetry brought by the silent selfish users and thus incurred extra transmission. Consequently, we propose scheme B with an asymmetric file division strategy where the subfiles are exclusively designated to be sent by unselfish users, thus eliminating the proxy transmissions. To evaluate the performance of proposed schemes, a new converse bound is derived by the index coding approach. The joint performance of schemes A and B in certain regime is shown to be exact-optimal under uncoded placement when$S=1$, where$S$represents the number of selfish users. Similar to existing works, schemes A and B require an assumption that$S\leq t-1$, where$t$represents the caching redundancy. When$S\geq t$, we further propose scheme$C$employing uncoded placement, which outperforms the existing MDS-code based scheme in certain regime due to reduction on coding overhead. Numerical simulations are conducted to verify the superior performance of the proposed schemes.

Coded caching is a novel technique to reduce network traffic by exploiting multicast opportunities over users. Practical networks may have two layers of caches, where the central server is first connected to an internal node called a “mirror” (e.g., a base station or wifi router) and this internal node links to end users through a broadcast channel. Previous work [1] shows that there exists a tension between rates in these two layers, and the optimal tradeoff is obtained in a simplified model with one mirror and two users. In this paper, we further consider a more general setting with one mirror and multiple users. The performance limits of coded caching on two-layer networks are obtained under uncoded placement. For converse bounds, it is shown that a linear combination of the worst-case rates in each layer is not less than a threshold. An optimal achievable scheme is designed accordingly to match the novel converse bounds.

Coded caching is an effective method to reduce the traffic load on network bottleneck. While the heterogeneities on the number of requests and cache sizes in coded caching have been studied independently, their joint impact is still unclear. This paper investigates coded caching in scenarios with heterogeneous number of requests and cache sizes. We propose two achievable schemes. The first scheme, based on file grouping and multi-round decentralized coded caching, is demonstrated to be order optimal under the worst setting, i.e., when user with the i-th smallest cache has the i-th largest number of requests. Moreover, we obtain an important insight that the lower bound of the achievable rate is predominantly influenced by users with high$\frac {X_{i}}{M_{i}}$ratios, where$X_{i}$and$M_{i}$represent the number of requests and cache size of user i, respectively. Since the achievable rate of our first scheme is difficult to analyze in the general setting, we further propose the second scheme to derive a tractable upper bound. Based on the insight, the second scheme rearranges the users according to their$\frac {X_{i}}{M_{i}}$ratios and employs a threshold to divide them into the head users who may have a large impact on the lower bound, and the tail users who may have a small impact on the lower bound. The server transmits the demands of the head users directly while applying the first scheme in groups among the tail users. Under the general setting, the gap between the rate of our second scheme and the lower bound is proved to be within a logarithmic factor. Simulations are conducted to verify the superior performance of our proposed schemes.

Link speed in datacenter networks (DCNs) keeps growing rapidly, inducing an increasingly large portion of network flows to become short flows which can be finished within one round-trip time (RTT). This phenomenon makes many existing congestion control schemes ineffective because they iteratively adjust the sending rate based on the latest congestion feedback in multiple rounds. We find that the representative DCQCN scheme for RDMA exhibits substantial performance degradation when there are many short flows, and this is specially true in High Performance Computing (HPC) scenarios where most of Message Passing Interface (MPI) messages are small. In this paper, we propose a data-driven rate control framework which can learn from long-term online data about past rate control decisions via a lightweight online learning technique named Multi-Armed Bandit (MAB) which has a provable performance guarantee. Utilizing the framework, we devise a rate control scheme named Dolce-RC, which dynamically controls the rate increase and reduction by learning from online data. We implement Dolce-RC in commodity smart NICs, and show via testbed experiments and large-scale simulations that compared to DCQCN, Dolce-RC reduces average completion time of MPI messages by up to 68%, while not requiring any modification to switches.

Coded caching is a promising technique for reducing traffic load in wireless networks. In this paper, coded caching is studied for heterogeneous lossy channels, where each user independently suffers packet loss with a distinct and fixed probability. In the original MAN transmission [1], each packet is destined for a specific combinational subset of users. When a packet is received by users beyond the destined subset, it is undecodable and will be dropped. We term these packets as the Overheard Packets (OPs). Interestingly, we find that the OPs can be exploited as side information to increase the multicast gain of the retransmitted packets. With this motivation, we propose a reliable coded caching scheme to reduce the retransmission rate over the shared link. This method enables the users to recover their own lost packets (could be different) from one encoded retransmitted packet. Aided by the OPs, the multicast gain of retransmissions can be increased up to K in certain cases, where K represents the number of users. In other cases, retransmission achieves at least the same multicast gain as the original transmission. Two well-known techniques for reliable transmission are employed in coded caching and serve as baseline schemes. Through both simulations and theoretical analysis we show that the proposed scheme significantly outperforms the baseline schemes in terms of the retransmission rate.

360-degree videos have gained considerable popularity by offering immersive experiences to viewers. However, they consume significantly high bandwidth and demand for specialized caching schemes at the edge network. Previous caching schemes are limited as they either rely on complete historical data or neglect the viewer-varying characteristics in 360-degree videos. In this paper, we present an online caching scheme for 360-degree videos that leverages feedback from sequentially arriving viewers at the network edge. Our scheme consists of two components: an online tile popularity prediction component that accurately predicts the popularity of the tiles with the PopPred algorithm, and an online tile-bitrate caching optimization component that optimizes caching decisions to enhance viewers’ quality of experience (QoE) with the CacheOpt algorithm. We prove that both algorithms have sublinear regret, i.e., $O(\sqrt K ),$ where K is the number of viewers. We also conduct comprehensive experiments using real-world data to show that our caching scheme achieves better performance with lower regrets, higher QoE, and higher hit ratios compared with existing algorithms.

There have been studies that consider optimizing applications in an online learning context using multi-armed bandit models. However, existing frameworks are problematic as they only consider finding the optimal decisions to minimize the regret, but neglect the constraints (or guarantee) requirements that may be excessively violated. In this paper, we formulate the stochastic constrained multi-armed bandit model with either ‘`time-varying’' or ‘`stochastic’' multi-level rewards for network application optimizations with guarantee by taking both regret and violation into consideration. Alongside this model, we design two constrained multi-armed bandit policies, Learning with Guarantee with time-Varying rewards (LG-V) and Learning with Guarantee with Stochastic rewards (LG-S), with provable sub-linear regret and violation bounds. Moreover, we illustrate how our policies can be applied to several emerging network application optimizations, namely, opportunistic multichannel selection, data-guaranteed mobile crowdsensing, and stability-guaranteed crowdsourced transcoding. To show the effectiveness of LG-V and LG-S in optimizing these applications with different requirements, we also conduct extensive simulations by comparing both LG-V and LG-S with existing state-of-the-art policies. We also show the impact of parameter variations, namely, the variations of the guarantee threshold and the number of selected arms, on the regrets and violations of LG-V and LG-S.

There is a growing trend that network applications not only require higher throughput, but also impose stricter delay requirements. The current Internet congestion control, which is driven by active queue management (AQM) algorithms interacting with the Transmission Control Protocol (TCP), has been playing an important role in supporting network applications. However, it still exhibits many open issues. Most of AQM algorithms only deploy a single-queue structure that cannot differentiate flows and easily leads to unfairness. Moreover, the parameter settings of AQM are often static, making them difficult to adapt to the dynamic network environments. In this paper, we propose a general framework for designing "self-tuning" queue management (SQM), which is adaptive to the changing environments and provides fair congestion control among flows. We first present a general architecture of SQM with fair queueing and propose a general fluid model to analyze it. To adapt to the stochastic environments, we formulate a stochastic network utility maximization (SNUM) problem, and utilize online convex optimization (OCO) and control theory to develop a distributed SQM algorithm which can self-tune different queue weights and control parameters. Numerical and packet-level simulation results show that our SQM algorithm significantly improves queueing delay and fairness among flows.

The web link selection problem is to select a small subset of web links from a large web link pool, and to place the selected links on a web page that can only accommodate a limited number of links, e.g., advertisements, recommendations, or news feeds. Despite the long concerned click-through rate which reflects the attractiveness of the link itself, revenue can only be obtained from user actions after clicks, e.g., purchasing after being directed to the product pages by recommendation links. Thus, web links have an intrinsic multi-level feedback structure. With this observation, we consider the context-free web link selection problem, where the objective is to maximize revenue while ensuring that the attractiveness is no less than a preset threshold. The key challenge of the problem is that each link's multi-level feedbacks are stochastic, and unobservable unless the link is selected. We model this problem with a constrained stochastic multi-armed bandit formulation, and design an efficient link selection algorithm, called Constrained Upper Confidence Bound algorithm (Con-UCB). We prove O(sqrt(T ln(T))) bounds on both regret and violation of the attractiveness constraint. We also conduct extensive experiments on three real-world datasets, and show that Con-UCB outperforms state-of-the-art context-free bandit algorithms concerning the multi-level feedback structure.

Network application optimization is essential for improving the performance of the application as well as its user experience. The network application parameters are crucial in making proper decisions for network application optimizations. However, many works are impractical by assuming a priori knowledge of the parameters which are usually unknown and need to be estimated. There have been studies that consider optimizing network application in an online learning context using multi-armed bandit models. However, existing frameworks are problematic as they only consider to find the optimal decisions to minimize the regret, but neglect the constraints (or guarantee) requirements which may be excessively violated. In this paper, we propose a novel online learning framework for network application optimizations with guarantee. To the best of our knowledge, we are the first to formulate the stochastic constrained multi-armed bandit model with time-varying “multi-level rewards” by taking both “regret” and “violation” into consideration. We are also the first to design a constrained bandit policy, Learning with Minimum Guarantee (LMG), with provable sub-linear regret and violation bounds. We illustrate how our framework can be applied to several emerging network application optimizations, namely, (1) opportunistic multichannel selection, (2) data-guaranteed crowdsensing, and (3) stability-guaranteed crowdsourced transcoding. To show the effectiveness of LMG in optimizing these applications with different minimum requirements, we also conduct extensive simulations by comparing LMG with existing state-of-the-art policies.

Mining the characteristics of information spreading in networks is crucial in communication studies, network security management, epidemic investigations, etc. Previous works are restrictive because they mainly focused on the information source detection using either a single observation, or multiple but independent observations of the underlying network while assuming a homogeneous information spreading rate. We conduct a theoretical and experimental study on information spreading, and propose a new and novel estimation framework to estimate 1) information spreading rates, 2) start time of the information source, and 3) the location of information source by utilizing multiple sequential and dependent snapshots where information can spread at heterogeneous rates. Our framework generalizes the current state-of-the-art rumor centrality [1] and the union rumor centrality [2]. Furthermore, we allow heterogeneous information spreading rates at different branches of a network. Our framework provides conditional maximum likelihood estimators for the above three metrics and is more accurate than rumor centrality and Jordan center in both synthetic networks and real-world networks. Applying our framework to the Twitter's retweet networks, we can accurately determine who made the initial tweet and at what time the tweet was sent. Furthermore, we also validate that the rates of information spreading are indeed heterogeneous among different parts of a retweet network.

Selecting the right web links for a website is important because appropriate links not only can provide high attractiveness but can also increase the website's revenue. In this work, we first show that web links have an intrinsic multi-level feedback structure. For example, consider a 2-level feedback web link: the 1st level feedback provides the Click-Through Rate (CTR) and the 2nd level feedback provides the potential revenue, which collectively produce the compound 2-level revenue. We consider the context-free links selection problem of selecting links for a homepage so as to maximize the total compound 2-level revenue while keeping the total 1st level feedback above a preset threshold. We further generalize the problem to links with n (n ≥ 2)-level feedback structure. The key challenge is that the links' multi-level feedback structures are unobservable unless the links are selected on the homepage. To our best knowledge, we are the first to model the links selection problem as a constrained multi-armed bandit problem and design an effective links selection algorithm by learning the links' multi-level structure with provable sub-linear regret and violation bounds. We uncover the multi-level feedback structures of web links in two real-world datasets. We also conduct extensive experiments on the datasets to compare our proposed LExp algorithm with two state-of-the-art context-free bandit algorithms and demonstrate that LExp algorithm is the most effective in links selection while satisfying the constraint.

Geometric routing or geo-routing has been shown as a promising approach to scalable routing in sensor networks. Despite its success in 2-D networks, very few designs are available for 3-D networks that can ensure short routes using only small per-node state, without incurring high load imbalance on the nodes. In this paper, we propose a novel addressing and routing scheme, i.e., OnionMap, for 3-D sensor networks that achieve the above goals, using solely connectivity information and at a linear message cost. The key idea is to decompose a 3-D network into a set of connected layers, which are then mapped to a set of concentric sphere structures (similar to an onion). On each sphere, a discrete Ricci flow method is used to assign each node a set of coordinates that permits purely greedy routing within that sphere; across the different spheres, a layer alignment algorithm helps rotate and scale the spheres, to form a coherent global coordinate system that guides global routing. Theoretical analysis and simulation show OnionMap's advantages over state-of-the-art solutions in path stretch, per-node storage, and load balance.

We study the problem of skeleton extraction for large-scale sensor networks with reliance purely on connectivity information. Existing efforts in this line highly depend on the boundary detection algorithms, which are used to extract accurate boundary nodes. One challenge is that in practical this could limit the applicability of the boundary detection algorithms. For instance, in low node density networks where boundary detection algorithms do not work well, the extracted boundary nodes are often incomplete. This paper brings a new view to skeleton extraction from a distance transform perspective, bridging the distance transform of the network and the incomplete boundaries. As such, we propose a distributed and scalable algorithm for skeleton extraction, called DIST, based on DIStance Transform, while incurring low communication overhead. The proposed algorithm does not require that the boundaries are complete or accurate, which makes the proposed algorithm more practical in applications. First, we compute the distance transform of the network. Specifically, the distance (hop count) of each node to the boundaries of a sensor network is estimated. The node map consisting of the distance values is considered as the distance transform (the distance map). The distance map is then used to identify skeleton nodes. Next, skeleton arcs are generated by controlled flooding within the identified skeleton nodes, thereby connecting these skeleton arcs, to extract a coarse skeleton. Finally, we refine the coarse skeleton by building shortest path trees followed by a prune phase. The obtained skeleton is robust to boundary noise or shape variations. Besides, we present two specific applications that benefit from the extracted skeleton: identifying complete boundaries and shape segmentation. First, with the extracted skeleton using DIST, we propose to identify more boundary nodes to form a meaningful boundary curve. Second, the utilization of the derived skeleton to segment the network into approximately convex pieces has been shown to be effective.

This paper proposes a novel approach, named DIST, to skeleton extraction from incomplete boundaries using the idea of {\em distance transform}, a concept in the computer graphics area. The main contribution is a distributed and low-cost algorithm that produces accurate network skeletons without requiring that the boundaries be complete or tight. The algorithm first establishes the network's distance transform -- the hop distance of each node to the network's boundaries. Based on this, some {\em critical skeleton nodes} are identified. Next, a set of {\em skeleton arcs} are generated by controlled flooding, connecting these skeleton arcs then gives us a coarse skeleton. The algorithm finally refines the coarse skeleton by building shortest path trees, followed by a prune phase. The obtained skeletons are robust to boundary noise and shape variations.