Data-driven machine learning approaches have been proposed to facilitate wireless network optimization by learning latent knowledge from historical optimization instances. However, existing works use simplistic network representations that cannot properly encode the topological difference. They are often limited to fixed topology, and the performance is degraded because the learning target does not get sufficient information since the topological information is not well captured.To address this, we leverage the graphical neural network techniques and propose a two-stage topology-aware deep learning (TADL) framework, which trains a graph embedding unit and a link usage prediction module jointly to discover links likely to be used in optimal scheduling. By properly encoding the network structure, it makes input data with varying topology possible, and also provides more informative clues for the learning target.Important techniques are developed to ensure learning efficiency. The performance is evaluated on canonical multi-hop flow problems with diverse network structures, sizes and realistic deployment scenarios. It achieves close-to-optimum solution quality with a significant reduction in computation time without retraining.

Networks undergo continuous changes to introduce new services and improve existing ones. Network change deployment involves carefully deciding when each change activity will be executed and who will be executing the change. This is a complex process because each service group has to plan its activities following a set of operational and technological constraints. Besides, multiple groups may be working on the same or dependent nodes at the same time, and they must coordinate their deployment plans. If they do not co-ordinate, conflicting change execution could result in unexpected impacts. Traditionally, change deployment has been a tedious and time-consuming task. To address this, we propose an innovative solution Zapper that aims for minimal human effort to coordinate the changes, minimal risk to service quality, and efficient plans to rapidly deploy the changes. Zapper maps change scheduling constraints into mathematical equations and then uses optimization algorithms to generate conflict-free change plans that satisfy all constraints across service groups. We have deployed Zapper at a large service provider and it is being used regularly by the network operations teams for more than two years to schedule over 4.5 million change activities.

While Deep Reinforcement Learning has emerged as a de facto approach to many complex experience-driven networking problems, it remains challenging to deploy DRL into real systems. Due to the random exploration or half-trained deep neural networks during the online training process, the DRL agent may make unexpected decisions, which may lead to system performance degradation or even system crash. In this paper, we propose PnP-DRL, an offline-trained, plug and play DRL solution, to leverage the batch reinforcement learning approach to learn the best control policy from pre-collected transition samples without interacting with the system. After being trained without interaction with systems, our Plug and Play DRL agent will start working seamlessly, without additional exploration or possible disruption of the running systems. We implement and evaluate our PnP-DRL solution on a prevalent experience-driven networking problem, Dynamic Adaptive Streaming over HTTP (DASH). Extensive experimental results manifest that 1) The existing batch reinforcement learning method has its limits; 2) Our approach PnP-DRL significantly outperforms classical adaptive bitrate algorithms in average user Quality of Experience (QoE); 3) PnP-DRL, unlike the state-of-the-art online DRL methods, can be off and running without learning gaps, while achieving comparable performances.

Modern communication networks have become very complicated and highly dynamic, which makes them hard to model, predict and control. In this paper, we develop a novel experience-driven approach that can learn to well control a communication network from its own experience rather than an accurate mathematical model, just as a human learns a new skill (such as driving, swimming, etc). Specifically, we, for the first time, propose to leverage emerging Deep Reinforcement Learning (DRL) for enabling model-free control in communication networks; and present a novel and highly effective DRL-based control framework, DRL-TE, for a fundamental networking problem: Traffic Engineering (TE). The proposed framework maximizes a widely-used utility function by jointly learning network environment and its dynamics, and making decisions under the guidance of powerful Deep Neural Networks (DNNs). We propose two new techniques, TE-aware exploration and actor-critic-based prioritized experience replay, to optimize the general DRL framework particularly for TE. To validate and evaluate the proposed framework, we implemented it in ns-3, and tested it comprehensively with both representative and randomly generated network topologies. Extensive packet-level simulation results show that 1) compared to several widely-used baseline methods, DRL-TE significantly reduces end-to-end delay and consistently improves the network utility, while offering better or comparable throughput; 2) DRL-TE is robust to network changes; and 3) DRL-TE consistently outperforms a state-of-the-art DRL method (for continuous control), Deep Deterministic Policy Gradient (DDPG), which, however, does not offer satisfying performance.

Traditional Internet routing is simple, scalable and robust, but cannot provide perfect QoS support due to the current completely distributed hop-by-hop routing architecture. Software defined networking (SDN) opens up the door to traffic engineering innovation and makes possible QoS routing with a broader picture of overall network resources. We further argue that SDN can provide more opportunity for the network users to make their own routing selections with network programmability. In this paper, we propose OpenMCR, a general framework for network users to make their own choice of routing given various requirements. OpenMCR provides routing subject to several additive QoS constraints, which is NP-hard when the number of constraints is two or more. By composing various necessary conditions with different path extension schemes, our platform can customize routing solutions for each network user based on their own requirements. Through experiments in an SDN emulated environment, we evaluate multiple aspects of OpenMCR, demonstrate its effectiveness compared with several baselines and validate our theoretical analysis.

Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is simultaneous routing along multiple paths. The use of Software-Defined Networking (SDN), with fine-grained forwarding rules and the limited forwarding table size of commodity switches, brings a new set of constraints and challenges. In this work, we consider the problem of routing demands with dependability in a software-defined ISP backbone. We propose splitting large demands over multiple paths to reduce fragmentation and achieve service reliability under failures. We also minimize the delay differential among these paths to reduce the number of out-of-order packets. Finally, our routing algorithm works with forwarding tables of bounded size, commonly required by low-cost SDN switches. We report emulation and simulation results confirming the practicality of our solutions.

Saving power on base stations (BSs) becomes a critical issue in wireless cellular networks. Many existing work has proposed to schedule BS into sleep to save energy. However, in reality, it is very difficult to shut down and reboot BSs frequently due to numerous technical issues and performance requirements. In this paper, we propose a much more practical solution and offer a new perspective on implementing green wireless networking by embracing the hot-trended small cell network idea. Instead of putting BSs into sleep, we tactically reduce the coverage (and the power usage) of each BS, and strategically place microcells (relay stations) to offload the traffic transmitted to/from BSs in order to save total power consumption. We propose approximation algorithms for various network design scenarios, with different wireless network setups and different power saving optimization objectives. Extensive numerical results are presented to confirm our theoretical analysis.

Inspired by the success of use of Virtual Machines (VMs) in cloud computing, virtualization has been introduced to wireless networking recently, enabling support for multiple Mobile Virtual Network Operators (MVNOs) via isolated slices over a shared wireless substrate. In this paper, we present design, implementation and evaluation of a novel cloud framework, R-Cloud, to enable radio resources at Base Stations (BSs) to be effectively allocated to multiple MVNOs as a service, which is referred to as Radio-as-a-Service (RaaS). R-Cloud employs a hybrid two-level control framework to enable coarse-grained and fine-grained resource allocation at the cloud and BS levels respectively. Specifically, R-Cloud not only coordinates resource allocation among BSs, MVNOs and mobile users across a Radio Access Network (RAN) and enables performance isolation by optimizing resource sharing and user association using an LP-rounding based algorithm at the cloud level; but also effectively schedule transmissions among multiple users at a BS using an optimal scheduling policy. We implemented R-Cloud over a wireless network testbed with software defined radios. It has been shown by extensive experimental and simulation results that R-Cloud can achieve effective RaaS over wireless networks and the proposed resource allocation algorithms outperform widely-used baseline solutions.

Device-to-device (D2D) communication has emerged as a promising technique for improving capacity and reducing power consumption in wireless networks. Most existing works on D2D communications either targeted CDMA-based single-channel networks or aimed at maximizing network throughput. In this paper, we, however, aim to enable green D2D communications in OFDMA-based wireless networks. We formally define an optimization problem based on a practical link data rate model, whose objective is to minimize total power consumption while meeting user data rate requirements. We propose solving it using a joint optimization approach by presenting two effective and efficient algorithms, which both jointly determines mode selection, channel allocation and power assignment. It has been shown by extensive simulation results that the proposed algorithms can achieve over 68% power savings, compared to several baseline methods.

In this paper, we study a Virtual Server Provisioning and Selection (VSPS) problem in distributed Data Centers (DCs) with the objective of minimizing the total operational cost while meeting the service response time requirement.We aim to develop general algorithms for the VSPS problem without assuming a particular queueing model for service processing in each DC. First, we present a Mixed Integer Linear Programming (MILP) formulation. Then we present a 3-step optimization framework, under which we develop a polynomial-time ln(N)-approximation algorithm (where N is the number of clients) along with a post-optimization procedure for performance improvement. We also show this problem is NP-hard to approximate and is not possible to obtain a better approximation ratio unless NP has TIME(nO(log log n)) deterministic time algorithms. In addition, we present an effective heuristic algorithm that jointly obtains the VS provisioning and selection solutions. Extensive simulation results are presented to justify effectiveness of the proposed algorithms.

With the exploding popularity of wireless communication, the radio spectrum has become a scarce commodity. To further improve the network capacity, various solutions have been proposed to increase spectrum efficiency and network throughput. Small cell network is one of these new trends for next generation mobile network design. One model is using relay stations (RS) as small cell providers to achieve extended coverage, lower cost, and higher network capacity. Considering multiple related physical constraints such as channel capacity, signal to noise ratio (SNR) requirement of subscribers, relay power and network topology, this paper studies a joint signal-aware RS placement and power allocation problem with multiple base stations in wireless relay networks. We presented approximation schemes which first find a minimum number of RS, using maximum transmission power, to cover all the subscribers meeting each SNR requirement, and then ensure communications between any subscriber to a base station by adjusting the transmission power of each RS. Numerical results are presented to confirm the theoretical analysis of our schemes, and to show strong performances of our solutions.

Device-to-Device (D2D) communication has emerged as a promising technique for improving capacity and reducing power consumption in wireless networks. Most existing works on D2D communications either targeted CDMA-based single-channel networks or aimed to maximize network throughput. In this paper, we, however, aim at enabling green D2D communications in OFDMA-based wireless networks. We formally define an optimization problem based on a practical link data rate model, whose objective is to minimize power consumption while meeting user data rate requirements. We then present an effective algorithm to solve it in polynomial time, which jointly determines mode selection, channel allocation and power assignment. It has been shown by extensive simulation results that the proposed algorithm can achieve over 57% power savings, compared to several baseline methods.

Saving power on base stations (BS) becomes a critical issue in wireless cellular networks. Many existing work has proposed to schedule BS into sleep to save energy. However, in reality, it is very difficult to shut down and reboot BSs frequently due to numerous technical issues and performance requirements. In this work, we propose a much more practical solution and offer a new perspective on implementing Green Wireless Networking by embracing the hot-trended small cell network idea. Instead of putting BSs into sleep, we tactically reduce the coverage (and the power usage) of each BS, and strategically place microcells (relay stations) to offload the traffic transmitted to/from BSs in order to save total power consumption. We propose approximation algorithms for various network design scenarios, with different wireless network setups and different power saving optimization objectives. Extensive numerical results are presented to confirm our theoretical analysis.

The growth of laptops, personal digital assistant (PDA) and 802.11/Wi-Fi wireless networking made mobile ad-hoc network (MANET) a popular research topic recently. However, the flexible deployment nature and the lack of fixed infrastructure make MANETs suffer from a variety of security attacks. We, in this paper, discuss the Misleading Routing Attack (MIRA) in Mobile Ad-hoc Networks and propose a mitigation scheme using a dynamic one-way hash chain to form a path signature to sign the path, thus allowing the nodes on the path to detect any unexpected changes occur in the path. Our simulation results show that by applying our path signature mitigation scheme, we can improve the network performance under MIRA attack in terms of packets transmission/retransmission in the network.

Small cell network is the new trend for next generation mobile network design. One feasible model is using Relay stations (RS) as small cell providers to achieve extended coverage, lower cost, and higher network capacity. This paper studies Signal-aware relay station placement and power allocation problem in wireless relay networks with multiple base stations in the field. This problem consists of both subscriber coverage problem and relay power optimization problem, which have not been extensively studied together in previous works. This work takes into account physical constraints such as channel capacity, signal to noise ratio (SNR) requirement of subscribers, relay power cost and network topology. We set up a two-step goal that is firstly to find minimum number of RS in order to cover all the subscribers meeting each SNR requirement, and then to ensure communications built between any subscriber to a base station. In order to ensure each subscriber's SNR, transmission power of each RS should be adjustable. Thus, minimizing power cost of RSs is our goal in the second step. We divide the problem into two sub-problems, Lower-tier Coverage Relay Allocation (LCRA) problem and Upper-tier Connectivity Relay Allocation (UCRA) problem. For the LCRA problem, we present two approximation solutions based on minimum hitting set and maximum independent set. For the UCRA problem, an approximation algorithm and an optimal algorithm are proposed. At the end, an approximation solution for our original problem, which combines the approaches of the two sub-problems, is provided. Numerical results are presented to confirm the theoretical analysis of our schemes, and to show strong performances of our solutions.

With wireless resource virtualization, multiple Mobile Virtual Network Operators (MVNOs) can be supported over a shared physical wireless network and traffic loads in a Base Station (BS) can be easily migrated to more power-efficient BSs in its neighborhood such that idle BSs can be turned off or put into sleep to save power. In this paper, we propose to leverage load migration and BS consolidation for green communications and consider a power-efficient network planning problem in virtualized Cognitive Radio Networks (CRNs) with the objective of minimizing total power consumption while meeting traffic load demand of each MVNO. First, we present a Mixed Integer Linear Programming (MILP) to provide optimal solutions. Then we present a general optimization framework to guide algorithm design, which solves two subproblems, channel assignment and load allocation, in sequence. For channel assignment, we present a (Δ1)-approximation algorithm (where Δ is the maximum number of BSs a BS can potentially interfere with). For load allocation, we present a polynomial-time optimal algorithm for a special case where BSs are power-proportional as well as two effective heuristic algorithms for the general case. In addition, we present an effective heuristic algorithm that jointly solves the two subproblems. It has been shown by extensive simulation results that the proposed algorithms produce close-to-optimal solutions, and moreover, achieve over 45% power savings compared to a baseline algorithm that does not migrate loads or consolidate BSs.

In this paper, we propose a service-aware approach to enhance survivability in virtualized data centers. The idea is to create and maintain a Survivable Virtual Infrastructure (SVI) for each service or tenant, which includes Virtual Machines (VMs) hosting the corresponding application and their backup VMs. A fundamental problem is to determine how to map each SVI to a data center network with minimum operational costs while satisfying each VM's resource requirements and bandwidth demands between VMs before and after failures. This problem can be naturally divided into two subproblems: VM Placement (VMP) and Virtual Link Mapping (VLM). We first present a general optimization framework. Then we propose an efficient algorithm for VMP, and a polynomial-time optimal algorithm for VLM, which can be used as subroutines in the framework. We also present an effective heuristic algorithm that jointly solves two subproblems. It has been shown by extensive simulation results based on the real VM workload traces collected from Syracuse University's green data center that compared to the First Fit Decreasing (FFD) and shortest path routing based baseline algorithm, the proposed algorithms significantly reduce the reserved bandwidth, and yield comparable results in terms of the number of active servers. \begin{keywords}Cloud Computing, Data Center, Service-aware, Survivability, Virtual Machine Management. \end{keywords}

ABSTRACT Mobile ad‐hoc networks (MANETs) have attracted significant research attention recently because of the fast growth of laptops, personal digital assistant, and 802.11/Wi‐Fi wireless networking. However, the flexible deployment nature and the lack of fixed infrastructure make MANETs suffer from a variety of security attacks. In this paper, we show how an adversary can utilize a colluding injected attack (CIA) in MANET by injecting malicious nodes in the network, while hiding their identities from other legitimate nodes. These injected nodeswill work together(colluding) to create a collision at an arbitrary node, thus preventing it from receiving or relaying any packet. Because of this collision, a legitimate node could be reported as malicious nodes by monitoring nodes in the neighborhood. In this work, we propose a monitoring verification scheme to mitigate the effect of the CIA attack. Our proposed scheme is able to accurately detect malicious nodes in the network compared with previous detection schemes. Through simulations, we show that our proposed scheme outperforms previous detection schemes in terms of true/false detection of any malicious behavior in the network caused by the CIA attack. Copyright © 2013 John Wiley & Sons, Ltd.

In a virtualized data center, survivability can be enhanced by creating redundant Virtual Machines (VMs) as backup for VMs such that after VM or server failures, affected services can be quickly switched over to backup VMs. To enable flexible and efficient resource management, we propose to use a service-aware approach in which multiple correlated VMs and their backups are grouped together to form a Survivable Virtual Infrastructure (SVI) for a service or a tenant. A fundamental problem in such a system is to determine how to map each SVI to a physical data center network such that operational costs are minimized subject to the constraints that each VM's resource requirements are met and bandwidth demands between VMs can be guaranteed before and after failures. This problem can be naturally divided into two sub-problems: VM Placement(VMP) and Virtual Link Mapping (VLM). We present a general optimization framework for this mapping problem. Then we present an efficient algorithm for the VMP sub problem as well as a polynomial-time algorithm that optimally solves the VLM sub problem, which can be used as subroutines in the framework. We also present an effective heuristic algorithm that jointly solves the two sub problems. It has been shown by extensive simulation results based on the real VM data traces collected from the green data center at Syracuse University that compared with the First Fit Descending (FFD) and single shortest path based baseline algorithm, both our VMP+VLM algorithm and joint algorithm significantly reduce the reserved bandwidth, and yield comparable results in terms of the number of active servers.

Reliability and energy efficiency are critical issues in wireless sensor networks. In this work, we study Delay-bounded Energy-constrained Adaptive Routing (DEAR) problem with reliability, differential delay, and transmission energy consumption constraints in wireless sensor networks. We aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple paths. This flexibility enabled by a multi-path routing scheme has the tradeoff of differential delay among the different paths. This requires increased memory in the base station to buffer the traffic until the data arrives on all the paths. Therefore, differential delay between the multiple paths should be bounded in a range to reduce additional hardware cost in the base station. Moreover, the energy consumption constraint should also be satisfied when transmitting packets among multiple paths. We present a pseudo-polynomial time solution to solve a special case of DEAR, representing edge delays as integers. Next, an (1+α)-approximation algorithm is proposed to solve the optimization version of the DEAR problem. An efficient heuristic is provided for the DEAR problem. We present numerical results confirming the advantage of our schemes as the first solution for the DEAR problem.

Mobile phones with a rich set of embedded sensors enable sensing applications in various domains. In this paper, we propose to leverage cloud-assisted collaborative sensing to reduce sensing energy consumption for mobile phone sensing applications. We formally define a minimum energy sensing scheduling problem and present a polynomial-time algorithm to obtain optimal solutions, which can be used to show energy savings that can potentially be achieved by using collaborative sensing in mobile phone sensing applications, and can also serve as a benchmark for performance evaluation. We also address individual energy consumption and fairness by presenting an algorithm to find fair energy-efficient sensing schedules. Under realistic assumptions, we present two practical and effective heuristic algorithms to find energy-efficient sensing schedules. It has been shown by simulation results based on real energy consumption (measured by the Monsoon power monitor) and location (collected from the Google Map) data that collaborative sensing significantly reduces energy consumption compared to a traditional approach without collaborations, and the proposed heuristic algorithm performs well in terms of both total energy consumption and fairness.

ABSTRACT The p‐cycle design problem has been extensively studied because it can provide both ring‐like fast self‐protection speed and spare capacity efficiency of path protection scheme. However, p‐cycle provisioning for dynamic traffic has not been fully addressed. Most related works have not considered link capacity in the construction of p‐cycles, which may cause problems in practice because the protection paths may not have enough backup bandwidth. In this paper, with the consideration of link capacity, we present a sufficient and necessary condition that guarantees p‐cycles for providing enough protection bandwidth. Based on this condition, we propose an effective solution to provide connections for dynamic requests with the property that each link used for a connection is protected by a p‐cycle. Simulation results show that our dynamic p‐cycle provisioning solution outperforms the traditional path protection scheme. Copyright © 2011 John Wiley & Sons, Ltd.

The growth of laptops, personal digital assistant (PDA) and 802.11/Wi-Fi wireless networking have made mobile ad-hoc network (MANET) a popular research topic recently. Due to the flexible deployment nature and the lack of fixed infrastructure, MANETs suffer from varieties of security attacks. In this paper, we propose the misleading routing attack (MIRA), which is different from the well known gray/black hole attacks, in which a node is relaying the coming packets and not dropping them. MIRA attack aims to delay the packet as much as possible so as to let the source node time out before it receives the acknowledgment. Also it aims to overload the network by increasing the number of unexpected routing packets generated in the network. Our simulation results show that the existence of an adversary in the network launching a misleading routing attack will degrade packet transmissions in the network and increasing the number of lost packets as well as the retransmissions at the sender.

The emerging WiMAX technology (IEEE 802.16) is a fourth generation standard for low-cost, high-speed and long range wireless communications for a large variety of civilian and military applications. IEEE 802.16j has introduced the concept of mesh network model and a special type of node called Relay Station (RS) for traffic relay for Subscriber Stations (SSs). A WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-Of-Sight (NLOS) communications. This paper studies a Multi-hop FAir Scheduling for Throughput Optimization (MFASTO) problem in WiMAX mesh networks. The goal here is to maximize the minimum satisfaction ratio among all the SSs. In order to solve the MFASTO problem, an ILP formulation and an efficient heuristic algorithm are proposed in this work. Simulation results are presented to justify the performance and efficiency of our proposed solutions.

Wireless mesh network (WMN) is a rapid deployed, self organized and multi-hop wireless network. The wireless and distributed natures of WMNs make them subject to various kinds of attacks, which raise a great challenge in securing these networks. Most existing security mechanisms are based on cryptographic keys where a high degree key management services are in demand. In this paper, we present an effective key management scheme which seeks an encryption key assignment such that the induced network is connected and well protected against potential eavesdropping attacks. Compared with previous work, our scheme assigns the available encryption keys among all the nodes in the network. The simulation results show that our scheme out performs previous schemes through providing a network that is resistant against malicious eavesdropping attack.

Recently, the sensor worm attack has been identified to be one of the serious threats to the wireless sensor networks. However, sensor nodes do not have complicated hardware architectures or operating systems to protect program safety. Sensor worms can exploit the vulnerabilities of sensor nodes, such as the vulnerability of the buffer-overflow. In this paper, we utilize a software diversity approach to defend the sensor worm attacks. A Worm Attack DEfence (WADE) problem, which is to minimize the total number of defective edges with limited software versions, is defined in this paper. To solve the WADE problem, we present a role-base graph coloring scheme. Simulation results illustrate the efficiency and efficacy of our approach.

The emerging WiMAX technology (IEEE 802.16) is the fourth generation standard for low-cost, high-speed and long-range wireless communications for a large variety of civilian and military applications. IEEE 802.16j has introduced the concept of mesh network model and a special type of node called Relay Station (RS) for traffic relay for Subscriber Stations (SSs). A WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-Of-Sight (NLOS) communications. This paper studies a Distance-Aware Relay Placement (DARP) problem in WiMAX mesh networks, which considers a more realistic model that takes into account physical constraints such as channel capacity, signal strength and network topology, which were largely ignored in previous studies. The goal here is to deploy the minimum number of RSs to meet system requirements such as user data rate requests, signal quality and network topology. We divide the DARP problem into two sub-problems, LOwer-tier Relay Coverage (LORC) Problem and Minimum Upper-tier Steiner Tree (MUST) Problem. For LORC problem, we present two approximation algorithms based on independent set and hitting set, respectively. For MUST problem, an efficient approximation algorithm is provided and proved. Then, an approximation solution for DARP is proposed and proved which combines the solutions of the two sub-problems. We also present numerical results confirming the theoretical analysis of our schemes as the first solution for the DARP problem.

Relay stations can be deployed in a wireless network to extend its coverage and improve its capacity. In this paper, we study a scheduling problem in OFDMA-based wireless relay networks with consideration for multi-user diversity, channel diversity and spatial reuse. First, we present a Mixed Integer Linear Programming (MILP) formulation to provide optimum solutions. It has been shown by previous research that performance of a wireless scheduling algorithm is usually related to the interference degree delta, which is the maximum number of links that interfere with a common link but do not interfere with each other. Therefore, we then show that the interference degree delta is at most 4 for any 2-hop relay network and 14 for any general h-hop (h >; 1) relay network. Furthermore, we present a simple greedy algorithm for the scheduling problem and show it has an approximation ratio of 1/(1+δ), which leads to an approximation ratio of 1/5 for the 2-hop case and 1/15} for the general case. In addition, we present three heuristic algorithms, namely, the weighted degree greedy algorithm, the Maximum Weighted Independent Set (MWIS) algorithm and the Linear Programming (LP) rounding algorithm, to solve the scheduling problem. Extensive simulation results have showed that the LP rounding algorithm performs best and always provides close-to-optimum solutions. The performance of the simple greedy algorithm is comparable to that of the other algorithms.

The performance of wireless networks can be significantly improved by multi-channel communications compared with single-channel communications since the use of multiple channels can reduce interference influence. In this paper, we study interference-aware topology control in IEEE 802.11-based multichannel wireless mesh networks with dynamic traffic. Channel assignment is one of the most basic and important issues in such networks. Different channel assignments can lead to different network topologies. Based on a novel definition of co-channel interference, we formally define and present an effective heuristic for the minimum interference robust topology design problem which seeks a channel assignment for the given network such that the induced network topology is 2-connected and has minimum network interference.

Interference has been proven to have an effect on the performance in wireless mesh networks (WMN). Using multichannels can improve the performance of WMNs by reducing interference influence. In this paper, we study how to design a robust WMN for a set of mesh nodes, each with Q Networking Interface Cards (NICs) and pre-defined connection requests. Our scheme aims to construct an interference-aware network topology for the nodes, then set up a pair of link-disjoint paths for each request with fault- tolerant capability. We propose two novel schemes to improve the network design. First, we embrace the network interference for providing resource- efficient protections. Second, protection links are shared and reused by multiple connections for protection, which further improves the efficiency of network resource usage. Our simulation results show that our scheme outperformed previous schemes.

Wireless Mesh Networks represent a promising technology to provide wireless Internet connectivity over a large community. This new technology not only allows a fast, easy and inexpensive network deployment, but also enables many new applications including community-scale peer-based communication or sharing of network resources and services. In this work, we propose an effective publish/subscribe communication paradigm to facilitate efficient data dissemination over wireless mesh networks. The proposed publish/subscribe scheme dynamically routes and delivers events and services from sources to interested users with minimum communication overhead and memory storage. The effectiveness of the system is demonstrated through comprehensive simulation studies.

Wireless communications over water may suffer from serious multipath fading due to strong specular reflections from conducting water surfaces. Cognitive radios enable dynamic spectrum access over a large frequency range, which can be used to mitigate this problem. In this paper, we study how to leverage cognitive radios for effective communications in wireless networks over water. We formally define the studied problem as the OVErwater Radio-Time Scheduling (OVERTS) problem which seeks a radio channel with time schedule such that the total of assigned eligible time slots, in which a " good " communication link is maintained between every Mobile Station (MS) and the Base Station (BS), satisfies the time slots requirement of each MS. Two effective heuristic algorithms are presented for the OVERTS problem. Simulation results are presented to justify the performance and efficiency of our proposed scheduling algorithms.

Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is the simultaneous routing along multiple disjoint paths. Most previous protection and restoration schemes were designed for all-or-nothing protection and thus, an overkill for data traffic. In this work, we study the Reliable Adaptive Multipath Provisioning (RAMP) problem with reliability and differential delay constraints. We aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple (not necessary disjoint) paths, allowing the whole network to carry sufficient traffic even when link/node failure occurs. The flexibility enabled by a multipath scheme has the tradeoff of differential delay among the diversely routed paths. This requires increased memory in the destination node in order to buffer the traffic until the data arrives on all the paths. Increased buffer size will raise the network element cost and could cause buffer overflow and data corruption. Therefore, differential delay between the multiple paths should be bounded by containing the delay of a path in a range. We first prove that RAMP is an NP-hard problem. Then we present a pseudo-polynomial time solution to solve a special case of RAMP, representing edge delays as integers. Next, an (1 + e)-approximation algorithm is proposed to solve the optimization version of the RAMP problem. An efficient heuristic is also provided for the RAMP problem. We also present numerical results confirming the advantage of our schemes as the first solution for the RAMP problem.

Wireless communications over water may suffer from serious multipath fading due to strong specular reflections from conducting water surfaces. Cognitive radios enable dynamic spectrum access over a large frequency range, which can be used to mitigate this problem. In this paper, we study how to leverage cognitive radios for effective communications in wireless networks over water. We formally define the related problem as the Overwater Channel Scheduling Problem (OCSP) which seeks a channel assignment schedule such that a "good" communication link can be maintained between every Mobile Station (MS) and the Base Station (BS) all the time. We present a general scheduling framework for solving the OCSP. Based on the proposed framework, we present an optimal algorithm and several fast heuristic algorithms. In addition, we discuss an extension to the heavy traffic load case and propose two throughput-aware scheduling algorithms. We performed simulation runs based on path loss data provided by the Advanced Refractive Effects Prediction System (AREPS) and present simulation results to justify the efficiency of the proposed scheduling algorithms.

Most research works in routing and design of optical networks assume that the optical medium can carry data signals without any bit error. However, physical impairments of the optical signal introduced by optical fibers and components, e.g., power loss, noise, and dispersions, impose fundamental constraints in WDM networks, and must be taken into consideration in the routing and design problems of WDM networks. Only through 3R (optical-electrical-optical) regeneration (reamplification, reshaping, retiming) with OEO conversion can a lightpath be recovered from those impairments. Because 3R regenerators are costly devices and the OEO conversion can affect the efficiency of optical networks we need to use the regenerators efficiently and effectively. In this paper, we study the problem of placing the minimum number of regenerators to accommodate all requests with the consideration of physical impairments. We first propose a novel ILP formulation for an optimal solution and a benchmark for this problem. We then provide an effective heuristic for large-sized WDM networks. Simulation results show that our schemes have good performance in terms of network design and running time.

The barrier coverage model was proposed for applications in which sensors are deployed for intrusion detection. In this paper, we study a strong barrier coverage problem in wireless sensor networks with directional sensors. First, we introduce the directional coverage graph to model barrier coverage with directional sensors. Based on this graph model, we present an integer linear programming formulation for the barrier coverage problem, which can be used to provide optimal solutions. Moreover, we present efficient centralized algorithms and a distributed algorithm to solve the problem. It has been shown by simulation results that the proposed algorithms provide close-to-optimal solutions and consistently outperform a simple greedy algorithm.

Most research works in routing and design of optical networks assume that the optical medium can carry signals without any bit error. However, the physical impairments on the optical signal quality introduced by optical components, such as erbium-doped fiber amplifiers (EDFA) and optical cross connects (OXCs), must be considered in the routing and design problems of WDM networks in practice. In this paper, we studied the dynamic connection provisioning problem in WDM networks under multiple signal quality constraints. We present a polynomial time optimal algorithm that finds an active path for an incoming connection request with minimum network resource consumption. Simulation results show that our solution outperforms the previously best solution to the problem.

In a wireless network (WN), the wireless devices generally localize themselves with the help of anchors that are pre-deployed in the network. Some of the techniques commonly used for localization are time of arrival (ToA), time difference of arrival (TDoA), angle of arrival (AoA), and time of flight (ToF). In the wireless domain, measurements are susceptible to errors resulting from the nature of the medium, the relatively low precision, and the presence of obstacles, which produce non-line of sight (NLOS) errors. The NLOS errors are a major concern as they could result in significant degradation in accuracy. In this paper, we propose an efficient technique that uses the distance estimates of the device from a group of anchors to localize the device with better accuracy in the presence of NLOS errors. Our technique is based on the notion that in general, for any estimate, the proportion of the NLOS error can be upper bounded. Using this upper bound information our technique reduces the uncertainty in the position of the wireless device that is being localized. The technique is distributed and is simple. In comparison to the standard localization procedure, where localization is done independent of the presence of NLOS errors, our technique uses the information about the NLOS error bounds to improve the accuracy of estimation. Simulation results show that our technique reduces the position error of the wireless device by 40% on an average and by at least 80% in the best case. The uncertainty in localization is also reduced significantly.

A fundamental problem in quality-of-service (QoS) routing is to find a path connecting a source node to a destination node that satisfies K ges 2 additive QoS constraints. This multi-constrained path problem (MCP) is known to be NP-complete. In a recent paper, Xue et at. showed that the shortest path with respect to a single auxiliary edge weight (obtained by combining the K edge weights into a single metric) is a if-approximation to MCP, in the sense thatthelargestratioofpathweightoveritscorrespondingconstraintis within a factor of K from minimum. In this paper, we present a simple greedy algorithm and prove that this greedy algorithm is also a if-approximation algorithm to MCP. Extensive computational results show that this greedy algorithm is superior to the previously best known if-approximation algorithm in terms of the quality of the path computed. Our algorithm is as simple as Dijkstra's shortest path algorithm, and is therefore suitable for implementation in Internet protocols.

Two fundamental functions of the sensor nodes in a wireless sensor network are to sense its environment and to transmit sensed information to a basestation. One approach to prolong sensor network lifetime is to deploy some relay nodes whose main function is to communicate with the sensor nodes, other relay nodes, and the basestations. It is desirable to deploy a minimum number of relay nodes to achieve certain connectivity requirement. In this paper, we study four related fault-tolerant relay node placement problems, each of which has been previously studied only in some restricted form. For each of them, we discuss its computational complexity and present a polynomial time O(1)-approximation algorithm with a small approximation ratio. When the problem reduces to a previously studied form, our algorithm either improves the previous best algorithm or reduces to the previous best algorithm.

In this paper, we study joint rate control, routing and scheduling in multi-channel wireless mesh networks (WMNs), which are traditionally known as transport layer, network layer and MAC layer issues respectively. Our objective is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions such that the network throughput is maximized, which is formally defined as the maximum throughput rate allocation (MRA) problem. As simple throughput maximization may result in a severe bias on rate allocation, we take account of fairness based on a simplified max-min fairness model and the proportional fairness models. We define the max-min guaranteed maximum throughput rate allocation (MMRA) problem and proportional fair rate allocation (PRA) problem. We present efficient linear programming (LP) and convex programming (CP) based schemes to solve these problems. Numerical results show that proportional fair rate allocation schemes achieves a good tradeoff between throughput and fairness.

Wireless mesh network is designed as an economical solution for last-mile broadband Internet access. In this paper, we study bandwidth allocation in multi-channel multihop wireless mesh networks. Our optimization goals are to maximize the network throughput and, at the same time, to enhance fairness. First, we formulate and present an Linear Programming (LP) formulation to solve the Maximum throughput Bandwidth Allocation (MBA) problem. However, simply maximizing the throughput may lead to a severe bias on bandwidth allocation among wireless mesh nodes. In order to achieve a good tradeoff between fairness and throughput, we consider a simple max-min fairness model which leads to high throughput solutions with guaranteed maximum minimum bandwidth allocation values, and the well-known Lexicographical Max-Min (LMM) model. Correspondingly, we formulate the Max-min guaranteed Maximum throughput Bandwidth Allocation (MMBA) problem and the Lexicographical Max-Min Bandwidth Allocation (LMMBA) problem. For the former one, we present an LP formulation to provide optimal solutions and for the later one, we propose a polynomial time optimal algorithm.

In this paper, we study rate allocation for a set of end-to-end communication sessions in multi-radio wireless mesh networks. We propose cross-layer schemes which can jointly solve rate allocation, channel assignment, routing, scheduling and power control problems in multiple layers. Specifically, a Linear Programming (LP) based scheme is presented to compute end-to-end rate allocation with the goal of maximizing network throughput. As simple throughput maximization may lead to a severe bias on rate allocation, we take fairness into consideration based on a parameter named Demand Satisfaction Factor (DSF), and two fairness models, a simplified max-min fairness model and the well-known proportional fairness model. We propose LP-based and Convex Programming (CP) based schemes to compute fair end-to-end rate allocation. Our schemes can provide upper bounds on achievable network throughput and max-min DSF values. Numerical results show that our proportional fair rate allocation scheme achieves a good tradeoff between throughput and fairness.

Routing and wavelength assignment (RWA) aims to assign the limited number of wavelengths in a wavelength-division multiplexed (WDM) optical network so as to achieve greater capacity. In a recent paper, Datta et al. studied the problem of establishing a set of disjoint lightpaths on a tree topology using a single wavelength to maximize the total traffic supported by the chosen set of lightpaths. They discussed applications of this problem to RWA and presented a dynamic programming algorithm which optimally solves this problem in /spl Oscr/(n/sup 4/+n/spl Dscr//sup 3/) time, where n is the number of nodes in the network and /spl Dscr/ is the maximum node degree. In this paper, we present an improved algorithm with a time complexity of /spl Oscr/(n/sup 2/+n/spl Dscr//sup 2/).

Network motifs have been demonstrated to be the building blocks in many biological networks such as transcriptional regulatory networks. Finding network motifs plays a key role in understanding system level functions and design principles of molecular interactions. In this paper, we present a novel definition of the neighborhood of a node. Based on this concept, we formally define and present an effective algorithm for finding network motifs. The method seeks a neighborhood assignment for each node such that the induced neighborhoods are partitioned with no overlap. We then present a parallel algorithm to find network motifs using a parallel cluster. The algorithm is applied on an E. coli transcriptional regulatory network to find motifs with size up to six. Compared with previous algorithms, our algorithm performs better in terms of running time and precision. Based on the motifs that are found in the network, we further analyze the topology and coverage of the motifs. The results suggest that a small number of key motifs can form the motifs of a bigger size. Also, some motifs exhibit a correlation with complex functions. This study presents a framework for detecting the most significant recurring subgraph patterns in transcriptional regulatory networks.

In this paper, we study dynamic light trail routing in a WDM optical network. We present an efficient algorithm for establishing a light trail routing for a new connection request, while using minimum network resources. We also study survivable routing using light trail technology. We present an efficient heuristic for computing a pair of working and protection light trails for a given connection request. Simulation results are presented which demonstrate the advantages of our routing schemes.

Broadcasting and multicasting packets in a power efficient way is a critical task in wireless ad hoc networks. In a recent paper Li et al., (2004) study the minimum energy broadcast (MEB) routing problem in a wireless ad hoc network where every node has an omni-directional antenna and a fixed transmission power level. We extend their work to wireless networks with directional antennas in this paper. We formulate the minimum power multicasting/broadcasting using directional antennas (PMDA/PBDA) problems. For each problem, we present an approximation algorithm with worst- case approximation ratio O(log/sup 2/n), where n is the number of nodes in the network. We also present several effective heuristics to solve the problems, the shortest path tree (SPT) heuristic, the directed minimum spanning tree (DMST) heuristic and a greedy heuristic. Simulation results are presented to show the performance of our algorithms.

As a generalization of the traditional path protection scheme in WDM networks where a backup path is needed for each active path, the partial path protection scheme uses a collection of backup paths to protect an active path, where each backup path in the collection protects one or more links on the active path such that every link on the active path is protected by one of the backup paths. While there is no known polynomial time algorithm for computing an active path and a corresponding backup path using the path protection scheme for a source-destination node pair, we show that an active path and a corresponding collection of backup paths using the partial path protection scheme can be computed in polynomial time, whenever they exist, under each of the following two network models: (a) dedicated protection in WDM networks without wavelength converters; and (b) shared protection in WDM networks without wavelength converters. Under each of the two models, we prove, that for any given source s and destination d in the network, if one candidate active path connecting s and d is protectable using partial path protection, then any candidate active path connecting s and d is also protectable using partial path protection. This fundamental property leads to efficient shortest active path algorithms that can find an active path and its corresponding partial path protections whenever they exist. Simulation results show that shared partial path protection outperforms shared path protection in terms of blocking probability.

Recent research has shown that interference can make a significant impact on the performance of multihop wireless networks. Researchers have studied interference-aware topology control recently [M. Burkhart et al., 2004]. In this paper, we study routing problems in a multihop wireless network using directional antennas with dynamic traffic. We present new definitions of link and path interference that are suitable for designing better routing algorithms. We then formulate and optimally solve two power constrained minimum interference single path routing problems. Routing along paths found by our interference-aware algorithms tends to have less channel collisions and higher network throughput. Our simulation results show that, compared with the minimum power path routing algorithm, our algorithms can reduce average path interference by 40% or more at the cost of a minor power increase. We also extend our work towards survivable routing by formulating and solving the power constrained minimum interference node-disjoint path routing problem.

Medard, Finn, Barry and Gallager proposed an elegant recovery scheme (known as the MFBG scheme) using redundant trees. Xue, Chen and Thulasiraman extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric of multifailure recovery capabilities for single failure recovery schemes. In this paper, we present three linear time algorithms for constructing redundant trees for single link failure recovery in 2-edge connected graphs and for single node failure recovery in 2-connected graphs. Our first algorithm aims at high QoP for single link recovery schemes in 2-edge connected graphs. The previous best algorithm has a running time of O(n/sup 2/(m+n)), where n and m are the number of nodes and links in the network. Our algorithm has a running time of O(m+n), with comparable performance. Our second algorithm aims at high QoS for single link recovery schemes in 2-edge connected graphs. Our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Our third algorithm aims at high QoS for single node recovery schemes in 2-connected graphs. Again, our algorithm improves the previous best algorithm with O(n/sup 2/(m+n)) time complexity to O(m+n) time complexity with comparable performance. Simulation results show that our new algorithms outperform previously known linear time algorithms significantly in terms of QoP or QoS, and outperform other known algorithms in terms of running time, with comparable QoP of QoS performance.

The throughput of wireless networks can be significantly improved by multi-channel communications compared with single-channel communications since the use of multiple channels can reduce interference influence. In this paper, we study interference-aware topology control and QoS routing in IEEE 802.11-based multi-channel wireless mesh networks with dynamic traffic. Channel assignment and routing are two basic issues in such networks. Different channel assignments can lead to different network topologies. We present a novel definition of co-channel interference. Based on this concept, we formally define and present an effective heuristic for the minimum INterference Survivable Topology Control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all K-connected topologies. We then formulate the Bandwidth-Aware Routing (BAR) problem for a given network topology, which seeks routes for QoS connection requests with bandwidth requirements. We present a polynomial time optimal algorithm to solve the BAR problem under the assumption that traffic demands are splittable. For the non-splittable case, we present a maximum bottleneck capacity path routing heuristic. Simulation results show that compared with the simple common channel assignment and shortest path routing approach, our scheme improves the system performance by 57% on average in terms of connection blocking ratio.

Throughput is an important performance consideration for multihop wireless networks. In this paper, we study the joint link scheduling and power control problem, focusing on maximizing the network throughput. We formulate the maximum throughput link scheduling with power control (MATH-SPC) problem, and present a mixed integer linear programming (MILP) formulation to provide optimal solutions. However, simply maximizing the throughput leads to a severe bias on bandwidth allocation among all links. In order to enhance both throughput and fairness, we define a new parameter, the demand satisfaction factor (DSF), to characterize the fairness of bandwidth allocation. We formulate the maximum throughput fair link scheduling with power control (MATA-SPC) problem and present an MILP formulation for this problem. We also present an effective polynomial time heuristic algorithm, namely, the serial LP rounding (SLPR) heuristic. Our numerical results show that bandwidth can be fairly allocated among all links/flows by solving our MATA-SPC formulation or using our heuristic algorithm at the cost of a minor reduction of network throughput.

Reliability is a major issue in mobile ad hoc routing. Shortest paths are usually used to route packets in mobile ad hoc networks (MANET) However, a shortest path may fail quickly, because some of the wireless links on the shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes can result in substantial data loss and communication overheads. We consider a MANET in the urban environment. We formulate and study two optimization problems related to reliable routing in MANET. In the minimum cost duration-bounded path (MCDBP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the maximum duration cost-bounded path (MDCBP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given constraint. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the duration prediction table. We also present an heuristic algorithm for the MDCBP routing problem. Our simulation results show that our mobility prediction based routing algorithms lead to better network throughput and longer average path duration, compared with the shortest path algorithm.