Reconstructing dense geometry for dynamic scenes from a monocular video is a critical yet challenging task. Recent memory-based methods enable efficient online reconstruction, but they fundamentally suffer from a Memory Demand Dilemma: The memory representation faces an inherent conflict between the long-term stability required for static structures and the rapid, high-fidelity detail retention needed for dynamic motion. This conflict forces existing methods into a compromise, leading to either geometric drift in static structures or blurred, inaccurate reconstructions of dynamic objects. To address this dilemma, we propose Mem4D, a novel framework that decouples the modeling of static geometry and dynamic motion. Guided by this insight, we design a dual-memory architecture: 1) The Transient Dynamics Memory (TDM) focuses on capturing high-frequency motion details from recent frames, enabling accurate and fine-grained modeling of dynamic content; 2) The Persistent Structure Memory (PSM) compresses and preserves long-term spatial information, ensuring global consistency and drift-free reconstruction for static elements. By alternating queries to these specialized memories, Mem4D simultaneously maintains static geometry with global consistency and reconstructs dynamic elements with high fidelity. Experiments on challenging benchmarks demonstrate that our method achieves state-of-the-art or competitive performance while maintaining high efficiency.

Vision-Language Navigation (VLN) tasks often leverage panoramic RGB and depth inputs to provide rich spatial cues for action planning, but these sensors can be costly or less accessible in real-world deployments. Recent approaches based on Vision-Language Action (VLA) models achieve strong results with monocular input, yet they still lag behind methods using panoramic RGB-D information. We present MonoDream, a lightweight VLA framework that enables monocular agents to learn a Unified Navigation Representation (UNR). This shared feature representation jointly aligns navigation-relevant visual semantics (e.g., global layout, depth, and future cues) and language-grounded action intent, enabling more reliable action prediction. MonoDream further introduces Latent Panoramic Dreaming (LPD) tasks to supervise the UNR, which train the model to predict latent features of panoramic RGB and depth observations at both current and future steps based on only monocular input. Experiments on multiple VLN benchmarks show that MonoDream consistently improves monocular navigation performance and significantly narrows the gap with panoramic-based agents.

Abstract With the advantages of flexibility and mobility, unmanned aerial vehicles (UAVs) have been widely used in the wireless rechargeable sensor networks (WRSNs) to collect data and supply energy for ground sensor nodes. Due to the limited battery capacity of UAVs and the continuity requirement of WRSN, mobile unmanned vehicles (MUVs) are introduced as mobile charging stations to ensure the energy supply for UAVs and mitigate energy wastage. This paper investigates the problem of Joint Optimization Mission Allocation and Cooperative Trajectory Planning for data collection in WRSNs. The goal is to maximize the minimum energy efficiency by optimizing mission allocation including UAV trajectory and MUV travel. This problem is proved to be NP-hard and solved by two proposed algorithms. The first algorithm incorporates the clustering utilizing the K-Means algorithm and genetic algorithm. The second algorithm is a self-attention architecture based on the reinforcement learning framework and formulate an actor-critic algorithm for training. The simulation results show the feasibility and efficiency of the proposed algorithms, which achieve better performance. The first algorithm has more advantages when the distribution of sensor nodes is relatively concentrated; and the second algorithm may be more suitable when more comprehensive global path planning optimization is required.

Detecting antagonistic near-balanced dense subgraphs is a crucial problem for community search and conflict detection in graph and network analysis, which has wide applications in social media analysis, business, geopolitics etc. To tackle the absence of a unified definition of antagonistic situation, we propose theantagonismmeasure, which quantifies the quality of subgraphs by three dimensions: polarity, internal cohesion, and external antagonistic normalized density. Inspired by the contribution of small antagonistic balanced patterns to antagonism and balance, this paper introduces an efficient algorithmic framework to mine locally specific pattern densest subgraph structure to find subgraphs with high antagonism. We in particular jointly consider$hx$-pattern compact number and L$hx$PDS and design a new Iterative Propose-Prune-and-Verify pipeline in signed graphs (IPPV-s) for top-$k$L$hx$PDS detection. The key contributions are: (1) The antagonism measure is defined, bridging the gap between structural density and balance theory. (2) An efficient algorithmic pipeline that combines convex optimization with maximum flow verification is proposed, which enables scalable and efficient antagonistic near-balanced dense subgraph discovery. (3) Extensive experiments on real signed network datasets show the effectiveness of our approach in uncovering meaningful subgraphs that capture both cooperative and conflicting dynamics.

Federated learning (FL) is a privacy-preserving distributed machine learning framework where multiple devices collaborate with the assistance of an aggregator. However, the limitations of aggregator communication result in only a portion of clients with high data quality being selected to participate in FL, but the quality of clients' data cannot be evaluated without access to the original data. Most existing methods for selecting clients employ a data quality metric with empirically defined scores, which may select clients with high non-ID degrees, thereby reducing the accuracy and freshness of the model. Furthermore, due to the unknown quality of clients' data, current incentive mechanisms lack FL convergence guarantees, which prevent the client behavior from improving the global model accuracy. To address these issues, in this paper, we propose using the gradient difference as a metric for the quality of clients' data, which can quantify the non-IID degree and contribution potential of each client. We formulate a client selection problem using the Combinatorial Multi-Armed Bandit (CMAB) model and design an effective selection strategy, improving the worst-case regret proof to provide a theoretical guarantee for it. Based on these results, we develop an incentive mechanism by the FL convergence analysis, quantifying the utility functions of the aggregator and clients, and modeling their interaction as a two-stage Stackelberg game. For the non-convex utility function, our method establishes the existence and uniqueness of the Stackelberg equilibrium, thereby enabling the determination of the optimal strategy for maximizing the utility of all participants. Finally, extensive simulation experiments on real-world datasets demonstrate the effectiveness of our proposed method compared to state-of-the-art approaches.

Photo-realistic scene reconstruction from sparse-view, uncalibrated images is highly required in practice. Although some successes have been made, existing methods are either Sparse-View but require accurate camera parameters (i.e., intrinsic and extrinsic), or SfM-free but need densely captured images. This paper proposes Dust to Tower (D2T), a novel coarse-to-fine framework to address the coupled difficulty. The key idea is to explicitly narrow down the solution space and then introduce reliable supervision at novel viewpoints without resorting to expensive diffusion-based view synthesis. To do this, we first introduce a Coarse Construction Module (CCM) which exploits a fast Multi-View Stereo model to initialize a 3D Gaussian Splatting (3DGS) and recover initial camera poses. To refine the 3D model at novel viewpoints, we introduce Confidence-Aware Depth Alignment (CADA), which aligns a monocular inverse-depth prior to the reliable regions of the coarse depth using DUSt3R confidence, producing sharp and scale-consistent depth maps for accurate warping. We further propose Warped Image-Guided Inpainting (WIGI), which converts the accurate warped views into multi-view-consistent pseudo supervision via elaborate warping and inpainting process. Experiments on three benchmark datasets show that D2T achieves superior novel view synthesis quality and pose accuracy over ten representative baselines, while keeping high efficiency.

This paper proposes a general solution to enable point cloud recognition models to handle distribution shifts at test time. Unlike prior methods, which rely heavily on training data (often inaccessible during online inference) and are limited to recognizing a fixed set of point cloud classes predefined during training, we explore a more practical and challenging scenario: adapting the model solely based on online test data to recognize both previously seen classes and novel, unseen classes at test time. To this end, we develop Point-Cache, a hierarchical cache model that captures essential clues of online test samples, particularly focusing on the global structure of point clouds and their local-part details. Point-Cache, which serves as a rich 3D knowledge base, is dynamically managed to prioritize the inclusion of high-quality samples. Designed as a plug-and- play module, our method can be flexibly integrated into large multimodal 3D models to support open-vocabulary point cloud recognition. Notably, our solution operates with efficiency comparable to zero-shot inference, as it is entirely training-free. Point-Cache demonstrates substantial gains across 8 challenging benchmarks and 4 representative large 3D models, highlighting its effectiveness. Code is available at https://github.com/auniquesun/Point-Cache.

Deep visual odometry has demonstrated great advancements by learning-to-optimize technology. This approach heavily relies on the visual matching across frames. However, ambiguous matching in challenging scenarios leads to significant errors in geometric modeling and bundle adjustment optimization, which undermines the accuracy and robustness of pose estimation. To address this challenge, this paper proposes MambaVO, which conducts robust initialization, Mamba-based sequential matching refinement, and smoothed training to enhance the matching quality and improve the pose estimation. Specifically, the new frame is matched with the closest keyframe in the maintained Point-Frame Graph (PFG) via the semi-dense based Geometric Initialization Module (GIM). Then the initialized PFG is processed by a proposed Geometric Mamba Module (GMM), which exploits the matching features to refine the overall inter-frame matching. The refined PFG is finally processed by differentiable BA to optimize the poses and the map. To deal with the gradient variance, a Trending-Aware Penalty (TAP) is proposed to smooth training and enhance convergence and stability. A loop closure module is finally applied to enable MambaVO++. On public benchmarks, MambaVO and MambaVO++ demonstrate SOTA performance, while ensuring real-time running.

Collaborative perception in multi-agent system enhances overall perceptual capabilities by facilitating the exchange of complementary information among agents. Current mainstream collaborative perception methods rely on discretized feature maps to conduct fusion, which however, lacks flexibility in extracting and transmitting the informative features and can hardly focus on the informative features during fusion. To address these problems, this paper proposes a novel Anchor-Centric paradigm for Collaborative Object detection (ACCO). It avoids grid precision issues and allows more flexible and efficient anchor-centric communication and fusion. ACCO is composed by three main components: (1) Anchor featuring block (AFB) that targets to generate anchor proposals and projects prepared anchor queries to image features. (2) Anchor confidence generator (ACG) is designed to minimize communication by selecting only the features in the confident anchors to transmit. (3) A local-global fusion module, in which local fusion is anchor alignment-based fusion (LAAF) and global fusion is conducted by spatial-aware cross-attention (SACA). LAAF and SACA run in multilayers, so agents conduct anchor-centric fusion iteratively to adjust the anchor proposals. Comprehensive experiments are conducted to evaluate ACCO on OPV2V and Dair-V2x datasets, which demonstrate ACCO's superiority in reducing the communication volume, and in improving the perception range and detection performances. Code can be found at: https://github.com/sidiangongyuan/ACCO.

Existing tracking-by-detection Multi-Object Tracking methods mainly rely on associating objects with tracklets using motion and appearance features. However, variations in viewpoint and occlusions can result in discrepancies between the features of current objects and those of historical tracklets. To tackle these challenges, this paper proposes a novel Spatial-Temporal Tracklet Graph Matching paradigm (STAR). The core idea of STAR is to achieve long-term, reliable object association through the association of ``tracklet clips (TCs)". TCs are segments of confidently associated multi-object trajectories, which are linked through graph matching. Specifically, STAR initializes TCs using a Confident Initial Tracklet Generator (CITG) and constructs a TC graph via Tracklet Clip Graph Construction (TCGC). In TCGC, each object in a TC is treated as a vertex, with the appearance and local topology features encoded on the vertex. The vertices and edges of the TC graph are then updated through message propagation to capture higher-order features. Finally, a Tracklet Clip Graph Matching (TCGM) method is proposed to efficiently and accurately associate the TCs through graph matching. STAR is model-agnostic, allowing for seamless integration with existing methods to enhance their performance. Extensive experiments on diverse datasets, including MOTChallenge, DanceTrack, and VisDrone2021-MOT, demonstrate the robustness and versatility of STAR, significantly improving tracking performance under challenging conditions.

Vision-Language Navigation is a critical task for developing embodied agents that can follow natural language instructions to navigate in complex real-world environments. Recent advances by finetuning large pretrained models have significantly improved generalization and instruction grounding compared to traditional approaches. However, the role of reasoning strategies in navigation—an action-centric, long-horizon task—remains underexplored, despite Chain-of-Thought reasoning's demonstrated success in static tasks like question answering and visual reasoning. To address this gap, we conduct the first systematic evaluation of reasoning strategies for VLN, including No-Think (direct action prediction), Pre-Think (reason before action), and Post-Think (reason after action). Surprisingly, our findings reveal the Inference-time Reasoning Collaps issue, where inference-time reasoning degrades navigation accuracy, highlighting the challenges of integrating reasoning into VLN. Based on this insight, we propose Aux-Think, a framework that trains models to internalize structured reasoning patterns through CoT supervision during training, while preserving No-Think inference for efficient action prediction. To support this framework, we release R2R-CoT-320k, a large-scale Chain-of-Thought annotated dataset. Empirically, Aux-Think significantly reduces training effort without compromising performance.

The Budget Limited Coreness Maximization (BLCM) problem aims to enhance average user engagement by activating a limited number of connections, i.e., inserting up to b edges to maximize the coreness gain of all vertices in a graph. Due to the cascading feature, we prove the BLCM is NP-hard, APX-hard, and not submodular, meaning greedy sequential edge insertion fails to deliver satisfactory results. As a result, solving BLCM requires combinatorial edge insertion and must face the combinatorial exploration difficulty. This paper proposes the first effective and polynomial-time approach to BLCM. It embeds local combinatorial optimization into global greedy search to boost the benefits of combinatorial optimization while restricting its complexity. Specifically, we propose efficient methods to evaluate the cascaded coreness improvements of two local combinatorial strategies, i.e., when a leader or a group of nodes increase their coreness values via local edge insertion. Note that the key difficulty lies in evaluating the cascading effects. Based on these, we propose three efficient combinatorial edge insertion strategies: (1) Leader-Centric Greedy Insertion (LCGI), (2) Group-Centric Greedy Insertion (GCGI), and (3) a Leader-Group Balance (LGB) insertion. LCGI greedily finds the most influential leader that can produce the highest coreness gain together with its followers. GCGI finds the most influential group that can promote the most coreness gain. LGB combines the two strategies to select edge combinations adaptively. We prove the low complexity of LCGI, GCGI and LGB. Experiments conducted on 13 real-world datasets highlight their practical utility and superiority over existing approaches.

Spatiotemporal Mobile CrowdSourcing (MCS) is a new intelligent sensing paradigm for large-scale data acquisition where requesters can recruit a crowd of workers to perform data collection tasks. How to recruit suitable workers in a dynamic environment to maximize platform utility is a key issue and has become a research hotspot. Many past studies have made great efforts in this regard, but most of them either assume that the worker quality is known in advance or ignore the limitations of workers’ short-term ability to provide resources. In this article, we consider a platform-centered online spatiotemporal MCS system where mobile workers have both long-term and short-term constraints for providing resources, and their quality is unknown to the platform, while the platform has a long-term budget constraint for recruiting workers. We aim to find an online worker scheduling scheme to maximize the platform’s long-term utility without violating the constraints of both workers and the platform. To address this problem, we first transform the long-term utility maximization problem into a real-time utility maximization problem by leveraging the Lyapunov optimization, then design algorithms based on the Upper Confidence Bound (UCB) and Markov approximation to solve each real-time utility maximization problem with unknown worker quality. We demonstrate that our UCB-based algorithm has a sublinear regret and prove that our proposed framework has a performance guarantee for the addressed problem. Finally, we evaluate our design through numerical simulation experiments, and the results demonstrate the effectiveness of our algorithm.

This article proposes a general solution for point set matching that effectively addresses the challenges of low-overlap, sparse, or featureless point set matching (LSFPM). Unlike previous methods that mainly rely on feature or neighborhood similarity that often fail under such difficult conditions, this work proposes a Geometry-based Point Matching (GPM) method. GPM first introduces two geometric concepts: the “Structural Element” (SE) and the “Superstructural Element” (SSE), both of which are constructed based on local geometric structures. The SSE is an enhanced version of the SE. A descriptor for the SE, called the SE Descriptor (SED), is designed to encode the SE and facilitate an efficient geometry-based similarity metric. We demonstrate that the cosine similarity of SEDs is invariant to scale and rotation. Subsequently, a SE Matching Maximization (SEMM) problem is formulated to identify a size-penalized SSE set that maximizes the sum of similarities. This problem is efficiently solved using the proposed SEMM-MCMC (Markov Chain Monte Carlo) algorithm. The matched SSEs then vote on corresponding point matches, generating high-confidence one-to-one matches, low-confidence one-to-one matches and one-to-many matches. Finally, the InferMatch algorithm is proposed to jointly assess low-confidence one-to-one point set matching while simultaneously distinguishing one-to-many point set matching. The GPM approach can also complement other feature-based and motion-based methods. It has been extensively validated on both synthetic and real datasets, demonstrating its versatility in addressing various point set matching problems, and is not limited to the LSFPM problem. Extensive experiments on diverse datasets, including SPair-71k, UAVDT, VisDrone2021-MOT, and SparseMatch, further demonstrate the robustness and versatility of GPM. The proposed approach significantly improves matching performance under challenging conditions and effectively addresses key limitations of existing point set matching methods.

Registering 3D point clouds with low overlap is challenging in 3D computer vision, primarily due to difficulties in identifying small overlap regions and removing correspondence outliers. We observe that the neighborhood similarity can be utilized to detect point correspondence, and the consistent neighborhood correspondence can be used as a criterion to detect robust overlapping regions. So that a Double-layer Multi-scale Star-graph (DMS) structure is proposed to detect robust correspondences using two different types of multi-scale star-graphs. The first-layer Multi-scale Neighbor Feature Star-graphs (MNFS) takes each point as the center and its multi-scale nearest neighbors as the leaves. The MNFS enables to establish the initial correspondence candidate set between the two point clouds based on multi-scale neighborhood topology and feature similarity. Subsequently, each pair of corresponding points find their nearest neighbors within the correspondence sets to construct a Multi-scale Matching Star-graphs (MMS) on each side, so the mutual correspondence relationships between the MMS vertices are identified. These identified mutual correspondences are treated as vertices to construct the Multi-scale Correspondence Star-graphs (MCS), that indicate the relationships among the correspondences. We design edge weight and vertex weight criterion in MCS to detect only the robust correspondence set that has strong neighborhood consistency, so as to reject the outliers. Finally, the point cloud registration is conducted based on the detected robust correspondence. The experimental results demonstrate clearly that the proposed DMS method exhibits superior robustness when compared to existing state-of-the-art registration algorithms.

Registering multiple point clouds (MPC) to form a consistent global map is a crucial problem for various 3D mapping applications, which is however highly challenging due to the tightly coupled difficulties of: 1) identifying the registrable point cloud pairs (RPCPs), 2) detecting the point correspondence in each RPCP, 3) estimating the relative transformation for each RPCP, and 4) aligning the RPCPs to generate the global map. This paper proposes an Iterative Pairing and Transformation (IPT) framework to address above difficulties. A Registrability Graph (RG) is in particular proposed, whose vertices represent the $n$n point clouds and its edges model the registerability between each pair of the point clouds. Registerability is an indicator for whether the relative transformation of the two point clouds can be trustfully estimated. Starting from an $N$N-clique, the obviously unregistrable pairs will be identified through an adaptive coarse registration stage using RANSAC, leading to a sparser RG. For the remained edges in RG, the relative transformation for each registrable pair is accessed by a learning-based pairwise registration algorithm. These pairwise relative poses among vertices are then input into the global registration step, which optimizes and generates globally consistent pose for each point cloud, as well as a global map. Then, based on the global poses of the point clouds, the edges of the RG will be reevaluated to adjusting the registrable pairs, and this local pairing and global optimization process will repeat until convergence. The experimental results show IPT outperforms current state-of-the-art MPC registration algorithms.

View-based methods have demonstrated promising performance in 3D shape understanding. However, they tend to make strong assumptions about the relations between views or learn the multi-view correlations indirectly, which limits the flexibility of exploring inter-view correlations and the effectiveness of target tasks. To overcome the above problems, this article investigates flexible organization and explicit correlation learning for multiple views. In particular, we propose to incorporate different views of a 3D shape into a permutation-invariant set, referred to as View Set, which removes rigid relation assumptions and facilitates adequate information exchange and fusion among views. Based on that, we devise a nimble Transformer model, named VSFormer, to explicitly capture pairwise and higher-order correlations of all elements in the set. Meanwhile, we theoretically reveal a natural correspondence between the Cartesian product of a view set and the correlation matrix in the attention mechanism, which supports our model design. Comprehensive experiments suggest that VSFormer has better flexibility, efficient inference efficiency and superior performance. Notably, VSFormer reaches state-of-the-art results on various 3 d recognition datasets, including ModelNet40, ScanObjectNN and RGBD. It also establishes new records on the SHREC'17 retrieval benchmark.

Bottom-up k-vertex connected component (k- VCC) enumeration methods, referred to as VCCE-BU, have exhib-ited better efficiency compared to the exact top-down k- VCC enumeration method (VCCE-TD). However, VCCE-BU has been found to have surprisingly low detection accuracy, that it may detect fewer k- VCC vertices than VCCE-TD. This raises the question of what causes VCCE-BU to have a low k-VCC enumeration quality. This paper investigates the reason and proposes that the local expansion should be reformulated as a Multiple vertex collaborative Expansion problem instead of the traditional Unitary Expansion (UE). A Multiple Expansion (ME) approach, which allows to expand multiple neighboring vertices jointly and collaboratively is proposed, which is proven exact in local expansion. However, the exact ME-based local expansion needs to explore large neighborhoods in each step, which is time-consuming. To address the efficiency issue, a Ring-based Multiple Expansion (RME) is proposed to conduct ME within one-hop neighbors. A maximum flow-based merging algorithm FBM is proposed for effective merging. A maximal clique and breath-first-search-based quick seeding algorithm QkVCS is proposed to generate k-VCC seeds efficiently. As a result, RIPPLE which integrates QkVCS+FBM+RME is presented as a new accurate and efficient bottom-up approach. Extensive verifications in real large-scale graph datasets demonstrate that even the single-thread RIPPLE is much more accurate and a magnitude faster than the state-of-the-art VCCE-BU method. We also demonstrate the effective speeding up to run RIPPLE in parallel.

The availability of city-scale Lidar maps enables the potential of city-scale place recognition using mobile cameras. However, the city-scale Lidar maps generally need to be compressed for storage efficiency, which increases the difficulty of direct visual place recognition in compressed Lidar maps. This paper proposes VOLoc, an accurate and efficient visual place recognition method that exploits geometric similarity to directly query the compressed Lidar map via the real-time captured image sequence. In the offline phase, VOLoc compresses the Lidar maps using a Geometry-Preserving Compressor (GPC), in which the compression is reversible, a crucial requirement for the downstream 6DoF pose estimation. In the online phase, VOLoc proposes an online Geometric Recovery Module (GRM), which is composed of online Visual Odometry (VO) and a point cloud optimization module, such that the local scene structure around the camera is online recovered to build the Querying Point Cloud (QPC). Then the QPC is compressed by the same GPC, and is aggregated into a global descriptor by an attentionbased aggregation module, to query the compressed Lidar map in the vector space. A transfer learning mechanism is also proposed to improve the accuracy and the generality of the aggregation network. Extensive evaluations show that VOLoc provides localization accuracy even better than the Lidar-toLidar place recognition, setting up a new record for utilizing the compressed Lidar map by low-end mobile cameras. The code are publicly available at https://github.com/Master-cai/VOLoc.

This paper presents a parameter-efficient prompt tuning method, named PPT, to adapt a large multi-modal model for 3D point cloud understanding. Existing strategies are quite expensive in computation and storage, and depend on timeconsuming prompt engineering. We address the problems from three aspects. Firstly, a PromptLearner module is devised to replace hand-crafted prompts with learnable contexts to automate the prompt tuning process. Then, we lock the pre-trained backbone instead of adopting the full fine-tuning paradigm to substantially improve the parameter efficiency. Finally, a lightweight PointAdapter module is arranged near target tasks to enhance prompt tuning for 3D point cloud understanding. Comprehensive experiments are conducted to demonstrate the superior parameter and data efficiency of the proposed method. Meanwhile, we obtain new records on 4 public datasets and multiple 3D tasks, i.e., point cloud recognition, few-shot learning, and part segmentation. The implementation is available at https://github.com/auniquesun/PPT.

Multi-object tracking (MOT) on static platforms, such as by surveillance cameras, has achieved significant progress, with various paradigms providing attractive performances. However, the effectiveness of traditional MOT methods is significantly reduced when it comes to dynamic platforms like drones. This decrease is attributed to the distinctive challenges in the MOT-on-drone scenario: (1) objects are generally small in the image plane, blurred, and frequently occluded, making them challenging to detect and recognize; (2) drones move and see objects from different angles, causing the unreliability of the predicted positions and feature embeddings of the objects. This paper proposes DroneMOT, which firstly proposes a Dual-domain Integrated Attention (DIA) module that considers the fast movements of drones to enhance the drone-based object detection and feature embedding for small-sized, blurred, and occluded objects. Then, an innovative Motion-Driven Association (MDA) scheme is introduced, considering the concurrent movements of both the drone and the objects. Within MDA, an Adaptive Feature Synchronization (AFS) technique is presented to update the object features seen from different angles. Additionally, a Dual Motion-based Prediction (DMP) method is employed to forecast the object positions. Finally, both the refined feature embeddings and the predicted positions are integrated to enhance the object association. Comprehensive evaluations on VisDrone2019-MOT and UAVDT datasets show that DroneMOT provides substantial performance improvements over the state-of-the-art in the domain of MOT on drones. The code will be available at https://github.com/PenK1nG/DroneMOT.

Image matching aims at identifying corresponding points between a pair of images. Currently, detector-free methods have shown impressive performance in challenging scenarios, thanks to their capability of generating dense matches and global receptive field. However, performing feature interaction and proposing matches across the entire image is unnecessary, because not all image regions contribute to the matching process. Interacting and matching in unmatchable areas can introduce errors, reducing matching accuracy and efficiency. Meanwhile, the scale discrepancy issue still troubles existing methods. To address above issues, we propose PRogressive dependency maxImization for Scale-invariant image Matching (PRISM), which jointly prunes irrelevant patch features and tackles the scale discrepancy. To do this, we firstly present a Multi-scale Pruning Module (MPM) to adaptively prune irrelevant features by maximizing the dependency between the two feature sets. Moreover, we design the Scale-Aware Dynamic Pruning Attention (SADPA) to aggregate information from different scales via a hierarchical design. Our method's superior matching performance and generalization capability are confirmed by leading accuracy across various evaluation benchmarks and downstream tasks. The code is publicly available at https://github.com/Master-cai/PRISM.

Collaborative autonomous driving with multiple vehicles usually requires the data fusion from multiple modalities. To ensure effective fusion, the data from each individual modality shall maintain a reasonably high quality. However, in collaborative perception, the quality of object detection based on a modality is highly sensitive to the relative pose errors among the agents. It leads to feature misalignment and significantly reduces collaborative performance. To address this issue, we propose RoCo, a novel unsupervised framework to conduct iterative object matching and agent pose adjustment. To the best of our knowledge, our work is the first to model the pose correction problem in collaborative perception as an object matching task, which reliably associates common objects detected by different agents. On top of this, we propose a graph optimization process to adjust the agent poses by minimizing the alignment errors of the associated objects, and the object matching is re-done based on the adjusted agent poses. This process is carried out iteratively until convergence. Experimental study on both simulated and real-world datasets demonstrates that the proposed framework RoCo consistently outperforms existing relevant methods in terms of the collaborative object detection performance, and exhibits highly desired robustness when the pose information of agents is with high-level noise. Ablation studies are also provided to show the impact of its key parameters and components. The code is released at https://github.com/HuangZhe885/RoCo.

This paper investigates the 3D domain generalization (3DDG) ability of large 3D models based on prevalent prompt learning. Recent works demonstrate the performances of 3D point cloud recognition can be boosted remarkably by parameter-efficient prompt tuning. However, we observe that the improvement on downstream tasks comes at the expense of a severe drop in 3D domain generalization. To resolve this challenge, we present a comprehensive regulation framework that allows the learnable prompts to actively interact with the well-learned general knowledge in large 3D models to maintain good generalization. Specifically, the proposed framework imposes multiple explicit constraints on the prompt learning trajectory by maximizing the mutual agreement between task-specific predictions and task-agnostic knowledge. We design the regulation framework as a plug-and-play module to embed into existing representative large 3D models. Surprisingly, our method not only realizes consistently increasing generalization ability but also enhances task-specific 3D recognition performances across various 3DDG benchmarks by a clear margin. Considering the lack of study and evaluation on 3DDG, we also create three new benchmarks, namely base-to-new, cross-dataset and few-shot generalization benchmarks, to enrich the field and inspire future research. Code and benchmarks are available at \url{https://github.com/auniquesun/Point-PRC}.

Mobile crowdsourcing (MCS) is a promising way to monitor urban-scale data by leveraging the crowds’ power and has attracted much attention recently. How to recruit suitable workers for requesters to perform the published sensing tasks is always a crucial problem and also a research hotspot. Many attempts have been made in past literature to maximize social welfare or to motivate workers to participate in the mobile crowdsourcing (MCS). However, most existing works do not consider the individual sensing quality requirements of tasks, which may not be suitable for some special scenarios, such as monitoring tasks of locations with different importance levels. In this work, we investigate the optimal worker selection problem for collaborative MCS, in which we study the recruitment cost minimization problem to meet individual sensing quality requirements of tasks for the requester-centric MCS, as well as the profit maximization problem for the platform-centric MCS. Both of the studied problems are proved to be NP-hard, and thus we design corresponding approximation algorithms for them. Specifically, to solve the recruitment cost minimization problem for requester-centric MCS, we design two different polynomial time algorithms, both of which have performance guarantees. For the profit maximization problem for platform-centric MCS, we introduce a double-greedy-based algorithm and then use the iterative pruning technique to ensure the performance guarantee of our algorithm with a much weaker condition. Finally, we evaluate our algorithms through numerical simulation experiments and validate the effectiveness of our designs by comparing them with baselines under different parameter settings.

Wireless Rechargeable Sensor Networks (WRSNs) have been widely utilized and have played an important role in many surveillance application scenarios. The optimization of the charging process is beneficial for guaranteeing continuous coverage and enhancing the charging efficiency of WRSNs. And there are several influence factors of the charging process, like the sensors’ battery consumption mode, the chargers’ charging pattern and the environmental factors, which should be considered into the charging model. Based on the charging model via assigning sensors’ charging priority weights, we introduce the spatio-temporal optimization for charging scheduling (STO-CS) Problem in WRSNs for the goals of meeting the on-demand charging requirements and saving the charging consumption. We prove the NP-hardness of the problem and propose two algorithms to solve it. The first algorithm is based on two-phase dynamic programming and is proved to find the optimal solution when the charging ability is sufficient; the second algorithm adopts the clustering idea with K-Means Algorithm which has better time complexity. A series of simulation experiments are performed to compare the performance of the proposed algorithms in terms of the charging cost and the running time, whose results are analyzed to conclude that they can be applied to the application scenarios with the accuracy requirements and the real-time requirements respectively.

Detecting locally, non-overlapping, near-clique densest subgraphs is a crucial problem for community search in social networks. As a vertex may be involved in multiple overlapped local cliques, detecting locally densest sub-structures considering h -clique density, i.e., locally h-clique densest subgraph (LhCDS) attracts great interests. This paper investigates the L h CDS detection problem and proposes an efficient and exact algorithm to list the top- k non-overlapping, locally h -clique dense, and compact subgraphs. We in particular jointly consider h -clique compact number and L h CDS and design a new ''Iterative Propose-Prune-and-Verify'' pipeline (IPPV) for top- k L h CDS detection. (1) In the proposal part, we derive initial bounds for h -clique compact numbers; prove the validity, and extend a convex programming method to tighten the bounds for proposing L h CDS candidates without missing any. (2) Then a tentative graph decomposition method is proposed to solve the challenging case where a clique spans multiple subgraphs in graph decomposition. (3) To deal with the verification difficulty, both a basic and a fast verification method are proposed, where the fast method constructs a smaller-scale flow network to improve efficiency while preserving the verification correctness. The verified L h CDSes are returned, while the candidates that remained unsure reenter the IPPV pipeline. (4) We further extend the proposed methods to locally more general pattern densest subgraph detection problems. We prove the exactness and low complexity of the proposed algorithm. Extensive experiments on real datasets show the effectiveness and high efficiency of IPPV. Codes are available at: https://github.com/Elssky/IPPV

When the edge between two nodes is not measured, is there any hint to know the edge property, and will the inferred edge property be useful? To answer these questions, this paper uniformly defines the properties of unmeasurable edges in generic graphs. For an unmeasurable edge$(i,j)$, it is called rangeable if its length is unique in any realization of the graph, rigid if the number of its possible lengths is finite, and flexible if it has infinite possible lengths. The rangeable edge can provide deterministic hidden knowledge as if the edge is measured. A condition for an unmeasured edge being rangeable in 2D space is firstly proposed, based on which a centralized identification algorithm (DRE) is designed. However, the centralized rangeable edge identification has the overhead of global information collection. Therefore distributed condition and algorithm to identify rangeable edges are further investigated. We prove that an unmeasurable edge$(i,j)$is rangeable if there are at least two Disjoint Minimally Rigid Branches (DMRBs) between$i$and$j$. The unmeasurable edge$(i,j)$is rigid and flexible when the number of DMRB is one and zero, respectively. A distributed Branching and Blacklisting (BB) algorithm is proposed to find DMRBs, so that rangeable edges are identified distributively. Then, the applications of rangeable, rigid, and flexible edges are discussed. Experimental evaluations show that the centralized and distributed algorithms can identify a rich set of unmeasurable but rangeable edges in distance graphs, even more than the number of directly measured edges. Moreover, BB has a similar identification performance as the centralized DRE algorithm and outperforms existing distributed unmeasurable edge inference algorithms significantly.

Identifying the Maximal Rigid subGraphs (MRGs) whose relative formations cannot deform continuously in$\Re ^{d}$, is a fundamental problem in network formation control and network localization. When$d=3$, it becomes extremely challenging and has been open for decades because the fundamental Laman condition doesn’t hold in$\Re ^{3}$. This paper presents a new understanding of this problem. Because of the existence of “implicit hinges” in 3D, its essence should be to detect the Maximal Rigid Clusters (MRCs). An MRC is a maximal set of vertices in which each vertex is mutually rigid to the others, but the vertices are not necessarily connected. We show that the MRGs in the original graph can be easily deduced from the connected components generated by the MRCs. For efficiently identifying the MRCs, at first, a randomized algorithm to detect mutually rigid vertex pairs is exploited. Based on this, a Basic MRC Identification algorithm (BMI) is proposed, which is an exact algorithm that can detect all MRCs based on the extracted rigid vertex pairs, but it has$O(|V|^{4})$time complexity. To further pursue an efficient algorithm, we observe the “hinge MRCs” appear rarely. So an Efficient framework for MRC Identification (EMI) is proposed. It consists of two steps: 1) a Trimmed-BMI algorithm that guarantees to detect all simple MRCs and may miss only hinge MRCs; 2) a Trim-FIX algorithm that can find all hinge MRCs. We prove EMI can guarantee to detect all the MRCs as accurately as BMI, using$O(|V|^{3})$times. Further, we show EMI achieves magnitudes of times faster than BMI in experiments. Extensive evaluations verify the effectiveness and high efficiency of EMI in various 3D networks. We have uploaded the code of the related program tohttps://github.com/fdwqh/EMI-algorithm.

Ranging-based localization is a fundamental problem in the Internet of Things and unmanned aerial vehicle networks. However, the nodes’ limited-ranging scope and users’ broad coverage purpose inevitably cause network sparsity or subnetwork sparsity. The performances of existing localization algorithms are extremely unsatisfactory in sparse networks. A crucial way to deal with the sparsity is to exploit the hidden knowledge provided by the unmeasured edges, which inspires this work to propose a hypothesis-based Joint Edge Inference and Localization algorithm called InferLoc . InferLoc mines the Unmeasured but Inferable Edges (UIEs). Each UIE is an unmeasured edge, but it is restricted through other edges in the network to be inside a rigid component, so it has only a limited number of possible lengths. We propose an efficient method to detect UIEs and geometric approaches to infer possible lengths for UIEs in 2D and 3D networks. The inferred possible lengths of UIEs are then treated as multiple hypotheses to determine the node locations and the lengths of UIEs simultaneously through a joint graph optimization process. In the joint graph optimization model, to make the 0/1 decision variables for hypotheses selection differentiable, differentiable functions are proposed to relax the 0/1 selections, and rounding is applied to select the final length after the optimization converges. We also prove the condition when a UIE can contribute to sparse localization. Extensive experiments show remarkably better accuracy and efficiency performances of InferLoc than the state-of-the-art network localization algorithms. In particular, it reduces the localization errors by more than 90% and speeds up the convergence time more than 100 times than that of the widely used G2O-based methods in sparse networks.

Recently, a growing number of work design unsupervised paradigms for point cloud processing to alleviate the limitation of expensive manual annotation and poor transferability of supervised methods. Among them, CrossPoint follows the contrastive learning framework and exploits image and point cloud data for unsupervised point cloud understanding. Although the promising performance is presented, the unbalanced architecture makes it unnecessarily complex and inefficient. For example, the image branch in CrossPoint is ~8.3x heavier than the point cloud branch leading to higher complexity and latency. To address this problem, in this paper, we propose a lightweight Vision-and-Pointcloud Transformer (ViPFormer) to unify image and point cloud processing in a single architecture. ViPFormer learns in an unsupervised manner by optimizing intra-modal and cross-modal contrastive objectives. Then the pretrained model is transferred to various downstream tasks, including 3D shape classification and semantic segmentation. Experiments on different datasets show ViPFormer surpasses previous state-of-the-art unsupervised methods with higher accuracy, lower model complexity and runtime latency. Finally, the effectiveness of each component in ViPFormer is validated by extensive ablation studies. The implementation of the proposed method is available at https://github.com/auniquesun/ViPFormer.

Over the past years, augmented reality (AR) based on mobile phones has gained great attention. When multiple phones are used in AR applications, collaborative simultaneous localization and mapping (SLAM) is considered one of the enabling technologies, i.e., multiple mobile phones complete the localization and mapping through collaboration. However, the state-of-the-art collaborative SLAM systems not only suffer from the delays introduced by a high-complexity graph optimization problem, but also may exhibit varying levels of accuracy across dissimilar environments or different types of mobile devices. In this paper, we propose a scalable and robust collaborative SLAM system, point-line-based Collaborative SLAM (ColSLAM). Technically, ColSLAM includes two innovative features that help achieve satisfactory scalability and robustness. First, a mapping cacher (MC) is designed for each agent on the server, which uses global keyframes to detect loop closures, updates the cached local map, and quickly responds to the agent's pose drifts. With MC, each agent's local pose is corrected using global knowledge in real-time. Secondly, to improve the robustness performance, ColSLAM employs point-line-fusion-based Visual Inertial Odometry (VIO), point-line-fusion-based NetVLAD loop detection, and an enhanced geometric verification and relative pose calculation method called PNPL. Empirical evaluations based on the EuRoc dataset and real degenerate environments demonstrate that ColSLAM outperforms the existing collaborative SLAM systems in terms of accuracy, robustness, and scalability.

Distributed estimation of 6-DOF relative states, including three-dimensional relative poses and three-dimensional relative positions, is a key problem in UAV (Unmanned Aerial Vehicle) networks, which generally requires vision-involved iterative state estimation. How to achieve communication efficiency is a crucial challenge considering the large volume of vision data. This paper jointly considers the communication efficiency, latency, and accuracy for distributed relative state estimation involving vision data in UAV networks. The key is to solve a distributed graph optimization problem, which includes two key steps: (1) local graph construction and node state initialization in an initialization phase, and (2) iterative state update and communication with neighbors until convergence in online iteration phase. A communication efficient, Locating Then Informing (LTI) initialization scheme is proposed, which is run only once by each node to initialize each node’s local graph and initial states. For online iteration, a RIPPLE-like distributed state iteration scheme is proposed. It inherits the advantages of traditional sequential and parallel methods while avoiding their drawbacks. It enables nodes’ states to converge quickly using fewer rounds of communications. The communication costs for the initialization and online iteration processes are analyzed theoretically. Extensive evaluations use synthetic data generated by AirSim (a widely used UAV network simulation platform) and real-world data are presented. The results show that the proposed method provides accuracy comparable to the centralized graph optimization method and significantly outperforms the other distributed methods in terms of accuracy, communication cost, and latency.

Attracted by the inherent security and privacy protection of the blockchain, incorporating blockchain into Internet of Things (IoT) has been widely studied in these years. However, the mining process requires high computational power, which prevents IoT devices from directly participating in blockchain construction. For this reason, edge computing service is introduced to help build the IoT blockchain, where IoT devices could purchase computational resources from the edge servers. In this paper, we consider the case that IoT devices also have other tasks that need the help of edge servers, such as data analysis and data storage. The profits they can get from these tasks is closely related to the amounts of resources they purchased from the edge servers. In this scenario, IoT devices will allocate their limited budgets to purchase different resources from different edge servers, such that their profits can be maximized. Moreover, edge servers will set “best” prices such that they can get the biggest benefits. Accordingly, there raise a pricing and budget allocation problem between edge servers and IoT devices. We model the interaction between edge servers and IoT devices as a multi-leader multi-follower Stackelberg game, whose objective is to reach the Stackelberg Equilibrium (SE). We prove the existence and uniqueness of the SE point, and design efficient algorithms to reach the SE point. In the end, we verify our model and algorithms by performing extensive simulations, and the results show the correctness and effectiveness of our designs.

The barycentric linear localization (BLL) methods provide a lightweight, distributed way to calculate locations for resource-limited IoT devices. A crucial requirement for BLL is that the nodes participating in the iterative location propagation are localizable. Otherwise, the unlocalizable nodes will continuously pose error information in the location propagation process, making even the theoretically localizable nodes converge to the wrong locations. However, the research on node localizability in BLL is much lacked, greatly limiting the application scope of BLL. In specific, BLL node localizability is detected on a generated graph$\mathcal {G^{A}}$. For any node, its neighbors appear in$\mathcal {G^{A}}$only when the neighbors can form triangle(s), so that$\mathcal {G^{A}}$is much sparser than the original$\mathcal G$. Thus, the node localizability condition in BLL is harder to be satisfied than that in traditional localization methods. Moreover, the distributed algorithm to detect BLL localizable nodes is still open. This paper thoroughly investigates the node localizability conditions and distributed localizable node detection algorithms in BLL. At first, an efficient and fully distributed Negative Edge Inference (NEI) algorithm is proposed for each node to infer implicit edges in its neighborhood. NEI strengthens the distance graph by revealing more distance constraints so that enables more neighboring triangles. Then a new sufficient condition, i.e., the recursive three disjoint path condition (Recursive-3DP) on the strengthened distance graph is proposed to identify BLL localizable nodes much more accurately. Secondly, a distributed Path Extension and Pruning (PEP) algorithm is proposed for distributed localizable node detection. PEP is proved to detect all the theoretically Recursive-3DP nodes in the strengthened distance graph. A Fast-PEP algorithm is further proposed, which misses very limited Recursive-3DP nodes while bringing significant improvement in efficiency. PEP and Fast-PEP guarantee to identify BLL localizable nodes in$2H$rounds, where$H$is the maximum hop number of the node disjoint paths. Finally, by using NEI and PEP (Fast-PEP), a localizability-aware BLL (LABEL) method is proposed, which correctly identifies localizable nodes and guarantees their correct location convergence. Extensive analysis and experiments show the advantages in localizability and location accuracy of the proposed schemes over the state-of-the-art methods.

Determining whether nodes can be uniquely localized, called localizability detection, is a concomitant problem in network localization. Localizability detection under the traditional Non-Linear Localization (NLL) schema has been well explored, whereas localizability under the emerging Barycentric coordinate-based Linear Localization (BLL) schema has not been well investigated. Non-awareness of the node localizability in BLL may cause theoretically localizable nodes to converge to wrong locations because their locations are impacted by the wrong locations of the unlocalizable nodes through the iterative location propagation. In this article, the deficiency of existing localizability theories and algorithms in BLL is firstly investigated and then a necessary condition and a sufficient condition for BLL node localizability detection are proposed. Based on these two conditions, an efficient Iterative Maximum Flow (IMF) algorithm is designed to identify BLL localizable nodes, and only localizable nodes are selected to enable a Localizability Aware Barycentric Linear Localization (LABLL) algorithm, which can guarantee the locations of the localizable nodes converging correctly. The proposed IMF and LABLL algorithms are validated by both theoretical analysis and experimental evaluations.

Partitioning the Maximal Redundant Rigid Components (MRRC) and Maximal Global Rigid Components (MGRC) in generic 2D graphs are critical problem for network structure analysis, network localizability detection, and localization algorithm design. This article presents efficient algorithms to partition MRRCs and MGRCs and develops an open-sourced toolbox, GPART, for these algorithms to be conveniently used by the society. We firstly propose conditions and an efficient algorithm to merge the over-constrained regions to form the maximal redundant rigid components (MRRC). The detected MRRCs are proved to be maximal and all the MRRCs are guaranteed to be detected. The time to merge the over-constrained regions is linear to the number of nodes in the over-constrained components. To detect MGRCs, the critical problem is to decompose 3-connected components in each MRRC. We exploit SPQR-tree based method and design a local optimization algorithm, called MGRC_acce to prune the unnecessary decomposition operations so that the SPQR-tree functions can be called much less number of times. We prove the MGRCs can be detected inside MRRCs using at most O(mn ) time. Then a GPART toolbox is developed and extensively tested in graphs of different densities. We show the proposed MRRC and MGRC detection algorithms are valid and MGRC_acce greatly outperforms the direct SPQR-tree based decomposition algorithm. GPART is outsourced at https://github.com/inlab-group/gpart .

Inferring network topology via inter-node distance measurements is an important problem. It is challenging when the distance measurements are sparse because the lack of edge constraints may lead to ambiguous realizations that differ greatly from the ground truth. The flipping ambiguities are caused by binary vertex cut sets in 2D and triple vertex cut sets in 3D, which are calledseparators. This paper investigates conditions on whether the flipping ambiguities caused by these separators can be disambiguated using neighborhood, full graph, and component-level conditions. Accordingly, local flipping-free condition (LFFC), global flipping-free condition (GFFC), and component-based flipping free condition (CFFC) are proposed. Then a disambiguating framework based on a combinatorial application of these conditions is proposed. It detects separators and first disambiguate separators locally by LFFC, which converts the graph to a binary tree, whose leaf nodes are flipping-free components and edges are LFFC unsolvable separators. Then the CFFC condition is further applied to disambiguate LFFC unsolvable separators between components. If$k$and$g$separators are disambiguated by LFFC and CFFC respectively, the number of ambiguous solutions for network localization will be reduced by${2^{k+g}}$times. Finally, the flipping-free components realize node coordinates in their local coordinate systems and a residue-based weighted component stitching algorithm (RWCS) is proposed to iteratively synchronize components’ local coordinates to generate global coordinates of the network. Extensive simulations show the LFFC, CFFC and RWCS frameworks are efficient, which resolve a major portion of flipping ambiguities and greatly improve the localization accuracy than the state of art algorithms in various sparse network settings.

Cyberbullying has caused serious consequences especially for social network users in recent years. However, the challenge is how to fight against the cyberbullying effectively from the algorithmic perspective. In this article, we study the fighting against the cyberbullying problem, i.e., identify an initial witness set with a budget to spread the positive influence to protect the users in a specific target set such that the number of cybervictim users in the target set being activated by the seed set of cyberbullying is minimized. We first formulate this problem and show its NP-hardness. We further prove that the objective function is submodular with respect to the size of witnesses set when we convert the original problem into the maximal version. Then we propose a stochastic approach to solve this maximal version problem based on the Reverse Sampling Technique with a constant factor guarantee. In addition, we provide theoretical analysis and discuss the relationship between the optimal value and the value returned by the proposed algorithm. To evaluate the proposed approach, we implement extensive experiments on synthetic and real datasets. The experimental results show our approach is superior to the comparison methods.

The increasing availability of autonomous small-size Unmanned Aerial Vehicles (UAVs) has provided a promising way for data gathering from Wireless Sensor Networks (WSNs) with the advantages of high mobility, flexibility, and good speed. However, few works considered the situations that multiple UAVs are collaboratively used and the fine-grained trajectory plans of multiple UAVs are devised for collecting data from network including detailed traveling and hovering plans of them in the continuous space. In this paper, we investigate the problem of the Fine-grained Trajectory Plan for multi-UAVs (FTP), in which m UAVs are used to collect data from a given WSN, where m ≥ 1. The problem entails not only to find the flight paths of multiple UAVs but also to design the detailed hovering and traveling plans on their paths for efficient data gathering from WSN. The objective of the problem is to minimize the maximum flight time of UAVs such that all sensory data of WSN is collected by the UAVs and transported to the base station. We first propose a mathematical model of the FTP problem and prove that the problem is NP-hard. To solve the FTP problem, we first study a special case of the FTP problem when m = 1, called FTP with Single UAV (FTPS) problem. Then we propose a constant-factor approximation algorithm for the FTPS problem. Based on the FTPS problem, an approximation algorithm for the general version of the FTP problem when m > 1 is further proposed, which can guarantee a constant factor of the optimal solution. Afterwards, the proposed algorithms are verified by extensive simulations.

Following the recent advances in the Internet of Things (IoT), it is drawing lots of attention to design distributed algorithms for various network optimization problems under the SINR (Signal‐to‐Interference‐and‐Noise‐Ratio) interference model, such as spanner construction. Since a spanner can maintain a linear number of links while still preserving efficient routes for any pair of nodes in wireless networks, it is important to design distributed algorithms for spanners. Given a constant t > 1 as the required stretch factor, the problem of our concern is to design an efficient distributed algorithm to construct a t‐spanner of the communication graph under SINR such that the delay for the task completion is minimized, where the delay is the time interval between the time slot that the first node commences its operation to the time slot that all the nodes finish their task of constructing the t‐spanner. Our main contributions include four aspects. First, we propose a proximity range and proximity independent set (PISet) to increase the number of nodes transmitting successfully at the same time in order to reduce the delay. Second, we develop a distributed randomized algorithm SINR‐Spanner to construct a required t‐spanner with high probability. Third, the approximation ratio of SINR‐Spanner is proven to be a constant. Finally, extensive simulations are carried out to verify the effectiveness and efficiency of our proposed algorithm.

Inferring nodes' locations by inter-node measurements is a crucial problem in the IoT era. Despite the various approaches to this problem, obtaining accurate results is still challenging when the measurements are noisy, sparse, or uneven. Such unsatisfactory measurements are, however, inevitable for the general consideration of the deployment cost and the limited sensing scope.This paper proposes a Hierarchical Graph Optimization (HGO) framework to address the network localization problem when the measurements are sparse and noisy. It firstly efficiently extracts the dense sub-graphs and realizes their local structures in local coordinate systems. The local structures of dense components are rather accurate for the local sufficiency of the measurements. Then, the noises of the inter-edges that sparsely connect the dense sub-graphs are found as the main course of the network localization errors. A close-loop condition is derived and two denoising algorithms are proposed to set up linear equation arrays to correct the noises of these critical edges. After that, a projection algorithm is proposed to realize a smoothed backbone graph using the corrected critical edges, and finally, a hierarchical registration method is proposed to register the realized backbone and the dense sub-components to produce the global network structure. A parallel implementation is further developed, which speeds up HGO in large scale networks. Extensive simulations verify that HGO consistently outperforms existing network localization algorithms in terms of accuracy, efficiency, and reliability under various measurement settings.

As a promising technology to achieve perpetual operation of battery-powered wireless sensor devices, wireless power transfer has attracted much attention recently. In wireless power transfer, the charger enables the energy to be wirelessly transmitted to the rechargeable sensor devices that are hungry for energy. Previous works mainly focus on maximizing the charging utility or minimizing the charging delay. This paper concerns a more practical issue of placing wireless chargers, which aims at minimizing the deployment cost of chargers while satisfying the overall requirement for charging utility. We investigate the above cost-minimum charger placement problem under two typical scenarios in which omni chargers and directional chargers are used, respectively. To resolve this problem under the two charging models, we first prove its NP-hardness and then propose two approximation algorithms with proven performance guarantees. Finally, we conduct extensive simulation experiments to validate our designs, and the experimental results demonstrate that the proposed algorithms significantly outperform the baselines.

In traditional viral marketing, the goal is to reach out to the maximum number of people. However, some studies have demonstrated that spreading a product indiscriminately in a network can cause some counter effect because it may reach people who evaluate it negatively. In this paper, we study how to make use of social networks to avoid negative people so that the 'positive effect' of viral marketing can be maximized, and this optimization problem is called Strengthening the Positive Effect (SPE). SPE has a non-monotone and non-submodular objective function, and it is NP-hard to be approximately solved with any positive factor. Although SPE is almost impossible to solve approximately, we make the pioneer contribution by discovering that: 1) The almost optimal solution is obtainable in some network; 2) For the general network, a polynomial algorithm that yields a multiplicative guarantee is also possible under a reasonable assumption. We test our solution on various realworld social networks with a comprehensive set of experiments. The result affirms that besides its performance analyzability, our solution is more scalable than the current heuristic.

The growing importance of social network for sharing and spreading various contents is leading to the changes in the way of information diffusion. To what extent can social content be diffused highly depends on the size of seed nodes and connectivity of the network. If the seed set is predetermined, then the best way to maximize the content spread is to add connectivities among the users. The existing work shows the content spread maximization problem to be NP-hard. One of the difficulties of designing an effective and efficient algorithm for the content spread maximization problem lies in that the objective function we aim to maximize lacks submodularity. In our work, we formulate the maximize content spread problem from an incremental marginal gain perspective. Although the objective function we derive is not submodular, both submodular lower and upper bounds are constructed and proved. Therefore, we apply the sandwich framework and devise a marginal increment-based algorithm (MIS) that guarantees a data-dependent factor. Furthermore, a novel scalable content spread maximization algorithm influence ranking and fast adjustment (IRFA), which is based on the influence ranking of a single node and fast adjustment with each boosting step in the network, is proposed. Through extensive experiments, we demonstrate that both MIS and IRFA algorithms are effective and outperform other edge selection strategies.

In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized. We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods.

One significant problem in exchange networks is finding the equilibrium. To solve this problem, the concept of stable outcome has been developed. However, there are few effective methods to solve it from the point of graph theory. In this paper, we propose a minimum cost stable outcome (MCSO) problem, which is to find a stable outcome whose total transaction cost is minimized. Two algorithms have been designed to solve this problem on unit and general profit networks respectively. For unit profit networks, we use minimum cost edge cover based method to give the optimal solution. For general profit networks, we develop an approximate algorithm and prove that performance ratio is no more than twice the optimal value. Moreover, we provide the probabilistic analysis. At last, extensive experiments have been conducted on synthetic and real-life datasets. Experimental results validate the performance of the proposed algorithms.

Accurate and robust localization is crucial for wireless ad-hoc and sensor networks. Among the localization techniques, component-based methods advance themselves for conquering network sparseness and anchor sparseness. But component-based methods are sensitive to ranging noises, which may cause a huge accumulated error either in component realization or merging process. This paper presents three results for robust component-based localization under ranging noises. (1) For a rigid graph component, a novel method is proposed to evaluate the graph's possible number of flip ambiguities under noises. In particular, graph's \emph{MInimal sepaRators that are neaRly cOllineaR (MIRROR) } is presented as the cause of flip ambiguity, and the number of MIRRORs indicates the possible number of flip ambiguities under noise. (2) Then the sensitivity of a graph's local deforming regarding ranging noises is investigated by perturbation analysis. A novel Ranging Sensitivity Matrix (RSM) is proposed to estimate the node location perturbations due to ranging noises. (3) By evaluating component robustness via the flipping and the local deforming risks, a Robust Component Generation and Realization (RCGR) algorithm is developed, which generates components based on the robustness metrics. RCGR was evaluated by simulations, which showed much better noise resistance and locating accuracy improvements than state-of-the-art of component-based localization algorithms.

We study the problem to maximize the profit for a social network host who offers viral marketing to multiple company campaigners. Each campaigner has its special interest for social network users, and she pays the host commission when a target user adopts her product. The campaigners decide the cost they are willing to pay for viral marketing, and the host collects cost from all campaigners and uses it for marketing. We call our optimization problem Competitive PROfit maximization for the host (CPro), and its solution is the seed allocation for campaigners, such that the profit (commission) campaigners given back to the host is maximized. CPro is NP-hard with a non-monotone and non-submodular objective function, which means existing techniques in influence or profit maximization cannot give guaranteed performance. To solve this issue, we design an efficient approximation algorithm that works on billion-scale networks, and more importantly, we give the performance bound of our algorithm. As far as we know, this is the first bounded scalable approximation algorithm for competitive profit maximization. A comprehensive set of experiments are set on various real networks with up to several billion edges from diverse disciplines, and our solution identifies the top choices for the host in only a few minutes on network that contains 1.5 billion edges.

A swarm of unmanned air vehicles (UAVs) may form a dynamic 3-D network whose topology changes frequently. Tracking the geometric formation of the network is a critical problem. Recent advantage of wireless ranging technologies (e.g., ultrawideband) enables inter-UAV distance measurement up to hundreds meters with errors in centimeter level. This makes it possible to track the network topology by the partially measured distance matrix among the UAVs, which is known as the formation tracking problem. But the measured distances are generally sparse and noisy, and the topology of UAV network is changing continuously. These cause the formation tracking highly challenging. Existing methods are generally fragile to the measurement noises and network sparsity. This paper exploits a fact that well-connected subcomponents, whose local structures can be calculated reliably, exist widely because the unevenness of node distribution in sparse networks. Therefore, a weighted component stitching (WCS) method to find the reliable components and stitch their local structures with weights is proposed for calculating the formation of the network accurately. In particular, we propose efficient two-center four-vertex-connected star-graph (2-4-star) detection and merging algorithms to extract the reliable global rigid components. A WCS algorithm and a weighted component-based Kalman filter algorithm with complexity both O(n3) are proposed for robust formation tracking in n vertex UAV networks. Extensive experiments were conducted, showing that the proposed methods can improve the formation tracking accuracy 21%-48% over existing state-of-the-art methods, especially in sparse, noisy UAV networks under different parameter settings.

The sensors in wireless sensor network (WSN) are vulnerable to malicious attacks due to the transmission nature of wireless media. Secure and authenticated message delivery with low energy consumption is one of the major aims in WSN. The identity‐based key authentication scheme is more suitable for the WSN. In this paper, the Hierarchical Matrix Decomposition‐based Signcryption (HMDS) algorithm was proposed, which is a kind of identity‐based authentication scheme. In HMDS scheme, three‐layer architecture, base station (BS), cluster head, and intracluster, is employed to adapt to the common structure of WSN. As the key generation center (KGC), the BS adopts matrix decomposition to generate the identification information and public key for cluster head, which not only reduces the cost of calculation and storage but also avoids the collusion attack. Experiments show that the HMDS algorithm has more advantages over other algorithms and is very suitable for the large‐scale WSN.

Online multi-kernel learning is promising in the era of mobile computing, in which a combined classifier with multiple kernels are offline trained, and online adapts to personalized features for serving the end user precisely and smartly. The online adaptation is mainly carried out at the end-devices, which requires the adaptation algorithms to be light, efficient and accurate. Previous results focused mainly on efficiency. This paper proposes an novel online model adaptation framework for not only efficiency but also optimal online adaptation. At first, an online optimal incremental simplex tableau (IST)algorithm is proposed, which approaches the model adaption by linear programming and produces the optimized model update in each step when a personalized training data is collected.But keeping online optimal in each step is expensive and may cause over-fitting especially when the online data is noisy. A Fast-IST approach is therefore proposed, which measures the deviation between the training data and the current model. It schedules updating only when enough deviation is detected. The efficiency of each update is further enhanced by running IST only limited iterations, which bounds the computation complexity. Theoretical analysis and extensive evaluations show that Fast-IST saves computation cost greatly, while achieving speedy and accurate model adaptation.It provides better model adaptation speed and accuracy while using even lower computing cost than the state-of-the art.

Social networks allow rapid spread of ideas and innovations while the negative information can also propagate widely. When the cascades with different opinions reaching the same user, the cascade arriving first is the most likely to be taken by the user. Therefore, once misinformation or rumor is detected, a natural containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of the positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1 - 1/e- δ) by a classic greedy algorithm combined with Monte Carlo simulation with the running time of O(k3mn ln n/δ2), where n and m are the number of users and edges, respectively. Unfortunately, the Monte-Carlo-simulation-based methods are extremely time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized algorithm which runs in O(km ln n/δ2) expected time and provides a (1 - 1/e - δ)-approximation with a high probability. The experimentally results on both the real-world and synthetic social networks have shown that the proposed randomized rumor blocking algorithm is much more efficient than the state-of-the-art method and it is able to find the seed nodes which are effective in limiting the spread of rumor.

Influence maximization problem is to find a set of seeds in social networks such that the cascade influence is maximized. Traditional models assume that all nodes are willing to spread the influence once they are influenced, and they ignore the disparity between influence and profit of a product. In this paper, by considering the role that price plays in viral marketing, we propose price related (PR) frame that contains PR-I and PR-L models for classic independent cascade and linear threshold models, respectively, which is a pioneer work. Two pricing strategies are designed, one is binary pricing (BYC), in which the seeds are offered free samples. The other is panoramic pricing (PAP), in which the seeds are offered different discounts. Furthermore, we find that influence and profit are like two sides of the coin, high price hinders the influence propagation and to enlarge the influence some sacrifice on profit is inevitable. Based on this observation under PR frame, by adopting a parameter to denote the decision maker's preference toward influence and profit, we propose balanced influence and profit (BIP) maximization problem. We prove the NP-hardness of BIP maximization under PR-I and PR-L model. Unlike influence maximization, the BIP objective function is not monotone. Despite the nonmonotony, we show BIP objective function is submodular under certain conditions. Two unbudgeted greedy algorithms separately, named algorithm of BYC and algorithm of PAP are devised. We conduct extensive simulations on real world data sets, test the effectiveness of our proposed parameters, compare the algorithms' performances, and evaluate the superiority of our algorithms over existing ones.

Following the recent advances in drone technologies, various algorithmic optimization problems related to the effective operation of drones are drawing lots of attentions. This paper considers two interesting multiple-drone-assisted search-and-reconnaissance scenarios, in each of which, the trajectory optimization of multiple drones is of great significance to minimize the latency in the system. In the first scenario, multiple drones, whose moments of mobilization are not necessarily the same, are trying to urgently collect intelligence from a given point of interest, and we would like to minimize the task completion time, i.e., the time period between the moment that the first drone commences its operation to the moment that the intelligence from all of the points are collected, by optimizing their trajectories. In the second scenario, multiple drones with different speeds, are hovering around the same routes to regularly collect intelligence from highly geographically-diversified points of interest over an extended time period, and we would like to minimize the worst-case data refreshment rate, the largest time gap between two consecutive observations over the same point of interest. In this paper, we formally define each problem, prove its NP-hardness, and propose an approximation algorithm for it. We also conduct a simulation to study the performance of our result.

This paper proposes a new polynomial time constant factor approximation algorithm for a more-a-decade-long open NP-hard problem, the minimum four-connected m-dominating set problem in unit disk graph (UDG) with any positive integer m ≥ 1 for the first time in the literature. We observe that it is difficult to modify the existing constant factor approximation algorithm for the minimum three-connected m-dominating set problem to solve the minimum four-connected m-dominating set problem in UDG due to the structural limitation of Tutte decomposition, which is the main graph theory tool used by Wang et al. to design their algorithm. To resolve this issue, we first reinvent a new constant factor approximation algorithm for the minimum three-connected m-dominating set problem in UDG and later use this algorithm to design a new constant factor approximation algorithm for the minimum four-connected m-dominating set problem in UDG.

We wonder that in a competitive environment, how an influence uses the minimum cost to choose seeds such that its influence spread can reach a desired threshold under thwarting from its competitors. At first we take a simple fact into account: the information arriving first has heavy impact, and present Competitive — Independent Cascade (C-IC) model to characterize how different influences competing with others in a social network. We have found that a specific influence's spread is monotone and submodular, and these nice properties make algorithm performance tractable. We then propose Minimum Cost Seed Set problem (MinSeed) to answer our original concern and give a greedy algorithm. We analyze the ratio of greedy algorithm, and give result significantly better than similar ones analyzed by others. Noticing that the computation of real information spread is hard to compute and simple greedy is too time consuming, we design an effective method for estimating information spread in C-IC model, and devise scalable algorithm applying for large social networks. Through simulation on real world datasets, we confirm that, our scalable algorithm outputs seed set with small total cost comparable to that given by simple greedy, with very fast computation.

Binary proximity sensors (BPS) is a generic model for many non- collaborative, presence detecting sensor. It outputs "1'' when one or more targets are presenting in its sensing range and "0" otherwise. It cannot tell the number of targets nor the targets' identities in its sensing range. But for its privacy protection and device-free properties, BPS-based tracking has attracted great attentions. However, multiple target counting and tracking (MTCT) by BPS network remains very challenging. Existing approaches generally rely on trajectory decomposition, which suffer association complexity issue and can hardly provide accurate results. To address these challenges, this paper presents an novel intensity-based counting and tracking approach, called IntenCT, which tracks the evolvement of the multi-targets' probabilistic density distribution overtime, without the complexity of enumerating the multiple targets' trajectories. Then, clustering algorithms on the density distribution are proposed to find the target groups, and count the targets in each group by calculating the integral of the density distribution in the group region. At last, the trajectories of the separable targets in each group are estimated using K-means and a motion consistency model. Extensive analysis and simulations show that IntenCT has quadratic complexity which is very efficient; provides the current best known multi-target counting lower bound; and tracks the multi-targets more accurately than the existing approaches.

Radio-map based method has been widely used for indoor location and navigation, but remaining key challenges are: 1) laborious efforts to calibrate a fine-grained radio-map, and 2) the locating result inaccuracy and not robust problems due to random signal strength (RSS) noises. An efficient way to overcome these problems is to collect RSS signatures along indoor paths and utilize sequence matching to enhance the location robustness. But, due to problems of indoor path combinational explosion, random RSS loss during movement, and moving speed disparity during online and offline phases, how to exploit sequence matching in radio-map remains difficult. This paper proposes WarpMap, an efficient sequence-type radio-map model and an accurate indoor location method by dynamic warping. Its distinct features include: 1) an undirected graph model (Trace-graph) for efficiently calibrating and storing sequence-type radio-map, which overcomes the path combinational explosion and RSS miss-of-detection problems; 2) an efficient sub-sequence dynamic time warping (SDTW) algorithm for accurate and efficient on-line locating. We show SDTW can tolerate random RSS disparities at discrete points and handle the moving speed differences in on-line and offline phases. The impacts of different warping distance functions, RSS preprocessing techniques were also investigated. Extensive experiments in office environments verified the efficiency and accuracy of WarpMap, which can calibrated within ten minutes by one person for 1100m2 area and provides overall nearly 20% accuracy improvements than the state-of-the-art of radio-map method.

Many distributed systems use a client-server model in which client assignment strategy plays an important role on the system performance. People use two criteria to evaluate server loads-1) total load and 2) load balance. The total load increases when the load balance decreases, and vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design algorithms based on semidefinite programming. We study the identical server case and general server case, present two algorithms (BSP and ABSP), and analyze these algorithms' bounds. In simulation, we evaluate that our client assignement strategies give the satisfiable total load and load balancing using reasonable time compared to the state-of-the-art, thus proving the effectiveness of our algorithms.

Over years, virtual backbone has attracted lots of attention as a promising approach to deal with the broadcasting storm problem in wireless networks. Frequently, the problem of a quality virtual backbone is formulated as a variation of the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum k-connected m-dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph by Wang assumes k ≤ 3 and m ≥ 1, and its performance ratio is 280 when k = m = 3. In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for k ≤ 3 and m ≥ 1. In particular, the algorithm features with (a) a drastically simple structure and (b) a much smaller performance ratio, which is nearly 62 when k = m = 3. We also conduct simulation to evaluate the performance of our algorithm.

Wireless sensor network is an important part of the Internet of Things. Preservation of privacy and integrity in wireless sensor networks is extremely urgent and challenging. To address this problem, we propose PPKN, an efficient and privacy-preserving k-NN query protocol in two-tiered wireless sensor networks. Our proposal prevents adversaries from gaining sensitive information of both queries issued by users and data collected by sensor nodes while allows the sink to verify whether results are valid. It offers confidentiality of queries and data by constructing a special code, provides integrity verification by the correlation among data. Moreover, by the implementation of KNQ query framework, PPKN also achieves high efficient in query response and energy consumption. Finally, the theoretical analysis and experiment results show the high performance of PPKN in terms of privacy preservation and query efficiency.

Visual sensor networks (VSNs) can track multiple pedestrians and capture high-quality videos of the monitored area. Therefore, VSNs is ideal for providing good broadcast service. In sports broadcasting, a basic requirement for broadcasters is to report the significant events as quickly as possible when they take place. To meet this requirement, we propose the Camera Scheduling for selected area coverage problem (CamS). Considering that Pan-Tilt-Zoom (PTZ) camera sensor has the flexibility of configuring its angle of view in both horizontal and vertical dimensions, we apply PTZ camera sensors to solve CamS. A polynomial time optimal algorithm that schedules PTZ camera sensors elegantly is devised for CamS. We set many realistic application scenarios in simulation and thoroughly study how our algorithm's performance is affected by different environmental parameters, including angle velocity, the number of camera sensors and the number of sub-areas.

Over years, virtual backbone has attracted lots of attentions as a promising approach to deal with the broadcasting storm problem in wireless networks. One popular way to construct a quality virtual backbone is to solve the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum k-connected m-dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph assumes k ≤ 3 and m ≥ 1 and its performance ratio is 280 when k = m = 3. In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for k ≤ 3 and m ≥ 3. In particular, the algorithm features with much simpler structure and much smaller performance ratio, e.g. nearly 66 when k = m = 3. We also conduct simulation to evaluate the performance of our algorithm.

Underwater Wireless Sensor Networks (UWSNs) are vulnerable to attack because of the broadcast nature of the transmission. The sensor nodes in UWSN are highly constrained in terms of computational capabilities and communication bandwidth. Authentication schemes for ground WSNs might not be applicable for UWSNs due to their less computation and communication capacity. Thus, it is necessary to design special schemes tailored to underwater environments. In this paper, a low computational complexity authentication scheme is proposed. By using Vandermonde matrix, we replace the matrix multiplication by matrix addition to greatly reduce the computation overhead. Moreover, our scheme is self-correctable and irreversible which further enhances the security of the UWSNs. Experiment results indicate our algorithm has advantages in energy and time consumption over traditional RSA and Blom's scheme.

The aim of influence maximization problem is to find a k-size seed set that has the maximum influence. In previous works the modification of user's attitude is seldom paid attention to. However from the psychology research, we know that people's opinions are affected by their friends. Base on this, we present a new Linear Threshold model with Instant Opinions (LT-IO). We devise an attitude function Atuthat describes node u's attitude at time t, and the broadcast attitude which is the attitude when a node becomes active. To simulate information propagation in real world, we define a trust threshold η to justify whether a node follows or opposes the influence from its neighbor. We propose a heuristic algorithm IMLT-IOA to solve our problem, prove its submodularity and monotonicity and then obtain its approximation ratio which is (1 - 1/e). To the best of our knowledge, this is the first work that focuses on the influence maximization with user's attitude modification. To verify our IMLT-IOA algorithm, we conduct extensive experiments on a large data collection obtained from real social networks, the results show that IMLT-IOA reduces the running time and meanwhile keeps effectiveness comparing to other algorithms.

Wireless Sensor Network is an important part of the Internet of Things. Data privacy preservation in wireless sensor networks is extremely urgent and challenging. To address this problem, we propose in this paper a privacy-preserving data aggregation protocol in wireless sensor networks. Compared to the previous research, our protocol protects the actual data from other nodes based on a rotation scheme while reducing communication overhead dramatically. The protocol achieves accurate aggregation results. Finally, theoretical analysis and simulation results confirm the high privacy and efficiency of our proposal.

A wireless sensor network is said to form a belt-barrier for a region if it is able to detect any object moving from outside the region to inside. Recently, Cheng and Tsai found if camera sensors are used to form a belt-barrier, the breadth of the barrier becomes an important quality factor to ensure high quality of monitoring (QoM). Then, they proposed the minimum β-breadth belt-barrier construction problem ((β,1)-B3CP) whose goal is to select a minimum number of camera sensors to form a β-breadth belt-barrier, which ensures the width of the picture of any object which moves through the barrier is at least β. In this paper, we perform more thorough investigation of the problem and introduce a new polynomial time exact algorithm for the problem under the assumption that the angle of each camera is fixed. Our simulation result shows our algorithm outperforms Cheng and Tsai's algorithm. We also introduce a variation of (β, 1)-B3CP, namely (β, k)-B3CP, which aims to construct k node-disjoint β-breadth belt-barrier for fault-tolerance purpose, propose a new heuristic algorithm for it, and conduct simulations to evaluate its performance.

This paper investigates two new groups of trajectory optimization problems which stem from networked multi-robotic systems. In particular, we study how to efficiently collect data from stationary sensor nodes using multiple robotic vehicles such as data ferries under different circumstance. The first group includes two new problems which aim to find the tours and the paths, respectively, of k robot vehicles with different mobilization conditions to collect data from ground sensor nodes with minimum latency. The second group consists of one new problem whose goal is to determine the quality tours of k robot vehicles with different speeds, where each of which follows its corresponding tour to repeatedly collect data from stationary sensors. We prove the three problems are NP-hard and propose constant factor approximation strategies for them. Through a simulation, an analytical study is conducted to evaluate the average performance of our core contribution.

Effectiveness of MapReduce as a big data processing framework depends on efficiencies of scale for both map and reduce phases. While most map tasks are preemptive and parallelizable, the reduce tasks typically are not easily decomposed and often become a bottleneck due to constraints of data locality and task complexity. By assuming that reduce tasks are non-parallelizable, we study offline scheduling of minimizing makespan and minimizing total completion time, respectively. Both preemptive and non-preemptive reduce tasks are considered. On makespan minimization, for preemptive version we design an algorithm and prove its optimality, for non-preemptive version we design an approximation algorithm with the worst ratio of 3/2-1/2h where h is the number of machines. On total complete time minimization, for non-preemptive version we devise an approximation algorithm with worst case ratio of 2-1/h, and for preemptive version we devise a heuristic. We confirm that our algorithms outperform state-of-art schedulers through experiments.

One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

Wireless sensor network is an important part of the Internet of Things. Preservation of privacy and integrity in wireless sensor networks is extremely urgent and challenging. To address this problem, we propose in this paper an efficient and secure range query protocol in two-tiered wireless sensor networks introducing master nodes. Our proposal not only prevents adversaries from gaining sensitive information of both queries issued by users and data collected by sensor nodes but also allows the sink to verify whether results are valid. It offers confidentiality of queries and data by constructing a special code, provides integrity verification by the correlation among data and also enables efficient query processing. Finally, theoretical analysis and simulation results confirm the security and efficiency of our proposal.

We study competitive influence propagation in social networks based on Independent Cascade (IC) model. First we propose two new models, in both of which each individual in the network is allowed to propagate multiple influences to its neighbors. In the first Deadline Independent Cascade (DIC) model, each individual has a deadline of following the final single influence and before that it may accept different influences. In the second Latency Independent Cascade (LIC) model, once an individual firstly receives any influence, it has a latency to make the final decision and in the latency it continues receiving influences. Second we analyze the combinatorial properties of our proposed models. We prove that the influence spread under DIC model is monotone and sub modular, which implies that the last influence source has a strategy that returns at least 1 -- 1/e of the best response. We also give examples showing that the influence spread under LIC model is neither monotone nor sub modular, which implies that even for the last influence source, it is hard to find the strategy with guaranteed performance.

Mobile phones with a rich set of embedded sensors have been applied in various collaborative sensing applications. In some applications, to encourage mobile phone users performing collaborative sensing tasks, the data demanders may pay mobile phone users. However, none of the existing works takes into account it. In this paper, we study the Minimum Cost of Attaining the Required Data with mobile phones (MCARD) problem in collaborative sensing network. Given sensing regions R = {R1, R2, ..., Rm}, the set of requisite data Difor each sensing region Riand a set of mobile phones M, the MCARD problem is how to select mobile phones to get all the required data such that the total cost on paying mobile phone users is minimized. We first formally define the MCARD problem. Then, we propose an approximation algorithm for the MCARD problem with the determinate trajectories of mobile phones and a heuristic algorithm for that trajectories are unknown respectively. Simulation results demonstrate our algorithms are efficient.

This paper introduces two new coverage problems in mission-driven camera sensor networks, namely the target temporal effective-sensing coverage with non-adjustable cameras (TEC-NC) problem and the target-temporal effective-sensing coverage with adjustable cameras (TEC-AC) problem. Given a mission period, the objective of the problems is to find a sleep-wakeup schedule of the camera sensor nodes such that the overall target-temporal coverage is maximized. We formally introduce a method called Identifiability Test to check if a target with a face direction is effectively-covered by a camera sensor, and prove the problems are NP-hard. For TEC-NC, we propose a 2-approximation algorithm and two heuristic algorithms. We also design a greedy strategy which can be combined with our solutions for TEC-NC to solve TEC-AC. The simulation results indicate the quality of the outputs of our algorithms are much better than that of the existing alternative as well as close to the theoretical optimum on average.

Influence maximization problem is to find a set of seeds in social networks such that the cascade influence is maximized. Traditional models assume all nodes are willing to spread the influence once they are influenced, and they ignore the disparity between influence and profit of a product. In this paper by considering the role that price plays in viral marketing, we propose price related (PR) frame that contains PR-I and PR-L models for classic IC and LT models respectively, which is a pioneer work. We find that influence and profit are like two sides of the coin, high price hinders the influence propagation and to enlarge the influence some sacrifice on profit is inevitable. We propose Balanced Influence and Profit (BIP) maximization problem. We prove the NP-hardness of BIP maximization under PR-I and PR-L model. Unlike influence maximization, the BIP objective function is not monotone. Despite the non-monotony, we show BIP objective function is sub modular under certain conditions. Two unbudgeted greedy algorithms separately are devised. We conduct simulations on real-world datasets and evaluate the superiority of our algorithms over existing ones.

Given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r ln n) where r is the link radius of the sensor network and n is the number of sensors. In this paper, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1 - ε, producing an approximation solution with performance ratio O(log3n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

Online Social Networks (OSNs) have recently emerged as an effective medium for information sharing. Unfortunately, it has been frequently observed that malicious rumors being spread over an OSN are not controllable, and this is not desirable. This paper proposes a new problem, namely the γ - k rumor restriction problem, whose goal is, given a social network, to find a set S of nodes with k protectors (γ * k protectors from the contaminated set, and (1 - γ) * k protectors from the decontaminated set) to protect the network such that the number of decontaminated nodes is maximum. We show that the objective function of the γ - k rumor restriction problem is submodular, and use this result to design a greedy approximation algorithm with performance ratio of 1 - 1/e for the problem under the linear threshold model and independent cascade model, respectively. To verify our algorithms, we conduct experiments on real word social networks including NetHEPT, WikiVote and Slashdot0811. The results show that our algorithm works efficiently and effectively.

Inspired by the backbone concept in wired networks, virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). Virtual backbone construction based on Connected Dominating Set (CDS) is a competitive approach among the existing methods used to establish virtual backbone in WSNs. Traditionally, CDS size was the only factor considered in the CDS-based approach. The motivation was that smaller CDS leads to simplified network maintenance. However, routing cost in terms of routing path length is also an important factor for virtual backbone construction. In our research, both of these two factors are taken into account. Specifically, we attempt to devise a polynomial-time constant-approximation algorithm that leads to a CDS with bounded CDS size and guaranteed routing cost. We prove that, under general graph model, there is no polynomial-time constant-approximation algorithm unless P = NP. Under Unit Disk Graph (UDG) model, we propose an innovative polynomial-time constant-approximation algorithm, GOC-MCDS-C, that produces a CDS D whose size I D is within a constant factor from that of the minimum CDS. In addition, for each node pair u and v, there exists a routing path with all intermediate nodes in D and path length at most 7 · d(u, v), where d(u, v) is the length of the shortest path between u and v. Our theoretical analysis and simulation results show that the distributed version of the proposed algorithm, GOC-MCDS-D, outperforms the existing approaches.

This paper identifies a new security problem of existing scheduling algorithms for barrier-coverage of sensors, which never considered before. A barrier-cover of wireless sensors is a subset of sensors seamlessly spanning between two opposite sides such that no intruder can move from one side to the other without being detected. The goal of the scheduling algorithms is to find a sleep-wakeup schedule of sensors such that the time to protect an area of interest using a series of alternating barrier-covers can be maximized. We introduce a new security problem which may exist when two barrier-covers, whose covered areas are not completely disjoint, alternate. We show how an intruder can utilize a set of points, namely “barrier-breaches”, to penetrate the alternating barrier-covers. We also propose two remedies for this problem for existing scheduling algorithms. Our analysis shows that depending on the input graph, one of our approaches works better than the other. Given that such scheduling algorithms only need to run during the initialization phase of a sensor network, we suggest to apply both approaches and pick the better schedule rather than relying solely on the approach which works well on average.

Recently, geometric routing has emerged as an efficient routing strategy on wireless networks. An ideal geometric routing is memoryless and does not suffer from the drawbacks of traditional proactive/reactive routings. All existing geometric routings on 3-D wireless networks either work deterministically only on the networks with special properties or do not guarantee delivery. In this paper, we divide the memoryless requirement into two sub-requirements, node-memoryless-ness and message-memoryless-ness. Then, we propose a new node-memoryless geometric routing, which is still free from the drawbacks of traditional routings. Our algorithm partitions the 3-D space with regular cubes and converts the routing problem over nodes into a routing problem over cubes. With minimal information attached to the header of a message, our algorithm deterministically delivers a message to its destination in any connected 3-D wireless networks. The forwarding decision on the message is made in a completely localized manner. The simulation results indicate that our algorithm outperforms its competitors on average.

The broadcast is a fundamental operation in computer and communication networks. We study broadcast in multiradio multichannel multi-hop wireless networks. Suppose through configuration, each node is already assigned with a transmission power level and a set of radio channels for receiving and forwarding data. Our problem is to select a forward scheme for broadcasting from a given source node and to minimize total energy consumption. This is a known NP-hard minimization problem. In this paper, we construct a polynomial-time (1.35 + ϵ)(1+ln(n-1))-approximation algorithm where n is the number of nodes in given network and ϵ is any positive constant. We also show that there is no polynomial-time (ρ ln n)-approximation for 0O(log log n)).

Barrier coverage is an important issue in wireless sensor network. In wireless camera sensor networks, the cameras take the images or videos of target objects, the position and angle of camera sensor impact on the sense range. Therefore, the barrier coverage problem in camera sensor network is different from scalar sensor network. In this paper, based on the definition of full-view coverage, we focus on the Minimum Camera Barrier Coverage Problem (MCBCP) in wireless camera sensor networks in which the camera sensors are deployed randomly in a target field. Firstly, we partition the target field into disjoint subregions which are full-view-covered regions or not-full-view-covered regions. Then we model the full-view-covered regions and their relationship as a weighted directed graph. Based on the graph, we propose an algorithm to find a feasible solution for the MCBCP problem. We also proved the correctness of the solution for the MCBCP problem. Furthermore, we propose an optimal algorithm for the MCBCP problem. Finally, simulation results demonstrate that our algorithm outperforms the existing algorithm.

In this paper, we studied the minimum latency conflict-free many-to-one data aggregation scheduling problem in multi-channel multi-hop wireless sensor networks: Given locations of all sensors and a base station, some sensors which are called as sources, find a schedule such that data from all sources can be transmitted to the base station without any conflict and the latency is minimized. In this model, each sensor has three parameters which are transmission range r, interference range ar and carrier sensing range βr where α, and β are constant. There are λ ≥ 1 available channels for communications. We designed an approximation algorithm with ratio (⌈a/λ⌉ + 11 ⌈b/λ⌉) This work improves our previous work when λ = 1. Extensive simulations valuate the performance of the algorithm.

In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size |D| is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

Numerous algorithms on geometric networks has been studied, and most of them were based on 2-dimensional networks. But 2-dimensional geometric routing algorithms cannot be directly adapted to the 3-dimensional networks. In this paper, we propose routing algorithms based on the iteration of specific angles on the networks of Delaunay Triangulation in 3D space, and prove the certainty of data transmission of our routing algorithms. In the algorithms, the messages only need to carry information of O(1) nodes and each node just keeps 1-hop neighbors' information.

In this paper, we study a novel coverage problem where each target has differentiated coverage quality requirement in directional sensor network. Since extending network lifetime is a very important issue in directional sensor network, we address the Maximal Network Lifetime Scheduling Problem (MNLS) which organizes the directions of sensors into a group of non-disjoint cover sets. One cover set which can cover all the targets satisfying their coverage quality requirement is activated at one time. Firstly, we prove the MNLS problem is NP-Hard and get an upper bound of the optimal solution for the problem. Secondly, we formulate the problem as an exact Integer Programming. Then we propose two efficient heuristic algorithms (MNLS-H and MNLS-H-T) for the problem. Finally, Extensive experiments have been conducted to demonstrate the performance of these algorithms through comparing the two heuristics with the upper bound.

Traffic congestion is a very serious problem in large cities. With the number of vehicles increasing rapidly, especially in cities whose economy is booming, the situation is getting even worse. In this paper, by leveraging the techniques of Vehicular Ad hoc Networks (VANETs) we present a dynamic navigation protocol called VAN for individual vehicles to find the shortest-time paths toward their given destinations. Specifically, a vehicle initiates a number of queries, which are routed by VANETs along different paths toward its destination. During query forwarding, the real-time road traffic information in each road segment is aggregated from multiple participating vehicles and returned to the source after the query reaches the destination. This information enables the source to calculate the shortest-time path. We also propose two forwarding optimization methods to reduce communication costs and an error handling mechanism to deal with abnormal circumstances. To evaluate its performance, we use the real traffic data of Beijing, including 2,308 road segments at two different times. Our simulation results demonstrate that our protocol, on average, could save around 30% driving time, compared to traveling along the shortest distance paths.

Service-oriented wireless sensor networks have recently been proposed to provide an integrated platform, where new applications can be rapidly developed through flexible service composition. In wireless sensor networks, sensors are periodically switched into the sleep mode for energy saving. This, however, will cause the unavailability of nodes, which, in turn, incurs disruptions to the service compositions requested by the applications. Thus, it is desirable to maintain enough active sensors in the system to provide each required service at any time in order to achieve dependable service compositions for various applications. In this paper, we study the cross-layer sleep scheduling design, which aims to prolong the network lifetime while satisfying the service availability requirement at the application layer. We formally define the problem, prove that the problem is NP-hard, and develop two approximation algorithms based on the LP relaxation and one efficient reordering heuristic algorithm. The proposed work will enhance the dependability of the service composition in service-oriented wireless sensor networks.

Broadcasting/Multicasting problems have been well studied in wireless ad hoc networks. However, only a few approaches take into account the low interference and energy efficiency as the optimization objective simultaneously. In this paper, we study the interference and power constrained broadcast/multicast and the delay-bounded interference and power constrained broadcast/multicast routing problems in wireless ad hoc networks using directional antennas. We propose an approximation and a heuristic algorithm for the two problems, respectively. Importantly, motivated by the study of above optimization problems, we propose approximation schemes for two multi-constrained directed Steiner tree problems, respectively. Broadcast/Multicast message by using the trees found by our algorithms tend to have less channel collisions and higher network throughput. The theoretical results are corroborated by simulation studies.

In this paper, we consider the problem of topology control by joint power control and routing to maximize the network throughput in wireless mesh networks. First, we present two mathematical formulations of the joint power control and routing problem according to two different definitions of network throughput: the total throughput and the minimal per-node throughput. To reduce the computation cost, we next decompose this joint problem into two sub-problems: the power control sub-problem and the routing sub-problem. For the first sub-problem, we design two heuristic algorithms to assign transmission powers to mesh routers, such that the total interference or the maximum node interference in the network is minimized. For the routing sub-problem, we design two linear programming formulations to maximize the total throughput or the minimal per-node throughput. Simulation results reveal the following relationship: the topology with minimum total interference has higher total throughput, while the topology with minimum maximal node interference has higher minimal per-node throughput. This can server as a guidance for network design to satisfy different throughput considerations.

This paper considers the problem of constructing data gathering trees in a wireless sensor network for a group of sensor nodes to send collected information to a single sink node. Sensors form application-directed groups and the sink node communicates with the group members, called source nodes, to gather the desired data using a multicast tree rooted at the sink node. The data gathering tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data gathering tree is to minimize the number of non-source nodes to be included in the tree so as to save energies of as many non-source nodes as possible. It can be shown that the optimization problem is NP-hard. We first propose an approximation algorithm with a performance ratio of four, and then give a distributed algorithm corresponding to the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithm. The results show that the proposed algorithm can find a tree of a good approximation to the optimal tree and has a high degree of scalability.

This paper investigates the optimal replication of data objects at hierarchical and transparent Web proxies. By transparent, we mean the proxies are capable of intercepting users' requests and forwarding the requests to a higher level proxy if the requested data are not present in their local cache. Two cases of data replication at proxies are studied: 1) proxies having unlimited storage capacities and 2) proxies having limited storage capacities. For the former case, an efficient algorithm for computing the optimal result is proposed. For the latter case, we prove the problem is NP-hard, and propose two heuristic algorithms. Extensive simulations have been conducted and the simulation results have demonstrated significant performance gain by using the proposed data replication algorithms and also shown the proposed algorithms out-perform the standard Web caching algorithm (LRU threshold method).

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network and a multicast request, to find a multicast tree such that the total energy cost of the multicast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove the problem is NP-hard, and then propose three heuristic algorithms, namely Steiner tree based heuristic, node-join-tree and tree-join-tree greedy algorithms. Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.

This work discusses the energy efficient QoS topology control problem in ad hoc wireless networks. Given a set of nodes in a plane, end-to-end traffic demands and delay bounds between node pairs, the problem is to find a network topology that can meet the QoS requirements and the maximum transmitting power of nodes is minimized. We consider two cases of the problem: 1) the traffic demands are not splittable, and 2) the traffic demands are splittable. For the former case, the problem is formulated as an integer linear programming problem. For the latter case, the problem is formulated as a mixed integer programming problem, and an optimal algorithm has been proposed to solve the problem.

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, to find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard, and propose three heuristic algorithms, namely shortest path tree heuristic, greedy heuristic and node weighted Steiner tree based heuristic. The approximation ratio of the set-cover based heuristic is proved to be (1+2ln(n-1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.

This paper investigates the optimal placement of proxies of a Web server on the Internet, with the consideration of both read and update operations to the data on the Web server. We first study the problem of optimal placement of $k$ proxies in a system to minimize the total access cost to the Web server. Then, for an unknown number of proxies, we find the optimal number of proxies required in the system. The problems are formulated by using the dynamic programming method and the optimal solutions are obtained. Simulations have been conducted to evaluate the performance of the proposed algorithms and to demonstrate how the effectiveness of proxy placement is affected by various factors, such as network traffic load, number of proxies, read–write ratio and proxy hit ratio.

Abstract A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum‐connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum‐connected dominating set in unit‐disk graphs. In this paper, we design a (1 + 1/s)‐approximation for the minimum‐connected dominating set in unit‐disk graphs, running in timenO((slogs)2). © 2003 Wiley Periodicals, Inc.

We consider the traffic grooming problem on general topology WDM networks. The problem is: given a set of t connections and their routes, and the grooming factor g, to find an optimal wavelength assignment and grooming such that the number of wavelengths required in the network is minimized. We first formulate this problem as an integer linear programming problem, and then propose a heuristics method to solve it. Our simulation results show that an increase of the grooming factor can considerably decrease the number of wavelengths required in the system.

An important goal of the design of WDM (wavelength division multiplexing) networks is to use less wavelengths to serve more communication needs. According to the wavelength conflict rule, we know that the number of wavelengths required in a WDM network is at least equal to the maximal number of channels over a fiber (called maximal link load) in the network. By placing wavelength converters at some nodes in the network, the number of wavelengths needed can be made equal to the maximal link load. In this paper we study the problem of placing the minimal number of converters in a network to achieve that the number of wavelengths in use is equal to the maximal link load. For duplex communication channels, we prove that an optimal solution can be obtained in polynomial-time. For unidirectional communication channels, which was proved to be NP-complete, we develop a set of lemmas which lead to an efficient approximation algorithm whose approximation ratio is two.

This paper investigates the optimal placement of proxies of a Web server on the Internet. With the consideration of both read and write operations to the data on the Web server. First, we study the problem of optimal placement of k proxies in a system to minimize the total access cost to the Web server. Then, for unknown number of proxies, we find the optimal number of proxies required in the system. The problems are formulated using a dynamic programming method and optimal solutions are obtained. Intensive simulations have been conducted to evaluate the performance of the proposed algorithms, and to demonstrate the relationship between the number of proxies required in the system and the read-write ratio. This work can significantly alleviate the Web access traffic on the Internet and improve the performance of the Web server.

This paper investigates the issues of the optimal placement of a limited number of Web proxies in an environment where a Web site is replicated (i.e. mirrored Web sites). Two different objectives are studied: minimizing the overall access cost by all clients to the Web site and minimizing the longest delay for any client to access the Web site. The problem is reduced to the placement of proxies in a set of trees whose root nodes are the server replicas. It is then formulated and solved by using a dynamic programming method. The significance of this work includes: (1) alleviating the Internet traffic of Web accesses; (2) improving the response time of Web page accesses; (3) maximizing Web server performance by using a limited number of proxies.

Given a WDM optical network with wavelength channels on its fiber links, we consider the problem of finding the minimum set of network nodes such that, with wavelength converters at these nodes, broadcast can be supported in the network. We call this problem the converter placement problem. We model a given network using a graph G with colors on its edges and give a mathematical formulation for the problem based on the graph model. Two related problems, color-covering and vertex color-covering, are given and analyzed. Both of them are shown to have a polynomial-time approximation with performance ratio ln n+1 and ln n is the best possible performance ratio unless NP /spl sub/ DTIME(n/sup poly log n/), where n is the number of vertices in G. Using these results, we show that the Converter Placement problem has a polynomial-time approximation with performance ratio 2(ln n+1) and 1/2 ln n is the best possible performance ratio unless NP /spl sub/ DTIME(n/sup poly log n/). We present an approximation algorithm to solve the converter placement problem and study the performance of the algorithm on randomly generated network topologies.

In multihop systems of wavelength division multiplexing (WDM) networks, wavelength conversion is required at the conjunction of two lightpaths if they use different wavelengths. We consider the problem of assigning wavelengths to the lightpaths by using a limited number of wavelengths, so that the overall number of wavelength conversions in the whole system is minimal. The problem is formulated as a maximum clique cover problem. An approximation algorithm is proposed to solve it. Our proposed theory also illustrates the tradeoff relationship between the number of wavelengths and the number of conversions in the system.

Investigates the issues of placing a limited number of Web proxies in an environment where the Web server is replicated (i.e. mirrored Web servers). Two different objectives are considered: (a) minimizing the overall access cost by all clients of the Web server, and (b) minimizing the longest delay for any client to access the Web server. The problems are formulated and solved by using a dynamic programming method. This work can: (1) alleviate the amount of Internet traffic incurred by fast-growing Web accesses; (2) improve the response time of Web server accesses; and (3) maximize Web server performance by using a limited number of proxies.

In a WDM network under multihop architecture, each link is associated with a set of wavelengths available for channel connections, and in the network, the number of wavelengths that can be used is limited. Data transmission over one wavelength to another requires wavelength conversion, which causes a long delay. Given a multicast connection, routing is to construct a tree for the connection that is rooted from the source and connects all destinations. In this paper, we consider the problem of constructing a routing tree with a minimal number of wavelengths on the tree. We first prove that this problem is NP-hard and then propose an approximation algorithm, which produces a routing tree that has not only a small number of wavelengths but also a short delay from the source to all destinations. © 2000 John Wiley & Sons, Inc.