We survey some mathematical models and tools that can be useful in the analysis and design of multi-hop wireless networks.

We generalize the well known random geometric graph based network topology model to a higher level of abstraction, to allow the inclusion of many different models. We explore the asymptotic relationship between node degrees and connectivity in this general model.

The way the network topology is modeled in a wireless network, primarily in ad hoc and sensor networks, has a fundamental influence on protocol design and efficiency. The frequently used graph models are simpler, and more amenable to analysis and protocol development. On the other hand, physical models represent the actual radio environment much more faithfully, albeit at the price of being far less supportive to network protocol development. We consider the potential future trend of resolving this conflict, via the integration of the two approaches. We present some results and challenges in exploring the connections between the two apparently very different classes of models.

We address multi-radio networks, i.e., wireless networks where the nodes are equipped with multiple air interfaces. We analyze, both analytically and via simulation, various gains that the multi-radio environment can provide. First we investigate the gain in network connectivity by modeling the topology of a multi-radio network by a multigraph. The gain is captured by introducing the novel graph theoretic concept of the multigraph advantage. It is the surplus of connectivity over the sum of the individual connectivities, as we put together several graphs to form a multigraph sum. We first prove that in the traditional random graph model it results in a strict super-additive behavior. We validate the theoretical results via simulations and show that similar phenomena occur in geometric random graph models. We then investigate, via ns2-based simulations, the nodal energy consumption as well as the end-to-end packet latency needed to route packets in a multi-radio network.

We consider large, random network topologies, typical in sensor or ad hoc networks. Achieving full connectivity in these networks is hard, as it is known to asymptotically require unbounded node degrees. This certainly involves a lack of scalability, since nodes with finite resources cannot handle an unbounded neighborhood with bounded delay. It does not exclude, however, partial connectivity, which is satisfactory in many applications, such as sensor networks. Therefore, an important step in analyzing the scalability of such networks is to quantify how large part of the random topology can be still expected to belong to a connected component if the nodes are confined to some bounded degree. We investigate this issue in a very general model that contains many of the often used models as special cases. We prove a bound on the asymptotic fraction of nodes that can belong to a connected component. The bound depends on the expected node degrees and is asymptotically sharp.

In many geometrically generated random network topologies it is a common phenomenon that the expected degree of an average node tends to infinity with the network size, whenever asymptotic connectivity is required. This is clearly an obstacle to scalability, as a real node cannot handle an unbounded number of links within bounded processing time. We call it the lack of degree scalability. To investigate this phenomenon, we set up a general modeling framework that contains many different random graph models as special cases. In this framework we identify two conditions and prove that whenever they are present, they make the lack of degree scalability unavoidable. As our general conditions are directly checkable in most specific cases, even in complicated ones, they can serve as powerful tools to show that a possibly complex random network topology model lacks degree scalability. Often this would otherwise be rather hard to prove via direct analysis of the stochastic geometry of the model.

How to adjust the transmission power at each node to achieve global energy efficiency while maintaining the network connectivity, referred as power management problem, is the major target of various topology control technologies. Moreover, fault tolerance which is often modeled as 2-edge or 2-vertex connectivity is another desired feature in many applications. In this paper, we study the fault tolerant dual power assignment problem. With the assumption of dual universal transmission power levels, we aim to minimize the total number of nodes assigned to high power level such that the resultant network topology is 2-edge or 2-vertex connected. As the problems are NP-hard, we design a novel algorithm to compute nearly-optimal solutions. From the theoretical perspective, we prove that our algorithm can guarantee 3.67-approximation for both 2-edge connectivity and 2-vertex connectivity, which improves the existing best approximation algorithm. We also conduct some numerical experiments which show that results of our algorithm are at most 2 times of optimal solutions in average and have significant improvements compared to that of existing algorithm.

Since the very first work of asymptotic capacity problem in a wireless ad-hoc network, rich variations such as adding mobility, the usage of directional antenna, and introducing infrastructure have been studied. The intention behind adding these technologies is to reduce inter-node interference and the relay burden of nodes because these are the main causes of vanishing throughput in wireless ad- hoc networks. Another way to increase network capacity is to use the utilization of multichannels. However, the most recent result on the capacity of a multichannel ad- hoc network showed that the usage of multichannels and multiple NICs can not break through the same capacity limit as with single channel. More specifically, assuming finite NICs at a node, the per-node throughput of at most Thetaradic(logn/n) can be maintained by utilizing up to Theta(logn/n) channels beyond which capacity loss occurs. In order to give a new perspective on this phenomenon, we define the Minimum Frequencies for the Virtual Maximum MAC Capacity (MFVMC) problem in this paper. The objective of the problem is to find the minimum frequencies to guarantee collision-free transmissions at a given time slot for any maximum matching of a given graph. Focusing our interest to the set of unit disk graphs with the maximum node degree of d, we prove that Theta(d) is the tight bound for the MFVMC problem. We discuss the implication of this result on the asymptotic network capacity in a multichannel ad-hoc network.

Unlike a cellular or wired network, there is no base station or network infrastructure in a wireless ad-hoc network, in which nodes communicate with each other via peer communications. In order to make routing and flooding efficient in such an infrastructureless network, Connected Dominating Set (CDS) as a virtual backbone has been extensively studied. Most of the existing studies on the CDS problem have focused on unit disk graphs, where every node in a network has the same transmission range. However, nodes may have different powers due to difference in functionalities, power control, topology control, and so on. In this case, it is desirable to model such a network as a disk graph where each node has different transmission range. In this paper, we define Minimum Strongly Connected Dominating and Absorbent Set (MSCDAS) in a disk graph, which is the counterpart of minimum CDS in unit disk graph. We propose a constant approximation algorithm when the ratio of the maximum to the minimum in transmission range is bounded. We also present two heuristics and compare the performances of the proposed schemes through simulation.

In this paper, we considered the problem of transporting layered video over erroneous multi-hop wireless networks and proposed a distributed system. Our proposed distributed scheme is comprised of distributed control (DC), distributed buffer (DB) and distributed error control schemes. The DC scheme improves the efficiency of the network bandwidth usage and reduces the end-to-end delay of the streaming application. End-to-end delay jitter can be reduced by proper use of the DB nodes' buffer. Replacing the traditional EEC and ARQ with our distributed FEC and ARQ scheme reduces the error-protection overhead and ARQ delay and improves the wireless channel throughput. A layered video module is developed in GlomoSim 2.03 for video streaming application. We simulated our distributed scheme employing the layered video module in GlomoSim 2.03. Our simulation results confirm that QoS of streaming video over erroneous multi-hop wireless network can be improved using our proposed distributed scheme.

We address the issue of finding a sequence of stable paths using the knowledge of future topology changes. We present an efficient polynomial time algorithm called OptTrans to determine the minimum required number of route transitions for a source-destination (s-d) session. Algorithm OptTrans operates on a simple greedy heuristic: Whenever an s-d path is required at time instant t, choose the longest-living s-d path since t. The above strategy is repeated over the duration of the s-d session. The sequence of such longest living stable paths is called the stable mobile path. Algorithm OptTrans is of O(n/sup 2/T) complexity where n is the number of nodes in the network and T is the duration of the s-d session. To account for the possibility of not knowing the complete knowledge of future topology changes at the time of route selection, we introduce the notion of look-ahead window size /spl Delta/ as the time for which the information about future topology changes are known. We study the performance of algorithm OptTrans by varying /spl Delta/ from O to /spl Delta//sub max/, where /spl Delta//sub max/ is the look-ahead window size beyond which there is no impact on the number of route transitions or the hop count. We also identify the tradeoff between hop count and the number of route transitions and show that both the minimum hop path and the stable path are not likely to be obtainable at the same time. We conclude the paper by presenting a preliminary design of a proactive stable path routing protocol that makes use of the look-ahead window concept proposed here. We explore the stochastic properties of the commonly used random-way point mobility model and propose an efficient technique to dissipate location update broadcasts by each node. We show that there exist a critical number of s-d sessions above which the location-update overhead in our proactive stable path routing approach would be less than the broadcast-based on-demand route discovery overhead.

Loss of connectivity to even node is significant in peer-to-peer ad hoc networks as any node can become a source or destination. Accordingly, we define the network lifetime as the time by which the first node runs out of battery power. Conditional min-max battery cost routing (CMMBCR) [C.K. Toh, 2001] is a generic power-aware routing algorithm proposed to strike a balance between the contrasting objectives of maximizing the node lifetimes and minimizing the energy consumption. CMMBCR works by defining a battery protection threshold /spl gamma/ to switch between a routing scheme in which the total energy consumption is minimized and a routing scheme in which the minimum residual energy of any node on the route is maximized. In an on-demand power-aware routing protocol, existing routes have to be changed/refreshed to take into account of the available battery power of the nodes and extend the time at which the nodes run out of their battery power. Very few works have studied the performance of an on-demand distributed version of CMMBCR. We claim that the route refresh frequency is critical to the performance of CMMBCR and it has to be chosen depending on the battery protection threshold /spl gamma/ and the level of node mobility. We also claim that when the network topology changes dynamically (moderate to high mobility), there is no need to do route discovery to refresh an existing route. Mobility itself guarantees that an existing route is short-lived and the residual battery levels of the nodes can be learnt when a route discovery is done due to route failures. Our simulation results are based on implementing CMMBCR on the top of DSR in ns-2 [K, Fall et al, 2001]. We study the impact of the route refresh frequency on the network lifetime and end-to-end delay per packet under different values of /spl gamma/, node mobility and offered traffic load. The results presented in this paper can aid in the on-demand performance study of existing power aware routing algorithms in mobile ad hoc networks.

We present a method that offers a simple way of estimating the availability of routes, trees or other subnetworks with dependent links. Such dependencies typically exist in ad hoc networks, where the evaluation of global availability is important for ensuring end-to-end quality of service. The method is presented in a general form, so that it can also be applied to many other scenarios.

A method is presented to compute a fundamental traffic engineering parameter, the end-to-end blocking probability, when both traffic and reliability aspects are taken into account. Additionally, link failures are not assumed independent. This situation is justified by the practical scenario of logical network, even if the physical link failures are independent, after mapping the failures into the logical network, the logical links do not fail independently. Dependent link failures can also occur as a result of a node failure.

The authors (Fumagalli and Tacca (2001)) introduced the concept of differentiated reliability (DiR) applied to dedicated path protection (DPP) switching in wavelength division multiplexing (WDM) rings. By means of the DiR concept, a network can be designed to provide multiple degrees of reliability and efficiently satisfy the user-specific requirements, yet minimizing the network total cost. This paper extends the DiR concept to the case of shared path protection (SPP) switching in arbitrary (mesh) topology, the so called SPP-DiR. A time efficient algorithm is proposed to determine the primary and backup path of each demand in both conventional SPP and SPP-DiR (WDM) networks. When compared to DPP, results obtained for the pan-European network by using the proposed algorithm indicate cost reductions of about 16% when SPP is applied, and up to 34% when SPP-DiR is applied.

MERIT is a framework to assess routing protocols in mobile Ad hoc networks (manets). It is based on the novel concept of a shortest mobile path (SMP) in a mobile qraph, generalizing the traditional shortest path concept for the mobile environment. As a standard measure for routing protocols in a manet, the MERIT framework proposes the mean ratio of the cost of the actually used route to the cost of the optimal mobile path, under the same history of link metrics in the changing network topology. The MERIT spectrum takes the MERIT ratio as a function of parameters of interest yielding a multi-faceted representation of protocol effectiveness. This Mean Real vs. Ideal cosT (MERIT) framework is unifying in that it provides a measure that allows a protocol to be assessed independently of other protocols, within its own environment. We show that there is an efficient algorithm to solve the underlying SMP problem for important cases, making the approach practically feasible. We also investigate generalizations of and extensions within the MERIT framework.

A systematic and automatic method for dynamically optimizing medium access control (MAC) protocol parameters is presented. Our meta-protocol approach is capable of performing on-line optimization of critical MAC parameters without knowing in advance what network conditions will arise or how they may fluctuate over time. Furthermore, this dynamic optimization is achieved without any centralized control or exchange of control messages between nodes. The power of the new technique is demonstrated by two examples. In a LAN environment, it outperforms traditional contention based MAC protocols that adjust retransmission probabilities, e.g., employing binary exponential backoff. In a synchronous multi-hop environment, it automatically converges to the proper transmission schedule assignments for the actual node density.

A simple, robust, explicit upper bound is derived on the blocking probability for general multirate traffic, dropping a number of traditional assumptions, such as Poisson arrivals, while still maintaining optimally tight exponent of the estimation. The new approach also makes it possible to the estimate blocking probability under incomplete information. Furthermore, it remains valid in situations when the individual call bandwidth demands aggregate in complex, nonlinear ways, e.g., in case of compressible flows, priority classes or processing constraints. We show that the bound is easily applicable for fast, robust link dimensioning. Moreover, it is very well fitted for embedding into more sophisticated network optimization problems, due to its convexity properties.

A systematic and automatic method to dynamically combine any set of existing MAC protocols into a single higher layer, or meta-MAC protocol, is presented. The new approach makes it possible to always achieve the performance of the best component protocol, without knowing in advance which protocol will match the potentially changing and unpredictable network conditions. Moreover, this dynamic optimization is entirely automatic and runs without any centralized control or any exchange of messages, using only local network feedback information. We describe the method and prove that the resulting meta-MAC protocol achieves optimal performance in a well-defined sense. Through simulation on different types of networks and with different component MAC protocols, we demonstrate that our simple and practical combination algorithm yields highly adaptive and scalable MAC solutions.

A method is presented to find routes for UBR (unspecified bit rate) circuits in ATM networks to make UBR traffic well-balanced. It selects an optimal path for each UBR circuit, while avoiding the potential problem of selecting the same optimal path or subpath repeatedly for different circuits. This is achieved by choosing an optimal path uniformly at random from the set of all optimal paths, according to any user-selected metric. Since the set of potential paths is exponentially large and has a complex structure, a new tool is needed to select a path uniformly at random from the set of all optimal paths efficiently. We propose a solution whose complexity is only that of shortest path selection, and we prove that it selects any optimal path with equal probability, thus providing good load balancing among candidate routes. Given the efficiency of the proposed solution and the above properties of the resulting paths selection, we believe the solution can be a practical approach to load balancing of UBR circuits in ATM networks.

An algorithm is presented for designing the logical topology of the virtual path (VP) network, an important task in ATM network design. We prove that the algorithm provides a VP network topology that is asymptotically optimal with respect to both connectivity and the diameter of the network. These optimality properties are combined with algorithmic simplicity and polynomial running time, thus overcoming the notorious "optimality vs. scalability" dilemma. This result is made possible by applying the theory of random graphs to this type of networks. This theory has the methodological advantage of increased accuracy with growing network size, thus turning the "curse of dimensionality" into a blessing. Therefore, the paper exemplifies that the theory of random graphs, beyond supporting analysis purposes, may serve as a useful tool in the design of algorithms that overcome the "scalability bottleneck", a problem that prevents current approaches from finding near-optimal solutions as today's networks grow in size and complexity.

We analyze the worst-case behavior of general connection-oriented networks, with first-in-first-out (FIFO) queueing policy, forwarding packets along an arbitrary system of routes. A worst-case bound is proven for the end-to-end queueing delay and buffer size needed to guarantee loss-free packet delivery, given that sources satisfy a given source rate condition. The results are based on a novel deterministic approach and help in reconciling the discrepancy between the unstable worst-case behavior of FIFO-based networks and their good practical performance.

The task of supporting integrated multi-rate multimedia traffic in a bandwidth poor wireless environment poses a unique and challenging problem for network managers. In this paper we propose a novel bandwidth allocation strategy which partitions the available bandwidth amongst the different traffic classes in a manner that ensures quality of service (QoS) guarantees for digital video while minimizing the maximum blocking probability for voice and data connections. At the connection level, optimum utilization of the reserved bandwidth is achieved through intra-frame statistical multiplexing, while at the system-level, the delicate task of partitioning the bandwidth is accomplished by developing an efficient algorithm which uses traffic parameters consisting only of aggregate traffic load and the total available bandwidth. The algorithm built on non-trivial mathematical results, is simple, robust, and well suited for practical implementations.

This paper addresses the issue of how to solve convex programming problems by analog artificial neural networks (ANNs), with applications in asynchronous transfer mode (ATM) resource management. We first show that the essential and difficult optimization problem of dimensioning the system of virtual subnetworks in ATM networks can be modeled as a convex programming task. Here the transformation of the problem into a convex programming task is a nontrivial step. We also present and analyze an analog ANN architecture that is capable of solving such convex programming tasks with time-varying penalty multipliers. The latter property makes it possible to perform quick sensitivity analysis with respect to the constraints in order to identify the bottleneck capacities in the network or those which give the highest return if we invest in extending them.

This paper introduces a novel technique called protocol threading, yielding a deterministic protocol that gives a guaranteed upper bound on the transmission delay of each packet at every node in a multihop mobile network. By eliminating the maximum degree constraint, the new method improves upon existing time-spread multiple-access (TSMA)-type protocols while preserving the advantages of the deterministic operation and topology transparency. We introduce the protocol threading solution, derive the maximum delay bound in a mobile topology, and analyze the performance of the protocol.

We address the problem of efficient circuit switching in wide area optical networks. The solution provided is based on finding optimal routes for lightpaths and the new concept of semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining together several lightpaths, using wavelength conversion at their junctions. A fast and practical algorithm is presented to optimally route lightpaths and semilightpaths taking into account both the cost of using the wavelengths on links and the cost of wavelength conversion. We prove that the running time of the algorithm is the best possible in the wide class of algorithms allowing linear algebraic operations on weights. This class encompasses all known related practical methods. Additionally, our method works for any physical realization of wavelength conversion, independently whether it is done via optoelectronic conversion or in a fully optical way.

A mathematical model is presented that provides a well-defined formulation of the logical configuration problem of ATM networks (the carriers of future B-ISDN) with the objective of maximizing the total expected network revenue, given the physical network parameters and the traffic requirements of each virtual subnetwork. A two-phase solution procedure is developed in which the decision variables are the logical link capacities that specify the logical decomposition into virtual subnetworks, and the load sharing parameters. The first phase of the solution finds a global optimum in a rougher model. The second phase uses this as an initial point for a gradient-based hill climbing that applies the partial derivatives of the network revenue function obtained in a more refined model.>

A topology transparent protocol for link activation in mobile CDMA networks is presented. The protocol resolves primary and secondary conflicts, and can easily be adapted to TDMA link activation, as well. The proposed protocol guarantees that each link will be successfully activated at least once in a frame without the need to adjust transmission schedules in mobile environments. Compared to other protocols with guaranteed delivery, the overhead due to the recomputation of transmission schedules is eliminated and, accordingly, transmissions need not be suspended for schedule reorganization. Furthermore, contrary to previously known protocols that adapt to mobility by schedule recomputation, the proposed solution is not subject to a potential catastrophic failure when the rate of topology changes exceeds the rate at which schedules can be readjusted. We prove the correctness and evaluate the efficiency of the new protocol by analytical methods.>

A multiple access packet communication model is analyzed in which the users can receive packets on more than one common channel. For this type of system, a new channel access protocol is presented. The authors prove that under heavy homogeneous load the protocol guarantees the maximum achievable throughput among all possible protocols. The general model can be applied to different systems, according to various realizations of the logical channels. For example, in packet radio networks the channels can be realized by different carrier frequencies (FDMA) or by different codes (CDMA). The simplicity and optimality of the protocol make it attractive for practical applications.>

Transmissions scheduling is a key design problem in packet radio networks, relevant to TDMA and CDMA systems. A large number of topology-dependent scheduling algorithms are available, in which changes of topology inevitably require recomputation of transmission schedules. The need for constant adaptation of schedules to mobile topologies entails significant, sometime insurmountable, problems. These are the protocol overhead due to schedule recomputation, performance penalty due to suspension of transmissions during schedule reorganization, exchange of control message and new schedule broadcast. Furthermore, if topology changes faster than the rate at which new schedules can be recomputed and distributed, the network can suffer a catastrophic failure. The authors propose a robust scheduling protocol which is unique in providing a topology transparent solution to scheduled access in multi-hop mobile radio networks. The proposed solution adds the main advantages of random access protocols to scheduled access. Similarly to random access it is robust in the presence of mobile nodes. Unlike random access, however, it does not suffer from inherent instability, and performance deterioration due to packet collisions. Unlike current scheduled access protocols, the transmission schedules of the proposed solution are independent of topology changes, and channel access is inherently fair and traffic adaptive.>

The virtual path (VP) concept is known to be a powerful transport mechanism for ATM networks. This paper deals with the optimization of the virtual paths system from a bandwidth utilization perspective. While previous research on VP management has basically assumed that bandwidth in ATM networks is unlimited, emerging technologies and applications are changing this premise. In many networks, such as wireless, bandwidth is always at a premium. In wired networks, with increasing user access speeds, less than a dozen of broadband connections can saturate even a Gigabit link. We present an efficient algorithm that finds a system of VP routes for a given set of VP terminators and VP capacity demands. This solution is motivated by the need to minimize the load, or reduce congestion, generated by the VP's on individual links. A nontrivial performance guarantee is proven for the quality of the proposed solution and numerical results show that the proposed solution carries the potential for a near optimal allocation of VPs.>

A fast nearest-neighbor algorithm is presented. It works in general spaces in which the known cell techniques cannot be implemented for various reasons, such as the absence of coordinate structure or high dimensionality. The central idea has already appeared several times in the literature with extensive computer simulation results. An exact probabilistic analysis of this family of algorithms that proves its O(1) asymptotic average complexity measured in the number of dissimilarity calculations is presented.>

In statistical pattern recognition, a classifier is called universally consistent if its error probability converges to the Bayes-risk as the size of the training data grows for all possible distributions of the random variable pair of the observation vector and its class. It is proven that if a one-layered neural network with properly chosen number of nodes is trained to minimize the empirical risk on the training data, then a universally consistent classifier results. It is shown that the exponent in the rate of convergence does not depend on the dimension if certain smoothness conditions on the distribution are satisfied. That is, this class of universally consistent classifiers does not suffer from the curse of dimensionality. A training algorithm is presented that finds the optimal set of parameters in polynomial time if the number of nodes and the space dimension is fixed and the amount of training data grows.>