We consider the problem of placing the minimum number of monitors in a dynamic network to identify additive link metrics from path metrics measured along cycle-free paths between monitors. Our goal is robust monitor placement, i.e., the same set of monitors can maintain network identifiability under topology changes. Our main contribution is a set of monitor placement algorithms with different performance-complexity tradeoffs that can simultaneously identify multiple topologies occurring during the network lifetime. In particular, we show that the optimal monitor placement is the solution to a generalized hitting set problem, for which we provide a polynomial-time algorithm to construct the input and a greedy algorithm to select the monitors with logarithmic approximation. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. Our secondary contribution is a dynamic triconnected decomposition algorithm to compute the input needed by the monitor placement algorithms, which is the first such algorithm that can handle edge deletions. Our evaluations on mobility-induced dynamic topologies verify the efficiency and the robustness of the proposed algorithms.

We consider the problem of placing the minimum number of monitors in a communication network with possible topology changes to identify additive link metrics from path metrics. The core of our solution is a suite of robust monitor placement algorithms with different performance-complexity tradeoffs that guarantee network identifiability for the multiple possible topologies. In particular, we show that the optimal (i.e., minimum) monitor placement is the solution to a generalized hitting set problem, where we provide a polynomial-time algorithm to construct the input. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. We further demonstrate how the proposed algorithms can be augmented to handle unpredictable topology changes and tradeoffs between monitor cost and adaptation cost. Our evaluations on mobility-induced dynamic topologies verify the effectiveness and robustness of the proposed algorithms.

Vehicular ad-hoc networks (VANETs) have received a lot of research and industrial attention, including the approval of the IEEE 802.11p standard. However, resource allocation in the standard still makes use of the traditional mechanisms (e.g., carrier sensing) without exploiting the unique characteristics of VANETs. This provides the motivation for this work. As a first step toward the goal and by considering vehicle density, this paper investigates how transmission probability can be determined to optimise throughput of VANETs. A challenging design issue of VANETs is to deal with node (vehicle) mobility, which causes various vehicular densities within the same network and consequently influences the connectivity and capacity of the network. This work shows that it is indeed possible to follow the dynamics of a network and consequently adapt the transmission probability at the MAC layer to reduce the interference and maximise the single-hop throughput between adjacent nodes. By exploiting the characteristics of VANETs, we introduce approximations in order to derive closed-form expressions of the network throughput and other performance metrics in terms of transmission probability, which would otherwise be impossible. Our extensive simulations validate the approximations and the proposed analytical model thus can serve as a promising tool to improve VANETs performance. For example, the optimal transmission probability can be used to develop efficient MAC protocols using vehicle density estimation in VANETs for our future work.

The continuously growing number of multimedia applications in current communication networks highlights the necessity for an efficient resource allocation mechanism to capture the unique characteristics of multi-tiered multimedia applications and allocate network capacity in an efficient way. This paper examines the problem of sharing the network throughput under the existence of inelastic traffic flows that follow a multi-tiered utility function. First, the concept of multi-sigmoidal utilities is introduced in order to describe user satisfaction, then, the implications of the use of such utilities are discussed for two different allocation policies; the bandwidth-proportional and the utility-proportional fairness allocation policies. In the former case, the intrinsic reasons of possible network oscillations are analyzed in detail and a heuristic to overcome such situations is proposed. In the latter one, where such oscillations are not possible, efficient ways to calculate a closed form solution for the optimal rate allocation are described. Moreover, a novel mathematical representation of such a multi-sigmoidal utility is presented and closed form solutions for a number of application types are calculated. Finally, the efficiency and robustness of the proposed algorithms is evaluated by simulations for different network topologies and compared against other work in literature.

Admission control (AC) is highly important in packet networks with quality-of-service (QoS) requirements since the uncontrolled admission of new data connections can jeopardize the QoS of existing connections and degrade the overall network performance. It requires a priory knowledge of the network capacity, the estimation of which is intricate and complex due to the operational characteristics of various communication protocols, complex network topologies, and dynamic traffic behavior with QoS requirements. In this work, we propose a generic admission control (GAC) methodology where the network conditions between any given ingress-egress node pair are summarized into a single parameter, referred to as the "QoS index". It accounts for various traffic volumes and QoS requirements, like throughput, delay, and packet error rate. Using this QoS index we track the network performance by predicting the potential impact of a new connection admission on the index. The decision depends on whether the predicted value lies below 1. We discuss its wide applicability and feasibility to many types of packet networks, wired or wireless, independent of what communication protocols in use at various layers. We finally validate the proposed GAC methodology by extensive simulations, confirming a significant improvement in terms of network goodput and QoS outage probability compared to other existing statistics-based AC methodologies.

The continuously increasing demand for resources in modern, both wired and wireless, communication networks urges for more efficient resource allocation. Such an allocation of resources to network users can be formulated as an optimization problem. Traditional resource allocation protocols, such as TCP, operate inefficiently in cases that there is competition for resources by multimedia applications and some, or possibly all, links in the network are wireless. In this paper, the performance degradation of TCP in modern networks is quantified to highlight the necessity for a novel optimization-based resource allocation protocol. To this direction, a new optimization framework is presented that can provide the theoretical foundations of such a protocol by proving a sufficient, and in some cases also necessary, condition for distributed solution of non-convex problems. The wide applicability of this general framework is illustrated by considering a resource allocation formulation in TDMA/CDMA ad-hoc networks. The convergence properties to the optimal solution are first identified and a distributed algorithm is proposed. Moreover, a novel heuristic is developed to approximate the optimal solution when the condition does not hold and resolve network oscillations. Finally, the performance of the proposed methodology is evaluated and compared against other approaches in literature by simulation.

Current communication networks support a variety of applications with different quality of service (QoS) requirements which compete for its resources. This continuously increasing competition highlights the necessity for more efficient and fair resource allocation. Current Network Utility Maximization (NUM) framework fails to achieve this target and alternative approaches cannot operate in networks that consist of wireless links. This paper presents a NUM framework for wireless networks that shares resources according to the utility proportional fairness policy. This policy is shown to prevent rate oscillations in the resource allocation process, allocate resources in a more fair manner among different types of applications and lead to the calculation of closed form solutions for the optimal rate allocation function. Based on this policy, a distributed rate and power allocation algorithm is proposed that gives priority to applications with greater need of resources. Finally, numerical results on the performance of the proposed algorithm are presented and compared against other approaches in the literature.

This paper presents a non-convex optimization framework for the Network Utility Maximization problem in Wireless Networks, which incorporates the interference among links and introduces a power penalty term in the objective function to assure both convergence and energy efficiency of the method. Moreover, a distributed gradient based algorithm is proposed that converges to the optimal solution for problems with zero duality gap and a fair-allocation heuristic is presented to resolve user oscillations when they occur. Finally, numerical results regarding the performance of the heuristic and the distributed approach are presented.

Localization algorithms for wireless sensors can use diverse measurement hardware as a source of geographical information in order to provide better location estimates. A relatively extensive set of measurement hardware comprises of machinery capable of measuring range, angle-of-arrival and earth gravity direction. Literature covers distance vector (DV) exchange algorithms for the measurements which provide the complete distance vector. In this work we develop a method for computing the complete DV in a distributed way, using linear antenna array and ranging to calculate a complete DV. We develop a localization algorithm that uses this concept. We also determine pathological situations of flip-error occurrence, but we incorporate this knowledge into the algorithm so that we prevent the flip-errors from occurring.

Wireless Mesh Networks (WMNs) is a promising key technology for next generation wireless backhauling that is expected to support various types of applications with different quality-of-service (QoS) demands. Advanced antenna techniques, novel scheduling algorithms and routing schemes have attracted increased research interests aiming to optimize the performance of WMNs and satisfy their vast and diverse traffic requirements. However, in such networks, uncontrolled admission of arbitrary large number of data flows, together with the distributed and dynamic nature of WMNs, can highly increase the wireless channel interference with catastrophic subsequence for the whole network. To overcome this difficulty, we provide a mathematical model to analyze and estimate the real-time "route capacity" associated with time-varying QoS requirements. This allows us to take admission control decisions for new data flows in a way that we can increase the resource utilization while maintaining all good QoS levels for users with different grade-of-service (GoS). Numerical and extensive simulations results show that the proposed scheme achieves higher network goodput while it significantly reduces the outage and session blocking probability if compared to other techniques.

The impact of wireless network coding on multiuser diversity gain is investigated. A generic framework to calculate the CDF of the opportunistic channel gain, for different communication scenarios with a single relay, when scheduling or network coding are used, is presented. The CDF and PDF of the lognormal and Rayleigh opportunistic channels for these scenarios are calculated and the average system capacity is derived. Numerical results show that while wireless network coding most of the time can provide significant throughput gain, for low mean received SNR and high channel variations it may result to lower ergodic capacity than simple opportunistic scheduling, especially when transmission overhearing is required. For these cases, we show that although a coding gain is achieved, there may be a larger reduction on the multiuser diversity gain which results to overall lower average system capacity compare to traditional opportunistic scheduling.

Wireless mesh networks (WMNs) is a promising key technology for next generation wireless backhauling that have recently attracted both the academic and industrial interest. Such networks are expected to have high throughput demands and support various types of applications with different quality-of-service (QoS) constraints. Opportunistic scheduling has been proven highly beneficial in such networks since it takes advantage of the dynamic nature of the channel between different wireless mesh routers. Recently a promising cross-layered framework has been proposed (IQoSR) that combines a distributed opportunistic scheduler with a multi-constrained QoS routing scheme and has been proven to outperform conventional layer 2 and 3 approaches. However, opportunistic scheduling cannot provide hard resource reservation; therefore, the admission of new flows in a route may jeopardize the QoS of the ongoing flows. In order to overcome this problem, in this work we introduce a connection admission control (CAC) scheme for different levels of QoS to efficiently manage the resources among existing and new flows. In this way, we improve the overall network performance and minimize the outage probability of the ongoing flows while we guarantee the required grade-of-service (GoS) to the underlying applications. Simulation analysis shows that the proposed scheme achieves lower blocking probability while it reduces the outage probability of the existing flows.

Cross-layer routing and scheduling algorithms design for wireless backhaul mesh network has attracted much research interest recently. The network is expected to support various types of applications with different quality of service (QoS) requirements from both routing and scheduling perspectives. Existing works do not efficiently integrate these QoS constraints in route discovery and maintenance phases and overlook the interaction between medium access control (MAC) and routing algorithms. In this work, we propose a novel cross- layer framework of QoS routing and distributed opportunistic scheduling for wireless mesh network, which provides resource reservation for QoS flows. Studies with different scheduling algorithms and routing protocols have shown that our algorithm successfully guarantees various QoS requirements and achieves higher network throughput when compared with other standard techniques.

Multihop wireless mesh networks (WMNs) are considered a promising technology to backhaul heterogeneous data traffic from wireless access networks to the wired Internet. WMNs are expected to support various types of applications with diverse quality of service (QoS) requirements, such as end-to-end packet delay, throughput, and packet-error-rate (PER). Recent works in this area are mainly concentrated on network layer routing algorithms with QoS provisioning that unfortunately cannot cooperate efficiently with existing medium access control (MAC) solutions to strictly guarantee multiple QoS constraints. This drawback may significantly deteriorate the and-to-end network performance and end-user experience especially for delay/throughput-sensitive applications such as voice-over IP (voIP) and interactive video. In this paper, we propose a fully distributed multi-constrained QoS scheduling algorithm to overcome this disadvantage. We show by simulation that the proposed scheduling scheme can efficiently organize the resources in physical (PHY) and MAC layers to successfully increase the network goodput, decrease the end-to-end (ETE) packet delay, and achieve less QoS outage probability if compared with other protocols.

In this paper, we address the issue of co-existence of Bluetooth (BT) and Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA)-based Wireless Local Area Networks (WLANs) in the license free 2.4 GHz band. Specifically, the probabilistic treatment presented in the following investigates the effect of the slotted p-persistent CSMA/CA system on a co-existing BT piconet. A closed-form expression for packet error probability (PEP) in BT as a function of CSMA/CA parameters such as the persistence probability, probability of packet generation and the number of users is derived. The analytical model entails different BT packet types, frequency hopping guard time, and different traffic models in the BT piconet.

Random access MAC protocols for radio environments are prone to collisions without offering a way to successfully avoid or identify them and thus fail to achieve the performance required by a multitude of applications. However, in some cases it is possible to use collision detection in order to reduce the time spent on collisions and improve the system efficiency. In this paper we provide an analytical framework for WCSMA/CD with a finite user population. The expected channel throughput is then derived for different design parameters and compared against p-persistent CSMA/CA.

We investigate the impact of power control on the performance of a multi-hop CSMA/CA system, also taking into account the additional traffic generated due to multi-hop transmissions. An analytical model is presented with emphasis on the influence of power, more specifically the number of nodes dwelling in the area covered by this power, on the number of hops and, consequently, on the end-to-end throughput. Unlike other works, a closed form solution is derived for the throughput performance of a multi-hop CSMA/CA system, as a function of the offered load, the nodes density and transmission power.

An approximate but explicit fractional bandwidth and power allocation algorithm for orthogonal regenerative frequency-division multiple-access-based multihop communication systems over ergodic flat-fading channels is presented. The exposed algorithm is assessed for a two-hop scenario, where it is shown to operate within 10% of the optimum resource allocation. The achieved end-to-end capacity is up to 45% higher if compared to a trivial allocation strategy with equal resources.

The objective of the IST project MIND (Mobile IP based network developments) is to facilitate IP-based broadband services for mobile users in various operating environments. Activities within MIND concentrate on the development, optimisation and harmonisation of the appropriate layers involved. The physical (PHY) layer was chosen to base on the high performance radio local area network type 2 standard (HIPERLAN/2). The work presented here demonstrates the applicability of HIPERLAN/2 to scenarios with increased mobility. Initially, HIPERLAN/2 was designed for rather static environments providing hot spot data rates of up to 54 Mbps. Mitigation techniques to overcome the drawbacks of a fast fading environment are thus studied within IST-MIND. The extracted transceiver structures allow the deployment of HIPERLAN/2 in almost any environments currently envisaged. Particularly, the system deployment of HIPERLAN/2 to a vehicle-to-vehicle communication scenario is studied and preliminary system level performance results presented.