The last two decades have witnessed the rapid growth of heterogeneous Internet-connected devices in smart homes, which have increasingly become a critical component of the overall Internet ecosystem. However, the diverse nature of these devices with weak security management presents substantial challenges in security and privacy. Many smart home devices fall victim to compromise, subsequently becoming part of botnets exploited by malicious attackers to launch cyberattacks towards other victims. In this paper, we characterize the remote hosts and domains the smart home devices have been communicating with, and more importantly detect if and when these devices communicate with known malicious hosts and domains. Furthermore, we design, implement, and deploy a malicious DNS query blocker system based on the efficient Bloom filter data structure to filter and block outgoing network traffic toward these known malicious hosts and domains, thereby improving the security of smart home networks and the connected devices.

The last few years have witnessed the power of online social media platforms for detecting the outbreaks of the global coronavirus pandemic. However, the explosive and endless data streams in social media have created significant computational challenges for resource-constrained researchers to mine valuable social media data-sets for research discovery. In this paper, we study how to explore sampled and small-scale data streams from social media platforms for effective pandemic surveillance and monitoring. Specifically, we introduce a systematic approach to detect and monitor global pandemics with real-time but sampled Twitter data streams with a combination of document clustering, natural language processing, and Bloom filter. Our approach first uses document clustering to identify coherent tweet clusters from sampled tweets with the same topics and similar contents, and subsequently applies natural language processing to extract the most important and common terms from each cluster. Finally, we design sliding Bloom filters to discover novel terms which potentially capture the underlying emerging events, e.g., early waring signs of global pandemics. Based on real sampled Twitter data streams, we have demonstrated our proposed method is able to effectively detect the early signs of the omicron variant wave of the coronavirus and to provide critical insights on the growth trends and social sentiment during its rapid rise to the dominant coronavirus variant.

Smart homes with various Internet of Things (IoT) devices generate a large amount of network traffic carrying rich information and play an important role in our lives. However, there is a lack of educational material with real case studies to teach undergraduate students smart home security. In this poster paper, we present a holistic curriculum design consisting of five components teaching conceptual understanding of smart home vulnerabilities, capturing and interpreting network traffic for normal and abnormal behaviors of home users and smart devices, and writing reports on smart home security analysis and defense recommendations. A case study on a known vulnerability of Ring doorbell which reveals the password of the smart home Wi-Fi during the initial setup stage is illustrated with the network topology and the captured http traffic. The project is at its initial stage of development by students in a cybersecurity concentration at a primarily undergraduate institution. Students have started collecting and analyzing smart home traffic as a project in the Wireless Network and Security class or through supervised individual undergraduate research studies.

The technology advance and convergence of cyber physical systems, smart sensors, short-range wireless communications, cloud computing, and smartphone apps have driven the proliferation of Internet of things (IoT) devices in smart homes and smart industry. In light of the high heterogeneity of IoT system, the prevalence of system vulnerabilities in IoT devices and applications, and the broad attack surface across the entire IoT protocol stack, a fundamental and urgent research problem of IoT security is how to effectively collect, analyze, extract, model, and visualize the massive network traffic of IoT devices for understanding what is happening to IoT devices. Towards this end, this paper develops and demonstrates an end-to-end system with three key components, i.e., the IoT network traffic monitoring system via programmable home routers, the backend IoT traffic behavior analysis system in the cloud, and the frontend IoT visualization system via smartphone apps, for monitoring, analyzing and virtualizing network traffic behavior of heterogeneous IoT devices in smart homes. The main contributions of this demonstration paper is to present a novel system with an end-to-end process of collecting, analyzing and visualizing IoT network traffic in smart homes.

The ubiquitous deployment of IoT devices in smart homes has led to growing research interests in studying the home network traffic for various applications such as network measurements, device profiling, and IoT device event inference. Recent studies have shown that user activities can be inferred from a home network using extracted device event logs. However, existing solutions for user activity inference such as IoTMosaic and$\text{E2AP}$have limitations when handling ambiguities caused by device malfunctions. In this paper, we first identify the challenges faced by the existing user activity inference algorithms and the root causes of their poor performances on certain types of inputs. We then show that useful information can still be obtained even in situations where device malfunctions introduce ambiguities in user activity patterns. We achieve so by designing an extension to the existing algorithms. We also apply our extension in a digital forensics application. Our extensive experimental evaluations demonstrate that our solutions can effectively provide insights to user activity inference despite the presence of indistinguishable user activity patterns.

Recent advances in cyber-physical systems, artificial intelligence, and cloud computing have driven the wide deployment of Internet-of-things (IoT) in smart homes. As IoT devices often directly interact with the users and environments, this paper studies if and how we could explore the collective insights from multiple heterogeneous IoT devices to infer user activities for home safety monitoring and assisted living. Specifically, we develop a new system, namely IoTMosaic, to first profile diverse user activities with distinct IoT device event sequences, which are extracted from smart home network traffic based on their TCP/IP data packet signatures. Given the challenges of missing and out-of-order IoT device events due to device malfunctions or varying network and system latencies, IoTMosaic further develops simple yet effective approximate matching algorithms to identify user activities from real-world IoT network traffic. Our experimental results on thousands of user activities in the smart home environment over two months show that our proposed algorithms can infer different user activities from IoT network traffic in smart homes with the overall accuracy, precision, and recall of 0.99, 0.99, and 1.00, respectively.

The rapid and ubiquitous deployment of Internet of Things (IoT) in smart homes has created unprecedented opportunities to automatically extract environmental knowledge, awareness, and intelligence. Many existing studies have adopted either machine learning approaches or deterministic approaches to infer IoT device events and/or user activities from network traffic in smart homes. In this paper, we study the problem of inferring user activity patterns from a sequence of device events by first deterministically extracting a small number of representative user activity patterns from the sequence of device events, then applying unsupervised learning to compute an optimal subset of these user activity patterns to infer user activity patterns. Based on extensive experiments with sequences of device events triggered by 2,959 real user activities and up to 30,000 synthetic user activities, we demonstrate that our scheme is resilient to device malfunctions and transient failures/delays, and outperforms the state-of-the-art solution.

The recent spate of cyber attacks towards Internet of Things (IoT) devices in smart homes calls for effective techniques to understand, characterize, and unveil IoT device activities. In this paper, we present a new system, named IoTAthena, to unveil IoT device activities from raw network traffic consisting of timestamped IP packets. IoTAthena characterizes each IoT device activity using an activity signature consisting of an ordered sequence of IP packets with inter-packet time intervals. IoTAthena has two novel polynomial time algorithms,sigMatchandactExtract. For any given signature,sigMatchcan capture all matches of the signature in the raw network traffic. UsingsigMatchas a subfunction,actExtractcan accurately unveil the sequence of various IoT device activities from the raw network traffic. Using the network traffic of heterogeneous IoT devices collected at the router of a real-world smart home testbed and a public IoT dataset, we demonstrate that IoTAthena is able to characterize and generate activity signatures of IoT device activities and accurately unveil the sequence of IoT device activities from raw network traffic.

The wide deployment of IoT systems in smart homes has changed the landscape of networked systems, Internet traffic, and data communications in residential broadband networks as well as the Internet at large. However, recent spates of cyber attacks and threats towards IoT systems in smart homes have revealed prevalent vulnerabilities and risks of IoT systems ranging from data link layer protocols to application services. To address the security challenges of IoT systems in smart homes, this paper introduces IoTArgos, a multi-layer security monitoring system, which collects, analyzes, and characterizes data communications of heterogeneous IoT devices via programmable home routers. More importantly, this system extracts a variety of multi-layer data communication features and develops supervised learning methods for classifying intrusion activities at system, network, and application layers. In light of the potential zero-day or unknown attacks, IoTArgos also incorporates unsupervised learning algorithms to discover unusual or suspicious behaviors towards smart home IoT systems. Our extensive experimental evaluations have demonstrated that IoTArgos is able to detect anomalous activities targeting IoT devices in smart homes with a precision of 0.9876 and a recall of 0.9763.

The recent spate of cyber attacks and security threats toward Internet-of-Things (IoT) systems in smart cities, smart homes, and industry 4.0 calls for effective techniques to understand if, when, who, what IoT systems are exploited and compromised by Internet attackers. Toward this end, this article attempts to study DNS behavioral patterns of IoT systems in edge networks as a first step of characterizing their communication patterns and their interactions with IoT users, cloud servers, and other IoT or non-IoT devices in the same edge networks. Specifically, we analyze the temporal-spatial patterns of DNS behaviors of a variety of IoT systems in two dozens of edge networks and develop a simple yet effective Bloom filter mechanism for detecting anomalous traffic patterns based on unusual DNS queries and answers. To the best of our knowledge, this article is the first effort to systematically measure and monitor IoT network traffic from a DNS perspective for providing the security of heterogeneous IoT systems and ensuring IoT user privacy.

The last decade has witnessed the explosive growth of online social media in users and contents. Due to the unprecedented scale and the cascading power of the underlying social networks, social media has created a new paradigm for sharing information, broadcasting breaking news, and reporting real-time events by any user from anywhere at any time. Many popular social media sites including Twitter provide streaming data services by standard APIs to the broad researcher and developer communities. Given the sheer data volume, rapid velocity, and feature variety of online social media, these sites often supply only a sampled set of streaming data, rather than the full data set to reduce the resource cost of computations, storage, and network bandwidth. In light of the substantial impact of sampling in Twitter data stream, this article explores a combination of spectral clustering, locality-sensitive hashing (LSH), latent Dirichlet allocation (LDA) topic modeling, and differential equation modeling to mitigate the impact of sampling on social media data analysis, in particular on detecting real-world events and predicting information diffusion. Our extensive experiments demonstrate that our proposed method is able to detect effectively the real-time emerging events and predict accurately the cascading pattern of these events from the 1% sampled Twitter data stream. To the best of our knowledge, this article is the first effort to introduce a systematic methodology to study and mitigate the impact of data sampling on social media analysis and mining.

Social media embed rich but noisy signals of physical locations of their users. Accurately inferring a user's location can significantly improve the user's experience on the social media and enable the development of new location-based applications. This paper proposes a novel community-based approach for predicting the location of a user by using communities in the egonet of the user. We further propose both geographical proximity and structural proximity metrics to profile communities in the ego-net of a user, and then evaluate the effectiveness of each individual metric on real social media data. We discover that geographical proximity metrics, such as average/median haversine distance and community closeness, are strong indicators of a good community for geotagging. In addition, structural proximity metric conductance performs comparable to geographical proximity metrics while triangle participation ratio and internal density are weak location indicators. To the best of our knowledge, this is the first effort to infer the physical location of a user from the perspective of latent communities in the user's ego-net.

The last decade has witnessed research advances and wide deployment of Internet-of-things (IoT) in smart homes and connected industry. However, the recent spate of cyber attacks exploiting the vulnerabilities and insufficient security management of IoT devices have created serious challenges for securing IoT devices and applications. As a first step towards understanding and mitigating diverse security threats of IoT devices, this paper develops a measurement framework to automatically collect network traffic of IoT devices in edge networks, and build multidimensional behavioral profiles of these devices which characterize who, when, what, and why on the behavioral patterns of IoT devices based on continuously collected traffic data. To the best of our knowledge, this paper is the first effort to shed light on the IP-spatial, temporal, and cloud service patterns of IoT devices in edge networks, and to explore these multidimensional behavioral fingerprints for IoT device classification, anomaly traffic detection, and network security monitoring for millions of vulnerable and resource-constrained IoT devices on the Internet.

Understanding the community structure of social media is critical due to its broad applications such as friend recommendations, user modeling, and content personalization. Existing research uses structural metrics such as modularity and conductance and functional metrics such as ground truth to measure the quality of the communities discovered by various community detection algorithms, while overlooking a natural and important dimension, community size. Recently, the anthropologist Dunbar suggests that the size of a stable community in social media should be limited to 150, referred to as Dunbar's number. In this paper, we propose a systematic way of algorithm comparison by orthogonally integrating community size as a new dimension into existing structural metrics for consistently and holistically evaluating the community quality in the social media context. We design a heuristic clique-based algorithm which controls the size and overlap of communities with adjustable parameters and evaluate it along with six state-of-the-art community detection algorithms on both Twitter and DBLP networks. Specifically, we divide the discovered communities based on their size into four classes called a close friend, a casual friend, acquaintance, and just-a-face, and then calculate the coverage, modularity, triangle participation ratio, conductance, transitivity, and the internal density of communities in each class. We discover that communities in different classes exhibit diverse structural qualities and many existing community detection algorithms tend to output extremely large communities.

The rapid growth of residential broadband connections and Internet-enabled home devices have driven the success of many useful applications such as video streaming and remote healthcare. However, poorly managed routers and connected devices in the home are vulnerable under persistent threats and exploitations from cyber attackers across the Internet who continuously identify, compromise, and control devices as part of botnets for launching click fraud, denial of service attacks, spam campaigns. These growing threats and broad damages have made it imperative to understand, characterize, filter, and reduce exploit traffic towards millions of home routers and billions of connected devices in the home. This paper presents a bloom-filter based analytics framework to capture persistent threats towards the same home routers and to identify correlated attacks towards distributed home networks. Our experimental results based on network traffic collected from real homes over 18months have revealed a number of interesting findings on persistent and correlated threats towards home networks, which calls for improved security and management of home networks. To the best of our knowledge, this paper is the first effort to characterize cyber threats towards home networks and to propose a simple and yet effective approach to identify persistent and aggressive attacks towards home networks. Copyright © 2016 John Wiley & Sons, Ltd.

These growing threats and broad damages have made it imperative to understand, characterize, filter, and reduce exploit traffic towards millions of home routers and billions of connected devices in the home. This paper presents a bloom-filter based analytic framework to capture persistent threats towards the same home routers and to identify correlated attacks towards distributed home networks. Our experimental results based on network traffic collected from real homes over 18 months have revealed a number of interesting findings on persistent and correlated threats towards home networks, which calls for improved security and management of home networks. To the best of our knowledge, this paper is the first effort to characterize cyber threats towards home networks and to propose a simple and yet effective approach to identify persistent and aggressive attacks towards home networks.

The explosive growth of online social networks in recent years have generated massive amount of data-sets in user behaviors, social graphs, and contents. Given the scale, heterogeneity, and diversity of such big data, sampling becomes a simple and intuitive approach to reduce the size of the data-sets for collecting, measuring, and understanding users, behaviors and traffic in online social networks. In this paper, we quantify the impact of random sampling on the analysis of online social networks with Twitter streaming data as a case study. In addition, we design different sampling strategies including community sampling and strata sampling, and evaluate their impact on a broad range of behavioral characteristics of online social networks. Our experimental results show that community sampling has the minimum impact on tweet distributions across users and the structure of retweeting graphs, while achieving the similar data reductions as random and stratified sampling.

As Internet traffic continues to grow in size and complexity, it has become an increasingly challenging task to understand behavior patterns of end-hosts and network applications. This paper presents a novel approach based on behavioral graph analysis to study the behavior similarity of Internet end-hosts. Specifically, we use bipartite graphs to model host communications from network traffic and build one-mode projections of bipartite graphs for discovering social-behavior similarity of end-hosts. By applying simple and efficient clustering algorithms on the similarity matrices and clustering coefficient of one-mode projection graphs, we perform network-aware clustering of end-hosts in the same network prefixes into different end-host behavior clusters and discover inherent clustered groups of Internet applications. Our experiment results based on real datasets show that end-host and application behavior clusters exhibit distinct traffic characteristics that provide improved interpretations on Internet traffic. Finally, we demonstrate the practical benefits of exploring behavior similarity in profiling network behaviors, discovering emerging network applications, and detecting anomalous traffic patterns.

The explosive growth of Internet-connected consumer devices in the digital home has made home networks one of the important emerging topics in networking research. A rich body of research efforts have been made to study broadband performance and home network management, little is known about network traffic that are exchanged within home networks or between Internet-connected devices in home networks and end hosts on the Internet. In this paper we design and implement a built-in traffic monitoring system on programmable home routers to collect and analyze incoming, outgoing and internal traffic for residential home networks. To illustrate the applications of the proposed built-in traffic monitoring system, we deploy the system in two real home networks, and demonstrate its capabilities of detecting unwanted traffic towards home networks as well as those suspicious traffic originating from compromised devices in home networks. In addition, our correlation analysis on unwanted traffic towards distributed home networks reveals aggressive scanners on the Internet and sheds lights on traffic characteristics of these scanners.

Mathematical modeling is an important approach to study information diffusion in online social networks. Prior studies have focused on the modeling of the temporal aspect of information diffusion. A recent effort introduced the spatiotemporal diffusion problem and addressed the problem with a theoretical framework built on the similarity between information propagation in online social networks and biological invasion in ecology [1]. This paper examines the spatio-temporal characteristics in further depth and reveals that there exist regularities in information diffusion in temporal and spatial dimensions. Furthermore, we propose a simpler linear partial differential equation that takes account of the influence of spatial population density and temporal decay of user interests in the information. We validate the proposed linear model with Digg news stories which received more than 3000 votes during June 2009, and show that the model can describe nearly 60% of the news stories with over 80% accuracy. We also use the most popular news story as a case study and find that the linear diffusive model can achieve an accuracy as high as 97:41% for this news story. Finally, we discuss the potential applications of this model towards finding super spreaders and classifying news story into groups.

The rapid growth of broadband connections and home networks has created new application opportunities such as video streaming and remote health care. However, managing and securing the increasingly complicated home networks has remained a serious challenge for most home users who have little technical expertise to manage their home networks and connected devices. Towards this end, we will demonstrate HomeTPS, a traffic profiling system for home networks that collects, analyzes and makes sense of home network traffic. The demonstration will show automatic traffic collection from programmable home routers, informative traffic summary reports and behavior profiles for Internet-capable home devices, and real-time discovery of anomalous traffic from Internet attackers or from compromised devices in home networks.

Recent years have witnessed rapid growth of innovative and disruptive Internet services such as video streaming and peer-to-peer applications. As network traffic of these applications continues to grow, it has become a challenging task to understand their communication patterns and traffic behavior of end hosts engaging in these applications. This paper presents a novel approach based on behavioral graph analysis to study social behavior of Internet applications based on bipartite graphs and one-mode projection graphs. Through a vector of graph properties including coefficient clustering that capture social behaviors of end hosts, we discover the inherent clustered groups of Internet applications that not only exhibit similar social behavior of end hosts, but also have similar characteristics in the aggregated traffic. In addition, we demonstrate the usage of the proposed approach in detecting emerging applications and anomalous traffic patterns towards Internet applications.

This paper explores the behavior similarity of Internet end hosts in the same network prefixes. We use bipartite graphs to model network traffic, and then construct one-mode projection graphs for capturing social-behavior similarity of end hosts. By applying a simple and efficient spectral clustering algorithm, we perform network-aware clustering of end hosts in the same prefixes into different behavior clusters. Based on information-theoretical measures, we find that the clusters exhibit distinct traffic characteristics which provides improved interpretations of the separated traffic compared with the aggregated traffic of the prefixes. Finally, we demonstrate the applications of exploring behavior similarity in profiling network behaviors and detecting anomalous behaviors through synthetic traffic that combines Internet backbone traffic and packet traces from real scenarios of worm propagations and denial of service attacks.

In this short paper, we present a preliminary design of a behavior profiling system in wireless home network (WHN) for network security monitoring. Figure 1 illustrates a schematic architecture of the behavior profiling system that is deployed in a typical wireless home network. The goals of the proposed behavior profiling system are to i) actively learn the traffic patterns of wireless home networks, ii) detect anomalous behavior from inside networks as well as from the Internet. Based on network traffic patterns for each computer, the system builds baseline behavior profiles, and subsequently detects events of interest through behavior deviations. The contributions of this work are two-fold. First, we propose to build the behavior profiles for each computer in WHNs towards a deep understanding of the traffic patterns in wireless residential networks. Secondly, we present a systematic architecture that aims to detect anomalous behavior through real-time traffic profiling.

Wireless sensor networks (WSNs) have been increasingly deployed for both civil and military applications under harsh, unpredictable or open environments. Such environments create opportunities for the intruders to launch a variety of attacks on multiple protocol layers in WSNs. This paper proposes a behavior monitoring and analysis framework for large scale WSNs. Within this framework, we address the monitor node selection problem and introduce a dedicated monitor nodes approach and propose a greedy algorithm for selecting monitor nodes. The simulation results show that the greedy algorithm is efficient in terms of monitor node set size.

Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. In this paper, we propose a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We show that CDSA has guaranteed quality by proving that the size of the CDSA constructed 2-connected backbone is within a constant factor of the optimal 2-connected virtual backbone size. Through extensive simulations, we demonstrate that in practice, CDSA can build a 2-connected virtual backbone with only small overhead.

Recent outages in several Web services have demonstrated the potential damage of availability disruptions, since millions of end users rely on these services powered by thousands of servers in large-scale Internet data centers. As Internet data centers continue to grow in scale and complexity, it has become a daunting task to monitor and manage thousands of servers simultaneously. This paper presents a cooperative monitoring framework to continuously monitor availability of thousands of servers in Internet data centers. We propose a simple yet effective algorithm for locating monitor nodes for the purposes of load balancing and resilience, and demonstrate the performance of this method through simulations based on dataset collected from a large Internet content provider. The results show that the monitoring load are well divided among the servers in the data centers, and cooperative monitoring adapts gracefully to the events of monitoring node failures.

This paper introduces the problem of fault tolerant topology control for all-to-one and one-to-all communication in static wireless networks with asymmetric wireless links. This problem is important in both theoretical and practical aspects. We investigate two approaches, namely minimum weight based approach and nearest neighbor augmentation approach, to address this problem. Furthermore, we give theoretical analysis for the proposed algorithms. Among other results, we show that the minimum weight based approach has a $k$-approximation algorithm for all-to-one fault tolerant topology control where $k$ is the number of disjoint paths. When $k=1$, this approach solves the minimum power all-to-one $1$-connected topology control problem. To the best of our knowledge, this paper is the first to study the fault tolerant topology control for all-to-one and one-to-all communication in asymmetric static wireless networks, and also is the first to demonstrate that the minimum power all-to-one 1-connected topology control problem has an optimal solution.

This paper presents the design and implementation of a real-time behavior profiling system for high-speed Internet links. The profiling system uses flow-level information from continuous packet or flow monitoring systems, and uses data mining and information-theoretic techniques to automatically discover significant events based on the communication patterns of end-hosts. We demonstrate the operational feasibility of the system by implementing it and performing extensive benchmarking of CPU and memory costs using a variety of packet traces from OC-48 links in an Internet backbone network. To improve the robustness of this system against sudden traffic surges such as those caused by denial of service attacks or worm outbreaks, we propose a simple yet effective filtering algorithm. The proposed algorithm successfully reduces the CPU and memory cost while maintaining high profiling accuracy.

Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a "trade-off" scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in [2].

In this paper, we study the Maximum lifetime Target Coverage problem (MTC), which is to maximize the network lifetime while guaranteeing the complete coverage of all the targets. Many centralized algorithms have been proposed to solve this problem. A very few distributed versions have also been presented but none of them obtains a good approximation ratio. In this paper, we propose two O(log n) localized algorithms. In particular, we first reduce the MTC problem to the domatic number problem in directed graphs. This relation shows that a feasible solution to the domatic number problem is also a feasible solution to the MTC problem. We next prove the lower and upper bounds of this domatic number. Based on this proof, we present two O(log n)-localized algorithms to solve the MTC problem.

Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone. The CDS of a graph representing a network has a significant impact on the efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which all nodes have the same transmission ranges. However, in practice, the transmission ranges of all nodes are not necessarily equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present two efficient approximation algorithms to obtain a minimum CDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. These algorithms can be implemented as distributed algorithms. Furthermore, we show a size relationship between a maximal independent set and a CDS as well as a bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.

Energy conservation is an important concern in wireless networks. Many algorithms for constructing a broadcast tree with minimum energy consumption and other goals have been developed. However, no previous research work considers the total energy consumption and transmission delays of the broadcast tree simultaneously. In this paper, based on an (alpha, beta)-tree, a novel concept to wireless networks, we define a new strongly connected broadcast arborescence with bounded transmission delay (SBAT) problem and design the strongly connected broadcast arborescence (SBA) algorithm with linear running time to construct a strongly connected broadcast tree with bounded total power, while satisfying the constraint that the transmission delays between the source and the other hosts are also bounded. We also propose the distributed version of the SBA algorithm. The theoretical analysis and simulation results show that the SBA algorithm gives a proper solution to the SBAT problem

In mobile ad-hoc networks, hosts communicate with each other without the help of any physical infrastructure. Inevitably, the communication tends to be less efficient in terms of computational and communicational overhead. Recent studies have shown that virtual backbone can help reduce the communication overhead. However, the backbone structure is very vulnerable due to several reasons, e.g., node mobility and unstable links, etc. In this paper, we introduce a localized virtual backbone construction scheme, connected maximal independent set with multiple initiators (MCMIS), which takes node stability into consideration and can construct the backbone quickly. We design MCMIS aiming at three goals: small backbone size, fast construction, stable backbone. Through extensive simulations, we find that our scheme could obtain a better performance on stability and backbone size than other localized schemes.

Abstract Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP‐hard. In this paper, we propose a new greedy algorithm, called S‐MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S‐MIS with its variation which is rS‐MIS. The simulation shows that the sizes of the CDSs generated by S‐MIS and rS‐MIS are almost the same. Copyright © 2005 John Wiley & Sons, Ltd.

In wireless ad-hoc networks, hosts communicate with each other without help of any physical infrastructure. Inevitably, the communication tends to be inefficient in terms of computational and network resources. Study on virtual infrastructures or backbones in wireless ad-hoc networks gets more attention in the hope of reducing the communication overhead. But the backbone structure is very vulnerable due to various factors like node mobility, unstable links, and so on. So a new scheme which is reliable and efficient both to construct and maintain the backbone structure is needed. We present our noble virtual backbone scheme which is reliable and efficient by considering stability and coverage of nodes.