Routing-efficient CDS construction in Disk-Containment Graphs

In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.     

Framework for link reliability in inter-working multi-hop wireless networks

With the increase in deployment of multi-hop wireless networks and the desire for seamless internet access through ubiquitous connectivity, the inter-working of heterogeneous multi-hop wireless networks will become prominent in the near future. To complement the quest for ubiquitous service access, multi-mode mobile terminals are now in existence. Inter-working heterogeneous multi-hop wireless networks can provide seamless connectivity for such multi-mode nodes but introduces a number of challenges due to its dynamic network topology. One of the challenges in ensuring seamless access to service through these terminals in an inter-working environment is the selection of reliable wireless point-to-point links by the multi-hop nodes. A wireless link is said to be reliable if its radio attribute satisfies the minimum requirements for successful communication. Successful communication is specified by metrics such as signal to interference and noise ratio (SINR), probability of bit error etc. However, the multi-hop wireless networks being inter-worked may operate with different link layer protocols. Therefore, how can the reliability of a wireless link be estimated irrespective of the link level technologies implemented in the networks being inter-worked so that optimal paths can be used for multi-hopping between nodes? In this paper, a generic framework which can estimate the reliability of a link in inter-working multi-hop wireless network is presented. The framework uses the relationship between inter-node interference, SINR and the probability of bit error to determine the reliability of a wireless link between two nodes. There is a threshold for the probability of bit error on a link for the link to be termed reliable. Using parameters such as the SINR threshold, nodes’ transmission power, link distance and interfering node density, the framework can evaluate the reliability of a link in an inter-working multi-hop network.     

Topology design for on-demand dual-path routing in wireless networks

One way to achieve reliability with low-latency is through multi-path routing and transport protocols that build redundant delivery channels (or data paths) to reduce end-to-end packet losses and retransmissions. However, the applicability and effectiveness of such protocols are limited by the topological constraints of the underlying communication infrastructure. Multiple data delivery paths can only be constructed over networks that are capable of supporting multiple paths. In mission-critical wireless networks, the underlying network topology is directly affected by the terrain, location and environmental interferences, however the settings of the wireless radios at each node can be properly configured to compensate for these effects for multi-path support. In this work we investigate optimization models for topology designs that enable end-to-end dual-path support on a distributed wireless sensor network. We consider the case of a fixed sensor network with isotropic antennas, where the control variable for topology management is the transmission power on network nodes. For optimization modeling, the network metrics of relevance are coverage, robustness and power utilization. The optimization models proposed in this work eliminate some of the typical assumptions made in the pertinent network design literature that are too strong in this application context.     

多无线WMN中干扰最小化信道分配算法研究

为了提高无线迈适网的通信容量,网络中的每个路由节点均配备有多个无线网卡,并提供多个可用的无线信道.如何将这些信道合理地分配到网络的各个通信链路上,使得整个网络的干扰最小是一个至关重要问题.分析了基于禁忌搜索的信道分配算法,并针对该算法存在的问题,提出了初步的改进算法.     

A queueing analysis of max-min fairness, proportional fairness and balanced fairness

We compare the performance of three usual allocations, namely max-min fairness, proportional fairness and balanced fairness, in a communication network whose resources are shared by a random number of data flows. The model consists of a network of processor-sharing queues. The vector of service rates, which is constrained by some compact, convex capacity set representing the network resources, is a function of the number of customers in each queue. This function determines the way network resources are allocated. We show that this model is representative of a rich class of wired and wireless networks. We give in this general framework the stability condition of max-min fairness, proportional fairness and balanced fairness and compare their performance on a number of toy networks.     

The N-policy of a discrete time Geo/G/1 queue with disasters and its application to wireless sensor networks

We analyze an N-policy of a discrete time Geo/G/1 queue with disasters. We obtain the probability generating functions of the queue length, the sojourn time, and regeneration cycles such as the idle period and the busy period. We apply the queue to a power saving scheme in wireless sensor networks under unreliable network connections where data packets are lost by external attacks or shocks. We present various numerical experiments for application to power consumption control in wireless sensor networks. We investigate the characteristics of the optimal N-policy that minimizes power consumption and derive practical insights on the operation of the N-policy in wireless sensor networks.     

Jamming communication networks under complete uncertainty

This paper describes a problem of interdicting/jamming wireless communication networks in uncertain environments. Jamming communication networks is an important problem with many applications, but has received relatively little attention in the literature. Most of the work on network interdiction is focused on preventing jamming and analyzing network vulnerabilities. Here, we consider the case where there is no information about the network to be jammed. Thus, the problem is reduced to jamming all points in the area of interest. The optimal solution will determine the locations of the minimum number of jamming devices required to suppress the network. We consider a subproblem which places jamming devices on the nodes of a uniform grid over the area of interest. The objective here is to determine the maximum grid step size. We derive upper and lower bounds for this problem and provide a convergence result. Further, we prove that due to the cumulative effect of the jamming devices, the proposed method produces better solutions than the classical technique of covering the region with uniform circles.     

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.     

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.     

Tandem queueing networks with neighbor blocking and back-offs

We introduce a novel class of tandem queueing networks which arise in modeling the congestion behavior of wireless multi-hop networks with distributed medium access control. These models provide valuable insight in how the network performance in terms of throughput depends on the back-off mechanism that governs the competition among neighboring nodes for access to the medium. The models fall at the interface between classical queueing networks and interacting particle systems, and give rise to high-dimensional stochastic processes that challenge existing methodologies. We present various open problems and conjectures, which are supported by partial results for special cases and limit regimes as well as simulation experiments.     

A Product Theorem for Markov Chains with Application to PF-Queueing Networks

Queueing networks in random environments represent more realistic models of computer and telecommunication systems than classical product form networks. This is due to the fact that network behaviour often depends on human activities which may vary according to daytime dependent behavioural patterns as well as physiological and mental indexes. In this paper we establish a product connection theorem for Markov chains which contains some corresponding results for spatial processes as well as for queueing networks in random environment as special cases. We demonstrate how our results can be applied to construct an adequate model for wireless networks with hook up capacity.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.     

Queueing Networks of Random Link Topology: Stationary Dynamics of Maximal Throughput Schedules

In this paper, we study the stationary dynamics of a processing system comprised of several parallel queues and a single server of constant rate. The connectivity of the server to each queue is randomly modulated, taking values 1 (connected) or 0 (severed). At any given time, only the currently connected queues may receive service. A key issue is how to schedule the server on the connected queues in order to maximize the system throughput. We investigate two dynamic schedules, which are shown to stabilize the system under the highest possible traffic load, by scheduling the server on the connected queue of maximum backlog (workload or job number). They are analyzed under stationary ergodic traffic flows and connectivity modulation. The results also extend to the more general case of random server rate.We then investigate the dynamics of acyclic (feed-forward) queueing networks with nodes of the previous type. Their links (connectivities) are stochastically modulated, inducing fluctuating network topologies. We focus on the issue of network throughput and show that it is maximized by simple node server schedules. Rate ergodicity of the traffic flows traversing the network is established, allowing the computation of the maximal throughput.Queueing networks of random topology model several practical systems with unreliable service, including wireless communication networks with extraneous interference, flexible manufacturing systems with failing components, production management under random availability of resources etc.Research supported in part by the National Science Foundation.This revised version was published online in June 2005 with corrected coverdate     

Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks

In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors.     

Resource allocation for end-to-end QoS provisioning in a hybrid wireless WCDMA and wireline IP-based DiffServ network

In the future UMTS network, the heterogeneous traffics of multimedia services demand various QoS provisioning. At the same time, the seamlessly conveying of information between mobile users and a hybrid network requires the networking from wireless to wireline domains. However, in both academia and industries, the end-to-end QoS provisioning in the integration of wireline and wireless networks remains a challenge. In this paper, a modeling of a hybrid wireless WCDMA and wireline IP-based DiffServ network is presented to investigate the resource allocation for end-to-end QoS provisioning for multimedia services. In the wireless domain, the mathematical modeling of the cross-layer model including the physical layer, the link layer and the network layer is built. The connection admission control scheme is implemented based on the cross-layer model to determine the amount of resource for different services. In the wireline domain, we define the mapping of QoS classes between UMTS and DiffServ networks according to different QoS requirements. We propose a bandwidth allocation scheme to provide satisfactory packet loss and delay guarantee in DiffServ networks. The final end-to-end admission control scheme combines the resource allocation and admission control in both wireless and wireline domains. The analytical and simulation results show that the proposed resource allocation and admission control schemes work cooperatively in the presented hybrid wireless and wireline networks to guarantee the end-to-end QoS requirements for multimedia services.     

Recent advances on failure and recovery in networks of networks

Until recently, network science has focused on the properties of single isolated networks that do not interact or depend on other networks. However it has now been recognized that many real-networks, such as power grids, transportation systems, and communication infrastructures interact and depend on other networks. Here, we will present a review of the framework developed in recent years for studying the vulnerability and recovery of networks composed of interdependent networks. In interdependent networks, when nodes in one network fail, they cause dependent nodes in other networks to also fail. This is also the case when some nodes, like for example certain people, play a role in two networks, i.e. in a multiplex. Dependency relations may act recursively and can lead to cascades of failures concluding in sudden fragmentation of the system. We review the analytical solutions for the critical threshold and the giant component of a network of n interdependent networks. The general theory and behavior of interdependent networks has many novel features that are not present in classical network theory. Interdependent networks embedded in space are significantly more vulnerable compared to non-embedded networks. In particular, small localized attacks may lead to cascading failures and catastrophic consequences. Finally, when recovery of components is possible, global spontaneous recovery of the networks and hysteresis phenomena occur. The theory developed for this process points to an optimal repairing strategy for a network of networks. Understanding realistic effects present in networks of networks is required in order to move towards determining system vulnerability.     

Flow-level performance and capacity of wireless networks with user mobility

The performance evaluation of wireless networks is severely complicated by the specific features of radio communication, such as highly variable channel conditions, interference issues, and possible hand-offs among base stations. The latter elements have no natural counterparts in wireline scenarios, and create a need for novel performance models that account for the impact of these characteristics on the service rates of users. Motivated by the above issues, we review several models for characterizing the capacity and evaluating the flow-level performance of wireless networks carrying elastic data transfers. We first examine the flow-level performance and stability of a wide family of so-called α-fair channel-aware scheduling strategies. We establish that these disciplines provide maximum stability, and describe how the special case of the Proportional Fair policy gives rise to a Processor-Sharing model with a state-dependent service rate. Next we turn attention to a network of several base stations with inter-cell interference. We derive both necessary and sufficient stability conditions and construct lower and upper bounds for the flow-level performance measures. Lastly we investigate the impact of user mobility that occurs on a slow timescale and causes possible hand-offs of active sessions. We show that the mobility tends to increase the capacity region, both in the case of globally optimal scheduling and local α-fair scheduling. It is additionally demonstrated that the capacity and user throughput improve with lower values of the fairness index α.     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

Stable network topologies using the notion of covering

An alternative perspective to evaluate networks and network evolution is introduced, based on the notion of covering. For a particular node in a network covering captures the idea of being outperformed by another node in terms of, for example, visibility and possibility of information gathering. In this paper, we focus on networks where these subdued network positions do not exist. We call these networks stable. Within this set we identify the minimal stable networks, which frequently have a ‘bubble-like’ structure. Severing a link in such a network results in at least one of the nodes being covered. In a minimal stable network therefore all nodes cooperate to avoid that one of the nodes ends up in a subdued position. Our results can be applied to, for example, the design of (covert) communication networks and the dynamics of social and information networks.     

Fast performance assessment of IEEE 802.11-based wireless networks

In this paper, we introduce a brand new analytical perspective for analyzing and evaluating the IEEE 802.11-based networks. We identify a tightly-coupled relationship between the number of contending nodes and their contention window sizes in the networks. Based on the relationship, we propose a downsizing model for reducing the computational complexity and for improving the simulation performance in the evaluation of the IEEE 802.11-based networks. We first formally prove that the proposed model preserves the operational characteristics of the original networks in their downsized networks through well-known analytical frameworks, such as the models proposed by Bianchi (2000) [7], Calí et al. (2000) [2], and Hu et al. (2006) [8]. We then demonstrate that the proposed model speeds up the simulation by maximally two orders of magnitude. Even though the simulation shows some difference between the results from an original network and those in its corresponding downsized networks in a wide range of network sizes and traffic patterns, the difference is acceptable since it has minimal values of 1% in most cases and maximum values of 10% in a very few cases. We also present the effectiveness of both the downsizing model and the downsizing-model-based simulation in comparison with other performance models and simulation techniques. As the size and complexity of wireless networks are increasing nowadays, we vision that the new proposed model will be of great advantage in conducting fast and accurate packet-level wireless simulations, as well as being a helpful tool for performing the numerically tractable theoretical studies for extensive performance evaluations, such as determining the network-wide throughput or end-to-end delays.