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

2.
The IEEE 802.11 MAC protocol now prevailing in wireless LANs is vulnerable to selfish backoff attacks consisting in selection of short backoff times in the constituent CSMA/CA procedure. Administrative prevention of such attacks fails in ad hoc configurations, where stations' behavior cannot be mandated. In this paper we take an incentive-oriented game-theoretic approach whereby stations are allowed to maximize their payoffs (achieved success rates). Using a fairly accurate performance model we show that a noncooperative CSMA/CA game then arises with a payoff structure characteristic of a Prisoners' Dilemma. For a repeated CSMA/CA game, a novel SPELL strategy is proposed and shown to yield to simple algorithmic design. Assuming that the stations are rational players and wish to maximize a mean-value-type long-term utility, SPELL is further shown to deter a single attacker by providing a disincentive to deviate from SPELL.  相似文献   

3.
Analysis of IEEE 802.11 non-saturated DCF by matrix analytic methods   总被引:1,自引:0,他引:1  
In the IEEE 802.11 MAC layer protocol, the basic access method is the Distributed Coordination Function based on the CSMA/CA. In this paper, we investigate the analytic performance of IEEE 802.11 DCF in the non-saturation mode. We assume that there is a fixed number n of competing stations and the packet arrival process to each station is a Poisson process. We model IEEE 802.11 DCF in non-saturation mode by a 3-dimensional Markov chain and derive the steady state probability of the Markov chain by applying the matrix analytic method. We obtain the probability generating function of Head-of-Line delay (HoL-delay), non-saturation throughput and packet loss probability. Our results can be used for finding the optimal number of stations that can be accommodated while satisfying a given QoS requirement. This research is supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).  相似文献   

4.
5.
The topology of a mobile wireless network changes over time. Maintaining routes between all nodes requires the continuous transmission of control information, which consumes precious power and bandwidth resources. Many routing protocols have been developed, trading off control overhead and route quality. In this paper, we ask whether there exist low‐overhead schemes that produce low‐stretch routes, even in large networks where all the nodes are mobile. We present a scheme that maintains a hierarchical structure within which constant‐stretch routes can be efficiently computed between every pair of nodes. The scheme rebuilds each level of the hierarchy periodically, at a rate that decreases exponentially with the level of the hierarchy. We prove that this scheme achieves constant stretch under a mild smoothness condition on the nodal mobility processes. Furthermore, we prove tight bounds for the network‐wide control overhead under the additional assumption of the connectivity graph forming a doubling metric space. Specifically, we show that for a connectivity model combining the random geometric graph with obstacles, constant‐stretch routes can be maintained with a total overhead of bits of control information per time unit. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 669–709, 2015  相似文献   

6.
Transmitters and receivers are the basic elements of wireless networks and are characterized by a number of radio-electrical parameters. The generic planning problem consists of establishing suitable values for these parameters so as to optimize some network performance indicator. The version here addressed, namely the Power Assignment Problem (pap), is the problem of assigning transmission powers to the transmitters of a wireless network so as to maximize the satisfied demand. This problem has relevant practical applications both in radio-broadcasting and in mobile telephony. Typical solution approaches make use of mixed integer linear programs with huge coefficients in the constraint matrix yielding numerical inaccuracy and poor bounds, and so cannot be exploited to solve large instances of practical interest. In order to overcome these inconveniences, we developed a two-phase heuristic to solve large instances of pap, namely a constructive heuristic followed by an improving local search. Both phases are based on successive shortest path computations on suitable directed graphs. Computational tests on a number of instances arising in the design of the national Italian Digital Video Broadcasting (DVB) network are presented.  相似文献   

7.
We analyze the performance of CSMA in multi-channel wireless networks, accounting for the random nature of traffic. Specifically, we assess the ability of CSMA to fully utilize the radio resources and in turn to stabilize the network in a dynamic setting with flow arrivals and departures. We prove that CSMA is optimal in the ad-hoc mode, when each flow goes through a unique dedicated wireless link from a transmitter to a receiver. It is generally suboptimal in infrastructure mode, when all data flows originate from or are destined to the same set of access points, due to the inherent bias of CSMA against downlink traffic. We propose a slight modification of CSMA that we refer to as flow-aware CSMA, which corrects this bias and makes the algorithm optimal in all cases. The analysis is based on some time-scale separation assumption which is proved valid in the limit of large flow sizes.  相似文献   

8.
9.
In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.  相似文献   

10.
11.
This is a summary of the authors PhD thesis supervised by Hervé Rivano and defended on 29 October 2009 at the Université de Nice-Sophia Antipolis. The thesis is written in French and is available from . This work deals with the optimization of the capacity of wireless mesh networks, defined as the throughput offered to each flow. We develop optimization models integrating the cross-layer characteristics of radio communications. The joint routing and scheduling is studied and solved using column generation. A linear formulation focusing on the transport capacity available on the network cuts is derived. We prove the equivalence of the models, and adapt the resolution method into a cross line and column generation process. Thorough tests, a contention area located around the gateways which constraints the capacity is highlighted. These results are applied to a quantitative study of the effects of acknowledgments on the capacity. Finally, a stability study of a protocol routing a traffic injected arbitrarily is investigated.  相似文献   

12.
One of the most critical issues in wireless sensor networks is represented by the limited availability of energy on network nodes; thus, making good use of energy is necessary to increase network lifetime. In this paper, we define network lifetime as the time spanning from the instant when the network starts functioning properly, i.e., satisfying the target level of coverage of the area of interest, until the same level of coverage cannot be guaranteed any more due to lack of energy in sensors. To maximize system lifetime, we propose to exploit sensor spatial redundancy by defining subsets of sensors active in different time periods, to allow sensors to save energy when inactive. Two approaches are presented to maximize network lifetime: the first one, based on column generation, must run in a centralized way, whereas the second one is based on a heuristic algorithm aiming at a distributed implementation. To assess their performance and provide guidance to network design, the two approaches are compared by varying several network parameters. The column generation based approach typically yields better solutions, but it may be difficult to implement in practice. Nevertheless it provides both a good benchmark against which heuristics may be compared and a modeling framework which can be extended to deal with additional features, such as reliability.  相似文献   

13.
We establish an O(nlog2n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(nlogn). The fastest previously known algorithm for this problem works in time O(n3/2). Using our broadcasting algorithm, we develop an O(n3/2log2n) algorithm for gossiping in the same network model.  相似文献   

14.
In this paper, we present a new model that combines quality of service and mobility aspects in wireless ATM networks. Namely, besides the hop count and load parameters of the basic ATM layouts, we introduce a new notion of distance that estimates the time needed to reconstruct the virtual channel of a wireless user when he moves through the network. Quality of service guarantee dictates that the rerouting phase must be imperceptible, that is, the maximum distance between two virtual channels must be maintained as low as possible. Therefore, a natural combinatorial problem arises in which suitable trade-offs must be determined between the different performance measures. We first show that establishing the existence of a layout with maximum hop count h, load l and distance d is NP-complete, even in the very restricted case h=2, l=1 and d=1. We then provide optimal layout constructions for basic interconnection networks, such as chains and rings.  相似文献   

15.
We study a combinatorial geometric problem related to the design of wireless networks with directional antennas. Specifically, we are interested in necessary and sufficient conditions on such antennas that enable one to build a connected communication network, and in efficient algorithms for building such networks when possible.We formulate the problem by a set P of n points in the plane, indicating the positions of n transceivers. Each point is equipped with an α-degree directional antenna, and one needs to adjust the antennas (represented as wedges), by specifying their directions, so that the resulting (undirected) communication graph G is connected. (Two points p,qP are connected by an edge in G, if and only if q lies in p?s wedge and p lies in q?s wedge.) We prove that if α=60°, then it is always possible to adjust the wedges so that G is connected, and that α?60° is sometimes necessary to achieve this. Our proof is constructive and yields an time algorithm for adjusting the wedges, where k is the size of the convex hull of P.Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if α=90°, then it is always possible to adjust the wedges so that G contains a Hamiltonian path. We give an alternative proof to this, which is interesting, since it produces paths of a different nature than those produced by the construction of Fekete and Woeginger. We also show that for any n and ε>0, there exist sets of points such that G cannot contain a Hamiltonian path if α=90°−ε.  相似文献   

16.
17.
One method for improving wireless network throughput involves using directional antennas to increase signal gain and/or decrease interference. The physical layer models used in current networking simulators only minimally address the interaction of directional antennas and radio propagation. This paper compares the models found in popular simulation tools with measurements taken across a variety of links in multiple environments. We find that the effects of antenna direction are significantly different from those predicted by the models used in the common wireless network simulators. We propose a parametric model that better captures the effects of different propagation environments on directional antenna systems; we also show that the derived models are sensitive to both the direction of signal gain and the environment in which the antenna is used.  相似文献   

18.
Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.  相似文献   

19.
Standard analyses of wireless random access protocols that are available in the literature assume negligible propagation delay between any two nodes. This assumption holds good in reasonably short-range terrestrial RF (radio frequency) wireless networks. On the contrary, in wireless communications involving acoustic wave propagation, as in underwater wireless networks, even short distance propagation has appreciably large propagation delay. This observation has led to several recent simulation and experimental studies on underwater Aloha and slotted-Aloha (S-Aloha) protocols and also a few new proposals on random access protocols for underwater wireless ad hoc networks (UWN). To study the efficiency of more advanced multiaccess communication protocols for UWN, it is important to benchmark their performances with respect to the two basic random access protocols, Aloha and S-Aloha. This paper provides an analytic framework to capture the performance of Aloha and S-Aloha protocols in an underwater environment with high and random internodal signal propagation delay. The performance of underwater Aloha and S-Aloha are contrasted with those in short-range terrestrial RF wireless networks. The analysis shows that random internodal propagation delay has no effect on the underwater Aloha performance. It also sheds light on the throughput degradation of underwater S-Aloha with a slotting concept that achieves RF S-Aloha equivalent one-slot vulnerability. Additionally, a modified slotting concept is introduced where the slot size is judiciously reduced such that even by allowing some collisions the overall system throughput can be increased. Our calculations show that, with the modified slotting approach up to 17% throughput performance gain can be achieved over the naive (RF S-Aloha equivalent) slotting approach in UWN. Our analytic results are supported by discrete event simulations.  相似文献   

20.
We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号