Full exploitation of the bandwidth resources of Wireless Networks is challenging because of the sharing of the radio medium among neighboring nodes. Practical algorithms and distributed schemes that tries to optimising the use of the network radio resources. In this technical report we present the proof that maximising the network capacity is is an APX Complete problem (not approximable within 1 (1 - 2^(-k)) - eps for eps > 0).
In a wired network, finding an elementary path between two nodes minimizing over-loaded nodes can be solved by using the distributed and polynomial dijkstra algorithm @cite_5 . In a wireless network, this problem is the Remaining Capacity problem ( ) defined in @cite_21 . @cite_15 @cite_25 , authors show that finding the shortest path (repectively longest path) that avoid over-loaded nodes cannot be solved in a polynomial time. Centralized heuristics are proposed in @cite_4 . Moreover, experimental studies aim at increasing the capacity of the network @cite_9 (i.e. we call network capacity the cumulated data rate flows present in the network) by giving the best routing decisions (distributed routing protocols) that avoids using over-loaded nodes, see @cite_4 @cite_17 @cite_2 @cite_16 @cite_10 @cite_14 . @cite_22 , authors try to decreased the maximum load with curve routing. This routing needs the knowledge of the geographical localization of nodes.
@cite_14 @cite_4 @cite_22 @cite_9 @cite_21 @cite_2 @cite_5 @cite_15 @cite_16 @cite_10 @cite_25 @cite_17
2089499640 1970554468 2117065758 2028069703 2132734927 2131992719 2040273581 2042123165 2963528540 2104060777 2949588463 2950317007
We address the problem of balancing the traffic load in multi-hop wireless networks. We consider a point-to-point communicating network with a uniform distribution of source-sink pairs. When routing along shortest paths, the nodes that are centrally located forward a disproportionate amount of traffic. This translates into increased congestion and energy consumption. However, the maximum load can be decreased if the packets follow curved paths. We show that the optimum such routing scheme can be expressed in terms of geometric optics and computed by linear programming. We then propose a practical solution, which we call Curveball Routing which achieves results not much worse than the optimum. We evaluate our solution at three levels of fidelity: a Java high-level simulator, the ns2 simulator, and the Intel Mirage Sensor Network Testbed. Simulation results using the high-level simulator show that our solution successfully avoids the crowded center of the network, and reduces the maximum load by up to 40 . At the same time, the increase of the expected path length is minimal, i.e., only 8 on average. Simulation results using the ns2 simulator show that our solution can increase throughput on moderately loaded networks by up to 15 , while testbed results show a reduction in peak energy usage by up to 25 . Our prototype suggests that our solution is easily deployable. The throughput of wireless networks can be significantly improved by multi-channel communications compared with single-channel communications since the use of multiple channels can reduce interference influence. In this paper, we study interference-aware topology control and QoS routing in IEEE 802.11-based multi-channel wireless mesh networks with dynamic traffic. Channel assignment and routing are two basic issues in such networks. Different channel assignments can lead to different network topologies. We present a novel definition of co-channel interference. Based on this concept, we formally define and present an effective heuristic for the minimum INterference Survivable Topology Control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all K-connected topologies. We then formulate the Bandwidth-Aware Routing (BAR) problem for a given network topology, which seeks routes for QoS connection requests with bandwidth requirements. We present a polynomial time optimal algorithm to solve the BAR problem under the assumption that traffic demands are splittable. For the non-splittable case, we present a maximum bottleneck capacity path routing heuristic. Simulation results show that compared with the simple common channel assignment and shortest path routing approach, our scheme improves the system performance by 57 on average in terms of connection blocking ratio. This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs (s i ,t i ) , what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics. We propose a routing strategy to improve the transportation efficiency on complex networks. Instead of using the routing strategy for shortest path, we give a generalized routing algorithm to find the so-called efficient path, which considers the possible congestion in the nodes along actual paths. Since the nodes with the largest degree are very susceptible to traffic congestion, an effective way to improve traffic and control congestion, as our strategy, can be redistributing traffic load in central nodes to other noncentral nodes. Simulation results indicate that the network capability in processing traffic is improved more than 10 times by optimizing the efficient path, which is in good agreement with the analysis. DOI: 10.1103 PhysRevE.73.046108 PACS numbers: 89.75.Hc Since the seminal work on scale-free networks by Barabasi and Albert BA model1 and on the small-world phenomenon by Watts and Strogatz 2, the structure and dynamics of complex networks have recently attracted a tremendous amount of interest and attention from the physics community see the review papers 3‐5 and references therein. The increasing importance of large communication networks such as the Internet 6, upon which our society survives, calls for the need for high efficiency in handling and delivering information. In this light, to find optimal strategies for traffic routing is one of the important issues we have to address. There have been many previous studies to understand and control traffic congestion on networks, with a basic assumption that the network has a homogeneous structure 7‐11. However, many real networks display both scale-free and small-world features, and thus it is of great interest to study the effect of network topology on traffic flow and the effect of traffic on network evolution. present a formalism that can cope simultaneously with the searching and traffic dynamics in parallel transportation systems 12. This formalism can be used to optimize network structure under a local search algorithm, while to obtain the formalism one should know the global information of the whole networks. Holme and Kim provide an in-depth analysis on the vertex edge overload cascading breakdowns based on evolving networks, and suggest a method to avoid Load balanced routing in a network, i.e., minimizing the maximum traffic load any node carries for unsplittable flows, is a well known NP-hard problem. Finding practical algorithms remains a long standing challenge. In this paper we propose greedy routing using virtual coordinates that achieves both small path stretch ratio (compared to shortest path) and small load balancing ratio (compared to optimal load balanced routing), in a large scale wireless sensor network deployed densely inside a geometric domain with complex shape. We first provide a greedy routing scheme on a disk with a stretch ratio of at most 2, and under which the maximum load is a factor 4√2 smaller than the maximum load under shortest path routing. This is the first simple routing scheme with a small stretch that has been proven to outperform shortest path routing in terms of load balancing. Then we transform a network of arbitrary shape to a disk by an area preserving map φ. We show that both the path length and the maximum traffic load in the original network only increases by an additional factor of d2, where d is the maximum length stretch of φ. Combined with the result on a disk we again achieve both bounded stretch and bounded load balancing ratio. Our simulation results evaluated the practical performance on both quality measures. We consider the problem of determining rates of growth for the maximum stable throughput achievable in dense wireless networks. We formulate this problem as one of finding maximum flows on random unit-disk graphs. Equipped with the max-flow min-cut theorem as our basic analysis tool, we obtain rates of growth under three models of communication: (a) omnidirectional transmissions; (b) "simple" directional transmissions, in which sending nodes generate a single beam aimed at a particular receiver; and (c) "complex" directional transmissions, in which sending nodes generate multiple beams aimed at multiple receivers. Our main finding is that an increase of Θlog2n in maximum stable throughput is all that can be achieved by allowing arbitrarily complex signal processing (in the form of generation of directed beams) at the transmitters and receivers. We conclude therefore that neither directional antennas, nor the ability to communicate simultaneously with multiple nodes, can be expected in practice to effectively circumvent the constriction on capacity in dense networks that results from the geometric layout of nodes in space. We study approximate distributed solutions to the weighted all-pairs shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. A deterministic (1+epsilon)-approximation to APSP with running time O(e-2n log n) rounds. The best previously known algorithm was randomized and slower by a Theta(log n) factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and that are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of o(n log n). In the relabeling model, we obtain the following results. A randomized O(k)-approximation to APSP, for any integer k>1, running in O(n1 2+1 k+D) rounds, where D is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from O(k log k) to O(k). Also, the new algorithm uses O(log n)-bit labels, which is asymptotically optimal. A randomized O(k)-approximation to APSP, for any integer k>1, running in time O((nD)1 2 n1 k+D) and producing compact routing tables of size O(n1 k). The node labels consist of O(k log n) bits. This improves on the approximation ratio of Theta(k2) for tables of that size achieved by the best previously known algorithm, which terminates faster, in O(n1 2+1 k+D) rounds. In addition, we improve on the time complexity of the best known deterministic algorithm for distributed approximate Steiner forest. This paper considers the problem of finding minimum-energy cooperative routes in a wireless network with variable wireless channels. We assume that each node in the network is equipped with a single omnidirectional antenna and, motivated by the large body of physical layer research indicating its potential utility, that multiple nodes are able to coordinate their transmissions at the physical layer in order to take advantage of spatial diversity. Such coordination, however, is intrinsically intertwined with routing decisions, thus motivating the work. We first formulate the energy cost of forming a cooperative link between two nodes based on a two-stage transmission strategy assuming that only statistical knowledge about channels is available. Utilizing the link cost formulation, we show that optimal static routes in a network can be computed by running Dijkstra's algorithm over an extended network graph created by cooperative links. However, due to the variability of wireless channels, we argue that a many-to-one cooperation model in static routing is suboptimal. Hence, we develop an opportunistic routing algorithm based on many-to-many cooperation, and show that optimal routes in a network can be computed by a stochastic version of the Bellman-Ford algorithm. We use static and opportunistic optimal algorithms as baselines to develop heuristic link selection algorithms that are energy efficient while being computationally simpler than the optimal algorithms. We simulate our algorithms and show that while optimal cooperation and link selection can reduce energy consumption by almost an order of magnitude compared to non-cooperative approaches, our simple heuristics achieve similar energy savings while being computationally efficient as well. We study computing all-pairs shortest paths (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits (1+o(1))-approximation &#xd5;(n)-time algorithms [2], [3], which are matched with &#x3a9;(n)-time lower bounds [4], [5], , &#xd5; and &#x3a9; hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios. . No &#x3a9;(n) lower bound or o(m) upper bound were known for exact computation.In this paper, we present an &#xd5;(n^ 5 4 )-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are asymmetric (a.k.a. the directed case where communication is bidirectional). Our techniques also yield an &#xd5;(n^ 3 4 k^ 1 2 +n)-time algorithm for the k-source shortest paths problem where we want every node to know distances from k sources; this improves Elkins recent bound [6] when k= &#x3a9;(n^ 1 4 ).We achieve the above results by developing distributed algorithms on top of the classic scaling technique, which we believe is used for the first time for distributed shortest paths computation. One new algorithm which might be of an independent interest is for the reversed r-sink shortest paths problem, where we want every of r sinks to know its distances from all other nodes, given that every node already knows its distance to every sink. We show an &#xd5;(n&#x221a; r )-time algorithm for this problem. Another new algorithm is called short range extension, where we show that in &#xd5;(n&#x221a; h ) time the knowledge about distances can be extended for additional h hops. For this, we use weight rounding to introduce small additive errors which can be later fixed. This paper studies a multi-facility network synthesis problem, called the Two-level Network Design (TLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks. We are given an undirected network containing two types of nodes---primary and secondary---and fixed costs for installing either a primary or a secondary facility on each edge. Primary nodes require higher grade interconnections than secondary nodes, using the more expensive primary facilities. The TLND problem seeks a minimum cost connected design that spans all the nodes, and connects primary nodes via edges containing primary facilities; the design can use either primary or secondary edges to connect the secondary nodes. The TLND problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we study the relationship between alternative model formulations for this problem (e.g., directed and undirected models), and analyze the worst-case performance for a composite TLND heuristic based upon solving embedded subproblems (e.g., minimum spanning tree and either Steiner tree or shortest path subproblems). When the ratio of primary to secondary costs is the same for all edges and when we solve the embedded subproblems optimally, the worst-case performance ratio of the composite TLND heuristic is 4 3. This result applies to the hierarchical network design problem with constant primary-to-secondary cost ratio since its subproblems are shortest path and minimum spanning tree problems. For more general situations, we express the TLND heuristic worst-case ratio in terms of the performance of any heuristic used to solve the embedded Steiner tree subproblem. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of a multi-level extension of this problem. We study approximate distributed solutions to the weighted all-pairs-shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. @math A deterministic @math -approximation to APSP in @math rounds. This improves over the best previously known algorithm, by both derandomizing it and by reducing the running time by a @math factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and require that these names are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of @math . In the relabeling model, we obtain the following results. @math A randomized @math -approximation to APSP, for any integer @math , running in @math rounds, where @math is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from @math to @math . Also, the new algorithm uses uses labels of asymptotically optimal size, namely @math bits. @math A randomized @math -approximation to APSP, for any integer @math , running in time @math and producing compact routing tables of size @math . The node lables consist of @math bits. This improves on the approximation ratio of @math for tables of that size achieved by the best previously known algorithm, which terminates faster, in @math rounds. We consider the adaptive shortest-path routing problem in wireless networks under unknown and stochastically varying link states. In this problem, we aim to optimize the quality of communication between a source and a destination through adaptive path selection. Due to the randomness and uncertainties in the network dynamics, the quality of each link varies over time according to a stochastic process with unknown distributions. After a path is selected for communication, the aggregated quality of all links on this path (e.g., total path delay) is observed. The quality of each individual link is not observable. We formulate this problem as a multi-armed bandit with dependent arms. We show that by exploiting arm dependencies, a regret polynomial with network size can be achieved while maintaining the optimal logarithmic order with time. This is in sharp contrast with the exponential regret order with network size offered by a direct application of the classic MAB policies that ignore arm dependencies. Furthermore, our results are obtained under a general model of link-quality distributions (including heavy-tailed distributions) and find applications in cognitive radio and ad hoc networks with unknown and dynamic communication environments.