A framework for misuse detection in ad hoc Networks-part I

We consider ad hoc networks with multiple, mobile intruders. We investigate the placement of the intrusion detection modules for misuse-based detection strategy. Our goal is to maximize the detection rate subject to limited availability of communication and computational resources. We mathematically formulate this problem, and show that computing the optimal solution is NP-hard. Thereafter, we propose two approximation algorithms that approximate the optimal solution within a constant factor, and prove that they attain the best possible approximation ratios. The approximation algorithms though require recomputation every time the topology changes. Thereafter, we modify these algorithms to adapt seamlessly to topological changes. We obtain analytical expressions to quantify the resource consumption versus detection rate tradeoffs for different algorithms. Using analysis and simulation, we evaluate these algorithms, and identify the appropriate algorithms for different detection rate and resource consumption tradeoffs.     

Downlink user selection and resource allocation for semi-elastic flows in an OFDM cell

We are concerned with user selection and resource allocation in wireless networks for semi-elastic applications such as video conferencing. While many packet scheduling algorithms have been proposed for elastic applications, and many user selection algorithms have been proposed for inelastic applications, little is known about optimal user selection and resource allocation for semi-elastic applications in wireless networks. We consider user selection and allocation of downlink transmission power and subcarriers in an orthogonal frequency division multiplexing cellular system. We pose a utility maximization problem, but find that direct solution is computationally intractable. We first propose a method that makes joint decisions about user selection and resource allocation by transforming the utility function into a concave function so that convex optimization techniques can be used, resulting in a complexity polynomial in the number of users with a bounded duality gap. This method can be implemented if the network communicates a shadow price for power to power allocation modules, which in turn communicate shadow prices for rate to individual users. We then propose a method that makes separate decisions about user selection and resource allocation, resulting in a complexity linear in the number of users.     

Efficient probe selection algorithms for fault diagnosis

Increase in the network usage for more and more performance critical applications has caused a demand for tools that can monitor network health with minimum management traffic. Adaptive probing has the potential to provide effective tools for end-to-end monitoring and fault diagnosis over a network. Adaptive probing based algorithms adapt the probe set to localize faults in the network by sending less probes in healthy areas and more probes in the suspected areas of failure. In this paper we present adaptive probing tools that meet the requirements to provide an effective and efficient solution for fault diagnosis for modern communication systems. We present a system architecture for adaptive probing based fault diagnosis tool and propose algorithms for probe selection to perform failure detection and fault localization. We compare the performance and efficiency of the proposed algorithms through simulation results.     

Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(kalpha)-approximation where is the best approximation factor for the related problem in wired networks (the best alpha so far is O(log k)). With a more careful analysis, we show our second (slightly more complicated) algorithm is an O(k)-approximation. Our third algorithm assumes that the edge lengths of the network graph form a metric. In this case, we present simple and practical distributed algorithms for the cases of 2- and 3-connectivity with constant approximation factors. We generalize this algorithm to obtain an O(k^2c+2)-approximation for general k-connectivity (2 les c les 4 is the power attenuation exponent). Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining -edge connectivity with guaranteed approximation factors. Recently, different set of authors used the notion of k-connectivity and the results of this paper to deal with the fault-tolerance issues for static wireless network settings.     

Toward a hierarchical and architecture‐based virtual machine allocation in cloud data centers

Number of cloud data centers which consists of hundreds of hosts has increased tremendously around the world due to increase in demands for cloud services. It is expected energy consumption of data centers will reach 139.8 billion Kwh by 2020. Many algorithms are proposed to reduce energy consumption as well as service level agreement violationby minimizing the number of active hosts. Current proposed algorithms do not consider data center architecture, the physical position of hosts, and energy consumption of numerous switches that are in data centers. In this paper, a novel hierarchical cloud resource management is proposed that not only minimizes the number of hosts but also aggregates virtual machines on a limited subset of data center racks and modules to minimize energy consumption. Experimental results with Cloudsim show that our proposed algorithm reduces energy consumption up to 26% and service level agreement violation up to 96%.     

Randomized data selection in detection with applications to distributed signal processing

Performing robust detection with resource limitations such as low-power requirements or limited communication bandwidth is becoming increasingly important in contexts involving distributed signal processing. One way to address these constraints consists of reducing the amount of data used by the detection algorithms. Intelligent data selection in detection can be highly dependent on a priori information about the signal and noise. In this paper, we explore detection strategies based on randomized data selection and analyze the resulting algorithms' performance. Randomized data selection is a viable approach in the absence of reliable and detailed a priori information, and it provides a reasonable lower bound on signal processing performance as more a priori information is incorporated. The randomized selection procedure has the added benefits of simple implementation in a distributed environment and limited communication overhead. As an example of detection algorithms based upon randomized selection, we analyze a binary hypothesis testing problem, and determine several useful properties of detectors derived from the likelihood ratio test. Additionally, we suggest an adaptive detector that accounts for fluctuations in the selected data subset. The advantages and disadvantages of this approach in distributed sensor networks applications are also discussed.     

Joint scheduling and routing with power control for centralized wireless sensor networks

We consider a TDMA-based multi-hop wireless sensor network, where nodes send data to a sink, which is aware of received powers at all receivers; the sink is responsible for creating the network topology and assigning time slots to links. Under this centralized approach, we propose two algorithms that jointly define the tree topology connecting nodes to the sink, and assign time slots, avoiding any packet loss. In contrast with previous works, the proposed algorithms accurately account for interference effects; when evaluating the signal-to-interference ratio to establish the tree and schedule transmissions, we consider the sum of all actual interfering signals, a fact of relevance for networks with increasing number of nodes. Optimal selection of transmit powers, minimizing energy consumption, is also applied. Our algorithms are compared to a benchmark solution and other proposals from the literature; it is shown that they bring to better radio resource utilization, higher throughput and lower energy consumption, while keeping the average delay limited.

     

Operationally optimal vertex-based shape coding

In this article, we address the issue of operationally optimal shape encoding, which is a step in the direction of globally optimal resource allocation in object-oriented video. After an overview of shape-based coding and algorithms, we define the problem mathematically, introduce the necessary notation, and then present the basic idea behind the proposed algorithms. We then discuss the constraints imposed on the code used to encode the approximation. We then introduce a definition of distortion that fits into the proposed framework and introduce the directed acyclic graph (DAG) formulation of the problem, which results in a fast solution approach. We also show how the DAG algorithm can be used to find the approximation with the minimum-maximum segment distortion for a given rate as well as to find the approximation with the smallest total distortion for a given rate. We then present experimental results and point out directions for future research     

Cooperation with multiple relays in wireless sensor networks: optimal cooperator selection and power assignment

We consider the energy-minimal joint cooperator set selection and power assignment problem in a cooperation scenario with multiple relays, under transmit power constraints, while satisfying a target frame error rate (FER) at the destination receiver. We first derive the FER of a cooperative system and present a simplified calculation that also involves a simple, yet close approximation to the average bit error rate of a multiple input single output system. Our FER calculation facilitates a closed-form solution for the joint optimization problem, resulting in the Optimal Cooperator Selection and Power Assignment (O-CSPA) algorithm. Next, we devise the Distributed Cooperator Selection and Power Assignment (D-CSPA) algorithm in which the relays individually decide to become a cooperator and determine their power levels. We evaluate the performance of O-CSPA and D-CSPA algorithms under several network topologies, varying target FER levels and different power consumption models, by considering the energy dissipated in the transceiver circuits and amplifiers of all involved nodes. We show that both algorithms provide notable energy savings and conclude that the extent of the savings depends significantly on the power consumption model. D-CSPA’s performance is shown to be not only close to that of optimal solution, but also robust to errors in channel estimation.     

Approximation Algorithm for Joint Node Placement and Frequency Selection in Bistatic Radar Sensor Networks

We consider a bistatic radar sensor network that consists of multiple separated radar transmitters and radar receivers, which are deployed to detect targets among a set of points of interest. Any transmitter-receiver pair with the same frequency forms a bistatic radar. In contrast to the disk-based sensing model in a traditional sensor network, the detection probability of a bistatic radar depends on both locations of the transmitter and receiver. Given the radar transmitters’ locations and illuminating frequencies, we study the problem of joint radar receiver placement and frequency selection to maximize the target detection probability. We first study the case where there is a set of candidate locations to place the radar receivers, and propose a simple algorithm with approximation ratio at least 0.63. We then consider the case where there is no constraint for radar receivers’ locations, and develop an approximation algorithm which is provably close to optimal. Finally, the numerical results are presented to show the efficacy of our algorithms.     

Robust Monitoring of Link Delays and Faults in IP Networks

In this paper, we develop failure-resilient techniques for monitoring link delays and faults in a Service Provider or Enterprise IP network. Our two-phased approach attempts to minimize both the monitoring infrastructure costs as well as the additional traffic due to probe messages. In the first phase, we compute the locations of a minimal set of monitoring stations such that all network links are covered, even in the presence of several link failures. Subsequently, in the second phase, we compute a minimal set of probe messages that are transmitted by the stations to measure link delays and isolate network faults. We show that both the station selection problem as well as the probe assignment problem are NP-hard. We then propose greedy approximation algorithms that achieve a logarithmic approximation factor for the station selection problem and a constant factor for the probe assignment problem. These approximation ratios are provably very close to the best possible bounds for any algorithm.     

Custom Networks-on-Chip Architectures With Multicast Routing

In this paper, we consider the problem of synthesizing custom networks-on-chip (NoC) architectures that are optimized for a given application. We consider both unicast and multicast traffic flows in the input specification. Multicast traffic flows are used in a variety of applications, and their direct support with only replication of packets at optimal bifurcation points rather than full end-to-end replication can significantly reduce network contention and resource requirements. Our problem formulation is based on the decomposition of the problem into the inter-related steps of finding good flow partitions, deriving a good physical network topology for each group in the partition, and providing an optimized network implementation for the derived topologies. Our solutions may be comprised of multiple custom networks, each interconnecting a subset of communicating modules. We propose several algorithms that can systematically examine different flow partitions, and we propose Rectilinear–Steiner-Tree (RST)-based algorithms for generating efficient network topologies. Our design flow integrates floorplanning, and our solutions consider deadlock-free routing. Experimental results on a variety of NoC benchmarks showed that our synthesis results can on average achieve a 4.82 times reduction in power consumption over different mesh implementations on unicast benchmarks and a 1.92 times reduction in power consumption on multicast benchmarks. Significant improvements in performance were also achieved, with an average of 2.92 times reduction in hop count on unicast benchmarks and 1.82 times reduction in hop count on multicast benchmarks. To further gauge the effectiveness of our heuristic algorithms, we also implemented an exact algorithm that enumerates all distinct set partitions. For the benchmarks where exact results could be obtained, our algorithms on average can achieve results within 3% of exact results, but with much shorter execution times.      

Relay Subset Selection in Wireless Networks Using Partial Decode-and-Forward Transmission

This paper considers the problem of selecting a subset of nodes in a two-hop wireless network to act as relays in aiding the communication between the source–destination pair. Optimal relay subset selection with the objective of maximizing the overall throughput is a difficult problem that depends on multiple factors, including node locations, queue lengths, and power consumption. A partial decode-and-forward strategy is applied in this paper to improve the tractability of the relay selection problem and the performance of the overall network. Note that the number of relays that are selected ultimately determines the performance of the network. This paper benchmarks this performance by determining the net diversity that is achieved using the relays that are selected and the partial decode-and-forward strategy. This framework is subsequently used to further transform relay selection into a simpler relay placement problem, and two proximity-based approximation algorithms are developed to determine the appropriate set of relays to be selected in the network. Other selection strategies, such as random relay selection and a greedy algorithm that relies on channel state information, are also presented. This paper concludes by showing that the proposed proximity-based relay selection strategies yield near-optimal expected rates for a small number of selected relays.      

融合面积估算和多目标优化的硬件任务划分算法

针对可重构计算机系统配置次数(划分块数)的最小化问题,提出了一种融合面积估算和多目标优化的硬件任务划分算法。该算法每次划分均进行硬件资源面积的估算,并且通过充分考虑可重构资源的使用、一个数据流图所有划分块执行延迟总和、划分模块间边数等因素构造了新的探测函数prior_assigned(),该函数能够计算每个就绪节点的优先权值,新算法通过该值能动态调整就绪列表任务节点的调度次序。实验结果表明,与现有的层划分、簇划分、增强静态列表、多目标时域划分、簇层次敏感等5种划分算法相比,该算法能获得最少的模块数,并且随着可重构处理单元面积的增大,除层划分算法之外,其执行延迟的均值也是最小的。     

Adaptive MIMO antenna selection via discrete stochastic optimization

Recently it has been shown that it is possible to improve the performance of multiple-input multiple-output (MIMO) systems by employing a larger number of antennas than actually used and selecting the optimal subset based on the channel state information. Existing antenna selection algorithms assume perfect channel knowledge and optimize criteria such as Shannon capacity or various bounds on error rate. This paper examines MIMO antenna selection algorithms where the set of possible solutions is large and only a noisy estimate of the channel is available. In the same spirit as traditional adaptive filtering algorithms, we propose simulation based discrete stochastic optimization algorithms to adaptively select a better antenna subset using criteria such as maximum mutual information, bounds on error rate, etc. These discrete stochastic approximation algorithms are ideally suited to minimize the error rate since computing a closed form expression for the error rate is intractable. We also consider scenarios of time-varying channels for which the antenna selection algorithms can track the time-varying optimal antenna configuration. We present several numerical examples to show the fast convergence of these algorithms under various performance criteria, and also demonstrate their tracking capabilities.     

Minimum-energy all-to-all multicasting in wireless ad hoc networks

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-Complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.     

一种高资源效率的Fast-RCSC极化码译码器

针对现有极化码软输出译码器存在的高资源消耗与低资源效率,设计了一种快速低复杂度软取消(Fast Reduced Complexity Soft-Cancelation,Fast-RCSC)译码算法及其译码器硬件架构。Fast-RCSC算法对内部特殊结点进行完整计算,在减少译码周期的同时仍有较好译码性能。基于不同特殊结点公式之间存在相似性,进而通过对引入的特殊结点模块进行计算结果复用以及计算模块分时复用,减少特殊结点模块资源消耗。通过共用存储单元以及对不足存储单元数据宽度的数据进行合并,降低存储资源消耗。在华润上华(Central Semiconductor Manufacturing Corporation,CSMC)180nm工艺下综合结果表明,设计的译码器在码长为1024的情况下,面积为2.92mm²,资源效率为245.2Mbps/mm²,相比现有软输出译码器有不同程度的提升。     

Joint wireless and optical resources allocation for availability-guaranteed service in survivable fiber-wireless access network

The fiber-wireless (FIWi) access network not only leverages the technical merits of wireless and optical access networks, but also provides a potential opportunity for the design of survivable access networks. Previous works have studied the survivability of FiWi access network against network component failure by means of backup fiber deployment and wireless rerouting. However, most of these works put less attention on the connection availability and ignore the joint allocation of wireless and optical resources, which plays an important role in improving the global network performance gain. In this paper, we consider a notable failure scenario in FiWi access network but less mentioned in previous works, i.e., single shared-risk link group failure. We first propose a model for FiWi network to estimate the connection availability of service demand. Then, a novel resource allocation approach is proposed to provide the availability-guaranteed service. Under the requirements of bandwidth and connection availability, we deal with the optimal allocation of joint wireless and optical resources with the objective of minimum resource consumption. Numerical results demonstrate that the proposed scheme can reduce the resource consumption significantly compared to the resource allocation without considering connection availability.     

A unified framework for finite-memory detection

In this paper, we present a general approach to finite-memory detection. From a semi-tutorial perspective, a number of previous results are rederived and new insights are gained within a unified framework. A probabilistic derivation of the well-known Viterbi algorithm, forward-backward, and sum-product algorithms, shows that a basic metric emerges naturally under very general causality and finite-memory conditions. This result implies that detection solutions based on one algorithm can be systematically extended to other algorithms. For stochastic channels described by a suitable parametric model, a conditional Markov property is shown to imply this finite-memory condition. This conditional Markov property, although seldom met exactly in practice, is shown to represent a reasonable and useful approximation in all considered cases. We consider, as examples, linear predictive and noncoherent detection schemes. While good performance for increasing complexity can often be achieved with a finite-memory detection strategy, key issues in the design of detection algorithms are the computational efficiency and the performance for limited complexity.     

Energy-efficient bandwidth allocation in wireless networks: algorithms, analysis, and simulations

In this paper, we present a new energy-efficient bandwidth allocation scheme for wireless networks. First of all, we investigate the intrinsic relationship between the energy consumption and transmission rates of mobile terminals, in which transmission rate is determined through channel allocations. Then, we propose two schemes for connection admission control: victim selection algorithm (VSA) and beneficiary selection algorithm (BSA) with the intent to reduce energy consumption of each terminal. Moreover, we introduce an adjustment algorithm to statistically meet the demands for quality of service (QoS) during the resource allocation. The performance of the proposed schemes is evaluated with respect to energy consumption rate of each successfully transmitted bit, throughput and call blocking probabilities. An extensive analysis and simulation study is conducted for Poisson and self-similar, multi-class traffic.