A distributed approximation algorithm for the bottleneck connected dominating set problem

Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication between the sensors. Connected dominating sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and to minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included.     

Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs

The strongly connected dominating and absorbing set (DAS) is used as a virtual backbone in heterogeneous wireless sensor. To reduce routing cost, we introduce a routing-cost constraint and study the problem of computing the minimum strongly connected DAS under routing-cost constraint. An approximation algorithm with guaranteed performance will be presented.     

On connected domination in unit ball graphs

Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.     

An approximation algorithm for the edge-dilation k-center problem

We provide an approximation algorithm for selecting centers in a complete graph so as to minimize the maximum ratio of the distance between any two nodes via their respective centers to their true graph distance. Placing centers under such an objective function is important in designing efficient communication networks which rely on hubs for routing.     

Heuristic algorithms for the multi-depot ring-star problem

In this paper, we consider the problem of designing urban optical networks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some transition points used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds and heuristic algorithms for the MDRSP. Computational results on randomly generated instances and real-life datasets are also presented.     

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(δ ² n), where δ is the maximum node degree in communication graph.     

Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs

A wireless MANET is a collection of wireless mobile hosts that dynamically create a temporary network without a fixed infrastructure. The topology of the network may change unpredictably and frequently. Therefore, multicast routing in ad hoc networks is a very challenging problem. This paper proposes a multi-constrained QoS multicast routing method using the genetic algorithm. The proposal will be flooding-limited using the available resources and minimum computation time in a dynamic environment. By selecting the appropriate values for parameters such as crossover, mutation, and population size, the genetic algorithm improves and tries to optimize the routes. Simulation results indicate its better performances compared to other methods.     

ATM network design for corporate networks

Asynchronous transfer mode (ATM) networks play an important role in support of distributed applications and modern corporate systems. The applications that use these architectures transfer high volumes of data in high-speed bursts and have stringent delay requirements. To address these needs, network managers seek cost efficient network solutions that provide network capacity sufficient to support high-speed applications.In this paper we present a new formulation and solution procedure for designing ATM networks to support corporate applications. Given the locations of the application servers and multiple clients we would like to design a minimum cost ATM network by which the clients can access the servers. Most of the previous work done in this area separates the problem into a routing problem (virtual circuit routing) and an assignment (virtual path assignment) problem. Thus, the solutions tend to be sub-optimal in the combined problem. This research optimizes virtual path (VP) assignment and virtual circuit (VC) routing simultaneously. We formulate the combined problem explicitly and develop an effective solution method. The solution method provides the designer with virtual paths and virtual circuits over which the actual communication takes place. Computational results are provided.     

Optimization architecture for joint multi-path routing and scheduling in wireless mesh networks

In Wireless Mesh Networks (WMN), the optimal routing of data depends on the link capacities which are determined by link scheduling. The optimal performance of the network, therefore, can only be achieved by joint routing and scheduling optimization. Although the joint single-path routing and scheduling optimization problem has been extensively studied, its multi-path counterpart within wireless mesh networks has not yet been fully investigated. In this paper, we present an optimization architecture for joint multi-path QoS routing and the underlying wireless link scheduling in wireless mesh networks. By employing the contention matrix to represent the wireless link interference, we formulate a utility maximization problem for the joint multi-path routing and MAC scheduling and resolve it using the primal–dual method. Since the multi-path routing usually results in the non-strict concavity of the primal objective function, we first introduce the Proximal Optimization Algorithm to get around such difficulty. We then propose an algorithm to solve the routing subproblem and the scheduling subproblem via the dual decomposition. Simulations demonstrate the efficiency and correctness of our algorithm.     

Neural and delay based heuristics for the Steiner problem in networks

High speed networks such as the B-ISDN must be adequately equipped to handle multipoint communication in a fast and economical manner. Multicast applications include desktop video conferencing, distance learning, distributed database applications, etc. In networks employing the asynchronous transfer mode (ATM) technology, routing a multicast is achieved by constructing a tree that spans the source and all the destinations. For the purpose of routing, the network is modeled as a weighted, undirected graph. The graph-theoretic solution is to find a minimum Steiner tree for the graph given a set of destinations. This formulation suffices for building multicast trees with a single optimization constraint as would be the xcase for best effort transport. For real-time traffic, however, it is necessary to ensure that the delay between the sender and each of the receivers is bounded. In this case the network is modeled as an undirected graph, where the edges have both a cost and a delay associated with them. The graph-theoretic solution is then to find a constrained minimum Steiner tree such that the delay between the source and each of the destinations does not violate the specified bound. Both of these problems are NP-complete. In this paper we review prior work on the multipoint routing problem and discuss the formulation of the unconstrained and constrained Steiner problems. We use the random neural network (RNN) to significantly improve the quality of trees found by the two existing best heuristics for finding Steiner trees - the minimum spanning tree heuristic and the average distance heuristic. We also develop a new heuristic for finding delay constrained Steiner trees. Experimental results are presented which show that the new heuristics improve significantly over existing ones.     

On connected dominating sets of restricted diameter

A connected dominating set (CDS) is commonly used to model a virtual backbone of a wireless network. To bound the distance that information must travel through the network, we explicitly restrict the diameter of a CDS to be no more than s leading to the concept of a dominating s-club. We prove that for any fixed positive integer s it is NP-complete to determine if a graph has a dominating s  -club, even when the graph has diameter s+1$s+1$. As a special case it is NP-complete to determine if a graph of diameter two has a dominating clique. We then propose a compact integer programming formulation for the related minimization problem, enhance the approach with variable fixing rules and valid inequalities, and present computational results.     

Modeling and optimization of energy efficient routing in wireless sensor networks

Wireless sensor networks (WSNs) have important applications in remote environmental monitoring and target tracking. The development of WSNs in recent years has been facilitated by the availability of sensors that are smaller, less expensive, and more intelligent. The design of a WSN depends significantly on its desired applications and must take into account factors such as the environment, the design objectives of the application, the associated costs, the necessary hardware, and any applicable system constraints. In this study, we propose mathematical models for a routing protocol (network design) under particular resource restrictions within a wireless sensor network. We consider two types of constraints: the distance between the linking sensors and the energy used by the sensors. The proposed models aim to identify energy-efficient paths that minimize the energy consumption of the network from the source sensor to the base station. The computational results show that the presented models can be used efficiently and applied to other network design contexts with resource restrictions (e.g., to multi-level supply chain networks).     

Coding and control for communication networks

The purpose of this paper is to survey techniques for constructing effective policies for controlling complex networks, and to extend these techniques to capture special features of wireless communication networks under different networking scenarios. Among the key questions addressed are:

1. The relationship between static network equilibria, and dynamic network control.
2. The effect of coding on control and delay through rate regions.
3. Routing, scheduling, and admission control.

Through several examples, ranging from multiple-access systems to network coded multicast, we demonstrate that the rate region for a coded communication network may be approximated by a simple polyhedral subset of a Euclidean space. The polyhedral structure of the rate region, determined by the coding, enables a powerful workload relaxation method that is used for addressing complexity—the relaxation technique provides approximations of a highly complex network by a far simpler one. These approximations are the basis of a specific formulation of an h-MaxWeight policy for network routing. Simulations show a 50% improvement in average delay performance as compared to methods used in current practice.     

Layouts for mobility management in wireless ATM networks

In this paper, we present a new model that combines quality of service and mobility aspects in wireless ATM networks. Namely, besides the hop count and load parameters of the basic ATM layouts, we introduce a new notion of distance that estimates the time needed to reconstruct the virtual channel of a wireless user when he moves through the network. Quality of service guarantee dictates that the rerouting phase must be imperceptible, that is, the maximum distance between two virtual channels must be maintained as low as possible. Therefore, a natural combinatorial problem arises in which suitable trade-offs must be determined between the different performance measures. We first show that establishing the existence of a layout with maximum hop count h, load l and distance d is NP-complete, even in the very restricted case h=2, l=1 and d=1. We then provide optimal layout constructions for basic interconnection networks, such as chains and rings.     

Optimal performance of parallel-server systems with job size prediction errors

Modern communication networks integrate distributed computing architectures, in which customers are processed in parallel. We show how to minimize the waiting time of customer's jobs by leveraging a simple threshold-based job dispatching policy. The optimal policy leverages the SITA routing, which assigns jobs to servers according to the size of the job. Moreover, the optimal policy permits to optimize system performance even when the job size is not known a priori and is estimated by means of error-prone predictors.     

互连网络的向量图模型

n-超立方体,环网,k元n超立方体,Star网络,煎饼(pancake)网络,冒泡排序(bubble sort)网络,对换树的Cayley图,De Bruijn图,Kautz图,Consecutive-d有向图,循环图以及有向环图等已被广泛的应用做处理机或通信互连网络.这些网络的性能通常通过它们的度,直径,连通度,hamiltonian性,容错度以及路由选择算法等来度量.在本文中,首先,我们提出了有向向量图和向量图的概念;其次,我们开发了有向向量图模型和向量图模型来更好地设计,分析,改良互连网络;我们进一步证明了上述各类著名互连网络都可表示为有向向量图模型或向量图模型;更重要的是该模型能够使我们设计出了新的互连网络---双星网络和三角形网络.     

A model for the capacitated,hop-constrained,per-packet wireless mesh network design problem

Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.     

Multi-period traffic routing in satellite networks

We introduce a traffic routing problem over an extended planning horizon that appears in geosynchronous satellite networks. Unlike terrestrial (e.g., fiber optic) networks, routing on a satellite network is not transparent to the customers. As a result, a route change is associated with significant monetary penalties that are usually in the form of discounts (up to 40%) offered by the satellite provider to the customer that is affected. The notion of these rerouting penalties requires the network planners to explicitly consider these penalties in their routing decisions over multiple time periods and introduces novel challenges that have not been considered previously in the literature. We develop a branch-and-price-and-cut procedure to solve this problem and describe an algorithm for the associated pricing problem. Our computational work demonstrates that the use of a multi-period optimization procedure as opposed to a myopic period-by-period approach can result in cost reductions up to 13% depending on problem characteristics and network size considered. These cost reductions correspond to potential savings of several hundred million dollars for large satellite providers.     

马氏模型下移动自组网随选型路由协议特性分析

移动自组网络（简称MANET）因其移动性及无基础设施支持等特点已经成为无线通信网络中的热门问题．通过将一个MANET网络中每条链边的长度看作一个生灭过程,并且假设在泛洪过程中空间可以复用n次,建立了移动自组网络空间可复用的马氏模型,简记为n-SRBDM．在一个典型的随选型路由协议即动态源路由（DSR）协议的基础上,研究了网络的一些关键性能参数,给出了路由泛洪距离的概率分布和期望,限定泛洪步数时成功寻路的概率、发现τ-时有效路径及对称有效路径的概率,发现一条有效路径的平均时间等,对于路由维护过程,也引入并研究了一些网络性能参数,例如,路由恢复的平均频率,路由有效的平均时间．对于这些网络参数在空间可复用和空间不可复用两种情形下进行了比较．证明了空间可复用模型下的路由选择更为有效．     

Self-stabilizing algorithm for efficient topology control in Wireless Sensor Networks

Wireless Sensor Networks lifetime mainly depends on energy saving efficiency. In this paper, we propose an energy-efficient self-stabilizing topology control protocol for WSN. We reduce the transmission power of each node so as to maintain network connectivity while saving maximum energy. Besides, we propose an approximation algorithm for minimum weighted connected dominating set that builds a virtual backbone formed by sensors with maximum energy. This backbone is used for efficient routing purpose. We proved the algorithm correctness and through our simulation results, we showed the efficiency of our proposed solution.