Advanced
Lightweight Acknowledgement-Based Method to Detect Misbehavior in MANETs
Lightweight Acknowledgement-Based Method to Detect Misbehavior in MANETs
KSII Transactions on Internet and Information Systems (TIIS). 2015. Dec, 9(12): 5150-5169
Copyright © 2015, Korean Society For Internet Information
  • Received : July 13, 2015
  • Accepted : October 03, 2015
  • Published : December 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
About the Authors
Vahid Heydari
Seong-Moo Yoo

Abstract
Mobile Ad hoc NETworks (MANETs) are the best choice when mobility, scalability, and decentralized network infrastructure are needed. Because of critical mission applications of MANETs, network security is the vital requirement. Most routing protocols in MANETs assume that every node in the network is trustworthy. However, due to the open medium, the wide distribution, and the lack of nodes’ physical protection, attackers can easily compromise MANETs by inserting misbehaving nodes into the network that make blackhole attacks. Previous research to detect the misbehaving nodes in MANETs used the overhearing methods, or additional ACKnowledgement (ACK) packets to confirm the reception of data packets. In this paper a special lightweight acknowledgement-based method is developed that, contrary to existing methods, it uses ACK packets of MAC layer instead of adding new ACK packets to the network layer for confirmations. In fact, this novel method, named PIGACK, uses ACK packets of MAC 802.11 to piggyback confirmations from a receiver to a sender in the same transmission duration that the sender sends a data packet to the receiver. Analytical and simulation results show that the proposed method considerably decreases the network overhead and increases the packet delivery ratio compared to the well-known method (2ACK).
Keywords
1. Introduction
W hen mobility and scalability are of vital importance, wireless networks are always preferred. In critical mission applications like military conflict or emergency recovery, Mobile Ad hoc NETworks (MANETs) are the best choice because of having a decentralized network infrastructure. MANETs rely on the benevolence of nodes within the network to forward packets from a source node to a destination node (multi-hop forwarding). Because of critical mission applications of MANETs, network security is one of the most important requirements. Unfortunately, due to the open medium and the lack of nodes’ physical protection, attackers can easily capture and compromise nodes to achieve their goals. In particular, most routing protocols in MANETs assume that every node in the network is trustworthy and presumably not malicious. So, attackers can easily compromise MANETs by inserting misbehaving nodes into the network. A misbehaving node is a node that cooperates in route finding phase and forwards all control packets (such as route request, route error, and route reply) correctly, but silently drops all data packets. Many research efforts have been devoted to detect the misbehaving nodes in MANETs that can be classified into two categories: monitoring-based methods and acknowledgment-based methods. The main problem with monitoring-based methods is that the overhearing method is unable to determine accurately the misbehaving nodes because of transmission instability in wireless networking environments that have been explained in [3] . The acknowledgment-based method solves the problems of monitoring-based methods by using additional ACK packets to confirm the reception of data packets. However, this performance improvement has an additional cost which is the overhead made by these ACK packets.
When a method adds one extra packet to the network layer, the method is actually adding at least four extra packets (RTS, CTS, Data, ACK), according to IEEE 802.11 protocol, to the MAC layer. Note that in MAC layer, IEEE 802.11 protocol uses mandatory ACK packets to confirm the reception of transmitted data packets. Therefore, in this paper a special lightweight acknowledgement-based method, named PIGACK, is developed that on the contrary to existing methods, it uses ACK packets of MAC layer instead of adding new ACK packets to the network layer for confirmations. In fact, this novel method uses ACK packets of MAC 802.11 to piggyback confirmations from a receiver to a sender in the same transmission duration that the sender sends a data packet to the receiver. In this method, a message authentication code is used to authenticate the sender of the packet. Analytical and simulation results show that the proposed method considerably decreases the network overhead and increases the packet delivery ratio compared to the well-known method (2ACK [10] ).
Our Contributions –We develop the PIGACK method for detecting and isolating misbehaving nodes. Compared to state-of-the-art, PIGACK provides the following additional features:
  • Misbehaving node detection instead of misbehaving link detection: PIGACK can detect misbehaving nodes and prevent using any links that include them (increase in packet delivery ratio).
  • Informing other source nodes by informing the neighbors (at least half of them) of the newly misbehaving node detected to prevent using this misbehaving node by other source nodes (increase in packet delivery ratio).
  • Decrease in routing overhead: PIGACK uses ACK packets of MAC 802.11 to piggyback confirmations from a receiver to a sender in the same transmission duration that the sender sends a data packet to the receiver. Therefore, PIGACK does not use any extra ACK packets.
Paper Organization – The rest of this paper is organized as follows. Related work is covered in Section 2. Proposed PIGACK method is introduced in Section 3 including attack types. Section 4 and 5 cover analytical model and simulation. Finally, conclusion is explained in Section 6.
2. Related Work
In this section, previous methods, to detect and mitigate malicious nodes in MANETs, are explained. As above-mentioned, these methods can be classified into two main categories; monitoring-based methods and acknowledgment-based methods. We introduce some important methods of each category and explain their advantages and disadvantages.
- 2.1 Monitoring-Based Methods
The main idea of monitoring-based methods is to exploit wireless medium nature that each transmission can be heard by one-hop neighbors. In these methods a sender places itself in a promiscuous mode after transmitting a packet to overhear the retransmission by the forwarding node. Using this method, a node can know whether the packet, which has been sent to its neighbor, is indeed forwarded or not. Marti et al. [11] proposed two extensions to the DSR protocol, Watchdog and Pathrater. The Watchdog is based on promiscuous mode operation of the nodes to detect misbehaving nodes. Pathrater uses the knowledge from Watchdog to choose a path without any misbehaving nodes. Buchegger and Boudec [4] proposed CONFIDANT, an extension to the DSR which adds the reputation system and the trust manager to the Watchdog and Pathrater mechanisms. When misbehaving nodes are detected via Watchdog, an alarm is sent to the other nodes, defined as friends, to isolate the misbehaving nodes from the network. Winjum et al. [15] described a mechanism that uses a trust metric for routing. This method is based on detection of routing information sent by trusted nodes or sent by other nodes in the network. Each node should store two routing tables, one for trusted routes and another for unreliable routes. Pirzada et al. [12] used trust and reputation in the DSR protocol. The trust value calculated in the promiscuous mode is used to select a trusted route without misbehaving nodes. But in this method a wrong recommendation may occur and be used by other nodes. Chang et al. [5] used distributed authentication authorities which employ distributed trusted groups for the authentication process. However, this method works in the dynamic MANET with high delay. Chen et al. [6] employed a distributed trusted routing framework that authenticates messages, nodes and routes. But this method needs the certificate authority. Xia et al. [16] presented a dynamic trust prediction model to evaluate the trustworthiness of nodes, which is based on the nodes’ historical behaviors, as well as the future behaviors via the prediction of extended fuzzy logic rules prediction.
The base of all above-mentioned methods is the trust degree of each node resulted from the promiscuous mode operation of the nodes. In other words, each node promiscuously listens to its wireless medium, catches all packets in its antenna range and sends these packets to the network layer, which saves all of them in the table and uses a watchdog timer to detect the misbehavior of the one-hop neighbors. However, the overhearing technique is not likely to be accurate for MANETs due to varying noise levels, varying signal propagation characteristics in different directions, and interference from competing transmissions [3] .
- 2.2 Acknowledgment-Based Methods
These methods are based on acknowledgments for packets delivery confirmation. Balakrishnan et al. [2] proposed a network-layer acknowledgment-based scheme, called TWOACK, to detect misbehaving nodes. The TWOACK is based on the Watchdog method; however, it does not use the overhearing technique (the promiscuous mode). It sends two-hop acknowledgment in the reverse direction to confirm that the intermediate nodes cooperated in the packet forwarding. The TWOACK resolved some problems of the promiscuous mode such as ambiguous collisions, receiver collisions and the limited transmission power. Liu et al. [10] proposed 2ACK scheme that uses acknowledgments like the original TWOACK scheme. Two major differences between them are as follows:
  • 1) The 2ACK scheme uses an authentication mechanism to avoid tampering of the 2ACK packets, whereas the TWOACK scheme does not use authentication.
  • 2) The intermediate nodes in the 2ACK scheme may only send a fraction of 2ACK packets with the tradeoff of increased delay in misbehavior detection (more packet dropping). Therefore, the 2ACK scheme may have less overhead than the TWOACK method because in the TWOACK scheme the intermediate nodes send the whole TWOACK packets for every data packet. Note that we will use 2ACK packets for all received data packets to achieve the best performance of 2ACK (minimum delay in misbehavior detection) in our analysis and simulation.
  • The shortcomings with the mentioned acknowledgement-based methods are as follows:
  • 1) Message overhead: both methods have overhead messages (2ACK and TWOACK packets).
  • 2) The 2ACK scheme cannot detect “false alarms”. The 2ACK waits a certain time to receive ACK packet; however, sometimes, because of congestion or link fail detection time, a link (a pair of nodes) may be reported as a misbehaving link. In this situation the 2ACK does not have any method to exonerate this link. In the worst case, “intentional false alarms” (slander attacks) may occur. Assume that we have n1, n2, n3, n4, n5, n6, n7 on the path. If n3 receives the ACK packet of n5, but sends a false alarm to n1, the link n4-n5 will be saved as a misbehaving link. However, neither n4 nor n5 is a misbehaving node. By this attack n3 can accuse all links between its neighbors and their neighbors.
Some other methods, mentioned below, claimed that not only can detect blackhole attacks but also are able to detect collusion blackhole attacks due to collusive misbehaving nodes which cooperate in the route discovery, but refuse to forward data packets and do not disclose the misbehavior of each other. Note that we assume no collusion among misbehaving nodes in our method.
Awerbuch et al. [1] proposed an on-demand secure routing protocol (ODSBR) to identify misbehaving links and collusion blackhole attacks. In ODSBR, audited nodes acknowledged audited packets back to the source. Then the source performs a binary search to identify the misbehaving link. The main problem of the ODSBR is explained in this example: Suppose in ODSBR a misbehaving node drops all data packets except the packets that contain probes for one of the next nodes, only the data packets contain probes will reach the destination node. Therefore, the packet delivery ratio cannot exceed 50%.
Sun et al. [14] proposed a scheme, called NACK, which adopts an acknowledgment-based approach and compares timestamps to resist collusion attacks. The NACK scheme, similar to the TWOACK and the 2ACK schemes, sends two-hop acknowledgments in the reverse direction (NACK packets) to confirm that the intermediate nodes cooperated in the packet forwarding. For this goal, the NACK scheme uses a timestamp comparison and an additional route between source nodes and destination nodes to detect malicious nodes. The NACK method uses time synchronization techniques and assumed that the second route does not have any misbehaving node.
Shakshuki et al. [13] proposed a hybrid scheme, called EAACK, to detect collusion blackhole attacks which includes three phase. First of all, the destination must send an end-to-end acknowledgement packet (ACK) to the source node. If the source node does not receive the ACK packet, it starts the second phase, where EAACK uses the TWOACK to detect two neighbor nodes as misbehaving nodes. However, the source node does not immediately trust the misbehavior report. When the second phase is finished, the source node starts the third phase. On this phase, the source node uses a second route and asks the destination whether it received the removed packet or not. This phase helps the source node to detect false misbehaving reports. The EAACK, like the NACK, assumed that the second route is available and does not have any malicious nodes. The main problem of the EAACK is similar to the ODSBR that a malicious node can do partial dropping without being recognized.
Two main common problems of above-mentioned acknowledgment-based methods are:
  • 1) Misbehaving link detection instead of misbehaving node detection: These methods cannot detect a misbehaving node. They can only determine two neighbor nodes and cannot detect which of them is misbehaving. By the error reports from one of the intermediate nodes, the source node detects the link between two nodes as a misbehaving link, but a link cannot be misbehaving, in fact, anyone of the two end nodes of a link may be misbehaving. The source node will not use this link in the future, but due to lack of accurate detection of the misbehaving node, the node may be used in another path by the source node. Therefore, a misbehaving node can be used for more than one time without being recognized. In fact, a misbehaving node can be placed on different paths equal to the number of its neighbors.
  • 2) When a misbehaving link is detected, an alarm will be sent to the source node. All intermediate nodes between the reporter and the source node as well as the source node will be informed of this link. However, a new source node which was not informed must detect this misbehaving link by itself, which consumes time and decreases the packet delivery rate. In fact, the 2ACK does not have any method to inform other source nodes of misbehaving links detected.
In this paper we try to solve the above-mentioned problems. Therefore, our goals are: decreasing the network overhead, detecting false alarms, detecting misbehaving nodes instead of misbehaving links, and informing other source nodes by informing the neighbors (at least half of them) of misbehaving node detected.
3. Proposed PIGACK Method
- 3.1 Assumptions
• DSR is the protocol used for network layer.
• There is no collusion among misbehaving nodes.
• Each node has a unique ID and cannot be spoofed.
• A misbehaving node is a node that cooperates in route finding phase and forwards all control packets (such as route request, route error, and route reply) correctly, but silently drops all data packets. Each node in a path may be malicious except source and destination nodes which are assumed to be trusted.
• A suspicious node is a node that was reported as a misbehaving node by another node. However, it already sent the PIGACK packet of its next node to the neighbors (and source in new route) to exonerate itself. If a node is detected two times as a suspicious node (reported by different nodes), it will be marked as a misbehaving node.
• By default, each node has a table and for every node in the network it has an entry with four fields: its ID, its public key (or symmetric key), malicious flag, and reporter. The malicious flag is zero by default and if it is detected that the node is misbehaving, this flag will be two. This flag will be one if the node is detected as a suspicious node. The reporter field is the node ID of the node that reports this misbehavior.
• Each node has a data structure. Each entry include: PreNodeID, NextHopNodeID, SecondHopNodeID, Cpkts, Cmis , and a list that contained PID, Send, State, Timeout, Confirmation . For node B , as an example, on the route { S, A, B, C, D }, PreNodeID is A ’s ID, NextHopNodeID is C ’s ID and SecondHopNodeID is D ’s ID. PreNodeID for S is zero (because S is the source). NextHopNodeID for D and SecondHopNodeID for C are zero (because D is the destination). Cpkts is a counter of forwarded data packets and Cmis is a counter of missed data packets. PID is the packet ID of received data packet. Received confirmation of next node in a PIGACK packet is saved on Confirmation field and Send field will be set when saved confirmation is forwarded to the previous node. State is zero when sending a new packet and Timeout (timeout period) is set. When next hop node’s confirmation is received, State will be set to one and after receiving confirmation of the second-hop node, it will be set to two and Timeout will be reset.
• Each PIGACK packet contains confirmations that the number of them is determined by Cconfirm (1 ≤ Cconfirm ≤ maximum number of packets waited for confirmation). Each confirmation includes three fields: NodeID, PID , and MAC. MAC is the message authentication code created by the node that its ID is NodeID and PID demonstrates the ID of the received data packet by this node.
We add one field to the route error packet of DSR named Malicious . If this field is set, the next node of this error producer is a misbehaving node. Malicious is zero for a normal route error packet.
- 3.2 Proposed Method
According to IEEE 802.11, an ACK packet must be sent by the receiver to confirm the reception of the packet. Our goal is piggybacking some information to these ACK packets of MAC layer instead of using ACK packets of network layer. Hereinafter, we use “PIGACK” as the ACK packet of MAC layer which contains confirmations. Each node when sends a data packet and receives PIGACK packet must save the next node’s confirmation (included in the received PIGACK) and send back with its confirmation for the next packet sent from the previous node inside a new PIGACK packet. In fact, each node when receives a data packet must send back a PIGACK packet that includes:
  • 1) The confirmation of reception of this packet created by this node, and
  • 2) The confirmation of the previous packet created by the next node to prove its honesty.
This idea works well in a network without any congestion so only one packet may be waited for confirmation in each node. Therefore, sometimes a node may not have any ready confirmation of its next node to send back to the previous node or may have more than one confirmation ready to send back. Therefore, we add Cconfirm to PIGACK packet to specify the number of confirmation included in this packet. PIGACK method can be summarized in the pseudocode as follows:
PPT Slide
Lager Image
Nodes have a table for each Path (specified by the previous node, the next hop node, and the second hop node). When a node receives a packet, the node adds its ID as a new entry to this table and calculates a timeout period for it. This timeout period is equal to the maximum waiting time to prepare the confirmation of the second hop node in the next hop node for this packet ID (so at the next sending packet, this confirmation will be received). Therefore, this timeout is equal to the maximum delay per two hops. If we use the 95-percentile of response time of each node as the delay per hop, we must specify a node as a misbehaving node if the ratio of C mis /C pkts is more than five percent ( Threshold ). If the timeout is reached and this node did not receive specific confirmation (the second hop confirmation) after sending a new packet to the next node, this node removes the table entry for that packet ID and increases Cmis . If the ratio of Cpkts to Cmis is more than specific Threshold , the next node ID will be stored as a misbehaving node and an error signal will be sent up from MAC layer to network layer that mentions this misbehavior and DSR will set Malicious field of the route error packet to inform other nodes of this misbehaving node. This route error packet will be sent to the source node IP address as the destination IP address (similar to normal DSR). However, the MAC layer will send it as a broadcast message. By this way, neighbors of this node will see this misbehaving node report, but only one of them (according to the header of DSR) will forward this packet to the source node. These neighbors and the source node will remove all routes in their caches that include the misbehaving node and set the malicious flag of this node to two and store the ID of its reporter in the table. Malicious flag in the table will be set to one if the misbehaving node proves its honesty so it will be change from a misbehaving node to a suspicious node.
Using this technique that neighbors are informed of this misbehavior can increase the packet delivery ratio because they abstain to forward any packet from other sources to this misbehaving node.
We put some change to DSR to behave correctly with its route request and route reply packet. When a node receives a route request or reply packet, it must check the route in the packet header (list of intermediate nodes saved on the header) and drop this packet if the route contains any pre-reported misbehaving node (or two neighbor suspicious nodes).
We change the ACK packet format of MAC layer to include confirmations to it. As mentioned in assumptions (Section 3.1), the new packet (PIGACK packet) format includes: (see Fig. 1 )
  • Standard ACK fields
  • Cconfirm(the number of confirmations included in this PIGACK)
  • One or more confirmations (NodeID,PID, andMAC)
PPT Slide
Lager Image
PIGACK packet format (number of confirmation is equal to Cconfirm).
- 3.3 Message Authentication Code
We have two choices for message authentication code:
  • 1) Digital signature (default method for PIGACK): In this method we use elliptic curve online/offline digital signature[18]that needs 160 bits key size for security level 80 and creates signatures with the size of 320 bits.We assume offline key distribution method and sequential packet ID started from a number mentioned in the first data packet (this packet does not need confirmations). Therefore, nodes will have enough time to prepare the next signature before receiving the next data packet.
  • 2) UMAC: This is the fastest reported message authentication code in the cryptographic literature used symmetric technique and a fast universal hash function[9]. The key size is 128 bits (security level 80) and its output is 64 bits. We assume offline distribution shared keys so each node has shared keys of other nodes. The advantages of this method are: (1) smaller key size and output size and (2) fast enough to prepare the code during a short interframe space (SIFS) time interval (the time between receiving a packet and sending an ACK according to IEEE 802.11), so we do not need the sequential packet ID. On the other hand, its disadvantage is: having problem (similar to 2ACK) to detect attack type 2 and 3 explained in Section 3.4. Hereinafter, we use PIGACK_U to refer to PIGACK that uses UMAC for message authentication codes.
- 3.4 Attack Types
In this section we explain different types of attacks related to our method. Assume a route from S to D includes A, B , and C ({ S, A, B, C, D }). In these attack types, a node may only drop data packets (blackhole attack), create false alarms by sending wrong 2ACK (or PIGACK) to slander other nodes (slander attack), or participate with other misbehaving nodes (collusion attack). Note that we assume no collusion attacks in the network so we will not discuss collusion blackhole, slander, or framing attack. The attack types that we consider are as follows:
Type 1. C does not send the 2ACK (or PIGACK) packet to B .
2ACK: A does not receive 2ACK of C so it detects link B-C as a misbehaving link and reports this link to the source. Other links that include C may be used by this source and all the links may be used by other sources.
PIGACK: A PIGACK packet contains the standard ACK packet and missing a PIGACK means missing the ACK, so B will send a route error packet according to IEEE 802.11 and DSR. On the other hand, if C sends a PIGACK without received D’ s confirmation, B will detect C as a misbehaving node after the timeout period.
Type 2. C sends its 2ACK (or PIGACK) packet to B with a wrong message authentication code (or wrong MAC of its confirmation inside PIGACK).
2ACK: B cannot detect any problem because the packet is signed for A and according to the message authentication code used by 2ACK, only C and A can read this packet. Therefore, A will detect link B-C as a misbehaving link.
PIGACK: B reads the digital signature of C and detects this fault and behaves similar to the situation that B did not receive the PIGACK of C (creates the route error packet).
Type 3. A creates a false alarm and mentions B as a misbehaving node.
2ACK: This problem cannot be solved in 2ACK because the misbehavior of A will not be detected by the source so the source will mention link B-C as a misbehaving link.
PIGACK: B is one of the neighbors of A so B will see this false alarm and will send the PIGACK packet containing the confirmation of C as a broadcast message with Time To Live (TTL) equal to two to inform the neighbors of A and will send it in a new route to the source. In this situation, the neighbors and the source will mention both A and B as misbehaving nodes. Although B is detected wrongly as a misbehaving node, A isolates itself by doing this attack. Therefore, creating a false alarm is so costly for a misbehaving node.
4. Analytical Model for Overhead Ratio
In this section we use an analytical model using queuing theory to obtain the network overhead ratio. For calculating the overhead in this paper, we focus on the overhead of both MAC and network layers instead of considering only the overhead of network layer because of two reasons:
  • 1) Some information is piggybacking to the ACK packet of MAC layer and 2ACK method adds new packets to the network layer, so we have to obtain the overhead from both layers.
  • 2) By focusing on the overhead of both MAC and network layers we can calculate the real overhead that includes all DSR and MAC headers, routing packets of DSR, and control packets of MAC layer. For example, when we add 2ACK packets to the network layer, we will have some additional overhead because of MAC control packets such as Request to Send (RTS), Clear to Send (CTS) and ACK packets. The number of RTS packets is not equal to the number of transmissions because of collisions. Therefore, adding a new packet or changing a packet size will change the network load and will have effect on the number of collisions and RTS packets so our real network overhead must be obtained by considering both layers instead of only the network layer.
First of all, we will briefly introduce IEEE 802.11 MAC protocol and explain the assumptions and queuing network model. Then, we explain our overhead analysis.
- 4.1 MAC Protocol I
IEEE 802.11 protocol defines a distributed coordination function (DCF), for sharing access to the medium, based on the CSMA/CA protocol. A node listens to the channel before the transmission to determine whether it is free or not. If the medium is sensed to be free for a DCF interframe space (DIFS) time interval, the transmission will proceed by sending a RTS packet to announce the upcoming transmission. When the destination node receives the RTS, it will send a CTS packet after a SIFS time interval. The source node is allowed to transmit the data packet only if it receives the CTS packet correctly. The destination node must send an ACK packet after a SIFS time on receiving the data packet.
If the medium is busy or the node does not receive the CTS packet, the node must defer its transmission until the end of the current transmission and then must wait an additional DIFS interval and generate a random backoff time. This process minimizes collisions during contention between multiple nodes.
Definition 1: Backoff time: backoff time = Random() × SlotTime where Random() is a pseudorandom integer among [0, CW-1] where CW min ≤ CW ≤ CW max and the SlotTime is one of the physical layer characteristics.
The contention window (CW) parameter must take the CW min as the initial value. Every node must maintain a Station Short Retry Count (SSRC) which must take an initial value of zero and its range is [0, 7]. After each unsuccessful transmission retry, the SSRC will be incremented and the CW will take the next value that is the result of multiplying the previous value by two. If the CW reaches the CW max , it will not continue to increase. If the SSRC reaches the last number in its range, the packet will be dropped. After each successful transmission, the CW and SSRC will be reset to the initial value.
Definition 2: The mean backoff time for the first try: E[T B ] = (CW min × SlotTime) / 2.
Because we want to consider the medium as a server and nodes as its customer (will be explained in Section 4.3), our server always will have at least one customer that is in the first round (CW min ) of backoff time. Therefore, we use CW min in Definition 2.
- 4.2 Assumptions
  • The total number of nodes in the network and the size of network must satisfy the network connectivity according to the node density of the network.
  • The network consists of N nodes that are distributed uniformly and independently over the area ofX×Y.
  • We assumed, for simplicity, an equal transmission range denoted byr(n) and equal carrier sensing range denoted byc(n) for each node.
  • Letrijdenote the distance between nodeiandj. They can communicate with each other as the neighbor nodes ifrij≤r(n).
  • A free-space model in uncontested environments is used.
  • DSR control packets are not included in our model. For this reason, we assume stationary nodes (avoiding broken routes and route error packets) and do not use the first 50 sec of simulation results (avoiding route setup duration with route request and reply packets).
  • According to IEEE 802.11, we have seven retry limits for a packet transmission. We assume no packet dropping in our model. Therefore, at most after six transmission collisions, a packet will be transmitted.
  • Each interfering neighbor node of a source or destination freezes its backoff counter as soon as detecting RTS or CTS packets. We do not consider noises. Because of these two assumptions, after receiving CTS by the source node, transmission will be done without any collision or problem. Therefore, the number of CTS and ACK packets are equal to the number of transmitted data packet per hop. Collisions may effect only on the number of RTS packets.
- 4.3 Queuing Network Model
An M/M/1 queue is used in our model. It is assumed that the arrivals occur at rate λ according to a Poisson process and the service times have an exponential distribution with parameter μ . There are no buffer or population size limitations and the service discipline is First Come, First Served (FCFS). To analyze the M/M/1 queue, we need to know only the mean arrival rate λ and the mean service rate μ in jobs per unit time. The mean service rate can be obtained by μ = 1/E[ S ] ( S is the service time of the server).
Definition 3: Utilization factor of the server: ρ = λ / μ [8]
Definition 4: Probability of zero job in the system: P0 = 1 - ρ [8]
Each node and its neighbors within the interference range must compete for access to the medium. When a node gets the right to use the medium, its neighbors that have a packet to send, must freeze their backoff counter and wait for medium to be free. We need to obtain this freezing time to calculate the service time of each node. For this reason, we consider the medium as the server and the interfering range’s nodes as the customers in the queue. In the service discipline of the server (the medium) each node with the backoff counter equal to zero will have access to the server.
In the traffic model, each node could be a source, a destination or a relay node. The packet generation process at each node is an independently and identically distributed Poisson process and the number of connections (packet flows) is constant and equal to nn . The arrival rate in jobs per unit time for each connection is λj (1 ≤ j nn ). The mean data packet length ( Ldata ) is the sum of data packet size of DSR, DSR header, the mean number of hops multiplied by four bytes (DSR packets include the route in their headers), and MAC header. The size of each 2ACK packet is equal to L2ACK bits and the headers of network and MAC layers are included in L2ACK , RTS, CTS, and ACK. The channel bit rate is constant and equal to W . The parameters of the queuing network model summarized in Table 1 .
Network model parameters
PPT Slide
Lager Image
Network model parameters
Before calculating the new parameters of the model, we need to obtain some basic parameters. To obtain the mean number of hops ( E [HOP]), the method of [7] is used in this paper. Other basic parameters are explained in definitions below.
Definition 5: The mean number of neighbors ( E [ ζr ]) in range r:
PPT Slide
Lager Image
[7] .
Definition 6: The mean random distance per hop:
PPT Slide
Lager Image
[7]
- 4.4 Mean Number of Hidden Neighbors
In wireless networks, each node has three different ranges:
  • The transmission range (r(n)) is mainly determined by transmission power and radio propagation properties.
  • The carrier sensing range (c(n)) is usually determined by the antenna sensitivity.
  • The interfering range (i(n)) is the range within which a node in receiving mode can be interfered by another transmission, leading to a collision at receiver.
The first two above-mentioned ranges are constant. However, the third one depends on the distance between the sender and the receiver. Note that the transmission power level assumed to be constant. Nodes within the interference range of a receiver are called hidden neighbors. Here, a receiver sends a CTS packet to the sender (as the response to the received RTS packet), if no any of its hidden neighbors are transmitting a packet.
We need to obtain the mean number of hidden neighbors to calculate the collision probability. For this purpose, we must obtain the interfering range and use this range for calculating the area of hidden neighbors.
Lemma 1: Hi is the number of hidden neighbors of node i . Then
PPT Slide
Lager Image
Proof: Using this usual assumption that the threshold of signal to noise ratio (SNR_THRESHOLD) equals to 10 and the mean distance between senders and receivers equals to E [ ri ] (Definition 6), The interfering range will be equal to 1.78× E [ ri ] [17] . Therefore, using Definition 5, the mean number of nodes in this range equals to E [ ξ 1.78×E[ri] ]. Note that one of these nodes is the sender and other nodes are hidden neighbors.
- 4.5 Overhead Analysis
Lemma 2: R2ACK is the ratio of the number of 2ACK packets to the number of total data and 2ACK packets. Then
PPT Slide
Lager Image
Proof: Each data packet traverses E[HOP] to reach a destination and according to 2ACK method, each node on the route, except the first two nodes, must send back a 2ACK packet and each 2ACK packet traverses two hops. The number of nodes on the route is equal to the number of hops plus one. Therefore, (2) is proved. If we use DSR or PIGACK, we will not have 2ACK packets.
Lemma 3: LACK is the length (bytes) of ACK packet in MAC layer. Then
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Proof: DSR and 2ACK use standard ACK packets, but PIGACK has standard ACK fields plus some new fields. We assume no packet dropping in the network, so each node (except destinations) must forward the received packet and send back PIGACK packet. Therefore, the number of confirmations in each PIGACK is equal to two (one for received packet and the other for previously transmitted packet). However, destinations only must send back one PIGACK. Therefore, the mean number of confirmations is equal to
PPT Slide
Lager Image
and for each confirmation we have NodeID (four bytes), PID (four bytes), and MAC (40 bytes for PIGACK and eight bytes for PIGACK_U). Besides, we have a new field CConfirm in each PIGACK packet that needs one byte.
Lemma 4: λi is arrival rate in jobs per unit time for each node. Then
PPT Slide
Lager Image
Proof: The number of sending (transmitting by the source node) and forwarding (transmitting by the intermediate nodes) per each packet of each connection is equal to the mean number of hops. Therefore, the total arrival rate of the network is
PPT Slide
Lager Image
However, according to 2ACK method and proof of Lemma 3, we must add
PPT Slide
Lager Image
for 2ACK method. Therefore, the total arrival rate for 2ACK is equal to
PPT Slide
Lager Image
and the mean of arrival rate for each node is (4).
Lemma 5: TD is the time duration to send a full data packet. Then
PPT Slide
Lager Image
Proof: According to IEEE 802.11 and the fact that the packet is a 2ACK packet with the probability of R2ACK , and is a data packet with the probability of (1- R2ACK ) and by using Lemma 2 and 3, we will obtain (5).
Lemma 6: S is the service time of the server. Then
PPT Slide
Lager Image
Proof: According to the IEEE 802.11 protocol, the medium is given to a node for transferring a packet ( TD from Lemma 5) after a backoff time (E[ TB ] from definition 2). The next packet will be sent after DIFS from the last sending packet. Therefore, each packet needs E[ TB ] + TD + DIFS to be served. (See Fig. 2 )
PPT Slide
Lager Image
Backoff mechanism of 802.11 MAC.
Theorem 1: PC is the probability of collision between the source node’s packets and the hidden neighbors’ packets. Then
PPT Slide
Lager Image
Proof: we would like to know the probability of sending packet by hidden neighbors. P 0 is the probability of zero job in the system. According to Definition 4, 1- P 0 = ρ is the probability of at least one job in the system. The simultaneous transmission by a hidden node and the source node makes a collision at the destination node. Therefore, PC is equal to the probability of at least one hidden neighbor’s job in the system ( ρ ). Using this fact that
PPT Slide
Lager Image
Definition 3,Lemma 1, and Lemma 4 we have:
PPT Slide
Lager Image
using Lemma 6:
PPT Slide
Lager Image
Theorem 2: CRTS is the number of RTS packets per each data packet (or 2ACK packet) transmission over one hop. Then,
  • F(0) = 2,F(1) = 1 + (1-PC) +PC(F(0)), ...,F(n) = 1 + (1-PC) +PC(F(n-1)) (2≤n≤5), andE[CRTS]=(1−PC) +PC(F(5)).
Proof: according to IEEE 802.11 protocol, a packet will be dropped after seven unsuccessful retries. We assume no packet dropping in our model. Therefore, we must include six collision possibilities and in the last retry the packet must be transmitted. In each retry step, the packet is sent by the probability of (1- PC ) (one RTS is sent), obtained by Theorem 1, and a collision may occur by the probability of PC (previous RTS is wasted and new one must be sent). F (0) is the last retry that includes one wasting RTS because of the last collision and one new RTS that the packet will be sent after this RTS.
Lemma 7: OHOP is the overhead per hop for each data packet. Then
PPT Slide
Lager Image
where Hdata is the header size of data packets (all headers included in Hdata ).
Proof: For transmitting each data packet (or 2ACK packet), a node must send E [ CRTS RTS , receive a CTS, send the packet (if the packet is a data packet so the overhead is its header, but if it is a 2ACK packet, the whole packet is overhead), and receive an ACK packet (normal ACK packet size or our new ACK packet used in our new method). Equation (10) uses Theorem 2, Lemma 2, and Lemma 3.
Lemma 8: Cpkt is the number of data and 2ACK packets per hop. Then
PPT Slide
Lager Image
Proof: According to the proof of Lemma 2 and 4, (11) will be proved.
Corollary: ORatio is the overhead ratio. Then
PPT Slide
Lager Image
Proof: According to Lemma 7 and 8, the overhead per hop is equal to Cpkt × OHOP . The denominator of equation is equal to the sum of data packet (without headers) per hop.
In the next Section we will compare our analytical results with those obtained from simulations.
5. Simulations
In the simulations, a version of network simulator (NS-2) is used. DSR and MAC 802.11 modules are modified to simulate PIGACK and 2ACK methods. Note that DSR and 2ACK methods use standard MAC 802.11, but PIGACK uses a modified version of that. The traffic and scenario patterns are randomly made using "cbrgen" and "setdest" tools of NS-2. Note that "setdest" uses uniform distribution for node places and random waypoint model for the movement of nodes. We use five traffic and five scenario patterns (25 simulation runs) for each simulation result. The simulation parameters are summarized in Table 2 .
Simulation parameters
PPT Slide
Lager Image
Simulation parameters
First, the comparison between analytical and simulation results according to the assumption of analytical model are explained and then, the simulation results for a real network by considering the mobility, DSR routing packets, and assumptions in Section 3.1, are given.
- 5.1 Comparing Analytical Results with Simulation Results
Table 3 shows the comparison between analytical and simulation results for calculating overhead ratio. We used the assumptions introduced in Section 4.2 in the simulations. The values of parameters in Table 3 were used in analytical results for this comparison.
Comparing the overhead ratio obtained from analytical results with those obtained from simulations
PPT Slide
Lager Image
Comparing the overhead ratio obtained from analytical results with those obtained from simulations
- 5.2 Simulation Results
In this part we use the simulation parameters summarized in Table 2 with these differences:
  • Node mobility is considered with the maximum speed and pause time equal to 20 m/sec and 20 sec, respectively.
  • Misbehaving nodes are considered 0, 10, 20, 30, and 40 percent of the whole nodes.
  • The following metrics are used to evaluate the performance of the DSR, PIGACK, PIGACK_U, and 2ACK methods with regard to UDP traffic:
  • Packet delivery ratio: The ratio of the number of data packets received by destination nodes to the number of data packets sent by source nodes.
  • Overhead ratio: The ratio of the amount of routing packets (route request, route reply, route error, and 2ACK) and MAC control packets (RTS, CTS, ACK, and PIGACK) per hop (headers are included) to the amount of data packets per hop. Note that in the overhead ratio used in analytical model in Section 4, we assumed no routing packet and the network was stationary. However, in this section we assume that we have a MANET with DSR routing packets.
- 5.2.1 Packet Delivery Ratio
In Fig. 3 we compare the packet delivery ratio as a function of misbehaving node ratio. The misbehaving node ratio ranges from 0 (all nodes are trustworthy) to 40 (40% of nodes are misbehaving). Here, we observe that increasing the number of misbehaving nodes reduces the packet delivery ratio. As expected, PIGACK and PIGACK_U methods have shown a much better performance in packet delivery ratio compared to 2ACK and DSR methods.
PPT Slide
Lager Image
Packet delivery ratio as a function of misbehaving nodes ratio.
There are two reasons of low packet delivery ratio of 2ACK. (1) Lack of detecting misbehaving node (it detects misbehaving link) lets a misbehaving node exist still in different routes used by the source node. (2) Lack of informing other nodes to prevent the presence of detected misbehaving node on the routes. Because of this reason, each source node must detect each misbehaving link by itself.
- 5.2.2 Overhead Ratio
In Fig. 4 we compare the overhead ratio of the methods as a function of misbehaving node ratio. The higher overhead in the all methods except the DSR is due to the transmission of extra acknowledgment packets (2ACK) or extra information in ACK packets of MAC layer (PIGACK and PIGACK_U). When a misbehaving node is detected, the source node must use other routes for packet transmission and this process may need new routing packets to find new routes. Because of this reason, the overhead of 2ACK and our methods are increased with the misbehaving nodes ratio. However, DSR does not detect the misbehaving nodes so it does not need to find new routes. Besides, increasing the misbehaving nodes will decrease the probability of broken route because they truncate the route and packet route errors may be created only by nodes between sources and misbehaving nodes not between sources and destinations and this is the reason of decline in the overhead of DSR as shown in Fig. 4 .
PPT Slide
Lager Image
Overhead ratio as a function of misbehaving nodes ratio.
- 5.3 One More Comparison Using Real Circumstance Example
2ACK had the minimum overhead between acknowledgment-based methods and we found that PIGACK has less overhead in comparison with 2ACK. So we can say that PIGACK has the minimum overhead between all acknowledgment-based methods.
To the best of our knowledge, previous acknowledgment-based methods used misbehaving link detection technique like [1] , [2] , [10] , [13] , [14] . Therefore, we can also claim that PIGACK has the best packet delivery ratio between acknowledgment-based methods when we do not have collusion among misbehaving nodes. We have two reasons for this claim:
1) Misbehaving node detection instead of misbehaving link detection.
2) Informing neighbors of misbehaving nodes.
We use a simple network example, shown in Fig. 5 , for better understanding. The square-shaped nodes are the sources and the circular shaped nodes are the destinations. Node 13 is a malicious node that drops all data packets. Misbehaving link detection methods may try all three routes containing node 13 for sending packets from node 11 to node 15. Note that node 1 also may use node 13 to send packets to node 25. Therefore, each source node should detect the misbehaving node by itself and this detection may need to test all links containing the misbehaving node.
PPT Slide
Lager Image
Simple network example.
On the other hand, in PIGACK method when node 12 detects node 13 as a malicious node, node 12 informs its neighbors (nodes 6, 7, 8, 13, 18, 17, 16, and 11) so these neighbors will not use node 13 on a path to a destination. In fact, one time misbehavior detection is enough for at least half of the sources.
Therefore, PIGACK method has the minimum overhead and maximum packet delivery ratio in comparison with other acknowledgment-based methods. Also we know that acknowledgment-based methods are more accurate than monitoring-based methods because the overhearing technique is not likely to be accurate as explain in [3] .
6. Conclusion
In this paper a special lightweight acknowledgement-based method, named PIGACK, is developed that uses ACK packets of MAC 802.11, instead of adding new ACK packets to the network layer, to piggyback confirmations from a receiver to a sender in the same transmission duration that the sender sends a data packet to the receiver. According to the analytical and simulations results, the proposed method considerably decreases the routing overhead and increases the packet delivery ratio compared to the well-known method (2ACK).
In the future work, we will investigate how to arm PIGACK to resist collusion misbehaving nodes that make collusion blackhole and slander attacks in MANETs.
BIO
Vahid Heydari received a Bachelor of Science from the University of Science and Culture and a Master of Science from Payame Noor University in computer engineering in Tehran, Iran. He is a PhD student in electrical and computer engineering and MS student in cybersecurity simultaneously at the University of Alabama in Huntsville. His research interests include mobile ad-hoc, sensor, and vehicular network security and moving target defense. He is a student member of ACM, IEEE Computer Society and Communications Society.
Seong-Moo Yoo is an Associate Professor of Electrical and Computer Engineering at the University of Alabama in Huntsville (UAH). Before joining UAH, he was an Assistant Professor at Columbus State University, Columbus, Georgia –USA. He earned MS and PhD degrees in Computer Science at the University of Texas at Arlington. His research interests include computer network security and wireless network routing. He has co-authored over 90 scientific articles in refereed journals and international conferences. He is a senior member of IEEE and a member of ACM.
References
Awerbuch B. , Curtmola R. , Holmer D. , Nita-Rotaru C. , Rubens H. 2008 “ODSBR: An on-demand secure Byzantine resilient routing protocol for wireless ad hoc networks,” ACM Trans. Inf. Syst. Secur. 10 (4) 1 - 35    DOI : 10.1145/1284680.1341892
Balakrishnan K. , Deng J. , Varshney P.K. “TWOACK: Preventing Selfishness in Mobile Ad Hoc Networks,” in Proc. of IEEE WCNC 2005 2137 - 2142
Boppana R.V. , Su X. 2011 “On the Effectiveness of Monitoring for Intrusion Detection in Mobile Ad Hoc Networks,” IEEE Trans. Mobile Comput. 10 (8) 1162 - 1174    DOI : 10.1109/TMC.2010.210
Buchegger S. , Boudec J. Y. “Performance analysis of the CONFIDANT protocol: cooperation of nodes: Fairness in dynamic ad-hoc networks,” in Proc. of MobiHOC 2002 226 - 236
Chang C. , Lin J. , Lai F. “Trust-group-based authentication services for mobile ad hoc networks,” in Proc. of ISWPC ’06 2006 37 - 40
Chen T. , Mehani O. , Boreli R. “Trusted routing for VANET,” in Proc. of ITST ’09 in Proc. of ITST ’09 2009 647 - 652
Heydari V. , Yoo S.M. 2015 “Mean Number of Hops in Flooding-Based Ad Hoc Networks,” Submitted to Inf. Process. Lett.
Jain R. 1991 “The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling,” Wiley- Interscience New York
Krovetz T. 2006 “RFC 4418: UMAC: Message Authentication Code using Universal Hashing,”
Liu K. , Deng J. , Varshney P. K. , Balakrishnan K. 2007 “An acknowledgment-based approach for the detection of routing misbehaviour in MANETs,” IEEE Trans. Mobile Comput. 6 (5) 536 - 550    DOI : 10.1109/TMC.2007.1036
Marti S. , Giuli T. , Lai K. , Baker M. 2000 “Mitigating Routing Misbehavior in Mobile Ad Hoc Networks,” in Proc. of MobiCom 255 - 265
Pirzada A. A. , Datta A. , McDonald C. 2006 “Incorporating trust and reputation in the DSR protocol for dependable routing,” Computer Communications 29 (15) 2806 - 2821    DOI : 10.1016/j.comcom.2005.10.032
Shakshuki M. , Kang N. , Sheltami T. R. 2013 “EAACK—A Secure Intrusion-Detection System for MANETs,” IEEE Trans. Ind. Electron. 60 (3) 1089 - 1098    DOI : 10.1109/TIE.2012.2196010
Sun H. M. , Chen C. H. , Ku Y. F. 2012 “A novel acknowledgment-based approach against collude attacks in MANET,” Expert Systems with Applications 39 (9) 7968 - 7975    DOI : 10.1016/j.eswa.2012.01.118
Winjum E. , Spilling P. , Kure O. “Trust Metric Routing to Regulate Routing Cooperation in Mobile Wireless Ad Hoc Networks,” in Proc. of Wireless Conference 2005-European wireless 2005 1 - 8
Xia H. , Jia Z. , Li X. , Ju L. , Sha E. H.-M. 2013 “Trust prediction and trust-based source routing in mobile ad hoc networks,” Ad Hoc Networks 11 (7) 2096 - 2114    DOI : 10.1016/j.adhoc.2012.02.009
Xu K. , Gerla M. , Bae S. “How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks,” in Proc. 2002 IEEE GLOBECOM Nov. 2002 72 - 76
Yao A.C.-C. , Zhao Y. 2013 “Online/Offline Signatures for Low-Power Devices,” IEEE Trans. Inf. Forensics Security 8 (2) 283 - 294    DOI : 10.1109/TIFS.2012.2232653