Abstract Graph-structured data are integral to applications like social networks, biological systems, cybersecurity, and fraud detection. Outsourcing these data to public clouds offers scalability but raises privacy concerns, as encryption is required before outsourcing, making traditional graph similarity search and access control challenging. This paper presents a novel solution for privacy-preserving full graph similarity search with fine-grained access control in cloud environments. To the best of our knowledge, this is the first work to integrate privacy-preserving graph similarity search in a multi-user/multi-query setting with attribute-based access control (ABAC). This enables scalable and secure access in realistic, collaborative environments. The graph owner leverages the neural Graph2vec model to create feature indexes for encrypted graph data. Simultaneously, a secure transfer learning mechanism enables graph users to generate query feature indexes in the same latent space, ensuring privacy while accurately capturing the user’s query intent. ABAC is employed to enforce flexible, fine-grained access policies. We conduct a formal security analysis under known-ciphertext and known-background threat models, demonstrating strong privacy guarantees. Experimental evaluations on real-world datasets show that our scheme achieves high semantic accuracy, lower search latency, and reduced storage overhead, outperforming existing approaches.

The robust network topology of the Internet of Things (IoT) system facilitates uninterrupted service provisioning when encountering device failures. Traditional topology optimization strategies use link-level algorithms to design robust network topologies for IoT device deployment, ensuring network resilience against failures. These algorithms struggle to provide a robust topology for large-scale networks due to the high complexity and computational cost of optimizing each link individually. To overcome this limitation, we introduceLEGO-Motif, a motif-based IoT topology generation algorithm inspired by preferential attachment (PA) and evolutionary theory. By sequentially integrating network motifs, similar to assembling LEGO bricks, the algorithm efficiently enhances topology robustness while reducing computational overhead. Specifically, we propose a novel metric based on motif density to measure topology robustness; then, guided by this metric, we design a topology generation algorithm that ensures optimal topology with high robustness against cyberattacks throughout its growth, inspired by an evolutionary neural network framework. The LEGO-Motif algorithm introduces novel recombination, PA-based mutation, and pruning operators to enhance optimization performance and reduce running-time costs. Comprehensive case studies and evaluations show that LEGO-Motif outperforms current topology optimization algorithms, achieving more robust network topologies with reduced running time, which offers a promising optimal solution for deploying the IoT topology.

Deploying quantum networks involves the placement of quantum repeaters, which generate entangled qubits for quantum computers to perform quantum teleportation. Besides placing repeaters on ground devices, there have been efforts towards the use of satellites or drones as repeaters. This paper considers the scenario of using drones due to their cost-efficiency and support for flexible network formation. While several issues in this scenario, such as enhancing network connectivity, have been studied, this paper addresses a new problem: how to minimize the number of drones placed in the air to cover all quantum computers on the ground and make the entire quantum network connected. Given that this problem is NP-hard, we propose a suboptimal but polynomial-time approach for it. Our approach consists of two stages. Stage 1 aims to minimize the number of drones needed to cover the ground computers, and Stage 2 aims to minimize the number of drones needed for connecting the drones returned by Stage 1. Both stages use algorithms of no more than quadratic time complexity. We conduct experiments to determine the best algorithm for the setting of quantum networks from several high-performing existing algorithms and design optimization techniques for existing algorithms. Our experiments confirm that our approach reduces the number of drones placed effectively.

With the scale of the Internet of Things (IoT) system growing constantly, node failures frequently occur due to device malfunctions or cyberattacks. Existing robust network generation methods utilize heuristic algorithms or neural network approaches to optimize the initial topology. These methods do not explore the core of topology robustness, namely how edges are allocated to each node in the topology. As a result, these methods use massive iterative processes to optimize the initial topology, leading to substantial time overhead when the scale of the topology is large. We examine various robust networks and observe that uniform degree distribution is the core of topology robustness. Consequently, we propose a novel UNIformity driven robusT topologY generation scheme (UNITY) for IoT systems to prevent the node degree from becoming excessively high or low, thereby balancing node degrees. Comprehensive experimental results demonstrate that networks generated with UNITY have an “olive-like” topology consisting of a substantial number of medium-degree nodes and possess strong robustness against both random node failures and targeted attacks. This promising result indicates that the UNITY makes a significant advancement in designing robust IoT systems.

Robust Topology is a key prerequisite to providing consistent connectivity for highly dynamic Internet-of-Things (IoT) applications that are suffering node failures. In this paper, we present a two-step approach to organizing the most robust IoT topology. First, we propose a novel robustness metric denoted as$I$, which is based on network motifs and is specifically designed to sensitively analyze the dynamic changes in topology resulting from node failures. Second, we introduce a Distributed duAl-layer collaborative competition optimization strategy based on Motif density (DAiMo). This strategy significantly expands the search space for optimal solutions and facilitates the identification of the optimal IoT topology. We utilize the motif density concept in the collaborative optimization process to efficiently search for the optimal topology. To support our approach, extensive mathematical proofs are provided to demonstrate the advantages of the metric$I$in effectively perceiving changes in IoT topology and to establish the convergence of the DAiMo algorithm. Finally, we conduct comprehensive performance evaluations of DAiMo and investigate the influence of network motifs on the resilience and reliability of IoT topologies. Experimental results clearly indicate that the proposed method outperforms existing state-of-the-art topology optimization methods in terms of enhancing network robustness.

Thanks to the applications such as Quantum Key Distribution and Distributed Quantum Computing, the deployment of quantum networks is gaining great momentum. A major component in quantum networks is repeaters, which are essential for reducing the error rate of qubit transmission for long-distance links. However, repeaters are expensive devices, so minimizing the number of repeaters placed in a quantum network while satisfying performance requirements becomes an important problem. Existing solutions typically solve this problem optimally by formulating an Integer Linear Program (ILP). However, the number of variables in their ILPs is O ( n 2 ) , where n is the number of nodes in a network. This incurs infeasible running time when the network scale is large. To overcome this drawback, this paper proposes to solve the repeater placement problem by two steps, with each step using a linear program of a much smaller scale with O ( n ) variables. Although this solution is not optimal, it dramatically reduces the time complexity, making it practical for large-scale networks. Moreover, it constructs networks that have higher node connectivity than those by existing solutions, since it deploys slightly more number of repeaters into networks. Our extensive experiments on both synthetic and real-world network topologies verified our claims.

Numerous sensor nodes deployed in the Internet of Things (IoT) can form a large heterogeneous network. The increased energy consumption of sensor nodes and the unbalanced communication load on multiple sink nodes reduce the energy efficiency of the network. Moreover, frequent network attacks also pose severe challenges to topology robustness. Optimizing the network topology to achieve the balance between energy efficiency and robustness is a complex problem. Multi-objective heuristic algorithms based on genetic evolution are commonly used to solve joint optimization problems. However, due to the lack of global search ability caused by the loss of genetic diversity, genetic operations are prone to premature convergence during multi-objective evolution. Therefore, this paper introduces multi-population cooperation into the multi-objective evolution process and proposes a novel layered-cooperation Topology Evolution Algorithm for Multi-sink IoT (TEAM). In TEAM, information entropy is used to measure the effectiveness of load balancing on multiple sink nodes. The crossover and mutation probabilities of different populations are dynamically adjusted to ensure genetic diversity. A layered-cooperation mechanism is designed to avoid premature convergence. Extensive experiments confirm that TEAM can effectively improve the energy efficiency and robustness of network topology while balancing the communication load on multi-sink nodes.

Fast-advancing mobile communication technologies have increased the scale of the Internet of Things (IoT) dramatically. However, this poses a tough challenge to the robustness of IoT networks when the network scale is large. In this paper, we present DAC-Motif, a distributed co-evolutionary method for optimizing network robustness based on network motifs. Unlike centralized evolutionary optimization approaches, DAC-Motif uses the technique of Divide-And-Conquer (DAC) to divide the large-scale IoT topology into partitions and then merge the self-evolving partitions into a global robust topology. This approach leverages both distributed computing and asynchronous communication mechanisms to mitigate premature convergence and reduce time complexity for large-scale IoT topologies. In our evaluation, DAC-Motif achieves three to four orders of magnitude shorter running time and over 10% robustness improvement compared to other centralized evolutionary algorithms under a scale of around 5,000 IoT devices.

Only when understanding hackers” tactics, can we thwart their attacks. With this spirit, this paper studies how hackers can effectively launch the so-called ‘targeted node attacks”, in which iterative attacks are staged on a network, and in each iteration the most important node is removed. In the existing attacks for weighted networks, the node importance is typically measured by the centralities related to shortest paths, and the attack effectiveness is also measured mostly by shortest-path-related metrics. However, this paper argues that flows can better reflect network functioning than shortest paths for those networks with carrying traffic as the main functionality. Thus, this paper proposes metrics based on flows for measuring the node importance and the attack effectiveness, respectively. Our node importance metrics include three flow-based centralities (flow betweenness, current-flow betweenness and current-flow closeness), which have not been proposed for use in the attacks on weighted networks yet. Our attack effectiveness metric is a new one proposed by us based on average network flow. Extensive experiments on both artificial and real-world networks show that the attack methods with our three suggested centralities are more effective than the existing attack methods when evaluated under our proposed attack effectiveness metric.

In recent years, cloud computing platforms have attracted more and more attention. A key challenge is that existing schedulers provide limited support for heterogeneous types of resources. This makes it difficult to allocate resources in a timely manner adaptively and efficiently to perform different kinds of tasks. In this paper, we develop and evaluate a scheduling system with QoS guarantees when multiple tasks are involved, in which we show a possible design driven by the use of utilities for task-based resource allocation. We call the resulting method PECS, which meets the following unique properties compared to existing systems: Pareto efficiency, i.e. no other assignment can increase the sum of utility of all tasks without harming at least one specific task; freedom of envyness, i.e. no task will find the allocation of resource for another task better for its own utility; finally, improvements based on equal distribution are guaranteed, that is, the utility of all tasks is at least as high as the equal distribution of all resources. Our evaluation results compare PECS with a state-of-the-art resource allocation method called DRF, where our results demonstrate the performance benefits of PECS applied to a rich set of task assignment scenarios.

Distributed Denial of Service (DDoS) attacks exhaust the resources of network services by generating a huge volume of network traffic. They constitute a primary threat to the current Internet community. To mitigate this threat, we propose a Machine Learning model based on Random Forest for detecting DDoS attacks. In our Random Forest, a great number of decision trees under both the Gini Index and Entropy criteria are constructed to improve the detection accuracy. Moreover, with the intrinsic simplicity of Random Forest model, our model is fast in terms of model convergence and attack detection. The data for building our model comes from the newly released dataset CICDDoS2019, which contains a large variety of DDoS attacks with a new classification based on network flows. The experimental results show that our model achieves high accuracy rates and F1_scores, and outperforms an existing state-of-the-art machine learning model for DDoS detection.

This work applies Game Theory to developing secure software. With the perspective of Game Theory, one can see secure software development as a game between software developers and software security engineers, who play this game repeatedly in processes such as agile Software Development Life Cycle (SDLC). The problem we observe is that there can be conflicts between these two players regarding who should find and fix certain software vulnerabilities. To solve this problem, our approach uses Mechanism Design in Game Theory to design games that enforce cooperation between these two players. In doing so, we identify the source of the conflicts between them by looking at the components of the software. These components may be the methods or functions in the software, or individual modules, or similar building blocks. The novelty of our work is that our mechanism constructs a game which allocates software components between these two players such that they work cooperatively while trying to maximize their own payoffs.

Robust network infrastructures are essential for the delivery of vital services for our daily lives. With the widespread cyber-attacks on them, measuring the robustness of these networks has become an important issue. In recent years, many robustness metrics have been proposed for this purpose. Among them, a metric called ‘R’ has received wide attention, and several variants have been proposed. These variants include a metric called Communication Robustness (CR) and the betweenness and closeness variants to both R and CR. However, no evaluations about the correlations among these variants have been made to shed light on their necessity and effectiveness. Addressing this research gap, this paper makes the following contributions. First, we measure the correlations between R and CR to verify that CR is valid to exist due to its unique perspective although it correlates closely with R. Second, we measure the correlations between R and its betweenness/closeness variants to show that they are quite different, and the same is observed for CR and its betweenness/closeness variants. Finally, we propose a new robustness metric called Simplified Communication Robustness (SCR), which simplifies the calculation of CR while working almost the same as CR.

The complex factory environment of the Industrial Internet of Things (IIoT) greatly increases the energy consumption of sensor nodes and reduces production profits. Especially, in mines, the terrain will change continuously as the mining progresses. Additionally, the heavy traffic load on a single sink node and the unbalanced load on multiple sink nodes also reduce the battery life. Therefore, how to build an energy-efficient topology based on the unique mine terrain characteristics is a critical issue. To address this problem, this article proposes a 3-D topology evolution scheme with self-adaption for mining areas (3D-TES) to reduce energy consumption. We build the multipeak terrain model according to the characteristics of the mining environment. Blocked by the undulating peaks on the mine, the strength of the node signal is quantified by the slope and aspect. The 3D-TES is then applied to determine the optimal number of sink nodes and find the best data transmission path between sensor nodes and multiple sink nodes. The experimental results show that 3D-TES outperforms the directed angulation toward the sink node model (DASM) in terms of reliability, average path length, and data load on sink nodes.

Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker's goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1/sqrt(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time.

Dependence of computing resources on each other in cloud computing systems (CCS) makes them prone to fail in correlated manner which significantly impacts their service reliability and energy efficiency. Focusing on these two metrics of CCS while considering correlated failures remained an open question, which is the focus of this work. This paper proposes mechanisms for improving reliability and energy efficiency jointly under correlated failures in CCS. In order to model failure correlation, statistical cluster analysis techniques are applied to real failure traces. Then, mathematical models are built to calculate reliability and energy consumption of failure prone CCS. These mathematical models are used to design fault-tolerant and energy-aware resource provisioning mechanisms/policies. In order to further reduce the energy consumption, a correlated failure-aware VM consolidation policy is also proposed in this paper. A simulation based study of the proposed resource management policies and fault tolerance mechanisms is conducted by using real failure traces and Bag-of-Tasks workload. The results demonstrate that by exploiting failure correlation with the proposed resource management policies, we reduce the occurrence of failures on tasks by 34 percent and increase the energy efficiency of the system by 20 percent, approximately in comparison to the environments where failures are handled independently.

This paper considers the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one category of such attacks, in which attacks happen by rounds, and in each round, the node with the highest centrality and its adjacent links are removed. Here the centrality can be any centrality measure such as Degree Centrality, Betweenness Centrality, etc. For this attack category, there currently exist two strategies: Initial and Adaptive. In the Initial strategy, node centralities are only calculated initially, while in the Adaptive strategy, node centralities are recalculated after each round of attack. In the literature, it has been shown that the Adaptive strategy is more effective than the Initial strategy for a centrality measure. In this paper, we propose a new strategy called the largest component (LC) strategy which further outperforms the Adaptive strategy in terms of both attack effectiveness and computation complexity. Moreover, we propose the use of current-flow versions of Betweenness Centrality and Closeness Centrality as the centrality measures in the attacks, since they are more granular and supported by the LC strategy. We verify the better performances of the LC strategy by extensive experiments on four kinds of artificial networks and two realworld networks. Our experiments also show that the Currentflow Betweenness Centrality makes attacks the most effective among the five centrality measures studied in this paper.

One critical challenge of managing modern data center networks lies in that existing network protocols provide limited visibility on the internal routing and forwarding decisions made by the control plane, leading to difficulties on fast diagnosis and identification of root causes for performance bugs and anomalies. In this paper, we develop and evaluate a “debugging mode” for packet forwarding, where we demonstrate a possible design space by introducing a programmable header field into data packets used for diagnosis purposes. These headers can be manipulated by routers in intermediate hops to perform tracing and diagnosis operations, thereby providing much greater visibility on the control plane and data plane operations. To make this design scalable and feasible, we exploit the software APIs provided by the latest software-defined networking (SDN) technologies, where the network control plane is separated from the underlying data plane, so that we can reprogram the network forwarding functions dynamically. Compared to existing alternative approaches, our approach is adaptive and programmable, allowing dynamic and on-demand receiver-side decoding with extremely low overhead. We emphasize that as this “debugging mode” can be enabled and disabled by network managers as demanded, it introduces zero overhead to normal traffic if everything is operating as expected. Our evaluation results on a real SDN network testbed demonstrate the effectiveness of the proposed approaches.

Wireless sensor networks (WSNs) have been the popular targets for cyberattacks these days. One type of network topology for WSNs, the scale-free topology, can effectively withstand random attacks in which the nodes in the topology are randomly selected as targets. However, it is fragile to malicious attacks in which the nodes with high node degrees are selected as targets. Thus, how to improve the robustness of the scale-free topology against malicious attacks becomes a critical issue. To tackle this problem, this paper proposes a Robustness Optimization scheme with multi-population Co-evolution for scale-free wireless sensor networKS (ROCKS) to improve the robustness of the scale-free topology. We build initial scale-free topologies according to the characteristics of WSNs in the real-world environment. Then, we apply our ROCKS with novel crossover operator and mutation operator to optimize the robustness of the scale-free topologies constructed for WSNs. For a scale-free WSNs topology, our proposed algorithm keeps the initial degree of each node unchanged such that the optimized topology remains scale-free. Based on a well-known metric for the robustness against malicious attacks, our experiment results show that ROCKS roughly doubles the robustness of initial scale-free WSNs, and outperforms two existing algorithms by about 16% when the network size is large.

The controller placement problem (CPP) is one of the key challenges of software defined networks (SDNs) to increase performance. Given the locations of n switches, CPP consists of choosing the controller locations that minimize the latency between switches and SDN controllers. In its current form, however, CPP assumes a fixed traffic and no existing solutions adapt the placement to the load. In this paper, we have addressed the dynamic CPP that consists of: 1) determining the locations of controller modules to bound communication latencies and 2) determining the number of controllers per module to support the dynamic load. We propose an algorithm named LiDy+ that runs in O(n2) and combines a controller module placement algorithm with a dynamic flow management algorithm. We evaluate the number of controllers, the controller utilization, and the power consumption and the maintenance cost of LiDy+ on both sparse and dense networks. Our comparison against a previous solution shows that LiDy+ does not only achieve a smaller number of controllers and a higher controller utilization but also incurs less energy and maintenance costs than the previous solution. Finally, we run LiDy+ in a large-scale environment where the previous solution of time complexity Ω(n2logn) is impractical.

Due to the recent proliferation of cyber-attacks, improving the robustness of wireless sensor networks (WSNs), so that they can withstand node failures has become a critical issue. Scale-free WSNs are important, because they tolerate random attacks very well; however, they can be vulnerable to malicious attacks, which particularly target certain important nodes. To address this shortcoming, this paper first presents a new modeling strategy to generate scale-free network topologies, which considers the constraints in WSNs, such as the communication range and the threshold on the maximum node degree. Then, ROSE, a novel robustness enhancing algorithm for scale-free WSNs, is proposed. Given a scale-free topology, ROSE exploits the position and degree information of nodes to rearrange the edges to resemble an onion-like structure, which has been proven to be robust against malicious attacks. Meanwhile, ROSE keeps the degree of each node in the topology unchanged such that the resulting topology remains scale-free. The extensive experimental results verify that our new modeling strategy indeed generates scale-free network topologies for WSNs, and ROSE can significantly improve the robustness of the network topologies generated by our modeling strategy. Moreover, we compare ROSE with two existing robustness enhancing algorithms, showing that ROSE outperforms both.

Improving energy efficiency of data centers has become increasingly important nowadays due to the significant amounts of power needed to operate these centers. An important method for achieving energy efficiency is server consolidation supported by virtualization. However, server consolidation may incur significant degradation to workload performance due to virtual machine (VM) co-location and migration. How to reduce such performance degradation becomes a critical issue to address. In this paper, we propose a profiling-based server consolidation framework which minimizes the number of physical machines (PMs) used in data centers while maintaining satisfactory performance of various workloads. Inside this framework, we first profile the performance losses of various workloads under two situations: running in co-location and experiencing migrations. We then design two modules: (1) consolidation planning module which, given a set of workloads, minimizes the number of PMs by an integer programming model, and (2) migration planning module which, given a source VM placement scenario and a target VM placement scenario, minimizes the number of VM migrations by a polynomial time algorithm. Also, based on the workload performance profiles, both modules can guarantee the performance losses of various workloads below configurable thresholds. Our experiments for workload profiling are conducted with real data center workloads and our experiments on our two modules validate the integer programming model and the polynomial time algorithm.

Greedy Forwarding algorithm is a widely-used routing algorithm for wireless networks. However, it can fail if the wireless network topologies contain voids, where a packet cannot be moved closer to destination. Since Yao graph and Theta graph are two types of geometric graphs exploited to construct wireless network topologies, this paper firstly studied whether these two types of graphs can contain voids, showing that when the number of cones in a Yao graph or Theta graph is less than six, Yao graph and Theta graph can have voids, and when the number of cones equals or exceeds six, Yao graph and Theta graph are free of voids. Secondly, this paper experimented on how well Greedy Forwarding is supported on Yao graphs and Theta graphs in terms oí stretch, i.e., the ratio between the path length found by Greedy Forwarding and the shortest path length in a graph. The experiments also included comparison with the stretch on Delaunay triangulation, another well-known geometric graph exploited in constructing wireless networks. Overall, our experiments revealed several interesting results.

This paper first envisions the advent of the wireless mesh networks with multiple radios and directional antennas in future. Then, based on the observation that simplicity induces efficiency and scalability, the paper proposes a joint geometric deployment and routing strategy for such mesh networks, and also gives a concrete approach under this strategy. The main idea of this strategy is to deploy mesh networks in certain kind of geometric graph, and then design a geometric routing protocol by exploiting the routing properties of this graph. The proposed concrete approach comprises two parts: (1) a topology generation algorithm based on Delaunay triangulations and (2) a geometric routing protocol based on the greedy forwarding algorithm. Both parts are characterized by simplicity and appealing properties, with formal proofs provided when possible. The simulation results validate our proposed approach.

Greedy forwarding is an efficient and scalable geographic routing algorithm for wireless networks. To guarantee the success of greedy forwarding, many research efforts assign virtual coordinates to nodes to obtain a greedy embedding of the network. Different from these existing efforts, this paper presents an approach that enables greedy forwarding to succeed in directional wireless networks by selecting links in the network instead of assigning virtual coordinates to the nodes. Specifically, this paper studies the following problem: given a set of nodes on the Euclidean plane, how can we add a minimum number of point-to-point links, such that the greedy forwarding algorithm succeeds on the resulting network. The motivation for studying this problem is that each point-to-point link in directional wireless networks is realized by a pair of directional antennas, so minimizing the number of links will reduce the network installation cost. This paper first presents the properties of the graphs supporting greedy forwarding, and then solves the above problem optimally by Integer Linear Programming and also sub-optimally by a polynomial-time 3-approximation algorithm. Finally, this paper compares the polynomial-time algorithm with the optimal solution, showing that the polynomial-time algorithm can actually generate within 1.1 times the number of links found by the optimal solution in most cases.

With popularity of data centers, energy efficiency of Ethernet switches in them is becoming a critical issue. Most existing energy saving approaches use a centralized methodology that assumes global knowledge of data center networks. Though these approaches can achieve nearly optimal energy saving for static traffic patterns, they are not suitable when the traffic patterns can change rapidly or the data centers have a large size. To overcome these limitations, this paper proposes a novel distributed approach called eAware that dynamically idles a port or a switch to save energy by examining the queue lengths and utilizations at switch ports. Through extensive simulations in ns-2, we compare eAware with an existing energy oblivious approach, showing that eAware can save 30%-50% on the total energy consumption by switches in data centers, and only increases the average end-to-end delay of packets by 3%-20% and the packet loss ratio by 0%-0.9%.

Memoryless online routing (MOR) algorithms are suitable for the applications only using local information to find paths, and Delaunay triangulations (DTs) are the class of geometric graphs widely proposed as network topologies. Motivated by these two facts, this paper reports a variety of new MOR algorithms that work for Delaunay triangulations, thus greatly enriching the family of such algorithms. This paper also evaluates and compares these new algorithms with three existing MOR algorithms. The experimental results shed light on their performance in terms of both Euclidean and link metrics, and also reveal certain properties of Delaunay triangulations. Finally, this paper poses three open problems, with their importance explained.

Memoryless online routing (MOR) algorithms are important for the applications with only local information available to make routing decisions. This paper gives two new MOR algorithms for a class of geometric graphs called Delaunay triangulations (DTs): the Midpoint Routing algorithm and the Compass Midpoint algorithm. More meaningfully, the former is generalized into a set of MOR algorithms that use the Euclidean distance as the reference and work for DTs, and the latter is generalized into a set of MOR algorithms that use the direction as the reference and work for DTs. Many other existing MOR algorithms can also be covered by these two sets. Finally, the two new algorithms are e valuated and compared with other existing MOR algorithms, and the experimental results give new findings on the performances of these algorithms in average and general cases.

Observing that simplicity implies efficiency and scalability, this paper proposes a position-based deployment and routing strategy, and then gives a concrete approach under this strategy, for the emerging wireless mesh networks with multiple radios and directional antennas. The main idea of this strategy is to deploy the mesh network in certain kind of geometric graph and then design a position-based routing protocol by exploiting the routing properties of this graph. The proposed concrete approach comprises two parts: (1) a topology generation algorithm based on Delaunay triangulations and (2) a routing protocol based on the greedy forwarding algorithm. Both parts have appealing properties for deployment or routing, with formal proofs provided when applicable. Our simulation results strongly support this proposed approach.

This work presents a new MAC protocol called RMAC that supports reliable multicast for wireless ad hoc networks. By utilizing the busy tone mechanism to realize multicast reliability, RMAC has the following three novelties: (1) it uses a variable-length control frame to stipulate an order for the receivers to respond, such that the problem of feedback collision is solved; (2) it extends the traditional usage of busy tone for preventing data frame collisions into the multicast scenario; and (3) it introduces a new usage of busy tone for acknowledging data frames. In addition, we also generalize RMAC into a comprehensive MAC protocol that provides both reliable and unreliable services for all the three modes of communications: unicast, multicast, and broadcast. Our evaluation shows that RMAC achieves high reliability with very limited overhead. We also compare RMAC with other reliable multicast MAC protocols, showing that RMAC not only provides higher reliability but also involves lower cost.

Application-layer multicast supports group applications without the need for a network-layer multicast protocol. Here, applications arrange themselves in a logical overlay network and transfer data within the overlay. We present an application-layer multicast solution that uses a Delaunay triangulation as an overlay network topology. An advantage of using a Delaunay triangulation is that it allows each application to locally derive next-hop routing information without requiring a routing protocol in the overlay. A disadvantage of using a Delaunay triangulation is that the mapping of the overlay to the network topology at the network and data link layer may be suboptimal. We present a protocol, called Delaunay triangulation (DT protocol), which constructs Delaunay triangulation overlay networks. We present measurement experiments of the DT protocol for overlay networks with up to 10 000 members, that are running on a local PC cluster with 100 Linux PCs. The results show that the protocol stabilizes quickly, e.g., an overlay network with 10 000 nodes can be built in just over 30 s. The traffic measurements indicate that the average overhead of a node is only a few kilobits per second if the overlay network is in a steady state. Results of throughput experiments of multicast transmissions (using TCP unicast connections between neighbors in the overlay network) show an achievable throughput of approximately 15 Mb/s in an overlay with 100 nodes and 2 Mb/s in an overlay with 1000 nodes.