The basic Binary Exponential Backoff algorithm, Modified Binary Exponential Backoff algorithm and their drawbacks are analyzed and a new variation called Probability Based Backoff algorithm is proposed, which takes network traffic also into consideration. The IEEE 802.11 MAC protocol provides shared access to a wireless channel. This paper uses an analytic model to study the channel capacity – i.e., maximum throughput – when using the basic access (two-way handshaking) method in this protocol. Dec 2, 2017 - Analytical Study of Backoff Algorithms for MAC Protocol in Mobile Ad Hoc Networks. Conference Paper (PDF Available) January 2006 with 16 Reads. Conference: 22nd. Mohamed Ould-Khaoua at Sultan Qaboos University.
We study a wireless sensor network using CSMA/CA in the MAC layer under a backoff attack: some of the sensors of the network are malicious and deviate from the defined contention mechanism. We use Bianchi’s network model to study the impact of the malicious sensors on the total network throughput, showing that it causes the throughput to be unfairly distributed among sensors. We model this conflict using game theory tools, where each sensor is a player. We obtain analytical solutions and propose an algorithm, based on Regret Matching, to learn the equilibrium of the game with an arbitrary number of players. Our approach is validated via simulations, showing that our theoretical predictions adjust to reality. Introduction The remarkable advances and proliferation in wireless networks in recent years have brought a significant interest in the security and threats to these networks. Specially wireless sensor networks can be the target of many different attacks due to the limited capabilities of the sensors, as some recent surveys show (for instance, ,).
A very important kind of attack addressed to these networks is the backoff attack. It affects to the Medium Access Control (MAC) layer when a CSMA/CA (carrier-sense medium access with collision avoidance) scheme is used to regulate the access to the medium. The backoff mechanism minimizes the risk of collision, i.e., that two or more stations transmit simultaneously, by deferring transmissions during a certain random time period: the backoff window. In a backoff attack, a sensor uses a lower backoff window than the rest of the sensors, thus obtaining a higher throughput at expense of the other sensors.
Backoff attacks are a real threat to wireless sensor networks. Firstly, because network adapters are highly programmable , thus allowing sensors to modify their backoff parameters. In addition, secondly, because many MAC layer protocols proposed for wireless sensor networks make use of CSMA as medium access mechanism, for instance, SMAC , WiseMAC , TMAC and DSMAC. Two surveys on MAC layer protocols , show that CSMA is the most common access mechanism in contention based MAC protocols. Some studies that treat backoff attacks, such as , focus only in the defense mechanism. However, any attack is a conflict between the attacker agents and the defense mechanism.
In order to better model this conflict, we will make use of game theory tools: a branch of mathematics used to model conflict. This approach is pretty popular: is a survey on game theory approaches to multiple access situations in wireless networks and is another survey focused on CSMA methods. Two works which study backoff attacks in wireless networks are ,. We differ from these works in the following points and contributions:. We assume that the defense mechanism lies in a sensor, to which other sensors communicate. We model the conflict individually between each communicating sensor—which can behave normally or attack —and the defending sensor.
This is the case of networks with a star topology, in which a central sensor receives the packets of the rest of the network. This topology appears, for instance, in hierarchical routing protocols : in these protocols, the sensors are clustered in order to be energy efficient (one recent example is ), each cluster following a star topology.
Yet our approach could be adapted to other network topologies (e.g., to a mesh); however, we focus in star topology in this work for simplicity. By differentiating between attacking sensors and the defense sensor, we use a heterogeneous network model: the attacking sensors are greedy and want the maximum individual throughput they can obtain, whereas the defending sensor tries to divide fairly the total throughput among the sensors that communicate with it.
This makes our model different from ,: each sensor may have different interests, which is a more complex and realistic situation. We solve our game both analytically and empirically, proposing a simple algorithm to obtain the game solution, based on regret-matching (RM) algorithm. Our contribution here is twofold: on one side, we provide a theoretical framework to the backoff attack problem, and solve it analytically. On the other side, we provide a simple algorithm that learns the solution to the game, which is very simple to implement, even in sensors with low computational capabilities.
This makes our model both well theoretically founded and also, practical to implement in real-life situations. Finally, note that we refer to the sensors as stations if we study the network from the MAC protocol perspective or as players or agents if we are studying the network from the game theoretic perspective. The rest of the work goes as follows. In, we explain the CSMA/CA mechanism as used in the IEEE 802.11 standard. We study this case because there is no standard for MAC layer protocols in wireless sensor networks and the 802.11 defines a very well known CSMA/CA implementation. The results we obtain can be applied to other MAC access mechanisms based on CSMA/CA.
Then, in we will use Bianchi model to obtain the theoretical throughput of the network and show how greedy stations do have a strong impact on the network throughput. In, we model the CSMA/CA problem using game theory tools, and solve it in. After, in, we will simulate the solutions proposed and analyze the results. Finally, in we will draw some conclusions. CSMA/CA in IEEE 802.11 The IEEE 802.11 standard defines the MAC and physical (PHY) layer specifications for a wireless local area network (WLAN). Each device connected using this standard is known as station (STA).
The access to the shared medium can be regulated using the Distributed Coordination Function (DCF), which uses CSMA/CA to access the medium. The basic mechanism used by the DCF in IEEE 802.11 standard is CSMA/CA to control the medium access and a positive acknowledgment frame (ACK): if no ACK is received, there is a retransmission. CSMA/CA operates using two procedures: a carrier sense (CS) which determines whether the channel is busy (i.e., other station is transmitting) or idle (i.e., no other station is transmitting); and a backoff procedure which determines when a station should start transmitting. A station willing to transmit invokes the CS mechanism to determine whether the channel is idle or not. If it is busy, the station defers the transmission until the channel is idle without interruption for a fixed period of time.
After, the station starts a counter, called backoff, for an additional deferral time before transmitting: the station transmits when its backoff counter reaches 0. This procedure minimizes collisions among multiple stations that have been deferring to the same event. The backoff follows a uniform random variable in the interval 0, C W − 1, where CW stands for contention window. If a collision is detected when a station transmits, its CW is duplicated (binary exponential backoff) and the backoff procedure starts over. When the station has transmitted the packet, it waits for an ACK; if none is received in a certain time (ACK timeout), the station starts the transmission procedure again. This mechanism is known as Basic Access (BA), and is based on a two-way handshaking. The standard also defines an alternative procedure, based on a four-way handshaking, called request-to-send/clear-to-send (RTS/CTS).
In this case, the transmitter station sends a RTS frame to the receiver, using the BA mechanism described above. The RTS frame is used to reserve the medium: when the receiver station receives a RTS, proceeds to reserve the channel for some time, sending a CTS frame to indicate that the channel reservation was successful. When the transmitting receives the CTS frame, starts transmitting its packet; when it finishes, if the transmission was successful, the receiving STA sends a positive ACK. While the channel is reserved, the rest of stations remain silent. The RTS/CTS procedure helps easing the hidden node problem , and provides a higher throughput than the BA mechanism when the MAC payload is large.
Theoretical Network Throughput The 802.11 standard does not provide a way to estimate the network throughput that is achieved. The best-known model to estimate the throughput in a network is Bianchi’s model , which provides expressions both for BA and RTS/CTS mechanisms. The main advantage of this model is that it provides analytical expressions to determine the network throughput. It assumes saturation of the network, that is, that each station always has a packet to transmit. This assumption could be relaxed using more complex models (as ). The CSMA/CA mechanism described in assumes that all stations will respect the backoff procedure. However, the stations can modify their backoff in such a way that they can obtain a higher throughput, at expense of other stations ,.
In order to analyze these effects, we will use Bianchi’s model to estimate the total network throughput. The results will be used in the posterior sections to study how to enforce network throughput fairness.
Academic Conferences: Analytical Study Of Backoff Algorithms For Mac Mac
This model relies on the computation of the following system for each of the i stations of the network. (1) where p i is the collision probability for station i (the probability that station i observes a collision while transmitting a packet, which Bianchi’s model assumes to be constant) and τ i is the probability that station i transmits a packet. The system assumes a binary exponential backoff, where the contention window C W lies in the interval W, C W m a x, where m is the maximum backoff stage, defined as C W m a x = 2 m W where W is the minimum size of the contention window. Let us assume that we have a network with n stations, split into two different classes. There are n 1 stations characterized by using a binary exponential backoff as described by IEEE 802.11 standard, and thus, following. Also, there are n 2 = n − n 1 stations using a uniformly distributed backoff in the range 0, W 2 − 1, whose expression is.
Simulation 1: Network Throughput and Fairness Now, we will make use of the expressions derived in the previous section to analyze the impact of having n 2 stations that follow a uniform backoff, and hence, do not respect the binary backoff procedure. The values used for time durations are the same as in , extracted from 802.11 standard, and can be seen in. Observe that we consider two different payload lengths, a short one, T p, s, and a long one, T p, l. We consider that the stations of class 1 follow the IEEE 802.11 standard binary backoff mechanism (normal stations), with W 1 = C W m i n,1 = 32, C W m a x,1 = 1024 and hence, m 1 = 5. The stations of class 2 (malicious stations) will follow a uniformly distributed backoff in the interval 0, W 2 − 1.
The throughput of normal stations decreases significantly for low values of W 2. This is independent of the number of malicious stations, the mechanism used (BA or RTS/CTS) and the payload size. This happens because the malicious stations use lower backoffs and hence, they have higher chances to win the contention procedure against normal stations. This causes that the throughput is not fairly distributed among stations. As W 2 increases (i.e., the malicious stations behave more similarly to the normal ones) the throughputs difference becomes smaller. If there is only one malicious station, this station consumes the major part of the network throughput for low W 2, because it usually wins the contentions.
This is independent of the mechanism used (BA or RTS/CTS) and the payload size. Yet when there are more than one malicious stations, the total throughput becomes 0 for W 2 = 1, because there are some stations trying to access the network that will always collide.
As the W 2 value increases, we observe that the throughput for the malicious stations also increases, presenting a maximum value which depends on the total number of stations in the network and the W 2 parameter. Also, as n 2 increases, the throughput a malicious station obtains decreases: it is better for a malicious station to be the only malicious station in the network. RTS/CTS mechanism provides higher throughput when using larger payloads: in e–h, RTS/CTS curves are always above BA curves. The opposite happens when using short payloads. Hence, if in a network using CSMA/CA there is one or more stations which can modify the binary exponential backoff procedure used by 802.11, the throughput that each station gets can be seriously affected.
This happens using both BA or RTS/CTS mechanisms. The results obtained in this section show that network fairness is seriously affected by a backoff attack; the next sections will propose a solution to this situation using game theory tools. (12) For our game, the players are the sensors and the actions are to attack or not to attack in case of greedy sensors, and detect a malicious behavior or not for the sensor that is receiving the packets.
We will use discrete sets of actions (i.e., A i are finite sets). Thus, the payoff functions will be discrete. Each of this discrete actions will be denoted as pure actions. Also, if there are N p = 2 players, the payoff functions for each player can be expressed using a matrix R i. The matrices will have dimension m × n, where m is the number of actions for player 1 and n the number of actions for player 2.
Hence, the element r a 1, a 2 of the matrix R i corresponds to the payoff for player i when player 1 plays pure action a 1 and player 2 pure action a 2. A game is said to be a zero-sum game if the sum of the payoffs of all players equals zero, that is, ∑ i u i( a) = 0, ∀ a ∈ A. This means that the gains of some players are the loses of the others, and hence, zero-sum games model situations of extreme competition among players.
In a zero-sum game of two players with a discrete set of actions, the payoff matrix satisfy that R 1 = − R 2 = R: player 1 maximizes the payoffs from R whereas player 2 tries to minimize the same payoff matrix R. If the sum of the payoffs is different from zero, then the game is called non-zero sum game. These games can model very different situations, ranging from extreme competition (i.e, the zero-sum case) until fully cooperative games (i.e., when all players have the same payoff function). Problem Description We use the network scheme in to model the CSMA/CA problem that arises when some stations modify their backoff procedure. There will be n 1 normal stations (NS), which always follow the binary exponential backoff; and n 2 malicious stations (MS), which can choose between using the binary exponential backoff or the uniform backoff. We denote by n the number of stations, with n = n 1 + n 2. All n stations are connected to a gateway, called server, which forwards their packets to a network.
The stations communicate with the server: we only consider the uplink in the problem. Observe that this problem arises in a situation in which a star topology is used. For convenience, we will denote the malicious stations as clients. Network scheme for the case that there are n 1 normal stations (NS) and n 2 malicious stations (MS). NS respect 802.11 binary exponential backoff, whereas MS can choose to use it or to use a uniform backoff.
The players of the game will be the server on one side, and the clients on the other. Thus, there will be N p = n 2 + 1 players (where N p denotes the number of players). Each client tries to maximize the throughput available to it, whereas the server tries to enforce that all stations in the network obtain a fair throughput. By fair, we mean that no station is getting a higher throughput at expense of others.
Under the saturation condition imposed before, this means that all clients receive the same proportion of the total throughput. The clients will have two different actions: either they behave selfishly ( s) by using the uniform backoff or they do not behave selfishly ( n s) by using the binary exponential backoff. The server will also have two actions: it can detect ( d) if the network throughput is begin fairly distributed or not to detect ( n d). If the server detects and catches a client behaving selfishly, it will drop its packet, as a punishment. This means that the client has to send again the packet, and the higher throughput advantage it had obtained by modifying its backoff vanishes. We must also take into account that this detection procedure cannot be free of charge for the server: there must be a cost associated to the detection procedure in terms of computational resources.
Two of the possible schemes that could be used to detect this selfish behavior are , which is based in Kolmogorov-Smirnov (K-S) statistics, and , which is based on a modified Cramer-von Mises (C-M) test. To simplify the modellinfg, we will assume that the server is able to perfectly detect when a station behaves selfishly. Two Player Case: N p = 2 Now, we center in the case when n 2 = 1, that is, there are only two players in the game: the server and one client. We proceed to describe the payoffs for each player. We denote by S 1 n s the throughput that the client can obtain by playing n s.
In that case, the n 1 normal stations will obtain each a throughput S n 1 n s = S 1 n s = S n s, that is, all stations obtain the same amount of throughput (cases (a,e) in ). If the client plays s, it obtains a throughput S c 1 if the server plays n d. This causes the normal stations to have a lower throughput, S n 1 s 0) as the cost of detecting malicious behavior for the server.
We model the cost function for client and server as a linear function of the throughput, with k s and k j as a constant for the server and the client respectively. Finally, we will assume that both players are maximizers, hence, they try to maximize the payoff function, that we define as follows:. It must happen that k s n 1 ( S n s − S n 1 s ) k d (observe that the previous point showed that the left hand side is positive).
This simply means that the cost of detecting is lower than the gain of detecting a deviation from the client. If that did not happen, it would be counterintuitive: the server incurs in a loss when it successfully detects a deviation from the client. Observe that our model includes the case in which there is no selfishness in the client as a particular case. If the server knows that the client will always play n s (i.e., like a normal station), then the server will always play n d and hence, both players receive a payoff of 0. Nash Equilibrium Concept The CSMA/CA game posed when N p = 2 is a non-zero sum, two player game. A very popular equilibrium concept for these games is the Nash equilibrium (NE) concept: it defines a situation in which no player can obtain a better payoff by deviating unilaterally.
Non-zero sum games might have more than one NE (Chapter 3and finding all of them might be hard (see ,). However, it is well known that every non-zero sum game has, at least, one NE in mixed strategies (Theorem 3.2, ). In a mixed equilibrium, each player has access to a randomizing device which outputs which pure action the player should play, with a given probability. This probability is the mixed NE. If there are two players, each of them with two actions to choose, we can define the payoff matrices as. (23) We simplify using.
We use the following shorthand notation: ϕ 11 = ϕ( n d ∩ s), ϕ 12 = ϕ( n d ∩ n s), ϕ 21 = ϕ( d ∩ s) and ϕ 22 = ϕ( d ∩ n s). Observe that this is the joint distribution probability, considering that the first subscript refers to the pure action of the server, and the second, to the pure action of the client. We also consider that pure action 1 for the server is n d, and pure action 2, d; for the client, s will be its pure action 1 and n s its pure action 2. Using all thisbecomes. Learning Algorithms: Regret Matching There are algorithms for learning static equilibria. One of the simplest and best known is Regret Matching (RM) algorithm, proposed by Hart and Mas-Colell ,.
It is a simple, adaptive strategy that guarantees that the joint distribution of play converges to the set of correlated equilibria of the underlying game if each player plays a regret matching strategy. The main idea of RM is to play a static game repeatedly and update a regret measure for each player depending on the outcome the players obtain each time they play the game. This algorithm requires that each player knows only her payoff and the actions of the other players (i.e., a player does not need to know the payoff functions of the other players). Each time the game is played, the regret W i ( a i ′ ) is obtained as. (28) where a i is the pure action played by player i, a − i denotes the pure actions played by all the other players, a i ′ is used to denote all pure actions available to player i and A i is the set of pure actions for player i.
If W i ( a i ′ ) 0, RM will assign positive probability to play a i ′ in the future, because the player would have gained in the past if she had played a i ′. On the other hand, if W i ( a i ′ ) ≤ 0, the player will assign probability 0 to play a i ′. At the beginning of the game, all regrets are initialized to 0, and they are updated with each repetition of the static game following. Histogram of actions obtained using RM algorithm, for n = 5 stations and variable number of malicious stations. Each histogram is computed using 5 bins. Cl stands for client.
Observe that the action of the server does not vary significantly, whereas the actions of the clients do. Also, observe how as n 2 increses, the clients histogram presents two peaks: the biggest close to 0 and a smaller peak at another mixed action value. This hints that the game tends to the two player case when there are many clients: all but one client tend to behave as normal stations. It is of special interest noting that, for n 2 ≥ 2, each of the clients distribution presents two peaks, clearer as n 2 grows; one of them is nearly 0. We observe that in each game realization all clients but one tend to behave as normal stations (i.e., they tend to play n s), as can be observed also in for n 2 = 4: client 1 plays a mixed action around z = 0.5 and the rest of clients tend to play z = 0, that is, they tend to always play n s. This means that the game tends to the two player case, even if there are more than two players. This might be due to having payoffs such that they do not encourage having more than one player behaving selfishly at once.
As we saw in, as the number of clients increased, the advantages of playing s for the clients decreased: the difference between the normal behavior throughput and the throughput obtained when using a different backoff shrank. Since the payoff of the clients is proportional to this difference, it is not enough gain for them to play n s: the loss when they play s and the server plays d do not compensate the gains when they play s and the server plays n d; hence, it is better for them playing n s. Conclusions In this paper, we study a CSMA/CA wireless sensor network under a backoff attack: some of the sensors of the network are malicious and deviate from the defined contention mechanism. We first use Bianchi’s network model to theoretically study the network throughput and observe that the malicious sensors have a gain on throughputs, at the expense of other sensors in the network. Even though the total throughput in some situations stays the same, it is not fairly distributed among sensors. This effect depends on the backoff parameters used by the malicious sensors, as well as on the number of malicious sensors present in the network. We then proceed to model the situation as a static game between the malicious sensors and a network gateway (thus, using a star topology): the gateway (server) tries to enforce the malicious sensors to behave following the contention mechanism, whereas the malicious sensors try to obtain a higher throughput.
We solve analytically the game for the case that there is only one malicious sensor and propose an algorithm based on Regret-Matching to learn the equilibrium with any number of players. Our approach is validated via simulations.
The framework we introduce in this paper can be further deepened in different ways. The malicious sensors could vary their parameters (for instance, their contention window) in order not to be easily detected by the defense system: this would mean that the action set of the client grows up and also, the game complexity. Another line of research would be modeling the game using dynamic game tools: in this case, the stations would choose their actions in order to maximize not their immediate rewards, but taking into account future interactions: in a wireless network, it is rare that the stations communicate only once. Finally, our approach shows that there is a trade-off between modeling complexity and computational complexity.
By making use of payoff matrices, we alleviate this trade-off: the game theoretic solutions we provide are agnostic with regards to where these payoffs come from. That is, we could use Bianchi’s model as we do to relate rewards with the throughput, or we could relate rewards to other network parameters (as delay or any other measure of the quality of service) and yet our game modeling would be valid: we should only replace the payoff matrix and solve the game, with these new matrices.
Hence, we believe that we introduce a framework simple enough to accommodate different situations, but also complex enough as to model the conflict and the actions of the different stations involved by using game theory tools. The following abbreviations are used in this manuscript: ACK Acknowledgement frame BA Basic Access mechanism CE Correlated Equilibrium CS Carrier Sense mechanism CSMA/CA Carrier-Sense Medium Access with Collision Avoidance CW Contention Window size DCF Distributed Coordination Function MAC Medium Access Control MS Malicious (greedy) Station NE Nash Equilibrium NS Normal Station RM Regret-Matching algorithm RTS/CTS Request-to-Send/Clear-to-Send mechanism STA Station WLAN Wireless Local Area Network.